TCMalloc是 Google 開發(fā)的內(nèi)存分配器谎痢，在不少項(xiàng)目中都有使用艘蹋，例如在 Golang 中就使用了類似的算法進(jìn)行內(nèi)存分配。它具有現(xiàn)代化內(nèi)存分配器的基本特征：對(duì)抗內(nèi)存碎片、在多核處理器能夠 scale挠他。據(jù)稱，它的內(nèi)存分配速度是 glibc2.3 中實(shí)現(xiàn)的 malloc的數(shù)倍篡帕。Golang的內(nèi)存管理就用了鼎鼎大名的 TCMalloc

總體結(jié)構(gòu)

在tcmalloc內(nèi)存管理的體系之中绩社，一共有三個(gè)層次：ThreadCache、CentralCache赂苗、PageHeap愉耙。
分配內(nèi)存和釋放內(nèi)存的時(shí)候都是按從前到后的順序，在各個(gè)層次中去進(jìn)行嘗試拌滋∑友兀基本思想是：前面的層次分配內(nèi)存失敗，則從下一層分配一批補(bǔ)充上來；前面的層次釋放了過多的內(nèi)存赌渣，則回收一批到下一層次魏铅。

這幾個(gè)層次從前到后，主要有這么幾方面的變化：

線程私有性：ThreadCache坚芜，顧名思義览芳，是每個(gè)線程一份的。理想情況下鸿竖，每個(gè)線程的內(nèi)存需求都在自己的ThreadCache里面完成沧竟，線程之間不需要競爭，非常高效缚忧。而CentralCache和PageHeap則是全局的悟泵；

內(nèi)存分配粒度：在tcmalloc里面，有兩種粒度的內(nèi)存闪水，object和span糕非。span是連續(xù)page的內(nèi)存，而object則是由span切成的小塊球榆。object的尺寸被預(yù)設(shè)了一些規(guī)格（class）朽肥，比如16字節(jié)、32字節(jié)持钉、等等鞠呈，同一個(gè)span切出來的object都是相同的規(guī)格。object不大于256K右钾，超大的內(nèi)存將直接分配span來使用蚁吝。ThreadCache和CentralCache都是管理object，而PageHeap管理的是span舀射。

ThreadCache

比較簡單窘茁，最主要的邏輯是維護(hù)一組FreeList，針對(duì)每一種class的object脆烟；

CentralCache

里面有多個(gè)CentralFreeList山林，針對(duì)每一種class的object。
CentralFreeList并不像ThreadCache那樣直接維護(hù)object的鏈表邢羔，而是維護(hù)span的鏈表驼抹，每個(gè)span下面再掛一個(gè)由這個(gè)span切分出來的object的鏈。這樣做便于在span內(nèi)的object是否都已經(jīng)free的情況下拜鹤，將span整體回收給PageHeap（span.refcount_記錄了被分配出去的object個(gè)數(shù)）框冀。但是這樣一來，每個(gè)回收回來的object都需要尋找自己所屬的span敏簿，然后才能掛進(jìn)freelist明也，過程會(huì)比較耗時(shí)宣虾。
所以CentralFreeList里面還搞了一個(gè)cache（tc_slots_），回收回來的一批object先往cache里面塞温数，塞不下了再回收進(jìn)span的objects鏈绣硝。分配object給ThreadCache時(shí)也是先嘗試在cache里面拿，沒了再去span里面分配撑刺。
多少個(gè)object算做是一批鹉胖？這都是預(yù)定義好的（稱作batch_size，比如32個(gè)）够傍，不同的class可能有不同的值甫菠。ThreadCache向CentralCache分配和回收object時(shí)，都盡量以batch_size為一個(gè)批次王带。而為了cache的簡單高效，如果批次個(gè)數(shù)不等于batch_size市殷，則會(huì)繞過cache愕撰。
另外，CentralFreeList里的span鏈表其實(shí)是有兩個(gè)：nonempty_和empty_醋寝，根據(jù)span的objects鏈?zhǔn)欠裼锌臻e搞挣，放入對(duì)應(yīng)鏈表。這樣就避免了在分配時(shí)去判斷span是否為空音羞，只需要在由空變非空囱桨、或者由非空變空時(shí)移動(dòng)一下span。

PageHeap

維護(hù)了兩個(gè)很重要的東西：page到span的映射關(guān)系嗅绰，和空閑span的伙伴系統(tǒng)舍肠。

當(dāng)應(yīng)用free()一個(gè)地址的時(shí)候，怎么知道該把它對(duì)應(yīng)的object放回哪里去呢窘面？tcmalloc里面并沒有針對(duì)object的控制結(jié)構(gòu)翠语，要解決這個(gè)問題，page到span的映射關(guān)系至關(guān)重要财边。地址值經(jīng)過地址對(duì)齊肌括，很容易知道它屬于哪一個(gè)page。再通過page到span的映射關(guān)系就能知道object應(yīng)該放到哪里酣难。span.sizeclass記錄了span被切分成的object屬于哪一個(gè)class谍夭，那么屬于這個(gè)span的object在free時(shí)就應(yīng)該放到ThreadCache對(duì)應(yīng)class的FreeList上面去；如果object需要放回CentralCache憨募，直接把它掛到對(duì)應(yīng)span的objects鏈表上即可紧索。

page到span的映射關(guān)系通過radix tree來實(shí)現(xiàn)，邏輯上可以把它理解為一個(gè)大數(shù)組菜谣，以page的值作為偏移齐板，就能訪問到page所對(duì)應(yīng)的節(jié)點(diǎn)。這個(gè)節(jié)點(diǎn)上面其實(shí)就是一個(gè)指針，指向這個(gè)page所對(duì)應(yīng)的span（注意甘磨，可能有多個(gè)page指向同一個(gè)span橡羞，因?yàn)閟pan的尺寸可能不止一個(gè)page）。
為減少查詢r(jià)adix tree的開銷济舆，PageHeap還維護(hù)了一個(gè)最近最常使用的若干個(gè)page到class（span.sizeclass）的對(duì)應(yīng)關(guān)系cache卿泽。為了保持cache的效率，cache只提供64K個(gè)固定坑位滋觉，舊的對(duì)應(yīng)關(guān)系會(huì)被新來的對(duì)應(yīng)關(guān)系替換掉签夭。

空閑span的伙伴系統(tǒng)為上層提供span的分配與回收。當(dāng)需要的span沒有空閑時(shí)椎侠，可以把更大尺寸的span拆械谧狻（如果大的span都沒有了，則需要重新找kernel分配）我纪；當(dāng)span回收時(shí)慎宾，又需要判斷相鄰的span是否空閑，以便將它們組合浅悉。判斷相鄰span還是要用到radix tree趟据，radix tree就像一個(gè)大數(shù)組，很容易取到當(dāng)前span前后相鄰的span术健。
span的尺寸有從1個(gè)page到255個(gè)page的所有規(guī)格汹碱，所以span總是可以按任意尺寸進(jìn)行拆分和組合（當(dāng)然是page粒度的）。大于255個(gè)page的span單獨(dú)歸為一類荞估，不作細(xì)分咳促。

伙伴系統(tǒng)的freelist其實(shí)是有兩個(gè)鏈，normal和returned勘伺，以區(qū)別活躍跟不活躍的內(nèi)存等缀。PageHeap并不會(huì)將內(nèi)存釋放給kernel，因?yàn)樗鼈冎g的交互都是針對(duì)一批連續(xù)page的娇昙，要想回收到整批的page尺迂，可能性很小。在PageHeap里面冒掌，多余的內(nèi)存會(huì)放到returned里面去噪裕，跟normal做一下隔離。這樣一來股毫，normal的內(nèi)存總是優(yōu)先被使用膳音，kernel傾向于一直保留它們。而returned的內(nèi)存則不常被使用铃诬，kernel在內(nèi)存不夠的時(shí)候會(huì)優(yōu)先將它們swap掉祭陷。
其實(shí)不用returned也能完成這樣的事情苍凛，因?yàn)閚ormal是個(gè)鏈表，每次分配回收總是作用在鏈表頭上兵志，那么鏈表內(nèi)的span本身就按從熱到冷的順序排序了醇蝴。鏈表尾部的span如果長期不被使用，不管是否移動(dòng)到returned鏈想罕，kernel都會(huì)傾向于將它們swap掉悠栓。不過，span進(jìn)入returned時(shí)按价，tcmalloc還附加了一個(gè)操作惭适，madvise(MADV_DONTNEED)，試圖告訴kernel這個(gè)內(nèi)存已經(jīng)不用了（kernel具體會(huì)怎么做楼镐，那就是另外一回事了）癞志。
所以，在伙伴系統(tǒng)中分配span時(shí)框产，會(huì)有三個(gè)過程：優(yōu)先在normal鏈中分配凄杯、嘗試未果則在returned鏈中分配、還搞不定就向kernel去申請(qǐng)新的內(nèi)存茅信。

在PageHeap里面盾舌，還有一個(gè)PageHeapAllocator墓臭，專門用于分配各種控制結(jié)構(gòu)的內(nèi)存蘸鲸，比如span、ThreadCache窿锉、等酌摇。可見嗡载，在tcmalloc里面控制結(jié)構(gòu)與object是分離的窑多。而object自身并不需要額外的控制結(jié)構(gòu)，當(dāng)它被分配時(shí)洼滚，它的所有內(nèi)存空間都服務(wù)于使用者埂息；而當(dāng)它空閑時(shí)，它的第一個(gè)8Byte空間被當(dāng)作鏈表指針遥巴，鏈在各種freelist里面千康。

分配回收過程

再通過malloc和free兩個(gè)過程把上述邏輯串起來看一看：

alloc

根據(jù)分配size，判斷是小塊內(nèi)存還是大塊內(nèi)存（256K為界）铲掐；
小塊內(nèi)存：
通過size得到對(duì)應(yīng)的class拾弃；
先嘗試在ThreadCache.list_[class]的FreeList里面分配，分配成功則直接返回摆霉；
嘗試在CentralCache里面分配batch_size個(gè)object豪椿，其中一個(gè)用于返回奔坟，其他的都加進(jìn)ThreadCache.list_[class]；
拿到class對(duì)應(yīng)的CentralFreeList搭盾；
嘗試在CentralFreeList.tc_slots_[]里面分配（CentralFreeList.used_slots_是空閑slot游標(biāo)）咳秉；
嘗試在CentralFreeList.nonempty_里面分配，盡量分配batch_size個(gè)object增蹭。但最后只要分配了多于一個(gè)object滴某，即可返回；
如果CentralFreeList.nonempty_為空滋迈，則要向PageHeap去申請(qǐng)一個(gè)span霎奢。對(duì)應(yīng)的class申請(qǐng)的span應(yīng)該包含多少個(gè)連續(xù)page，這個(gè)也是預(yù)設(shè)好的饼灿。拿到span之后將其拆分成N個(gè)object幕侠，然后返回前面所需要的object；
PageHeap先從伙伴系統(tǒng)對(duì)應(yīng)npages的span鏈表里面查找空閑的span（優(yōu)先查normal鏈碍彭、然后returned鏈）晤硕，有則直接返回；
在更大npages的span里面查找空閑的span（優(yōu)先查normal鏈庇忌、然后returned鏈）舞箍，有則將其拆小，并返回所需要的span皆疹；
向kernel申請(qǐng)若干個(gè)page的內(nèi)存（可能大于npage）疏橄，返回所需要的span，其他的span放回伙伴系統(tǒng)略就；
大塊內(nèi)存：
直接向PageHeap去申請(qǐng)一個(gè)剛好大于等于請(qǐng)求size的span捎迫。申請(qǐng)過程與小塊內(nèi)存走到這一步時(shí)的過程一致；

free

通過釋放的ptr表牢，在PageHeap維護(hù)的映射關(guān)系中窄绒，找到對(duì)應(yīng)span的class（先嘗試在cache里面找，沒有再查radix tree崔兴，然后插入cache彰导。cache里面自動(dòng)淘汰老的項(xiàng)）。class為0代表ptr指向的是大塊內(nèi)存敲茄；
小塊內(nèi)存：
將ptr指向的內(nèi)存釋放到ThreadCache.list_[class]里面位谋；
如果ThreadCache.list_[class]長度超過閾值（FreeList.length_>=FreeList.max_length_），或者ThreadCache的容量超過閾值（ThreadCache.size_>=ThreadCache.max_size_）折汞，則觸發(fā)回收過程倔幼。兩種情況分別針對(duì)class對(duì)應(yīng)的FreeList，和ThreadCache下面的所有FreeList進(jìn)行回收（具體的策略后續(xù)再討論）爽待；
object被回收到CentralCache里面class對(duì)應(yīng)的CentralFreeList上损同。先嘗試batch_size個(gè)object的整塊回收翩腐，CentralFreeList會(huì)試圖將其釋放到自己的cache里面去（tc_slots_）；
如果cache裝滿膏燃，或者湊不滿batch_size個(gè)整數(shù)的object茂卦，則單個(gè)回收，回收進(jìn)其對(duì)應(yīng)的span.objects组哩。這個(gè)回收過程不必拿著object在CentralFreeList的span鏈表中逐個(gè)去尋找自己對(duì)應(yīng)的span等龙，而是通過PageHeap中的對(duì)應(yīng)關(guān)系直接找到span；
如果span下面的object都已經(jīng)回收了（refcount_減為0）伶贰，則進(jìn)一步將其釋放回PageHeap蛛砰；
在radix tree中找到span之前和這后的span，如果它們空閑且也在normal鏈上黍衙，則進(jìn)行合并泥畅；
PageHeap將多余的span回收到其對(duì)應(yīng)的returned鏈上，然后繼續(xù)考慮span之間的合并（要求span都在returned鏈上）（具體策略后續(xù)再討論）琅翻；
大塊內(nèi)存：
ptr對(duì)應(yīng)的直接就是一個(gè)span位仁，直接將其釋放回PageHeap即可；

回收策略

tcmalloc的主要數(shù)據(jù)結(jié)構(gòu)基本上就是這些了方椎。上面討論的時(shí)候聂抢，有一個(gè)細(xì)節(jié)一直沒深入：每一個(gè)層次在空閑量達(dá)到一定閾值的時(shí)候，會(huì)向下做一次釋放棠众。那么這個(gè)閾值該怎么定呢琳疏？

CentralCache => PageHeap

span從CentralCache回收到PageHeap的過程比較簡單，只要一個(gè)span里面的object都空閑了摄欲，就將它回收到PageHeap轿亮；

normal => returned

在PageHeap中疮薇，span從normal鏈表回收到returned鏈表的過程則略復(fù)雜一些：
考慮到這個(gè)過程是很偏避的一個(gè)邏輯胸墙，span是否移到returned鏈表對(duì)整體性能而言差別并不會(huì)太大，所以盡量lazy按咒〕儆纾基本思路是，每當(dāng)PageHeap回收到N個(gè)page的span時(shí)（這個(gè)過程中可能伴隨著相當(dāng)數(shù)目的span分配）励七，觸發(fā)一次normal到returned的回收智袭，只回收一個(gè)span。
這個(gè)N值初始化為1G內(nèi)存的page數(shù)掠抬，每次回收span到returned鏈之后吼野，可能還會(huì)增加N值，但是最大不超過4G两波。
觸發(fā)回收的過程也比較簡單瞳步，每次進(jìn)來輪詢伙伴系統(tǒng)中的一個(gè)normal鏈表闷哆，將鏈尾的span回收即可。
這里面沒有判斷normal鏈?zhǔn)欠駪?yīng)該被回收单起，如果回收了不該回收的span抱怔，后續(xù)的分配過程會(huì)把span從returned鏈里面撈回來。否則span將長期呆在returned鏈里面嘀倒。

ThreadCache => CentralCache

ThreadCache是tcmalloc的核心屈留，它里面的FreeList長度控制還是比較復(fù)雜的。
前面提到過测蘑，F(xiàn)reeList長度超過限額和ThreadCache容量超過限額灌危，這兩種情況下會(huì)觸發(fā)object回收√几欤考慮到應(yīng)用程序的多樣性乍狐，這兩個(gè)限額不能是定死的，必需得自適應(yīng)：有些線程對(duì)內(nèi)存的需求可能遠(yuǎn)多于其他一些線程固逗、有些線程可能總是在分配內(nèi)存而另一些線程則總是釋放內(nèi)存（生產(chǎn)者消費(fèi)者）浅蚪、等等。

先來看ThreadCache的容量限額烫罩，其思想是：為每一個(gè)ThreadCache初始化一個(gè)比較小的限額惜傲，然后每當(dāng)ThreadCache由于cache超限而觸發(fā)object到CentralCache的回收時(shí)，就增大該ThreadCache的限額贝攒。有限額增大盗誊，就應(yīng)該有限額回收。tcmalloc預(yù)設(shè)了一個(gè)所有ThreadCache的總?cè)萘堪祝?dāng)ThreadCache需要增大容量時(shí)哈踱，如果總?cè)萘可杏杏囝~，則使用這些余額梨熙。否則需要增大的容量就從其他線程的ThreadCache里面去收刮（具體從收刮哪個(gè)線程的容量开镣，簡單采用了輪詢的方式）。這樣一來咽扇，只需要在ThreadCache內(nèi)存回收時(shí)做一些簡單的處理邪财，就能實(shí)現(xiàn)ThreadCache的容量的自適應(yīng)：內(nèi)存需求大的線程總是收刮別人的容量，而內(nèi)存需求低的線程則總是被收刮质欲。當(dāng)然树埠，收刮與被收刮并不是無節(jié)制的，會(huì)有一個(gè)最大值最小值的限制嘶伟，比如128字節(jié)~4M怎憋。
到達(dá)ThreadCache的容量限額時(shí)，會(huì)對(duì)它下面的每一個(gè)FreeList進(jìn)行回收九昧，回收的數(shù)目是該Freelist.lowator_的一半绊袋。什么是lowator_呢赠橙？就是該Freelist在ThreadCache超限的兩次回收周期之間內(nèi)，F(xiàn)reeList的最小長度愤炸。也就是說期揪，在上一個(gè)周期中，F(xiàn)reeList里面有l(wèi)owator_個(gè)object是從未被用到的规个。通過這一歷史信息凤薛，可以預(yù)估在下一次回收到來時(shí)，可能也有l(wèi)owator_個(gè)object可能不會(huì)被用到诞仓。不過保守一點(diǎn)缤苫，只回收lowator_的一半。
回收過程其實(shí)只是對(duì)每一個(gè)FreeList的保守回收墅拭，回收完成之后ThreadCache的容量可能還會(huì)繼續(xù)高于限額活玲，不過隨著這次回收，ThreadCache的容量限額也會(huì)被抬高谍婉。

下一個(gè)問題是單個(gè)FreeList的限額舒憾，tcmalloc采用慢啟動(dòng)策略，每個(gè)FreeList初始時(shí)長度限額為1穗熬。在限額為1~batch_size之間時(shí)镀迂，為慢啟動(dòng)狀態(tài)。此時(shí)唤蔗，不管是alloc遇到空FreeList探遵、還是free遇到長度超限，都給限額加1妓柜。這樣做可以給不常用或者使用很規(guī)律的object確定一個(gè)合適的限額箱季，而如果object的使用抖動(dòng)較大的話，應(yīng)該給它一個(gè)更大的buffer棍掐。
如果限額增加達(dá)到batch_size藏雏，則慢啟動(dòng)狀態(tài)結(jié)束。此時(shí)塌衰，如果alloc遇到空FreeList诉稍，限額會(huì)按batch_size的整數(shù)倍進(jìn)行擴(kuò)展蝠嘉。而如果free超限最疆，則限額將按照batch_size的整數(shù)倍進(jìn)行縮減。
alloc遇到空FreeList（說明FreeList的限額達(dá)不到線程的分配需求）蚤告，應(yīng)該不斷增加限額努酸，這個(gè)好理解。那么free超限的情況下杜恰，為什么慢啟動(dòng)狀態(tài)下要增加限額获诈，非慢啟動(dòng)狀態(tài)則要減少限額呢仍源？如果free總是超限，說明線程對(duì)object的free要多于alloc舔涎，線程之間對(duì)該object的分配回收很可能是不對(duì)稱的笼踩。那么作為專職回收的那個(gè)線程，沒必要給他留大的限額亡嫌，因?yàn)樗姆峙湫枨蠛苌俸坑凇６龁?dòng)狀態(tài)下超限還給限額做加1遞增，一方面可以應(yīng)對(duì)抖動(dòng)挟冠，另一方面遞增限額的目的是使之能夠達(dá)到batch_size（如果free確實(shí)遠(yuǎn)多于alloc話）于购，從而在回收object時(shí)可以按batch_size批量回收。
FreeList限額超限的處理比較簡單知染，直接回收batch_size個(gè)object即可（不足batch_size個(gè)肋僧，則有多少回收多少）】氐可見嫌吠，處于慢啟動(dòng)狀態(tài)下的FreeList限額超限，將導(dǎo)致FreeList被清空掺炭。