>>> 此貼的回復 >> slab 管理
slab分配器在內存分配中起的作用
slab分配器通過頁面級分配器獲得頁塊後，做進一步的精細分配, 將這個頁塊分割成一個個的對象，有點類似c中的malloc c, mfree的作用。
cache描述符
struct kmem_cache_s { /* 1) each alloc & free */ /* full, partial first, then free */ struct list_head slabs; struct list_head *firstnotfull; 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; #ifdef CONFIG_SMP /* 4) per-cpu data */ cpucache_t *cpudata[NR_CPUS]; #endif #if STATS unsigned long num_active; unsigned long num_allocations; unsigned long high_mark; unsigned long grown; unsigned long reaped; unsigned long errors; #ifdef CONFIG_SMP atomic_t allochit; atomic_t allocmiss; atomic_t freehit; atomic_t freemiss; #endif #endif };
slabs用它將這個cache的slab連成一個鏈表 firstnotfull指向第一個不滿的slab,當分配(復用)對象的時候，首先考慮在它指向的slab裡分配. objsize該cache中對象大小 flags num對象個數
gfporder該cache中slab一個占用多少頁面，當構造新的slab,按照這個大小向頁面級分配器申請頁面。 gfpflags申請頁面時，向頁面級分配器提出的要求，例如是否要求申請DMA的頁面，是否要求申請是原子的(即頁面分配器在分配的時候不能被阻塞) colour colour的范圍，這個cache的slab依次用0,1,...,colour-1,0,1,...為顏色。 colour_off這個cache中colour粒度，例如為一個L1-CACHE線。 colour_next下一個colour數，當cache分配一個新的slab時，采用這個colour,也就是colour * colour_off為slab空出的字節數 slabp_cache 當這個cache中的slab,其管理部分(slab描述符和kmem_bufctl_t數組)放在slab外面時，這個指針指向放置的通用cache growing dflags ctor 指向對象的構造器，在這個cache創建一個新的slab時，對裡面所有的對象都進行一次構造調用(參見slab的設計思想中關於對象復用部分) dtor 指向對象的析構器，在這個cache銷毀一個slab時，對裡面所有的對象都進行一次析構調用 failures
name 這個cache的名字 next 用它和其它的cache串成一個鏈，在這個鏈上按照時鐘算法定期地回收某個cache的部分slab
slab描述符
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;
list用於鏈表，這個鏈表將cache中所有的slab連接起來 colouroff這個slab中第一個對象距離slab起始位置(也就是頁塊起始位置)的字節數，實際上s_mem=頁塊首地址+colouroff s_mem這個slab中第一個對象的起始位置 inuse這個slab中被使用的對象個數，用於調整slab格局，當inuse=0說明這個slab全空，將這個slab從部分滿的slab段中移動到全空的slab段中 free第一個未用對象的ID, 當在這個slab"分配"(復用)對象時，首先用這個ID的對象。
通用cache索引結構 用這個結構組成的數組cache_sizes給不同尺寸的通用cache提供索引 typedef struct cache_sizes { size_t cs_size; kmem_cache_t *cs_cachep; kmem_cache_t *cs_dmacachep; } cache_sizes_t; cs_size通用cache的對象尺寸 cs_cachep指向一個通用cache, 它的對象尺寸為cs_size cs_dmacachep指向一個通用DMA的cache, 它的對象尺寸為cs_size
Slab分配器的結構
Slab 分配器用於管理內核的核心對象。
它有若干個 cache 組成。每個 cache 管理一個特定類的對象。
每個cache有若干個 slab (Slab分配器的名字可能就是怎麼來的)組成,每個 slab 實際上就是若干個頁面組成的一個頁塊。這個頁塊被細分成許多對象。 cache為管理這些slab, 通過 cache描述符( kmem_cache_t )以及指針將這些 slab 連起來。
驗證 cache的數據結構中下面這個字段: struct kmem_cache_s {
struct list_headslabs; ... ... }
與slab結構中下面字段:
typedef struct slab_s { struct list_headlist; ... } slab_t;
共同構成這個鏈表. slab如何管理它的對象
一個 slab 通過自己的 kmem_bufctl_t 數組，來管理它的空閒對象。這個數組的元素和該 slab中的對象是一一對應的。 初始化一個slab時，每個對象都是空的，所以這個數組每個元素(除最後一個)都指向下一個: 在kmem_cache_init_objs中 static inline void kmem_cache_init_objs (kmem_cache_t * cachep, slab_t * slabp, unsigned long ctor_flags) { int i;
for (i = 0; i < cachep->num; i++) { .. ... slab_bufctl(slabp)[ i ] = i+1; } slab_bufctl(slabp)[i-1] = BUFCTL_END; ... ... }
分配對象時，在下面的語句中，
objp = slabp->s_mem + slabp->free*cachep->objsize; slabp->free=slab_bufctl(slabp)[slabp->free];
取出free的數值1，計算對象1的位置即可。然後將free指向3. 回收(應該說將對象置為未用)時，將數組中對象對應的元素插入鏈表頭即可: slab_bufctl(slabp)[objnr] = slabp->free; slabp->free = objnr;
cache如何管理它的slab
格局
一個cache的所有 slab 通過指針連成一個隊列，這些 slab的排列始終保持一個格局: 全滿的，部分滿的，和全空的。 另外，cache 描述符有一個指針始終指向第一個不滿的slab(首先可能是部分滿的，其次是全空的),當它指向描述符本身的時候，說明沒有不滿的 slab了。當 slab 是否滿的狀態有變化時，cache會調整它的位置，以保持上述格局，例如一個部分滿的 slab由於它的最後一個對象被設置為不使用，即它為全空的了，那麼它將被調整到全空的slab部分中。
當分配一個新的對象時，cache 首先通過 firstnotfull 找到它的第一個不滿的slab, 在那麼分配對象。如果沒有不滿的slab, 則向頁面級分配器申請一個頁塊，然後初始化為一個slab.
回收對象
當回收一個對象時，即便在這之後，這個對象所在的 slab 為全空，cache也不會將這個 slab 占用的頁塊還給頁面級分配器。
回收slab
slab分配器算法提供兩種回收slab的方式，一種是回收某個特定的cache的所有全空的slab,直到有用戶又在該cache分配新的 slab為止( kmem_cache_shrink);一種是對所有的 cache 采用時鐘算法，每次選擇一個比較合適的 cache,回收它部分的空 slab( kmem_cache_reap ).
驗證
每次分配的時候總是考察從firstnotfull指向的第一個不滿的slab： #define kmem_cache_alloc_one(cachep) \ ({ \ slab_t*slabp; \ \ /* Get slab alloc is to come from. */ \ { \ struct list_head* p = cachep->firstnotfull;/*slabs) \ goto alloc_new_slab;/*簿褪撬狄湊飧鯿ache的slab全滿了，要麼就沒有slab,這個時候要分配新的slab*/ \ slabp = list_entry(p,slab_t, list); \ } \ kmem_cache_alloc_one_tail(cachep, slabp); \
})
在後面的kmem_cache_alloc_one_tail函數中在這個firstnotfull指向的slab中分配一個對象，如果這個slab因此而滿了，則將firstnotfull指向下一個不滿的slab: static inline void * kmem_cache_alloc_one_tail (kmem_cache_t *cachep, slab_t *slabp) { ... ... slabp->free=slab_bufctl(slabp)[slabp->free]; if (slabp->free == BUFCTL_END)/*firstnotfull = slabp->list.next; ... ... }
下面看看"釋放"一個對象時，是如何保持隊列的格局的: static inline void kmem_cache_free_one(kmem_cache_t *cachep, void *objp) { ... ... if (slabp->inuse-- ==cachep->num)/*inuse)/*firstnotfull;/*床糠致畝恿型凡?/
cachep->firstnotfull = &slabp->list;
if (slabp->list.next == t) return; list_del(&slabp->list); list_add_tail(&slabp->list, t); return; }
moveslab_free: /* * was partial, now empty. * c_firstnotfull might point to slabp * FIXME: optimize */ { struct list_head *t = cachep->firstnotfull->prev;
list_del(&slabp->list);
list_add_tail(&slabp->list,&cachep->slabs);/*firstnotfull == &slabp->list) cachep->firstnotfull = t->next;
return;
}
}
slab的管理部分 slab描述符和管理空閒對象用的數組(kmem_bufctl_t)不妨被稱為slab的管理部分
slab的管理部分放置的位置 1. 管理部分可以和對象都放在slab裡 2. 管理部分也可以放到slab外面(在某個通用的cache中，見通用cache)
1. 如果對象比較大，那麼把管理部分放到slab裡面，會浪費slab大量空間。舉一個極端的例子，對象大小為2K, 頁塊為4K,那麼如果把管理部分放到slab裡面，這個頁塊就只能放一個對象，浪費的空間=4k-2k-管理部分的尺寸接近2K!
2. 但是放在外面會帶來一些小小的效率上的損失。 如果管理部分和對象放在兩個地方，那麼一定是在不同的頁塊中。於是用戶申請一個對象時，首先要訪問slab管理部分，然後提供指向未用對象的指針，然後用戶訪問這個對象的地址。這樣，完成一個流程需要訪問兩個頁塊，也就是在TLB上要"踩"上兩個腳印(footprint).
如果管理部分和對象放在一個slab中，因而很有可能在一個頁塊中，因此完成這個流程只需在TLB上踩上一個腳印。在引起TLB失效的可能性上，前者比後者大，因而效率低。
Color slab算法中利用slab的剩余空間來做平移，第1個slab不平移；第2個slab平移1個colour粒度；...;周而復始. 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);/*colour)/*colour_next = 0; offset *=cachep->colour_off;/*s_mem =objp+colour_off;/*free指向該對象即可。為了保證這個cache中的slab格局(滿，部分滿，全空),必要的時候，要調整這個slab在鏈表中的位置，具體地說： slab原本是滿的，那麼需要將它移動到部分滿的slab中去(goto moveslab_partial) slab原本是部分滿的，現在空了，那麼將它移動到空的slab中去(moveslab_free) ~~~~~~~~ 空間回收 ~~~~~~ 所謂空間回收包括兩個工作: slab分配器把slab中的對象析構(如果有析構器的話) 將占用的頁面交還給頁面級分配器 slab的回收 kmem_slab_destroy -------------------------------------------------- 如果其中的對象有析構函數，則對這個slab中每個對象調用析構函數將這個slab占用的頁面交還給頁面級分配器.如果這個slab的管理部分在外面的話，還要到通用cache中free它的管理部分(將這個管理部分設為未用)
cache的頁面回收:__kmem_cache_shrink ------------------------------------------------------ 特點是針對某個特定的cache,將它的全空的slab全部回收從這個cache的最後一個slab往前考察(注意cache的slab的格局),回收所有全空的slab kmem_slab_destroy,除非有其它用戶在這個cache分配新的slab(這部分我還沒有仔細考慮).
cache的頁面回收: kmem_cache_reap ------------------------------------------ 在所有cache范圍內考察，每次選擇一個cache, 回收它的部分空的slab,這實際上是個垃圾回收的工作。所有在使用的cache描述符構成一個循環鏈表。為公平起見，reap采用時鐘算法，每次從當前指針位置遍歷 REAP_SCANLEN 個cache(當然可能中途結束遍歷),對這些cache進行考察，選出最佳的cache,對它的頁面進行回收: (1)排除一些當前不能回收的cache (2)計算剩下的cache中，每個cache可回收的slab個數，以及權重pages (3)選出其中權重最大的，如果某個cache的可回收的slab個數已經達到要求(>=REAP_PERFECT),就結束遍歷，對這個cache進行回收 回收:不回收這個cache中所有的空的slab, 只回收約80%, 方式和 __kmem_cache_shrink 一樣
注: 用戶接口指外部用戶可以調用的接口，其它為內部調用接口 藍色字是slab分配器的一件主要工作 綠色字是一件工作中的主要線索
一般分配一個對象，首先要創建一個cache來管理所有同類的對象(通用cache除外)。如果有cache了，那麼就在其中分配一個對象。
(用戶接口) 初始化一個cache (kmem_cache_create ) ------------------------------------ 在進行一些合法性檢查之後，首先在cache_cache中分配這個cache的描述符。 然後對一些尺寸進行處理，包括:size至少是字對齊的 對象對齊方式至少是字對齊的，如果要求是CACHE對齊，那麼方式為CACHE對齊，或者是1/2CACHE對齊(如果對象尺寸它所在的頁面 ----> cache 和 slab 第一個映射很容易(頁對齊即可)在這個函數裡主要設置第二個映射, 臨時借用了page結構裡的一個鏈表結構(這個結構list在頁面級分配器管理空閒頁面用，現在不使用)next, prev分配用來指向cache, slab.