📚 课程目录第4章伙伴系统算法

4. 伙伴系统算法

伙伴系统，这个名字听起来挺有江湖气的。说白了，它就是一套管理物理内存的算法，专门解决“大块内存怎么分配、小块内存怎么回收”的问题。我刚开始接触内核源码时，看到伙伴系统那堆链表和位图，说实话有点懵。但后来自己动手调过几次内存碎片问题后，才真正体会到这设计的精妙之处。

4.1 伙伴系统的设计思想：二分法的艺术

伙伴系统的核心思想，其实就四个字：二分递归。把一整块内存不断对半切，直到切出合适的大小。你想想看，这就像切蛋糕——来了个客人要小块，你就切一小块给他；客人走了，再把小块合并回大块。

具体来说，伙伴系统把内存按2的幂次方划分成块。比如2^0、2^1、2^2……一直到2^MAX_ORDER。每个大小级别都有一个空闲链表。分配时从合适大小的链表里取，没有就向上找更大的块，然后分裂。

  关键概念： 两个大小相同、地址连续的块互为“伙伴”。它们可以合并成一个更大的块。

举个例子。假设系统有1MB内存，按2^0=4KB为最小块。来了个请求要8KB，系统就从2^1（8KB）的链表里找。没有？那就从2^2（16KB）里拿一块，分裂成两个8KB的伙伴。一个给你用，另一个挂回8KB链表。

我当年在嵌入式项目里遇到过一个问题：频繁分配释放小内存，导致大量碎片。后来改用伙伴系统管理一块专用内存池，碎片率直接降了60%。嗯，这就是二分法的好处——天然抗碎片。

4.2 内存块合并与分裂：核心操作详解

分裂和合并，是伙伴系统的两个基本操作。咱们一个一个说。

4.2.1 分裂过程

分裂就是把一个大块切成两个小块。但这里有个关键：必须保证两个小块互为伙伴。什么叫互为伙伴？就是它们地址连续，且大小相同。

假设我们有一个大小为2^n的块，起始地址为addr。分裂后得到两个大小为2^(n-1)的块：

块A：起始地址 addr，大小 2^(n-1)
块B：起始地址 addr + 2^(n-1)，大小 2^(n-1)

块A和块B就是伙伴。它们可以合并回原来的大块。

我的经验： 分裂时要注意地址对齐。我曾经在移植Linux内核到新平台时，发现伙伴系统分配的内存地址不对齐，导致DMA传输失败。查了两天才发现是伙伴系统的起始地址没按最大块对齐。

4.2.2 合并过程

合并是分裂的逆操作。当两个伙伴块都空闲时，就把它们合并成一个更大的块。合并的条件很严格：

两个块大小必须相同
两个块地址必须连续
两个块必须互为伙伴（即地址满足特定关系）

合并时，系统会检查伙伴块是否空闲。如果是，就从当前链表摘下两个块，合并后挂到上一级链表。然后继续向上检查，看能不能继续合并。这个过程叫递归合并。

我曾经在调试一个内存泄漏问题时，发现伙伴系统合并不成功。原因是某个块被错误标记为“已分配”。嗯，从那以后我写内存管理代码时，都会特别小心状态标记的同步。

4.3 Linux中的实现：从源码角度看伙伴系统

Linux内核的伙伴系统实现，主要在 mm/page_alloc.c 里。核心数据结构是 struct free_area：

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

每个 free_area 对应一个大小级别（order）。free_list 是空闲块链表，按迁移类型（MIGRATE_TYPES）分类。为什么要分类？因为不同用途的内存页，迁移成本不一样。比如不可移动的页（内核分配）和可移动的页（用户空间），分开管理能减少碎片。

分配函数是 __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;

    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);
        // 如果分配的块比请求的大，就分裂
        if (current_order != order)
            expand(zone, page, order, current_order, migratetype);
        return page;
    }
    return NULL;
}

你看，它从请求的order开始向上找，找到第一个非空链表。取出一块后，如果比请求的大，就调用 expand() 分裂。

释放函数是 __free_one_page()，合并逻辑在这里：

static inline void __free_one_page(struct page *page,
    unsigned long pfn, struct zone *zone, unsigned int order,
    int migratetype)
{
    unsigned long page_idx = pfn;
    unsigned long combined_idx;
    unsigned long buddy_idx;
    struct page *buddy;

    while (order < MAX_ORDER-1) {
        buddy_idx = __find_buddy_index(page_idx, order);
        buddy = page + (buddy_idx - page_idx);

        if (!page_is_buddy(buddy, order, migratetype))
            break;

        // 合并伙伴
        list_del(&buddy->lru);
        combined_idx = buddy_idx & page_idx;
        page = page + (combined_idx - page_idx);
        page_idx = combined_idx;
        order++;
    }
    // 挂到空闲链表
    set_page_order(page, order);
    list_add(&page->lru,
             &zone->free_area[order].free_list[migratetype]);
}

这里有个关键函数 __find_buddy_index()，它计算伙伴块的索引。公式很简单：

static inline unsigned long
__find_buddy_index(unsigned long page_idx, unsigned int order)
{
    return page_idx ^ (1 << order);
}

用异或操作找伙伴，这设计太巧妙了。为什么？因为伙伴块的地址，就是在第order位上取反。比如order=0时，伙伴就是相邻页；order=1时，伙伴就是隔一页的块。

注意： 伙伴系统只管理连续物理内存。对于非连续内存（如vmalloc区域），它管不了。另外，伙伴系统的最小单位是页（通常4KB），更小的内存分配由slab分配器处理。

4.4 伙伴系统的优缺点

优点	缺点
分配和释放速度快（O(1)复杂度）	内部碎片：分配2^n大小，实际可能用不完
天然抗外部碎片	对非2的幂次大小不友好
实现简单，易于验证	大块内存分配可能失败（需要合并）
支持多种迁移类型	内存热插拔时处理复杂

我个人觉得，伙伴系统最大的优点是确定性。分配时间可预测，这对实时系统很重要。但缺点也很明显——如果你频繁分配奇数大小的块，内部碎片会累积。这时候就需要slab分配器来兜底了。

4.5 知识体系图

下面这张图展示了伙伴系统的核心逻辑：

这张图展示了伙伴系统的完整流程：从分配请求开始，查找空闲块，找不到就向上分裂，找到就返回。释放时则检查伙伴，能合并就合并。

避坑指南： 我曾经在写一个内存分配器时，忘了处理合并时的递归情况。结果释放一个大块后，只合并了一级，导致上层链表一直为空。后来加了个while循环，问题就解决了。记住：合并要一直向上，直到不能合并为止。

好了，伙伴系统就讲到这里。它的设计思想其实很简单——二分法，但实现细节里藏着不少坑。Linux内核的实现已经非常成熟，建议你直接读源码，比看任何文档都管用。