segment.c
1 /* ---------------------------------------------------------------------------- 2 Copyright (c) 2018-2024, 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 uint8_t* mi_segment_raw_page_start(const mi_segment_t* segment, const mi_page_t* page, size_t* page_size); 17 18 /* -------------------------------------------------------------------------------- 19 Segment allocation 20 We allocate pages inside bigger "segments" (4MiB on 64-bit). This is to avoid 21 splitting VMA's on Linux and reduce fragmentation on other OS's. 22 Each thread owns its own segments. 23 24 Currently we have: 25 - small pages (64KiB), 64 in one segment 26 - medium pages (512KiB), 8 in one segment 27 - large pages (4MiB), 1 in one segment 28 - huge segments have 1 page in one segment that can be larger than `MI_SEGMENT_SIZE`. 29 it is used for blocks `> MI_LARGE_OBJ_SIZE_MAX` or with alignment `> MI_BLOCK_ALIGNMENT_MAX`. 30 31 The memory for a segment is usually committed on demand. 32 (i.e. we are careful to not touch the memory until we actually allocate a block there) 33 34 If a thread ends, it "abandons" pages that still contain live blocks. 35 Such segments are abondoned and these can be reclaimed by still running threads, 36 (much like work-stealing). 37 -------------------------------------------------------------------------------- */ 38 39 40 /* ----------------------------------------------------------- 41 Queue of segments containing free pages 42 ----------------------------------------------------------- */ 43 44 #if (MI_DEBUG>=3) 45 static bool mi_segment_queue_contains(const mi_segment_queue_t* queue, const mi_segment_t* segment) { 46 mi_assert_internal(segment != NULL); 47 mi_segment_t* list = queue->first; 48 while (list != NULL) { 49 if (list == segment) break; 50 mi_assert_internal(list->next==NULL || list->next->prev == list); 51 mi_assert_internal(list->prev==NULL || list->prev->next == list); 52 list = list->next; 53 } 54 return (list == segment); 55 } 56 #endif 57 58 /* 59 static bool mi_segment_queue_is_empty(const mi_segment_queue_t* queue) { 60 return (queue->first == NULL); 61 } 62 */ 63 64 static void mi_segment_queue_remove(mi_segment_queue_t* queue, mi_segment_t* segment) { 65 mi_assert_expensive(mi_segment_queue_contains(queue, segment)); 66 if (segment->prev != NULL) segment->prev->next = segment->next; 67 if (segment->next != NULL) segment->next->prev = segment->prev; 68 if (segment == queue->first) queue->first = segment->next; 69 if (segment == queue->last) queue->last = segment->prev; 70 segment->next = NULL; 71 segment->prev = NULL; 72 } 73 74 static void mi_segment_enqueue(mi_segment_queue_t* queue, mi_segment_t* segment) { 75 mi_assert_expensive(!mi_segment_queue_contains(queue, segment)); 76 segment->next = NULL; 77 segment->prev = queue->last; 78 if (queue->last != NULL) { 79 mi_assert_internal(queue->last->next == NULL); 80 queue->last->next = segment; 81 queue->last = segment; 82 } 83 else { 84 queue->last = queue->first = segment; 85 } 86 } 87 88 static mi_segment_queue_t* mi_segment_free_queue_of_kind(mi_page_kind_t kind, mi_segments_tld_t* tld) { 89 if (kind == MI_PAGE_SMALL) return &tld->small_free; 90 else if (kind == MI_PAGE_MEDIUM) return &tld->medium_free; 91 else return NULL; 92 } 93 94 static mi_segment_queue_t* mi_segment_free_queue(const mi_segment_t* segment, mi_segments_tld_t* tld) { 95 return mi_segment_free_queue_of_kind(segment->page_kind, tld); 96 } 97 98 // remove from free queue if it is in one 99 static void mi_segment_remove_from_free_queue(mi_segment_t* segment, mi_segments_tld_t* tld) { 100 mi_segment_queue_t* queue = mi_segment_free_queue(segment, tld); // may be NULL 101 bool in_queue = (queue!=NULL && (segment->next != NULL || segment->prev != NULL || queue->first == segment)); 102 if (in_queue) { 103 mi_segment_queue_remove(queue, segment); 104 } 105 } 106 107 static void mi_segment_insert_in_free_queue(mi_segment_t* segment, mi_segments_tld_t* tld) { 108 mi_segment_enqueue(mi_segment_free_queue(segment, tld), segment); 109 } 110 111 112 /* ----------------------------------------------------------- 113 Invariant checking 114 ----------------------------------------------------------- */ 115 116 #if (MI_DEBUG >= 2) || (MI_SECURE >= 2) 117 static size_t mi_segment_page_size(const mi_segment_t* segment) { 118 if (segment->capacity > 1) { 119 mi_assert_internal(segment->page_kind <= MI_PAGE_MEDIUM); 120 return ((size_t)1 << segment->page_shift); 121 } 122 else { 123 mi_assert_internal(segment->page_kind >= MI_PAGE_LARGE); 124 return segment->segment_size; 125 } 126 } 127 #endif 128 129 #if (MI_DEBUG>=2) 130 static bool mi_pages_purge_contains(const mi_page_t* page, mi_segments_tld_t* tld) { 131 mi_page_t* p = tld->pages_purge.first; 132 while (p != NULL) { 133 if (p == page) return true; 134 p = p->next; 135 } 136 return false; 137 } 138 #endif 139 140 #if (MI_DEBUG>=3) 141 static bool mi_segment_is_valid(const mi_segment_t* segment, mi_segments_tld_t* tld) { 142 mi_assert_internal(segment != NULL); 143 mi_assert_internal(_mi_ptr_cookie(segment) == segment->cookie); 144 mi_assert_internal(segment->used <= segment->capacity); 145 mi_assert_internal(segment->abandoned <= segment->used); 146 mi_assert_internal(segment->page_kind <= MI_PAGE_MEDIUM || segment->capacity == 1); // one large or huge page per segment 147 size_t nfree = 0; 148 for (size_t i = 0; i < segment->capacity; i++) { 149 const mi_page_t* const page = &segment->pages[i]; 150 if (!page->segment_in_use) { 151 nfree++; 152 } 153 if (page->segment_in_use) { 154 mi_assert_expensive(!mi_pages_purge_contains(page, tld)); 155 } 156 mi_assert_internal(page->is_huge == (segment->page_kind == MI_PAGE_HUGE)); 157 } 158 mi_assert_internal(nfree + segment->used == segment->capacity); 159 // mi_assert_internal(segment->thread_id == _mi_thread_id() || (segment->thread_id==0)); // or 0 160 mi_assert_internal(segment->page_kind == MI_PAGE_HUGE || 161 (mi_segment_page_size(segment) * segment->capacity == segment->segment_size)); 162 return true; 163 } 164 #endif 165 166 static bool mi_page_not_in_queue(const mi_page_t* page, mi_segments_tld_t* tld) { 167 mi_assert_internal(page != NULL); 168 if (page->next != NULL || page->prev != NULL) { 169 mi_assert_internal(mi_pages_purge_contains(page, tld)); 170 return false; 171 } 172 else { 173 // both next and prev are NULL, check for singleton list 174 return (tld->pages_purge.first != page && tld->pages_purge.last != page); 175 } 176 } 177 178 179 /* ----------------------------------------------------------- 180 Guard pages 181 ----------------------------------------------------------- */ 182 183 static void mi_segment_protect_range(void* p, size_t size, bool protect) { 184 if (protect) { 185 _mi_os_protect(p, size); 186 } 187 else { 188 _mi_os_unprotect(p, size); 189 } 190 } 191 192 static void mi_segment_protect(mi_segment_t* segment, bool protect, mi_os_tld_t* tld) { 193 // add/remove guard pages 194 if (MI_SECURE != 0) { 195 // in secure mode, we set up a protected page in between the segment info and the page data 196 const size_t os_psize = _mi_os_page_size(); 197 mi_assert_internal((segment->segment_info_size - os_psize) >= (sizeof(mi_segment_t) + ((segment->capacity - 1) * sizeof(mi_page_t)))); 198 mi_assert_internal(((uintptr_t)segment + segment->segment_info_size) % os_psize == 0); 199 mi_segment_protect_range((uint8_t*)segment + segment->segment_info_size - os_psize, os_psize, protect); 200 #if (MI_SECURE >= 2) 201 if (segment->capacity == 1) 202 #endif 203 { 204 // and protect the last (or only) page too 205 mi_assert_internal(MI_SECURE <= 1 || segment->page_kind >= MI_PAGE_LARGE); 206 uint8_t* start = (uint8_t*)segment + segment->segment_size - os_psize; 207 if (protect && !segment->memid.initially_committed) { 208 if (protect) { 209 // ensure secure page is committed 210 if (_mi_os_commit(start, os_psize, NULL, tld->stats)) { // if this fails that is ok (as it is an unaccessible page) 211 mi_segment_protect_range(start, os_psize, protect); 212 } 213 } 214 } 215 else { 216 mi_segment_protect_range(start, os_psize, protect); 217 } 218 } 219 #if (MI_SECURE >= 2) 220 else { 221 // or protect every page 222 const size_t page_size = mi_segment_page_size(segment); 223 for (size_t i = 0; i < segment->capacity; i++) { 224 if (segment->pages[i].is_committed) { 225 mi_segment_protect_range((uint8_t*)segment + (i+1)*page_size - os_psize, os_psize, protect); 226 } 227 } 228 } 229 #endif 230 } 231 } 232 233 /* ----------------------------------------------------------- 234 Page reset 235 ----------------------------------------------------------- */ 236 237 static void mi_page_purge(mi_segment_t* segment, mi_page_t* page, mi_segments_tld_t* tld) { 238 // todo: should we purge the guard page as well when MI_SECURE>=2 ? 239 mi_assert_internal(page->is_committed); 240 mi_assert_internal(!page->segment_in_use); 241 if (!segment->allow_purge) return; 242 mi_assert_internal(page->used == 0); 243 mi_assert_internal(page->free == NULL); 244 mi_assert_expensive(!mi_pages_purge_contains(page, tld)); 245 size_t psize; 246 void* start = mi_segment_raw_page_start(segment, page, &psize); 247 const bool needs_recommit = _mi_os_purge(start, psize, tld->stats); 248 if (needs_recommit) { page->is_committed = false; } 249 } 250 251 static bool mi_page_ensure_committed(mi_segment_t* segment, mi_page_t* page, mi_segments_tld_t* tld) { 252 if (page->is_committed) return true; 253 mi_assert_internal(segment->allow_decommit); 254 mi_assert_expensive(!mi_pages_purge_contains(page, tld)); 255 256 size_t psize; 257 uint8_t* start = mi_segment_raw_page_start(segment, page, &psize); 258 bool is_zero = false; 259 const size_t gsize = (MI_SECURE >= 2 ? _mi_os_page_size() : 0); 260 bool ok = _mi_os_commit(start, psize + gsize, &is_zero, tld->stats); 261 if (!ok) return false; // failed to commit! 262 page->is_committed = true; 263 page->used = 0; 264 page->free = NULL; 265 page->is_zero_init = is_zero; 266 if (gsize > 0) { 267 mi_segment_protect_range(start + psize, gsize, true); 268 } 269 return true; 270 } 271 272 273 /* ----------------------------------------------------------- 274 The free page queue 275 ----------------------------------------------------------- */ 276 277 // we re-use the `free` field for the expiration counter. Since this is a 278 // a pointer size field while the clock is always 64-bit we need to guard 279 // against overflow, we use substraction to check for expiry which works 280 // as long as the reset delay is under (2^30 - 1) milliseconds (~12 days) 281 static uint32_t mi_page_get_expire( mi_page_t* page ) { 282 return (uint32_t)((uintptr_t)page->free); 283 } 284 285 static void mi_page_set_expire( mi_page_t* page, uint32_t expire ) { 286 page->free = (mi_block_t*)((uintptr_t)expire); 287 } 288 289 static void mi_page_purge_set_expire(mi_page_t* page) { 290 mi_assert_internal(mi_page_get_expire(page)==0); 291 uint32_t expire = (uint32_t)_mi_clock_now() + mi_option_get(mi_option_purge_delay); 292 mi_page_set_expire(page, expire); 293 } 294 295 // we re-use the `free` field for the expiration counter. Since this is a 296 // a pointer size field while the clock is always 64-bit we need to guard 297 // against overflow, we use substraction to check for expiry which work 298 // as long as the reset delay is under (2^30 - 1) milliseconds (~12 days) 299 static bool mi_page_purge_is_expired(mi_page_t* page, mi_msecs_t now) { 300 int32_t expire = (int32_t)mi_page_get_expire(page); 301 return (((int32_t)now - expire) >= 0); 302 } 303 304 static void mi_segment_schedule_purge(mi_segment_t* segment, mi_page_t* page, mi_segments_tld_t* tld) { 305 mi_assert_internal(!page->segment_in_use); 306 mi_assert_internal(mi_page_not_in_queue(page,tld)); 307 mi_assert_expensive(!mi_pages_purge_contains(page, tld)); 308 mi_assert_internal(_mi_page_segment(page)==segment); 309 if (!segment->allow_purge) return; 310 311 if (mi_option_get(mi_option_purge_delay) == 0) { 312 // purge immediately? 313 mi_page_purge(segment, page, tld); 314 } 315 else if (mi_option_get(mi_option_purge_delay) > 0) { // no purging if the delay is negative 316 // otherwise push on the delayed page reset queue 317 mi_page_queue_t* pq = &tld->pages_purge; 318 // push on top 319 mi_page_purge_set_expire(page); 320 page->next = pq->first; 321 page->prev = NULL; 322 if (pq->first == NULL) { 323 mi_assert_internal(pq->last == NULL); 324 pq->first = pq->last = page; 325 } 326 else { 327 pq->first->prev = page; 328 pq->first = page; 329 } 330 } 331 } 332 333 static void mi_page_purge_remove(mi_page_t* page, mi_segments_tld_t* tld) { 334 if (mi_page_not_in_queue(page,tld)) return; 335 336 mi_page_queue_t* pq = &tld->pages_purge; 337 mi_assert_internal(pq!=NULL); 338 mi_assert_internal(!page->segment_in_use); 339 mi_assert_internal(mi_page_get_expire(page) != 0); 340 mi_assert_internal(mi_pages_purge_contains(page, tld)); 341 if (page->prev != NULL) page->prev->next = page->next; 342 if (page->next != NULL) page->next->prev = page->prev; 343 if (page == pq->last) pq->last = page->prev; 344 if (page == pq->first) pq->first = page->next; 345 page->next = page->prev = NULL; 346 mi_page_set_expire(page,0); 347 } 348 349 static void mi_segment_remove_all_purges(mi_segment_t* segment, bool force_purge, mi_segments_tld_t* tld) { 350 if (segment->memid.is_pinned) return; // never reset in huge OS pages 351 for (size_t i = 0; i < segment->capacity; i++) { 352 mi_page_t* page = &segment->pages[i]; 353 if (!page->segment_in_use) { 354 mi_page_purge_remove(page, tld); 355 if (force_purge && page->is_committed) { 356 mi_page_purge(segment, page, tld); 357 } 358 } 359 else { 360 mi_assert_internal(mi_page_not_in_queue(page,tld)); 361 } 362 } 363 } 364 365 static void mi_pages_try_purge(bool force, mi_segments_tld_t* tld) { 366 if (mi_option_get(mi_option_purge_delay) < 0) return; // purging is not allowed 367 368 mi_msecs_t now = _mi_clock_now(); 369 mi_page_queue_t* pq = &tld->pages_purge; 370 // from oldest up to the first that has not expired yet 371 mi_page_t* page = pq->last; 372 while (page != NULL && (force || mi_page_purge_is_expired(page,now))) { 373 mi_page_t* const prev = page->prev; // save previous field 374 mi_page_purge_remove(page, tld); // remove from the list to maintain invariant for mi_page_purge 375 mi_page_purge(_mi_page_segment(page), page, tld); 376 page = prev; 377 } 378 // discard the reset pages from the queue 379 pq->last = page; 380 if (page != NULL){ 381 page->next = NULL; 382 } 383 else { 384 pq->first = NULL; 385 } 386 } 387 388 389 /* ----------------------------------------------------------- 390 Segment size calculations 391 ----------------------------------------------------------- */ 392 393 static size_t mi_segment_raw_page_size(const mi_segment_t* segment) { 394 return (segment->page_kind == MI_PAGE_HUGE ? segment->segment_size : (size_t)1 << segment->page_shift); 395 } 396 397 // Raw start of the page available memory; can be used on uninitialized pages (only `segment_idx` must be set) 398 // The raw start is not taking aligned block allocation into consideration. 399 static uint8_t* mi_segment_raw_page_start(const mi_segment_t* segment, const mi_page_t* page, size_t* page_size) { 400 size_t psize = mi_segment_raw_page_size(segment); 401 uint8_t* p = (uint8_t*)segment + page->segment_idx * psize; 402 403 if (page->segment_idx == 0) { 404 // the first page starts after the segment info (and possible guard page) 405 p += segment->segment_info_size; 406 psize -= segment->segment_info_size; 407 } 408 409 #if (MI_SECURE > 1) // every page has an os guard page 410 psize -= _mi_os_page_size(); 411 #elif (MI_SECURE==1) // the last page has an os guard page at the end 412 if (page->segment_idx == segment->capacity - 1) { 413 psize -= _mi_os_page_size(); 414 } 415 #endif 416 417 if (page_size != NULL) *page_size = psize; 418 mi_assert_internal(page->block_size == 0 || _mi_ptr_page(p) == page); 419 mi_assert_internal(_mi_ptr_segment(p) == segment); 420 return p; 421 } 422 423 // Start of the page available memory; can be used on uninitialized pages (only `segment_idx` must be set) 424 uint8_t* _mi_segment_page_start(const mi_segment_t* segment, const mi_page_t* page, size_t* page_size) 425 { 426 size_t psize; 427 uint8_t* p = mi_segment_raw_page_start(segment, page, &psize); 428 const size_t block_size = mi_page_block_size(page); 429 if (/*page->segment_idx == 0 &&*/ block_size > 0 && block_size <= MI_MAX_ALIGN_GUARANTEE) { 430 // for small and medium objects, ensure the page start is aligned with the block size (PR#66 by kickunderscore) 431 mi_assert_internal(segment->page_kind <= MI_PAGE_MEDIUM); 432 size_t adjust = block_size - ((uintptr_t)p % block_size); 433 if (adjust < block_size && psize >= block_size + adjust) { 434 p += adjust; 435 psize -= adjust; 436 mi_assert_internal((uintptr_t)p % block_size == 0); 437 } 438 } 439 mi_assert_internal(_mi_is_aligned(p, MI_MAX_ALIGN_SIZE)); 440 mi_assert_internal(block_size == 0 || block_size > MI_MAX_ALIGN_GUARANTEE || _mi_is_aligned(p,block_size)); 441 442 if (page_size != NULL) *page_size = psize; 443 mi_assert_internal(_mi_ptr_page(p) == page); 444 mi_assert_internal(_mi_ptr_segment(p) == segment); 445 return p; 446 } 447 448 449 static size_t mi_segment_calculate_sizes(size_t capacity, size_t required, size_t* pre_size, size_t* info_size) 450 { 451 const size_t minsize = sizeof(mi_segment_t) + ((capacity - 1) * sizeof(mi_page_t)) + 16 /* padding */; 452 size_t guardsize = 0; 453 size_t isize = 0; 454 455 456 if (MI_SECURE == 0) { 457 // normally no guard pages 458 #if MI_DEBUG_GUARDED 459 isize = _mi_align_up(minsize, _mi_os_page_size()); 460 #else 461 isize = _mi_align_up(minsize, 16 * MI_MAX_ALIGN_SIZE); 462 #endif 463 } 464 else { 465 // in secure mode, we set up a protected page in between the segment info 466 // and the page data (and one at the end of the segment) 467 const size_t page_size = _mi_os_page_size(); 468 isize = _mi_align_up(minsize, page_size); 469 guardsize = page_size; 470 //required = _mi_align_up(required, isize + guardsize); 471 } 472 473 if (info_size != NULL) *info_size = isize; 474 if (pre_size != NULL) *pre_size = isize + guardsize; 475 return (required==0 ? MI_SEGMENT_SIZE : _mi_align_up( required + isize + 2*guardsize, MI_PAGE_HUGE_ALIGN) ); 476 } 477 478 479 /* ---------------------------------------------------------------------------- 480 Segment caches 481 We keep a small segment cache per thread to increase local 482 reuse and avoid setting/clearing guard pages in secure mode. 483 ------------------------------------------------------------------------------- */ 484 485 static void mi_segments_track_size(long segment_size, mi_segments_tld_t* tld) { 486 if (segment_size>=0) _mi_stat_increase(&tld->stats->segments,1); 487 else _mi_stat_decrease(&tld->stats->segments,1); 488 tld->count += (segment_size >= 0 ? 1 : -1); 489 if (tld->count > tld->peak_count) tld->peak_count = tld->count; 490 tld->current_size += segment_size; 491 if (tld->current_size > tld->peak_size) tld->peak_size = tld->current_size; 492 } 493 494 static void mi_segment_os_free(mi_segment_t* segment, size_t segment_size, mi_segments_tld_t* tld) { 495 segment->thread_id = 0; 496 _mi_segment_map_freed_at(segment); 497 mi_segments_track_size(-((long)segment_size),tld); 498 if (segment->was_reclaimed) { 499 tld->reclaim_count--; 500 segment->was_reclaimed = false; 501 } 502 503 if (MI_SECURE != 0) { 504 mi_assert_internal(!segment->memid.is_pinned); 505 mi_segment_protect(segment, false, tld->os); // ensure no more guard pages are set 506 } 507 508 bool fully_committed = true; 509 size_t committed_size = 0; 510 const size_t page_size = mi_segment_raw_page_size(segment); 511 for (size_t i = 0; i < segment->capacity; i++) { 512 mi_page_t* page = &segment->pages[i]; 513 if (page->is_committed) { committed_size += page_size; } 514 if (!page->is_committed) { fully_committed = false; } 515 } 516 MI_UNUSED(fully_committed); 517 mi_assert_internal((fully_committed && committed_size == segment_size) || (!fully_committed && committed_size < segment_size)); 518 519 _mi_arena_free(segment, segment_size, committed_size, segment->memid, tld->stats); 520 } 521 522 // called from `heap_collect`. 523 void _mi_segments_collect(bool force, mi_segments_tld_t* tld) { 524 mi_pages_try_purge(force,tld); 525 #if MI_DEBUG>=2 526 if (!_mi_is_main_thread()) { 527 mi_assert_internal(tld->pages_purge.first == NULL); 528 mi_assert_internal(tld->pages_purge.last == NULL); 529 } 530 #endif 531 } 532 533 534 /* ----------------------------------------------------------- 535 Segment allocation 536 ----------------------------------------------------------- */ 537 538 static mi_segment_t* mi_segment_os_alloc(bool eager_delayed, size_t page_alignment, mi_arena_id_t req_arena_id, 539 size_t pre_size, size_t info_size, bool commit, size_t segment_size, 540 mi_segments_tld_t* tld, mi_os_tld_t* tld_os) 541 { 542 mi_memid_t memid; 543 bool allow_large = (!eager_delayed && (MI_SECURE == 0)); // only allow large OS pages once we are no longer lazy 544 size_t align_offset = 0; 545 size_t alignment = MI_SEGMENT_SIZE; 546 if (page_alignment > 0) { 547 alignment = page_alignment; 548 align_offset = _mi_align_up(pre_size, MI_SEGMENT_SIZE); 549 segment_size = segment_size + (align_offset - pre_size); // adjust the segment size 550 } 551 552 mi_segment_t* segment = (mi_segment_t*)_mi_arena_alloc_aligned(segment_size, alignment, align_offset, commit, allow_large, req_arena_id, &memid, tld_os); 553 if (segment == NULL) { 554 return NULL; // failed to allocate 555 } 556 557 if (!memid.initially_committed) { 558 // ensure the initial info is committed 559 mi_assert_internal(!memid.is_pinned); 560 bool ok = _mi_os_commit(segment, pre_size, NULL, tld_os->stats); 561 if (!ok) { 562 // commit failed; we cannot touch the memory: free the segment directly and return `NULL` 563 _mi_arena_free(segment, segment_size, 0, memid, tld_os->stats); 564 return NULL; 565 } 566 } 567 568 MI_UNUSED(info_size); 569 segment->memid = memid; 570 segment->allow_decommit = !memid.is_pinned; 571 segment->allow_purge = segment->allow_decommit && (mi_option_get(mi_option_purge_delay) >= 0); 572 segment->segment_size = segment_size; 573 segment->subproc = tld->subproc; 574 mi_segments_track_size((long)(segment_size), tld); 575 _mi_segment_map_allocated_at(segment); 576 return segment; 577 } 578 579 // Allocate a segment from the OS aligned to `MI_SEGMENT_SIZE` . 580 static mi_segment_t* mi_segment_alloc(size_t required, mi_page_kind_t page_kind, size_t page_shift, size_t page_alignment, 581 mi_arena_id_t req_arena_id, mi_segments_tld_t* tld, mi_os_tld_t* os_tld) 582 { 583 // required is only > 0 for huge page allocations 584 mi_assert_internal((required > 0 && page_kind > MI_PAGE_LARGE)|| (required==0 && page_kind <= MI_PAGE_LARGE)); 585 586 // calculate needed sizes first 587 size_t capacity; 588 if (page_kind == MI_PAGE_HUGE) { 589 mi_assert_internal(page_shift == MI_SEGMENT_SHIFT + 1 && required > 0); 590 capacity = 1; 591 } 592 else { 593 mi_assert_internal(required == 0 && page_alignment == 0); 594 size_t page_size = (size_t)1 << page_shift; 595 capacity = MI_SEGMENT_SIZE / page_size; 596 mi_assert_internal(MI_SEGMENT_SIZE % page_size == 0); 597 mi_assert_internal(capacity >= 1 && capacity <= MI_SMALL_PAGES_PER_SEGMENT); 598 } 599 size_t info_size; 600 size_t pre_size; 601 const size_t init_segment_size = mi_segment_calculate_sizes(capacity, required, &pre_size, &info_size); 602 mi_assert_internal(init_segment_size >= required); 603 604 // Initialize parameters 605 const bool eager_delayed = (page_kind <= MI_PAGE_MEDIUM && // don't delay for large objects 606 // !_mi_os_has_overcommit() && // never delay on overcommit systems 607 _mi_current_thread_count() > 1 && // do not delay for the first N threads 608 tld->peak_count < (size_t)mi_option_get(mi_option_eager_commit_delay)); 609 const bool eager = !eager_delayed && mi_option_is_enabled(mi_option_eager_commit); 610 const bool init_commit = eager; // || (page_kind >= MI_PAGE_LARGE); 611 612 // Allocate the segment from the OS (segment_size can change due to alignment) 613 mi_segment_t* segment = mi_segment_os_alloc(eager_delayed, page_alignment, req_arena_id, pre_size, info_size, init_commit, init_segment_size, tld, os_tld); 614 if (segment == NULL) return NULL; 615 mi_assert_internal(segment != NULL && (uintptr_t)segment % MI_SEGMENT_SIZE == 0); 616 mi_assert_internal(segment->memid.is_pinned ? segment->memid.initially_committed : true); 617 618 // zero the segment info (but not the `mem` fields) 619 ptrdiff_t ofs = offsetof(mi_segment_t, next); 620 _mi_memzero((uint8_t*)segment + ofs, info_size - ofs); 621 622 // initialize pages info 623 const bool is_huge = (page_kind == MI_PAGE_HUGE); 624 for (size_t i = 0; i < capacity; i++) { 625 mi_assert_internal(i <= 255); 626 segment->pages[i].segment_idx = (uint8_t)i; 627 segment->pages[i].is_committed = segment->memid.initially_committed; 628 segment->pages[i].is_zero_init = segment->memid.initially_zero; 629 segment->pages[i].is_huge = is_huge; 630 } 631 632 // initialize 633 segment->page_kind = page_kind; 634 segment->capacity = capacity; 635 segment->page_shift = page_shift; 636 segment->segment_info_size = pre_size; 637 segment->thread_id = _mi_thread_id(); 638 segment->cookie = _mi_ptr_cookie(segment); 639 640 // set protection 641 mi_segment_protect(segment, true, tld->os); 642 643 // insert in free lists for small and medium pages 644 if (page_kind <= MI_PAGE_MEDIUM) { 645 mi_segment_insert_in_free_queue(segment, tld); 646 } 647 648 return segment; 649 } 650 651 652 static void mi_segment_free(mi_segment_t* segment, bool force, mi_segments_tld_t* tld) { 653 MI_UNUSED(force); 654 mi_assert(segment != NULL); 655 // don't purge as we are freeing now 656 mi_segment_remove_all_purges(segment, false /* don't force as we are about to free */, tld); 657 mi_segment_remove_from_free_queue(segment, tld); 658 659 mi_assert_expensive(!mi_segment_queue_contains(&tld->small_free, segment)); 660 mi_assert_expensive(!mi_segment_queue_contains(&tld->medium_free, segment)); 661 mi_assert(segment->next == NULL); 662 mi_assert(segment->prev == NULL); 663 _mi_stat_decrease(&tld->stats->page_committed, segment->segment_info_size); 664 665 // return it to the OS 666 mi_segment_os_free(segment, segment->segment_size, tld); 667 } 668 669 /* ----------------------------------------------------------- 670 Free page management inside a segment 671 ----------------------------------------------------------- */ 672 673 674 static bool mi_segment_has_free(const mi_segment_t* segment) { 675 return (segment->used < segment->capacity); 676 } 677 678 static bool mi_segment_page_claim(mi_segment_t* segment, mi_page_t* page, mi_segments_tld_t* tld) { 679 mi_assert_internal(_mi_page_segment(page) == segment); 680 mi_assert_internal(!page->segment_in_use); 681 mi_page_purge_remove(page, tld); 682 683 // check commit 684 if (!mi_page_ensure_committed(segment, page, tld)) return false; 685 686 // set in-use before doing unreset to prevent delayed reset 687 page->segment_in_use = true; 688 segment->used++; 689 mi_assert_internal(page->segment_in_use && page->is_committed && page->used==0 && !mi_pages_purge_contains(page,tld)); 690 mi_assert_internal(segment->used <= segment->capacity); 691 if (segment->used == segment->capacity && segment->page_kind <= MI_PAGE_MEDIUM) { 692 // if no more free pages, remove from the queue 693 mi_assert_internal(!mi_segment_has_free(segment)); 694 mi_segment_remove_from_free_queue(segment, tld); 695 } 696 return true; 697 } 698 699 700 /* ----------------------------------------------------------- 701 Free 702 ----------------------------------------------------------- */ 703 704 static void mi_segment_abandon(mi_segment_t* segment, mi_segments_tld_t* tld); 705 706 // clear page data; can be called on abandoned segments 707 static void mi_segment_page_clear(mi_segment_t* segment, mi_page_t* page, mi_segments_tld_t* tld) 708 { 709 mi_assert_internal(page->segment_in_use); 710 mi_assert_internal(mi_page_all_free(page)); 711 mi_assert_internal(page->is_committed); 712 mi_assert_internal(mi_page_not_in_queue(page, tld)); 713 714 size_t inuse = page->capacity * mi_page_block_size(page); 715 _mi_stat_decrease(&tld->stats->page_committed, inuse); 716 _mi_stat_decrease(&tld->stats->pages, 1); 717 718 page->is_zero_init = false; 719 page->segment_in_use = false; 720 721 // zero the page data, but not the segment fields and capacity, page start, and block_size (for page size calculations) 722 size_t block_size = page->block_size; 723 uint8_t block_size_shift = page->block_size_shift; 724 uint8_t heap_tag = page->heap_tag; 725 uint8_t* page_start = page->page_start; 726 uint16_t capacity = page->capacity; 727 uint16_t reserved = page->reserved; 728 ptrdiff_t ofs = offsetof(mi_page_t,capacity); 729 _mi_memzero((uint8_t*)page + ofs, sizeof(*page) - ofs); 730 page->capacity = capacity; 731 page->reserved = reserved; 732 page->block_size = block_size; 733 page->block_size_shift = block_size_shift; 734 page->heap_tag = heap_tag; 735 page->page_start = page_start; 736 segment->used--; 737 738 // schedule purge 739 mi_segment_schedule_purge(segment, page, tld); 740 741 page->capacity = 0; // after purge these can be zero'd now 742 page->reserved = 0; 743 } 744 745 void _mi_segment_page_free(mi_page_t* page, bool force, mi_segments_tld_t* tld) 746 { 747 mi_assert(page != NULL); 748 mi_segment_t* segment = _mi_page_segment(page); 749 mi_assert_expensive(mi_segment_is_valid(segment,tld)); 750 mi_pages_try_purge(false /*force?*/, tld); 751 752 // mark it as free now 753 mi_segment_page_clear(segment, page, tld); 754 755 if (segment->used == 0) { 756 // no more used pages; remove from the free list and free the segment 757 mi_segment_free(segment, force, tld); 758 } 759 else { 760 if (segment->used == segment->abandoned) { 761 // only abandoned pages; remove from free list and abandon 762 mi_segment_abandon(segment,tld); 763 } 764 else if (segment->used + 1 == segment->capacity) { 765 mi_assert_internal(segment->page_kind <= MI_PAGE_MEDIUM); // large and huge pages are always the single page in a segment 766 if (segment->page_kind <= MI_PAGE_MEDIUM) { 767 // move back to segments free list 768 mi_segment_insert_in_free_queue(segment,tld); 769 } 770 } 771 } 772 } 773 774 775 /* ----------------------------------------------------------- 776 Abandonment 777 778 When threads terminate, they can leave segments with 779 live blocks (reached through other threads). Such segments 780 are "abandoned" and will be reclaimed by other threads to 781 reuse their pages and/or free them eventually. The 782 `thread_id` of such segments is 0. 783 784 When a block is freed in an abandoned segment, the segment 785 is reclaimed into that thread. 786 787 Moreover, if threads are looking for a fresh segment, they 788 will first consider abondoned segments -- these can be found 789 by scanning the arena memory 790 (segments outside arena memoryare only reclaimed by a free). 791 ----------------------------------------------------------- */ 792 793 /* ----------------------------------------------------------- 794 Abandon segment/page 795 ----------------------------------------------------------- */ 796 797 static void mi_segment_abandon(mi_segment_t* segment, mi_segments_tld_t* tld) { 798 mi_assert_internal(segment->used == segment->abandoned); 799 mi_assert_internal(segment->used > 0); 800 mi_assert_expensive(mi_segment_is_valid(segment, tld)); 801 802 // Potentially force purge. Only abandoned segments in arena memory can be 803 // reclaimed without a free so if a segment is not from an arena we force purge here to be conservative. 804 mi_pages_try_purge(false /*force?*/,tld); 805 const bool force_purge = (segment->memid.memkind != MI_MEM_ARENA) || mi_option_is_enabled(mi_option_abandoned_page_purge); 806 mi_segment_remove_all_purges(segment, force_purge, tld); 807 808 // remove the segment from the free page queue if needed 809 mi_segment_remove_from_free_queue(segment, tld); 810 mi_assert_internal(segment->next == NULL && segment->prev == NULL); 811 812 // all pages in the segment are abandoned; add it to the abandoned list 813 _mi_stat_increase(&tld->stats->segments_abandoned, 1); 814 mi_segments_track_size(-((long)segment->segment_size), tld); 815 segment->abandoned_visits = 0; 816 if (segment->was_reclaimed) { 817 tld->reclaim_count--; 818 segment->was_reclaimed = false; 819 } 820 _mi_arena_segment_mark_abandoned(segment); 821 } 822 823 void _mi_segment_page_abandon(mi_page_t* page, mi_segments_tld_t* tld) { 824 mi_assert(page != NULL); 825 mi_assert_internal(mi_page_thread_free_flag(page)==MI_NEVER_DELAYED_FREE); 826 mi_assert_internal(mi_page_heap(page) == NULL); 827 mi_segment_t* segment = _mi_page_segment(page); 828 mi_assert_expensive(!mi_pages_purge_contains(page, tld)); 829 mi_assert_expensive(mi_segment_is_valid(segment, tld)); 830 segment->abandoned++; 831 _mi_stat_increase(&tld->stats->pages_abandoned, 1); 832 mi_assert_internal(segment->abandoned <= segment->used); 833 if (segment->used == segment->abandoned) { 834 // all pages are abandoned, abandon the entire segment 835 mi_segment_abandon(segment, tld); 836 } 837 } 838 839 /* ----------------------------------------------------------- 840 Reclaim abandoned pages 841 ----------------------------------------------------------- */ 842 843 // Possibly clear pages and check if free space is available 844 static bool mi_segment_check_free(mi_segment_t* segment, size_t block_size, bool* all_pages_free) 845 { 846 mi_assert_internal(mi_atomic_load_relaxed(&segment->thread_id) == 0); 847 bool has_page = false; 848 size_t pages_used = 0; 849 size_t pages_used_empty = 0; 850 for (size_t i = 0; i < segment->capacity; i++) { 851 mi_page_t* page = &segment->pages[i]; 852 if (page->segment_in_use) { 853 pages_used++; 854 // ensure used count is up to date and collect potential concurrent frees 855 _mi_page_free_collect(page, false); 856 if (mi_page_all_free(page)) { 857 // if everything free already, page can be reused for some block size 858 // note: don't clear the page yet as we can only OS reset it once it is reclaimed 859 pages_used_empty++; 860 has_page = true; 861 } 862 else if (mi_page_block_size(page) == block_size && mi_page_has_any_available(page)) { 863 // a page has available free blocks of the right size 864 has_page = true; 865 } 866 } 867 else { 868 // whole empty page 869 has_page = true; 870 } 871 } 872 mi_assert_internal(pages_used == segment->used && pages_used >= pages_used_empty); 873 if (all_pages_free != NULL) { 874 *all_pages_free = ((pages_used - pages_used_empty) == 0); 875 } 876 return has_page; 877 } 878 879 880 // Reclaim a segment; returns NULL if the segment was freed 881 // set `right_page_reclaimed` to `true` if it reclaimed a page of the right `block_size` that was not full. 882 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) { 883 if (right_page_reclaimed != NULL) { *right_page_reclaimed = false; } 884 // can be 0 still with abandoned_next, or already a thread id for segments outside an arena that are reclaimed on a free. 885 mi_assert_internal(mi_atomic_load_relaxed(&segment->thread_id) == 0 || mi_atomic_load_relaxed(&segment->thread_id) == _mi_thread_id()); 886 mi_assert_internal(segment->subproc == heap->tld->segments.subproc); // only reclaim within the same subprocess 887 mi_atomic_store_release(&segment->thread_id, _mi_thread_id()); 888 segment->abandoned_visits = 0; 889 segment->was_reclaimed = true; 890 tld->reclaim_count++; 891 mi_segments_track_size((long)segment->segment_size, tld); 892 mi_assert_internal(segment->next == NULL && segment->prev == NULL); 893 mi_assert_expensive(mi_segment_is_valid(segment, tld)); 894 _mi_stat_decrease(&tld->stats->segments_abandoned, 1); 895 896 for (size_t i = 0; i < segment->capacity; i++) { 897 mi_page_t* page = &segment->pages[i]; 898 if (page->segment_in_use) { 899 mi_assert_internal(page->is_committed); 900 mi_assert_internal(mi_page_not_in_queue(page, tld)); 901 mi_assert_internal(mi_page_thread_free_flag(page)==MI_NEVER_DELAYED_FREE); 902 mi_assert_internal(mi_page_heap(page) == NULL); 903 segment->abandoned--; 904 mi_assert(page->next == NULL); 905 _mi_stat_decrease(&tld->stats->pages_abandoned, 1); 906 // get the target heap for this thread which has a matching heap tag (so we reclaim into a matching heap) 907 mi_heap_t* target_heap = _mi_heap_by_tag(heap, page->heap_tag); // allow custom heaps to separate objects 908 if (target_heap == NULL) { 909 target_heap = heap; 910 _mi_error_message(EFAULT, "page with tag %u cannot be reclaimed by a heap with the same tag (using heap tag %u instead)\n", page->heap_tag, heap->tag ); 911 } 912 // associate the heap with this page, and allow heap thread delayed free again. 913 mi_page_set_heap(page, target_heap); 914 _mi_page_use_delayed_free(page, MI_USE_DELAYED_FREE, true); // override never (after heap is set) 915 _mi_page_free_collect(page, false); // ensure used count is up to date 916 if (mi_page_all_free(page)) { 917 // if everything free already, clear the page directly 918 mi_segment_page_clear(segment, page, tld); // reset is ok now 919 } 920 else { 921 // otherwise reclaim it into the heap 922 _mi_page_reclaim(target_heap, page); 923 if (requested_block_size == mi_page_block_size(page) && mi_page_has_any_available(page) && heap == target_heap) { 924 if (right_page_reclaimed != NULL) { *right_page_reclaimed = true; } 925 } 926 } 927 } 928 /* expired 929 else if (page->is_committed) { // not in-use, and not reset yet 930 // note: do not reset as this includes pages that were not touched before 931 // mi_pages_purge_add(segment, page, tld); 932 } 933 */ 934 } 935 mi_assert_internal(segment->abandoned == 0); 936 if (segment->used == 0) { 937 mi_assert_internal(right_page_reclaimed == NULL || !(*right_page_reclaimed)); 938 mi_segment_free(segment, false, tld); 939 return NULL; 940 } 941 else { 942 if (segment->page_kind <= MI_PAGE_MEDIUM && mi_segment_has_free(segment)) { 943 mi_segment_insert_in_free_queue(segment, tld); 944 } 945 return segment; 946 } 947 } 948 949 950 // attempt to reclaim a particular segment (called from multi threaded free `alloc.c:mi_free_block_mt`) 951 bool _mi_segment_attempt_reclaim(mi_heap_t* heap, mi_segment_t* segment) { 952 if (mi_atomic_load_relaxed(&segment->thread_id) != 0) return false; // it is not abandoned 953 if (segment->subproc != heap->tld->segments.subproc) return false; // only reclaim within the same subprocess 954 if (!_mi_heap_memid_is_suitable(heap,segment->memid)) return false; // don't reclaim between exclusive and non-exclusive arena's 955 // don't reclaim more from a `free` call than half the current segments 956 // this is to prevent a pure free-ing thread to start owning too many segments 957 // (but not for out-of-arena segments as that is the main way to be reclaimed for those) 958 if (segment->memid.memkind == MI_MEM_ARENA && heap->tld->segments.reclaim_count * 2 > heap->tld->segments.count) { 959 return false; 960 } 961 if (_mi_arena_segment_clear_abandoned(segment)) { // atomically unabandon 962 mi_segment_t* res = mi_segment_reclaim(segment, heap, 0, NULL, &heap->tld->segments); 963 mi_assert_internal(res == segment); 964 return (res != NULL); 965 } 966 return false; 967 } 968 969 void _mi_abandoned_reclaim_all(mi_heap_t* heap, mi_segments_tld_t* tld) { 970 mi_segment_t* segment; 971 mi_arena_field_cursor_t current; 972 _mi_arena_field_cursor_init(heap, tld->subproc, true /* visit all, blocking */, ¤t); 973 while ((segment = _mi_arena_segment_clear_abandoned_next(¤t)) != NULL) { 974 mi_segment_reclaim(segment, heap, 0, NULL, tld); 975 } 976 _mi_arena_field_cursor_done(¤t); 977 } 978 979 static long mi_segment_get_reclaim_tries(mi_segments_tld_t* tld) { 980 // limit the tries to 10% (default) of the abandoned segments with at least 8 and at most 1024 tries. 981 const size_t perc = (size_t)mi_option_get_clamp(mi_option_max_segment_reclaim, 0, 100); 982 if (perc <= 0) return 0; 983 const size_t total_count = mi_atomic_load_relaxed(&tld->subproc->abandoned_count); 984 if (total_count == 0) return 0; 985 const size_t relative_count = (total_count > 10000 ? (total_count / 100) * perc : (total_count * perc) / 100); // avoid overflow 986 long max_tries = (long)(relative_count <= 1 ? 1 : (relative_count > 1024 ? 1024 : relative_count)); 987 if (max_tries < 8 && total_count > 8) { max_tries = 8; } 988 return max_tries; 989 } 990 991 static mi_segment_t* mi_segment_try_reclaim(mi_heap_t* heap, size_t block_size, mi_page_kind_t page_kind, bool* reclaimed, mi_segments_tld_t* tld) 992 { 993 *reclaimed = false; 994 long max_tries = mi_segment_get_reclaim_tries(tld); 995 if (max_tries <= 0) return NULL; 996 997 mi_segment_t* result = NULL; 998 mi_segment_t* segment = NULL; 999 mi_arena_field_cursor_t current; 1000 _mi_arena_field_cursor_init(heap, tld->subproc, false /* non-blocking */, ¤t); 1001 while ((max_tries-- > 0) && ((segment = _mi_arena_segment_clear_abandoned_next(¤t)) != NULL)) 1002 { 1003 mi_assert(segment->subproc == heap->tld->segments.subproc); // cursor only visits segments in our sub-process 1004 segment->abandoned_visits++; 1005 // todo: should we respect numa affinity for abondoned reclaim? perhaps only for the first visit? 1006 // todo: an arena exclusive heap will potentially visit many abandoned unsuitable segments and use many tries 1007 // Perhaps we can skip non-suitable ones in a better way? 1008 bool is_suitable = _mi_heap_memid_is_suitable(heap, segment->memid); 1009 bool all_pages_free; 1010 bool has_page = mi_segment_check_free(segment,block_size,&all_pages_free); // try to free up pages (due to concurrent frees) 1011 if (all_pages_free) { 1012 // free the segment (by forced reclaim) to make it available to other threads. 1013 // note1: we prefer to free a segment as that might lead to reclaiming another 1014 // segment that is still partially used. 1015 // note2: we could in principle optimize this by skipping reclaim and directly 1016 // freeing but that would violate some invariants temporarily) 1017 mi_segment_reclaim(segment, heap, 0, NULL, tld); 1018 } 1019 else if (has_page && segment->page_kind == page_kind && is_suitable) { 1020 // found a free page of the right kind, or page of the right block_size with free space 1021 // we return the result of reclaim (which is usually `segment`) as it might free 1022 // the segment due to concurrent frees (in which case `NULL` is returned). 1023 result = mi_segment_reclaim(segment, heap, block_size, reclaimed, tld); 1024 break; 1025 } 1026 else if (segment->abandoned_visits >= 3 && is_suitable) { 1027 // always reclaim on 3rd visit to limit the list length. 1028 mi_segment_reclaim(segment, heap, 0, NULL, tld); 1029 } 1030 else { 1031 // otherwise, mark it back as abandoned 1032 // todo: reset delayed pages in the segment? 1033 _mi_arena_segment_mark_abandoned(segment); 1034 } 1035 } 1036 _mi_arena_field_cursor_done(¤t); 1037 return result; 1038 } 1039 1040 1041 /* ----------------------------------------------------------- 1042 Reclaim or allocate 1043 ----------------------------------------------------------- */ 1044 1045 static mi_segment_t* mi_segment_reclaim_or_alloc(mi_heap_t* heap, size_t block_size, mi_page_kind_t page_kind, size_t page_shift, mi_segments_tld_t* tld, mi_os_tld_t* os_tld) 1046 { 1047 mi_assert_internal(page_kind <= MI_PAGE_LARGE); 1048 mi_assert_internal(block_size <= MI_LARGE_OBJ_SIZE_MAX); 1049 1050 // 1. try to reclaim an abandoned segment 1051 bool reclaimed; 1052 mi_segment_t* segment = mi_segment_try_reclaim(heap, block_size, page_kind, &reclaimed, tld); 1053 mi_assert_internal(segment == NULL || _mi_arena_memid_is_suitable(segment->memid, heap->arena_id)); 1054 if (reclaimed) { 1055 // reclaimed the right page right into the heap 1056 mi_assert_internal(segment != NULL && segment->page_kind == page_kind && page_kind <= MI_PAGE_LARGE); 1057 return NULL; // pretend out-of-memory as the page will be in the page queue of the heap with available blocks 1058 } 1059 else if (segment != NULL) { 1060 // reclaimed a segment with empty pages (of `page_kind`) in it 1061 return segment; 1062 } 1063 // 2. otherwise allocate a fresh segment 1064 return mi_segment_alloc(0, page_kind, page_shift, 0, heap->arena_id, tld, os_tld); 1065 } 1066 1067 1068 /* ----------------------------------------------------------- 1069 Small page allocation 1070 ----------------------------------------------------------- */ 1071 1072 static mi_page_t* mi_segment_find_free(mi_segment_t* segment, mi_segments_tld_t* tld) { 1073 mi_assert_internal(mi_segment_has_free(segment)); 1074 mi_assert_expensive(mi_segment_is_valid(segment, tld)); 1075 for (size_t i = 0; i < segment->capacity; i++) { // TODO: use a bitmap instead of search? 1076 mi_page_t* page = &segment->pages[i]; 1077 if (!page->segment_in_use) { 1078 bool ok = mi_segment_page_claim(segment, page, tld); 1079 if (ok) return page; 1080 } 1081 } 1082 mi_assert(false); 1083 return NULL; 1084 } 1085 1086 // Allocate a page inside a segment. Requires that the page has free pages 1087 static mi_page_t* mi_segment_page_alloc_in(mi_segment_t* segment, mi_segments_tld_t* tld) { 1088 mi_assert_internal(mi_segment_has_free(segment)); 1089 return mi_segment_find_free(segment, tld); 1090 } 1091 1092 static mi_page_t* mi_segment_page_try_alloc_in_queue(mi_heap_t* heap, mi_page_kind_t kind, mi_segments_tld_t* tld) { 1093 // find an available segment the segment free queue 1094 mi_segment_queue_t* const free_queue = mi_segment_free_queue_of_kind(kind, tld); 1095 for (mi_segment_t* segment = free_queue->first; segment != NULL; segment = segment->next) { 1096 if (_mi_arena_memid_is_suitable(segment->memid, heap->arena_id) && mi_segment_has_free(segment)) { 1097 return mi_segment_page_alloc_in(segment, tld); 1098 } 1099 } 1100 return NULL; 1101 } 1102 1103 static mi_page_t* mi_segment_page_alloc(mi_heap_t* heap, size_t block_size, mi_page_kind_t kind, size_t page_shift, mi_segments_tld_t* tld, mi_os_tld_t* os_tld) { 1104 mi_page_t* page = mi_segment_page_try_alloc_in_queue(heap, kind, tld); 1105 if (page == NULL) { 1106 // possibly allocate or reclaim a fresh segment 1107 mi_segment_t* const segment = mi_segment_reclaim_or_alloc(heap, block_size, kind, page_shift, tld, os_tld); 1108 if (segment == NULL) return NULL; // return NULL if out-of-memory (or reclaimed) 1109 mi_assert_internal(segment->page_kind==kind); 1110 mi_assert_internal(segment->used < segment->capacity); 1111 mi_assert_internal(_mi_arena_memid_is_suitable(segment->memid, heap->arena_id)); 1112 page = mi_segment_page_try_alloc_in_queue(heap, kind, tld); // this should now succeed 1113 } 1114 mi_assert_internal(page != NULL); 1115 #if MI_DEBUG>=2 && !MI_TRACK_ENABLED // && !MI_TSAN 1116 // verify it is committed 1117 mi_segment_raw_page_start(_mi_page_segment(page), page, NULL)[0] = 0; 1118 #endif 1119 return page; 1120 } 1121 1122 static mi_page_t* mi_segment_small_page_alloc(mi_heap_t* heap, size_t block_size, mi_segments_tld_t* tld, mi_os_tld_t* os_tld) { 1123 return mi_segment_page_alloc(heap, block_size, MI_PAGE_SMALL,MI_SMALL_PAGE_SHIFT,tld,os_tld); 1124 } 1125 1126 static mi_page_t* mi_segment_medium_page_alloc(mi_heap_t* heap, size_t block_size, mi_segments_tld_t* tld, mi_os_tld_t* os_tld) { 1127 return mi_segment_page_alloc(heap, block_size, MI_PAGE_MEDIUM, MI_MEDIUM_PAGE_SHIFT, tld, os_tld); 1128 } 1129 1130 /* ----------------------------------------------------------- 1131 large page allocation 1132 ----------------------------------------------------------- */ 1133 1134 static mi_page_t* mi_segment_large_page_alloc(mi_heap_t* heap, size_t block_size, mi_segments_tld_t* tld, mi_os_tld_t* os_tld) { 1135 mi_segment_t* segment = mi_segment_reclaim_or_alloc(heap,block_size,MI_PAGE_LARGE,MI_LARGE_PAGE_SHIFT,tld,os_tld); 1136 if (segment == NULL) return NULL; 1137 mi_page_t* page = mi_segment_find_free(segment, tld); 1138 mi_assert_internal(page != NULL); 1139 #if MI_DEBUG>=2 && !MI_TRACK_ENABLED // && !MI_TSAN 1140 mi_segment_raw_page_start(segment, page, NULL)[0] = 0; 1141 #endif 1142 return page; 1143 } 1144 1145 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) 1146 { 1147 mi_segment_t* segment = mi_segment_alloc(size, MI_PAGE_HUGE, MI_SEGMENT_SHIFT + 1, page_alignment, req_arena_id, tld, os_tld); 1148 if (segment == NULL) return NULL; 1149 mi_assert_internal(mi_segment_page_size(segment) - segment->segment_info_size - (2*(MI_SECURE == 0 ? 0 : _mi_os_page_size())) >= size); 1150 #if MI_HUGE_PAGE_ABANDON 1151 segment->thread_id = 0; // huge pages are immediately abandoned 1152 mi_segments_track_size(-(long)segment->segment_size, tld); 1153 #endif 1154 mi_page_t* page = mi_segment_find_free(segment, tld); 1155 mi_assert_internal(page != NULL); 1156 mi_assert_internal(page->is_huge); 1157 1158 // for huge pages we initialize the block_size as we may 1159 // overallocate to accommodate large alignments. 1160 size_t psize; 1161 uint8_t* start = mi_segment_raw_page_start(segment, page, &psize); 1162 page->block_size = psize; 1163 1164 // reset the part of the page that will not be used; this can be quite large (close to MI_SEGMENT_SIZE) 1165 if (page_alignment > 0 && segment->allow_decommit && page->is_committed) { 1166 uint8_t* aligned_p = (uint8_t*)_mi_align_up((uintptr_t)start, page_alignment); 1167 mi_assert_internal(_mi_is_aligned(aligned_p, page_alignment)); 1168 mi_assert_internal(psize - (aligned_p - start) >= size); 1169 uint8_t* decommit_start = start + sizeof(mi_block_t); // for the free list 1170 ptrdiff_t decommit_size = aligned_p - decommit_start; 1171 _mi_os_reset(decommit_start, decommit_size, os_tld->stats); // do not decommit as it may be in a region 1172 } 1173 1174 return page; 1175 } 1176 1177 #if MI_HUGE_PAGE_ABANDON 1178 // free huge block from another thread 1179 void _mi_segment_huge_page_free(mi_segment_t* segment, mi_page_t* page, mi_block_t* block) { 1180 // huge page segments are always abandoned and can be freed immediately by any thread 1181 mi_assert_internal(segment->page_kind==MI_PAGE_HUGE); 1182 mi_assert_internal(segment == _mi_page_segment(page)); 1183 mi_assert_internal(mi_atomic_load_relaxed(&segment->thread_id)==0); 1184 1185 // claim it and free 1186 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. 1187 // paranoia: if this it the last reference, the cas should always succeed 1188 size_t expected_tid = 0; 1189 if (mi_atomic_cas_strong_acq_rel(&segment->thread_id, &expected_tid, heap->thread_id)) { 1190 mi_block_set_next(page, block, page->free); 1191 page->free = block; 1192 page->used--; 1193 page->is_zero_init = false; 1194 mi_assert(page->used == 0); 1195 mi_tld_t* tld = heap->tld; 1196 mi_segments_track_size((long)segment->segment_size, &tld->segments); 1197 _mi_segment_page_free(page, true, &tld->segments); 1198 } 1199 #if (MI_DEBUG!=0) 1200 else { 1201 mi_assert_internal(false); 1202 } 1203 #endif 1204 } 1205 1206 #else 1207 // reset memory of a huge block from another thread 1208 void _mi_segment_huge_page_reset(mi_segment_t* segment, mi_page_t* page, mi_block_t* block) { 1209 mi_assert_internal(segment->page_kind == MI_PAGE_HUGE); 1210 mi_assert_internal(segment == _mi_page_segment(page)); 1211 mi_assert_internal(page->used == 1); // this is called just before the free 1212 mi_assert_internal(page->free == NULL); 1213 if (segment->allow_decommit && page->is_committed) { 1214 size_t usize = mi_usable_size(block); 1215 if (usize > sizeof(mi_block_t)) { 1216 usize = usize - sizeof(mi_block_t); 1217 uint8_t* p = (uint8_t*)block + sizeof(mi_block_t); 1218 _mi_os_reset(p, usize, &_mi_stats_main); 1219 } 1220 } 1221 } 1222 #endif 1223 1224 /* ----------------------------------------------------------- 1225 Page allocation 1226 ----------------------------------------------------------- */ 1227 1228 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) { 1229 mi_page_t* page; 1230 if mi_unlikely(page_alignment > MI_BLOCK_ALIGNMENT_MAX) { 1231 mi_assert_internal(_mi_is_power_of_two(page_alignment)); 1232 mi_assert_internal(page_alignment >= MI_SEGMENT_SIZE); 1233 //mi_assert_internal((MI_SEGMENT_SIZE % page_alignment) == 0); 1234 if (page_alignment < MI_SEGMENT_SIZE) { page_alignment = MI_SEGMENT_SIZE; } 1235 page = mi_segment_huge_page_alloc(block_size, page_alignment, heap->arena_id, tld, os_tld); 1236 } 1237 else if (block_size <= MI_SMALL_OBJ_SIZE_MAX) { 1238 page = mi_segment_small_page_alloc(heap, block_size, tld, os_tld); 1239 } 1240 else if (block_size <= MI_MEDIUM_OBJ_SIZE_MAX) { 1241 page = mi_segment_medium_page_alloc(heap, block_size, tld, os_tld); 1242 } 1243 else if (block_size <= MI_LARGE_OBJ_SIZE_MAX /* || mi_is_good_fit(block_size, MI_LARGE_PAGE_SIZE - sizeof(mi_segment_t)) */ ) { 1244 page = mi_segment_large_page_alloc(heap, block_size, tld, os_tld); 1245 } 1246 else { 1247 page = mi_segment_huge_page_alloc(block_size, page_alignment, heap->arena_id, tld, os_tld); 1248 } 1249 mi_assert_expensive(page == NULL || mi_segment_is_valid(_mi_page_segment(page),tld)); 1250 mi_assert_internal(page == NULL || (mi_segment_page_size(_mi_page_segment(page)) - (MI_SECURE == 0 ? 0 : _mi_os_page_size())) >= block_size); 1251 // mi_segment_try_purge(tld); 1252 mi_assert_internal(page == NULL || mi_page_not_in_queue(page, tld)); 1253 mi_assert_internal(page == NULL || _mi_page_segment(page)->subproc == tld->subproc); 1254 return page; 1255 } 1256 1257 1258 /* ----------------------------------------------------------- 1259 Visit blocks in a segment (only used for abandoned segments) 1260 ----------------------------------------------------------- */ 1261 1262 static bool mi_segment_visit_page(mi_page_t* page, bool visit_blocks, mi_block_visit_fun* visitor, void* arg) { 1263 mi_heap_area_t area; 1264 _mi_heap_area_init(&area, page); 1265 if (!visitor(NULL, &area, NULL, area.block_size, arg)) return false; 1266 if (visit_blocks) { 1267 return _mi_heap_area_visit_blocks(&area, page, visitor, arg); 1268 } 1269 else { 1270 return true; 1271 } 1272 } 1273 1274 bool _mi_segment_visit_blocks(mi_segment_t* segment, int heap_tag, bool visit_blocks, mi_block_visit_fun* visitor, void* arg) { 1275 for (size_t i = 0; i < segment->capacity; i++) { 1276 mi_page_t* const page = &segment->pages[i]; 1277 if (page->segment_in_use) { 1278 if (heap_tag < 0 || (int)page->heap_tag == heap_tag) { 1279 if (!mi_segment_visit_page(page, visit_blocks, visitor, arg)) return false; 1280 } 1281 } 1282 } 1283 return true; 1284 }