STL源码剖析笔记 - STL的Allocator

C++

目标

配置器的作用是对模板对象进行空间分配和归还

结构

配置器一般分为两级，一级配置器和二级配置器，其中一级配置器直接与操作系统交互，向操作系统申请和归还内存。二级配置器，是在预申请内存小于128K时，从自身维护的内存池中直接分配和归还内存。

一级配置器

class __malloc_alloc_template{
private:
    // 三个函数指针处理内存不足的情况，oom = out of memory
    static void *oom_malloc(size_t);
    static void *oom_realloc(void*, size_t);
    static void (*__malloc_alloc_oom_handler)();
public:
    static void * allocate(size_t n);
    static void deallocate(void *p, size_t);
    static void * reallocate(void *p, size_t , size_t new_sz);
    static void (*  set_malloc_handler(void (*f)()))(); //仿真C++的set_new_handler()
}

oom_malloc和oom_realloc函数只有在allocate和reallocate中调用malloc不成功的时候才调用，两个oom函数中不断地尝试申请和重新申请内存，直到申请成功或者调用malloc_handler或者抛出BAD_ALLOC异常

二级配置器

二级配置器维护一个内存池，并负责内存的分配和回收。并且会将任何小额区块的内存需求上调至8的倍数，并维护16个free-list，每个free-list分别管理$i * 8, i \in [1...16]$bytes的区块，每个free-list是一个链表，该链表的节点结构如下

union obj{
    union obj * free_list_link;
    char client_data[1]; // clients see this
}

为了避免节点中存储额外的指针指向后继的节点，因此节点用的是union，达到一物二用的目的。从第一项看，是指针，第二项看，是数据空间

enum {__ALIGN = 8};
enum {__MAX_BYTES = 128};
enum {__NFREELISTS = __MAX_BYTES / __ALIGN};
class __default_alloc_template{
private:
    static size_t ROUND_UP(size_t bytes){
        return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
    }
private:
    union obj{
        union obj * free_list_link;
        char client_data[1];
    };
    static obj * volatile free_list[__NFREELISTS];
    static size_t FREELIST_INDEX(size_t bytes){
        return (((bytes) + __ALIGN - 1) / __ALIGN - 1);
    }
    static void *refill(size_t n);
    //申请可以包含nobjs个free-list节点的空间，如果不行，那么会尝试降低nobjs的大小
    static char *chunk_alloc(size_t size, int &nobjs); 
    static char *start_free;
    static char *end_free;
    static size_t heap_size;
public:
    static void * allocate(size_t n){...}
    static void dallocate(void *p, size_t n){...}
    static void * reallocate(void *p, size_t old_sz, size_t new_sz);
}

空间申请函数allocate()

static void * allocate(size_t n)
{
    obj * volatile * my_free_list;
    obj * result;
    // 大于128就调用一级配置器
    if(n > (size_t) __MAX_BYTES){
        return (malloc_alloc::allocate(n));
    }
    // 寻找16个free lists中合适的节点
    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;
    if(result == 0){ // 节点不足
        void *r = refill(ROUND_UP(n)); // 上调大小并重新申请节点
        return r;
    }
    *my_free_list = result -> free_list_link; // 调整free-list
    return (result);
}

空间释放函数deallocate()

先判断区块大小，大于128bytes调用第一级配置器，小于128bytes就找出相应的free-list，将区块放回

static void deallocate(void *p, size_t n)
{
    obj *q = (obj*) p;
    obj * volatile * my_free_list;
    if (n > (size_t) __MAX_BYTES) { // 大于__MAX_BYTES是大区块
        malloc_alloc::deallocate(p, n);
        return;
    }
    // 寻找对应的free-list
    my_free_list = free_list + FREELIST_INDEX(n);
    q -> free_list_link = *my_free_list;
    *my_free_list = q;
}

图示

重新填充free lists （refill函数）

free-list中没有可用区块时，就调用refill()给free list重新补充“弹药”，缺省获得20个新节点，万一内存池中空间不足，获得的节点数可能小于20

// 返回一个大小为n的对象，并且为free-list适当增加节点
// 假设n已经上调至8的倍数，n是一个节点的大小
void * __default_alloc_template<>::refill(size_t n)
{
    int nobjs = 20;
    // 调用 chunk_alloc()，尝试取得nobjs个区块作为free list的新节点
    // nobjs是pass by reference，当内存不够时，被调整
    char * chunk = chunk_alloc(n, nobjs);
    obj * volatile * my_free_list;
    obj * result;
    obj * current_obj, * next_obj;
    int i;
    // 如果只获得一个区块，就直接分配给调用者，free list没有新节点
    if (1 == nobjs) return (chunk);
    // 否则调整free list，加入新的节点
    my_free_list = free_list + FREELIST_INDEX(n);
    // 在chunk空间内建立free list
    result = (obj*) chunk; //这一块准备返回给客户端
    // 以下引导free list指向新配置的空间
    *my_free_list = next_obj = (obj*)(chunk + n);
    // 将free list各个节点串起来
    for( i = 1; ; ++i) {  // 从1开始，第0个返回给客户端
        current_obj = next_obj;
        next_obj = (obj *) ((char*) next_obj + n);
        if(nobjs - 1 == i) {
            current_obj -> free_list_link = 0;
            break;
        }else {
            current_obj -> free_list_link = next_obj;
        }
    }
    return (result);
}

内存池

从内存池中取空间free list使用，上文的chunk_alloc()的工作

char* chunk_alloc(size_t size, int &objs)
{
    char * result;
    size_t total_bytes = size * nobjs;
    size_t bytes_left = end_free - start_free;
    if(bytes_left > total_bytes){ //剩余内存完全满足需求量
        result = start_free;
        start_free += total_bytes;
        return(result);
    }else if(bytes_left >= size){ // 
        nobjs = bytes_left / size;
        total_bytes = size * nobjs;
        result = start_free;
        start_free += total_bytes;
        return (result);
    }else{
        // 
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        // 
        if(bytes_left > 0) {
            obj * volatile * 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);
        if(0 == start_free){
            int i;
            obj * volatile * my_free_list, *p;
            for(i = size; i <= __MAX_BYTES; i += __ALIGN) {
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if (0 != p)
                {
                    *my_free_list = p -> free_list_link;
                    start_free = (char*) p;
                    end_free = start_free + i;
                    return(chunk_alloc(size, alloc));
                }
            }
            end_free = 0; //
            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));
    }
}

chunk_alloc()中以end_free - start_free判断内存池中的水量。如果
1. 水量充足，直接调出20个区块返回给free list。
2. 如果不足以20个区块，但足够一个以上的区块，就拨出这不足20个区块的空间出去，并修改pass by reference的nobjs为实际能够供应的区块数。
3. 一个区块都没法供应，那么就需要用malloc()从heap中配置内存，为内存池中注入活水源头，新水量的大小为需求量的两倍，再加上一个随着配置次数增加而越来越大的附加量。
4. 万一山穷水尽，整个系统的heap空间都不够了，malloc()失败，chunk_alloc()就试着寻找没有被用到，并且更大的区块，找到一块就挖出，找不到就调用第一级配置器。第一级配置器使用malloc()配置内存，依赖它的out-of-memory处理机制，有机会释放其他的内存拿来使用，如果可以，就成功，否则，最后发出BAD_ALLOC异常。

两级配置的优点

可以避免内存碎片和抖动