# 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](https://s3.shizhz.me/linux-mm/3.2-wu-li-nei-cun/broken-reference) 的数据结构时，我们提到过每个 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列表中，整个算法思路与前文讨论的一样。