一、原理介绍

linux系统中，slab分配器用于分配比页更小的内存，用kmem_cache结构管理page对应内存页面上小块内存对象，然后让该page指向kmem_cache，由kmem_cache_node结构管理多个page。

在SLAB分配器中，它把一个内存页面或者一组连续的内存页面，划分成大小相同的块，其中这一个小的内存块就是SLAB对象，但是这一组连续的内存页面中不只是SLAB对象，还有SLAB管理头和着色区。

二、数据结构

1、管理头 kmem_cache

struct array_cache {
    unsigned int avail;     // 当前可用对象的数目
    unsigned int limit;     // 允许容纳对象的最大数目
    void *entry[];          // 指向对象数组
};
struct kmem_cache {
    struct array_cache __percpu *cpu_cache;   // __precpu类型，每个CPU都有一个该变量
    unsigned int size;                        // cache大小
    slab_flags_t flags;                       // slab标志
    unsigned int num;                         // 对象个数
    unsigned int gfporder;                    // 分配内存页面的order
    gfp_t allocflags;
    size_t colour;                            // 着色区大小
    unsigned int colour_off;                  // 着色区的开始偏移
    const char *name;                         // 本SLAB的名字
    struct list_head list;                    // 所有的SLAB都要链接起来
    int refcount;                             // 引用计数
    int object_size;                          // 对象大小
    int align;                                // 对齐大小
    struct kmem_cache_node *node[MAX_NUMNODES]; // 指向管理kmemcache的上层结构
};

2、初始化 kmem_cache

// 全局静态定义
static struct kmem_cache kmem_cache_boot = {
    .batchcount = 1,
    .limit = BOOT_CPUCACHE_ENTRIES,
    .shared = 1,
    .size = sizeof(struct kmem_cache),
    .name = "kmem_cache",
};

void __init kmem_cache_init(void)
{
    int i;

    kmem_cache = &kmem_cache_boot;

    for (i = 0; i < NUM_INIT_LISTS; i++)
        kmem_cache_node_init(&init_kmem_cache_node[i]);
    
    // 建立保存kmem_cache结构的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);
    
    // 加入全局slab_caches链表中
    list_add(&kmem_cache->list, &slab_caches);
    {
        int nid;
        for_each_online_node(nid) {
            init_list(kmem_cache, &init_kmem_cache_node[CACHE_CACHE + nid], nid);
            init_list(kmalloc_caches[KMALLOC_NORMAL][INDEX_NODE],                      &init_kmem_cache_node[SIZE_NODE + nid], nid);
        }
    }
    
    // 建立kmalloc函数使用的的kmem_cache
    create_kmalloc_caches(ARCH_KMALLOC_FLAGS);
}

3、内存节点 kmem_cache_node

#define NUM_INIT_LISTS (2 * MAX_NUMNODES)
static struct kmem_cache_node __initdata init_kmem_cache_node[NUM_INIT_LISTS];

struct kmem_cache_node {
    spinlock_t list_lock;             // 自旋锁
    struct list_head slabs_partial;   // 有一部分空闲对象的kmem_cache结构
    struct list_head slabs_full;      // 没有空闲对象的kmem_cache结构
    struct list_head slabs_free;      // 对象全部空闲kmem_cache结构
    unsigned long total_slabs;        // 一共多少kmem_cache结构
    unsigned long free_slabs;         // 空闲的kmem_cache结构
    unsigned long free_objects;       // 空闲的对象
    unsigned int free_limit;
};
static void __init init_list(struct kmem_cache *cachep, struct kmem_cache_node *list,
    int nodeid)
{
    struct kmem_cache_node *ptr;
    // 分配新的 kmem_cache_node 结构的空间
    ptr = kmalloc_node(sizeof(struct kmem_cache_node), GFP_NOWAIT, nodeid);
    BUG_ON(!ptr);
    // 复制初始时的静态kmem_cache_node结构
    memcpy(ptr, list, sizeof(struct kmem_cache_node));
    spin_lock_init(&ptr->list_lock);
    MAKE_ALL_LISTS(cachep, ptr, nodeid);
    // 设置kmem_cache_node的地址
    cachep->node[nodeid] = ptr;
}

4、获取内存页面

cache_grow_begin函数会为kmem_cache结构分配用来存放对象的页面，随后会调用与之对应的cache_grow_end函数，把页面挂载到kmem_cache_node结构的链表中，并让页面指向kmem_cache结构。

static void slab_map_pages(struct kmem_cache *cache, struct page *page,void *freelist)
{
    // 页面结构指向kmem_cache结构
    page->slab_cache = cache;
    // 指向空闲对象的链表
    page->freelist = freelist;
}
static struct page *cache_grow_begin(struct kmem_cache *cachep,
    gfp_t flags, int nodeid)
{
    void *freelist;
    size_t offset;
    gfp_t local_flags;
    int page_node;
    struct kmem_cache_node *n;
    struct page *page;

    WARN_ON_ONCE(cachep->ctor && (flags & __GFP_ZERO));
    local_flags = flags & (GFP_CONSTRAINT_MASK|GFP_RECLAIM_MASK);
    // 获取页面
    page = kmem_getpages(cachep, local_flags, nodeid);
    // 获取页面所在的内存节点号
    page_node = page_to_nid(page);
    // 根据内存节点获取对应kmem_cache_node结构
    n = get_node(cachep, page_node);
    // 分配管理空闲对象的数据结构
    freelist = alloc_slabmgmt(cachep, page, offset,
            local_flags & ~GFP_CONSTRAINT_MASK, page_node);
    // 让页面中相关的字段指向kmem_cache和空闲对象
    slab_map_pages(cachep, page, freelist);
    // 初始化空闲对象管理数据
    cache_init_objs(cachep, page);
    return page;
}

static void cache_grow_end(struct kmem_cache *cachep, struct page *page)
{
    struct kmem_cache_node *n;
    void *list = NULL;
    if (!page)
        return;
    // 初始化结page构的slab_list链表
    INIT_LIST_HEAD(&page->slab_list);
    // 根据内存节点获取对应kmem_cache_node结构.
    n = get_node(cachep, page_to_nid(page));
    spin_lock(&n->list_lock);
    // slab计数增加
    n->total_slabs++;
    if (!page->active) {
        // 把这个page结构加入到kmem_cache_node结构的空闲链表中
        list_add_tail(&page->slab_list, &n->slabs_free);
        n->free_slabs++;
    } 
    spin_unlock(&n->list_lock);
}

三、分配过程

slab分配对象的流程如下：根据分配请求查找对应的kmem_cache结构，然后获取arry_cache结构，最后分配对象；
如果未找到，则在kmem_cache对应的kmem_cache_node结构中查找有空闲对象的kmem_cache；
如果还未找到，则分配内存页面新增kmem_cache结构。

1、分配函数入口：kmalloc

kmalloc函数，SLAB分配接口，用于分配小的缓冲区，或者数据结构分配实例空间。
kmalloc函数在查找size对应的kmem_cache后，调用slab_alloc进行对象分配。

static __always_inline void *__do_kmalloc(size_t size, gfp_t flags,unsigned long caller)
{
    struct kmem_cache *cachep;
    void *ret;
    if (unlikely(size > KMALLOC_MAX_CACHE_SIZE))
        return NULL;
    
    // 查找size对应的kmem_cache
    cachep = kmalloc_slab(size, flags);    
    if (unlikely(ZERO_OR_NULL_PTR(cachep)))
        return cachep;
    
    // 分配对象
    ret = slab_alloc(cachep, flags, caller);
    return ret;
}

void *__kmalloc(size_t size, gfp_t flags)
{
    return __do_kmalloc(size, flags, _RET_IP_);
}
static __always_inline void *kmalloc(size_t size, gfp_t flags)
{
    return __kmalloc(size, flags);
}

2、查找kmem_cache：kmalloc_slab

根据size和flags作为全局数组的下标，返回数组内容作为kmem_cache。

enum kmalloc_cache_type {
    KMALLOC_NORMAL = 0,
    KMALLOC_RECLAIM,
#ifdef CONFIG_ZONE_DMA
    KMALLOC_DMA,
#endif
    NR_KMALLOC_TYPES
};
struct kmem_cache *kmalloc_caches[NR_KMALLOC_TYPES][KMALLOC_SHIFT_HIGH + 1] __ro_after_init = { static u8 size_index[24] __ro_after_init = {
    3,  /* 8 */
    4,  /* 16 */
    5,  /* 24 */
    5,  /* 32 */
    6,  /* 40 */
    6,  /* 48 */
    6,  /* 56 */
    6,  /* 64 */
    1,  /* 72 */
    1,  /* 80 */
    1,  /* 88 */
    1,  /* 96 */
    7,  /* 104 */
    7,  /* 112 */
    7,  /* 120 */
    7,  /* 128 */
    2,  /* 136 */
    2,  /* 144 */
    2,  /* 152 */
    2,  /* 160 */
    2,  /* 168 */
    2,  /* 176 */
    2,  /* 184 */
    2   /* 192 */
}};

//根据分配标志返回枚举类型
static __always_inline enum kmalloc_cache_type kmalloc_type(gfp_t flags)
{
#ifdef CONFIG_ZONE_DMA
    if (likely((flags & (__GFP_DMA | __GFP_RECLAIMABLE)) == 0))
        return KMALLOC_NORMAL;
    return flags & __GFP_DMA ? KMALLOC_DMA : KMALLOC_RECLAIM;
#else
    return flags & __GFP_RECLAIMABLE ? KMALLOC_RECLAIM : KMALLOC_NORMAL;
#endif
}

// 由size计算出index，同flags共同确定数组下标
struct kmem_cache *kmalloc_slab(size_t size, gfp_t flags)
{
    unsigned int index;
    //计算出index
    if (size <= 192) {
        if (!size)
            return ZERO_SIZE_PTR;
        index = size_index[size_index_elem(size)];
    } else {
        if (WARN_ON_ONCE(size > KMALLOC_MAX_CACHE_SIZE))
            return NULL;
        index = fls(size - 1);
    }
    return kmalloc_caches[kmalloc_type(flags)][index];
}

全局数组kmalloc_caches的建立过程如下：

struct kmem_cache *__init create_kmalloc_cache(const char *name,
        unsigned int size, slab_flags_t flags,
        unsigned int useroffset, unsigned int usersize)
{
    // 从第一个kmem_cache中分配一个对象放kmem_cache
    struct kmem_cache *s = kmem_cache_zalloc(kmem_cache, GFP_NOWAIT);

    if (!s)
        panic("Out of memory when creating slab %s\n", name);
    // 设置s的对齐参数，处理s的freelist就是arr_cache
    create_boot_cache(s, name, size, flags, useroffset, usersize);
    list_add(&s->list, &slab_caches);
    s->refcount = 1;
    return s;
}

// 新建一个kmem_cache
static void __init new_kmalloc_cache(int idx, enum kmalloc_cache_type type, slab_flags_t flags)
{
    if (type == KMALLOC_RECLAIM)
        flags |= SLAB_RECLAIM_ACCOUNT;
        //根据kmalloc_info中信息建立一个kmem_cache
    kmalloc_caches[type][idx] = create_kmalloc_cache(
                    kmalloc_info[idx].name[type],
                    kmalloc_info[idx].size, flags, 0,
                    kmalloc_info[idx].size);
}

//建立所有的kmalloc_caches中的kmem_cache
void __init create_kmalloc_caches(slab_flags_t flags)
{
    int i;
    enum kmalloc_cache_type type;
    for (type = KMALLOC_NORMAL; type <= KMALLOC_RECLAIM; type++) {
        for (i = KMALLOC_SHIFT_LOW; i <= KMALLOC_SHIFT_HIGH; i++) {
            if (!kmalloc_caches[type][i])
                //建立一个新的kmem_cache
                new_kmalloc_cache(i, type, flags);
            if (KMALLOC_MIN_SIZE <= 32 && i == 6 &&
                    !kmalloc_caches[type][1])
                new_kmalloc_cache(1, type, flags);
            if (KMALLOC_MIN_SIZE <= 64 && i == 7 &&
                    !kmalloc_caches[type][2])
                new_kmalloc_cache(2, type, flags);
        }
    }
}

3、分配对象：slab_alloc

slab_alloc函数的第一个参数是kmem_cache结构的指针，表示从该kmem_cache结构中分配对象。

首先获取当前kmem_cache结构中指向array_cache结构的指针，如果找到空闲对象的地址，在array_cache结构中取出一个空闲对象地址返回，即分配成功。

未找到空闲对象时，获取先cache所属的kmem_cache_node，然后调用get_first_slab获取kmem_cache_node结构，查看是否包含空闲对象的kmem_cache；
如果kmem_cache_node结构没有包含空闲对象的kmem_cache，调用cache_grow_begin函数，找伙伴系统分配新的内存页面，并进行必要的初始化，最后调用cache_grow_end函数，把分配的page挂载到kmem_cache_node结构的slabs_list链表上。

接口调用过程如下：

slab_alloc
    __do_cache_alloc
        ____cache_alloc
            cpu_cache_get    // 获取当前cpu在cachep结构中的array_cache结构的指针
                // 找到空闲对象后，返回对象地址，分配过程结束
            
            // 未找到空闲对象时
            cache_alloc_refill  
                numa_mem_id
                cpu_cache_get
                get_node          // 获取kmem_cache_node
                    // 没有包含空闲对象的kmem_cache
                    get_first_slab
                    alloc_block      // 获取kmem_cache_node结构中其它kmem_cache, 
                
                cache_grow_begin  // 分配新的kmem_cache并初始化
                cpu_cache_get
                cache_grow_end  // 将page挂载到kmem_cache_node结构的slabs_list链表山

详细流程如下：

static __always_inline void *slab_alloc(struct kmem_cache *cachep, gfp_t flags, unsigned long caller)
{
    unsigned long save_flags;
    void *objp;
    //关中断
    local_irq_save(save_flags);
    //分配对象
    objp = __do_cache_alloc(cachep, flags);
    //恢复中断
    local_irq_restore(save_flags);
    return objp;
}


// 对象分配过程
static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)
{
    void *objp;
    struct array_cache *ac;
    //获取当前cpu在cachep结构中的array_cache结构的指针
    ac = cpu_cache_get(cachep);

    //如果ac中的avail不为0,说明当前kmem_cache结构中freelist是有空闲对象
    if (likely(ac->avail)) {
        ac->touched = 1;
        //空间对象的地址保存在ac->entry
        objp = ac->entry[--ac->avail];
        goto out;
    }

    // 未找到空闲对象
    objp = cache_alloc_refill(cachep, flags);    
out:
    return objp;
}
static __always_inline void *__do_cache_alloc(struct kmem_cache *cachep, gfp_t flags)
{
    return ____cache_alloc(cachep, flags);
}

static struct page *get_first_slab(struct kmem_cache_node *n, bool pfmemalloc)
{
    struct page *page;
    assert_spin_locked(&n->list_lock);
    //首先从kmem_cache_node结构中的slabs_partial链表上查看有没有page
    page = list_first_entry_or_null(&n->slabs_partial, struct page,slab_list);
    if (!page) {
    //如果没有
        n->free_touched = 1;
    //从kmem_cache_node结构中的slabs_free链表上查看有没有page
        page = list_first_entry_or_null(&n->slabs_free, struct page,slab_list);
        if (page)
            n->free_slabs--; //空闲slab计数减一
    }
    //返回page
    return page;
}
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;

    // 获取内存节点
    node = numa_mem_id();
    ac = cpu_cache_get(cachep);
    batchcount = ac->batchcount;
    // 获取cache所属的kmem_cache_node
    n = get_node(cachep, node);
    shared = READ_ONCE(n->shared);
    if (!n->free_objects && (!shared || !shared->avail))
        goto direct_grow;
    while (batchcount > 0) {
        // 获取kmem_cache_node结构中其它kmem_cache,返回的是page，而page会指向kmem_cache
        page = get_first_slab(n, false);
        if (!page)
            goto must_grow;
        batchcount = alloc_block(cachep, ac, page, batchcount);
    }
must_grow:
    n->free_objects -= ac->avail;
direct_grow:
    if (unlikely(!ac->avail)) {
        //分配新的kmem_cache并初始化
        page = cache_grow_begin(cachep, gfp_exact_node(flags), node);
        ac = cpu_cache_get(cachep);
        if (!ac->avail && page)
            alloc_block(cachep, ac, page, batchcount);
        //让page挂载到kmem_cache_node结构的slabs_list链表上
        cache_grow_end(cachep, page);
        if (!ac->avail)
            return NULL;
    }
    ac->touched = 1;
    //重新分配
    return ac->entry[--ac->avail];
}