SLAB分配器

2016-1-12 chenhui 内存管理

Linux 根据内存的访问速度把不同的内存按照节点进行分类,而一个节点的内存又通过内存管理区分成 DMA 内存和 NORMAL 内存,每个内存管理区又通过伙伴系统把自己的内存分为各种大小的内存块,伙伴系统的这些内存块大小不一,由一个或多个页框组成。一个页框的大小是 4K,这个大小是不可改变的,这就会导致一个问题,那就是如果我需要分配 10 个字节的内存,难道你也要给我一个页框(4K)吗?这很显然是不可能的,所以我们需要一种对页框再进行划分的内存管理方案,这就是 SLAB 分配器。


SLAB 分配器的基础理论就不多说了,本文只是简单粗暴地讲解 Linux 用来实现 SLAB 分配器的源代码。


在 start_kernel() 中,内核调用了 kmem_cache_init() 来初始化 slab 分配器。


void __init kmem_cache_init(void)    
{
	size_t left_over;
	struct cache_sizes *sizes;
	struct cache_names *names; 

	if (num_physpages > (32 << 20) >> PAGE_SHIFT)		
		//num_physpages是记录系统实际存在物理内存的总页框数
		//他大于32M才可以创建高阶指数内存页数的高速缓存内存对象。
		slab_break_gfp_order = BREAK_GFP_ORDER_HI;
		
	init_MUTEX(&cache_chain_sem);
	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.objsize = ALIGN(cache_cache.objsize, cache_line_size());
	cache_estimate(0, cache_cache.objsize, cache_line_size(), 
                 0,&left_over, &cache_cache.num);
	
	if (!cache_cache.num)
		//如果一页内存空间不可以保存任何一个内存对象,则系统崩溃。
		BUG();

	cache_cache.colour = left_over/cache_cache.colour_off;
	cache_cache.colour_next = 0;
	cache_cache.slab_size = 
		ALIGN(cache_cache.num*sizeof(kmem_bufctl_t) + sizeof(struct slab), 
			  cache_line_size());
	sizes = malloc_sizes;
	names = cache_names;

	while (sizes->cs_size) {

		sizes->cs_cachep = 
			kmem_cache_create(
					names->name,
					sizes->cs_size, 
					ARCH_KMALLOC_MINALIGN,	
					(ARCH_KMALLOC_FLAGS | SLAB_PANIC), 
					NULL, NULL);

		if (!(OFF_SLAB(sizes->cs_cachep))) {

			offslab_limit = sizes->cs_size-sizeof(struct slab);
			offslab_limit /= sizeof(kmem_bufctl_t);
		}

		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 cache_cache 和 struct cache_names。

struct cache_cache 的定义如下:



struct cache_sizes {

	size_t		 cs_size;
	kmem_cache_t	*cs_cachep; 
	kmem_cache_t	*cs_dmacachep;
};


cs_size:缓存的内存块的大小(就是下面这两个缓存对象的内存块的大小)

cs_cachep:kmalloc 使用的缓存对象

cs_dmacachep:kmalloc 分配 dma 内存时,使用的缓存对象。


slab 分配器是一种技术,而使用这种技术来进行分配内存的对象由 kmem_cache_t 来描述,kmem_cachet 又是 struct kmem_cache_s 的 typedef,也就是缓存对象,一个缓存对象可以分配多个内存块,这些内存块从页框里划分,他的大小是固定的,不可改变的。


那么这个 struct cache_size 又是干什么的?为什么他里面要有两个缓存对象?很简单,当然是用来分配内存的。内核里有一个 kmalloc 函数,他和用户空间的 malloc 很像,都是分配一段内存,但是我们说过,分配内存不能导致内存浪费,所以 kmalloc 会根据传入的内存块大小分配所需的内存块。 


那么 kmalloc 又是怎么实现不浪费内存的呢?实际上,内核预先申请了很多个缓存对象保存在一个数组里,他们的内存块大小从小到大都不一样,kmalloc 就是从这个数组里找到内存块刚好能满足申请者申请的内存大小的缓存对象,然后从这个缓存对象中取出一个内存块返回。当然,这个内存块大小有时候并不会刚好和找到的缓存对象的内存块大小一致,所以会造成极小的内存浪费,但这已经是最好的解决方案了。


这个 struct cache_sizes,就是用来描述那个数组的数组项的,那个数组的定义如下:


struct cache_sizes malloc_sizes[] = {
#define CACHE(x) { .cs_size = (x) }, 
#include <linux/kmalloc_sizes.h>
	{ 0, }
#undef CACHE
};


这里包含了 kmalloc_sizes.h 这个头文件,他的内容如下:



CACHE(32)
CACHE(64)
CACHE(96)
CACHE(128)
CACHE(192)
CACHE(256)
CACHE(512)
CACHE(1024)
CACHE(2048)
CACHE(4096)
CACHE(8192)
CACHE(16384)
CACHE(32768)
CACHE(65536)
CACHE(131072)
CACHE(262144)
CACHE(524288)
CACHE(1048576)
CACHE(2097152)
CACHE(4194304)


很明显,这里就是定义了一个 cache_sizes 数组,并初始化他们的大小。我们说过,kmalloc 需要很多不同内存块大小的缓存对象,他们的大小就是在这里初始化的。至于 struct cache_size 的两个缓存对象,就不在这里初始化,而是在 kmem_cache_init() 里初始化。


接下来再来看 struct cache_names,他是为了匹配上面说到的数组而生的,每个缓存对象都有一个名字,这个对象就是为不同大小的缓存对象提供名字。其定义如下:


struct cache_names {
	char *name;
	char *name_dma;   
};

static struct cache_names __initdata cache_names[] = {
#define CACHE(x) { .name = "size-" #x, .name_dma = "size-" #x "(DMA)" },
#include <linux/kmalloc_sizes.h>
	{ NULL, }
#undef CACHE
};


这里的套路和上面的是一样的,就是为 struct cache_size 对象的两个缓存对象提供一个名字而已。


最后,我们再来重新看 kmem_cache_init() 的那段代码。

12~13 行,所有的缓存对象都存放在一个链表里,并由一个信号量保护。这里初始化这个链表和信号量。

14 行,把 cache_cache 加入链表,这个 cache_cache 用来分配其他缓存对象,总不能让其他缓存对象都静态定义吧?。

15 行,色块大小,这个着色比较复杂,不说他。

17 行,这里的 objsize 就是缓存对象的内存块的大小,也就是 sizeof(kmem_cache_t),这里是让他对齐,为什么对齐?也是因为着色。

18 行,计算一个页框可容纳几个内存块,这里计算内存块时,包括了描述内存块的 struct slab 对象以及和内存块个数相等的 struct  kmem_bufctl_t 对象。最终保存在 num 字段。如果页框有剩余的内存空间,其大小保存在*left_over中

25~26 行,一个页框剩余的内存,会被色块使用,这里计算可存放的色块的个数,也是着色用的。

27 行,计算内存块的头部和内存块本身所占据的内存的大小。这里的头部,等到下面再讲。

30~31 行,这两个很熟悉了,就是 kmalloc 使用的那个数组。

33~56 行,经过之前的讲解,这段代码恐怕已经很简单了,就是初始化 kmalloc 使用的数组而已。


说白了,这段代码就是在初始化 cache_cache 和 kmalloc() 使用的 cache_size[]。


说明了这段代码,接下来的就是着色和内存块及其头部,关于这个着色,是一种防止处理器自带的硬件高速缓存里的缓存块频繁换入换出到内存的机制,感兴趣的可阅读 ARM 书籍的高速缓存章节(注意映射部分)并上网搜索相关资料,不感兴趣的也没关系,不妨碍对 slab 的理解,这里不多讲。下面仔细说说这个内存块和其头部。


缓存对象 kmem_cache_t 用来管理一些相同大小的内存块,但他不是直接管理内存块的,而是使用多个 struct slab 对象来管理内存块,一个 slab 对象可根据内存块的状态分为 全空闲,部分空闲,无空闲 三类,三类分别存放在缓存对象的三个链表中


下面来看看 struct slab 的定义:



struct slab {

	struct list_head	list; 
	unsigned long		colouroff; 
	void			*s_mem;	
	unsigned int		inuse;
	kmem_bufctl_t		free;
};


list :挂到缓存对象的链表中。

s_mem :一个 slab 对象管理多个内存块,这里保存的是第一个内存块的地址。

inuse:正在使用的内存块个数

free:slab中下一个空闲对象的下标。s_mem + (objsize * free) 就得到了下一个空闲对象的地址。


在 slab 对象的屁股后面跟随着一个 kmem_bufctl_t 数组,这个数组的长度和内存块个数一致,即和内存块对应。比如 [0] 保存了第一个内存块的下标(s_mem + 0 就能得到第一个内存块的地址),第 [4] 保存了第五个内存块的下标。

我们如果要想取 slab 中的一个内存块,需要按照这个算法来:s_mem + ( (slab + 1)[要取的内存块号]  * objsize)。slab + 1 是因为 kmem_bufctl_t 数组跟随在他后面,加一就能指向他的屁股后面了。


最后再来分析下 kmem_cache_alloc() 来分析下内存块的申请。



void * kmem_cache_alloc (kmem_cache_t *cachep, int flags)
{
	return __cache_alloc(cachep, flags);
}


cachep :要分配的缓存对象。

flags :一些标志,比如是否从 DMA 管理区分配。


static inline void * __cache_alloc (kmem_cache_t *cachep, int flags)
{
	unsigned long save_flags;
	void* objp;
	struct array_cache *ac;

	local_irq_save(save_flags);
	
	//取出当前CPU的本地高速缓存 
	ac = cachep->array[smp_processor_id()];

	if (likely(ac->avail)) {
		//如果avail>0说明当前处理器的高速缓存中有内存对象可以分配。
		//那么avail字段就包含最后被释放的对象的项在本地高速缓存中的下标。
		
		STATS_INC_ALLOCHIT(cachep);		
		ac->touched = 1;
		
		//从本地高速缓存中取出内存块
		objp = ((void**)(ac+1))[--ac->avail];
		
	} else {
		// 本地高速缓存中没有空闲对象,则从缓存对象中补充,然后再返回一个内存块。  
	
		STATS_INC_ALLOCMISS(cachep);
		objp = cache_alloc_refill(cachep, flags); 
	}
		
	local_irq_restore(save_flags);
	
	...
	
	//返回得到的内存块的地址。
	return objp;
}


这里又涉及到一个本地高速缓存。

这个本地高速缓存,实际上是每个处理器都有的(并非是硬件层面,而是 SLAB 分配器为加快分配速度,相当于预读内存块),他存放在缓存对象的 array 数组中(这个数组长度是 CPU 个数,每个CPU都有这么一项),取出的是一个 array_cache。



struct array_cache {

	unsigned int avail;
	unsigned int limit;
	unsigned int batchcount; 
	unsigned int touched;
};


avail :这是本地高速缓存里记录的内存块个数,同时也是可用的内存块的下标。为什么这么说?因为这里的内存块,是从高处往下取的,所以自然有这种奇效。

limit :本地高速缓存的大小,也就是本地高速缓存中指针的最大个数

batchcount :本地高速缓存不足时,需要填充的块数

touched :如果最近被使用过,则置为1


可以发现的是,他并没有记录本地高速缓存所缓存的内存块的地址,他只有一个索引,那么内存块到底存放在哪呢?

很简单,内存块就跟随在这个结构体的屁股后面!这样 20 行才可以通过直接对他加一,再用下标进行索引,来得到内存块。


从上面也可以看出的是,本地高速缓存所记录的,不是真正的内存块,因为内存块大小都不一样,而他却是简单的减一来获取,这样子减一最多减去 4 字节,这不能满足大小不一的内存块。

他所记录的,不过是真正的内存块的地址,通过数组方式索引后,就得到了他。


接下来再来看本地高速缓存不足后,怎么对他进行补充并返回一个内存块。



static void* cache_alloc_refill(kmem_cache_t* cachep, int flags)
{
	int batchcount; 
	struct kmem_list3 *l3;
	struct array_cache *ac; 

	ac = cachep->array[smp_processor_id()];
	
retry:

	//batchcount是每次补充的数量。
	batchcount = ac->batchcount;
	
	
	if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {
		//如果本缓存是没有使用过的同时补充的数量还大于最大的限制。
		//那么限制他。
		
		batchcount = BATCHREFILL_LIMIT;
	}
	
	//得到缓存对象的 lists 对象。
	//之前说过,slab 分为三类放在三个链表中,这三个链表都是在这个字段里的。
	l3 = &(cachep)->lists;

	BUG_ON(ac->avail > 0);

	spin_lock(&cachep->spinlock);

	
	if (l3->shared) {
		
		//缓存对象除了有每个CPU专用的本地高速缓存外,还有CPU共享的共享高速缓存
		//这里取出这个共享高速缓存
		struct array_cache *shared_array = l3->shared;

		if (shared_array->avail) {
			//如果这个共享高速缓存有可用的内存块,就考虑从他这里拿 
			
			if (batchcount > shared_array->avail)
				//如果共享高速缓存不够了,那就让他少申请点嘛!
				batchcount = shared_array->avail;
			
			//有内存块被拿走了,减去被拿走的数量
			shared_array->avail -= batchcount;
			
			//既然本地高速缓存多了内存块,也要递增
			ac->avail = batchcount;
			
			//共享高速缓存也是把内存块的指针存放在自己屁股后的
			//这里把这些指针复制给本地高速缓存
			memcpy((void**)(ac+1), 
					&(void**)(shared_array+1)[shared_array->avail],
						sizeof(void*)*batchcount);

			shared_array->touched = 1;
			goto alloc_done;
		}
	}

	/* 到了这里,就说明共享高速缓存也不够了,准备从缓存对象的 slab 对象中取 */
 
	while (batchcount > 0) {
		//
		struct list_head *entry;
		struct slab *slabp;
		
		//首先先访问部分空闲SLAB链表,使entry指向第一个节点。
		entry = l3->slabs_partial.next;

		if (entry == &l3->slabs_partial) {
			//如果部分空闲SLAB链表为空(链表头的next指向自己,说明队列里没有元素了)
			
			l3->free_touched = 1;
			
			//部分空闲SLAB链表为空,那再看看全部空闲 SLAB 链表。
			entry = l3->slabs_free.next;
			
			if (entry == &l3->slabs_free)
				//如果全部空闲SLAB链表也为空时,那就彻底没有啦!
				goto must_grow;
		}

		//至少全部空闲或者是部分空闲SLAB链表有一个不为空,那么就取出该链表所属的SLAB 
		slabp = list_entry(entry, struct slab, list);
		

		while (slabp->inuse < cachep->num && batchcount--) {
			//循环分配处理的数量的对象
			//新增的内存块不超过高速缓存内存的对象限制,同时添加数不为空,循环后自动减1。
			
			kmem_bufctl_t next;
			STATS_INC_ALLOCED(cachep);
			STATS_INC_ACTIVE(cachep);
			STATS_SET_HIGH(cachep);

			//在本地高速缓存记录当前内存块的地址
			(void**)(ac+1)[ac->avail++] = 
                                 slabp->s_mem + slabp->free*cachep->objsize;
			
			//使用中的内存块加一
			slabp->inuse++;
			
			//slab 屁股后面跟随的是 kmem_bufctl_t 数组,详情见前文。
			//这里即得到下一个空闲内存块的索引
			next = ((kmem_bufctl_t *)(slabp+1))[slabp->free];
			
			//更新free字段,使得它指向slab中下一个空闲对象的下标。
			slabp->free = next;
		}
		
		check_slabp(cachep, slabp);  

		//把 slab 从原来的链表中摘除
		list_del(&slabp->list);
		
		//如果 slab 没有空闲块了,则加入无空闲链表,否则加入半空闲链表
		if (slabp->free == BUFCTL_END)
			list_add(&slabp->list, &l3->slabs_full);
		else
			list_add(&slabp->list, &l3->slabs_partial);
	}
	
	.... //省略一大堆,核心操作全在上面了
	
	
	return ac_entry(ac)[--ac->avail];
}





发表评论:

Copyright ©2015-2016 freehui All rights reserved