# 3.2.4 Buddy System(伙伴系统)
## 3.2.4.1 算法思路
对于内存管理，一个最基础的需求就是对连续内存页面的分配与释放，而在对内存页面的分配与释放过程中，需要解决的一个重要问题就是如何避免内存出现大量的碎片。例如对于一个有4个页面的系统，系统发起了两次请求，每次申请一个页面，系统可以有如下两种分配策略：
在方案一中，剩下的两个页面被隔离开了，如果系统接下来想要申请两个连续页面，那么请求就会失败；而方案二中，被分配的两个页面是挨着的，系统还可以成功地申请两个连续的页面。不管实际上物理内存页面的数量如何，一个优秀的内存分配器都应该采用方案二这种方式来工作，尽可能地将可用页面保留成连续的区域。
> 这种碎片被称为外部碎片（External Fragmentation），与之相对应的是内部碎片（Internal Fragmentation），指在页内分配对象时造成的浪费，这在后续介绍Slab Allocator时会提及。
Linux内核使用Buddy System来负责连续页面的分配与释放，内核将连续的内存页面按照固定的数量进行分组，对于任何一个分组，合法的页面数量是 `2^n` 且 `0<=n<=10`, 大小相等且相邻的两个分组是彼此的Buddy, 例如下图中，当 `n=1` 时，组的页面数量是2, 此时 Group 1 与 Group 2 互为Buddy, 但Group 1 与 Group 3 由于隔开了，就不是Buddy.
我们定义Buddy这个概念的目的是在内存分配与释放的过程中，能够动态地维护尽可能长的连续内存。例如上图中，如果 Group1 与 Group 2 都被释放回来后，系统就将会对两个Buddy进行合并，形成一个数量更大的组Group 4, 这也是两个Buddy必须相邻的原因。在分配内存时，Buddy System 会首先根据请求的页面数量确定目标分组，如果请求的连续内存数量是k, 那么Buddy System 将选择满足 `2^n >= k` 的最小的数字n 对应的那个分组，如果Buddy System 中没有对应的分组，那么系统将会将更大的分组劈开形成一对Buddy, 然后看劈开后的分组是否适合，如果不行的话就继续劈开，直到到达合适的大小为止。下图演示了一个Buddy System 从64页连续内存中分配8页的过程：
系统本来只有一个64 页的分组，完成此次分配之后，系统中可用的分组如下：一个8页分组、一个16页分组、以及一个32页的分组，即图中红色方框的部分。由于每个分组的页数都满足 `2^n`, 为了避免分配页面时出现碎片，Buddy System要求分配时请求的页面数量也必须满足 `2^n` 的数字大小，如果实际请求的数字 k 不满足2的n次方的话，Buddy System会分配大于等于 k 的最小的2的某次方的那个数字进行分配，例如如果系统请求的页面数量是7, 那么系统实际上会分配8个页面。
当释放内存时，Buddy System 会查看释放分组的Buddy 是否空闲，如果空闲的话便会合并两个分组形成一个更大的分组，并递归该操作直到当前分组的Buddy 繁忙（指被分配出去还未释放）或已经形成最大数量的分组为止。例如上图中，如果系统释放刚刚分配回去的8 个页面的话，Buddy System 又会自底向上地合并所有的分组，最终又形成一个64页的分组。
> 由此可知，图2中的Group 2与 Group 3虽然数量相等且相邻，但他们并不是Buddy, 根据Buddy System 中对于分组数量的规定，两个分组如何可合并的话，那么第一个分组的首地址必然是合并后组内页面数量的整数倍。如果将Group 2与Group 3合并，将得到一个页数是4的分组，因此Group 2的起始地址应该是4的整数倍，但Group 2的起始地址是2, 因此Group 2与Group 3不会有合并的机会。
Buddy System是内存管理的基础，其分配的对象的连续的物理页面，这是一个比较大的粒度，内核会在Buddy System 之上构建更加精细的内存分配机制提供给程序使用，这就是后续将要介绍的Slab系统。
## 3.2.4.2 数据结构
Buddy System从 `zone` 中分配内存，zone 中使用一个数组来管理不同大小的Buddy, 该字段定义如下：
```
/* file: include/linux/mmzone.h */
struct zone {
/* free areas of different sizes */
struct free_area free_area[MAX_ORDER];
}
```
`MAX_ORDER` 的值是 11, 也就是说，Buddy System 一次能够分配的最大连续页面是 210=1024 个，即4M的连续内存。数组 `free_area` 每个索引 i 存放的就是大小为 2i 页面数量的分组，这样可以提升Buddy System分配内存时查找分组的效率。数据结构 `free_area` 的定义如下：
```
/* file: include/linux/mmzone.h */
struct free_area {
struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free;
};
```
`free_area` 中的空闲分组按照 `MIGRATE_TYPES` 进行了分组，每种类型都保存在一个双向链表中，这里我们将关注点放在Buddy System算法的实现上，不展开讨论 `MIGRATE_TYPES`.
分配内存时还需要很多标记类参数，例如指定目标 `zone` （是从 DMA 请求内存还是 NORMAL)、分配到的内存是否要全部置零、如果内存不足，是否可以触发内存回收机制等等，这些标记都定义在 `include/linux/gfp.h` 中，例如：
```
/* file: include/linux/gfp.h */
#define ___GFP_DMA 0x01u
#define ___GFP_HIGHMEM 0x02u
#define ___GFP_DMA32 0x04u
#define ___GFP_MOVABLE 0x08u
#define ___GFP_RECLAIMABLE 0x10u
#define ___GFP_HIGH 0x20u
#define ___GFP_IO 0x40u
#define ___GFP_FS 0x80u
#define ___GFP_ZERO 0x100u
#define ___GFP_ATOMIC 0x200u
/* 通过位运算将不同的标记组合起来 */
#define GFP_ATOMIC (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM)
#define GFP_KERNEL (__GFP_RECLAIM | __GFP_IO | __GFP_FS)
#define GFP_KERNEL_ACCOUNT (GFP_KERNEL | __GFP_ACCOUNT)
#define GFP_NOWAIT (__GFP_KSWAPD_RECLAIM)
```
源文件中对每个标记位的作用都有详细的说明，这里不再一一讨论。特别指出的是，GFP是Get Free Page的简称，这些标记叫着GFP Flags, 他们控制着Buddy System分配内存时的行为。
## 3.2.4.3 分配内存
### **入口函数**
> 涉及物理内存分配的主要代码在文件 `include/linux/gpf.h` 与 `mm/page_alloc.c` 中，本节的代码也都是摘自这两个文件。
内存分配的入口函数有很多，我们来看一个典型的入口函数申明：
```
/* file: include/linux/gfp.h */
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, 另一个用来指定页面数量：参数 `order` 表示需要申请 `2^order` 个连续页面。该函数是NUMA架构下的入口函数之一，其首先通过函数 `numa_node_id` 找到当前CPU所在的NUMA Node, 即定位目标 `pglist_data` 对象，然后调用 `alloc_pages_node` 函数进行内存分配。不管入口函数是哪个，最终都会调用到 `__alloc_pages`:
```
/* file: include/linux/gfp.h */
static inline struct page *
__alloc_pages(gfp_t gfp_mask, unsigned int order, int preferred_nid)
{
return __alloc_pages_nodemask(gfp_mask, order, preferred_nid, NULL);
}
```
总而言之，内核在向Buddy System申请内存时需要提供如下信息：
* 如果在NUMA架构下，需要指定目标Node
* 页面数量
* GFP Flags, 用来控制Buddy System的各种行为
函数 `__alloc_pages_nodemask` 是Buddy System 的核心，包含三部分：
1. 准备内存分配的上下文，即初始化各种参数并将其封装到数据结构 `alloc_context` 中
2. 尝试通过快速路径（fastpath）分配内存，快速路径表示系统能够直接满足内存分配请求
3. 尝试通过慢速路径（slowpath）分配内存，表示当前系统无法满足内存分配请求，系统会暂时挂起内存分配操作，并通过回收内存、规整（compact）内存、或者通过 [OOM](https://en.wikipedia.org/wiki/Out_of_memory) Killer 杀死某些进程回首内存之后，再尝试内存分配操作
函数的总体逻辑如下：
```
/* file: mm/page_alloc.c */
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; /* The gfp_t that was actually used for allocation */
struct alloc_context ac = {};
/* 1. 第一步，准备内存分配的上下文 */
if (!prepare_alloc_pages(gfp_mask, order, preferred_nid, nodemask, &ac,
&alloc_mask, &alloc_flags))
return NULL;
/* 2. 快速路径分配内存 */
page = get_page_from_freelist(alloc_mask, order, alloc_flags, &ac);
if (likely(page))
/* 如果快速路径分配成功，则直接返回 */
goto out;
/* 3. 慢速路径分配内存 */
page = __alloc_pages_slowpath(alloc_mask, order, &ac);
out:
return page;
}
```
后续我们将主要关注快速路径的分配逻辑。
### **定位目标zone**
想要完成内存分配操作，首先需要找到合适的 zone. 细心的读者可以已经发现，函数 `__alloc_pages` 中用于指定目标 node 的参数名叫 `preferred_nid`, 之所以叫 `preferred` 的原因是当前所选择的目标 node 可能无法满足程序的内存申请，此时系统可能会尝试着从其它 node 进行分配。在讨论 [2.4](broken://pages/bMTqTlFBUUs5tpuZ1t5Q) 的数据结构时，我们提到过每个 node 中都保存着所有 node 的所有 zone，相关字段定义如下：
```
/* file: include/linux/mmzone.h */
typedef struct pglist_data {
/*
* node_zonelists contains references to all zones in all nodes.
* Generally the first zones will be references to this node's
* node_zones.
*/
struct zonelist node_zonelists[MAX_ZONELISTS];
}
/*
* One allocation request operates on a zonelist. A zonelist
* is a list of zones, the first one is the 'goal' of the
* allocation, the other zones are fallback zones, in decreasing
* priority.
*
* To speed the reading of the zonelist, the zonerefs contain the zone index
* of the entry being read. Helper functions to access information given
* a struct zoneref are
*
* zonelist_zone() - Return the struct zone * for an entry in _zonerefs
* zonelist_zone_idx() - Return the index of the zone for an entry
* zonelist_node_idx() - Return the index of the node for an entry
*/
struct zonelist {
struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1];
};
/*
* This struct contains information about a zone in a zonelist. It is stored
* here to avoid dereferences into large structures and lookups of tables
*/
struct zoneref {
struct zone *zone; /* Pointer to actual zone */
int zone_idx; /* zone_idx(zoneref->zone) */
};
```
数组 `node_zonelists` 长度通过 `MAX_ZONELISTS` 确定：
```
/* file: include/linux/mmzone.h */
enum {
ZONELIST_FALLBACK, /* zonelist with fallback */
#ifdef CONFIG_NUMA
/*
* The NUMA zonelists are doubled because we need zonelists that
* restrict the allocations to a single node for __GFP_THISNODE.
*/
ZONELIST_NOFALLBACK, /* zonelist without fallback (__GFP_THISNODE) */
#endif
MAX_ZONELISTS
};
```
在NUMA架构下，该数组包含着两个列表，一个 `fallback` 列表一个 `nofallback` 列表，前者包含着系统中所有的 zone, 列表的排列顺序就是Buddy System 分配内存时选择 zone 的优先级顺序，后者仅包含当前 node 的 zone。fallback 的意思是当前 node 的 zone 无法满足要求时，是否需要使用其它 node 中的 zone 来顶替。 `zonelist` 就是一个 zone 的数组，Buddy System分配内存时就会遍历整个数组，从第一个合适的 zone 中分配内存，zonelist 的长度定义如下：
```
/* file: include/linux/mmzone.h */
/* zonelist 的最大长度，node 数量乘以每个 node 的分区数量，用于存放整个 fallback 列表 */
#define MAX_ZONES_PER_ZONELIST (MAX_NUMNODES * MAX_NR_ZONES)
```
两个 zonelist 在系统的启动阶段进行初始化，NUMA 架构下 fallback 列表的构建逻辑是先将所有的 node 按照到当前 node 的“远近程度”排序，然后再将每个 node 的 zone 按照一定顺序排列起来。核心代码如下：
```
/* file: mm/page_alloc.c */
/*
* Build zonelists ordered by zone and nodes within zones.
* This results in conserving DMA zone[s] until all Normal memory is
* exhausted, but results in overflowing to remote node while memory
* may still exist in local DMA zone.
*/
static void build_zonelists(pg_data_t *pgdat)
{
static int node_order[MAX_NUMNODES];
int node, load, nr_nodes = 0;
nodemask_t used_mask = NODE_MASK_NONE;
int local_node, prev_node;
/* NUMA-aware ordering of nodes */
local_node = pgdat->node_id;
load = nr_online_nodes;
prev_node = local_node;
memset(node_order, 0, sizeof(node_order));
/* find_next_best_node 会寻找下一个距离 local_node 最近的 node */
while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
/*
* We don't want to pressure a particular node.
* So adding penalty to the first node in same
* distance group to make it round-robin.
*/
if (node_distance(local_node, node) !=
node_distance(local_node, prev_node))
node_load[node] = load;
node_order[nr_nodes++] = node;
prev_node = node;
load--;
}
build_zonelists_in_node_order(pgdat, node_order, nr_nodes);
build_thisnode_zonelists(pgdat);
}
```
函数 `find_next_best_node` 会寻找下一个距离 localnode 最近的 node, 这样通过 while 循环就可以将所有的 node 按照“距离（Distance）”排好序。“距离（Distance）”是NUMA架构下CPU访问其它节点的内存耗时的一个度量单位，两个CPU 节点距离越远，访问起来越耗时，因此构建 fallback 列表时，需要按照距离由近到远对所有的 node 进行排序。例如下图中，三个CPU 的 fallback 顺序依次是：
* Node 1: 1 -> 2 -> 3
* Node 2: 2 -> 1 -> 3
* Node 3: 3 -> 1 -> 2
对 node 排好序之后，通过函数 `build_zonelists_in_node_order` 来构建当前 node 的 fallback 列表：
```
/* file: mm/page_alloc.c */
static void build_zonelists_in_node_order(pg_data_t *pgdat, int *node_order,
unsigned nr_nodes)
{
struct zoneref *zonerefs;
int i;
/* 拿到当前 node 的 fallback 列表 */
zonerefs = pgdat->node_zonelists[ZONELIST_FALLBACK]._zonerefs;
for (i = 0; i < nr_nodes; i++) {
int nr_zones;
/* 获取到对应的 node */
pg_data_t *node = NODE_DATA(node_order[i]);
/* 将 node 中的各个分区按照由高到低的顺序放入 zonerefs 中，放入顺序为：Movable -> Normal -> DMA */
nr_zones = build_zonerefs_node(node, zonerefs);
zonerefs += nr_zones;
}
zonerefs->zone = NULL;
zonerefs->zone_idx = 0;
}
```
分配内存时的遍历逻辑在函数 `get_page_from_freelist` 中（该函数也是快速路径分配的入口函数），通过宏 `for_next_zone_zonelist_nodemask` 来完成，找到合适的 `zone` 了之后，系统通过函数 `rmqueue` 来完成内存分配。
### **内存分配**
快速路径（fastpath）下分配内存的核心逻辑在函数 `rmqueue` 中，函数的主体代码如下：
```
/* file: mm/page_alloc.c */
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)) {
/* 对于 order=0 的情况，尝试从 per_cpu_pageset 中分配内存 */
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;
}
}
/* 访问 zone 时需要加锁 */
spin_lock_irqsave(&zone->lock, flags);
do {
page = NULL;
if (order > 0 && alloc_flags & ALLOC_HARDER) {
/* 从 zone 的free area中分配内存，free area 就是Buddy System 中用来存放各种 order 的内存页面的地方 */
page = __rmqueue_smallest(zone, order,
MIGRATE_HIGHATOMIC);
}
/* 如果还没有分配到内存，则尝试通过 fallback 列表分配内存 */
if (!page)
page = __rmqueue(zone, order, migratetype, alloc_flags);
} while (page && check_new_pages(page, order));
/* 释放锁 */
spin_unlock(&zone->lock);
if (!page)
goto failed;
local_irq_restore(flags);
out:
return page;
failed:
local_irq_restore(flags);
return NULL;
}
```
总体来说，函数的逻辑根据 order 的大小分为两部分：
1. 当order = 0, 即申请的内存页数等于1时，系统会从每个CPU的缓存页面中分配内存
2. 当order > 0, 即申请的内存页数大于1时，系统会从 zone 中分配内存
之所以这样区别对待，是因为 `zone` 是共享的数据结构，在多核系统中会面临巨大的竞争，通过代码也可以发现，当通过 zone 分配内存时需要对 zone->lock 加锁。而根据实际经验，人们发现系统对于 order=0 的内存分配请求是出现频次最高的，为了提升性能，系统就为每个CPU 建立了一个“缓存池”，也就是前文讨论 `zone` 的数据结构时提到的字段 `struct per_cpu_pageset __percpu *pageset;`, 内核将其称为 pcplist, 即 per cpu pages list, 从 pcplist 分配内存的函数是 `rmqueue_pcplist`:
```
/* file: mm/page_alloc.c */
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);
/* 获取到当前CPU 的 pageset */
pcp = &this_cpu_ptr(zone->pageset)->pcp;
/* 拿到 pageset 中对应类型的内存列表 */
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;
}
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 {
/* 如果目标列表为空，则通过 Buddy System 为该列表补充内存，然后再进行分配 */
if (list_empty(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;
}
```
整个逻辑非常直观，就是找到当前CPU 的内存“缓存池”，然后从取出一页 migratetype 对应的内存即可。值得一提的是如果 migratetype 对应的内存列表为空，那么系统会通过 Buddy System 为该列表补充内存，该逻辑通过函数 `rmqueue_bulk` 完成，这里不再深入。
如果 order>0, 则通过函数 `__rmqueue_smallest` 从 zone 中分配内存，Buddy System 的算法实现也包含在该函数中：
```
/* file: mm/page_alloc.c */
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]);
/* include/linux/mmzone.h: 作用是从 area->free_list[migratetype] 列表中拿到第一个元素，也就是一个连续 2^order 个物理页面 */
page = get_page_from_free_area(area, migratetype);
/* 如果没有对应大小的free list, 则尝试下一个 order 的列表 */
if (!page)
continue;
del_page_from_free_list(page, zone, current_order);
/* 如果 order ！= current_order, 则需要按照Buddy Algorithm将更大的连续内存劈开成更小的Buddy并插入到对应的 free area 列表中，该逻辑在 expand 函数中完成 */
expand(zone, page, order, current_order, migratetype);
set_pcppage_migratetype(page, migratetype);
return page;
}
return NULL;
}
```
函数通过 for 循环遍历 `zone->free_area`, 找到能够满足请求的最小的Buddy并从中分配内存，如果实际的Buddy 列表大小大于请求的 order, 则通过 `expand` 对其进行拆分并将未分配的内存存入对应 order 的Buddy列表中，整个算法思路与前文讨论的一样。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://s3.shizhz.me/linux-mm/3.2-wu-li-nei-cun/3.2.4-buddy-system-huo-ban-xi-tong.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.