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, 该字段定义如下：

MAX_ORDER 的值是 11, 也就是说，Buddy System 一次能够分配的最大连续页面是 210=1024 个，即4M的连续内存。数组 free_area 每个索引 i 存放的就是大小为 2i 页面数量的分组，这样可以提升Buddy System分配内存时查找分组的效率。数据结构 free_area 的定义如下：

free_area 中的空闲分组按照 MIGRATE_TYPES 进行了分组，每种类型都保存在一个双向链表中，这里我们将关注点放在Buddy System算法的实现上，不展开讨论 MIGRATE_TYPES.

分配内存时还需要很多标记类参数，例如指定目标 zone （是从 DMA 请求内存还是 NORMAL)、分配到的内存是否要全部置零、如果内存不足，是否可以触发内存回收机制等等，这些标记都定义在 include/linux/gfp.h 中，例如：

源文件中对每个标记位的作用都有详细的说明，这里不再一一讨论。特别指出的是，GFP是Get Free Page的简称，这些标记叫着GFP Flags, 他们控制着Buddy System分配内存时的行为。

3.2.4.3 分配内存

入口函数

涉及物理内存分配的主要代码在文件 include/linux/gpf.h 与 mm/page_alloc.c 中，本节的代码也都是摘自这两个文件。

内存分配的入口函数有很多，我们来看一个典型的入口函数申明：

函数接收两个参数，一个是 GFP Mask, 另一个用来指定页面数量：参数 order 表示需要申请 2^order 个连续页面。该函数是NUMA架构下的入口函数之一，其首先通过函数 numa_node_id 找到当前CPU所在的NUMA Node, 即定位目标 pglist_data 对象，然后调用 alloc_pages_node 函数进行内存分配。不管入口函数是哪个，最终都会调用到 __alloc_pages:

总而言之，内核在向Buddy System申请内存时需要提供如下信息：

  • 如果在NUMA架构下，需要指定目标Node

  • 页面数量

  • GFP Flags, 用来控制Buddy System的各种行为

函数 __alloc_pages_nodemask 是Buddy System 的核心，包含三部分：

  1. 准备内存分配的上下文，即初始化各种参数并将其封装到数据结构 alloc_context 中

  2. 尝试通过快速路径（fastpath）分配内存，快速路径表示系统能够直接满足内存分配请求

  3. 尝试通过慢速路径（slowpath）分配内存，表示当前系统无法满足内存分配请求，系统会暂时挂起内存分配操作，并通过回收内存、规整（compact）内存、或者通过 OOM Killer 杀死某些进程回首内存之后，再尝试内存分配操作

函数的总体逻辑如下：

后续我们将主要关注快速路径的分配逻辑。

定位目标zone

想要完成内存分配操作，首先需要找到合适的 zone. 细心的读者可以已经发现，函数 __alloc_pages 中用于指定目标 node 的参数名叫 preferred_nid, 之所以叫 preferred 的原因是当前所选择的目标 node 可能无法满足程序的内存申请，此时系统可能会尝试着从其它 node 进行分配。在讨论 2.4 的数据结构时，我们提到过每个 node 中都保存着所有 node 的所有 zone，相关字段定义如下：

数组 node_zonelists 长度通过 MAX_ZONELISTS 确定：

在NUMA架构下，该数组包含着两个列表，一个 fallback 列表一个 nofallback 列表，前者包含着系统中所有的 zone, 列表的排列顺序就是Buddy System 分配内存时选择 zone 的优先级顺序，后者仅包含当前 node 的 zone。fallback 的意思是当前 node 的 zone 无法满足要求时，是否需要使用其它 node 中的 zone 来顶替。 zonelist 就是一个 zone 的数组，Buddy System分配内存时就会遍历整个数组，从第一个合适的 zone 中分配内存，zonelist 的长度定义如下：

两个 zonelist 在系统的启动阶段进行初始化，NUMA 架构下 fallback 列表的构建逻辑是先将所有的 node 按照到当前 node 的“远近程度”排序，然后再将每个 node 的 zone 按照一定顺序排列起来。核心代码如下：

函数 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 列表：

分配内存时的遍历逻辑在函数 get_page_from_freelist 中（该函数也是快速路径分配的入口函数），通过宏 for_next_zone_zonelist_nodemask 来完成，找到合适的 zone 了之后，系统通过函数 rmqueue 来完成内存分配。

内存分配

快速路径（fastpath）下分配内存的核心逻辑在函数 rmqueue 中，函数的主体代码如下：

总体来说，函数的逻辑根据 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:

整个逻辑非常直观，就是找到当前CPU 的内存“缓存池”，然后从取出一页 migratetype 对应的内存即可。值得一提的是如果 migratetype 对应的内存列表为空，那么系统会通过 Buddy System 为该列表补充内存，该逻辑通过函数 rmqueue_bulk 完成，这里不再深入。

如果 order>0, 则通过函数 __rmqueue_smallest 从 zone 中分配内存，Buddy System 的算法实现也包含在该函数中：

函数通过 for 循环遍历 zone->free_area, 找到能够满足请求的最小的Buddy并从中分配内存，如果实际的Buddy 列表大小大于请求的 order, 则通过 expand 对其进行拆分并将未分配的内存存入对应 order 的Buddy列表中，整个算法思路与前文讨论的一样。

Previous3.2.3 物理内存模型Next3.2.5 SLAB/SLUB/SLOB

Last updated

Was this helpful?