上节在学习第二级配置器时了解了第二级配置器通过内存池与*链表来处理小区块内存的申请。但只是对其概念进行点到为止的认识，并未深入探究。这节就来学习一下*链表的填充和内存池的内存分配机制。
refill()函数——重新填充*链表
前情提要，从上节第二级配置器的源码中可以看到，在空间配置函数allocate()中，当所需的某号*链表为空时，才会调用refill()函数来填充链表。refill()函数默认申请20块区块的内存（5行），但所得内存不一定就是20块，要看当前内存池的剩余情况和堆容量的情况，这个在学习chunk_alloc()函数时会详解讨论，然后将第零块返回给allocate()函数，allocate()函数再返回给真正申请内存的用户，剩余内存分成区块串接成*链表。
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n)
{
int nobjs = ; //需要填充*链表时，尝试分配20个区块作为*链表的新结点
char * chunk = chunk_alloc(n, nobjs); //交给chunk_alloc去分配内存，后述
obj * __VOLATILE * my_free_list;
obj * result;
obj * current_obj, * next_obj;
int i;
if ( == nobjs) return(chunk); //如果只分配到1个区块，则直接返回给申请者，*链表无新结点
my_free_list = free_list + FREELIST_INDEX(n);
/* Build free list in chunk */
result = (obj *)chunk; //如果分配到大于1个区块，即将第0个区块返回给申请者，剩下的作为*链表的空闲区块
*my_free_list = next_obj = (obj *)(chunk + n); //从新分配内存的第一个区块开始串接成*链表
for (i = ; ; i++) {
current_obj = next_obj;
next_obj = (obj *)((char *)next_obj + n);
if (nobjs - == i) {
current_obj -> free_list_link = ;
break;
} else {
current_obj -> free_list_link = next_obj;
}
}
return(result);
}
chunk_alloc()函数——内存池
其实内存池仅仅是靠三个静态成员变量来管理的，并没有多复杂的机制：
static char *start_free; //内存池起始指针
static char *end_free; //内存池的尾指针
static size_t heap_size; //多次调用内存池, 就会在内存池中分配更多的内存, 这就是一个增量.
这在上节的第二级配置器源码中也有提到。真正复杂的是为内存池的分配内存和*链表与内存池的交互上，这两个在chunk_alloc()上有所体现。
template <bool threads, int inst>
char*
__default_alloc_template<threads, inst>::chunk_alloc(size_t size, int&
nobjs) //注意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 = * total_bytes + ROUND_UP(heap_size >> );
// 如果当前内存池要有剩余，寻找哪号*链表能收了它.
if (bytes_left > ) {
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 ( == start_free) { //堆空间也不足了，malloc()失败
int i;
obj * __VOLATILE * my_free_list, *p;
//尝试查看更大号的*链表中是否有1个空闲块能供我们使用
for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if ( != p) { //如果有，把它从*链表中划进内存池，并返回递归调用chunk_alloc()函数的结果，修正nobjs
*my_free_list = p->free_list_link;
start_free = (char *)p;
end_free = start_free + i;
return(chunk_alloc(size, nobjs)); //在递归调用chunk_alloc后，会发现内存池拥有了大于1个区块的内存了，可以把该区块返回给refill()函数
}
}
//堆空间没内存，其它*链表也没内存，山穷水尽
end_free = ;
start_free = (char *)malloc_alloc::allocate(bytes_to_get); //调用第一级配置器，期望out-of-memory机制能否尽点力
}
heap_size += bytes_to_get; //记录内存池已经开辟的堆大小
end_free = start_free + bytes_to_get;
return(chunk_alloc(size, nobjs));
}
}
总结上述源码的功能，以end_free - start_free来判断内存池大小是否足够，如果充足则直接调出20个区块返回给*链表。如果不足20个区块但还足够供应一个以上的区块，就拔出这不足20个区块的空间出去。这时pass by reference的nobjs将被修改为实际能够供应的区块数。如果内存池连一个区块空间都无法提供，此时便需利用malloc()，从堆中配置内存，为内存池注入足够的内存以应付需求，这足够的内存（22行）是指需求量的两倍再加上随着配置次数增加而越来越大的附加量（heap_size），如果能通过malloc()申请到40块内存，就将第前20块给*链表，后20块放进内存池备用。
举个实际的例子，让我们对这段源码有更深刻的认识：假设程序一开始，客端调用chunk_alloc(32, 20)，于是malloc()配置40个32bytes区块，其中第一个交出，另外19个交给free_list[3]维护，剩余的20个留给内存池。接下来客端调用chunk_alloc(64, 20)，此时free_list[7]空空如也，必须向内存池要求支持。内存池只够供应(32*60)/64=10个64bytes区块，就把这10个区块返回，第1个交给客端，余下交由free_list[7]维护。此时内存池空空如也。再调用chunk_alloc(96, 20)，free_list[11]也空空如也，必须向内存池要求支持，而内存池表示爱莫能助，只能再向堆申请40+n个96bytes区块的内存，其中第1个交出，另外19个交给free_list[11]维护，余20+n个区块留给内存池......
万一真的山穷水尽，整个堆空间都不够了，malloc()失败，chunk_alloc()就四处寻找有无“有未用且足够大区块”的*链表。找到了就挖一块交出，找不到就调用第一级配置器。第一级配置器也使用malloc()来配置内存，但它有out-of-memory处理机制，或许有机会释放其它内存拿来此处使用。如果可以就成功，不可以就发出bad_alloc异常。