Linux對(duì)象分配器 Slab 算法
本文轉(zhuǎn)載自微信公眾號(hào)「Linux內(nèi)核那些事」，作者songsong001。轉(zhuǎn)載本文請(qǐng)聯(lián)系Linux內(nèi)核那些事公眾號(hào)。
由于這篇文章寫得比較早, 當(dāng)時(shí)使用的是Linux-2.4.16版本內(nèi)核, 但不影響整體的源碼分析.
SLAB分配算法
上一節(jié)說(shuō)過(guò)Linux內(nèi)核使用伙伴系統(tǒng)算法來(lái)管理內(nèi)存頁(yè), 但伙伴系統(tǒng)算法分配的單位是內(nèi)存頁(yè), 就是至少要分配一個(gè)或以上的內(nèi)存塊. 但很多時(shí)候我們并不需要分配一個(gè)內(nèi)存頁(yè), 例如我們要申請(qǐng)一個(gè)大小為200字節(jié)的結(jié)構(gòu)體時(shí), 如果使用伙伴系統(tǒng)分配算法至少申請(qǐng)一個(gè)內(nèi)存頁(yè), 但只使用了200字節(jié)的內(nèi)存, 那么剩余的3896字節(jié)就被浪費(fèi)掉了.
為了解決小塊內(nèi)存申請(qǐng)的問(wèn)題, Linux內(nèi)核引入了 SLAB 分配算法. Linux 所使用的 SLAB 分配算法 的基礎(chǔ)是 Jeff Bonwick 為SunOS 操作系統(tǒng)首次引入的一種算法。在內(nèi)核中，會(huì)為有限的對(duì)象集(例如文件描述符和其他常見(jiàn)結(jié)構(gòu))分配大量?jī)?nèi)存。Jeff發(fā)現(xiàn)對(duì)內(nèi)核中普通對(duì)象進(jìn)行初始化所需的時(shí)間超過(guò)了對(duì)其進(jìn)行分配和釋放所需的時(shí)間。因此他的結(jié)論是不應(yīng)該將內(nèi)存釋放回一個(gè)全局的內(nèi)存池，而是將內(nèi)存保持為針對(duì)特定目而初始化的狀態(tài)。
為了更好的理解 SLAB分配算法, 我們先來(lái)介紹一下算法使用到的數(shù)據(jù)結(jié)構(gòu).
相關(guān)數(shù)據(jù)結(jié)構(gòu)
SLAB分配算法 有兩個(gè)重要的數(shù)據(jù)結(jié)構(gòu), 一個(gè)是 kmem_cache_t，另外一個(gè)是 slab_t . 下面我們先來(lái)看看 kmem_cache_t 結(jié)構(gòu):
- 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結(jié)構(gòu)中比較重要的字段：
- slab_full：完全分配的slab
- slab_partial：部分分配的slab
- slab_free：沒(méi)有被分配過(guò)的slab
- objsize：存儲(chǔ)的對(duì)象大小
- num：一個(gè)slab能夠存儲(chǔ)的對(duì)象個(gè)數(shù)
- gfporder：一個(gè)slab由2gfporder個(gè)內(nèi)存頁(yè)組成
- colour/colour_off/colour_next：著色區(qū)大小(后面會(huì)講到)
slab_t結(jié)構(gòu)定義如下：
- 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結(jié)構(gòu)各個(gè)字段的用途如下：
- list：連接(全滿/部分/全空)鏈
- colouroff：著色補(bǔ)償
- s_mem：存儲(chǔ)對(duì)象的起始內(nèi)存地址
- inuse：已經(jīng)分配多少個(gè)對(duì)象
- free：用于連接空閑的對(duì)象
用圖來(lái)表示它們之間的關(guān)系，如下：
SLAB分配算法初始化
SLAB分配算法的初始化由 kmem_cache_init() 函數(shù)完成，如下：
- 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;
- }
這個(gè)函數(shù)主要用來(lái)初始化 cache_cache 這個(gè)變量，cache_cache 是一個(gè)類型為 kmem_cache_t 的結(jié)構(gòu)體變量，定義如下：
- 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",
- };
為什么需要一個(gè)這樣的對(duì)象呢?因?yàn)楸旧?kmem_cache_t 結(jié)構(gòu)體也是小內(nèi)存對(duì)象，所以也應(yīng)該有slab分配器來(lái)分配的，但這樣就出現(xiàn)“雞蛋和雞誰(shuí)先出現(xiàn)”的問(wèn)題。在系統(tǒng)初始化的時(shí)候，slab分配器還沒(méi)有初始化，所以并不能使用slab分配器來(lái)分配一個(gè) kmem_cache_t 對(duì)象，這時(shí)候只能通過(guò)定義一個(gè) kmem_cache_t 類型的靜態(tài)變量來(lái)來(lái)管理slab分配器了，所以 cache_cache 靜態(tài)變量就是用來(lái)管理slab分配器的。
從上面的代碼可知，cache_cache 的 objsize字段 被設(shè)置為 sizeof(kmem_cache_t) 的大小，所以這個(gè)對(duì)象主要是用來(lái)分配不同類型的 kmem_cache_t 對(duì)象的。
kmem_cache_init() 函數(shù)調(diào)用了 kmem_cache_estimate() 函數(shù)來(lái)計(jì)算一個(gè)slab能夠保存多少個(gè)大小為 cache_cache.objsize 的對(duì)象，并保存到 cache_cache.num 字段中。一個(gè)slab中不可能全部都用來(lái)分配對(duì)象的，舉個(gè)例子：一個(gè)4096字節(jié)大小的slab用來(lái)分配大小為22字節(jié)的對(duì)象，可以劃分為186個(gè)，但還剩余4字節(jié)不能使用的，所以這部分內(nèi)存用來(lái)作為著色區(qū)。著色區(qū)的作用是為了錯(cuò)開(kāi)不同的slab，讓CPU更有效的緩存slab。當(dāng)然這屬于優(yōu)化部分，對(duì)slab分配算法沒(méi)有多大的影響。就是說(shuō)就算不對(duì)slab進(jìn)行著色操作，slab分配算法還是可以工作起來(lái)的。
kmem_cache_t對(duì)象申請(qǐng)
kmem_cache_t 是用來(lái)管理和分配對(duì)象的，所以要使用slab分配器時(shí)，必須先申請(qǐng)一個(gè) kmem_cache_t 對(duì)象，申請(qǐng) kmem_cache_t 對(duì)象由 kmem_cache_create() 函數(shù)進(jìn)行：
- 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() 函數(shù)比較長(zhǎng)，所以上面代碼去掉了一些不那么重要的地方，使代碼更清晰的體現(xiàn)其原理。
在 kmem_cache_create() 函數(shù)中，首先調(diào)用 kmem_cache_alloc() 函數(shù)申請(qǐng)一個(gè) kmem_cache_t 對(duì)象，我們看到調(diào)用 kmem_cache_alloc() 時(shí)，傳入的就是 cache_cache 變量。申請(qǐng)完 kmem_cache_t對(duì)象 后需要對(duì)其進(jìn)行初始化操作，主要是對(duì) kmem_cache_t對(duì)象 的所有字段進(jìn)行初始化：
- 計(jì)算需要多少個(gè)頁(yè)面來(lái)作為slab的大小。
- 計(jì)算一個(gè)slab能夠分配多少個(gè)對(duì)象。
- 計(jì)算著色區(qū)信息。
- 初始化 slab_full / slab_partial / slab_free 鏈表。
- 把申請(qǐng)的 kmem_cache_t對(duì)象 保存到 cache_chain 鏈表中。
對(duì)象分配
申請(qǐng)完 kmem_cache_t對(duì)象 后，就使用通過(guò)調(diào)用 kmem_cache_alloc() 函數(shù)來(lái)申請(qǐng)指定的對(duì)象。kmem_cache_alloc() 函數(shù)代碼如下：
- 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() 函數(shù)被我展開(kāi)之后如上代碼，kmem_cache_alloc() 函數(shù)的主要步驟是：
從kmem_cache_t對(duì)象 的 slab_partial 列表中查找是否有slab可用，如果有就直接從slab中分配一個(gè)對(duì)象。
如果 slab_partial 列表中沒(méi)有可用的slab，那么就從 slab_free 列表中查找可用的slab，如果有可用slab，就從slab分配一個(gè)對(duì)象，并且把此slab放置到 slab_partial 列表中。
如果 slab_free 列表中沒(méi)有可用的slab，那么就調(diào)用 kmem_cache_grow() 函數(shù)申請(qǐng)新的slab來(lái)進(jìn)行對(duì)象的分配。kmem_cache_grow() 函數(shù)會(huì)調(diào)用 __get_free_pages() 函數(shù)來(lái)申請(qǐng)內(nèi)存頁(yè)并且初始化slab.
一個(gè)slab的結(jié)構(gòu)如下圖：
灰色部分是著色區(qū)，綠色部分是slab管理結(jié)構(gòu)，黃色部分是空閑對(duì)象鏈表的索引，紅色部分是對(duì)象的實(shí)體。我們可以看到slab結(jié)構(gòu)的s_mem字段指向了對(duì)象實(shí)體列表的起始地址。
分配對(duì)象的時(shí)候就是先通過(guò)slab結(jié)構(gòu)的free字段查看是否有空閑的對(duì)象可用，free字段保存了空閑對(duì)象鏈表的首節(jié)點(diǎn)索引。
對(duì)象釋放
對(duì)象的釋放比較簡(jiǎn)單，主要通過(guò)調(diào)用 kmem_cache_free() 函數(shù)完成，而 kmem_cache_free() 函數(shù)最終會(huì)調(diào)用 kmem_cache_free_one() 函數(shù)，代碼如下：
- 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);
- }
- }
- }
對(duì)象釋放的時(shí)候首先會(huì)把對(duì)象的索引添加到slab的空閑對(duì)象鏈表中，然后根據(jù)slab的使用情況移動(dòng)slab到合適的列表中。
如果slab所有對(duì)象都被釋放完時(shí)，把slab放置到 slab_free 列表中。
如果對(duì)象所在的slab原來(lái)在 slab_full 中，那么就把slab移動(dòng)到 slab_partial 中。
