Linux對象分配器 Slab 算法
本文轉載自微信公眾號「Linux內核那些事」，作者songsong001。轉載本文請聯系Linux內核那些事公眾號。
由于這篇文章寫得比較早, 當時使用的是Linux-2.4.16版本內核, 但不影響整體的源碼分析.
SLAB分配算法
上一節說過Linux內核使用伙伴系統算法來管理內存頁, 但伙伴系統算法分配的單位是內存頁, 就是至少要分配一個或以上的內存塊. 但很多時候我們并不需要分配一個內存頁, 例如我們要申請一個大小為200字節的結構體時, 如果使用伙伴系統分配算法至少申請一個內存頁, 但只使用了200字節的內存, 那么剩余的3896字節就被浪費掉了.
為了解決小塊內存申請的問題, Linux內核引入了 SLAB 分配算法. Linux 所使用的 SLAB 分配算法 的基礎是 Jeff Bonwick 為SunOS 操作系統首次引入的一種算法。在內核中，會為有限的對象集(例如文件描述符和其他常見結構)分配大量內存。Jeff發現對內核中普通對象進行初始化所需的時間超過了對其進行分配和釋放所需的時間。因此他的結論是不應該將內存釋放回一個全局的內存池，而是將內存保持為針對特定目而初始化的狀態。
為了更好的理解 SLAB分配算法, 我們先來介紹一下算法使用到的數據結構.
相關數據結構
SLAB分配算法 有兩個重要的數據結構, 一個是 kmem_cache_t，另外一個是 slab_t . 下面我們先來看看 kmem_cache_t 結構:
- struct kmem_cache_s {
- /* 1) each alloc & free */
- /* full, partial first, then free */
- struct list_head slabs_full;
- struct list_head slabs_partial;
- struct list_head slabs_free;
- unsigned int objsize;
- unsigned int flags; /* constant flags */
- unsigned int num; /* # of objs per slab */
- spinlock_t spinlock;
- #ifdef CONFIG_SMP
- unsigned int batchcount;
- #endif
- /* 2) slab additions /removals */
- /* order of pgs per slab (2^n) */
- unsigned int gfporder;
- /* force GFP flags, e.g. GFP_DMA */
- unsigned int gfpflags;
- size_t colour; /* cache colouring range */
- unsigned int colour_off; /* colour offset */
- unsigned int colour_next; /* cache colouring */
- kmem_cache_t *slabp_cache;
- unsigned int growing;
- unsigned int dflags; /* dynamic flags */
- /* constructor func */
- void (*ctor)(void *, kmem_cache_t *, unsigned long);
- /* de-constructor func */
- void (*dtor)(void *, kmem_cache_t *, unsigned long);
- unsigned long failures;
- /* 3) cache creation/removal */
- char name[CACHE_NAMELEN];
- struct list_head next;
- ...
- };
下面介紹一下kmem_cache_t結構中比較重要的字段：
- slab_full：完全分配的slab
- slab_partial：部分分配的slab
- slab_free：沒有被分配過的slab
- objsize：存儲的對象大小
- num：一個slab能夠存儲的對象個數
- gfporder：一個slab由2gfporder個內存頁組成
- colour/colour_off/colour_next：著色區大小(后面會講到)
slab_t結構定義如下：
- typedef struct slab_s {
- struct list_head list;
- unsigned long colouroff;
- void *s_mem; /* including colour offset */
- unsigned int inuse; /* num of objs active in slab */
- kmem_bufctl_t free;
- } slab_t;
slab_t結構各個字段的用途如下：
- list：連接(全滿/部分/全空)鏈
- colouroff：著色補償
- s_mem：存儲對象的起始內存地址
- inuse：已經分配多少個對象
- free：用于連接空閑的對象
用圖來表示它們之間的關系，如下：
SLAB分配算法初始化
SLAB分配算法的初始化由 kmem_cache_init() 函數完成，如下：
- void __init kmem_cache_init(void)
- {
- size_t left_over;
- init_MUTEX(&cache_chain_sem);
- INIT_LIST_HEAD(&cache_chain);
- kmem_cache_estimate(0, cache_cache.objsize, 0,
- &left_over, &cache_cache.num);
- if (!cache_cache.num)
- BUG();
- cache_cache.colour = left_over/cache_cache.colour_off;
- cache_cache.colour_next = 0;
- }
這個函數主要用來初始化 cache_cache 這個變量，cache_cache 是一個類型為 kmem_cache_t 的結構體變量，定義如下：
- static kmem_cache_t cache_cache = {
- slabs_full: LIST_HEAD_INIT(cache_cache.slabs_full),
- slabs_partial: LIST_HEAD_INIT(cache_cache.slabs_partial),
- slabs_free: LIST_HEAD_INIT(cache_cache.slabs_free),
- objsize: sizeof(kmem_cache_t),
- flags: SLAB_NO_REAP,
- spinlock: SPIN_LOCK_UNLOCKED,
- colour_off: L1_CACHE_BYTES,
- name: "kmem_cache",
- };
為什么需要一個這樣的對象呢?因為本身 kmem_cache_t 結構體也是小內存對象，所以也應該有slab分配器來分配的，但這樣就出現“雞蛋和雞誰先出現”的問題。在系統初始化的時候，slab分配器還沒有初始化，所以并不能使用slab分配器來分配一個 kmem_cache_t 對象，這時候只能通過定義一個 kmem_cache_t 類型的靜態變量來來管理slab分配器了，所以 cache_cache 靜態變量就是用來管理slab分配器的。
從上面的代碼可知，cache_cache 的 objsize字段 被設置為 sizeof(kmem_cache_t) 的大小，所以這個對象主要是用來分配不同類型的 kmem_cache_t 對象的。
kmem_cache_init() 函數調用了 kmem_cache_estimate() 函數來計算一個slab能夠保存多少個大小為 cache_cache.objsize 的對象，并保存到 cache_cache.num 字段中。一個slab中不可能全部都用來分配對象的，舉個例子：一個4096字節大小的slab用來分配大小為22字節的對象，可以劃分為186個，但還剩余4字節不能使用的，所以這部分內存用來作為著色區。著色區的作用是為了錯開不同的slab，讓CPU更有效的緩存slab。當然這屬于優化部分，對slab分配算法沒有多大的影響。就是說就算不對slab進行著色操作，slab分配算法還是可以工作起來的。
kmem_cache_t對象申請
kmem_cache_t 是用來管理和分配對象的，所以要使用slab分配器時，必須先申請一個 kmem_cache_t 對象，申請 kmem_cache_t 對象由 kmem_cache_create() 函數進行：
- kmem_cache_t *
- kmem_cache_create (const char *name, size_t size, size_t offset,
- unsigned long flags, void (*ctor)(void*, kmem_cache_t *, unsigned long),
- void (*dtor)(void*, kmem_cache_t *, unsigned long))
- {
- const char *func_nm = KERN_ERR "kmem_create: ";
- size_t left_over, align, slab_size;
- kmem_cache_t *cachep = NULL;
- ...
- cachep = (kmem_cache_t *) kmem_cache_alloc(&cache_cache, SLAB_KERNEL);
- if (!cachep)
- goto opps;
- memset(cachep, 0, sizeof(kmem_cache_t));
- ...
- do {
- unsigned int break_flag = 0;
- cal_wastage:
- kmem_cache_estimate(cachep->gfporder, size, flags,
- &left_over, &cachep->num);
- if (break_flag)
- break;
- if (cachep->gfporder >= MAX_GFP_ORDER)
- break;
- if (!cachep->num)
- goto next;
- if (flags & CFLGS_OFF_SLAB && cachep->num > offslab_limit) {
- cachep->gfporder--;
- break_flag++;
- goto cal_wastage;
- }
- if (cachep->gfporder >= slab_break_gfp_order)
- break;
- if ((left_over*8) <= (PAGE_SIZE<<cachep->gfporder))
- break; /* Acceptable internal fragmentation. */
- next:
- cachep->gfporder++;
- } while (1);
- if (!cachep->num) {
- printk("kmem_cache_create: couldn't create cache %s.\n", name);
- kmem_cache_free(&cache_cache, cachep);
- cachep = NULL;
- goto opps;
- }
- slab_size = L1_CACHE_ALIGN(cachep->num*sizeof(kmem_bufctl_t)+sizeof(slab_t));
- if (flags & CFLGS_OFF_SLAB && left_over >= slab_size) {
- flags &= ~CFLGS_OFF_SLAB;
- left_over -= slab_size;
- }
- offset += (align-1);
- offset &= ~(align-1);
- if (!offset)
- offset = L1_CACHE_BYTES;
- cachep->colour_off = offset;
- cachep->colour = left_over/offset;
- if (!cachep->gfporder && !(flags & CFLGS_OFF_SLAB))
- flags |= CFLGS_OPTIMIZE;
- cachep->flags = flags;
- cachep->gfpflags = 0;
- if (flags & SLAB_CACHE_DMA)
- cachep->gfpflags |= GFP_DMA;
- spin_lock_init(&cachep->spinlock);
- cachep->objsize = size;
- INIT_LIST_HEAD(&cachep->slabs_full);
- INIT_LIST_HEAD(&cachep->slabs_partial);
- INIT_LIST_HEAD(&cachep->slabs_free);
- if (flags & CFLGS_OFF_SLAB)
- cachep->slabp_cache = kmem_find_general_cachep(slab_size,0);
- cachep->ctor = ctor;
- cachep->dtor = dtor;
- strcpy(cachep->name, name);
- #ifdef CONFIG_SMP
- if (g_cpucache_up)
- enable_cpucache(cachep);
- #endif
- down(&cache_chain_sem);
- {
- struct list_head *p;
- list_for_each(p, &cache_chain) {
- kmem_cache_t *pc = list_entry(p, kmem_cache_t, next);
- if (!strcmp(pc->name, name))
- BUG();
- }
- }
- list_add(&cachep->next, &cache_chain);
- up(&cache_chain_sem);
- opps:
- return cachep;
- }
kmem_cache_create() 函數比較長，所以上面代碼去掉了一些不那么重要的地方，使代碼更清晰的體現其原理。
在 kmem_cache_create() 函數中，首先調用 kmem_cache_alloc() 函數申請一個 kmem_cache_t 對象，我們看到調用 kmem_cache_alloc() 時，傳入的就是 cache_cache 變量。申請完 kmem_cache_t對象 后需要對其進行初始化操作，主要是對 kmem_cache_t對象 的所有字段進行初始化：
- 計算需要多少個頁面來作為slab的大小。
- 計算一個slab能夠分配多少個對象。
- 計算著色區信息。
- 初始化 slab_full / slab_partial / slab_free 鏈表。
- 把申請的 kmem_cache_t對象 保存到 cache_chain 鏈表中。
對象分配
申請完 kmem_cache_t對象 后，就使用通過調用 kmem_cache_alloc() 函數來申請指定的對象。kmem_cache_alloc() 函數代碼如下：
- static inline void * kmem_cache_alloc_one_tail (kmem_cache_t *cachep, slab_t *slabp)
- {
- void *objp;
- ...
- slabp->inuse++;
- objp = slabp->s_mem + slabp->free*cachep->objsize;
- slabp->free=slab_bufctl(slabp)[slabp->free];
- if (unlikely(slabp->free == BUFCTL_END)) {
- list_del(&slabp->list);
- list_add(&slabp->list, &cachep->slabs_full);
- }
- return objp;
- }
- #define kmem_cache_alloc_one(cachep) \
- ({ \
- struct list_head * slabs_partial, * entry; \
- slab_t *slabp; \
- \
- slabs_partial = &(cachep)->slabs_partial; \
- entry = slabs_partial->next; \
- if (unlikely(entry == slabs_partial)) { \
- struct list_head * slabs_free; \
- slabs_free = &(cachep)->slabs_free; \
- entry = slabs_free->next; \
- if (unlikely(entry == slabs_free)) \
- goto alloc_new_slab; \
- list_del(entry); \
- list_add(entry, slabs_partial); \
- } \
- slabp = list_entry(entry, slab_t, list); \
- kmem_cache_alloc_one_tail(cachep, slabp); \
- })
- static inline void * __kmem_cache_alloc (kmem_cache_t *cachep, int flags)
- {
- unsigned long save_flags;
- void* objp;
- kmem_cache_alloc_head(cachep, flags);
- try_again:
- local_irq_save(save_flags);
- ...
- objp = kmem_cache_alloc_one(cachep);
- local_irq_restore(save_flags);
- return objp;
- alloc_new_slab:
- ...
- local_irq_restore(save_flags);
- if (kmem_cache_grow(cachep, flags))
- goto try_again;
- return NULL;
- }
- void * kmem_cache_alloc (kmem_cache_t *cachep, int flags)
- {
- return __kmem_cache_alloc(cachep, flags);
- }
kmem_cache_alloc() 函數被我展開之后如上代碼，kmem_cache_alloc() 函數的主要步驟是：
從kmem_cache_t對象 的 slab_partial 列表中查找是否有slab可用，如果有就直接從slab中分配一個對象。
如果 slab_partial 列表中沒有可用的slab，那么就從 slab_free 列表中查找可用的slab，如果有可用slab，就從slab分配一個對象，并且把此slab放置到 slab_partial 列表中。
如果 slab_free 列表中沒有可用的slab，那么就調用 kmem_cache_grow() 函數申請新的slab來進行對象的分配。kmem_cache_grow() 函數會調用 __get_free_pages() 函數來申請內存頁并且初始化slab.
一個slab的結構如下圖：
灰色部分是著色區，綠色部分是slab管理結構，黃色部分是空閑對象鏈表的索引，紅色部分是對象的實體。我們可以看到slab結構的s_mem字段指向了對象實體列表的起始地址。
分配對象的時候就是先通過slab結構的free字段查看是否有空閑的對象可用，free字段保存了空閑對象鏈表的首節點索引。
對象釋放
對象的釋放比較簡單，主要通過調用 kmem_cache_free() 函數完成，而 kmem_cache_free() 函數最終會調用 kmem_cache_free_one() 函數，代碼如下：
- static inline void kmem_cache_free_one(kmem_cache_t *cachep, void *objp)
- {
- slab_t* slabp;
- CHECK_PAGE(virt_to_page(objp));
- slabp = GET_PAGE_SLAB(virt_to_page(objp));
- {
- unsigned int objnr = (objp-slabp->s_mem)/cachep->objsize;
- slab_bufctl(slabp)[objnr] = slabp->free;
- slabp->free = objnr;
- }
- STATS_DEC_ACTIVE(cachep);
- {
- int inuse = slabp->inuse;
- if (unlikely(!--slabp->inuse)) {
- list_del(&slabp->list);
- list_add(&slabp->list, &cachep->slabs_free);
- } else if (unlikely(inuse == cachep->num)) {
- list_del(&slabp->list);
- list_add(&slabp->list, &cachep->slabs_partial);
- }
- }
- }
對象釋放的時候首先會把對象的索引添加到slab的空閑對象鏈表中，然后根據slab的使用情況移動slab到合適的列表中。
如果slab所有對象都被釋放完時，把slab放置到 slab_free 列表中。
如果對象所在的slab原來在 slab_full 中，那么就把slab移動到 slab_partial 中。
