malloc 不是魔法。K&R 全書的壓軸範例（§8.7）用不到一百行實作了一個真正能用的
記憶體配置器，把 union 對齊、指標運算、環狀串列、系統呼叫全部串在一起。
讀懂它，你對「指標到底是什麼」的理解會上一個台階。
本單元完整解析 K&R 配置器，並提供一個可攜版實作：以
static char arena[65536] 靜態陣列取代 sbrk（sbrk 在 macOS 已棄用且會觸發警告），
邏輯與 K&R 原版一致，並示範配置、釋放與相鄰空塊合併的完整過程。
學習目標
- 理解 free list（空閒串列）的設計：環狀單向串列、依位址排序
- 理解 Header 的 union 技巧與對齊（alignment）需求
- 能解釋 first-fit 配置、區塊切割（split）與釋放時的合併（coalesce）
- 理解
morecore/sbrk的角色，以及本教材用靜態 arena 取代的原因 - 實作
my_malloc/my_free並能追蹤 free list 的變化 - 認識碎片化（fragmentation）問題與實務配置器的改良方向
對照章節 / 參考來源
- K&R §8.7 Example — A Storage Allocator（
malloc/free/morecore） - K&R §6.8 Unions（Header 的 union 技巧來源）
- 《The C Programming Language》習題 8-6 ~ 8-8
- Doug Lea, "A Memory Allocator"（dlmalloc 設計文，實務配置器的起點）
觀念講解
1. 問題設定
malloc(n) 要回傳一塊至少 n 位元組、對齊正確、彼此不重疊的記憶體；
free(p) 要把它收回並且讓相鄰的空塊合併，否則記憶體會碎成一堆小塊
（碎片化），明明總量夠卻配不出大塊。
2. Header 與 union 對齊技巧
每個區塊前面藏一個 Header，記錄「大小」與「下一個空塊」：
typedef long Align; /* 對齊到最嚴格型別的邊界 */
union header {
struct {
union header *ptr; /* 下一個空閒塊（free list 上） */
size_t size; /* 本塊大小（以 Header 為單位！） */
} s;
Align x; /* 從不使用：只為了逼出對齊 */
};
typedef union header Header;兩個巧思：
- union 逼對齊：
Align x讓整個 Header 的大小與對齊至少符合long， 於是「Header 後面緊接著的使用者記憶體」也自動對齊。 - 以 Header 為度量單位：
size不以位元組計，而以「幾個 Header 大」計， 指標運算hp + hp->s.size直接跳到下一塊，乾淨俐落。
3. 記憶體佈局
使用者拿到的指標 p = header 位址 + 1（跳過 Header）
┌────────┬──────────────────────────┐
│ Header │ 使用者資料區 │
│ ptr/sz │ (size-1) 個 Header 大 │
└────────┴──────────────────────────┘
^ ^
(Header*)p-1 p
free list（空塊的環狀串列，依「位址」排序）：
base ──> [ blk A ] ──> [ blk C ] ──> [ blk F ] ──┐
^ │
└──────────────────────────────────────────────┘
（已配置的 B、D、E 不在串列上）依位址排序是為了合併：釋放 B 時，掃 free list 找到「位址剛好在 B 前後」的 A 與 C，若緊貼就直接把 size 相加、串列縮短——碎片消失。
4. my_malloc：first-fit + 切割
walk free list:
塊太小 -> 下一塊
剛剛好 -> 從串列摘除，回傳
太大 -> 從「尾端」切下需要的量（前段留在串列上，
size 減小；尾段裝上新 Header 回傳）
繞回起點 -> 空間不足：K&R 呼叫 morecore 向 OS 要，
本可攜版改從靜態 arena 撥出（或回傳 NULL）從尾端切割的好處：留在串列上的前段不需要改動串列指標，只改 size。
5. my_free：插入 + 雙向合併
釋放時沿環狀串列找到正確的位址插入點（維持位址排序），然後檢查兩側：
case 1: 與後鄰接壤 -> size 併入後鄰、指標跳過它
case 2: 與前鄰接壤 -> 前鄰的 size 直接加上本塊
case 3: 兩側都接壤 -> 兩步都做，三塊變一塊
case 4: 都不接壤 -> 單純插入串列範例程式會在每一步印出 free list，四種情況都能親眼看到。
6. morecore 與可攜性說明
K&R 原版在空間不足時呼叫 morecore，內部用 sbrk(NALLOC * sizeof(Header))
向作業系統擴展 data segment。現況：
sbrk在 macOS 標記為 deprecated（編譯即警告），且 64 位系統上僅為模擬。- 現代
malloc實作改用mmap取得大塊匿名記憶體。
本教材的可攜版把「向 OS 要記憶體」簡化為「從 static char arena[65536]
撥出」——morecore 的邏輯保留（一次撥一大塊、掛回 free list），
但來源變成編譯期就存在的靜態陣列，任何平台零警告可編譯，
也更容易在除錯器裡觀察整個 heap。
7. 實務配置器往哪裡進化
| 課題 | K&R 版 | 實務（dlmalloc/jemalloc/tcmalloc） |
|---|---|---|
| 搜尋 | first-fit O(n) | 分大小桶（bins/size classes）O(1) |
| 合併 | 立即合併 | 邊界標記（boundary tags）雙向 O(1) |
| 多執行緒 | 無保護 | per-thread cache、arena 分離 |
| 大塊 | 同一機制 | 直接 mmap，free 即還 OS |
範例程式
| 檔案 | 內容 | 編譯 / 執行 |
|---|---|---|
01_kr_malloc.c |
K&R §8.7 可攜版全實作：my_malloc/my_free/靜態 arena morecore、free list 傾印、四種合併情況逐步展示 | cc -std=c11 -Wall -Wextra -o out 01_kr_malloc.c && ./out |
02_pool_allocator.c |
對照組：固定大小 pool allocator（O(1) 配置/釋放、零碎片），說明何時該用它 | cc -std=c11 -Wall -Wextra -o out 02_pool_allocator.c && ./out |
常見錯誤與陷阱
- 忘記「size 以 Header 為單位」：位元組數與單位數混用，
切割時指標一跳就跳出區塊。K&R 的換算公式
nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1要逐項理解。 - free 不合併：只把塊插回串列，跑久了全是小碎塊， 大請求永遠失敗——合併是配置器的靈魂。
- double free / free 野指標：K&R 版完全信任呼叫者， free 一個不是 my_malloc 回傳的指標會把串列攪爛（實務配置器也常只能 crash）。
- 對齊被破壞：自作聰明把 Header 改成
struct { void *p; int n; }而沒有 union Align，在要求 16-byte 對齊的平台上使用者資料就 misaligned。 - 寫入越界踩壞下一塊的 Header：
p[n]越界一個位元組就可能改掉鄰塊 size， 崩潰點遠在事發之後——這正是 heap corruption 難查的原因。
練習題
- 【易】為
01_kr_malloc.c加上my_calloc(n, size)：配置後清零 （注意乘法溢位檢查）。 - 【易】加上統計功能：目前已配置塊數、free list 塊數、最大可配置區塊。
- 【中】把 first-fit 改成 best-fit（找「最小的够用塊」）， 用同一組配置序列比較兩者的碎片化程度。
- 【中】實作 K&R 習題 8-8
bfree(p, n)：把任意一塊使用者提供的記憶體 掛進 free list（想想對齊怎麼處理）。 - 【難】為每塊加「魔數」欄位，在 free 時驗證，偵測 double-free 與 踩壞 Header 的越界寫入。
- 【難】實作
my_realloc：就地擴展（後鄰是空塊且夠大時合併）優先， 否則配新塊 + memcpy + 釋放舊塊。
補充：讀懂 K&R 原始碼的三個關鍵句
K&R §8.7 的程式碼精煉到每一行都值得停下來想。三個最容易卡住的地方：
nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;(a + b - 1) / b 是 ⌈a/b⌉；最後的 +1 是 Header 自己的位置。
p += p->s.size; /* 切割時 */p 是 Header*，
+ size 就前進 size 個 Header，恰好跳到被切下的尾段起點。
這行是「size 以 Header 為單位」設計的回報。
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;p >= p->s.ptr 表示走到了環的「繞回點」（位址最大塊接回位址最小塊），
此時 bp 若在兩端之外（比最大還大、或比最小還小）也算找到位置。
延伸閱讀
- K&R §8.7（原始碼必讀）與習題 8-6 ~ 8-8
- Doug Lea, "A Memory Allocator"（dlmalloc 論文式說明）
- jemalloc / tcmalloc 設計文件（size class 與 thread cache）
- 《The Linux Programming Interface》第 7 章（heap 與 brk/sbrk 的真相）
- Valgrind massif / macOS Instruments：實際觀測 heap 行為的工具