357｜内存管理：Buddy System 伙伴系统
金句：把内存切成整齐的 2 的幂次块，用完了合并，用完了合并，用完了合并。这套”分分合合”的算法，是 Linux 物理内存管理的起点。
1. 伙伴系统解决什么问题？
物理内存分配，核心问题是碎片化。
假设有 512KB 物理内存，某时刻分配出去的情况：
已分配： [ 64KB ][ 128KB ][ 32KB ]
空闲： [ 96KB ][ 192KB ]这时候来了一个程序要申请 128KB：剩余最大连续块只有 96KB + 192KB = 288KB，但它们不连续，无法满足 128KB 的连续分配。
这就是外部碎片化：内存总量够，但连续空间不够。
Buddy System 用一个简单规则解决这个问题：总是分配 2 的幂次大小的块，释放时总是尝试合并相邻的同尺寸伙伴。
2. 基本思想：分而治之
假设我们有 8MB 物理内存，从 8MB 开始：
初始状态（order=23，表示 2^23 * PAGE_SIZE = 8MB）：
┌─────────────────────────────────────┐
│ 8MB │ ← 一整块
└─────────────────────────────────────┘需要分配 1MB = 2^20？
第一次分裂（8MB → 两个 4MB）：
┌───────────────┬───────────────┐
│ 4MB │ 4MB │
│ (空闲) │ (空闲) │
└───────────────┴───────────────┘
第二次分裂（4MB → 两个 2MB）：
┌───────┬───────┬───────────────┐
│ 2MB │ 2MB │ 4MB │
└───────┴───────┴───────────────┘
第三次分裂（2MB → 两个 1MB）：
┌─────┬─────┬───────┬───────────┐
│ 1MB │ 1MB │ 2MB │ 4MB │
└─────┴─────┴───────┴───────────┘
分配出第一块 1MB：
┌─────┬ [1MB] ────────┬──────────┐
│ 1MB │ (已分配) │ 4MB │
└─────┴───────────────┴──────────┘每次分裂产生的两个块，互为伙伴（Buddy）：它们的物理地址是连续的，且大小相同。
3. 伙伴的定义
两个块是伙伴，当且仅当：
- 大小相同（都是 2^k）
- 物理地址连续
- 地址关系：其中一块的起始地址是
另一块起始地址 + 大小
示例（1MB 块）：
块A 起始地址 0x00000000，大小 1MB
块B 起始地址 0x00100000，大小 1MB
块A 和块B 是伙伴
块C 起始地址 0x00080000，大小 1MB
块C 和块A 不是伙伴（不连续）释放时，内核检查伙伴是否也空闲。如果是，合并成更大的块。
4. 数据结构：free_area 数组
Linux 用 free_area 数组管理每个阶（order）的空闲块链表：
#define MAX_ORDER 11 // 最大 2^11 * 4KB = 8MB
struct zone {
struct free_area free_area[MAX_ORDER];
unsigned long start_pfn, end_pfn;
...
};
struct free_area {
struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free;
};free_area[0] 是 4KB 单页的空闲链表，free_area[1] 是 8KB 双页的空闲链表，以此类推。
free_area 数组结构：
order=0 (4KB): [list] → [page] → [page] → ...
order=1 (8KB): [list] → [buddy pair] → ...
order=2 (16KB): [list] → ...
...
order=10 (4MB): [list] → ...5. 分配流程：__alloc_pages
当内核调用 alloc_pages(gfp, order) 申请 2^order 个连续物理页时，Buddy System 的搜索路径：
__alloc_pages(gfp, order):
for (o = order; o < MAX_ORDER; o++):
if (free_area[o].nr_free > 0):
# 找到！取一块
page = list_entry(free_area[o].free_list.next)
list_del(&page->lru)
free_area[o].nr_free--
# 拆分成两块（如果 o > order）
split_page(page, o) # 递归分裂
return page # 返回恰好大小的块
# 找不到
return NULL示例：申请 order=2（16KB = 4页），但 free_area[2] 为空，free_area[3] 有块：
1. 从 free_area[3] 取一个 8KB 的块（伙伴对的一半）
2. split_page 将 8KB 拆成两个 4KB
3. 把其中一个 4KB 放回 free_area[0]
4. 剩下一个 4KB 继续拆分（o=2 → o=1）
5. 得到两个 2KB，其中一个放回 free_area[0]
6. 分配出 4KB（2页）6. 释放流程：__free_pages
释放时，内核检查是否可以和伙伴合并：
__free_pages(page, order):
while (order < MAX_ORDER-1):
buddy_paddr = page ^ (1 << order) # 计算伙伴地址
if buddy_paddr 空闲且 order 相同：
# 合并！
list_del(&buddy->lru)
merge(page, buddy) → 形成 (order+1) 的块
order++
page = min(page, buddy_paddr) # 合并后的起始地址
continue # 继续尝试往更大阶合并
else:
break
# 放进去
list_add(&page->lru, free_area[order].free_list)
free_area[order].nr_free++
page ^ (1 << order)是计算伙伴地址的巧妙方法：
块起始地址p和伙伴起始地址p ^ (2^order)只差那 1 位。
举例：释放 0x00000000（1MB 块，order=20）：
第一轮检查（order=20，伙伴 = 0x00100000）：
如果 0x00100000 空闲且是伙伴 → 合并成 2MB
如果不空闲 → 直接放入 free_area[20]
第二轮检查（order=21，伙伴 = 0x00200000）：
如果 0x00200000 空闲且是伙伴 → 合并成 4MB
...7. 伙伴系统的碎片化问题
Buddy System 本身不解决碎片化。
它的分配必须是连续的 2 的幂次块，所以：
- 申请 3MB：必须分配 4MB（浪费 1MB）
- 申请 6MB：必须分配 8MB（浪费 2MB）
- 长期运行后，小块耗尽但大块有余，造成内部碎片化
但它的价值在于：保证合并效率。
两个相邻的 2^order 块合并后，形成的 2^(order+1) 块一定也是连续的。这使得碎片化的反面——合并——变得高效。
slab 分配器（将在 K01 中讲）建立在 Buddy System 之上，用 buddy 分配 4KB 页，再在页上切分成固定大小的对象（slab），解决内部碎片化问题。
8. 实际内存大小和 MAX_ORDER
假设 PAGE_SIZE = 4KB，MAX_ORDER = 11：
| Order | 块大小 | 能连续分配的最大物理内存 |
|---|---|---|
| 0 | 4KB | 4KB |
| 1 | 8KB | 8KB |
| 2 | 16KB | 16KB |
| 3 | 32KB | 32KB |
| 4 | 64KB | 64KB |
| 5 | 128KB | 128KB |
| 6 | 256KB | 256KB |
| 7 | 512KB | 512KB |
| 8 | 1MB | 1MB |
| 9 | 2MB | 2MB |
| 10 | 4MB | 4MB |
如果系统有 8GB 物理内存，Buddy System 最高只能直接分配 4MB（order=10）。更大内存需要多个 4MB 块拼起来。
9. 总结
| 知识点 | 关键结论 |
|---|---|
| 伙伴定义 | 同大小、物理连续、地址差 2^order |
| 分配 | 从请求的 order 往上找，有块就分裂 |
| 释放 | 尝试和伙伴合并，无法合并就放入对应链表 |
| 伙伴地址公式 | addr ^ (1 << order) |
| 优点 | 合并高效，避免外部碎片化恶化 |
| 缺点 | 2 的幂次分配造成内部碎片化 |
| slab/slub | 基于 Buddy System，上层切分固定大小对象 |
下篇预告（358）：定时器（HPET）和时钟中断——jiffies 是怎么累加的，schedule 是怎么被定时唤醒的，以及时间管理在内核里的实现。
关注公众号「AI不着急」，回复”资料”获取内核学习路线图。
评论