3. Buddy 分配器核心思想：伙伴算法原理、2 的幂次阶分配、合并与分裂机制

Buddy（伙伴）分配器是 Linux 内核物理内存管理的基石，负责管理连续物理页框的分配与释放。其核心设计围绕 伙伴算法、2 的幂次阶分配 以及 合并与分裂机制 展开，旨在以极低的开销解决外部碎片问题。

3.1 伙伴算法原理

伙伴算法的基本思想是将物理内存划分为固定大小的块（页框），并通过一种特定的“伙伴”关系来管理这些块的合并与分裂。两个内存块互为“伙伴”需满足以下三个条件：

1. 大小相等：两个块的大小必须相同。
2. 物理地址连续：两个块在物理地址空间上是相邻的。
3. 由同一个更大的块分裂而来：它们必须是由同一个父块通过一次分裂操作产生的。

基于此关系，Buddy 分配器维护一个由 free_area 结构体组成的数组，每个数组项对应一个 阶（order），管理该阶下所有空闲的连续页框块。

3.2 2 的幂次阶分配

Buddy 分配器只分配大小为 2^order 个连续页框的内存块。当内核请求分配 n 个页框时，分配器会将其向上取整到最接近的 2 的幂次，即 order = ceil(log2(n))。

3.3 分裂与合并机制

Buddy 分配器的核心操作分为 分配（分裂） 和 释放（合并） 两个方向。

3.3.1 分配过程：向上分裂

当请求一个特定阶 order 的块时：

1. 查找：从 free_area[order] 开始查找空闲链表。
2. 分裂：如果当前阶没有空闲块，则向上一阶 order+1 查找。找到后，将该块从高阶链表中移除，并分裂成两个大小相等的伙伴块。
3. 下放：将分裂出的两个伙伴块中，一个放入当前阶 order 的空闲链表，另一个继续用于分配或进一步分裂。
4. 递归：重复步骤 2-3，直到找到满足请求的阶。

3.3.2 释放过程：向下合并

当释放一个阶 order 的块时：

1. 查找伙伴：计算该块的伙伴地址。伙伴地址可以通过对块起始地址的对应位进行异或操作得到。
2. 检查伙伴状态：检查伙伴块是否也在 free_area[order] 的空闲链表中，且未被分配。
3. 合并：如果伙伴空闲，则将两者从链表中移除，合并成一个大小为 2^order+1 的块。
4. 递归：将合并后的块视为一个整体，递归地尝试向更高阶 order+1 合并。
5. 插入：当无法继续合并时，将最终块插入到对应阶的空闲链表中。

3.4 核心数据结构与接口

Buddy 分配器的核心数据结构是 struct zone 中的 free_area 数组。Linux 内核定义了最大阶 MAX_ORDER（通常为 11），因此支持从 2⁰（1 页）到 2¹⁰（1024 页）的连续内存分配。

// 核心分配与释放接口 (简化)
struct page *alloc_pages(gfp_t gfp_mask, unsigned int order);
void free_pages(unsigned long addr, unsigned int order);

// 内部实现依赖于伙伴算法
static inline struct page *__rmqueue(struct zone *zone, unsigned int order) {
    // 1. 从 free_area[order] 开始查找
    // 2. 若为空，则向高阶查找并分裂
    // 3. 返回分配的内存块
}

static inline void __free_pages(struct page *page, unsigned int order) {
    // 1. 计算伙伴地址
    // 2. 检查伙伴是否空闲
    // 3. 若空闲则合并，并递归向上
    // 4. 将最终块插入 free_area
}

3.5 伙伴算法优缺点总结