空间配置器

空间配置器

SGI STL 中的 空间配置器（allocator） 是 STL 容器使用内存的核心组件。

在《STL 源码剖析》中，侯捷将其拆解为：

• 一级配置器（__malloc_alloc_template）：大对象，直接调用 malloc/free
• 二级配置器（__default_alloc_template）：小对象，用内存池+free list优化

SGI STL 中默认使用的 allocator 是一种两级配置策略（dual-level memory allocator）：

级别	面向对象大小	采用机制	是否复用内存	特点
一级	> 128 bytes	malloc/new	否	简单稳定，但慢
二级	≤ 128 bytes	内存池 + free list	是	快、节省空间

第一级配置器 —— __malloc_alloc_template

用于处理大对象（>128字节），直接调用 malloc() 和 free()，保证简单、稳定，但不一定快。

// 一级配置器类模板，inst 是模板参数，用于区分不同实例（用于支持多线程等场景）
template<int inst>
class __malloc_alloc_template {
public:
    // 分配 n 字节内存，内部使用 malloc()
    static void* allocate(size_t n);

    // 释放内存，内部使用 free()
    static void deallocate(void* p, size_t n);

    // 重新分配内存块，内部使用 realloc()
    static void* reallocate(void* p, size_t old_sz, size_t new_sz);
};

当 malloc() 返回 nullptr 时，会尝试调用用户自定义的 oom_handler（Out Of Memory 处理器）：

static void (*__malloc_alloc_oom_handler)();

默认是空的，允许用户通过：

__malloc_alloc::set_malloc_handler(my_handler);

来替换 new_handler 逻辑。这个机制类似 set_new_handler()。

第二级配置器 —— __default_alloc_template

用于处理小型内存（≤128字节）分配，避免频繁调用 malloc/free，提升性能和内存利用率。

核心优化策略：

• 内存对齐：统一以 8 字节对齐，支持分配 8、16、24…128 字节块
• 维护 16 条 free list 链表
• 使用 chunk_alloc() 批量向系统申请内存
• 使用 refill() 向空链表填充内存块

类定义简化版

// 二级配置器模板类
// threads: 是否支持多线程，inst：实例编号（支持多版本区分）
template<bool threads, int inst>
class __default_alloc_template {
private:
    // 内存块链表节点结构体（union保证空间利用）
    union obj {
        union obj* free_list_link;  // 指向下一空闲块的指针，形成链表
        char client_data[1];        // 实际存放数据的起始地址（占位用）
    };

    // 16条空闲链表数组，分别管理不同大小的内存块
    static obj* free_list[__NFREELISTS];

    // 内存池管理指针：start_free 和 end_free 指向系统申请的大块内存区间
    static char* start_free;  
    static char* end_free;

    // 记录系统分配给内存池的总字节数
    static size_t heap_size;

    // 辅助函数：将 bytes 向上调整到 8 的倍数对齐
    static size_t ROUND_UP(size_t bytes);

    // 辅助函数：根据字节大小计算对应 free_list 索引
    static size_t FREELIST_INDEX(size_t bytes);

    // 当 free_list 为空时，调用 refill 函数向链表填充指定大小内存块
    static void* refill(size_t n);

    // 向系统批量申请内存块，尝试一次申请 nobjs 个大小为 size 的块
    static char* chunk_alloc(size_t size, int& nobjs);

public:
    // 分配大小为 n 字节的内存块
    static void* allocate(size_t n);

    // 释放大小为 n 字节的内存块，回收到对应的 free_list 链表
    static void deallocate(void* p, size_t n);
};

实现机制：free list + 内存池

SGI STL 中：

// 内存对齐字节数，所有小内存块都按8字节对齐分配
#define __ALIGN 8

// 小内存块的最大尺寸，超过128字节使用一级配置器
#define __MAX_BYTES 128

// 空闲链表数量 = 最大尺寸 / 对齐大小 = 128 / 8 = 16
// 代表有16条链表，每条链表管理一种大小的内存块
#define __NFREELISTS (__MAX_BYTES / __ALIGN)  // 16个free list

• __ALIGN：对内存大小进行向上取整的对齐单位，确保分配的内存块大小是8的倍数，方便CPU访问，提高性能。
• __MAX_BYTES：定义了使用二级配置器管理的小块最大尺寸，超过这个尺寸的内存分配会切换到一级配置器。
• __NFREELISTS：表示二级配置器中维护的空闲链表个数，每条链表管理固定大小的内存块，大小从8字节递增至128字节，每8字节一个档次，共16档。

每个 free_list[i] 存放大小为 8 * (i + 1) 字节的空闲块。

共有 16 条链表，编号从 0 到 15，每条链表对应一种内存块大小：

i (链表编号)	管理的内存块大小（字节）
0	8 字节（8 × (0+1)）
1	16 字节（8 × (1+1)）
2	24 字节
…	…
15	128 字节（8 × (15+1)）

• 许多 STL 容器会频繁地申请/释放小对象（如 vector<int> 里的每个元素）
• 如果每次都 malloc/free，开销大而且容易内存碎片化
• 所以干脆预分配并管理这些固定大小的小内存块
• 每种大小维护一条链表，用来重复利用（这就是所谓的 内存池）

分配流程（allocate）

输入：用户请求 n 字节

1. 如果 n > 128 字节：进入第一级配置器
2. 否则：
   • ROUND_UP：将 n 向上对齐到 8 的倍数
   • 找到对应 free_list[i]
   • 如果链表非空，返回首节点
   • 如果为空：调用 refill(n)，向链表填充默认 20 个小块，返回第一个

示例代码

void* allocate(size_t n) {
    // 如果请求的内存块大于128字节，走一级配置器（直接malloc）
    if (n > __MAX_BYTES) return malloc_alloc::allocate(n);

    // 找到对应的空闲链表索引
    obj** my_free_list = free_list + FREELIST_INDEX(n);

    // 拿到对应大小的空闲链表头结点
    obj* result = *my_free_list;

    // 如果空闲链表为空，就调用 refill 填充它（默认分配20个小块）
    if (result == nullptr)
        return refill(ROUND_UP(n));  // ROUND_UP 是 8字节对齐函数

    // 否则，从链表头取出一个空闲块
    *my_free_list = result->free_list_link;

    // 返回这块内存
    return result;
}

回收流程（deallocate）

• 如果大小 > 128 字节，直接 free；
• 否则，将指针头插回对应的 free_list[i] 中，供下次复用。

// 回收内存函数，将内存块 p 大小为 n 的内存回收到空闲链表
void deallocate(void* p, size_t n) {
    // 如果释放的内存块大于128字节，交由一级配置器处理（直接调用 free）
    if (n > __MAX_BYTES) {
        malloc_alloc::deallocate(p, n);
        return;
    }

    // 否则，先把 void* 指针转换为 obj*，方便操作链表指针
    obj* q = static_cast<obj*>(p);

    // 根据大小 n 找到对应的空闲链表索引
    obj** my_free_list = free_list + FREELIST_INDEX(n);

    // 将当前块插入该空闲链表的头部
    // q->free_list_link 指向链表当前的头节点
    q->free_list_link = *my_free_list;

    // 头节点指针指向 q，完成头插操作
    *my_free_list = q;
}

refill：空链表填充器

默认申请 20 个对象：

// refill：向free_list中填充n字节大小的内存块，默认分配20个
void* refill(size_t n) {
    int nobjs = 20;  // 期望分配的块数，默认20个

    // 从内存池或系统申请一大块内存，尝试分配nobjs个n字节大小的块
    // 这个函数会修改 nobjs，实际分配数量可能小于20
    char* chunk = chunk_alloc(n, nobjs);

    // 如果只分配到了1个块，直接返回这个块给调用者
    if (nobjs == 1) 
        return chunk;

    // 计算对应free_list的索引，找到对应链表头指针
    obj** my_free_list = free_list + FREELIST_INDEX(n);

    // 将chunk的起始地址作为返回的第一个块
    obj* result = (obj*)chunk;

    // 将第二个块开始的地址赋值给free_list链表头
    obj* next = (obj*)(chunk + n);
    *my_free_list = next;

    // 通过循环把剩余的内存块串成链表（从第二块开始）
    obj* cur;
    for (int i = 1;; ++i) {
        cur = next;                  // 当前块
        next = (obj*)((char*)next + n);  // 指向下一个块地址

        if (i == nobjs - 1) {       // 最后一个块的next指针置为空，链表结束
            cur->free_list_link = nullptr;
            break;
        } else {
            // 将当前块的free_list_link指向下一个块
            cur->free_list_link = next;
        }
    }

    // 返回第一块给调用者使用，剩余块挂入free_list供后续复用
    return result;
}

• chunk_alloc 尝试批量从大内存池或系统申请足够多的小块；
• refill 只返回第一个块给调用者，其余块组成链表挂载到对应 free_list；
• 这样做提高了分配效率，减少了对系统的频繁请求。

chunk_alloc：批量向系统申请内存

// chunk_alloc：从内存池或系统批量分配nobjs个size大小的内存块
char* chunk_alloc(size_t size, int& nobjs) {
    size_t total_bytes = size * nobjs;          // 申请的总字节数
    size_t bytes_left = end_free - start_free;  // 内存池剩余可用字节数

    // 1. 内存池剩余空间足够满足请求
    if (bytes_left >= total_bytes) {
        char* result = start_free;               // 返回起始地址
        start_free += total_bytes;               // 移动内存池起始指针
        return result;
    }
    // 2. 内存池剩余空间不足以满足全部请求，但能分配至少一个块
    else if (bytes_left >= size) {
        nobjs = bytes_left / size;                // 重新计算能分配的块数
        total_bytes = size * nobjs;
        char* result = start_free;
        start_free += total_bytes;
        return result;
    }
    // 3. 内存池剩余空间不足以分配一个完整块
    else {
        // 计算向系统请求的字节数（通常是请求两倍的总大小，加上heap_size的一部分增长量）
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);

        // 如果内存池还有剩余空间，将剩余部分挂回对应的free_list中回收利用
        if (bytes_left > 0) {
            obj** my_free_list = free_list + FREELIST_INDEX(bytes_left);
            ((obj*)start_free)->free_list_link = *my_free_list;
            *my_free_list = (obj*)start_free;
        }

        // 重新向系统申请大块内存
        start_free = (char*)malloc(bytes_to_get);

        // 如果系统申请失败，尝试从较大的free_list中回收内存，防止内存用尽
        if (start_free == nullptr) {
            for (int i = size; i <= __MAX_BYTES; i += __ALIGN) {
                obj** my_free_list = free_list + FREELIST_INDEX(i);
                if (*my_free_list) {
                    // 找到非空的free_list，取一个块用来满足分配请求
                    start_free = (char*)(*my_free_list);
                    *my_free_list = (*my_free_list)->free_list_link;
                    end_free = start_free + i;
                    // 递归调用自己重新尝试分配
                    return chunk_alloc(size, nobjs);
                }
            }

            // 如果都没找到，则调用一级配置器分配内存，可能抛异常或其他处理
            start_free = (char*)malloc_alloc::allocate(bytes_to_get);
        }

        // 记录分配给内存池的总字节数增长
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;

        // 递归调用，尝试再次分配
        return chunk_alloc(size, nobjs);
    }
}

• 内存池剩余空间足够 直接从 start_free 返回申请空间，并移动指针。
• 内存池空间不足，但还能分配部分块 计算能分配的块数 nobjs，返回相应内存。
• 内存池空间不够分配一个完整块
  • 计算新的申请大小（加倍并带增长因子）
  • 将剩余的零散内存挂回对应大小的空闲链表
  • 向系统申请一大块内存（malloc）
  • 若失败，尝试从其他空闲链表中回收内存再分配
  • 若依旧失败，调用一级配置器的分配函数（可能抛异常或退出）
  • 更新内存池指针和大小后，递归尝试分配

STL 中的 allocator 接口封装

最终，STL 封装了一个标准接口 allocator：

template<typename T>
class allocator {
public:
    static T* allocate(size_t n);
    static void deallocate(T* p, size_t n);
};

它的实现最终会使用前面实现的一级/二级配置器，完成真正的内存管理。

内存基本处理工具

uninitialized_copy

将一段已初始化的内存 [first, last) 中的元素复制到另一块未初始化的内存区 [result, result + (last - first))，在目标内存逐个调用元素的拷贝构造函数。

template <class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);

• first, last：已初始化元素区间。
• result：目标未初始化内存起始地址。
• 对于POD类型（Plain Old Data，简单数据类型，如 int、char），直接用 memcpy 或 std::copy 做浅拷贝即可。
• 对于非POD类型，需要逐个调用对象的拷贝构造函数，在未初始化内存上构造元素。

示例（伪代码）

template <typename InputIterator, typename ForwardIterator>
ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result) {
    ForwardIterator cur = result;
    try {
        for (; first != last; ++first, ++cur) {
            // 定位new：在未初始化内存cur上用拷贝构造构造元素
            new ((void*)&*cur) typename std::iterator_traits<ForwardIterator>::value_type(*first);
        }
        return cur;
    } catch (...) {
        // 发生异常时销毁已经构造的元素，防止内存泄漏
        for (; result != cur; ++result) {
            result->~value_type();
        }
        throw;
    }
}

uninitialized_fill

用指定的值 x 对一块未初始化内存 [first, last) 的每个元素进行构造，调用拷贝构造函数。

template <class ForwardIterator, class T>
void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);

• first, last：目标未初始化内存区间。
• x：用于构造每个元素的值。
• POD类型直接用 std::fill 或内存填充优化。
• 非POD类型调用定位 new 对每个元素构造。

示例（伪代码）

template <typename ForwardIterator, typename T>
void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x) {
    ForwardIterator cur = first;
    try {
        for (; cur != last; ++cur) {
            new ((void*)&*cur) typename std::iterator_traits<ForwardIterator>::value_type(x);
        }
    } catch (...) {
        for (; first != cur; ++first) {
            first->~value_type();
        }
        throw;
    }
}

uninitialized_fill_n

对一块未初始化内存起始地址 first，构造 n 个值为 x 的元素。

template <class ForwardIterator, class Size, class T>
ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T& x);

• first：起始未初始化内存地址。
• n：元素数量。
• x：用于构造的值。
• 同样根据类型是否POD，做优化和调用构造。

示例（伪代码）

template <typename ForwardIterator, typename Size, typename T>
ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T& x) {
    ForwardIterator cur = first;
    try {
        for (; n > 0; --n, ++cur) {
            new ((void*)&*cur) typename std::iterator_traits<ForwardIterator>::value_type(x);
        }
        return cur;
    } catch (...) {
        for (; first != cur; ++first) {
            first->~value_type();
        }
        throw;
    }
}

总结

方面	内容
内存分配策略	分级（>128为一级，≤128为二级）
小对象分配	使用 free list 复用小块
系统内存获取	chunk_alloc + malloc
refill	一次分配多个块（默认20）以提升效率
线程支持	可以通过模板参数支持多线程
异常处理	oom_handler 控制内存分配失败后的策略
STL allocator 封装	最终对外接口兼容 STL 要求