#include "mimalloc.h"
#include "mimalloc/prim/prim-tls.h"
#include "mimalloc/util/stats.h"
#include "mimalloc/util/memid.h"
#include "mimalloc/alloc/page.h"
#include "mimalloc/arena/arena-alloc.h"
#include "mimalloc/profile/sample-guarded.h"
#include "mimalloc/arena/arena-page.h"
#include "arena-page.h"
static void mi_heap_qsbr_collect_delayed(mi_heap_t* heap, size_t max_pages, bool destroy);
typedef struct mi_heap_visit_info_s {
mi_heap_t* heap;
mi_block_visit_fun* visitor;
void* arg;
bool visit_blocks;
bool abandoned_only;
} mi_heap_visit_info_t;
static bool mi_heap_visit_page(mi_page_t* page, const mi_heap_visit_info_t* vinfo) {
mi_heap_area_t area;
const bool abandoned = mi_page_is_abandoned(page);
const bool claimed = (abandoned && mi_page_claim_ownership(page));
if (!abandoned) { _mi_page_free_collect(page, true); } if (claimed && _mi_abandoned_page_unown(page, NULL)) return true; _mi_heap_area_init(&area, page);
mi_assert_internal(vinfo->heap == mi_page_heap(page));
if (!vinfo->visitor(vinfo->heap, &area, NULL, area.block_size, vinfo->arg)) {
return false; }
if (vinfo->visit_blocks) {
return _mi_theap_area_visit_blocks(&area, page, vinfo->visitor, vinfo->arg); }
else {
return true; }
}
static bool mi_heap_visit_page_at(size_t slice_index, size_t slice_count, mi_arena_t* arena, void* arg) {
MI_UNUSED(slice_count);
const mi_heap_visit_info_t* vinfo = (const mi_heap_visit_info_t*)arg;
mi_page_t* page = mi_arena_page_at_slice(arena, slice_index);
return mi_heap_visit_page(page, vinfo); }
static bool mi_heap_visit_arena(mi_arena_t* arena, const void* arg, void** result) {
MI_UNUSED(result);
const mi_heap_visit_info_t* vinfo = (const mi_heap_visit_info_t*)arg;
mi_heap_visit_info_t visit_info = *vinfo;
mi_heap_t* const heap = vinfo->heap;
mi_arena_pages_t* arena_pages = mi_heap_arena_pages(heap, arena);
if (arena_pages == NULL) return true; if (vinfo->abandoned_only) {
for (size_t bin = 0; bin < MI_ARENA_BIN_COUNT; bin++) {
if (mi_atomic_load_relaxed(&heap->abandoned_count[bin]) > 0) {
if (!_mi_bitmap_forall_set(arena_pages->pages_abandoned[bin], &mi_heap_visit_page_at, arena, &visit_info)) return false; }
}
return true; }
else {
return _mi_bitmap_forall_set(arena_pages->pages, &mi_heap_visit_page_at, arena, &visit_info); }
}
static bool mi_heap_visit_owned_os_blocks(mi_heap_t* heap, bool visit_blocks, mi_block_visit_fun* visitor, void* arg) {
const mi_heap_visit_info_t visit_info = { heap, visitor, arg, visit_blocks, false };
for (mi_theap_t* theap = heap->theaps; theap != NULL; theap = theap->hnext) {
if (theap->page_count_os == 0) continue;
for (size_t bin = 0; bin <= MI_BIN_FULL; bin++) {
mi_page_t* page = theap->pages[bin].first;
while (page != NULL) {
mi_page_t* const next = page->next;
if (page->memid.memkind != MI_MEM_ARENA && !mi_heap_visit_page(page, &visit_info)) return false;
page = next;
}
}
}
return true;
}
static bool mi_heap_visit_blocks_locked(mi_heap_t* heap, bool abandoned_only, bool visit_blocks, mi_block_visit_fun* visitor, void* arg) {
const mi_heap_visit_info_t visit_info = { heap, visitor, arg, visit_blocks, abandoned_only };
bool ok = mi_forall_arenas(heap, NULL, 0, &mi_heap_visit_arena, &visit_info, NULL);
if (!ok) return false;
mi_page_t* page = NULL;
#if MI_QSBR
if (!abandoned_only) {
page = mi_atomic_load_ptr_relaxed(mi_page_t, &heap->qsbr_delayed);
while (ok && page != NULL) {
mi_page_t* next = page->next;
if (page->memid.memkind != MI_MEM_ARENA) { ok = mi_heap_visit_page(page, &visit_info); }
page = next;
}
}
#endif
mi_lock(&heap->os_abandoned_pages_lock) {
page = heap->os_abandoned_pages;
}
while (ok && page != NULL) {
mi_page_t* next = page->next; ok = mi_heap_visit_page(page, &visit_info);
page = next;
}
if (ok && !abandoned_only) {
ok = mi_heap_visit_owned_os_blocks(heap, visit_blocks, visitor, arg);
}
return ok;
}
bool _mi_heap_visit_blocks(mi_heap_t* heap, bool abandoned_only, bool visit_blocks, mi_block_visit_fun* visitor, void* arg) {
mi_assert(visitor!=NULL);
if (visitor==NULL) return false;
if (!mi_heap_handle_is_valid(heap)) return false;
bool ok = false;
mi_lock(&heap->theaps_lock) {
ok = mi_heap_visit_blocks_locked(heap, abandoned_only, visit_blocks, visitor, arg);
}
return ok;
}
bool mi_heap_visit_blocks(mi_heap_t* heap, bool visit_blocks, mi_block_visit_fun* visitor, void* arg) {
return _mi_heap_visit_blocks(heap, false, visit_blocks, visitor, arg);
}
bool mi_heap_visit_abandoned_blocks(mi_heap_t* heap, bool visit_blocks, mi_block_visit_fun* visitor, void* arg) {
return _mi_heap_visit_blocks(heap, true, visit_blocks, visitor, arg);
}
typedef struct mi_heap_move_info_s {
mi_heap_t* heap;
mi_heap_t* heap_target; mi_theap_t* theap_target;
bool retry; } mi_heap_move_info_t;
static void mi_heap_move_page(const mi_heap_move_info_t* info, mi_page_t* page) {
mi_heap_t* const heap = info->heap;
mi_heap_t* heap_target = info->heap_target;
mi_assert_internal(mi_page_is_owned(page));
mi_assert_internal(mi_page_is_abandoned(page));
mi_assert_internal(mi_page_heap(page) == heap);
mi_assert_internal(heap_target == NULL || !mi_heap_qsbr_is_enabled(heap));
_mi_page_free_collect(page, true); _mi_page_qsbr_clear(page); _mi_arenas_page_unabandon(page, NULL);
if (mi_page_used(page)==0) {
_mi_arenas_page_free_direct(page, NULL);
}
else if (heap_target==NULL) {
#if MI_GUARDED
_mi_page_unguard_all(page); #endif
_mi_page_free_collect(page, false); mi_page_used_reset(page); _mi_arenas_page_free_direct(page, NULL);
}
else {
const size_t sbin = _mi_page_stats_bin(page);
mi_arena_t* arena = NULL;
size_t slice_index = 0;
if (page->memid.memkind == MI_MEM_ARENA) {
size_t slice_count;
mi_arena_pages_t* arena_pages = NULL;
arena = _mi_page_arena_pages(page, &slice_index, &slice_count, &arena_pages);
mi_assert_internal(mi_bitmap_is_set(arena_pages->pages, slice_index));
mi_bitmap_clear(arena_pages->pages, slice_index);
}
else {
mi_assert_internal(mi_memid_is_os(page->memid) && page->next == NULL);
mi_atomic_decrement_relaxed(&heap->os_page_count);
mi_atomic_increment_relaxed(&heap_target->os_page_count);
}
mi_heap_stat_decrease(heap, page_bins[sbin], 1);
mi_heap_stat_decrease(heap, pages, 1);
mi_theap_t* theap_target = info->theap_target;
if (arena != NULL) {
mi_arena_pages_t* arena_pages_target = _mi_heap_ensure_arena_pages(heap_target, arena);
if mi_unlikely(arena_pages_target==NULL) {
heap_target = _mi_arena_heap_main(arena);
theap_target = mi_heap_theap(heap_target); arena_pages_target = _mi_heap_ensure_arena_pages(heap_target, arena);
mi_assert_internal(arena_pages_target!=NULL);
}
mi_assert_internal(mi_bitmap_is_clear(arena_pages_target->pages, slice_index));
mi_bitmap_set(arena_pages_target->pages, slice_index);
}
page->heap = heap_target;
#if MI_DEBUG>0
mi_atomic_store_relaxed(&page->debug_fill_preserve, mi_atomic_load_relaxed(&heap_target->debug_fill_preserve));
#endif
mi_theap_stat_increase(theap_target, page_bins[sbin], 1);
mi_theap_stat_increase(theap_target, pages, 1);
_mi_arenas_page_abandon(page, theap_target);
}
}
static bool mi_heap_move_page_at(size_t slice_index, size_t slice_count, mi_arena_t* arena, void* arg) {
MI_UNUSED(slice_count);
mi_heap_move_info_t* const info = (mi_heap_move_info_t*)arg;
mi_bitmap_t* const pages = mi_heap_arena_pages(info->heap, arena)->pages;
if (!mi_bitmap_clear(pages, slice_index)) return true; mi_page_t* const page = mi_arena_page_at_slice(arena, slice_index);
const bool claimed = mi_page_claim_ownership(page);
mi_bitmap_set(pages, slice_index);
if (claimed) { mi_heap_move_page(info, page); }
else { info->retry = true; } return true;
}
static bool mi_heap_move_arena_pages(mi_arena_t* arena, const void* arg, void** result) {
MI_UNUSED(result);
mi_heap_move_info_t* const info = (mi_heap_move_info_t*)arg;
mi_arena_pages_t* const arena_pages = mi_heap_arena_pages(info->heap, arena);
if (arena_pages != NULL) {
_mi_bitmap_forall_set(arena_pages->pages, &mi_heap_move_page_at, arena, info);
}
return true; }
static mi_page_t* mi_heap_os_abandoned_page_try_claim(mi_heap_move_info_t* info) {
mi_heap_t* const heap = info->heap;
mi_page_t* claimed = NULL;
mi_lock(&heap->os_abandoned_pages_lock) {
for (mi_page_t* page = heap->os_abandoned_pages; page != NULL && claimed == NULL; page = page->next) {
if (mi_page_claim_ownership(page)) { claimed = page; }
else { info->retry = true; }
}
}
return claimed;
}
#if MI_DEBUG>1
static bool mi_heap_has_pages(mi_heap_t* heap) {
for (size_t i = 0; i < MI_MAX_ARENAS; i++) {
mi_arena_pages_t* const arena_pages = mi_atomic_load_ptr_relaxed(mi_arena_pages_t, &heap->arena_pages[i]);
if (arena_pages != NULL && !mi_bitmap_is_all_clear(arena_pages->pages)) return true;
}
bool has_os_pages = false;
mi_lock(&heap->os_abandoned_pages_lock) {
has_os_pages = (heap->os_abandoned_pages != NULL);
}
return has_os_pages;
}
#endif
static void mi_heap_move_pages(mi_heap_t* heap, mi_heap_t* heap_target) {
mi_assert_internal(heap->is_deleted && heap->theaps == NULL);
#if MI_QSBR
mi_assert_internal(mi_atomic_load_ptr_relaxed(mi_page_t, &heap->qsbr_delayed) == NULL); #endif
mi_heap_move_info_t info = { heap, heap_target, (heap_target != NULL ? _mi_heap_theap(heap_target) : NULL), false };
do {
info.retry = false;
mi_forall_arenas(heap, NULL, 0, &mi_heap_move_arena_pages, &info, NULL);
mi_page_t* page;
while ((page = mi_heap_os_abandoned_page_try_claim(&info)) != NULL) {
mi_heap_move_page(&info, page);
}
if (mi_atomic_load_acquire(&heap->os_page_count) > 0) { info.retry = true; } if (info.retry) { _mi_prim_thread_yield(); } } while (info.retry);
#if MI_DEBUG>1
mi_assert_internal(!mi_heap_has_pages(heap));
for (size_t i = 0; i < MI_ARENA_BIN_COUNT; i++) {
mi_assert_internal(mi_atomic_load_relaxed(&heap->abandoned_count[i])==0);
}
#endif
}
void _mi_heap_move_pages(mi_heap_t* heap_from, mi_heap_t* heap_to) {
if (mi_is_heap_main(heap_from)) return;
if (heap_to==NULL) { heap_to = heap_from->subproc->heap_main; }
mi_heap_move_pages(heap_from, heap_to);
}
void _mi_heap_destroy_pages(mi_heap_t* heap_from) {
if (mi_is_heap_main(heap_from)) return;
mi_heap_qsbr_collect_delayed(heap_from, SIZE_MAX, true); mi_heap_move_pages(heap_from, NULL);
}
#if MI_QSBR
static void mi_heap_qsbr_delayed_append(mi_heap_t* heap, mi_page_t* first, mi_page_t* last) {
mi_assert_internal(first != NULL && last != NULL && last->next == NULL);
if (heap->qsbr_delayed_last == NULL) {
mi_atomic_store_ptr_relaxed(mi_page_t, &heap->qsbr_delayed, first);
}
else {
heap->qsbr_delayed_last->next = first;
}
heap->qsbr_delayed_last = last;
}
void _mi_heap_qsbr_delayed_enqueue(mi_page_t* page) {
mi_assert_internal(mi_page_is_owned(page) && mi_page_is_abandoned(page));
mi_assert_internal(mi_page_all_free(page) && mi_page_is_singleton(page));
mi_assert_internal(!mi_page_is_abandoned_mapped(page));
mi_assert_internal(page->next == NULL && page->prev == NULL);
mi_assert_internal(!mi_page_qsbr_is_in_queue(page) && page->qsbr_next == NULL && page->qsbr_prev == NULL);
mi_assert_internal(!mi_page_qsbr_is_clear(&page->qsbr));
mi_heap_t* heap = mi_page_heap(page);
mi_assert_internal(mi_heap_qsbr_is_enabled(heap));
_mi_page_update_stats(page);
mi_lock(&heap->qsbr_delayed_lock) {
mi_heap_qsbr_delayed_append(heap, page, page);
}
}
static void mi_heap_qsbr_collect_delayed(mi_heap_t* heap, size_t max_pages, bool destroy) {
if (mi_atomic_load_ptr_relaxed(mi_page_t, &heap->qsbr_delayed) == NULL) return;
if (!mi_lock_try_acquire(&heap->qsbr_delayed_lock)) return;
mi_page_t* const first = mi_atomic_load_ptr_relaxed(mi_page_t, &heap->qsbr_delayed);
if (first == NULL) {
mi_lock_release(&heap->qsbr_delayed_lock);
return;
}
mi_page_t* last = first;
while (--max_pages > 0 && last->next != NULL) { last = last->next; }
mi_atomic_store_ptr_relaxed(mi_page_t, &heap->qsbr_delayed, last->next);
if (last->next == NULL) { heap->qsbr_delayed_last = NULL; }
last->next = NULL;
mi_lock_release(&heap->qsbr_delayed_lock);
mi_page_t* delayed_first = NULL;
mi_page_t* delayed_last = NULL;
mi_page_t* next;
for (mi_page_t* page = first; page != NULL; page = next) {
next = page->next;
page->next = NULL;
if (destroy || !_mi_page_qsbr_should_delay(page)) {
_mi_page_qsbr_clear(page);
_mi_arenas_page_free_direct(page, NULL);
}
else {
if (delayed_last == NULL) { delayed_first = page; }
else { delayed_last->next = page; }
delayed_last = page;
}
}
if (delayed_first != NULL) {
mi_lock(&heap->qsbr_delayed_lock) {
mi_heap_qsbr_delayed_append(heap, delayed_first, delayed_last);
}
}
}
void _mi_heap_qsbr_collect_delayed(mi_heap_t* heap) {
mi_heap_qsbr_collect_delayed(heap, 8, false);
}
static void mi_heap_collect_abandoned_page(mi_page_t* page) {
mi_assert_internal(mi_page_is_owned(page));
_mi_page_free_collect(page, true);
if (mi_page_all_free(page) && !_mi_page_qsbr_should_delay(page)) {
_mi_arenas_page_unabandon(page, NULL);
_mi_arenas_page_free(page, NULL); }
else {
_mi_abandoned_page_unown(page, NULL); }
}
static bool mi_heap_collect_abandoned_page_at(size_t slice_index, size_t slice_count, mi_arena_t* arena, void* arg) {
MI_UNUSED(slice_count);
mi_heap_t* const heap = (mi_heap_t*)arg;
mi_bitmap_t* const pages = mi_heap_arena_pages(heap, arena)->pages;
if (!mi_bitmap_clear(pages, slice_index)) return true; mi_page_t* const page = mi_arena_page_at_slice(arena, slice_index);
const bool claimed = (mi_page_is_abandoned(page) && mi_page_claim_ownership(page));
mi_bitmap_set(pages, slice_index);
if (claimed) { mi_heap_collect_abandoned_page(page); }
return true;
}
static bool mi_heap_collect_abandoned_arena(mi_arena_t* arena, const void* arg, void** result) {
MI_UNUSED(result);
mi_heap_t* heap = (mi_heap_t*)arg;
mi_arena_pages_t* arena_pages = mi_heap_arena_pages(heap, arena);
if (arena_pages == NULL) return true;
return _mi_bitmap_forall_set(arena_pages->pages, &mi_heap_collect_abandoned_page_at, arena, heap);
}
static mi_page_t* mi_heap_os_abandoned_page_claim_next(mi_heap_t* heap, mi_page_t* page) {
mi_page_t* claimed = NULL;
mi_lock(&heap->os_abandoned_pages_lock) {
for (mi_page_t* p = (page==NULL ? heap->os_abandoned_pages : page->next); p != NULL && claimed == NULL; p = p->next) {
if (mi_page_claim_ownership(p)) { claimed = p; }
}
}
return claimed;
}
void _mi_heap_collect_abandoned(mi_heap_t* heap) {
mi_assert_internal(heap != NULL);
mi_lock(&heap->theaps_lock) {
mi_forall_arenas(heap, NULL, 0, &mi_heap_collect_abandoned_arena, heap, NULL);
mi_page_t* page = mi_heap_os_abandoned_page_claim_next(heap, NULL);
while (page != NULL) {
mi_page_t* const next = mi_heap_os_abandoned_page_claim_next(heap, page); mi_heap_collect_abandoned_page(page);
page = next;
}
mi_heap_qsbr_collect_delayed(heap, SIZE_MAX, false);
}
}
#else
static void mi_heap_qsbr_collect_delayed(mi_heap_t* heap, size_t max_pages, bool destroy) {
MI_UNUSED(heap); MI_UNUSED(max_pages); MI_UNUSED(destroy);
return;
}
void _mi_heap_qsbr_collect_delayed(mi_heap_t* heap) {
MI_UNUSED(heap);
return;
}
void _mi_heap_collect_abandoned(mi_heap_t* heap) {
MI_UNUSED(heap);
return;
}
#endif