原文請移步我的博客：TCMalloc解密

寫在前面

本文首先簡單介紹TCMalloc及其使用方法，然后解釋TCMalloc替代系統(tǒng)的內(nèi)存分配函數(shù)的原理，然后從宏觀上討論其內(nèi)存分配的策略仁连，在此之后再深入討論實現(xiàn)細節(jié)。

有幾點需要說明：

• 本文只討論gperftools中TCMalloc部分的代碼达舒，對應版本gperftools-2.7灿渴。
• 本文是根據(jù)TCMalloc源碼以及簡短的官方介紹作出的個人理解，難免有紕漏之處艺沼，且難以覆蓋TCMalloc的方方面面册舞，不足之處還請各位看官留言指正。
• 除非特別說明障般，以下討論均以32位系統(tǒng)调鲸、TCMalloc默認page大小（8KB）為基礎挽荡，不同架構或不同page大小藐石，有些相關數(shù)值可能不一樣，但基本原理是相似的定拟。
• 為了控制篇幅于微，我會盡量少貼大段代碼，只給出關鍵代碼的位置或函數(shù)名青自，各位看官可自行參閱TCMalloc相關代碼株依。

TCMalloc是什么

TCMalloc全稱Thread-Caching Malloc，即線程緩存的malloc延窜，實現(xiàn)了高效的多線程內(nèi)存管理恋腕，用于替代系統(tǒng)的內(nèi)存分配相關的函數(shù)（malloc、free需曾，new吗坚，new[]等）祈远。

TCMalloc是gperftools的一部分呆万，除TCMalloc外，gperftools還包括heap-checker车份、heap-profiler和cpu-profiler谋减。本文只討論gperftools的TCMalloc部分。

git倉庫：https://github.com/gperftools/gperftools.git

官方介紹：https://gperftools.github.io/gperftools/TCMalloc.html（里面有些內(nèi)容已經(jīng)過時了）

如何使用TCMalloc

安裝

以下是比較常規(guī)的安裝步驟出爹，詳細可參考gperftools中的INSTALL铸董。

1. 從git倉庫clone版本的gperftools的安裝依賴autoconf汰具、automake恰聘、libtool排作，以Debian為例：

   # apt install autoconf automake libtool
   

2. 生成configure等一系列文件

   $ ./autogen.sh
   

3. 生成Makefile

   $ ./configure
   

4. 編譯

   $ make
   

5. 安裝

   # make install
   

   默認安裝在/usr/local/下的相關路徑（bin楞件、lib拌夏、share），可在configure時以--prefix=PATH指定其他路徑履因。

64位Linux系統(tǒng)需要注意

在64位Linux環(huán)境下障簿，gperftools使用glibc內(nèi)置的stack-unwinder可能會引發(fā)死鎖，因此官方推薦在配置和安裝gperftools之前栅迄，先安裝libunwind-0.99-beta站故，最好就用這個版本，版本太新或太舊都可能會有問題毅舆。

即便使用libunwind西篓，在64位系統(tǒng)上還是會有問題，但只影響heap-checker憋活、heap-profiler和cpu-profiler岂津，TCMalloc不受影響，因此不再贅述悦即，感興趣的讀者可參閱gperftools的INSTALL吮成。

如果不希望安裝libunwind，也可以用gperftools內(nèi)置的stack unwinder辜梳，但需要應用程序粱甫、TCMalloc庫、系統(tǒng)庫（比如libc）在編譯時開啟幀指針（frame pointer）選項作瞄。

在x86-64下茶宵，編譯時開啟幀指針選項并不是默認行為。因此需要指定-fno-omit-frame-pointer編譯所有應用程序宗挥，然后在configure時通過--enable-frame-pointers選項使用內(nèi)置的gperftools stack unwinder乌庶。

使用

以動態(tài)庫的方式

安裝之后，通過-ltcmalloc或-ltcmalloc_minimal將TCMalloc鏈接到應用程序即可契耿。

#include <stdlib.h>

int main( int argc, char *argv[] )
{   
    malloc(1);
}

$ g++ -O0 -g -ltcmalloc test.cc && gdb a.out

(gdb) b test.cc:5
Breakpoint 1 at 0x7af: file test.cc, line 5.
(gdb) r
Starting program: /home/wanglong/test/https://wallenwang.com/tcmalloc/a.out 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Breakpoint 1, main (argc=1, argv=0x7fffffffddd8) at test.cc:5
5           malloc(1);
(gdb) s
tc_malloc (size=1) at src/tcmalloc.cc:1892
1892      return malloc_fast_path<tcmalloc::malloc_oom>(size);
(gdb) 

通過gdb斷點可以看到對malloc()的調(diào)用已經(jīng)替換為TCMalloc的實現(xiàn)瞒大。

以靜態(tài)庫的方式

gperftools的README中說靜態(tài)庫應該使用libtcmalloc_and_profiler.a庫而不是libprofiler.a和libtcmalloc.a，但簡單測試后者也是OK的宵喂，而且在實際項目中也是用的后者糠赦，不知道是不是文檔太過老舊了。

$ g++ -O0 -g -pthread test.cc /usr/local/lib/libtcmalloc_and_profiler.a

如果使用了libunwind锅棕，需要指定-Wl,--eh-frame-hdr選項拙泽，以確保libunwind可以找到編譯器生成的信息來進行棧回溯裸燎。

eh-frame（exception handling frame）參考資料：

• http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0803d/pge1446568291678.html
• http://zhaohongjian000.is-programmer.com/posts/29660.html
• https://www.cnblogs.com/catch/p/3619379.html

TCMalloc是如何生效的

為什么指定-ltcmalloc或者與libtcmalloc_and_profiler.a連接之后顾瞻，對malloc、free德绿、new荷荤、delete等的調(diào)用就由默認的libc中的函數(shù)調(diào)用變?yōu)門CMalloc中相應的函數(shù)調(diào)用了呢？答案在libc_override.h中移稳，下面只討論常見的兩種情況：使用了glibc蕴纳，或者使用了GCC編譯器。其余情況可自行查看相應的libc_override頭文件个粱。

使用glibc（但沒有使用GCC編譯器）

在glibc中古毛，內(nèi)存分配相關的函數(shù)都是弱符號（weak symbol），因此TCMalloc只需要定義自己的函數(shù)將其覆蓋即可都许，以malloc和free為例：

libc_override_redefine.h

extern "C" { 
  void* malloc(size_t s)                         { return tc_malloc(s);       }
  void  free(void* p)                            { tc_free(p);                }
}  // extern "C"

可以看到稻薇，TCMalloc將malloc()和free()分別定義為對tc_malloc()和tc_free()的調(diào)用，并在tc_malloc()和tc_free()中實現(xiàn)具體的內(nèi)存分配和回收邏輯胶征。

new和delete也類似：

void* operator new(size_t size)                  { return tc_new(size);       }
void operator delete(void* p) CPP_NOTHROW        { tc_delete(p);              }

使用GCC編譯器

如果使用了GCC編譯器塞椎，則使用其支持的函數(shù)屬性：alias。

libc_override_gcc_and_weak.h：

#define ALIAS(tc_fn)   __attribute__ ((alias (#tc_fn), used))

extern "C" { 
  void* malloc(size_t size) __THROW               ALIAS(tc_malloc);
  void free(void* ptr) __THROW                    ALIAS(tc_free);
}   // extern "C"

將宏展開睛低，__attribute__ ((alias ("tc_malloc"), used))表明tc_malloc是malloc的別名案狠。

具體可參閱GCC相關文檔：

alias ("target")
? The alias attribute causes the declaration to be emitted as an alias for another symbol, which must be specified. For instance,
? void __f () { /* Do something. */; }
? void f () __attribute__ ((weak, alias ("__f")));
? defines f to be a weak alias for __f. In C++, the mangled name for the target must be used. It is an error if __f is not defined in the same translation unit.
? Not all target machines support this attribute.

used
? This attribute, attached to a function, means that code must be emitted for the function even if it appears that the function is not referenced. This is useful, for example, when the function is referenced only in inline assembly.
? When applied to a member function of a C++ class template, the attribute also means that the function will be instantiated if the class itself is instantiated.

TCMalloc的初始化

何時初始化

TCMalloc定義了一個類TCMallocGuard，并在文件tcmalloc.cc中定義了該類型的靜態(tài)變量module_enter_exit_hook钱雷，在其構造函數(shù)中執(zhí)行TCMalloc的初始化邏輯莺戒，以確保TCMalloc在main()函數(shù)之前完成初始化，防止在初始化之前就有多個線程急波。

tcmalloc.cc：

static TCMallocGuard module_enter_exit_hook;

如果需要確保TCMalloc在某些全局構造函數(shù)運行之前就初始化完成从铲，則需要在文件頂部創(chuàng)建一個靜態(tài)TCMallocGuard實例。

如何初始化

TCMallocGuard的構造函數(shù)實現(xiàn)：

static int tcmallocguard_refcount = 0;  // no lock needed: runs before main()
TCMallocGuard::TCMallocGuard() {
  if (tcmallocguard_refcount++ == 0) {
    ReplaceSystemAlloc();    // defined in libc_override_*.h
    tc_free(tc_malloc(1));
    ThreadCache::InitTSD();
    tc_free(tc_malloc(1));
    // Either we, or debugallocation.cc, or valgrind will control memory
    // management.  We register our extension if we're the winner.
#ifdef TCMALLOC_USING_DEBUGALLOCATION
    // Let debugallocation register its extension.
#else
    if (RunningOnValgrind()) {
      // Let Valgrind uses its own malloc (so don't register our extension).
    } else {
      MallocExtension::Register(new TCMallocImplementation);
    }
#endif
  }
} 

可以看到澄暮，TCMalloc初始化的方式是調(diào)用tc_malloc()申請一字節(jié)內(nèi)存并隨后調(diào)用tc_free()將其釋放名段。至于為什么在InitTSD前后各申請釋放一次，不太清楚泣懊，猜測是為了測試在TSD（Thread Specific Data伸辟，詳見后文）初始化之前也能正常工作。

初始化內(nèi)容

那么TCMalloc在初始化時都執(zhí)行了哪些操作呢馍刮？這里先簡單列一下信夫，后續(xù)討論TCMalloc的實現(xiàn)細節(jié)時再逐一詳細討論：

• 初始化SizeMap（Size Class）
• 初始化各種Allocator
• 初始化CentralCache
• 創(chuàng)建PageHeap

總之一句話，創(chuàng)建TCMalloc自身的一些元數(shù)據(jù)，比如劃分小對象的大小等等静稻。

TCMalloc的內(nèi)存分配算法概覽

TCMalloc的官方介紹中將內(nèi)存分配稱為Object Allocation警没，本文也沿用這種叫法，并將object翻譯為對象振湾，可以將其理解為具有一定大小的內(nèi)存杀迹。

按照所分配內(nèi)存的大小，TCMalloc將內(nèi)存分配分為三類：

• 小對象分配押搪，(0, 256KB]
• 中對象分配树酪，(256KB, 1MB]
• 大對象分配，(1MB, +∞)

簡要介紹幾個概念大州，Page续语，Span，PageHeap：

與操作系統(tǒng)管理內(nèi)存的方式類似厦画，TCMalloc將整個虛擬內(nèi)存空間劃分為n個同等大小的Page疮茄，每個page默認8KB。又將連續(xù)的n個page稱為一個Span苛白。

TCMalloc定義了PageHeap類來處理向OS申請內(nèi)存相關的操作娃豹，并提供了一層緩存」喝梗可以認為懂版，PageHeap就是整個可供應用程序動態(tài)分配的內(nèi)存的抽象。

PageHeap以span為單位向系統(tǒng)申請內(nèi)存躏率，申請到的span可能只有一個page躯畴，也可能包含n個page∞敝ィ可能會被劃分為一系列的小對象蓬抄，供小對象分配使用，也可能當做一整塊當做中對象或大對象分配夯到。

小對象分配

Size Class

對于256KB以內(nèi)的小對象分配嚷缭，TCMalloc按大小劃分了85個類別（官方介紹中說是88個左右，但我個人實際測試是85個耍贾，不包括0字節(jié)大性乃），稱為Size Class荐开，每個size class都對應一個大小付翁，比如8字節(jié)，16字節(jié)晃听，32字節(jié)百侧。應用程序申請內(nèi)存時砰识，TCMalloc會首先將所申請的內(nèi)存大小向上取整到size class的大小，比如1_{8字節(jié)之間的內(nèi)存申請都會分配8字節(jié)佣渴，9}16字節(jié)之間都會分配16字節(jié)辫狼，以此類推。因此這里會產(chǎn)生內(nèi)部碎片观话。TCMalloc將這里的內(nèi)部碎片控制在12.5%以內(nèi)予借，具體的做法在討論size class的實現(xiàn)細節(jié)時再詳細分析越平。

ThreadCache

對于每個線程频蛔，TCMalloc都為其保存了一份單獨的緩存，稱之為ThreadCache秦叛，這也是TCMalloc名字的由來（Thread-Caching Malloc）晦溪。每個ThreadCache中對于每個size class都有一個單獨的FreeList，緩存了n個還未被應用程序使用的空閑對象挣跋。

小對象的分配直接從ThreadCache的FreeList中返回一個空閑對象三圆，相應的，小對象的回收也是將其重新放回ThreadCache中對應的FreeList中避咆。

由于每線程一個ThreadCache舟肉，因此從ThreadCache中取用或回收內(nèi)存是不需要加鎖的，速度很快查库。

為了方便統(tǒng)計數(shù)據(jù)路媚，各線程的ThreadCache連接成一個雙向鏈表。ThreadCache的結構示大致如下：

tcmalloc-ThreadCache

CentralCache

那么ThreadCache中的空閑對象從何而來呢樊销？答案是CentralCache——一個所有線程公用的緩存整慎。

與ThreadCache類似，CentralCache中對于每個size class也都有一個單獨的鏈表來緩存空閑對象围苫，稱之為CentralFreeList裤园，供各線程的ThreadCache從中取用空閑對象。

由于是所有線程公用的剂府，因此從CentralCache中取用或回收對象拧揽，是需要加鎖的。為了平攤鎖操作的開銷腺占，ThreadCache一般從CentralCache中一次性取用或回收多個空閑對象淤袜。

CentralCache在TCMalloc中并不是一個類，只是一個邏輯上的概念湾笛，其本質(zhì)是CentralFreeList類型的數(shù)組饮怯。后文會詳細討論CentralCache的內(nèi)部結構，現(xiàn)在暫且認為CentralCache的簡化結構如下：

tcmalloc-CentralCache

PageHeap

CentralCache中的空閑對象又是從何而來呢嚎研？答案是之前提到的PageHeap——TCMalloc對可動態(tài)分配的內(nèi)存的抽象蓖墅。

當CentralCache中的空閑對象不夠用時库倘，CentralCache會向PageHeap申請一塊內(nèi)存（可能來自PageHeap的緩存，也可能向系統(tǒng)申請新的內(nèi)存）论矾，并將其拆分成一系列空閑對象教翩，添加到對應size class的CentralFreeList中。

PageHeap內(nèi)部根據(jù)內(nèi)存塊（span）的大小采取了兩種不同的緩存策略贪壳。128個page以內(nèi)的span饱亿，每個大小都用一個鏈表來緩存，超過128個page的span闰靴，存儲于一個有序set（std::set）彪笼。討論TCMalloc的實現(xiàn)細節(jié)時再具體分析，現(xiàn)在可以認為PageHeap的簡化結構如下：

tcmalloc-PageHeap

內(nèi)存回收

上面說的都是內(nèi)存分配蚂且，內(nèi)存回收的情況是怎樣的配猫？

應用程序調(diào)用free()或delete一個小對象時，僅僅是將其插入到ThreadCache中其size class對應的FreeList中而已杏死，不需要加鎖泵肄，因此速度也是非常快的淑翼。

只有當滿足一定的條件時腐巢，ThreadCache中的空閑對象才會重新放回CentralCache中苛坚，以供其他線程取用葵陵。同樣的，當滿足一定條件時迹卢，CentralCache中的空閑對象也會還給PageHeap惠豺，PageHeap再還給系統(tǒng)银还。

內(nèi)存在這些組件之間的移動會在后文詳細討論，現(xiàn)在先忽略這些細節(jié)洁墙。

小結

總結一下蛹疯，小對象分配流程大致如下：

• 將要分配的內(nèi)存大小映射到對應的size class。
• 查看ThreadCache中該size class對應的FreeList热监。
• 如果FreeList非空捺弦，則移除FreeList的第一個空閑對象并將其返回，分配結束孝扛。
• 如果FreeList是空的：
  • 從CentralCache中size class對應的CentralFreeList獲取一堆空閑對象列吼。
    • 如果CentralFreeList也是空的，則：
      • 向PageHeap申請一個span苦始。
      • 拆分成size class對應大小的空閑對象寞钥，放入CentralFreeList中。
  • 將這堆對象放置到ThreadCache中size class對應的FreeList中（第一個對象除外）陌选。
  • 返回從CentralCache獲取的第一個對象理郑，分配結束蹄溉。

中對象分配

超過256KB但不超過1MB（128個page）的內(nèi)存分配被認為是中對象分配，采取了與小對象不同的分配策略您炉。

首先柒爵，TCMalloc會將應用程序所要申請的內(nèi)存大小向上取整到整數(shù)個page（因此，這里會產(chǎn)生1B~8KB的內(nèi)部碎片）赚爵。之后的操作表面上非常簡單棉胀，向PageHeap申請一個指定page數(shù)量的span并返回其起始地址即可：

Span* span = Static::pageheap()->New(num_pages);
result = (PREDICT_FALSE(span == NULL) ? NULL : SpanToMallocResult(span));
return result;

問題在于，PageHeap是如何管理這些span的冀膝？即PageHeap::New()是如何實現(xiàn)的唁奢。

前文說到，PageHeap提供了一層緩存畸写，因此PageHeap::New()并非每次都向系統(tǒng)申請內(nèi)存驮瞧，也可能直接從緩存中分配氓扛。

對128個page以內(nèi)的span和超過128個page的span枯芬，PageHeap采取的緩存策略不一樣。為了描述方便采郎，以下將128個page以內(nèi)的span稱為小span千所，大于128個page的span稱為大span。

先來看小span是如何管理的蒜埋，大span的管理放在大對象分配一節(jié)介紹淫痰。

PageHeap中有128個小span的鏈表，分別對應1~128個page的span：

tcmalloc-SpanList

假設要分配一塊內(nèi)存整份，其大小經(jīng)過向上取整之后對應k個page待错，因此需要從PageHeap取一個大小為k

個page的span，過程如下：

• 從k個page的span鏈表開始烈评，到128個page的span鏈表火俄，按順序找到第一個非空鏈表。
• 取出這個非空鏈表中的一個span讲冠，假設有n個page瓜客，將這個span拆分成兩個span：
  • 一個span大小為k個page，作為分配結果返回竿开。
  • 另一個span大小為n - k個page谱仪，重新插入到n - k個page的span鏈表中。
• 如果找不到非空鏈表否彩，則將這次分配看做是大對象分配疯攒，分配過程詳見下文。

大對象分配

超過1MB（128個page）的內(nèi)存分配被認為是大對象分配列荔，與中對象分配類似敬尺，也是先將所要分配的內(nèi)存大小向上取整到整數(shù)個page称杨，假設是k個page，然后向PageHeap申請一個k個page大小的span筷转。

對于中對象的分配姑原，如果上述的span鏈表無法滿足，也會被當做是大對象來處理呜舒。也就是說锭汛，TCMalloc在源碼層面其實并沒有區(qū)分中對象和大對象，只是對于不同大小的span的緩存方式不一樣罷了袭蝗。

大對象分配用到的span都是超過128個page的span唤殴，其緩存方式不是鏈表，而是一個按span大小排序的有序set（std::set）到腥，以便按大小進行搜索朵逝。

假設要分配一塊超過1MB的內(nèi)存，其大小經(jīng)過向上取整之后對應k個page（k>128）乡范，或者是要分配一塊1MB以內(nèi)的內(nèi)存配名，但無法由中對象分配邏輯來滿足，此時k <= 128晋辆。不管哪種情況渠脉，都是要從PageHeap的span set中取一個大小為k個page的span，其過程如下：

• 搜索set瓶佳，找到不小于k個page的最小的span（best-fit）芋膘，假設該span有n個page。
• 將這個span拆分為兩個span：
  • 一個span大小為k個page霸饲，作為結果返回为朋。
  • 另一個span大小為n - k個page，如果n - k > 128厚脉，則將其插入到大span的set中习寸，否則，將其插入到對應的小span鏈表中器仗。
• 如果找不到合適的span融涣，則使用sbrk或mmap向系統(tǒng)申請新的內(nèi)存以生成新的span，并重新執(zhí)行中對象或大對象的分配算法精钮。

小結

以上討論忽略了很多實現(xiàn)上的細節(jié)威鹿，比如PageHeap對span的管理還區(qū)分了normal狀態(tài)的span和returned狀態(tài)的span，接下來會詳細分析這些細節(jié)轨香。

在此之前忽你，畫張圖概括下TCMalloc的管理內(nèi)存的策略：

tcmalloc-Overview

可以看到，不超過256KB的小對象分配臂容，在應用程序和內(nèi)存之間其實有三層緩存：PageHeap科雳、CentralCache根蟹、ThreadCache。而中對象和大對象分配糟秘，則只有PageHeap一層緩存简逮。

TCMalloc的實現(xiàn)細節(jié)

算法概覽一節(jié)涉及到了很多概念，比如Page尿赚，Span散庶，Size Class，PageHeap凌净，ThreadCache等悲龟，但只是粗略的一提，本節(jié)將詳細討論這些概念所涉及的實現(xiàn)細節(jié)冰寻。

Page

Page是TCMalloc管理內(nèi)存的基本單位（這里的page要區(qū)分于操作系統(tǒng)管理虛擬內(nèi)存的page）须教，page的默認大小為8KB，可在configure時通過選項調(diào)整為32KB或64KB斩芭。

./configure <other flags> --with-tcmalloc-pagesize=32 (or 64)

page越大轻腺，TCMalloc的速度相對越快，但其占用的內(nèi)存也會越高秒旋。簡單說约计，就是空間換時間的道理。默認的page大小通過減少內(nèi)存碎片來最小化內(nèi)存使用迁筛，但跟蹤這些page會花費更多的時間。使用更大的page則會帶來更多的內(nèi)存碎片耕挨，但速度上會有所提升细卧。官方文檔給出的數(shù)據(jù)是在某些google應用上有3%~5%的速度提升。

PageID

TCMalloc并非只將堆內(nèi)存看做是一個個的page筒占，而是將整個虛擬內(nèi)存空間都看做是page的集合贪庙。從內(nèi)存地址0x0開始，每個page對應一個遞增的PageID翰苫，如下圖（以32位系統(tǒng)為例）：

tcmalloc-Page

對于任意內(nèi)存地址ptr止邮，都可通過簡單的移位操作來計算其所在page的PageID：

static const size_t kPageShift  = 13; // page大小：1 << 13 = 8KB
const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift;

即奏窑，ptr所屬page的PageID為ptr / page_size导披。

Span

一個或多個連續(xù)的Page組成一個Span（a contiguous run of pages）。TCMalloc以Span為單位向系統(tǒng)申請內(nèi)存埃唯。

tcmalloc-Span

如圖撩匕，第一個span包含2個page，第二個和第四個span包含3個page墨叛，第三個span包含5個page止毕。

一個span記錄了起始page的PageID（start）模蜡，以及所包含page的數(shù)量（length）。

一個span要么被拆分成多個相同size class的小對象用于小對象分配扁凛，要么作為一個整體用于中對象或大對象分配忍疾。當作用作小對象分配時，span的sizeclass成員變量記錄了其對應的size class谨朝。

span中還包含兩個Span類型的指針（prev, next）膝昆，用于將多個span以鏈表的形式存儲。

span的三種狀態(tài)

一個span處于以下三種狀態(tài)中的一種：

• IN_USE
• ON_NORMAL_FREELIST
• ON_RETURNED_FREELIST

IN_USE比較好理解叠必，正在使用中的意思荚孵，要么被拆分成小對象分配給CentralCache或者ThreadCache了，要么已經(jīng)分配給應用程序了纬朝。因為span是由PageHeap來管理的收叶，因此即使只是分配給了CentralCache，還沒有被應用程序所申請共苛，在PageHeap看來判没，也是IN_USE了。

ON_NORMAL_FREELIST和ON_RETURNED_FREELIST都可以認為是空閑狀態(tài)隅茎，區(qū)別在于澄峰，ON_RETURNED_FREELIST是指span對應的內(nèi)存已經(jīng)被PageHeap釋放給系統(tǒng)了（在Linux中，對于MAP_PRIVATE|MAP_ANONYMOUS的內(nèi)存使用madvise來實現(xiàn)）辟犀。需要注意的是俏竞，即使歸還給系統(tǒng)，其虛擬內(nèi)存地址依然是可訪問的堂竟，只是對這些內(nèi)存的修改丟失了而已魂毁，在下一次訪問時會導致page fault以用0來重新初始化。

空閑對象鏈表

被拆分成多個小對象的span還包含了一個記錄空閑對象的鏈表objects出嘹，由CentralFreeList來維護席楚。

對于新創(chuàng)建的span，將其對應的內(nèi)存按size class的大小均分成若干小對象税稼，在每一個小對象的起始位置處存儲下一個小對象的地址烦秩，首首相連：

tcmalloc-FreshSpan

但當span中的小對象經(jīng)過一系列申請和回收之后，其順序就不確定了：

tcmalloc-UsedSpan

可以看到郎仆，有些小對象已經(jīng)不再空閑對象鏈表objects中了只祠，鏈表中的元素順序也已經(jīng)被打亂。

空閑對象鏈表中的元素亂序沒什么影響丸升，因為只有當一個span的所有小對象都被釋放之后铆农，CentralFreeList才會將其還給PageHeap。

PageMap

PageMap之前沒有提到過墩剖，它主要用于解決這么一個問題：給定一個page，如何確定這個page屬于哪個span岭皂？

即郊霎，PageMap緩存了PageID到Span的對應關系。

32位系統(tǒng)爷绘、x86-64书劝、arm64使用兩級PageMap，以32位系統(tǒng)為例：

tcmalloc-PageMap

在root_數(shù)組中包含512個指向Leaf的指針土至，每個Leaf又是1024個void*的數(shù)組购对，數(shù)組索引為PageID，數(shù)組元素為page所屬Span的指針陶因。一共個數(shù)組元素骡苞，對應32位系統(tǒng)的個page。

使用兩級map可以減少TCMalloc元數(shù)據(jù)的內(nèi)存占用楷扬，因為初始只會給第一層（即root_數(shù)組）分配內(nèi)存（2KB）解幽，第二層只有在實際用到時才會實際分配內(nèi)存。而如果初始就給個page都分配內(nèi)存的話烘苹，則會占用的內(nèi)存躲株。

Size Class

TCMalloc將每個小對象的大小（1B~256KB）分為85個類別（官方介紹中說是88個左右镣衡，但我個人實際測試是85個霜定，不包括0字節(jié)大小）捆探，稱之為Size Class然爆，每個size class一個編號，從0開始遞增（實際編號為0的size class是對應0字節(jié)黍图，是沒有實際意義的）。

舉個例子奴烙，896字節(jié)對應編號為30的size class助被，下一個size class 31大小為1024字節(jié)，那么897字節(jié)到1024字節(jié)之間所有的分配都會向上舍入到1024字節(jié)切诀。

SizeMap::Init()實現(xiàn)了對size class的劃分揩环，規(guī)則如下：

劃分跨度

• 16字節(jié)以內(nèi)，每8字節(jié)劃分一個size class幅虑。
  • 滿足這種情況的size class只有兩個：8字節(jié)丰滑、16字節(jié)。
• 16~128字節(jié)倒庵，每16字節(jié)劃分一個size class褒墨。
  • 滿足這種情況的size class有7個：32, 48, 64, 80, 96, 112, 128字節(jié)炫刷。
• 128B~256KB，按照每次步進(size / 8)字節(jié)的長度劃分郁妈，并且步長需要向下對齊到2的整數(shù)次冪浑玛，比如：
  • 144字節(jié)：128 + 128 / 8 = 128 + 16 = 144
  • 160字節(jié)：144 + 144 / 8 = 144 + 18 = 144 + 16 = 160
  • 176字節(jié)：160 + 160 / 8 = 160 + 20 = 160 + 16 = 176
  • 以此類推

一次移動多個空閑對象

ThreadCache會從CentralCache中獲取空閑對象，也會將超出限制的空閑對象放回CentralCache噩咪。ThreadCache和CentralCache之間的對象移動是批量進行的顾彰，即一次移動多個空閑對象。CentralCache由于是所有線程公用胃碾，因此對其進行操作時需要加鎖涨享，一次移動多個對象可以均攤鎖操作的開銷，提升效率仆百。

那么一次批量移動多少呢厕隧？每次移動64KB大小的內(nèi)存，即因size class而異儒旬，但至少2個栏账，至多32個（可通過環(huán)境變量TCMALLOC_TRANSFER_NUM_OBJ調(diào)整）。

移動數(shù)量的計算也是在size class初始化的過程中計算得出的栈源。

一次申請多個page

對于每個size class挡爵，TCMalloc向系統(tǒng)申請內(nèi)存時一次性申請n個page（一個span），然后均分成多個小對象進行緩存甚垦，以此來均攤系統(tǒng)調(diào)用的開銷茶鹃。

不同的size class對應的page數(shù)量是不同的，如何決定n的大小呢艰亮？從1個page開始遞增闭翩，一直到均分成若干小對象后所剩的空間小于span總大小的1/8為止，因此迄埃，浪費的內(nèi)存被控制在12.5%以內(nèi)疗韵。這是TCMalloc減少內(nèi)部碎片的一種措施。

另外侄非，所分配的page數(shù)量還需滿足一次移動多個空閑對象的數(shù)量要求（源碼中的注釋是這樣說的蕉汪，不過實際代碼是滿足1/4即可，原因不明）逞怨。

合并操作

在上述規(guī)則之上者疤，還有一個合并操作：TCMalloc會將相同page數(shù)量，相同對象數(shù)量的相鄰的size class合并為一個size class叠赦。比如：

size_merge

第30個size class的對象大小是832字節(jié)驹马，page數(shù)量為1個，因此包含8192 / 832 = 9個小對象。

第31個size class對應的page數(shù)量（1個）和對象數(shù)量（9個）跟第30個size class完全一樣糯累，因此第30個size class和第31個size class合并算利，所以第30個size class對應的對象大小為896字節(jié)。

下一個size class對應的對象大小為1024字節(jié)寇蚊，page數(shù)量為1個笔时，因此對象數(shù)量是8個，跟第30個size class的對象數(shù)量不一樣仗岸，無法合并允耿。

最終，第30個size class對應的對象大小為896字節(jié)扒怖。

記錄映射關系

由以上劃分規(guī)則可以看到较锡，一個size class對應：

• 一個對象大小
• 一個申請page的數(shù)量
• 一個批量移動對象的數(shù)量

TCMalloc將size class與這些信息的映射關系分別記錄在三個以size class的編號為索引的數(shù)組中（class_to_size_，num_objects_to_move_盗痒， class_to_pages_）蚂蕴。

還有一項非常重要的映射關系：小對象大小到size class編號的映射。TCMalloc將其記錄在一個一維數(shù)組class_array_中俯邓。

256KB以內(nèi)都是小對象骡楼，而size class的編號用一個字節(jié)就可以表示，因此存儲小對象大小對應的size class編號需要256K個unsigned char稽鞭，即256KB的內(nèi)存鸟整。但由于size class之間是有間隔的（1024字節(jié)以內(nèi)間隔至少8字節(jié)，1024以上間隔至少128字節(jié)）朦蕴，因此可以通過簡單的計算對class_array_的索引進行壓縮篮条，以減少內(nèi)存占用。

給定大小s吩抓，其對應的class_array_索引計算方式如下：

// s <= 1024
static inline size_t SmallSizeClass(size_t s) {
  return (static_cast<uint32_t>(s) + 7) >> 3;
}

// s > 1024
static inline size_t LargeSizeClass(size_t s) {
  return (static_cast<uint32_t>(s) + 127 + (120 << 7)) >> 7;
}

當s = 256KB時涉茧，計算結果即為class_array_的最大索引2169，因此數(shù)組的大小為2170字節(jié)疹娶。

計算任意內(nèi)存地址對應的對象大小

當應用程序調(diào)用free()或delete釋放內(nèi)存時伴栓，需要有一種方式獲取所要釋放的內(nèi)存地址對應的內(nèi)存大小。結合前文所述的各種映射關系雨饺，在TCMalloc中按照以下順序計算任意內(nèi)存地址對應的對象大姓跫ⅰ：

• 計算給定地址計所在的PageID（ptr >> 13）
• 從PageMap中查詢該page所在的span
• span中記錄了size class編號
• 根據(jù)size class編號從class_to_size_數(shù)組中查詢對應的對象大小

這樣做的好處是：不需要在內(nèi)存塊的頭部記錄內(nèi)存大小，減少內(nèi)存的浪費沛膳。

小結

size class的實現(xiàn)中有很多省空間省時間的做法：

• 省空間
  • 控制劃分跨度的最大值（8KB），減少內(nèi)部碎片
  • 控制一次申請page的數(shù)量汛聚，減少內(nèi)部碎片
  • 通過計算和一系列元數(shù)據(jù)記錄內(nèi)存地址到內(nèi)存大小的映射關系锹安，避免在實際分配的內(nèi)存塊中記錄內(nèi)存大小，減少內(nèi)存浪費
  • 兩級PageMap或三級PageMap
  • 壓縮class_array_
• 省時間
  • 一次申請多個page
  • 一次移動多個空閑對象

PageHeap

前面介紹的都是TCMalloc如何對內(nèi)存進行劃分瘾婿，接下來看TCMalloc如何管理如此劃分后的內(nèi)存套硼，這是PageHeap的主要職責悯森。

TCMalloc源碼中對PageHeap的注釋：

// -------------------------------------------------------------------------
// Page-level allocator
//  * Eager coalescing
//
// Heap for page-level allocation.  We allow allocating and freeing a
// contiguous runs of pages (called a "span").
// -------------------------------------------------------------------------

空閑Span管理器

如前所述嫉称，128page以內(nèi)的span稱為小span谍肤，128page以上的span稱為大span荞下。PageHeap對于這兩種span采取了不同的管理策略傍衡。小span用鏈表蠢壹，而且每個大小的span都用一個單獨的鏈表來管理超升。大span用std::set入宦。

前文沒有提到的是，從另一個維度來看室琢，PageHeap是分開管理ON_NORMAL_FREELIST和ON_RETURNED_FREELIST狀態(tài)的span的乾闰。因此，每個小span對應兩個鏈表盈滴，所有大span對應兩個set涯肩。

// We segregate spans of a given size into two circular linked
// lists: one for normal spans, and one for spans whose memory
// has been returned to the system.
struct SpanList {
  Span        normal;
  Span        returned;
};

// Array mapping from span length to a doubly linked list of free spans
//
// NOTE: index 'i' stores spans of length 'i + 1'.
SpanList free_[kMaxPages];    // 128

typedef std::set<SpanPtrWithLength, SpanBestFitLess, STLPageHeapAllocator<SpanPtrWithLength, void> > SpanSet;

// Sets of spans with length > kMaxPages.
//
// Rather than using a linked list, we use sets here for efficient
// best-fit search.
SpanSet large_normal_;
SpanSet large_returned_;

因此，實際的PageHeap是這樣的：

tcmalloc-PageHeap2

Heap段的使用限制

可以通過FLAGS_tcmalloc_heap_limit_mb對進程heap段的內(nèi)存使用量進行限制巢钓，默認值0表示不做限制病苗。如果開啟了限制并且對heap段內(nèi)存的使用量接近這個限制時，TCMalloc會更積極的將空閑內(nèi)存釋放給系統(tǒng)症汹，進而會引發(fā)更多的軟分頁錯誤（minor page fault）硫朦。

為了簡化討論，后文均假設沒有對heap段的內(nèi)存使用做任何限制烈菌。

創(chuàng)建Span

// Allocate a run of "n" pages.  Returns zero if out of memory.
// Caller should not pass "n == 0" -- instead, n should have
// been rounded up already.
Span* New(Length n);

創(chuàng)建span的過程其實就是分配中對象和大對象的過程阵幸，假設要創(chuàng)建k個page大小的span（以下簡稱大小為k的span），過程如下：

搜索空閑span

Span* SearchFreeAndLargeLists(Length n);

1. 搜索空閑span鏈表芽世，按照以下順序挚赊，找出第一個不小于k的span：
   • 從大小為k的span的鏈表開始依次搜索
   • 對于某個大小的span，先搜normal鏈表济瓢，再搜returned鏈表
2. 如果span鏈表中沒找到合適的span荠割，則搜索存儲大span的set：
   • 從大小為k的span開始搜索
   • 同樣先搜normal再搜returned
   • 優(yōu)先使用長度最小并且起始地址最小的span（best-fit）
3. 如果通過以上兩步找到了一個大小為m的span，則將其拆成兩個span：
   • 大小為m - k的span重新根據(jù)大小和狀態(tài)放回鏈表或set中
   • 大小為k的span作為結果返回旺矾，創(chuàng)建span結束
4. 如果沒搜到合適的span蔑鹦，則繼續(xù)后面的步驟：向系統(tǒng)申請內(nèi)存。

小插曲：釋放所有空閑內(nèi)存

ReleaseAtLeastNPages(static_cast<Length>(0x7fffffff));

當沒有可用的空閑span時箕宙，需要向系統(tǒng)申請新的內(nèi)存嚎朽，但在此之前，還有一次避免向系統(tǒng)申請新內(nèi)存的機會：釋放所有空閑內(nèi)存柬帕。向系統(tǒng)申請的內(nèi)存每達到128MB哟忍，且空閑內(nèi)存超過從系統(tǒng)申請的總內(nèi)存的1/4狡门，就需要將所有的空閑內(nèi)存釋放。

因為TCMalloc將normal和returned的內(nèi)存分開管理锅很，而這兩種內(nèi)存不會合并在一起其馏。因此，可能有一段連續(xù)的空閑內(nèi)存符合要求（k個page大斜病）叛复，但因為它既有normal的部分，又有returned的部分扔仓，因此前面的搜索規(guī)則搜不到它褐奥。而釋放所有內(nèi)存可以將normal的內(nèi)存也變?yōu)閞eturned的，然后就可以合并了（合并規(guī)則詳細后文合并span）当辐。

之所以控制在每128MB一次的頻率抖僵，是為了避免高頻小量申請內(nèi)存的程序遭受太多的minor page fault。

釋放完畢后缘揪，會按照前面的搜索規(guī)則再次嘗試搜索空閑span耍群，如果還搜不到，才繼續(xù)后續(xù)的步驟找筝。

向系統(tǒng)申請內(nèi)存

bool GrowHeap(Length n);

找不到合適的空閑span蹈垢，就只能向系統(tǒng)申請新的內(nèi)存了。

TCMalloc以sbrk()和mmap()兩種方式向系統(tǒng)申請內(nèi)存袖裕，所申請內(nèi)存的大小和位置均按page對齊曹抬，優(yōu)先使用sbrk()，申請失敗則會嘗試使用mmap()（64位系統(tǒng)Debug模式優(yōu)先使用mmap急鳄，原因詳見InitSystemAllocators()注釋）谤民。

TCMalloc向系統(tǒng)申請應用程序所使用的內(nèi)存時，每次至少嘗試申請1MB（kMinSystemAlloc）疾宏，申請TCMalloc自身元數(shù)據(jù)所使用的內(nèi)存時张足，每次至少申請8MB（kMetadataAllocChunkSize）。這樣做有兩點好處：

• 減少外部內(nèi)存碎片（減少所申請內(nèi)存與TCMalloc元數(shù)據(jù)所占內(nèi)存的交替）
• 均攤系統(tǒng)調(diào)用的開銷坎藐，提升性能

另外为牍，當從系統(tǒng)申請的總內(nèi)存超過128MB時就為PageMap一次性申請一大塊內(nèi)存，保證可以存儲所有page和span的對應關系岩馍。這一舉措可以減少TCMalloc的元數(shù)據(jù)將內(nèi)存分塊而導致的外部碎片碉咆。從源碼中可以發(fā)現(xiàn)，僅在32位系統(tǒng)下才會這樣做蛀恩，可能是因為64位系統(tǒng)內(nèi)存的理論上限太大疫铜，不太現(xiàn)實。

// bool PageHeap::GrowHeap(Length n);
if (old_system_bytes < kPageMapBigAllocationThreshold
    && stats_.system_bytes >= kPageMapBigAllocationThreshold) {
  pagemap_.PreallocateMoreMemory();
}

sbrk

先來看如何使用sbrk()從Heap段申請內(nèi)存双谆，下圖展示了SbrkSysAllocator::Alloc()的執(zhí)行流程块攒，為了說明外部碎片的產(chǎn)生励稳，并覆蓋到SbrkSysAllocator::Alloc()的大部分流程，假設page大小為8KB囱井，所申請的內(nèi)存大小為16KB：

tcmalloc-SbrkAlloc

1. 假設在申請內(nèi)存之前，pb（program break趣避，可以認為是堆內(nèi)存的上邊界）指向紅色箭頭所示位置庞呕，即沒有在page的邊界處。
2. 第一次sbrk申請16KB內(nèi)存程帕，因此pb移至綠色箭頭所示位置住练。
3. 由于需要對申請的內(nèi)存按page對齊，因此需要第二次sbrk愁拭，pb指向藍色箭頭所示位置讲逛，page的邊界處。
4. 最終岭埠，返回的內(nèi)存地址為黑色箭頭所示位置盏混，黑色和藍色箭頭之間剛好16KB。

可以看出惜论，紅色箭頭和黑色箭頭之間的內(nèi)存就無法被使用了许赃，產(chǎn)生了外部碎片。

mmap

如果使用sbrk申請內(nèi)存失敗馆类，TCMalloc會嘗試使用mmap來分配混聊。同樣，為了覆蓋MmapSysAllocator::Alloc()的大部分情況乾巧，下圖假設系統(tǒng)的page為4KB句喜，TCMalloc的page為16KB，申請的內(nèi)存大小為32KB：

tcmalloc-MmapAlloc

1. 假設在申請內(nèi)存之前沟于，mmap段的邊界位于紅色箭頭所示位置咳胃。
2. 第一次mmap，會在32KB的基礎上社裆，多申請(對齊大小 - 系統(tǒng)page大小) = 16 -4 = 12KB的內(nèi)存拙绊。此時mmap的邊界位于綠色箭頭所示位置。
3. 然后通過兩次munmap將所申請內(nèi)存的兩側邊界分別對齊到TCMalloc的page邊界泳秀。
4. 最終申請到的內(nèi)存為兩個藍色箭頭之間的部分标沪，返回左側藍色箭頭所指示的內(nèi)存地址。

如果申請內(nèi)存成功嗜傅，則創(chuàng)建一個新的span并立即刪除金句，可將其放入空閑span的鏈表或set中，然后繼續(xù)后面的步驟吕嘀。

最后的搜索

最后违寞，重新搜索一次空閑span贞瞒，如果還找不到合適的空閑span，那就認為是創(chuàng)建失敗了趁曼。

至此军浆，創(chuàng)建span的操作結束。

刪除Span

// Delete the span "[p, p+n-1]".
// REQUIRES: span was returned by earlier call to New() and
//           has not yet been deleted.
void Delete(Span* span);

當span所拆分成的小對象全部被應用程序釋放變?yōu)榭臻e對象挡闰，或者作為中對象或大對象使用的span被應用程序釋放時乒融，需要將span刪除。不過并不是真正的刪除摄悯，而是放到空閑span的鏈表或set中赞季。

刪除的操作非常簡單，但可能會觸發(fā)合并span的操作奢驯，以及釋放內(nèi)存到系統(tǒng)的操作申钩。

合并Span

當span被delete時，會嘗試向前向后合并一個span瘪阁。

合并規(guī)則如下：

• 只有在虛擬內(nèi)存空間上連續(xù)的span才可以被合并撒遣。
• 只有同是normal狀態(tài)的span或同是returned狀態(tài)的span才可以被合并。

tcmalloc-SpanMerge1

上圖中罗洗，被刪除的span的前一個span是normal狀態(tài)愉舔，因此可以與之合并，而后一個span是returned狀態(tài)伙菜，無法與之合并轩缤。合并操作之后如下圖：

tcmalloc-SpanMerge2

還有一個值得注意的開關：aggressive_decommit_，開啟后TCMalloc會積極的釋放內(nèi)存給系統(tǒng)贩绕，默認是關閉狀態(tài)火的，可通過以下方式更改：

MallocExtension::instance()->SetNumericProperty("tcmalloc.aggressive_memory_decommit", value)

當開啟了aggressive_decommit_后，刪除normal狀態(tài)的span時會嘗試將其釋放給系統(tǒng)淑倾，釋放成功則狀態(tài)變?yōu)閞eturned馏鹤。

在合并時，如果被刪除的span此時是returned狀態(tài)娇哆，則會將與其相鄰的normal狀態(tài)的span也釋放給系統(tǒng)湃累，然后再嘗試合并。

因此碍讨，上面的例子中治力，被刪除的span和其前一個span都會被更改為returned狀態(tài)，合并之后如下勃黍，即三個span被合并成為一個span：

tcmalloc-SpanMerge3

釋放span

Length ReleaseAtLeastNPages(Length num_pages);

在delete一個span時還會以一定的頻率觸發(fā)釋放span的內(nèi)存給系統(tǒng)的操作（ReleaseAtLeastNPages()）宵统。釋放的頻率可以通過環(huán)境變量TCMALLOC_RELEASE_RATE來修改。默認值為1覆获，表示每刪除1000個page就嘗試釋放至少1個page马澈，2表示每刪除500個page嘗試釋放至少1個page瓢省，依次類推，10表示每刪除100個page嘗試釋放至少1個page痊班。0表示永遠不釋放勤婚，值越大表示釋放的越快，合理的取值區(qū)間為[0, 10]辩块。

釋放規(guī)則：

• 從小到大循環(huán)蛔六，按順序釋放空閑span，直到釋放的page數(shù)量滿足需求废亭。
• 多次調(diào)用會從上一次循環(huán)結束的位置繼續(xù)循環(huán)，而不會重新從頭（1 page）開始具钥。
• 釋放的過程中能合并span就合并span
• 可能釋放少于num_pages豆村，沒那么多free的span了。
• 可能釋放多于num_pages骂删，還差一點就夠num_pages了掌动，但剛好碰到一個很大的span。

釋放方式：

如果系統(tǒng)支持宁玫，通過madvise(MADV_DONTNEED)釋放span對應的內(nèi)存粗恢。因此，即使釋放成功欧瘪，對應的虛擬內(nèi)存地址空間仍然可訪問眷射，但內(nèi)存的內(nèi)容會丟失，在下次訪問時會導致minor page fault以用0來重新初始化佛掖。

ThreadCache

TCMalloc分配小對象的速度是非逞铮快的，這得益于其對每個線程都有一份單獨的cache芥被，即ThreadCache欧宜。

ThreadCache其實就是一組FreeList而已。對于每個size class拴魄，在ThreadCache中都有一個FreeList冗茸，緩存了一組空閑對象，應用程序申請256KB以內(nèi)的小內(nèi)存時匹中，優(yōu)先返回FreeList中的一個空閑對象夏漱。因為每個線程每個size class都有單獨的FreeList，因此這個過程是不需要加鎖的职员，速度非陈樘＃快。

如果FreeList為空焊切，TCMalloc才會從size class對應的CentralFreeList中獲取一組空閑對象放入ThreadCache的FreeList中扮授，并將其中一個對象返回芳室。從CentralFreeList中獲取空閑對象需要加鎖的。

回顧下ThreadCache的結構：

tcmalloc-ThreadCache

各個線程的ThreadCache互相連接成為一個雙向鏈表刹勃，主要目的是為了方便統(tǒng)計信息堪侯。

每線程Cache

那么每個線程一個ThreadCache是如何實現(xiàn)的呢？

這依賴于兩種技術：Thread Local Storage（TLS)荔仁，和Thread Specific Data（TSD）伍宦。兩者的功能基本是一樣的，都是提供每線程存儲乏梁。TLS用起來更方便次洼，讀取數(shù)據(jù)更快，但在線程銷毀時TLS無法執(zhí)行清理操作遇骑，而TSD可以卖毁，因此TCMalloc使用TSD為每個線程提供一個ThreadCache，如果TLS可用落萎，則同時使用TLS保存一份拷貝以加速數(shù)據(jù)的訪問亥啦。

TLS和TSD的具體細節(jié)可參考《The Linux Programming Interface》相關章節(jié)（31.3，31.4）练链，本文不再展開討論翔脱。

詳細可參考源碼中ThreadCache::CreateCacheIfNecessary()函數(shù)和threadlocal_data_變量相關代碼。

何時創(chuàng)建ThreadCache

當某線程第一次申請分配內(nèi)存時媒鼓，TCMalloc為該線程創(chuàng)建其專屬的ThreadCache（ThreadCache::GetCache() -> ThreadCache::CreateCacheIfNecessary()）届吁。

何時銷毀ThreadCache

在TCMalloc初始化TSD時，會調(diào)用Pthreads API中的pthread_key_create()創(chuàng)建ThreadCache對應的key隶糕，并且指定了銷毀ThreadCache的函數(shù)ThreadCache::DestroyThreadCache()瓷产。因此，當一個線程銷毀時枚驻，其對應的ThreadCache會由該函數(shù)銷毀濒旦。

ThreadCache的大小

TCMalloc定義了一些變量來建議ThreadCache的大小。注意再登，是建議尔邓，而非強制。也就是說锉矢，實際的大小可能會超過這些值梯嗽。

所有線程的ThreadCache的總大小限制（overall_thread_cache_size_）默認為32MB（kDefaultOverallThreadCacheSize），取值范圍512KB~1GB沽损，可以通過環(huán)境變量TCMalloc_MAX_TOTAL_THREAD_CACHE_BYTES或以下方式來進行調(diào)整：

MallocExtension::instance()->SetNumericProperty("TCMalloc.max_total_thread_cache_bytes", value);

每個線程的ThreadCache的大小限制默認為4MB（kMaxThreadCacheSize）灯节。調(diào)整ThreadCache總大小時，會修改每個ThreadCache的大小限制到512KB~4MB之間的相應值。

慢啟動算法：FreeList的長度控制

控制ThreadCache中各個FreeList中元素的數(shù)量是很重要的：

• 太醒捉：不夠用卡骂，需要經(jīng)常去CentralCache獲取空閑對象，帶鎖操作
• 太大：太多對象在空閑列表中閑置形入，浪費內(nèi)存

不僅是內(nèi)存分配全跨，對于內(nèi)存釋放來說控制FreeList的長度也很重要：

• 太小：需要經(jīng)常將空閑對象移至CentralCache亿遂，帶鎖操作
• 太大：太多對象在空閑列表中閑置浓若，浪費內(nèi)存

并且，有些線程的分配和釋放是不對稱的蛇数，比如生產(chǎn)者線程和消費者線程挪钓，這也是需要考慮的一個點。

類似TCP的擁塞控制算法耳舅，TCMalloc采用了慢啟動（slow start）的方式來控制FreeList的長度诵原，其效果如下：

• FreeList被使用的越頻繁，最大長度就越大挽放。
• 如果FreeList更多的用于釋放而不是分配，則其最大長度將僅會增長到某一個點蔓纠，以有效的將整個空閑對象鏈表一次性移動到CentralCache中辑畦。

分配內(nèi)存時的慢啟動代碼如下（FetchFromCentralCache）：

const int batch_size = Static::sizemap()->num_objects_to_move(cl);

// Increase max length slowly up to batch_size.  After that,
// increase by batch_size in one shot so that the length is a
// multiple of batch_size.
if (list->max_length() < batch_size) {
  list->set_max_length(list->max_length() + 1);
} else { 
  // Don't let the list get too long.  In 32 bit builds, the length
  // is represented by a 16 bit int, so we need to watch out for
  // integer overflow.
  int new_length = min<int>(list->max_length() + batch_size,
                            kMaxDynamicFreeListLength);
  // The list's max_length must always be a multiple of batch_size,
  // and kMaxDynamicFreeListLength is not necessarily a multiple
  // of batch_size.
  new_length -= new_length % batch_size;
  ASSERT(new_length % batch_size == 0);
  list->set_max_length(new_length);
}

max_length即為FreeList的最大長度，初始值為1腿倚。batch_size是size class一節(jié)提到的一次性移動空閑對象的數(shù)量，其值因size class而異暂筝。

可以看到焕襟，只要max_length沒有超過batch_size饭豹，每當FreeList中沒有元素需要從CentralCache獲取空閑對象時（即FetchFromCentralCache），max_length就加1它褪。

一旦max_length達到batch_size翘悉，接下來每次FetchFromCentralCache就會導致max_length增加batch_size茫打。

但并不會無限制的增加，最大到kMaxDynamicFreeListLength（8192），以避免從FreeList向CentralCache移動對象時老赤，因為對象過多而過長的占用鎖轮洋。

再來看內(nèi)存回收時的情況，每次釋放小對象诗越，都會檢查FreeList的當前長度是否超過max_length：

if (PREDICT_FALSE(length > list->max_length())) {
  ListTooLong(list, cl);
  return;
} 

如果超長砖瞧，則執(zhí)行以下邏輯：

void ThreadCache::ListTooLong(FreeList* list, uint32 cl) {
  size_ += list->object_size();
    
  const int batch_size = Static::sizemap()->num_objects_to_move(cl);
  ReleaseToCentralCache(list, cl, batch_size);
  
  // If the list is too long, we need to transfer some number of
  // objects to the central cache.  Ideally, we would transfer
  // num_objects_to_move, so the code below tries to make max_length
  // converge on num_objects_to_move.
      
  if (list->max_length() < batch_size) {
    // Slow start the max_length so we don't overreserve.
    list->set_max_length(list->max_length() + 1);
  } else if (list->max_length() > batch_size) {
    // If we consistently go over max_length, shrink max_length.  If we don't
    // shrink it, some amount of memory will always stay in this freelist.
    list->set_length_overages(list->length_overages() + 1);
    if (list->length_overages() > kMaxOverages) {
      ASSERT(list->max_length() > batch_size);
      list->set_max_length(list->max_length() - batch_size);
      list->set_length_overages(0);
    }
  }

  if (PREDICT_FALSE(size_ > max_size_)) {
    Scavenge();
  }
}

與內(nèi)存分配的情況類似，只要max_length還沒有達到batch_size嚷狞，每當FreeList的長度超過max_length块促，max_length的值就加1。

當max_length達到或超過batch_size后床未，并不會立即調(diào)整max_length竭翠，而是累計超過3次（kMaxOverages）后，才會將max_length減少batch_size薇搁。

垃圾回收

TODO：本節(jié)還沒寫完斋扰，請先參閱官方介紹Garbage Collection of Thread Caches一節(jié)。啃洋。

從ThreadCache中回收垃圾對象传货，將未使用的對象返回到CentralFreeList，可以控制緩存的大小宏娄。

不同線程對緩存大小的需求是不一樣的粮宛，因此不能統(tǒng)一對待：有些線程需要大的緩存，有些線程需要小的緩存即可扛伍，甚至有些線程不需要緩存汁咏。

當一個ThreadCache大小超過其max_size_時攘滩，觸發(fā)垃圾回收：

if (PREDICT_FALSE(size_ > max_size_)){
  Scavenge();
}

只有當應用程序釋放內(nèi)存時（ThreadCache::Deallocate()）才會觸發(fā)垃圾回收赖瞒，遍歷ThreadCache中所有的FreeList栏饮，將FreeList中的一些對象移至對應的CentralFreeList中。

具體移動多少對象由低水位標記L（lowater_伺通，每個FreeList一個）來決定罐监。L記錄自上次垃圾收集以來，F(xiàn)reeList的最小長度矢空。

CentralCache

CentralCache是邏輯上的概念妇多，其本質(zhì)是CentralFreeListPadded類型（CentralFreeList的子類立莉，用于64字節(jié)對齊）的數(shù)組茫舶，每個size class對應數(shù)組中的一個元素饶氏。

ATTRIBUTE_HIDDEN static CentralFreeListPadded central_cache_[kClassSizesMax];

由于各線程公用一個CentralCache，因此喊崖，使用CentralCache時需要加鎖茁裙。

以下討論都是針對某一個size class的。

CentralFreeList中緩存了一系列小對象矾瘾，供各線程的ThreadCache取用霜威，各線程也會將多余的空閑小對象還給CentralFreeList，另外CentralFreeList還負責從PageHeap申請span以分割成小對象大猛，以及將不再使用的span還給PageHeap。

管理span

CentralFreeList真正管理的是span唉堪，而小對象是包含在span中的空閑對象鏈表中的唠亚。CentralFreeList的empty_鏈表保存了已經(jīng)沒有空閑對象可用的span灶搜，nonempty_鏈表保存了還有空閑對象可用的span：

tcmalloc-CentralFreeList

CentralFreeList? PageHeap

從PageHeap獲取span

當ThreadCache從CentralFreeList取用空閑對象（RemoveRange）患雏，但CentralFreeList的空閑對象數(shù)量不夠時剿涮，CentralFreeList調(diào)用Populate()從PageHeap申請一個span拆分成若干小對象悬槽，首首連接記錄在span的objects指針中初婆，即每個小對象的起始位置處，記錄了下一個小對象的地址弊琴。此時的span如下圖：

tcmalloc-FreshSpan

可以看到，此時span包含的對象按順序連接在一起腋寨。

新申請的span被放入CentralFreeList的nonempty_鏈表頭部。

將span還給PageHeap

CentralFreeList維護span的成員變量refcount，用來記錄ThreadCache從中獲取了多少對象赖阻。

當ThreadCache將不再使用的對象歸還給CentralCache以致refcount減為0棋电，即span中所有對象都空閑時企锌，則CentralCache將這個span還給PageHeap陡鹃。截取CentralFreeList::ReleaseToSpans()部分代碼如下：

span->refcount--;
if (span->refcount == 0) {
  Event(span, '#', 0);
  counter_ -= ((span->length<<kPageShift) /
               Static::sizemap()->ByteSizeForClass(span->sizeclass));
  tcmalloc::DLL_Remove(span);
  --num_spans_;

  // Release central list lock while operating on pageheap
  lock_.Unlock();
  {
    SpinLockHolder h(Static::pageheap_lock());
    Static::pageheap()->Delete(span);
  }
  lock_.Lock();
}

CentralFreeList?ThreadCache

CentralFreeList和ThreadCache之間的對象移動是批量進行的：

// Insert the specified range into the central freelist.  N is the number of
// elements in the range.  RemoveRange() is the opposite operation.
void InsertRange(void *start, void *end, int N);

// Returns the actual number of fetched elements and sets *start and *end.
int RemoveRange(void **start, void **end, int N);

start和end指定小對象鏈表的范圍，N指定小對象的數(shù)量脊阴。批量移動小對象可以均攤鎖操作的開銷嘿期。

ThreadCache取用小對象

當ThreadCache中某個size class沒有空閑對象可用時，需要從CentralFreeList獲取N個對象，那么N的值是多少呢瓣铣？從ThreadCache::FetchFromCentralCache()中可以找到答案：

const int batch_size = Static::sizemap()->num_objects_to_move(cl);
const int num_to_move = min<int>(list->max_length(), batch_size);
void *start, *end;
int fetch_count = Static::central_cache()[cl].RemoveRange(&start, &end, num_to_move);

移動數(shù)量N為max_length和batch_size的最小值（兩者的具體涵義參見ThreadCache慢啟動一節(jié)）。

假設只考慮內(nèi)存分配的情況蓖救，一開始移動1個，然后是2個从橘、3個，以此類推，同時max_length每次也加1香府，直到達到batch_size后锭碳，每次移動batch_size個對象工禾。

CentralFreeList和ThreadCache之間的對象移動有個優(yōu)化措施癣丧，因為大部分情況都是每次移動batch_size個對象胁编，為了減少鏈表操作早直，提升效率枫振，CentralFreeList將移動的batch_size個對象的鏈表的首尾指針緩存在了TCEntry中斧拍。因此后續(xù)只要需要移動batch_size個對象予权，只需要操作鏈表的首尾即可昂勉。

// Here we reserve space for TCEntry cache slots.  Space is preallocated
// for the largest possible number of entries than any one size class may
// accumulate.  Not all size classes are allowed to accumulate
// kMaxNumTransferEntries, so there is some wasted space for those size
// classes.
TCEntry tc_slots_[kMaxNumTransferEntries];

ThreadCache歸還小對象

當ThreadCache中的空閑對象過多時（ThreadCache::ListTooLong()），會將一部分空閑對象放回CentralFreeList（ThreadCache::ReleaseToCentralCache()）伟件。如何判斷空閑對象過多請參考ThreadCache慢啟動一節(jié)。

線程銷毀也會將其ThreadCache中所有的空閑對象都放回CentralFreeList议经。

如果ThreadCache緩存的內(nèi)存大小超過其允許的最大值斧账，會觸發(fā)GC操作（ThreadCache::Scavenge()）谴返，在其中也會將部分小對象歸還給CentralFreeList习绢，具體請參考ThreadCache垃圾回收一節(jié)放航。

全文完。