| 1 |
/* ---------------------------------------------------------------------------- |
| 2 |
Copyright (c) 2019-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 |
|
| 8 |
/* ----------------------------------------------------------- |
| 9 |
The following functions are to reliably find the segment or |
| 10 |
block that encompasses any pointer p (or NULL if it is not |
| 11 |
in any of our segments). |
| 12 |
We maintain a bitmap of all memory with 1 bit per MI_SEGMENT_SIZE (64MiB) |
| 13 |
set to 1 if it contains the segment meta data. |
| 14 |
----------------------------------------------------------- */ |
| 15 |
#include "mimalloc.h" |
| 16 |
#include "mimalloc/internal.h" |
| 17 |
#include "mimalloc/atomic.h" |
| 18 |
|
| 19 |
#if (MI_INTPTR_SIZE==8) |
| 20 |
#define MI_MAX_ADDRESS ((size_t)40 << 40) // 40TB (to include huge page areas) |
| 21 |
#else |
| 22 |
#define MI_MAX_ADDRESS ((size_t)2 << 30) // 2Gb |
| 23 |
#endif |
| 24 |
|
| 25 |
#define MI_SEGMENT_MAP_BITS (MI_MAX_ADDRESS / MI_SEGMENT_SIZE) |
| 26 |
#define MI_SEGMENT_MAP_SIZE (MI_SEGMENT_MAP_BITS / 8) |
| 27 |
#define MI_SEGMENT_MAP_WSIZE (MI_SEGMENT_MAP_SIZE / MI_INTPTR_SIZE) |
| 28 |
|
| 29 |
static _Atomic(uintptr_t) mi_segment_map[MI_SEGMENT_MAP_WSIZE + 1]; // 2KiB per TB with 64MiB segments |
| 30 |
|
| 31 |
static size_t mi_segment_map_index_of(const mi_segment_t* segment, size_t* bitidx) { |
| 32 |
mi_assert_internal(_mi_ptr_segment(segment + 1) == segment); // is it aligned on MI_SEGMENT_SIZE? |
| 33 |
if ((uintptr_t)segment >= MI_MAX_ADDRESS) { |
| 34 |
*bitidx = 0; |
| 35 |
return MI_SEGMENT_MAP_WSIZE; |
| 36 |
} |
| 37 |
else { |
| 38 |
const uintptr_t segindex = ((uintptr_t)segment) / MI_SEGMENT_SIZE; |
| 39 |
*bitidx = segindex % MI_INTPTR_BITS; |
| 40 |
const size_t mapindex = segindex / MI_INTPTR_BITS; |
| 41 |
mi_assert_internal(mapindex < MI_SEGMENT_MAP_WSIZE); |
| 42 |
return mapindex; |
| 43 |
} |
| 44 |
} |
| 45 |
|
| 46 |
void _mi_segment_map_allocated_at(const mi_segment_t* segment) { |
| 47 |
size_t bitidx; |
| 48 |
size_t index = mi_segment_map_index_of(segment, &bitidx); |
| 49 |
mi_assert_internal(index <= MI_SEGMENT_MAP_WSIZE); |
| 50 |
if (index==MI_SEGMENT_MAP_WSIZE) return; |
| 51 |
uintptr_t mask = mi_atomic_load_relaxed(&mi_segment_map[index]); |
| 52 |
uintptr_t newmask; |
| 53 |
do { |
| 54 |
newmask = (mask | ((uintptr_t)1 << bitidx)); |
| 55 |
} while (!mi_atomic_cas_weak_release(&mi_segment_map[index], &mask, newmask)); |
| 56 |
} |
| 57 |
|
| 58 |
void _mi_segment_map_freed_at(const mi_segment_t* segment) { |
| 59 |
size_t bitidx; |
| 60 |
size_t index = mi_segment_map_index_of(segment, &bitidx); |
| 61 |
mi_assert_internal(index <= MI_SEGMENT_MAP_WSIZE); |
| 62 |
if (index == MI_SEGMENT_MAP_WSIZE) return; |
| 63 |
uintptr_t mask = mi_atomic_load_relaxed(&mi_segment_map[index]); |
| 64 |
uintptr_t newmask; |
| 65 |
do { |
| 66 |
newmask = (mask & ~((uintptr_t)1 << bitidx)); |
| 67 |
} while (!mi_atomic_cas_weak_release(&mi_segment_map[index], &mask, newmask)); |
| 68 |
} |
| 69 |
|
| 70 |
// Determine the segment belonging to a pointer or NULL if it is not in a valid segment. |
| 71 |
static mi_segment_t* _mi_segment_of(const void* p) { |
| 72 |
if (p == NULL) return NULL; |
| 73 |
mi_segment_t* segment = _mi_ptr_segment(p); |
| 74 |
mi_assert_internal(segment != NULL); |
| 75 |
size_t bitidx; |
| 76 |
size_t index = mi_segment_map_index_of(segment, &bitidx); |
| 77 |
// fast path: for any pointer to valid small/medium/large object or first MI_SEGMENT_SIZE in huge |
| 78 |
const uintptr_t mask = mi_atomic_load_relaxed(&mi_segment_map[index]); |
| 79 |
if mi_likely((mask & ((uintptr_t)1 << bitidx)) != 0) { |
| 80 |
return segment; // yes, allocated by us |
| 81 |
} |
| 82 |
if (index==MI_SEGMENT_MAP_WSIZE) return NULL; |
| 83 |
|
| 84 |
// TODO: maintain max/min allocated range for efficiency for more efficient rejection of invalid pointers? |
| 85 |
|
| 86 |
// search downwards for the first segment in case it is an interior pointer |
| 87 |
// could be slow but searches in MI_INTPTR_SIZE * MI_SEGMENT_SIZE (512MiB) steps through |
| 88 |
// valid huge objects |
| 89 |
// note: we could maintain a lowest index to speed up the path for invalid pointers? |
| 90 |
size_t lobitidx; |
| 91 |
size_t loindex; |
| 92 |
uintptr_t lobits = mask & (((uintptr_t)1 << bitidx) - 1); |
| 93 |
if (lobits != 0) { |
| 94 |
loindex = index; |
| 95 |
lobitidx = mi_bsr(lobits); // lobits != 0 |
| 96 |
} |
| 97 |
else if (index == 0) { |
| 98 |
return NULL; |
| 99 |
} |
| 100 |
else { |
| 101 |
mi_assert_internal(index > 0); |
| 102 |
uintptr_t lomask = mask; |
| 103 |
loindex = index; |
| 104 |
do { |
| 105 |
loindex--; |
| 106 |
lomask = mi_atomic_load_relaxed(&mi_segment_map[loindex]); |
| 107 |
} while (lomask != 0 && loindex > 0); |
| 108 |
if (lomask == 0) return NULL; |
| 109 |
lobitidx = mi_bsr(lomask); // lomask != 0 |
| 110 |
} |
| 111 |
mi_assert_internal(loindex < MI_SEGMENT_MAP_WSIZE); |
| 112 |
// take difference as the addresses could be larger than the MAX_ADDRESS space. |
| 113 |
size_t diff = (((index - loindex) * (8*MI_INTPTR_SIZE)) + bitidx - lobitidx) * MI_SEGMENT_SIZE; |
| 114 |
segment = (mi_segment_t*)((uint8_t*)segment - diff); |
| 115 |
|
| 116 |
if (segment == NULL) return NULL; |
| 117 |
mi_assert_internal((void*)segment < p); |
| 118 |
bool cookie_ok = (_mi_ptr_cookie(segment) == segment->cookie); |
| 119 |
mi_assert_internal(cookie_ok); |
| 120 |
if mi_unlikely(!cookie_ok) return NULL; |
| 121 |
if (((uint8_t*)segment + mi_segment_size(segment)) <= (uint8_t*)p) return NULL; // outside the range |
| 122 |
mi_assert_internal(p >= (void*)segment && (uint8_t*)p < (uint8_t*)segment + mi_segment_size(segment)); |
| 123 |
return segment; |
| 124 |
} |
| 125 |
|
| 126 |
// Is this a valid pointer in our heap? |
| 127 |
static bool mi_is_valid_pointer(const void* p) { |
| 128 |
return ((_mi_segment_of(p) != NULL) || (_mi_arena_contains(p))); |
| 129 |
} |
| 130 |
|
| 131 |
mi_decl_nodiscard mi_decl_export bool mi_is_in_heap_region(const void* p) mi_attr_noexcept { |
| 132 |
return mi_is_valid_pointer(p); |
| 133 |
} |
| 134 |
|
| 135 |
/* |
| 136 |
// Return the full segment range belonging to a pointer |
| 137 |
static void* mi_segment_range_of(const void* p, size_t* size) { |
| 138 |
mi_segment_t* segment = _mi_segment_of(p); |
| 139 |
if (segment == NULL) { |
| 140 |
if (size != NULL) *size = 0; |
| 141 |
return NULL; |
| 142 |
} |
| 143 |
else { |
| 144 |
if (size != NULL) *size = segment->segment_size; |
| 145 |
return segment; |
| 146 |
} |
| 147 |
mi_assert_expensive(page == NULL || mi_segment_is_valid(_mi_page_segment(page),tld)); |
| 148 |
mi_assert_internal(page == NULL || (mi_segment_page_size(_mi_page_segment(page)) - (MI_SECURE == 0 ? 0 : _mi_os_page_size())) >= block_size); |
| 149 |
mi_reset_delayed(tld); |
| 150 |
mi_assert_internal(page == NULL || mi_page_not_in_queue(page, tld)); |
| 151 |
return page; |
| 152 |
} |
| 153 |
*/ |