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