1 | /* ---------------------------------------------------------------------------- |
2 | Copyright (c) 2018-2022, Microsoft Research, Daan Leijen |
3 | This is free software; you can redistribute it and/or modify it under the |
4 | terms 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. |
29 | extern 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 | |
88 | static 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 |
111 | mi_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 | |
115 | mi_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 |
120 | extern 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 | |
140 | mi_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 | |
144 | mi_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 |
149 | mi_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 | |
153 | mi_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 | |
157 | mi_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 |
169 | static 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 | |
177 | static 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 | |
192 | static 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 |
205 | static 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 |
217 | static 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. |
232 | static 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 | |
240 | static 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 | |
262 | static 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`. |
274 | static 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 |
288 | static void mi_check_padding(const mi_page_t* page, const mi_block_t* block) { |
289 | MI_UNUSED(page); |
290 | MI_UNUSED(block); |
291 | } |
292 | |
293 | static 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 | |
298 | static 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) |
307 | static 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 |
331 | static 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 |
338 | static 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 |
349 | static 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) |
359 | static 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 |
417 | static 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. |
445 | mi_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 | |
453 | static 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. |
464 | static 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 |
496 | void 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 |
528 | bool _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 |
553 | mi_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 | |
561 | static 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 | |
575 | mi_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 |
585 | void* _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 | |
602 | void 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 | |
608 | void 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 | |
614 | void 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 | |
620 | mi_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 | |
626 | mi_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` |
631 | mi_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 | |
637 | mi_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) |
642 | void* 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 | |
655 | void* _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 | |
685 | mi_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 | |
689 | mi_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 |
697 | mi_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 | |
703 | mi_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 | |
707 | mi_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 | |
714 | mi_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 | |
718 | mi_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 |
723 | mi_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 | |
727 | mi_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 | |
731 | mi_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 |
742 | mi_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 | |
750 | mi_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 |
755 | mi_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 | |
767 | mi_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> |
778 | mi_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 |
797 | static 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 | |
808 | char* 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 | |
824 | mi_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 | /*------------------------------------------------------- |
830 | C++ new and new_aligned |
831 | The standard requires calling into `get_new_handler` and |
832 | throwing the bad_alloc exception on failure. If we compile |
833 | with a C++ compiler we can implement this precisely. If we |
834 | use a C compiler we cannot throw a `bad_alloc` exception |
835 | but we call `exit` instead (i.e. not returning). |
836 | -------------------------------------------------------*/ |
837 | |
838 | #ifdef __cplusplus |
839 | #include <new> |
840 | static 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 |
860 | typedef void (*std_new_handler_t)(void); |
861 | |
862 | #if (defined(__GNUC__) || (defined(__clang__) && !defined(_MSC_VER))) // exclude clang-cl, see issue #631 |
863 | std_new_handler_t __attribute__((weak)) _ZSt15get_new_handlerv(void) { |
864 | return NULL; |
865 | } |
866 | static 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`. |
871 | static std_new_handler_t mi_get_new_handler() { |
872 | return NULL; |
873 | } |
874 | #endif |
875 | |
876 | static 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 | |
892 | static 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 | |
900 | mi_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 | |
906 | mi_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 | |
912 | mi_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 | |
921 | mi_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 | |
930 | mi_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 | |
941 | mi_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 | |
949 | mi_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 | |