我们知道，SGI STL的第一级配置器是直接使用malloc()， free(), realloc()并配合类似C++ new-handler机制实现的。第二级配置器的工作机制要根据区块的大小是否大于128bytes来采取不同的策略：
申请的内存是否大于128bytes？
是–>使用第一级配置器–>以malloc(), free(), realloc()等C函数执行操作，并实现类似C++ new-handler的机制
否–>使用memory pool–>???
1.memory pool的工作原理是什么？
我们已经知道了，当区块小于128bytes时，就会以内存池(memory pool)来管理，此法也称为次层配置(sub-allocation)，其工作原理是：
（1）每次配置一大块内存，并维护对应的自由链表(free-list)。下次若再有相同大小的内存需求，就直接从free-list中拨出。
（2）配置器除了负责配置，还负责回收：如果客端释放小额区块，就由配置器回收到free-list中。
（3）SGI第二级配置器会主动将任何小额区块的内存需求量上调到8的倍数（例如客户端申请30bytes，就自动调整为32bytes）。
（4）同时，SGI第二级配置器维护16个free-list，各自管理大小分别为8,16,24…128bytes的小额区块。
2.我们该如何去维护一个自由链表呢？
我们知道，一方面，自由链表中有些区块已经分配给了客端使用，所以free-list不需要再指向它们；另一方面，为了维护free-list，每个节点还需要额外的指针指向下一个节点。
那么问题来了，如果每个节点有两个指针？这不就造成了额外负担吗？本来我们设计STL容器就是用来保存对象的，这倒好，对象还没保存之前，自己已经占据了额外的内存空间了。那么，有方法解决吗？有的!
（1）再这之前我们先来了解另一个概念——union（联合体/共用体），对union已经熟悉的同学可以跳过这一部分的内容：
（a）共用体是一种特殊的类，也是一种构造类型的数据结构。
（b）共用体表示几个变量共用一个内存位置，在不同的时间保存不同的数据类型和不同长度的变量。
（c）所有的共用体成员共用一个空间，并且同一时间只能储存其中一个成员变量的值。例如如下：
|
1 2 3 4 5 6 7 |
union StateMachine { char character; int number; char *str; double exp; }; |
一个union 只配置一个足够大的空间以来容纳最大长度的数据成员，以上例而言，最大长度是double 类型，所以StateMachine 的空间大小就是double 数据类型的大小。在C++里，union 的成员默认属性页为public。union 主要用来压缩空间。如果一些数据不可能在同一时间同时被用到，则可以使用union。
（2）了解了union之后，我们可以借助union的帮助，先来观察一下free-list节点的结构：
|
1 2 3 4 |
union obj { union obj * free_list_link; char client_data[1]; //the clinet sees this. }; |
以及free-list的实现技巧图：
在union obj中，定义了两个字段，再结合上图来分析：
从第一个字段看，obj可以看做一个指针，指向链表中的下一个节点；
从第二个字段看，obj可以也看做一个指针，不过此时是指向实际的内存区。
3.第二级配置器的部分实现内容
到这里，我们已经基本了解了第二级配置器中free-list的工作原理了。最后附上第二级配置器的部分实现内容源码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
enum {__ALIGN = 8}; //小区块的上调边界 enum {__MAX_BYTES = 128;} //小型区块的上限 enum {__NFREELISTS = __MAX_BYTES/____ALIGN}; //free-list个数 //以下是第二级配置器 //注意，无“template类型参数”，且第二参数完全没派上用场 //第一参数用于多线程环境下。这里不讨论多线程环境 template <bool threads, int inst> class __default_alloc_template { private: //ROUND_UP()将bytes上调至8的倍数 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]; }; private: //16个free-lists static obj *volatile free_list [__NFREELISTS]; //以下函数根据区块大小，决定使用第n号free-list.n从0起算 static size_t FREELIST_INDEX(size_t bytes) { return (((bytes) + __ALIGN-1)/__ALIGN-1); } //返回一个大小为n的对象，并可能加入大小为n的其他区块到free list static void *refill(size_t n); //配置一大块空间，可容纳nobjs个大小为“size”的区块 //如果配置nobjs个区块有所不便，nobjs可能会降低 static char *chunk_alloc(size_t size, int &nobjs); //Chunk allocation state static char *start_free; //内存池起始位置。只在chunk_alloc()中变化 static char *end_free; //内存池结束位置。只在chunk_alloc()中变化 static size_t heap_size; public: static void *allocate(size_t n) { /*详述于后*/} static void deallocate(void *p, size_t n) { /*详述于后*/} static void *reallocate(void *p, size_t old_sz, size_t new_sz); }; //以下是static data member的定义与初始值设定 template <bool threads, int inst> char *__default_alloc_template<threads, inst>::start_free = 0; template <bool threads, int inst> char *__default_alloc_template<threads, inst>::end_free = 0; template <bool threads, int inst> size_t __default_alloc_template<threads, inst>::heap_size = 0; template <bool threads, int inst> __default_alloc_template<threads, inst>::obj *volatile __default_alloc_template<threads, inst>::free_list[__NFREELISTS] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; |
4.空间配置函数allocate()
我们知道第二级配置器拥有配置器的标准接口函数allocate()。此函数首先判断区块的大小？
大于128bytes–>调用第一级配置器。
小于128bytes–>就检查对应的free list。（如果没有可用区块，就将区块上调至8倍数的边界，然后调用refill(),为free list重新填充空间。
下面是allocate()代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
//n must be > 0 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 ) { //没有找到可用的free list，准备重新填充free list void *r = refill(ROUND_UP(n)); //下节详述 return r; } //调整free list *my_free_list = result ->free_list_link; return (result); }; |
NOTE：每次都是从对应的free list的头部取出可用的内存块。然后对free list进行调整，使上一步拨出的内存的下一个节点变为头结点。
区块自free list调出的操作，如图所示：
5. 空间释放函数deallocate()
同样，作为第二级配置器拥有配置器标准接口函数deallocate()。该函数首先判断区块大小？
大于128bytes就调用第一级配置器。
小于128bytes就找出对应的free list，将区块回收。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//p不可以是0 static void deallocate(void *p, size_t n) { obj *q = (obj*) p; obj *volatile *my_free_list; //大于128就调用第一级配置器 if (n > (size_t)__MAX_BYTES) { malloc_alloc::deallocate(p,n); return; } //寻找对应的free list my_free_list = free_list +FREELIST_INDEX(n); //调整free list，回收区块 q->free_list_link = *my_free_list; *my_free_list = q; } |
NOTE：通过调整free list链表将区块放入free list的头部。
区块回收纳入free list的操作，如图所示：
6.重新填充free lists
我们知道，（1）当发现free list中没有可用区块时，就会调用refill()为free list重新填充空间；（2）新的空间将取自内存池（经由chunk_alloc()完成）；（3）缺省取得20个新节点（区块），但万一内存池空间不足，获得的节点数可能小于20。
下面是源代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
//返回一个大小为n的对象，并且有时候会为适当的free list增加节点 //假设n已经适当上调至8的倍数 template <bool threads, int inst> void* __default_alloc_template<threads, inst>::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 == nonjs ) 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); } |
6.内存池（memory pool）
唔…从文章开头就提到了memory pool，现在终于轮到这个大boss上场了。
首先，我们要知道从内存池中取空间给free list使用，是chunk_alloc()在工作，它是怎么工作的呢？
我们先来分析chunk_alloc()的工作机制：
chunk_alloc()函数以end_free – start_free来判断内存池的“水量”（哈哈，很形象的比喻）。
（1）当向内存池申请空间时，需要判断该内存池中还有多少“水量”？
（a）水量充足———>直接调出20个区块返回给free list（缺省是20）
（b）1≤水量＜20——>拨出这不足20的区块的空间出去
（c）水量=0———–>调用malloc()从heap中配置内存（新水量的大小为需求量的两倍）
（2）万一连system heap空间都不够了，malloc()注水失败怎么办呢？此时，chunk_alloc()会寻找有无“尚有未用区块，且区块足够大”的free list？
（a）有—–>找到了就挖出一块并交出
（b）无—–>调用第一级配置器
（3）我们知道第一级配置器其实也是使用malloc()来配置内存的，但它有out-of-memory处理机制（类似new handler机制），或许有机会释放其他的内存拿来此处使用。
（4）如果第一级配置器的malloc()也失败了，就发出bad_alloc异常。
说了这么多，我们还是来看看SGI STL中的源码吧：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
//假设size已经适当上调至8的倍数 //注意参数nobjs是pass by reference template <bool threads, int inst> char* __default_alloc_template<threads, inst>:: chunk_alloc(size_t size, int& nobjs) { 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 ) { //内存池还有一些零头，先配给适当的free list //首先寻找适当的free list obj *volatile *my_free_list = free_list +FREELIST_INDEX(bytes_left); //调整free list，将内存池中的残余空间编入 ((obj*)start_free)-> free_list_link = *my_free_list; *my_free_list = (obj*)start_free; } //配置heap空间，用来补充内存池 start_free = (char*)malloc(bytes_to_get); if (0 == start_free) { //heap 空间不足，malloc()失败 int i; obj* volatile * my_free_list, *p; //试着检视我们手上拥有的东西。这不会造成伤害，我们不打算尝试配置 //较小的区块，因为那再多进程机器上容易导致灾难 //以下搜寻适当的free list //所谓适当是指“尚有未用区块，且区块够大”的free list for (i = size; i <= __MAX_BYTES; i += __ALIGN) { my_free_list = free_list + FREELIST_INDEX(i); p = *my_free_list; if (0 != p) { //free list内尚有未用区块 //调整free list以释出未用区块 *my_free_list = p->free_list_link; start_free = (char*)p; end_free = start_free + i; //递归调用自己，为了修正nobjs return (chunk_alloc(size, nobjs)); //注意，任何残余零头终将被编入释放的free list中备用 } } end_free = 0; //如果出现意外（山穷水尽，到处都没内存可用了） //调用第一级配置器，看看out-of-memory机制能够尽点力 start_free = (char*)malloc_alloc::allocate(bytes_to_get); //这会导致抛出异常，或内存不足的情况获得改善 } heap_size += bytes_to_get; end_free = start_free + bytes_to_get; //递归调用自己，为了修正nobjs return (chunk_alloc(size, nobjs)); } } |
下图显示内存池实际操作结果：
小结：
SGI STL的一级、二级空间配置器的内容就结束了。回想一下前面提到的那个提供配置器标准接口的simple_alloc，SGI容器通常以这种方式来使用配置器：
|
1 2 3 4 5 6 7 8 9 10 |
template <class T, class Alloc=alloc> //缺省使用alloc为配置器 class vector { public: typedef T value_type; ... protected: //专属之空间配置器，每次配置一个元素大小 typedef simple_alloc<value_type, Alloc> data_allocator; ... }; |
其中第二个template参数所接受的缺省参数alloc，可以是第一级配置器，也可以是第二级配置器。不过，SGI STL已经把它设为第二级配置器。
参考：STL源码剖析