不懂伙伴系统,别说精通linux内核

从内存碎片说起：为什么需要伙伴系统？

想象一下您正在整理一个图书馆。当新书不断被借走又归还时，书架上会出现越来越多的小空隙。虽然总空间可能还很大，但这些零散的空隙却无法容纳一本完整的书。计算机的物理内存管理面临着同样的挑战——内存碎片问题。

在Linux系统启动时，物理内存是一片连续的"沃土"。但随着进程的创建、销毁和内存的动态分配释放，这片沃土逐渐被分割成无数零散的小块。当一个进程需要分配一大块连续内存时，即使系统总空闲内存充足，也可能因为没有足够大的连续块而分配失败。

伙伴系统（Buddy System）正是Linux内核用来解决这一难题的精妙设计。它像一位聪明的图书管理员，不仅记录每一块空闲内存的位置，还能在需要时将相邻的小块"合并"成大块，实现高效的内存分配与回收。

伙伴系统的核心思想

伙伴系统的核心原理可以用一句话概括：将物理内存划分为大小为2的幂次方的块，并维护一个空闲链表数组，通过合并相邻的伙伴块来减少内存碎片。

基本术语

• 阶（Order）
  ：表示内存块大小的级别，order = 0 对应最小分配单元（通常是一个页面，4KB），order = n 对应 2^n 个页面
• 伙伴块
  ：两个相邻的、大小相同的内存块称为伙伴
• 空闲链表
  ：每个阶都维护一个链表，存放该阶的空闲内存块

分配过程

当内核需要分配 2^n 个页面时：

1. 首先检查第 n 阶的空闲链表是否有可用块
2. 如果有，直接分配该块
3. 如果没有，向更高阶（n+1）查找
4. 找到更高阶的块后，将其分裂成两个伙伴块，将其中一块分配出去，另一块加入 n 阶空闲链表

回收过程

当内核释放内存块时：

1. 将该块加入对应阶的空闲链表
2. 检查其伙伴块是否也在空闲链表中
3. 如果伙伴块也空闲，将两块合并成一个更高阶的块
4. 重复上述过程，直到无法再合并

Linux内核中的伙伴系统实现

在Linux内核中，伙伴系统的核心数据结构定义在 include/linux/mmzone.h 中：

structfree_area {
structlist_headfree_list[MIGRATE_TYPES];
unsignedlong nr_free;
};

structzone {
/* 每个阶的空闲区域 */
structfree_areafree_area[MAX_ORDER];

/* 管理区名称 */
char *name;

/* 管理区中的页面数 */
unsignedlong managed_pages;

/* 管理区起始地址（物理地址） */
phys_addr_t zone_start_pfn;

/* 水位标记，用于内存回收决策 */
unsignedlong watermark[NR_WMARK];

/* 自旋锁，保护free_area */
spinlock_t lock;
    ...
};

结构体成员注释：

• free_area
  ：数组，每个元素对应一个阶，维护该阶的空闲链表和空闲页数
• free_list
  ：链表头数组，按迁移类型（可移动、不可移动、回收等）分类
• nr_free
  ：该阶空闲页面总数
• managed_pages
  ：该管理区中被伙伴系统管理的页面数
• watermark
  ：内存水位标记（min/low/high），用于触发内存回收

核心操作：分配与释放

1. 页面分配函数 __alloc_pages

structpage *__alloc_pages(gfp_tgfp_mask, unsignedintorder,
structzonelist *zonelist)
{
structpage *page =NULL;
structzone *zone;
int z;

/* 遍历管理区列表 */
    for_each_zone_zonelist_nodemask(zone, z, zonelist, NULL) {
/* 检查管理区是否可用 */
if (!zone_watermark_ok(zone, order, gfp_mask))
continue;

/* 尝试分配 */
        page = rmqueue(zone, order, gfp_mask);
if (page)
break;
    }

return page;
}

2. 实际分配函数 rmqueue

staticinlinestruct page *rmqueue(struct zone *zone, unsignedint order,
gfp_t gfp_flags)
{
structpage *page;
unsignedint current_order;

/* 从请求的阶开始查找 */
for (current_order = order; current_order < MAX_ORDER; ++current_order) {
structfree_area *area = &zone->free_area[current_order];

/* 如果该阶有空闲块 */
if (!list_empty(&area->free_list[migratetype])) {
            page = list_first_entry(&area->free_list[migratetype],
struct page, lru);
            list_del(&page->lru);
            area->nr_free--;

/* 如果分裂出了更小的块，需要将剩余块加入低阶链表 */
while (current_order > order) {
                --current_order;
structpage *buddy = page + (1 << current_order);

/* 将伙伴块加入低阶空闲链表 */
                list_add(&buddy->lru, 
                         &zone->free_area[current_order].free_list[migratetype]);
                zone->free_area[current_order].nr_free++;
            }

return page;
        }
    }

returnNULL;
}

3. 页面释放函数 __free_pages

void __free_pages(struct page *page, unsignedint order)
{
structzone *zone = page_zone(page);

/* 释放页面到伙伴系统 */
    __free_pages_ok(page, order);
}

staticvoid __free_pages_ok(struct page *page, unsignedint order)
{
unsignedlong page_idx;
structzone *zone;
unsignedlong flags;

    zone = page_zone(page);
    page_idx = page_to_pfn(page) - zone->zone_start_pfn;

    spin_lock_irqsave(&zone->lock, flags);

/* 尝试合并伙伴块 */
while (order < MAX_ORDER - 1) {
structpage *buddy;
unsignedlong buddy_idx = page_idx ^ (1 << order);

/* 获取伙伴页面 */
        buddy = page + (buddy_idx - page_idx);

/* 检查伙伴是否空闲且可以合并 */
if (!page_is_buddy(page, buddy, order))
break;

/* 从空闲链表中移除伙伴 */
        list_del(&buddy->lru);
        zone->free_area[order].nr_free--;

/* 合并到更高阶 */
        page_idx = min(page_idx, buddy_idx);
        page = page + (page_idx - (page_to_pfn(page) - zone->zone_start_pfn));
        order++;
    }

/* 将最终的块加入空闲链表 */
    list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
    zone->free_area[order].nr_free++;

    spin_unlock_irqrestore(&zone->lock, flags);
}

关键技术点解析

1. 伙伴查找算法

伙伴系统使用异或运算快速定位伙伴块：

buddy_idx = page_idx ^ (1 << order);

例如，假设 order = 2（块大小为4页）：

• 如果当前块索引为 0b1000，伙伴索引为 0b1100
• 如果当前块索引为 0b1100，伙伴索引为 0b1000

这种设计保证了两个伙伴块的索引只有一个比特位不同。

2. 迁移类型（Migrate Types）

Linux内核将页面分为多种迁移类型，以优化内存分配：

enummigrate_type {
    MIGRATE_UNMOVABLE,   /* 不可移动页（内核数据结构） */
    MIGRATE_RECLAIMABLE, /* 可回收页（缓存页） */
    MIGRATE_MOVABLE,     /* 可移动页（用户空间页） */
    MIGRATE_PCPTYPES,    /* 每CPU页类型 */
    MIGRATE_RESERVE,     /* 保留页 */
    MIGRATE_ISOLATE,     /* 隔离页（用于内存热插拔） */
    NR_MIGRATE_TYPES
};

这种分类可以减少内存碎片，因为相同迁移类型的页面更可能被一起分配和释放。

3. 内存管理区（Zone）

Linux将物理内存划分为多个管理区，处理不同类型的内存：

实践：查看伙伴系统状态

在Linux系统中，可以通过以下命令查看伙伴系统的运行状态：

# 查看每个管理区的空闲内存分布
cat /proc/buddyinfo

# 输出示例：
# Node 0, zone      DMA      3      3      2      1      1      0      0      0      1      1      3
# Node 0, zone    DMA32   1551   1555    781    391    200    101     50     26     12      6      3
# Node 0, zone   Normal   2048   2049   1025    512    256    128     64     32     16      8      4

# 解释：每行代表一个管理区，数字代表各阶的空闲块数量

# 查看内存统计信息
cat /proc/meminfo

# 关注以下字段：
# MemTotal:       16384000 kB
# MemFree:        12288000 kB
# MemAvailable:   14336000 kB
# HugePages_Total:       0
# HugePages_Free:        0

性能优势与局限性

优势

1. 高效分配
   ：O(log N) 的时间复杂度
2. 减少碎片
   ：通过合并机制保持大块连续内存
3. 简单可靠
   ：算法逻辑清晰，易于实现和维护

局限性

1. 内部碎片
   ：分配的内存总是2的幂次方大小，可能造成浪费
2. 外部碎片
   ：虽然减少但无法完全消除
3. 高阶分配困难
   ：大内存块分配成功率较低

互动讨论

1. 思考： 在嵌入式系统中，内存资源通常非常有限。如果您正在为一个资源受限的嵌入式设备设计内存管理系统，您会对伙伴系统做哪些优化？为什么？

2. 讨论： 现代服务器通常配备数百GB甚至TB级别的内存。在这样的场景下，伙伴系统是否仍然适用？为什么Linux内核没有采用其他更复杂的内存分配策略？

关注'linux探究'微信公众号，获取更多Linux技术干货与版本更新资讯