422
tcmalloc淺析
最近因debug需要，閱讀了一下慕名已久的tcmalloc，略記一些自己的理解。
一圖勝千言：
總體結構
在tcmalloc內存管理的體係之中，一共有三個層次：ThreadCache、CentralCache、PageHeap，如上圖所示。
分配內存和釋放內存的時候都是按從前到後的順序，在各個層次中去進行嚐試。基本思想是：前麵的層次分配內存失敗，則從下一層分配一批補充上來；前麵的層次釋放了過多的內存，則回收一批到下一層次。
這幾個層次從前到後，主要有這麼幾方麵的變化：
- 線程私有性：ThreadCache，顧名思義，是每個線程一份的。理想情況下，每個線程的內存需求都在自己的ThreadCache裏麵完成，線程之間不需要競爭，非常高效。而CentralCache和PageHeap則是全局的；
- 內存分配粒度：在tcmalloc裏麵，有兩種粒度的內存，object和span。span是連續page的內存，而object則是由span切成的小塊。object的尺寸被預設了一些規格（class），比如16字節、32字節、等等，同一個span切出來的object都是相同的規格。object不大於256K，超大的內存將直接分配span來使用。ThreadCache和CentralCache都是管理object，而PageHeap管理的是span。
ThreadCache
比較簡單，最主要的邏輯是維護一組FreeList，針對每一種class的object；
CentralCache
裏麵有多個CentralFreeList，針對每一種class的object。
CentralFreeList並不像ThreadCache那樣直接維護object的鏈表，而是維護span的鏈表，每個span下麵再掛一個由這個span切分出來的object的鏈。這樣做便於在span內的object是否都已經free的情況下，將span整體回收給PageHeap（span.refcount_記錄了被分配出去的object個數）。但是這樣一來，每個回收回來的object都需要尋找自己所屬的span，然後才能掛進freelist，過程會比較耗時。
所以CentralFreeList裏麵還搞了一個cache（tc_slots_），回收回來的一批object先往cache裏麵塞，塞不下了再回收進span的objects鏈。分配object給ThreadCache時也是先嚐試在cache裏麵拿，沒了再去span裏麵分配。
多少個object算做是一批？這都是預定義好的（稱作batch_size，比如32個），不同的class可能有不同的值。ThreadCache向CentralCache分配和回收object時，都盡量以batch_size為一個批次。而為了cache的簡單高效，如果批次個數不等於batch_size，則會繞過cache。
另外，CentralFreeList裏的span鏈表其實是有兩個：nonempty_和empty_，根據span的objects鏈是否有空閑，放入對應鏈表。這樣就避免了在分配時去判斷span是否為空，隻需要在由空變非空、或者由非空變空時移動一下span。
PageHeap
維護了兩個很重要的東西：page到span的映射關係，和空閑span的夥伴係統。
當應用free()一個地址的時候，怎麼知道該把它對應的object放回哪裏去呢？tcmalloc裏麵並沒有針對object的控製結構，要解決這個問題，page到span的映射關係至關重要。地址值經過地址對齊，很容易知道它屬於哪一個page。再通過page到span的映射關係就能知道object應該放到哪裏。span.sizeclass記錄了span被切分成的object屬於哪一個class，那麼屬於這個span的object在free時就應該放到ThreadCache對應class的FreeList上麵去；如果object需要放回CentralCache，直接把它掛到對應span的objects鏈表上即可。
page到span的映射關係通過radix tree來實現，邏輯上可以把它理解為一個大數組，以page的值作為偏移，就能訪問到page所對應的節點。這個節點上麵其實就是一個指針，指向這個page所對應的span（注意，可能有多個page指向同一個span，因為span的尺寸可能不止一個page）。
為減少查詢radix tree的開銷，PageHeap還維護了一個最近最常使用的若幹個page到class（span.sizeclass）的對應關係cache。為了保持cache的效率，cache隻提供64K個固定坑位，舊的對應關係會被新來的對應關係替換掉。
空閑span的夥伴係統為上層提供span的分配與回收。當需要的span沒有空閑時，可以把更大尺寸的span拆小（如果大的span都沒有了，則需要重新找kernel分配）；當span回收時，又需要判斷相鄰的span是否空閑，以便將它們組合。判斷相鄰span還是要用到radix tree，radix tree就像一個大數組，很容易取到當前span前後相鄰的span。
span的尺寸有從1個page到255個page的所有規格，所以span總是可以按任意尺寸進行拆分和組合（當然是page粒度的）。大於255個page的span單獨歸為一類，不作細分。
夥伴係統的freelist其實是有兩個鏈，normal和returned，以區別活躍跟不活躍的內存。PageHeap並不會將內存釋放給kernel，因為它們之間的交互都是針對一批連續page的，要想回收到整批的page，可能性很小。在PageHeap裏麵，多餘的內存會放到returned裏麵去，跟normal做一下隔離。這樣一來，normal的內存總是優先被使用，kernel傾向於一直保留它們。而returned的內存則不常被使用，kernel在內存不夠的時候會優先將它們swap掉。
其實不用returned也能完成這樣的事情，因為normal是個鏈表，每次分配回收總是作用在鏈表頭上，那麼鏈表內的span本身就按從熱到冷的順序排序了。鏈表尾部的span如果長期不被使用，不管是否移動到returned鏈，kernel都會傾向於將它們swap掉。不過，span進入returned時，tcmalloc還附加了一個操作，madvise(MADV_DONTNEED)，試圖告訴kernel這個內存已經不用了（kernel具體會怎麼做，那就是另外一回事了）。
所以，在夥伴係統中分配span時，會有三個過程：優先在normal鏈中分配、嚐試未果則在returned鏈中分配、還搞不定就向kernel去申請新的內存。
在PageHeap裏麵，還有一個PageHeapAllocator，專門用於分配各種控製結構的內存，比如span、ThreadCache、等。可見，在tcmalloc裏麵控製結構與object是分離的。而object自身並不需要額外的控製結構，當它被分配時，它的所有內存空間都服務於使用者；而當它空閑時，它的第一個8Byte空間被當作鏈表指針，鏈在各種freelist裏麵。
分配回收過程
再通過malloc和free兩個過程把上述邏輯串起來看一看：
alloc
- 根據分配size，判斷是小塊內存還是大塊內存（256K為界）；
- 小塊內存：
- 通過size得到對應的class；
- 先嚐試在ThreadCache.list_[class]的FreeList裏麵分配，分配成功則直接返回；
- 嚐試在CentralCache裏麵分配batch_size個object，其中一個用於返回，其他的都加進ThreadCache.list_[class]；
- 拿到class對應的CentralFreeList；
- 嚐試在CentralFreeList.tc_slots_[]裏麵分配（CentralFreeList.used_slots_是空閑slot遊標）；
- 嚐試在CentralFreeList.nonempty_裏麵分配，盡量分配batch_size個object。但最後隻要分配了多於一個object，即可返回；
- 如果CentralFreeList.nonempty_為空，則要向PageHeap去申請一個span。對應的class申請的span應該包含多少個連續page，這個也是預設好的。拿到span之後將其拆分成N個object，然後返回前麵所需要的object；
- PageHeap先從夥伴係統對應npages的span鏈表裏麵查找空閑的span（優先查normal鏈、然後returned鏈），有則直接返回；
- 在更大npages的span裏麵查找空閑的span（優先查normal鏈、然後returned鏈），有則將其拆小，並返回所需要的span；
- 向kernel申請若幹個page的內存（可能大於npage），返回所需要的span，其他的span放回夥伴係統；
- 大塊內存：
- 直接向PageHeap去申請一個剛好大於等於請求size的span。申請過程與小塊內存走到這一步時的過程一致；
free
- 通過釋放的ptr，在PageHeap維護的映射關係中，找到對應span的class（先嚐試在cache裏麵找，沒有再查radix tree，然後插入cache。cache裏麵自動淘汰老的項）。class為0代表ptr指向的是大塊內存；
- 小塊內存：
- 將ptr指向的內存釋放到ThreadCache.list_[class]裏麵；
- 如果ThreadCache.list_[class]長度超過閾值（FreeList.length_>=FreeList.max_length_），或者ThreadCache的容量超過閾值（ThreadCache.size_>=ThreadCache.max_size_），則觸發回收過程。兩種情況分別針對class對應的FreeList，和ThreadCache下麵的所有FreeList進行回收（具體的策略後續再討論）；
- object被回收到CentralCache裏麵class對應的CentralFreeList上。先嚐試batch_size個object的整塊回收，CentralFreeList會試圖將其釋放到自己的cache裏麵去（tc_slots_）；
- 如果cache裝滿，或者湊不滿batch_size個整數的object，則單個回收，回收進其對應的span.objects。這個回收過程不必拿著object在CentralFreeList的span鏈表中逐個去尋找自己對應的span，而是通過PageHeap中的對應關係直接找到span；
- 如果span下麵的object都已經回收了（refcount_減為0），則進一步將其釋放回PageHeap；
- 在radix tree中找到span之前和這後的span，如果它們空閑且也在normal鏈上，則進行合並；
- PageHeap將多餘的span回收到其對應的returned鏈上，然後繼續考慮span之間的合並（要求span都在returned鏈上）（具體策略後續再討論）；
- 大塊內存：
- ptr對應的直接就是一個span，直接將其釋放回PageHeap即可；
回收策略
tcmalloc的主要數據結構基本上就是這些了。上麵討論的時候，有一個細節一直沒深入：每一個層次在空閑量達到一定閾值的時候，會向下做一次釋放。那麼這個閾值該怎麼定呢？
CentralCache => PageHeap
span從CentralCache回收到PageHeap的過程比較簡單，隻要一個span裏麵的object都空閑了，就將它回收到PageHeap；
normal => returned
在PageHeap中，span從normal鏈表回收到returned鏈表的過程則略複雜一些：
考慮到這個過程是很偏避的一個邏輯，span是否移到returned鏈表對整體性能而言差別並不會太大，所以盡量lazy。基本思路是，每當PageHeap回收到N個page的span時（這個過程中可能伴隨著相當數目的span分配），觸發一次normal到returned的回收，隻回收一個span。
這個N值初始化為1G內存的page數，每次回收span到returned鏈之後，可能還會增加N值，但是最大不超過4G。
觸發回收的過程也比較簡單，每次進來輪詢夥伴係統中的一個normal鏈表，將鏈尾的span回收即可。
這裏麵沒有判斷normal鏈是否應該被回收，如果回收了不該回收的span，後續的分配過程會把span從returned鏈裏麵撈回來。否則span將長期呆在returned鏈裏麵。
ThreadCache => CentralCache
ThreadCache是tcmalloc的核心，它裏麵的FreeList長度控製還是比較複雜的。
前麵提到過，FreeList長度超過限額和ThreadCache容量超過限額，這兩種情況下會觸發object回收。考慮到應用程序的多樣性，這兩個限額不能是定死的，必需得自適應：有些線程對內存的需求可能遠多於其他一些線程、有些線程可能總是在分配內存而另一些線程則總是釋放內存（生產者消費者）、等等。
先來看ThreadCache的容量限額，其思想是：為每一個ThreadCache初始化一個比較小的限額，然後每當ThreadCache由於cache超限而觸發object到CentralCache的回收時，就增大該ThreadCache的限額。有限額增大，就應該有限額回收。tcmalloc預設了一個所有ThreadCache的總容量，當ThreadCache需要增大容量時，如果總容量尚有餘額，則使用這些餘額。否則需要增大的容量就從其他線程的ThreadCache裏麵去收刮（具體從收刮哪個線程的容量，簡單采用了輪詢的方式）。這樣一來，隻需要在ThreadCache內存回收時做一些簡單的處理，就能實現ThreadCache的容量的自適應：內存需求大的線程總是收刮別人的容量，而內存需求低的線程則總是被收刮。當然，收刮與被收刮並不是無節製的，會有一個最大值最小值的限製，比如128字節~4M。
到達ThreadCache的容量限額時，會對它下麵的每一個FreeList進行回收，回收的數目是該Freelist.lowator_的一半。什麼是lowator_呢？就是該Freelist在ThreadCache超限的兩次回收周期之間內，FreeList的最小長度。也就是說，在上一個周期中，FreeList裏麵有lowator_個object是從未被用到的。通過這一曆史信息，可以預估在下一次回收到來時，可能也有lowator_個object可能不會被用到。不過保守一點，隻回收lowator_的一半。
回收過程其實隻是對每一個FreeList的保守回收，回收完成之後ThreadCache的容量可能還會繼續高於限額，不過隨著這次回收，ThreadCache的容量限額也會被抬高。
下一個問題是單個FreeList的限額，tcmalloc采用慢啟動策略，每個FreeList初始時長度限額為1。在限額為1~batch_size之間時，為慢啟動狀態。此時，不管是alloc遇到空FreeList、還是free遇到長度超限，都給限額加1。這樣做可以給不常用或者使用很規律的object確定一個合適的限額，而如果object的使用抖動較大的話，應該給它一個更大的buffer。
如果限額增加達到batch_size，則慢啟動狀態結束。此時，如果alloc遇到空FreeList，限額會按batch_size的整數倍進行擴展。而如果free超限，則限額將按照batch_size的整數倍進行縮減。
alloc遇到空FreeList（說明FreeList的限額達不到線程的分配需求），應該不斷增加限額，這個好理解。那麼free超限的情況下，為什麼慢啟動狀態下要增加限額，非慢啟動狀態則要減少限額呢？如果free總是超限，說明線程對object的free要多於alloc，線程之間對該object的分配回收很可能是不對稱的。那麼作為專職回收的那個線程，沒必要給他留大的限額，因為它的分配需求很少。而慢啟動狀態下超限還給限額做加1遞增，一方麵可以應對抖動，另一方麵遞增限額的目的是使之能夠達到batch_size（如果free確實遠多於alloc話），從而在回收object時可以按batch_size批量回收。
FreeList限額超限的處理比較簡單，直接回收batch_size個object即可（不足batch_size個，則有多少回收多少）。可見，處於慢啟動狀態下的FreeList限額超限，將導致FreeList被清空。
最後更新：2017-11-22 00:04:06