SGI 空间配置器

前言

空间配置器是 STL 六大组件之一，它总是隐藏在容器的背后，默默工作，默默付出。本文为《STL 源码剖析》读书笔记，主要讨论 SGI 版本空间的配置和释放，对代码进行解读时会改变一些写法，使其更易于阅读。

对象构造前的空间配置和对象析构后的空间释放，由 <stl_alloc.h> 负责，SGI 对此的设计哲学如下：

• 向系统堆申请空间
• 考虑多线程状态（本文不考虑多线程情况）
• 考虑内存不足时的应变措施
• 考虑小块内存过多造成的内存碎片问题

一级配置器

一级配置器并没有什么特殊的地方，就是调用 malloc() 和 free() 申请和释放内存。

__malloc_alloc_template 源码：

#if 0
#   include <new>
#   define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
#   include <iostream.h>
#   define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1)
#endiftemplate <int inst>
class __malloc_alloc_template {private:static void *oom_malloc(size_t);static void *oom_realloc(void *, size_t);#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUGstatic void (* __malloc_alloc_oom_handler)();
#endifpublic:static void * allocate(size_t n)
{void *result = malloc(n);if (0 == result) result = oom_malloc(n);return result;
}static void deallocate(void *p, size_t /* n */)
{free(p);
}static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
{void * result = realloc(p, new_sz);if (0 == result) result = oom_realloc(p, new_sz);return result;
}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#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template <int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
#endiftemplate <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);}
}typedef __malloc_alloc_template<0> malloc_alloc;

oom

什么是 oom（out of member）？

申请内存时，如果没有空闲的物理内存，那么内核就会开始进行回收内存的工作。如果内存回收后，空闲的物理内存仍然无法满足此次物理内存的申请，那么内核就会触发 OOM （Out of Memory）机制。

OOM 机制会根据算法选择一个占用物理内存较高的进程，然后将其杀死，以便释放内存资源，如果物理内存依然不足，OOM 会继续杀死占用物理内存较高的进程，直到释放足够的内存。

SGI 中的 __malloc_alloc_oom_handler 操作又是什么？

__malloc_alloc_oom_handler 指向内存不足时的处理函数，是 SGI 模仿 C++ 的 set_new_handler，因为没有使用 ::operator new 来分配内存，所以不能直接使用 set_new_handler。

一个设计良好的 new_handler 函数做以下事情：

• 让更多内存可以被使用
• 安装另一个 new_handler
• 卸载 new_handler
• 抛出 bad_alloc
• 不返回

SGI 中内存不足时调用 oom_malloc() 和 oom_realloc()，在它们内部不断调用「内存不足处理函数」，期望在某次调用后，就得到了足够的内存然后返回。但如果「内存不足处理函数」并没有被客户端设定，便会调用 __THROW_BAD_ALLOC，丢出异常信息并终止进程。

内存不足时的处理操作：

// 此处的条件编译一定会执行 elif 部分
// 最后尽力了也申请不到内存时，就打印错误语句，结束程序
#if 0
#   include <new>
#   define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
#   include <iostream.h>
#   define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1)
#endif// 成员变量，指向内存不足时的处理函数，初始值为空
static void (* __malloc_alloc_oom_handler)();// 参数为新设置的内存不足处理函数
// 返回值为旧的内存不足处理函数
static auto set_malloc_handler(void (*f)()) -> void (*)() {void (* old)() = __malloc_alloc_oom_handler;__malloc_alloc_oom_handler = f;return(old);
}// 该非类型模板参数没有用处
template <int inst>
void * __malloc_alloc_template<inst>::oom_malloc(size_t n) {void (* my_malloc_handler)();void *result;		// 指向申请到的内存while(true) {// 获取内存不足时的处理函数my_malloc_handler = __malloc_alloc_oom_handler;if (0 == my_malloc_handler) {	// 如果没有设置处理函数，终止进程__THROW_BAD_ALLOC; }(*my_malloc_handler)();			// 调用内存不足处理函数result = malloc(n);				// 再次尝试申请if (result != nullptr) {return(result);				// 申请成功返回}}
}template <int inst>
void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n) {void (* my_malloc_handler)();void *result;while(true) {// 获取内存不足时的处理函数my_malloc_handler = __malloc_alloc_oom_handler;if (0 == my_malloc_handler) {	// 如果没有设置处理函数，终止进程__THROW_BAD_ALLOC; }(*my_malloc_handler)();			// 调用内存不足处理函数result = realloc(p, n);			// 再次尝试申请if (result != nullptr) {return(result);				// 申请成功返回}}
}

申请内存

一级配置器申请内存直接调用 malloc() 和 realloc() 函数。

static void * allocate(size_t n) {void *result = malloc(n);if (0 == result) {result = oom_malloc(n);				// 申请失败时调用 oom_malloc}return result;
}static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz) {void * result = realloc(p, new_sz);if (0 == result) {result = oom_realloc(p, new_sz);	// 申请失败时调用 oom_realloc}return result;
}

释放内存

一级配置器释放内存直接调用 free() 函数。

// 第二个参数没有作用
static void deallocate(void *p, size_t /* n */) {free(p);
}

二级配置器

二级配置器就比一级配置器复杂的多，大于 128 字节的申请调用一级配置器，小于 128 字节的内存使用自由链表数组分配。整个二级配置器共享一个内存池，内存不足时从内存池获取。提供函数从下层获取内存，并向自由链表中填充内存。

自由链表如下，提供以 8 为倍数的小块内存，小块内存的头部 4/8 字节指向下一空闲节点。

__default_alloc_template 源码：

enum {__ALIGN = 8};
enum {__MAX_BYTES = 128};
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};template <bool threads, int inst>
class __default_alloc_template {private:static size_t ROUND_UP(size_t bytes) {return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1));}
private:union obj {union obj * free_list_link;char client_data[1];    /* The client sees this.        */};
private:static obj * volatile free_list[__NFREELISTS]; static  size_t FREELIST_INDEX(size_t bytes) {return (((bytes) + __ALIGN-1)/__ALIGN - 1);}static void *refill(size_t n);static char *chunk_alloc(size_t size, int &nobjs);// Chunk allocation state.static char *start_free;static char *end_free;static size_t heap_size;public:/* n must be > 0      */static void * allocate(size_t n){obj * volatile * my_free_list;obj * result;if (n > (size_t) __MAX_BYTES) {return(malloc_alloc::allocate(n));}my_free_list = free_list + FREELIST_INDEX(n);result = *my_free_list;if (result == 0) {void *r = refill(ROUND_UP(n));return r;}*my_free_list = result -> free_list_link;return (result);}/* p may not be 0 */static void deallocate(void *p, size_t n){obj *q = (obj *)p;obj * volatile * my_free_list;if (n > (size_t) __MAX_BYTES) {malloc_alloc::deallocate(p, n);return;}my_free_list = free_list + FREELIST_INDEX(n);q -> free_list_link = *my_free_list;*my_free_list = q;}static void* reallocate(void *p, size_t old_sz, size_t new_sz){void * result;size_t copy_sz;if (old_sz > (size_t) __MAX_BYTES && new_sz > (size_t) __MAX_BYTES) {return(realloc(p, new_sz));}if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return(p);result = allocate(new_sz);copy_sz = new_sz > old_sz? old_sz : new_sz;memcpy(result, p, copy_sz);deallocate(p, old_sz);return(result);}} ;template <bool threads, int inst>
char*
__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;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);// Try to make use of the left-over piece.if (bytes_left > 0) {obj * __VOLATILE * my_free_list =free_list + FREELIST_INDEX(bytes_left);((obj *)start_free) -> free_list_link = *my_free_list;*my_free_list = (obj *)start_free;}start_free = (char *)malloc(bytes_to_get);if (0 == start_free) {int i;obj * __VOLATILE * my_free_list, *p;// Try to make do with what we have.  That can't// hurt.  We do not try smaller requests, since that tends// to result in disaster on multi-process machines.for (i = size; i <= __MAX_BYTES; i += __ALIGN) {my_free_list = free_list + FREELIST_INDEX(i);p = *my_free_list;if (0 != p) {*my_free_list = p -> free_list_link;start_free = (char *)p;end_free = start_free + i;return(chunk_alloc(size, nobjs));// Any leftover piece will eventually make it to the// right free list.}}end_free = 0;	// In case of exception.start_free = (char *)malloc_alloc::allocate(bytes_to_get);// This should either throw an// exception or remedy the situation.  Thus we assume it// succeeded.}heap_size += bytes_to_get;end_free = start_free + bytes_to_get;return(chunk_alloc(size, nobjs));}
}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;if (1 == nobjs) return(chunk);my_free_list = free_list + FREELIST_INDEX(n);/* Build free list in chunk */result = (obj *)chunk;*my_free_list = next_obj = (obj *)(chunk + n);for (i = 1; ; i++) {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);
}template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::start_free = 0;template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::end_free = 0;template <bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;template <bool threads, int inst>
__default_alloc_template<threads, inst>::obj * __VOLATILE
__default_alloc_template<threads, inst> ::free_list[__NFREELISTS] = 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };

成员变量

enum {__ALIGN = 8};								// 对齐数
enum {__MAX_BYTES = 128};						// 可以申请的最大字节数
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};		// 自由链表个数static obj * volatile free_list[__NFREELISTS];	// 自由链表数组
static char *start_free;						// 内存池空间起始位置
static char *end_free;							// 内存池空间结束位置
static size_t heap_size;						// 多开辟的堆大小

还有一个比较特殊的成员，自由链表的节点结构。

该联合体从第一个字段看：它可以被视为一个指针，指向下一节点。从第二个字段看：它可以被视为一个指针，指向实际的数据空间。

实际上该联合体并没有实际的作用，只是为了便于理解。申请的一块内存，在没被使用的时候，可以用其头部 4/8 字节指向下一空闲节点，不用维护另外的指针。

union obj {union obj * free_list_link;char client_data[1];    /* The client sees this.        */
};

工具部分

这部分提供内存对齐，获取在自由链表数组中下标的函数。

因为自由链表中提供以 8 为倍数的小块内存，因此需要将申请的内存对齐为 8 的倍数。

static size_t ROUND_UP(size_t bytes) {// (bytes) + __ALIGN - 1 保证向对齐数进一位// ~(__ALIGN - 1) 去掉低位的 1return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1));
}

同时也需要知道对应大小在自由链表数组中的下标，以边获取内存和归还内存。

static  size_t FREELIST_INDEX(size_t bytes) {// - 1 因为数组的下标从零开始// 等于 ROUND_UP(bytes) / _ALIGN - 1// 因为低位的数在除对齐数后没有影响return (((bytes) + __ALIGN - 1) / __ALIGN - 1);
}

申请内存

申请内存时首先判断大小，大于 128 字节就调用一级配置器，小于 128 字节就去自由链表中获取，自由链表中没有内存就调用 refill() 填充内存。

static void * allocate(size_t n) {obj * volatile * my_free_list;	obj * result;					// 带回申请的内存// 大于 128 字节调用一级配置器if (n > (size_t) __MAX_BYTES) {return(malloc_alloc::allocate(n));}// 找到对应大小的自由链表my_free_list = free_list + FREELIST_INDEX(n);result = *my_free_list;if (result == 0) {// 自由链表中没有内存可用，为其填充内存void *r = refill(ROUND_UP(n));return r;}// 取出一个节点，调整 free_list 指向下一节点*my_free_list = result -> free_list_link;return (result);
}

释放内存

释放时同样需要先判断内存大小，大于 128 字节调用一级配置器释放，小于 128 字节还给自由链表。

// p 为要释放的首地址，n 为对象的大小
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;}// 找到要插入的位置my_free_list = free_list + FREELIST_INDEX(n);// 将节点头插进去q -> free_list_link = *my_free_list;*my_free_list = q;
}

填充自由链表

当申请内存时发现自由链表中没有可用内存后，就调用 refill()。refill() 的作用是为指定自由链表填充内存，新的内存从内存池中获取，默认情况下是填充 20 个节点，但万一内存池中内存不足，获取的节点可能小于 20 个。

template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n) {int nobjs = 20;							// 默认填充的个数// 从内存池获取内存，nobjs 为引用传参，带回实际申请到的个数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);}// 调整 my_free_list 指向，指向要添加节点的自由链表my_free_list = free_list + FREELIST_INDEX(n);// 需要将多余的节点插入到自由链表中// 获取第一个节点，后续返回使用result = (obj *)chunk;// + n 指向第二个节点*my_free_list = (obj *)(chunk + n);next_obj = (obj *)(chunk + n);for (i = 1; ; ++i) {// 分别指向当前节点、下一节点current_obj = next_obj;// (char *)next_obj + n 取一个节点的大小next_obj = (obj *)((char *)next_obj + n);// 一共申请了 nobjs 个节点，需要插入 n - 1 个if (nobjs - 1 == i) {// 将最后一个插入的节点置空current_obj -> free_list_link = 0;break;} else {// 采用尾插的方式current_obj -> free_list_link = next_obj;}}return(result);
}

内存池

chunk_alloc() 首先检查内存池中是否有内存可用，如果没有就尝试调用 malloc() 申请内存，申请失败就去更大节点的自由链表中寻找内存。如果经过上述艰难的过程，还是没有获取到内存的话，就会调用一级配置器，祈祷「内存不足处理函数」有所作用。

template <bool threads, int inst>
char* __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;start_free += total_bytes;	// 将 start 向后移，表示内存已被使用return(result);} else if (bytes_left >= size) {// 内存池剩余空间不能满足要求，但足够一个以上的节点nobjs = bytes_left/size;	// 能带回的节点个数total_bytes = size * nobjs;	// 申请到的字节数result = start_free;start_free += total_bytes;	// 调整 startreturn(result);} else {// 内存池剩余空间连一个节点也不能满足// 申请成功后后取走 total_bytes 字节，剩余部分留在内存池size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);if (bytes_left > 0) {// 内存池中还有剩余内存，把它分配到合适的自由链表中// 申请是 8 的倍数，使用也是 8 的倍数，因此可以找到合适的位置obj * volatile * my_free_list = free_list + FREELIST_INDEX(bytes_left);((obj *)start_free) -> free_list_link = *my_free_list;*my_free_list = (obj *)start_free;}// 调用 malloc 向堆申请内存start_free = (char *)malloc(bytes_to_get);if (0 == start_free) {// 申请内存失败int i;obj * volatile * my_free_list, *p;for (i = size; i <= __MAX_BYTES; i += __ALIGN) {// 检查配有更大节点的自由链表是否有空间可用// 例如 32 字节自由链表没有内存可用，可以去 40、48 等自由链表查看my_free_list = free_list + FREELIST_INDEX(i);p = *my_free_list;if (0 != p) {// 更大的自由链表中有内存可用*my_free_list = p -> free_list_link;	// 弹出一个节点start_free = (char *)p;					// 将弹出的节点放入内存池中end_free = start_free + i;				// 调整内存池大小return(chunk_alloc(size, nobjs));		// 此时已经有内存了，递归调用自己获取}}// 此时内存池没有内存，malloc 失败，也没有更大的可用节点// 尝试调用一级配置器，看内存不足处理函数是否有办法end_free = 0;start_free = (char *)malloc_alloc::allocate(bytes_to_get);} // end of if (0 == start_free)heap_size += bytes_to_get;				// 随着次数而增大，不太理解含义end_free = start_free + bytes_to_get;	// 调整内存池大小return(chunk_alloc(size, nobjs));		// 此时已经有内存了，递归调用自己获取} // end of if (bytes_left >= total_bytes)
}