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