STL源码剖析-空间配置器
STL源码剖析--空间配置器
STL的设计非常巧妙，组件间互取短长，形成了一个世界，这是这个世界里的组件：
1. containers（容器）：所谓容器，是指存放数据的地方，将数据以一定的方法组织存放。根据不同的组织方式，可以把容器分为顺序容器，如vector、deque、list，关联容器，如set、map。Container是一种class template。
2. algorithm（算法）：各种常用不常用的算法如sort、copy、search等等。algorithm是一种function template。
3. iterator（迭代器）：迭代器是算法和容器之前的胶合剂，算法作用于容器之上，但算法以迭代器作为形参。从实现上看，迭代器是一种将operator*，operator++，operator--，operator->等指针相关操作予以重载的class template。所以容器都带有自己的迭代器，因为只有容器设计者才知道如何遍历自己的元素。
4. functors（仿函数）：行为类似函数，可作为算法的某种策略。从实现的角度来看，仿函数是一种重载了operator()的class或class template，它常常是算法的一个输入，类似于一种策略。
5. adapters（适配器）：用来形容容器、迭代器或仿函数接口的东西，有时候上面那些组件的行为可能跟我们想要的约束不大一样，于是给它们包装一下，使它们遵守一定的行为。
6. allocator（配置器）：负责空间配置与管理。从实现的角度来看，配置器是一种实现了动态空间配置、管理、空间释放的class template。
STL中的空间配置器，使用了两层架构，一层用于分类大块内存，一层用于管理小块内存。大块内存基本上是用完了就返回给操作系统，而小块内存则由内存池管理。另外，我们知道当我们new一个对象的时候，不仅仅是给了它内存，同时还可能调用了构造函数对这块内存进行了初始化（假如它是用户自定义类型），当我们delete一个对象的时候，同样，也可能是先调用了析构函数，然后再把内存还回去。调用构造、析构函数是要付出代价的，可是对于基本类型如int、long这种Plain-Old-Data，根本就不存在这样的构造/析构函数，便没有必要为它花费这种心思了。因此，为了便于分开处理这两种情况，STL把new/delete的执行过程分开成了两部分，一部分放在<stl_construct>里，用于在必要的时候调用构造、析构函数，一部分放在<stl_alloc>里，用于策略性地分配内存，跟内存分配管理相关的，还有一个<stl_uninitialized>，针对多个对象的初始化、复制做了一定的优化（当然也是以是否为POD来区分）。
<stl_construct>里定义了一个construct和两个destroy，construct基本上就是一个placement new，在指定内存上调用构造函数，而destroy有两个版本，一个是只析构单独一个对象的，直接调用了对应的~T()版本，另一个版本用于析构一段范围内的对象，这样的话如果对象是POD类型的，还for[i,j)地去执行，就是一种无谓的浪费了，因此，这个destroy将根据数据类型，决定调用特定版本的__destroy，如果是POD类型，则什么都不做，如果不是POD类型，则for[i,j)地去调用~T()。这些类型判断都是在编译时就确定的（通过__type_traits<T>::has_trivial_destructor），因此并不影响运行时效率。另外你肯定会想，为什么针对destroy这番考虑，针对construct却没有呢？反正当时我就是这么想的，后来发现原来这些事情交给uninitialized_fill、uninitialized_copy和unintialized_fill_n去做了，因为对象的初始化可能是经由constructor，也可能是经由copy constructor去执行呀。这里面，**_copy可能在必要的时候直接使用memmove来执行。
每次配置器需要向系统要内存的时候，都不是按客户需求向系统申请的，而是一次性向系统要了比需求更多的内存，放在内存池里，有一个free_start和free_end指示剩余的空间（也就是说内存池剩余的空间都是连续的，因此每次重新向system heap要空间的时候，都会把原先内存池里没用完的空间分配给合适的free list。）当free-list中没有可用区块了的时候，会首先从内存池里要内存，同样，也不是以按客户需求要多少块的，而是一次可能会要上20块，如果内存池内空间允许的话，可能会得到20个特定大小的内存，如果内存池给不了那么多，那么就只好尽力给出；如果连一个都给不出，那么就要开始向系统即system heap要空间了。换算的标准是bytes_to_get=2*total_bytes+ROUND_UP(heap_size>>4)。这个时候使用的是malloc，如果没成功，就尝试着从大块一点的freelist那里要一个来还给内存池，如果还是不行，那么会调用第一级空间配置器的malloc::allocate，看看out-of-memory机制能做点什么不。
总结起来整个过程大概是这样的，假设我们向系统要x大小的内存，
（1）x大于128byte，用第一级配置器直接向系统malloc，至于不成功的处理，过程仿照new，通过set_new_handler来处理，直到成功返回相应大小的内存或者是抛出异常或者是干脆结束运行；
（2）x小于128byte，用第二级配置器向内存池相应的free_list要内存，如果该freelist上面没有空闲块了，
（2.1）从内存池里面要内存，差不多要的是<=20个相应freelist大小的块，如果要不到：
（2.2）从系统的heap里面要内存给到内存池，换算的标准是bytes_to_get=2*total_bytes+ROUND_UP(heap_size>>4)，这时使用的是系统的malloc，如果要不到：
（2.3）从比较大的freelist那里要内存到内存池，如果还是要不到：
（2.4）从系统的heap里面要内存给到内存池，换算标准跟2.2一样，但是这时候使用的是第一级配置器的allocate，主要是看看能不能通过out_of_memory机制得到一点内存。所以，freelist总是从内存池里要内存的，而内存池可能从freelist也可能从系统heap那里要内存。
sgi stl的alloc的主要开销就在于管理这些小内存，管理这些小内存的主要开销就在于，每次freelist上的内存块用完了，需要重新要空间，然后建立起这个list来。freelist上的内存，会一直保留着直到程序退出才还给系统。但这不会产生内存泄漏，一来是管理的都是小内存，二来是，占用的内存只会是整个程序运行过程中小内存占用量最大的那一刻所占用的内存。
SGI STL的alloc是一种内存管理机制，用于管理小内存块的分配，以减少内存碎片。后来我又看了另外一些内存管理机制（利用对象管理资源），包括智能指针的RAII，用于复杂但可能过程不是很久的算法内存管理AutoFreeAlloc，ScopeAlloc，以及boost中的pool跟object_pool。总的来说，内存管理的基本要求就是：不重不漏，既不重复delete，也不漏掉delete。
首先是智能指针，智能指针的基本思想是利用编译器在对象离开作用范围后自动调用析构函数来实现内存的自动释放，即通过对象来管理资源，把指针封装成一个对象，在其构造、析构、赋值函数中，实现对内存的管理。最简单的是auto_ptr，你把指针给了它，它就在析构的时候把指针指向的内存释放掉。可是我要把指针赋值给其他人怎么办？它说，哦，那没办法，被赋值的那个人接管了你的内存，你就退休指向NULL吧。这显然给指针的应用带来了相当大的不便，想想，在用裸指针时，用temp = head, head = head->next这样的状况是多么常见，用容器存放指针也是常有的事（存放到容器是一种赋值行为）。那就使用share_ptr吧。share_ptr中记录了一块内存的reference_count，在构造时其为一，在复制构造、赋值时修改reference_count，在析构时reference_count--，如果reference_count为0，那么就把内存给释放了。在多线程中，reference_count便成了一个竞争资源，因此可能会成为瓶颈。另外，所谓的这个“把内存给释放了”，其实也可能只是一种指定的操作，例如把它放到freelist去啊之类的，是可以自定义的。
上面的那个malloc_alloc就是第一级allocator, 是针对较大内存分配时才使用的，所以对于在第二级自身malloc的内存，这个函数只是简单的把那块内存返还到了指定大小的链表中而已。
我感觉虽然不该在这里释放，但也总要释放的吧？是我看漏了哪里吗？难道sgi stl的实现中有另一个函数来做这种工作？
如果没有的话，针对这种情形应该如何释放呢？
所有的链表中的内存块都不是独立malloc的，而是一次malloc中的一部分，而且一次malloc的内存很可能分散在多组链表里，我现在想的，是用一个数据结构把每次malloc的内存块的指针保存下来，在最后的最后全部free掉，但是这样又比较危险，如果有对象正在使用这块内存。
是否是这种设计本身决定了不能随便释放内存呢，有没有其他方法可以比较灵活的紧缩/释放allocator占用的内存呢？
STL的设计非常巧妙，组件间互取短长，形成了一个世界，这是这个世界里的组件：
1. containers（容器）：所谓容器，是指存放数据的地方，将数据以一定的方法组织存放。根据不同的组织方式，可以把容器分为顺序容器，如vector、deque、list，关联容器，如set、map。Container是一种class template。
2. algorithm（算法）：各种常用不常用的算法如sort、copy、search等等。algorithm是一种function template。
3. iterator（迭代器）：迭代器是算法和容器之前的胶合剂，算法作用于容器之上，但算法以迭代器作为形参。从实现上看，迭代器是一种将operator*，operator++，operator--，operator->等指针相关操作予以重载的class template。所以容器都带有自己的迭代器，因为只有容器设计者才知道如何遍历自己的元素。
4. functors（仿函数）：行为类似函数，可作为算法的某种策略。从实现的角度来看，仿函数是一种重载了operator()的class或class template，它常常是算法的一个输入，类似于一种策略。
5. adapters（适配器）：用来形容容器、迭代器或仿函数接口的东西，有时候上面那些组件的行为可能跟我们想要的约束不大一样，于是给它们包装一下，使它们遵守一定的行为。
6. allocator（配置器）：负责空间配置与管理。从实现的角度来看，配置器是一种实现了动态空间配置、管理、空间释放的class template。
STL中的空间配置器，使用了两层架构，一层用于分类大块内存，一层用于管理小块内存。大块内存基本上是用完了就返回给操作系统，而小块内存则由内存池管理。另外，我们知道当我们new一个对象的时候，不仅仅是给了它内存，同时还可能调用了构造函数对这块内存进行了初始化（假如它是用户自定义类型），当我们delete一个对象的时候，同样，也可能是先调用了析构函数，然后再把内存还回去。调用构造、析构函数是要付出代价的，可是对于基本类型如int、long这种Plain-Old-Data，根本就不存在这样的构造/析构函数，便没有必要为它花费这种心思了。因此，为了便于分开处理这两种情况，STL把new/delete的执行过程分开成了两部分，一部分放在<stl_construct>里，用于在必要的时候调用构造、析构函数，一部分放在<stl_alloc>里，用于策略性地分配内存，跟内存分配管理相关的，还有一个<stl_uninitialized>，针对多个对象的初始化、复制做了一定的优化（当然也是以是否为POD来区分）。
<stl_construct>里定义了一个construct和两个destroy，construct基本上就是一个placement new，在指定内存上调用构造函数，而destroy有两个版本，一个是只析构单独一个对象的，直接调用了对应的~T()版本，另一个版本用于析构一段范围内的对象，这样的话如果对象是POD类型的，还for[i,j)地去执行，就是一种无谓的浪费了，因此，这个destroy将根据数据类型，决定调用特定版本的__destroy，如果是POD类型，则什么都不做，如果不是POD类型，则for[i,j)地去调用~T()。这些类型判断都是在编译时就确定的（通过__type_traits<T>::has_trivial_destructor），因此并不影响运行时效率。另外你肯定会想，为什么针对destroy这番考虑，针对construct却没有呢？反正当时我就是这么想的，后来发现原来这些事情交给uninitialized_fill、uninitialized_copy和unintialized_fill_n去做了，因为对象的初始化可能是经由constructor，也可能是经由copy constructor去执行呀。这里面，**_copy可能在必要的时候直接使用memmove来执行。
然后就是那个大头，空间分配器了。<stl_alloc.h>内定义了两个template，一个是__malloc_alloc_template，这是sgi stl的一级配置器，它的allocate()直接使用malloc()而deallocate()直接使用free()，同时，它模拟C++的set_new_handler()处理内存不足的状况。第二个是__default_alloc_template，它维护了16个free list，每个list上集合着大小分别为8，16，24，...128大小的内存块。内存池以malloc()配置而得，如果内存不足，转调用第一级配置器，因为那里设置了内存不足的处理程序。如果请求的内存块大小大于128bytes，就转调用第一级配置器。另外定义了两个alloc，一个是debug_alloc，每次配置一块内存时，都会配置比需求多8byte的空间以存储空间大小，通过assert语句来检查会不会内存溢出。另一个是simple_alloc，定义了两个版本的allocate和deallocate，它们都只是单纯的转调用。sgi stl容器全都使用simple_alloc接口。free-list的节点巧妙地使用了一个union结构来管理链表：
union obj{
union obj* free_list_link; //当作为*链表的一个结点时，存储其下一个节点的地址
char client_date[1]; //当其作为返回值时，返回的正好是分配内存的首地址
}
每次配置器需要向系统要内存的时候，都不是按客户需求向系统申请的，而是一次性向系统要了比需求更多的内存，放在内存池里，有一个free_start和free_end指示剩余的空间（也就是说内存池剩余的空间都是连续的，因此每次重新向system heap要空间的时候，都会把原先内存池里没用完的空间分配给合适的free list。）当free-list中没有可用区块了的时候，会首先从内存池里要内存，同样，也不是以按客户需求要多少块的，而是一次可能会要上20块，如果内存池内空间允许的话，可能会得到20个特定大小的内存，如果内存池给不了那么多，那么就只好尽力给出；如果连一个都给不出，那么就要开始向系统即system heap要空间了。换算的标准是bytes_to_get=2*total_bytes+ROUND_UP(heap_size>>4)。这个时候使用的是malloc，如果没成功，就尝试着从大块一点的freelist那里要一个来还给内存池，如果还是不行，那么会调用第一级空间配置器的malloc::allocate，看看out-of-memory机制能做点什么不。
总结起来整个过程大概是这样的，假设我们向系统要x大小的内存，
（1）x大于128byte，用第一级配置器直接向系统malloc，至于不成功的处理，过程仿照new，通过set_new_handler来处理，直到成功返回相应大小的内存或者是抛出异常或者是干脆结束运行；
（2）x小于128byte，用第二级配置器向内存池相应的free_list要内存，如果该freelist上面没有空闲块了，
（2.1）从内存池里面要内存，差不多要的是<=20个相应freelist大小的块，如果要不到：
（2.2）从系统的heap里面要内存给到内存池，换算的标准是bytes_to_get=2*total_bytes+ROUND_UP(heap_size>>4)，这时使用的是系统的malloc，如果要不到：
（2.3）从比较大的freelist那里要内存到内存池，如果还是要不到：
（2.4）从系统的heap里面要内存给到内存池，换算标准跟2.2一样，但是这时候使用的是第一级配置器的allocate，主要是看看能不能通过out_of_memory机制得到一点内存。所以，freelist总是从内存池里要内存的，而内存池可能从freelist也可能从系统heap那里要内存。
sgi stl的alloc的主要开销就在于管理这些小内存，管理这些小内存的主要开销就在于，每次freelist上的内存块用完了，需要重新要空间，然后建立起这个list来。freelist上的内存，会一直保留着直到程序退出才还给系统。但这不会产生内存泄漏，一来是管理的都是小内存，二来是，占用的内存只会是整个程序运行过程中小内存占用量最大的那一刻所占用的内存。
SGI STL的alloc是一种内存管理机制，用于管理小内存块的分配，以减少内存碎片。后来我又看了另外一些内存管理机制（利用对象管理资源），包括智能指针的RAII，用于复杂但可能过程不是很久的算法内存管理AutoFreeAlloc，ScopeAlloc，以及boost中的pool跟object_pool。总的来说，内存管理的基本要求就是：不重不漏，既不重复delete，也不漏掉delete。
首先是智能指针，智能指针的基本思想是利用编译器在对象离开作用范围后自动调用析构函数来实现内存的自动释放，即通过对象来管理资源，把指针封装成一个对象，在其构造、析构、赋值函数中，实现对内存的管理。最简单的是auto_ptr，你把指针给了它，它就在析构的时候把指针指向的内存释放掉。可是我要把指针赋值给其他人怎么办？它说，哦，那没办法，被赋值的那个人接管了你的内存，你就退休指向NULL吧。这显然给指针的应用带来了相当大的不便，想想，在用裸指针时，用temp = head, head = head->next这样的状况是多么常见，用容器存放指针也是常有的事（存放到容器是一种赋值行为）。那就使用share_ptr吧。share_ptr中记录了一块内存的reference_count，在构造时其为一，在复制构造、赋值时修改reference_count，在析构时reference_count--，如果reference_count为0，那么就把内存给释放了。在多线程中，reference_count便成了一个竞争资源，因此可能会成为瓶颈。另外，所谓的这个“把内存给释放了”，其实也可能只是一种指定的操作，例如把它放到freelist去啊之类的，是可以自定义的。
对它的实现思路基本了解了，也就是分两级，我主要对第二级，也就是默认的那个allocator的实现有些疑问，
大概说来它是这样的：对于较小的内存分配请求，采用预分配的链表的形式，以8的倍数大小为单位的内存区块(8,16,24,...128 )，每种大小都是一个链表，然后用一个数组把这些链表的头结点存起来，请求内存小于128bytes时就从数组找到对应的链表节点，如果该组链表结点不足，就从一个内部的heap划分出来20块请求大小的内存，加到链表中，再从链表取走一块用，当heap不够20块时，就直接分出去1块用，当一块都不够时(这个时候剩的大小一定也是8的倍数)，就把零头全加入到合适大小的链表中去，然后malloc 大小为40块请求大小的内存，20块再和刚刚同样处理(加入合适的链表，分出去一块),
其余20块大小的chunk就留在heap里备用，问题就是他是怎么释放掉malloc的内存的，我只看到malloc了，第二级allocator的代码里没有看到free的字眼，其中的deallocate函数是这样的
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;
}
上面的那个malloc_alloc就是第一级allocator, 是针对较大内存分配时才使用的，所以对于在第二级自身malloc的内存，这个函数只是简单的把那块内存返还到了指定大小的链表中而已。
我感觉虽然不该在这里释放，但也总要释放的吧？是我看漏了哪里吗？难道sgi stl的实现中有另一个函数来做这种工作？
如果没有的话，针对这种情形应该如何释放呢？
所有的链表中的内存块都不是独立malloc的，而是一次malloc中的一部分，而且一次malloc的内存很可能分散在多组链表里，我现在想的，是用一个数据结构把每次malloc的内存块的指针保存下来，在最后的最后全部free掉，但是这样又比较危险，如果有对象正在使用这块内存。
是否是这种设计本身决定了不能随便释放内存呢，有没有其他方法可以比较灵活的紧缩/释放allocator占用的内存呢？
一言以蔽之：不释放，等程序退出系统释放
参考：http://blog.csdn.net/hackbuteer1/article/details/7724534