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;/*<----------這裡*/ \ if (p == &cachep->slabs) \ goto alloc_new_slab;/*<---------如果這個指針指向cache了，說明沒有不滿的slab了，?br>簿褪撬狄湊飧鯿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)/*<-------現在滿了，指向下一個*/ /* slab now full: move to next slab for next alloc */ cachep->firstnotfull = slabp->list.next; ... ... }
下面看看"釋放"一個對象時，是如何保持隊列的格局的: static inline void kmem_cache_free_one(kmem_cache_t *cachep, void *objp) { ... ... if (slabp->inuse-- ==cachep->num)/*<-----原來是滿的，現在"釋放"一個,變得部分滿了，則將它調整到部分滿的隊列部分中去*/
goto moveslab_partial;
if(!slabp->inuse)/*<-------原來只有一個在使用，現在這個也釋放了，因而全空了，則調整到全空的隊列部分中去*/ goto moveslab_free; return;
moveslab_partial: /* was full. * Even if the page is now empty, we can set c_firstnotfull to * slabp: there are no partial slabs in this case */ { struct list_head *t = cachep->firstnotfull;/*<-----將這個slab插到firstnotfull指向的位置就可以了,?br>床糠致畝恿型凡?/
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);/*<--------插到整個隊列尾部就可以了*/ if (cachep->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);/*<----------left_over是最多可以空出多少地方供colour使用*/ if (!cache_cache.num) BUG(); cache_cache.colour = left_over/cache_cache.colour_off;/*<--------這裡colour是最大colour的粒度，colour_off是粒度單位*/ cache_cache.colour_next =0;/*<----------------------------------下一個slab用的colour粒度*/ }
在一個cache中每增加一個slab,就要平移一個colour,在下面的函數kmem_cache_grow中: ... offset =cachep->colour_next;/*<--------------------------offset是colour粒度*/ cachep->colour_next++;/*<-------------------------准備再下一個slab用的colour*/
if (cachep->colour_next >=cachep->colour)/*<-----周而復始的使用colour*/ cachep->colour_next = 0; offset *=cachep->colour_off;/*<-----------------乘以粒度單位colour_off才是位移的字節數*/
------------------------------------- 在後面的if (!(slabp = kmem_cache_slabmgmt(cachep, objp, offset,local_flags))) 中用了這個offset,kmem_cache_slabmgmt用於分配一個slab管理部分，包括slab描述符和控制數組，如果這些結構在這個slab頁面裡面的話，就要用到colour了: static inline slab_t * kmem_cache_slabmgmt (kmem_cache_t *cachep,void *objp, int colour_off, int local_flags) { ... if (OFF_SLAB(cachep)) { ... ... } else {/*<--------------------------slab管理部分放在slab頁面裡,用到colour*/ ... ... slabp =objp+colour_off;/*<--------------------slab描述符平移了colour_off個字節，即上面的offset個字節*/ colour_off += L1_CACHE_ALIGN(cachep->num * sizeof(kmem_bufctl_t) +sizeof(slab_t)); /*<-----slab中對象還在slab描述符和控制數組之後*/
} slabp->inuse = 0; slabp->colouroff = colour_off; slabp->s_mem =objp+colour_off;/*<--------------這裡指向的就是slab中對象開始的位置*/ return slabp; } 在slab算法中提到兩個cache 一個是指CPU中的CACHE,我們知道i386一般有一個L1 DATA CACHE, 本質上一塊硬件內存.cache line指的是這個CACHE被劃分成許多部分，每部分16字節或者32字節(或其它)，它和一般內存(L2 CACHE)交互一次至少讀/寫這樣一個部分，這個部分被稱為cache line.而且這些cache line和一般內存交互的部分是被嚴格限制的，每個cache line只能和一般內存中的很小一部分交互.一個是slab中的cache,它被用來管理一個類的對象，是一個數據結構，它其中的colour的概念恰恰是為了配合L1 DATA CACHE的cache line這麼個機制的。
一個L1 DATA CACHE相當於一塊小的內存，我們假設它為16K大，它會與一般物理內存交互。它和內存交互一般一次傳輸16個字節(32個字節),也就是: CACHE 字節0-15一次寫到/讀取物理內存 ，字節16-31一次寫到/讀取物理內存.32-47 ... ...這些一次被傳輸的字節被稱為cache line。 另外，cache寫到物理內存的位置不是任意的，我們假定內存為64K,那麼cache地址0的數值只能和物理內存的地址0, 16K, 32K交互；cache地址1的數值只能和物理內存的地址1, 16K+1, 32K+1交互。。。cache地址16K-1的數值只能和物理內存的地址6K-1, 16K+16K-1, 32K+16K -1交互. 這說明了兩點: (1)假設對象A的一個字段長為16個字節，如果它放在物理地址 0-15,那麼它將和cache的第一個cache line 交互，如果放在物理地址 8-23,那麼如果CPU要訪問這個字段，必須將第一個和第二個cache line 都讀入，才能獲得這個字段的信息，顯然這樣速度慢，所以一般字段需要cache line對齊，在這裡就是16個字節對齊。 (2)關於colour 一般一個對象某些字段訪問頻繁些。假定一個cache(這個cache指slab的cache,不是上面提到CPU的L1 DATA CACHE)占用5個頁面也就是20K.假定其中對象大小為32個字節，前16個字節訪問頻繁許多。假定對象A起始於物理地址0，對象C起始於31,對象B起始於物理地址16K,那麼對象A，對象B的前16個字節都和第一個cache line 交互，後16個字節都和第二個cache line 交互對象C前16個字節與第3個cache交互。
我們假定內核訪問A後就訪問B,再訪問A,交錯進行，並且前16個字節次數都是50次，後16個為10次。C也是。這樣第一個cache line 要交互100次，第二個20次，一共120次。如果讓對象B向後移動16個字節，也就是對象B的前16個字節與第二個cache line 交互，後16個與第3個交互。那麼第一個為2次，因為只有開頭結尾2次要與內存交互，其它每次都在L1 DATACACHE 中寫就可以了。第2個cache line為20次左右(後面的只須在CACHE中讀寫),第3個cache line為20次，3個line一共才41次，你不妨仔細模擬一下。
所以進行錯位能降低CACHE的交互次數，從而提高CPU處理速度能力。這個錯位(也就是上面的16個字節)就是colour.
釋放(將對象至於未用狀態,但不析構)kfree/kmem_cache_free /kmem_cache_free_one ------------------------------------------------------------------------------------- 這裡的釋放指的是將對象設為未用狀態，而沒有析構和空間回收的操作,以備將來復用。通過映射得到對象所在的cache和slab(前者只在 kfree中使用)改動slab管理空閒對象的數組鏈表，將slabp->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對齊(如果對象尺寸<=1/2 cache line的話)考慮這個cache的slab的管理部分是否放在slab裡面. 找到一個合適的頁塊的大小，cache中每個slab將獲得這樣大小的頁塊。同時計算剩余的空間(kmem_cache_estimate以及外面的循環) 接下來的工作是: 如果剩余空間比slab管理部分大，那麼即使開始要求管理部分放在外面，現在還是將它們移動到slab裡面.計算顏色的相關數據對這個cache的描述符進行一些初始化(包括slab的鏈表)將它加到鏈表裡，以便用時鐘算法進行回收 (用戶接口) 在一個cache中分配一個對象(kmem_cache_alloc/__kmem_cache_alloc) ------------------------------------------- (在宏中kmem_cache_alloc_one) 考慮first_not_full指向的不滿的slab ●如果指向描述符本身，說明該cache都是滿的slab(或者沒有slab),於是分配一個新的slab(跳轉到alloc_new_slab然後調用kmem_cache_grow) ●如果有不滿的slab，那麼在這個slab中分配(復用)一個對象(kmem_cache_alloc_one_tail)
為某個cache分配一個新的slab(kmem_cache_grow) ------------------------------------------ 檢查是否合法(例如在中斷中必須使用原子的頁面分配，即不能在頁面分配的時候睡眠)一些設置(包括新的colour的設置) 從頁面分配器那裡獲得頁面(調用kmem_getpages)兩個初始化: 這個slab的管理部分的初始化(kmem_cache_slabmgmt),包括管理部分的位置的選取，數組的初始化等對這個新slab中所有對象初始化(如果有構造函數的話)(kmem_cache_init_objs),回顧一下slab分配器的特點可以知道在一開始的時候需要對所有對象進行初始化
還有一個特別重要的工作: 將所有對象映射到它所在的cache和slab原因是:在釋放某個對象的時候，一般slab分配器的用戶只提供對象的指針，而slab分配器必須知道它所在的cache描述符和slab描述符才好操作。
將這個slab串到cache的隊列裡采用的方法: 對象 --->它所在的頁面 ----> cache 和 slab 第一個映射很容易(頁對齊即可)在這個函數裡主要設置第二個映射, 臨時借用了page結構裡的一個鏈表結構(這個結構list在頁面級分配器管理空閒頁面用，現在不使用)next, prev分配用來指向cache, slab.
將這個slab串到cache的隊列裡采用的方法: 對象 --->它所在的頁面 ----> cache 和 slab 第一個映射很容易(頁對齊即可)在這個函數裡主要設置第二個映射, 臨時借用了page結構裡的一個鏈表結構(這個結構list在頁面級分配器管理空閒頁面用，現在不使用)next, prev分配用來指向cache, slab.
還有一個特別重要的工作: 將所有對象映射到它所在的cache和slab原因是:在釋放某個對象的時候，一般slab分配器的用戶只提供對象的指針，而slab分配器必須知道它所在的cache描述符和slab描述符才好操作。
將這個slab串到cache的隊列裡采用的方法: 對象 --->它所在的頁面 ----> cache 和 slab 第一個映射很容易(頁對齊即可)在這個函數裡主要設置第二個映射, 臨時借用了page結構裡的一個鏈表結構(這個結構list在頁面級分配器管理空閒頁面用，現在不使用)next, prev分配用來指向cache, slab.