下面會(huì)結(jié)合關(guān)鍵源碼分析C++STL(SGI版本)的內(nèi)存配置器設(shè)計(jì)思想。關(guān)鍵詞既然是“思想”，所以重點(diǎn)也就呼之欲出了。

1、allocator的簡短介紹

我閱讀的源碼是SGI公司的版本，也是看起來最清楚的版本，各種命名最容易讓人看懂。allocator有人叫它空間配置器，因?yàn)榭臻g不一定是內(nèi)存，也可以是磁盤或其他輔助存儲(chǔ)介質(zhì)。我說的內(nèi)存配置就是指的allocator。

C++標(biāo)準(zhǔn)規(guī)范了allocator的一些必要接口，由各個(gè)廠家實(shí)現(xiàn)。SGI的版本與眾不同，也與標(biāo)準(zhǔn)規(guī)范不同，它的名稱是alloc而不是allocator，且不接受任何參數(shù)。

假設(shè)你在程序中顯示寫出allocator，不能像下面這樣寫：

必須要這樣寫才對：

雖然SGI STL并不符合規(guī)范，但我們用起來好像很自然。這是因?yàn)槲覀兪褂脮r(shí)空間配置器是缺省的，不需要我們自行指定。例如，STL中vector的聲明如下：

注意：下文我基本就用截圖來解釋代碼了，因?yàn)槲野l(fā)現(xiàn)比起粘貼代碼，這樣更清晰（有顏色對比）。

2、源碼文件簡單介紹

STL標(biāo)準(zhǔn)規(guī)定：STL的allocator定義于<Memory>文件中，<Memory>主要包含了一些頭文件，我們主要說的是兩個(gè)：

<stl_alloc.h>負(fù)責(zé)內(nèi)存空間的配置與釋放；<stl_construct.h>負(fù)責(zé)對象內(nèi)容的構(gòu)造與析構(gòu)

3、構(gòu)造和析構(gòu)工具：construct()和destroy()

先來說一下簡單的<stl_construct.h>文件。這部分也不涉及什么思想，只是有一個(gè)版本的destroy()應(yīng)該認(rèn)真看看。

（1）構(gòu)造工具：construct()

construct()只有一個(gè)版本：

這里使用了placement new表達(dá)式（定位new 表達(dá)式），它的作用是p指向的內(nèi)存類型為T1，用value值初始化這塊內(nèi)存。

（2）析構(gòu)工具

destroy()倒是有幾個(gè)版本：

***個(gè)版本：

這種顯示調(diào)用析構(gòu)函數(shù)的做法，你也應(yīng)該要熟悉。

第二個(gè)版本：

第二個(gè)版本可有點(diǎn)說法。調(diào)用層次是這樣的：destroy-> __destroy-> __destroy_aux，__destroy_aux最終調(diào)用***個(gè)版本的destroy。這個(gè)版本的destroy接受一對迭代器作為參數(shù)，析構(gòu)迭代器所指向的范圍內(nèi)元素。

講解這個(gè)流程前，先簡單說一下trivial_destructor。

如果用戶不定義析構(gòu)函數(shù)，而是用編譯器合成的，則說明析構(gòu)函數(shù)基本沒有什么用（但默認(rèn)會(huì)被調(diào)用），稱之為trivial destructor。

那么，如果一對迭代器所指向的元素都是trivial destructor的，就沒必要浪費(fèi)時(shí)間對每個(gè)對象依次執(zhí)行它的析構(gòu)函數(shù)了，依靠編譯器的行為就好了。這樣在效率上是一種提升。這是STL allocator優(yōu)化的一個(gè)點(diǎn)。

首先利用value_type()取得迭代器指向?qū)ο蟮男蛣e，再利用__type_traits<T>判斷對象的析構(gòu)函數(shù)是否為trivial_destructor。如果是__true_type就什么都不做，否則循環(huán)調(diào)用***版本的destroy()。

第三個(gè)版本：

這是針對迭代器為char*和wchar_t*的特化版本，看到它們的函數(shù)體為空，你應(yīng)該猜到了，無須執(zhí)行析構(gòu)操作。

4、內(nèi)存的申請與銷毀，std::alloc

內(nèi)存的申請和銷毀由<stl_alloc.h>負(fù)責(zé)。SGI關(guān)于這一點(diǎn)的設(shè)計(jì)哲學(xué)是：

（1）向system heap要求空間。

（2）考慮多線程狀態(tài)。

（3）考慮內(nèi)存不足時(shí)的應(yīng)變策略。

（4）考慮過多“小型區(qū)塊”可能造成的內(nèi)存碎片問題。

其實(shí)我最主要想說的是（3）（4）的設(shè)計(jì)策略，尤其是內(nèi)存池的思路。

std::alloc的整體設(shè)計(jì)思想為：

SGI設(shè)計(jì)了雙層級配置器，***級配置器直接使用malloc和free；第二級配置器視情況不同采用不同策略：當(dāng)配置區(qū)塊超過128bytes 時(shí)，視為“足夠大”，調(diào)用***級配置器處理；當(dāng)配置區(qū)塊小于128bytes時(shí)，視為“過小”，為降低額外負(fù)擔(dān)，采用memory pool（內(nèi)存池）處理方式，不再借助于***級配置器。

一、***級內(nèi)存配置器解析

***級配置器主要函數(shù)有：allocate分配內(nèi)存、deallocate釋放內(nèi)存、reallocate重新分配內(nèi)存等。

（1）allocate

直接調(diào)用C函數(shù)malloc，如果內(nèi)存無法滿足需求，就調(diào)用oom_malloc函數(shù)。

原來，這是自己實(shí)現(xiàn)的handler函數(shù)啊，為什么自己實(shí)現(xiàn)呢？因?yàn)樗褂玫牟⒉皇莖perator new配置的內(nèi)存，所以無法使用C++new-handler機(jī)制。

關(guān)于這個(gè)機(jī)制，實(shí)際上能有不少東西可說呢，如果你不熟悉它的用途或自己實(shí)現(xiàn)的方法，我建議你看看《Effective C++》，或者看看我對《Effective C++》做的筆記。我這里主要不是想分析語法方面的東西。

（2）deallocate

代碼放上去就應(yīng)該明白了。

（3）reallocate

這里依然是調(diào)用C的realloc函數(shù)，如果調(diào)用失敗，就調(diào)用oom_realloc函數(shù)。

可以看出oom_realloc也是個(gè)handler函數(shù)。

基本上***級內(nèi)存配置器就解釋清楚了。這里再提一點(diǎn)：SGI以malloc而非operator new來配置內(nèi)存一方面是歷史原因，另一方面C++并未提供realloc函數(shù)。這樣造成了SGI不能直接使用C++的set_new_handler()，只能自己仿真一個(gè)。如何仿真set_new_handler，是有特定模式的。

#p#

二、第二級內(nèi)存配置器解析

第二級內(nèi)存配置器增加了一些機(jī)制，避免太多小額區(qū)塊造成的內(nèi)存碎片。小額區(qū)塊帶來的不僅是內(nèi)存碎片，配置時(shí)的額外負(fù)擔(dān)也是個(gè)大問題。額外負(fù)擔(dān)永遠(yuǎn)無法避免，畢竟系統(tǒng)要靠這多出來的空間來管理內(nèi)存，但區(qū)塊越小，額外負(fù)擔(dān)所占的比例越大，自然越浪費(fèi)。

第二級內(nèi)存配置器的整體思想是：

（1）如果申請的區(qū)塊超過128bytes，就交給***級內(nèi)存配置器處理。

（2）如果申請的區(qū)塊小于等于128bytes，用內(nèi)存池管理。

具體為：第二級內(nèi)存配置器會(huì)將任何小額區(qū)塊的內(nèi)存需求上調(diào)至8的倍數(shù)，并維護(hù)16個(gè)free-lists，各自管理大小為8、16、24、32、40、48、56、64、72、80、88、96、104、112、120、128字節(jié)的小額區(qū)塊。

free-lists中節(jié)點(diǎn)結(jié)構(gòu)如下：（我已經(jīng)將這個(gè)union注釋）

注意：union的這種用法，也被稱為”柔性數(shù)組“成員。本質(zhì)上，與小端對齊這種存儲(chǔ)方式有關(guān)，這是一種技巧。

（1）allocate

第二級內(nèi)存配置器__default_alloc_template的內(nèi)存分配接口是allocate函數(shù)。

關(guān)鍵部分我已經(jīng)用紅框注釋過了。FREELIST_INDEX(n)函數(shù)根據(jù)n的值返回16個(gè)free-list中合適的那個(gè)list的下標(biāo)。

再看看ROUND_UP(n)，這個(gè)函數(shù)我認(rèn)為寫的挺巧妙的，將bytes值調(diào)整至8字節(jié)的倍數(shù)。

理解這個(gè)函數(shù)你可以先舉幾個(gè)bytes值，看看返回值是什么，自然就理解了。refill()函數(shù)很有用處，我放在下面再來介紹。

（2）deallocate()

首先判斷區(qū)塊大小，大于128字節(jié)就調(diào)用***級配置器，否則就根據(jù)需要回收的字節(jié)大小，判斷出應(yīng)該把它回歸到哪個(gè)free list，然后由這個(gè)free list回收。

（3）refill()

這個(gè)函數(shù)挺重要的，所以要單獨(dú)拿出來介紹。當(dāng)free list中沒有可用的區(qū)塊時(shí)，就調(diào)用這個(gè)函數(shù)，為該free list重新填充一部分空間。新的空間取自內(nèi)存池（由chunk_alloc完成）。缺省取得20個(gè)新區(qū)塊，如果內(nèi)存池空間不足，獲得的新區(qū)塊數(shù)目可能小 于20。

圖中兩個(gè)紅框是值得注意的兩個(gè)點(diǎn)。一旦從內(nèi)存池獲得內(nèi)存區(qū)塊后，拿出一個(gè)給調(diào)用者，另外的還要找到合適的free list”穿“起來。

（4）內(nèi)存池函數(shù)chunk_alloc()

內(nèi)存池一直用來供給free list。下面要將這個(gè)函數(shù)分開截圖說明了。

***個(gè)分支：看看內(nèi)存池內(nèi)的容量夠不夠，夠的話直接拿走就好。

第二個(gè)分支：內(nèi)存池不夠20個(gè)塊的容量，但是大于等于1個(gè)塊的長度，就把剩下的都給出去了。此時(shí)，內(nèi)存池是空的。

第三個(gè)分支：如果內(nèi)存池連1個(gè)對應(yīng)的塊都不能提供了，比如需要32字節(jié)，但只有8字節(jié)了，這時(shí)候***的做法是把這8個(gè)字節(jié)鏈接到相應(yīng)的free list利用上。不出意料，此時(shí)內(nèi)存池也是空的。

第四個(gè)分支：內(nèi)存池空空如也，所以內(nèi)存池求助于運(yùn)行時(shí)堆，堆也沒有那么多空間了，于是就檢查這16個(gè)free list中有哪些塊沒用過呢，把這些補(bǔ)充到內(nèi)存池。

第五個(gè)分支：沒錯(cuò)，heap也無能為力了，內(nèi)存池干脆直接調(diào)用***級配置器，因?yàn)?**級配置器有new-handler機(jī)制，或許有機(jī)會(huì)釋放其他內(nèi)存拿來此處調(diào)用呢。如果可以，就成功否則拋出bad-alloc異常。

小結(jié)：

如果別人問我STL內(nèi)存配置的思想。我可能會(huì)這樣說：C++STL是兩級配置內(nèi)存的，具體來說：***級負(fù)責(zé)管理大塊內(nèi)存，要保證有類似new- handler的機(jī)制；第二級負(fù)責(zé)管理小塊內(nèi)存，為了更好的管理內(nèi)存碎片，建立16個(gè)鏈表，每個(gè)鏈表“穿”著一塊一塊固定大小的內(nèi)存，這16個(gè)鏈表（0至 15）分別“穿”的內(nèi)存是8、16、24…128倍數(shù)關(guān)系。需要內(nèi)存時(shí)，從“合適”的鏈表取走，如果“合適”的鏈表內(nèi)存不夠用了，從內(nèi)存池里拿，如果內(nèi)存 池不夠用了，從運(yùn)行時(shí)heap里拿，如果heap也溢出了，就交給***級配置器，因?yàn)樗衝ew-handler機(jī)制。