Linux slab分配器-浅析

本文主要以内核Linux 4.19来简单说明slab分配器的大概流程。slab是Linux操作系统的一种内存分配机制，slab分配算法采用cache 存储内核对象。slab 缓存、从缓存中分配和释放对象然后销毁缓存的过程必须要定义一个 kmem_cache 对象，然后对其进行初始化这个特定的缓存包含 32 字节的对象(来自百度百科)。为了防止内存碎片, Linux在slab机制中明确的将伙伴子系统中的page 分成了多组内存大小不同的片段，如96, 192, 2^3,2^4...等，不同大小的片段属于不同的kmem_cache，因此，当用户调用kmalloc申请内存的时候，只会从对应内存大小片段的kmem_cache中去分配。

首先如下是一个kmem_cache结构（Linux中存在多个这样的结构，每个这样的结构可以管理分配对应大小的内存片段），这里只列出了关键的几个成员。

点击(此处)折叠或打开

struct kmem_cache {
struct array_cache __percpu *cpu_cache; // 用于找到空闲内存的结点信息
unsigned int batchcount; // 一次分配或者释放的大小为size的数量
unsigned int limit; // 该kmem最大支持的size数量，也就是几个node的总和
unsigned int shared; // 共享数量
unsigned int size; // 每个内存分配块的大小（这个size包含给用户内存、pad，kasan大小的总和）
unsigned int num; // 每个order的page能分配的最大size个数
unsigned int gfporder; // 需要从order为rfporder的伙伴子系统申请page
gfp_t allocflags; // 申请page的flag
size_t colour;
unsigned int colour_off;
struct kmem_cache *freelist_cache; // 如果管理结构和slag不在一起，就会使用该结构
unsigned int freelist_size; // 管理结构大小
const char *name; // 名字
int object_size; // 用户能在当前kmem_cache申请的最大内存
int align; // 对齐
#ifdef CONFIG_KASAN
struct kasan_cache kasan_info; // 指向kasan结构，主要用于检查内存越界使用的
#endif
unsigned int useroffset; /* Usercopy region offset */
unsigned int usersize; /* Usercopy region size */
struct kmem_cache_node *node[MAX_NUMNODES]; // 记录mem node（numa）的具体信息
}

kmem_cache_node结构如下（该结构表示在numa中的一个内存bank），
点击(此处)折叠或打开

struct kmem_cache_node {
spinlock_t list_lock;
struct list_head slabs_partial; // 用于存放没有完全使用的page
struct list_head slabs_full; // 用于存放完全使用了的page
struct list_head slabs_free; // 用于存放空闲的page,这里的page可能会被释放到伙伴子系统当中
unsigned long total_slabs; /* length of all slab lists */
unsigned long free_slabs; /* length of free slab list only */
unsigned long free_objects; // 空闲的大小为size的个数
unsigned int free_limit; // 空闲个数的最大值
unsigned int colour_next; /* Per-node cache coloring */
struct array_cache *shared; // 共享内存结点
struct alien_cache **alien; /* on other nodes */
unsigned long next_reap; /* updated without locking */
int free_touched; /* updated without locking */
}

从上可以了解到，从伙伴子系统中分配出来的page会被挂到对应内存node的partial/full/free等三个链表。当page刚被申请出来时在free链表，如果该page被部分使用了，则在partial链表，如果全部被使用了，则在full链表。对于array_cache结构如下，该结构是用于分配内存的时候，能快速拿到希望的内存结点而使用的，

点击(此处)折叠或打开

struct array_cache {
unsigned int avail; // cache中可用的内存片段数量
unsigned int limit; // ac中最大可用缓存的片段数量
unsigned int batchcount; // ac一次性申请或者释放的片段数量
unsigned int touched;
void *entry[];// 指向不同内存片段的内存地址
}

上述为kmem_cache的关键结构体，那么用图形表示为，

因此，之间的关系如图，page的lru会链接到mem_node的slabs_xxx链表上，而page的freelist用来记录该order的page的不同片段的起始地址，page->s_mem为page所代码的地址的起始地址。另外分配有些从kmem_cache的ac中分配，然后再是mem_node（ac只是mem_node的一个缓存而已）。

先看看kmem_cache的初始化，初始化栈如下，本章只会对几个函数做出说明，
点击(此处)折叠或打开

start_kernel
mm_init
kmem_cache_init // 初始化kmem_cache
create_boot_cache // 创建启动kmem,用于为创建其他kmem_cache的时候分配结点内存
create_kmalloc_cache // 创建用于分配kmem_cache的结点kmem
create_kmalloc_caches // 创建其他大小的kmem_cache
new_kmalloc_cache // 创建新的一个kmem_cache
create_kmalloc_cache
create_boot_cache
__kmem_cache_create // 初始化kmem_cache结构成员的默认值
kasan_cache_create // 预留Kasan的空间，即增加size大小
set_objfreelist_slab_cache // 设置管理page片段的管理结构位置
set_off_slab_cache // 设置 page片段管理结构不在slab上
set_on_slab_cache // 设置Page片段管理结构在slab上
setup_cpu_cache // 初始化ac,即array_cache结构
enable_cpucache

从上发现，在kmem_cache_init中，需要先调用create_boot_cache，这是为什么呢？这主要是因为后期在创建kmem_cache的时候也会申请内存，但是由于kmem_cache都还没有，又怎么能申请到内存呢，于是增加了一个boot_kmem_cache，这个结构是一个静态结构，不需要分配空间。这样，当初始化了这个结构后，后面去创建其他kmem_cache的时候，就能正常分配结点内存了。

点击(此处)折叠或打开

void __init kmem_cache_init(void)
{
int i;
kmem_cache = &kmem_cache_boot; // 准备初始化boot kmem cache
if (!IS_ENABLED(CONFIG_NUMA) || num_possible_nodes() == 1)
use_alien_caches = 0;
for (i = 0; i < NUM_INIT_LISTS; i++)
kmem_cache_node_init(&init_kmem_cache_node[i]); // 初始化kmem node信息
if (!slab_max_order_set && totalram_pages > (32 << 20) >> PAGE_SHIFT)
slab_max_order = SLAB_MAX_ORDER_HI;
// 初始化 boot kmem_cache
create_boot_cache(kmem_cache, "kmem_cache",
offsetof(struct kmem_cache, node) +
nr_node_ids * sizeof(struct kmem_cache_node *),
SLAB_HWCACHE_ALIGN, 0, 0);
list_add(&kmem_cache->list, &slab_caches); // 添加到slag_caches全局链表
memcg_link_cache(kmem_cache);
slab_state = PARTIAL; // slab_stae设置为PARTIAL，这影响array_cache和node初始化
//初始化用于申请node的结点
kmalloc_caches[INDEX_NODE] = create_kmalloc_cache(
kmalloc_info[INDEX_NODE].name,
kmalloc_size(INDEX_NODE), ARCH_KMALLOC_FLAGS,
0, kmalloc_size(INDEX_NODE));
slab_state = PARTIAL_NODE; // 设置slab_state为PARTAL_NODE, setup_cpu_cache会用到
setup_kmalloc_cache_index_table();
slab_early_init = 0;
{ // 将boot kmem cache的node数据内容和INDEX_NODE的node数据置换
int nid;
for_each_online_node(nid) {
init_list(kmem_cache, &init_kmem_cache_node[CACHE_CACHE + nid], nid);
init_list(kmalloc_caches[INDEX_NODE],
&init_kmem_cache_node[SIZE_NODE + nid], nid);
}
}
// 创建其他大小的kmem_cache，实现就是一个for循环，调用__kmem_cache_create的过程
create_kmalloc_caches(ARCH_KMALLOC_FLAGS);
}

其他的函数没什么说的，下面说说 __kmem_cache_create函数，该函数用来初始化kmem_cache，实现如下

点击(此处)折叠或打开

int __kmem_cache_create(struct kmem_cache *cachep, slab_flags_t flags)
{
size_t ralign = BYTES_PER_WORD;
gfp_t gfp;
int err;
unsigned int size = cachep->size;
size = ALIGN(size, BYTES_PER_WORD); // 对齐
if (flags & SLAB_RED_ZONE) { // kasan对齐相关
ralign = REDZONE_ALIGN;
size = ALIGN(size, REDZONE_ALIGN);
}
if (ralign < cachep->align) {
ralign = cachep->align;
}
if (ralign > __alignof__(unsigned long long))
flags &= ~(SLAB_RED_ZONE | SLAB_STORE_USER);
cachep->align = ralign; //赋值对齐值
cachep->colour_off = cache_line_size();
if (cachep->colour_off < cachep->align)
cachep->colour_off = cachep->align;
if (slab_is_available()) // 申请标记
gfp = GFP_KERNEL;
else
gfp = GFP_NOWAIT;
kasan_cache_create(cachep, &size, &flags); // 如果支持kasan，则为kasan在用户申请内存中，预留空间
size = ALIGN(size, cachep->align);
if (FREELIST_BYTE_INDEX && size < SLAB_OBJ_MIN_SIZE)
size = ALIGN(SLAB_OBJ_MIN_SIZE, cachep->align);
// 这里需要注意，freelist用于管理对应order的page中分出来的大小为size的每个片段索引号，objfreelist, off slab, on slab三者只用其中一个，优先考虑objfreelist,然后是off slab，最后是on slab
if (set_objfreelist_slab_cache(cachep, size, flags)) {
flags |= CFLGS_OBJFREELIST_SLAB;
goto done;
}
if (set_off_slab_cache(cachep, size, flags)) {
flags |= CFLGS_OFF_SLAB;
goto done;
}
if (set_on_slab_cache(cachep, size, flags))
goto done;
return -E2BIG;
done:
cachep->freelist_size = cachep->num * sizeof(freelist_idx_t); // freelist大小
cachep->flags = flags;
cachep->allocflags = __GFP_COMP;
if (flags & SLAB_CACHE_DMA)
cachep->allocflags |= GFP_DMA;
if (flags & SLAB_CACHE_DMA32)
cachep->allocflags |= GFP_DMA32;
if (flags & SLAB_RECLAIM_ACCOUNT)
cachep->allocflags |= __GFP_RECLAIMABLE;
cachep->size = size;
cachep->reciprocal_buffer_size = reciprocal_value(size);
if (OFF_SLAB(cachep)) {
cachep->freelist_cache =
kmalloc_slab(cachep->freelist_size, 0u);
}
err = setup_cpu_cache(cachep, gfp); // 初始化 cpu cache和mem node
if (err) {
__kmem_cache_release(cachep);
return err;
}
return 0;
}

通过上面函数，我们大概知道用户调用kmalloc申请一个内存的时候，内存的分布

如上图，user_size才是用户申请的时候填写的数据大小，后面都是为了检测内存越界而预留的空间。

点击(此处)折叠或打开

static int __ref setup_cpu_cache(struct kmem_cache *cachep, gfp_t gfp)
{
if (slab_state >= FULL) // 刚开始 slab_state状态是DOWN，只有最后都成功了会是FULL
return enable_cpucache(cachep, gfp);
cachep->cpu_cache = alloc_kmem_cache_cpus(cachep, 1, 1);
if (!cachep->cpu_cache)
return 1;
if (slab_state == DOWN) { // 安装boot kmem的node信息
/* Creation of first cache (kmem_cache). */
set_up_node(kmem_cache, CACHE_CACHE);
} else if (slab_state == PARTIAL) {
/* For kmem_cache_node */
set_up_node(cachep, SIZE_NODE); // 安装size node的node信息
} else {
int node;
for_each_online_node(node) { // 为每个mem node申请内存结点
cachep->node[node] = kmalloc_node(
sizeof(struct kmem_cache_node), gfp, node);
BUG_ON(!cachep->node[node]);
kmem_cache_node_init(cachep->node[node]);
}
}
// 初始化ac结点
cachep->node[numa_mem_id()]->next_reap =
jiffies + REAPTIMEOUT_NODE +
((unsigned long)cachep) % REAPTIMEOUT_NODE;
cpu_cache_get(cachep)->avail = 0;
cpu_cache_get(cachep)->limit = BOOT_CPUCACHE_ENTRIES;
cpu_cache_get(cachep)->batchcount = 1;
cpu_cache_get(cachep)->touched = 0;
cachep->batchcount = 1;
cachep->limit = BOOT_CPUCACHE_ENTRIES;
return 0;
}

从上面知道，初始化的时候，ac的limit都是1，那么什么时候会改变limit的值呢？栈如下,
点击(此处)折叠或打开

start_kernel
kmem_cache_init_late
enable_cpucache // 这里会调整ac等的limit值

内存申请函数kmalloc，申请规则：kmalloc会先从对应kmem_cache的ac缓存中去获取内存片段，如果无法从ac中获取到内存片段，则尝试从node的shared中分配，如果依然无法分配则考虑从mem node的链表上去获取page，当然如果链表上也没有了，就只有从最慢的的伙伴子系统中去分配了，函数调用栈如下，

点击(此处)折叠或打开

kmalloc
kmalloc_large // 用户传入的size大于KMALLOC_MAX_CACHE_SIZE的时候，用kmalloc_order，实际就是从伙伴子系统中分配内存
kmalloc_order
alloc_pages
__kmalloc
__do_kmalloc
kmalloc_slab // 通过用户传入的size，查找需要从哪个kmem_cache中分配
slab_alloc
__do_cache_alloc
____cache_alloc // 从kmem_cache中分配内存
kasan_kmalloc // 将内存object_size没有用完的部分，填充kasan red pading

下面重点讲解 ___cache_alloc函数，该函数完成内存从kmem_cache中的分配，实现如下
点击(此处)折叠或打开

static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)
{
void *objp;
struct array_cache *ac;
check_irq_off();
ac = cpu_cache_get(cachep); // 获取到当前kmem_cache的arrary_cache成员
if (likely(ac->avail)) { // 判断ac中是否还有未分配的内存片段，有就直接赋值分配。goto out
ac->touched = 1;
objp = ac->entry[--ac->avail];
STATS_INC_ALLOCHIT(cachep);
goto out;
}
// 因为ac中没有可用于分配的内存片段，则需要从slabs_partial或者slabs_free链表中去要
STATS_INC_ALLOCMISS(cachep);
objp = cache_alloc_refill(cachep, flags);
ac = cpu_cache_get(cachep);
out：
if (objp) // 如果分配内存成功，将ac中对该内存信息，进行清除，以免再次被分配
kmemleak_erase(&ac->entry[ac->avail]);
return objp;
}

从node链表slabs_partial、slabs_free中去获取内存片段的函数实现如下，
点击(此处)折叠或打开

static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags)
{
int batchcount;
struct kmem_cache_node *n;
struct array_cache *ac, *shared;
int node;
void *list = NULL;
struct page *page;
check_irq_off();
node = numa_mem_id();
ac = cpu_cache_get(cachep); // 获取ac
batchcount = ac->batchcount; // 得到一次性要从node中申请的片段个数
if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {
batchcount = BATCHREFILL_LIMIT;
}
n = get_node(cachep, node); // 得到cache对应的Node结构
BUG_ON(ac->avail > 0 || !n);
shared = READ_ONCE(n->shared); // 如果存在没有共享内存片段，并且结点从也没有内存片段，则需要跳转到direct_grow去向伙伴子系统进货
if (!n->free_objects && (!shared || !shared->avail))
goto direct_grow;
spin_lock(&n->list_lock);
shared = READ_ONCE(n->shared);
// 发现有共享内存片段，则优先从共享中申请batchcount个片段
if (shared && transfer_objects(ac, shared, batchcount)) {
shared->touched = 1;
goto alloc_done;
}
while (batchcount > 0) { // 还有片段未申请完，则调用get_first_slab从node的链表上获取
/* Get slab alloc is to come from. */
page = get_first_slab(n, false);
if (!page)
goto must_grow;
check_spinlock_acquired(cachep);
batchcount = alloc_block(cachep, ac, page, batchcount);
fixup_slab_list(cachep, n, page, &list); // 因为page中的片段被使用，则需要调整page所在的链表
}
must_grow:
n->free_objects -= ac->avail;
alloc_done:
spin_unlock(&n->list_lock);
fixup_objfreelist_debug(cachep, &list);
direct_grow: // 没有足够的内存片段，则向伙伴子系统进货
if (unlikely(!ac->avail)) {
/* Check if we can use obj in pfmemalloc slab */
if (sk_memalloc_socks()) {
void *obj = cache_alloc_pfmemalloc(cachep, n, flags);
if (obj)
return obj;
}
page = cache_grow_begin(cachep, gfp_exact_node(flags), node); // 从伙伴子系统申请一个order的page
/*
* cache_grow_begin() can reenable interrupts,
* then ac could change.
*/
ac = cpu_cache_get(cachep);
if (!ac->avail && page)
alloc_block(cachep, ac, page, batchcount); // 释放到ac中缓存起来
cache_grow_end(cachep, page);
if (!ac->avail)
return NULL;
}
ac->touched = 1;
return ac->entry[--ac->avail]; // 返回第一个片段
}

get_first_slab实现如下，
点击(此处)折叠或打开

static struct page *get_first_slab(struct kmem_cache_node *n, bool pfmemalloc)
{
struct page *page;
assert_spin_locked(&n->list_lock);// 优先从slabs_partial中去获取page
page = list_first_entry_or_null(&n->slabs_partial, struct page, lru);
if (!page) {
n->free_touched = 1;
page = list_first_entry_or_null(&n->slabs_free, struct page,
lru);
if (page)
n->free_slabs--;
}
if (sk_memalloc_socks())
page = get_valid_first_slab(n, page, pfmemalloc);
return page;
}

fixup_slab_list实现如下，
点击(此处)折叠或打开

static inline void fixup_slab_list(struct kmem_cache *cachep,
struct kmem_cache_node *n, struct page *page,
void **list)
{
list_del(&page->lru);
if (page->active == cachep->num) {
list_add(&page->lru, &n->slabs_full);
if (OBJFREELIST_SLAB(cachep)) {
page->freelist = NULL;
}
} else
list_add(&page->lru, &n->slabs_partial);
}

内存释放函数kfree, 释放规则：kfree会优先将内存片段释放到kmem_cache的ac缓存中，如果ac缓存满了，则需要将一定数量的内存片段释放到mem node的链表上，如果mem node的链表也超过了限制，就将page释放到伙伴子系统当中。为什么要设置限制？就是防止slab占用过多的内存，而导致内核系统中其他区间可用内存不足。函数调用栈如下，
点击(此处)折叠或打开

kfree
virt_to_cache // 通过虚拟地址获取对应的kmem_cache结构
__cache_free
kasan_slab_free // 释放kasan
___cache_free // 释放内存片段到kmem_cache

___cache_free实现如下，
点击(此处)折叠或打开

void ___cache_free(struct kmem_cache *cachep, void *objp,
unsigned long caller)
{
struct array_cache *ac = cpu_cache_get(cachep); // 获取到ac
check_irq_off();
kmemleak_free_recursive(objp, cachep->flags);
objp = cache_free_debugcheck(cachep, objp, caller);
if (nr_online_nodes > 1 && cache_free_alien(cachep, objp))
return;
if (ac->avail < ac->limit) { // 如果ac中缓存的数量没有超过限制，就释放到ac中缓存起来
STATS_INC_FREEHIT(cachep);
} else { // ac中的缓存超过限制，则释放到node对应的链表上
STATS_INC_FREEMISS(cachep);
cache_flusharray(cachep, ac);
}
if (sk_memalloc_socks()) {
struct page *page = virt_to_head_page(objp);
if (unlikely(PageSlabPfmemalloc(page))) {
cache_free_pfmemalloc(cachep, page, objp);
return;
}
}
ac->entry[ac->avail++] = objp;
}

cache_flusharray释放一个batchcount的内存片段到node的链表上，实现如下
点击(此处)折叠或打开

static void cache_flusharray(struct kmem_cache *cachep, struct array_cache *ac)
{
int batchcount;
struct kmem_cache_node *n;
int node = numa_mem_id();
LIST_HEAD(list);
batchcount = ac->batchcount;
check_irq_off();
n = get_node(cachep, node);
spin_lock(&n->list_lock);
if (n->shared) { // 存在共享，则优先释放到node的共享结点上
struct array_cache *shared_array = n->shared;
int max = shared_array->limit - shared_array->avail;
if (max) {
if (batchcount > max)
batchcount = max;
memcpy(&(shared_array->entry[shared_array->avail]),
ac->entry, sizeof(void *) * batchcount);
shared_array->avail += batchcount;
goto free_done;
}
}
free_block(cachep, ac->entry, batchcount, node, &list); // 释放ac到node的链表上，如果存在node中也超出了限制，则把free链表上的page挂到list指向的链表上
free_done:
spin_unlock(&n->list_lock);
slabs_destroy(cachep, &list); // 将list上面挂的page释放到伙伴子系统
ac->avail -= batchcount; // 调整ac缓存
memmove(ac->entry, &(ac->entry[batchcount]), sizeof(void *)*ac->avail);
}

free_block实现，
点击(此处)折叠或打开

static void free_block(struct kmem_cache *cachep, void **objpp,
int nr_objects, int node, struct list_head *list)
{
int i;
struct kmem_cache_node *n = get_node(cachep, node);
struct page *page;
n->free_objects += nr_objects;
// 依次释放ac中的每个内存片段
for (i = 0; i < nr_objects; i++) {
void *objp;
struct page *page;
objp = objpp[i];
page = virt_to_head_page(objp);
list_del(&page->lru);
check_spinlock_acquired_node(cachep, node);
slab_put_obj(cachep, page, objp);
STATS_DEC_ACTIVE(cachep);
if (page->active == 0) { // 如果active为0表示，该page的所有片段都已经被释放，空闲
list_add(&page->lru, &n->slabs_free);
n->free_slabs++;
} else {
list_add_tail(&page->lru, &n->slabs_partial);
}
}
// 这里如果free_objects数量超出了free_limit限制，则释放slabs_free上面的page
while (n->free_objects > n->free_limit && !list_empty(&n->slabs_free)) {
n->free_objects -= cachep->num;
page = list_last_entry(&n->slabs_free, struct page, lru);
list_move(&page->lru, list);
n->free_slabs--;
n->total_slabs--;
}
}

什么是kasan？ kasan是Linux内核引入的一种专门检测slab内存越界问题的，通过给内存打上特定的pad来实现，这个操作比较消耗内存。

BugMan

Linux slab分配器-浅析