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#include "mimalloc.h"
8#include "mimalloc-internal.h"
9
10#include <string.h> // memcpy, memset
11#include <stdlib.h> // atexit
12
13// Empty page used to initialize the small free pages array
14const mi_page_t _mi_page_empty = {
15 0, false, false, false, false, 0, 0,
16 { 0 }, false,
17 NULL, // free
18 #if MI_ENCODE_FREELIST
19 0,
20 #endif
21 0, // used
22 NULL,
23 ATOMIC_VAR_INIT(0), ATOMIC_VAR_INIT(0),
24 0, NULL, NULL, NULL
25 #if (MI_INTPTR_SIZE==8 && defined(MI_ENCODE_FREELIST)) || (MI_INTPTR_SIZE==4 && !defined(MI_ENCODE_FREELIST))
26 , { NULL } // padding
27 #endif
28};
29
30#define MI_PAGE_EMPTY() ((mi_page_t*)&_mi_page_empty)
31#define MI_SMALL_PAGES_EMPTY \
32 { MI_INIT128(MI_PAGE_EMPTY), MI_PAGE_EMPTY(), MI_PAGE_EMPTY() }
33
34
35// Empty page queues for every bin
36#define QNULL(sz) { NULL, NULL, (sz)*sizeof(uintptr_t) }
37#define MI_PAGE_QUEUES_EMPTY \
38 { QNULL(1), \
39 QNULL( 1), QNULL( 2), QNULL( 3), QNULL( 4), QNULL( 5), QNULL( 6), QNULL( 7), QNULL( 8), /* 8 */ \
40 QNULL( 10), QNULL( 12), QNULL( 14), QNULL( 16), QNULL( 20), QNULL( 24), QNULL( 28), QNULL( 32), /* 16 */ \
41 QNULL( 40), QNULL( 48), QNULL( 56), QNULL( 64), QNULL( 80), QNULL( 96), QNULL( 112), QNULL( 128), /* 24 */ \
42 QNULL( 160), QNULL( 192), QNULL( 224), QNULL( 256), QNULL( 320), QNULL( 384), QNULL( 448), QNULL( 512), /* 32 */ \
43 QNULL( 640), QNULL( 768), QNULL( 896), QNULL( 1024), QNULL( 1280), QNULL( 1536), QNULL( 1792), QNULL( 2048), /* 40 */ \
44 QNULL( 2560), QNULL( 3072), QNULL( 3584), QNULL( 4096), QNULL( 5120), QNULL( 6144), QNULL( 7168), QNULL( 8192), /* 48 */ \
45 QNULL( 10240), QNULL( 12288), QNULL( 14336), QNULL( 16384), QNULL( 20480), QNULL( 24576), QNULL( 28672), QNULL( 32768), /* 56 */ \
46 QNULL( 40960), QNULL( 49152), QNULL( 57344), QNULL( 65536), QNULL( 81920), QNULL( 98304), QNULL(114688), QNULL(131072), /* 64 */ \
47 QNULL(163840), QNULL(196608), QNULL(229376), QNULL(262144), QNULL(327680), QNULL(393216), QNULL(458752), QNULL(524288), /* 72 */ \
48 QNULL(MI_LARGE_OBJ_WSIZE_MAX + 1 /* 655360, Huge queue */), \
49 QNULL(MI_LARGE_OBJ_WSIZE_MAX + 2) /* Full queue */ }
50
51#define MI_STAT_COUNT_NULL() {0,0,0,0}
52
53// Empty statistics
54#if MI_STAT>1
55#define MI_STAT_COUNT_END_NULL() , { MI_STAT_COUNT_NULL(), MI_INIT32(MI_STAT_COUNT_NULL) }
56#else
57#define MI_STAT_COUNT_END_NULL()
58#endif
59
60#define MI_STATS_NULL \
61 MI_STAT_COUNT_NULL(), MI_STAT_COUNT_NULL(), \
62 MI_STAT_COUNT_NULL(), MI_STAT_COUNT_NULL(), \
63 MI_STAT_COUNT_NULL(), MI_STAT_COUNT_NULL(), \
64 MI_STAT_COUNT_NULL(), MI_STAT_COUNT_NULL(), \
65 MI_STAT_COUNT_NULL(), MI_STAT_COUNT_NULL(), \
66 MI_STAT_COUNT_NULL(), MI_STAT_COUNT_NULL(), \
67 MI_STAT_COUNT_NULL(), \
68 { 0, 0 }, { 0, 0 }, { 0, 0 }, \
69 { 0, 0 }, { 0, 0 }, { 0, 0 }, { 0, 0 } \
70 MI_STAT_COUNT_END_NULL()
71
72// --------------------------------------------------------
73// Statically allocate an empty heap as the initial
74// thread local value for the default heap,
75// and statically allocate the backing heap for the main
76// thread so it can function without doing any allocation
77// itself (as accessing a thread local for the first time
78// may lead to allocation itself on some platforms)
79// --------------------------------------------------------
80
81const mi_heap_t _mi_heap_empty = {
82 NULL,
83 MI_SMALL_PAGES_EMPTY,
84 MI_PAGE_QUEUES_EMPTY,
85 ATOMIC_VAR_INIT(NULL),
86 0,
87 0,
88 0,
89 0,
90 false
91};
92
93// the thread-local default heap for allocation
94mi_decl_thread mi_heap_t* _mi_heap_default = (mi_heap_t*)&_mi_heap_empty;
95
96
97#define tld_main_stats ((mi_stats_t*)((uint8_t*)&tld_main + offsetof(mi_tld_t,stats)))
98
99static mi_tld_t tld_main = {
100 0, false,
101 &_mi_heap_main,
102 { { NULL, NULL }, {NULL ,NULL}, 0, 0, 0, 0, 0, 0, NULL, tld_main_stats }, // segments
103 { 0, tld_main_stats }, // os
104 { MI_STATS_NULL } // stats
105};
106
107mi_heap_t _mi_heap_main = {
108 &tld_main,
109 MI_SMALL_PAGES_EMPTY,
110 MI_PAGE_QUEUES_EMPTY,
111 NULL,
112 0, // thread id
113#if MI_INTPTR_SIZE==8 // the cookie of the main heap can be fixed (unlike page cookies that need to be secure!)
114 0xCDCDCDCDCDCDCDCDUL,
115#else
116 0xCDCDCDCDUL,
117#endif
118 0, // random
119 0, // page count
120 false // can reclaim
121};
122
123bool _mi_process_is_initialized = false; // set to `true` in `mi_process_init`.
124
125mi_stats_t _mi_stats_main = { MI_STATS_NULL };
126
127/* -----------------------------------------------------------
128 Initialization of random numbers
129----------------------------------------------------------- */
130
131#if defined(_WIN32)
132#include <windows.h>
133#elif defined(__APPLE__)
134#include <mach/mach_time.h>
135#else
136#include <time.h>
137#endif
138
139uintptr_t _mi_random_shuffle(uintptr_t x) {
140 #if (MI_INTPTR_SIZE==8)
141 // by Sebastiano Vigna, see: <http://xoshiro.di.unimi.it/splitmix64.c>
142 x ^= x >> 30;
143 x *= 0xbf58476d1ce4e5b9UL;
144 x ^= x >> 27;
145 x *= 0x94d049bb133111ebUL;
146 x ^= x >> 31;
147 #elif (MI_INTPTR_SIZE==4)
148 // by Chris Wellons, see: <https://nullprogram.com/blog/2018/07/31/>
149 x ^= x >> 16;
150 x *= 0x7feb352dUL;
151 x ^= x >> 15;
152 x *= 0x846ca68bUL;
153 x ^= x >> 16;
154 #endif
155 return x;
156}
157
158uintptr_t _mi_random_init(uintptr_t seed /* can be zero */) {
159#ifdef __wasi__ // no ASLR when using WebAssembly, and time granularity may be coarse
160 uintptr_t x;
161 arc4random_buf(&x, sizeof x);
162#else
163 // Hopefully, ASLR makes our function address random
164 uintptr_t x = (uintptr_t)((void*)&_mi_random_init);
165 x ^= seed;
166 // xor with high res time
167#if defined(_WIN32)
168 LARGE_INTEGER pcount;
169 QueryPerformanceCounter(&pcount);
170 x ^= (uintptr_t)(pcount.QuadPart);
171#elif defined(__APPLE__)
172 x ^= (uintptr_t)mach_absolute_time();
173#else
174 struct timespec time;
175 clock_gettime(CLOCK_MONOTONIC, &time);
176 x ^= (uintptr_t)time.tv_sec;
177 x ^= (uintptr_t)time.tv_nsec;
178#endif
179 // and do a few randomization steps
180 uintptr_t max = ((x ^ (x >> 17)) & 0x0F) + 1;
181 for (uintptr_t i = 0; i < max; i++) {
182 x = _mi_random_shuffle(x);
183 }
184#endif
185 return x;
186}
187
188/* -----------------------------------------------------------
189 Initialization and freeing of the thread local heaps
190----------------------------------------------------------- */
191
192typedef struct mi_thread_data_s {
193 mi_heap_t heap; // must come first due to cast in `_mi_heap_done`
194 mi_tld_t tld;
195} mi_thread_data_t;
196
197// Initialize the thread local default heap, called from `mi_thread_init`
198static bool _mi_heap_init(void) {
199 if (mi_heap_is_initialized(_mi_heap_default)) return true;
200 if (_mi_is_main_thread()) {
201 // the main heap is statically allocated
202 _mi_heap_set_default_direct(&_mi_heap_main);
203 mi_assert_internal(_mi_heap_default->tld->heap_backing == mi_get_default_heap());
204 }
205 else {
206 // use `_mi_os_alloc` to allocate directly from the OS
207 mi_thread_data_t* td = (mi_thread_data_t*)_mi_os_alloc(sizeof(mi_thread_data_t),&_mi_stats_main); // Todo: more efficient allocation?
208 if (td == NULL) {
209 _mi_error_message("failed to allocate thread local heap memory\n");
210 return false;
211 }
212 mi_tld_t* tld = &td->tld;
213 mi_heap_t* heap = &td->heap;
214 memcpy(heap, &_mi_heap_empty, sizeof(*heap));
215 heap->thread_id = _mi_thread_id();
216 heap->random = _mi_random_init(heap->thread_id);
217 heap->cookie = ((uintptr_t)heap ^ _mi_heap_random(heap)) | 1;
218 heap->tld = tld;
219 memset(tld, 0, sizeof(*tld));
220 tld->heap_backing = heap;
221 tld->segments.stats = &tld->stats;
222 tld->os.stats = &tld->stats;
223 _mi_heap_set_default_direct(heap);
224 }
225 return false;
226}
227
228// Free the thread local default heap (called from `mi_thread_done`)
229static bool _mi_heap_done(mi_heap_t* heap) {
230 if (!mi_heap_is_initialized(heap)) return true;
231
232 // reset default heap
233 _mi_heap_set_default_direct(_mi_is_main_thread() ? &_mi_heap_main : (mi_heap_t*)&_mi_heap_empty);
234
235 // todo: delete all non-backing heaps?
236
237 // switch to backing heap and free it
238 heap = heap->tld->heap_backing;
239 if (!mi_heap_is_initialized(heap)) return false;
240
241 // collect if not the main thread
242 if (heap != &_mi_heap_main) {
243 _mi_heap_collect_abandon(heap);
244 }
245
246 // merge stats
247 _mi_stats_done(&heap->tld->stats);
248
249 // free if not the main thread
250 if (heap != &_mi_heap_main) {
251 _mi_os_free(heap, sizeof(mi_thread_data_t), &_mi_stats_main);
252 }
253#if (MI_DEBUG > 0)
254 else {
255 _mi_heap_destroy_pages(heap);
256 mi_assert_internal(heap->tld->heap_backing == &_mi_heap_main);
257 }
258#endif
259 return false;
260}
261
262
263
264// --------------------------------------------------------
265// Try to run `mi_thread_done()` automatically so any memory
266// owned by the thread but not yet released can be abandoned
267// and re-owned by another thread.
268//
269// 1. windows dynamic library:
270// call from DllMain on DLL_THREAD_DETACH
271// 2. windows static library:
272// use `FlsAlloc` to call a destructor when the thread is done
273// 3. unix, pthreads:
274// use a pthread key to call a destructor when a pthread is done
275//
276// In the last two cases we also need to call `mi_process_init`
277// to set up the thread local keys.
278// --------------------------------------------------------
279
280static void _mi_thread_done(mi_heap_t* default_heap);
281
282#ifdef __wasi__
283// no pthreads in the WebAssembly Standard Interface
284#elif !defined(_WIN32)
285#define MI_USE_PTHREADS
286#endif
287
288#if defined(_WIN32) && defined(MI_SHARED_LIB)
289 // nothing to do as it is done in DllMain
290#elif defined(_WIN32) && !defined(MI_SHARED_LIB)
291 // use thread local storage keys to detect thread ending
292 #include <windows.h>
293 #include <fibersapi.h>
294 static DWORD mi_fls_key;
295 static void NTAPI mi_fls_done(PVOID value) {
296 if (value!=NULL) _mi_thread_done((mi_heap_t*)value);
297 }
298#elif defined(MI_USE_PTHREADS)
299 // use pthread locol storage keys to detect thread ending
300 #include <pthread.h>
301 static pthread_key_t mi_pthread_key;
302 static void mi_pthread_done(void* value) {
303 if (value!=NULL) _mi_thread_done((mi_heap_t*)value);
304 }
305#elif defined(__wasi__)
306// no pthreads in the WebAssembly Standard Interface
307#else
308 #pragma message("define a way to call mi_thread_done when a thread is done")
309#endif
310
311// Set up handlers so `mi_thread_done` is called automatically
312static void mi_process_setup_auto_thread_done(void) {
313 static bool tls_initialized = false; // fine if it races
314 if (tls_initialized) return;
315 tls_initialized = true;
316 #if defined(_WIN32) && defined(MI_SHARED_LIB)
317 // nothing to do as it is done in DllMain
318 #elif defined(_WIN32) && !defined(MI_SHARED_LIB)
319 mi_fls_key = FlsAlloc(&mi_fls_done);
320 #elif defined(MI_USE_PTHREADS)
321 pthread_key_create(&mi_pthread_key, &mi_pthread_done);
322 #endif
323}
324
325
326bool _mi_is_main_thread(void) {
327 return (_mi_heap_main.thread_id==0 || _mi_heap_main.thread_id == _mi_thread_id());
328}
329
330// This is called from the `mi_malloc_generic`
331void mi_thread_init(void) mi_attr_noexcept
332{
333 // ensure our process has started already
334 mi_process_init();
335
336 // initialize the thread local default heap
337 // (this will call `_mi_heap_set_default_direct` and thus set the
338 // fiber/pthread key to a non-zero value, ensuring `_mi_thread_done` is called)
339 if (_mi_heap_init()) return; // returns true if already initialized
340
341 // don't further initialize for the main thread
342 if (_mi_is_main_thread()) return;
343
344 _mi_stat_increase(&mi_get_default_heap()->tld->stats.threads, 1);
345
346 //_mi_verbose_message("thread init: 0x%zx\n", _mi_thread_id());
347}
348
349void mi_thread_done(void) mi_attr_noexcept {
350 _mi_thread_done(mi_get_default_heap());
351}
352
353static void _mi_thread_done(mi_heap_t* heap) {
354 // stats
355 if (!_mi_is_main_thread() && mi_heap_is_initialized(heap)) {
356 _mi_stat_decrease(&heap->tld->stats.threads, 1);
357 }
358 // abandon the thread local heap
359 if (_mi_heap_done(heap)) return; // returns true if already ran
360}
361
362void _mi_heap_set_default_direct(mi_heap_t* heap) {
363 mi_assert_internal(heap != NULL);
364 _mi_heap_default = heap;
365
366 // ensure the default heap is passed to `_mi_thread_done`
367 // setting to a non-NULL value also ensures `mi_thread_done` is called.
368 #if defined(_WIN32) && defined(MI_SHARED_LIB)
369 // nothing to do as it is done in DllMain
370 #elif defined(_WIN32) && !defined(MI_SHARED_LIB)
371 FlsSetValue(mi_fls_key, heap);
372 #elif defined(MI_USE_PTHREADS)
373 pthread_setspecific(mi_pthread_key, heap);
374 #endif
375}
376
377
378
379// --------------------------------------------------------
380// Run functions on process init/done, and thread init/done
381// --------------------------------------------------------
382static void mi_process_done(void);
383
384static bool os_preloading = true; // true until this module is initialized
385static bool mi_redirected = false; // true if malloc redirects to mi_malloc
386
387// Returns true if this module has not been initialized; Don't use C runtime routines until it returns false.
388bool _mi_preloading() {
389 return os_preloading;
390}
391
392bool mi_is_redirected() mi_attr_noexcept {
393 return mi_redirected;
394}
395
396// Communicate with the redirection module on Windows
397#if defined(_WIN32) && defined(MI_SHARED_LIB)
398#ifdef __cplusplus
399extern "C" {
400#endif
401mi_decl_export void _mi_redirect_entry(DWORD reason) {
402 // called on redirection; careful as this may be called before DllMain
403 if (reason == DLL_PROCESS_ATTACH) {
404 mi_redirected = true;
405 }
406 else if (reason == DLL_PROCESS_DETACH) {
407 mi_redirected = false;
408 }
409 else if (reason == DLL_THREAD_DETACH) {
410 mi_thread_done();
411 }
412}
413__declspec(dllimport) bool mi_allocator_init(const char** message);
414__declspec(dllimport) void mi_allocator_done();
415#ifdef __cplusplus
416}
417#endif
418#else
419static bool mi_allocator_init(const char** message) {
420 if (message != NULL) *message = NULL;
421 return true;
422}
423static void mi_allocator_done() {
424 // nothing to do
425}
426#endif
427
428// Called once by the process loader
429static void mi_process_load(void) {
430 os_preloading = false;
431 atexit(&mi_process_done);
432 _mi_options_init();
433 mi_process_init();
434 //mi_stats_reset();
435 if (mi_redirected) _mi_verbose_message("malloc is redirected.\n");
436
437 // show message from the redirector (if present)
438 const char* msg = NULL;
439 mi_allocator_init(&msg);
440 if (msg != NULL && (mi_option_is_enabled(mi_option_verbose) || mi_option_is_enabled(mi_option_show_errors))) {
441 _mi_fputs(NULL,NULL,msg);
442 }
443
444 if (mi_option_is_enabled(mi_option_reserve_huge_os_pages)) {
445 size_t pages = mi_option_get(mi_option_reserve_huge_os_pages);
446 double max_secs = (double)pages / 2.0; // 0.5s per page (1GiB)
447 mi_reserve_huge_os_pages(pages, max_secs, NULL);
448 }
449}
450
451// Initialize the process; called by thread_init or the process loader
452void mi_process_init(void) mi_attr_noexcept {
453 // ensure we are called once
454 if (_mi_process_is_initialized) return;
455 // access _mi_heap_default before setting _mi_process_is_initialized to ensure
456 // that the TLS slot is allocated without getting into recursion on macOS
457 // when using dynamic linking with interpose.
458 mi_heap_t* h = mi_get_default_heap();
459 _mi_process_is_initialized = true;
460
461 _mi_heap_main.thread_id = _mi_thread_id();
462 _mi_verbose_message("process init: 0x%zx\n", _mi_heap_main.thread_id);
463 uintptr_t random = _mi_random_init(_mi_heap_main.thread_id) ^ (uintptr_t)h;
464 #ifndef __APPLE__
465 _mi_heap_main.cookie = (uintptr_t)&_mi_heap_main ^ random;
466 #endif
467 _mi_heap_main.random = _mi_random_shuffle(random);
468 mi_process_setup_auto_thread_done();
469 _mi_os_init();
470 #if (MI_DEBUG)
471 _mi_verbose_message("debug level : %d\n", MI_DEBUG);
472 #endif
473 _mi_verbose_message("secure level: %d\n", MI_SECURE);
474 mi_thread_init();
475 mi_stats_reset(); // only call stat reset *after* thread init (or the heap tld == NULL)
476}
477
478// Called when the process is done (through `at_exit`)
479static void mi_process_done(void) {
480 // only shutdown if we were initialized
481 if (!_mi_process_is_initialized) return;
482 // ensure we are called once
483 static bool process_done = false;
484 if (process_done) return;
485 process_done = true;
486
487 #ifndef NDEBUG
488 mi_collect(true);
489 #endif
490 if (mi_option_is_enabled(mi_option_show_stats) ||
491 mi_option_is_enabled(mi_option_verbose)) {
492 mi_stats_print(NULL);
493 }
494 mi_allocator_done();
495 _mi_verbose_message("process done: 0x%zx\n", _mi_heap_main.thread_id);
496 os_preloading = true; // don't call the C runtime anymore
497}
498
499
500
501#if defined(_WIN32) && defined(MI_SHARED_LIB)
502 // Windows DLL: easy to hook into process_init and thread_done
503 __declspec(dllexport) BOOL WINAPI DllMain(HINSTANCE inst, DWORD reason, LPVOID reserved) {
504 UNUSED(reserved);
505 UNUSED(inst);
506 if (reason==DLL_PROCESS_ATTACH) {
507 mi_process_load();
508 }
509 else if (reason==DLL_THREAD_DETACH) {
510 if (!mi_is_redirected()) mi_thread_done();
511 }
512 return TRUE;
513 }
514
515#elif defined(__cplusplus)
516 // C++: use static initialization to detect process start
517 static bool _mi_process_init(void) {
518 mi_process_load();
519 return (_mi_heap_main.thread_id != 0);
520 }
521 static bool mi_initialized = _mi_process_init();
522
523#elif defined(__GNUC__) || defined(__clang__)
524 // GCC,Clang: use the constructor attribute
525 static void __attribute__((constructor)) _mi_process_init(void) {
526 mi_process_load();
527 }
528
529#elif defined(_MSC_VER)
530 // MSVC: use data section magic for static libraries
531 // See <https://www.codeguru.com/cpp/misc/misc/applicationcontrol/article.php/c6945/Running-Code-Before-and-After-Main.htm>
532 static int _mi_process_init(void) {
533 mi_process_load();
534 return 0;
535 }
536 typedef int(*_crt_cb)(void);
537 #ifdef _M_X64
538 __pragma(comment(linker, "/include:" "_mi_msvc_initu"))
539 #pragma section(".CRT$XIU", long, read)
540 #else
541 __pragma(comment(linker, "/include:" "__mi_msvc_initu"))
542 #endif
543 #pragma data_seg(".CRT$XIU")
544 _crt_cb _mi_msvc_initu[] = { &_mi_process_init };
545 #pragma data_seg()
546
547#else
548#pragma message("define a way to call mi_process_load on your platform")
549#endif
550