add an owner-biased guard to remote free batching
diff --git a/include/mimalloc/atomic.h b/include/mimalloc/atomic.h index 2cbe248..c3ed9dd 100644 --- a/include/mimalloc/atomic.h +++ b/include/mimalloc/atomic.h
@@ -74,6 +74,7 @@ #define mi_atomic_store_release(p,x) mi_atomic(store_explicit)(p,x,mi_memory_order(release)) #define mi_atomic_store_relaxed(p,x) mi_atomic(store_explicit)(p,x,mi_memory_order(relaxed)) #define mi_atomic_exchange_relaxed(p,x) mi_atomic(exchange_explicit)(p,x,mi_memory_order(relaxed)) +#define mi_atomic_exchange_acquire(p,x) mi_atomic(exchange_explicit)(p,x,mi_memory_order(acquire)) #define mi_atomic_exchange_release(p,x) mi_atomic(exchange_explicit)(p,x,mi_memory_order(release)) #define mi_atomic_exchange_acq_rel(p,x) mi_atomic(exchange_explicit)(p,x,mi_memory_order(acq_rel))
diff --git a/include/mimalloc/types.h b/include/mimalloc/types.h index b4fb21e..6000523 100644 --- a/include/mimalloc/types.h +++ b/include/mimalloc/types.h
@@ -810,6 +810,7 @@ size_t batched_total; bool collecting; mi_free_batch_entry_t entries[MI_FREE_BATCH_COUNT]; + _Atomic(size_t) guard; } mi_free_batch_t; // Thread local data
diff --git a/src/alloc/free.c b/src/alloc/free.c index 61bb702..5ac6a9a 100644 --- a/src/alloc/free.c +++ b/src/alloc/free.c
@@ -669,21 +669,44 @@ tld->free_batch.heap = heap; } -static inline void mi_free_batch_push(mi_tld_t* tld, mi_free_batch_entry_t* batch, mi_page_t* page, mi_block_t* block) { +static inline bool mi_free_batch_try_acquire(mi_tld_t* tld) { + // Owner only: 0 is owner-released; a foreign drainer must release with 2. + const size_t previous = mi_atomic_exchange_relaxed(&tld->free_batch.guard, 1); + if mi_likely(previous == 0) return true; + if (previous != 2) return false; + // Acquire the foreign release through the preceding RMW's release sequence. + return (mi_atomic_load_acquire(&tld->free_batch.guard) == 1); +} + +static inline void mi_free_batch_release(mi_tld_t* tld) { + mi_atomic_store_release(&tld->free_batch.guard, 0); +} + +static mi_decl_noinline void mi_free_batch_collect_finish(mi_tld_t* tld) { + _mi_free_collect(tld); + mi_free_batch_release(tld); +} + +// The push and miss paths release the guard before returning. +static inline void mi_free_batch_push(mi_tld_t* tld, mi_free_batch_entry_t* batch, mi_page_t* page, mi_block_t* block, size_t block_size) { // Until publication these blocks remain counted as used and keep the page alive. mi_block_set_next(page, block, batch->head); batch->head = block; batch->count++; - tld->free_batch.batched_total += mi_page_block_size(page); + tld->free_batch.batched_total += block_size; if mi_unlikely(tld->free_batch.batched_total >= MI_FREE_BATCH_BYTES) { - _mi_free_collect(tld); + mi_free_batch_collect_finish(tld); + } + else { + mi_free_batch_release(tld); } } -static mi_decl_noinline void mi_free_batch_miss(mi_tld_t* tld, mi_free_batch_entry_t* batch, mi_page_t* page, mi_block_t* block) { +static mi_decl_noinline void mi_free_batch_miss(mi_tld_t* tld, mi_free_batch_entry_t* batch, mi_page_t* page, mi_block_t* block, size_t block_size) { // Destroyable heaps cannot retain pointers in other threads' caches. // Detached metadata pages must also stay on the immediate path. - if (mi_page_heap(page) != tld->free_batch.heap || mi_page_thread_id(page) == MI_THREADID_DETACHED) { + if mi_unlikely(mi_page_heap(page) != tld->free_batch.heap || mi_page_thread_id(page) == MI_THREADID_DETACHED) { + mi_free_batch_release(tld); mi_free_block_mt_publish(page, block, block, true); return; } @@ -697,14 +720,19 @@ } batch->page = page; batch->tail = block; - mi_free_batch_push(tld, batch, page, block); + mi_free_batch_push(tld, batch, page, block, block_size); } static mi_decl_noinline void mi_free_block_mt_batch(mi_page_t* page, mi_block_t* block) { mi_theap_t* const theap = _mi_theap_default(); mi_tld_t* const tld = (theap == NULL ? NULL : theap->tld); const size_t block_size = mi_page_block_size(page); - if (tld == NULL || tld->free_batch.heap == NULL || block_size > MI_MEDIUM_MAX_OBJ_SIZE) { + if mi_unlikely(tld == NULL || tld->free_batch.heap == NULL || block_size > MI_MEDIUM_MAX_OBJ_SIZE) { + mi_free_block_mt_publish(page, block, block, true); + return; + } + + if mi_unlikely(!mi_free_batch_try_acquire(tld)) { mi_free_block_mt_publish(page, block, block, true); return; } @@ -714,10 +742,10 @@ key ^= key >> 17; mi_free_batch_entry_t* const batch = &tld->free_batch.entries[key & (MI_FREE_BATCH_COUNT - 1)]; if mi_likely(batch->page == page) { - mi_free_batch_push(tld, batch, page, block); + mi_free_batch_push(tld, batch, page, block, block_size); } else { - mi_free_batch_miss(tld, batch, page, block); + mi_free_batch_miss(tld, batch, page, block, block_size); } }
diff --git a/src/heap/init.c b/src/heap/init.c index b8803d0..da085b3 100644 --- a/src/heap/init.c +++ b/src/heap/init.c
@@ -129,7 +129,7 @@ false, // recurse false, // is_in_threadpool MI_MEMID_STATIC, // memid - { NULL, 0, false, { { NULL, NULL, NULL, 0 } } } + { NULL, 0, false, { { NULL, NULL, NULL, 0 } }, MI_ATOMIC_VAR_INIT(0) } }; #ifdef __cplusplus @@ -271,6 +271,7 @@ tld->free_batch.heap = NULL; tld->free_batch.batched_total = 0; tld->free_batch.collecting = false; + mi_atomic_store_relaxed(&tld->free_batch.guard, 0); mi_memzero(tld->free_batch.entries, sizeof(tld->free_batch.entries)); mi_lock_init(&tld->theaps_lock); if (tld->thread_id == MI_THREADID_DETACHED) {
diff --git a/test/test-free-batch.c b/test/test-free-batch.c index 7d01f1f..5dfccb6 100644 --- a/test/test-free-batch.c +++ b/test/test-free-batch.c
@@ -48,6 +48,7 @@ const unsigned char* p = (const unsigned char*)blocks[i]; if (p[0] != i % 251 || p[sizes[i]-1] != i % 251) return false; mi_free(blocks[i]); + if (mi_atomic_load_relaxed(&tld->free_batch.guard) != 0) return false; if (tld->free_batch.batched_total >= MI_FREE_BATCH_BYTES) return false; if (tld->free_batch.batched_total != 0) pending = true; } @@ -106,6 +107,47 @@ return disposable != NULL && allocate_blocks() && mi_run_on_thread(free_blocks); } +static bool free_with_busy_guard(void) { + mi_thread_init(); + mi_collect(true); + mi_tld_t* const tld = _mi_theap_default()->tld; + mi_free(blocks[0]); + const size_t pending = tld->free_batch.batched_total; + if (pending == 0) return false; + + if (!mi_free_batch_try_acquire(tld)) return false; + mi_free(blocks[1]); + const bool bypassed = (tld->free_batch.batched_total == pending && + mi_atomic_load_relaxed(&tld->free_batch.guard) == 1); + mi_free_batch_release(tld); + + mi_heap_t* const heap = tld->free_batch.heap; + tld->free_batch.heap = NULL; + tld->free_batch.collecting = true; + if (!mi_free_batch_try_acquire(tld)) return false; + mi_free(blocks[2]); + _mi_free_collect(tld); + const bool reentered = (tld->free_batch.batched_total == pending && + mi_atomic_load_relaxed(&tld->free_batch.guard) == 1); + tld->free_batch.collecting = false; + tld->free_batch.heap = heap; + mi_free_batch_release(tld); + + mi_atomic_store_release(&tld->free_batch.guard, 2); + mi_free(blocks[3]); + const bool handed_back = (tld->free_batch.batched_total > pending && + mi_atomic_load_relaxed(&tld->free_batch.guard) == 0); + for (size_t i = 4; i < block_count; i++) mi_free(blocks[i]); + mi_collect(true); + return bypassed && reentered && handed_back && tld->free_batch.batched_total == 0; +} + +static bool test_busy_guard(void) { + mode = 0; + block_count = 128; + return allocate_blocks() && mi_run_on_thread(free_with_busy_guard) && all_freed(); +} + static bool departing_owner(void) { const bool allocated = allocate_blocks(); mi_atomic_store_release(&owner_ready, allocated ? 1 : 2); @@ -153,6 +195,7 @@ CHECK("free without thread initialization", test_uninitialized_free()); CHECK("remote free abandoned owner", test_abandoned_owner()); CHECK("destroy heap after remote frees", test_destroyed_heap()); + CHECK("remote free busy guard and reentry", test_busy_guard()); CHECK("remote free concurrent owner exit", test_concurrent_owner_exit()); return print_test_summary(); }