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, 16,
16, 16, 17 <repeats 16 times>, 18 <repeats 16 times>, 19 <repeats 16 times>,
20 <repeats 16 times>, 21 <repeats 32 times>, 22 <repeats 32 times>,
23 <repeats 32 times>, 24 <repeats 32 times>, 25 <repeats 64 times>,
26 <repeats 64 times>, 27 <repeats 64 times>}
該數組的含義與binary buddy算法是一致的. 對應的bin index越高, 其在數組中占用的
字節數就越多. 除了0號bin之外, 相鄰的4個bin屬於同一group, 兩個group之間相差二倍,
因此在數組中占用的字節數也就相差2倍. 所以, 上面數組的group劃分如下,
{0}, {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}, ...
以bin#9為例, 其所管轄的范圍(128, 160], 由於其位於更高一級group, 因此相比bin#8
在lookup table中多一倍的字節數, 假設我們需要查詢132, 經過映射,
(132 - 1) >> 3 = 16
這樣可以快速得到其所在的bin #9. 如圖,
bin #1 bin #3 132 is HERE!
| | |
v v v
+----------------------------------------------------------------
| 0 | 1 | 2 2 | 3 3 | ... | 8 8 | 9 9 9 9 | ... | 16 ... 16 | ...
+----------------------------------------------------------------
^ ^ ^ ^ ^
| | | | |
bin #0 bin #2 bin #8 bin #9 bin #16
Je巧妙的通過前面介紹CLASS_SIZE宏生成了這個lookup table, 代碼如下,
JEMALLOC_ALIGNED(CACHELINE)
const uint8_t small_size2bin_tab[] = {
#define S2B_3(i) i,
#define S2B_4(i) S2B_3(i) S2B_3(i)
#define S2B_5(i) S2B_4(i) S2B_4(i)
#define S2B_6(i) S2B_5(i) S2B_5(i)
#define S2B_7(i) S2B_6(i) S2B_6(i)
#define S2B_8(i) S2B_7(i) S2B_7(i)
#define S2B_9(i) S2B_8(i) S2B_8(i)
#define S2B_no(i)
#define SC(index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup) \
S2B_##lg_delta_lookup(index)
SIZE_CLASSES
#undef S2B_3
#undef S2B_4
#undef S2B_5
#undef S2B_6
#undef S2B_7
#undef S2B_8
#undef S2B_9
#undef S2B_no
#undef SC
};
這裡的S2B_xx是一系列宏的嵌套展開, 最終對應的就是不同group在lookup table中
占據的字節數以及bin索引. 相信看懂了前面的介紹就不難理解.
另一方面, 大於LOOKUP_MAXCLASS但小於SMALL_MAXCLASS的size class不能查表獲得,
需要進行計算. 簡言之, 一個bin number是三部分組成的,
bin_number = NTBIN + group_number << LG_SIZE_CLASS_GROUP + mod
即tiny bin數量加上其所在group再加上group中的偏移(0-2). 源碼如下,
JEMALLOC_INLINE size_t
small_size2bin_compute(size_t size)
{
......
{
// xf: lg_floor相當於ffs
size_t x = lg_floor((size<<1)-1);
// xf: 計算size class所在group number
size_t shift = (x < LG_SIZE_CLASS_GROUP + LG_QUANTUM) ? 0 :
x - (LG_SIZE_CLASS_GROUP + LG_QUANTUM);
size_t grp = shift << LG_SIZE_CLASS_GROUP;
size_t lg_delta = (x < LG_SIZE_CLASS_GROUP + LG_QUANTUM + 1)
? LG_QUANTUM : x - LG_SIZE_CLASS_GROUP - 1;
size_t delta_inverse_mask = ZI(-1) << lg_delta;
// xf: 計算剩余mod部分
size_t mod = ((((size-1) & delta_inverse_mask) >> lg_delta)) &
((ZU(1) << LG_SIZE_CLASS_GROUP) - 1);
// xf: 組合計算bin number
size_t bin = NTBINS + grp + mod;
return (bin);
}
}
其中LG_SIZE_CLASS_GROUP是size_classes.h中的定值, 代表一個group中包含的bin
數量, 根據binary buddy算法, 該值通常情況下是2.
而要找到size class所在的group, 與其最高有效位相關. Je通過類似於ffs的函數
首先獲得size的最高有效位x,
size_t x = lg_floor((size<<1)-1);
至於group number, 則與quantum size有關. 因為除了tiny class, quantum size
位於group #0的第一個. 因此不難推出,
group_number = 2^x / quantum_size / 2^LG_SIZE_CLASS_GROUP
對應代碼就是,
size_t shift = (x < LG_SIZE_CLASS_GROUP + LG_QUANTUM) ? 0 :
x - (LG_SIZE_CLASS_GROUP + LG_QUANTUM);
而對應group起始位置就是,
size_t grp = shift << LG_SIZE_CLASS_GROUP;
至於mod部分, 與之相關的是最高有效位之後的兩個bit.
Je在這裡經過了復雜的位變換,
size_t lg_delta = (x < LG_SIZE_CLASS_GROUP + LG_QUANTUM + 1)
? LG_QUANTUM : x - LG_SIZE_CLASS_GROUP - 1;
size_t delta_inverse_mask = ZI(-1) << lg_delta;
size_t mod = ((((size-1) & delta_inverse_mask) >> lg_delta)) &
((ZU(1) << LG_SIZE_CLASS_GROUP) - 1);
上面代碼直白的翻譯, 實際上就是要求得如下兩個bit,
1 0000
10 0000
11 0000
group #0 100 0000
-------------------------------------------------
+--+
101 0000 - 1 = 1|00| 1111
110 0000 - 1 = 1|01| 1111
111 0000 - 1 = 1|10| 1111
group #1 1000 0000 - 1 = 1|11| 1111
+--+
--------------------------------------------------
+--+
1010 0000 - 1 = 1|00|1 1111
1100 0000 - 1 = 1|01|1 1111
1110 0000 - 1 = 1|10|1 1111
group #2 10000 0000 - 1 = 1|11|1 1111
+--+
--------------------------------------------------
根據這個圖示再去看Je的代碼就不難理解了. mod的計算結果就是從0-3的數值.
而最終的結果是前面三部分的組合即,
size_t bin = NTBINS + grp + mod;
而bin2size查詢就簡單得多. 上一節介紹SIZE_CLASSES時提到過small region的計算
公式, 只需要根據該公式提前計算出所有bin對應的region size, 直接查表即可.
這裡不再贅述.
----[ 2.5 - bins (arena_bin_t)
run是分配的執行者, 而分配的調度者是bin. 這個概念同Dl中的bin是類似的, 但Je中
bin要更復雜一些. 直白地說, 可以把bin看作non-full run的倉庫, bin負責記錄當前
arena中某一個size class范圍內所有non-full run的使用情況. 當有分配請求時,
arena查找相應size class的bin, 找出可用於分配的run, 再由run分配region. 當然,
因為只有small region分配需要run, 所以bin也只對應small size class.
與bin相關的數據結構主要有兩個, 分別是arena_bin_t和arena_bin_info_t.
在2.1.3中提到arena_t內部保存了一個bin數組, 其中的成員就是arena_bin_t.
其結構如下,
struct arena_bin_s {
malloc_mutex_t lock;
arena_run_t *runcur;
arena_run_tree_t runs;
malloc_bin_stats_t stats;
};
lock: 該lock同arena內部的lock不同, 主要負責保護current run. 而對於run本身的
分配和釋放還是需要依賴arena lock. 通常情況下, 獲得bin lock的前提是獲得
arena lock, 但反之不成立.
runcur: 當前可用於分配的run, 一般情況下指向地址最低的non-full run, 同一時間
一個bin只有一個current run用於分配.
runs: rb tree, 記錄當前arena中該bin對應size class的所有non-full runs. 因為
分配是通過current run完成的, 所以也相當於current run的倉庫.
stats: 統計信息.
另一個與bin相關的結構是arena_bin_info_t. 與前者不同, bin_info保存的是
arena_bin_t的靜態信息, 包括相對應size class run的bitmap offset, region size,
region number, bitmap info等等(此類信息只要class size決定, 就固定下來). 所有
上述信息在Je中由全局數組arena_bin_info記錄. 因此與arena無關, 全局僅保留一份.
arena_bin_info_t的定義如下,
struct arena_bin_info_s {
size_t reg_size;
size_t redzone_size;
size_t reg_interval;
size_t run_size;
uint32_t nregs;
uint32_t bitmap_offset;
bitmap_info_t bitmap_info;
uint32_t reg0_offset;
};
reg_size: 與當前bin的size class相關聯的region size.
reg_interval: reg_size+redzone_size
run_size: 當前bin的size class相關聯的run size.
nregs: 當前bin的size class相關聯的run中region數量.
bitmap_offset: 當前bin的size class相關聯的run中bitmap偏移.
bitmap_info: 記錄當前bin的size class相關聯的run中bitmap信息.
reg0_offset: index為0的region在run中的偏移量.
以上記錄的靜態信息中尤為重要的是bitmap_info和bitmap_offset.
其中bitmap_info_t定義如下,
struct bitmap_info_s {
size_t nbits;
unsigned nlevels;
bitmap_level_t levels[BITMAP_MAX_LEVELS+1];
};
nbits: bitmap中邏輯bit位數量(特指level#0的bit數)
nlevels: bitmap的level數量
levels: level偏移量數組, 每一項記錄該級level在bitmap中的起始index
struct bitmap_level_s {
size_t group_offset;
};
在2.3.1節中介紹arena_run_t時曾提到Je通過外掛bitmap將bookkeeping和user memory
分離. 但bitmap查詢速度要慢於boundary tag. 為了彌補這個缺陷, Je對此做了改進,
通過多級level緩沖以替代線性查找.
Je為bitmap增加了多級level, bottom level同普通bitmap一致, 每1bit代表一個region.
而高一級level中1bit代表前一級level中一個byte. 譬如說, 若我們在當前run中存在128
個region, 則在ILP32系統上, 需要128/32 = 4byte來表示這128個region. Je將這4個byte
看作level #0. 為了進一步表示這4個字節是否被占用, 又額外需要1byte以緩存這4byte
的內容(僅使用了4bit), 此為level#1. 即整個bitmap, 一共有2級level, 共5byte來描述.
+--------------+ +--------+
+-----------|------------ +| +----------|-------+|
v v || v v ||
+--------------------------------------------------------------------------
| 1101 0010 | 0000 0000 | ... | 10?? ???? | ???? ???? | 1??? ???? | ...
+--------------------------------------------------------------------------
|<--------- level #0 -------->|<----- level #1 ------>|<- level #2 ->|
----[ 2.6 - Thread caches (tcache_t)
TLS/TSD是另一種針對多線程優化使用的分配技術, Je中稱為tcache. tcache解決
的是同一cpu core下不同線程對heap的競爭. 通過為每個線程指定專屬分配區域,
來減小線程間的干擾. 但顯然這種方法會增大整體內存消耗量. 為了減小副作用,
je將tcache設計成一個bookkeeping結構, 在tcache中保存的僅僅是指向外部region
的指針, region對象仍然位於各個run當中. 換句話說, 如果一個region被tcache
記錄了, 那麼從run的角度看, 它就已經被分配了.
tcache的內容如下,
struct tcache_s {
ql_elm(tcache_t) link;
uint64_t prof_accumbytes;
arena_t *arena;
unsigned ev_cnt;
unsigned next_gc_bin;
tcache_bin_t tbins[1];
};
link: 鏈接節點, 用於將同一個arena下的所有tcache鏈接起來.
prof_accumbytes: memory profile相關.
arena: 該tcache所屬的arena指針.
ev_cnt: 是tcache內部的一個周期計數器. 每當tcache執行一次分配或釋放時,
ev_cnt會記錄一次. 直到周期到來, Je會執行一次incremental gc.
這裡的gc會清理tcache中多余的region, 將它們釋放掉. 盡管這不意味
著系統內存會獲得釋放, 但可以解放更多的region交給其他更饑餓的
線程以分配.
next_gc_bin: 指向下一次gc的binidx. tcache gc按照一周期清理一個bin執行.
tbins: tcache bin數組. 同樣外掛在tcache後面.
同arena bin類似, tcache同樣有tcache_bin_t和tcache_bin_info_t.
tcache_bin_t作用類似於arena bin, 但其結構要比後者更簡單. 准確的說,
tcache bin並沒有分配調度的功能, 而僅起到記錄作用. 其內部通過一個stack
記錄指向外部arena run中的region指針. 而一旦region被cache到tbins內,
就不能再被其他任何線程所使用, 盡管它可能甚至與其他線程tcache中記錄的
region位於同一個arena run中.
tcache bin結構如下,
struct tcache_bin_s {
tcache_bin_stats_t tstats;
int low_water;
unsigned lg_fill_div;
unsigned ncached;
void **avail;
}
tstats: tcache bin內部統計.
low_water: 記錄兩次gc間tcache內部使用的最低水線. 該數值與下一次gc時嘗試
釋放的region數量有關. 釋放量相當於low water數值的3/4.
lg_fill_div: 用作tcache refill時作為除數. 當tcache耗盡時, 會請求arena run
進行refill. 但refill不會一次性灌滿tcache, 而是依照其最大容量
縮小2^lg_fill_div的倍數. 該數值同low_water一樣是動態的, 兩者
互相配合確保tcache處於一個合理的充滿度.
ncached: 指當前緩存的region數量, 同時也代表棧頂index.
avail: 保存region指針的stack, 稱為avail-stack.
tcache_bin_info_t保存tcache bin的靜態信息. 其本身只保存了tcache max容量.
該數值是在tcache boot時根據相對應的arena bin的nregs決定的. 通常等於nregs
的二倍, 但不得超過TCACHE_NSLOTS_SMALL_MAX. 該數值默認為200, 但在android
中大大提升了該限制, small bins不得超過8, large bins則為16.
struct tcache_bin_info_s {
unsigned ncached_max;
};
tcache layout如下,
+---------------+
/ | link |
tcache_t < | next_gc_bin |
\ | ... |
|---------------|
/ | tstats |
tbins[0] < | ... |
| | ncached |
\ | avail --------------+
|---------------| |
| ... | |
| ... | |
| ... | |
|---------------| |
/ | tstats | |
tbins[nhb < | ... | |
ins] | | ncached | |
\ | avail --------------|---+
|---------------| | | current arena run
| padding | | | +----------------+
|---------------| <---+ | | run header |
/ | stack[0] | | | ... |
avail-stack < | stack[1] | | | bitmap |
for tbins[0] | | ... | | | ... |
| | ... | | |----------------|
| | stack[ncached | | | region #0 |
\ | _max - 1] | | | ... |
|---------------| | |----------------|
| ... | | +--------> | region #1 |
| ... | | | | ... |
| ... | | | |----------------|
|---------------| <-------+ | | ... |
avail-stack / | stack[0] |--------------|--+ | ... |
for tbins[ < | ... | | | |----------------|
nhbins] | | stack[n] |--------------|--|-----> | region #n |
| | ... | | | | ... |
| | stack[ncached | | | |----------------|
\ | _max - 1] |--------------+ | | ... |
+---------------+ | | ... |
| |----------------|
+-----> | region #nregs-1|
| ... |
+----------------+
----[ 2.7 - Extent Node (extent_node_t)
extent node代表huge region, 即大於chunk大小的內存單元. 同arena run不同,
extent node並非是一個header構造, 而是外掛的. 因此其本身仍屬small region.
只不過並不通過bin分配, 而由base_nodes直接動態創建.
Je中對所有huge region都是通過rb tree管理. 因此extent node同時也是tree node.
一個node節點被同時掛載到兩棵rb tree上. 一棵采用szad的查詢方式, 另一棵則采用
純ad的方式. 作用是當執行chunk recycle時查詢到可用region, 後面會詳述.
struct extent_node_s {
rb_node(extent_node_t) link_szad;
rb_node(extent_node_t) link_ad;
prof_ctx_t *prof_ctx;
void *addr;
size_t size;
arena_t *arena;
bool zeroed;
};
link_szad: szad tree的link節點.
link_ad: ad tree的link節點.
prof_ctx: 用於memory profile.
addr: 指向huge region的指針.
size: region size.
arena: huge region所屬arena.
zeroed: 代表是否zero-filled, chunk recycle時會用到.
----[ 2.8 - Base
base並不是數據類型, 而是一塊特殊區域, 主要服務於內部meta data(例如arena_t,
tcache_t, extent_node_t等等)的分配. base區域管理與如下變量相關,
static malloc_mutex_t base_mtx; static void *base_pages; static void *base_next_addr; static void *base_past_addr; static extent_node_t *base_nodes;
base_mtx: base lock
base_pages: base page指針, 代表整個區域的起始位置.
base_next_addr: 當前base指針, 類似於brk指針.
base_past_addr: base page的上限指針.
base_nodes: 指向extent_node_t鏈表的外掛頭指針.
base page源於arena中的空閒chunk, 通常情況下, 大小相當於chunk. 當base耗盡時,
會以chunk alloc的名義重新申請新的base pages.
為了保證內部meta data的快速分配和訪問. Je將內部請求大小都對齊到cache-line上,
以避免在SMP下的false sharing. 而分配方式上, 采用了快速移動base_next_addr
指針進行高速開采的方法.
void *
base_alloc(size_t size)
{
......
// xf: 將內部分配請求對齊的cache-line上, 阻止false sharing
csize = CACHELINE_CEILING(size);
malloc_mutex_lock(&base_mtx);
// xf: 如果base耗盡, 則重新分配base_pages. 默認大小為chunksize.
if ((uintptr_t)base_next_addr + csize > (uintptr_t)base_past_addr) {
if (base_pages_alloc(csize)) {
malloc_mutex_unlock(&base_mtx);
return (NULL);
}
}
// xf: 快速向前開采
ret = base_next_addr;
base_next_addr = (void *)((uintptr_t)base_next_addr + csize);
malloc_mutex_unlock(&base_mtx);
return (ret);
}
與通常的base alloc有所不同, 分配extent_node_t會優先從一個node鏈表中獲取
節點, 而base_nodes則為該鏈表的外掛頭指針. 只有當其耗盡時, 才使用前面的
分配方式. 這裡區別對待extent_node_t與其他類型, 主要與chunk recycle機制
有關, 後面會做詳細說明.
有意思的是, 該鏈表實際上借用了extent node內部rb tree node的左子樹節點指針
作為其link指針. 如2.7節所述, extent_node_t結構的起始位置存放一個rb node.
但在這裡, 當base_nodes賦值給ret後, 會強制將ret轉型成(extent_node_t **),
實際上就是指向extent_node_t結構體的第一個field的指針, 並將其指向的node
指針記錄到base_nodes裡, 成為新的header節點. 這裡需要仔細體會這個強制類型
轉換的巧妙之處.
ret = base_nodes
|
v +---- (extent_node_t**)ret
+---|------------------------------ +
| | extent_node |
| +-|-------------------------+ |
| | v rb_node | |
| | +----------+-----------+ | |
| | | rbn_left | rbn_right | | ... |
| | +----------+-----------+ | |
| +-------|-------------------+ |
+---------|-------------------------+
v
base_nodes---> +---------------+
| extent_node |
+---------------+
extent_node_t *
base_node_alloc(void)
{
extent_node_t *ret;
malloc_mutex_lock(&base_mtx);
if (base_nodes != NULL) {
ret = base_nodes;
// xf: 這裡也可以理解為, base_nodes = (extent_node_t*)(*ret);
base_nodes = *(extent_node_t **)ret;
malloc_mutex_unlock(&base_mtx);
} else {
malloc_mutex_unlock(&base_mtx);
ret = (extent_node_t *)base_alloc(sizeof(extent_node_t));
}
return (ret);
}
--[ 3 - Allocation
----[ 3.1 - Overview
在2.3.2節中得知, Je將size class劃分成small, large, huge三種類型. 分配時
這三種類型分別按照不同的算法執行. 後面的章節也將按照這個類型順序描述.
總體來說, Je分配函數從je_malloc入口開始, 經過,
je_malloc -> imalloc_body -> imalloc -> imalloct ---> arena_malloc
|
+-> huge_malloc
實際執行分配的分別是對應small/large的arena malloc和對應huge的huge malloc.
分配算法可以概括如下,
1. 首先檢查Je是否初始化, 如果沒有則初始化Je, 並標記全局malloc_initialized標記.
2. 檢查請求size是否大於huge, 如果是則執行8, 否則進入下一步.
3. 執行arena_malloc, 首先檢查size是否小於等於small maxclass, 如果是則下一步,
否則執行6.
4. 如果允許且當前線程已綁定tcache, 則從tcache分配small, 並返回. 否則下一步.
5. choose arena, 並執行arena malloc small, 返回.
6. 如果允許且當前線程已綁定tcache, 則從tcache分配large, 並返回. 否則下一步.
7. choose arena, 並執行arena malloc large, 返回.
8. 執行huge malloc, 並返回.
----[ 3.2 - Initialize
Je通過全局標記malloc_initialized指代是否初始化. 在每次分配時, 需要檢查該標記,
如果沒有則執行malloc_init.
但通常條件下, malloc_init是在Je庫被載入之前就調用的. 通過gcc的編譯擴展屬性
"constructor"實現,
JEMALLOC_ATTR(constructor)
static void
jemalloc_constructor(void)
{
malloc_init();
}
接下來由malloc_init_hard執行各項初始化工作. 這裡首先需要考慮的是多線程初始化
導致的重入, Je通過malloc_initialized和malloc_initializer兩個標記來識別.
malloc_mutex_lock(&init_lock);
// xf: 如果在獲得init_lock前已經有其他線程完成malloc_init,
// 或者當前線程在初始化過程中執行了malloc, 導致遞歸初始化, 則立即退出.
if (malloc_initialized || IS_INITIALIZER) {
malloc_mutex_unlock(&init_lock);
return (false);
}
// xf: 如果開啟多線程初始化, 需要執行busy wait直到malloc_init在另外線程中
// 執行完畢後返回.
#ifdef JEMALLOC_THREADED_INIT
if (malloc_initializer != NO_INITIALIZER && IS_INITIALIZER == false) {
do {
malloc_mutex_unlock(&init_lock);
CPU_SPINWAIT;
malloc_mutex_lock(&init_lock);
} while (malloc_initialized == false);
malloc_mutex_unlock(&init_lock);
return (false);
}
#endif
// xf: 將當前線程注冊為initializer
malloc_initializer = INITIALIZER;
初始化工作由各個xxx_boot函數完成. 注意的是, boot函數返回false代表成功,
否則代表失敗.
tsd boot: Thread specific data初始化, 主要負責tsd析構函數數組長度初始化.
base boot: base是Je內部用於meta data分配的保留區域, 使用內部獨立的分配方式.
base boot負責base node和base mutex的初始化.
chunk boot: 主要有三件工作,
1. 確認chunk_size和chunk_npages
2. chunk_dss_boot, chunk dss指chunk分配的dss(Data Storage Segment)
方式. 其中涉及dss_base, dss_prev指針的初始化工作.
3. chunk tree的初始化, 在chunk recycle時要用到.
arena boot: 主要是確認arena_maxclass, 這個size代表arena管理的最大region,
超過該值被認為huge region.
在2.2.2小節中有過介紹, 先通過多次迭代計算出map_bias, 再用
chunksize - (map_bias << LG_PAGE)即可得到.
另外還對另一個重要的靜態數組arena_bin_info執行了初始化. 可參考
2.3.2介紹class size的部分.
tcache boot: 分為tcache_boot0和tcache_boot1兩個部分執行.
前者負責tcache所有靜態信息, 包含tcache_bin_info, stack_nelms,
nhbins等的初始化.
後者負責tcache tsd數據的初始化(tcache保存到線程tsd中).
huge boot: 負責huge mutex和huge tree的初始化.
除此之外, 其他重要的初始化還包括分配arenas數組. 注意arenas是一個指向指針數組
的指針, 因此各個arena還需要動態創建. 這裡Je采取了lazy create的方式, 只有當
choose_arena時才可能由choose_arena_hard創建真實的arena實例. 但在malloc_init
中, 首個arena還是會在此時創建, 以保證基本的分配.
相關代碼如下,
arena_t *init_arenas[1];
......
// xf: 此時narenas_total只有1
narenas_total = narenas_auto = 1;
arenas = init_arenas;
memset(arenas, 0, sizeof(arena_t *) * narenas_auto);
// xf: 創建首個arena實例, 保存到臨時數組init_arenas中
arenas_extend(0);
......
// xf: 獲得當前系統核心數量
ncpus = malloc_ncpus();
......
// xf: 默認的narenas為核心數量的4倍
if (opt_narenas == 0) {
if (ncpus > 1)
opt_narenas = ncpus << 2;
else
opt_narenas = 1;
}
// xf: android中max arenas限制為2, 參考mk文件
#if defined(ANDROID_MAX_ARENAS)
if (opt_narenas > ANDROID_MAX_ARENAS)
opt_narenas = ANDROID_MAX_ARENAS;
#endif
narenas_auto = opt_narenas;
......
// xf: 修正narenas_total
narenas_total = narenas_auto;
// xf: 根據total數量, 構造arenas數組, 並置空
arenas = (arena_t **)base_alloc(sizeof(arena_t *) * narenas_total);
......
memset(arenas, 0, sizeof(arena_t *) * narenas_total);
// xf: 將之前的首個arena實例指針保存到新構造的arenas數組中
arenas[0] = init_arenas[0];
----[ 3.3 - Small allocation (Arena)
先介紹最復雜的arena malloc small.
1. 先通過small_size2bin查到bin index(2.4.3節有述).
2. 若對應bin中current run可用則進入下一步, 否則執行4.
3. 由arena_run_reg_alloc在current run中直接分配, 並返回.
4. current run耗盡或不存在, 嘗試從bin中獲得可用run以填充current run,
成功則執行9, 否則進入下一步.
5. 當前bin的run tree中沒有可用run, 轉而從arena的avail-tree上嘗試切割一個
可用run, 成功則執行9, 否則進入下一步.
6. 當前arena沒有可用的空閒run, 構造一個新的chunk以分配new run. 成功則
執行9, 否則進入下一步.
7. chunk分配失敗, 再次查詢arena的avail-tree, 查找可用run. 成功則執行9,
否則進入下一步.
8. alloc run嘗試徹底失敗, 則再次查詢當前bin的run-tree, 嘗試獲取run.
9. 在使用新獲得run之前, 重新檢查當前bin的current run, 如果可用(這裡有
兩種可能, 其一是其他線程可能通過free釋放了多余的region或run, 另一種
可能是搶在當前線程之前已經分配了新run), 則使用其分配, 並返回.
另外, 如果當前手中的new run是空的, 則將其釋放掉. 否則若其地址比current
run更低, 則交換二者, 將舊的current run插回avail-tree.
10. 在new run中分配region, 並返回.
void *
arena_malloc_small(arena_t *arena, size_t size, bool zero)
{
......
// xf: 根據size計算bin index
binind = small_size2bin(size);
assert(binind < NBINS);
bin = &arena->bins[binind];
size = small_bin2size(binind);
malloc_mutex_lock(&bin->lock);
// xf: 如果bin中current run不為空, 且存在空閒region, 則在current
// run中分配. 否則在其他run中分配.
if ((run = bin->runcur) != NULL && run->nfree > 0)
ret = arena_run_reg_alloc(run, &arena_bin_info[binind]);
else
ret = arena_bin_malloc_hard(arena, bin);
// xf: 若返回null, 則分配失敗.
if (ret == NULL) {
malloc_mutex_unlock(&bin->lock);
return (NULL);
}
......
return (ret);
}
------[ 3.3.1 - arena_run_reg_alloc
1. 首先根據bin_info中的靜態信息bitmap_offset計算bitmap基址.
2. 掃描當前run的bitmap, 獲得第一個free region所在的位置.
3. region地址 = run基址 + 第一個region的偏移量 + free region索引 *
region內部size
static inline void *
arena_run_reg_alloc(arena_run_t *run, arena_bin_info_t *bin_info)
{
......
// xf: 計算bitmap基址
bitmap_t *bitmap = (bitmap_t *)((uintptr_t)run +
(uintptr_t)bin_info->bitmap_offset);
......
// xf: 獲得當前run中第一個free region所在bitmap中的位置
regind = bitmap_sfu(bitmap, &bin_info->bitmap_info);
// xf: 計算返回值
ret = (void *)((uintptr_t)run + (uintptr_t)bin_info->reg0_offset +
(uintptr_t)(bin_info->reg_interval * regind));
// xf: free減1
run->nfree--;
......
return (ret);
}
其中bitmap_sfu是執行bitmap遍歷並設置第一個unset bit. 如2.5節所述, bitmap由
多級組成, 遍歷由top level開始循環迭代, 直至bottom level.
JEMALLOC_INLINE size_t
bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo)
{
......
// xf: 找到最高級level, 並計算ffs
i = binfo->nlevels - 1;
g = bitmap[binfo->levels[i].group_offset];
bit = jemalloc_ffsl(g) - 1;
// xf: 循環迭代, 直到level0
while (i > 0) {
i--;
// xf: 根據上一級level的結果, 計算當前level的group
g = bitmap[binfo->levels[i].group_offset + bit];
// xf: 根據當前level group, 計算下一級需要的bit
bit = (bit << LG_BITMAP_GROUP_NBITS) + (jemalloc_ffsl(g) - 1);
}
// xf: 得到level0的bit, 設置bitmap
bitmap_set(bitmap, binfo, bit);
return (bit);
}
bitmap_set同普通bitmap操作沒有什麼區別, 只是在set/unset之後需要反向迭代
更新各個高等級level對應的bit位.
JEMALLOC_INLINE void
bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
{
......
// xf: 計算該bit所在level0中的group
goff = bit >> LG_BITMAP_GROUP_NBITS;
// xf: 得到目標group的值g
gp = &bitmap[goff];
g = *gp;
// xf: 根據remainder, 找到target bit, 並反轉
g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
*gp = g;
......
// xf: 若target bit所在group為0, 則需要更新highlevel的相應bit,
// 是bitmap_sfu的反向操作.
if (g == 0) {
unsigned i;
for (i = 1; i < binfo->nlevels; i++) {
bit = goff;
goff = bit >> LG_BITMAP_GROUP_NBITS;
gp = &bitmap[binfo->levels[i].group_offset + goff];
g = *gp;
assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)));
g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK);
*gp = g;
if (g != 0)
break;
}
}
}
------[ 3.3.2 - arena_bin_malloc_hard
1. 從bin中獲得可用的nonfull run, 這個過程中bin->lock有可能被解鎖.
2. 暫不使用new run, 返回檢查bin->runcur是否重新可用. 如果是,
則直接在其中分配region(其他線程在bin lock解鎖期間可能提前
修改了runcur). 否則, 執行4.
3. 重新檢查1中得到的new run, 如果為空, 則釋放該run.
否則與當前runcur作比較, 若地址低於runcur, 則與其做交換.
將舊的runcur插回run tree. 並返回new rigion.
4. 用new run填充runcur, 並在其中分配region, 返回.
static void *
arena_bin_malloc_hard(arena_t *arena, arena_bin_t *bin)
{
......
// xf: 獲得bin對應的arena_bin_info, 並將current run置空
binind = arena_bin_index(arena, bin);
bin_info = &arena_bin_info[binind];
bin->runcur = NULL;
// xf: 從指定bin中獲得一個可用的run
run = arena_bin_nonfull_run_get(arena, bin);
// 對bin->runcur做重新檢查. 如果可用且未耗盡, 則直接分配.
if (bin->runcur != NULL && bin->runcur->nfree > 0) {
ret = arena_run_reg_alloc(bin->runcur, bin_info);
// xf: 若new run為空, 則將其釋放. 否則重新插入run tree.
if (run != NULL) {
arena_chunk_t *chunk;
chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
if (run->nfree == bin_info->nregs)
arena_dalloc_bin_run(arena, chunk, run, bin);
else
arena_bin_lower_run(arena, chunk, run, bin);
}
return (ret);
}
if (run == NULL)
return (NULL);
// xf: 到這裡在bin->runcur中分配失敗, 用當前新獲得的run填充current run
bin->runcur = run;
// xf: 在new run中分配region
return (arena_run_reg_alloc(bin->runcur, bin_info));
}
------[ 3.3.3 - arena_bin_nonfull_run_get
1. 嘗試在當前run tree中尋找可用run, 成功則返回, 否則進入下一步
2. 解鎖bin lock, 並加鎖arena lock, 嘗試在當前arena中分配new run.
之後重新解鎖arena lock, 並加鎖bin lock. 如果成功則返回, 否則
進入下一步.
3. 分配失敗, 重新在當前run tree中尋找一遍可用run.
static arena_run_t *
arena_bin_nonfull_run_get(arena_t *arena, arena_bin_t *bin)
{
......
// xf: 嘗試從當前run tree中尋找一個可用run, 如果存在就返回
run = arena_bin_nonfull_run_tryget(bin);
if (run != NULL)
return (run);
......
// xf: 打開bin lock, 讓其他線程可以操作當前的bin tree
malloc_mutex_unlock(&bin->lock);
// xf: 鎖住arena lock, 以分配new run
malloc_mutex_lock(&arena->lock);
// xf: 嘗試分配new run
run = arena_run_alloc_small(arena, bin_info->run_size, binind);
if (run != NULL) {
// 初始化new run和bitmap
bitmap_t *bitmap = (bitmap_t *)((uintptr_t)run +
(uintptr_t)bin_info->bitmap_offset);
run->bin = bin;
run->nextind = 0;
run->nfree = bin_info->nregs;
bitmap_init(bitmap, &bin_info->bitmap_info);
}
// xf: 解鎖arena lock
malloc_mutex_unlock(&arena->lock);
// xf: 重新加鎖bin lock
malloc_mutex_lock(&bin->lock);
if (run != NULL) {
......
return (run);
}
// xf: 如果run alloc失敗, 則回過頭重新try get一次(前面解鎖bin lock
// 給了其他線程機會).
run = arena_bin_nonfull_run_tryget(bin);
if (run != NULL)
return (run);
return (NULL);
}
------[ 3.3.4 - Small Run Alloc
1. 從arena avail tree上獲得一個可用run, 並對其切割. 失敗進入下一步.
2. 嘗試給arena分配新的chunk, 以構造new run. 此過程可能會解鎖arena lock.
失敗進入下一步.
3. 其他線程可能在此過程中釋放了某些run, 重新檢查avail-tree, 嘗試獲取run.
static arena_run_t *
arena_run_alloc_small(arena_t *arena, size_t size, size_t binind)
{
......
// xf: 從available tree上嘗試尋找並切割一個合適的run, 並對其初始化
run = arena_run_alloc_small_helper(arena, size, binind);
if (run != NULL)
return (run);
// xf: 當前arena內沒有可用的空閒run, 構造一個新的chunk以分配new run.
chunk = arena_chunk_alloc(arena);
if (chunk != NULL) {
run = (arena_run_t *)((uintptr_t)chunk + (map_bias << LG_PAGE));
arena_run_split_small(arena, run, size, binind);
return (run);
}
// xf: 重新檢查arena avail-tree.
return (arena_run_alloc_small_helper(arena, size, binind));
}
static arena_run_t *
arena_run_alloc_small_helper(arena_t *arena, size_t size, size_t binind)
{
......
// xf: 在arena的available tree中尋找一個大於等於size大小的最小run
key = (arena_chunk_map_t *)(size | CHUNK_MAP_KEY);
mapelm = arena_avail_tree_nsearch(&arena->runs_avail, key);
if (mapelm != NULL) {
arena_chunk_t *run_chunk = CHUNK_ADDR2BASE(mapelm);
size_t pageind = arena_mapelm_to_pageind(mapelm);
// xf: 計算候選run的地址
run = (arena_run_t *)((uintptr_t)run_chunk + (pageind <<
LG_PAGE));
// xf: 根據分配需求, 切割候選run
arena_run_split_small(arena, run, size, binind);
return (run);
}
return (NULL);
}
切割small run主要分為4步,
1. 將候選run的arena_chunk_map_t節點從avail-tree上摘除.
2. 根據節點儲存的原始page信息, 以及need pages信息, 切割該run.
3. 更新remainder節點信息(只需更新首尾page), 重新插入avail-tree.
4. 設置切割後new run所有page對應的map節點信息(根據2.3.3節所述).
static void
arena_run_split_small(arena_t *arena, arena_run_t *run, size_t size,
size_t binind)
{
......
// xf: 獲取目標run的dirty flag
chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(run);
run_ind = (unsigned)(((uintptr_t)run - (uintptr_t)chunk) >> LG_PAGE);
flag_dirty = arena_mapbits_dirty_get(chunk, run_ind);
need_pages = (size >> LG_PAGE);
// xf: 1. 將候選run從available tree上摘除
// 2. 根據need pages對候選run進行切割
// 3. 將remainder重新插入available tree
arena_run_split_remove(arena, chunk, run_ind, flag_dirty, need_pages);
// xf: 設置剛剛被split後的run的第一個page
arena_mapbits_small_set(chunk, run_ind, 0, binind, flag_dirty);
......
// xf: 依次設置run中的其他page, run index依次遞增
for (i = 1; i < need_pages - 1; i++) {
arena_mapbits_small_set(chunk, run_ind+i, i, binind, 0);
.......
}
// xf: 設置run中的最後一個page
arena_mapbits_small_set(chunk, run_ind+need_pages-1, need_pages-1,
binind, flag_dirty);
......
}
------[ 3.3.5 - Chunk Alloc
arena獲取chunk一般有兩個途徑. 其一是通過內部的spare指針. 該指針緩存了最近
一次chunk被釋放的記錄. 因此該方式速度很快. 另一種更加常規, 通過內部分配函
數分配, 最終將由chunk_alloc_core執行. 但在Je的設計中, 執行arena chunk的分
配器是可定制的, 你可以替換任何第三方chunk分配器. 這裡僅討論默認情況.
Je在chunk_alloc_core中同傳統分配器如Dl有較大區別. 通常情況下, 從系統獲取
內存無非是morecore或mmap兩種方式. Dl中按照先morecore->mmap的順序, 而Je更
為靈活, 具體的順序由dss_prec_t決定.
該類型是一個枚舉, 定義如下,
typedef enum {
dss_prec_disabled = 0,
dss_prec_primary = 1,
dss_prec_secondary = 2,
dss_prec_limit = 3
} dss_prec_t;
這裡dss和morecore含義是相同的. primary表示優先dss, secondary則優先mmap.
Je默認使用後者.
實際分配時, 無論采用哪種策略, 都會優先執行chunk_recycle, 再執行chunk
alloc, 如下,
static void *
chunk_alloc_core(size_t size, size_t alignment, bool base, bool *zero,
dss_prec_t dss_prec)
{
void *ret;
if (have_dss && dss_prec == dss_prec_primary) {
if ((ret = chunk_recycle(&chunks_szad_dss, &chunks_ad_dss, size,
alignment, base, zero)) != NULL)
return (ret);
if ((ret = chunk_alloc_dss(size, alignment, zero)) != NULL)
return (ret);
}
if ((ret = chunk_recycle(&chunks_szad_mmap, &chunks_ad_mmap, size,
alignment, base, zero)) != NULL)
return (ret);
if ((ret = chunk_alloc_mmap(size, alignment, zero)) != NULL)
return (ret);
if (have_dss && dss_prec == dss_prec_secondary) {
if ((ret = chunk_recycle(&chunks_szad_dss, &chunks_ad_dss, size,
alignment, base, zero)) != NULL)
return (ret);
if ((ret = chunk_alloc_dss(size, alignment, zero)) != NULL)
return (ret);
}
return (NULL);
}
所謂chunk recycle是在alloc chunk之前, 優先在廢棄的chunk tree上搜索可用chunk,
並分配base node以儲存meta data的過程. 好處是其一可以加快分配速度, 其二是使
空間分配更加緊湊, 並節省內存.
在Je中存在4棵全局的rb tree, 分別為,
static extent_tree_t chunks_szad_mmap; static extent_tree_t chunks_ad_mmap; static extent_tree_t chunks_szad_dss; static extent_tree_t chunks_ad_dss;
它們分別對應mmap和dss方式. 當一個chunk或huge region被釋放後, 將收集到
這4棵tree中. szad和ad在內容上並無本質區別, 只是檢索方式不一樣. 前者采用
先size後address的方式, 後者則是純address的檢索.
recycle算法概括如下,
1. 檢查base標志, 如果為真則直接返回, 否則進入下一步.
開始的檢查是必要的, 因為recycle過程中可能會創建新的extent node, 要求
調用base allocator分配. 另一方面, base alloc可能因為耗盡的原因而反過
來調用chunk alloc. 如此將導致dead loop.
2. 根據alignment計算分配大小, 並在szad tree(mmap還是dss需要上一級決定)上
尋找一個大於等於alloc size的最小node.
3. chunk tree上的node未必對齊到alignment上, 將地址對齊, 之後將得到leadsize
和trailsize.
4. 將原node從chunk tree上remove. 若leadsize不為0, 則將其作為新的chunk重新
insert回chunk tree. trailsize不為0的情況亦然. 若leadsize和trailsize同時
不為0, 則通過base_node_alloc為trailsize生成新的node並插入. 若base alloc
失敗, 則整個新分配的region都要銷毀.
5. 若leadsize和trailsize都為0, 則將node(注意僅僅是節點)釋放. 返回對齊後的
chunk地址.
static void *
chunk_recycle(extent_tree_t *chunks_szad, extent_tree_t *chunks_ad, size_t size,
size_t alignment, bool base, bool *zero)
{
......
// xf: 由於構造extent_node時可能因為內存不足的原因, 同樣需要構造chunk,
// 這樣就導致recursively dead loop. 因此依靠base標志, 區分普通alloc和
// base node alloc. 如果是base alloc, 則立即返回.
if (base) {
return (NULL);
}
// xf: 計算分配大小
alloc_size = size + alignment - chunksize;
......
key.addr = NULL;
key.size = alloc_size;
// xf: 在指定的szad tree上尋找大於等於alloc size的最小可用node
malloc_mutex_lock(&chunks_mtx);
node = extent_tree_szad_nsearch(chunks_szad, &key);
......
// xf: 將候選節點基址對齊到分配邊界上, 並計算leadsize, trailsize
// 以及返回地址.
leadsize = ALIGNMENT_CEILING((uintptr_t)node->addr, alignment) -
(uintptr_t)node->addr;
trailsize = node->size - leadsize - size;
ret = (void *)((uintptr_t)node->addr + leadsize);
......
// xf: 將原node從szad/ad tree上移除
extent_tree_szad_remove(chunks_szad, node);
extent_tree_ad_remove(chunks_ad, node);
// xf: 如果存在leadsize, 則將前面多余部分作為一個chunk重新插入
// szad/ad tree上.
if (leadsize != 0) {
node->size = leadsize;
extent_tree_szad_insert(chunks_szad, node);
extent_tree_ad_insert(chunks_ad, node);
node = NULL;
}
// xf: 同樣如果存在trailsize, 也將後面的多余部分插入.
if (trailsize != 0) {
// xf: 如果leadsize不為0, 這時原來的extent_node已經被用過了,
// 則必須為trailsize部分重新分配新的extent_node
if (node == NULL) {
malloc_mutex_unlock(&chunks_mtx);
node = base_node_alloc();
......
}
// xf: 計算trail chunk, 並插入
node->addr = (void *)((uintptr_t)(ret) + size);
node->size = trailsize;
node->zeroed = zeroed;
extent_tree_szad_insert(chunks_szad, node);
extent_tree_ad_insert(chunks_ad, node);
node = NULL;
}
malloc_mutex_unlock(&chunks_mtx);
// xf: leadsize & basesize都不存在, 將node釋放.
if (node != NULL)
base_node_dalloc(node);
......
return (ret);
}
常規分配方式先來看dss. 由於dss是與當前進程的brk指針相關的, 任何線程(包括可能
不通過Je執行分配的線程)都有權修改該指針值. 因此, 首先要把dss指針調整到對齊在
chunksize邊界的位置, 否則很多與chunk相關的計算都會失效. 接下來, 還要做第二次
調整對齊到外界請求的alignment邊界. 在此基礎上再進行分配.
與dss分配相關的變量如下,
static malloc_mutex_t dss_mtx; static void *dss_base; static void *dss_prev; static void *dss_max;
dss_mtx: dss lock. 注意其並不能起到保護dss指針的作用, 因為brk是一個系統資源.
該lock保護的是dss_prev, dss_max指針.
dss_base: 只在chunk_dss_boot時更新一次. 主要用作識別chunk在線性地址空間中所
處的位置, 與mmap作出區別.
dss_prev: 當前dss指針, 是系統brk指針的副本, 值等於-1代表dss耗盡.
dss_max: 當前dss區域上限.
dss alloc算法如下,
1. 獲取brk指針, 更新到dss_max.
2. 將dss_max對齊到chunksize邊界上, 計算padding大小gap_size
3. 再將dss_max對齊到aligment邊界上, 得到cpad_size
4. 計算需要分配的大小, 並嘗試sbrk
incr = gap_size + cpad_size + size
5. 分配成功, 檢查cpad是否非0, 是則將這部分重新回收. 而gap_size部分因為
不可用則被廢棄.
6. 如果分配失敗, 則檢查dss是否耗盡, 如果沒有則返回1重新嘗試. 否則返回.
示意圖,
chunk_base cpad ret dss_next
| | | |
v v v v
+--------+----------+-----------+------ ---+
| used | gap_size | cpad_size | size ... |
+--------+----------+-----------+------ ---+
|<------------- incr -------------->|
^ ^ ^
| | |
dss_max chunk_base + +-- chunk_base +
chunk_size alignment
源碼注釋,
void *
chunk_alloc_dss(size_t size, size_t alignment, bool *zero)
{
......
// xf: dss是否耗盡
malloc_mutex_lock(&dss_mtx);
if (dss_prev != (void *)-1) {
......
do {
// xf: 獲取當前dss指針
dss_max = chunk_dss_sbrk(0);
// xf: 計算對齊到chunk size邊界需要的padding大小
gap_size = (chunksize - CHUNK_ADDR2OFFSET(dss_max)) &
chunksize_mask;
// xf: 對齊到chunk邊界的chunk起始地址
cpad = (void *)((uintptr_t)dss_max + gap_size);
// xf: 對齊到alignment邊界的起始地址
ret = (void *)ALIGNMENT_CEILING((uintptr_t)dss_max,
alignment);
cpad_size = (uintptr_t)ret - (uintptr_t)cpad;
// xf: dss_max分配後的更新地址
dss_next = (void *)((uintptr_t)ret + size);
......
incr = gap_size + cpad_size + size;
// xf: 從dss分配
dss_prev = chunk_dss_sbrk(incr);
if (dss_prev == dss_max) {
dss_max = dss_next;
malloc_mutex_unlock(&dss_mtx);
// xf: 如果ret和cpad對齊不在同一個位置, 則將cpad開始
// cpad_size大小的內存回收到szad/ad tree中. 而以之前
// dss起始的gap_size大小內存由於本身並非對齊到
// chunk_size, 則被廢棄.
if (cpad_size != 0)
chunk_unmap(cpad, cpad_size);
......
return (ret);
}
} while (dss_prev != (void *)-1); // xf: 反復嘗試直至dss耗盡
}
malloc_mutex_unlock(&dss_mtx);
return (NULL);
}
最後介紹chunk_alloc_mmap. 同dss方式類似, mmap也存在對齊的問題. 由於系統mmap
調用無法指定alignment, 因此Je實現了一個可以實現對齊但速度更慢的mmap slow方式.
作為彌補, 在chunk alloc mmap時先嘗試依照普通方式mmap, 如果返回值恰好滿足對齊
要求則直接返回(多數情況下是可行的). 否則將返回值munmap, 再調用mmap slow.
void *
chunk_alloc_mmap(size_t size, size_t alignment, bool *zero)
{
......
ret = pages_map(NULL, size);
if (ret == NULL)
return (NULL);
offset = ALIGNMENT_ADDR2OFFSET(ret, alignment);
if (offset != 0) {
pages_unmap(ret, size);
return (chunk_alloc_mmap_slow(size, alignment, zero));
}
......
return (ret);
}
mmap slow通過事先分配超量size, 對齊後再執行trim, 去掉前後余量實現mmap對齊.
page trim通過兩次munmap將leadsize和trailsize部分分別釋放. 因此理論上, mmap
slow需要最多三次munmap.
|<-------------alloc_size---------->|
+-----------+----- --+------------+
| lead_size | size... | trail_size |
+-----------+----- --+------------+
^ ^
| |
pages ret(alignment)
static void *
chunk_alloc_mmap_slow(size_t size, size_t alignment, bool *zero)
{
......
alloc_size = size + alignment - PAGE;
if (alloc_size < size)
return (NULL);
do {
pages = pages_map(NULL, alloc_size);
if (pages == NULL)
return (NULL);
leadsize = ALIGNMENT_CEILING((uintptr_t)pages, alignment) -
(uintptr_t)pages;
ret = pages_trim(pages, alloc_size, leadsize, size);
} while (ret == NULL);
......
return (ret);
}
static void *
pages_trim(void *addr, size_t alloc_size, size_t leadsize, size_t size)
{
void *ret = (void *)((uintptr_t)addr + leadsize);
......
{
size_t trailsize = alloc_size - leadsize - size;
if (leadsize != 0)
pages_unmap(addr, leadsize);
if (trailsize != 0)
pages_unmap((void *)((uintptr_t)ret + size), trailsize);
return (ret);
}
}
----[ 3.4 - Small allocation (tcache)
tcache內分配按照先easy後hard的方式. easy方式直接從tcache bin的avail-stack
中獲得可用region. 如果tbin耗盡, 使用hard方式, 先refill avail-stack, 再執行
easy分配.
JEMALLOC_ALWAYS_INLINE void *
tcache_alloc_small(tcache_t *tcache, size_t size, bool zero)
{
......
// xf: 先從tcache bin嘗試分配
ret = tcache_alloc_easy(tbin);
// xf: 如果嘗試失敗, 則refill tcache bin, 並嘗試分配
if (ret == NULL) {
ret = tcache_alloc_small_hard(tcache, tbin, binind);
if (ret == NULL)
return (NULL);
}
......
// xf: 執行tcache event
tcache_event(tcache);
return (ret);
}
JEMALLOC_ALWAYS_INLINE void *
tcache_alloc_easy(tcache_bin_t *tbin)
{
void *ret;
// xf: 如果tcache bin耗盡, 更新水線為-1
if (tbin->ncached == 0) {
tbin->low_water = -1;
return (NULL);
}
// xf: pop棧頂的region, 如果需要更新水線
tbin->ncached--;
if ((int)tbin->ncached < tbin->low_water)
tbin->low_water = tbin->ncached;
ret = tbin->avail[tbin->ncached];
return (ret);
}
void *
tcache_alloc_small_hard(tcache_t *tcache, tcache_bin_t *tbin, size_t binind)
{
void *ret;
arena_tcache_fill_small(tcache->arena, tbin, binind,
config_prof ? tcache->prof_accumbytes : 0);
if (config_prof)
tcache->prof_accumbytes = 0;
ret = tcache_alloc_easy(tbin);
return (ret);
}
tcache fill同普通的arena bin分配類似. 首先, 獲得與tbin相同index的arena bin.
之後確定fill值, 該數值與2.7節介紹的lg_fill_div有關. 如果arena run的runcur
可用則直接分配並push stack, 否則arena_bin_malloc_hard分配region. push後的
順序按照從低到高排列, 低地址的region更靠近棧頂位置.
void
arena_tcache_fill_small(arena_t *arena, tcache_bin_t *tbin, size_t binind,
uint64_t prof_accumbytes)
{
......
// xf: 得到與tbin同index的arena bin
bin = &arena->bins[binind];
malloc_mutex_lock(&bin->lock);
// xf: tbin的充滿度與lg_fill_div相關
for (i = 0, nfill = (tcache_bin_info[binind].ncached_max >>
tbin->lg_fill_div); i < nfill; i++) {
// xf: 如果current run可用, 則從中分配
if ((run = bin->runcur) != NULL && run->nfree > 0)
ptr = arena_run_reg_alloc(run, &arena_bin_info[binind]);
else // xf: current run耗盡, 則從bin中查找其他run分配
ptr = arena_bin_malloc_hard(arena, bin);
if (ptr == NULL)
break;
......
// xf: 低地址region優先放入棧頂
tbin->avail[nfill - 1 - i] = ptr;
}
......
malloc_mutex_unlock(&bin->lock);
// xf: 更新ncached
tbin->ncached = i;
}
另外, 如2.7節所述, tcache在每次分配和釋放後都會更新ev_cnt計數器. 當計數周期
達到TCACHE_GC_INCR時, 就會啟動tcache gc. gc過程中會清理相當於low_water 3/4
數量的region, 並根據當前的low_water和lg_fill_div動態調整下一次refill時,
tbin的充滿度.
void
tcache_bin_flush_small(tcache_bin_t *tbin, size_t binind, unsigned rem,
tcache_t *tcache)
{
......
// xf: 循環scan, 直到nflush為空.
// 因為avail-stack中的region可能來自不同arena, 因此需要多次scan.
// 每次scan將不同arena的region移動到棧頂, 留到下一輪scan時清理.
for (nflush = tbin->ncached - rem; nflush > 0; nflush = ndeferred) {
// xf: 獲得棧頂region所屬的arena和arena bin
arena_chunk_t *chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(
tbin->avail[0]);
arena_t *arena = chunk->arena;
arena_bin_t *bin = &arena->bins[binind];
......
// xf: 鎖住棧頂region的arena bin
malloc_mutex_lock(&bin->lock);
......
// xf: ndefered代表所屬不同arena的region被搬移的位置, 默認從0開始.
// 本意是隨著scan進行, nflush逐漸遞增, nflush之前的位置空缺出來.
// 當scan到不同arena region時, 將其指針移動到nflush前面的空缺中,
// 留到下一輪scan, nflush重新開始. 直到ndefered和nflush重新為0.
ndeferred = 0;
for (i = 0; i < nflush; i++) {
ptr = tbin->avail[i];
chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
// xf: 如果scan的region與棧頂region位於同一arena, 則釋放,
// 否則移動到ndefered標注的位置, 留到後面scan.
if (chunk->arena == arena) {
size_t pageind = ((uintptr_t)ptr -
(uintptr_t)chunk) >> LG_PAGE;
arena_chunk_map_t *mapelm =
arena_mapp_get(chunk, pageind);
......
// xf: 釋放多余region
arena_dalloc_bin_locked(arena, chunk, ptr,
mapelm);
} else {
tbin->avail[ndeferred] = ptr;
ndeferred++;
}
}
malloc_mutex_unlock(&bin->lock);
}
......
// xf: 將remainder regions指針移動到棧頂位置, 完成gc過程
memmove(tbin->avail, &tbin->avail[tbin->ncached - rem],
rem * sizeof(void *));
// xf: 修正ncached以及low_water
tbin->ncached = rem;
if ((int)tbin->ncached < tbin->low_water)
tbin->low_water = tbin->ncached;
}
----[ 3.5 - Large allocation
Arena上的large alloc同small相比除了省去arena bin的部分之外, 並無本質區別.
基本算法如下,
1. 把請求大小對齊到page size上, 直接從avail-tree上尋找first-best-fit runs.
如果成功, 則根據請求大小切割內存. 切割過程也同切割small run類似, 區別在
之後對chunk map的初始化不同. chunk map細節可回顧2.3.3. 如果失敗, 則進入
下一步.
2. 沒有可用runs, 嘗試創建new chunk, 成功同樣切割run, 失敗進入下一步.
3. 再次嘗試從avail-tree上尋找可用runs, 並返回.
同上面的過程可以看出, 所謂large region分配相當於small run的分配. 區別僅
在於chunk map信息不同.
Tcache上的large alloc同樣按照先easy後hard的順序. 盡管常規arena上的分配不
存在large bin, 但在tcache中卻存在large tbin, 因此仍然是先查找avail-stack.
如果tbin中找不到, 就會向arena申請large runs. 這裡與small alloc的區別在不
執行tbin refill, 因為考慮到過多large region的占用量問題. large tbin僅在
tcache_dalloc_large的時候才負責收集region. 當tcache已滿或GC周期到時執行
tcache gc.
----[ 3.6 - Huge allocation
Huge alloc相對於前面就更加簡單. 因為對於Je而言, huge region和chunk是等同的,
這在前面有過敘述. Huge alloc就是調用chunk alloc, 並將extent_node記錄在huge
tree上.
void *
huge_palloc(arena_t *arena, size_t size, size_t alignment, bool zero)
{
void *ret;
size_t csize;
extent_node_t *node;
bool is_zeroed;
// xf: huge alloc對齊到chunksize
csize = CHUNK_CEILING(size);
......
// xf: create extent node以記錄huge region
node = base_node_alloc();
......
arena = choose_arena(arena);
// xf: 調用chunk alloc分配
ret = arena_chunk_alloc_huge(arena, csize, alignment, &is_zeroed);
// xf: 失敗則清除extent node
if (ret == NULL) {
base_node_dalloc(node);
return (NULL);
}
node->addr = ret;
node->size = csize;
node->arena = arena;
// xf: 插入huge tree上
malloc_mutex_lock(&huge_mtx);
extent_tree_ad_insert(&huge, node);
malloc_mutex_unlock(&huge_mtx);
......
return (ret);
}
--[ 4 - Deallocation
----[ 4.1 - Overview
釋放同分配過程相反, 按照一個從ptr -> run -> bin -> chunk -> arena的路徑.
但因為涉及page合並和purge, 實現更為復雜.
dalloc的入口從je_free -> ifree -> iqalloc -> iqalloct -> idalloct.
對dalloc的分析從idalloct開始. 代碼如下,
JEMALLOC_ALWAYS_INLINE void
idalloct(void *ptr, bool try_tcache)
{
......
// xf: 獲得被釋放地址所在的chunk
chunk = (arena_chunk_t *)CHUNK_ADDR2BASE(ptr);
if (chunk != ptr)
arena_dalloc(chunk, ptr, try_tcache);
else
huge_dalloc(ptr);
}
首先會檢測被釋放指針ptr所在chunk的首地址與ptr是否一致, 如果是, 則一定為
huge region, 否則為small/large. 從這裡分為arena和huge兩條線.
再看一下arena_dalloc,
JEMALLOC_ALWAYS_INLINE void
arena_dalloc(arena_chunk_t *chunk, void *ptr, bool try_tcache)
{
......
// xf: 得到頁面mapbits
mapbits = arena_mapbits_get(chunk, pageind);
if ((mapbits & CHUNK_MAP_LARGE) == 0) {
if (try_tcache && (tcache = tcache_get(false)) != NULL) {
// xf: ptr所在tcache的index
binind = arena_ptr_small_binind_get(ptr, mapbits);
tcache_dalloc_small(tcache, ptr, binind);
} else
arena_dalloc_small(chunk->arena, chunk, ptr, pageind);
} else {
size_t size = arena_mapbits_large_size_get(chunk, pageind);
if (try_tcache && size <= tcache_maxclass && (tcache =
tcache_get(false)) != NULL) {
tcache_dalloc_large(tcache, ptr, size);
} else
arena_dalloc_large(chunk->arena, chunk, ptr);
}
}
這裡通過得到ptr所在page的mapbits, 判斷其來自於small還是large. 然後再
分別作處理.
因此, 在dalloc一開始基本上分成了small/large/huge三條路線執行. 事實上,
結合前面的知識, large/huge可以看作run和chunk的特例. 所以, 這三條dalloc
路線最終會匯到一起, 只需要搞清楚其中最為復雜的small region dalloc
就可以了.
無論small/large region, 都會先嘗試釋放回tcache, 不管其是否從tache中分配
而來. 所謂tcache dalloc只不過是將region記錄在tbin中, 並不算真正的釋放.
除非兩種情況, 一是如果當前線程tbin已滿, 會直接執行一次tbin flush, 釋放出
部分tbin空間. 二是如果tcache_event觸發發了tache gc, 也會執行flush. 兩者的
區別在於, 前者會回收指定tbin 1/2的空間, 而後者則釋放next_gc_bin相當於3/4
low water數量的空間.
JEMALLOC_ALWAYS_INLINE void
tcache_dalloc_small(tcache_t *tcache, void *ptr, size_t binind)
{
......
tbin = &tcache->tbins[binind];
tbin_info = &tcache_bin_info[binind];
// xf: 如果當前tbin已滿, 則執行flush清理tbin
if (tbin->ncached == tbin_info->ncached_max) {
tcache_bin_flush_small(tbin, binind, (tbin_info->ncached_max >>
1), tcache);
}
// xf: 將被釋放的ptr重新push進tbin
tbin->avail[tbin->ncached] = ptr;
tbin->ncached++;
tcache_event(tcache);
}
tcache gc和tcache flush在2.7和3.4節中已經介紹, 不再贅述.
----[ 4.2 - arena_dalloc_bin
small region dalloc的第一步是嘗試將region返還給所屬的bin. 首要的步驟就是
根據用戶傳入的ptr推算出其所在run的地址.
run addr = chunk base + run page offset << LG_PAGE
而run page offset根據2.3.3小節的說明, 可以通過ptr所在page的mapbits獲得.
run page offset = ptr page index - ptr page offset
得到run後就進一步拿到所屬的bin, 接著對bin加鎖並回收, 如下,
void
arena_dalloc_bin(arena_t *arena, arena_chunk_t *chunk, void *ptr,
size_t pageind, arena_chunk_map_t *mapelm)
{
......
// xf: 計算ptr所在run地址.
run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)((pageind -
arena_mapbits_small_runind_get(chunk, pageind)) << LG_PAGE));
bin = run->bin;
malloc_mutex_lock(&bin->lock);
arena_dalloc_bin_locked(arena, chunk, ptr, mapelm);
malloc_mutex_unlock(&bin->lock);
}
lock的內容無非是將region在run內部的bitmap上標記為可用. bitmap unset的
過程此處省略, 請參考3.3.1小節中分配算法的解釋. 與tcache dalloc類似,
通常情況下region並不會真正釋放. 但如果run內部全部為空閒region, 則會
進一步觸發run的釋放.
void
arena_dalloc_bin_locked(arena_t *arena, arena_chunk_t *chunk, void *ptr,
arena_chunk_map_t *mapelm)
{
......
// xf: 通過run回收region, 在bitmap上重新標記region可用.
arena_run_reg_dalloc(run, ptr);
// xf: 如果其所在run完全free, 則嘗試釋放該run.
// 如果所在run處在將滿狀態(因為剛剛的釋放騰出一個region的空間),
// 則根據地址高低優先將其交換到current run的位置(MRU).
if (run->nfree == bin_info->nregs) {
arena_dissociate_bin_run(chunk, run, bin);
arena_dalloc_bin_run(arena, chunk, run, bin);
} else if (run->nfree == 1 && run != bin->runcur)
arena_bin_lower_run(arena, chunk, run, bin);
......
}
此外還有一種情況是, 如果原先run本來是滿的, 因為前面的釋放多出一個空閒位置,
就會嘗試與current run交換位置. 若當前run比current run地址更低, 會替代後者
並成為新的current run, 這樣的好處顯然可以保證低地址的內存更緊實.
static void
arena_bin_lower_run(arena_t *arena, arena_chunk_t *chunk, arena_run_t *run,
arena_bin_t *bin)
{
if ((uintptr_t)run < (uintptr_t)bin->runcur) {
if (bin->runcur->nfree > 0)
arena_bin_runs_insert(bin, bin->runcur);
bin->runcur = run;
if (config_stats)
bin->stats.reruns++;
} else
arena_bin_runs_insert(bin, run);
}
通常情況下, 至此一個small region就釋放完畢了, 准確的說是回收了. 但如前面
所說, 若整個run都為空閒region, 則進入run dalloc. 這是一個比較復雜的過程.
----[ 4.3 - small run dalloc
一個non-full的small run被記錄在bin內的run tree上, 因此要移除它, 首先要移除
其在run tree中的信息, 即arena_dissociate_bin_run.
static void
arena_dissociate_bin_run(arena_chunk_t *chunk, arena_run_t *run,
arena_bin_t *bin)
{
// xf: 如果當前run為current run, 清除runcur. 否則, 從run tree上remove.
if (run == bin->runcur)
bin->runcur = NULL;
else {
......
if (bin_info->nregs != 1) {
arena_bin_runs_remove(bin, run);
}
}
}
接下來要通過arena_dalloc_bin_run()正式釋放run, 由於過程稍復雜, 這裡先給出整個
算法的梗概,
1. 計算nextind region所在page的index. 所謂nextind是run內部clean-dirty region
的邊界. 如果內部存在clean pages則執行下一步, 否則執行3.
2. 將原始的small run轉化成large run, 之後根據上一步得到的nextind將run切割成
dirty和clean兩部分, 且單獨釋放掉clean部分.
3. 將待remove的run pages標記為unalloc. 且根據傳入的dirty和cleaned兩個hint
決定標記後的page mapbits的dirty flag.
4. 檢查unalloc後的run pages是否可以前後合並. 合並的標准是,
1) 不超過chunk范圍
2) 前後毗鄰的page同樣為unalloc
3) 前後毗鄰page的dirty flag與run pages相同.
5. 將合並後(也可能沒合並)的unalloc run插入avail-tree.
6. 檢查如果unalloc run的大小等於chunk size, 則將chunk釋放掉.
7. 如果之前釋放run pages為dirty, 則檢查當前arena內部的dirty-active pages比例.
若dirty數量超過了active的1/8(Android這裡的標准有所不同), 則啟動arena purge.
否則直接返回.
8. 計算當前arena可以清理的dirty pages數量npurgatory.
9. 從dirty tree上依次取出dirty chunk, 並檢查內部的unalloc dirty pages, 將其
重新分配為large pages, 並插入到臨時的queue中.
10. 對臨時隊列中的dirty pages執行purge, 返回值為unzeroed標記. 再將purged pages
的unzeroed標記設置一遍.
11. 最後對所有purged pages重新執行一遍dalloc run操作, 將其重新釋放回avail-tree.
可以看到, 釋放run本質上是將其回收至avail-tree. 但額外的dirty page機制卻增加了
整個算法的復雜程度. 原因就在於, Je使用了不同以往的內存釋放方式.
在Dl這樣的經典分配器中, 系統內存回收方式更加"古板". 比如在heap區需要top-most
space存在大於某個threshold的連續free空間時才能進行auto-trimming. 而mmap區則
更要等到某個segment全部空閒才能執行munmap. 這對於回收系統內存是極為不利的,
因為條件過於嚴格.
而Je使用了更為聰明的方式, 並不會直接交還系統內存, 而是通過madvise暫時釋放掉
頁面與物理頁面之間的映射. 本質上這同sbrk/munmap之類的調用要達到的目的是類似的,
只不過從進程內部的角度看, 該地址仍然被占用. 但Je對這些使用過的地址都詳細做了
記錄, 因此再分配時可以recycle, 並不會導致對線性地址無休止的開采.
另外, 為了提高對已釋放page的利用率, Je將unalloc pages用dirty flag(注意, 這裡
同page replacement中的含義不同)做了標記(參考2.3.3節中chunkmapbits). 所有pages
被分成active, dirty和clean三種. dirty pages表示曾經使用過, 且仍可能關聯著物理
頁面, recycle速度較快. 而clean則代表尚未使用, 或已經通過purge釋放了物理頁面,
較前者速度慢. 顯然, 需要一種內置算法來保持三種page的動態平衡, 以兼顧分配速度
和內存占用量. 如果當前dirty pages數量超過了active pages數量的
1/2^opt_lg_dirty_mult, 就會啟動arena_purge(). 這個值默認是1/8, 如下,
static inline void
arena_maybe_purge(arena_t *arena)
{
......
// xf: 如果當前dirty pages全部在執行purging, 則直接返回.
if (arena->ndirty <= arena->npurgatory)
return;
// xf: 檢查purageable pages是否超出active-dirty比率, 超出則
// 執行purge. google在這裡增加了ANDROID_ALWAYS_PURGE開關,
// 打開則總會執行arena_purge(默認是打開的).
#if !defined(ANDROID_ALWAYS_PURGE)
npurgeable = arena->ndirty - arena->npurgatory;
threshold = (arena->nactive >> opt_lg_dirty_mult);
if (npurgeable <= threshold)
return;
#endif
// xf: 執行purge
arena_purge(arena, false);
}
但google顯然希望對dirty pages管理更嚴格一些, 以適應移動設備上內存
偏小的問題. 這裡增加了一個ALWAYS_PURGE的開關, 打開後會強制每次釋放
時都執行arena_purge.
arena_run_dalloc代碼如下,
static void
arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty, bool cleaned)
{
......
// xf: 如果run pages的dirty flag實際讀取為true, 且cleaned不為true,
// 則同樣認為該pages在dalloc後是dirty的, 否則被視為clean(該情況適用於
// chunk purge後, 重新dalloc時, 此時的run pages雖然dirty flag可能為ture,
// 但經過purge後應該修改為clean).
if (cleaned == false && arena_mapbits_dirty_get(chunk, run_ind) != 0)
dirty = true;
flag_dirty = dirty ? CHUNK_MAP_DIRTY : 0;
// xf: 將被remove的run標記為unalloc pages. 前面的判斷如果是dirty, 則pages
// mapbits將帶有dirty flag, 否則將不帶有dirty flag.
if (dirty) {
arena_mapbits_unallocated_set(chunk, run_ind, size,
CHUNK_MAP_DIRTY);
arena_mapbits_unallocated_set(chunk, run_ind+run_pages-1, size,
CHUNK_MAP_DIRTY);
} else {
arena_mapbits_unallocated_set(chunk, run_ind, size,
arena_mapbits_unzeroed_get(chunk, run_ind));
arena_mapbits_unallocated_set(chunk, run_ind+run_pages-1, size,
arena_mapbits_unzeroed_get(chunk, run_ind+run_pages-1));
}
// xf: 嘗試將被remove run與前後unalloc pages 合並.
arena_run_coalesce(arena, chunk, &size, &run_ind, &run_pages,
flag_dirty);
......
// xf: 將執行過合並後的run重新insert到avail-tree
arena_avail_insert(arena, chunk, run_ind, run_pages, true, true);
// xf: 檢查如果合並後的size已經完全unallocated, 則dalloc整個chunk
if (size == arena_maxclass) {
......
arena_chunk_dalloc(arena, chunk);
}
if (dirty)
arena_maybe_purge(arena);
}
coalesce代碼如下,
static void
arena_run_coalesce(arena_t *arena, arena_chunk_t *chunk, size_t *p_size,
size_t *p_run_ind, size_t *p_run_pages, size_t flag_dirty)
{
......
// xf: 嘗試與後面的pages合並
if (run_ind + run_pages < chunk_npages &&
arena_mapbits_allocated_get(chunk, run_ind+run_pages) == 0 &&
arena_mapbits_dirty_get(chunk, run_ind+run_pages) == flag_dirty) {
size_t nrun_size = arena_mapbits_unallocated_size_get(chunk,
run_ind+run_pages);
size_t nrun_pages = nrun_size >> LG_PAGE;
......
// xf: 如果與後面的unalloc pages合並, remove page時後方的adjacent
// hint應為true
arena_avail_remove(arena, chunk, run_ind+run_pages, nrun_pages,
false, true);
size += nrun_size;
run_pages += nrun_pages;
arena_mapbits_unallocated_size_set(chunk, run_ind, size);
arena_mapbits_unallocated_size_set(chunk, run_ind+run_pages-1, size);
}
// xf: 嘗試與前面的pages合並
if (run_ind > map_bias && arena_mapbits_allocated_get(chunk,
run_ind-1) == 0 && arena_mapbits_dirty_get(chunk, run_ind-1) ==
flag_dirty) {
......
}
*p_size = size;
*p_run_ind = run_ind;
*p_run_pages = run_pages;
}
avail-tree remove代碼如下,
static void
arena_avail_remove(arena_t *arena, arena_chunk_t *chunk, size_t pageind,
size_t npages, bool maybe_adjac_pred, bool maybe_adjac_succ)
{
......
// xf: 該調用可能將導致chunk內部的碎片化率改變, 從而影響其在dirty tree
// 中的排序. 因此, 在正式remove之前需要將chunk首先從dirty tree中remove,
// 待更新內部ndirty後, 再將其重新insert回dirty tree.
if (chunk->ndirty != 0)
arena_chunk_dirty_remove(&arena->chunks_dirty, chunk);
// xf: maybe_adjac_pred/succ是外界傳入的hint, 根據該值檢查前後是否存在
// clean-dirty邊界. 若存在邊界, 則remove avail pages後邊界將減1.
if (maybe_adjac_pred && arena_avail_adjac_pred(chunk, pageind))
chunk->nruns_adjac--;
if (maybe_adjac_succ && arena_avail_adjac_succ(chunk, pageind, npages))
chunk->nruns_adjac--;
chunk->nruns_avail--;
......
// xf: 更新arena及chunk中dirty pages統計.
if (arena_mapbits_dirty_get(chunk, pageind) != 0) {
arena->ndirty -= npages;
chunk->ndirty -= npages;
}
// xf: 如果chunk內部dirty不為0, 將其重新insert到arena dirty tree.
if (chunk->ndirty != 0)
arena_chunk_dirty_insert(&arena->chunks_dirty, chunk);
// xf: 從chunk avail-tree中remove掉unalloc pages.
arena_avail_tree_remove(&arena->runs_avail, arena_mapp_get(chunk,
pageind));
}
從avail-tree上remove pages可能會改變當前chunk內部clean-dirty碎片率, 因此
一開始要將其所在chunk從dirty tree上remove, 再從avail-tree上remove pages.
另外, arena_avail_insert()的算法同remove是一樣的, 只是方向相反, 不再贅述.
----[ 4.4 - arena purge
清理arena的方式是按照從小到大的順序遍歷一棵dirty tree, 直到將dirty pages降低
到threshold以下. dirty tree掛載所有dirty chunks, 同其他tree的區別在於它的cmp
函數較特殊, 決定了最終的purging order, 如下,
static inline int
arena_chunk_dirty_comp(arena_chunk_t *a, arena_chunk_t *b)
{
......
if (a == b)
return (0);
{
size_t a_val = (a->nruns_avail - a->nruns_adjac) *
b->nruns_avail;
size_t b_val = (b->nruns_avail - b->nruns_adjac) *
a->nruns_avail;
if (a_val < b_val)
return (1);
if (a_val > b_val)
return (-1);
}
{
uintptr_t a_chunk = (uintptr_t)a;
uintptr_t b_chunk = (uintptr_t)b;
int ret = ((a_chunk > b_chunk) - (a_chunk < b_chunk));
if (a->nruns_adjac == 0) {
assert(b->nruns_adjac == 0);
ret = -ret;
}
return (ret);
}
}
Je在這裡給出的算法是這樣的,
1. 首先排除short cut, 即a和b相同的特例.
2. 計算a, b的fragmentation, 該數值越高, 相應的在dirty tree上就越靠前.
其計算方法為,
當前平均avail run大小 所有avail run數量 - 邊界數量
--------------------- = -----------------------------
去碎片後的平均大小 所有avail run數量
注意, 這個fragment不是通常意義理解的碎片. 這裡指由於clean-dirty
邊界形成的所謂碎片, 並且是可以通過purge清除掉的, 如圖,
nruns_adjac = 2
+--------+----------+--------+-------+---------+----------+--------+-----
| dirty | clean | | clean | dirty | | dirty | ...
+--------+----------+--------+-------+---------+----------+--------+-----
^ ^
| |
+--adjac #0 +--adjac #1
3. 當a, b的fragmentation相同時, 同通常的方法類似, 按地址大小排序. 但若
nruns_adjac為0, 即不存在clean-dirty邊界時, 反而會將低地址chunk排到後面.
因為adjac為0的chunk再利用價值是比較高的, 所以放到後面可以增加其在purge
中的幸存幾率, 從而提升recycle效率.
這裡需要說明的是, Je這個cmp函數個人覺得似乎有問題, 實際跟蹤代碼也發現其並
不能更優先purge高碎片率的chunk. 但與其本人證實並未得到信服的說明. 但這套
算法僅僅在3.x版本中有效, 在最新的4.x中則完全拋棄了現有的回收算法.
purge代碼如下,
static void
arena_purge(arena_t *arena, bool all)
{
......
// xf: 計算purgeable pages, 結果加入到npurgatory信息中.
npurgatory = arena_compute_npurgatory(arena, all);
arena->npurgatory += npurgatory;
// xf: 從dirty chunk tree上逐chunk執行purge, 直到期望值npurgatory為0
while (npurgatory > 0) {
......
chunk = arena_chunk_dirty_first(&arena->chunks_dirty);
// xf: traversal結束, 當前線程無法完成purge任務, 返回.
if (chunk == NULL) {
arena->npurgatory -= npurgatory;
return;
}
npurgeable = chunk->ndirty;
......
// xf: 如果當前chunk中purgeable大於前期計算的purgatory,
// 且其clean-dirty碎片為0, 則讓當前線程負責purge所有prgeable pages.
// 原因是為了盡可能避免避免多個線程對該chunk的purge競爭.
if (npurgeable > npurgatory && chunk->nruns_adjac == 0) {
arena->npurgatory += npurgeable - npurgatory;
npurgatory = npurgeable;
}
arena->npurgatory -= npurgeable;
npurgatory -= npurgeable;
npurged = arena_chunk_purge(arena, chunk, all);
// xf: 計算purge期望值npurgatory和實際purge值npurged差值
nunpurged = npurgeable - npurged;
arena->npurgatory += nunpurged;
npurgatory += nunpurged;
}
}
chunk purge如下,
static inline size_t
arena_chunk_purge(arena_t *arena, arena_chunk_t *chunk, bool all)
{
......
if (chunk == arena->spare) {
......
arena_chunk_alloc(arena);
}
......
// xf: 為了減小arena purge時arena lock的暫停時間, 先將所有滿足
// 需求的unalloc dirty pages重新"alloc"並保存, 待purge結束再重新
// 釋放回avail-tree.
arena_chunk_stash_dirty(arena, chunk, all, &mapelms);
npurged = arena_chunk_purge_stashed(arena, chunk, &mapelms);
arena_chunk_unstash_purged(arena, chunk, &mapelms);
return (npurged);
}
chunk purge重點在於這是一個線性查找dirty pages過程, Je在這裡會導致性能
下降. 更糟糕的是, 之前和之後都是在arena lock被鎖定的條件下被執行, 綁定
同一arena的線程不得不停下工作. 因此, 在正式purge前需要先把unalloc dirty
pages全部臨時分配出來, 當purging時解鎖arena lock, 而結束後再一次將它們
全部釋放.
stash dirty代碼,
static void
arena_chunk_stash_dirty(arena_t *arena, arena_chunk_t *chunk, bool all,
arena_chunk_mapelms_t *mapelms)
{
......
for (pageind = map_bias; pageind < chunk_npages; pageind += npages) {
arena_chunk_map_t *mapelm = arena_mapp_get(chunk, pageind);
if (arena_mapbits_allocated_get(chunk, pageind) == 0) {
......
if (arena_mapbits_dirty_get(chunk, pageind) != 0 &&
(all || arena_avail_adjac(chunk, pageind,
npages))) {
arena_run_t *run = (arena_run_t *)((uintptr_t)
chunk + (uintptr_t)(pageind << LG_PAGE));
// xf: 暫時將這些unalloc dirty pages通過split large
// 重新分配出來.
arena_run_split_large(arena, run, run_size,
false);
// 加入臨時列表, 留待後用.
ql_elm_new(mapelm, u.ql_link);
ql_tail_insert(mapelms, mapelm, u.ql_link);
}
} else {
//xf: 跳過allocated pages
......
}
}
......
}
stash時會根據傳入的hint all判斷, 如果為false, 只會stash存在clean-dirty
adjac的pages, 否則會全部加入列表.
purge stashed pages代碼如下,
static size_t
arena_chunk_purge_stashed(arena_t *arena, arena_chunk_t *chunk,
arena_chunk_mapelms_t *mapelms)
{
......
// xf: 暫時解鎖arena lock, 前面已經realloc過, 這裡不考慮contention問題.
malloc_mutex_unlock(&arena->lock);
......
ql_foreach(mapelm, mapelms, u.ql_link) {
......
// xf: 逐個purge dirty page, 返回pages是否unzeroed.
unzeroed = pages_purge((void *)((uintptr_t)chunk + (pageind <<
LG_PAGE)), (npages << LG_PAGE));
flag_unzeroed = unzeroed ? CHUNK_MAP_UNZEROED : 0;
// xf: 逐pages設置unzeroed標志.
for (i = 0; i < npages; i++) {
arena_mapbits_unzeroed_set(chunk, pageind+i,
flag_unzeroed);
}
......
}
// xf: purging結束重新lock arena
malloc_mutex_lock(&arena->lock);
......
return (npurged);
}
這裡要注意的是, 在page purge過後, 會逐一設置unzero flag. 這是因為有些
操作系統在demand page後會有一步zero-fill-on-demand. 因此, 被purge過的
clean page當再一次申請到物理頁面時會全部填充為0.
unstash代碼,
static void
arena_chunk_unstash_purged(arena_t *arena, arena_chunk_t *chunk,
arena_chunk_mapelms_t *mapelms)
{
......
for (mapelm = ql_first(mapelms); mapelm != NULL;
mapelm = ql_first(mapelms)) {
......
run = (arena_run_t *)((uintptr_t)chunk + (uintptr_t)(pageind <<
LG_PAGE));
ql_remove(mapelms, mapelm, u.ql_link);
arena_run_dalloc(arena, run, false, true);
}
}
unstash需要再一次調用arena_run_dalloc()以釋放臨時分配的pages. 要注意
此時我們已經位於arena_run_dalloc調用棧中, 而避免無限遞歸重入依靠參數
cleaned flag.
----[ 4.5 - arena chunk dalloc
當free chunk被Je釋放時, 根據局部性原理, 會成為下一個spare chunk而保存起來,
其真身並未消散. 而原先的spare則會根據內部dalloc方法被處理掉.
static void
arena_chunk_dalloc(arena_t *arena, arena_chunk_t *chunk)
{
......
// xf: 將chunk從avail-tree上remove
arena_avail_remove(arena, chunk, map_bias, chunk_npages-map_bias,
false, false);
// xf: 如果spare不為空, 則將被釋放的chunk替換原spare chunk.
if (arena->spare != NULL) {
arena_chunk_t *spare = arena->spare;
arena->spare = chunk;
arena_chunk_dalloc_internal(arena, spare);
} else
arena->spare = chunk;
}
同chunk alloc一樣, chunk dalloc算法也是可定制的. Je提供的默認算法
chunk_dalloc_default最終會調用chunk_unmap, 如下,
void
chunk_unmap(void *chunk, size_t size)
{
......
// xf: 如果啟用dss, 且當前chunk在dss內, 將其record在dss tree上.
// 否則如果就記錄在mmap tree上, 或者直接munmap釋放掉.
if (have_dss && chunk_in_dss(chunk))
chunk_record(&chunks_szad_dss, &chunks_ad_dss, chunk, size);
else if (chunk_dalloc_mmap(chunk, size))
chunk_record(&chunks_szad_mmap, &chunks_ad_mmap, chunk, size);
}
在3.3.5小節中alloc時會根據dss和mmap優先執行recycle. 源自在dalloc時record
在四棵chunk tree上的記錄. 但同spare記錄的不同, 這裡的記錄僅僅只剩下軀殼,
record時會強行釋放物理頁面, 因此recycle速度相比spare較慢.
chunk record算法如下,
1. 先purge chunk內部所有pages
2. 預分配base node, 以記錄釋放後的chunk. 這裡分配的node到後面可能沒有用,
提前分配是因為接下來要加鎖chunks_mtx. 而如果在臨界段內再分配base node,
則可能因為base pages不足而申請新的chunk, 這樣一來就會導致dead lock.
3. 尋找與要插入chunk的毗鄰地址. 首先嘗試與後面的地址合並, 成功則用後者
的base node記錄, 之後執行5.
4. 合並失敗, 用預分配的base node記錄chunk.
5. 嘗試與前面的地址合並.
6. 如果預分配的base node沒有使用, 釋放掉.
代碼如下,
static void
chunk_record(extent_tree_t *chunks_szad, extent_tree_t *chunks_ad, void *chunk,
size_t size)
{
......
// xf: purge all chunk pages
unzeroed = pages_purge(chunk, size);
// xf: 預先分配extent_node以記錄chunk. 如果該chunk可以進行合並, 該node
// 可能並不會使用. 這裡預先分配主要是避免dead lock. 因為某些情況
// base_node_alloc同樣可能會alloc base chunk, 由於後面chunk mutex被lock,
// 那樣將導致dead lock.
xnode = base_node_alloc();
xprev = NULL;
malloc_mutex_lock(&chunks_mtx);
// xf: 首先嘗試與後面的chunk合並.
key.addr = (void *)((uintptr_t)chunk + size);
node = extent_tree_ad_nsearch(chunks_ad, &key);
if (node != NULL && node->addr == key.addr) {
extent_tree_szad_remove(chunks_szad, node);
node->addr = chunk;
node->size += size;
node->zeroed = (node->zeroed && (unzeroed == false));
extent_tree_szad_insert(chunks_szad, node);
} else {
// xf: 合並失敗, 用提前分配好的xnode保存當前chunk信息.
if (xnode == NULL) {
goto label_return;
}
node = xnode;
xnode = NULL;
node->addr = chunk;
node->size = size;
node->zeroed = (unzeroed == false);
extent_tree_ad_insert(chunks_ad, node);
extent_tree_szad_insert(chunks_szad, node);
}
// xf: 再嘗試與前面的chunk合並
prev = extent_tree_ad_prev(chunks_ad, node);
if (prev != NULL && (void *)((uintptr_t)prev->addr + prev->size) ==
chunk) {
......
}
label_return:
malloc_mutex_unlock(&chunks_mtx);
// xf: 如果預先分配的node沒有使用, 則在此將之銷毀
if (xnode != NULL)
base_node_dalloc(xnode);
if (xprev != NULL)
base_node_dalloc(xprev);
}
最後順帶一提, 對於mmap區的pages, Je也可以直接munmap, 前提是需要在
jemalloc_internal_defs.h中開啟JEMALLOC_MUNMAP, 這樣就不會執行pages purge.
默認該選項是不開啟的. 但源自dss區中的分配則不存在反向釋放一說, 默認Je也
不會優先選擇dss就是了.
bool
chunk_dalloc_mmap(void *chunk, size_t size)
{
if (config_munmap)
pages_unmap(chunk, size);
return (config_munmap == false);
}
----[ 4.6 - large/huge dalloc
前面說過large/huge相當於以run和chunk為粒度的特例.
因此對於arena dalloc large來說, 最終就是arena_run_dalloc,
void
arena_dalloc_large_locked(arena_t *arena, arena_chunk_t *chunk, void *ptr)
{
if (config_fill || config_stats) {
size_t pageind = ((uintptr_t)ptr - (uintptr_t)chunk) >> LG_PAGE;
size_t usize = arena_mapbits_large_size_get(chunk, pageind);
arena_dalloc_junk_large(ptr, usize);
if (config_stats) {
arena->stats.ndalloc_large++;
arena->stats.allocated_large -= usize;
arena->stats.lstats[(usize >> LG_PAGE) - 1].ndalloc++;
arena->stats.lstats[(usize >> LG_PAGE) - 1].curruns--;
}
}
arena_run_dalloc(arena, (arena_run_t *)ptr, true, false);
}
而huge dalloc, 則是在huge tree上搜尋, 最終執行chunk_dalloc,
void
huge_dalloc(void *ptr)
{
......
malloc_mutex_lock(&huge_mtx);
key.addr = ptr;
node = extent_tree_ad_search(&huge, &key);
assert(node != NULL);
assert(node->addr == ptr);
extent_tree_ad_remove(&huge, node);
malloc_mutex_unlock(&huge_mtx);
huge_dalloc_junk(node->addr, node->size);
arena_chunk_dalloc_huge(node->arena, node->addr, node->size);
base_node_dalloc(node);
}
void
arena_chunk_dalloc_huge(arena_t *arena, void *chunk, size_t size)
{
chunk_dalloc_t *chunk_dalloc;
malloc_mutex_lock(&arena->lock);
chunk_dalloc = arena->chunk_dalloc;
if (config_stats) {
arena->stats.mapped -= size;
arena->stats.allocated_huge -= size;
arena->stats.ndalloc_huge++;
stats_cactive_sub(size);
}
arena->nactive -= (size >> LG_PAGE);
malloc_mutex_unlock(&arena->lock);
chunk_dalloc(chunk, size, arena->ind);
}
前面已做了充分介紹, 這裡不再贅述.
----[ 5 - 總結: 與Dl的對比
1. 單核單線程分配能力上兩者不相上下, 甚至小塊內存分配速度理論上Dl還略占優勢.
原因是Dl利用雙向鏈表組織free chunk可以做到O(1), 而盡管Je在bitmap上做了一定
優化, 但不能做到常數時間.
2. 多核多線程下, Je可以秒殺Dl. arena的加入既可以避免false sharing, 又可以減少
線程間lock contention. 另外, tcache也是可以大幅加快多線程分配速度的技術.
這些Dl完全不具備競爭力.
3. 系統內存交換效率上也是Je占明顯優勢. Je使用mmap/madvise的組合要比Dl使用
sbrk/mmap/munmap靈活的多. 實際對系統的壓力也更小. 另外, Dl使用dss->mmap,
追求的是速度, 而Je相反mmap->dss, 為的是靈活性.
4. 小塊內存的碎片抑制上雙方做的都不錯, 但總體上個人覺得Je更好一些. 首先
dalloc時, 兩者對空閒內存都可以實時coalesce. alloc時Dl依靠dv約束外部碎片,
Je更簡單暴力, 直接在固定的small runs裡分配.
兩相比較, dv的候選者是隨機的, 大小不固定, 如果選擇比較小的chunk, 效果
其實有限. 更甚者, 當找不到dv時, Dl會隨意切割top-most space, 通常這不利於
heap trim.
而small runs則是固定大小, 同時是頁面的整數倍, 對外部碎片的約束力和規整度上
都更好.
但Dl的優勢在算法更簡單, 速度更快. 無論是coalesce還是split代價都很低. 在Je
中有可能因為分配8byte的內存而實際去分配並初始化4k甚至4M的空間.
5. 大塊內存分配能力上, Dl使用dst管理, 而Je采用rb tree. 原理上, 據說rb tree
的cache親和力較差, 不適合memory allocator. 我沒有仔細研究Je的rb tree實現
有何過人之處, 暫且認為各有千秋吧. 可以肯定的是Je的large/huge region具有
比Dl更高的內部碎片, 皆因為其更規整的size class劃分導致的.
6. 說到size class, 可以看到Je的劃分明顯比Dl更細致, tiny/small/large/huge四種
分類能兼顧更多的內存使用模型. 且根據不同架構和配置, 可以靈活改變劃分方式,
具有更好的兼容性. Dl劃分的相對粗糙很多且比較固定. 一方面可能在當時256byte
以上就可以算作大塊的分配了吧. 另一方面某種程度是礙於算法的限制. 比如在
boundary tag中為了容納更多的信息, 就不能小於8byte(實際有效的最小chunk是
16byte), bin數量不得多余31個也是基於位運算的方式.
7. bookkeeping占用上Dl因為算法簡單, 本應該占用更少內存. 但由於boundary tag
本身導致的占用, chunk數量越多, bookkeeping就越大. 再考慮到系統回收效率上
的劣勢, 應該說, 應用內存占用越大, 尤其是小內存使用量越多, 運行時間越長,
Dl相對於Je內存使用量傾向越大.
8. 安全健壯性. 只說一點, boundary tag是原罪, 其他的可以免談了.
--[ 附: 快速調試Jemalloc
一個簡單的調試Je的方法是以靜態庫的方式將其編譯到你的應用程序中.
先編譯Je的靜態庫, 在源碼目錄下執行,
./configure
make
make install
就可以編譯並安裝Je到系統路徑. 調試還必須打開一些選項, 例如,
./configure --enable-debug --with-jemalloc-prefix=<prefix>
這些選項的意義可以參考INSTALL文檔. 比如,
--disable-tcache 是否禁用tcache, 對調試非tcache流程有用.
--disable-prof 是否禁用heap profile.
--enable-debug 打開調試模式, 啟動assert並關閉優化.
--with-jemalloc-prefix 將編譯出的malloc加上設定的前綴, 以區別c庫的調用.
之後就可以將其編譯到你的代碼中, 如,
gcc main.c /usr/local/lib/libjemalloc.a -std=c99 -O0 -g3 -pthread -o jhello
