前兩篇指南留下的痛處
第 1 篇給了你一個通用配置器：一條穿過孔洞的閒置串列、用首次適配或最佳適配挑選區塊，以及搭配邊界標記的切割與合併來保持記憶體緊密。它能應付任何順序的任何大小——但這份通用性是要付代價的。每次 free() 都可能掃過一條長串列，而每次合併都得去追相鄰區塊、改寫標頭與頁尾。第 2 篇接著展示了另一個極端：arena或記憶體池為了純粹的速度而放棄通用性，用寥寥幾道指令交還固定大小的槽位，卻無法一次只釋放一個物件，或根本無法服務混合大小。
本篇談的是兩種巧妙地坐落在這兩極之間的設計。夥伴系統（buddy system）保留了通用配置器服務一系列大小的能力，卻藉由只允許 2 的次方大小，讓切割與合併幾乎不花成本。slab 配置器保留了記憶體池對單一物件型別那種飛快的速度，卻加上了釋放個別物件、以及重用它們已初始化好的形狀的能力。它們可不是當玩具發明的：夥伴系統管理著 Linux 核心的實體分頁框，而 slab 配置器（及其後代）就坐在它正上方，服務核心數以百萬計的小物件。讀到最後，你應該會看出每一種為什麼長成它那個樣子。
夥伴系統：2 的次方，與那個 XOR 妙招
回想第 1 篇裡合併的痛苦：要融合兩塊閒置區塊，你得找到相鄰區塊、確認它是閒置的、再確認這兩塊物理上相鄰且屬於同一個邏輯單元。夥伴系統藉由強加一條規則，讓這三項檢查都變得微不足道：每塊區塊的大小都是 2 的次方，而一塊大小為 2^k 的區塊，只能由一塊大小為 2^(k+1) 的區塊精確地對半切割而來。一次切割所生出的兩個半塊，稱為彼此的夥伴（buddy）。一塊區塊永遠只能與它自己的夥伴合併——絕不能與某個任意的相鄰區塊——這正是讓合併變得便宜又可預測的關鍵。
這裡有個讓它運轉如歌的妙招。若一塊大小為 2^k 的區塊起始於位址 a（從記憶體池起點算起），它夥伴的位址就單純是 a XOR 2^k——把第 k 位的那一個位元翻轉。這一道位元運算，不必走任何串列、不必讀任何頁尾，就告訴你夥伴確切住在哪裡。要釋放一塊區塊：算出夥伴位址，檢查夥伴是否也閒置且大小相同，若是就翻轉那個位元、躍升到大小為 2^(k+1) 的合併後父塊，再往上一層重複檢查。配置則把同一套機制反著跑：為每個大小級距各保一條閒置串列（一條 16 KiB 區塊的串列、一條 32 KiB 的，依此類推）；若恰當大小的串列空了，就從上一級拿一塊來切割，把一個夥伴放上較小的串列、用掉另一個。
Pool of 64 KiB. Ask for a 6 KiB block -> round up to 8 KiB (2^13). [-------------------- 64 --------------------] need 8 [------- 32 -------][------- 32 -------] split 64 [-- 16 --][-- 16 --] split left 32 [ 8 ][ 8 ] split left 16 <- return this 8 The returned 8 KiB block sits at offset 0x0000. Its buddy is at 0x0000 XOR 0x2000 = 0x2000 (the other 8). Free both 8s -> merge to the 16 -> its buddy is the right 16 -> merge to 32 -> buddy is the right 32 -> merge back to the full 64.
Slab 配置器：讓物件保持預先成形
現在翻到另一個問題。核心會不斷地配置與釋放同一種小物件——這裡一個任務結構、那裡一個 inode，每秒數千個，全都大小相同。通用配置器把每一個都當成匿名的一團：把大小向上取整、搜尋一條串列、寫一個標頭，釋放時再合併。當每個物件形狀都相同時，這很浪費。slab 配置器由 Jeff Bonwick 於 1994 年為 SunOS 發明，建立在第 2 篇的記憶體池點子之上，多了一個組織性的洞見：為單一物件型別專設一個快取（cache），把連續分頁的大型 slab 切成一格剛好物件大小的網格，再從那個網格供應。
因為一個快取裡每個槽位都同樣大小，所以不必搜尋、不必取整：一條由相同槽位組成的閒置串列，意味著相當於 malloc 的操作就是「彈出串列頭」、相當於 free 的就是「壓入串列頭」，兩者都是 O(1)。一個 slab 不過是一連串分頁，加上它空槽位的一條小閒置串列；配置器把 slab 分類整理成三種狀態——全滿（每個槽位都用了）、部分使用（有些空著）、與全空（全部空著）——並且總是從一個部分使用的 slab 供應，好讓記憶體保持密實。當一整個 slab 變空，在記憶體壓力下它可以交還給分頁配置器。注意這分層的設計：下層的夥伴系統交出分頁大小的區塊，上層的 slab 配置器把那些切成細顆粒的物件。Linux 正是這樣建構的，kmalloc()坐在 slab 快取上、slab 快取又坐在夥伴配置器上。
追蹤物件：帳本放哪裡？
slab 配置器面臨第 1 篇提出的同一個中介資料問題——給定一個要釋放的指標，你怎麼找到它的 slab 與它的閒置串列？——但它的回答方式不同，而這差異對快取行為很重要。原始設計把每個 slab 的控制結構與它那組空槽索引存在 slab 自己裡面，通常擺在分頁串尾端。這讓一個 slab 自成一體，但對小物件而言，slab 內的中介資料會偷走槽位，更糟的是，每次配置去碰那些管理資料，都會把一條額外的快取線拖進 CPU。
還有一條更俐落、完全避開每物件標頭的路。因為一個 slab 裡每個物件大小相同、且 slab 起始於分頁邊界，你可以單憑算術從一個物件的位址還原它的 slab——把指標遮罩到分頁（在 4 KiB 分頁上大約是 p & ~0xFFF），再到一張全域表裡查那個分頁屬於哪個快取。物件本身完全不帶標頭；slab 的中介資料另置一旁。這是現代的做法，也是為什麼一個 slab 物件往往是零每物件開銷，不像第 1 篇那些帶標頭的區塊。誠實地說：每物件的帳本工作並沒有消失，它搬進了一個緊湊的每-slab 結構與一次分頁查表，而這之所以更便宜，正是因為它被數以千計的相同物件分攤了。
把夥伴與 slab 拼在一起，以及接下來是什麼
退一步看整台機器，因為這兩個點子是夥伴、不是對手。夥伴系統是個粗顆粒、通用的配置器：它以便宜的切割與合併、幾近於零的外部碎裂化，供應大塊的 2 的次方區塊（分頁與分頁串），並容忍內部浪費，因為分頁大小的請求很少需要大幅取整。slab 配置器是個細顆粒、專門化的配置器：它拿那些大塊，把每一塊切成單一物件型別的精確槽位，配置／釋放皆 O(1)、且零每物件標頭。底下粗而通用、上面細而專門——這分兩層的切分，是整個系統記憶體管理裡最常被重用的模式之一。
- 某個核心子系統需要一個新的 inode 物件，於是呼叫它的配置器。inode 的 slab 快取被請求給出一個槽位。
- 若某個部分使用的 slab 有空槽，就彈出它閒置串列的串列頭——一兩道指令，完成。該物件可能已處於已建構狀態，所以不必重新初始化。
- 若每個 slab 都滿了，快取就向夥伴系統要一串新的分頁，把它切成一格 inode 大小的網格，那就成為一個由空轉為部分使用的新 slab。
- 釋放時，把指標遮罩到它的分頁、找到所屬的 slab 與快取、把槽位壓回閒置串列。當一整個 slab 清空且記憶體吃緊時，它的分頁回到夥伴配置器，後者可能把它們與其夥伴合併回去。
仍在拉扯這個設計的兩條線，正好指向接下來的指南。其一，圍繞單一固定物件大小打造的配置器，對核心很美妙，但對必須服務任意大小的 malloc() 卻沒用——解法是在精心選定的若干大小上，保留許多類 slab 的記憶體池，也就是第 4 篇的大小級距。其二，單一共享的 slab 快取，在許多 CPU 同時配置時會變成鎖爭用的瓶頸，這就是為什麼真實的核心與使用者配置器，會在前端裝上一個每-CPU 或每執行緒快取——也就是第 5 篇展示其驅動 jemalloc、tcmalloc 與 mimalloc 的那個結構。你現在已看過兩個最乾淨的專門化配置器；本級其餘部分，談的就是讓一個通用配置器借用它們的妙招。