浅析Buddy算法

共计 3632 个字符，预计需要花费 10 分钟才能阅读完成。

目前，内核中的 Buddy 算法采用下图的方式管理内存。我把 Buddy 算法分为如下图所示的三部分，在区域一中，核心的数据结构是 struct zone；在区域二中核心的数据结构是 struct free_area free_area[MAX_ORDER]；在区域三中，page 链表是核心内容。接下来，我将详细介绍这三个板块，并通过分配函数来说明 Buddy 的工作细节。

通常用 zone 代表不同的内存管理区，即把内存划分成不同的组，每个组就是一个 zone。

在内核中，每个 zone 通过结构体 struct zone 来表示，其结构体中主要成员如下：

struct zone {unsigned long watermark[NR_WMARK];

unsigned long   zone_start_pfn;    
unsigned long   managed_pages;     
unsigned long   spanned_pages;     
unsigned long   present_pages;
struct free_area  free_area[MAX_ORDER];
const char  *name;
struct pglist_data  *zone_pgdat;
}

标识内存水线的成员 unsigned long watermark[NR_WMARK]，其中 NR_WMARK 定义如下：

enum zone_watermarks {
  WMARK_MIN,
  WMARK_LOW,
  WMARK_HIGH,
  NR_WMARK
};

从上面定义可知，每个 zone 存在三个水线，若当前 zone 中空闲页高于 WMARK_HIGH，则当前 zone 区的空闲内存较多；若空闲页低于 WMARK_LOW，则交换守护进程开始将内存交换到磁盘上；若空闲页低于 WMARK_MIN，则内存回收系统还需要大量回收内存。在使用 Buddy 进行内存申请时，会进行水线判断，从而进行相应的操作；

伙伴系统管理相关的成员

unsigned long   zone_start_pfn;    
unsigned long   managed_pages;     
unsigned long   spanned_pages;     
unsigned long   present_pages;
struct free_area  free_area[MAX_ORDER]

前四个是相应 zone 区对应的页号信息，free_area 是伙伴算法中的关键成员，也是区域一和区域二衔接的关键成员，每个 zone 区会划分为 MAX_ORDER 个组，数组 free_area 中的每个成员就代表一个组。

成员 const char *name 指明了对应 zone 区的名称，通常情况下为 dma，Normal 或 highmem，其中 highmem 不会出现在 64 位的系统中；下面是典型的 32 位系统中的 zone 划分方式：
ZONE_DMA(0～16M)：DMA 内存分配区；

ZONE_NORMAL(16MB～896MB)：普通映射的内存区域；

ZONE_HIGHMEM(896MB~)：高端内存区域，其中的页不能永久映射到内核地址空间；内核一般不使用，如果要使用，通过 kmap 做动态映射；

指向 zone 区对应 node 的指针成员 struct pglist_data *zone_pgdat，node 是内存管理中的一个重要成员。对于 UMA 架构，仅有一个 node，所有的 zone 均属于同一个 node，但对于 NUMA 架
构，会有多个不同的 node，每个 node 又划分为不同的 zone，所有 zone 区也是通过 struct pglist_data 组织在一起的。

在内存管理和分配过程中，有一个重要参数 order，当我们采用 kmalloc 申请大内存时，最后会调用函数__alloc_pages_nodemask 来进行内存申请。该函数需要一个参数 order，当 order = 0 时，表示要申请的内存大小是 1（20）个页面；当 order = 1 时，表示要申请的内存大小是 2（21）个页面。

在 Buddy 算法中，把内存按照 2 的幂次方 (即 2order，order 的范围从 0 到 MAX_ORDER) 划分成不同的组，每个组分别用对应的 free_area[order]表示，例如 free_area[0]对应的就是由内存块大小为 20 个页块组成的组，free_area[1]对应的就是由内存块大小为 21 个页块组成的组，而结构体 struct zone 正是通过成员 free_area 把图 1 中的区域一和区域二串联在一起。

结构体 struct free_area 定义如下（不同平台或者不同内核会有差异，但核心思想相同）：

struct free_area {struct list_head  free_list[MIGRATE_TYPES];
  unsigned long   nr_free;
 };

从该结构可以看出，每一个 free_area 又根据 MIGRATE_TYPES 划分为不同的组，每组分别通过链表 free_list 把同一类页块串联在一起，这样 free_list 就把图 1 中的区域二和区域三串联在一起了，从而间接的把区域一和区域三关联在一起了。

结构体 struct page 比较复杂，其中有一个成员 struct list_head lru，通过该成员把图 1 中区域三中的页块同区域二中对应的 free_list 链接在一起。

在此，我将通过一个示例来简要地展示 Buddy 内存分配的核心思想。当通过 Buddy 分配一个物理页 (即 order = 0) 时，会从对应 zone 区中 free_area[0]管理的区域分配一个页面（暂时先不考虑 PCP 的情况），并将该页面从 free_area[0] 链表中移除；当 free_area[0] 上没有可用的物理页时，Buddy 会在 free_area[1]上查找，若存在可用的物理页，则将该页块从 free_area[1] 的链表中移除，同时把该页块拆分成两块，其中一块插入到 free_area[0]中，另一块传递给内存请求者；倘若 free_area[1]上也没有可用页，则会继续向上查找。

下图 2 所示是没有对应 oder = 0 的页块情况，因此把 order = 1 中的一个页块进行拆分，一半返回给 order = 1 的链表，一半返回给请求者。假如 order = 1 中没有需要的页块，在内存分配过程中会继续从 order = 3 中进行查找，直到找到页块或者遍历完所有 order。

实际上，在整个内存分配过程中，会伴随很多特殊情况处理。Buddy 算法在进行内存分配时，会根据水线设置，来进行内存回收或者唤醒内核线程 kswapd，或者是采用 CPU 的冷热页面队列进行内存分配，或者是进行页面移动等。假如已经尝试页面移动，kswapd 已经唤出了一些页面，同时也进行了内存回收，依然没有可分配的内存，此时就会触发 out_of_memory。总之，这些特殊情况的处理方式均离不开图 1 所示的 Buddy 框架。

下图是我根据我本地的代码整理的采用 kmalloc 申请大内存时的调用过程(使用 kmalloc 申请小内存时不通过 Buddy)，其中最关键的内存分配函数是 prepare_alloc_pages，get_page_from_freelist，rmqueue 和__alloc_pages_slowpath。感兴趣的朋友可以结合图 1 所示的框架查看这几个函数的具体实现。

当向系统释放一个物理页的时候，会通过 struct page 来推导出该 page 对应的 zone 区 (比如该 page 属于 NORMAL 区) 和对应的 page 类型，紧接着将根据对应的 order 进行页的合并 (即图 1 中区域三的部分进行合并)，最后将合并后的块插入到新的 order 中去，这个合并过程一直持续下去，直到不能合并或者已经合并到最大的 order 处。例如当释放的物理页得到其属于 NORMAL 区的 free_area[0]，此时 free_area[0] 中存在页面可以和释放的页面合并，从而把合并后的添加到 free_area[1]中，这个合并操作会一直持续下去，直到合并完为止。这个过程实际上就是图 2 的反过程。

内存的管理比较复杂，本文主要介绍了 Buddy 的核心思想，但这仅仅是内存管理的冰山一角，却是比较基础且核心的内容，因此了解 Buddy 整体架构是非常有必要的。

作者介绍
赵青窕，51CTO 社区编辑，从事多年驱动开发。研究兴趣包含安全 OS 和网络安全领域，发表过网络相关专利。

阿里云 2 核 2G 服务器 3M 带宽 61 元 1 年，有高配

腾讯云新客低至 82 元 / 年，老客户 99 元 / 年

代金券：在阿里云专用满减优惠券