内核管理页面使用了2个算法：伙伴算法和slub算法，伙伴算法以页为单位管理内存，但在大多数情况下，程序需要的并不是一整页，而是几个、几十个字节的小内存。于是需要另外一套系统来完成对小内存的管理，这就是slub系统。slub系统运行在伙伴系统之上，为内核提供小内存管理的功能。

​ slub把内存分组管理，每个组分别包含 8、64、512、…2048个字节，在4K页大小的默认情况下，另外还有两个特殊的组，分别是96B和192B，共11组。之所以这样分配是因为如果申请2^12B大小的内存，就可以使用伙伴系统提供的接口直接申请一个完整的页面即可。

​ slub就相当于零售商，它向伙伴系统“批发”内存，然后在零售出去。一下是整个slub系统的框图：

一切的一切源于kmalloc_caches[12]这个数组，该数组的定义如下：

struct kmem_cache *kmalloc_caches[KMALLOC_SHIFT_HIGH + 1];
每个数组元素对应一种大小的内存，可以把一个kmem_cache结构体看做是一个特定大小内存的零售商，整个slub系统中共有12个这样的零售商，每个“零售商”只“零售”特定大小的内存，例如：有的“零售商”只"零售"8Byte大小的内存，有的只”零售“16Byte大小的内存。

​ 每个零售商(kmem_cache)有两个“部门”，一个是“仓库”：kmem_cache_node，一个“营业厅”：kmem_cache_cpu。“营业厅”里只保留一个slab，只有在营业厅(kmem_cache_cpu)中没有空闲内存的情况下才会从仓库中换出其他的slab。
​ 所谓slab就是零售商(kmem_cache)批发的连续的整页内存，零售商把这些整页的内存分成许多小内存，然后分别“零售”出去，一个slab可能包含多个连续的内存页。slab的大小和零售商有关。

1. slub的分配原理
​ slub管理器从伙伴系统哪里每次批发2^order个页面，之后这些物理页面被按照对象大小(objsize)组织成单向链表。由于单项链表的指针要分配额外的存储空间，所以一个对象的实际大小要大约分配给程序使用的大小。kmem_cache中的size就表示实际大小，而objsize表示分配出去可以使用的大小。在多CPU的系统中，为了防止过多使用自旋锁带来的性能开销，每一个CPU有一个kmem_cache_cpu结构，仓库中货物主要是通过kmem_cache_cpu结构管理。oid*指向的是下一个空闲的object的首地址，这样object就连成了一个单链表。

slub系统刚刚创建处理，第一次申请slub内存

此时slub系统刚刚建立起来，营业厅(kmem_cache_cpu)和仓库(kmem_cache_node)中没有任何可用的slub可以使用，此时只能向伙伴同中申请可用的内存项，并把这些页面分成很多的object，取出其中一个object标志为已被占用，并返回给用户，其余的object标志为空闲并放在kmem_cache_cpu中保存。

slub的kmem_cache_cpu中保存的slab上有空闲的object可以使用

直接把kmem_cache_cpu中保存的一个空闲object返回给用户，并把freelist指向下一个空闲的object

kmem_cache_cpu中已经没有空闲的object了，但kmem_cache_node的partial中有空闲的object

从kmem_cache_node的partial变量中获取有空闲object的slab，并把一个空闲的object返回给用户

在kmem_cache_cpu和kmem_cache_node中都没有空闲页面了

slub已经连续申请了很多页，现在kmem_cache_cpu中保存的物理页面上已经没有空闲的object可以使用了，而此时kmem_cache_node中也没有空闲页面了，只能向内存管理器(伙伴系统)申请slub，并把该slub初始化，返回第一个obect

向slub系统释放内存块(object)时，如果kmem_cache_cpu中缓存的slab就是该object所在的slab，则把该object放在空闲链表中即可，如果kmem_cache_cpu中缓存的slab不是该object所在的slab，然后把该object释放到该object所在的slab中。在释放object的时候可以分为一下三种情况：

object在释放之前slab是full状态的时候（slab中的object都是被占用的），释放该object后，这是该slab就是半满（partail）的状态了，这时需要把该slab添加到kmem_cache_node中的partial链表中。
slab是partial状态时（slab中既有object被占用，又有空闲的），直接把该object加入到该slab的空闲队列中即可。
该object在释放后，slab中的object全部是空闲的，还需要把该slab释放掉。
在分配缓存块的时候，要分两种路径，fast path和slow path，也就是快速通道和普通通道。其中 kmem_cache_cpu 就是快速通道，kmem_cache_node 是普通通道。每次分配的时候，要先从 kmem_cache_cpu 进行分配。如果 kmem_cache_cpu 里面没有空闲的块，那就到 kmem_cache_node 中进行分配；如果还是没有空闲的块，才去伙伴系统分配新的页。

2. slub分配和释放API

对于内核的申请内存，有两种方式，一种是通过伙伴系统申请page allocator，一种是通过slab allocatorr，对于内核有驱动模块，文件系统等方式会申请内存。其主要的方式有两种

提供特定类型的内核缓存方式

内核为专用高速缓存的申请和释放提供了一套完整的接口，根据所传入的参数为具体的对象分配 slab 缓存kmem_cache_create() 用于对一个指定的对象创建高速缓存。它从 cache_cache 普通高速缓存中为新的专有缓存分配一个高速缓存描述符，并把这个描述符插入到高速缓存描述符形成的 cache_chain 链表中kmem_cache_alloc() 在其参数所指定的高速缓存中分配一个 slab。相反， kmem_cache_free() 在其参数所指定的高速缓存中释放一个 slab

struct kmem_cache *kmem_cache_create(const char *, size_t, size_t,---------创建slab描述符kmem_cache，此时并没有真正分配内存
            unsigned long, void (*)(void *));
void *kmem_cache_alloc(struct kmem_cache *, gfp_t flags);------------------分配slab缓存对象
void kmem_cache_free(struct kmem_cache *, void *);-------------------------释放slab缓存对象
void kmem_cache_destroy(struct kmem_cache *);-----------------------------销毁slab描述符

供一般的内存分配方式，适合于所有的device drivers

kmalloc(size,flags)分配长度为size字节的一个内存区，并返回指向该内存区起始处的一个void指针，如果没有足够内存，则结果为NULL指针
kfree(*ptr)释放 *ptr指向的内存区

3. kmalloc分配函数
内核常用的kmalloc函数的核心是slab机制，按照内存块的2^order来创建多个slab描述符，例如16B/32B…等大小，系统启动的时候在create_kmalloc_caches函数中完成。我们主要来看看kmalloc的实现

static __always_inline void *kmalloc(size_t size, gfp_t flags)
{if (__builtin_constant_p(size)) {                                                              if (size > KMALLOC_MAX_CACHE_SIZE)return kmalloc_large(size, flags);
#ifndef CONFIG_SLOBif (!(flags & GFP_DMA)) {int index = kmalloc_index(size);if (!index)return ZERO_SIZE_PTR;return kmem_cache_alloc_trace(kmalloc_caches[index],flags, size);}
#endif}return __kmalloc(size, flags);
}

当超过KMALLOC_MAX_CACHE_SIZE（如果为slub，则为2页），则使用伙伴系统从kmalloc_large页面分配器分配页面，_builtin_constant_p(exp)是gcc的内建函数，用于判断一个值是否为编译时常数，如果参数exp的值是常数，函数返回 1，否则返回 0。就是说，如果size不是常数，就调用__kmalloc(size, flags);去处理
kmalloc_index（）函数按大小计算索引值，然后调用kmem_cache_alloc_trace分配
static __always_inline int kmalloc_index(size_t size)
{
    if (!size)
        return 0;

    if (size <= KMALLOC_MIN_SIZE)
        return KMALLOC_SHIFT_LOW;

    if (KMALLOC_MIN_SIZE <= 32 && size > 64 && size <= 96)
        return 1;
    if (KMALLOC_MIN_SIZE <= 64 && size > 128 && size <= 192)
        return 2;
    if (size <=          8) return 3;
    if (size <=         16) return 4;
    if (size <=         32) return 5;
    if (size <=         64) return 6;
    if (size <=        128) return 7;
    if (size <=        256) return 8;
    if (size <=        512) return 9;
    if (size <=       1024) return 10;
    if (size <=   2 * 1024) return 11;
    if (size <=   4 * 1024) return 12;
    if (size <=   8 * 1024) return 13;
    if (size <=  16 * 1024) return 14;
    if (size <=  32 * 1024) return 15;
    if (size <=  64 * 1024) return 16;
    if (size <= 128 * 1024) return 17;
    if (size <= 256 * 1024) return 18;
    if (size <= 512 * 1024) return 19;
    if (size <= 1024 * 1024) return 20;
    if (size <=  2 * 1024 * 1024) return 21;
    if (size <=  4 * 1024 * 1024) return 22;
    if (size <=  8 * 1024 * 1024) return 23;
    if (size <=  16 * 1024 * 1024) return 24;
    if (size <=  32 * 1024 * 1024) return 25;
    if (size <=  64 * 1024 * 1024) return 26;
    BUG();

    /* Will never be reached. Needed because the compiler may complain */
    return -1;
}
1
根据0到64M或更小的请求大小返回索引，为0到23之间的数字。如果超过64M，则返回-1作为错误。

根据请求大小的索引值

0 =无分配（零分配）
1 = 65 … 96字节
2 = 120 … 192字节
n = 2 ^（n-1）… 2 ^ n -1
3 = 1 … 8
4 = 9 … 16
5 = 17 … 32
6 = 33 … 64
…
26 = 32M-1 … 64M
但是，如果大小为1〜KMALLOC_MIN_SIZE，则返回KMALLOC_SHIFT_LOW。
rpi2示例）KMALLOC_MIN_SIZE = 64，KMALLOC_SHIFT_LOW = 6
arm64 ex）KMALLOC_MIN_SIZE = 128，KMALLOC_SHIFT_LOW = 7
下面我们来看看__kmalloc，其处理流程如下：

void *__kmalloc(size_t size, gfp_t flags)
{struct kmem_cache *s;void *ret;if (unlikely(size > KMALLOC_MAX_CACHE_SIZE))return kmalloc_large(size, flags);s = kmalloc_slab(size, flags);if (unlikely(ZERO_OR_NULL_PTR(s)))return s;ret = slab_alloc(s, flags, _RET_IP_);trace_kmalloc(_RET_IP_, ret, size, s->size, flags);kasan_kmalloc(s, ret, size, flags);return ret;
}

如果超过KMALLOC_MAX_CACHE_SIZE（如果为slub，则为2页），则使用伙伴系统通过kmalloc_large()函数从页面分配器分配页面。
检索适当的kmalloc slab缓存
获得kmalloc缓存中分配的。
struct kmem_cache *kmalloc_slab(size_t size, gfp_t flags)
{
    int index;

    if (unlikely(size > KMALLOC_MAX_SIZE)) {                                                --------------------------(1)
        WARN_ON_ONCE(!(flags & __GFP_NOWARN));
        return NULL;
    }

    if (size <= 192) {                                                                     ---------------------------(2)
        if (!size)
            return ZERO_SIZE_PTR;

        index = size_index[size_index_elem(size)];
    } else
        index = fls(size - 1);

#ifdef CONFIG_ZONE_DMA                                                                      -------------------------(3)
    if (unlikely((flags & GFP_DMA)))
        return kmalloc_dma_caches[index];

#endif
    return kmalloc_caches[index];
}

20

24
size为1至192，则使用已创建的size_index []表来计算索引，193至KMALLOC_MAX_SIZE（对于slub，则为2页），则将计算并返回所需的位数。

193〜256→8
257〜512→9
513〜1024 → 10
1025〜2048 → 11
2049〜4096 → 12
4097〜8192 → 13
1

最后如果开启了DMA内存配置且设置了GFP_DMA标志，将结合索引值通过kmalloc_dma_caches返回kmem_cache管理结构信息，否则将通过kmalloc_caches返回该结构。

由此可以看出kmalloc()实现较为简单，起分配所得的内存不仅是虚拟地址上的连续存储空间，同时也是物理地址上的连续存储空间。

slab(或slub/slob)对内存进行了二次管理，使系统可以申请小块内存。Slab先从buddy拿到数个页的内存，然后切成固定的小块（称为object），再分配出去。从/proc/slabinfo中可以看到系统内有很多slab，每个slab管理着数个页的内存，它们可分为两种：一个是各模块专用的，一种是通用的。

一类是内核里常用的数据结构，如TCPv6,UDPv6等，由于内核经常要申请和释放这类数据结构，所以就针对这些数据结构做一个slab，然后再次申请这类结构体时就总是从这个slab里来申请一个object（使用kmem_cache_alloc（）申请）。
另一类是一些小粒度的内存申请，如slabinfo中的kmalloc-16，kmalloc-32等（使用kmalloc()申请）。

1.前言

在Linux中，伙伴系统（buddy system）是以页为单位管理和分配内存。但是现实的需求却以字节为单位，假如我们需要申请20Bytes，总不能分配一页吧！那岂不是严重浪费内存。那么该如何分配呢？slab分配器就应运而生了，专为小内存分配而生。slab分配器分配内存以Byte为单位。但是slab分配器并没有脱离伙伴系统，而是基于伙伴系统分配的大内存进一步细分成小内存分配。

前段时间学习了下slab分配器工作原理。因为自己本身是做手机的，发现现在好像都在使用slub分配器，想想还是再研究一下slub的工作原理。之前看了代码，感觉挺多数据结构和成员的。成员的意思是什么？数据结构之间的关系是什么？不知道你是否感觉云里雾里。既然代码阅读起来晦涩难懂，如果有精美的配图，不知是否有助于阁下理解slub的来龙去脉呢？我想表达的意思就是文章图多，图多，图多。我们只说原理，尽量不看代码。因为所有代码中包含的内容我都会用图来说明。你感兴趣绝对有助于你看代码。

说明：slub是slab中的一种，slab也是slab中的一种。有时候用slab来统称slab, slub和slob。slab, slub和slob仅仅是分配内存策略不同。本篇文章中说的是slub分配器工作的原理。但是针对分配器管理的内存，下文统称为slab缓存池。所以文章中slub和slab会混用，表示同一个意思。

注：文章代码分析基于linux-4.15.0-rc3。 图片有点走形，请单独点开图片查看。

2. slub数据结构

slub的数据结构相对于slab来说要简单很多。并且对外接口和slab兼容。所以说，从slab的系统更换到slub，可以说是易如反掌。

2.1. kmem_cache

现在假如从伙伴系统分配一页内存供slub分配器管理。对于slub分配器来说，就是将这段连续内存平均分成若干大小相等的object（对象）进行管理。可是我们总得知道每一个object的size吧！管理的内存页数也是需要知道的吧！不然怎么知道如何分配呢！因此需要一个数据结构管理。那就是struct kmem_cache。kmem_cache数据结构描述如下：

1. struct kmem_cache {
2. struct kmem_cache_cpu __percpu *cpu_slab;
3. /* Used for retriving partial slabs etc */
4. slab_flags_t flags;
5. unsigned long min_partial;
6. int size; /* The size of an object including meta data */
7. int object_size; /* The size of an object without meta data */
8. int offset; /* Free pointer offset. */
9. #ifdef CONFIG_SLUB_CPU_PARTIAL
10. int cpu_partial; /* Number of per cpu partial objects to keep around */
11. #endif
12. struct kmem_cache_order_objects oo;
13. /* Allocation and freeing of slabs */
14. struct kmem_cache_order_objects max;
15. struct kmem_cache_order_objects min;
16. gfp_t allocflags; /* gfp flags to use on each alloc */
17. int refcount; /* Refcount for slab cache destroy */
18. void (*ctor)(void *);
19. int inuse; /* Offset to metadata */
20. int align; /* Alignment */
21. int reserved; /* Reserved bytes at the end of slabs */
22. const char *name; /* Name (only for display!) */
23. struct list_head list; /* List of slab caches */
24. struct kmem_cache_node *node[MAX_NUMNODES];
25. };

1)     cpu_slab：一个per cpu变量，对于每个cpu来说，相当于一个本地内存缓存池。当分配内存的时候优先从本地cpu分配内存以保证cache的命中率。

2)     flags：object分配掩码，例如经常使用的SLAB_HWCACHE_ALIGN标志位，代表创建的kmem_cache管理的object按照硬件cache 对齐，一切都是为了速度。

3)     min_partial：限制struct kmem_cache_node中的partial链表slab的数量。虽说是mini_partial，但是代码的本意告诉我这个变量是kmem_cache_node中partial链表最大slab数量，如果大于这个mini_partial的值，那么多余的slab就会被释放。

4)     size：分配的object size

5)     object_size：实际的object size，就是创建kmem_cache时候传递进来的参数。和size的关系就是，size是各种地址对齐之后的大小。因此，size要大于等于object_size。

6)     offset：slub分配在管理object的时候采用的方法是：既然每个object在没有分配之前不在乎每个object中存储的内容，那么完全可以在每个object中存储下一个object内存首地址，就形成了一个单链表。很巧妙的设计。那么这个地址数据存储在object什么位置呢？offset就是存储下个object地址数据相对于这个object首地址的偏移。

7)     cpu_partial：per cpu partial中所有slab的free object的数量的最大值，超过这个值就会将所有的slab转移到kmem_cache_node的partial链表。

8)     oo：低16位代表一个slab中所有object的数量（oo & ((1 << 16) - 1)），高16位代表一个slab管理的page数量（(2^(oo  16)) pages）。

9)     max：看了代码好像就是等于oo。

10)  min：当按照oo大小分配内存的时候出现内存不足就会考虑min大小方式分配。min只需要可以容纳一个object即可。

11)  allocflags：从伙伴系统分配内存掩码。

12)  inuse：object_size按照word对齐之后的大小。

13)  align：字节对齐大小。

14)  name：sysfs文件系统显示使用。

15)  list：系统有一个slab_caches链表，所有的slab都会挂入此链表。

16)  node：slab节点。在NUMA系统中，每个node都有一个struct kmem_cache_node数据结构。

2.2. kmem_cache_cpu

struct kmem_cache_cpu是对本地内存缓存池的描述，每一个cpu对应一个结构体。其数据结构如下： 

1. struct kmem_cache_cpu {
2. void **freelist; /* Pointer to next available object */
3. unsigned long tid; /* Globally unique transaction id */
4. struct page *page; /* The slab from which we are allocating */
5. #ifdef CONFIG_SLUB_CPU_PARTIAL
6. struct page *partial; /* Partially allocated frozen slabs */
7. #endif
8. };

1)     freelist：指向下一个可用的object。

2)     tid：一个神奇的数字，主要用来同步作用的。

3)     page：slab内存的page指针。

4)     partial：本地slab partial链表。主要是一些部分使用object的slab。

2.3. kmem_cache_node

slab节点使用struct kmem_cache_node结构体描述。对于slub分配器来说，成员很少，远比slab分配器简洁。

struct kmem_cache_node {spinlock_t list_lock;unsigned long nr_partial;struct list_head partial;
};

1)     list_lock：自旋锁，保护数据。

2)     nr_partial：slab节点中slab的数量。

3)     partial：slab节点的slab partial链表，和struct kmem_cache_cpu的partial链表功能类似。

2.4. slub接口

了解了基本的数据结构，再来看看slub提供的API。如果你了解slub，我想这几个接口你是再熟悉不过了。 

struct kmem_cache *kmem_cache_create(const char *name,
size_t size,
size_t align,
unsigned long flags,
void (*ctor)(void *));
void kmem_cache_destroy(struct kmem_cache *);
void *kmem_cache_alloc(struct kmem_cache *cachep, int flags);
void kmem_cache_free(struct kmem_cache *cachep, void *objp);

1) kmem_cache_create是创建kmem_cache数据结构，参数描述如下：

    name：kmem_cache的名称

    size ：slab管理对象的大小

    align：slab分配器分配内存的对齐字节数(以align字节对齐)

    flags：分配内存掩码

    ctor ：分配对象的构造回调函数

2) kmem_cache_destroy作用和kmem_cache_create相反，就是销毁创建的kmem_cache。

3) kmem_cache_alloc是从cachep参数指定的kmem_cache管理的内存缓存池中分配一个对象，其中flags是分配掩码，GFP_KERNEL是不是很熟悉的掩码？

4) kmem_cache_free是kmem_cache_alloc的反操作

slab分配器提供的接口该如何使用呢？其实很简单，总结分成以下几个步骤：

1) kmem_cache_create创建一个kmem_cache数据结构。

2) 使用kmem_cache_alloc接口分配内存，kmem_cache_free接口释放内存。

3) release第一步创建的kmem_cache数据结构。

再来一段demo示例代码就更好了。 

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

1) 首先使用kmem_cache_create创建名称为kmem_cache_16的kmem_cache，该kmem_cache主要是描述如何管理一堆对象，其实就是slab的布局。每个对象都是16字节，并且分配的对象地址按照8字节对齐，也就是说从kmem_cache_16中分配的对象大小全是16字节。不管你要申请多少，反正就是16Bytes。当然，kmem_cache_create仅仅是创建了一个描述slab缓存池布局的数据结构，并没有从伙伴系统申请内存，具体的申请内存操作是在kmeme_cache_alloc中完成的。

2) kmeme_cache_alloc从kmem_cache_16分配一个对象。

3) 内存使用结束记得kmem_cache_free释放。

4) 如果不需要这个kmem_cache的话，就可以调用kmem_cache_destroy进行销毁吧。在释放kmem_cache之前要保证从该kmem_cache中分配的对象全部释放了，否则无法释放kmem_cache。 

3. slub数据结构之间关系

什么是slab缓存池呢？我的解释是使用struct kmem_cache结构描述的一段内存就称作一个slab缓存池。一个slab缓存池就像是一箱牛奶，一箱牛奶中有很多瓶牛奶，每瓶牛奶就是一个object。分配内存的时候，就相当于从牛奶箱中拿一瓶。总有拿完的一天。当箱子空的时候，你就需要去超市再买一箱回来。超市就相当于partial链表，超市存储着很多箱牛奶。如果超市也卖完了，自然就要从厂家进货，然后出售给你。厂家就相当于伙伴系统。

说了这么多终于要抛出辛辛苦苦画的美图了。

好了，后面说的大部分内容请看这张图。足以表明数据结构之间的关系了。看懂了这张图，就可以理清数据结构之间的关系了。

3.1. slub管理object方法

在图片的左上角就是一个slub缓存池中object的分布以及数据结构和kmem_cache之间的关系。首先一个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成员。

3.2. per cpu freelist

针对每一个cpu都会分配一个struct kmem_cacche_cpu的结构体。可以称作是本地缓存池。当内存申请的时候，优先从本地cpu缓存池申请。在分配初期，本地缓存池为空，自然要从伙伴系统分配一定页数的内存。内核会为每一个物理页帧创建一个struct page的结构体。kmem_cacche_cpu中page就会指向正在使用的slab的页帧。freelist成员指向第一个可用内存obj首地址。处于正在使用的slab的struct page结构体中的freelist会置成NULL，因为没有其他地方使用。struct page结构体中inuse代表已经使用的obj数量。这地方有个很有意思的地方，在刚从伙伴系统分配的slab的 inuse在分配初期就置成obj的总数，在分配obj的时候并不会改变。你是不是觉得很奇怪，既然表示已经使用obj的数量，为什么一直是obj的总数呢？你想想，slab中的对象总有分配完的时候，那个时候就直接脱离kmem_cache_cpu了。此时的inuse不就名副其实了嘛！对于full slab就像图的右下角，就像无人看管的孩子，没有任何链表来管理。

3.3. 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链表。

3.4. 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的内存。 

4. slub分配内存原理

当调用kmem_cache_alloc()分配内存的时候，我们可以从正在使用slab分配，也可以从per cpu partial分配，同样还可以从per node partial分配，那么分配的顺序是什么呢？我们可以用下图表示。

首先从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. slub释放内存原理

我们可以通过kmem_cache_free()接口释放申请的obj对象。释放对象的流程如下图所示。

如果释放的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的内存。其他情况就直接释放即可。

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

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

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成员的话的话，释放情况如下图所示。

6. kmalloc

好了，说了这么多，估计你会感觉slab好像跟我们没什么关系。如果作为一个驱动开发者，是不是感觉自己写的driver从来没有使用过这些接口呢？其实我们经常使用，只不过隐藏在kmalloc的面具之下。

kmalloc的内存分配就是基于slab分配器，在系统启动初期调用create_kmalloc_caches ()创建多个管理不同大小对象的kmem_cache，例如：8B、16B、32B、64B、…、64MB等大小。当然默认配置情况下，系统系统启动之后创建的最大size的kmem_cache是kmalloc-8192。因此，通过slab接口分配的最大内存是8192 bytes。那么通过kmalloc接口申请的内存大于8192 bytes该怎么办呢？其实kmalloc会判断申请的内存是否大于8192 bytes，如果大于的话就会通过alloc_pages接口申请内存。kmem_cache的名称以及大小使用struct kmalloc_info_struct管理。所有管理不同大小对象的kmem_cache的名称如下： 

1. const struct kmalloc_info_struct kmalloc_info[] __initconst = {
2. {NULL, 0}, {"kmalloc-96", 96},
3. {"kmalloc-192", 192}, {"kmalloc-8", 8},
4. {"kmalloc-16", 16}, {"kmalloc-32", 32},
5. {"kmalloc-64", 64}, {"kmalloc-128", 128},
6. {"kmalloc-256", 256}, {"kmalloc-512", 512},
7. {"kmalloc-1024", 1024}, {"kmalloc-2048", 2048},
8. {"kmalloc-4096", 4096}, {"kmalloc-8192", 8192},
9. {"kmalloc-16384", 16384}, {"kmalloc-32768", 32768},
10. {"kmalloc-65536", 65536}, {"kmalloc-131072", 131072},
11. {"kmalloc-262144", 262144}, {"kmalloc-524288", 524288},
12. {"kmalloc-1048576", 1048576}, {"kmalloc-2097152", 2097152},
13. {"kmalloc-4194304", 4194304}, {"kmalloc-8388608", 8388608},
14. {"kmalloc-16777216", 16777216}, {"kmalloc-33554432", 33554432},
15. {"kmalloc-67108864", 67108864}
16. };

经过create_kmalloc_caches ()函数之后，系统通过create_kmalloc_cache()创建以上不同size的kmem_cache，并将这些kmem_cache存储在kmalloc_caches全局变量中以备后续kmalloc分配内存。现在假如通过kmalloc(17, GFP_KERNEL)申请内存，系统会从名称“kmalloc-32”管理的slab缓存池中分配一个对象。即使浪费了15Byte。

我们来看看kmalloc的实现方式。 

1. static __always_inline void *kmalloc(size_t size, gfp_t flags)
2. {
3. if (__builtin_constant_p(size)) {
4. if (size > KMALLOC_MAX_CACHE_SIZE)
5. return kmalloc_large(size, flags);
6. if (!(flags & GFP_DMA)) {
7. int index = kmalloc_index(size);
8. if (!index)
9. return ZERO_SIZE_PTR;
10. return kmem_cache_alloc_trace(kmalloc_caches[index], flags, size);
11. }
12. }
13. return __kmalloc(size, flags);
14. }

1)     __builtin_constant_p是gcc工具用来判断参数是否是一个常数，毕竟有些操作对于常数来说是可以优化的。

2)     通过kmalloc_index函数查找符合满足分配大小的最小kmem_cache。

3)     将index作为下表从kmalloc_caches数组中找到符合的kmem_cache，并从slab缓存池中分配对象。

我们再看一下kmalloc_index的实现。 

1. static __always_inline int kmalloc_index(size_t size)
2. {
3. if (!size)
4. return 0;
5. if (size <= KMALLOC_MIN_SIZE)
6. return KMALLOC_SHIFT_LOW;
7. if (KMALLOC_MIN_SIZE <= 32 && size > 64 && size <= 96)
8. return 1;
9. if (KMALLOC_MIN_SIZE <= 64 && size > 128 && size <= 192)
10. return 2;
11. if (size <= 8) return 3;
12. if (size <= 16) return 4;
13. if (size <= 32) return 5;
14. if (size <= 64) return 6;
15. if (size <= 128) return 7;
16. if (size <= 256) return 8;
17. if (size <= 512) return 9;
18. if (size <= 1024) return 10;
19. if (size <= 2 * 1024) return 11;
20. if (size <= 4 * 1024) return 12;
21. if (size <= 8 * 1024) return 13;
22. if (size <= 16 * 1024) return 14;
23. if (size <= 32 * 1024) return 15;
24. if (size <= 64 * 1024) return 16;
25. if (size <= 128 * 1024) return 17;
26. if (size <= 256 * 1024) return 18;
27. if (size <= 512 * 1024) return 19;
28. if (size <= 1024 * 1024) return 20;
29. if (size <= 2 * 1024 * 1024) return 21;
30. if (size <= 4 * 1024 * 1024) return 22;
31. if (size <= 8 * 1024 * 1024) return 23;
32. if (size <= 16 * 1024 * 1024) return 24;
33. if (size <= 32 * 1024 * 1024) return 25;
34. if (size <= 64 * 1024 * 1024) return 26;
35. /* Will never be reached. Needed because the compiler may complain */
36. return -1;
37. } 

1. 原创文章，转发请注明出处。蜗窝科技，www.wowotech.net。

 在linux的内核运行需要动态分配内存的时候，其中有两种分配方案：

第一种是以页为单位分配内存，即一次分配内存的大小必须是页的整数倍
第二种是按需分配，一次分配的内存大小是随机的
​ 对于第一种方案是通过伙伴系统实现，以页为单位管理和分配内存，但是这个单位确实也太大了。对于第二种方案，在现实的需求中，如果我们要为一个10个字符的字符串分配空间，如果按照伙伴系统采用分配一个4KB或者更多空间的完整页面，不仅浪费而且完全不可接受。显然的解决方案是需要将页拆分为更小的单位，可以容纳大量的小对象。同时新的解决方案月不能给内核带来更大的开销，不能对系统性能产生影响，同时也必须保证内存的利用率和效率。基于此，slab的分配器就应运而生，该机制是并没有脱离伙伴系统，是基于伙伴系统分配的大内存进一步细化分成小内存分配，SLAB 就是为了解决这个小粒度内存分配的问题的。

slab分配器对许多可能的工作负荷都能很好工作，但是有一些场景，也无法提供最优化的性能。如果某些计算机处于当前硬件尺度的边界上，slab分配器就会出现一些问题。同时对于嵌入式系统来说slab分配器代码量和复杂度都太高，所以内核增加了两个替代品，所以目前有三种实现算法，分别是slab、slub、slob，并且，依据它们各自的分配算法，在适用性方面会有一定的侧重。

Slab是最基础的，最早基于Bonwick的开创性论文并且可用 自Linux内核版本2.2起。
slob是被改进的slab，针对嵌入式系统进行了特别优化，以便减小代码量。围绕一个简单的内存块链表展开，在分配内存时，使用同样简单的最新适配算法。slob分配器只有大约600行代码，总的代码量很小。从速度来说，它不是最高效的分配器，页肯定不是为大型系统设计的。
slub是在slab上进行的改进简化，在大型机上表现出色，并且能更好的使用NUMA系统，slub相对于slab有5%-10%的性能提升和减小50%的内存占用
文章代码分析基于以linux-4.9.88，以NXP的IMX系列硬件，分析slub的工作原理。

1. 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;
    int size;        /* The size of an object including meta data */
    int object_size;    /* The size of an object without meta data */
    int offset;        /* Free pointer offset. */
    int cpu_partial;    /* Number of per cpu partial objects to keep around */
    struct kmem_cache_order_objects oo;

    /* Allocation and freeing of slabs */
    struct kmem_cache_order_objects max;
    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 */
    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 */
    struct kmem_cache_node *node[MAX_NUMNODES];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
结构体成员变量    含义
cpu_slab    一个per cpu变量，对于每个cpu来说，相当于一个本地内存缓存池。当分配内存的时候优先从本地cpu分配内存以保证cache的命中率。
flags    object分配掩码
min_partial    限制struct kmem_cache_node中的partial链表slab的数量。如果大于这个mini_partial的值，那么多余的slab就会被释放。
size    分配的object size
object_size    实际的object size
offset    offset就是存储下个object地址数据相对于这个object首地址的偏移。
cpu_partial    per cpu partial中所有slab的free object的数量的最大值，超过这个值就会将所有的slab转移到kmem_cache_node的partial链表
oo    oo用来存放分配给slub的页框的阶数(高16位)和 slub中的对象数量(低16位)
min    当按照oo大小分配内存的时候出现内存不足就会考虑min大小方式分配。min只需要可以容纳一个object即可。
allocflags    从伙伴系统分配内存掩码。
list    有一个slab_caches链表，所有的slab都会挂入此链表。
node    slab节点。在NUMA系统中，每个node都有一个struct kmem_cache_node数据结构
在该结构体中，有一个变量struct list_head list，可以想象下，对于操作系统来讲，要创建和管理的缓存不至于task_struct，对于mm_struct，fs_struct都需要这个结构体，所有的缓存最后都会放到这个链表中，也就是LIST_HEAD(slab_caches)。对于缓存中哪些对象被分配，哪些是空着，什么情况下整个大内存块都被分配完了，需要向伙伴系统申请几个页形成新的大内存块？这些信息该由谁来维护呢？？就引出了两个成员变量kmem_cache_cpu和kmem_cache_node。

在分配缓存的时候，需要分两种路径，快速通道(kmem_cache_cpu)和普通通道(kmem_cache_node)，每次分配的时候，要先从kmem_cache_cpu分配；如果kmem_cache_cpu里面没有空闲块，那就从kmem_cache_node中进行分配；如果还是没有空闲块，最后从伙伴系统中分配新的页。

cpu_cache对于每个CPU来说，相当于一个本地内存缓冲池，当分配内存的时候，优先从本地CPU分配内存以及保证cache的命中率，struct kmem_cache_cpu用于管理slub缓存

struct kmem_cache_cpu {
    void **freelist;    /* Pointer to next available object */
    unsigned long tid;    /* Globally unique transaction id */
    struct page *page;    /* The slab from which we are allocating */
    struct page *partial;    /* Partially allocated frozen slabs */
#ifdef CONFIG_SLUB_STATS
    unsigned stat[NR_SLUB_STAT_ITEMS];
#endif
};
1
2
3
4
5
6
7
8
9
结构体成员变量    含义
freelist    指向本地CPU的第一个空闲对象，这一项会有指针指向下一个空闲的项，最终所有空闲的项会形成一个链表
tid    主要用来同步
page    指向大内存块的第一个页，缓存块就是从里面分配的
partial    大内存块的第一个页，之所以名字叫 partial（部分），就是因为它里面部分被分配出去了，部分是空的。这是一个备用列表，当 page 满了，就会从这里找
struct kmem_cache_node：用于管理每个Node的slub页面，由于每个Node的访问速度不一致，slub页面由Node来管理；

struct kmem_cache_node {
    spinlock_t list_lock;
#ifdef CONFIG_SLUB
    unsigned long nr_partial;               /* partial slab链表中slab的数量 */
    struct list_head partial;               /* partial slab链表表头 */
#ifdef CONFIG_SLUB_DEBUG
    atomic_long_t nr_slabs;                 /* 节点中的slab数 */  
    atomic_long_t total_objects;            /* 节点中的对象数 */  
    struct list_head full;                  /* full slab链表表头 */  
#endif
#endi
}
1
2
3
4
5
6
7
8
9
10
11
12
结构体成员变量    含义
list_lock    自旋锁，保护数据
nr_partial    partial slab链表中slab的数量
partial    这个链表里存放的是部分空闲的大内存块。这是 kmem_cache_cpu 里面的 partial 的备用列表，如果那里没有，就到这里来找。
其结构图如下图所示

2. 初始化
为了初始化slub的数据结构，内核需要若干远小于一整页的内存块，这些最适合使用kmalloc来分配。但是此时只有slub系统已经完成初始化后，才能使用kmalloc。换而言之，kmalloc只能在kmalloc已经初始化之后初始化，这个是不可能，所以内核使用kmem_cache_init函数用于初始化slub分配器。
分配器的初始化工作主要是初始化用于kmalloc的gerneral cache，slub分配器的gerneral cache定义如下：

extern struct kmem_cache *kmalloc_caches[KMALLOC_SHIFT_HIGH + 1];
#define KMALLOC_SHIFT_HIGH    (PAGE_SHIFT + 1)
#define PAGE_SHIFT  12 
//(各个架构下的定义都有些差异,如果是arm64,那么是通过CONFIG_ARM64_PAGE_SHIFT来指定的,这个配置项在arch/arm64/Kconfig文件中定义,默认为12，也就是默认页面大小为4KiB,笔者以arm64为例)
1
2
3
4
那么KMALLOC_SHIFT_HIGH=PAGE_SHIFT + 1 = 12 + 1 = 13,KMALLOC_SHIFT_HIGH+1=13+ 1= 14说明kmalloc_caches数组中有14个元素,每个元素是kmem_cache这个结构体

它在内核初始化阶段(start_kernel)、伙伴系统启用之后调用，它首先执行缓存初始化过程，如下图所示

从缓存中分配kmem_cache对象，并复制并使用临时kmem_cache
从缓存中分配kmem_cache_node对象，然后复制并使用临时使用的kmem_cache_node
kmalloc boot cache
起初并没有boot cache，因此定义了两个静态变量（boot_kmem_cache，boot_kmem_cache_node）用于临时使用。这里的核心是boot cache创建函数：create_boot_cache()

当调用create_boot_cache创建完kmem_cache和kmem_cache_node两个Cache后，就需要调用bootstrap从Cache中为kmem_cache和kmem_cache_node分配内存空间然后将静态变量boot_kmem_cache和boot_kmem_cache_node中的内容复制到分配的内存空间中，这相当于完成了一次对自身的重建。

static struct kmem_cache * __init bootstrap(struct kmem_cache *static_cache)
{
    int node;
    struct kmem_cache *s = kmem_cache_zalloc(kmem_cache, GFP_NOWAIT);                                        --------------------(1)
    struct kmem_cache_node *n;

    memcpy(s, static_cache, kmem_cache->object_size);

    /*
     * This runs very early, and only the boot processor is supposed to be
     * up.  Even if it weren't true, IRQs are not up so we couldn't fire
     * IPIs around.
     */
    __flush_cpu_slab(s, smp_processor_id());
    for_each_kmem_cache_node(s, node, n) {                                                                   --------------------(2)
        struct page *p;

        list_for_each_entry(p, &n->partial, lru)
            p->slab_cache = s;

#ifdef CONFIG_SLUB_DEBUG
        list_for_each_entry(p, &n->full, lru)
            p->slab_cache = s;
#endif
    }
    slab_init_memcg_params(s);
    list_add(&s->list, &slab_caches);
    return s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
1.首先将会通过kmem_cache_zalloc()申请kmem_cache空间，值得注意的是该函数申请调用kmem_cache_zalloc()->kmem_cache_alloc()->slab_alloc()，其最终将会通过前面create_boot_cache()初始化创建的kmem_cache来申请slub空间来使用。临时使用的kmem_cache结构形式接收的参数static_cache的内容复制到新分配的缓存中，其大小与object_size相同。早期引导过程中，因此无法对其他CPU进行IPI调用，因此仅刷新本地CPU。

2.通过for_each_node_state()遍历各个内存管理节点node,在通过get_node()获取对应节点的slab，如果slab不为空这回遍历部分满slab链，修正每个slab指向kmem_cache的指针，如果开启CONFIG_SLUB_DEBUG，则会遍历满slab链，设置每个slab指向kmem_cache的指针；最后将kmem_cache添加到全局slab_caches链表中。

接下来是创建kmalloc boot cache - create_kmalloc_caches()，来初始化kmalloc_caches表，其最终创建的kmalloc_caches是以{0,96,192,8,16,32,64,128,256,512,1024,2046,4096，8196}为大小的slab表；创建完之后，将设置slab_state为UP，然后将kmem_cache的name成员进行初始化；最后如果配置了CONFIG_ZONE_DMA，将会初始化创建kmalloc_dma_caches表。可以得到size_index与kmalloc_caches的对应关系

我们以通常情况下KMALLOC_MIN_SIZE等于8为例进行说明。size_index[0-23]数组根据对象大小映射到不同的kmalloc_caches[0-13]保存的cache。观察kmalloc_caches[0-13]数组，可见索引即该cache slab块的order。由于最小对象为8（23）字节，kmalloc_caches[0-2]这三个数组元素没有用到，slub使用kmalloc_caches[1]保存96字节大小的对象，kmalloc_caches[2] 保存192字节大小的对象，相当于细分了kmalloc的粒度，有利于减少空间的浪费。kmalloc_caches[0]未使用。

3. 总结
slab分配器中用到了对象这个概念，就是内核中的数据结构以及对该数据结构进行创建和撤销的操作。其核心思想如下

将内核中经常使用的对象放到高速缓存中，并且由系统保持为初始的可利用状态，比如进程描述符，内核中会频繁对此数据进行申请和释放
当一个新进场创建时，内核就会直接从slab分配器的高速缓存中获取一个已经初始化的对象
当进程结束时，该结构所占的页框并不被释放，而是重新返回slab分配器中，如果没有基于对象的slab分配器，内核将花费更多的时间去分配、初始化、已经释放对象。

上图显示了slab、cache及object 三者之间的关系。该图显示了2个大小为3KB 的内核对象和3个大小为7KB的对象，它们位于各自的cache中。slab分配算法采用 cache来存储内核对象。在创建 cache 时，若干起初标记为free的对象被分配到 cache。cache内的对象数量取决于相关slab的大小。例如，12KB slab(由3个连续的4KB页面组成)可以存储6个2KB对象。最初，cache内的所有对象都标记为空闲。当需要内核数据结构的新对象时，分配器可以从cache上分配任何空闲对象以便满足请求。从cache上分配的对象标记为used(使用)。

让我们考虑一个场景，这里内核为表示进程描述符的对象从slab分配器请求内存。在 Linux 系统中，进程描述符属于 struct task_struct 类型，它需要大约1.7KB的内存。当Linux内核创建一个新任务时，它从cache中请求 struct task_struct对象的必要内存。cache 利用已经在slab中分配的并且标记为 free (空闲)的 struct task_struct对象来满足请求。
在Linux中，slab可以处于三种可能状态之一：

满的：slab的所有对象标记为使用。
空的：slab上的所有对象标记为空闲。
部分：slab上的对象有的标记为使用，有的标记为空闲。
slab分配器首先尝试在部分为空的slab中用空闲对象来满足请求。如果不存在，则从空的slab 中分配空闲对象。如果没有空的slab可用，则从连续物理页面分配新的slab，并将其分配给cache；从这个slab上，再分配对象内存。slab分配器提供两个主要优点：

减小伙伴算法在分配小块连续内存时所产生的内部碎片问题，因为每个内核数据结构都有关联的cache，每个 cache都由一个或多个slab组成，而slab按所表示对象的大小来分块。因此，当内核请求对象内存时，slab 分配器可以返回刚好表示对象的所需内存。
将频繁使用的对象缓存起来，减小分配、初始化和释放的时间开销 ，当对象频繁地被分配和释放时，如来自内核请求的情况，slab 分配方案在管理内存时特别有效。分配和释放内存的动作可能是一个耗时过程。然而，由于对象已预先创建，因此可以从cache 中快速分配。再者，当内核用完对象并释放它时，它被标记为空闲并返回到cache，从而立即可用于后续的内核请求。
对于伙伴系统和slab分配器，就好比“批发商”和“零售商”，“批发商”，是指按页面管理并分配内存的机制；而“零售商”，则是从“批发商”那里批发获取资源，并以字节为单位，管理和分配内存的机制。作为零售商的slab，那么就需要解决两个问题

该如何从批发商buddy system批发内存
如何管理批发的内存并把这些内存“散卖“出去，如何使这些散内存由更高的使用效率

背景

• Read the fucking source code! --By 鲁迅
• A picture is worth a thousand words. --By 高尔基

说明：

1. Kernel版本：4.14
2. ARM64处理器，Contex-A53，双核
3. 使用工具：Source Insight 3.5， Visio

1. 概述

之前的文章分析的都是基于页面的内存分配，而小块内存的分配和管理是通过块分配器来实现的。目前内核中，有三种方式来实现小块内存分配：slab, slub, slob，最先有slab分配器，slub/slob分配器是改进版，slob分配器适用于小内存嵌入式设备，而slub分配器目前已逐渐成为主流块分配器。接下来的文章，就是以slub分配器为目标，进一步深入。

先来一个初印象：

2. 数据结构

有四个关键的数据结构：

• struct kmem_cache：用于管理SLAB缓存，包括该缓存中对象的信息描述，per-CPU/Node管理slab页面等；
  关键字段如下：

/** Slab cache management.*/
struct kmem_cache {struct kmem_cache_cpu __percpu *cpu_slab;       //每个CPU slab页面/* Used for retriving partial slabs etc */unsigned long flags;unsigned long min_partial;int size;		/* The size of an object including meta data */int object_size;	/* The size of an object without meta data */int offset;		/* Free pointer offset. */
#ifdef CONFIG_SLUB_CPU_PARTIAL/* Number of per cpu partial objects to keep around */unsigned int cpu_partial;
#endifstruct kmem_cache_order_objects oo;     //该结构体会描述申请页面的order值，以及object的个数/* Allocation and freeing of slabs */struct kmem_cache_order_objects max;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 */int reserved;		/* Reserved bytes at the end of slabs */int red_left_pad;	/* Left redzone padding size */const char *name;	/* Name (only for display!) */struct list_head list;	/* List of slab caches */       //kmem_cache最终会链接在一个全局链表中struct kmem_cache_node *node[MAX_NUMNODES];     //Node管理slab页面
};

• struct kmem_cache_cpu：用于管理每个CPU的slab页面，可以使用无锁访问，提高缓存对象分配速度；

struct kmem_cache_cpu {void **freelist;	/* Pointer to next available object */                  //指向空闲对象的指针unsigned long tid;	/* Globally unique transaction id */                struct page *page;	/* The slab from which we are allocating */     //slab缓存页面
#ifdef CONFIG_SLUB_CPU_PARTIALstruct page *partial;	/* Partially allocated frozen slabs */
#endif
#ifdef CONFIG_SLUB_STATSunsigned stat[NR_SLUB_STAT_ITEMS];
#endif
};

• struct kmem_cache_node：用于管理每个Node的slab页面，由于每个Node的访问速度不一致，slab页面由Node来管理；

/** The slab lists for all objects.*/
struct kmem_cache_node {spinlock_t list_lock;#ifdef CONFIG_SLUBunsigned long nr_partial;    //slab页表数量struct list_head partial;       //slab页面链表
#ifdef CONFIG_SLUB_DEBUGatomic_long_t nr_slabs;atomic_long_t total_objects;struct list_head full;
#endif
#endif
};

• struct page：用于描述slab页面，struct page结构体中很多字段都是通过union联合体进行复用的。
  struct page结构中，用于slub的成员如下：

struct page {union {...void *s_mem;			/* slab first object */...};/* Second double word */union {...void *freelist;		/* sl[aou]b first free object */...};union {...struct {union {...struct {			/* SLUB */unsigned inuse:16;unsigned objects:15;unsigned frozen:1;};...};...};       };   /** Third double word block*/union {...struct {		/* slub per cpu partial pages */struct page *next;	/* Next partial slab */
#ifdef CONFIG_64BITint pages;	/* Nr of partial slabs left */int pobjects;	/* Approximate # of objects */
#elseshort int pages;short int pobjects;
#endif};struct rcu_head rcu_head;	/* Used by SLAB* when destroying via RCU*/};...struct kmem_cache *slab_cache;	/* SL[AU]B: Pointer to slab */    ...
}

图来了：

3. 流程分析

针对Slub的使用，可以从三个维度来分析：

1. slub缓存创建
2. slub对象分配
3. slub对象释放

下边将进一步分析。

3.1 kmem_cache_create

在内核中通过kmem_cache_create接口来创建一个slab缓存。

先看一下这个接口的函数调用关系图：

1. kmem_cache_create完成的功能比较简单，就是创建一个用于管理slab缓存的kmem_cache结构，并对该结构体进行初始化，最终添加到全局链表中。kmem_cache结构体初始化，包括了上文中分析到的kmem_cache_cpu和kmem_cache_node两个字段结构。

2. 在创建的过程中，当发现已有的slab缓存中，有存在对象大小相近，且具有兼容标志的slab缓存，那就只需要进行merge操作并返回，而无需进一步创建新的slab缓存。

3. calculate_sizes函数会根据指定的force_order或根据对象大小去计算kmem_cache结构体中的size/min/oo等值，其中kmem_cache_order_objects结构体，是由页面分配order值和对象数量两者通过位域拼接起来的。

4. 在创建slab缓存的时候，有一个先鸡后蛋的问题：kmem_cache结构体来管理一个slab缓存，而创建kmem_cache结构体又是从slab缓存中分配出来的对象，那么这个问题是怎么解决的呢？可以看一下kmem_cache_init函数，内核中定义了两个静态的全局变量kmem_cache和kmem_cache_node，在kmem_cache_init函数中完成了这两个结构体的初始化之后，相当于就是创建了两个slab缓存，一个用于分配kmem_cache结构体对象的缓存池，一个用于分配kmem_cache_node结构体对象的缓存池。由于kmem_cache_cpu结构体是通过__alloc_percpu来分配的，因此不需要创建一个相关的slab缓存。

3.2 kmem_cache_alloc

kmem_cache_alloc接口用于从slab缓存池中分配对象。

看一下大体的调用流程图：

从上图中可以看出，分配slab对象与Buddy System中分配页面类似，存在快速路径和慢速路径两种，所谓的快速路径就是per-CPU缓存，可以无锁访问，因而效率更高。

整体的分配流程大体是这样的：优先从per-CPU缓存中进行分配，如果per-CPU缓存中已经全部分配完毕，则从Node管理的slab页面中迁移slab页到per-CPU缓存中，再重新分配。当Node管理的slab页面也不足的情况下，则从Buddy System中分配新的页面，添加到per-CPU缓存中。

还是用图来说明更清晰，分为以下几步来分配：

1. fastpath
   快速路径下，以原子的方式检索per-CPU缓存的freelist列表中的第一个对象，如果freelist为空并且没有要检索的对象，则跳入慢速路径操作，最后再返回到快速路径中重试操作。

   

2. slowpath-1
   将per-CPU缓存中page指向的slab页中的空闲对象迁移到freelist中，如果有空闲对象，则freeze该页面，没有空闲对象则跳转到slowpath-2。

   

3. slowpath-2
   将per-CPU缓存中partial链表中的第一个slab页迁移到page指针中，如果partial链表为空，则跳转到slowpath-3。

   

4. slowpath-3
   将Node管理的partial链表中的slab页迁移到per-CPU缓存中的page中，并重复第二个slab页将其添加到per-CPU缓存中的partial链表中。如果迁移的slab中空闲对象超过了kmem_cache.cpu_partial的一半，则仅迁移slab页，并且不再重复。
   如果每个Node的partial链表都为空，跳转到slowpath-4。

   

5. slowpath-4
   从Buddy System中获取页面，并将其添加到per-CPU的page中。

   

3.2 kmem_cache_free

kmem_cache_free的操作，可以看成是kmem_cache_alloc的逆过程，因此也分为快速路径和慢速路径两种方式，同时，慢速路径中又分为了好几种情况，可以参考kmem_cache_alloc的过程。

调用流程图如下：

效果如下：

1. 快速路径释放
   快速路径下，直接将对象返回到freelist中即可。

   

2. put_cpu_partial
   put_cpu_partial函数主要是将一个刚freeze的slab页，放入到partial链表中。
   在put_cpu_partial函数中调用unfreeze_partials函数，这时候会将per-CPU管理的partial链表中的slab页面添加到Node管理的partial链表的尾部。如果超出了Node的partial链表，溢出的slab页面中没有分配对象的slab页面将会返回到伙伴系统。

   

3. add_partial
   添加slab页到Node的partial链表中。

   

4. remove_partial
   从Node的partial链表移除slab页。

   

具体释放的流程走哪个分支，跟对象的使用情况，partial链表的个数nr_partial/min_partial等相关，细节就不再深入分析了。