os

伙伴系统、SLAB/SLUB 与 Linux 内存分配器

从伙伴系统的 2 的幂拆分与合并机制，到 SLAB/SLOB/SLUB 三种内核对象分配器的演进，再到 Linux 当前默认的 SLUB 实现、CMA 连续内存分配、per-CPU 页分配器与调试特性，本文系统深入地讲解操作系统内核内存分配的核心基础设施，帮助开发者理解 kmalloc 与 vmalloc 的本质差异。

Leeting Yan 10 分钟阅读 4626 字

操作系统内核需要管理物理内存，为自己和上层进程提供高效、可靠的分配服务。在页级分配之上，Linux 内核采用了**伙伴系统（Buddy System）**来管理连续物理页框；在对象级分配之上，则使用 SLAB/SLUB 等分配器来快速分配和回收内核数据结构。这两者共同构成了内核内存管理的基石。

本文从外部碎片与内部碎片这对核心矛盾出发，逐步展开伙伴系统的分裂与合并算法，对比 SLAB、SLOB、SLUB 三种内核对象分配器，深入讲解当前 Linux 默认的 SLUB 实现与调试特性，最后覆盖 CMA、per-CPU 页分配器以及 kmalloc 与 vmalloc 的区别。

一、外部碎片与内部碎片

1.1 两种碎片的定义

内存分配面临两种碎片问题：

  • 外部碎片（External Fragmentation）：内存总量足够，但没有一段连续的空闲区域能满足请求。例如，内存中有多个零散的空闲块，但每个都太小，无法满足一个需要大块连续的分配请求。
  • 内部碎片（Internal Fragmentation）：分配给请求者的内存块大于实际需求，多余的内部空间被浪费。例如，请求 100 字节但分配了 128 字节。

伙伴系统通过 2 的幂对齐策略在内部碎片和外部碎片之间取得平衡；而 SLAB/SLUB 分配器则通过对象缓存大幅减少了内部碎片。

二、伙伴系统（Buddy System）

2.1 核心思想

伙伴系统将物理内存划分为大小为 2 的幂次方的块（以页为单位）：1 页（2^0）、2 页（2^1）、4 页（2^2）……直到最大阶数（MAX_ORDER，Linux 内核中通常为 11，即 2^10 = 1024 页 = 4MB）。

每个阶数维护自己的空闲链表（free list）。当需要分配 2^k 页时：

  1. 检查第 k 阶的空闲链表，如果有空闲块，直接分配
  2. 如果没有，检查第 k+1 阶，找到一个更大的块将其**分裂（split）**为两个伙伴（buddy），一个用于分配，另一个放回第 k 阶链表
  3. 递归向上分裂直到找到可用的块

2.2 分配与释放算法

#define MAX_ORDER 11
#define PAGE_SIZE 4096

// 每个阶数的空闲块链表
typedef struct FreeBlock {
    struct FreeBlock *next;
    struct FreeBlock *prev;
    unsigned long start_pfn;  // 起始物理页框号
} FreeBlock;

FreeBlock *free_area[MAX_ORDER];  // 11 个阶数的空闲链表

// 判断两个块是否为"伙伴"：大小相同、地址相邻、起始地址对齐
static int is_buddy(unsigned long pfn1, unsigned long pfn2, int order) {
    unsigned long mask = (1UL << order);
    // 伙伴页的起始页号 XOR 块大小等于另一个伙伴的起始页号
    return (pfn1 ^ mask) == pfn2;
}

// 分裂一个 2^order 的块为两个 2^(order-1) 的伙伴
static void split_block(int order, unsigned long pfn) {
    unsigned long buddy_pfn = pfn + (1UL << (order - 1));
    printf("Split: order=%d pfn=%lu => two buddies at %lu and %lu\n",
           order, pfn, pfn, buddy_pfn);
    // 将下半块加入 free_area[order-1]
    add_to_free_list(order - 1, buddy_pfn);
}

// 分配 2^order 个连续页框
unsigned long buddy_alloc(int order) {
    // 从当前阶数开始向上查找
    for (int current = order; current < MAX_ORDER; current++) {
        if (free_area[current] != NULL) {
            // 找到一个可用块
            FreeBlock *block = free_area[current];
            remove_from_free_list(current, block);
            unsigned long pfn = block->start_pfn;
            free(block);

            // 如果找到的块比需求大，逐级分裂
            while (current > order) {
                current--;
                unsigned long buddy_pfn = pfn + (1UL << current);
                add_to_free_list(current, buddy_pfn);
            }
            return pfn;
        }
    }
    return 0;  // 分配失败
}

// 释放页框并尝试合并
void buddy_free(unsigned long pfn, int order) {
    add_to_free_list(order, pfn);
    printf("Free: order=%d pfn=%lu\n", order, pfn);

    // 尝试向上合并
    while (order < MAX_ORDER - 1) {
        unsigned long buddy_pfn = pfn ^ (1UL << order);
        FreeBlock *buddy = find_in_free_list(order, buddy_pfn);
        if (!buddy) break;  // 伙伴未释放，无法合并

        remove_from_free_list(order, buddy);
        free(buddy);
        // 合并后起始地址取较小的那个
        pfn = pfn < buddy_pfn ? pfn : buddy_pfn;
        order++;
        printf("Coalesce: new order=%d pfn=%lu\n", order, pfn);
    }
    add_to_free_list(order, pfn);
}

2.3 伙伴系统的优点与局限

优点：

  • 合并操作高效：通过地址异或运算即可定位伙伴
  • 不产生外部碎片（任何大小的请求最终都能找到匹配的块）
  • 分配和释放均为 O(log N) 时间复杂度

局限：

  • 内部碎片：请求的 2^k 页与实际需要的页数可能差异巨大
  • 粒度限制：最小分配单位是一整页（4KB），无法服务小于一页的内核对象分配
  • 对非 2 的幂大小的分配效率不高

三、SLAB/SLOB/SLUB 内核对象分配器

为了服务内核对象（如进程描述符 task_struct、文件对象 struct file 等）的频繁分配与释放，Linux 引入了多种对象级分配器。

3.1 SLAB 分配器

SLAB 分配器最早由 SunOS 的 Jeff Bonwick 提出，核心思想是：

  1. 为每种对象类型维护一个缓存（kmem_cache）
  2. 每个缓存由多个SLAB组成，每个 SLAB 是一组连续物理页
  3. 每个 SLAB 的状态分为三种：Full（全满）、Partial（部分空闲）、Empty（全空）

当分配对象时，优先从 Partial SLAB 中取出空闲对象；如果没有 Partial SLAB，从 Empty SLAB 中分配；如果连 Empty 都没有，向伙伴系统申请新的页框创建新 SLAB。

// SLAB 分配器的简化元数据结构
typedef struct KmemCache {
    char *name;              // 缓存名称，如 "task_struct"
    size_t obj_size;         // 对象原始大小
    size_t align;            // 对齐要求
    unsigned int flags;      // SLAB_* 标志
    
    struct Slab *partial;    // 部分空闲的 SLAB 链表
    struct Slab *full;       // 全满的 SLAB 链表
    struct Slab *free;       // 全空的 SLAB 链表
    
    // 构造函数/析构函数
    void (*ctor)(void *);
} KmemCache;

typedef struct Slab {
    struct Slab *next;
    struct Slab *prev;
    void *s_mem;             // SLAB 中第一个对象的地址
    unsigned int inuse;      // 已使用对象数
    unsigned int free;       // 下一个空闲对象的索引
    unsigned char *bitmap;   // 对象使用位图
} Slab;

3.2 SLOB 分配器

SLOB（Simple List Of Blocks）是一种简化的分配器，专为内存极度受限的嵌入式系统（如早期嵌入式 Linux）设计。它将所有空闲对象放在一个链表中，采用**首次适配（First-Fit）**策略。SLOB 的代码极简洁（只有几百行），但碎片问题严重，分配效率也较低。现代系统已很少使用。

3.3 SLUB 分配器

SLUB（SLAB Unqueued）由 Christoph Lameter 在 Linux 2.6.22 中引入，是当前 Linux 内核的默认分配器。相比 SLAB，SLUB 做了大量简化与优化：

  1. 去除了 Per-CPU 缓存队列（array_cache）的复杂结构：SLUB 使用更轻量的 per-CPU 局部页（cpu_slab）
  2. 统一 SLAB 元数据管理：不再区分三种 SLAB 状态链表，每个 node 只维护一个 Partial 链表
  3. 内置调试 easier：通过 Kconfig 打开调试选项（如 poison、redzone、tracking）即可获得丰富的诊断能力
  4. 默认对齐到硬件缓存行：减少 CPU 缓存伪共享
// SLUB 简化的 per-CPU 结构（概念示意）
struct kmem_cache_cpu {
    void **freelist;         // 当前 CPU slab 上的空闲对象链表
    struct page *page;       // 当前被该 CPU 使用的 slab 页
    int node;                // NUMA 节点
};

struct kmem_cache {
    const char *name;
    unsigned int size;       // 对齐后的对象大小
    unsigned int object_size;// 用户请求的对象大小
    
    struct kmem_cache_cpu __percpu *cpu_slab;
    
    // NUMA 节点级别的数据结构
    struct kmem_cache_node *node[MAX_NUMNODES];
};

SLUB 分配对象时的快速路径完全在 per-CPU 上下文中完成：

cpu_slab->freelist 有可用对象？
  ├── 是：弹出一个对象返回（无锁，极快）
  └── 否：
      ├── 检查 partial 链表
      │   └── 有：取一个 partial slab 作为 cpu_slab
      └── 无：向伙伴系统申请新页

四、Linux SLUB 实现细节

4.1 kmem_cache 创建与销毁

内核模块或子系统可以为特定对象类型创建专用缓存：

// 创建一个专用缓存
struct kmem_cache *my_cache;

my_cache = kmem_cache_create(
    "my_object_cache",     // 名称
    sizeof(struct my_obj), // 对象大小
    0,                     // 对齐（0 = 默认）
    SLAB_HWCACHE_ALIGN,    // 标志：按硬件缓存行对齐
    NULL                   // 构造函数
);

// 分配对象
struct my_obj *obj = kmem_cache_alloc(my_cache, GFP_KERNEL);

// 释放对象
kmem_cache_free(my_cache, obj);

// 销毁缓存
kmem_cache_destroy(my_cache);

4.2 SLUB 的调试特性

通过内核启动参数或 /sys/kernel/slab/ 接口，可以开启多种调试模式：

  • Poison（SLAB_POISON）：分配时填充 0x5a5a5a5a（“S”），释放时填充 0x6b6b6b6b（“k”）。如果程序读取到这些魔数，说明发生了 use-after-free 或 uninitialized read
  • Redzone（SLAB_RED_ZONE）：在对象前后添加保护区，检测越界写入
  • Tracking（SLAB_STORE_USER）：记录每次分配/释放的调用栈，用于分析内存泄漏
  • Panics：检测到损坏时立即触发 panic，便于调试
# 在启动参数中开启 SLUB 调试
slub_debug=PZU

# P = Poison
# Z = Redzone
# U = Store User (tracking)

4.3 /proc/slabinfo 分析

$ cat /proc/slabinfo | head -20
slabinfo - version: 2.1
# name       <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab>
kmem_cache      200    200    320   25    1
kmem_cache_node 384    384     64   64    1
nf_conntrack_ffff88007b...       32     32   1152    7    1
...

字段含义：

  • active_objs：当前活跃（已分配）的对象数量
  • num_objs：SLAB 中总对象数量
  • objsize：每个对象占用字节数
  • objperslab：每个 SLAB 页容纳的对象数
  • pagesperslab：每个 SLAB 占用多少页

五、CMA 连续内存分配

5.1 CMA 的设计动机

许多硬件设备（如 DMA 控制器、GPU、视频编解码器）要求分配的物理内存是连续的，且可能需要大块内存（如几 MB 到数百 MB）。传统的伙伴系统在高负载下难以满足大块连续内存请求。

CMA（Contiguous Memory Allocator）在内核启动时预留一片连续物理内存区域，这块区域平时可用于可迁移页（movable pages），当设备驱动需要时，CMA 将所有可迁移页搬离，腾出连续区域。

// 设备树（Device Tree）中配置 CMA 区域
// arch/arm64/boot/dts/xxx.dtsi
cma {
    compatible = "shared-dma-pool";
    size = <0x0 0x4000000>;  // 64MB
    alignment = <0x0 0x200000>;  // 2MB 对齐
    alloc-ranges = <0x0 0x80000000 0x0 0x40000000>;
};

5.2 CMA 分配 API

// 驱动中使用 CMA 分配
struct device *dev = ...;
dma_addr_t dma_handle;

void *vaddr = dma_alloc_coherent(dev, size, &dma_handle, GFP_KERNEL);
// 返回 CPU 虚拟地址 vaddr 和 DMA 总线地址 dma_handle
// 物理地址连续，且满足一致性（coherent）要求

dma_free_coherent(dev, size, vaddr, dma_handle);

六、per-CPU 页分配器

6.1 为什么要 per-CPU 分配

在多核系统中，多个 CPU 同时向全局页分配器申请内存时，必须加锁保护全局数据结构，导致严重的锁竞争。per-CPU 页分配器（PCP, Per-CPU Pageset）为每个 CPU 缓存一批本地页框，只有本地缓存不足时才访问全局伙伴系统，大幅降低锁竞争。

// per-CPU 页分配器在快速路径上的行为
void *alloc_page_fast(gfp_t gfp) {
    struct per_cpu_pages *pcp = &this_cpu_ptr(zone->pageset)->pcp;
    struct list_head *list = &pcp->lists[migratetype];
    
    // 本地缓存中有页？直接弹出一个（无锁）
    if (!list_empty(list)) {
        page = list_first_entry(list, struct page, lru);
        list_del(&page->lru);
        pcp->count--;
        return page;
    }
    
    // 本地缓存为空，走慢速路径（需要加全局锁）
    return __alloc_pages_slowpath(gfp, order);
}

6.2 水位线与批量策略

每个 per-CPU 缓存有高水位（high）和低水位（low）：

  • 当缓存低于低水位时，批量从伙伴系统补充
  • 当缓存超过高水位时，批量归还到伙伴系统

这平衡了缓存命中率和内存占用。

七、kmalloc 与 vmalloc 的区别

特性kmalloc/kzallocvmalloc/vzalloc
物理连续性要求物理地址连续仅虚拟地址连续，物理页可离散
最大大小受 MAX_ORDER 限制（通常 4MB）可达几乎整个虚拟地址空间
速度快（直接使用伙伴系统+SLUB）较慢（需要创建页表映射）
大小对齐2 的幂对齐，最小 8/16 字节页对齐（4KB）
适用场景小对象、DMA、需物理连续的内存大缓冲区、模块加载、内核映射
内部碎片可能有（2 的幂对齐）较大（必须页对齐）
// kmalloc 示例
char *buf = kmalloc(1024, GFP_KERNEL);   // 分配 1KB 物理连续内存
if (!buf) return -ENOMEM;
kfree(buf);

// vmalloc 示例：分配 8MB 大缓冲区
char *big_buf = vmalloc(8 * 1024 * 1024);
if (!big_buf) return -ENOMEM;
// big_buf 虚拟地址连续，但底层物理页可能散落各处
vfree(big_buf);

7.1 kmalloc 的内部实现

kmalloc 并非直接调用伙伴系统，而是通过 SLUB 的通用缓存实现。内核预先创建了一组大小固定的通用缓存（8, 16, 32, 64, 128 … up to 8KB），kmalloc 根据请求大小向上取整到最接近的缓存大小，从对应的缓存分配。

// 查看 kmalloc 的通用缓存
$ cat /proc/slabinfo | grep kmalloc
kmalloc-8k        32     32   8192    4    8
kmalloc-4k        64     64   4096    8    8
kmalloc-2k       128    128   2048   16    8
kmalloc-1k       256    256   1024   32    8
kmalloc-512      512    512    512   32    4
...

相关阅读

  • https://plumephp.com/os-linux-memory/ —— Linux 内存子系统中 OOM Killer、swap 与 cgroup 内存限制的深入分析
  • https://plumephp.com/os-virtual-memory/ —— 虚拟内存与分页机制的基础原理，理解页框管理的必要背景
  • https://plumephp.com/os-page-replacement-algorithms/ —— 页面置换算法详解，与伙伴系统回收连续页框的策略互补

延伸阅读

  1. Linux Kernel Source: mm/page_alloc.c（伙伴系统实现）、mm/slub.c（SLUB 分配器）
  2. Jeff Bonwick, “The Slab Allocator: An Object-Caching Kernel Memory Allocator”, USENIX 1994
  3. Christoph Lameter, “SLUB: The Unqueued Slab Allocator”, Linux Symposium 2007
  4. CMA 内核文档：Documentation/devicetree/bindings/reserved-memory/
  5. 《Understanding the Linux Kernel》内存管理章节
  6. Linux 内核启动参数 slub_debug= 完整文档
// ============================================================
// 完整可运行示例：伙伴系统分配/释放与合并模拟
// 编译: gcc -Wall -o buddy_demo buddy_demo.c
// ============================================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_ORDER 6  // 最大支持 32 页 = 128KB

typedef struct Block {
    int order;
    unsigned long start;
    struct Block *next;
} Block;

Block *free_lists[MAX_ORDER];
int used[MAX_ORDER][100];  // 简单标记已分配块

void init_buddy(void) {
    memset(free_lists, 0, sizeof(free_lists));
    memset(used, 0, sizeof(used));
    // 初始状态下第 MAX_ORDER-1 阶有一整块
    Block *b = calloc(1, sizeof(Block));
    b->order = MAX_ORDER - 1;
    b->start = 0;
    free_lists[MAX_ORDER - 1] = b;
}

void add_free(int order, unsigned long start) {
    Block *b = calloc(1, sizeof(Block));
    b->order = order;
    b->start = start;
    b->next = free_lists[order];
    free_lists[order] = b;
}

Block* take_free(int order) {
    Block *b = free_lists[order];
    if (b) free_lists[order] = b->next;
    return b;
}

unsigned long buddy_alloc(int order) {
    for (int o = order; o < MAX_ORDER; o++) {
        Block *b = take_free(o);
        if (!b) continue;
        unsigned long addr = b->start;
        free(b);
        // 分裂
        while (o > order) {
            o--;
            add_free(o, addr + (1UL << o));
        }
        used[order][addr] = 1;
        printf("ALLOC: order=%d start=%lu\n", order, addr);
        return addr;
    }
    printf("ALLOC FAILED: order=%d\n", order);
    return (unsigned long)-1;
}

void buddy_free(unsigned long addr, int order) {
    used[order][addr] = 0;
    while (order < MAX_ORDER - 1) {
        unsigned long buddy = addr ^ (1UL << order);
        // 简单线搜索伙伴是否在空闲列表中
        Block **p = &free_lists[order];
        int found = 0;
        while (*p) {
            if ((*p)->start == buddy) {
                Block *del = *p;
                *p = del->next;
                free(del);
                found = 1;
                break;
            }
            p = &(*p)->next;
        }
        if (!found) break;
        addr = addr < buddy ? addr : buddy;
        order++;
        printf("COALESCE: new order=%d addr=%lu\n", order, addr);
    }
    add_free(order, addr);
    printf("FREE: order=%d addr=%lu\n", order, addr);
}

int main() {
    init_buddy();
    printf("初始: MAX_ORDER=%d (最大块=%lu页)\n\n", MAX_ORDER, 1UL << (MAX_ORDER-1));

    unsigned long a1 = buddy_alloc(2);  // 4页
    unsigned long a2 = buddy_alloc(3);  // 8页
    unsigned long a3 = buddy_alloc(1);  // 2页

    printf("\n释放 a1 (order=2):\n");
    buddy_free(a1, 2);

    printf("\n释放 a2 (order=3):\n");
    buddy_free(a2, 3);  // 应与相邻空闲块合并

    printf("\n释放 a3 (order=1):\n");
    buddy_free(a3, 1);

    return 0;
}

继续阅读

探索更多技术文章

浏览归档，发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「os」更多文章

  1. ARM64 体系结构与内核实现
  2. 内核网络栈：sk_buff、NAPI 与 XDP
  3. eBPF 开发实战：CO-RE 与 libbpf