| 1 |
/*---------------------------------------------------------------------------- |
| 2 |
Copyright (c) 2018-2021, 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 |
|
| 8 |
#include "mimalloc.h" |
| 9 |
#include "mimalloc/internal.h" |
| 10 |
#include "mimalloc/atomic.h" |
| 11 |
#include "mimalloc/prim.h" // mi_prim_get_default_heap |
| 12 |
|
| 13 |
#include <string.h> // memset, memcpy |
| 14 |
|
| 15 |
#if defined(_MSC_VER) && (_MSC_VER < 1920) |
| 16 |
#pragma warning(disable:4204) // non-constant aggregate initializer |
| 17 |
#endif |
| 18 |
|
| 19 |
/* ----------------------------------------------------------- |
| 20 |
Helpers |
| 21 |
----------------------------------------------------------- */ |
| 22 |
|
| 23 |
// return `true` if ok, `false` to break |
| 24 |
typedef bool (heap_page_visitor_fun)(mi_heap_t* heap, mi_page_queue_t* pq, mi_page_t* page, void* arg1, void* arg2); |
| 25 |
|
| 26 |
// Visit all pages in a heap; returns `false` if break was called. |
| 27 |
static bool mi_heap_visit_pages(mi_heap_t* heap, heap_page_visitor_fun* fn, void* arg1, void* arg2) |
| 28 |
{ |
| 29 |
if (heap==NULL || heap->page_count==0) return true; |
| 30 |
|
| 31 |
// visit all pages |
| 32 |
#if MI_DEBUG>1 |
| 33 |
size_t total = heap->page_count; |
| 34 |
size_t count = 0; |
| 35 |
#endif |
| 36 |
|
| 37 |
for (size_t i = 0; i <= MI_BIN_FULL; i++) { |
| 38 |
mi_page_queue_t* pq = &heap->pages[i]; |
| 39 |
mi_page_t* page = pq->first; |
| 40 |
while(page != NULL) { |
| 41 |
mi_page_t* next = page->next; // save next in case the page gets removed from the queue |
| 42 |
mi_assert_internal(mi_page_heap(page) == heap); |
| 43 |
#if MI_DEBUG>1 |
| 44 |
count++; |
| 45 |
#endif |
| 46 |
if (!fn(heap, pq, page, arg1, arg2)) return false; |
| 47 |
page = next; // and continue |
| 48 |
} |
| 49 |
} |
| 50 |
mi_assert_internal(count == total); |
| 51 |
return true; |
| 52 |
} |
| 53 |
|
| 54 |
|
| 55 |
#if MI_DEBUG>=2 |
| 56 |
static bool mi_heap_page_is_valid(mi_heap_t* heap, mi_page_queue_t* pq, mi_page_t* page, void* arg1, void* arg2) { |
| 57 |
MI_UNUSED(arg1); |
| 58 |
MI_UNUSED(arg2); |
| 59 |
MI_UNUSED(pq); |
| 60 |
mi_assert_internal(mi_page_heap(page) == heap); |
| 61 |
mi_segment_t* segment = _mi_page_segment(page); |
| 62 |
mi_assert_internal(segment->thread_id == heap->thread_id); |
| 63 |
mi_assert_expensive(_mi_page_is_valid(page)); |
| 64 |
return true; |
| 65 |
} |
| 66 |
#endif |
| 67 |
#if MI_DEBUG>=3 |
| 68 |
static bool mi_heap_is_valid(mi_heap_t* heap) { |
| 69 |
mi_assert_internal(heap!=NULL); |
| 70 |
mi_heap_visit_pages(heap, &mi_heap_page_is_valid, NULL, NULL); |
| 71 |
return true; |
| 72 |
} |
| 73 |
#endif |
| 74 |
|
| 75 |
|
| 76 |
|
| 77 |
|
| 78 |
/* ----------------------------------------------------------- |
| 79 |
"Collect" pages by migrating `local_free` and `thread_free` |
| 80 |
lists and freeing empty pages. This is done when a thread |
| 81 |
stops (and in that case abandons pages if there are still |
| 82 |
blocks alive) |
| 83 |
----------------------------------------------------------- */ |
| 84 |
|
| 85 |
typedef enum mi_collect_e { |
| 86 |
MI_NORMAL, |
| 87 |
MI_FORCE, |
| 88 |
MI_ABANDON |
| 89 |
} mi_collect_t; |
| 90 |
|
| 91 |
|
| 92 |
static bool mi_heap_page_collect(mi_heap_t* heap, mi_page_queue_t* pq, mi_page_t* page, void* arg_collect, void* arg2 ) { |
| 93 |
MI_UNUSED(arg2); |
| 94 |
MI_UNUSED(heap); |
| 95 |
mi_assert_internal(mi_heap_page_is_valid(heap, pq, page, NULL, NULL)); |
| 96 |
mi_collect_t collect = *((mi_collect_t*)arg_collect); |
| 97 |
_mi_page_free_collect(page, collect >= MI_FORCE); |
| 98 |
if (mi_page_all_free(page)) { |
| 99 |
// no more used blocks, free the page. |
| 100 |
// note: this will free retired pages as well. |
| 101 |
bool freed = _PyMem_mi_page_maybe_free(page, pq, collect >= MI_FORCE); |
| 102 |
if (!freed && collect == MI_ABANDON) { |
| 103 |
// _PyMem_mi_page_maybe_free may have moved the page to a different |
| 104 |
// page queue, so we need to re-fetch the correct queue. |
| 105 |
uint8_t bin = (mi_page_is_in_full(page) ? MI_BIN_FULL : _mi_bin(page->xblock_size)); |
| 106 |
_mi_page_abandon(page, &heap->pages[bin]); |
| 107 |
} |
| 108 |
} |
| 109 |
else if (collect == MI_ABANDON) { |
| 110 |
// still used blocks but the thread is done; abandon the page |
| 111 |
_mi_page_abandon(page, pq); |
| 112 |
} |
| 113 |
return true; // don't break |
| 114 |
} |
| 115 |
|
| 116 |
static bool mi_heap_page_never_delayed_free(mi_heap_t* heap, mi_page_queue_t* pq, mi_page_t* page, void* arg1, void* arg2) { |
| 117 |
MI_UNUSED(arg1); |
| 118 |
MI_UNUSED(arg2); |
| 119 |
MI_UNUSED(heap); |
| 120 |
MI_UNUSED(pq); |
| 121 |
_mi_page_use_delayed_free(page, MI_NEVER_DELAYED_FREE, false); |
| 122 |
return true; // don't break |
| 123 |
} |
| 124 |
|
| 125 |
static void mi_heap_collect_ex(mi_heap_t* heap, mi_collect_t collect) |
| 126 |
{ |
| 127 |
if (heap==NULL || !mi_heap_is_initialized(heap)) return; |
| 128 |
|
| 129 |
const bool force = collect >= MI_FORCE; |
| 130 |
_mi_deferred_free(heap, force); |
| 131 |
|
| 132 |
// gh-112532: we may be called from a thread that is not the owner of the heap |
| 133 |
bool is_main_thread = _mi_is_main_thread() && heap->thread_id == _mi_thread_id(); |
| 134 |
|
| 135 |
// note: never reclaim on collect but leave it to threads that need storage to reclaim |
| 136 |
const bool force_main = |
| 137 |
#ifdef NDEBUG |
| 138 |
collect == MI_FORCE |
| 139 |
#else |
| 140 |
collect >= MI_FORCE |
| 141 |
#endif |
| 142 |
&& is_main_thread && mi_heap_is_backing(heap) && !heap->no_reclaim; |
| 143 |
|
| 144 |
if (force_main) { |
| 145 |
// the main thread is abandoned (end-of-program), try to reclaim all abandoned segments. |
| 146 |
// if all memory is freed by now, all segments should be freed. |
| 147 |
_mi_abandoned_reclaim_all(heap, &heap->tld->segments); |
| 148 |
} |
| 149 |
|
| 150 |
// if abandoning, mark all pages to no longer add to delayed_free |
| 151 |
if (collect == MI_ABANDON) { |
| 152 |
mi_heap_visit_pages(heap, &mi_heap_page_never_delayed_free, NULL, NULL); |
| 153 |
} |
| 154 |
|
| 155 |
// free all current thread delayed blocks. |
| 156 |
// (if abandoning, after this there are no more thread-delayed references into the pages.) |
| 157 |
_mi_heap_delayed_free_all(heap); |
| 158 |
|
| 159 |
// collect retired pages |
| 160 |
_mi_heap_collect_retired(heap, force); |
| 161 |
|
| 162 |
// free pages that were delayed with QSBR |
| 163 |
_PyMem_mi_heap_collect_qsbr(heap); |
| 164 |
|
| 165 |
// collect all pages owned by this thread |
| 166 |
mi_heap_visit_pages(heap, &mi_heap_page_collect, &collect, NULL); |
| 167 |
mi_assert_internal( collect != MI_ABANDON || mi_atomic_load_ptr_acquire(mi_block_t,&heap->thread_delayed_free) == NULL ); |
| 168 |
|
| 169 |
// collect abandoned segments (in particular, purge expired parts of segments in the abandoned segment list) |
| 170 |
// note: forced purge can be quite expensive if many threads are created/destroyed so we do not force on abandonment |
| 171 |
_mi_abandoned_collect(heap, collect == MI_FORCE /* force? */, &heap->tld->segments); |
| 172 |
|
| 173 |
// collect segment local caches |
| 174 |
if (force) { |
| 175 |
_mi_segment_thread_collect(&heap->tld->segments); |
| 176 |
} |
| 177 |
|
| 178 |
// collect regions on program-exit (or shared library unload) |
| 179 |
if (force && is_main_thread && mi_heap_is_backing(heap)) { |
| 180 |
_mi_thread_data_collect(); // collect thread data cache |
| 181 |
_mi_arena_collect(true /* force purge */, &heap->tld->stats); |
| 182 |
} |
| 183 |
} |
| 184 |
|
| 185 |
void _mi_heap_collect_abandon(mi_heap_t* heap) { |
| 186 |
mi_heap_collect_ex(heap, MI_ABANDON); |
| 187 |
} |
| 188 |
|
| 189 |
void mi_heap_collect(mi_heap_t* heap, bool force) mi_attr_noexcept { |
| 190 |
mi_heap_collect_ex(heap, (force ? MI_FORCE : MI_NORMAL)); |
| 191 |
} |
| 192 |
|
| 193 |
void mi_collect(bool force) mi_attr_noexcept { |
| 194 |
mi_heap_collect(mi_prim_get_default_heap(), force); |
| 195 |
} |
| 196 |
|
| 197 |
|
| 198 |
/* ----------------------------------------------------------- |
| 199 |
Heap new |
| 200 |
----------------------------------------------------------- */ |
| 201 |
|
| 202 |
mi_heap_t* mi_heap_get_default(void) { |
| 203 |
mi_thread_init(); |
| 204 |
return mi_prim_get_default_heap(); |
| 205 |
} |
| 206 |
|
| 207 |
static bool mi_heap_is_default(const mi_heap_t* heap) { |
| 208 |
return (heap == mi_prim_get_default_heap()); |
| 209 |
} |
| 210 |
|
| 211 |
|
| 212 |
mi_heap_t* mi_heap_get_backing(void) { |
| 213 |
mi_heap_t* heap = mi_heap_get_default(); |
| 214 |
mi_assert_internal(heap!=NULL); |
| 215 |
mi_heap_t* bheap = heap->tld->heap_backing; |
| 216 |
mi_assert_internal(bheap!=NULL); |
| 217 |
mi_assert_internal(bheap->thread_id == _mi_thread_id()); |
| 218 |
return bheap; |
| 219 |
} |
| 220 |
|
| 221 |
void _mi_heap_init_ex(mi_heap_t* heap, mi_tld_t* tld, mi_arena_id_t arena_id, bool no_reclaim, uint8_t tag) |
| 222 |
{ |
| 223 |
_mi_memcpy_aligned(heap, &_mi_heap_empty, sizeof(mi_heap_t)); |
| 224 |
heap->tld = tld; |
| 225 |
heap->thread_id = _mi_thread_id(); |
| 226 |
heap->arena_id = arena_id; |
| 227 |
if (heap == tld->heap_backing) { |
| 228 |
_mi_random_init(&heap->random); |
| 229 |
} |
| 230 |
else { |
| 231 |
_mi_random_split(&tld->heap_backing->random, &heap->random); |
| 232 |
} |
| 233 |
heap->cookie = _mi_heap_random_next(heap) | 1; |
| 234 |
heap->keys[0] = _mi_heap_random_next(heap); |
| 235 |
heap->keys[1] = _mi_heap_random_next(heap); |
| 236 |
heap->no_reclaim = no_reclaim; |
| 237 |
heap->tag = tag; |
| 238 |
// push on the thread local heaps list |
| 239 |
heap->next = heap->tld->heaps; |
| 240 |
heap->tld->heaps = heap; |
| 241 |
} |
| 242 |
|
| 243 |
mi_decl_nodiscard mi_heap_t* mi_heap_new_in_arena(mi_arena_id_t arena_id) { |
| 244 |
mi_heap_t* bheap = mi_heap_get_backing(); |
| 245 |
mi_heap_t* heap = mi_heap_malloc_tp(bheap, mi_heap_t); // todo: OS allocate in secure mode? |
| 246 |
if (heap == NULL) return NULL; |
| 247 |
// don't reclaim abandoned pages or otherwise destroy is unsafe |
| 248 |
_mi_heap_init_ex(heap, bheap->tld, arena_id, true, 0); |
| 249 |
return heap; |
| 250 |
} |
| 251 |
|
| 252 |
mi_decl_nodiscard mi_heap_t* mi_heap_new(void) { |
| 253 |
return mi_heap_new_in_arena(_mi_arena_id_none()); |
| 254 |
} |
| 255 |
|
| 256 |
bool _mi_heap_memid_is_suitable(mi_heap_t* heap, mi_memid_t memid) { |
| 257 |
return _mi_arena_memid_is_suitable(memid, heap->arena_id); |
| 258 |
} |
| 259 |
|
| 260 |
uintptr_t _mi_heap_random_next(mi_heap_t* heap) { |
| 261 |
return _mi_random_next(&heap->random); |
| 262 |
} |
| 263 |
|
| 264 |
// zero out the page queues |
| 265 |
static void mi_heap_reset_pages(mi_heap_t* heap) { |
| 266 |
mi_assert_internal(heap != NULL); |
| 267 |
mi_assert_internal(mi_heap_is_initialized(heap)); |
| 268 |
// TODO: copy full empty heap instead? |
| 269 |
memset(&heap->pages_free_direct, 0, sizeof(heap->pages_free_direct)); |
| 270 |
_mi_memcpy_aligned(&heap->pages, &_mi_heap_empty.pages, sizeof(heap->pages)); |
| 271 |
heap->thread_delayed_free = NULL; |
| 272 |
heap->page_count = 0; |
| 273 |
} |
| 274 |
|
| 275 |
// called from `mi_heap_destroy` and `mi_heap_delete` to free the internal heap resources. |
| 276 |
static void mi_heap_free(mi_heap_t* heap) { |
| 277 |
mi_assert(heap != NULL); |
| 278 |
mi_assert_internal(mi_heap_is_initialized(heap)); |
| 279 |
if (heap==NULL || !mi_heap_is_initialized(heap)) return; |
| 280 |
if (mi_heap_is_backing(heap)) return; // dont free the backing heap |
| 281 |
|
| 282 |
// reset default |
| 283 |
if (mi_heap_is_default(heap)) { |
| 284 |
_mi_heap_set_default_direct(heap->tld->heap_backing); |
| 285 |
} |
| 286 |
|
| 287 |
// remove ourselves from the thread local heaps list |
| 288 |
// linear search but we expect the number of heaps to be relatively small |
| 289 |
mi_heap_t* prev = NULL; |
| 290 |
mi_heap_t* curr = heap->tld->heaps; |
| 291 |
while (curr != heap && curr != NULL) { |
| 292 |
prev = curr; |
| 293 |
curr = curr->next; |
| 294 |
} |
| 295 |
mi_assert_internal(curr == heap); |
| 296 |
if (curr == heap) { |
| 297 |
if (prev != NULL) { prev->next = heap->next; } |
| 298 |
else { heap->tld->heaps = heap->next; } |
| 299 |
} |
| 300 |
mi_assert_internal(heap->tld->heaps != NULL); |
| 301 |
|
| 302 |
// and free the used memory |
| 303 |
mi_free(heap); |
| 304 |
} |
| 305 |
|
| 306 |
|
| 307 |
/* ----------------------------------------------------------- |
| 308 |
Heap destroy |
| 309 |
----------------------------------------------------------- */ |
| 310 |
|
| 311 |
static bool _mi_heap_page_destroy(mi_heap_t* heap, mi_page_queue_t* pq, mi_page_t* page, void* arg1, void* arg2) { |
| 312 |
MI_UNUSED(arg1); |
| 313 |
MI_UNUSED(arg2); |
| 314 |
MI_UNUSED(heap); |
| 315 |
MI_UNUSED(pq); |
| 316 |
|
| 317 |
// ensure no more thread_delayed_free will be added |
| 318 |
_mi_page_use_delayed_free(page, MI_NEVER_DELAYED_FREE, false); |
| 319 |
|
| 320 |
// stats |
| 321 |
const size_t bsize = mi_page_block_size(page); |
| 322 |
if (bsize > MI_MEDIUM_OBJ_SIZE_MAX) { |
| 323 |
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 |
#if (MI_STAT) |
| 331 |
_mi_page_free_collect(page, false); // update used count |
| 332 |
const size_t inuse = page->used; |
| 333 |
if (bsize <= MI_LARGE_OBJ_SIZE_MAX) { |
| 334 |
mi_heap_stat_decrease(heap, normal, bsize * inuse); |
| 335 |
#if (MI_STAT>1) |
| 336 |
mi_heap_stat_decrease(heap, normal_bins[_mi_bin(bsize)], inuse); |
| 337 |
#endif |
| 338 |
} |
| 339 |
mi_heap_stat_decrease(heap, malloc, bsize * inuse); // todo: off for aligned blocks... |
| 340 |
#endif |
| 341 |
|
| 342 |
/// pretend it is all free now |
| 343 |
mi_assert_internal(mi_page_thread_free(page) == NULL); |
| 344 |
page->used = 0; |
| 345 |
|
| 346 |
// and free the page |
| 347 |
// mi_page_free(page,false); |
| 348 |
page->next = NULL; |
| 349 |
page->prev = NULL; |
| 350 |
_mi_segment_page_free(page,false /* no force? */, &heap->tld->segments); |
| 351 |
|
| 352 |
return true; // keep going |
| 353 |
} |
| 354 |
|
| 355 |
void _mi_heap_destroy_pages(mi_heap_t* heap) { |
| 356 |
mi_heap_visit_pages(heap, &_mi_heap_page_destroy, NULL, NULL); |
| 357 |
mi_heap_reset_pages(heap); |
| 358 |
} |
| 359 |
|
| 360 |
#if MI_TRACK_HEAP_DESTROY |
| 361 |
static bool mi_cdecl mi_heap_track_block_free(const mi_heap_t* heap, const mi_heap_area_t* area, void* block, size_t block_size, void* arg) { |
| 362 |
MI_UNUSED(heap); MI_UNUSED(area); MI_UNUSED(arg); MI_UNUSED(block_size); |
| 363 |
mi_track_free_size(block,mi_usable_size(block)); |
| 364 |
return true; |
| 365 |
} |
| 366 |
#endif |
| 367 |
|
| 368 |
void mi_heap_destroy(mi_heap_t* heap) { |
| 369 |
mi_assert(heap != NULL); |
| 370 |
mi_assert(mi_heap_is_initialized(heap)); |
| 371 |
mi_assert(heap->no_reclaim); |
| 372 |
mi_assert_expensive(mi_heap_is_valid(heap)); |
| 373 |
if (heap==NULL || !mi_heap_is_initialized(heap)) return; |
| 374 |
if (!heap->no_reclaim) { |
| 375 |
// don't free in case it may contain reclaimed pages |
| 376 |
mi_heap_delete(heap); |
| 377 |
} |
| 378 |
else { |
| 379 |
// track all blocks as freed |
| 380 |
#if MI_TRACK_HEAP_DESTROY |
| 381 |
mi_heap_visit_blocks(heap, true, mi_heap_track_block_free, NULL); |
| 382 |
#endif |
| 383 |
// free all pages |
| 384 |
_mi_heap_destroy_pages(heap); |
| 385 |
mi_heap_free(heap); |
| 386 |
} |
| 387 |
} |
| 388 |
|
| 389 |
// forcefully destroy all heaps in the current thread |
| 390 |
void _mi_heap_unsafe_destroy_all(void) { |
| 391 |
mi_heap_t* bheap = mi_heap_get_backing(); |
| 392 |
mi_heap_t* curr = bheap->tld->heaps; |
| 393 |
while (curr != NULL) { |
| 394 |
mi_heap_t* next = curr->next; |
| 395 |
if (curr->no_reclaim) { |
| 396 |
mi_heap_destroy(curr); |
| 397 |
} |
| 398 |
else { |
| 399 |
_mi_heap_destroy_pages(curr); |
| 400 |
} |
| 401 |
curr = next; |
| 402 |
} |
| 403 |
} |
| 404 |
|
| 405 |
/* ----------------------------------------------------------- |
| 406 |
Safe Heap delete |
| 407 |
----------------------------------------------------------- */ |
| 408 |
|
| 409 |
// Transfer the pages from one heap to the other |
| 410 |
static void mi_heap_absorb(mi_heap_t* heap, mi_heap_t* from) { |
| 411 |
mi_assert_internal(heap!=NULL); |
| 412 |
if (from==NULL || from->page_count == 0) return; |
| 413 |
|
| 414 |
// reduce the size of the delayed frees |
| 415 |
_mi_heap_delayed_free_partial(from); |
| 416 |
|
| 417 |
// transfer all pages by appending the queues; this will set a new heap field |
| 418 |
// so threads may do delayed frees in either heap for a while. |
| 419 |
// note: appending waits for each page to not be in the `MI_DELAYED_FREEING` state |
| 420 |
// so after this only the new heap will get delayed frees |
| 421 |
for (size_t i = 0; i <= MI_BIN_FULL; i++) { |
| 422 |
mi_page_queue_t* pq = &heap->pages[i]; |
| 423 |
mi_page_queue_t* append = &from->pages[i]; |
| 424 |
size_t pcount = _mi_page_queue_append(heap, pq, append); |
| 425 |
heap->page_count += pcount; |
| 426 |
from->page_count -= pcount; |
| 427 |
} |
| 428 |
mi_assert_internal(from->page_count == 0); |
| 429 |
|
| 430 |
// and do outstanding delayed frees in the `from` heap |
| 431 |
// note: be careful here as the `heap` field in all those pages no longer point to `from`, |
| 432 |
// turns out to be ok as `_mi_heap_delayed_free` only visits the list and calls a |
| 433 |
// the regular `_mi_free_delayed_block` which is safe. |
| 434 |
_mi_heap_delayed_free_all(from); |
| 435 |
#if !defined(_MSC_VER) || (_MSC_VER > 1900) // somehow the following line gives an error in VS2015, issue #353 |
| 436 |
mi_assert_internal(mi_atomic_load_ptr_relaxed(mi_block_t,&from->thread_delayed_free) == NULL); |
| 437 |
#endif |
| 438 |
|
| 439 |
// and reset the `from` heap |
| 440 |
mi_heap_reset_pages(from); |
| 441 |
} |
| 442 |
|
| 443 |
// Safe delete a heap without freeing any still allocated blocks in that heap. |
| 444 |
void mi_heap_delete(mi_heap_t* heap) |
| 445 |
{ |
| 446 |
mi_assert(heap != NULL); |
| 447 |
mi_assert(mi_heap_is_initialized(heap)); |
| 448 |
mi_assert_expensive(mi_heap_is_valid(heap)); |
| 449 |
if (heap==NULL || !mi_heap_is_initialized(heap)) return; |
| 450 |
|
| 451 |
if (!mi_heap_is_backing(heap)) { |
| 452 |
// transfer still used pages to the backing heap |
| 453 |
mi_heap_absorb(heap->tld->heap_backing, heap); |
| 454 |
} |
| 455 |
else { |
| 456 |
// the backing heap abandons its pages |
| 457 |
_mi_heap_collect_abandon(heap); |
| 458 |
} |
| 459 |
mi_assert_internal(heap->page_count==0); |
| 460 |
mi_heap_free(heap); |
| 461 |
} |
| 462 |
|
| 463 |
mi_heap_t* mi_heap_set_default(mi_heap_t* heap) { |
| 464 |
mi_assert(heap != NULL); |
| 465 |
mi_assert(mi_heap_is_initialized(heap)); |
| 466 |
if (heap==NULL || !mi_heap_is_initialized(heap)) return NULL; |
| 467 |
mi_assert_expensive(mi_heap_is_valid(heap)); |
| 468 |
mi_heap_t* old = mi_prim_get_default_heap(); |
| 469 |
_mi_heap_set_default_direct(heap); |
| 470 |
return old; |
| 471 |
} |
| 472 |
|
| 473 |
|
| 474 |
|
| 475 |
|
| 476 |
/* ----------------------------------------------------------- |
| 477 |
Analysis |
| 478 |
----------------------------------------------------------- */ |
| 479 |
|
| 480 |
// static since it is not thread safe to access heaps from other threads. |
| 481 |
static mi_heap_t* mi_heap_of_block(const void* p) { |
| 482 |
if (p == NULL) return NULL; |
| 483 |
mi_segment_t* segment = _mi_ptr_segment(p); |
| 484 |
bool valid = (_mi_ptr_cookie(segment) == segment->cookie); |
| 485 |
mi_assert_internal(valid); |
| 486 |
if mi_unlikely(!valid) return NULL; |
| 487 |
return mi_page_heap(_mi_segment_page_of(segment,p)); |
| 488 |
} |
| 489 |
|
| 490 |
bool mi_heap_contains_block(mi_heap_t* heap, const void* p) { |
| 491 |
mi_assert(heap != NULL); |
| 492 |
if (heap==NULL || !mi_heap_is_initialized(heap)) return false; |
| 493 |
return (heap == mi_heap_of_block(p)); |
| 494 |
} |
| 495 |
|
| 496 |
|
| 497 |
static bool mi_heap_page_check_owned(mi_heap_t* heap, mi_page_queue_t* pq, mi_page_t* page, void* p, void* vfound) { |
| 498 |
MI_UNUSED(heap); |
| 499 |
MI_UNUSED(pq); |
| 500 |
bool* found = (bool*)vfound; |
| 501 |
mi_segment_t* segment = _mi_page_segment(page); |
| 502 |
void* start = _mi_page_start(segment, page, NULL); |
| 503 |
void* end = (uint8_t*)start + (page->capacity * mi_page_block_size(page)); |
| 504 |
*found = (p >= start && p < end); |
| 505 |
return (!*found); // continue if not found |
| 506 |
} |
| 507 |
|
| 508 |
bool mi_heap_check_owned(mi_heap_t* heap, const void* p) { |
| 509 |
mi_assert(heap != NULL); |
| 510 |
if (heap==NULL || !mi_heap_is_initialized(heap)) return false; |
| 511 |
if (((uintptr_t)p & (MI_INTPTR_SIZE - 1)) != 0) return false; // only aligned pointers |
| 512 |
bool found = false; |
| 513 |
mi_heap_visit_pages(heap, &mi_heap_page_check_owned, (void*)p, &found); |
| 514 |
return found; |
| 515 |
} |
| 516 |
|
| 517 |
bool mi_check_owned(const void* p) { |
| 518 |
return mi_heap_check_owned(mi_prim_get_default_heap(), p); |
| 519 |
} |
| 520 |
|
| 521 |
/* ----------------------------------------------------------- |
| 522 |
Visit all heap blocks and areas |
| 523 |
Todo: enable visiting abandoned pages, and |
| 524 |
enable visiting all blocks of all heaps across threads |
| 525 |
----------------------------------------------------------- */ |
| 526 |
|
| 527 |
// Separate struct to keep `mi_page_t` out of the public interface |
| 528 |
typedef struct mi_heap_area_ex_s { |
| 529 |
mi_heap_area_t area; |
| 530 |
mi_page_t* page; |
| 531 |
} mi_heap_area_ex_t; |
| 532 |
|
| 533 |
static void mi_fast_divisor(size_t divisor, size_t* magic, size_t* shift) { |
| 534 |
mi_assert_internal(divisor > 0 && divisor <= UINT32_MAX); |
| 535 |
*shift = MI_INTPTR_BITS - mi_clz(divisor - 1); |
| 536 |
*magic = (size_t)(((1ULL << 32) * ((1ULL << *shift) - divisor)) / divisor + 1); |
| 537 |
} |
| 538 |
|
| 539 |
static size_t mi_fast_divide(size_t n, size_t magic, size_t shift) { |
| 540 |
mi_assert_internal(n <= UINT32_MAX); |
| 541 |
return ((((uint64_t) n * magic) >> 32) + n) >> shift; |
| 542 |
} |
| 543 |
|
| 544 |
bool _mi_heap_area_visit_blocks(const mi_heap_area_t* area, mi_page_t *page, mi_block_visit_fun* visitor, void* arg) { |
| 545 |
mi_assert(area != NULL); |
| 546 |
if (area==NULL) return true; |
| 547 |
mi_assert(page != NULL); |
| 548 |
if (page == NULL) return true; |
| 549 |
|
| 550 |
mi_assert_internal(page->local_free == NULL); |
| 551 |
if (page->used == 0) return true; |
| 552 |
|
| 553 |
const size_t bsize = mi_page_block_size(page); |
| 554 |
const size_t ubsize = mi_page_usable_block_size(page); // without padding |
| 555 |
size_t psize; |
| 556 |
uint8_t* pstart = _mi_page_start(_mi_page_segment(page), page, &psize); |
| 557 |
mi_heap_t* heap = mi_page_heap(page); |
| 558 |
|
| 559 |
if (page->capacity == 1) { |
| 560 |
// optimize page with one block |
| 561 |
mi_assert_internal(page->used == 1 && page->free == NULL); |
| 562 |
return visitor(heap, area, pstart, ubsize, arg); |
| 563 |
} |
| 564 |
|
| 565 |
if (page->used == page->capacity) { |
| 566 |
// optimize full pages |
| 567 |
uint8_t* block = pstart; |
| 568 |
for (size_t i = 0; i < page->capacity; i++) { |
| 569 |
if (!visitor(heap, area, block, ubsize, arg)) return false; |
| 570 |
block += bsize; |
| 571 |
} |
| 572 |
return true; |
| 573 |
} |
| 574 |
|
| 575 |
// create a bitmap of free blocks. |
| 576 |
#define MI_MAX_BLOCKS (MI_SMALL_PAGE_SIZE / sizeof(void*)) |
| 577 |
uintptr_t free_map[MI_MAX_BLOCKS / MI_INTPTR_BITS]; |
| 578 |
size_t bmapsize = (page->capacity + MI_INTPTR_BITS - 1) / MI_INTPTR_BITS; |
| 579 |
memset(free_map, 0, bmapsize * sizeof(uintptr_t)); |
| 580 |
|
| 581 |
if (page->capacity % MI_INTPTR_BITS != 0) { |
| 582 |
size_t shift = (page->capacity % MI_INTPTR_BITS); |
| 583 |
uintptr_t mask = (UINTPTR_MAX << shift); |
| 584 |
free_map[bmapsize-1] = mask; |
| 585 |
} |
| 586 |
|
| 587 |
// fast repeated division by the block size |
| 588 |
size_t magic, shift; |
| 589 |
mi_fast_divisor(bsize, &magic, &shift); |
| 590 |
|
| 591 |
#if MI_DEBUG>1 |
| 592 |
size_t free_count = 0; |
| 593 |
#endif |
| 594 |
for (mi_block_t* block = page->free; block != NULL; block = mi_block_next(page,block)) { |
| 595 |
#if MI_DEBUG>1 |
| 596 |
free_count++; |
| 597 |
#endif |
| 598 |
mi_assert_internal((uint8_t*)block >= pstart && (uint8_t*)block < (pstart + psize)); |
| 599 |
size_t offset = (uint8_t*)block - pstart; |
| 600 |
mi_assert_internal(offset % bsize == 0); |
| 601 |
size_t blockidx = mi_fast_divide(offset, magic, shift); |
| 602 |
mi_assert_internal(blockidx == offset / bsize); |
| 603 |
mi_assert_internal(blockidx < MI_MAX_BLOCKS); |
| 604 |
size_t bitidx = (blockidx / MI_INTPTR_BITS); |
| 605 |
size_t bit = blockidx - (bitidx * MI_INTPTR_BITS); |
| 606 |
free_map[bitidx] |= ((uintptr_t)1 << bit); |
| 607 |
} |
| 608 |
mi_assert_internal(page->capacity == (free_count + page->used)); |
| 609 |
|
| 610 |
// walk through all blocks skipping the free ones |
| 611 |
#if MI_DEBUG>1 |
| 612 |
size_t used_count = 0; |
| 613 |
#endif |
| 614 |
uint8_t* block = pstart; |
| 615 |
for (size_t i = 0; i < bmapsize; i++) { |
| 616 |
if (free_map[i] == 0) { |
| 617 |
// every block is in use |
| 618 |
for (size_t j = 0; j < MI_INTPTR_BITS; j++) { |
| 619 |
#if MI_DEBUG>1 |
| 620 |
used_count++; |
| 621 |
#endif |
| 622 |
if (!visitor(heap, area, block, ubsize, arg)) return false; |
| 623 |
block += bsize; |
| 624 |
} |
| 625 |
} |
| 626 |
else { |
| 627 |
uintptr_t m = ~free_map[i]; |
| 628 |
while (m) { |
| 629 |
#if MI_DEBUG>1 |
| 630 |
used_count++; |
| 631 |
#endif |
| 632 |
size_t bitidx = mi_ctz(m); |
| 633 |
if (!visitor(heap, area, block + (bitidx * bsize), ubsize, arg)) return false; |
| 634 |
m &= m - 1; |
| 635 |
} |
| 636 |
block += bsize * MI_INTPTR_BITS; |
| 637 |
} |
| 638 |
} |
| 639 |
mi_assert_internal(page->used == used_count); |
| 640 |
return true; |
| 641 |
} |
| 642 |
|
| 643 |
typedef bool (mi_heap_area_visit_fun)(const mi_heap_t* heap, const mi_heap_area_ex_t* area, void* arg); |
| 644 |
|
| 645 |
void _mi_heap_area_init(mi_heap_area_t* area, mi_page_t* page) { |
| 646 |
_mi_page_free_collect(page,true); |
| 647 |
const size_t bsize = mi_page_block_size(page); |
| 648 |
const size_t ubsize = mi_page_usable_block_size(page); |
| 649 |
area->reserved = page->reserved * bsize; |
| 650 |
area->committed = page->capacity * bsize; |
| 651 |
area->blocks = _mi_page_start(_mi_page_segment(page), page, NULL); |
| 652 |
area->used = page->used; // number of blocks in use (#553) |
| 653 |
area->block_size = ubsize; |
| 654 |
area->full_block_size = bsize; |
| 655 |
} |
| 656 |
|
| 657 |
static bool mi_heap_visit_areas_page(mi_heap_t* heap, mi_page_queue_t* pq, mi_page_t* page, void* vfun, void* arg) { |
| 658 |
MI_UNUSED(heap); |
| 659 |
MI_UNUSED(pq); |
| 660 |
mi_heap_area_visit_fun* fun = (mi_heap_area_visit_fun*)vfun; |
| 661 |
mi_heap_area_ex_t xarea; |
| 662 |
xarea.page = page; |
| 663 |
_mi_heap_area_init(&xarea.area, page); |
| 664 |
return fun(heap, &xarea, arg); |
| 665 |
} |
| 666 |
|
| 667 |
// Visit all heap pages as areas |
| 668 |
static bool mi_heap_visit_areas(const mi_heap_t* heap, mi_heap_area_visit_fun* visitor, void* arg) { |
| 669 |
if (visitor == NULL) return false; |
| 670 |
return mi_heap_visit_pages((mi_heap_t*)heap, &mi_heap_visit_areas_page, (void*)(visitor), arg); // note: function pointer to void* :-{ |
| 671 |
} |
| 672 |
|
| 673 |
// Just to pass arguments |
| 674 |
typedef struct mi_visit_blocks_args_s { |
| 675 |
bool visit_blocks; |
| 676 |
mi_block_visit_fun* visitor; |
| 677 |
void* arg; |
| 678 |
} mi_visit_blocks_args_t; |
| 679 |
|
| 680 |
static bool mi_heap_area_visitor(const mi_heap_t* heap, const mi_heap_area_ex_t* xarea, void* arg) { |
| 681 |
mi_visit_blocks_args_t* args = (mi_visit_blocks_args_t*)arg; |
| 682 |
if (!args->visitor(heap, &xarea->area, NULL, xarea->area.block_size, args->arg)) return false; |
| 683 |
if (args->visit_blocks) { |
| 684 |
return _mi_heap_area_visit_blocks(&xarea->area, xarea->page, args->visitor, args->arg); |
| 685 |
} |
| 686 |
else { |
| 687 |
return true; |
| 688 |
} |
| 689 |
} |
| 690 |
|
| 691 |
// Visit all blocks in a heap |
| 692 |
bool mi_heap_visit_blocks(const mi_heap_t* heap, bool visit_blocks, mi_block_visit_fun* visitor, void* arg) { |
| 693 |
mi_visit_blocks_args_t args = { visit_blocks, visitor, arg }; |
| 694 |
_mi_heap_delayed_free_partial((mi_heap_t *)heap); |
| 695 |
return mi_heap_visit_areas(heap, &mi_heap_area_visitor, &args); |
| 696 |
} |