4. 伙伴系统（Buddy System）：算法原理、内存碎片化问题、alloc_pages接口实现

伙伴系统是Linux内核物理内存管理的核心算法，负责解决物理页框的分配与释放问题。其设计目标是在满足快速分配/释放的同时，尽可能减少外部碎片。本章深入剖析伙伴算法的数学原理、碎片化挑战以及核心分配接口 alloc_pages 的实现路径。

4.1 伙伴算法原理

伙伴算法的核心思想是“以2的幂次方分割，以伙伴对合并”。系统维护一个空闲链表数组，每个索引对应一种特定大小的连续内存块（order）。

• Order（阶）：表示连续页框的数量，大小为 \(2^{order}\) 个连续页框。例如 order=0 为1页，order=3 为8页。
• 空闲链表数组：free_area[MAX_ORDER]，每个元素是一个链表，链接该 order 下所有空闲块。
• 伙伴关系：两个大小相同、地址连续且由同一个大块分裂出来的块互为伙伴。伙伴的物理地址仅相差一个块的大小。

分配过程（以 order=2 为例）：

1. 检查 free_area[2] 链表是否为空。
2. 若不为空，直接摘取一个块返回。
3. 若为空，向上一级 order=3 申请一个块，将其分裂为两个 order=2 的伙伴块。
4. 一个块返回给调用者，另一个块挂入 free_area[2] 链表。
5. 若 order=3 也为空，继续向 order=4 申请，递归进行。

释放过程：

1. 将释放的块挂回对应 order 的空闲链表。
2. 检查其伙伴是否也在同一 order 的空闲链表中。
3. 若伙伴空闲，将两个块从链表摘下，合并为一个更大的块，挂入上一级 order 链表。
4. 递归向上合并，直到无法合并为止。

4.2 内存碎片化问题

尽管伙伴系统通过合并机制缓解了外部碎片，但在长期运行的系统中，碎片化仍然不可避免。碎片化主要分为两类：

Linux内核针对碎片化采取以下对抗策略：

• 反碎片化（Anti-fragmentation）：将可移动页（MIGRATE_MOVABLE）与不可移动页（MIGRATE_UNMOVABLE）分配到不同的区域，避免不可移动页阻塞大块连续内存的形成。
• 内存规整（Memory Compaction）：通过扫描并迁移可移动页，将分散的空闲页合并为连续大块。
• 虚拟可移动区域（Virtually Movable Zone）：允许通过页表映射调整物理页的使用方式。

4.3 alloc_pages 接口实现

alloc_pages 是内核中分配物理页框的核心接口，定义在 include/linux/gfp.h 中。其原型为：

struct page *alloc_pages(gfp_t gfp_mask, unsigned int order);

参数说明：

• gfp_mask：分配标志，控制分配行为（如是否允许睡眠、是否允许I/O、从哪个内存域分配等）。
• order：请求的阶数，分配 \(2^{order}\) 个连续物理页。

返回值：成功返回第一个页框的 struct page 指针，失败返回 NULL。

调用路径（简化）：

1. alloc_pages → alloc_pages_node → __alloc_pages。
2. __alloc_pages 是伙伴系统的核心分配函数，位于 mm/page_alloc.c。
3. 内部调用 get_page_from_freelist 尝试从空闲链表直接分配。
4. 若失败，进入慢路径 __alloc_pages_slowpath，触发内存回收、规整等操作。

核心分配流程伪代码：

static inline struct page *__alloc_pages(gfp_t gfp_mask, unsigned int order)
{
    struct page *page;
    // 1. 快速路径：尝试从空闲链表直接分配
    page = get_page_from_freelist(gfp_mask, order);
    if (likely(page))
        return page;

    // 2. 慢速路径：回收、规整、重试
    page = __alloc_pages_slowpath(gfp_mask, order);
    return page;
}

static struct page *get_page_from_freelist(gfp_t gfp_mask, unsigned int order)
{
    struct zone *zone;
    struct free_area *area;
    int migratetype;

    // 遍历内存域，从最高优先级开始
    for_each_zone_zonelist(zone, zonelist, high_zoneidx) {
        // 检查内存域水位线
        if (!zone_watermark_ok(zone, order, ...))
            continue;
        // 尝试从对应order的空闲链表分配
        area = &zone->free_area[order];
        migratetype = gfpflags_to_migratetype(gfp_mask);
        page = __rmqueue(zone, order, migratetype);
        if (page)
            return page;
    }
    return NULL;
}

__rmqueue 函数是伙伴系统分裂操作的具体实现：

static inline struct page *__rmqueue(struct zone *zone, unsigned int order,
                                     int migratetype)
{
    struct free_area *area;
    unsigned int current_order;
    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[migratetype]))
            continue;

        // 摘取一个空闲块
        page = list_entry(area->free_list[migratetype].next,
                          struct page, lru);
        list_del(&page->lru);
        // 更新zone统计信息
        zone->free_area[current_order].nr_free--;

        // 如果找到的块比请求的大，进行分裂
        if (current_order != order)
            expand(zone, page, order, current_order, migratetype);

        return page;
    }
    return NULL;
}

expand 函数负责将大块分裂为小块，并将多余的伙伴块挂入对应 order 的空闲链表：

static inline void expand(struct zone *zone, struct page *page,
                          int low, int high, int migratetype)
{
    unsigned long size = 1 << high;
    while (high > low) {
        high--;
        size >>= 1;
        // 将伙伴块加入空闲链表
        list_add(&page[size].lru, &zone->free_area[high].free_list[migratetype]);
        zone->free_area[high].nr_free++;
        // 设置伙伴块的order信息
        set_page_order(&page[size], high);
    }
}