Linux內(nèi)核之塊分配器

作者簡介：

余華兵，2005年畢業(yè)于華中科技大學(xué)計算機(jī)學(xué)院，取得碩士學(xué)位。畢業(yè)后的十余年一直在網(wǎng)絡(luò)通信行業(yè)從事軟件設(shè)計和開發(fā)工作，研究方向包括IPv4協(xié)議棧、IPv6協(xié)議棧和Linux內(nèi)核。

目錄

3.8塊分配器

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

3.8 塊分配器

為了解決小塊內(nèi)存的分配問題，Linux 內(nèi)核提供了塊分配器，最早實現(xiàn)的塊分配器是SLAB 分配器。

SLAB 分配器的作用不僅僅是分配小塊內(nèi)存，更重要的作用是針對經(jīng)常分配和釋放的對象充當(dāng)緩存。SLAB 分配器的核心思想是：為每種對象類型創(chuàng)建一個內(nèi)存緩存，每個內(nèi)存緩存由多個大塊（slab，原意是大塊的混凝土）組成，一個大塊是一個或多個連續(xù)的物理頁，每個大塊包含多個對象。SLAB 采用了面向?qū)ο蟮乃枷?，基于對象類型管理?nèi)存，每種對象被劃分為一類，例如進(jìn)程描述符（task_struct）是一個類，每個進(jìn)程描述符實例是一個對象。

內(nèi)存緩存的組成如圖3.21所示。

SLAB 分配器在某些情況下表現(xiàn)不太好，所以 Linux 內(nèi)核提供了兩個改進(jìn)的塊分配器。

（1）在配備了大量物理內(nèi)存的大型計算機(jī)上，SLAB 分配器的管理數(shù)據(jù)結(jié)構(gòu)的內(nèi)存開銷比較大，所以設(shè)計了 SLUB 分配器。

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

目前 SLUB 分配器已成為默認(rèn)的塊分配器。

3.8.1 編程接口

3 種塊分配器提供了統(tǒng)一的編程接口。

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

通用的內(nèi)存緩存的編程接口如下。

（1）分配內(nèi)存。

（2）重新分配內(nèi)存。

（3）釋放內(nèi)存。

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

（1）創(chuàng)建內(nèi)存緩存。

（2）從指定的內(nèi)存緩存分配對象。

（3）釋放對象。

（4）銷毀內(nèi)存緩存。

3.8.2 SLAB 分配器

1．?dāng)?shù)據(jù)結(jié)構(gòu)

內(nèi)存緩存的數(shù)據(jù)結(jié)構(gòu)如圖 3.22 所示。

（1）每個內(nèi)存緩存對應(yīng)一個 kmem_cache 實例。

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

（2）每個內(nèi)存節(jié)點對應(yīng)一個 kmem_cache_node 實例。

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

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

page 結(jié)構(gòu)體的相關(guān)成員如下。

1）成員 flags 設(shè)置標(biāo)志位 PG_slab，表示頁屬于 SLAB 分配器。

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

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

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

5）成員 slab_cache 指向 kmem_cache 實例。

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

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

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

• 根據(jù)物理地址得到物理頁號。

• 根據(jù)物理頁號得到 page 實例。

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

• 根據(jù) page 實例的成員 slab_cache 得到 kmem_cache 實例。

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

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

每個對象的內(nèi)存布局如圖 3.23 所示。

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

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

（3）填充：用來對齊的填充字節(jié)。

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

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

對象的長度是 kmem_cache.size。紅色區(qū)域 1、紅色區(qū)域 2 和最后一個使用者是可選的，當(dāng)想要發(fā)現(xiàn)內(nèi)存分配和使用的錯誤，打開調(diào)試配置宏 CONFIG_DEBUG_SLAB 的時候，對象才包含這 3 個成員。

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

（1）如果創(chuàng)建內(nèi)存緩存時指定了標(biāo)志位 SLAB_HWCACHE_ALIGN，要求和處理器的一級緩存行的長度對齊，計算對齊值的方法如下。

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

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

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

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

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

（3）把對齊值向上調(diào)整為指針長度的整數(shù)倍。

2．空閑對象鏈表

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

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

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

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

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

（2）已分配對象的數(shù)量是 0。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

創(chuàng)建內(nèi)存緩存的時候，確定空閑對象鏈表的位置的方法如下。

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

1）如果指定了對象的構(gòu)造函數(shù)，那么這種方案不適合。

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

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

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

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

3．計算 slab 長度

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

（1）計算對象數(shù)量和剩余長度。

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

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

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

（5）如果 slab 是可回收的（設(shè)置了標(biāo)志位 SLAB_RECLAIM_ACCOUNT），那么選擇這個階數(shù)。

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

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

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

4．著色

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

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

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

內(nèi)存緩存中著色相關(guān)的成員如下。

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

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

192 3.8 塊分配器

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

在內(nèi)存節(jié)點 n 上創(chuàng)建新的 slab，計算 slab 的顏色偏移的方法如下。

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

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

slab 對應(yīng)的 page 結(jié)構(gòu)體的成員 s_mem 存放第一個對象的地址，等于（slab 的起始地址 +slab 的顏色偏移）。

5．每處理器數(shù)組緩存

如圖 3.33 所示，內(nèi)存緩存為每個處理器創(chuàng)建了一個數(shù)組緩存（結(jié)構(gòu)體 array_cache）。釋放對象時，把對象存放到當(dāng)前處理器對應(yīng)的數(shù)組緩存中；分配對象的時候，先從當(dāng)前處理器的數(shù)組緩存分配對象，采用后進(jìn)先出（Last In First Out，LIFO）的原則，這種做法可以提高性能。

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

（2）減少鏈表操作。

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

結(jié)構(gòu)體 array_cache 如下。

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

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

（3）成員 limit 是數(shù)組的大小，和結(jié)構(gòu)體 kmem_cache 的成員 limit 的值相同，是根據(jù)對象長度猜測的一個值。

（4）成員 batchcount 是批量值，和結(jié)構(gòu)體 kmem_cache 的成員 batchcount 的值相同，批量值是數(shù)組大小的一半。

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

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

6．對 NUMA 的支持

我們看看 SLAB 分配器怎么支持 NUMA 系統(tǒng)。如圖 3.34 所示，內(nèi)存緩存針對每個內(nèi)存節(jié)點創(chuàng)建一個 kmem_cache_node 實例。

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

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

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

分配和釋放本地內(nèi)存節(jié)點的對象時，也會使用共享數(shù)組緩存。

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

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

全局變量 use_alien_caches 用來控制是否使用遠(yuǎn)程節(jié)點數(shù)組緩存分階段釋放從其他節(jié)點分配的對象，默認(rèn)值是 1，可以在引導(dǎo)內(nèi)核時使用內(nèi)核參數(shù)“noaliencache”指定。

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

（kmem_cache.shared * kmem_cache.batchcount），kmem_cache.batchcount 是批量值，kmem_cache.shared 用來控制共享數(shù)組緩存的大小，當(dāng)前代碼實現(xiàn)指定的值是 8。

7．內(nèi)存緩存合并

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

假設(shè)正在創(chuàng)建的內(nèi)存緩存是 t。

如果合并控制變量 slab_nomerge 的值是 1，那么不能合并。默認(rèn)值是 0，如果想要禁止合并，可以在引導(dǎo)內(nèi)核時使用內(nèi)核參數(shù)“slab_nomerge”指定。

如果 t 指定了對象構(gòu)造函數(shù)，不能合并。

如果 t 設(shè)置了阻止合并的標(biāo)志位，那么不能合并。阻止合并的標(biāo)志位是調(diào)試和使用 RCU技術(shù)延遲釋放 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)

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

（1）如果 s 設(shè)置了阻止合并的標(biāo)志位，那么 t 不能和 s 合并。

（2）如果 s 指定了對象構(gòu)造函數(shù)，那么 t 不能和 s 合并。

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

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

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

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

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

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

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

找到可以合并的內(nèi)存緩存以后，把引用計數(shù)加 1，對象的原始長度取兩者的最大值，然后把內(nèi)存緩存的地址返回給調(diào)用者。

8．回收內(nèi)存

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

如圖 3.35 所示，結(jié)構(gòu)體 kmem_cache_node的成員slabs_free是空閑slab鏈表的頭節(jié)點，成員 free_objects 是空閑對象的數(shù)量，成員 free_limit 是空閑對象的數(shù)量限制。

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

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

每個處理器每隔 2 秒針對每個內(nèi)存緩存執(zhí)行。

（1）回收節(jié)點 n（假設(shè)當(dāng)前處理器屬于節(jié)點 n）對應(yīng)的遠(yuǎn)程節(jié)點數(shù)組緩存中的對象。

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

每個處理器每隔 4 秒針對每個內(nèi)存緩存執(zhí)行。

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

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

9．調(diào)試

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

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

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

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

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

3.8.3 SLUB 分配器

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

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

結(jié)構(gòu)體的成員，沒有使 page 結(jié)構(gòu)體的大小增加?，F(xiàn)在 SLAB 分配器反過來向 SLUB 分配器學(xué)習(xí)，拋棄了 slab 描述符，把 slab 的管理信息保存在 page 結(jié)構(gòu)體中。

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

（3）SLAB 分配器對 NUMA 系統(tǒng)的支持復(fù)雜，每個內(nèi)存節(jié)點有共享數(shù)組緩存和遠(yuǎn)程節(jié)點數(shù)組緩存，對象在這些數(shù)組緩存之間轉(zhuǎn)移，實現(xiàn)復(fù)雜。SLUB 分配器做了簡化。

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

1．?dāng)?shù)據(jù)結(jié)構(gòu)

SLUB 分配器內(nèi)存緩存的數(shù)據(jù)結(jié)構(gòu)如圖 3.37 所示。

（1）每個內(nèi)存緩存對應(yīng)一個 kmem_cache 實例。

成員 size 是包括元數(shù)據(jù)的對象長度，成員 object_size 是對象原始長度。

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

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

（2）每個內(nèi)存節(jié)點對應(yīng)一個 kmem_cache_node 實例。

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

（3）每個 slab 由一個或多個連續(xù)的物理頁組成，頁的階數(shù)是最優(yōu) slab 或最小 slab 的階第 3 章 內(nèi)存管理數(shù)，如果階數(shù)大于 0，組成一個復(fù)合頁。

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

在創(chuàng)建內(nèi)存緩存的時候，如果指定標(biāo)志位 SLAB_TYPESAFE_BY_RCU，要求使用 RCU延遲釋放 slab，在調(diào)用函數(shù) call_rcu 把釋放 slab 的函數(shù)加入 RCU 回調(diào)函數(shù)隊列的時候，需要提供一個 rcu_head 實例，slab 提供的 rcu_head 實例的位置分兩種情況。

1）如果 page 結(jié)構(gòu)體的成員 lru 的長度大于或等于 rcu_head 結(jié)構(gòu)體的長度，那么重用成員 lru。

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

page 結(jié)構(gòu)體的相關(guān)成員如下。

1）成員 flags 設(shè)置標(biāo)志位 PG_slab，表示頁屬于 SLUB 分配器。

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

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

4）成員 objects 是對象數(shù)量。

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

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

7）成員 slab_cache 指向 kmem_cache 實例。

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

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

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

對象有兩種內(nèi)存布局，區(qū)別是空閑指針的位置不同。

第一種內(nèi)存布局如圖 3.38 所示，空閑指針在紅色區(qū)域 2 的后面。

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

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

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

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

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

以下 3 種情況下選擇第一種內(nèi)存布局。

（1）指定構(gòu)造函數(shù)。

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

（3）指定標(biāo)志位 SLAB_POISON，要求毒化對象。

其他情況下使用第二種內(nèi)存布局。

2．空閑對象鏈表

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

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

3．計算 slab 長度

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

計算最優(yōu) slab 的長度時，有 3 個重要的控制參數(shù)。

（1）slub_min_objects：slab 的最小對象數(shù)量，默認(rèn)值是 0，可以在引導(dǎo)內(nèi)核時使用內(nèi)核參數(shù)“slub_min_objects”設(shè)置。

（2）slub_min_order：slab 的最小階數(shù)，默認(rèn)值是 0，可以在引導(dǎo)內(nèi)核時使用內(nèi)核參數(shù)“slub_min_order”設(shè)置。

（3）slub_max_order：slab 的最大階數(shù)，默認(rèn)值是頁分配器認(rèn)為昂貴的階數(shù) 3，可以在引導(dǎo)內(nèi)核時使用內(nèi)核參數(shù)“slub_max_order”設(shè)置。

函數(shù) calculate_order 負(fù)責(zé)計算最優(yōu) slab 的長度，其算法如下：

函數(shù) slab_order 負(fù)責(zé)計算階數(shù)，輸入?yún)?shù)是（對象長度 size，最小對象數(shù)量 min_objects，最大階數(shù) max_order，剩余部分比例 fraction，保留長度 reserved），其算法如下：

4．每處理器 slab 緩存

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

如圖 3.42 所示，內(nèi)存緩存為每個處理器創(chuàng)建了一個 slab 緩存。

（1）使用結(jié)構(gòu)體 kmem_cache_cpu 描述 slab 緩存，成員 page 指向當(dāng)前使用的 slab 對應(yīng)的 page 實例，成員 freelist 指向空閑對象鏈表，成員 partial 指向部分空閑 slab 鏈表。

（2）當(dāng)前使用的 slab 對應(yīng)的 page 實例：成員 frozen 的值為 1，表示當(dāng)前 slab 被凍結(jié)在每處理器 slab 緩存中；成員 freelist 被設(shè)置為空指針。

（3）部分空閑 slab 鏈表：只有打開配置宏 CONFIG_SLUB_CPU_PARTIAL，才會使用部分空閑 slab 鏈表（如果打開了調(diào)試配置宏 CONFIG_SLUB_DEBUG，還要求沒有設(shè)置 slab調(diào)試標(biāo)志位），目前默認(rèn)打開了這個配置宏。為了和內(nèi)存節(jié)點的空閑 slab 鏈表區(qū)分，我們把每處理器 slab 緩存中的空閑 slab 鏈表稱為每處理器空閑 slab 鏈表。

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

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

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

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

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

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

（2）否則，創(chuàng)建一個新的 slab，作為當(dāng)前使用的 slab。

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

釋放對象的時候，如果對象所屬的 slab 以前沒有空閑對象，并且沒有凍結(jié)在每處理器slab 緩存中，那么把 slab 放到當(dāng)前處理器的部分空閑 slab 鏈表中。如果發(fā)現(xiàn)當(dāng)前處理器的部分空閑 slab 鏈表中空閑對象的總數(shù)超過限制 kmem_cache.cpu_partial，先把鏈表中的所有slab 歸還到內(nèi)存節(jié)點的部分空閑 slab 鏈表中。

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

5．對 NUMA 的支持

我們看看 SLUB 分配器怎么支持 NUMA 系統(tǒng)。

（1）內(nèi)存緩存針對每個內(nèi)存節(jié)點創(chuàng)建一個 kmem_cache_node 實例。

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

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

函數(shù) get_any_partial 負(fù)責(zé)從其他內(nèi)存節(jié)點借用部分空閑 slab，算法如下：

6．回收內(nèi)存

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

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

7．調(diào)試

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

（1）打開配置宏 CONFIG_SLUB_DEBUG_ON，為所有內(nèi)存緩存打開所有調(diào)試選項。

（2）在引導(dǎo)內(nèi)核時使用內(nèi)核參數(shù)“slub_debug”。

slub_debug=<調(diào)試選項> 為所有內(nèi)存緩存打開調(diào)試選項slub_debug=<調(diào)試選項>,<內(nèi)存緩存名稱> 只為指定的內(nèi)存緩存打開調(diào)試選項

調(diào)試選項如下所示。

1）F：在分配和釋放時執(zhí)行昂貴的一致性檢查（對應(yīng)標(biāo)志位 SLAB_CONSISTENCY_CHECKS）

2）Z：紅色區(qū)域（對應(yīng)標(biāo)志位 SLAB_RED_ZONE）

3）P：毒化對象（對應(yīng)標(biāo)志位 SLAB_POISON）

4）U：分配/釋放用戶跟蹤（對應(yīng)標(biāo)志位 SLAB_STORE_USER）

5）T：跟蹤分配和釋放（對應(yīng)標(biāo)志位 SLAB_TRACE），只在一個內(nèi)存緩存上使用。

6）A：注入分配對象失敗的錯誤（對應(yīng)標(biāo)志位 SLAB_FAILSLAB，需要打開配置宏CONFIG_FAILSLAB）

7）O：為可能導(dǎo)致更高的最小 slab 階數(shù)的內(nèi)存緩存關(guān)閉調(diào)試。

8）-：關(guān)閉所有調(diào)試選項，在內(nèi)核配置了 CONFIG_SLUB_DEBUG_ON 時有用處。

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

3.8.4 SLOB 分配器

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

1．?dāng)?shù)據(jù)結(jié)構(gòu)

SLOB 分配器內(nèi)存緩存的數(shù)據(jù)結(jié)構(gòu)如圖 3.43 所示。

（1）每個內(nèi)存緩存對應(yīng)一個 kmem_cache 實例。

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

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

每個 slab 的長度是一頁，page 結(jié)構(gòu)體的相關(guān)成員如下。

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

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

3）成員 units 表示空閑單元的數(shù)量。

4）成員 lru 作為鏈表節(jié)點加入 slab 鏈表。

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

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

2．空閑對象鏈表

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

空閑塊的內(nèi)存布局分為如下兩種情況。

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

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

長度和偏移都是單元數(shù)量，偏移的基準(zhǔn)是頁的起始地址。

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

假設(shè)頁長度是 4KB，單元是 2 字節(jié)，一個 slab 的空閑對象鏈表的初始狀態(tài)如圖 3.44 所示。

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

slab 對應(yīng)的 page 結(jié)構(gòu)體的成員 freelist 指向第一個空閑塊，成員 units 存放空閑單元數(shù)量 2048。

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

3．分配對象

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

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

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

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

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

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

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

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

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

審核編輯：湯梓紅