空间配置器（allocator）详解-stl源码剖析学习笔记

一、什么是空间配置器

空间配置器也就是配置空间，配置容器所需要的空间，该空间获取可以是内存，也可以是磁盘或其他存储介质。

二、STL规范必要接口

stl有很多实现版本，根据stl规范，allocator的必要接口如下：

//类型型别，设计缘由后续章节会介绍
allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference_type
//一个嵌套的模板类。class rebind<U>拥有唯一成员other，一个allocator<U>的typedef类型定义
allocator::rebind
//默认构造函数
allocator::allocator()
//拷贝构造函数
allocator::allocator(const allocator&)
//泛化的拷贝构造函数
template<class U> allocator::allocator(const allocator<U>&)
//默认析构函数
allocator::~allocator()
//返回某个对象的地址。算式a.address(x)等同于&x
pointer allocator::address(reference x) const
//返回某个const对象地址。算式a.address(x)等同于&x
//配置空间，足以存储n个T对象。第二个参数是个提示。实现上可能会利用它来增进区域性，或可完全忽略
pointer allocator::allocate(size_type n, const void* = 0)
//归还先前配置的空间
void allocator::deallocate(pointer p, size_type n)
//返回可成功配置的最大量
size_type allocator::max_size() const
//等同于new((const void*) p) T(x)
void allocator::construct(pointer p, const T& x)
//等同于p->~T()
void allocator::destroy(pointer p)

SGI STL的实现版本的空间配置有一个符合部分标准的空间配置std::allocator，该配置器只对::operator new和::operator delete进行了薄薄的封装，另有一个特殊空间配置器std::alloc进行复杂的内存动态配置和释放。以下我们讲SGI STL的空间配置。

三、配置器构造、析构部分

一般我们所习惯的C++内存配置操作和释放操作是这样的：

class Foo {};
Foo* pf = new Foo();	//配置内存，然后构造对象
delete pf;				//将对象析构，然后释放内存 

其中new算式包含两阶段操作：
1>调用::operator new配置内存
2>调用Foo::Foo()构造对象内容
delete算式也包含两阶段内容：
1>调用Foo::~Foo()析构对象
2>调用::operator delete释放内存

为了精密分工，stl allocator将这两个阶段区分开来。内存配置操作由alloc::allocate()负责，内存释放由alloc::deallocate()负责，对象构造由::construct()负责，对象析构由::destroy()负责。

stl配置器定义于中，SGI包含了以下两个文件：
#include<stl_alloc.h> //负责内存空间的配置和释放
#include<stl_construct.h> //负责对象内容的构造和析构

下图为的包含文件以及定义的内容：

<stl_construct.h>中的construct()实现：

#include<new.h>	//欲使用placement new，先包含此文件

template<class T1, class T2>
inline void constuct(T1* p, const T2& value) {
	new(p) T1(value);	//placement new，调用T1::T1(value)；
}

placement new：operator new的一个重载版本，不能自定义，分配内存空间在一个指定的已知空间，对应语法结构为A *p = new(ptr) A；次步骤为在ptr上分配空间，然后调用A的构造函数生成对象，p与ptr所指向的地址相同。此处为调用T1::T1(value)，在指定地址p所指空间上设置初始值value。

destroy()实现:

//destroy第二个版本，接受两个迭代器，value_type找出数值型别
template<class ForwardIterator>
inline void destroy(ForwardIterator  first, ForwardIterator last) {
	__destroy(first, last, value_type(first));
}
//判断value_type是否有trivial destructor
template<class ForwardIterator, class T>
inline void __destroy(ForwardIterator  first, ForwardIterator last, T*) {
	typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
	__destroy_aux(first, last, trivial_destructor());
}
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) {}

destroy()第一个版本直接调用析构函数，第二个版本会获取迭代器所指之物的型别，再利用_type_traits判断是否为trivial即是否无关痛痒，如果每个对象的析构函数操作都无关痛痒，则什么都不做，较少效率伤害，如果为_false_type则循环访问整个迭代器范围，并每次调用第一版本的destroy()。

四、空间的配置和释放

空间的配置和释放在<stl_alloc.h>中，考虑到小型区块可能造成的内存破碎问题，采用双层级配置器结构，利用宏定义_USE_MALLOC决定开放一级配置器，或者同时开放二级配置器。实际可以测试，SGI STL并未定义该宏。一二级配置结构如下：

1> 第一级配置

第一级配置以malloc()，free()，realloc()来实现配置，释放，再配置，如果配置需求不能被满足，则会循环调用自设定的模拟set_new_handler()并尝试再次配置，企图会在一次再次配置时成功。

2> 第二级配置

第二级配置避免了太多小额区块造成内存碎片以及其带来的管理内存的额外空间负担。其做法是区块够大交给第一级配置，区块小于128bytes交由内存池管理。

整个过程是怎么操作的呢？

第二级配置共维护16个free_lists，各自管理大小为8的倍数的小额区块，分别为
8，16,24,32,40,48,56,64,72,80,88,96,104，112，120,128bytes的小额区块。每次有内存需求，就从free_lists中拨出，如果客端释还小额区块，则回收到free_lists中。每次分配的需求量配置器会主动上调至8的倍数。其维护的函数有配置函数allocate()，释放函数deallocate()，以及free_list不可用时的填充函数refill（）。

函数allocate()的实现过程：判断区块大小n是否大于128bytes，大于调用一级函数malloc_alloc::allocate(n)，不大于则寻找适当的free_list，比如n为96bytes，对应的第12个free_list，如果该free_list有可用则拨出，调整剩余free_list的指向，如果没有则调用refill()填充free_list。图示如下：

释放函数deallocate()，同样先判断区块大小是否大于128，大于则调用一级配置malloc_alloc::deallocate(p,n)，不大于则找到对应的free_list进行回收。图示如下：

填充函数refill()，free_list没有可用空间时，将从内存池取空间(chunk_alloc()函数完成)并将结果区块依次连接到free_list进行填充。

chunk_alloc()函数，以end_free-start_free来判断内存池水量是否充足，如果充足则返回20个区块(默认取20个)给free_list，如果不充足但足够一个以上的区块，则把这些不足的返回给free_list，并调整nobjs为实际区块数，如果一个都不够，则利用malloc从heap中获取，新水量为获取量的两倍和一个随配置次数增加的附加量，heap成功，则递归调用自己，调整nobjs，按刚才策略返回给free_list，剩余留给内存池，如果heap失败，则遍历free_lists寻找是否有剩余的尚未使用且区块够大的空间，找到了就挖一块交出，找不到就调用一级配置，因为它有类似的new_handler机制，尝试看是否还能释放出内存，否则就发出bad_alloc异常。
以上为第二级空间配置器的设计内容。

内存池分配示例：