1、什么是空间配置器？
空间配置器负责空间配置与管理。配置器是一个实现了动态空间配置、空间管理、空间释放的class template。以内存池方式实现小块内存管理分配。关于内存池概念可以点击：内存池。
2、STL空间配置器产生的缘由
在软件开发，程序设计中，我们不免因为程序需求，使用很多的小块内存（基本类型以及小内存的自定义类型）。在程序中动态申请，释放。这个过程过程并不是一定能够控制好的，于是乎出现以下问题：
问题1：就出现了内存碎片问题。（ps外碎片问题）
问题2：一直在因为小块内存而进行内存申请，调用malloc，系统调用产生性能问题。
注：内碎片：因为内存对齐/访问效率（CPU取址次数）而产生 如 用户需要3字节，实际得到4或者8字节的问题，其中的碎片是浪费掉的。
外碎片：系统中内存总量足够，但是不连续，所以无法分配给用户使用而产生的浪费。如图：
（1）一级空间配置器和二级空间配置器实现思路：
空间配置策略：
用户申请空间大于128？
yes：调用一级空间配置器
no：调用二级空间配置器
客户端可以通过宏__USE_MALLOC进行自定义选择是否使用二级空间配置器。
STL设计了双层级配置器，第一级配置直接使用malloc()和free()；第二级配置器则视情况采用不同的策略，当配置区大于128bytes时，直接调用第一级配置器；当配置区块小于128bytes时，遍不借助第一级配置器，而使用一个memory pool来实现。究竟是使用第一级配置器还是第二级配置器，由一个__USE_MALLOC宏定义来控制。SGI STL中默认使用第二级配置器。
3、一级空间配置器
主要是Allocate()函数和Dellocate()函数，直接封装了malloc，free进行处理，增加了C++中的set_handler机制，增加内存分配时客户端可选处理机制。
#define __TRACE_DEBUG(...) \
__trace_debug(__FUNCTION__ , __FILE__, __LINE__, __VA_ARGS__); typedef void (*HANDLE_FUNC)(); template<int inst>
class MallocAllocTemplate
{
public:
//static void(*__malloc_alloc_oom_handler)();
static HANDLE_FUNC _malloc_alloc_oom_handler; void* OOM_Malloc(size_t n)
{
while ()//死循环一直申请空间,直到申请成功，或失败抛异常
{
if (_malloc_alloc_oom_handler == )
{
throw bad_alloc();
}
_malloc_alloc_oom_handler();//释放内存
void* second = malloc(n); //再次申请空间
if (second)
return second;
}
}
// 1： 分配内存成功， 则直接返回
// 2： 若分配失败， 则检查是否设置处理的handler，
//有则调用以后再分配。 不断重复这个过程， 直到分配成功为止。
//没有设置处理的handler， 则直接结束程序。
static void* Allocate(size_t n)
{
__TRACE_DEBUG("一级空间配置器申请%ubytes\n", n); void* first = malloc(n);
if (first == NULL) //第一次申请空间失败
{
first = OOM_Malloc();
}
return first;
}
//realloc实现机制与allocate类似
void* OOM_Realloc(size_t n)
{
while ()//死循环一直申请空间,直到申请成功，或失败抛异常
{
if (_malloc_alloc_oom_handler == )
{
throw bad_alloc();
}
_malloc_alloc_oom_handler();
void* second = realloc(n);
if (second)
return second;
}
}
static void* Rllocate(size_t n)
{
__TRACE_DEBUG("一级空间配置器申请%ubytes\n", n); void* first = realloc(n);
if (first == NULL)
{
first = OOM_Realloc();
}
return first;
} static void Delloctate(void* p, size_t n)
{
__TRACE_DEBUG("一级空间配置器释放%ubytes\n", n);
free(p);
} static HANDLE_FUNC SetMallocHandler(HANDLE_FUNC f)
{
HANDLE_FUNC old = f;
__malloc_alloc_oom_handler = f;
return old;
}
// static void(*SetMallocHandler(void(*f)()))()
// {
// void(*old)() = __malloc_alloc_oom_handler;
// __malloc_alloc_oom_handler = f;
// return(old);
// }
private:
}; //分配内存失败处理函数的句柄函数指针
template<int inst>
HANDLE_FUNC __MallocAllocTemplate<inst>::__malloc_alloc_oom_handler = NULL;
SetMallocHandler(HANDLE_FUNC f)
malloc，free，realloc等库函数是向系统申请内存并且操作的函数。平时我们并不太会遇到内存空间分配不出来的情况，但是如果这一套程序是运行在服务器上的，各种各样的进程都需要内存。这样频繁的分配内存，终有一个时候，服务器再也分配不出内存，那么空间配置器该怎么办呢？这个函数指针指向的句柄函数就是处理这种情况的设计。
SetMallocAllocHander（）一般是自己设计的一种策略。这种策略想要帮助操作系统得到内存空间用以分配。所以，设计这个函数就是一个提升空间配置器效率的一个方法。如果并不想设计这个策略，也可以把句柄函数初始化为0。
__TRACE_DEBUG使用
对于内存池的内部实现过程共还是比较复杂的，虽然代码量，函数比较简单。但是调用过程可能比较复杂。这时，如果我们选择debug调试，过程会相当的繁琐，需要仔细记录调用堆栈过程以及数据流向，逻辑变更等。对于楼主这种水货来说，估计完事就要苦了。
所以，就__TRACE_DEBUG使用进行跟踪，打印数据流向，逻辑走向，文件，函数，方法，行位置。那么我们就能根据这个记录进行程序的排错以及调优了。
//通过__TRACE_DEBUG做白盒测试 //#define __DEBUG__
static string GetFileName(const string& path)
{
char ch = '/'; #ifdef _WIN32
ch = '\\';
#endif size_t pos = path.rfind(ch);
if (pos == string::npos)
return path;
else
return path.substr(pos + );
} // 用于调试追溯的trace log
inline static void __trace_debug(const char* function,
const char * filename, int line, char* format, ...)
{
// 读取配置文件
#ifdef __DEBUG__
// 输出调用函数的信息
fprintf(stdout, "【 %s:%d】%s", GetFileName(filename).c_str(), line, function); // 输出用户打的trace信息
va_list args;
va_start(args, format);
vfprintf(stdout, format, args);
va_end(args);
#endif
} #define __TRACE_DEBUG(...) __trace_debug(__FUNCTION__ , __FILE__, __LINE__, __VA_ARGS__)；
4、二级空间配置器
二级空间配置器的实现就比较复杂了，主要由内存池以及伙伴系统：*链表组成。
template<bool threads, int inst>
class DefaultAllocTemplate
{
enum { __ALIGN = }; //(排列基准值，即排列间隔)
enum { __MAX_BYTES = }; //最大值
enum { __NFREELISTS = __MAX_BYTES / __ALIGN }; //排列链
public:
static size_t FreeList_index(size_t n) //计算应该去取内存块的相应位置，对齐
{
return (n + __ALIGN - ) / __ALIGN - ;
}
static size_t Round_up(size_t bytes) //对齐
{
return ((bytes + __ALIGN - ) & ~(__ALIGN - ));
} // 到内存池申请nobjs个对象
static char* ChunkAlloc(size_t bytes, size_t& nobjs)
{
size_t needBytes = bytes * nobjs;
size_t leftBytes = _endfree - _startfree;
if (needBytes <= leftBytes)
{
__TRACE_DEBUG("狭义内存池有足够%u个对象\n", nobjs); char* ret = _startfree;
_startfree += needBytes;
return ret; //申请到20个
}
else if(leftBytes > bytes){
nobjs = leftBytes / needBytes;
__TRACE_DEBUG("狭义内存池只有%u个对象\n", nobjs); char* ret = _startfree;
_startfree += nobjs;
return ret; //申请到1~19个
}
else
{
//处理余下的小块内存
if (leftBytes > )//挂到*链表上的对应位置（头插）
{
size_t index = FreeList_index(leftBytes);
((obj*)_startfree)->_freelistlink = _freeList[index];
_freeList[index] = (obj*)_startfree;
} //一个也没有
size_t sizeToGet = needBytes * + Round_up(_heapsize >> );
__TRACE_DEBUG("一个对象都没有，到系统申请%ubytes\n", sizeToGet); _startfree = (char*)malloc(sizeToGet);
if (_startfree == NULL)
{
// 系统已经没有足够的内存-尽力为之
// 到更大的*链表中去取内存块，置入内存池
for (size_t i = FreeList_index(bytes); i < __NFREELISTS; i++)
{
if (_freeList[i]) //（头删）
{
_startfree = (char*)_freeList[i];
_freeList[i] = ((obj*)_startfree)->_freelistlink;
_endfree = _startfree + (i + ) * __ALIGN;
return ChunkAlloc(bytes, nobjs);//重新申请
}
}
// 山穷水尽 -- 求助一级空间配置器
//*链表中也没有分配到内存， 则再到一级配置器中分配内存，
//一级配置器中可能有设置的处理内存， 或许能分配到内存。
_endfree = NULL;
_startfree = (char*)MallocAllocTemplate<>::Allocate(sizeToGet);
}
//更新内存池
_heapsize += sizeToGet;
_endfree = _startfree + sizeToGet;
return ChunkAlloc(bytes, nobjs); //重新申请
}
}
// 填充*链表
static void* Refill(size_t bytes)
{
size_t nobjs = ;
__TRACE_DEBUG("到狭义内存池取%u个%ubytes字节的对象\n", nobjs, bytes); char* chunk = ChunkAlloc(bytes, nobjs);
__TRACE_DEBUG("取到了%u个对象，返回一个对象，将剩余的%u对象挂到*链表的下面\n", nobjs, nobjs - ); if (nobjs == )//如果只分配到一块，直接使用它
{
return chunk;
}
size_t index = FreeList_index(bytes);
obj *cur = NULL;
obj *next = NULL;
for (size_t i = ; i < nobjs; i++)
{
next = (obj*)(chunk + i*bytes);
if (_freeList[index] == NULL)
{
_freeList[index] = next;
}
else {
cur->_freelistlink = next;
}
cur = next;
}
if (cur)
{
cur->_freelistlink = NULL;
}
return chunk;
}
static void* Allocate(size_t n)
{
__TRACE_DEBUG("二级空间配置器申请%ubytes\n", n); if (n>__MAX_BYTES)
{
return MallocAllocTemplate<>::Allocate(n);
} // ps:多线程环境需要考虑加锁
size_t index = FreeList_index(n); //计算n在*链表中的位置
if (_freeList[index] == NULL) //*链表为空
{
__TRACE_DEBUG("在freeList[%u]下面没有内存块对象\n", index); return Refill(Round_up()); //获取大块内存插入到*链表中
}
else{ //*链表不为空，取第一块，类似于头删
__TRACE_DEBUG("在freeList[%u]取一个内存块对象\n", index); obj* result = _freeList[index];
_freeList[index] = result->_freelistlink;
return result;
}
}
static void Dellocate(void* ptr, size_t n)
{ if (n > __MAX_BYTES)
{
MallocAllocTemplate<>::Dellocate(ptr, n);
return;
} // ps:多线程环境需要考虑加锁
size_t index = FreeList_index(n);
__TRACE_DEBUG("将释放的内存块对象挂到freeList[%u]\n", index); if (ptr)
{
obj* back = (obj*)ptr; //将释放的内存块对象挂到_freeList[index]上，类似于头插
back->_freelistlink = _freeList[index];
_freeList[index] = back;
}
}
protected:
//定义*链表
union obj
{
obj* _freelistlink; //指向下一个内存块的指针
char clientdata[]; /* The client sees this. */
};
static obj* _freeList[__NFREELISTS];//*链表 //狭义内存池
static char* _startfree; //内存池水位线开始处
static char* _endfree; //内存池水位线结束处
static size_t _heapsize; //从系统堆分配的总大小
};
代码中逻辑明了，而且已经注释得很清楚了，这里就不在赘述了。
template <bool threads, int inst>
char* DefaultAllocTemplate<threads, inst>::_startfree = ; template <bool threads, int inst>
char* DefaultAllocTemplate<threads, inst>::_endfree = ; template <bool threads, int inst>
size_t DefaultAllocTemplate<threads, inst>::_heapsize = ; template <bool threads, int inst>
typename DefaultAllocTemplate<threads, inst>::obj* DefaultAllocTemplate<threads, inst>::_freeList[__NFREELISTS] = { }; #ifdef __USE_MALLOC
typedef MallocAllocTemplate<> alloc;
#else
typedef DefaultAllocTemplate<false, > alloc;
#endif //__USE_MALLOC template<class T, class Alloc>
class SimpleAlloc
{
public:
static T* Allocate(size_t n)
{
return == n ? : (T*)Alloc::Allocate(n * sizeof(T));
} static T* Allocate(void)
{
return (T*)Alloc::Allocate(sizeof(T));
} static void Dellocate(T *p, size_t n)
{
if ( != n)
Alloc::Dellocate(p, n * sizeof(T));
} static void Dellocate(T *p)
{
Alloc::Dellocate(p, sizeof(T));
}
}; void TestAlloc1()
{
void *p1 = DefaultAllocTemplate<false, >::Allocate();
DefaultAllocTemplate<false, >::Dellocate(p1, ); void *p2 = DefaultAllocTemplate<false, >::Allocate();
void *p3 = DefaultAllocTemplate<false, >::Allocate(); DefaultAllocTemplate<false, >::Dellocate(p2, );
DefaultAllocTemplate<false, >::Dellocate(p3, );
} void TestAlloc2()
{
cout << " 测试系统堆内存耗尽 " << endl; DefaultAllocTemplate<false, >::Allocate( * * );
//DefaultAllocTemplate<false, 0>::Allocate(1024 * 1024 * 512);
//DefaultAllocTemplate<false, 0>::Allocate(1024 * 1024); // 不好测试，说明系统管理小块内存的能力还是很强的。
for (int i = ; i < ; ++i)
{
DefaultAllocTemplate<false, >::Allocate();
}
}
TestAlloc1()
TestAlloc2()
5、空间配置器存在的问题
（1）貌似二级空间配置器中的空间重头到尾都没看到他归还给系统。那么问题就是，内存池空间何时释放？
对于这个问题，在回头浏览一下源码及结构图，你就会发现，大于128的内存，客户程序Deallocate之后会调free释放掉，归还给了系统。
但是，内存池中获取的空间，最终，假定用户都调用Dealloc释放调了，那么他们又在哪里呢？
没有还给系统，没有在内存池，在*链表中。
Got it：程序中不曾释放，只是在*链表中，且配置器的所有方法，成员都是静态的，那么他们就是存放在静态区。释放时机就是程序结束。
（2）如果需要释放，那么应该怎么处理呢？
因为真正可以在程序运行中就归还系统的只有*链表中的未使用值，但是他们并不一定是连续的（用户申请空间，释放空间顺序的不可控制性），所以想要在合适时间（eg一级配置器的handler中释放，或者设置各阀值，分配空间量到达时处理），就必须保证释放的空间要是连续的。保证连续的方案就是：跟踪分配释放过程，记录节点信心。释放时，仅释放连续的大块。
（3）STL空间配置器的效率
既然已经存在，而又被广泛使用，那么，整体的效率，以及和STL内部容器之间的使用配合还是没问题的。什么时候使用空间配置器最高效呢？就是你使用进行类似于容器中频繁的插入删除操作，而频繁的操作小块内存时，配置器就是比较高效的了，它的时间复杂度这个时候可以达到Ｏ（１）。而且避免了外碎片问题。
但是，我们考虑几种情况：
a. 用户只需要无限的char类型空间，然而配置器中却对齐到8，于是乎，整个程序中就会有7/8的空间浪费。
b.对于假定用户申请N次8空间，将系统资源耗到一定程度，然后全部释放了，*链表中的空间都是连续的。却没有释放。
但是：用户需要申请大于8的空间时，却依旧没有空间可用。
总之：这个问题就是，空间可能全部积攒在小块*链表中，却没有用户可用的。这就尴尬了。
附：利用空间配置器给容器分配空间
//myList.h
#pragma once #include "myAllocator.h" template<class T>
struct ListNode
{
ListNode<T>* _prev;
ListNode<T>* _next; T _data;
}; template<class T, class Ref, class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> Self;
Node* _node; ListIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(operator*());
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator==(const Self& s) const
{
return _node = s._node;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
}; template<class T, class Alloc = alloc>
class List
{
typedef ListNode<T> Node;
typedef SimpleAlloc<Node, Alloc> ListAllocator;
public:
typedef ListIterator<T, T&, T*> Iterator;
typedef ListIterator<T, const T&, const T*> ConstIterator; Iterator Begin()
{
return _head->_next;
}
ConstIterator Begin() const
{
return _head->_next;
}
Iterator End()
{
return _head;
}
ConstIterator End() const
{
return _head;
} List()
{
_head = Create(T());
_head->_next = _head;
_head->_prev = _head;
}
Node* Create(const T&x)
{
Node* _node = ListAllocator::Allocate();//申请空间
new(&_node->_data)T(x); //构造对象 _node->_data = x;
_node->_next = NULL;
_node->_prev = NULL; return _node;
}
~List()
{
Clear();
DestoryNode(_head);
_head = NULL;
}
void Clear()
{
Node* cur = _head->_next;
while (cur!=_head)
{
Node* next = cur->_next;
DestoryNode(cur);
cur = next;
}
_head->_next = _head;
_head->_prev = _head;
}
void DestoryNode(Node* node)
{
(&node->_data)->~T();
ListAllocator::Dellocate(node);
} void PushBack(const T& x)
{
Node* _tail = _head->_prev;
Node* tmp = Create(x); _tail->_next = tmp;
tmp->_prev = _tail;
_head->_prev = tmp;
tmp->_next = _head; Insert(--End(), x);
}
void PushFront(const T& x)
{
Insert(Begin(), x);
}
void Insert(Iterator it, const T& x)
{
Node* pos = it._node;
Node* tmp = Create(x);
Node* prev = pos->_prev;
assert(pos); prev->_next = tmp;
tmp->_prev = prev;
tmp->_next = pos;
pos->_prev = tmp;
}
void PopBack()
{
Erase(--End());
}
void PopFront()
{
Erase(Begin());
}
Iterator Erase(Iterator& it)
{
Node* pos = it._node;
Node* prev = pos->_prev;
Node* next = pos->_next;
assert(pos&&pos != _head); prev->_next = next;
next->_prev = prev; DestoryNode(pos);
it._node = prev;
return next;
}
private:
Node* _head;
}; void Print(const List<int>& l1)
{
List<int>::ConstIterator it = l1.Begin();
while (it != l1.End())
{
cout << *it << " ";
it++;
}
cout << endl;
} void TestList1()
{
List<int> l1;
l1.PushBack();
l1.PushBack();
l1.PushBack();
l1.PushBack();
l1.PushBack();
l1.PushBack();
Print(l1);
List<int>::Iterator it2 = l1.Begin();
while (it2!=l1.End())
{
if (*it2%==)
{
l1.Erase(it2);
}
*it2++;
}
Print(l1);
} void TestList2()
{
List<string> l2;
l2.PushBack("ping");
l2.PushBack("z");
l2.PushBack("");
l2.PushFront("");
l2.PushFront("");
l2.PushFront("");
l2.PushFront("");
List<string>::Iterator it = l2.Begin();
while (it != l2.End())
{
cout << *it << " ";
++it;
}
cout << endl;
}
//myVector.h
#pragma once
#include "myAllocator.h" template<class T, class Alloc = alloc>
class Vector
{
typedef SimpleAlloc<T, Alloc> DataAllocator;
public:
typedef T* Iterator;
typedef const T* ConstIterator; Vector()
:_start(NULL)
,_finish(NULL)
,_endofStorage(NULL)
{}
~Vector()
{
for (size_t i=;i<Size();i++)
{
(_start + i)->~T();
}
DataAllocator::Dellocate(_start, Capacity());
}
void PushBack(const T& x)
{
if (_finish == _endofStorage)
{
size_t size = Size();
size_t newsize = size ? size * : ;
Expand(newsize);
} new(_finish)T(x);
++_finish;
}
void Expand(size_t n)
{
if (n > Capacity())
{
size_t size = Size();
size_t capacity = Capacity();
T* tmp = DataAllocator::Allocate(n);
for (size_t i= ;i<size;++i)
{
new(tmp + i)T(_start[i]);
(_start + i)->~T();
} DataAllocator::Dellocate(_start, capacity);
_start = tmp;
_finish = _start + size;
_endofStorage = _start + capacity;
}
}
void Reserver(size_t n)
{
Expand(n);
}
inline size_t Size()
{
return _finish - _start;
}
inline size_t Capacity()
{
return _endofStorage - _start;
}
Iterator Begin()
{
return _start;
}
Iterator End()
{
return _finish;
}
T& operator[](size_t pos)
{
assert(pos < Size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < Size());
return _start[pos];
}
protected:
Iterator _start; //指向顺序表头
Iterator _finish; //指向指向顺序表最后一个元素的下一个位置
Iterator _endofStorage; //指向顺序表尾部
}; void TestVector1()
{
Vector<int> v;
v.PushBack();
v.PushBack();
v.PushBack();
v.PushBack();
v.PushBack(); Vector<int>::Iterator it = v.Begin();
while (it != v.End())
{
cout << *it << " ";
++it;
}
cout << endl;
} void TestVector2()
{
Vector<string> v1;
v1.PushBack("");
v1.PushBack("");
v1.PushBack("");
v1.PushBack(""); for (size_t i = ; i < v1.Size(); ++i)
{
cout << v1[i] << " ";
}
cout << endl;
}
The end.....