【OS.0x04】Linux 内核内存管理浅析 III - Slub Allocator

本文最后更新于：2023年12月18日 早上

别人问你哪里丑态你再把他反手挂到自己的小 slub 里寻求认同

0x00.一切开始之前

因为这系列文章🕊🕊🕊太久了，内核的内存管理也发生了一定的变化，所以本文直接用最新的 6.2 版本的内核源码：）

在上一篇文章 中笔者简要介绍了 buddy system 的基本流程，但其为一个「页」这一级的 allocator，在日常生活中使用（？）难免有些浪费，因为内核中需要动态内存分配的场景虽然很多，但是我们通常并不需要使用一整页起步的内存，而往往是需要分配一些比较小的对象——因此 slab allocator 应运而生，其代替我们向 buddy system 请求内存页，并分割为多个小的 object，当我们每次需要时只需要取一个 object 即可

slab 又被称为内核的堆（heap）内存管理，因为其与用户态的内存“堆”（heap）类似，都是动态分配的内存

slab allocator 一共有三种版本：

  • slab（最初的版本，机制比较复杂，效率不高）
  • slob（用于嵌入式等场景的极为简化版本）
  • slub（优化后的版本，现在的通用版本）

这三种内存分配器的顶层 API 是一致的，但内部实现是不一致的（例如 slab 和 slub 各自有一个对 kmem_cache 的不同定义）

本篇文章中我们主要介绍的是 slub ，也是现在内核中最为通用的小对象分配器

0x01. slub allocator 的基本结构

首先来一张 Overview：

image.png

一、slab：单份 object 池

Linux kernel 中用以统筹所有内存的依然是 buddy system，slub allocator 也不例外，其负责向 buddy system 请求内存后分割给多个小 object 后再返还给上层调用者，单次向 buddy system 所请求的一份连续内存页便称之为一张 slab，在内核中对应 slab 结构体，本质上是复用 page 结构体：

这里我们仅关注 slub，所以笔者仅截取 slub 所需字段

老版本中 slab 是直接内嵌在 page 结构体中的

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
30
31
32
33
34
35
36
37
38
39
40
41
42
/* Reuses the bits in struct page */
struct slab {
	unsigned long __page_flags;

//...

#elif defined(CONFIG_SLUB)

	struct kmem_cache *slab_cache;
	union {
		struct {
			union {
				struct list_head slab_list;
#ifdef CONFIG_SLUB_CPU_PARTIAL
				struct {
					struct slab *next;
					int slabs;	/* 剩余的 slabs 数量 */
				};
#endif
			};
			/* Double-word boundary */
			void *freelist;		/* 第一个空闲对象 */
			union {
				unsigned long counters;
				struct {
					unsigned inuse:16;
					unsigned objects:15;
					unsigned frozen:1;
				};
			};
		};
		struct rcu_head rcu_head;
	};
	unsigned int __unused;

//...

	atomic_t __page_refcount;
#ifdef CONFIG_MEMCG
	unsigned long memcg_data;
#endif
};
  • slab_cache ：该 slab 对应的内存池
  • freelist ：Slab 上的空闲对象组织为一个 NULL 结尾的单向链表，该指针指向第一个空闲对象，耗尽时为 NULL
  • slab_list ：按用途连接多个 slabs 的双向链表
  • inuse ：已被使用的对象数量
  • objects：该 slab 上的对象总数
  • frozen：是否被冻结，即已经归属于特定的 CPU

这里我们需要注意的是 counters 成员直接涵盖了 inuse & objects & frozen，后面会有大量的直接通过 counters 成员进行赋值的操作，实际上就是赋值了 inuse & objects & frozen

正如一个 page 结构体直接对应一张内存页（或复合页），复用了 page 结构体的 slab 也直接对应一份 slab 内存页，借助 page_to_pfn() 等函数可以直接完成 slab 结构体到对应内存页虚拟地址的转换，反之亦然，即我们可以直接通过一个空闲对象的虚拟地址找到对应的 slab 结构体

image.png

二、kmem_cache：特定大小&用途对象（堆块）的内存池

kmem_cache 为一个基本的 allocator 组件，可以理解为 用于分配某个特定大小（某种特定用途）的对象的内存池，所有的 kmem_cache 构成一个双向链表，并存在一个对应的通用 kmem_cache 数组 kmalloc_caches 

1
2
3
4
struct kmem_cache *
kmalloc_caches[NR_KMALLOC_TYPES][KMALLOC_SHIFT_HIGH + 1] __ro_after_init =
{ /* initialization for https://bugs.llvm.org/show_bug.cgi?id=42570 */ };
EXPORT_SYMBOL(kmalloc_caches);

老版本还有个 dma 专用数组 kmalloc_dma_caches ，在 这个 commit 给合并起来了

I. 基本结构

该结构体定义于 include/linux/slub_def.h 中，如下：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*
 * Slab 缓存管理.
 */
struct kmem_cache {
#ifndef CONFIG_SLUB_TINY
	struct kmem_cache_cpu __percpu *cpu_slab;
#endif
	/* 用于取回 partial slabs 等. */
	slab_flags_t flags;
	unsigned long min_partial;
	unsigned int size;	/* 一个对象包含元数据的大小 */
	unsigned int object_size;/* 一个对象不包含元数据的大小 */
	struct reciprocal_value reciprocal_size;
	unsigned int offset;	/* 空闲指针的偏移 */
#ifdef CONFIG_SLUB_CPU_PARTIAL
	/* 要保留的 per cpu partial 对象数量 */
	unsigned int cpu_partial;
	/* 要保留的 per cpu partial slub 数量 */
	unsigned int cpu_partial_slabs;
#endif
	struct kmem_cache_order_objects oo;

	/* 分配与释放 slabs */
	struct kmem_cache_order_objects min;
	gfp_t allocflags;	/* （译注：向 buddy system）分配时所用的 gfp 标志位 */
	int refcount;		/* 用于 slab 缓存销毁的引用计数 */
	void (*ctor)(void *);
	unsigned int inuse;		/* 元数据的偏移 */
	unsigned int align;		/* 对齐 */
	unsigned int red_left_pad;	/* Left redzone padding size */
	const char *name;	/* Name (only for display!) */
	struct list_head list;	/* slab 缓存链表 */
#ifdef CONFIG_SYSFS
	struct kobject kobj;	/* For sysfs */
#endif
#ifdef CONFIG_SLAB_FREELIST_HARDENED
	unsigned long random;	// 用于加密 freelist 指针的随机值
#endif

#ifdef CONFIG_NUMA
	/*
	 * 通过从一个 remote node 分配以去碎片化.
	 */
	unsigned int remote_node_defrag_ratio;
#endif

#ifdef CONFIG_SLAB_FREELIST_RANDOM
	unsigned int *random_seq;	// 用于在初始化时随机化 freelist
#endif

#ifdef CONFIG_KASAN
	struct kasan_cache kasan_info;
#endif

#ifdef CONFIG_HARDENED_USERCOPY
	unsigned int useroffset;	/* 用户拷贝区域的偏移 */
	unsigned int usersize;		/* 用户拷贝区域的大小 */
#endif

	struct kmem_cache_node *node[MAX_NUMNODES];
};

  • cpu_slab： percpu 变量 ，指向一个 kmem_cache_cpu 结构体，即当前 CPU 独占的内存池

  • flags：标志位

  • min_partial：node partial 链表上 slab 的最大数量（👴也不知道为什么要叫min，但实际判定发挥的是max的作用）

  • cpu_partial_slabs：cpu partial 链表上 slab 的最大数量

  • cpu_partial：per cpu partial list 中最多的对象数量（但好象是没啥用）

  • size：一个对象的实际大小

  • object_size：一个对象所用数据的大小

    例如 struct cred 大小为 176（object_size），实际分配的对象大小为 192 （size）

  • offset：slab 上空闲对象链表指针在对象上的偏移

  • oo ： 其实就是一个 int

    • 低 16 位：一张 slab 上的对象数量
    • 高 16 位：一张 slab 的大小（2n 张内存页）

  • min：一张 slab 上最少的对象数量

  • allocflags：向 buddy system 请求页面时所用的 gfp flag

  • ctor：对象的构造函数，在分配对象后会调用该函数进行初始化

  • inuse：实际上就是 object_size

  • align：对象对齐的宽度

  • Randomed freelist 保护相关：

    • random_seq ：用于在 slab 初始化时随机化 freelist 上空闲对象的连接顺序

  • Hardened Usercopy 保护相关

    • useroffset：用户空间能读写区域的起始偏移
    • usersize：用户空间能读写区域的大小

  • node：一个 kmem_cache_node 数组，对应多个不同 node 的后备内存池

image.png

II. 类型

初始时一共有如下几种类型的 kmem_cache，在进行内存分配时若未指定内存池则会根据对应的 flag 从不同的 kmem_cache 中取：

  • KMALLOC_NORMAL ：通用类型内存池，对应 kmalloc-*，对应分配 flag 为 GFP_KERNEL
  • KMALLOC_DMA：用于 DMA 的内存池，对应 kmalloc-dma-*
  • KMALLOC_RECLAIM 可以被回收的内存池，对应 kmalloc-rcl-*
  • KMALLOC_CGROUP ：用于需要进行数量统计（accounted，主要用于 CGROUP 相关）的内存池，对应 kmalloc-cg-* ，对应分配 flag 为 GFP_KERNEL_ACCOUNT

若是未开启对应的编译选项，则默认合并入 KMALLOC_NORMAL 

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
/*
 * Whenever changing this, take care of that kmalloc_type() and
 * create_kmalloc_caches() still work as intended.
 *
 * KMALLOC_NORMAL can contain only unaccounted objects whereas KMALLOC_CGROUP
 * is for accounted but unreclaimable and non-dma objects. All the other
 * kmem caches can have both accounted and unaccounted objects.
 */
enum kmalloc_cache_type {
	KMALLOC_NORMAL = 0,
#ifndef CONFIG_ZONE_DMA
	KMALLOC_DMA = KMALLOC_NORMAL,
#endif
#ifndef CONFIG_MEMCG_KMEM
	KMALLOC_CGROUP = KMALLOC_NORMAL,
#endif
#ifdef CONFIG_SLUB_TINY
	KMALLOC_RECLAIM = KMALLOC_NORMAL,
#else
	KMALLOC_RECLAIM,
#endif
#ifdef CONFIG_ZONE_DMA
	KMALLOC_DMA,
#endif
#ifdef CONFIG_MEMCG_KMEM
	KMALLOC_CGROUP,
#endif
	NR_KMALLOC_TYPES
};

III. slab alias（mergeability）

slab alias 机制是一种对同等/相近大小 object 的 kmem_cache 进行复用的一种机制：

  • 当一个 kmem_cache 在创建时，若已经存在能分配相等/近似大小的 object 的 kmem_cache ，则不会创建新的 kmem_cache，而是为原有的 kmem_cache 起一个 alias，作为“新的” kmem_cache 返回

举个🌰，cred_jar 是专门用以分配 cred 结构体的 kmem_cache，在 Linux 4.4 之前的版本中，其为 kmalloc-192 的 alias，即 cred 结构体与其他的 192 大小的 object 都会从同一个 kmem_cache——kmalloc-192 中分配

对于初始化时设置了 SLAB_ACCOUNT 这一 flag 的 kmem_cache 而言，则会新建一个新的 kmem_cache 而非为原有的建立 alias，🌰如在新版的内核当中 cred_jar 与 kmalloc-192 便是两个独立的 kmem_cache，彼此之间互不干扰

三、kmem_cache_cpu：各 CPU 独占内存池

当进程向 slab allocator 请求内存分配时，首先会尝试从当前 CPU 的独占内存池进行分配 ——kmem_cache_cpu 结构体表示每个 CPU 独占的内存池，其在 kmem_cache 中为一个 percpu 变量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
 * When changing the layout, make sure freelist and tid are still compatible
 * with this_cpu_cmpxchg_double() alignment requirements.
 */
struct kmem_cache_cpu {
	void **freelist;	/* 指向下一个可用对象的指针 */
	unsigned long tid;	/* Globally unique transaction id */
	struct slab *slab;	/* 用以内存分配的 slab */
#ifdef CONFIG_SLUB_CPU_PARTIAL
	struct slab *partial;	/* Partially allocated frozen slabs */
#endif
	local_lock_t lock;	/* Protects the fields above */
#ifdef CONFIG_SLUB_STATS
	unsigned stat[NR_SLUB_STAT_ITEMS];
#endif
};
  • freelist：指向下一个空闲对象的指针
  • slab：当前用以进行内存分配的 slab
  • partial：percpu partial slab 链表，链表上为仍有一定空闲对象的 slab

slab 的 freelist 仅当其在 partial 链表上时有用，当一张 slab 为当前 CPU 正在使用的 slab 时，其 freelist 为 NULL，由 kmem_cache_cpu.freelist 指向第一个空闲对象

image.png

四、kmem_cache_node：各 node 后备内存池

每个 node 对应的后备内存池，当 percpu 的独占内存池耗尽后便会从对应 node 的后备内存池尝试分配

不过大部分计算机都仅有一个 node，所以通常情况下每个 kmem_cache 也就只有一个 kmem_cache_node 😄

因为本文主要讲 slub，所以仅截取 slub 相关字段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef CONFIG_SLOB
/*
 * The slab lists for all objects.
 */
struct kmem_cache_node {
#ifdef CONFIG_SLAB
	//...
#endif

#ifdef CONFIG_SLUB
	spinlock_t list_lock;
	unsigned long nr_partial;
	struct list_head partial;
#ifdef CONFIG_SLUB_DEBUG
	atomic_long_t nr_slabs;
	atomic_long_t total_objects;
	struct list_head full;
#endif
#endif

};
  • list_lock：保护 partial 和 full 链表的锁
  • partial：partial slab 链表，连接有着部分空闲对象剩余的 slab
  • nr_partial：partial slab 的数量
  • full：full slab 链表，连接空闲对象完全耗尽的 slab（注：该链表基本上不常用）
  • nr_slabs：总的 slab 数量
  • total_objects：总的对象数量

image.png

0x02. 对象的分配

※ 一、slab_alloc_node()：从指定的 kmem_cache 分配 object

在 slab allocator 中存在着多个不同的内存分配接口，其最后都会调用到 slab_alloc_node() 完成内存分配的工作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * 内联化的快速路径以让分配函数 (kmalloc, kmem_cache_alloc) 中包含快速路径.
 * 因此，对于快速路径可以满足的请求，没有函数调用的开销.
 *
 * 快速路径首先检查无锁的空闲链表是否可以被使用.
 * 若否，调用 __slab_alloc 进行缓慢处理.
 *
 * 否则我们可以简单地从无锁空闲链表取出下一个对象.
 */
static __fastpath_inline void *slab_alloc_node(struct kmem_cache *s, struct list_lru *lru,
		gfp_t gfpflags, int node, unsigned long addr, size_t orig_size)
{
	void *object;
	struct obj_cgroup *objcg = NULL;
	bool init = false;

该函数首先会调用 slab_pre_alloc_hook() 进行分配前的检查工作，不通过则返回 NULL，这一步主要是检查分配标志位是否合法等：

1
2
3
s = slab_pre_alloc_hook(s, lru, &objcg, 1, gfpflags);
if (!s)
	return NULL;

接下来调用 kfence_alloc() 进行内存错误检测，不通过则直接跳转到 out，这里用到了 Kfence (Kernel Electric Fence) 内存纠错机制，主要是检查对 data page 的访问是否越界：

1
2
3
object = kfence_alloc(s, orig_size, gfpflags);
if (unlikely(object))
	goto out;

接下来调用 __slab_alloc_node() 进行正式的内存分配，这一步便是真正的核心分配函数：

1
object = __slab_alloc_node(s, gfpflags, node, addr, orig_size);

最后调用 maybe_wipe_obj_freeptr() 将 object 原本存放 next free object 指针的位置清零，之后调用 slab_want_init_on_alloc() 检查标志位是否有 __GFP_ZERO，若有则调用 slab_post_alloc_hook() 将 object 上数据清零

1
2
3
4
5
6
7
8
9
10
11
12
	maybe_wipe_obj_freeptr(s, object);
	init = slab_want_init_on_alloc(gfpflags, s);

out:
	/*
	 * 当 init == 'true', 类似 kzalloc() 族, 
	 * 仅有 @orig_size 字节会被清零，而非 s->object_size
	 */
	slab_post_alloc_hook(s, objcg, gfpflags, 1, &object, init, orig_size);

	return object;
}

接下来我们来看真正的核心分配函数 __slab_alloc_node()

I. __slab_alloc_node()：从 percpu freelist 进行分配（fast path）

该函数首先会先获取 percpu 的 kmem_cache_cpu 上的 freelist 与 slab，若 slab 或 freelist 为空 / slab 与 node 不匹配，则调用 __slab_alloc() 分配一张新 slab 并从其中获取一个空闲对象：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
static __always_inline void *__slab_alloc_node(struct kmem_cache *s,
		gfp_t gfpflags, int node, unsigned long addr, size_t orig_size)
{
	struct kmem_cache_cpu *c;
	struct slab *slab;
	unsigned long tid;
	void *object;

redo:
	/*
	 * 必须通过该 cpu ptr 读取 kmem_cache cpu 数据. 抢占是开启的.
	 * 我们可能会在从一个 cpu 区域读取时在 cpu 间切换.
	 * 只要我们在 cmpxchg 时在原本的 cpu 上重新结束便不要紧.
	 *
	 * 我们必须保证 tid 与 kmem_cache_cpu 被在同一 cpu 上取回.
	 * 我们首先读取 kmem_cache_cpu 指针并用其读取 tid.
	 * 若我们在两次读取间被抢占并切换到另一 cpu，由于这两者仍与同一 cpu 关联，
	 * cmpxchg 稍后将会验证 cpu ，这是 OK 的.
	 */
	c = raw_cpu_ptr(s->cpu_slab);
	tid = READ_ONCE(c->tid);

	/*
	 * 此处使用的无中断（irqless） 对象分配/释放算法决定于获取 cpu_slab 数据的顺序.
	 * tid 应当在在 c 上的任何事之前被获取以确保与此前 tid 关联的对象与 slab
	 * 不会被与当前 tid 一起使用. 若我们先获取 tid，对象与 slab 可能会与下一个 tid 
	 * 相关联，而我们的分配/释放请求也将会失败.这种情况下我们会重试所以没问题.
	 */
	barrier();

	/*
	 * The transaction ids are globally unique per cpu and per operation on
	 * a per cpu queue（这句翻成中文咋都不顺，直接看原文吧😄）.
	 * 由此可以确保 cmpxchg_double 发生在正确的处理器上且其间在链表上没有任何操作.
	 */

	object = c->freelist;
	slab = c->slab;

	if (!USE_LOCKLESS_FAST_PATH() ||
	    unlikely(!object || !slab || !node_match(slab, node))) {
		object = __slab_alloc(s, gfpflags, node, addr, c, orig_size);

若有 freelist & slub，则调用 get_freepointer_safe() 获取当前空闲对象下一个空闲对象；接下来 this_cpu_cmpxchg_double() 会检查是否 freelist == object、cpu_slab->tid == tid，若是则将 freelist 设为 next_object 并获取设置下一 tid，否则说明发生了抢占（我们已经不在原 cpu 上了），跳转回 redo 重新在当前 cpu 上进行分配：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
} else {
	void *next_object = get_freepointer_safe(s, object);

	/*
	 * 仅当没有额外操作且我们在正确的处理器上时 cmpxchg 将匹配.
	 *
	 * cmpxchg 原子地进行了如下： (没有锁语义!)
	 * 1. 重定位第一个指针到当前的 per cpu 区域.
	 * 2. 验证 tid & freelist 没有被改变
	 * 3. 若未被改变，替换 tid & freelist
	 *
	 * 自从没有锁语义，保护仅需要对抗在该 cpu 上执行的代码*不*从其他的 cpu 上访问.
	 */
	if (unlikely(!this_cpu_cmpxchg_double(
			s->cpu_slab->freelist, s->cpu_slab->tid,
			object, tid,
			next_object, next_tid(tid)))) {

		note_cmpxchg_failure("slab_alloc", s, tid);
		goto redo;
	}

最后对于直接从 cpu_slab 上分配的对象会通过 prefetch_freepointer() 调用 prefetchw 指令提前将已分配对象的地址载入缓存中，之后就是返回分配成功的空闲对象

1
2
3
4
5
6
		prefetch_freepointer(s, next_object);
		stat(s, ALLOC_FASTPATH);
	}

	return object;
}

II. ___slab_alloc()：获取另一 slab 进行分配（slow path）

__slab_alloc() 其实是在开启了抢占的情况下（默认开启）对 ___slab_alloc() 的一个简单的 wrapper，主要就是重新读取 kmem_cache_cpu 的指针：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * 当抢占没有关闭时 ___slab_alloc() 用于上下文的 wrapper.
 * 通过重新获取 percpu 区域的指针来补偿可能的 cpu 更改.
 */
static void *__slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
			  unsigned long addr, struct kmem_cache_cpu *c, unsigned int orig_size)
{
	void *p;

#ifdef CONFIG_PREEMPT_COUNT
	/*
	 * 我们可能已被抢占且在关闭抢占前调度到了不同的 cpu 上.
	 * 需要重新载入 cpu 区域指针.
	 */
	c = slub_get_cpu_ptr(s->cpu_slab);
#endif

	p = ___slab_alloc(s, gfpflags, node, addr, c, orig_size);
#ifdef CONFIG_PREEMPT_COUNT
	slub_put_cpu_ptr(s->cpu_slab);
#endif
	return p;
}

接下来我们来看 ___slab_alloc()，该函数便是慢速分配路径的核心函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * 慢速路径. 无锁 freelist 为空或是我们需要进行调试任务.
 *
 * 若新的对象已经被释放到常规的 freelist 上，则过程仍是很快的.
 * 这种情况下我们简单地让常规的 freelist 取代无锁 freelist
 * 并 zap the regular freelist.（zap想不出咋翻译好😄）
 *
 * 若这不起作用，则我们回退到 partial 链表. 我们将 freelist 上的第一个元素
 * 作为要分配的对象并将 freelist 的剩余部分移动到无锁 freelist.
 *
 * 若我们无法从 partial slab 链表上获得一个新的 slab，我们需要分配一个新的 slab.
 * 因为这包含对页分配器的调用与新 slab 的设置，这是最慢的路径.
 *
 * 当我们知道抢占被禁用时所用的 __slab_alloc 的版本 (也是造成大量分配的原因).
 */
static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
			  unsigned long addr, struct kmem_cache_cpu *c, unsigned int orig_size)
{
	void *freelist;
	struct slab *slab;
	unsigned long flags;
	struct partial_context pc;

	stat(s, ALLOC_SLOWPATH);

接下来笔者按照代码标签顺序进行分析

① reread_slab：读取 percpu slab

首先读取 percpu 的 slab，若没有 slab 则判断分配节点，并跳转到 new_slab 分配新的 slab，注意这一块代码对应 reread_slab 标签：

1
2
3
4
5
6
7
8
9
10
11
12
reread_slab:

	slab = READ_ONCE(c->slab);
	if (!slab) {
		/*
		 * 若 node 未上线或没有 normal memory，忽略 node 约束
		 */
		if (unlikely(node != NUMA_NO_NODE &&
			     !node_isset(node, slab_nodes)))
			node = NUMA_NO_NODE;
		goto new_slab;
	}

② redo：获取 percpu slab->freelist

接下来这块代码对应 redo 标签：

  • 若 percpu slab 不为空，判断 slab 是否属于指定的节点且与分配标志位匹配，若否，则跳转到 deactivate_slab 标签

  • 接下来检查 slab 是否仍为原来的 cpu slab（因为我们可能被抢占），若否，则跳转回 reread_slab

  • 接下来获取 per-cpu 的 freelist，若不为空，则跳转到 load_freelist，否则调用 get_freelist() 获取 slab 的 freelist

  • 若 slab 的 freelist 仍为空，将 per-cpu freelist 设为 NULL，获取下一个 tid，并跳转到 new_slab 分配新的 slab

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
30
31
32
33
34
35
36
37
38
39
40
41
42
redo:

	if (unlikely(!node_match(slab, node))) {
		/*
		 * 与上面相同但 node_match() 为 false 则早已说明 node != NUMA_NO_NODE
		 */
		if (!node_isset(node, slab_nodes)) {
			node = NUMA_NO_NODE;
		} else {
			stat(s, ALLOC_NODE_MISMATCH);
			goto deactivate_slab;
		}
	}

	/*
	 * 我们理应搜索一个 PFMEMALLOC 的 slab 页面，但现在，
	 * 当页面离开 per-cpu 分配器，我们正在失去 pfmemalloc 信息
	 */
	if (unlikely(!pfmemalloc_match(slab, gfpflags)))
		goto deactivate_slab;

	/* 必须再次检查 c->slab 以免我们被抢占使其发生了更改 */
	local_lock_irqsave(&s->cpu_slab->lock, flags);
	if (unlikely(slab != c->slab)) {
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);
		goto reread_slab;
	}
	freelist = c->freelist;
	if (freelist)
		goto load_freelist;

	freelist = get_freelist(s, slab);

	if (!freelist) {
		c->slab = NULL;
		c->tid = next_tid(c->tid);
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);
		stat(s, DEACTIVATE_BYPASS);
		goto new_slab;
	}

	stat(s, ALLOC_REFILL);

get_freelist() 函数主要就是获取 slab->freelist 后将 slab->freelist 设为 NULL 并返回原来的 freelist

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
30
31
32
33
34
/*
 * 检查 slab->freelist 并将 freelist 传送给 percpu freelist
 * 或是将 slab 给 deactivate.
 *
 * 若返回值非 NULL 则 slab 仍被冻结.
 *
 * 若该函数返回 NULL 则 slab 被解冻.
 */
static inline void *get_freelist(struct kmem_cache *s, struct slab *slab)
{
	struct slab new;
	unsigned long counters;
	void *freelist;

	lockdep_assert_held(this_cpu_ptr(&s->cpu_slab->lock));

	do {
		freelist = slab->freelist;
		counters = slab->counters;

		new.counters = counters;
		VM_BUG_ON(!new.frozen);

		new.inuse = slab->objects;
		new.frozen = freelist != NULL;

	} while (!__cmpxchg_double_slab(s, slab,
		freelist, counters,
		NULL, new.counters,
		"get_freelist"));

	return freelist;
}

③ load_freelist：从 freelist 分配对象

继续返回 ___slab_alloc() 中，接下来这块代码对应 load_freelist 标签，主要就是调用 get_freepointer() 将 percpu freelist 指向第二个空闲对象，并获取下一个 tid 后返回前面获取的 freelist（也就是第一个空闲对象）：

1
2
3
4
5
6
7
8
9
10
11
12
13
load_freelist:

	lockdep_assert_held(this_cpu_ptr(&s->cpu_slab->lock));

	/*
	 * freelist 指向要被使用的对象链表. slab 指向获得对象的 slab.
	 * 因此 slab 必须被冻结以让 percpu 的分配正常工作.
	 */
	VM_BUG_ON(!c->slab->frozen);
	c->freelist = get_freepointer(s, freelist);
	c->tid = next_tid(c->tid);
	local_unlock_irqrestore(&s->cpu_slab->lock, flags);
	return freelist;

这里注意在 get_freepointer() 里套了两层，最后会调用到 freelist_ptr() 获取到第二个空闲对象的指针，这里需要注意的是当开启了 Hardened freelist 保护后在 next 指针的位置存放的是 第一个空闲对象地址 ^ 第二个空闲对象地址 ^ 一个随机值（kmem_cache->random）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * 返回 freelist 指针 (ptr). 在有加固的情况下其通过一个
 * 对存储指针的地址与 per-cache 随机值的异或进行混淆.
 */
static inline void *freelist_ptr(const struct kmem_cache *s, void *ptr,
				 unsigned long ptr_addr)
{
#ifdef CONFIG_SLAB_FREELIST_HARDENED
	/*
	 * 当开启了 CONFIG_KASAN_SW/HW_TAGS, ptr_addr 可能被打上标签.
	 * 通常这不会造成任何问题，因为 set_freepointer() 与 get_freepointer() 
	 * 调用时都会有标签相同的指针.
	 * 但是 CONFIG_SLUB_DEBUG 的代码有些问题. 例如当 __free_slub() 在
	 * 一个 cache 中迭代对象时,其将没有标签的指针传给 check_object(). 
	 * check_object() 依次带着一个没有标签的指针调用 get_freepointer()，
	 * 从而造成 freepointer 存储错误.
	 */
	return (void *)((unsigned long)ptr ^ s->random ^
			swab((unsigned long)kasan_reset_tag((void *)ptr_addr)));
#else
	return ptr;
#endif
}

从这里我们也可以看出 slab->freelist 是没有加密的，但链表上的后续指针都是加密了的

④ deactivate_slab：deactivate percpu slab

继续返回 ___slab_alloc() 中，接下来这块代码对应 deactivate_slab 标签，首先还是惯例地检查是否被抢占调度到了别的 CPU，若是则跳转回 reread_slab；之后就是简单地将 percpu 的 slab 和 freelist 设为 NULL 并获取下一个 tid，之后调用 deactivate_slab() 将这张 slab 给 deactivate 了：

1
2
3
4
5
6
7
8
9
10
11
12
13
deactivate_slab:

	local_lock_irqsave(&s->cpu_slab->lock, flags);
	if (slab != c->slab) {
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);
		goto reread_slab;
	}
	freelist = c->freelist;
	c->slab = NULL;
	c->freelist = NULL;
	c->tid = next_tid(c->tid);
	local_unlock_irqrestore(&s->cpu_slab->lock, flags);
	deactivate_slab(s, slab, freelist);

deactivate_slab() 的逻辑如下：

  • 遍历 freelist 检查是否被破坏，放弃被破坏的部分
  • 将 slab->freelist 设为原 kmem_cache_cpu->freelist，若 slab 上原有 freelist 不为 NULL 则再接到后面
  • 设置 slab 的 counters，其中将 frozen 设为 0
  • 若 slab 上的对象全部空闲**且 node 的 partial slab 数量大于 kmem_cache->min_partial**，调用 discard_slab() 将 slab 释放
  • 若 slab 上存在空闲对象，调用 add_partial() 将其加入 node 的 partial 链表
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/*
 * 结束移除 cpu slab. 合并 cpu's freelist 与 slab's freelist,
 * 解冻 slabs 并放在合适的链表上.
 * 假设 slab 已经被调用者安全地从 kmem_cache_cpu 上取下.
 */
static void deactivate_slab(struct kmem_cache *s, struct slab *slab,
			    void *freelist)
{
	enum slab_modes { M_NONE, M_PARTIAL, M_FREE, M_FULL_NOLIST };
	struct kmem_cache_node *n = get_node(s, slab_nid(slab));
	int free_delta = 0;
	enum slab_modes mode = M_NONE;
	void *nextfree, *freelist_iter, *freelist_tail;
	int tail = DEACTIVATE_TO_HEAD;
	unsigned long flags = 0;
	struct slab new;
	struct slab old;

	if (slab->freelist) {
		stat(s, DEACTIVATE_REMOTE_FREES);
		tail = DEACTIVATE_TO_TAIL;
	}

	/*
	 * 阶段一: 统计 cpu's freelist 上的对象数量（free_delta） 
	 * 并保存最后一个对象（freelist_tail） 用于后面的拼接.
	 */
	freelist_tail = NULL;
	freelist_iter = freelist;
	while (freelist_iter) {
		nextfree = get_freepointer(s, freelist_iter);

		/*
		 * 若 'nextfree' 无效, 在 'freelist_iter' 上的对象可能已被破坏.
		 * 故通过略过 'freelist_iter' 起的所有对象来进行隔离.
		 */
		if (freelist_corrupted(s, slab, &freelist_iter, nextfree))
			break;

		freelist_tail = freelist_iter;
		free_delta++;

		freelist_iter = nextfree;
	}

	/*
	 * 阶段二: 解冻slab并将per-cpu freelist拼接到slab's freelist头部.
	 *
	 * 确保链表的存在反映了在解冻期间实际的对象数量时，slab 已被解冻.
	 *
	 * 我们首先在持有锁的情况下进行compxchg并当其成功时将 slab 插入链表.
	 * 若有不匹配的情况则 slab 为未冻结且 slab 上的数量可能发生了改变.
	 * 释放锁并再次重试 cmpxchg.
	 */
redo:

	old.freelist = READ_ONCE(slab->freelist);
	old.counters = READ_ONCE(slab->counters);
	VM_BUG_ON(!old.frozen);

	/* 确定 slab 的目标状态 */
	new.counters = old.counters;
	if (freelist_tail) {
		new.inuse -= free_delta;
		set_freepointer(s, freelist_tail, old.freelist);
		new.freelist = freelist;
	} else
		new.freelist = old.freelist;

	new.frozen = 0;

	if (!new.inuse && n->nr_partial >= s->min_partial) {
		mode = M_FREE;
	} else if (new.freelist) {
		mode = M_PARTIAL;
		/*
		 * 持有自旋锁消除了acquire_slab()看到一个slab为冻结的可能性
		 */
		spin_lock_irqsave(&n->list_lock, flags);
	} else {
		mode = M_FULL_NOLIST;
	}


	if (!cmpxchg_double_slab(s, slab,
				old.freelist, old.counters,
				new.freelist, new.counters,
				"unfreezing slab")) {
		if (mode == M_PARTIAL)
			spin_unlock_irqrestore(&n->list_lock, flags);
		goto redo;
	}


	if (mode == M_PARTIAL) {
		add_partial(n, slab, tail);
		spin_unlock_irqrestore(&n->list_lock, flags);
		stat(s, tail);
	} else if (mode == M_FREE) {
		stat(s, DEACTIVATE_EMPTY);
		discard_slab(s, slab);
		stat(s, FREE_SLAB);
	} else if (mode == M_FULL_NOLIST) {
		stat(s, DEACTIVATE_FULL);
	}
}

④ new_slab：获取 percpu partial slab

接下来是 new_slab 标签，主要就是检查若有 percpu partial slab 则从 percpu partial 链表上获取一个 slab 将其设为 percpu slab 后 再跳转回 redo 标签：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
new_slab:

	if (slub_percpu_partial(c)) {//有 percpu partial slab
		local_lock_irqsave(&s->cpu_slab->lock, flags);
		if (unlikely(c->slab)) {//percpu slab 不为空，直接跳回 redo
			local_unlock_irqrestore(&s->cpu_slab->lock, flags);
			goto reread_slab;
		}
		if (unlikely(!slub_percpu_partial(c))) {//被抢占然后partial空了
			local_unlock_irqrestore(&s->cpu_slab->lock, flags);
			/* 我们被抢占了且 partial 链表空了 */
			goto new_objects;
		}

		// 获取一张 percpu patial slab，跳回 redo
		slab = c->slab = slub_percpu_partial(c);
		slub_set_percpu_partial(c, slab);
		local_unlock_irqrestore(&s->cpu_slab->lock, flags);
		stat(s, CPU_PARTIAL_ALLOC);
		goto redo;
	}

⑤ new_objects：获取 node pertial slab 或向 buddy 请求新 slab 进行分配

若 percpu partial 链表也为空，那么便来到接下来的 new_objects 标签分配一个新的 slab，首先会设置 partial_context，调用 get_partial() 尝试从 kmem_cache_node 的 partial 链表分配一个 slab，若分配成功则直接跳转到 check_new_slab

1
2
3
4
5
6
7
8
9
new_objects:

	pc.flags = gfpflags;
	pc.slab = &slab;
	pc.orig_size = orig_size;
	freelist = get_partial(s, node, &pc);
	if (freelist)
		goto check_new_slab;

get_partial() 首先会调用 get_partial_node() 从当前 node 的 kmem_cache_node 的 partial 链表分配 slab，若成功了则直接返回，如果失败了但是指定了分配的 node 为 NUMA_NO_NODE，则调用 get_any_partial() 从其他的 kmem_cache_node 的 partial 链表尝试分配：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * 获取一个 partial slab, 加锁并返回.
 */
static void *get_partial(struct kmem_cache *s, int node, struct partial_context *pc)
{
	void *object;
	int searchnode = node;

	if (node == NUMA_NO_NODE)
		searchnode = numa_mem_id();

	// 从当前 node 的 partial 链表分配 slab
	object = get_partial_node(s, get_node(s, searchnode), pc);
	if (object || node != NUMA_NO_NODE)
		return object;

	// 从其他 node 的 partial 链表分配 slab
	return get_any_partial(s, pc);
}

若 get_partial() 没法获取到 slab，则调用 new_slab() 向 buddy system 请求一份新的 slab，若失败了则直接返回：

1
2
3
4
5
6
7
8
9
10
slub_put_cpu_ptr(s->cpu_slab);
slab = new_slab(s, gfpflags, node);
c = slub_get_cpu_ptr(s->cpu_slab);

if (unlikely(!slab)) {
	slab_out_of_memory(s, gfpflags, node);
	return NULL;
}

stat(s, ALLOC_SLAB);

new_slab() 最后会调用到 allocate_slab()：

  • 首先检查页面分配标志位，之后调用 alloc_slab_page() 在指定 node 上进行分配
    • 若 node == NUMA_NO_NODE，则该函数会调用 alloc_pages()，否则会调用 __alloc_pages_node()
  • 若失败了则再次调用 alloc_slab_page() 尝试进行最小内存分配（kmem_cache->min），仍失败则直接返回 NULL
  • 初始化 slab 各成员，并调用 shuffle_freelist() 为空闲对象构造随机化链表，若未开启随机化则将空闲对象按顺序连接
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
static struct slab *allocate_slab(struct kmem_cache *s, gfp_t flags, int node)
{
	struct slab *slab;
	struct kmem_cache_order_objects oo = s->oo;
	gfp_t alloc_gfp;
	void *start, *p, *next;
	int idx;
	bool shuffle;

	flags &= gfp_allowed_mask;

	flags |= s->allocflags;

	/*
	 * 让最初的 higher-order 分配在内存压力下失败
	 * 由此我们返回到最小 order 的分配.
	 */
	alloc_gfp = (flags | __GFP_NOWARN | __GFP_NORETRY) & ~__GFP_NOFAIL;
	if ((alloc_gfp & __GFP_DIRECT_RECLAIM) && oo_order(oo) > oo_order(s->min))
		alloc_gfp = (alloc_gfp | __GFP_NOMEMALLOC) & ~__GFP_RECLAIM;

	slab = alloc_slab_page(alloc_gfp, node, oo);
	if (unlikely(!slab)) {//分配失败，尝试最小内存分配
		oo = s->min;
		alloc_gfp = flags;
		/*
		 * 分配可能因为碎片化而失败.
		 * 可能的话尝试一个 lower order 的分配
		 */
		slab = alloc_slab_page(alloc_gfp, node, oo);
		if (unlikely(!slab))
			return NULL;
		stat(s, ORDER_FALLBACK);
	}

	slab->objects = oo_objects(oo);
	slab->inuse = 0;
	slab->frozen = 0;

	account_slab(slab, oo_order(oo), s, flags);

	slab->slab_cache = s;

	kasan_poison_slab(slab);

	start = slab_address(slab);

	setup_slab_debug(s, slab, start);

	//开启了随机化会在该函数内随机连接
	shuffle = shuffle_freelist(s, slab);

	//未开启随机化，按顺序连接
	if (!shuffle) {
		start = fixup_red_left(s, start);
		start = setup_object(s, start);
		slab->freelist = start;
		for (idx = 0, p = start; idx < slab->objects - 1; idx++) {
			next = p + s->size;
			next = setup_object(s, next);
			set_freepointer(s, p, next);
			p = next;
		}
		set_freepointer(s, p, NULL);
	}

	return slab;
}

这里用了一个函数 set_freepointer()，主要就是用 freelist_ptr() 向 object + s->offset 的位置写入用 freelist_ptr() 加密后的 fp 指针：

1
2
3
4
5
6
7
8
9
10
11
static inline void set_freepointer(struct kmem_cache *s, void *object, void *fp)
{
	unsigned long freeptr_addr = (unsigned long)object + s->offset;

#ifdef CONFIG_SLAB_FREELIST_HARDENED
	BUG_ON(object == fp); /* naive detection of double free or corruption */
#endif

	freeptr_addr = (unsigned long)kasan_reset_tag((void *)freeptr_addr);
	*(void **)freeptr_addr = freelist_ptr(s, fp, freeptr_addr);
}

返回 ___slab_alloc()，如果该 kmem_cache 设置了 SLAB_DEBUG_FLAGS 标志位，则接下来会调用 alloc_single_from_new_slab() 从新获取到的 slab 上分配一个对象后将 slab 重新挂回 partial/full 链表，若分配失败则跳转回 new_objects，成功则直接返回

1
2
3
4
5
6
7
8
9
10
11
if (kmem_cache_debug(s)) {
	freelist = alloc_single_from_new_slab(s, slab, orig_size);

	if (unlikely(!freelist))
		goto new_objects;

	if (s->flags & SLAB_STORE_USER)
		set_track(s, freelist, TRACK_ALLOC, addr);

	return freelist;
}

如果没有设置 SLAB_DEBUG_FLAGS 标志位，则接下来获取 slab 的 freelist，并调用 inc_slabs_node() 增加 node 上的计数

1
2
3
4
5
6
7
8
9
10
/*
 * No other reference to the slab yet so we can
 * muck around with it freely without cmpxchg
 */
freelist = slab->freelist;
slab->freelist = NULL;
slab->inuse = slab->objects;
slab->frozen = 1;

inc_slabs_node(s, slab_nid(slab), slab->objects);

⑥ check_new_slab：检查 slab

接下来对新获取的 slab 进行检查，若该 kmem_cache 设置了 SLAB_DEBUG_FLAGS 标志位，检查是否设置了 SLAB_STORE_USER 标志位，之后直接返回 freelist

接下来调用 pfmemalloc_match() 检查 slab 与分配标志位是否不匹配，若是则调用 deactivate_slab() 使其不再活动并返回 freelist

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
check_new_slab:

	if (kmem_cache_debug(s)) {
		/*
		 * For debug caches here we had to go through
		 * alloc_single_from_partial() so just store the tracking info
		 * and return the object
		 */
		if (s->flags & SLAB_STORE_USER)
			set_track(s, freelist, TRACK_ALLOC, addr);

		return freelist;
	}

	if (unlikely(!pfmemalloc_match(slab, gfpflags))) {
		/*
		 * For !pfmemalloc_match() case we don't load freelist so that
		 * we don't make further mismatched allocations easier.
		 */
		deactivate_slab(s, slab, get_freepointer(s, freelist));
		return freelist;
	}

⑦ retry_load_slab：

最后就是尝试加载新获得的 slab，如果 percpu slab 不为 NULL 则使其不再活动，并设置 percpu slab & freelist 为 NULL，并获取下一个 tid

最后就是将 percpu slab 设为新获取的 slab 并跳转回 load_freelist 分配对象并返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
retry_load_slab:

	local_lock_irqsave(&s->cpu_slab->lock, flags);
	if (unlikely(c->slab)) {
		void *flush_freelist = c->freelist;
		struct slab *flush_slab = c->slab;

		c->slab = NULL;
		c->freelist = NULL;
		c->tid = next_tid(c->tid);

		local_unlock_irqrestore(&s->cpu_slab->lock, flags);

		deactivate_slab(s, flush_slab, flush_freelist);

		stat(s, CPUSLAB_FLUSH);

		goto retry_load_slab;
	}
	c->slab = slab;

	goto load_freelist;
}

至此， slub 分配算法的核心逻辑分析结束

二、kmalloc： NUMA_NO_NODE 的通用上层分配接口

我们日常生活中（？）最常用的其实还是 kmalloc()，其会根据分配的大小与标志位帮我们完成 kmem_cache 的选取并进行对象分配

函数整体逻辑比较简单：

  • 若分配的大小在编译期已知（__builtin_constant_p()）则判断大小：
    • 若大小大于 KMALLOC_MAX_CACHE_SIZE 则使用 kmalloc_large() 进行分配
    • 通过 kmalloc_index() 与 kmalloc_type() 获取 kmalloc_caches 中对应的数组下标并调用 kmalloc_trace 进行对象分配
  • 若大小是动态传入的，调用 __kmalloc() 进行分配
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * kmalloc - 分配内核内存
 * @size: 需要的内存字节数.
 * @flags: 描述分配上下文
 *
 * kmalloc 是内核中分配小于页面大小的内存对象的通用方法.
 *
 * 被分配的对象地址至少要对齐到 ARCH_KMALLOC_MINALIGN 字节.
 * 对于 2^n 字节的 @size , 对齐也需要保证至少到该大小.
 *
 * @flags argument 可能是 include/linux/gfp.h 中定义的GFP 标志位，描述于
 * :ref:`Documentation/core-api/mm-api.rst <mm-api-gfp-flags>`
 *
 * 推荐的对 @flags 使用描述于
 * :ref:`Documentation/core-api/memory-allocation.rst <memory_allocation>`
 *
 * 以下为最常用的 GFP 标志位简要概述
 *
 * %GFP_KERNEL
 *	分配普通内核内存. 可能睡眠.
 *
 * %GFP_NOWAIT
 *	分配将不会睡眠.
 *
 * %GFP_ATOMIC
 *	分配将不会睡眠.  可能使用 emergency pools.
 *
 * 也可以通过异或以下的一个或多个额外@flags来设置不同的标志位:
 *
 * %__GFP_ZERO
 *	在返回前清零分配的内存. 也可参见 kzalloc().
 *
 * %__GFP_HIGH
 *	这个分配有着高优先级且可能使用 emergency pools.
 *
 * %__GFP_NOFAIL
 *	表示此次分配不允许失败
 *	(在使用前再次思考).
 *
 * %__GFP_NORETRY
 *	若内存不会马上可用,立即放弃.
 *
 * %__GFP_NOWARN
 *	若分配失败，不要提交警告.
 *
 * %__GFP_RETRY_MAYFAIL
 *	努力尝试使分配成功，但最终失败.
 */
#ifndef CONFIG_SLOB
static __always_inline __alloc_size(1) void *kmalloc(size_t size, gfp_t flags)
{
	if (__builtin_constant_p(size) && size) {
		unsigned int index;

		if (size > KMALLOC_MAX_CACHE_SIZE)
			return kmalloc_large(size, flags);

		index = kmalloc_index(size);
		return kmalloc_trace(
				kmalloc_caches[kmalloc_type(flags)][index],
				flags, size);
	}
	return __kmalloc(size, flags);
}

I. kmalloc_large()：直接向 buddy system 请求内存

对于请求大小大于 KMALLOC_MAX_CACHE_SIZE 的内存分配请求而言， kmalloc() 会直接调用 kmalloc_large() 完成内存分配，最后实际上会在 __kmalloc_large_node() 调用 alloc_pages() 向 buddy system 请求内存：

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
30
31
32
33
34
35
36
37
38
39
/*
 * 为了避免不必要的开销,我们将大的分配请求直接传递给页面分配器.
 * 我们使用 __GFP_COMP, 因为我们需要知道分配的 order 以在 kfree 中恰当地释放.
 */

static void *__kmalloc_large_node(size_t size, gfp_t flags, int node)
{
	struct page *page;
	void *ptr = NULL;
	unsigned int order = get_order(size);

	if (unlikely(flags & GFP_SLAB_BUG_MASK))
		flags = kmalloc_fix_flags(flags);

	flags |= __GFP_COMP;
	page = alloc_pages_node(node, flags, order);
	if (page) {
		ptr = page_address(page);
		mod_lruvec_page_state(page, NR_SLAB_UNRECLAIMABLE_B,
				      PAGE_SIZE << order);
	}

	ptr = kasan_kmalloc_large(ptr, size, flags);
	/* As ptr might get tagged, call kmemleak hook after KASAN. */
	kmemleak_alloc(ptr, size, 1, flags);
	kmsan_kmalloc_large(ptr, size, flags);

	return ptr;
}

void *kmalloc_large(size_t size, gfp_t flags)
{
	void *ret = __kmalloc_large_node(size, flags, NUMA_NO_NODE);

	trace_kmalloc(_RET_IP_, ret, size, PAGE_SIZE << get_order(size),
		      flags, NUMA_NO_NODE);
	return ret;
}
EXPORT_SYMBOL(kmalloc_large);

II. __kmalloc_index()：获取size对应下标

kmalloc_index() 其实就是 __kmalloc_index（），根据请求的大小返回对应的下标，整体逻辑非常简单粗暴：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
 * 算出一个特定大小的分配属于哪个 kmalloc slab .
 * 0 = zero alloc
 * 1 =  65 .. 96 bytes
 * 2 = 129 .. 192 bytes
 * n = 2^(n-1)+1 .. 2^n
 *
 * 注意: __kmalloc_index() 在编译期优化, 没有运行时优化;
 * 典型的用法为通过 kmalloc_index() 以在编译期优化.
 * 大小非常量的调用者仅应当为__kmalloc_index()的运行时开销可以被接受的测试模块.
 * 同样参见 kmalloc_slab().
 */
static __always_inline unsigned int __kmalloc_index(size_t size,
						    bool size_is_constant)
{
	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 (!IS_ENABLED(CONFIG_PROFILE_ALL_BRANCHES) && size_is_constant)
		BUILD_BUG_ON_MSG(1, "unexpected size in kmalloc_index()");
	else
		BUG();

	/* Will never be reached. Needed because the compiler may complain */
	return -1;
}

III. kmalloc_types()：获取标志位对应类型

kmalloc_type() 其实主要就是根据标志位返回类型，除了指定了 __GFP_DMA/__GFP_RECLAIMABLE/__GFP_ACCOUNT 以外就都是 KMALLOC_NORMAL：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static __always_inline enum kmalloc_cache_type kmalloc_type(gfp_t flags)
{
	/*
	 * 最常规的情况为 KMALLOC_NORMAL, 所以用一个单独的分支测试所有相关的标志位.
	 */
	if (likely((flags & KMALLOC_NOT_NORMAL_BITS) == 0))
		return KMALLOC_NORMAL;

	/*
	 * 至少需要设置一种标志位. 优先顺序为:
	 *  1) __GFP_DMA
	 *  2) __GFP_RECLAIMABLE
	 *  3) __GFP_ACCOUNT
	 */
	if (IS_ENABLED(CONFIG_ZONE_DMA) && (flags & __GFP_DMA))
		return KMALLOC_DMA;
	if (!IS_ENABLED(CONFIG_MEMCG_KMEM) || (flags & __GFP_RECLAIMABLE))
		return KMALLOC_RECLAIM;
	else
		return KMALLOC_CGROUP;
}

IV. kmalloc_trace()：常规大小的 NUMA_NO_NODE 对象分配

kmalloc_trace() 主要是对 __kmem_cache_alloc_node() 的 wrapper，加上 tracepoint 和 kasan 的相关设置，需要注意的是这里会指定 node 为 NUMA_NO_NODE：

不知道什么是 kernel trace point 的可以参见 这里

1
2
3
4
5
6
7
8
9
10
11
void *kmalloc_trace(struct kmem_cache *s, gfp_t gfpflags, size_t size)
{
	void *ret = __kmem_cache_alloc_node(s, gfpflags, NUMA_NO_NODE,
					    size, _RET_IP_);

	trace_kmalloc(_RET_IP_, ret, size, s->size, gfpflags, NUMA_NO_NODE);

	ret = kasan_kmalloc(s, ret, size, gfpflags);
	return ret;
}
EXPORT_SYMBOL(kmalloc_trace);

__kmem_cache_alloc_node() 其实就是 slab_alloc_node() 的 wrapper：

1
2
3
4
5
6
7
void *__kmem_cache_alloc_node(struct kmem_cache *s, gfp_t gfpflags,
			      int node, size_t orig_size,
			      unsigned long caller)
{
	return slab_alloc_node(s, NULL, gfpflags, node,
			       caller, orig_size);
}

V. __kmalloc()：常规大小的 NUMA_NO_NODE 对象分配

__kmalloc() 其实就是指定 node 为 NUMA_NO_NODE 的 __do_kmalloc_node() ：

1
2
3
4
5
void *__kmalloc(size_t size, gfp_t flags)
{
	return __do_kmalloc_node(size, flags, NUMA_NO_NODE, _RET_IP_);
}
EXPORT_SYMBOL(__kmalloc);

VI. __do_kmalloc_node()：判断所需 kmem_cache 并进行对象分配

该函数的主要逻辑为：

  • 若 size > KMALLOC_MAX_CACHE_SIZE ，则调用 __kmalloc_large_node() 进行分配，并进行 tracepoint 与 kasan 相关设置
  • 对于常规 size：
    • 首先调用 kmalloc_slab() 获取对应的 kmem_cache
    • 接下来调用 __kmem_cache_alloc_node() 进行内存分配
    • 最后进行 tracepoint 与 kasan 相关设置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static __always_inline
void *__do_kmalloc_node(size_t size, gfp_t flags, int node, unsigned long caller)
{
	struct kmem_cache *s;
	void *ret;

	if (unlikely(size > KMALLOC_MAX_CACHE_SIZE)) {
		ret = __kmalloc_large_node(size, flags, node);
		trace_kmalloc(caller, ret, size,
			      PAGE_SIZE << get_order(size), flags, node);
		return ret;
	}

	s = kmalloc_slab(size, flags);

	if (unlikely(ZERO_OR_NULL_PTR(s)))
		return s;

	ret = __kmem_cache_alloc_node(s, flags, node, size, caller);
	ret = kasan_kmalloc(s, ret, size, flags);
	trace_kmalloc(caller, ret, size, s->size, flags, node);
	return ret;
}

kmalloc_slab() 中寻找 kmem_cache 的过程和 kmalloc 类似，不过寻找下标用的是 size_index[size_index_elem(size)] 和 fls() ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
 * 寻找满足给定大小的分配的 kmem_cache 结构体
 */
struct kmem_cache *kmalloc_slab(size_t size, gfp_t flags)
{
	unsigned int 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];
}

size_index 和 size_index_elem() 的定义都非常简单粗暴：

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
30
31
32
33
34
35
36
37
/*
 * Conversion table for small slabs sizes / 8 to the index in the
 * kmalloc array. This is necessary for slabs < 192 since we have non power
 * of two cache sizes there. The size of larger slabs can be determined using
 * fls.
 */
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 inline unsigned int size_index_elem(unsigned int bytes)
{
	return (bytes - 1) / 8;
}

三、上层调用接口关系图

因为很多比如说 __kmem_cache_alloc_lru() 一类的函数其实最后都是对 slab_alloc_node() 的套娃，这里笔者直接给出一个简易的调用关系图：

只截取了笔者认为比较主要的那些，因为作图作到后面实在蚌埠住了

image.png

0x03. 对象的释放

※ 一、do_slab_free()：向指定的 kmem_cache 释放对象（链）

在 slab allocator 中存在着多个不同的内存释放接口，其最后都会调用到 do_slab_free() 完成内存释放的工作，需要注意的是该函数 允许释放已经连接成一条 freelist 且已经加密好的多个对象 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * 强制内联快速路径以创造无需额外的函数调用便能完成快速路径释放的kfree&kmem_cache_free.
 *
 * 快速路径仅在我们要释放会当前 cpu slab 时生效.
 * 这通常是在我们刚刚分配了该对象的情况.
 *
 * 若快速路径不可用则退回 __slab_free 以处理所有种类的特殊处理.
 *
 * 通过指定 head & tail 指针 加上对象数量（cnt），可以大量释放包含多个对象的freelist.
 * Bulk free indicated by tail pointer being set.
 */
static __always_inline void do_slab_free(struct kmem_cache *s,
				struct slab *slab, void *head, void *tail,
				int cnt, unsigned long addr)
{
	void *tail_obj = tail ? : head;
	struct kmem_cache_cpu *c;
	unsigned long tid;
	void **freelist;

与分配类似，释放同样分为快速路径与慢速路径

I. 直接释放回 percpu slab（fast path）

快速路径比较简单，主要就是对比待释放对象所属 slab 是否为 percpu slab，若是则直接挂回去即可，遵循 LIFO 机制：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
redo:
	/*
	 * 确定当前的 per cpu slab. 
	 * cpu 可能在之后改变.但由于数据已经通过该指针获得，这并没问题.
	 * 若我们在 cmpxchg 期间在同一 cpu 上，释放将会成功.
	 */
	c = raw_cpu_ptr(s->cpu_slab);
	tid = READ_ONCE(c->tid);

	/* 与 slab_alloc_node() 中在 barrier() 上的注释一样 */
	barrier();

	// 不属于 percpu slab，调用 __slab_free() 进行释放
	if (unlikely(slab != c->slab)) {
		__slab_free(s, slab, head, tail_obj, cnt, addr);
		return;
	}

	if (USE_LOCKLESS_FAST_PATH()) {
		freelist = READ_ONCE(c->freelist);

		// 直接将 percpu freelist 接到 tail_obj 后面
		set_freepointer(s, tail_obj, freelist);

		if (unlikely(!this_cpu_cmpxchg_double(
				s->cpu_slab->freelist, s->cpu_slab->tid,
				freelist, tid,
				head, next_tid(tid)))) {

			note_cmpxchg_failure("slab_free", s, tid);
			goto redo;
		}
	} else {
		/* Update the free list under the local lock */
		local_lock(&s->cpu_slab->lock);
		c = this_cpu_ptr(s->cpu_slab);
		if (unlikely(slab != c->slab)) {
			local_unlock(&s->cpu_slab->lock);
			goto redo;
		}
		tid = c->tid;
		freelist = c->freelist;

		// 直接将 percpu freelist 接到 tail_obj 后面
		set_freepointer(s, tail_obj, freelist);
		c->freelist = head;
		c->tid = next_tid(tid);

		local_unlock(&s->cpu_slab->lock);
	}
	stat(s, FREE_FASTPATH);
}

II. __slab_free()：释放回对应的 slab（slow path）

如果待释放对象不属于 percpu clab，则调用 __slab_free() 进行释放：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * 处理慢速路径. 这可能会被频繁调用因为在大部分情况下对象比cpu slab生命周期更长
 *
 * 所以我们仍尝试减少缓存行的使用率. 拿取 slab lock 并释放对象即可.
 * 若不需要额外的 partial slab handling 我们便可立即返回.
 */
static void __slab_free(struct kmem_cache *s, struct slab *slab,
			void *head, void *tail, int cnt,
			unsigned long addr)

{
	void *prior;
	int was_frozen;
	struct slab new;
	unsigned long counters;
	struct kmem_cache_node *n = NULL;
	unsigned long flags;

	stat(s, FREE_SLOWPATH);

首先还是 kfence 和 debug 相关，如果该 kmem_cache 设置了 SLAB_DEBUG_FLAGS 标志位则直接调用 free_to_partial_list() 后返回即可：

1
2
3
4
5
6
7
if (kfence_free(head))
	return;

if (IS_ENABLED(CONFIG_SLUB_TINY) || kmem_cache_debug(s)) {
	free_to_partial_list(s, slab, head, tail, cnt, addr);
	return;
}

之后是一个 do while 循环，首先会将 待释放 freelist 所属 slab 的 freelist 连接到 待释放 freelist 的 tail object 后边，这里的 new 是一个栈上的临时 slab 结构体：

1
2
3
4
5
6
7
8
9
10
11
do {
	if (unlikely(n)) {
		spin_unlock_irqrestore(&n->list_lock, flags);
		n = NULL;
	}
	prior = slab->freelist;
	counters = slab->counters;
	set_freepointer(s, tail, prior);
	new.counters = counters;
	was_frozen = new.frozen;
	new.inuse -= cnt;

接下来检查是否 (所有的对象都*将*为空闲对象 || 原 slab 上无空闲对象) && slab 未被冻结 ，若满足该条件则：

  • 检查是否有 percpu partial slab 且原 slab 上无空闲对象（即 slab->freelist（也就是代码中的 prior）为 NULL）：
    • 若是，则设置 slab 将被冻结（new.frozen=1）
    • 若否，则获取 slab 所对应的 kmem_cache_node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
if ((!new.inuse || !prior) && !was_frozen) {

	if (kmem_cache_has_cpu_partial(s) && !prior) {

		/*
		 * Slab 之前不在链表上且将会部分为空
		 * 我们可以推迟链表移动，而是反之将其冻结.
		 */
		new.frozen = 1;

	} else { /* 需要从一个链表上取下 */

		n = get_node(s, slab_nid(slab));
		/*
		 * 推测性地获取 list_lock.
		 * 若 cmpxchg 未成功，则我们可能
		 * 在不进行任何处理的情况下放弃 list_lock.
		 *
		 * 否则 list_lock 将与其他处理器同步更新 slabs 链表
		 */
		spin_lock_irqsave(&n->list_lock, flags);

	}
}

循环的终止条件用了一个 cmpxchg_double_slab() 函数，套娃套得👴头昏眼花，主要逻辑为：

  • 对比 slab->freelist == prior && slab->counters == counters，若是，则将 slab->freelist 设为 head 且将 slab->counters 设为 new.counters，该操作成功则返回 true，条件不符则返回 false

成功了循环将会直接跳出：）

1
2
3
4
} while (!cmpxchg_double_slab(s, slab,
	prior, counters,
	head, new.counters,
	"__slab_free"));

接下来检查该 slab 是否需要从一个 kmem_cache_node 的链表上取下，若否，则：

  • 若 slab 已经被冻结，stat() 一下（基本上等于啥都不做）
  • 若 slab 需要被冻结 （new.frozen 为 true），调用 put_cpu_partial() 直接将 slab 放到 percpu partial 链表
  • 释放工作完成，返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if (likely(!n)) {

	if (likely(was_frozen)) {
		/*
		 * 链表锁未被占用，因此不需要活跃任何链表.
		 */
		stat(s, FREE_FROZEN);
	} else if (new.frozen) {
		/*
		 * If we just froze the slab then put it onto the
		 * per cpu partial list.
		 */
		put_cpu_partial(s, slab, 1);
		stat(s, CPU_PARTIAL_FREE);
	}

	return;
}

如果 slab 上所有对象都被释放，且 node 上的 partial slab 数量已经超过 kmem_cache->min_partial ，这意味着这是一张完全空闲的 slab，接下来跳转到 slab_empty 标签，该标签对应代码块主要是：

  • 若 slab 上原来有空闲对象（位于 node partial 链表），则从 partial 链表移除
  • 若 slab 上原来无空闲对象（位于 node full 链表），则从 full 链表移除
  • 最后调用 discard_slab() 释放这一张 slab
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
	if (unlikely(!new.inuse && n->nr_partial >= s->min_partial))
		goto slab_empty;

	//...

slab_empty:
	if (prior) {
		/*
		 * Slab on the partial list.
		 */
		remove_partial(n, slab);
		stat(s, FREE_REMOVE_PARTIAL);
	} else {
		/* Slab must be on the full list */
		remove_full(s, n, slab);
	}

	spin_unlock_irqrestore(&n->list_lock, flags);
	stat(s, FREE_SLAB);
	discard_slab(s, slab);
}

若不满足上面的条件，则检查是否没有 percpu partial slab 且 slab 上原 freelist 为 NULL（即位于 node full 链表），若是则从 full 链表移除并添加到 node partial 链表

1
2
3
4
5
6
7
8
9
10
11
/*
 * Objects left in the slab. If it was not on the partial list before
 * then add it.
 */
if (!kmem_cache_has_cpu_partial(s) && unlikely(!prior)) {
	remove_full(s, n, slab);
	add_partial(n, slab, DEACTIVATE_TO_TAIL);
	stat(s, FREE_ADD_PARTIAL);
}
spin_unlock_irqrestore(&n->list_lock, flags);
return;

至此， slub 算法的释放逻辑分析完毕

二、kfree：通用的上层释放接口

正如同 kmalloc() 是最为通用的内核对象分配函数，与之相对应的释放函数便是 kfree() 了，这个函数其实主要就是 __kmem_cache_free() 的 wrapper，对于较大的对象则会用 free_large_kmalloc() 进行释放，如果 object 为 NULL 则直接返回：

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
30
/**
 * kfree - 释放之前分配的对象
 * @object: kmalloc 返回的指针.
 *
 * 若 @object 为 NULL, 则不会进行任何操作.
 *
 * 不要释放不由 kmalloc() 分配的内存，否则会出问题.
 */
void kfree(const void *object)
{
	struct folio *folio;
	struct slab *slab;
	struct kmem_cache *s;

	trace_kfree(_RET_IP_, object);

	if (unlikely(ZERO_OR_NULL_PTR(object)))
		return;

	folio = virt_to_folio(object);
	if (unlikely(!folio_test_slab(folio))) {
		free_large_kmalloc(folio, (void *)object);
		return;
	}

	slab = folio_slab(folio);
	s = slab->slab_cache;
	__kmem_cache_free(s, (void *)object, _RET_IP_);
}
EXPORT_SYMBOL(kfree);

I. folio 结构：一段物理、虚拟、逻辑上都连续的内存

注意到这里用了一个名为 folio 的结构体，其表示了一块物理、虚拟、逻辑上都连续的内存， 其实本质上还是复用了 page 结构体，只不过这一次是将 page 转为 folio ，定义比较长这里就不贴代码了

virt_to_folio() 首先会用 virt_to_page() 找到待释放对象虚拟地址对应的 page 结构体，之后用 page_folio() 将其转换为 folio 结构体——其实就是对于复合页而言会找到第一张页面，由此如果是复合页的话那说明是大 slab 所以会调用 free_large_kmalloc()，不是复合页说明是小 slab 所以会调用 __kmem_cache_free()：

1
2
3
4
5
6
7
8
9
10
11
12
static inline struct folio *virt_to_folio(const void *x)
{
	struct page *page = virt_to_page(x);

	return page_folio(page);
}

//...

#define page_folio(p)		(_Generic((p),				\
	const struct page *:	(const struct folio *)_compound_head(p), \
	struct page *:		(struct folio *)_compound_head(p)))

然后 folio_test_slab() 其实是 include/linux/page-flags.h 里的拼接宏，这里就不深入展开了：

1
2
static __always_inline bool folio_test_##lname(struct folio *folio)	\
{ return test_bit(PG_##lname, folio_flags(folio, FOLIO_##policy)); }	\

II. free_large_kmalloc()：直接将页面释放回 buddy system

正如对于大对象的分配 kmalloc_large() 会直接从 buddy system 请求内存一般，相对应的 free_large_kmalloc() 也会直接将页面释放回 buddy system：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void free_large_kmalloc(struct folio *folio, void *object)
{
	unsigned int order = folio_order(folio);

	if (WARN_ON_ONCE(order == 0))
		pr_warn_once("object pointer: 0x%p\n", object);

	kmemleak_free(object);
	kasan_kfree_large(object);
	kmsan_kfree_large(object);

	mod_lruvec_page_state(folio_page(folio, 0), NR_SLAB_UNRECLAIMABLE_B,
			      -(PAGE_SIZE << order));
	__free_pages(folio_page(folio, 0), order);
}

III. __kmem_cache_free()：常规的释放函数

__kmem_cache_free() 主要就是对 slab_free() 的 wrapper，不过会指定 tail 为 NULL：

1
2
3
4
void __kmem_cache_free(struct kmem_cache *s, void *x, unsigned long caller)
{
	slab_free(s, virt_to_slab(x), x, NULL, &x, 1, caller);
}

而 slab_free() 则会最终调用到 do_slab_free()：

1
2
3
4
5
6
7
8
9
10
11
12
static __fastpath_inline void slab_free(struct kmem_cache *s, struct slab *slab,
				      void *head, void *tail, void **p, int cnt,
				      unsigned long addr)
{
	memcg_slab_free_hook(s, slab, p, cnt);
	/*
	 * With KASAN enabled slab_free_freelist_hook modifies the freelist
	 * to remove objects, whose reuse must be delayed.
	 */
	if (slab_free_freelist_hook(s, &head, &tail, &cnt))
		do_slab_free(s, slab, head, tail, cnt, addr);
}

这里用到了一个函数 slab_free_freelist_hook()，主要的作用是遍历待释放的 freelist：

  • 如果设置了 free hook（ slab_free_hook() == true ），则仅减少计数以推迟释放
  • 否则重新建立一遍 freelist 后返回
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

static inline bool slab_free_freelist_hook(struct kmem_cache *s,
					   void **head, void **tail,
					   int *cnt)
{

	void *object;
	void *next = *head;
	void *old_tail = *tail ? *tail : *head;

	if (is_kfence_address(next)) {
		slab_free_hook(s, next, false);
		return true;
	}

	/* Head and tail of the reconstructed freelist */
	*head = NULL;
	*tail = NULL;

	do {
		object = next;
		next = get_freepointer(s, object);

		/* If object's reuse doesn't have to be delayed */
		if (!slab_free_hook(s, object, slab_want_init_on_free(s))) {
			/* Move object to the new freelist */
			set_freepointer(s, object, *head);
			*head = object;
			if (!*tail)
				*tail = object;
		} else {
			/*
			 * Adjust the reconstructed freelist depth
			 * accordingly if object's reuse is delayed.
			 */
			--(*cnt);
		}
	} while (object != old_tail);

	if (*head == *tail)
		*tail = NULL;

	return *head != NULL;
}

三、上层调用接口关系图

涉及到内存释放的函数相较于内存分配其实少很多，常用的主要就是 kfree()、kfree_sensitive()、kmem_cache_free() 这三大函数：

image.png

OS
#Linux #Linux Kernel #操作系统 #内存管理 #slub allocator
【OS.0x04】Linux 内核内存管理浅析 III - Slub Allocator
https://arttnba3.github.io/2023/02/24/OS-0X04-LINUX-KERNEL-MEMORY-6.2-PART-III/
作者
arttnba3
发布于
2023年2月24日
许可协议