一、内核内存分配

在linux内核中伙伴系统用来管理物理内存，其分配的单位是页，但是向用户程序一样，内核也需要动态分配内存，而伙伴系统分配的粒度又太大。由于内核无法借助标准的C库，因而需要别的手段来实现内核中动态内存的分配管理，linux采用的是slab分配器。slab分配器不仅可以提供动态内存的管理功能，而且可以作为经常分配并释放的内存的缓存。通过slab缓存，内核能够储备一些对象，供后续使用。需要注意的是slab分配器只管理内核的常规地址空间（准确的说是直接被映射到内核地址空间的那部分内存包括 ZONE_NORMAL和ZONE_DMA）。
采用了slab分配器后，在释放内存时，slab分配器将释放的内存块保存在一个列表中，而不是返回给伙伴系统。在下一次内核申请同样类型的对象时，会使用该列表中的内存开。slab分配器分配的优点：

• 可以提供小块内存的分配支持
• 不必每次申请释放都和伙伴系统打交道，提供了分配释放效率
• 如果在slab缓存的话，其在CPU高速缓存的概率也会较高。
• 伙伴系统的操作队系统的数据和指令高速缓存有影响，slab分配器降低了这种副作用
• 伙伴系统分配的页地址都页的倍数，这对CPU的高速缓存的利用有负面影响，页首地址对齐在页面大小上使得如果每次都将数据存放到从伙伴系统分配的页开始的位置会使得高速缓存的有的行被过度使用，而有的行几乎从不被使用。slab分配器通过着色使得slab对象能够均匀的使用高速缓存，提高高速缓存的利用率

在引入了slab分配器后，内核的内存管理方案如图所示：

slab分配器也不是万能的，它也有缺陷：

• 对于微型嵌入式系统，它显得比较复杂，这是可以使用经过优化的slob分配器，它使用内存块链表，并使用最先适配算法
• 对于具有大量内存的大型系统，仅仅建立slab分配器的数据结构就需要大量内存，这时候可以使用经过优化的slub分配器

无论是slab分配器家族的这三个中的那个一，它们提供的接口都是相同的：
kmalloc,__kmalloc和kmalloc_node用于普通内存的分配
kmem_cache_alloc，kmem_cache_alloc_node用于申请特定类型的内存
内核中普通内存的申请使用kmalloc(size,flags),size是申请的大小，flags告诉分配器分配什么样的内存，如何分配等等。
内核中普通内存的释放使用kfree(*ptr);释放ptr所指向的内存区。
可以通过/proc/slabinfo查看活动的缓存列表。

二、slab分配器的原理

slab算法是1994年开发出来的并首先用于sun microsystem solaris 2.4操作系统。这种算法的使用基于以下几个前提：

1. 所存放数据的类型可以影响存储器取区的分配方式。
2. 内核函数倾向于反复请求同一类型的存储器区。
3. 对存储器区的请求可以根据它们发生的频率来分类。
4. 所引入的对象大小不是几何分布的。
5. 硬件高速缓存的高性能。在这种情况下，伙伴函数的每次调用都增加了对内存的平均访问时间。

slab分配器把对象分组放进高速缓存。每个高速缓存都是同种类型对象的一种“储备”。一个cache管理一组大小固定的内存块（也称为对象实体），每个内存块都可用作一种数据结构。cache中的内存块来自一到多个slab。一个slab来自物理内存管理器的一到多个物理页，该slab被分成一组固定大小的块，被称为slab对象（object），一个slab属于一个cache，其中的对象就是该cache所管理的固定大小的内存块。所以一个cache可以有一到多个slab。下图给出了slab分配器的各个部分及其相互关系：

在基于slab的内核内存管理器中，基本的概念是保存管理型数据的缓存（即slab cache，slab缓存）和保存被管理对象的各个slab。每个缓存都负责一种对象类型，比如kmalloc-128会负责管理65-128字节的内存的kmalloc分配。系统中的所有缓存类型都保存在一个链表slab_caches中。

1.slab缓存

slab缓存的详细结构 如图所示：

每个缓存结构都包括了两个重要的成员：

• struct kmem_list3 **nodelists：kmem_list3结构中包含了三个链表头，分别对应于完全用尽的slab链表，部分用尽的slab链，空闲的slab链表，其中部分空闲的在最开始
• struct array_cache *array[NR_CPUS + MAX_NUMNODES]：array是一个数组，系统中的每一个CPU，每一个内存节点都对应该数组中的一个元素。array_cache结构包含了一些特定于该CPU/节点的管理数据以及一个数组，每个数组元素都指向一个该CPU/节点刚释放的内存对象。该数组有助于提高高速缓存的利用率。
  • 当释放内存对象时，首先将内存对象释放到该数组中对应的元素中
  • 申请内存时，内核假定刚释放的内存对象仍然处于CPU高速缓存中，因而会先从该数组的对应数组元素中查找，看是否可以申请。
  • 当特定于CPU/节点的缓存数组是空时，会用slab缓存中的空闲对象填充它

因此，对象分配的次序为：

1. 特定于CPU/节点的缓存列表中的对象
2. 当前已经存在于slab缓存中中的未用对象
3. 从伙伴系统获得内存，然后创建的对象

2.slab对象

对象在slab中不是连续排列的，其排列如图所示:

slab对象的长度并不代表其确切的长度，因为需要对长度进行调整以满足对齐要求。对齐要求可能是：

• 创建slab时指定了SLAB_HWCACHE_ALIGN标志，则会按照cache_line_size的返回值对齐，即对齐的硬件缓存行上。如果对象小于硬件缓存行的一半，则将多个对象放入一个缓存行。
• 如果没有指定对齐标记，则对齐到BYTES_PER_WORD，即对齐到void指针所需字节数目。

为了使得slab满足对齐要求，会在slab对象中添加填充字节以满足对齐要求,使用对齐的地址可以会加速内存访问。每个slab都对应一个管理结构，它可能位于slab内部也可能位于slab外部专门为它申请的内存中，它保存了所有的管理数据，也包括一个链表域用于将slab连接起来，还包括一个指针指向它所属的cache。
大多数情况下，slab内存区的长度是不能被对象长度整除的，因而就有了一些多余的内存，这些内存可以被用来以偏移量的形式给slab“着色”，着色后，缓存的各个slab成员会指定到不同的偏移量，进而可以将数据定位到不同的缓存行。
内核通过对象自身即可找到它对应的slab，过程是:对象的物理地址->物理地址对应的page结构。然后由page找到对应的slab以及cache（包含在page结构中）。

三、slab分配器的实现

1.使用的数据结构

linux使用struct kmem_cache表示slab缓存，使用struct kmem_list3管理缓存所对应的slab链表的链表头，使用struct array_cache管理特定于CPU的slab对象的缓存(注意不是slab缓存是slab对象的缓存)。

2.内核采用的其它保护机制

为了检测错误，内核采用了一些机制来对内存进行保护，主要的方法有：
危险区：在每个对象的开始和结束处增加一个额外的内存区，其中会填充一些特殊的字段。如果这个区域被修改了，可能就是某些代码访问了不该访问的内存区域
对象毒化：在建立和释放slab时，将对象用预定义的模式填充。如果在对象分配时发现该模式已经改变，就可能是发生了内存越界。

3.初始化

slab分配器的初始化涉及到一个鸡与蛋的问题。为了初始化slab数据结构，内核需要很多远小于一页的内存区，很显然由kmalloc分配这种内存最合适，但是kmalloc只有在slab分配器初始化完才能使用。内核借助一些技巧来解决该问题。
kmem_cache_init函数被内核用来初始化slab分配器。它在伙伴系统启用后调用。在SMP系统中，启动CPU正在运行，其它CPU还未初始化，它要在smp_init之前调用。slab采用多步逐步初始化slab分配器，其工作过程：
创建第一个名为kmem_cache的slab缓存，此时该缓存的管理数据结构使用的是静态分配的内存。在slab分配器初始化完成后，会将这里使用的静态数据结构替换为动态分配的内存。
初始化其它的slab缓存，由于已经初始化了第一个slab缓存，因此这一步是可行。
将初始化过程由于“鸡与蛋”的问题而使用的静态数据结构替换为动态分配的。

4.API

1.创建缓存

slab分配器使用kmem_cache_create创建一个新的slab缓存。该函数的基本工作过程为：

1. 参数检查
2. 计算对齐
3. 分配缓存的管理结构所需的内存
4. 计算slab所需的物理内存大小以及每个slab中slab对象的个数
5. 计算slab管理部分应该放在哪里，并存储在缓存的flags域中
6. 计算slab的颜色，颜色数目存在color中，颜色偏移量存在color_off中
7. 建立每CPU的缓存
8. 将新创建的缓存添加到全局slab缓存链表slab_caches中

2.分配对象

kmem_cache_alloc用于从指定的slab缓存分配对象。与kmalloc相比，它多了一个缓存指针的参数，用于指向所要从其中分配内存的缓存。
其工作过程如图：

在NUMA系统中，如果在本节点分配失败，还会尝试其它节点。

cache_grow用于缓存的增长，它会从伙伴系统获取内存。其流程如图所示：

3.释放对象

4.缓存收缩

5.通用缓存