STL-內存的配置與釋放

STL有兩級空間配置器，默認是使用第二級。第二級空間配置器會在某些情況下去調用第一級空間配置器。空間配置器都是在allocate函數內分配內存，在deallocate函數內釋放內存。

第一級空間配置器

第一級配置器只是對malloc函數和free函數的簡單封裝，在allocate內調用malloc，在deallocate內調用free。同時第一級配置器的oom_malloc函數，用來處理malloc失敗的情況。如下所示：

allocate對malloc函數簡單封裝 :

static void *allocate(size_t n)
{void *result = malloc(n);if (NULL == result)result = oom_malloc(n);return result;
}

deallocate對free函數簡單封裝 :

static void deallocate(void *p, size_t) { free(p); }

oom_malloc調用外部提供的malloc失敗處理函數，然后重新試著再次調用malloc。重復執行此過程，直到malloc成功為止 :

template <int inst>
void* __malloc_alloc<inst>::oom_malloc(size_t n)
{void (*my_malloc_handler)();void *result;for (;;){my_malloc_handler = malloc_alloc_oom_handler;if (NULL == my_malloc_handler)__THROW_BAD_ALLOC;(*my_malloc_handler)();result = malloc(n);if (result)return result;}
}

第二級空間配置器

第一級配置器直接調用malloc和free帶來了幾個問題：

1. 內存分配/釋放的效率低。

2. 當配置大量的小內存塊時，會導致內存碎片比較嚴重。

3. 配置內存時，需要額外的部分空間存儲內存塊信息，所以配置大量的小內存塊時，還會導致額外內存負擔。

第二級配置器維護了一個自由鏈表數組，每次需要分配內存時，直接從相應的鏈表上取出一個內存節點就完成工作，效率很高。

自由鏈表數組

自由鏈表數組其實就是個指針數組，數組中的每個指針元素指向一個鏈表的起始節點。數組大小為16，即維護了16個鏈表，鏈表的每個節點就是實際的內存塊，相同鏈表上的內存塊大小都相同，不同鏈表的內存塊大小不同，從8一直到128。如下所示，obj為鏈表上的節點，free_list就是鏈表數組。

//自由鏈表
union obj
{union obj *free_list_link;char data[1];
};
//自由鏈表數組
static obj *volatile free_list[__NFREELISTS];

內存分配

allocate函數內先判斷要分配的內存大小，若大于128字節，直接調用第一級配置器，否則根據要分配的內存大小從16個鏈表中選出一個鏈表，取出該鏈表的第一個節點。若相應的鏈表為空，則調用refill函數填充該鏈表。如下：

template <bool threads>
void *__default_alloc<threads>::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 == NULL){//第n號鏈表無內存塊，則準備重新填充該鏈表void *r = refill(ROUND_UP(n));return r;}*my_free_list = result->free_list_link;return result;
}

填充鏈表

若allocate函數內要取出節點的鏈表為空，則會調用refill函數填充該鏈表。

refill函數內會先調用chunk_alloc函數從內存池分配一大塊內存，該內存大小默認為20個鏈表節點大小，當內存池的內存也不足時，返回的內存塊節點數目會不足20個。接著refill的工作就是將這一大塊內存分成20份相同大小的內存塊，并將各內存塊連接起來形成一個鏈表。如下：

template <bool threads>
void *__default_alloc<threads>::refill(size_t n)
{int nobjs = __NOBJS;char *chunk = chunk_alloc(n, nobjs);  //從內存池獲取內存if (nobjs == 1)  //只能分配一塊，則直接返回給調用者return chunk;obj *volatile *my_free_list;obj *result, *next_obj, *current_obj;result = (obj *)chunk;my_free_list = free_list + FREELIST_INDEX(n);*my_free_list = next_obj = (obj *)(chunk + n);for (int i = 1; i < nobjs - 1; i++)  //將剩下的區塊添加進鏈表{current_obj = next_obj;next_obj = (obj *)(char *)(next_obj + n);current_obj->free_list_link = next_obj;}//最后一塊current_obj = next_obj;current_obj->free_list_link = NULL;return result;
}

內存池

chunk_alloc函數內管理了一塊內存池，當refill函數要填充鏈表時，就會調用chunk_alloc函數，從內存池取出相應的內存。

在chunk_alloc函數內首先判斷內存池大小是否足夠填充一個有20個節點的鏈表，若內存池足夠大，則直接返回20個內存節點大小的內存塊給refill。如下：

        if (size_left >= total_size)  //內存池剩余空間滿足需求{result = start_free;start_free += total_size;return result;}

若內存池大小無法滿足20個內存節點的大小，但至少滿足1個內存節點，則直接返回相應的內存節點大小的內存塊給refill；

        else if (size_left >= size)  //剩余空間不能全部滿足，但至少滿足一塊{nobjs = size_left / size;result = start_free;start_free += nobjs * size;return result;}

若內存池連1個內存節點大小的內存塊都無法提供，則chunk_alloc函數會將內存池中那一點點的內存大小分配給其他合適的鏈表，然后去調用malloc函數分配的內存大小為所需的兩倍。若malloc成功，則返回相應的內存大小給refill；若malloc失敗，會先搜尋其他鏈表的可用的內存塊，添加到內存池，然后遞歸調用chunk_alloc函數來分配內存，若其他鏈表也無內存塊可用，則只能調用第一級空間配置器，因為第一級空間配置器有malloc失敗的出錯處理函數，最終的希望只能寄托在那里了。

如下是整個chunk_alloc函數：

template <bool threads>
char *__default_alloc<threads>::chunk_alloc(size_t size, int& nobjs)
{size_t total_size = size * nobjs;char *result;size_t size_left = end_free - start_free;if (size_left >= total_size)  //內存池剩余空間滿足需求{result = start_free;start_free += total_size;return result;}else if (size_left >= size)  //剩余空間不能全部滿足，但至少滿足一塊{nobjs = size_left / size;result = start_free;start_free += nobjs * size;return result;}else  //連一個區塊都無法滿足{if (size_left > 0)  //將殘余內存分配給其他合適的鏈表{obj *volatile *my_free_list = free_list + FREELIST_INDEX(size_left);((obj *)start_free)->free_list_link = *my_free_list;  //在頭部插入*my_free_list = (obj *)start_free;}size_t bytes_to_get = 2 * total_size + ROUND_UP(heap_size >> 4);start_free = (char *)malloc(bytes_to_get);if (start_free == NULL)  //堆空間不足{int i;obj *volatile *my_free_list;obj *p;for (i = size; i < __MAX_BYTES; i++){my_free_list = free_list + FREELIST_INDEX(i);p = *my_free_list;if (p != NULL){*my_free_list = p->free_list_link;start_free = (char *)p;end_free = start_free + i;return chunk_alloc(size, nobjs);}}end_free = NULL;//調用第一級配置器start_free = (char *)malloc_alloc::allocate(bytes_to_get);}heap_size += bytes_to_get;end_free = start_free + heap_size;return chunk_alloc(size, nobjs);}
}

內存釋放

第二級配置器的deallocate函數并不會直接釋放內存塊。當內存塊大小大于128字節時才會直接釋放，否則會將內存塊回收到相應的鏈表當中。如下：

void __default_alloc<threads>::deallocate(void *p, size_t n)
{//大于__MAX_BYTES，則釋放該內存if (n > (size_t)__MAX_BYTES)malloc_alloc::deallocate(p, n);obj *q = (obj *)p;obj *volatile *my_free_list;my_free_list = free_list + FREELIST_INDEX(n);//小于__MAX_BYTES，則回收區塊,并未釋放q->free_list_link = *my_free_list;*my_free_list = q;
}

內存對外接口

STL對外提供了一個simple_alloc類，該類提供統一的接口：allocate函數、deallocate函數，使得外部無需關心使用的是幾級內存配置器。另外simple_alloc類將外部所需的對象個數轉換為字節。如下。

template <typename T, typename Alloc>
class simple_alloc
{
public:static T *allocate(size_t n) // 個數{return n == 0 ? 0 : (T*)Alloc::allocate(n * sizeof(T)); // 將個數轉換為字節}static T *allocate(void){return (T*)Alloc::allocate(sizeof(T));}static void deallocate(T *p, size_t n) // 個數{if (n != 0)Alloc::deallocate(p, n * sizeof(T));}static void deallocate(T *p){Alloc::deallocate(p, sizeof(T));}
};