内存管理之slab分配器

STL中的空间配置器采用一、二级配置器进行内存管理，当配置区块

    在一级配置器中，allocate()直接使用malloc()，deallocate()直接使用free()，对于内存不足的情况，模拟C++的set_new_handler()机制；

      在二级配置器中，首先会维护16个*链表（free lists），负责16种小型区块的次配置能力；如果内存不足，转调一级配置器中的set_new_handler()。如果请求内存块大于128bytes，就转调一级配置器。当请求内存块小于128bytes，则以内存池管理。

这里的free lists，即空闲链表，包含可供使用的、已经分配好的数据结构块。当代码需要一个新的数据结构实例时，就可以从空闲链表中抓取一个，而不需要分配内存，可以直接把数据放进去。当不再需要这个数据结构的实例时，就把它放回空闲链表，而不是释放它。

    但是，空闲链表主要的问题是不能全局控制。当内存变得紧缺时，内核无法通知每个空闲链表，让其收缩缓存的大小以便释放出一些内存来。Linux内核为了弥补这一缺陷，增加了slab分配器。

    slab分配器相当于通用数据结构缓存层，为具体对象类型分配。

slab分配器基本原则：

· 频繁使用的数据结构会频繁分配和释放，因此应当缓存。

· 频繁分配和回收会导致内存碎片。为了避免内存碎片现象，空闲链表的缓存会连续的存放。因为已释放的数据结构又会放会空闲链表，因此不会导致碎片。

· 回收的对象可以立即投入下一次分配。对于频繁的分配和释放，空闲链表能够提高其性能。

· 对存放的对象进行着色，以防止多个对象映射到相同的高速缓存行（cache line）。

· 如果分配器知道对象大小、页大小和总的高速缓存的大小，会更合适。

· 如果分配器是与NUMA相关的，就可以从相同的内存节点为请求者进行分配。（NUMA：非统一内存访问，遵循对称多处理（SMP）架构）

slab层的设计

       slab是由一个或多个物理上连续的页组成。每个高速缓存可由多个slab。

      slab层把不同的对象划分为所谓高速缓存组，其中每个高速缓存组都存放不同类型的对象。即每种对象类型对应一个高速缓存。 而且，kmalloc()接口建立在slab层上，使用了一组通用高速缓存。

    每个高速缓存使用结构体kmem_cache表示。这个结构包含三个链表：slabs_full、slabs_partial、slabs_empty，均可放在kmem_list3结构中。该结构在mm/slab.c中定义。

struct kmem_cache_s {
/* 1) per-cpu data, touched during every alloc/free */
	/**
	 * 每CPU指针数组，指向包含空闲对象的本地高速缓存。
	 */
	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 */
	/**
	 * 在一个单独slab中的对象的个数。高速缓存中的所有slab具有相同的大小。
	 */
	unsigned int		num;	/* # of objs per slab */
	/**
	 * 整个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) */
	/**
	 * 一个单独slab中包含的连续页框数目的对数。
	 */
	unsigned int		gfporder;

	/* force GFP flags, e.g. GFP_DMA */
	/**
	 * 分配页框时传递给伙伴系统函数的一组标志。
	 */
	unsigned int		gfpflags;

	/**
	 * slab使用的颜色个数。用于slab着色。
	 */
	size_t			colour;		/* cache colouring range */
	/**
	 * slab中的基本对齐偏移。
	 */
	unsigned int		colour_off;	/* colour offset */
	/**
	 * 下一个被分配的slab使用的颜色。就是对齐因子。
	 */
	unsigned int		colour_next;	/* cache colouring */
	/**
	 * 指向包含slab描述符的普通slab高速缓存。如果使用了内部slab描述符，则这个字段为NULL。
	 */
	kmem_cache_t		*slabp_cache;
	/**
	 * 单个slab的大小。
	 */
	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;

struct kmem_list3 {
	/**
	 * 空闲和非空闲对象的slab描述符双向循环链表。
	 */
	struct list_head	slabs_partial;	/* partial list first, better asm code */
	/**
	 * 不包含空闲对象的slab描述符双向循环链表。
	 */
	struct list_head	slabs_full;
	/**
	 * 只包含空闲对象的slab描述符双向循环链表。
	 */
	struct list_head	slabs_free;
	unsigned long	free_objects;
	/**
	 * slab分配器的页回收算法使用。
	 */
	int		free_touched;
	/**
	 * slab分配器的页回收算法使用。
	 */
	unsigned long	next_reap;
	/**
	 * 所有CPU共享的一个本地高速缓存的指针。它使得将空闲对象从一个本地高速缓存移动到另外一个高速缓存的任务更容易。
	 * 它的初始大小是batchcount字段的8倍。
	 */
	struct array_cache	*shared;
};

slab描述符要么在slab之外另行分配，要不就放在slab自身开始的地方。

slab描述符struct slab用来描述每个slab：

struct slab {
	/**
	 * slab高速缓存描述符的三个双向循环链表中的一个。
	 */
	struct list_head	list;
	/**
	 * slab中第一个对象的偏移。
	 * 同一个高速缓存的不同slab有不同的coloroff值。这样可以避免硬件缓存行的不利影响。
	 */
	unsigned long		colouroff;
	/**
	 * slab中第一个对象的地址。
	 */
	void			*s_mem;		/* including colour offset */
	/**
	 * 当前正在使用的slab中的对象个数。
	 */
	unsigned int		inuse;		/* num of objs active in slab */
	/**
	 * slab中下一个空闲对象的下标。如果没有剩下空闲对象则为BUFCT_END
	 */
	kmem_bufctl_t		free;
};

每个slab都包含一些对象成员，即被缓存的数据结构。每个slab处于三种状态之一：

· slabs_full

完全分配的slab（所有对象已分配）

· slabs_partial

部分分配的slab

· slabs_empty

空slab，或者没有对象被分配                                                                                                                                                    

分配策略：当内核的某一部分需要一个新的对象时，先从部分满的slab中进行分配；如果没有部分满的slab，就从空的slab中进行分配；如果没有空的slab，会选择去创建一个slab。

    这种分配策略可减少内存碎片。                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        slab分配器可以创建新的slab，是通过alloc_pages()低级内核页分配器进行的：                                                                                                                                                                                              

static void *kmem_getpages(kmem_cache_t *cachep, int flags, int nodeid)
{
	struct page *page;
	void *addr;
	int i;

	flags |= cachep->gfpflags;
	if (likely(nodeid == -1)) {
		page = alloc_pages(flags, cachep->gfporder);
	} else {
		page = alloc_pages_node(nodeid, flags, cachep->gfporder);
	}
	if (!page)
		return NULL;
	addr = page_address(page);

	i = (1 << cachep->gfporder);
	if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
		atomic_add(i, &slab_reclaim_pages);
	add_page_state(nr_slab, i);
	while (i--) {
		SetPageSlab(page);
		page++;
	}
	return addr;
}

/**
 * 分配2^order个连续的页框。它返回第一个所分配页框描述符的地址或者返回NULL
 */
static inline struct page *
alloc_pages(unsigned int gfp_mask, unsigned int order)
{
	if (unlikely(order >= MAX_ORDER))
		return NULL;

	return alloc_pages_current(gfp_mask, order);
}

    通过alloc_pages（）来为高速缓存分配足够多的内存。

       接着调用kmem_freepages()来释放内存，而对于给定的高速缓存页，kmem_freepages()最终调用的是free_pages()。

static void kmem_freepages(kmem_cache_t *cachep, void *addr)
{
	unsigned long i = (1<<cachep->gfporder);
	struct page *page = virt_to_page(addr);
	const unsigned long nr_freed = i;

	while (i--) {
		if (!TestClearPageSlab(page))
			BUG();
		page++;
	}
	sub_page_state(nr_slab, nr_freed);
	/**
	 * 如果当前进程正在执行回存回收。就适当增加reclaimed_slab字段。
	 * 于是刚被释放的页就能通过回收算法被记录下来。
	 */
	if (current->reclaim_state)
		current->reclaim_state->reclaimed_slab += nr_freed;
	free_pages((unsigned long)addr, cachep->gfporder);
	/**
	 * 如果SLAB_RECLAIM_ACCOUNT被置位，slab_reclaim_pages则被适当的减少。
	 */
	if (cachep->flags & SLAB_RECLAIM_ACCOUNT) 
		atomic_sub(1<<cachep->gfporder, &slab_reclaim_pages);
}

free_pagees()中调用的也就是__free_pages()，

/**
 * 首先检查page指向的页描述符。
 * 如果该页框未被保留，就把描述符的count字段减1
 * 如果count变为0,就假定从与page对应的页框开始的2^order个连续页框不再被使用。
 * 这种情况下，该函数释放页框。
 */
fastcall void __free_pages(struct page *page, unsigned int order)
{
	if (!PageReserved(page) && put_page_testzero(page)) {
		if (order == 0)
			free_hot_page(page);
		else
			__free_pages_ok(page, order);
	}
}

    slab层的关键是避免频繁分配和释放页。因此，slab分配器只有当给定的高速缓存中既没有满的也没有空的slab时才会调用页分配函数。

而只有在下列情况下才会调用释放函数：当可用内存变得紧缺时，系统视图释放出更多内存以供使用；或者当高速缓存显式地被撤销时。

slab层的管理是在每个高速缓存的基础上，通过提供给整个内核一个简单的接口来完成的。

也就是说，当你创建一个高速缓存后，slab层所起的作用就像一个专用的分配器，可以为具体的对象类型进行分配。

slab分配器接口

kmem_cache_create()

    创建一个新的高速缓存。

这通常是在内核初始化时执行的，或者在首次加载内核模块时执行。其原型定义如下：

kmem_cache_t *
kmem_cache_create (const char *name, size_t size, size_t align,
	unsigned long flags, void (*ctor)(void*, kmem_cache_t *, unsigned long),
	void (*dtor)(void*, kmem_cache_t *, unsigned long))

    name参数是高速缓存的名字；size参数是高速缓存中每个元素的大小；align参数是slab内第一个对象的偏移，它用来确保在页内进行特定的对齐。

flag参数是可选的设置项，用来控制高速缓存的行为，标志如下：

· SLAB_HWCACHE_ALIGN——指定缓存对象必须按高速缓存行对齐。该标志适合频繁使用的高速缓存。可提高性能，但以增加内存开销为代价。

· SLAB_POION——使slab层用已知的值填充slab。有利于对未初始化内存的访问，即允许对缓存中的对象进行监视。

· SLAB_RED_ZONE——在对象头、尾插入标志，用来支持对缓冲区溢出的检查，以探测缓冲越界

· SLAB_CACHE_DMA——使slab层使用可以执行DMA的内存给每个slab分配空间。

    ctor和dtor参数是高速缓存的构造函数和析构函数。只有在新的页追加到高速缓存时，构造函数才被调用。但是，在Linux内核中的高速缓存不使用构造函数，为NULL。

kmem_cache_create()在创建缓存后返回一个指向所创建高速缓存的指针；否则，返回NULL。

该函数不能用于中断上下文中，因为它可能会睡眠。

kmem_cache_destroy()

    撤销一个高速缓存，并将它从cache_chain链表上删除。

int kmem_cache_destroy (kmem_cache_t * cachep)

    该函数通常在模块的注销代码中被调用（是指创建了自己的高速缓存的模块），即内核模块在被卸载时执行。

    不能从中断上下文中调用该函数，因为它可能睡眠。

调用该函数需确保两个条件：

· 高速缓存中的所有slab都为空。不管在哪个slab中，只要还有一个对象被分配并在使用，就不能撤销这个高速缓存。

· 在调用kmem_cache_destroy()过程中，不再访问这个高速缓存，调用者必须确保这种同步。

kmem_cache_alloc()

    从一个命名的缓存中分配一个对象。

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

    该函数从给定的高速缓存cachep中返回一个指向对象的指针。通过函数__cache_alloc()，

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

	cache_alloc_debugcheck_before(cachep, flags);

	local_irq_save(save_flags);
	/**
	 * 首先试图从本地高速缓存获得一个空闲对象。
	 */
	ac = ac_data(cachep);
	/**
	 * 如果本地高速缓存有空闲对象，那么avail字段就包含最后被释放的对象的项在本地高速缓存中的下标。
	 */
	if (likely(ac->avail)) {
		STATS_INC_ALLOCHIT(cachep);
		ac->touched = 1;
		/**
		 * 因为本地高速缓存数组正好存放在ac描述符的后面。
		 * 所以(void**)(ac+1)[--ac->avail]获得空闲对象的地址，并递减ac->avail的值。
		 */
		objp = ac_entry(ac)[--ac->avail];
	} else {/* 本地高速缓存中没有空闲对象。 */
		STATS_INC_ALLOCMISS(cachep);
		/**
		 * cache_alloc_refill重新填充本地高速缓存并获得一个空闲对象。
		 */
		objp = cache_alloc_refill(cachep, flags);
	}
	local_irq_restore(save_flags);
	objp = cache_alloc_debugcheck_after(cachep, flags, objp, __builtin_return_address(0));
	return objp;
}

    首先，试图从本地高速缓存中获得一个空闲对象。

    如果本地高速缓存有空闲对象，那么ac->avail字段就包含最后被释放的对象的项在本地高速缓存中的下标；

    如果高速缓存中的所有slab中都没有空闲的对象，那么slab层必须通过cache_alloc_refill()重新填充本地高速缓存并获得一个空闲对象。

kmem_cache_free()

    释放一个对象，并把它返回给原先的slab。

参数cachep是高速缓存描述符的地址，参数objp是要释放的对象的地址。也就是把cachep中的对象标记为空闲。

void kmem_cache_free (kmem_cache_t *cachep, void *objp)
{
	unsigned long flags;

	local_irq_save(flags);
	__cache_free(cachep, objp);
	local_irq_restore(flags);
}

static inline void __cache_free (kmem_cache_t *cachep, void* objp)
{
	struct array_cache *ac = ac_data(cachep);

	check_irq_off();
	objp = cache_free_debugcheck(cachep, objp, __builtin_return_address(0));

	/**
	 * 首先检查本地高速缓存是否有空间给指向一个空闲对象的额外指针。
	 */
	if (likely(ac->avail < ac->limit)) {
		STATS_INC_FREEHIT(cachep);
		/**
		 * 本地高速缓存有空闲指针，则该指针被加到本地高速缓存后返回。
		 */
		ac_entry(ac)[ac->avail++] = objp;
		return;
	} else {
		STATS_INC_FREEMISS(cachep);
		/**
		 * 调用cache_flusharray，清空本地高速缓存
		 */
		cache_flusharray(cachep, ac);
		/**
		 * 然后将指针加到本地高速缓存。
		 */
		ac_entry(ac)[ac->avail++] = objp;
	}
}

slab分配器应用

    slab层负责内存紧缺情况下所有底层的对齐、着色、分配、释放和回收等。

    如果要频繁创建和释放很多相同类型的对象，就应该考虑slab高速缓存。

补充：

内部碎片和外部碎片

（1）内存上，

内部碎片：已经被分配出去，但不能被利用的内存区域。

    处于一个操作系统分配的用于装载某一进程的内存区域内部的存储块。

外部碎片：指还没有分配出去，但太小了无法满足内存分配请求大小的内存空闲区域。

    处于（两个操作系统）任何两个已分配区域或页面之间的空闲内存块。地址不连续的。

（2）磁盘上，

内部碎片：硬盘上的每个分区都是由最小存储单元——簇组成的。就好比，一面墙是由一块块转头组成的。簇的大小可以在分区格式化时由用户定义，一般是数个KB大小，比如是8KB。假设我有一个文件，大小是80MB零1KB（1MB=1000KB），换算一下就是80,001KB，其中的80,000KB正好占用10000个簇，剩下的那1KB，不得以也要占用1个簇，但这最后一个簇还有7KB的空间没用上了。而且这个未完全使用的簇，其他文件也不允许继续使用。这就造成了一点点的空间浪费。

不少人就把这被浪费了的7KB空间就是磁盘上的内部碎片。

外部碎片：将文件分割成几块不相连的分片，不相连的分片也是文件碎片。

磁盘碎片清理工具清理的是外部碎片。

伙伴系统算法减少外碎片，ab分配器减少内碎片