之前對于配置器的原理及一級配置器的介紹請看博文
這裡寫連結内容
下來我們直接介紹二級空間配置器。
二級空間配置器
我們通過之前的學習，已經知道。
如果所要申請的空間大于128位元組，則直接交至一級空間配置器處理，如果小于128位元組，則使用二級空間配置器。
二級空間配置器對記憶體的管理減少了小區塊造成的記憶體碎片，它主要通過一個連結清單管理：
它是用一個16（128/8）個元素的自由連結清單來管理的，每個位置下挂載着大小為8的倍數個位元組（分别為8、16、24、32、48、56、64、72、80、88、96、104、112、120、128位元組），每次将所需記憶體提升到8的倍數。
free_list它的節點結構為一個共用體：
union obj
{
union obj * free_list_link;
char client_data[1];
}; 二級空間配置器結構如下圖所示：
如圖所示：
在連結清單中空間沒有配置設定出去之前，該空間中一直存放的是所指向的下一個節點的位址，當該空間配置設定出去時，讓對應的my_free_list指向它的下一個節點，然後将它内部的值改為要放入使用者的data值。
如何配置設定記憶體
它的記憶體配置設定主要分為以下幾種情況：
1、對應的free_list不為空
所需空間大小提升為8的倍數後(如需要13bytes空間，我們會給它配置設定16bytes大小)，所對應的free_list不為空時，它會像上圖所示那樣直接從對應的free_list中拔出，第一位置向後移動指向。
2、對應的free_list為空，其記憶體池不為空時：
（1）先檢驗它剩餘空間是否夠20個節點大小（即所需記憶體大小(提升後) * 20），若足夠則直接從記憶體池中拿出20個節點大小空間，将其中一個配置設定給使用者使用，另外19個當作自由連結清單中的區塊挂在相應的free_list下，這樣下次再有相同大小的記憶體需求時，可直接從 free-list 中撥出。
（2）如果不夠20個節點大小，則看它是否能滿足1個節點大小，如果夠的話則直接拿出一個配置設定給使用者，然後從剩餘的空間中配置設定盡可能多的節點挂在相應的free_list中。
（3）如果連一個節點記憶體都不能滿足的話，則将記憶體池中剩餘的空間挂在相應的free_list中（找到相應的free_list），然後再給記憶體池申請記憶體。
3、記憶體池為空，申請記憶體
此時二級空間配置器會使用malloc()從heap上申請記憶體，（一次所申請的記憶體大小為2 * 所需節點記憶體大小（提升後）* 20 + 一段額外空間）。
4、malloc沒有成功
在第三種情況下，如果malloc()失敗了，說明heap上沒有足夠空間配置設定給我們了，這時，二級空間配置器會從比所需節點空間大的free_list中一一搜尋，從任意一個比它所需節點空間大的free_list中拔除一個節點來使用。
5、查找失敗，調用一級空間配置器
第四種情況下，如果查找失敗了，說明比其大的free_list中都沒有自由區塊了，此時會調動一級空間配置器oom_allocate()。
（一級空間配置器文首給出了博文連結）
（記憶體池的概念請看博文這裡寫連結内容）
部分源碼分析
按照上面記憶體配置設定的步驟，我們一步步來看：
/*将 __bytes 上調至最鄰近的 8 的倍數*/
static size_t _S_round_up(size_t __bytes)
{
return (((__bytes)+(size_t)_ALIGN - 1) & ~((size_t)_ALIGN - 1));
}
/*傳回 __bytes 大小的小額區塊位于 free-list 中的編号*/
static size_t _S_freelist_index(size_t __bytes) {
return (((__bytes)+(size_t)_ALIGN - 1) / (size_t)_ALIGN - 1);
} 根據使用者所需記憶體塊大小，申請記憶體：
static void* allocate(size_t __n) //配置設定大小為 __n 的區塊
{
void* __ret = 0;
if (__n > (size_t)_MAX_BYTES) {
__ret = malloc_alloc::allocate(__n); //大于128 bytes 就調用第一級配置器
}
else { //__n 大小區塊對應的位置：free-lists 首位址 + __n 位于free-lists 中的編号
_Obj* __STL_VOLATILE* __my_free_list //這裡是二級指針，便于調整 free-lists
= _S_free_list + _S_freelist_index(__n);
# ifndef _NOTHREADS
_Lock __lock_instance;
# endif
_Obj* __RESTRICT __result = *__my_free_list; //将對應位置的區塊撥出(第一個)
if (__result == 0) //如果 free-lists 中沒有對應大小的區塊
__ret = _S_refill(_S_round_up(__n)); //調用 _S_refill()
else {
*__my_free_list = __result->_M_free_list_link;//這個結構有點類似鍊式哈希表結構，這裡是指向下一塊空閑記憶體塊
//二級指針調整 free-lists，撥出去的區塊就不屬于該連結清單了
__ret = __result;
}
}
return __ret;
}; 如果 free-list 中沒有對應大小的區塊，轉去調用 _S_refill()：
template <bool __threads, int __inst>
void* //重新填充__n大小的區塊進 free-list
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
int __nobjs = 20; //預設取得 20 個新區塊
char* __chunk = _S_chunk_alloc(__n, __nobjs); //調用_S_chunk_alloc()
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
int __i;
/*如果隻獲得一個新區塊，直接劃給使用者，free-list 仍然無新節點*/
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);
/*接下來的區塊(撥出去了__n大小給使用者)填補進 free-list*/
for (__i = 1;; __i++) {
__current_obj = __next_obj;
__next_obj = (_Obj*)((char*)__next_obj + __n);
/*将配置設定的連續大塊"分割"成__n bytes大小的區塊*/
if (__nobjs - 1 == __i) { //如果新區塊填補完畢
__current_obj->_M_free_list_link = 0; //free-list 最後位置指向0
break;
}
else {//把_M_free_list_link當做連結清單的 next 指針了解
__current_obj->_M_free_list_link = __next_obj; //将各節點串聯起來填進空閑連結清單
}
}
return(__result);
} 給對應的哈希桶申請空間：
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; //調整記憶體池位置
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); /
if (__bytes_left > 0) { //充分利用記憶體池中的剩餘空間
_Obj* __STL_VOLATILE* __my_free_list = //剩餘空間尋找适當的free-list
_S_free_list + _S_freelist_index(__bytes_left);
//調整 free-list，将記憶體池中殘餘空間編入 free-list 對應位置中
((_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); //配置heap空間，用來補充記憶體池
if (0 == _S_start_free) { //system heap 空間不足，配置設定失敗
size_t __i;
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __p;
for (__i = __size; //起始大小為需求區塊大小
__i <= (size_t)_MAX_BYTES;
__i += (size_t)_ALIGN) { //以 8 為步長搜尋整個 free-list
__my_free_list = _S_free_list + _S_freelist_index(__i); //找到 __i大小區塊在free-list 中的位置
__p = *__my_free_list;
if (0 != __p) { //如果 free-list 中該區塊未使用
*__my_free_list = __p->_M_free_list_link; //調整 free-list，釋放第一位置塊
_S_start_free = (char*)__p; //編入記憶體池
_S_end_free = _S_start_free + __i;
return(_S_chunk_alloc(__size, __nobjs)); //遞歸調用
/*該for循環的作用就是從 free-list 中劃出大于需求區塊(單個）的未用空間區塊到記憶體池，然後再從記憶體池中取出。
由于從大于__size 的區塊開始搜尋，是以如果 free-list 中搜尋到，那麼隻需動用該搜尋區塊的第一位置區塊即可，
最後取出的空間也可能是單個區塊，也可能是多個區塊(取決于 free-list 未用區塊的最小區塊(大于__size)的大小)*/
}
}
_S_end_free = 0; //表示到處無記憶體可用，for循環中free-list沒有搜尋到适當的未用空間
_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get); //調用第一級配置器
/*要麼記憶體不足的問題獲得改善，要麼抛出 bad_alloc 異常*/
}
_S_heap_size += __bytes_to_get; //調用第一級配置器後，記憶體不足問題獲得改善，調整堆空間
_S_end_free = _S_start_free + __bytes_to_get; //編入記憶體池
return(_S_chunk_alloc(__size, __nobjs)); //重新調用 _S_chunk_alloc()
}
} 釋放空間
當使用者從二級空間配置器中申請的記憶體被釋放時，要将其回收然後插入對應的free_list：
/*空間釋放後被編入 free-list*/
static void deallocate(void* __p, size_t __n)
{
if (__n > (size_t)_MAX_BYTES) //大于 128 就調用第一級配置器
malloc_alloc::deallocate(__p, __n);
else {
_Obj* __STL_VOLATILE* __my_free_list //定位到對應的 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; //調整 free-list 回收區塊
*__my_free_list = __q; //回收的區塊是挂接到free-list 對應區塊的第一位置，而不是添加到尾端
}
} 模拟實作
我們測試時加入一級空間配置器的代碼：
//一級空間配置器 >128
//函數指針
typedef void(*pMallocHandle)();
template<int inst>
class MallocAllocTemplate
{
public:
static void* Allocate(size_t size)
{
void* result = malloc(size);
//申請失敗調用OOM_Malloc()函數
if (NULL == result)
{
result = OOM_Malloc(size);
}
__TRACE_DEBUG("一級空間配置器：%d\n", size);
return result;
}
//重新配置設定空間
static void* ReAllocate(void* p, size_t, size_t newSize) //三個參數
{
void* result = realloc(p, newSize);
if (NULL == result)
{
result = OOM_Realloc(p, newSize);
}
return result;
}
static void DeAllocate(void* p, size_t) //底層是兩個參數
{
__TRACE_DEBUG("一級釋放\n");
free(p);
}
private:
static void* OOM_Malloc(size_t size)
{
pMallocHandle mallocHandle;
void* res;
for (;;)
{
mallocHandle = _mallocHandle;
if (NULL == mallocHandle)
throw std::bad_alloc();
//嘗試去釋放已經擷取，但是不用的堆空間
mallocHandle();
//嘗試重新配置設定記憶體
res = malloc(size);
if (res)
return res;
}
}
static void* OOM_Realloc(void *p, size_t size)
{
pMallocHandle mallocHandle;
void* res;
__TRACE_DEBUG("一級：第一次申請失敗，OOM處理：%d\n", size);
for (;;)
{
mallocHandle = _mallocHandle;
if (NULL == mallocHandle)
throw std::bad_alloc();
//嘗試去釋放已經擷取但是不用的堆空間
mallocHandle();
res = realloc(p, size);
if (res)
return res;
}
}
//若申請失敗，釋放方法
static pMallocHandle SetMallocHandle(pMallocHandle mallocHandle)
{
pMallocHandle old = _mallocHandle;
_mallocHandle = mallocHandle;
return old;
}
private:
static pMallocHandle _mallocHandle;
};
pMallocHandle MallocAllocTemplate<0>::_mallocHandle = NULL; 根據上面的分析，二級空間配置器的代碼如下：
//<=128個位元組
//交給二級配置器
//小的記憶體塊，減少頻繁的向系統malloc
template<int inst>
class DefaultAllocateTemplate
{
public:
//申請記憶體
static void* Allocate(size_t size)
{
if (size > 128)
return MallocAllocTemplate<0>::Allocate(size);
__TRACE_DEBUG("二級空間配置器：%d\n", size);
size_t index = FreeListIndex(size); //求出對應的索引
if (_freeList[index] == NULL) //連結清單沒有，從記憶體池申請填充
{
__TRACE_DEBUG("二級：%d桶中(%d)沒有可用空間，需要記憶體池補充\n", index, size);
return ReFill(ROUND_UP(size));
}
//将對應哈希桶中連結清單中第一塊撥出給使用者
void* result = _freeList[index];
_freeList[index] = _freeList[index]->_freeListLink;
return result;
}
//釋放記憶體
static void DeAllocate(void *ptr, size_t size)
{
if (size > 128)
return MallocAllocTemplate<0>::DeAllocate(ptr, size);
__TRACE_DEBUG("二級空間配置器釋放：%d\n", size);
size_t index = FreeListIndex(size);
((OBJ*)ptr)->_freeListLink = _freeList[index];
_freeList[index] = (OBJ*)ptr;
}
private:
//向上對齊為8的整數倍
static size_t ROUND_UP(size_t bytes)
{
return (((bytes)+_ALIGN - 1)&~(_ALIGN - 1));
}
//bytes對應的哈希桶的下标
static size_t FreeListIndex(size_t bytes)
{
return (((bytes)+_ALIGN - 1) / _ALIGN - 1);
}
//給對應的桶裡填充記憶體塊
static void* ReFill(size_t size)
{
size_t nobjs = 20;
char* chunk = (char*)ChunkAlloc(size, nobjs);
if (nobjs == 1) //隻有一個直接給使用者
return chunk;
size_t index = FreeListIndex(size);
//将剩下的記憶體塊管理起來，連結在對應的桶裡
OBJ* cur = (OBJ*)(chunk + size);
__TRACE_DEBUG("二級：記憶體池補充%d個小塊記憶體\n", nobjs);
while (--nobjs)
{
cur->_freeListLink = _freeList[index]; //頭插每個size大小的記憶體塊
_freeList[index] = cur;
cur = (OBJ*)((char*)cur + size);
}
return chunk;
}
//給桶申請空間
static void* ChunkAlloc(size_t size, size_t& nobjs)
{
size_t TotalBytes = size*nobjs;
size_t LeftBytes = _endFree - _startFree; //記憶體池剩餘空間
char *result;
//記憶體池空間足夠 nobjs=20
if (LeftBytes >= TotalBytes)
{
__TRACE_DEBUG("二級:記憶體池可以提供20個%d位元組的記憶體塊\n", size)
result = _startFree;
_startFree += TotalBytes;
return result;
}
//小于需要的20塊，隻能提供至少一塊記憶體 1<=nobjs<20
else if (LeftBytes >= size)
{
nobjs = LeftBytes / size;
__TRACE_DEBUG("二級：記憶體池不太夠，可以提供%d個%d位元組的記憶體塊\n", nobjs, size);
result = _startFree;
_startFree += nobjs*size;
return result;
}
//一塊記憶體都不夠,給記憶體池補充空間
else
{
__TRACE_DEBUG("二級：記憶體池一個%d位元組的小塊記憶體都不能提供\n", size);
//1.将記憶體池剩餘的空間挂到對應的連結清單中
size_t index = FreeListIndex(LeftBytes);
if (LeftBytes > 0)
{
OBJ* cur = (OBJ*)_startFree;
cur->_freeListLink = _freeList[index];
_freeList[index] = cur;
}
//2.在堆中給記憶體池申請空間
size_t Getbytes = 2 * TotalBytes + ROUND_UP(_heapSize >> 4); //系統堆給記憶體池配置設定空間的大小
__TRACE_DEBUG("二級：記憶體池不夠了，需要在堆申請%d位元組的記憶體塊\n", Getbytes);
_startFree = (char*)malloc(Getbytes);
//2.1申請失敗
if (_startFree == NULL)
{
__TRACE_DEBUG("二級:記憶體池不夠且在堆中申請失敗，在連結清單中找更大的記憶體塊，%d位元組\n", (index + 1)*_ALIGN);
//在二級空間配置器中找更大的記憶體塊
size_t index = FreeListIndex(size);
for (int i = index; i < _NFREELISTS; i++)
{
OBJ* Cur = _freeList[index];
if (Cur != NULL)
{
_startFree = (char*)Cur;
_freeList[index] = Cur->_freeListLink;
_endFree = _startFree + (index + 1)*_ALIGN;
return ChunkAlloc(size, nobjs);
}
}
__TRACE_DEBUG("二級:山窮水盡了，向一級空間配置器申請，%d位元組的記憶體塊\n", Getbytes);
_endFree = NULL; //避免異常，置空
_startFree = (char*)MallocAllocTemplate<0>::Allocate(Getbytes);
}
//2.2在堆中申請成功
__TRACE_DEBUG("二級:在堆中申請成功了%d位元組的記憶體塊\n", Getbytes);
_heapSize += Getbytes;
_endFree = _startFree + Getbytes;
return (ChunkAlloc(size, nobjs));
}
}
private:
enum { _ALIGN = 8 };
enum { _MAX_BYTES = 128 };
enum { _NFREELISTS = _MAX_BYTES / _ALIGN };
union OBJ
{
OBJ* _freeListLink;
char clientData[1]; //
};
private:
static char* _startFree; //标記記憶體池的起始位址
static char* _endFree; //标記記憶體池的結束位址
static size_t _heapSize; //之前向堆中申請的位元組數
static OBJ* _freeList[_NFREELISTS]; //存放OBJ的指針數組
};
//靜态成員變量需要在類外初始化
template<int inst>
char* DefaultAllocateTemplate<inst>::_startFree = NULL;
template<int inst>
char* DefaultAllocateTemplate<inst>::_endFree = NULL;
template<int inst>
size_t DefaultAllocateTemplate<inst>::_heapSize = NULL;
template<int inst>
typename DefaultAllocateTemplate<inst>::OBJ* DefaultAllocateTemplate<inst>::\
_freeList[DefaultAllocateTemplate<inst>::_NFREELISTS] = { 0 }; 為了友善測試，我們将空間配置器封裝為一個類：
//給空間配置器起别名
#ifdef USE_MALLOC
typedef MallocAllocTemplate<0> _Alloc;
#else
typedef DefaultAllocateTemplate<0> _Alloc;
#endif
template <class T, class Alloc>
class SimpleAllocate
{
public:
static void* Allocate(size_t n) //申請n個類型為T的位元組大小
{
return (0 == n) ? 0 : Alloc::Allocate(n*sizeof(T));
}
static void* Allocate(void) //申請T位元組大小
{
return (0 == n) ? 0 : Alloc::Allocate(sizeof(T));
}
static void DeAllocate(void* p, size_t n)
{
Alloc::DeAllocate(p, n*sizeof(T));
}
static void deallocate(void *p)
{
Alloc::Deallocate(p, sizeof(T));
}
}; 我們用一個特殊的測試函數測試，上述代碼中有很多__TRACE_DEBUG包含的資訊，這樣測試友善我們知道代碼的運作及資料的變化是否正确：
#define _DEBUG_
static string GetFileName(const string& path)
{
char ch = '/';
#ifdef _WIN32
ch = '\\';
#endif
size_t pos = path.rfind(ch);
if (pos == string::npos)
return path;
else
return path.substr(pos + 1);
}
//用于調試追蹤的trace log
inline static void _trace_debug(const char * funcName, const char * fileName, int line, char* format, ...)
{
#ifdef _DEBUG_
fprintf(stdout, "[%s:%d]%s", GetFileName(fileName).c_str(), line, funcName);
// 輸出使用者資訊
va_list args;
va_start(args, format);
vfprintf(stdout, format, args);
va_end(args);
#endif
}
#define __TRACE_DEBUG(...) _trace_debug(__FUNCDNAME__, __FILE__, __LINE__, __VA_ARGS__); 測試：
//測試
void TestAlloc()
{
//一級
int *p1 = (int*)SimpleAllocate<int, _Alloc>::Allocate(100);
SimpleAllocate<int, _Alloc>::DeAllocate(p1, 100);
//二級
p1 = (int*)SimpleAllocate<int, _Alloc>::Allocate(2);
SimpleAllocate<int, _Alloc>::DeAllocate(p1, 2);
p1 = (int*)SimpleAllocate<int, _Alloc>::Allocate(5); //記憶體池--->16
int *p2 = (int*)SimpleAllocate <int, _Alloc>::Allocate(10);
SimpleAllocate<int, _Alloc>::DeAllocate(p1, 5);
SimpleAllocate<int, _Alloc>::DeAllocate(p2, 10);
} 觀察結果：
