# mimalloc 原始碼分析
> 以最新版本 2.0.1 為例
> - `dev`: development branch for mimalloc v1.
> - `dev-slice`: development branch for mimalloc v2 with a new algorithm for managing internal mimalloc pages.
## Types
### `mi_block`
```c
// The free lists use encoded next fields
// (Only actually encodes when MI_ENCODED_FREELIST is defined.)
typedef uintptr_t mi_encoded_t;
// free lists contain blocks
typedef struct mi_block_s {
mi_encoded_t next;
} mi_block_t;
```
用來回傳使用者真正需要的記憶體空間位置，不需要紀錄 block 的大小是因為 `mi_block_t` 都由 `mi_page_t` 來管理，而每個 `mi_page_t` 都只對應一個固定的大小 `xblock_size` 來決定 `mi_block_t` 可使用的範圍。
每個尚未分配給使用者的 `mi_block_t` 皆為一個 linked list，其使用 `next` 欄位紀錄在同個 `mi_page_t` 內的下個未使用的 `mi_block_t`。特別的是當定義 `MI_ENCODED_FREELIST` 時，`next` 不是紀錄記憶體位置，而是會透過編碼轉換 (類似 XOR) 來增加安全性。
故使用者透過 `mi_malloc(size_t size)` 獲得的空間，一般情況下，內部為該 block 在 `mi_page_t` 時存放的 `next` 之內容，而當 `MI_SECURE` 開啟時，則會特別將 `next` 清空，防止資料洩漏：
```c
extern inline void* _mi_page_malloc(mi_heap_t* heap, mi_page_t* page, size_t size) mi_attr_noexcept {
...
#elif (MI_SECURE!=0)
block->next = 0; // don't leak internal data
#endif
...
}
```
### `mi_page`
```c
typedef struct mi_page_s {
// "owned" by the segment
uint32_t slice_count; // slices in this page (0 if not a page)
uint32_t slice_offset; // distance from the actual page data slice (0 if a page)
uint8_t is_reset : 1; // `true` if the page memory was reset
uint8_t is_committed : 1; // `true` if the page virtual memory is committed
uint8_t is_zero_init : 1; // `true` if the page was zero initialized
// layout like this to optimize access in `mi_malloc` and `mi_free`
uint16_t capacity; // number of blocks committed, must be the first field, see `segment.c:page_clear`
uint16_t reserved; // number of blocks reserved in memory
mi_page_flags_t flags; // `in_full` and `has_aligned` flags (8 bits)
uint8_t is_zero : 1; // `true` if the blocks in the free list are zero initialized
uint8_t retire_expire : 7; // expiration count for retired blocks
mi_block_t* free; // list of available free blocks (`malloc` allocates from this list)
#ifdef MI_ENCODE_FREELIST
uintptr_t keys[2]; // two random keys to encode the free lists (see `_mi_block_next`)
#endif
uint32_t used; // number of blocks in use (including blocks in `local_free` and `thread_free`)
uint32_t xblock_size; // size available in each block (always `>0`)
mi_block_t* local_free; // list of deferred free blocks by this thread (migrates to `free`)
_Atomic(mi_thread_free_t) xthread_free; // list of deferred free blocks freed by other threads
_Atomic(uintptr_t) xheap;
struct mi_page_s* next; // next page owned by this thread with the same `block_size`
struct mi_page_s* prev; // previous page owned by this thread with the same `block_size`
// 64-bit 9 words, 32-bit 12 words, (+2 for secure)
#if MI_INTPTR_SIZE==8
uintptr_t padding[1];
#endif
} mi_page_t;
```
* `mi_block_t* free`：此 page 中，尚未被使用者使用的 block
* `mi_block_t* local_free`：對應論文中的 local free list
* `mi_thread_free_t* xthread_free`：對應論文中的 thread free list
另外 `xblock_size` 為此 page 內每個 block 可佔有的空間，每個存有相同大小的 block 之 page 也會由 `next` 與 `prev` 欄位連結成 doubly linked list。
### `mi_segment`
```c
typedef mi_page_t mi_slice_t;
typedef struct mi_segment_s {
size_t memid; // memory id for arena allocation
bool mem_is_pinned; // `true` if we cannot decommit/reset/protect in this memory (i.e. when allocated using large OS pages)
bool mem_is_large; // in large/huge os pages?
bool mem_is_committed; // `true` if the whole segment is eagerly committed
bool allow_decommit;
mi_msecs_t decommit_expire;
mi_commit_mask_t decommit_mask;
mi_commit_mask_t commit_mask;
_Atomic(struct mi_segment_s*) abandoned_next;
// from here is zero initialized
struct mi_segment_s* next; // the list of freed segments in the cache (must be first field, see `segment.c:mi_segment_init`)
size_t abandoned; // abandoned pages (i.e. the original owning thread stopped) (`abandoned <= used`)
size_t abandoned_visits; // count how often this segment is visited in the abandoned list (to force reclaim it it is too long)
size_t used; // count of pages in use
uintptr_t cookie; // verify addresses in debug mode: `mi_ptr_cookie(segment) == segment->cookie`
size_t segment_slices; // for huge segments this may be different from `MI_SLICES_PER_SEGMENT`
size_t segment_info_slices; // initial slices we are using segment info and possible guard pages.
// layout like this to optimize access in `mi_free`
mi_segment_kind_t kind;
_Atomic(uintptr_t) thread_id; // unique id of the thread owning this segment
size_t slice_entries; // entries in the `slices` array, at most `MI_SLICES_PER_SEGMENT`
mi_slice_t slices[MI_SLICES_PER_SEGMENT];
} mi_segment_t;
```
`mi_segment` 為實際上 mimalloc 主要從 OS 上獲得的空間，管理著所需要的 page (`mi_slice_t slices[MI_SLICES_PER_SEGMENT`)。其中 `slices[0]` 被用來儲存 segment 中的額外資訊。
### `mi_heap`
```c
// A heap owns a set of pages.
struct mi_heap_s {
mi_tld_t* tld;
mi_page_t* pages_free_direct[MI_PAGES_DIRECT]; // optimize: array where every entry points a page with possibly free blocks in the corresponding queue for that size.
mi_page_queue_t pages[MI_BIN_FULL + 1]; // queue of pages for each size class (or "bin")
_Atomic(mi_block_t*) thread_delayed_free;
uintptr_t thread_id; // thread this heap belongs too
uintptr_t cookie; // random cookie to verify pointers (see `_mi_ptr_cookie`)
uintptr_t keys[2]; // two random keys used to encode the `thread_delayed_free` list
mi_random_ctx_t random; // random number context used for secure allocation
size_t page_count; // total number of pages in the `pages` queues.
size_t page_retired_min; // smallest retired index (retired pages are fully free, but still in the page queues)
size_t page_retired_max; // largest retired index into the `pages` array.
mi_heap_t* next; // list of heaps per thread
bool no_reclaim; // `true` if this heap should not reclaim abandoned pages
};
```
每個執行緒上都有一個 `mi_heap`，用來紀錄目前該執行緒所儲存的 page，放入在 `mi_page_queue_t pages` 當中，其中相同大小的 page 被放入在同個 queue 之中，而 `pages[MI_BIN_FULL - 1]` 特別被用作放置存有特別大的 block 之 page，`pages[MI_BIN_FULL]` 則用來當作存放論文中提到的 full list。
### `mi_tld`
```c
// Thread local data
struct mi_tld_s {
unsigned long long heartbeat; // monotonic heartbeat count
bool recurse; // true if deferred was called; used to prevent infinite recursion.
mi_heap_t* heap_backing; // backing heap of this thread (cannot be deleted)
mi_heap_t* heaps; // list of heaps in this thread (so we can abandon all when the thread terminates)
mi_segments_tld_t segments; // segment tld
mi_os_tld_t os; // os tld
mi_stats_t stats; // statistics
};
```
`mi_tid` 存放此執行緒的相關運行資料，包括 `mi_heap` 的資料、作業系統的資料等等，`mi_segments_tld_t segment` 為目前此執行緒中與 segment 相關的資料，其內部 `mi_tld_t->segments->spans[MI_SEGMENT_BIN_MAX+1]` 成員存放此執行緒可供使用的所有 page 用來加快存取效率。
## Function
### `mi_malloc`
```c
extern inline mi_decl_restrict void* mi_malloc(size_t size) mi_attr_noexcept {
return mi_heap_malloc(mi_get_default_heap(), size);
}
```
透過 `mi_malloc` 分配記憶體，其中 `mi_get_default_heap` 會回傳 `_mi_heap_deafult1`，取得目前執行緒所管理的 heap。
* 如果是主執行緒 (main thread)，則執行緒管理的 `_mi_heap_default` 在程式執行時已被設定為 `_mi_heap_main`
* 如果是非主行緒，則執行緒管理的 `_mi_heap_default` 初始化為 `_mi_heap_empty`，表示此 heap 尚未分配空間，在其後 `mi_malloc` 的過程中分配新的空間給予 `_meap_default` 來當作此執行緒可用的 heap。
```c
extern inline mi_decl_restrict void* mi_heap_malloc(mi_heap_t* heap, size_t size) mi_attr_noexcept {
if (mi_likely(size <= MI_SMALL_SIZE_MAX)) {
return mi_heap_malloc_small(heap, size);
}
else {
void* const p = _mi_malloc_generic(heap, size + MI_PADDING_SIZE); // note: size can overflow but it is detected in malloc_generic
return p;
}
}
```
依照需要的 block 大小與 `MI_SMALL_SIZE_MAX (128)` 決定使用 `mi_malloc` 的 fast path 還是 slow path。
* fast path
```c
static inline mi_page_t* _mi_heap_get_free_small_page(mi_heap_t* heap, size_t size) {
const size_t idx = _mi_wsize_from_size(size);
return heap->pages_free_direct[idx];
}
// allocate a small block
extern inline mi_decl_restrict void* mi_heap_malloc_small(mi_heap_t* heap, size_t size) mi_attr_noexcept {
mi_page_t* page = _mi_heap_get_free_small_page(heap,size + MI_PADDING_SIZE);
void* p = _mi_page_malloc(heap, page, size + MI_PADDING_SIZE);
return p;
}
```
`heap->page_free_direct` 為存有 130 個 `mi_page_t` 的陣列，儲存 size 較小的 page，fast path 會從 `heap->pages_free_direct` 內直接取得需要配置空間的 page，而不需要逐一走訪 page queue 中尋找可用的 page。
```c
// Fast allocation in a page: just pop from the free list.
// Fall back to generic allocation only if the list is empty.
extern inline void* _mi_page_malloc(mi_heap_t* heap, mi_page_t* page, size_t size) mi_attr_noexcept {
mi_block_t* const block = page->free;
if (mi_unlikely(block == NULL)) {
return _mi_malloc_generic(heap, size);
}
// pop from the free list
page->used++;
page->free = mi_block_next(page, block);
return block;
}
```
`page->free` 指向此 page 中尚未被用到的 block 空間，故分配時只需從該空間取出可用的 block，當 page 內沒有可用的 block 時，呼叫 `_mi_malloc_generic` 轉移到 slow path 做 malloc。
* slow path
當分配所需空間 > `MI_SMALL_SIZE_MAX` 、page 為空 (`page == _mi_page_empty`) 或是 page 沒有可用空間 (`page->free == NULL`) 時，呼叫 `_mi_malloc_generic` 函式尋找新的 page：
```c
// Generic allocation routine if the fast path (`alloc.c:mi_page_malloc`) does not succeed.
// Note: in debug mode the size includes MI_PADDING_SIZE and might have overflowed.
void* _mi_malloc_generic(mi_heap_t* heap, size_t size) mi_attr_noexcept
{
// initialize if necessary
if (mi_unlikely(!mi_heap_is_initialized(heap))) {
mi_thread_init(); // calls `_mi_heap_init` in turn
heap = mi_get_default_heap();
if (mi_unlikely(!mi_heap_is_initialized(heap))) {
return NULL;
}
}
// call potential deferred free routines
_mi_deferred_free(heap, false);
// free delayed frees from other threads
_mi_heap_delayed_free(heap);
// find (or allocate) a page of the right size
mi_page_t* page = mi_find_page(heap, size);
if (mi_unlikely(page == NULL)) { // first time out of memory, try to collect and retry the allocation once more
mi_heap_collect(heap, true /* force */);
page = mi_find_page(heap, size);
}
if (mi_unlikely(page == NULL)) { // out of memory
const size_t req_size = size - MI_PADDING_SIZE; // correct for padding_size in case of an overflow on `size`
_mi_error_message(ENOMEM, "unable to allocate memory (%zu bytes)\n", req_size);
return NULL;
}
// and try again, this time succeeding! (i.e. this should never recurse)
return _mi_page_malloc(heap, page, size);
}
```
`_mi_malloc_generic` 會先檢查 heap 是否初始化，如果呼叫此函式的執行緒為第一次呼叫 `mi_malloc` 且不為主執行緒時，`mi_heap_is_initialized` 會回傳 false 進入 `mi_thread_init` 做初始化。
`_mi_deferred_free` 呼叫使用者自訂的釋放函式，`_mi_heap_delayed_free` 則釋放 thread delayed free list，其下方再介紹。
`mi_find_page` 會嘗試尋找可用的 page，可用的 page 可能是重新分配一個 segment 來取得，或是從已分配的 segment 中尋找。當 `mi_find_page` 回傳 `NULL` 時，表示 out of memory，透過 `mi_heap_collect` 嘗試回收更多的空間並在試一次。最後再重新進入 `_mi_page_malloc` 從取得的 page 回傳可使用的 block 空間。
```c
// Allocate a page
// Note: in debug mode the size includes MI_PADDING_SIZE and might have overflowed.
static mi_page_t* mi_find_page(mi_heap_t* heap, size_t size) mi_attr_noexcept {
// huge allocation?
const size_t req_size = size - MI_PADDING_SIZE; // correct for padding_size in case of an overflow on `size`
if (mi_unlikely(req_size > (MI_MEDIUM_OBJ_SIZE_MAX - MI_PADDING_SIZE) )) {
if (mi_unlikely(req_size > PTRDIFF_MAX)) { // we don't allocate more than PTRDIFF_MAX (see <https://sourceware.org/ml/libc-announce/2019/msg00001.html>)
_mi_error_message(EOVERFLOW, "allocation request is too large (%zu bytes)\n", req_size);
return NULL;
}
else {
return mi_large_huge_page_alloc(heap,size);
}
}
else {
// otherwise find a page with free blocks in our size segregated queues
return mi_find_free_page(heap, size);
}
}
```
`mi_find_page` 用來尋找或分配 page，依據 `MI_MEDIUM_OBJ_SIZE_MAX` 分類，當需要分配的空間大於此數值時，此時每個 page 皆只包含一個 block，其大小為需要的空間，故直接執行 `mi_large_huge_page_alloc` 從 segment 分配一個新的 page，而不需要再從 page queue 中搜尋；當需要分配的空間大小不超過 `MI_MEDIUM_OBJ_SIZE_MAX` 時，可用的 block 空間可能會在已分配的 page 中找到，故從對應的 page queue 中尋找，如果找不到時，也會跟 `mi_large_huge_page_alloc` 呼叫路徑相同從 segment 中重新分配一個新的 page。
```c
static inline mi_page_queue_t* mi_page_queue(const mi_heap_t* heap, size_t size) {
return &((mi_heap_t*)heap)->pages[_mi_bin(size)];
}
// Find a page with free blocks of `size`.
static inline mi_page_t* mi_find_free_page(mi_heap_t* heap, size_t size) {
mi_page_queue_t* pq = mi_page_queue(heap,size);
mi_page_t* page = pq->first;
if (page != NULL) {
_mi_page_free_collect(page,false);
if (mi_page_immediate_available(page)) {
page->retire_expire = 0;
return page; // fast path
}
}
return mi_page_queue_find_free_ex(heap, pq, true);
}
```
`mi_page_queue` 會找到 size 對應的 page queue，如果該 page queue 之 `first` 的 free list 不為空，則表示該 page 可用，直接回傳，否則呼叫 `mi_page_queue_find_free_ex` 在 page queue 中搜尋 free list 不為空的 page：
```c
// Find a page with free blocks of `page->block_size`.
static mi_page_t* mi_page_queue_find_free_ex(mi_heap_t* heap, mi_page_queue_t* pq, bool first_try)
{
// search through the pages in "next fit" order
mi_page_t* page = pq->first;
while (page != NULL)
{
mi_page_t* next = page->next; // remember next
// 0. collect freed blocks by us and other threads
_mi_page_free_collect(page, false);
// 1. if the page contains free blocks, we are done
if (mi_page_immediate_available(page)) {
break; // pick this one
}
// 2. Try to extend
if (page->capacity < page->reserved) {
mi_page_extend_free(heap, page, heap->tld);
break;
}
// 3. If the page is completely full, move it to the `mi_pages_full`
// queue so we don't visit long-lived pages too often.
mi_page_to_full(page, pq);
page = next;
} // for each page
if (page == NULL) {
_mi_heap_collect_retired(heap, false); // perhaps make a page available?
page = mi_page_fresh(heap, pq);
if (page == NULL && first_try) {
// out-of-memory _or_ an abandoned page with free blocks was reclaimed, try once again
page = mi_page_queue_find_free_ex(heap, pq, false);
}
}
else {
page->retire_expire = 0;
}
return page;
}
```
如果 page queue 不為空，則逐一走訪 queue 並嘗試釋放空間，如果在走訪的過程中找到空的 free block 時便直接回傳該 page。當 page queue 中的所有 page 都沒有可用的 block 時，先呼叫 `_mi_heap_collect_retired` 回收空間，接著 `mi_page_fresh` 會嘗試從 segment 中獲得一塊新的 page 空間使用。
```c
// Get a fresh page to use
static mi_page_t* mi_page_fresh(mi_heap_t* heap, mi_page_queue_t* pq) {
mi_page_t* page = mi_page_fresh_alloc(heap, pq, pq->block_size);
if (page==NULL) return NULL;
return page;
}
// allocate a fresh page from a segment
static mi_page_t* mi_page_fresh_alloc(mi_heap_t* heap, mi_page_queue_t* pq, size_t block_size) {
mi_page_t* page = _mi_segment_page_alloc(heap, block_size, &heap->tld->segments, &heap->tld->os);
if (page == NULL) {
// this may be out-of-memory, or an abandoned page was reclaimed (and in our queue)
return NULL;
}
mi_page_init(heap, page, block_size, heap->tld);
if (pq!=NULL) mi_page_queue_push(heap, pq, page); // huge pages use pq==NULL
return page;
}
```
`_mi_segment_page_alloc` 為實際從 segment 分配 page 的函式，當找到可用的 page 時，通過 `_mi_page_init` 初始化，並將該 page 放到先前所選擇對應大小的 page queue 中。
```c
mi_page_t* _mi_segment_page_alloc(mi_heap_t* heap, size_t block_size, mi_segments_tld_t* tld, mi_os_tld_t* os_tld) {
mi_page_t* page;
if (block_size <= MI_SMALL_OBJ_SIZE_MAX) {
page = mi_segments_page_alloc(heap,MI_PAGE_SMALL,block_size,block_size,tld,os_tld);
}
else if (block_size <= MI_MEDIUM_OBJ_SIZE_MAX) {
page = mi_segments_page_alloc(heap,MI_PAGE_MEDIUM,MI_MEDIUM_PAGE_SIZE,block_size,tld, os_tld);
}
else if (block_size <= MI_LARGE_OBJ_SIZE_MAX) {
page = mi_segments_page_alloc(heap,MI_PAGE_LARGE,block_size,block_size,tld, os_tld);
}
else {
page = mi_segment_huge_page_alloc(block_size,tld,os_tld);
}
return page;
}
```
根據 `block_size` 決定分配 page 所需的大小，mimalloc 中將 `block_size` 分成四類，每類配置的空間的方式都不同：
* Small, [$0$ KiB, $8$ KiB]
每個 segment 有多個 page，每個 page 有多個 block，每個 block 的 `block_size` 為 small 大小
* Medium, ($8$ KiB, $128$ KiB]
每個 segment 有多個 page，每個 page 有多個 block，每個 block 的 `block_size` 為 medium 大小
* Large, ($128$ KiB, $4$ MiB]
每個 segment 有多個 page，每個 page 有一個 block，每個 block 的 `block_size` 為 large 大小
* Huge, ($4$ MiB, $2^{63}$ Bytes)
每個 segment 有一個 page，每個 page 有一個 block，每個 block 的 `block_size` 為 huge 大小
```c
static mi_page_t* mi_segments_page_alloc(mi_heap_t* heap, mi_page_kind_t page_kind, size_t required, size_t block_size, mi_segments_tld_t* tld, mi_os_tld_t* os_tld)
{
// find a free page
size_t page_size = _mi_align_up(required, (required > MI_MEDIUM_PAGE_SIZE ? MI_MEDIUM_PAGE_SIZE : MI_SEGMENT_SLICE_SIZE));
size_t slices_needed = page_size / MI_SEGMENT_SLICE_SIZE;
mi_page_t* page = mi_segments_page_find_and_allocate(slices_needed, tld);
if (page==NULL) {
// no free page, allocate a new segment and try again
if (mi_segment_reclaim_or_alloc(heap, slices_needed, block_size, tld, os_tld) == NULL) {
// OOM or reclaimed a good page in the heap
return NULL;
}
else {
// otherwise try again
return mi_segments_page_alloc(heap, page_kind, required, block_size, tld, os_tld);
}
}
mi_segment_delayed_decommit(_mi_ptr_segment(page), false, tld->stats);
return page;
}
```
`mi_segments_page_find_and_allocate` 會從已經分配的 segment 中尋找可用的 page，如果找不到則透過 `mi_segment_reclaim_or_alloc` 重新分配一個新的 segment 來尋找。
```c
static mi_segment_t* mi_segment_reclaim_or_alloc(mi_heap_t* heap, size_t needed_slices, size_t block_size, mi_segments_tld_t* tld, mi_os_tld_t* os_tld)
{
// 1. try to get a segment from our cache
mi_segment_t* segment = mi_segment_cache_pop(MI_SEGMENT_SIZE, tld);
if (segment != NULL) {
mi_segment_init(segment, 0, tld, os_tld, NULL);
return segment;
}
// 2. try to reclaim an abandoned segment
bool reclaimed;
segment = mi_segment_try_reclaim(heap, needed_slices, block_size, &reclaimed, tld);
if (reclaimed) {
// reclaimed the right page right into the heap
return NULL; // pretend out-of-memory as the page will be in the page queue of the heap with available blocks
}
else if (segment != NULL) {
// reclaimed a segment with a large enough empty span in it
return segment;
}
// 3. otherwise allocate a fresh segment
return mi_segment_alloc(0, tld, os_tld, NULL);
}
```
TODO: reclaim usage
嘗試獲得 semgent 空間，在 semgent 用完時，會將該 segment 放到 cache 中等待下次分配，這樣可以防止頻繁的從系統中分配空間，如果 cache 以及 reclaim 都失敗的話，呼叫 `mi_segment_alloc` 從 OS 分配實際的空間出來。
```c
static mi_page_t* mi_segments_page_find_and_allocate(size_t slice_count, mi_segments_tld_t* tld) {
// search from best fit up
mi_span_queue_t* sq = mi_span_queue_for(slice_count, tld);
if (slice_count == 0) slice_count = 1;
while (sq <= &tld->spans[MI_SEGMENT_BIN_MAX]) {
for (mi_slice_t* slice = sq->first; slice != NULL; slice = slice->next) {
if (slice->slice_count >= slice_count) {
// found one
mi_span_queue_delete(sq, slice);
mi_segment_t* segment = _mi_ptr_segment(slice);
if (slice->slice_count > slice_count) {
mi_segment_slice_split(segment, slice, slice_count, tld);
}
mi_page_t* page = mi_segment_span_allocate(segment, mi_slice_index(slice), slice->slice_count, tld);
if (page == NULL) {
// commit failed; return NULL but first restore the slice
mi_segment_span_free_coalesce(slice, tld);
return NULL;
}
return page;
}
}
sq++;
}
// could not find a page..
return NULL;
}
```
`mi_segments_tld_t:spans` 紀錄在該執行緒中，所有 segment 內可用的空間，並以 queue 串接。中間的 `for` 迴圈就是在從這些 queue 內尋找可用來當成 page 的空間 (這邊命名為 `slice`)，並從該空間取得對應的 segment。`mi_segment_slice_split` 將此空間分割成目前需要的空間以及用不到的空間，並把用不到的空間放回 queue 中以便之後可以再利用。目前需要的空間則透過 `mi_segment_span_allocate` 實際設定成 page，以及 page 的相關訊息。`mi_segment_span_free_coalesce` 則是分配失敗時，把剛剛分割的空間還原。
segment 使用 `mi_segment_t:slices` 紀錄所分配的 page，每個 `slice` 內的成員 `slice_count`，表示此 page 占用 segment 的幾個 `slice`，`slice_offset` 不為 0 則表示此 `slice` 被其他實際的 `slice` 占用，而 `slice_offset` 就是該 `slice` 與實際 `slice` 間的 byte 數，以圖片表示：
```graphviz
digraph {
node [shape=record, fontcolor=black, fontsize=14.5, width=11, height=1, fixedsize=true];
values [label="<f0> slices[0]\n\{slice_count=2\}\n\{slice_offset=0\} | <f1> slices[1]\n\{slice_count=0\}\n\{slice_offset=96\} | <f2> slices[2]\n\{slice_count=1\}\n\{slice_offset=0\} | <f3> slices[3]\n\{slice_count=3\}\n\{slice_offset=0\} | <f4> slices[4]\n\{slice_count=0\}\n\{slice_offset=96\} | <f5> slices[5]\n\{slice_count=0\}\n\{slice_offset=192\} | <f6> slices[6]\n\{slice_count=1\}\n\{slice_offset=0\}"]
}
```
:::info
因 `sizeof(mi_slice_t)=96`，故 `slice_offset` 為 96 的倍數。
:::
其中 `slices[0], slices[2], slices[3], skuces[6]` 都會回傳並成為 page，而 page 實際大小就為該 page 所占有的所有 slices。
```c
static void mi_segment_slice_split(mi_segment_t* segment, mi_slice_t* slice, size_t slice_count, mi_segments_tld_t* tld) {
if (slice->slice_count <= slice_count) return;
size_t next_index = mi_slice_index(slice) + slice_count;
size_t next_count = slice->slice_count - slice_count;
mi_segment_span_free(segment, next_index, next_count, tld);
slice->slice_count = (uint32_t)slice_count;
}
```
再回頭看 `mi_segment_slice_split` 便很好理解，`next_index` 為分割後下個 `slice` 的位置，`next_count` 為下個 `slice` 擁有的 slice 數目，再透過 `mi_segment_span_free` 把這些數據設定到 segment 中下個 slice 的位置。
```c
// note: can be called on abandoned segments
static void mi_segment_span_free(mi_segment_t* segment, size_t slice_index, size_t slice_count, mi_segments_tld_t* tld) {
mi_span_queue_t* sq = (segment->kind == MI_SEGMENT_HUGE || mi_segment_is_abandoned(segment)
? NULL : mi_span_queue_for(slice_count,tld));
if (slice_count==0) slice_count = 1;
// set first and last slice (the intermediates can be undetermined)
mi_slice_t* slice = &segment->slices[slice_index];
slice->slice_count = (uint32_t)slice_count;
slice->slice_offset = 0;
if (slice_count > 1) {
mi_slice_t* last = &segment->slices[slice_index + slice_count - 1];
last->slice_count = 0;
last->slice_offset = (uint32_t)(sizeof(mi_page_t)*(slice_count - 1));
last->xblock_size = 0;
}
// perhaps decommit
mi_segment_perhaps_decommit(segment,mi_slice_start(slice),slice_count*MI_SEGMENT_SLICE_SIZE,tld->stats);
// and push it on the free page queue (if it was not a huge page)
if (sq != NULL) mi_span_queue_push( sq, slice );
else slice->xblock_size = 0; // mark huge page as free anyways
}
```
設定 `slice_count`，以及更新最後一個 `slice` 的 `slice_offset` (最後一個 `slice` 的 `slice_offset` 為與最高 index 的 `slice` 間的 byte 數)，最後 `mi_span_queue_push` 將這個新分割的 `slice` 放回 queue 中，以便下次搜尋可以使用。
```c
// Note: may still return NULL if committing the memory failed
static mi_page_t* mi_segment_span_allocate(mi_segment_t* segment, size_t slice_index, size_t slice_count, mi_segments_tld_t* tld) {
mi_slice_t* slice = &segment->slices[slice_index];
// commit before changing the slice data
if (!mi_segment_ensure_committed(segment, _mi_segment_page_start_from_slice(segment, slice, NULL), slice_count * MI_SEGMENT_SLICE_SIZE, tld->stats)) {
return NULL; // commit failed!
}
// convert the slices to a page
slice->slice_offset = 0;
slice->slice_count = (uint32_t)slice_count;
const size_t bsize = slice_count * MI_SEGMENT_SLICE_SIZE;
slice->xblock_size = (uint32_t)(bsize >= MI_HUGE_BLOCK_SIZE ? MI_HUGE_BLOCK_SIZE : bsize);
mi_page_t* page = mi_slice_to_page(slice);
// set slice back pointers for the first MI_MAX_SLICE_OFFSET entries
size_t extra = slice_count-1;
if (extra > MI_MAX_SLICE_OFFSET) extra = MI_MAX_SLICE_OFFSET;
if (slice_index + extra >= segment->slice_entries) extra = segment->slice_entries - slice_index - 1; // huge objects may have more slices than avaiable entries in the segment->slices
slice++;
for (size_t i = 1; i <= extra; i++, slice++) {
slice->slice_offset = (uint32_t)(sizeof(mi_slice_t)*i);
slice->slice_count = 0;
slice->xblock_size = 1;
}
// and also for the last one (if not set already) (the last one is needed for coalescing)
mi_slice_t* last = &segment->slices[slice_index + slice_count - 1];
if (last < mi_segment_slices_end(segment) && last >= slice) {
last->slice_offset = (uint32_t)(sizeof(mi_slice_t)*(slice_count-1));
last->slice_count = 0;
last->xblock_size = 1;
}
// and initialize the page
page->is_reset = false;
page->is_committed = true;
segment->used++;
return page;
}
```
`mi_segment_span_allocate` 將 `slice` 轉成 page 回傳，要注意此時 `slice->xblock_size` 並非 page 內 block 的大小，而是 page 本身的大小，再之後會呼叫 `mi_page_init` 將 `slice->xblock_size` 設定為應儲存的 block 大小。`extra` 為此 slice 會占用到的所有其他 slice 的數量，需要將這些 slice 的 `slice_offset` 設定為正確的距離，另外最後一個 slice 沒設置時也會一併設定。
```c
// note: can be called on abandoned segments
static mi_slice_t* mi_segment_span_free_coalesce(mi_slice_t* slice, mi_segments_tld_t* tld) {
mi_segment_t* segment = _mi_ptr_segment(slice);
bool is_abandoned = mi_segment_is_abandoned(segment);
// for huge pages, just mark as free but don't add to the queues
if (segment->kind == MI_SEGMENT_HUGE) {
slice->xblock_size = 0; // mark as free anyways
// we should mark the last slice `xblock_size=0` now to maintain invariants but we skip it to
// avoid a possible cache miss (and the segment is about to be freed)
return slice;
}
// otherwise coalesce the span and add to the free span queues
size_t slice_count = slice->slice_count;
mi_slice_t* next = slice + slice->slice_count;
if (next < mi_segment_slices_end(segment) && next->xblock_size==0) {
// free next block -- remove it from free and merge
slice_count += next->slice_count; // extend
if (!is_abandoned) {
mi_segment_span_remove_from_queue(next, tld);
}
}
if (slice > segment->slices) {
mi_slice_t* prev = mi_slice_first(slice - 1);
if (prev->xblock_size==0) {
// free previous slice -- remove it from free and merge
slice_count += prev->slice_count;
if (!is_abandoned) {
mi_segment_span_remove_from_queue(prev, tld);
}
slice = prev;
}
}
// and add the new free page
mi_segment_span_free(segment, mi_slice_index(slice), slice_count, tld);
return slice;
}
```
`mi_segment_span_free_coalesce` 將先前分割的 slice 合併，並且加入回 `tld` 中的 queue，另外對於 huge 類型的 segment (只含有一個 page) 則不須加入到 queue 當中，因其是使用 `mi_segment_huge_page_alloc` 分配 segment 空間，而不是 `mi_segments_page_alloc` 從 queue 中尋找。
如果在 `mi_find_page` 要分配的 page 的大小超過 `MI_MEDIUM_OBJ_SIZE_MAX` 時，此時直接呼叫 `mi_large_huge_page_alloc` 從 segment 中找可用的 page 空間：
```c
// Large and huge page allocation.
// Huge pages are allocated directly without being in a queue.
// Because huge pages contain just one block, and the segment contains
// just that page, we always treat them as abandoned and any thread
// that frees the block can free the whole page and segment directly.
static mi_page_t* mi_large_huge_page_alloc(mi_heap_t* heap, size_t size) {
size_t block_size = _mi_os_good_alloc_size(size);
bool is_huge = (block_size > MI_LARGE_OBJ_SIZE_MAX);
mi_page_queue_t* pq = (is_huge ? NULL : mi_page_queue(heap, block_size));
mi_page_t* page = mi_page_fresh_alloc(heap, pq, block_size);
if (page != NULL) {
const size_t bsize = mi_page_block_size(page); // note: not `mi_page_usable_block_size` as `size` includes padding
if (pq == NULL) {
mi_page_set_heap(page, NULL);
}
}
return page;
}
```
可以看到與 `mi_find_free_page` 失敗時一樣，皆會呼叫 `mi_page_fresh_alloc` 來從 segment 中尋找 page。另外 huge 類型因為每個 segment 只有一個 page，所有不用 page queue 儲存。
`mi_page_fresh_alloc` 接著會呼叫 `_mi_segment_page_alloc` 嘗試從 segment 上尋找可用的 page (上方有介紹)，在 `_mi_segment_page_alloc` 中，當 `block_size` 為 huge 類型時呼叫 `mi_segment_huge_page_alloc` 直接分配新的 segment：
```c
static mi_page_t* mi_segment_huge_page_alloc(size_t size, mi_segments_tld_t* tld, mi_os_tld_t* os_tld)
{
mi_page_t* page = NULL;
mi_segment_t* segment = mi_segment_alloc(size,tld,os_tld,&page);
if (segment == NULL || page==NULL) return NULL;
segment->thread_id = 0; // huge segments are immediately abandoned
return page;
}
```
### `mi_free`
```c
// Free a block
void mi_free(void* p) mi_attr_noexcept
{
const mi_segment_t* const segment = mi_checked_ptr_segment(p,"mi_free");
if (mi_unlikely(segment == NULL)) return;
const uintptr_t tid = _mi_thread_id();
mi_page_t* const page = _mi_segment_page_of(segment, p);
if (mi_likely(tid == segment->thread_id && page->flags.full_aligned == 0)) { // the thread id matches and it is not a full page, nor has aligned blocks
// local, and not full or aligned
mi_block_t* block = (mi_block_t*)(p);
mi_block_set_next(page, block, page->local_free);
page->local_free = block;
if (mi_unlikely(--page->used == 0)) { // using this expression generates better code than: page->used--; if (mi_page_all_free(page))
_mi_page_retire(page);
}
}
else {
// non-local, aligned blocks, or a full page; use the more generic path
// note: recalc page in generic to improve code generation
mi_free_generic(segment, tid == segment->thread_id, p);
}
}
```
`mi_free` 與 `mi_malloc` 一樣分成兩種情況，第一種是執行緒釋放相同執行緒上的變數，此時只需將 block 放入 `page->local_free` 當中即可，而實際將 `page->local_free` 移動到 `page->free` 形成可用空間的時機在於執行 `_mi_malloc_generic` 中找尋 page 的過程。
如果是不同執行緒間的釋放空間、釋放 full list 上的 page 或是釋放 unaligned 的 page，則會呼叫 `mi_free_generic`。
:::info
```c
typedef union mi_page_flags_s {
uint8_t full_aligned;
struct {
uint8_t in_full : 1;
uint8_t has_aligned : 1;
} x;
} mi_page_flags_t;
```
page 將 `in_full`, `has_aligned` 與 `full_aligned` 用同個 union 表示，只要 `x` 中有一個成員不為 0，則 `full_aligned` 就不為 0。
:::
```c
static void mi_decl_noinline mi_free_generic(const mi_segment_t* segment, bool local, void* p) {
mi_page_t* const page = _mi_segment_page_of(segment, p);
mi_block_t* const block = (mi_page_has_aligned(page) ? _mi_page_ptr_unalign(segment, page, p) : (mi_block_t*)p);
_mi_free_block(page, local, block);
}
// regular free
static inline void _mi_free_block(mi_page_t* page, bool local, mi_block_t* block)
{
// and push it on the free list
if (mi_likely(local)) {
// owning thread can free a block directly
if (mi_unlikely(mi_check_is_double_free(page, block))) return;
mi_block_set_next(page, block, page->local_free);
page->local_free = block;
page->used--;
if (mi_unlikely(mi_page_all_free(page))) {
_mi_page_retire(page);
}
else if (mi_unlikely(mi_page_is_in_full(page))) {
_mi_page_unfull(page);
}
}
else {
_mi_free_block_mt(page,block);
}
}
```
`_mi_free_block` 前半段同個執行緒下的釋放空間與 `mi_free` 相同，後方 `_mi_free_block_mt` 則為不同執行緒間的釋放函式，因為要處理不同執行緒間的變數，故在 `_mi_free_block_mt` 之中使用到了 atomic operation：
```c
// multi-threaded free
static mi_decl_noinline void _mi_free_block_mt(mi_page_t* page, mi_block_t* block)
{
// huge page segments are always abandoned and can be freed immediately
mi_segment_t* segment = _mi_page_segment(page);
if (segment->kind==MI_SEGMENT_HUGE) {
_mi_segment_huge_page_free(segment, page, block);
return;
}
// Try to put the block on either the page-local thread free list, or the heap delayed free list.
mi_thread_free_t tfreex;
bool use_delayed;
mi_thread_free_t tfree = mi_atomic_load_relaxed(&page->xthread_free);
do {
use_delayed = (mi_tf_delayed(tfree) == MI_USE_DELAYED_FREE);
if (mi_unlikely(use_delayed)) {
// unlikely: this only happens on the first concurrent free in a page that is in the full list
tfreex = mi_tf_set_delayed(tfree,MI_DELAYED_FREEING);
}
else {
// usual: directly add to page thread_free list
mi_block_set_next(page, block, mi_tf_block(tfree));
tfreex = mi_tf_set_block(tfree,block);
}
} while (!mi_atomic_cas_weak_release(&page->xthread_free, &tfree, tfreex));
if (mi_unlikely(use_delayed)) {
// racy read on `heap`, but ok because MI_DELAYED_FREEING is set (see `mi_heap_delete` and `mi_heap_collect_abandon`)
mi_heap_t* const heap = (mi_heap_t*)(mi_atomic_load_acquire(&page->xheap)); //mi_page_heap(page);
if (heap != NULL) {
// add to the delayed free list of this heap. (do this atomically as the lock only protects heap memory validity)
mi_block_t* dfree = mi_atomic_load_ptr_relaxed(mi_block_t, &heap->thread_delayed_free);
do {
mi_block_set_nextx(heap,block,dfree, heap->keys);
} while (!mi_atomic_cas_ptr_weak_release(mi_block_t,&heap->thread_delayed_free, &dfree, block));
}
// and reset the MI_DELAYED_FREEING flag
tfree = mi_atomic_load_relaxed(&page->xthread_free);
do {
tfreex = tfree;
mi_assert_internal(mi_tf_delayed(tfree) == MI_DELAYED_FREEING);
tfreex = mi_tf_set_delayed(tfree,MI_NO_DELAYED_FREE);
} while (!mi_atomic_cas_weak_release(&page->xthread_free, &tfree, tfreex));
}
}
```
`_mi_free_block_mt` 會將 block 放到兩個可能的地方，一個是 heap 的 thread delayed free list (`heap->thread_delayed_free`) 當中，另一個為 page 的 thread free list (`page->xthread_free`) 當中，只有當 thread delayed free list 為空時 (page 第一次分配 block 或呼叫 `_mi_heap_delayed_free` 後)，才會將 block 放到該 list 當中。
thread delayed free list 的用途在於節省 lock 的時間，當某個 page 內的 block 數已滿時，該 page 會透過 `mi_page_to_full` 函式被放入到 `heap->page[MI_BIN_FULL]` 中 (論文內的 full list)，使其不在 page queue 當中被搜尋以加快節點走訪速度。而當該 page 內的 block 被釋放後，需要將該 page 從 full list 移回 page queue 當中，如果是同個執行緒，則在 `mi_free` 時就會執行此動作，因為是同個執行緒所以不需要考慮 race condition，但如果釋放的空間是放在 thread free list 的話，檢查 block 是否釋放以及 page 的移動 (可能在移動的過程中 page 內的 block 被其他執行緒釋放) 都必須加上 lock 防止衝突。
在 heap 上增加 thread delayed free list 後，移動 page 的這個動作被延後執行，`_mi_heap_delayed_free` (在 `_mi_malloc_generic` 時呼叫) 會透過 atomic operation 把 thread delayed free list 移動到 `heap->local_free` 當中，之後由於都在同個執行緒上，便不需要額外的 lock，在 `_mi_heap_delayed_free -> _mi_free_delayed_block -> _mi_free_block` 中便能無鎖的把 page 從 full list 移回 page queue。
簡單來說，thread delayed free list 將有被不同執行緒釋放 block 的 page 連接，並給予 page 一個固定的時間點檢查該 page 是否需要從 full list 移動到 page queue 當中，同時也能真正釋放這些被不同執行緒釋放的 block。
> 如果沒有 thread delayed free list 的設計，在 `_mi_malloc_generic` 的過程中，會先嘗試從 segment 中找可用的 page，而不是從 full list 中找尋有被其他 thread 釋放空間 page，造成記憶體用量增加。
在 mimalloc 中，使用 `page->xthread_free` LSB 的 3 個 bits 來當作 delayed free 的 flags，其餘 bits 表示 thread free list 的 block：
```c
// Thread free flag helpers
static inline mi_block_t* mi_tf_block(mi_thread_free_t tf) {
return (mi_block_t*)(tf & ~0x03);
}
static inline mi_delayed_t mi_tf_delayed(mi_thread_free_t tf) {
return (mi_delayed_t)(tf & 0x03);
}
```
所以上方 `_mi_free_block_mt` 在 `mi_tf_delayed(tfree) == MI_USE_DELAYED_FREE` 時會將 block 放到 thread delayed free list (`heap->thread_delayed_free`)，其餘時間則放到 thread free list (`page->xthread_free`) 中，並把 `page->xthread_free` 內的 flag 設定為 `MI_NO_DELAYED_FREE`，下次就不會再使用 delayed free list。
在 `_mi_malloc_generic` 中有提到會呼叫 `_mi_heap_delayed_free`，此函式會實際將 heap 中的 thread delayed free list 移動回 page 的 `local_free`：
```c
void _mi_heap_delayed_free(mi_heap_t* heap) {
// take over the list (note: no atomic exchange since it is often NULL)
mi_block_t* block = mi_atomic_load_ptr_relaxed(mi_block_t, &heap->thread_delayed_free);
while (block != NULL && !mi_atomic_cas_ptr_weak_acq_rel(mi_block_t, &heap->thread_delayed_free, &block, NULL)) { /* nothing */ };
// and free them all
while(block != NULL) {
mi_block_t* next = mi_block_nextx(heap,block, heap->keys);
// use internal free instead of regular one to keep stats etc correct
if (!_mi_free_delayed_block(block)) {
// we might already start delayed freeing while another thread has not yet
// reset the delayed_freeing flag; in that case delay it further by reinserting.
mi_block_t* dfree = mi_atomic_load_ptr_relaxed(mi_block_t, &heap->thread_delayed_free);
do {
mi_block_set_nextx(heap, block, dfree, heap->keys);
} while (!mi_atomic_cas_ptr_weak_release(mi_block_t,&heap->thread_delayed_free, &dfree, block));
}
block = next;
}
}
```
`while` 迴圈逐一走訪 thread delayed free list，並對每個 block 執行 `_mi_free_delayed_block`。
```c
bool _mi_free_delayed_block(mi_block_t* block) {
// get segment and page
const mi_segment_t* const segment = _mi_ptr_segment(block);
mi_page_t* const page = _mi_segment_page_of(segment, block);
// Clear the no-delayed flag so delayed freeing is used again for this page.
// This must be done before collecting the free lists on this page -- otherwise
// some blocks may end up in the page `thread_free` list with no blocks in the
// heap `thread_delayed_free` list which may cause the page to be never freed!
// (it would only be freed if we happen to scan it in `mi_page_queue_find_free_ex`)
_mi_page_use_delayed_free(page, MI_USE_DELAYED_FREE, false /* dont overwrite never delayed */);
// collect all other non-local frees to ensure up-to-date `used` count
_mi_page_free_collect(page, false);
// and free the block (possibly freeing the page as well since used is updated)
_mi_free_block(page, true, block);
return true;
}
```
`_mi_page_use_delayed_free` 很簡單，就是將 page 內的 delayed free list 中的 flag 設定回 `MI_USE_DELAYED_FREE`，表示 block 可以再放到 thread delayed free list 中；`_mi_page_free_collect` 將可用空間 thread free list 及 local free list 移動回 free list；`_mi_free_block` 上方有介紹，將此 block (在 thread delayed free list 中的 block) 移動回 page 的 local free list 中。
```c
void _mi_page_free_collect(mi_page_t* page, bool force) {
// collect the thread free list
if (force || mi_page_thread_free(page) != NULL) { // quick test to avoid an atomic operation
_mi_page_thread_free_collect(page);
}
// and the local free list
if (page->local_free != NULL) {
if (mi_likely(page->free == NULL)) {
// usual case
page->free = page->local_free;
page->local_free = NULL;
page->is_zero = false;
}
else if (force) {
// append -- only on shutdown (force) as this is a linear operation
mi_block_t* tail = page->local_free;
mi_block_t* next;
while ((next = mi_block_next(page, tail)) != NULL) {
tail = next;
}
mi_block_set_next(page, tail, page->free);
page->free = page->local_free;
page->local_free = NULL;
page->is_zero = false;
}
}
}
```
`_mi_page_free_collect` 是把 local free list 以及 thread free list 移回 free list 的函式，除了在 `_mi_free_delayed_block` 中被呼叫外，也會在其他需要 page 空間時呼叫來取得可用 page 空間。
其中 `_mi_page_thread_free_collect` 用來回收 thread free list，而下方則是一般 local free list 的回收，將 `page->local_free` 與 `page->free` 連接，並把 `page->local_free` 清空。
### `_mi_thread_done`
每個執行緒結束時都要正確回收空間，在 mimalloc 當中註冊了 `_mi_thread_done` 函式，讓執行緒在結束時能夠呼叫該函式來回收空間。
```c
// Set up handlers so `mi_thread_done` is called automatically
static void mi_process_setup_auto_thread_done(void) {
static bool tls_initialized = false; // fine if it races
if (tls_initialized) return;
tls_initialized = true;
#if defined(_WIN32) && defined(MI_SHARED_LIB)
// nothing to do as it is done in DllMain
#elif defined(_WIN32) && !defined(MI_SHARED_LIB)
mi_fls_key = FlsAlloc(&mi_fls_done);
#elif defined(MI_USE_PTHREADS)
mi_assert_internal(_mi_heap_default_key == (pthread_key_t)(-1));
pthread_key_create(&_mi_heap_default_key, &mi_pthread_done);
#endif
_mi_heap_set_default_direct(&_mi_heap_main);
}
```
在 windows 平台上註冊 `mi_fls_done`；在 POSIX 上則是註冊 `mi_pthread_done`，兩函式皆會呼叫 `_mi_thread_done` 來回收空間。
```c
static void _mi_thread_done(mi_heap_t* heap) {
// check thread-id as on Windows shutdown with FLS the main (exit) thread may call this on thread-local heaps...
if (heap->thread_id != _mi_thread_id()) return;
// abandon the thread local heap
if (_mi_heap_done(heap)) return; // returns true if already ran
}
// Free the thread local default heap (called from `mi_thread_done`)
static bool _mi_heap_done(mi_heap_t* heap) {
if (!mi_heap_is_initialized(heap)) return true;
// reset default heap
_mi_heap_set_default_direct(_mi_is_main_thread() ? &_mi_heap_main : (mi_heap_t*)&_mi_heap_empty);
// switch to backing heap
heap = heap->tld->heap_backing;
if (!mi_heap_is_initialized(heap)) return false;
// delete all non-backing heaps in this thread
mi_heap_t* curr = heap->tld->heaps;
while (curr != NULL) {
mi_heap_t* next = curr->next; // save `next` as `curr` will be freed
if (curr != heap) {
mi_heap_delete(curr);
}
curr = next;
}
// collect if not the main thread
if (heap != &_mi_heap_main) {
_mi_heap_collect_abandon(heap);
}
// merge stats
_mi_stats_done(&heap->tld->stats);
// free if not the main thread
if (heap != &_mi_heap_main) {
// the following assertion does not always hold for huge segments as those are always treated
// as abondened: one may allocate it in one thread, but deallocate in another in which case
// the count can be too large or negative. todo: perhaps not count huge segments? see issue #363
// mi_assert_internal(heap->tld->segments.count == 0 || heap->thread_id != _mi_thread_id());
_mi_os_free(heap, sizeof(mi_thread_data_t), &_mi_stats_main);
}
return false;
}
```
`_mi_thread_done` 會呼叫 `_mi_heap_done` 釋放 heap 空間，在 `_mi_heap_done` 中，會透過 `mi_heap_delete` 刪除 `heap->tld->heaps` 中除了 `heap->tld->heap_backing` 外的其他 heap，這些 heap 是透過 `mi_heap_new` 產生的，在後方會再說明。接著執行 `_mi_heap_collect_abandon`，此函式將 heap 內部的 page 回收，最後 `_mi_os_free` 則實際釋放該 heap 的記憶體空間。
```c
void _mi_heap_collect_abandon(mi_heap_t* heap) {
mi_heap_collect_ex(heap, MI_ABANDON);
}
static void mi_heap_collect_ex(mi_heap_t* heap, mi_collect_t collect)
{
if (heap==NULL || !mi_heap_is_initialized(heap)) return;
_mi_deferred_free(heap, collect >= MI_FORCE);
// note: never reclaim on collect but leave it to threads that need storage to reclaim
if (
#ifdef NDEBUG
collect == MI_FORCE
#else
collect >= MI_FORCE
#endif
&& _mi_is_main_thread() && mi_heap_is_backing(heap) && !heap->no_reclaim)
{
// the main thread is abandoned (end-of-program), try to reclaim all abandoned segments.
// if all memory is freed by now, all segments should be freed.
_mi_abandoned_reclaim_all(heap, &heap->tld->segments);
}
// if abandoning, mark all pages to no longer add to delayed_free
if (collect == MI_ABANDON) {
mi_heap_visit_pages(heap, &mi_heap_page_never_delayed_free, NULL, NULL);
}
// free thread delayed blocks.
// (if abandoning, after this there are no more thread-delayed references into the pages.)
_mi_heap_delayed_free(heap);
// collect retired pages
_mi_heap_collect_retired(heap, collect >= MI_FORCE);
// collect all pages owned by this thread
mi_heap_visit_pages(heap, &mi_heap_page_collect, &collect, NULL);
// collect segment caches
if (collect >= MI_FORCE) {
_mi_segment_thread_collect(&heap->tld->segments);
}
}
```
`_mi_deferred_free` 會呼叫使用者註冊的 `deferred_free` 函式，其下方的 `_mi_abandoned_reclaim_all` 因不是主執行緒不會運行到，`mi_heap_visit_pages` 會逐一走訪 page，並對每個 page 執行給定的函式 (此例為 `mi_heap_page_never_delayed_free`)。
下方 `_mi_heap_delayed_free` 及 `_mi_heap_collect_retired` 回收 delayed free list 以及 retireed page。並再呼叫一次 `mi_heap_visit_pages` 回收所有 page。最後 `_mi_segment_thread_collect` 把存在 cache 中的 segment 釋放。
```c
static bool mi_heap_page_collect(mi_heap_t* heap, mi_page_queue_t* pq, mi_page_t* page, void* arg_collect, void* arg2 ) {
UNUSED(arg2);
UNUSED(heap);
mi_collect_t collect = *((mi_collect_t*)arg_collect);
_mi_page_free_collect(page, collect >= MI_FORCE);
if (mi_page_all_free(page)) {
// no more used blocks, free the page.
// note: this will free retired pages as well.
_mi_page_free(page, pq, collect >= MI_FORCE);
}
else if (collect == MI_ABANDON) {
// still used blocks but the thread is done; abandon the page
_mi_page_abandon(page, pq);
}
return true; // don't break
}
```
在 `mi_heap_collect_ex` 中，`mi_heap_visit_pages` 會將每個 page 透過 `mi_heap_page_collect` 來釋放，`_mi_page_free_collect` 在上方已有介紹，`mi_page_all_free` 檢查 page 內的 block 是否全部釋放，如果是的話則 `_mi_page_free` 會將該 page 從 segment 中釋放；如果該 page 還有可用的 block 在其他 thread 中被使用，則會呼叫 `_mi_page_abandon` 將該 page 設置為 abandon。
```c
// Free a page with no more free blocks
void _mi_page_free(mi_page_t* page, mi_page_queue_t* pq, bool force) {
// no more aligned blocks in here
mi_page_set_has_aligned(page, false);
mi_heap_t* heap = mi_page_heap(page);
// remove from the page list
// (no need to do _mi_heap_delayed_free first as all blocks are already free)
mi_segments_tld_t* segments_tld = &heap->tld->segments;
mi_page_queue_remove(pq, page);
// and free it
mi_page_set_heap(page,NULL);
_mi_segment_page_free(page, force, segments_tld);
}
```
`_mi_page_free` 將 page 從 page queue 中移除，並把 `page->heap` 設為 NULL，最後 `_mi_segment_page_free` 將 page 從 segment 中刪除。
```c
void _mi_segment_page_free(mi_page_t* page, bool force, mi_segments_tld_t* tld)
{
mi_segment_t* segment = _mi_page_segment(page);
// mark it as free now
mi_segment_page_clear(page, tld);
if (segment->used == 0) {
// no more used pages; remove from the free list and free the segment
mi_segment_free(segment, force, tld);
}
else if (segment->used == segment->abandoned) {
// only abandoned pages; remove from free list and abandon
mi_segment_abandon(segment,tld);
}
}
```
`mi_segment_page_clear` 將 page 回收回 segment，與 page 相似，當沒有可用的 page 時，透過 `mi_segment_free` 將 segment 也釋放，否則呼叫 `mi_segment_abandon` 將該 segment 設為 abandon。
```c
// note: can be called on abandoned pages
static mi_slice_t* mi_segment_page_clear(mi_page_t* page, mi_segments_tld_t* tld) {
mi_segment_t* segment = _mi_ptr_segment(page);
size_t inuse = page->capacity * mi_page_block_size(page);
// reset the page memory to reduce memory pressure?
if (!segment->mem_is_pinned && !page->is_reset && mi_option_is_enabled(mi_option_page_reset)) {
size_t psize;
uint8_t* start = _mi_page_start(segment, page, &psize);
page->is_reset = true;
_mi_os_reset(start, psize, tld->stats);
}
// zero the page data, but not the segment fields
page->is_zero_init = false;
ptrdiff_t ofs = offsetof(mi_page_t, capacity);
memset((uint8_t*)page + ofs, 0, sizeof(*page) - ofs);
page->xblock_size = 1;
// and free it
mi_slice_t* slice = mi_segment_span_free_coalesce(mi_page_to_slice(page), tld);
segment->used--;
// cannot assert segment valid as it is called during reclaim
// mi_assert_expensive(mi_segment_is_valid(segment, tld));
return slice;
}
```
`mi_segment_page_clear` 將 page 內的值清空，並透過 `mi_segment_span_free_coalesce` 把 page 放回 `tld->span` 這個 queue 中。
```c
static void mi_segment_free(mi_segment_t* segment, bool force, mi_segments_tld_t* tld) {
// Remove the free pages
mi_slice_t* slice = &segment->slices[0];
const mi_slice_t* end = mi_segment_slices_end(segment);
size_t page_count = 0;
while (slice < end) {
if (slice->xblock_size == 0 && segment->kind != MI_SEGMENT_HUGE) {
mi_segment_span_remove_from_queue(slice, tld);
}
page_count++;
slice = slice + slice->slice_count;
}
if (!force && mi_segment_cache_push(segment, tld)) {
// it is put in our cache
}
else {
// otherwise return it to the OS
mi_segment_os_free(segment, tld);
}
}
```
`mi_segment_free` 檢查 segment 中的所有 `slice`，將這些有用到的 `slice` 放回 span queue 當中，要注意當 `slice` 還未分配出去時，`xblock_size` 用來表示該 `slice` 是否位於 span queue 中，0 表示在 queue 當中，1 則表示不在 queue 當中。`mi_segment_cache_push` 將 segment 放入 cache 中，下次需要 segment 時可以直接從 cache 中取得記憶體。如果必須釋放空間的話 (如 huge segment)，則呼叫 `mi_segment_os_free` 真正釋放開記憶體。
:::info
`page`(`slice`) 中的 `xblock_size` 有許多用途，在 `slice` 階段 (還未要分配給使用者)時，分成兩種：
* `xblock_size == 0` 表示此 slice 目前存放在 `tld->spans` 這個 queue 當中
* `xblock_size == 1` 表示此 slice 目前不存放在 `tld->spans` 這個 queue 當中
當要把 `slice` 分配給使用者時，分配函式 `mi_segment_span_allocate` 內的 `xblock_size` 表示的是此 `slice` (`page`) 實際佔有的空間，也就是所有可分配的空間；在分配後，`xblock_size` 變成這個 `page` 內的每個 block 擁有的空間。
:::
### `mi_heap_*`
mimalloc 提供建立在執行緒內自行管理的 heap，相關函式可參考[連結](https://microsoft.github.io/mimalloc/group__heap.html)。
```c
mi_heap_t* mi_heap_new(void)
{
mi_heap_t* bheap = mi_heap_get_backing();
mi_heap_t* heap = mi_heap_malloc_tp(bheap, mi_heap_t); // todo: OS allocate in secure mode?
if (heap==NULL) return NULL;
_mi_memcpy_aligned(heap, &_mi_heap_empty, sizeof(mi_heap_t));
heap->tld = bheap->tld;
heap->thread_id = _mi_thread_id();
_mi_random_split(&bheap->random, &heap->random);
heap->cookie = _mi_heap_random_next(heap) | 1;
heap->keys[0] = _mi_heap_random_next(heap);
heap->keys[1] = _mi_heap_random_next(heap);
heap->no_reclaim = true; // don't reclaim abandoned pages or otherwise destroy is unsafe
// push on the thread local heaps list
heap->next = heap->tld->heaps;
heap->tld->heaps = heap;
return heap;
}
```
`mi_heap_new` 在目前執行緒中建立一個新的 heap，`mi_heap_get_backing` 回傳目前執行緒的主要 heap，`mi_heap_malloc_tp` 實際分配一個新的 heap 空間，要注意的是分配 heap 與一般分配 block 的程式碼相同是使用 `mi_heap_malloc` 在目前執行緒的主要 heap 的 page 上分配，設置 heap 的過程與 `mi_heap_main_init` 相似，最後再將新增的 heap 放到 `tld->heads` 的 linked list 上。
```c
// Safe delete a heap without freeing any still allocated blocks in that heap.
void mi_heap_delete(mi_heap_t* heap)
{
if (heap==NULL || !mi_heap_is_initialized(heap)) return;
if (!mi_heap_is_backing(heap)) {
// tranfer still used pages to the backing heap
mi_heap_absorb(heap->tld->heap_backing, heap);
}
else {
// the backing heap abandons its pages
_mi_heap_collect_abandon(heap);
}
mi_heap_free(heap);
}
```
`mi_heap_delete` 將 heap 內的 block 回收，其中在 heap 與執行緒主要 heap 不同時呼叫 `mi_heap_absorb`，將要被釋放的 heap 內空間轉移給主要 heap 來管理，而如果是執行緒主要的 heap，則改呼叫 `_mi_heap_collect_abandon` 將內部空間釋放，其作用上方已有解釋，最後 `mi_heap_free` 會實際把 heap 從 `tld->heaps` 上移除，並釋放 heap 空間。
:::info
:information_source: `mi_heap_free` 或許可以改為放在 `if (!mi_heap_is_backing(heap))` 底下。
:::
```c
// Tranfer the pages from one heap to the other
static void mi_heap_absorb(mi_heap_t* heap, mi_heap_t* from) {
if (from==NULL || from->page_count == 0) return;
// reduce the size of the delayed frees
_mi_heap_delayed_free(from);
// transfer all pages by appending the queues; this will set a new heap field
// so threads may do delayed frees in either heap for a while.
// note: appending waits for each page to not be in the `MI_DELAYED_FREEING` state
// so after this only the new heap will get delayed frees
for (size_t i = 0; i <= MI_BIN_FULL; i++) {
mi_page_queue_t* pq = &heap->pages[i];
mi_page_queue_t* append = &from->pages[i];
size_t pcount = _mi_page_queue_append(heap, pq, append);
heap->page_count += pcount;
from->page_count -= pcount;
}
// and do outstanding delayed frees in the `from` heap
// note: be careful here as the `heap` field in all those pages no longer point to `from`,
// turns out to be ok as `_mi_heap_delayed_free` only visits the list and calls a
// the regular `_mi_free_delayed_block` which is safe.
_mi_heap_delayed_free(from);
// and reset the `from` heap
mi_heap_reset_pages(from);
}
```
`mi_heap_absorb` 將有用到的 page queue append 到目標 heap 上，再用 `mi_heap_rest_pages` 把 heap 內的 page 歸 0。
```c
// called from `mi_heap_destroy` and `mi_heap_delete` to free the internal heap resources.
static void mi_heap_free(mi_heap_t* heap) {
if (heap==NULL || !mi_heap_is_initialized(heap)) return;
if (mi_heap_is_backing(heap)) return; // dont free the backing heap
// reset default
if (mi_heap_is_default(heap)) {
_mi_heap_set_default_direct(heap->tld->heap_backing);
}
// remove ourselves from the thread local heaps list
// linear search but we expect the number of heaps to be relatively small
mi_heap_t* prev = NULL;
mi_heap_t* curr = heap->tld->heaps;
while (curr != heap && curr != NULL) {
prev = curr;
curr = curr->next;
}
if (curr == heap) {
if (prev != NULL) { prev->next = heap->next; }
else { heap->tld->heaps = heap->next; }
}
// and free the used memory
mi_free(heap);
}
```
`mi_heap_free` 設定 default heap 並將 heap 從 `tld->heaps` 中移除，最後利用 `mi_free` 釋放 heap 空間，因為 internal heap 與一般的 block 一樣記憶體是存放在 page 當中，故與一般釋放 block 一樣透過 `mi_free` 即可釋放。
```c
void mi_heap_destroy(mi_heap_t* heap) {
if (heap==NULL || !mi_heap_is_initialized(heap)) return;
if (!heap->no_reclaim) {
// don't free in case it may contain reclaimed pages
mi_heap_delete(heap);
}
else {
// free all pages
_mi_heap_destroy_pages(heap);
mi_heap_free(heap);
}
}
void _mi_heap_destroy_pages(mi_heap_t* heap) {
mi_heap_visit_pages(heap, &_mi_heap_page_destroy, NULL, NULL);
mi_heap_reset_pages(heap);
}
```
`mi_heap_destroy` 與 `mi_heap_delete` 不同的地方在於會把 heap 內使用的空間全部釋放，透過呼叫 `_mi_heap_destroy_pages` 來釋放每個 page。`_mi_heap_destroy_page` 會逐一走訪 heap 上的每個 page，並對每個 page 執行 `_mi_heap_page_destroy` 函式：
```c
static bool _mi_heap_page_destroy(mi_heap_t* heap, mi_page_queue_t* pq, mi_page_t* page, void* arg1, void* arg2) {
// ensure no more thread_delayed_free will be added
_mi_page_use_delayed_free(page, MI_NEVER_DELAYED_FREE, false);
/// pretend it is all free now
page->used = 0;
// and free the page
// mi_page_free(page,false);
page->next = NULL;
page->prev = NULL;
_mi_segment_page_free(page,false /* no force? */, &heap->tld->segments);
return true; // keep going
}
```
`_mi_heap_page_destroy` 呼叫 `_mi_segment_page_free` 來將 segment 內的該 page 移除。
Sign in with Wallet
Connect another wallet