2. 伙伴系统原理

2.1 伙伴系统概述

伙伴系统（Buddy System）是 Linux 内核管理物理内存的核心算法，负责解决物理内存分配与回收中的外部碎片问题。它将物理内存划分为 2 的幂次方大小的连续块，通过分裂与合并操作，在分配灵活性与碎片控制之间取得平衡。

2.2 伙伴算法的核心思想

伙伴算法基于以下三个基本原则：

1. 幂次方划分：所有内存块大小均为 2^k 页（k 为 0 到 MAX_ORDER-1）。
2. 伙伴关系：两个大小相同、地址连续且由同一个更大块分裂而来的内存块互为“伙伴”。
3. 延迟合并：释放时立即检查伙伴是否空闲，若空闲则合并为更大块，并递归向上合并。

2.3 内存块分裂机制

当内核请求一个大小为 2^k 页的内存块时，分配流程如下：

1. 查找空闲链表：从 order = k 的空闲链表开始查找。
2. 向上搜索：若当前 order 链表为空，则向 order+1 链表查找。
3. 分裂操作：从更高 order 链表中取出一个块，将其分裂为两个大小相等的伙伴块。
4. 递归分裂：将其中一个伙伴块放入低一阶的链表，另一个继续分裂，直到达到目标 order。
5. 分配返回：将最终得到的 2^k 大小块返回给调用者。

2.4 内存块合并机制

当内存块被释放时，内核执行反向合并操作：

1. 检查伙伴：计算当前释放块的伙伴地址，检查伙伴是否在空闲链表中。
2. 合并条件：伙伴必须满足：大小相同、地址连续、且当前也在空闲链表中。
3. 执行合并：将两个伙伴块从当前 order 链表移除，合并为 2^k+1 大小的块。
4. 递归合并：将合并后的块放入高一阶链表，并继续检查其伙伴是否空闲。
5. 终止条件：直到伙伴不空闲或达到 MAX_ORDER-1 为止。

2.5 伙伴地址计算

伙伴地址的计算是合并操作的核心，其数学原理基于二进制地址的位操作：

/* 内核源码：mm/page_alloc.c */
static inline unsigned long
__find_buddy_pfn(unsigned long page_pfn, unsigned int order)
{
    return page_pfn ^ (1 << order);
}

/* 示例：假设 page_pfn = 0x1000, order = 2 */
/* 计算：0x1000 ^ (1 << 2) = 0x1000 ^ 0x4 = 0x1004 */
/* 伙伴 PFN 为 0x1004，即两个 4 页块互为伙伴 */

2.6 合并过程完整示例

以下展示从 order=1 块释放到合并为 order=3 块的完整流程：

2.7 伙伴系统的数据结构

Linux 内核使用 struct free_area 管理每个 order 的空闲块链表：

/* 内核源码：include/linux/mmzone.h */
struct free_area {
    struct list_head    free_list[MIGRATE_TYPES];
    unsigned long       nr_free;
};

struct zone {
    /* ... */
    struct free_area    free_area[MAX_ORDER];
    /* ... */
};

/* MAX_ORDER 默认值为 11，即最大连续块为 2^10 = 1024 页 */

2.8 性能优化要点

2.9 伙伴系统 vs 其他分配算法