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

主要的幾個(gè)特性如下：

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

如何使用

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

架構(gòu)概覽

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

• Front-end，主要維護(hù)線程cache，用來(lái)為應(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 可以在每一個(gè)cpu下維護(hù) 或者 每一個(gè)線程下維護(hù)，back-end` 則能夠支持大內(nèi)存的pageheap管理，也能支持小內(nèi)存的pageheap 管理。

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

1. TCMalloc Front-end

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

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

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

如果用戶請(qǐng)求的內(nèi)存大小超過(guò)了front-end 本身能緩存的大?。ù髢?nèi)存需求），或者middle-end 緩存的內(nèi)存頁(yè)也被用盡了，那這個(gè)時(shí)候會(huì)直接讓從back-end分配內(nèi)存給用戶。

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

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

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

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

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

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

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

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

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

1.3 Per-CPU mode

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

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

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

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

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

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

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

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

1.4 Per-thread mode

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

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

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

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

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

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

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

1.5 per-cpu 和 per-thread 運(yùn)行時(shí)內(nèi)存管理算法對(duì)比

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

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

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

2. TCMalloc Middle-end

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

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

Middle-end 的組成主要有 Transfer cache 和 Central free list。對(duì)于每一個(gè)size-class，都會(huì)有有一個(gè)各自的 transfer cache 和 central free list。這一些caches 會(huì)有自己的 mutex lock，所以對(duì)于這一些cache的訪問(wèn)， 因?yàn)殒i粒度較低，則不會(huì)有過(guò)多的沖突，保證了訪問(wèn)的性能。

2.1 Transfer Cache

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

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

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

2.2 Central Free List

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

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

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

2.3 Pagemap 和 Spans

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

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

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

3. TCMalloc Backend

tcmalloc 的back-end 主要有三個(gè)工作線程：

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

還有兩個(gè)后端組件：

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

3.1 Legacy Pageheap

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

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

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

3.2 大頁(yè)場(chǎng)景分配器設(shè)計(jì)

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

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

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