2^n 阶伙伴算法:Linux 内核 Buddy System 的分配、合并与拆分
- 2026-06-30 16:47:20
1. 一个具体问题：为什么内核分配 1 个 page 却能找到？
假设一台服务器刚启动，内核的某个 zone 里只剩一块 1MB 的空闲内存（order 8，256 个连续 page）。 此时一个进程申请 1 个 page（order 0）。内核不能把整块 1MB 分出去——它需要把这 256 个 page 拆开， 只给出 1 个，把剩下的 255 个重新挂回到对应 order 的链表上。
反过来，当这 255 个 page 陆续被释放回来时，内核如何知道它们恰好相邻，可以合并回 1MB？ 如果其中有一个 page 还被占用，合并链就在哪里断裂？
这就是 Buddy System 要解决的核心问题：在 2^n 粒度下，用 O(1) 的位运算找到"伙伴"，用 2^n 阶链表管理碎片。 本文以 Linux 7.0 源码为准，逐行拆解 mm/page_alloc.c 中 buddy 分配、合并、拆分的实现。
2. 源码位置
核心文件：
mm/page_alloc.c数据结构：
include/linux/mmzone.h（free_area, struct zone 的 free_area 字段）内联函数：
mm/internal.h（find_buddy_page_pfn, page_is_buddy）页标志：
include/linux/page-flags.h（PageBuddy）关键函数：
__rmqueue_smallest,expand,__free_one_page,find_buddy_page_pfn内核版本：Linux 7.0
3. 前置知识
理解 buddy system 需要以下概念：
Order：2^n 中的 n。order 0 = 1 page（4KB），order 1 = 2 pages（8KB），order 10 = 1024 pages（4MB）
MAX_PAGE_ORDER：默认 10，即 buddy system 最大管理 2^10 = 1024 个连续 page
NR_PAGE_ORDERS：MAX_PAGE_ORDER + 1 = 11，zone 中有 11 个阶的 free_list
Migrate Type：页面的迁移类型（UNMOVABLE / RECLAIMABLE / MOVABLE 等），每个 order 的 free_list 按 migratetype 分桶
PageBuddy：页面在 buddy 系统中的标志位，设置后表示该页面是空闲的且在 buddy 链表中
zone->lock：保护 buddy list 操作的自旋锁，所有对 free_area 的修改必须持锁
4. 关键数据结构
4.1 struct free_area
/* include/linux/mmzone.h:192 */struct free_area {struct list_head free_list[MIGRATE_TYPES];unsigned long nr_free;};
每个 free_area 对应一个 order。它包含：
free_list[MIGRATE_TYPES] | struct page 的 buddy_list 串联 |
nr_free |
4.2 struct zone 中的 free_area 数组
/* include/linux/mmzone.h:1087 */struct zone {/* ... */struct free_area free_area[NR_PAGE_ORDERS];/* ... */};
每个 zone 维护 11 个 free_area（order 0 ~ 10）。分配时从低阶向高阶扫描，释放时从低阶向高阶合并。
4.3 MAX_PAGE_ORDER 的定义
/* include/linux/mmzone.h:30-39 */#ifndef CONFIG_ARCH_FORCE_MAX_ORDER#define MAX_PAGE_ORDER 10#else#define MAX_PAGE_ORDER CONFIG_ARCH_FORCE_MAX_ORDER#endif#define MAX_ORDER_NR_PAGES (1 << MAX_PAGE_ORDER)#define NR_PAGE_ORDERS (MAX_PAGE_ORDER + 1)
默认情况下 MAX_PAGE_ORDER = 10，即最大可分配 2^10 = 1024 个连续 page（4MB @ 4K page）。 架构可通过 CONFIG_ARCH_FORCE_MAX_ORDER 覆盖。
4.4 PageBuddy 机制
/* mm/page_alloc.c:708 */static inline void set_buddy_order(struct page *page, unsigned int order){set_page_private(page, order);__SetPageBuddy(page);}
页面进入 buddy 系统时，通过 page_private(page) 存储其 order，通过 PageBuddy 标志位标记其空闲状态。 这一设计使得给定任意页面，可以通过 位运算 在 O(1) 时间内定位其伙伴。
5. 调用链
Buddy system 的分配路径是从 __alloc_pages 到 __rmqueue_smallest，释放路径是从 free_pages 到 __free_one_page。
上图展示了分配路径的 4 阶段状态机：
RMQUEUE_NORMAL：首选 migratetype 的
__rmqueue_smallest，从小到大扫描 free_areaRMQUEUE_CMA：CMA 区域回退，可移动分配优先从 CMA 取页
RMQUEUE_CLAIM：夺取整个 pageblock 并转换 migratetype
RMQUEUE_STEAL：从其他 migratetype 偷取单页（不转换 block）
核心分配函数 __rmqueue_smallest（蓝色）通过 expand（红色）将高阶块拆分为目标阶。
释放路径相对简单：__free_pages -> __free_one_page -> find_buddy_page_pfn（XOR 位运算）-> page_is_buddy（验证）-> __add_to_free_list（挂入更高阶链表）。
6. 核心执行流程
6.1 分配：__rmqueue_smallest — 从小到大扫描
/* mm/page_alloc.c:1888 */struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,int migratetype){unsigned int current_order;struct free_area *area;struct page *page;/* Find a page of the appropriate size in the preferred list */for (current_order = order; current_order < NR_PAGE_ORDERS; ++current_order) {area = &(zone->free_area[current_order]);page = get_page_from_free_area(area, migratetype);if (!page)continue;page_del_and_expand(zone, page, order, current_order,migratetype);trace_mm_page_alloc_zone_locked(page, order, migratetype,pcp_allowed_order(order) &&migratetype < MIGRATE_PCPTYPES);return page;}return NULL;}
执行逻辑：
从请求的
order开始，逐阶向上扫描（order, order+1, order+2, …）在每一阶的
free_area中查找对应migratetype的空闲页面第一个找到的页面，通过
page_del_and_expand拆分到目标 order返回拆分后的页面指针
关键设计：如果 order 0 没有空闲页面，就扫描 order 1、order 2……找到第一个满足条件的更高阶块，然后拆分。 这叫 “smallest suitable” —— 找到能满足需求的最小阶，避免过度拆分。
6.2 拆分：expand — 高阶块切为低阶
/* mm/page_alloc.c:1701 */static inline unsigned int expand(struct zone *zone, struct page *page, int low,int high, int migratetype){unsigned int size = 1 << high;unsigned int nr_added = 0;while (high > low) {high--;size >>= 1;VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);/** Mark as guard pages (or page), that will allow to* merge back to allocator when buddy will be freed.* Corresponding page table entries will not be touched,* pages will stay not present in virtual address space*/if (set_page_guard(zone, &page[size], high))continue;__add_to_free_list(&page[size], zone, high, migratetype, false);set_buddy_order(&page[size], high);nr_added += size;}return nr_added;}
执行逻辑（以 order 8 → order 0 为例）：
初始：一块 order 8 的块（256 pages）目标：分配 order 0（1 page）迭代 1: high=7, size=128 -> 把后 128 页挂入 order 7 链表迭代 2: high=6, size=64 -> 把后 64 页挂入 order 6 链表迭代 3: high=5, size=32 -> 把后 32 页挂入 order 5 链表迭代 4: high=4, size=16 -> 把后 16 页挂入 order 4 链表迭代 5: high=3, size=8 -> 把后 8 页挂入 order 3 链表迭代 6: high=2, size=4 -> 把后 4 页挂入 order 2 链表迭代 7: high=1, size=2 -> 把后 2 页挂入 order 1 链表结束: high=0, 剩下的前 1 页分配给调用者共 7 次链表插入，返回 255（新挂入的页数）
关键设计：每次迭代把块的后半部分挂入对应阶的链表，前半部分继续向下拆分。
size = 1 << high，size >>= 1每次减半。&page[size]指向后半部分的起始页。
6.3 释放与合并：__free_one_page — 向上合并
/* mm/page_alloc.c:933 */static inline void __free_one_page(struct page *page,unsigned long pfn,struct zone *zone, unsigned int order,int migratetype, fpi_t fpi_flags){struct capture_control *capc = task_capc(zone);unsigned long buddy_pfn = 0;unsigned long combined_pfn;struct page *buddy;bool to_tail;/* ... 省略参数校验 ... */account_freepages(zone, 1 << order, migratetype);while (order < MAX_PAGE_ORDER) {int buddy_mt = migratetype;if (compaction_capture(capc, page, order, migratetype)) {account_freepages(zone, -(1 << order), migratetype);return;}buddy = find_buddy_page_pfn(page, pfn, order, &buddy_pfn);if (!buddy)goto done_merging;/* 大 order 的 migratetype 兼容性检查 */if (unlikely(order >= pageblock_order)) {buddy_mt = get_pfnblock_migratetype(buddy, buddy_pfn);if (migratetype != buddy_mt &&(!migratetype_is_mergeable(migratetype) ||!migratetype_is_mergeable(buddy_mt)))goto done_merging;}/* 伙伴是 guard page 或空闲页，合并并上移一阶 */if (page_is_guard(buddy))clear_page_guard(zone, buddy, order);else__del_page_from_free_list(buddy, zone, order, buddy_mt);if (unlikely(buddy_mt != migratetype)) {change_pageblock_range(buddy, order, migratetype);}combined_pfn = buddy_pfn & pfn;page = page + (combined_pfn - pfn);pfn = combined_pfn;order++;}done_merging:set_buddy_order(page, order);if (fpi_flags & FPI_TO_TAIL)to_tail = true;else if (is_shuffle_order(order))to_tail = shuffle_pick_tail();elseto_tail = buddy_merge_likely(pfn, buddy_pfn, page, order);__add_to_free_list(page, zone, order, migratetype, to_tail);if (!(fpi_flags & FPI_SKIP_REPORT_NOTIFY))page_reporting_notify_free(order);}
执行逻辑（以释放 order 0 为例）：
释放 page@pfn=100, order=0迭代 1: 找 buddy -> pfn = 100 ^ (1<<0) = 101buddy@101 也在 free_list[0] 中 -> 合并combined_pfn = 101 & 100 = 100page = page@100, order 变为 1迭代 2: 找 buddy -> pfn = 100 ^ (1<<1) = 102buddy@102 不在 free_list[1] 中 -> 停止合并done_merging: 把 page@100 (order 1, 2 pages) 挂入 free_list[1]
6.4 找伙伴：find_buddy_page_pfn — 核心位运算
/* mm/internal.h:777 */static inline unsigned long__find_buddy_pfn(unsigned long page_pfn, unsigned int order){return page_pfn ^ (1 << order);}static inline struct page *find_buddy_page_pfn(struct page *page,unsigned long pfn, unsigned int order, unsigned long *buddy_pfn){unsigned long __buddy_pfn = __find_buddy_pfn(pfn, order);struct page *buddy;buddy = page + (__buddy_pfn - pfn);if (buddy_pfn)*buddy_pfn = __buddy_pfn;if (page_is_buddy(page, buddy, order))return buddy;return NULL;}
核心公式：buddy_pfn = pfn ^ (1 << order)
这是 buddy system 最精妙的设计——通过 XOR 位运算在 O(1) 时间内找到伙伴的 PFN，无需查表、无需遍历。
运行时走一遍：
为什么 XOR 能工作？ 因为 2^n 阶的 buddy pair 总是以 2^(n+1) 对齐的。例如 order 1 的块总是以 2-page 边界对齐（PFN 为偶数开始），所以 buddy 就是翻转第 1 位。order 2 的块以 4-page 边界对齐，buddy 就是翻转第 2 位。
6.5 伙伴验证：page_is_buddy
找到 PFN 后，还需要验证它真的是有效的伙伴：
/* mm/internal.h:738 */static inline bool page_is_buddy(struct page *page, struct page *buddy,unsigned int order){if (!page_is_guard(buddy) && !PageBuddy(buddy))return false;if (buddy_order(buddy) != order)return false;/* zone 检查放在最后，避免不必要的计算 */if (page_zone_id(page) != page_zone_id(buddy))return false;VM_BUG_ON_PAGE(page_count(buddy) != 0, buddy);return true;}
验证四个条件：
伙伴是 guard page 或设置了 PageBuddy（在 buddy 链表中）
伙伴的 order 与当前页面相同
伙伴与当前页面在同一个 zone
伙伴的引用计数为 0（确实空闲）
7. 分支路径分析
7.1 分配时的 fallback 链
当请求的 migratetype 没有空闲页面时，__rmqueue 按以下顺序尝试：
RMQUEUE_NORMAL (首选 migratetype)-> __rmqueue_smallest: 失败RMQUEUE_CMA (CMA 区域回退)-> __rmqueue_cma_fallback: 从 MIGRATE_CMA 分配RMQUEUE_CLAIM (从其他 migratetype 借用)-> __rmqueue_claim: 检查 fallbacks 表RMQUEUE_STEAL (steal 整个 pageblock)-> __rmqueue_steal: 把整个 pageblock 转为请求的 migratetype
fallback 表定义了优先级：
/* mm/page_alloc.c:1918 */static int fallbacks[MIGRATE_PCPTYPES][MIGRATE_PCPTYPES - 1] = {[MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE },[MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE },[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE },};
7.2 合并时的 migratetype 冲突处理
当伙伴的 migratetype 与当前页面不同时：
/* mm/page_alloc.c:990 */if (unlikely(buddy_mt != migratetype)) {/** Match buddy type. This ensures that an* expand() down the line puts the sub-blocks* on the right freelists.*/change_pageblock_range(buddy, order, migratetype);}
合并后的块会统一为当前页面的 migratetype，确保后续 expand() 拆分时子块挂入正确的链表。
7.3 合并优化：buddy_merge_likely
释放页面时，内核会预测"这个页面是否很快会和更高阶的伙伴合并"：
/* mm/page_alloc.c:883 */static inline boolbuddy_merge_likely(unsigned long pfn, unsigned long buddy_pfn,struct page *page, unsigned int order){unsigned long higher_page_pfn;struct page *higher_page;if (order >= MAX_PAGE_ORDER - 1)return false;higher_page_pfn = buddy_pfn & pfn;higher_page = page + (higher_page_pfn - pfn);return find_buddy_page_pfn(higher_page, higher_page_pfn, order + 1,NULL) != NULL;}
直觉：如果合并后的块在高阶也有空闲伙伴，说明内存正在被大量释放，很快会发生进一步的合并。 此时把页面挂到链表尾部（to_tail = true），让它不被立即分配出去，等合并完成再一起使用。
这是一个反碎片启发式策略：与其把一个页面立刻分出去，不如等它和伙伴合并成更大的块。
运行时走一遍：
释放 page@pfn=8, order=1当前 buddy@pfn=10 也空闲，合并到 order 2合并后: higher_page_pfn = 10 & 8 = 8higher_page = page@8检查: find_buddy_page_pfn(page@8, pfn=8, order=3)-> buddy_pfn = 8 ^ (1<<3) = 8 ^ 8 = 0-> buddy@0 也在 free_list[3] 中吗？情况 A: buddy@0 空闲 -> 返回 true, to_tail = true合并后的 order 2 块挂到链表尾部因为它很快会和 buddy@0 合并为 order 3情况 B: buddy@0 已分配 -> 返回 false, to_tail = false合并后的 order 2 块挂到链表头部可以立即被后续分配使用
关键洞察：buddy_pfn & pfn 计算的是合并后块的起始 PFN（两个伙伴的公共前缀）。 然后用这个起始 PFN 去检查更高一阶是否也有空闲伙伴。
8. 并发与生命周期分析
8.1 锁保护
所有 buddy system 操作都在 zone->lock 保护下进行：
__rmqueue_smallest：由get_page_from_freelist调用，该函数持 zone->lock__free_one_page：由free_pages->__free_pages调用，也持 zone->lock所有对
free_area链表的修改（__add_to_free_list、__del_page_from_free_list）必须持锁
这意味着 buddy system 的分配和释放在同一个 zone 内是串行化的。多核并发时， 不同 zone 可以并行分配，同一 zone 内竞争通过 spinlock 解决。
8.2 PageBuddy 生命周期
上图展示了页面在 buddy 系统中的完整状态流转：
FreeInBuddy（核心状态）：页面在 free_list 上，PageBuddy=1，order 记录在 page_private。所有操作受 zone->lock 保护。
合并循环：
__free_one_page中通过 XOR 位运算找到伙伴，验证 page_is_buddy() 成功后合并到更高阶，重复直到无伙伴或达到 MAX_PAGE_ORDER。Allocated：
__del_page_from_free_list清除 PageBuddy 标志，页面从链表移除，交给调用者使用。compaction_capture：合并过程中如果有内存压缩机制在等待页面，会提前捕获而非挂入链表。
8.3 错误路径
bad_range 检查：
expand和__free_one_page中都有VM_BUG_ON_PAGE(bad_range(...))，确保操作不超出 zone 边界PageBuddy 重复检查：
page_is_buddy中先检查 PageBuddy 标志，防止把已分配的页面误认为空闲compaction_capture：在合并循环中，如果有 compaction 在等待捕获页面，会提前退出合并，把页面交给 compaction
9. Kconfig 依赖分析
9.1 MAX_PAGE_ORDER
CONFIG_ARCH_FORCE_MAX_ORDER: int定义位置：各架构的 Kconfig（如 arch/arm64/Kconfig）类型：int默认：10（通过 #ifndef 在 mmzone.h 中定义）影响：buddy system 最大可分配的阶数
如果设置为 11，则最大可分配 2^11 = 2048 pages（8MB @ 4K page）。 某些架构（如 IA-64）需要更大的 MAX_ORDER 来支持更大的 I/O 区域。
9.2 CMA 相关
CONFIG_CMA: bool定义位置：mm/Kconfig依赖：MMU影响：启用后 __rmqueue 增加 CMA fallback 路径
启用 CMA 后，分配路径会优先检查 CMA 区域的空闲页面， 当 CMA 空闲超过 zone 总空闲的一半时，可移动分配会优先从 CMA 区域分配。
10. 调试与验证方法
10.1 查看 buddy 信息
# 查看每个 zone 每个 order 的空闲页面数# 运行目录：/sys/kernel/debug/# 权限：rootcat /sys/kernel/debug/buddyinfo
典型输出：
Node 0, zone DMA 1 2 1 0 2 1 1 0 1 1 3Node 0, zone DMA32 234 156 89 45 23 11 5 2 1 0 2Node 0, zone Normal 1023 512 256 128 64 32 16 8 4 2 1
每列对应一个 order（0 到 10），数字表示该 order 下有多少个块（不是 page 数）。
10.2 查看 zone 信息
# 查看每个 zone 的详细统计信息# 运行目录：/proccat /proc/zoneinfo
输出中包含 free_area 的信息：
Node 0, zone Normalpages free 524288min 12345low 15431high 18517...free_area: 0: nr_free: 1234free_area: 1: nr_free: 567free_area: 2: nr_free: 234...
10.3 ftrace 追踪分配路径
# 启用 mm_page_alloc 事件追踪# 运行目录：/sys/kernel/debug/tracing/# 权限：rootecho 1 > /sys/kernel/debug/tracing/events/mm_page_alloc/enablecat /sys/kernel/debug/tracing/trace_pipe
输出示例：
kworker-123 [002] .... 1234.567890: mm_page_alloc: page=0xffffea0004000000 pfn=65536 order=0 migratetype=010.4 验证环境说明
内核版本：Linux 7.0（本文分析基于此版本）
CPU 架构：x86_64 / ARM64（buddy system 核心逻辑与架构无关）
内存要求：至少 1GB（确保有足够页面观察多阶分配）
内核配置：无需特殊配置，buddy system 是内核基础功能
权限要求：查看 buddyinfo 和 ftrace 需要 root 权限
11. 总结
Buddy System 的核心可以概括为三句话：
分配：从请求的 order 开始向上扫描，找到第一个有空闲块的阶，通过
expand逐层拆分，把不需要的部分挂回对应阶的链表。释放：通过
pfn ^ (1 << order)在 O(1) 时间内定位伙伴，如果伙伴也空闲则合并，order +1 后继续向上尝试。标记：用
PageBuddy标志位 +page_private存储 order，无需额外的位图或树结构。
这套设计的关键权衡：
实践意义：内核开发者何时需要关心
12. 参考资料
Linux 7.0 源码：
mm/page_alloc.c：buddy 分配器核心实现include/linux/mmzone.h：free_area、struct zone、MAX_PAGE_ORDER 定义mm/internal.h：find_buddy_page_pfn、page_is_buddy 内联函数include/linux/page-flags.h：PageBuddy 标志定义Mel Gorman, “Understanding the Linux Virtual Memory Manager”, Chapter 3 (The Buddy Allocator)
Robert Love, “Linux Kernel Development”, 3rd Edition, Chapter 12 (Memory Management)
Linux Kernel Documentation:
Documentation/core-api/mm_api.rstLWN.net: “The buddy allocator” (系列文章)
随机文章
-
10个月宝宝每天需要喝多少奶粉？
- 一周背完python八股文,面试必过
- 手把手打造一个 AI Agent——用 Python 实现迷你版Claude Code
- 别再乱学PS、Python了,普通大学生该看懂的技能趋势
- 【科研必备】最新AI与Python近红外光谱数据智能分析高阶实践培训班
- Python 空间解释性机器学习实战:基于 RF 与 GeoShapley 的全流程代码解析
- 【2026首发】Python就业全栈视频课程
- 【一起学Python】第80天:NumPy高级索引全攻略,数据筛选的终极武器!
- 终结者 T800 运行着 Linux 操作系统内核,天哥说态势(20300504)
- 做账会计学了Python对涨薪有帮助吗?
- 修复方案 | Linux Kernel 爆高危本地提权漏洞
