練習題與詳解 — 儲存配置器

本檔收錄 6 題由易到難的練習。建議流程：先蓋住解答自己寫，卡住再看 「解題思路」，寫完對照「參考解答」。每題完整程式碼在 exercises/：

cc -std=c11 -Wall -Wextra -o /tmp/out exercises/ex1_my_calloc.c && /tmp/out

每題都以 01_kr_malloc.c 的可攜版配置器（靜態 arena 取代 sbrk） 為基底，解答檔各自完整可獨立編譯。動手前請先把 K&R §8.7 的 my_malloc/my_free 讀懂——尤其「size 以 Header 為單位」這件事。

---

練習 1：my_calloc — 配置並清零（難度：基礎）

題目

為配置器加上 my_calloc(n, size)：配置 n 個 size 位元組的元素， 內容全部清零。必須檢查 n * size 的乘法溢位。 用實驗展示：malloc 重用的塊帶著垃圾、calloc 的塊保證是 0、 溢位請求被拒絕。

解題思路

1. calloc = malloc + memset？ 幾乎是，但差一個致命細節。 n * size 兩個 size_t 相乘可能繞回（wrap around）： SIZE_MAX/2 + 1 乘 2 = SIZE_MAX + 2 = 溢位後變成 1。 沒檢查的話 malloc「成功」配出 1 位元組，呼叫者卻以為有 9EB——接下來的寫入全是堆溢位。歷史上不少 CVE 正是這個洞。
2. 溢位判斷式：想驗證 n * size <= SIZE_MAX 但乘法本身會溢位， 改用除法：n > SIZE_MAX / size 即溢位（size 為 0 要先排除， 除以零是 UB）。
3. 為什麼需要清零：free list 重用的塊留著前任的資料。 實驗設計：malloc → 寫入 42 → free → 再 malloc 同大小 （拿回同一塊）→ 讀到 42！換 calloc 再做一次 → 讀到 0。 「垃圾親眼看見」比背規則有效。
4. 邊界：my_calloc(0, 8)——0 位元組是合法請求 （K&R malloc 對 0 也會配出只有 Header 的塊）。

參考解答

/*
 * 練習 1：my_calloc — 配置並清零（含乘法溢位檢查）
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex1_my_calloc.c
 * 執行：/tmp/out
 *
 * 重點：calloc(n, size) = malloc(n*size) + 清零，
 *       但 n*size 可能溢位——溢位檢查是本題的靈魂。
 * 配置器本體 = 01_kr_malloc.c 的可攜版（靜態 arena）。
 */
#include <stdio.h>
#include <string.h>
#include <stddef.h>
#include <stdint.h>     /* SIZE_MAX */

/* ---------------- K&R 配置器本體（同 01_kr_malloc.c） ---------------- */

typedef long Align;

union header {
    struct {
        union header *ptr;
        size_t        size;             /* 大小，以 Header 為單位 */
    } s;
    Align x;
};
typedef union header Header;

#define ARENA_BYTES 65536
#define NALLOC      128

static _Alignas(Header) char arena[ARENA_BYTES];
static size_t arena_used = 0;
static Header  base;
static Header *freep = NULL;

static void my_free(void *ap);

static Header *morecore(size_t nu)
{
    if (nu < NALLOC)
        nu = NALLOC;
    size_t nbytes = nu * sizeof(Header);
    if (arena_used + nbytes > sizeof arena)
        return NULL;
    Header *up = (Header *)(void *)(arena + arena_used);
    arena_used += nbytes;
    up->s.size = nu;
    my_free((void *)(up + 1));
    return freep;
}

static void *my_malloc(size_t nbytes)
{
    Header *p, *prevp;
    size_t nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

    if ((prevp = freep) == NULL) {
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) {
            if (p->s.size == nunits) {
                prevp->s.ptr = p->s.ptr;
            } else {
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void *)(p + 1);
        }
        if (p == freep)
            if ((p = morecore(nunits)) == NULL)
                return NULL;
    }
}

static void my_free(void *ap)
{
    Header *bp = (Header *)ap - 1;
    Header *p;

    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break;

    if (bp + bp->s.size == p->s.ptr) {
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr   = p->s.ptr->s.ptr;
    } else {
        bp->s.ptr = p->s.ptr;
    }
    if (p + p->s.size == bp) {
        p->s.size += bp->s.size;
        p->s.ptr   = bp->s.ptr;
    } else {
        p->s.ptr = bp;
    }
    freep = p;
}

/* ---------------- 本題：my_calloc ---------------- */

/*
 * my_calloc(n, size)：配置 n 個 size 位元組的元素並全部清零。
 *
 * 溢位檢查：n * size 若超過 size_t 的表示範圍會「繞回」成小數字，
 * malloc 配了一小塊、呼叫者卻以為有一大塊——經典的堆溢位漏洞。
 * 判斷式：size != 0 且 n > SIZE_MAX / size 即溢位。
 */
static void *my_calloc(size_t n, size_t size)
{
    if (size != 0 && n > SIZE_MAX / size)   /* n*size 會溢位 */
        return NULL;

    size_t nbytes = n * size;
    void *p = my_malloc(nbytes);
    if (p != NULL)
        memset(p, 0, nbytes);               /* calloc 的第二重任務：清零 */
    return p;
}

int main(void)
{
    /* --- 1. 正常使用：配 10 個 int，驗證全為 0 --- */
    printf("=== my_calloc(10, sizeof(int)) ===\n");
    int *a = my_calloc(10, sizeof(int));
    if (a == NULL) {
        printf("  unexpected NULL\n");
        return 1;
    }
    int all_zero = 1;
    for (int i = 0; i < 10; i++)
        if (a[i] != 0)
            all_zero = 0;
    printf("  all 10 ints are zero: %s\n", all_zero ? "yes" : "NO!");

    /* 對照：my_malloc 不清零（可能拿到上次的殘留值） */
    a[3] = 42;                          /* 弄髒 */
    my_free(a);
    int *b = my_malloc(10 * sizeof(int));   /* 重用同一塊 */
    printf("  recycled my_malloc block, b[3] = %d (garbage from a!)\n",
           b[3]);
    my_free(b);

    int *c = my_calloc(10, sizeof(int));    /* calloc 版本 */
    printf("  recycled my_calloc block, c[3] = %d (zeroed)\n", c[3]);
    my_free(c);

    /* --- 2. 溢位攻擊測試 --- */
    printf("\n=== overflow check ===\n");
    printf("  my_calloc(SIZE_MAX, 2)          -> %s\n",
           my_calloc(SIZE_MAX, 2) == NULL ? "NULL (refused)" : "?!");
    printf("  my_calloc(SIZE_MAX/2 + 1, 2)    -> %s\n",
           my_calloc(SIZE_MAX / 2 + 1, 2) == NULL ? "NULL (refused)" : "?!");
    /* 沒有溢位檢查的版本：n*size = SIZE_MAX/2*2+2 繞回成很小的數，
       malloc 會「成功」配出一小塊——災難的開始。 */

    /* --- 3. 邊界：0 個元素 --- */
    printf("\n=== edge cases ===\n");
    void *z = my_calloc(0, 8);
    printf("  my_calloc(0, 8) -> %s (0 bytes is a legal request)\n",
           z != NULL ? "non-NULL" : "NULL");
    if (z != NULL)
        my_free(z);

    printf("\ndone.\n");
    return 0;
}

程式碼講解

• 溢位檢查只有兩行，卻是本題的全部價值： if (size != 0 && n > SIZE_MAX / size) return NULL; ——順序重要，先排除 size==0 再除。
• memset(p, 0, nbytes) 清的是位元組；「全位元組 0」 對整數型別保證是數值 0（對指標與浮點在特殊平台上 理論上不保證，但 POSIX 平台皆成立——真正的 calloc 也是這樣做的）。
• 實驗中 b[3] = 42 (garbage from a!)：free 只把塊掛回串列， Header 以外的資料原封不動——「free 不清資料」也是 安全上的著名議題（敏感資料要先手動清）。
• 易錯處：把檢查寫成 n * size > SIZE_MAX——恆假 （乘積已經繞回），等於沒檢查。

範例輸出

=== my_calloc(10, sizeof(int)) ===
  all 10 ints are zero: yes
  recycled my_malloc block, b[3] = 42 (garbage from a!)
  recycled my_calloc block, c[3] = 0 (zeroed)

=== overflow check ===
  my_calloc(SIZE_MAX, 2)          -> NULL (refused)
  my_calloc(SIZE_MAX/2 + 1, 2)    -> NULL (refused)

=== edge cases ===
  my_calloc(0, 8) -> non-NULL (0 bytes is a legal request)

done.

---

練習 2：配置器統計（難度：基礎）

題目

為配置器加上統計功能：目前已配置塊數與單位數、free list 的 塊數與總單位數、最大空塊（= 目前能成功配置的最大請求）。 用一連串 alloc/free 觀察合併如何反映在數字上。

解題思路

1. 兩種統計來源，各擅勝場： - 計數器：my_malloc 成功時 ++、my_free 時 --。 O(1)、即時，但只能統計「事件」； - 掃描 free list：走訪環狀串列累計塊數、總量、最大塊。 O(n)，但拿得到「結構」資訊（碎片分布）。 已配置塊數用計數器（配置出去的塊不在任何串列上， 想掃也沒得掃！）；free 側用掃描。
2. morecore 的記帳陷阱——本題最容易踩的坑： morecore 借用 my_free 把新塊掛上串列，而 my_free 會把 計數器減一。解法：morecore 先把計數器墊高， 讓 my_free 的遞減恰好抵銷——或者換個角度想， morecore「假裝」先配置了一大塊再釋放它。
3. 最大可配置位元組：最大空塊有 k 單位，其中 1 單位是 Header，所以答案是 (k-1) * sizeof(Header)。
4. 實驗劇本：配 a、b、c → free(b) 出現洞（free 塊 1→2） → free(c)（c 與 b 的洞、與底部大空塊都接壤，三合一， free 塊 2→1）→ free(a)（全部歸位成一大塊）。 數字的每一步變化都能對照合併的四種情況。

參考解答

/*
 * 練習 2：配置器統計 — 已配置塊數、free list 狀態、最大可配置塊
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex2_stats.c
 * 執行：/tmp/out
 *
 * 重點：兩種統計來源——「計數器」（配置時 ++、釋放時 --）
 *       與「掃描 free list」（塊數、總量、最大塊）；
 *       合併行為直接反映在 free 塊數的變化上。
 */
#include <stdio.h>
#include <string.h>
#include <stddef.h>

/* ---------------- K&R 配置器本體（同 01_kr_malloc.c） ---------------- */

typedef long Align;

union header {
    struct {
        union header *ptr;
        size_t        size;
    } s;
    Align x;
};
typedef union header Header;

#define ARENA_BYTES 65536
#define NALLOC      128

static _Alignas(Header) char arena[ARENA_BYTES];
static size_t arena_used = 0;
static Header  base;
static Header *freep = NULL;

/* --- 本題新增：配置計數器 --- */
static int    g_alloc_blocks = 0;   /* 目前「已配置、未釋放」的塊數 */
static size_t g_alloc_units  = 0;   /* 已配置的總單位數（含 Header） */

static void my_free(void *ap);

static Header *morecore(size_t nu)
{
    if (nu < NALLOC)
        nu = NALLOC;
    size_t nbytes = nu * sizeof(Header);
    if (arena_used + nbytes > sizeof arena)
        return NULL;
    Header *up = (Header *)(void *)(arena + arena_used);
    arena_used += nbytes;
    up->s.size = nu;

    /* morecore 借用 my_free 掛新塊——先把計數器「墊高」，
       抵銷 my_free 內的遞減，新塊才不會被算成一次釋放 */
    g_alloc_blocks++;
    g_alloc_units += nu;
    my_free((void *)(up + 1));
    return freep;
}

static void *my_malloc(size_t nbytes)
{
    Header *p, *prevp;
    size_t nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

    if ((prevp = freep) == NULL) {
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) {
            if (p->s.size == nunits) {
                prevp->s.ptr = p->s.ptr;
            } else {
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            g_alloc_blocks++;               /* ★ 統計：配置成功 */
            g_alloc_units += p->s.size;
            return (void *)(p + 1);
        }
        if (p == freep)
            if ((p = morecore(nunits)) == NULL)
                return NULL;
    }
}

static void my_free(void *ap)
{
    Header *bp = (Header *)ap - 1;
    Header *p;

    g_alloc_blocks--;                       /* ★ 統計：釋放 */
    g_alloc_units -= bp->s.size;

    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break;

    if (bp + bp->s.size == p->s.ptr) {
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr   = p->s.ptr->s.ptr;
    } else {
        bp->s.ptr = p->s.ptr;
    }
    if (p + p->s.size == bp) {
        p->s.size += bp->s.size;
        p->s.ptr   = bp->s.ptr;
    } else {
        p->s.ptr = bp;
    }
    freep = p;
}

/* ---------------- 本題：統計功能 ---------------- */

struct alloc_stats {
    int    alloc_blocks;    /* 已配置塊數（計數器） */
    size_t alloc_units;     /* 已配置單位數（計數器） */
    int    free_blocks;     /* free list 上的塊數（掃描） */
    size_t free_units;      /* free list 總單位數（掃描） */
    size_t largest_units;   /* 最大空塊（掃描） */
};

/* 掃一圈 free list 收集統計；計數器直接抄全域值 */
static struct alloc_stats get_stats(void)
{
    struct alloc_stats st = {
        .alloc_blocks = g_alloc_blocks,
        .alloc_units  = g_alloc_units,
    };
    if (freep == NULL)
        return st;

    const Header *p = base.s.ptr;
    while (p != &base) {                    /* 環狀串列：繞回 base 停 */
        st.free_blocks++;
        st.free_units += p->s.size;
        if (p->s.size > st.largest_units)
            st.largest_units = p->s.size;
        p = p->s.ptr;
    }
    return st;
}

static void print_stats(const char *when)
{
    struct alloc_stats st = get_stats();
    /* 最大可配置位元組：最大空塊扣掉 1 單位的 Header */
    size_t max_bytes =
        st.largest_units > 0 ? (st.largest_units - 1) * sizeof(Header) : 0;

    printf("  [%s]\n", when);
    printf("    allocated: %d block(s), %zu units (%zu bytes with headers)\n",
           st.alloc_blocks, st.alloc_units,
           st.alloc_units * sizeof(Header));
    printf("    free list: %d block(s), %zu units; largest %zu units"
           " -> my_malloc(%zu) max\n",
           st.free_blocks, st.free_units, st.largest_units, max_bytes);
}

int main(void)
{
    printf("=== fresh allocator ===\n");
    print_stats("before anything");

    printf("\n=== allocate a, b, c ===\n");
    char *a = my_malloc(100);
    char *b = my_malloc(200);
    char *c = my_malloc(300);
    (void)a;
    print_stats("after 3 allocations");

    printf("\n=== free b: a hole appears (free blocks 1 -> 2) ===\n");
    my_free(b);
    print_stats("after free(b)");

    printf("\n=== free c: adjacent to b's hole -> coalesce ===\n");
    /* c 與 b 的洞、又與底部的大空塊都接壤：
       三塊合併成一塊，free 塊數 2 -> 1，最大塊反而變大 */
    my_free(c);
    print_stats("after free(c)");

    printf("\n=== free a: everything coalesces back ===\n");
    my_free(a);
    print_stats("after free(a)");

    printf("\nnote: allocated blocks is back to 0 and the free list\n"
           "collapsed into one big block -- no leaks, no fragmentation.\n");
    return 0;
}

程式碼講解

• get_stats 掃描環狀串列的終止條件是 p != &base—— base 是 size 0 的哨兵，從 base.s.ptr 出發繞一圈回到它。
• 已配置單位數在「剛剛好」與「切割」兩個分支都要加 p->s.size（切割分支 p 已指向尾段、size 已是 nunits）。
• 輸出對帳：a+b+c = 8+14+20 = 42 單位、free 86 單位， 42+86 = 128 = 一次 morecore 的量——總量守恆是 統計正確性的第一驗證。
• free(c) 後 free 塊 2→1 而最大塊 86→120：塊數變少、 塊變大——這就是合併的意義（對照練習 3 的碎片化）。
• 易錯處：morecore 忘記墊計數器——統計會出現 「配置 3 塊、卻記錄 2 塊」的漂移，且 arena 每擴展一次 漂移一次。

範例輸出

=== fresh allocator ===
  [before anything]
    allocated: 0 block(s), 0 units (0 bytes with headers)
    free list: 0 block(s), 0 units; largest 0 units -> my_malloc(0) max

=== allocate a, b, c ===
  [after 3 allocations]
    allocated: 3 block(s), 42 units (672 bytes with headers)
    free list: 1 block(s), 86 units; largest 86 units -> my_malloc(1360) max

=== free b: a hole appears (free blocks 1 -> 2) ===
  [after free(b)]
    allocated: 2 block(s), 28 units (448 bytes with headers)
    free list: 2 block(s), 100 units; largest 86 units -> my_malloc(1360) max

=== free c: adjacent to b's hole -> coalesce ===
  [after free(c)]
    allocated: 1 block(s), 8 units (128 bytes with headers)
    free list: 1 block(s), 120 units; largest 120 units -> my_malloc(1904) max

=== free a: everything coalesces back ===
  [after free(a)]
    allocated: 0 block(s), 0 units (0 bytes with headers)
    free list: 1 block(s), 128 units; largest 128 units -> my_malloc(2032) max

note: allocated blocks is back to 0 and the free list
collapsed into one big block -- no leaks, no fragmentation.

---

練習 3：first-fit vs best-fit（難度：進階）

題目

把 first-fit 改成 best-fit（掃完整條 free list，挑「最小但夠用」 的塊），然後設計一組配置序列，讓 first-fit 因碎片化而失敗、 best-fit 成功。arena 縮成恰好 128 單位讓「耗盡」可控。

解題思路

1. 兩種策略一句話：first-fit 拿第一個夠大的塊 （K&R 原版）；best-fit 拿最小的夠用塊。 直覺上 best-fit「省」，但要掃完整條串列（O(n) 必然）。
2. 讓差異現形的劇本——關鍵是「一大一小兩個洞 + 兩個請求」：

洞：      [40 units]        [10 units]
請求 8：  first-fit 從 40 切 -> 剩 [32] [10]
          best-fit  從 10 切 -> 剩 [40] [ 2]
請求 36： first-fit：32 不夠、10 不夠 -> 失敗！
          best-fit ：40 夠 -> 成功

first-fit 把大洞切碎了；best-fit 犧牲小洞、保住大洞。 3. 洞怎麼挖：塊與塊之間要放「隔板」（allocated 的小塊）， 否則釋放時兩個洞會合併成一個，實驗就失效—— 合併是配置器的優點，本題卻要刻意繞開它。 4. 單位數精準控制：my_malloc(nbytes) 的單位數是 ceil(nbytes/16)+1，反推 UNITS(n) = (n-1)*16 位元組 恰好配出 n 單位——測資直接以單位表達，輸出可對帳。 5. best-fit 的實作：從 freep 出發恰好繞一圈 （do...while (prevp != freep)），記住最小合格塊與其前手； 切割邏輯與 first-fit 共用（抽成 take_from）。 6. 公平比較：兩輪之間 reset_allocator() 清空一切， 並在挖完洞後統一 freep = &base——搜尋起點一致， 結果才可重現。 7. best-fit 的暗面（輸出裡也看得到）：切小洞留下 2 單位的 「碎屑」（sliver）——best-fit 傾向製造大量小到沒人能用的 碎片，這是實務配置器不採用純 best-fit 的原因之一。

參考解答

/*
 * 練習 3：first-fit vs best-fit — 同一配置序列的碎片化比較
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex3_best_fit.c
 * 執行：/tmp/out
 *
 * 重點：兩種放置策略對「洞」的挑法不同——
 *       first-fit 拿第一個夠大的（可能切碎大洞）、
 *       best-fit 拿最小的夠用的（保住大洞）。
 *       用刻意設計的序列讓 first-fit 失敗、best-fit 成功。
 *
 * 為了讓「記憶體耗盡」可控，本題把 arena 縮成恰好 128 單位。
 */
#include <stdio.h>
#include <string.h>
#include <stddef.h>

typedef long Align;

union header {
    struct {
        union header *ptr;
        size_t        size;
    } s;
    Align x;
};
typedef union header Header;

/* arena 恰好 = NALLOC 單位：morecore 只成功一次，之後配置只能靠 free list */
#define NALLOC      128
#define ARENA_BYTES (NALLOC * sizeof(Header))

static _Alignas(Header) char arena[ARENA_BYTES];
static size_t arena_used = 0;
static Header  base;
static Header *freep = NULL;

/* 放置策略開關 */
enum policy { FIRST_FIT, BEST_FIT };
static enum policy g_policy = FIRST_FIT;

static void my_free(void *ap);

static Header *morecore(size_t nu)
{
    if (nu < NALLOC)
        nu = NALLOC;
    size_t nbytes = nu * sizeof(Header);
    if (arena_used + nbytes > sizeof arena)
        return NULL;
    Header *up = (Header *)(void *)(arena + arena_used);
    arena_used += nbytes;
    up->s.size = nu;
    my_free((void *)(up + 1));
    return freep;
}

/* 從塊 p 切出 nunits 給呼叫者（p 的前手是 prevp） */
static void *take_from(Header *prevp, Header *p, size_t nunits)
{
    if (p->s.size == nunits) {
        prevp->s.ptr = p->s.ptr;        /* 剛剛好：整塊摘走 */
    } else {
        p->s.size -= nunits;            /* 太大：切尾端 */
        p += p->s.size;
        p->s.size = nunits;
    }
    freep = prevp;
    return (void *)(p + 1);
}

static void *my_malloc(size_t nbytes)
{
    Header *p, *prevp;
    size_t nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

    if ((prevp = freep) == NULL) {
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }

    if (g_policy == FIRST_FIT) {
        /* K&R 原版：走到第一個夠大的塊就用 */
        for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
            if (p->s.size >= nunits)
                return take_from(prevp, p, nunits);
            if (p == freep)
                if ((p = morecore(nunits)) == NULL)
                    return NULL;
        }
    }

    /* BEST_FIT：掃完整圈，挑「最小但夠用」的塊 */
    for (;;) {
        Header *best = NULL, *best_prev = NULL;
        prevp = freep;
        p = prevp->s.ptr;
        do {
            if (p->s.size >= nunits &&
                (best == NULL || p->s.size < best->s.size)) {
                best = p;
                best_prev = prevp;
            }
            prevp = p;
            p = p->s.ptr;
        } while (prevp != freep);       /* 恰好繞一圈 */

        if (best != NULL)
            return take_from(best_prev, best, nunits);
        if (morecore(nunits) == NULL)
            return NULL;
    }
}

static void my_free(void *ap)
{
    Header *bp = (Header *)ap - 1;
    Header *p;

    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break;

    if (bp + bp->s.size == p->s.ptr) {
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr   = p->s.ptr->s.ptr;
    } else {
        bp->s.ptr = p->s.ptr;
    }
    if (p + p->s.size == bp) {
        p->s.size += bp->s.size;
        p->s.ptr   = bp->s.ptr;
    } else {
        p->s.ptr = bp;
    }
    freep = p;
}

/* ---------------- 實驗工具 ---------------- */

static void reset_allocator(void)
{
    arena_used = 0;
    freep = NULL;
    memset(&base, 0, sizeof base);
    memset(arena, 0, sizeof arena);
}

static void dump_freelist(void)
{
    printf("    free list:");
    const Header *p = base.s.ptr;
    while (p != &base) {
        printf(" [off=%4td size=%3zu]",
               (const char *)p - arena, p->s.size);
        p = p->s.ptr;
    }
    printf("\n");
}

/* 位元組數 <-> 單位數：讓測資直接以「單位」表達，好對帳 */
#define UNITS(n) (((n) - 1) * sizeof(Header))   /* 請求 n 單位的位元組數 */

/*
 * 場景（單位數）：
 *   小洞塊 10、隔板 2、大洞塊 40、隔板 2、其餘 74 —— 恰好 128。
 *   釋放小洞與大洞 -> free list = 大洞(40) 、小洞(10)（位址序）。
 *   然後請求 8 單位、再請求 36 單位。
 */
static void run_scenario(enum policy pol, const char *name)
{
    reset_allocator();
    g_policy = pol;
    printf("=== %s ===\n", name);

    void *small = my_malloc(UNITS(10));     /* 位址最高（從尾端切） */
    void *sep1  = my_malloc(UNITS(2));
    void *big   = my_malloc(UNITS(40));
    void *sep2  = my_malloc(UNITS(2));
    void *rest  = my_malloc(UNITS(74));     /* 吃光剩餘空間 */

    my_free(big);                           /* 挖出 40 單位的洞 */
    my_free(small);                         /* 挖出 10 單位的洞 */
    freep = &base;                          /* 統一搜尋起點，結果可重現 */
    printf("  two holes: 40 units (low addr) and 10 units (high addr)\n");
    dump_freelist();

    printf("  request 8 units:\n");
    void *r1 = my_malloc(UNITS(8));
    printf("    -> got offset %td\n", (char *)r1 - arena);
    dump_freelist();

    printf("  request 36 units:\n");
    void *r2 = my_malloc(UNITS(36));
    if (r2 == NULL)
        printf("    -> NULL: the 40-unit hole was broken up. FRAGMENTED!\n");
    else
        printf("    -> got offset %td. big hole survived.\n",
               (char *)r2 - arena);
    dump_freelist();

    /* 清理（NULL 免釋放） */
    my_free(r1);
    if (r2 != NULL)
        my_free(r2);
    my_free(sep1);
    my_free(sep2);
    my_free(rest);
    printf("\n");
}

int main(void)
{
    printf("arena = exactly %d units; two holes then two requests.\n\n",
           NALLOC);

    run_scenario(FIRST_FIT, "FIRST-FIT (K&R original)");
    run_scenario(BEST_FIT, "BEST-FIT");

    printf("lesson: first-fit is O(first match) and fast, but can carve\n"
           "up big holes; best-fit preserves big holes at the cost of a\n"
           "full scan (and it tends to leave tiny slivers instead).\n");
    return 0;
}

程式碼講解

• take_from(prevp, p, nunits)：把 K&R 的「剛剛好摘走／太大 切尾端」抽成函式，兩種策略共用——策略只決定選哪塊， 切割方式不變。
• best-fit 迴圈的訪問順序：prevp 從 freep 出發， 每個節點恰好當一次 p；比較 p->s.size < best->s.size 找最小合格者。
• ARENA_BYTES (NALLOC * sizeof(Header))：arena 恰好一次 morecore 的量——第二次 morecore 必然失敗， 「記憶體耗盡」變成可控的實驗條件。
• 輸出對帳：first-fit 請求 8 後大洞 40→32；best-fit 請求 8 後 小洞 10→2。請求 36 的成敗與預測一致。
• 易錯處：兩輪實驗共用 arena 不重置——第二輪的 free list 繼承第一輪的碎片，比較毫無意義；「實驗要控制變因」 寫程式也一樣。

範例輸出

arena = exactly 128 units; two holes then two requests.

=== FIRST-FIT (K&R original) ===
  two holes: 40 units (low addr) and 10 units (high addr)
    free list: [off=1216 size= 40] [off=1888 size= 10]
  request 8 units:
    -> got offset 1744
    free list: [off=1216 size= 32] [off=1888 size= 10]
  request 36 units:
    -> NULL: the 40-unit hole was broken up. FRAGMENTED!
    free list: [off=1216 size= 32] [off=1888 size= 10]

=== BEST-FIT ===
  two holes: 40 units (low addr) and 10 units (high addr)
    free list: [off=1216 size= 40] [off=1888 size= 10]
  request 8 units:
    -> got offset 1936
    free list: [off=1216 size= 40] [off=1888 size=  2]
  request 36 units:
    -> got offset 1296. big hole survived.
    free list: [off=1216 size=  4] [off=1888 size=  2]

lesson: first-fit is O(first match) and fast, but can carve
up big holes; best-fit preserves big holes at the cost of a
full scan (and it tends to leave tiny slivers instead).

---

練習 4：bfree — 收編外來記憶體（K&R 習題 8-8）（難度：進階）

題目

實作 bfree(p, n)：把呼叫者提供的任意緩衝區（位址可能不對齊、 長度任意）掛進 free list，回傳實際入列的單位數；太小則拒收回 0。 示範：配置器在沒有任何記憶體來源的情況下，靠捐贈的緩衝區 服務 malloc。

解題思路

1. 問題的核心是「外來位址不可信」：my_free 的前提是 指標來自 my_malloc（Header 就位、位址對齊）。bfree 收的是 任意位址——第一步必須自己把秩序建立起來。
2. 向上對齊（align up）的慣用式：

aligned = (addr + A - 1) & ~(A - 1);    /* A = sizeof(Header)，2 的冪 */

與進位除法同構：先加 A-1 再把低位清零。位址運算要經過 uintptr_t——指標不能直接做位元運算。 3. 長度的三重修正： - 對齊耗掉 aligned - addr 位元組（起點右移）； - 剩餘位元組向下取整成單位數（多報會越界）； - 不足 2 單位（Header + 至少 1 單位資料）拒收—— 只有 Header 的塊永遠配不出去，掛上去只是垃圾。 4. 入列直接借 my_free：填好 size 後呼叫 my_free(hp + 1)——位址排序、相鄰合併全部免費繼承。 輸出的最後一幕就是彩蛋：兩塊獨立捐贈的靜態陣列剛好 前後相鄰，free 之後自動合併成一塊（63+32＝95 單位）。 5. 驗證設計：把 morecore 拿掉（要不到記憶體就 NULL）， 一開始 malloc 必然失敗；捐贈後成功，且回傳的指標 落在捐贈陣列的範圍內——「配置器真的在用捐來的記憶體」 有實據。

參考解答

/*
 * 練習 4：bfree — 把任意記憶體掛進 free list（K&R 習題 8-8）
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex4_bfree.c
 * 執行：/tmp/out
 *
 * 重點：外來的緩衝區位址不一定對齊 Header 邊界——
 *       要先把起點「向上取整」到對齊邊界、長度向下修正，
 *       夠放 Header + 至少 1 單位資料才收；否則拒收。
 */
#include <stdio.h>
#include <string.h>
#include <stddef.h>
#include <stdint.h>     /* uintptr_t */

/* ---------------- K&R 配置器本體（同 01_kr_malloc.c） ---------------- */

typedef long Align;

union header {
    struct {
        union header *ptr;
        size_t        size;
    } s;
    Align x;
};
typedef union header Header;

/* 本題把 arena 縮小到 0：所有可用記憶體都來自 bfree 捐贈，
   更能證明配置器真的在用捐來的緩衝區。 */
static Header  base;
static Header *freep = NULL;

static void my_free(void *ap);

static void *my_malloc(size_t nbytes)
{
    Header *p, *prevp;
    size_t nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

    if ((prevp = freep) == NULL) {
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) {
            if (p->s.size == nunits) {
                prevp->s.ptr = p->s.ptr;
            } else {
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void *)(p + 1);
        }
        if (p == freep)
            return NULL;                /* 沒有 morecore：要不到就 NULL */
    }
}

static void my_free(void *ap)
{
    Header *bp = (Header *)ap - 1;
    Header *p;

    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break;

    if (bp + bp->s.size == p->s.ptr) {
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr   = p->s.ptr->s.ptr;
    } else {
        bp->s.ptr = p->s.ptr;
    }
    if (p + p->s.size == bp) {
        p->s.size += bp->s.size;
        p->s.ptr   = bp->s.ptr;
    } else {
        p->s.ptr = bp;
    }
    freep = p;
}

/* ---------------- 本題：bfree ---------------- */

/*
 * bfree(p, n)：把呼叫者提供的 n 位元組緩衝區捐給 free list。
 * 回傳實際入列的單位數；緩衝區太小（湊不出 Header + 1 單位）回 0。
 *
 * 步驟：
 *   1. 把起點向上對齊到 sizeof(Header) 邊界（外來位址不可信）；
 *   2. 對齊耗掉的位元組從 n 扣除；
 *   3. 剩餘位元組換算成整數單位（向下取整——不能多報）；
 *   4. 不足 2 單位（Header + 至少 1 單位資料）拒收；
 *   5. 填 size、呼叫 my_free 入列（順便獲得合併能力）。
 */
static size_t bfree(void *p, size_t n)
{
    uintptr_t addr = (uintptr_t)p;
    uintptr_t aligned = (addr + sizeof(Header) - 1)
                        & ~(uintptr_t)(sizeof(Header) - 1);
    size_t skip = (size_t)(aligned - addr);     /* 對齊犧牲的位元組 */

    if (n < skip)
        return 0;
    size_t usable = n - skip;
    size_t units = usable / sizeof(Header);     /* 向下取整 */
    if (units < 2)                              /* 連 Header+1 單位都不夠 */
        return 0;

    Header *hp = (Header *)(void *)aligned;
    hp->s.size = units;
    my_free((void *)(hp + 1));                  /* 借 my_free 入列＋合併 */
    return units;
}

static void dump_freelist(const char *when)
{
    printf("  free list %s:", when);
    if (freep == NULL) {
        printf(" (empty)\n");
        return;
    }
    const Header *p = base.s.ptr;
    while (p != &base) {
        printf(" [size=%zu]", p->s.size);
        p = p->s.ptr;
    }
    printf("\n");
}

/* 捐贈用的緩衝區（獨立的靜態陣列，模擬「外來記憶體」） */
static _Alignas(Header) char donation_a[1024];
static _Alignas(Header) char donation_b[512];

int main(void)
{
    printf("sizeof(Header) = %zu\n\n", sizeof(Header));

    /* 初始化退化串列（沒有任何可用記憶體） */
    printf("=== allocator with NO memory source ===\n");
    void *fail = my_malloc(64);
    printf("  my_malloc(64) -> %s\n\n",
           fail == NULL ? "NULL (nothing to give)" : "?!");

    /* --- 1. 捐一塊「故意不對齊」的緩衝區 --- */
    printf("=== donate donation_a+1 (deliberately misaligned) ===\n");
    size_t got = bfree(donation_a + 1, sizeof donation_a - 1);
    printf("  bfree(%zu bytes at odd address) -> %zu units accepted\n",
           sizeof donation_a - 1, got);
    dump_freelist("after donation");

    /* --- 2. 從捐來的記憶體配置 --- */
    printf("\n=== allocate from donated memory ===\n");
    char *s = my_malloc(100);
    printf("  my_malloc(100) -> %s\n", s != NULL ? "ok" : "NULL?!");
    strcpy(s, "living inside donation_a");
    printf("  s = \"%s\"\n", s);
    printf("  s is inside donation_a: %s\n",
           (s >= donation_a && s < donation_a + sizeof donation_a)
               ? "yes" : "no");
    dump_freelist("after malloc");

    /* --- 3. 再捐一塊，free list 出現兩個來源 --- */
    printf("\n=== donate a second buffer ===\n");
    got = bfree(donation_b, sizeof donation_b);
    printf("  bfree(donation_b, %zu) -> %zu units\n",
           sizeof donation_b, got);
    dump_freelist("two donations");

    /* --- 4. 太小的捐贈要拒收 --- */
    printf("\n=== donations too small to hold Header + 1 unit ===\n");
    static char tiny[16];
    printf("  bfree(tiny, 16)  -> %zu units (need >= 2 units = %zu bytes)\n",
           bfree(tiny, sizeof tiny), 2 * sizeof(Header));
    printf("  bfree(buf+1, 17) -> %zu units (alignment eats the slack)\n",
           bfree(donation_a + 1, 17));

    printf("\n");
    my_free(s);
    dump_freelist("after final free (s coalesced back)");

    printf("\ndone: bfree turned foreign buffers into heap space.\n");
    return 0;
}

程式碼講解

• (uintptr_t)p → 對齊運算 → (Header *)(void *)aligned： 指標→整數→運算→指標的完整往返；中途經過 void * 避開對齊警告（我們剛剛才「製造」了對齊，是安全的）。
• skip = aligned - addr 後先檢查 n < skip——緩衝區 可能短到連對齊都撐不過去，先擋再減，無號減法不會繞回。
• 拒收測試兩個角度：tiny[16] 絕對大小不足； donation_a+1, 17 名目上 17 位元組、對齊吃掉 15 之後 只剩 2——對齊的代價要算進驗收。
• 已捐過的記憶體再捐一次是呼叫者的錯（如同 double-free）， 本題的第二次 donation_a+1 呼叫因太小被拒， 恰好沒踩到這個雷——真要防禦得記錄捐贈範圍。
• 易錯處：單位數用進位除法（照抄 my_malloc）—— 多報一單位，尾端 15 位元組不是你的，寫入即踩人。 malloc 是「需求至少要滿足」所以進位；bfree 是 「供給不能誇大」所以捨去——方向相反。

範例輸出

sizeof(Header) = 16

=== allocator with NO memory source ===
  my_malloc(64) -> NULL (nothing to give)

=== donate donation_a+1 (deliberately misaligned) ===
  bfree(1023 bytes at odd address) -> 63 units accepted
  free list after donation: [size=63]

=== allocate from donated memory ===
  my_malloc(100) -> ok
  s = "living inside donation_a"
  s is inside donation_a: yes
  free list after malloc: [size=55]

=== donate a second buffer ===
  bfree(donation_b, 512) -> 32 units
  free list two donations: [size=55] [size=32]

=== donations too small to hold Header + 1 unit ===
  bfree(tiny, 16)  -> 0 units (need >= 2 units = 32 bytes)
  bfree(buf+1, 17) -> 0 units (alignment eats the slack)

  free list after final free (s coalesced back): [size=95]

done: bfree turned foreign buffers into heap space.

---

練習 5：魔數防線 — 偵測 double-free 與 Header 踩壞（難度：挑戰）

題目

為每個塊的 Header 加「魔數」欄位：配置時蓋「使用中」印章、 釋放時驗印後改蓋「已釋放」。用實驗觸發並攔截三種災難： double-free、越界寫入踩壞鄰塊 Header、free 野指標。 所有攔截都不得讓程式崩潰。

解題思路

1. 問題背景：K&R 版完全信任呼叫者——free 兩次、 free 野指標、越界寫入，都會把 free list 攪爛， 而崩潰點遠在事發之後（heap corruption 難查的原因）。 防線的思路：在 Header 裡放一個「不太可能自然出現」的 值，free 時檢查它還在不在。
2. 兩個印章的狀態機：

my_malloc          my_free（驗印）
────────>  ALLOC  ──────────> FREE
             ^                  │
             └──── my_malloc ───┘

free 時看到 FREE   -> double-free（這塊已在串列上）
free 時看到其他值  -> Header 被踩 / 野指標

3. 偵測後怎麼辦：報警（stderr）並拒絕操作—— 繼續走 free 流程只會把災難擴大。實務配置器 （macOS 的 malloc、glibc）遇到這種情況通常直接 abort， 本題為了展示三種情況選擇「攔截後繼續」。
4. 越界實驗的精確計算：Header 加了 magic 後是 24 位元組； 請求 64 位元組 → 進位成 4 單位 → 資料區實得 72 位元組。 後配的塊在低位址（K&R 從尾端切割），它的資料區 往上長就是先配塊的 Header——寫 96 位元組恰好 把鄰塊 Header 全蓋成 'X'（magic 變 0x58585858， 輸出裡看得到 'X' 的 ASCII 碼）。
5. 偵測的極限：魔數擋得住「踩壞 Header」與 double-free， 擋不住「踩壞鄰塊資料區」（magic 沒事）； 也可能漏報（攻擊者恰好寫回正確 magic）。 實務工具再加金絲雀、隔離區、影子記憶體 （AddressSanitizer 的做法）——防線是機率遊戲。

參考解答

/*
 * 練習 5：魔數防線 — 偵測 double-free 與 Header 踩壞
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex5_magic.c
 * 執行：/tmp/out
 *
 * 重點：Header 加一個 magic 欄位，配置時蓋「使用中」印章、
 *       釋放時驗印再改蓋「已釋放」——
 *       double-free 與越界寫入都會在 free 的當下被抓到，
 *       而不是等到 free list 被攪爛之後才神祕崩潰。
 */
#include <stdio.h>
#include <string.h>
#include <stddef.h>
#include <stdint.h>

/* ---------------- 帶魔數的 K&R 配置器 ---------------- */

typedef long Align;

#define MAGIC_ALLOC 0xA110CA7EU     /* "allocate" 的印章 */
#define MAGIC_FREE  0xF7EEB10CU     /* "free block" 的印章 */

union header {
    struct {
        union header *ptr;
        size_t        size;
        uint32_t      magic;        /* ★ 新增：狀態印章 */
    } s;
    Align x;                        /* union 仍保住對齊 */
};
typedef union header Header;

#define ARENA_BYTES 65536
#define NALLOC      128

static _Alignas(Header) char arena[ARENA_BYTES];
static size_t arena_used = 0;
static Header  base;
static Header *freep = NULL;

static void my_free(void *ap);

static Header *morecore(size_t nu)
{
    if (nu < NALLOC)
        nu = NALLOC;
    size_t nbytes = nu * sizeof(Header);
    if (arena_used + nbytes > sizeof arena)
        return NULL;
    Header *up = (Header *)(void *)(arena + arena_used);
    arena_used += nbytes;
    up->s.size = nu;
    up->s.magic = MAGIC_ALLOC;      /* 讓 my_free 的驗印通過 */
    my_free((void *)(up + 1));
    return freep;
}

static void *my_malloc(size_t nbytes)
{
    Header *p, *prevp;
    size_t nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

    if ((prevp = freep) == NULL) {
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
        base.s.magic = MAGIC_FREE;
    }
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) {
            if (p->s.size == nunits) {
                prevp->s.ptr = p->s.ptr;
            } else {
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            p->s.magic = MAGIC_ALLOC;       /* ★ 蓋「使用中」印章 */
            return (void *)(p + 1);
        }
        if (p == freep)
            if ((p = morecore(nunits)) == NULL)
                return NULL;
    }
}

/*
 * my_free：入列前先驗印。
 *   MAGIC_FREE  -> double-free：這塊已經在 free list 上了
 *   其他值      -> Header 被踩壞（越界寫入）或 free 野指標
 * 兩種情況都「報警並拒絕操作」——繼續處理只會把串列攪爛。
 */
static void my_free(void *ap)
{
    Header *bp = (Header *)ap - 1;
    Header *p;

    if (bp->s.magic == MAGIC_FREE) {
        fprintf(stderr,
                "  [ALLOCATOR] double-free detected for %p -- ignored\n",
                ap);
        return;
    }
    if (bp->s.magic != MAGIC_ALLOC) {
        fprintf(stderr,
                "  [ALLOCATOR] corrupted header at %p "
                "(magic=0x%08X) -- heap overflow? ignored\n",
                ap, bp->s.magic);
        return;
    }
    bp->s.magic = MAGIC_FREE;               /* ★ 改蓋「已釋放」 */

    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break;

    if (bp + bp->s.size == p->s.ptr) {
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr   = p->s.ptr->s.ptr;
    } else {
        bp->s.ptr = p->s.ptr;
    }
    if (p + p->s.size == bp) {
        p->s.size += bp->s.size;
        p->s.ptr   = bp->s.ptr;
    } else {
        p->s.ptr = bp;
    }
    freep = p;
}

int main(void)
{
    printf("sizeof(Header) = %zu (ptr + size + magic, union-aligned)\n\n",
           sizeof(Header));

    /* --- 1. 正常流程：驗印通過 --- */
    printf("=== normal allocate / free ===\n");
    char *a = my_malloc(64);
    strcpy(a, "well-behaved block");
    printf("  a = \"%s\"\n", a);
    my_free(a);
    printf("  free(a): ok, no complaints\n");

    /* --- 2. double-free：第二次 free 被攔下 --- */
    printf("\n=== double free ===\n");
    char *b = my_malloc(64);
    my_free(b);
    printf("  first  free(b): ok\n");
    fflush(stdout);
    my_free(b);                             /* 會被偵測並忽略 */
    printf("  second free(b): rejected, free list still intact\n");

    /* --- 3. 越界寫入踩壞鄰塊 Header --- */
    printf("\n=== buffer overflow smashing the next header ===\n");
    char *c = my_malloc(64);                /* 先配（位址較高） */
    char *d = my_malloc(64);                /* 後配（緊貼在 c 下方） */
    strcpy(c, "victim block c");

    /*
     * 要求 64 位元組，進位後 d 實得 4 單位 = 資料區 3*24 = 72 位元組。
     * d 緊貼在 c 下方，d 的資料區再往上就是 c 的 Header（24 位元組）。
     * 故意寫 96 位元組：越界 24 位元組，把 c 的 Header 整個蓋成 'X'。
     */
    printf("  writing 96 bytes into d's 72-byte data area...\n");
    memset(d, 'X', 96);                     /* ★ 越界！ */

    fflush(stdout);
    my_free(c);                             /* 驗印失敗：Header 被踩 */
    printf("  free(c) was rejected -- corruption caught at free time,\n"
           "  not as a mystery crash three functions later.\n");

    my_free(d);                             /* d 自己的 Header 沒事 */
    printf("  free(d): ok (its own header was untouched)\n");

    /* --- 4. free 野指標 --- */
    printf("\n=== freeing a pointer that never came from my_malloc ===\n");
    static _Alignas(Header) char not_heap[64];  /* 全 0 的靜態陣列 */
    fflush(stdout);
    my_free(not_heap + sizeof(Header));     /* 假 Header 的 magic 是 0 */
    printf("  rejected as well.\n");

    printf("\ndone: magic numbers turn silent corruption into loud errors.\n");
    return 0;
}

程式碼講解

• Header 變成 {ptr, size, magic} + Align x 的 union： 24 位元組、對齊不變——所有單位運算的程式碼一行都 不用改，這是「size 以 Header 為單位」設計的又一次回報。
• morecore 也要蓋 ALLOC 印章：它借用 my_free 入列， 不蓋章會被自己的驗印擋下——改了不變量（invariant）， 所有路徑都要遵守。
• 驗印的兩個分支順序：先查 == MAGIC_FREE（double-free 的專屬訊息），再查 != MAGIC_ALLOC（其他一切異常）—— 訊息越精確，除錯越快。
• memset(d, 'X', 96) 越界 24 位元組：故意的「犯罪現場」。 隨後 free(c) 當場被攔，訊息裡 magic=0x58585858 就是四個 'X'——證據確鑿。
• 野指標測試用全零的靜態陣列：偽 Header 的 magic 是 0， 兩個印章都不是 → 攔截。
• 易錯處：把 magic 放在資料區後面（塊尾）才能抓 「本塊自己的溢位」——本題的 Header magic 抓的是 「鄰塊踩過來」；兩種佈局互補，實務配置器兩個都放 （頭尾金絲雀）。

範例輸出

sizeof(Header) = 24 (ptr + size + magic, union-aligned)

=== normal allocate / free ===
  a = "well-behaved block"
  free(a): ok, no complaints

=== double free ===
  first  free(b): ok
  [ALLOCATOR] double-free detected for 0x100210c20 -- ignored
  second free(b): rejected, free list still intact

=== buffer overflow smashing the next header ===
  writing 96 bytes into d's 72-byte data area...
  [ALLOCATOR] corrupted header at 0x100210c20 (magic=0x58585858) -- heap overflow? ignored
  free(c) was rejected -- corruption caught at free time,
  not as a mystery crash three functions later.
  free(d): ok (its own header was untouched)

=== freeing a pointer that never came from my_malloc ===
  [ALLOCATOR] corrupted header at 0x100210018 (magic=0x00000000) -- heap overflow? ignored
  rejected as well.

done: magic numbers turn silent corruption into loud errors.

（指標位址隨執行環境而異，其餘輸出固定。）

---

練習 6：my_realloc — 就地擴展優先（難度：挑戰）

題目

實作 my_realloc(p, n)，依序嘗試三條路：

• (a) 縮小：原地完成，多出的尾巴切回 free list；
• (b) 擴大且緊鄰的下一塊（高位址側）是夠大的空塊： 合併鄰塊、原地完成（免拷貝）；
• (c) 其他：malloc 新塊 + memcpy + free 舊塊。

並處理 realloc(NULL, n) = malloc、realloc(p, 0) = free。 展示「原地擴展位址不變」與「搬家內容不失」。

解題思路

1. realloc 的價值排序：不拷貝 > 拷貝。三條路按成本 排序：縮小（免費）→ 吃鄰塊（免費）→ 搬家（O(n) 拷貝）。 真實的 realloc 也是這個決策樹。
2. 「下一塊」怎麼找——size 以 Header 為單位的甜頭：

[ Hdr | data ......... ][ ??? ]
  bp                     bp + bp->s.size

bp + bp->s.size 一個加法就是緊鄰塊的 Header 位址。 剩下的問題是「它是不是空塊」——free list 是唯一的 空塊名冊，走訪比對位址即可（detach_free_block_at）。 3. 吃鄰塊的三步：從串列摘除鄰塊 → bp->s.size += nb->s.size （兩塊變一塊）→ 若合併後太大，trim_tail 把多的切回去。 摘除時 freep 不能留在被摘的塊上（下次 malloc 會從 幽靈塊出發）。 4. trim_tail 的門檻：尾巴至少 2 單位才切（Header + 1 單位 資料），否則留著當 slack——切出永遠配不出去的 1 單位塊 只是污染串列。 5. 搬家的細節：拷貝量是 min(舊資料區, 新請求)—— 舊塊資料區 (size-1) * sizeof(Header) 位元組； malloc 失敗時舊塊必須原封不動（標準 realloc 的約定， 呼叫者還要用它）。 6. 實驗佈局：先配 a、b、c（從尾端切割，a 在最高位址）； free(a) 讓 b 的正後方出現洞 → realloc(b, 200) 走 (b) 路 （位址不變）；realloc(c, 400) 的正後方是 b（使用中） → 走 (c) 路搬家（位址改變、字串完好）。

參考解答

/*
 * 練習 6：my_realloc — 就地擴展優先，搬家為後備
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex6_my_realloc.c
 * 執行：/tmp/out
 *
 * 重點：realloc 的三條路——
 *   (a) 縮小：切掉尾巴還給 free list（原地）
 *   (b) 擴大且「正後方」是夠大的空塊：合併鄰塊（原地，免拷貝）
 *   (c) 其他：malloc 新塊 + memcpy + free 舊塊（搬家）
 * 「size 以 Header 為單位」讓 (b) 的鄰塊判斷只是一個指標加法。
 */
#include <stdio.h>
#include <string.h>
#include <stddef.h>

/* ---------------- K&R 配置器本體（同 01_kr_malloc.c） ---------------- */

typedef long Align;

union header {
    struct {
        union header *ptr;
        size_t        size;
    } s;
    Align x;
};
typedef union header Header;

#define ARENA_BYTES 65536
#define NALLOC      128

static _Alignas(Header) char arena[ARENA_BYTES];
static size_t arena_used = 0;
static Header  base;
static Header *freep = NULL;

static void my_free(void *ap);

static Header *morecore(size_t nu)
{
    if (nu < NALLOC)
        nu = NALLOC;
    size_t nbytes = nu * sizeof(Header);
    if (arena_used + nbytes > sizeof arena)
        return NULL;
    Header *up = (Header *)(void *)(arena + arena_used);
    arena_used += nbytes;
    up->s.size = nu;
    my_free((void *)(up + 1));
    return freep;
}

static void *my_malloc(size_t nbytes)
{
    Header *p, *prevp;
    size_t nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

    if ((prevp = freep) == NULL) {
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) {
            if (p->s.size == nunits) {
                prevp->s.ptr = p->s.ptr;
            } else {
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void *)(p + 1);
        }
        if (p == freep)
            if ((p = morecore(nunits)) == NULL)
                return NULL;
    }
}

static void my_free(void *ap)
{
    Header *bp = (Header *)ap - 1;
    Header *p;

    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break;

    if (bp + bp->s.size == p->s.ptr) {
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr   = p->s.ptr->s.ptr;
    } else {
        bp->s.ptr = p->s.ptr;
    }
    if (p + p->s.size == bp) {
        p->s.size += bp->s.size;
        p->s.ptr   = bp->s.ptr;
    } else {
        p->s.ptr = bp;
    }
    freep = p;
}

/* ---------------- 本題：my_realloc ---------------- */

/* 若塊尾巴多出 extra 單位，切下來還給 free list（縮小/合併後修边） */
static void trim_tail(Header *bp, size_t nunits)
{
    size_t extra = bp->s.size - nunits;
    if (extra < 2)              /* 尾巴太短，切了也沒人能用：留著 */
        return;
    bp->s.size = nunits;
    Header *tail = bp + nunits;
    tail->s.size = extra;
    my_free((void *)(tail + 1));
}

/*
 * 在 free list 上找「起點恰好是 target」的空塊。
 * 找到就從串列摘除並回傳；沒有回 NULL。
 */
static Header *detach_free_block_at(Header *target)
{
    if (freep == NULL)
        return NULL;
    Header *prev = &base;
    Header *p = base.s.ptr;
    while (p != &base) {
        if (p == target) {
            prev->s.ptr = p->s.ptr;
            freep = prev;       /* freep 不可留在被摘掉的塊上 */
            return p;
        }
        prev = p;
        p = p->s.ptr;
    }
    return NULL;
}

static void *my_realloc(void *ap, size_t nbytes)
{
    if (ap == NULL)                     /* realloc(NULL, n) == malloc(n) */
        return my_malloc(nbytes);
    if (nbytes == 0) {                  /* realloc(p, 0)：釋放並回 NULL */
        my_free(ap);
        return NULL;
    }

    Header *bp = (Header *)ap - 1;
    size_t nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

    /* --- (a) 縮小（或不變）：原地，切尾巴 --- */
    if (bp->s.size >= nunits) {
        trim_tail(bp, nunits);
        return ap;
    }

    /* --- (b) 就地擴展：正後方（高位址側）恰好是空塊？ --- */
    Header *next = bp + bp->s.size;     /* 指標運算：跳到緊鄰的下一塊 */
    Header *nb = detach_free_block_at(next);
    if (nb != NULL) {
        if (bp->s.size + nb->s.size >= nunits) {
            bp->s.size += nb->s.size;   /* 合併鄰塊 */
            trim_tail(bp, nunits);      /* 多的切回去 */
            return ap;                  /* 位址沒變！ */
        }
        /* 鄰塊不夠大：原封不動掛回去，走搬家路徑 */
        my_free((void *)(nb + 1));
    }

    /* --- (c) 搬家：新塊 + 拷貝 + 釋放舊塊 --- */
    void *np = my_malloc(nbytes);
    if (np == NULL)
        return NULL;                    /* 失敗時舊塊必須保持有效 */
    size_t old_bytes = (bp->s.size - 1) * sizeof(Header);
    memcpy(np, ap, old_bytes < nbytes ? old_bytes : nbytes);
    my_free(ap);
    return np;
}

/* ---------------- 展示 ---------------- */

static void show(const char *tag, const void *p)
{
    printf("  %-28s offset %5td\n", tag, (const char *)p - arena);
}

int main(void)
{
    /* 佈局（配置從尾端切，先配的在高位址）：
         [ ...free... ][ c ][ b ][ a ]
       free(a) 之後，b 的正後方就是空塊——就地擴展的舞台。 */
    char *a = my_malloc(100);
    char *b = my_malloc(100);
    char *c = my_malloc(100);
    strcpy(b, "block b: do not lose me");
    strcpy(c, "block c: me neither");
    show("a =", a);
    show("b =", b);
    show("c =", c);

    printf("\n=== free(a): a hole opens right behind b ===\n");
    my_free(a);

    printf("\n=== grow b 100 -> 200: in-place (merge with the hole) ===\n");
    char *b2 = my_realloc(b, 200);
    show("realloc(b,200) =", b2);
    printf("  same address as b?  %s\n", b2 == b ? "YES (in-place)" : "no");
    printf("  content intact?     \"%s\"\n", b2);

    printf("\n=== grow c 100 -> 400: must move (b2 sits behind it) ===\n");
    char *c2 = my_realloc(c, 400);
    show("realloc(c,400) =", c2);
    printf("  same address as c?  %s\n", c2 == c ? "yes" : "NO (moved)");
    printf("  content intact?     \"%s\"\n", c2);

    printf("\n=== shrink b2 200 -> 40: in-place, tail returned ===\n");
    char *b3 = my_realloc(b2, 40);
    show("realloc(b2,40) =", b3);
    printf("  same address?       %s\n", b3 == b2 ? "YES (in-place)" : "no");

    printf("\n=== realloc(NULL, n) and realloc(p, 0) ===\n");
    char *d = my_realloc(NULL, 50);         /* = malloc */
    printf("  realloc(NULL,50) -> %s\n", d != NULL ? "ok (malloc)" : "NULL");
    d = my_realloc(d, 0);                   /* = free */
    printf("  realloc(d,0)     -> %s\n", d == NULL ? "NULL (freed)" : "?!");

    my_free(b3);
    my_free(c2);
    printf("\ndone: in-place growth avoided a copy; the move path\n"
           "preserved the contents byte for byte.\n");
    return 0;
}

程式碼講解

• detach_free_block_at(target)：線性走訪比對 p == target ——K&R 的串列沒有反向索引，O(n) 是這個設計下的必然； 實務配置器用邊界標記（boundary tag）把這步變 O(1)。
• (b) 分支「鄰塊不夠大」的回滾：my_free(nb + 1) 原樣掛回 ——摘了不用就要還，否則那塊記憶體就漏了。
• 縮小分支直接 trim_tail 後回傳原指標——縮小永遠可以 原地，這也是為什麼「先縮小判斷」放最前面。
• 輸出對帳：realloc(b,200) 位址不變（offset 1808）， 字串完好；realloc(c,400) 位址改變（1680 → 1264）， 字串也完好——兩條路的行為差異與正確性同時驗證。
• realloc(p, 0) 的語意在 C23 已改為未定義；本實作採 傳統行為（free + NULL）並在介面註解言明——寫庫的人 要對語意變動敏感。
• 易錯處一：搬家時先 free 舊塊再 malloc——free 可能把 舊塊資料的前 16 位元組改成串列指標（Header 復用）， 拷貝已毀。順序必須 malloc → memcpy → free。
• 易錯處二：只會找「低位址側」的前鄰——前鄰合併後 使用者資料必須搬移（起點變了），並不是免費的； 本題只吃高位址側的後鄰，才是真正的零拷貝。

範例輸出

  a =                          offset  1936
  b =                          offset  1808
  c =                          offset  1680

=== free(a): a hole opens right behind b ===

=== grow b 100 -> 200: in-place (merge with the hole) ===
  realloc(b,200) =             offset  1808
  same address as b?  YES (in-place)
  content intact?     "block b: do not lose me"

=== grow c 100 -> 400: must move (b2 sits behind it) ===
  realloc(c,400) =             offset  1264
  same address as c?  NO (moved)
  content intact?     "block c: me neither"

=== shrink b2 200 -> 40: in-place, tail returned ===
  realloc(b2,40) =             offset  1808
  same address?       YES (in-place)

=== realloc(NULL, n) and realloc(p, 0) ===
  realloc(NULL,50) -> ok (malloc)
  realloc(d,0)     -> NULL (freed)

done: in-place growth avoided a copy; the move path
preserved the contents byte for byte.

---

常見錯誤解法對照

錯誤寫法	症狀	正解
calloc 不查 n*size 溢位	配小塊當大塊用，堆溢位	n > SIZE_MAX / size（練習 1）
morecore 借 my_free 不補計數	統計漂移	先墊高再借（練習 2）
實驗不重置配置器	兩種策略比較無效	reset + 統一 freep（練習 3）
bfree 單位數用進位除法	尾端越界踩人	供給向下取整（練習 4）
改了 Header 卻漏掉 morecore 的印章	自己的塊被自己攔	所有路徑維護不變量（練習 5）
realloc 先 free 再 malloc	資料被串列指標蓋掉	malloc → memcpy → free（練習 6）
realloc 失敗毀掉舊塊	呼叫者拿著懸空指標	失敗時舊塊保持有效（練習 6）