From: http://blog.csdn.net/pizi0475/article/details/6301796
STL的記憶體配置設定器
題記：記憶體管理一直是C/C++程式的×××。關于記憶體管理的話題，大緻有兩類側重點，一類是記憶體的正确使用，例如C++中new和delete應該成對出現，用RAII技巧管理記憶體資源，auto_ptr等方面，很多C/C++書籍中都使用技巧的介紹。另一類是記憶體管理的實作，如linux核心的slab配置設定器，STL中的allocator實作，以及一些特定于某種對象的記憶體管理等。最近閱讀了一些記憶體管理實作方面的資料和源碼，整理了一下，彙編成一個系列介紹一些常用的記憶體管理政策。
1. STL容器簡介
STL提供了很多泛型容器，如vector，list和map。程式員在使用這些容器時隻需關心何時往容器内塞對象，而不用關心如何管理記憶體，需要用多少記憶體，這些STL容器極大地友善了C++程式的編寫。例如可以通過以下語句建立一個vector，它實際上是一個按需增長的動态數組，其每個元素的類型為int整型：
stl::vector<int> array;
擁有這樣一個動态數組後，使用者隻需要調用push_back方法往裡面添加對象，而不需要考慮需要多少記憶體：
array.push_back(10);
array.push_back(2);
vector會根據需要自動增長記憶體，在array退出其作用域時也會自動銷毀占有的記憶體，這些對于使用者來說是透明的，stl容器巧妙的避開了繁瑣且易出錯的記憶體管理工作。
2. STL的預設記憶體配置設定器
隐藏在這些容器後的記憶體管理工作是通過STL提供的一個預設的allocator實作的。當然，使用者也可以定制自己的allocator，隻要實作allocator模闆所定義的接口方法即可，然後通過将自定義的allocator作為模闆參數傳遞給STL容器，建立一個使用自定義allocator的STL容器對象，如：
stl::vector<int, UserDefinedAllocator> array;
大多數情況下，STL預設的allocator就已經足夠了。這個allocator是一個由兩級配置設定器構成的記憶體管理器，當申請的記憶體大小大于128byte時，就啟動第一級配置設定器通過malloc直接向系統的堆空間配置設定，如果申請的記憶體大小小于128byte時，就啟動第二級配置設定器，從一個預先配置設定好的記憶體池中取一塊記憶體傳遞給使用者，這個記憶體池由16個不同大小（8的倍數，8~128byte）的空閑清單組成，allocator會根據申請記憶體的大小（将這個大小round up成8的倍數）從對應的空閑塊清單取表頭塊給使用者。
這種做法有兩個優點：
1）小對象的快速配置設定。小對象是從記憶體池配置設定的，這個記憶體池是系統調用一次malloc配置設定一塊足夠大的區域給程式備用，當記憶體池耗盡時再向系統申請一塊新的區域，整個過程類似于批發和零售，起先是由allocator向總經商批發一定量的貨物，然後零售給使用者，與每次都總經商要一個貨物再零售給使用者的過程相比，顯然是快捷了。當然，這裡的一個問題時，記憶體池會帶來一些記憶體的浪費，比如當隻需配置設定一個小對象時，為了這個小對象可能要申請一大塊的記憶體池，但這個浪費還是值得的，況且這種情況在實際應用中也并不多見。
2）避免了記憶體碎片的生成。程式中的小對象的配置設定極易造成記憶體碎片，給作業系統的記憶體管理帶來了很大壓力，系統中碎片的增多不但會影響記憶體配置設定的速度，而且會極大地降低記憶體的使用率。以記憶體池組織小對象的記憶體，從系統的角度看，隻是一大塊記憶體池，看不到小對象記憶體的配置設定和釋放。
實作時，allocator需要維護一個存儲16個空閑塊清單表頭的數組free_list，數組元素i是一個指向塊大小為8*(i+1)位元組的空閑塊清單的表頭，一個指向記憶體池起始位址的指針start_free和一個指向結束位址的指針end_free。空閑塊清單節點的結構如下：
union obj {
union obj *free_list_link;
char client_data[1];
};
這個結構可以看做是從一個記憶體塊中摳出4個位元組大小來，當這個記憶體塊空閑時，它存儲了下個空閑塊，當這個記憶體塊傳遞給使用者時，它存儲的時使用者的資料。是以，allocator中的空閑塊連結清單可以表示成：
obj* free_list[16];
3. 配置設定算法
allocator配置設定記憶體的算法如下：
算法：allocate
輸入：申請記憶體的大小size
輸出：若配置設定成功，則傳回一個記憶體的位址，否則傳回NULL
{
if(size大于128）{ 啟動第一級配置設定器直接調用malloc配置設定所需的記憶體并傳回記憶體位址；}
else {
将size向上round up成8的倍數并根據大小從free_list中取對應的表頭free_list_head;
if(free_list_head不為空）{
從該清單中取下第一個空閑塊并調整free_list；
傳回free_list_head;
} else {
調用refill算法建立空閑塊清單并傳回所需的記憶體位址；
}
}
}
算法： refill
輸入：記憶體塊的大小size
輸出：建立空閑塊連結清單并傳回第一個可用的記憶體塊位址
調用chunk_alloc算法配置設定若幹個大小為size的連續記憶體區域并傳回起始位址chunk和成功配置設定的塊數nobj；
if(塊數為1)直接傳回chunk；
否則
{
開始在chunk位址塊中建立free_list;
根據size取free_list中對應的表頭元素free_list_head;
将free_list_head指向chunk中偏移起始位址為size的位址處, 即free_list_head=(obj*)(chunk+size);
再将整個chunk中剩下的nobj-1個記憶體塊串聯起來構成一個空閑清單；
傳回chunk，即chunk中第一塊空閑的記憶體塊；
}
算法：chunk_alloc
輸入：記憶體塊的大小size，預配置設定的記憶體塊塊數nobj(以引用傳遞)
輸出：一塊連續的記憶體區域的位址和該區域内可以容納的記憶體塊的塊數
計算總共所需的記憶體大小total_bytes；
if(記憶體池中足以配置設定，即end_free - start_free >= total_bytes) {
則更新start_free;
傳回舊的start_free;
} else if(記憶體池中不夠配置設定nobj個記憶體塊，但至少可以配置設定一個){
計算可以配置設定的記憶體塊數并修改nobj；
更新start_free并傳回原來的start_free;
} else { //記憶體池連一塊記憶體塊都配置設定不了
先将記憶體池的記憶體塊鍊入到對應的free_list中後；
調用malloc操作重新配置設定記憶體池，大小為2倍的total_bytes加附加量，start_free指向傳回的記憶體位址；
if(配置設定不成功) {
if(16個空閑清單中尚有空閑塊）
嘗試将16個空閑清單中空閑塊回收到記憶體池中再調用chunk_alloc(size, nobj)；
else {
調用第一級配置設定器嘗試out of memory機制是否還有用；
}
}
更新end_free為start_free+total_bytes，heap_size為2倍的total_bytes;
調用chunk_alloc(size,nobj);
}
算法：deallocate
輸入：需要釋放的記憶體塊位址p和大小size
if(size大于128位元組）直接調用free(p)釋放；
else{
将size向上取8的倍數，并據此擷取對應的空閑清單表頭指針free_list_head;
調整free_list_head将p鍊入空閑清單塊中；
假設這樣一個場景，free_list[2]已經指向了大小為24位元組的空閑塊連結清單，如圖1所示，當使用者向allocator申請21位元組大小的記憶體塊時，allocaotr會首先檢查free_list[2]并将free_list[2]所指的記憶體塊配置設定給使用者，然後将表頭指向下一個可用的空閑塊，如圖2所示。注意，當記憶體塊在連結清單上是，前4個位元組是用作指向下一個空閑塊，當配置設定給使用者時，它是一塊普通的記憶體區。
圖1 某時刻allocator的狀态
圖2 配置設定24位元組大小的記憶體塊
4. 小結
STL中的記憶體配置設定器實際上是基于空閑清單(free list)的配置設定政策，最主要的特點是通過組織16個空閑清單，對小對象的配置設定做了優化。
1）小對象的快速配置設定和釋放。當一次性預先配置設定好一塊固定大小的記憶體池後，對小于128位元組的小塊記憶體配置設定和釋放的操作隻是一些基本的指針操作，相比于直接調用malloc/free，開銷小。
2）避免記憶體碎片的産生。零亂的記憶體碎片不僅會浪費記憶體空間，而且會給OS的記憶體管理造成壓力。
3）盡可能最大化記憶體的使用率。當記憶體池尚有的空閑區域不足以配置設定所需的大小時，配置設定算法會将其鍊入到對應的空閑清單中，然後會嘗試從空閑清單中尋找是否有合适大小的區域，