Slub分配器的来龙去脉
以下文章来源于人人都是极客 ，作者贺东升
工程师们自己的Linux底层技术社区，分享体系架构、内核、网络、安全和驱动。
slab分配器设计的需求
在Linux内核的内存子系统中，伙伴系统无疑处于内存管理的核心地带，但是如果将内存管理从逻辑上分层，它的位置则处于最底层。Buddy是所有物理内存的管家，不论使用何种接口申请内存都要经由伙伴系统进行分配。但是，伙伴系统管理的物理内存是以页为单位，以4K页为例，它也包含了4096个字节。但是无论是内核自己还是用户程序，在日常的使用中都很少会需要使用四千多字节大小的内存。试想如果我们仅需要为10个字符的字符串分配内存，但是伙伴系统却给了我们一页，那这一页剩余没有使用的内存就浪费了，而且这个浪费近乎奢侈。除了浪费的问题， 还有一个更需要关心的问题是，在这样的分配情况下，如果分配非常频繁，系统可能很快就会面临严重的碎片化问题。因为频繁使用的数据结构也会频繁的分配和释放，加速生产内存碎片。另外，直接调用伙伴系统的操作对系统的数据和指令高速缓存也有很大的影响。所以，基于以上的原因，也源于现实需求，内核需要一种轻量的、快速的、灵活的新型内存分配器，最主要的是，它可以提供小块内存的分配。为了实现这样的小内存分配器，Sun公司的J.Bonwick首先在Solaris 2.4中设计并实现了slab分配器，并对其开源。在Linux中也实现了具有相同的基本设计思想的同名分配器slab。
slab、slob和slub关系
slab、slob和slub都是小内存分配器，slab是slob和slub实现的基础，而slob和slub是针对slab在不同场景下的优化版本。在slab引入Linux的很多年内，其都是Linux内核管理对象缓冲区的主流算法。并且由于slab的实现非常复杂，很长一段时间内都少有对它的改动。随着多处理器的发展和NUMA架构的广泛应用，slab的不足也逐渐显现。slab的缓存队列管理复杂，其用于管理的数据结构存储开销大，对NUMA支持复杂，slab着色机制效果不明显。这些不足让slab很难在两种场景下提供最优的性能：小型嵌入式系统和配备有大量物理内存的大规模并行系统。对于小型嵌入式系统来说，slab分配器的代码量和复杂性都太高；对于大规模并行系统，slab用于自身管理的数据结构就需要占用很多G字节内存。针对slab的不足，内核开发人员Christoph Lameter在在内核版本2.6开发期间，引入了新的Slub分配器。Slub简化了slab一些复杂的设计，但保持slab的基本设计思想。同时，一种新的针对小型嵌入式系统的分配器slob也被引入，为了适应嵌入式系统的特点，slob进行了特别的优化，以大幅减少代码量（slob只有大约600行代码）。
slab层在内存管理子系统的层次
slab层可以理解为一个通用层，其包含了slab、slob和slub，至于底层具体使用哪种分配器可以通过配置内核选项进行选择。对于内核的其他模块，则不需要关注底层使用了哪个分配器。因为为了保证内核的其他模块都可以无缝迁移到Slub/slob，所有分配器的接口都是相同的，它们都实现了一组特定的接口用于内存分配。下图为Slab层在内存管理中的层次图：
逻辑上看，slab层位于伙伴系统之上。因为Buddy是最底层的分配器，Slub需要先向Buddy申请内存，而不能越过Buddy获取page。从Buddy申请到内存后，Slub才可以对其进行自己的操作。
slub分配器框架
下图是在读完宋牧春大侠的《图解Slub》后，我也总结了一张Slub分配器框架图，可以大致的看到Slub的框架。Slub的框架如下图（图片很大，可以放大）：
这篇文章（原文链接以置文末）中用了一个通俗易懂的例子来介绍Slub的工作原理，我觉的这个例子很恰当，所以这里继续借举一下。
每个数组元素对应一种大小的内存，可以把一个kmem_cache结构体看做是一个特定大小内存的零售商，整个Slub系统中有很多个这样的零售商，每个“零售商”只“零售”特定大小的内存，例如：有的“零售商”只"零售"8Byte大小的内存，有的只”零售“16Byte大小的内存。——引自luken.《linux内核内存管理slub算法(一)原理》
Slub的工作原理和日常生产生活的产销环节很类似，所以为了清晰直观的看到其工作原理，我把这个过程画了一幅图来表示，如下图：
每个零售商(kmem_cache)有两个“部门”，一个是“仓库”：kmem_cache_node，一个“营业厅”：kmem_cache_cpu。“营业厅”里只保留一个slab，只有在营业厅(kmem_cache_cpu)中没有空闲内存的情况下才会从仓库中换出其他的slab。所谓slab就是零售商(kmem_cache)批发的连续的整页内存，零售商把这些整页的内存分成许多小内存，然后分别“零售”出去，一个slab可能包含多个连续的内存页。slab的大小和零售商有关。——引自luken.《linux内核内存管理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;
/* size = object_size + 对象后面下个空闲对象的指针的size */
int size; /* The size of an object including meta data */
int object_size; /* The size of an object without meta data */
/* object首地址 + offset = 下一个空闲对象的指针地址 */
int offset; /* Free pointer offset. */
int cpu_partial; /* Number of per cpu partial objects to keep around */
/*
* oo表示存放最优slab的order和object的数量
* 低16位表示对象数，高16位表示slab的order
*/
struct kmem_cache_order_objects oo;
/* Allocation and freeing of slabs */
struct kmem_cache_order_objects max;
/*
* 最小slab只需要足够存放一个对象。当设备长时间运行以后，内存碎片化严重，
* 分配连续物理页很难成功，如果分配最优slab失败，就分配最小slab。
*/
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 */
// 当slab长度不是对象长度的整数倍的时候，尾部有剩余部分，保存在reserved中
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 */
#ifdef CONFIG_SYSFS
struct kobject kobj; /* For sysfs */
#endif
#ifdef CONFIG_MEMCG
struct memcg_cache_params memcg_params;
int max_attr_size; /* for propagation, maximum size of a stored attr */
#ifdef CONFIG_SYSFS
struct kset *memcg_kset;
#endif
#endif
#ifdef CONFIG_NUMA
/*
* Defragmentation by allocating from a remote node.
*/
int remote_node_defrag_ratio;
#endif
#ifdef CONFIG_SLAB_FREELIST_RANDOM
unsigned int *random_seq;
#endif
#ifdef CONFIG_KASAN
struct kasan_cache kasan_info;
#endif
struct kmem_cache_node *node[MAX_NUMNODES]; /* 每个NUMA节点都有一个kmem_cache_node */
};
根据是否打开Slub Debug，next object指针可以有两种方式放置，如果打开了Slub Debug，则采用指针外置式；反之，采用指针内置式。两种指针放置方式如下图：
指针外置式
指针内置式
指针内置式的方法实际上是复用了object的前8个字节，因为在object被分配出去之前，这一段内存具体存放什么内容并不重要，所以可以利用这一段内存来保存下一个free object的地址。
kmem_cache_cpu
struct kmem_cache_cpu {
/* 指向下一个空闲的object，用于快速找到可用对象 */
void **freelist; /* Pointer to next available object */
/*
* 要保证tid和kmem_cache是由同一个CPU访问。
* 开启了内核抢占后，访问tid和kmem_cache的CPU可能不是同一个CPU，
* 所以要检查是否匹配，直到它们是由同一个CPU进行访问
*/
unsigned long tid; /* Globally unique transaction id */
/* 指向当前使用的slab */
struct page *page; /* The slab from which we are allocating */
/* 指向当前cpu上缓存的部分空闲slab链表 */
struct page *partial; /* Partially allocated frozen slabs */
#ifdef CONFIG_SLUB_STATS
/*
* 记录对slab操作的状态变化，这个stat非常重要，
* 通过这个stat就大概了解object从申请到释放经过了哪些步骤
*/
unsigned stat[NR_SLUB_STAT_ITEMS];
#endif
};
kmem_cache_node
struct kmem_cache_node {
spinlock_t list_lock;
/* 此处省略掉SLAB的配置 */
#ifdef CONFIG_SLUB
/* 挂入kmem_cache_node中的slab数量 */
unsigned long nr_partial;
/* 指向当前内存节点上的部分空闲slab链表 */
struct list_head partial;
#ifdef CONFIG_SLUB_DEBUG
atomic_long_t nr_slabs;
atomic_long_t total_objects;
struct list_head full;
#endif
#endif
};
page中描述Slub信息的字段：
struct page {
/* 如果flag设置成PG_slab,表示页属于slub分配器 */
unsigned long flags;
union {
struct address_space *mapping;
/* 指向当前slab中第一个object */
void *s_mem; /* slab first object */
atomic_t compound_mapcount; /* first tail page */
};
union {
pgoff_t index; /* Our offset within mapping. */
/* 指向当前slab中第一个空闲的object */
void *freelist; /* sl[aou]b first free object */
};
union {
unsigned counters;
struct {
union {
atomic_t _mapcount;
unsigned int active; /* SLAB */
struct { /* SLUB */
/* 该slab中已经分配使用的object数量 */
unsigned inuse:16;
/* 该slab中的所有object数量 */
unsigned objects:15;
/*
* 如果slab在kmem_cache_cpu中，表示处于冻结状态；
* 如果slab在kmem_cache_node的部分空闲slab链表中，表示处于解冻状态
*/
unsigned frozen:1;
};
int units; /* SLOB */
};
atomic_t _refcount;
};
};
union {
/* 作为链表节点加入到kmem_cache_node的部分空闲slab链表中
struct list_head lru; /* Pageout list */
struct dev_pagemap *pgmap;
struct { /* slub per cpu partial pages */
struct page *next; /* Next partial slab */
int pages; /* Nr of partial slabs left */
int pobjects; /* Approximate # of objects */
};
struct rcu_head rcu_head;
struct {
unsigned long compound_head; /* If bit zero is set */
unsigned int compound_dtor;
unsigned int compound_order;
};
};
union {
unsigned long private;
struct kmem_cache *slab_cache; /* SL[AU]B: Pointer to slab */
};
......
}
Slub的分配过程
Slub的分配流程大致如下：首先从kmem_cache_cpu中分配，如果没有则从kmem_cache_cpu的partial链表分配，如果还没有则从kmem_cache_node中分配，如果kmem_cache_node中也没有，则需要向伙伴系统申请内存。
Slub的分配接口是kmem_cache_malloc()。其分配object的流程大概如下：首先在kmem_cache_cpu所使用的slab中查找free object，如果当前slab中有free object，则返回这个object。如果当前slab没有free object，就要看Slub是否开启了kmem_cache_cpu的Partial队列，如果开启了partial队列，就在Partial队列中查看有没有free object的slab，如果有的话就选定这个slab，并返回其free object。如果kmem_cache_cpu的partial链表中也没有拥有free object的slab，则在kmem_cache_node中查找。如果kmem_cache_node中的slab有free object，则选定这个slab并返回free object。如果kmem_cache_node中也没有free object，则需要向伙伴系统申请内存，制作新的slab。
创建slab缓存(kmem_cache)的函数分析
斗胆分析一下slab缓存的创建过程，新手小白分析内核代码，分析的可能不够深度和完整，如有不对还请各路高手指教，提前谢过。
函数调用流程：
kmem_cache_create()
——> kmem_cache_create_usercopy()
——> create_cache()
——> __kmem_cache_create()
——> kmem_cache_open()
下面是每个函数的主干分析，代码有精简。
kmem_cache_create()：
kmem_cache_create()里继续调用了kmem_cache_create_usercopy()。
kmem_cache_create() {
return kmem_cache_create_usercopy(name, size, align, flags, 0, 0, ctor);
}
kmem_cache_create_usercopy()：
kmem_cache_create_usercopy() {
struct kmem_cache *s = NULL;
const char *cache_name;
/*
* Some allocators will constraint the set of valid flags to a subset
* of all flags. We expect them to define CACHE_CREATE_MASK in this
* case, and we'll just provide them with a sanitized version of the
* passed flags.
*/
flags &= CACHE_CREATE_MASK;
/* 定义这个缓存的名字，用于在/proc/slabinfo中显示 */
cache_name = kstrdup_const(name, GFP_KERNEL);
/* kmem_cache结构，并返回其地址 */
s = create_cache(cache_name, size,
calculate_alignment(flags, align, size),
flags, useroffset, usersize, ctor, NULL, NULL);
return s;
}
create_cache()：
create_cache() {
struct kmem_cache *s;
int err;
/* 为kmem_cache结构申请一段内存并清零 */
s = kmem_cache_zalloc(kmem_cache, GFP_KERNEL);
/* 初始化kmem_cache结构的部分成员 */
s->name = name;
s->size = s->object_size = object_size;
s->align = align;
s->ctor = ctor;
s->useroffset = useroffset;
s->usersize = usersize;
/* 核心函数，slub/slab/slob都实现了这个函数 */
err = __kmem_cache_create(s, flags);
/* 将新创建的kmem_cache加入slab caches链表 */
list_add(&s->list, &slab_caches);
return s;
}
__kmem_cache_create()：
__kmem_cache_create() {
int err;
/* 在kmem_cache_open中处理剩余的结构成员，如min_partial、cpu_partial等 */
err = kmem_cache_open(s, flags);
}
kmem_cache_open()：
kmem_cache_open() {
/* 设置kmem_cache中的min_partial,它表示kmem_cache_node中partial链表可挂入的slab数量 */
set_min_partial(s, ilog2(s->size) / 2);
/* 设置kmem_cache中的cpu_partial,它表示per cpu partial上所有slab中free object总数 */
set_cpu_partial(s);
/* 为每个节点分配kmem_cache_node */
if (!init_kmem_cache_nodes(s))
goto error;
/* 为kmem_cache_cpu变量创建每CPU副本 */
if (alloc_kmem_cache_cpus(s))
return 0;
}
分配对象(object)的函数分析
函数调用流程：
kmem_cache_alloc()
——> slab_alloc()
——> slab_alloc_node()
——> __slab_alloc()
——> ___slab_alloc()
kmem_cache_alloc()：
kmem_cache_alloc() {
/* 直接调用slab_alloc */
void *ret = slab_alloc(s, gfpflags, _RET_IP_);
return ret;
}
slab_alloc()：
slab_alloc() {
return slab_alloc_node(s, gfpflags, NUMA_NO_NODE, addr);
}
slab_alloc_node()：
slab_alloc_node() {
void *object;
struct kmem_cache_cpu *c;
struct page *page;
redo:
/*
* 要保证tid和kmem_cache是由同一个CPU访问。但是如果配置了CONFIG_PREEMPT = y，
* 即开启了内核抢占后，访问tid和kmem_cache的CPU可能不是同一个CPU，所以要检查
* 是否匹配，直到它们是由同一个CPU进行访问。
*
* 内核态抢占的时机是：
* 1.中断处理函数返回内核空间之前会检查请求重新调度的标志(TIF_NEED_RESCHED)，
* 如果置位则调用preempt_schedule_irq()执行抢占。
* 2. 当内核从non-preemptible(禁止抢占)状态变成preemptible(允许抢占)的时候。
*/
do {
tid = this_cpu_read(s->cpu_slab->tid); /* 访问当前CPU的per CPU变量的副本的tid */
c = raw_cpu_ptr(s->cpu_slab);
} while (IS_ENABLED(CONFIG_PREEMPT) && /* 检查是否开启了内核抢占 */
unlikely(tid != READ_ONCE(c->tid)));
barrier(); /* 内存屏障，消除指令乱序执行的影响 */
object = c->freelist; /* 下一个free object的地址 */
page = c->page; /* 当前使用的slab */
if (unlikely(!object || !node_match(page, node))) {
/* 调用核心函数__slab_alloc() */
object = __slab_alloc(s, gfpflags, node, addr, c);
stat(s, ALLOC_SLOWPATH);
} else {
void *next_object = get_freepointer_safe(s, object);
if (unlikely(!this_cpu_cmpxchg_double(
s->cpu_slab->freelist, s->cpu_slab->tid,
object, tid,
next_object, next_tid(tid)))) {
note_cmpxchg_failure("slab_alloc", s, tid);
goto redo;
}
prefetch_freepointer(s, next_object);
stat(s, ALLOC_FASTPATH);
}
maybe_wipe_obj_freeptr(s, object);
/* 如果gfpflags标志需要对object对象的内存清零 */
if (unlikely(slab_want_init_on_alloc(gfpflags, s)) && object)
memset(object, 0, s->object_size);
slab_post_alloc_hook(s, gfpflags, 1, &object);
return object;
}
__slab_alloc()：
__slab_alloc() {
void *p;
unsigned long flags;
/*
* 关中断。关闭当前处理器上的所有中断处理
*
* local_irq_save()将当前的中断状态(开或关)
* 保存在flags中然后再禁用处理器上的中断。
*
* 与local_irq_save不同，local_irq_disable()
* 不保存状态而关闭本地处理器的中断服务。
*/
local_irq_save(flags);
#ifdef CONFIG_PREEMPT
/*
* 在关中断之前，可能已经被抢占并被调度在不同的CPU上，
* 所以需要重新加载CPU区域的指针。
*/
c = this_cpu_ptr(s->cpu_slab);
#endif
/* 调用核心函数___slab_alloc() */
p = ___slab_alloc(s, gfpflags, node, addr, c);
/*
* 恢复本地处理器的中断。
*
* local_irq_restore()将local_irq_save()保存的状态值(flags)恢复，
* 注意是恢复之前的中断状态，不一定会开启中断。如果之前的状态是
* 开中断，就打开中断；如果之前的状态是关中断，就关闭中断。
* 而local_irq_enable()会无条件开启中断，所以可能会破坏之前的中
* 断环境。所以local_irq_restore()比local_irq_enable()更安全。
*/
local_irq_restore(flags);
return p;
}
slub的frozen（冻结）和unfrozen（解冻）
如果cpu1的kcmem_cache_cpu的slab是frozen, 那么cpu1可以从该slab中取出或放回obj，但是cpu2不能从该slab中取obj, 只能把obj还给该slab。另外，cpu partial上的slab都是frozen状态。node partial上的slab都是unfrozen。耗尽kmem_cache_cpu的slab的obj后解冻slab。