linux 内核 内存管理之 buddy 系统

---

一、Buddy 系统是什么？

Buddy 系统（伙伴系统）是 Linux 内核中用于管理和分配 物理内存页 的核心算法。它的主要目标是高效地分配和释放连续的物理内存块，并最大限度地减少外部碎片。

1. 核心思想

Buddy 系统的核心思想可以概括为：分而治之，合二为一。

• 分（Split）：当需要分配一块内存时，如果当前没有大小正好的内存块，系统会找到一个更大的空闲块，然后将其对半分割。分割后的两块互为“伙伴”（Buddy）。这个过程会一直持续，直到产生一块大小刚好满足需求的内存块。
• 合（Merge）：当一块内存被释放时，系统会检查其“伙伴”是否也处于空闲状态。如果伙伴也是空闲的，系统就会将这两块合并成一个更大的内存块。这个合并过程会递归进行，直到无法再向上合并为止。

2. 数据结构与实现

• 内存块大小 (order)：Buddy 系统管理的内存块大小都是 2 的幂次方。这个幂次被称为 “阶”（order）。一块内存的大小为 2^order 个物理页。
  • order = 0：内存块大小为 2^0 = 1 个页。
  • order = 1：内存块大小为 2^1 = 2 个页。
  • order = 2：内存块大小为 2^2 = 4 个页。
  • …
  • 最大 order 通常是 MAX_ORDER - 1（一般为 10，即最大可一次性分配 2^10 = 1024 个页，约 4MB）。
• free_area 数组：内核为每个内存管理区（Zone，如 ZONE_NORMAL, ZONE_DMA）都维护一个名为 free_area 的数组。这个数组是伙伴系统的核心数据结构。 struct free_area { struct list_head free_list; // 指向该 order 大小的空闲块链表 unsigned long nr_free; // 该 order 的空闲块数量 }; // 在 Zone 结构体中 struct zone { // ... struct free_area free_area[MAX_ORDER]; // ... }; free_area 数组的每个元素对应一个 order。free_area[i] 存储了所有大小为 2^i 个页的空闲内存块，这些块通过一个双向链表 free_list 连接起来。

3. 工作流程示例

分配过程：

1. 假设需要分配一个 8KB 大小的内存块（在 4KB 页大小的系统上，即 2 个页）。
2. 内核计算出需要的 order。2^1 = 2 个页，所以 order = 1。
3. 内核查询 free_area[1] 的 free_list，看是否有空闲块。
4. 如果有：直接从链表中取出一个块，分配给请求者。
5. 如果没有：内核会去查找 order = 2 的链表（即 free_area[2]，大小为 4 个页的块）。
6. 如果 free_area[2] 有空闲块，内核就取出一个。将其分裂成两个 order = 1 的块（互为伙伴）。一个块分配给请求者，另一个块被添加到 free_area[1] 的空闲链表中。
7. 如果 free_area[2] 也没有，就继续向上查找 free_area[3], free_area[4] … 直到找到空闲块为止，然后逐级分裂下来。如果直到 MAX_ORDER 都没有，则分配失败。

释放过程：

1. 假设一个 order = 1 的块被释放。
2. 内核首先通过该块的地址和 order 计算出其伙伴的地址。
3. 然后检查这个伙伴块是否也处于空闲状态，并且 order 也为 1。
4. 如果伙伴是空闲的：内核将这两个 order = 1 的块合并成一个 order = 2 的大块。然后，它会继续对这个新合并的 order = 2 的块重复这个过程，即检查它的伙伴是否空闲，尝试继续向上合并。
5. 如果伙伴不空闲：内核无法合并，只好直接将被释放的 order = 1 的块添加到 free_area[1] 的空闲链表中。

4. 优点

• 减少外部碎片：通过积极合并相邻的空闲块，Buddy 系统可以将小的空闲块聚合成大的连续空闲块，大大增加了分配大块连续内存的成功率。
• 分配和释放速度快：查找、分裂和合并操作的算法复杂度相对较低。

---

buddy 系统 页面分配流程图：

buddy 系统 页面释放流程图：

二、内核开发接口

1. 核心分配接口

这些函数是与 Buddy 系统交互的最直接方式，它们返回一个指向 struct page 的指针，struct page 是描述一个物理页的元数据结构。

• alloc_pages(gfp_mask, order):
  • 这是最核心的分配函数。
  • gfp_mask: 分配标志（Get Free Pages mask），用于控制分配行为。例如：
    • GFP_KERNEL: 常规分配，允许睡眠（阻塞），可以用在进程上下文中。
    • GFP_ATOMIC: 原子分配，不允许睡眠，必须立刻完成。常用于中断处理程序和自旋锁保护的临界区。
    • __GFP_ZERO: 一个修饰符，表示分配到的内存需要清零。
  • order: 需要分配的内存大小，2^order 个页。
  • 返回 struct page *。
• alloc_page(gfp_mask):
  • 一个方便的宏，等同于 alloc_pages(gfp_mask, 0)，用于分配单个页面。

2. 核心释放接口

• __free_pages(struct page *page, unsigned int order):
  • 最核心的释放函数，用于释放由 alloc_pages 分配的内存。
  • page: 要释放的内存块的起始页的 struct page 指针。
  • order: 释放的内存块大小。
• free_page(struct page *page):
  • 一个宏，等同于 __free_pages(page, 0)，用于释放单个页面。

3. 返回虚拟地址的便利接口

这些接口在内部分配了物理页后，会立即将其映射到内核的虚拟地址空间，并返回一个虚拟地址指针，使用起来更方便。

• __get_free_pages(gfp_mask, order):
  • 功能同 alloc_pages，但返回的是内核虚拟地址 (unsigned long 或 void *)。
• get_zeroed_page(gfp_mask):
  • 分配一个页并将其清零，返回内核虚拟地址。
• free_pages(unsigned long addr, unsigned int order):
  • 与 __get_free_pages 配套使用，释放指定虚拟地址对应的物理页。

重要关系：Slab/Slub/Slob 分配器（如 kmalloc/kfree）是构建在 Buddy 系统之上的。当 Slab 分配器需要一块新的内存“板坯（slab）”来切割成小对象时，它会调用 alloc_pages 从 Buddy 系统获取一块或多块连续的物理页。因此，Buddy 系统是更高层内存分配器的基础。

---

三、在内核中的具体应用

Buddy 系统作为基础物理内存分配器，在内核中无处不在。几乎所有需要 大块连续物理内存 的地方都会直接或间接地使用它。

1. Slab/Slub/Slob 分配器:
   • 这是 Buddy 系统最大的“客户”。当内核需要为各种小对象（如 task_struct, inode, dentry, 文件对象等）分配内存时，会通过 kmalloc 请求。kmalloc 从 Slab 分配器获取内存。如果 Slab 分配器中没有合适的缓存，它就会调用 alloc_pages 向 Buddy 系统申请一大块连续内存（称为 slab），然后自己管理这块内存，将其切成小块进行分配。
2. 设备驱动程序:
   • 许多硬件设备，特别是需要 DMA (Direct Memory Access) 的设备，要求使用物理上连续的内存缓冲区。例如，网卡的接收/发送环形缓冲区、声卡的音频缓冲区、显卡的帧缓冲区等。这些驱动会调用 alloc_pages 或 dma_alloc_coherent (其底层也依赖页分配器) 来获取这块连续的物理内存。
3. 页表处理:
   • 当一个进程发生 缺页中断 (Page Fault)，需要一个新的物理页来映射到它的虚拟地址空间时，缺页异常处理程序会调用 alloc_page 从 Buddy 系统获得一个空闲的物理页。
4. 内核栈:
   • 每个内核线程都有自己的内核栈，通常是 8KB 或 16KB（即 order=1 或 order=2）。这块连续的内存就是通过 Buddy 系统分配的。
5. 内核模块加载:
   • 使用 insmod 加载内核模块（.ko 文件）时，模块的代码段和数据段需要被加载到内存中。内核会使用 alloc_pages (通常通过 module_alloc 封装) 为模块分配连续的内存空间。
6. 页缓存 (Page Cache) 和 缓冲区缓存 (Buffer Cache):
   • 当内核从磁盘读取文件数据时，会将数据缓存在内存中以加速后续访问。这些缓存就是以页为单位存放在物理内存中的，而这些物理页正是由 Buddy 系统分配的。