本節(jié)將專注于TCMalloc 的架構(gòu)設(shè)計細(xì)節(jié)，來整體看一下TCMalloc 的設(shè)計特性。

主要的幾個特性如下：

1. 高性能。大多數(shù)對象的分配和釋放都不需要產(chǎn)生太多的競爭，因為tcmalloc 維護(hù)了thread-cache 來提供當(dāng)前線程的內(nèi)存分配需求。所以，應(yīng)用大多數(shù)的內(nèi)存申請需求不會有鎖的競爭，而且在多核場景有較好的擴(kuò)展性。
2. 靈活的使用內(nèi)存資源。用戶不使用的內(nèi)存，tcmalloc會選擇服復(fù)用或者歸還操作系統(tǒng)。
3. 降低了每個請求的內(nèi)存開銷。通過分配相同大小的page 降低內(nèi)存使用的開銷，這在小對象場景較為有效。
4. 內(nèi)部信息統(tǒng)計開銷較低。能夠開啟細(xì)粒度的應(yīng)用內(nèi)存占用信息，來幫助用戶展示tcmalloc內(nèi)部內(nèi)存使用的細(xì)節(jié)。

如何使用

安裝tcmalloc，應(yīng)用編譯加入 -ltcmalloc即可默認(rèn)將glibc的malloc 替換為tcmalloc的malloc 。

架構(gòu)概覽

前面的文章中在介紹整體的tcmalloc的時候已經(jīng)介紹過了，大體分為三個部分：

• Front-end，主要維護(hù)線程cache，用來為應(yīng)用提供 快速分配以及釋放內(nèi)存的需求。
• Middle-end，主要負(fù)責(zé)為font-end 中的thread-cache 填充內(nèi)存。
• back-end，負(fù)責(zé)從os直接獲取內(nèi)存。

需要注意的是front-end 的 thread-cache 可以在每一個cpu下維護(hù) 或者 每一個線程下維護(hù)，back-end` 則能夠支持大內(nèi)存的pageheap管理，也能支持小內(nèi)存的pageheap 管理。

接下來，我們進(jìn)入每一個組件詳細(xì)看一下其設(shè)計細(xì)節(jié)。

1. TCMalloc Front-end

Front-end 提供了Cache ，能夠緩存一部分內(nèi)存 用來分配給應(yīng)用 ，也能夠持有應(yīng)用釋放的內(nèi)存。這個Cache 作為per-cpu/per-thread 存在，其同一時刻只能由一個線程訪問，所以本身不需要任何的鎖，這也是多線程下內(nèi)存分配釋放高效的原因。

如果Front-end 持有的內(nèi)存大小足夠，其能夠滿足應(yīng)用線程任何內(nèi)存需求。如果持有的內(nèi)存為空了，那它會從 middle-end 組件請求一批內(nèi)存頁進(jìn)行填充。

Middle-end 是由 CentralFreeList 和 TransferCache 兩部分組成，后續(xù)會詳細(xì)介紹這兩個組件。

如果用戶請求的內(nèi)存大小超過了front-end 本身能緩存的大小（大內(nèi)存需求），或者middle-end 緩存的內(nèi)存頁也被用盡了，那這個時候會直接讓從back-end分配內(nèi)存給用戶。

Front-end 在 TCMalloc 的演進(jìn)過程中有兩種類型的實現(xiàn)：

1. 最開始的時候只支持 per-thread 的cache 模式，這也是TCMalloc 名字 Thread-Cacheing malloc的由來。然而這種場景會隨著用戶線程的大量增加，出現(xiàn)了一些內(nèi)存問題：每個線程只能有極小的thread-cache，需要消耗較多的CPU資源來聚合每個線程的內(nèi)存資源。
2. 較新版本的TCMalloc 支持了 per-CPU 模式。這種模式下每一個邏輯CPU 會有自己的的thread-cache 用來為運行在這個cpu的現(xiàn)場分配內(nèi)存。在x86系統(tǒng)上，每一個邏輯cpu 和 一個超線程等價，我們lscpu 命令看到的cpu core是包括超線程的個數(shù)在內(nèi)的。

1.1 小對象和大對象的內(nèi)存分配過程

針對小內(nèi)存對象的分配，F(xiàn)ront-end的cache 會按照其大小將其映射到 60-80個size-classes 中的一個，實際的內(nèi)存分配會按照該大小對應(yīng)的size-class 的大小進(jìn)行分配，size-class也是front-end 分配內(nèi)存的粒度。

比如12B 的對象會best-fit到16B 的size-class中。設(shè)置這么多的size-class 還是為了盡可能得降低內(nèi)存的浪費，比如原本的內(nèi)存分配粒度都是2的n次冪，那對于23字節(jié)的內(nèi)存需求就需要分配一個32字節(jié)的內(nèi)存區(qū)域，而在tcmalloc的size-class的配置中只需要分配24字節(jié)即可。

Tcmalloc 在編譯的時候可以配置 size-class 的 內(nèi)存分配是按照多少 Bytes 對齊，比如指定了__STDCPP_DEFAULT_NEW_ALIGNMENT__ <= 8，那size-class 內(nèi)部可選的內(nèi)存大小配置就是 8bytes 對齊，即8 bytes的倍數(shù)。如果編譯時指定了大于 8bytes，那后續(xù)所有的 ::operator new 的內(nèi)存申請都會按照 16 bytes 進(jìn)行對齊。

對于大內(nèi)存需求的對象來說，內(nèi)存大小的需求超過kMaxSize 256K，則會直接從back-end 分配。因此，這一部分的內(nèi)存需求不會緩存再 front-end 以及 middle-end 中，由back-end的page-heap 進(jìn)行管理。對于大內(nèi)存對象的實際內(nèi)存分配會按照tcmalloc page size 進(jìn)行對齊。

1.2 內(nèi)存釋放過程

如果要釋放一個對象，編譯期間如果能夠知道這個對象的大小，編譯器會直接告訴分配器這個對象的大小。大多數(shù)的時候，編譯期間并不清楚對象的大小，會從pagemap中查找這個對象。如果這個對象是一個小內(nèi)存對象，釋放的時候會告訴front-end cache進(jìn)行管理，如果是一個超過kMaxSize 的對象，則會直接釋放給back-end 的 pageheap。

1.3 Per-CPU mode

Per-cpu mode 和 per-thread mode 是 tcmalloc 的font-end 主體部分的兩種模式。因為per-thread mode 受到系統(tǒng)進(jìn)程的線程數(shù)的影響，在大量線程的情況下會讓每個thread-cache 只能夠處理一小部分的內(nèi)存申請釋放需求，還會消耗大量的cpu 來 由middle-end 進(jìn)行不同thread-cache 之間的內(nèi)存遷移。

所以 tcmalloc 提供了優(yōu)化版本的 per-cpu mode，即每一個邏輯核 維護(hù)一個 ‘cpu-cache’ ，用來處理運行在當(dāng)前核的線程的內(nèi)存申請/釋放需求。

大體形態(tài)如下：

Per-cpu mode 下會申請一個大內(nèi)存塊(也可以稱為slab)，這個slab 會被多個cpu共享，其中每一個cpu會 持有slab 的一部分內(nèi)存，并在其上存儲一系列元數(shù)據(jù)管理對應(yīng)線程的內(nèi)存對象。

上圖中的cpu1 會管理 on slab 的綠色部分內(nèi)存區(qū)域，在這一部分區(qū)域中會先存儲一些元數(shù)據(jù)和指針來管理不同大小的 size-classes 的內(nèi)存對象。其中元數(shù)據(jù)中包含一個header指針 和 每一個size-class 的索引block。

每一個size-class 的header 指針數(shù)據(jù)結(jié)構(gòu)會有指向某一種實際存儲內(nèi)存對象的指針數(shù)組，即是一個數(shù)組，每一個元素是一個指針，總共是三個指針，分別指向這一種size-class 內(nèi)存對象區(qū)域的起始地址塊，當(dāng)前地址塊（后續(xù)分配這個size-class 大小對象的時候會從current 開始分配），最大地址。

每一個cpu 能夠緩存的內(nèi)存大小是通過SetMaxPerCpuCacheSize 配置的，也就是當(dāng)前font-end 能夠緩存的內(nèi)存總大小取決去當(dāng)前系統(tǒng)的cpu核心數(shù)，擁有更好核心數(shù)的機(jī)器使用tcmalloc 能夠緩存更多的內(nèi)存。為了避免 perf-cpu 長時間持有內(nèi)存，tcmalloc 允許通過MallocExtension::ReleaseCpuMemory 接口來 指定釋放某一個cpu的內(nèi)存。

當(dāng)每一個cpu cache 的內(nèi)存被分配耗盡，想要從 middle-end 獲取內(nèi)存來緩存更多的對象時，也需要考慮對size-class進(jìn)行擴(kuò)容。如果這個size-class 的內(nèi)存分配需求還在持續(xù)增加，則這個size-class的容量會持續(xù)增加，直到達(dá)到這個size-class 容量的hard-code。

1.4 Per-thread mode

用戶可以指定使用某一個thread 的cache，也就是指定thread-local cache。小內(nèi)存的申請和釋放會根據(jù)thread-cache的需求在middle-end 之間遷移。

每一個 thread-cache 內(nèi)部 不同size-class 對象會各自構(gòu)造一個單鏈表（如果有 n 個size-classes，也就會有對應(yīng) n 個單鏈表），類似如下圖：

分配某一個對應(yīng)size-class 對象的時候，對應(yīng) size-class 鏈表對象會被從單鏈表移除（free-list），表示這個指針對應(yīng)地址的內(nèi)存可以被用戶使用。釋放對象的時候，則會將這個對象地址追加到thread-cache 管理的 size-class 的鏈表。

在這個過程中，如果thread-cache 管理的內(nèi)存不夠，或者超限，則會從 middle-end 獲取更多的內(nèi)存對象或者將多余的內(nèi)存對象釋放給 middle-end。

對于per-thread caches來說，可以通過 MallocExtension::SetMaxTotalThreadCacheBytes 設(shè)置最大的可用內(nèi)存大小。每一個線程有自己的最小的 thread-cache 大小 KMinThreadCacheSize 512K，如果當(dāng)前線程內(nèi)存申請需求較大，內(nèi)存容量也會通過middle-end 將其他線程的可用內(nèi)存遷移到當(dāng)前線程。

通過 middle-end 來協(xié)調(diào)當(dāng)前的thread-cache 內(nèi)存，通過ThreadCache::Scavenge(); 進(jìn)行。

如果當(dāng)前線程退出，則會將自己的thread-cache 的內(nèi)存返回給 middle-end。

1.5 per-cpu 和 per-thread 運行時內(nèi)存管理算法對比

對于thread-cache 和 per-cpu cache來說，在應(yīng)用程序運行的時候如果 front-end 的cache 內(nèi)存太小，那就需要頻繁從 central-freelist 也就是 middle-end 中獲取內(nèi)存；但如果太大，就會讓過多的內(nèi)存被閑置。如何配置一個合理的 front-end cache 的大小，這里兩種模式都提供了動態(tài)配置 cache大小的算法。

• Per-thread 模式下，cache 內(nèi)部的最大存儲對象容量 達(dá)到當(dāng)前最大閾值時就會從middle-end 獲取更多的對象，從而增大這個限制。降低最大限制的前提是發(fā)現(xiàn)了較多的未被使用的對象，則會將這一些對象根據(jù)需求還給middle-end。
• Per-cpu 模式下，增加cache 容量的前提是當(dāng)前cache 是否在頻繁的從 middle-end 獲取內(nèi)存 以及 釋放內(nèi)存交替，則需增加容量限制，有更多的空間來緩存這一些內(nèi)存對象。降低容量限制的前提是發(fā)現(xiàn)有一些空閑容量長時間沒有被使用。

這里在代碼細(xì)節(jié)上有很多的設(shè)計，比如如何設(shè)置合理的空閑時間的長度？如何界定 內(nèi)存申請是頻繁的？都是一些動態(tài)規(guī)劃的最優(yōu)思想的設(shè)計，值得去探索代碼細(xì)節(jié)。

2. TCMalloc Middle-end

到此，font-end 部分大體設(shè)計描述完。從前面的設(shè)計中可以看到，middle-end 的作用在 per-cpu和per-thread 模式都有非常重要的作用。

Middle-end 的主要作用為 font-end 提供內(nèi)存申請需求，并將空閑內(nèi)存返回給 back-end。

Middle-end 的組成主要有 Transfer cache 和 Central free list。對于每一個size-class，都會有有一個各自的 transfer cache 和 central free list。這一些caches 會有自己的 mutex lock，所以對于這一些cache的訪問， 因為鎖粒度較低，則不會有過多的沖突，保證了訪問的性能。

2.1 Transfer Cache

當(dāng) front-end 請求內(nèi)存 或者 釋放內(nèi)存的時候，會先到達(dá) transfer cache。

Transfer cache 會持有 一個數(shù)組指針進(jìn)行內(nèi)存的釋放 或者 將新的內(nèi)存對象填充進(jìn)來并返回給font-end。

Transfer cache 會將一個cpu/tthread 釋放的內(nèi)存分配給另一個cpu/thread 對內(nèi)存的需求，這個類似于內(nèi)存池的 內(nèi)存對象流動在兩個不同的cpu/threads 之間可以非常迅速。

2.2 Central Free List

Central free list 通過 span 數(shù)據(jù)結(jié)構(gòu)來管理內(nèi)存，一個span 可以管理一個或者多個tcmalloc page，span 數(shù)據(jù)結(jié)構(gòu)會在下文詳細(xì)描述。

Font-end 如果從 central free list 請求一個或者多個內(nèi)存對象的時候，central free list 會從span中提取對應(yīng)大小的對象，如果此時span 沒有足夠的pages 返回，則會從back-end 請求更多的span。

當(dāng)內(nèi)存對象返回給central free list，則這一些對象會通過 pagemap 被映射到對應(yīng)的span中進(jìn)行管理，如果所有的對象都返回給span，這個span就可以被釋放給back-end.

2.3 Pagemap 和 Spans

tcmalloc 管理的堆內(nèi)存會在編譯期間確定一個page-size，并將這么多內(nèi)存映射為對應(yīng)size的一個個page。一系列正在被使用的pages 可以被一個span 對象描述，一個span 對象可以管理一個大的內(nèi)存對象，也可以按照size-class 管理多個小對象。

pagemap 則是用來查找一個內(nèi)存對象屬于哪一個span的，或者申請一個指定size-class 的內(nèi)存對象。pagemap 是一個 2層或者3層的 radix-tree。下圖展示了一個兩層的 page-map 如何管理 span的，其中 spanA 管理了2個page，spanB 管理了三個page。

Span 這個數(shù)據(jù)結(jié)構(gòu) 在 middle-end中用來 管理回收的內(nèi)存對象；在back-end 用來管理 對應(yīng)大小的pages，負(fù)責(zé)給central-list 提供對應(yīng)大小的span。

3. TCMalloc Backend

tcmalloc 的back-end 主要有三個工作線程：

• 管理未使用的大塊內(nèi)存區(qū)域
• 負(fù)責(zé)從 os 中獲取內(nèi)存，來滿足其他組件的內(nèi)存需求
• 負(fù)責(zé)將其他組件不需要返回的內(nèi)存，還給os

還有兩個后端組件：

1. legacy pageheap. 管理tcmalloc 的pages
2. 管理大頁內(nèi)存的 pageheap。用來提升應(yīng)用程序大頁內(nèi)存的申請需求，降低TLB的miss。

3.1 Legacy Pageheap

legacy pageheap 是一個數(shù)組的freelist，統(tǒng)一管理可用內(nèi)存頁。數(shù)組的每一個節(jié)點是一個free list，也就是單鏈表。一般這個數(shù)組的大小 k < 256，對于第k 個數(shù)組元素來說，它的鏈表中的每一個節(jié)點都管理了 k 個pages。

如果想要申請 k 個pages，則直接查找這個數(shù)組的第k 個元素，從free list中取一個節(jié)點即可。如果這個free list是空的，那就查找下一個數(shù)組元素的free list,直到找到一個非空的free list。如果還是失敗，則直接mmap 獲取內(nèi)存。

當(dāng)一段連續(xù)的pages 被返回給了pageheap，則會根據(jù)當(dāng)前pages 是否能夠形成一個連續(xù)的pages區(qū)域，然后串聯(lián)這一些pages 并根據(jù)page數(shù)量 添加到對應(yīng)的free list中。

3.2 大頁場景分配器設(shè)計

針對hugepage 的分配器設(shè)計 是希望其能夠有效持有 hugepage 大小的內(nèi)存塊，需要的時候能夠快速分配，不需要的時候也能在合理的內(nèi)存占用情況下釋放給操作系統(tǒng)。

hugepage 在x86 系統(tǒng)上一般是2M 及 以上的大小，tcmalloc 的back-end 擁有三個不同的cache 來管理大頁內(nèi)存的分配：

1. filler cache。能夠持有hugepage ，并提供一些大頁內(nèi)存的申請需求。類似于legacy pageheap，通過一些free lists 管理pages 那樣管理huge page，主要用于處理小于hugepage 大小的內(nèi)存申請。
2. region cache。用于大于hugepage 大小的內(nèi)存申請，這個cache 允許分配多個連續(xù)的hugepage。
3. hugepage cache。和region cache的功能有點重復(fù)，也是用于分配大于hugepage 的內(nèi)存申請。