[導讀]??大家好，我是唐唐！本文關于C內(nèi)存管理學習筆記自侯捷，上次筆記見?C內(nèi)存管理（一）。1.各個標準分配器實現(xiàn)1.1VC6.0malloc在第一節(jié)中提到，malloc的內(nèi)存塊布局如上，其中cookie(記錄區(qū)塊大小)小，浪費率高，因為cookie始終占8字節(jié)。cookie是我們不需...
??
大家好，我是唐唐！本文關于 C 內(nèi)存管理學習筆記自侯捷，上次筆記見?C 內(nèi)存管理（一）。
結論：同 vc6.0。
而 g2.9 容器使用的分配器，不是 std::allocator,而是std::alloc。對于前面提到的 malloc 設計，如果想要優(yōu)化,可以減少malloc次數(shù)，同時減少cookie。而去除 cookie 的先決條件是你的 cookie 大小一致。容器里面的元素是一樣的大小，這就滿足了先決條件！分配器的客戶不是給你應用程序用，而是給容器用。
1.5 G4.9結構
g4.9 的 __pool_alloc 是我們在容器中使用的分配器。而普通的 allocator，則是通過 operator new 與 operator delete 調(diào)用 malloca 與 free。其實沒有什么特殊設計。最后，來個測試用例,通過對比 allocator 與 __pool_alloc 來看看連續(xù)地址相差字節(jié)，來判斷是否攜帶 cookie。
2.2 std::alloc運行過程
申請32bytes圖32 字節(jié)對應 #3 指針所指向的鏈表,此時由于戰(zhàn)備池為空,故向戰(zhàn)備池中充值
申請 96bytes 圖由于戰(zhàn)備池中沒有余量，此時向戰(zhàn)備池中注入
山窮水盡了，怎么辦,此時給出了兩種辦法，但是在 GCC 中沒有采納任何作法！
定義了 union free_list_link，嵌入式指針，在上一章中我們構建的一個小的分配器中也定義了該聯(lián)合體，作用類似，該聯(lián)合體只有一個成員,因此可以使用 struct 代替。free_list 是一個有 16個obj* 元素的數(shù)組，在前面講過，GCC 2.9 的分配器用一個16 字節(jié)數(shù)組管理 16 條鏈表，free_list 便是該管理數(shù)組。refill 和 chunk_alloc 在后面再介紹。start_free 和 end_free 分別指向該內(nèi)存池的頭和尾。中間管理的就是戰(zhàn)備池！這一塊對應到 G4.9 中，代碼如下：
大家好，我是唐唐！本文關于 C 內(nèi)存管理學習筆記自侯捷，上次筆記見?C 內(nèi)存管理（一）。
1.各個標準分配器實現(xiàn)
1.1 VC6.0 malloc
在第一節(jié)中提到，malloc 的內(nèi)存塊布局如上，其中 cookie (記錄區(qū)塊大小)小，浪費率高，因為 cookie 始終占 8 字節(jié)。cookie 是我們不需要的，如果大量調(diào)用 malloc 的話 cookie 總和會增多，這會造成較大的浪費，因此減少 malloc 調(diào)用次數(shù)，去掉 cookie 總是好的。1.2 VC6.0標準分配器
結論：VC6.0 的 allocate() 函數(shù)只是對 malloc 的二次封裝，并沒有做什么很特殊的操作，它是以類型字節(jié)長度為單位分配內(nèi)存的，上圖就分配了512個int類型空間。結論：同 vc6.0。
1.3 G2.9 malloc
GCC 2.9 版本的 allocator 如上圖所示,同樣這里的 allocator 同前面提到的幾個標準分配器一樣。而 g2.9 容器使用的分配器，不是 std::allocator,而是std::alloc。對于前面提到的 malloc 設計，如果想要優(yōu)化,可以減少malloc次數(shù)，同時減少cookie。而去除 cookie 的先決條件是你的 cookie 大小一致。容器里面的元素是一樣的大小，這就滿足了先決條件！分配器的客戶不是給你應用程序用，而是給容器用。
1.4 G4.9 malloc
在 GCC 4.9 版本，2.9 版本的 alloc 變成了 __pool_alloc。從上面兩張圖可以對比看出，2.9 版本的 allocate 和 4.9 版本的 __pool_alloc 做的事是一樣的，只是修改了變量名和一些細小操作而已。1.5 G4.9結構
g4.9 的 __pool_alloc 是我們在容器中使用的分配器。而普通的 allocator，則是通過 operator new 與 operator delete 調(diào)用 malloca 與 free。其實沒有什么特殊設計。最后，來個測試用例,通過對比 allocator 與 __pool_alloc 來看看連續(xù)地址相差字節(jié)，來判斷是否攜帶 cookie。#include #include #include
using namespace std;
templatevoid cookie_test(Alloc alloc, size_t n){ typename Alloc::value_type *p1, *p2, *p3;//需有 typename p1 = alloc.allocate(n); //allocate() and deallocate() 是 non-static, 需以 object 呼叫之. p2 = alloc.allocate(n); p3 = alloc.allocate(n);
cout << "p1= " << p1 << '\t' << "p2= " << p2 << '\t' << "p3= " << p3 << '\n';
alloc.deallocate(p1,sizeof(typename Alloc::value_type)); //需有 typename alloc.deallocate(p2,sizeof(typename Alloc::value_type)); //有些 allocator 對於 2nd argument 的值無所謂 alloc.deallocate(p3,sizeof(typename Alloc::value_type));}
int main(void){ cout << sizeof(__gnu_cxx::__pool_alloc) << endl; vector > vecPool; cookie_test(__gnu_cxx::__pool_alloc(), 1);
cout << "----------------------" << endl;
cout << sizeof(std::allocator) << endl; vector > vecPool2; cookie_test(std::allocator(), 1);
return 0;}輸出：1p1= 0x5557fc0f1280p2= 0x5557fc0f1288p3= 0x5557fc0f1290----------------------1p1= 0x5557fc0f13d0p2= 0x5557fc0f13f0p3= 0x5557fc0f1410可以發(fā)現(xiàn)容器使用的 __pool_alloc 后，連續(xù)地址相差 8 字節(jié),而一個 double 類型變量的大小也是 8 個字節(jié)，說明這連續(xù)幾塊內(nèi)存之間是不帶 cookie 的（即使這幾塊內(nèi)存在物理上也是不連續(xù)的）。而后面那個則相差更多(相差 32 字節(jié)，攜帶了 cookie )。2.std::alloc
2.1 G2.9 運作模式
G2.9 std::alloc 運作模式使用一個 16 個攜帶指針頭的數(shù)組來管理內(nèi)存鏈表，而我們上一章只是用了一條鏈表。數(shù)組不同的元素管理不同的區(qū)塊，每個元素之間相差 8 字節(jié),例如 #3 號元素負責管理 32bytes 為一小塊的鏈表。途中 pool 就是戰(zhàn)備池( start_free 與 end_free 中間部分)，所以總是把分配的東西放到戰(zhàn)備池中，再從戰(zhàn)備池挖適當?shù)目臻g到鏈表來。這樣構思，代碼寫起來特別漂亮。假設現(xiàn)在用戶需要 32 字節(jié)的內(nèi)存，std::allloc 先申請一塊區(qū)間，為32*20*2 大小，用一條鏈表管理，然后讓數(shù)組的#3鏈表指針管理這條鏈表。接著講該以 32 為一個單元的鏈表的中的一個單元（ 32 字節(jié)）分給用戶。(對應圖中綠色部分).為什么是 32*20*2？前面 32*20 空間是分配給用戶的，但是后面的 32*20 空間是預留的，如圖所示,如果這時用戶需要一個 64 字節(jié)的空間，那么剩下的 32*20 空間將變成 64*10，然后將其中 64 字節(jié)分配給用戶，而不用再一次地構建鏈表和申請空間。其中 20 是開發(fā)團隊設計的一個值。如果該鏈表組維護的鏈表最大的一個小塊為 128byte，但是用戶申請內(nèi)存塊超過了 128byte，那么 std::alloc 將調(diào)用 malloc 給用戶分配空間，然后該塊將帶上 cookie頭和尾。前面一節(jié)提到內(nèi)存管理的核心設計:嵌入式指針.在真正的商業(yè)級的內(nèi)存分配器中，一般都會使用嵌入式指針，將每一個小塊的前四個字節(jié)用作指針連接下一塊可用的內(nèi)存塊。這樣不需要多分配額外空間,就可以完成任務。2.2 std::alloc運行過程
申請32bytes圖32 字節(jié)對應 #3 指針所指向的鏈表,此時由于戰(zhàn)備池為空,故向戰(zhàn)備池中充值 32*20*2 RoundUp(0>>4=1280) ,從中切出一塊返回給客戶,剩余 19 塊,累計申請量有 1280 字節(jié),戰(zhàn)備池有 640 字節(jié).RoundUp 實現(xiàn) 8 字節(jié)對齊.例如傳入 13,傳出的就是 16. 0>>4 表示右移 4 位,每次除以 16.申請 64bytes 圖上次的戰(zhàn)備池有 640 字節(jié)，下次的分配就會從戰(zhàn)備池中取，這次申請 64 字節(jié)，對應到#7鏈表指針，此時使用戰(zhàn)備池中的字節(jié)做區(qū)塊,可以得到 10 個，從中切出一塊返回給用戶，剩余 9，此時累計申請量：1280 ，戰(zhàn)備池大小此時為 0。申請 96bytes 圖由于戰(zhàn)備池中沒有余量，此時向戰(zhàn)備池中注入
96*20*2 RoundUp(1280>>4) 其余原理同上。后面的申請圖同上原理。戰(zhàn)備池不夠了，碎片狀態(tài)如何處理：在前面的戰(zhàn)備池中還有 24 字節(jié)，此時需要 72 字節(jié)，戰(zhàn)備池中 1 個區(qū)塊都不能夠滿足，因此要先解決 24 區(qū)字節(jié)碎片，再重新往 #8 中充值。碎片處理，24 字節(jié)對應的是 #2，那么把剛才的 24 字節(jié)塊拉到 #2 即可。此時要重新往 #8 中充值,同事此時假設系統(tǒng)的 heap 大小為 10000，此時分配的72*20*2 RoundUp(9688>>4 再加上之前的累計申請量，更新后就超過了 10000，資源不夠了，那此時就需要從后面最近的鏈表元素借。在上一個圖中我們發(fā)現(xiàn) #9 滿足,此時 80 - 72=8，也就是戰(zhàn)備池為 8。切除了 72 返回給用戶。再申請 72 字節(jié)原理結合了碎片處理與上面的資源限制處理：此時申請 120 字節(jié),對應 #14，根據(jù)上述原理,此時已經(jīng)山窮水盡！山窮水盡了，怎么辦,此時給出了兩種辦法，但是在 GCC 中沒有采納任何作法！
3.std::allloc 源碼剖析
3.1 G2.9 與 G4.9 簡要對比
侯老師的 ppt 講解源碼是 G2.9，這里我將以 G4.9 自學方式對比課上 G2.9 內(nèi)容。在 G2.9 中有 std::alloc 的第一級分配器與第二級分配器,在 G4.9 中只有前面的第二級分配器，因此侯老師在講解過程中先從第二級分配器講解，只提及第一級分配器中的設計注意點，下面一起來學習。上面是 G2.9 的源碼,其中分配器為 __default_alloc_template，一開始默認使用的分配器，在該類中定義了 ROUND_UP 函數(shù)，用來將申請內(nèi)存數(shù)量做 8 字節(jié)對齊。定義了 union free_list_link，嵌入式指針，在上一章中我們構建的一個小的分配器中也定義了該聯(lián)合體，作用類似，該聯(lián)合體只有一個成員,因此可以使用 struct 代替。free_list 是一個有 16個obj* 元素的數(shù)組，在前面講過，GCC 2.9 的分配器用一個16 字節(jié)數(shù)組管理 16 條鏈表，free_list 便是該管理數(shù)組。refill 和 chunk_alloc 在后面再介紹。start_free 和 end_free 分別指向該內(nèi)存池的頭和尾。中間管理的就是戰(zhàn)備池！這一塊對應到 G4.9 中，代碼如下：
class __pool_alloc_base{protected:
enum { _S_align = 8 }; enum { _S_max_bytes = 128 }; enum { _S_free_list_size = (size_t)_S_max_bytes / (size_t)_S_align };
union _Obj{union _Obj* _M_free_list_link;char _M_client_data[1]; // The client sees this.};
static _Obj* volatile _S_free_list[_S_free_list_size];
// Chunk allocation state. static char* _S_start_free; static char* _S_end_free; static size_t _S_heap_size;
size_t _M_round_up(size_t __bytes){ return ((__bytes (size_t)_S_align - 1) 
下載文檔
