Linux內核之塊分配器

作者簡介：

余華兵，2005年畢業于華中科技大學計算機學院，取得碩士學位。畢業后的十余年一直在網絡通信行業從事軟件設計和開發工作，研究方向包括IPv4協議棧、IPv6協議棧和Linux內核。

目錄

3.8塊分配器

3.8.1編程接口3.8.2SLAB分配器3.8.3SLUB分配器3.8.4SLOB分配器

3.8 塊分配器

為了解決小塊內存的分配問題，Linux 內核提供了塊分配器，最早實現的塊分配器是SLAB 分配器。

SLAB 分配器的作用不僅僅是分配小塊內存，更重要的作用是針對經常分配和釋放的對象充當緩存。SLAB 分配器的核心思想是：為每種對象類型創建一個內存緩存，每個內存緩存由多個大塊（slab，原意是大塊的混凝土）組成，一個大塊是一個或多個連續的物理頁，每個大塊包含多個對象。SLAB 采用了面向對象的思想，基于對象類型管理內存，每種對象被劃分為一類，例如進程描述符（task_struct）是一個類，每個進程描述符實例是一個對象。

內存緩存的組成如圖3.21所示。

SLAB 分配器在某些情況下表現不太好，所以 Linux 內核提供了兩個改進的塊分配器。

（1）在配備了大量物理內存的大型計算機上，SLAB 分配器的管理數據結構的內存開銷比較大，所以設計了 SLUB 分配器。

（2）在小內存的嵌入式設備上，SLAB 分配器的代碼太多、太復雜，所以設計了一個3.8 塊分配器精簡的 SLOB 分配器。SLOB 是“Simple List Of Blocks”的縮寫，意思是簡單的塊鏈表。

目前 SLUB 分配器已成為默認的塊分配器。

3.8.1 編程接口

3 種塊分配器提供了統一的編程接口。

為了方便使用，塊分配器在初始化的時候創建了一些通用的內存緩存，對象的長度大多數是 字節，從普通區域分配頁的內存緩存的名稱是“kmalloc-”（size 是對象的長度），從 DMA 區域分配頁的內存緩存的名稱是“dma-kmalloc-”，執行命令“cat /proc/slabinfo”可以看到這些通用的內存緩存。

通用的內存緩存的編程接口如下。

（1）分配內存。

（2）重新分配內存。

（3）釋放內存。

使用通用的內存緩存的缺點是：塊分配器需要找到一個對象的長度剛好大于或等于請求的內存長度的通用內存緩存，如果請求的內存長度和內存緩存的對象長度相差很遠，浪費比較大，例如申請 36 字節，實際分配的內存長度是 64 字節，浪費了 28 字節。所以有時候使用者需要創建專用的內存緩存，編程接口如下。

（1）創建內存緩存。

（2）從指定的內存緩存分配對象。

（3）釋放對象。

（4）銷毀內存緩存。

3.8.2 SLAB 分配器

1．數據結構

內存緩存的數據結構如圖 3.22 所示。

（1）每個內存緩存對應一個 kmem_cache 實例。

成員 gfporder 是 slab 的階數，成員 num 是每個 slab 包含的對象數量，成員 object_size是對象原始長度，成員 size 是包括填充的對象長度。

（2）每個內存節點對應一個 kmem_cache_node 實例。

kmem_cache_node 實例包含 3 條 slab 鏈表：鏈表 slabs_partial 把部分對象空閑的 slab鏈接起來，鏈表 slabs_full 把沒有空閑對象的 slab 鏈接起來，鏈表 slabs_free 把所有對象空閑的 slab 鏈接起來。成員 total_slabs 是 slab 數量。

每個 slab 由一個或多個連續的物理頁組成，頁的階數是 kmem_cache.gfporder，如果階數大于 0，組成一個復合頁。slab 被劃分為多個對象，大多數情況下 slab 長度不是對象長度的整數倍，slab 有剩余部分，可以用來給 slab 著色：“把 slab 的第一個對象從 slab 的起始位置偏移一個數值，偏移值是處理器的一級緩存行長度的整數倍，不同 slab 的偏移值不同，使不同 slab 的對象映射到處理器不同的緩存行”，所以我們看到在 slab 的前面有一個著色部分。

page 結構體的相關成員如下。

1）成員 flags 設置標志位 PG_slab，表示頁屬于 SLAB 分配器。

2）成員 s_mem 存放 slab 第一個對象的地址。

3）成員 active 表示已分配對象的數量。

4）成員 lru 作為鏈表節點加入其中一條 slab 鏈表。

5）成員 slab_cache 指向 kmem_cache 實例。

6）成員 freelist 指向空閑對象鏈表。

這里解答思考題：kfree 函數怎么知道對象屬于哪個通用的內存緩存？分為 5 步。

• 根據對象的虛擬地址得到物理地址，因為塊分配器使用的虛擬地址屬于直接映射的內核虛擬地址空間，虛擬地址=物理地址+常量，把虛擬地址轉換成物理地址很方便。

• 根據物理地址得到物理頁號。

• 根據物理頁號得到 page 實例。

• 如果是復合頁，需要得到首頁的 page 實例。

• 根據 page 實例的成員 slab_cache 得到 kmem_cache 實例。

（3）kmem_cache 實例的成員 cpu_slab 指向 array_cache 實例，每個處理器對應一個array_cache 實例，稱為數組緩存，用來緩存剛剛釋放的對象，分配時首先從當前處理器的數組緩存分配，避免每次都要從 slab 分配，減少鏈表操作和鎖操作，提高分配速度。

成員limit 是數組大小，成員avail 是數組entry 存放的對象數量，數組entry 存放對象的地址。

每個對象的內存布局如圖 3.23 所示。

（1）紅色區域 1：長度是 8 字節，寫入一個魔幻數，如果值被修改，說明對象被改寫。

（2）真實對象：長度是 kmem_cache.obj_size，偏移是 kmem_cache.obj_offset。

（3）填充：用來對齊的填充字節。

（4）紅色區域 2：長度是 8 字節，寫入一個魔幻數，如果值被修改，說明對象被改寫。

（5）最后一個使用者：在 64 位系統上長度是 8 字節，存放最后一個調用者的地址，用來確定對象被誰改寫。

對象的長度是 kmem_cache.size。紅色區域 1、紅色區域 2 和最后一個使用者是可選的，當想要發現內存分配和使用的錯誤，打開調試配置宏 CONFIG_DEBUG_SLAB 的時候，對象才包含這 3 個成員。

kmem_cache.obj_size 是調用者指定的對象長度，kmem_cache.size 是對象實際占用的內存長度，通常比前者大，原因是為了提高訪問對象的速度，需要把對象的地址和長度都對齊到某個值，對齊值的計算步驟如下。

（1）如果創建內存緩存時指定了標志位 SLAB_HWCACHE_ALIGN，要求和處理器的一級緩存行的長度對齊，計算對齊值的方法如下。

• 如果對象的長度大于一級緩存行的長度的一半，對齊值取一級緩存行的長度。

• 如果對象的長度小于或等于一級緩存行的長度的一半，對齊值?。ㄒ患壘彺嫘械?/span>長度/），把個對象放在一個一級緩存行里面，需要為 n 找到一個合適的值。

• 如果對齊值小于指定的對齊值，取指定的對齊值。

舉例說明：假設指定的對齊值是 4 字節，一級緩存行的長度是 32 字節，對象的長度是12 字節，那么對齊值是 16 字節，對象占用的內存長度是 16 字節，把兩個對象放在一個一級緩存行里面。

(2)如果對齊值小于 ARCH_SLAB_MINALIGN，那么取 ARCH_SLAB_MINALIGN。ARCH_SLAB_MINALIGN 是各種處理器架構定義的最小對齊值，默認值是 8。

（3）把對齊值向上調整為指針長度的整數倍。

2．空閑對象鏈表

每個 slab 需要一個空閑對象鏈表，從而把所有空閑對象鏈接起來，空閑對象鏈表是用數組實現的，數組的元素個數是 slab 的對象數量，數組存放空閑對象的索引。假設一個 slab

包含 4 個對象，空閑對象鏈表的初始狀態如圖 3.24 所示。

page->freelist 指向空閑對象鏈表，數組中第 n 個元素存放的對象索引是 n，如果打開了SLAB 空閑鏈表隨機化的配置宏 CONFIG_SLAB_FREELIST_RANDOM，數組中第 n 個元素存放的對象索引是隨機的。

page->active 為 0，有兩重意思。

（1）存放空閑對象索引的第一個數組元素的索引是 0。

（2）已分配對象的數量是 0。

第一次分配對象，從 0 號數組元素取出空閑對象索引 0，page->active 增加到 1，空閑對象鏈表如圖 3.25 所示。

當所有對象分配完畢后，page->active 增加到 4，等于 slab 的對象數量，空閑對象鏈表如圖 3.26 所示。

當釋放索引為 0 的對象以后，page->active 減 1 變成 3，3 號數組元素存放空閑對象索引 0，空閑對象鏈表如圖 3.27 所示。

空閑對象鏈表的位置有 3 種選擇。

（1）使用一個對象存放空閑對象鏈表，此時 kmem_cache.flags 設置了標志位 CFLGS_OBJFREELIST_SLAB。

（2）把空閑對象鏈表放在 slab 外面，此時 kmem_cache.flags 設置了標志位 CFLGS_OFF_SLAB。

（3）把空閑對象鏈表放在 slab 尾部。如果 kmem_cache.flags 沒有設置上面兩個標志位，就表示把空閑對象鏈表放在 slab 尾部。

如果使用一個對象存放空閑對象鏈表，默認使用最后一個對象。如果打開了 SLAB 空閑鏈表隨機化的配置宏 CONFIG_SLAB_FREELIST_RANDOM，這個對象是隨機選擇的。

假設一個 slab 包含 4 個對象，使用 1 號對象存放空閑對象鏈表，初始狀態如圖 3.28 所示。

這種方案會不會導致可以分配的對象減少一個呢？答案是不會，存放空閑對象鏈表的對象可以被分配。這種方案采用了巧妙的方法。

（1）必須把存放空閑對象鏈表的對象索引放在空閑對象數組的最后面，保證這個對象是最后一個被分配出去的。

（2）分配最后一個空閑對象，page->active增加到 4，page->freelist 變成空指針，所有對象被分配出去，已經不需要空閑對象鏈表，如圖 3.29 所示。

（3）在所有對象分配完畢后，假設現在釋放 2 號對象，slab 使用 2 號對象存放空閑對象鏈表，page->freelist 指向 2 號對象，把對象索引 2 存放在空閑對象數組的最后面，如圖 3.30 所示。

如果把空閑對象鏈表放在 slab 外面，需要為空閑對象鏈表創建一個內存緩存，kmem_cache.freelist_cache 指向空閑對象鏈表的內存緩存，如圖 3.31 所示。

如果 slab 尾部的剩余部分足夠大，可以把空閑對象鏈表放在 slab 尾部，如圖 3.32所示。

創建內存緩存的時候，確定空閑對象鏈表的位置的方法如下。

（1）首先嘗試使用一個對象存放空閑對象鏈表。

1）如果指定了對象的構造函數，那么這種方案不適合。

2）如果指定了標志位 SLAB_TYPESAFE_BY_RCU，表示使用 RCU 技術延遲釋放 slab，那么這種方案不適合。

3）計算出 slab 長度和 slab 的對象數量，空閑對象鏈表的長度等于（slab 的對象數量 *對象索引長度）。如果空閑對象鏈表的長度大于對象長度，那么這種方案不適合。

（2）接著嘗試把空閑對象鏈表放在 slab 外面，計算出 slab 長度和 slab 的對象數量。如果 slab 的剩余長度大于或等于空閑對象鏈表的長度，應該把空閑對象鏈表放在 slab 尾部，不應該使用這種方案。

（3）最后嘗試把空閑對象鏈表放在 slab 尾部。

3．計算 slab 長度

函數 calculate_slab_order 負責計算 slab 長度，從 0 階到 kmalloc()函數支持的最大階數（KMALLOC_MAX_ORDER），嘗試如下。

（1）計算對象數量和剩余長度。

（2）如果對象數量是 0，那么不合適。

（3）如果對象數量大于允許的最大 slab 對象數量，那么不合適。允許的最大 slab 對象數量是 SLAB_OBJ_MAX_NUM，等于（× 8 ? 1），freelist_idx_t 是對象索引的數據類型。

（4）對于空閑對象鏈表在 slab 外面的情況，如果空閑對象鏈表的長度大于對象長度的一半，那么不合適。

（5）如果 slab 是可回收的（設置了標志位 SLAB_RECLAIM_ACCOUNT），那么選擇這個階數。

（6）如果階數大于或等于允許的最大 slab 階數（slab_max_order），那么選擇這個階數。盡量選擇低的階數，因為申請高階頁塊成功的概率低。

（7）如果剩余長度小于或等于 slab 長度的 1/8，那么選擇這個階數。

slab_max_order：允許的最大 slab 階數。如果內存容量大于 32MB，那么默認值是 1，否則默認值是 0?？梢酝ㄟ^內核參數“slab_max_order”指定。

4．著色

slab 是一個或多個連續的物理頁，起始地址總是頁長度的整數倍，不同 slab 中相同偏移的位置在處理器的一級緩存中的索引相同。如果 slab 的剩余部分的長度超過一級緩存行的長度，剩余部分對應的一級緩存行沒有被利用；如果對象的填充字節的長度超過一級緩存行的長度，填充字節對應的一級緩存行沒有被利用。這兩種情況導致處理器的某些緩存行被過度使用，另一些緩存行很少使用。

在 slab 的剩余部分的長度超過一級緩存行長度的情況下，為了均勻利用處理器的所有一級緩存行，slab 著色（slab coloring）利用 slab 的剩余部分，使不同 slab 的第一個對象的偏移不同。

著色是一個比喻，和顏色無關，只是表示 slab 中的第一個對象需要移動一個偏移值，使對象放到不同的一級緩存行里。

內存緩存中著色相關的成員如下。

（1）kmem_cache.colour_off 是顏色偏移，等于處理器的一級緩存行的長度，如果小于對齊值，那么取對齊值。

（2）kmem_cache.colour 是著色范圍，等于（slab 的剩余長度/顏色偏移）。

192 3.8 塊分配器

（3）kmem_cache.node[n]->colour_next 是下一種顏色，初始值是 0。

在內存節點 n 上創建新的 slab，計算 slab 的顏色偏移的方法如下。

（1）把kmem_cache.node[n]->colour_next 加1，如果大于或等于著色范圍，那么把值設置為0。

(2)slab 的顏色偏移 = kmem_cache.node[n]->colour_next * kmem_cache.colour_off。

slab 對應的 page 結構體的成員 s_mem 存放第一個對象的地址，等于（slab 的起始地址 +slab 的顏色偏移）。

5．每處理器數組緩存

如圖 3.33 所示，內存緩存為每個處理器創建了一個數組緩存（結構體 array_cache）。釋放對象時，把對象存放到當前處理器對應的數組緩存中；分配對象的時候，先從當前處理器的數組緩存分配對象，采用后進先出（Last In First Out，LIFO）的原則，這種做法可以提高性能。

（1）剛釋放的對象很可能還在處理器的緩存中，可以更好地利用處理器的緩存。

（2）減少鏈表操作。

（3）避免處理器之間的互斥，減少自旋鎖操作。

結構體 array_cache 如下。

（1）成員 entry 是存放對象地址的數組。

（2）成員 avail 是數組存放的對象的數量。

（3）成員 limit 是數組的大小，和結構體 kmem_cache 的成員 limit 的值相同，是根據對象長度猜測的一個值。

（4）成員 batchcount 是批量值，和結構體 kmem_cache 的成員 batchcount 的值相同，批量值是數組大小的一半。

分配對象的時候，先從當前處理器的數組緩存分配對象。如果數組緩存是空的，那么批量分配對象以重新填充數組緩存，批量值就是數組緩存的成員 batchcount。

釋放對象的時候，如果數組緩存是滿的，那么先把數組緩存中的對象批量歸還給 slab，批量值就是數組緩存的成員 batchcount，然后把正在釋放的對象存放到數組緩存中。

6．對 NUMA 的支持

我們看看 SLAB 分配器怎么支持 NUMA 系統。如圖 3.34 所示，內存緩存針對每個內存節點創建一個 kmem_cache_node 實例。

kmem_cache_node 實例的成員 shared 指向共享數組緩存，成員 alien 指向遠程節點數組緩存，每個節點一個遠程節點數組緩存。這兩個成員有什么用處呢？用來分階段釋放從其他節點借用的對象，先釋放到遠程節點數組緩存，然后轉移到共享數組緩存，最后釋放到遠程節點的 slab。

假設處理器 0 屬于內存節點 0，處理器 1 屬于內存節點 1。處理器 0 申請分配對象的時候，首先從節點 0 分配對象，如果分配失敗，從節點 1 借用對象。

處理器 0 釋放從節點 1 借用的對象時，需要把對象放到節點 0 的 kmem_cache_node 實例中與節點 1 對應的遠程節點緩存數組中，先看是不是滿了，如果是滿的，那么必須先清空：把對象轉移到節點 1 的共享數組緩存中，如果節點 1 的共享數組緩存滿了，那么把剩下的對象直接釋放到 slab。

分配和釋放本地內存節點的對象時，也會使用共享數組緩存。

（1）申請分配對象時，如果當前處理器的數組緩存是空的，共享數組緩存里面的對象可以用來重填。

（2）釋放對象時，如果當前處理器的數組緩存是滿的，并且共享數組緩存有空閑空間，那么可以轉移一部分對象到共享數組緩存，不需要把對象批量歸還給 slab，然后把正在釋放的對象添加到當前處理器的數組緩存中。

全局變量 use_alien_caches 用來控制是否使用遠程節點數組緩存分階段釋放從其他節點分配的對象，默認值是 1，可以在引導內核時使用內核參數“noaliencache”指定。

當包括填充的對象長度不超過頁長度的時候，使用共享數組緩存，數組大小是

（kmem_cache.shared * kmem_cache.batchcount），kmem_cache.batchcount 是批量值，kmem_cache.shared 用來控制共享數組緩存的大小，當前代碼實現指定的值是 8。

7．內存緩存合并

為了減少內存開銷和增加對象的緩存熱度，塊分配器會合并相似的內存緩存。在創建內存緩存的時候，從已經存在的內存緩存中找到一個相似的內存緩存，和原始的創建者共享這個內存緩存。3 種塊分配器都支持內存緩存合并。

假設正在創建的內存緩存是 t。

如果合并控制變量 slab_nomerge 的值是 1，那么不能合并。默認值是 0，如果想要禁止合并，可以在引導內核時使用內核參數“slab_nomerge”指定。

如果 t 指定了對象構造函數，不能合并。

如果 t 設置了阻止合并的標志位，那么不能合并。阻止合并的標志位是調試和使用 RCU技術延遲釋放 slab，其代碼如下：

#define SLAB_NEVER_MERGE (SLAB_RED_ZONE | SLAB_POISON | SLAB_STORE_USER| SLAB_TRACE | SLAB_TYPESAFE_BY_RCU | SLAB_NOLEAKTRACE |  SLAB_FAILSLAB | SLAB_KASAN)

遍歷每個內存緩存 s，判斷 t 是否可以和 s 合并。

（1）如果 s 設置了阻止合并的標志位，那么 t 不能和 s 合并。

（2）如果 s 指定了對象構造函數，那么 t 不能和 s 合并。

（3）如果 t 的對象長度大于 s 的對象長度，那么 t 不能和 s 合并。

（4）如果 t 的下面 4 個標志位和 s 不相同，那么 t 不能和 s 合并。

#define SLAB_MERGE_SAME (SLAB_RECLAIM_ACCOUNT | SLAB_CACHE_DMA |  SLAB_NOTRACK | SLAB_ACCOUNT)

（5）如果對齊值不兼容，即s 的對象長度不是t 的對齊值的整數倍，那么t 不能和s 合并。

（6）如果 s 的對象長度和 t 的對象長度的差值大于或等于指針長度，那么 t 不能和 s 合并。

（7）SLAB 分配器特有的檢查項：如果 t 的對齊值不是 0，并且 t 的對齊值大于 s 的對齊值，或者 s 的對齊值不是 t 的對齊值的整數倍，那么 t 不能和 s 合并。

（8）順利通過前面 7 項檢查，說明 t 和 s 可以合并。

找到可以合并的內存緩存以后，把引用計數加 1，對象的原始長度取兩者的最大值，然后把內存緩存的地址返回給調用者。

8．回收內存

對于所有對象空閑的 slab，沒有立即釋放，而是放在空閑 slab 鏈表中。只有內存節點上空閑對象的數量超過限制，才開始回收空閑 slab，直到空閑對象的數量小于或等于限制。

如圖 3.35 所示，結構體 kmem_cache_node的成員slabs_free是空閑slab鏈表的頭節點，成員 free_objects 是空閑對象的數量，成員 free_limit 是空閑對象的數量限制。

節點 n 的空閑對象的數量限制 = （1 + 節點的處理器數量）* kmem_cache.batchcount +kmem_cache.num。

SLAB 分配器定期回收對象和空閑 slab，實現方法是在每個處理器上向全局工作隊列添加 1 個延遲工作項，工作項的處理函數是 cache_reap。

每個處理器每隔 2 秒針對每個內存緩存執行。

（1）回收節點 n（假設當前處理器屬于節點 n）對應的遠程節點數組緩存中的對象。

（2）如果過去 2 秒沒有從當前處理器的數組緩存分配對象，那么回收數組緩存中的對象。

每個處理器每隔 4 秒針對每個內存緩存執行。

（1）如果過去 4 秒沒有從共享數組緩存分配對象，那么回收共享數組緩存中的對象。

（2）如果過去 4 秒沒有從空閑 slab 分配對象，那么回收空閑 slab。

9．調試

出現內存改寫時，我們需要定位出是誰改寫。SLAB 分配器提供了調試功能，我們可以打開調試配置宏 CONFIG_DEBUG_SLAB，此時對象增加 3 個字段：紅色區域 1、紅色區域 2 和最后一個使用者，如圖 3.36 所示。

分配對象時，把對象毒化：把最后 1 字節以外的每個字節設置為 0x5a，把最后一個字節設置為 0xa5；把對象前后的紅色區域設置為宏 RED_ACTIVE 表示的魔幻數；字段“最后一個使用者”保存調用函數的地址。

釋放對象時，檢查對象：如果對象前后的紅色區域都是宏 RED_ACTIVE 表示的魔幻數，說明正常；如果對象前后的紅色區域都是宏 RED_INACTIVE 表示的魔幻數，說明重復釋放；其他情況，說明寫越界。

釋放對象時，把對象毒化：把最后 1 字節以外的每個字節設置為 0x6b，把最后 1 字節設置為 0xa5；把對象前后的紅色區域都設置為 RED_INACTIVE，字段“最后一個使用者”保存調用函數的地址。

再次分配對象時，檢查對象：如果對象不符合“最后 1 字節以外的每個字節是 0x6b，最后 1 字節是 0xa5”，說明對象被改寫；如果對象前后的紅色區域不是宏 RED_INACTIVE表示的魔幻數，說明重復釋放或者寫越界。

3.8.3 SLUB 分配器

SLUB 分配器繼承了 SLAB 分配器的核心思想，在某些地方做了改進。

（1）SLAB 分配器的管理數據結構開銷大，早期每個 slab 有一個描述符和跟在后面的空閑對象數組。SLUB 分配器把 slab 的管理信息保存在 page 結構體中，使用聯合體重用 page

結構體的成員，沒有使 page 結構體的大小增加?，F在 SLAB 分配器反過來向 SLUB 分配器學習，拋棄了 slab 描述符，把 slab 的管理信息保存在 page 結構體中。

（2）SLAB 分配器的鏈表多，分為空閑 slab 鏈表、部分空閑 slab 鏈表和滿 slab 鏈表，管理復雜。SLUB 分配器只保留部分空閑 slab 鏈表。

（3）SLAB 分配器對 NUMA 系統的支持復雜，每個內存節點有共享數組緩存和遠程節點數組緩存，對象在這些數組緩存之間轉移，實現復雜。SLUB 分配器做了簡化。

（4）SLUB 分配器拋棄了效果不明顯的 slab 著色。

1．數據結構

SLUB 分配器內存緩存的數據結構如圖 3.37 所示。

（1）每個內存緩存對應一個 kmem_cache 實例。

成員 size 是包括元數據的對象長度，成員 object_size 是對象原始長度。

成員 oo 存放最優 slab 的階數和對象數，低 16 位是對象數，高 16 位是 slab 的階數，即 oo 等于（（slab 的階數 << 16）| 對象數）。最優 slab 是剩余部分最小的 slab。

成員 min 存放最小 slab 的階數和對象數，格式和 oo 相同。最小 slab 只需要足夠存放一個對象。當設備長時間運行以后，內存碎片化，分配連續物理頁很難成功，如果分配最優 slab 失敗，就分配最小 slab。

（2）每個內存節點對應一個 kmem_cache_node 實例。

鏈表 partial 把部分空閑的 slab 鏈接起來，成員 nr_partial 是部分空閑 slab 的數量。

（3）每個 slab 由一個或多個連續的物理頁組成，頁的階數是最優 slab 或最小 slab 的階第 3 章 內存管理數，如果階數大于 0，組成一個復合頁。

slab 被劃分為多個對象，如果 slab 長度不是對象長度的整數倍，尾部有剩余部分。尾部也可能有保留部分，kmem_cache 實例的成員 reserved 存放保留長度。

在創建內存緩存的時候，如果指定標志位 SLAB_TYPESAFE_BY_RCU，要求使用 RCU延遲釋放 slab，在調用函數 call_rcu 把釋放 slab 的函數加入 RCU 回調函數隊列的時候，需要提供一個 rcu_head 實例，slab 提供的 rcu_head 實例的位置分兩種情況。

1）如果 page 結構體的成員 lru 的長度大于或等于 rcu_head 結構體的長度，那么重用成員 lru。

2）如果 page 結構體的成員 lru 的長度小于 rcu_head 結構體的長度，那么必須在 slab尾部為 rcu_head 結構體保留空間，保留長度是 rcu_head 結構體的長度。

page 結構體的相關成員如下。

1）成員 flags 設置標志位 PG_slab，表示頁屬于 SLUB 分配器。

2）成員 freelist 指向第一個空閑對象。

3）成員 inuse 表示已分配對象的數量。

4）成員 objects 是對象數量。

5）成員 frozen 表示 slab 是否被凍結在每處理器 slab 緩存中。如果 slab 在每處理器 slab緩存中，它處于凍結狀態；如果 slab 在內存節點的部分空閑 slab 鏈表中，它處于解凍狀態。

6）成員 lru 作為鏈表節點加入部分空閑 slab 鏈表。

7）成員 slab_cache 指向 kmem_cache 實例。

（4）kmem_cache 實例的成員 cpu_slab 指向 kmem_cache_cpu 實例，每個處理器對應一個 kmem_cache_cpu 實例，稱為每處理器 slab 緩存。

SLAB 分配器的每處理器數組緩存以對象為單位，而 SLUB 分配器的每處理器 slab 緩存以 slab 為單位。

成員 freelist 指向當前使用的 slab 的空閑對象鏈表，成員 page 指向當前使用的 slab 對應的 page 實例，成員 partial 指向每處理器部分空閑 slab 鏈表。

對象有兩種內存布局，區別是空閑指針的位置不同。

第一種內存布局如圖 3.38 所示，空閑指針在紅色區域 2 的后面。

第二種內存布局如圖 3.39 所示，空閑指針重用真實對象的第一個字。

kmem_cache.offset 是空閑指針的偏移，空閑指針的地址等于（真實對象的地址 + 空閑指針偏移）。

紅色區域 1 的長度 = kmem_cache.red_left_pad = 字長對齊到指定的對齊值

紅色區域 2 的長度 = 字長 ?（對象長度 % 字長）

當開啟 SLUB 分配器的調試配置宏 CONFIG_SLUB_DEBUG 的時候，對象才包含紅色區域 1、紅色區域 2、分配用戶跟蹤和釋放用戶跟蹤這 4 個成員。

以下 3 種情況下選擇第一種內存布局。

（1）指定構造函數。

（2）指定標志位 SLAB_TYPESAFE_BY_RCU，要求使用 RCU 延遲釋放 slab。

（3）指定標志位 SLAB_POISON，要求毒化對象。

其他情況下使用第二種內存布局。

2．空閑對象鏈表

以對象使用第一種內存布局為例說明，一個 slab 的空閑對象鏈表的初始狀態如圖 3.40所示，page->freelist 指向第一個空閑對象中的真實對象，前一個空閑對象中的空閑指針指向后一個空閑對象中的真實對象，最后一個空閑對象中的空閑指針是空指針。如果打開了SLAB 空閑鏈表隨機化的配置宏 CONFIG_SLAB_FREELIST_RANDOM，每個對象在空閑對象鏈表中的位置是隨機的。

分配一個對象以后，page->freelist 指向下一個空閑對象中的真實對象，空閑對象鏈表如圖 3.41 所示。

3．計算 slab 長度

SLUB 分配器在創建內存緩存的時候計算了兩種 slab 長度：最優 slab 和最小 slab。最優 slab 是剩余部分比例最小的 slab，最小 slab 只需要足夠存放一個對象。當設備長時間運行以后，內存碎片化，分配連續物理頁很難成功，如果分配最優 slab 失敗，就分配最小 slab。

計算最優 slab 的長度時，有 3 個重要的控制參數。

（1）slub_min_objects：slab 的最小對象數量，默認值是 0，可以在引導內核時使用內核參數“slub_min_objects”設置。

（2）slub_min_order：slab 的最小階數，默認值是 0，可以在引導內核時使用內核參數“slub_min_order”設置。

（3）slub_max_order：slab 的最大階數，默認值是頁分配器認為昂貴的階數 3，可以在引導內核時使用內核參數“slub_max_order”設置。

函數 calculate_order 負責計算最優 slab 的長度，其算法如下：

函數 slab_order 負責計算階數，輸入參數是（對象長度 size，最小對象數量 min_objects，最大階數 max_order，剩余部分比例 fraction，保留長度 reserved），其算法如下：

4．每處理器 slab 緩存

SLAB分配器的每處理器緩存以對象為單位，而SLUB分配器的每處理器緩存以slab為單位。

如圖 3.42 所示，內存緩存為每個處理器創建了一個 slab 緩存。

（1）使用結構體 kmem_cache_cpu 描述 slab 緩存，成員 page 指向當前使用的 slab 對應的 page 實例，成員 freelist 指向空閑對象鏈表，成員 partial 指向部分空閑 slab 鏈表。

（2）當前使用的 slab 對應的 page 實例：成員 frozen 的值為 1，表示當前 slab 被凍結在每處理器 slab 緩存中；成員 freelist 被設置為空指針。

（3）部分空閑 slab 鏈表：只有打開配置宏 CONFIG_SLUB_CPU_PARTIAL，才會使用部分空閑 slab 鏈表（如果打開了調試配置宏 CONFIG_SLUB_DEBUG，還要求沒有設置 slab調試標志位），目前默認打開了這個配置宏。為了和內存節點的空閑 slab 鏈表區分，我們把每處理器 slab 緩存中的空閑 slab 鏈表稱為每處理器空閑 slab 鏈表。

鏈表中每個 slab 對應的 page 實例的成員 frozen 的值為 1，表示 slab 被凍結在每處理器slab 緩存中；成員 next 指向下一個 slab 對應的 page 實例。

鏈表中第一個 slab 對應的 page 實例的成員 pages 存放鏈表中 slab 的數量，成員 pobjects存放鏈表中空閑對象的數量；后面的 slab 沒有使用這兩個成員。

kmem_cache 實例的成員 cpu_partial 決定了鏈表中空閑對象的最大數量，是根據對象長度估算的值。

分配對象時，首先從當前處理器的 slab 緩存分配，如果當前有一個 slab 正在使用并且有空閑對象，那么分配一個對象；如果 slab 緩存中的部分空閑 slab 鏈表不是空的，那么取

第一個 slab 作為當前使用的 slab；其他情況下，需要重填當前處理器的 slab 緩存。

（1）如果內存節點的部分空閑 slab 鏈表不是空的，那么取第一個 slab 作為當前使用的slab，并且重填 slab 緩存中的部分空閑 slab 鏈表，直到取出的所有 slab 的空閑對象總數超過限制 kmem_cache.cpu_partial 的一半為止。

（2）否則，創建一個新的 slab，作為當前使用的 slab。

什么情況下會把 slab 放到每處理器部分空閑 slab 鏈表中？

釋放對象的時候，如果對象所屬的 slab 以前沒有空閑對象，并且沒有凍結在每處理器slab 緩存中，那么把 slab 放到當前處理器的部分空閑 slab 鏈表中。如果發現當前處理器的部分空閑 slab 鏈表中空閑對象的總數超過限制 kmem_cache.cpu_partial，先把鏈表中的所有slab 歸還到內存節點的部分空閑 slab 鏈表中。

這種做法的好處是：把空閑對象非常少的 slab 放在每處理器空閑 slab 鏈表中，優先從空閑對象非常少的 slab 分配對象，減少內存浪費。

5．對 NUMA 的支持

我們看看 SLUB 分配器怎么支持 NUMA 系統。

（1）內存緩存針對每個內存節點創建一個 kmem_cache_node 實例。

（2）分配對象時，如果當前處理器的 slab 緩存是空的，需要重填當前處理器的 slab 緩存。首先從本地內存節點的部分空閑 slab 鏈表中取 slab，如果本地內存節點的部分空閑 slab鏈表是空的，那么從其他內存節點的部分空閑 slab 鏈表借用 slab。

kmem_cache 實例的成員 remote_node_defrag_ratio 稱為遠程節點反碎片比例，用來控制從遠程節點借用部分空閑 slab 和從本地節點取部分空閑 slab 的比例，值越小，從本地節點取部分空閑 slab 的傾向越大。默認值是 1000，可以通過文件“/sys/kernel/slab/<內存緩存名稱>/remote_node_defrag_ratio”設置某個內存緩存的遠程節點反碎片比例，用戶設置的范圍是[0, 100]，內存緩存保存的比例值是乘以 10 以后的值。

函數 get_any_partial 負責從其他內存節點借用部分空閑 slab，算法如下：

6．回收內存

對于所有對象空閑的 slab，如果內存節點的部分空閑 slab 的數量大于或等于最小部分空閑 slab 數量，那么直接釋放，否則放在部分空閑 slab 鏈表的尾部。

最小部分空閑 slab 數量 kmem_cache.min_partial 的計算方法是：（log2 對象長度）/2，并且把限制在范圍[5,10]。

7．調試

如果我們需要使用 SLUB 分配器的調試功能，首先需要打開調試配置宏 CONFIG_DEBUG_SLUB，然后有如下兩種選擇。

（1）打開配置宏 CONFIG_SLUB_DEBUG_ON，為所有內存緩存打開所有調試選項。

（2）在引導內核時使用內核參數“slub_debug”。

slub_debug=<調試選項> 為所有內存緩存打開調試選項slub_debug=<調試選項>,<內存緩存名稱> 只為指定的內存緩存打開調試選項

調試選項如下所示。

1）F：在分配和釋放時執行昂貴的一致性檢查（對應標志位 SLAB_CONSISTENCY_CHECKS）

2）Z：紅色區域（對應標志位 SLAB_RED_ZONE）

3）P：毒化對象（對應標志位 SLAB_POISON）

4）U：分配/釋放用戶跟蹤（對應標志位 SLAB_STORE_USER）

5）T：跟蹤分配和釋放（對應標志位 SLAB_TRACE），只在一個內存緩存上使用。

6）A：注入分配對象失敗的錯誤（對應標志位 SLAB_FAILSLAB，需要打開配置宏CONFIG_FAILSLAB）

7）O：為可能導致更高的最小 slab 階數的內存緩存關閉調試。

8）-：關閉所有調試選項，在內核配置了 CONFIG_SLUB_DEBUG_ON 時有用處。

如果沒有指定調試選項（即“slub_debug=”），表示打開所有調試選項。

3.8.4 SLOB 分配器

SLOB 分配器最大的特點就是簡潔，代碼只有 600 多行，特別適合小內存的嵌入式設備。

1．數據結構

SLOB 分配器內存緩存的數據結構如圖 3.43 所示。

（1）每個內存緩存對應一個 kmem_cache 實例。

成員 object_size 是對象原始長度，成員 size 是包括填充的對象長度，align 是對齊值。

（2）所有內存緩存共享 slab，所有對象長度小于 256 字節的內存緩存共享小對象 slab鏈表中的 slab，所有對象長度小于 1024 字節的內存緩存共享中等對象 slab 鏈表中的 slab，所有對象長度小于 1 頁的內存緩存共享大對象 slab 鏈表中的 slab。對象長度大于或等于 1頁的內存緩存，直接從頁分配器分配頁，不需要經過 SLOB 分配器。

每個 slab 的長度是一頁，page 結構體的相關成員如下。

1）成員 flags 設置標志位 PG_slab，表示頁屬于 SLOB 分配器；設置標志位 PG_slob_free，表示 slab 在 slab 鏈表中。

2）成員 freelist 指向第一個空閑對象。

3）成員 units 表示空閑單元的數量。

4）成員 lru 作為鏈表節點加入 slab 鏈表。

SLOB 分配器的分配粒度是單元，也就是說，分配長度必須是單元的整數倍，單元是數據類型 slobidx_t 的長度，通常是 2 字節。數據類型 slobidx_t 的定義如下：

mm/slob.c#if PAGE_SIZE <= (32767 * 2)typedef s16 slobidx_t;#elsetypedef s32 slobidx_t;#endif

2．空閑對象鏈表

我們看看 SLOB 分配器怎么組織空閑對象。在 SLOB 分配器中，對象更準確的說法是塊（block），因為多個對象長度不同的內存緩存可能從同一個 slab 分配對象，一個 slab 可能出現大小不同的塊。

空閑塊的內存布局分為如下兩種情況。

（1）對于長度大于一個單元的塊，第一個單元存放塊長度，第二個單元存放下一個空閑塊的偏移。

（2）對于只有一個單元的塊，該單元存放下一個空閑塊的偏移的相反數，也就是說，是一個負數。

長度和偏移都是單元數量，偏移的基準是頁的起始地址。

已經分配出去的塊：如果是使用 kmalloc()從通用內存緩存分配的塊，使用塊前面的 4字節存放申請的字節數，因為使用 kfree()釋放時需要知道塊的長度。如果是從專用內存緩存分配的塊，從 kmem_cache 結構體的成員 size 可以知道塊的長度。

假設頁長度是 4KB，單元是 2 字節，一個 slab 的空閑對象鏈表的初始狀態如圖 3.44 所示。

slab 只有一個空閑塊，第一個單元存放長度 2048，第二個單元存放下一個空閑塊的偏移 2048，

slab 對應的 page 結構體的成員 freelist 指向第一個空閑塊，成員 units 存放空閑單元數量 2048。

假設一個對象長度是 32 字節的內存緩存從這個 slab 分配了一個對象，空閑對象鏈表如圖 3.45 所示，slab 的前面 32 字節被分配，空閑塊從第 32 字節開始，第一個單元存放長度2032，第二個單元存放下一個空閑塊的偏移 2048，slab 對應的 page 結構體的成員 freelist指向這個空閑塊，成員 units 存放空閑單元數量 2032。

3．分配對象

分配對象時，根據對象長度選擇不同的策略。

（1）如果對象長度小于 256 字節，那么從小對象 slab 鏈表中查找 slab 分配。

（2）如果對象長度小于 1024 字節，那么從中等對象 slab 鏈表中查找 slab 分配。

（3）如果對象長度小于 1 頁，那么從大對象 slab 鏈表中查找 slab 分配。

（4）如果對象長度大于或等于 1 頁，那么直接從頁分配器分配頁，不需要經過 SLOB分配器。

對于前面 3 種情況，遍歷 slab 鏈表，對于空閑單元數量（page.units）大于或等于對象長度的 slab，遍歷空閑對象鏈表，當找到一個合適的空閑塊時，處理方法是：如果空閑塊的長度等于對象長度，那么把這個空閑塊從空閑對象鏈表中刪除；如果空閑塊的長度大于對象長度，那么把這個空閑塊分裂為兩部分，一部分分配出去，剩下部分放在空閑對象鏈表中。

如果分配對象以后，slab 的空閑單元數量變成零，那么從 slab 鏈表中刪除，并且清除標志位 PG_slob_free。

為了減少平均查找時間，從某個 slab 分配對象以后，把 slab 鏈表的頭節點移到這個 slab的前面，下一次分配對象的時候從這個 slab 開始查找。

如果遍歷完 slab 鏈表，沒有找到合適的空閑塊，那么創建新的 slab。

審核編輯：湯梓紅