Slub

Slab是基于Buddy的分配器，也就是首先向Buddy分配对应的大内存，对这块内存进行管理，从而避免内部碎片。

具体的，Slab向Buddy申请特地大小的内存，这块内存的大小要求能被结构体大小整除，即正好能放下完整的对象，不会存在内部碎片。

Slab策略看起来像池的思想，但由于对象类型很多，不可能每个都分配一个池，Slab可以看成一个通用的拟内存池机制。

一个Slab包含一个或多个连续的物理页面，然后将这些页面均分成固定的大小的各等份，每一等份就是一个对象，各对象通过链表串起来。有关slab 的信息封装在 page 中，对应的字段如下

/* file: include/linux/mm_types.h */

struct page {
    union {
        struct { /* slab, slob and slub */
            union {
                /* slab 列表，slab 可能在 partial */
                struct list_head slab_list;
                struct { /* Partial pages */
                    struct page *next;
#ifdef CONFIG_64BIT
                    int pages; /* Nr of pages left */
                    int pobjects; /* Approximate count */
#else
                    short int pages;
                    short int pobjects;
#endif
                };
            };
            /* 使用该页作为 slab 的 kmem_cache, 通过文件 slub.c 中的函数 allocate_slab() 设置 */
            struct kmem_cache *slab_cache; /* not slob */
            /* 当页面用于 slab 缓存时，slab 的首页对应的 page 的该字段会指向整个 slab 的空闲对象列表。
             * 但当 slab 当前正在被 kmem_cache_cpu 使用时，page 的该字段会设置为 NULL, 而 kmem_cache_cpu 中的 freelist 字段会指向 slab 的空闲对象列表 */
            void *freelist; /* first free object */
            union {
                void *s_mem; /* slab: first object */
                /* 因为 counters 与下面包含 inuse, objects, frozen 字段的结构体是 union 关系，所以很多时候需要新建 page 然后对后面三个字段赋值时，直接将 counters 的值付过去就 OK 了 */
                unsigned long counters; /* SLUB */
                struct { /* SLUB */
                    /* 记录被使用的对象，但是初始值与 objects 相同 */
                    unsigned inuse : 16;
                    /* 记录 slab 中包含 object 的总数，即为 kmem_cache 中 kmem_cache_order_objects 中低 15 位表示的值。该值在 slub.c 中的函数 allocate_slab 中设置 */
                    unsigned objects : 15;
                    /* 标记该 slab 是否被某个 cpu “锁定”，如果处于 frozen 状态，那么只有对应的CPU 能够从该slab中分配对象，其他CPU 只能往该页面释放对象。初始值设置为 1 */
                    unsigned frozen : 1;
                };
            };
        };
} _struct_page_alignment;

如果页面被分配用于 slab, 那么这些字段就会被设置。其中 kmem_cache 与注释中提到的 kmem_cache_cpu 等是重点关注的结构。

Slub接口及使用

struct kmem_cache *kmem_cache_create(const char *name, //kmem_cache的名称
        size_t size, //slab管理对象的大小
        size_t align, //slab分配器分配内存的对齐字节数(以align字节对齐)
        unsigned long flags, //分配内存掩码，实际会调用到buddy处执行。
        void (*ctor)(void *)); //分配对象的构造回调函数
void kmem_cache_destroy(struct kmem_cache *); //销毁该cache
void *kmem_cache_alloc(struct kmem_cache *cachep, int flags); //从该cache分配一块对象
void kmem_cache_free(struct kmem_cache *cachep, void *objp); //从该cache回收指定对象

使用步骤如下

1. mem_cache_create创建一个kmem_cache数据结构。
2. 使用kmem_cache_alloc接口分配内存给buf
3. 使用buf
4. kmem_cache_free接口释放buf。
5. release第一步创建的kmem_cache数据结构。

代码如下

/*
 *　This is a demo for how to use kmem_cache_create
 */
void slab_demo(void)
{
    /*1. create kmem_cache. */
    struct kmem_cache *kmem_cache_16 = kmem_cache_create("kmem_cache_16", 16,
            8, ARCH_KMALLOC_FLAGS,
            NULL);
 
    /*2. now you can alloc memory, the buf points to 16 bytes of memory*/
    char *buf = kmeme_cache_alloc(kmem_cache_16, GFP_KERNEL);
 	/*3. use buf...*/
    
    /*4. and 5. don't forget to release the memory after use */
    kmem_cache_free(kmem_cache_16, buf);
    kmem_cache_destroy(kmem_cache_16);
}

创建slab

内核创建一个slab的逻辑也很直观：首先向Buddy System申请一定数量的连续页面，然后初始化对象并构建好对象列表。代码如下

/* file: mm/slub.c */

static struct page *allocate_slab(struct kmem_cache *s, gfp_t flags, int node) {
    struct page *page;
    /* 结构 kmem_cache_order_objects 中记录着一个 slab 应该申请的页面数量与总的对象数量，两个量封装在一个字段 unsigned int x 中，其中低16位表示对象总数，高位表示连续页面的阶，即需要分配2^(oo.x >> 16)个连续页面 */
    struct kmem_cache_order_objects oo = s->oo;
    /* 传给Buddy System的各类Flag, 这里我们删掉了对该参数的初始化逻辑 */
    gfp_t alloc_gfp;
    /* 初始化对象列表时使用的指针变量 */
    void *start, *p, *next;
    int idx;
    bool shuffle;

    /* 分配连续 2^(oo.x>>OO_SHIFT) 个连续页面，其中 OO_SHIFT 为 16  */
    page = alloc_slab_page(s, alloc_gfp, node, oo);
    if (unlikely(!page)) {
        /* 如果 buddy system 没有足够的连续物理页，则减少 oo 的数值再尝试一次 */
        oo = s->min;
        alloc_gfp = flags;
        page = alloc_slab_page(s, alloc_gfp, node, oo);
        /* s->min 是实例化一个 slab 所需要的最小的内存页数量，如果依旧无法满足的话就直接退出了 */
        if (unlikely(!page))
            goto out;
        stat(s, ORDER_FALLBACK);
    }

    /* oo.x 的低 15 位表示该 slab 中可以存放的 object 总数 */
    /* 函数oo_objects 就是取出 oo.x 的低16位的数字，即 oo.x&(1<<16 -1) 的值*/
    page->objects = oo_objects(oo);

    /* 将 kmem_cache 记录到第一个内存页中，kmem_cache 在下一节介绍 */
    page->slab_cache = s;
    /* 设置 page 的标记位，标记该页面用于 slab */
    __SetPageSlab(page);

    start = page_address(page);

    shuffle = shuffle_freelist(s, page);

    /* if block 中构建对象列表 */
    if (!shuffle) {
        /* 初始化第一个对象，因为 for 循环中处理的都是下一个对象 */
        start = fixup_red_left(s, start);
        /* 如果为 slab 配置了对象的初始化函数，则会在函数 setup_object 调用，对每个对象进行初始化  */
        start = setup_object(s, page, start);
        /* slab 中空闲对象列表的地址为第一个对象 */
        page->freelist = start;
        /* 初始化 slab 中的空闲对象列表 */
        for (idx = 0, p = start; idx < page->objects - 1; idx++) {
            /* s->size 表示每个对象的大小，这里计算出下一个对象的地址 */
            next = p + s->size;
            /* 初始化下一个对象 */
            next = setup_object(s, page, next);
            /* 建立空闲对象列表的单链表，其中 p 为当前对象，next 为下一个对象，将 next 的地址写入 p+s.offset 位置处 */
            set_freepointer(s, p, next);
            p = next;
        }
        /* 链表最后一个元素的next属性指向 NULL */
        set_freepointer(s, p, NULL);
    }

    page->inuse = page->objects;
    page->frozen = 1;

out:
    if (!page)
        return NULL;

    return page;
}

Slab管理空闲对象

前文中我们提到过slab中的对象就是一个固定大小的连续内存块，通过对象列表的构建逻辑我们可以对此有更深刻的理解，内核并没有单独定义一个结构体来封装对象信息，在构建对象列表时，指向下一个空闲对象的指针也是直接存放在该对象的内存地址内部，因为对象还没有被分配出去时内存是不会被使用的，而被分配之后也不需要该指针了，这是一个比较精巧的设计。

页面的freelist 总是指向slab 中第一个空闲对象，也是 slab 分配与释放对象的入口点。

首先一个slab缓存池包含的页数是由oo决定的。oo拆分为两部分，低16位代表一个slab缓存池中object的数量，高16位代表包含的页数。使用kmem_cache_create()接口创建kmem_cache的时候需要指出obj的size和对齐align。也就是传入的参数。kmem_cache_create()主要是就是填充kmem_cache结构体成员。既然从伙伴系统得到(2^(oo >> 16)) pages大小内存，按照size大小进行平分。一般来说都不会整除，因此剩下的就是图中灰色所示。由于每一个object的大小至少8字节，当然可以用来存储下一个object的首地址。就像图中所示的，形成单链表。图中所示下个obj地址存放的位置位于每个obj首地址处，在内核中称作指针内置式。同时，下个obj地址存放的位置和obj首地址之间的偏移存储在kmem_cache的offset成员。两外一种方式是指针外置式，即下个obj的首地址存储的位置位于obj尾部，也就是在obj尾部再分配sizeof(void *)字节大小的内存。对于外置式则offset就等于kmem_cache的inuse成员。

整体组织

我们把每次向Buddy申请的那块内存，称为slab。每个slab的第一个页面会存储本slab的管理信息。页面内的对象以链表组织。页面与页面之间以单链表组织。

不同slab大小由不同的kmem_cache管理。每种kmem_cache的名称、大小等属性有所不同，但管理方式一致。

CPU一般是多核心的，为了减少锁的开小，为每一个CPU核心都创建一个缓存。整体组织如下

所有的、不同大小的 kmem_cache 保留在全局变量 kmalloc_caches 中。由slub的接口可知，具体请求哪一个kmem_cache内的对象，是由内核开发者函数传参决定的。

per cpu freelist

针对每一个cpu都会分配一个struct kmem_cache_cpu的结构体。可以称作是本地缓存池。当内存申请的时候，优先从本地cpu缓存池申请。在分配初期，本地缓存池为空，自然要从伙伴系统分配一定页数的内存。内核会为每一个物理页帧创建一个struct page的结构体。kmem_cacche_cpu中page就会指向正在使用的slab的页帧。freelist成员指向第一个可用内存obj首地址。处于正在使用的slab的struct page结构体中的freelist会置成NULL，因为没有其他地方使用。struct page结构体中inuse代表已经使用的obj数量。full slab就像无人看管的孩子，没有任何链表来管理。释放完全由内核开发者手动。

per cpu partial

当full slab释放obj的时候，首先就会将slab挂入per cpu partial链表管理。通过struct page中next成员形成单链表。per cpu partial链表指向的第一个page中会存放一些特殊的数据。例如：pobjects存储着per cpu partial链表中所有slab可供分配obj的总数，如图所示。当然还有一个图中没有体现的pages成员存储per cpu partial链表中所有slab缓存池的个数。pobjects到底有什么用呢？我们从full slab中释放一个obj就添加到per cpu partial链表，总不能无限制的添加吧！因此，每次添加的时候都会判断当前的pobjects是否大于kmem_cache的cpu_partial成员，如果大于，那么就会将此时per cpu partial链表中所有的slab移送到kmem_cache_node的partial链表，然后再将刚刚释放obj的slab插入到per cpu partial链表。如果不大于，则更新pobjects和pages成员，并将slab插入到per cpu partial链表。

per node partial

per node partia链表类似per cpu partial，区别是node中的slab是所有cpu共享的，而per cpu是每个cpu独占的。假如现在的slab布局如上图所示。假如现在如红色箭头指向的obj将会释放，那么就是一个empty slab，此时判断kmem_cache_node的nr_partial是否大于kmem_cache的min_partial，如果大于则会释放该slab的内存。

Slub内存分配流程

由创建cache的流程，不难发现cache会记录对象大小和构造函数。

struct kmem_cache *kmem_cache_create(const char *name, //kmem_cache的名称
        size_t size, //slab管理对象的大小
        size_t align, //slab分配器分配内存的对齐字节数(以align字节对齐)
        unsigned long flags, //分配内存掩码，实际会调用到buddy处执行。
        void (*ctor)(void *)); //分配对象的构造回调函数

创建时，仅仅需要传递kmem_cache和标志信息flags。

void *kmem_cache_alloc(struct kmem_cache *cachep, int flags); //从该cache分配一块对象

深入原理，分配顺序是

• cpu的freelist
• cpu的partial
• 各核心共享的node

首先从cpu 本地缓存池分配，如果freelist不存在，就会转向per cpu partial分配，如果per cpu partial也没有可用对象，继续查看per node partial，如果很不幸也不没有可用对象的话，就只能从伙伴系统分配一个slab了，并挂入per cpu freelist。

流程图如下

我们详细看一下这几种情况。

1. kmem_cache刚刚建立，还没有任何对象可供分配，此时只能从伙伴系统分配一个slab，如下图所示。

   

2. 如果正在使用的slab有free obj，那么就直接分配即可，这种是最简单快捷的。如下图所示。

3. 随着正在使用的slab中obj的一个个分配出去，最终会无obj可分配，此时per cpu partial链表中有可用slab用于分配，那么就会从per cpu partial链表中取下一个slab用于分配obj。如下图所示。

   

4. 随着正在使用的slab中obj的一个个分配出去，最终会无obj可分配，此时per cpu partial链表也为空，此时发现per node partial链表中有可用slab用于分配，那么就会从per node partial链表中取下一个slab用于分配obj。如下图所示。

5. 走到这一步，说明node_partial也没有可用对象，就只能从伙伴系统分配一个slab了。

Slub内存释放流程

通过void kmem_cache_free()回收指定对象，具体签名如下

void kmem_cache_free(struct kmem_cache *cachep, void *objp); //从该cache回收指定对象

释放流程图如下

如果释放的obj就是属于正在使用cpu上的slab，那么直接释放即可，非常简单；如果不是的话，首先判断所属slub是不是full状态，因为full slab是没妈的孩子，释放之后就变成partial empty，急需要找个链表领养啊！这个妈就是per cpu partial链表。如果per cpu partial链表管理的所有slab的free object数量超过kmem_cache的cpu_partial成员的话，就需要将per cpu partial链表管理的所有slab移动到per node partial链表管理；如果不是full slab的话，继续判断释放当前obj后的slab是否是empty slab，如果是empty slab，那么在满足kmem_cache_node的nr_partial大于kmem_cache的min_partial的情况下，则会释放该slab的内存。其他情况就直接释放即可。

即，min_cpu_partial保证CPU有一定数量的缓存对象，而min_partial保证node有一定数量的缓存对象。

具体情况分析如下

1. 释放该对象后，整个slab都空闲，则回收整个slab；释放完该对象，所属slab不全空闲，则移动该对象到空闲链表，如下图。

   假设下图左边的情况下释放obj，如果满足kmem_cache_node的nr_partial大于kmem_cache的min_partial的话，释放情况如下图所示。

   

2. 假设下图左边的情况下释放obj，如果不满足kmem_cache_node的nr_partial大于kmem_cache的min_partial的话，释放情况如下图所示。即min_partial保证该kmem_cache有最低数量的slab。

   

3. 假设下图从full slab释放obj的话，如果满足per cpu partial管理的所有slab的free object数量大于kmem_cache的cpu_partial成员的话的话，将per cpu partial链表管理的所有slab移动到per node partial链表管理，释放情况如下图所示。

   

4. 假设下图从full slab释放obj的话，如果不满足per cpu partial管理的所有slab的free object数量大于kmem_cache的cpu_partial成员的话的话，释放情况如下图所示。

   

kmalloc和vmalloc

看起来Slab只能分配固定大小的的内存，实际上，Linux的Slab实现了kmalloc和vmalloc，可以提供不同大小的可分配内存。

kmalloc、vmalloc对于常用的大小，创建了对应大小的的高速缓存组，部分如下。分配时找到第一个大于等于请求值的那个缓存组分配即可。

kmalloc和vmalloc接口

void * kmalloc(size_t size, gfp_t flags); 
void * vmalloc(unsigned long size);
void kfree(const void* ptr);
void vfree(const void* addr);

kmallo和vmalloc具体实现原理就在是创建多个不同大小的kmem_cache，可以通过cat /proc/slabinfo查看所有的kmem_cache，其中含kmalloc就是用于分配不固定大小的内存。

root:/ # cat /proc/slabinfo | grep "kmalloc"
kmalloc-8k           407    416   8192    4    8 : tunables    0    0    0 : slabdata    104    104      0
kmalloc-4k          3189   3256   4096    8    8 : tunables    0    0    0 : slabdata    407    407      0
kmalloc-2k          2647   2800   2048   16    8 : tunables    0    0    0 : slabdata    175    175      0
kmalloc-1k          4177   4256   1024   32    8 : tunables    0    0    0 : slabdata    133    133      0
kmalloc-512        22044  55360    512   32    4 : tunables    0    0    0 : slabdata   1730   1730      0
kmalloc-256        20964  23168    256   32    2 : tunables    0    0    0 : slabdata    724    724      0
kmalloc-192        20440  22638    192   21    1 : tunables    0    0    0 : slabdata   1078   1078      0
kmalloc-128         3427   4192    128   32    1 : tunables    0    0    0 : slabdata    131    131      0
kmalloc-96          5628   5628     96   42    1 : tunables    0    0    0 : slabdata    134    134      0
kmalloc-64         26512  27584     64   64    1 : tunables    0    0    0 : slabdata    431    431      0
kmalloc-32         60345  61568     32  128    1 : tunables    0    0    0 : slabdata    481    481      0
kmalloc-16         24109  27136     16  256    1 : tunables    0    0    0 : slabdata    106    106      0
kmalloc-8          12800  12800      8  512    1 : tunables    0    0    0 : slabdata     25     25      0

假如通过kmalloc(17, GFP_KERNEL)申请内存，系统会从名称“kmalloc-32”管理的slab缓存池中分配一个对象。即使浪费了15Byte。

通过slab接口分配的最大内存是8192 bytes。那么通过kmalloc接口申请的内存大于8192 bytes该怎么办呢？

其实kmalloc会判断申请的内存是否大于8192 bytes，如果大于的话就会通过伙伴系统的alloc_pages接口申请内存。

kmalloc和vmalloc区别

kmalloc分配的内存是物理连续的，而vmalloc是不一定是物理连续的。当然它们都是逻辑连续的。

vmalloc通过分配非连续的物理内存块，再修正页表，实现逻辑连续。由于需要建立页表项，同时一个一个地进行映射，导致分配慢、TLB抖动，都会影响效率。因此，内核在不得已才使用，如分配大块内存的情况下，比如加载模块。

参考

• 图解slub
• slub分配器
• 3.2.5 SLAB/SLUB/SLOB