Pwn进你的心
0%

BuddySystem&Slub

Posted on Edited on In 14k 12 mins.

伙伴系统

伙伴关系

伙伴关系的定义为：由一个母实体分成的两个各方面属性一致的两个子实体，这两个子实体就处于伙伴关系

  • 在操作系统分配内存的过程中，一个内存块经常被分成两个大小相等的内存块，这两个大小相等的内存块就处于伙伴关系
  • 它满足3个条件：
    • 两个块具有相同大小
    • 物理地址是连续的
    • 从同一个大块中拆分出来

伙伴系统

伙伴系统（buddy system）是内核中用来管理物理内存的一种算法，Linux2.6 为每个管理区使用不同的伙伴系统，内核空间分为三种区，DMA，NORMAL，HIGHMEM，对于每一种区，都有对应的伙伴算法

  • 我们知道内存中有一些是被内核代码占用，还有一些是被特殊用途所保留，那么剩余的空闲内存都会交给内核内存管理系统来进行统一管理和分配
  • 内核中会把内存按照页来组织分配，随着进程的对内存的申请和释放，系统的内存会不断的区域碎片化
  • 到最后会发现，明明系统还有很多空闲内存，却无法分配出一块连续的内存，这对于系统来说并不是好事

伙伴系统（buddy system）把系统中要管理的物理内存按照页面个数分为了 11 个组，分别对应11种大小不同的连续内存块，每组中的内存块大小都相等，且必须是 2 的 n 次幂 (Pow(2, n))，即 1, 2, 4, 8, 16, 32, 64, 128 … 1024 

1
2
3
4
5
6
7
8
9
10
11
/* include\linux\mmzone.h */
    
#define MAX_ORDER 11
    
struct zone {
	struct free_area	free_area[MAX_ORDER]; /* 不同大小的空闲区域 */
}
struct free_area {
	struct list_head	free_list[MIGRATE_TYPES]; /* 内存块链表连接时只需把内存块的第一个页关联即可(都是连续的) */
	unsigned long		nr_free; /* 表示这种内存块(包括所有迁移类型)的数量 */
};
  • 那么系统中就存在 2^0~2^10 这么11种大小不同的内存块，对应内存块大小为 4KB ~ 4M 内核用 11 个链表来管理 11 种大小不同的内存块

伙伴分配器的数据结构在逻辑上的表示就像是一个完全二叉树，大概像这样：

  • 当然实际编码过程中并不会使用一个 struct TreeNode 的形式去把二叉树的各个节点用指针连起来，因为是这个树一定是完全二叉树，所以可以使用一个数组来表示树的结构
  • 用这一个数组，就可以表示所有节点的位置信息

当一个页面被等分时，它自己也就不存在了：

位图管理

为了便于页面的维护，将多个页面组成内存块，每个内存块都有 “2的方幂” 个页，方幂的指数被称为阶

在操作内存时，经常将这些内存块分成大小相等的两个块，分成的两个内存块被称为伙伴块，采用 “一位二进制数” 来表示它们的伙伴关系

系统根据该位为 “0” 或位为 “1” 来决定是否使用或者分配该页面块，系统每次分配和回收伙伴块时都要对它们的伙伴位跟 “1” 进行异或运算

  • 刚开始时，父块还没有等分，所以伙伴块不存在（也可以认为是：两个伙伴块都空闲），它们的伙伴位为 “0”
  • 如果需要等分，则把第一块插入下一级，第二块分配出去，异或后得 “1”（只使用了一个块）
  • 如果另一块也被使用，异或后得 “0”（两个块都使用了）
  • 如果前面一块回收了异或后得 “1”
  • 如果另一块也回收了异或后得 “0”

整理一下便是：

  • 当这个位为 “1”，表示其中一块在使用
  • 当这个位为 “0”，表示两个页面块都在使用（一个完整的块不会分为两个空块）

注意：这个 “一位二进制数” 存储在 “位图 map” 中

空闲内存块管理

下图可以展示 free_area 的整体结构：

  • free_area 就是一个数组，存放有许多 free_list
  • 每个 free_list（free_area[x]）都有一个 map 位图（用于表示各个伙伴块的关系）
1
2
3
struct list_head {
	struct list_head *next, *prev;
};

下图就是一个 free_list（free_area[x]）的结构：

  • free_list（free_area[x]）用于链接 “2的n次方” 组成的内存块
  • map 中的一个“二进制位”表示两个伙伴块的关系

重要结构体

  • 页（page）：一个 page 结构表示一个物理内存页面
  • 区（zone）：因为硬件限制，Linux 内核不能把所有的物理内存页统一对待，把属性相同的物理内存页面归结到了一个区中
  • 节点（pglist_data）：pglist_data 结构中包含了 zonelist 数组，第一个 zonelist 类型的元素指向本节点内的 zone 数组，第二个 zonelist 类型的元素指向其它节点的 zone 数组，而一个 zone 结构中的 free_area 数组中又挂载着 page 结构

伙伴算法-分配流程

我先从 free_area 的角度继续分析，假如系统需要 4(2x2) 个页面大小的内存块：

  • 该算法首先到 free_area[2] 中查找：
    • 如果链表中有空闲块：就直接从中摘下并分配出去
    • 如果没有：算法将顺着数组向上查找 free_area[3]
      • 如果 free_area[3] 中有空闲块：则将其从链表中摘下，分成等大小的两部分，前 4 个页面作为一个块插入 free_area[2] 的链表头部，后 4 个页面分配出去
      • 如果 free_area[3] 中也没有：就再向上查找 free_area[4]
        • 如果 free_area[4] 中有：就将这 16(2x2x2x2) 个页面等分成两份，前一半的 8 个页挂 free_area[3] 的链表头部，后一半的 8 个页再次等分为 2 个 4 页，前一半挂 free_area[2] 的链表中，后一半分配出去
        • 假如 free_area[4] 也没有：则重复上面的过程，知道到达 free_area 数组的最后，如果还没有则放弃分配
  • free_area 中只存放空闲块，从空闲块的视角来看的话：
    • 从小到大进行查找，优先分配小块
    • 如果没有小块，就等分大块，前半部分插入下一级链表头部，后半部分进行分配
    • 如果后半部分仍然可以等分，就重复进行“等分插链”的操作

伙伴算法-释放流程

内存的释放是分配的逆过程，也可以看作是伙伴的合并过程

  • 当释放一个块时，先在其对应的链表中考查是否有伙伴存在
    • 如果没有伙伴块：就直接把要释放的块挂入链表头
    • 如果有：则从链表中摘下伙伴，合并成一个大块，然后继续考察合并后的块在更大一级链表中是否有伙伴存在，直到不能合并或者已经合并到了最大的块

PS：整个过程中，位图扮演了重要的角色，位图的某一位对应两个互为伙伴的块

  • 为“1”表示其中一块已经分配出去了，为“0”表示两块都都分配出去了
  • 伙伴中无论是分配还是释放都只是相对的位图进行异或操作，释放过程根据位图判断伙伴是否存在
    • 如果对相应位的异或操作得“1”（原本是“0”），代表没有伙伴可以合并
    • 如果异或操作得“0”（原本是“1”），代表伙伴块中的另一个已经空闲，可以进行合并
    • 并且继续按这种方式合并伙伴，直到不能合并为止

Slab分配器

slab的出现

我们知道内核中的物理内存由伙伴系统（buddy system）进行管理，它的分配粒度是以物理页帧（page）为单位的，但内核中有大量的数据结构只需要若干 bytes 的空间，倘若仍按页来分配，势必会造成大量的内存被浪费掉

slab 分配器的出现（而 slub 是 slab 的衍生产物），就是为了解决内核中这些小块内存分配与管理的难题

slab 分配器，把常用的数据结构都看成一个个对象

  • 我们知道 buddy 分配器的分配单元是以页为单位的，然后将不同 order 的空闲物理页帧串成若干链表，分配时从对应链表里取出
  • 而 slab 分配器则是以目标数据结构为单分配单元，且会将目标数据结构提前分配并串成链表，分配时从中取用

从 2.6 内核开始对 slab 分配器的实现添加了两个备选方案 slub 和 slob（用 slub 比较多）

  • slub 就是在之前 slab 上优化后的一个产物，去除了许多臃肿的实现，逐渐会完全替代老的 slab
  • 而 slob 则是一个很轻量级的 slab 实现，代码量不大，官方说适合一些嵌入式设备

重要结构体

这里有个复杂且重要的结构体：struct kmem_cache，即 缓存描述符（缓存器），准确的来说它并不包含实际的缓存空间，而是包含了一些缓存的管理数据，和指向实际缓存空间的指针

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
/* \linux-4.19.26\include\linux\slab_def.h */
struct kmem_cache {
	struct array_cache __percpu *cpu_cache; /* 本地高速缓存,每CPU结构对象释放时,优先放入这个本地CPU高速缓存中 */

/* 1) Cache tunables. Protected by slab_mutex */
	unsigned int batchcount; 
	unsigned int limit; /* 本地高速缓存中entry数组中空闲obj的最大数目 */
	unsigned int shared; /* CPU共享高速缓存标志,实际地址保存在kmem_cache_node结构中 */
	unsigned int size; /* 对象长度+填充字节 */
	struct reciprocal_value reciprocal_buffer_size;
    
/* 2) touched by every alloc & free from the backend */
	slab_flags_t flags; /* 属性的flag标志,如果SLAB管理结构放在外部,则CFLAGS_OFF_SLAB置'1' */
	unsigned int num; /* 每个slab中obj数量 */

/* 3) cache_grow/shrink */
	unsigned int gfporder; /* 每个slab页块的阶(一个slab由2^gfporder个页构) */
	gfp_t allocflags; /* 从伙伴系统分配页,补足slab时,页分配的gfp码 */
	size_t colour; /* 缓存着色范围 */
	unsigned int colour_off; /* 一个cache colour的长度(和一个cache line的大小相同) */
    
	struct kmem_cache *freelist_cache; /* 空闲对象链表放在slab外部时使用,管理用于slab对象管理结构中freelist成员的缓存,也就是又一个新缓存 */
	unsigned int freelist_size; /* 空闲对象链表的大小 */
	void (*ctor)(void *obj); /* 创建高速缓存时的构造函数指针,一半为null */

/* 4) cache creation/removal */
	const char *name; /* slab缓存名字 */
	struct list_head list; /* slab缓存描述符双向链表指针 */
	int refcount;
	int object_size; /* slab中每个obj的大小 */
	int align; /* obj对齐字节 */

/* 5) statistics */
#ifdef CONFIG_DEBUG_SLAB
	unsigned long num_active;
	unsigned long num_allocations;
	unsigned long high_mark;
	unsigned long grown;
	unsigned long reaped;
	unsigned long errors;
	unsigned long max_freeable;
	unsigned long node_allocs;
	unsigned long node_frees;
	unsigned long node_overflow;
	atomic_t allochit;
	atomic_t allocmiss;
	atomic_t freehit;
	atomic_t freemiss;
#ifdef CONFIG_DEBUG_SLAB_LEAK
	atomic_t store_user_clean;
#endif
	int obj_offset;
#endif /* CONFIG_DEBUG_SLAB */

#ifdef CONFIG_MEMCG
	struct memcg_cache_params memcg_params;
#endif
#ifdef CONFIG_KASAN
	struct kasan_cache kasan_info;
#endif

#ifdef CONFIG_SLAB_FREELIST_RANDOM
	unsigned int *random_seq;
#endif

	unsigned int useroffset;	/* Usercopy region offset */
	unsigned int usersize;		/* Usercopy region size */

	struct kmem_cache_node *node[MAX_NUMNODES]; /* slab节点链表组,对于NUMA系统中每个节点都会有一个struct kmem_cache_node数据结构 */
};
  • slab cache 中所有 slab 的大小一致，由一个或多个连续页组成（通常为一个page，伙伴系统提供）
  • 每个 slab 中的 obj 大小和数量也是相同的

slab cache 描述符 struct kmem_cache 中除了相关的管理数据外，有两个很重要的成员：

  • struct array_cache __percpu *cpu_cache：
    • cpu_cache 是一个 Per-CPU 数据结构，每个 CPU 独享（相当于函数和它局部变量的关系），用来表示本地 CPU 的 slab cache 对象缓冲池（注意是 slab cache obj 缓冲池不是 slab cache slab 缓冲池）
    • CPU 都有自己的硬件高速缓存，当前 CPU 上释放对象时，这个对象很可能还在 CPU 的硬件高速缓存中，这时使用这个对象的代价是非常小的，不需要重新装载到硬件高速缓存中，离 CPU 又最近，同时还可以减少锁的竞争，尤其是在多个 CPU 同时申请同样 size 或者同个缓存对象时，无需加锁即可操作
    • array_cache中 的 entry 空数组，就是用于保存本地 cpu 刚释放的 obj，所以该数组初始化时为空，只有本地 cpu 释放 slab cache 的 obj 后才会将此 obj 装入到 entry 数组 array_cache 的 entry 成员数组中保存的 obj 数量是由成员 limit 控制的，超过该限制后会将 entry 数组中的 batchcount 个 obj 迁移到对应节点 cpu 共享的空闲对象链表中
    • entry 数组的访问机制是 LIFO（last in fist out），此种设计非常巧妙，能保证本地 cpu 最近释放该 slab cache 的 obj 立马被下一个 slab 内存申请者获取到（有很大概率此 obj 仍然在本地 cpu 的硬件高速缓存中）
  • struct kmem_cache_node *node[MAX_NUMNODES]：
    • slab 缓存会为不同的节点维护一个自己的 slab 链表，用来缓存和管理自己节点的 slab obj，这通过 kmem_cache 中 node 数组成员来实现，node 数组中的每个数组项都为其对应的节点分配了一个 struct kmem_cache_node 结构
    • struct kmem_cache_node 结构定义的变量是一个每 node 变量，相比于 struct array_cache 定义的每 cpu 变量，kmem_cache_node 管理的内存区域粒度更大，因为kmem_cache_node 维护的对象是 slab，而 array_cache 维护的对象是 slab 中的 obj（一个 kmem_cache 可能包含一个或多个 slab，而一个 slab 中可能包含一个或多个 slab obj）
    • 通过下面 struct kmem_cache_node 结构的代码实现我们来分析该结构体如何实现对本地节点指定 slab cache 中所有的 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
struct kmem_cache_node {
	spinlock_t list_lock;

#ifdef CONFIG_SLAB
	struct list_head slabs_partial;	/* 该链表中存储的所有slab中只有部分obj是空闲的 */
	struct list_head slabs_full; /* 该链表中存储的所有slab中不存在空闲的obj */
	struct list_head slabs_free; /* 该链表中存储的所有slab中每个obj都是空闲的 */
	unsigned long total_slabs; /* 该节点中此kmem_cache的slab总数 */
	unsigned long free_slabs; /* 该节点中此kmem_cache空闲slab总数 */
	unsigned long free_objects; /* 该节点中此kmem_cache空闲obj总数 */
	unsigned int free_limit; /* 该节点中此kmem_cache中空闲obj数量的上限,多了就会回收到伙伴系统的空闲链表中 */
	unsigned int colour_next; /* Per-node cache coloring */
	struct array_cache *shared;	/* 该节点上所有cpu共享的本地高速缓存 */
	struct alien_cache **alien;	/* 其他节点上所有cpu共享的本地高速缓存 */
	unsigned long next_reap; /* updated without locking */
	int free_touched; /* updated without locking */
#endif

#ifdef CONFIG_SLUB
	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

};
  • 由上代码可以看出，struct kmem_cache_node 对于本节点中 slab 的管理主要分了3个链表:
    • 部分空闲 slab 链表（slabs_partial）
    • 全空闲 slab 链表（slabs_free）
    • 非空闲 slab 链表（slabs_full）
  • 单个 slab 可以在不同的链表之间移动，例如当一个 slab 被分配完，就会从 slab_partial 移动到 slabs_full，当一个 slab 中有对象被释放后，就会从 slab_full 再次回到 slab_partial，所有对象都被释放完的话，就会从 slab_partial 移动到 slabs_free
  • struct kmem_cache_node 还会将本地节点中需要节点共享的 slab obj 缓存在它的 shared 成员中，若本地节点向访问其他节点贡献的 slab obj，可以利用 struct kmem_cache_node 中的 alien 成员去获取

slab机制

slab 算法在伙伴算法的基础上，对小内存的场景专门做了优化，采用了内存池的方案，解决内部碎片问题

先挂一张图片：

从 buddy 分配出来的那一份份连续的 page 就是一个 slab

  • 首先我们要知道是 slab 分配器是基于 buddy 分配器的，即 slab 需要从 buddy 分配器获取连续的物理页帧作为制造对象的原材料
  • 简单来说，就是基于 buddy 分配器获得连续的 pages，作为某数据结构对象的缓存，再将这段连续的 pages 从内部切割成一个个对齐的对象，使用时从中取用，这样一段连续的 page 我们称为一个 slab

把各个 slab 分组管理，每一个组对应一个 kmem_cache，对应一种分配“规则”

  • 在 slab 算法中维护着大小不同的 slab 集合，在最顶层是 cache_chain，cache_chain 中维护着一组 kmem_cache 引用
  • kmem_cache 负责管理一块固定大小的对象池，通常会提前分配一块内存，然后将这块内存划分为大小相同的 object（分配给用户的对象），不会对内存块再进行合并，同时使用位图 bitmap 记录每个 object 的使用情况
  • 把各个 slab 进行分组管理，每个组分别包含 2^3，2^4，2^5 … 2^11 … 个字节（在 4K 页大小的默认情况下），另外还有两个特殊的组，分别是 96B 和 192B，每个组就是一个 kmem_cache
  • 不同内核版本的分组数不同（大约20个），比如我的内核就分配了26个组：
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
static __always_inline unsigned 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();

	return -1;
}
  • slab 分配器并非一开始就能智能的根据内存分档值分配相应长度的内存的，它需要先创建一个这样的“规则”式的东西，之后才可以根据这个“规则”分配相应长度的内存
  • 内核 slab 分配器之所以能够默认的提供26种内存长度分档，肯定也需要创建这样26个“规则”，这是由函数 kmem_cache_init 在初始化时创建的
  • 比如现在有一个内核模块想要申请一种它自创的结构，这个结构是111字节，并且它不想获取128字节内存就想获取111字节长度内存，那么它需要在 slab 分配器中创建一个这样的“规则”，这个规则规定 slab 分配器当按这种“规则”分配时要给我111字节的内存，这个“规则”的创建方法就是调用函数 kmem_cache_create
  • 函数 kmem_cache_destroy 可以销毁 kmem_cache_create 创建的“规则”，而这个“规则”就是“缓存描述符 kmem_cache”

slub接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 分配一块给某个数据结构使用的kmem_cache(缓存描述符) */
struct kmem_cache *kmem_cache_create( const char *name, size_t size, size_t align, unsigned long flags， void (*ctor)(void*));

/* 销毁kmem_cache_create分配的kmem_cache */
int kmem_cache_destroy(struct kmem_cache *cachep);

/* 从目标kmem_cache中分配一个object */  
void* kmem_cache_alloc(struct kmem_cache* cachep, gfp_t flags);

/* 释放object,把它返还给原先的kmem_cache */
void kmem_cache_free(struct kmem_cache* cachep,  void* objp);

/* 输入想要的size,分配一个object,其他工作交给伙伴系统和slub */
void *kmalloc(size_t size, int flags);

/* 输入目标obj,释放它,其他工作交给伙伴系统和slub */
void kfree(const void *objp)
  • 先通过 kmem_cache_create 创建一个缓存管理描述符 kmem_cache
  • 使用 kmem_cache_alloc 从缓存 kmem_cache 中申请 object 使用
  • 函数 kmem_cache_init 在初始化时会自动创建默认的 kmem_cache

kmalloc

kmalloc 本质上是调用 __kmalloc：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* linux-4.20.1\mm\slub.c */
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_); /* 从对应的kmem_cache中分配对象 */

	trace_kmalloc(_RET_IP_, ret, size, s->size, flags);

	kasan_kmalloc(s, ret, size, flags);

	return ret;
}
EXPORT_SYMBOL(__kmalloc);
  • kmalloc() 先根据 size 找到对应的 struct kmem_cache 然后调用 slab_alloc() 从中分配对象

slab_alloc：

1
2
3
4
5
6
/* linux-4.20.1\mm\slub.c */
static __always_inline void *slab_alloc(struct kmem_cache *s,
		gfp_t gfpflags, unsigned long addr)
{
	return slab_alloc_node(s, gfpflags, NUMA_NO_NODE, addr);
}
  • 然后在 slab_alloc() 中调用 slab_alloc_node

slab_alloc_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
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
static __always_inline void *slab_alloc_node(struct kmem_cache *s,
		gfp_t gfpflags, int node, unsigned long addr)
{
	void *object;
	struct kmem_cache_cpu *c;
	struct page *page;
	unsigned long tid;

	s = slab_pre_alloc_hook(s, gfpflags);
	if (!s)
		return NULL;
redo:
    /*
        必须通过本cpu指针去读kmem_cache中的cpu相关数据, 
        当读一个CPU区域内的数据时有可能在cpu直接来回切换
        只要我们在执行cmpxchg时再次使用原始 cpu，这并不重要

        必须保证tid和kmem_cache都是通过同一个CPU获取的
        如果开启了CONFIG_PREEMPT(内核抢占), 那么有可能获取tid之后被换出, 导致tid与c不对应, 所以这里需要一个检查
    */
	do {
		tid = this_cpu_read(s->cpu_slab->tid);
		c = raw_cpu_ptr(s->cpu_slab);
	} while (IS_ENABLED(CONFIG_PREEMPT) &&
		 unlikely(tid != READ_ONCE(c->tid)));

	barrier(); // 编译屏障, 防止指令乱序

	object = c->freelist; // 获取空闲链表中的对象
	page = c->page; // 正在被用来分配对象的页
	if (unlikely(!object || !node_match(page, node))) {
        /* 如果空闲链表为空或者page不属于要求的节点,那么就进入slowpath部分 */
		object = __slab_alloc(s, gfpflags, node, addr, c);
		stat(s, ALLOC_SLOWPATH);
	} else {
        /* 否则进入fastpath,通过CPU缓存中的freelist进行分配 */
		void *next_object = get_freepointer_safe(s, object);

        /*这里要执行链表的取出操作, this_cpu_cmpxchg_double()作用为:
        如果s->cpu_slab->freelist==object, 那么s->cpu_slab->freelist=next_object
        如果s->cpu_slab->tid==tid, 那么s->cpu_slab->tid=next_tid(tid), next_tid(tid)
        如果执行到一半s->cpu_slab被其他slub拿去使用, 那么compare失败, 不执行写入, 返回redo重新试一下
        */
		if (unlikely(!this_cpu_cmpxchg_double(
				s->cpu_slab->freelist, s->cpu_slab->tid,
				object, tid,
				next_object, next_tid(tid)))) { // next_tid(tid)相当于tid+1

			note_cmpxchg_failure("slab_alloc", s, tid);
			goto redo;
		}
		prefetch_freepointer(s, next_object); // 把预读进缓存
		stat(s, ALLOC_FASTPATH); // 记录状态
	}

	if (unlikely(gfpflags & __GFP_ZERO) && object) // 如果flag要求清0
		memset(object, 0, s->object_size);

	slab_post_alloc_hook(s, gfpflags, 1, &object); // 空操作

	return object;
}
  • 这里我们主要考虑 fastpath，也就是使用 freelist 的这种情况

get_freepointer_safe：

1
2
3
4
5
6
7
8
9
10
11
12
13
static inline void *get_freepointer_safe(struct kmem_cache *s, void *object)
{
	unsigned long freepointer_addr;
	void *p;

	if (!debug_pagealloc_enabled()) /* 如果没开启CONFIG_DEBUG_PAGEALLOC,那么就会进入get_freepointer() */
		return get_freepointer(s, object);
	
    /* 否则就会进行加密 */
	freepointer_addr = (unsigned long)object + s->offset;
	probe_kernel_read(&p, (void **)freepointer_addr, sizeof(p));
	return freelist_ptr(s, p, freepointer_addr);
}
  • 这就是 Harden_freelist 保护（使用 s->random 与 指针所在地址 去加密原空闲指针）
  • 加固指针 = 空闲指针 ^ 空闲指针地址 ^ 随机数R，只要知道这些值就可以绕过 Harden_freelist