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 | return true; |
70 | } |
71 | |
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 | |
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 | |
126 | void _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 | |
132 | bool _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. |
167 | static 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 | |
203 | void _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 |
243 | void _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 |
257 | static 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 |
273 | static 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 | ----------------------------------------------------------- */ |
286 | void _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 |
293 | bool _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 |
323 | void _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 | |
337 | static 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. |
352 | void _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 |
382 | void _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. |
414 | void _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. |
447 | void _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 | |
485 | 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) { |
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 | |
542 | 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) |
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?) |
584 | static 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 |
635 | static 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`. |
688 | static 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`. |
742 | static 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 | |
773 | static mi_deferred_free_fun* volatile deferred_free = NULL; |
774 | static _Atomic(void*) deferred_arg; // = NULL |
775 | |
776 | void _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 | |
785 | void 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. |
800 | static 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. |
836 | static 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. |
857 | void* _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 | |