在Linux中,伙伴系统(buddy system)是以页为单位管理和分配内存。但是现实的需求却以字节为单位,假如我们需要申请20Bytes,总不能分配一页吧!那岂不是严重浪费内存。那么该如何分配呢?slab分配器就应运而生了,专为小内存分配而生。slab分配器分配内存以Byte为单位。但是slab分配器并没有脱离伙伴系统,而是基于伙伴系统分配的大内存进一步细分成小内存分配。
说明:slub是slab中的一种,slab也是slab中的一种。有时候用slab来统称slab, slub和slob。slab, slub和slob仅仅是分配内存策略不同。本篇文章中说的是slub分配器工作的原理。但是针对分配器管理的内存,下文统称为slab缓存池。所以文章中slub和slab会混用,表示同一个意思。
slub的数据结构相对于slab来说要简单很多。并且对外接口和slab兼容。所以说,从slab的系统更换到slub,可以说是易如反掌。
现在假如从伙伴系统分配一页内存供slub分配器管理。对于slub分配器来说,就是将这段连续内存平均分成若干大小相等的object(对象)进行管理。可是我们总得知道每一个object的size吧!管理的内存页数也是需要知道的吧!不然怎么知道如何分配呢!因此需要一个数据结构管理。那就是struct kmem_cache。kmem_cache数据结构描述如下:
struct kmem_cache {
struct kmem_cache_cpu __percpu *cpu_slab;
/* Used for retriving partial slabs etc */
slab_flags_t flags;
unsignedlong min_partial;
int size;/* The size of an object including meta data */
int object_size;/* The size of an object without meta data */
int offset;/* Free pointer offset. */
#ifdef CONFIG_SLUB_CPU_PARTIAL
int cpu_partial;/* Number of per cpu partial objects to keep around */
#endif
struct kmem_cache_order_objects oo;
/* Allocation and freeing of slabs */
struct kmem_cache_order_objects max;
struct kmem_cache_order_objects min;
gfp_t allocflags;/* gfp flags to use on each alloc */
int refcount;/* Refcount for slab cache destroy */
void(*ctor)(void*);
int inuse;/* Offset to metadata */
int align;/* Alignment */
int reserved;/* Reserved bytes at the end of slabs */
constchar*name;/* Name (only for display!) */
structlist_head list;/* List of slab caches */
struct kmem_cache_node *node[MAX_NUMNODES];
};
struct kmem_cache_cpu是对本地内存缓存池的描述,每一个cpu对应一个结构体。其数据结构如下:
struct kmem_cache_cpu {
void**freelist;/* Pointer to next available object */
unsignedlong tid;/* Globally unique transaction id */
struct page *page;/* The slab from which we are allocating */
#ifdef CONFIG_SLUB_CPU_PARTIAL
struct page *partial;/* Partially allocated frozen slabs */
#endif
};
了解了基本的数据结构,再来看看slub提供的API。如果你了解slub,我想这几个接口你是再熟悉不过了。
struct kmem_cache *kmem_cache_create(constchar*name,
size_t size,
size_t align,
unsignedlong flags,
void(*ctor)(void*));
void kmem_cache_destroy(struct kmem_cache *);
void*kmem_cache_alloc(struct kmem_cache *cachep,int flags);
void kmem_cache_free(struct kmem_cache *cachep,void*objp);
slab分配器提供的接口该如何使用呢?其实很简单,总结分成以下几个步骤:
再来一段demo示例代码就更好了。
/*
* This is a demo for how to use kmem_cache_create
*/
void slab_demo(void)
{
struct kmem_cache *kmem_cache_16 = kmem_cache_create("kmem_cache_16",16,
8, ARCH_KMALLOC_FLAGS,
NULL);
/* now you can alloc memory, the buf points to 16 bytes of memory*/
char*buf = kmeme_cache_alloc(kmem_cache_16, GFP_KERNEL);
/*
* do something what you what, don't forget to release the memory after use
*/
kmem_cache_free(kmem_cache_16, buf);
kmem_cache_destroy(kmem_cache_16);
}
什么是slab缓存池呢?我的解释是使用struct kmem_cache结构描述的一段内存就称作一个slab缓存池。一个slab缓存池就像是一箱牛奶,一箱牛奶中有很多瓶牛奶,每瓶牛奶就是一个object。分配内存的时候,就相当于从牛奶箱中拿一瓶。总有拿完的一天。当箱子空的时候,你就需要去超市再买一箱回来。超市就相当于partial链表,超市存储着很多箱牛奶。如果超市也卖完了,自然就要从厂家进货,然后出售给你。厂家就相当于伙伴系统。
说了这么多终于要抛出辛辛苦苦画的美图了。
好了,后面说的大部分内容请看这张图。足以表明数据结构之间的关系了。看懂了这张图,就可以理清数据结构之间的关系了。
在图片的左上角就是一个slub缓存池中object的分布以及数据结构和kmem_cache之间的关系。首先一个slab缓存池包含的页数是由oo决定的。oo拆分为两部分,低16位代表一个slab缓存池中object的数量,高16位代表包含的页数。使用kmem_cache_create()接口创建kmem_cache的时候需要指出obj的size和对齐align。也就是传入的参数。kmem_cache_create()主要是就是填充kmem_cache结构体成员。既然从伙伴系统得到(2^(oo >> 16)) pages大小内存,按照size大小进行平分。一般来说都不会整除,因此剩下的就是图中灰色所示。由于每一个object的大小至少8字节,当然可以用来存储下一个object的首地址。就像图中所示的,形成单链表。图中所示下个obj地址存放的位置位于每个obj首地址处,在内核中称作指针内置式。同时,下个obj地址存放的位置和obj首地址之间的偏移存储在kmem_cache的offset成员。两外一种方式是指针外置式,即下个obj的首地址存储的位置位于obj尾部,也就是在obj尾部再分配sizeof(void *)字节大小的内存。对于外置式则offset就等于kmem_cache的inuse成员。
针对每一个cpu都会分配一个struct kmem_cacche_cpu的结构体。可以称作是本地缓存池。当内存申请的时候,优先从本地cpu缓存池申请。在分配初期,本地缓存池为空,自然要从伙伴系统分配一定页数的内存。内核会为每一个物理页帧创建一个struct page的结构体。kmem_cacche_cpu中page就会指向正在使用的slab的页帧。freelist成员指向第一个可用内存obj首地址。处于正在使用的slab的struct page结构体中的freelist会置成NULL,因为没有其他地方使用。struct page结构体中inuse代表已经使用的obj数量。这地方有个很有意思的地方,在刚从伙伴系统分配的slab的 inuse在分配初期就置成obj的总数,在分配obj的时候并不会改变。你是不是觉得很奇怪,既然表示已经使用obj的数量,为什么一直是obj的总数呢?你想想,slab中的对象总有分配完的时候,那个时候就直接脱离kmem_cache_cpu了。此时的inuse不就名副其实了嘛!对于full slab就像图的右下角,就像无人看管的孩子,没有任何链表来管理。
当图中右下角full slab释放obj的时候,首先就会将slab挂入per cpu partial链表管理。通过struct page中next成员形成单链表。per cpu partial链表指向的第一个page中会存放一些特殊的数据。例如:pobjects存储着per cpu partial链表中所有slab可供分配obj的总数,如图所示。当然还有一个图中没有体现的pages成员存储per cpu partial链表中所有slab缓存池的个数。pobjects到底有什么用呢?我们从full slab中释放一个obj就添加到per cpu partial链表,总不能无限制的添加吧!因此,每次添加的时候都会判断当前的pobjects是否大于kmem_cache的cpu_partial成员,如果大于,那么就会将此时per cpu partial链表中所有的slab移送到kmem_cache_node的partial链表,然后再将刚刚释放obj的slab插入到per cpu partial链表。如果不大于,则更新pobjects和pages成员,并将slab插入到per cpu partial链表。
per node partia链表类似per cpu partial,区别是node中的slab是所有cpu共享的,而per cpu是每个cpu独占的。假如现在的slab布局如上图所示。假如现在如红色箭头指向的obj将会释放,那么就是一个empty slab,此时判断kmem_cache_node的nr_partial是否大于kmem_cache的min_partial,如果大于则会释放该slab的内存。
当调用kmem_cache_alloc()分配内存的时候,我们可以从正在使用slab分配,也可以从per cpu partial分配,同样还可以从per node partial分配,那么分配的顺序是什么呢?我们可以用下图表示。
首先从cpu 本地缓存池分配,如果freelist不存在,就会转向per cpu partial分配,如果per cpu partial也没有可用对象,继续查看per node partial,如果很不幸也不没有可用对象的话,就只能从伙伴系统分配一个slab了,并挂入per cpu freelist。我们详细看一下这几种情况。
我们可以通过kmem_cache_free()接口释放申请的obj对象。释放对象的流程如下图所示。
如果释放的obj就是属于正在使用cpu上的slab,那么直接释放即可,非常简单;如果不是的话,首先判断所属slub是不是full状态,因为full slab是没妈的孩子,释放之后就变成partial empty,急需要找个链表领养啊!这个妈就是per cpu partial链表。如果per cpu partial链表管理的所有slab的free object数量超过kmem_cache的cpu_partial成员的话,就需要将per cpu partial链表管理的所有slab移动到per node partial链表管理;如果不是full slab的话,继续判断释放当前obj后的slab是否是empty slab,如果是empty slab,那么在满足kmem_cache_node的nr_partial大于kmem_cache的min_partial的情况下,则会释放该slab的内存。其他情况就直接释放即可。
了,说了这么多,估计你会感觉slab好像跟我们没什么关系。如果作为一个驱动开发者,是不是感觉自己写的driver从来没有使用过这些接口呢?其实我们经常使用,只不过隐藏在kmalloc的面具之下。
kmalloc的内存分配就是基于slab分配器,在系统启动初期调用create_kmalloc_caches ()创建多个管理不同大小对象的kmem_cache,例如:8B、16B、32B、64B、…、64MB等大小。当然默认配置情况下,系统系统启动之后创建的最大size的kmem_cache是kmalloc-8192。因此,通过slab接口分配的最大内存是8192 bytes。那么通过kmalloc接口申请的内存大于8192 bytes该怎么办呢?其实kmalloc会判断申请的内存是否大于8192 bytes,如果大于的话就会通过alloc_pages接口申请内存。kmem_cache的名称以及大小使用struct kmalloc_info_struct管理。所有管理不同大小对象的kmem_cache的名称如下:
conststruct kmalloc_info_struct kmalloc_info[] __initconst ={
{NULL,0},{"kmalloc-96",96},
{"kmalloc-192",192},{"kmalloc-8",8},
{"kmalloc-16",16},{"kmalloc-32",32},
{"kmalloc-64",64},{"kmalloc-128",128},
{"kmalloc-256",256},{"kmalloc-512",512},
{"kmalloc-1024",1024},{"kmalloc-2048",2048},
{"kmalloc-4096",4096},{"kmalloc-8192",8192},
{"kmalloc-16384",16384},{"kmalloc-32768",32768},
{"kmalloc-65536",65536},{"kmalloc-131072",131072},
{"kmalloc-262144",262144},{"kmalloc-524288",524288},
{"kmalloc-1048576",1048576},{"kmalloc-2097152",2097152},
{"kmalloc-4194304",4194304},{"kmalloc-8388608",8388608},
{"kmalloc-16777216",16777216},{"kmalloc-33554432",33554432},
{"kmalloc-67108864",67108864}
};
经过create_kmalloc_caches ()函数之后,系统通过create_kmalloc_cache()创建以上不同size的kmem_cache,并将这些kmem_cache存储在kmalloc_caches全局变量中以备后续kmalloc分配内存。现在假如通过kmalloc(17, GFP_KERNEL)申请内存,系统会从名称“kmalloc-32”管理的slab缓存池中分配一个对象。即使浪费了15Byte。
我们来看看kmalloc的实现方式。
static __always_inline void*kmalloc(size_t size,gfp_t flags)
{
if(__builtin_constant_p(size)){
if(size > KMALLOC_MAX_CACHE_SIZE)
return kmalloc_large(size, flags);
if(!(flags & GFP_DMA)){
int index = kmalloc_index(size);
if(!index)
return ZERO_SIZE_PTR;
return kmem_cache_alloc_trace(kmalloc_caches[index], flags, size);
}
}
return __kmalloc(size, flags);
}
我们再看一下kmalloc_index的实现。
static __always_inline int kmalloc_index(size_t size)
{
if(!size)
return0;
if(size <= KMALLOC_MIN_SIZE)
return KMALLOC_SHIFT_LOW;
if(KMALLOC_MIN_SIZE <=32&& size >64&& size <=96)
return1;
if(KMALLOC_MIN_SIZE <=64&& size >128&& size <=192)
return2;
if(size <=8)return3;
if(size <=16)return4;
if(size <=32)return5;
if(size <=64)return6;
if(size <=128)return7;
if(size <=256)return8;
if(size <=512)return9;
if(size <=1024)return10;
if(size <=2*1024)return11;
if(size <=4*1024)return12;
if(size <=8*1024)return13;
if(size <=16*1024)return14;
if(size <=32*1024)return15;
if(size <=64*1024)return16;
if(size <=128*1024)return17;
if(size <=256*1024)return18;
if(size <=512*1024)return19;
if(size <=1024*1024)return20;
if(size <=2*1024*1024)return21;
if(size <=4*1024*1024)return22;
if(size <=8*1024*1024)return23;
if(size <=16*1024*1024)return24;
if(size <=32*1024*1024)return25;
if(size <=64*1024*1024)return26;
/* Will never be reached. Needed because the compiler may complain */
return-1;
}