空间配置器（allocator）剖析：一级配置器与二级配置器，内存池与自由链表

说到 STL 的空间配置器，我估计不少朋友第一反应就是「哦，那个负责分配内存的东西」。没错，但它远比你想象的复杂。我当年刚接触 STL 源码时，也被这套设计惊艳到了——它居然能同时兼顾效率和内存碎片问题。

说白了，空间配置器就是 STL 容器的「后勤部长」。容器只管往里放元素，至于内存从哪来、怎么管理，全交给 allocator。今天我们就深入扒一扒 SGI STL 的 allocator 实现，看看它到底有多巧妙。

为什么需要两级配置器？

你想想看，如果每次 new 一个对象都去调用 malloc，频繁的小内存分配会导致两个问题：一是性能开销大，二是容易产生内存碎片。我在项目中就遇到过这种情况——一个服务跑了一周后，内存碎片率高达 30%，明明还有空闲内存，却分配不出连续的大块。

所以 SGI STL 的设计者想了个办法：大块内存直接走一级配置器，小块内存走二级配置器。阈值是 128 字节。这个数字不是随便定的，它刚好是大多数 CPU 缓存行大小的两倍，经验证明这个值效果最好。

一级配置器：简单粗暴

一级配置器其实没什么花哨的。它直接调用 malloc，如果失败就调用用户自定义的 out-of-memory handler。我习惯把它看作一个「带重试机制的 malloc 封装」。

// 一级配置器核心逻辑（简化版）
template <int inst>
class __malloc_alloc_template {
private:
    static void* oom_malloc(size_t n) {
        void (*my_malloc_handler)();
        while (true) {
            my_malloc_handler = __malloc_alloc_oom_handler;
            if (my_malloc_handler == 0) throw bad_alloc();
            (*my_malloc_handler)();  // 调用用户设置的 handler
            void* result = malloc(n);
            if (result) return result;
        }
    }
public:
    static void* allocate(size_t n) {
        void* result = malloc(n);
        if (result == 0) result = oom_malloc(n);
        return result;
    }
    static void deallocate(void* p, size_t /*n*/) {
        free(p);
    }
};

嗯，这里要注意：一级配置器的 deallocate 直接调 free，根本不关心你释放的内存大小。为什么？因为大块内存的释放不需要额外管理，交给操作系统就好。

二级配置器：内存池 + 自由链表

这才是重头戏。二级配置器维护一个内存池和 16 条自由链表，每条链表负责一种固定大小的内存块。大小从 8 字节到 128 字节，以 8 字节对齐。

为什么会是 16 条？128 / 8 = 16，刚好覆盖所有小块内存的需求。我刚开始看源码时觉得这个设计太死板了，后来才发现——固定大小分配能彻底避免外部碎片。

// 自由链表节点结构
union obj {
    union obj* free_list_link;  // 指向下一个空闲块
    char client_data[1];        // 用户数据起始地址
};

// 二级配置器核心（简化）
class __default_alloc_template {
private:
    static const size_t ALIGN = 8;
    static const size_t MAX_BYTES = 128;
    static const size_t NFREELISTS = MAX_BYTES / ALIGN;
    
    static obj* volatile free_list[NFREELISTS];
    static char* start_free;   // 内存池起始
    static char* end_free;     // 内存池结束
    static size_t heap_size;   // 已分配总量
    
    // 将 bytes 上调至 8 的倍数
    static size_t ROUND_UP(size_t bytes) {
        return (bytes + ALIGN - 1) & ~(ALIGN - 1);
    }
    
    // 根据大小选择自由链表索引
    static size_t FREELIST_INDEX(size_t bytes) {
        return (bytes + ALIGN - 1) / ALIGN - 1;
    }
};

分配流程：从自由链表到内存池

当容器请求 n 字节时，二级配置器会这样处理：

1. 如果 n > 128，直接转给一级配置器处理
2. 否则，将 n 上调到 8 的倍数，找到对应的自由链表
3. 如果链表不为空，直接取第一个节点返回
4. 如果链表为空，调用 refill() 从内存池批量分配

这个 refill 函数很有意思。它一次分配 20 个块，但只返回第一个给用户，剩下的 19 个挂到自由链表上。为什么是 20？这是经验值——太少会导致频繁 refill，太多会浪费内存。

// 从内存池分配一大块，然后切分成小块
static void* refill(size_t n) {
    size_t nobjs = 20;  // 默认分配 20 个块
    char* chunk = chunk_alloc(n, nobjs);  // 实际可能少于 20
    
    if (nobjs == 1) return chunk;  // 只拿到一个，直接返回
    
    // 将剩余的挂到自由链表
    obj* volatile* my_free_list = free_list + FREELIST_INDEX(n);
    obj* result = (obj*)chunk;
    obj* next_obj;
    obj* current_obj;
    
    *my_free_list = next_obj = (obj*)(chunk + n);
    for (int i = 1; ; ++i) {
        current_obj = next_obj;
        next_obj = (obj*)((char*)next_obj + n);
        if (i == nobjs - 1) {
            current_obj->free_list_link = 0;
            break;
        } else {
            current_obj->free_list_link = next_obj;
        }
    }
    return result;
}

你可能会问：如果内存池也不够用了怎么办？chunk_alloc 会尝试从内存池中取出剩余内存，然后调用 malloc 向系统申请。如果 malloc 也失败，它会去更大的自由链表中「借」内存——这个递归回退机制我特别喜欢，它体现了「不浪费任何可用资源」的设计哲学。

内存池的回收策略

二级配置器的 deallocate 很简单：如果释放的内存大于 128 字节，直接 free；否则，把它插回对应的自由链表头部。

但这里有个坑：自由链表的内存不会归还给操作系统。我当年第一次看到这个设计时觉得不合理，后来才明白——小块内存的频繁分配释放如果每次都跟系统交互，性能损失太大了。而且这些内存最终会被复用，不会真正泄漏。

整体架构一览

下面这张图展示了二级配置器的完整工作流程，我建议你仔细看看：

从这张图可以清楚看到：用户请求先判断大小，大块走一级，小块走二级。二级内部先查自由链表，有就直接取，没有就找内存池批量分配。内存池不够了再向系统申请。整个流程环环相扣，没有一步是多余的。

总结一下

SGI STL 的空间配置器设计，说白了就是「大块直接管，小块池化管」。一级配置器简单可靠，二级配置器高效灵活。两者配合，既避免了频繁系统调用，又控制了内存碎片。

我个人觉得，这套设计最值得学习的地方不是具体代码，而是它的分层思想——根据不同的场景选择不同的策略。你在自己写内存池或者对象池时，也可以借鉴这种思路：先定义好阈值，然后针对不同大小的请求采用不同的管理方式。

嗯，关于空间配置器就聊这么多。记住一句话：理解 allocator，你就理解了 STL 的内存管理哲学。