考虑到过多“小型区块”可能造成的内存碎片问题，SGI设计了双层级配置器：
第一级配置器直接调用malloc()和free()；
第二级配置器分两种情况：当配置区块大于128字节时，调用第一级配置器；当配置区块小于128字节时，采用内存池管理。
一.第一级配置器
1.__malloc_alloc_tempalte源码
template <int inst>
class __malloc_alloc_template
{
private:
//以下函数用来处理内存不足的情况
static void *oom_malloc(size_t);
static void *oom_realloc(void *, size_t);
static void (* __malloc_alloc_oom_handler)();
public:
static void * allocate(size_t n)
{
void *result = malloc(n); //第一级配置器直接使用malloc();
//以下情况无法满足时，改用oom_malloc()
if (0 == result) result = oom_malloc(n);
return result;
}
static void deallocate(void *p, size_t /* n */)
{
free(p);//第一级配置器直接使用free()
}
static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
{
void * result = realloc(p, new_sz);//第一级配置器直接使用realloc()
//以下情况无法满足需求时，改用oom_realloc()
if (0 == result) result = oom_realloc(p, new_sz);
return result;
}
//仿真C++的set_new_handler()
static void (* set_malloc_handler(void (*f)()))()
{
void (* old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return(old);
}
};
// malloc_alloc out-of-memory handling
template <int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
template <int inst>
void * __malloc_alloc_template<inst>::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);
}
}
template <int inst>
void * __malloc_alloc_template<inst>::oom_realloc(void *p, 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 = realloc(p, n);//再次尝试配置内存
if (result) return(result);
}
}
从源码中我们看到，第一级配置器通过malloc()，free()，realloc()等C函数来实现内存的配置和释放，并实现了类似C++的new handler机制（你可以要求系统在内存需求无法满足时，调用一个你所指定的函数）。
第一级配置器的allocate()和realloc()都是在调用malloc()和realloc()不成功后，改调用oom_malloc()和oom_realloc()。这两个函数都有内循环，不断调用"内存不足处理例程"，期望在某次调用之后，获得足够的内存而圆满完成任务。但如果“内存不足处理例程“并未被客端设定，oom_malloc()和oom_realloc便调用_THROW_BAD_ALLOC丢出bad_alloc异常信息，或利用exit(1)直接中止程序。
二.第二级配置器
第二级配置器相比第一级配置器多了一些机制，用来避免太多小区块造成的内存碎片和额外负担（指动态分配内存块的时候，位于其头部的额外信息，包括记录内存块大小的信息以及内存保护区）。
所谓内存池管理：每次配置一大块内存，并维护一个自由链表（free-list）。下次再有相同大小的内存需求，就直接从free-lists中配置。如果客端释放小型区块，就由配置器会受到free-lists中。为了方便管理，第二级配置器会主动将任何小区块的内存需求上调至8的倍数（比如需求30字节，就自动调整为32字节），并维护16个free-lists，分别管理8,16,24，...，120,128字节的小区块。free-lists结点结构如下：
union obj //free-lists数据结构
{
union obj * free_list_link;
char client_data[1]; /* The client sees this. */
};
union能够实现一物二用的效果：当节点所指的内存块是空闲块时，obj被视为一个指针，指向另一个节点。当节点已被分配时，被视为一个指针，指向实际区块。所以维护链表（lists）并不会造成额外负担。
1.__default_alloc_tempalte源码
enum {__ALIGN = 8}; //小型区块的上调边界
enum {__MAX_BYTES = 128}; //小型区块的上线
enum {__NFREELISTS = __MAX_BYTES/__ALIGN}; //free-lists个数
template <bool threads, int inst>//threads用于多线程
class __default_alloc_template {
private:
//将bytes上调至8的倍数
static size_t ROUND_UP(size_t bytes)
{
return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
}
private:
union obj //free-lists数据结构
{
union obj * free_list_link;
char client_data[1]; /* The client sees this. */
};
private:
//16个free-lists
static obj * free_list[__NFREELISTS];
//根据函数申请的区块大小，决定使用第n个free-list，n从0开始
static size_t FREELIST_INDEX(size_t bytes)
{
return (((bytes) + __ALIGN-1)/__ALIGN - 1);
}
//返回一个大小为n的对象，并可能加入大小为n的其他区块到free list
static void *refill(size_t n);
//配置一大块空间，可容纳nobjs个大小为“size”的区块
//不足时,nobjs返回不定数目
static char *chunk_alloc(size_t size, int &nobjs);
static char *start_free;//内存池起始位置，只在chunk_alloc变化
static char *end_free;//内存池结束位置，只在chunk_alloc变化
static size_t heap_size;
public:
static void * allocate(size_t n);
static void deallocate(void *p, size_t n);
static void * reallocate(void *p, size_t old_sz, size_t new_sz);
};
2.空间配置函数allocate()源码
首先判断区块大小，大于128字节就调用第一级配置器，否则就寻找对应的free list。如果有可用区块，就直接使用，否则，就将区块大小大小上调至8的倍数，然后调用refill()，准备为free list重新填充空间。
static void * allocate(size_t n)
{
obj * __VOLATILE * my_free_list;
obj * __RESTRICT result;
//大于128字节就调用第一级配置器
if (n > (size_t) __MAX_BYTES)
{
return(malloc_alloc::allocate(n));
}
//寻找16个free lists中适合的
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if (result == 0)
{
//没有找到，准备重新填充free list
void *r = refill(ROUND_UP(n));
return r;
}
//调整free list
*my_free_list = result -> free_list_link;
return (result);
};
区块从free list中调出的操作如下图：
3.空间释放函数deallocate()
该函数首先判断区块大小，大于128字节就调用第一级配置器。
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;
}
3.refill()源码
使用allocate()配置空间时，富哦发现free list中没有可用区块，就调用refill()，为free list填充空间。缺省取得20个新区块，若果内存池空间不足，获得区块可能少于20个。
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n)
{
int nobjs = 20; //默认申请块数
char * chunk = chunk_alloc(n, nobjs);
obj * __VOLATILE * my_free_list;
obj * result;
obj * current_obj, * next_obj;
int i;
//如果只获得一个区块，这个区块就分配给调用者使用，free list无新节点
if (1 == nobjs) return(chunk);
//否则准备调整free list，纳入新节点
my_free_list = free_list + FREELIST_INDEX(n);
//在chunk空间内建立free list
result = (obj *)chunk; //这一块准备返回给客端
//将free list指向从内存池拿出的空间
*my_free_list = next_obj = (obj *)(chunk + n);
//将新free list的节点串接起来
for (i = 1; ; i++) //从1开始，第0个返回给客端
{
current_obj = next_obj;
next_obj = (obj *)((char *)next_obj + n);
if (nobjs - 1 == i)
{
current_obj -> free_list_link = 0;
break;
}
else
{
current_obj -> free_list_link = next_obj;
}
}
return(result);
}
4.chunk_alloc()源码
template <bool threads, int inst>
__default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs)
{
char * result; //申请总量
size_t total_bytes = size * nobjs;
size_t bytes_left = end_free - start_free; //内存池剩余空间
if (bytes_left >= total_bytes)
{
//内存池剩余空间满足申请总量
result = start_free; //返回result
start_free += total_bytes; //内存池可用起始地址+=申请总量
return(result);
}
else if (bytes_left >= size)
{
//内存池剩余空间不足以满足申请总量，但是可以供应一个以上的区块
nobjs = bytes_left/size;//重新得到能够供应个数
total_bytes = size * nobjs;//重新计算总量
result = start_free;
start_free += total_bytes;
return(result);
}
else
{
//内存池剩余空间无法提供一个区块
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
//尝试用内存池中的残余零头
if (bytes_left > 0)
{
//内存池中还有一些零头，先配给适当的free list
//首先寻找适当的free list
obj * __VOLATILE * my_free_list = free_list + FREELIST_INDEX(bytes_left);
//调整free list，将内存池中的残余空间编入
((obj *)start_free) -> free_list_link = *my_free_list;
*my_free_list = (obj *)start_free;
}
//配置heap空间，用来补充内存池
start_free = (char *)malloc(bytes_to_get);
if (0 == start_free)
{
//heap空间不足，malloc()失败
int i;
obj * __VOLATILE * my_free_list, *p;
//以下搜索适当的free list
//适当是指"尚有未用区块，且区块够大"的free list
for (i = size; i <= __MAX_BYTES; i += __ALIGN)
{
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
//
if (0 != p) //free list中还有未用区块
{
//调整list free，释放未使用区块
//链表起始指向下一个区块
*my_free_list = p -> free_list_link;
//内存池开头指向这个区块
start_free = (char *)p;
//结尾指向区块结尾
end_free = start_free + i;
//再一次调用自身，修正nobjs
return(chunk_alloc(size, nobjs));
//任何残余零头最终都将被编入适当的free-list中备用
}
}
end_free = 0; //没办法没内存用了
//调用第一级配置器看看out-of-memory机制能否出点力
start_free = (char *)malloc_alloc::allocate(bytes_to_get);
//这会导致跑出异常exception，或内存不足的情况获得改善
}
heap_size += bytes_to_get;
//结束位置重新界定
end_free = start_free + bytes_to_get;
//递归调用，修正nobjs
return(chunk_alloc(size, nobjs));
}
}
内存池操作如下图：
资料：《STL源码剖析》