伙伴系统与 SLUB 分配器：Linux 物理内存管理的两层架构

在内核中写一行代码：

void *p = kmalloc(64, GFP_KERNEL);

3 微秒后你拿到了 64 字节的指针。看似简单，背后却涉及两套完全不同的分配器协同工作：

1. 伙伴系统（Buddy System） 管理物理页面——以 4KB 为最小单位，按 2 的幂次分配连续页面。
2. SLUB 分配器 把伙伴系统拿到的页面切碎成小对象——64 字节、128 字节、256 字节的 kmalloc 缓存。

为什么不用一层搞定？因为物理内存管理面临两个截然不同的问题：大块连续内存的分配与回收（DMA 缓冲区、页表、大的内核数据结构），和大量小对象的高速分配（socket 缓冲区、inode、dentry）。用同一套机制同时解决这两个问题，要么太慢，要么太浪费。

这篇文章从底层到顶层拆解这两层架构。

一、为什么需要两层

物理页面的粒度问题

Linux 的物理内存以页帧（page frame）为基本单位，x86-64 上通常是 4KB。伙伴系统管理这些页帧，最小分配单位就是一个页——4096 字节。

但内核的大部分分配请求远小于 4KB：

如果每次分配 64 字节都去伙伴系统申请一个 4KB 的页，内存利用率只有 64/4096 = 1.5%。这在服务器上不可接受——一台运行数万连接的 Web 服务器，可能同时存在数百万个小对象。

性能的分层需求

伙伴系统的设计目标是减少外部碎片——它通过合并相邻空闲块来维护大的连续区域。这对 DMA、huge page、内核栈等需要连续物理内存的场景至关重要。但合并操作需要检查伙伴状态、可能触发链式合并，不适合每秒百万次的小对象分配。

SLUB 的设计目标是极速分配小对象——它预先从伙伴系统拿到整页，在页内维护空闲链表，分配和释放只需要几条指令。per-CPU 缓存更是把锁竞争降到几乎为零。

这是一个经典的分层抽象：底层（伙伴系统）保证物理内存的结构性和连续性，上层（SLUB）在此之上提供高吞吐的小对象分配。我认为这种分层设计是 Linux 内存管理最精妙的架构决策之一——它让两个子系统各自专注于自己擅长的事情。

二、伙伴系统深入解析

二叉分解：分配大小的表示

伙伴系统的核心思想来自 Knuth 在《计算机程序设计艺术》中描述的算法：任何分配请求都向上取整到 2 的幂次个页面。

Linux 伙伴系统管理 11 个阶（order）：

当你请求 5 个页面时，系统会向上取整到 order 3（8 个页面），浪费 3 个页面。这就是内部碎片——伙伴系统为了维护 2 的幂次结构而付出的代价。

空闲链表与分裂

每个内存区域（zone）为每个阶维护一个空闲链表。数据结构大致如下：

struct zone {
    struct free_area free_area[MAX_ORDER]; // MAX_ORDER = 11
    // ...
};

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

分配过程（以请求 order 2 为例）：

1. 查看 free_area[2] 的空闲链表——如果有空闲块，取出一个，完成。
2. 如果 order 2 为空，向上查找 order 3。
3. 找到一个 order 3 的块（8 页），分裂（split）成两个 order 2 的块（各 4 页）。
4. 一个返回给调用者，另一个放入 free_area[2] 的空闲链表。
5. 如果 order 3 也为空，继续向上找 order 4，分裂两次。

这个过程最坏情况下需要从 order 10 一路分裂到 order 0——10 次分裂操作。但实际中很少发生，因为系统运行一段时间后，各阶都会有空闲块。

合并：伙伴查找的异或技巧

释放比分配更有趣。当一个 order n 的块被释放时，系统检查它的伙伴（buddy）是否也空闲。如果是，两者合并成一个 order n+1 的块。这个过程递归进行，直到伙伴不空闲或达到最大阶。

关键问题：如何找到伙伴的地址？

假设一个 order n 的块起始页帧号是 pfn，它的伙伴页帧号是：

buddy_pfn = pfn ^ (1 << order);

这就是著名的异或技巧。原理很简单：order n 的两个伙伴在地址空间中相邻，它们的起始地址只在第 order 位上不同。异或这一位就能在两个伙伴之间切换。

举例：

order = 2 (4 页一组)

pfn = 0b...01000 (页帧 8)  → buddy = 8 ^ 4 = 12  (页帧 12)
pfn = 0b...01100 (页帧 12) → buddy = 12 ^ 4 = 8   (页帧 8)

pfn = 0b...10000 (页帧 16) → buddy = 16 ^ 4 = 20  (页帧 20)
pfn = 0b...10100 (页帧 20) → buddy = 20 ^ 4 = 16  (页帧 16)

内核中的实际代码（mm/page_alloc.c）：

static inline unsigned long
__find_buddy_pfn(unsigned long page_pfn, unsigned int order)
{
    return page_pfn ^ (1 << order);
}

合并过程的伪代码：

void free_pages(struct page *page, unsigned int order)
{
    unsigned long pfn = page_to_pfn(page);

    while (order < MAX_ORDER - 1) {
        unsigned long buddy_pfn = pfn ^ (1 << order);
        struct page *buddy = pfn_to_page(buddy_pfn);

        if (!page_is_buddy(buddy, order))
            break;  // 伙伴不空闲或阶不匹配

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

        // 合并：取两者中较小的 pfn 作为新块的起始
        pfn = pfn & ~(1 << order);  // 清除第 order 位
        order++;
    }

    // 将合并后的块加入对应阶的空闲链表
    list_add(&page->lru, &free_area[order].free_list);
    free_area[order].nr_free++;
}

我个人觉得这个异或技巧是计算机科学中最优雅的位操作之一。它利用了 2 的幂次对齐的数学性质，把一个看似需要查表的操作变成了单条指令。

反碎片化：迁移类型

伙伴系统最大的敌人是外部碎片。考虑这个场景：系统运行一段时间后，物理内存中交错着已分配和空闲的页面，即使空闲页面总数足够，也可能凑不出一个连续的 order 3 块。

Linux 2.6.24 引入了迁移类型（migrate type）来缓解这个问题。每个 pageblock（通常是 huge page 大小，x86-64 上是 2MB = 512 页）被标记为以下类型之一：

思路很简单：把相同类型的分配聚集在一起。可移动的页面放在一起，需要连续空间时，可以通过页面迁移（page migration）把它们搬走。不可移动的页面也聚在一起，避免它们零散地阻碍合并。

这不是完美方案——当某种类型的空间不够时，会退化（fallback）到其他类型，碎片化仍然会逐渐发生。但在实践中，它把碎片化推迟了很久，给了内存压缩（compaction）足够的时间窗口来整理碎片。

读懂 /proc/buddyinfo

cat /proc/buddyinfo

输出示例：

Node 0, zone      DMA      1      1      0      0      2      1      1      0      1      1      3
Node 0, zone    DMA32    463    355    194     88     52     27     12      6      3      2    152
Node 0, zone   Normal  34729  18252   8471   3826   1692    725    298    121     44     15    209

每行对应一个 NUMA 节点的一个内存区域，数字从左到右分别是 order 0 到 order 10 的空闲块数量。

解读上面的 Normal zone： - order 0（4KB）：34729 个空闲块 = ~135 MB - order 10（4MB）：209 个空闲块 = ~836 MB

如果你发现高阶空闲块很少（比如 order 9 和 order 10 都是 0），而低阶空闲块很多，这说明内存碎片化严重。这时即使总空闲内存充足，也可能无法分配 huge page。

内存压缩（Compaction）

当高阶分配失败时，内核会尝试内存压缩——扫描内存，把可移动的页面从低地址搬到高地址（或反过来），在中间腾出连续空间。

压缩有两个扫描器： - 迁移扫描器（migration scanner）：从低地址向上扫描，找可移动的页面。 - 空闲扫描器（free scanner）：从高地址向下扫描，找空闲的页面。

两个扫描器相遇时，压缩结束。过程中，可移动的页面被重新映射到空闲页面的位置，原来的位置就空出来形成连续区域。

压缩前:  [U][M][ ][M][U][ ][ ][M][ ][U]
                                        
迁移扫描器 →                ← 空闲扫描器

压缩后:  [U][ ][ ][ ][U][M][M][M][ ][U]
              ^^^^^^^^
              连续空闲区域

（U = Unmovable, M = Movable, [ ] = Free）

压缩是比较昂贵的操作——需要修改页表项并刷新 TLB。但比 OOM killer 杀进程强多了。可以通过 /proc/sys/vm/compact_memory 手动触发：

echo 1 > /proc/sys/vm/compact_memory

我在生产环境中见过碎片化导致 transparent huge page（THP）分配持续失败的情况。监控 /proc/buddyinfo 的高阶空闲块数量，在碎片化严重时主动触发压缩或者干脆关闭 THP，是比较实用的运维手段。

三、从 SLAB 到 SLUB 的演进

SLAB 分配器（Bonwick, 1994）

Jeff Bonwick 在 1994 年为 SunOS 5.4 设计了 SLAB 分配器，后来被 Linux 采用。核心思想是：

1. 对象缓存（Object Caching）：为每种大小（或每种内核数据结构）维护一个缓存。缓存中预分配了大量对象，分配时直接取出，释放时放回，避免反复初始化。

2. Slab：缓存的基本管理单位。一个 slab 是一个或多个连续的物理页面，被划分成固定大小的对象。

3. 着色（Coloring）：不同 slab 中相同偏移位置的对象可能映射到 CPU 缓存的同一行（cache line conflict）。着色通过在 slab 开头添加不同大小的偏移，让不同 slab 中的对象错开缓存行。

SLAB 的三链表结构：

kmem_cache
  ├── slabs_full    (所有对象都已分配的 slab)
  ├── slabs_partial  (部分对象已分配的 slab)
  └── slabs_free     (所有对象都空闲的 slab)

每个 slab 内部用一个 kmem_bufctl_t 数组作为空闲对象索引。

为什么 SLAB 太复杂了

SLAB 在设计之初（1994 年）面对的是单 CPU 系统。随着 SMP、NUMA 架构普及，SLAB 逐渐变得臃肿：

1. per-CPU 阵列缓存 + 共享缓存 + 三链表 = 太多队列。对于一个有 1024 个 CPU 的 NUMA 系统，每个 kmem_cache 需要维护 1024 个 per-CPU 缓存 + 多个 NUMA 节点的共享缓存 + 三链表。光是元数据就消耗大量内存。

2. NUMA 感知差。SLAB 的 NUMA 支持是后来打补丁加的，每个节点有独立的三链表，但对象在节点之间的迁移逻辑复杂且容易出 bug。

3. 调试困难。SLAB 代码超过 5000 行，充满了性能优化的特殊路径。内核开发者修改内存分配器的信心越来越低。

4. 对象构造函数（constructor）在实践中很少用到。SLAB 的一个卖点是对象复用时不需要重新初始化，但大部分内核对象在释放时状态已经脏了，分配时仍需完全初始化。

SLUB 的诞生（Christoph Lameter, 2007）

Christoph Lameter 在 2007 年提出了 SLUB，它在 Linux 2.6.22 中合入，成为默认分配器。设计哲学是简化：

• 去掉三链表——改用 per-CPU slab + 节点 partial 链表。
• 去掉着色——现代 CPU 的缓存关联度足够高，着色的收益可以忽略。
• 去掉空闲对象索引数组——改用对象内嵌的空闲链表指针。
• 去掉对象构造函数——几乎没人用。
• 代码量从 ~5000 行降到 ~2500 行。

SLUB 的核心数据结构：

struct kmem_cache {
    struct kmem_cache_cpu __percpu *cpu_slab;  // per-CPU 数据
    unsigned int size;       // 对象大小（含元数据）
    unsigned int object_size; // 用户请求的对象大小
    unsigned int offset;     // 空闲指针在对象中的偏移
    struct kmem_cache_order_objects oo; // slab 的阶和对象数
    gfp_t allocflags;       // 分配标志
    int refcount;           // 引用计数
    struct list_head list;  // 所有 kmem_cache 的全局链表
    struct kmem_cache_node *node[MAX_NUMNODES]; // 每个 NUMA 节点的数据
    // ...
};

struct kmem_cache_cpu {
    void **freelist;         // 当前 slab 的空闲链表头
    struct page *page;       // 当前正在使用的 slab 页面
    struct page *partial;    // per-CPU partial 链表（frozen slabs）
    unsigned int tid;        // 事务 ID，用于无锁操作
};

struct kmem_cache_node {
    spinlock_t list_lock;
    unsigned long nr_partial; // partial 链表中的 slab 数量
    struct list_head partial; // 节点级 partial 链表
};

我认为 SLUB 替代 SLAB 是 Linux 内核演进中一个教科书式的重构案例：新设计在代码量减半的同时，性能持平甚至更好。这得益于对”哪些特性真的有用”的清醒判断。

四、SLUB 内部机制详解

分配的快速路径

SLUB 的分配路径分为三级，越往后越慢：

快速路径（fastpath）：从当前 CPU 的 freelist 取对象。

// 简化的 kmalloc 快速路径
void *kmalloc(size_t size, gfp_t flags)
{
    struct kmem_cache *s = kmalloc_caches[size_index(size)];
    return slab_alloc(s, flags);
}

static void *slab_alloc(struct kmem_cache *s, gfp_t gfpflags)
{
    struct kmem_cache_cpu *c;
    void *object;

redo:
    c = this_cpu_ptr(s->cpu_slab);
    object = c->freelist;

    if (likely(object)) {
        // 快速路径：直接从 freelist 取
        void *next = get_freepointer(s, object);
        // 使用 cmpxchg_double 实现无锁更新
        if (this_cpu_cmpxchg_double(s->cpu_slab->freelist, s->cpu_slab->tid,
                                     object, tid,
                                     next, next_tid(tid)))
            return object;
        goto redo;  // CAS 失败，重试
    }

    // 慢速路径
    return __slab_alloc(s, gfpflags, c);
}

快速路径的关键：无锁。通过 cmpxchg_double（x86 的 CMPXCHG16B 指令）原子更新 freelist 指针和事务 ID，不需要任何锁。这意味着多个 CPU 可以同时从各自的 per-CPU slab 分配对象，完全无竞争。

慢速路径 1：当前 per-CPU slab 的 freelist 为空——检查 per-CPU partial 链表。

static void *__slab_alloc(struct kmem_cache *s, gfp_t gfpflags,
                           struct kmem_cache_cpu *c)
{
    struct page *page;

    // 尝试 per-CPU partial 链表
    page = c->partial;
    if (page) {
        c->partial = page->next;
        c->page = page;
        c->freelist = page->freelist;
        page->freelist = NULL;  // "冻结"这个 slab
        return slab_alloc_fastpath(s, c);
    }

    // 慢速路径 2：从节点 partial 链表获取
    return new_slab_objects(s, gfpflags);
}

慢速路径 2：per-CPU partial 也为空——从 NUMA 节点的 partial 链表获取 slab，或者调用伙伴系统分配新的页面。

static void *new_slab_objects(struct kmem_cache *s, gfp_t flags)
{
    struct kmem_cache_node *n = get_node(s, numa_node_id());
    struct page *page;

    // 尝试从节点 partial 链表获取
    spin_lock(&n->list_lock);
    page = get_partial_node(n);
    spin_unlock(&n->list_lock);

    if (page)
        return setup_cpu_slab(s, page);

    // 最终手段：从伙伴系统分配新页面
    page = allocate_slab(s, flags);  // 调用 alloc_pages()
    return setup_cpu_slab(s, page);
}

对象内嵌的空闲链表

SLAB 用独立的数组记录空闲对象索引。SLUB 的做法更激进：把空闲链表指针直接存在空闲对象内部。

一个 slab 页面（假设对象大小 64 字节，4KB 页可容纳 64 个对象）:

+--------+--------+--------+--------+--------+-----+--------+
| obj 0  | obj 1  | obj 2  | obj 3  | obj 4  | ... | obj 63 |
+--------+--------+--------+--------+--------+-----+--------+

空闲链表（假设 obj 1, 3, 4 已分配，其余空闲）:

freelist → obj 0 → obj 2 → obj 5 → obj 6 → ... → obj 63 → NULL
               ^        ^        ^
               |        |        |
          这些指针存储在对象内存的前 8 字节

当对象被分配给用户时，用户数据会覆盖这个指针——这完全没问题，因为已分配的对象不需要在链表中。释放时，对象的前几个字节又被写回链表指针。

这个设计的优点是零额外内存开销——不需要任何元数据数组。缺点是：如果发生 use-after-free 或缓冲区溢出，空闲链表指针可能被破坏，导致分配器返回错误地址甚至任意地址——这是内核安全漏洞的常见来源。

冻结 slab（Frozen Slab）

SLUB 引入了”冻结”的概念。当一个 slab 被某个 CPU 的 per-CPU 缓存持有时，它处于”冻结”状态——其他 CPU 不能直接操作它的空闲链表。这避免了锁竞争。

当一个冻结的 slab 所有对象都被分配完（freelist 为空），它被”解冻”并从 per-CPU 缓存移除。当其上的对象被释放时，如果不再被任何 CPU 冻结，它可以回到节点 partial 链表。

CPU 0 的 per-CPU 缓存:
  page (frozen) → freelist: obj3 → obj7 → obj12 → NULL
  partial → slab_A (frozen) → slab_B (frozen) → NULL

Node 0 partial 链表:
  slab_C (unfrozen) → slab_D (unfrozen) → NULL

SLUB 调试

SLUB 提供了强大的调试功能，可以通过内核启动参数或 sysfs 开启：

Red Zone（红区）：在对象前后各添加一段填充区域，填入特殊模式（0xbb）。释放时检查红区是否被破坏——如果被破坏，说明发生了缓冲区溢出。

+----------+--------+-----------+
| red zone | object | red zone  |
| 0xbb...  | (data) | 0xbb...   |
+----------+--------+-----------+

Poisoning（毒化）：空闲对象被填充特殊模式（0x6b），分配时检查是否仍然完整——如果被修改，说明发生了 use-after-free 写入。

Tracking（跟踪）：记录每次分配和释放的调用栈。用于追踪内存泄漏和 double-free。

启用调试：

# 启动参数（全局）
slub_debug=FPZU

# 运行时（针对特定缓存）
echo 1 > /sys/kernel/slab/kmalloc-64/red_zone
echo 1 > /sys/kernel/slab/kmalloc-64/poison
echo 1 > /sys/kernel/slab/kmalloc-64/trace

# 查看 slab 统计
cat /proc/slabinfo
# 或者用 slabtop
slabtop -o

我在内核模块开发中大量使用 slub_debug=FPZU。它确实会让分配变慢（增加检查和填充操作），但对于发现 use-after-free 和 buffer overflow 极为有效。建议开发和测试环境始终开启。

五、两层协作：kmalloc 的完整路径

现在我们可以完整追踪 kmalloc(64, GFP_KERNEL) 的路径：

用户调用: kmalloc(64, GFP_KERNEL)
    |
    v
kmalloc_caches[size_index(64)] → 找到 kmalloc-64 缓存
    |
    v
SLUB 快速路径: 检查 per-CPU freelist
    |
    ├── 有空闲对象 → 原子取出 → 返回指针（~几十纳秒）
    |
    └── 无空闲对象 → 慢速路径
            |
            ├── per-CPU partial 有 slab → 切换 slab → 取对象
            |
            ├── 节点 partial 有 slab → 加锁获取 → 取对象
            |
            └── 都没有 → 调用 alloc_pages(GFP_KERNEL, order)
                    |
                    v
                伙伴系统: 从 free_area[order] 分配页面
                    |
                    ├── 对应阶有空闲块 → 取出 → 返回
                    |
                    └── 没有 → 向上查找更高阶 → 分裂 → 返回
                            |
                            └── 全部没有 → 触发回收/压缩/OOM

kmalloc 的大小类

Linux 预创建了一系列 kmalloc 缓存：

cat /proc/slabinfo | grep kmalloc

典型输出：

kmalloc-8192       32     32   8192    4    8 : tunables    0    0    0 : ...
kmalloc-4096       64     64   4096    8    8 : tunables    0    0    0 : ...
kmalloc-2048      128    128   2048   16    8 : tunables    0    0    0 : ...
kmalloc-1024      256    256   1024   32    8 : tunables    0    0    0 : ...
kmalloc-512       512    512    512    8    1 : tunables    0    0    0 : ...
kmalloc-256       768    768    256   16    1 : tunables    0    0    0 : ...
kmalloc-192      2940   2940    192   21    1 : tunables    0    0    0 : ...
kmalloc-128      1024   1024    128   32    1 : tunables    0    0    0 : ...
kmalloc-96       1260   1260     96   42    1 : tunables    0    0    0 : ...
kmalloc-64       2048   2048     64   64    1 : tunables    0    0    0 : ...
kmalloc-32       3072   3072     32  128    1 : tunables    0    0    0 : ...
kmalloc-16       4096   4096     16  256    1 : tunables    0    0    0 : ...
kmalloc-8        8192   8192      8  512    1 : tunables    0    0    0 : ...

注意 kmalloc-192 和 kmalloc-96——它们不是 2 的幂。Linux 在 2 的幂之间插入了一些中间大小（96、192），减少内部碎片。如果只有 2 的幂（64、128、256），一个 65 字节的请求会被分配 128 字节，浪费 49%。有了 96 字节的缓存，65 字节只浪费 32%。

当请求大小超过 KMALLOC_MAX_CACHE_SIZE（通常是 8KB 或 page order 1）时，kmalloc 直接调用伙伴系统的 alloc_pages()，不经过 SLUB。

六、与用户态分配器的比较

内核的 SLAB/SLUB 设计对用户态分配器有深远影响。

jemalloc 的 slab 灵感

jemalloc（Facebook 开发，被 FreeBSD 和 Android 使用）的 small bin 机制直接借鉴了内核 slab：

设计理念的共通性

内核分配器和用户态分配器面临同样的核心矛盾：

1. 速度 vs 碎片：per-CPU/per-thread 缓存极快但可能囤积内存；全局池碎片少但锁竞争大。
2. 内部碎片 vs 外部碎片：固定大小类导致内部碎片；变长分配导致外部碎片。
3. 吞吐量 vs 延迟：批量操作提高吞吐但增加尾延迟。

这些矛盾在内核态和用户态是完全一致的。区别在于约束条件不同：内核不能用 mmap 按需映射虚拟地址（伙伴系统管理的是物理页面），不能容忍分配失败（OOM 是最后手段），也不能阻塞在中断上下文中（GFP_ATOMIC）。

我认为理解内核的 SLUB 是理解所有用户态分配器的最佳捷径。因为内核面临的约束更严苛，设计上必须更精确，没有”用虚拟内存兜底”的余地。一旦理解了 SLUB，再看 jemalloc 或 tcmalloc，会有”不过如此”的感觉。

七、工程陷阱速查表

八、实现：简易伙伴分配器

以下是一个完整的伙伴系统实现，支持分配、释放和合并。约 200 行 C 代码，用于演示核心算法。

/*
 * buddy.c - 简易伙伴分配器
 *
 * 管理一块 2^MAX_ORDER 个页面的连续内存区域。
 * 支持按阶分配和释放，释放时自动合并伙伴。
 *
 * 编译: gcc -o buddy buddy.c -Wall -Wextra
 * 运行: ./buddy
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define MAX_ORDER   10          /* 最大阶：2^10 = 1024 页 */
#define PAGE_SIZE   4096
#define TOTAL_PAGES (1 << MAX_ORDER)

/* 页面状态 */
enum page_status {
    PAGE_FREE,
    PAGE_USED,
    PAGE_BUDDY,  /* 空闲且在空闲链表中 */
};

/* 页面描述符（类似 Linux 的 struct page 简化版） */
struct page {
    enum page_status status;
    int order;              /* 当前块的阶（仅首页有效） */
    struct page *prev;      /* 双向链表：前驱 */
    struct page *next;      /* 双向链表：后继 */
};

/* 空闲链表头（每个阶一个，用哨兵节点简化操作） */
struct free_list {
    struct page head;       /* 哨兵节点 */
    int count;
};

/* 伙伴分配器上下文 */
struct buddy_allocator {
    struct page pages[TOTAL_PAGES];       /* 页面描述符数组 */
    struct free_list free_lists[MAX_ORDER + 1]; /* order 0 到 MAX_ORDER */
    char memory[TOTAL_PAGES * PAGE_SIZE]; /* 模拟的物理内存 */
};

/* ---- 双向链表操作 ---- */

static void list_init(struct free_list *fl)
{
    fl->head.prev = &fl->head;
    fl->head.next = &fl->head;
    fl->count = 0;
}

static void list_add(struct free_list *fl, struct page *p)
{
    p->next = fl->head.next;
    p->prev = &fl->head;
    fl->head.next->prev = p;
    fl->head.next = p;
    fl->count++;
    p->status = PAGE_BUDDY;
}

static void list_del(struct free_list *fl, struct page *p)
{
    p->prev->next = p->next;
    p->next->prev = p->prev;
    p->prev = NULL;
    p->next = NULL;
    fl->count--;
}

static int list_empty(struct free_list *fl)
{
    return fl->head.next == &fl->head;
}

/* ---- 辅助函数 ---- */

static int page_to_pfn(struct buddy_allocator *ba, struct page *p)
{
    return (int)(p - ba->pages);
}

static struct page *pfn_to_page(struct buddy_allocator *ba, int pfn)
{
    return &ba->pages[pfn];
}

/* 伙伴查找：异或技巧 */
static int find_buddy_pfn(int pfn, int order)
{
    return pfn ^ (1 << order);
}

/* ---- 核心接口 ---- */

/*
 * buddy_init - 初始化伙伴分配器
 *
 * 将整块内存作为一个 MAX_ORDER 的空闲块。
 */
void buddy_init(struct buddy_allocator *ba)
{
    memset(ba, 0, sizeof(*ba));

    /* 初始化所有空闲链表 */
    for (int i = 0; i <= MAX_ORDER; i++)
        list_init(&ba->free_lists[i]);

    /* 初始化所有页面描述符 */
    for (int i = 0; i < TOTAL_PAGES; i++) {
        ba->pages[i].status = PAGE_FREE;
        ba->pages[i].order = -1;
        ba->pages[i].prev = NULL;
        ba->pages[i].next = NULL;
    }

    /* 整块内存作为一个 MAX_ORDER 块放入空闲链表 */
    ba->pages[0].order = MAX_ORDER;
    list_add(&ba->free_lists[MAX_ORDER], &ba->pages[0]);
}

/*
 * buddy_alloc - 分配 2^order 个连续页面
 *
 * 返回指向分配内存的指针，失败返回 NULL。
 */
void *buddy_alloc(struct buddy_allocator *ba, int order)
{
    if (order < 0 || order > MAX_ORDER)
        return NULL;

    /* 从请求的阶开始，向上查找有空闲块的阶 */
    int current_order = order;
    while (current_order <= MAX_ORDER) {
        if (!list_empty(&ba->free_lists[current_order]))
            break;
        current_order++;
    }

    if (current_order > MAX_ORDER)
        return NULL;  /* 没有足够的连续内存 */

    /* 从空闲链表取出一个块 */
    struct page *block = ba->free_lists[current_order].head.next;
    list_del(&ba->free_lists[current_order], block);

    /* 分裂：如果取到的块比请求的大，持续对半分裂 */
    while (current_order > order) {
        current_order--;
        int pfn = page_to_pfn(ba, block);
        int buddy_pfn = pfn + (1 << current_order);
        struct page *buddy = pfn_to_page(ba, buddy_pfn);

        /* 将后半部分（伙伴）放入更低阶的空闲链表 */
        buddy->order = current_order;
        list_add(&ba->free_lists[current_order], buddy);
    }

    /* 标记所有页面为已使用 */
    int pfn = page_to_pfn(ba, block);
    for (int i = 0; i < (1 << order); i++) {
        ba->pages[pfn + i].status = PAGE_USED;
    }
    block->order = order;

    return &ba->memory[pfn * PAGE_SIZE];
}

/*
 * buddy_free - 释放之前分配的内存
 *
 * ptr 必须是 buddy_alloc 返回的指针。
 */
void buddy_free(struct buddy_allocator *ba, void *ptr)
{
    if (!ptr)
        return;

    /* 从指针反推页帧号 */
    int offset = (int)((char *)ptr - ba->memory);
    int pfn = offset / PAGE_SIZE;

    if (pfn < 0 || pfn >= TOTAL_PAGES)
        return;

    struct page *block = pfn_to_page(ba, pfn);
    int order = block->order;

    /* 标记页面为空闲 */
    for (int i = 0; i < (1 << order); i++) {
        ba->pages[pfn + i].status = PAGE_FREE;
    }

    /* 尝试与伙伴合并 */
    while (order < MAX_ORDER) {
        int buddy_pfn = find_buddy_pfn(pfn, order);

        /* 检查伙伴是否在范围内 */
        if (buddy_pfn < 0 || buddy_pfn >= TOTAL_PAGES)
            break;

        struct page *buddy = pfn_to_page(ba, buddy_pfn);

        /* 伙伴必须空闲且阶匹配才能合并 */
        if (buddy->status != PAGE_BUDDY || buddy->order != order)
            break;

        /* 从空闲链表移除伙伴 */
        list_del(&ba->free_lists[order], buddy);
        buddy->order = -1;

        /* 合并：取较小的 pfn */
        pfn = pfn & ~(1 << order);
        order++;
    }

    /* 将合并后的块加入空闲链表 */
    block = pfn_to_page(ba, pfn);
    block->order = order;
    list_add(&ba->free_lists[order], block);
}

/*
 * buddy_dump - 打印当前空闲链表状态（类似 /proc/buddyinfo）
 */
void buddy_dump(struct buddy_allocator *ba)
{
    printf("Free lists (like /proc/buddyinfo):\n");
    printf("Order: ");
    for (int i = 0; i <= MAX_ORDER; i++)
        printf("%4d ", i);
    printf("\nCount: ");
    for (int i = 0; i <= MAX_ORDER; i++)
        printf("%4d ", ba->free_lists[i].count);
    printf("\nPages: ");
    for (int i = 0; i <= MAX_ORDER; i++)
        printf("%4d ", ba->free_lists[i].count * (1 << i));
    printf("\n");

    int total_free = 0;
    for (int i = 0; i <= MAX_ORDER; i++)
        total_free += ba->free_lists[i].count * (1 << i);
    printf("Total free pages: %d / %d (%.1f%%)\n\n",
           total_free, TOTAL_PAGES,
           100.0 * total_free / TOTAL_PAGES);
}

/* ---- 测试 ---- */

int main(void)
{
    static struct buddy_allocator ba;
    buddy_init(&ba);

    printf("=== 初始状态 ===\n");
    buddy_dump(&ba);

    printf("=== 分配 order 0 (1 页, 4KB) ===\n");
    void *p1 = buddy_alloc(&ba, 0);
    printf("  p1 = %p (pfn %ld)\n", p1, (long)(p1 - (void *)ba.memory) / PAGE_SIZE);
    buddy_dump(&ba);

    printf("=== 分配 order 3 (8 页, 32KB) ===\n");
    void *p2 = buddy_alloc(&ba, 3);
    printf("  p2 = %p (pfn %ld)\n", p2, (long)(p2 - (void *)ba.memory) / PAGE_SIZE);
    buddy_dump(&ba);

    printf("=== 分配 order 2 (4 页, 16KB) ===\n");
    void *p3 = buddy_alloc(&ba, 2);
    printf("  p3 = %p (pfn %ld)\n", p3, (long)(p3 - (void *)ba.memory) / PAGE_SIZE);
    buddy_dump(&ba);

    printf("=== 释放 p1 (order 0) ===\n");
    buddy_free(&ba, p1);
    buddy_dump(&ba);

    printf("=== 释放 p2 (order 3) ===\n");
    buddy_free(&ba, p2);
    buddy_dump(&ba);

    printf("=== 释放 p3 (order 2)，触发连锁合并 ===\n");
    buddy_free(&ba, p3);
    buddy_dump(&ba);

    /* 验证：分配整块内存 */
    printf("=== 分配 order 10 (整块 1024 页) ===\n");
    void *p4 = buddy_alloc(&ba, MAX_ORDER);
    printf("  p4 = %p (应该成功)\n", p4);
    buddy_dump(&ba);

    printf("=== 再分配 order 0（应该失败）===\n");
    void *p5 = buddy_alloc(&ba, 0);
    printf("  p5 = %p (应该是 NULL)\n", p5);

    printf("=== 释放 order 10，恢复初始状态 ===\n");
    buddy_free(&ba, p4);
    buddy_dump(&ba);

    printf("=== 碎片化测试：交替分配释放 ===\n");
    void *ptrs[16];
    for (int i = 0; i < 16; i++) {
        ptrs[i] = buddy_alloc(&ba, 0);
    }
    printf("分配了 16 个 order 0 块后:\n");
    buddy_dump(&ba);

    /* 释放偶数位置 */
    for (int i = 0; i < 16; i += 2) {
        buddy_free(&ba, ptrs[i]);
    }
    printf("释放偶数位置后（碎片化）:\n");
    buddy_dump(&ba);

    /* 尝试分配 order 1（需要 2 个连续页）*/
    void *p6 = buddy_alloc(&ba, 1);
    printf("分配 order 1: %p (应该成功，从高地址未碎片化区域取)\n", p6);
    buddy_dump(&ba);

    /* 释放所有 */
    for (int i = 1; i < 16; i += 2) {
        buddy_free(&ba, ptrs[i]);
    }
    buddy_free(&ba, p6);
    printf("全部释放后（应恢复初始状态）:\n");
    buddy_dump(&ba);

    printf("所有测试通过。\n");
    return 0;
}

编译和运行：

gcc -o buddy buddy.c -Wall -Wextra -O2
./buddy

预期输出（部分）：

=== 初始状态 ===
Free lists (like /proc/buddyinfo):
Order:    0    1    2    3    4    5    6    7    8    9   10
Count:    0    0    0    0    0    0    0    0    0    0    1
Pages:    0    0    0    0    0    0    0    0    0    0 1024
Total free pages: 1024 / 1024 (100.0%)

=== 分配 order 0 (1 页, 4KB) ===
  ...
Free lists (like /proc/buddyinfo):
Order:    0    1    2    3    4    5    6    7    8    9   10
Count:    0    1    1    1    1    1    1    1    1    1    0
Pages:    0    2    4    8   16   32   64  128  256  512    0
Total free pages: 1022 / 1024 (99.8%)

分配一个 order 0 的块导致 order 10 被分裂了 10 次——你可以看到 order 1 到 order 9 各有一个空闲块。这正是伙伴系统的特征：初始状态下的第一次小块分配会触发一系列分裂。但这些”碎片”是有序的——它们随时可以两两合并回高阶。

九、SLUB 的未来与替代方案

SLOB：嵌入式场景

Linux 内核实际上提供了三个 slab 分配器（虽然 SLOB 在 6.4 中被移除了）：

从 Linux 6.5 开始，SLUB 是唯一的 slab 分配器。SLAB 和 SLOB 都已从内核主线移除。这是简化内核的趋势——维护三套功能重叠的分配器的成本远高于收益。

SLUB 的持续优化

SLUB 仍在不断演进：

1. KFENCE（Kernel Electric Fence）：概率性采样的轻量级 use-after-free 和 out-of-bounds 检测器。它在每 N 次分配中随机选择一个，放入独立的防护页中。这比 slub_debug 开销小得多，适合在生产环境开启。

2. 随机化空闲链表：为了增加漏洞利用难度，SLUB 支持在 slab 初始化时随机化对象的空闲链表顺序（CONFIG_SLAB_FREELIST_RANDOM）。攻击者无法预测下一次分配返回的对象在 slab 中的位置。

3. 空闲指针混淆：CONFIG_SLAB_FREELIST_HARDENED 对空闲链表指针进行异或加密，use-after-free 漏洞更难利用。

我认为内存分配器是内核安全的关键战场。现代漏洞利用的第一步几乎总是”控制 slab 分配的布局”（heap feng shui）。SLUB 的安全加固措施——KFENCE、随机化、指针混淆——不是锦上添花，而是生死攸关的防线。

十、总结与个人思考

回到开头的问题：kmalloc(64, GFP_KERNEL) 背后发生了什么？

两层架构:

伙伴系统（Buddy System）
  - 管理物理页面，以 4KB 为单位
  - 11 个阶（order 0-10），按 2 的幂次组织
  - 分裂与合并，异或查找伙伴
  - 迁移类型防止碎片化
  - 压缩作为最后手段
        |
        | alloc_pages() / free_pages()
        |
        v
SLUB 分配器
  - 把页面切成小对象
  - per-CPU 无锁快速路径
  - 三级退化：per-CPU → 节点 partial → 新建 slab
  - 对象内嵌空闲链表
  - 调试：红区、毒化、跟踪

这个两层设计教给我几件事：

第一，分层是管理复杂性的最佳工具。 伙伴系统不需要知道小对象的存在，SLUB 不需要关心物理页面的合并。两者通过简洁的 alloc_pages / free_pages 接口通信。这种解耦让每一层都可以独立演进——SLAB 被 SLUB 替代时，伙伴系统不需要任何改动。

第二，简洁胜过精巧。 SLAB 的着色、构造函数、多层缓存在理论上都有道理，但实践证明大部分是过度设计。SLUB 砍掉了这些特性，代码量减半，性能反而更好。这让我想起 Rob Pike 的话：“少即是指数级的多。”

第三，安全是分配器设计中不可忽视的维度。 从 SLUB 的 red zone、poisoning，到 KFENCE、freelist 随机化、指针混淆——每一项都是对抗真实攻击的防线。在设计任何内存分配器时（不管是内核态还是用户态），“攻击者会如何利用这个分配器”应该是核心设计问题之一。

最后，理解底层让你写出更好的上层代码。 知道 kmalloc(64) 实际上走的是 per-CPU 无锁路径，你就不会在热路径上犹豫是否该缓存分配结果。知道 order > 1 的分配可能因碎片化失败，你就会主动避免在内核中请求大的连续内存。知道 GFP_ATOMIC 不能触发回收和压缩，你就会理解为什么中断上下文中的分配更容易失败。

这些知识不是理论——它们直接指导工程决策。

上一篇: I/O 调度：CFQ → mq-deadline → BFQ → kyber 下一篇: 文件系统的树

相关阅读: - 内存分配器对决：ptmalloc vs jemalloc vs tcmalloc vs mimalloc - epoll 的数据结构内幕