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 | #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 | |
16 | static void mi_segment_delayed_decommit(mi_segment_t* segment, bool force, mi_stats_t* stats); |
17 | |
18 | |
19 | // ------------------------------------------------------------------- |
20 | // commit mask |
21 | // ------------------------------------------------------------------- |
22 | |
23 | static 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 | |
30 | static 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 | |
37 | static 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 | |
43 | static 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 | |
49 | static 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 | |
55 | static 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 | |
82 | size_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 | |
101 | size_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 | |
161 | static const mi_slice_t* mi_segment_slices_end(const mi_segment_t* segment) { |
162 | return &segment->slices[segment->slice_entries]; |
163 | } |
164 | |
165 | static 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 | |
177 | static 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 | |
187 | static 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 | |
195 | static 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 | |
207 | static 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 | |
218 | static 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 | |
225 | static 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 | |
242 | static bool mi_slice_is_used(const mi_slice_t* slice) { |
243 | return (slice->xblock_size > 0); |
244 | } |
245 | |
246 | |
247 | #if (MI_DEBUG>=3) |
248 | static 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 | |
255 | static 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 | |
310 | static size_t mi_segment_info_size(mi_segment_t* segment) { |
311 | return segment->segment_info_slices * MI_SEGMENT_SLICE_SIZE; |
312 | } |
313 | |
314 | static 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 |
325 | uint8_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 | |
335 | static 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 | /* ---------------------------------------------------------------------------- |
357 | Segment caches |
358 | We keep a small segment cache per thread to increase local |
359 | reuse and avoid setting/clearing guard pages in secure mode. |
360 | ------------------------------------------------------------------------------- */ |
361 | |
362 | static 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 | |
371 | static 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 |
398 | void _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 | |
408 | static 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 | |
459 | static 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 | |
507 | static 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 | |
514 | static 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 | |
549 | static 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 | |
573 | static 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 |
578 | static 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 |
607 | static 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 | |
615 | static 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 |
623 | static 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 | |
665 | static 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 |
678 | static 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 = 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 | |
724 | static 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` . |
764 | static 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` . |
915 | static 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 | |
920 | static 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 | |
954 | static void mi_segment_abandon(mi_segment_t* segment, mi_segments_tld_t* tld); |
955 | |
956 | // note: can be called on abandoned pages |
957 | static 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 | |
989 | void _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 | /* ----------------------------------------------------------- |
1012 | Abandonment |
1013 | |
1014 | When threads terminate, they can leave segments with |
1015 | live blocks (reachable through other threads). Such segments |
1016 | are "abandoned" and will be reclaimed by other threads to |
1017 | reuse their pages and/or free them eventually |
1018 | |
1019 | We maintain a global list of abandoned segments that are |
1020 | reclaimed on demand. Since this is shared among threads |
1021 | the implementation needs to avoid the A-B-A problem on |
1022 | popping abandoned segments: <https://en.wikipedia.org/wiki/ABA_problem> |
1023 | We use tagged pointers to avoid accidentially identifying |
1024 | reused segments, much like stamped references in Java. |
1025 | Secondly, we maintain a reader counter to avoid resetting |
1026 | or decommitting segments that have a pending read operation. |
1027 | |
1028 | Note: the current implementation is one possible design; |
1029 | another way might be to keep track of abandoned segments |
1030 | in the arenas/segment_cache's. This would have the advantage of keeping |
1031 | all concurrent code in one place and not needing to deal |
1032 | with ABA issues. The drawback is that it is unclear how to |
1033 | scan abandoned segments efficiently in that case as they |
1034 | would 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 |
1040 | typedef uintptr_t mi_tagged_segment_t; |
1041 | |
1042 | static mi_segment_t* mi_tagged_segment_ptr(mi_tagged_segment_t ts) { |
1043 | return (mi_segment_t*)(ts & ~MI_TAGGED_MASK); |
1044 | } |
1045 | |
1046 | static 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. |
1055 | static mi_decl_cache_align _Atomic(mi_segment_t*) abandoned_visited; // = NULL |
1056 | |
1057 | // The abandoned page list (tagged as it supports pop) |
1058 | static 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) |
1061 | static mi_decl_cache_align _Atomic(size_t) abandoned_count; |
1062 | static 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. |
1067 | static mi_decl_cache_align _Atomic(size_t) abandoned_readers; // = 0 |
1068 | |
1069 | // Push on the visited list |
1070 | static 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. |
1083 | static 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. |
1127 | static 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 |
1143 | void _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 |
1152 | static 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 | |
1189 | static 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 | |
1221 | void _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 | |
1242 | static 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 |
1251 | static 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. |
1298 | static 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 | |
1361 | void _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 | |
1368 | static 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 | |
1407 | void _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 | |
1435 | static 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 | |
1461 | static 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 | |
1493 | static 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 |
1505 | void _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 | ----------------------------------------------------------- */ |
1534 | mi_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 | |