microsoft/qdk
Publicmirrored fromhttps://github.com/microsoft/qdkAvailable
source/allocator/mimalloc-sys/mimalloc/src/arena-abandon.c
346lines · modecode
| 1 | /* ---------------------------------------------------------------------------- |
| 2 | Copyright (c) 2019-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 | |
| 8 | #if !defined(MI_IN_ARENA_C) |
| 9 | #error "this file should be included from 'arena.c' (so mi_arena_t is visible)" |
| 10 | // add includes help an IDE |
| 11 | #include "mimalloc.h" |
| 12 | #include "mimalloc/internal.h" |
| 13 | #include "bitmap.h" |
| 14 | #endif |
| 15 | |
| 16 | // Minimal exports for arena-abandoned. |
| 17 | size_t mi_arena_id_index(mi_arena_id_t id); |
| 18 | mi_arena_t* mi_arena_from_index(size_t idx); |
| 19 | size_t mi_arena_get_count(void); |
| 20 | void* mi_arena_block_start(mi_arena_t* arena, mi_bitmap_index_t bindex); |
| 21 | bool mi_arena_memid_indices(mi_memid_t memid, size_t* arena_index, mi_bitmap_index_t* bitmap_index); |
| 22 | |
| 23 | /* ----------------------------------------------------------- |
| 24 | Abandoned blocks/segments: |
| 25 | |
| 26 | _mi_arena_segment_clear_abandoned |
| 27 | _mi_arena_segment_mark_abandoned |
| 28 | |
| 29 | This is used to atomically abandon/reclaim segments |
| 30 | (and crosses the arena API but it is convenient to have here). |
| 31 | |
| 32 | Abandoned segments still have live blocks; they get reclaimed |
| 33 | when a thread frees a block in it, or when a thread needs a fresh |
| 34 | segment. |
| 35 | |
| 36 | Abandoned segments are atomically marked in the `block_abandoned` |
| 37 | bitmap of arenas. Any segments allocated outside arenas are put |
| 38 | in the sub-process `abandoned_os_list`. This list is accessed |
| 39 | using locks but this should be uncommon and generally uncontended. |
| 40 | Reclaim and visiting either scan through the `block_abandoned` |
| 41 | bitmaps of the arena's, or visit the `abandoned_os_list` |
| 42 | |
| 43 | A potentially nicer design is to use arena's for everything |
| 44 | and perhaps have virtual arena's to map OS allocated memory |
| 45 | but this would lack the "density" of our current arena's. TBC. |
| 46 | ----------------------------------------------------------- */ |
| 47 | |
| 48 | |
| 49 | // reclaim a specific OS abandoned segment; `true` on success. |
| 50 | // sets the thread_id. |
| 51 | static bool mi_arena_segment_os_clear_abandoned(mi_segment_t* segment, bool take_lock) { |
| 52 | mi_assert(segment->memid.memkind != MI_MEM_ARENA); |
| 53 | // not in an arena, remove from list of abandoned os segments |
| 54 | mi_subproc_t* const subproc = segment->subproc; |
| 55 | if (take_lock && !mi_lock_try_acquire(&subproc->abandoned_os_lock)) { |
| 56 | return false; // failed to acquire the lock, we just give up |
| 57 | } |
| 58 | // remove atomically from the abandoned os list (if possible!) |
| 59 | bool reclaimed = false; |
| 60 | mi_segment_t* const next = segment->abandoned_os_next; |
| 61 | mi_segment_t* const prev = segment->abandoned_os_prev; |
| 62 | if (next != NULL || prev != NULL || subproc->abandoned_os_list == segment) { |
| 63 | #if MI_DEBUG>3 |
| 64 | // find ourselves in the abandoned list (and check the count) |
| 65 | bool found = false; |
| 66 | size_t count = 0; |
| 67 | for (mi_segment_t* current = subproc->abandoned_os_list; current != NULL; current = current->abandoned_os_next) { |
| 68 | if (current == segment) { found = true; } |
| 69 | count++; |
| 70 | } |
| 71 | mi_assert_internal(found); |
| 72 | mi_assert_internal(count == mi_atomic_load_relaxed(&subproc->abandoned_os_list_count)); |
| 73 | #endif |
| 74 | // remove (atomically) from the list and reclaim |
| 75 | if (prev != NULL) { prev->abandoned_os_next = next; } |
| 76 | else { subproc->abandoned_os_list = next; } |
| 77 | if (next != NULL) { next->abandoned_os_prev = prev; } |
| 78 | else { subproc->abandoned_os_list_tail = prev; } |
| 79 | segment->abandoned_os_next = NULL; |
| 80 | segment->abandoned_os_prev = NULL; |
| 81 | mi_atomic_decrement_relaxed(&subproc->abandoned_count); |
| 82 | mi_atomic_decrement_relaxed(&subproc->abandoned_os_list_count); |
| 83 | if (take_lock) { // don't reset the thread_id when iterating |
| 84 | mi_atomic_store_release(&segment->thread_id, _mi_thread_id()); |
| 85 | } |
| 86 | reclaimed = true; |
| 87 | } |
| 88 | if (take_lock) { mi_lock_release(&segment->subproc->abandoned_os_lock); } |
| 89 | return reclaimed; |
| 90 | } |
| 91 | |
| 92 | // reclaim a specific abandoned segment; `true` on success. |
| 93 | // sets the thread_id. |
| 94 | bool _mi_arena_segment_clear_abandoned(mi_segment_t* segment) { |
| 95 | if mi_unlikely(segment->memid.memkind != MI_MEM_ARENA) { |
| 96 | return mi_arena_segment_os_clear_abandoned(segment, true /* take lock */); |
| 97 | } |
| 98 | // arena segment: use the blocks_abandoned bitmap. |
| 99 | size_t arena_idx; |
| 100 | size_t bitmap_idx; |
| 101 | mi_arena_memid_indices(segment->memid, &arena_idx, &bitmap_idx); |
| 102 | mi_arena_t* arena = mi_arena_from_index(arena_idx); |
| 103 | mi_assert_internal(arena != NULL); |
| 104 | // reclaim atomically |
| 105 | bool was_marked = _mi_bitmap_unclaim(arena->blocks_abandoned, arena->field_count, 1, bitmap_idx); |
| 106 | if (was_marked) { |
| 107 | mi_assert_internal(mi_atomic_load_acquire(&segment->thread_id) == 0); |
| 108 | mi_atomic_decrement_relaxed(&segment->subproc->abandoned_count); |
| 109 | mi_atomic_store_release(&segment->thread_id, _mi_thread_id()); |
| 110 | } |
| 111 | // mi_assert_internal(was_marked); |
| 112 | mi_assert_internal(!was_marked || _mi_bitmap_is_claimed(arena->blocks_inuse, arena->field_count, 1, bitmap_idx)); |
| 113 | //mi_assert_internal(arena->blocks_committed == NULL || _mi_bitmap_is_claimed(arena->blocks_committed, arena->field_count, 1, bitmap_idx)); |
| 114 | return was_marked; |
| 115 | } |
| 116 | |
| 117 | |
| 118 | // mark a specific OS segment as abandoned |
| 119 | static void mi_arena_segment_os_mark_abandoned(mi_segment_t* segment) { |
| 120 | mi_assert(segment->memid.memkind != MI_MEM_ARENA); |
| 121 | // not in an arena; we use a list of abandoned segments |
| 122 | mi_subproc_t* const subproc = segment->subproc; |
| 123 | mi_lock(&subproc->abandoned_os_lock) { |
| 124 | // push on the tail of the list (important for the visitor) |
| 125 | mi_segment_t* prev = subproc->abandoned_os_list_tail; |
| 126 | mi_assert_internal(prev == NULL || prev->abandoned_os_next == NULL); |
| 127 | mi_assert_internal(segment->abandoned_os_prev == NULL); |
| 128 | mi_assert_internal(segment->abandoned_os_next == NULL); |
| 129 | if (prev != NULL) { prev->abandoned_os_next = segment; } |
| 130 | else { subproc->abandoned_os_list = segment; } |
| 131 | subproc->abandoned_os_list_tail = segment; |
| 132 | segment->abandoned_os_prev = prev; |
| 133 | segment->abandoned_os_next = NULL; |
| 134 | mi_atomic_increment_relaxed(&subproc->abandoned_os_list_count); |
| 135 | mi_atomic_increment_relaxed(&subproc->abandoned_count); |
| 136 | // and release the lock |
| 137 | } |
| 138 | return; |
| 139 | } |
| 140 | |
| 141 | // mark a specific segment as abandoned |
| 142 | // clears the thread_id. |
| 143 | void _mi_arena_segment_mark_abandoned(mi_segment_t* segment) |
| 144 | { |
| 145 | mi_assert_internal(segment->used == segment->abandoned); |
| 146 | mi_atomic_store_release(&segment->thread_id, (uintptr_t)0); // mark as abandoned for multi-thread free's |
| 147 | if mi_unlikely(segment->memid.memkind != MI_MEM_ARENA) { |
| 148 | mi_arena_segment_os_mark_abandoned(segment); |
| 149 | return; |
| 150 | } |
| 151 | // segment is in an arena, mark it in the arena `blocks_abandoned` bitmap |
| 152 | size_t arena_idx; |
| 153 | size_t bitmap_idx; |
| 154 | mi_arena_memid_indices(segment->memid, &arena_idx, &bitmap_idx); |
| 155 | mi_arena_t* arena = mi_arena_from_index(arena_idx); |
| 156 | mi_assert_internal(arena != NULL); |
| 157 | // set abandonment atomically |
| 158 | mi_subproc_t* const subproc = segment->subproc; // don't access the segment after setting it abandoned |
| 159 | const bool was_unmarked = _mi_bitmap_claim(arena->blocks_abandoned, arena->field_count, 1, bitmap_idx, NULL); |
| 160 | if (was_unmarked) { mi_atomic_increment_relaxed(&subproc->abandoned_count); } |
| 161 | mi_assert_internal(was_unmarked); |
| 162 | mi_assert_internal(_mi_bitmap_is_claimed(arena->blocks_inuse, arena->field_count, 1, bitmap_idx)); |
| 163 | } |
| 164 | |
| 165 | |
| 166 | /* ----------------------------------------------------------- |
| 167 | Iterate through the abandoned blocks/segments using a cursor. |
| 168 | This is used for reclaiming and abandoned block visiting. |
| 169 | ----------------------------------------------------------- */ |
| 170 | |
| 171 | // start a cursor at a randomized arena |
| 172 | void _mi_arena_field_cursor_init(mi_heap_t* heap, mi_subproc_t* subproc, bool visit_all, mi_arena_field_cursor_t* current) { |
| 173 | mi_assert_internal(heap == NULL || heap->tld->segments.subproc == subproc); |
| 174 | current->bitmap_idx = 0; |
| 175 | current->subproc = subproc; |
| 176 | current->visit_all = visit_all; |
| 177 | current->hold_visit_lock = false; |
| 178 | const size_t abandoned_count = mi_atomic_load_relaxed(&subproc->abandoned_count); |
| 179 | const size_t abandoned_list_count = mi_atomic_load_relaxed(&subproc->abandoned_os_list_count); |
| 180 | const size_t max_arena = mi_arena_get_count(); |
| 181 | if (heap != NULL && heap->arena_id != _mi_arena_id_none()) { |
| 182 | // for a heap that is bound to one arena, only visit that arena |
| 183 | current->start = mi_arena_id_index(heap->arena_id); |
| 184 | current->end = current->start + 1; |
| 185 | current->os_list_count = 0; |
| 186 | } |
| 187 | else { |
| 188 | // otherwise visit all starting at a random location |
| 189 | if (abandoned_count > abandoned_list_count && max_arena > 0) { |
| 190 | current->start = (heap == NULL || max_arena == 0 ? 0 : (mi_arena_id_t)(_mi_heap_random_next(heap) % max_arena)); |
| 191 | current->end = current->start + max_arena; |
| 192 | } |
| 193 | else { |
| 194 | current->start = 0; |
| 195 | current->end = 0; |
| 196 | } |
| 197 | current->os_list_count = abandoned_list_count; // max entries to visit in the os abandoned list |
| 198 | } |
| 199 | mi_assert_internal(current->start <= max_arena); |
| 200 | } |
| 201 | |
| 202 | void _mi_arena_field_cursor_done(mi_arena_field_cursor_t* current) { |
| 203 | if (current->hold_visit_lock) { |
| 204 | mi_lock_release(¤t->subproc->abandoned_os_visit_lock); |
| 205 | current->hold_visit_lock = false; |
| 206 | } |
| 207 | } |
| 208 | |
| 209 | static mi_segment_t* mi_arena_segment_clear_abandoned_at(mi_arena_t* arena, mi_subproc_t* subproc, mi_bitmap_index_t bitmap_idx) { |
| 210 | // try to reclaim an abandoned segment in the arena atomically |
| 211 | if (!_mi_bitmap_unclaim(arena->blocks_abandoned, arena->field_count, 1, bitmap_idx)) return NULL; |
| 212 | mi_assert_internal(_mi_bitmap_is_claimed(arena->blocks_inuse, arena->field_count, 1, bitmap_idx)); |
| 213 | mi_segment_t* segment = (mi_segment_t*)mi_arena_block_start(arena, bitmap_idx); |
| 214 | mi_assert_internal(mi_atomic_load_relaxed(&segment->thread_id) == 0); |
| 215 | // check that the segment belongs to our sub-process |
| 216 | // note: this is the reason we need the `abandoned_visit` lock in the case abandoned visiting is enabled. |
| 217 | // without the lock an abandoned visit may otherwise fail to visit all abandoned segments in the sub-process. |
| 218 | // for regular reclaim it is fine to miss one sometimes so without abandoned visiting we don't need the `abandoned_visit` lock. |
| 219 | if (segment->subproc != subproc) { |
| 220 | // it is from another sub-process, re-mark it and continue searching |
| 221 | const bool was_zero = _mi_bitmap_claim(arena->blocks_abandoned, arena->field_count, 1, bitmap_idx, NULL); |
| 222 | mi_assert_internal(was_zero); MI_UNUSED(was_zero); |
| 223 | return NULL; |
| 224 | } |
| 225 | else { |
| 226 | // success, we unabandoned a segment in our sub-process |
| 227 | mi_atomic_decrement_relaxed(&subproc->abandoned_count); |
| 228 | return segment; |
| 229 | } |
| 230 | } |
| 231 | |
| 232 | static mi_segment_t* mi_arena_segment_clear_abandoned_next_field(mi_arena_field_cursor_t* previous) { |
| 233 | const size_t max_arena = mi_arena_get_count(); |
| 234 | size_t field_idx = mi_bitmap_index_field(previous->bitmap_idx); |
| 235 | size_t bit_idx = mi_bitmap_index_bit_in_field(previous->bitmap_idx); |
| 236 | // visit arena's (from the previous cursor) |
| 237 | for (; previous->start < previous->end; previous->start++, field_idx = 0, bit_idx = 0) { |
| 238 | // index wraps around |
| 239 | size_t arena_idx = (previous->start >= max_arena ? previous->start % max_arena : previous->start); |
| 240 | mi_arena_t* arena = mi_arena_from_index(arena_idx); |
| 241 | if (arena != NULL) { |
| 242 | bool has_lock = false; |
| 243 | // visit the abandoned fields (starting at previous_idx) |
| 244 | for (; field_idx < arena->field_count; field_idx++, bit_idx = 0) { |
| 245 | size_t field = mi_atomic_load_relaxed(&arena->blocks_abandoned[field_idx]); |
| 246 | if mi_unlikely(field != 0) { // skip zero fields quickly |
| 247 | // we only take the arena lock if there are actually abandoned segments present |
| 248 | if (!has_lock && mi_option_is_enabled(mi_option_visit_abandoned)) { |
| 249 | has_lock = (previous->visit_all ? (mi_lock_acquire(&arena->abandoned_visit_lock),true) : mi_lock_try_acquire(&arena->abandoned_visit_lock)); |
| 250 | if (!has_lock) { |
| 251 | if (previous->visit_all) { |
| 252 | _mi_error_message(EFAULT, "internal error: failed to visit all abandoned segments due to failure to acquire the visitor lock"); |
| 253 | } |
| 254 | // skip to next arena |
| 255 | break; |
| 256 | } |
| 257 | } |
| 258 | mi_assert_internal(has_lock || !mi_option_is_enabled(mi_option_visit_abandoned)); |
| 259 | // visit each set bit in the field (todo: maybe use `ctz` here?) |
| 260 | for (; bit_idx < MI_BITMAP_FIELD_BITS; bit_idx++) { |
| 261 | // pre-check if the bit is set |
| 262 | size_t mask = ((size_t)1 << bit_idx); |
| 263 | if mi_unlikely((field & mask) == mask) { |
| 264 | mi_bitmap_index_t bitmap_idx = mi_bitmap_index_create(field_idx, bit_idx); |
| 265 | mi_segment_t* const segment = mi_arena_segment_clear_abandoned_at(arena, previous->subproc, bitmap_idx); |
| 266 | if (segment != NULL) { |
| 267 | //mi_assert_internal(arena->blocks_committed == NULL || _mi_bitmap_is_claimed(arena->blocks_committed, arena->field_count, 1, bitmap_idx)); |
| 268 | if (has_lock) { mi_lock_release(&arena->abandoned_visit_lock); } |
| 269 | previous->bitmap_idx = mi_bitmap_index_create_ex(field_idx, bit_idx + 1); // start at next one for the next iteration |
| 270 | return segment; |
| 271 | } |
| 272 | } |
| 273 | } |
| 274 | } |
| 275 | } |
| 276 | if (has_lock) { mi_lock_release(&arena->abandoned_visit_lock); } |
| 277 | } |
| 278 | } |
| 279 | return NULL; |
| 280 | } |
| 281 | |
| 282 | static mi_segment_t* mi_arena_segment_clear_abandoned_next_list(mi_arena_field_cursor_t* previous) { |
| 283 | // go through the abandoned_os_list |
| 284 | // we only allow one thread per sub-process to do to visit guarded by the `abandoned_os_visit_lock`. |
| 285 | // The lock is released when the cursor is released. |
| 286 | if (!previous->hold_visit_lock) { |
| 287 | previous->hold_visit_lock = (previous->visit_all ? (mi_lock_acquire(&previous->subproc->abandoned_os_visit_lock),true) |
| 288 | : mi_lock_try_acquire(&previous->subproc->abandoned_os_visit_lock)); |
| 289 | if (!previous->hold_visit_lock) { |
| 290 | if (previous->visit_all) { |
| 291 | _mi_error_message(EFAULT, "internal error: failed to visit all abandoned segments due to failure to acquire the OS visitor lock"); |
| 292 | } |
| 293 | return NULL; // we cannot get the lock, give up |
| 294 | } |
| 295 | } |
| 296 | // One list entry at a time |
| 297 | while (previous->os_list_count > 0) { |
| 298 | previous->os_list_count--; |
| 299 | mi_lock_acquire(&previous->subproc->abandoned_os_lock); // this could contend with concurrent OS block abandonment and reclaim from `free` |
| 300 | mi_segment_t* segment = previous->subproc->abandoned_os_list; |
| 301 | // pop from head of the list, a subsequent mark will push at the end (and thus we iterate through os_list_count entries) |
| 302 | if (segment == NULL || mi_arena_segment_os_clear_abandoned(segment, false /* we already have the lock */)) { |
| 303 | mi_lock_release(&previous->subproc->abandoned_os_lock); |
| 304 | return segment; |
| 305 | } |
| 306 | // already abandoned, try again |
| 307 | mi_lock_release(&previous->subproc->abandoned_os_lock); |
| 308 | } |
| 309 | // done |
| 310 | mi_assert_internal(previous->os_list_count == 0); |
| 311 | return NULL; |
| 312 | } |
| 313 | |
| 314 | |
| 315 | // reclaim abandoned segments |
| 316 | // this does not set the thread id (so it appears as still abandoned) |
| 317 | mi_segment_t* _mi_arena_segment_clear_abandoned_next(mi_arena_field_cursor_t* previous) { |
| 318 | if (previous->start < previous->end) { |
| 319 | // walk the arena |
| 320 | mi_segment_t* segment = mi_arena_segment_clear_abandoned_next_field(previous); |
| 321 | if (segment != NULL) { return segment; } |
| 322 | } |
| 323 | // no entries in the arena's anymore, walk the abandoned OS list |
| 324 | mi_assert_internal(previous->start == previous->end); |
| 325 | return mi_arena_segment_clear_abandoned_next_list(previous); |
| 326 | } |
| 327 | |
| 328 | |
| 329 | bool mi_abandoned_visit_blocks(mi_subproc_id_t subproc_id, int heap_tag, bool visit_blocks, mi_block_visit_fun* visitor, void* arg) { |
| 330 | // (unfortunately) the visit_abandoned option must be enabled from the start. |
| 331 | // This is to avoid taking locks if abandoned list visiting is not required (as for most programs) |
| 332 | if (!mi_option_is_enabled(mi_option_visit_abandoned)) { |
| 333 | _mi_error_message(EFAULT, "internal error: can only visit abandoned blocks when MIMALLOC_VISIT_ABANDONED=ON"); |
| 334 | return false; |
| 335 | } |
| 336 | mi_arena_field_cursor_t current; |
| 337 | _mi_arena_field_cursor_init(NULL, _mi_subproc_from_id(subproc_id), true /* visit all (blocking) */, ¤t); |
| 338 | mi_segment_t* segment; |
| 339 | bool ok = true; |
| 340 | while (ok && (segment = _mi_arena_segment_clear_abandoned_next(¤t)) != NULL) { |
| 341 | ok = _mi_segment_visit_blocks(segment, heap_tag, visit_blocks, visitor, arg); |
| 342 | _mi_arena_segment_mark_abandoned(segment); |
| 343 | } |
| 344 | _mi_arena_field_cursor_done(¤t); |
| 345 | return ok; |
| 346 | } |
| 347 | |