2008年（27）
分类： LINUX
2008-06-07 12:20:51
七：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);
}
十一：总结：
Slab分配器中有很多值得仔细研读的代码。与2.4相比，2。6内核新增了两个缓冲结构，一个是AC，另一个是share。有效的缓减了对伙伴系统的压力
