2. 伙伴系统：Buddy System原理、内存分配与释放、order与page block、碎片整理

2.1 伙伴系统核心原理

伙伴系统（Buddy System）是Linux内核管理物理内存的核心算法，负责将连续的物理页面高效地分配和回收。其基本思想是将物理内存按2的幂次方划分为连续的块（称为“伙伴”），分配时从满足需求的最小块开始，若没有则向上合并；释放时检查其伙伴是否空闲，若是则合并为更大的块。

2.2 Order与Page Block

在伙伴系统中，order 表示内存块的大小指数。一个order为n的块包含2ⁿ个连续的物理页面（每个页面通常为4KB）。内核维护一个以order为索引的空闲链表数组，每个链表链接相同大小的空闲块。

2.3 内存分配流程

当内核请求分配2^order个连续页面时，伙伴系统执行以下步骤：

1. 查找空闲块： 从当前order的空闲链表开始查找，若有空闲块则直接分配。
2. 向上分裂： 若当前order无空闲块，则向更高order（order+1）查找，将大块分裂为两个伙伴块，一个放入当前order链表，另一个继续分配。
3. 递归分裂： 重复步骤2直到找到满足需求的块或达到MAX_ORDER。
4. 分配失败： 若MAX_ORDER也无空闲块，则触发内存回收（kswapd）或直接内存回收（direct reclaim）。

2.4 内存释放与伙伴合并

释放内存时，伙伴系统执行与分配相反的操作——合并（Coalescing）。当释放一个块时，内核检查其伙伴是否也空闲，若是则将两者合并为更大的块，并递归向上合并。

判断伙伴地址的公式：

buddy_pfn = page_pfn ^ (1 << order)

其中 page_pfn 是当前页框号，order 是块大小指数。通过异或操作即可快速定位伙伴的起始页框号。

2.5 碎片整理机制

随着系统长时间运行，频繁的分配和释放会导致物理内存碎片化——虽然总空闲内存充足，但无法分配连续的2^order大块。Linux内核提供多种碎片整理手段：

2.6 碎片整理流程

内存规整（Compaction）是内核对抗碎片的主要手段，其工作流程如下：

1. 扫描迁移源： 从区域尾部开始扫描，标记可移动的页面。
2. 扫描迁移目标： 从区域头部开始扫描，寻找空闲页面作为迁移目标。
3. 页面迁移： 将源页面内容复制到目标页面，更新所有映射该页面的页表项。
4. 释放源页面： 源页面变为空闲，加入伙伴系统。
5. 重复执行： 直到满足分配需求或无法继续迁移。

2.7 容器场景下的碎片挑战

在容器化环境中，伙伴系统的碎片问题尤为突出：

• 频繁分配释放： 容器启动和销毁导致大量order-0页面分配释放，产生微观碎片。
• 大页需求： 数据库、缓存类容器常请求2MB大页（order-9），碎片化严重时分配失败。
• 内存热插拔： 容器内存上限动态调整时，需要连续物理内存区域。
• NUMA影响： 跨NUMA节点的内存分配加剧碎片化，影响容器内存访问延迟。

2.8 关键数据结构

伙伴系统的核心数据结构是 struct free_area，每个zone维护一个free_area数组：

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

struct zone {
    ...
    struct free_area    free_area[MAX_ORDER];
    unsigned long       _watermark[NR_WMARK];
    ...
};

其中 free_list 按迁移类型（MIGRATE_UNMOVABLE、MIGRATE_RECLAIMABLE、MIGRATE_MOVABLE等）组织，避免不可迁移页面阻塞大块合并。