STL空間配置器那點事，stl空間配置
STL簡介
STL（Standard Template Library，標准模板庫），從根本上說，STL是一些“容器”的集合，這些“容器”有list,vector,set,map等，STL也是算法和其他一些組件的集合。
談及組件，那麼我們就首先來簡單談下STL六大組件，其相關的設計模式使用，以及各組件之間的協作關系。
設計模式一覽
六大組件簡單介紹
1. 空間配置器：內存池實現小塊內存分配,對應到設計模式--單例模式（工具類，提供服務，一個程序只需要一個空間配置器即可），享元模式（小塊內存統一由內存池進行管理）
2.迭代器：迭代器模式，模板方法
3.容器：STL的核心之一，其他組件圍繞容器進行工作：迭代器提供訪問方式，空間配置器提供容器內存分配，算法對容器中數據進行處理，仿函數偽算法提供具體的策略，類型萃取 實現對自定義類型內部類型提取。保證算法覆蓋性。其中涉及到的設計模式：組合模式（樹形結構），門面模式（外部接口提供），適配器模式（stack，queue通過deque適配得 到），建造者模式（不同類型樹的建立過程）。
4.類型萃取：基於范型編程的內部類型解析，通過typename獲取。可以獲取迭代器內部類型value_type,Poter,Reference等。
5.仿函數：一種類似於函數指針的可回調機制，用於算法中的決策處理。涉及：策略模式，模板方法。
6適配器：STL中的stack，queue通過雙端隊列deque適配實現，map，set通過RB-Tree適配實現。涉及適配器模式。
關於六大組件之間的具體關系如圖簡單描述
ps（圖技術比較水，見諒，如有bug，請指正）
貌似扯的多了，來談談主題《空間配置器》問題吧。
STL空間配置器產生的緣由：
在軟件開發，程序設計中，我們不免因為程序需求，使用很多的小塊內存（基本類型以及小內存的自定義類型）。在程序中動態申請，釋放。
這個過程過程並不是一定能夠控制好的，於是乎，
問題1：就出現了內存碎片問題。（ps外碎片問題）
問題2：一直在因為小塊內存而進行內存申請，調用malloc，系統調用產生性能問題。
注：內碎片：因為內存對齊/訪問效率（CPU取址次數）而產生 如 用戶需要3字節，實際得到4或者8字節的問題，其中的碎片是浪費掉的。
外碎片：系統中內存總量足夠，但是不連續，所以無法分配給用戶使用而產生的浪費。下邊簡單圖解
這兩個問題解釋清楚之後，就來談STL空間配置器的實現細節了
實現策略
用戶申請空間大於128？
yes：調用一級空間配置器
no：調用二級空間配置器
大致實現為：
二級空間配置由內存池以及伙伴系統：自由鏈表組成
一級空間配置器直接封裝malloc，free進行處理，增加了C++中的set_handler機制（這裡其實也就是個略顯牽強的裝飾/適配模式了），增加內存分配時客戶端可選處理機制。
可配置性：
客戶端可以通過宏__USE_MALLOC進行自定義選擇是否使用二級空間配置器。
一級空間配置器就主要封裝malloc，添加handler機制了，這裡就不羅嗦了，相信各位都是可以通過源碼了解到的
關於二級空間配置器：
最後再羅嗦一點，說說Trace問題，然後就給出代碼了。
Trace使用
對於內存池的內部實現過程共還是比較復雜的，雖然代碼量，函數比較簡單。但是調用過程可能比較復雜。這時，如果我們選擇debug調試，過程會相當的繁瑣，需要仔細記錄調用堆棧過程以及數據流向，邏輯變更等。對於樓主這種水貨來說，估計完事就要苦了。
所以，就使用Trace進行跟蹤，打印數據流向，邏輯走向，文件，函數，方法，行位置。那麼我們就能根據這個記錄進行程序的排錯以及調優了。
具體Trace簡單如下
#pragma once
#define ___TRACE(...) fprintf(fout, "file[%s]line[%u]func[%s]::",__FILE__,__LINE__,__func__);\
fprintf(fout,__VA_ARGS__)
沒錯，就是這麼簡單，利用宏打印文件，行，函數位置，然後利用可變參數列表方式接收代碼中具體位置的記錄跟蹤。
如下是代碼摘取的Alloc中的跟中。
static void *Allocate(size_t n)
{
___TRACE("__MallocAllocTemplate to get n = %u\n",n);
void *result = malloc(n);
if (0 == result)
{
result = OomMalloc(n);
}
return result;
}
我的天：組織不好，手速太差，終於前奏完成。那麼就給出空間配置器的代碼了。
具體也可以在個人的github中獲取源碼
https://github.com/langya0/llhProjectFile/tree/master/STL
文件：Alloc.h
![]()
#pragma once
#include "Config.h"
__STLBEGIN
#include <memory.h>
#include <stdlib.h>
#define __THROW_BAD_ALLOC throw std::bad_alloc()
class __MallocAllocTemplate
{
private:
static void *OomMalloc(size_t);
static void *OomRealloc(void *, size_t);
static void(*__malloc_alloc_oom_handler)();
public:
static void *Allocate(size_t n)
{
___TRACE("__MallocAllocTemplate to get n = %u\n",n);
void *result = malloc(n);
if (0 == result)
{
result = OomMalloc(n);
}
return result;
}
static void *Reallocate(void *p, size_t old_sz, size_t new_sz)
{
void* result = realloc(p, new_sz);
if (0 == result)
{
result = OomRealloc(p, new_sz);
return result;
}
}
static void Deallocate(void *p,size_t n)
{
___TRACE("一級空間配置器釋放 p= %p n = %u\n",p,n);
free(p);
}
//
static void(*set_malloc_handler(void(*f)()))()
{
___TRACE("一級空間配置器,set Handler f = %p\n",f);
void(*old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return (old);
}
};
void *__MallocAllocTemplate::OomMalloc(size_t n)
{
___TRACE("一級空間配置器,不足進入Oo中n = %u\n",n);
void(*my_malloc_handler)();
void* result;
for (;;)
{
my_malloc_handler = __malloc_alloc_oom_handler;
if (0 == my_malloc_handler)
{
__THROW_BAD_ALLOC;
}
(*__malloc_alloc_oom_handler)();
result = malloc(n);
if (result)
return result;
}
}
void* __MallocAllocTemplate::OomRealloc(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;
}
}
void(*__MallocAllocTemplate::__malloc_alloc_oom_handler)() = 0;
typedef __MallocAllocTemplate MallocAlloc; //////這裡放在#ifdef前邊是因為二級空間配置器中還需要調用一級空間配置器
/////////////////////////////////////////根據是否配置__USE_ALLOC選擇使用一級還是二級空間配置器
#ifdef __USE_ALLOC
typedef MallocAlloc Alloc;
#else //not define __USE_ALLOC
template <bool threads, int inst>
class __DefaultAllocTemplate
{
protected:
enum {_ALIGN = 8};
enum {_MAX_BYTES = 128};
enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN
static size_t RoundUp(size_t bytes)
{
return (((bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1));
}
protected:
union _Obj {
// 節點鏈接指針
union _Obj* _freeListLink;
//客戶端數據
char _ClientData[1];
};
//桶結構,保存鏈表
static _Obj* _freeList[_NFREELISTS];
//獲取具體大小元素在表中的下標
static size_t _FreeListIndex(size_t __bytes)
{
return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
}
static char* _start_free;
static char* _end_free;
static size_t _heap_size;
public:
static void* Allocate(size_t n)
{
void * ret = 0;
___TRACE("二級空間配置器申請n = %u\n",n);
if(n>_MAX_BYTES)
ret = MallocAlloc::Allocate(n);
_Obj* volatile * __my_free_list = _freeList + _FreeListIndex(n);
_Obj* __result = *__my_free_list;
if (__result == 0)
ret = _Refill(RoundUp(n));
else
{
*__my_free_list = __result -> _freeListLink;
ret = __result;
}
return ret;
}
static void Deallocate(void* p, size_t n)
{
___TRACE("二級空間配置器刪除p = %p,n = %d\n",p,n);
if (n > (size_t) _MAX_BYTES)
MallocAlloc::Deallocate(p, n);
else
{
_Obj* volatile* __my_free_list = _freeList + _FreeListIndex(n);
_Obj* q = (_Obj*)p;
q -> _freeListLink = *__my_free_list;
*__my_free_list = q;
}
}
static void *Reallocate(void* p,size_t __old_sz,size_t __new_sz)
{
___TRACE("二級空間配置器重新申請p = %p,new_sz = %d\n",p,__new_sz);
void* __result;
size_t __copy_sz;
if (__old_sz > (size_t)_MAX_BYTES && __new_sz > (size_t)_MAX_BYTES)
{
return(realloc(p, __new_sz));
}
if (RoundUp(__old_sz) == RoundUp(__new_sz))
return(p);
__result = Allocate(__new_sz);
__copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
memcpy(__result, p, __copy_sz);
Deallocate(p, __old_sz);
return(__result);
}
protected:
static void *_Refill(size_t n)
{
___TRACE("二級空間配置器自由鏈表填充n = %u\n",n);
size_t nobjs = 20;
void * ret;
char * chunks = _ChunkAlloc(n,nobjs);
if(nobjs == 1)
{
return chunks;
}
_Obj* volatile * __my_free_list = _freeList+_FreeListIndex(n);
ret = chunks;
for(size_t i = 1;i<nobjs;i++)
{
((_Obj*)(chunks+n*i))->_freeListLink = *__my_free_list;
*__my_free_list = (_Obj*)(chunks+n*i);
}
return ret;
}
/////////////這裡的nobjs使用&，，內部需要復用邏輯，可能改變之
static char * _ChunkAlloc(size_t n,size_t &nobjs)
{
size_t totalBytes = n*nobjs;
size_t bytesLeft = _end_free - _start_free;
if(bytesLeft>=totalBytes)
{
___TRACE("二級空間配置器內存池填充n = %u,nobjs = %d\n",n,nobjs);
_start_free += n*nobjs;
return _start_free;
}
else if(bytesLeft>=n)
{
nobjs = (_end_free- _start_free)/n;
___TRACE("二級空間配置器內存池填充n = %u,nobjs = %d\n",n,nobjs);
_start_free +=n*nobjs;
return _start_free;
}
//bytesLeft [0,1)
_Obj* volatile * __my_free_list = _freeList + _FreeListIndex(bytesLeft);
if(_start_free)
{
___TRACE("二級空間配置器剩余bytesLeft = %u\n",bytesLeft);
((_Obj*)_start_free)->_freeListLink=*__my_free_list;
*__my_free_list = (_Obj*)_start_free;
}
size_t bytesToGet = nobjs*n*2+(_heap_size>>4);
//malloc
_start_free = (char*)malloc(bytesToGet);
if(!_start_free)
{
___TRACE("二級空間配置器malloc失敗，在後續鏈表查找n = %d\n",n);
for(size_t i = n + _ALIGN;i < _MAX_BYTES;i+=_ALIGN)
{
_Obj* volatile * cur = _freeList+_FreeListIndex(i);
if(*cur)
{
*cur = (*cur)->_freeListLink;
_start_free = (char*)*cur;
_end_free = _start_free + i;
return _ChunkAlloc(n,nobjs);
}
}
___TRACE("二級空間配置器：後續鏈表查找失敗，轉接一級配置，借用handler機制終止程序或者得到空間n = %d\n",n);
_start_free = (char*)MallocAlloc::Allocate(n);
return _ChunkAlloc(n,nobjs);
}
else
{
_end_free = _start_free + bytesToGet;
_heap_size += bytesToGet;
return _ChunkAlloc(n,nobjs);
}
}
};
template <bool __threads, int __inst>
char* __DefaultAllocTemplate<__threads, __inst>::_start_free= 0;
template <bool __threads, int __inst>
char* __DefaultAllocTemplate<__threads, __inst>::_end_free = 0;
template <bool __threads, int __inst>
size_t __DefaultAllocTemplate<__threads, __inst>::_heap_size = 0;
// static _Obj* _freeList[_NFREELISTS];
template <bool threads, int inst>
typename __DefaultAllocTemplate<threads,inst>::_Obj*
__DefaultAllocTemplate<threads,inst>::_freeList[__DefaultAllocTemplate<threads,inst>::_NFREELISTS]
= {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
typedef __DefaultAllocTemplate<0,0> Alloc;
#endif
__STLEND
void handler()
{
cout << "here in handler!\n"<<endl;
}
void test()
{
// stl::Alloc::set_malloc_handler(handler);
void *arr[21] = {0};
___TRACE("Clint to Get size = %u\n",5);
// for(size_t i =0;i < 21;++i)
// arr[i] = stl::Alloc::Allocate(5);
// for(size_t i =0;i < 21;++i)
// stl::Alloc::Deallocate(arr[i],5);
arr[1] = stl::Alloc::Allocate(8);
arr[2] = stl::Alloc::Allocate(72);
arr[3] = stl::Alloc::Allocate(80);
}
View Code
文件：Trace.h
#pragma once
#define ___TRACE(...) fprintf(fout, "file[%s]line[%u]func[%s]::",__FILE__,__LINE__,__func__);\
fprintf(fout,__VA_ARGS__)
文件Config.h
#pragma once
/////模擬std實現宏方式開始，結束命名空間
namespace __STLNAMESPACE {}
#define __STLBEGIN namespace __STLNAMESPACE {
#define __STLEND }
namespace stl = __STLNAMESPACE;
//for malloc
// #define __USE_MALLOC
///for trace
#define __DEBUG
#ifdef __DEBUG
#include <stdio.h>
#define fout stdout ///方便配置，修改Trace記錄位置
#endif
終於大功告成，源碼finished，那麼，再給出測試結果截圖了
最後，完成了主題工作之後。
再來說一些空間配置器的遺留問題吧：
1.仔細探究源碼之後，你一定會發現一個問題，
貌似二級空間配置器中的空間重頭到尾都沒看到他歸還給系統。那麼問題就是，內存池空間何時釋放？
對於這個問題，在回頭浏覽一下源碼及結構圖，你就會發現
大於128的內存，客戶程序Deallocate之後會調free釋放掉，歸還給了系統。
但是呢...............
內存池中獲取的空間，最終，假定用戶都調用Dealloc釋放調了，那麼他們又在哪裡呢？
沒有還給系統，沒有在內存池，在自由鏈表中。
Got it：程序中不曾釋放，只是在自由鏈表中，且配置器的所有方法，成員都是靜態的，那麼他們就是存放在靜態區。釋放時機就是程序結束。
2.如果需要釋放，那麼應該怎麼處理呢？
因為真正可以在程序運行中就歸還系統的只有自由鏈表中的未使用值，但是他們並不一定是連續的（用戶申請空間，釋放空間順序的不可控制性），所以想要在合適時間（eg一級配置器的handler中釋放，或者設置各閥值，分配空間量到達時處理），就必須保證釋放的空間要是連續的。保證連續的方案就是：跟蹤分配釋放過程，記錄節點信心。釋放時，僅釋放連續的大塊。
3.關於STL空間配置器的效率考究
既然已經存在，而又被廣泛使用，那麼，整體的效率，以及和STL內部容器之間的使用配合還是沒問題的。
我們考慮幾種情況：
a. 用戶只需要無限的char類型空間，然而配置器中卻對齊到8，於是乎，整個程序中就會有7/8的空間浪費。
b.對於假定用戶申請N次8空間，將系統資源耗到一定程度，然後全部釋放了，自由鏈表中的空間都是連續的。卻沒有釋放。
但是：用戶需要申請大於8的空間時，卻依舊沒有空間可用。
總之：這個問題就是，空間可能全部積攢在小塊自由鏈表中，卻沒有用戶可用的。這就尴尬了。
最後，關於配置器的其它問題，如果各位有什麼新的思考，歡迎交流。郵箱：[email protected]
