2. 伙伴系统核心思想

伙伴系统（Buddy System）是 Linux 内核管理物理内存的核心算法，其设计目标是在分配与释放频繁发生的场景下，既能快速找到连续物理页，又能有效抑制外部碎片。理解伙伴系统的三个基石——伙伴定义、阶（order）与二叉树、合并与分裂规则，是掌握整个内存子系统的前提。

2.1 伙伴（Buddy）的严格定义

在伙伴系统中，两个内存块互为“伙伴”必须同时满足以下三个条件：

1. 大小相等：两个块包含的连续物理页框（page frame）数量相同，均为 2^order 页。
2. 物理地址连续：两个块在物理地址空间上紧邻，前一块的结束地址与后一块的起始地址相差一个块大小。
3. 由同一个大块分裂而来：两个块必须来自同一个大小为 2^order+1 的父块的一次分裂，且它们的物理起始地址满足“伙伴对齐”条件。

下表总结了不同阶下伙伴块的关键属性：

2.2 阶（order）与二叉树结构

伙伴系统使用阶（order）来量化内存块的大小。一个阶为 order 的块包含 2order 个连续物理页。内核维护一个以阶为索引的空闲链表数组 free_area[order]，每个链表串连该阶下所有空闲块。

从数据结构视角看，伙伴系统天然对应一棵完全二叉树：

• 根节点：代表整个管理区（zone）的最大连续内存块，阶为 MAX_ORDER-1。
• 内部节点：代表一个大小为 2^order 的块，其左子节点和右子节点互为伙伴。
• 叶子节点：阶为 0，代表单个物理页框。

下图展示了一个从 order=3（8 页）到 order=0（1 页）的伙伴二叉树结构：

2.3 内存块分裂规则

当内核请求分配 2order 个连续页时，若对应阶的空闲链表为空，则触发分裂（split）操作：

1. 向上查找：从 free_area[order] 开始，逐级检查更高阶的空闲链表，直到找到第一个非空链表 free_area[higher]。
2. 取出大块：从 free_area[higher] 链表中摘取一个空闲块。
3. 递归分裂：将大块一分为二，得到两个大小为 2higher-1 的伙伴块。
4. 插入空闲链表：将其中一个伙伴块（通常是地址较低的那个）插入 free_area[higher-1] 链表。
5. 重复：对另一个伙伴块继续分裂，直到得到目标 order 的块。
6. 返回：将最终得到的 2order 大小的块返回给调用者。

分裂过程可以用以下伪代码清晰表达：

/* 伙伴系统分裂核心逻辑（简化） */
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order)
{
    unsigned int current_order;
    struct free_area *area;
    struct page *page;

    /* 从目标 order 开始向上查找 */
    for (current_order = order; current_order < MAX_ORDER; current_order++) {
        area = &zone->free_area[current_order];
        if (list_empty(&area->free_list))
            continue;  /* 当前阶无空闲块，继续向上 */

        /* 取出第一个空闲块 */
        page = list_first_entry(&area->free_list, struct page, lru);
        list_del(&page->lru);
        area->nr_free--;

        /* 将多余部分分裂后放回低阶链表 */
        while (current_order > order) {
            current_order--;
            area = &zone->free_area[current_order];
            /* 伙伴块地址 = 当前块地址 + 2^current_order 页 */
            struct page *buddy = page + (1 << current_order);
            list_add(&buddy->lru, &area->free_list);
            area->nr_free++;
        }
        return page;
    }
    return NULL;  /* 内存不足 */
}

2.4 内存块合并规则

当内存块被释放时，内核尝试将其与伙伴块合并（coalesce），以构建更大的连续内存区域。合并是分裂的逆操作，遵循以下规则：

1. 计算伙伴地址：根据释放块的物理地址和阶 order，通过异或运算 buddy_pfn = pfn ^ (1 << order) 得到伙伴块的页框号。
2. 检查伙伴状态：确认伙伴块是否空闲且位于同一个管理区（zone），并且未被预留或隔离。
3. 从链表摘除：若伙伴空闲，将其从 free_area[order] 链表中移除。
4. 合并成大块：将释放块与伙伴块合并，形成阶为 order+1 的新块。
5. 递归尝试：以新块为起点，继续尝试向更高阶合并，直到无法合并为止。
6. 插入最终链表：将合并后的最终块插入对应阶的空闲链表。

合并操作的核心代码片段：

/* 伙伴系统合并核心逻辑（简化） */
static inline unsigned long
__free_one_page(struct page *page, unsigned long pfn,
                struct zone *zone, unsigned int order)
{
    unsigned long buddy_pfn;
    struct page *buddy;

    while (order < MAX_ORDER - 1) {
        /* 计算伙伴页框号：关键位运算 */
        buddy_pfn = pfn ^ (1 << order);
        buddy = page + (buddy_pfn - pfn);

        /* 检查伙伴是否可合并 */
        if (!page_is_buddy(page, buddy, order))
            break;  /* 伙伴不满足条件，停止合并 */

        /* 从空闲链表摘除伙伴 */
        list_del(&buddy->lru);
        zone->free_area[order].nr_free--;

        /* 合并：取两个伙伴中地址较小的作为新块起始 */
        if (buddy_pfn < pfn) {
            page = buddy;
            pfn = buddy_pfn;
        }
        order++;
    }

    /* 将合并后的块放入对应阶的空闲链表 */
    list_add(&page->lru, &zone->free_area[order].free_list);
    zone->free_area[order].nr_free++;

    return order;
}

2.5 分裂与合并的完整流程可视化

下图展示了一个从 order=2 分配 4 页，以及后续释放并触发合并的完整生命周期：

2.6 伙伴系统的核心优势与局限