上一篇讲了 huge page 如何通过增大映射粒度降低 TLB 和页表开销。但分配 2MB 连续物理内存本身就不是简单的事——物理页分配器必须能快速找到指定大小的连续空闲块。Buddy system 就是 Linux 用来解决这个问题的核心机制。

核心问题可以压成一句话：

buddy allocator 用按阶（order）拆分和合并管理连续物理页，解决的是页级分配与碎片控制问题。

问题从哪里来

内核需要分配连续物理页的场景很多：DMA buffer 要求物理连续、huge page 需要 order-9（2MB）或 order-18（1GB）的连续块、设备驱动需要特定对齐的物理内存。

最简单的方案是维护一个空闲页链表。但这有两个问题：第一，找"连续 N 页"需要遍历链表检查物理地址连续性，时间复杂度不可控；第二，反复分配释放后内存碎片化，即使总空闲页足够也可能凑不出连续块。

Buddy system 用 power-of-two 分块解决这两个问题：只管理 2^n 大小的块（称为 order-n 块），分配时拆大块为小块，释放时合并相邻同阶块为更大块。这保证了分配是 O(1) 查找 + O(log(max_order)) 拆分，合并也是 O(log(max_order))。

node、zone 和 free_area 的层次

物理内存管理的层次结构：

1
2
3
4
5
6
7
8
pg_data_t (node)
 └── struct zone [DMA, DMA32, NORMAL, MOVABLE, ...]
      └── free_area[MAX_PAGE_ORDER + 1]
           ├── free_area[0]: order-0 blocks (single pages, 4KB)
           ├── free_area[1]: order-1 blocks (2 pages, 8KB)
           ├── free_area[2]: order-2 blocks (4 pages, 16KB)
           ├── ...
           └── free_area[MAX_PAGE_ORDER]: largest blocks

每个 free_area[order] 维护一个空闲块链表。每个块是 2^order 个物理连续页。MAX_PAGE_ORDER 在大多数架构上是 10（即最大块 2^10 = 1024 页 = 4MB）或 11。

zone 按物理地址范围划分，反映硬件约束：DMA zone 给只能寻址低 16MB 的老设备、DMA32 给 32 位 DMA 设备、NORMAL 是一般用途、MOVABLE 专门放可迁移页面以辅助碎片整理。

分配时按 zone 优先级回退：先在最高允许的 zone 尝试，失败则向下回退。例如请求 NORMAL zone 的页面失败后可以回退到 DMA32。

分配：拆大块

分配 order-n 的页面时，buddy allocator 的步骤：

  1. 查看 free_area[n] 是否有空闲块。有则取出，完成。
  2. 没有则查看 free_area[n+1]。有则取出一个 order-(n+1) 块，拆成两个 order-n 块：一个返回给调用者，另一个挂到 free_area[n] 链表。
  3. 继续向上查找，直到找到一个足够大的块或耗尽所有 order。
1
2
3
4
5
6
7
8
9
10
11
分配 order-2 (4 pages)，当前 free_area[2] 为空:

free_area[3] 有一个 order-3 块 (8 pages, 起始 PFN=0x1000):
  split: [0x1000..0x1003] + [0x1004..0x1007]
  返回 [0x1000..0x1003] (order-2)
  [0x1004..0x1007] 挂入 free_area[2]

如果 free_area[3] 也为空，继续向上找 free_area[4]:
  split order-4 -> 2 × order-3
  再 split 其中一个 order-3 -> 2 × order-2
  返回一个 order-2，剩余的 order-3 和 order-2 各挂入对应链表

这个递归拆分保证了一个性质：分配后剩余的碎片总是 power-of-two 对齐的块，可以在未来被合并回去。

释放：合并 buddy

释放一个 order-n 块时，buddy allocator 检查它的"伙伴"（buddy）是否也空闲。buddy 的定义：与当前块大小相同、物理地址相邻、且满足对齐约束（两者合并后的起始地址必须对齐到 2^(n+1) 页边界）。

1
2
3
4
5
6
7
释放 PFN=0x1004, order=2 (4 pages):
  buddy PFN = 0x1004 XOR (1 << 2) = 0x1000
  检查 PFN=0x1000 的 order-2 块是否空闲
  如果空闲: 合并为 order-3 块 [0x1000..0x1007]
    继续检查 order-3 的 buddy (PFN=0x1008)
    如果空闲: 合并为 order-4 块 [0x1000..0x100F]
    ...直到 buddy 不空闲或达到 MAX_PAGE_ORDER

buddy 的 PFN 通过 XOR 计算：buddy_pfn = pfn ^ (1 << order)。这是 power-of-two 对齐的数学性质——同阶的两个 buddy 恰好占据一个更高阶块的上下两半。

合并是释放的逆操作。持续合并使得长时间运行后，如果没有碎片化的分配模式，大块会逐渐恢复。

per-cpu pagesets：热路径加速

大多数内核分配是 order-0（单页）。如果每次 order-0 分配都要取 zone->lock 操作 free_area，多核系统上锁竞争严重。

per-cpu pagesets（PCP）是 buddy allocator 前面的一层缓存。每个 CPU 维护一个本地的空闲页列表，order-0 分配优先从本地列表取页，释放优先归还到本地列表。只有当本地列表为空（需要从 buddy 批量补充）或超过高水位（需要批量归还给 buddy）时才接触全局 free_area。

1
2
3
4
5
6
7
8
9
10
order-0 分配路径:
  1. check per-cpu pageset (no lock needed)
     -> 有页? 取出，完成
     -> 空? 取 zone->lock，从 free_area[0] 批量取 batch 个页填充 PCP
  2. 从 PCP 取一页返回

order-0 释放路径:
  1. 归还到 per-cpu pageset (no lock needed)
  2. PCP 页数超过 high watermark?
     -> 取 zone->lock，批量归还 batch 个页到 free_area[0]

batch 大小和 high watermark 根据 zone 大小和 CPU 数量动态计算。这使得绝大多数 order-0 操作无锁完成，大幅提升多核扩展性。

对于 order > 0 的分配，直接走 buddy allocator（取 zone->lock），因为高阶分配频率远低于 order-0。

碎片与 compaction

长时间运行后，物理内存可能碎片化：大量 order-0 页被零散占用，free_area 的高阶链表为空，即使总空闲页足够也无法分配 order-9（huge page）。

内核用两种机制应对：

页面迁移（migration）：把可移动页面（用户空间匿名页、page cache 页）搬到一起，空出连续物理区域。ZONE_MOVABLE 就是专门存放可迁移页面的 zone，保证该 zone 内总能通过迁移腾出大块。

compaction：kcompactd 后台线程或直接 compaction 在分配失败时触发。它从 zone 的低地址端扫描可迁移页面，从高地址端扫描空闲页，把可迁移页面搬到高端的空闲位置，低端就空出连续块。

1
2
3
4
5
6
compaction 前:
  [used][free][used][free][used][free][used][free]

compaction 后:
  [free][free][free][free][used][used][used][used]
  ^--- 连续空闲块可满足高阶分配

/proc/buddyinfo 直接展示碎片化程度：如果高阶列的数字都是 0，说明没有大的连续块可用。

模式提炼：按阶拆分分配，按阶合并释放

1
power-of-two blocks -> split on allocation -> merge on free
维度 buddy 的选择 替代方案 为什么这样选
块大小 只有 2^n 任意大小 XOR 快速定位 buddy，无需搜索
分配 拆分最小可用块 首次适配 / 最佳适配 拆分产物仍是有效的 power-of-two 块
释放 递归合并 buddy 只归还不合并 抵抗碎片化
热路径 per-cpu cache 全局 freelist 消除 order-0 锁竞争

这个模式在其他系统中也存在：jemalloc 的 size class 是 power-of-two 对齐的，TCP 的 window size 按倍数增长，B-tree 节点分裂产生半满页。核心思想是：限制粒度为 2 的幂，换取快速的地址计算和确定性的分裂/合并语义。

一个最小实验：读取 /proc/buddyinfo

这个实验不需要编写 C 代码——/proc/buddyinfo 本身就是 buddy allocator 状态的直接暴露。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/mman.h>

static void show_buddyinfo(const char *label) {
    printf("=== %s ===\n", label);
    FILE *f = fopen("/proc/buddyinfo", "r");
    if (!f) { perror("fopen"); return; }
    char line[256];
    while (fgets(line, sizeof(line), f))
        printf("  %s", line);
    fclose(f);
    printf("\n");
}

int main(void) {
    long page_size = sysconf(_SC_PAGESIZE);
    printf("Page size: %ld bytes\n\n", page_size);
    printf("Format: Node N, zone Z  order0 order1 order2 ... order10\n");
    printf("Each column = count of free blocks at that order\n");
    printf("order-N block = %ld KB\n\n", (page_size * (1L << 10)) / 1024);

    show_buddyinfo("Initial state");

    /* 分配 256MB 匿名内存并 touch，消耗 order-0 页 */
    size_t alloc_size = 256UL * 1024 * 1024;
    char *buf = mmap(NULL, alloc_size, PROT_READ | PROT_WRITE,
                     MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
    if (buf == MAP_FAILED) { perror("mmap"); return 1; }

    /* Touch every page to force physical allocation */
    for (size_t off = 0; off < alloc_size; off += (size_t)page_size)
        buf[off] = 1;

    show_buddyinfo("After allocating 256MB");

    /* 释放 */
    munmap(buf, alloc_size);
    show_buddyinfo("After freeing 256MB");

    return 0;
}

编译与运行：

1
2
cc -Wall -Wextra -O2 buddy_demo.c -o buddy_demo
./buddy_demo

完成实验后清理：

1
rm -f buddy_demo buddy_demo.c

读取实验结果

/proc/buddyinfo 的输出格式：

1
Node 0, zone   Normal  1234  567  234  89  34  12  5  2  1  0  0

从左到右分别是 order-0 到 order-10 的空闲块数量。每个数字表示该阶有多少空闲块可用。

分配 256MB 后：低阶（order-0, order-1）的数字应该明显减少。256MB = 65536 个 4KB 页，这些页来自 buddy allocator 的各阶拆分。高阶数字可能也减少——因为分配器需要拆分高阶块来满足大量 order-0 请求。

释放 256MB 后：低阶数字恢复，如果释放的页面能找到各自的 buddy，高阶数字也可能增加（合并效果）。但不一定完全恢复到初始状态——因为释放的页面的 buddy 可能被系统其他部分占用，无法合并。

关键观察：

  • 高阶列全为 0 意味着无法分配 huge page（order-9 需要至少一个条目）。这是 THP fallback 到 4KB 的根本原因。
  • cat /proc/pagetypeinfo 提供更详细的信息，按迁移类型（Unmovable、Movable、Reclaimable）分列。Movable 类型的高阶块可以通过 compaction 获得。
  • /proc/vmstat 中 pgalloc_* 和 pgfree 计数器反映分配/释放的频率。

模式提炼：观测窗口直接映射内部状态

1
2
/proc/buddyinfo columns = free_area[order].nr_free
observation overhead ≈ 0 (just reads counters)

Linux 的 /proc 接口设计哲学：内核内部数据结构的关键计数器直接暴露为文件，无需 debugfs 或 tracing。这比"运行诊断命令获取快照"更轻量，适合持续监控。

源码锚点

入口 读它的目的
mm/page_alloc.c __alloc_pages()：分配入口，zone 选择和 fallback
mm/page_alloc.c __free_one_page()：释放入口，buddy 合并逻辑
mm/page_alloc.c expand()：从高阶块拆分到目标阶
include/linux/mmzone.h struct free_area、struct zone 定义
mm/compaction.c compact_zone()：碎片整理的核心循环

读 __free_one_page() 时可以带着一个问题：XOR 计算 buddy PFN 后，如何验证这个 buddy 确实空闲且属于同一个 zone？（提示：PageBuddy() 标志和 page_order() 检查）

研究生迁移表

Linux 概念 一般系统设计
buddy allocator power-of-two 空闲块管理（jemalloc size class）
order-N split B-tree 节点分裂
buddy merge on free 区间合并（interval coalescing）
per-cpu pageset 线程本地缓存（thread-local cache）
zone fallback 多级存储降级（SSD → HDD fallback）
ZONE_MOVABLE 专用池保证碎片整理可行性
compaction 在线碎片整理（LSM compaction、磁盘碎片整理）
/proc/buddyinfo 分配器状态的实时暴露（metrics endpoint）

power-of-two 管理是系统设计中的经典范式。网络 MTU 通常对齐到 power-of-two、CPU cache line 是 64 字节（2^6）、磁盘块大小是 512/4096 字节。核心收益是：地址计算退化为位运算，空间对齐有天然保证。

常见误解

第一个误解是认为 buddy allocator 管理所有内核内存分配。实际上 buddy 只管页级分配（最小粒度 4KB）。小于一页的对象由 SLUB 分配器管理——SLUB 从 buddy 获取整页后再切分。两者是不同层次。

第二个误解是认为 buddy 合并总能恢复大块。合并要求 buddy 必须空闲。如果一个 order-9 块的 1024 个页面中有一个被 pin 住（如被 DMA 使用），整个 order-9 区域都无法通过合并重建。这就是为什么需要 ZONE_MOVABLE 和 compaction。

第三个误解是认为 MAX_PAGE_ORDER 是内核能分配的最大连续内存。实际上 CMA（Contiguous Memory Allocator）可以预留更大的连续区域，compound page 也可以超过 MAX_PAGE_ORDER。buddy 的 MAX_PAGE_ORDER 只是常规分配路径的上限。

第四个误解是认为 per-cpu pageset 只缓存 order-0 页。虽然 PCP 主要服务 order-0 分配，但在较新内核中它也可以缓存低阶（order-1 到 order-3）的页面，以减少这些常见大小的锁竞争。

第五个误解是认为 /proc/buddyinfo 中高阶数字大就代表内存充裕。一个 order-10 块（4MB）等价于 1024 个 order-0 页，所以高阶列的一个计数代表的空闲内存远大于低阶列的一个计数。判断可用内存应该用 MemAvailable 而不是直接解读 buddyinfo 的数字。

练习

第一，在一台 Linux 机器上读取 /proc/buddyinfo，计算 Normal zone 中各阶空闲块代表的总空闲内存。验证它与 /proc/meminfo 中 MemFree 的关系（应该近似相等，差异来自 per-cpu pageset 中的页面和 reserved 页）。

第二，运行上面的实验程序，对比分配前后 /proc/buddyinfo 的变化。重点关注：分配 256MB 后，order-0 的空闲数减少量是否等于 65536？如果不等，解释差异来源（提示：高阶拆分）。

第三，用 cat /proc/pagetypeinfo 查看按迁移类型分列的 buddy 状态。找出 Movable 类型在高阶的计数，思考为什么 ZONE_MOVABLE 的高阶空闲块比 ZONE_NORMAL 更可能存在。

第四，阅读 mm/page_alloc.c 中 __free_one_page() 的实现。画出释放一个 order-0 页面时可能触发的最长合并链（从 order-0 一直合并到 MAX_PAGE_ORDER）需要满足的条件。

第五，在高负载系统上监控 /proc/vmstat 中的 compact_stall（直接 compaction 次数）和 compact_success（成功率）。如果成功率低，分析可能的原因（pinned pages、碎片化严重、Unmovable 类型页面过多）。

系列导航

参考资料