内核管理页面使用了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()申请）。

Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。

它的内容包括：

大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw

目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：

想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询

同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】即可免费领取。

阅读全文

操作系统详解

linux内存管理笔记(二八)--内存管理 slub算法

1. slub的分配原理

2. slub分配和释放API

3. kmalloc分配函数