深入linux内核架构--slab分配器（建议收藏）

简介：malloc对于大家来说应该都不陌生了，这是系统库给我们提供了申请指定大小内存的函数，之前介绍的伙伴系统，只能以页的方式申请内存，对于小块(小于一页)内存的申请我们就得通过自定义的库函数来实现相关需求，所以在用户空间层面诞生了诸如ptmalloc(glibc)，tcmalloc(google)，jemalloc(facebook)等优秀的内存分配库。但是这些库内核没法使用，且内核也有大量申请小块内存的需求，诸如管理dentry，inode，fs_struct，page，task_struct等等一系列内核对象。所以内核提出了slab分配器，用来管理内核中小块内存分配，而cpu cache也是配合slab使用的，有时候也把slab称为缓存。

内核中内存管理

对于内核来说，slab主要包括kmalloc及kfree两个函数来分配及释放小块内存：
kmalloc(size, flags)：分配长度为size字节的一个内存区，并返回指向该内存区起始void指针，如果没有足够内存，返回NULL。

kfree(ptr)：释放ptr指向的内存区。

对于内核开发者还可以通过kmem_cache_create创建一个缓存kmem_cache对象；
通过kmem_cache_alloc、kmem_cache_alloc_node提供特定类型的内核缓存对象申请。他们最终都会调用到slab_alloc。所以主要的slab操作都在slab_alloc函数中。

slab缓存由两部分组成：保存管理性数据的缓存对象和保存被管理对象的各个slab对象

【文章福利】小编推荐自己的Linux内核技术交流群：【977878001】整理一些个人觉得比较好得学习书籍、视频资料共享在群文件里面，有需要的可以自行添加哦！！！前100进群领取，额外赠送一份价值699的内核资料包（含视频教程、电子书、实战项目及代码）

slab cache
上图中缓存即为kmem_cache，slab即为page页帧，缓存对象即为void指针。一个kmem_cache会在不同的内存节点管理很多页帧，这些页帧在各个内存节点被划分为3类：部分空闲，全部空闲以及全部分配。

每个缓存kmem_cache对象只负责一种slab对象类型的管理，各个kmem_cache缓存中slab对象大小各不相同，由创建的时候指定，而缓存会根据指定的slab对象大小根据cpu cacheline 或者void*指针大小进行对齐，然后根据一个公式计算一个合适的gfporder来确定每次申请的内存页帧的数量。其计算方法为：

对应的计算函数为calculate_slab_order，相关代码如下：

系统中所有的缓存都保存在一个双链表中，这使得内核可以遍历所有的缓存，这主要用于缩减分配给内存的数量，常见的场景就是：dentry及inode slab缓存的回收，当机器物理内存不足时就会缩减这一部分内存占用(这一部分内存被称为SReclaimable，可以通过cat /proc/meminfo查看)。

基本结构

kmem_cache数据结构代表一个slab 缓存，其中有一些缓存元信息包括：缓存名，缓存对象大小，关联的内存页帧数，着色信息等等；还有一个__per_cpu array_cache用于表示该缓存在各个CPU中的slab对象；kmem_cache_node用于管理各个内存节点上slab对象的分配。

array_cache是一个per_cpu数组，所以访问不需要加锁，是与cpu cache打交道的直接数据结构，每次获取空闲slab对象时都是通过entry[avail--]去获取，当avail==0时，又从kmem_cache_node中获取batchcount个空闲对象到array_cache中。

kmem_cache_node用于管理slab(实际对象存储伙伴页帧)，其会管理三个slab列表，部分空闲partial，全部空闲empty，全部占用full。array_cache获取batchcount空闲对象时，先尝试从partial分配，如果不够则再从empty分配剩余对象，如果都不够，则需要grow分配新的slab页帧

page页帧，这个就不必多说了，这是物理存储地址，是一个union结构，当被用作slab时，会初始化一下slab管理数据，诸如起始object地址s_mem，lru缓存节点，是否被激活active，关联到的kmem_cache以及freelist空闲对象数组(是一个void*指针，其实存的是char or short数组)。

具体数据结构如下：

kmalloc

kmalloc的基本调用结构如下：

主要包括两个操作：

从kmalloc_caches中获取kmem_cache(kmalloc_cache在slab初始化的时候已经生成好)。
通过slab_alloc从kmem_cache中分配一个slab对象，并返回。

具体细节我们后续详细讨论slab_alloc的详细实现。

kfree

kfree最终会调用到___cache_free，具体我们再 slab free中详细讨论。

初始化

内核的大部分管理数据结构都是通过kmalloc分配内存的，那么slab本身结构的内存管理就出现了一个鸡与蛋的问题，slab数据结构所需内存远小于一整页的内存块，这些最适合kmalloc分配，而kmalloc只有在slab初始化完之后才能使用。

所以就需要内核在启动时进行一些初始化操作，让内核在后续的数据结构能够找到对应的kmem_cache对象供kmalloc使用，而这一机制就是之前提到的kmalloc_caches。kernel启动时会先进行slab初始化，slab初始化时会先为kmalloc_caches分配内存，后续slab对象关联的kmem_cache可以从kmalloc_caches中获取，这样slab本身数据结构的内存分配就可以使用了，而这些内存会存在kmem_cache_boot这个缓存中。

kmem_cache_init是初始化slab分配器的函数，其主要作用就是通过create_kmalloc_caches初始化kmalloc_caches。而kmalloc_caches数组中的kmem_cache对象本身则存储在kmem_cache_boot中，因为kmem_cache对象的大小是固定的，所以只需要一个kmem_cache就可以了，而该函数在start_kernel中被调用进行初始化，create_kmalloc_caches的实现如下：

基本调用关系图如下：

slab 初始化主要是为了初始化kmem_cache_boot及kmalloc_caches数组，方便后续内核核心代码使用kmalloc，而不需要额外管理slab内存数据结构，这样slab本身的数据结构内存申请就可以直接使用上kmalloc了。kmem_cache相关数据都是由kmem_cache_boot管理的，kmalloc调用时使用的kmem_cache都是在初始化时已经创建好的kmalloc_caches中的kmem_cache缓存对象，上述__kmem_cache_create就是创建kmem_cache对象的关键函数，这个我们在后续slab create中详细介绍。

在介绍slab 初始化的时候有提到__kmem_cache_create。其实kmem_cache_create最终也是通过__kmem_cache_create来初始化kmem_cache相关变量，具体调用关系图如下：

slab create的主要目的就是初始化一个kmem_cache缓存对象中的起始值，主要包括：batchcount，size，align，useroffset，usersize，flags，colour，num，gfporder等等。但是这里有特别需要注意的是：batchcount及limit在create的时候是设为1，且并没有分配相应的页帧来存储slab对象，这些都需要在slab alloc发现没有可用对象时进行grow分配。

slab create根据需要被管理的对象size，计算kmem_cache_node中管理的伙伴页帧阶gfporder大小，我们把这样一个伙伴页帧叫做slab，通过slab中的页数以及对象size就可以计算出一个slab中能存储的对象数量num = ((PAGE_SIZE << gfporder) - head) / size 下取整。
代码如下：

这里需要特别单独说一下的是kmalloc_node，这是分配kmem_cache_node的关键函数，相关函数调用如下：

相关代码如下：

总结

简而言之，slab缓存的基本思想如下：

内核使用slab分配器时，主要包括两个步骤：

通过kmem_cache_create创建一个缓存。
通过kmem_cache_alloc在指定缓存中申请一个slab对象。

细分描述如下：

通过kmem_cache_create(size, flags)函数创建一个缓存对象，根据size计算缓存的gfporder，从而可以知道每次新分配管理页帧的数量，也就可以计算一个kmem_cache_node页帧中能管理的slab对象数目num。
当通过kmem_cache_create(*cachep, flags)函数申请slab对象分配时，首先查找cachep->array_caches[curr_cpu]中是否有可用空闲对象，有则直接返回，没有则执行步骤3。
从kmem_cache_node中一次导入batchcount数量的空闲对象到array_caches，导入规则是，先选择部分空闲页帧，然后是全部空闲页帧，将内存中对象装载到array_cache中，当没有可用页帧时执行grow，跳入步骤4，否则跳入步骤6。
通过伙伴系统申请2^gfporder数量的页，并初始化slab头部信息及空闲列表信息，就每个空闲对象的起始地址随机打散到page->freelist数组中，这样每次分配时指向的地址会比较随机。并将该页帧伙伴放入kmem_cache_node->slab_free中。
继续像步骤3一样继续装载空闲对象到array_cache，直至batchcount为0后跳入步骤6。
6.返回array_cache->entry[--array_cache->avail];

具体可以结合slab data struct图一起看，应该会有一个比较清晰的整体感观。

slab coloring：

在深入理解linux内核架构原文中，是这么描述的:如果数据存储在伙伴系统直接提供的页中，那么其地址总是出现在2的幂次的整数倍附近。这对CPU高速缓存的利用有负面影响，由于这种地址分布，使得某些缓存行过度使用，而其他的则几乎为空。通过slab着色(slab coloring)，slab分配器能够均匀的分布对象，以实现均匀的缓存利用，在看了slab coloring的实现原理后我百思不得其解，为啥通过对页内slab对象加一个偏移就可以让缓存命中均匀了呢，通过翻阅大量资料发现，其实这个slab coloring好像并没有什么卵用。

要理解slab着色并不能让缓存利用更均匀，首先得对cpu cache有一定了解：cpu cache将cache划分成固定大小的cache line，一般来说一个cache line的大小为64Byte，然后将cache line与内存地址映射。cpu cache目前主要有三种映射：1、直接映射；2、全相连映射；3、组相连映射。缓存行由三个部分组成 valid，tag，data；其中valid表示该缓存行中数据是否有效，tag用于判断对应cach行存储的确实是目标地址，data则是缓存行具体的64Byte数据。

我们以32位物理内存地址，1MB cache，64Byte cache line系统为例：
那么该系统缓存地址有20位(2^20 = 1MB)，其中低6位用于定位缓存行内数据，高14位用于定位缓存行，而我们的物理内存地址有32位，那么同一缓存行中可能存储2^12种不同地址，所以就需要一个12位的TAG来确定缓存中存储的确实是指定物理地址的数据。比如0x000XXX和0x001XXX都会命中同一缓存行，而通过TAG中存储的值来确认存储的是0x000XXX还是0x001XXX的数据。

具体过程如下：

而缓存行的定位跟缓存与物理地址映射有关：

直接映射

直接映射中cache地址与内存地址是固定好的映射关系；因此可能会存在某些行过热的情况出现(某些倍数地址临时访问频繁，这种情况在大数据处理中很常见，hash shuffle的时候有时候很容易出现长尾)。

全相连映射

全相连映射中，每一个内存块可以随意的映射到任意一个cache line，由于可以随意映射，所以每次访问的时候要匹配每个cache line的tag来确认是否是对应的物理地址。

组相连映射

组相连映射是直接映射和全相连映射的折中，组间直接映射，组内全相连映射，这样一定程度上可以缓解热点问题，又能避免对比太多TAG。

经过上面的分析，对于CPU hardware cache有了大致的了解。那么slab coloring这种偏移页内一个cache line的做法对于避免缓存行有什么帮助呢？看上去并没有什么太多用，看下面的分析：

比如一个slab A分配的page起始地址为0X00000000，另一个slab B分配的page起始地址为0X00002000，cache的大小为1MB，每个缓存行大小为64Byte，一共有16384行。那么slab A对应的缓存行为0~63行，而slab B对应的缓存行为128~191行，他们本来就不会命中到同一缓存行，你页内再怎么偏移也没有任何关系。即使如果两个slab对应的page会命中到同一缓存行，页内的偏移也看上去不会有什么不同的改善，是不是？反而组相连可以比较好的解决相同命中时的冲突问题。

但是仔细想一想kmem_cache_node中的slab页帧结构你会发现，如果没有着色偏移的话，那么每次对应的缓存行一般都是从一个固定值开始的，假如我们忽略slab head的大小，每次slab对象都从页的起始位置开始分配，由于slab对象与cache line 一般来说是不等的，那么每次映射的缓存行一般是0 ~ 61或者0 ~ 62这种，所以62，63这种缓存行就会有较低访问概率，所以就需要这个着色偏移，让首尾缓存访问的概率趋于相同