GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored from https://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
a59f3d620bf32fa6426ca3f1da69c3c1f619e4e2

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/allocator/mimalloc-sys/mimalloc/src

allocator/mimalloc-sys/mimalloc/src/alloc.c

1060lines · modeblame

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