1/* ----------------------------------------------------------------------------
2Copyright (c) 2018, 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#pragma once
8#ifndef MIMALLOC_INTERNAL_H
9#define MIMALLOC_INTERNAL_H
10
11#include "mimalloc-types.h"
12
13#if defined(MI_MALLOC_OVERRIDE) && (defined(__APPLE__) || defined(__OpenBSD__))
14#define MI_TLS_RECURSE_GUARD
15#endif
16
17#if (MI_DEBUG>0)
18#define mi_trace_message(...) _mi_trace_message(__VA_ARGS__)
19#else
20#define mi_trace_message(...)
21#endif
22
23#if defined(_MSC_VER)
24#define mi_decl_noinline __declspec(noinline)
25#define mi_attr_noreturn
26#elif defined(__GNUC__) || defined(__clang__)
27#define mi_decl_noinline __attribute__((noinline))
28#define mi_attr_noreturn __attribute__((noreturn))
29#else
30#define mi_decl_noinline
31#define mi_attr_noreturn
32#endif
33
34
35// "options.c"
36void _mi_fputs(mi_output_fun* out, const char* prefix, const char* message);
37void _mi_fprintf(mi_output_fun* out, const char* fmt, ...);
38void _mi_error_message(const char* fmt, ...);
39void _mi_warning_message(const char* fmt, ...);
40void _mi_verbose_message(const char* fmt, ...);
41void _mi_trace_message(const char* fmt, ...);
42void _mi_options_init(void);
43void _mi_fatal_error(const char* fmt, ...) mi_attr_noreturn;
44
45// "init.c"
46extern mi_stats_t _mi_stats_main;
47extern const mi_page_t _mi_page_empty;
48bool _mi_is_main_thread(void);
49uintptr_t _mi_random_shuffle(uintptr_t x);
50uintptr_t _mi_random_init(uintptr_t seed /* can be zero */);
51bool _mi_preloading(); // true while the C runtime is not ready
52
53// os.c
54size_t _mi_os_page_size(void);
55void _mi_os_init(void); // called from process init
56void* _mi_os_alloc(size_t size, mi_stats_t* stats); // to allocate thread local data
57void _mi_os_free(void* p, size_t size, mi_stats_t* stats); // to free thread local data
58size_t _mi_os_good_alloc_size(size_t size);
59
60// memory.c
61void* _mi_mem_alloc_aligned(size_t size, size_t alignment, bool* commit, bool* large, bool* is_zero, size_t* id, mi_os_tld_t* tld);
62void _mi_mem_free(void* p, size_t size, size_t id, mi_stats_t* stats);
63
64bool _mi_mem_reset(void* p, size_t size, mi_stats_t* stats);
65bool _mi_mem_unreset(void* p, size_t size, bool* is_zero, mi_stats_t* stats);
66bool _mi_mem_commit(void* p, size_t size, bool* is_zero, mi_stats_t* stats);
67bool _mi_mem_protect(void* addr, size_t size);
68bool _mi_mem_unprotect(void* addr, size_t size);
69
70void _mi_mem_collect(mi_stats_t* stats);
71
72// "segment.c"
73mi_page_t* _mi_segment_page_alloc(size_t block_wsize, mi_segments_tld_t* tld, mi_os_tld_t* os_tld);
74void _mi_segment_page_free(mi_page_t* page, bool force, mi_segments_tld_t* tld);
75void _mi_segment_page_abandon(mi_page_t* page, mi_segments_tld_t* tld);
76bool _mi_segment_try_reclaim_abandoned( mi_heap_t* heap, bool try_all, mi_segments_tld_t* tld);
77void _mi_segment_thread_collect(mi_segments_tld_t* tld);
78uint8_t* _mi_segment_page_start(const mi_segment_t* segment, const mi_page_t* page, size_t block_size, size_t* page_size); // page start for any page
79
80// "page.c"
81void* _mi_malloc_generic(mi_heap_t* heap, size_t size) mi_attr_noexcept mi_attr_malloc;
82
83void _mi_page_retire(mi_page_t* page); // free the page if there are no other pages with many free blocks
84void _mi_page_unfull(mi_page_t* page);
85void _mi_page_free(mi_page_t* page, mi_page_queue_t* pq, bool force); // free the page
86void _mi_page_abandon(mi_page_t* page, mi_page_queue_t* pq); // abandon the page, to be picked up by another thread...
87void _mi_heap_delayed_free(mi_heap_t* heap);
88
89void _mi_page_use_delayed_free(mi_page_t* page, mi_delayed_t delay);
90size_t _mi_page_queue_append(mi_heap_t* heap, mi_page_queue_t* pq, mi_page_queue_t* append);
91void _mi_deferred_free(mi_heap_t* heap, bool force);
92
93void _mi_page_free_collect(mi_page_t* page,bool force);
94void _mi_page_reclaim(mi_heap_t* heap, mi_page_t* page); // callback from segments
95
96size_t _mi_bin_size(uint8_t bin); // for stats
97uint8_t _mi_bin(size_t size); // for stats
98uint8_t _mi_bsr(uintptr_t x); // bit-scan-right, used on BSD in "os.c"
99
100// "heap.c"
101void _mi_heap_destroy_pages(mi_heap_t* heap);
102void _mi_heap_collect_abandon(mi_heap_t* heap);
103uintptr_t _mi_heap_random(mi_heap_t* heap);
104void _mi_heap_set_default_direct(mi_heap_t* heap);
105
106// "stats.c"
107void _mi_stats_done(mi_stats_t* stats);
108double _mi_clock_end(double start);
109double _mi_clock_start(void);
110
111// "alloc.c"
112void* _mi_page_malloc(mi_heap_t* heap, mi_page_t* page, size_t size) mi_attr_noexcept; // called from `_mi_malloc_generic`
113void* _mi_heap_malloc_zero(mi_heap_t* heap, size_t size, bool zero);
114void* _mi_heap_realloc_zero(mi_heap_t* heap, void* p, size_t newsize, bool zero);
115mi_block_t* _mi_page_ptr_unalign(const mi_segment_t* segment, const mi_page_t* page, const void* p);
116bool _mi_free_delayed_block(mi_block_t* block);
117void _mi_block_zero_init(const mi_page_t* page, void* p, size_t size);
118
119#if MI_DEBUG>1
120bool _mi_page_is_valid(mi_page_t* page);
121#endif
122
123
124// ------------------------------------------------------
125// Branches
126// ------------------------------------------------------
127
128#if defined(__GNUC__) || defined(__clang__)
129#define mi_unlikely(x) __builtin_expect((x),0)
130#define mi_likely(x) __builtin_expect((x),1)
131#else
132#define mi_unlikely(x) (x)
133#define mi_likely(x) (x)
134#endif
135
136#ifndef __has_builtin
137#define __has_builtin(x) 0
138#endif
139
140
141
142/* -----------------------------------------------------------
143 Inlined definitions
144----------------------------------------------------------- */
145#define UNUSED(x) (void)(x)
146#if (MI_DEBUG>0)
147#define UNUSED_RELEASE(x)
148#else
149#define UNUSED_RELEASE(x) UNUSED(x)
150#endif
151
152#define MI_INIT4(x) x(),x(),x(),x()
153#define MI_INIT8(x) MI_INIT4(x),MI_INIT4(x)
154#define MI_INIT16(x) MI_INIT8(x),MI_INIT8(x)
155#define MI_INIT32(x) MI_INIT16(x),MI_INIT16(x)
156#define MI_INIT64(x) MI_INIT32(x),MI_INIT32(x)
157#define MI_INIT128(x) MI_INIT64(x),MI_INIT64(x)
158#define MI_INIT256(x) MI_INIT128(x),MI_INIT128(x)
159
160
161// Overflow detecting multiply
162#define MI_MUL_NO_OVERFLOW ((size_t)1 << (4*sizeof(size_t))) // sqrt(SIZE_MAX)
163static inline bool mi_mul_overflow(size_t count, size_t size, size_t* total) {
164#if __has_builtin(__builtin_umul_overflow) || __GNUC__ >= 5
165#include <limits.h> // UINT_MAX, ULONG_MAX
166#if (SIZE_MAX == UINT_MAX)
167 return __builtin_umul_overflow(count, size, total);
168#elif (SIZE_MAX == ULONG_MAX)
169 return __builtin_umull_overflow(count, size, total);
170#else
171 return __builtin_umulll_overflow(count, size, total);
172#endif
173#else /* __builtin_umul_overflow is unavailable */
174 *total = count * size;
175 return ((size >= MI_MUL_NO_OVERFLOW || count >= MI_MUL_NO_OVERFLOW)
176 && size > 0 && (SIZE_MAX / size) < count);
177#endif
178}
179
180// Is `x` a power of two? (0 is considered a power of two)
181static inline bool _mi_is_power_of_two(uintptr_t x) {
182 return ((x & (x - 1)) == 0);
183}
184
185// Align upwards
186static inline uintptr_t _mi_align_up(uintptr_t sz, size_t alignment) {
187 uintptr_t mask = alignment - 1;
188 if ((alignment & mask) == 0) { // power of two?
189 return ((sz + mask) & ~mask);
190 }
191 else {
192 return (((sz + mask)/alignment)*alignment);
193 }
194}
195
196// Is memory zero initialized?
197static inline bool mi_mem_is_zero(void* p, size_t size) {
198 for (size_t i = 0; i < size; i++) {
199 if (((uint8_t*)p)[i] != 0) return false;
200 }
201 return true;
202}
203
204// Align a byte size to a size in _machine words_,
205// i.e. byte size == `wsize*sizeof(void*)`.
206static inline size_t _mi_wsize_from_size(size_t size) {
207 mi_assert_internal(size <= SIZE_MAX - sizeof(uintptr_t));
208 return (size + sizeof(uintptr_t) - 1) / sizeof(uintptr_t);
209}
210
211
212/* -----------------------------------------------------------
213 The thread local default heap
214----------------------------------------------------------- */
215
216extern const mi_heap_t _mi_heap_empty; // read-only empty heap, initial value of the thread local default heap
217extern mi_heap_t _mi_heap_main; // statically allocated main backing heap
218extern bool _mi_process_is_initialized;
219
220extern mi_decl_thread mi_heap_t* _mi_heap_default; // default heap to allocate from
221
222static inline mi_heap_t* mi_get_default_heap(void) {
223#ifdef MI_TLS_RECURSE_GUARD
224 // on some platforms, like macOS, the dynamic loader calls `malloc`
225 // to initialize thread local data. To avoid recursion, we need to avoid
226 // accessing the thread local `_mi_default_heap` until our module is loaded
227 // and use the statically allocated main heap until that time.
228 // TODO: patch ourselves dynamically to avoid this check every time?
229 if (!_mi_process_is_initialized) return &_mi_heap_main;
230#endif
231 return _mi_heap_default;
232}
233
234static inline bool mi_heap_is_default(const mi_heap_t* heap) {
235 return (heap == mi_get_default_heap());
236}
237
238static inline bool mi_heap_is_backing(const mi_heap_t* heap) {
239 return (heap->tld->heap_backing == heap);
240}
241
242static inline bool mi_heap_is_initialized(mi_heap_t* heap) {
243 mi_assert_internal(heap != NULL);
244 return (heap != &_mi_heap_empty);
245}
246
247static inline uintptr_t _mi_ptr_cookie(const void* p) {
248 return ((uintptr_t)p ^ _mi_heap_main.cookie);
249}
250
251/* -----------------------------------------------------------
252 Pages
253----------------------------------------------------------- */
254
255static inline mi_page_t* _mi_heap_get_free_small_page(mi_heap_t* heap, size_t size) {
256 mi_assert_internal(size <= MI_SMALL_SIZE_MAX);
257 return heap->pages_free_direct[_mi_wsize_from_size(size)];
258}
259
260// Get the page belonging to a certain size class
261static inline mi_page_t* _mi_get_free_small_page(size_t size) {
262 return _mi_heap_get_free_small_page(mi_get_default_heap(), size);
263}
264
265// Segment that contains the pointer
266static inline mi_segment_t* _mi_ptr_segment(const void* p) {
267 // mi_assert_internal(p != NULL);
268 return (mi_segment_t*)((uintptr_t)p & ~MI_SEGMENT_MASK);
269}
270
271// Segment belonging to a page
272static inline mi_segment_t* _mi_page_segment(const mi_page_t* page) {
273 mi_segment_t* segment = _mi_ptr_segment(page);
274 mi_assert_internal(segment == NULL || page == &segment->pages[page->segment_idx]);
275 return segment;
276}
277
278// used internally
279static inline uintptr_t _mi_segment_page_idx_of(const mi_segment_t* segment, const void* p) {
280 // if (segment->page_size > MI_SEGMENT_SIZE) return &segment->pages[0]; // huge pages
281 ptrdiff_t diff = (uint8_t*)p - (uint8_t*)segment;
282 mi_assert_internal(diff >= 0 && diff < MI_SEGMENT_SIZE);
283 uintptr_t idx = (uintptr_t)diff >> segment->page_shift;
284 mi_assert_internal(idx < segment->capacity);
285 mi_assert_internal(segment->page_kind <= MI_PAGE_MEDIUM || idx == 0);
286 return idx;
287}
288
289// Get the page containing the pointer
290static inline mi_page_t* _mi_segment_page_of(const mi_segment_t* segment, const void* p) {
291 uintptr_t idx = _mi_segment_page_idx_of(segment, p);
292 return &((mi_segment_t*)segment)->pages[idx];
293}
294
295// Quick page start for initialized pages
296static inline uint8_t* _mi_page_start(const mi_segment_t* segment, const mi_page_t* page, size_t* page_size) {
297 return _mi_segment_page_start(segment, page, page->block_size, page_size);
298}
299
300// Get the page containing the pointer
301static inline mi_page_t* _mi_ptr_page(void* p) {
302 return _mi_segment_page_of(_mi_ptr_segment(p), p);
303}
304
305// Thread free access
306static inline mi_block_t* mi_tf_block(mi_thread_free_t tf) {
307 return (mi_block_t*)(tf & ~0x03);
308}
309static inline mi_delayed_t mi_tf_delayed(mi_thread_free_t tf) {
310 return (mi_delayed_t)(tf & 0x03);
311}
312static inline mi_thread_free_t mi_tf_make(mi_block_t* block, mi_delayed_t delayed) {
313 return (mi_thread_free_t)((uintptr_t)block | (uintptr_t)delayed);
314}
315static inline mi_thread_free_t mi_tf_set_delayed(mi_thread_free_t tf, mi_delayed_t delayed) {
316 return mi_tf_make(mi_tf_block(tf),delayed);
317}
318static inline mi_thread_free_t mi_tf_set_block(mi_thread_free_t tf, mi_block_t* block) {
319 return mi_tf_make(block, mi_tf_delayed(tf));
320}
321
322// are all blocks in a page freed?
323static inline bool mi_page_all_free(const mi_page_t* page) {
324 mi_assert_internal(page != NULL);
325 return (page->used - page->thread_freed == 0);
326}
327
328// are there immediately available blocks
329static inline bool mi_page_immediate_available(const mi_page_t* page) {
330 mi_assert_internal(page != NULL);
331 return (page->free != NULL);
332}
333// are there free blocks in this page?
334static inline bool mi_page_has_free(mi_page_t* page) {
335 mi_assert_internal(page != NULL);
336 bool hasfree = (mi_page_immediate_available(page) || page->local_free != NULL || (mi_tf_block(page->thread_free) != NULL));
337 mi_assert_internal(hasfree || page->used - page->thread_freed == page->capacity);
338 return hasfree;
339}
340
341// are all blocks in use?
342static inline bool mi_page_all_used(mi_page_t* page) {
343 mi_assert_internal(page != NULL);
344 return !mi_page_has_free(page);
345}
346
347// is more than 7/8th of a page in use?
348static inline bool mi_page_mostly_used(const mi_page_t* page) {
349 if (page==NULL) return true;
350 uint16_t frac = page->reserved / 8U;
351 return (page->reserved - page->used + page->thread_freed <= frac);
352}
353
354static inline mi_page_queue_t* mi_page_queue(const mi_heap_t* heap, size_t size) {
355 return &((mi_heap_t*)heap)->pages[_mi_bin(size)];
356}
357
358
359
360//-----------------------------------------------------------
361// Page flags
362//-----------------------------------------------------------
363static inline bool mi_page_is_in_full(const mi_page_t* page) {
364 return page->flags.x.in_full;
365}
366
367static inline void mi_page_set_in_full(mi_page_t* page, bool in_full) {
368 page->flags.x.in_full = in_full;
369}
370
371static inline bool mi_page_has_aligned(const mi_page_t* page) {
372 return page->flags.x.has_aligned;
373}
374
375static inline void mi_page_set_has_aligned(mi_page_t* page, bool has_aligned) {
376 page->flags.x.has_aligned = has_aligned;
377}
378
379
380// -------------------------------------------------------------------
381// Encoding/Decoding the free list next pointers
382// Note: we pass a `null` value to be used as the `NULL` value for the
383// end of a free list. This is to prevent the cookie itself to ever
384// be present among user blocks (as `cookie^0==cookie`).
385// -------------------------------------------------------------------
386
387static inline bool mi_is_in_same_segment(const void* p, const void* q) {
388 return (_mi_ptr_segment(p) == _mi_ptr_segment(q));
389}
390
391static inline bool mi_is_in_same_page(const void* p, const void* q) {
392 mi_segment_t* segmentp = _mi_ptr_segment(p);
393 mi_segment_t* segmentq = _mi_ptr_segment(q);
394 if (segmentp != segmentq) return false;
395 uintptr_t idxp = _mi_segment_page_idx_of(segmentp, p);
396 uintptr_t idxq = _mi_segment_page_idx_of(segmentq, q);
397 return (idxp == idxq);
398}
399
400static inline mi_block_t* mi_block_nextx( const void* null, const mi_block_t* block, uintptr_t cookie ) {
401 #ifdef MI_ENCODE_FREELIST
402 mi_block_t* b = (mi_block_t*)(block->next ^ cookie);
403 if (mi_unlikely((void*)b==null)) { b = NULL; }
404 return b;
405 #else
406 UNUSED(cookie); UNUSED(null);
407 return (mi_block_t*)block->next;
408 #endif
409}
410
411static inline void mi_block_set_nextx(const void* null, mi_block_t* block, const mi_block_t* next, uintptr_t cookie) {
412 #ifdef MI_ENCODE_FREELIST
413 if (mi_unlikely(next==NULL)) { next = (mi_block_t*)null; }
414 block->next = (mi_encoded_t)next ^ cookie;
415 #else
416 UNUSED(cookie); UNUSED(null);
417 block->next = (mi_encoded_t)next;
418 #endif
419}
420
421static inline mi_block_t* mi_block_next(const mi_page_t* page, const mi_block_t* block) {
422 #ifdef MI_ENCODE_FREELIST
423 mi_block_t* next = mi_block_nextx(page,block,page->cookie);
424 // check for free list corruption: is `next` at least in our segment range?
425 // TODO: check if `next` is `page->block_size` aligned?
426 if (next!=NULL && !mi_is_in_same_page(block, next)) {
427 _mi_fatal_error("corrupted free list entry of size %zub at %p: value 0x%zx\n", page->block_size, block, (uintptr_t)next);
428 next = NULL;
429 }
430 return next;
431 #else
432 UNUSED(page);
433 return mi_block_nextx(page,block,0);
434 #endif
435}
436
437static inline void mi_block_set_next(const mi_page_t* page, mi_block_t* block, const mi_block_t* next) {
438 #ifdef MI_ENCODE_FREELIST
439 mi_block_set_nextx(page,block,next, page->cookie);
440 #else
441 UNUSED(page);
442 mi_block_set_nextx(page,block, next,0);
443 #endif
444}
445
446// -------------------------------------------------------------------
447// Getting the thread id should be performant
448// as it is called in the fast path of `_mi_free`,
449// so we specialize for various platforms.
450// -------------------------------------------------------------------
451#if defined(_WIN32)
452#define WIN32_LEAN_AND_MEAN
453#include <windows.h>
454static inline uintptr_t _mi_thread_id(void) mi_attr_noexcept {
455 // Windows: works on Intel and ARM in both 32- and 64-bit
456 return (uintptr_t)NtCurrentTeb();
457}
458#elif (defined(__GNUC__) || defined(__clang__)) && \
459 (defined(__x86_64__) || defined(__i386__) || defined(__arm__) || defined(__aarch64__))
460// TLS register on x86 is in the FS or GS register
461// see: https://akkadia.org/drepper/tls.pdf
462static inline uintptr_t _mi_thread_id(void) mi_attr_noexcept {
463 uintptr_t tid;
464 #if defined(__i386__)
465 __asm__("movl %%gs:0, %0" : "=r" (tid) : : ); // 32-bit always uses GS
466 #elif defined(__MACH__)
467 __asm__("movq %%gs:0, %0" : "=r" (tid) : : ); // x86_64 macOS uses GS
468 #elif defined(__x86_64__)
469 __asm__("movq %%fs:0, %0" : "=r" (tid) : : ); // x86_64 Linux, BSD uses FS
470 #elif defined(__arm__)
471 asm volatile ("mrc p15, 0, %0, c13, c0, 3" : "=r" (tid));
472 #elif defined(__aarch64__)
473 asm volatile ("mrs %0, tpidr_el0" : "=r" (tid));
474 #endif
475 return tid;
476}
477#else
478// otherwise use standard C
479static inline uintptr_t _mi_thread_id(void) mi_attr_noexcept {
480 return (uintptr_t)&_mi_heap_default;
481}
482#endif
483
484
485#endif
486