3、固定大小块分配：原理、实现、位图管理、空闲链表

大家好，我是老吴。今天咱们聊聊固定大小块分配。说实话，这是我在RTOS项目里用得最多的内存管理方式，没有之一。为什么？因为它简单、可靠、确定性高。你想想看，在实时系统里，最怕的就是内存分配时间不确定，或者分配着分配着就碎片化了。固定大小块分配，说白了就是把这些烦恼一刀切掉。

3.1 基本原理：为什么是固定大小？

固定大小块分配的核心思想，就是把内存池预先切成若干个大小相等的块。每个块的大小，通常由你系统中最大的那个数据结构决定。比如你的任务控制块是64字节，那就用64字节的块。如果你有不同大小的需求，那就建多个内存池，每个池子管一种大小。

我在项目中遇到过这样一个场景：一个通信协议栈，需要频繁分配和释放各种报文缓冲区。如果用通用malloc，跑个几天内存就碎成渣了。后来我改成固定大小块分配，每个报文类型对应一个内存池，问题直接解决。嗯，这就是固定大小块的魅力——没有碎片，分配和释放的时间都是常数。

3.2 两种管理方式：位图 vs 空闲链表

固定大小块分配，管理空闲块的方式主要有两种：位图管理和空闲链表管理。我个人习惯根据场景选，下面详细说说。

3.2.1 位图管理

位图管理，就是用一串二进制位来标记每个块是否空闲。1表示空闲，0表示已分配。每个位对应一个内存块。

举个例子，假设内存池有32个块，那就需要一个32位的整数作为位图。分配时，从位图中找到第一个为1的位，把它置0，然后返回对应的块地址。释放时，把对应位置1就行。

代码实现大概是这样的：

// 位图管理的内存池结构
typedef struct {
    uint32_t bitmap;        // 32位位图，最多管理32个块
    void *pool_start;       // 内存池起始地址
    size_t block_size;      // 每个块的大小
    size_t total_blocks;    // 总块数
} bitmap_pool_t;

// 分配一个块
void *bitmap_alloc(bitmap_pool_t *pool) {
    // 找到第一个空闲位
    int index = __builtin_ctz(pool->bitmap);
    if (index >= pool->total_blocks) {
        return NULL;  // 没有空闲块
    }
    // 标记为已使用
    pool->bitmap &= ~(1U << index);
    // 计算地址并返回
    return (void *)((uint8_t *)pool->pool_start + index * pool->block_size);
}

// 释放一个块
void bitmap_free(bitmap_pool_t *pool, void *ptr) {
    // 计算块索引
    int index = ((uint8_t *)ptr - (uint8_t *)pool->pool_start) / pool->block_size;
    // 标记为空闲
    pool->bitmap |= (1U << index);
}

3.2.2 空闲链表管理

空闲链表管理，就是把所有空闲块通过链表串起来。每个空闲块的前几个字节存放指向下一个空闲块的指针。分配时从链表头部取一个块，释放时把块插回链表头部。

这种方式的优点是：不限制块数，只要内存够，多少块都行。而且实现起来非常简洁。

// 空闲链表管理的内存池结构
typedef struct free_block {
    struct free_block *next;
} free_block_t;

typedef struct {
    free_block_t *free_list;    // 空闲链表头
    void *pool_start;           // 内存池起始地址
    size_t block_size;          // 每个块的大小
    size_t total_blocks;        // 总块数
} list_pool_t;

// 初始化内存池
void list_pool_init(list_pool_t *pool, void *memory, 
                    size_t block_size, size_t num_blocks) {
    pool->pool_start = memory;
    pool->block_size = block_size;
    pool->total_blocks = num_blocks;
    pool->free_list = (free_block_t *)memory;
    
    // 把所有块串成链表
    free_block_t *current = pool->free_list;
    for (size_t i = 0; i < num_blocks - 1; i++) {
        current->next = (free_block_t *)((uint8_t *)current + block_size);
        current = current->next;
    }
    current->next = NULL;  // 最后一个块指向NULL
}

// 分配一个块
void *list_alloc(list_pool_t *pool) {
    if (pool->free_list == NULL) {
        return NULL;  // 没有空闲块
    }
    free_block_t *block = pool->free_list;
    pool->free_list = block->next;
    return (void *)block;
}

// 释放一个块
void list_free(list_pool_t *pool, void *ptr) {
    free_block_t *block = (free_block_t *)ptr;
    block->next = pool->free_list;
    pool->free_list = block;
}

3.3 位图 vs 空闲链表：怎么选？

这两种方式各有千秋，我整理了一个对比表，方便你根据实际情况选择：

对比维度	位图管理	空闲链表
内存开销	固定（每个块1位）	每个空闲块4/8字节（指针）
分配速度	O(n)最坏（找空闲位）	O(1)常数时间
释放速度	O(1)常数时间	O(1)常数时间
适合场景	块数少（<64），块大小小	块数多，块大小大
实现复杂度	中等（需要位运算）	简单（链表操作）

我个人习惯是：块数少于64个时用位图，多于64个时用空闲链表。为什么是64？因为64位CPU上，一个64位整数就能管理64个块，查找空闲位用一条指令就搞定了，效率极高。

3.4 避坑指南

做固定大小块分配，有几个坑我踩过，分享给你：

• 块大小对齐问题：块大小最好对齐到CPU的字长（4字节或8字节）。我曾经因为没对齐，在ARM Cortex-M4上跑出了奇怪的硬fault，查了半天才发现是地址对齐问题。
• 内存池起始地址对齐：整个内存池的起始地址也要对齐，最好是页对齐（4KB）。这样方便做MMU映射，也方便调试。
• 多线程安全：如果多个任务同时分配释放，记得加锁。我一般用关中断的方式，简单粗暴，实时性好。
• 调试信息：建议在内存池结构里加一个magic number，用来检测内存池是否被意外破坏。这个习惯救过我很多次。

3.5 总结

固定大小块分配，是实时系统内存管理的基石。它用空间换时间，用确定性换碎片。你想想看，在RTOS里，任务控制块、信号量、消息队列、定时器，这些内核对象哪个不是固定大小的？所以很多RTOS内核内部都在用这种分配方式。

位图管理和空闲链表管理，两种方式各有适用场景。我的建议是：先搞清楚你的需求，块数多不多？块大小大不大？实时性要求有多高？然后根据这些参数选。实在拿不准，就用空闲链表，它更通用，实现也更简单。

下一章，咱们聊聊伙伴系统（Buddy System），那是另一种经典的内存管理算法，在Linux内核里用得很多。到时候我会结合一个实际项目案例来讲，敬请期待。