---

title: Linux内核Buddy System内存分配器深度原理与实战

category: 内存管理

keywords: Linux内核, Buddy System, 内存分配器, 页面分配, 碎片整理, 内核内存管理

description: 深入解析Linux内核Buddy System内存分配器的核心算法、数据结构、页面分配与释放流程、伙伴系统工作原理、GFP标志、页面迁移与碎片整理机制、以及性能调优与工程实战。

---

Linux内核Buddy System内存分配器深度原理与实战

一、引言

Buddy System（伙伴系统）是Linux内核物理内存管理的基石算法。自1963年由Harry Markowitz提出以来，经过Ken Thompson首次在Unix中实现，至今已有超过半个世纪的历史。它简单、高效、工程可靠，支撑了现代操作系统中几乎所有物理页帧的分配与释放。

理解Buddy System，是理解整个Linux内核内存管理子系统（包括Slab分配器、KSM、CMA、内存热插拔等）的必经之路。本文将从核心数据结构出发，深入剖析算法原理、GFP分配标志、页面迁移策略、碎片整理机制，并最终给出工程实践中的监控与调优方法。

二、核心数据结构与概念

2.1 节点（Node）与区域（Zone）

Linux内核将物理内存组织为 Node → Zone → Page 的三级层次结构：

// NUMA节点
typedef struct pglist_data {
    struct zone node_zones[MAX_NR_ZONES];  // 该节点包含的内存区域
    struct zoneref node_zonelists[MAX_ZONETYPES]; // 分配回退区域列表
    int nr_zones;
    struct page *node_mem_map;            // 页描述符数组
    unsigned long node_start_pfn;         // 起始物理页帧号
    unsigned long node_present_pages;     // 当前可用物理页数
    unsigned long node_spanned_pages;     // 跨越的物理页数（含空洞）
} pg_data_t;

每个NUMA节点包含多个内存区域（Zone），x86_64典型的类型包括：

Zone	描述	典型范围
ZONE_DMA	ISA设备DMA可用内存	< 16MB
ZONE_DMA32	32位DMA设备可用	< 4GB
ZONE_NORMAL	内核直接映射	16MB ~ 896MB
ZONE_MOVABLE	可移动页面（用于碎片整理）	动态
ZONE_DEVICE	设备持久内存	特殊

关键洞察：ZONE_NORMAL由内核线性映射（page_offset_base），访问开销最小，是大多数内核分配的首选区域。ZONE_DMA在x86_64上基本退化为兼容历史设备的小区域。

2.2 空闲区域（Free Area）

Buddy System的核心数据结构是 struct free_area，为每个order维护一个空闲块链表：

struct free_area {
    struct free_area_free_list {
        struct list_head free_list[MIGRATE_TYPES]; // 按迁移类型分组的空闲链表
    };
    unsigned long nr_free;   // 该order下的空闲页面总数
};

每个Zone内部维护一个 free_area 数组（通常为0到MAX_ORDER-1）。MAX_ORDER通常为11（对应2^10 = 1024页 = 4MB的连续块），嵌入式系统可能使用更小的值（如MAX_ORDER=8）。

2.3 页面描述符（Page Struct）

系统中的每个物理页都对应一个 struct page 描述符（全局的 mem_map 数组）。在伙伴系统相关的字段中：

struct page {
    // 链表节点（用于串联空闲页面）
    struct lru _list;
    // 私有数据（存储order等信息）
    unsigned long _private;
    // 页引用计数
    atomic_t _refcount;
    // 映射计数
    atomic_t _mapcount;
};

• `_private` 字段：空闲时存储该块的order值（释放时用于伙伴查找），使用时存储其他含义。
• `PG_buddy` 位：标识页面是否在伙伴系统的空闲链表中（通过 `page_private()` 检查）。

三、Buddy System核心算法

3.1 伙伴（Buddy）的定义

两个块互为"伙伴"，当且仅当：

1. 大小相同（同为2^order页）
2. 物理地址连续
3. 合并后恰好构成一个2^(order+1)页的块

伙伴地址计算公式（一个块的伙伴地址为）：

buddy_addr = page_addr XOR (1 << (order + PAGE_SHIFT))

或者等价地：

buddy_pfn = page_pfn XOR (1 << order)

这个XOR操作巧妙地利用了：相同size且连续的块，只有order+1位不同，因此XOR即可得到伙伴地址。

3.2 分配流程（ alloc_pages → __alloc_pages_nodemask → __alloc_pages → __get_free_pages → __rmqueue → __rmqueue_smallest → rmqueue_buddy → expand）

分配路径的调用链：

alloc_pages()
  └─► __alloc_pages_nodemask()
        └─► get_page_from_freelist()        // 快速路径：直接分配
              └─► __rmqueue()                     // 从伙伴系统取出
                    └─► __rmqueue_smallest()      // 从小到大拆分取块
        └─► __alloc_pages_slowpath()      // 慢速路径：内存不足时的回退
              └─► direct_reclaim()              // 直接回收
              └─► direct_compact()              // 直接碎片整理

快速分配流程（__rmqueue_smallest）：

static struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
                                       int migratetype)
{
    // 从请求的order开始，逐级向上查找有可用块的order
    for (; order < MAX_ORDER; order++) {
        struct free_area *area = &zone->free_area[order];

        // 在对应order和迁移类型的空闲链表中获取一个块
        page = get_page_from_free_list(area, migratetype, order);
        if (!page)
            continue;

        // 如果order > 请求order，将多余的后半块逐级回收（expand）
        expand(zone, page, order, ..., migratetype);
        return page;
    }
    return NULL; // 所有order都没有可用块
}

expand（展开）操作：当从较高order取得大块时，需要将块不断二等分，将后半部分投入低一级order的空闲链表，直到块大小等于请求大小。

请求 order=2（16KB），找到 order=5（128KB）块
128KB → 拆分 → 64KB（回收到order=4链表） + 64KB
 64KB → 拆分 → 32KB（回收到order=3链表） + 32KB
 32KB → 拆分 → 16KB（回收到order=2链表） + 16KB
 16KB (order=2) = 请求大小，返回使用的页

注意：expand总是回收后半部分，因为前半部分从较低地址开始，满足地址对齐要求（2^(order+1)对齐的块的前沿对齐）。

3.3 释放流程（ __free_pages → __free_one_page → __free_one_page → __free_pages_ok → free_one_page → __free_one_page）

释放流程是分配的逆操作，核心在合并（coalesce）：

static inline void __free_one_page(struct page *page, unsigned long pfn,
                                   struct zone *zone, unsigned int order,
                                   int migratetype)
{
    // 循环尝试向上合并
    while (order < MAX_ORDER - 1) {
        // 计算伙伴页帧号
        unsigned long buddy_pfn = __find_buddy_pfn(pfn, order);

        // 获取伙伴的page结构
        struct page *buddy = page + (buddy_pfn - pfn);

        // 检查伙伴是否可以合并（在同一zone、同迁移类型、在free_list中）
        if (!page_is_buddy(page, buddy, order))
            break; // 不能合并，停止

        // 从当前order的空闲链表中移除伙伴
        del_page_from_free_list(buddy, zone, order);

        // 清除order值
        Combined_pfn = pfn & buddy_pfn;
        page = page + (combined_pfn - pfn);
        pfn = combined_pfn;

        order++; // 成功合并一次，order提升
    }

    // 设置最终块的order并加入对应空闲链表
    set_buddy_order(page, order);
    add_to_free_list(page, zone, order, migratetype);
}

三种典型合并场景：

1. **最佳情况**：释放的页面与伙伴页都空闲，逐级合并直至达到最高order。序列分配、序列释放的场景下效率最高。
2. **中间情况**：只能与一侧伙伴合并，最终形成中等大小的块。
3. **最差情况**：伙伴不在空闲链表中，无法合并，只能将当前块加入对应order的空闲链表。

3.4 伙伴查找的优化

__find_buddy_pfn 的实现极其简洁高效：

static inline unsigned long
__find_buddy_pfn(unsigned long page_pfn, unsigned int order)
{
    return page_pfn ^ (1UL << order);
}

这个XOR运算的前提是：参与合并的两个块必须恰好填满一个高一阶的块空间。也就是说，低地址块的pfn必须是对齐到2^(order+1)的，XOR后得到的高地址块起始地址。

四、GFP分配标志

GFP（Get Free Pages）标志是调用 alloc_pages 时传递的控制标志，决定了分配器的行为：

4.1 区域修饰符（Zone Modifiers）

标志	含义
__GFP_DMA	强制从ZONE_DMA分配
__GFP_DMA32	强制从ZONE_DMA32分配
__GFP_HIGHMEM	允许高端内存
__GFP_MOVABLE	页面可移动
__GFP_RECLAIM	允许直接回收

4.2 行为修饰符（Action Modifiers）

标志	含义	工程影响
__GFP_WAIT	允许阻塞等待回收	进程上下文可用
__GFP_IO	允许启动IO（写脏页）	可能触发磁盘写入
__GFP_FS	允许调用文件系统操作	可能触发文件写回
__GFP_COLD	请求冷页（不在CPU缓存中）	初始化缓冲区使用
__GFP_NOWARN	分配失败时不打印告警	可优雅降级的路径
__GFP_RETRY_MAYFAIL	重试但允许最终失败	不等死，可回退
__GFP_ZERO	分配的页清零	安全敏感数据
__GFP_NOFAIL	永不返回NULL（deprecated高危）	慎用！可能导致活锁

4.3 GFP快速决策矩阵

if (进程上下文 && 可阻塞) → 允许 __GFP_IO | __GFP_FS | __GFP_RECLAIM
if (中断上下文)       → 绝对禁止 __GFP_IO/__GFP_FS/__GFP_WAIT
if (持有自旋锁)      → 禁止任何可能阻塞的操作
if (文件系统递归)    → 控制 __GFP_FS 防止递归

常见GFP组合的工程语义：

• `GFP_KERNEL` = `__GFP_WAIT | __GFP_IO | __GFP_FS` — 标准内核分配，可能触发回收和IO
• `GFP_ATOMIC` = `0`（不含清晰标志）— 用于中断/原子上下文，不阻塞，可能失败
• `GFP_NOIO` = `__GFP_WAIT` — IO路径中分配，允许回收但不启动IO
• `GFP_NOWAIT` = `0` — 不等待，不回收，最轻量
• `GFP_HIGHUSER` = 用户空间相关的高端内存分配

五、抗碎片化：页面迁移类型

5.1 为什么要分组？

在长期运行的系统中，页面不断分配和释放，即使总空闲页数充足，也可能找不到足够大的连续物理块（外部碎片）。Buddy System无法解决外部碎片——它只能合并正好相邻的伙伴页。

Linux的解决方案：按分配可迁移性分组，尽量让同类页面聚在一起，为后续碎片整理创造条件。

5.2 迁移类型（Migratetype）

enum migratetype {
    MIGRATE_UNMOVABLE,   // 不可移动（内核数据结构、页表等）
    MIGRATE_MOVABLE,     // 可移动（用户空间页面、页缓存）
    MIGRATE_RECLAIMABLE, // 可回收（文件映射页，但暂时不写IO）
    MIGRATE_PCP,         // Per-CPU页面（临时缓存）
    MIGRATE_ISOLATE,     // 已隔离（仅内存热插拔使用）
    MIGRATE_TYPES
};

核心原则：

• 不可移动页和可移动页永远不混在同一order链，避免两类页面交叉占据一块连续内存——这样当需要搬走可移动页时，不可移动页不会成为障碍。
• 即使释放后，同一order的链表也只存放相同迁移类型的块。

5.3 分组 fallback 策略

当一个order链表中没有对应迁移类型的空闲块时，分配器会向其他类型"偷取"（fallback）。偷取顺序（由 zone_fallbacks 定义）：

UNMOVABLE链表空 → 尝试 RECLAIMABLE → 尝试 MOVABLE → ...（从不易争夺的资源偷取）
MOVABLE链表空 → 尝试 UNMOVABLE（谨慎）→ 尝试 RECLAIMABLE

为什么UNMOVABLE优先偷RECLAIMABLE？因为RECLAIMABLE可以回收，比UNDOABLE（绝对无法搬走）对碎片的影响更小。

六、碎片整理（Memory Compaction）

6.1 问题场景

碎片整理解决的核心问题是：区域中有大量空闲页面，但分散在不同小块中，无法组成满足高阶请求的连续块。

[B][F][B][F][F][B][F][B][F][F]  
B=被占用, F=空闲
虽然总空闲=5页，但无连续4+页块，order=2的请求失败。

碎片整理的目标：移动可移动页面，整合出大块连续空间。

6.2 直接碎片整理（kcompactd）

内核有专门的 kcompactd 内核线程，基于扫描（isolate + migrate + free）流程：

// 碎片整理核心区域扫描
static void compact_zone(struct zone *zone, struct compact_control *cc)
{
    // 1. ISOLATE 阶段：从zone前端向前扫描，将可移动页隔离
    isolate_movable_pages(pfn_start, pfn_end, &source_list);

    // 2. MIGRATE 阶段：将隔离的页面迁移到zone后端空余处
    migrate_pages(&source_list, compaction_alloc, ...);

    // 3. FREE 阶段：迁移源地址现在已空，并入伙伴系统
    // （migrate_pages已完成free，buddy合并）
}

• **扫描方向**：正向扫描找"可迁移源"，反向扫描找"空闲目标"。
• **终止条件**：找到一块满足请求大小的空闲连续空间即停止。
• **开销评估**：`compaction_suitable()` 检查碎片是否严重到值得付出代价。

6.3 Proactive Compaction（主动碎片整理）

Linux 5.9引入了 proactive compaction（proactiveness 参数触发条件），定期主动整合碎片，避免被动压缩时的延迟。

# 主动碎片整理参数
/sys/kernel/debug/extfrag/extfrag_index  # 各order的碎片指数
/proc/sys/vm/compact_memory              # 手动触发全系统碎片整理
/sys/kernel/debug/zonelist               # 各zone碎片化视图

七、Per-CPU Pageset（PCP）

7.1 设计思想

多核系统每CPU直接访问伙伴系统的锁竞争严重。Linux引入Per-CPU页面集作为缓存层，每个CPU维护一小批空闲页面，优先从本地缓存分配。

struct per_cpu_pages {
    unsigned int count;       // 当前缓存页面数
    unsigned int high;        // 高水位（超过则批量返还伙伴系统）
    unsigned int batch;       // 每批加入/取出页面数（默认=30*4KB=120KB）

    struct list_head lists[MHIGHPERPAGE_RCL_PCP_LISTS]; // 按冷热分组的链表
};

7.2 PCP的工作流程

分配：

1. 从 `pcp->list` 链表取出页面
2. 若链表空，从伙伴系统批量获取 `batch` 个页面
3. 页面从伙伴系统中以 **order=0**（单页）形式取出（分批）

释放：

1. 将页面放回 `pcp->list` 链表
2. 若链表长度超过 `high`，批量返还伙伴系统

这样的设计既减少了锁争用，又保持了页面的局部性——最近使用过的页面更可能在CPU缓存中（热页）。

八、内存水位线（Watermarks）

Zone结构中维护了三个水位线，用于判断内存充裕程度：

struct zone {
    unsigned long _watermark[NR_MARK];  // WMARK_MIN, WMARK_LOW, WMARK_HIGH
    unsigned long percpu_drift_mark;
    unsigned long watermark_boost; // 由临时提升水位的碎片整理设置
};

水位	含义	阈值比例（相对于zone大小）
WMARK_MIN	紧急保留，分配低于此直接失败	~0.005% (~256页)
WMARK_LOW	kswapd开始后台回收	~0.01% (~512页)
WMARK_HIGH	kswapd可停止回收	~0.015% (~768页)

分配路径上的水位检查：

• 快速路径检查：`zone_watermark_fast(zone, order, mark)`，mark通常为 `WMARK_LOW`
• 如果当前空闲页数 > `WMARK_HIGH` + 需求页数 → 直接分配（免回收）
• 如果当前空闲页数 < `WMARK_MIN` + 需求页数 → 分配失败/触发快回收

可调整参数：

# 全局调整
/proc/sys/vm/min_free_kbytes       # WMARK_MIN基准（单位KB）
/proc/sys/vm/swappiness            # 匿名页vs文件页回收比率

九、工程实战：监控与调试

9.1 /proc/buddyinfo

最直接的工具，展示每个order在各zone的空闲块数：

Node 0, zone   Normal   10   5   8   3   2   1   1   0   0   0   0
              order=0   1    2    3    4    5    6    7    8    9    10

解读：order=0有10个空闲页，order=2有8个（每块4页，总计32页），order=9以上几乎为0（大块连续内存极度稀缺）。

9.2 /proc/pagetypeinfo

更丰富的信息，包含迁移类型分组：

Free pages count at each order
      migratetype    Unmovable      Movable  Reclaimable      HighAtomic      ...
Order    0      20          5000        3000          10
Order    1      5           150         80            2
...

通过这个信息可以判断碎片化类型和分布。

9.3 /proc/vmstat 中的伙伴系统事件

pgalloc_dma          # DMA区域分配次数
pgalloc_normal       # NORMAL区域分配次数
pgalloc_movable      # MOVABLE区域分配次数
pgcompact_success    # 碎片整理成功次数
pgcompact_fail       # 碎片整理失败次数
compact_stall        # 碎片整理被阻塞次数
compact_fail         # 碎片整理无法找到可移动页
compact_success      # 碎片整理成功整合出大块
kcompactd_wakeup     # kcompactd被唤醒次数

9.4 slabtop / /proc/slabinfo

Slab分配器建立在Buddy之上，通过slabinfo可以看到从Buddy获取了多少页面：

cat /proc/slabinfo | head -20

9.5 碎片指数（Fragmentation Index）

通过 /sys/kernel/debug/extfrag/extfrag_index 查看每个zone每个order的碎片化指数：

Node 0, zone      DMA -1.000 0.412 0.412 0.412 ...
Node 0, zone   Normal -1.000 0.263 0.228 0.203 ...

• `-1.0`：碎片极低（所有空闲页都能组成该order的块）
• 正值越大：碎片越严重。值= `1 - (可用大块数/最大可能大块数)`

9.6 内存压力测试工具

# stress-ng 内存压力测试
stress-ng --vm 4 --vm-bytes 80% --vm-keep -t 60s

# 触发直接回收（诊断用）
echo 3 > /proc/sys/vm/drop_caches       # 清理缓存，增加空闲页
echo 1 > /proc/sys/vm/compact_memory    # 手动触发全系统碎片整理

# 用ftrace追踪分配行为
cat /sys/kernel/debug/tracing/events/kmem/mm_page_alloc/format
echo 1 > /sys/kernel/debug/tracing/events/kmem/mm_page_alloc/enable

十、Buddy System的工程陷阱

陷阱 1：高阶请求在UP系统中平凡成功，在NUMA下失败

在UP（单处理器）系统中，内存连续性好，高阶请求（order≥3）容易成功。但在NUMA系统中，每个Node的总内存相对较小，高阶请求经常失败。

解决方案：Node内使用 __GFP_THISNODE 约束分配，或使用NUMA感知的分配策略。

陷阱 2：DMA32碎片化导致IO失败

32位DMA设备只能访问低4GB物理内存。当DMA32区域的碎片积累后，即使有大量总空闲页，也可能找不到对齐的连续块。

解决方案：尽量使用包括 ZONE_DMA32 范围的对齐分配，或使用可迁移页（让碎片整理发挥作用）。

陷阱 3：GFP_KERNEL在中断上下文使用

在中断处理函数中使用 GFP_KERNEL 会因等待回收而触发内核崩溃（"scheduling while atomic"）。

修正：中断/原子上下文中使用 GFP_ATOMIC，或推迟到workqueue中使用GFP_KERNEL。

陷阱 4：__GFP_NOFAIL的隐患

__GFP_NOFAIL 永不返回NULL，在内存极度紧张时可能导致活锁（反复回收但分配永不满足，而NOFAIL又不放弃）。

建议：Linux 5.0+已标记为deprecated，几乎所有使用都应替换为 GFP_RETRY_MAYFAIL 或显式错误处理。

陷阱 5：频繁大块分配后的"慢路径依赖"

长期运行的系统经历大量大块分配→释放后，order分布呈现"低阶满、高阶空"的状态，最终所有大块请求只能走慢路径（回收+碎片整理），性能极差。

解决方案：周期性主动碎片整理，避免累积；使用 MADVISE_HUGEPAGE 提前转换透明大页。

十一、与Slab/SLOB/SLUB的关系

Buddy System分配的最小单位是一页（通常4KB），直接用于小于页大小的对象分配会造成巨大浪费（内部碎片）。因此Linux构建了Slab层：

应用层
  ↓ kmalloc()/kmem_cache_alloc()
Slab分配器 (SLUB/SLOB/Slab)
  ↓ alloc_pages()/free_pages()
Buddy System
  ↓ 物理页分配
物理内存管理器（由固件/BIOS构建）

• Buddy System负责：页级物理内存分配、碎片抗理、NUMA感知
• Slab分配器负责：细粒度对象分配（几十字节到2^11字节）、对齐缓存、着色（color）优化
• Kmalloc：≥页大小的请求直接下发给Buddy；<页大小则通过Slab从Buddy获取大块再拆分

关键工程考量：Buddy System缺乏对象级缓存能力——如果频繁分配释放少量字节，会不断在"请求1页→使用小块→归还1页"之间循环，产生严重的页级碎片（pgalloc/pgfault抖动）。这正是Slab要解决的。

十二、总结

Buddy System是一个精巧的工程艺术品，它的核心机制可以用一句话概括："拆分时对半，回收时合并伙伴"。围绕这一核心，Linux内核演化出了一整套抗碎片化、NUMA优化、Per-CPU加速、水位控制的基础设施。

理解Buddy System，就打开了深入理解以下主题的大门：

1. 透明大页（THP）如何利用高阶页分配实现低TLB miss
2. KSM如何依赖伙伴系统的迁移机制实现页面合并
3. 内存热插拔时页面如何在Node间迁移
4. CMA（连续内存分配器）如何在启动阶段为设备预留连续内存
5. 实时系统中内存延迟的上界分析方法

在下一篇文章中，我们将深入探讨Slub分配器的内部实现，以及内核对象生命周期的内存管理。

---

本文基于 Linux 6.x 内核源码分析整理，重点关注 Buddy System 在现代多核/NUMA系统下的最新演进。