TCMalloc 技術(shù)細節(jié)詳解
TCMalloc 是 Google 開發(fā)的 gperftools 中的一款內(nèi)存分配工具，在 Golang 等諸多知名項目中均有使用。今天我們一起走近技術(shù)細節(jié)，解密它的高效內(nèi)核。
一、總體架構(gòu)
TCMalloc?按照內(nèi)存大小區(qū)間劃分為小/中/大三類，由不同的數(shù)據(jù)結(jié)構(gòu)進行管理。
通過 SizeMap，還可以對小內(nèi)存繼續(xù)細分。SizeMap 將用戶申請的不超過 256K 的內(nèi)存大小映射到 85 種對齊的大小類型（size class），最小 8 字節(jié)，最大 256K，并記錄了大小類型到 num_objects_to_move、class_to_pages 的映射關(guān)系。（這兩個整型數(shù)值的意義詳見后文）
大塊連續(xù)的內(nèi)存按照 Page (8K) 為最小單位進行追蹤，一個或多個連續(xù)的 Page 構(gòu)成一個 Span。Page ID 與 Span 的映射關(guān)系由 Page Map（通過 radix-tree 實現(xiàn)，如下圖）進行維護。
一個 Span 可能作為一塊連續(xù)的中/大內(nèi)存直接分配給用戶使用，也可能分裂成小內(nèi)存塊（object）放到 Central Cache 或者 Thread Cache 中，再分配給用戶。Span 結(jié)構(gòu)體記錄一個 Span 的詳細信息，它包括：
start 和 length：記錄 Span 包含的 Page 范圍
prev 和 next ：Span 類型的指針，用于將 Span 連接成 Spanlist
objects ：記錄 Span 分裂成的小內(nèi)存塊的鏈表
span_iter_space：記錄 Span 在 SpanSet（Page Heap中的Span集合）中的迭代器，方便 Span 從 SpanSet 中移除
sizeclass 表示 Span 分裂成的小內(nèi)存塊的大小類型（0 表示沒有分裂成小內(nèi)存）
refcount 表示 Span 分裂成的小內(nèi)存塊的引用計數(shù)，即分配給 Thread Cache 使用的 object 數(shù)量
location 枚舉變量記錄 Span 所在的位置（pageID 相鄰且 location 相同的空閑 Span 可以合并成更大的 Span）
TCMalloc的總體架構(gòu)以及申請釋放內(nèi)存的流程如下圖所示，其中 System Allocator 使用的是 mmap 和 sbrk：
二、Central Cache 與 Thread Cache
小內(nèi)存（Size≤256 K）通過 Thread Cache 和 Central Cache 分配，每個線程都有一個 Thread Cache，所有線程共享一個 Central Cache。
它們都由 85 條固定大小類型（最小 8 字節(jié)，最大 256K）的 freelist 構(gòu)成。freelist?包含相同大小類型的 object 構(gòu)成的鏈表，并使用嵌入式指針連接以提高內(nèi)存利用率。
分配小內(nèi)存的流程如下：
通過 Size Map 將其大小映射到相應的大小類型
在 Thread Cache 中查找該大小類型對應的 freelist
如果 freelist 不為空，我們從列表中刪除第一個 object 并返回它。由于線程內(nèi)不存在內(nèi)存的并發(fā)申請，這個過程無需獲得任何鎖
如果 Thread Cache 的 freelist 為空：
我們從 Central Cache 中該大小類型的 freelist 即 Central freelist 上獲取一堆 object（由于 Central Cache 由所有 Thread 持鎖并發(fā)訪問，內(nèi)存在 Thread Cache 和 Central Cache 之間傳遞時，每次傳遞 num_objects_to_move個object，以提高內(nèi)存?zhèn)鬟f的效率）
將它們放在 Thread Cache 的?freelist?中
將新獲取的 object 之一返回給申請者
如果 Central freelist 也是空的：
我們以 Page 為單位從 Page Heap 分配一系列連續(xù) Page（即一個 Span），具體的 Page 數(shù)是從 SizeMap 獲取的該大小類型的 class_to_pages 值
將這些 Page 拆分為該大小類型的一組 object
將新的 object 放在 Central freelist 中
和以前一樣，將其中一些 object 移到 Thread Cache 的?freelist?中
上述的流程在實現(xiàn)上有很多重要的細節(jié)：
每條 Central freelist 通過 empty 和 nonempty 兩條鏈表記錄從 Page Heap 獲取的 Span，empty 表示 Span 全部傳遞給了 Thread Cache。Span 先分裂成該大小類型的 objects 并掛在 nonempty 上，refcount 初始值為 0，當 object 傳遞給 Thread Cache 時 refcount 增加。
為了方便地在 Thread Cache 和 Central Cache 之間進行 num_objects_to_move 個內(nèi)存塊的傳遞，每條 Central freelist 上都有一個定長 64 的插槽數(shù)組 tc_slots_，存用于放從 Thread cache 回收的 objects，數(shù)組元素為 TCEntry，每個 entry 記錄 num_objects_to_move 個 object 的頭尾指針，即一次移動的 objects 放在一個插槽里。
通過 max_cache_size=min(64, 1M/(num_objects_to_move*size_bytes))，每條?Central?freelist 就能把 tc_slots_ 總大小限制在 1M 以內(nèi)，插槽數(shù)不超過 64 個且有一個初始的 cache_size（≤max_cache_size）。
Central freelist 收到 thread cache 交還的 objects 后，如果 Central Cache 還有空間，即 freelist 還有插槽可用（即 used<cache_size），或者能讓隨機一條其他 size class ?的 Central freelist 的 cache_size 減少，使得本條 freelist 的cache_size 增加且不超過 max_cache_size（只需要隨機到的這條 Central freelist 的 cache_size>0 就能滿足）。
把這些 objects 插入空閑的插槽；否則把 objects 逐一釋放給對應的 Span，Span 的 refcount 也相應地減少，當 refcount 為 0 時，說明整個 Span 都是空閑的，將其釋放回 Page Heap 中。
Thread Cache 向 Central Cache 申請內(nèi)存時，會優(yōu)先從插槽數(shù)組 tc_slots_ 獲取，如果 tc_slots_ 為空，再從 nonempty 鏈表上的 Span 中獲取。
另外，為了使線程可以快速獲取 Thread Cache，Thread Cache 的指針被保存在了?__thread 修飾的靜態(tài)變量 threadlocal_data_ 中。該修飾符表示對于每一個線程，都有一個線程本地的靜態(tài)變量，線程之間互不干擾。
為了自動銷毀 Thread Cache，使用 pthread 的 pthread_key_create 接口注冊 DestroyThreadCache 方法，該方法將在線程結(jié)束時執(zhí)行以銷毀 Thread Cache。
三、Page Heap
超過 256K 的內(nèi)存以及 Central Cache 以 page 為單位申請的內(nèi)存都由 Page Heap 分配。
Page Heap 有 128 對 SpanList，分別放置內(nèi)存大小 1 page 到 128 page 的 Span。超過 128 page 的 Span 則放在一對 SpanSet（使用 std::set，底層是用紅黑樹實現(xiàn)的）中管理。
當申請 K 個 page 的內(nèi)存時，從第 K 對 SpanList 開始搜索，如果該對 SpanList 為空，查看下一對 SpanList，以此類推。
如果找到長度 ≥K 的 Span，則切出長度為 K 的 Span 返回，剩余部分被重新插入合適的 SpanList 中。如果沒有 SpanList 可以滿足分配，則通過 std::set 提供的 upper_bound 接口，從 SpanSet 中找到大于等于 K 個 page 的最小 Span，同樣切割后進行返回，剩余部分根據(jù)大小插入 SpanSet 或合適的 SpanList。
如果沒有找到滿足需求的 Span，將通過 System Allocator 從系統(tǒng)獲取內(nèi)存后重復上述搜索過程。從 System Allocator 獲取內(nèi)存時，如果實際需要的內(nèi)存不滿 1M，先嘗試申請 1M 內(nèi)存；如果申請失敗，再嘗試申請實際需要的內(nèi)存大小。
在上述流程的實現(xiàn)中，我們依然找到了一些有意思的細節(jié)：
一對 SpanList，包含 normal 和 returned 兩條鏈表，搜索時先查找 normal，如果 normal 為空，再查找 returned。從 System Allocator 獲取的或從 Central Cache 歸還的空閑 Span 掛在 normal 上，從 normal 上釋放給操作系統(tǒng)的 Span 掛在 returned 上。
這里使用了一個特殊的技巧來提高 Page Heap 的效率：returned 上的 Span 并沒有真的被釋放，只是使用 MADV_FREE 標記了這塊內(nèi)存，內(nèi)核會等到內(nèi)存緊張時才真正將其釋放。在真正釋放之前，這塊內(nèi)存依然可以隨時復用。SpanSet 同理。
釋放給 Page Heap 的 Span 會盡可能合并：Span 結(jié)構(gòu)體中記錄了 Span 的 Page 范圍以及它的 location（位于 normal 還是 returned 鏈表中）。當一個 Span 被釋放回 Page Heap ?時，假設(shè) Page 范圍是 [p, q]，我們查找 Page p-1 和 q+1 所在的 Span。
如果有相鄰且 location 相同的空閑 Span，就將它（們）與 Span[p, q] 合并。合并成的 Span 根據(jù)大小被插入到合適的 SpanList 中或 SpanSet 中。這樣的處理對減少內(nèi)存碎片頗有幫助。
