考虑到小型区块所可能造成的内存破碎问题，SGI 设计了双层级配置器，这里则学习第二级配置器，第二级配置器的设计思想为：
- 如果配置区块超过128 bytes，则移交给第一级配置器处理；
- 如果配置区块小于128 bytes，则采用内存池管理（memory pool）。每次配置一大块内存，则维护对应的自由链表（free-list），下次若再有相同大小的内存需求，就直接从 free-list 中拨出（没有就继续配置内存，具体后面讲述），如果客端释换小额区块，就有配置器回收到 free-list 中。
需要说明的是：本系列引用的STL源码版本为 v3.3，对比版本 v2.03 风格上有了些许变化，但设计思想还是不变的。
1
2
3
4
5
6
7
8
9
|
enum { _ALIGN = 8 };
enum { _MAX_BYTES = 128 };
enum { _NFREELISTS = 16 };
union _Obj {
union _Obj* _M_free_list_link;
char _M_client_data[1];
};
|
考虑内存对其等因素，SGI 第二级配置器会主动将任何小额区块的内存需求量上调至 8 的倍数。并维护 16 个 free-list，各自管理大小分别为 8，16，24，32，40，48，56，64，72，80，88，96，104，112，120，128 bytes 的小额区块。
union _Obj 中的 Mclient_data 是C/C++中常见的变长数组实现方式（如果编译器支持 0 长度的数组，还可以声明为 Mclient_data[0] 达到更节省的目的），所以 union _Obj 的大小就是一个指针大小（Mfree_list_link 指针的大小）。union 实现一物二用，这个free-list 有两个作用：一个是指向下一块空白内存（当存在于 free-list 中时），一个就是供用户使用的一块内存（不存在于 free-list）。
回顾第二级配置器的设计思想的第 2 点，内存空间的分配大致是这样的：\配置器分配空间时，先从 free-list 中拨出，如果有，就直接拨出，该需求大小的区块位于 free-list 对应编号的第一位置，然后从该链表中拨出，这样该区块就不位于 free-list 中对应编号内，第一位置向后移动指向，仅此一区块(刚已经拨出去)，则指向 0 ，表示 free-list 中没有该大小的区块；如果没有则需要向 free-list 填补区块，继而转向内存块分配函数，然后分配所需大小的新区块(一次性缺省分配20个，不够就分配小于20的，至少一个)，分配成功后，第一个区块直接划给客端，然后后面的（如果有）就填进 free-list，这样下次再有相同大小的内存需求时，可直接从 free-list 中拨出，如果一个区块都分配不出，就转向调用第一级配置器里的内存分配异常处理例程。 配置器还可以回收释放的内存，释还的小额内存区块划进 free-list 中（其实是关联到 free-list 对应编号区域）。
**
SGI 缺省的 free-list 中都是0值，也就是说该链表中没有可用的小额区块，因为不可能 SGI STL 一开始就自动的给你分配出来（它知道你要多少呀）。
1
2
3
4
5
|
template <bool __threads, int __inst>
__default_alloc_template<__threads, __inst>::_Obj* volatile
__default_alloc_template<__threads, __inst> ::_S_free_list[_NFREELISTS] =
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
|
最开始只要需求小额区块内存，就会转到内存块分配函数。这样一来，相当于 free-list 是用来分配内存的，底层分配内存时，一次性分配一定数量的该额度区块（实际上是一次性分配大块内存，然后“分割”成小块），这样下次需求的时候直接从 free-list 中获取，而不用频繁的分配小额内存块，减少了内存碎片的产生，也提高了效率。
下面我们跟踪源码，来看看其内部是如何来实现这种机制的。
1
2
3
4
5
6
7
8
9
10
|
static size_t
_S_round_up(size_t __bytes)
{
return (((__bytes)+(size_t)_ALIGN - 1) & ~((size_t)_ALIGN - 1));
}
static size_t _S_freelist_index(size_t __bytes) {
return (((__bytes)+(size_t)_ALIGN - 1) / (size_t)_ALIGN - 1);
}
|
先看 allocate()，然后穿针引线。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| static void* allocate(size_t __n)
{
void* __ret = 0;
if (__n > (size_t)_MAX_BYTES) {
__ret = malloc_alloc::allocate(__n);
}
else {
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);
# ifndef _NOTHREADS
_Lock __lock_instance;
# endif
_Obj* __RESTRICT __result = *__my_free_list;
if (__result == 0)
__ret = _S_refill(_S_round_up(__n));
else {
*__my_free_list = __result->_M_free_list_link;
__ret = __result;
}
}
return __ret;
};
|
区块自 free-list 拨出的操作（下面这个数据结构类似于链式哈希表），如下图所示（图片源自《STL源码剖析》）
%20%E7%AC%AC%E4%BA%8C%E7%BA%A7%E9%85%8D%E7%BD%AE%E5%99%A8/20140221155259531)
如果 free-list 中没有对应大小的区块，就转去调用 Srefill()。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
int __nobjs = 20;
char* __chunk = _S_chunk_alloc(__n, __nobjs);
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
int __i;
if (1 == __nobjs) return(__chunk);
__my_free_list = _S_free_list + _S_freelist_index(__n);
__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->_M_free_list_link = 0;
break;
}
else {
__current_obj->_M_free_list_link = __next_obj;
}
}
return(__result);
}
|
这样将把第一块返回给客端的剩余 “大块”内存 “分割” 成指定大小的区块，并填进 free-list 中。新的区块取自内存池，由 Schunk_alloc() 完成。
这个函数的具体实现思想为：
1、内存池剩余空间完全满足 20 个区块的需求量，则直接取出对应大小的空间；
2、内存池剩余空间不能完全满足 20 个区块的需求量，但可以提供一个及以上的区块，
则取出能够满足需求区块的最大个数的空间；
3、内存池剩余空间不能满足一个需求区块的大小，则进行以下处理：
\1. 首先判池中是否存在残余零头的内存空间，如果有则进行回收，将其划入 free-list 中的适当位置；
\2. 然后向 system heap 申请空间，补充内存池。
2.1 若 heap 空间充足，则空间分配成功；
2.2 若 heap 空间不足，出现 malloc() 调用失败。
则搜寻适当的 free-list （适当是指 “尚有未有区块，且区块较大” 的 free-list ），
即搜寻 free-list 大于等于需求块的区块，将其编入内存池，然后递归调用 Schunk_alloc()
函数从内存池中取空间重复上述过程。如果很不幸，free-list 中没有合适的内存空间可用了，
这时候则调用第一级配置器，利用 out-of-memory 机制尝试解决内存不足问题，
结果要么内存不足的情况获得改善，要么抛出 bad_alloc 异常。
接下来直接看源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| static char* _S_start_free;
static char* _S_end_free;
static size_t _S_heap_size;
template <bool __threads, int __inst>
char*__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size,
int& __nobjs)
{
char* __result;
size_t __total_bytes = __size * __nobjs;
size_t __bytes_left = _S_end_free - _S_start_free;
if (__bytes_left >= __total_bytes) {
__result = _S_start_free;
_S_start_free += __total_bytes;
}
else if (__bytes_left >= __size) {
__nobjs = (int)(__bytes_left / __size);
__total_bytes = __size * __nobjs;
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
}
else {
size_t __bytes_to_get =
2 * __total_bytes + _S_round_up(_S_heap_size >> 4); /
if (__bytes_left > 0) {
_Obj* __STL_VOLATILE* __my_free_list =
_S_free_list + _S_freelist_index(__bytes_left);
((_Obj*)_S_start_free)->_M_free_list_link = *__my_free_list;
*__my_free_list = (_Obj*)_S_start_free;
}
_S_start_free = (char*)malloc(__bytes_to_get);
if (0 == _S_start_free) {
size_t __i;
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __p;
for (__i = __size;
__i <= (size_t)_MAX_BYTES;
__i += (size_t)_ALIGN) {
__my_free_list = _S_free_list + _S_freelist_index(__i);
__p = *__my_free_list;
if (0 != __p) {
*__my_free_list = __p->_M_free_list_link;
_S_start_free = (char*)__p;
_S_end_free = _S_start_free + __i;
return(_S_chunk_alloc(__size, __nobjs));
}
}
_S_end_free = 0;
_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
}
_S_heap_size += __bytes_to_get;
_S_end_free = _S_start_free + __bytes_to_get;
return(_S_chunk_alloc(__size, __nobjs));
}
}
|
这里补充一下内存池的概念：内存池是在真正使用内存之前，先申请分配一定数量的、大小相等(一般情况下)的内存块留作备用。当有新的内存需求时，就从内存池中分出一部分内存块，若内存块不够再继续申请新的内存。这样，内存池允许在运行期以常数时间规划内存块，并且尽量避免了内存破碎的情况产生，使得内存分配的效率得到提升。
内存池实际操练结果如下图：
%20%E7%AC%AC%E4%BA%8C%E7%BA%A7%E9%85%8D%E7%BD%AE%E5%99%A8/20140221191442375)
如上图，加入程序一开始，客端就调用 Schunk_alloc(32, 20)，于是 malloc() 配置 40 个 32 bytes 区块，其中第 1 个返回给客端，另 19 个交给 Sfree_list [3] 维护，余 20 个留给内存池。接下来客端调用 Schunk_alloc(64, 20)，此时 Sfree_list [7] 是空的，必须向内存池要求空间，内存池只够供应 (32 * 20) / 64 = 10 个 64 bytes 区块，就把这 10 个区块返回，第 1 个交给客端，余 9 个由 Sfree_list [7] 维护，此时内存池全空，接下来再调用 Schunk_alloc(96, 20)，此时 Sfree_list [11] 空空如也，必须向内存池要求支持，而内存池此时也是空的，于是以 malloc() 配置 40 + n（附加量）个 96 bytes 区块，其中第 1 个交出，另 19 个交给 Sfree_list [11] 维护，余 20 + n 个区块留给内存池……
如果到最后，整个 system heap 空间都不够了，malloc() 分配失败，Schunk_alloc() 就四处寻找有无 “尚有未用区块，且足够大” 的 free-list。找到了就挖一块交出，找不到就调用第一级配置器，第一级其实也是调用 malloc() 来配置内存，但它有 out-of-memory 处理机制，或许有机会释放其它的内存拿来此处使用。如果可以，就成功，否则发出 bad_alloc 异常。
配置器自然也有释放空间的能力，这里再学习空间释放函数 deallocate()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
static void deallocate(void* __p, size_t __n)
{
if (__n > (size_t)_MAX_BYTES)
malloc_alloc::deallocate(__p, __n);
else {
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);
_Obj* __q = (_Obj*)__p;
# ifndef _NOTHREADS
_Lock __lock_instance;
# endif
__q->_M_free_list_link = *__my_free_list;
*__my_free_list = __q;
}
}
|
区块回收纳入 free-list 的操作（序号对应顺序），如下图所示
%20%E7%AC%AC%E4%BA%8C%E7%BA%A7%E9%85%8D%E7%BD%AE%E5%99%A8/20140221201652625)