STL之空间配置器

空间配置器 allocator 只是基层内存配置/释放行为的一层薄薄的包装，没有任何效率上的强化。一般而言，C++ 内存配置操作和释放操作如下：

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

其中，new 内含两阶段的操作：

1. 调用 ::operator new 配置内存；
2. 调用 Foo::Foo() 构造对象内容。

delete 也内含两阶段的操作：

1. 调用 Foo::~Foo() 将对象析构；
2. 调用 ::operator delete 释放内存。

allocator 将这两阶段的操作分开来。内存配置操作由 alloc::allocate() 负责，内存释放操作由 alloc::deallocate() 负责；对象构造操作由 ::construct() 负责，对象析构由 ::destroy() 负责。

在 <stl_construct.h> 中，destroy() 有两个版本。第一个版本接受一个指针，将指针所指之物析构掉。而第二个版本接受两个迭代器，将 [first, last) 范围内的所有对象析构掉。但是如果每个对象的析构函数都无关痛痒，而且对象数目很多，则会造成效率上的问题。所以首先利用 value_type() 获得迭代器所指对象的型别，再利用 __type_traits<T> 判断该型别的析构函数是否无关痛痒。

在 <stl_alloc.h> 中，考虑到小型区块所可能造成的内存碎片问题，SGI 设计了双层级配置器：

1. 第一级配置器直接使用 malloc() 和 free()
2. 第二级配置器则视情况采用不同的策略。

当配置区块超过 128 bytes 时，便调用第一级配置器；当配置区块小于 128 bytes 时，便采用复杂的内存池(memory pool)整理方式。

无论是第一级或第二级配置器，SGI 还为它再包装一个接口如下，使得配置器的接口符合 STL 规格：

template<class T. class Alloc>
class simple_alloc {
public:
    static T* allocate(size_t n)
    { return 0 == n ? 0 : (T*)Alloc::allocate(n * sizeof(T)); }
    static T* allocate(void)
    { return (T*)Alloc::allocate(sizeof(T)); }
    static void deallocate(T* p, size_t n)
    { if(0 != n) Alloc::deallocate(p, n * sizeof(T)); }
    static void deallocate(T* p)
    { Alloc::deallocate(p, sizeof(T)); }
};

第一级配置器以 malloc()、free()、realloc() 等 C 函数执行实际的内存配置、释放、重配置操作，并实现出类似 C++ new-handler 的机制。SGI 以 malloc() 而非 ::operator new 来配置内存，因此，SGI 不能直接使用 C++ 的 set_new_handler() 的操作，必须仿真一个 set_malloc_handler()。一旦内存不足，无法分配，则抛出 bad_alloc 异常，或是利用 exit(1) 直接终止程序，在此之前，会先调用由客户指定的处理例程。

对于第二级配置器，避免了太多小额区块造成内存的碎片，如下图:

SGI 第二级配置器的做法是：如果区块过大，超过 128 Bytes 时，就移交给第一级配置器处理。当区块小于 128 Bytes 时，则以内存池管理，也称为【次级配置】。每次配置一大块内存，并维护对应的自由链表，下次若有相同大小的内存需求，则直接从自由链表中取出。同时，如果客户释放小额区块，则由配置器回收到自由链表中。为了方便管理，SGI 第二级配置器会主动将任何小额区块的内存需求量上调至 8 的倍数（例如客户需求 30 Bytes，则上调到 32 Bytes），并维护 16 个链表，各自管理大小分别为 8、16、24、32、40、48、56、64、72、80、88、96、104、112、120、128 bytes 的小额区块。自由链表节点结构如下：

union obj {
    union obj* free_list_link;
    char client_data[1];
};

而结点正是因为 union 的缘故，所以从第一个字段出发，obj 被视为指向另一个结点的指针，从第二个字段出发，obj 被视为指向实际区块的指针。这样的方式节省了内存，省下了额外负担。

第二级配置器通过 allocate() 分配内存，通过 deallocate() 释放内存。如果申请内存时，自由链表中没有可用区块时，就调用 refill() 为自由链表重新填充空间。新的空间取自内存池，由 chunk_alloc() 来完成，它通过 end_free - start_free 来判断内存池的水量。

如果水量充足，就直接调出 20 个区块返回给自由链表。

如果水量不足以提供 20 个区块，但是还足够提供一个以上的区块，就取出这个不足 20 个区块的空间出去，同时，将 pass-by-reference 的 nobjs 参数修改为实际能够供应的区块数。

如果内存池连一个区块空间都无法供应，此时便需要利用 malloc() 从 heap 中配置内存，为内存池注入新的内存以供需求。先将内存池剩余的零头配置给合适的自由链表，然后向堆空间申请新的内存，新注入的水量为需求量的 2 倍，再加上一个随着配置次数增加而愈来愈大的附加量。最后将将第一块返回给用户，剩下的 19 块依附在自由链表上，余下的 20+n 个留在内存池中。

如果整个堆空间的内存已经不够申请了，malloc() 行动失败，那么 chunk_alloc() 就找寻有无尚未使用之区块，且区块足够大的自由链表，如果找到了就取出来；如果没找到就调用第一级空间配置器，利用其 out-of-memory 处理机制，或许有机会释放其他内存拿来使用。如果可以就成功，否则发出 bad_alloc 异常。