linux内存管理--slab及其代码解析
Linux内核使用了源自于 Solaris 的一种方法，但是这种方法在嵌入式系统中已经使用了很长时间了，它是将内存作为对象按照大小进行分配，被称为slab高速缓存。
内存管理的目标是提供一种方法，为实现各种目的而在各个用户之间实现内存共享。内存管理方法应该实现以下两个功能：
最小化管理内存所需的时间
最大化用于一般应用的可用内存（最小化管理开销）
内存管理实际上是一种关于权衡的零和游戏。您可以开发一种使用少量内存进行管理的算法，但是要花费更多时间来管理可用内存。也可以开发一个算法来有效地管理内存，但却要使用更多的内存。最终，特定应用程序的需求将促使对这种权衡作出选择。
每个内存管理器都使用了一种基于堆的分配策略。在这种方法中，大块内存（称为 堆）用来为用户定义的目的提供内存。当用户需要一块内存时，就请求给自己分配一定大小的内存。堆管理器会查看可用内存的情况（使用特定算法）并返回一块内存。搜索过程中使用的一些算法有 first-fit（在堆中搜索到的第一个满足请求的内存块）和 best-fit（使用堆中满足请求的最合适的内存块）。当用户使用完内存后，就将内存返回给堆。
这种基于堆的分配策略的根本问题是碎片（fragmentation）。当内存块被分配后，它们会以不同的顺序在不同的时间返回。这样会在堆中留下一些洞，需要花一些时间才能有效地管理空闲内存。这种算法通常具有较高的内存使用效率（分配需要的内存），但是却需要花费更多时间来对堆进行管理。
另外一种方法称为 buddy memory allocation，是一种更快的内存分配技术，它将内存划分为 2 的幂次方个分区，并使用 best-fit 方法来分配内存请求。当用户释放内存时，就会检查 buddy 块，查看其相邻的内存块是否也已经被释放。如果是的话，将合并内存块以最小化内存碎片。这个算法的时间效率更高，但是由于使用 best-fit 方法的缘故，会产生内存浪费。
slab 缓存
Linux 所使用的 slab 分配器的基础是 Jeff Bonwick 为 SunOS 操作系统首次引入的一种算法。Jeff 的分配器是围绕对象缓存进行的。在内核中，会为有限的对象集（例如文件描述符和其他常见结构）分配大量内存。Jeff 发现对内核中普通对象进行初始化所需的时间超过了对其进行分配和释放所需的时间。因此他的结论是不应该将内存释放回一个全局的内存池，而是将内存保持为针对特定目而初始化的状态。例如，如果内存被分配给了一个互斥锁，那么只需在为互斥锁首次分配内存时执行一次互斥锁初始化函数（mutex_init）即可。后续的内存分配不需要执行这个初始化函数，因为从上次释放和调用析构之后，它已经处于所需的状态中了。
Linux slab 分配器使用了这种思想和其他一些思想来构建一个在空间和时间上都具有高效性的内存分配器。
图 1 给出了 slab 结构的高层组织结构。在最高层是 cache_chain，这是一个 slab 缓存的链接列表。这对于 best-fit 算法非常有用，可以用来查找最适合所需要的分配大小的缓存（遍历列表）。cache_chain 的每个元素都是一个 kmem_cache 结构的引用（称为一个 cache）。它定义了一个要管理的给定大小的对象池。
图 1. slab 分配器的主要结构
每个缓存都包含了一个 slabs 列表，这是一段连续的内存块（通常都是页面）。存在 3 种 slab：
slabs_full
完全分配的 slab
slabs_partial
部分分配的 slab
slabs_empty
空 slab，或者没有对象被分配
注意 slabs_empty 列表中的 slab 是进行回收（reaping）的主要备选对象。正是通过此过程，slab 所使用的内存被返回给操作系统供其他用户使用。
slab 列表中的每个 slab 都是一个连续的内存块（一个或多个连续页），它们被划分成一个个对象。这些对象是从特定缓存中进行分配和释放的基本元素。注意 slab 是 slab 分配器进行操作的最小分配单位，因此如果需要对 slab 进行扩展，这也就是所扩展的最小值。通常来说，每个 slab 被分配为多个对象。
由于对象是从 slab 中进行分配和释放的，因此单个 slab 可以在 slab 列表之间进行移动。例如，当一个 slab 中的所有对象都被使用完时，就从 slabs_partial 列表中移动到 slabs_full 列表中。当一个 slab 完全被分配并且有对象被释放后，就从 slabs_full 列表中移动到 slabs_partial 列表中。当所有对象都被释放之后，就从 slabs_partial 列表移动到 slabs_empty 列表中。
3.4.1slab相关数据结构
1slab高速缓存描述符
3.4.2slab的本地对象缓存
linux2.6为了更好的支持多处理器，减少自旋锁的竞争并更好的利用硬件高速缓存，slab分配器的每个高速缓存都包含一个被称为slab本地高速缓存的每cpu数据结构，该结构由一个指向被释放对象的指针数组组成。这样的话，slab对象的释放和分配就只影响到本地的指针数组，减少了并发性。只有本地数组上溢或者下溢时才会去涉及slab结构。相关数据结构如下：static inline void __cache_free(struct kmem_cache *cachep, void *objp){struct array_cache *ac = cpu_cache_get(cachep);check_irq_off();objp = cache_free_debugcheck(cachep, objp, __builtin_return_address(0));if (cache_free_alien(cachep, objp))return;//本地高速缓存可用的空闲对象尚未达到限制，将空闲对象放入本地高速缓存if (likely(ac->avail < ac->limit)) {STATS_INC_FREEHIT(cachep);ac->entry[ac->avail++] = objp;return;} else {//cache_flusharray()会将本地高速缓存的一些空闲对象放入到slab中cache_flusharray(cachep, ac);ac->entry[ac->avail++] = objp;}}static void cache_flusharray(struct kmem_cache *cachep, struct array_cache *ac){int batchcount;struct kmem_list3 *l3;int node = numa_node_id();//一次应该将batchcount个空闲对象归还到slab中batchcount = ac->batchcount;check_irq_off();//得到对应内存节点的slab list3,上面记录着该节点的slab链表l3 = cachep->nodelists[node];spin_lock(&l3->list_lock);//优先先归还到本地共享高速缓存中，注意本地共享高速缓存中的//空闲对象是仅供该内存节点上的各个cpu分配使用的，这样可以使内存访问的效率最高。if (l3->shared) {struct array_cache *shared_array = l3->shared;int max = shared_array->limit - shared_array->avail;if (max) {if (batchcount > max)batchcount = max;//将batchcount个数组元素copy到本地高速缓存中memcpy(&(shared_array->entry[shared_array->avail]), ac->entry, sizeof(void *) * batchcount);shared_array->avail += batchcount;goto free_done;}}//在没有本地高速缓存的情况下，释放回slab中free_block(cachep, ac->entry, batchcount, node);free_done:spin_unlock(&l3->list_lock);ac->avail -= batchcount;//将删除后剩下的空闲对象往前移动一下，hoho,可能还剩下些空闲对象memmove(ac->entry, &(ac->entry[batchcount]), sizeof(void *)*ac->avail);}static void free_block(struct kmem_cache *cachep, void **objpp, int nr_objects, int node){int i;struct kmem_list3 *l3;for (i = 0; i < nr_objects; i++) {void *objp = objpp[i];struct slab *slabp;//先从对象获取到其所在的page，再从page得到其所属的slab//page->lru.prev中记录了page所属的slabslabp = virt_to_slab(objp);l3 = cachep->nodelists[node];list_del(&slabp->list);check_spinlock_acquired_node(cachep, node);check_slabp(cachep, slabp);//放入对应的slabslab_put_obj(cachep, slabp, objp, node);STATS_DEC_ACTIVE(cachep);l3->free_objects++;check_slabp(cachep, slabp);/* fixup slab chains *///slab所有的对象都已经被归还if (slabp->inuse == 0) {//slab高速缓存的空闲对象数超过了限制，可以释放掉该slab，以//释放其所占有的内存if (l3->free_objects > l3->free_limit) {l3->free_objects -= cachep->num;slab_destroy(cachep, slabp);} else {//加入到完全空闲slab链表中list_add(&slabp->list, &l3->slabs_free);}} else {//加入到部分空闲的slab链表中list_add_tail(&slabp->list, &l3->slabs_partial);}}}
