21、内存池进阶：定长分配器、伙伴算法、slab分配器

内存池这东西，说白了就是提前跟系统申请一大块内存，然后自己慢慢分着用。基础的内存池我讲过，就是一块连续内存，谁要就给谁一块。但实际项目中，这种"一刀切"的方式往往不够用。

我做过一个网络服务器项目，里面要频繁创建和销毁连接对象。每个连接对象大小固定，但数量巨大。用malloc/free？性能扛不住。用基础内存池？碎片问题又让人头疼。后来我用了定长分配器，问题迎刃而解。

今天咱们就聊聊三种进阶的内存管理方案：定长分配器、伙伴算法、slab分配器。这三种各有各的适用场景，搞懂了它们，你的内存管理水平会上一个台阶。

定长分配器：最简单也最实用

定长分配器，顾名思义，就是只分配固定大小的内存块。你想想看，如果所有对象大小都一样，那管理起来多简单？

它的核心思想是这样的：把一大块内存切成若干个大小相同的槽位，每个槽位可以放一个对象。用一个空闲链表把这些槽位串起来，分配时从链表头部取一个，释放时再放回去。

// 定长分配器的核心结构
typedef struct fixed_pool {
    void *memory;           // 内存池起始地址
    size_t block_size;      // 每个块的大小
    size_t block_count;     // 块的数量
    void *free_list;        // 空闲链表头
} fixed_pool_t;

// 初始化定长分配器
fixed_pool_t* fixed_pool_create(size_t block_size, size_t count) {
    fixed_pool_t *pool = malloc(sizeof(fixed_pool_t));
    pool->block_size = block_size;
    pool->block_count = count;
    pool->memory = malloc(block_size * count);
    
    // 构建空闲链表
    pool->free_list = pool->memory;
    char *ptr = (char*)pool->memory;
    for (size_t i = 0; i < count - 1; i++) {
        void **next = (void**)(ptr + i * block_size);
        *next = ptr + (i + 1) * block_size;
    }
    void **last = (void**)(ptr + (count - 1) * block_size);
    *last = NULL;
    
    return pool;
}

// 分配一个块
void* fixed_pool_alloc(fixed_pool_t *pool) {
    if (pool->free_list == NULL) return NULL;
    
    void *block = pool->free_list;
    pool->free_list = *(void**)block;
    return block;
}

// 释放一个块
void fixed_pool_free(fixed_pool_t *pool, void *block) {
    *(void**)block = pool->free_list;
    pool->free_list = block;
}

这段代码看着简单，但效率极高。分配和释放都是O(1)操作，没有内存碎片。我在项目中用这个管理网络连接对象，性能比malloc提升了至少5倍。

伙伴算法：解决大小不一的问题

定长分配器虽然快，但只能处理固定大小的对象。那如果对象大小不一样怎么办？伙伴算法就是用来解决这个问题的。

伙伴算法的核心思想是：把内存按2的幂次方分成块。比如一块1MB的内存，可以分成两个512KB的块，每个512KB又可以分成两个256KB的块，以此类推。分配时，找到大小最合适的块；释放时，如果相邻的块也是空闲的，就合并成更大的块。

// 伙伴算法的简化实现
#define MIN_BLOCK_SIZE 32      // 最小块大小
#define MAX_ORDER 10           // 最大阶数（2^10 = 1024）

typedef struct buddy_block {
    struct buddy_block *next;   // 空闲链表指针
    int order;                  // 阶数
    int free;                   // 是否空闲
} buddy_block_t;

typedef struct buddy_allocator {
    buddy_block_t *free_lists[MAX_ORDER + 1];  // 每阶的空闲链表
    void *memory_start;                         // 内存起始地址
    size_t total_size;                          // 总大小
} buddy_allocator_t;

// 分配内存
void* buddy_alloc(buddy_allocator_t *alloc, size_t size) {
    // 计算需要的阶数
    int order = 0;
    size_t block_size = MIN_BLOCK_SIZE;
    while (block_size < size) {
        order++;
        block_size <<= 1;
    }
    
    // 查找可用的块
    int current_order = order;
    while (current_order <= MAX_ORDER) {
        if (alloc->free_lists[current_order] != NULL) {
            // 找到了，从链表中取出
            buddy_block_t *block = alloc->free_lists[current_order];
            alloc->free_lists[current_order] = block->next;
            block->free = 0;
            
            // 如果当前阶数大于需要的阶数，需要分裂
            while (current_order > order) {
                current_order--;
                // 分裂成两个小块
                buddy_block_t *buddy = (buddy_block_t*)((char*)block + (1 << current_order));
                buddy->order = current_order;
                buddy->free = 1;
                buddy->next = alloc->free_lists[current_order];
                alloc->free_lists[current_order] = buddy;
                
                block->order = current_order;
            }
            
            return (void*)(block + 1);  // 返回数据区
        }
        current_order++;
    }
    
    return NULL;  // 没有足够的内存
}

伙伴算法的好处是外部碎片很少，而且分配和释放的速度也很快。但有个问题：内部碎片。比如你要分配一个33字节的对象，它得给你一个64字节的块，浪费了将近一半的空间。

Slab分配器：Linux内核的智慧

Slab分配器是Linux内核里用的内存管理方案，它结合了定长分配器和伙伴算法的优点。说白了，就是为每种类型的对象维护一个专属的"缓存池"。

Slab分配器的核心思想是这样的：

• 每种对象类型（比如task_struct、inode）都有自己的slab缓存
• 每个slab缓存包含多个slab，每个slab是一块连续内存
• 每个slab被分成若干个对象槽位
• 对象有三种状态：使用中、空闲、未初始化

我画个图帮你理解一下：

Slab分配器最妙的地方在于：它利用了"对象缓存"的概念。当一个对象被释放时，它不会真的被销毁，而是留在slab里，下次分配时直接复用。这就避免了频繁的构造和析构开销。

// Slab分配器的简化实现
#define SLAB_SIZE 4096  // 每个slab的大小

typedef struct slab {
    void *free_list;           // 空闲对象链表
    struct slab *next;         // 下一个slab
    struct slab *prev;         // 上一个slab
    int inuse;                 // 正在使用的对象数
    int total;                 // 总对象数
} slab_t;

typedef struct kmem_cache {
    char name[32];             // 缓存名称
    size_t obj_size;           // 对象大小
    slab_t *slabs_full;        // 全满的slab链表
    slab_t *slabs_partial;     // 部分空闲的slab链表
    slab_t *slabs_free;        // 全空的slab链表
    int gfp_order;             // 伙伴系统的阶数
} kmem_cache_t;

// 从slab缓存中分配对象
void* slab_alloc(kmem_cache_t *cache) {
    slab_t *slab;
    
    // 优先从部分空闲的slab中分配
    if (cache->slabs_partial) {
        slab = cache->slabs_partial;
    } else if (cache->slabs_free) {
        // 没有部分空闲的，从全空的slab中拿一个
        slab = cache->slabs_free;
        // 移到部分空闲链表
        // ... 链表操作省略
    } else {
        // 都没有，需要创建新的slab
        slab = create_new_slab(cache);
        if (!slab) return NULL;
    }
    
    // 从空闲链表中取一个对象
    void *obj = slab->free_list;
    slab->free_list = *(void**)obj;
    slab->inuse++;
    
    // 如果slab满了，移到全满链表
    if (slab->inuse == slab->total) {
        // ... 链表操作省略
    }
    
    return obj;
}

实际项目中的选择

说了这么多，到底该用哪种？我个人的经验是这样的：

• 如果对象大小固定，比如网络连接、线程控制块，直接用定长分配器，简单高效
• 如果对象大小变化范围大，比如文件缓冲区、消息队列，用伙伴算法
• 如果系统中有多种类型的对象，每种类型大小不同但固定，用slab分配器

我记得有一次做嵌入式数据库，里面要管理多种数据结构：索引节点、数据页、日志记录。每种结构大小不同，但各自固定。我用了slab分配器，每种结构一个缓存，性能比原来用malloc提升了将近10倍。

嗯，这三种进阶的内存管理方案就讲到这里。定长分配器适合单一大小对象，伙伴算法适合大小可变场景，slab分配器则是前两者的结合体，适合复杂系统。搞懂了它们，你的内存管理能力绝对能上一个台阶。

公众号:蓝海资料掘金营，微信deep3321