3、伙伴系统（Buddy System）：伙伴算法的核心原理、内存碎片化问题、alloc_pages流程
好，咱们今天来聊聊伙伴系统。说实话，这是Android内核内存管理里最绕不开的一块基石。我当年刚接触内核时，觉得这名字挺有意思——"伙伴"，后来才发现，这背后是一套极其精巧的数学逻辑。
3.1 伙伴算法的核心原理
伙伴系统要解决什么问题？说白了，就是内核在频繁分配和释放内存后，如何避免内存变成一盘散沙。你想想看，如果每次分配都随便切一块出去，时间长了，空闲内存会碎成无数小片，大块请求就满足不了了。
伙伴算法的思路很直接：把内存按2的幂次方分成块。比如4KB、8KB、16KB……一直到4MB。每个大小的块都挂在对应的链表上。
核心规则：两个大小相同、地址连续的块，可以合并成一个更大的块。这两个块互为"伙伴"。
怎么判断两个块是不是伙伴？有个简单公式：
如果块A的起始地址是 addr，大小是 size，那么它的伙伴地址就是 addr ^ size（按位异或）。
举个例子：假设一个4KB的块起始地址是0x1000，它的伙伴就是0x1000 ^ 0x1000 = 0x0000？不对，这里要注意，size是块的实际字节数。4KB = 0x1000，所以伙伴地址是 0x1000 ^ 0x1000 = 0x0000。嗯，这其实意味着0x0000和0x1000这两个4KB块互为伙伴。
我个人习惯把伙伴关系想象成"镜像对称"——两个块在地址空间里像照镜子一样对齐。这个特性保证了合并时地址一定是连续的。
3.2 内存碎片化问题
伙伴系统虽然经典，但并非完美。我在项目中遇到过最头疼的问题就是外部碎片。
什么叫外部碎片？就是空闲内存总量够，但都是小块的，凑不出一块大的。比如你有10个4KB的空闲块，但想分配一个64KB的块，对不起，做不到。
我曾经踩过的坑：在一个长期运行的Android设备上，系统启动后内存分配正常，但运行了几天后，突然出现分配大块DMA缓冲区失败的情况。排查下来，就是伙伴系统的外部碎片导致的。
碎片化主要有几个来源：
- 频繁分配释放不同大小的块：比如一会儿分配3个页，一会儿释放2个页，时间长了就乱套了
- 长期占用中间大小的块：有些驱动分配了16KB后一直不释放，导致它两边的8KB块无法合并成16KB
- 内存规整性被破坏：移动页面时，如果页面被锁定（比如正在DMA操作），就无法迁移
那怎么解决？内核提供了几种手段：
- 内存规整（compaction）：把可移动的页面集中到一起，腾出连续空间
- 防碎片化策略：通过
__GFP_RECLAIMABLE等标志，让内核知道哪些页面可以迁移 - 虚拟可移动域（ZONE_MOVABLE）：专门放可迁移的页面
我个人建议，写驱动时尽量用kzalloc而不是__get_free_pages，除非你真的需要物理连续内存。因为kzalloc走的是slab分配器，对伙伴系统的压力小得多。
3.3 alloc_pages 流程
好，咱们来看看alloc_pages到底是怎么工作的。这是伙伴系统最核心的分配入口。
先看简化版的调用链：
alloc_pages(gfp_mask, order)
└─> __alloc_pages_nodemask(gfp_mask, order, preferred_nid, nodemask)
└─> get_page_from_freelist(alloc_context)
└─> rmqueue(zone, order, migratetype)
└─> __rmqueue(zone, order, migratetype)
└─> __rmqueue_smallest(zone, order, migratetype)
└─> expand(zone, page, low, high, migratetype)嗯，看着有点长，但核心逻辑其实就几步：
- 检查水位：先看当前zone的空闲内存够不够，不够就触发内存回收
- 找合适大小的块：从order对应的链表开始找，如果有就直接取走
- 分裂更大的块：如果当前order没有空闲块，就找更大的order，然后不断二分，直到得到目标大小的块
- 更新伙伴信息：分裂后，剩余的部分要挂到对应的链表上
举个例子：假设要分配一个4KB的块（order=0），但order=0的链表是空的。内核会去order=1（8KB）的链表找，如果也没有，继续找order=2（16KB）……直到找到为止。
找到后，把16KB的块一分为二：两个8KB。一个8KB再一分为二：两个4KB。其中一个4KB返回给调用者，另一个4KB挂到order=0链表，那个没用的8KB挂到order=1链表。
一个小技巧：看__rmqueue_smallest的实现时，注意expand函数。它负责把分裂后多余的块挂回链表。我曾经调试过一个bug，就是expand里伙伴关系计算错了，导致内存泄漏。后来发现是页描述符的private字段没清零。
再看一下关键的数据结构：
| 结构体 | 作用 |
|---|---|
struct free_area |
管理每个order的空闲块链表 |
struct zone |
内存域，包含多个free_area |
struct page |
页描述符，记录页的状态和伙伴信息 |
每个struct page里有个private字段，当页是空闲时，它记录的是这个页所属的order。当页被分配后，这个字段就归使用者了。嗯，这里要注意，private是个union，不同场景下含义不同。
最后，说说gfp_mask。这个标志位决定了分配行为：
GFP_KERNEL：普通内核分配，可以睡眠等待GFP_ATOMIC：原子分配，不能睡眠，比如中断上下文__GFP_HIGHMEM：允许从高端内存分配__GFP_ZERO：分配后自动清零
我个人习惯在调试时加个__GFP_ZERO，虽然慢一点，但能避免很多"未初始化内存"的诡异问题。你想想看，一个随机值导致的bug，查起来多痛苦。
好了，伙伴系统的核心就这些。下一节咱们聊聊更高级的——页面回收和LRU链表。到时候你会发现，伙伴系统只是内存管理的冰山一角。