源码剖析：STL中空间配置器(allocator)

前言

针对阅读STL源码而言，或许许多人觉得阅读侯捷所著的《STL源码剖析》是过时的，但是我并不觉得，因为这些人往往是阅读过该书，学的更深入才对这本书进行这样的评价，针对入门的为而言，有一本书能带你大致了解STL源码的框架，这是极为便利的。针对最新版本的源码而言，这本书的确是过时的，但是并不影响我们去了解STL源码的框架，去熟悉源码的语法。我觉得一本好书不在于所有人的评价，只要它是让人学习的过程中首先了解到的便是好书。

了解配置器前应该知道

实现相关配置器的头文件：

1.cstddef：该头文件包含了与大小有关的类型和宏

2.cstdlib：该头文件包含通用工具的函数，如free()，malloc()和exit()等函数

3.climits：包含基本整数类型的最大值和最小值

实现相关配置器的类型：

4.ptrdiff_t：用于安全的存储两个指针之间的差值，使代码更好的实现跨平台特性

实现相关配置器的函数：

5.set_new_handler()：该函数用于设置处理当程序申请内存失败时执行的函数，为0则代表调用默认的std::terminate()函数

6.volatile：用于指示变量的值可能会在程序的控制之外被改变

原地构造New

关于原地构造new函数，参见以下源码。其中：

1.size_t：存在头文件cstddef中，而size_t是一个无符号整数类型，用于表示大小、长度或计数

2.::operator new()：该语句代表使用全局的new函数

3.(T*)(::operator new(size_t)(szie * sizeof(T)))：该语句表示使用全局的new()函数来分配了size个类型为T的对象所需的内存，并将其强转换为T*类型

cpp

#include <cstddef>template<calss T>        //模板函数inline T* fun(int vlaue,T*){    T* pointer = (T*)(::operator new((size_t)(size * sizeof(T))));    //原地构造new函数}

不太看得懂语法？没关系，接下将通俗易懂的讲解原地构造new:

cpp

#include <new>     //引入new头文件char* buffer = new char[sizeof(MyClass)];      //使用new相内存申请一个大小为MyClass类的内存MyClass* pointer = new (buffer) MyClass();     //定义一个MyClass指针pointer//使用原地构造new，将对象的存储地址置为buffer上poiter->~MyClass();   //需要手动调用析构函数，析构MyClass类中的属性delete[] buffer;      //调用delete []释放内存

配置器区别

在SGI标准下的配置器（后续对STL源码的刨析也将针对于SGI标准下的源码。SGI标准：关于STL分为三个标准，SGI，PJ和PW标准，其中SGI标准因高度优化和良好的性能而闻名，并且源码开源，可读性高）的作用主要是内存的分配和释放，在该标准下配置器分为一级配置器和二级配置器：

1.一级配置器：处理大于某一个阈值(通常为128字节)的大块内存分配

2.二级配置器：采用内存池的技术，处理小于或等于阈值的小块内存分配

一级配置器详解

关于一级配置器，其中分配内存的allocate()函数和deallocate()函数将直接调用malloc()函数和free()函数，针对内存不足无法分配内存空间的情况将调用set_new_handler()函数处理，以下我们将对其源码解析刨析：

1.分配内存源码：

cpp

static void* allocate(size_t n){    void* result = malloc(n);    //一级配置器直接使用malloc分配内存    if(0 == result) result = oom_malloc(n);    //使用0 == result方式判断可以防止少些一个等于号，使其误写为赋值操作    return result} template<int inst>    //模板特化void* _malloc_alloc_template<inst>::oom_malloc(siez_t n){    void (* my_malloc_handler)();    //函数指针，指向内存分配失败处理函数    void* result;    for(;;){    //死循环，直到分配好内存        my_malloc_handler = _malloc_alloc_oom_handler;        if(0 == my_malloc_handler){ _THROW_BAD_ALLOC; }        //抛出std::bad_alloc异常，表示无法处理内存分配失败的情况        (*my_malloc_handler)();        result  = realloc(p,n);        if(result) return(result);    }}

2.内存释放源码：

cpp

static void deallocate(void* p, size_t /* n */){    free(n);    //一级配置器直接使用free()函数释放内存}

3.内存重新分配源码：

cpp

static void* reallpcate(void* p, size_t /* old_sz */,size_t new_sz){    //old_sz代表旧的内存，但是此处并没有使用参数old_sz    void* result = realloc(p, new_sz);    //当内存不能一次性分配完成时，使用oom_realloc函数分配    if (0 == result) result = oom_realloc(p, new_sz);    return result;}templae<int inst>    //模板特化void* _malloc_alloc_template<inst>::oom_realloc(void* p, size_t n){    void (* my_malloc_handler) ();    void* result;    for(;;){    //不断释放内存，再不断配置内存，直到分配至合适的大小        my_malloc_handler = _malloc_alloc_oom_handler;        if(0 == my_malloc_handler) { _THROW_BAD_ALLOC; }        (*my_malloc_hanlder) ();        result = realloc(p,n);    //配置内存        if(result) return(result);        }}

关于一级配置器，我引用原文的一段话来进行总结：SGI的一级配置器的allocate()和realloc()函数都是在调用malloc()和remalloc()函数不成功后，改调用oom_malloc()和oom_realloc()。后两者存在内循环，不断调用“内存处理不足例程”，期望在某次调用之后，获得足够的内存而圆满完成任务。但如果“内存处理不足例程”并没有被设定函数，则调用_THROW_BAD_ALLOC，抛出bad_alloc异常，或者利于exit(1)来终止程序

二级配置器详解

关于二级配置器，如果进程申请的空间超过128bytes时，就移交第一级配置器处理(使用malloc()和free()管理内存)。当申请的空间小于或等于128bytes时，则以内存池的方式进行管理。在以内存池的方式进行管理中，为了方便管理内存以及为了使用较少的管理指针管理大片空间的目的，SGI的二级配置器会主动将任何较小的区块的内存需求量调整至8的倍数(申请1bytes的空间，调整至申请8bytes，申请10bytes的空间调整至申请16bytes)，当申请内存或释放内存时，二级配置器将会维护其中的free-listes链表，下图将对二级配置器中的链表构造进行讲解：

图1.二级配置器free-listes链表构造图

1.union obj结构代码：

cpp

union obj{	union obj* free_list_link;    //指向下一个union对象的地址	char client_data[1];          //指向一片与所对应的块相同大小的地址};

2.必要的属性或成员代码：

cpp

enum {_ALIGN = 8};                     //最小区块的大小enum {_MAX_BYTES = 128};               //最大区块的大小enum {_NFREELISTS = _MAX_BYTES/_ALIGN};//链表的个数(区块的个数)static obj * volatile free_list[_NFREELISTS];    //区块下标，用于管理区块static size_t ROUND_UP(size_t bytes){    //将申请的内存上调至8的倍数    return (((bytes + _ALIGN - 1) & ~(_ALIGN - 1)));}static size_t FREELIST_INDEX(size_t bytes){    //计算申请的空间应该向哪个区块申请分配空间    return (((bytes) + _ALIGN - 1 ) / _ALIGN - 1);}

3.分配内存源码：

cpp

static void* allocate(size_t n){    obj* volatile * my_free_list;    /*第一个星号表示volatile修饰的是指针      第二个星号表示这是一个指向指针的指针*/      obj* result;    //指向分配的地址    if(n > (size_t)_MAX_BYTES){    //当申请的内存大于Bytes时，使用一级配置器        return (malloc_alloc::allocate(n));    }        //寻找16个区块中合适的区块分配内存    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;    return (result)}

4.内存释放源码：

cpp

static void deallocate(void* p, size_t n){    //p代表释放的空间地址，n代表区块    obj* q = (obj*)p;        obj * volatile * my_free_list;        if(n > (size_t) _MAX_BYTES){    //当释放的内存大于128bytes时使用一级配置器        malloc_alloc::deallocate(p,n);        return;    }    //调整内存池    my_free_list = free_list + FREELIST_INDEX(n);    q->free_list_link = *my_free_list;    *my_free_list = q;}

5.填充free-list源码：

cpp

template <bool threads,int inst>void* _default_alloc_template<threads,inst>::refill(size_t n){    int nobjs = 20;    //向内存池获取的区块个数    char* chunk = chunk_alloc(n,nobjs);    //该函数用于向内存池申请空间，本文不对内存池讲述    obj * volatile * my_free_list;    obj* result;     //申请空间的头指针    obj* next_obj;   //申请空间的尾指针    obj* current_obj;//过渡指针(临时存放尾指针)    int i;        //获得区块个数为1则直接分配给调用者，free-list不新增节点    if(1 == nobjs) return(chunk);        //调整free-list，加入节点    my_free_list = free_list + FREELIST_INDEX(n);    //把向内存池申请空间接入free-list    *my_free_list = next_obj = (obj*)(chunk + n);    //将内存池申请到的空间链接成链表    for(i = 1; ; i++){        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);}

PS：由于二级配置器是向内存池申请空间，所以原文还对内存池进行了大概讲解，但是我觉得一个结点可能讲不完内存池，所以后续将对内存池单独出一篇文章进行讲解

C++ new handler机制

C++ new handler机制：可以要求系统在内存配置需求无法被满足的时候，调用你指定的函数。也就是说当::operator new无法完成内存分配任务时，在抛出std::bad_alloc异常状态之前，会先调用你指定的处理例程(即你指定的函数)

内存基本处理函数

在STL中定义有五个全局函数作用于未初始化的空间上，其中含有用于构造的construct()函数，用于析构的destroy()函数，用于复制构造的uninitialized_copy()函数，用于填充操作的uninitialized_fill()函数和uninitialized_fill_n()函数，本小节将通过函数源码对其进行讲解

1.construct()函数构图及源码：

图2.construct()构图

cpp

template <class T1, class T2>inline void construct(T1* p, const T2& value){    new (p) T1(value);       //原地构造New}

2.destroy()函数构图及源码：

图3.destroy()构图

cpp

//第一个版本，接受一个指针template <class T>inline void destory(T* pointer){    pointer->~T();}//第二个版本，接受了个迭代器， 根据元素的类型进行删除template <class ForwardIterator, class T>inline void destory(ForwardIterator first, ForwardIterator last, T*){    _destory_aux(first, last, value_type(first));}//第三个版本，数值类型有非虚的析构函数template<class ForwardIterator>inline void _destroy_aux(ForwardIterator first, ForwardIterator last, __false_type){    for(; first<last; ++first)        destroy(&*first);}//第四个版本，数值类型有虚析构函数template<class ForwardIterator>inline void _destroy_aux(ForwardIterator first, ForwardIterator last, __true_type){    //针对迭代器为char*和wchar*的特化版    inline void destroy(char*, char*){}    inline void destroy(wchar_t*, wchar_t*){}}//第五个版本，数值类型是否有虚析构函数template <class ForwardIterator, class T>inline void _destory(ForwardIterator first, ForwardIterator last, T*){    typedef typename _type_traits<T>::has_trivial_destructor trivial_destructor;    _destory_aux(first, last, trivial_destructor());    //trivial_destructor()函数用于判断类型是否具有编译器默认的析构函数}

3.uninitialized_copy()函数构图及源码：

图4.uninitialized_copy()构图

cpp

//以下函数中，first代表输入端起始位置，last代表输入端结束位置，result代表输出端起始位置template<class InputIterator,class ForwardIterator>inline ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result) {    return _uninitialized_copy(first,last,result,value_type(result));}template<class InputIterator,class ForwardIterator,class T>inline ForwardIterator _uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result, T*) {    typedef typename _type_traits<T>::is_POD_type is_POD;    return _uninitialized_copy_aux(first,last,result,is_POD());    //is_POD()函数用于判断类型是否属于POD类型    //POD类型：拥有默认构造，析构，拷贝构造，赋值运算符的类型}//以下泛化函数针对POD型别template<class InputIterator,class ForwardIterator>inline ForwardIterator _uninitialized_copy_aux(InputIterator first, InputIterator last, ForwardIterator result, _true_type) {    return copy(first,last,result);    //调用STL算法copy()}template<class InputIterator,class ForwardIterator>ForwardIterator _uninitialized_copy_aux(InputIterator first, InputIterator last, ForwardIterator result, _false_type) {    ForwardIterator cur = result;    for(;first != last;++first,++cur){        construct(&*cur,*first);    }    return cur;}//以下特化函数针对char和wchar类型inline char* uninitialized_copy(const char* first,const char* last,char* result){    memmove(result,first,last - first);    //直接移动内存内容    return result + (last - first);}inline wchar* uninitialized_copy(const wchar* first,const wchar* last,wchar* result){    memmove(result,first,sizeof(wchar_t) * (last - first));    //直接移动内存内容    return result + (last - first);}

4.uninitialized_fill()函数构图及源码：

图5.uninitialized_fill()构图

cpp

//以下函数中，first代表输入端起始位置，last代表输入端结束位置，x代表初值template<class ForwardInterator,class T>inline void uninitialized_fill(ForwardInterator first, ForwardInterator last, const T& x) {	_uninitialized_fill(first,lase,x,value_type(first));}//以下泛化函数针对POD型别template<class ForwardInterator,class T,class T1>inline void uninitialized_fill(ForwardInterator first, ForwardInterator last, const T& x,T1*) {    typedef typename _type_traits<T1>::is_POD_type is_POD;	_uninitialized_fill_aux(first,lase,x,is_POD());}//是POD型别template<class ForwardInterator,class T>inline void uninitialized_fill_aux(ForwardInterator first, ForwardInterator last, const T& x,_true_type) {    fill(first,last,x);    //调用STL算法fill()}//不是POD型别template<class ForwardInterator,class T>inline void uninitialized_fill_aux(ForwardInterator first, ForwardInterator last, const T& x,_false_type) {    ForwardInterator cut = first;    for(;cur != last;++cur){        construct(&*cur,x);    }}

5.uninitialized_fill_n()函数构图及源码：

图6.uninitialized_fill_n()构图

cpp

//以下函数中，first代表输入端起始位置，n代表初始化空间大小，x代表初值template<class ForwardInterator,class Size,class T>inline ForwardInterator uninitialized_fill_n(ForwardInterator first, Size n, const T& x) {	return _uninitialized_fill_n(first,n,x,value_type(first));}//以下泛化函数针对POD型别template<class ForwardInterator,class Size,class T,class T1>inline ForwardInterator _uninitialized_fill_n(ForwardInterator first, Size n, const T& x,T1*) {    typedef typename _type_traits<T1>::is_POD_type is_POD;	return _uninitialized_fill_n_aux(first,n,x,is_POD());}//是POD型别template<class ForwardInterator,class Size,class T>inline ForwardInterator uninitialized_fill_n_aux(ForwardInterator first, Size n, const T& x,_true_type) {    return fill_n(first,n,x);}//不是POD型别template<class ForwardInterator,class T>inline ForwardInterator uninitialized_fill_n_aux(ForwardInterator first, Size n, const T& x,_false_type) {    ForwardInterator cut = first;    for(;n > 0; --n, ++cur){        construct(&*cur,x);    }    return cur;}