????????STL中內(nèi)存管理非常精妙徐紧，本文以SGI STL為例静檬，分析其內(nèi)存管理的設(shè)計(jì)思路炭懊，也是對(duì)侯捷老師的《STL源碼剖析》中相關(guān)內(nèi)容的總結(jié)。
????????首先拂檩，從總體上看侮腹，STL空間配置器分為兩級(jí)，針對(duì)大內(nèi)存的申請(qǐng)广恢，調(diào)用第一級(jí)空間配置器凯旋，對(duì)于小內(nèi)存的申請(qǐng)呀潭，則調(diào)用第二級(jí)配置器钉迷。
第一級(jí)空間配置器
????????第一級(jí)空間配置器對(duì)外提供了allocate()，deallocate(),reallocate()三個(gè)函數(shù)供用戶使用钠署，同時(shí)糠聪，其內(nèi)部定義了oom_allocate()和oom_reallocate()函數(shù)，用于處理內(nèi)存不足的情況谐鼎。
????????deallocate()函數(shù)直接調(diào)用free函數(shù)釋放內(nèi)存舰蟆，無(wú)須關(guān)心其他問(wèn)題，重點(diǎn)在于內(nèi)存不足情況下allocate()函數(shù)和reallocate()函數(shù)是如何應(yīng)對(duì)的狸棍。
????????allocate()函數(shù)首先調(diào)用malloc函數(shù)獲取內(nèi)存身害，在內(nèi)存不足的情況下，該函數(shù)會(huì)返回空指針NULL草戈，當(dāng)malloc函數(shù)返回NULL時(shí)塌鸯，則會(huì)調(diào)用oom_allocate()函數(shù)嘗試釋放一些內(nèi)存并再次進(jìn)行申請(qǐng)。
????????這就是第一級(jí)空間配置器所提供的一種緩沖機(jī)制唐片，第一級(jí)配置器中定義了一個(gè)函數(shù)指針丙猬，這個(gè)指針?biāo)赶虻暮瘮?shù)由用戶所定義，因?yàn)橹挥杏脩糁滥男﹥?nèi)存可以被釋放來(lái)騰出空間费韭，如果沒有為該函數(shù)指針賦予相應(yīng)的函數(shù)茧球，則此時(shí)直接會(huì)拋出bad_alloc異常，若該函數(shù)指針被指定星持，則會(huì)不停調(diào)用該函數(shù)抢埋，直到申請(qǐng)到足夠的內(nèi)存，這里把它叫做內(nèi)存不足處理函數(shù)督暂，它的運(yùn)行過(guò)程如圖所示
????????reallocate函數(shù)的內(nèi)部運(yùn)行過(guò)程和allocate函數(shù)的過(guò)程是相似的羹令，只不過(guò)把malloc換成了realloc，oom_allocate換成了oom_reallocate损痰，過(guò)程都是一樣的福侈。
第二級(jí)空間配置器
????????第二級(jí)內(nèi)存配置器負(fù)責(zé)小內(nèi)存的管理
????????當(dāng)申請(qǐng)大量的小內(nèi)存時(shí)，一方面會(huì)把完整的內(nèi)存區(qū)間劃分的很破碎卢未，當(dāng)再次申請(qǐng)較大的內(nèi)存時(shí)肪凛，可能會(huì)出現(xiàn)沒有足夠長(zhǎng)的區(qū)間的情況堰汉，另一方面，大量的小區(qū)間也會(huì)使操作系統(tǒng)用來(lái)記錄內(nèi)存狀態(tài)的數(shù)據(jù)結(jié)構(gòu)很臃腫伟墙。
????????第二級(jí)內(nèi)存配置器所采取的策略是翘鸭，在第一次申請(qǐng)小內(nèi)存時(shí)，先申請(qǐng)一大塊內(nèi)存留作備用戳葵，以后再申請(qǐng)小內(nèi)存時(shí)就乓，直接從上次申請(qǐng)的那一大塊內(nèi)存中劃去要求的部分，不再向系統(tǒng)申請(qǐng)拱烁。
????????同樣的生蚁，第二級(jí)空間配置器提供了標(biāo)準(zhǔn)接口allocate()、deallocate()戏自、reallocate()三個(gè)接口邦投，在介紹這三個(gè)接口之前，先介紹一下接下來(lái)會(huì)遇到的一些名詞擅笔。
????????1. 內(nèi)存區(qū)塊志衣，有時(shí)也簡(jiǎn)稱區(qū)塊
????????內(nèi)存區(qū)塊是指一塊小內(nèi)存，它的大小均為8的倍數(shù)猛们，最大為128Bytes念脯，即有8、16弯淘、24绿店、32、40耳胎、48惯吕、56、64怕午、72废登、80、88郁惜、96堡距、114、122兆蕉、128這幾種羽戒，內(nèi)存區(qū)塊有自己的首地址，可以存儲(chǔ)數(shù)據(jù)虎韵。在每個(gè)區(qū)塊的前8個(gè)字節(jié)易稠，存儲(chǔ)下一個(gè)可用區(qū)塊的地址，通過(guò)這種方式包蓝，可以形成一條區(qū)塊鏈表
????????2. freelist數(shù)組
????????freelist數(shù)組是一個(gè)數(shù)組企量，內(nèi)含16個(gè)元素，每一個(gè)元素是一個(gè)區(qū)塊鏈表的首指針
????????3. 內(nèi)存池
????????內(nèi)存池是是一大塊內(nèi)存亡电，它有三個(gè)參數(shù)：起始地址届巩，終止地址以及大小，內(nèi)存池的大小=終止地址 - 起始地址
????????在初始狀態(tài)下份乒，內(nèi)存池是空的恕汇，內(nèi)存區(qū)塊也是不存在的，freelist數(shù)組中保存的都是空指針或辖。
????????我們從這種狀態(tài)下開始分析瘾英，該機(jī)制是如何運(yùn)作的。
運(yùn)行過(guò)程
????????當(dāng)申請(qǐng)的內(nèi)存大于128bytes時(shí)孝凌，直接轉(zhuǎn)交第一級(jí)配置器進(jìn)行內(nèi)存申請(qǐng)方咆。
????????當(dāng)申請(qǐng)的內(nèi)存不大于128bytes時(shí)月腋，假設(shè)申請(qǐng)n字節(jié)
????????1. 計(jì)算（n + 7）/7蟀架，得到一個(gè)整數(shù)值i，這個(gè)i即為freelist的元素索引
????????2. 訪問(wèn)freelist位于i的元素榆骚，此時(shí)該元素為NULL片拍，不指向任何可用區(qū)塊，這時(shí)將n向上調(diào)整為8的倍數(shù)妓肢，并調(diào)用refill函數(shù)
//n 調(diào)整為8的倍數(shù)后申請(qǐng)的單個(gè)區(qū)塊的大小
//返回值 該區(qū)塊的地址
void* __default_alloc_template<threads,inst>::refill(size_t n);
????????3. refill函數(shù)的作用是給freelist重新填充內(nèi)存區(qū)塊捌省，這些區(qū)塊從內(nèi)存池中獲得，一次默認(rèn)取20個(gè)碉钠，通過(guò)函數(shù)chunk_alloc獲得
char*
__default_alloc_template<threads,inst>::
chunk_alloc(size_t size , int& nobjs);
//size 申請(qǐng)的單個(gè)區(qū)塊的大小
//nobjs 注意纲缓，nobjs是一個(gè)引用類型
//在refill調(diào)用這個(gè)函數(shù)時(shí)，傳入的nobjs是20喊废，即20個(gè)區(qū)塊
//chunk_alloc執(zhí)行完成后祝高，nobjs會(huì)被修改為實(shí)際獲得的區(qū)塊數(shù)目
????????chunk_alloc函數(shù)返回的是一塊長(zhǎng)度為nobjs*n的內(nèi)存塊，refill函數(shù)需要將這一整塊連續(xù)內(nèi)存分割為一個(gè)個(gè)內(nèi)存區(qū)塊污筷，并構(gòu)建鏈表的鏈接關(guān)系
????????在內(nèi)存充足的情況下工闺，第一個(gè)內(nèi)存塊會(huì)被返回給用戶使用，從第二塊內(nèi)存塊開始構(gòu)建鏈接關(guān)系瓣蛀，如圖所示
????????在內(nèi)存不足的情況下陆蟆，假如只分配到了一個(gè)區(qū)塊，則該區(qū)塊直接交給用戶使用惋增，freelist不進(jìn)行更新
????????如果不足20個(gè)叠殷，則仍將獲得的內(nèi)存構(gòu)建鏈接關(guān)系。
????????如果一個(gè)區(qū)塊都沒有獲得诈皿，因?yàn)閏hunk_alloc函數(shù)內(nèi)部調(diào)用了第一級(jí)配置器填充內(nèi)存池林束，因此會(huì)按照第一級(jí)內(nèi)存配置器的方式處理內(nèi)存不足的情況钩杰。
chunk_alloc函數(shù)
char*
__default_alloc_template<threads,inst>::
chunk_alloc(size_t size , int& nobjs);
????????這里我們要關(guān)注幾個(gè)參數(shù)
????????1. 申請(qǐng)的內(nèi)存總大小——size*nobjs，這里用total_bytes來(lái)表示
????????2. 內(nèi)存池剩余空間——用bytes_left表示
????????如果total_bytes小于bytes_left诊县，則直接劃走total_bytes這么多內(nèi)存讲弄，同時(shí)更新內(nèi)存池的狀態(tài)
????????如果內(nèi)存池的剩余空間不夠申請(qǐng)的那么多區(qū)塊，即size < bytes_left < total_bytes依痊，即能夠供應(yīng)一部分區(qū)塊避除，則計(jì)算最多能劃多少塊，并劃走
????????如果連一個(gè)區(qū)塊都無(wú)法供應(yīng)胸嘁，這時(shí)候就要給內(nèi)存池“加水”了
????????在“加水”之前瓶摆，首先要把內(nèi)存池中剩下的水收集起來(lái)，別浪費(fèi)了性宏，加到freelist上去群井，具體的步驟是，根據(jù)剩下的內(nèi)存的大小確定freelist的index毫胜，因?yàn)槊總€(gè)內(nèi)存塊都是8的倍數(shù)书斜，劃走時(shí)也按照8的倍數(shù)劃分的，因此生下來(lái)的內(nèi)存一定可以構(gòu)成一個(gè)內(nèi)存區(qū)塊酵使，找到合適的freelist位置后荐吉，將這個(gè)區(qū)塊加到freelist上，這時(shí)口渔，就可以開始“加水”了
????????首先要確定“加多少水”样屠，即為內(nèi)存池填充的內(nèi)存總量
????????1. 加完“水”后，要滿足這次的內(nèi)存申請(qǐng)的量缺脉，即大于total_bytes
????????2. 加完“水”后痪欲，內(nèi)存池的大小應(yīng)該比上一次的要大
????????SGI STL選擇的量是
????????2 × total_bytes + heap_size >> 4
????????heap_size是以往內(nèi)存池的容量的累加和，這里把它作為一個(gè)附加變量來(lái)看待攻礼，要滿足业踢，隨著“加水”次數(shù)變多，每次加水的量應(yīng)該越來(lái)越大這個(gè)條件
????????確定加多少水后秘蛔，通過(guò)malloc函數(shù)獲取內(nèi)存
????????如果獲取成功陨亡，則更新內(nèi)存池的狀態(tài)，并遞歸調(diào)用chunk_malloc深员，因?yàn)閮?nèi)存池已經(jīng)充足负蠕，下一次能夠直接獲取指定的內(nèi)存
????????如果沒能獲取那么多內(nèi)存
????????首先，遍歷freelist倦畅，如果freelist里面有大小大于一個(gè)size的空閑區(qū)塊遮糖，則將這個(gè)區(qū)塊加入到內(nèi)存池，并遞歸
????????注意叠赐，這里的遍歷并不是那種從freelist第一個(gè)開始逐個(gè)檢查欲账，而是以size為起點(diǎn)屡江，確定freelist中相應(yīng)的index，如果該index不含有空閑區(qū)塊赛不，則將size增加8字節(jié)惩嘉，也就是檢查下個(gè)freelist，直到后面的freelist都檢查完踢故，中途找到任何一個(gè)空閑區(qū)塊文黎，都會(huì)立即返回，不再遍歷
如果遍歷freelist也找不到足夠的空閑區(qū)塊殿较，那么只能指望第一級(jí)配置器中由用戶設(shè)置的內(nèi)存不足處理函數(shù)能否解決耸峭，這里轉(zhuǎn)交給第一級(jí)空間配置器，這時(shí)淋纲，要么第一級(jí)空間配置器順利獲得內(nèi)存劳闹，這時(shí)會(huì)更新內(nèi)存池，并遞歸洽瞬，沒能順利獲得內(nèi)存本涕，則會(huì)拋出異常。
釋放內(nèi)存
????????釋放內(nèi)存的過(guò)程相對(duì)簡(jiǎn)單片任，由第二級(jí)內(nèi)存配置器分配的內(nèi)存偏友，在釋放時(shí)并不交由free函數(shù)進(jìn)行釋放蔬胯，也不放到內(nèi)存池中对供，而是把內(nèi)存加入到freelist鏈表中，以備下次使用氛濒，這個(gè)過(guò)程主要是簡(jiǎn)單的鏈表操作产场，不作詳解。
內(nèi)存區(qū)塊鏈表
????????freelist中舞竿，每一個(gè)元素都是obj*京景，obj的結(jié)構(gòu)如圖所示
union obj
{
union obj* free_list_link;
char client_data[1];
}
????????這里為什么要采用這種結(jié)構(gòu)？
????????首先考慮它的功能骗奖，它是內(nèi)存區(qū)塊的鏈表結(jié)點(diǎn)确徙，它需要記錄當(dāng)前區(qū)塊的地址，以及下個(gè)區(qū)塊的地址执桌，每個(gè)地址都是8個(gè)字節(jié)的指針鄙皇，用一個(gè)struct來(lái)表示，需要16字節(jié)仰挣，而使用union結(jié)構(gòu)伴逸，只需要8個(gè)字節(jié)
????????在每個(gè)內(nèi)存區(qū)塊的前8個(gè)字節(jié)處，是個(gè)obj對(duì)象膘壶，它存儲(chǔ)著下一個(gè)內(nèi)存區(qū)塊的地址错蝴，當(dāng)用free_list_link來(lái)解引用這個(gè)指針時(shí)洲愤，有效區(qū)間為這8個(gè)字節(jié)，client_data是一個(gè)長(zhǎng)度為1的數(shù)組顷锰，只有一個(gè)元素柬赐，它就是內(nèi)存區(qū)塊的第一個(gè)字節(jié)，為這個(gè)字節(jié)定義一個(gè)變量官紫，并對(duì)它取址躺率，得到的就是當(dāng)前區(qū)塊的地址，這里采用數(shù)組的形式而不是直接定義一個(gè)char万矾，目的是直接將client_data作為數(shù)組首地址返回悼吱，而不需要調(diào)用取址運(yùn)算符，將該內(nèi)存區(qū)塊返回時(shí)良狈，返回client_data后添，無(wú)須進(jìn)行類型轉(zhuǎn)換，直接在union中切換就行薪丁，狀態(tài)的改變不會(huì)改變前8個(gè)字節(jié)的內(nèi)容遇西，但內(nèi)存區(qū)塊交出去后，前八個(gè)字節(jié)的內(nèi)容丟失也不重要了严嗜，在將內(nèi)存區(qū)塊加入到freelist中時(shí)粱檀，會(huì)重新設(shè)置前8個(gè)字節(jié)的值，保證數(shù)據(jù)的有效性漫玄。
