天天看點
傳回

TCMalloc(Thread-Caching malloc) 基本設計原理

文章目錄

  • ​​背景​​
  • ​​如何使用​​
  • ​​架構概覽​​
  • ​​1. TCMalloc Front-end​​
  • ​​1.1 小對象和大對象的記憶體配置設定過程​​
  • ​​1.2 記憶體釋放過程​​
  • ​​1.3 Per-CPU mode​​
  • ​​1.4 Per-thread mode​​
  • ​​1.5 per-cpu 和 per-thread 運作時記憶體管理算法對比​​
  • ​​2. TCMalloc Middle-end​​
  • ​​2.1 Transfer Cache​​
  • ​​2.2 Central Free List​​
  • ​​2.3 Pagemap 和 Spans​​
  • ​​3. TCMalloc Backend​​
  • ​​3.1 Legacy Pageheap​​
  • ​​3.2 大頁場景配置設定器設計​​
  • ​​4. 參考​​

背景

之前介紹了TCMalloc, Jemalloc, Glibc-malloc 的性能 以及 TCMalloc和Glibc Malloc 的大體架構和主要優勢：​​三種 Allocator 性能 以及 glibc/tcmalloc 設計差異​​。

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

主要的幾個特性如下：

  1. 高性能。大多數對象的配置設定和釋放都不需要産生太多的競争，因為tcmalloc 維護了thread-cache 來提供目前線程的記憶體配置設定需求。是以，應用大多數的記憶體申請需求不會有鎖的競争，而且在多核場景有較好的擴充性。
  2. 靈活的使用記憶體資源。使用者不使用的記憶體，tcmalloc會選擇服複用或者歸還作業系統。
  3. 降低了每個請求的記憶體開銷。通過配置設定相同大小的page 降低記憶體使用的開銷，這在小對象場景較為有效。
  4. 内部資訊統計開銷較低。能夠開啟細粒度的應用記憶體占用資訊，來幫助使用者展示tcmalloc内部記憶體使用的細節。

如何使用

安裝tcmalloc，應用編譯加入 ​

​-ltcmalloc​

​即可預設将glibc的malloc 替換為tcmalloc的malloc ，之前的文章中關于性能的對比測試中能夠直接看到。

架構概覽

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

TCMalloc(Thread-Caching malloc) 基本設計原理
  • ​

    ​Front-end​

     ​，主要維護線程cache，用來為應用提供 快速配置設定以及釋放記憶體的需求。
  • ​

    ​Middle-end​

     ​，主要負責為font-end 中的thread-cache 填充記憶體。
  • ​

    ​back-end​

     ​，負責從os直接擷取記憶體。

需要注意的是​

​front-end 的 thread-cache 可以在每一個cpu下維護 或者 每一個線程下維護，​

​back-end` 則能夠支援大記憶體的pageheap管理，也能支援小記憶體的pageheap 管理。

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

1. 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 的演進過程中有兩種類型的實作：

  1. 最開始的時候隻支援 per-thread 的cache 模式，這也是TCMalloc 名字 Thread-Cacheing malloc的由來。然而這種場景會随着使用者線程的大量增加，出現了一些記憶體問題：每個線程隻能有極小的thread-cache，需要消耗較多的CPU資源來聚合每個線程的記憶體資源。
  2. 較新版本的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’ ，用來處理運作在目前核的線程的記憶體申請/釋放需求。

大體形态如下：

TCMalloc(Thread-Caching malloc) 基本設計原理

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 個單連結清單），類似如下圖：

TCMalloc(Thread-Caching malloc) 基本設計原理

配置設定某一個對應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 擷取記憶體 以及 釋放記憶體交替，則需增加容量限制，有更多的空間來緩存這一些記憶體對象。降低容量限制的前提是發現有一些空閑容量長時間沒有被使用。

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

2. 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。

TCMalloc(Thread-Caching malloc) 基本設計原理

Span 這個資料結構 在 middle-end中用來 管理回收的記憶體對象；在back-end 用來管理 對應大小的pages，負責給central-list 提供對應大小的span。

3. TCMalloc Backend

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

  • 管理未使用的大塊記憶體區域
  • 負責從 os 中擷取記憶體，來滿足其他元件的記憶體需求
  • 負責将其他元件不需要傳回的記憶體，還給os

還有兩個後端元件：

  1. legacy pageheap. 管理tcmalloc 的pages
  2. 管理大頁記憶體的 pageheap。用來提升應用程式大頁記憶體的申請需求，降低TLB的miss。

3.1 Legacy Pageheap

legacy pageheap 是一個數組的freelist，統一管理可用記憶體頁。數組的每一個節點是一個free list，也就是單連結清單。一般這個數組的大小 k < 256，對于第k 個數組元素來說，它的連結清單中的每一個節點都管理了 k 個pages。

TCMalloc(Thread-Caching malloc) 基本設計原理

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

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

3.2 大頁場景配置設定器設計

針對hugepage 的配置設定器設計 是希望其能夠有效持有 hugepage 大小的記憶體塊，需要的時候能夠快速配置設定，不需要的時候也能在合理的記憶體占用情況下釋放給作業系統。

  1. filler cache。能夠持有hugepage ，并提供一些大頁記憶體的申請需求。類似于legacy pageheap，通過一些free lists 管理pages 那樣管理huge page，主要用于處理小于hugepage 大小的記憶體申請。
  2. region cache。用于大于hugepage 大小的記憶體申請，這個cache 允許配置設定多個連續的hugepage。
  3. hugepage cache。和region cache的功能有點重複，也是用于配置設定大于hugepage 的記憶體申請。

4. 參考

資料結構 資料庫 Linux 記憶體配置設定 緩存
上一篇: 磁盤I:O 性能名額 以及 如何通過 fio 對nvme ssd,optane ssd, pmem 性能摸底
下一篇: 免688申請蘋果開發者證書，開發自己得蘋果應用

繼續閱讀