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分配器的结构
[1] [2] [3] [4] [5] 下一页
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;
上一页 [1] [2] [3] [4] [5] 下一页
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这么个机制的。
上一页 [1] [2] [3] [4] [5] 下一页
一个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)
上一页 [1] [2] [3] [4] [5] 下一页
为某个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.
（出处：http://www.sheup.com）
将这个slab串到cache的队列里采用的方法: 对象 --->它所在的页面 ----> cache 和 slab 第一个映射很容易(页对齐即可)在这个函数里主要设置第二个映射, 临时借用了page结构里的一个链表结构(这个结构list在页面级分配器管理空闲页面用，现在不使用)next, prev分配用来指向cache, slab.
（出处：http://www.sheup.com）
还有一个特别重要的工作: 将所有对象映射到它所在的cache和slab原因是:在释放某个对象的时候，一般slab分配器的用户只提供对象的指针，而slab分配器必须知道它所在的cache描述符和slab描述符才好操作。
将这个slab串到cache的队列里采用的方法: 对象 --->它所在的页面 ----> cache 和 slab 第一个映射很容易(页对齐即可)在这个函数里主要设置第二个映射, 临时借用了page结构里的一个链表结构(这个结构list在页面级分配器管理空闲页面用，现在不使用)next, prev分配用来指向cache, slab.
（出处：http://www.sheup.com/）