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

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

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

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

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

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

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

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

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

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

1 SLUB分配器的初始化

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

1.1 申請kmem_cache的kmem_cache

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

void __init kmem_cache_init（void）

{

//聲明靜態(tài)變量，存儲臨時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;

//申請slub緩沖區(qū)，管理數(shù)據(jù)放在臨時結(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）;

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

kmem_cache = bootstrap（&boot_kmem_cache）;

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

kmem_cache_node = bootstrap（&boot_kmem_cache_node）;

???

}

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

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

void __init create_kmalloc_caches（unsigned long flags）

{

???

/*使用SLUB時KMALLOC_SHIFT_LOW=3，KMALLOC_SHIFT_HIGH=13

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

申請內(nèi)存是向上對其2的n次冪，創(chuàng)建對應(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

*/

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

保存在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進行，在創(chuàng)建新的緩存以前，嘗試找到可以合并的緩存，合并條件包括對對象大小以及緩存屬性的判斷，如果可以合并則直接返回已存在的kmem_cache，并創(chuàng)建一個kobj鏈接指向同一個節(jié)點。

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

2.2 緩存的銷毀

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

3 申請對象

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

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

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

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

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

deactivate_slab主要進行兩步工作：

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

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

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

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

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

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

下面重點看calculate_order這個函數(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--;

}

//嘗試一個slab只包含一個對象

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

if （order 《= slub_max_order）

return order;

//使用MAX_ORDER且一個slab只含一個對象

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

if （order 《 MAX_ORDER）

return order;

return -ENOSYS;

}

4 釋放對象

從上面申請對象的流程也可以看出，釋放的object有幾個去處：

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隊列；如果cpu_slab partial隊列過多，則將隊列中所有slab一次性解凍到各自node的partial隊列中。

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