/* ---------------------------------------------------------------------------- Copyright (c) 2018-2023, Microsoft Research, Daan Leijen This is free software; you can redistribute it and/or modify it under the terms of the MIT license. A copy of the license can be found in the file "LICENSE" at the root of this distribution. -----------------------------------------------------------------------------*/ #pragma once #ifndef MIMALLOC_TYPES_H #define MIMALLOC_TYPES_H // -------------------------------------------------------------------------- // This file contains the main type definitions for mimalloc: // mi_heap_t : all data for a thread-local heap, contains // lists of all managed heap pages. // mi_segment_t : a larger chunk of memory (32GiB) from where pages // are allocated. // mi_page_t : a mimalloc page (usually 64KiB or 512KiB) from // where objects are allocated. // -------------------------------------------------------------------------- #include <stddef.h> // ptrdiff_t #include <stdint.h> // uintptr_t, uint16_t, etc #include "atomic.h" // _Atomic #ifdef _MSC_VER #pragma warning(disable:4214) // bitfield is not int #endif // Minimal alignment necessary. On most platforms 16 bytes are needed // due to SSE registers for example. This must be at least `sizeof(void*)` #ifndef MI_MAX_ALIGN_SIZE #define MI_MAX_ALIGN_SIZE … #endif #define MI_CACHE_LINE … #if defined(_MSC_VER) #pragma warning(disable:4127) // suppress constant conditional warning (due to MI_SECURE paths) #pragma warning(disable:26812) // unscoped enum warning #define mi_decl_noinline … #define mi_decl_thread … #define mi_decl_cache_align … #elif (defined(__GNUC__) && (__GNUC__ >= 3)) || defined(__clang__) // includes clang and icc #define mi_decl_noinline … #define mi_decl_thread … #define mi_decl_cache_align … #else #define mi_decl_noinline #define mi_decl_thread … #define mi_decl_cache_align #endif // ------------------------------------------------------ // Variants // ------------------------------------------------------ // Define NDEBUG in the release version to disable assertions. // #define NDEBUG // Define MI_TRACK_<tool> to enable tracking support // #define MI_TRACK_VALGRIND 1 // #define MI_TRACK_ASAN 1 // #define MI_TRACK_ETW 1 // Define MI_STAT as 1 to maintain statistics; set it to 2 to have detailed statistics (but costs some performance). // #define MI_STAT 1 // Define MI_SECURE to enable security mitigations // #define MI_SECURE 1 // guard page around metadata // #define MI_SECURE 2 // guard page around each mimalloc page // #define MI_SECURE 3 // encode free lists (detect corrupted free list (buffer overflow), and invalid pointer free) // #define MI_SECURE 4 // checks for double free. (may be more expensive) #if !defined(MI_SECURE) #define MI_SECURE … #endif // Define MI_DEBUG for debug mode // #define MI_DEBUG 1 // basic assertion checks and statistics, check double free, corrupted free list, and invalid pointer free. // #define MI_DEBUG 2 // + internal assertion checks // #define MI_DEBUG 3 // + extensive internal invariant checking (cmake -DMI_DEBUG_FULL=ON) #if !defined(MI_DEBUG) #if !defined(NDEBUG) || defined(_DEBUG) #define MI_DEBUG … #else #define MI_DEBUG … #endif #endif // Reserve extra padding at the end of each block to be more resilient against heap block overflows. // The padding can detect buffer overflow on free. #if !defined(MI_PADDING) && (MI_SECURE>=3 || MI_DEBUG>=1 || (MI_TRACK_VALGRIND || MI_TRACK_ASAN || MI_TRACK_ETW)) #define MI_PADDING … #endif // Check padding bytes; allows byte-precise buffer overflow detection #if !defined(MI_PADDING_CHECK) && MI_PADDING && (MI_SECURE>=3 || MI_DEBUG>=1) #define MI_PADDING_CHECK … #endif // Encoded free lists allow detection of corrupted free lists // and can detect buffer overflows, modify after free, and double `free`s. #if (MI_SECURE>=3 || MI_DEBUG>=1) #define MI_ENCODE_FREELIST … #endif // We used to abandon huge pages but to eagerly deallocate if freed from another thread, // but that makes it not possible to visit them during a heap walk or include them in a // `mi_heap_destroy`. We therefore instead reset/decommit the huge blocks if freed from // another thread so most memory is available until it gets properly freed by the owning thread. // #define MI_HUGE_PAGE_ABANDON 1 // ------------------------------------------------------ // Platform specific values // ------------------------------------------------------ // ------------------------------------------------------ // Size of a pointer. // We assume that `sizeof(void*)==sizeof(intptr_t)` // and it holds for all platforms we know of. // // However, the C standard only requires that: // p == (void*)((intptr_t)p)) // but we also need: // i == (intptr_t)((void*)i) // or otherwise one might define an intptr_t type that is larger than a pointer... // ------------------------------------------------------ #if INTPTR_MAX > INT64_MAX #define MI_INTPTR_SHIFT … #elif INTPTR_MAX == INT64_MAX #define MI_INTPTR_SHIFT … #elif INTPTR_MAX == INT32_MAX #define MI_INTPTR_SHIFT … #else #error platform pointers must be 32, 64, or 128 bits #endif #if SIZE_MAX == UINT64_MAX #define MI_SIZE_SHIFT … mi_ssize_t; #elif SIZE_MAX == UINT32_MAX #define MI_SIZE_SHIFT … typedef int32_t mi_ssize_t; #else #error platform objects must be 32 or 64 bits #endif #if (SIZE_MAX/2) > LONG_MAX #define MI_ZU … #define MI_ZI … #else #define MI_ZU(x) … #define MI_ZI(x) … #endif #define MI_INTPTR_SIZE … #define MI_INTPTR_BITS … #define MI_SIZE_SIZE … #define MI_SIZE_BITS … #define MI_KiB … #define MI_MiB … #define MI_GiB … // ------------------------------------------------------ // Main internal data-structures // ------------------------------------------------------ // Main tuning parameters for segment and page sizes // Sizes for 64-bit (usually divide by two for 32-bit) #define MI_SEGMENT_SLICE_SHIFT … #if MI_INTPTR_SIZE > 4 #define MI_SEGMENT_SHIFT … #else #define MI_SEGMENT_SHIFT … #endif #define MI_SMALL_PAGE_SHIFT … #define MI_MEDIUM_PAGE_SHIFT … // Derived constants #define MI_SEGMENT_SIZE … #define MI_SEGMENT_ALIGN … #define MI_SEGMENT_MASK … #define MI_SEGMENT_SLICE_SIZE … #define MI_SLICES_PER_SEGMENT … #define MI_SMALL_PAGE_SIZE … #define MI_MEDIUM_PAGE_SIZE … #define MI_SMALL_OBJ_SIZE_MAX … #define MI_MEDIUM_OBJ_SIZE_MAX … #define MI_MEDIUM_OBJ_WSIZE_MAX … #define MI_LARGE_OBJ_SIZE_MAX … #define MI_LARGE_OBJ_WSIZE_MAX … // Maximum number of size classes. (spaced exponentially in 12.5% increments) #define MI_BIN_HUGE … #if (MI_MEDIUM_OBJ_WSIZE_MAX >= 655360) #error "mimalloc internal: define more bins" #endif // Maximum slice offset (15) #define MI_MAX_SLICE_OFFSET … // Used as a special value to encode block sizes in 32 bits. #define MI_HUGE_BLOCK_SIZE … // blocks up to this size are always allocated aligned #define MI_MAX_ALIGN_GUARANTEE … // Alignments over MI_ALIGNMENT_MAX are allocated in dedicated huge page segments #define MI_ALIGNMENT_MAX … // ------------------------------------------------------ // Mimalloc pages contain allocated blocks // ------------------------------------------------------ // The free lists use encoded next fields // (Only actually encodes when MI_ENCODED_FREELIST is defined.) mi_encoded_t; // thread id's mi_threadid_t; // free lists contain blocks mi_block_t; // The delayed flags are used for efficient multi-threaded free-ing mi_delayed_t; // The `in_full` and `has_aligned` page flags are put in a union to efficiently // test if both are false (`full_aligned == 0`) in the `mi_free` routine. #if !MI_TSAN mi_page_flags_t; #else // under thread sanitizer, use a byte for each flag to suppress warning, issue #130 typedef union mi_page_flags_s { uint16_t full_aligned; struct { uint8_t in_full; uint8_t has_aligned; } x; } mi_page_flags_t; #endif // Thread free list. // We use the bottom 2 bits of the pointer for mi_delayed_t flags mi_thread_free_t; // A page contains blocks of one specific size (`block_size`). // Each page has three list of free blocks: // `free` for blocks that can be allocated, // `local_free` for freed blocks that are not yet available to `mi_malloc` // `thread_free` for freed blocks by other threads // The `local_free` and `thread_free` lists are migrated to the `free` list // when it is exhausted. The separate `local_free` list is necessary to // implement a monotonic heartbeat. The `thread_free` list is needed for // avoiding atomic operations in the common case. // // // `used - |thread_free|` == actual blocks that are in use (alive) // `used - |thread_free| + |free| + |local_free| == capacity` // // We don't count `freed` (as |free|) but use `used` to reduce // the number of memory accesses in the `mi_page_all_free` function(s). // // Notes: // - Access is optimized for `mi_free` and `mi_page_alloc` (in `alloc.c`) // - Using `uint16_t` does not seem to slow things down // - The size is 8 words on 64-bit which helps the page index calculations // (and 10 words on 32-bit, and encoded free lists add 2 words. Sizes 10 // and 12 are still good for address calculation) // - To limit the structure size, the `xblock_size` is 32-bits only; for // blocks > MI_HUGE_BLOCK_SIZE the size is determined from the segment page size // - `thread_free` uses the bottom bits as a delayed-free flags to optimize // concurrent frees where only the first concurrent free adds to the owning // heap `thread_delayed_free` list (see `alloc.c:mi_free_block_mt`). // The invariant is that no-delayed-free is only set if there is // at least one block that will be added, or as already been added, to // the owning heap `thread_delayed_free` list. This guarantees that pages // will be freed correctly even if only other threads free blocks. mi_page_t; // ------------------------------------------------------ // Mimalloc segments contain mimalloc pages // ------------------------------------------------------ mi_page_kind_t; mi_segment_kind_t; // ------------------------------------------------------ // A segment holds a commit mask where a bit is set if // the corresponding MI_COMMIT_SIZE area is committed. // The MI_COMMIT_SIZE must be a multiple of the slice // size. If it is equal we have the most fine grained // decommit (but setting it higher can be more efficient). // The MI_MINIMAL_COMMIT_SIZE is the minimal amount that will // be committed in one go which can be set higher than // MI_COMMIT_SIZE for efficiency (while the decommit mask // is still tracked in fine-grained MI_COMMIT_SIZE chunks) // ------------------------------------------------------ #define MI_MINIMAL_COMMIT_SIZE … #define MI_COMMIT_SIZE … #define MI_COMMIT_MASK_BITS … #define MI_COMMIT_MASK_FIELD_BITS … #define MI_COMMIT_MASK_FIELD_COUNT … #if (MI_COMMIT_MASK_BITS != (MI_COMMIT_MASK_FIELD_COUNT * MI_COMMIT_MASK_FIELD_BITS)) #error "the segment size must be exactly divisible by the (commit size * size_t bits)" #endif mi_commit_mask_t; mi_slice_t; mi_msecs_t; // Memory can reside in arena's, direct OS allocated, or statically allocated. The memid keeps track of this. mi_memkind_t; static inline bool mi_memkind_is_os(mi_memkind_t memkind) { … } mi_memid_os_info_t; mi_memid_arena_info_t; mi_memid_t; // Segments are large allocated memory blocks (8mb on 64 bit) from // the OS. Inside segments we allocated fixed size _pages_ that // contain blocks. mi_segment_t; mi_tagged_segment_t; // Segments unowned by any thread are put in a shared pool mi_abandoned_pool_t; // ------------------------------------------------------ // Heaps // Provide first-class heaps to allocate from. // A heap just owns a set of pages for allocation and // can only be allocate/reallocate from the thread that created it. // Freeing blocks can be done from any thread though. // Per thread, the segments are shared among its heaps. // Per thread, there is always a default heap that is // used for allocation; it is initialized to statically // point to an empty heap to avoid initialization checks // in the fast path. // ------------------------------------------------------ // Thread local data mi_tld_t; // Pages of a certain block size are held in a queue. mi_page_queue_t; #define MI_BIN_FULL … // Random context mi_random_ctx_t; // In debug mode there is a padding structure at the end of the blocks to check for buffer overflows #if (MI_PADDING) typedef struct mi_padding_s { uint32_t canary; // encoded block value to check validity of the padding (in case of overflow) uint32_t delta; // padding bytes before the block. (mi_usable_size(p) - delta == exact allocated bytes) } mi_padding_t; #define MI_PADDING_SIZE … #define MI_PADDING_WSIZE … #else #define MI_PADDING_SIZE … #define MI_PADDING_WSIZE … #endif #define MI_PAGES_DIRECT … // A heap owns a set of pages. struct mi_heap_s { … }; // ------------------------------------------------------ // Debug // ------------------------------------------------------ #if !defined(MI_DEBUG_UNINIT) #define MI_DEBUG_UNINIT … #endif #if !defined(MI_DEBUG_FREED) #define MI_DEBUG_FREED … #endif #if !defined(MI_DEBUG_PADDING) #define MI_DEBUG_PADDING … #endif #if (MI_DEBUG) // use our own assertion to print without memory allocation void _mi_assert_fail(const char* assertion, const char* fname, unsigned int line, const char* func ); #define mi_assert … #else #define mi_assert(x) … #endif #if (MI_DEBUG>1) #define mi_assert_internal … #else #define mi_assert_internal(x) … #endif #if (MI_DEBUG>2) #define mi_assert_expensive … #else #define mi_assert_expensive(x) … #endif // ------------------------------------------------------ // Statistics // ------------------------------------------------------ #ifndef MI_STAT #if (MI_DEBUG>0) #define MI_STAT … #else #define MI_STAT … #endif #endif mi_stat_count_t; mi_stat_counter_t; mi_stats_t; void _mi_stat_increase(mi_stat_count_t* stat, size_t amount); void _mi_stat_decrease(mi_stat_count_t* stat, size_t amount); void _mi_stat_counter_increase(mi_stat_counter_t* stat, size_t amount); #if (MI_STAT) #define mi_stat_increase … #define mi_stat_decrease … #define mi_stat_counter_increase … #else #define mi_stat_increase(stat,amount) … #define mi_stat_decrease(stat,amount) … #define mi_stat_counter_increase(stat,amount) … #endif #define mi_heap_stat_counter_increase(heap,stat,amount) … #define mi_heap_stat_increase(heap,stat,amount) … #define mi_heap_stat_decrease(heap,stat,amount) … // ------------------------------------------------------ // Thread Local data // ------------------------------------------------------ // A "span" is is an available range of slices. The span queues keep // track of slice spans of at most the given `slice_count` (but more than the previous size class). mi_span_queue_t; #define MI_SEGMENT_BIN_MAX … // OS thread local data mi_os_tld_t; // Segments thread local data mi_segments_tld_t; // Thread local data struct mi_tld_s { … }; #endif
Codebase Browser
cpython