内核管理页面使用了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_SLOB
if (!(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;
}
根据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];
}
- 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
- 最后如果开启了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()申请）。
