本文转载自微信公众号《Linux内核那些事儿》，作者songsong001。转载本文请联系Linux内核那些事儿公众号。由于本文写得较早，当时使用的是Linux-2.4.16内核，但不影响整体源码分析。上一节提到的SLAB分配算法，Linux内核使用buddy系统算法来管理内存页，但是buddy系统算法分配的单位是一个内存页，即至少要有一个或多个内存块分配。但是很多时候我们并不需要分配一个内存页，比如当我们要申请一个大小为200字节的结构体时，如果我们使用伙伴系统分配算法至少申请一个内存页，但是只使用了200字节的内存，那么剩下的3896字节就被浪费掉了。为了解决小块内存申请问题，Linux内核引入了SLAB分配算法。Linux所使用的SLAB分配算法基于JeffBonwick首先为SunOS操作系统引入的算法。在内核中，大量内存分配给一组有限的对象，例如文件描述符和其他公共结构。Jeff发现在内核中初始化公共对象比分配和释放它们花费的时间更多。所以他的结论是内存不应该被释放回全局内存池，而应该保持在目的初始化状态。为了更好的理解SLAB分配算法，我们先来介绍一下该算法使用的数据结构。相关数据结构SLAB分配算法有两个重要的数据结构，一个是kmem_cache_t，一个是slab_t。先来看看kmem_cache_t结构:structkmem_cache_s{/*1)eachalloc&free*//*full,partialfirst,thenfree*/structlist_headslabs_full;structlist_headslabs_partial;structlist_headslabs_free;unsignedintobjsize;unsignedintflags;/*constantflags*/unsignedintnum;/*#ofpinjslock;#ifdefCONFIG_SMPunsignedintbatchcount;#endif/*2)slabadditions/removals*//*orderofpgsperslab(2^n)*/unsignedintgfporder;/*forceGFPflags,e.g.GFP_DMA*/unsignedintgfpflags;size_tcolour;/*cachecolouringrange*/unsignedintcolour_off;/*colournext*/unsignedintgfporder;/*colournext*/unsignedintcolour;/*cachecolouring*/kmem_cache_t*slabp_cache;unsignedintgrowing;unsignedintdflags;/*dynamicflags*//*constructorfunc*/void(*ctor)(void*,kmem_cache_t*,unsignedlong);/*de-constructorfunc*/void(*dtor)(void*,kmem_cache_t*,unsignedlong);unsignedlongfailures;/*3)cachecreation/removal*/charname[CACHE_NAMELEN];structlist_headnext;...};下面介绍一下kmem_cache_t结构中比较重要的字段：slab_full:fullyallocatedslabslab_partial:partiallyallocatedslabslab_free:unallocatedslabobjsize:storedobjectsizenum:一个slab可以存储的对象个数gfporder:一个slab由2gfporder内存页组成颜色/colour_off/colour_next：着色区域的大小（后面会讲到）slab_t结构定义如下：slab_t;slab_t结构体各字段作用如下：list：连接（full/partial/empty）chaincolouroff：着色补偿s_mem：存储对象的起始内存地址inuse：分配了多少Objectsfree：已使用将空闲对象用图连接起来，表示它们之间的关系，如下：SLAB分配算法初始化t的初始化SLAB分配算法由kmem_cache_init()函数完成，如下：if(!cache_cache.num)BUG();cache_cache.colour=left_over/cache_cache.colour_off;cache_cache.colour_next=0;}这个函数主要用来初始化变量cache_cache，cache_cache是??kmem_cache_t的一种的结构体变量，定义如下：statickmem_cache_tcache_cache={slabs_full:LIST_HEAD_INIT(cache_cache.slabs_full),slabs_partial:LIST_HEAD_INIT(cache_cache.slabs_partial),slabs_free:LIST_HEAD_INIT(cache_cache.slabs_free),objsize:sizeof(kmem_cache_t),flags:SLAB_NO_REAP,spinlock:SPIN_LOCK_UNLOCKED,colour_off:L1_CACHE_BYTES,name:"kmem_cache",};为什么我们需要这样一个对象？因为kmem_cache_t结构本身也是一个小内存对象，所以应该有一个slab分配器来分配它，但是这样会出现“egg”系统初始化的时候，slab分配器还没有初始化，所以slab分配器不能使用分配一个kmem_cache_t对象，此时只能通过定义一个kmem_cache_t类型的静态变量来管理slab分配器，所以使用cache_cache静态变量来管理slab分配器。从上面的代码可以看出，cache_cache的objsize字段设置为sizeof(kmem_cache_t)的大小，所以这个对象主要用来分配不同类型的kmem_cache_t对象，kmem_cache_init()函数调用kmem_cache_estimate()函数计算有多少个大小为cache_cache的对象.objsize一个slab可以保存，保存在cache_cache.num字段中，不可能分配一个slab中的所有对象，例如：一个slab大小为4096字节的slab来分配对象大小为22字节。可以分成186个对象，但是还有4个字节不能用，所以这部分内存被用作着色区域。着色区的作用是将不同的slab错开，让CPU更有效的缓存slab。当然这属于优化部分，对slab分配算法影响不大。也就是说，即使不对slab进行着色操作，slab分配算法仍然可以工作。kmem_cache_t的kmem_cache_t对象申请是用来管理和分配对象的，所以在使用slaballocator时，必须先申请一个kmem_cache_t对象，通过kmem_cache_create()函数申请kmem_cache_t对象：kmem_cache_t*kmem_cache_create(constchar*name,size_tsize,size_toffset,unsignedlongflags,void(*ctor)(void*,kmem_cache_t*,unsignedlong),void(*dtor)(void*,kmem_cache_t*,unsignedlong)){constchar*func_nm=KERN_ERR"kmem_create:";size_tleft_over,align,slab_size;kmem_cache_t*cachep=NULL;...cachep=(kmem_cache_t*)kmem_cache_alloc(&cache_cache,SLAB_KERNEL);if(!cachep)gotoopps;memset(cachep,0,sizeof(kmem_cache_t));...do{unsignedintbreak_flag=0;cal_wastage:kmem_cache_estimate(cachep->gfporder,size,flags,&left_over,&cachep->num);if(break_flag)break;if(cachep->gfporder>=MAX_GFP_ORDER)break;if(!cachep->num)gotonext;if(flags&CFLGS_OFF_SLAB&&cachep->num>offslab_limit){cachep->gfporder--;break_flag++;gotocal_wastage;}if(cachep->gfporder>=slab_break_gfp_order)break;if((left_over*8)<=(PAGE_SIZE<gfporder))break;/*Acceptableinternalfragmentation.*/next:cachep->gfporder++;}while(1);if(!cachep->num){printk("kmem_cache_create:couldn'tcreatecache%s.\n",name);kmem_cache_free(&cache_cache,cachep);cachep=NULL;gotoopps;}slab_size=L1_CACHE_ALIGN(cachep->num*sizeof(kmem_bufctl_t)+sizeof(slab_t));if(flags&CFLGS_OFF_SLAB&&left_over>=slab_size){flags&=~CFLGS_OFF_SLAB;left_over-=slab_size;}offset+=(align-1);offset&=~(align-1);if(!offset)offset=L1_CACHE_BYTES;cachep->colour_off=offset;cachep->colour=left_over/offset;if(!cachep->gfporder&&!(flags&CFLGS_OFF_SLAB))flags|=CFLGS_OPTIMIZE;cachep->flags=flags;cachep->gfpflags=0;if(flags&SLAB_CACHE_DMA)cachep->gfpflags|=GFP_DMA;spin_lock_init(&cachep->spinlock);cachep->objsize=size;INIT_LIST_HEAD(&cachep->slabs_full);INIT_LIST_HEAD(&cachep->slabs_partial);INIT_LIST_HEAD(&cachep->slabs_free);if(flags&CFLGS_OFF_SLAB)cachep->slabp_cache=kmem_find_general_cachep(slab_size,0);cachep->ctor=ctor;cachep->dtor=dtor;strcpy(cachep->name,name);#ifdefCONFIG_SMPif(g_cpucache_up)enable_cpucache(cachep);#endifdown(&cache_chain_sem);{structlist_head*p;list_for_each(p,&cache_chain){kmem_cache_t*pc=list_entry(p,kmem_cache_t,next);if(!strcmp(pc->name,name))BUG();}}list_add(&cachep->next,&cache_chain);up(&cache_chain_sem);opps:returncachep;}kmem_cache_create()函数比较长，所以上面的代码去掉了一些不太重要的部分，让代码更清晰体现它的原理在kmem_cache_create()函数中，首先调用kmem_cache_alloc()函数申请一个kmem_cache_t对象，我们看到在调用kmem_cache_alloc()时，传入了cache_cache变量。申请完kmem_cache_t对象后，需要initialized，主要是初始化kmem_cache_t对象的所有字段：计算需要多少页作为t的大小他平板。计算一个slab可以分配多少个对象。计算着色器信息。初始化slab_full/slab_partial/slab_free列表。将请求的kmem_cache_t对象保存到cache_chain链表中。对象分配申请完kmem_cache_t对象后，使用kmem_cache_alloc()函数申请指定对象。kmem_cache_alloc()函数代码如下：staticinlinevoid*kmem_cache_alloc_one_tail(kmem_cache_t*cachep,slab_t*slabp){void*objp;...slabp->inuse++;objp=slabp->s_mem+slabp->free*cachep->objsize;slabp->free=slab_bufctl(slabp)[slabp->free];if(不太可能(slabp->free==BUFCTL_END)){list_del(&slabp->list);list_add(&slabp->list,&cachep->slabs_full);}returnobjp;}#definekmem_cache_alloc_one(cachep)\({\structlist_head*slabs_partial,*entry;\slab_t*slabp;\\slabs_partial=&(cachep)->slabs_partial;\entry=slabs_partial->next;\if(不太可能(entry==slabs_partial)){\structlist_head*slabs_free;\slabs_free=&(cachep)->slabs_free;\entry=slabs_free->next;\if(不太可能(entry==slabs_free))\gotoalloc_new_slab;\list_del(entry);\list_add(入口,slabs_partial);\}\slabp=list_entry(入口,slab_t,list);\kmem_cache_alloc_one_tail(cachep,slabp);\})staticinlinevoid*__kmem_cache_alloc(kmem_cache_t*cachep,intflags){unsignedlongsave_flags;void*objp；kmem_cache_alloc_head（cachep，标志）；try_again：local_irq_save（save_flags）；...objp=kmem_cache_alloc_one（cachep）；local_irq_restore（save_flags）；返回objp；alloc_new_slab：...local_irq_restore（save_flags），if（growem_cachep（cachep）))gototry_again;returnNULL;}void*kmem_cache_alloc(kmem_cache_t*cachep,intflags){return__kmem_cache_alloc(cachep,flags);}kmem_cache_alloc()函数是我扩展的。kmem_cache_alloc()函数的主要步骤是：从kmem_cache_t对象中查找slab_partial列表中是否有可用的slab，如果有则直接从slab中分配一个对象如果slab_partial列表中没有可用的slab，则从slab_free列表中搜索可用的slab，如果有可用的slab，则从slab中分配一个对象，并将此slab放入slab_partial列表中。如果slab_free列表中没有可用的slab，则调用kmem_cache_grow()函数申请新的slab进行对象分配。kmem_cache_grow()函数会调用__get_free_pages()函数申请内存页并初始化slab。一个slab的结构如下：灰色部分是彩色区域，绿色部分是slab管理结构，黄色部分是空闲对象列表的索引，红色部分是对象的实体。我们可以看到slab结构体的s_mem字段指向了对象实体列表的起始地址。分配对象时，首先通过slab结构的free域检查是否有可用的空闲对象。free字段存储自由对象链表的第一个节点索引。对象释放对象的释放比较简单，主要是调用kmem_cache_free()函数，而kmem_cache_free()函数最终会调用kmem_cache_free_one()函数，代码如下：staticinlinevoidkmem_cache_free_one(kmem_cache_t*cachep,void*objp){slab_t*slabp;CHECK_PAGE(virt_to_page(objp));slabp=GET_PAGE_SLAB(virt_to_page(objp));{unsignedintobjnr=(objp-slabp->s_mem)/cachep->objsize;slab_bufctl(slabp)[objnr]=slabp->free;slabp->free=objnr;}STATS_DEC_ACTIVE(cachep);{intinuse=slabp->inuse;if(不太可能(!--slabp->inuse)){list_del(&slabp->list);list_add(&slabp->list,&cachep->slabs_free);}elseif(unlikely(inuse==cachep->num)){list_del(&slabp->list);list_add(&slabp->list,&cachep->slabs_partial);}}}当释放对象，首先会把被释放对象的索引添加到slab的空闲对象链表中，然后根据slab的使用情况将slab移动到合适的链表中。如果slab中的所有对象都被释放，则将slab放入slab_free列表中。如果对象所在的slab原来在slab_full，那么把slab移到slab_partial。
