| 1 |
/*---------------------------------------------------------------------------- |
| 2 |
Copyright (c) 2018-2020, Microsoft Research, Daan Leijen |
| 3 |
This is free software; you can redistribute it and/or modify it under the |
| 4 |
terms of the MIT license. A copy of the license can be found in the file |
| 5 |
"LICENSE" at the root of this distribution. |
| 6 |
-----------------------------------------------------------------------------*/ |
| 7 |
|
| 8 |
/* ----------------------------------------------------------- |
| 9 |
The core of the allocator. Every segment contains |
| 10 |
pages of a certain block size. The main function |
| 11 |
exported is `mi_malloc_generic`. |
| 12 |
----------------------------------------------------------- */ |
| 13 |
|
| 14 |
#include "mimalloc.h" |
| 15 |
#include "mimalloc/internal.h" |
| 16 |
#include "mimalloc/atomic.h" |
| 17 |
|
| 18 |
/* ----------------------------------------------------------- |
| 19 |
Definition of page queues for each block size |
| 20 |
----------------------------------------------------------- */ |
| 21 |
|
| 22 |
#define MI_IN_PAGE_C |
| 23 |
#include "page-queue.c" |
| 24 |
#undef MI_IN_PAGE_C |
| 25 |
|
| 26 |
|
| 27 |
/* ----------------------------------------------------------- |
| 28 |
Page helpers |
| 29 |
----------------------------------------------------------- */ |
| 30 |
|
| 31 |
// Index a block in a page |
| 32 |
static inline mi_block_t* mi_page_block_at(const mi_page_t* page, void* page_start, size_t block_size, size_t i) { |
| 33 |
MI_UNUSED(page); |
| 34 |
mi_assert_internal(page != NULL); |
| 35 |
mi_assert_internal(i <= page->reserved); |
| 36 |
return (mi_block_t*)((uint8_t*)page_start + (i * block_size)); |
| 37 |
} |
| 38 |
|
| 39 |
static void mi_page_init(mi_heap_t* heap, mi_page_t* page, size_t size, mi_tld_t* tld); |
| 40 |
static void mi_page_extend_free(mi_heap_t* heap, mi_page_t* page, mi_tld_t* tld); |
| 41 |
|
| 42 |
#if (MI_DEBUG>=3) |
| 43 |
static size_t mi_page_list_count(mi_page_t* page, mi_block_t* head) { |
| 44 |
size_t count = 0; |
| 45 |
while (head != NULL) { |
| 46 |
mi_assert_internal(page == _mi_ptr_page(head)); |
| 47 |
count++; |
| 48 |
head = mi_block_next(page, head); |
| 49 |
} |
| 50 |
return count; |
| 51 |
} |
| 52 |
|
| 53 |
/* |
| 54 |
// Start of the page available memory |
| 55 |
static inline uint8_t* mi_page_area(const mi_page_t* page) { |
| 56 |
return _mi_page_start(_mi_page_segment(page), page, NULL); |
| 57 |
} |
| 58 |
*/ |
| 59 |
|
| 60 |
static bool mi_page_list_is_valid(mi_page_t* page, mi_block_t* p) { |
| 61 |
size_t psize; |
| 62 |
uint8_t* page_area = _mi_page_start(_mi_page_segment(page), page, &psize); |
| 63 |
mi_block_t* start = (mi_block_t*)page_area; |
| 64 |
mi_block_t* end = (mi_block_t*)(page_area + psize); |
| 65 |
while(p != NULL) { |
| 66 |
if (p < start || p >= end) return false; |
| 67 |
p = mi_block_next(page, p); |
| 68 |
} |
| 69 |
#if MI_DEBUG>3 // generally too expensive to check this |
| 70 |
if (page->free_is_zero) { |
| 71 |
const size_t ubsize = mi_page_usable_block_size(page); |
| 72 |
for (mi_block_t* block = page->free; block != NULL; block = mi_block_next(page, block)) { |
| 73 |
mi_assert_expensive(mi_mem_is_zero(block + 1, ubsize - sizeof(mi_block_t))); |
| 74 |
} |
| 75 |
} |
| 76 |
#endif |
| 77 |
return true; |
| 78 |
} |
| 79 |
|
| 80 |
static bool mi_page_is_valid_init(mi_page_t* page) { |
| 81 |
mi_assert_internal(page->xblock_size > 0); |
| 82 |
mi_assert_internal(page->used <= page->capacity); |
| 83 |
mi_assert_internal(page->capacity <= page->reserved); |
| 84 |
|
| 85 |
mi_segment_t* segment = _mi_page_segment(page); |
| 86 |
uint8_t* start = _mi_page_start(segment,page,NULL); |
| 87 |
mi_assert_internal(start == _mi_segment_page_start(segment,page,NULL)); |
| 88 |
//const size_t bsize = mi_page_block_size(page); |
| 89 |
//mi_assert_internal(start + page->capacity*page->block_size == page->top); |
| 90 |
|
| 91 |
mi_assert_internal(mi_page_list_is_valid(page,page->free)); |
| 92 |
mi_assert_internal(mi_page_list_is_valid(page,page->local_free)); |
| 93 |
|
| 94 |
#if MI_DEBUG>3 // generally too expensive to check this |
| 95 |
if (page->free_is_zero) { |
| 96 |
const size_t ubsize = mi_page_usable_block_size(page); |
| 97 |
for(mi_block_t* block = page->free; block != NULL; block = mi_block_next(page,block)) { |
| 98 |
mi_assert_expensive(mi_mem_is_zero(block + 1, ubsize - sizeof(mi_block_t))); |
| 99 |
} |
| 100 |
} |
| 101 |
#endif |
| 102 |
|
| 103 |
#if !MI_TRACK_ENABLED && !MI_TSAN |
| 104 |
mi_block_t* tfree = mi_page_thread_free(page); |
| 105 |
mi_assert_internal(mi_page_list_is_valid(page, tfree)); |
| 106 |
//size_t tfree_count = mi_page_list_count(page, tfree); |
| 107 |
//mi_assert_internal(tfree_count <= page->thread_freed + 1); |
| 108 |
#endif |
| 109 |
|
| 110 |
size_t free_count = mi_page_list_count(page, page->free) + mi_page_list_count(page, page->local_free); |
| 111 |
mi_assert_internal(page->used + free_count == page->capacity); |
| 112 |
|
| 113 |
return true; |
| 114 |
} |
| 115 |
|
| 116 |
extern bool _mi_process_is_initialized; // has mi_process_init been called? |
| 117 |
|
| 118 |
bool _mi_page_is_valid(mi_page_t* page) { |
| 119 |
mi_assert_internal(mi_page_is_valid_init(page)); |
| 120 |
#if MI_SECURE |
| 121 |
mi_assert_internal(page->keys[0] != 0); |
| 122 |
#endif |
| 123 |
if (mi_page_heap(page)!=NULL) { |
| 124 |
mi_segment_t* segment = _mi_page_segment(page); |
| 125 |
|
| 126 |
mi_assert_internal(!_mi_process_is_initialized || segment->thread_id==0 || segment->thread_id == mi_page_heap(page)->thread_id); |
| 127 |
#if MI_HUGE_PAGE_ABANDON |
| 128 |
if (segment->kind != MI_SEGMENT_HUGE) |
| 129 |
#endif |
| 130 |
{ |
| 131 |
mi_page_queue_t* pq = mi_page_queue_of(page); |
| 132 |
mi_assert_internal(mi_page_queue_contains(pq, page)); |
| 133 |
mi_assert_internal(pq->block_size==mi_page_block_size(page) || mi_page_block_size(page) > MI_MEDIUM_OBJ_SIZE_MAX || mi_page_is_in_full(page)); |
| 134 |
mi_assert_internal(mi_heap_contains_queue(mi_page_heap(page),pq)); |
| 135 |
} |
| 136 |
} |
| 137 |
return true; |
| 138 |
} |
| 139 |
#endif |
| 140 |
|
| 141 |
void _mi_page_use_delayed_free(mi_page_t* page, mi_delayed_t delay, bool override_never) { |
| 142 |
while (!_mi_page_try_use_delayed_free(page, delay, override_never)) { |
| 143 |
mi_atomic_yield(); |
| 144 |
} |
| 145 |
} |
| 146 |
|
| 147 |
bool _mi_page_try_use_delayed_free(mi_page_t* page, mi_delayed_t delay, bool override_never) { |
| 148 |
mi_thread_free_t tfreex; |
| 149 |
mi_delayed_t old_delay; |
| 150 |
mi_thread_free_t tfree; |
| 151 |
size_t yield_count = 0; |
| 152 |
do { |
| 153 |
tfree = mi_atomic_load_acquire(&page->xthread_free); // note: must acquire as we can break/repeat this loop and not do a CAS; |
| 154 |
tfreex = mi_tf_set_delayed(tfree, delay); |
| 155 |
old_delay = mi_tf_delayed(tfree); |
| 156 |
if mi_unlikely(old_delay == MI_DELAYED_FREEING) { |
| 157 |
if (yield_count >= 4) return false; // give up after 4 tries |
| 158 |
yield_count++; |
| 159 |
mi_atomic_yield(); // delay until outstanding MI_DELAYED_FREEING are done. |
| 160 |
// tfree = mi_tf_set_delayed(tfree, MI_NO_DELAYED_FREE); // will cause CAS to busy fail |
| 161 |
} |
| 162 |
else if (delay == old_delay) { |
| 163 |
break; // avoid atomic operation if already equal |
| 164 |
} |
| 165 |
else if (!override_never && old_delay == MI_NEVER_DELAYED_FREE) { |
| 166 |
break; // leave never-delayed flag set |
| 167 |
} |
| 168 |
} while ((old_delay == MI_DELAYED_FREEING) || |
| 169 |
!mi_atomic_cas_weak_release(&page->xthread_free, &tfree, tfreex)); |
| 170 |
|
| 171 |
return true; // success |
| 172 |
} |
| 173 |
|
| 174 |
/* ----------------------------------------------------------- |
| 175 |
Page collect the `local_free` and `thread_free` lists |
| 176 |
----------------------------------------------------------- */ |
| 177 |
|
| 178 |
// Collect the local `thread_free` list using an atomic exchange. |
| 179 |
// Note: The exchange must be done atomically as this is used right after |
| 180 |
// moving to the full list in `mi_page_collect_ex` and we need to |
| 181 |
// ensure that there was no race where the page became unfull just before the move. |
| 182 |
static void _mi_page_thread_free_collect(mi_page_t* page) |
| 183 |
{ |
| 184 |
mi_block_t* head; |
| 185 |
mi_thread_free_t tfreex; |
| 186 |
mi_thread_free_t tfree = mi_atomic_load_relaxed(&page->xthread_free); |
| 187 |
do { |
| 188 |
head = mi_tf_block(tfree); |
| 189 |
tfreex = mi_tf_set_block(tfree,NULL); |
| 190 |
} while (!mi_atomic_cas_weak_acq_rel(&page->xthread_free, &tfree, tfreex)); |
| 191 |
|
| 192 |
// return if the list is empty |
| 193 |
if (head == NULL) return; |
| 194 |
|
| 195 |
// find the tail -- also to get a proper count (without data races) |
| 196 |
uint32_t max_count = page->capacity; // cannot collect more than capacity |
| 197 |
uint32_t count = 1; |
| 198 |
mi_block_t* tail = head; |
| 199 |
mi_block_t* next; |
| 200 |
while ((next = mi_block_next(page,tail)) != NULL && count <= max_count) { |
| 201 |
count++; |
| 202 |
tail = next; |
| 203 |
} |
| 204 |
// if `count > max_count` there was a memory corruption (possibly infinite list due to double multi-threaded free) |
| 205 |
if (count > max_count) { |
| 206 |
_mi_error_message(EFAULT, "corrupted thread-free list\n"); |
| 207 |
return; // the thread-free items cannot be freed |
| 208 |
} |
| 209 |
|
| 210 |
// and append the current local free list |
| 211 |
mi_block_set_next(page,tail, page->local_free); |
| 212 |
page->local_free = head; |
| 213 |
|
| 214 |
// update counts now |
| 215 |
page->used -= count; |
| 216 |
|
| 217 |
if (page->used == 0) { |
| 218 |
// The page may have had a QSBR goal set from a previous point when it |
| 219 |
// was all-free. That goal is no longer valid because the page was |
| 220 |
// allocated from and then freed again by other threads. |
| 221 |
_PyMem_mi_page_clear_qsbr(page); |
| 222 |
} |
| 223 |
} |
| 224 |
|
| 225 |
void _mi_page_free_collect(mi_page_t* page, bool force) { |
| 226 |
mi_assert_internal(page!=NULL); |
| 227 |
|
| 228 |
// collect the thread free list |
| 229 |
if (force || mi_page_thread_free(page) != NULL) { // quick test to avoid an atomic operation |
| 230 |
_mi_page_thread_free_collect(page); |
| 231 |
} |
| 232 |
|
| 233 |
// and the local free list |
| 234 |
if (page->local_free != NULL) { |
| 235 |
if mi_likely(page->free == NULL) { |
| 236 |
// usual case |
| 237 |
page->free = page->local_free; |
| 238 |
page->local_free = NULL; |
| 239 |
page->free_is_zero = false; |
| 240 |
} |
| 241 |
else if (force) { |
| 242 |
// append -- only on shutdown (force) as this is a linear operation |
| 243 |
mi_block_t* tail = page->local_free; |
| 244 |
mi_block_t* next; |
| 245 |
while ((next = mi_block_next(page, tail)) != NULL) { |
| 246 |
tail = next; |
| 247 |
} |
| 248 |
mi_block_set_next(page, tail, page->free); |
| 249 |
page->free = page->local_free; |
| 250 |
page->local_free = NULL; |
| 251 |
page->free_is_zero = false; |
| 252 |
} |
| 253 |
} |
| 254 |
|
| 255 |
mi_assert_internal(!force || page->local_free == NULL); |
| 256 |
} |
| 257 |
|
| 258 |
|
| 259 |
|
| 260 |
/* ----------------------------------------------------------- |
| 261 |
Page fresh and retire |
| 262 |
----------------------------------------------------------- */ |
| 263 |
|
| 264 |
// called from segments when reclaiming abandoned pages |
| 265 |
void _mi_page_reclaim(mi_heap_t* heap, mi_page_t* page) { |
| 266 |
mi_assert_expensive(mi_page_is_valid_init(page)); |
| 267 |
|
| 268 |
mi_assert_internal(mi_page_heap(page) == heap); |
| 269 |
mi_assert_internal(mi_page_thread_free_flag(page) != MI_NEVER_DELAYED_FREE); |
| 270 |
#if MI_HUGE_PAGE_ABANDON |
| 271 |
mi_assert_internal(_mi_page_segment(page)->kind != MI_SEGMENT_HUGE); |
| 272 |
#endif |
| 273 |
|
| 274 |
// TODO: push on full queue immediately if it is full? |
| 275 |
mi_page_queue_t* pq = mi_page_queue(heap, mi_page_block_size(page)); |
| 276 |
mi_page_queue_push(heap, pq, page); |
| 277 |
_PyMem_mi_page_reclaimed(page); |
| 278 |
mi_assert_expensive(_mi_page_is_valid(page)); |
| 279 |
} |
| 280 |
|
| 281 |
// allocate a fresh page from a segment |
| 282 |
static mi_page_t* mi_page_fresh_alloc(mi_heap_t* heap, mi_page_queue_t* pq, size_t block_size, size_t page_alignment) { |
| 283 |
#if !MI_HUGE_PAGE_ABANDON |
| 284 |
mi_assert_internal(pq != NULL); |
| 285 |
mi_assert_internal(mi_heap_contains_queue(heap, pq)); |
| 286 |
mi_assert_internal(page_alignment > 0 || block_size > MI_MEDIUM_OBJ_SIZE_MAX || block_size == pq->block_size); |
| 287 |
#endif |
| 288 |
mi_page_t* page = _mi_segment_page_alloc(heap, block_size, page_alignment, &heap->tld->segments, &heap->tld->os); |
| 289 |
if (page == NULL) { |
| 290 |
// this may be out-of-memory, or an abandoned page was reclaimed (and in our queue) |
| 291 |
return NULL; |
| 292 |
} |
| 293 |
mi_assert_internal(page_alignment >0 || block_size > MI_MEDIUM_OBJ_SIZE_MAX || _mi_page_segment(page)->kind != MI_SEGMENT_HUGE); |
| 294 |
mi_assert_internal(pq!=NULL || page->xblock_size != 0); |
| 295 |
mi_assert_internal(pq!=NULL || mi_page_block_size(page) >= block_size); |
| 296 |
// a fresh page was found, initialize it |
| 297 |
const size_t full_block_size = ((pq == NULL || mi_page_queue_is_huge(pq)) ? mi_page_block_size(page) : block_size); // see also: mi_segment_huge_page_alloc |
| 298 |
mi_assert_internal(full_block_size >= block_size); |
| 299 |
mi_page_init(heap, page, full_block_size, heap->tld); |
| 300 |
mi_heap_stat_increase(heap, pages, 1); |
| 301 |
if (pq != NULL) { mi_page_queue_push(heap, pq, page); } |
| 302 |
mi_assert_expensive(_mi_page_is_valid(page)); |
| 303 |
return page; |
| 304 |
} |
| 305 |
|
| 306 |
// Get a fresh page to use |
| 307 |
static mi_page_t* mi_page_fresh(mi_heap_t* heap, mi_page_queue_t* pq) { |
| 308 |
mi_assert_internal(mi_heap_contains_queue(heap, pq)); |
| 309 |
mi_page_t* page = mi_page_fresh_alloc(heap, pq, pq->block_size, 0); |
| 310 |
if (page==NULL) return NULL; |
| 311 |
mi_assert_internal(pq->block_size==mi_page_block_size(page)); |
| 312 |
mi_assert_internal(pq==mi_page_queue(heap, mi_page_block_size(page))); |
| 313 |
return page; |
| 314 |
} |
| 315 |
|
| 316 |
/* ----------------------------------------------------------- |
| 317 |
Do any delayed frees |
| 318 |
(put there by other threads if they deallocated in a full page) |
| 319 |
----------------------------------------------------------- */ |
| 320 |
void _mi_heap_delayed_free_all(mi_heap_t* heap) { |
| 321 |
while (!_mi_heap_delayed_free_partial(heap)) { |
| 322 |
mi_atomic_yield(); |
| 323 |
} |
| 324 |
} |
| 325 |
|
| 326 |
// returns true if all delayed frees were processed |
| 327 |
bool _mi_heap_delayed_free_partial(mi_heap_t* heap) { |
| 328 |
// take over the list (note: no atomic exchange since it is often NULL) |
| 329 |
mi_block_t* block = mi_atomic_load_ptr_relaxed(mi_block_t, &heap->thread_delayed_free); |
| 330 |
while (block != NULL && !mi_atomic_cas_ptr_weak_acq_rel(mi_block_t, &heap->thread_delayed_free, &block, NULL)) { /* nothing */ }; |
| 331 |
bool all_freed = true; |
| 332 |
|
| 333 |
// and free them all |
| 334 |
while(block != NULL) { |
| 335 |
mi_block_t* next = mi_block_nextx(heap,block, heap->keys); |
| 336 |
// use internal free instead of regular one to keep stats etc correct |
| 337 |
if (!_mi_free_delayed_block(block)) { |
| 338 |
// we might already start delayed freeing while another thread has not yet |
| 339 |
// reset the delayed_freeing flag; in that case delay it further by reinserting the current block |
| 340 |
// into the delayed free list |
| 341 |
all_freed = false; |
| 342 |
mi_block_t* dfree = mi_atomic_load_ptr_relaxed(mi_block_t, &heap->thread_delayed_free); |
| 343 |
do { |
| 344 |
mi_block_set_nextx(heap, block, dfree, heap->keys); |
| 345 |
} while (!mi_atomic_cas_ptr_weak_release(mi_block_t,&heap->thread_delayed_free, &dfree, block)); |
| 346 |
} |
| 347 |
block = next; |
| 348 |
} |
| 349 |
return all_freed; |
| 350 |
} |
| 351 |
|
| 352 |
/* ----------------------------------------------------------- |
| 353 |
Unfull, abandon, free and retire |
| 354 |
----------------------------------------------------------- */ |
| 355 |
|
| 356 |
// Move a page from the full list back to a regular list |
| 357 |
void _mi_page_unfull(mi_page_t* page) { |
| 358 |
mi_assert_internal(page != NULL); |
| 359 |
mi_assert_expensive(_mi_page_is_valid(page)); |
| 360 |
mi_assert_internal(mi_page_is_in_full(page)); |
| 361 |
if (!mi_page_is_in_full(page)) return; |
| 362 |
|
| 363 |
mi_heap_t* heap = mi_page_heap(page); |
| 364 |
mi_page_queue_t* pqfull = &heap->pages[MI_BIN_FULL]; |
| 365 |
mi_page_set_in_full(page, false); // to get the right queue |
| 366 |
mi_page_queue_t* pq = mi_heap_page_queue_of(heap, page); |
| 367 |
mi_page_set_in_full(page, true); |
| 368 |
mi_page_queue_enqueue_from(pq, pqfull, page); |
| 369 |
} |
| 370 |
|
| 371 |
static void mi_page_to_full(mi_page_t* page, mi_page_queue_t* pq) { |
| 372 |
mi_assert_internal(pq == mi_page_queue_of(page)); |
| 373 |
mi_assert_internal(!mi_page_immediate_available(page)); |
| 374 |
mi_assert_internal(!mi_page_is_in_full(page)); |
| 375 |
|
| 376 |
if (mi_page_is_in_full(page)) return; |
| 377 |
mi_page_queue_enqueue_from(&mi_page_heap(page)->pages[MI_BIN_FULL], pq, page); |
| 378 |
_mi_page_free_collect(page,false); // try to collect right away in case another thread freed just before MI_USE_DELAYED_FREE was set |
| 379 |
} |
| 380 |
|
| 381 |
|
| 382 |
// Abandon a page with used blocks at the end of a thread. |
| 383 |
// Note: only call if it is ensured that no references exist from |
| 384 |
// the `page->heap->thread_delayed_free` into this page. |
| 385 |
// Currently only called through `mi_heap_collect_ex` which ensures this. |
| 386 |
void _mi_page_abandon(mi_page_t* page, mi_page_queue_t* pq) { |
| 387 |
mi_assert_internal(page != NULL); |
| 388 |
mi_assert_expensive(_mi_page_is_valid(page)); |
| 389 |
mi_assert_internal(pq == mi_page_queue_of(page)); |
| 390 |
mi_assert_internal(mi_page_heap(page) != NULL); |
| 391 |
|
| 392 |
mi_heap_t* pheap = mi_page_heap(page); |
| 393 |
|
| 394 |
#ifdef Py_GIL_DISABLED |
| 395 |
if (page->qsbr_node.next != NULL) { |
| 396 |
// remove from QSBR queue, but keep the goal |
| 397 |
llist_remove(&page->qsbr_node); |
| 398 |
} |
| 399 |
#endif |
| 400 |
|
| 401 |
// remove from our page list |
| 402 |
mi_segments_tld_t* segments_tld = &pheap->tld->segments; |
| 403 |
mi_page_queue_remove(pq, page); |
| 404 |
|
| 405 |
// page is no longer associated with our heap |
| 406 |
mi_assert_internal(mi_page_thread_free_flag(page)==MI_NEVER_DELAYED_FREE); |
| 407 |
mi_page_set_heap(page, NULL); |
| 408 |
|
| 409 |
#if (MI_DEBUG>1) && !MI_TRACK_ENABLED |
| 410 |
// check there are no references left.. |
| 411 |
for (mi_block_t* block = (mi_block_t*)pheap->thread_delayed_free; block != NULL; block = mi_block_nextx(pheap, block, pheap->keys)) { |
| 412 |
mi_assert_internal(_mi_ptr_page(block) != page); |
| 413 |
} |
| 414 |
#endif |
| 415 |
|
| 416 |
// and abandon it |
| 417 |
mi_assert_internal(mi_page_heap(page) == NULL); |
| 418 |
_mi_segment_page_abandon(page,segments_tld); |
| 419 |
} |
| 420 |
|
| 421 |
|
| 422 |
// Free a page with no more free blocks |
| 423 |
void _mi_page_free(mi_page_t* page, mi_page_queue_t* pq, bool force) { |
| 424 |
mi_assert_internal(page != NULL); |
| 425 |
mi_assert_expensive(_mi_page_is_valid(page)); |
| 426 |
mi_assert_internal(pq == mi_page_queue_of(page)); |
| 427 |
mi_assert_internal(mi_page_all_free(page)); |
| 428 |
mi_assert_internal(mi_page_thread_free_flag(page)!=MI_DELAYED_FREEING); |
| 429 |
|
| 430 |
// no more aligned blocks in here |
| 431 |
mi_page_set_has_aligned(page, false); |
| 432 |
|
| 433 |
mi_heap_t* heap = mi_page_heap(page); |
| 434 |
|
| 435 |
#ifdef Py_GIL_DISABLED |
| 436 |
mi_assert_internal(page->qsbr_goal == 0); |
| 437 |
mi_assert_internal(page->qsbr_node.next == NULL); |
| 438 |
#endif |
| 439 |
|
| 440 |
// remove from the page list |
| 441 |
// (no need to do _mi_heap_delayed_free first as all blocks are already free) |
| 442 |
mi_segments_tld_t* segments_tld = &heap->tld->segments; |
| 443 |
mi_page_queue_remove(pq, page); |
| 444 |
|
| 445 |
// and free it |
| 446 |
mi_page_set_heap(page,NULL); |
| 447 |
_mi_segment_page_free(page, force, segments_tld); |
| 448 |
} |
| 449 |
|
| 450 |
// Retire parameters |
| 451 |
#define MI_MAX_RETIRE_SIZE (MI_MEDIUM_OBJ_SIZE_MAX) |
| 452 |
#define MI_RETIRE_CYCLES (16) |
| 453 |
|
| 454 |
// Retire a page with no more used blocks |
| 455 |
// Important to not retire too quickly though as new |
| 456 |
// allocations might coming. |
| 457 |
// Note: called from `mi_free` and benchmarks often |
| 458 |
// trigger this due to freeing everything and then |
| 459 |
// allocating again so careful when changing this. |
| 460 |
void _mi_page_retire(mi_page_t* page) mi_attr_noexcept { |
| 461 |
mi_assert_internal(page != NULL); |
| 462 |
mi_assert_expensive(_mi_page_is_valid(page)); |
| 463 |
mi_assert_internal(mi_page_all_free(page)); |
| 464 |
|
| 465 |
mi_page_set_has_aligned(page, false); |
| 466 |
|
| 467 |
// any previous QSBR goals are no longer valid because we reused the page |
| 468 |
_PyMem_mi_page_clear_qsbr(page); |
| 469 |
|
| 470 |
// don't retire too often.. |
| 471 |
// (or we end up retiring and re-allocating most of the time) |
| 472 |
// NOTE: refine this more: we should not retire if this |
| 473 |
// is the only page left with free blocks. It is not clear |
| 474 |
// how to check this efficiently though... |
| 475 |
// for now, we don't retire if it is the only page left of this size class. |
| 476 |
mi_page_queue_t* pq = mi_page_queue_of(page); |
| 477 |
if mi_likely(page->xblock_size <= MI_MAX_RETIRE_SIZE && !mi_page_queue_is_special(pq)) { // not too large && not full or huge queue? |
| 478 |
if (pq->last==page && pq->first==page) { // the only page in the queue? |
| 479 |
mi_stat_counter_increase(_mi_stats_main.page_no_retire,1); |
| 480 |
page->retire_expire = 1 + (page->xblock_size <= MI_SMALL_OBJ_SIZE_MAX ? MI_RETIRE_CYCLES : MI_RETIRE_CYCLES/4); |
| 481 |
mi_heap_t* heap = mi_page_heap(page); |
| 482 |
mi_assert_internal(pq >= heap->pages); |
| 483 |
const size_t index = pq - heap->pages; |
| 484 |
mi_assert_internal(index < MI_BIN_FULL && index < MI_BIN_HUGE); |
| 485 |
if (index < heap->page_retired_min) heap->page_retired_min = index; |
| 486 |
if (index > heap->page_retired_max) heap->page_retired_max = index; |
| 487 |
mi_assert_internal(mi_page_all_free(page)); |
| 488 |
return; // don't free after all |
| 489 |
} |
| 490 |
} |
| 491 |
_PyMem_mi_page_maybe_free(page, pq, false); |
| 492 |
} |
| 493 |
|
| 494 |
// free retired pages: we don't need to look at the entire queues |
| 495 |
// since we only retire pages that are at the head position in a queue. |
| 496 |
void _mi_heap_collect_retired(mi_heap_t* heap, bool force) { |
| 497 |
size_t min = MI_BIN_FULL; |
| 498 |
size_t max = 0; |
| 499 |
for(size_t bin = heap->page_retired_min; bin <= heap->page_retired_max; bin++) { |
| 500 |
mi_page_queue_t* pq = &heap->pages[bin]; |
| 501 |
mi_page_t* page = pq->first; |
| 502 |
if (page != NULL && page->retire_expire != 0) { |
| 503 |
if (mi_page_all_free(page)) { |
| 504 |
page->retire_expire--; |
| 505 |
if (force || page->retire_expire == 0) { |
| 506 |
#ifdef Py_GIL_DISABLED |
| 507 |
mi_assert_internal(page->qsbr_goal == 0); |
| 508 |
#endif |
| 509 |
_PyMem_mi_page_maybe_free(page, pq, force); |
| 510 |
} |
| 511 |
else { |
| 512 |
// keep retired, update min/max |
| 513 |
if (bin < min) min = bin; |
| 514 |
if (bin > max) max = bin; |
| 515 |
} |
| 516 |
} |
| 517 |
else { |
| 518 |
page->retire_expire = 0; |
| 519 |
} |
| 520 |
} |
| 521 |
} |
| 522 |
heap->page_retired_min = min; |
| 523 |
heap->page_retired_max = max; |
| 524 |
} |
| 525 |
|
| 526 |
|
| 527 |
/* ----------------------------------------------------------- |
| 528 |
Initialize the initial free list in a page. |
| 529 |
In secure mode we initialize a randomized list by |
| 530 |
alternating between slices. |
| 531 |
----------------------------------------------------------- */ |
| 532 |
|
| 533 |
#define MI_MAX_SLICE_SHIFT (6) // at most 64 slices |
| 534 |
#define MI_MAX_SLICES (1UL << MI_MAX_SLICE_SHIFT) |
| 535 |
#define MI_MIN_SLICES (2) |
| 536 |
|
| 537 |
static void mi_page_free_list_extend_secure(mi_heap_t* const heap, mi_page_t* const page, const size_t bsize, const size_t extend, mi_stats_t* const stats) { |
| 538 |
MI_UNUSED(stats); |
| 539 |
#if (MI_SECURE<=2) |
| 540 |
mi_assert_internal(page->free == NULL); |
| 541 |
mi_assert_internal(page->local_free == NULL); |
| 542 |
#endif |
| 543 |
mi_assert_internal(page->capacity + extend <= page->reserved); |
| 544 |
mi_assert_internal(bsize == mi_page_block_size(page)); |
| 545 |
void* const page_area = _mi_page_start(_mi_page_segment(page), page, NULL); |
| 546 |
|
| 547 |
// initialize a randomized free list |
| 548 |
// set up `slice_count` slices to alternate between |
| 549 |
size_t shift = MI_MAX_SLICE_SHIFT; |
| 550 |
while ((extend >> shift) == 0) { |
| 551 |
shift--; |
| 552 |
} |
| 553 |
const size_t slice_count = (size_t)1U << shift; |
| 554 |
const size_t slice_extend = extend / slice_count; |
| 555 |
mi_assert_internal(slice_extend >= 1); |
| 556 |
mi_block_t* blocks[MI_MAX_SLICES]; // current start of the slice |
| 557 |
size_t counts[MI_MAX_SLICES]; // available objects in the slice |
| 558 |
for (size_t i = 0; i < slice_count; i++) { |
| 559 |
blocks[i] = mi_page_block_at(page, page_area, bsize, page->capacity + i*slice_extend); |
| 560 |
counts[i] = slice_extend; |
| 561 |
} |
| 562 |
counts[slice_count-1] += (extend % slice_count); // final slice holds the modulus too (todo: distribute evenly?) |
| 563 |
|
| 564 |
// and initialize the free list by randomly threading through them |
| 565 |
// set up first element |
| 566 |
const uintptr_t r = _mi_heap_random_next(heap); |
| 567 |
size_t current = r % slice_count; |
| 568 |
counts[current]--; |
| 569 |
mi_block_t* const free_start = blocks[current]; |
| 570 |
// and iterate through the rest; use `random_shuffle` for performance |
| 571 |
uintptr_t rnd = _mi_random_shuffle(r|1); // ensure not 0 |
| 572 |
for (size_t i = 1; i < extend; i++) { |
| 573 |
// call random_shuffle only every INTPTR_SIZE rounds |
| 574 |
const size_t round = i%MI_INTPTR_SIZE; |
| 575 |
if (round == 0) rnd = _mi_random_shuffle(rnd); |
| 576 |
// select a random next slice index |
| 577 |
size_t next = ((rnd >> 8*round) & (slice_count-1)); |
| 578 |
while (counts[next]==0) { // ensure it still has space |
| 579 |
next++; |
| 580 |
if (next==slice_count) next = 0; |
| 581 |
} |
| 582 |
// and link the current block to it |
| 583 |
counts[next]--; |
| 584 |
mi_block_t* const block = blocks[current]; |
| 585 |
blocks[current] = (mi_block_t*)((uint8_t*)block + bsize); // bump to the following block |
| 586 |
mi_block_set_next(page, block, blocks[next]); // and set next; note: we may have `current == next` |
| 587 |
current = next; |
| 588 |
} |
| 589 |
// prepend to the free list (usually NULL) |
| 590 |
mi_block_set_next(page, blocks[current], page->free); // end of the list |
| 591 |
page->free = free_start; |
| 592 |
} |
| 593 |
|
| 594 |
static mi_decl_noinline void mi_page_free_list_extend( mi_page_t* const page, const size_t bsize, const size_t extend, mi_stats_t* const stats) |
| 595 |
{ |
| 596 |
MI_UNUSED(stats); |
| 597 |
#if (MI_SECURE <= 2) |
| 598 |
mi_assert_internal(page->free == NULL); |
| 599 |
mi_assert_internal(page->local_free == NULL); |
| 600 |
#endif |
| 601 |
mi_assert_internal(page->capacity + extend <= page->reserved); |
| 602 |
mi_assert_internal(bsize == mi_page_block_size(page)); |
| 603 |
void* const page_area = _mi_page_start(_mi_page_segment(page), page, NULL ); |
| 604 |
|
| 605 |
mi_block_t* const start = mi_page_block_at(page, page_area, bsize, page->capacity); |
| 606 |
|
| 607 |
// initialize a sequential free list |
| 608 |
mi_block_t* const last = mi_page_block_at(page, page_area, bsize, page->capacity + extend - 1); |
| 609 |
mi_block_t* block = start; |
| 610 |
while(block <= last) { |
| 611 |
mi_block_t* next = (mi_block_t*)((uint8_t*)block + bsize); |
| 612 |
mi_block_set_next(page,block,next); |
| 613 |
block = next; |
| 614 |
} |
| 615 |
// prepend to free list (usually `NULL`) |
| 616 |
mi_block_set_next(page, last, page->free); |
| 617 |
page->free = start; |
| 618 |
} |
| 619 |
|
| 620 |
/* ----------------------------------------------------------- |
| 621 |
Page initialize and extend the capacity |
| 622 |
----------------------------------------------------------- */ |
| 623 |
|
| 624 |
#define MI_MAX_EXTEND_SIZE (4*1024) // heuristic, one OS page seems to work well. |
| 625 |
#if (MI_SECURE>0) |
| 626 |
#define MI_MIN_EXTEND (8*MI_SECURE) // extend at least by this many |
| 627 |
#else |
| 628 |
#define MI_MIN_EXTEND (4) |
| 629 |
#endif |
| 630 |
|
| 631 |
// Extend the capacity (up to reserved) by initializing a free list |
| 632 |
// We do at most `MI_MAX_EXTEND` to avoid touching too much memory |
| 633 |
// Note: we also experimented with "bump" allocation on the first |
| 634 |
// allocations but this did not speed up any benchmark (due to an |
| 635 |
// extra test in malloc? or cache effects?) |
| 636 |
static void mi_page_extend_free(mi_heap_t* heap, mi_page_t* page, mi_tld_t* tld) { |
| 637 |
MI_UNUSED(tld); |
| 638 |
mi_assert_expensive(mi_page_is_valid_init(page)); |
| 639 |
#if (MI_SECURE<=2) |
| 640 |
mi_assert(page->free == NULL); |
| 641 |
mi_assert(page->local_free == NULL); |
| 642 |
if (page->free != NULL) return; |
| 643 |
#endif |
| 644 |
if (page->capacity >= page->reserved) return; |
| 645 |
|
| 646 |
size_t page_size; |
| 647 |
_mi_page_start(_mi_page_segment(page), page, &page_size); |
| 648 |
mi_stat_counter_increase(tld->stats.pages_extended, 1); |
| 649 |
|
| 650 |
// calculate the extend count |
| 651 |
const size_t bsize = (page->xblock_size < MI_HUGE_BLOCK_SIZE ? page->xblock_size : page_size); |
| 652 |
size_t extend = page->reserved - page->capacity; |
| 653 |
mi_assert_internal(extend > 0); |
| 654 |
|
| 655 |
size_t max_extend = (bsize >= MI_MAX_EXTEND_SIZE ? MI_MIN_EXTEND : MI_MAX_EXTEND_SIZE/(uint32_t)bsize); |
| 656 |
if (max_extend < MI_MIN_EXTEND) { max_extend = MI_MIN_EXTEND; } |
| 657 |
mi_assert_internal(max_extend > 0); |
| 658 |
|
| 659 |
if (extend > max_extend) { |
| 660 |
// ensure we don't touch memory beyond the page to reduce page commit. |
| 661 |
// the `lean` benchmark tests this. Going from 1 to 8 increases rss by 50%. |
| 662 |
extend = max_extend; |
| 663 |
} |
| 664 |
|
| 665 |
mi_assert_internal(extend > 0 && extend + page->capacity <= page->reserved); |
| 666 |
mi_assert_internal(extend < (1UL<<16)); |
| 667 |
|
| 668 |
// and append the extend the free list |
| 669 |
if (extend < MI_MIN_SLICES || MI_SECURE==0) { //!mi_option_is_enabled(mi_option_secure)) { |
| 670 |
mi_page_free_list_extend(page, bsize, extend, &tld->stats ); |
| 671 |
} |
| 672 |
else { |
| 673 |
mi_page_free_list_extend_secure(heap, page, bsize, extend, &tld->stats); |
| 674 |
} |
| 675 |
// enable the new free list |
| 676 |
page->capacity += (uint16_t)extend; |
| 677 |
mi_stat_increase(tld->stats.page_committed, extend * bsize); |
| 678 |
mi_assert_expensive(mi_page_is_valid_init(page)); |
| 679 |
} |
| 680 |
|
| 681 |
// Initialize a fresh page |
| 682 |
static void mi_page_init(mi_heap_t* heap, mi_page_t* page, size_t block_size, mi_tld_t* tld) { |
| 683 |
mi_assert(page != NULL); |
| 684 |
mi_segment_t* segment = _mi_page_segment(page); |
| 685 |
mi_assert(segment != NULL); |
| 686 |
mi_assert_internal(block_size > 0); |
| 687 |
// set fields |
| 688 |
mi_page_set_heap(page, heap); |
| 689 |
page->tag = heap->tag; |
| 690 |
page->use_qsbr = heap->page_use_qsbr; |
| 691 |
page->debug_offset = heap->debug_offset; |
| 692 |
page->xblock_size = (block_size < MI_HUGE_BLOCK_SIZE ? (uint32_t)block_size : MI_HUGE_BLOCK_SIZE); // initialize before _mi_segment_page_start |
| 693 |
size_t page_size; |
| 694 |
const void* page_start = _mi_segment_page_start(segment, page, &page_size); |
| 695 |
MI_UNUSED(page_start); |
| 696 |
mi_track_mem_noaccess(page_start,page_size); |
| 697 |
mi_assert_internal(mi_page_block_size(page) <= page_size); |
| 698 |
mi_assert_internal(page_size <= page->slice_count*MI_SEGMENT_SLICE_SIZE); |
| 699 |
mi_assert_internal(page_size / block_size < (1L<<16)); |
| 700 |
page->reserved = (uint16_t)(page_size / block_size); |
| 701 |
mi_assert_internal(page->reserved > 0); |
| 702 |
#if (MI_PADDING || MI_ENCODE_FREELIST) |
| 703 |
page->keys[0] = _mi_heap_random_next(heap); |
| 704 |
page->keys[1] = _mi_heap_random_next(heap); |
| 705 |
#endif |
| 706 |
page->free_is_zero = page->is_zero_init; |
| 707 |
#if MI_DEBUG>2 |
| 708 |
if (page->is_zero_init) { |
| 709 |
mi_track_mem_defined(page_start, page_size); |
| 710 |
mi_assert_expensive(mi_mem_is_zero(page_start, page_size)); |
| 711 |
} |
| 712 |
#endif |
| 713 |
|
| 714 |
mi_assert_internal(page->is_committed); |
| 715 |
mi_assert_internal(page->capacity == 0); |
| 716 |
mi_assert_internal(page->free == NULL); |
| 717 |
mi_assert_internal(page->used == 0); |
| 718 |
mi_assert_internal(page->xthread_free == 0); |
| 719 |
mi_assert_internal(page->next == NULL); |
| 720 |
mi_assert_internal(page->prev == NULL); |
| 721 |
#ifdef Py_GIL_DISABLED |
| 722 |
mi_assert_internal(page->qsbr_goal == 0); |
| 723 |
mi_assert_internal(page->qsbr_node.next == NULL); |
| 724 |
#endif |
| 725 |
mi_assert_internal(page->retire_expire == 0); |
| 726 |
mi_assert_internal(!mi_page_has_aligned(page)); |
| 727 |
#if (MI_PADDING || MI_ENCODE_FREELIST) |
| 728 |
mi_assert_internal(page->keys[0] != 0); |
| 729 |
mi_assert_internal(page->keys[1] != 0); |
| 730 |
#endif |
| 731 |
mi_assert_expensive(mi_page_is_valid_init(page)); |
| 732 |
|
| 733 |
// initialize an initial free list |
| 734 |
mi_page_extend_free(heap,page,tld); |
| 735 |
mi_assert(mi_page_immediate_available(page)); |
| 736 |
} |
| 737 |
|
| 738 |
|
| 739 |
/* ----------------------------------------------------------- |
| 740 |
Find pages with free blocks |
| 741 |
-------------------------------------------------------------*/ |
| 742 |
|
| 743 |
// Find a page with free blocks of `page->block_size`. |
| 744 |
static mi_page_t* mi_page_queue_find_free_ex(mi_heap_t* heap, mi_page_queue_t* pq, bool first_try) |
| 745 |
{ |
| 746 |
// search through the pages in "next fit" order |
| 747 |
#if MI_STAT |
| 748 |
size_t count = 0; |
| 749 |
#endif |
| 750 |
mi_page_t* page = pq->first; |
| 751 |
while (page != NULL) |
| 752 |
{ |
| 753 |
mi_page_t* next = page->next; // remember next |
| 754 |
#if MI_STAT |
| 755 |
count++; |
| 756 |
#endif |
| 757 |
|
| 758 |
// 0. collect freed blocks by us and other threads |
| 759 |
_mi_page_free_collect(page, false); |
| 760 |
|
| 761 |
// 1. if the page contains free blocks, we are done |
| 762 |
if (mi_page_immediate_available(page)) { |
| 763 |
break; // pick this one |
| 764 |
} |
| 765 |
|
| 766 |
// 2. Try to extend |
| 767 |
if (page->capacity < page->reserved) { |
| 768 |
mi_page_extend_free(heap, page, heap->tld); |
| 769 |
mi_assert_internal(mi_page_immediate_available(page)); |
| 770 |
break; |
| 771 |
} |
| 772 |
|
| 773 |
// 3. If the page is completely full, move it to the `mi_pages_full` |
| 774 |
// queue so we don't visit long-lived pages too often. |
| 775 |
mi_assert_internal(!mi_page_is_in_full(page) && !mi_page_immediate_available(page)); |
| 776 |
mi_page_to_full(page, pq); |
| 777 |
|
| 778 |
page = next; |
| 779 |
} // for each page |
| 780 |
|
| 781 |
mi_heap_stat_counter_increase(heap, searches, count); |
| 782 |
|
| 783 |
if (page == NULL) { |
| 784 |
_PyMem_mi_heap_collect_qsbr(heap); // some pages might be safe to free now |
| 785 |
_mi_heap_collect_retired(heap, false); // perhaps make a page available? |
| 786 |
page = mi_page_fresh(heap, pq); |
| 787 |
if (page == NULL && first_try) { |
| 788 |
// out-of-memory _or_ an abandoned page with free blocks was reclaimed, try once again |
| 789 |
page = mi_page_queue_find_free_ex(heap, pq, false); |
| 790 |
} |
| 791 |
} |
| 792 |
else { |
| 793 |
mi_assert(pq->first == page); |
| 794 |
page->retire_expire = 0; |
| 795 |
_PyMem_mi_page_clear_qsbr(page); |
| 796 |
} |
| 797 |
mi_assert_internal(page == NULL || mi_page_immediate_available(page)); |
| 798 |
return page; |
| 799 |
} |
| 800 |
|
| 801 |
|
| 802 |
|
| 803 |
// Find a page with free blocks of `size`. |
| 804 |
static inline mi_page_t* mi_find_free_page(mi_heap_t* heap, size_t size) { |
| 805 |
mi_page_queue_t* pq = mi_page_queue(heap,size); |
| 806 |
mi_page_t* page = pq->first; |
| 807 |
if (page != NULL) { |
| 808 |
#if (MI_SECURE>=3) // in secure mode, we extend half the time to increase randomness |
| 809 |
if (page->capacity < page->reserved && ((_mi_heap_random_next(heap) & 1) == 1)) { |
| 810 |
mi_page_extend_free(heap, page, heap->tld); |
| 811 |
mi_assert_internal(mi_page_immediate_available(page)); |
| 812 |
} |
| 813 |
else |
| 814 |
#endif |
| 815 |
{ |
| 816 |
_mi_page_free_collect(page,false); |
| 817 |
} |
| 818 |
|
| 819 |
if (mi_page_immediate_available(page)) { |
| 820 |
page->retire_expire = 0; |
| 821 |
_PyMem_mi_page_clear_qsbr(page); |
| 822 |
return page; // fast path |
| 823 |
} |
| 824 |
} |
| 825 |
return mi_page_queue_find_free_ex(heap, pq, true); |
| 826 |
} |
| 827 |
|
| 828 |
|
| 829 |
/* ----------------------------------------------------------- |
| 830 |
Users can register a deferred free function called |
| 831 |
when the `free` list is empty. Since the `local_free` |
| 832 |
is separate this is deterministically called after |
| 833 |
a certain number of allocations. |
| 834 |
----------------------------------------------------------- */ |
| 835 |
|
| 836 |
static mi_deferred_free_fun* volatile deferred_free = NULL; |
| 837 |
static _Atomic(void*) deferred_arg; // = NULL |
| 838 |
|
| 839 |
void _mi_deferred_free(mi_heap_t* heap, bool force) { |
| 840 |
heap->tld->heartbeat++; |
| 841 |
if (deferred_free != NULL && !heap->tld->recurse) { |
| 842 |
heap->tld->recurse = true; |
| 843 |
deferred_free(force, heap->tld->heartbeat, mi_atomic_load_ptr_relaxed(void,&deferred_arg)); |
| 844 |
heap->tld->recurse = false; |
| 845 |
} |
| 846 |
} |
| 847 |
|
| 848 |
void mi_register_deferred_free(mi_deferred_free_fun* fn, void* arg) mi_attr_noexcept { |
| 849 |
deferred_free = fn; |
| 850 |
mi_atomic_store_ptr_release(void,&deferred_arg, arg); |
| 851 |
} |
| 852 |
|
| 853 |
|
| 854 |
/* ----------------------------------------------------------- |
| 855 |
General allocation |
| 856 |
----------------------------------------------------------- */ |
| 857 |
|
| 858 |
// Large and huge page allocation. |
| 859 |
// Huge pages are allocated directly without being in a queue. |
| 860 |
// Because huge pages contain just one block, and the segment contains |
| 861 |
// just that page, we always treat them as abandoned and any thread |
| 862 |
// that frees the block can free the whole page and segment directly. |
| 863 |
// Huge pages are also use if the requested alignment is very large (> MI_ALIGNMENT_MAX). |
| 864 |
static mi_page_t* mi_large_huge_page_alloc(mi_heap_t* heap, size_t size, size_t page_alignment) { |
| 865 |
size_t block_size = _mi_os_good_alloc_size(size); |
| 866 |
mi_assert_internal(mi_bin(block_size) == MI_BIN_HUGE || page_alignment > 0); |
| 867 |
bool is_huge = (block_size > MI_LARGE_OBJ_SIZE_MAX || page_alignment > 0); |
| 868 |
#if MI_HUGE_PAGE_ABANDON |
| 869 |
mi_page_queue_t* pq = (is_huge ? NULL : mi_page_queue(heap, block_size)); |
| 870 |
#else |
| 871 |
mi_page_queue_t* pq = mi_page_queue(heap, is_huge ? MI_HUGE_BLOCK_SIZE : block_size); // not block_size as that can be low if the page_alignment > 0 |
| 872 |
mi_assert_internal(!is_huge || mi_page_queue_is_huge(pq)); |
| 873 |
#endif |
| 874 |
mi_page_t* page = mi_page_fresh_alloc(heap, pq, block_size, page_alignment); |
| 875 |
if (page != NULL) { |
| 876 |
mi_assert_internal(mi_page_immediate_available(page)); |
| 877 |
|
| 878 |
if (is_huge) { |
| 879 |
mi_assert_internal(_mi_page_segment(page)->kind == MI_SEGMENT_HUGE); |
| 880 |
mi_assert_internal(_mi_page_segment(page)->used==1); |
| 881 |
#if MI_HUGE_PAGE_ABANDON |
| 882 |
mi_assert_internal(_mi_page_segment(page)->thread_id==0); // abandoned, not in the huge queue |
| 883 |
mi_page_set_heap(page, NULL); |
| 884 |
#endif |
| 885 |
} |
| 886 |
else { |
| 887 |
mi_assert_internal(_mi_page_segment(page)->kind != MI_SEGMENT_HUGE); |
| 888 |
} |
| 889 |
|
| 890 |
const size_t bsize = mi_page_usable_block_size(page); // note: not `mi_page_block_size` to account for padding |
| 891 |
if (bsize <= MI_LARGE_OBJ_SIZE_MAX) { |
| 892 |
mi_heap_stat_increase(heap, large, bsize); |
| 893 |
mi_heap_stat_counter_increase(heap, large_count, 1); |
| 894 |
} |
| 895 |
else { |
| 896 |
mi_heap_stat_increase(heap, huge, bsize); |
| 897 |
mi_heap_stat_counter_increase(heap, huge_count, 1); |
| 898 |
} |
| 899 |
} |
| 900 |
return page; |
| 901 |
} |
| 902 |
|
| 903 |
|
| 904 |
// Allocate a page |
| 905 |
// Note: in debug mode the size includes MI_PADDING_SIZE and might have overflowed. |
| 906 |
static mi_page_t* mi_find_page(mi_heap_t* heap, size_t size, size_t huge_alignment) mi_attr_noexcept { |
| 907 |
// huge allocation? |
| 908 |
const size_t req_size = size - MI_PADDING_SIZE; // correct for padding_size in case of an overflow on `size` |
| 909 |
if mi_unlikely(req_size > (MI_MEDIUM_OBJ_SIZE_MAX - MI_PADDING_SIZE) || huge_alignment > 0) { |
| 910 |
if mi_unlikely(req_size > PTRDIFF_MAX) { // we don't allocate more than PTRDIFF_MAX (see <https://sourceware.org/ml/libc-announce/2019/msg00001.html>) |
| 911 |
_mi_error_message(EOVERFLOW, "allocation request is too large (%zu bytes)\n", req_size); |
| 912 |
return NULL; |
| 913 |
} |
| 914 |
else { |
| 915 |
_PyMem_mi_heap_collect_qsbr(heap); |
| 916 |
return mi_large_huge_page_alloc(heap,size,huge_alignment); |
| 917 |
} |
| 918 |
} |
| 919 |
else { |
| 920 |
// otherwise find a page with free blocks in our size segregated queues |
| 921 |
#if MI_PADDING |
| 922 |
mi_assert_internal(size >= MI_PADDING_SIZE); |
| 923 |
#endif |
| 924 |
return mi_find_free_page(heap, size); |
| 925 |
} |
| 926 |
} |
| 927 |
|
| 928 |
// Generic allocation routine if the fast path (`alloc.c:mi_page_malloc`) does not succeed. |
| 929 |
// Note: in debug mode the size includes MI_PADDING_SIZE and might have overflowed. |
| 930 |
// The `huge_alignment` is normally 0 but is set to a multiple of MI_SEGMENT_SIZE for |
| 931 |
// very large requested alignments in which case we use a huge segment. |
| 932 |
void* _mi_malloc_generic(mi_heap_t* heap, size_t size, bool zero, size_t huge_alignment) mi_attr_noexcept |
| 933 |
{ |
| 934 |
mi_assert_internal(heap != NULL); |
| 935 |
|
| 936 |
// initialize if necessary |
| 937 |
if mi_unlikely(!mi_heap_is_initialized(heap)) { |
| 938 |
heap = mi_heap_get_default(); // calls mi_thread_init |
| 939 |
if mi_unlikely(!mi_heap_is_initialized(heap)) { return NULL; } |
| 940 |
} |
| 941 |
mi_assert_internal(mi_heap_is_initialized(heap)); |
| 942 |
|
| 943 |
// call potential deferred free routines |
| 944 |
_mi_deferred_free(heap, false); |
| 945 |
|
| 946 |
// free delayed frees from other threads (but skip contended ones) |
| 947 |
_mi_heap_delayed_free_partial(heap); |
| 948 |
|
| 949 |
// find (or allocate) a page of the right size |
| 950 |
mi_page_t* page = mi_find_page(heap, size, huge_alignment); |
| 951 |
if mi_unlikely(page == NULL) { // first time out of memory, try to collect and retry the allocation once more |
| 952 |
mi_heap_collect(heap, true /* force */); |
| 953 |
page = mi_find_page(heap, size, huge_alignment); |
| 954 |
} |
| 955 |
|
| 956 |
if mi_unlikely(page == NULL) { // out of memory |
| 957 |
const size_t req_size = size - MI_PADDING_SIZE; // correct for padding_size in case of an overflow on `size` |
| 958 |
_mi_error_message(ENOMEM, "unable to allocate memory (%zu bytes)\n", req_size); |
| 959 |
return NULL; |
| 960 |
} |
| 961 |
|
| 962 |
mi_assert_internal(mi_page_immediate_available(page)); |
| 963 |
mi_assert_internal(mi_page_block_size(page) >= size); |
| 964 |
|
| 965 |
// and try again, this time succeeding! (i.e. this should never recurse through _mi_page_malloc) |
| 966 |
if mi_unlikely(zero && page->xblock_size == 0) { |
| 967 |
// note: we cannot call _mi_page_malloc with zeroing for huge blocks; we zero it afterwards in that case. |
| 968 |
void* p = _mi_page_malloc(heap, page, size, false); |
| 969 |
mi_assert_internal(p != NULL); |
| 970 |
_mi_memzero_aligned(p, mi_page_usable_block_size(page)); |
| 971 |
return p; |
| 972 |
} |
| 973 |
else { |
| 974 |
return _mi_page_malloc(heap, page, size, zero); |
| 975 |
} |
| 976 |
} |