Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/python3.14/internal/mimalloc/mimalloc/internal.h
1 /* ---------------------------------------------------------------------------- 2 Copyright (c) 2018-2023, 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 #pragma once 8 #ifndef MIMALLOC_INTERNAL_H 9 #define MIMALLOC_INTERNAL_H 10 11 12 // -------------------------------------------------------------------------- 13 // This file contains the internal API's of mimalloc and various utility 14 // functions and macros. 15 // -------------------------------------------------------------------------- 16 17 #include "types.h" 18 #include "track.h" 19 20 #if (MI_DEBUG>0) 21 #define mi_trace_message(...) _mi_trace_message(__VA_ARGS__) 22 #else 23 #define mi_trace_message(...) 24 #endif 25 26 #if defined(__EMSCRIPTEN__) && !defined(__wasi__) 27 #define __wasi__ 28 #endif 29 30 #if defined(__cplusplus) 31 #define mi_decl_externc extern "C" 32 #else 33 #define mi_decl_externc 34 #endif 35 36 // pthreads 37 #if !defined(_WIN32) && !defined(__wasi__) 38 #define MI_USE_PTHREADS 39 #include <pthread.h> 40 #endif 41 42 // "options.c" 43 void _mi_fputs(mi_output_fun* out, void* arg, const char* prefix, const char* message); 44 void _mi_fprintf(mi_output_fun* out, void* arg, const char* fmt, ...); 45 void _mi_warning_message(const char* fmt, ...); 46 void _mi_verbose_message(const char* fmt, ...); 47 void _mi_trace_message(const char* fmt, ...); 48 void _mi_options_init(void); 49 void _mi_error_message(int err, const char* fmt, ...); 50 51 // random.c 52 void _mi_random_init(mi_random_ctx_t* ctx); 53 void _mi_random_init_weak(mi_random_ctx_t* ctx); 54 void _mi_random_reinit_if_weak(mi_random_ctx_t * ctx); 55 void _mi_random_split(mi_random_ctx_t* ctx, mi_random_ctx_t* new_ctx); 56 uintptr_t _mi_random_next(mi_random_ctx_t* ctx); 57 uintptr_t _mi_heap_random_next(mi_heap_t* heap); 58 uintptr_t _mi_os_random_weak(uintptr_t extra_seed); 59 static inline uintptr_t _mi_random_shuffle(uintptr_t x); 60 61 // init.c 62 extern mi_decl_cache_align mi_stats_t _mi_stats_main; 63 extern mi_decl_cache_align const mi_page_t _mi_page_empty; 64 bool _mi_is_main_thread(void); 65 size_t _mi_current_thread_count(void); 66 bool _mi_preloading(void); // true while the C runtime is not initialized yet 67 mi_threadid_t _mi_thread_id(void) mi_attr_noexcept; 68 mi_heap_t* _mi_heap_main_get(void); // statically allocated main backing heap 69 void _mi_thread_done(mi_heap_t* heap); 70 void _mi_thread_data_collect(void); 71 void _mi_tld_init(mi_tld_t* tld, mi_heap_t* bheap); 72 73 // os.c 74 void _mi_os_init(void); // called from process init 75 void* _mi_os_alloc(size_t size, mi_memid_t* memid, mi_stats_t* stats); 76 void _mi_os_free(void* p, size_t size, mi_memid_t memid, mi_stats_t* stats); 77 void _mi_os_free_ex(void* p, size_t size, bool still_committed, mi_memid_t memid, mi_stats_t* stats); 78 79 size_t _mi_os_page_size(void); 80 size_t _mi_os_good_alloc_size(size_t size); 81 bool _mi_os_has_overcommit(void); 82 bool _mi_os_has_virtual_reserve(void); 83 84 bool _mi_os_purge(void* p, size_t size, mi_stats_t* stats); 85 bool _mi_os_reset(void* addr, size_t size, mi_stats_t* tld_stats); 86 bool _mi_os_commit(void* p, size_t size, bool* is_zero, mi_stats_t* stats); 87 bool _mi_os_decommit(void* addr, size_t size, mi_stats_t* stats); 88 bool _mi_os_protect(void* addr, size_t size); 89 bool _mi_os_unprotect(void* addr, size_t size); 90 bool _mi_os_purge(void* p, size_t size, mi_stats_t* stats); 91 bool _mi_os_purge_ex(void* p, size_t size, bool allow_reset, mi_stats_t* stats); 92 93 void* _mi_os_alloc_aligned(size_t size, size_t alignment, bool commit, bool allow_large, mi_memid_t* memid, mi_stats_t* stats); 94 void* _mi_os_alloc_aligned_at_offset(size_t size, size_t alignment, size_t align_offset, bool commit, bool allow_large, mi_memid_t* memid, mi_stats_t* tld_stats); 95 96 void* _mi_os_get_aligned_hint(size_t try_alignment, size_t size); 97 bool _mi_os_use_large_page(size_t size, size_t alignment); 98 size_t _mi_os_large_page_size(void); 99 100 void* _mi_os_alloc_huge_os_pages(size_t pages, int numa_node, mi_msecs_t max_secs, size_t* pages_reserved, size_t* psize, mi_memid_t* memid); 101 102 // arena.c 103 mi_arena_id_t _mi_arena_id_none(void); 104 void _mi_arena_free(void* p, size_t size, size_t still_committed_size, mi_memid_t memid, mi_stats_t* stats); 105 void* _mi_arena_alloc(size_t size, bool commit, bool allow_large, mi_arena_id_t req_arena_id, mi_memid_t* memid, mi_os_tld_t* tld); 106 void* _mi_arena_alloc_aligned(size_t size, size_t alignment, size_t align_offset, bool commit, bool allow_large, mi_arena_id_t req_arena_id, mi_memid_t* memid, mi_os_tld_t* tld); 107 bool _mi_arena_memid_is_suitable(mi_memid_t memid, mi_arena_id_t request_arena_id); 108 bool _mi_arena_contains(const void* p); 109 void _mi_arena_collect(bool force_purge, mi_stats_t* stats); 110 void _mi_arena_unsafe_destroy_all(mi_stats_t* stats); 111 112 // "segment-map.c" 113 void _mi_segment_map_allocated_at(const mi_segment_t* segment); 114 void _mi_segment_map_freed_at(const mi_segment_t* segment); 115 116 // "segment.c" 117 extern mi_abandoned_pool_t _mi_abandoned_default; // global abandoned pool 118 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); 119 void _mi_segment_page_free(mi_page_t* page, bool force, mi_segments_tld_t* tld); 120 void _mi_segment_page_abandon(mi_page_t* page, mi_segments_tld_t* tld); 121 bool _mi_segment_try_reclaim_abandoned( mi_heap_t* heap, bool try_all, mi_segments_tld_t* tld); 122 void _mi_segment_thread_collect(mi_segments_tld_t* tld); 123 bool _mi_abandoned_pool_visit_blocks(mi_abandoned_pool_t* pool, uint8_t page_tag, bool visit_blocks, mi_block_visit_fun* visitor, void* arg); 124 125 126 #if MI_HUGE_PAGE_ABANDON 127 void _mi_segment_huge_page_free(mi_segment_t* segment, mi_page_t* page, mi_block_t* block); 128 #else 129 void _mi_segment_huge_page_reset(mi_segment_t* segment, mi_page_t* page, mi_block_t* block); 130 #endif 131 132 uint8_t* _mi_segment_page_start(const mi_segment_t* segment, const mi_page_t* page, size_t* page_size); // page start for any page 133 void _mi_abandoned_reclaim_all(mi_heap_t* heap, mi_segments_tld_t* tld); 134 void _mi_abandoned_await_readers(mi_abandoned_pool_t *pool); 135 void _mi_abandoned_collect(mi_heap_t* heap, bool force, mi_segments_tld_t* tld); 136 137 // "page.c" 138 void* _mi_malloc_generic(mi_heap_t* heap, size_t size, bool zero, size_t huge_alignment) mi_attr_noexcept mi_attr_malloc; 139 140 void _mi_page_retire(mi_page_t* page) mi_attr_noexcept; // free the page if there are no other pages with many free blocks 141 void _mi_page_unfull(mi_page_t* page); 142 void _mi_page_free(mi_page_t* page, mi_page_queue_t* pq, bool force); // free the page 143 void _mi_page_abandon(mi_page_t* page, mi_page_queue_t* pq); // abandon the page, to be picked up by another thread... 144 void _mi_heap_delayed_free_all(mi_heap_t* heap); 145 bool _mi_heap_delayed_free_partial(mi_heap_t* heap); 146 void _mi_heap_collect_retired(mi_heap_t* heap, bool force); 147 148 void _mi_page_use_delayed_free(mi_page_t* page, mi_delayed_t delay, bool override_never); 149 bool _mi_page_try_use_delayed_free(mi_page_t* page, mi_delayed_t delay, bool override_never); 150 size_t _mi_page_queue_append(mi_heap_t* heap, mi_page_queue_t* pq, mi_page_queue_t* append); 151 void _mi_deferred_free(mi_heap_t* heap, bool force); 152 153 void _mi_page_free_collect(mi_page_t* page,bool force); 154 void _mi_page_reclaim(mi_heap_t* heap, mi_page_t* page); // callback from segments 155 156 size_t _mi_bin_size(uint8_t bin); // for stats 157 uint8_t _mi_bin(size_t size); // for stats 158 159 // "heap.c" 160 void _mi_heap_init_ex(mi_heap_t* heap, mi_tld_t* tld, mi_arena_id_t arena_id, bool no_reclaim, uint8_t tag); 161 void _mi_heap_destroy_pages(mi_heap_t* heap); 162 void _mi_heap_collect_abandon(mi_heap_t* heap); 163 void _mi_heap_set_default_direct(mi_heap_t* heap); 164 bool _mi_heap_memid_is_suitable(mi_heap_t* heap, mi_memid_t memid); 165 void _mi_heap_unsafe_destroy_all(void); 166 void _mi_heap_area_init(mi_heap_area_t* area, mi_page_t* page); 167 bool _mi_heap_area_visit_blocks(const mi_heap_area_t* area, mi_page_t *page, mi_block_visit_fun* visitor, void* arg); 168 169 // "stats.c" 170 void _mi_stats_done(mi_stats_t* stats); 171 mi_msecs_t _mi_clock_now(void); 172 mi_msecs_t _mi_clock_end(mi_msecs_t start); 173 mi_msecs_t _mi_clock_start(void); 174 175 // "alloc.c" 176 void* _mi_page_malloc(mi_heap_t* heap, mi_page_t* page, size_t size, bool zero) mi_attr_noexcept; // called from `_mi_malloc_generic` 177 void* _mi_heap_malloc_zero(mi_heap_t* heap, size_t size, bool zero) mi_attr_noexcept; 178 void* _mi_heap_malloc_zero_ex(mi_heap_t* heap, size_t size, bool zero, size_t huge_alignment) mi_attr_noexcept; // called from `_mi_heap_malloc_aligned` 179 void* _mi_heap_realloc_zero(mi_heap_t* heap, void* p, size_t newsize, bool zero) mi_attr_noexcept; 180 mi_block_t* _mi_page_ptr_unalign(const mi_segment_t* segment, const mi_page_t* page, const void* p); 181 bool _mi_free_delayed_block(mi_block_t* block); 182 void _mi_free_generic(const mi_segment_t* segment, mi_page_t* page, bool is_local, void* p) mi_attr_noexcept; // for runtime integration 183 void _mi_padding_shrink(const mi_page_t* page, const mi_block_t* block, const size_t min_size); 184 185 // option.c, c primitives 186 char _mi_toupper(char c); 187 int _mi_strnicmp(const char* s, const char* t, size_t n); 188 void _mi_strlcpy(char* dest, const char* src, size_t dest_size); 189 void _mi_strlcat(char* dest, const char* src, size_t dest_size); 190 size_t _mi_strlen(const char* s); 191 size_t _mi_strnlen(const char* s, size_t max_len); 192 193 194 #if MI_DEBUG>1 195 bool _mi_page_is_valid(mi_page_t* page); 196 #endif 197 198 199 // ------------------------------------------------------ 200 // Branches 201 // ------------------------------------------------------ 202 203 #if defined(__GNUC__) || defined(__clang__) 204 #define mi_unlikely(x) (__builtin_expect(!!(x),false)) 205 #define mi_likely(x) (__builtin_expect(!!(x),true)) 206 #elif (defined(__cplusplus) && (__cplusplus >= 202002L)) || (defined(_MSVC_LANG) && _MSVC_LANG >= 202002L) 207 #define mi_unlikely(x) (x) [[unlikely]] 208 #define mi_likely(x) (x) [[likely]] 209 #else 210 #define mi_unlikely(x) (x) 211 #define mi_likely(x) (x) 212 #endif 213 214 #ifndef __has_builtin 215 #define __has_builtin(x) 0 216 #endif 217 218 219 /* ----------------------------------------------------------- 220 Error codes passed to `_mi_fatal_error` 221 All are recoverable but EFAULT is a serious error and aborts by default in secure mode. 222 For portability define undefined error codes using common Unix codes: 223 <https://www-numi.fnal.gov/offline_software/srt_public_context/WebDocs/Errors/unix_system_errors.html> 224 ----------------------------------------------------------- */ 225 #include <errno.h> 226 #ifndef EAGAIN // double free 227 #define EAGAIN (11) 228 #endif 229 #ifndef ENOMEM // out of memory 230 #define ENOMEM (12) 231 #endif 232 #ifndef EFAULT // corrupted free-list or meta-data 233 #define EFAULT (14) 234 #endif 235 #ifndef EINVAL // trying to free an invalid pointer 236 #define EINVAL (22) 237 #endif 238 #ifndef EOVERFLOW // count*size overflow 239 #define EOVERFLOW (75) 240 #endif 241 242 243 /* ----------------------------------------------------------- 244 Inlined definitions 245 ----------------------------------------------------------- */ 246 #define MI_UNUSED(x) (void)(x) 247 #if (MI_DEBUG>0) 248 #define MI_UNUSED_RELEASE(x) 249 #else 250 #define MI_UNUSED_RELEASE(x) MI_UNUSED(x) 251 #endif 252 253 #define MI_INIT4(x) x(),x(),x(),x() 254 #define MI_INIT8(x) MI_INIT4(x),MI_INIT4(x) 255 #define MI_INIT16(x) MI_INIT8(x),MI_INIT8(x) 256 #define MI_INIT32(x) MI_INIT16(x),MI_INIT16(x) 257 #define MI_INIT64(x) MI_INIT32(x),MI_INIT32(x) 258 #define MI_INIT128(x) MI_INIT64(x),MI_INIT64(x) 259 #define MI_INIT256(x) MI_INIT128(x),MI_INIT128(x) 260 261 262 #include <string.h> 263 // initialize a local variable to zero; use memset as compilers optimize constant sized memset's 264 #define _mi_memzero_var(x) memset(&x,0,sizeof(x)) 265 266 // Is `x` a power of two? (0 is considered a power of two) 267 static inline bool _mi_is_power_of_two(uintptr_t x) { 268 return ((x & (x - 1)) == 0); 269 } 270 271 // Is a pointer aligned? 272 static inline bool _mi_is_aligned(void* p, size_t alignment) { 273 mi_assert_internal(alignment != 0); 274 return (((uintptr_t)p % alignment) == 0); 275 } 276 277 // Align upwards 278 static inline uintptr_t _mi_align_up(uintptr_t sz, size_t alignment) { 279 mi_assert_internal(alignment != 0); 280 uintptr_t mask = alignment - 1; 281 if ((alignment & mask) == 0) { // power of two? 282 return ((sz + mask) & ~mask); 283 } 284 else { 285 return (((sz + mask)/alignment)*alignment); 286 } 287 } 288 289 // Align downwards 290 static inline uintptr_t _mi_align_down(uintptr_t sz, size_t alignment) { 291 mi_assert_internal(alignment != 0); 292 uintptr_t mask = alignment - 1; 293 if ((alignment & mask) == 0) { // power of two? 294 return (sz & ~mask); 295 } 296 else { 297 return ((sz / alignment) * alignment); 298 } 299 } 300 301 // Divide upwards: `s <= _mi_divide_up(s,d)*d < s+d`. 302 static inline uintptr_t _mi_divide_up(uintptr_t size, size_t divider) { 303 mi_assert_internal(divider != 0); 304 return (divider == 0 ? size : ((size + divider - 1) / divider)); 305 } 306 307 // Is memory zero initialized? 308 static inline bool mi_mem_is_zero(const void* p, size_t size) { 309 for (size_t i = 0; i < size; i++) { 310 if (((uint8_t*)p)[i] != 0) return false; 311 } 312 return true; 313 } 314 315 316 // Align a byte size to a size in _machine words_, 317 // i.e. byte size == `wsize*sizeof(void*)`. 318 static inline size_t _mi_wsize_from_size(size_t size) { 319 mi_assert_internal(size <= SIZE_MAX - sizeof(uintptr_t)); 320 return (size + sizeof(uintptr_t) - 1) / sizeof(uintptr_t); 321 } 322 323 // Overflow detecting multiply 324 #if __has_builtin(__builtin_umul_overflow) || (defined(__GNUC__) && (__GNUC__ >= 5)) 325 #include <limits.h> // UINT_MAX, ULONG_MAX 326 #if defined(_CLOCK_T) // for Illumos 327 #undef _CLOCK_T 328 #endif 329 static inline bool mi_mul_overflow(size_t count, size_t size, size_t* total) { 330 #if (SIZE_MAX == ULONG_MAX) 331 return __builtin_umull_overflow(count, size, (unsigned long *)total); 332 #elif (SIZE_MAX == UINT_MAX) 333 return __builtin_umul_overflow(count, size, (unsigned int *)total); 334 #else 335 return __builtin_umulll_overflow(count, size, (unsigned long long *)total); 336 #endif 337 } 338 #else /* __builtin_umul_overflow is unavailable */ 339 static inline bool mi_mul_overflow(size_t count, size_t size, size_t* total) { 340 #define MI_MUL_NO_OVERFLOW ((size_t)1 << (4*sizeof(size_t))) // sqrt(SIZE_MAX) 341 *total = count * size; 342 // note: gcc/clang optimize this to directly check the overflow flag 343 return ((size >= MI_MUL_NO_OVERFLOW || count >= MI_MUL_NO_OVERFLOW) && size > 0 && (SIZE_MAX / size) < count); 344 } 345 #endif 346 347 // Safe multiply `count*size` into `total`; return `true` on overflow. 348 static inline bool mi_count_size_overflow(size_t count, size_t size, size_t* total) { 349 if (count==1) { // quick check for the case where count is one (common for C++ allocators) 350 *total = size; 351 return false; 352 } 353 else if mi_unlikely(mi_mul_overflow(count, size, total)) { 354 #if MI_DEBUG > 0 355 _mi_error_message(EOVERFLOW, "allocation request is too large (%zu * %zu bytes)\n", count, size); 356 #endif 357 *total = SIZE_MAX; 358 return true; 359 } 360 else return false; 361 } 362 363 364 /*---------------------------------------------------------------------------------------- 365 Heap functions 366 ------------------------------------------------------------------------------------------- */ 367 368 extern const mi_heap_t _mi_heap_empty; // read-only empty heap, initial value of the thread local default heap 369 370 static inline bool mi_heap_is_backing(const mi_heap_t* heap) { 371 return (heap->tld->heap_backing == heap); 372 } 373 374 static inline bool mi_heap_is_initialized(mi_heap_t* heap) { 375 mi_assert_internal(heap != NULL); 376 return (heap != &_mi_heap_empty); 377 } 378 379 static inline uintptr_t _mi_ptr_cookie(const void* p) { 380 extern mi_heap_t _mi_heap_main; 381 mi_assert_internal(_mi_heap_main.cookie != 0); 382 return ((uintptr_t)p ^ _mi_heap_main.cookie); 383 } 384 385 /* ----------------------------------------------------------- 386 Pages 387 ----------------------------------------------------------- */ 388 389 static inline mi_page_t* _mi_heap_get_free_small_page(mi_heap_t* heap, size_t size) { 390 mi_assert_internal(size <= (MI_SMALL_SIZE_MAX + MI_PADDING_SIZE)); 391 const size_t idx = _mi_wsize_from_size(size); 392 mi_assert_internal(idx < MI_PAGES_DIRECT); 393 return heap->pages_free_direct[idx]; 394 } 395 396 // Segment that contains the pointer 397 // Large aligned blocks may be aligned at N*MI_SEGMENT_SIZE (inside a huge segment > MI_SEGMENT_SIZE), 398 // and we need align "down" to the segment info which is `MI_SEGMENT_SIZE` bytes before it; 399 // therefore we align one byte before `p`. 400 static inline mi_segment_t* _mi_ptr_segment(const void* p) { 401 mi_assert_internal(p != NULL); 402 return (mi_segment_t*)(((uintptr_t)p - 1) & ~MI_SEGMENT_MASK); 403 } 404 405 static inline mi_page_t* mi_slice_to_page(mi_slice_t* s) { 406 mi_assert_internal(s->slice_offset== 0 && s->slice_count > 0); 407 return (mi_page_t*)(s); 408 } 409 410 static inline mi_slice_t* mi_page_to_slice(mi_page_t* p) { 411 mi_assert_internal(p->slice_offset== 0 && p->slice_count > 0); 412 return (mi_slice_t*)(p); 413 } 414 415 // Segment belonging to a page 416 static inline mi_segment_t* _mi_page_segment(const mi_page_t* page) { 417 mi_segment_t* segment = _mi_ptr_segment(page); 418 mi_assert_internal(segment == NULL || ((mi_slice_t*)page >= segment->slices && (mi_slice_t*)page < segment->slices + segment->slice_entries)); 419 return segment; 420 } 421 422 static inline mi_slice_t* mi_slice_first(const mi_slice_t* slice) { 423 mi_slice_t* start = (mi_slice_t*)((uint8_t*)slice - slice->slice_offset); 424 mi_assert_internal(start >= _mi_ptr_segment(slice)->slices); 425 mi_assert_internal(start->slice_offset == 0); 426 mi_assert_internal(start + start->slice_count > slice); 427 return start; 428 } 429 430 // Get the page containing the pointer (performance critical as it is called in mi_free) 431 static inline mi_page_t* _mi_segment_page_of(const mi_segment_t* segment, const void* p) { 432 mi_assert_internal(p > (void*)segment); 433 ptrdiff_t diff = (uint8_t*)p - (uint8_t*)segment; 434 mi_assert_internal(diff > 0 && diff <= (ptrdiff_t)MI_SEGMENT_SIZE); 435 size_t idx = (size_t)diff >> MI_SEGMENT_SLICE_SHIFT; 436 mi_assert_internal(idx <= segment->slice_entries); 437 mi_slice_t* slice0 = (mi_slice_t*)&segment->slices[idx]; 438 mi_slice_t* slice = mi_slice_first(slice0); // adjust to the block that holds the page data 439 mi_assert_internal(slice->slice_offset == 0); 440 mi_assert_internal(slice >= segment->slices && slice < segment->slices + segment->slice_entries); 441 return mi_slice_to_page(slice); 442 } 443 444 // Quick page start for initialized pages 445 static inline uint8_t* _mi_page_start(const mi_segment_t* segment, const mi_page_t* page, size_t* page_size) { 446 return _mi_segment_page_start(segment, page, page_size); 447 } 448 449 // Get the page containing the pointer 450 static inline mi_page_t* _mi_ptr_page(void* p) { 451 return _mi_segment_page_of(_mi_ptr_segment(p), p); 452 } 453 454 // Get the block size of a page (special case for huge objects) 455 static inline size_t mi_page_block_size(const mi_page_t* page) { 456 const size_t bsize = page->xblock_size; 457 mi_assert_internal(bsize > 0); 458 if mi_likely(bsize < MI_HUGE_BLOCK_SIZE) { 459 return bsize; 460 } 461 else { 462 size_t psize; 463 _mi_segment_page_start(_mi_page_segment(page), page, &psize); 464 return psize; 465 } 466 } 467 468 static inline bool mi_page_is_huge(const mi_page_t* page) { 469 return (_mi_page_segment(page)->kind == MI_SEGMENT_HUGE); 470 } 471 472 // Get the usable block size of a page without fixed padding. 473 // This may still include internal padding due to alignment and rounding up size classes. 474 static inline size_t mi_page_usable_block_size(const mi_page_t* page) { 475 return mi_page_block_size(page) - MI_PADDING_SIZE; 476 } 477 478 // size of a segment 479 static inline size_t mi_segment_size(mi_segment_t* segment) { 480 return segment->segment_slices * MI_SEGMENT_SLICE_SIZE; 481 } 482 483 static inline uint8_t* mi_segment_end(mi_segment_t* segment) { 484 return (uint8_t*)segment + mi_segment_size(segment); 485 } 486 487 // Thread free access 488 static inline mi_block_t* mi_page_thread_free(const mi_page_t* page) { 489 return (mi_block_t*)(mi_atomic_load_relaxed(&((mi_page_t*)page)->xthread_free) & ~3); 490 } 491 492 static inline mi_delayed_t mi_page_thread_free_flag(const mi_page_t* page) { 493 return (mi_delayed_t)(mi_atomic_load_relaxed(&((mi_page_t*)page)->xthread_free) & 3); 494 } 495 496 // Heap access 497 static inline mi_heap_t* mi_page_heap(const mi_page_t* page) { 498 return (mi_heap_t*)(mi_atomic_load_relaxed(&((mi_page_t*)page)->xheap)); 499 } 500 501 static inline void mi_page_set_heap(mi_page_t* page, mi_heap_t* heap) { 502 mi_assert_internal(mi_page_thread_free_flag(page) != MI_DELAYED_FREEING); 503 mi_atomic_store_release(&page->xheap,(uintptr_t)heap); 504 } 505 506 // Thread free flag helpers 507 static inline mi_block_t* mi_tf_block(mi_thread_free_t tf) { 508 return (mi_block_t*)(tf & ~0x03); 509 } 510 static inline mi_delayed_t mi_tf_delayed(mi_thread_free_t tf) { 511 return (mi_delayed_t)(tf & 0x03); 512 } 513 static inline mi_thread_free_t mi_tf_make(mi_block_t* block, mi_delayed_t delayed) { 514 return (mi_thread_free_t)((uintptr_t)block | (uintptr_t)delayed); 515 } 516 static inline mi_thread_free_t mi_tf_set_delayed(mi_thread_free_t tf, mi_delayed_t delayed) { 517 return mi_tf_make(mi_tf_block(tf),delayed); 518 } 519 static inline mi_thread_free_t mi_tf_set_block(mi_thread_free_t tf, mi_block_t* block) { 520 return mi_tf_make(block, mi_tf_delayed(tf)); 521 } 522 523 // are all blocks in a page freed? 524 // note: needs up-to-date used count, (as the `xthread_free` list may not be empty). see `_mi_page_collect_free`. 525 static inline bool mi_page_all_free(const mi_page_t* page) { 526 mi_assert_internal(page != NULL); 527 return (page->used == 0); 528 } 529 530 // are there any available blocks? 531 static inline bool mi_page_has_any_available(const mi_page_t* page) { 532 mi_assert_internal(page != NULL && page->reserved > 0); 533 return (page->used < page->reserved || (mi_page_thread_free(page) != NULL)); 534 } 535 536 // are there immediately available blocks, i.e. blocks available on the free list. 537 static inline bool mi_page_immediate_available(const mi_page_t* page) { 538 mi_assert_internal(page != NULL); 539 return (page->free != NULL); 540 } 541 542 // is more than 7/8th of a page in use? 543 static inline bool mi_page_mostly_used(const mi_page_t* page) { 544 if (page==NULL) return true; 545 uint16_t frac = page->reserved / 8U; 546 return (page->reserved - page->used <= frac); 547 } 548 549 static inline mi_page_queue_t* mi_page_queue(const mi_heap_t* heap, size_t size) { 550 return &((mi_heap_t*)heap)->pages[_mi_bin(size)]; 551 } 552 553 554 555 //----------------------------------------------------------- 556 // Page flags 557 //----------------------------------------------------------- 558 static inline bool mi_page_is_in_full(const mi_page_t* page) { 559 return page->flags.x.in_full; 560 } 561 562 static inline void mi_page_set_in_full(mi_page_t* page, bool in_full) { 563 page->flags.x.in_full = in_full; 564 } 565 566 static inline bool mi_page_has_aligned(const mi_page_t* page) { 567 return page->flags.x.has_aligned; 568 } 569 570 static inline void mi_page_set_has_aligned(mi_page_t* page, bool has_aligned) { 571 page->flags.x.has_aligned = has_aligned; 572 } 573 574 575 /* ------------------------------------------------------------------- 576 Encoding/Decoding the free list next pointers 577 578 This is to protect against buffer overflow exploits where the 579 free list is mutated. Many hardened allocators xor the next pointer `p` 580 with a secret key `k1`, as `p^k1`. This prevents overwriting with known 581 values but might be still too weak: if the attacker can guess 582 the pointer `p` this can reveal `k1` (since `p^k1^p == k1`). 583 Moreover, if multiple blocks can be read as well, the attacker can 584 xor both as `(p1^k1) ^ (p2^k1) == p1^p2` which may reveal a lot 585 about the pointers (and subsequently `k1`). 586 587 Instead mimalloc uses an extra key `k2` and encodes as `((p^k2)<<<k1)+k1`. 588 Since these operations are not associative, the above approaches do not 589 work so well any more even if the `p` can be guesstimated. For example, 590 for the read case we can subtract two entries to discard the `+k1` term, 591 but that leads to `((p1^k2)<<<k1) - ((p2^k2)<<<k1)` at best. 592 We include the left-rotation since xor and addition are otherwise linear 593 in the lowest bit. Finally, both keys are unique per page which reduces 594 the re-use of keys by a large factor. 595 596 We also pass a separate `null` value to be used as `NULL` or otherwise 597 `(k2<<<k1)+k1` would appear (too) often as a sentinel value. 598 ------------------------------------------------------------------- */ 599 600 static inline bool mi_is_in_same_segment(const void* p, const void* q) { 601 return (_mi_ptr_segment(p) == _mi_ptr_segment(q)); 602 } 603 604 static inline bool mi_is_in_same_page(const void* p, const void* q) { 605 mi_segment_t* segment = _mi_ptr_segment(p); 606 if (_mi_ptr_segment(q) != segment) return false; 607 // assume q may be invalid // return (_mi_segment_page_of(segment, p) == _mi_segment_page_of(segment, q)); 608 mi_page_t* page = _mi_segment_page_of(segment, p); 609 size_t psize; 610 uint8_t* start = _mi_segment_page_start(segment, page, &psize); 611 return (start <= (uint8_t*)q && (uint8_t*)q < start + psize); 612 } 613 614 static inline uintptr_t mi_rotl(uintptr_t x, uintptr_t shift) { 615 shift %= MI_INTPTR_BITS; 616 return (shift==0 ? x : ((x << shift) | (x >> (MI_INTPTR_BITS - shift)))); 617 } 618 static inline uintptr_t mi_rotr(uintptr_t x, uintptr_t shift) { 619 shift %= MI_INTPTR_BITS; 620 return (shift==0 ? x : ((x >> shift) | (x << (MI_INTPTR_BITS - shift)))); 621 } 622 623 static inline void* mi_ptr_decode(const void* null, const mi_encoded_t x, const uintptr_t* keys) { 624 void* p = (void*)(mi_rotr(x - keys[0], keys[0]) ^ keys[1]); 625 return (p==null ? NULL : p); 626 } 627 628 static inline mi_encoded_t mi_ptr_encode(const void* null, const void* p, const uintptr_t* keys) { 629 uintptr_t x = (uintptr_t)(p==NULL ? null : p); 630 return mi_rotl(x ^ keys[1], keys[0]) + keys[0]; 631 } 632 633 static inline mi_block_t* mi_block_nextx( const void* null, const mi_block_t* block, const uintptr_t* keys ) { 634 mi_track_mem_defined(block,sizeof(mi_block_t)); 635 mi_block_t* next; 636 #ifdef MI_ENCODE_FREELIST 637 next = (mi_block_t*)mi_ptr_decode(null, mi_atomic_load_relaxed((_Atomic(mi_encoded_t)*)&block->next), keys); 638 #else 639 MI_UNUSED(keys); MI_UNUSED(null); 640 next = (mi_block_t*)mi_atomic_load_relaxed((_Atomic(mi_encoded_t)*)&block->next); 641 #endif 642 mi_track_mem_noaccess(block,sizeof(mi_block_t)); 643 return next; 644 } 645 646 static inline void mi_block_set_nextx(const void* null, mi_block_t* block, const mi_block_t* next, const uintptr_t* keys) { 647 mi_track_mem_undefined(block,sizeof(mi_block_t)); 648 #ifdef MI_ENCODE_FREELIST 649 mi_atomic_store_relaxed(&block->next, mi_ptr_encode(null, next, keys)); 650 #else 651 MI_UNUSED(keys); MI_UNUSED(null); 652 mi_atomic_store_relaxed(&block->next, (mi_encoded_t)next); 653 #endif 654 mi_track_mem_noaccess(block,sizeof(mi_block_t)); 655 } 656 657 static inline mi_block_t* mi_block_next(const mi_page_t* page, const mi_block_t* block) { 658 #ifdef MI_ENCODE_FREELIST 659 mi_block_t* next = mi_block_nextx(page,block,page->keys); 660 // check for free list corruption: is `next` at least in the same page? 661 // TODO: check if `next` is `page->block_size` aligned? 662 if mi_unlikely(next!=NULL && !mi_is_in_same_page(block, next)) { 663 _mi_error_message(EFAULT, "corrupted free list entry of size %zub at %p: value 0x%zx\n", mi_page_block_size(page), block, (uintptr_t)next); 664 next = NULL; 665 } 666 return next; 667 #else 668 MI_UNUSED(page); 669 return mi_block_nextx(page,block,NULL); 670 #endif 671 } 672 673 static inline void mi_block_set_next(const mi_page_t* page, mi_block_t* block, const mi_block_t* next) { 674 #ifdef MI_ENCODE_FREELIST 675 mi_block_set_nextx(page,block,next, page->keys); 676 #else 677 MI_UNUSED(page); 678 mi_block_set_nextx(page,block,next,NULL); 679 #endif 680 } 681 682 683 // ------------------------------------------------------------------- 684 // commit mask 685 // ------------------------------------------------------------------- 686 687 static inline void mi_commit_mask_create_empty(mi_commit_mask_t* cm) { 688 for (size_t i = 0; i < MI_COMMIT_MASK_FIELD_COUNT; i++) { 689 cm->mask[i] = 0; 690 } 691 } 692 693 static inline void mi_commit_mask_create_full(mi_commit_mask_t* cm) { 694 for (size_t i = 0; i < MI_COMMIT_MASK_FIELD_COUNT; i++) { 695 cm->mask[i] = ~((size_t)0); 696 } 697 } 698 699 static inline bool mi_commit_mask_is_empty(const mi_commit_mask_t* cm) { 700 for (size_t i = 0; i < MI_COMMIT_MASK_FIELD_COUNT; i++) { 701 if (cm->mask[i] != 0) return false; 702 } 703 return true; 704 } 705 706 static inline bool mi_commit_mask_is_full(const mi_commit_mask_t* cm) { 707 for (size_t i = 0; i < MI_COMMIT_MASK_FIELD_COUNT; i++) { 708 if (cm->mask[i] != ~((size_t)0)) return false; 709 } 710 return true; 711 } 712 713 // defined in `segment.c`: 714 size_t _mi_commit_mask_committed_size(const mi_commit_mask_t* cm, size_t total); 715 size_t _mi_commit_mask_next_run(const mi_commit_mask_t* cm, size_t* idx); 716 717 #define mi_commit_mask_foreach(cm,idx,count) \ 718 idx = 0; \ 719 while ((count = _mi_commit_mask_next_run(cm,&idx)) > 0) { 720 721 #define mi_commit_mask_foreach_end() \ 722 idx += count; \ 723 } 724 725 726 727 /* ----------------------------------------------------------- 728 memory id's 729 ----------------------------------------------------------- */ 730 731 static inline mi_memid_t _mi_memid_create(mi_memkind_t memkind) { 732 mi_memid_t memid; 733 _mi_memzero_var(memid); 734 memid.memkind = memkind; 735 return memid; 736 } 737 738 static inline mi_memid_t _mi_memid_none(void) { 739 return _mi_memid_create(MI_MEM_NONE); 740 } 741 742 static inline mi_memid_t _mi_memid_create_os(bool committed, bool is_zero, bool is_large) { 743 mi_memid_t memid = _mi_memid_create(MI_MEM_OS); 744 memid.initially_committed = committed; 745 memid.initially_zero = is_zero; 746 memid.is_pinned = is_large; 747 return memid; 748 } 749 750 751 // ------------------------------------------------------------------- 752 // Fast "random" shuffle 753 // ------------------------------------------------------------------- 754 755 static inline uintptr_t _mi_random_shuffle(uintptr_t x) { 756 if (x==0) { x = 17; } // ensure we don't get stuck in generating zeros 757 #if (MI_INTPTR_SIZE==8) 758 // by Sebastiano Vigna, see: <http://xoshiro.di.unimi.it/splitmix64.c> 759 x ^= x >> 30; 760 x *= 0xbf58476d1ce4e5b9UL; 761 x ^= x >> 27; 762 x *= 0x94d049bb133111ebUL; 763 x ^= x >> 31; 764 #elif (MI_INTPTR_SIZE==4) 765 // by Chris Wellons, see: <https://nullprogram.com/blog/2018/07/31/> 766 x ^= x >> 16; 767 x *= 0x7feb352dUL; 768 x ^= x >> 15; 769 x *= 0x846ca68bUL; 770 x ^= x >> 16; 771 #endif 772 return x; 773 } 774 775 // ------------------------------------------------------------------- 776 // Optimize numa node access for the common case (= one node) 777 // ------------------------------------------------------------------- 778 779 int _mi_os_numa_node_get(mi_os_tld_t* tld); 780 size_t _mi_os_numa_node_count_get(void); 781 782 extern _Atomic(size_t) _mi_numa_node_count; 783 static inline int _mi_os_numa_node(mi_os_tld_t* tld) { 784 if mi_likely(mi_atomic_load_relaxed(&_mi_numa_node_count) == 1) { return 0; } 785 else return _mi_os_numa_node_get(tld); 786 } 787 static inline size_t _mi_os_numa_node_count(void) { 788 const size_t count = mi_atomic_load_relaxed(&_mi_numa_node_count); 789 if mi_likely(count > 0) { return count; } 790 else return _mi_os_numa_node_count_get(); 791 } 792 793 794 795 // ----------------------------------------------------------------------- 796 // Count bits: trailing or leading zeros (with MI_INTPTR_BITS on all zero) 797 // ----------------------------------------------------------------------- 798 799 #if defined(__GNUC__) 800 801 #include <limits.h> // LONG_MAX 802 #define MI_HAVE_FAST_BITSCAN 803 static inline size_t mi_clz(uintptr_t x) { 804 if (x==0) return MI_INTPTR_BITS; 805 #if (INTPTR_MAX == LONG_MAX) 806 return __builtin_clzl(x); 807 #else 808 return __builtin_clzll(x); 809 #endif 810 } 811 static inline size_t mi_ctz(uintptr_t x) { 812 if (x==0) return MI_INTPTR_BITS; 813 #if (INTPTR_MAX == LONG_MAX) 814 return __builtin_ctzl(x); 815 #else 816 return __builtin_ctzll(x); 817 #endif 818 } 819 820 #elif defined(_MSC_VER) 821 822 #include <limits.h> // LONG_MAX 823 #include <intrin.h> // BitScanReverse64 824 #define MI_HAVE_FAST_BITSCAN 825 static inline size_t mi_clz(uintptr_t x) { 826 if (x==0) return MI_INTPTR_BITS; 827 unsigned long idx; 828 #if (INTPTR_MAX == LONG_MAX) 829 _BitScanReverse(&idx, x); 830 #else 831 _BitScanReverse64(&idx, x); 832 #endif 833 return ((MI_INTPTR_BITS - 1) - idx); 834 } 835 static inline size_t mi_ctz(uintptr_t x) { 836 if (x==0) return MI_INTPTR_BITS; 837 unsigned long idx; 838 #if (INTPTR_MAX == LONG_MAX) 839 _BitScanForward(&idx, x); 840 #else 841 _BitScanForward64(&idx, x); 842 #endif 843 return idx; 844 } 845 846 #else 847 static inline size_t mi_ctz32(uint32_t x) { 848 // de Bruijn multiplication, see <http://supertech.csail.mit.edu/papers/debruijn.pdf> 849 static const unsigned char debruijn[32] = { 850 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 851 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 852 }; 853 if (x==0) return 32; 854 return debruijn[((x & -(int32_t)x) * 0x077CB531UL) >> 27]; 855 } 856 static inline size_t mi_clz32(uint32_t x) { 857 // de Bruijn multiplication, see <http://supertech.csail.mit.edu/papers/debruijn.pdf> 858 static const uint8_t debruijn[32] = { 859 31, 22, 30, 21, 18, 10, 29, 2, 20, 17, 15, 13, 9, 6, 28, 1, 860 23, 19, 11, 3, 16, 14, 7, 24, 12, 4, 8, 25, 5, 26, 27, 0 861 }; 862 if (x==0) return 32; 863 x |= x >> 1; 864 x |= x >> 2; 865 x |= x >> 4; 866 x |= x >> 8; 867 x |= x >> 16; 868 return debruijn[(uint32_t)(x * 0x07C4ACDDUL) >> 27]; 869 } 870 871 static inline size_t mi_clz(uintptr_t x) { 872 if (x==0) return MI_INTPTR_BITS; 873 #if (MI_INTPTR_BITS <= 32) 874 return mi_clz32((uint32_t)x); 875 #else 876 size_t count = mi_clz32((uint32_t)(x >> 32)); 877 if (count < 32) return count; 878 return (32 + mi_clz32((uint32_t)x)); 879 #endif 880 } 881 static inline size_t mi_ctz(uintptr_t x) { 882 if (x==0) return MI_INTPTR_BITS; 883 #if (MI_INTPTR_BITS <= 32) 884 return mi_ctz32((uint32_t)x); 885 #else 886 size_t count = mi_ctz32((uint32_t)x); 887 if (count < 32) return count; 888 return (32 + mi_ctz32((uint32_t)(x>>32))); 889 #endif 890 } 891 892 #endif 893 894 // "bit scan reverse": Return index of the highest bit (or MI_INTPTR_BITS if `x` is zero) 895 static inline size_t mi_bsr(uintptr_t x) { 896 return (x==0 ? MI_INTPTR_BITS : MI_INTPTR_BITS - 1 - mi_clz(x)); 897 } 898 899 900 // --------------------------------------------------------------------------------- 901 // Provide our own `_mi_memcpy` for potential performance optimizations. 902 // 903 // For now, only on Windows with msvc/clang-cl we optimize to `rep movsb` if 904 // we happen to run on x86/x64 cpu's that have "fast short rep movsb" (FSRM) support 905 // (AMD Zen3+ (~2020) or Intel Ice Lake+ (~2017). See also issue #201 and pr #253. 906 // --------------------------------------------------------------------------------- 907 908 #if !MI_TRACK_ENABLED && defined(_WIN32) && (defined(_M_IX86) || defined(_M_X64)) 909 #include <intrin.h> 910 extern bool _mi_cpu_has_fsrm; 911 static inline void _mi_memcpy(void* dst, const void* src, size_t n) { 912 if (_mi_cpu_has_fsrm) { 913 __movsb((unsigned char*)dst, (const unsigned char*)src, n); 914 } 915 else { 916 memcpy(dst, src, n); 917 } 918 } 919 static inline void _mi_memzero(void* dst, size_t n) { 920 if (_mi_cpu_has_fsrm) { 921 __stosb((unsigned char*)dst, 0, n); 922 } 923 else { 924 memset(dst, 0, n); 925 } 926 } 927 #else 928 static inline void _mi_memcpy(void* dst, const void* src, size_t n) { 929 memcpy(dst, src, n); 930 } 931 static inline void _mi_memzero(void* dst, size_t n) { 932 memset(dst, 0, n); 933 } 934 #endif 935 936 // ------------------------------------------------------------------------------- 937 // The `_mi_memcpy_aligned` can be used if the pointers are machine-word aligned 938 // This is used for example in `mi_realloc`. 939 // ------------------------------------------------------------------------------- 940 941 #if (defined(__GNUC__) && (__GNUC__ >= 4)) || defined(__clang__) 942 // On GCC/CLang we provide a hint that the pointers are word aligned. 943 static inline void _mi_memcpy_aligned(void* dst, const void* src, size_t n) { 944 mi_assert_internal(((uintptr_t)dst % MI_INTPTR_SIZE == 0) && ((uintptr_t)src % MI_INTPTR_SIZE == 0)); 945 void* adst = __builtin_assume_aligned(dst, MI_INTPTR_SIZE); 946 const void* asrc = __builtin_assume_aligned(src, MI_INTPTR_SIZE); 947 _mi_memcpy(adst, asrc, n); 948 } 949 950 static inline void _mi_memzero_aligned(void* dst, size_t n) { 951 mi_assert_internal((uintptr_t)dst % MI_INTPTR_SIZE == 0); 952 void* adst = __builtin_assume_aligned(dst, MI_INTPTR_SIZE); 953 _mi_memzero(adst, n); 954 } 955 #else 956 // Default fallback on `_mi_memcpy` 957 static inline void _mi_memcpy_aligned(void* dst, const void* src, size_t n) { 958 mi_assert_internal(((uintptr_t)dst % MI_INTPTR_SIZE == 0) && ((uintptr_t)src % MI_INTPTR_SIZE == 0)); 959 _mi_memcpy(dst, src, n); 960 } 961 962 static inline void _mi_memzero_aligned(void* dst, size_t n) { 963 mi_assert_internal((uintptr_t)dst % MI_INTPTR_SIZE == 0); 964 _mi_memzero(dst, n); 965 } 966 #endif 967 968 969 #endif
