>>> 此贴的回复 >> 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.