剖析SGI STL空间配置器（核心设计：_S_chunk_alloc函数）

_S_chunk_alloc函数是chunk内存块的内存源头。当申请某个自由链表结点下的chunk块不足时，就会调用_S_refill函数来补充chunk块，而填充内存的来源，就是通过_S_chunk_alloc函数申请的。
_S_chunk_alloc函数的设计可以说是二级空间配置器最精妙的设计了。来看它的定义：

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;
        return(__result);
    } 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);
        // Try to make use of the left-over piece.
        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;
            // 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 <= (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));
                    // Any leftover piece will eventually make it to the
                    // right free list.
                }
            }
	    _S_end_free = 0;	// In case of exception.
            _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
            // This should either throw an
            // exception or remedy the situation.  Thus we assume it
            // succeeded.
        }
        _S_heap_size += __bytes_to_get;
        _S_end_free = _S_start_free + __bytes_to_get;
        return(_S_chunk_alloc(__size, __nobjs));
    }
}
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
62
63

_S_chunk_alloc函数的参数分别是申请内存chunk块的大小__size和需要的块数__nobjs。
首先做的就是计算申请内存块的总大小：size_t __total_bytes = __size * __nobjs;。

size_t __bytes_left = _S_end_free - _S_start_free; 是计算备用池的大小。备用池就是一块完整的、没有被切成chunk块的一块内存空间，_S_start_free和_S_end_free 维护的是这块内存的起始地址和末尾地址。
下面逐个条件对这个函数进行分析：

备用池满足20个块的申请

__bytes_left >= __total_bytes 条件为真，说明备用池已有的空间满足申请内存的大小，这样我们就可以直接把备用池的起始地址返回给__S_refill函数使用，在把_S_start_free维护的备用池做相应的调整就好。
比如我们要申请chunk块大小为8，块数为20的内存块也就是160字节，而我们的备用池内存的大小_S_end_free - _S_start_free 有320字节，我们只需要保存_S_start_free的值返回，在把_S_start_free偏移160个字节即可完成内存申请。过程如下图：

备用池不够20块，但至少满足1块

备用池虽然不满足默认申请的20块，但大于一块的情况下，_S_chunk_alloc函数会把备用池能分的最大块数给分配出去，修改引用传进来的__nobjs，然后再调整维护备用池的_S_start_free指针即可。
假设备用池还有160字节大小的内存，_S_refill函数需要24字节大小的chunk块，大体步骤如下图：

备用池不足一块（核心设计）

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;	// In case of exception.
            _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));
    }
}
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

备用池不足以分出一个chunk块时，就需要malloc从堆申请内存了。申请的大小是chunk块的40块加上上次填备用池大小_S_heap_size >>4。
假设_S_chunk_alloc的请求是按下面的顺序调用的：

1. 第一次要申请大小为8的chunk块，内存池初始为空，则需要申请2*8*20 + _S_round_up(_S_heap_size >>4)=320个字节，然后根据上面的分析，会分出去160字节，备用池还有160字节；
2. 第二次申请24字节的chunk块，分出去160/24*24=144字节，备用池还剩16字节；
3. 第三次申请40字节的chunk块，备用池剩的16字节已经不足以分出一个chunk块了，这时就需要申请2*40*20+_S_round_up(_S_heap_size >>4) = 800 + _S_round_up(20) = 824字节了

可以很容易推出，两次在同一个chunk大小的结点都需要补充备用池的时候，备用池是越申请越大的。
在第三步需要填备用池时，还剩出16字节的内存没有被分出去，_S_chunk_alloc函数并没有丢弃这块内存，而是把这块内存串到了对应大小的自由链表_S_free_list结点下，没有浪费一点内存。

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;
        }
1
2
3
4
5
6
7

剩余的内存处理完后，就是malloc从堆申请内存了。如果malloc申请成功，调整_S_start_free，_S_end_free,_S_heap_size的值，递归调用_S_chunk_alloc，就会进入第一个判断条件处理返回结果了。

但malloc是有申请失败的可能的！
malloc失败时，_S_chunk_alloc的处理过程很值得学习。

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;	// In case of exception.
            _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

首先会依次遍历存储比该chunk块大的自由链表_S_free_list结点，看有没有比当前chunk块大的空闲chunk块，如果存在：

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));
}
1
2
3
4
5
6

把_S_start_free 和_S_end_free 指向这块空闲chunk块的起始地址和末尾地址，然后递归调用_S_chunk_alloc，这时候_S_end_free -_S_start_free 的值，是绝对比申请chunk块大小__size大的，就会进入第二个判断条件处理返回结果了。

如果还是没有可用的内存块呢？ SGI STL二级空间配置器的异常处理还能挣扎一下！回去调用_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);这个函数，我们找到这个函数的定义：

malloc_alloc::allocate首先会再尝试malloc申请，如果还是申请失败，就会调用_S_oom_malloc函数，其定义如下：

_S_oom_malloc函数会定义一个函数指针void (* __my_malloc_handler)();，检查用户有没有事先注册一个释放内存的回调函数。
如果没有注册，则会抛出__THROW_BAD_ALLOC;的异常处理；
如果注册了，就会执行这个函数释放资源，如果释放了资源再malloc申请，就有可能申请成功。
如果注册的函数没有释放资源或释放的资源不足malloc成功，程序就会陷入死循环，直到申请成功为止。