📚 课程目录第3章伙伴系统算法

3. 伙伴系统算法

3.1 伙伴系统（Buddy System）核心原理

伙伴系统是Linux内核管理物理内存页面分配与回收的核心算法。其设计目标是在满足快速分配/释放的同时，尽可能减少外部碎片。内核将物理内存划分为连续的页面块（page block），每个块包含2^order个连续的物理页面（order为分配阶）。

  核心思想： 所有空闲页面块按大小（order）分组，存放在不同的链表中。分配时从满足需求的最小order链表中取出一个块；释放时检查其“伙伴”是否也为空闲，若是则合并为更大的块，并递归向上合并。

伙伴的定义： 两个大小相同、物理地址连续的页面块，且它们由同一个更大的页面块分裂而来。设块A的起始物理页框号为p，块大小为2^order，则其伙伴的起始页框号为 p ^ (1 << order)。

关键特性： 伙伴系统通过“分裂-合并”机制，在分配与释放过程中动态调整页面块大小，兼顾了分配灵活性与内存利用率。

3.2 Order 与 Page Block 详解

Order（分配阶）是伙伴系统的核心参数，取值范围为0到MAX_ORDER-1（通常MAX_ORDER=11）。每个order对应一个空闲链表，链表中每个页面块的大小为2^order个连续物理页。

Order	页面数	大小（4K页）	典型用途
0	1	4 KB	最小分配单元，slab分配器后备
1	2	8 KB	小尺寸DMA缓冲区
2	4	16 KB	文件系统元数据
3	8	32 KB	网络收发缓冲区
4	16	64 KB	中等DMA/IO缓冲区
5	32	128 KB	音频/视频帧缓冲区
6	64	256 KB	相机ISP缓冲区
7	128	512 KB	显示帧缓冲
8	256	1 MB	CMA区域常用块大小
9	512	2 MB	大块连续分配
10	1024	4 MB	最大order块（默认MAX_ORDER=11）

Page Block（页面块）是伙伴系统管理的基本单位。每个page block由2^order个连续的struct page组成。内核通过struct free_area管理每个order的空闲块链表：

// include/linux/mmzone.h
struct free_area {
    struct list_head    free_list[MIGRATE_TYPES];
    unsigned long       nr_free;
};

注意： 在Linux 5.x及以上内核中，每个free_area内部又按迁移类型（MIGRATE_UNMOVABLE、MIGRATE_RECLAIMABLE、MIGRATE_MOVABLE等）进一步细分链表，以减少不可移动页面导致的长期碎片。

3.3 内存碎片产生原因

伙伴系统虽然能有效减少外部碎片，但在长期运行的嵌入式系统中，碎片问题依然严峻。碎片主要分为两类：

内部碎片： 分配的内存块大于实际需求，多余部分无法被其他请求利用。例如，请求3KB时分配order=2（16KB）的块，造成13KB内部浪费。
外部碎片： 空闲内存总量充足，但无法满足连续大块分配请求。例如，系统有10个order=0的空闲页，但无法分配一个order=3（8页）的连续块。

碎片产生的核心原因：

不可移动页面的锚定效应： 内核代码段、页表、某些驱动分配的DMA缓冲区等不可移动页面散布在物理地址空间中，将空闲内存分割成不连续的小块。
分配与释放顺序不匹配： 长时间运行后，不同大小的页面块交错分配释放，导致高阶空闲块难以形成。
最大order限制： 默认MAX_ORDER=11，最大连续块仅4MB。对于需要更大连续内存的设备（如GPU、多媒体编解码器），伙伴系统无法直接满足。
迁移类型混杂： 不同迁移类型的页面块混合在同一区域，导致可移动页面无法有效聚集，阻碍大块合并。

3.4 伙伴系统分配与释放算法

分配流程（__alloc_pages_slowpath简化版）：

从请求的order开始，检查对应free_area链表是否有空闲块。
若有，直接取出并返回。
若无，向更高order（order+1）的链表请求一个块。
将取出的高阶块分裂为两个低阶块（伙伴对），一个用于分配，另一个挂入当前order的空闲链表。
若所有order均无空闲块，触发内存回收或OOM。

释放流程（__free_pages）：

计算待释放块的伙伴地址：buddy_pfn = pfn ^ (1 << order)。
检查伙伴是否为空闲且order相同。
若伙伴空闲，将两个块从链表移除，合并为一个高阶块，order加1，递归检查合并。
若伙伴不空闲，直接将当前块挂入对应order的空闲链表。

// 伙伴地址计算示例
// 假设页面块起始pfn=0x100，order=2（4页）
// 伙伴pfn = 0x100 ^ (1 << 2) = 0x100 ^ 0x4 = 0x104
unsigned long buddy_pfn = pfn ^ (1 << order);

  性能关键点： 伙伴系统的分裂与合并操作时间复杂度为O(1)（仅涉及链表操作），但合并操作可能递归向上遍历多个order。在嵌入式实时系统中，需关注最坏情况下的合并延迟。

3.5 嵌入式场景下的碎片问题与应对策略

场景	碎片问题	应对策略
多媒体播放器	频繁分配/释放视频帧缓冲区（order=5~7），导致高阶块碎片	使用CMA预留区域，避免与普通内存分配竞争
网络路由器	大量order=0的skb分配，长时间运行后无法分配order=4以上块	启用页面迁移（migration）和compaction机制
摄像头ISP	需要order=8~9连续块，但系统碎片严重	配置CMA区域，使用dma_alloc_coherent从CMA分配
工业控制器	长时间运行（数月），内存碎片逐渐累积	定期触发内存压缩（echo 1 > /proc/sys/vm/compact_memory）

内核提供的碎片缓解机制：

内存压缩（Compaction）： 通过页面迁移将可移动页面集中到区域一端，释放连续大块。
页面迁移（Page Migration）： 支持MIGRATE_MOVABLE类型的页面在物理地址间移动。
CMA（Contiguous Memory Allocator）： 预留专用区域，仅在需要时分配连续大块，平时可作为可移动页面使用。
ZONE_MOVABLE： 将内存划分为不可移动和可移动区域，减少不可移动页面对连续空间的干扰。

实战建议： 在嵌入式系统设计阶段，应通过/proc/buddyinfo监控各order的空闲块数量。若order≥3的块长期为0，说明碎片严重，需考虑启用CMA或调整内存布局。

3.6 关键数据结构与API

核心数据结构：

// 每个内存区域（zone）包含一个free_area数组
struct zone {
    // ...
    struct free_area    free_area[MAX_ORDER];
    // ...
};

// 每个页面描述符包含伙伴系统相关字段
struct page {
    unsigned long       flags;      // 包含PG_buddy等标志
    // 当页面空闲时，以下字段组成链表节点
    union {
        struct {    /* 用于伙伴系统 */
            struct list_head lru;   // 空闲链表指针
            unsigned long private;  // 存储order值
        };
        // ...
    };
};

常用API：

API	功能	返回
`alloc_pages(gfp_mask, order)`	分配2^order个连续物理页	struct page *
`__get_free_pages(gfp_mask, order)`	分配并返回虚拟地址	unsigned long
`__free_pages(page, order)`	释放伙伴系统页面块	void
`free_pages(addr, order)`	通过虚拟地址释放	void
`split_page(page, order)`	手动分裂一个高阶块	void

嵌入式开发陷阱： 在中断上下文或持有自旋锁时，不能使用alloc_pages的慢速路径（可能触发内存回收导致睡眠）。应使用GFP_ATOMIC标志，仅从快速路径分配。

监控碎片状态：

# 查看各order空闲块数量
cat /proc/buddyinfo

# 输出示例（Node 0, Zone Normal）：
# Node 0, zone   Normal   1234   567   234   89   34   12   5   2   1   0   0
# 对应 order:       0      1     2     3    4    5   6   7   8   9  10

通过/proc/buddyinfo可以快速判断系统碎片程度：若高阶order（≥4）的空闲块数量长期为0或很小，说明系统面临连续内存分配压力，需要采取碎片缓解措施。