📚 课程目录第4章 Buddy数据结构详解

4. Buddy 数据结构详解：free_area 数组、struct page 的 flags 与 lru 链表、MAX_ORDER 配置

Buddy 分配器的核心数据结构围绕 free_area 数组、struct page 的元数据字段以及 MAX_ORDER 编译常量展开。理解这三者的协作关系，是掌握 Buddy 分配与合并机制的基础。

4.1 free_area 数组：空闲块的组织核心

free_area 是 Buddy 分配器管理空闲内存块的主数据结构，定义在 include/linux/mmzone.h 中。每个内存域（zone）都包含一个 free_area 数组，数组的每个索引对应一种 order（阶），即 2^order 个连续物理页框。

字段	类型	说明
`free_list[MIGRATE_TYPES]`	`struct list_head`	按迁移类型（MIGRATE_UNMOVABLE、MIGRATE_RECLAIMABLE、MIGRATE_MOVABLE 等）分组的空闲页块链表
`nr_free`	`unsigned long`	当前 order 下所有迁移类型链表中空闲块的总数（注意：是块数，不是页数）

数组索引 i 对应的 free_area[i] 管理大小为 2ⁱ 页的连续块。例如 free_area[0] 管理单页块，free_area[3] 管理 8 页块。

  关键点： 分配时从请求 order 对应的链表开始搜索；若当前 order 无空闲块，则向更高 order 查找，找到后逐级分裂。释放时检查相邻 buddy 块是否空闲，若空闲则合并并上移 order。

4.2 struct page 的 flags 与 lru 链表

每个物理页框对应一个 struct page 实例，Buddy 分配器利用其中的 flags 字段和 lru 链表节点来追踪页面的状态与归属。

4.2.1 flags 字段的关键位

flags 是一个 unsigned long 位图，每个比特位表示页面的某种属性。Buddy 分配器最关心的标志位包括：

PG_buddy（第 19 位）：标记该页框属于 Buddy 分配器的空闲块。当页面被分配出去时，此位被清除。
PG_private（第 11 位）：表示 page->private 字段有效。对于 Buddy 页面，private 存储该页块所属的 order。
PG_compound（第 14 位）：用于复合页（compound page），Buddy 分配器在分配高阶块时也会用到。
PG_slab（第 8 位）：标记页面被 Slab 分配器使用，Buddy 分配器在回收页面时会检查此位。

调试技巧： 在 /proc/pagetypeinfo 中可以看到每个迁移类型下各 order 的空闲块数量。若某个 order 的 nr_free 异常，可检查对应页面的 PG_buddy 位是否一致。

4.2.2 lru 链表：空闲页块的串联结构

struct page 中的 lru 字段（类型 struct list_head）在 Buddy 分配器中扮演双重角色：

空闲时： 作为 free_area 链表的节点，将同一 order 的空闲页块串联起来。
分配后： 被其他子系统复用（如 LRU 回收链表、匿名页链表等）。

Buddy 分配器通过 list_add() 和 list_del() 操作 lru 指针来维护空闲链表。当页面被分配时，lru 从 free_area 链表中摘除；释放时重新挂入。

4.3 MAX_ORDER 配置与影响

MAX_ORDER 是编译时宏，定义在 include/linux/mmzone.h 中，默认值为 11。它决定了 free_area 数组的大小，即 Buddy 分配器支持的最大连续页块阶数。

配置项	默认值	含义
`MAX_ORDER`	11	free_area 数组元素个数，索引范围 0 ~ (MAX_ORDER-1)
最大连续页数	2^{(MAX_ORDER-1)} = 1024 页	对应 4MB 连续物理内存（页大小 4KB）
最小分配单元	2⁰ = 1 页	order 0 对应单页

注意事项： 增大 MAX_ORDER 会扩大 free_area 数组，增加内存开销；同时高阶块的分裂与合并操作更频繁，可能影响分配延迟。嵌入式系统可减小 MAX_ORDER 以节省内存。修改后需重新编译内核。

4.4 数据结构关系图

下图展示了 free_area 数组、struct page 的 lru 链表以及 MAX_ORDER 之间的协作关系：

4.5 迁移类型与 free_list 细化

为了减少内存碎片，Buddy 分配器将空闲链表按 迁移类型（MIGRATE_TYPES）进一步细分。每个 free_area 元素包含多个 free_list，每种迁移类型一个链表。

迁移类型	用途	典型页面
MIGRATE_UNMOVABLE	不可迁移的页面	内核代码、页表、slab 分配的内存
MIGRATE_RECLAIMABLE	可回收但不可迁移的页面	文件系统元数据缓存
MIGRATE_MOVABLE	可迁移的页面	用户空间匿名页、文件页
MIGRATE_PCPTYPES	每 CPU 页框缓存类型	热页缓存
MIGRATE_CMA	连续内存分配器预留	DMA 大块内存
MIGRATE_ISOLATE	隔离页（用于内存热插拔）	正在迁移的页面

  实践要点： 通过 /proc/pagetypeinfo 可以观察每个迁移类型下各 order 的空闲块分布。若某个迁移类型的某个 order 长期为空，可能表明该类型的内存分配压力较大或碎片严重。

4.6 代码结构示例

以下代码展示了 free_area 在 struct zone 中的定义以及 MAX_ORDER 的典型配置：

/* include/linux/mmzone.h */
#define MAX_ORDER 11

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

struct zone {
    /* ... */
    struct free_area    free_area[MAX_ORDER];
    /* ... */
};

Buddy 分配器通过 __rmqueue() 函数从 free_area 中分配页面，通过 __free_one_page() 释放并尝试合并。这两个函数的核心逻辑就是遍历 free_area 数组、操作 lru 链表、检查 PG_buddy 标志位。