SLAB分配算法

上一節(jié)說過Linux內核使用伙伴系統(tǒng)算法來管理內存頁, 但伙伴系統(tǒng)算法分配的單位是內存頁, 就是至少要分配一個或以上的內存塊. 但很多時候我們并不需要分配一個內存頁, 例如我們要申請一個大小為200字節(jié)的結構體時, 如果使用伙伴系統(tǒng)分配算法至少申請一個內存頁, 但只使用了200字節(jié)的內存, 那么剩余的3896字節(jié)就被浪費掉了.

為了解決小塊內存申請的問題, Linux內核引入了 SLAB 分配算法. Linux 所使用的 SLAB 分配算法 的基礎是 Jeff Bonwick 為SunOS 操作系統(tǒng)首次引入的一種算法。在內核中，會為有限的對象集（例如文件描述符和其他常見結構）分配大量內存。Jeff發(fā)現(xiàn)對內核中普通對象進行初始化所需的時間超過了對其進行分配和釋放所需的時間。因此他的結論是不應該將內存釋放回一個全局的內存池，而是將內存保持為針對特定目而初始化的狀態(tài)。

為了更好的理解 SLAB分配算法, 我們先來介紹一下算法使用到的數(shù)據結構.

SLAB分配算法初始化

SLAB分配算法的初始化由 kmem_cache_init() 函數(shù)完成，如下：

這個函數(shù)主要用來初始化 cache_cache 這個變量，cache_cache 是一個類型為 kmem_cache_t 的結構體變量，定義如下：

為什么需要一個這樣的對象呢？因為本身 kmem_cache_t 結構體也是小內存對象，所以也應該有slab分配器來分配的，但這樣就出現(xiàn)“雞蛋和雞誰先出現(xiàn)”的問題。在系統(tǒng)初始化的時候，slab分配器還沒有初始化，所以并不能使用slab分配器來分配一個 kmem_cache_t 對象，這時候只能通過定義一個 kmem_cache_t 類型的靜態(tài)變量來來管理slab分配器了，所以 cache_cache 靜態(tài)變量就是用來管理slab分配器的。

從上面的代碼可知，cache_cache 的 objsize字段 被設置為 sizeof(kmem_cache_t) 的大小，所以這個對象主要是用來分配不同類型的 kmem_cache_t 對象的。

kmem_cache_init() 函數(shù)調用了 kmem_cache_estimate() 函數(shù)來計算一個slab能夠保存多少個大小為 cache_cache.objsize 的對象，并保存到 cache_cache.num 字段中。一個slab中不可能全部都用來分配對象的，舉個例子：一個4096字節(jié)大小的slab用來分配大小為22字節(jié)的對象，可以劃分為186個，但還剩余4字節(jié)不能使用的，所以這部分內存用來作為著色區(qū)。著色區(qū)的作用是為了錯開不同的slab，讓CPU更有效的緩存slab。當然這屬于優(yōu)化部分，對slab分配算法沒有多大的影響。就是說就算不對slab進行著色操作，slab分配算法還是可以工作起來的。

【文章福利】小編推薦自己的Linux內核技術交流群:【891587639】整理了一些個人覺得比較好的學習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ??

kmem_cache_t對象申請

kmem_cache_t 是用來管理和分配對象的，所以要使用slab分配器時，必須先申請一個 kmem_cache_t 對象，申請 kmem_cache_t 對象由 kmem_cache_create() 函數(shù)進行：

kmem_cache_create() 函數(shù)比較長，所以上面代碼去掉了一些不那么重要的地方，使代碼更清晰的體現(xiàn)其原理。

在 kmem_cache_create() 函數(shù)中，首先調用 kmem_cache_alloc() 函數(shù)申請一個 kmem_cache_t 對象，我們看到調用 kmem_cache_alloc() 時，傳入的就是 cache_cache 變量。申請完 kmem_cache_t對象 后需要對其進行初始化操作，主要是對 kmem_cache_t對象 的所有字段進行初始化：

• 計算需要多少個頁面來作為slab的大小。

• 計算一個slab能夠分配多少個對象。

• 計算著色區(qū)信息。

• 初始化 slab_full / slab_partial / slab_free 鏈表。

• 把申請的 kmem_cache_t對象 保存到 cache_chain 鏈表中。

對象分配

申請完 kmem_cache_t對象 后，就使用通過調用 kmem_cache_alloc() 函數(shù)來申請指定的對象。kmem_cache_alloc() 函數(shù)代碼如下：

kmem_cache_alloc() 函數(shù)被我展開之后如上代碼，kmem_cache_alloc() 函數(shù)的主要步驟是：

• 從kmem_cache_t對象 的 slab_partial 列表中查找是否有slab可用，如果有就直接從slab中分配一個對象。

• 如果 slab_partial 列表中沒有可用的slab，那么就從 slab_free 列表中查找可用的slab，如果有可用slab，就從slab分配一個對象，并且把此slab放置到 slab_partial 列表中。

• 如果 slab_free 列表中沒有可用的slab，那么就調用 kmem_cache_grow() 函數(shù)申請新的slab來進行對象的分配。kmem_cache_grow() 函數(shù)會調用 __get_free_pages() 函數(shù)來申請內存頁并且初始化slab.

對象釋放

對象的釋放比較簡單，主要通過調用 kmem_cache_free() 函數(shù)完成，而 kmem_cache_free() 函數(shù)最終會調用 kmem_cache_free_one() 函數(shù)，代碼如下：

對象釋放的時候首先會把對象的索引添加到slab的空閑對象鏈表中，然后根據slab的使用情況移動slab到合適的列表中。

• 如果slab所有對象都被釋放完時，把slab放置到 slab_free 列表中。

• 如果對象所在的slab原來在 slab_full 中，那么就把slab移動到 slab_partial 中。