Jemalloc最初是Jason Evans為FreeBSD開發的新一代記憶體分配器, 用來替代原來的 phkmalloc, 最早投入使用是在2005年. 到目前為止, 除了原版Je, 還有很多變種 被用在各種項目里. Google在android5.0里將bionic中的預設分配器從Dl替換為Je,...
INSIDE OF JEMALLOC
The Algorithm and Implementation of Jemalloc
author: vector03
mail: [email protected]
--[ Table of contents
1 - 簡介 2 - Basic structures 2.1 - Overview 2.2 - Arena (arena_t) 2.2.1 - CPU Cache-Line 2.2.2 - Arena原理 2.2.3 - choose_arena 2.2.4 - Arena結構 2.3 - Chunk (arena_chunk_t) 2.3.1 - overview 2.3.2 - chunk結構 2.3.3 - chunk map (arena_chunk_map_t) 2.4 - Run (arena_run_t) 2.4.1 - run結構 2.4.2 - size class 2.4.3 - size2bin/bin2size 2.5 - Bins (arena_bin_t) 2.6 - Thread caches (tcache_t) 2.7 - Extent Node (extent_node_t) 2.8 - Base 3 - Allocation 3.1 - Overview 3.2 - Initialize 3.3 - small allocation (Arena) 3.3.1 - arena_run_reg_alloc 3.3.2 - arena_bin_malloc_hard 3.3.3 - arena_bin_nonfull_run_get 3.3.4 - small run alloc 3.3.5 - chunk alloc 3.4 - small allocation (tcache) 3.5 - large allocation 3.6 - huge allocation 4 - Deallocation 4.1 - Overview 4.2 - arena_dalloc_bin 4.3 - small run dalloc 4.4 - arena purge 4.5 - arena chunk dalloc 4.6 - large/huge dalloc 5 - 總結: 與Dl的對比 附: 快速調試Jemalloc
--[ 1 - 簡介
Jemalloc最初是Jason Evans為FreeBSD開發的新一代記憶體分配器, 用來替代原來的
phkmalloc, 最早投入使用是在2005年. 到目前為止, 除了原版Je, 還有很多變種
被用在各種項目里. Google在android5.0里將bionic中的預設分配器從Dl替換為Je,
也是看中了其強大的多核多線程分配能力.
同經典分配器, 如Dlmalloc相比, Je在基本思路和實現上存在明顯的差別. 比如,
Dl在分配策略上傾向於先dss後mmap的方式, 為的是快速向前分配, 但Je則完全相反.
而實現上也放棄了經典的boundary tag. 這些設計犧牲了局部分配速度和回收效率,
但在更大的空間和時間範圍內卻獲得更好的分配效果.
更重要的是, 相對經典分配器, Je最大的優勢還是其強大的多核/多線程分配能力.
以現代電腦硬體架構來說, 最大的瓶頸已經不再是記憶體容量或cpu速度, 而是
多核/多線程下的lock contention. 因為無論核心數量如何多, 通常情況下記憶體
只有一份. 可以說, 如果記憶體足夠大, CPU的核心數量越多, 程式線程數越多,
Je的分配速度越快. 而這一點是經典分配器所無法達到的.
這篇文章基於android5.x中的Jemalloc3.6.0. 最新的版本為4.x, 獲取最新代碼請至,
https://github.com/jemalloc/jemalloc/releases
--[ 2 - Basic structures
相對於Dl, Je引入了更多更複雜的分配結構, 如arena, chunk, bin, run, region,
tcache等等. 其中有些類似Dl, 但更多的具有不同含義, 本節將對它們做一一介紹.
----[ 2.1 - Overview
首先, 先給出一個整體的概念. Je對記憶體劃分按照如下由高到低的順序,
1. 記憶體是由一定數量的arenas進行管理.
2. 一個arena被分割成若幹chunks, 後者主要負責記錄bookkeeping.
3. chunk內部又包含著若幹runs, 作為分配小塊記憶體的基本單元.
4. run由pages組成, 最終被劃分成一定數量的regions,
5. 對於small size的分配請求來說, 這些region就相當於user memory.
Arena #0 +----------------------------------------------------------------------------+ | | | Chunk #0 Chunk #1 | | +---------------------------------+ +---------------------------------+ | | | | | | | | | Run #0 Run #1 | | Run #0 Run #1 | | | | +-------------+ +-------------+ | | +-------------+ +-------------+ | | | | | | | | | | | | | | | | | | | Page | | Page | | | | Page | | Page | | | | | | +---------+ | | +---------+ | | | | +---------+ | | +---------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Regions | | | | Regions | | | | | | Regions | | | | Regions | | | | | | | |[] [] [] | | | |[] [] [] | | | | | |[] [] [] | | | |[] [] [] | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +---------+ | | +---------+ | | | | +---------+ | | +---------+ | | | | | | | | | | | | | | | | | | | | Page | | Page | | | | Page | | Page | | | | | | +---------+ | | +---------+ | | | | +---------+ | | +---------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ... | | | | ... | | | | | | ... | | | | ... | | | | | | | +---------+ | | +---------+ | | | | +---------+ | | +---------+ | | | | | +-------------+ +-------------+ | | +-------------+ +-------------+ | | | +---------------------------------+ +---------------------------------+ | +----------------------------------------------------------------------------+
----[ 2.2 - Arena (arena_t)
如前所述, Arena是Je中最大或者說最頂層的基礎結構. 這個概念其實上是針對"對稱
多處理機(SMP)"產生的. 在SMP中, 導致性能劣化的一個重要原因在於"false sharing"
導致cache-line失效.
為瞭解決cache-line共用問題, 同時保證更少的內部碎片(internal fragmentation),
Je使用了arena.
------[ 2.2.1 - CPU Cache-Line
現代處理器為瞭解決記憶體匯流排吞吐量的瓶頸使用了內部cache技術. 儘管cache的
工作機制很複雜, 且對外透明, 但在編程上, 還是有必要瞭解cache的基本性質.
Cache是嵌入到cpu內部的一組SRAM, 速度是主存的N倍, 但造價較高, 因此
一般容量很小. 有些cpu設計了容量逐級逐漸增大的多級cache, 但速度逐級遞減.
多級處理更複雜, 但原理類似, 為了簡化, 僅討論L1 data cache.
cache同主存進行數據交換有一個最小粒度, 稱為cache-line, 通常這個值為64. 例如
在一個ILP32的機器上, 一次cache交換可以讀寫連續16個int型數據. 因此當訪問數組
#0元素時, 後面15個元素也被同時"免費"讀到了cache中, 這對於數組的連續訪問是
非常有利的.
然而這種免費載入不總是會帶來好處, 有時候甚至起到反效果, 所謂"false sharing".
試想兩個線程A和B分別執行在不同的cpu核心中並分別操作各自上下文中的變數x和y.
如果因為某種原因(比如x, y可能位於同一個class內部, 或者分別是數組中的兩個相鄰
元素), 兩者位於相同的cache-line中, 則在兩個core的L1 cache里都存在x和y的副本.
倘若線程A修改了x的值, 就會導致在B中的x與A中看到的不一致. 儘管這個變數x對B可能
毫無用處, 但cpu為了保證前後的正確和一致性, 只能判定core #1的cache失效. 因此
core #0必須將cache-line回寫到主存, 然後core #1再重新載入cache-line, 反之亦然.
如果恰好兩個線程交替操作同一cache-line中的數據, 將對cache將造成極大的損害,
導致嚴重的性能退化.
+-----------------------+ +-----------------------+ | core #0 | | core #1 | | | | | | +----------+ | | +----------+ | | | ThreadA | | | | ThreadB | | | +----------+ | | +----------+ | | | | | | | | +---+ | | | | | | | | | | | v D-cache | | v D-cache | | +-----------------+ | | +-----------------+ | | | x'| y | ... ... | <---+ +---> | x | y'| ... ... | | | |-----------------| | | | | |-----------------| | | | ... ... | | | | | | ... ... | | | | ... ... | | | | | | ... ... | | | | ... ... | | | | | | ... ... | | | +-----------------+ | | | | +-----------------+ | +-----------------------+ | | +-----------------------+ | | +------+ | | | v v memory +----------------------------- | ... | x | y | ... ... +-----------------------------
說到底, 從程式的角度看, 變數是獨立的地址單元, 但在CPU看來則是以cache-line為
整體的單元. 單獨的變數競爭可以在代碼中增加同步來解決, 而cache-line的競爭是
透明的, 不可控的, 只能被動由CPU仲裁. 這種觀察角度和處理方式的區別, 正是false
sharing的根源.
------[ 2.2.2 - Arena原理
回到memory allocator的話題上. 對於一個多線程+多CPU核心的運行環境, 傳統
分配器中大量開銷被浪費在lock contention和false sharing上, 隨著線程數量
和核心數量增多, 這種分配壓力將越來越大.
針對多線程, 一種解決方法是將一把global lock分散成很多與線程相關的lock.
而針對多核心, 則要儘量把不同線程下分配的記憶體隔離開, 避免不同線程使用同
一個cache-line的情況. 按照上面的思路, 一個較好的實現方式就是引入arena.
+---------+ +---------+ +---------+ +---------+ +---------+
| threadA | | threadB | | threadC | | threadD | | threadE |
+---------+ +---------+ +---------+ +---------+ +---------+
| | | | |
| +---------------|---------------|---------+ |
+------------------+ +-------+ +------+ | |
+-----------------|----|----------------|----------------|-----+
| | | | |
v v v v v
+----------+ +----------+ +----------+ +----------+
| | | | | | | |
| Arena #0 | | Arena #1 | | Arena #2 | | Arena #3 |
| | | | | | | |
+----------+ +----------+ +----------+ +----------+
Je將記憶體劃分成若幹數量的arenas, 線程最終會與某一個arena綁定. 比如上圖中的
threadA和B就分別綁定到arena #1和#3上. 由於兩個arena在地址空間上幾乎不存在任何
聯繫, 就可以在無鎖的狀態下完成分配. 同樣由於空間不連續, 落到同一個cache-line
中的幾率也很小, 保證了各自獨立.
由於arena的數量有限, 因此不能保證所有線程都能獨占arena, 比如, 圖中threadA和C
就都綁定到了arena1上. 分享同一個arena的所有線程, 由該arena內部的lock保持同步.
Je將arena保存到一個數組中, 該數組全局記錄了所有arenas,
arena_t **arenas;
事實上, 該數組是動態分配的, arenas僅僅是一個數組指針. 預設情況下arenas數組的
長度與如下變數相關,
unsigned narenas_total; unsigned narenas_auto; size_t opt_narenas = 0;
而它們又與當前cpu核心數量相關. 核心數量記錄在另外一個全局變數ncpus里,
unsigned ncpus;
如果ncpus等於1, 則有且僅有一個arena, 如果大於1, 則預設arenas的數量為ncpus的四倍.
即雙核下8個arena, 四核下16個arena, 依此類推.
(gdb) p ncpus $20 = 4 (gdb) p narenas_total $21 = 16
jemalloc變體很多, 不同變體對arenas的數量有所調整, 比如firefox中arena固定為1,
而android被限定為最大不超過2. 這個限制被寫到android jemalloc的mk文件中.
------[ 2.2.3 - choose_arena
最早引入arena並非由Je首創, 但早期線程與arena綁定是通過hash線程id實現的, 相對
來說隨機性比較強. Je改進了綁定的演算法, 使之更加科學合理.
Je中線程與arena綁定由函數choose_arena完成, 被綁定的arena記錄在該線程的tls中,
JEMALLOC_INLINE arena_t * choose_arena(arena_t *arena) { ...... // xf: 通常情況下線程所綁定的arena記錄在arenas_tls中 if ((ret = *arenas_tsd_get()) == NULL) { // xf: 如果當前thread未綁定arena, 則為其指定一個, 並保存到tls ret = choose_arena_hard(); } return (ret); }
初次搜索arenas_tsd_get可能找不到該函數在何處被定義. 實際上, Je使用了一組巨集,
來生成一個函數族, 以達到類似函數模板的目的. tsd相關的函數族被定義在tsd.h中.
1. malloc_tsd_protos - 定義了函數聲明, 包括初始化函數boot, get/set函數
2. malloc_tsd_externs - 定義變數聲明, 包括tls, 初始化標誌等等
3. malloc_tsd_data - tls變數定義
4. malloc_tsd_funcs - 定義了1中聲明函數的實現.
與arena tsd相關的函數和變數聲明如下,
malloc_tsd_protos(JEMALLOC_ATTR(unused), arenas, arena_t *) malloc_tsd_externs(arenas, arena_t *) malloc_tsd_data(, arenas, arena_t *, NULL) malloc_tsd_funcs(JEMALLOC_ALWAYS_INLINE, arenas, arena_t *, NULL, arenas_cleanup)
當線程還未與任何arena綁定時, 會進一步通過choose_arena_hard尋找一個合適的arena
進行綁定. Je會遍歷arenas數組, 並按照優先順序由高到低的順序挑選,
1. 如果找到當前線程綁定數為0的arena, 則優先使用它.
2. 如果當前已初始化arena中沒有線程綁定數為0的, 則優先使用剩餘空的數組位置
構造一個新的arena. 需要說明的是, arenas數組遵循lazy create原則, 初始狀態
整個數組只有0號元素是被初始化的, 其他的slot位置都是null指針. 因此隨著新的
線程不斷創造出來, arena數組也被逐漸填滿.
3. 如果1,2兩條都不滿足, 則選擇當前綁定數最小的, 且slot位置更靠前的一個arena.
arena_t * choose_arena_hard(void) { ...... if (narenas_auto > 1) { ...... first_null = narenas_auto; // xf: 迴圈遍歷所有arenas, 找到綁定thread數量最小的arena, 並記錄 // first_null索引值 for (i = 1; i < narenas_auto; i++) { if (arenas[i] != NULL) { if (arenas[i]->nthreads < arenas[choose]->nthreads) choose = i; } else if (first_null == narenas_auto) { first_null = i; } } // xf: 若選定的arena綁定thread為0, 或者當前arena數組中已滿, 則返回 // 被選中的arena if (arenas[choose]->nthreads == 0 || first_null == narenas_auto) { ret = arenas[choose]; } else { // xf: 否則構造並初始化一個新的arena ret = arenas_extend(first_null); } ...... } else { // xf: 若不存在多於一個arena(單核cpu或人為強制設定), 則返回唯一的 // 0號arena ret = arenas[0]; ...... } // xf: 將已綁定的arena設置到tsd中 arenas_tsd_set(&ret); return (ret); }
對比早期的綁定方式, Je的演算法顯然更加公平, 儘可能的讓各個cpu核心平分當前線程,
平衡負載.
------[ 2.2.4 - Arena結構
struct arena_s { unsigned ind; unsigned nthreads; malloc_mutex_t lock; arena_stats_t stats; ql_head(tcache_t) tcache_ql; uint64_t prof_accumbytes; dss_prec_t dss_prec; arena_chunk_tree_t chunks_dirty; arena_chunk_t *spare; size_t nactive; size_t ndirty; size_t npurgatory; arena_avail_tree_t runs_avail; chunk_alloc_t *chunk_alloc; chunk_dalloc_t *chunk_dalloc; arena_bin_t bins[NBINS]; };
ind: 在arenas數組中的索引值.
nthreads: 當前綁定的線程數.
lock: 局部arena lock, 取代傳統分配器的global lock.
一般地, 如下操作需要arena lock同步,
1. 線程綁定, 需要修改nthreads
2. new chunk alloc
3. new run alloc
stats: 全局統計, 需要打開統計功能.
tcache_ql: ring queue, 註冊所有綁定線程的tcache, 作為統計用途, 需要打開統計功能.
dss_prec: 代表當前chunk alloc時對系統記憶體的使用策略, 分為幾種情況,
typedef enum { dss_prec_disabled = 0, dss_prec_primary = 1, dss_prec_secondary = 2, dss_prec_limit = 3 } dss_prec_t;
第一個代表禁止使用系統DSS, 後兩種代表是否優先選用DSS. 如果使用
primary, 則本著先dss->mmap的順序, 否則按照先mmap->dss. 預設使用
dss_prec_secondary.
chunks_dirty: rb tree, 代表所有包含dirty page的chunk集合. 後面在chunk中會
詳細介紹.
spare: 是一個緩存變數, 記錄最近一次被釋放的chunk. 當arena收到一個新的chunk
alloc請求時, 會優先從spare中開始查找, 由此提高頻繁分配釋放時, 可能
導致內部chunk利用率下降的情況.
runs_avail: rb tree, 記錄所有未被分配的runs, 用來在分配new run時尋找合適的
available run. 一般作為alloc run時的倉庫.
chunk_alloc/chunk_dalloc: 用戶可定製的chunk分配/釋放函數, Je提供了預設的版本,
chunk_alloc_default/chunk_dalloc_default
bins: bins數組, 記錄不同class size可用free regions的分配信息, 後面會詳細介紹.
----[ 2.3 - Chunk (arena_chunk_t)
chunk是僅次於arena的次級記憶體結構. 如果有瞭解過Dlmalloc, 就會知道在Dl中同樣
定義了名為'chunk'的基礎結構. 但這個概念在兩個分配器中含義完全不同, Dl中的
chunk指代最低級分配單元, 而Je中則是一個較大的記憶體區域.
------[ 2.3.1 - overview
從前面arena的數據結構可以發現, 它是一個非常抽象的概念, 其大小也不代表實際的
記憶體分配量. 原始的記憶體數據既非掛載在arena外部, 也並沒有通過內部指針引用,
而是記錄在chunk中. 按照一般的思路, chunk包含原始記憶體數據, 又從屬於arena,
因此後者應該會有一個數組之類的結構以記錄所有chunk信息. 但事實上同樣找不到
這樣的記錄. 那Je又如何獲得chunk指針呢?
所謂的chunk結構, 只是整個chunk的一個header, bookkeeping以及user memory都掛在
header外面. 另外Je對chunk又做了規定, 預設每個chunk大小為4MB, 同時還必須對齊
到4MB的邊界上.
#define LG_CHUNK_DEFAULT 22
這個巨集定義了chunk的大小. 註意到首碼'LG_', 代表log即指數部分.
Je中所有該首碼的代碼都是這個含義, 便於通過bit操作進行快速的運算.
有了上述規定, 獲得chunk就變得幾乎沒有代價. 因為返回給user程式的記憶體地址肯定
屬於某個chunk, 而該chunk header對齊到4M邊界上, 且不可能超過4M大小, 所以只需要
對該地址做一個下對齊就得到chunk指針, 如下,
#define CHUNK_ADDR2BASE(a) \ ((void *)((uintptr_t)(a) & ~chunksize_mask))
計算相對於chunk header的偏移量,
#define CHUNK_ADDR2OFFSET(a) \ ((size_t)((uintptr_t)(a) & chunksize_mask))
以及上對齊到chunk邊界的計算,
#define CHUNK_CEILING(s) \ (((s) + chunksize_mask) & ~chunksize_mask)
用圖來表示如下,
chunk_ptr(4M aligned) memory for user | | v v +--------------+-------------------------------------------- | chunk header | ... ... | region | ... ... +--------------+-------------------------------------------- |<------------- offset ------------>|
------[ 2.3.2 - Chunk結構
struct arena_chunk_s { arena_t *arena; rb_node(arena_chunk_t) dirty_link; size_t ndirty; size_t nruns_avail; size_t nruns_adjac; arena_chunk_map_t map[1]; }
arena: chunk屬於哪個arena
dirty_link: 用於rb tree的鏈接節點. 如果某個chunk內部含有任何dirty page,
就會被掛載到arena中的chunks_dirty tree上.
ndirty: 內部dirty page數量.
nruns_avail: 內部available runs數量.
nruns_adjac: available runs又分為dirty和clean兩種, 相鄰的兩種run是無法合併的,
除非其中的dirty runs通過purge才可以. 該數值記錄的就是可以通過
purge合併的run數量.
map: 動態數組, 每一項對應chunk中的一個page狀態(不包含header即map本身的占用).
chunk(包括內部的run)都是由page組成的. page又分為unallocated, small,
large三種.
unallocated指的那些還未建立run的page.
small/large分別指代該page所屬run的類型是small/large run.
這些page的分配狀態, 屬性, 偏移量, 及其他的標記信息等等, 都記錄在
arena_chunk_map_t中.
|<--------- map_bias ----------->| | page | page | ... ... | page | +-----------------------------------------------------------------------+ | chunk_header | chunk map | page #0 | page #1 | ... | page #n | | ... ... | [0] [1] ... [n] | | | | | +-----------------|---|-------|-----------------------------------------+ | | | ^ ^ ^ +---|-------|-------+ | | +-------|------------------+ | + -----------------------------------+
至於由chunk header和chunk map占用的page數量, 保存在map_bias變數中.
該變數是Je在arena boot時通過迭代演算法預先計算好的, 所有chunk都是相同的.
迭代方法如下,
1. 第一次迭代初始map_bias等於0, 計算最大可能大小, 即
header_size + chunk_npages * map_size
獲得header+map需要的page數量, 結果肯定高於最終的值.
2. 第二次將之前計算的map_bias迭代回去, 將最大page數減去map_bias數, 重新計算
header+map大小, 由於第一次迭代map_bias過大, 第二次迭代必定小於最終結果.
3. 第三次再將map_bias迭代回去, 得到最終大於第二次且小於第一次的計算結果.
相關代碼如下,
void arena_boot(void) { ...... map_bias = 0; for (i = 0; i < 3; i++) { header_size = offsetof(arena_chunk_t, map) + (sizeof(arena_chunk_map_t) * (chunk_npages-map_bias)); map_bias = (header_size >> LG_PAGE) + ((header_size & PAGE_MASK) != 0); } ...... }
------[ 2.3.3 - chunk map (arena_chunk_map_t)
chunk記錄page狀態的結構為arena_chunk_map_t, 為了節省空間, 使用了bit壓縮存儲信息.
struct arena_chunk_map_s { #ifndef JEMALLOC_PROF union { #endif union { rb_node(arena_chunk_map_t) rb_link; ql_elm(arena_chunk_map_t) ql_link; } u; prof_ctx_t *prof_ctx; #ifndef JEMALLOC_PROF }; #endif size_t bits; }
chunk map內部包含兩個link node, 分別可以掛載到rb tree或環形隊列上, 同時
為了節省空間又使用了union. 由於run本身也是由連續page組成的, 因此chunk map
除了記錄page狀態之外, 還負責run的基址檢索.
舉例來說, Je會把所有已分配run記錄在內部rb tree上以快速檢索, 實際地操作是
將該run中第一個page對應的chunk_map作為rb node掛載到tree上. 檢索時也是先
找出將相應的chunk map, 再進行地址轉換得到run的基址.
按照通常的設計思路, 我們可能會把run指針作為節點直接保存到rb tree中. 但Je中
的設計明顯要更複雜. 究其原因, 如果把link node放到run中, 後果是bookkeeping和
user memory將混淆在一起, 這對於分配器的安全性是很不利的. 包括Dl在內的傳統
分配器都具有這樣的缺陷. 而如果單獨用link node記錄run, 又會造成空間浪費.
正因為Je中無論是chunk還是run都是連續page組成, 所以用首個page對應的chunk map
就能同時代表該run的基址.
Je中通常用mapelm換算出pageind, 再將pageind << LG_PAGE + chunk_base, 就能得到
run指針, 代碼如下,
arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm); size_t pageind = arena_mapelm_to_pageind(mapelm); run = (arena_run_t *)((uintptr_t)run_chunk + (pageind << LG_PAGE)); JEMALLOC_INLINE_C size_t arena_mapelm_to_pageind(arena_chunk_map_t *mapelm) { uintptr_t map_offset = CHUNK_ADDR2OFFSET(mapelm) - offsetof(arena_chunk_t, map); return ((map_offset / sizeof(arena_chunk_map_t)) + map_bias); }
chunk map對page狀態描述都壓縮記錄到bits中, 由於內容較多, 直接引用Je代碼
中的註釋,
下麵是一個假想的ILP32系統下的bits layout,
???????? ???????? ????nnnn nnnndula
"?"的部分分三種情況, 分別對應unallocated, small和large.
? : Unallocated: 首尾page寫入該run的地址, 而內部page則不做要求.
Small: 全部是page的偏移量.
Large: 首page是run size, 後續的page不做要求.
n : 對於small run指其所在bin的index, 對large run寫入BININD_INVALID.
d : dirty?
u : unzeroed?
l : large?
a : allocated?
下麵是對三種類型的run page做的舉例,
p : run page offset
s : run size
n : binind for size class; large objects set these to BININD_INVALID
x : don't care
- : 0
+ : 1
[DULA] : bit set
[dula] : bit unset
Unallocated (clean):
ssssssss ssssssss ssss++++ ++++du-a
xxxxxxxx xxxxxxxx xxxxxxxx xxxx-Uxx
ssssssss ssssssss ssss++++ ++++dU-a
Unallocated (dirty):
ssssssss ssssssss ssss++++ ++++D--a
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
ssssssss ssssssss ssss++++ ++++D--a
Small:
pppppppp pppppppp ppppnnnn nnnnd--A
pppppppp pppppppp ppppnnnn nnnn---A
pppppppp pppppppp ppppnnnn nnnnd--A
Small page需要註意的是, 這裡代表的p並非是一個固定值, 而是該page相對於
其所在run的第一個page的偏移量, 比如可能是這樣,
00000000 00000000 0000nnnn nnnnd--A
00000000 00000000 0001nnnn nnnn---A
00000000 00000000 0010nnnn nnnn---A
00000000 00000000 0011nnnn nnnn---A
...
00000000 00000001 1010nnnn nnnnd--A
Large:
ssssssss ssssssss ssss++++ ++++D-LA
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
-------- -------- ----++++ ++++D-LA
Large (sampled, size <= PAGE):
ssssssss ssssssss ssssnnnn nnnnD-LA
Large (not sampled, size == PAGE):
ssssssss ssssssss ssss++++ ++++D-LA
為了提取/設置map bits內部的信息, Je提供了一組函數, 這裡列舉兩個最基本的,
剩下的都是讀取mapbits後做一些位運算而已,
讀取mapbits,
JEMALLOC_ALWAYS_INLINE size_t arena_mapbits_get(arena_chunk_t *chunk, size_t pageind) { return (arena_mapbitsp_read(arena_mapbitsp_get(chunk, pageind))); }
根據pageind獲取對應的chunk map,
JEMALLOC_ALWAYS_INLINE arena_chunk_map_t * arena_mapp_get(arena_chunk_t *chunk, size_t pageind) { ...... return (&chunk->map[pageind-map_bias]); }
----[ 2.4 - Run (arena_run_t)
如同在2.1節所述, 在Je中run才是真正負責分配的主體(前提是對small region來說).
run的大小對齊到page size上, 並且在內部劃分成大小相同的region. 當有外部分配
請求時, run就會從內部挑選一個free region返回. 可以認為run就是small region倉庫.
------[ 2.4.1 - Run結構
struct arena_run_s { arena_bin_t *bin; uint32_t nextind; unsigned nfree; };
run的結構非常簡單, 但同chunk類似, 所謂的arena_run_t不過是整個run的header部分.
bin: 與該run相關聯的bin. 每個run都有其所屬的bin, 詳細內容在之後介紹.
nextind: 記錄下一個clean region的索引.
nfree: 記錄當前空閑region數量.
除了header部分之外, run的真實layout如下,
/--------------------\ | arena_run_t header | | ... | bitmap_offset | bitmap | | ... | |--------------------| | redzone | reg0_offset | region 0 | | redzone | |--------------------| \ | redzone | | | region 1 | > reg_interval | redzone | / |--------------------| | ... | | ... | | ... | |--------------------| | redzone | | region nregs-1 | | redzone | |--------------------| | alignment pad? | \--------------------/
正如chunk通過chunk map記錄內部所有page狀態一樣, run通過在header後掛載
bitmap來記錄其內部的region狀態. bitmap之後是regions區域. 內部region
大小相等, 且在前後都有redzone保護(需要在設置里打開redzone選項).
簡單來說, run就是通過查詢bitmap來找到可用的region. 而傳統分配器由於使用
boundary tag, 空閑region一般是被雙向鏈表管理的. 相比之下, 傳統方式查找
速度更快, 也更簡單. 缺點之前也提到過, 安全和穩定性都存在缺陷. 從這一點
可以看到, Je在設計思路上將bookkeeping和user memory分離是貫穿始終的原則,
更甚於對性能的影響(事實上這點影響在併發條件下被大大賺回來了).
------[ 2.4.2 - size classes
記憶體分配器對內部管理的region往往按照某種特殊規律來分配. 比如Dl將記憶體劃分成
small和large兩種類型. small類型從8位元組開始每8個位元組為一個分割直至256位元組.
而large類型則從256位元組開始, 掛載到dst上. 這種劃分方式有助於分配器對記憶體進行
有效的管理和控制, 讓已分配的記憶體更加緊實(tightly packed), 以降低外部碎片率.
Je進一步優化了分配效率. 採用了類似於"二分伙伴(Binary Buddy)演算法"的分配方式.
在Je中將不同大小的類型稱為size class.
在Je源碼的size_classes.h文件中, 定義了不同體系架構下的region size. 該文件
實際是通過名為size_classes.sh的shell script自動生成的. script按照四種不同
量綱定義來區分各個體系平臺的區別, 然後將它們做排列組合, 就可以相容各個體系.
這四種量綱分別是,
LG_SIZEOF_PTR: 代表指針長度, ILP32下是2, LP64則是3.
LG_QUANTUM: 量子, binary buddy分得的最小單位. 除了tiny size, 其他的size
classes都是quantum的整數倍大小.
LG_TINY_MIN: 是比quantum更小的size class, 且必須對齊到2的指數倍上. 它是Je可
分配的最小的size class.
LG_PAGE: 就是page大小
根據binary buddy演算法, Je會將記憶體不斷的二平分, 每一份稱作一個group. 同一個
group內又做四等分. 例如, 一個典型的ILP32, tiny等於8byte, quantum為16byte,
page為4096byte的系統, 其size classes劃分是這樣的,
#if (LG_SIZEOF_PTR == 2 && LG_TINY_MIN == 3 && LG_QUANTUM == 4 && LG_PAGE == 12) #define SIZE_CLASSES \ index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup \ SC( 0, 3, 3, 0, yes, 3) \ \ SC( 1, 3, 3, 1, yes, 3) \ SC( 2, 4, 4, 1, yes, 4) \ SC( 3, 4, 4, 2, yes, 4) \ SC( 4, 4, 4, 3, yes, 4) \ \ SC( 5, 6, 4, 1, yes, 4) \ SC( 6, 6, 4, 2, yes, 4) \ SC( 7, 6, 4, 3, yes, 4) \ SC( 8, 6, 4, 4, yes, 4) \ \ SC( 9, 7, 5, 1, yes, 5) \ SC( 10, 7, 5, 2, yes, 5) \ SC( 11, 7, 5, 3, yes, 5) \ SC( 12, 7, 5, 4, yes, 5) \ ... ...
巨集SIZE_CLASSES主要功能就是可以生成幾種類型的table. 而SC則根據不同的情況
被定義成不同的含義. SC傳入的6個參數的含義如下,
index: 在table中的位置
lg_grp: 所在group的指數
lg_delta: group內偏移量指數
ndelta: group內偏移數
bin: 是否由bin記錄. small region是記錄在bins中
lg_delta_lookup: 在lookup table中的調用S2B_#的尾數尾碼
因此得到reg_size的計算公式, reg_size = 1 << lg_grp + ndelta << lg_delta
根據該公式, 可以得到region的範圍,
┌─────────┬─────────┬───────────────────────────────────────┐ │Category │ Spacing │ Size │ ├─────────┼─────────┼───────────────────────────────────────┤ │ │ lg │ [8] │ │ ├─────────┼───────────────────────────────────────┤ │ │ 16 │ [16, 32, 48, ..., 128] │ │ ├─────────┼───────────────────────────────────────┤ │ │ 32 │ [160, 192, 224, 256] │ │ ├─────────┼───────────────────────────────────────┤ │Small │ 64 │ [320, 384, 448, 512] │ │ ├─────────┼───────────────────────────────────────┤ │ │ 128 │ [640, 768, 896, 1024] │ │ ├─────────┼───────────────────────────────────────┤ │ │ 256 │ [1280, 1536, 1792, 2048] │ │ ├─────────┼───────────────────────────────────────┤ │ │ 512 │ [2560, 3072, 3584] │ ├─────────┼─────────┼───────────────────────────────────────┤ │Large │ 4 KiB │ [4 KiB, 8 KiB, 12 KiB, ..., 4072 KiB] │ ├─────────┼─────────┼───────────────────────────────────────┤ │Huge │ 4 MiB │ [4 MiB, 8 MiB, 12 MiB, ...] │ └─────────┴─────────┴───────────────────────────────────────┘
除此之外, 在size_classes.h中還定義了一些常量,
tiny bins的數量
#define NTBINS 1
可以通過lookup table查詢的bins數量
#define NLBINS 29
small bins的數量
#define NBINS 28
最大tiny size class的指數
#define LG_TINY_MAXCLASS 3
最大lookup size class, 也就是NLBINS - 1個bins
#define LOOKUP_MAXCLASS ((((size_t)1) << 11) + (((size_t)4) << 9))
最大small size class, 也就是NBINS - 1個bins
#define SMALL_MAXCLASS ((((size_t)1) << 11) + (((size_t)3) << 9))
------[ 2.4.3 - size2bin/bin2size
通過SIZE_CLASSES建立的table就是為了在O(1)的時間複雜度內快速進行size2bin或者
bin2size切換. 同樣的技術在Dl中有所體現, 來看Je是如何實現的.
size2bin切換提供了兩種方式, 較快的是通過查詢lookup table, 較慢的是計算得到.
從原理上, 只有small size class需要查找bins, 但可通過lookup查詢的size class
數量要小於整個small size class數量. 因此, 部分size class只能計算得到.
在原始Je中統一隻採用查表法, 但在android版本中可能是考慮減小lookup table
size, 而增加了直接計演算法.
JEMALLOC_ALWAYS_INLINE size_t small_size2bin(size_t size) { ...... if (size <= LOOKUP_MAXCLASS) return (small_size2bin_lookup(size)); else return (small_size2bin_compute(size)); }
小於LOOKUP_MAXCLASS的請求通過small_size2bin_lookup直接查表.
查詢的演算法是這樣的,
size_t ret = ((size_t)(small_size2bin_tab[(size-1) >> LG_TINY_MIN]));
也就是說, Je通過一個
f(x) = (x - 1) / 2^LG_TINY_MIN
的變換將size映射到lookup table的相應區域. 這個table在gdb中可能是這樣的,
(gdb) p /d small_size2bin $6 = {0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, <
