在linux的内核运行需要动态分配内存的时候，其中有两种分配方案：
- 第一种是以页为单位分配内存，即一次分配内存的大小必须是页的整数倍
- 第二种是按需分配，一次分配的内存大小是随机的
对于第一种方案是通过伙伴系统实现，以页为单位管理和分配内存，但是这个单位确实也太大了。对于第二种方案，在现实的需求中，如果我们要为一个10个字符的字符串分配空间，如果按照伙伴系统采用分配一个4KB或者更多空间的完整页面，不仅浪费而且完全不可接受。显然的解决方案是需要将页拆分为更小的单位，可以容纳大量的小对象。同时新的解决方案月不能给内核带来更大的开销，不能对系统性能产生影响，同时也必须保证内存的利用率和效率。基于此，slab的分配器就应运而生，该机制是并没有脱离伙伴系统，是基于伙伴系统分配的大内存进一步细化分成小内存分配，SLAB 就是为了解决这个小粒度内存分配的问题的。
slab分配器对许多可能的工作负荷都能很好工作，但是有一些场景，也无法提供最优化的性能。如果某些计算机处于当前硬件尺度的边界上，slab分配器就会出现一些问题。同时对于嵌入式系统来说slab分配器代码量和复杂度都太高，所以内核增加了两个替代品，所以目前有三种实现算法，分别是slab、slub、slob，并且，依据它们各自的分配算法，在适用性方面会有一定的侧重。
- Slab是最基础的，最早基于Bonwick的开创性论文并且可用 自Linux内核版本2.2起。
- slob是被改进的slab，针对嵌入式系统进行了特别优化，以便减小代码量。围绕一个简单的内存块链表展开，在分配内存时，使用同样简单的最新适配算法。slob分配器只有大约600行代码，总的代码量很小。从速度来说，它不是最高效的分配器，页肯定不是为大型系统设计的。
- slub是在slab上进行的改进简化，在大型机上表现出色，并且能更好的使用NUMA系统，slub相对于slab有5%-10%的性能提升和减小50%的内存占用
文章代码分析基于以linux-4.9.88，以NXP的IMX系列硬件，分析slub的工作原理。
1. slub数据结构
要想理解slub分配器，首先需要了解slub分配器的核心结构体，kmem_cache的结构体定义如下
struct kmem_cache {
struct kmem_cache_cpu __percpu *cpu_slab;
/* Used for retriving partial slabs etc */
unsigned long flags;
unsigned long min_partial;
int size; /* The size of an object including meta data */
int object_size; /* The size of an object without meta data */
int offset; /* Free pointer offset. */
int cpu_partial; /* Number of per cpu partial objects to keep around */
struct kmem_cache_order_objects oo;
/* Allocation and freeing of slabs */
struct kmem_cache_order_objects max;
struct kmem_cache_order_objects min;
gfp_t allocflags; /* gfp flags to use on each alloc */
int refcount; /* Refcount for slab cache destroy */
void (*ctor)(void *);
int inuse; /* Offset to metadata */
int align; /* Alignment */
int reserved; /* Reserved bytes at the end of slabs */
const char *name; /* Name (only for display!) */
struct list_head list; /* List of slab caches */
int red_left_pad; /* Left redzone padding size */
struct kmem_cache_node *node[MAX_NUMNODES];
}
| 结构体成员变量 | 含义 |
|---|---|
| cpu_slab | 一个percpu变量，对于每个cpu来说，相当于一个本地内存缓存池。当分配内存的时候优先从本地cpu分配内存以保证cache的命中率。 |
| flags | object分配掩码 |
| min_partial | 限制structkmem_cache_node中的partial链表slab的数量。如果大于这个mini_partial的值，那么多余的slab就会被释放。 |
| size | 分配的objectsize |
| object_size | 实际的objectsize |
| offset | offset就是存储下个object地址数据相对于这个object首地址的偏移。 |
| cpu_partial | percpupartial中所有slab的freeobject的数量的最大值，超过这个值就会将所有的slab转移到kmem_cache_node的partial链表 |
| oo | oo用来存放分配给slub的页框的阶数(高16位)和slub中的对象数量(低16位) |
| min | 当按照oo大小分配内存的时候出现内存不足就会考虑min大小方式分配。min只需要可以容纳一个object即可。 |
| allocflags | 从伙伴系统分配内存掩码。 |
| list | 有一个slab_caches链表，所有的slab都会挂入此链表。 |
| node | slab节点。在NUMA系统中，每个node都有一个structkmem_cache_node数据结构 |
在该结构体中，有一个变量struct list_head list，可以想象下，对于操作系统来讲，要创建和管理的缓存不至于task_struct，对于mm_struct，fs_struct都需要这个结构体，所有的缓存最后都会放到这个链表中，也就是LIST_HEAD(slab_caches)。对于缓存中哪些对象被分配，哪些是空着，什么情况下整个大内存块都被分配完了，需要向伙伴系统申请几个页形成新的大内存块？这些信息该由谁来维护呢？？就引出了两个成员变量kmem_cache_cpu和kmem_cache_node。
在分配缓存的时候，需要分两种路径，快速通道(kmem_cache_cpu)和普通通道(kmem_cache_node)，每次分配的时候，要先从kmem_cache_cpu分配；如果kmem_cache_cpu里面没有空闲块，那就从kmem_cache_node中进行分配；如果还是没有空闲块，最后从伙伴系统中分配新的页。
cpu_cache对于每个CPU来说，相当于一个本地内存缓冲池，当分配内存的时候，优先从本地CPU分配内存以及保证cache的命中率，struct kmem_cache_cpu用于管理slub缓存
struct kmem_cache_cpu {
void **freelist; /* Pointer to next available object */
unsigned long tid; /* Globally unique transaction id */
struct page *page; /* The slab from which we are allocating */
struct page *partial; /* Partially allocated frozen slabs */
#ifdef CONFIG_SLUB_STATS
unsigned stat[NR_SLUB_STAT_ITEMS];
#endif
};
| 结构体成员变量 | 含义 |
|---|---|
| freelist | 指向本地CPU的第一个空闲对象，这一项会有指针指向下一个空闲的项，最终所有空闲的项会形成一个链表 |
| tid | 主要用来同步 |
| page | 指向大内存块的第一个页，缓存块就是从里面分配的 |
| partial | 大内存块的第一个页，之所以名字叫partial（部分），就是因为它里面部分被分配出去了，部分是空的。这是一个备用列表，当page满了，就会从这里找 |
struct kmem_cache_node：用于管理每个Node的slub页面，由于每个Node的访问速度不一致，slub页面由Node来管理；
struct kmem_cache_node {
spinlock_t list_lock;
#ifdef CONFIG_SLUB
unsigned long nr_partial; /* partial slab链表中slab的数量 */
struct list_head partial; /* partial slab链表表头 */
#ifdef CONFIG_SLUB_DEBUG
atomic_long_t nr_slabs; /* 节点中的slab数 */
atomic_long_t total_objects; /* 节点中的对象数 */
struct list_head full; /* full slab链表表头 */
#endif
#endi
}
| 结构体成员变量 | 含义 |
|---|---|
| list_lock | 自旋锁，保护数据 |
| nr_partial | partialslab链表中slab的数量 |
| partial | 这个链表里存放的是部分空闲的大内存块。这是kmem_cache_cpu里面的partial的备用列表，如果那里没有，就到这里来找。 |
其结构图如下图所示
2. 初始化
为了初始化slub的数据结构，内核需要若干远小于一整页的内存块，这些最适合使用kmalloc来分配。但是此时只有slub系统已经完成初始化后，才能使用kmalloc。换而言之，kmalloc只能在kmalloc已经初始化之后初始化，这个是不可能，所以内核使用kmem_cache_init函数用于初始化slub分配器。
分配器的初始化工作主要是初始化用于kmalloc的gerneral cache，slub分配器的gerneral cache定义如下：
extern struct kmem_cache *kmalloc_caches[KMALLOC_SHIFT_HIGH + 1];
#define KMALLOC_SHIFT_HIGH (PAGE_SHIFT + 1)
#define PAGE_SHIFT 12
//(各个架构下的定义都有些差异,如果是arm64,那么是通过CONFIG_ARM64_PAGE_SHIFT来指定的,这个配置项在arch/arm64/Kconfig文件中定义,默认为12，也就是默认页面大小为4KiB,笔者以arm64为例)
那么KMALLOC_SHIFT_HIGH=PAGE_SHIFT + 1 = 12 + 1 = 13,KMALLOC_SHIFT_HIGH+1=13+ 1= 14说明kmalloc_caches数组中有14个元素,每个元素是kmem_cache这个结构体
它在内核初始化阶段(start_kernel)、伙伴系统启用之后调用，它首先执行缓存初始化过程，如下图所示
- 从缓存中分配kmem_cache对象，并复制并使用临时kmem_cache
- 从缓存中分配kmem_cache_node对象，然后复制并使用临时使用的kmem_cache_node
- kmalloc boot cache
起初并没有boot cache，因此定义了两个静态变量（boot_kmem_cache，boot_kmem_cache_node）用于临时使用。这里的核心是boot cache创建函数：create_boot_cache()
当调用create_boot_cache创建完kmem_cache和kmem_cache_node两个Cache后，就需要调用bootstrap从Cache中为kmem_cache和kmem_cache_node分配内存空间然后将静态变量boot_kmem_cache和boot_kmem_cache_node中的内容复制到分配的内存空间中，这相当于完成了一次对自身的重建。
static struct kmem_cache * __init bootstrap(struct kmem_cache *static_cache)
{
int node;
struct kmem_cache *s = kmem_cache_zalloc(kmem_cache, GFP_NOWAIT); --------------------(1)
struct kmem_cache_node *n;
memcpy(s, static_cache, kmem_cache->object_size);
/*
* This runs very early, and only the boot processor is supposed to be
* up. Even if it weren't true, IRQs are not up so we couldn't fire
* IPIs around.
*/
__flush_cpu_slab(s, smp_processor_id());
for_each_kmem_cache_node(s, node, n) { --------------------(2)
struct page *p;
list_for_each_entry(p, &n->partial, lru)
p->slab_cache = s;
#ifdef CONFIG_SLUB_DEBUG
list_for_each_entry(p, &n->full, lru)
p->slab_cache = s;
#endif
}
slab_init_memcg_params(s);
list_add(&s->list, &slab_caches);
return s;
}
-
1.首先将会通过kmem_cache_zalloc()申请kmem_cache空间，值得注意的是该函数申请调用kmem_cache_zalloc()->kmem_cache_alloc()->slab_alloc()，其最终将会通过前面create_boot_cache()初始化创建的kmem_cache来申请slub空间来使用。临时使用的kmem_cache结构形式接收的参数static_cache的内容复制到新分配的缓存中，其大小与object_size相同。早期引导过程中，因此无法对其他CPU进行IPI调用，因此仅刷新本地CPU。
-
2.通过for_each_node_state()遍历各个内存管理节点node,在通过get_node()获取对应节点的slab，如果slab不为空这回遍历部分满slab链，修正每个slab指向kmem_cache的指针，如果开启CONFIG_SLUB_DEBUG，则会遍历满slab链，设置每个slab指向kmem_cache的指针；最后将kmem_cache添加到全局slab_caches链表中。
接下来是创建kmalloc boot cache - create_kmalloc_caches()，来初始化kmalloc_caches表，其最终创建的kmalloc_caches是以{0,96,192,8,16,32,64,128,256,512,1024,2046,4096，8196}为大小的slab表；创建完之后，将设置slab_state为UP，然后将kmem_cache的name成员进行初始化；最后如果配置了CONFIG_ZONE_DMA，将会初始化创建kmalloc_dma_caches表。可以得到size_index与kmalloc_caches的对应关系
我们以通常情况下KMALLOC_MIN_SIZE等于8为例进行说明。size_index[0-23]数组根据对象大小映射到不同的kmalloc_caches[0-13]保存的cache。观察kmalloc_caches[0-13]数组，可见索引即该cache slab块的order。由于最小对象为8（23）字节，kmalloc_caches[0-2]这三个数组元素没有用到，slub使用kmalloc_caches[1]保存96字节大小的对象，kmalloc_caches[2] 保存192字节大小的对象，相当于细分了kmalloc的粒度，有利于减少空间的浪费。kmalloc_caches[0]未使用。
3. 总结
slab分配器中用到了对象这个概念，就是内核中的数据结构以及对该数据结构进行创建和撤销的操作。其核心思想如下
- 将内核中经常使用的对象放到高速缓存中，并且由系统保持为初始的可利用状态，比如进程描述符，内核中会频繁对此数据进行申请和释放
- 当一个新进场创建时，内核就会直接从slab分配器的高速缓存中获取一个已经初始化的对象
- 当进程结束时，该结构所占的页框并不被释放，而是重新返回slab分配器中，如果没有基于对象的slab分配器，内核将花费更多的时间去分配、初始化、已经释放对象。
上图显示了slab、cache及object 三者之间的关系。该图显示了2个大小为3KB 的内核对象和3个大小为7KB的对象，它们位于各自的cache中。slab分配算法采用 cache来存储内核对象。在创建 cache 时，若干起初标记为free的对象被分配到 cache。cache内的对象数量取决于相关slab的大小。例如，12KB slab(由3个连续的4KB页面组成)可以存储6个2KB对象。最初，cache内的所有对象都标记为空闲。当需要内核数据结构的新对象时，分配器可以从cache上分配任何空闲对象以便满足请求。从cache上分配的对象标记为used(使用)。
让我们考虑一个场景，这里内核为表示进程描述符的对象从slab分配器请求内存。在 Linux 系统中，进程描述符属于 struct task_struct 类型，它需要大约1.7KB的内存。当Linux内核创建一个新任务时，它从cache中请求 struct task_struct对象的必要内存。cache 利用已经在slab中分配的并且标记为 free (空闲)的 struct task_struct对象来满足请求。
在Linux中，slab可以处于三种可能状态之一：
- 满的：slab的所有对象标记为使用。
- 空的：slab上的所有对象标记为空闲。
- 部分：slab上的对象有的标记为使用，有的标记为空闲。
slab分配器首先尝试在部分为空的slab中用空闲对象来满足请求。如果不存在，则从空的slab 中分配空闲对象。如果没有空的slab可用，则从连续物理页面分配新的slab，并将其分配给cache；从这个slab上，再分配对象内存。slab分配器提供两个主要优点：
- 减小伙伴算法在分配小块连续内存时所产生的内部碎片问题，因为每个内核数据结构都有关联的cache，每个 cache都由一个或多个slab组成，而slab按所表示对象的大小来分块。因此，当内核请求对象内存时，slab 分配器可以返回刚好表示对象的所需内存。
- 将频繁使用的对象缓存起来，减小分配、初始化和释放的时间开销 ，当对象频繁地被分配和释放时，如来自内核请求的情况，slab 分配方案在管理内存时特别有效。分配和释放内存的动作可能是一个耗时过程。然而，由于对象已预先创建，因此可以从cache 中快速分配。再者，当内核用完对象并释放它时，它被标记为空闲并返回到cache，从而立即可用于后续的内核请求。
对于伙伴系统和slab分配器，就好比“批发商”和“零售商”，“批发商”，是指按页面管理并分配内存的机制；而“零售商”，则是从“批发商”那里批发获取资源，并以字节为单位，管理和分配内存的机制。作为零售商的slab，那么就需要解决两个问题
- 该如何从批发商buddy system批发内存
- 如何管理批发的内存并把这些内存“散卖“出去，如何使这些散内存由更高的使用效率
4. 参考文档
趣谈Linux操作系统
Linux内存管理：slub分配器
操作系统内存分配算法_操作系统基础45-伙伴系统和slab内存分配
