宋牧春： 多圖詳解Linux記憶體分配器slub

1. 前言

在Linux中，夥伴系統（buddy system）是以頁為單位管理和分配記憶體。但是現實的需求卻以位元組為單位，假如我們需要申請20Bytes，總不能分配一頁吧！那豈不是嚴重浪費記憶體。那麼該如何分配呢？slab分配器就應運而生了，專為小記憶體分配而生。slab分配器分配記憶體以Byte為單位。但是slab分配器並沒有脫離夥伴系統，而是基於夥伴系統分配的大記憶體進一步細分成小記憶體分配。

前段時間學習了下slab分配器工作原理。因為自己本身是做手機的，發現現在好像都在使用slub分配器，想想還是再研究一下slub的工作原理。之前看了程式碼，感覺挺多資料結構和成員的。成員的意思是什麼？資料結構之間的關係是什麼？不知道你是否感覺雲裡霧裡。既然程式碼閱讀起來晦澀難懂，如果有精美的配圖，不知是否有助於閣下理解slub的來龍去脈呢？我想表達的意思就是文章圖多，圖多，圖多。我們只說原理，儘量不看程式碼。因為所有程式碼中包含的內容我都會用圖來說明。你感興趣絕對有助於你看程式碼。

註：文章程式碼分析基於linux-4.15.0-rc3。

2. slub資料結構

slub的資料結構相對於slab來說要簡單很多。並且對外介面和slab相容。所以說，從slab的系統更換到slub，可以說是易如反掌。

2.1. kmem_cache

現在假如從夥伴系統分配一頁記憶體供slub分配器管理。對於slub分配器來說，就是將這段連續記憶體平均分成若干大小相等的object（物件）進行管理。可是我們總得知道每一個object的size吧！管理的記憶體頁數也是需要知道的吧！不然怎麼知道如何分配呢！因此需要一個資料結構管理。那就是structkmem_cache。kmem_cache資料結構描述如下：

• cpu_slab：一個per cpu變數，對於每個cpu來說，相當於一個本地記憶體快取池。當分配記憶體的時候優先從本地cpu分配記憶體以保證cache的命中率。

• flags：object分配掩碼，例如經常使用的SLAB_HWCACHE_ALIGN標誌位，代表建立的kmem_cache管理的object按照硬體cache 對齊，一切都是為了速度。

• min_partial：限制struct kmem_cache_node中的partial連結串列slab的數量。雖說是mini_partial，但是程式碼的本意告訴我這個變數是kmem_cache_node中partial連結串列最大slab數量，如果大於這個mini_partial的值，那麼多餘的slab就會被釋放。

• size：分配的object size

• object_size：實際的object size，就是建立kmem_cache時候傳遞進來的引數。和size的關係就是，size是各種地址對齊之後的大小。因此，size要大於等於object_size。

• offset：slub分配在管理object的時候採用的方法是：既然每個object在沒有分配之前不在乎每個object中儲存的內容，那麼完全可以在每個object中儲存下一個object記憶體首地址，就形成了一個單連結串列。很巧妙的設計。那麼這個地址資料儲存在object什麼位置呢？offset就是儲存下個object地址資料相對於這個object首地址的偏移。

• cpu_partial：per cpu partial中所有slab的free object的數量的最大值，超過這個值就會將所有的slab轉移到kmem_cache_node的partial連結串列。

• oo：低16位代表一個slab中所有object的數量（oo &((1 << 16) - 1)），高16位代表一個slab管理的page數量（(2^(oo  16)) pages）。

• max：看了程式碼好像就是等於oo。

• min：當按照oo大小分配記憶體的時候出現記憶體不足就會考慮min大小方式分配。min只需要可以容納一個object即可。

• allocflags：從夥伴系統分配記憶體掩碼。

• inuse：object_size按照word對齊之後的大小。

• align：位元組對齊大小。

• name：sysfs檔案系統顯示使用。

• list：系統有一個slab_caches連結串列，所有的slab都會掛入此連結串列。

• node：slab節點。在NUMA系統中，每個node都有一個struct kmem_cache_node資料結構。

2.2. kmem_cache_cpu

struct kmem_cache_cpu是對本地記憶體快取池的描述，每一個cpu對應一個結構體。其資料結構如下：

• freelist：指向下一個可用的object。

• tid：一個神奇的數字，主要用來同步作用的。

• page：slab記憶體的page指標。

• partial：本地slab partial連結串列。主要是一些部分使用object的slab。

2.3. kmem_cache_node

slab節點使用structkmem_cache_node結構體描述。對於slub分配器來說，成員很少，遠比slab分配器簡潔。

• list_lock：自旋鎖，保護資料。

• nr_partial：slab節點中slab的數量。

• partial：slab節點的slab partial連結串列，和structkmem_cache_cpu的partial鏈表功能類似。

2.4. slub介面

瞭解了基本的資料結構，再來看看slub提供的API。如果你瞭解slub，我想這幾個介面你是再熟悉不過了。

1)kmem_cache_create是建立kmem_cache資料結構，引數描述如下：

    name：kmem_cache的名稱

    size ：slab管理物件的大小

    align：slab分配器分配記憶體的對齊位元組數(以align位元組對齊)

    flags：分配記憶體掩碼

    ctor ：分配物件的構造回呼函式

2)kmem_cache_destroy作用和kmem_cache_create相反，就是銷毀建立的kmem_cache。

3)kmem_cache_alloc是從cachep引數指定的kmem_cache管理的記憶體快取池中分配一個物件，其中flags是分配掩碼，GFP_KERNEL是不是很熟悉的掩碼？

4)kmem_cache_free是kmem_cache_alloc的反操作

slab分配器提供的介面該如何使用呢？其實很簡單，總結分成以下幾個步驟：

1)kmem_cache_create建立一個kmem_cache資料結構。

2) 使用kmem_cache_alloc介面分配記憶體，kmem_cache_free介面釋放記憶體。

3) release第一步建立的kmem_cache資料結構。

再來一段demo示例程式碼就更好了。

1) 首先使用kmem_cache_create建立名稱為kmem_cache_16的kmem_cache，該kmem_cache主要是描述如何管理一堆物件，其實就是slab的佈局。每個物件都是16位元組，並且分配的物件地址按照8位元組對齊，也就是說從kmem_cache_16中分配的物件大小全是16位元組。不管你要申請多少，反正就是16Bytes。當然，kmem_cache_create僅僅是建立了一個描述slab快取池佈局的資料結構，並沒有從夥伴系統申請記憶體，具體的申請記憶體操作是在kmeme_cache_alloc中完成的。

2)kmeme_cache_alloc從kmem_cache_16分配一個物件。

3) 記憶體使用結束記得kmem_cache_free釋放。

4) 如果不需要這個kmem_cache的話，就可以呼叫kmem_cache_destroy進行銷毀吧。在釋放kmem_cache之前要保證從該kmem_cache中分配的物件全部釋放了，否則無法釋放kmem_cache。

3. slub資料結構之間關係

什麼是slab快取池呢？我的解釋是使用struct kmem_cache結構描述的一段記憶體就稱作一個slab快取池。一個slab快取池就像是一箱牛奶，一箱牛奶中有很多瓶牛奶，每瓶牛奶就是一個object。分配記憶體的時候，就相當於從牛奶箱中拿一瓶。總有拿完的一天。當箱子空的時候，你就需要去超市再買一箱回來。超市就相當於partial連結串列，超市儲存著很多箱牛奶。如果超市也賣完了，自然就要從廠家進貨，然後出售給你。廠家就相當於夥伴系統。

說了這麼多終於要丟擲辛辛苦苦畫的美圖了。

好了，後面說的大部分內容請看這張圖。足以表明資料結構之間的關係了。看懂了這張圖，就可以理清資料結構之間的關係了。

3.1. slub管理object方法

在圖片的左上角就是一個slub快取池中object的分佈以及資料結構和kmem_cache之間的關係。首先一個slab快取池包含的頁數是由oo決定的。oo拆分為兩部分，低16位代表一個slab快取池中object的數量，高16位代表包含的頁數。使用kmem_cache_create()介面建立kmem_cache的時候需要指出obj的size和對齊align。也就是傳入的引數。kmem_cache_create()主要是就是填充kmem_cache結構體成員。既然從夥伴系統得到(2^(oo>> 16)) pages大小記憶體，按照size大小進行平分。一般來說都不會整除，因此剩下的就是圖中灰色所示。由於每一個object的大小至少8位元組，當然可以用來儲存下一個object的首地址。就像圖中所示的，形成單連結串列。圖中所示下個obj地址存放的位置位於每個obj首地址處，在核心中稱作指標內建式。同時，下個obj地址存放的位置和obj首地址之間的偏移儲存在kmem_cache的offset成員。兩外一種方式是指標外接式，即下個obj的首地址儲存的位置位於obj尾部，也就是在obj尾部再分配sizeof(void*)位元組大小的記憶體。對於外接式則offset就等於kmem_cache的inuse成員。

3.2. per cpu freelist

針對每一個cpu都會分配一個struct kmem_cacche_cpu的結構體。可以稱作是本地快取池。當記憶體申請的時候，優先從本地cpu快取池申請。在分配初期，本地快取池為空，自然要從夥伴系統分配一定頁數的記憶體。核心會為每一個物理頁幀建立一個struct page的結構體。kmem_cacche_cpu中page就會指向正在使用的slab的頁幀。freelist成員指向第一個可用記憶體obj首地址。處於正在使用的slab的struct page結構體中的freelist會置成NULL，因為沒有其他地方使用。struct page結構體中inuse代表已經使用的obj數量。這地方有個很有意思的地方，在剛從夥伴系統分配的slab的 inuse在分配初期就置成obj的總數，在分配obj的時候並不會改變。你是不是覺得很奇怪，既然表示已經使用obj的數量，為什麼一直是obj的總數呢？你想想，slab中的物件總有分配完的時候，那個時候就直接脫離kmem_cache_cpu了。此時的inuse不就名副其實了嘛！對於full slab就像圖的右下角，就像無人看管的孩子，沒有任何連結串列來管理。

3.3. per cpu partial

當圖中右下角full slab釋放obj的時候，首先就會將slab掛入per cpu partial連結串列管理。透過struct page中next成員形成單連結串列。per cpu partial連結串列指向的第一個page中會存放一些特殊的資料。例如：pobjects儲存著per cpu partial連結串列中所有slab可供分配obj的總數，如圖所示。當然還有一個圖中沒有體現的pages成員儲存per cpu partial連結串列中所有slab記憶體的頁數。pobjects到底有什麼用呢？我們從fullslab中釋放一個obj就新增到per cpu partial連結串列，總不能無限制的新增吧！因此，每次新增的時候都會判斷當前的pobjects是否大於kmem_cache的cpu_partial成員，如果大於，那麼就會將此時per cpu partial連結串列中所有的slab移送到kmem_cache_node的partial連結串列，然後再將剛剛釋放obj的slab插入到per cpu partial連結串列。如果不大於，則更新pobjects和pages成員，並將slab插入到per cpu partial連結串列。

3.4. per node partial

per node partia連結串列類似per cpu partial，區別是node中的slab是所有cpu共享的，而per cpu是每個cpu獨佔的。假如現在的slab佈局如上圖所示。假如現在如紅色箭頭指向的obj將會釋放，那麼就是一個empty slab，此時判斷kmem_cache_node的nr_partial是否大於kmem_cache的min_partial，如果大於則會釋放該slab的記憶體。

4. slub分配記憶體原理

當呼叫kmem_cache_alloc()分配記憶體的時候，我們可以從正在使用slab分配，也可以從percpu partial分配，同樣還可以從pernode partial分配，那麼分配的順序是什麼呢？我們可以用下圖表示。

首先從cpu 本地快取池分配，如果freelist不存在，就會轉向per cpu partial分配，如果per cpu partial也沒有可用物件，繼續檢視per node partial，如果很不幸也不沒有可用物件的話，就只能從夥伴系統分配一個slab了，並掛入per cpu freelist。我們詳細看一下這幾種情況。

1) kmem_cache剛剛建立，還沒有任何物件可供分配，此時只能從夥伴系統分配一個slab，如下圖所示。

2)如果正在使用的slab有free obj，那麼就直接分配即可，這種是最簡單快捷的。如下圖所示。

3)隨著正在使用的slab中obj的一個個分配出去，最終會無obj可分配，此時per cpupartial連結串列中有可用slab用於分配，那麼就會從percpu partial連結串列中取下一個slab用於分配obj。如下圖所示。

4)隨著正在使用的slab中obj的一個個分配出去，最終會無obj可分配，此時per cpupartial連結串列也為空，此時發現per node partial連結串列中有可用slab用於分配，那麼就會從per node partial連結串列中取下一個slab用於分配obj。如下圖所示。

5. slub釋放記憶體原理

我們可以透過kmem_cache_free()介面釋放申請的obj物件。釋放物件的流程如下圖所示。

如果釋放的obj就是屬於正在使用cpu上的slab，那麼直接釋放即可，非常簡單；如果不是的話，首先判斷所屬slub是不是full狀態，因為full slab是沒媽的孩子，釋放之後就變成partial empty，急需要找個連結串列領養啊！這個媽就是per cpu partial連結串列。如果per cpu partial連結串列管理的所有slab的free object數量超過kmem_cache的cpu_partial成員的話，就需要將per cpu partial連結串列管理的所有slab移動到per node partial連結串列管理；如果不是full slab的話，繼續判斷釋放當前obj後的slab是否是empty slab，如果是empty slab，那麼在滿足kmem_cache_node的nr_partial大於kmem_cache的min_partial的情況下，則會釋放該slab的記憶體。其他情況就直接釋放即可。

1)假設下圖左邊的情況下釋放obj，如果滿足kmem_cache_node的nr_partial大於kmem_cache的min_partial的話，釋放情況如下圖所示。

2) 假設下圖左邊的情況下釋放obj，如果不滿足kmem_cache_node的nr_partial大於kmem_cache的min_partial的話，釋放情況如下圖所示。

3) 假設下圖從full slab釋放obj的話，如果滿足per cpu partial管理的所有slab的free object數量大於kmem_cache的cpu_partial成員的話的話，將per cpu partial連結串列管理的所有slab移動到per node partial連結串列管理，釋放情況如下圖所示。

4)假設下圖從full slab釋放obj的話，如果不滿足per cpu partial管理的所有slab的free object數量大於kmem_cache的cpu_partial成員的話的話，釋放情況如下圖所示。

6. kmalloc

好了，說了這麼多，估計你會感覺slab好像跟我們沒什麼關係。如果作為一個驅動開發者，是不是感覺自己寫的driver從來沒有使用過這些介面呢？其實我們經常使用，只不過隱藏在kmalloc的面具之下。

kmalloc的記憶體分配就是基於slab分配器，在系統啟動初期呼叫create_kmalloc_caches()建立多個管理不同大小物件的kmem_cache，例如：8B、16B、32B、64B、…、64MB等大小。kmem_cache的名稱以及大小使用structkmalloc_info_struct管理。所有管理不同大小物件的kmem_cache的名稱如下：

經過create_kmalloc_caches()函式之後，系統透過create_kmalloc_cache()建立以上不同size的kmem_cache，並將這些kmem_cache儲存在kmalloc_caches全域性變數中以備後續kmalloc分配記憶體。現在假如透過kmalloc(17, GFP_KERNEL)申請記憶體，系統會從名稱“kmalloc-32”管理的slab快取池中分配一個物件。即使浪費了15Byte。

我們來看看kmalloc的實現方式。

• __builtin_constant_p是gcc工具用來判斷引數是否是一個常數，畢竟有些操作對於常數來說是可以最佳化的。

• 透過kmalloc_index函式查詢符合滿足分配大小的最小kmem_cache。

• 將index作為下表從kmalloc_caches陣列中找到符合的kmem_cache，並從slab快取池中分配物件。

我們再看一下kmalloc_index的實現。