ptmalloc、tcmalloc 與 jemalloc 對比分析

背景介紹

在開發中，爲了進行耗時優化，基礎庫這層按照慣例使用 tcmalloc 替代 glibc 標配的 ptmalloc 做優化，CPU 消耗和耗時確實有所降低。但在晚上高峯時期，在 CPU 剛剛超過 50% 之後卻出現了指數上升，服務在幾分鐘之內不可用。最終定位到是 tcmalloc 在內存分配的時候使用自旋鎖，在鎖衝突嚴重的時候導致 CPU 飆升。爲了弄清楚 tcmalloc 到底做了什麼，仔細瞭解各種內存管理庫迫在眉睫。

內存管理不外乎三個層面，用戶程序層，C 運行時庫層，內核層。allocator 正是值 C 運行時庫的內存管理模塊, 它響應用戶的分配請求, 向內核申請內存, 然後將其返回給用戶程序。爲了保持高效的分配, allocator 一般都會預先分配一塊大於用戶請求的內存, 並通過某種算法管理這塊內存. 來滿足用戶的內存分配要求, 用戶 free 掉的內存也並不是立即就返回給操作系統, 相反, allocator 會管理這些被 free 掉的空閒空間, 以應對用戶以後的內存分配要求. 也就是說, allocator 不但要管理已分配的內存塊, 還需要管理空閒的內存塊, 當響應用戶分配要求時, allocator 會首先在空閒空間中尋找一塊合適的內存給用戶, 在空閒空間中找不到的情況下才分配一塊新的內存。業界常見的庫包括：ptmalloc(glibc 標配)、tcmalloc(google)、jemalloc(facebook)

接下來我們將從兩個角度對這些庫進行分析：

系統向：看內存管理庫是如何管理空閒內存的
用戶向：看用戶程序如何向內存管理庫申請內存 (釋放大致相似，可以參考申請)

ptmalloc

GNU Libc 的內存分配器 (allocator)—ptmalloc，起源於 Doug Lea 的 malloc。由 Wolfram Gloger 改進得到可以支持多線程。

在 Doug Lea 實現的內存分配器中只有一個主分配區（main arena），每次分配內存都必須對主分配區加鎖，分配完成後釋放鎖，在 SMP 多線程環境下，對主分配區的鎖的爭用很激烈，嚴重影響了 malloc 的分配效率。ptmalloc 增加了動態分配區（dynamic arena），主分配區與動態分配區用環形鏈表進行管理。每一個分配區利用互斥鎖（mutex）使線程對於該分配區的訪問互斥。每個進程只有一個主分配區，但可能存在多個動態分配區，ptmalloc 根據系統對分配區的爭用情況動態增加動態分配區的數量，分配區的數量一旦增加，就不會再減少了。主分配區在二進制啓動時調用 sbrk 從 heap 區域分配內存，Heap 是由用戶內存塊組成的連續的內存域。而動態分配區每次使用 mmap()向操作系統 “批發”HEAP_MAX_SIZE 大小的虛擬內存，如果內存耗盡，則會申請新的內存鏈到動態分配區 heap data 的“strcut malloc_state”。如果用戶請求的大小超過 HEAP_MAX_SIZE，動態分配區則會直接調用 mmap() 分配內存，並且當 free 的時候調用 munmap()，該類型的內存塊不會鏈接到任何 heap data。用戶向請求分配內存時，內存分配器將緩存的內存切割成小塊 “零售” 出去。從用戶空間分配內存，減少系統調用，是提高內存分配速度的好方法，畢竟前者要高效的多。

系統向看 ptmalloc 內存管理

在「glibc malloc」中主要有 3 種數據結構：

malloc_state(Arena header)：一個 thread arena 可以維護多個堆，這些堆共享同一個 arena header。Arena header 描述的信息包括：bins、top chunk、last remainder chunk 等；
heap_info(Heap Header)：每個堆都有自己的堆 Header（注：也即頭部元數據）。當這個堆的空間耗盡時，新的堆（而非連續內存區域）就會被 mmap 當前堆的 aerna 裏；
malloc_chunk(Chunk header)：根據用戶請求，每個堆被分爲若干 chunk。每個 chunk 都有自己的 chunk header。內存管理使用 malloc_chunk，把 heap 當作 link list 從一個內存塊遊走到下一個塊。

struct malloc_state {
	mutex_t mutex;
	int flags;
	mfastbinptr fastbinsY[NFASTBINS];
	/* Base of the topmost chunk -- not otherwise kept in a bin */
	mchunkptr top;
	/* The remainder from the most recent split of a small request */
	mchunkptr last_remainder;
	/* Normal bins packed as described above */
	mchunkptr bins[NBINS * 2 - 2];
	unsigned int binmap[BINMAPSIZE];
	struct malloc_state *next;
	/* Memory allocated from the system in this arena. */
	INTERNAL_SIZE_T system_mem;
	INTERNAL_SIZE_T max_system_mem;
};

typedef struct _heap_info {
	mstate ar_ptr; /* Arena for this heap. */
	struct _heap_info *prev; /* Previous heap. */
	size_t size; /* Current size in bytes. */
	size_t mprotect_size; /* Size in bytes that has been mprotected
	PROT_READ|PROT_WRITE. */
	/* Make sure the following data is properly aligned, particularly
	that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
	MALLOC_ALIGNMENT. */
	char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

struct malloc_chunk {
	INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
	INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
	struct malloc_chunk* fd; /* double links -- used only if free. */
	struct malloc_chunk* bk;
	/* Only used for large blocks: pointer to next larger size. */
	struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
	struct malloc_chunk* bk_nextsize;
};

注意：Main arena 無需維護多個堆，因此也無需 heap_info。當空間耗盡時，與 thread arena 不同，main arena 可以通過 sbrk 拓展堆段，直至堆段「碰」到內存映射段；

用戶向看 ptmalloc 內存管理

當某一線程需要調用 malloc() 分配內存空間時，該線程先查看線程私有變量中是否已經存在一個分配區，如果存在，嘗試對該分配區加鎖，如果加鎖成功，使用該分配區分配內存，如果失敗，該線程搜索循環鏈表試圖獲得一個沒有加鎖的分配區。如果所有的分配區都已經加鎖，那麼 malloc() 會開闢一個新的分配區，把該分配區加入到全局分配區循環鏈表並加鎖，然後使用該分配區進行分配內存操作。在釋放操作中，線程同樣試圖獲得待釋放內存塊所在分配區的鎖，如果該分配區正在被別的線程使用，則需要等待直到其他線程釋放該分配區的互斥鎖之後纔可以進行釋放操作。

For 32 bit systems:
Number of arena = 2 * number of cores + 1.
For 64 bit systems:
Number of arena = 8 * number of cores + 1.

線程中內存管理

對於空閒的 chunk，ptmalloc 採用分箱式內存管理方式，每一個內存分配區中維護着 [bins] 的列表數據結構，用於保存 free chunks。根據空閒 chunk 的大小和處於的狀態將其放在四個不同的 bin 中，這四個空閒 chunk 的容器包括 fast bins，unsorted bin， small bins 和 large bins。

從工作原理來看：

Fast bins 是小內存塊的高速緩存，當一些大小小於 64 字節的 chunk 被回收時，首先會放入 fast bins 中，在分配小內存時，首先會查看 fast bins 中是否有合適的內存塊，如果存在，則直接返回 fast bins 中的內存塊，以加快分配速度。
Usorted bin 只有一個，回收的 chunk 塊必須先放到 unsorted bin 中，分配內存時會查看 unsorted bin 中是否有合適的 chunk，如果找到滿足條件的 chunk，則直接返回給用戶，否則將 unsorted bin 的所有 chunk 放入 small bins 或是 large bins 中。
Small bins 用於存放固定大小的 chunk，共 64 個 bin，最小的 chunk 大小爲 16 字節或 32 字節，每個 bin 的大小相差 8 字節或是 16 字節，當分配小內存塊時，採用精確匹配的方式從 small bins 中查找合適的 chunk。
Large bins 用於存儲大於等於 512B 或 1024B 的空閒 chunk，這些 chunk 使用雙向鏈表的形式按大小順序排序，分配內存時按最近匹配方式從 large bins 中分配 chunk。

從作用來看：

Fast bins 可以看着是 small bins 的一小部分 cache，主要是用於提高小內存的分配效率，雖然這可能會加劇內存碎片化，但也大大加速了內存釋放的速度！
Unsorted bin 可以重新使用最近 free 掉的 chunk，從而消除了尋找合適 bin 的時間開銷，進而加速了內存分配及釋放的效率。
Small bins 相鄰的 free chunk 將被合併，這減緩了內存碎片化，但是減慢了 free 的速度；
Large bin 中所有 chunk 大小不一定相同，各 chunk 大小遞減保存。最大的 chunk 保存頂端，而最小的 chunk 保存在尾端；查找較慢，且釋放時兩個相鄰的空閒 chunk 會被合併。其中 fastbins 保存在 malloc_state 結構的 fastbinsY 變量中，其他三者保存在 malloc_state 結構的 bins 變量中。

Chunk 說明

一個 arena 中最頂部的 chunk 被稱爲「top chunk」。它不屬於任何 bin 。當所有 bin 中都沒有合適空閒內存時，就會使用 top chunk 來響應用戶請求。當 top chunk 的大小比用戶請求的大小小的時候，top chunk 就通過 sbrk（main arena）或 mmap（ thread arena）系統調用擴容。

「last remainder chunk」即最後一次 small request 中因分割而得到的剩餘部分，它有利於改進引用局部性，也即後續對 small chunk 的 malloc 請求可能最終被分配得彼此靠近。當用戶請求 small chunk 而無法從 small bin 和 unsorted bin 得到服務時，分配器就會通過掃描 binmaps 找到最小非空 bin。正如前文所提及的，如果這樣的 bin 找到了，其中最合適的 chunk 就會分割爲兩部分：返回給用戶的 User chunk 、添加到 unsorted bin 中的 Remainder chunk。這一 Remainder chunk 就將成爲 last remainder chunk。當用戶的後續請求 small chunk，並且 last remainder chunk 是 unsorted bin 中唯一的 chunk，該 last remainder chunk 就將分割成兩部分：返回給用戶的 User chunk、添加到 unsorted bin 中的 Remainder chunk（也是 last remainder chunk）。因此後續的請求的 chunk 最終將被分配得彼此靠近。

問題

如果後分配的內存先釋放，無法及時歸還系統。因爲 ptmalloc 收縮內存是從 top chunk 開始, 如果與 top chunk 相鄰的 chunk 不能釋放, top chunk 以下的 chunk 都無法釋放。
內存不能在線程間移動，多線程使用內存不均衡將導致內存浪費
每個 chunk 至少 8 字節的開銷很大
不定期分配長生命週期的內存容易造成內存碎片，不利於回收。
加鎖耗時，無論當前分區有無耗時，在內存分配和釋放時，會首先加鎖。

從上述來看 ptmalloc 的主要問題其實是內存浪費、內存碎片、以及加鎖導致的性能問題。

備註：glibc 2.26(2017-08-02) 中已經添加了 tcache(thread local cache) 優化 malloc 速度

tcmalloc

tcmalloc 是 Google 開發的內存分配器，在 Golang、Chrome 中都有使用該分配器進行內存分配。有效的優化了 ptmalloc 中存在的問題。當然爲此也付出了一些代價，按下不表，先看 tcmalloc 的具體實現。

系統向看 tcmalloc 內存管理

tcmalloc 把 8kb 的連續內存稱爲一個頁 (Page)，可以用下面兩個常量來描述：

const size_t kPageShift = 13;
const size_t kPageSize = 1 << kPageShift;

對於一個指針 p，p>>kPageShift 即是 p 的頁地址。同樣的對於一個頁地址 x，管理的實際內存區間是 [x <<kPageShift, (x+1)<<kPageShift)。一個或多個連續的頁組成一個 Span. 對於一個 Span，管理的實際內存區間是 [start<<kPageShift, (start+length)<<kPageShift)。tcmalloc 中所有頁級別的操作，都是對 Span 的操作。PageHeap 是一個全局的用來管理 Span 的類。PageHeap 把小於的空閒 Span 保存在雙向循環鏈表上，而大的 span 則保存在 SET 中。保證了所有的內存的申請速度，減少了內存查找。

// Information kept for a span (a contiguous run of pages).
struct Span {
  PageID        start;          // Starting page number
  Length        length;         // Number of pages in span
  Span*         next;           // Used when in link list
  Span*         prev;           // Used when in link list
  union {
    void* objects;              // Linked list of free objects

    // Span may contain iterator pointing back at SpanSet entry of
    // this span into set of large spans. It is used to quickly delete
    // spans from those sets. span_iter_space is space for such
    // iterator which lifetime is controlled explicitly.
    char span_iter_space[sizeof(SpanSet::iterator)];
  };
  unsigned int  refcount : 16;  // Number of non-free objects
  unsigned int  sizeclass : 8;  // Size-class for small objects (or 0)
  unsigned int  location : 2;   // Is the span on a freelist, and if so, which?
  unsigned int  sample : 1;     // Sampled object?
  bool          has_span_iter : 1; // If span_iter_space has valid
                                   // iterator. Only for debug builds.
  // What freelist the span is on: IN_USE if on none, or normal or returned
  enum { IN_USE, ON_NORMAL_FREELIST, ON_RETURNED_FREELIST };
};

// We segregate spans of a given size into two circular linked
// lists: one for normal spans, and one for spans whose memory
// has been returned to the system.
struct SpanList {
Span        normal;
Span        returned;
};

// Array mapping from span length to a doubly linked list of free spans
//
// NOTE: index 'i' stores spans of length 'i + 1'.
SpanList free_[kMaxPages];

// Sets of spans with length > kMaxPages.
//
// Rather than using a linked list, we use sets here for efficient
// best-fit search.
SpanSet large_normal_;
SpanSet large_returned_;

用戶向看 tcmalloc 內存管理

TCMalloc 是專門對多線併發的內存管理而設計的，TCMalloc 主要是在線程級實現了緩存，使得用戶在申請內存時大多情況下是無鎖內存分配。整個 TCMalloc 實現了三級緩存，分別是 ThreadCache(線程級緩存)，Central Cache(中央緩存：CentralFreeeList)，PageHeap(頁緩存)，最後兩級需要加鎖訪問。如圖爲內存分配

每個線程都一個線程局部的 ThreadCache，ThreadCache 中包含一個鏈表數組 FreeList list_[kNumClasses]，維護了不同規格的空閒內存的鏈表；當申請內存的時候可以直接根據大小尋找恰當的規則的內存。如果 ThreadCache 的對象不夠了，就從 CentralCache 進行批量分配；如果 CentralCache 依然沒有，就從 PageHeap 申請 Span；PageHeap 首先在 free[n,128]中查找、然後到 large set 中查找，目標就是找到一個最小的滿足要求的空閒 Span，優先使用 normal 類鏈表中的 Span。如果找到了一個 Span，則嘗試分裂 (Carve) 這個 Span 並分配出去；如果所有的鏈表中都沒找到 length>=n 的 Span，則只能從操作系統申請了。Tcmalloc 一次最少向系統申請 1MB 的內存，默認情況下，使用 sbrk 申請，在 sbrk 失敗的時候，使用 mmap 申請。

當我們申請的內存大於 kMaxSize(256k) 的時候，內存大小超過了 ThreadCache 和 CenterCache 的最大規格，所以會直接從全局的 PageHeap 中申請最小的 Span 分配出去 (return span->start << kPageShift))

tcmalloc 的優勢

小內存可以在 ThreadCache 中不加鎖分配 (加鎖的代價大約 100ns)
大內存可以直接按照大小分配不需要再像 ptmalloc 一樣進行查找
大內存加鎖使用更高效的自旋鎖
減少了內存碎片然而，tcmalloc 也帶來了一些問題，使用自旋鎖雖然減少了加鎖效率，但是如果使用大內存較多的情況下，內存在 Central Cache 或者 Page Heap 加鎖分配。而 tcmalloc 對大小內存的分配過於保守，在一些內存需求較大的服務（如推薦系統），小內存上限過低，當請求量上來，鎖衝突嚴重，CPU 使用率將指數暴增。

jemalloc

jemalloc 最初由 Jason Evans 開發，用於 FreeBSD 的 libc 庫，後續在 firefox、facebook 服務器、android 5.0 等服務中大量使用。jemalloc 最大的優勢還是其強大的多核 / 多線程分配能力. 以現代計算機硬件架構來說, 最大的瓶頸已經不再是內存容量或 cpu 速度, 而是多核 / 多線程下的 lock contention(鎖競爭). 因爲無論 CPU 核心數量如何多, 通常情況下內存只有一份. 可以說, 如果內存足夠大, CPU 的核心數量越多, 程序線程數越多, jemalloc 的分配速度越快。

系統向看 jemalloc 內存管理

對於一個多線程 + 多 CPU 核心的運行環境, 傳統分配器中大量開銷被浪費在 lock contention 和 false sharing 上, 隨着線程數量和核心數量增多, 這種分配壓力將越來越大. 針對多線程, 一種解決方法是將一把 global lock 分散成很多與線程相關的 lock. 而針對多核心, 則要儘量把不同線程下分配的內存隔離開, 避免不同線程使用同一個 cache-line 的情況. 按照上面的思路, 一個較好的實現方式就是引入 arena. 將內存劃分成若干數量的 arenas, 線程最終會與某一個 arena 綁定. 由於兩個 arena 在地址空間上幾乎不存在任何聯繫, 就可以在無鎖的狀態下完成分配. 同樣由於空間不連續, 落到同一個 cache-line 中的幾率也很小, 保證了各自獨立。由於 arena 的數量有限, 因此不能保證所有線程都能獨佔 arena, 分享同一個 arena 的所有線程, 由該 arena 內部的 lock 保持同步.

chunk 是僅次於 arena 的次級內存結構，arena 都有專屬的 chunks, 每個 chunk 的頭部都記錄了 chunk 的分配信息。chunk 是具體進行內存分配的區域，目前的默認大小是 4M。chunk 以 page（默認爲 4K) 爲單位進行管理，每個 chunk 的前幾個 page（默認是 6 個）用於存儲 chunk 的元數據，後面跟着一個或多個 page 的 runs。後面的 runs 可以是未分配區域，多個小對象組合在一起組成 run, 其元數據放在 run 的頭部。大對象構成的 run, 其元數據放在 chunk 的頭部。在使用某一個 chunk 的時候，會把它分割成很多個 run，並記錄到 bin 中。不同 size 的 class 對應着不同的 bin，在 bin 裏，都會有一個紅黑樹來維護空閒的 run，並且在 run 裏，使用了 bitmap 來記錄了分配狀態。此外，每個 arena 裏面維護一組按地址排列的可獲得的 run 的紅黑樹。

struct arena_s {
    ...
    /* 當前arena管理的dirty chunks */
    arena_chunk_tree_t  chunks_dirty;
    /* arena緩存的最近釋放的chunk, 每個arena一個spare chunk */
    arena_chunk_t       *spare;
    /* 當前arena中正在使用的page數. */
    size_t          nactive;
    /*當前arana中未使用的dirty page數*/
    size_t          ndirty;
    /* 需要清理的page的大概數目 */
    size_t          npurgatory;
 
 
    /* 當前arena可獲得的runs構成的紅黑樹， */
    /* 紅黑樹按大小/地址順序進行排列。分配run時採用first-best-fit策略*/
    arena_avail_tree_t  runs_avail;
    /* bins儲存不同大小size的內存區域 */
    arena_bin_t     bins[NBINS];
};
/* Arena chunk header. */
struct arena_chunk_s {
    /* 管理當前chunk的Arena */
    arena_t         *arena;
    /* 鏈接到所屬arena的dirty chunks樹的節點*/
    rb_node(arena_chunk_t)  dirty_link;
    /* 髒頁數 */
    size_t          ndirty;
    /* 空閒run數 Number of available runs. */
    size_t          nruns_avail;
    /* 相鄰的run數，清理的時候可以合併的run */
    size_t          nruns_adjac;
    /* 用來跟蹤chunk使用狀況的關於page的map, 它的下標對應於run在chunk中的位置，通過加map_bias不跟蹤chunk 頭部的信息
     * 通過加map_bias不跟蹤chunk 頭部的信息
     */
    arena_chunk_map_t   map[1]; /* Dynamically sized. */
};
struct arena_run_s {
    /* 所屬的bin */
    arena_bin_t *bin;
    /*下一塊可分配區域的索引 */
    uint32_t    nextind;
    /* 當前run中空閒塊數目. */
    unsigned    nfree;
};

用戶向看 jemalloc 內存管理

jemalloc 按照內存分配請求的尺寸，分了 small object (例如 1 – 57344B)、 large object (例如 57345 – 4MB )、 huge object (例如 4MB 以上)。jemalloc 同樣有一層線程緩存的內存名字叫 tcache，當分配的內存大小小於 tcache_maxclass 時，jemalloc 會首先在 tcache 的 small object 以及 large object 中查找分配，tcache 不中則從 arena 中申請 run，並將剩餘的區域緩存到 tcache。若 arena 找不到合適大小的內存塊，則向系統申請內存。當申請大小大於 tcache_maxclass 且大小小於 huge 大小的內存塊時，則直接從 arena 開始分配。而 huge object 的內存不歸 arena 管理，直接採用 mmap 從 system memory 中申請，並由一棵與 arena 獨立的紅黑樹進行管理。

jemalloc 的優勢

多線程下加鎖大大減少

總結

總的來看，作爲基礎庫的 ptmalloc 是最爲穩定的內存管理器，無論在什麼環境下都能適應，但是分配效率相對較低。而 tcmalloc 針對多核情況有所優化，性能有所提高，但是內存佔用稍高，大內存分配容易出現 CPU 飆升。jemalloc 的內存佔用更高，但是在多核多線程下的表現也最爲優異。

看一看後臺系統遇到的問題最終通過鏈接 jemalloc 得到了解決，內存管理庫的短板和優勢其實也給我們帶來了一些思考點，在什麼情況下我們應該考慮好內存分配如何管理：

多核多線程的情況下，內存管理需要考慮內存分配加鎖、異步內存釋放、多線程之間的內存共享、線程的生命週期內存當作磁盤使用的情況下，需要考慮內存分配和釋放的效率，是使用內存管理庫還是應該自己進行大對象大內存的管理。（在搜索以及推薦系統中尤爲突出）

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

猜你喜歡