复习SGI STL二级空间配置器（内存池） | 笔记自用

在以前学习C++的时，写过一些剖析STL空间配置器的文章，如今回头再看一遍，想着复习一下。

SGI STL空间配置器： 【该目录中查看】

SGI STL包含了一级空间配置器和二级空间配置器，其中一级空间配置器allocator采用malloc和free来管理内存，和C++标准库中提供的allocator是一样的，但其二级空间配置器allocator采用了基于freelist自由链表原理的内存池机制实现内存管理。

• 前言
• 空间配置器相关定义
• 重要类型和变量定义
• 两个重要辅助接口函数
• 内存池管理函数
• 该内存池的优点

template 
class vector : protected _Vector_base<_Tp, _Alloc>

容器的默认空间配置器是__STL_DEFAULT_ALLOCATOR( _Tp)，它是一个宏定义，如下：

# ifndef __STL_DEFAULT_ALLOCATOR
# ifdef __STL_USE_STD_ALLOCATORS
# define __STL_DEFAULT_ALLOCATOR(T) allocator< T >
# else
# define __STL_DEFAULT_ALLOCATOR(T) alloc
# endif
# endif

从上面可以看到__STL_DEFAULT_ALLOCATOR通过宏控制有两种实现，一种是allocator< T >，另一种是alloc，这两种分别就是SGI STL的一级空间配置器和二级空间配置器的实现。

根据英文意思，默认的空间配置器就是二级配置器，申请大于128字节的内存块就交给第一级配置器。。。。

template 
class __malloc_alloc_template // 一级空间配置器内存管理类 -- 通过malloc和free管理内存

template 
class __default_alloc_template { // 二级空间配置器内存管理类 -- 通过自定义内存池实现内存管理

先是三个枚举量，表示粒度信息

// 内存池的粒度信息
enum {_ALIGN = 8}; // 8的倍数递增
enum {_MAX_BYTES = 128}; // 分配的最大字节数128
enum {_NFREELISTS = 16}; // 自由链表个数（数组长度）

这个是每个内存chunk块的信息，实际上可当作链表，这个_M_free_list_link相当于next域。

// 每一个内存chunk块的头信息
union _Obj {
	union _Obj* _M_free_list_link;
	char _M_client_data[1]; 
};

这个指针数组就是维护16个自由链表，先记住数组名（_S_free_list）

// 组织所有自由链表的数组，数组的每一个元素的类型是_Obj*，全部初始化为0
static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS];

这三个静态变量是维护内存池（向堆区申请的）。前两个指针变量，表示内存池的开始位置和结束位置，而heap_size表示向堆区申请的字节总数。先将他们全初始化为0。

// Chunk allocation state. 记录内存chunk块的分配情况
static char* _S_start_free;
static char* _S_end_free;
static size_t _S_heap_size;

template 
char* __default_alloc_template<__threads, __inst>::_S_start_free = 0;
template 
char* __default_alloc_template<__threads, __inst>::_S_end_free = 0;
template 
size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;

1. ROUND_UP

意义是将客户端想要申请的字节数上调到8的倍数。比如申请9各字节，就上调到16个字节；申请20字节，就上调到24个字节。原理是位操作。

static size_t _S_round_up(size_t __bytes) { 
	return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); 
}

示例：申请9字节
那这个就可看成下面的二进制：进行位与后就变成了 16

00000000 00000000 00000000 00010000
1111 1111 1111 1111 1111 1111 1111 1000

2. FREELIST_INDEX

意思是找到要去申请的具体的自由链表。下标从0开始，所以用的 '/'运算符。

static size_t _S_freelist_index(size_t __bytes) {
	return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
 }

个人感觉最关键最不好理解的就是 chunk_alloc()函数，需要多画图，走几遍流程。

// 分配内存的入口函数
static void* allocate(size_t __n);

// 负责把分配好的chunk块进行连接，添加到自由链表当中
static void* _S_refill(size_t __n);

// 分配相应内存字节大小的chunk块，并且给下面三个成员变量初始化
static char* _S_chunk_alloc(size_t __size, int& __nobjs);

// 把chunk块归还到内存池
static void deallocate(void* __p, size_t __n);

// 内存池扩容函数
template 
void*
__default_alloc_template::reallocate(void* __p,
											size_t __old_sz,
											size_t __new_sz);

1. 对于每一个字节数的chunk块分配，都是给出一部分进行使用，另一部分作为备用，这个备用可以给当前字节数使用，也可以给其它字节数使用。

2. 对于备用内存池划分完chunk块以后，如果还有剩余的很小的内存块，再次分配的时候，会把这些小的内存块再次分配出去，备用内存池使用的干干净净!

3. 当指定字节数内存分配失败以后，有一个异常处理的过程，bytes - 128字节所有的chunk块进行查看，如果哪个字节数有空闲的chunk块，直接借一个出去

4. 如果上面的操作失败，还会调用 _oom_malloc这个提前设置好的malloc内存分配失败的回调函数，
   如果没设置就会抛出异常（throw_bad_alloc)
   如果设置了，就会启动一个无限循环 for(; ; )，一直调用(*oom_malloc_handler)();函数，完了后继续调用malloc()。。。