Linux内存管理子系统源码分析：Buddy System整体设计

第7章：Buddy System整体设计——Linux到底怎么管理空闲物理页？

前面几章已经把Linux物理内存的基本组织关系建立起来了：

System
  ↓
Node（pg_data_t）
  ↓
Zone（struct zone）
  ↓
Page Frame（struct page）

但知道系统中有哪些物理页，还不等于知道如何分配物理页。内核还必须持续回答下面几个问题：

哪些物理页当前空闲？
这些空闲页能组成多大的连续物理块？
申请小块时，怎样从大块中拆出来？
释放小块时，怎样重新恢复成大块？
为什么总空闲内存很多，高阶分配仍可能失败？

解决这些问题的核心机制，就是Buddy System（伙伴系统）。

Buddy System把连续物理页按2^order的大小组织起来。分配时可以把较大的空闲块逐级拆分，释放时可以把互为伙伴的空闲块逐级合并。

本章先建立算法模型、数据结构和设计边界。下一章再沿着alloc_pages()进入真实的Linux物理页分配主链。

0. 源码基线与阅读边界

本文以Linux v6.1正式版本为基线：

source:
  repository: https://github.com/torvalds/linux
  tag: v6.1
  commit: 830b3c68c1fb1e9176028d02ef86f3cf76aa2476
  architecture: generic MM，示例默认4KiB PAGE_SIZE
  config: 未绑定单一defconfig；涉及条件编译处单独说明

主要源码位置：

include/linux/mmzone.h
    struct zone
    struct free_area
    MAX_ORDER
    enum migratetype

include/linux/page-flags.h
    PageBuddy相关操作

mm/page_alloc.c
    空闲链表维护
    split
    Buddy分配
    Buddy释放与merge
    PCP与Buddy之间的批量转移

本文只回答Buddy System本身怎样组织连续空闲物理页。下面这些内容不在本章展开：

GFP如何确定目标Zone
Zonelist如何回退
Watermark完整判断过程
直接回收与OOM完整路径
Compaction的逐函数实现
alloc_pages()的完整慢速路径

这些机制会在后续章节单独分析。

本文使用三种提示：

1
2
3

【源码事实】目标v6.1源码可以直接确认的实现。
【简化模型】为了先建立心智模型而省略部分分支。
【工程提醒】调试、性能或稳定性中容易踩坑的地方。

7.1 为什么不能只维护一个空闲页链表

先从最简单的方案开始。假设一个Zone中的所有空闲页都挂在同一条链表上：

free_pages
    │
    ▼
page → page → page → page → page → ...

如果只申请一页，这个模型非常简单：

1
2
3

取出链表头
    ↓
返回一个struct page

但内核不只需要单页，还可能需要多个物理地址连续的页面。例如申请8个连续页，需要找到类似下面的PFN区间：

PFN 100
PFN 101
PFN 102
PFN 103
PFN 104
PFN 105
PFN 106
PFN 107

“找到8个空闲页”和“找到8个连续空闲页”是两个完全不同的问题：

场景A：F F F F F F F F
       可以组成8页连续块

场景B：F U F U F U F U F U F U F U F U
       空闲页数量同样是8，但连2页连续块都没有

其中：

1 2	`F = Free U = Used`

即使把单链表按PFN排序，申请大块时仍然需要扫描链表、计算连续长度；释放时为了保持顺序，也要寻找插入位置。Zone包含数百万个页面时，这种处理并不理想。

内核真正需要的数据结构应该能够直接回答：

现在有没有1页连续块？
有没有2页连续块？
有没有4页连续块？
有没有8页连续块？

Buddy System就是按这个思路组织空闲页的。

单一空闲页链表主要描述“哪些页空闲”；Buddy System进一步描述“这些空闲页组成了哪些大小的连续物理块”。

7.2 Buddy System的核心思想

Buddy System只管理大小为2的幂次方的连续页块：

1 page
2 pages
4 pages
8 pages
16 pages
...

这样，一个大块总能平均拆成两个同样大小的小块：

           8 pages
          /       \
      4 pages    4 pages
      /   \       /   \
  2 pages 2 pages 2 pages 2 pages
   /  \
1 page 1 page

同一个父块拆出来的两个子块互为伙伴，也就是Buddy。

Buddy System包含两个方向相反的操作：

1
2
3

分配：大块 → split → 小块

释放：小块 + buddy → merge → 大块

假设最初有8个连续空闲页：

1	`[0 1 2 3 4 5 6 7]`

它可以作为一个8页空闲块管理。申请2页时，先拆成两个4页块，再把其中一个4页块拆成两个2页块：

         [0........7]
               │ split
      ┌────────┴────────┐
      ▼                 ▼
   [0..3]             [4..7]
      │ split
  ┌───┴───┐
  ▼       ▼
[0,1]   [2,3]
  │
return

最终状态：

allocated:
    [0,1]

free:
    [2,3]   2页块
    [4..7]  4页块

当[0,1]被释放后，它与[2,3]重新合并成[0..3]；如果[4..7]仍然空闲，还能继续合并为[0..7]。

这就是Buddy System最核心的循环：

allocate
   ↓
寻找最小但足够大的块
   ↓
必要时split

free
   ↓
检查唯一的buddy
   ↓
必要时merge并继续向上

7.3 order到底是什么

Buddy使用order表示块的阶数：

1 2	`pages = 2^order bytes = 2^order × PAGE_SIZE`

假设PAGE_SIZE = 4KiB：

order	连续页数	连续物理内存大小
0	1	4KiB
1	2	8KiB
2	4	16KiB
3	8	32KiB
4	16	64KiB
5	32	128KiB
8	256	1MiB
10	1024	4MiB

所以：

1 2	`order 3 ≠ 3 pages order 3 = 2³ pages = 8 pages`

调用：

1
2
3

struct page *page;

page = alloc_pages(GFP_KERNEL, 3);

语义是申请8个连续物理页，返回值指向整个块的第一个struct page。

MAX_ORDER的边界

Linux v6.1的include/linux/mmzone.h中：

#ifndef CONFIG_ARCH_FORCE_MAX_ORDER
#define MAX_ORDER 11
#else
#define MAX_ORDER CONFIG_ARCH_FORCE_MAX_ORDER
#endif

#define MAX_ORDER_NR_PAGES (1 << (MAX_ORDER - 1))

要注意：

1 2	`free_area[]有效下标：0 ... MAX_ORDER - 1 最大块order：MAX_ORDER - 1`

默认MAX_ORDER=11时，最大order为10，对应1024页；4KiB页面下就是4MiB连续物理内存。但架构可以通过CONFIG_ARCH_FORCE_MAX_ORDER改变它，因此不要死记所有平台最大块都是4MiB。

v6.1还定义：

1	`#define PAGE_ALLOC_COSTLY_ORDER 3`

它表示从更高order开始，分配被认为成本和失败风险明显增加。它不是Buddy能够管理的最大order。

7.4 free_area[]是什么

Linux的Buddy不是整个系统共享一套全局链表，而是每个Zone拥有自己的Buddy状态。

struct zone中的核心字段是：

struct zone {
    ...

    /* free areas of different sizes */
    struct free_area free_area[MAX_ORDER];

    /* Primarily protects free_area */
    spinlock_t lock;

    ...
};

每个数组下标对应一个order：

zone->free_area[0]  → 1页块
zone->free_area[1]  → 2页块
zone->free_area[2]  → 4页块
zone->free_area[3]  → 8页块
...

struct free_area定义为：

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

它包含两类状态：

free_list[]
    该order下按migratetype分类的空闲块链表

nr_free
    该order下的空闲块数量，不是空闲页数量

例如：

1	`free_area[3].nr_free = 10`

表示有10个order-3空闲块。每个块8页，因此共代表：

1	`10 × 2³ = 80 pages`

4KiB页面下为：

1	`80 × 4KiB = 320KiB`

整体数据结构如下：

struct zone
   │
   └── free_area[MAX_ORDER]
          │
          ├── free_area[0]
          │      ├── free_list[UNMOVABLE]
          │      ├── free_list[MOVABLE]
          │      └── free_list[RECLAIMABLE]
          │
          ├── free_area[1]
          │      ├── free_list[UNMOVABLE]
          │      ├── free_list[MOVABLE]
          │      └── free_list[RECLAIMABLE]
          │
          └── ...

为什么Buddy是per-Zone的

不同Zone中的物理页具有不同使用限制。即使ZONE_DMA32的最后一块与ZONE_NORMAL的第一块在物理地址上连续，它们也不能合并：

ZONE_DMA32                     ZONE_NORMAL
[最后一个空闲块] [第一个空闲块]
                  ▲
                  │ Zone边界，禁止合并

否则一个块会同时跨越两种分配能力，Zone的水位、回退和DMA约束都无法继续正确表达。

7.5 order-0到高阶内存块如何组织

假设一个Zone中的PFN 0～15全部空闲，并且这些PFN满足一个order-4块的对齐和边界条件。

最紧凑的表示不是16个order-0块，而是：

1 2	`free_area[4] └── [PFN 0................................15]`

同一组页面不会同时以多种order重复挂链。例如它作为一个order-4块挂入链表后，不会再把其中每个页面同时挂到free_area[0]。

当order-4块被拆分时，较小的剩余伙伴才会进入较低order链表：

分配order-2：

order 4: [0................15]
                   │ split
order 3: [0......7] [8.....15]
             │ split
order 2: [0..3] [4..7]
          │
        return

剩余：
free_area[2] → [4..7]
free_area[3] → [8..15]

此时：

1	`free_area[4]中不再有原来的[0..15]`

因为这个大块已经被拆开，不能再作为完整order-4空闲块分配。

7.6 分配时为什么要split

申请order-N时，Buddy先检查目标order。如果没有，就从目标order向上寻找第一个可用块。

【简化模型】

for current_order = requested_order ... MAX_ORDER-1
    if free_area[current_order]有块
        取出
        拆到requested_order
        返回

Linux v6.1中的核心函数是__rmqueue_smallest()：

static __always_inline
struct page *__rmqueue_smallest(struct zone *zone,
                                unsigned int order,
                                int migratetype)
{
    unsigned int current_order;
    struct free_area *area;
    struct page *page;

    for (current_order = order;
         current_order < MAX_ORDER;
         ++current_order) {

        area = &zone->free_area[current_order];
        page = get_page_from_free_area(area, migratetype);
        if (!page)
            continue;

        del_page_from_free_list(page, zone, current_order);
        expand(zone, page, order, current_order, migratetype);
        ...
        return page;
    }

    return NULL;
}

这段代码解决两个问题：

1 2	`1. 从requested order向上找，而不是直接拿最大块 2. 找到更大块后调用expand()逐级拆分`

为什么不直接从最大块开始？因为申请一页时如果总去拆最大的块，会造成不必要的拆分，过早破坏高阶连续内存。

整个分配和合并的逻辑如下

expand()做了什么

假设：

1 2	`low = 1，需要order-1 high = 3，找到order-3`

expand()逐级执行：

1 2	`order 3 → order 2 order 2 → order 1`

每次把一半留给后续拆分，另一半标记为空闲伙伴并放回对应的free_area[]：

8 pages
   ├── 4 pages继续拆
   └── 4 pages放入free_area[2]

4 pages
   ├── 2 pages返回
   └── 2 pages放入free_area[1]

因此split不会丢失页面，它只是改变空闲页的组织阶数。

7.7 释放时为什么能merge

释放一个块时，如果它的伙伴块满足合并条件，就能合成高一阶的块：

1
2
3

order-N + order-N
        ↓
    order-(N+1)

例如：

1
2
3

[0,1] + [2,3]
       ↓
     [0..3]

然后继续检查[0..3]的order-2伙伴：

1
2
3

[0..3] + [4..7]
          ↓
        [0..7]

Linux v6.1的核心合并函数是__free_one_page()。它的主干可以概括为：

当前page、pfn、order、zone、migratetype
        ↓
检查起始PFN对齐和Zone边界
        ↓
find_buddy_page_pfn()
        ↓
没有可合并buddy？──是──→ 停止合并
        │
        否
        ↓
从当前order空闲链表移除buddy
        ↓
计算合并块的较低起始PFN
        ↓
order++
        ↓
继续尝试更高阶合并
        ↓
将最终块加入free_area[order]

能够合并通常至少要求：

地址上是真正的伙伴
buddy当前在Buddy中空闲
buddy记录的order相同
没有跨越Zone边界
页面状态允许合并
pageblock/migratetype规则允许合并

所以“两个块物理相邻”并不自动等于“可以合并”。

7.8 buddy到底怎么计算

对一个order-N块来说：

1	`block_size = 1 << order // 单位：page`

它的伙伴起始PFN可以用下面的数学模型理解：

1	`buddy_pfn = pfn ^ (1 << order)`

例1：PFN 8，order 2

1 2	`block_size = 1 << 2 = 4 pages buddy_pfn = 8 ^ 4 = 12`

所以：

1
2
3

当前块：[8..11]
伙伴块：[12..15]
合并后：[8..15]，成为order-3

例2：PFN 12，order 2

1	`buddy_pfn = 12 ^ 4 = 8`

又回到PFN 8，因此伙伴关系是对称的。

为什么异或有效

一个order-N块的伙伴，只需要翻转起始PFN中代表该块大小的那一位：

1	`order 2 → 翻转数值4对应的bit`

低于这一位的bit必须为0，这正是块对齐条件。高位决定当前父区域，翻转这一位就在父区域的左右两半之间切换。

7.9 为什么块大小必须是2的幂

2的幂使Buddy具有三个关键性质。

只有一种等分方式

1
2
3

8 → 4 + 4
4 → 2 + 2
2 → 1 + 1

如果允许任意大小，例如10页，拆分可能是：

拆分和合并策略会复杂很多。

每个块只有一个伙伴

在给定order下，一个块只有唯一伙伴可以与它组成高一阶块，所以查找不需要遍历所有相邻空闲块。

对齐关系简单

order-N块起始PFN必须满足：

1	`pfn % (1 << order) == 0`

等价位运算检查：

1	`pfn & ((1 << order) - 1)`

在v6.1的__free_one_page()中可以看到对应的调试断言：

1	`VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page);`

如果order-2块从PFN 6开始，范围将是[6..9]，它跨过了标准4页边界，伙伴层次无法稳定建立。因此合法起点是：

1	`0、4、8、12、16……`

7.10 struct page在Buddy中承担什么角色

Buddy管理的是一整块连续物理页，但不需要把块中的每个struct page都挂入空闲链表。

例如order-3块：

PFN 100 101 102 103 104 105 106 107
     ▲
     │
块首页struct page代表整个8页空闲块

空闲链表中挂的是块首页：

free_area[3].free_list[migratetype]
       │
       ▼
struct page(PFN 100)
       │
       └── 代表PFN 100～107

Linux v6.1中，加入空闲链表的核心动作类似：

1
2
3

list_add(&page->buddy_list,
         &area->free_list[migratetype]);
area->nr_free++;

这里的page是空闲块首页，buddy_list用于把这个块连接到对应order、对应migratetype的链表。

因此需要区分：

1
2
3

Zone管理这段范围内的所有页面

free_area[]只组织当前空闲块的首页

7.11 PageBuddy、private与order

Linux需要从块首页判断：

1 2	`它是否真的位于Buddy空闲链表？它当前代表哪个order的块？`

Linux v6.1使用PageBuddy(page)表示该页是Buddy空闲块的代表页。include/linux/page-flags.h中的注释明确说明：

1	`PageBuddy() indicates that the page is free and in the buddy system`

设置空闲块状态的代码为：

static inline void set_buddy_order(struct page *page,
                                   unsigned int order)
{
    set_page_private(page, order);
    __SetPageBuddy(page);
}

所以在v6.1中：

PageBuddy(page)
    表示page是Buddy空闲块的首页

page_private(page)
    保存该空闲块的order

page->buddy_list
    把空闲块首页挂入free_area[order]链表

从空闲链表取出块时，会反向清理这些状态：

list_del(&page->buddy_list);
__ClearPageBuddy(page);
set_page_private(page, 0);
zone->free_area[order].nr_free--;

【工程提醒】

这里的page_private()是struct page字段在“Buddy空闲块首页”这一生命周期阶段的复用。它不意味着所有已分配页面的private字段始终表示Buddy order。

同样需要区分：

1	`Buddy空闲块的order`

与：

1	`已分配compound page记录的compound_order`

二者处于不同状态和用途，不能混为一谈。

7.12 Migratetype为什么存在

如果Buddy只按order管理，系统长期运行后容易产生外部碎片。

假设不同可迁移属性的页面交叉分配：

1	`U M U M U M U M`

其中：

1 2	`U = Unmovable，不容易迁移 M = Movable，可以迁移`

以后即使把所有M迁走：

1	`U _ U _ U _ U _`

仍然无法形成大的连续空闲区，因为不可移动页面像钉子一样散布在中间。

如果一开始尽量分类放置：

1	`U U U U \| M M M M`

迁移M以后：

1	`U U U U \| _ _ _ _`

右侧更容易恢复为高阶Buddy块。

因此migratetype的目标是：

尽量让迁移属性相似的分配集中在相同pageblock中，降低不可移动页面长期切碎大块连续空间的概率。

Linux v6.1中的主要类型包括：

enum migratetype {
    MIGRATE_UNMOVABLE,
    MIGRATE_MOVABLE,
    MIGRATE_RECLAIMABLE,
    MIGRATE_PCPTYPES,
    MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
#ifdef CONFIG_CMA
    MIGRATE_CMA,
#endif
#ifdef CONFIG_MEMORY_ISOLATION
    MIGRATE_ISOLATE,
#endif
    MIGRATE_TYPES
};

基础心智模型：

MIGRATE_UNMOVABLE
    难以迁移的内核分配

MIGRATE_MOVABLE
    可以通过页面迁移改变物理位置的页面

MIGRATE_RECLAIMABLE
    在内存压力下可回收的一类内核分配

MIGRATE_HIGHATOMIC
    为高阶原子分配保留的页面块

MIGRATE_CMA
    CONFIG_CMA下供连续内存分配机制使用

MIGRATE_ISOLATE
    CONFIG_MEMORY_ISOLATION下隔离页面块，不参与普通分配

【简化模型】

第一次学习先重点区分UNMOVABLE / MOVABLE / RECLAIMABLE。其他类型涉及高阶原子储备、CMA和内存隔离策略。

7.13 free_list[MIGRATE_TYPES]的意义

free_area[order]不是只有一条链表，而是：

1	`struct list_head free_list[MIGRATE_TYPES];`

所以Buddy的分类是二维的：

1 2	`第一维：order 第二维：migratetype`

例如：

free_area[2]
   ├── free_list[MIGRATE_UNMOVABLE]
   ├── free_list[MIGRATE_MOVABLE]
   ├── free_list[MIGRATE_RECLAIMABLE]
   ├── free_list[MIGRATE_HIGHATOMIC]
   └── 条件类型...

这些链表中的块大小完全相同，都是4页；差别在于它们所在pageblock的迁移属性和分配策略。

请求先尝试期望的migratetype。如果目标链表耗尽，分配器还可能按照fallback规则从其他可兼容类型取块。v6.1中基础fallback顺序类似：

static int fallbacks[MIGRATE_TYPES][3] = {
    [MIGRATE_UNMOVABLE] = {
        MIGRATE_RECLAIMABLE,
        MIGRATE_MOVABLE,
        MIGRATE_TYPES
    },
    [MIGRATE_MOVABLE] = {
        MIGRATE_RECLAIMABLE,
        MIGRATE_UNMOVABLE,
        MIGRATE_TYPES
    },
    [MIGRATE_RECLAIMABLE] = {
        MIGRATE_UNMOVABLE,
        MIGRATE_MOVABLE,
        MIGRATE_TYPES
    },
};

fallback提升了当前分配成功率，但也可能污染其他迁移类型的pageblock、增加未来碎片风险。这里体现了典型的权衡：

1
2
3

当前分配成功率
        vs
长期连续内存质量

7.14 外部碎片是什么

外部碎片是指：

空闲空间总量可能足够，但它被已使用页面分割成许多小块，无法满足所需的连续分配。

例如：

1	`F U F U F U F U`

这里有4个空闲页，但没有2个连续空闲页。因此：

1 2	`order-0申请：可能成功 order-1申请：失败`

外部碎片与内部碎片不同：

外部碎片
    空闲空间分散，连续性不足

内部碎片
    分配块大于实际需求，块内部存在浪费

例如需要5页，但Buddy只能申请8页的order-3块，多出来的3页属于内部浪费。Linux也提供alloc_pages_exact()等接口，在部分场景下申请较大块后释放尾部多余页面，但底层仍然绕不开Buddy的2次幂组织。

7.15 为什么还有很多free memory却申请不到高阶页

假设系统还有500MiB空闲内存，但这些内存主要由大量4KiB和8KiB小块组成。现在申请：

1
2
3

order 8
= 256 pages
= 1MiB连续物理内存（PAGE_SIZE=4KiB）

如果没有任何一个1MiB连续空闲区，申请仍然会失败。

因此：

总free memory充足
        ≠
目标Zone中有足够内存
        ≠
存在目标order连续块

排查高阶分配失败时，不能只看：

free -h

还应观察：

1 2	`cat /proc/zoneinfo cat /proc/buddyinfo`

分别判断：

Zone水位是否不足？
正确Zone是否还有可用页？
高阶空闲块是否已经耗尽？
是否只是大量低阶块仍然存在？

7.16 Compaction和Buddy的关系

Buddy能够合并的前提是伙伴都已经空闲。如果连续范围中夹着正在使用的可移动页面，Buddy不能直接越过它进行合并。

Compaction（内存规整）尝试迁移可移动页面，把分散的空闲页集中起来：

Before:

F M F M F M F M

        ↓ migrate

After:

M M M M F F F F

右侧连续空闲页被释放回Buddy后，就可能逐级合并成更高order。

必须区分Reclaim和Compaction：

Reclaim
    将可回收页面变为空闲页
    主要解决“空闲页数量够不够”

Compaction
    搬迁可移动页面，集中空闲空间
    主要解决“空闲页连续不连续”

二者可能协同工作，但不是同一种机制。

Buddy与Compaction的关系是：

Compaction创造连续空闲条件
        ↓
页面释放回Buddy
        ↓
Buddy重新merge成高阶块

7.17 PCP与Buddy的关系

如果每次小页分配都直接修改zone->free_area[]，多个CPU会频繁竞争zone->lock：

CPU0 ─┐
CPU1 ─┼──→ zone->lock → free_area[]
CPU2 ─┤
CPU3 ─┘

Linux在Buddy前面增加了Per-CPU Pageset（PCP）：

CPU本地小页分配
       ↓
      PCP
       ↓ 不足时批量补充
Zone Buddy free_area[]

释放小页时也可以先进入本CPU的PCP，积累到一定程度再批量归还Buddy。这样把许多单次操作聚合成少量批量操作，降低Zone共享锁竞争。

【简化模型】

常见介绍会说“order-0优先走PCP”。这有助于理解PCP的主要用途，但Linux v6.1真实实现更宽一些：

static inline bool pcp_allowed_order(unsigned int order)
{
    if (order <= PAGE_ALLOC_COSTLY_ORDER)
        return true;
#ifdef CONFIG_TRANSPARENT_HUGEPAGE
    if (order == pageblock_order)
        return true;
#endif
    return false;
}

默认PAGE_ALLOC_COSTLY_ORDER=3，所以符合条件的低阶请求不只order-0能经过PCP；特定THP配置还有额外条件路径。

PCP并没有取代Buddy：

PCP
    每CPU快速缓存，优化高频路径

Buddy
    Zone级连续空闲页主仓库

PCP页面暂时离开Buddy链表，因此阅读/proc/buddyinfo时也要意识到，它展示的是Buddy各阶空闲块，不等价于系统所有可快速使用页面的完整视图。

7.18 Buddy分配的大体源码主链

本章只建立Buddy相关主干，完整alloc_pages()调用链留到下一章。

Linux v6.1中可以先记住：

alloc_pages()
    ↓
__alloc_pages()
    ↓
get_page_from_freelist()
    ↓
rmqueue()
    ├── rmqueue_pcplist()
    │      └── PCP快速路径
    │
    └── rmqueue_buddy()
           ↓
         __rmqueue()
           ↓
     __rmqueue_smallest()
           ↓
 zone->free_area[current_order]
           ↓
        expand()

其中真正体现基础Buddy算法的是：

__rmqueue_smallest()
    从requested order向上找第一个可用块

expand()
    将较大块逐级拆到目标order

真实代码还要处理：

migratetype fallback
MIGRATE_HIGHATOMIC
CMA约束
页面状态检查
统计与tracepoint
Zone锁

第一遍不要把这些分支与Buddy基本算法混在一起。先抓住主状态变化：

空闲块从高阶链表删除
        ↓
拆出的伙伴加入低阶链表
        ↓
目标块离开Buddy并返回

7.19 Buddy释放的大体源码主链

释放路径需要区分“先进入PCP”和“最终归还Buddy”。概念主线如下：

__free_pages()
    ↓
free_the_page()
    ├── 符合PCP条件
    │      ↓
    │  free_unref_page()
    │      ↓
    │  进入PCP
    │      ↓ 达到批量归还条件
    │  free_pcppages_bulk()
    │
    └── 不走PCP
           ↓
     __free_pages_ok()

最终回到Zone Buddy时会进入：

free_one_page()
    ↓ 获取zone->lock
__free_one_page()
    ↓
find_buddy_page_pfn()
    ↓
merge loop
    ↓
add_to_free_list()

__free_one_page()才是最纯粹的Buddy合并核心。其源码注释明确说明：每一阶链表保存连续1 << order页块的首页，首页设置PageBuddy，order记录在page_private(page)中。

释放时最关键的状态变化：

当前块变为空闲候选
        ↓
查找同阶空闲buddy
        ↓
从free list删除buddy
        ↓
清理buddy的PageBuddy/order元数据
        ↓
选择较低PFN作为新块首页
        ↓
order++继续
        ↓
最终首页设置PageBuddy/order并挂回free list

7.20 /proc/buddyinfo如何读

运行：

1	`cat /proc/buddyinfo`

可能得到：

1 2	`Node 0, zone DMA 3 2 1 0 0 ... Node 0, zone Normal 1024 512 128 64 10 ...`

一行对应：

1	`一个Node中的一个Zone`

数字列从左到右依次对应：

order 0
order 1
order 2
order 3
...

数字表示该order有多少个空闲块，而不是多少个空闲页。

例如：

1	`Node 0, zone Normal 10 4 2 1`

代表：

order 0：10个块，每块1页  → 10页
order 1： 4个块，每块2页  →  8页
order 2： 2个块，每块4页  →  8页
order 3： 1个块，每块8页  →  8页

总计：

1	`10 + 8 + 8 + 8 = 34 pages`

4KiB页面下：

1	`34 × 4KiB = 136KiB`

通用公式：

FreePages
= Σ nr_free(order) × 2^order

FreeBytes
= Σ nr_free(order) × 2^order × PAGE_SIZE

怎样观察碎片趋势

如果看到：

1 2	`低order列仍然很多高order列长期为0或非常少`

说明这个Zone仍有空闲页，但大块连续物理内存比较稀缺。这是碎片风险的重要信号，但不能仅凭一次快照断言所有高阶分配必然失败，因为分配器还可能进行回收、规整或从其他Zone回退。

7.21 实验：手工模拟split与merge

这一章最有效的实验不是背函数，而是自己模拟一次状态变化。

实验问题

假设：

PAGE_SIZE = 4KiB
总页数 = 16
初始PFN = 0～15全部空闲
最大块 = order 4

依次执行：

1. alloc(order 2)
2. alloc(order 1)
3. free(PFN 4, order 1)
4. free(PFN 0, order 2)

预测每一步的free_area[]。

初始状态

order 0:
order 1:
order 2:
order 3:
order 4: [0..15]

第一步：alloc(order 2)

拆分过程：

[0..15]
   ↓
[0..7] [8..15]
   ↓
[0..3] [4..7]

返回[0..3]：

allocated: [0..3]

order 2: [4..7]
order 3: [8..15]

第二步：alloc(order 1)

从[4..7]拆分：

1
2
3

[4..7]
   ↓
[4,5] [6,7]

返回[4,5]：

allocated: [0..3] [4,5]

order 1: [6,7]
order 3: [8..15]

第三步：free(PFN 4, order 1)

PFN 4对应块[4,5]，它的同阶伙伴是[6,7]，两者合并：

1	`[4,5] + [6,7] → [4..7]`

状态：

allocated: [0..3]

order 2: [4..7]
order 3: [8..15]

第四步：free(PFN 0, order 2)

先合并：

1	`[0..3] + [4..7] → [0..7]`

再合并：

1	`[0..7] + [8..15] → [0..15]`

最终恢复初始状态：

1	`order 4: [0..15]`

可选：观察真实系统

先保存快照：

1 2	`cat /proc/buddyinfo > /tmp/buddy.before cat /proc/zoneinfo > /tmp/zone.before`

运行自己的正常工作负载后再次保存：

cat /proc/buddyinfo > /tmp/buddy.after
cat /proc/zoneinfo  > /tmp/zone.after

diff -u /tmp/buddy.before /tmp/buddy.after

预测：Buddy各阶数量会随系统活动发生变化；单次快照只是瞬时状态。

如果要用内核模块直接测试alloc_pages(GFP_KERNEL, order)，应只在可重启的开发环境中进行，并保证每个成功分配都按原order释放。不要在生产设备上盲目发起大量高阶分配。

7.22 常见误区

误区1：order 3表示3个页面

错误：

1	`order 3 = 2³ = 8 pages`

误区2：整个系统只有一个Buddy

错误。核心空闲链表位于struct zone中，因此是per-Zone Buddy：

1
2
3

Node 0 / ZONE_DMA32  → 一套free_area[]
Node 0 / ZONE_NORMAL → 另一套free_area[]
Node 1 / ZONE_NORMAL → 又一套free_area[]

误区3：每个空闲页都单独挂在对应链表

错误。一个高阶空闲块通常由首页struct page代表并挂链。

误区4：两个相邻空闲块一定能merge

错误。它们必须是同阶的真正伙伴，并满足Zone、pageblock和页面状态等约束。

误区5：free memory多，高阶分配一定成功

错误。高阶分配要求目标Zone中存在足够大的连续块。

误区6：Reclaim可以解决所有高阶失败

错误。Reclaim增加空闲页数量，但新空闲页仍可能分散。连续性问题通常还需要Compaction和页面迁移配合。

误区7：Compaction会凭空增加空闲内存

错误。Compaction主要搬移可迁移页面、集中空闲空间，不等价于释放更多页面。

误区8：PCP就是Buddy的一条普通链表

不准确。PCP是每CPU快速缓存，页面会在PCP和Zone Buddy之间批量转移，两者的锁、组织和作用范围不同。

误区9：`page_private()`永远保存Buddy order

错误。struct page字段会在不同生命周期和不同页面用途下复用；只有Buddy空闲块首页这一语境下，才能按本节方式解释。

7.23 性能与工程意义

高阶分配的成本增长

order越高：

要求连续页越多
      ↓
越容易受到外部碎片影响
      ↓
更可能触发migratetype fallback
      ↓
更可能触发Compaction或Reclaim
      ↓
延迟和失败概率上升

所以工程中应谨慎引入长期、频繁的高阶物理页申请。如果硬件和接口允许，可以考虑：

scatter-gather
DMA SG
vmalloc（虚拟连续而非物理连续）
分段缓冲区
CMA（确实需要大块DMA连续内存时）

具体选择取决于设备DMA能力、映射接口、访问性能和生命周期，不能简单认为哪种方案永远最好。

排查page allocation failure

遇到类似：

1	`page allocation failure: order:N`

至少应同时考虑：

请求order多大？
GFP标志允许做什么？
目标Node/Zone是什么？
Zone水位是否满足？
/proc/buddyinfo中对应高阶块是否存在？
是否在不可睡眠或原子上下文？
是否允许Reclaim和Compaction？
是否长期存在不可移动页造成的碎片？

free -h只能回答系统容量的一部分问题，不能直接回答目标Zone中是否存在连续高阶块。

并发与扩展性

zone->lock主要保护free_area[]。如果所有CPU每次分配一页都直接操作Buddy，锁竞争会非常严重。PCP通过批量补充和批量归还，把大量高频小分配挡在Zone共享锁之外。

所以Buddy与PCP体现了分层设计：

1 2	`PCP：优化常见、高频、本CPU路径 Buddy：维护全局于Zone的连续物理页结构`

7.24 本章总结

Buddy System是Linux物理页分配器中管理连续空闲物理页的核心机制。

每个Zone维护：

1	`struct free_area free_area[MAX_ORDER];`

free_area[order]管理大小为2^order页的连续空闲块，并通过：

1	`free_list[MIGRATE_TYPES]`

按迁移类型进一步分类。

分配时：

requested order
       ↓
从当前order向上查找
       ↓
找到最小可用高阶块
       ↓
expand()逐级split
       ↓
返回目标块

释放时：

释放块
   ↓
寻找同阶buddy
   ↓
buddy可合并？
   ├── 否：挂入当前order
   └── 是：merge、order++、继续

空闲块通常由首页struct page代表：

1
2
3

PageBuddy(page)   → 它是Buddy空闲块首页
page_private(page)→ v6.1中记录Buddy order
page->buddy_list  → 挂入对应free list

Buddy擅长快速分配、拆分和合并2^order大小的连续物理块，但不能彻底消除长期外部碎片。因此Linux还需要：

Migratetype
Page Migration
Compaction
Reclaim
PCP

分别改善长期布局、连续性、容量和并发性能。

一句话总结：

Buddy System关注的不只是“还剩多少空闲页”，更关注“这些空闲页当前能组成哪些大小的连续物理块”。

7.25 学完检查题

不要只判断“看懂了没有”，尽量不看正文完成下面的解释、推演和调试题。

概念解释

为什么只维护一个空闲页链表无法高效支持连续页分配？
order是什么？order 3表示多少页？
free_area[]位于什么结构中？为什么Buddy必须是per-Zone？
free_area[3].nr_free = 10表示多少个空闲页？
为什么块大小选择2的幂？
为什么两个物理相邻的空闲块不一定是buddy？
PageBuddy、page_private()和buddy_list分别承担什么角色？

手工推演

只有一个order-3空闲块时，申请order-1会发生哪些split？每个剩余伙伴进入哪个free_area[]？
PFN 8、order 2的伙伴起始PFN是多少？
PFN 12、order 2的伙伴起始PFN是多少？
为什么PFN 6不能作为标准order-2块的起点？
16个空闲页最初组成order-4块，先申请order-2，再申请order-1，画出剩余链表状态。

设计原因

migratetype为什么能降低长期外部碎片？
fallback为什么既能提高当前分配成功率，又可能伤害长期连续性？
Reclaim与Compaction分别解决什么问题？
PCP为什么能够降低zone->lock竞争？
为什么说PCP没有取代Buddy？

调试与预测

/proc/buddyinfo低阶列很多、高阶列全为0，说明什么？
系统还有500MiB free，order-8申请为什么仍可能失败？
order 5有3个block、PAGE_SIZE=4KiB，一共代表多少内存？
日志出现page allocation failure: order:5时，你会先收集哪些证据？
如果一个工作负载持续消耗高阶块，却释放成大量分散小块，你预测/proc/buddyinfo会怎样变化？

第20题答案用于自检：

1
2
3

3 × 2⁵ × 4KiB
= 3 × 32 × 4KiB
= 384KiB

如果能够不看正文独立画出下面两条路径，就说明本章的整体模型已经建立：

Zone
  ↓
free_area[order]
  ↓
higher-order block
  ↓ split
target block

free block
  ↓
find buddy
  ↓ merge
higher-order block

下一章：alloc_pages()分配主链

下一章开始追踪Linux v6.1真实的物理页分配路径：

alloc_pages()
    ↓
__alloc_pages()
    ↓
prepare_alloc_pages()
    ↓
get_page_from_freelist()
    ↓
rmqueue()
    ├── rmqueue_pcplist()
    └── rmqueue_buddy()
            ↓
      __rmqueue_smallest()
    ↓
struct page *

届时会把前面学过的概念真正串成一次分配：

GFP
 ↓
Zonelist
 ↓
Watermark
 ↓
PCP / Buddy
 ↓
struct page

参考源码与文档

Linux Kernel > Memory Management

#Linux Memory #Memory Management #Page Allocator #Buddy System

Linux内存管理子系统源码分析：Buddy System整体设计

https://cj0510.github.io/2026/10/07/Linux Kernel/Memory Management/Linux内存管理子系统源码分析-第7章-Buddy-System整体设计/

作者

CJ1018

发布于

2026年10月7日

许可协议

CC BY-NC-SA 4.0

Linux内存管理子系统源码分析：alloc_pages物理页分配上一篇

Agent Skill 原理与工程实践（十七）：循环、重试、Fallback 怎么设计下一篇

Linux内存管理子系统源码分析：Buddy System整体设计

第7章：Buddy System整体设计——Linux到底怎么管理空闲物理页？

0. 源码基线与阅读边界

7.1 为什么不能只维护一个空闲页链表

7.2 Buddy System的核心思想

7.3 order到底是什么

MAX_ORDER的边界

7.4 free_area[]是什么

为什么Buddy是per-Zone的

7.5 order-0到高阶内存块如何组织

7.6 分配时为什么要split

expand()做了什么

7.7 释放时为什么能merge

7.8 buddy到底怎么计算

例1：PFN 8，order 2

例2：PFN 12，order 2

为什么异或有效

7.9 为什么块大小必须是2的幂

只有一种等分方式

每个块只有一个伙伴

对齐关系简单

7.10 struct page在Buddy中承担什么角色

7.11 PageBuddy、private与order

7.12 Migratetype为什么存在

7.13 free_list[MIGRATE_TYPES]的意义

7.14 外部碎片是什么

7.15 为什么还有很多free memory却申请不到高阶页

7.16 Compaction和Buddy的关系

7.17 PCP与Buddy的关系

7.18 Buddy分配的大体源码主链

7.19 Buddy释放的大体源码主链

7.20 /proc/buddyinfo如何读

怎样观察碎片趋势

7.21 实验：手工模拟split与merge

实验问题

初始状态

第一步：alloc(order 2)

第二步：alloc(order 1)

第三步：free(PFN 4, order 1)

第四步：free(PFN 0, order 2)

可选：观察真实系统

7.22 常见误区

误区1：order 3表示3个页面

误区2：整个系统只有一个Buddy

误区3：每个空闲页都单独挂在对应链表

误区4：两个相邻空闲块一定能merge

误区5：free memory多，高阶分配一定成功

误区6：Reclaim可以解决所有高阶失败

误区7：Compaction会凭空增加空闲内存

误区8：PCP就是Buddy的一条普通链表

误区9：page_private()永远保存Buddy order

7.23 性能与工程意义

高阶分配的成本增长

排查page allocation failure

并发与扩展性

7.24 本章总结

7.25 学完检查题

概念解释

手工推演

设计原因

调试与预测

下一章：alloc_pages()分配主链

参考源码与文档

订阅博客更新

误区9：`page_private()`永远保存Buddy order