Linux slab分配器-浅析

本文主要以内核Linux 4.19来简单说明slab分配器的大概流程。slab是操作系统的一种机制，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来实现，这个操作比较消耗内存。