技术改变命运
分类： LINUX
2016-07-26 18:49:26
原文地址：Linux slab 分配器剖析 作者：andyhzw
Slab将缓存分为两种：一种是专用高速缓存，另外一种是普通高速缓存。请注意，这里所说的高速缓存和硬件没有必然的关系，它只是slab分配器中的一个软件概念。
专用高速缓存中用来存放内核使用的数据结构，例如：mm,skb,vm等等
普通高速缓存是指存放一般的数据，比如内核为指针分配一段内存
所有的高速缓存区都通过链表的方式组织在一起，它的首结点是cache_chain
另外，普通高速缓存将分配区分为32*(2^0),32*(2^1),32*(2^2) ….32*(2^12)大小，共13个区域大小，另外，每个大小均有两个高速缓存，一个为DMA高速缓存，一个是常规高速缓存。它们都存放在一个名这cache_size的表中.
Slab分配器把每一个请求的内存称之为对象（和oop设计方法中的对象类似，都有初始化与析构）.对象又存放在slab中.slab又按照空，末满，全满全部链接至高速缓存中.如下图所示：
三：slab分配器相关的数据结构：
高速缓存：
typedef struct kmem_cache_s kmem_cache_t;
struct kmem_cache_s {
struct array_cache *array[NR_CPUS];/*per cpu结构，每次分配与释放的时候都先从这里取值与存值*/
unsigned int batchcount; /*array[NR_CPUS]中没有空闲对象时，一次为数组所分配的对象数*/
unsigned int limit; /* array[NR_CPUS]中所允许的最大空闲数 */
struct kmem_list3 lists; /*将在后面分析*/
unsigned int objsize; /*slab中的对象大小*/
unsigned int flags; /* cache标志*/
unsigned int num; /*每个slab中的对象数量 */
unsigned int free_limit; /* upper limit of objects in the lists */
spinlock_t spinlock;
unsigned int gfporder; /*2^gfporder即为cache中slab的大小*/
unsigned int gfpflags;
size_t colour; /*着色机制，后面会详细分析 */
unsigned int colour_off; /* colour offset */
unsigned int colour_next; /* cache colouring */
kmem_cache_t *slabp_cache;/*slab描述符放在缓存区外面时，此值指向描述符在普通缓存区中的位置*/
unsigned int slab_size; /*每一个slab的大小*/
unsigned int dflags; /* dynamic flags */
void (*ctor)(void *, kmem_cache_t *, unsigned long); /*构造函数*/
void (*dtor)(void *, kmem_cache_t *, unsigned long); /*析构函数*/
const char *name; /*cache的名字*/
struct list_head next; /*下一个cache 用来构成链表*/
/* 5) statistics */
#if STATS
unsigned long num_active;
unsigned long num_allocations;
unsigned long high_mark;
unsigned long grown;
unsigned long reaped;
unsigned long errors;
unsigned long max_freeable;
atomic_t allochit;
atomic_t allocmiss;
atomic_t freehit;
atomic_t freemiss;
#endif
#if DEBUG
int dbghead;
int reallen;
#endif
}
这里值得注意的地方是，与2.4相比，slab部份的结构与成员位置发生了很大改变。一般来说经常用的成员放在结构体的前面。后面会解述为什么。
在cache这个结构里，有两个很重要的结构：struct array_cache *array[NR_CPUS]与struct kmem_list3 lists;详细分析一下
struct array_cache {
unsigned int avail; //当前空闲对象的位置
unsigned int limit; //允许的空闲对象的最大值
unsigned int batchcount; //一次要填充给数组的对象数，或者一次要释放的对象数
unsigned int touched; //如果从该组中分配了对象，则把此值置为1
}
struct kmem_list3 {
struct list_head slabs_partial; /*末满的slab链 */
struct list_head slabs_full; /*满的slab链*/
struct list_head slabs_free; /*完全空闲的slab链*/
unsigned long free_objects; /*空链的对象数*/
int free_touched;
unsigned long next_reap;
struct array_cache *shared; /*全局shar数组。当array[NR_CPUS]满了之后，会将对象释放至此，array[NR_CPUS]请求对象时，会先在这里取得对象 */
}
Slab的数据结构
struct slab {
struct list_head list; /*用来构成链表*/
unsigned long colouroff; /*着色机制，后面会详解*/
void *s_mem; /* 首个对象的起始地址 */
unsigned int inuse; /* slab中的使用对象个数 */
kmem_bufctl_t free; /*slab中的第一个空闲对象的序号*/
};
四：slab中的着色机制
在我们分析详细的代码之前，有必要首先了解一下slab的着色机制。
Slab中引用着色机制是为了提高L1缓冲的效率。我们知道linux是一个兼容性很高的平台，但现在处理器的缓冲区方式多种多样，有的每个处理器有自己的独立缓存。有的很多处理器共享一个缓存。有的除了一级缓存（L1）外还是二级缓存（L2），因此，linux为了更好的兼容处理平台，只优化了一级缓存
为了下面的分析，我们不妨假设一下：假设处理器每根缓存线为32字节，L1大小为16K （可以算出共有512根缓存线）,每根缓存线与主存交互的大小也被称为cache line ，在这个例子中cache line是32字节
只有当处理器检测到缓存线冲突时（读或者写失效），才会与主存交互，例如当处理器检测到缓存读失效，会将相应地址所在的32字节读取到缓存。有这里有一点要注意的是，缓存与主存的交互是按照块大小来的，即一次读或者写32字节。而且每条缓存线所读取的地址不是任意的。例如：第0根缓存总线只能读取 0~32 16K ~ 16K+32 32K~32K+32的地址
Slab分配器要求对象按照cache line对齐，我们来看一下，如果没有对齐，会造成什么样的影响：
假设对象为20个字节，一个对象的起始地址是0 位于第0条缓存线。第二个地址的0~9位于第0条缓存线，10~19位于第1条缓存线。可以想象一下，如果要读入第二个对象，就会刷新二个缓存，共64个字节的数据。若是按照cache line对齐，则只要刷新一次高速缓存，只要交互32字节的数据。
当然，如果对象大小太小，我们是以cache line折半来对齐的，这我们在后面的代码中可以看到
讨论完cache line对齐之后，我们再来看看什么叫着色。
假设现在有这样的两个对象A，B A位于0~64于，第0条缓存线。B位于16K之后的64个字节，也是第0条缓存线。我们在上面的分析可以看到，常用的数据结构经常放在结构体的前面。此时就会有高32位的访问频率大大高于低32位的访问频率。假设此时，访问A之后再来访问B。高位访问50次，低位访问10次。
我们来看看这时的情况：
处理器在访问完A后，再访问B的地址，发现B需要缓冲线0，则把缓冲线0的数据写回主存，再读入B的值，访问完B后，发现又要访问A，此时，又把B的值写回主存，再读入A的值 …
按这样计算，共需要和主存交互50*2 + 10*2 = 120次
我们不妨把B后移32字节，这样B的高32位就位于缓存线1 低32位处于缓存线2。这时，访问完A后，访问B只需要把B的数据读科第1，第2缓存线，直接交互就行了。
如果经常有这样的情况发生，就会产生极大的“颠簸”，极度影响系统效率
基于这样的情况。Slab 分器配把每一个slab都错开了，都往后移了一个或者是多个cache line
详细情况可以参考：
)
在此非常感谢linuxforum的lucian_yao,你的文章给了我极大的帮助 ^_^
五：kmem_cache_create（）分析
我们以一个例子来跟踪分析一下slab的机制：
下面是一个测试模块的代码：
点击(此处)折叠或打开
我们把模块加载之后，用dmesg的命令可以看到如下的输出信息：
点击(此处)折叠或打开
点击(此处)折叠或打开
从上我们可以看到，当从cache中分配一个对象时，会初始化很多object（dmesg输出信息中，出现多次in ctor fuction ...），当一个对象释放时，并没有马上调用其析构函数。
我们来看看具体的代码
kmem_cache_create（）是创建一个专用cache.同样的，所有专用缓冲区头部也由一个slab分配器维护，它的名字叫：cache_cache。其中每个大个对象的大小均为sizeof(cache).它是静态初始化的：
static kmem_cache_t cache_cache = {
.lists = LIST3_INIT(cache_cache.lists),
.batchcount = 1,
.limit = BOOT_CPUCACHE_ENTRIES,
.objsize = sizeof(kmem_cache_t),
.flags = SLAB_NO_REAP,
.spinlock = SPIN_LOCK_UNLOCKED,
.name = "kmem_cache",
#if DEBUG
.reallen = sizeof(kmem_cache_t),
#endif
};
Kmem_cache_creat的代码在slab.c中，如下所示：
//参数含义：
//name:cache名字。Align:对齐量.flags:分配标志，ctor:初始化函数 ,dtor析构函数
kmem_cache_t *kmem_cache_create (const char *name, size_t size, size_t align,
unsigned long flags, void (*ctor)(void*, kmem_cache_t *, unsigned long),
void (*dtor)(void*, kmem_cache_t *, unsigned long))
{
size_t left_over, slab_size;
kmem_cache_t *cachep = NULL;
//参数检测名字不能为空，有析构函数，必须要用初始化函数，不能在中断中，对像不能太大也不能太小(不//能超过2^5个页)
if ((!name) ||in_interrupt() ||(size < BYTES_PER_WORD) ||
(size > (1<
(dtor && !ctor)) {
printk(KERN_ERR "%s: Early error in slab %s\n",
__FUNCTION__, name);
BUG();
}
if (flags & SLAB_DESTROY_BY_RCU)
BUG_ON(dtor);
//flag参数的有效性检查
if (flags & ~CREATE_MASK)
BUG();
//align参数的调整。如无特别要求，align设为零，flag设为SLAB_HWCACHE_ALIGN。按照处理器缓//存对齐
if (align) {
flags &= ~(SLAB_RED_ZONE|SLAB_STORE_USER);
} else {
if (flags & SLAB_HWCACHE_ALIGN) {
//cache_line_size取得处理平始的cache line.前面已经分析过
align = cache_line_size();
//如果对象太小，为了提高利用了，取cache line半数对齐
while (size <= align/2)
align /= 2;
} else {
align = BYTES_PER_WORD;
}
}
//从cache_cache中分得一个缓存描述符 kmem_cache_alloc函数在后面讲述
cachep = (kmem_cache_t *) kmem_cache_alloc(&cache_cache, SLAB_KERNEL);
if (!cachep)
goto opps;
//初始化
memset(cachep, 0, sizeof(kmem_cache_t));
//把大小按照BYTES_PER_WORD 对齐。BYTES_PER_WORD也即处理器的地址单元，在i32 为32
if (size & (BYTES_PER_WORD-1)) {
size += (BYTES_PER_WORD-1);
size &= ~(BYTES_PER_WORD-1);
}
//如果size 大于1/8 个页面。就把slab放到缓存区的外面
if (size >= (PAGE_SIZE>>3))
flags |= CFLGS_OFF_SLAB;
//使size按照align对齐
size = ALIGN(size, align);
if ((flags & SLAB_RECLAIM_ACCOUNT) && size <= PAGE_SIZE) {
cachep->gfporder = 0;
cache_estimate(cachep->gfporder, size, align, flags,
&left_over, &cachep->num);
} else {
//在这里，为cache中每个slab的大小以及slab中的对象个数取得一个平衡点
do {
unsigned int break_flag = 0;
cal_wastage:
//cache_estimate:指定slab的大小后，返回slab中的对像个数
//以及剩余空间数
cache_estimate(cachep->gfporder, size, align, 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) {
/* This num of objs will cause problems. */
cachep->gfporder--;
break_flag++;
goto cal_wastage;
}
/*
* Large num of objs is good, but v. large slabs are
* currently bad for the gfp()s.
*/
if (cachep->gfporder >= slab_break_gfp_order)
break;
if ((left_over*8) <= (PAGE_SIZE<
break; /* Acceptable internal fragmentation. */
next:
cachep->gfporder++;
} while (1);
}
if (!cachep->num) {
//出现意外，打印出常现的oops错误
printk("kmem_cache_create: couldn't create cache %s.\n", name);
kmem_cache_free(&cache_cache, cachep);
cachep = NULL;
goto opps;
}
使slab大小按照align对齐
slab_size = ALIGN(cachep->num*sizeof(kmem_bufctl_t)
+ sizeof(struct slab), align);
if (flags & CFLGS_OFF_SLAB && left_over >= slab_size) {
//如果剩余空间足间大，就把slab描述符放到缓存区里面
flags &= ~CFLGS_OFF_SLAB;
left_over -= slab_size;
}
if (flags & CFLGS_OFF_SLAB) {
//如果slab描述符依然只能放到缓存区外面。则取slab_size大小的实际值
//也就是说不需要与alin 对齐了
slab_size = cachep->num*sizeof(kmem_bufctl_t)+sizeof(struct slab);
}
//着色偏移量，至少为一个cache_size.若align值是自己指定的，且超出了一个cache size.这样//值就会取设定的align
cachep->colour_off = cache_line_size();
if (cachep->colour_off < align)
cachep->colour_off = align;
//颜色的总数,为剩余的空间数/着色偏移量
//从这里我们可以看到，如果偏移量太少，着色机制是没有任何意义的
//这是值得提醒的是colour_next没有被特别赋值，即为默认值0
cachep->colour = left_over/cachep->colour_off;
//各种成员的初始化
cachep->slab_size = slab_size;
cachep->flags = flags;
cachep->gfpflags = 0;
if (flags & SLAB_CACHE_DMA)
cachep->gfpflags |= GFP_DMA;
spin_lock_init(&cachep->spinlock);
cachep->objsize = size;
/* NUMA */
INIT_LIST_HEAD(&cachep->lists.slabs_full);
INIT_LIST_HEAD(&cachep->lists.slabs_partial);
INIT_LIST_HEAD(&cachep->lists.slabs_free);
//如果slab描述符是放在缓存区外面的。那就为slab描述符指定一个分配缓存
if (flags & CFLGS_OFF_SLAB)
cachep->slabp_cache = kmem_find_general_cachep(slab_size,0);
cachep->ctor = ctor;
cachep->dtor = dtor;
cachep->name = name;
/* Don't let CPUs to come and go */
lock_cpu_hotplug();
//g_cpucache_up：判断普通缓存是否就绪的标志
//NONE是初始值 PARTIAL：是一个中间的状态，即普通缓存正在初始化
//FULL：普通缓存已经初始化完成
if (g_cpucache_up == FULL) {
enable_cpucache(cachep);
} else {
if (g_cpucache_up == NONE) {
/* Note: the first kmem_cache_create must create
* the cache that's used by kmalloc(24), otherwise
* the creation of further caches will BUG().
*/
cachep->array[smp_processor_id()] =
&initarray_generic.cache;
g_cpucache_up = PARTIAL;
} else {
cachep->array[smp_processor_id()] =
kmalloc(sizeof(struct arraycache_init),
GFP_KERNEL);
}
BUG_ON(!ac_data(cachep));
ac_data(cachep)->avail = 0;
ac_data(cachep)->limit = BOOT_CPUCACHE_ENTRIES;
ac_data(cachep)->batchcount = 1;
ac_data(cachep)->touched = 0;
cachep->batchcount = 1;
cachep->limit = BOOT_CPUCACHE_ENTRIES;
cachep->free_limit = (1+num_online_cpus())*cachep->batchcount
+ cachep->num;
}
cachep->lists.next_reap = jiffies + REAPTIMEOUT_LIST3 +
((unsigned long)cachep)%REAPTIMEOUT_LIST3;
//查看是否有相同名字的cache
down(&cache_chain_sem);
{
struct list_head *p;
mm_segment_t old_fs;
old_fs = get_fs();
set_fs(KERNEL_DS);
list_for_each(p, &cache_chain) {
kmem_cache_t *pc = list_entry(p, kmem_cache_t, next);
char tmp;
/*
* This happens when the module gets unloaded and
* doesn't destroy its slab cache and noone else reuses
* the vmalloc area of the module. Print a warning.
*/
#ifdef CONFIG_X86_UACCESS_INDIRECT
if (__direct_get_user(tmp,pc->name)) {
#else
if (__get_user(tmp,pc->name)) {
#endif
printk("SLAB: cache with size %d has lost its "
"name\n", pc->objsize);
continue;
}
if (!strcmp(pc->name,name)) {
printk("kmem_cache_create: duplicate "
"cache %s\n",name);
up(&cache_chain_sem);
unlock_cpu_hotplug();
BUG();
}
}
set_fs(old_fs);
}
//将cache挂至cache_chain链
list_add(&cachep->next, &cache_chain);
up(&cache_chain_sem);
unlock_cpu_hotplug();
opps:
if (!cachep && (flags & SLAB_PANIC))
panic("kmem_cache_create(): failed to create slab `%s'\n",
name);
return cachep;
}
首先我们遇到的问题是第一个鸡与鸡蛋的问题：新建cache描述符是从cache_cache中分配cache描述符，那cache_cache是从何而来呢？cache_cache是静态定义的一个数据结构，只要静态初始化它的成员就可以了。另一个鸡与鸡蛋的问题就是cache中array数组的初始化问题。例如:
cachep->array[smp_processor_id()] =
kmalloc(sizeof(struct arraycache_init),
GFP_KERNEL);
也就是说从普通缓存中分得空间，那普通缓存区中的arry如何取得空间呢？这也是一个静态定义的数组：initarray_generic.cache。我们以后再详细分析内存各子系统的初始化过程。详情请关注本站更新。
另外，我们也接触到了着色部份的代码。如下所示：
cachep->colour_off = cache_line_size();
if (cachep->colour_off < align)
cachep->colour_off = align;
cachep->colour = left_over/cachep->colour_off;
着色的原理在前面已经分析过了。Colour_off:每一个slab中偏移值。以colour:颜色的总数，即最大的偏移位置，它的大小为剩余大小/偏移值，colour_next初始化为零。
举例说明:
Colour_off = 32 colour = 2; colour_next = 0
第一个slab偏移colour_next* Colour_off = 0*32 = 0 然后colour_next加1。即为1
第二个slab偏移colour_next* Colour_off = 1*32 = 32然后colour_next加1。即为2
第三个slab偏移colour_next* Colour_off = 2*32 = 64然后colour_next加1。即为3，由于colour为2。所以，colour_next = 0;
第四个slab偏移colour_next* Colour_off = 0*32 = 0
……
另外：要注意的是slab大小计算的时候：
slab_size = ALIGN(cachep->num*sizeof(kmem_bufctl_t) + sizeof(struct slab), align);
虽然在struct slab里没有定义kmem_bufctl_t.但在为slab申请空间的时候申请了num个kmem_bufctl_t的多余空间，也就是说kmem_bufctl_t数组紧放在slab描述符之后
此外，array被初始化了arraycache_init大小。
struct arraycache_init {
struct array_cache cache;
void * entries[BOOT_CPUCACHE_ENTRIES];
};
为什么要这样做？我们在后面再给出分析
六：kmem_cache_alloc的实现分析:
我们在上面可以看到，创建一个cache描述符的时候，并没有这之分配slab数据。现在我们来看一下怎么从cache中申请对象
void * kmem_cache_alloc (kmem_cache_t *cachep, int flags)
{
return __cache_alloc(cachep, flags);
}
实际上会调用__cache_alloc
如下：
static inline void * __cache_alloc (kmem_cache_t *cachep, int flags)
{
unsigned long save_flags;
void* objp;
struct array_cache *ac;
//如果定义了__GFP_WAIT。可能会引起睡眠
cache_alloc_debugcheck_before(cachep, flags);
local_irq_save(save_flags);
//取得当前处理器所在的array_cache(简称为AC，我们下面也这样称呼它)
ac = ac_data(cachep);
//ac->avail:AC中第后一个可用的对象索引
//如果AC中还有可用的对象
if (likely(ac->avail)) {
STATS_INC_ALLOCHIT(cachep);
//每次分配都会把ac->touched置为1
ac->touched = 1;
objp = ac_entry(ac)[--ac->avail];
} else {
//如果AC中没有可用对象，那只能从l3中“搬出”对象到AC中
STATS_INC_ALLOCMISS(cachep);
objp = cache_alloc_refill(cachep, flags);
}
local_irq_restore(save_flags);
objp = cache_alloc_debugcheck_after(cachep, flags, objp, __builtin_return_address(0));
return objp;
}
首先，会从AC中分配对象，如果AC中无可用对象，那就从l3链表中分配对象了，首先它会从share链表中取对象，然后再从末满，空链表中取对象，如果都没有空闲对象的话，只能从伙伴系统中分配内存了.接着看下面的代码：
static void* cache_alloc_refill(kmem_cache_t* cachep, int flags)
{
int batchcount;
struct kmem_list3 *l3;
struct array_cache *ac;
check_irq_off();
ac = ac_data(cachep);
retry:
//batchcount:一次向AC填充的对象值
batchcount = ac->batchcount;
if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {
batchcount = BATCHREFILL_LIMIT;
}
//取得cache所对象的l3
l3 = list3_data(cachep);
//如果Ac中依然有可用对象，则退出
BUG_ON(ac->avail > 0);
spin_lock(&cachep->spinlock);
//首先会从shared中取对象
if (l3->shared) {
struct array_cache *shared_array = l3->shared;
if (shared_array->avail) {
如果share的剩余量不足batchcount。则把它全部都移至AC中
if (batchcount > shared_array->avail)
batchcount = shared_array->avail;
shared_array->avail -= batchcount;
ac->avail = batchcount;
//把share链中的object拷贝到AC中
memcpy(ac_entry(ac), &ac_entry(shared_array)[shared_array->avail],
sizeof(void*)*batchcount);
shared_array->touched = 1;
//AC中已经有数据了，那么，可以直接从AC中分配了
goto alloc_done;
}
}
//运行到这里的话，那说明share链中没有对象了
while (batchcount > 0) {
//先从末满的链表中获取，若末满链为空的话，从全空链表中获取
struct list_head *entry;
struct slab *slabp;
/* Get slab alloc is to come from. */
entry = l3->slabs_partial.next;
//判断slabs_partial是否为空
if (entry == &l3->slabs_partial) {
l3->free_touched = 1;
//判断slabs_free链是否为空
entry = l3->slabs_free.next;
if (entry == &l3->slabs_free)
//若全为空的话，就从伙伴系统中分配页面了
goto must_grow;
}
//从链表中取得slab描述符
slabp = list_entry(entry, struct slab, list);
check_slabp(cachep, slabp);
check_spinlock_acquired(cachep);
//对象取尽，或者已经满尽分配要求
while (slabp->inuse < cachep->num && batchcount--) {
//从相应的slab中分配对象
kmem_bufctl_t next;
STATS_INC_ALLOCED(cachep);
STATS_INC_ACTIVE(cachep);
STATS_SET_HIGH(cachep);
//得到空闲对象指针
ac_entry(ac)[ac->avail++] = slabp->s_mem + slabp->free*cachep->objsize;
//更新计数
slabp->inuse++;
next = slab_bufctl(slabp)[slabp->free];
#if DEBUG
slab_bufctl(slabp)[slabp->free] = BUFCTL_FREE;
#endif
//使free指向下一人空闲对像的索引
slabp->free = next;
}
check_slabp(cachep, slabp);
/* move slabp to correct slabp list: */
//slab从链中脱落
list_del(&slabp->list);
if (slabp->free == BUFCTL_END)
//如果slab中没有空闲对象了，则把它加入slabs_full链
list_add(&slabp->list, &l3->slabs_full);
else
//如果slab中没有空闲对象了，则把它加入slabs_partial链
list_add(&slabp->list, &l3->slabs_partial);
}
must_grow:
//更新free_objects计数.(如果三链都为空的情况下：ac->avail为进入函数的初始值，即为0)
l3->free_objects -= ac->avail;
alloc_done:
spin_unlock(&cachep->spinlock);
if (unlikely(!ac->avail)) {
int x;
x = cache_grow(cachep, flags);
// cache_grow can reenable interrupts, then ac could change.
ac = ac_data(cachep);
//如果grow失败，返回NULL
if (!x && ac->avail == 0) // no objects in sight? abort
return NULL;
//如果grow成功，则重复上述操作，即从三链表中取空闲对象^_^
if (!ac->avail) // objects refilled by interrupt?
goto retry;
}
ac->touched = 1;
return ac_entry(ac)[--ac->avail];
}
这段代码涉及到slab_bufctl（），等我们看完分配，释放的全过程后。再来详细分析它涉及到的各项操作,cache_grow()用来做slab分配器与slab的交互。它的代码如下示：
static int cache_grow (kmem_cache_t * cachep, int flags)
{
struct slab *slabp;
void *objp;
size_t offset;
int local_flags;
unsigned long ctor_flags;
if (flags & ~(SLAB_DMA|SLAB_LEVEL_MASK|SLAB_NO_GROW))
BUG();
if (flags & SLAB_NO_GROW)
return 0;
ctor_flags = SLAB_CTOR_CONSTRUCTOR;
local_flags = (flags & SLAB_LEVEL_MASK);
if (!(local_flags & __GFP_WAIT))
/*
* Not allowed to sleep. Need to tell a constructor about
* this - it might need to know...
*/
ctor_flags |= SLAB_CTOR_ATOMIC;
/* About to mess with non-constant members - lock. */
check_irq_off();
spin_lock(&cachep->spinlock);
//取得下一个偏移索引（着色机制在前面已经详细分析了）
offset = cachep->colour_next;
cachep->colour_next++;
//如果大于允许的最大颜色，那就把计数归位，即为0
if (cachep->colour_next >= cachep->colour)
cachep->colour_next = 0;
//计算偏移量
offset *= cachep->colour_off;
spin_unlock(&cachep->spinlock);
if (local_flags & __GFP_WAIT)
local_irq_enable();
kmem_flagcheck(cachep, flags);
//向伙伴系统申请内存
if (!(objp = kmem_getpages(cachep, flags, -1)))
goto failed;
//分配slab描述符，这里有两种情况，一种是slab在缓存外部，另一种是内部
if (!(slabp = alloc_slabmgmt(cachep, objp, offset, local_flags)))
goto opps1;
set_slab_attr(cachep, slabp, objp);
//初始化slab的对像
cache_init_objs(cachep, slabp, ctor_flags);
if (local_flags & __GFP_WAIT)
local_irq_disable();
check_irq_off();
spin_lock(&cachep->spinlock);
//将新构建的slab加至slabs_free链
list_add_tail(&slabp->list, &(list3_data(cachep)->slabs_free));
STATS_INC_GROWN(cachep);
//更新计数
list3_data(cachep)->free_objects += cachep->num;
spin_unlock(&cachep->spinlock);
return 1;
opps1:
//发生了错误，把内存归还伙伴系统
kmem_freepages(cachep, objp);
failed:
if (local_flags & __GFP_WAIT)
local_irq_disable();
return 0;
}
我们看到了cache_grow的概貌，接着分析它里面调用的子函数。
kmem_getpages（）用于slab分配器向伙伴系统分配内存，代码如下：
//nodeid:分配内面的cpu结点。如果从当前CPU分存，nodeid置为-1
static void *kmem_getpages(kmem_cache_t *cachep, int flags, int nodeid)
{
struct page *page;
void *addr;
int i;
flags |= cachep->gfpflags;
//__get_free_pages与alloc_pages_node在《linux内存管理之伙伴系统分析》一文中已有详
//细分析，请参考
if (likely(nodeid == -1)) {
//从当前cpu结点分配内存
addr = (void*)__get_free_pages(flags, cachep->gfporder);
if (!addr)
return NULL;
//将地址转换为页描述符
page = virt_to_page(addr);
} else {
//从指定结点分配内存
page = alloc_pages_node(nodeid, flags, cachep->gfporder);
if (!page)
return NULL;
addr = page_address(page);
}
//计算页面个数。即为2^ cachep->gfporder
i = (1 << cachep->gfporder);
if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
atomic_add(i, &slab_reclaim_pages);
//更新cpu nr_slab状态计数
add_page_state(nr_slab, i);
while (i--) {
//将页面标识为PG_slab,表示该页面已被slab使用
SetPageSlab(page);
page++;
}
return addr;
}
alloc_slabmgmt()是一个slab描述符分配器接口，代码如下：
static struct slab* alloc_slabmgmt (kmem_cache_t *cachep,
void *objp, int colour_off, int local_flags)
{
struct slab *slabp;
//如果slab描述符是外置的
if (OFF_SLAB(cachep)) {
//从对应的cache中分配slab描述符
slabp = kmem_cache_alloc(cachep->slabp_cache, local_flags);
if (!slabp)
return NULL;
} else {
//从偏移量后开始安置slab
slabp = objp+colour_off;
//更新偏移量，即加上slab的大小，这位置也是有效数据的起始偏移位置
colour_off += cachep->slab_size;
}
slabp->inuse = 0;
slabp->colouroff = colour_off;
slabp->s_mem = objp+colour_off;
return slabp;
}
cache_init_objs（）初始化分配得到的每一个对象，代码如下：
static void cache_init_objs (kmem_cache_t * cachep,
struct slab * slabp, unsigned long ctor_flags)
{
int i;
for (i = 0; i < cachep->num; i++) {
//取slab中的每一个对像
void* objp = slabp->s_mem+cachep->objsize*i;
#if DEBUG
//忽略掉debug信息
/* need to poison the objs? */
if (cachep->flags & SLAB_POISON)
poison_obj(cachep, objp, POISON_FREE);
if (cachep->flags & SLAB_STORE_USER)
*dbg_userword(cachep, objp) = NULL;
if (cachep->flags & SLAB_RED_ZONE) {
*dbg_redzone1(cachep, objp) = RED_INACTIVE;
*dbg_redzone2(cachep, objp) = RED_INACTIVE;
}
/*
* Constructors are not allowed to allocate memory from
* the same cache which they are a constructor for.
* Otherwise, deadlock. They must also be threaded.
*/
if (cachep->ctor && !(cachep->flags & SLAB_POISON))
cachep->ctor(objp+obj_dbghead(cachep), cachep, ctor_flags);
if (cachep->flags & SLAB_RED_ZONE) {
if (*dbg_redzone2(cachep, objp) != RED_INACTIVE)
slab_error(cachep, "constructor overwrote the"
" end of an object");
if (*dbg_redzone1(cachep, objp) != RED_INACTIVE)
slab_error(cachep, "constructor overwrote the"
" start of an object");
}
if ((cachep->objsize % PAGE_SIZE) == 0 && OFF_SLAB(cachep) && cachep->flags & SLAB_POISON)
kernel_map_pages(virt_to_page(objp), cachep->objsize/PAGE_SIZE, 0);
#else
//如果有初始化函数，则调用之
if (cachep->ctor)
cachep->ctor(objp, cachep, ctor_flags);
#endif
//更新bufctl数组
slab_bufctl(slabp)[i] = i+1;
}
//置末尾描述符
slab_bufctl(slabp)[i-1] = BUFCTL_END;
slabp->free = 0;
}
同样，slab_bufctl的分析，等讲完释放对像的时候再继续
到此，我们已经看完到分配对象的全过程，接着来看怎么释放一个对象
七：kmem_cache_free（）的实现
kmem_cache_free用于把从slab中分配的对象释放掉，同分配一样，它首先会把它放到AC中，如果AC满了，则把对象释放到share链中，如果share也满了，也就把它释放至slab。来看具体的代码：
void kmem_cache_free (kmem_cache_t *cachep, void *objp)
{
unsigned long flags;
local_irq_save(flags);
__cache_free(cachep, objp);
local_irq_restore(flags);
}
函数调用__cache_free(),代码如下：
static inline void __cache_free (kmem_cache_t *cachep, void* objp)
{
struct array_cache *ac = ac_data(cachep);
check_irq_off();
//DEBUG用，忽略
objp = cache_free_debugcheck(cachep, objp, __builtin_return_address(0));
//如果AC中的对像没有超过限制，那就把它释放到AC中。
if (likely(ac->avail < ac->limit)) {
STATS_INC_FREEHIT(cachep);
ac_entry(ac)[ac->avail++] = objp;
return;
} else {
//如果AC中对象数目到了限值，则cache_flusharray（）后，再把对像加入AC中
STATS_INC_FREEMISS(cachep);
cache_flusharray(cachep, ac);
ac_entry(ac)[ac->avail++] = objp;
}
}
如果当前AC中对象数已经到达限值，就会调用cache_flusharray()将里面的对象“刷新”出去。代码如下：
static void cache_flusharray (kmem_cache_t* cachep, struct array_cache *ac)
{
int batchcount;
//要从AC中转移的对象数
batchcount = ac->batchcount;
#if DEBUG
BUG_ON(!batchcount || batchcount > ac->avail);
#endif
check_irq_off();
spin_lock(&cachep->spinlock);
if (cachep->lists.shared) {
struct array_cache *shared_array = cachep->lists.shared;
int max = shared_array->limit-shared_array->avail;
if (max) {
//如果share中还有可闲
if (batchcount > max)
batchcount = max;
//将AC中的对象复制到share中
memcpy(&ac_entry(shared_array)[shared_array->avail],
&ac_entry(ac)[0],
sizeof(void*)*batchcount);
shared_array->avail += batchcount;
goto free_done;
}
}
//运行到这里。说明share也满了，只能把对象归还slab了
free_block(cachep, &ac_entry(ac)[0], batchcount);
free_done:
//STATS只有在打开DEBUG开关的时候才会为1，起DEBUG作用，忽略之
#if STATS
{
int i = 0;
struct list_head *p;
p = list3_data(cachep)->slabs_free.next;
while (p != &(list3_data(cachep)->slabs_free)) {
struct slab *slabp;
slabp = list_entry(p, struct slab, list);
BUG_ON(slabp->inuse);
i++;
p = p->next;
}
STATS_SET_FREEABLE(cachep, i);
}
#endif
spin_unlock(&cachep->spinlock);
//更新avail计数
ac->avail -= batchcount;
//从前面已经知道，实际上AC中的0~batchcount项都已经转移到share中了
//所以，把batchcount后面的项移到前面
memmove(&ac_entry(ac)[0], &ac_entry(ac)[batchcount],
sizeof(void*)*ac->avail);
}
free_block()用于将对象归还给slab,代码如下：
static void free_block(kmem_cache_t *cachep, void **objpp, int nr_objects)
{
int i;
check_spinlock_acquired(cachep);
//更新free_objects计数
cachep->lists.free_objects += nr_objects;
for (i = 0; i < nr_objects; i++) {
void *objp = objpp[i];
struct slab *slabp;
unsigned int objnr;
//取得对象所在的slab
slabp = GET_PAGE_SLAB(virt_to_page(objp));
list_del(&slabp->list);
//对象在slab中的序号
objnr = (objp - slabp->s_mem) / cachep->objsize;
check_slabp(cachep, slabp);
#if DEBUG
if (slab_bufctl(slabp)[objnr] != BUFCTL_FREE) {
printk(KERN_ERR "slab: double free detected in cache '%s', objp %p.\n",
cachep->name, objp);
BUG();
}
#endif
//更新bufctl
slab_bufctl(slabp)[objnr] = slabp->free;
slabp->free = objnr;
STATS_DEC_ACTIVE(cachep);
slabp->inuse--;
check_slabp(cachep, slabp);
//调整slab所在的链表
if (slabp->inuse == 0) {
//如果slabp中没有被使用的对像
if (cachep->lists.free_objects > cachep->free_limit) {
//如果cahce中空闲对象数超过限值，则把slab释放掉
cachep->lists.free_objects -= cachep->num;
slab_destroy(cachep, slabp);
} else {
//把slab移到“全空”链表
list_add(&slabp->list,
&list3_data_ptr(cachep, objp)->slabs_free);
}
} else {
//把slabp加入到slabs_partial末尾
list_add_tail(&slabp->list,
&list3_data_ptr(cachep, objp)->slabs_partial);
}
}
}
//slab_destroy用于将slabp所点的空间全部都释放掉
static void slab_destroy (kmem_cache_t *cachep, struct slab *slabp)
{
//将slabp->s_mem前移colouroff位，即为slab的起始地址
void *addr = slabp->s_mem - slabp->colouroff;
//忽略掉DEBUG
#if DEBUG
int i;
for (i = 0; i < cachep->num; i++) {
void *objp = slabp->s_mem + cachep->objsize * i;
if (cachep->flags & SLAB_POISON) {
#ifdef CONFIG_DEBUG_PAGEALLOC
if ((cachep->objsize%PAGE_SIZE)==0 && OFF_SLAB(cachep))
kernel_map_pages(virt_to_page(objp), cachep->objsize/PAGE_SIZE,1);
else
check_poison_obj(cachep, objp);
#else
check_poison_obj(cachep, objp);
#endif
}
if (cachep->flags & SLAB_RED_ZONE) {
if (*dbg_redzone1(cachep, objp) != RED_INACTIVE)
slab_error(cachep, "start of a freed object "
"was overwritten");
if (*dbg_redzone2(cachep, objp) != RED_INACTIVE)
slab_error(cachep, "end of a freed object "
"was overwritten");
}
if (cachep->dtor && !(cachep->flags & SLAB_POISON))
(cachep->dtor)(objp+obj_dbghead(cachep), cachep, 0);
}
#else
//为其中的每一对象调用析构函数
if (cachep->dtor) {
int i;
for (i = 0; i < cachep->num; i++) {
void* objp = slabp->s_mem+cachep->objsize*i;
(cachep->dtor)(objp, cachep, 0);
}
}
#endif
if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU)) {
struct slab_rcu *slab_rcu;
slab_rcu = (struct slab_rcu *) slabp;
slab_rcu->cachep = cachep;
slab_rcu->addr = addr;
call_rcu(&slab_rcu->head, kmem_rcu_free);
} else {
//将内存归还伙伴系统
kmem_freepages(cachep, addr);
if (OFF_SLAB(cachep))
//如果slab是外置的，则将slab则相应的cache中释放掉
kmem_cache_free(cachep->slabp_cache, slabp);
}
}
八：kmem_cache_destroy（）实现:
Kmem_cache_destroy先会将AC和share中的对象释放到slab中，再把每一个slab都释放掉，如果当前cache中没有被分配对象的话，就会释放掉cache描述符，AC和share。代码如下：
int kmem_cache_destroy (kmem_cache_t * cachep)
{
int i;
//参数为空，或者在中断处理中。
if (!cachep || in_interrupt())
BUG();
/* Don't let CPUs to come and go */
lock_cpu_hotplug();
/* Find the cache in the chain of caches. */
down(&cache_chain_sem);
//将cache脱链
list_del(&cachep->next);
up(&cache_chain_sem);
//_cache_shrink(cachep)：将cachep中的所有slabp全都释放掉
if (__cache_shrink(cachep)) {
//如果当前cache中还有被分配对象，返回
slab_error(cachep, "Can't free all objects");
down(&cache_chain_sem);
//重新加入链表
list_add(&cachep->next,&cache_chain);
up(&cache_chain_sem);
unlock_cpu_hotplug();
return 1;
}
if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU))
synchronize_kernel();
//释放掉AC
for (i = 0; i < NR_CPUS; i++)
kfree(cachep->array[i]);
//释放掉share
kfree(cachep->lists.shared);
cachep->lists.shared = NULL;
//将cache描述符也释放掉
kmem_cache_free(&cache_cache, cachep);
unlock_cpu_hotplug();
return 0;
}
接着看_cache_shrink()：
static int __cache_shrink(kmem_cache_t *cachep)
{
struct slab *slabp;
int ret;
//将AC share中的对象全都释放给slab.我们在前面的代码中看到，释放对象时，先将对象释放到
//AC中，如果AC满了，再释放到share中，若是share满了，才会释放到slab.当cache要销毁的时候，//这些缓冲中的对象用不着了，先释放到slab中，再把整个slab释放掉
drain_cpu_caches(cachep);
check_irq_on();
spin_lock_irq(&cachep->spinlock);
//将slabs_free中的slab全被释放掉
for(;;) {
struct list_head *p;
p = cachep->lists.slabs_free.prev;
if (p == &cachep->lists.slabs_free)
break;
slabp = list_entry(cachep->lists.slabs_free.prev, struct slab, list);
#if DEBUG
if (slabp->inuse)
BUG();
#endif
list_del(&slabp->list);
cachep->lists.free_objects -= cachep->num;
spin_unlock_irq(&cachep->spinlock);
//这函数我们在前面已经分析过了的
slab_destroy(cachep, slabp);
spin_lock_irq(&cachep->spinlock);
}
//如果cachep->lists.slabs_ful和slabs_partial还有对象，说明cache中还被分配的对象，
ret = !list_empty(&cachep->lists.slabs_full) ||
!list_empty(&cachep->lists.slabs_partial);
spin_unlock_irq(&cachep->spinlock);
return ret;
}
九：几点补充：
1: Slab中使用的页面都会加上“PG_slab”标志，以跟一般的页面区别。另外，在释放内存的时候，经常需要用到从页面到slab的对应转换关系。那是怎样标识的呢？
关于标志：
注意有以下代码：
static void *kmem_getpages(kmem_cache_t *cachep, int flags, int nodeid)
{
……
while (i--) {
//为分得的每一个页面设置PG_slab标志
SetPageSlab(page);
page++;
}
……
}
关于从页面到slab的转换：
向伙伴系统请求内存
static int cache_grow (kmem_cache_t * cachep, int flags)
{
……
//请求内存过后，设置内存属性
set_slab_attr(cachep, slabp, objp);
……
}
static void set_slab_attr(kmem_cache_t *cachep, struct slab *slabp, void *objp)
{
int i;
struct page *page;
//计算页面总数
i = 1 << cachep->gfporder;
//虚拟地址转换成相应页面
page = virt_to_page(objp);
do {
// #define SET_PAGE_CACHE(pg,x) ((pg)->lru.next = (struct list_head *)(x))
SET_PAGE_CACHE(page, cachep);
#define SET_PAGE_SLAB(pg,x) ((pg)->lru.prev = (struct list_head *)(x))
SET_PAGE_SLAB(page, slabp);
page++;
} while (--i);
}
从上面的函数可以看出，pg->lru.next指向它所在的cache pg->lru.prev指向它所在slab
在代码中，用slabp = GET_PAGE_SLAB(virt_to_page(objp))来计算对象所在的slab
GET_PAGE_SLAB定义如下：
#define GET_PAGE_SLAB(pg) ((struct slab *)(pg)->lru.prev)
所以，只要直接取pg的lru.prev即可。
Slab的这部份设计很高效，很巧妙
2:在上述代码中，经常用到slab_bufctl的操作，下面就来详细分析一下：
先来看下cache中的slab大小的计算。即cache的slab_size字段：
kmem_cache_t * kmem_cache_create (const char *name, size_t size, size_t align,
unsigned long flags, void (*ctor)(void*, kmem_cache_t *, unsigned long),
void (*dtor)(void*, kmem_cache_t *, unsigned long))
{
……
slab_size = ALIGN(cachep->num*sizeof(kmem_bufctl_t) + sizeof(struct slab), align);
……
}
Cachep->num:slab中的object个数
从上面可以看到，slab_size已经包括了num个kmem_bufctl_t大小，也可以理解成有num个元素的kmem_bufctl_t数组。实际上kmem_bufctl_t又被定义为：unsigned short
typedef unsigned short kmem_bufctl_t;
slab_bufctl（）用来计算kmem_bufctl_t数组的首地址。代码如下：
static inline kmem_bufctl_t *slab_bufctl(struct slab *slabp)
{
return (kmem_bufctl_t *)(slabp+1);
}
我们接着看一下，kmem_bufctl_t数组如何被初始化。初始化是在新增一个slab 的时候，看下相应的代码：
static int cache_grow (kmem_cache_t * cachep, int flags)
{
…
cache_init_objs(cachep, slabp, ctor_flags);
….
}
在对每个对象初始化的时候：
static void cache_init_objs (kmem_cache_t * cachep,
struct slab * slabp, unsigned long ctor_flags)
{
int i;
//i为页面在slab中的序号
for (i = 0; i < cachep->num; i++) {
void* objp = slabp->s_mem+cachep->objsize*i;
……
……
slab_bufctl(slabp)[i] = i+1;
}
slab_bufctl(slabp)[i-1] = BUFCTL_END;
slabp->free = 0;
}
初始化之后，kmem_bufctl_t数组中的值如下图所示：
从上面的分析可以看到，slab中的free字段与kmem_bufctl_t数组中的值会错开一个值。
再来看从slab中分配对象的时候：
static void* cache_alloc_refill(kmem_cache_t* cachep, int flags)
{
while (slabp->inuse < cachep->num && batchcount--) {
……
//取当前free值
ac_entry(ac)[ac->avail++] = slabp->s_mem + slabp->free*cachep->objsize;
slabp->inuse++;
//使free指向下一项.下一项的值即为数组中的free项
next = slab_bufctl(slabp)[slabp->free];
slabp->free = next;
}
……
}
释放对像的时候：
static void free_block(kmem_cache_t *cachep, void **objpp, int nr_objects)
{
……
slab_bufctl(slabp)[objnr] = slabp->free;
slabp->free = objnr;
……
}
结合上面的初始化可以看到，有这样的一个规律：
kmem_bufctl_t数组中的slabp->free项的值就是下一个空闲对像的序号。结合这一样就能很好的理解这一部份代码了
十：kmalloc()/kfree()的实现
Kmalloc/kfree的实现其实跟上面是所讨论的是一样的，所不同的是。上面讨论的是属于专用cache，这里所讨论的普通cache.也可以这样说：专用cache是从数据结构方面来管理内存的。普通cache是以大小来管理的。
我们在前面曾讨论过，slab分配器按大32*(2^0),32*(2^1),32*(2^2) ….32*(2^12)大小，共划分了13个区域。Kmalloc()根据所申请的数据大小，选择合适的cache分配内存
代码如下示：
void * __kmalloc (size_t size, int flags)
{
struct cache_sizes *csizep = malloc_sizes;
//取得相应大小的普通cache
for (; csizep->cs_size; csizep++) {
if (size > csizep->cs_size)
continue;
#if DEBUG
/* This happens if someone tries to call
* kmem_cache_create(), or kmalloc(), before
* the generic caches are initialized.
*/
BUG_ON(csizep->cs_cachep == NULL);
#endif
//按请求内类型从不同的cache中分配内存
//__cache_alloc这函数我们在上面已经详细的分析过了
return __cache_alloc(flags & GFP_DMA ?
csizep->cs_dmacachep : csizep->cs_cachep, flags);
}
return NULL;
}
Kfree的实现代码：
void kfree (const void *objp)
{
kmem_cache_t *c;
unsigned long flags;
if (!objp)
return;
local_irq_save(flags);
kfree_debugcheck(objp);
//取得对象所对应的CACHE
c = GET_PAGE_CACHE(virt_to_page(objp));
//从cache中释放object
//__cache_free这函数我们在前面已经分析过了
__cache_free(c, (void*)objp);
local_irq_restore(flags);
}
