內存分配器：TCMalloc 基本設計原理詳解

本節將專注於 TCMalloc 的架構設計細節，來整體看一下 TCMalloc 的設計特性。

主要的幾個特性如下：

高性能。大多數對象的分配和釋放都不需要產生太多的競爭，因爲 tcmalloc 維護了 thread-cache 來提供當前線程的內存分配需求。所以，應用大多數的內存申請需求不會有鎖的競爭，而且在多核場景有較好的擴展性。
靈活的使用內存資源。用戶不使用的內存，tcmalloc 會選擇服複用或者歸還操作系統。
降低了每個請求的內存開銷。通過分配相同大小的 page 降低內存使用的開銷，這在小對象場景較爲有效。
內部信息統計開銷較低。能夠開啓細粒度的應用內存佔用信息，來幫助用戶展示 tcmalloc 內部內存使用的細節。

如何使用

安裝 tcmalloc，應用編譯加入 -ltcmalloc 即可默認將 glibc 的 malloc 替換爲 tcmalloc 的 malloc 。

架構概覽

前面的文章中在介紹整體的 tcmalloc 的時候已經介紹過了，大體分爲三個部分：

Front-end，主要維護線程 cache，用來爲應用提供快速分配以及釋放內存的需求。
Middle-end，主要負責爲 font-end 中的 thread-cache 填充內存。
back-end，負責從 os 直接獲取內存。

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

接下來，我們進入每一個組件詳細看一下其設計細節。

TCMalloc Front-end

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

如果 Front-end 持有的內存大小足夠，其能夠滿足應用線程任何內存需求。如果持有的內存爲空了，那它會從 middle-end 組件請求一批內存頁進行填充。

Middle-end 是由 CentralFreeList 和 TransferCache 兩部分組成，後續會詳細介紹這兩個組件。

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

Front-end 在 TCMalloc 的演進過程中有兩種類型的實現：

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

1.1 小對象和大對象的內存分配過程

針對小內存對象的分配，Front-end 的 cache 會按照其大小將其映射到 60-80 個 size-classes 中的一個，實際的內存分配會按照該大小對應的 size-class 的大小進行分配，size-class 也是 front-end 分配內存的粒度。

比如 12B 的對象會 best-fit 到 16B 的 size-class 中。設置這麼多的 size-class 還是爲了儘可能得降低內存的浪費，比如原本的內存分配粒度都是 2 的 n 次冪，那對於 23 字節的內存需求就需要分配一個 32 字節的內存區域，而在 tcmalloc 的 size-class 的配置中只需要分配 24 字節即可。

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

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

1.2 內存釋放過程

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

1.3 Per-CPU mode

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

所以 tcmalloc 提供了優化版本的 per-cpu mode，即每一個邏輯核維護一個 ‘cpu-cache’ ，用來處理運行在當前核的線程的內存申請 / 釋放需求。

大體形態如下：

Per-cpu mode 下會申請一個大內存塊 (也可以稱爲 slab)，這個 slab 會被多個 cpu 共享，其中每一個 cpu 會持有 slab 的一部分內存，並在其上存儲一系列元數據管理對應線程的內存對象。

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

每一個 size-class 的 header 指針數據結構會有指向某一種實際存儲內存對象的指針數組，即是一個數組，每一個元素是一個指針，總共是三個指針，分別指向這一種 size-class 內存對象區域的起始地址塊，當前地址塊（後續分配這個 size-class 大小對象的時候會從 current 開始分配），最大地址。

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

// 設置每一個cpu 能夠cache住的內存大小
void MallocExtension::SetMaxPerCpuCacheSize(int32_t value) {
#if ABSL_INTERNAL_HAVE_WEAK_MALLOCEXTENSION_STUBS
  if (MallocExtension_Internal_SetMaxPerCpuCacheSize == nullptr) {
    return;
  }

  MallocExtension_Internal_SetMaxPerCpuCacheSize(value); // 實際的執行函數
#else
  (void)value;
#endif
}

// 釋放某一個cpu cache的內存
size_t MallocExtension::ReleaseCpuMemory(int cpu) {
#if ABSL_INTERNAL_HAVE_WEAK_MALLOCEXTENSION_STUBS
  if (MallocExtension_Internal_ReleaseCpuMemory != nullptr) {
    return MallocExtension_Internal_ReleaseCpuMemory(cpu);
  }
#endif
  return 0;
}

當每一個 cpu cache 的內存被分配耗盡，想要從 middle-end 獲取內存來緩存更多的對象時，也需要考慮對 size-class 進行擴容。如果這個 size-class 的內存分配需求還在持續增加，則這個 size-class 的容量會持續增加，直到達到這個 size-class 容量的 hard-code。

1.4 Per-thread mode

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

每一個 thread-cache 內部不同 size-class 對象會各自構造一個單鏈表（如果有 n 個 size-classes，也就會有對應 n 個單鏈表），類似如下圖：

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

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

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

通過 middle-end 來協調當前的 thread-cache 內存，通過 ThreadCache::Scavenge(); 進行。

如果當前線程退出，則會將自己的 thread-cache 的內存返回給 middle-end。

1.5 per-cpu 和 per-thread 運行時內存管理算法對比

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

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

這裏在代碼細節上有很多的設計，比如如何設置合理的空閒時間的長度？如何界定內存申請是頻繁的？都是一些動態規劃的最優思想的設計，值得去探索代碼細節。

TCMalloc Middle-end

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

Middle-end 的主要作用爲 font-end 提供內存申請需求，並將空閒內存返回給 back-end。

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

2.1 Transfer Cache

當 front-end 請求內存或者釋放內存的時候，會先到達 transfer cache。

Transfer cache 會持有一個數組指針進行內存的釋放或者將新的內存對象填充進來並返回給 font-end。

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

2.2 Central Free List

Central free list 通過 span 數據結構來管理內存，一個 span 可以管理一個或者多個 tcmalloc page，span 數據結構會在下文詳細描述。

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

當內存對象返回給 central free list，則這一些對象會通過 pagemap 被映射到對應的 span 中進行管理，如果所有的對象都返回給 span，這個 span 就可以被釋放給 back-end.

2.3 Pagemap 和 Spans

tcmalloc 管理的堆內存會在編譯期間確定一個 page-size，並將這麼多內存映射爲對應 size 的一個個 page。一系列正在被使用的 pages 可以被一個 span 對象描述，一個 span 對象可以管理一個大的內存對象，也可以按照 size-class 管理多個小對象。

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

Span 這個數據結構在 middle-end 中用來管理回收的內存對象；在 back-end 用來管理對應大小的 pages，負責給 central-list 提供對應大小的 span。

TCMalloc Backend

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

管理未使用的大塊內存區域
負責從 os 中獲取內存，來滿足其他組件的內存需求
負責將其他組件不需要返回的內存，還給 os

還有兩個後端組件：

legacy pageheap. 管理 tcmalloc 的 pages
管理大頁內存的 pageheap。用來提升應用程序大頁內存的申請需求，降低 TLB 的 miss。

3.1 Legacy Pageheap

legacy pageheap 是一個數組的 freelist，統一管理可用內存頁。數組的每一個節點是一個 free list，也就是單鏈表。一般這個數組的大小 k < 256，對於第 k 個數組元素來說，它的鏈表中的每一個節點都管理了 k 個 pages。

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

當一段連續的 pages 被返回給了 pageheap，則會根據當前 pages 是否能夠形成一個連續的 pages 區域，然後串聯這一些 pages 並根據 page 數量添加到對應的 free list 中。

3.2 大頁場景分配器設計

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

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

filler cache。能夠持有 hugepage ，並提供一些大頁內存的申請需求。類似於 legacy pageheap，通過一些 free lists 管理 pages 那樣管理 huge page，主要用於處理小於 hugepage 大小的內存申請。
region cache。用於大於 hugepage 大小的內存申請，這個 cache 允許分配多個連續的 hugepage。
hugepage cache。和 region cache 的功能有點重複，也是用於分配大於 hugepage 的內存申請。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/kV0sqWI8UpZpEmfg5tdr9Q

猜你喜歡