add length to mi_thread_free_t on 64-bit with 48 VA bits; avoids walking the xthread_free list on mi_free_block_mt
diff --git a/include/mimalloc/internal.h b/include/mimalloc/internal.h index e832444..1267989 100644 --- a/include/mimalloc/internal.h +++ b/include/mimalloc/internal.h
@@ -260,10 +260,10 @@ void _mi_arenas_unsafe_destroy_all(mi_subproc_t* subproc); mi_page_t* _mi_arenas_page_alloc(mi_theap_t* theap, size_t block_size, size_t page_alignment); -void _mi_arenas_page_free(mi_page_t* page, mi_theap_t* current_theapx /* can be NULL */); +void _mi_arenas_page_free(mi_page_t* page, size_t pending, mi_theap_t* current_theapx /* can be NULL */); void _mi_arenas_page_abandon(mi_page_t* page, mi_theap_t* current_theap); void _mi_arenas_page_unabandon(mi_page_t* page, mi_theap_t* current_theapx /* can be NULL */); -bool _mi_arenas_page_try_reabandon_to_mapped(mi_page_t* page); +bool _mi_arenas_page_try_reabandon_to_mapped(mi_page_t* page, size_t pending); // "page-map.c" bool _mi_page_map_init(void); @@ -283,7 +283,7 @@ void _mi_page_abandon(mi_page_t* page, mi_page_queue_t* pq); // abandon the page, to be picked up by another thread... void _mi_deferred_free(mi_theap_t* theap, bool force); bool _mi_page_free_collect(mi_page_t* page, bool force); // returns `true` if cross-thread free'd blocks were collected -mi_block_t* _mi_page_free_collect_partly(mi_page_t* page, mi_block_t* head); +mi_thread_free_t _mi_page_free_collect_partly(mi_page_t* page, mi_thread_free_t thead); mi_decl_nodiscard bool _mi_page_init(mi_theap_t* theap, mi_page_t* page); bool _mi_page_queue_is_valid(mi_theap_t* theap, const mi_page_queue_t* pq); void _mi_page_update_stats(mi_page_t* page); @@ -977,12 +977,15 @@ #endif } +static inline bool mi_page_all_free_ex(const mi_page_t* page, size_t pending) { + mi_assert_internal(page != NULL); + return (mi_page_used(page)==pending); +} // are all blocks in a page freed? // note: needs up-to-date used count, (as the `xthread_free` list may not be empty). see `_mi_page_collect_free`. static inline bool mi_page_all_free(const mi_page_t* page) { - mi_assert_internal(page != NULL); - return (mi_page_used(page)==0); + return mi_page_all_free_ex(page,0); } // are there immediately available blocks, i.e. blocks available on the free list. @@ -1000,17 +1003,26 @@ } -static inline bool mi_page_is_full(const mi_page_t* page) { - const bool full = (page->reserved == mi_page_used(page)); +static inline bool mi_page_is_full_ex(const mi_page_t* page, size_t pending) { + const bool full = (pending == 0 && page->reserved == mi_page_used(page)); mi_assert_internal(!full || page->free == NULL); return full; } +static inline bool mi_page_is_full(const mi_page_t* page) { + return mi_page_is_full_ex(page, 0); +} + // is more than 7/8th of a page in use? -static inline bool mi_page_is_mostly_used(const mi_page_t* page) { +static inline bool mi_page_is_mostly_used_ex(const mi_page_t* page, size_t pending) { if (page==NULL) return true; uint16_t frac = page->reserved / 8U; - return (page->reserved - mi_page_used(page) <= frac); + return (page->reserved - mi_page_used(page) - pending <= frac); +} + +// is more than 7/8th of a page in use? +static inline bool mi_page_is_mostly_used(const mi_page_t* page) { + return mi_page_is_mostly_used_ex(page, 0); } // is more than (n-1)/n'th of a page in use? @@ -1170,22 +1182,52 @@ // Thread free list and ownership //----------------------------------------------------------- +#if MI_INTPTR_BITS - MI_MAX_VABITS >= 16 +#define MI_THREAD_FREE_HAS_LEN 1 +#else +#define MI_THREAD_FREE_HAS_LEN 0 +#endif + // Thread free flag helpers static inline mi_block_t* mi_tf_block(mi_thread_free_t tf) { + #if MI_THREAD_FREE_HAS_LEN + tf >>= 16; + #endif return (mi_block_t*)(tf & ~1); } static inline bool mi_tf_is_owned(mi_thread_free_t tf) { + #if MI_THREAD_FREE_HAS_LEN + tf >>= 16; + #endif return ((tf & 1) == 1); } -static inline mi_thread_free_t mi_tf_create(mi_block_t* block, bool owned) { - const uintptr_t base = (uintptr_t)block | (owned ? 1 : 0); - return (mi_thread_free_t)base; +static inline size_t mi_tf_len(mi_thread_free_t tf) { + #if MI_THREAD_FREE_HAS_LEN + return (tf & 0xFFFF); + #else + return 0; + #endif +} + +static inline mi_thread_free_t mi_tf_create(mi_block_t* block, bool owned, size_t len) { + mi_thread_free_t tf = (mi_thread_free_t)block | (owned ? 1 : 0); + #if MI_THREAD_FREE_HAS_LEN + tf = (tf<<16 | (len & 0xFFFF)); + #else + MI_UNUSED(len); + #endif + mi_assert_internal(mi_tf_block(tf) == block); + return tf; } static inline mi_thread_free_t mi_tf_set_owned(mi_thread_free_t tf, bool owned) { - return mi_tf_create(mi_tf_block(tf), owned); + return mi_tf_create(mi_tf_block(tf), owned, mi_tf_len(tf)); +} + +static inline mi_thread_free_t mi_tf_set_len(mi_thread_free_t tf, size_t len) { + return mi_tf_create(mi_tf_block(tf), mi_tf_is_owned(tf), len); } // Thread free access @@ -1193,6 +1235,11 @@ return mi_tf_block(mi_atomic_load_relaxed(&((mi_page_t*)page)->xthread_free)); } +// for assertions +static inline size_t mi_page_pending(const mi_page_t* page) { + return mi_tf_len(mi_atomic_load_relaxed(&((mi_page_t*)page)->xthread_free)); +} + // are there any available blocks? static inline bool mi_page_has_any_available(const mi_page_t* page) { mi_assert_internal(page != NULL && page->reserved > 0); @@ -1206,8 +1253,13 @@ // get ownership; returns true if the page was not owned before. static inline bool mi_page_claim_ownership(mi_page_t* page) { - const uintptr_t old = mi_atomic_or_acq_rel(&page->xthread_free, (uintptr_t)1); - return ((old&1)==0); + #if MI_THREAD_FREE_HAS_LEN + const uintptr_t mask = (uintptr_t)1 << 16; + #else + const uintptr_t mask = (uintptr_t)1; + #endif + const uintptr_t old = mi_atomic_or_acq_rel(&page->xthread_free, mask); + return ((old&mask)==0); }
diff --git a/src/arena.c b/src/arena.c index 1b7c8cb..5f6921c 100644 --- a/src/arena.c +++ b/src/arena.c
@@ -637,13 +637,13 @@ _mi_page_free_collect(page, false); // update used if (mi_page_all_free(page)) { // it may become free just before unowning it _mi_arenas_page_unabandon(page, current_theapx); - _mi_arenas_page_free(page, current_theapx); + _mi_arenas_page_free(page, 0, current_theapx); return true; } tf_old = mi_atomic_load_relaxed(&page->xthread_free); } mi_assert_internal(mi_tf_block(tf_old)==NULL); - tf_new = mi_tf_create(NULL, false); + tf_new = mi_tf_create(NULL, false, 0); } while (!mi_atomic_cas_weak_acq_rel(&page->xthread_free, &tf_old, tf_new)); return false; } @@ -1157,7 +1157,7 @@ mi_assert_internal(page->memid.memkind != MI_MEM_ARENA || page->memid.mem.arena.slice_count == slice_count); if (!_mi_page_init(theap, page)) { - _mi_arenas_page_free(page,theap); + _mi_arenas_page_free(page,0,theap); return NULL; } @@ -1184,7 +1184,7 @@ mi_assert(page->reserved == 1); if (!_mi_page_init(theap, page)) { - _mi_arenas_page_free(page,theap); + _mi_arenas_page_free(page,0,theap); return NULL; } @@ -1229,7 +1229,7 @@ mi_assert_internal(_mi_is_aligned(mi_page_slice_start(page), MI_PAGE_ALIGN)); mi_assert_internal(_mi_ptr_page(mi_page_start(page))==page); mi_assert_internal(mi_page_is_owned(page)); - mi_assert_internal(mi_page_all_free(page)); + // mi_assert_internal(mi_page_all_free(page)); mi_assert_internal(page->next==NULL && page->prev==NULL); #if MI_DEBUG>1 @@ -1297,11 +1297,12 @@ _mi_arenas_free( mi_page_subproc(page), mi_page_slice_start(page), mi_page_full_size(page), page->memid); } -void _mi_arenas_page_free(mi_page_t* page, mi_theap_t* current_theapx) { +void _mi_arenas_page_free(mi_page_t* page, size_t pending, mi_theap_t* current_theapx) { + MI_UNUSED_RELEASE(pending); mi_assert_internal(_mi_is_aligned(mi_page_slice_start(page), MI_PAGE_ALIGN)); mi_assert_internal(_mi_ptr_page(mi_page_start(page))==page); mi_assert_internal(mi_page_is_owned(page)); - mi_assert_internal(mi_page_all_free(page)); + mi_assert_internal(mi_page_all_free_ex(page, pending)); mi_assert_internal(mi_page_is_abandoned(page)); mi_assert_internal(page->next==NULL && page->prev==NULL); mi_assert_internal(mi_theap_matches_thread(current_theapx)); @@ -1309,8 +1310,10 @@ mi_heap_t* const heap = mi_page_heap(page); mi_theapx_stat_decrease(heap, current_theapx, page_bins[_mi_page_stats_bin(page)], 1); mi_theapx_stat_decrease(heap, current_theapx, pages, 1); - _mi_page_free_collect(page,false); // update used count for cross-thread free's - _mi_page_update_stats(page); // and update the stats + if (pending==0) { + _mi_page_free_collect(page,false); // update used count for cross-thread free's + } + _mi_page_update_stats(page); // and update the stats mi_arenas_page_free_prim(page); } @@ -1324,6 +1327,7 @@ mi_assert_internal(mi_page_is_owned(page)); mi_assert_internal(mi_page_is_abandoned(page)); mi_assert_internal(!mi_page_all_free(page)); + // mi_assert_internal(mi_page_pending(page)==0); // can happen in a reabandon mi_assert_internal(page->next==NULL && page->prev == NULL); mi_assert_internal(mi_theap_matches_thread(current_theapx)); // mi_assert_internal(current_theap == _mi_page_associated_theap(page)); @@ -1379,16 +1383,16 @@ // this is called from `free.c:mi_free_try_collect_mt` only. -bool _mi_arenas_page_try_reabandon_to_mapped(mi_page_t* page) { +bool _mi_arenas_page_try_reabandon_to_mapped(mi_page_t* page, size_t pending) { mi_assert_internal(_mi_is_aligned(mi_page_slice_start(page), MI_PAGE_ALIGN)); mi_assert_internal(_mi_ptr_page(mi_page_start(page))==page); mi_assert_internal(mi_page_is_owned(page)); mi_assert_internal(mi_page_is_abandoned(page)); mi_assert_internal(!mi_page_is_abandoned_mapped(page)); - mi_assert_internal(!mi_page_is_full(page)); - mi_assert_internal(!mi_page_all_free(page)); + mi_assert_internal(!mi_page_is_full_ex(page, pending)); + mi_assert_internal(!mi_page_all_free_ex(page, pending)); mi_assert_internal(!mi_page_is_singleton(page)); - if (mi_page_is_full(page) || mi_page_is_abandoned_mapped(page) || page->memid.memkind != MI_MEM_ARENA) { + if (mi_page_is_full_ex(page, pending) || mi_page_is_abandoned_mapped(page) || page->memid.memkind != MI_MEM_ARENA) { return false; } else { @@ -2570,7 +2574,7 @@ if (mi_page_used(page)==0) { // free the page - _mi_arenas_page_free(page, theap); + _mi_arenas_page_free(page, 0, theap); } else if (heap_target==NULL) { #if MI_GUARDED @@ -2578,7 +2582,7 @@ #endif // destroy the page mi_page_used_reset(page); // note: invariant `|local_free| + |free| == reserved - used` does not hold in this case - _mi_arenas_page_free(page, theap); + _mi_arenas_page_free(page, 0, theap); } else { // move the page to `heap_target` as an abandoned page
diff --git a/src/free.c b/src/free.c index 4e7070f..4780fc0 100644 --- a/src/free.c +++ b/src/free.c
@@ -59,7 +59,7 @@ } // Forward declaration for multi-threaded collect -static void mi_decl_noinline mi_free_try_collect_mt(mi_page_t* page, mi_block_t* mt_free, bool allow_reclaim) mi_attr_noexcept; +static void mi_decl_noinline mi_free_try_collect_mt(mi_page_t* page, mi_thread_free_t tfree, bool allow_reclaim) mi_attr_noexcept; // Free a block multi-threaded #if defined(_MSC_VER) @@ -86,8 +86,9 @@ mi_thread_free_t tf_new; mi_thread_free_t tf_old = mi_atomic_load_relaxed(&page->xthread_free); do { + const size_t pending = mi_tf_len(tf_old); mi_block_set_next(page, block, mi_tf_block(tf_old)); - tf_new = mi_tf_create(block, true); + tf_new = mi_tf_create(block, true, pending+1); } while (!mi_atomic_cas_weak_acq_rel(&page->xthread_free, &tf_old, tf_new)); // and atomically try to collect the page if it was abandoned @@ -95,7 +96,7 @@ if (is_newly_owned) { mi_assert_internal(mi_page_is_abandoned(page)); // mi_assert_internal(!mi_page_is_abandoned_mapped(page)); - mi_free_try_collect_mt(page, block, allow_reclaim); + mi_free_try_collect_mt(page, tf_new, allow_reclaim); } } @@ -440,52 +441,53 @@ // -------------------------------------------------------------------------------------------- // Helper for mi_free_try_collect_mt: free if the page has no more used blocks (this is updated by `_mi_page_free_collect(_partly)`) -static bool mi_abandoned_page_try_free(mi_page_t* page) +static bool mi_abandoned_page_try_free(mi_page_t* page, size_t pending) { - if (!mi_page_all_free(page)) return false; + if (!mi_page_all_free_ex(page, pending)) return false; // first remove it from the abandoned pages in the arena (if mapped, this might wait for any readers to finish) _mi_arenas_page_unabandon(page,NULL); - _mi_arenas_page_free(page,NULL); // we can now free the page directly + _mi_arenas_page_free(page,pending,NULL); // we can now free the page directly return true; } // Helper for mi_free_try_collect_mt: try if we can reabandon a previously abandoned mostly full page to be mapped -static bool mi_abandoned_page_try_reabandon_to_mapped(mi_page_t* page) +static bool mi_abandoned_page_try_reabandon_to_mapped(mi_page_t* page, size_t pending) { // if the page is unmapped, try to reabandon so it can possibly be mapped and found for allocations // We only reabandon if a full page starts to have enough blocks available to prevent immediate re-abandon of a full page - if (mi_page_is_mostly_used(page)) return false; // not too full + if (mi_page_is_mostly_used_ex(page, pending)) return false; // not too full if (page->memid.memkind != MI_MEM_ARENA || mi_page_is_abandoned_mapped(page)) return false; // and not already mapped (or unmappable) - mi_assert(!mi_page_is_full(page)); - return _mi_arenas_page_try_reabandon_to_mapped(page); + mi_assert(!mi_page_is_full_ex(page, pending)); + return _mi_arenas_page_try_reabandon_to_mapped(page, pending); } // Release ownership of a page. This may free or reabandoned the page if other blocks are concurrently // freed in the meantime. Returns `true` if the page was freed. // By passing the captured `expected_thread_free`, we can often avoid calling `mi_page_free_collect`. -static void mi_abandoned_page_unown_from_free(mi_page_t* page, mi_block_t* page_thread_free) { +static void mi_abandoned_page_unown_from_free(mi_page_t* page, mi_thread_free_t tfree) { mi_assert_internal(mi_page_is_owned(page)); mi_assert_internal(mi_page_is_abandoned(page)); mi_assert_internal(!mi_page_all_free(page)); // try to cas atomically the original free list (`mt_free`) back with the ownership cleared. - mi_thread_free_t tf_expect = mi_tf_create(page_thread_free,true); - mi_thread_free_t tf_new = mi_tf_set_owned(tf_expect,false); + mi_thread_free_t tf_expect = tfree; + mi_thread_free_t tf_new = mi_tf_set_owned(tfree,false); while mi_unlikely(!mi_atomic_cas_strong_acq_rel(&page->xthread_free, &tf_expect, tf_new)) { mi_assert_internal(mi_tf_is_owned(tf_expect)); // while the xthread_free list is not empty.. while (mi_tf_block(tf_expect) != NULL) { // if there were concurrent updates to the thread-free list, we retry to free or reabandon to mapped (if it became !mosty_used). _mi_page_free_collect(page,false); // update used count - if (mi_abandoned_page_try_free(page)) return; - if (mi_abandoned_page_try_reabandon_to_mapped(page)) return; + if (mi_abandoned_page_try_free(page,0)) return; + if (mi_abandoned_page_try_reabandon_to_mapped(page,0)) return; // otherwise continue un-owning tf_expect = mi_atomic_load_acquire(&page->xthread_free); } // and try again to release ownership mi_subproc_stat_counter_increase(mi_page_subproc(page), pages_unown_cas_retry, 1); mi_assert_internal(mi_tf_block(tf_expect)==NULL); - tf_new = mi_tf_create(NULL, false); + mi_assert_internal(mi_tf_len(tf_expect)==0); + tf_new = mi_tf_create(NULL, false, 0); } } @@ -497,7 +499,7 @@ } // Helper for mi_free_try_collect_mt: try to reclaim the page for ourselves -static mi_decl_noinline bool mi_abandoned_page_try_reclaim(mi_page_t* page, long reclaim_on_free) mi_attr_noexcept +static mi_decl_noinline bool mi_abandoned_page_try_reclaim(mi_page_t* page, long reclaim_on_free, size_t pending) mi_attr_noexcept { // note: reclaiming can improve benchmarks like `larson` or `rbtree-ck` a lot even in the single-threaded case, // since free-ing from an owned page avoids atomic operations. However, if we reclaim too eagerly in @@ -507,7 +509,7 @@ // pages when we allocate a fresh page). mi_assert_internal(mi_page_is_owned(page)); mi_assert_internal(mi_page_is_abandoned(page)); - mi_assert_internal(!mi_page_all_free(page)); + mi_assert_internal(!mi_page_all_free_ex(page, pending)); mi_assert_internal(page->block_size <= MI_MEDIUM_MAX_OBJ_SIZE); mi_assert_internal(reclaim_on_free >= 0); @@ -528,7 +530,7 @@ } else if (reclaim_on_free == 1 && // if cross-thread is allowed !theap->tld->is_in_threadpool && // and we are not part of a threadpool - !mi_page_is_mostly_used(page) && // and the page is not too full + !mi_page_is_mostly_used_ex(page, pending) && // and the page is not too full _mi_arena_memid_is_suitable(page->memid, _mi_theap_heap(theap)->exclusive_arena)) { // and it fits our memory // across threads max_reclaim = _mi_option_get_fast(mi_option_page_cross_thread_max_reclaim); @@ -549,41 +551,46 @@ // We freed a block in an abandoned page (that was not owned). Try to collect -static void mi_decl_noinline mi_free_try_collect_mt(mi_page_t* page, mi_block_t* mt_free, bool allow_reclaim) mi_attr_noexcept +static void mi_decl_noinline mi_free_try_collect_mt(mi_page_t* page, mi_thread_free_t tfree, bool allow_reclaim) mi_attr_noexcept { mi_assert_internal(mi_page_is_owned(page)); mi_assert_internal(mi_page_is_abandoned(page)); - mi_assert_internal(mt_free != NULL); + mi_assert_internal(mi_tf_block(tfree) != NULL); // mi_assert_internal(!allow_reclaim || _mi_subproc() == mi_page_subproc(page)); // never reclaim across subprocesses // we own the page now, and it is safe to collect the thread atomic free list - if (page->block_size <= MI_SMALL_SIZE_MAX) { - // use the `_partly` version to avoid atomic operations since we already have the `mt_free` pointing into the thread free list - // (after this the `used` count might be too high (as some blocks may have been concurrently added to the thread free list and are yet uncounted). - // however, if the page became completely free, the used count is guaranteed to be 0.) - mi_assert_internal(page->reserved>=16); // below this even one freed block goes from full to no longer mostly used. - mt_free = _mi_page_free_collect_partly(page, mt_free); + const size_t pending = mi_tf_len(tfree); + if (pending==0) { + // !MI_THREAD_FREE_HAS_LEN, we need to update the used count + if (page->block_size <= MI_SMALL_SIZE_MAX) { + // use the `_partly` version to avoid atomic operations since we already have the `mt_free` pointing into the thread free list + // (after this the `used` count might be too high (as some blocks may have been concurrently added to the thread free list and are yet uncounted). + // however, if the page became completely free, the used count is guaranteed to be 0.) + mi_assert_internal(page->reserved>=16); // below this even one freed block goes from full to no longer mostly used. + tfree = _mi_page_free_collect_partly(page, tfree); + } + else { + // for larger blocks we use the regular collect + _mi_page_free_collect(page,false /* no force */); + tfree = mi_tf_create(NULL,mi_tf_is_owned(tfree),0); // set to NULL + } } - else { - // for larger blocks we use the regular collect - _mi_page_free_collect(page,false /* no force */); - mt_free = NULL; // expected page->xthread_free value after collection - } + const long reclaim_on_free = (allow_reclaim ? _mi_option_get_fast(mi_option_page_reclaim_on_free) : -1); #if MI_DEBUG > 1 - if (mi_page_is_singleton(page)) { mi_assert_internal(mi_page_all_free(page)); } - if (mi_page_is_full(page)) { mi_assert(mi_page_is_mostly_used(page)); } + if (mi_page_is_singleton(page)) { mi_assert_internal(mi_page_all_free_ex(page,pending)); } + if (mi_page_is_full_ex(page,pending)) { mi_assert(mi_page_is_mostly_used_ex(page,pending)); } #endif // try to: 1. free it, 2. reclaim it, or 3. reabandon it to be mapped - if (mi_abandoned_page_try_free(page)) return; + if (mi_abandoned_page_try_free(page, pending)) return; if (page->block_size <= MI_MEDIUM_MAX_OBJ_SIZE && reclaim_on_free >= 0) { // early test for better codegen - if (mi_abandoned_page_try_reclaim(page, reclaim_on_free)) return; + if (mi_abandoned_page_try_reclaim(page, reclaim_on_free, pending)) return; } - if (mi_abandoned_page_try_reabandon_to_mapped(page)) return; + if (mi_abandoned_page_try_reabandon_to_mapped(page, pending)) return; // otherwise unown the page again - mi_abandoned_page_unown_from_free(page, mt_free); + mi_abandoned_page_unown_from_free(page, tfree); }
diff --git a/src/page.c b/src/page.c index e4d0f77..ac528f3 100644 --- a/src/page.c +++ b/src/page.c
@@ -157,9 +157,8 @@ #endif #if MI_SAMPLE==1 /* for ==2, the countdown is already done at every `alloc.c:mi_page_alloc_zero` */ -static void mi_theap_adjust_sample_countdown(mi_theap_t* theap, mi_page_t* page, size_t alloc_count) +static void mi_theap_adjust_sample_countdown(mi_theap_t* theap, mi_page_t* page, size_t alloc_count) { - mi_assert_internal(mi_page_alloc_count(page) + mi_page_last_used(page) >= mi_page_used(page)); mi_assert_internal(theap!=NULL); if (theap->sample_rate==0) return; @@ -318,18 +317,30 @@ Page collect the `local_free` and `thread_free` lists ----------------------------------------------------------- */ -static void mi_page_thread_collect_to_local(mi_page_t* page, mi_block_t* head) +static void mi_page_thread_collect_to_local(mi_page_t* page, mi_block_t* head, size_t pending) { if (head == NULL) return; - // find the last block in the list -- also to get a proper use count (without data races) - size_t max_count = page->capacity; // cannot collect more than capacity - size_t count = 1; - mi_block_t* last = head; - mi_block_t* next; - while ((next = mi_block_next(page, last)) != NULL && count <= max_count) { - count++; - last = next; + const size_t max_count = page->capacity; // cannot collect more than capacity + size_t count; + mi_block_t* last; + #if !MI_SECURE + if (pending > 0 && page->local_free == NULL) { // MI_THREAD_FREE_HAS_LEN + // skip visiting the list if we already know the pending count and the local free list is empty + count = pending; + last = NULL; + } + else + #endif + { + // find the last block in the list -- also to get a proper use count (without data races) + count = 1; + last = head; + mi_block_t* next; + while ((next = mi_block_next(page, last)) != NULL && count <= max_count) { + count++; + last = next; + } } // if `count > max_count` there was a memory corruption (possibly infinite list due to double multi-threaded free) @@ -344,7 +355,13 @@ } // and append the current local free list - mi_block_set_next(page, last, page->local_free); + if (last!=NULL) { + mi_block_set_next(page, last, page->local_free); + } + else { + // case where we have MI_THREAD_FREE_HAS_LEN and an empty local_free list + mi_assert_internal(page->local_free==NULL); + } page->local_free = head; // update counts now @@ -358,18 +375,19 @@ static bool mi_page_thread_free_collect(mi_page_t* page) { // atomically capture the thread free list + mi_thread_free_t thead = mi_atomic_load_relaxed(&page->xthread_free); mi_block_t* head; - mi_thread_free_t tfreex; - mi_thread_free_t tfree = mi_atomic_load_relaxed(&page->xthread_free); + mi_thread_free_t tnull; + mi_assert_internal(mi_tf_is_owned(thead)); do { - head = mi_tf_block(tfree); + head = mi_tf_block(thead); if mi_likely(head == NULL) return false; // return if the list is empty - tfreex = mi_tf_create(NULL,mi_tf_is_owned(tfree)); // set the thread free list to NULL - } while (!mi_atomic_cas_weak_acq_rel(&page->xthread_free, &tfree, tfreex)); // release is enough? + tnull = mi_tf_create(NULL,mi_tf_is_owned(thead),0); // set the thread free list to NULL + } while (!mi_atomic_cas_weak_acq_rel(&page->xthread_free, &thead, tnull)); // release is enough? mi_assert_internal(head != NULL); // and move it to the local list - mi_page_thread_collect_to_local(page, head); + mi_page_thread_collect_to_local(page, head, mi_tf_len(thead)); return true; } @@ -425,13 +443,19 @@ // `head` must be in the `xthread_free` list. It will not collect `head` itself // so the `used` count is not fully updated in general. However, if the `head` is // the last remaining element, it will be collected and the used count will become `0` (so `mi_page_all_free` becomes true). -mi_block_t* _mi_page_free_collect_partly(mi_page_t* page, mi_block_t* head) { +mi_thread_free_t _mi_page_free_collect_partly(mi_page_t* page, mi_thread_free_t thead) { mi_assert_internal(mi_page_is_owned(page)); - if (head == NULL) return NULL; - mi_block_t* next = mi_block_next(page,head); // we cannot collect the head element itself as `page->thread_free` may point to it (and we want to avoid atomic ops) - if (next != NULL) { + mi_assert_internal(mi_tf_is_owned(thead)); + mi_block_t* const head = mi_tf_block(thead); + if (head == NULL) return thead; + mi_block_t* const tail = mi_block_next(page,head); // we cannot collect the head element itself as `page->thread_free` may point to it (and we want to avoid atomic ops) + if (tail != NULL) { + // cut the head list + const size_t tail_len = (mi_tf_len(thead) > 0 ? mi_tf_len(thead) - 1 : 0); mi_block_set_next(page, head, NULL); - mi_page_thread_collect_to_local(page, next); + thead = mi_tf_set_len(thead, 0); + // and collect the tail + mi_page_thread_collect_to_local(page, tail, tail_len); if (page->local_free != NULL && page->free == NULL) { page->free = page->local_free; page->local_free = NULL; @@ -444,10 +468,10 @@ mi_assert_internal(mi_tf_block(mi_atomic_load_relaxed(&page->xthread_free)) == head); mi_assert_internal(mi_block_next(page,head) == NULL); _mi_page_free_collect(page, false); // collect the final element - return NULL; + return mi_tf_create(NULL, mi_tf_is_owned(thead), 0); } else { - return head; + return thead; } } @@ -592,7 +616,7 @@ // and free it mi_theap_t* theap = mi_page_theap(page); mi_assert_internal(theap!=NULL); mi_page_set_theap(page,NULL); - _mi_arenas_page_free(page, theap); + _mi_arenas_page_free(page, 0, theap); // TODO: is pending correct? // _mi_arenas_collect(false, false, theap->tld); // allow purging } @@ -920,7 +944,7 @@ mi_assert_internal(mi_page_used(page) == 0); mi_assert_internal(page->xused.used_alloc == 0); mi_assert_internal(mi_page_is_owned(page)); - mi_assert_internal(page->xthread_free == 1); + mi_assert_internal(page->xthread_free == mi_tf_create(NULL, true, 0)); mi_assert_internal(page->next == NULL); mi_assert_internal(page->prev == NULL); mi_assert_internal(page->retire_expire == 0);