slab分配器学习系列之linux2.6

前言

前文通过存储桶了解了 slab 分配器最简单的实现方式，在后续的 linux 版本中，slab 分配器被正式提出，并用于解决内核中小样本分配问题。笔者打算先从 2.6.18 入手进行 slab 分配器的学习

主要参考资料为 《深入Linux内核架构》

slab 分配器

物理页并不是内存管理的最小单位，为了减少内部碎片，提出了 slab 分配机制。该机制其实是内存桶的复杂版，主要入口函数为 kmalloc 。其核心思想与内存桶类似，即在物理页上进一步划分连续的相同大小对象，并对此进行管理。在此使用 《简说Linux之slab机制》 做的图，能够很好地说明slab层的设计思想

即，cache_chain 关联了多个不同大小的 kmem_cache，每个 kmem_cache 关联一个 slabs ，slabs 由多个 slab 组成，每个 slab 又对应多个 page，每个 page 按照 kmem_cache 对应大小平分了多个 object 空间。实际上，slab 的实现与 linux 0.12 版本中 内存桶的思想较为类似。 《深入Linux内核架构》中也有相关图示，如下

• kmem_cache ：管理一整个结构。不同类型对象的 kmem_cache 不同，不同 size 也对应不同的 kmem_cache
• array_cache: 用于进行 slab 缓存。当需要分配对象时，先从缓存中找，找不到再去 slab 空闲链表中获取。不同 cpu 对应不同 array_cache。这么做属于本地缓存，避免了多核竞争需要上锁带来的消耗。
• slab链表：可以看到 kmem_cache 中涉及空闲、部分空闲、用尽三种类型的 slab 链表，其串联了相应的 slab 。要注意的是 slab 头部结构与 Obj 内容在同一页帧中

而每个 kmem_cache 又通过双向链表组织

主要数据结构

struct cache_sizes malloc_sizes[];
struct cache_sizes {
	size_t		 cs_size;
	kmem_cache_t	*cs_cachep;
	kmem_cache_t	*cs_dmacachep;
};
struct kmem_cache {

	struct array_cache *array[NR_CPUS];

	unsigned int batchcount;
	unsigned int limit;
	unsigned int shared;
	unsigned int buffer_size;
	struct kmem_list3 *nodelists[MAX_NUMNODES];
	gfp_t gfpflags;
	size_t colour;			
	unsigned int colour_off;	
	struct kmem_cache *slabp_cache;
	unsigned int slab_size;
	unsigned int dflags;		
	const char *name;
	struct list_head next;
	// 省略部分属性
};
struct kmem_list3 {
	struct list_head slabs_partial;	
	struct list_head slabs_full;
	struct list_head slabs_free;
	unsigned long free_objects;
	unsigned int free_limit;
	unsigned int colour_next;	
	spinlock_t list_lock;
	struct array_cache *shared;	
	struct array_cache **alien;	
	unsigned long next_reap;	
	int free_touched;		
};
struct array_cache {
	unsigned int avail;
	unsigned int limit;
	unsigned int batchcount;
	unsigned int touched;
	spinlock_t lock;
	void *entry[0];	
	unsigned int inuse;	
	kmem_bufctl_t free;
	unsigned short nodeid;
};

kmalloc (2.6.18)

slab分配器的分配入口为 kmalloc，其调用链如下

kmalloc
    --- __kmalloc ==> __do_kmalloc
    	--- __find_general_cachep ： 根据 size 和 flags, 从 malloc_sizes 中获取对应的 kmem_cache
    	--- __cache_alloc ==> ____cache_alloc ： 根据 kmem_cache 进行分配
    

____cache_alloc 函数中，首先通过 cpu_cache_get 获取到对应 kmem_cache 在当前 CPU 下的 array_cache。并判断是否为空，不为空直接获取 objp。否则要执行 cache_alloc_refill 从具体 slab 结构中获取。

具体地，array_cache 中的 entry 为指针数组，存放缓存 obj 的指针。跟踪 array_cache 的定义会发现，entry 被定义为 void *entry[0]。即这是一个长度为0的数组？实际上这是一个小知识点，该类型数组在 c语言中称为柔性数组，参考 《C语言柔性数组》，其只会出现在结构体最后一个属性，可以后续动态的为其申请不定长度的内存，进行使用。

static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)
{
	void *objp;
	struct array_cache *ac;

	check_irq_off();
	
	ac = cpu_cache_get(cachep);
	if (likely(ac->avail)) {
		STATS_INC_ALLOCHIT(cachep);
		ac->touched = 1;
		objp = ac->entry[--ac->avail];
	} else {
		STATS_INC_ALLOCMISS(cachep);
		objp = cache_alloc_refill(cachep, flags);
		
		ac = cpu_cache_get(cachep);
	}

	if (objp)
		kmemleak_erase(&ac->entry[ac->avail]);
	return objp;
}

简单地看下 cache_alloc_refill。大概就是先找到需要被分配的 slab，并将其上对象地址获取，放入缓存 array_cache 中，并返回

1. 首先通过 nodelist 获取关联了 slab 的链表（图3-45）
2. 从 slabs_partial 中试图获取空闲的 entry，如果能找到，那么得到对应的 slab。如果找不到，则调用 cache_grow 申请新的slab
3. 接着遍历 slab 上的 obj，通过 slab_get_obj 获取 slab 上空闲的obj 并将其加入 array_cache 中，具体需要添加多少个 obj 进入 array_cache 则由 batchcount 决定
4. 最后返回

意味着通过 cache_alloc_refill 将为 array_cache 一次性填充多个空闲的 obj

static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags)
{
	int batchcount;
	struct kmem_list3 *l3;
	struct array_cache *ac;
	int node;
	// 省略部分代码
	l3 = cachep->nodelists[node];
	// 省略部分代码
	while (batchcount > 0) {
		struct list_head *entry;
		struct slab *slabp;
		
		entry = l3->slabs_partial.next;
		if (entry == &l3->slabs_partial) {
			l3->free_touched = 1;
			entry = l3->slabs_free.next;
			if (entry == &l3->slabs_free)
				goto must_grow;
		}

		slabp = list_entry(entry, struct slab, list);
		check_slabp(cachep, slabp);
		check_spinlock_acquired(cachep);

		
		BUG_ON(slabp->inuse >= cachep->num);

		while (slabp->inuse < cachep->num && batchcount--) {
			STATS_INC_ALLOCED(cachep);
			STATS_INC_ACTIVE(cachep);
			STATS_SET_HIGH(cachep);

			ac->entry[ac->avail++] = slab_get_obj(cachep, slabp,
							    node);
		}
		check_slabp(cachep, slabp);

		
		list_del(&slabp->list);
		if (slabp->free == BUFCTL_END)
			list_add(&slabp->list, &l3->slabs_full);
		else
			list_add(&slabp->list, &l3->slabs_partial);
	}

must_grow:
	l3->free_objects -= ac->avail;
alloc_done:
	spin_unlock(&l3->list_lock);

	if (unlikely(!ac->avail)) {
		int x;
		x = cache_grow(cachep, flags | GFP_THISNODE, node, NULL);

		
		ac = cpu_cache_get(cachep);
		if (!x && ac->avail == 0)	
			return NULL;

		if (!ac->avail)		
			goto retry;
	}
	ac->touched = 1;
	return ac->entry[--ac->avail];
}

至此，slab分配过程基本清楚了。那么接下来的问题是，cachep 的 nodelists 上的 slab 是何时被初始化的？

kmem_cache_init

具体地，kmem_cache_init 会完成 kmem_cache 的初始化，主要作用是将不同大小的 kmem_cache 创建出来并关联到 malloc_sizes 上。要注意的是，在初始化的过程中， slab 并不会被提前创建。只有当申请 obj 发现 slab 不足时，才会调用 cache_grow 进行创建

具体地，在《深入Linux内核架构》中 3.6 节就有详细地解释。主要地，由于 kmem_cache 本身也需要通过 kmalloc 申请内存，因此会存在鸡生蛋还是蛋生鸡的问题，需要先手动创建一个 kmem_cache （静态分配），便于通过 kmalloc 创建 kmem_cache，名为 cache_cache。

1. 首先会对 cache_cache 初始化 nodelists 、array_cache (赋予 initarray_cache.cache )及一系列属性
2. 接着通过 kmem_cache_create ，利用初始化好的 cache_cache 创建 kmem_cache，并将其关联到 malloc_sizes 中，便于后续通过 size 可以进行索引
3. 由于第一步的 array_cache 也是静态分配的，需要将其替换成由 kmalloc 申请的地址，便于统一管理（4. Replace the bootstrap head arrays）
4. 通过 init_list 替换初始化好的 kmem_cache 的 nodelists

上述流程的后半部分，主要是将最开始通过静态分配初始化的 cache_cache 内容替换成由 kmalloc 申请的内容。以及 kmem_cache 中的 nodelist。最后所有结构都由 kmalloc 生成，便于管理

其英文注释写的很清楚

	
	if (num_physpages > (32 << 20) >> PAGE_SHIFT)
		slab_break_gfp_order = BREAK_GFP_ORDER_HI;
    
	
	INIT_LIST_HEAD(&cache_chain);
	list_add(&cache_cache.next, &cache_chain);
	cache_cache.colour_off = cache_line_size();
	cache_cache.array[smp_processor_id()] = &initarray_cache.cache;
	cache_cache.nodelists[numa_node_id()] = &initkmem_list3[CACHE_CACHE];

	cache_cache.buffer_size = ALIGN(cache_cache.buffer_size,
					cache_line_size());

	for (order = 0; order < MAX_ORDER; order++) {
		cache_estimate(order, cache_cache.buffer_size,
			cache_line_size(), 0, &left_over, &cache_cache.num);
		if (cache_cache.num)
			break;
	}
	BUG_ON(!cache_cache.num);
	cache_cache.gfporder = order;
	cache_cache.colour = left_over / cache_cache.colour_off;
	cache_cache.slab_size = ALIGN(cache_cache.num * sizeof(kmem_bufctl_t) +
				      sizeof(struct slab), cache_line_size());

	
	sizes = malloc_sizes;
	names = cache_names;

	

	sizes[INDEX_AC].cs_cachep = kmem_cache_create(names[INDEX_AC].name,
					sizes[INDEX_AC].cs_size,
					ARCH_KMALLOC_MINALIGN,
					ARCH_KMALLOC_FLAGS|SLAB_PANIC,
					NULL, NULL);

	if (INDEX_AC != INDEX_L3) {
		sizes[INDEX_L3].cs_cachep =
			kmem_cache_create(names[INDEX_L3].name,
				sizes[INDEX_L3].cs_size,
				ARCH_KMALLOC_MINALIGN,
				ARCH_KMALLOC_FLAGS|SLAB_PANIC,
				NULL, NULL);
	}

	slab_early_init = 0;

	while (sizes->cs_size != ULONG_MAX) {
		
		if (!sizes->cs_cachep) {
			sizes->cs_cachep = kmem_cache_create(names->name,
					sizes->cs_size,
					ARCH_KMALLOC_MINALIGN,
					ARCH_KMALLOC_FLAGS|SLAB_PANIC,
					NULL, NULL);
		}
		init_lock_keys(sizes);

		sizes->cs_dmacachep = kmem_cache_create(names->name_dma,
					sizes->cs_size,
					ARCH_KMALLOC_MINALIGN,
					ARCH_KMALLOC_FLAGS|SLAB_CACHE_DMA|
						SLAB_PANIC,
					NULL, NULL);
		sizes++;
		names++;
	}
	
	{
		struct array_cache *ptr;

		ptr = kmalloc(sizeof(struct arraycache_init), GFP_KERNEL);

		local_irq_disable();
		BUG_ON(cpu_cache_get(&cache_cache) != &initarray_cache.cache);
		memcpy(ptr, cpu_cache_get(&cache_cache),
		       sizeof(struct arraycache_init));
		
		spin_lock_init(&ptr->lock);

		cache_cache.array[smp_processor_id()] = ptr;
		local_irq_enable();

		ptr = kmalloc(sizeof(struct arraycache_init), GFP_KERNEL);

		local_irq_disable();
		BUG_ON(cpu_cache_get(malloc_sizes[INDEX_AC].cs_cachep)
		       != &initarray_generic.cache);
		memcpy(ptr, cpu_cache_get(malloc_sizes[INDEX_AC].cs_cachep),
		       sizeof(struct arraycache_init));
		
		spin_lock_init(&ptr->lock);

		malloc_sizes[INDEX_AC].cs_cachep->array[smp_processor_id()] =
		    ptr;
		local_irq_enable();
	}
	
	{
		int node;
		
		init_list(&cache_cache, &initkmem_list3[CACHE_CACHE],
			  numa_node_id());

		for_each_online_node(node) {
			init_list(malloc_sizes[INDEX_AC].cs_cachep,
				  &initkmem_list3[SIZE_AC + node], node);

			if (INDEX_AC != INDEX_L3) {
				init_list(malloc_sizes[INDEX_L3].cs_cachep,
					  &initkmem_list3[SIZE_L3 + node],
					  node);
			}
		}
	}

	
	{
		struct kmem_cache *cachep;
		mutex_lock(&cache_chain_mutex);
		list_for_each_entry(cachep, &cache_chain, next)
			enable_cpucache(cachep);
		mutex_unlock(&cache_chain_mutex);
	}

}

cache_grow

在分析 cache_grow 之前，需要对 slab 的布局有所了解，不然有些更新操作看得云里雾里

参考《深入Linux内核架构》3.6.3给出的 slab 结构图，如下所示

结合上述三幅图，可以知道，struct slab 指的是头部管理数据，在头部管理数据之后，为一个管理数组，每个位置存储了该位置对应的下一个 slab 对象的索引

因此，向 slab 申请 obj 的过程为

1. 获取 slab 结构体，从 slab->free 中获取当前空闲的 obj 对象索引
2. 通过简单地计算能够根据索引获得该 obj 对象的地址
3. 同时需要进入管理数组，获取 slab->free 位置对应的下一个 obj 对象地址，并设入 slab->free

具体地，函数入口为 slab_get_obj，slabp 为头部管理数据指针

1. 通过 index_to_obj 根据 slabp->free 获取到当前 slab 上的 obj 对应地址
2. 将 inuse 自增
3. 通过 slab_bufctl 获取到当前 slab 的管理数组【只需要 (int *)(slabp +1)即可】，并获取到 slabp->free 对应的下一个 obj 索引 next
4. 将 next 赋予 slabp->free

static inline void *index_to_obj(struct kmem_cache *cache, struct slab *slab,unsigned int idx)
{
	return slab->s_mem + cache->buffer_size * idx;
}
static void *slab_get_obj(struct kmem_cache *cachep, struct slab *slabp,int nodeid)
{
	void *objp = index_to_obj(cachep, slabp, slabp->free);
	kmem_bufctl_t next;

	slabp->inuse++;
	next = slab_bufctl(slabp)[slabp->free];
#if DEBUG
	slab_bufctl(slabp)[slabp->free] = BUFCTL_FREE;
	WARN_ON(slabp->nodeid != nodeid);
#endif
	slabp->free = next;

	return objp;
}

设置 obj 则是逆过程，slab_put_obj

static void slab_put_obj(struct kmem_cache *cachep, struct slab *slabp,
				void *objp, int nodeid)
{
	unsigned int objnr = obj_to_index(cachep, slabp, objp);

#if DEBUG
	
	WARN_ON(slabp->nodeid != nodeid);

	if (slab_bufctl(slabp)[objnr] + 1 <= SLAB_LIMIT + 1) {
		printk(KERN_ERR "slab: double free detected in cache "
				"'%s', objp %pn", cachep->name, objp);
		BUG();
	}
#endif
	slab_bufctl(slabp)[objnr] = slabp->free;
	slabp->free = objnr;
	slabp->inuse--;
}

了解了上述内容后，我们可以开始对 cache_grow 流程进行学习了，cache_grow 实现了对 slab 结构的扩容，因此必然涉及 slab 所在页 page 的申请，并需要在该 page 上初始化 slab 头部结构以及管理数组，最后还需要划分 n 个 obj 对象

对应地，cache_grow 的调用链如下

cache_grow
    --- kmem_getpages : 申请并返回空闲页 page 的地址
        --- alloc_pages_node
        --- page_address
    --- alloc_slabmgmt : 在 page 上初始化 slab 头部管理结构
    --- slab_map_pages :
    --- cache_init_objs :
    --- kmem_freepages :

alloc_slabmgmt

kmem_getpages 比较简单就不进行分析了。alloc_slabmgmt 主要通过 objp + colour_off 获得 slabp 的地址，也很好理解。objp 便是当前页起始地址

进而初始化 slabp 的一些属性（此时还没有初始化管理数组）

static struct slab *alloc_slabmgmt(struct kmem_cache *cachep, void *objp,
				   int colour_off, gfp_t local_flags,
				   int nodeid)
{
	struct slab *slabp;

	if (OFF_SLAB(cachep)) {
		
		slabp = kmem_cache_alloc_node(cachep->slabp_cache,
					      local_flags, nodeid);
		if (!slabp)
			return NULL;
	} else {
		slabp = objp + colour_off;
		colour_off += cachep->slab_size;
	}
	slabp->inuse = 0;
	slabp->colouroff = colour_off;
	slabp->s_mem = objp + colour_off;
	slabp->nodeid = nodeid;
	return slabp;
}

slab_map_pages

依次调用 page_set_cache 和 page_set_slab 将 cache 和 slab 绑定到 page 的 lru 上，意味着可以从 page 找到 slab ，不然只能从 slab 找到 page

static void slab_map_pages(struct kmem_cache *cache, struct slab *slab,void *addr)
{
	int nr_pages;
	struct page *page;

	page = virt_to_page(addr);

	nr_pages = 1;
	if (likely(!PageCompound(page)))
		nr_pages <<= cache->gfporder;

	do {
		page_set_cache(page, cache);
		page_set_slab(page, slab);
		page++;
	} while (--nr_pages);
}

cache_init_objs

该函数主要用于初始化管理数组，由 slab_bufctl(slabp)[i] = i + 1 可以见得，默认地，每个元素存放的其下一个 obj 索引为按顺序的后一个，并且最后结束的位置会存放 BUFCTL_END 作为标识

static void cache_init_objs(struct kmem_cache *cachep,
			    struct slab *slabp, unsigned long ctor_flags)
{
	int i;

	for (i = 0; i < cachep->num; i++) {
		void *objp = index_to_obj(cachep, slabp, i);
		slab_bufctl(slabp)[i] = i + 1;
	}
	slab_bufctl(slabp)[i - 1] = BUFCTL_END;
	slabp->free = 0;
}

可以见得，具体的 obj 对象并不需要初始化，只需要使用时通过索引算出地址即可拿来使用

至此，slab 分配器基本梳理完成。kmalloc 并没有指定 flag 为 GDP_HIGHMEM ，因此分配的是直接映射的普通内存区域

slab 分配器与存储桶的对比

进一步地，笔者对前文记录的存储桶和本文介绍的 slab 分配器进行对比，看看两者实现上有何不同

相同之处

分配流程本质上是一样的

存储桶：

1. 根据 size 查找桶目录 bucket_dir 找到对应 size 的桶描述符 bucket_desc
2. 遍历桶描述符链表，找到 freeptr 不为空的桶描述符 bucket_desc
3. 根据 freeptr 获取可用的空闲地址

slab 分配器：
4. 根据 size 查找 malloc_sizes 找到对应 size 的 kmem_cache
5. 遍历 kmem_cache-》slabs_partial(free)-》slabp 头部管理数据结构，找到可用的 slabp
6. 通过 slabp->free 定位到可用的空闲地址

两者都是懒惰初始化，即用到了才会申请内存进行初始化，具体地初始化方式却不同

不同之处 obj 组织形式

存储桶：

• 桶描述符 bucket_desc 中 freeptr 指向对应 page 中的地址
• obj 之间通过链表进行串联
  
  slab分配器:
• slabp 与 obj 在同一页内
• obj 之间没有链表串联，而是通过一个数组进行管理，数组记录了每个obj的下一个obj（其实也算链表了）
• 加入了颜色空间，着色，解决 cacheline 伪共享问题
  
  slab 的组织形式看上去更紧凑一些，但具体有什么好处呢？笔者不太清楚

缓存

存储桶：

• bucket_dir 直接就到 bucket_desc 了，然后就进行 obj 的分配

slab：

• malloc_sizes 之后，获取到kmem_cache，还要先考虑本地缓存 array_cache，才到 slabp
• 这部分的优化是必须的，因为分配的流程较长，会影响速度

由于组织方式的不同，初始化及分配的方式都会有差异，在此不进行对比