你向 malloc 真正請求的是什麼
在前面幾級你學過：堆積是你自己去成長的那塊記憶體，而 malloc() 與 free() 是你從中切下小塊、再交還回去的方法。那是使用者那一側的視角。現在你坐到呼叫的另一邊。配置器的全部工作就是這個：一支程式會以它喜歡的任何順序，請求任何大小的區塊——這裡 8 位元組、那裡 4000 位元組、24 位元組、1 MiB——之後又會把每一塊交還回來，順序同樣隨意。配置器從核心那裡擁有一大片位址空間，必須全部從中滿足每一個請求，並為每一次 malloc() 精確決定要回傳哪些位元組。
這樣赤裸地說來似乎很簡單，但有四個要求互相拉扯，而配置器設計的藝術正是去平衡它們。它必須快：malloc() 與 free() 坐在幾乎每支程式的熱路徑上，所以一個要花一微秒才算得出的答案就已經是場災難。它必須省空間：若它交出去的位元組浪費掉一半，你的程式就需要兩倍的記憶體。它必須避免碎裂化：即使總計還有大量閒置位元組，它仍可能找不到足夠的連續位元組來滿足一個請求。而且它在並行下必須正確，因為真實的程式會同時從許多執行緒配置。本級的每一項技術，都是這場四方拔河中的一步棋。
帳本：每個區塊上的標頭
這裡有第一道謎題。當你呼叫 free(p) 時，你只交還一個指標——你並沒有說那塊區塊有多大。然而配置器必須知道它的大小才能再利用。所以大小一定要被寫在某個它光憑 p 就能找到的地方。經典手法是配置中介資料：在它回傳給你的那些位元組之前，配置器藏著一個小小的標頭（header）。若一塊有 32 個可用位元組的區塊位於位址 p，標頭就坐在前面幾個位元組處，也就是 p 減去標頭大小之處，並記錄該區塊的總長度以及它是閒置還是使用中。
這就是為什麼 malloc(32) 常常吃掉明顯多於 32 位元組的堆積：你要為承載資料、加上標頭、再加上為對齊而向上取整的部分付費。這也是為什麼堆積程式設計的頭號大罪——寫到區塊尾端後面的一個位元組——如此危險：你承載資料後面緊接的那個位元組，往往就是下一個區塊的標頭，而毀掉一個大小欄位，會把配置器自己的資料結構變成垃圾。那次崩潰——如果你夠幸運能撞到一次的話——通常會浮現在稍後某次無辜的、離真正臭蟲很遠的 free() 上。
... | header | payload (returned to you) | header | payload | ...
^ ^
p - 8 p <- malloc() returns p; free(p) reads p-8
header (one common layout):
size of this block, in bytes (low bits unused -> reused as flags)
in-use / free bit
[optional] link to next free block閒置串列：一條穿過孔洞的鏈
現在來到整個這一級的核心觀念。當你 free() 一塊區塊時，配置器並不把它的位元組還給核心——那會很慢，而且你很可能不久後又會請求一塊那樣大小的區塊。它反而把該區塊標記為閒置，並把它串接到一條閒置串列上：一條鏈結串列，串起目前每一塊可供再利用的區塊。聰明之處在於：一塊閒置區塊的承載資料，依定義並未被你的程式使用，所以配置器就把串列的「下一個」指標存在那塊閒置區塊自己裡面。閒置串列不花任何額外記憶體；它就住在那些孔洞裡。
有了這條串列在手，malloc(n) 就變成一場搜尋：走過閒置串列，尋找一塊大到足以容納 n 位元組的區塊。你挑哪一塊，就是放置策略，而兩個經典選擇就把整個張力都教給你了。首次適配（first fit）取第一塊夠大的區塊——很快，因為你提早停下，但它傾向啃掉串列前端那些大區塊。最佳適配（best fit）掃過整條串列，找出大小最接近 n 的那一塊——它每次配置浪費掉最少的剩餘位元組，但比較慢，而且違反直覺地，它可能在堆積上留下一堆細小、無法使用的碎片。沒有放諸四海皆準的最佳策略；每一種都在搜尋時間與浪費空間之間做取捨，這就是那場四方拔河以微縮形式現身。
切割與合併：對抗碎裂化
假設 malloc(16) 找到一塊 64 位元組的閒置區塊。為了滿足一個 16 位元組的請求而把整整 64 位元組都交出去，會浪費 48 位元組——這種區塊內部的浪費就是內部碎裂化。解法是切割（splitting）：把這 64 位元組的區塊切成一塊 16 位元組（你回傳出去）與一塊 48 位元組的餘料（以較小的閒置區塊身分回到閒置串列上）。現在你既緊湊地服務了請求，又把剩料保留下來可供使用。切割是配置器保持記憶體緊密的一半辦法；本級各處你都會在切割與合併裡再看見它。
相反的危險則隨時間浮現。這裡釋放一塊、那裡釋放一塊，堆積就填滿了散落在存活區塊之間的小閒置區塊——總計有很多閒置位元組，卻沒有任何單一孔洞大到足以應付一個大請求。這就是外部碎裂化（external fragmentation），是更微妙、更陰險的失敗模式：malloc() 可能在數百萬位元組閒置時回傳 NULL，純粹因為它們不連續。解藥是合併（coalescing）：當你釋放一塊區塊時，檢查物理上與它相鄰的區塊是否也閒置，若是，就把這兩塊閒置區塊融合成一塊更大的閒置區塊。每次 free() 都這麼做，小孔洞就會不斷癒合回大孔洞。
不過合併藏著一道真正的謎題。從一個指向區塊的指標，你能輕易找到下一個區塊——它的位址就是你的位址加上你的大小。但你要怎麼找到前一個區塊，好檢查它是否閒置？你手上只有一個指進堆積中段的指標；沒有回指鏈結。經典解答是邊界標記（boundary tag）（Knuth 的手法）：把區塊的大小不只寫在它的標頭，也寫在它最尾端的一個頁尾（footer）。如此一來，前一個區塊的頁尾就坐落在你標頭前面緊接的那些位元組裡，於是讀取你標頭前面那一個字，就告訴你前一個區塊的大小與閒置位元——你便能退一步走到它那裡。有了標頭與頁尾，合併相鄰的閒置區塊就成了兩側皆為常數時間的檢查。
把一次配置從頭走到尾
讓我們把這一切變得具體，追蹤一次採用首次適配閒置串列與邊界標記的 malloc(24)。看看標頭讀取、串列搜尋、切割與對齊如何全都在一次普通的呼叫裡現身——這就是接下來四篇指南不斷精煉的那個迴圈。
- 把請求向上取整。24 位元組加上標頭／頁尾的開銷，再向上取整到對齊大小（譬如 16），成為一個實際的區塊大小——這樣你絕不會交出一塊未對齊或太小的區塊。
- 從串列頭走過閒置串列，讀取每塊區塊的標頭大小，並在第一塊大到足以容納那個取整後大小的閒置區塊處停下。
- 決定是否切割。若找到的區塊遠大於所需，就把剩料切成一塊新的閒置區塊，寫好它的標頭與頁尾，再把它串回閒置串列上。
- 把選中的區塊標記為使用中：在標頭與頁尾都設定它的使用中位元（size | 0x1），並把它從閒置串列上解開。
- 回傳標頭之後緊接的那個指標。程式寫入它的 24 位元組；稍後，free(p) 讀取 p 減去標頭大小，以還原一切，並開始合併。
本級後面的每一個觀念，都是對你在那個迴圈裡早已感受得到的某個弱點的回應。步驟 2 的串列走訪是 O(n)——所以第 4 篇引入大小級距與分離串列，好直接跳到一條恰當大小區塊的串列。切割／合併的反覆攪動在對抗碎裂化——所以第 3 篇帶來夥伴系統（buddy system），它把大小限制在 2 的次方，使切割與合併變得便宜到不值一提。單一共享串列在多執行緒下是個爭用點——所以第 5 篇展示 jemalloc、tcmalloc 與 mimalloc 如何給每個執行緒自己的快取。你現在握住了骨架；本級的其餘部分就是肌肉。