【操作系统百科】Buddy 系统

所有 kmalloc、vmalloc、page cache、anon page 最终都从 buddy 系统拿物理页。buddy 用 2^order 空闲链表，分裂合并 O(1)，简单、确定、快。

一、先看图

flowchart TD
    REQ[alloc_pages<br/>order=0] --> PCP{per-CPU page<br/>cache 有空闲?}
    PCP -->|有| FAST[直接返回<br/>快速路径]
    PCP -->|无| BUDDY[buddy free list<br/>order 0..10]
    BUDDY --> SPLIT{order 0 有?}
    SPLIT -->|有| RET[返回]
    SPLIT -->|无| UP[向上找 order 1]
    UP --> SPLIT2{order 1 有?}
    SPLIT2 -->|有| SPL[拆成 2×order0<br/>返回 1 个]
    SPLIT2 -->|无| UP2[继续向上...]
    UP2 --> FAIL[直到 order 10<br/>或失败]
    classDef fast fill:#3fb95022,stroke:#3fb950,color:#adbac7;
    classDef slow fill:#f0883e22,stroke:#f0883e,color:#adbac7;
    class PCP,FAST fast
    class UP,UP2,FAIL slow

二、buddy 算法

每个 zone 维护 11 条空闲链表（order 0-10）：

order 0:  4KB 页面
order 1:  8KB（2 页连续）
...
order 10: 4MB（1024 页连续）

分配：从请求的 order 链表取；没有 → 从更高 order 取一块、拆开，一半返回一半放回低 order 链表。

释放：放回对应 order 链表；检查 buddy（伙伴块）是否也空闲 → 合并成更高 order → 递归合并。

查看：

cat /proc/buddyinfo
# Node 0, zone   Normal  1234  567  321  89  34  12  4  2  1  0  0
#                         ^o0  ^o1  ^o2  ...

三、Zone 划分

ZONE_DMA       0-16MB     ISA DMA 设备（x86 遗留）
ZONE_DMA32     0-4GB      32 位 DMA 设备
ZONE_NORMAL    4GB+       主力
ZONE_MOVABLE   可选       热插拔/CMA 用
ZONE_HIGHMEM   仅 32 位   64 位无

每个 zone 有独立的 buddy 空闲链表和 watermark。

四、gfp flags

分配时传 gfp_t（Get Free Pages flags）告诉 buddy：

__GFP_DMA         // 从 DMA zone
__GFP_DMA32       // 从 DMA32 zone
__GFP_HIGHMEM     // 允许 HIGHMEM
__GFP_MOVABLE     // 可迁移（compaction 友好）
__GFP_IO          // 允许触发 I/O（writeback）
__GFP_FS          // 允许文件系统操作
__GFP_NOWAIT      // 不等待
__GFP_RETRY_MAYFAIL // 重试但可能失败
__GFP_NOFAIL      // 绝不失败（死循环重试）
__GFP_ZERO        // 零填充

常用组合：

GFP_KERNEL   = __GFP_RECLAIM | __GFP_IO | __GFP_FS    // 进程上下文
GFP_ATOMIC   = __GFP_HIGH | __GFP_KSWAPD_RECLAIM      // 中断上下文
GFP_USER     = GFP_KERNEL | __GFP_HARDWALL             // 用户空间
GFP_HIGHUSER_MOVABLE = GFP_USER | __GFP_HIGHMEM | __GFP_MOVABLE

五、per-CPU page cache（pcp）

order-0 分配（最频繁）走 pcp 快速路径：

• 每 CPU 缓存 high 个页（默认几百）
• 分配/释放不碰 buddy 主锁
• batch 模式补货/归还

cat /proc/zoneinfo | grep -A5 "pagesets"
# cpu: 0
#   count: 312
#   high:  378
#   batch: 63

pcp 让 order-0 分配几乎无锁。

六、碎片与 compaction

buddy 的弱点：高 order 分配（order≥2）容易因碎片化失败——虽然总空闲页够，但凑不出连续的。

6.1 migrate type

buddy 把页按 migrate type 分组：

• MIGRATE_UNMOVABLE：内核数据结构
• MIGRATE_MOVABLE：用户匿名/文件页（可迁移）
• MIGRATE_RECLAIMABLE：可回收页

分组目的：把可迁移的页聚在一起 → compaction 更高效。

6.2 compaction

compact_zone 扫描：

1. 从 zone 低地址找 movable 页
2. 从 zone 高地址找空洞
3. 把 movable 页迁移到高地址空洞
4. 低地址腾出连续大块

触发：

• alloc_pages 高 order 失败时
• kcompactd 后台线程
• echo 1 > /proc/sys/vm/compact_memory 手动

6.3 CMA

Contiguous Memory Allocator：启动时预留一块 MIGRATE_CMA 区域，平时给 movable 页用，DMA 需要时强制迁移出来。

dmesg | grep cma    # 看 CMA 预留大小

七、watermark 与分配失败

D-36 讲过 watermark。buddy 分配时检查：

if (free < min + lowmem_reserve)
    → 触发 direct reclaim / OOM

lowmem_reserve_ratio 保护低 zone（DMA/DMA32）不被高 zone 请求耗尽。

八、大型分配的替代

九、观察与调试

cat /proc/buddyinfo          # 各 order 空闲块数
cat /proc/pagetypeinfo       # 按 migrate type 细分
cat /proc/vmstat | grep compact  # compaction 统计
cat /proc/zoneinfo           # watermark + pcp

# 实时
watch -d cat /proc/buddyinfo

# 碎片指数
cat /sys/kernel/debug/extfrag/extfrag_index  2>/dev/null

十、小结

• buddy 用 2^order 空闲链表，分裂/合并 O(1)
• pcp 让 order-0 几乎无锁
• zone + gfp flags 约束分配从哪取
• migrate type + compaction 治碎片
• CMA 为 DMA 设备预留连续内存

参考文献

• Gorman, M. “Understanding the Linux Virtual Memory Manager.” §6 “Physical Page Allocation”
• mm/page_alloc.c
• Documentation/admin-guide/mm/concepts.rst
• Vlastimil Babka, “Compaction improvements.” LPC 2018
• include/linux/gfp_types.h

工具

• /proc/buddyinfo、/proc/pagetypeinfo
• /proc/zoneinfo
• vmstat、sar -B
• trace-cmd + page_alloc tracepoints

上一篇：HugeTLB 与 THP 下一篇：Slab/SLUB 分配器