【无标题】

【无标题】

SGI STL源码剖析——空间配置器

前言

空间配置器SGI空间配置器内存配置和对象构造构造和析构空间的配置和释放

第一级配置器第二级配置器

前言

这段时间读了侯捷老师的STL源码剖析，有一些体会和收获，看书的过程也碰到了许多疑惑，因此将自己的理解记录下来，原书和源码
https://github.com/SilverMaple/STLSourceCodeNote

空间配置器

配置器负责空间配置和管理，STL的所有容器都需要配置空间才能存放内容，这里所谓空间配置就是指内存配置。配置器其实就是一个实现了动态空间配置、管理和释放的类模板。
C/C++中本就有内存申请和释放的 *** 作，STL为什么还要单独实现空间配置器呢，主要还是为了效率问题。如果任由STL中的容器自行通过malloc分配内存，那么频繁的分配和释放内存会导致堆中有很多的外部碎片。可能堆中的所有空闲空间之和很大，但当申请新的内存的请求到来时，没有足够大的连续内存可以分配，这将导致内存分配失败。
注：
内碎片：因为内存对齐/访问效率（CPU取址次数）而产生 如 用户需要3字节，实际得到4或者8字节的问题，其中的碎片是浪费掉的。
外碎片：系统中内存总量足够，但是不连续，所以无法分配给用户使用而产生的浪费。

SGI空间配置器

按照STL的标准规范，空间配置器是一个类模板，名称是allocator，而SGI STL的配置器有所不同。它的名称是alloc，并且实例化不接受参数，如果在声明容器时指定SGI配置器，

vector iv;

但是实际上SGI STL已经为每一个容器都缺省了alloc为空间配置器，并不需要我们指定。
SGI也提供了标准额的空间配置器allocator，但只是对new和delete的封装，所以效率不佳。因此我们重点学习的是SGI提供的特殊空间配置器std::alloc，即书中所述具备次配置力的SGI空间配置器。

内存配置和对象构造

C++中通过new申请一个对象的 *** 作

class Foo { ... };
Foo* pf = new Foo;
delete pf;

new一个对象（单身狗狂喜）实际上是包含了两步 *** 作的，通过::operator new申请内存，然后再通过类的构造函数构造对象初始化内存。delete时也是分为两步，先将对象析构，再调用::operator delete释放内存。
为什么是::operator new呢，那就有必要看一下new和operator new的区别。
我们都知道new和malloc是有区别的，有些地方解释说new是运算符，实际上不太准确，new本质上来说是一个关键字，那为啥说new可以重载呢，求实重载的是运算符或者说函数operator new。如上面所说，new本身就是包含两步 *** 作的，那这第一步的申请内存就是::operator new了。
new：指我们在C++里通常用到的运算符，比如A* a = new A; 对于new来说，有new和::new之分，前者位于std
operator new()：指对new的重载形式，它是一个函数，并不是运算符。对于operator new来说，分为全局重载和类重载，全局重载是void* ::operator new(size_t size)，在类中重载形式 void* A::operator new(size_t size)。还要注意的是这里的operator new()完成的 *** 作一般只是分配内存，事实上系统默认的全局::operator new(size_t size)也只是调用malloc分配内存，并且返回一个void*指针。
operator new就像operator + 一样，是可以重载的。如果类中没有重载operator new，那么调用的就是全局的::operator new来完成堆的分配。同理，operator new[]、operator delete、operator delete[]也是可以重载的。
也就是说如果我们在类中重载了new，那么编译器就会使用我们重载的new来完成第一步。
我们可以做个验证，

#include
#include
using namespace std;
class A
{  
private:
    int val;
public:
    A(int x): val(x)
    {
        cout << "构造" << endl;
    }
    ~A()
    {
        cout << "析构" << endl;
    }
    void * operator new(size_t sz){  

        A * t = (A*)malloc(sizeof(A));  
        cout << "内存分配" << endl;  
        return t;  
    }  

    void operator delete(void *p){  

        free(p);  
        cout << "内存释放" << endl;  
        return;  
    } 
};
int main()
{
    A *p = new A(3);
    delete p;
}

[pengzheng@localhost ~]$ g++ -o main main.cpp
[pengzheng@localhost ~]$ ./main
内存分配
构造
析构
内存释放
好了，这样我们就明白了new一个对象是分为两步的，也明白了第一步调用的是::operator new，那还有一个经常提起的new是placement new，这有是啥呢？
placement new实际上也是对::operator new的重载，
void* operator new (std::size_t size, void* ptr) throw();
它不分配内存，调用合适的构造函数在ptr所指的地方构造一个对象，之后返回实参指针ptr。
简单来说，就是使用new申请空间时，是从系统的“堆”（heap）中分配空间。申请所得的空间的位置是根据当时的内存的实际使用情况决定的。但是，在某些特殊情况下，可能需要在已分配的特定内存创建对象，这就是所谓的“定位放置new”（placement new） *** 作。
定位放置new *** 作的语法形式不同于普通的new *** 作。例如，一般都用A* p=new A申请空间，而定位放置new *** 作则使用如下语句

A* p=new (ptr)A;

申请空间，其中ptr就是指定的内存首地址。
好了，说了这么多，主要是为了说明STL的allocator是将new一个对象的两阶段 *** 作分开来，内存配置和释放分别由alloc:allocate()以及alloc:deallocate()负责，而对象构造和析构由::construct()和::destroy()负责。

构造和析构

先来看构造，构造通过construct

template 
inline void _Construct(_T1* __p, const _T2& __value) {
	//这里就是调用placement new，在调用_T1的构造函数去将初始值设置到指定内存p所指位置
	new ((void*) __p) _T1(__value);  
}

当然还有一个接受无参的版本

template 
inline void _Construct(_T1* __p) {
	new ((void*) __p) _T1();
}

构造比较简单，然后看析构，析构的复杂之处在于要判断是否需要真的去析构，因为有些析构函数实际上是什么都没有做。先看简单的版本，

template 
inline void _Destroy(_Tp* __pointer) {
	//这个析构就是直接调用类的析构函数去析构
	__pointer->~_Tp();  
}

然后看第二个版本，这里传入了一个first和last两个迭代器，然后析构此范围内的所有对象

template 
inline void _Destroy(_ForwardIterator __first, _ForwardIterator __last) {
	//__VALUE_TYPE判断指针类型
	__destroy(__first, __last, __VALUE_TYPE(__first));
}
//__destroy干了啥呢
template 
inline void 
__destroy(_ForwardIterator __first, _ForwardIterator __last, _Tp*)
{
	typedef typename __type_traits<_Tp>::has_trivial_destructor _Trivial_destructor;    
	__destroy_aux(__first, __last, _Trivial_destructor());
}
//__destroy_aux又干了啥呢，有两个版本
template  
inline void __destroy_aux(_ForwardIterator, _ForwardIterator, __true_type) {}

template 
void __destroy_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type)
{
	for ( ; __first != __last; ++__first)
	destroy(&*__first);
}

第二个版本的destroy()做了什么呢？在[first, last)这个范围去析构对象，每个对象都析构一次，这些析构如果没有什么实际的 *** 作那就太没必要了，所以呢先用__VALUE_TYPE判断了迭代器所指对象的类型，再利用__type_traits<_Tp>::has_trivial_destructor判断是否是没什么 *** 作的析构函数，是的话到__true_type里面什么都不执行，不是的话到__false_type里面虚幻调用第一个版本的destroy(&*__first)。
这里确实很有意思，需要关注一下。

空间的配置和释放

对象的构造和析构相对比较简单，就是调用构造函数和析构函数处理。SGI STL的内存配置使用了两层的配置器。我们知道C++申请和释放内存的基本 *** 作是::operator new和::operator delete，其底层实现就是malloc()和free()。SGI的第一层配置器就是使用malloc()和free()，同时实现了第二层配置器来解决频繁申请内存的内存碎片和效率问题。
当配置区块超过128 bytes 时，视之为 “足够大”，便调用第一级配置器；当配置区块小于 128 bytes 时，视之为 “过小” ，为了降低额外负担，便采用内存池管理方式。
前面说了SGI STL的配置器是alloc，这实际上是个typedef，

//直接将inst参数设置为0，所以alloc本身不支持指定任何参数了
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;

在分析alloc之前，我们要知道SGI为alloc封装了一个接口以符合STL规范，

template
class simple_alloc {
public:
    static _Tp* allocate(size_t __n)
      { return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }
    static _Tp* allocate(void)
      { return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
    static void deallocate(_Tp* __p, size_t __n)
      { if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
    static void deallocate(_Tp* __p)
      { _Alloc::deallocate(__p, sizeof (_Tp)); }
};

这个封装的接口将配置器的配置单位从byte转为元素大小sizeof (_Tp)，后面看容器代码我们会发现，所有容器都是用这个simple_alloc

第一级配置器

第一级配置器是__malloc_alloc_template这个模板，只是对malloc和free的封装，

//注意，无「template型别参数」。至于「非型别参数」inst，完全没派上用场。
template 
class __malloc_alloc_template {
private:
	// 函数指针，处理内存不足情况，这里需要注意_S_oom_malloc和_S_oom_realloc是在内存不足时必定
	// 调用的，然后其中又去调用__malloc_alloc_oom_handler这个由用户指定的处理函数
	static void* _S_oom_malloc(size_t);
	static void* _S_oom_realloc(void*, size_t);
	#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
		static void (* __malloc_alloc_oom_handler)();
	#endif
public:
	static void* allocate(size_t __n)
	{
		// 第一级配置器直接使用malloc
		void* __result = malloc(__n);
		// malloc返回NULL说明内存不足，改用oom方法处理内存不足
		if (0 == __result) __result = _S_oom_malloc(__n);
		return __result;
	}
	
	static void deallocate(void* __p, size_t )
	{
		// 第一级配置器直接使用free
		free(__p); 
	}
	
	//realloc尝试重新调整之前调用 malloc 申请的内存
	static void* reallocate(void* __p, size_t , size_t __new_sz)
	{
		// 第一级配置器直接使用realloc()
		void* __result = realloc(__p, __new_sz);
		// 无法满足需求时使用oom_realloc()
		if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
		return __result;
	}

  // 以下模拟c++的set_new_handler(),可以指定自己的oom handler
	static void (* __set_malloc_handler(void (*__f)()))()
	{
		void (* __old)() = __malloc_alloc_oom_handler;
		__malloc_alloc_oom_handler = __f;
		return(__old);
	}

};

在C++中有一个new handler机制，当内存分配无法满足时可以在抛出bad_alloc异常前调用指定的处理函数，这个处理函数就是new handler。由于这里直接采用malloc，所以就没有new handler，那就只能单独实现一个__set_malloc_handler。
我们可以看一下这个_S_oom_malloc里面干了啥，

template 
// 由客户端设定
void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
template 
void* __malloc_alloc_template<__inst>::_S_oom_malloc(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_handler)();  // 企图释放内存
        __result = malloc(__n);   // 尝试配置内存
        if (__result) return(__result);
    }
}

可以看到，第一级配置器还是比较简单的，就是malloc的 *** 作

第二级配置器