5千字長文+30張圖解 | 陪你手撕STL空間配置器源碼
1. 前言
天下大事，必作于細(xì)。
源碼之前，了無秘密。
你清楚下面這幾個(gè)問題嗎？
-
當(dāng)你調(diào)用 new 和 delete 時(shí)編譯器底層到底做了哪些工作？
STL 各大容器底層空間配置原理是怎樣的？
STL 空間配置器到底要考慮什么？
什么是內(nèi)存的配置和釋放？
…
這篇，我們就來回答這些問題。
2. STL 六大組件
在深入配置器之前，我們有必要了解下 STL 的背景知識：
標(biāo)準(zhǔn)模板庫（英文：Standard Template Library，縮寫：STL），是一個(gè) C++ 軟件庫。
STL 的價(jià)值在于兩個(gè)方面，就底層而言，STL 帶給我們一套極具實(shí)用價(jià)值的零部件以及一個(gè)整合的組織；除此之外，STL 還帶給我們一個(gè)高層次的、以泛型思維 (Generic Paradigm) 為基礎(chǔ)的、系統(tǒng)化的“軟件組件分類學(xué)”。
STL 提供六大組件，了解這些為接下來的閱讀打下基礎(chǔ)。
1、容器（containers）:各種數(shù)據(jù)結(jié)構(gòu)，如 vector, list, deque, set, map 用來存放數(shù)據(jù)。從實(shí)現(xiàn)的角度來看，STL 容器是一種 class template。
2、算法（algorithms）：各種常用的算法如 sort, search, copy, erase…從實(shí)現(xiàn)角度來看，STL 算法是一種 function template。
3、迭代器（iterators）：扮演容器與算法之間的膠合劑，是所謂的“泛型指針”。從實(shí)現(xiàn)角度來看，迭代器是一種將 operator *, operator ->, operator++, operator– 等指針相關(guān)操作予以重載的class template。
4、仿函數(shù)（functors）：行為類似函數(shù)，可以作為算法的某種策略。從實(shí)現(xiàn)角度來看，仿函數(shù)是一種重載了 operator() 的 class 或class template。
5、適配器（adapters）：一種用來修飾容器或仿函數(shù)或迭代器接口的東西。例如 STL 提供的 queue 和 stack，雖然看似容器，其實(shí)只能算是一種容器適配器，因?yàn)樗鼈兊牡撞客耆柚?deque，所有操作都由底層的 deque 供應(yīng)。
6、配置器（allocator）：負(fù)責(zé)空間配置與管理，從實(shí)現(xiàn)角度來看，配置器是一個(gè)實(shí)現(xiàn)了動(dòng)態(tài)空間配置、空間管理、空間釋放的 class template。
初學(xué)作圖，有點(diǎn)丑，還能看，嘿嘿
3. 何為空間配置器
3.1 為何需要先了解空間配置器？
從使用 STL 層面而言，空間配置器并不需要介紹 ，因?yàn)槿萜鞯讓佣冀o你包裝好了，但若是從 STL 實(shí)現(xiàn)角度出發(fā)，空間配置器是首要理解的。
作為 STL 設(shè)計(jì)背后的支撐，空間配置器總是在默默地付出著。為什么你可以使用算法來高效地處理數(shù)據(jù)，為什么你可以對容器進(jìn)行各種操作，為什么你用迭代器可以遍歷空間，這一切的一切，都有“空間配置器”的功勞。
3.2 SGI STL 專屬空間配置器
SGI STL 的空間配置器與眾不同，且與 STL 標(biāo)準(zhǔn)規(guī)范不同。
其名為 alloc，而非 allocator。
雖然 SGI 也配置了 allocatalor，但是它自己并不使用，也不建議我們使用，原因是效率比較感人，因?yàn)樗皇窃诨鶎舆M(jìn)行配置/釋放空間而已，而且不接受任何參數(shù)。
SGI STL 的每一個(gè)容器都已經(jīng)指定缺省的空間配置器是 alloc。
在 C++ 里，當(dāng)我們調(diào)用 new 和 delete 進(jìn)行對象的創(chuàng)建和銷毀的時(shí)候，也同時(shí)會(huì)有內(nèi)存配置操作和釋放操作:
這其中的 new 和 delete 都包含兩階段操作：
a. 對于 new 來說，編譯器會(huì)先調(diào)用 ::operator new 分配內(nèi)存；然后調(diào)用 Obj::Obj() 構(gòu)造對象內(nèi)容。
b. 對于 delete 來說，編譯器會(huì)先調(diào)用 Obj::~Obj() 析構(gòu)對象；然后調(diào)用? ::operator delete 釋放空間。
為了精密分工，STL allocator 決定將這兩個(gè)階段操作區(qū)分開來。
c. 對象構(gòu)造由 ::construct() 負(fù)責(zé)；對象釋放由 ::destroy() 負(fù)責(zé)。
d. 內(nèi)存配置由 alloc::allocate() 負(fù)責(zé)；內(nèi)存釋放由 alloc::deallocate() 負(fù)責(zé)；
STL配置器定義在中，下圖直觀的描述了這一框架結(jié)構(gòu)：
4. 構(gòu)造和析構(gòu)源碼
我們知道，程序內(nèi)存的申請和釋放離不開基本的構(gòu)造和析構(gòu)基本工具：construct() 和 destroy()?。
在 STL 里面，construct() 函數(shù)接受一個(gè)指針 P 和一個(gè)初始值 value，該函數(shù)的用途就是將初值設(shè)定到指針?biāo)傅目臻g上。
destroy() 函數(shù)有兩個(gè)版本，第一個(gè)版本接受一個(gè)指針，準(zhǔn)備將該指針?biāo)钢镂鰳?gòu)掉。直接調(diào)用析構(gòu)函數(shù)即可。
第二個(gè)版本接受 first 和 last 兩個(gè)迭代器，將[first,last)范圍內(nèi)的所有對象析構(gòu)掉。
其中 destroy() 只截取了部分源碼，全部實(shí)現(xiàn)還考慮到特化版本，比如判斷元素的數(shù)值類型 (value type) 是否有 trivial destructor 等限于篇幅，完整代碼請參閱《STL 源碼剖析》。
再來張圖吧，獻(xiàn)丑了。
5. 內(nèi)存的配置與釋放
前面所講都是對象的構(gòu)造和析構(gòu)，接下來要講的是對象構(gòu)造和析構(gòu)背后的故事—（內(nèi)存的分配與釋放），這塊是才真正的硬核，不要搞混了哦。
5.1 真· alloc 設(shè)計(jì)奧義
對象構(gòu)造和析構(gòu)之后的內(nèi)存管理諸項(xiàng)事宜，由
a. 向 system heap 要求空間
b. 考慮多線程 (multi-threads) 狀態(tài)
c. 考慮內(nèi)存不足時(shí)的應(yīng)變措施
d. 考慮過多“小型區(qū)塊”可能造成的內(nèi)存碎片 (fragment) 問題
考慮到小型區(qū)塊可能造成的內(nèi)存破碎問題，SGI 為此設(shè)計(jì)了雙層級配置器。當(dāng)配置區(qū)塊超過 128bytes 時(shí)，稱為足夠大，使用第一級配置器，直接使用 malloc() 和 free()。
當(dāng)配置區(qū)塊不大于 128bytes 時(shí)，為了降低額外負(fù)擔(dān)，直接使用第二級配置器，采用復(fù)雜的 memory pool 處理方式。
無論使用第一級配接器（__malloc_alloc_template）或是第二級配接器（__default_alloc_template），alloc 都為其包裝了接口，使其能夠符合 STL 標(biāo)準(zhǔn)。
其中， __malloc_alloc_template 就是第一級配置器;
__default_alloc_template 就是第二級配置器。
這么一大堆源碼看懵了吧，別著急，請看下圖。
其中 SGI STL 將配置器多了一層包裝使得 Alloc 具備標(biāo)準(zhǔn)接口。
6.?alloc 一級配置器源碼解讀
這里截取部分（精華）解讀
（1）第一級配置器以 malloc(), free(), realloc() 等 C 函數(shù)執(zhí)行實(shí)際的內(nèi)存配置、釋放和重配置操作，并實(shí)現(xiàn)類似 C++ new-handler 的機(jī)制（因?yàn)樗⒎鞘褂?::operator new 來配置內(nèi)存，所以不能直接使用C++ new-handler 機(jī)制）。
（2）SGI 第一級配置器的 allocate() 和 reallocate() 都是在調(diào)用malloc() 和 realloc() 不成功后，改調(diào)用 oom_malloc() 和oom_realloc()。
（3）oom_malloc()?和 oom_realloc() 都有內(nèi)循環(huán)，不斷調(diào)用“內(nèi)存不足處理例程”，期望某次調(diào)用后，獲得足夠的內(nèi)存而圓滿完成任務(wù)，哪怕有一絲希望也要全力以赴申請啊，如果用戶并沒有指定“內(nèi)存不足處理程序”，這個(gè)時(shí)候便無力乏天，真的是沒內(nèi)存了，STL 便拋出異常?；蛘{(diào)用exit(1) 終止程序。
7.?alloc 二級配置器源碼解讀
照例，還是截取部分（精華）源碼解讀。看累了嘛，遠(yuǎn)眺歇會(huì)，回來繼續(xù)看，接下來的這部分，將會(huì)更加的讓我們?yōu)榇髱煹闹腔壅鄯?/span>
第二級配置器多了一些機(jī)制，專門針對內(nèi)存碎片。內(nèi)存碎片化帶來的不僅僅是回收時(shí)的困難，配置也是一個(gè)負(fù)擔(dān)，額外負(fù)擔(dān)永遠(yuǎn)無法避免，畢竟系統(tǒng)要?jiǎng)澇鲞@么多的資源來管理另外的資源，但是區(qū)塊越小，額外負(fù)擔(dān)率就越高。
7.1 SGI 第二級配置器到底解決了多少問題呢？
簡單來說 SGI第二級配置器的做法是：sub-allocation （層次架構(gòu)）：
前面也說過了，SGI STL 的第一級配置器是直接使用 malloc()， free(), realloc() 并配合類似 C++ new-handler 機(jī)制實(shí)現(xiàn)的。第二級配置器的工作機(jī)制要根據(jù)區(qū)塊的大小是否大于 128bytes 來采取不同的策略：
繼續(xù)跟上節(jié)奏，上面提到了 memory pool ，相信程序員朋友們很熟悉這個(gè)名詞了，沒錯(cuò)，這就是二級配置器的精髓所在，如何理解？請看下圖：
有了內(nèi)存池，是不是就可以了，當(dāng)然沒有這么簡單。上圖中還提到了自由鏈表，這個(gè)又是何方神圣？
我們來一探究竟！
7.2 自由鏈表自由在哪？又該如何維護(hù)呢？
我們知道，一方面，自由鏈表中有些區(qū)塊已經(jīng)分配給了客端使用，所以 free_list 不需要再指向它們；另一方面，為了維護(hù) free-list，每個(gè)節(jié)點(diǎn)還需要額外的指針指向下一個(gè)節(jié)點(diǎn)。
那么問題來了，如果每個(gè)節(jié)點(diǎn)有兩個(gè)指針？這不就造成了額外負(fù)擔(dān)嗎？本來我們設(shè)計(jì) STL 容器就是用來保存對象的，這倒好，對象還沒保存之前，已經(jīng)占據(jù)了額外的內(nèi)存空間了。那么，有方法解決嗎？當(dāng)然有！再來感受一次大師的智慧！
（1）在這之前我們先來了解另一個(gè)概念——union（聯(lián)合體/共用體），對 union 已經(jīng)熟悉的讀者可以跳過這一部分的內(nèi)容；如果忘記了也沒關(guān)系，趁此來回顧一下：
（a）共用體是一種特殊的類，也是一種構(gòu)造類型的數(shù)據(jù)結(jié)構(gòu)。
（b）共用體表示幾個(gè)變量共用一個(gè)內(nèi)存位置，在不同的時(shí)間保存不同的數(shù)據(jù)類型和不同長度的變量。
（c）所有的共用體成員共用一個(gè)空間，并且同一時(shí)間只能儲(chǔ)存其中一個(gè)成員變量的值。例如如下：
一個(gè)union 只配置一個(gè)足夠大的空間以來容納最大長度的數(shù)據(jù)成員，以上例而言，最大長度是 double 類型，
所以 ChannelManager 的空間大小就是 double 數(shù)據(jù)類型的大小。在 C++ 里，union 的成員默認(rèn)屬性頁為 public。union 主要用來壓縮空間，如果一些數(shù)據(jù)不可能在同一時(shí)間同時(shí)被用到，則可以使用 union。
（2）了解了 union 之后，我們可以借助 union 的幫助，先來觀察一下 free-list 節(jié)點(diǎn)的結(jié)構(gòu)
來深入了解 free_list 的實(shí)現(xiàn)技巧，請看下圖。
在 union obj 中，定義了兩個(gè)字段，再結(jié)合上圖來分析：
從第一個(gè)字段看，obj 可以看做一個(gè)指針，指向鏈表中的下一個(gè)節(jié)點(diǎn)；
從第二個(gè)字段看，obj 可以也看做一個(gè)指針，不過此時(shí)是指向?qū)嶋H的內(nèi)存區(qū)。
一物二用的好處就是不會(huì)為了維護(hù)鏈表所必須的指針而造成內(nèi)存的另一種浪費(fèi)，或許這就是所謂的自由奧義所在！大師的智慧躍然紙上。
7.3 第二級配置器的部分實(shí)現(xiàn)內(nèi)容
到這里，我們已經(jīng)基本了解了第二級配置器中 free_list 的工作原理了。附上第二級配置器的部分實(shí)現(xiàn)內(nèi)容源碼：
太長了吧，看懵逼了，沒關(guān)系，請耐心接著往下看。
8. 空間配置器函數(shù)allocate源碼解讀
我們知道第二級配置器擁有配置器的標(biāo)準(zhǔn)接口函數(shù) allocate()。此函數(shù)首先判斷區(qū)塊的大小，如果大于 128bytes –> 調(diào)用第一級配置器；小于128bytes–> 就檢查對應(yīng)的 free_list（如果沒有可用區(qū)塊，就將區(qū)塊上調(diào)至 8 倍數(shù)的邊界，然后調(diào)用 refill(), 為 free list 重新填充空間。
8.1 空間申請
調(diào)用標(biāo)準(zhǔn)接口函數(shù) allocate()：
NOTE：每次都是從對應(yīng)的 free_list 的頭部取出可用的內(nèi)存塊。然后對free_list 進(jìn)行調(diào)整，使上一步撥出的內(nèi)存的下一個(gè)節(jié)點(diǎn)變?yōu)轭^結(jié)點(diǎn)。
8.2?空間釋放
同樣，作為第二級配置器擁有配置器標(biāo)準(zhǔn)接口函數(shù) deallocate()。該函數(shù)首先判斷區(qū)塊大小，大于 128bytes 就調(diào)用第一級配置器。小于 128bytes 就找出對應(yīng)的 free_list，將區(qū)塊回收。
NOTE：通過調(diào)整free_ list鏈表將區(qū)塊放入free list的頭部。
區(qū)塊回收納入 free_list 的操作，如圖所示：
8.3 重新填充 free_lists
（1）當(dāng)發(fā)現(xiàn) free list 中沒有可用區(qū)塊時(shí)，就會(huì)調(diào)用 refill() 為free_list 重新填充空間；
（2）新的空間將取自內(nèi)存池（經(jīng)由 chunk_alloc() 完成）；
（3）缺省取得20個(gè)新節(jié)點(diǎn)（區(qū)塊），但萬一內(nèi)存池空間不足，獲得的節(jié)點(diǎn)數(shù)可能小于 20。
8.4 內(nèi)存池（memory pool）
唔…在前面提到了 memory pool，現(xiàn)在終于輪到這個(gè)大 boss 上場。
首先，我們要知道從內(nèi)存池中取空間給 free_list 使用，是 chunk_alloc() 在工作，它是怎么工作的呢？
我們先來分析 chunk_alloc() 的工作機(jī)制：
chunk_alloc() 函數(shù)以 end_free – start_free 來判斷內(nèi)存池的“水量”（哈哈，很形象的比喻）。
具體邏輯都在下面的圖里了，很形象吧。
如果第一級配置器的 malloc()?也失敗了，就發(fā)出 bad_alloc 異常。
說了這么多來看一下 STL 的源碼吧。
太長了，又看懵逼了吧，沒關(guān)系，請看下圖。
NOTE：上述就是 STL 源碼當(dāng)中實(shí)際內(nèi)存池的操作原理，我們可以看到其實(shí)以共用體串聯(lián)起來共享內(nèi)存形成了free_list的實(shí)質(zhì)組成。
9.本文小結(jié)
STL 源碼本身博大精深，還有很多精妙的設(shè)計(jì)等著大家去探索。
小賀本人才疏學(xué)淺，在這里也只是在自己掌握的程度下寫出自己的理解，不足之處希望對大家多多指出，互相討論學(xué)習(xí)。
這篇肝了一個(gè)禮拜的文章，在周日的晚上終于寫完了，文中所有的圖都是自己一個(gè)個(gè)親手畫的，不畫不知道，畫完之后真心感覺不容易啊。
第一次寫這種圖解的文章，不知道讀者朋友們喜不喜歡。如果反饋還不錯(cuò)的話，后面有時(shí)間會(huì)繼續(xù)更新類型的圖解文章。
參考文章：
《STL源碼剖析-侯捷》
https://cloud.tencent.com/developer/article/1686585
https://dulishu.top/allocator-of-stl/
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！
下載文檔
