第28章内存分配器实现

课程目录第28章内存分配器实现

第二十八章：内存分配器实现：实现一个简单的malloc/free、伙伴系统、slab分配器

内存分配器，说白了就是自己管内存。很多嵌入式开发的朋友觉得直接用标准库的 malloc/free 就完事了，但我在实际项目中吃过不少亏——碎片化、分配延迟、确定性不够，这些问题在实时系统里都是致命的。这一章，咱们手撸三个经典分配器：简单 malloc/free、伙伴系统、slab 分配器。每个都有它的适用场景，你想想看，搞懂了它们，你才算真正摸到了内存管理的门道。

28.1 简单malloc/free：最朴素的分配器

先来个最基础的。我刚开始做嵌入式时，第一个分配器就是照着这个思路写的。它用空闲链表管理内存块，每个块前面加个头信息。

核心思想：把一大块内存切成小块，用链表串起来。分配时遍历链表找合适的块，释放时把块挂回链表。

// 内存块头结构
typedef struct mem_block {
    size_t size;           // 块大小（含头）
    int free;              // 1=空闲，0=已分配
    struct mem_block *next; // 下一个块
} mem_block_t;

#define BLOCK_SIZE sizeof(mem_block_t)
#define MEM_POOL_SIZE 1024 * 10  // 10KB 堆区

static char mem_pool[MEM_POOL_SIZE];
static mem_block_t *free_list = NULL;

// 初始化堆区
void mem_init() {
    free_list = (mem_block_t *)mem_pool;
    free_list->size = MEM_POOL_SIZE - BLOCK_SIZE;
    free_list->free = 1;
    free_list->next = NULL;
}

// 简单malloc
void *my_malloc(size_t size) {
    mem_block_t *curr = free_list;
    mem_block_t *prev = NULL;

    // 对齐到4字节
    size = (size + 3) & ~3;

    while (curr) {
        if (curr->free && curr->size >= size) {
            // 如果剩余空间够大，就分裂
            if (curr->size > size + BLOCK_SIZE + 4) {
                mem_block_t *new_block = (mem_block_t *)((char *)curr + BLOCK_SIZE + size);
                new_block->size = curr->size - size - BLOCK_SIZE;
                new_block->free = 1;
                new_block->next = curr->next;
                curr->size = size;
                curr->next = new_block;
            }
            curr->free = 0;
            return (void *)((char *)curr + BLOCK_SIZE);
        }
        prev = curr;
        curr = curr->next;
    }
    return NULL; // 没找到合适的块
}

// 简单free
void my_free(void *ptr) {
    if (!ptr) return;
    mem_block_t *block = (mem_block_t *)((char *)ptr - BLOCK_SIZE);
    block->free = 1;

    // 合并相邻空闲块（向前合并）
    mem_block_t *curr = free_list;
    while (curr) {
        if (curr->free && curr->next && curr->next->free) {
            curr->size += BLOCK_SIZE + curr->next->size;
            curr->next = curr->next->next;
        }
        curr = curr->next;
    }
}

我的经验：这个分配器在小型 MCU 上跑得挺欢，但碎片化严重。我曾经在一个跑了几天的设备上发现，明明还有 2KB 空闲，却分配不出一个 100 字节的块——全是碎片。所以，它只适合临时用用，或者你知道分配释放模式很规律的情况。

28.2 伙伴系统：解决碎片化的利器

伙伴系统是我个人比较喜欢的一种分配器。它把内存按 2 的幂次分成块，分配和释放都很快，而且碎片化比简单链表好得多。

为什么会这样？因为伙伴系统只合并「伙伴」——也就是大小相同、地址相邻的两个块。这样合并操作简单，而且不会产生小碎片。

#define MIN_BLOCK_SIZE 32   // 最小块 32 字节
#define MAX_ORDER 10        // 最大阶数 2^10 = 1024
#define MEM_SIZE (1 << (MAX_ORDER + 4)) // 16KB

typedef struct buddy_block {
    struct buddy_block *next;
} buddy_block_t;

static buddy_block_t *free_lists[MAX_ORDER + 1];
static char mem_area[MEM_SIZE];

// 初始化伙伴系统
void buddy_init() {
    for (int i = 0; i <= MAX_ORDER; i++) {
        free_lists[i] = NULL;
    }
    // 把整块内存挂到最大阶
    free_lists[MAX_ORDER] = (buddy_block_t *)mem_area;
    free_lists[MAX_ORDER]->next = NULL;
}

// 获取块大小对应的阶数
int get_order(size_t size) {
    int order = 0;
    size_t block_size = MIN_BLOCK_SIZE;
    while (block_size < size) {
        block_size <<= 1;
        order++;
    }
    return order;
}

// 伙伴分配
void *buddy_alloc(size_t size) {
    int order = get_order(size);
    if (order > MAX_ORDER) return NULL;

    // 查找可用块
    int current_order = order;
    while (current_order <= MAX_ORDER && free_lists[current_order] == NULL) {
        current_order++;
    }
    if (current_order > MAX_ORDER) return NULL;

    // 取出块
    buddy_block_t *block = free_lists[current_order];
    free_lists[current_order] = block->next;

    // 分裂直到目标阶数
    while (current_order > order) {
        current_order--;
        size_t block_size = MIN_BLOCK_SIZE << current_order;
        buddy_block_t *buddy = (buddy_block_t *)((char *)block + block_size);
        buddy->next = free_lists[current_order];
        free_lists[current_order] = buddy;
    }

    return (void *)block;
}

// 伙伴释放
void buddy_free(void *ptr, size_t size) {
    int order = get_order(size);
    if (order > MAX_ORDER) return;

    buddy_block_t *block = (buddy_block_t *)ptr;
    size_t block_size = MIN_BLOCK_SIZE << order;

    // 尝试合并伙伴
    while (order < MAX_ORDER) {
        // 计算伙伴地址
        buddy_block_t *buddy = (buddy_block_t *)((uintptr_t)ptr ^ block_size);
        // 检查伙伴是否在空闲链表中（简化版，实际需要更复杂的标记）
        // 这里假设伙伴一定在链表中——实际实现需要位图或标记
        block->next = free_lists[order];
        free_lists[order] = block;
        order++;
        block_size <<= 1;
        // 实际合并需要找到伙伴并移除，这里简化
        break;
    }

    // 挂回链表
    block->next = free_lists[order];
    free_lists[order] = block;
}

注意：上面的伙伴释放代码做了简化。实际项目中，你需要用位图或标记来记录每个块的状态，才能正确判断伙伴是否空闲。我曾经在一个项目中偷懒没做位图，结果合并时把已分配的块也合并了，系统直接崩溃。嗯，从那以后我再也不敢省这一步了。

28.3 Slab分配器：为固定大小对象而生

Slab 分配器是 Linux 内核里用的那一套。它专门对付频繁分配释放固定大小对象的情况——比如 task_struct、inode 这些内核对象。说白了，就是预先准备好一批相同大小的对象，用的时候直接拿，用完放回去。

#define SLAB_OBJ_SIZE 64    // 每个对象 64 字节
#define SLAB_OBJ_NUM  16    // 每个 slab 放 16 个对象
#define SLAB_SIZE (SLAB_OBJ_SIZE * SLAB_OBJ_NUM)

typedef struct slab {
    void *free_list;        // 空闲对象链表
    int free_count;         // 空闲对象数
    struct slab *next;      // 链表指针
    char data[SLAB_SIZE];   // 对象存储区
} slab_t;

static slab_t *slab_head = NULL;

// 初始化 slab
void slab_init() {
    slab_head = (slab_t *)malloc(sizeof(slab_t));
    slab_head->free_count = SLAB_OBJ_NUM;
    slab_head->next = NULL;

    // 构建空闲链表
    char *ptr = slab_head->data;
    void **prev = &slab_head->free_list;
    for (int i = 0; i < SLAB_OBJ_NUM; i++) {
        *prev = (void *)ptr;
        prev = (void **)ptr;
        ptr += SLAB_OBJ_SIZE;
    }
    *prev = NULL;
}

// slab 分配
void *slab_alloc() {
    slab_t *slab = slab_head;
    while (slab) {
        if (slab->free_count > 0) {
            void *obj = slab->free_list;
            slab->free_list = *(void **)obj;
            slab->free_count--;
            return obj;
        }
        slab = slab->next;
    }

    // 没有空闲 slab，创建新的
    slab_t *new_slab = (slab_t *)malloc(sizeof(slab_t));
    new_slab->free_count = SLAB_OBJ_NUM;
    new_slab->next = slab_head;
    slab_head = new_slab;

    // 初始化空闲链表
    char *ptr = new_slab->data;
    void **prev = &new_slab->free_list;
    for (int i = 0; i < SLAB_OBJ_NUM; i++) {
        *prev = (void *)ptr;
        prev = (void **)ptr;
        ptr += SLAB_OBJ_SIZE;
    }
    *prev = NULL;

    // 分配第一个对象
    void *obj = new_slab->free_list;
    new_slab->free_list = *(void **)obj;
    new_slab->free_count--;
    return obj;
}

// slab 释放
void slab_free(void *ptr) {
    // 找到对象所属的 slab（简化版：遍历所有 slab）
    slab_t *slab = slab_head;
    while (slab) {
        if (ptr >= (void *)slab->data && 
            ptr < (void *)(slab->data + SLAB_SIZE)) {
            // 把对象放回空闲链表
            *(void **)ptr = slab->free_list;
            slab->free_list = ptr;
            slab->free_count++;
            return;
        }
        slab = slab->next;
    }
    // 没找到——说明 ptr 不是这个 slab 分配的
    // 实际项目中应该 panic 或记录错误
}

我的习惯：在 RTOS 的任务控制块、信号量、消息队列这些内核对象上，我几乎都用 slab。分配一个任务块只需要几条指令，比通用 malloc 快一个数量级。而且没有碎片——因为所有对象大小一样，释放后直接复用。

28.4 三种分配器对比

特性	简单malloc/free	伙伴系统	Slab分配器
分配速度	O(n)，遍历链表	O(log n)，分裂	O(1)，直接取
释放速度	O(n)，合并	O(log n)，合并	O(1)，放回链表
碎片化	严重	内部碎片（2的幂次对齐）	无碎片（固定大小）
适用场景	小系统、临时使用	通用分配、实时系统	频繁分配固定大小对象
内存利用率	高（但碎片多）	中（内部碎片）	高（无碎片）

28.5 实战建议

我个人在实际项目中，通常这样搭配使用：

启动阶段：用简单 malloc/free 做临时分配，反正这时候系统还没跑起来，碎片不是问题。
运行时：用伙伴系统做通用内存分配，特别是需要分配不同大小内存块的场景。
内核对象：用 slab 分配器管理固定大小的结构体，比如任务块、信号量、缓冲区描述符。

你想想看，这三种分配器各有各的脾气。简单 malloc/free 就像菜市场——什么都有，但乱。伙伴系统像超市——整齐，但包装有点浪费。slab 分配器像工厂流水线——专一，但高效。选哪个，得看你的系统到底要什么。

避坑指南：我曾经在一个项目中只用伙伴系统，结果发现分配 33 字节时，实际占了 64 字节——内部碎片接近 50%。后来我加了个 slab 分配器专门处理小对象，内存利用率从 60% 提升到了 85%。所以，别指望一个分配器解决所有问题。

好了，这一章的内容就到这。三种分配器，从简单到复杂，从通用到专用，你都可以在项目中找到它们的位置。记住，没有银弹——选对工具，比会用工具更重要。

📚 课程目录

第二十八章：内存分配器实现：实现一个简单的malloc/free、伙伴系统、slab分配器

28.1 简单malloc/free：最朴素的分配器

28.2 伙伴系统：解决碎片化的利器

28.3 Slab分配器：为固定大小对象而生

28.4 三种分配器对比

28.5 实战建议