Linux 伙伴系统（Buddy System）：内核内存分配器的核心机制与碎片问题

连续物理内存：比想象中更刚需

绝大多数应用眼里，内存都是虚拟的。你拿到一个指针，后面跟着的是一段看似连续的地址空间，至于底层物理页散落在哪里，你基本无感。但对 Linux 内核来说，物理页的连续性从来都是需要考虑的问题。DMA 描述符、驱动使用的 dma_alloc_coherent、非一致内存访问（NUMA）节点内的页表分配、以及内核栈，这些路径对物理连续地址都有明确要求。

如果物理内存没有任何碎片，分配一块连续区域只需要在空闲列表中从头到尾切一块出来就行。但系统运行一段时间后，不同生命周期的页会被反复分配和释放。用户态进程的匿名页常常被 swap 出去，文件缓存页会按压力被回收，而内核自己的 slab 对象则可能长期驻留。这些页面交错在一起，你要分配 4MB 的连续物理内存，结果空闲页总数是够的，可每块最大连续区域只有几百 KB。这就是外部碎片（external fragmentation）。

内核需要一个能高效分配任意大小连续物理页的机制，同时又不能因为碎片的增加而让系统内的内存变成“看得见用不着”。这个任务的答案，就是伙伴系统。

伙伴系统的核心：以 2 的幂拆分，也以 2 的幂合并

伙伴系统的基本思想不复杂：把空闲物理页按大小分组，每组大小是 2 的幂次个页帧。内核把大小为 2^order 个页的空闲块挂在 free_area[order] 对应的链表上。你要分配 size 个页帧，就找到满足 2^(order-1) < size <= 2^order 的最小 order，然后从那个链表拿一块出来。如果链表非空，直接摘一块；如果链表为空，就到更高阶去找，找到后一层层往下拆。

这个过程里有个关键设计：每个被拆出来的半块都能找到它的“伙伴”，也就是与它在物理地址上相邻、大小相同的另一半。释放的时候，内核会先把页块放回对应 order 的链表，然后检查它的伙伴是不是也是空闲的。如果伙伴空闲，就把两个块合并成一个高一阶的块，再继续向上检查。这样一来，碎片有机会被“拼接”回去。

伙伴系统并不追求最优分配，它的好处在于：分配和释放的复杂度都是常数级别（虽然有修锁开销），而且合并逻辑简单可靠。对内核这种对延迟敏感的基础设施来说，可预测的 O(1) 行为比最优适配重要得多。

从数据结构看伙伴系统

在每个内存节点（zone）里，伙伴系统对应一组 free_area。以 4KB 页大小为例，order 从 0 到 10（MAX_ORDER 通常是 11，但也可能更大），最大可管理的连续区域是 4MB。超过这个大小的连续分配，就要走其他机制，比如 CMA 或者直接预留内存。

struct zone {
    struct free_area free_area[NR_PAGE_ORDER_MAX];
    ...
};

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

注意上面 free_area 里还有一个维度是迁移类型（MIGRATE_TYPES），这在后面讨论碎片时再展开。单看 order 的话，每个链表挂的是该大小下所有空闲块。内核通常只保存每个块的首页的 page 结构，block 的尾页信息通过算法推导。

分配和释放时的拆分与合并

分配流程是典型的“从大到小”过程。拿 Linux 架设 page allocator 之后，slowpath 里会有很多额外检查，但 fastpath 的核心逻辑可以简化成下面这样：

struct page *__rmqueue(struct zone *zone, unsigned int order)
{
    int current_order = order;
    struct page *page;

    // 从当前阶开始，向上找到第一个有空闲块的阶
    for (; current_order < MAX_ORDER; ++current_order) {
        struct free_area *area = &zone->free_area[current_order];
        if (!list_empty(&area->free_list[MIGRATE_MOVABLE])) {
            page = list_first_entry(...);
            list_del(&page->lru);
            expand(zone, page, current_order, order, area);
            return page;
        }
    }
    return NULL; // 进入 slowpath：回收、压缩或返回失败
}

这段代码省略了迁移类型、锁和 pcp（per-cpu page list）等内容，但足以看出一个关键点：从高阶链表摘下一块大内存后，expand() 会把多余的部分按 2 的幂次拆开，并挂回低阶链表。

释放时反过来，先从低阶向上看能不能和伙伴合并。判断伙伴的地址有一个技巧：假设当前页块的起始 pfn 是 pfn，阶为 order，那么伙伴的 pfn 就是 pfn ^ (1 << order)。因为页块大小是 2^order，这个异或操作天然满足“地址相邻且同大小”的条件。

int __free_one_page(unsigned long pfn, unsigned int order)
{
    while (order < MAX_ORDER - 1) {
        unsigned long buddy_pfn = pfn ^ (1UL << order);
        if (!page_is_buddy(pfn_to_page(buddy_pfn), order))
            break;
        // 把伙伴从空闲链表卸下来，合并
        del_page_from_free_list(page_to_page(buddy_pfn), order);
        if (buddy_pfn < pfn)
            pfn = buddy_pfn;
        order++;
    }
    add_to_free_list(pfn, order);
    return order;
}

注意合并时 pfn 的更新：当 buddy 在低地址侧时，新区块的低地址就是 buddy 的地址，所以要取两者中较小者作为合并后的块首。这个细节在做内存热插拔或者分析 buddyinfo 时容易被忽略。

碎片问题：为什么合并不能解决一切

既然合并机制存在，为什么系统跑久了仍然会出现大量外部碎片？原因在于合并的前提是伙伴也要是空闲的。如果两个相邻块中的一块被长期占用，另一块释放后无法与它合并，只能挂在低阶链表上。这些低阶空闲块越积越多，相互之间被不可移动的页隔开，高阶区域就无法形成。

典型的场景是：一台文件服务器长时间运行后，文件缓存页被回收，释放出来的页块大小并不均匀。这些空闲页如果正好分布在内核 slab 页之间，就无法和相邻的空闲页合并。尽管系统还有不少空闲内存，但你要分配一个 order-5（128KB）的区域，系统得先做内存压缩（compaction）或者直接失败。

另一个容易踩坑的地方是 percpu 页列表（pcp）。percpu 机制把 order-0 页的分配和释放都放到了每 CPU 缓存里，减少了锁竞争，但也意味着这些热页暂时“藏”在缓存中，不会被伙伴系统看见。释放到 pcp 的页如果长时间不批量回流到伙伴系统，同样会影响高阶块的合并。好在内核会定期通过 pcp->expire 和 vm.zone_reclaim 等逻辑把多余的页刷回去，但这也说明伙伴系统感知到的空闲状态并不是实时的。

内核为了抗碎片做了哪些设计

迁移类型：让“不可移动”的页尽量扎堆

碎片化的根源之一是不可移动页和可移动页交错。如果能把相同迁移属性的页聚在一起，那么释放某个类型内存时，就有更大机会形成大块空闲区。于是内核在 free_area 里增加了一个维度：迁移类型。

分配器在找内存时，优先从同类型的链表中取。如果用户态申请匿名页，优先用 MIGRATE_MOVABLE；内核启动时申请页表，优先用 MIGRATE_UNMOVABLE。这样做的结果是：不可移动的页会慢慢集中到一部分区域内，可移动页则其余区域频繁迁移合并，最终大块连续区域更容易出现在可移动区里。

当然，这种隔离不是绝对的。如果某个迁移类型的空闲列表为空，内核会允许 fallback 到其他类型。比如不可移动页缺少时，会去可回收类型里借用。这种借用会让碎片状态变差，所以内核从 Linux 3.x 开始引入了一些 fallback 次序的优化，比如优先从可回收页面中偷取，而不是可移动页面。

CMA 与 vmalloc：把连续内存需求“外包”

对于驱动需要大块连续内存的场景，比如相机的 DMA buffer，直接依赖伙伴系统分配很容易失败。CMA（Contiguous Memory Allocator）通过预留一块可移动的区域，平时这些页会作为可移动页面交给系统使用，当驱动需要连续内存时，内核通过内存迁移把该区域的页集中起来，形成大块连续区域。这相当于用预留空间换取了运行时灵活性。

vmalloc 是另一条思路：它把物理上不连续的页映射到连续的虚拟地址空间。但 vmalloc 的代价也不小——每次分配需要修改页表，TLB 和缓存也一样会受到影响，而且 vm 区域还要防止页表自映射之类的问题。内核里只有确实需要大块虚拟连续且不要求物理连续的场合才用它，比如内核模块加载时的代码段映射。

内存压缩与碎片指数

当分配高阶页失败时，伙伴系统不会立刻放弃。它还有一个慢路径（slowpath），其中最重要的动作是内存压缩（compaction）。compaction 会把可移动页从一片区域搬到另一片区域，在原来的位置留下空闲页块，再尝试合并。这个过程只有在碎片指数达到一定阈值时才会有效率，否则会导致大量页迁移而收益甚微。

碎片指数（fragmentation index）是一个介于 0 和 1000 之间的值，用来衡量分配失败时该阶的碎片程度。如果有足够多可移动页可以迁移，指数会偏高，compaction 可能有效；如果碎片多是不可移动页造成的，compaction 无能为力。管理员可以观察 /proc/pagetypeinfo 中各种迁移类型的页分布，判断是否需要调整预留比例或者加大 CMA。

常见误区：不是所有碎片都是伙伴系统的锅

很多开发者第一次接触碎片问题，容易把锅甩给伙伴系统算法。其实伙伴系统只是按 2 的幂次切分空闲块，真正导致碎片的是不同生命周期的页交错分布。为了避免混淆，这里有三个常见误区值得单独说明：

• 误区一：伙伴系统算法本身产生碎片。伙伴系统拆分会把大块变成小块，但小块释放后如果能合并仍能复原。真正的麻烦在于伙伴被无关页面占据，合并率低。任何物理分配器都避不开这一点。
• 误区二：vmalloc 能替代伙伴系统应对碎片。vmalloc 解决的是虚拟地址连续，底层物理页仍然来自伙伴系统，使用频繁时页表开销和 TLB 压力都不小，也无法用于 DMA。
• 误区三：迁移类型可以完全消除碎片。迁移类型只是提高合并概率，内存紧张时的 fallback 会让分类失效。隔离无法替代回收和压缩，诊断时还是要看实际空闲块分布。

实际运维里怎么观察和应对碎片

我们经常用 /proc/buddyinfo 判断系统是否有碎片风险。它按内存节点输出每个阶的空闲块数量。如果你看到 order-4 以上的块很少，而内存总量还很宽裕，说明这个节点的碎片化已经比较明显。长期低于阈值时，就需要考虑是否触发内存规整。

# 查看该机器 buddyinfo 片段
root@host:/proc# cat buddyinfo
Node 0, zone   Normal,  1  1  2  1  3  5  2  0  1  1  0  0
Node 0, zone  Movable,  0  0  0  0  0  0  0  0  0  0  0  0

在长时间运行的生产服务器上，如果业务不需要大量高阶分配，碎片问题通常不会直接产生故障。真正容易受影响的是虚拟化宿主机和数据库节点。给虚拟机分配 2MB 巨页时，伙伴系统必须提供 order-9（按 4KB 页计算）的连续区域；如果分配失败，可能触发 THP 回收，进而带来卡顿。

应对策略一般分三层：

1. 抑制碎片扩大：保持系统有足够的内存弹性，设置合理的 vm.min_free_kbytes，避免在内存紧张时频繁进行直接回收。
2. 主动规整：通过 echo 1 > /proc/sys/vm/compact_memory 触发全系统压缩，或者让 khugepaged 和 compaction 自然运转。
3. 预防性预留：对需要大块连续内存的业务，用 CMA 或者启动时预留内存，而不是运行时依赖碎片回收。

总结

伙伴系统不是万能的，但它仍然是内核物理内存分配的地基。它的独特之处在于用 2 的幂次把“分配”和“合并”转换为常数级操作，同时把碎片问题留给上层机制去缓解。理解它，不只是为了看懂内核源代码，更是为了在真实环境中判断内存碎片到底会不会影响你的业务，以及要用什么样的手段去兜底。

如果今天从这篇文章里带一个核心认知走，我希望是：伙伴系统决定的是“如何高效地切分和合并空闲页”，而真正决定系统能否持续提供大块连续内存的，是页面的可迁移性、回收策略以及分配时的类型隔离。这些机制协同起来，才构成了 Linux 内存管理对抗碎片的完整故事。