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里面完成，線程之間不需要競(jìng)爭(zhēng)，非常高效。而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

比較簡(jiǎn)單，最主要的邏輯是維護(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的簡(jiǎn)單高效，如果批次個(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拆?。ㄈ绻蟮膕pan都沒有了，則需要重新找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如果長(zhǎng)期不被使用，不管是否移動(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]長(zhǎng)度超過閾值（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的過程比較簡(jiǎn)單，只要一個(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ā)回收的過程也比較簡(jiǎn)單，每次進(jìn)來輪詢伙伴系統(tǒng)中的一個(gè)normal鏈表，將鏈尾的span回收即可。
這里面沒有判斷normal鏈?zhǔn)欠駪?yīng)該被回收，如果回收了不該回收的span，后續(xù)的分配過程會(huì)把span從returned鏈里面撈回來。否則span將長(zhǎng)期呆在returned鏈里面。

ThreadCache => CentralCache

ThreadCache是tcmalloc的核心，它里面的FreeList長(zhǎng)度控制還是比較復(fù)雜的。
前面提到過，F(xiàn)reeList長(zhǎng)度超過限額和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è)線程的容量，簡(jiǎn)單采用了輪詢的方式）。這樣一來，只需要在ThreadCache內(nèi)存回收時(shí)做一些簡(jiǎn)單的處理，就能實(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的最小長(zhǎng)度。也就是說，在上一個(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í)長(zhǎng)度限額為1。在限額為1~batch_size之間時(shí)，為慢啟動(dòng)狀態(tài)。此時(shí)，不管是alloc遇到空FreeList、還是free遇到長(zhǎng)度超限，都給限額加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限額超限的處理比較簡(jiǎn)單，直接回收batch_size個(gè)object即可（不足batch_size個(gè)，則有多少回收多少）?？梢?，處于慢啟動(dòng)狀態(tài)下的FreeList限額超限，將導(dǎo)致FreeList被清空。