kernel hacker修炼之道之内存管理-SLAB(SLAB的基本数据结构)

kernel hacker修炼之道之内存管理-SLAB

作者：李万鹏 于北京 borqs

2011.9.13 21:15

本SLAB系列文章从几个方面讨论：

1. SLAB的基本数据结构

2. 创建SLAB高速缓存kmem_cache_create()

3. 销毁SLAB高速缓存kmem_cache_destroy()

4. 创建SLAB块cache_grow()

5. 撤销SLAB块cache_destroy()

6. 分配SLAB对象kmem_cache_alloc()

7. 释放SLAB对象kmem_cache_free()

8. SLAB系统的初始化代码

slab分配器基本原理：

slab最初是在Solaris 2.4中引入linux操作系统的，用于解决内碎片问题。程序经常需要创建一些数据结构，比如进程描述符task_struct，内存描述符mm_struct等。slab分配器把这些需要分配的小块内存区作为对象，类似面向对象的思想。每一类对象分配一个cache，cache有一个或多个slab组成，slab由一个或多个物理页面组成。需要分配对象的时候从slab中空闲的对象取，用完了再放回slab中，而不是释放给物理页分配器，这样下次用的时候就不用重新初始化了，实现了对象的复用。

struct kmem_cache_s {
/* 1) per-cpu data, touched during every alloc/free */
	struct array_cache	*array[NR_CPUS];
	unsigned int		batchcount;
	unsigned int		limit;
/* 2) touched by every alloc & free from the backend */
	struct kmem_list3	lists;
	/* NUMA: kmem_3list_t	*nodelists[MAX_NUMNODES] */
	unsigned int		objsize;
	unsigned int	 	flags;	/* constant flags */
	unsigned int		num;	/* # of objs per slab */
	unsigned int		free_limit; /* upper limit of objects in the lists */
	spinlock_t		spinlock;

/* 3) cache_grow/shrink */
	/* 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		slab_size;
	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);

/* 4) cache creation/removal */
	const char		*name;
	struct list_head	next;

/* 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;
	unsigned long		node_allocs;
	atomic_t		allochit;
	atomic_t		allocmiss;
	atomic_t		freehit;
	atomic_t		freemiss;
#endif
#if DEBUG
	int			dbghead;
	int			reallen;
#endif
};

如图，每一个cache用高速缓存描述符struct kmem_cache_t来描述，所有的cache链接在一个以cache_chain为链表头的链表上。其中ctor，dtor 分别是构造和析构函数，在调用cache_grow()分配slab块之后，会调用ctor为每个对象初始化，有点面向对象的思想。colour是颜色的粒度的最大值，colour_off是颜色粒度的单位，colour_next下一个被分配的slab使用的颜色。

struct kmem_list3 {
	struct list_head	slabs_partial;	/* partial list first, better asm code */
	struct list_head	slabs_full;
	struct list_head	slabs_free;
	unsigned long	free_objects;
	int		free_touched;
	unsigned long	next_reap;
	struct array_cache	*shared;
};

struct kmem_cache_t有一个叫做struct kmem_list3的字段，里边保存了一些链表头，有list3，也就是slabs_full(没有空闲对象)，slabs_partial(有部分空闲对象)，slabs_free(只包含空闲对象)。还有一个struct array_cache *share字段，指向一个共享本地高速缓存。

struct array_cache {
	unsigned int avail;        
	unsigned int limit;
	unsigned int batchcount;
	unsigned int touched;
};

struct kmem_cache_t的struct array_cache *array[NR_CPUS];字段指向了CPU的本地高速缓存。avail当前空闲对象的位置，limit是空闲对象的最大值。batchcount一次要填充给数组的对象数，或一次要释放的对象数。至于touched，如果本地高速缓存最近被使用过则touched置1。

<span style="font-size: 24px;">struct cache_sizes {
	size_t		 cs_size;
	kmem_cache_t	*cs_cachep;
	kmem_cache_t	*cs_dmacachep;
};</span>

这个是malloc_sizes表的类型，即普通高速缓存，cs_size指出了cache每次分配的内存区的大小，为32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072。这里一共13种几何分布的内存区，每种有两个高速缓存，一个用于ISA DMA分配，另一个适用于常规分配。

struct slab {
	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描述符了，所有的slab描述符连在头节点为slabs_full,slabs_partial,slabs_free的双向链表上，colouroff为第一个对象的偏移。s_mem是slab中第一个对象的地址。这里的kmem_bufctl_t是对象描述符，在i386体系中是unsigned short类型，占2个字节。free保存下一个空闲对象的下标。

普通和专用高速缓存：

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，存放在cache_cache变量中，它包含由内核其他部分使用的高速缓存的高速缓存描述符。上边说的那个叫malloc_sizes的表保存了指向这26个高速缓存的描述符。专用高速缓存使用kmem_cache_create()创建的，下一篇文档会专门介绍。

slab着色基本原理：

CPU访问内存时，会把一些经常访问的缓存到cache中。缓存到哪个cache line是靠低地址，所以即使距离很远的两块内存，只要低地址相同还是会被缓存到相同的cache line中，如下图。这样会经常造成cache miss，cache line被不停的换入，换出，导致cache颠簸。

如果在同一个cache的不同slab前加上不同的偏移，这样他们的低地址就不同了，可以被缓存在不同的cache line。

但是这样也存在问题，比如colour是3，那么第一个对象的偏移是0*32，第二个是1*32，第三个是2*32，可是第四个的时候又循环回来0*32，所以着色是有局限性的，当slab比较少的时候可以，比较多了着色就不起什么作用了，这是slab的缺陷之一。