為什麼核心不能直接呼叫 malloc()
回到「學 C」那一級，malloc() 是一個函式庫呼叫，它向核心要堆積記憶體，然後交給你一個乾淨的指標。但核心自己底下沒有任何函式庫——它就是最底層。當核心程式碼需要一個緩衝區來放網路封包、一個新的行程控制區塊、或一份檔案的中介資料時，沒有 malloc() 可呼叫，因為 malloc() 的運作方式，正是發出系統呼叫進入核心。核心必須自己長出它的記憶體，從原始的實體分頁往上長，而且它得在那些它連等待都不被允許的脈絡裡這麼做。這一節和下一節講的就是這套機械。
實體記憶體以固定大小的分頁來到核心面前——通常每個 4 KiB。因此核心記憶體管理最底層是一個分頁配置器：給我一個分頁、或四個連續的分頁，我把實體位址交還給你。最主流的設計是夥伴配置器（buddy allocator）。它把分頁依階（order）分組放進串列：階 0 是一個分頁、階 1 是兩個連續分頁、階 2 是四個，依此以二的次方類推。要滿足一個請求，它找出剛好放得下的最小階；若只有更大的區塊空著，它就把那個區塊對半切開——切出的兩半互稱為夥伴。當一個區塊被釋放時，配置器檢查它的夥伴是否也空著，若是，就把兩者合併回一個更大的區塊。二的次方讓「找出一個區塊的夥伴」變成單一一次位址計算，這就是為什麼這套方案在劇烈進出之下依然很快。
夥伴配置器只處理整個分頁，但大多數核心物件都很小：一個結構可能只有 96 位元組。為一個 96 位元組的物件切出一整個全新的 4 KiB 分頁，會浪費它超過 97%，所以在夥伴配置器之上坐著slab 配置器。一個 slab 是從夥伴配置器領上來的一個（或幾個）分頁，被預先切成許多相同大小的物件槽位，並有一條空閒串列穿過它們。配置一個物件於是就是從那條串列上彈出一個槽位——寥寥幾道指令、沒有分頁表的工作，而且這個物件往往還帶著一個最近被釋放的同伴留下的溫熱 CPU 快取行回來。slab 也快取部分建構好的物件，於是重用一個就能跳過重新初始化。這個兩層切分——分頁用夥伴、物件用 slab——是核心配置的骨幹。
kmalloc、vmalloc，以及禁止睡眠的那些脈絡
核心程式碼不會直接戳 slab；它呼叫 kmalloc()，這個函式把你的請求向上湊到一組固定大小級別的其中之一，然後從對應的 slab 快取裡拉出一個物件。kmalloc() 回傳的記憶體是實體連續的，這很要緊，因為有些硬體——一個把資料交給網路卡的 DMA 引擎——直接讀實體位址，沒辦法跟著一個散落的對映走。代價是：當實體記憶體碎裂時，一個大的連續請求可能直接失敗，哪怕總空閒記憶體還很多。對於那些不需要實體連續的大型配置，vmalloc() 則把實體上散落的分頁縫在一起，對映到核心位址空間裡一段連續的虛擬範圍——方便，但它燒掉分頁表項、對TLB造成壓力，所以 kmalloc() 仍是預設，vmalloc() 留給真正大的東西。
這裡有一個微妙之處，是第四篇那個排程器強加給我們的。kmalloc() 接受一個旗標引數，最常見的兩個值是 GFP_KERNEL 和 GFP_ATOMIC。GFP_KERNEL 說「我在一個可以睡眠也沒關係的脈絡裡」——若沒有空閒記憶體，配置器可以阻塞這個執行緒、讓排程器去跑別的東西、甚至在回傳前把髒分頁寫到磁碟以回收記憶體。GFP_ATOMIC 說「我絕不可以睡眠——立刻從一塊緊急保留區給我記憶體，或者失敗。」選錯是一個真正的臭蟲，而要選對，你得知道哪些脈絡被允許睡眠。
自旋鎖：一把拒絕睡眠的鎖
那條不准睡眠的規則，正是為什麼核心需要一把使用者空間那一級從不需要的鎖。一把互斥鎖在拿不到時會睡眠——而我們剛剛看到，睡眠在中斷脈絡裡是被禁止的。那麼一個中斷處理常式要怎麼保護一份它和核心其餘部分共享的串列？用自旋鎖（spinlock）。一把已經被持有的自旋鎖不會把等待者送去睡；等待者只是單純地自旋——迴圈、用一個原子的比較並交換反覆重讀那個鎖字組——燒著 CPU，直到鎖被釋放。它從不呼叫排程器，所以在任何脈絡裡都合法。
自旋之所以說得通，唯一的原因是這把鎖只被持有極短的時間——幾道指令拼接一個串列節點，沒有 I/O、沒有任何可能睡眠的配置。這定下了一條鐵律，逮住每一個核心新手：持有自旋鎖時，你絕不可以睡眠。 如果你抓了一把自旋鎖、然後用 GFP_KERNEL 呼叫 kmalloc()（它可能睡眠），排程器可能在鎖仍被持有的情況下把你的執行緒停泊起來。現在其他每一顆想要那把鎖的 CPU，都在一個正熟睡的持有者身上永遠自旋——一個直到某天記憶體恰好緊到讓那次配置真的阻塞，才會現身的死結。在自旋鎖裡，你用 GFP_ATOMIC 配置，或者更好，根本不配置。
還有一個轉折，連回第二篇的中斷機制。假設一個普通的核心執行緒持有一把自旋鎖，接著一個中斷在同一顆 CPU 上觸發，而它的處理常式試圖拿同一把鎖。處理常式自旋著、等那個執行緒釋放——但那個執行緒被凍住了，因為中斷搶佔了它，而處理常式在拿到鎖之前不會返回。這顆 CPU 卡死在自己身上。解法是 spin_lock_irqsave()：當一把鎖也可能從中斷處理常式裡被拿時，你在持有它的期間停用這顆 CPU 上的中斷，於是沒有任何處理常式能觸發來製造那個陷阱。核心逼你一把鎖一把鎖地寫清楚：中斷是否必須被遮蔽——這是一個 pthreads 世界根本從來不會有的鋒利邊緣。
每-CPU 資料與 RCU：徹底避開鎖
每一把鎖即使在無爭用時也有代價：抓住它的那個原子操作會逼一個快取行在多顆 CPU 之間彈跳，而兩個核心更新的計數器只要共用一個快取行，就會透過偽共享互相拖慢，哪怕它們從未碰過同一個變數。核心的第一個答案是把共享移除：每-CPU 資料。像「收到的封包數」這樣的統計量，不再是一個共享計數器，而是一個陣列、每顆 CPU 各有一個私有槽位。每顆 CPU 只增加自己的槽位——不上鎖、無爭用、沒有彈跳的快取行——而一個想要總數的讀者，只要把所有槽位加總起來。只要遞增時停用了搶佔、讓一個執行緒不會在更新到一半時遷移到另一顆 CPU，就根本不需要任何同步。
每-CPU 資料在每顆 CPU 各自擁有一份副本時管用，但核心裡滿是那種真正共享、卻讀得遠比寫得頻繁的結構——路由表、已載入模組的串列、掛載點。對這些，核心動用 RCU，讀-複製-更新，而它整個重點在於：讀者那一側完全不上鎖、也完全不做原子操作。一個讀者用 rcu_read_lock() 和 rcu_read_unlock() 把它的存取括起來，這兩者在經典的核心建置裡，展開成的不過是停用這顆 CPU 上的搶佔——一個便宜的每-CPU 旗標，不是鎖。在裡面，讀者全速跟著指標走，零爭用。
一個寫者要怎麼在無鎖讀者正走著的同時改動共享資料？它從不原地修改。寫者讀取節點、做一份私有複本、在複本上編輯，然後透過原子地把一個指標從舊節點甩向新節點來更新——於是每個讀者看到的要嘛是整個舊節點、要嘛是整個新節點，絕不是編輯到一半的混合物。不過舊節點不能立刻釋放：一個在甩動之前就開始的讀者可能還在走它。RCU 等一個寬限期（grace period）——每顆 CPU 都通過了一個可證明它不在任何讀者端區間裡的點（一次脈絡切換、閒置迴圈、返回使用者空間）的那一刻。一旦每顆 CPU 各排程過一次，之前所有讀者都已排空，只有到這時 free() 才安全。
WRITER READER (no lock, no atomic) ------------------------------------ ------------------------------- new = copy_of(old); rcu_read_lock(); // disables preempt edit(new); p = rcu_dereference(shared); rcu_assign_pointer(shared, new); use(*p); // old OR new node /* ^ one atomic pointer swing */ rcu_read_unlock(); synchronize_rcu(); /* wait grace */ kfree(old); /* now safe: no reader can still hold old */
藏在明處的屏障
那個讀者端有一個陷阱，鋒利到曾咬過真實的核心開發者。寫者在甩動那個被發布的指標之前填好新節點的欄位。讀者載入指標、然後解參考它去讀那些欄位。但在像 ARM 這樣寬鬆的 CPU 上，讀者可能在新節點的欄位寫入傳播開來之前就先看見新的指標值——於是它解參考進一個還是半團垃圾的節點。單獨一次樸素的指標儲存，本身並不保證寫者較早的那些欄位寫入會先變得可見；那個保證必須被明確地要求。
這正是為什麼這個 API 在寫者端是 rcu_assign_pointer()、在讀者端是 rcu_dereference()，而不是樸素的指派。它們嵌了一道記憶體屏障：assign 是一次釋放（release）儲存，強制所有欄位寫入在指標之前先出去；dereference 是對應的取得（acquire）載入，保證看見新指標的讀者也看見在它之前發布的一切。兩者一起建起那個讓發布安全的釋放-取得排序。省略它們，你的程式碼會在強排序的 x86 上通過每一項測試，然後在它跑上一支 ARM 手機或伺服器的第一天，悄悄毀壞記憶體。兩級之前還覺得抽象的那個硬體記憶體模型，現在正承重地撐在出貨給數十億台裝置的程式碼底下。