3. 伙伴系统数据结构

伙伴系统的核心数据结构围绕三个层次展开：区域（zone）、迁移类型（migrate type） 和 阶（order）。理解 free_area 数组、struct page、zone 结构体以及 buddy bitmap 的协作关系，是掌握伙伴系统内存分配与回收机制的基础。

3.1 zone 结构体：内存区域的“总控室”

每个 struct zone 描述一个物理内存区域（如 ZONE_DMA、ZONE_NORMAL、ZONE_HIGHMEM）。伙伴系统在该区域内的所有操作，都通过 zone 结构体中的 free_area 数组和 pageblock_flags 等字段进行管理。

3.2 free_area 数组：按阶组织的空闲页块链表

free_area[MAX_ORDER] 是伙伴系统的核心索引结构。数组下标 order 表示页块的阶（0 到 MAX_ORDER-1，通常 MAX_ORDER=11），每个元素包含一个链表头和一个位图。

// include/linux/mmzone.h
struct free_area {
    struct list_head    free_list[MIGRATE_TYPES];
    unsigned long       *map;   // buddy bitmap
};

• free_list[MIGRATE_TYPES]：每个迁移类型对应一个链表，链入该阶下该迁移类型的空闲页块。
• map：指向 buddy bitmap 的指针，用于快速判断两个页块是否为伙伴。

3.3 struct page：物理页的“身份证”

每个物理页框对应一个 struct page 实例，伙伴系统通过该结构体管理页面的状态、引用计数和链表指针。

3.4 buddy bitmap：伙伴关系判定位图

每个 free_area 元素包含一个位图 map，用于快速判断两个连续页块是否为伙伴。位图的每一位对应一对候选伙伴页块。

• 位图大小：对于阶 order，位图位数 = zone 总页数 >> (order + 1)。
• 位图含义：某位为 1 表示该对伙伴中至少有一个页块是空闲的；为 0 表示两个页块都已分配或都不存在。
• 作用：在释放页块时，通过位图快速判断伙伴是否空闲，从而决定是否合并。

// 判断两个页块是否为伙伴的简化逻辑
static inline unsigned long find_buddy(unsigned long page_idx, unsigned int order) {
    return page_idx ^ (1 << order);
}

// 通过 buddy bitmap 检查伙伴是否空闲
static inline int buddy_is_free(struct page *buddy, unsigned int order) {
    unsigned long buddy_idx = page_to_pfn(buddy);
    unsigned long bit = buddy_idx >> (order + 1);
    return test_bit(bit, zone->free_area[order].map);
}

3.5 数据结构关系总览

下图展示了 zone、free_area、struct page 和 buddy bitmap 之间的协作关系：

3.6 数据结构协作流程

1. 分配请求到达：内存分配器根据请求大小计算所需阶 order，并确定迁移类型 migratetype。
2. 定位 free_area：从 zone 的 free_area[order] 开始查找，若该阶有空闲页块，则从对应迁移类型的 free_list[migratetype] 中取出。
3. 无空闲则升级：若当前阶无空闲，则向高阶查找，找到后分裂页块，并将低阶页块插入对应 free_list。
4. 更新位图：分配或释放页块时，同步更新 buddy bitmap 对应位，确保伙伴关系判定准确。
5. 释放与合并：释放页块时，通过 buddy bitmap 检查伙伴是否空闲，若空闲则合并为高阶页块，并递归向上合并。