作者簡介：

宋牧春，linux內核愛好者，2017年6月本科畢業于江蘇大學。現就職于一家手機研發公司，任職BSP驅動工程師，主要負責TP驅動bringup和調試。

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數據結構描述如下：

struct kmem_cache {

struct kmem_cache_cpu __percpu *cpu_slab;

/* Used for retriving partial slabs etc */

slab_flags_t flags;

unsigned long min_partial;

int size;???????????? /* The size of an object including meta data */

int object_size;???? /* The size of an object without meta data */

int offset;?????????? /* Free pointer offset. */

#ifdef CONFIG_SLUB_CPU_PARTIAL

int cpu_partial;????? /* Number of per cpu partial objects to keep around */

#endif

struct kmem_cache_order_objects oo;

/* Allocation and freeing of slabs */

struct kmem_cache_order_objects max;

struct kmem_cache_order_objects min;

gfp_t allocflags;??? /* gfp flags to use on each alloc */

int refcount;?????? ??/* Refcount for slab cache destroy */

void (*ctor)(void *);

int inuse;?????????? ?/* Offset to metadata */

int align;?????????? ?/* Alignment */

int reserved;??????? ?/* Reserved bytes at the end of slabs */

const char *name;??? /* Name (only for display!) */

struct list_head list;? /* List of slab caches */

struct kmem_cache_node *node[MAX_NUMNODES];

};

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對應一個結構體。其數據結構如下：

struct kmem_cache_cpu {

void **freelist;??? /* Pointer to next available object */

unsigned long tid;? /* Globally unique transaction id */

struct page *page;? /* The slab from which we are allocating */

#ifdef CONFIG_SLUB_CPU_PARTIAL

struct page *partial;?? /* Partially allocated frozen slabs */

#endif

};

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

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

page：slab內存的page指針。

partial：本地slab partial鏈表。主要是一些部分使用object的slab。

2.3. kmem_cache_node

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

struct kmem_cache_node {

spinlock_t list_lock;

unsigned long nr_partial;

struct list_head partial;

};

list_lock：自旋鎖，保護數據。

nr_partial：slab節點中slab的數量。

partial：slab節點的slab partial鏈表，和structkmem_cache_cpu的partial鏈表功能類似。

2.4. slub接口

了解了基本的數據結構，再來看看slub提供的API。如果你了解slub，我想這幾個接口你是再熟悉不過了。

struct kmem_cache *kmem_cache_create(const char *name,

size_t size,

size_t align,

unsigned long flags,

void (*ctor)(void *));

void kmem_cache_destroy(struct kmem_cache *);

void *kmem_cache_alloc(struct kmem_cache *cachep, int flags);

void kmem_cache_free(struct kmem_cache *cachep, void *objp);

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示例代碼就更好了。

/*

*　This is a demo for how to use kmem_cache_create

*/

void slab_demo(void)

{

struct kmem_cache *kmem_cache_16 = kmem_cache_create("kmem_cache_16", 16,

8, ARCH_KMALLOC_FLAGS,

NULL);

/* now you can alloc memory, the buf points to 16 bytes of memory*/

char *buf = kmeme_cache_alloc(kmem_cache_16, GFP_KERNEL);

/*

* do something what you what, don't forget to release the memory after use

*/

kmem_cache_free(kmem_cache_16, buf);

kmem_cache_destroy(kmem_cache_16);

}

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的名稱如下：

const struct kmalloc_info_struct kmalloc_info[] __initconst = {

{NULL,????????????????? ??????0},???? {"kmalloc-96",???????????? 96},

{"kmalloc-192",?????????? 192},???? {"kmalloc-8",?????????????? 8},

{"kmalloc-16",???????????? 16},???? {"kmalloc-32",???????????? 32},

{"kmalloc-64",???????????? 64},?? ??{"kmalloc-128",?????????? 128},

{"kmalloc-256",?????????? 256},???? {"kmalloc-512",?????????? 512},

{"kmalloc-1024",???????? 1024},???? {"kmalloc-2048",???????? 2048},

{"kmalloc-4096",???????? 4096},???? {"kmalloc-8192",???????? 8192},

{"kmalloc-16384",?????? 16384},???? {"kmalloc-32768",?????? 32768},

{"kmalloc-65536",?????? 65536},???? {"kmalloc-131072",???? 131072},

{"kmalloc-262144",???? 262144},???? {"kmalloc-524288",???? 524288},

{"kmalloc-1048576",?? 1048576},???? {"kmalloc-2097152",?? 2097152},

{"kmalloc-4194304",?? 4194304},???? {"kmalloc-8388608",?? 8388608},

{"kmalloc-16777216", 16777216},???? {"kmalloc-33554432", 33554432},

{"kmalloc-67108864", 67108864}

};

經過create_kmalloc_caches()函數之后，系統通過create_kmalloc_cache()創建以上不同size的kmem_cache，并將這些kmem_cache存儲在kmalloc_caches全局變量中以備后續kmalloc分配內存。現在假如通過kmalloc(17, GFP_KERNEL)申請內存，系統會從名稱“kmalloc-32”管理的slab緩存池中分配一個對象。即使浪費了15Byte。

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

static __always_inline void *kmalloc(size_t size, gfp_t flags)

{

if (__builtin_constant_p(size)) {

if (size > KMALLOC_MAX_CACHE_SIZE)

return kmalloc_large(size, flags);

if (!(flags & GFP_DMA)) {

int index = kmalloc_index(size);

if (!index)

return ZERO_SIZE_PTR;

return kmem_cache_alloc_trace(kmalloc_caches[index], flags, size);

}

}

return __kmalloc(size, flags);

}

__builtin_constant_p是gcc工具用來判斷參數是否是一個常數，畢竟有些操作對于常數來說是可以優化的。

通過kmalloc_index函數查找符合滿足分配大小的最小kmem_cache。

將index作為下表從kmalloc_caches數組中找到符合的kmem_cache，并從slab緩存池中分配對象。

我們再看一下kmalloc_index的實現。

static __always_inline int kmalloc_index(size_t size)

{

if (!size)

return 0;

if (size <= KMALLOC_MIN_SIZE)

return KMALLOC_SHIFT_LOW;

if (KMALLOC_MIN_SIZE <= 32 && size > 64 && size <= 96)

return 1;

if (KMALLOC_MIN_SIZE <= 64 && size > 128 && size <= 192)

return 2;

if (size <=????????? 8) return 3;

if (size <=???????? 16) return 4;

if (size <=???????? 32) return 5;

if (size <=???????? 64) return 6;

if (size <=??????? 128) return 7;

if (size <=??????? 256) return 8;

if (size <=??????? 512) return 9;

if (size <=?????? 1024) return 10;

if (size <=?? 2 * 1024) return 11;

if (size <=?? 4 * 1024) return 12;

if (size <=?? 8 * 1024) return 13;

if (size <=? 16 * 1024) return 14;

if (size <=? 32 * 1024) return 15;

if (size <=? 64 * 1024) return 16;

if (size <= 128 * 1024) return 17;

if (size <= 256 * 1024) return 18;

if (size <= 512 * 1024) return 19;

if (size <= 1024 * 1024) return 20;

if (size <=? 2 * 1024 * 1024) return 21;

if (size <=? 4 * 1024 * 1024) return 22;

if (size <=? 8 * 1024 * 1024) return 23;

if (size <=? 16 * 1024 * 1024) return 24;

if (size <=? 32 * 1024 * 1024) return 25;

if (size <=? 64 * 1024 * 1024) return 26;

/* Will never be reached. Needed because the compiler may complain */

return -1;

}

編輯：黃飛