add length to free and local_free lists
diff --git a/include/mimalloc/internal.h b/include/mimalloc/internal.h index e18a9d9..78dff9b 100644 --- a/include/mimalloc/internal.h +++ b/include/mimalloc/internal.h
@@ -949,18 +949,107 @@ return (slice_committed == 0 ? mi_page_size(page) : slice_committed - mi_page_slice_offset_of(page,0)); } + +// The number of blocks that are committed in a page. +// If `MI_HAS_FREE_LEN` the capacity is stored in the _lower_ 16 bits of the `xthread_id` +// (which is loaded anyway in the `mi_free` fast path) while the thread id (with the page +// flags in its lowest bits) is shifted up by 16 bits. This way both the thread id test +// (`eor xtid, tid, pxtid lsr #16`) and the capacity (`cmp .., pxtid uxth`) come for free +// as shifted/extended register operands. +#if MI_HAS_FREE_LEN +#define MI_PAGE_TID_SHIFT (16) +#define MI_PAGE_CAPACITY_MASK ((mi_threadid_t)0xFFFF) +#else +#define MI_PAGE_TID_SHIFT (0) +#define MI_PAGE_CAPACITY_MASK ((mi_threadid_t)0) +#endif + +// the page flags as they are stored in the `xthread_id` +#define MI_PAGE_XFLAG_MASK ((mi_threadid_t)MI_PAGE_FLAG_MASK << MI_PAGE_TID_SHIFT) + +static inline size_t mi_page_capacity(const mi_page_t* page) { + #if !MI_HAS_FREE_LEN + return page->xcapacity; + #else + const mi_threadid_t xtid = mi_atomic_load_relaxed(&((mi_page_t*)page)->xthread_id); + return (size_t)(xtid & MI_PAGE_CAPACITY_MASK); + #endif +} + +// Increase the capacity by `delta` blocks. +static inline void mi_page_capacity_increase(mi_page_t* page, size_t delta) { + mi_assert_internal(mi_page_capacity(page) + delta <= page->reserved); + #if !MI_HAS_FREE_LEN + page->xcapacity += (uint16_t)delta; + #else + // note: we can use an atomic add as the capacity never overflows into the thread id bits + // (and a concurrent thread may still set the `MI_PAGE_HAS_INTERIOR_POINTERS` flag) + mi_atomic_add_relaxed(&page->xthread_id, (mi_threadid_t)delta); + #endif +} + static inline size_t mi_page_used(const mi_page_t* page) { mi_assert_internal(page != NULL); + #if !MI_HAS_FREE_LEN return mi_xused_used_count(page->xused); + #else + mi_assert_internal(mi_page_capacity(page) >= mi_free_len(page->free) + mi_free_len(page->local_free)); + return mi_page_capacity(page) - mi_free_len(page->free) - mi_free_len(page->local_free); + #endif } +// Set the `used` count to zero (only used when destroying a page with live blocks) +static inline size_t mi_page_alloc_count(const mi_page_t* page); + static inline void mi_page_used_reset(mi_page_t* page) { + #if !MI_HAS_FREE_LEN page->xused = mi_xused_used_reset(page->xused); + #else + // pretend the capacity equals the free'd blocks so that `mi_page_used(page) == 0` + const size_t acc = mi_page_alloc_count(page); + const size_t freed = mi_free_len(page->free) + mi_free_len(page->local_free); + mi_threadid_t xtid_old = mi_atomic_load_relaxed(&page->xthread_id); + mi_threadid_t xtid; + do { + xtid = (xtid_old & ~MI_PAGE_CAPACITY_MASK) | (mi_threadid_t)freed; + } while (!mi_atomic_cas_weak_release(&page->xthread_id, &xtid_old, xtid)); + page->xused.used_alloc = (page->xused.used_alloc & ~MI_ZU(0xFFFFFFFF)) | (acc << 16) | mi_free_len(page->free); + mi_assert_internal(mi_page_used(page) == 0); + #endif } -static inline size_t mi_page_alloc_count(const mi_page_t* page) { - return mi_xused_alloc_count(page->xused); +static inline size_t mi_page_last_used(const mi_page_t* page); + +#if MI_HAS_FREE_LEN +// The length of the `free` list at the last refill (bits 0..15 of `used_alloc`, unused in this mode). +static inline size_t mi_page_last_free_len(const mi_page_t* page) { + return (page->xused.used_alloc & MI_FREE_LEN_MAX); } +#endif + +static inline size_t mi_page_alloc_count(const mi_page_t* page) { + #if !MI_HAS_FREE_LEN + return mi_xused_alloc_count(page->xused); + #else + // blocks are only ever allocated from the `free` list (which shrinks by one per allocation), + // so the count since the last refill is exactly `last_free_len - |free|`. + const size_t acc = mi_xused_alloc_count(page->xused) + ((mi_page_last_free_len(page) - mi_free_len(page->free)) & MI_FREE_LEN_MAX); + return (acc > MI_FREE_LEN_MAX ? MI_FREE_LEN_MAX : acc); + #endif +} + +#if MI_HAS_FREE_LEN +// Refill the `free` list: accumulate the allocations done since the last refill and set the new baseline. +static inline void mi_page_set_free(mi_page_t* page, mi_free_t newfree) { + const size_t acc = mi_page_alloc_count(page); + page->xused.used_alloc = (page->xused.used_alloc & ~MI_ZU(0xFFFFFFFF)) | (acc << 16) | mi_free_len(newfree); + page->free = newfree; +} +#else +static inline void mi_page_set_free(mi_page_t* page, mi_free_t newfree) { + page->free = newfree; +} +#endif static inline size_t mi_page_last_used(const mi_page_t* page) { #if MI_SIZE_SIZE >= 8 @@ -989,21 +1078,21 @@ // are there immediately available blocks, i.e. blocks available on the free list. static inline bool mi_page_immediate_available(const mi_page_t* page) { mi_assert_internal(page != NULL); - return (page->free != NULL); + return (!mi_free_is_empty(page->free)); } // is the page not yet used up to its reserved space? static inline bool mi_page_is_expandable(const mi_page_t* page) { mi_assert_internal(page != NULL); - mi_assert_internal(page->capacity <= page->reserved); - return (page->capacity < page->reserved); + mi_assert_internal(mi_page_capacity(page) <= page->reserved); + return (mi_page_capacity(page) < page->reserved); } static inline bool mi_page_is_full(const mi_page_t* page) { const bool full = (page->reserved == mi_page_used(page)); - mi_assert_internal(!full || page->free == NULL); + mi_assert_internal(!full || mi_free_is_empty(page->free)); return full; } @@ -1044,8 +1133,10 @@ //----------------------------------------------------------- // Thread id of thread that owns this page (with flags in the bottom 2 bits) +// (if `MI_HAS_FREE_LEN` the lower 16 bits hold the page capacity and are shifted out) static inline mi_threadid_t mi_page_xthread_id(const mi_page_t* page) { - return mi_atomic_load_relaxed(&((mi_page_t*)page)->xthread_id); + const mi_threadid_t xtid = mi_atomic_load_relaxed(&((mi_page_t*)page)->xthread_id); + return (xtid >> MI_PAGE_TID_SHIFT); } // Plain thread id of the thread that owns this page @@ -1058,10 +1149,11 @@ } static inline bool mi_page_flags_set(mi_page_t* page, bool set, mi_page_flags_t newflag) { - mi_page_flags_t old; - if (set) { old = mi_atomic_or_relaxed(&page->xthread_id, newflag); } - else { old = mi_atomic_and_relaxed(&page->xthread_id, ~newflag); } - return ((old & newflag) == newflag); + const mi_threadid_t xflag = ((mi_threadid_t)newflag << MI_PAGE_TID_SHIFT); + mi_threadid_t old; + if (set) { old = mi_atomic_or_relaxed(&page->xthread_id, xflag); } + else { old = mi_atomic_and_relaxed(&page->xthread_id, ~xflag); } + return ((old & xflag) == xflag); } static inline bool mi_page_is_in_full(const mi_page_t* page) { @@ -1075,7 +1167,7 @@ mi_theap_t* const theap = page->theap; mi_assert_internal(theap!=NULL); if (theap != NULL) { - mi_assert_internal(page->capacity==page->reserved); + mi_assert_internal(mi_page_capacity(page)==page->reserved); const size_t size = page->reserved * mi_page_block_size(page); if (in_full) { theap->pages_full_size += size; } else { mi_assert_internal(size <= theap->pages_full_size); theap->pages_full_size -= size; } @@ -1096,12 +1188,13 @@ page->theap = theap; const mi_threadid_t tid = (theap == NULL ? MI_THREADID_ABANDONED : theap->tld->thread_id); mi_assert_internal((tid & MI_PAGE_FLAG_MASK) == 0); + mi_assert_internal(((tid << MI_PAGE_TID_SHIFT) >> MI_PAGE_TID_SHIFT) == tid); // thread id's must fit when shifted up // we need to use an atomic cas since a concurrent thread may still set the MI_PAGE_HAS_INTERIOR_POINTERS flag (see `alloc_aligned.c`). - mi_threadid_t xtid_old = mi_page_xthread_id(page); + mi_threadid_t xtid_old = mi_atomic_load_relaxed(&page->xthread_id); mi_threadid_t xtid; do { - xtid = tid | (xtid_old & MI_PAGE_FLAG_MASK); + xtid = (tid << MI_PAGE_TID_SHIFT) | (xtid_old & (MI_PAGE_XFLAG_MASK | MI_PAGE_CAPACITY_MASK)); } while (!mi_atomic_cas_weak_release(&page->xthread_id, &xtid_old, xtid)); } @@ -1116,12 +1209,12 @@ static inline void mi_page_set_abandoned_mapped(mi_page_t* page) { mi_assert_internal(mi_page_is_abandoned(page)); - mi_atomic_or_relaxed(&page->xthread_id, (mi_threadid_t)MI_THREADID_ABANDONED_MAPPED); + mi_atomic_or_relaxed(&page->xthread_id, (mi_threadid_t)MI_THREADID_ABANDONED_MAPPED << MI_PAGE_TID_SHIFT); } static inline void mi_page_clear_abandoned_mapped(mi_page_t* page) { mi_assert_internal(mi_page_is_abandoned_mapped(page)); - mi_atomic_and_relaxed(&page->xthread_id, (mi_threadid_t)MI_PAGE_FLAG_MASK); + mi_atomic_and_relaxed(&page->xthread_id, MI_PAGE_XFLAG_MASK | MI_PAGE_CAPACITY_MASK); } @@ -1296,29 +1389,29 @@ // return (_mi_ptr_page(p) == _mi_ptr_page(q)); } -static inline void* mi_ptr_decode(const void* null, const mi_encoded_t x, const uintptr_t* keys) { +static inline uintptr_t mi_ptr_decode(const void* null, const mi_encoded_t x, const uintptr_t* keys) { const uintptr_t k1 = keys[0]; #if MI_PAGE_KEY_COUNT==2 const uintptr_t k2 = keys[1]; #else const uintptr_t k2 = mi_rotr(k1,13); #endif - void* p = (void*)(mi_rotr(x - k1, k1) ^ k2); - return (p==null ? NULL : p); + uintptr_t p = mi_rotr(x - k1, k1) ^ k2; + return (p==((uintptr_t)null) ? 0 : p); } -static inline mi_encoded_t mi_ptr_encode(const void* null, const void* p, const uintptr_t* keys) { +static inline mi_encoded_t mi_ptr_encode(const void* null, uintptr_t p, const uintptr_t* keys) { const uintptr_t k1 = keys[0]; #if MI_PAGE_KEY_COUNT==2 const uintptr_t k2 = keys[1]; #else const uintptr_t k2 = mi_rotr(k1,13); #endif - const uintptr_t x = (uintptr_t)(p==NULL ? null : p); + const uintptr_t x = (uintptr_t)(p==0 ? (uintptr_t)null : p); return mi_rotl(x ^ k2, k1) + k1; } -static inline uint32_t mi_ptr_encode_canary(const void* null, const void* p, const uintptr_t* keys) { +static inline uint32_t mi_ptr_encode_canary(const void* null, uintptr_t p, const uintptr_t* keys) { const uint32_t x = (uint32_t)(mi_ptr_encode(null,p,keys)); // make the lowest byte 0 to prevent spurious read overflows which could be a security issue (issue #951) // also clear bit 9 which we set only when a block is freed. @@ -1337,20 +1430,20 @@ return (canary == mi_ptr_encode_canary_freed()); } -static inline mi_block_t* mi_block_nextx( const void* null, const mi_block_t* block, const uintptr_t* keys ) { +static inline mi_free_t mi_block_nextx( const void* null, const mi_block_t* block, const uintptr_t* keys ) { mi_track_mem_defined(block,sizeof(mi_block_t)); - mi_block_t* next; + mi_free_t next; #if MI_ENCODE_FREELIST - next = (mi_block_t*)mi_ptr_decode(null, block->next, keys); + next = mi_ptr_decode(null, block->next, keys); #else MI_UNUSED(keys); MI_UNUSED(null); - next = (mi_block_t*)block->next; + next = block->next; #endif mi_track_mem_noaccess(block,sizeof(mi_block_t)); return next; } -static inline void mi_block_set_nextx(const void* null, mi_block_t* block, const mi_block_t* next, const uintptr_t* keys) { +static inline void mi_block_set_nextx(const void* null, mi_block_t* block, mi_free_t next, const uintptr_t* keys) { mi_track_mem_undefined(block,sizeof(mi_block_t)); #if MI_ENCODE_FREELIST block->next = mi_ptr_encode(null, next, keys); @@ -1361,15 +1454,16 @@ mi_track_mem_noaccess(block,sizeof(mi_block_t)); } -mi_block_t* _mi_block_next_is_corrupted(const mi_page_t* page, const mi_block_t* block, const mi_block_t* next); // in options.c +mi_free_t _mi_block_next_is_corrupted(const mi_page_t* page, const mi_block_t* block, const mi_block_t* next); // in options.c -static inline mi_block_t* mi_block_next(const mi_page_t* page, const mi_block_t* block) { +static inline mi_free_t mi_block_next(const mi_page_t* page, const mi_block_t* block) { #if MI_ENCODE_FREELIST - mi_block_t* next = mi_block_nextx(page,block,page->keys); + mi_free_t next = mi_block_nextx(page,block,page->keys); // check for free list corruption: is `next` at least in the same page? // todo: check if `next` is `page->block_size` aligned? - if mi_unlikely(next!=NULL && !mi_page_contains_address(page,next)) { - return _mi_block_next_is_corrupted(page,block,next); // returns NULL + mi_block_t* next_block = mi_free_block(next); + if mi_unlikely(next_block!=NULL && !mi_page_contains_address(page,next_block)) { + return _mi_block_next_is_corrupted(page,block,next_block); // returns NULL } return next; #else @@ -1378,7 +1472,7 @@ #endif } -static inline void mi_block_set_next(const mi_page_t* page, mi_block_t* block, const mi_block_t* next) { +static inline void mi_block_set_next(const mi_page_t* page, mi_block_t* block, mi_free_t next) { #if MI_ENCODE_FREELIST mi_block_set_nextx(page,block,next, page->keys); #else
diff --git a/include/mimalloc/types.h b/include/mimalloc/types.h index 745084c..2dd47ab 100644 --- a/include/mimalloc/types.h +++ b/include/mimalloc/types.h
@@ -414,6 +414,34 @@ // This way we can push a block on the thread free list and try to claim ownership atomically in `free.c:mi_free_block_mt`. typedef uintptr_t mi_thread_free_t; +// A free list is a `mi_free_t`: on 64-bit systems where a user-space address needs at most +// 48 bits, the lower 16 bits hold the _length_ of the list while the upper bits hold the +// pointer to the first block. Together with the `capacity` (which is stored in the lower 16 +// bits of `xthread_id`) the `used` count can be derived as `capacity - |free| - |local_free|` +// and we no longer need to update a `used` field in the `mi_malloc` fast path. +#if MI_INTPTR_BITS - MI_MAX_VABITS >= 16 +#define MI_HAS_FREE_LEN (16) +#else +#define MI_HAS_FREE_LEN (0) +#endif + +typedef uintptr_t mi_free_t; + +#define MI_FREE_NULL ((mi_free_t)0) +#define MI_FREE_LEN_MAX (0xFFFF) + +#if MI_HAS_FREE_LEN +static inline size_t mi_free_len(mi_free_t f) { return (f & MI_FREE_LEN_MAX); } +static inline mi_block_t* mi_free_block(mi_free_t f) { return (mi_block_t*)(f >> MI_HAS_FREE_LEN); } +static inline mi_free_t mi_free_create(const mi_block_t* block, size_t len) { return (((mi_free_t)block << MI_HAS_FREE_LEN) | len); } +#else +static inline size_t mi_free_len(mi_free_t f) { (void)(f); return 0; } +static inline mi_block_t* mi_free_block(mi_free_t f) { return (mi_block_t*)f; } +static inline mi_free_t mi_free_create(const mi_block_t* block, size_t len) { (void)(len); return (mi_free_t)block; } +#endif + +static inline bool mi_free_is_empty(mi_free_t f) { return (f == MI_FREE_NULL); } + // We store the currently used block count together with the total malloc call count as 16-bit numbers. // This is done for better codegen `mi_malloc/mi_free` (where we can increment both at once as `used_alloc += 0x10001` for example). // The `last_used` is the `used` count since the statistics are last updated; on 32-bit platforms this @@ -434,8 +462,8 @@ } mi_used_t; static inline size_t mi_xused_used_count(mi_used_t xused) { return (xused.used_alloc & 0xFFFF); } -static inline size_t mi_xused_alloc_count(mi_used_t xused) { return ((xused.used_alloc>>16) & 0xFFFF); } static inline mi_used_t mi_xused_used_reset(mi_used_t xused) { xused.used_alloc = xused.used_alloc & ~0xFFFF; return xused; } +static inline size_t mi_xused_alloc_count(mi_used_t xused) { return ((xused.used_alloc>>16) & 0xFFFF); } // A page contains blocks of one specific size (`block_size`). // Each page has three list of free blocks: @@ -469,17 +497,26 @@ _Atomic(struct mi_page_s*) self; // points to the actual page info (for pages that span multiple slices) #endif _Atomic(mi_threadid_t) xthread_id; // thread this page belongs to. (= `theap->thread_id (or 0 or 4 if abandoned) | page_flags`) - mi_block_t* free; // list of available free blocks (`malloc` allocates from this list) - mi_used_t xused; // number of blocks in use (including blocks in `thread_free`) (and the allocated count for statistics) + mi_free_t free; // list of available free blocks (`malloc` allocates from this list) + #if MI_HAS_FREE_LEN + mi_free_t local_free; + mi_used_t xused; // used field is not used + #else + mi_used_t xused; #if MI_SIZE_SIZE < 8 uint16_t xlast_used; // for statistics; on 64-bit platforms it is in bits 32..47 of xused. uint16_t xlast_alloc; // for sampling; on 64-bit platforms it is in bits 48..63 of xused. #endif - mi_block_t* local_free; // list of deferred free blocks by this thread (migrates to `free`) - + mi_free_t local_free; // list of deferred free blocks by this thread (migrates to `free`) + #endif + size_t block_size; // const: size available in each block (always `>0`) size_t page_offset; // const: relative offset from the page to the start of the blocks - uint16_t capacity; // number of blocks committed + #if !MI_HAS_FREE_LEN + uint16_t xcapacity; // number of blocks committed (see `mi_page_capacity`) + #else + uint16_t xcapacity_unused; // the capacity is in the low 16 bits of `xthread_id` + #endif uint16_t reserved; // number of blocks reserved in memory uint16_t slice_pcommitted; // committed size in OS page sizes relative to the first arena slice of the page data (or 0 if the page is fully committed already) uint8_t retire_expire; // expiration count for retired blocks
diff --git a/src/alloc-aligned.c b/src/alloc-aligned.c index 51f2973..bc7950a 100644 --- a/src/alloc-aligned.c +++ b/src/alloc-aligned.c
@@ -205,8 +205,8 @@ const uintptr_t align_mask = alignment-1; // for any x, `(x & align_mask) == (x % alignment)` const size_t padsize = size + MI_PADDING_SIZE; mi_page_t* page = _mi_theap_get_free_small_page(theap, padsize, false); - if mi_likely(page->free != NULL) { - const bool is_aligned = (((uintptr_t)page->free + offset) & align_mask)==0; + if mi_likely(!mi_free_is_empty(page->free)) { + const bool is_aligned = (((uintptr_t)mi_free_block(page->free) + offset) & align_mask)==0; if mi_likely(is_aligned) { if (ppage!=NULL) { *ppage = page; }
diff --git a/src/alloc.c b/src/alloc.c index 647ecef..3094342 100644 --- a/src/alloc.c +++ b/src/alloc.c
@@ -34,7 +34,7 @@ const ptrdiff_t delta = ((uint8_t*)padding - (uint8_t*)block - (size - MI_PADDING_SIZE)); mi_assert_internal(delta >= 0 && bsize >= (size - MI_PADDING_SIZE + delta)); mi_track_mem_defined(padding,sizeof(mi_padding_t)); // note: re-enable since mi_page_usable_block_size may set noaccess - padding->canary = mi_ptr_encode_canary(page,block,page->keys); + padding->canary = mi_ptr_encode_canary(page,(uintptr_t)block,page->keys); padding->delta = (uint32_t)(delta); #if MI_PADDING_CHECK_BYTES if (!mi_page_is_huge(page)) { @@ -60,15 +60,17 @@ } // check the free list - mi_block_t* const block = page->free; + mi_block_t* const block = mi_free_block(page->free); + #if !MI_HAS_FREE_LEN mi_used_t xused = page->xused; xused.used_alloc += 0x10001; // increment both (16-bit) used count and alloc count - #if defined(__GNUC__) && defined(__aarch64__) + #if defined(__GNUC__) && MI_ARCH_ARM64 // on arm64 this pairs the `free` and `xused` loads into a single `ldp` (and the stores into an `stp`). // we do _not_ do this on x86-64 where it instead prevents the compiler from folding the // increment into a single `add $0x10001, xused(%page)` read-modify-write instruction. __asm("" : : : "memory" ); // always load the `used` field before the test #endif + #endif if (block == NULL) { return _mi_malloc_generic(theap, size, (zero ? 1 : 0), ppage); } @@ -76,7 +78,7 @@ if (ppage != NULL) { *ppage = page; }; // pop from the free list - mi_block_t* next = mi_block_next(page,block); + mi_free_t next = mi_block_next(page,block); mi_track_mem_undefined(block,sizeof(*block)); #if MI_SECURE @@ -84,8 +86,10 @@ #endif page->free = next; + #if !MI_HAS_FREE_LEN page->xused = xused; - mi_assert_internal(page->free == NULL || _mi_ptr_page(page->free) == page); + #endif + mi_assert_internal(mi_free_block(page->free) == NULL || _mi_ptr_page(mi_free_block(page->free)) == page); mi_assert_internal(page->block_size < MI_MAX_ALIGN_SIZE || _mi_is_aligned(block, MI_MAX_ALIGN_SIZE)); #if MI_SAMPLE==2
diff --git a/src/arena.c b/src/arena.c index 1b7c8cb..c75434f 100644 --- a/src/arena.c +++ b/src/arena.c
@@ -1104,7 +1104,7 @@ #endif #endif - mi_assert_internal(page->free==NULL); + mi_assert_internal(mi_free_is_empty(page->free)); mi_assert_internal(page_meta_is_separate == mi_page_meta_is_separated(page)); mi_assert_internal(mi_page_slice_start(page) == slice_start); mi_assert_internal(mi_page_size(page) <= page_noguard_size);
diff --git a/src/free.c b/src/free.c index bcb4cb2..28155f4 100644 --- a/src/free.c +++ b/src/free.c
@@ -24,7 +24,7 @@ // regular free of a (thread local) block pointer // fast path written carefully to prevent spilling on the stack -static inline void mi_free_block_local(mi_page_t* page, mi_block_t* block, bool was_guarded, bool check_full) +static inline void mi_free_block_local(mi_page_t* page, mi_block_t* block, size_t capacity, bool was_guarded, bool check_full) { // checks size_t usable_size; @@ -40,13 +40,31 @@ #endif // actual free: push on the local free list + #if !MI_HAS_FREE_LEN + MI_UNUSED(capacity); mi_used_t xused = page->xused; xused.used_alloc--; // decrement used count mi_block_set_next(page, block, page->local_free); page->xused = xused; - page->local_free = block; + page->local_free = mi_free_create(block,0); mi_assert_internal(mi_page_alloc_count(page) + mi_page_last_used(page) >= mi_page_used(page)); - if mi_unlikely(mi_xused_used_count(xused) == 0) { // is used count zero ? + if mi_unlikely(mi_xused_used_count(xused) == 0) + #else + const mi_free_t free = page->free; + mi_free_t lfree = page->local_free; + #if defined(__GNUC__) && MI_ARCH_ARM64 + // pair the `free` and `local_free` loads into a single `ldp` + __asm("" : : "r"(free) : ); + #endif + mi_block_set_next(page, block, lfree); + lfree++; // whole word increment: the length can never carry into the block bits + page->local_free = mi_free_create(block, mi_free_len(lfree)); + // `|free| + |local_free| - capacity` equals `-used` modulo 2^16 (which is zero exactly when `used` is zero) + const size_t nused = (lfree + mi_free_len(free) - capacity) & MI_FREE_LEN_MAX; + mi_assert_internal((nused == 0) == (mi_page_used(page) == 0)); + if mi_unlikely(nused == 0) + #endif + { if (page->retire_expire==0) { // no need to re-retire retired pages (happens when we alloc/free one block repeatedly in an empty page) _mi_page_retire(page); } @@ -82,7 +100,7 @@ mi_thread_free_t tf_new; mi_thread_free_t tf_old = mi_atomic_load_relaxed(&page->xthread_free); do { - mi_block_set_next(page, block, mi_tf_block(tf_old)); + mi_block_set_next(page, block, mi_free_create(mi_tf_block(tf_old), 0)); // the length is recomputed when collected tf_new = mi_tf_create(block, true); } while (!mi_atomic_cas_weak_acq_rel(&page->xthread_free, &tf_old, tf_new)); @@ -166,7 +184,7 @@ // mi_block_t* const block = (mi_page_has_interior_pointers(page) ? _mi_page_ptr_unalign(page, p) : mi_validate_block_from_ptr(page,p)); // mi_block_check_profiled(page,block,p); // const bool was_guarded = mi_block_check_unguard(page, block, p); - mi_free_block_local(page, block, was_guarded, true /* check for a full page */); + mi_free_block_local(page, block, mi_page_capacity(page), was_guarded, true /* check for a full page */); } // free a pointer owned by another thread (page parameter comes first for better codegen) @@ -263,14 +281,23 @@ mi_assert_internal(p!=NULL && page!=NULL); if (pblock_size!=NULL) { *pblock_size = mi_page_block_size(page); } - const mi_threadid_t ptid = mi_page_xthread_id(page); - const mi_threadid_t xtid = (_mi_prim_thread_id() ^ ptid); - if mi_likely(xtid == 0) { // `tid == mi_page_thread_id(page) && mi_page_flags(page) == 0` + const mi_threadid_t pxtid = mi_atomic_load_relaxed(&page->xthread_id); + #if MI_HAS_FREE_LEN + const size_t capacity = (size_t)(pxtid & MI_PAGE_CAPACITY_MASK); + #else + const size_t capacity = 0; + #endif + // note: we compare directly (instead of using `xtid` in the fast path) so the thread id + // shift can be folded into the compare as a shifted register operand. + const mi_threadid_t tid = _mi_prim_thread_id(); + if mi_likely((pxtid >> MI_PAGE_TID_SHIFT) == tid) { // `tid == mi_page_thread_id(page) && mi_page_flags(page) == 0` // thread-local, aligned, and not a full page mi_block_t* const block = mi_validate_block_from_ptr(page,p); - mi_free_block_local(page, block, false /* was guarded */, false /* no need to check if the page is full */); + mi_free_block_local(page, block, capacity, false /* was guarded */, false /* no need to check if the page is full */); + return; } - else if (xtid <= MI_PAGE_FLAG_MASK) { // `tid == mi_page_thread_id(page) && mi_page_flags(page) != 0` + const mi_threadid_t xtid = (tid ^ mi_page_xthread_id(page)); // note: re-load to keep the shift out of the fast path + if (xtid <= MI_PAGE_FLAG_MASK) { // `tid == mi_page_thread_id(page) && mi_page_flags(page) != 0` // page is local, but is full or contains (inner) aligned blocks; use generic path mi_free_generic_local(page, p); } @@ -600,11 +627,11 @@ #if MI_SECURE>=3 && !MI_PADDING // linear check if the free list contains a specific element static bool mi_list_contains(const mi_page_t* page, const mi_block_t* list, const mi_block_t* elem, const char* list_kind) { - const size_t max_count = page->capacity; // can never hold more blocks than the capacity + const size_t max_count = mi_page_capacity(page); // can never hold more blocks than the capacity size_t count = 0; while (list != NULL && count <= max_count) { // double-free can create cycles so we limit the number of iterations if (elem==list) return true; - list = mi_block_next(page, list); + list = mi_free_block(mi_block_next(page, list)); count++; } if mi_unlikely(count > max_count) { @@ -616,8 +643,8 @@ static mi_decl_noinline bool mi_check_double_freex(const mi_page_t* page, const mi_block_t* block) { // The decoded value is in the same page (or NULL). // Walk the free lists to verify positively if it is already freed - if (mi_list_contains(page, page->free, block, "free") || - mi_list_contains(page, page->local_free, block, "local free") || + if (mi_list_contains(page, mi_free_block(page->free), block, "free") || + mi_list_contains(page, mi_free_block(page->local_free), block, "local free") || mi_list_contains(page, mi_page_thread_free(page), block, "thread free")) { _mi_error_message(EAGAIN, "double free detected of block %p with size %zu\n", block, mi_page_block_size(page)); @@ -628,7 +655,7 @@ // Used for double free checking to avoid checking free lists too frequently static inline bool mi_block_could_be_double_free(const mi_page_t* page, const mi_block_t* block) { - mi_block_t* n = mi_block_nextx(page,block,page->keys); + mi_block_t* n = mi_free_block(mi_block_nextx(page,block,page->keys)); return (_mi_is_aligned(block,MI_SIZE_SIZE) && // quick check: aligned pointer? (n==NULL || mi_page_contains_address(page,n))); // quick check: in the same page or NULL? } @@ -663,7 +690,7 @@ mi_track_mem_defined(padding,sizeof(mi_padding_t)); *delta = padding->delta; const uint32_t canary = padding->canary; - const bool ok = (mi_ptr_encode_canary(page,block,page->keys) == canary && *delta <= *bsize); + const bool ok = (mi_ptr_encode_canary(page,(uintptr_t)block,page->keys) == canary && *delta <= *bsize); if (double_free!=NULL) { if mi_unlikely(!ok) { *double_free = mi_ptr_decode_canary_is_freed(canary); } // double free? else { padding->canary = mi_ptr_encode_canary_freed(); } // mark as freed
diff --git a/src/heap.c b/src/heap.c index d7f1db1..0017a9c 100644 --- a/src/heap.c +++ b/src/heap.c
@@ -294,7 +294,7 @@ bool mi_unsafe_heap_page_is_under_utilized(mi_heap_t* heap, void* p, size_t perc_threshold) mi_attr_noexcept { if (p==NULL) return false; const mi_page_t* const page = _mi_safe_ptr_page(p); // Get the page containing this pointer - if (page==NULL || mi_page_used(page)==page->capacity || page->capacity < page->reserved) return false; + if (page==NULL || mi_page_used(page)==mi_page_capacity(page) || mi_page_capacity(page) < page->reserved) return false; // If the page is the head of the queue, it is currently being used for // allocations; we skip it to avoid immediate thrashing. if (page->prev == NULL) return false; @@ -305,7 +305,7 @@ if (heap!=NULL && page_heap!=heap) return false; // check utilization - if (page->capacity==0) return false; + if (mi_page_capacity(page)==0) return false; if (perc_threshold>=100) return true; - return (perc_threshold >= ((100UL*mi_page_used(page)) / page->capacity)); + return (perc_threshold >= ((100UL*mi_page_used(page)) / mi_page_capacity(page))); }
diff --git a/src/init.c b/src/init.c index 580876a..a9f1ad6 100644 --- a/src/init.c +++ b/src/init.c
@@ -18,13 +18,19 @@ MI_ATOMIC_VAR_INIT(NULL), // self #endif MI_ATOMIC_VAR_INIT(0), // xthread_id - NULL, // free + #if MI_HAS_FREE_LEN + 0, // free + 0, // local_free + {0}, // xused + #else + 0, // free {0}, // xused #if MI_SIZE_SIZE < 8 0, // xlast_used 0, // xlast_alloc #endif - NULL, // local_free + 0, // local_free + #endif 0, // block_size 0, // page_offset 0, // capacity
diff --git a/src/options.c b/src/options.c index a43505a..5078d5e 100644 --- a/src/options.c +++ b/src/options.c
@@ -630,9 +630,9 @@ } } -mi_decl_noinline mi_block_t* _mi_block_next_is_corrupted(const mi_page_t* page, const mi_block_t* block, const mi_block_t* next) { +mi_decl_noinline mi_free_t _mi_block_next_is_corrupted(const mi_page_t* page, const mi_block_t* block, const mi_block_t* next) { _mi_error_message(EFAULT, "corrupted free list entry of size %zub at %p: value 0x%zx\n", mi_page_block_size(page), block, (uintptr_t)next); - return NULL; + return MI_FREE_NULL; } // --------------------------------------------------------
diff --git a/src/page.c b/src/page.c index 506c37e..1afac30 100644 --- a/src/page.c +++ b/src/page.c
@@ -49,7 +49,7 @@ while (head != NULL) { mi_assert_internal((uint8_t*)head - slice_start > (ptrdiff_t)MI_LARGE_PAGE_SIZE || page == _mi_ptr_page(head)); count++; - head = mi_block_next(page, head); + head = mi_free_block(mi_block_next(page, head)); } return count; } @@ -68,12 +68,12 @@ mi_block_t* end = (mi_block_t*)(page_area + psize); while(p != NULL) { if (p < start || p >= end) return false; - p = mi_block_next(page, p); + p = mi_free_block(mi_block_next(page, p)); } #if MI_DEBUG>3 // generally too expensive to check this if (page->free_is_zero) { const size_t ubsize = mi_page_usable_block_size(page); - for (mi_block_t* block = page->free; block != NULL; block = mi_block_next(page, block)) { + for (mi_block_t* block = mi_free_block(page->free); block != NULL; block = mi_free_block(mi_block_next(page, block))) { mi_assert_expensive(mi_mem_is_zero(block + 1, ubsize - sizeof(mi_block_t))); } } @@ -81,10 +81,26 @@ return true; } +#if MI_HAS_FREE_LEN +// every interior `next` field must carry the exact remaining list length +static bool mi_page_list_lens_are_valid(mi_page_t* page, mi_free_t list) { + size_t rem = mi_free_len(list); + mi_block_t* block = mi_free_block(list); + while (block != NULL) { + if (rem == 0) return false; + rem--; + const mi_free_t next = mi_block_next(page, block); + if (mi_free_len(next) != rem) return false; + block = mi_free_block(next); + } + return (rem == 0); +} +#endif + static bool mi_page_is_valid_init(mi_page_t* page) { mi_assert_internal(mi_page_block_size(page) > 0); - mi_assert_internal(mi_page_used(page) <= page->capacity); - mi_assert_internal(page->capacity <= page->reserved); + mi_assert_internal(mi_page_used(page) <= mi_page_capacity(page)); + mi_assert_internal(mi_page_capacity(page) <= page->reserved); mi_assert_internal(page->heap!=NULL); mi_theap_t* const page_theap = _mi_heap_theap_peek(page->heap); @@ -94,13 +110,19 @@ // uint8_t* start = mi_page_start(page); //mi_assert_internal(start + page->capacity*page->block_size == page->top); - mi_assert_internal(mi_page_list_is_valid(page,page->free)); - mi_assert_internal(mi_page_list_is_valid(page,page->local_free)); + mi_assert_internal(mi_page_list_is_valid(page,mi_free_block(page->free))); + mi_assert_internal(mi_page_list_is_valid(page,mi_free_block(page->local_free))); + mi_assert_internal(!MI_HAS_FREE_LEN || mi_page_list_count(page,mi_free_block(page->free)) == mi_free_len(page->free)); + mi_assert_internal(!MI_HAS_FREE_LEN || mi_page_list_count(page,mi_free_block(page->local_free)) == mi_free_len(page->local_free)); + #if MI_HAS_FREE_LEN + mi_assert_internal(mi_page_list_lens_are_valid(page, page->free)); + mi_assert_internal(mi_page_list_lens_are_valid(page, page->local_free)); + #endif #if MI_DEBUG>3 // generally too expensive to check this if (page->free_is_zero) { const size_t ubsize = mi_page_usable_block_size(page); - for(mi_block_t* block = page->free; block != NULL; block = mi_block_next(page,block)) { + for(mi_block_t* block = mi_free_block(page->free); block != NULL; block = mi_free_block(mi_block_next(page,block))) { mi_assert_expensive(mi_mem_is_zero(block + 1, ubsize - sizeof(mi_block_t))); } } @@ -113,8 +135,8 @@ //mi_assert_internal(tfree_count <= page->thread_freed + 1); #endif - size_t free_count = mi_page_list_count(page, page->free) + mi_page_list_count(page, page->local_free); - mi_assert_internal(mi_page_used(page) + free_count == page->capacity); + size_t free_count = mi_page_list_count(page, mi_free_block(page->free)) + mi_page_list_count(page, mi_free_block(page->local_free)); + mi_assert_internal(mi_page_used(page) + free_count == mi_page_capacity(page)); mi_assert_internal(mi_page_alloc_count(page) + mi_page_last_used(page) >= mi_page_used(page)); return true; @@ -261,7 +283,9 @@ } // reset the `alloc_count` (and `last_alloc`), and set `last_used` to `used` - #if MI_SIZE_SIZE >= 8 + #if MI_HAS_FREE_LEN + page->xused.used_alloc = (used << 32) | mi_free_len(page->free); // reset the alloc count and re-baseline `|free|` + #elif MI_SIZE_SIZE >= 8 page->xused.used_alloc = (used << 32) | used; #else page->xused.used_alloc = used; @@ -323,11 +347,11 @@ 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 max_count = mi_page_capacity(page); // 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) { + while ((next = mi_free_block(mi_block_next(page, last))) != NULL && count <= max_count) { count++; last = next; } @@ -344,13 +368,25 @@ } // and append the current local free list - mi_block_set_next(page, last, page->local_free); - page->local_free = head; + const mi_free_t lfree = page->local_free; + #if MI_HAS_FREE_LEN + // the blocks in the thread-free list have no valid list length yet; set them in a second pass + size_t rem = count - 1 + mi_free_len(lfree); + for (mi_block_t* block = head; block != last; rem--) { + mi_block_t* const bnext = mi_free_block(mi_block_next(page, block)); + mi_block_set_next(page, block, mi_free_create(bnext, rem)); + block = bnext; + } + mi_assert_internal(rem == mi_free_len(lfree)); + #endif + mi_block_set_next(page, last, lfree); + page->local_free = mi_free_create(head, count + mi_free_len(lfree)); // update counts now mi_assert_internal(count <= UINT16_MAX); - mi_assert_internal(mi_page_used(page) >= count); + #if !MI_HAS_FREE_LEN page->xused.used_alloc -= count; // page->used = page->used - (uint16_t)count; + #endif } // Collect the local `thread_free` list using an atomic exchange. @@ -376,16 +412,40 @@ // returns `true` if after collection `mi_page_immediate_available` is true. static inline bool mi_page_free_quick_collect(mi_page_t* page) { - if mi_likely(page->free != NULL) return true; - if (page->local_free == NULL) return false; + if mi_likely(!mi_free_is_empty(page->free)) return true; + if (mi_free_is_empty(page->local_free)) return false; // move local_free to free - page->free = page->local_free; - page->local_free = NULL; + mi_page_set_free(page, page->local_free); + page->local_free = MI_FREE_NULL; page->free_is_zero = false; mi_page_update_sample_countdown(page); return true; } +// Concatenate two free lists by appending `second` to the tail of `first` (walking `first`). +static mi_free_t mi_free_concat(mi_page_t* page, mi_free_t first, mi_free_t second) { + if (mi_free_is_empty(first)) return second; + if (mi_free_is_empty(second)) return first; + mi_block_t* tail = mi_free_block(first); + mi_block_t* next; + #if MI_HAS_FREE_LEN + // the list lengths of the `first` blocks all increase by `|second|` + size_t rem = mi_free_len(first) - 1 + mi_free_len(second); + while ((next = mi_free_block(mi_block_next(page, tail))) != NULL) { + mi_block_set_next(page, tail, mi_free_create(next, rem)); + rem--; + tail = next; + } + mi_assert_internal(rem == mi_free_len(second)); + #else + while ((next = mi_free_block(mi_block_next(page, tail))) != NULL) { + tail = next; + } + #endif + mi_block_set_next(page, tail, second); + return mi_free_create(mi_free_block(first), mi_free_len(first) + mi_free_len(second)); +} + bool _mi_page_free_collect(mi_page_t* page, bool force) { mi_assert_internal(page!=NULL); @@ -393,28 +453,22 @@ const bool collected_xfree = mi_page_thread_free_collect(page); // and the local free list - if (page->local_free != NULL) { - if mi_likely(page->free == NULL) { + if (!mi_free_is_empty(page->local_free)) { + if mi_likely(mi_free_is_empty(page->free)) { // usual case - page->free = page->local_free; - page->local_free = NULL; + mi_page_set_free(page, page->local_free); + page->local_free = MI_FREE_NULL; page->free_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; + mi_page_set_free(page, mi_free_concat(page, page->local_free, page->free)); + page->local_free = MI_FREE_NULL; page->free_is_zero = false; } mi_page_update_sample_countdown(page); } - mi_assert_internal(!force || page->local_free == NULL); + mi_assert_internal(!force || mi_free_is_empty(page->local_free)); return collected_xfree; } @@ -428,13 +482,13 @@ mi_block_t* _mi_page_free_collect_partly(mi_page_t* page, mi_block_t* head) { 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) + mi_block_t* next = mi_free_block(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_block_set_next(page, head, NULL); + mi_block_set_next(page, head, MI_FREE_NULL); mi_page_thread_collect_to_local(page, next); - if (page->local_free != NULL && page->free == NULL) { - page->free = page->local_free; - page->local_free = NULL; + if (!mi_free_is_empty(page->local_free) && mi_free_is_empty(page->free)) { + mi_page_set_free(page, page->local_free); + page->local_free = MI_FREE_NULL; page->free_is_zero = false; mi_page_update_sample_countdown(page); } @@ -442,7 +496,7 @@ if (mi_page_used(page) == 1) { // all elements are free'd since we skipped the `head` element itself mi_assert_internal(mi_tf_block(mi_atomic_load_relaxed(&page->xthread_free)) == head); - mi_assert_internal(mi_block_next(page,head) == NULL); + mi_assert_internal(mi_free_is_empty(mi_block_next(page,head))); _mi_page_free_collect(page, false); // collect the final element return NULL; } @@ -717,10 +771,10 @@ static void mi_page_free_list_extend_secure(mi_theap_t* const theap, mi_page_t* const page, const size_t bsize, const size_t extend) { #if (MI_SECURE < 2) - mi_assert_internal(page->free == NULL); - mi_assert_internal(page->local_free == NULL); + mi_assert_internal(mi_free_is_empty(page->free)); + mi_assert_internal(mi_free_is_empty(page->local_free)); #endif - mi_assert_internal(page->capacity + extend <= page->reserved); + mi_assert_internal(mi_page_capacity(page) + extend <= page->reserved); mi_assert_internal(bsize == mi_page_block_size(page)); void* const page_area = mi_page_start(page); @@ -736,7 +790,7 @@ mi_block_t* blocks[MI_MAX_SLICES]; // current start of the slice size_t counts[MI_MAX_SLICES]; // available objects in the slice for (size_t i = 0; i < slice_count; i++) { - blocks[i] = mi_page_block_at(page, page_area, bsize, page->capacity + i*slice_extend); + blocks[i] = mi_page_block_at(page, page_area, bsize, mi_page_capacity(page) + i*slice_extend); counts[i] = slice_extend; } counts[slice_count-1] += (extend % slice_count); // final slice holds the modulus too (todo: distribute evenly?) @@ -747,6 +801,8 @@ size_t current = r % slice_count; counts[current]--; mi_block_t* const free_start = blocks[current]; + // the remaining list length after each block (only used if `MI_HAS_FREE_LEN`) + size_t rem = extend - 1 + mi_free_len(page->free); // and iterate through the rest; use `random_shuffle` for performance size_t rnd = _mi_random_shuffle(r|1); // ensure not 0 for (size_t i = 1; i < extend; i++) { @@ -763,37 +819,42 @@ counts[next]--; mi_block_t* const block = blocks[current]; blocks[current] = (mi_block_t*)((uint8_t*)block + bsize); // bump to the following block - mi_block_set_next(page, block, blocks[next]); // and set next; note: we may have `current == next` + mi_block_set_next(page, block, mi_free_create(blocks[next], rem)); // and set next; note: we may have `current == next` + rem--; current = next; } // prepend to the free list (usually NULL) + mi_assert_internal(rem == mi_free_len(page->free)); mi_block_set_next(page, blocks[current], page->free); // end of the list - page->free = free_start; + mi_page_set_free(page, mi_free_create(free_start, extend + mi_free_len(page->free))); } static mi_decl_noinline void mi_page_free_list_extend( mi_page_t* const page, const size_t bsize, const size_t extend) { #if (MI_SECURE < 2) - mi_assert_internal(page->free == NULL); - mi_assert_internal(page->local_free == NULL); + mi_assert_internal(mi_free_is_empty(page->free)); + mi_assert_internal(mi_free_is_empty(page->local_free)); #endif - mi_assert_internal(page->capacity + extend <= page->reserved); + mi_assert_internal(mi_page_capacity(page) + extend <= page->reserved); mi_assert_internal(bsize == mi_page_block_size(page)); void* const page_area = mi_page_start(page); - mi_block_t* const start = mi_page_block_at(page, page_area, bsize, page->capacity); + mi_block_t* const start = mi_page_block_at(page, page_area, bsize, mi_page_capacity(page)); // initialize a sequential free list - mi_block_t* const last = mi_page_block_at(page, page_area, bsize, page->capacity + extend - 1); + mi_block_t* const last = mi_page_block_at(page, page_area, bsize, mi_page_capacity(page) + extend - 1); mi_block_t* block = start; - while(block <= last) { + size_t rem = extend - 1 + mi_free_len(page->free); // remaining list length after each block + while(block < last) { mi_block_t* next = (mi_block_t*)((uint8_t*)block + bsize); - mi_block_set_next(page,block,next); + mi_block_set_next(page,block,mi_free_create(next,rem)); + rem--; block = next; } // prepend to free list (usually `NULL`) + mi_assert_internal(rem == mi_free_len(page->free)); mi_block_set_next(page, last, page->free); - page->free = start; + mi_page_set_free(page, mi_free_create(start, extend + mi_free_len(page->free))); } /* ----------------------------------------------------------- @@ -815,11 +876,11 @@ static bool mi_page_extend_free(mi_theap_t* theap, mi_page_t* page) { mi_assert_expensive(mi_page_is_valid_init(page)); #if (MI_SECURE < 2) - mi_assert(page->free == NULL); - mi_assert(page->local_free == NULL); - if (page->free != NULL) return true; + mi_assert(mi_free_is_empty(page->free)); + mi_assert(mi_free_is_empty(page->local_free)); + if (!mi_free_is_empty(page->free)) return true; #endif - if (page->capacity >= page->reserved) return true; + if (mi_page_capacity(page) >= page->reserved) return true; size_t page_size; //uint8_t* page_start = @@ -828,7 +889,7 @@ // calculate the extend count const size_t bsize = mi_page_block_size(page); - size_t extend = (size_t)page->reserved - page->capacity; + size_t extend = (size_t)page->reserved - mi_page_capacity(page); mi_assert_internal(extend > 0); size_t max_extend = (bsize >= MI_MAX_EXTEND_SIZE ? MI_MIN_EXTEND : MI_MAX_EXTEND_SIZE/bsize); @@ -841,7 +902,7 @@ extend = max_extend; } - mi_assert_internal(extend > 0 && extend + page->capacity <= page->reserved); + mi_assert_internal(extend > 0 && extend + mi_page_capacity(page) <= page->reserved); mi_assert_internal(extend < (1UL<<16)); // commit on demand? @@ -852,7 +913,7 @@ extend = _mi_divide_up(MI_ARENA_SLICE_SIZE, bsize); } // commit required size - const size_t needed_size = (page->capacity + extend)*bsize; + const size_t needed_size = (mi_page_capacity(page) + extend)*bsize; mi_assert_internal(needed_size <= page_size); size_t needed_commit = _mi_align_up( mi_page_slice_offset_of(page, needed_size), mi_page_min_commit_size()); #if MI_SECURE>=5 @@ -880,7 +941,7 @@ mi_page_free_list_extend_secure(theap, page, bsize, extend); } // enable the new free list - page->capacity += (uint16_t)extend; + mi_page_capacity_increase(page, extend); mi_theap_stat_increase(theap, page_committed, extend * bsize); mi_assert_expensive(mi_page_is_valid_init(page)); return true; @@ -915,8 +976,8 @@ mi_assert_internal(page->heap == _mi_theap_heap(theap)); mi_assert_internal(page->theap!=NULL); mi_assert_internal(page->theap == mi_page_theap(page)); - mi_assert_internal(page->capacity == 0); - mi_assert_internal(page->free == NULL); + mi_assert_internal(mi_page_capacity(page) == 0); + mi_assert_internal(mi_free_is_empty(page->free)); mi_assert_internal(mi_page_used(page) == 0); mi_assert_internal(page->xused.used_alloc == 0); mi_assert_internal(mi_page_is_owned(page)); @@ -1080,7 +1141,7 @@ if mi_likely(page!=NULL && mi_page_free_quick_collect(page)) { // fast path #if (MI_SECURE>=2) // in secure mode, we extend half the time to increase randomness - if (page->capacity < page->reserved && ((_mi_theap_random_next(theap) & 1) == 1)) { + if (mi_page_capacity(page) < page->reserved && ((_mi_theap_random_next(theap) & 1) == 1)) { (void)mi_page_extend_free(theap, page); // ok if this fails mi_assert_internal(mi_page_immediate_available(page)); }
diff --git a/src/theap.c b/src/theap.c index 9665fb0..0342605 100644 --- a/src/theap.c +++ b/src/theap.c
@@ -509,7 +509,7 @@ const size_t bsize = mi_page_block_size(page); const size_t ubsize = mi_page_usable_block_size(page); area->reserved = page->reserved * bsize; - area->committed = page->capacity * bsize; + area->committed = mi_page_capacity(page) * bsize; area->blocks = mi_page_start(page); area->used = mi_page_used(page); // number of blocks in use (#553) area->block_size = ubsize; @@ -536,7 +536,7 @@ if (page == NULL) return true; _mi_page_free_collect(page,true); // collect both thread_delayed and local_free - mi_assert_internal(page->local_free == NULL); + mi_assert_internal(mi_free_is_empty(page->local_free)); if (mi_page_used(page) == 0) return true; size_t psize; @@ -546,16 +546,16 @@ const size_t ubsize = mi_page_usable_block_size(page); // without padding // optimize page with one block - if (page->capacity == 1) { - mi_assert_internal(mi_page_used(page) == 1 && page->free == NULL); + if (mi_page_capacity(page) == 1) { + mi_assert_internal(mi_page_used(page) == 1 && mi_free_is_empty(page->free)); return visitor(heap, area, pstart, ubsize, arg); } mi_assert(bsize <= UINT32_MAX); // optimize full pages - if (mi_page_used(page) == page->capacity) { + if (mi_page_used(page) == mi_page_capacity(page)) { uint8_t* block = pstart; - for (size_t i = 0; i < page->capacity; i++) { + for (size_t i = 0; i < mi_page_capacity(page); i++) { if (!visitor(heap, area, block, ubsize, arg)) return false; block += bsize; } @@ -565,11 +565,11 @@ // create a bitmap of free blocks. #define MI_MAX_BLOCKS (MI_SMALL_PAGE_SIZE / sizeof(void*)) uintptr_t free_map[MI_MAX_BLOCKS / MI_INTPTR_BITS]; - const uintptr_t bmapsize = _mi_divide_up(page->capacity, MI_INTPTR_BITS); + const uintptr_t bmapsize = _mi_divide_up(mi_page_capacity(page), MI_INTPTR_BITS); memset(free_map, 0, bmapsize * sizeof(intptr_t)); - if (page->capacity % MI_INTPTR_BITS != 0) { + if (mi_page_capacity(page) % MI_INTPTR_BITS != 0) { // mark left-over bits at the end as free - size_t shift = (page->capacity % MI_INTPTR_BITS); + size_t shift = (mi_page_capacity(page) % MI_INTPTR_BITS); uintptr_t mask = (UINTPTR_MAX << shift); free_map[bmapsize - 1] = mask; } @@ -582,7 +582,7 @@ #if MI_DEBUG>1 size_t free_count = 0; #endif - for (mi_block_t* block = page->free; block != NULL; block = mi_block_next(page, block)) { + for (mi_block_t* block = mi_free_block(page->free); block != NULL; block = mi_free_block(mi_block_next(page, block))) { #if MI_DEBUG>1 free_count++; #endif @@ -597,7 +597,7 @@ size_t bit = blockidx - (bitidx * MI_INTPTR_BITS); free_map[bitidx] |= ((uintptr_t)1 << bit); } - mi_assert_internal(page->capacity == (free_count + mi_page_used(page))); + mi_assert_internal(mi_page_capacity(page) == (free_count + mi_page_used(page))); // walk through all blocks skipping the free ones #if MI_DEBUG>1
diff --git a/test/test-pthread-exit.c b/test/test-pthread-exit.c new file mode 100644 index 0000000..3a51c9e --- /dev/null +++ b/test/test-pthread-exit.c
@@ -0,0 +1,58 @@ +#define _GNU_SOURCE +#include <dlfcn.h> +#include <pthread.h> +#include <stdio.h> +#include <stdlib.h> + +typedef void* (*mi_malloc_fn)(size_t); +typedef void (*mi_free_fn)(void*); + +static const char* lib_path; +static mi_malloc_fn mi_malloc_p; +static mi_free_fn mi_free_p; + +static void alloc_and_free(void) { + void* p[4]; + for (int i = 0; i < 4; i++) p[i] = mi_malloc_p((size_t)64 << i); + for (int i = 0; i < 4; i++) mi_free_p(p[i]); +} + +// T1: loads mimalloc (constructor -> mi_process_init runs here), allocates, exits. +static void* t1(void* arg) { + (void)arg; + printf("T1 pthread_self=%p (dlopen + first mi_malloc happen here, then T1 exits)\n", (void*)pthread_self()); + void* h = dlopen(lib_path, RTLD_NOW); // never dlclose'd: the library stays loaded + if (h == NULL) { fprintf(stderr, "dlopen: %s\n", dlerror()); exit(2); } + mi_malloc_p = (mi_malloc_fn)dlsym(h, "mi_malloc"); + mi_free_p = (mi_free_fn)dlsym(h, "mi_free"); + if (mi_malloc_p == NULL || mi_free_p == NULL) { fprintf(stderr, "dlsym: %s\n", dlerror()); exit(2); } + alloc_and_free(); + return (void*)pthread_self(); +} + +// T2: a fresh thread; with the same stack size glibc's stack cache hands it T1's TCB. +static void* t2(void* arg) { + (void)arg; + printf("T2 pthread_self=%p (calling mi_malloc on this thread)\n", (void*)pthread_self()); + fflush(stdout); + alloc_and_free(); + return (void*)pthread_self(); +} + +int main(int argc, char** argv) { + if (argc < 2) { fprintf(stderr, "usage: %s <libmimalloc.so>\n", argv[0]); return 2; } + lib_path = argv[1]; + pthread_attr_t attr; + pthread_attr_init(&attr); + pthread_attr_setstacksize(&attr, (size_t)4 << 20); // same size for every thread + pthread_t th; void* t1_self; void* t2_self; + if (pthread_create(&th, &attr, t1, NULL) != 0 || pthread_join(th, &t1_self) != 0) return 2; + int n = 0; + do { // usually the very first T2 reuses T1's TCB; loop just in case + n++; + if (pthread_create(&th, &attr, t2, NULL) != 0 || pthread_join(th, &t2_self) != 0) return 2; + } while (t2_self != t1_self && n < 64); + printf("%s (after %d T2 thread%s)\n", t2_self == t1_self ? "T2 reused T1's TCB" : "no TCB reuse observed", n, n == 1 ? "" : "s"); + printf("OK\n"); + return 0; +}