在一切开始之前

一个总览图：

malloc，brk，mmap返回的都是线性地址（虚拟地址）

kmalloc从slab中申请到的是物理内存，位于物理内存的映射区，且地址连续，但返回的是线性地址（虚拟地址），该线性地址与真实地址仅相差一个固定的偏移，通过内核提供的virt_to_phys()可以实现该虚拟地址到真实的内核物理地址之间的转换:

1
2
3
4
static inline phys_addr_t virt_to_phys(volatile void *address)
{
	return __pa(address);
}

buddy_system

进程地址空间与虚拟地址空间：

img

buddy system

上文说到，zone的空闲页帧由buddy system管理，具体的,管理的是zone结构体中的struct free_area free_area[MAX_ORDER];在代码中可以找到

1
#define MAX_ORDER 11

也就是管理着11个free_area结构体

我们可以在 /include/linux/mmzone.h 中找到其定义

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

struct list_head 是内核通用链表，而 MIGRATE_TYPES 代表了迁移的种类数目，nr_free代表链表上所有空闲页帧的数目（以内存块为单位，只有第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
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 than
	 * a single pageblock.
	 */
	MIGRATE_CMA,
#endif
#ifdef CONFIG_MEMORY_ISOLATION
	MIGRATE_ISOLATE,	/* can't allocate from here */
#endif
	MIGRATE_TYPES
};

这里讲一下页面迁移的知识

img

假如上图中大部分页都是可移动页，而分配出去的四个页都是不可移动页，由于不可移动页插在了其他类型页的中间，就导致了无法从原本空闲的连续内存区中分配较大的内存块。

将可回收页和不可移动页分开，这样虽然在不可移动页的区域当中无法分配大块的连续内存，但是可回收页的区域却没有受其影响，可以分配大块的连续内存

故free_area 结构并非只有一个链表，而是多个链表，主要以页的迁移种类来分类，而不同的free_area所存储的页面大小也是不同的

  • free_area[0] 中存储了2^0大小的页面组成的list（即一个page大小）
  • free_area[1] 中存储了2^1大小的页面组成的list（即两个page大小）
  • ……
  • free_area[10] 中存储了2^10大小的页面组成的list（即十个page大小）

结构大致如下图所示：

image-20221105005845503

结合上面的page结构体分析，链表是利用空闲区间第一个物理页page结构的lru成员构成的双向链表。

在linux上可以利用 cat /proc/buddyinfo 查看相关信息

image-20221105010718360

右侧各列数字代表0~10order 空闲区间页帧的数量。

分配

一个总览图：

我现在审计的版本核心函数应该是__alloc_pages。好奇去翻了下commit，不过 没找到到底是啥时候改的

在这里插入图片描述

alloc_pages 函数返回内存块的首个页帧page结构体指针，实现于 /include/linux/gfp.h

函数调用链：

1
2
3
4
alloc_pages
  alloc_pages_node
      __alloc_pages_node(nid, gfp_mask, order) 
          __alloc_pages(gfp_mask, order, nid, NULL) 
1
2
3
4
static inline struct page *alloc_pages(gfp_t gfp_mask, unsigned int order)
{
	return alloc_pages_node(numa_node_id(), gfp_mask, order);
}

gfp_mask为分配修饰符，在/include/linux/gfp.h 中都可以找到，例如行为修饰符：

这里书上或者源码里都有较详细的注释，我直接copy arttnba3师傅的表格了（

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

除此之外还有区修饰符，以及类型标志（各种修饰符的组合）

order也就是要分配的空间大小的阶数

1
2
3
4
5
6
7
8
static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask,
						unsigned int order)
{
	if (nid == NUMA_NO_NODE)
		nid = numa_mem_id();

	return __alloc_pages_node(nid, gfp_mask, order);
}

nid就是node节点的id，一般是离cpu最近的那个

1
2
3
4
5
6
7
8
__alloc_pages_node(int nid, gfp_t gfp_mask, unsigned int order)
{
	VM_BUG_ON(nid < 0 || nid >= MAX_NUMNODES);
	VM_WARN_ON((gfp_mask & __GFP_THISNODE) && !node_online(nid));

	return __alloc_pages(gfp_mask, order, nid, NULL);
}

__alloc_pages()

核心函数

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
struct page *__alloc_pages(gfp_t gfp, unsigned int order, int preferred_nid,
							nodemask_t *nodemask)
{
	struct page *page;
	unsigned int alloc_flags = ALLOC_WMARK_LOW;
	gfp_t alloc_gfp; /* The gfp_t that was actually used for allocation */
	struct alloc_context ac = { };

	/*
	 * There are several places where we assume that the order value is sane
	 * so bail out early if the request is out of bound.
	 */
	if (unlikely(order >= MAX_ORDER)) {
		WARN_ON_ONCE(!(gfp & __GFP_NOWARN));
		return NULL;
	}

	gfp &= gfp_allowed_mask;
	/*
	 * Apply scoped allocation constraints. This is mainly about GFP_NOFS
	 * resp. GFP_NOIO which has to be inherited for all allocation requests
	 * from a particular context which has been marked by
	 * memalloc_no{fs,io}_{save,restore}. And PF_MEMALLOC_PIN which ensures
	 * movable zones are not used during allocation.
	 */
	gfp = current_gfp_context(gfp);
	alloc_gfp = gfp;
	if (!prepare_alloc_pages(gfp, order, preferred_nid, nodemask, &ac,
			&alloc_gfp, &alloc_flags))
		return NULL;

	/*
	 * Forbid the first pass from falling back to types that fragment
	 * memory until all local zones are considered.
	 */
	alloc_flags |= alloc_flags_nofragment(ac.preferred_zoneref->zone, gfp);

	/* First allocation attempt */
	page = get_page_from_freelist(alloc_gfp, order, alloc_flags, &ac);
	if (likely(page))
		goto out;

	alloc_gfp = gfp;
	ac.spread_dirty_pages = false;

	/*
	 * Restore the original nodemask if it was potentially replaced with
	 * &cpuset_current_mems_allowed to optimize the fast-path attempt.
	 */
	ac.nodemask = nodemask;

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

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

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

	return page;
}

这里分配了个 alloc_context 结构体，定义于 /mm/internal.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
/*
 * 用以保存在分配时涉及到的函数间传递的
 * 绝大部分的不可变的分配参数的结构体，
 * 包括 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 的性质，低于最高 zoneidx 的 zone 上的内存将受到 lowmem_reserve[highest_zoneidx] 的保护。
    highest_zoneidx 也被回收/压缩用于限制目标区域，因为高于此索引的区域不能用于此分配请求。
    */
	
	enum zone_type highest_zoneidx;  
    
	bool spread_dirty_pages;
};

zonelist结构体定于如下：

1
2
3
4
5
6
7
8
9
10
11
12
/* 一个分配请求在 zonelist 上运行。 zonelist 是区域列表，第一个是分配的“目标”，其他区域是后备区域，优先级递减。
  *
  * 为了加快 zonelist 的读取速度，zonerefs 包含正在读取的条目的区域索引。 在给定结构 zoneref 的情况下访问信息的辅助函数是
  *
  * zonelist_zone() - 返回结构区域 * 用于 _zonerefs 中的条目
  * zonelist_zone_idx() - 返回一个条目的区域索引
  * zonelist_node_idx() - 返回条目的节点索引
*/

struct zonelist {
	struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1];
};

zoneref

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

也就是记录了本次分配上下文中，我们将要操作的zone列表

struct zoneref *preferred_zoneref; 如字面意思，就是分配优先级较高的zone

而NODEMASK 作为内核基础数据结构，常用于统计当前 Online/Possible Online NUMA NODE 的数量、判断 NUMA NODE 是否包含内存、判断 NUMA NODE 是否与 CPU 进行绑定等，NODEMASK 作为 NUMA 子系统不可或缺的一部分，为内核和其他子系统提供了 NUMA NODE 的多种信息，首先来看一下 NODEMASK 定义:

1
2
typedef struct { DECLARE_BITMAP(bits, MAX_NUMNODES); } nodemask_t;
extern nodemask_t _unused_nodemask_arg_;

在支持多 NUMA NODE 的架构体系中，内核可以最多支持 MAX_NUMNODES 个 NUMA NODE, NODEMASK 基于 Bitmap 机制，将每个 NUMA NODE 通过 bitmap 中的一个 bit 进行维护，因此定义了 NODEMASK 逻辑结构，每个 NUMA NODE 对应了 NODEMASK 中的一个 bit，也可以称为 node，通过 node 的置位或清零来维护指定信息。

可以理解为于NUMA 有关的node信息

migratetype就是页面迁移种类，现在重新审视__alloc_pages（）函数

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
struct page *__alloc_pages(gfp_t gfp, unsigned int order, int preferred_nid,
							nodemask_t *nodemask)
{
	struct page *page;
	unsigned int alloc_flags = ALLOC_WMARK_LOW;
	gfp_t alloc_gfp; /* The gfp_t that was actually used for allocation */
	struct alloc_context ac = { }; //存放上下文信息的结构体

	/*
	 有几个地方我们假设请求值是合理的，所以如果请求超出范围，请尽早退出。
	 */
	if (unlikely(order >= MAX_ORDER)) {
		WARN_ON_ONCE(!(gfp & __GFP_NOWARN));
		return NULL;
	}

	gfp &= gfp_allowed_mask;
	/*
	 应用范围分配约束。 这主要是关于 GFP_NOFS resp。 GFP_NOIO 必须为来自特定上下文的所有分配请求继承，该上下文已由 memalloc_no{fs,io}_{save,restore} 标记  ，PF_MEMALLOC_PIN 确保在分配期间不使用可移动区域。
	 */
	gfp = current_gfp_context(gfp);////根据当前进程的flags（current->flags）调整gfp
	alloc_gfp = gfp;
	if (!prepare_alloc_pages(gfp, order, preferred_nid, nodemask, &ac,
			&alloc_gfp, &alloc_flags))
        // 对alloc_context 结构体进行赋值,以及一些分配浅浅的准备操作
		return NULL;

	/*
	 在考虑所有本地区域之前，禁止第一次回退到碎片内存的类型。
	 */
	alloc_flags |= alloc_flags_nofragment(ac.preferred_zoneref->zone, gfp);

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

	alloc_gfp = gfp;
	ac.spread_dirty_pages = false;

	/*
	 如果它可能被 &cpuset_current_mems_allowed 替换，则恢复原始节点掩码以优化快速路径尝试。
	 */
	ac.nodemask = nodemask;
	//第一次失败 尝试第二次分配 慢速路径
	page = __alloc_pages_slowpath(alloc_gfp, order, &ac);

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

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

	return page;
}

get_page_from_freelist()

快分配路径，由zone中的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
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
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 ，尝试找一个拥有足够free pages的zone
	 * See also __cpuset_node_allowed() comment in kernel/cpuset.c.
	 */
	no_fallback = alloc_flags & ALLOC_NOFRAGMENT; //避免内存碎片
	z = ac->preferred_zoneref;//尝试从优先的zone开始分配
    //从优先zone z开始遍历zonelist中的zoneref数组
    //此函数返回以z为起点，遍历到小于等于高水位zone的下一个zone
    /*
    宏定义如下
    #define for_next_zone_zonelist_nodemask(zone, z, highidx, nodemask) \
	for (zone = z->zone;	\
		zone;							\
		z = next_zones_zonelist(++z, highidx, nodemask),	\
			zone = zonelist_zone(z))
    */
    
    
	for_next_zone_zonelist_nodemask(zone, z, ac->highest_zoneidx,
					ac->nodemask) {
		struct page *page;
		unsigned long mark;
		//开启了cpuset的情况，判断gfp和flag
		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 中节点的意识.
		 */
		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;
			}
		}

		if (no_fallback && nr_online_nodes > 1 &&
		    zone != ac->preferred_zoneref->zone) { //当前zone不是优先zone&&node数量>1
			int local_nid;

			/*
			 * 若移动到了 remote node（译注：非当前node？）, 则重试，
			 * 但允许 fragmenting fallbacks. 局部性比避免碎片更加重要。
			 */
			local_nid = zone_to_nid(ac->preferred_zoneref->zone);
            //判断node是否是local node，不是的话去除ALLOC_NOFRAGMENT位，优先分配local node中的zone
			if (zone_to_nid(zone) != local_nid) {
				alloc_flags &= ~ALLOC_NOFRAGMENT;
				goto retry;
			}
		}
		//获取水位线 并判断是否充足 
		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);
			if (alloc_flags & ALLOC_NO_WATERMARKS)//不需要检查水位线的话 直接从该zone分配
				goto try_this_zone;

			if (!node_reclaim_enabled() ||
			    !zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
				continue;
			//进行页面回收
			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:
        //rmqueue函数内部即buddy算法的实现
		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;
	}c

	return NULL;
}

总流程如下：

偷，侵删

偷的图.png

rmqueue()

在这之前先简单梳理一下伙伴算法，以便于理解函数流程

伙伴的定义：

  1. 两个块大小相同；
  2. 两个块地址连续；
  3. 两个块必须是同一个大块中分离出来的；

对于分配和回收算法的概述，维基上有非常详细的例子:https://en.wikipedia.org/wiki/Buddy_memory_allocation

image-20221124161451211

分配：

image-20221105005845503

对于这样一个free_area链表，假设系统需要分配16k大小 (4个4k page)的块，则会执行以下步骤

  • 寻找free_area[2],
    • 有空闲块,则直接取出并退出
    • 无空闲块
      • 继续顺着数组向上寻找至有空闲块的链表free_area[k]
        • k为数组的最后，则说明没有空闲块，放弃
        • k不为数组的最后，则将free_area[k]的一个空闲块先平均分割，分割出来的一半放在 free_area[k-1]处继续作为内存块
          • 另一半也是如此继续分割，直至分割出来的大小刚好满足系统申请的大小（即刚好大于或等于，在这里即刚好大于等于16k）分配给系统，而其余分割出来的作为内存块挂在相应的free_area链表上

一个更形象的实例：

我们想分配70K的块空间

1.70K向上取整到2的倍数：128K

2.查询有128K空闲块吗？

3.没有，分配256K块。

　　a.有256K的空闲块吗？

　　b.没有，分配512K的块。

　　　　i.有512K空闲块吗？

　　　　ii.没有，分配1M的空闲块

　　　　　　i.有1M的空闲块吗？

　　　　　　ii.有，从1M的那个空闲链表中摘下，分配出去

​ iii.拆开一半挂在512k空闲链表上

           iv.返回另一半512K块

　　c.拆开一半挂在256k空闲链表上

　　d.返回另一半256k块

4.将获得的256K的块拆两半，一半挂在128K空闲链表中

5.另一半128K块返回用户。

https://blog.51cto.com/u_15351135/3726710

函数原型：

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
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(pcp_allowed_order(order))) {
        // 检查是否需要通过PCP进行分配，所谓PCP即Per_CPU方式，即内核将变量缓存给每一个CPU上，不同的CPU都保留有自己的副本，这样不同的CPU可以并发的访问自己的这部分变量而无需上锁。
		/*
		  * MIGRATE_MOVABLE 的 pcplist 可能在 CMA 区域有着页面，
		 * 当从 CMA 的分配不被允许时我们需要略过它
		 */
        
		if (!IS_ENABLED(CONFIG_CMA) || alloc_flags & ALLOC_CMA ||
				migratetype != MIGRATE_MOVABLE) {
			page = rmqueue_pcplist(preferred_zone, zone, order,
					gfp_flags, migratetype, alloc_flags);
            //直接使用 per_cpu_lists 分配
			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 的请求应略过它。
		 */
		if (order > 0 && alloc_flags & ALLOC_HARDER) {//尽力分配,则从MIGRATE_HIGHATOMIC所预留的空间分配
			page = __rmqueue_smallest(zone, order, 	MIGRATE_HIGHATOMIC);
			if (page)
				trace_mm_page_alloc_zone_locked(page, order, migratetype);
		}
		if (!page)
			page = __rmqueue(zone, order, migratetype, alloc_flags);//核心分配函数
	} while (page && check_new_pages(page, order));
	if (!page)
		goto failed;
	//更新zone freepage状态
	__mod_zone_freepage_state(zone, -(1 << order),
				  get_pcppage_migratetype(page));
	spin_unlock_irqrestore(&zone->lock, flags);

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

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:
	spin_unlock_irqrestore(&zone->lock, flags);
	return NULL;
}

在较早期的版本中是 likely(order ==0) ，直接判断当前阶是否是0来选择是否由per cpu lists 分配

而在此版本中已经是 if (likely(pcp_allowed_order(order)))，per cpu list分配已经支持更多order的链表了，具体的

，order<=3 时都会用pcp的方式分配

1
2
3
4
5
6
7
8
9
10
11
#define PAGE_ALLOC_COSTLY_ORDER 3
static inline bool pcp_allowed_order(unsigned int order)
{
	if (order <= PAGE_ALLOC_COSTLY_ORDER)
		return true;
#ifdef CONFIG_TRANSPARENT_HUGEPAGE
	if (order == pageblock_order)
		return true;
#endif
	return false;
}

函数流程图 偷的

img

rmqueue_pcplist

使用 per_cpu_lists 分配

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
static struct page *rmqueue_pcplist(struct zone *preferred_zone,
			struct zone *zone, unsigned int order,
			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_lock_irqsave(&pagesets.lock, flags);

	/*
	 * On allocation, reduce the number of pages that are batch freed.
	 * See nr_pcp_free() where free_factor is increased for subsequent
	 * frees.
	 */
	pcp = this_cpu_ptr(zone->per_cpu_pageset);
	pcp->free_factor >>= 1;
	list = &pcp->lists[order_to_pindex(migratetype, order)];//选择list
	page = __rmqueue_pcplist(zone, order, migratetype, alloc_flags, pcp, list);
	local_unlock_irqrestore(&pagesets.lock, flags);
	if (page) {
		__count_zid_vm_events(PGALLOC, page_zonenum(page), 1);
		zone_statistics(preferred_zone, zone, 1);
	}
	return page;
}

该函数主要就是为调用__rmqueue_pcplist做准备，即根据order来选择相应的pcp_list

__rmqueue_pcplist()
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
struct page *__rmqueue_pcplist(struct zone *zone, unsigned int order,
			int migratetype,
			unsigned int alloc_flags,
			struct per_cpu_pages *pcp,
			struct list_head *list)
{
	struct page *page;

	do {//大循环寻找内存块
		if (list_empty(list)) {
			int batch = READ_ONCE(pcp->batch);
			int alloced;

			/*
			 如果请求意味着空闲页面可以存储在 PCP 上，则相对于请求缩放批次。 对于小区域或引导页面集，Batch 可以是 1，因为这些页面可能属于任意区域，所以它们不应该存储空闲页面。
			 */
			if (batch > 1)
				batch = max(batch >> order, 2);
			alloced = rmqueue_bulk(zone, order,
					batch, list,
					migratetype, alloc_flags);

			pcp->count += alloced << order;
			if (unlikely(list_empty(list)))
				return NULL;
		}

		page = list_first_entry(list, struct page, lru);//unlink 脱链
		list_del(&page->lru);
		pcp->count -= 1 << order;//减小的是空闲页数 而不是块
	} while (check_new_pcp(page));

	return page;
}

如果list为空，则会调用rmqueue_bulk() 来申请page填充到list

rmqueue_bulk()：
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
/*
 * 为了高效率，从 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, allocated = 0;

	/*
	 * local_lock_irq held so equivalent to spin_lock_irqsave for
	 * both PREEMPT_RT and non-PREEMPT_RT configurations.
	 */
	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);
		allocated++;
		if (is_migrate_cma(get_pcppage_migratetype(page)))
			__mod_zone_page_state(zone, NR_FREE_CMA_PAGES,
					      -(1 << order));
	}

	/*
	* i 页面已从好友列表中删除，即使由于一些泄漏
	* 到 check_pcp_refill 失败所以调整基于 NR_FREE_PAGES
	* 在 i 上。 不要与 'allocated' 混淆，后者是
	* 添加到 pcp 列表的页面。
	 */
	__mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
	spin_unlock(&zone->lock);
	return allocated;
}

主要就是申请page，内部也调用了__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
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;

	/* Find a page of the appropriate size in the preferred list */
	for (current_order = order; current_order < MAX_ORDER; ++current_order) {
		area = &(zone->free_area[current_order]);
		page = get_page_from_free_area(area, migratetype);//从指定迁移类型的list中找到page，如果失败，则寻找的order++;
		if (!page)
			continue;
		del_page_from_free_list(page, zone, current_order);//负责将其list中拿走，操作包括list_del，list的计数--等;
		expand(zone, page, order, current_order, migratetype);//负责拆分的函数，即如果从odrer较大的list中选择了一一组page进行拆分，那么拆分后剩余的page将被添加到较低order的list中
		set_pcppage_migratetype(page, migratetype);
		return page;
	}

	return NULL;
}

十分精简的函数，就是遍历所有order链表，直至找到合适的page,由于上面讲过算法思想了，所以此函数十分好理解

最后此函数返回合适的page，这就是整个分配流程了（其实还有个慢分配路径没看，先坑了…

1
2
3
static inline struct page *
__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
						struct alloc_context *ac)

待补

回收：

  • 当我们释放内存块时把它挂到相应的空闲链表上，查询其伙伴是否在其空闲链表上(1)
    • 不在，退出
    • 在，合并成两倍大小的块，挂在下一个链表上
      • 对该两倍大小的块进行递归查询，即重复执行(1)，直至没有伙伴为止

类似这样的图例

img

from https://www.cnblogs.com/alantu2018/p/8527821.html

1.此时，如果有一个程序A想要申请一块45K大小的内存，则系统会将第一块64K的内存块分配给该程序（产生内部碎片为代价），如图b所示；

2.然后程序B向系统申请一块68K大小的内存，系统会将128K内存分配给该程序，如图c所示；

3.接下来，程序C要申请一块大小为35K的内存。系统将空闲的64K内存分配给该程序，如图d所示；

4.之后程序D需要一块大小为90K的内存。当程序提出申请时，系统本该分配给程序D一块128K大小的内存，但此时内存中已经没有空闲的128K内存块了，于是根据伙伴算法的原理，系统会将256K大小的内存块平分，将其中一块分配给程序D，另一块作为空闲内存块保留，等待以后使用，如图e所示；

5.紧接着，程序C释放了它申请的64K内存。在内存释放的同时，系统还负责检查与之相邻并且同样大小的内存是否也空闲，由于此时程序A并没有释放它的内存，所以系统只会将程序C的64K内存回收，如图f所示；

6.然后程序A也释放掉由它申请的64K内存，系统随机发现与之相邻且大小相同的一段内存块恰好也处于空闲状态。于是，将两者合并成128K内存，如图g所示；

7.之后程序B释放掉它的128k，系统也将这块内存与相邻的128K内存合并成256K的空闲内存，如图h所示；

8.最后程序D也释放掉它的内存，经过三次合并后，系统得到了一块1024K的完整内存。

回收函数相对就简单很多

主要流程

  • free_pages

    • __free_pages

      • free_the_page

        • __free_pages_ok

        • free_one_page

        • free_unref_page

          • free_one_page

            • free_one_page
__free_pages

主函数

1
2
3
4
5
6
7
8
9
void __free_pages(struct page *page, unsigned int order)
{
	if (put_page_testzero(page))
		free_the_page(page, order);
	else if (!PageHead(page))
		while (order-- > 0)
			free_the_page(page + (1 << order), order);
}
EXPORT_SYMBOL(__free_pages);
free_the_page
1
2
3
4
5
6
7
static inline void free_the_page(struct page *page, unsigned int order)
{
	if (pcp_allowed_order(order))		/* 通过pcp 分配 */
		free_unref_page(page, order);
	else
		__free_pages_ok(page, order, FPI_NONE);
}
free_unref_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
void free_unref_page(struct page *page, unsigned int order)
{
	unsigned long flags;
	unsigned long pfn = page_to_pfn(page);
	int migratetype;

	if (!free_unref_page_prepare(page, pfn, order))
		return;

	/*
	* 我们只跟踪 pcp 列表上的不可移动、可回收和可移动。
	* 将 ISOLATE 页面放在隔离列表中，因为它们正在
	* 已离线，但将 HIGHATOMIC 视为可移动页面，以便我们可以获取这些页面
	* 必要时返回区域。 否则，我们可能不得不释放
	* 过度进入页面分配器
	 */
	migratetype = get_pcppage_migratetype(page);
	if (unlikely(migratetype >= MIGRATE_PCPTYPES)) {
		if (unlikely(is_migrate_isolate(migratetype))) {
			free_one_page(page_zone(page), page, pfn, order, migratetype, FPI_NONE);
            //核心free函数
			return;
		}
		migratetype = MIGRATE_MOVABLE;
	}
	//free 后的处理
	local_lock_irqsave(&pagesets.lock, flags);
	free_unref_page_commit(page, pfn, migratetype, order);
	local_unlock_irqrestore(&pagesets.lock, flags);
}

free_unref_page_commit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static void free_unref_page_commit(struct page *page, unsigned long pfn,
				   int migratetype, unsigned int order)
{
	struct zone *zone = page_zone(page);
	struct per_cpu_pages *pcp;
	int high;
	int pindex;

	__count_vm_event(PGFREE);
	pcp = this_cpu_ptr(zone->per_cpu_pageset);
	pindex = order_to_pindex(migratetype, order);
	list_add(&page->lru, &pcp->lists[pindex]); //将page插入pcp链表头
	pcp->count += 1 << order;
	high = nr_pcp_high(pcp, zone);
	if (pcp->count >= high) {
		int batch = READ_ONCE(pcp->batch);
		free_pcppages_bulk(zone, nr_pcp_free(pcp, high, batch), pcp);
        //如果pcp中page的数量大于了node中pcp page最大数量，则将多余的page放入buddy system中
	}
}

在早期的版本中，是在本函数调用的free_one_page

1
free_one_page(zone, page, pfn, 0, migratetype, FPI_NONE);
free_one_page
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void free_one_page(struct zone *zone,
				struct page *page, unsigned long pfn,
				unsigned int order,
				int migratetype, fpi_t fpi_flags)
{
	unsigned long flags;

	spin_lock_irqsave(&zone->lock, flags);
	if (unlikely(has_isolate_pageblock(zone) ||
		is_migrate_isolate(migratetype))) {
		migratetype = get_pfnblock_migratetype(page, pfn);
	}
	__free_one_page(page, pfn, zone, order, migratetype, fpi_flags);
	spin_unlock_irqrestore(&zone->lock, flags);
}

封装了__free_one_page,主要是判断迁移类型等

__free_one_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
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 的想法是为多种“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;
	//获取最大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 = page + (buddy_pfn - pfn);//page结构体

		if (!page_is_buddy(page, buddy, order))//判断是否是伙伴
            /*
            1.page与buddy在同一个zone
            2.page与buddy在同一个order
            3.page与buddy都在buddy system中
            */
			goto done_merging;//是伙伴的话就去合并，不是的话就不需要merge
		/*
		buddy(被释放页的伙伴)是空闲的或是 CONFIG_DEBUG_PAGEALLOC 保护的页,
		合并它，并放在更大的order链表中
		 */
		if (page_is_guard(buddy))
			clear_page_guard(zone, buddy, order, migratetype);//清除保护
		else
			del_page_from_free_list(buddy, zone, order);//unlink buddy
        
        //合并 重置新的pfn
		combined_pfn = buddy_pfn & pfn;
		page = page + (combined_pfn - pfn);
		pfn = combined_pfn;
		order++;
	}
	if (order < MAX_ORDER - 1) {
		/*
		如果我们在这里，则意味着 order >= pageblock_order。
		我们希望防止隔离页块和普通页块上的空闲页合并。 如果没有这个，页块隔离可能会导致不正确的 freepage 或 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:
    //设置order，同时标记为buddy system 的 page
	set_buddy_order(page, order);
    // 判断free page该插入链表头还是尾
	if (fpi_flags & FPI_TO_TAIL)
		to_tail = true;
	else if (is_shuffle_order(order))
		to_tail = shuffle_pick_tail();
	else
        //检查下一个最高阶的buddy 是否空闲
        //如果是空闲的，那么free page可能很快被合并，加入尾部 方便合并
		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);
}

参考资料

https://en.wikipedia.org/wiki/Buddy_memory_allocation

https://cloud.tencent.com/developer/article/1518174

https://zhuanlan.zhihu.com/p/502525143

https://arttnba3.cn/2022/06/30/OS-0X03-LINUX-KERNEL-MEMORY-5.11-PART-II/

https://bbs.pediy.com/thread-269149.htm#msg_header_h3_12