接着上回，這節開始說allocte記憶體配置設定的實作
目錄
allocate源碼流程：
_S_refill 的實作：
_S_chunk_alloc的實作：
deallocate：
reallocate：
二級空間配置器的邏輯步驟：
假如現在申請n個位元組：
1、判斷n是否大于128，如果大于128則直接調用一級空間配置器。如果不大于，則将n上調至8的倍數處，然後再去自由連結清單中相應的結點下面找，如果該結點下面挂有未使用的記憶體，則摘下來直接傳回這塊空間的位址。否則的話我們就要調用refill(size_t n)函數去記憶體池中申請。
2、向記憶體池申請的時候可以多申請幾個，STL預設一次申請nobjs=20個，将多餘的挂在自由連結清單上，這樣能夠提高效率。
進入refill函數後，先調chunk_alloc(size_t n,size_t& nobjs)函數去記憶體池中申請，如果申請成功的話，再回到refill函數。
這時候就有兩種情況，如果nobjs=1的話則表示記憶體池隻夠配置設定一個，這時候隻需要傳回這個位址就可以了。否則就表示nobjs大于1，則将多餘的記憶體塊挂到自由連結清單上。
如果chunk_alloc失敗的話，在他内部有處理機制。
3、進入chunk_alloc(size_t n,size_t& nobjs )向記憶體池申請空間的話有三種情況：
3.1、記憶體池剩餘的空間足夠nobjs*n這麼大的空間，則直接配置設定好傳回就可以了。
3.2、記憶體池剩餘的空間leftAlloc的範圍是n<=leftAlloc<nobjs*n,則這時候就配置設定nobjs=(leftAlloc)/n這麼多個的空間傳回。
3.3、記憶體池中剩餘的空間連一個n都不夠了，這時候就要向heap申請記憶體，不過在申請之前先要将記憶體池中剩餘的記憶體挂到自由連結清單上，之後再向heap申請。
3.3.1、如果申請成功的話，則就再調一次chunk_alloc重新配置設定。
3.3.2、如果不成功的話，這時候再去自由連結清單中看看有沒有比n大的空間，如果有就将這塊空間還給記憶體池，然後再調一次chunk_alloc重新配置設定。
3.3.3、如果沒有的話，則就調用一級空間配置器配置設定，看看記憶體不足處理機制能否處理。
allocate源碼流程：
static void* allocate(size_t __n)
{
void* __ret = 0;
//如果申請大于128位元組了，就不受記憶體池管了
if (__n > (size_t) _MAX_BYTES) {
__ret = malloc_alloc::allocate(__n);
}//通過malloc去開辟
else {
//小于等于，通過記憶體池去開辟配置設定了
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);
// Acquire the lock here with a constructor call.
// This ensures that it is released in exit or during stack
// unwinding.
# ifndef _NOTHREADS
/*REFERENCED*/
_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;
};
整個流程：利用棧上對象出作用域自動析構的特點，構造析構加鎖解鎖，完全支援線程安全
_S_refill 的實作：
底層配置設定記憶體的接口
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);
/* Build free list in chunk */
__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);
}
以要開辟8位元組記憶體為例：
讓__my_free_list指向對應下标位置，讓result指向了連結清單chunk塊頭，一次移動一塊，讓頭指針往下移
_S_refill 就幹了兩件事，一件是從記憶體池配置設定了每條帶20個結點的連結清單，另一件就是根據指針移動配置設定記憶體結點，把各個chunk記憶體塊連接配接起來
下面就是通過_S_chunk_alloc去從記憶體池裡配置設定一塊一塊的chunk
_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;//記憶體池要配置設定的位元組數8*20 ，20個結點
size_t __bytes_left = _S_end_free - _S_start_free;//剩餘的位元組數，0,320
if (__bytes_left >= __total_bytes) {//chunk夠用，遞歸第二遍開始走320>160
__result = _S_start_free; //如果剩餘的大小大于等于申請的大小，則傳回這個這
_S_start_free += __total_bytes;//直接加到160,40個結點分兩半
return(__result);
} else if (__bytes_left >= __size) {
//如果剩餘的記憶體足夠配置設定一個新size, 比如8位元組連結清單下還有20塊，現在要配置設定16位元組的
//8*20=160 剛好能配置設定10個16位元組，這樣的話就把這邊8位元組的塊合成10塊當16位元組配置設定了
//然後把這些chunk塊寫到16位元組編号下面
//等于配置設定的40個位元組，前20個給8位元組，後20備用，如果需要16,32...位元組就按剩下的塊整合
//按照新位元組大小配置設定出去，把整合剩的挂到新size編号上
__nobjs = (int)(__bytes_left/__size);
__total_bytes = __size * __nobjs;
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
} else { //記憶體池中的記憶體已經不夠一個size了，一開始走這
size_t __bytes_to_get = //最開始開辟40個結點
2 * __total_bytes + _S_round_up(_S_heap_size >> 4);//0>>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);//320
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;//走到128
__i += (size_t) _ALIGN) { //一次走8
__my_free_list = _S_free_list + _S_freelist_index(__i);
__p = *__my_free_list;//周遊編号，走到能配置設定的位置>=目前size，去配置設定chunk
if (0 != __p) {
//比如要配置設定40位元組，40上也不夠了，就走到48上去，56上去..
*__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.
}
}
//找不到能配置設定的就malloc從堆往記憶體池申請
_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;//走完一遍，__bytes_left就有值了
return(_S_chunk_alloc(__size, __nobjs));//遞歸調用
}
}
如果沒有配置設定，就一上來配置設定20個結點，再*2，_S_heap_size是0，是以最初一共配置設定40個，把40個平分兩半，把前20個就傳回回去，進到_S_refill 裡面，把這20個結點連起來，用出去，後20個作為備用
如果前20各用完了，用到備用20個的時候，要申請大于目前編号位元組數的位元組時走第二個else if
- 如果剩餘的記憶體足夠配置設定一個新size, 比如8位元組連結清單下還有20塊，現在要配置設定16位元組的
- 8*20=160 剛好能配置設定10個16位元組，這樣的話就把這邊8位元組的塊合成10塊當16位元組配置設定了
- 然後把這些chunk塊寫到16位元組編号下面
- 等于配置設定的40個位元組，前20個給8位元組，後20備用，如果需要16,32...位元組就按剩下的塊整合
- 按照新位元組大小劃分配置設定出去，把整合剩的挂到新size編号上
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);
如果我們備用chunk剩了32位元組，現在要配置設定40位元組，我們連一塊也配置設定不出去，此時進到最後一個else
剩的32也不能浪費了，先把這32位元組接到對應到能用到的編号下，是以放到了32位元組編号下，32位元組obj就指向剩的這32位元組頭，把這32位元組和編号下原有的連結清單串起來了，
SGI STL二級空間配置器源碼剖析（2）
如果目前位置上剩的不夠配置設定，就從目前位置8位元組循環為往後找，看哪個位置上有chunk能配置設定
上述所有操作開辟失敗了就malloc從堆申請，這塊malloc也是很巧妙的，一直循環去申請直到申請成功
template <int __inst>
void* __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n)
{
void (* __my_malloc_handler)();//回調函數
void* __result;
for (;;) { //死循環一直去申請
__my_malloc_handler = __malloc_alloc_oom_handler;
if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }
(*__my_malloc_handler)();
__result = realloc(__p, __n);
if (__result) return(__result);
}
}
deallocate：
reallocate：
template <bool threads, int inst>
void*
__default_alloc_template<threads, inst>::reallocate(void* __p,
size_t __old_sz,
size_t __new_sz)
{
void* __result;
size_t __copy_sz;
//大于128
if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES) {
return(realloc(__p, __new_sz));
}
//如果是小塊記憶體的擴容縮容
if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);//調整8倍數
__result = allocate(__new_sz);//如果在不同位元組下，重新allocate配置設定new_sz
__copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;//擴容 縮容
memcpy(__result, __p, __copy_sz);//拷貝
deallocate(__p, __old_sz);
return(__result);
}
空間配置器的其他問題：
1、在空間配置器中所有的函數和變量都是靜态的，是以他們在程式結束的時候才會被釋放發。二級空間配置器中沒有将申請的記憶體還給作業系統，隻是将他們挂在自由連結清單上。是以說隻有當你的程式結束了之後才會将開辟的記憶體還給作業系統。
2、由于它沒有将記憶體還給作業系統，是以就會出現二種極端的情況。
2.1、假如我不斷的開辟小塊記憶體，最後将整個heap上的記憶體都挂在了自由連結清單上，但是都沒有用這些空間，再想要開辟一個大塊記憶體的話會開辟失敗。
2.2、再比如我不斷的開辟char,最後将整個heap記憶體全挂在了自由連結清單的第一個結點的後面，這時候我再想開辟一個16個位元組的記憶體，也會失敗。
總的來說上面的情況隻是小機率情況。如果非得想辦法解決的話，我想的是：針對2.1我們可以引入釋放二級空間配置器的方法，但是這個釋放比較麻煩。針對2.2我們可以合并自由連結清單上的連續的小的記憶體塊。
3、二級空間配置器會造成内碎片問題，極端的情況下一直申請char，則就會浪費7/8的空間。