Debian Codegraph @

Objects/mimalloc/heap.c

raw
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 }