1/*----------------------------------------------------------------------------
2Copyright (c) 2018-2020, 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
8/* -----------------------------------------------------------
9 The core of the allocator. Every segment contains
10 pages of a certain block size. The main function
11 exported is `mi_malloc_generic`.
12----------------------------------------------------------- */
13
14#include "mimalloc.h"
15#include "mimalloc-internal.h"
16#include "mimalloc-atomic.h"
17
18/* -----------------------------------------------------------
19 Definition of page queues for each block size
20----------------------------------------------------------- */
21
22#define MI_IN_PAGE_C
23#include "page-queue.c"
24#undef MI_IN_PAGE_C
25
26
27/* -----------------------------------------------------------
28 Page helpers
29----------------------------------------------------------- */
30
31// Index a block in a page
32static inline mi_block_t* mi_page_block_at(const mi_page_t* page, void* page_start, size_t block_size, size_t i) {
33 MI_UNUSED(page);
34 mi_assert_internal(page != NULL);
35 mi_assert_internal(i <= page->reserved);
36 return (mi_block_t*)((uint8_t*)page_start + (i * block_size));
37}
38
39static void mi_page_init(mi_heap_t* heap, mi_page_t* page, size_t size, mi_tld_t* tld);
40static void mi_page_extend_free(mi_heap_t* heap, mi_page_t* page, mi_tld_t* tld);
41
42#if (MI_DEBUG>=3)
43static size_t mi_page_list_count(mi_page_t* page, mi_block_t* head) {
44 size_t count = 0;
45 while (head != NULL) {
46 mi_assert_internal(page == _mi_ptr_page(head));
47 count++;
48 head = mi_block_next(page, head);
49 }
50 return count;
51}
52
53/*
54// Start of the page available memory
55static inline uint8_t* mi_page_area(const mi_page_t* page) {
56 return _mi_page_start(_mi_page_segment(page), page, NULL);
57}
58*/
59
60static bool mi_page_list_is_valid(mi_page_t* page, mi_block_t* p) {
61 size_t psize;
62 uint8_t* page_area = _mi_page_start(_mi_page_segment(page), page, &psize);
63 mi_block_t* start = (mi_block_t*)page_area;
64 mi_block_t* end = (mi_block_t*)(page_area + psize);
65 while(p != NULL) {
66 if (p < start || p >= end) return false;
67 p = mi_block_next(page, p);
68 }
69 return true;
70}
71
72static bool mi_page_is_valid_init(mi_page_t* page) {
73 mi_assert_internal(page->xblock_size > 0);
74 mi_assert_internal(page->used <= page->capacity);
75 mi_assert_internal(page->capacity <= page->reserved);
76
77 mi_segment_t* segment = _mi_page_segment(page);
78 uint8_t* start = _mi_page_start(segment,page,NULL);
79 mi_assert_internal(start == _mi_segment_page_start(segment,page,NULL));
80 //const size_t bsize = mi_page_block_size(page);
81 //mi_assert_internal(start + page->capacity*page->block_size == page->top);
82
83 mi_assert_internal(mi_page_list_is_valid(page,page->free));
84 mi_assert_internal(mi_page_list_is_valid(page,page->local_free));
85
86 #if MI_DEBUG>3 // generally too expensive to check this
87 if (page->is_zero) {
88 const size_t ubsize = mi_page_usable_block_size(page);
89 for(mi_block_t* block = page->free; block != NULL; block = mi_block_next(page,block)) {
90 mi_assert_expensive(mi_mem_is_zero(block + 1, ubsize - sizeof(mi_block_t)));
91 }
92 }
93 #endif
94
95 mi_block_t* tfree = mi_page_thread_free(page);
96 mi_assert_internal(mi_page_list_is_valid(page, tfree));
97 //size_t tfree_count = mi_page_list_count(page, tfree);
98 //mi_assert_internal(tfree_count <= page->thread_freed + 1);
99
100 size_t free_count = mi_page_list_count(page, page->free) + mi_page_list_count(page, page->local_free);
101 mi_assert_internal(page->used + free_count == page->capacity);
102
103 return true;
104}
105
106bool _mi_page_is_valid(mi_page_t* page) {
107 mi_assert_internal(mi_page_is_valid_init(page));
108 #if MI_SECURE
109 mi_assert_internal(page->keys[0] != 0);
110 #endif
111 if (mi_page_heap(page)!=NULL) {
112 mi_segment_t* segment = _mi_page_segment(page);
113
114 mi_assert_internal(!_mi_process_is_initialized || segment->thread_id==0 || segment->thread_id == mi_page_heap(page)->thread_id);
115 if (segment->kind != MI_SEGMENT_HUGE) {
116 mi_page_queue_t* pq = mi_page_queue_of(page);
117 mi_assert_internal(mi_page_queue_contains(pq, page));
118 mi_assert_internal(pq->block_size==mi_page_block_size(page) || mi_page_block_size(page) > MI_MEDIUM_OBJ_SIZE_MAX || mi_page_is_in_full(page));
119 mi_assert_internal(mi_heap_contains_queue(mi_page_heap(page),pq));
120 }
121 }
122 return true;
123}
124#endif
125
126void _mi_page_use_delayed_free(mi_page_t* page, mi_delayed_t delay, bool override_never) {
127 while (!_mi_page_try_use_delayed_free(page, delay, override_never)) {
128 mi_atomic_yield();
129 }
130}
131
132bool _mi_page_try_use_delayed_free(mi_page_t* page, mi_delayed_t delay, bool override_never) {
133 mi_thread_free_t tfreex;
134 mi_delayed_t old_delay;
135 mi_thread_free_t tfree;
136 size_t yield_count = 0;
137 do {
138 tfree = mi_atomic_load_acquire(&page->xthread_free); // note: must acquire as we can break/repeat this loop and not do a CAS;
139 tfreex = mi_tf_set_delayed(tfree, delay);
140 old_delay = mi_tf_delayed(tfree);
141 if mi_unlikely(old_delay == MI_DELAYED_FREEING) {
142 if (yield_count >= 4) return false; // give up after 4 tries
143 yield_count++;
144 mi_atomic_yield(); // delay until outstanding MI_DELAYED_FREEING are done.
145 // tfree = mi_tf_set_delayed(tfree, MI_NO_DELAYED_FREE); // will cause CAS to busy fail
146 }
147 else if (delay == old_delay) {
148 break; // avoid atomic operation if already equal
149 }
150 else if (!override_never && old_delay == MI_NEVER_DELAYED_FREE) {
151 break; // leave never-delayed flag set
152 }
153 } while ((old_delay == MI_DELAYED_FREEING) ||
154 !mi_atomic_cas_weak_release(&page->xthread_free, &tfree, tfreex));
155
156 return true; // success
157}
158
159/* -----------------------------------------------------------
160 Page collect the `local_free` and `thread_free` lists
161----------------------------------------------------------- */
162
163// Collect the local `thread_free` list using an atomic exchange.
164// Note: The exchange must be done atomically as this is used right after
165// moving to the full list in `mi_page_collect_ex` and we need to
166// ensure that there was no race where the page became unfull just before the move.
167static void _mi_page_thread_free_collect(mi_page_t* page)
168{
169 mi_block_t* head;
170 mi_thread_free_t tfreex;
171 mi_thread_free_t tfree = mi_atomic_load_relaxed(&page->xthread_free);
172 do {
173 head = mi_tf_block(tfree);
174 tfreex = mi_tf_set_block(tfree,NULL);
175 } while (!mi_atomic_cas_weak_acq_rel(&page->xthread_free, &tfree, tfreex));
176
177 // return if the list is empty
178 if (head == NULL) return;
179
180 // find the tail -- also to get a proper count (without data races)
181 uint32_t max_count = page->capacity; // cannot collect more than capacity
182 uint32_t count = 1;
183 mi_block_t* tail = head;
184 mi_block_t* next;
185 while ((next = mi_block_next(page,tail)) != NULL && count <= max_count) {
186 count++;
187 tail = next;
188 }
189 // if `count > max_count` there was a memory corruption (possibly infinite list due to double multi-threaded free)
190 if (count > max_count) {
191 _mi_error_message(EFAULT, "corrupted thread-free list\n");
192 return; // the thread-free items cannot be freed
193 }
194
195 // and append the current local free list
196 mi_block_set_next(page,tail, page->local_free);
197 page->local_free = head;
198
199 // update counts now
200 page->used -= count;
201}
202
203void _mi_page_free_collect(mi_page_t* page, bool force) {
204 mi_assert_internal(page!=NULL);
205
206 // collect the thread free list
207 if (force || mi_page_thread_free(page) != NULL) { // quick test to avoid an atomic operation
208 _mi_page_thread_free_collect(page);
209 }
210
211 // and the local free list
212 if (page->local_free != NULL) {
213 if mi_likely(page->free == NULL) {
214 // usual case
215 page->free = page->local_free;
216 page->local_free = NULL;
217 page->is_zero = false;
218 }
219 else if (force) {
220 // append -- only on shutdown (force) as this is a linear operation
221 mi_block_t* tail = page->local_free;
222 mi_block_t* next;
223 while ((next = mi_block_next(page, tail)) != NULL) {
224 tail = next;
225 }
226 mi_block_set_next(page, tail, page->free);
227 page->free = page->local_free;
228 page->local_free = NULL;
229 page->is_zero = false;
230 }
231 }
232
233 mi_assert_internal(!force || page->local_free == NULL);
234}
235
236
237
238/* -----------------------------------------------------------
239 Page fresh and retire
240----------------------------------------------------------- */
241
242// called from segments when reclaiming abandoned pages
243void _mi_page_reclaim(mi_heap_t* heap, mi_page_t* page) {
244 mi_assert_expensive(mi_page_is_valid_init(page));
245
246 mi_assert_internal(mi_page_heap(page) == heap);
247 mi_assert_internal(mi_page_thread_free_flag(page) != MI_NEVER_DELAYED_FREE);
248 mi_assert_internal(_mi_page_segment(page)->kind != MI_SEGMENT_HUGE);
249 mi_assert_internal(!page->is_reset);
250 // TODO: push on full queue immediately if it is full?
251 mi_page_queue_t* pq = mi_page_queue(heap, mi_page_block_size(page));
252 mi_page_queue_push(heap, pq, page);
253 mi_assert_expensive(_mi_page_is_valid(page));
254}
255
256// allocate a fresh page from a segment
257static mi_page_t* mi_page_fresh_alloc(mi_heap_t* heap, mi_page_queue_t* pq, size_t block_size) {
258 mi_assert_internal(pq==NULL||mi_heap_contains_queue(heap, pq));
259 mi_page_t* page = _mi_segment_page_alloc(heap, block_size, &heap->tld->segments, &heap->tld->os);
260 if (page == NULL) {
261 // this may be out-of-memory, or an abandoned page was reclaimed (and in our queue)
262 return NULL;
263 }
264 mi_assert_internal(pq==NULL || _mi_page_segment(page)->kind != MI_SEGMENT_HUGE);
265 mi_page_init(heap, page, block_size, heap->tld);
266 mi_heap_stat_increase(heap, pages, 1);
267 if (pq!=NULL) mi_page_queue_push(heap, pq, page); // huge pages use pq==NULL
268 mi_assert_expensive(_mi_page_is_valid(page));
269 return page;
270}
271
272// Get a fresh page to use
273static mi_page_t* mi_page_fresh(mi_heap_t* heap, mi_page_queue_t* pq) {
274 mi_assert_internal(mi_heap_contains_queue(heap, pq));
275 mi_page_t* page = mi_page_fresh_alloc(heap, pq, pq->block_size);
276 if (page==NULL) return NULL;
277 mi_assert_internal(pq->block_size==mi_page_block_size(page));
278 mi_assert_internal(pq==mi_page_queue(heap, mi_page_block_size(page)));
279 return page;
280}
281
282/* -----------------------------------------------------------
283 Do any delayed frees
284 (put there by other threads if they deallocated in a full page)
285----------------------------------------------------------- */
286void _mi_heap_delayed_free_all(mi_heap_t* heap) {
287 while (!_mi_heap_delayed_free_partial(heap)) {
288 mi_atomic_yield();
289 }
290}
291
292// returns true if all delayed frees were processed
293bool _mi_heap_delayed_free_partial(mi_heap_t* heap) {
294 // take over the list (note: no atomic exchange since it is often NULL)
295 mi_block_t* block = mi_atomic_load_ptr_relaxed(mi_block_t, &heap->thread_delayed_free);
296 while (block != NULL && !mi_atomic_cas_ptr_weak_acq_rel(mi_block_t, &heap->thread_delayed_free, &block, NULL)) { /* nothing */ };
297 bool all_freed = true;
298
299 // and free them all
300 while(block != NULL) {
301 mi_block_t* next = mi_block_nextx(heap,block, heap->keys);
302 // use internal free instead of regular one to keep stats etc correct
303 if (!_mi_free_delayed_block(block)) {
304 // we might already start delayed freeing while another thread has not yet
305 // reset the delayed_freeing flag; in that case delay it further by reinserting the current block
306 // into the delayed free list
307 all_freed = false;
308 mi_block_t* dfree = mi_atomic_load_ptr_relaxed(mi_block_t, &heap->thread_delayed_free);
309 do {
310 mi_block_set_nextx(heap, block, dfree, heap->keys);
311 } while (!mi_atomic_cas_ptr_weak_release(mi_block_t,&heap->thread_delayed_free, &dfree, block));
312 }
313 block = next;
314 }
315 return all_freed;
316}
317
318/* -----------------------------------------------------------
319 Unfull, abandon, free and retire
320----------------------------------------------------------- */
321
322// Move a page from the full list back to a regular list
323void _mi_page_unfull(mi_page_t* page) {
324 mi_assert_internal(page != NULL);
325 mi_assert_expensive(_mi_page_is_valid(page));
326 mi_assert_internal(mi_page_is_in_full(page));
327 if (!mi_page_is_in_full(page)) return;
328
329 mi_heap_t* heap = mi_page_heap(page);
330 mi_page_queue_t* pqfull = &heap->pages[MI_BIN_FULL];
331 mi_page_set_in_full(page, false); // to get the right queue
332 mi_page_queue_t* pq = mi_heap_page_queue_of(heap, page);
333 mi_page_set_in_full(page, true);
334 mi_page_queue_enqueue_from(pq, pqfull, page);
335}
336
337static void mi_page_to_full(mi_page_t* page, mi_page_queue_t* pq) {
338 mi_assert_internal(pq == mi_page_queue_of(page));
339 mi_assert_internal(!mi_page_immediate_available(page));
340 mi_assert_internal(!mi_page_is_in_full(page));
341
342 if (mi_page_is_in_full(page)) return;
343 mi_page_queue_enqueue_from(&mi_page_heap(page)->pages[MI_BIN_FULL], pq, page);
344 _mi_page_free_collect(page,false); // try to collect right away in case another thread freed just before MI_USE_DELAYED_FREE was set
345}
346
347
348// Abandon a page with used blocks at the end of a thread.
349// Note: only call if it is ensured that no references exist from
350// the `page->heap->thread_delayed_free` into this page.
351// Currently only called through `mi_heap_collect_ex` which ensures this.
352void _mi_page_abandon(mi_page_t* page, mi_page_queue_t* pq) {
353 mi_assert_internal(page != NULL);
354 mi_assert_expensive(_mi_page_is_valid(page));
355 mi_assert_internal(pq == mi_page_queue_of(page));
356 mi_assert_internal(mi_page_heap(page) != NULL);
357
358 mi_heap_t* pheap = mi_page_heap(page);
359
360 // remove from our page list
361 mi_segments_tld_t* segments_tld = &pheap->tld->segments;
362 mi_page_queue_remove(pq, page);
363
364 // page is no longer associated with our heap
365 mi_assert_internal(mi_page_thread_free_flag(page)==MI_NEVER_DELAYED_FREE);
366 mi_page_set_heap(page, NULL);
367
368#if MI_DEBUG>1
369 // check there are no references left..
370 for (mi_block_t* block = (mi_block_t*)pheap->thread_delayed_free; block != NULL; block = mi_block_nextx(pheap, block, pheap->keys)) {
371 mi_assert_internal(_mi_ptr_page(block) != page);
372 }
373#endif
374
375 // and abandon it
376 mi_assert_internal(mi_page_heap(page) == NULL);
377 _mi_segment_page_abandon(page,segments_tld);
378}
379
380
381// Free a page with no more free blocks
382void _mi_page_free(mi_page_t* page, mi_page_queue_t* pq, bool force) {
383 mi_assert_internal(page != NULL);
384 mi_assert_expensive(_mi_page_is_valid(page));
385 mi_assert_internal(pq == mi_page_queue_of(page));
386 mi_assert_internal(mi_page_all_free(page));
387 mi_assert_internal(mi_page_thread_free_flag(page)!=MI_DELAYED_FREEING);
388
389 // no more aligned blocks in here
390 mi_page_set_has_aligned(page, false);
391
392 mi_heap_t* heap = mi_page_heap(page);
393
394 // remove from the page list
395 // (no need to do _mi_heap_delayed_free first as all blocks are already free)
396 mi_segments_tld_t* segments_tld = &heap->tld->segments;
397 mi_page_queue_remove(pq, page);
398
399 // and free it
400 mi_page_set_heap(page,NULL);
401 _mi_segment_page_free(page, force, segments_tld);
402}
403
404// Retire parameters
405#define MI_MAX_RETIRE_SIZE MI_MEDIUM_OBJ_SIZE_MAX
406#define MI_RETIRE_CYCLES (8)
407
408// Retire a page with no more used blocks
409// Important to not retire too quickly though as new
410// allocations might coming.
411// Note: called from `mi_free` and benchmarks often
412// trigger this due to freeing everything and then
413// allocating again so careful when changing this.
414void _mi_page_retire(mi_page_t* page) mi_attr_noexcept {
415 mi_assert_internal(page != NULL);
416 mi_assert_expensive(_mi_page_is_valid(page));
417 mi_assert_internal(mi_page_all_free(page));
418
419 mi_page_set_has_aligned(page, false);
420
421 // don't retire too often..
422 // (or we end up retiring and re-allocating most of the time)
423 // NOTE: refine this more: we should not retire if this
424 // is the only page left with free blocks. It is not clear
425 // how to check this efficiently though...
426 // for now, we don't retire if it is the only page left of this size class.
427 mi_page_queue_t* pq = mi_page_queue_of(page);
428 if mi_likely(page->xblock_size <= MI_MAX_RETIRE_SIZE && !mi_page_is_in_full(page)) {
429 if (pq->last==page && pq->first==page) { // the only page in the queue?
430 mi_stat_counter_increase(_mi_stats_main.page_no_retire,1);
431 page->retire_expire = 1 + (page->xblock_size <= MI_SMALL_OBJ_SIZE_MAX ? MI_RETIRE_CYCLES : MI_RETIRE_CYCLES/4);
432 mi_heap_t* heap = mi_page_heap(page);
433 mi_assert_internal(pq >= heap->pages);
434 const size_t index = pq - heap->pages;
435 mi_assert_internal(index < MI_BIN_FULL && index < MI_BIN_HUGE);
436 if (index < heap->page_retired_min) heap->page_retired_min = index;
437 if (index > heap->page_retired_max) heap->page_retired_max = index;
438 mi_assert_internal(mi_page_all_free(page));
439 return; // dont't free after all
440 }
441 }
442 _mi_page_free(page, pq, false);
443}
444
445// free retired pages: we don't need to look at the entire queues
446// since we only retire pages that are at the head position in a queue.
447void _mi_heap_collect_retired(mi_heap_t* heap, bool force) {
448 size_t min = MI_BIN_FULL;
449 size_t max = 0;
450 for(size_t bin = heap->page_retired_min; bin <= heap->page_retired_max; bin++) {
451 mi_page_queue_t* pq = &heap->pages[bin];
452 mi_page_t* page = pq->first;
453 if (page != NULL && page->retire_expire != 0) {
454 if (mi_page_all_free(page)) {
455 page->retire_expire--;
456 if (force || page->retire_expire == 0) {
457 _mi_page_free(pq->first, pq, force);
458 }
459 else {
460 // keep retired, update min/max
461 if (bin < min) min = bin;
462 if (bin > max) max = bin;
463 }
464 }
465 else {
466 page->retire_expire = 0;
467 }
468 }
469 }
470 heap->page_retired_min = min;
471 heap->page_retired_max = max;
472}
473
474
475/* -----------------------------------------------------------
476 Initialize the initial free list in a page.
477 In secure mode we initialize a randomized list by
478 alternating between slices.
479----------------------------------------------------------- */
480
481#define MI_MAX_SLICE_SHIFT (6) // at most 64 slices
482#define MI_MAX_SLICES (1UL << MI_MAX_SLICE_SHIFT)
483#define MI_MIN_SLICES (2)
484
485static void mi_page_free_list_extend_secure(mi_heap_t* const heap, mi_page_t* const page, const size_t bsize, const size_t extend, mi_stats_t* const stats) {
486 MI_UNUSED(stats);
487 #if (MI_SECURE<=2)
488 mi_assert_internal(page->free == NULL);
489 mi_assert_internal(page->local_free == NULL);
490 #endif
491 mi_assert_internal(page->capacity + extend <= page->reserved);
492 mi_assert_internal(bsize == mi_page_block_size(page));
493 void* const page_area = _mi_page_start(_mi_page_segment(page), page, NULL);
494
495 // initialize a randomized free list
496 // set up `slice_count` slices to alternate between
497 size_t shift = MI_MAX_SLICE_SHIFT;
498 while ((extend >> shift) == 0) {
499 shift--;
500 }
501 const size_t slice_count = (size_t)1U << shift;
502 const size_t slice_extend = extend / slice_count;
503 mi_assert_internal(slice_extend >= 1);
504 mi_block_t* blocks[MI_MAX_SLICES]; // current start of the slice
505 size_t counts[MI_MAX_SLICES]; // available objects in the slice
506 for (size_t i = 0; i < slice_count; i++) {
507 blocks[i] = mi_page_block_at(page, page_area, bsize, page->capacity + i*slice_extend);
508 counts[i] = slice_extend;
509 }
510 counts[slice_count-1] += (extend % slice_count); // final slice holds the modulus too (todo: distribute evenly?)
511
512 // and initialize the free list by randomly threading through them
513 // set up first element
514 const uintptr_t r = _mi_heap_random_next(heap);
515 size_t current = r % slice_count;
516 counts[current]--;
517 mi_block_t* const free_start = blocks[current];
518 // and iterate through the rest; use `random_shuffle` for performance
519 uintptr_t rnd = _mi_random_shuffle(r|1); // ensure not 0
520 for (size_t i = 1; i < extend; i++) {
521 // call random_shuffle only every INTPTR_SIZE rounds
522 const size_t round = i%MI_INTPTR_SIZE;
523 if (round == 0) rnd = _mi_random_shuffle(rnd);
524 // select a random next slice index
525 size_t next = ((rnd >> 8*round) & (slice_count-1));
526 while (counts[next]==0) { // ensure it still has space
527 next++;
528 if (next==slice_count) next = 0;
529 }
530 // and link the current block to it
531 counts[next]--;
532 mi_block_t* const block = blocks[current];
533 blocks[current] = (mi_block_t*)((uint8_t*)block + bsize); // bump to the following block
534 mi_block_set_next(page, block, blocks[next]); // and set next; note: we may have `current == next`
535 current = next;
536 }
537 // prepend to the free list (usually NULL)
538 mi_block_set_next(page, blocks[current], page->free); // end of the list
539 page->free = free_start;
540}
541
542static mi_decl_noinline void mi_page_free_list_extend( mi_page_t* const page, const size_t bsize, const size_t extend, mi_stats_t* const stats)
543{
544 MI_UNUSED(stats);
545 #if (MI_SECURE <= 2)
546 mi_assert_internal(page->free == NULL);
547 mi_assert_internal(page->local_free == NULL);
548 #endif
549 mi_assert_internal(page->capacity + extend <= page->reserved);
550 mi_assert_internal(bsize == mi_page_block_size(page));
551 void* const page_area = _mi_page_start(_mi_page_segment(page), page, NULL );
552
553 mi_block_t* const start = mi_page_block_at(page, page_area, bsize, page->capacity);
554
555 // initialize a sequential free list
556 mi_block_t* const last = mi_page_block_at(page, page_area, bsize, page->capacity + extend - 1);
557 mi_block_t* block = start;
558 while(block <= last) {
559 mi_block_t* next = (mi_block_t*)((uint8_t*)block + bsize);
560 mi_block_set_next(page,block,next);
561 block = next;
562 }
563 // prepend to free list (usually `NULL`)
564 mi_block_set_next(page, last, page->free);
565 page->free = start;
566}
567
568/* -----------------------------------------------------------
569 Page initialize and extend the capacity
570----------------------------------------------------------- */
571
572#define MI_MAX_EXTEND_SIZE (4*1024) // heuristic, one OS page seems to work well.
573#if (MI_SECURE>0)
574#define MI_MIN_EXTEND (8*MI_SECURE) // extend at least by this many
575#else
576#define MI_MIN_EXTEND (1)
577#endif
578
579// Extend the capacity (up to reserved) by initializing a free list
580// We do at most `MI_MAX_EXTEND` to avoid touching too much memory
581// Note: we also experimented with "bump" allocation on the first
582// allocations but this did not speed up any benchmark (due to an
583// extra test in malloc? or cache effects?)
584static void mi_page_extend_free(mi_heap_t* heap, mi_page_t* page, mi_tld_t* tld) {
585 MI_UNUSED(tld);
586 mi_assert_expensive(mi_page_is_valid_init(page));
587 #if (MI_SECURE<=2)
588 mi_assert(page->free == NULL);
589 mi_assert(page->local_free == NULL);
590 if (page->free != NULL) return;
591 #endif
592 if (page->capacity >= page->reserved) return;
593
594 size_t page_size;
595 _mi_page_start(_mi_page_segment(page), page, &page_size);
596 mi_stat_counter_increase(tld->stats.pages_extended, 1);
597
598 // calculate the extend count
599 const size_t bsize = (page->xblock_size < MI_HUGE_BLOCK_SIZE ? page->xblock_size : page_size);
600 size_t extend = page->reserved - page->capacity;
601 mi_assert_internal(extend > 0);
602
603 size_t max_extend = (bsize >= MI_MAX_EXTEND_SIZE ? MI_MIN_EXTEND : MI_MAX_EXTEND_SIZE/(uint32_t)bsize);
604 if (max_extend < MI_MIN_EXTEND) { max_extend = MI_MIN_EXTEND; }
605 mi_assert_internal(max_extend > 0);
606
607 if (extend > max_extend) {
608 // ensure we don't touch memory beyond the page to reduce page commit.
609 // the `lean` benchmark tests this. Going from 1 to 8 increases rss by 50%.
610 extend = max_extend;
611 }
612
613 mi_assert_internal(extend > 0 && extend + page->capacity <= page->reserved);
614 mi_assert_internal(extend < (1UL<<16));
615
616 // and append the extend the free list
617 if (extend < MI_MIN_SLICES || MI_SECURE==0) { //!mi_option_is_enabled(mi_option_secure)) {
618 mi_page_free_list_extend(page, bsize, extend, &tld->stats );
619 }
620 else {
621 mi_page_free_list_extend_secure(heap, page, bsize, extend, &tld->stats);
622 }
623 // enable the new free list
624 page->capacity += (uint16_t)extend;
625 mi_stat_increase(tld->stats.page_committed, extend * bsize);
626
627 // extension into zero initialized memory preserves the zero'd free list
628 if (!page->is_zero_init) {
629 page->is_zero = false;
630 }
631 mi_assert_expensive(mi_page_is_valid_init(page));
632}
633
634// Initialize a fresh page
635static void mi_page_init(mi_heap_t* heap, mi_page_t* page, size_t block_size, mi_tld_t* tld) {
636 mi_assert(page != NULL);
637 mi_segment_t* segment = _mi_page_segment(page);
638 mi_assert(segment != NULL);
639 mi_assert_internal(block_size > 0);
640 // set fields
641 mi_page_set_heap(page, heap);
642 page->xblock_size = (block_size < MI_HUGE_BLOCK_SIZE ? (uint32_t)block_size : MI_HUGE_BLOCK_SIZE); // initialize before _mi_segment_page_start
643 size_t page_size;
644 const void* page_start = _mi_segment_page_start(segment, page, &page_size);
645 MI_UNUSED(page_start);
646 mi_track_mem_noaccess(page_start,page_size);
647 mi_assert_internal(mi_page_block_size(page) <= page_size);
648 mi_assert_internal(page_size <= page->slice_count*MI_SEGMENT_SLICE_SIZE);
649 mi_assert_internal(page_size / block_size < (1L<<16));
650 page->reserved = (uint16_t)(page_size / block_size);
651 #ifdef MI_ENCODE_FREELIST
652 page->keys[0] = _mi_heap_random_next(heap);
653 page->keys[1] = _mi_heap_random_next(heap);
654 #endif
655 #if MI_DEBUG > 0
656 page->is_zero = false; // ensure in debug mode we initialize with MI_DEBUG_UNINIT, see issue #501
657 #else
658 page->is_zero = page->is_zero_init;
659 #endif
660
661 mi_assert_internal(page->is_committed);
662 mi_assert_internal(!page->is_reset);
663 mi_assert_internal(page->capacity == 0);
664 mi_assert_internal(page->free == NULL);
665 mi_assert_internal(page->used == 0);
666 mi_assert_internal(page->xthread_free == 0);
667 mi_assert_internal(page->next == NULL);
668 mi_assert_internal(page->prev == NULL);
669 mi_assert_internal(page->retire_expire == 0);
670 mi_assert_internal(!mi_page_has_aligned(page));
671 #if (MI_ENCODE_FREELIST)
672 mi_assert_internal(page->keys[0] != 0);
673 mi_assert_internal(page->keys[1] != 0);
674 #endif
675 mi_assert_expensive(mi_page_is_valid_init(page));
676
677 // initialize an initial free list
678 mi_page_extend_free(heap,page,tld);
679 mi_assert(mi_page_immediate_available(page));
680}
681
682
683/* -----------------------------------------------------------
684 Find pages with free blocks
685-------------------------------------------------------------*/
686
687// Find a page with free blocks of `page->block_size`.
688static mi_page_t* mi_page_queue_find_free_ex(mi_heap_t* heap, mi_page_queue_t* pq, bool first_try)
689{
690 // search through the pages in "next fit" order
691 size_t count = 0;
692 mi_page_t* page = pq->first;
693 while (page != NULL)
694 {
695 mi_page_t* next = page->next; // remember next
696 count++;
697
698 // 0. collect freed blocks by us and other threads
699 _mi_page_free_collect(page, false);
700
701 // 1. if the page contains free blocks, we are done
702 if (mi_page_immediate_available(page)) {
703 break; // pick this one
704 }
705
706 // 2. Try to extend
707 if (page->capacity < page->reserved) {
708 mi_page_extend_free(heap, page, heap->tld);
709 mi_assert_internal(mi_page_immediate_available(page));
710 break;
711 }
712
713 // 3. If the page is completely full, move it to the `mi_pages_full`
714 // queue so we don't visit long-lived pages too often.
715 mi_assert_internal(!mi_page_is_in_full(page) && !mi_page_immediate_available(page));
716 mi_page_to_full(page, pq);
717
718 page = next;
719 } // for each page
720
721 mi_heap_stat_counter_increase(heap, searches, count);
722
723 if (page == NULL) {
724 _mi_heap_collect_retired(heap, false); // perhaps make a page available?
725 page = mi_page_fresh(heap, pq);
726 if (page == NULL && first_try) {
727 // out-of-memory _or_ an abandoned page with free blocks was reclaimed, try once again
728 page = mi_page_queue_find_free_ex(heap, pq, false);
729 }
730 }
731 else {
732 mi_assert(pq->first == page);
733 page->retire_expire = 0;
734 }
735 mi_assert_internal(page == NULL || mi_page_immediate_available(page));
736 return page;
737}
738
739
740
741// Find a page with free blocks of `size`.
742static inline mi_page_t* mi_find_free_page(mi_heap_t* heap, size_t size) {
743 mi_page_queue_t* pq = mi_page_queue(heap,size);
744 mi_page_t* page = pq->first;
745 if (page != NULL) {
746 #if (MI_SECURE>=3) // in secure mode, we extend half the time to increase randomness
747 if (page->capacity < page->reserved && ((_mi_heap_random_next(heap) & 1) == 1)) {
748 mi_page_extend_free(heap, page, heap->tld);
749 mi_assert_internal(mi_page_immediate_available(page));
750 }
751 else
752 #endif
753 {
754 _mi_page_free_collect(page,false);
755 }
756
757 if (mi_page_immediate_available(page)) {
758 page->retire_expire = 0;
759 return page; // fast path
760 }
761 }
762 return mi_page_queue_find_free_ex(heap, pq, true);
763}
764
765
766/* -----------------------------------------------------------
767 Users can register a deferred free function called
768 when the `free` list is empty. Since the `local_free`
769 is separate this is deterministically called after
770 a certain number of allocations.
771----------------------------------------------------------- */
772
773static mi_deferred_free_fun* volatile deferred_free = NULL;
774static _Atomic(void*) deferred_arg; // = NULL
775
776void _mi_deferred_free(mi_heap_t* heap, bool force) {
777 heap->tld->heartbeat++;
778 if (deferred_free != NULL && !heap->tld->recurse) {
779 heap->tld->recurse = true;
780 deferred_free(force, heap->tld->heartbeat, mi_atomic_load_ptr_relaxed(void,&deferred_arg));
781 heap->tld->recurse = false;
782 }
783}
784
785void mi_register_deferred_free(mi_deferred_free_fun* fn, void* arg) mi_attr_noexcept {
786 deferred_free = fn;
787 mi_atomic_store_ptr_release(void,&deferred_arg, arg);
788}
789
790
791/* -----------------------------------------------------------
792 General allocation
793----------------------------------------------------------- */
794
795// Large and huge page allocation.
796// Huge pages are allocated directly without being in a queue.
797// Because huge pages contain just one block, and the segment contains
798// just that page, we always treat them as abandoned and any thread
799// that frees the block can free the whole page and segment directly.
800static mi_page_t* mi_large_huge_page_alloc(mi_heap_t* heap, size_t size) {
801 size_t block_size = _mi_os_good_alloc_size(size);
802 mi_assert_internal(mi_bin(block_size) == MI_BIN_HUGE);
803 bool is_huge = (block_size > MI_LARGE_OBJ_SIZE_MAX);
804 mi_page_queue_t* pq = (is_huge ? NULL : mi_page_queue(heap, block_size));
805 mi_page_t* page = mi_page_fresh_alloc(heap, pq, block_size);
806 if (page != NULL) {
807 mi_assert_internal(mi_page_immediate_available(page));
808
809 if (pq == NULL) {
810 // huge pages are directly abandoned
811 mi_assert_internal(_mi_page_segment(page)->kind == MI_SEGMENT_HUGE);
812 mi_assert_internal(_mi_page_segment(page)->used==1);
813 mi_assert_internal(_mi_page_segment(page)->thread_id==0); // abandoned, not in the huge queue
814 mi_page_set_heap(page, NULL);
815 }
816 else {
817 mi_assert_internal(_mi_page_segment(page)->kind != MI_SEGMENT_HUGE);
818 }
819
820 const size_t bsize = mi_page_usable_block_size(page); // note: not `mi_page_block_size` to account for padding
821 if (bsize <= MI_LARGE_OBJ_SIZE_MAX) {
822 mi_heap_stat_increase(heap, large, bsize);
823 mi_heap_stat_counter_increase(heap, large_count, 1);
824 }
825 else {
826 mi_heap_stat_increase(heap, huge, bsize);
827 mi_heap_stat_counter_increase(heap, huge_count, 1);
828 }
829 }
830 return page;
831}
832
833
834// Allocate a page
835// Note: in debug mode the size includes MI_PADDING_SIZE and might have overflowed.
836static mi_page_t* mi_find_page(mi_heap_t* heap, size_t size) mi_attr_noexcept {
837 // huge allocation?
838 const size_t req_size = size - MI_PADDING_SIZE; // correct for padding_size in case of an overflow on `size`
839 if mi_unlikely(req_size > (MI_MEDIUM_OBJ_SIZE_MAX - MI_PADDING_SIZE)) {
840 if mi_unlikely(req_size > PTRDIFF_MAX) { // we don't allocate more than PTRDIFF_MAX (see <https://sourceware.org/ml/libc-announce/2019/msg00001.html>)
841 _mi_error_message(EOVERFLOW, "allocation request is too large (%zu bytes)\n", req_size);
842 return NULL;
843 }
844 else {
845 return mi_large_huge_page_alloc(heap,size);
846 }
847 }
848 else {
849 // otherwise find a page with free blocks in our size segregated queues
850 mi_assert_internal(size >= MI_PADDING_SIZE);
851 return mi_find_free_page(heap, size);
852 }
853}
854
855// Generic allocation routine if the fast path (`alloc.c:mi_page_malloc`) does not succeed.
856// Note: in debug mode the size includes MI_PADDING_SIZE and might have overflowed.
857void* _mi_malloc_generic(mi_heap_t* heap, size_t size, bool zero) mi_attr_noexcept
858{
859 mi_assert_internal(heap != NULL);
860
861 // initialize if necessary
862 if mi_unlikely(!mi_heap_is_initialized(heap)) {
863 mi_thread_init(); // calls `_mi_heap_init` in turn
864 heap = mi_get_default_heap();
865 if mi_unlikely(!mi_heap_is_initialized(heap)) { return NULL; }
866 }
867 mi_assert_internal(mi_heap_is_initialized(heap));
868
869 // call potential deferred free routines
870 _mi_deferred_free(heap, false);
871
872 // free delayed frees from other threads (but skip contended ones)
873 _mi_heap_delayed_free_partial(heap);
874
875 // find (or allocate) a page of the right size
876 mi_page_t* page = mi_find_page(heap, size);
877 if mi_unlikely(page == NULL) { // first time out of memory, try to collect and retry the allocation once more
878 mi_heap_collect(heap, true /* force */);
879 page = mi_find_page(heap, size);
880 }
881
882 if mi_unlikely(page == NULL) { // out of memory
883 const size_t req_size = size - MI_PADDING_SIZE; // correct for padding_size in case of an overflow on `size`
884 _mi_error_message(ENOMEM, "unable to allocate memory (%zu bytes)\n", req_size);
885 return NULL;
886 }
887
888 mi_assert_internal(mi_page_immediate_available(page));
889 mi_assert_internal(mi_page_block_size(page) >= size);
890
891 // and try again, this time succeeding! (i.e. this should never recurse through _mi_page_malloc)
892 if mi_unlikely(zero && page->xblock_size == 0) {
893 // note: we cannot call _mi_page_malloc with zeroing for huge blocks; we zero it afterwards in that case.
894 void* p = _mi_page_malloc(heap, page, size, false);
895 mi_assert_internal(p != NULL);
896 _mi_memzero_aligned(p, mi_page_usable_block_size(page));
897 return p;
898 }
899 else {
900 return _mi_page_malloc(heap, page, size, zero);
901 }
902}
903