1/* ----------------------------------------------------------------------------
2Copyright (c) 2018-2022, Microsoft Research, Daan Leijen
3This is free software; you can redistribute it and/or modify it under the
4terms of the MIT license. A copy of the license can be found in the file
5"LICENSE" at the root of this distribution.
6-----------------------------------------------------------------------------*/
7#ifndef _DEFAULT_SOURCE
8#define _DEFAULT_SOURCE // for realpath() on Linux
9#endif
10
11#include "mimalloc.h"
12#include "mimalloc-internal.h"
13#include "mimalloc-atomic.h"
14
15
16#include <string.h> // memset, strlen
17#include <stdlib.h> // malloc, exit
18
19#define MI_IN_ALLOC_C
20#include "alloc-override.c"
21#undef MI_IN_ALLOC_C
22
23// ------------------------------------------------------
24// Allocation
25// ------------------------------------------------------
26
27// Fast allocation in a page: just pop from the free list.
28// Fall back to generic allocation only if the list is empty.
29extern inline void* _mi_page_malloc(mi_heap_t* heap, mi_page_t* page, size_t size, bool zero) mi_attr_noexcept {
30 mi_assert_internal(page->xblock_size==0||mi_page_block_size(page) >= size);
31 mi_block_t* const block = page->free;
32 if mi_unlikely(block == NULL) {
33 return _mi_malloc_generic(heap, size, zero);
34 }
35 mi_assert_internal(block != NULL && _mi_ptr_page(block) == page);
36 // pop from the free list
37 page->used++;
38 page->free = mi_block_next(page, block);
39 mi_assert_internal(page->free == NULL || _mi_ptr_page(page->free) == page);
40
41 // allow use of the block internally
42 // note: when tracking we need to avoid ever touching the MI_PADDING since
43 // that is tracked by valgrind etc. as non-accessible (through the red-zone, see `mimalloc-track.h`)
44 mi_track_mem_undefined(block, mi_page_usable_block_size(page));
45
46 // zero the block? note: we need to zero the full block size (issue #63)
47 if mi_unlikely(zero) {
48 mi_assert_internal(page->xblock_size != 0); // do not call with zero'ing for huge blocks (see _mi_malloc_generic)
49 const size_t zsize = (page->is_zero ? sizeof(block->next) + MI_PADDING_SIZE : page->xblock_size);
50 _mi_memzero_aligned(block, zsize - MI_PADDING_SIZE);
51 }
52
53#if (MI_DEBUG>0) && !MI_TRACK_ENABLED
54 if (!page->is_zero && !zero) { memset(block, MI_DEBUG_UNINIT, mi_page_usable_block_size(page)); }
55#elif (MI_SECURE!=0)
56 if (!zero) { block->next = 0; } // don't leak internal data
57#endif
58
59#if (MI_STAT>0)
60 const size_t bsize = mi_page_usable_block_size(page);
61 if (bsize <= MI_MEDIUM_OBJ_SIZE_MAX) {
62 mi_heap_stat_increase(heap, normal, bsize);
63 mi_heap_stat_counter_increase(heap, normal_count, 1);
64#if (MI_STAT>1)
65 const size_t bin = _mi_bin(bsize);
66 mi_heap_stat_increase(heap, normal_bins[bin], 1);
67#endif
68 }
69#endif
70
71#if (MI_PADDING > 0) && defined(MI_ENCODE_FREELIST) && !MI_TRACK_ENABLED
72 mi_padding_t* const padding = (mi_padding_t*)((uint8_t*)block + mi_page_usable_block_size(page));
73 ptrdiff_t delta = ((uint8_t*)padding - (uint8_t*)block - (size - MI_PADDING_SIZE));
74 #if (MI_DEBUG>1)
75 mi_assert_internal(delta >= 0 && mi_page_usable_block_size(page) >= (size - MI_PADDING_SIZE + delta));
76 mi_track_mem_defined(padding,sizeof(mi_padding_t)); // note: re-enable since mi_page_usable_block_size may set noaccess
77 #endif
78 padding->canary = (uint32_t)(mi_ptr_encode(page,block,page->keys));
79 padding->delta = (uint32_t)(delta);
80 uint8_t* fill = (uint8_t*)padding - delta;
81 const size_t maxpad = (delta > MI_MAX_ALIGN_SIZE ? MI_MAX_ALIGN_SIZE : delta); // set at most N initial padding bytes
82 for (size_t i = 0; i < maxpad; i++) { fill[i] = MI_DEBUG_PADDING; }
83#endif
84
85 return block;
86}
87
88static inline mi_decl_restrict void* mi_heap_malloc_small_zero(mi_heap_t* heap, size_t size, bool zero) mi_attr_noexcept {
89 mi_assert(heap != NULL);
90 mi_assert(heap->thread_id == 0 || heap->thread_id == _mi_thread_id()); // heaps are thread local
91 mi_assert(size <= MI_SMALL_SIZE_MAX);
92#if (MI_PADDING)
93 if (size == 0) {
94 size = sizeof(void*);
95 }
96#endif
97 mi_page_t* page = _mi_heap_get_free_small_page(heap, size + MI_PADDING_SIZE);
98 void* p = _mi_page_malloc(heap, page, size + MI_PADDING_SIZE, zero);
99 mi_assert_internal(p == NULL || mi_usable_size(p) >= size);
100#if MI_STAT>1
101 if (p != NULL) {
102 if (!mi_heap_is_initialized(heap)) { heap = mi_get_default_heap(); }
103 mi_heap_stat_increase(heap, malloc, mi_usable_size(p));
104 }
105#endif
106 mi_track_malloc(p,size,zero);
107 return p;
108}
109
110// allocate a small block
111mi_decl_nodiscard extern inline mi_decl_restrict void* mi_heap_malloc_small(mi_heap_t* heap, size_t size) mi_attr_noexcept {
112 return mi_heap_malloc_small_zero(heap, size, false);
113}
114
115mi_decl_nodiscard extern inline mi_decl_restrict void* mi_malloc_small(size_t size) mi_attr_noexcept {
116 return mi_heap_malloc_small(mi_get_default_heap(), size);
117}
118
119// The main allocation function
120extern inline void* _mi_heap_malloc_zero(mi_heap_t* heap, size_t size, bool zero) mi_attr_noexcept {
121 if mi_likely(size <= MI_SMALL_SIZE_MAX) {
122 return mi_heap_malloc_small_zero(heap, size, zero);
123 }
124 else {
125 mi_assert(heap!=NULL);
126 mi_assert(heap->thread_id == 0 || heap->thread_id == _mi_thread_id()); // heaps are thread local
127 void* const p = _mi_malloc_generic(heap, size + MI_PADDING_SIZE, zero); // note: size can overflow but it is detected in malloc_generic
128 mi_assert_internal(p == NULL || mi_usable_size(p) >= size);
129 #if MI_STAT>1
130 if (p != NULL) {
131 if (!mi_heap_is_initialized(heap)) { heap = mi_get_default_heap(); }
132 mi_heap_stat_increase(heap, malloc, mi_usable_size(p));
133 }
134 #endif
135 mi_track_malloc(p,size,zero);
136 return p;
137 }
138}
139
140mi_decl_nodiscard extern inline mi_decl_restrict void* mi_heap_malloc(mi_heap_t* heap, size_t size) mi_attr_noexcept {
141 return _mi_heap_malloc_zero(heap, size, false);
142}
143
144mi_decl_nodiscard extern inline mi_decl_restrict void* mi_malloc(size_t size) mi_attr_noexcept {
145 return mi_heap_malloc(mi_get_default_heap(), size);
146}
147
148// zero initialized small block
149mi_decl_nodiscard mi_decl_restrict void* mi_zalloc_small(size_t size) mi_attr_noexcept {
150 return mi_heap_malloc_small_zero(mi_get_default_heap(), size, true);
151}
152
153mi_decl_nodiscard extern inline mi_decl_restrict void* mi_heap_zalloc(mi_heap_t* heap, size_t size) mi_attr_noexcept {
154 return _mi_heap_malloc_zero(heap, size, true);
155}
156
157mi_decl_nodiscard mi_decl_restrict void* mi_zalloc(size_t size) mi_attr_noexcept {
158 return mi_heap_zalloc(mi_get_default_heap(),size);
159}
160
161
162// ------------------------------------------------------
163// Check for double free in secure and debug mode
164// This is somewhat expensive so only enabled for secure mode 4
165// ------------------------------------------------------
166
167#if (MI_ENCODE_FREELIST && (MI_SECURE>=4 || MI_DEBUG!=0))
168// linear check if the free list contains a specific element
169static bool mi_list_contains(const mi_page_t* page, const mi_block_t* list, const mi_block_t* elem) {
170 while (list != NULL) {
171 if (elem==list) return true;
172 list = mi_block_next(page, list);
173 }
174 return false;
175}
176
177static mi_decl_noinline bool mi_check_is_double_freex(const mi_page_t* page, const mi_block_t* block) {
178 // The decoded value is in the same page (or NULL).
179 // Walk the free lists to verify positively if it is already freed
180 if (mi_list_contains(page, page->free, block) ||
181 mi_list_contains(page, page->local_free, block) ||
182 mi_list_contains(page, mi_page_thread_free(page), block))
183 {
184 _mi_error_message(EAGAIN, "double free detected of block %p with size %zu\n", block, mi_page_block_size(page));
185 return true;
186 }
187 return false;
188}
189
190#define mi_track_page(page,access) { size_t psize; void* pstart = _mi_page_start(_mi_page_segment(page),page,&psize); mi_track_mem_##access( pstart, psize); }
191
192static inline bool mi_check_is_double_free(const mi_page_t* page, const mi_block_t* block) {
193 bool is_double_free = false;
194 mi_block_t* n = mi_block_nextx(page, block, page->keys); // pretend it is freed, and get the decoded first field
195 if (((uintptr_t)n & (MI_INTPTR_SIZE-1))==0 && // quick check: aligned pointer?
196 (n==NULL || mi_is_in_same_page(block, n))) // quick check: in same page or NULL?
197 {
198 // Suspicous: decoded value a in block is in the same page (or NULL) -- maybe a double free?
199 // (continue in separate function to improve code generation)
200 is_double_free = mi_check_is_double_freex(page, block);
201 }
202 return is_double_free;
203}
204#else
205static inline bool mi_check_is_double_free(const mi_page_t* page, const mi_block_t* block) {
206 MI_UNUSED(page);
207 MI_UNUSED(block);
208 return false;
209}
210#endif
211
212// ---------------------------------------------------------------------------
213// Check for heap block overflow by setting up padding at the end of the block
214// ---------------------------------------------------------------------------
215
216#if (MI_PADDING>0) && defined(MI_ENCODE_FREELIST) && !MI_TRACK_ENABLED
217static bool mi_page_decode_padding(const mi_page_t* page, const mi_block_t* block, size_t* delta, size_t* bsize) {
218 *bsize = mi_page_usable_block_size(page);
219 const mi_padding_t* const padding = (mi_padding_t*)((uint8_t*)block + *bsize);
220 mi_track_mem_defined(padding,sizeof(mi_padding_t));
221 *delta = padding->delta;
222 uint32_t canary = padding->canary;
223 uintptr_t keys[2];
224 keys[0] = page->keys[0];
225 keys[1] = page->keys[1];
226 bool ok = ((uint32_t)mi_ptr_encode(page,block,keys) == canary && *delta <= *bsize);
227 mi_track_mem_noaccess(padding,sizeof(mi_padding_t));
228 return ok;
229}
230
231// Return the exact usable size of a block.
232static size_t mi_page_usable_size_of(const mi_page_t* page, const mi_block_t* block) {
233 size_t bsize;
234 size_t delta;
235 bool ok = mi_page_decode_padding(page, block, &delta, &bsize);
236 mi_assert_internal(ok); mi_assert_internal(delta <= bsize);
237 return (ok ? bsize - delta : 0);
238}
239
240static bool mi_verify_padding(const mi_page_t* page, const mi_block_t* block, size_t* size, size_t* wrong) {
241 size_t bsize;
242 size_t delta;
243 bool ok = mi_page_decode_padding(page, block, &delta, &bsize);
244 *size = *wrong = bsize;
245 if (!ok) return false;
246 mi_assert_internal(bsize >= delta);
247 *size = bsize - delta;
248 uint8_t* fill = (uint8_t*)block + bsize - delta;
249 const size_t maxpad = (delta > MI_MAX_ALIGN_SIZE ? MI_MAX_ALIGN_SIZE : delta); // check at most the first N padding bytes
250 mi_track_mem_defined(fill,maxpad);
251 for (size_t i = 0; i < maxpad; i++) {
252 if (fill[i] != MI_DEBUG_PADDING) {
253 *wrong = bsize - delta + i;
254 ok = false;
255 break;
256 }
257 }
258 mi_track_mem_noaccess(fill,maxpad);
259 return ok;
260}
261
262static void mi_check_padding(const mi_page_t* page, const mi_block_t* block) {
263 size_t size;
264 size_t wrong;
265 if (!mi_verify_padding(page,block,&size,&wrong)) {
266 _mi_error_message(EFAULT, "buffer overflow in heap block %p of size %zu: write after %zu bytes\n", block, size, wrong );
267 }
268}
269
270// When a non-thread-local block is freed, it becomes part of the thread delayed free
271// list that is freed later by the owning heap. If the exact usable size is too small to
272// contain the pointer for the delayed list, then shrink the padding (by decreasing delta)
273// so it will later not trigger an overflow error in `mi_free_block`.
274static void mi_padding_shrink(const mi_page_t* page, const mi_block_t* block, const size_t min_size) {
275 size_t bsize;
276 size_t delta;
277 bool ok = mi_page_decode_padding(page, block, &delta, &bsize);
278 mi_assert_internal(ok);
279 if (!ok || (bsize - delta) >= min_size) return; // usually already enough space
280 mi_assert_internal(bsize >= min_size);
281 if (bsize < min_size) return; // should never happen
282 size_t new_delta = (bsize - min_size);
283 mi_assert_internal(new_delta < bsize);
284 mi_padding_t* padding = (mi_padding_t*)((uint8_t*)block + bsize);
285 padding->delta = (uint32_t)new_delta;
286}
287#else
288static void mi_check_padding(const mi_page_t* page, const mi_block_t* block) {
289 MI_UNUSED(page);
290 MI_UNUSED(block);
291}
292
293static size_t mi_page_usable_size_of(const mi_page_t* page, const mi_block_t* block) {
294 MI_UNUSED(block);
295 return mi_page_usable_block_size(page);
296}
297
298static void mi_padding_shrink(const mi_page_t* page, const mi_block_t* block, const size_t min_size) {
299 MI_UNUSED(page);
300 MI_UNUSED(block);
301 MI_UNUSED(min_size);
302}
303#endif
304
305// only maintain stats for smaller objects if requested
306#if (MI_STAT>0)
307static void mi_stat_free(const mi_page_t* page, const mi_block_t* block) {
308 #if (MI_STAT < 2)
309 MI_UNUSED(block);
310 #endif
311 mi_heap_t* const heap = mi_heap_get_default();
312 const size_t bsize = mi_page_usable_block_size(page);
313 #if (MI_STAT>1)
314 const size_t usize = mi_page_usable_size_of(page, block);
315 mi_heap_stat_decrease(heap, malloc, usize);
316 #endif
317 if (bsize <= MI_MEDIUM_OBJ_SIZE_MAX) {
318 mi_heap_stat_decrease(heap, normal, bsize);
319 #if (MI_STAT > 1)
320 mi_heap_stat_decrease(heap, normal_bins[_mi_bin(bsize)], 1);
321 #endif
322 }
323 else if (bsize <= MI_LARGE_OBJ_SIZE_MAX) {
324 mi_heap_stat_decrease(heap, large, bsize);
325 }
326 else {
327 mi_heap_stat_decrease(heap, huge, bsize);
328 }
329}
330#else
331static void mi_stat_free(const mi_page_t* page, const mi_block_t* block) {
332 MI_UNUSED(page); MI_UNUSED(block);
333}
334#endif
335
336#if (MI_STAT>0)
337// maintain stats for huge objects
338static void mi_stat_huge_free(const mi_page_t* page) {
339 mi_heap_t* const heap = mi_heap_get_default();
340 const size_t bsize = mi_page_block_size(page); // to match stats in `page.c:mi_page_huge_alloc`
341 if (bsize <= MI_LARGE_OBJ_SIZE_MAX) {
342 mi_heap_stat_decrease(heap, large, bsize);
343 }
344 else {
345 mi_heap_stat_decrease(heap, huge, bsize);
346 }
347}
348#else
349static void mi_stat_huge_free(const mi_page_t* page) {
350 MI_UNUSED(page);
351}
352#endif
353
354// ------------------------------------------------------
355// Free
356// ------------------------------------------------------
357
358// multi-threaded free (or free in huge block)
359static mi_decl_noinline void _mi_free_block_mt(mi_page_t* page, mi_block_t* block)
360{
361 // The padding check may access the non-thread-owned page for the key values.
362 // that is safe as these are constant and the page won't be freed (as the block is not freed yet).
363 mi_check_padding(page, block);
364 mi_padding_shrink(page, block, sizeof(mi_block_t)); // for small size, ensure we can fit the delayed thread pointers without triggering overflow detection
365 #if (MI_DEBUG!=0) && !MI_TRACK_ENABLED // note: when tracking, cannot use mi_usable_size with multi-threading
366 memset(block, MI_DEBUG_FREED, mi_usable_size(block));
367 #endif
368
369 // huge page segments are always abandoned and can be freed immediately
370 mi_segment_t* segment = _mi_page_segment(page);
371 if (segment->kind==MI_SEGMENT_HUGE) {
372 mi_stat_huge_free(page);
373 _mi_segment_huge_page_free(segment, page, block);
374 return;
375 }
376
377 // Try to put the block on either the page-local thread free list, or the heap delayed free list.
378 mi_thread_free_t tfreex;
379 bool use_delayed;
380 mi_thread_free_t tfree = mi_atomic_load_relaxed(&page->xthread_free);
381 do {
382 use_delayed = (mi_tf_delayed(tfree) == MI_USE_DELAYED_FREE);
383 if mi_unlikely(use_delayed) {
384 // unlikely: this only happens on the first concurrent free in a page that is in the full list
385 tfreex = mi_tf_set_delayed(tfree,MI_DELAYED_FREEING);
386 }
387 else {
388 // usual: directly add to page thread_free list
389 mi_block_set_next(page, block, mi_tf_block(tfree));
390 tfreex = mi_tf_set_block(tfree,block);
391 }
392 } while (!mi_atomic_cas_weak_release(&page->xthread_free, &tfree, tfreex));
393
394 if mi_unlikely(use_delayed) {
395 // racy read on `heap`, but ok because MI_DELAYED_FREEING is set (see `mi_heap_delete` and `mi_heap_collect_abandon`)
396 mi_heap_t* const heap = (mi_heap_t*)(mi_atomic_load_acquire(&page->xheap)); //mi_page_heap(page);
397 mi_assert_internal(heap != NULL);
398 if (heap != NULL) {
399 // add to the delayed free list of this heap. (do this atomically as the lock only protects heap memory validity)
400 mi_block_t* dfree = mi_atomic_load_ptr_relaxed(mi_block_t, &heap->thread_delayed_free);
401 do {
402 mi_block_set_nextx(heap,block,dfree, heap->keys);
403 } while (!mi_atomic_cas_ptr_weak_release(mi_block_t,&heap->thread_delayed_free, &dfree, block));
404 }
405
406 // and reset the MI_DELAYED_FREEING flag
407 tfree = mi_atomic_load_relaxed(&page->xthread_free);
408 do {
409 tfreex = tfree;
410 mi_assert_internal(mi_tf_delayed(tfree) == MI_DELAYED_FREEING);
411 tfreex = mi_tf_set_delayed(tfree,MI_NO_DELAYED_FREE);
412 } while (!mi_atomic_cas_weak_release(&page->xthread_free, &tfree, tfreex));
413 }
414}
415
416// regular free
417static inline void _mi_free_block(mi_page_t* page, bool local, mi_block_t* block)
418{
419 // and push it on the free list
420 //const size_t bsize = mi_page_block_size(page);
421 if mi_likely(local) {
422 // owning thread can free a block directly
423 if mi_unlikely(mi_check_is_double_free(page, block)) return;
424 mi_check_padding(page, block);
425 #if (MI_DEBUG!=0) && !MI_TRACK_ENABLED
426 memset(block, MI_DEBUG_FREED, mi_page_block_size(page));
427 #endif
428 mi_block_set_next(page, block, page->local_free);
429 page->local_free = block;
430 page->used--;
431 if mi_unlikely(mi_page_all_free(page)) {
432 _mi_page_retire(page);
433 }
434 else if mi_unlikely(mi_page_is_in_full(page)) {
435 _mi_page_unfull(page);
436 }
437 }
438 else {
439 _mi_free_block_mt(page,block);
440 }
441}
442
443
444// Adjust a block that was allocated aligned, to the actual start of the block in the page.
445mi_block_t* _mi_page_ptr_unalign(const mi_segment_t* segment, const mi_page_t* page, const void* p) {
446 mi_assert_internal(page!=NULL && p!=NULL);
447 const size_t diff = (uint8_t*)p - _mi_page_start(segment, page, NULL);
448 const size_t adjust = (diff % mi_page_block_size(page));
449 return (mi_block_t*)((uintptr_t)p - adjust);
450}
451
452
453static void mi_decl_noinline mi_free_generic(const mi_segment_t* segment, bool local, void* p) mi_attr_noexcept {
454 mi_page_t* const page = _mi_segment_page_of(segment, p);
455 mi_block_t* const block = (mi_page_has_aligned(page) ? _mi_page_ptr_unalign(segment, page, p) : (mi_block_t*)p);
456 mi_stat_free(page, block); // stat_free may access the padding
457 mi_track_free(p);
458 _mi_free_block(page, local, block);
459}
460
461// Get the segment data belonging to a pointer
462// This is just a single `and` in assembly but does further checks in debug mode
463// (and secure mode) if this was a valid pointer.
464static inline mi_segment_t* mi_checked_ptr_segment(const void* p, const char* msg)
465{
466 MI_UNUSED(msg);
467#if (MI_DEBUG>0)
468 if mi_unlikely(((uintptr_t)p & (MI_INTPTR_SIZE - 1)) != 0) {
469 _mi_error_message(EINVAL, "%s: invalid (unaligned) pointer: %p\n", msg, p);
470 return NULL;
471 }
472#endif
473
474 mi_segment_t* const segment = _mi_ptr_segment(p);
475 if mi_unlikely(segment == NULL) return NULL; // checks also for (p==NULL)
476
477#if (MI_DEBUG>0)
478 if mi_unlikely(!mi_is_in_heap_region(p)) {
479 _mi_warning_message("%s: pointer might not point to a valid heap region: %p\n"
480 "(this may still be a valid very large allocation (over 64MiB))\n", msg, p);
481 if mi_likely(_mi_ptr_cookie(segment) == segment->cookie) {
482 _mi_warning_message("(yes, the previous pointer %p was valid after all)\n", p);
483 }
484 }
485#endif
486#if (MI_DEBUG>0 || MI_SECURE>=4)
487 if mi_unlikely(_mi_ptr_cookie(segment) != segment->cookie) {
488 _mi_error_message(EINVAL, "%s: pointer does not point to a valid heap space: %p\n", msg, p);
489 return NULL;
490 }
491#endif
492 return segment;
493}
494
495// Free a block
496void mi_free(void* p) mi_attr_noexcept
497{
498 mi_segment_t* const segment = mi_checked_ptr_segment(p,"mi_free");
499 if mi_unlikely(segment == NULL) return;
500
501 mi_threadid_t tid = _mi_thread_id();
502 mi_page_t* const page = _mi_segment_page_of(segment, p);
503
504 if mi_likely(tid == mi_atomic_load_relaxed(&segment->thread_id) && page->flags.full_aligned == 0) { // the thread id matches and it is not a full page, nor has aligned blocks
505 // local, and not full or aligned
506 mi_block_t* block = (mi_block_t*)(p);
507 if mi_unlikely(mi_check_is_double_free(page,block)) return;
508 mi_check_padding(page, block);
509 mi_stat_free(page, block);
510 #if (MI_DEBUG!=0) && !MI_TRACK_ENABLED
511 memset(block, MI_DEBUG_FREED, mi_page_block_size(page));
512 #endif
513 mi_track_free(p);
514 mi_block_set_next(page, block, page->local_free);
515 page->local_free = block;
516 if mi_unlikely(--page->used == 0) { // using this expression generates better code than: page->used--; if (mi_page_all_free(page))
517 _mi_page_retire(page);
518 }
519 }
520 else {
521 // non-local, aligned blocks, or a full page; use the more generic path
522 // note: recalc page in generic to improve code generation
523 mi_free_generic(segment, tid == segment->thread_id, p);
524 }
525}
526
527// return true if successful
528bool _mi_free_delayed_block(mi_block_t* block) {
529 // get segment and page
530 const mi_segment_t* const segment = _mi_ptr_segment(block);
531 mi_assert_internal(_mi_ptr_cookie(segment) == segment->cookie);
532 mi_assert_internal(_mi_thread_id() == segment->thread_id);
533 mi_page_t* const page = _mi_segment_page_of(segment, block);
534
535 // Clear the no-delayed flag so delayed freeing is used again for this page.
536 // This must be done before collecting the free lists on this page -- otherwise
537 // some blocks may end up in the page `thread_free` list with no blocks in the
538 // heap `thread_delayed_free` list which may cause the page to be never freed!
539 // (it would only be freed if we happen to scan it in `mi_page_queue_find_free_ex`)
540 if (!_mi_page_try_use_delayed_free(page, MI_USE_DELAYED_FREE, false /* dont overwrite never delayed */)) {
541 return false;
542 }
543
544 // collect all other non-local frees to ensure up-to-date `used` count
545 _mi_page_free_collect(page, false);
546
547 // and free the block (possibly freeing the page as well since used is updated)
548 _mi_free_block(page, true, block);
549 return true;
550}
551
552// Bytes available in a block
553mi_decl_noinline static size_t mi_page_usable_aligned_size_of(const mi_segment_t* segment, const mi_page_t* page, const void* p) mi_attr_noexcept {
554 const mi_block_t* block = _mi_page_ptr_unalign(segment, page, p);
555 const size_t size = mi_page_usable_size_of(page, block);
556 const ptrdiff_t adjust = (uint8_t*)p - (uint8_t*)block;
557 mi_assert_internal(adjust >= 0 && (size_t)adjust <= size);
558 return (size - adjust);
559}
560
561static inline size_t _mi_usable_size(const void* p, const char* msg) mi_attr_noexcept {
562 const mi_segment_t* const segment = mi_checked_ptr_segment(p, msg);
563 if (segment==NULL) return 0; // also returns 0 if `p == NULL`
564 const mi_page_t* const page = _mi_segment_page_of(segment, p);
565 if mi_likely(!mi_page_has_aligned(page)) {
566 const mi_block_t* block = (const mi_block_t*)p;
567 return mi_page_usable_size_of(page, block);
568 }
569 else {
570 // split out to separate routine for improved code generation
571 return mi_page_usable_aligned_size_of(segment, page, p);
572 }
573}
574
575mi_decl_nodiscard size_t mi_usable_size(const void* p) mi_attr_noexcept {
576 return _mi_usable_size(p, "mi_usable_size");
577}
578
579
580// ------------------------------------------------------
581// ensure explicit external inline definitions are emitted!
582// ------------------------------------------------------
583
584#ifdef __cplusplus
585void* _mi_externs[] = {
586 (void*)&_mi_page_malloc,
587 (void*)&_mi_heap_malloc_zero,
588 (void*)&mi_malloc,
589 (void*)&mi_malloc_small,
590 (void*)&mi_zalloc_small,
591 (void*)&mi_heap_malloc,
592 (void*)&mi_heap_zalloc,
593 (void*)&mi_heap_malloc_small
594};
595#endif
596
597
598// ------------------------------------------------------
599// Allocation extensions
600// ------------------------------------------------------
601
602void mi_free_size(void* p, size_t size) mi_attr_noexcept {
603 MI_UNUSED_RELEASE(size);
604 mi_assert(p == NULL || size <= _mi_usable_size(p,"mi_free_size"));
605 mi_free(p);
606}
607
608void mi_free_size_aligned(void* p, size_t size, size_t alignment) mi_attr_noexcept {
609 MI_UNUSED_RELEASE(alignment);
610 mi_assert(((uintptr_t)p % alignment) == 0);
611 mi_free_size(p,size);
612}
613
614void mi_free_aligned(void* p, size_t alignment) mi_attr_noexcept {
615 MI_UNUSED_RELEASE(alignment);
616 mi_assert(((uintptr_t)p % alignment) == 0);
617 mi_free(p);
618}
619
620mi_decl_nodiscard extern inline mi_decl_restrict void* mi_heap_calloc(mi_heap_t* heap, size_t count, size_t size) mi_attr_noexcept {
621 size_t total;
622 if (mi_count_size_overflow(count,size,&total)) return NULL;
623 return mi_heap_zalloc(heap,total);
624}
625
626mi_decl_nodiscard mi_decl_restrict void* mi_calloc(size_t count, size_t size) mi_attr_noexcept {
627 return mi_heap_calloc(mi_get_default_heap(),count,size);
628}
629
630// Uninitialized `calloc`
631mi_decl_nodiscard extern mi_decl_restrict void* mi_heap_mallocn(mi_heap_t* heap, size_t count, size_t size) mi_attr_noexcept {
632 size_t total;
633 if (mi_count_size_overflow(count, size, &total)) return NULL;
634 return mi_heap_malloc(heap, total);
635}
636
637mi_decl_nodiscard mi_decl_restrict void* mi_mallocn(size_t count, size_t size) mi_attr_noexcept {
638 return mi_heap_mallocn(mi_get_default_heap(),count,size);
639}
640
641// Expand (or shrink) in place (or fail)
642void* mi_expand(void* p, size_t newsize) mi_attr_noexcept {
643 #if MI_PADDING
644 // we do not shrink/expand with padding enabled
645 MI_UNUSED(p); MI_UNUSED(newsize);
646 return NULL;
647 #else
648 if (p == NULL) return NULL;
649 const size_t size = _mi_usable_size(p,"mi_expand");
650 if (newsize > size) return NULL;
651 return p; // it fits
652 #endif
653}
654
655void* _mi_heap_realloc_zero(mi_heap_t* heap, void* p, size_t newsize, bool zero) mi_attr_noexcept {
656 // if p == NULL then behave as malloc.
657 // else if size == 0 then reallocate to a zero-sized block (and don't return NULL, just as mi_malloc(0)).
658 // (this means that returning NULL always indicates an error, and `p` will not have been freed in that case.)
659 const size_t size = _mi_usable_size(p,"mi_realloc"); // also works if p == NULL (with size 0)
660 if mi_unlikely(newsize <= size && newsize >= (size / 2) && newsize > 0) { // note: newsize must be > 0 or otherwise we return NULL for realloc(NULL,0)
661 // todo: adjust potential padding to reflect the new size?
662 mi_track_free(p);
663 mi_track_malloc(p,newsize,true);
664 return p; // reallocation still fits and not more than 50% waste
665 }
666 void* newp = mi_heap_malloc(heap,newsize);
667 if mi_likely(newp != NULL) {
668 if (zero && newsize > size) {
669 // also set last word in the previous allocation to zero to ensure any padding is zero-initialized
670 const size_t start = (size >= sizeof(intptr_t) ? size - sizeof(intptr_t) : 0);
671 memset((uint8_t*)newp + start, 0, newsize - start);
672 }
673 if mi_likely(p != NULL) {
674 if mi_likely(_mi_is_aligned(p, sizeof(uintptr_t))) { // a client may pass in an arbitrary pointer `p`..
675 const size_t copysize = (newsize > size ? size : newsize);
676 mi_track_mem_defined(p,copysize); // _mi_useable_size may be too large for byte precise memory tracking..
677 _mi_memcpy_aligned(newp, p, copysize);
678 }
679 mi_free(p); // only free the original pointer if successful
680 }
681 }
682 return newp;
683}
684
685mi_decl_nodiscard void* mi_heap_realloc(mi_heap_t* heap, void* p, size_t newsize) mi_attr_noexcept {
686 return _mi_heap_realloc_zero(heap, p, newsize, false);
687}
688
689mi_decl_nodiscard void* mi_heap_reallocn(mi_heap_t* heap, void* p, size_t count, size_t size) mi_attr_noexcept {
690 size_t total;
691 if (mi_count_size_overflow(count, size, &total)) return NULL;
692 return mi_heap_realloc(heap, p, total);
693}
694
695
696// Reallocate but free `p` on errors
697mi_decl_nodiscard void* mi_heap_reallocf(mi_heap_t* heap, void* p, size_t newsize) mi_attr_noexcept {
698 void* newp = mi_heap_realloc(heap, p, newsize);
699 if (newp==NULL && p!=NULL) mi_free(p);
700 return newp;
701}
702
703mi_decl_nodiscard void* mi_heap_rezalloc(mi_heap_t* heap, void* p, size_t newsize) mi_attr_noexcept {
704 return _mi_heap_realloc_zero(heap, p, newsize, true);
705}
706
707mi_decl_nodiscard void* mi_heap_recalloc(mi_heap_t* heap, void* p, size_t count, size_t size) mi_attr_noexcept {
708 size_t total;
709 if (mi_count_size_overflow(count, size, &total)) return NULL;
710 return mi_heap_rezalloc(heap, p, total);
711}
712
713
714mi_decl_nodiscard void* mi_realloc(void* p, size_t newsize) mi_attr_noexcept {
715 return mi_heap_realloc(mi_get_default_heap(),p,newsize);
716}
717
718mi_decl_nodiscard void* mi_reallocn(void* p, size_t count, size_t size) mi_attr_noexcept {
719 return mi_heap_reallocn(mi_get_default_heap(),p,count,size);
720}
721
722// Reallocate but free `p` on errors
723mi_decl_nodiscard void* mi_reallocf(void* p, size_t newsize) mi_attr_noexcept {
724 return mi_heap_reallocf(mi_get_default_heap(),p,newsize);
725}
726
727mi_decl_nodiscard void* mi_rezalloc(void* p, size_t newsize) mi_attr_noexcept {
728 return mi_heap_rezalloc(mi_get_default_heap(), p, newsize);
729}
730
731mi_decl_nodiscard void* mi_recalloc(void* p, size_t count, size_t size) mi_attr_noexcept {
732 return mi_heap_recalloc(mi_get_default_heap(), p, count, size);
733}
734
735
736
737// ------------------------------------------------------
738// strdup, strndup, and realpath
739// ------------------------------------------------------
740
741// `strdup` using mi_malloc
742mi_decl_nodiscard mi_decl_restrict char* mi_heap_strdup(mi_heap_t* heap, const char* s) mi_attr_noexcept {
743 if (s == NULL) return NULL;
744 size_t n = strlen(s);
745 char* t = (char*)mi_heap_malloc(heap,n+1);
746 if (t != NULL) _mi_memcpy(t, s, n + 1);
747 return t;
748}
749
750mi_decl_nodiscard mi_decl_restrict char* mi_strdup(const char* s) mi_attr_noexcept {
751 return mi_heap_strdup(mi_get_default_heap(), s);
752}
753
754// `strndup` using mi_malloc
755mi_decl_nodiscard mi_decl_restrict char* mi_heap_strndup(mi_heap_t* heap, const char* s, size_t n) mi_attr_noexcept {
756 if (s == NULL) return NULL;
757 const char* end = (const char*)memchr(s, 0, n); // find end of string in the first `n` characters (returns NULL if not found)
758 const size_t m = (end != NULL ? (size_t)(end - s) : n); // `m` is the minimum of `n` or the end-of-string
759 mi_assert_internal(m <= n);
760 char* t = (char*)mi_heap_malloc(heap, m+1);
761 if (t == NULL) return NULL;
762 _mi_memcpy(t, s, m);
763 t[m] = 0;
764 return t;
765}
766
767mi_decl_nodiscard mi_decl_restrict char* mi_strndup(const char* s, size_t n) mi_attr_noexcept {
768 return mi_heap_strndup(mi_get_default_heap(),s,n);
769}
770
771#ifndef __wasi__
772// `realpath` using mi_malloc
773#ifdef _WIN32
774#ifndef PATH_MAX
775#define PATH_MAX MAX_PATH
776#endif
777#include <windows.h>
778mi_decl_nodiscard mi_decl_restrict char* mi_heap_realpath(mi_heap_t* heap, const char* fname, char* resolved_name) mi_attr_noexcept {
779 // todo: use GetFullPathNameW to allow longer file names
780 char buf[PATH_MAX];
781 DWORD res = GetFullPathNameA(fname, PATH_MAX, (resolved_name == NULL ? buf : resolved_name), NULL);
782 if (res == 0) {
783 errno = GetLastError(); return NULL;
784 }
785 else if (res > PATH_MAX) {
786 errno = EINVAL; return NULL;
787 }
788 else if (resolved_name != NULL) {
789 return resolved_name;
790 }
791 else {
792 return mi_heap_strndup(heap, buf, PATH_MAX);
793 }
794}
795#else
796#include <unistd.h> // pathconf
797static size_t mi_path_max(void) {
798 static size_t path_max = 0;
799 if (path_max <= 0) {
800 long m = pathconf("/",_PC_PATH_MAX);
801 if (m <= 0) path_max = 4096; // guess
802 else if (m < 256) path_max = 256; // at least 256
803 else path_max = m;
804 }
805 return path_max;
806}
807
808char* mi_heap_realpath(mi_heap_t* heap, const char* fname, char* resolved_name) mi_attr_noexcept {
809 if (resolved_name != NULL) {
810 return realpath(fname,resolved_name);
811 }
812 else {
813 size_t n = mi_path_max();
814 char* buf = (char*)mi_malloc(n+1);
815 if (buf==NULL) return NULL;
816 char* rname = realpath(fname,buf);
817 char* result = mi_heap_strndup(heap,rname,n); // ok if `rname==NULL`
818 mi_free(buf);
819 return result;
820 }
821}
822#endif
823
824mi_decl_nodiscard mi_decl_restrict char* mi_realpath(const char* fname, char* resolved_name) mi_attr_noexcept {
825 return mi_heap_realpath(mi_get_default_heap(),fname,resolved_name);
826}
827#endif
828
829/*-------------------------------------------------------
830C++ new and new_aligned
831The standard requires calling into `get_new_handler` and
832throwing the bad_alloc exception on failure. If we compile
833with a C++ compiler we can implement this precisely. If we
834use a C compiler we cannot throw a `bad_alloc` exception
835but we call `exit` instead (i.e. not returning).
836-------------------------------------------------------*/
837
838#ifdef __cplusplus
839#include <new>
840static bool mi_try_new_handler(bool nothrow) {
841 #if defined(_MSC_VER) || (__cplusplus >= 201103L)
842 std::new_handler h = std::get_new_handler();
843 #else
844 std::new_handler h = std::set_new_handler();
845 std::set_new_handler(h);
846 #endif
847 if (h==NULL) {
848 _mi_error_message(ENOMEM, "out of memory in 'new'");
849 if (!nothrow) {
850 throw std::bad_alloc();
851 }
852 return false;
853 }
854 else {
855 h();
856 return true;
857 }
858}
859#else
860typedef void (*std_new_handler_t)(void);
861
862#if (defined(__GNUC__) || (defined(__clang__) && !defined(_MSC_VER))) // exclude clang-cl, see issue #631
863std_new_handler_t __attribute__((weak)) _ZSt15get_new_handlerv(void) {
864 return NULL;
865}
866static std_new_handler_t mi_get_new_handler(void) {
867 return _ZSt15get_new_handlerv();
868}
869#else
870// note: on windows we could dynamically link to `?get_new_handler@std@@YAP6AXXZXZ`.
871static std_new_handler_t mi_get_new_handler() {
872 return NULL;
873}
874#endif
875
876static bool mi_try_new_handler(bool nothrow) {
877 std_new_handler_t h = mi_get_new_handler();
878 if (h==NULL) {
879 _mi_error_message(ENOMEM, "out of memory in 'new'");
880 if (!nothrow) {
881 abort(); // cannot throw in plain C, use abort
882 }
883 return false;
884 }
885 else {
886 h();
887 return true;
888 }
889}
890#endif
891
892static mi_decl_noinline void* mi_try_new(size_t size, bool nothrow ) {
893 void* p = NULL;
894 while(p == NULL && mi_try_new_handler(nothrow)) {
895 p = mi_malloc(size);
896 }
897 return p;
898}
899
900mi_decl_nodiscard mi_decl_restrict void* mi_new(size_t size) {
901 void* p = mi_malloc(size);
902 if mi_unlikely(p == NULL) return mi_try_new(size,false);
903 return p;
904}
905
906mi_decl_nodiscard mi_decl_restrict void* mi_new_nothrow(size_t size) mi_attr_noexcept {
907 void* p = mi_malloc(size);
908 if mi_unlikely(p == NULL) return mi_try_new(size, true);
909 return p;
910}
911
912mi_decl_nodiscard mi_decl_restrict void* mi_new_aligned(size_t size, size_t alignment) {
913 void* p;
914 do {
915 p = mi_malloc_aligned(size, alignment);
916 }
917 while(p == NULL && mi_try_new_handler(false));
918 return p;
919}
920
921mi_decl_nodiscard mi_decl_restrict void* mi_new_aligned_nothrow(size_t size, size_t alignment) mi_attr_noexcept {
922 void* p;
923 do {
924 p = mi_malloc_aligned(size, alignment);
925 }
926 while(p == NULL && mi_try_new_handler(true));
927 return p;
928}
929
930mi_decl_nodiscard mi_decl_restrict void* mi_new_n(size_t count, size_t size) {
931 size_t total;
932 if mi_unlikely(mi_count_size_overflow(count, size, &total)) {
933 mi_try_new_handler(false); // on overflow we invoke the try_new_handler once to potentially throw std::bad_alloc
934 return NULL;
935 }
936 else {
937 return mi_new(total);
938 }
939}
940
941mi_decl_nodiscard void* mi_new_realloc(void* p, size_t newsize) {
942 void* q;
943 do {
944 q = mi_realloc(p, newsize);
945 } while (q == NULL && mi_try_new_handler(false));
946 return q;
947}
948
949mi_decl_nodiscard void* mi_new_reallocn(void* p, size_t newcount, size_t size) {
950 size_t total;
951 if mi_unlikely(mi_count_size_overflow(newcount, size, &total)) {
952 mi_try_new_handler(false); // on overflow we invoke the try_new_handler once to potentially throw std::bad_alloc
953 return NULL;
954 }
955 else {
956 return mi_new_realloc(p, total);
957 }
958}
959