1/* ----------------------------------------------------------------------------
2Copyright (c) 2018-2020, Microsoft Research, Daan Leijen
3This is free software; you can redistribute it and/or modify it under the
4terms of the MIT license. A copy of the license can be found in the file
5"LICENSE" at the root of this distribution.
6-----------------------------------------------------------------------------*/
7#include "mimalloc.h"
8#include "mimalloc-internal.h"
9#include "mimalloc-atomic.h"
10
11#include <string.h> // memset
12#include <stdio.h>
13
14#define MI_PAGE_HUGE_ALIGN (256*1024)
15
16static void mi_segment_delayed_decommit(mi_segment_t* segment, bool force, mi_stats_t* stats);
17
18
19// -------------------------------------------------------------------
20// commit mask
21// -------------------------------------------------------------------
22
23static bool mi_commit_mask_all_set(const mi_commit_mask_t* commit, const mi_commit_mask_t* cm) {
24 for (size_t i = 0; i < MI_COMMIT_MASK_FIELD_COUNT; i++) {
25 if ((commit->mask[i] & cm->mask[i]) != cm->mask[i]) return false;
26 }
27 return true;
28}
29
30static bool mi_commit_mask_any_set(const mi_commit_mask_t* commit, const mi_commit_mask_t* cm) {
31 for (size_t i = 0; i < MI_COMMIT_MASK_FIELD_COUNT; i++) {
32 if ((commit->mask[i] & cm->mask[i]) != 0) return true;
33 }
34 return false;
35}
36
37static void mi_commit_mask_create_intersect(const mi_commit_mask_t* commit, const mi_commit_mask_t* cm, mi_commit_mask_t* res) {
38 for (size_t i = 0; i < MI_COMMIT_MASK_FIELD_COUNT; i++) {
39 res->mask[i] = (commit->mask[i] & cm->mask[i]);
40 }
41}
42
43static void mi_commit_mask_clear(mi_commit_mask_t* res, const mi_commit_mask_t* cm) {
44 for (size_t i = 0; i < MI_COMMIT_MASK_FIELD_COUNT; i++) {
45 res->mask[i] &= ~(cm->mask[i]);
46 }
47}
48
49static void mi_commit_mask_set(mi_commit_mask_t* res, const mi_commit_mask_t* cm) {
50 for (size_t i = 0; i < MI_COMMIT_MASK_FIELD_COUNT; i++) {
51 res->mask[i] |= cm->mask[i];
52 }
53}
54
55static void mi_commit_mask_create(size_t bitidx, size_t bitcount, mi_commit_mask_t* cm) {
56 mi_assert_internal(bitidx < MI_COMMIT_MASK_BITS);
57 mi_assert_internal((bitidx + bitcount) <= MI_COMMIT_MASK_BITS);
58 if (bitcount == MI_COMMIT_MASK_BITS) {
59 mi_assert_internal(bitidx==0);
60 mi_commit_mask_create_full(cm);
61 }
62 else if (bitcount == 0) {
63 mi_commit_mask_create_empty(cm);
64 }
65 else {
66 mi_commit_mask_create_empty(cm);
67 size_t i = bitidx / MI_COMMIT_MASK_FIELD_BITS;
68 size_t ofs = bitidx % MI_COMMIT_MASK_FIELD_BITS;
69 while (bitcount > 0) {
70 mi_assert_internal(i < MI_COMMIT_MASK_FIELD_COUNT);
71 size_t avail = MI_COMMIT_MASK_FIELD_BITS - ofs;
72 size_t count = (bitcount > avail ? avail : bitcount);
73 size_t mask = (count >= MI_COMMIT_MASK_FIELD_BITS ? ~((size_t)0) : (((size_t)1 << count) - 1) << ofs);
74 cm->mask[i] = mask;
75 bitcount -= count;
76 ofs = 0;
77 i++;
78 }
79 }
80}
81
82size_t _mi_commit_mask_committed_size(const mi_commit_mask_t* cm, size_t total) {
83 mi_assert_internal((total%MI_COMMIT_MASK_BITS)==0);
84 size_t count = 0;
85 for (size_t i = 0; i < MI_COMMIT_MASK_FIELD_COUNT; i++) {
86 size_t mask = cm->mask[i];
87 if (~mask == 0) {
88 count += MI_COMMIT_MASK_FIELD_BITS;
89 }
90 else {
91 for (; mask != 0; mask >>= 1) { // todo: use popcount
92 if ((mask&1)!=0) count++;
93 }
94 }
95 }
96 // we use total since for huge segments each commit bit may represent a larger size
97 return ((total / MI_COMMIT_MASK_BITS) * count);
98}
99
100
101size_t _mi_commit_mask_next_run(const mi_commit_mask_t* cm, size_t* idx) {
102 size_t i = (*idx) / MI_COMMIT_MASK_FIELD_BITS;
103 size_t ofs = (*idx) % MI_COMMIT_MASK_FIELD_BITS;
104 size_t mask = 0;
105 // find first ones
106 while (i < MI_COMMIT_MASK_FIELD_COUNT) {
107 mask = cm->mask[i];
108 mask >>= ofs;
109 if (mask != 0) {
110 while ((mask&1) == 0) {
111 mask >>= 1;
112 ofs++;
113 }
114 break;
115 }
116 i++;
117 ofs = 0;
118 }
119 if (i >= MI_COMMIT_MASK_FIELD_COUNT) {
120 // not found
121 *idx = MI_COMMIT_MASK_BITS;
122 return 0;
123 }
124 else {
125 // found, count ones
126 size_t count = 0;
127 *idx = (i*MI_COMMIT_MASK_FIELD_BITS) + ofs;
128 do {
129 mi_assert_internal(ofs < MI_COMMIT_MASK_FIELD_BITS && (mask&1) == 1);
130 do {
131 count++;
132 mask >>= 1;
133 } while ((mask&1) == 1);
134 if ((((*idx + count) % MI_COMMIT_MASK_FIELD_BITS) == 0)) {
135 i++;
136 if (i >= MI_COMMIT_MASK_FIELD_COUNT) break;
137 mask = cm->mask[i];
138 ofs = 0;
139 }
140 } while ((mask&1) == 1);
141 mi_assert_internal(count > 0);
142 return count;
143 }
144}
145
146
147/* --------------------------------------------------------------------------------
148 Segment allocation
149
150 If a thread ends, it "abandons" pages with used blocks
151 and there is an abandoned segment list whose segments can
152 be reclaimed by still running threads, much like work-stealing.
153-------------------------------------------------------------------------------- */
154
155
156/* -----------------------------------------------------------
157 Slices
158----------------------------------------------------------- */
159
160
161static const mi_slice_t* mi_segment_slices_end(const mi_segment_t* segment) {
162 return &segment->slices[segment->slice_entries];
163}
164
165static uint8_t* mi_slice_start(const mi_slice_t* slice) {
166 mi_segment_t* segment = _mi_ptr_segment(slice);
167 mi_assert_internal(slice >= segment->slices && slice < mi_segment_slices_end(segment));
168 return ((uint8_t*)segment + ((slice - segment->slices)*MI_SEGMENT_SLICE_SIZE));
169}
170
171
172/* -----------------------------------------------------------
173 Bins
174----------------------------------------------------------- */
175// Use bit scan forward to quickly find the first zero bit if it is available
176
177static inline size_t mi_slice_bin8(size_t slice_count) {
178 if (slice_count<=1) return slice_count;
179 mi_assert_internal(slice_count <= MI_SLICES_PER_SEGMENT);
180 slice_count--;
181 size_t s = mi_bsr(slice_count); // slice_count > 1
182 if (s <= 2) return slice_count + 1;
183 size_t bin = ((s << 2) | ((slice_count >> (s - 2))&0x03)) - 4;
184 return bin;
185}
186
187static inline size_t mi_slice_bin(size_t slice_count) {
188 mi_assert_internal(slice_count*MI_SEGMENT_SLICE_SIZE <= MI_SEGMENT_SIZE);
189 mi_assert_internal(mi_slice_bin8(MI_SLICES_PER_SEGMENT) <= MI_SEGMENT_BIN_MAX);
190 size_t bin = mi_slice_bin8(slice_count);
191 mi_assert_internal(bin <= MI_SEGMENT_BIN_MAX);
192 return bin;
193}
194
195static inline size_t mi_slice_index(const mi_slice_t* slice) {
196 mi_segment_t* segment = _mi_ptr_segment(slice);
197 ptrdiff_t index = slice - segment->slices;
198 mi_assert_internal(index >= 0 && index < (ptrdiff_t)segment->slice_entries);
199 return index;
200}
201
202
203/* -----------------------------------------------------------
204 Slice span queues
205----------------------------------------------------------- */
206
207static void mi_span_queue_push(mi_span_queue_t* sq, mi_slice_t* slice) {
208 // todo: or push to the end?
209 mi_assert_internal(slice->prev == NULL && slice->next==NULL);
210 slice->prev = NULL; // paranoia
211 slice->next = sq->first;
212 sq->first = slice;
213 if (slice->next != NULL) slice->next->prev = slice;
214 else sq->last = slice;
215 slice->xblock_size = 0; // free
216}
217
218static mi_span_queue_t* mi_span_queue_for(size_t slice_count, mi_segments_tld_t* tld) {
219 size_t bin = mi_slice_bin(slice_count);
220 mi_span_queue_t* sq = &tld->spans[bin];
221 mi_assert_internal(sq->slice_count >= slice_count);
222 return sq;
223}
224
225static void mi_span_queue_delete(mi_span_queue_t* sq, mi_slice_t* slice) {
226 mi_assert_internal(slice->xblock_size==0 && slice->slice_count>0 && slice->slice_offset==0);
227 // should work too if the queue does not contain slice (which can happen during reclaim)
228 if (slice->prev != NULL) slice->prev->next = slice->next;
229 if (slice == sq->first) sq->first = slice->next;
230 if (slice->next != NULL) slice->next->prev = slice->prev;
231 if (slice == sq->last) sq->last = slice->prev;
232 slice->prev = NULL;
233 slice->next = NULL;
234 slice->xblock_size = 1; // no more free
235}
236
237
238/* -----------------------------------------------------------
239 Invariant checking
240----------------------------------------------------------- */
241
242static bool mi_slice_is_used(const mi_slice_t* slice) {
243 return (slice->xblock_size > 0);
244}
245
246
247#if (MI_DEBUG>=3)
248static bool mi_span_queue_contains(mi_span_queue_t* sq, mi_slice_t* slice) {
249 for (mi_slice_t* s = sq->first; s != NULL; s = s->next) {
250 if (s==slice) return true;
251 }
252 return false;
253}
254
255static bool mi_segment_is_valid(mi_segment_t* segment, mi_segments_tld_t* tld) {
256 mi_assert_internal(segment != NULL);
257 mi_assert_internal(_mi_ptr_cookie(segment) == segment->cookie);
258 mi_assert_internal(segment->abandoned <= segment->used);
259 mi_assert_internal(segment->thread_id == 0 || segment->thread_id == _mi_thread_id());
260 mi_assert_internal(mi_commit_mask_all_set(&segment->commit_mask, &segment->decommit_mask)); // can only decommit committed blocks
261 //mi_assert_internal(segment->segment_info_size % MI_SEGMENT_SLICE_SIZE == 0);
262 mi_slice_t* slice = &segment->slices[0];
263 const mi_slice_t* end = mi_segment_slices_end(segment);
264 size_t used_count = 0;
265 mi_span_queue_t* sq;
266 while(slice < end) {
267 mi_assert_internal(slice->slice_count > 0);
268 mi_assert_internal(slice->slice_offset == 0);
269 size_t index = mi_slice_index(slice);
270 size_t maxindex = (index + slice->slice_count >= segment->slice_entries ? segment->slice_entries : index + slice->slice_count) - 1;
271 if (mi_slice_is_used(slice)) { // a page in use, we need at least MAX_SLICE_OFFSET valid back offsets
272 used_count++;
273 for (size_t i = 0; i <= MI_MAX_SLICE_OFFSET && index + i <= maxindex; i++) {
274 mi_assert_internal(segment->slices[index + i].slice_offset == i*sizeof(mi_slice_t));
275 mi_assert_internal(i==0 || segment->slices[index + i].slice_count == 0);
276 mi_assert_internal(i==0 || segment->slices[index + i].xblock_size == 1);
277 }
278 // and the last entry as well (for coalescing)
279 const mi_slice_t* last = slice + slice->slice_count - 1;
280 if (last > slice && last < mi_segment_slices_end(segment)) {
281 mi_assert_internal(last->slice_offset == (slice->slice_count-1)*sizeof(mi_slice_t));
282 mi_assert_internal(last->slice_count == 0);
283 mi_assert_internal(last->xblock_size == 1);
284 }
285 }
286 else { // free range of slices; only last slice needs a valid back offset
287 mi_slice_t* last = &segment->slices[maxindex];
288 if (segment->kind != MI_SEGMENT_HUGE || slice->slice_count <= (segment->slice_entries - segment->segment_info_slices)) {
289 mi_assert_internal((uint8_t*)slice == (uint8_t*)last - last->slice_offset);
290 }
291 mi_assert_internal(slice == last || last->slice_count == 0 );
292 mi_assert_internal(last->xblock_size == 0 || (segment->kind==MI_SEGMENT_HUGE && last->xblock_size==1));
293 if (segment->kind != MI_SEGMENT_HUGE && segment->thread_id != 0) { // segment is not huge or abandoned
294 sq = mi_span_queue_for(slice->slice_count,tld);
295 mi_assert_internal(mi_span_queue_contains(sq,slice));
296 }
297 }
298 slice = &segment->slices[maxindex+1];
299 }
300 mi_assert_internal(slice == end);
301 mi_assert_internal(used_count == segment->used + 1);
302 return true;
303}
304#endif
305
306/* -----------------------------------------------------------
307 Segment size calculations
308----------------------------------------------------------- */
309
310static size_t mi_segment_info_size(mi_segment_t* segment) {
311 return segment->segment_info_slices * MI_SEGMENT_SLICE_SIZE;
312}
313
314static uint8_t* _mi_segment_page_start_from_slice(const mi_segment_t* segment, const mi_slice_t* slice, size_t xblock_size, size_t* page_size)
315{
316 ptrdiff_t idx = slice - segment->slices;
317 size_t psize = (size_t)slice->slice_count * MI_SEGMENT_SLICE_SIZE;
318 // make the start not OS page aligned for smaller blocks to avoid page/cache effects
319 size_t start_offset = (xblock_size >= MI_INTPTR_SIZE && xblock_size <= 1024 ? MI_MAX_ALIGN_GUARANTEE : 0);
320 if (page_size != NULL) { *page_size = psize - start_offset; }
321 return (uint8_t*)segment + ((idx*MI_SEGMENT_SLICE_SIZE) + start_offset);
322}
323
324// Start of the page available memory; can be used on uninitialized pages
325uint8_t* _mi_segment_page_start(const mi_segment_t* segment, const mi_page_t* page, size_t* page_size)
326{
327 const mi_slice_t* slice = mi_page_to_slice((mi_page_t*)page);
328 uint8_t* p = _mi_segment_page_start_from_slice(segment, slice, page->xblock_size, page_size);
329 mi_assert_internal(page->xblock_size > 0 || _mi_ptr_page(p) == page);
330 mi_assert_internal(_mi_ptr_segment(p) == segment);
331 return p;
332}
333
334
335static size_t mi_segment_calculate_slices(size_t required, size_t* pre_size, size_t* info_slices) {
336 size_t page_size = _mi_os_page_size();
337 size_t isize = _mi_align_up(sizeof(mi_segment_t), page_size);
338 size_t guardsize = 0;
339
340 if (MI_SECURE>0) {
341 // in secure mode, we set up a protected page in between the segment info
342 // and the page data (and one at the end of the segment)
343 guardsize = page_size;
344 required = _mi_align_up(required, page_size);
345 }
346
347 if (pre_size != NULL) *pre_size = isize;
348 isize = _mi_align_up(isize + guardsize, MI_SEGMENT_SLICE_SIZE);
349 if (info_slices != NULL) *info_slices = isize / MI_SEGMENT_SLICE_SIZE;
350 size_t segment_size = (required==0 ? MI_SEGMENT_SIZE : _mi_align_up( required + isize + guardsize, MI_SEGMENT_SLICE_SIZE) );
351 mi_assert_internal(segment_size % MI_SEGMENT_SLICE_SIZE == 0);
352 return (segment_size / MI_SEGMENT_SLICE_SIZE);
353}
354
355
356/* ----------------------------------------------------------------------------
357Segment caches
358We keep a small segment cache per thread to increase local
359reuse and avoid setting/clearing guard pages in secure mode.
360------------------------------------------------------------------------------- */
361
362static void mi_segments_track_size(long segment_size, mi_segments_tld_t* tld) {
363 if (segment_size>=0) _mi_stat_increase(&tld->stats->segments,1);
364 else _mi_stat_decrease(&tld->stats->segments,1);
365 tld->count += (segment_size >= 0 ? 1 : -1);
366 if (tld->count > tld->peak_count) tld->peak_count = tld->count;
367 tld->current_size += segment_size;
368 if (tld->current_size > tld->peak_size) tld->peak_size = tld->current_size;
369}
370
371static void mi_segment_os_free(mi_segment_t* segment, mi_segments_tld_t* tld) {
372 segment->thread_id = 0;
373 _mi_segment_map_freed_at(segment);
374 mi_segments_track_size(-((long)mi_segment_size(segment)),tld);
375 if (MI_SECURE>0) {
376 // _mi_os_unprotect(segment, mi_segment_size(segment)); // ensure no more guard pages are set
377 // unprotect the guard pages; we cannot just unprotect the whole segment size as part may be decommitted
378 size_t os_pagesize = _mi_os_page_size();
379 _mi_os_unprotect((uint8_t*)segment + mi_segment_info_size(segment) - os_pagesize, os_pagesize);
380 uint8_t* end = (uint8_t*)segment + mi_segment_size(segment) - os_pagesize;
381 _mi_os_unprotect(end, os_pagesize);
382 }
383
384 // purge delayed decommits now? (no, leave it to the cache)
385 // mi_segment_delayed_decommit(segment,true,tld->stats);
386
387 // _mi_os_free(segment, mi_segment_size(segment), /*segment->memid,*/ tld->stats);
388 const size_t size = mi_segment_size(segment);
389 if (size != MI_SEGMENT_SIZE || !_mi_segment_cache_push(segment, size, segment->memid, &segment->commit_mask, &segment->decommit_mask, segment->mem_is_large, segment->mem_is_pinned, tld->os)) {
390 const size_t csize = _mi_commit_mask_committed_size(&segment->commit_mask, size);
391 if (csize > 0 && !segment->mem_is_pinned) _mi_stat_decrease(&_mi_stats_main.committed, csize);
392 _mi_abandoned_await_readers(); // wait until safe to free
393 _mi_arena_free(segment, mi_segment_size(segment), segment->memid, segment->mem_is_pinned /* pretend not committed to not double count decommits */, tld->os);
394 }
395}
396
397// called by threads that are terminating
398void _mi_segment_thread_collect(mi_segments_tld_t* tld) {
399 MI_UNUSED(tld);
400 // nothing to do
401}
402
403
404/* -----------------------------------------------------------
405 Span management
406----------------------------------------------------------- */
407
408static void mi_segment_commit_mask(mi_segment_t* segment, bool conservative, uint8_t* p, size_t size, uint8_t** start_p, size_t* full_size, mi_commit_mask_t* cm) {
409 mi_assert_internal(_mi_ptr_segment(p) == segment);
410 mi_assert_internal(segment->kind != MI_SEGMENT_HUGE);
411 mi_commit_mask_create_empty(cm);
412 if (size == 0 || size > MI_SEGMENT_SIZE || segment->kind == MI_SEGMENT_HUGE) return;
413 const size_t segstart = mi_segment_info_size(segment);
414 const size_t segsize = mi_segment_size(segment);
415 if (p >= (uint8_t*)segment + segsize) return;
416
417 size_t pstart = (p - (uint8_t*)segment);
418 mi_assert_internal(pstart + size <= segsize);
419
420 size_t start;
421 size_t end;
422 if (conservative) {
423 // decommit conservative
424 start = _mi_align_up(pstart, MI_COMMIT_SIZE);
425 end = _mi_align_down(pstart + size, MI_COMMIT_SIZE);
426 mi_assert_internal(start >= segstart);
427 mi_assert_internal(end <= segsize);
428 }
429 else {
430 // commit liberal
431 start = _mi_align_down(pstart, MI_MINIMAL_COMMIT_SIZE);
432 end = _mi_align_up(pstart + size, MI_MINIMAL_COMMIT_SIZE);
433 }
434 if (pstart >= segstart && start < segstart) { // note: the mask is also calculated for an initial commit of the info area
435 start = segstart;
436 }
437 if (end > segsize) {
438 end = segsize;
439 }
440
441 mi_assert_internal(start <= pstart && (pstart + size) <= end);
442 mi_assert_internal(start % MI_COMMIT_SIZE==0 && end % MI_COMMIT_SIZE == 0);
443 *start_p = (uint8_t*)segment + start;
444 *full_size = (end > start ? end - start : 0);
445 if (*full_size == 0) return;
446
447 size_t bitidx = start / MI_COMMIT_SIZE;
448 mi_assert_internal(bitidx < MI_COMMIT_MASK_BITS);
449
450 size_t bitcount = *full_size / MI_COMMIT_SIZE; // can be 0
451 if (bitidx + bitcount > MI_COMMIT_MASK_BITS) {
452 _mi_warning_message("commit mask overflow: idx=%zu count=%zu start=%zx end=%zx p=0x%p size=%zu fullsize=%zu\n", bitidx, bitcount, start, end, p, size, *full_size);
453 }
454 mi_assert_internal((bitidx + bitcount) <= MI_COMMIT_MASK_BITS);
455 mi_commit_mask_create(bitidx, bitcount, cm);
456}
457
458
459static bool mi_segment_commitx(mi_segment_t* segment, bool commit, uint8_t* p, size_t size, mi_stats_t* stats) {
460 mi_assert_internal(mi_commit_mask_all_set(&segment->commit_mask, &segment->decommit_mask));
461
462 // try to commit in at least MI_MINIMAL_COMMIT_SIZE sizes.
463 /*
464 if (commit && size > 0) {
465 const size_t csize = _mi_align_up(size, MI_MINIMAL_COMMIT_SIZE);
466 if (p + csize <= mi_segment_end(segment)) {
467 size = csize;
468 }
469 }
470 */
471 // commit liberal, but decommit conservative
472 uint8_t* start = NULL;
473 size_t full_size = 0;
474 mi_commit_mask_t mask;
475 mi_segment_commit_mask(segment, !commit/*conservative*/, p, size, &start, &full_size, &mask);
476 if (mi_commit_mask_is_empty(&mask) || full_size==0) return true;
477
478 if (commit && !mi_commit_mask_all_set(&segment->commit_mask, &mask)) {
479 bool is_zero = false;
480 mi_commit_mask_t cmask;
481 mi_commit_mask_create_intersect(&segment->commit_mask, &mask, &cmask);
482 _mi_stat_decrease(&_mi_stats_main.committed, _mi_commit_mask_committed_size(&cmask, MI_SEGMENT_SIZE)); // adjust for overlap
483 if (!_mi_os_commit(start,full_size,&is_zero,stats)) return false;
484 mi_commit_mask_set(&segment->commit_mask, &mask);
485 }
486 else if (!commit && mi_commit_mask_any_set(&segment->commit_mask, &mask)) {
487 mi_assert_internal((void*)start != (void*)segment);
488 //mi_assert_internal(mi_commit_mask_all_set(&segment->commit_mask, &mask));
489
490 mi_commit_mask_t cmask;
491 mi_commit_mask_create_intersect(&segment->commit_mask, &mask, &cmask);
492 _mi_stat_increase(&_mi_stats_main.committed, full_size - _mi_commit_mask_committed_size(&cmask, MI_SEGMENT_SIZE)); // adjust for overlap
493 if (segment->allow_decommit) {
494 _mi_os_decommit(start, full_size, stats); // ok if this fails
495 }
496 mi_commit_mask_clear(&segment->commit_mask, &mask);
497 }
498 // increase expiration of reusing part of the delayed decommit
499 if (commit && mi_commit_mask_any_set(&segment->decommit_mask, &mask)) {
500 segment->decommit_expire = _mi_clock_now() + mi_option_get(mi_option_decommit_delay);
501 }
502 // always undo delayed decommits
503 mi_commit_mask_clear(&segment->decommit_mask, &mask);
504 return true;
505}
506
507static bool mi_segment_ensure_committed(mi_segment_t* segment, uint8_t* p, size_t size, mi_stats_t* stats) {
508 mi_assert_internal(mi_commit_mask_all_set(&segment->commit_mask, &segment->decommit_mask));
509 // note: assumes commit_mask is always full for huge segments as otherwise the commit mask bits can overflow
510 if (mi_commit_mask_is_full(&segment->commit_mask) && mi_commit_mask_is_empty(&segment->decommit_mask)) return true; // fully committed
511 return mi_segment_commitx(segment,true,p,size,stats);
512}
513
514static void mi_segment_perhaps_decommit(mi_segment_t* segment, uint8_t* p, size_t size, mi_stats_t* stats) {
515 if (!segment->allow_decommit) return;
516 if (mi_option_get(mi_option_decommit_delay) == 0) {
517 mi_segment_commitx(segment, false, p, size, stats);
518 }
519 else {
520 // register for future decommit in the decommit mask
521 uint8_t* start = NULL;
522 size_t full_size = 0;
523 mi_commit_mask_t mask;
524 mi_segment_commit_mask(segment, true /*conservative*/, p, size, &start, &full_size, &mask);
525 if (mi_commit_mask_is_empty(&mask) || full_size==0) return;
526
527 // update delayed commit
528 mi_assert_internal(segment->decommit_expire > 0 || mi_commit_mask_is_empty(&segment->decommit_mask));
529 mi_commit_mask_t cmask;
530 mi_commit_mask_create_intersect(&segment->commit_mask, &mask, &cmask); // only decommit what is committed; span_free may try to decommit more
531 mi_commit_mask_set(&segment->decommit_mask, &cmask);
532 mi_msecs_t now = _mi_clock_now();
533 if (segment->decommit_expire == 0) {
534 // no previous decommits, initialize now
535 segment->decommit_expire = now + mi_option_get(mi_option_decommit_delay);
536 }
537 else if (segment->decommit_expire <= now) {
538 // previous decommit mask already expired
539 // mi_segment_delayed_decommit(segment, true, stats);
540 segment->decommit_expire = now + mi_option_get(mi_option_decommit_extend_delay); // (mi_option_get(mi_option_decommit_delay) / 8); // wait a tiny bit longer in case there is a series of free's
541 }
542 else {
543 // previous decommit mask is not yet expired, increase the expiration by a bit.
544 segment->decommit_expire += mi_option_get(mi_option_decommit_extend_delay);
545 }
546 }
547}
548
549static void mi_segment_delayed_decommit(mi_segment_t* segment, bool force, mi_stats_t* stats) {
550 if (!segment->allow_decommit || mi_commit_mask_is_empty(&segment->decommit_mask)) return;
551 mi_msecs_t now = _mi_clock_now();
552 if (!force && now < segment->decommit_expire) return;
553
554 mi_commit_mask_t mask = segment->decommit_mask;
555 segment->decommit_expire = 0;
556 mi_commit_mask_create_empty(&segment->decommit_mask);
557
558 size_t idx;
559 size_t count;
560 mi_commit_mask_foreach(&mask, idx, count) {
561 // if found, decommit that sequence
562 if (count > 0) {
563 uint8_t* p = (uint8_t*)segment + (idx*MI_COMMIT_SIZE);
564 size_t size = count * MI_COMMIT_SIZE;
565 mi_segment_commitx(segment, false, p, size, stats);
566 }
567 }
568 mi_commit_mask_foreach_end()
569 mi_assert_internal(mi_commit_mask_is_empty(&segment->decommit_mask));
570}
571
572
573static bool mi_segment_is_abandoned(mi_segment_t* segment) {
574 return (segment->thread_id == 0);
575}
576
577// note: can be called on abandoned segments
578static void mi_segment_span_free(mi_segment_t* segment, size_t slice_index, size_t slice_count, mi_segments_tld_t* tld) {
579 mi_assert_internal(slice_index < segment->slice_entries);
580 mi_span_queue_t* sq = (segment->kind == MI_SEGMENT_HUGE || mi_segment_is_abandoned(segment)
581 ? NULL : mi_span_queue_for(slice_count,tld));
582 if (slice_count==0) slice_count = 1;
583 mi_assert_internal(slice_index + slice_count - 1 < segment->slice_entries);
584
585 // set first and last slice (the intermediates can be undetermined)
586 mi_slice_t* slice = &segment->slices[slice_index];
587 slice->slice_count = (uint32_t)slice_count;
588 mi_assert_internal(slice->slice_count == slice_count); // no overflow?
589 slice->slice_offset = 0;
590 if (slice_count > 1) {
591 mi_slice_t* last = &segment->slices[slice_index + slice_count - 1];
592 last->slice_count = 0;
593 last->slice_offset = (uint32_t)(sizeof(mi_page_t)*(slice_count - 1));
594 last->xblock_size = 0;
595 }
596
597 // perhaps decommit
598 mi_segment_perhaps_decommit(segment,mi_slice_start(slice),slice_count*MI_SEGMENT_SLICE_SIZE,tld->stats);
599
600 // and push it on the free page queue (if it was not a huge page)
601 if (sq != NULL) mi_span_queue_push( sq, slice );
602 else slice->xblock_size = 0; // mark huge page as free anyways
603}
604
605/*
606// called from reclaim to add existing free spans
607static void mi_segment_span_add_free(mi_slice_t* slice, mi_segments_tld_t* tld) {
608 mi_segment_t* segment = _mi_ptr_segment(slice);
609 mi_assert_internal(slice->xblock_size==0 && slice->slice_count>0 && slice->slice_offset==0);
610 size_t slice_index = mi_slice_index(slice);
611 mi_segment_span_free(segment,slice_index,slice->slice_count,tld);
612}
613*/
614
615static void mi_segment_span_remove_from_queue(mi_slice_t* slice, mi_segments_tld_t* tld) {
616 mi_assert_internal(slice->slice_count > 0 && slice->slice_offset==0 && slice->xblock_size==0);
617 mi_assert_internal(_mi_ptr_segment(slice)->kind != MI_SEGMENT_HUGE);
618 mi_span_queue_t* sq = mi_span_queue_for(slice->slice_count, tld);
619 mi_span_queue_delete(sq, slice);
620}
621
622// note: can be called on abandoned segments
623static mi_slice_t* mi_segment_span_free_coalesce(mi_slice_t* slice, mi_segments_tld_t* tld) {
624 mi_assert_internal(slice != NULL && slice->slice_count > 0 && slice->slice_offset == 0);
625 mi_segment_t* segment = _mi_ptr_segment(slice);
626 bool is_abandoned = mi_segment_is_abandoned(segment);
627
628 // for huge pages, just mark as free but don't add to the queues
629 if (segment->kind == MI_SEGMENT_HUGE) {
630 mi_assert_internal(segment->used == 1); // decreased right after this call in `mi_segment_page_clear`
631 slice->xblock_size = 0; // mark as free anyways
632 // we should mark the last slice `xblock_size=0` now to maintain invariants but we skip it to
633 // avoid a possible cache miss (and the segment is about to be freed)
634 return slice;
635 }
636
637 // otherwise coalesce the span and add to the free span queues
638 size_t slice_count = slice->slice_count;
639 mi_slice_t* next = slice + slice->slice_count;
640 mi_assert_internal(next <= mi_segment_slices_end(segment));
641 if (next < mi_segment_slices_end(segment) && next->xblock_size==0) {
642 // free next block -- remove it from free and merge
643 mi_assert_internal(next->slice_count > 0 && next->slice_offset==0);
644 slice_count += next->slice_count; // extend
645 if (!is_abandoned) { mi_segment_span_remove_from_queue(next, tld); }
646 }
647 if (slice > segment->slices) {
648 mi_slice_t* prev = mi_slice_first(slice - 1);
649 mi_assert_internal(prev >= segment->slices);
650 if (prev->xblock_size==0) {
651 // free previous slice -- remove it from free and merge
652 mi_assert_internal(prev->slice_count > 0 && prev->slice_offset==0);
653 slice_count += prev->slice_count;
654 if (!is_abandoned) { mi_segment_span_remove_from_queue(prev, tld); }
655 slice = prev;
656 }
657 }
658
659 // and add the new free page
660 mi_segment_span_free(segment, mi_slice_index(slice), slice_count, tld);
661 return slice;
662}
663
664
665static void mi_segment_slice_split(mi_segment_t* segment, mi_slice_t* slice, size_t slice_count, mi_segments_tld_t* tld) {
666 mi_assert_internal(_mi_ptr_segment(slice)==segment);
667 mi_assert_internal(slice->slice_count >= slice_count);
668 mi_assert_internal(slice->xblock_size > 0); // no more in free queue
669 if (slice->slice_count <= slice_count) return;
670 mi_assert_internal(segment->kind != MI_SEGMENT_HUGE);
671 size_t next_index = mi_slice_index(slice) + slice_count;
672 size_t next_count = slice->slice_count - slice_count;
673 mi_segment_span_free(segment, next_index, next_count, tld);
674 slice->slice_count = (uint32_t)slice_count;
675}
676
677// Note: may still return NULL if committing the memory failed
678static mi_page_t* mi_segment_span_allocate(mi_segment_t* segment, size_t slice_index, size_t slice_count, mi_segments_tld_t* tld) {
679 mi_assert_internal(slice_index < segment->slice_entries);
680 mi_slice_t* slice = &segment->slices[slice_index];
681 mi_assert_internal(slice->xblock_size==0 || slice->xblock_size==1);
682
683 // commit before changing the slice data
684 if (!mi_segment_ensure_committed(segment, _mi_segment_page_start_from_slice(segment, slice, 0, NULL), slice_count * MI_SEGMENT_SLICE_SIZE, tld->stats)) {
685 return NULL; // commit failed!
686 }
687
688 // convert the slices to a page
689 slice->slice_offset = 0;
690 slice->slice_count = (uint32_t)slice_count;
691 mi_assert_internal(slice->slice_count == slice_count);
692 const size_t bsize = slice_count * MI_SEGMENT_SLICE_SIZE;
693 slice->xblock_size = (uint32_t)(bsize >= MI_HUGE_BLOCK_SIZE ? MI_HUGE_BLOCK_SIZE : bsize);
694 mi_page_t* page = mi_slice_to_page(slice);
695 mi_assert_internal(mi_page_block_size(page) == bsize);
696
697 // set slice back pointers for the first MI_MAX_SLICE_OFFSET entries
698 size_t extra = slice_count-1;
699 if (extra > MI_MAX_SLICE_OFFSET) extra = MI_MAX_SLICE_OFFSET;
700 if (slice_index + extra >= segment->slice_entries) extra = segment->slice_entries - slice_index - 1; // huge objects may have more slices than avaiable entries in the segment->slices
701 slice++;
702 for (size_t i = 1; i <= extra; i++, slice++) {
703 slice->slice_offset = (uint32_t)(sizeof(mi_slice_t)*i);
704 slice->slice_count = 0;
705 slice->xblock_size = 1;
706 }
707
708 // and also for the last one (if not set already) (the last one is needed for coalescing)
709 // note: the cast is needed for ubsan since the index can be larger than MI_SLICES_PER_SEGMENT for huge allocations (see #543)
710 mi_slice_t* last = &((mi_slice_t*)segment->slices)[slice_index + slice_count - 1];
711 if (last < mi_segment_slices_end(segment) && last >= slice) {
712 last->slice_offset = (uint32_t)(sizeof(mi_slice_t)*(slice_count-1));
713 last->slice_count = 0;
714 last->xblock_size = 1;
715 }
716
717 // and initialize the page
718 page->is_reset = false;
719 page->is_committed = true;
720 segment->used++;
721 return page;
722}
723
724static mi_page_t* mi_segments_page_find_and_allocate(size_t slice_count, mi_arena_id_t req_arena_id, mi_segments_tld_t* tld) {
725 mi_assert_internal(slice_count*MI_SEGMENT_SLICE_SIZE <= MI_LARGE_OBJ_SIZE_MAX);
726 // search from best fit up
727 mi_span_queue_t* sq = mi_span_queue_for(slice_count, tld);
728 if (slice_count == 0) slice_count = 1;
729 while (sq <= &tld->spans[MI_SEGMENT_BIN_MAX]) {
730 for (mi_slice_t* slice = sq->first; slice != NULL; slice = slice->next) {
731 if (slice->slice_count >= slice_count) {
732 // found one
733 mi_segment_t* segment = _mi_ptr_segment(slice);
734 if (_mi_arena_memid_is_suitable(segment->memid, req_arena_id)) {
735 // found a suitable page span
736 mi_span_queue_delete(sq, slice);
737
738 if (slice->slice_count > slice_count) {
739 mi_segment_slice_split(segment, slice, slice_count, tld);
740 }
741 mi_assert_internal(slice != NULL && slice->slice_count == slice_count && slice->xblock_size > 0);
742 mi_page_t* page = mi_segment_span_allocate(segment, mi_slice_index(slice), slice->slice_count, tld);
743 if (page == NULL) {
744 // commit failed; return NULL but first restore the slice
745 mi_segment_span_free_coalesce(slice, tld);
746 return NULL;
747 }
748 return page;
749 }
750 }
751 }
752 sq++;
753 }
754 // could not find a page..
755 return NULL;
756}
757
758
759/* -----------------------------------------------------------
760 Segment allocation
761----------------------------------------------------------- */
762
763// Allocate a segment from the OS aligned to `MI_SEGMENT_SIZE` .
764static mi_segment_t* mi_segment_init(mi_segment_t* segment, size_t required, mi_arena_id_t req_arena_id, mi_segments_tld_t* tld, mi_os_tld_t* os_tld, mi_page_t** huge_page)
765{
766 mi_assert_internal((required==0 && huge_page==NULL) || (required>0 && huge_page != NULL));
767 mi_assert_internal((segment==NULL) || (segment!=NULL && required==0));
768 // calculate needed sizes first
769 size_t info_slices;
770 size_t pre_size;
771 const size_t segment_slices = mi_segment_calculate_slices(required, &pre_size, &info_slices);
772 const size_t slice_entries = (segment_slices > MI_SLICES_PER_SEGMENT ? MI_SLICES_PER_SEGMENT : segment_slices);
773 const size_t segment_size = segment_slices * MI_SEGMENT_SLICE_SIZE;
774
775 // Commit eagerly only if not the first N lazy segments (to reduce impact of many threads that allocate just a little)
776 const bool eager_delay = (// !_mi_os_has_overcommit() && // never delay on overcommit systems
777 _mi_current_thread_count() > 1 && // do not delay for the first N threads
778 tld->count < (size_t)mi_option_get(mi_option_eager_commit_delay));
779 const bool eager = !eager_delay && mi_option_is_enabled(mi_option_eager_commit);
780 bool commit = eager || (required > 0);
781
782 // Try to get from our cache first
783 bool is_zero = false;
784 const bool commit_info_still_good = (segment != NULL);
785 mi_commit_mask_t commit_mask;
786 mi_commit_mask_t decommit_mask;
787 if (segment != NULL) {
788 commit_mask = segment->commit_mask;
789 decommit_mask = segment->decommit_mask;
790 }
791 else {
792 mi_commit_mask_create_empty(&commit_mask);
793 mi_commit_mask_create_empty(&decommit_mask);
794 }
795 if (segment==NULL) {
796 // Allocate the segment from the OS
797 bool mem_large = (!eager_delay && (MI_SECURE==0)); // only allow large OS pages once we are no longer lazy
798 bool is_pinned = false;
799 size_t memid = 0;
800 segment = (mi_segment_t*)_mi_segment_cache_pop(segment_size, &commit_mask, &decommit_mask, &mem_large, &is_pinned, &is_zero, req_arena_id, &memid, os_tld);
801 if (segment==NULL) {
802 segment = (mi_segment_t*)_mi_arena_alloc_aligned(segment_size, MI_SEGMENT_SIZE, &commit, &mem_large, &is_pinned, &is_zero, req_arena_id, &memid, os_tld);
803 if (segment == NULL) return NULL; // failed to allocate
804 if (commit) {
805 mi_commit_mask_create_full(&commit_mask);
806 }
807 else {
808 mi_commit_mask_create_empty(&commit_mask);
809 }
810 }
811 mi_assert_internal(segment != NULL && (uintptr_t)segment % MI_SEGMENT_SIZE == 0);
812
813 const size_t commit_needed = _mi_divide_up(info_slices*MI_SEGMENT_SLICE_SIZE, MI_COMMIT_SIZE);
814 mi_assert_internal(commit_needed>0);
815 mi_commit_mask_t commit_needed_mask;
816 mi_commit_mask_create(0, commit_needed, &commit_needed_mask);
817 if (!mi_commit_mask_all_set(&commit_mask, &commit_needed_mask)) {
818 // at least commit the info slices
819 mi_assert_internal(commit_needed*MI_COMMIT_SIZE >= info_slices*MI_SEGMENT_SLICE_SIZE);
820 bool ok = _mi_os_commit(segment, commit_needed*MI_COMMIT_SIZE, &is_zero, tld->stats);
821 if (!ok) return NULL; // failed to commit
822 mi_commit_mask_set(&commit_mask, &commit_needed_mask);
823 }
824 mi_track_mem_undefined(segment,commit_needed);
825 segment->memid = memid;
826 segment->mem_is_pinned = is_pinned;
827 segment->mem_is_large = mem_large;
828 segment->mem_is_committed = mi_commit_mask_is_full(&commit_mask);
829 mi_segments_track_size((long)(segment_size), tld);
830 _mi_segment_map_allocated_at(segment);
831 }
832
833 // zero the segment info? -- not always needed as it is zero initialized from the OS
834 mi_atomic_store_ptr_release(mi_segment_t, &segment->abandoned_next, NULL); // tsan
835 if (!is_zero) {
836 ptrdiff_t ofs = offsetof(mi_segment_t, next);
837 size_t prefix = offsetof(mi_segment_t, slices) - ofs;
838 memset((uint8_t*)segment+ofs, 0, prefix + sizeof(mi_slice_t)*segment_slices);
839 }
840
841 if (!commit_info_still_good) {
842 segment->commit_mask = commit_mask; // on lazy commit, the initial part is always committed
843 segment->allow_decommit = (mi_option_is_enabled(mi_option_allow_decommit) && !segment->mem_is_pinned && !segment->mem_is_large);
844 if (segment->allow_decommit) {
845 segment->decommit_expire = _mi_clock_now() + mi_option_get(mi_option_decommit_delay);
846 segment->decommit_mask = decommit_mask;
847 mi_assert_internal(mi_commit_mask_all_set(&segment->commit_mask, &segment->decommit_mask));
848 #if MI_DEBUG>2
849 const size_t commit_needed = _mi_divide_up(info_slices*MI_SEGMENT_SLICE_SIZE, MI_COMMIT_SIZE);
850 mi_commit_mask_t commit_needed_mask;
851 mi_commit_mask_create(0, commit_needed, &commit_needed_mask);
852 mi_assert_internal(!mi_commit_mask_any_set(&segment->decommit_mask, &commit_needed_mask));
853 #endif
854 }
855 else {
856 mi_assert_internal(mi_commit_mask_is_empty(&decommit_mask));
857 segment->decommit_expire = 0;
858 mi_commit_mask_create_empty( &segment->decommit_mask );
859 mi_assert_internal(mi_commit_mask_is_empty(&segment->decommit_mask));
860 }
861 }
862
863
864 // initialize segment info
865 segment->segment_slices = segment_slices;
866 segment->segment_info_slices = info_slices;
867 segment->thread_id = _mi_thread_id();
868 segment->cookie = _mi_ptr_cookie(segment);
869 segment->slice_entries = slice_entries;
870 segment->kind = (required == 0 ? MI_SEGMENT_NORMAL : MI_SEGMENT_HUGE);
871
872 // memset(segment->slices, 0, sizeof(mi_slice_t)*(info_slices+1));
873 _mi_stat_increase(&tld->stats->page_committed, mi_segment_info_size(segment));
874
875 // set up guard pages
876 size_t guard_slices = 0;
877 if (MI_SECURE>0) {
878 // in secure mode, we set up a protected page in between the segment info
879 // and the page data, and at the end of the segment.
880 size_t os_pagesize = _mi_os_page_size();
881 mi_assert_internal(mi_segment_info_size(segment) - os_pagesize >= pre_size);
882 _mi_os_protect((uint8_t*)segment + mi_segment_info_size(segment) - os_pagesize, os_pagesize);
883 uint8_t* end = (uint8_t*)segment + mi_segment_size(segment) - os_pagesize;
884 mi_segment_ensure_committed(segment, end, os_pagesize, tld->stats);
885 _mi_os_protect(end, os_pagesize);
886 if (slice_entries == segment_slices) segment->slice_entries--; // don't use the last slice :-(
887 guard_slices = 1;
888 }
889
890 // reserve first slices for segment info
891 mi_page_t* page0 = mi_segment_span_allocate(segment, 0, info_slices, tld);
892 mi_assert_internal(page0!=NULL); if (page0==NULL) return NULL; // cannot fail as we always commit in advance
893 mi_assert_internal(segment->used == 1);
894 segment->used = 0; // don't count our internal slices towards usage
895
896 // initialize initial free pages
897 if (segment->kind == MI_SEGMENT_NORMAL) { // not a huge page
898 mi_assert_internal(huge_page==NULL);
899 mi_segment_span_free(segment, info_slices, segment->slice_entries - info_slices, tld);
900 }
901 else {
902 mi_assert_internal(huge_page!=NULL);
903 mi_assert_internal(mi_commit_mask_is_empty(&segment->decommit_mask));
904 mi_assert_internal(mi_commit_mask_is_full(&segment->commit_mask));
905 *huge_page = mi_segment_span_allocate(segment, info_slices, segment_slices - info_slices - guard_slices, tld);
906 mi_assert_internal(*huge_page != NULL); // cannot fail as we commit in advance
907 }
908
909 mi_assert_expensive(mi_segment_is_valid(segment,tld));
910 return segment;
911}
912
913
914// Allocate a segment from the OS aligned to `MI_SEGMENT_SIZE` .
915static mi_segment_t* mi_segment_alloc(size_t required, mi_arena_id_t req_arena_id, mi_segments_tld_t* tld, mi_os_tld_t* os_tld, mi_page_t** huge_page) {
916 return mi_segment_init(NULL, required, req_arena_id, tld, os_tld, huge_page);
917}
918
919
920static void mi_segment_free(mi_segment_t* segment, bool force, mi_segments_tld_t* tld) {
921 MI_UNUSED(force);
922 mi_assert_internal(segment != NULL);
923 mi_assert_internal(segment->next == NULL);
924 mi_assert_internal(segment->used == 0);
925
926 // Remove the free pages
927 mi_slice_t* slice = &segment->slices[0];
928 const mi_slice_t* end = mi_segment_slices_end(segment);
929 size_t page_count = 0;
930 while (slice < end) {
931 mi_assert_internal(slice->slice_count > 0);
932 mi_assert_internal(slice->slice_offset == 0);
933 mi_assert_internal(mi_slice_index(slice)==0 || slice->xblock_size == 0); // no more used pages ..
934 if (slice->xblock_size == 0 && segment->kind != MI_SEGMENT_HUGE) {
935 mi_segment_span_remove_from_queue(slice, tld);
936 }
937 page_count++;
938 slice = slice + slice->slice_count;
939 }
940 mi_assert_internal(page_count == 2); // first page is allocated by the segment itself
941
942 // stats
943 _mi_stat_decrease(&tld->stats->page_committed, mi_segment_info_size(segment));
944
945 // return it to the OS
946 mi_segment_os_free(segment, tld);
947}
948
949
950/* -----------------------------------------------------------
951 Page Free
952----------------------------------------------------------- */
953
954static void mi_segment_abandon(mi_segment_t* segment, mi_segments_tld_t* tld);
955
956// note: can be called on abandoned pages
957static mi_slice_t* mi_segment_page_clear(mi_page_t* page, mi_segments_tld_t* tld) {
958 mi_assert_internal(page->xblock_size > 0);
959 mi_assert_internal(mi_page_all_free(page));
960 mi_segment_t* segment = _mi_ptr_segment(page);
961 mi_assert_internal(segment->used > 0);
962
963 size_t inuse = page->capacity * mi_page_block_size(page);
964 _mi_stat_decrease(&tld->stats->page_committed, inuse);
965 _mi_stat_decrease(&tld->stats->pages, 1);
966
967 // reset the page memory to reduce memory pressure?
968 if (!segment->mem_is_pinned && !page->is_reset && mi_option_is_enabled(mi_option_page_reset)) {
969 size_t psize;
970 uint8_t* start = _mi_page_start(segment, page, &psize);
971 page->is_reset = true;
972 _mi_os_reset(start, psize, tld->stats);
973 }
974
975 // zero the page data, but not the segment fields
976 page->is_zero_init = false;
977 ptrdiff_t ofs = offsetof(mi_page_t, capacity);
978 memset((uint8_t*)page + ofs, 0, sizeof(*page) - ofs);
979 page->xblock_size = 1;
980
981 // and free it
982 mi_slice_t* slice = mi_segment_span_free_coalesce(mi_page_to_slice(page), tld);
983 segment->used--;
984 // cannot assert segment valid as it is called during reclaim
985 // mi_assert_expensive(mi_segment_is_valid(segment, tld));
986 return slice;
987}
988
989void _mi_segment_page_free(mi_page_t* page, bool force, mi_segments_tld_t* tld)
990{
991 mi_assert(page != NULL);
992
993 mi_segment_t* segment = _mi_page_segment(page);
994 mi_assert_expensive(mi_segment_is_valid(segment,tld));
995
996 // mark it as free now
997 mi_segment_page_clear(page, tld);
998 mi_assert_expensive(mi_segment_is_valid(segment, tld));
999
1000 if (segment->used == 0) {
1001 // no more used pages; remove from the free list and free the segment
1002 mi_segment_free(segment, force, tld);
1003 }
1004 else if (segment->used == segment->abandoned) {
1005 // only abandoned pages; remove from free list and abandon
1006 mi_segment_abandon(segment,tld);
1007 }
1008}
1009
1010
1011/* -----------------------------------------------------------
1012Abandonment
1013
1014When threads terminate, they can leave segments with
1015live blocks (reachable through other threads). Such segments
1016are "abandoned" and will be reclaimed by other threads to
1017reuse their pages and/or free them eventually
1018
1019We maintain a global list of abandoned segments that are
1020reclaimed on demand. Since this is shared among threads
1021the implementation needs to avoid the A-B-A problem on
1022popping abandoned segments: <https://en.wikipedia.org/wiki/ABA_problem>
1023We use tagged pointers to avoid accidentially identifying
1024reused segments, much like stamped references in Java.
1025Secondly, we maintain a reader counter to avoid resetting
1026or decommitting segments that have a pending read operation.
1027
1028Note: the current implementation is one possible design;
1029another way might be to keep track of abandoned segments
1030in the arenas/segment_cache's. This would have the advantage of keeping
1031all concurrent code in one place and not needing to deal
1032with ABA issues. The drawback is that it is unclear how to
1033scan abandoned segments efficiently in that case as they
1034would be spread among all other segments in the arenas.
1035----------------------------------------------------------- */
1036
1037// Use the bottom 20-bits (on 64-bit) of the aligned segment pointers
1038// to put in a tag that increments on update to avoid the A-B-A problem.
1039#define MI_TAGGED_MASK MI_SEGMENT_MASK
1040typedef uintptr_t mi_tagged_segment_t;
1041
1042static mi_segment_t* mi_tagged_segment_ptr(mi_tagged_segment_t ts) {
1043 return (mi_segment_t*)(ts & ~MI_TAGGED_MASK);
1044}
1045
1046static mi_tagged_segment_t mi_tagged_segment(mi_segment_t* segment, mi_tagged_segment_t ts) {
1047 mi_assert_internal(((uintptr_t)segment & MI_TAGGED_MASK) == 0);
1048 uintptr_t tag = ((ts & MI_TAGGED_MASK) + 1) & MI_TAGGED_MASK;
1049 return ((uintptr_t)segment | tag);
1050}
1051
1052// This is a list of visited abandoned pages that were full at the time.
1053// this list migrates to `abandoned` when that becomes NULL. The use of
1054// this list reduces contention and the rate at which segments are visited.
1055static mi_decl_cache_align _Atomic(mi_segment_t*) abandoned_visited; // = NULL
1056
1057// The abandoned page list (tagged as it supports pop)
1058static mi_decl_cache_align _Atomic(mi_tagged_segment_t) abandoned; // = NULL
1059
1060// Maintain these for debug purposes (these counts may be a bit off)
1061static mi_decl_cache_align _Atomic(size_t) abandoned_count;
1062static mi_decl_cache_align _Atomic(size_t) abandoned_visited_count;
1063
1064// We also maintain a count of current readers of the abandoned list
1065// in order to prevent resetting/decommitting segment memory if it might
1066// still be read.
1067static mi_decl_cache_align _Atomic(size_t) abandoned_readers; // = 0
1068
1069// Push on the visited list
1070static void mi_abandoned_visited_push(mi_segment_t* segment) {
1071 mi_assert_internal(segment->thread_id == 0);
1072 mi_assert_internal(mi_atomic_load_ptr_relaxed(mi_segment_t,&segment->abandoned_next) == NULL);
1073 mi_assert_internal(segment->next == NULL);
1074 mi_assert_internal(segment->used > 0);
1075 mi_segment_t* anext = mi_atomic_load_ptr_relaxed(mi_segment_t, &abandoned_visited);
1076 do {
1077 mi_atomic_store_ptr_release(mi_segment_t, &segment->abandoned_next, anext);
1078 } while (!mi_atomic_cas_ptr_weak_release(mi_segment_t, &abandoned_visited, &anext, segment));
1079 mi_atomic_increment_relaxed(&abandoned_visited_count);
1080}
1081
1082// Move the visited list to the abandoned list.
1083static bool mi_abandoned_visited_revisit(void)
1084{
1085 // quick check if the visited list is empty
1086 if (mi_atomic_load_ptr_relaxed(mi_segment_t, &abandoned_visited) == NULL) return false;
1087
1088 // grab the whole visited list
1089 mi_segment_t* first = mi_atomic_exchange_ptr_acq_rel(mi_segment_t, &abandoned_visited, NULL);
1090 if (first == NULL) return false;
1091
1092 // first try to swap directly if the abandoned list happens to be NULL
1093 mi_tagged_segment_t afirst;
1094 mi_tagged_segment_t ts = mi_atomic_load_relaxed(&abandoned);
1095 if (mi_tagged_segment_ptr(ts)==NULL) {
1096 size_t count = mi_atomic_load_relaxed(&abandoned_visited_count);
1097 afirst = mi_tagged_segment(first, ts);
1098 if (mi_atomic_cas_strong_acq_rel(&abandoned, &ts, afirst)) {
1099 mi_atomic_add_relaxed(&abandoned_count, count);
1100 mi_atomic_sub_relaxed(&abandoned_visited_count, count);
1101 return true;
1102 }
1103 }
1104
1105 // find the last element of the visited list: O(n)
1106 mi_segment_t* last = first;
1107 mi_segment_t* next;
1108 while ((next = mi_atomic_load_ptr_relaxed(mi_segment_t, &last->abandoned_next)) != NULL) {
1109 last = next;
1110 }
1111
1112 // and atomically prepend to the abandoned list
1113 // (no need to increase the readers as we don't access the abandoned segments)
1114 mi_tagged_segment_t anext = mi_atomic_load_relaxed(&abandoned);
1115 size_t count;
1116 do {
1117 count = mi_atomic_load_relaxed(&abandoned_visited_count);
1118 mi_atomic_store_ptr_release(mi_segment_t, &last->abandoned_next, mi_tagged_segment_ptr(anext));
1119 afirst = mi_tagged_segment(first, anext);
1120 } while (!mi_atomic_cas_weak_release(&abandoned, &anext, afirst));
1121 mi_atomic_add_relaxed(&abandoned_count, count);
1122 mi_atomic_sub_relaxed(&abandoned_visited_count, count);
1123 return true;
1124}
1125
1126// Push on the abandoned list.
1127static void mi_abandoned_push(mi_segment_t* segment) {
1128 mi_assert_internal(segment->thread_id == 0);
1129 mi_assert_internal(mi_atomic_load_ptr_relaxed(mi_segment_t, &segment->abandoned_next) == NULL);
1130 mi_assert_internal(segment->next == NULL);
1131 mi_assert_internal(segment->used > 0);
1132 mi_tagged_segment_t next;
1133 mi_tagged_segment_t ts = mi_atomic_load_relaxed(&abandoned);
1134 do {
1135 mi_atomic_store_ptr_release(mi_segment_t, &segment->abandoned_next, mi_tagged_segment_ptr(ts));
1136 next = mi_tagged_segment(segment, ts);
1137 } while (!mi_atomic_cas_weak_release(&abandoned, &ts, next));
1138 mi_atomic_increment_relaxed(&abandoned_count);
1139}
1140
1141// Wait until there are no more pending reads on segments that used to be in the abandoned list
1142// called for example from `arena.c` before decommitting
1143void _mi_abandoned_await_readers(void) {
1144 size_t n;
1145 do {
1146 n = mi_atomic_load_acquire(&abandoned_readers);
1147 if (n != 0) mi_atomic_yield();
1148 } while (n != 0);
1149}
1150
1151// Pop from the abandoned list
1152static mi_segment_t* mi_abandoned_pop(void) {
1153 mi_segment_t* segment;
1154 // Check efficiently if it is empty (or if the visited list needs to be moved)
1155 mi_tagged_segment_t ts = mi_atomic_load_relaxed(&abandoned);
1156 segment = mi_tagged_segment_ptr(ts);
1157 if mi_likely(segment == NULL) {
1158 if mi_likely(!mi_abandoned_visited_revisit()) { // try to swap in the visited list on NULL
1159 return NULL;
1160 }
1161 }
1162
1163 // Do a pop. We use a reader count to prevent
1164 // a segment to be decommitted while a read is still pending,
1165 // and a tagged pointer to prevent A-B-A link corruption.
1166 // (this is called from `region.c:_mi_mem_free` for example)
1167 mi_atomic_increment_relaxed(&abandoned_readers); // ensure no segment gets decommitted
1168 mi_tagged_segment_t next = 0;
1169 ts = mi_atomic_load_acquire(&abandoned);
1170 do {
1171 segment = mi_tagged_segment_ptr(ts);
1172 if (segment != NULL) {
1173 mi_segment_t* anext = mi_atomic_load_ptr_relaxed(mi_segment_t, &segment->abandoned_next);
1174 next = mi_tagged_segment(anext, ts); // note: reads the segment's `abandoned_next` field so should not be decommitted
1175 }
1176 } while (segment != NULL && !mi_atomic_cas_weak_acq_rel(&abandoned, &ts, next));
1177 mi_atomic_decrement_relaxed(&abandoned_readers); // release reader lock
1178 if (segment != NULL) {
1179 mi_atomic_store_ptr_release(mi_segment_t, &segment->abandoned_next, NULL);
1180 mi_atomic_decrement_relaxed(&abandoned_count);
1181 }
1182 return segment;
1183}
1184
1185/* -----------------------------------------------------------
1186 Abandon segment/page
1187----------------------------------------------------------- */
1188
1189static void mi_segment_abandon(mi_segment_t* segment, mi_segments_tld_t* tld) {
1190 mi_assert_internal(segment->used == segment->abandoned);
1191 mi_assert_internal(segment->used > 0);
1192 mi_assert_internal(mi_atomic_load_ptr_relaxed(mi_segment_t, &segment->abandoned_next) == NULL);
1193 mi_assert_internal(segment->abandoned_visits == 0);
1194 mi_assert_expensive(mi_segment_is_valid(segment,tld));
1195
1196 // remove the free pages from the free page queues
1197 mi_slice_t* slice = &segment->slices[0];
1198 const mi_slice_t* end = mi_segment_slices_end(segment);
1199 while (slice < end) {
1200 mi_assert_internal(slice->slice_count > 0);
1201 mi_assert_internal(slice->slice_offset == 0);
1202 if (slice->xblock_size == 0) { // a free page
1203 mi_segment_span_remove_from_queue(slice,tld);
1204 slice->xblock_size = 0; // but keep it free
1205 }
1206 slice = slice + slice->slice_count;
1207 }
1208
1209 // perform delayed decommits
1210 mi_segment_delayed_decommit(segment, mi_option_is_enabled(mi_option_abandoned_page_decommit) /* force? */, tld->stats);
1211
1212 // all pages in the segment are abandoned; add it to the abandoned list
1213 _mi_stat_increase(&tld->stats->segments_abandoned, 1);
1214 mi_segments_track_size(-((long)mi_segment_size(segment)), tld);
1215 segment->thread_id = 0;
1216 mi_atomic_store_ptr_release(mi_segment_t, &segment->abandoned_next, NULL);
1217 segment->abandoned_visits = 1; // from 0 to 1 to signify it is abandoned
1218 mi_abandoned_push(segment);
1219}
1220
1221void _mi_segment_page_abandon(mi_page_t* page, mi_segments_tld_t* tld) {
1222 mi_assert(page != NULL);
1223 mi_assert_internal(mi_page_thread_free_flag(page)==MI_NEVER_DELAYED_FREE);
1224 mi_assert_internal(mi_page_heap(page) == NULL);
1225 mi_segment_t* segment = _mi_page_segment(page);
1226
1227 mi_assert_expensive(mi_segment_is_valid(segment,tld));
1228 segment->abandoned++;
1229
1230 _mi_stat_increase(&tld->stats->pages_abandoned, 1);
1231 mi_assert_internal(segment->abandoned <= segment->used);
1232 if (segment->used == segment->abandoned) {
1233 // all pages are abandoned, abandon the entire segment
1234 mi_segment_abandon(segment, tld);
1235 }
1236}
1237
1238/* -----------------------------------------------------------
1239 Reclaim abandoned pages
1240----------------------------------------------------------- */
1241
1242static mi_slice_t* mi_slices_start_iterate(mi_segment_t* segment, const mi_slice_t** end) {
1243 mi_slice_t* slice = &segment->slices[0];
1244 *end = mi_segment_slices_end(segment);
1245 mi_assert_internal(slice->slice_count>0 && slice->xblock_size>0); // segment allocated page
1246 slice = slice + slice->slice_count; // skip the first segment allocated page
1247 return slice;
1248}
1249
1250// Possibly free pages and check if free space is available
1251static bool mi_segment_check_free(mi_segment_t* segment, size_t slices_needed, size_t block_size, mi_segments_tld_t* tld)
1252{
1253 mi_assert_internal(block_size < MI_HUGE_BLOCK_SIZE);
1254 mi_assert_internal(mi_segment_is_abandoned(segment));
1255 bool has_page = false;
1256
1257 // for all slices
1258 const mi_slice_t* end;
1259 mi_slice_t* slice = mi_slices_start_iterate(segment, &end);
1260 while (slice < end) {
1261 mi_assert_internal(slice->slice_count > 0);
1262 mi_assert_internal(slice->slice_offset == 0);
1263 if (mi_slice_is_used(slice)) { // used page
1264 // ensure used count is up to date and collect potential concurrent frees
1265 mi_page_t* const page = mi_slice_to_page(slice);
1266 _mi_page_free_collect(page, false);
1267 if (mi_page_all_free(page)) {
1268 // if this page is all free now, free it without adding to any queues (yet)
1269 mi_assert_internal(page->next == NULL && page->prev==NULL);
1270 _mi_stat_decrease(&tld->stats->pages_abandoned, 1);
1271 segment->abandoned--;
1272 slice = mi_segment_page_clear(page, tld); // re-assign slice due to coalesce!
1273 mi_assert_internal(!mi_slice_is_used(slice));
1274 if (slice->slice_count >= slices_needed) {
1275 has_page = true;
1276 }
1277 }
1278 else {
1279 if (page->xblock_size == block_size && mi_page_has_any_available(page)) {
1280 // a page has available free blocks of the right size
1281 has_page = true;
1282 }
1283 }
1284 }
1285 else {
1286 // empty span
1287 if (slice->slice_count >= slices_needed) {
1288 has_page = true;
1289 }
1290 }
1291 slice = slice + slice->slice_count;
1292 }
1293 return has_page;
1294}
1295
1296// Reclaim an abandoned segment; returns NULL if the segment was freed
1297// set `right_page_reclaimed` to `true` if it reclaimed a page of the right `block_size` that was not full.
1298static mi_segment_t* mi_segment_reclaim(mi_segment_t* segment, mi_heap_t* heap, size_t requested_block_size, bool* right_page_reclaimed, mi_segments_tld_t* tld) {
1299 mi_assert_internal(mi_atomic_load_ptr_relaxed(mi_segment_t, &segment->abandoned_next) == NULL);
1300 mi_assert_expensive(mi_segment_is_valid(segment, tld));
1301 if (right_page_reclaimed != NULL) { *right_page_reclaimed = false; }
1302
1303 segment->thread_id = _mi_thread_id();
1304 segment->abandoned_visits = 0;
1305 mi_segments_track_size((long)mi_segment_size(segment), tld);
1306 mi_assert_internal(segment->next == NULL);
1307 _mi_stat_decrease(&tld->stats->segments_abandoned, 1);
1308
1309 // for all slices
1310 const mi_slice_t* end;
1311 mi_slice_t* slice = mi_slices_start_iterate(segment, &end);
1312 while (slice < end) {
1313 mi_assert_internal(slice->slice_count > 0);
1314 mi_assert_internal(slice->slice_offset == 0);
1315 if (mi_slice_is_used(slice)) {
1316 // in use: reclaim the page in our heap
1317 mi_page_t* page = mi_slice_to_page(slice);
1318 mi_assert_internal(!page->is_reset);
1319 mi_assert_internal(page->is_committed);
1320 mi_assert_internal(mi_page_thread_free_flag(page)==MI_NEVER_DELAYED_FREE);
1321 mi_assert_internal(mi_page_heap(page) == NULL);
1322 mi_assert_internal(page->next == NULL && page->prev==NULL);
1323 _mi_stat_decrease(&tld->stats->pages_abandoned, 1);
1324 segment->abandoned--;
1325 // set the heap again and allow delayed free again
1326 mi_page_set_heap(page, heap);
1327 _mi_page_use_delayed_free(page, MI_USE_DELAYED_FREE, true); // override never (after heap is set)
1328 _mi_page_free_collect(page, false); // ensure used count is up to date
1329 if (mi_page_all_free(page)) {
1330 // if everything free by now, free the page
1331 slice = mi_segment_page_clear(page, tld); // set slice again due to coalesceing
1332 }
1333 else {
1334 // otherwise reclaim it into the heap
1335 _mi_page_reclaim(heap, page);
1336 if (requested_block_size == page->xblock_size && mi_page_has_any_available(page)) {
1337 if (right_page_reclaimed != NULL) { *right_page_reclaimed = true; }
1338 }
1339 }
1340 }
1341 else {
1342 // the span is free, add it to our page queues
1343 slice = mi_segment_span_free_coalesce(slice, tld); // set slice again due to coalesceing
1344 }
1345 mi_assert_internal(slice->slice_count>0 && slice->slice_offset==0);
1346 slice = slice + slice->slice_count;
1347 }
1348
1349 mi_assert(segment->abandoned == 0);
1350 if (segment->used == 0) { // due to page_clear
1351 mi_assert_internal(right_page_reclaimed == NULL || !(*right_page_reclaimed));
1352 mi_segment_free(segment, false, tld);
1353 return NULL;
1354 }
1355 else {
1356 return segment;
1357 }
1358}
1359
1360
1361void _mi_abandoned_reclaim_all(mi_heap_t* heap, mi_segments_tld_t* tld) {
1362 mi_segment_t* segment;
1363 while ((segment = mi_abandoned_pop()) != NULL) {
1364 mi_segment_reclaim(segment, heap, 0, NULL, tld);
1365 }
1366}
1367
1368static mi_segment_t* mi_segment_try_reclaim(mi_heap_t* heap, size_t needed_slices, size_t block_size, bool* reclaimed, mi_segments_tld_t* tld)
1369{
1370 *reclaimed = false;
1371 mi_segment_t* segment;
1372 long max_tries = mi_option_get_clamp(mi_option_max_segment_reclaim, 8, 1024); // limit the work to bound allocation times
1373 while ((max_tries-- > 0) && ((segment = mi_abandoned_pop()) != NULL)) {
1374 segment->abandoned_visits++;
1375 // todo: an arena exclusive heap will potentially visit many abandoned unsuitable segments
1376 // and push them into the visited list and use many tries. Perhaps we can skip non-suitable ones in a better way?
1377 bool is_suitable = _mi_heap_memid_is_suitable(heap, segment->memid);
1378 bool has_page = mi_segment_check_free(segment,needed_slices,block_size,tld); // try to free up pages (due to concurrent frees)
1379 if (segment->used == 0) {
1380 // free the segment (by forced reclaim) to make it available to other threads.
1381 // note1: we prefer to free a segment as that might lead to reclaiming another
1382 // segment that is still partially used.
1383 // note2: we could in principle optimize this by skipping reclaim and directly
1384 // freeing but that would violate some invariants temporarily)
1385 mi_segment_reclaim(segment, heap, 0, NULL, tld);
1386 }
1387 else if (has_page && is_suitable) {
1388 // found a large enough free span, or a page of the right block_size with free space
1389 // we return the result of reclaim (which is usually `segment`) as it might free
1390 // the segment due to concurrent frees (in which case `NULL` is returned).
1391 return mi_segment_reclaim(segment, heap, block_size, reclaimed, tld);
1392 }
1393 else if (segment->abandoned_visits > 3 && is_suitable) {
1394 // always reclaim on 3rd visit to limit the abandoned queue length.
1395 mi_segment_reclaim(segment, heap, 0, NULL, tld);
1396 }
1397 else {
1398 // otherwise, push on the visited list so it gets not looked at too quickly again
1399 mi_segment_delayed_decommit(segment, true /* force? */, tld->stats); // forced decommit if needed as we may not visit soon again
1400 mi_abandoned_visited_push(segment);
1401 }
1402 }
1403 return NULL;
1404}
1405
1406
1407void _mi_abandoned_collect(mi_heap_t* heap, bool force, mi_segments_tld_t* tld)
1408{
1409 mi_segment_t* segment;
1410 int max_tries = (force ? 16*1024 : 1024); // limit latency
1411 if (force) {
1412 mi_abandoned_visited_revisit();
1413 }
1414 while ((max_tries-- > 0) && ((segment = mi_abandoned_pop()) != NULL)) {
1415 mi_segment_check_free(segment,0,0,tld); // try to free up pages (due to concurrent frees)
1416 if (segment->used == 0) {
1417 // free the segment (by forced reclaim) to make it available to other threads.
1418 // note: we could in principle optimize this by skipping reclaim and directly
1419 // freeing but that would violate some invariants temporarily)
1420 mi_segment_reclaim(segment, heap, 0, NULL, tld);
1421 }
1422 else {
1423 // otherwise, decommit if needed and push on the visited list
1424 // note: forced decommit can be expensive if many threads are destroyed/created as in mstress.
1425 mi_segment_delayed_decommit(segment, force, tld->stats);
1426 mi_abandoned_visited_push(segment);
1427 }
1428 }
1429}
1430
1431/* -----------------------------------------------------------
1432 Reclaim or allocate
1433----------------------------------------------------------- */
1434
1435static mi_segment_t* mi_segment_reclaim_or_alloc(mi_heap_t* heap, size_t needed_slices, size_t block_size, mi_segments_tld_t* tld, mi_os_tld_t* os_tld)
1436{
1437 mi_assert_internal(block_size < MI_HUGE_BLOCK_SIZE);
1438 mi_assert_internal(block_size <= MI_LARGE_OBJ_SIZE_MAX);
1439
1440 // 1. try to reclaim an abandoned segment
1441 bool reclaimed;
1442 mi_segment_t* segment = mi_segment_try_reclaim(heap, needed_slices, block_size, &reclaimed, tld);
1443 if (reclaimed) {
1444 // reclaimed the right page right into the heap
1445 mi_assert_internal(segment != NULL);
1446 return NULL; // pretend out-of-memory as the page will be in the page queue of the heap with available blocks
1447 }
1448 else if (segment != NULL) {
1449 // reclaimed a segment with a large enough empty span in it
1450 return segment;
1451 }
1452 // 2. otherwise allocate a fresh segment
1453 return mi_segment_alloc(0, heap->arena_id, tld, os_tld, NULL);
1454}
1455
1456
1457/* -----------------------------------------------------------
1458 Page allocation
1459----------------------------------------------------------- */
1460
1461static mi_page_t* mi_segments_page_alloc(mi_heap_t* heap, mi_page_kind_t page_kind, size_t required, size_t block_size, mi_segments_tld_t* tld, mi_os_tld_t* os_tld)
1462{
1463 mi_assert_internal(required <= MI_LARGE_OBJ_SIZE_MAX && page_kind <= MI_PAGE_LARGE);
1464
1465 // find a free page
1466 size_t page_size = _mi_align_up(required, (required > MI_MEDIUM_PAGE_SIZE ? MI_MEDIUM_PAGE_SIZE : MI_SEGMENT_SLICE_SIZE));
1467 size_t slices_needed = page_size / MI_SEGMENT_SLICE_SIZE;
1468 mi_assert_internal(slices_needed * MI_SEGMENT_SLICE_SIZE == page_size);
1469 mi_page_t* page = mi_segments_page_find_and_allocate(slices_needed, heap->arena_id, tld); //(required <= MI_SMALL_SIZE_MAX ? 0 : slices_needed), tld);
1470 if (page==NULL) {
1471 // no free page, allocate a new segment and try again
1472 if (mi_segment_reclaim_or_alloc(heap, slices_needed, block_size, tld, os_tld) == NULL) {
1473 // OOM or reclaimed a good page in the heap
1474 return NULL;
1475 }
1476 else {
1477 // otherwise try again
1478 return mi_segments_page_alloc(heap, page_kind, required, block_size, tld, os_tld);
1479 }
1480 }
1481 mi_assert_internal(page != NULL && page->slice_count*MI_SEGMENT_SLICE_SIZE == page_size);
1482 mi_assert_internal(_mi_ptr_segment(page)->thread_id == _mi_thread_id());
1483 mi_segment_delayed_decommit(_mi_ptr_segment(page), false, tld->stats);
1484 return page;
1485}
1486
1487
1488
1489/* -----------------------------------------------------------
1490 Huge page allocation
1491----------------------------------------------------------- */
1492
1493static mi_page_t* mi_segment_huge_page_alloc(size_t size, mi_arena_id_t req_arena_id, mi_segments_tld_t* tld, mi_os_tld_t* os_tld)
1494{
1495 mi_page_t* page = NULL;
1496 mi_segment_t* segment = mi_segment_alloc(size,req_arena_id,tld,os_tld,&page);
1497 if (segment == NULL || page==NULL) return NULL;
1498 mi_assert_internal(segment->used==1);
1499 mi_assert_internal(mi_page_block_size(page) >= size);
1500 segment->thread_id = 0; // huge segments are immediately abandoned
1501 return page;
1502}
1503
1504// free huge block from another thread
1505void _mi_segment_huge_page_free(mi_segment_t* segment, mi_page_t* page, mi_block_t* block) {
1506 // huge page segments are always abandoned and can be freed immediately by any thread
1507 mi_assert_internal(segment->kind==MI_SEGMENT_HUGE);
1508 mi_assert_internal(segment == _mi_page_segment(page));
1509 mi_assert_internal(mi_atomic_load_relaxed(&segment->thread_id)==0);
1510
1511 // claim it and free
1512 mi_heap_t* heap = mi_heap_get_default(); // issue #221; don't use the internal get_default_heap as we need to ensure the thread is initialized.
1513 // paranoia: if this it the last reference, the cas should always succeed
1514 size_t expected_tid = 0;
1515 if (mi_atomic_cas_strong_acq_rel(&segment->thread_id, &expected_tid, heap->thread_id)) {
1516 mi_block_set_next(page, block, page->free);
1517 page->free = block;
1518 page->used--;
1519 page->is_zero = false;
1520 mi_assert(page->used == 0);
1521 mi_tld_t* tld = heap->tld;
1522 _mi_segment_page_free(page, true, &tld->segments);
1523 }
1524#if (MI_DEBUG!=0)
1525 else {
1526 mi_assert_internal(false);
1527 }
1528#endif
1529}
1530
1531/* -----------------------------------------------------------
1532 Page allocation and free
1533----------------------------------------------------------- */
1534mi_page_t* _mi_segment_page_alloc(mi_heap_t* heap, size_t block_size, mi_segments_tld_t* tld, mi_os_tld_t* os_tld) {
1535 mi_page_t* page;
1536 if (block_size <= MI_SMALL_OBJ_SIZE_MAX) {
1537 page = mi_segments_page_alloc(heap,MI_PAGE_SMALL,block_size,block_size,tld,os_tld);
1538 }
1539 else if (block_size <= MI_MEDIUM_OBJ_SIZE_MAX) {
1540 page = mi_segments_page_alloc(heap,MI_PAGE_MEDIUM,MI_MEDIUM_PAGE_SIZE,block_size,tld, os_tld);
1541 }
1542 else if (block_size <= MI_LARGE_OBJ_SIZE_MAX) {
1543 page = mi_segments_page_alloc(heap,MI_PAGE_LARGE,block_size,block_size,tld, os_tld);
1544 }
1545 else {
1546 page = mi_segment_huge_page_alloc(block_size,heap->arena_id,tld,os_tld);
1547 }
1548 mi_assert_internal(page == NULL || _mi_heap_memid_is_suitable(heap, _mi_page_segment(page)->memid));
1549 mi_assert_expensive(page == NULL || mi_segment_is_valid(_mi_page_segment(page),tld));
1550 return page;
1551}
1552
1553
1554