【OS.0x03】Linux内核内存管理II - Buddy System

本文最后更新于：2023年10月27日 中午

HEY DUDE!

0x00.一切开始之前

在上一篇文章中笔者简要阐述了 Linux 内核当中内存的基本组织架构：页、区、节点，在本篇文章当中笔者将阐述内核中最基础的内存分配器——Buddy Systen（伙伴系统）

通过读取 /proc/buddyinfo 可以获取当前系统中 buddy system 的详细信息

image.png

笔者的💻配置比较🚮，所以只有一个 node，非常抱歉…

这篇文章其实很早就写了个框架了，但是后面一直没有来得及进行补完…（其实就是懒而已吧（恼））

image.png

0x01.buddy system 中的内存组织形式

zone 中的 free_area 结构体数组

前文中我们讲到，每个 zone 结构体中都有一个 free_area 结构体数组，用以存储 buddy system 按照 order 管理的页面

1
2
3
4
struct zone {
    //...
    struct free_area	free_area[MAX_ORDER];
    //...

其中的 MAX_ORDER 为一个常量，值为 11

在 buddy system 中按照空闲页面的连续大小进行分阶管理，这里的 order 的实际含义为连续的空闲页面的大小，不过单位不是页面数，而是阶，即对于每个下标而言，其中所存储的页面大小为：
$$
2^{order}
$$
在 free_area 中存放的页面通过自身的相应字段连接成双向链表结构，由此我们得到这样一张_Overview_：

自己画的图.png

下面我们来解析 free_area 的具体结构，该结构体定义如下：

1
2
3
4
struct free_area {
	struct list_head	free_list[MIGRATE_TYPES];
	unsigned long		nr_free;
};

free_list：空闲页面双向链表

我们不难看出：free_area 的 free_list 字段便是用以存放指向空闲页面的指针，其通过 page 结构体的 lru 字段将 page 结构体连接成双向链表

1
2
3
4
5
6
7
8
9
10
11
struct page {
    //...
    union {
		struct {	/* 页缓存与匿名页 */
			/**
			 * @lru: Pageout 链表, 例如 active_list 便由
			 * lruvec->lru_lock 保护。  
			 * 有时会被页所有者作为常规链表使用。
			 */
			struct list_head lru;
    //...

page 结构体中的 lru 这一字段的类型为 struct list_head，这是内核编程中通用的双向链表结构，free_list 与 lru 链表都使用该字段 将页结构体组织为_双向链表_，即_一个页是不可能同时出现在 lru 链表与 buddy system 中的_

迁移类型分链表

在这里我们注意到free_area 中并非只有一个双向链表，而是按照不同的“迁移类型”（migrate type）进行分开存放，这是由于_页面迁移_机制的存在

页面迁移主要用以解决内核空间中的碎片问题，在长期的运行之后内存当中空闲页面的分布可能是零散的，这便导致了内核有可能无法映射到足够大的连续内存，因此需要进行_页面迁移_——将旧的页面迁移到新的位置

从知乎偷的图.png

但并非所有的页面都是能够随意迁移的，因此我们在 buddy system 当中还需要将页面按照迁移类型进行分类

迁移类型由一个枚举类型定义，定义于 /include/linux/mmzone.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
enum migratetype {
	MIGRATE_UNMOVABLE,
	MIGRATE_MOVABLE,
	MIGRATE_RECLAIMABLE,
	MIGRATE_PCPTYPES,	/* the number of types on the pcp lists */
	MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
#ifdef CONFIG_CMA
	/*
	 * MIGRATE_CMA migration type is designed to mimic the way
	 * ZONE_MOVABLE works.  Only movable pages can be allocated
	 * from MIGRATE_CMA pageblocks and page allocator never
	 * implicitly change migration type of MIGRATE_CMA pageblock.
	 *
	 * The way to use it is to change migratetype of a range of
	 * pageblocks to MIGRATE_CMA which can be done by
	 * __free_pageblock_cma() function.  What is important though
	 * is that a range of pageblocks must be aligned to
	 * MAX_ORDER_NR_PAGES should biggest page be bigger then
	 * a single pageblock.
	 */
	MIGRATE_CMA,
#endif
#ifdef CONFIG_MEMORY_ISOLATION
	MIGRATE_ISOLATE,	/* can't allocate from here */
#endif
	MIGRATE_TYPES
};
  • MIGRATE_UNMOVABLE：这类型页面在内存当中有着固定的位置，不能移动
  • MIGRATE_MOVABLE：这类页面可以随意移动，例如用户空间的页面，我们只需要复制数据后改变页表映射即可
  • MIGRATE_RECLAIMABLE：这类页面不能直接移动，但是可以删除，例如映射自文件的页
  • MIGRATE_PCPTYPES：per_cpu_pageset，即每 CPU 页帧缓存，其迁移仅限于同一节点内
  • MIGRATE_CMA：Contiguous Memory Allocator，即连续的物理内存
  • MIGRATE_ISOLATE：不能从该链表分配页面，该链表用于跨 NUMA 节点进行页面移动，将页面移动到使用该页面最为频繁的 CPU 所处节点
  • MIGRATE_TYPES_：表示迁移类型的数目，_并不存在这一链表

以 free_list[0] 作为例子，我们可以得到如下 overview：

自己画的图.png

nr_free：空闲页面（块）计数

该字段记录了在当前 free_area 中的空闲页面块的数量，对于 free_area[0] 以外的 free_area 而言其单位并非是单个页框，而是以_内存块_为单位

0x02.页的分配

buddy system 提供了一组用以进行页面分配的接口，接下来笔者将以自底向上的方式进行源码分析

一、GFP（get free page）标志位

GFP标志位这一节基本上搬运自这篇文章

在 kernel memory allocation 中我们经常能见到 gfp_t 类型，其表示分配时的标志位，定义在 include/linux/gfp.h 中，大概有如下这些可用标志位：

  • 内存管理区修饰符 (zone modifiers)

内存管理区修饰符主要描述从哪些内存管理区来分配内存

flag description
__GFP_DMA 从ZONE_DMA区中分配内存
__GFP_HIGNMEM 从ZONE_HIGHMEM区中分配内存
__GFP_DMA32 从ZONE_DMA32区中分配内存
__GFP_MOVABLE 内存规整时可以迁移或回收页面
  • 移动和替换修饰符(mobility and placement modifiers)

移动和替换修饰符主要表示分配出来的页面具有的迁移属性

flag description
__GFP_RECLAIMABLE 分配的内存页面可以回收
__GFP_WRITE 申请的页面会被弄成脏页
__GFP_HARDWALL 强制使用cpuset内存分配策略
__GFP_THISNODE 在指定的节点上分配内存
__GFP_ACCOUNT kmemcg会记录分配过程
  • 水位修饰符 （watermark modifiers）

与水位线相关的标志位

flag description
__GFP_ATOMIC 高优先级分配内存，分配器可以分配最低警戒水位线下的预留内存
__GFP_HIGH 分配内存的过程中不可以睡眠或执行页面回收动作
__GFP_MEMALLOC 允许访问所有的内存
__GFP_NOMEMALLOC 不允许访问最低警戒水位线下的系统预留内存
  • 页面回收修饰符（reclaim modifiers)

与页面回收相关的标志位

flag description
__GFP_IO 启动物理I/O传输
__GFP_FS 允许调用底层FS文件系统。可避免分配器递归到可能已经持有锁的文件系统中， 避免死锁
__GFP_DIRECT_RECLAIM 分配内存过程中可以使用直接内存回收
__GFP_KSWAPD_RECLAIM 内存到达低水位时唤醒kswapd线程异步回收内存
__GFP_RECLAIM 表示是否可以直接内存回收或者使用kswapd线程进行回收
__GFP_RETRY_MAYFAIL 分配内存可以可能会失败，但是在申请过程中会回收一些不必要的内存，是整个系统受益
__GFP_NOFAIL 内存分配失败后无限制的重复尝试，知道分配成功
__GFP_NORETRY 直接页面回收或者内存规整后还是无法分配内存时，不启用retry反复尝试分配内存，直接返回NULL
  • 行为修饰符 (action modifiers)

与分配时的行为相关的标志位

flag description
__GFP_NOWARN 关闭内存分配过程中的WARNING
__GFP_COMP 分配的内存页面将被组合成复合页compound page
__GFP_ZERO 返回一个全部填充为0的页面
  • 组合类型标志(Useful GFP flag combinations)

前面描述的修饰符种过于繁多，因此linux定义了一些组合的类型标志，供开发者使用。

flag element description
GFP_ATOMIC __GFP_HIGH |__GFP_ATOMIC |__GFP_KSWAPD_RECLAIM 分配过程不能休眠，分配具有高优先级，可以访问系统预留内存
GFP_KERNEL __GFP_RECLAIM |__GFP_IO |__GFP_FS 分配内存时可以被阻塞(即休眠)
GFP_KERNEL_ACCOUNT GFP_KERNEL |__GFP_ACCOUNT 和GFP_KERNEL作用一样，但是分配的过程会被kmemcg记录
GFP_NOWAIT __GFP_KSWAPD_RECLAIM 分配过程中不允许因直接内存回收而导致停顿
GFP_NOIO __GFP_RECLAIM 不需要启动任何的I/O操作
GFP_NOFS __GFP_RECLAIM |__GFP_IO 不会有访问任何文件系统的操作
GFP_USER __GFP_RECLAIM |__GFP_IO |__GFP_FS |__GFP_HARDWALL 用户空间的进程分配内存
GFP_DMA __GFP_DMA 从ZONE_DMA区分配内存
GFP_DMA32 __GFP_DMA32 从ZONE_DMA32区分配内存
GFP_HIGHUSER GFP_USER | __GFP_HIGHMEM 用户进程分配内存，优先使用ZONE_HIGHMEM， 且这些页面不允许迁移
GFP_HIGHUSER_MOVABLE GFP_HIGHUSER | __GFP_MOVABLE 和GFP_HIGHUSER类似，但是页面可以迁移
GFP_TRANSHUGE_LIGHT GFP_HIGHUSER_MOVABLE | __GFP_COMP | __GFP_NOMEMALLOC | __GFP_NOWARN) & ~__GFP_RECLAIM 透明大页的内存分配， light表示不进行内存压缩和回收
GFP_TRANSHUGE GFP_TRANSHUGE_LIGHT | __GFP_DIRECT_RECLAIM 和GFP_TRANSHUGE_LIGHT类似，通常khugepaged使用该标志

二、alloc_context 结构体：分配的上下文

这是一个分配过程中非常重要的结构体，用来表示我们单次内存分配的上下文信息

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
/*
 * 用以保存在分配时涉及到的函数间传递的
 * 绝大部分的不可变的分配参数的结构体，
 * 包括 alloc_pages 函数族
 *
 * nodemask, migratetype 与 highest_zoneidx 仅在
 * __alloc_pages_nodemask() 中被初始化一次，之后不再改变.
 *
 * zonelist, preferred_zone 与 highest_zoneidx 最初在
 * __alloc_pages_nodemask() 中为快速路径设置, 之后可能会在
 * __alloc_pages_slowpath() 中被改变. 其他所有的函数通过
 * 常量指针传递该结构体。
 */
struct alloc_context {
	struct zonelist *zonelist;
	nodemask_t *nodemask;
	struct zoneref *preferred_zoneref;
	int migratetype;

	/*
	 * highest_zoneidx 表示分配请求中最高的可用 zone 的下标。
	 * 由于 zone 的性质, 相较于 highest_zoneidx，
	 * 在更低的 zone 上的内存会由 lowmem_reserve[highest_zoneidx] 保护。
	 * 译注：就是水位线机制，不记得的回去看上一篇文章
	 *
	 * highest_zoneidx 同样被回收/压缩使用以限制目标 zone，
	 * 因为高于该下标的 zone 无法用于此分配请求
	 */
	enum zone_type highest_zoneidx;
	bool spread_dirty_pages;
};

我们主要关注如下成员：

  • zonelist

该成员表示在这一次的分配上下文中，我们将要操作的 zone 的列表，其为一个 zonelist 类型的结构体数组，该结构体定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
 * 单次分配请求在一个 zonelist 上操作. 一个 zonelist 便是一组 zone 的列表，
 * 其中第一个 zone 为分配的“目标”，而其他的 zone 为后备的zone，优先级降低。
 *
 * 为了提高 zonelist 的读取速度, 在 zonerefs 中包含正在被读取的 entry 的 zone index。
 * 用来访问所给的 zoneref 结构体信息的帮助函数有：
 *
 * zonelist_zone()	- 返回一个 struct zone 的指针作为 _zonerefs 中的一个 entry
 * zonelist_zone_idx()	- 返回作为 entry 的 zone 的 index
 * zonelist_node_idx()	- 返回作为 entry 的 node 的 index
 */
struct zonelist {
	struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1];
};

可以看到的是其为一个 zoneref 类型的结构体数组，该结构体定义如下，包含了一个 zone 的指针以及一个 index：

1
2
3
4
5
6
7
8
/*
 * 该结构包含了 zonelist 中一个 zone 的信息。 
 * 其被储存在这里以预防对大结构体的解引用与对表的查询。
 */
struct zoneref {
	struct zone *zone;	/* 指向实际上的 zone 的指针 */
	int zone_idx;		/* zone_idx(zoneref->zone) */
};
  • preferred_zoneref

该成员为一个 zoneref 类型的结构体，表示优先用来进行分配的 zone

  • spread_dirty_pages

布尔值，表示此次分配是否可能产生脏页（需要进行写回），通常分配需要写入的页会出现

三、__alloc_pages_nodemask()：分配页面的「核心函数」，返回 page 结构体

该函数是 buddy system 中用以进行页面分配的核心函数，所有的页面分配 API 都是基于该函数的封装，其需要传入的四个参数为：

  • gfp_mask：分配行为参数（可以参见 这里）
  • order：分配的连续物理页框的阶
  • preferred_nid 选取的节点的 id
  • nodemask：

返回值为分配的连续物理页中的第一张物理页的 page 结构体

如果你已经不记得 page 结构体与物理页的页框号间的转换公式了，可以回去看上一篇文章

当然，笔者比较好心（笑），这里直接给出计算公式，mem_section 结构体中的 section_mem_map 成员存储了其起始地址减掉其起始地址对应的物理页框的页框号的差值，该成员与 page 结构体间做指针差值运算便能获得 page 结构体对应的物理页框号：
$$
address_{struct\ page} - section_mem_map = address_{struct\ page} - (address_{mem_map} - start_PFN)\
=(address_{struct\ page} - address_{mem_map}) + start_PFN
\
=PFN
$$

这是一张_Overview_

从知乎偷的.png

该函数定义于 /mm/page_alloc.c 中，如下：

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
/*
 * This is the 'heart' of the zoned buddy allocator.
 */
struct page *
__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, int preferred_nid,
							nodemask_t *nodemask)
{
	struct page *page;
	unsigned int alloc_flags = ALLOC_WMARK_LOW;
	gfp_t alloc_mask; /* 实际用于分配的 gfp_t ，这是一个int类型的整型*/
	struct alloc_context ac = { };

	/*
	 * 我们假定 order 的值在一些地方是正常的，
	 * 因此若请求超出范围则提前退出
	 */
	if (unlikely(order >= MAX_ORDER)) {
		WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
		return NULL;
	}

	gfp_mask &= gfp_allowed_mask;
	alloc_mask = gfp_mask;
	if (!prepare_alloc_pages(gfp_mask, order, preferred_nid, nodemask, &ac, &alloc_mask, &alloc_flags))
		return NULL;

	/*
	 * 直到所有的 local zone 都被考虑之前，
	 * 禁止从 falling back 到内存碎片种类的第一次传递
	 */
	alloc_flags |= alloc_flags_nofragment(ac.preferred_zoneref->zone, gfp_mask);

	/* 第一次分配尝试 */
	page = get_page_from_freelist(alloc_mask, order, alloc_flags, &ac);
	if (likely(page))
		goto out;

	/*
	 * 应用作用域分配约束 这主要与 GFP_NOFS 有关。
	 * GFP_NOIO 必须从一个特定的由 memalloc_no{fs,io}_{save,restore}
	 * 所标记的上下文中所有的分配请求中继承
	 */
	alloc_mask = current_gfp_context(gfp_mask);
	ac.spread_dirty_pages = false;

	/*
	 * 恢复最初的 nodemask （其可能被替换为 &cpuset_current_mems_allowed
	 * 以优化快速（分配）路径的尝试）
	 */
	ac.nodemask = nodemask;

	page = __alloc_pages_slowpath(alloc_mask, order, &ac);

out:
	if (memcg_kmem_enabled() && (gfp_mask & __GFP_ACCOUNT) && page &&
	    unlikely(__memcg_kmem_charge_page(page, gfp_mask, order) != 0)) {
		__free_pages(page, order);
		page = NULL;
	}

	trace_mm_page_alloc(page, order, alloc_mask, ac.migratetype);

	return page;
}
EXPORT_SYMBOL(__alloc_pages_nodemask);

这个函数的具体步骤主要分为三步：

  • 检查参数合法性，并做分配前准备工作
  • 进行快速分配，成功则直接返回结果
  • 若快速分配失败，则进行慢速分配

接下来我们来深入快速分配与慢速分配的内部细节

I. prepare_alloc_pages()：分配前的准备工作

这个函数比较简单，主要是做分配前的一些准备的工作，包括初始化 alloc_context 结构体、获取 zone 数组等：

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
static inline bool prepare_alloc_pages(gfp_t gfp_mask, unsigned int order,
		int preferred_nid, nodemask_t *nodemask,
		struct alloc_context *ac, gfp_t *alloc_mask,
		unsigned int *alloc_flags)
{
	ac->highest_zoneidx = gfp_zone(gfp_mask);
	ac->zonelist = node_zonelist(preferred_nid, gfp_mask); // 获取 zonelist
	ac->nodemask = nodemask;
	ac->migratetype = gfp_migratetype(gfp_mask);

    // 若开启了 cpuset（限制某一组进程只运行在某些cpu和内存节点上），则设置对应的标志位。
	if (cpusets_enabled()) {
		*alloc_mask |= __GFP_HARDWALL;
		/*
		 * 若我们在中断上下文中, 则这与当前进程上下文无关。
		 * 这意味着任一 node 都是 ok 的.
		 */
		if (!in_interrupt() && !ac->nodemask)
			ac->nodemask = &cpuset_current_mems_allowed;
		else
			*alloc_flags |= ALLOC_CPUSET;
	}

	fs_reclaim_acquire(gfp_mask);
	fs_reclaim_release(gfp_mask);

	might_sleep_if(gfp_mask & __GFP_DIRECT_RECLAIM);

	if (should_fail_alloc_page(gfp_mask, order))
		return false;

	*alloc_flags = current_alloc_flags(gfp_mask, *alloc_flags);

	/* Dirty zone 的平衡仅在 fast path 中完成 */
	ac->spread_dirty_pages = (gfp_mask & __GFP_WRITE);

	/*
	 * preferred zone 被用于进行数据统计， 但非常重要的是其页被用作
	 * zonelist 迭代器的起始点. 对于忽略内存策略的分配，其可能会被重置。
	 */
	ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
					ac->highest_zoneidx, ac->nodemask);

	return true;
}
  • 首先调用 node_zonelist() 从 preferred_nid 参数所指定的 node 中获取一个 zonelist，其实就是取 pglist_data->node_zonelists[gfp_zonelist(flags)]
  • 进行 cpuset 相关判断与标志位设置，若是在中断上下文则直接将 nodemask 设为 cpuset_current_mems_allowed
  • 最后调用 first_zones_zonelist() 设置 preferred zone，大概是在 zonelist 中→nodemask 所包含的 zone 中→ highest_zoneidx 以下的第一个 zone

反正源码注释是这么写的hhh

II. get_page_from_freelist()：快速分配路径（核心分配函数）

该函数定义于 /mm/page_alloc.c 中，主要是遍历分配上下文对应的 zonelist 中的 zone 进行内存分配，如下：

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
/*
 * get_page_from_freelist 遍历 zonelist 尝试分配页面
 */
static struct page *
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
						const struct alloc_context *ac)
{
	struct zoneref *z;
	struct zone *zone;
	struct pglist_data *last_pgdat_dirty_limit = NULL;
	bool no_fallback;

retry:
	/*
	 * 扫描 zonelist, 寻找有着足够空闲页面的 zone.
	 * 参见 __cpuset_node_allowed() 的注释（kernel/cpuset.c）
	 */
	no_fallback = alloc_flags & ALLOC_NOFRAGMENT; // 避免内存碎片的flag
	z = ac->preferred_zoneref; // 先尝试从 preferred zone 中分配
    // 这是一个封装宏，表示从 z 开始遍历 zonelist 中的 zoneref 数组，
    // 其核心是单次迭代调用 next_zones_zonelist()，该函数返回:
    // 		在 nodemask 的 zone 中，以当前 zone 作为起点游标的
    // 		【位于或低于】highest_zoneidx 的下一个 zone
	for_next_zone_zonelist_nodemask(zone, z, ac->highest_zoneidx,
					ac->nodemask) {
		struct page *page;
		unsigned long mark;

        // 开启了 cpuset 且 flag 中有 ALLOC_CPUSET 标志位，
        // 但是 cpuset 中不允许以该 gfp_mask 在该 zone 中分配，
        // 进行下一次迭代
		if (cpusets_enabled() &&
			(alloc_flags & ALLOC_CPUSET) &&
			!__cpuset_zone_allowed(zone, gfp_mask))
				continue;
		/*
		 * 在分配页缓存（page cache）页以进行写入时, 我们想要
		 * 在一个节点的“脏限制”（dirty limit）内获得他, 
         * 由此，没有一个节点有着超过全局允许的脏页比例。
		 * 脏限制考虑了节点的低端内存保留和高水位线，
		 * 以便于 kswapd 能平衡它，而不必从其 LRU 列表中写入页面。
		 *
		 * XXX: 现在, 在进入回收之前，
		 * 允许分配可能超过 慢速路径中 (spread_dirty_pages unset)
		 * 单节点的 dirty limit，这在一个允许节点们在一起都未够大以达到全局限制
         * 的 NUMA 设置中是很重要的。对于这些情况的合适的修补将需要对
		 * dirty-throttling 与 flusher threads 中节点的意识.
		 */
        // 译注：原文就是XXX，笔者也不知道这个XXX是什么...
        // 大概就是检查当前zone对应node的脏页数量是不是达到限制了
		if (ac->spread_dirty_pages) {
			if (last_pgdat_dirty_limit == zone->zone_pgdat)
				continue;

			if (!node_dirty_ok(zone->zone_pgdat)) {
				last_pgdat_dirty_limit = zone->zone_pgdat;
				continue;
			}
		}

        // node 数量大于1，且当前 zone 并非 preferred zone
		if (no_fallback && nr_online_nodes > 1 &&
		    zone != ac->preferred_zoneref->zone) {
			int local_nid;

			/*
			 * 若移动到了 remote node（译注：非当前node？）, 则重试，
			 * 但允许 fragmenting fallbacks. 局部性比避免碎片更加重要。
			 */
            // 比对当前 zone 是否在 local node（就是离当前CPU最近那个 node）
            // 若否，则去掉 ALLOC_NOFRAGMENT 标志位，并从 preferred zone 开始重试。
            // 即：kernel 更倾向于优先从 local zone 进行分配，哪怕会产生内存碎片
			local_nid = zone_to_nid(ac->preferred_zoneref->zone);
			if (zone_to_nid(zone) != local_nid) {
				alloc_flags &= ~ALLOC_NOFRAGMENT;
				goto retry;
			}
		}

        // 获取当前 zone 的水位线标记
		mark = wmark_pages(zone, alloc_flags & ALLOC_WMARK_MASK);
		if (!zone_watermark_fast(zone, order, mark,
				       ac->highest_zoneidx, alloc_flags,
				       gfp_mask)) { // 水位线相关操作
			int ret;

#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
			/*
			 * 该 zone 的水位线失败, 但若其包含了 deferred pages，
			 * 则我们会看该 zone 是否还能再进行扩展
			 */
			if (static_branch_unlikely(&deferred_pages)) {
				if (_deferred_grow_zone(zone, order))
					goto try_this_zone;
			}
#endif
			/* Checked here to keep the fast path fast */
			BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
            // 该标志位意为【不检查水位线】，此时我们直接尝试从该 zone 中分配
			if (alloc_flags & ALLOC_NO_WATERMARKS)
				goto try_this_zone;

			if (node_reclaim_mode == 0 ||
			    !zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
				continue;

            // 首先进行页面回收，之后查看是否满足水位线要求，若‘
            // 		不扫描/没有可回收/检查未通过
            // 则都会进行下一次迭代，尝试下一个 zone
			ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
			switch (ret) {
			case NODE_RECLAIM_NOSCAN:
				/* 不扫描 */
				continue;
			case NODE_RECLAIM_FULL:
				/* 扫描了但不可回收 */
				continue;
			default:
				/* 检查我们是否回收了足够页面 */
				if (zone_watermark_ok(zone, order, mark,
					ac->highest_zoneidx, alloc_flags))
					goto try_this_zone;

				continue;
			}
		}

try_this_zone:
        // 来到该 label 表示我们终于通过了前面一系列的各种检查，现在开始正式进行页面分配
        // **************************
        // rmqueue() 即为我们在OS教科书上看到的的 buddy system 模型,
        // 取 freelist 对应下标 page，若无则向上遍历拆更高 order 的 page
        // **************************
		page = rmqueue(ac->preferred_zoneref->zone, zone, order,
				gfp_mask, alloc_flags, ac->migratetype);
		if (page) {
			prep_new_page(page, order, gfp_mask, alloc_flags);

			/*
			 * 若这是一个高阶的原子分配，
			 * 检查我们是否该为将来保留 pageblock
			 */
			if (unlikely(order && (alloc_flags & ALLOC_HARDER)))
				reserve_highatomic_pageblock(page, zone, order);

			return page;	// 取到了，返回
		} else {	// 没取到
#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
			/* 若该 zone 有 deferred pages，再试一遍 */
			if (static_branch_unlikely(&deferred_pages)) {
				if (_deferred_grow_zone(zone, order))
					goto try_this_zone;
			}
#endif
		}
	}

	/*
	 * 在一台 UMA 机器上可能所以的 zone 都是破碎的，
	 * 若避免碎片, 重置并重试.
	 */
	if (no_fallback) {
		alloc_flags &= ~ALLOC_NOFRAGMENT;
		goto retry;
	}

	return NULL;
}

该函数流程总结如下：

  • for_next_zone_zonelist_nodemask 迭代遍历分配上下文中 zonelist 中的 zoneref 数组 对应的 zone

    其核心是单次迭代调用 next_zones_zonelist()，该函数返回:

    • 在 nodemask 的 zone 中，以当前 zone 作为起点游标的【位于或低于】highest_zoneidx 的下一个 zone

    • 若开启了 cpuset，检查当前 zone 是否满足 cpuset 的要求，若否，则尝试下一个 zone

    • 检查当前 zone 对应 node 的脏页数量是否超出限制，若否，则尝试下一个 zone

    • 若 ALLOC_NOFRAGMENT 但是当前 zone 非 preferred zone、且对应 node 为 remote node，则清除该标志位后重新开始分配，因为 locality 比避免碎片更加重要

    • 获取当前 zone 的水位线标记

      • 若是设置了 ALLOC_NO_WATERMARKS 则直接到下一步进行分配
      • 若水位线检查未通过，调用 node_reclaim() 进行页面回收
      • 若回收后页面还是不足，则尝试下一个 zone

    • 调用 rmqueue() 正式进行内存分配，该函数即为 buddy system 分配算法

偷的图.png

rmqueue()：从给定的 page 中进行页面分配

该函数定义于 /mm/page_alloc.c 中，主要是从给定 zone 中进行内存分配

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
/*
 * 从给定 zone 中进行内存分配. 对于 order-0 的分配则使用 pcplists.
 */
static inline
struct page *rmqueue(struct zone *preferred_zone,
			struct zone *zone, unsigned int order,
			gfp_t gfp_flags, unsigned int alloc_flags,
			int migratetype)
{
	unsigned long flags;
	struct page *page;

	if (likely(order == 0)) {
		/*
		 * MIGRATE_MOVABLE 的 pcplist 可能在 CMA 区域有着页面，
		 * 当从 CMA 的分配不被允许时我们需要略过它
		 */
        // 对于 order-0 的分配，
        // 若没有开启 CMA | 设置了 ALLOC_CMA | 迁移类型非 MIGRATE_MOVABLE
        // 则先从 pcplist 上分配
		if (!IS_ENABLED(CONFIG_CMA) || alloc_flags & ALLOC_CMA ||
				migratetype != MIGRATE_MOVABLE) {
			page = rmqueue_pcplist(preferred_zone, zone, gfp_flags,
					migratetype, alloc_flags);
			goto out;
		}
	}

	/*
	 * 我们绝不希望 callers 尝试
	 * 在带有 __GFP_NOFAIL 时分配大于 order-1 的页
	 */
	WARN_ON_ONCE((gfp_flags & __GFP_NOFAIL) && (order > 1));
	spin_lock_irqsave(&zone->lock, flags);

	do {
		page = NULL;
		/*
		 * 若由于非CMA的分配上下文导致略过了 pcplist，则order-0 的请求可以到达此处.
		 * HIGHATOMIC 区域为更高 order 的原子分配所保留，
		 * 故 order-0 的请求应略过它。
		 */
        // 若 order > 0 且带有 ALLOC_HARDER 标志位，调用 __rmqueue_smallest() 分配
        // 这个标志位意为将水位线减去 1/4，实际上 GFP_ATOMIC 中便会包含该标志位
		if (order > 0 && alloc_flags & ALLOC_HARDER) {
			page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
			if (page)
				trace_mm_page_alloc_zone_locked(page, order, migratetype);
		}
        // 调用 __rmqueue() 进行分配，这个就是真正的核心分配函数了
		if (!page)
			page = __rmqueue(zone, order, migratetype, alloc_flags);
	} while (page && check_new_pages(page, order)); // 这个检查函数通过了返回false
	spin_unlock(&zone->lock);
	if (!page)
		goto failed;
	__mod_zone_freepage_state(zone, -(1 << order),
				  get_pcppage_migratetype(page));

	__count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
	zone_statistics(preferred_zone, zone);
	local_irq_restore(flags);

out:
	/* Separate test+clear to avoid unnecessary atomics */
	if (test_bit(ZONE_BOOSTED_WATERMARK, &zone->flags)) {
		clear_bit(ZONE_BOOSTED_WATERMARK, &zone->flags);
		wakeup_kswapd(zone, 0, 0, zone_idx(zone));
	}

	VM_BUG_ON_PAGE(page && bad_range(zone, page), page);
	return page;

failed:
	local_irq_restore(flags);
	return NULL;
}

分析函数流程前我们先回顾一下这个概念——per-cpu pageset ，这是 zone 上的一个 per-cpu 的页面集，在分配时会优先从这里进行分配

该函数其实还是对分配的核心逻辑的封装，主要是以下流程：

  • 分配的 order 为 0，若没有开启 CMA | 设置了 ALLOC_CMA | 迁移类型非 MIGRATE_MOVABLE，则尝试从 per-cpu pageset 中分配并返回
  • order > 0，调用 __rmqueue_smallest() 进行页面分配
  • 之前未分配成功，调用 __rmqueue() 进行页面分配
  • 结果检查，其中循环内是用 check_new_pages()，未通过则重新循环（回到第二步）
① rmqueue_pcplist()：从 per-cpu pageset 上做 order-0 的分配

主要是关中断→页面分配→开中断三步走，最后分配调用到的是 __rmqueue_pcplist()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* Lock and remove page from the per-cpu list */
static struct page *rmqueue_pcplist(struct zone *preferred_zone,
			struct zone *zone, gfp_t gfp_flags,
			int migratetype, unsigned int alloc_flags)
{
	struct per_cpu_pages *pcp;
	struct list_head *list;
	struct page *page;
	unsigned long flags;

	local_irq_save(flags); // 关中断
	pcp = &this_cpu_ptr(zone->pageset)->pcp;
	list = &pcp->lists[migratetype]; // 获取迁移类型链表
	page = __rmqueue_pcplist(zone,  migratetype, alloc_flags, pcp, list); // 分配
	if (page) {
		__count_zid_vm_events(PGALLOC, page_zonenum(page), 1);
		zone_statistics(preferred_zone, zone);
	}
	local_irq_restore(flags); // 开中断
	return page;
}

__rmqueue_pcplist() 主要就是一个大循环，若 pcplist 为空则调用 rmqueue_bulk() 先从 zone 上拿 pages，之后就是简单的链表脱链，分配结果使用 check_new_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
/* 从 per-cpu 链表上取出 page, 调用者必须保护链表 */
static struct page *__rmqueue_pcplist(struct zone *zone, int migratetype,
			unsigned int alloc_flags,
			struct per_cpu_pages *pcp,
			struct list_head *list)
{
	struct page *page;

	do {
		if (list_empty(list)) { // list 是空的
            // 
			pcp->count += rmqueue_bulk(zone, 0,
					READ_ONCE(pcp->batch), list,
					migratetype, alloc_flags);
			if (unlikely(list_empty(list)))
				return NULL;
		}

        // 链表脱链
		page = list_first_entry(list, struct page, lru);
		list_del(&page->lru);
		pcp->count--;
	} while (check_new_pcp(page));

	return page;
}

rmqueue_bulk() 则最终会调用到 __rmqueue() 为 pcplist 进行 pcp->batch 次的 order-0 的页面分配，并建立链表

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
/*
 * 为了高效率，从 buddy 分配器获得指定数量的元素, 
 * 所有的单个元素都在持有锁的情况下进行.  将其添加到提供的链表中.
 * 返回放置在 *list 链表上的 pages 数量.
 */
static int rmqueue_bulk(struct zone *zone, unsigned int order,
			unsigned long count, struct list_head *list,
			int migratetype, unsigned int alloc_flags)
{
	int i, alloced = 0;

	spin_lock(&zone->lock);
	for (i = 0; i < count; ++i) {
		struct page *page = __rmqueue(zone, order, migratetype,
								alloc_flags);
		if (unlikely(page == NULL))
			break;

		if (unlikely(check_pcp_refill(page)))
			continue;

		/*
		 * 由 expand() 返回的分割 buddy 页面在此处以物理页框顺序接收。
		 * 页面被添加到 caller 的链表尾部。从 caller 的角度看，链表在
		 * 某些情况下是按照页码排序的。这对一些可以从头部前向的IO设备是有用的，
		 * 因为链表也是在物理页的顺序上的。这对于可以在物理页合理排序的情况下
		 * 合并IO请求的IO设备是有用的。
		 */
		list_add_tail(&page->lru, list);
		alloced++;
		if (is_migrate_cma(get_pcppage_migratetype(page)))
			__mod_zone_page_state(zone, NR_FREE_CMA_PAGES,
					      -(1 << order));
	}

	/*
	 * i pages were removed from the buddy list even if some leak due
	 * to check_pcp_refill failing so adjust NR_FREE_PAGES based
	 * on i. Do not confuse with 'alloced' which is the number of
	 * pages added to the pcp list.
	 */
	__mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
	spin_unlock(&zone->lock);
	return alloced;
}
② __rmqueue_smallest()：遍历指定 migrationtype 链表的 buddy 算法（核心中的核心）

我们重新来回顾一下 free_area 的结构，在其中根据迁移类型分成了多个链表：

自己画的图.png

而一个 zone 是由多个 free_area 组成的，一个 free_area 对应一个 order，那么对于该函数而言其只会遍历特定的 order，那么就成了下面的模型：

自己画的图.png

现在我们可以以来看这个函数了：从待分配 order 所对应的 free_area 的指定的 migration type 链表上分配，若不够则一直向更高 order 进行分配后对半向下拆到低 order，这里向更高 order 分配是通过简单的循环 + 链表脱链操作完成的，而拆高阶 page 的操作则是通过 expand() 完成的

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
/*
 * 对给定的 migrationtype 遍历 free lists 
 * 并从 freelists 上移除最小可用的页面
 */
static __always_inline
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
						int migratetype)
{
	unsigned int current_order;
	struct free_area *area;
	struct page *page;

	/* 在 preferred list 上寻找一个合适 size 的 page */
	for (current_order = order; current_order < MAX_ORDER; ++current_order) {
		area = &(zone->free_area[current_order]);
		page = get_page_from_free_area(area, migratetype);
		if (!page)
			continue;
		del_page_from_free_list(page, zone, current_order);
		expand(zone, page, order, current_order, migratetype);
		set_pcppage_migratetype(page, migratetype);
		return page;
	}

	return NULL;
}

expand() 的逻辑就比较简单，从高阶 order 一直循环到待分配的 order：

  • 首先高阶 order–，之后页面拆两半，把后半部分挂到链表上，前半部分留到下次循环继续拆
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
/*
 * 此处再分割的顺序对 IO subsystem 而言是十分重要的.
 * 请不要在有好的理由及回归测试前改变这个顺序。
 * 特别地，当大块的内存被分割，更小块（内存）被传递的顺序
 * 则由他们在该函数中被分割的顺序决定。
 * 根据实际测试，这是影响传递给IO子系统的 pages 顺序的主要因素，
 * 考虑到包含一个内存大块（由一系列小的分配作用）的 buddy system 的行为，
 * 这也是合理的。这种行为是 sglist 合并成功的关键因素。
 *
 * -- nyc
 */
static inline void expand(struct zone *zone, struct page *page,
	int low, int high, int migratetype)
{
	unsigned long size = 1 << high;

	while (high > low) {
		high--;
		size >>= 1;
		VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);

		/*
		 * 标记为 guard pages (或 page), 这将允许在 buddy 将被
		 * 释放时合并回分配器.对应的页表项不会被创建，
		 * pages 在 虚拟地址空间上仍将保持不存在。
		 */
		if (set_page_guard(zone, &page[size], high, migratetype))
			continue;

		add_to_free_list(&page[size], zone, high, migratetype);
		set_buddy_order(&page[size], high);
	}
}
③ __rmqueue()：分配封装函数

这个函数其实主要是对其他分配函数的封装，最终的核心函数其实都还是 __rmqueue_smallest()：

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
/*
 * 从 buddy allocator 上移除一个元素.
 * 在持有 zone->lock 时调用.
 */
static __always_inline struct page *
__rmqueue(struct zone *zone, unsigned int order, int migratetype,
						unsigned int alloc_flags)
{
	struct page *page;

	if (IS_ENABLED(CONFIG_CMA)) {
		/*
		 * 通过当半数空闲内存在 CMA 区域时从 CMA 中分配
		 * 以平衡常规的与CMA区域的可迁移的分配。
		 */
		if (alloc_flags & ALLOC_CMA &&
		    zone_page_state(zone, NR_FREE_CMA_PAGES) >
		    zone_page_state(zone, NR_FREE_PAGES) / 2) {
			page = __rmqueue_cma_fallback(zone, order);
			if (page)
				goto out;
		}
	}
retry:
	page = __rmqueue_smallest(zone, order, migratetype);
	if (unlikely(!page)) {
		if (alloc_flags & ALLOC_CMA)
			page = __rmqueue_cma_fallback(zone, order);

		if (!page && __rmqueue_fallback(zone, order, migratetype,
								alloc_flags))
			goto retry;
	}
out:
	if (page)
		trace_mm_page_alloc_zone_locked(page, order, migratetype);
	return page;
}

流程如下：

  • 若开启了 CMA，比对常规区域与 CMA 区域的空闲页面数量，若 CMA 的多则调用 __rmqueue_cma_fallback() 从 CMA 区域分配（其实就是调用 __rmqueue_smallest() 从迁移类型为 MIGRATE_CMA 的链表上分配），成功则直接返回
  • 调用 __rmqueue_smallest() 从指定迁移类型链表进行分配，若未成功：
    • 若设置了 ALLOC_CMA 的分配 flag，调用 __rmqueue_cma_fallback() 从 CMA 区域进行分配
    • 若上一步失败则调用 __rmqueue_fallback() 尝试从其他迁移类型链表获取页面，若还是失败则重试这一个大步骤

III. __alloc_pages_slowpath()：慢速分配路径

当快速路径的分配不成功时，说明系统当前可能已经没有足够的连续的空闲页面，这时我们就要进入到慢速路径的分配，进行内存碎片整理与内存回收，之后再进行分配

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
static inline struct page *
__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
						struct alloc_context *ac)
{
	bool can_direct_reclaim = gfp_mask & __GFP_DIRECT_RECLAIM;
	const bool costly_order = order > PAGE_ALLOC_COSTLY_ORDER;
	struct page *page = NULL;
	unsigned int alloc_flags;
	unsigned long did_some_progress;
	enum compact_priority compact_priority;
	enum compact_result compact_result;
	int compaction_retries;
	int no_progress_loops;
	unsigned int cpuset_mems_cookie;
	int reserve_flags;

	/*
	 * 我们还进行了健全性检查，以发现非原子上下文中的 caller 滥用原子储备（的行为）。
	 */
	if (WARN_ON_ONCE((gfp_mask & (__GFP_ATOMIC|__GFP_DIRECT_RECLAIM)) ==
				(__GFP_ATOMIC|__GFP_DIRECT_RECLAIM)))
		gfp_mask &= ~__GFP_ATOMIC;

retry_cpuset:
	compaction_retries = 0;
	no_progress_loops = 0;
	compact_priority = DEF_COMPACT_PRIORITY;
	cpuset_mems_cookie = read_mems_allowed_begin();

	/*
	 * 仅在 kswapd 需要被唤醒前，快速路径使用保守的 alloc_flags 才能成功，
	 * 并且避免精确地设置 alloc_flags。 所以我们现在这么做。
	 */
    // 重新设置 alloc_flags，因为快速路径的分配在 kswapd 被唤醒之前
    // 只有使用保守的 alloc_flags 才能成功，而现在我们将唤醒 kswapd，
    // 因此恢复使用原有的 gfp_mask 对应的 alloc_flags
	alloc_flags = gfp_to_alloc_flags(gfp_mask);

	/*
	 * 我们需要为 zonelist 迭代器重新计算起始点，因为我们可能在快速路径中
	 * 使用了不同的 nodemask ，或是有个 cpuset 的修改而我们正在重试
	 * - 否则我们可能会无休止地迭代不合格的 zone
	 */
	ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
					ac->highest_zoneidx, ac->nodemask);
	if (!ac->preferred_zoneref->zone)
		goto nopage;

    // 如果 ALLOC_KSWAPD，唤醒 kswapd 线程回收内存
	if (alloc_flags & ALLOC_KSWAPD)
		wake_all_kswapds(order, gfp_mask, ac);

	/*
	 * 调整后的 alloc_flags 可能会立即成功，所以先进行尝试
	 */
	page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
	if (page)
		goto got_pg;

	/*
	 * 对于代价高的分配, 首先尝试直接的 compaction（译注：碎片整理机制）,
	 * 因为有可能我们仍有足够的基本页面，并不需要去回收. 对于不可迁移的高阶分配，
	 * 同样这么做, 因为 compaction 将尝试通过从相同迁移类型的块进行迁移
	 * 以避免永久的碎片. 别对允许忽视水位线的分配尝试这个，因为
	 * ALLOC_NO_WATERMARKS 还没发生。
	 */
	if (can_direct_reclaim &&
			(costly_order ||
			   (order > 0 && ac->migratetype != MIGRATE_MOVABLE))
			&& !gfp_pfmemalloc_allowed(gfp_mask)) {
		page = __alloc_pages_direct_compact(gfp_mask, order,
						alloc_flags, ac,
						INIT_COMPACT_PRIORITY,
						&compact_result);
		if (page)
			goto got_pg;

		/*
		 * 检查带有 __GFP_NORETRY 的代价高的分配, 其
		 * 包括一些 THP page fault 的分配
		 */
		if (costly_order && (gfp_mask & __GFP_NORETRY)) {
			/*
			 * 若分配整个 pageblock(s) 且 compaction 由于所有的 zone
			 * 都在水位线下失败了，或是被禁止了因为其最近在该order上失败了，
			 * 除非分配器有请求的 compaction 与回收尝试，否则直接失败
			 *
			 * 回收是：
			 *  - 可能非常昂贵因为 zones 可能远低于他们的低水位线，
			 *    或是这是非常突发的高阶分配的一部分,
			 *  - 不一定会有帮助因为 isolate_freepages() 可能不会在
			 *    被释放的页面上迭代作为其线性扫描的一部分，且
			 *  - 不大可能会让整个 pageblocks 自己释放
			 */
			if (compact_result == COMPACT_SKIPPED ||
			    compact_result == COMPACT_DEFERRED)
				goto nopage;

			/*
			 * 看起来好像 reclaim/compaction 是值得尝试的, 但
			 * 同步的 compaction 可能会非常 expensive, 故保持
			 * 使用异步的 compaction.
			 */
			compact_priority = INIT_COMPACT_PRIORITY;
		}
	}

retry:
	/* 确保只要我们循环， kswapd 便不会意外地休眠 */
	if (alloc_flags & ALLOC_KSWAPD)
		wake_all_kswapds(order, gfp_mask, ac);

	reserve_flags = __gfp_pfmemalloc_flags(gfp_mask);
	if (reserve_flags)
		alloc_flags = current_alloc_flags(gfp_mask, reserve_flags);

	/*
	 * 若内存策略可以忽略，重置 nodemask 与 zonelist 迭代器。
	 * 这些分配具有高优先级与系统性，而非用户导向。
	 */
	if (!(alloc_flags & ALLOC_CPUSET) || reserve_flags) {
		ac->nodemask = NULL;
		ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
					ac->highest_zoneidx, ac->nodemask);
	}

	/* 带着可能调整过 zonelist 与 alloc_flags 再次尝试 */
	page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
	if (page)
		goto got_pg;

	/* 调用方不想要回收, 我们无法平衡任何事 */
	if (!can_direct_reclaim)
		goto nopage;

	/* 避免递归地直接回收 */
	if (current->flags & PF_MEMALLOC)
		goto nopage;

	/* 尝试直接回收后分配 */
	page = __alloc_pages_direct_reclaim(gfp_mask, order, alloc_flags, ac,
							&did_some_progress);
	if (page)
		goto got_pg;

	/* 尝试直接 compaction 后分配 */
	page = __alloc_pages_direct_compact(gfp_mask, order, alloc_flags, ac,
					compact_priority, &compact_result);
	if (page)
		goto got_pg;

	/* 若是特别指定的请求，不要循环 */
	if (gfp_mask & __GFP_NORETRY)
		goto nopage;

	/*
	 * 不要重试高花销的高阶分配除非他们是
	 * __GFP_RETRY_MAYFAIL
	 */
	if (costly_order && !(gfp_mask & __GFP_RETRY_MAYFAIL))
		goto nopage;

	if (should_reclaim_retry(gfp_mask, order, ac, alloc_flags,
				 did_some_progress > 0, &no_progress_loops))
		goto retry;

	/*
	 * 若0阶的回收无法取得任何进展，则重试 compaction 没有任何意义，
	 * 因为当前对 compaction 的实现是基于有足够的空闲内存的
	 *  (参见 __compaction_suitable)
	 */
	if (did_some_progress > 0 &&
			should_compact_retry(ac, order, alloc_flags,
				compact_result, &compact_priority,
				&compaction_retries))
		goto retry;


	/* 在我们开始 OOM killing 之前处理可能的 cpuset 更新竞争 */
	if (check_retry_cpuset(cpuset_mems_cookie, ac))
		goto retry_cpuset;

	/* 回收失败了, 开始 killing 一些东西 */
    // 要杀一些进程或是别的东西来腾内存了
	page = __alloc_pages_may_oom(gfp_mask, order, ac, &did_some_progress);
	if (page)
		goto got_pg;

	/* 在无尽的循环中避免没有水位线的分配 */
	if (tsk_is_oom_victim(current) &&
	    (alloc_flags & ALLOC_OOM ||
	     (gfp_mask & __GFP_NOMEMALLOC)))
		goto nopage;

	/* 若 OOM killer 取得了一些成效，重试 */
	if (did_some_progress) {
		no_progress_loops = 0;
		goto retry;
	}

nopage:
	/* 在我们失败之前处理可能的 cpuset 的更新竞争 */
	if (check_retry_cpuset(cpuset_mems_cookie, ac))
		goto retry_cpuset;

	/*
	 * 确保 __GFP_NOFAIL 请求没有泄露且确保我们一直在重试
	 */
	if (gfp_mask & __GFP_NOFAIL) {
		/*
		 * 所有存在的 __GFP_NOFAIL 用户都是可以被阻塞的, 
		 * 故对任何新的实际上需要 GFP_NOWAIT 的用户进行警告
		 */
		if (WARN_ON_ONCE(!can_direct_reclaim))
			goto fail;

		/*
		 * 这个上下文的 PF_MEMALLOC 请求非常奇怪
		 * 因为我们不能回收任何东西只能循环等待
		 * 某人来为我们做些什么
		 */
		WARN_ON_ONCE(current->flags & PF_MEMALLOC);

		/*
		 * 无失败的高开销的 orders 是一项艰巨的要求，
		 * 我们对此并没有太多准备，故让我们警告这些用户
		 * 以便于我们能够识别出他们并将之转化为别的东西
		 */
		WARN_ON_ONCE(order > PAGE_ALLOC_COSTLY_ORDER);

		/*
		 * 通过让他们能访问保留的内存来帮助非失败的分配
		 * 但不使用 ALLOC_NO_WATERMARKS 因为这可能
		 * 大量减少内存保留区而让情况更坏
		 */
		page = __alloc_pages_cpuset_fallback(gfp_mask, order, ALLOC_HARDER, ac);
		if (page)
			goto got_pg;

		cond_resched();
		goto retry;
	}
fail:
	warn_alloc(gfp_mask, ac->nodemask,
			"page allocation failure: order:%u", order);
got_pg:
	return page;
}

这里我们先补充一个概念——Memory compaction 机制，其实就是整理内存碎片，对零散的内存页进行迁移，从而将零散的空闲内存页变成大块的空闲内存，不过这里只整理可以移动的碎片：

从知乎偷的图.png

现在我们来看慢速分配的整个流程：

  • 使用原有的 gfp_flag 重新设置 alloc_flag，并重新计算 preferred zone，若设置了 ALLOC_KSWAPD 则调用 wake_all_kswapds() 唤醒 kswapd 线程进行内存回收
  • 之后重新尝试快速路径的分配，若成功则直接返回
  • 接下来调用 __alloc_pages_direct_compact() 进行 compaction，该函数内部在整理完后会重新尝试快速路径的分配，若成功则直接返回
  • （retry）接下来调用 wake_all_kswapds() 唤醒 kswapd 线程进行内存回收
  • 调整 zonelist 与 alloc_flag，之后再次尝试快速路径分配，若成功则直接返回
  • 若 gfp_flag 中没有 __GFP_DIRECT_RECLAIM 或是进程 PCB 的 flag 中有 PF_MEMALLOC，直接跳转到 （nopage）
  • 调用 __alloc_pages_direct_reclaim() 进行内存回收（内部调用 __perform_reclaim()）与快速路径分配，若成功则直接返回
  • 调用 __alloc_pages_direct_compact() 进行 compaction 与快速路径分配，若成功则直接返回
  • 如果设置了 __GFP_NORETRY ，或是该次内存分配开销较高（order > PAGE_ALLOC_COSTLY_ORDER）且未设置 __GFP_RETRY_MAYFAIL，直接跳到 （nopage）
  • 调用 should_reclaim_retry() 判断是否需要重新回收，若是则跳回（retry）
  • 调用 should_compact_retry() 判断是否需要重新进行 compaction，若是则跳回（retry）
  • 调用 check_retry_cpuset() 检查 cpuset 是否发生变化，若是则跳转回开头
  • 调用 __alloc_pages_may_oom() 尝试 kill 一些进程来释放内存，该函数内首先还是会先进行一次快速分配，之后才是调用 out_of_memory() 来杀掉最适合的进程以释放内存，最后若设置了 __GFP_NOFAIL 则调用 __alloc_pages_cpuset_fallback() 再次尝试内存分配，在该函数中会两次走快速路径进行分配（第一次会额外附加上 ALLOC_CPUSET 的 flag）
  • 如果把当前进程杀掉了，跳到（nopage）；如果杀进程取得了成效，跳回（retry）
  • （nopage）调用 check_retry_cpuset() 检查 cpuset 是否发生变化，若是则跳转回开头
  • 若设置了 __GFP_NOFAIL 则进行一系列的警告，并调用 __alloc_pages_cpuset_fallback() 再次尝试内存分配，若未成功则跳回（retry）
  • 返回结果

image.png

四、上层封装分配函数

在 __alloc_pages_nodemask() 上层主要有三个页面分配函数，其调用路径如下：

1
2
3
4
5
6
7
8
9
10
11
12
__alloc_pages_node  /*返回struct page的指针*/
    __alloc_pages
    	__alloc_pages_nodemask

alloc_pages         /*返回struct page的指针*/
    alloc_pages_current
    	__alloc_pages_nodemask
        
__get_free_pages    /*返回页面的虚拟地址*/
    alloc_pages
        alloc_pages_current
            __alloc_pages_nodemask

0x03.页的释放

前面我们讲了页面是如何分配的，现在我们来看页面是如何释放的

一、__free_one_page()：释放页面的核心函数

该函数是 buddy system 中用以进行页面释放的核心函数，所有的页面释放 API 都是基于该函数的封装

该函数定义于 /mm/page_alloc.c 中，主要作用是将特定页面释放到特定 zone 上，需要注意的是这里的 one page 不是一张页框而是一块连续内存（可能有多张页）

还需要注意的是这是一个释放页面的基本函数，故我们需要提供待释放页面的页结构体（struct page）、页框号、页面块的阶（order）、目标 zone、迁移类型等信息——这些信息通常由上层封装函数提供，这个函数所做的只是简单地将页挂回对应链表并检查合并的操作

如下：

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/*
 * buddy system 分配器的释放函数.
 *
 * buddy system 的想法是为多种“orders”的内存块
 * 维护一个直接映射表（包含位值）. 底部级别的表包含
 * 对最小的可分配内存单元（这里便是页面）的映射,
 * 而往上每更高一级则描述了从其下的一级的一对单元，因此是"buddies".
 * 从高层看，这里所做的仅是在标记底层可用的表项，
 * 并根据需要向上传播更改，再加上一些与 VM 系统的其他部分
 * 良好协作所需要的计数。
 * 在每个级别, 我们都保持一个 pages 的 list, 作为连续的
 * 长度为(1 << order)的空闲页的头节点并标记上 PageBuddy.
 * Page's order 被记录在 page_private(page) 域.
 * 故当我们在分配或释放其一时, 我们可以得到另一个的状态。
 * 也就是说，若我们分配一个小的块，而两个都是空闲的，
 * 区域的剩余部分必须被分割成块. 若一个块被释放了，
 * 而他的 buddy 也是闲置的, 那么这将触发合并成一个更大的块
 *
 * -- nyc
 */

static inline void __free_one_page(struct page *page,
		unsigned long pfn,
		struct zone *zone, unsigned int order,
		int migratetype, fpi_t fpi_flags)
{
	struct capture_control *capc = task_capc(zone);
	unsigned long buddy_pfn;
	unsigned long combined_pfn;
	unsigned int max_order;
	struct page *buddy;
	bool to_tail;

    // 这里的 MAX_ORDER 和 pageblock_order 都是宏
	max_order = min_t(unsigned int, MAX_ORDER - 1, pageblock_order);

	VM_BUG_ON(!zone_is_initialized(zone));
	VM_BUG_ON_PAGE(page->flags & PAGE_FLAGS_CHECK_AT_PREP, page);

	VM_BUG_ON(migratetype == -1);
	if (likely(!is_migrate_isolate(migratetype)))
		__mod_zone_freepage_state(zone, 1 << order, migratetype);

	VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page);
	VM_BUG_ON_PAGE(bad_range(zone, page), page);

continue_merging:
	while (order < max_order) {
		if (compaction_capture(capc, page, order, migratetype)) {
			__mod_zone_freepage_state(zone, -(1 << order),
								migratetype);
			return;
		}
		buddy_pfn = __find_buddy_pfn(pfn, order);	// 计算 buddy 页框号
		buddy = page + (buddy_pfn - pfn);		// 计算 buddy 的页结构体，注意这里是指针加法

		if (!pfn_valid_within(buddy_pfn)) // 页框号合法性检查
			goto done_merging;
		if (!page_is_buddy(page, buddy, order))  // 检查 page 和 buddy 是否是一对
			goto done_merging;
		/*
		 * 我们的 buddy（译注：释放页面的“配对”页面，可以看开头的注释） 是空闲的
		 * 或其为 CONFIG_DEBUG_PAGEALLOC 的 guard page，
		 * 与其合并后升到高一级的order。
		 */
		if (page_is_guard(buddy))
			clear_page_guard(zone, buddy, order, migratetype);
		else
			del_page_from_free_list(buddy, zone, order);
		combined_pfn = buddy_pfn & pfn;
		page = page + (combined_pfn - pfn);
		pfn = combined_pfn;
		order++;
	}
	if (order < MAX_ORDER - 1) {
		/* 若我们到了这，这意味着 order >= pageblock_order.
		 * 我们想要预防在常规 pageblock 与独立的pageblock 之间的合并。
		 * 没有这个，pageblock隔离可能造成错误的空闲页或CMA计数. 
		 *
		 * 我们不想为了更频繁的低阶合并使用这个代码
		 */
		if (unlikely(has_isolate_pageblock(zone))) {
			int buddy_mt;

			buddy_pfn = __find_buddy_pfn(pfn, order);
			buddy = page + (buddy_pfn - pfn);
			buddy_mt = get_pageblock_migratetype(buddy);

			if (migratetype != buddy_mt
					&& (is_migrate_isolate(migratetype) ||
						is_migrate_isolate(buddy_mt)))
				goto done_merging;
		}
		max_order = order + 1;
		goto continue_merging;
	}

done_merging:
	set_buddy_order(page, order); // 在 page->private 中储存其 order

    // 判断是插到链表头还是链表尾，通常是链表头，即遵循 LIFO
	if (fpi_flags & FPI_TO_TAIL)
		to_tail = true;
	else if (is_shuffle_order(order))
		to_tail = shuffle_pick_tail();
	else
        // 该函数会检查是否下一个最高阶的 buddy 是否空闲
        // 若是，则可能正在释放的页面块将很快被合并，此时我们应当将其添加到链表的尾部
        // 这样就不大可能又被别的进程很快就分配走了，而是可能被合并为高阶页面
		to_tail = buddy_merge_likely(pfn, buddy_pfn, page, order);

    // 插入特定迁移链表
	if (to_tail)
		add_to_free_list_tail(page, zone, order, migratetype);
	else
		add_to_free_list(page, zone, order, migratetype);

	/* Notify page reporting subsystem of freed page */
	if (!(fpi_flags & FPI_SKIP_REPORT_NOTIFY))
		page_reporting_notify_free(order);
}

我们将与待释放页面凑成一对的内存块称为 buddy，所谓凑成一对便是这两个内存块在物理上连续，且能凑成一个更高一阶的大内存块，由此称之为一对 buddies

该函数主要流程如下：

  • （continue_merging，循环开头）调用 __find_buddy_pfn() 计算待释放页面的 buddy 的第一张物理页的页框号，算法比较暴力：page_pfn ^ (1 << order)
  • 调用 page_is_buddy() 检查 buddy 与 待释放页面是否是一对 buddies，若否，则跳到（done_merging），这里的检查需要满足四个要素：
    • buddy 不在空洞中
    • buddy 在 buddy system 中（即 buddy 也是空闲内存块）
    • 待释放页面与其 buddy 在同一个 zone 中
    • 待释放页面与其 buddy 有着同样的阶（order）
  • 若 buddy 为 guard page，则调用 clear_page_guard() 清楚这个属性让其变成空闲页面，这里清除的操作是通过将 page 结构体的 private 字段置 0 实现的；若否，则说明是常规的空闲页面，调用 del_page_from_free_list() 将其脱链
  • 此时我们的新的高阶内存块就完成合成了，接下来我们回到循环开头重新寻找这个合成的新内存块的 buddy，这个循环一直持续到 max_order （一般是10），作为下一次循环的页框号的计算方式是 buddy_pfn & pfn，之后做指针运算 page + (combined_pfn - pfn) 找到对应的 page 结构体
  • 若退出循环时的 order 满足 order < MAX_ORDER - 1 ，则调用 has_isolate_pageblock() 检查 zone 中是否有 isolate block，若是则进行相关操作（这块代码还没看懂），最后跳转回（continue_merging）；这一步主要是防止 isolate pageblock 与常规的 pageblock 发生合并
  • （done_merging）这一步主要是调用 set_buddy_order() 在 page 结构体的 private 字段存放该内存块的 order
  • 若是设置了 FPI_TO_TAIL flag，则将 to_tail 置为 true；否则，若内存块的 order >= SHUFFLE_ORDER（MAX_ORDER - 1），则将 to_tail 置为随机结果（shuffle_pick_tail()）；否则置为调用 buddy_merge_likely() 的结果，该函数会检查是否下一个最高阶的 buddy 是否空闲，若是，则可能正在释放的页面块将很快被合并，此时我们应当将其添加到链表的尾部，这样就不大可能又被别的进程很快就分配走了，而是可能被合并为高阶页面
  • 若 to_tail 为真，则调用 add_to_free_list_tail() 将该空闲页添加到链表末尾，否则调用 add_to_free_list() 添加到链表开头

二、上层封装函数

所有页面释放的函数其实都是对 __free_one_page() 的封装，最终都会调用到这个函数，路径如下：

image.png

OS
#Linux #Linux Kernel #操作系统 #内存管理 #buddy system
【OS.0x03】Linux内核内存管理II - Buddy System
https://arttnba3.github.io/2022/06/30/OS-0X03-LINUX-KERNEL-MEMORY-5.11-PART-II/
作者
arttnba3
发布于
2022年6月30日
许可协议