| 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_try_purge(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->purge_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 |
// note: the offset must always be an xblock_size multiple since we assume small allocations |
| 320 |
// are aligned (see `mi_heap_malloc_aligned`). |
| 321 |
size_t start_offset = 0; |
| 322 |
if (xblock_size >= MI_INTPTR_SIZE) { |
| 323 |
if (xblock_size <= 64) { start_offset = 3*xblock_size; } |
| 324 |
else if (xblock_size <= 512) { start_offset = xblock_size; } |
| 325 |
} |
| 326 |
if (page_size != NULL) { *page_size = psize - start_offset; } |
| 327 |
return (uint8_t*)segment + ((idx*MI_SEGMENT_SLICE_SIZE) + start_offset); |
| 328 |
} |
| 329 |
|
| 330 |
// Start of the page available memory; can be used on uninitialized pages |
| 331 |
uint8_t* _mi_segment_page_start(const mi_segment_t* segment, const mi_page_t* page, size_t* page_size) |
| 332 |
{ |
| 333 |
const mi_slice_t* slice = mi_page_to_slice((mi_page_t*)page); |
| 334 |
uint8_t* p = _mi_segment_page_start_from_slice(segment, slice, page->xblock_size, page_size); |
| 335 |
mi_assert_internal(page->xblock_size > 0 || _mi_ptr_page(p) == page); |
| 336 |
mi_assert_internal(_mi_ptr_segment(p) == segment); |
| 337 |
return p; |
| 338 |
} |
| 339 |
|
| 340 |
|
| 341 |
static size_t mi_segment_calculate_slices(size_t required, size_t* pre_size, size_t* info_slices) { |
| 342 |
size_t page_size = _mi_os_page_size(); |
| 343 |
size_t isize = _mi_align_up(sizeof(mi_segment_t), page_size); |
| 344 |
size_t guardsize = 0; |
| 345 |
|
| 346 |
if (MI_SECURE>0) { |
| 347 |
// in secure mode, we set up a protected page in between the segment info |
| 348 |
// and the page data (and one at the end of the segment) |
| 349 |
guardsize = page_size; |
| 350 |
if (required > 0) { |
| 351 |
required = _mi_align_up(required, MI_SEGMENT_SLICE_SIZE) + page_size; |
| 352 |
} |
| 353 |
} |
| 354 |
|
| 355 |
if (pre_size != NULL) *pre_size = isize; |
| 356 |
isize = _mi_align_up(isize + guardsize, MI_SEGMENT_SLICE_SIZE); |
| 357 |
if (info_slices != NULL) *info_slices = isize / MI_SEGMENT_SLICE_SIZE; |
| 358 |
size_t segment_size = (required==0 ? MI_SEGMENT_SIZE : _mi_align_up( required + isize + guardsize, MI_SEGMENT_SLICE_SIZE) ); |
| 359 |
mi_assert_internal(segment_size % MI_SEGMENT_SLICE_SIZE == 0); |
| 360 |
return (segment_size / MI_SEGMENT_SLICE_SIZE); |
| 361 |
} |
| 362 |
|
| 363 |
|
| 364 |
/* ---------------------------------------------------------------------------- |
| 365 |
Segment caches |
| 366 |
We keep a small segment cache per thread to increase local |
| 367 |
reuse and avoid setting/clearing guard pages in secure mode. |
| 368 |
------------------------------------------------------------------------------- */ |
| 369 |
|
| 370 |
static void mi_segments_track_size(long segment_size, mi_segments_tld_t* tld) { |
| 371 |
if (segment_size>=0) _mi_stat_increase(&tld->stats->segments,1); |
| 372 |
else _mi_stat_decrease(&tld->stats->segments,1); |
| 373 |
tld->count += (segment_size >= 0 ? 1 : -1); |
| 374 |
if (tld->count > tld->peak_count) tld->peak_count = tld->count; |
| 375 |
tld->current_size += segment_size; |
| 376 |
if (tld->current_size > tld->peak_size) tld->peak_size = tld->current_size; |
| 377 |
} |
| 378 |
|
| 379 |
static void mi_segment_os_free(mi_segment_t* segment, mi_segments_tld_t* tld) { |
| 380 |
segment->thread_id = 0; |
| 381 |
_mi_segment_map_freed_at(segment); |
| 382 |
mi_segments_track_size(-((long)mi_segment_size(segment)),tld); |
| 383 |
if (MI_SECURE>0) { |
| 384 |
// _mi_os_unprotect(segment, mi_segment_size(segment)); // ensure no more guard pages are set |
| 385 |
// unprotect the guard pages; we cannot just unprotect the whole segment size as part may be decommitted |
| 386 |
size_t os_pagesize = _mi_os_page_size(); |
| 387 |
_mi_os_unprotect((uint8_t*)segment + mi_segment_info_size(segment) - os_pagesize, os_pagesize); |
| 388 |
uint8_t* end = (uint8_t*)segment + mi_segment_size(segment) - os_pagesize; |
| 389 |
_mi_os_unprotect(end, os_pagesize); |
| 390 |
} |
| 391 |
|
| 392 |
// purge delayed decommits now? (no, leave it to the arena) |
| 393 |
// mi_segment_try_purge(segment,true,tld->stats); |
| 394 |
|
| 395 |
const size_t size = mi_segment_size(segment); |
| 396 |
const size_t csize = _mi_commit_mask_committed_size(&segment->commit_mask, size); |
| 397 |
|
| 398 |
_mi_abandoned_await_readers(tld->abandoned); // wait until safe to free |
| 399 |
_mi_arena_free(segment, mi_segment_size(segment), csize, segment->memid, tld->stats); |
| 400 |
} |
| 401 |
|
| 402 |
// called by threads that are terminating |
| 403 |
void _mi_segment_thread_collect(mi_segments_tld_t* tld) { |
| 404 |
MI_UNUSED(tld); |
| 405 |
// nothing to do |
| 406 |
} |
| 407 |
|
| 408 |
|
| 409 |
/* ----------------------------------------------------------- |
| 410 |
Commit/Decommit ranges |
| 411 |
----------------------------------------------------------- */ |
| 412 |
|
| 413 |
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) { |
| 414 |
mi_assert_internal(_mi_ptr_segment(p + 1) == segment); |
| 415 |
mi_assert_internal(segment->kind != MI_SEGMENT_HUGE); |
| 416 |
mi_commit_mask_create_empty(cm); |
| 417 |
if (size == 0 || size > MI_SEGMENT_SIZE || segment->kind == MI_SEGMENT_HUGE) return; |
| 418 |
const size_t segstart = mi_segment_info_size(segment); |
| 419 |
const size_t segsize = mi_segment_size(segment); |
| 420 |
if (p >= (uint8_t*)segment + segsize) return; |
| 421 |
|
| 422 |
size_t pstart = (p - (uint8_t*)segment); |
| 423 |
mi_assert_internal(pstart + size <= segsize); |
| 424 |
|
| 425 |
size_t start; |
| 426 |
size_t end; |
| 427 |
if (conservative) { |
| 428 |
// decommit conservative |
| 429 |
start = _mi_align_up(pstart, MI_COMMIT_SIZE); |
| 430 |
end = _mi_align_down(pstart + size, MI_COMMIT_SIZE); |
| 431 |
mi_assert_internal(start >= segstart); |
| 432 |
mi_assert_internal(end <= segsize); |
| 433 |
} |
| 434 |
else { |
| 435 |
// commit liberal |
| 436 |
start = _mi_align_down(pstart, MI_MINIMAL_COMMIT_SIZE); |
| 437 |
end = _mi_align_up(pstart + size, MI_MINIMAL_COMMIT_SIZE); |
| 438 |
} |
| 439 |
if (pstart >= segstart && start < segstart) { // note: the mask is also calculated for an initial commit of the info area |
| 440 |
start = segstart; |
| 441 |
} |
| 442 |
if (end > segsize) { |
| 443 |
end = segsize; |
| 444 |
} |
| 445 |
|
| 446 |
mi_assert_internal(start <= pstart && (pstart + size) <= end); |
| 447 |
mi_assert_internal(start % MI_COMMIT_SIZE==0 && end % MI_COMMIT_SIZE == 0); |
| 448 |
*start_p = (uint8_t*)segment + start; |
| 449 |
*full_size = (end > start ? end - start : 0); |
| 450 |
if (*full_size == 0) return; |
| 451 |
|
| 452 |
size_t bitidx = start / MI_COMMIT_SIZE; |
| 453 |
mi_assert_internal(bitidx < MI_COMMIT_MASK_BITS); |
| 454 |
|
| 455 |
size_t bitcount = *full_size / MI_COMMIT_SIZE; // can be 0 |
| 456 |
if (bitidx + bitcount > MI_COMMIT_MASK_BITS) { |
| 457 |
_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); |
| 458 |
} |
| 459 |
mi_assert_internal((bitidx + bitcount) <= MI_COMMIT_MASK_BITS); |
| 460 |
mi_commit_mask_create(bitidx, bitcount, cm); |
| 461 |
} |
| 462 |
|
| 463 |
static bool mi_segment_commit(mi_segment_t* segment, uint8_t* p, size_t size, mi_stats_t* stats) { |
| 464 |
mi_assert_internal(mi_commit_mask_all_set(&segment->commit_mask, &segment->purge_mask)); |
| 465 |
|
| 466 |
// commit liberal |
| 467 |
uint8_t* start = NULL; |
| 468 |
size_t full_size = 0; |
| 469 |
mi_commit_mask_t mask; |
| 470 |
mi_segment_commit_mask(segment, false /* conservative? */, p, size, &start, &full_size, &mask); |
| 471 |
if (mi_commit_mask_is_empty(&mask) || full_size == 0) return true; |
| 472 |
|
| 473 |
if (!mi_commit_mask_all_set(&segment->commit_mask, &mask)) { |
| 474 |
// committing |
| 475 |
bool is_zero = false; |
| 476 |
mi_commit_mask_t cmask; |
| 477 |
mi_commit_mask_create_intersect(&segment->commit_mask, &mask, &cmask); |
| 478 |
_mi_stat_decrease(&_mi_stats_main.committed, _mi_commit_mask_committed_size(&cmask, MI_SEGMENT_SIZE)); // adjust for overlap |
| 479 |
if (!_mi_os_commit(start, full_size, &is_zero, stats)) return false; |
| 480 |
mi_commit_mask_set(&segment->commit_mask, &mask); |
| 481 |
} |
| 482 |
|
| 483 |
// increase purge expiration when using part of delayed purges -- we assume more allocations are coming soon. |
| 484 |
if (mi_commit_mask_any_set(&segment->purge_mask, &mask)) { |
| 485 |
segment->purge_expire = _mi_clock_now() + mi_option_get(mi_option_purge_delay); |
| 486 |
} |
| 487 |
|
| 488 |
// always clear any delayed purges in our range (as they are either committed now) |
| 489 |
mi_commit_mask_clear(&segment->purge_mask, &mask); |
| 490 |
return true; |
| 491 |
} |
| 492 |
|
| 493 |
static bool mi_segment_ensure_committed(mi_segment_t* segment, uint8_t* p, size_t size, mi_stats_t* stats) { |
| 494 |
mi_assert_internal(mi_commit_mask_all_set(&segment->commit_mask, &segment->purge_mask)); |
| 495 |
// note: assumes commit_mask is always full for huge segments as otherwise the commit mask bits can overflow |
| 496 |
if (mi_commit_mask_is_full(&segment->commit_mask) && mi_commit_mask_is_empty(&segment->purge_mask)) return true; // fully committed |
| 497 |
mi_assert_internal(segment->kind != MI_SEGMENT_HUGE); |
| 498 |
return mi_segment_commit(segment, p, size, stats); |
| 499 |
} |
| 500 |
|
| 501 |
static bool mi_segment_purge(mi_segment_t* segment, uint8_t* p, size_t size, mi_stats_t* stats) { |
| 502 |
mi_assert_internal(mi_commit_mask_all_set(&segment->commit_mask, &segment->purge_mask)); |
| 503 |
if (!segment->allow_purge) return true; |
| 504 |
|
| 505 |
// purge conservative |
| 506 |
uint8_t* start = NULL; |
| 507 |
size_t full_size = 0; |
| 508 |
mi_commit_mask_t mask; |
| 509 |
mi_segment_commit_mask(segment, true /* conservative? */, p, size, &start, &full_size, &mask); |
| 510 |
if (mi_commit_mask_is_empty(&mask) || full_size==0) return true; |
| 511 |
|
| 512 |
if (mi_commit_mask_any_set(&segment->commit_mask, &mask)) { |
| 513 |
// purging |
| 514 |
mi_assert_internal((void*)start != (void*)segment); |
| 515 |
mi_assert_internal(segment->allow_decommit); |
| 516 |
const bool decommitted = _mi_os_purge(start, full_size, stats); // reset or decommit |
| 517 |
if (decommitted) { |
| 518 |
mi_commit_mask_t cmask; |
| 519 |
mi_commit_mask_create_intersect(&segment->commit_mask, &mask, &cmask); |
| 520 |
_mi_stat_increase(&_mi_stats_main.committed, full_size - _mi_commit_mask_committed_size(&cmask, MI_SEGMENT_SIZE)); // adjust for double counting |
| 521 |
mi_commit_mask_clear(&segment->commit_mask, &mask); |
| 522 |
} |
| 523 |
} |
| 524 |
|
| 525 |
// always clear any scheduled purges in our range |
| 526 |
mi_commit_mask_clear(&segment->purge_mask, &mask); |
| 527 |
return true; |
| 528 |
} |
| 529 |
|
| 530 |
static void mi_segment_schedule_purge(mi_segment_t* segment, uint8_t* p, size_t size, mi_stats_t* stats) { |
| 531 |
if (!segment->allow_purge) return; |
| 532 |
|
| 533 |
if (mi_option_get(mi_option_purge_delay) == 0) { |
| 534 |
mi_segment_purge(segment, p, size, stats); |
| 535 |
} |
| 536 |
else { |
| 537 |
// register for future purge in the purge mask |
| 538 |
uint8_t* start = NULL; |
| 539 |
size_t full_size = 0; |
| 540 |
mi_commit_mask_t mask; |
| 541 |
mi_segment_commit_mask(segment, true /*conservative*/, p, size, &start, &full_size, &mask); |
| 542 |
if (mi_commit_mask_is_empty(&mask) || full_size==0) return; |
| 543 |
|
| 544 |
// update delayed commit |
| 545 |
mi_assert_internal(segment->purge_expire > 0 || mi_commit_mask_is_empty(&segment->purge_mask)); |
| 546 |
mi_commit_mask_t cmask; |
| 547 |
mi_commit_mask_create_intersect(&segment->commit_mask, &mask, &cmask); // only purge what is committed; span_free may try to decommit more |
| 548 |
mi_commit_mask_set(&segment->purge_mask, &cmask); |
| 549 |
mi_msecs_t now = _mi_clock_now(); |
| 550 |
if (segment->purge_expire == 0) { |
| 551 |
// no previous purgess, initialize now |
| 552 |
segment->purge_expire = now + mi_option_get(mi_option_purge_delay); |
| 553 |
} |
| 554 |
else if (segment->purge_expire <= now) { |
| 555 |
// previous purge mask already expired |
| 556 |
if (segment->purge_expire + mi_option_get(mi_option_purge_extend_delay) <= now) { |
| 557 |
mi_segment_try_purge(segment, true, stats); |
| 558 |
} |
| 559 |
else { |
| 560 |
segment->purge_expire = now + mi_option_get(mi_option_purge_extend_delay); // (mi_option_get(mi_option_purge_delay) / 8); // wait a tiny bit longer in case there is a series of free's |
| 561 |
} |
| 562 |
} |
| 563 |
else { |
| 564 |
// previous purge mask is not yet expired, increase the expiration by a bit. |
| 565 |
segment->purge_expire += mi_option_get(mi_option_purge_extend_delay); |
| 566 |
} |
| 567 |
} |
| 568 |
} |
| 569 |
|
| 570 |
static void mi_segment_try_purge(mi_segment_t* segment, bool force, mi_stats_t* stats) { |
| 571 |
if (!segment->allow_purge || mi_commit_mask_is_empty(&segment->purge_mask)) return; |
| 572 |
mi_msecs_t now = _mi_clock_now(); |
| 573 |
if (!force && now < segment->purge_expire) return; |
| 574 |
|
| 575 |
mi_commit_mask_t mask = segment->purge_mask; |
| 576 |
segment->purge_expire = 0; |
| 577 |
mi_commit_mask_create_empty(&segment->purge_mask); |
| 578 |
|
| 579 |
size_t idx; |
| 580 |
size_t count; |
| 581 |
mi_commit_mask_foreach(&mask, idx, count) { |
| 582 |
// if found, decommit that sequence |
| 583 |
if (count > 0) { |
| 584 |
uint8_t* p = (uint8_t*)segment + (idx*MI_COMMIT_SIZE); |
| 585 |
size_t size = count * MI_COMMIT_SIZE; |
| 586 |
mi_segment_purge(segment, p, size, stats); |
| 587 |
} |
| 588 |
} |
| 589 |
mi_commit_mask_foreach_end() |
| 590 |
mi_assert_internal(mi_commit_mask_is_empty(&segment->purge_mask)); |
| 591 |
} |
| 592 |
|
| 593 |
|
| 594 |
/* ----------------------------------------------------------- |
| 595 |
Span free |
| 596 |
----------------------------------------------------------- */ |
| 597 |
|
| 598 |
static bool mi_segment_is_abandoned(mi_segment_t* segment) { |
| 599 |
return (segment->thread_id == 0); |
| 600 |
} |
| 601 |
|
| 602 |
// note: can be called on abandoned segments |
| 603 |
static void mi_segment_span_free(mi_segment_t* segment, size_t slice_index, size_t slice_count, bool allow_purge, mi_segments_tld_t* tld) { |
| 604 |
mi_assert_internal(slice_index < segment->slice_entries); |
| 605 |
mi_span_queue_t* sq = (segment->kind == MI_SEGMENT_HUGE || mi_segment_is_abandoned(segment) |
| 606 |
? NULL : mi_span_queue_for(slice_count,tld)); |
| 607 |
if (slice_count==0) slice_count = 1; |
| 608 |
mi_assert_internal(slice_index + slice_count - 1 < segment->slice_entries); |
| 609 |
|
| 610 |
// set first and last slice (the intermediates can be undetermined) |
| 611 |
mi_slice_t* slice = &segment->slices[slice_index]; |
| 612 |
slice->slice_count = (uint32_t)slice_count; |
| 613 |
mi_assert_internal(slice->slice_count == slice_count); // no overflow? |
| 614 |
slice->slice_offset = 0; |
| 615 |
if (slice_count > 1) { |
| 616 |
mi_slice_t* last = &segment->slices[slice_index + slice_count - 1]; |
| 617 |
last->slice_count = 0; |
| 618 |
last->slice_offset = (uint32_t)(sizeof(mi_page_t)*(slice_count - 1)); |
| 619 |
last->xblock_size = 0; |
| 620 |
} |
| 621 |
|
| 622 |
// perhaps decommit |
| 623 |
if (allow_purge) { |
| 624 |
mi_segment_schedule_purge(segment, mi_slice_start(slice), slice_count * MI_SEGMENT_SLICE_SIZE, tld->stats); |
| 625 |
} |
| 626 |
|
| 627 |
// and push it on the free page queue (if it was not a huge page) |
| 628 |
if (sq != NULL) mi_span_queue_push( sq, slice ); |
| 629 |
else slice->xblock_size = 0; // mark huge page as free anyways |
| 630 |
} |
| 631 |
|
| 632 |
/* |
| 633 |
// called from reclaim to add existing free spans |
| 634 |
static void mi_segment_span_add_free(mi_slice_t* slice, mi_segments_tld_t* tld) { |
| 635 |
mi_segment_t* segment = _mi_ptr_segment(slice); |
| 636 |
mi_assert_internal(slice->xblock_size==0 && slice->slice_count>0 && slice->slice_offset==0); |
| 637 |
size_t slice_index = mi_slice_index(slice); |
| 638 |
mi_segment_span_free(segment,slice_index,slice->slice_count,tld); |
| 639 |
} |
| 640 |
*/ |
| 641 |
|
| 642 |
static void mi_segment_span_remove_from_queue(mi_slice_t* slice, mi_segments_tld_t* tld) { |
| 643 |
mi_assert_internal(slice->slice_count > 0 && slice->slice_offset==0 && slice->xblock_size==0); |
| 644 |
mi_assert_internal(_mi_ptr_segment(slice)->kind != MI_SEGMENT_HUGE); |
| 645 |
mi_span_queue_t* sq = mi_span_queue_for(slice->slice_count, tld); |
| 646 |
mi_span_queue_delete(sq, slice); |
| 647 |
} |
| 648 |
|
| 649 |
// note: can be called on abandoned segments |
| 650 |
static mi_slice_t* mi_segment_span_free_coalesce(mi_slice_t* slice, mi_segments_tld_t* tld) { |
| 651 |
mi_assert_internal(slice != NULL && slice->slice_count > 0 && slice->slice_offset == 0); |
| 652 |
mi_segment_t* segment = _mi_ptr_segment(slice); |
| 653 |
bool is_abandoned = mi_segment_is_abandoned(segment); |
| 654 |
|
| 655 |
// for huge pages, just mark as free but don't add to the queues |
| 656 |
if (segment->kind == MI_SEGMENT_HUGE) { |
| 657 |
// issue #691: segment->used can be 0 if the huge page block was freed while abandoned (reclaim will get here in that case) |
| 658 |
mi_assert_internal((segment->used==0 && slice->xblock_size==0) || segment->used == 1); // decreased right after this call in `mi_segment_page_clear` |
| 659 |
slice->xblock_size = 0; // mark as free anyways |
| 660 |
// we should mark the last slice `xblock_size=0` now to maintain invariants but we skip it to |
| 661 |
// avoid a possible cache miss (and the segment is about to be freed) |
| 662 |
return slice; |
| 663 |
} |
| 664 |
|
| 665 |
// otherwise coalesce the span and add to the free span queues |
| 666 |
size_t slice_count = slice->slice_count; |
| 667 |
mi_slice_t* next = slice + slice->slice_count; |
| 668 |
mi_assert_internal(next <= mi_segment_slices_end(segment)); |
| 669 |
if (next < mi_segment_slices_end(segment) && next->xblock_size==0) { |
| 670 |
// free next block -- remove it from free and merge |
| 671 |
mi_assert_internal(next->slice_count > 0 && next->slice_offset==0); |
| 672 |
slice_count += next->slice_count; // extend |
| 673 |
if (!is_abandoned) { mi_segment_span_remove_from_queue(next, tld); } |
| 674 |
} |
| 675 |
if (slice > segment->slices) { |
| 676 |
mi_slice_t* prev = mi_slice_first(slice - 1); |
| 677 |
mi_assert_internal(prev >= segment->slices); |
| 678 |
if (prev->xblock_size==0) { |
| 679 |
// free previous slice -- remove it from free and merge |
| 680 |
mi_assert_internal(prev->slice_count > 0 && prev->slice_offset==0); |
| 681 |
slice_count += prev->slice_count; |
| 682 |
if (!is_abandoned) { mi_segment_span_remove_from_queue(prev, tld); } |
| 683 |
slice = prev; |
| 684 |
} |
| 685 |
} |
| 686 |
|
| 687 |
// and add the new free page |
| 688 |
mi_segment_span_free(segment, mi_slice_index(slice), slice_count, true, tld); |
| 689 |
return slice; |
| 690 |
} |
| 691 |
|
| 692 |
|
| 693 |
|
| 694 |
/* ----------------------------------------------------------- |
| 695 |
Page allocation |
| 696 |
----------------------------------------------------------- */ |
| 697 |
|
| 698 |
// Note: may still return NULL if committing the memory failed |
| 699 |
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) { |
| 700 |
mi_assert_internal(slice_index < segment->slice_entries); |
| 701 |
mi_slice_t* const slice = &segment->slices[slice_index]; |
| 702 |
mi_assert_internal(slice->xblock_size==0 || slice->xblock_size==1); |
| 703 |
|
| 704 |
// commit before changing the slice data |
| 705 |
if (!mi_segment_ensure_committed(segment, _mi_segment_page_start_from_slice(segment, slice, 0, NULL), slice_count * MI_SEGMENT_SLICE_SIZE, tld->stats)) { |
| 706 |
return NULL; // commit failed! |
| 707 |
} |
| 708 |
|
| 709 |
// convert the slices to a page |
| 710 |
slice->slice_offset = 0; |
| 711 |
slice->slice_count = (uint32_t)slice_count; |
| 712 |
mi_assert_internal(slice->slice_count == slice_count); |
| 713 |
const size_t bsize = slice_count * MI_SEGMENT_SLICE_SIZE; |
| 714 |
slice->xblock_size = (uint32_t)(bsize >= MI_HUGE_BLOCK_SIZE ? MI_HUGE_BLOCK_SIZE : bsize); |
| 715 |
mi_page_t* page = mi_slice_to_page(slice); |
| 716 |
mi_assert_internal(mi_page_block_size(page) == bsize); |
| 717 |
|
| 718 |
// set slice back pointers for the first MI_MAX_SLICE_OFFSET entries |
| 719 |
size_t extra = slice_count-1; |
| 720 |
if (extra > MI_MAX_SLICE_OFFSET) extra = MI_MAX_SLICE_OFFSET; |
| 721 |
if (slice_index + extra >= segment->slice_entries) extra = segment->slice_entries - slice_index - 1; // huge objects may have more slices than available entries in the segment->slices |
| 722 |
|
| 723 |
mi_slice_t* slice_next = slice + 1; |
| 724 |
for (size_t i = 1; i <= extra; i++, slice_next++) { |
| 725 |
slice_next->slice_offset = (uint32_t)(sizeof(mi_slice_t)*i); |
| 726 |
slice_next->slice_count = 0; |
| 727 |
slice_next->xblock_size = 1; |
| 728 |
} |
| 729 |
|
| 730 |
// and also for the last one (if not set already) (the last one is needed for coalescing and for large alignments) |
| 731 |
// note: the cast is needed for ubsan since the index can be larger than MI_SLICES_PER_SEGMENT for huge allocations (see #543) |
| 732 |
mi_slice_t* last = slice + slice_count - 1; |
| 733 |
mi_slice_t* end = (mi_slice_t*)mi_segment_slices_end(segment); |
| 734 |
if (last > end) last = end; |
| 735 |
if (last > slice) { |
| 736 |
last->slice_offset = (uint32_t)(sizeof(mi_slice_t) * (last - slice)); |
| 737 |
last->slice_count = 0; |
| 738 |
last->xblock_size = 1; |
| 739 |
} |
| 740 |
|
| 741 |
// and initialize the page |
| 742 |
page->is_committed = true; |
| 743 |
segment->used++; |
| 744 |
return page; |
| 745 |
} |
| 746 |
|
| 747 |
static void mi_segment_slice_split(mi_segment_t* segment, mi_slice_t* slice, size_t slice_count, mi_segments_tld_t* tld) { |
| 748 |
mi_assert_internal(_mi_ptr_segment(slice) == segment); |
| 749 |
mi_assert_internal(slice->slice_count >= slice_count); |
| 750 |
mi_assert_internal(slice->xblock_size > 0); // no more in free queue |
| 751 |
if (slice->slice_count <= slice_count) return; |
| 752 |
mi_assert_internal(segment->kind != MI_SEGMENT_HUGE); |
| 753 |
size_t next_index = mi_slice_index(slice) + slice_count; |
| 754 |
size_t next_count = slice->slice_count - slice_count; |
| 755 |
mi_segment_span_free(segment, next_index, next_count, false /* don't purge left-over part */, tld); |
| 756 |
slice->slice_count = (uint32_t)slice_count; |
| 757 |
} |
| 758 |
|
| 759 |
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) { |
| 760 |
mi_assert_internal(slice_count*MI_SEGMENT_SLICE_SIZE <= MI_LARGE_OBJ_SIZE_MAX); |
| 761 |
// search from best fit up |
| 762 |
mi_span_queue_t* sq = mi_span_queue_for(slice_count, tld); |
| 763 |
if (slice_count == 0) slice_count = 1; |
| 764 |
while (sq <= &tld->spans[MI_SEGMENT_BIN_MAX]) { |
| 765 |
for (mi_slice_t* slice = sq->first; slice != NULL; slice = slice->next) { |
| 766 |
if (slice->slice_count >= slice_count) { |
| 767 |
// found one |
| 768 |
mi_segment_t* segment = _mi_ptr_segment(slice); |
| 769 |
if (_mi_arena_memid_is_suitable(segment->memid, req_arena_id)) { |
| 770 |
// found a suitable page span |
| 771 |
mi_span_queue_delete(sq, slice); |
| 772 |
|
| 773 |
if (slice->slice_count > slice_count) { |
| 774 |
mi_segment_slice_split(segment, slice, slice_count, tld); |
| 775 |
} |
| 776 |
mi_assert_internal(slice != NULL && slice->slice_count == slice_count && slice->xblock_size > 0); |
| 777 |
mi_page_t* page = mi_segment_span_allocate(segment, mi_slice_index(slice), slice->slice_count, tld); |
| 778 |
if (page == NULL) { |
| 779 |
// commit failed; return NULL but first restore the slice |
| 780 |
mi_segment_span_free_coalesce(slice, tld); |
| 781 |
return NULL; |
| 782 |
} |
| 783 |
return page; |
| 784 |
} |
| 785 |
} |
| 786 |
} |
| 787 |
sq++; |
| 788 |
} |
| 789 |
// could not find a page.. |
| 790 |
return NULL; |
| 791 |
} |
| 792 |
|
| 793 |
|
| 794 |
/* ----------------------------------------------------------- |
| 795 |
Segment allocation |
| 796 |
----------------------------------------------------------- */ |
| 797 |
|
| 798 |
static mi_segment_t* mi_segment_os_alloc( size_t required, size_t page_alignment, bool eager_delayed, mi_arena_id_t req_arena_id, |
| 799 |
size_t* psegment_slices, size_t* ppre_size, size_t* pinfo_slices, |
| 800 |
bool commit, mi_segments_tld_t* tld, mi_os_tld_t* os_tld) |
| 801 |
|
| 802 |
{ |
| 803 |
mi_memid_t memid; |
| 804 |
bool allow_large = (!eager_delayed && (MI_SECURE == 0)); // only allow large OS pages once we are no longer lazy |
| 805 |
size_t align_offset = 0; |
| 806 |
size_t alignment = MI_SEGMENT_ALIGN; |
| 807 |
|
| 808 |
if (page_alignment > 0) { |
| 809 |
// mi_assert_internal(huge_page != NULL); |
| 810 |
mi_assert_internal(page_alignment >= MI_SEGMENT_ALIGN); |
| 811 |
alignment = page_alignment; |
| 812 |
const size_t info_size = (*pinfo_slices) * MI_SEGMENT_SLICE_SIZE; |
| 813 |
align_offset = _mi_align_up( info_size, MI_SEGMENT_ALIGN ); |
| 814 |
const size_t extra = align_offset - info_size; |
| 815 |
// recalculate due to potential guard pages |
| 816 |
*psegment_slices = mi_segment_calculate_slices(required + extra, ppre_size, pinfo_slices); |
| 817 |
|
| 818 |
// mi_page_t.slice_count type is uint32_t |
| 819 |
if (*psegment_slices > (size_t)UINT32_MAX) return NULL; |
| 820 |
} |
| 821 |
|
| 822 |
const size_t segment_size = (*psegment_slices) * MI_SEGMENT_SLICE_SIZE; |
| 823 |
mi_segment_t* segment = (mi_segment_t*)_mi_arena_alloc_aligned(segment_size, alignment, align_offset, commit, allow_large, req_arena_id, &memid, os_tld); |
| 824 |
if (segment == NULL) { |
| 825 |
return NULL; // failed to allocate |
| 826 |
} |
| 827 |
|
| 828 |
// ensure metadata part of the segment is committed |
| 829 |
mi_commit_mask_t commit_mask; |
| 830 |
if (memid.initially_committed) { |
| 831 |
mi_commit_mask_create_full(&commit_mask); |
| 832 |
} |
| 833 |
else { |
| 834 |
// at least commit the info slices |
| 835 |
const size_t commit_needed = _mi_divide_up((*pinfo_slices)*MI_SEGMENT_SLICE_SIZE, MI_COMMIT_SIZE); |
| 836 |
mi_assert_internal(commit_needed>0); |
| 837 |
mi_commit_mask_create(0, commit_needed, &commit_mask); |
| 838 |
mi_assert_internal(commit_needed*MI_COMMIT_SIZE >= (*pinfo_slices)*MI_SEGMENT_SLICE_SIZE); |
| 839 |
if (!_mi_os_commit(segment, commit_needed*MI_COMMIT_SIZE, NULL, tld->stats)) { |
| 840 |
_mi_arena_free(segment,segment_size,0,memid,tld->stats); |
| 841 |
return NULL; |
| 842 |
} |
| 843 |
} |
| 844 |
mi_assert_internal(segment != NULL && (uintptr_t)segment % MI_SEGMENT_SIZE == 0); |
| 845 |
|
| 846 |
segment->memid = memid; |
| 847 |
segment->allow_decommit = !memid.is_pinned; |
| 848 |
segment->allow_purge = segment->allow_decommit && (mi_option_get(mi_option_purge_delay) >= 0); |
| 849 |
segment->segment_size = segment_size; |
| 850 |
segment->commit_mask = commit_mask; |
| 851 |
segment->purge_expire = 0; |
| 852 |
mi_commit_mask_create_empty(&segment->purge_mask); |
| 853 |
mi_atomic_store_ptr_release(mi_segment_t, &segment->abandoned_next, NULL); // tsan |
| 854 |
|
| 855 |
mi_segments_track_size((long)(segment_size), tld); |
| 856 |
_mi_segment_map_allocated_at(segment); |
| 857 |
return segment; |
| 858 |
} |
| 859 |
|
| 860 |
|
| 861 |
// Allocate a segment from the OS aligned to `MI_SEGMENT_SIZE` . |
| 862 |
static mi_segment_t* mi_segment_alloc(size_t required, size_t page_alignment, mi_arena_id_t req_arena_id, mi_segments_tld_t* tld, mi_os_tld_t* os_tld, mi_page_t** huge_page) |
| 863 |
{ |
| 864 |
mi_assert_internal((required==0 && huge_page==NULL) || (required>0 && huge_page != NULL)); |
| 865 |
|
| 866 |
// calculate needed sizes first |
| 867 |
size_t info_slices; |
| 868 |
size_t pre_size; |
| 869 |
size_t segment_slices = mi_segment_calculate_slices(required, &pre_size, &info_slices); |
| 870 |
|
| 871 |
// mi_page_t.slice_count type is uint32_t |
| 872 |
if (segment_slices > (size_t)UINT32_MAX) return NULL; |
| 873 |
|
| 874 |
// Commit eagerly only if not the first N lazy segments (to reduce impact of many threads that allocate just a little) |
| 875 |
const bool eager_delay = (// !_mi_os_has_overcommit() && // never delay on overcommit systems |
| 876 |
_mi_current_thread_count() > 1 && // do not delay for the first N threads |
| 877 |
tld->count < (size_t)mi_option_get(mi_option_eager_commit_delay)); |
| 878 |
const bool eager = !eager_delay && mi_option_is_enabled(mi_option_eager_commit); |
| 879 |
bool commit = eager || (required > 0); |
| 880 |
|
| 881 |
// Allocate the segment from the OS |
| 882 |
mi_segment_t* segment = mi_segment_os_alloc(required, page_alignment, eager_delay, req_arena_id, |
| 883 |
&segment_slices, &pre_size, &info_slices, commit, tld, os_tld); |
| 884 |
if (segment == NULL) return NULL; |
| 885 |
|
| 886 |
// zero the segment info? -- not always needed as it may be zero initialized from the OS |
| 887 |
if (!segment->memid.initially_zero) { |
| 888 |
ptrdiff_t ofs = offsetof(mi_segment_t, next); |
| 889 |
size_t prefix = offsetof(mi_segment_t, slices) - ofs; |
| 890 |
size_t zsize = prefix + (sizeof(mi_slice_t) * (segment_slices + 1)); // one more |
| 891 |
_mi_memzero((uint8_t*)segment + ofs, zsize); |
| 892 |
} |
| 893 |
|
| 894 |
// initialize the rest of the segment info |
| 895 |
const size_t slice_entries = (segment_slices > MI_SLICES_PER_SEGMENT ? MI_SLICES_PER_SEGMENT : segment_slices); |
| 896 |
segment->segment_slices = segment_slices; |
| 897 |
segment->segment_info_slices = info_slices; |
| 898 |
segment->thread_id = _mi_thread_id(); |
| 899 |
segment->cookie = _mi_ptr_cookie(segment); |
| 900 |
segment->slice_entries = slice_entries; |
| 901 |
segment->kind = (required == 0 ? MI_SEGMENT_NORMAL : MI_SEGMENT_HUGE); |
| 902 |
|
| 903 |
// _mi_memzero(segment->slices, sizeof(mi_slice_t)*(info_slices+1)); |
| 904 |
_mi_stat_increase(&tld->stats->page_committed, mi_segment_info_size(segment)); |
| 905 |
|
| 906 |
// set up guard pages |
| 907 |
size_t guard_slices = 0; |
| 908 |
if (MI_SECURE>0) { |
| 909 |
// in secure mode, we set up a protected page in between the segment info |
| 910 |
// and the page data, and at the end of the segment. |
| 911 |
size_t os_pagesize = _mi_os_page_size(); |
| 912 |
mi_assert_internal(mi_segment_info_size(segment) - os_pagesize >= pre_size); |
| 913 |
_mi_os_protect((uint8_t*)segment + mi_segment_info_size(segment) - os_pagesize, os_pagesize); |
| 914 |
uint8_t* end = (uint8_t*)segment + mi_segment_size(segment) - os_pagesize; |
| 915 |
mi_segment_ensure_committed(segment, end, os_pagesize, tld->stats); |
| 916 |
_mi_os_protect(end, os_pagesize); |
| 917 |
if (slice_entries == segment_slices) segment->slice_entries--; // don't use the last slice :-( |
| 918 |
guard_slices = 1; |
| 919 |
} |
| 920 |
|
| 921 |
// reserve first slices for segment info |
| 922 |
mi_page_t* page0 = mi_segment_span_allocate(segment, 0, info_slices, tld); |
| 923 |
mi_assert_internal(page0!=NULL); if (page0==NULL) return NULL; // cannot fail as we always commit in advance |
| 924 |
mi_assert_internal(segment->used == 1); |
| 925 |
segment->used = 0; // don't count our internal slices towards usage |
| 926 |
|
| 927 |
// initialize initial free pages |
| 928 |
if (segment->kind == MI_SEGMENT_NORMAL) { // not a huge page |
| 929 |
mi_assert_internal(huge_page==NULL); |
| 930 |
mi_segment_span_free(segment, info_slices, segment->slice_entries - info_slices, false /* don't purge */, tld); |
| 931 |
} |
| 932 |
else { |
| 933 |
mi_assert_internal(huge_page!=NULL); |
| 934 |
mi_assert_internal(mi_commit_mask_is_empty(&segment->purge_mask)); |
| 935 |
mi_assert_internal(mi_commit_mask_is_full(&segment->commit_mask)); |
| 936 |
*huge_page = mi_segment_span_allocate(segment, info_slices, segment_slices - info_slices - guard_slices, tld); |
| 937 |
mi_assert_internal(*huge_page != NULL); // cannot fail as we commit in advance |
| 938 |
} |
| 939 |
|
| 940 |
mi_assert_expensive(mi_segment_is_valid(segment,tld)); |
| 941 |
return segment; |
| 942 |
} |
| 943 |
|
| 944 |
|
| 945 |
static void mi_segment_free(mi_segment_t* segment, bool force, mi_segments_tld_t* tld) { |
| 946 |
MI_UNUSED(force); |
| 947 |
mi_assert_internal(segment != NULL); |
| 948 |
mi_assert_internal(segment->next == NULL); |
| 949 |
mi_assert_internal(segment->used == 0); |
| 950 |
|
| 951 |
// Remove the free pages |
| 952 |
mi_slice_t* slice = &segment->slices[0]; |
| 953 |
const mi_slice_t* end = mi_segment_slices_end(segment); |
| 954 |
#if MI_DEBUG>1 |
| 955 |
size_t page_count = 0; |
| 956 |
#endif |
| 957 |
while (slice < end) { |
| 958 |
mi_assert_internal(slice->slice_count > 0); |
| 959 |
mi_assert_internal(slice->slice_offset == 0); |
| 960 |
mi_assert_internal(mi_slice_index(slice)==0 || slice->xblock_size == 0); // no more used pages .. |
| 961 |
if (slice->xblock_size == 0 && segment->kind != MI_SEGMENT_HUGE) { |
| 962 |
mi_segment_span_remove_from_queue(slice, tld); |
| 963 |
} |
| 964 |
#if MI_DEBUG>1 |
| 965 |
page_count++; |
| 966 |
#endif |
| 967 |
slice = slice + slice->slice_count; |
| 968 |
} |
| 969 |
mi_assert_internal(page_count == 2); // first page is allocated by the segment itself |
| 970 |
|
| 971 |
// stats |
| 972 |
_mi_stat_decrease(&tld->stats->page_committed, mi_segment_info_size(segment)); |
| 973 |
|
| 974 |
// return it to the OS |
| 975 |
mi_segment_os_free(segment, tld); |
| 976 |
} |
| 977 |
|
| 978 |
|
| 979 |
/* ----------------------------------------------------------- |
| 980 |
Page Free |
| 981 |
----------------------------------------------------------- */ |
| 982 |
|
| 983 |
static void mi_segment_abandon(mi_segment_t* segment, mi_segments_tld_t* tld); |
| 984 |
|
| 985 |
// note: can be called on abandoned pages |
| 986 |
static mi_slice_t* mi_segment_page_clear(mi_page_t* page, mi_segments_tld_t* tld) { |
| 987 |
mi_assert_internal(page->xblock_size > 0); |
| 988 |
mi_assert_internal(mi_page_all_free(page)); |
| 989 |
mi_segment_t* segment = _mi_ptr_segment(page); |
| 990 |
mi_assert_internal(segment->used > 0); |
| 991 |
#ifdef Py_GIL_DISABLED |
| 992 |
mi_assert_internal(page->qsbr_goal == 0); |
| 993 |
mi_assert_internal(page->qsbr_node.next == NULL); |
| 994 |
#endif |
| 995 |
|
| 996 |
size_t inuse = page->capacity * mi_page_block_size(page); |
| 997 |
_mi_stat_decrease(&tld->stats->page_committed, inuse); |
| 998 |
_mi_stat_decrease(&tld->stats->pages, 1); |
| 999 |
|
| 1000 |
// reset the page memory to reduce memory pressure? |
| 1001 |
if (segment->allow_decommit && mi_option_is_enabled(mi_option_deprecated_page_reset)) { |
| 1002 |
size_t psize; |
| 1003 |
uint8_t* start = _mi_page_start(segment, page, &psize); |
| 1004 |
_mi_os_reset(start, psize, tld->stats); |
| 1005 |
} |
| 1006 |
|
| 1007 |
// zero the page data, but not the segment fields |
| 1008 |
page->is_zero_init = false; |
| 1009 |
ptrdiff_t ofs = offsetof(mi_page_t, capacity); |
| 1010 |
_mi_memzero((uint8_t*)page + ofs, sizeof(*page) - ofs); |
| 1011 |
page->xblock_size = 1; |
| 1012 |
|
| 1013 |
// and free it |
| 1014 |
mi_slice_t* slice = mi_segment_span_free_coalesce(mi_page_to_slice(page), tld); |
| 1015 |
segment->used--; |
| 1016 |
// cannot assert segment valid as it is called during reclaim |
| 1017 |
// mi_assert_expensive(mi_segment_is_valid(segment, tld)); |
| 1018 |
return slice; |
| 1019 |
} |
| 1020 |
|
| 1021 |
void _mi_segment_page_free(mi_page_t* page, bool force, mi_segments_tld_t* tld) |
| 1022 |
{ |
| 1023 |
mi_assert(page != NULL); |
| 1024 |
|
| 1025 |
mi_segment_t* segment = _mi_page_segment(page); |
| 1026 |
mi_assert_expensive(mi_segment_is_valid(segment,tld)); |
| 1027 |
|
| 1028 |
// mark it as free now |
| 1029 |
mi_segment_page_clear(page, tld); |
| 1030 |
mi_assert_expensive(mi_segment_is_valid(segment, tld)); |
| 1031 |
|
| 1032 |
if (segment->used == 0) { |
| 1033 |
// no more used pages; remove from the free list and free the segment |
| 1034 |
mi_segment_free(segment, force, tld); |
| 1035 |
} |
| 1036 |
else if (segment->used == segment->abandoned) { |
| 1037 |
// only abandoned pages; remove from free list and abandon |
| 1038 |
mi_segment_abandon(segment,tld); |
| 1039 |
} |
| 1040 |
} |
| 1041 |
|
| 1042 |
|
| 1043 |
/* ----------------------------------------------------------- |
| 1044 |
Abandonment |
| 1045 |
|
| 1046 |
When threads terminate, they can leave segments with |
| 1047 |
live blocks (reachable through other threads). Such segments |
| 1048 |
are "abandoned" and will be reclaimed by other threads to |
| 1049 |
reuse their pages and/or free them eventually |
| 1050 |
|
| 1051 |
We maintain a global list of abandoned segments that are |
| 1052 |
reclaimed on demand. Since this is shared among threads |
| 1053 |
the implementation needs to avoid the A-B-A problem on |
| 1054 |
popping abandoned segments: <https://en.wikipedia.org/wiki/ABA_problem> |
| 1055 |
We use tagged pointers to avoid accidentally identifying |
| 1056 |
reused segments, much like stamped references in Java. |
| 1057 |
Secondly, we maintain a reader counter to avoid resetting |
| 1058 |
or decommitting segments that have a pending read operation. |
| 1059 |
|
| 1060 |
Note: the current implementation is one possible design; |
| 1061 |
another way might be to keep track of abandoned segments |
| 1062 |
in the arenas/segment_cache's. This would have the advantage of keeping |
| 1063 |
all concurrent code in one place and not needing to deal |
| 1064 |
with ABA issues. The drawback is that it is unclear how to |
| 1065 |
scan abandoned segments efficiently in that case as they |
| 1066 |
would be spread among all other segments in the arenas. |
| 1067 |
----------------------------------------------------------- */ |
| 1068 |
|
| 1069 |
// Use the bottom 20-bits (on 64-bit) of the aligned segment pointers |
| 1070 |
// to put in a tag that increments on update to avoid the A-B-A problem. |
| 1071 |
#define MI_TAGGED_MASK MI_SEGMENT_MASK |
| 1072 |
|
| 1073 |
static mi_segment_t* mi_tagged_segment_ptr(mi_tagged_segment_t ts) { |
| 1074 |
return (mi_segment_t*)(ts & ~MI_TAGGED_MASK); |
| 1075 |
} |
| 1076 |
|
| 1077 |
static mi_tagged_segment_t mi_tagged_segment(mi_segment_t* segment, mi_tagged_segment_t ts) { |
| 1078 |
mi_assert_internal(((uintptr_t)segment & MI_TAGGED_MASK) == 0); |
| 1079 |
uintptr_t tag = ((ts & MI_TAGGED_MASK) + 1) & MI_TAGGED_MASK; |
| 1080 |
return ((uintptr_t)segment | tag); |
| 1081 |
} |
| 1082 |
|
| 1083 |
mi_abandoned_pool_t _mi_abandoned_default; |
| 1084 |
|
| 1085 |
// Push on the visited list |
| 1086 |
static void mi_abandoned_visited_push(mi_abandoned_pool_t *pool, mi_segment_t* segment) { |
| 1087 |
mi_assert_internal(segment->thread_id == 0); |
| 1088 |
mi_assert_internal(mi_atomic_load_ptr_relaxed(mi_segment_t,&segment->abandoned_next) == NULL); |
| 1089 |
mi_assert_internal(segment->next == NULL); |
| 1090 |
mi_assert_internal(segment->used > 0); |
| 1091 |
mi_segment_t* anext = mi_atomic_load_ptr_relaxed(mi_segment_t, &pool->abandoned_visited); |
| 1092 |
do { |
| 1093 |
mi_atomic_store_ptr_release(mi_segment_t, &segment->abandoned_next, anext); |
| 1094 |
} while (!mi_atomic_cas_ptr_weak_release(mi_segment_t, &pool->abandoned_visited, &anext, segment)); |
| 1095 |
mi_atomic_increment_relaxed(&pool->abandoned_visited_count); |
| 1096 |
} |
| 1097 |
|
| 1098 |
// Move the visited list to the abandoned list. |
| 1099 |
static bool mi_abandoned_visited_revisit(mi_abandoned_pool_t *pool) |
| 1100 |
{ |
| 1101 |
// quick check if the visited list is empty |
| 1102 |
if (mi_atomic_load_ptr_relaxed(mi_segment_t, &pool->abandoned_visited) == NULL) return false; |
| 1103 |
|
| 1104 |
// grab the whole visited list |
| 1105 |
mi_segment_t* first = mi_atomic_exchange_ptr_acq_rel(mi_segment_t, &pool->abandoned_visited, NULL); |
| 1106 |
if (first == NULL) return false; |
| 1107 |
|
| 1108 |
// first try to swap directly if the abandoned list happens to be NULL |
| 1109 |
mi_tagged_segment_t afirst; |
| 1110 |
mi_tagged_segment_t ts = mi_atomic_load_relaxed(&pool->abandoned); |
| 1111 |
if (mi_tagged_segment_ptr(ts)==NULL) { |
| 1112 |
size_t count = mi_atomic_load_relaxed(&pool->abandoned_visited_count); |
| 1113 |
afirst = mi_tagged_segment(first, ts); |
| 1114 |
if (mi_atomic_cas_strong_acq_rel(&pool->abandoned, &ts, afirst)) { |
| 1115 |
mi_atomic_add_relaxed(&pool->abandoned_count, count); |
| 1116 |
mi_atomic_sub_relaxed(&pool->abandoned_visited_count, count); |
| 1117 |
return true; |
| 1118 |
} |
| 1119 |
} |
| 1120 |
|
| 1121 |
// find the last element of the visited list: O(n) |
| 1122 |
mi_segment_t* last = first; |
| 1123 |
mi_segment_t* next; |
| 1124 |
while ((next = mi_atomic_load_ptr_relaxed(mi_segment_t, &last->abandoned_next)) != NULL) { |
| 1125 |
last = next; |
| 1126 |
} |
| 1127 |
|
| 1128 |
// and atomically prepend to the abandoned list |
| 1129 |
// (no need to increase the readers as we don't access the abandoned segments) |
| 1130 |
mi_tagged_segment_t anext = mi_atomic_load_relaxed(&pool->abandoned); |
| 1131 |
size_t count; |
| 1132 |
do { |
| 1133 |
count = mi_atomic_load_relaxed(&pool->abandoned_visited_count); |
| 1134 |
mi_atomic_store_ptr_release(mi_segment_t, &last->abandoned_next, mi_tagged_segment_ptr(anext)); |
| 1135 |
afirst = mi_tagged_segment(first, anext); |
| 1136 |
} while (!mi_atomic_cas_weak_release(&pool->abandoned, &anext, afirst)); |
| 1137 |
mi_atomic_add_relaxed(&pool->abandoned_count, count); |
| 1138 |
mi_atomic_sub_relaxed(&pool->abandoned_visited_count, count); |
| 1139 |
return true; |
| 1140 |
} |
| 1141 |
|
| 1142 |
// Push on the abandoned list. |
| 1143 |
static void mi_abandoned_push(mi_abandoned_pool_t* pool, mi_segment_t* segment) { |
| 1144 |
mi_assert_internal(segment->thread_id == 0); |
| 1145 |
mi_assert_internal(mi_atomic_load_ptr_relaxed(mi_segment_t, &segment->abandoned_next) == NULL); |
| 1146 |
mi_assert_internal(segment->next == NULL); |
| 1147 |
mi_assert_internal(segment->used > 0); |
| 1148 |
mi_tagged_segment_t next; |
| 1149 |
mi_tagged_segment_t ts = mi_atomic_load_relaxed(&pool->abandoned); |
| 1150 |
do { |
| 1151 |
mi_atomic_store_ptr_release(mi_segment_t, &segment->abandoned_next, mi_tagged_segment_ptr(ts)); |
| 1152 |
next = mi_tagged_segment(segment, ts); |
| 1153 |
} while (!mi_atomic_cas_weak_release(&pool->abandoned, &ts, next)); |
| 1154 |
mi_atomic_increment_relaxed(&pool->abandoned_count); |
| 1155 |
} |
| 1156 |
|
| 1157 |
// Wait until there are no more pending reads on segments that used to be in the abandoned list |
| 1158 |
// called for example from `arena.c` before decommitting |
| 1159 |
void _mi_abandoned_await_readers(mi_abandoned_pool_t* pool) { |
| 1160 |
size_t n; |
| 1161 |
do { |
| 1162 |
n = mi_atomic_load_acquire(&pool->abandoned_readers); |
| 1163 |
if (n != 0) mi_atomic_yield(); |
| 1164 |
} while (n != 0); |
| 1165 |
} |
| 1166 |
|
| 1167 |
// Pop from the abandoned list |
| 1168 |
static mi_segment_t* mi_abandoned_pop(mi_abandoned_pool_t* pool) { |
| 1169 |
mi_segment_t* segment; |
| 1170 |
// Check efficiently if it is empty (or if the visited list needs to be moved) |
| 1171 |
mi_tagged_segment_t ts = mi_atomic_load_relaxed(&pool->abandoned); |
| 1172 |
segment = mi_tagged_segment_ptr(ts); |
| 1173 |
if mi_likely(segment == NULL) { |
| 1174 |
if mi_likely(!mi_abandoned_visited_revisit(pool)) { // try to swap in the visited list on NULL |
| 1175 |
return NULL; |
| 1176 |
} |
| 1177 |
} |
| 1178 |
|
| 1179 |
// Do a pop. We use a reader count to prevent |
| 1180 |
// a segment to be decommitted while a read is still pending, |
| 1181 |
// and a tagged pointer to prevent A-B-A link corruption. |
| 1182 |
// (this is called from `region.c:_mi_mem_free` for example) |
| 1183 |
mi_atomic_increment_relaxed(&pool->abandoned_readers); // ensure no segment gets decommitted |
| 1184 |
mi_tagged_segment_t next = 0; |
| 1185 |
ts = mi_atomic_load_acquire(&pool->abandoned); |
| 1186 |
do { |
| 1187 |
segment = mi_tagged_segment_ptr(ts); |
| 1188 |
if (segment != NULL) { |
| 1189 |
mi_segment_t* anext = mi_atomic_load_ptr_relaxed(mi_segment_t, &segment->abandoned_next); |
| 1190 |
next = mi_tagged_segment(anext, ts); // note: reads the segment's `abandoned_next` field so should not be decommitted |
| 1191 |
} |
| 1192 |
} while (segment != NULL && !mi_atomic_cas_weak_acq_rel(&pool->abandoned, &ts, next)); |
| 1193 |
mi_atomic_decrement_relaxed(&pool->abandoned_readers); // release reader lock |
| 1194 |
if (segment != NULL) { |
| 1195 |
mi_atomic_store_ptr_release(mi_segment_t, &segment->abandoned_next, NULL); |
| 1196 |
mi_atomic_decrement_relaxed(&pool->abandoned_count); |
| 1197 |
} |
| 1198 |
return segment; |
| 1199 |
} |
| 1200 |
|
| 1201 |
/* ----------------------------------------------------------- |
| 1202 |
Abandon segment/page |
| 1203 |
----------------------------------------------------------- */ |
| 1204 |
|
| 1205 |
static void mi_segment_abandon(mi_segment_t* segment, mi_segments_tld_t* tld) { |
| 1206 |
mi_assert_internal(segment->used == segment->abandoned); |
| 1207 |
mi_assert_internal(segment->used > 0); |
| 1208 |
mi_assert_internal(mi_atomic_load_ptr_relaxed(mi_segment_t, &segment->abandoned_next) == NULL); |
| 1209 |
mi_assert_internal(segment->abandoned_visits == 0); |
| 1210 |
mi_assert_expensive(mi_segment_is_valid(segment,tld)); |
| 1211 |
|
| 1212 |
// remove the free pages from the free page queues |
| 1213 |
mi_slice_t* slice = &segment->slices[0]; |
| 1214 |
const mi_slice_t* end = mi_segment_slices_end(segment); |
| 1215 |
while (slice < end) { |
| 1216 |
mi_assert_internal(slice->slice_count > 0); |
| 1217 |
mi_assert_internal(slice->slice_offset == 0); |
| 1218 |
if (slice->xblock_size == 0) { // a free page |
| 1219 |
mi_segment_span_remove_from_queue(slice,tld); |
| 1220 |
slice->xblock_size = 0; // but keep it free |
| 1221 |
} |
| 1222 |
slice = slice + slice->slice_count; |
| 1223 |
} |
| 1224 |
|
| 1225 |
// perform delayed decommits (forcing is much slower on mstress) |
| 1226 |
mi_segment_try_purge(segment, mi_option_is_enabled(mi_option_abandoned_page_purge) /* force? */, tld->stats); |
| 1227 |
|
| 1228 |
// all pages in the segment are abandoned; add it to the abandoned list |
| 1229 |
_mi_stat_increase(&tld->stats->segments_abandoned, 1); |
| 1230 |
mi_segments_track_size(-((long)mi_segment_size(segment)), tld); |
| 1231 |
segment->thread_id = 0; |
| 1232 |
mi_atomic_store_ptr_release(mi_segment_t, &segment->abandoned_next, NULL); |
| 1233 |
segment->abandoned_visits = 1; // from 0 to 1 to signify it is abandoned |
| 1234 |
mi_abandoned_push(tld->abandoned, segment); |
| 1235 |
} |
| 1236 |
|
| 1237 |
void _mi_segment_page_abandon(mi_page_t* page, mi_segments_tld_t* tld) { |
| 1238 |
mi_assert(page != NULL); |
| 1239 |
mi_assert_internal(mi_page_thread_free_flag(page)==MI_NEVER_DELAYED_FREE); |
| 1240 |
mi_assert_internal(mi_page_heap(page) == NULL); |
| 1241 |
mi_segment_t* segment = _mi_page_segment(page); |
| 1242 |
|
| 1243 |
mi_assert_expensive(mi_segment_is_valid(segment,tld)); |
| 1244 |
segment->abandoned++; |
| 1245 |
|
| 1246 |
_mi_stat_increase(&tld->stats->pages_abandoned, 1); |
| 1247 |
mi_assert_internal(segment->abandoned <= segment->used); |
| 1248 |
if (segment->used == segment->abandoned) { |
| 1249 |
// all pages are abandoned, abandon the entire segment |
| 1250 |
mi_segment_abandon(segment, tld); |
| 1251 |
} |
| 1252 |
} |
| 1253 |
|
| 1254 |
/* ----------------------------------------------------------- |
| 1255 |
Reclaim abandoned pages |
| 1256 |
----------------------------------------------------------- */ |
| 1257 |
|
| 1258 |
static mi_slice_t* mi_slices_start_iterate(mi_segment_t* segment, const mi_slice_t** end) { |
| 1259 |
mi_slice_t* slice = &segment->slices[0]; |
| 1260 |
*end = mi_segment_slices_end(segment); |
| 1261 |
mi_assert_internal(slice->slice_count>0 && slice->xblock_size>0); // segment allocated page |
| 1262 |
slice = slice + slice->slice_count; // skip the first segment allocated page |
| 1263 |
return slice; |
| 1264 |
} |
| 1265 |
|
| 1266 |
// Possibly free pages and check if free space is available |
| 1267 |
static bool mi_segment_check_free(mi_segment_t* segment, size_t slices_needed, size_t block_size, mi_segments_tld_t* tld) |
| 1268 |
{ |
| 1269 |
mi_assert_internal(block_size < MI_HUGE_BLOCK_SIZE); |
| 1270 |
mi_assert_internal(mi_segment_is_abandoned(segment)); |
| 1271 |
bool has_page = false; |
| 1272 |
|
| 1273 |
// for all slices |
| 1274 |
const mi_slice_t* end; |
| 1275 |
mi_slice_t* slice = mi_slices_start_iterate(segment, &end); |
| 1276 |
while (slice < end) { |
| 1277 |
mi_assert_internal(slice->slice_count > 0); |
| 1278 |
mi_assert_internal(slice->slice_offset == 0); |
| 1279 |
if (mi_slice_is_used(slice)) { // used page |
| 1280 |
// ensure used count is up to date and collect potential concurrent frees |
| 1281 |
mi_page_t* const page = mi_slice_to_page(slice); |
| 1282 |
_mi_page_free_collect(page, false); |
| 1283 |
if (mi_page_all_free(page) && _PyMem_mi_page_is_safe_to_free(page)) { |
| 1284 |
// if this page is all free now, free it without adding to any queues (yet) |
| 1285 |
mi_assert_internal(page->next == NULL && page->prev==NULL); |
| 1286 |
_mi_stat_decrease(&tld->stats->pages_abandoned, 1); |
| 1287 |
#ifdef Py_GIL_DISABLED |
| 1288 |
page->qsbr_goal = 0; |
| 1289 |
mi_assert_internal(page->qsbr_node.next == NULL); |
| 1290 |
#endif |
| 1291 |
segment->abandoned--; |
| 1292 |
slice = mi_segment_page_clear(page, tld); // re-assign slice due to coalesce! |
| 1293 |
mi_assert_internal(!mi_slice_is_used(slice)); |
| 1294 |
if (slice->slice_count >= slices_needed) { |
| 1295 |
has_page = true; |
| 1296 |
} |
| 1297 |
} |
| 1298 |
else { |
| 1299 |
if (page->xblock_size == block_size && mi_page_has_any_available(page)) { |
| 1300 |
// a page has available free blocks of the right size |
| 1301 |
has_page = true; |
| 1302 |
} |
| 1303 |
} |
| 1304 |
} |
| 1305 |
else { |
| 1306 |
// empty span |
| 1307 |
if (slice->slice_count >= slices_needed) { |
| 1308 |
has_page = true; |
| 1309 |
} |
| 1310 |
} |
| 1311 |
slice = slice + slice->slice_count; |
| 1312 |
} |
| 1313 |
return has_page; |
| 1314 |
} |
| 1315 |
|
| 1316 |
static mi_heap_t* mi_heap_by_tag(mi_heap_t* heap, uint8_t tag) { |
| 1317 |
if (heap->tag == tag) { |
| 1318 |
return heap; |
| 1319 |
} |
| 1320 |
for (mi_heap_t *curr = heap->tld->heaps; curr != NULL; curr = curr->next) { |
| 1321 |
if (curr->tag == tag) { |
| 1322 |
return curr; |
| 1323 |
} |
| 1324 |
} |
| 1325 |
return NULL; |
| 1326 |
} |
| 1327 |
|
| 1328 |
// Reclaim an abandoned segment; returns NULL if the segment was freed |
| 1329 |
// set `right_page_reclaimed` to `true` if it reclaimed a page of the right `block_size` that was not full. |
| 1330 |
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) { |
| 1331 |
mi_assert_internal(mi_atomic_load_ptr_relaxed(mi_segment_t, &segment->abandoned_next) == NULL); |
| 1332 |
mi_assert_expensive(mi_segment_is_valid(segment, tld)); |
| 1333 |
if (right_page_reclaimed != NULL) { *right_page_reclaimed = false; } |
| 1334 |
|
| 1335 |
segment->thread_id = _mi_thread_id(); |
| 1336 |
segment->abandoned_visits = 0; |
| 1337 |
mi_segments_track_size((long)mi_segment_size(segment), tld); |
| 1338 |
mi_assert_internal(segment->next == NULL); |
| 1339 |
_mi_stat_decrease(&tld->stats->segments_abandoned, 1); |
| 1340 |
|
| 1341 |
// for all slices |
| 1342 |
const mi_slice_t* end; |
| 1343 |
mi_slice_t* slice = mi_slices_start_iterate(segment, &end); |
| 1344 |
while (slice < end) { |
| 1345 |
mi_assert_internal(slice->slice_count > 0); |
| 1346 |
mi_assert_internal(slice->slice_offset == 0); |
| 1347 |
if (mi_slice_is_used(slice)) { |
| 1348 |
// in use: reclaim the page in our heap |
| 1349 |
mi_page_t* page = mi_slice_to_page(slice); |
| 1350 |
mi_heap_t* target_heap = mi_heap_by_tag(heap, page->tag); |
| 1351 |
mi_assert_internal(page->is_committed); |
| 1352 |
mi_assert_internal(mi_page_thread_free_flag(page)==MI_NEVER_DELAYED_FREE); |
| 1353 |
mi_assert_internal(mi_page_heap(page) == NULL); |
| 1354 |
mi_assert_internal(page->next == NULL && page->prev==NULL); |
| 1355 |
_mi_stat_decrease(&tld->stats->pages_abandoned, 1); |
| 1356 |
segment->abandoned--; |
| 1357 |
// set the heap again and allow delayed free again |
| 1358 |
mi_page_set_heap(page, target_heap); |
| 1359 |
_mi_page_use_delayed_free(page, MI_USE_DELAYED_FREE, true); // override never (after heap is set) |
| 1360 |
_mi_page_free_collect(page, false); // ensure used count is up to date |
| 1361 |
if (mi_page_all_free(page) && _PyMem_mi_page_is_safe_to_free(page)) { |
| 1362 |
// if everything free by now, free the page |
| 1363 |
#ifdef Py_GIL_DISABLED |
| 1364 |
page->qsbr_goal = 0; |
| 1365 |
mi_assert_internal(page->qsbr_node.next == NULL); |
| 1366 |
#endif |
| 1367 |
slice = mi_segment_page_clear(page, tld); // set slice again due to coalesceing |
| 1368 |
} |
| 1369 |
else { |
| 1370 |
// otherwise reclaim it into the heap |
| 1371 |
_mi_page_reclaim(target_heap, page); |
| 1372 |
if (requested_block_size == page->xblock_size && mi_page_has_any_available(page) && |
| 1373 |
requested_block_size <= MI_MEDIUM_OBJ_SIZE_MAX && heap == target_heap) { |
| 1374 |
if (right_page_reclaimed != NULL) { *right_page_reclaimed = true; } |
| 1375 |
} |
| 1376 |
} |
| 1377 |
} |
| 1378 |
else { |
| 1379 |
// the span is free, add it to our page queues |
| 1380 |
slice = mi_segment_span_free_coalesce(slice, tld); // set slice again due to coalesceing |
| 1381 |
} |
| 1382 |
mi_assert_internal(slice->slice_count>0 && slice->slice_offset==0); |
| 1383 |
slice = slice + slice->slice_count; |
| 1384 |
} |
| 1385 |
|
| 1386 |
mi_assert(segment->abandoned == 0); |
| 1387 |
if (segment->used == 0) { // due to page_clear |
| 1388 |
mi_assert_internal(right_page_reclaimed == NULL || !(*right_page_reclaimed)); |
| 1389 |
mi_segment_free(segment, false, tld); |
| 1390 |
return NULL; |
| 1391 |
} |
| 1392 |
else { |
| 1393 |
return segment; |
| 1394 |
} |
| 1395 |
} |
| 1396 |
|
| 1397 |
|
| 1398 |
void _mi_abandoned_reclaim_all(mi_heap_t* heap, mi_segments_tld_t* tld) { |
| 1399 |
mi_segment_t* segment; |
| 1400 |
while ((segment = mi_abandoned_pop(tld->abandoned)) != NULL) { |
| 1401 |
mi_segment_reclaim(segment, heap, 0, NULL, tld); |
| 1402 |
} |
| 1403 |
} |
| 1404 |
|
| 1405 |
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) |
| 1406 |
{ |
| 1407 |
*reclaimed = false; |
| 1408 |
mi_segment_t* segment; |
| 1409 |
long max_tries = mi_option_get_clamp(mi_option_max_segment_reclaim, 8, 1024); // limit the work to bound allocation times |
| 1410 |
while ((max_tries-- > 0) && ((segment = mi_abandoned_pop(tld->abandoned)) != NULL)) { |
| 1411 |
segment->abandoned_visits++; |
| 1412 |
// todo: an arena exclusive heap will potentially visit many abandoned unsuitable segments |
| 1413 |
// and push them into the visited list and use many tries. Perhaps we can skip non-suitable ones in a better way? |
| 1414 |
bool is_suitable = _mi_heap_memid_is_suitable(heap, segment->memid); |
| 1415 |
bool has_page = mi_segment_check_free(segment,needed_slices,block_size,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 |
// note1: we prefer to free a segment as that might lead to reclaiming another |
| 1419 |
// segment that is still partially used. |
| 1420 |
// note2: we could in principle optimize this by skipping reclaim and directly |
| 1421 |
// freeing but that would violate some invariants temporarily) |
| 1422 |
mi_segment_reclaim(segment, heap, 0, NULL, tld); |
| 1423 |
} |
| 1424 |
else if (has_page && is_suitable) { |
| 1425 |
// found a large enough free span, or a page of the right block_size with free space |
| 1426 |
// we return the result of reclaim (which is usually `segment`) as it might free |
| 1427 |
// the segment due to concurrent frees (in which case `NULL` is returned). |
| 1428 |
return mi_segment_reclaim(segment, heap, block_size, reclaimed, tld); |
| 1429 |
} |
| 1430 |
else if (segment->abandoned_visits > 3 && is_suitable) { |
| 1431 |
// always reclaim on 3rd visit to limit the abandoned queue length. |
| 1432 |
mi_segment_reclaim(segment, heap, 0, NULL, tld); |
| 1433 |
} |
| 1434 |
else { |
| 1435 |
// otherwise, push on the visited list so it gets not looked at too quickly again |
| 1436 |
mi_segment_try_purge(segment, true /* force? */, tld->stats); // force purge if needed as we may not visit soon again |
| 1437 |
mi_abandoned_visited_push(tld->abandoned, segment); |
| 1438 |
} |
| 1439 |
} |
| 1440 |
return NULL; |
| 1441 |
} |
| 1442 |
|
| 1443 |
|
| 1444 |
void _mi_abandoned_collect(mi_heap_t* heap, bool force, mi_segments_tld_t* tld) |
| 1445 |
{ |
| 1446 |
mi_segment_t* segment; |
| 1447 |
mi_abandoned_pool_t* pool = tld->abandoned; |
| 1448 |
int max_tries = (force ? 16*1024 : 1024); // limit latency |
| 1449 |
if (force) { |
| 1450 |
mi_abandoned_visited_revisit(pool); |
| 1451 |
} |
| 1452 |
while ((max_tries-- > 0) && ((segment = mi_abandoned_pop(pool)) != NULL)) { |
| 1453 |
mi_segment_check_free(segment,0,0,tld); // try to free up pages (due to concurrent frees) |
| 1454 |
if (segment->used == 0) { |
| 1455 |
// free the segment (by forced reclaim) to make it available to other threads. |
| 1456 |
// note: we could in principle optimize this by skipping reclaim and directly |
| 1457 |
// freeing but that would violate some invariants temporarily) |
| 1458 |
mi_segment_reclaim(segment, heap, 0, NULL, tld); |
| 1459 |
} |
| 1460 |
else { |
| 1461 |
// otherwise, purge if needed and push on the visited list |
| 1462 |
// note: forced purge can be expensive if many threads are destroyed/created as in mstress. |
| 1463 |
mi_segment_try_purge(segment, force, tld->stats); |
| 1464 |
mi_abandoned_visited_push(pool, segment); |
| 1465 |
} |
| 1466 |
} |
| 1467 |
} |
| 1468 |
|
| 1469 |
/* ----------------------------------------------------------- |
| 1470 |
Reclaim or allocate |
| 1471 |
----------------------------------------------------------- */ |
| 1472 |
|
| 1473 |
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) |
| 1474 |
{ |
| 1475 |
mi_assert_internal(block_size < MI_HUGE_BLOCK_SIZE); |
| 1476 |
mi_assert_internal(block_size <= MI_LARGE_OBJ_SIZE_MAX); |
| 1477 |
|
| 1478 |
// 1. try to reclaim an abandoned segment |
| 1479 |
bool reclaimed; |
| 1480 |
mi_segment_t* segment = mi_segment_try_reclaim(heap, needed_slices, block_size, &reclaimed, tld); |
| 1481 |
if (reclaimed) { |
| 1482 |
// reclaimed the right page right into the heap |
| 1483 |
mi_assert_internal(segment != NULL); |
| 1484 |
return NULL; // pretend out-of-memory as the page will be in the page queue of the heap with available blocks |
| 1485 |
} |
| 1486 |
else if (segment != NULL) { |
| 1487 |
// reclaimed a segment with a large enough empty span in it |
| 1488 |
return segment; |
| 1489 |
} |
| 1490 |
// 2. otherwise allocate a fresh segment |
| 1491 |
return mi_segment_alloc(0, 0, heap->arena_id, tld, os_tld, NULL); |
| 1492 |
} |
| 1493 |
|
| 1494 |
|
| 1495 |
/* ----------------------------------------------------------- |
| 1496 |
Page allocation |
| 1497 |
----------------------------------------------------------- */ |
| 1498 |
|
| 1499 |
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) |
| 1500 |
{ |
| 1501 |
mi_assert_internal(required <= MI_LARGE_OBJ_SIZE_MAX && page_kind <= MI_PAGE_LARGE); |
| 1502 |
|
| 1503 |
// find a free page |
| 1504 |
size_t page_size = _mi_align_up(required, (required > MI_MEDIUM_PAGE_SIZE ? MI_MEDIUM_PAGE_SIZE : MI_SEGMENT_SLICE_SIZE)); |
| 1505 |
size_t slices_needed = page_size / MI_SEGMENT_SLICE_SIZE; |
| 1506 |
mi_assert_internal(slices_needed * MI_SEGMENT_SLICE_SIZE == page_size); |
| 1507 |
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); |
| 1508 |
if (page==NULL) { |
| 1509 |
// no free page, allocate a new segment and try again |
| 1510 |
if (mi_segment_reclaim_or_alloc(heap, slices_needed, block_size, tld, os_tld) == NULL) { |
| 1511 |
// OOM or reclaimed a good page in the heap |
| 1512 |
return NULL; |
| 1513 |
} |
| 1514 |
else { |
| 1515 |
// otherwise try again |
| 1516 |
return mi_segments_page_alloc(heap, page_kind, required, block_size, tld, os_tld); |
| 1517 |
} |
| 1518 |
} |
| 1519 |
mi_assert_internal(page != NULL && page->slice_count*MI_SEGMENT_SLICE_SIZE == page_size); |
| 1520 |
mi_assert_internal(_mi_ptr_segment(page)->thread_id == _mi_thread_id()); |
| 1521 |
mi_segment_try_purge(_mi_ptr_segment(page), false, tld->stats); |
| 1522 |
return page; |
| 1523 |
} |
| 1524 |
|
| 1525 |
|
| 1526 |
|
| 1527 |
/* ----------------------------------------------------------- |
| 1528 |
Huge page allocation |
| 1529 |
----------------------------------------------------------- */ |
| 1530 |
|
| 1531 |
static mi_page_t* mi_segment_huge_page_alloc(size_t size, size_t page_alignment, mi_arena_id_t req_arena_id, mi_segments_tld_t* tld, mi_os_tld_t* os_tld) |
| 1532 |
{ |
| 1533 |
mi_page_t* page = NULL; |
| 1534 |
mi_segment_t* segment = mi_segment_alloc(size,page_alignment,req_arena_id,tld,os_tld,&page); |
| 1535 |
if (segment == NULL || page==NULL) return NULL; |
| 1536 |
mi_assert_internal(segment->used==1); |
| 1537 |
mi_assert_internal(mi_page_block_size(page) >= size); |
| 1538 |
#if MI_HUGE_PAGE_ABANDON |
| 1539 |
segment->thread_id = 0; // huge segments are immediately abandoned |
| 1540 |
#endif |
| 1541 |
|
| 1542 |
// for huge pages we initialize the xblock_size as we may |
| 1543 |
// overallocate to accommodate large alignments. |
| 1544 |
size_t psize; |
| 1545 |
uint8_t* start = _mi_segment_page_start(segment, page, &psize); |
| 1546 |
page->xblock_size = (psize > MI_HUGE_BLOCK_SIZE ? MI_HUGE_BLOCK_SIZE : (uint32_t)psize); |
| 1547 |
|
| 1548 |
// decommit the part of the prefix of a page that will not be used; this can be quite large (close to MI_SEGMENT_SIZE) |
| 1549 |
if (page_alignment > 0 && segment->allow_decommit) { |
| 1550 |
uint8_t* aligned_p = (uint8_t*)_mi_align_up((uintptr_t)start, page_alignment); |
| 1551 |
mi_assert_internal(_mi_is_aligned(aligned_p, page_alignment)); |
| 1552 |
mi_assert_internal(psize - (aligned_p - start) >= size); |
| 1553 |
uint8_t* decommit_start = start + sizeof(mi_block_t); // for the free list |
| 1554 |
ptrdiff_t decommit_size = aligned_p - decommit_start; |
| 1555 |
_mi_os_reset(decommit_start, decommit_size, &_mi_stats_main); // note: cannot use segment_decommit on huge segments |
| 1556 |
} |
| 1557 |
|
| 1558 |
return page; |
| 1559 |
} |
| 1560 |
|
| 1561 |
#if MI_HUGE_PAGE_ABANDON |
| 1562 |
// free huge block from another thread |
| 1563 |
void _mi_segment_huge_page_free(mi_segment_t* segment, mi_page_t* page, mi_block_t* block) { |
| 1564 |
// huge page segments are always abandoned and can be freed immediately by any thread |
| 1565 |
mi_assert_internal(segment->kind==MI_SEGMENT_HUGE); |
| 1566 |
mi_assert_internal(segment == _mi_page_segment(page)); |
| 1567 |
mi_assert_internal(mi_atomic_load_relaxed(&segment->thread_id)==0); |
| 1568 |
|
| 1569 |
// claim it and free |
| 1570 |
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. |
| 1571 |
// paranoia: if this it the last reference, the cas should always succeed |
| 1572 |
size_t expected_tid = 0; |
| 1573 |
if (mi_atomic_cas_strong_acq_rel(&segment->thread_id, &expected_tid, heap->thread_id)) { |
| 1574 |
mi_block_set_next(page, block, page->free); |
| 1575 |
page->free = block; |
| 1576 |
page->used--; |
| 1577 |
page->is_zero = false; |
| 1578 |
mi_assert(page->used == 0); |
| 1579 |
mi_tld_t* tld = heap->tld; |
| 1580 |
_mi_segment_page_free(page, true, &tld->segments); |
| 1581 |
} |
| 1582 |
#if (MI_DEBUG!=0) |
| 1583 |
else { |
| 1584 |
mi_assert_internal(false); |
| 1585 |
} |
| 1586 |
#endif |
| 1587 |
} |
| 1588 |
|
| 1589 |
#else |
| 1590 |
// reset memory of a huge block from another thread |
| 1591 |
void _mi_segment_huge_page_reset(mi_segment_t* segment, mi_page_t* page, mi_block_t* block) { |
| 1592 |
MI_UNUSED(page); |
| 1593 |
mi_assert_internal(segment->kind == MI_SEGMENT_HUGE); |
| 1594 |
mi_assert_internal(segment == _mi_page_segment(page)); |
| 1595 |
mi_assert_internal(page->used == 1); // this is called just before the free |
| 1596 |
mi_assert_internal(page->free == NULL); |
| 1597 |
if (segment->allow_decommit) { |
| 1598 |
size_t csize = mi_usable_size(block); |
| 1599 |
if (csize > sizeof(mi_block_t)) { |
| 1600 |
csize = csize - sizeof(mi_block_t); |
| 1601 |
uint8_t* p = (uint8_t*)block + sizeof(mi_block_t); |
| 1602 |
_mi_os_reset(p, csize, &_mi_stats_main); // note: cannot use segment_decommit on huge segments |
| 1603 |
} |
| 1604 |
} |
| 1605 |
} |
| 1606 |
#endif |
| 1607 |
|
| 1608 |
/* ----------------------------------------------------------- |
| 1609 |
Page allocation and free |
| 1610 |
----------------------------------------------------------- */ |
| 1611 |
mi_page_t* _mi_segment_page_alloc(mi_heap_t* heap, size_t block_size, size_t page_alignment, mi_segments_tld_t* tld, mi_os_tld_t* os_tld) { |
| 1612 |
mi_page_t* page; |
| 1613 |
if mi_unlikely(page_alignment > MI_ALIGNMENT_MAX) { |
| 1614 |
mi_assert_internal(_mi_is_power_of_two(page_alignment)); |
| 1615 |
mi_assert_internal(page_alignment >= MI_SEGMENT_SIZE); |
| 1616 |
if (page_alignment < MI_SEGMENT_SIZE) { page_alignment = MI_SEGMENT_SIZE; } |
| 1617 |
page = mi_segment_huge_page_alloc(block_size,page_alignment,heap->arena_id,tld,os_tld); |
| 1618 |
} |
| 1619 |
else if (block_size <= MI_SMALL_OBJ_SIZE_MAX) { |
| 1620 |
page = mi_segments_page_alloc(heap,MI_PAGE_SMALL,block_size,block_size,tld,os_tld); |
| 1621 |
} |
| 1622 |
else if (block_size <= MI_MEDIUM_OBJ_SIZE_MAX) { |
| 1623 |
page = mi_segments_page_alloc(heap,MI_PAGE_MEDIUM,MI_MEDIUM_PAGE_SIZE,block_size,tld, os_tld); |
| 1624 |
} |
| 1625 |
else if (block_size <= MI_LARGE_OBJ_SIZE_MAX) { |
| 1626 |
page = mi_segments_page_alloc(heap,MI_PAGE_LARGE,block_size,block_size,tld, os_tld); |
| 1627 |
} |
| 1628 |
else { |
| 1629 |
page = mi_segment_huge_page_alloc(block_size,page_alignment,heap->arena_id,tld,os_tld); |
| 1630 |
} |
| 1631 |
mi_assert_internal(page == NULL || _mi_heap_memid_is_suitable(heap, _mi_page_segment(page)->memid)); |
| 1632 |
mi_assert_expensive(page == NULL || mi_segment_is_valid(_mi_page_segment(page),tld)); |
| 1633 |
return page; |
| 1634 |
} |
| 1635 |
|
| 1636 |
/* ----------------------------------------------------------- |
| 1637 |
Visit blocks in abandoned segments |
| 1638 |
----------------------------------------------------------- */ |
| 1639 |
|
| 1640 |
static bool mi_segment_visit_page(mi_segment_t* segment, mi_page_t* page, bool visit_blocks, mi_block_visit_fun* visitor, void* arg) |
| 1641 |
{ |
| 1642 |
mi_heap_area_t area; |
| 1643 |
_mi_heap_area_init(&area, page); |
| 1644 |
if (!visitor(NULL, &area, NULL, area.block_size, arg)) return false; |
| 1645 |
if (visit_blocks) { |
| 1646 |
return _mi_heap_area_visit_blocks(&area, page, visitor, arg); |
| 1647 |
} |
| 1648 |
else { |
| 1649 |
return true; |
| 1650 |
} |
| 1651 |
} |
| 1652 |
|
| 1653 |
static bool mi_segment_visit_pages(mi_segment_t* segment, uint8_t page_tag, bool visit_blocks, mi_block_visit_fun* visitor, void* arg) { |
| 1654 |
const mi_slice_t* end; |
| 1655 |
mi_slice_t* slice = mi_slices_start_iterate(segment, &end); |
| 1656 |
while (slice < end) { |
| 1657 |
if (mi_slice_is_used(slice)) { |
| 1658 |
mi_page_t* const page = mi_slice_to_page(slice); |
| 1659 |
if (page->tag == page_tag) { |
| 1660 |
if (!mi_segment_visit_page(segment, page, visit_blocks, visitor, arg)) return false; |
| 1661 |
} |
| 1662 |
} |
| 1663 |
slice = slice + slice->slice_count; |
| 1664 |
} |
| 1665 |
return true; |
| 1666 |
} |
| 1667 |
|
| 1668 |
// Visit all blocks in a abandoned segments |
| 1669 |
bool _mi_abandoned_pool_visit_blocks(mi_abandoned_pool_t* pool, uint8_t page_tag, bool visit_blocks, mi_block_visit_fun* visitor, void* arg) { |
| 1670 |
// Note: this is not safe in any other thread is abandoning or claiming segments from the pool |
| 1671 |
mi_segment_t* segment = mi_tagged_segment_ptr(pool->abandoned); |
| 1672 |
while (segment != NULL) { |
| 1673 |
if (!mi_segment_visit_pages(segment, page_tag, visit_blocks, visitor, arg)) return false; |
| 1674 |
segment = segment->abandoned_next; |
| 1675 |
} |
| 1676 |
|
| 1677 |
segment = pool->abandoned_visited; |
| 1678 |
while (segment != NULL) { |
| 1679 |
if (!mi_segment_visit_pages(segment, page_tag, visit_blocks, visitor, arg)) return false; |
| 1680 |
segment = segment->abandoned_next; |
| 1681 |
} |
| 1682 |
|
| 1683 |
return true; |
| 1684 |
} |