Debian Codegraph @

Objects/mimalloc/page.c

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