Linux的物理內(nèi)存管理采用了以頁為單位的buddy system（伙伴系統(tǒng)），但是很多情況下，內(nèi)核僅僅需要一個(gè)較小的對(duì)象空間，而且這些小塊的空間對(duì)于不同對(duì)象又是變化的、不可預(yù)測的，所以需要一種類似用戶空間堆內(nèi)存的管理機(jī)制（malloc/free）。然而內(nèi)核對(duì)對(duì)象的管理又有一定的特殊性，有些對(duì)象的訪問非常頻繁，需要采用緩沖機(jī)制；對(duì)象的組織需要考慮硬件cache的影響；需要考慮多處理器以及NUMA架構(gòu)的影響。90年代初期，在Solaris 2.4操作系統(tǒng)中，采用了一種稱為“slab”（原意是大塊的混凝土）的緩沖區(qū)分配和管理方法，在相當(dāng)程度上滿足了內(nèi)核的特殊需求。

多年以來，SLAB成為linux kernel對(duì)象緩沖區(qū)管理的主流算法，甚至長時(shí)間沒有人愿意去修改，因?yàn)樗鼘?shí)在是非常復(fù)雜，而且在大多數(shù)情況下，它的工作完成的相當(dāng)不錯(cuò)。但是，隨著大規(guī)模多處理器系統(tǒng)和 NUMA系統(tǒng)的廣泛應(yīng)用，SLAB 分配器逐漸暴露出自身的嚴(yán)重不足：

1）。 緩存隊(duì)列管理復(fù)雜；

2）。 管理數(shù)據(jù)存儲(chǔ)開銷大；

3）。 對(duì)NUMA支持復(fù)雜；

4）。 調(diào)試調(diào)優(yōu)困難；

5）。 摒棄了效果不太明顯的slab著色機(jī)制；

針對(duì)這些SLAB不足，內(nèi)核開發(fā)人員Christoph Lameter在Linux內(nèi)核2.6.22版本中引入一種新的解決方案：SLUB分配器。SLUB分配器特點(diǎn)是簡化設(shè)計(jì)理念，同時(shí)保留SLAB分配器的基本思想：每個(gè)緩沖區(qū)由多個(gè)小的slab 組成，每個(gè) slab 包含固定數(shù)目的對(duì)象。SLUB分配器簡化kmem_cache，slab等相關(guān)的管理數(shù)據(jù)結(jié)構(gòu)，摒棄了SLAB 分配器中眾多的隊(duì)列概念，并針對(duì)多處理器、NUMA系統(tǒng)進(jìn)行優(yōu)化，從而提高了性能和可擴(kuò)展性并降低了內(nèi)存的浪費(fèi)。為了保證內(nèi)核其它模塊能夠無縫遷移到SLUB分配器，SLUB還保留了原有SLAB分配器所有的接口API函數(shù)。

（注：本文源碼分析基于linux-4.1.x）

整體數(shù)據(jù)結(jié)構(gòu)關(guān)系如下圖所示：

1 SLUB分配器的初始化

SLUB初始化有兩個(gè)重要的工作：第一，創(chuàng)建用于申請(qǐng)struct kmem_cache和struct kmem_cache_node的kmem_cache；第二，創(chuàng)建用于常規(guī)kmalloc的kmem_cache。

1.1 申請(qǐng)kmem_cache的kmem_cache

第一個(gè)工作涉及到一個(gè)“先有雞還是先有蛋”的問題，因?yàn)閯?chuàng)建kmem_cache需要從kmem_cache的緩沖區(qū)申請(qǐng)，而這時(shí)候還沒有創(chuàng)建kmem_cache的緩沖區(qū)。kernel的解決辦法是先用兩個(gè)靜態(tài)變量boot_kmem_cache和boot_kmem_cache_node來保存struct kmem_cach和struct kmem_cache_node緩沖區(qū)管理數(shù)據(jù)，以兩個(gè)靜態(tài)變量為基礎(chǔ)申請(qǐng)大小為struct kmem_cache和struct kmem_cache_node對(duì)象大小的slub緩沖區(qū)，隨后再從這些緩沖區(qū)中分別申請(qǐng)兩個(gè)kmem_cache，然后把boot_kmem_cache和boot_kmem_cache_node中的內(nèi)容拷貝到新申請(qǐng)的對(duì)象中，從而完成了struct kmem_cache和struct kmem_cache_node管理結(jié)構(gòu)的bootstrap（自引導(dǎo)）。

void __init kmem_cache_init（void）

{

//聲明靜態(tài)變量，存儲(chǔ)臨時(shí)kmem_cache管理結(jié)構(gòu)

static __initdata struct kmem_cache boot_kmem_cache，

boot_kmem_cache_node;

???

kmem_cache_node = &boot_kmem_cache_node;

kmem_cache = &boot_kmem_cache;

//申請(qǐng)slub緩沖區(qū)，管理數(shù)據(jù)放在臨時(shí)結(jié)構(gòu)中

create_boot_cache（kmem_cache_node， “kmem_cache_node”，

sizeof（struct kmem_cache_node）， SLAB_HWCACHE_ALIGN）;

create_boot_cache（kmem_cache， “kmem_cache”，

offsetof（struct kmem_cache， node） +

nr_node_ids * sizeof（struct kmem_cache_node *），

SLAB_HWCACHE_ALIGN）;

//從剛才掛在臨時(shí)結(jié)構(gòu)的緩沖區(qū)中申請(qǐng)kmem_cache的kmem_cache，并將管理數(shù)據(jù)拷貝到新申請(qǐng)的內(nèi)存中

kmem_cache = bootstrap（&boot_kmem_cache）;

//從剛才掛在臨時(shí)結(jié)構(gòu)的緩沖區(qū)中申請(qǐng)kmem_cache_node的kmem_cache，并將管理數(shù)據(jù)拷貝到新申請(qǐng)的內(nèi)存中

kmem_cache_node = bootstrap（&boot_kmem_cache_node）;

???

}

1.2 創(chuàng)建kmalloc常規(guī)緩存

原則上系統(tǒng)會(huì)為每個(gè)2次冪大小的內(nèi)存塊申請(qǐng)一個(gè)緩存，但是內(nèi)存塊過小時(shí)，會(huì)產(chǎn)生很多碎片浪費(fèi)，所以系統(tǒng)為96B和192B也各自創(chuàng)建了一個(gè)緩存。于是利用了一個(gè)size_index數(shù)組來幫助確定小于192B的內(nèi)存塊使用哪個(gè)緩存

void __init create_kmalloc_caches（unsigned long flags）

{

???

/*使用SLUB時(shí)KMALLOC_SHIFT_LOW=3，KMALLOC_SHIFT_HIGH=13

也就是說使用kmalloc能夠申請(qǐng)的最小內(nèi)存是8B，最大內(nèi)存是8KB

申請(qǐng)內(nèi)存是向上對(duì)其2的n次冪，創(chuàng)建對(duì)應(yīng)大小緩存保存在kmalloc_caches ［n］*/

for （i = KMALLOC_SHIFT_LOW; i 《= KMALLOC_SHIFT_HIGH; i++） {

if （！kmalloc_caches［i］） {

kmalloc_caches［i］ = create_kmalloc_cache（NULL，

1 《《 i， flags）;

}

/*

* Caches that are not of the two-to-the-power-of size.

* These have to be created immediately after the

* earlier power of two caches

*/

/*有兩個(gè)例外，大小為64~96B和128B~192B，單獨(dú)創(chuàng)建了兩個(gè)緩存

保存在kmalloc_caches ［1］和kmalloc_caches ［2］*/

if （KMALLOC_MIN_SIZE 《= 32 && ！kmalloc_caches［1］ && i == 6）

kmalloc_caches［1］ = create_kmalloc_cache（NULL， 96， flags）;

if （KMALLOC_MIN_SIZE 《= 64 && ！kmalloc_caches［2］ && i == 7）

kmalloc_caches［2］ = create_kmalloc_cache（NULL， 192， flags）;

}

???

}

2 緩存的創(chuàng)建與銷毀

2.1 緩存的創(chuàng)建

創(chuàng)建緩存通過接口kmem_cache_create進(jìn)行，在創(chuàng)建新的緩存以前，嘗試找到可以合并的緩存，合并條件包括對(duì)對(duì)象大小以及緩存屬性的判斷，如果可以合并則直接返回已存在的kmem_cache，并創(chuàng)建一個(gè)kobj鏈接指向同一個(gè)節(jié)點(diǎn)。

創(chuàng)建新的緩存主要是申請(qǐng)管理結(jié)構(gòu)暫用的空間，并初始化，這些管理結(jié)構(gòu)包括kmem_cache、kmem_cache_nodes、kmem_cache_cpu。同時(shí)在sysfs創(chuàng)建kobject節(jié)點(diǎn)。最后把kmem_cache加入到全局cahce鏈表slab_caches中。

2.2 緩存的銷毀

銷毀過程比創(chuàng)建過程簡單的多，主要工作是釋放partial隊(duì)列所有page，釋放kmem_cache_cpu，釋放每個(gè)node的kmem_cache_node，最后釋放kmem_cache本身。

3 申請(qǐng)對(duì)象

對(duì)象是SLUB分配器中可分配的內(nèi)存單元，與SLAB相比，SLUB對(duì)象的組織非常簡潔，申請(qǐng)過程更加高效。SLUB沒有任何管理區(qū)結(jié)構(gòu)來管理對(duì)象，而是將對(duì)象之間的關(guān)聯(lián)嵌入在對(duì)象本身的內(nèi)存中，因?yàn)樯暾?qǐng)者并不關(guān)心對(duì)象在分配之前內(nèi)存的內(nèi)容是什么。而且各個(gè)SLUB之間的關(guān)聯(lián)，也利用page自身結(jié)構(gòu)進(jìn)行處理。

每個(gè)CPU都有一個(gè)slab作為本地高速緩存，只要slab所在的node與申請(qǐng)者要求的node匹配，同時(shí)該slab還有空閑對(duì)象，則直接在cpu_slab中取出空閑對(duì)象，否則就進(jìn)入慢速路徑。

每個(gè)對(duì)象內(nèi)存的offset偏移位置都存放著下一個(gè)空閑對(duì)象，offset通常為0，也就是復(fù)用對(duì)象內(nèi)存的第一個(gè)字來保存下一個(gè)空閑對(duì)象的指針，當(dāng)滿足條件（flags & （SLAB_DESTROY_BY_RCU | SLAB_POISON）） 或者有對(duì)象構(gòu)造函數(shù)時(shí)，offset不為0，每個(gè)對(duì)象的結(jié)構(gòu)如下圖。

cpu_slab的freelist則保存著當(dāng)前第一個(gè)空閑對(duì)象的地址。

如果本地CPU緩存沒有空閑對(duì)象，則申請(qǐng)新的slab；如果有空閑對(duì)象，但是內(nèi)存node不相符，則deactive當(dāng)前cpu_slab，再申請(qǐng)新的slab。

deactivate_slab主要進(jìn)行兩步工作：

第一步，將cpu_slab的freelist全部釋放回page-》freelist；

第二部，根據(jù)page（slab）的狀態(tài)進(jìn)行不同操作，如果該slab有部分空閑對(duì)象，則將page移到kmem_cache_node的partial隊(duì)列；如果該slab全部空閑，則直接釋放該slab；如果該slab全部占用，而且開啟了CONFIG_SLUB_DEBUG編譯選項(xiàng)，則將page移到full隊(duì)列。

page的狀態(tài)也從frozen改變?yōu)閡nfrozen。（frozen代表slab在cpu_slub，unfroze代表在partial隊(duì)列或者full隊(duì)列）。

申請(qǐng)新的slab有兩種情況，如果cpu_slab的partial隊(duì)列不為空，則取出隊(duì)列中下一個(gè)page作為新的cpu_slab，同時(shí)再次檢測內(nèi)存node是否相符，還不相符則循環(huán)處理。

如果cpu_slab的partial隊(duì)列為空，則查看本node的partial隊(duì)列是否為空，如果不空，則取出page；如果為空，則看一定距離范圍內(nèi)其它node的partial隊(duì)列，如果還為空，則需要?jiǎng)?chuàng)建新slab。

創(chuàng)建新slab其實(shí)就是申請(qǐng)對(duì)應(yīng)order的內(nèi)存頁，用來放足夠數(shù)量的對(duì)象。值得注意的是其中order以及對(duì)象數(shù)量的確定，這兩者又是相互影響的。order和object數(shù)量同時(shí)存放在kmem_cache成員kmem_cache_order_objects中，低16位用于存放object數(shù)量，高位存放order。order與object數(shù)量的關(guān)系非常簡單：（（PAGE_SIZE 《《 order） - reserved） / size。

下面重點(diǎn)看calculate_order這個(gè)函數(shù)

static inline int calculate_order（int size， int reserved）

{

???

//嘗試找到order與object數(shù)量的最佳配合方案

//期望的效果就是剩余的碎片最小

min_objects = slub_min_objects;

if （！min_objects）

min_objects = 4 * （fls（nr_cpu_ids） + 1）;

max_objects = order_objects（slub_max_order， size， reserved）;

min_objects = min（min_objects， max_objects）;

//fraction是碎片因子，需要滿足的條件是碎片部分乘以fraction小于slab大小

// （slab_size - reserved） % size 《= slab_size / fraction

while （min_objects 》 1） {

fraction = 16;

while （fraction 》= 4） {

order = slab_order（size， min_objects，

slub_max_order， fraction， reserved）;

if （order 《= slub_max_order）

return order;

//放寬條件，容忍的碎片大小增倍

fraction /= 2;

}

min_objects--;

}

//嘗試一個(gè)slab只包含一個(gè)對(duì)象

order = slab_order（size， 1， slub_max_order， 1， reserved）;

if （order 《= slub_max_order）

return order;

//使用MAX_ORDER且一個(gè)slab只含一個(gè)對(duì)象

order = slab_order（size， 1， MAX_ORDER， 1， reserved）;

if （order 《 MAX_ORDER）

return order;

return -ENOSYS;

}

4 釋放對(duì)象

從上面申請(qǐng)對(duì)象的流程也可以看出，釋放的object有幾個(gè)去處：

1）cpu本地緩存slab，也就是cpu_slab；

2）放回object所在的page（也就是slab）中；另外要處理所在的slab：

2.1）如果放回之后，slab完全為空，則直接銷毀該slab；

2.2）如果放回之前，slab為滿，則判斷slab是否已被凍結(jié)；如果已凍結(jié)，則不需要做其他事；如果未凍結(jié)，則將其凍結(jié)，放入cpu_slab的partial隊(duì)列；如果cpu_slab partial隊(duì)列過多，則將隊(duì)列中所有slab一次性解凍到各自node的partial隊(duì)列中。

值得注意的是cpu partial隊(duì)列的功能是個(gè)可選項(xiàng)，依賴于內(nèi)核選項(xiàng)CONFIG_SLUB_CPU_PARTIAL，如果沒有開啟，則不使用cpu partial隊(duì)列，直接使用各個(gè)node的partial隊(duì)列。
編輯：hfy