1 | /* ---------------------------------------------------------------------------- |
2 | Copyright (c) 2018, 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_TYPES_H |
9 | #define MIMALLOC_TYPES_H |
10 | |
11 | #include <stddef.h> // ptrdiff_t |
12 | #include <stdint.h> // uintptr_t, uint16_t, etc |
13 | #include <mimalloc-atomic.h> // _Atomic |
14 | |
15 | // ------------------------------------------------------ |
16 | // Variants |
17 | // ------------------------------------------------------ |
18 | |
19 | // Define NDEBUG in the release version to disable assertions. |
20 | // #define NDEBUG |
21 | |
22 | // Define MI_STAT as 1 to maintain statistics; set it to 2 to have detailed statistics (but costs some performance). |
23 | // #define MI_STAT 1 |
24 | |
25 | // Define MI_SECURE to enable security mitigations |
26 | // #define MI_SECURE 1 // guard page around metadata |
27 | // #define MI_SECURE 2 // guard page around each mimalloc page |
28 | // #define MI_SECURE 3 // encode free lists (detect corrupted free list (buffer overflow), and invalid pointer free) |
29 | // #define MI_SECURE 4 // checks for double free. (may be more expensive) |
30 | |
31 | #if !defined(MI_SECURE) |
32 | #define MI_SECURE 0 |
33 | #endif |
34 | |
35 | // Define MI_DEBUG for debug mode |
36 | // #define MI_DEBUG 1 // basic assertion checks and statistics, check double free, corrupted free list, and invalid pointer free. |
37 | // #define MI_DEBUG 2 // + internal assertion checks |
38 | // #define MI_DEBUG 3 // + extensive internal invariant checking (cmake -DMI_DEBUG_FULL=ON) |
39 | #if !defined(MI_DEBUG) |
40 | #if !defined(NDEBUG) || defined(_DEBUG) |
41 | #define MI_DEBUG 2 |
42 | #else |
43 | #define MI_DEBUG 0 |
44 | #endif |
45 | #endif |
46 | |
47 | // Encoded free lists allow detection of corrupted free lists |
48 | // and can detect buffer overflows and double `free`s. |
49 | #if (MI_SECURE>=3 || MI_DEBUG>=1) |
50 | #define MI_ENCODE_FREELIST 1 |
51 | #endif |
52 | |
53 | // ------------------------------------------------------ |
54 | // Platform specific values |
55 | // ------------------------------------------------------ |
56 | |
57 | |
58 | // ------------------------------------------------------ |
59 | // Size of a pointer. |
60 | // We assume that `sizeof(void*)==sizeof(intptr_t)` |
61 | // and it holds for all platforms we know of. |
62 | // |
63 | // However, the C standard only requires that: |
64 | // p == (void*)((intptr_t)p)) |
65 | // but we also need: |
66 | // i == (intptr_t)((void*)i) |
67 | // or otherwise one might define an intptr_t type that is larger than a pointer... |
68 | // ------------------------------------------------------ |
69 | |
70 | #if INTPTR_MAX == 9223372036854775807LL |
71 | # define MI_INTPTR_SHIFT (3) |
72 | #elif INTPTR_MAX == 2147483647LL |
73 | # define MI_INTPTR_SHIFT (2) |
74 | #else |
75 | #error platform must be 32 or 64 bits |
76 | #endif |
77 | |
78 | #define MI_INTPTR_SIZE (1<<MI_INTPTR_SHIFT) |
79 | |
80 | #define KiB ((size_t)1024) |
81 | #define MiB (KiB*KiB) |
82 | #define GiB (MiB*KiB) |
83 | |
84 | // ------------------------------------------------------ |
85 | // Main internal data-structures |
86 | // ------------------------------------------------------ |
87 | |
88 | // Main tuning parameters for segment and page sizes |
89 | // Sizes for 64-bit, divide by two for 32-bit |
90 | #define MI_SMALL_PAGE_SHIFT (13 + MI_INTPTR_SHIFT) // 64kb |
91 | #define MI_MEDIUM_PAGE_SHIFT ( 3 + MI_SMALL_PAGE_SHIFT) // 512kb |
92 | #define MI_LARGE_PAGE_SHIFT ( 3 + MI_MEDIUM_PAGE_SHIFT) // 4mb |
93 | #define MI_SEGMENT_SHIFT ( MI_LARGE_PAGE_SHIFT) // 4mb |
94 | |
95 | // Derived constants |
96 | #define MI_SEGMENT_SIZE (1<<MI_SEGMENT_SHIFT) |
97 | #define MI_SEGMENT_MASK ((uintptr_t)MI_SEGMENT_SIZE - 1) |
98 | |
99 | #define MI_SMALL_PAGE_SIZE (1<<MI_SMALL_PAGE_SHIFT) |
100 | #define MI_MEDIUM_PAGE_SIZE (1<<MI_MEDIUM_PAGE_SHIFT) |
101 | #define MI_LARGE_PAGE_SIZE (1<<MI_LARGE_PAGE_SHIFT) |
102 | |
103 | #define MI_SMALL_PAGES_PER_SEGMENT (MI_SEGMENT_SIZE/MI_SMALL_PAGE_SIZE) |
104 | #define MI_MEDIUM_PAGES_PER_SEGMENT (MI_SEGMENT_SIZE/MI_MEDIUM_PAGE_SIZE) |
105 | #define MI_LARGE_PAGES_PER_SEGMENT (MI_SEGMENT_SIZE/MI_LARGE_PAGE_SIZE) |
106 | |
107 | // The max object size are checked to not waste more than 12.5% internally over the page sizes. |
108 | // (Except for large pages since huge objects are allocated in 4MiB chunks) |
109 | #define MI_SMALL_OBJ_SIZE_MAX (MI_SMALL_PAGE_SIZE/4) // 16kb |
110 | #define MI_MEDIUM_OBJ_SIZE_MAX (MI_MEDIUM_PAGE_SIZE/4) // 128kb |
111 | #define MI_LARGE_OBJ_SIZE_MAX (MI_LARGE_PAGE_SIZE/2) // 2mb |
112 | #define MI_LARGE_OBJ_WSIZE_MAX (MI_LARGE_OBJ_SIZE_MAX/MI_INTPTR_SIZE) |
113 | #define MI_HUGE_OBJ_SIZE_MAX (2*MI_INTPTR_SIZE*MI_SEGMENT_SIZE) // (must match MI_REGION_MAX_ALLOC_SIZE in memory.c) |
114 | |
115 | // Minimal alignment necessary. On most platforms 16 bytes are needed |
116 | // due to SSE registers for example. This must be at least `MI_INTPTR_SIZE` |
117 | #define MI_MAX_ALIGN_SIZE 16 // sizeof(max_align_t) |
118 | |
119 | // Maximum number of size classes. (spaced exponentially in 12.5% increments) |
120 | #define MI_BIN_HUGE (73U) |
121 | |
122 | #if (MI_LARGE_OBJ_WSIZE_MAX >= 655360) |
123 | #error "define more bins" |
124 | #endif |
125 | |
126 | // The free lists use encoded next fields |
127 | // (Only actually encodes when MI_ENCODED_FREELIST is defined.) |
128 | typedef uintptr_t mi_encoded_t; |
129 | |
130 | // free lists contain blocks |
131 | typedef struct mi_block_s { |
132 | mi_encoded_t next; |
133 | } mi_block_t; |
134 | |
135 | |
136 | // The delayed flags are used for efficient multi-threaded free-ing |
137 | typedef enum mi_delayed_e { |
138 | MI_NO_DELAYED_FREE = 0, |
139 | MI_USE_DELAYED_FREE = 1, |
140 | MI_DELAYED_FREEING = 2, |
141 | MI_NEVER_DELAYED_FREE = 3 |
142 | } mi_delayed_t; |
143 | |
144 | |
145 | // The `in_full` and `has_aligned` page flags are put in a union to efficiently |
146 | // test if both are false (`full_aligned == 0`) in the `mi_free` routine. |
147 | typedef union mi_page_flags_s { |
148 | uint8_t full_aligned; |
149 | struct { |
150 | uint8_t in_full : 1; |
151 | uint8_t has_aligned : 1; |
152 | } x; |
153 | } mi_page_flags_t; |
154 | |
155 | // Thread free list. |
156 | // We use the bottom 2 bits of the pointer for mi_delayed_t flags |
157 | typedef uintptr_t mi_thread_free_t; |
158 | |
159 | // A page contains blocks of one specific size (`block_size`). |
160 | // Each page has three list of free blocks: |
161 | // `free` for blocks that can be allocated, |
162 | // `local_free` for freed blocks that are not yet available to `mi_malloc` |
163 | // `thread_free` for freed blocks by other threads |
164 | // The `local_free` and `thread_free` lists are migrated to the `free` list |
165 | // when it is exhausted. The separate `local_free` list is necessary to |
166 | // implement a monotonic heartbeat. The `thread_free` list is needed for |
167 | // avoiding atomic operations in the common case. |
168 | // |
169 | // `used - thread_freed` == actual blocks that are in use (alive) |
170 | // `used - thread_freed + |free| + |local_free| == capacity` |
171 | // |
172 | // note: we don't count `freed` (as |free|) instead of `used` to reduce |
173 | // the number of memory accesses in the `mi_page_all_free` function(s). |
174 | // note: the funny layout here is due to: |
175 | // - access is optimized for `mi_free` and `mi_page_alloc` |
176 | // - using `uint16_t` does not seem to slow things down |
177 | typedef struct mi_page_s { |
178 | // "owned" by the segment |
179 | uint8_t segment_idx; // index in the segment `pages` array, `page == &segment->pages[page->segment_idx]` |
180 | uint8_t segment_in_use:1; // `true` if the segment allocated this page |
181 | uint8_t is_reset:1; // `true` if the page memory was reset |
182 | uint8_t is_committed:1; // `true` if the page virtual memory is committed |
183 | uint8_t is_zero_init:1; // `true` if the page was zero initialized |
184 | |
185 | // layout like this to optimize access in `mi_malloc` and `mi_free` |
186 | uint16_t capacity; // number of blocks committed, must be the first field, see `segment.c:page_clear` |
187 | uint16_t reserved; // number of blocks reserved in memory |
188 | mi_page_flags_t flags; // `in_full` and `has_aligned` flags (8 bits) |
189 | bool is_zero; // `true` if the blocks in the free list are zero initialized |
190 | |
191 | mi_block_t* free; // list of available free blocks (`malloc` allocates from this list) |
192 | #ifdef MI_ENCODE_FREELIST |
193 | uintptr_t cookie; // random cookie to encode the free lists |
194 | #endif |
195 | size_t used; // number of blocks in use (including blocks in `local_free` and `thread_free`) |
196 | |
197 | mi_block_t* local_free; // list of deferred free blocks by this thread (migrates to `free`) |
198 | volatile _Atomic(uintptr_t) thread_freed; // at least this number of blocks are in `thread_free` |
199 | volatile _Atomic(mi_thread_free_t) thread_free; // list of deferred free blocks freed by other threads |
200 | |
201 | // less accessed info |
202 | size_t block_size; // size available in each block (always `>0`) |
203 | mi_heap_t* heap; // the owning heap |
204 | struct mi_page_s* next; // next page owned by this thread with the same `block_size` |
205 | struct mi_page_s* prev; // previous page owned by this thread with the same `block_size` |
206 | |
207 | // improve page index calculation |
208 | // without padding: 10 words on 64-bit, 11 on 32-bit. Secure adds one word |
209 | #if (MI_INTPTR_SIZE==8 && defined(MI_ENCODE_FREELIST)) || (MI_INTPTR_SIZE==4 && !defined(MI_ENCODE_FREELIST)) |
210 | void* padding[1]; // 12 words on 64-bit with cookie, 12 words on 32-bit plain |
211 | #endif |
212 | } mi_page_t; |
213 | |
214 | |
215 | |
216 | typedef enum mi_page_kind_e { |
217 | MI_PAGE_SMALL, // small blocks go into 64kb pages inside a segment |
218 | MI_PAGE_MEDIUM, // medium blocks go into 512kb pages inside a segment |
219 | MI_PAGE_LARGE, // larger blocks go into a single page spanning a whole segment |
220 | MI_PAGE_HUGE // huge blocks (>512kb) are put into a single page in a segment of the exact size (but still 2mb aligned) |
221 | } mi_page_kind_t; |
222 | |
223 | // Segments are large allocated memory blocks (2mb on 64 bit) from |
224 | // the OS. Inside segments we allocated fixed size _pages_ that |
225 | // contain blocks. |
226 | typedef struct mi_segment_s { |
227 | // memory fields |
228 | size_t memid; // id for the os-level memory manager |
229 | bool mem_is_fixed; // `true` if we cannot decommit/reset/protect in this memory (i.e. when allocated using large OS pages) |
230 | bool mem_is_committed; // `true` if the whole segment is eagerly committed |
231 | |
232 | // segment fields |
233 | struct mi_segment_s* next; // must be the first segment field -- see `segment.c:segment_alloc` |
234 | struct mi_segment_s* prev; |
235 | volatile _Atomic(struct mi_segment_s*) abandoned_next; |
236 | size_t abandoned; // abandoned pages (i.e. the original owning thread stopped) (`abandoned <= used`) |
237 | size_t used; // count of pages in use (`used <= capacity`) |
238 | size_t capacity; // count of available pages (`#free + used`) |
239 | size_t segment_size;// for huge pages this may be different from `MI_SEGMENT_SIZE` |
240 | size_t segment_info_size; // space we are using from the first page for segment meta-data and possible guard pages. |
241 | uintptr_t cookie; // verify addresses in debug mode: `mi_ptr_cookie(segment) == segment->cookie` |
242 | |
243 | // layout like this to optimize access in `mi_free` |
244 | size_t page_shift; // `1 << page_shift` == the page sizes == `page->block_size * page->reserved` (unless the first page, then `-segment_info_size`). |
245 | volatile _Atomic(uintptr_t) thread_id; // unique id of the thread owning this segment |
246 | mi_page_kind_t page_kind; // kind of pages: small, large, or huge |
247 | mi_page_t pages[1]; // up to `MI_SMALL_PAGES_PER_SEGMENT` pages |
248 | } mi_segment_t; |
249 | |
250 | |
251 | // ------------------------------------------------------ |
252 | // Heaps |
253 | // Provide first-class heaps to allocate from. |
254 | // A heap just owns a set of pages for allocation and |
255 | // can only be allocate/reallocate from the thread that created it. |
256 | // Freeing blocks can be done from any thread though. |
257 | // Per thread, the segments are shared among its heaps. |
258 | // Per thread, there is always a default heap that is |
259 | // used for allocation; it is initialized to statically |
260 | // point to an empty heap to avoid initialization checks |
261 | // in the fast path. |
262 | // ------------------------------------------------------ |
263 | |
264 | // Thread local data |
265 | typedef struct mi_tld_s mi_tld_t; |
266 | |
267 | // Pages of a certain block size are held in a queue. |
268 | typedef struct mi_page_queue_s { |
269 | mi_page_t* first; |
270 | mi_page_t* last; |
271 | size_t block_size; |
272 | } mi_page_queue_t; |
273 | |
274 | #define MI_BIN_FULL (MI_BIN_HUGE+1) |
275 | |
276 | // A heap owns a set of pages. |
277 | struct mi_heap_s { |
278 | mi_tld_t* tld; |
279 | mi_page_t* pages_free_direct[MI_SMALL_WSIZE_MAX + 2]; // optimize: array where every entry points a page with possibly free blocks in the corresponding queue for that size. |
280 | mi_page_queue_t pages[MI_BIN_FULL + 1]; // queue of pages for each size class (or "bin") |
281 | volatile _Atomic(mi_block_t*) thread_delayed_free; |
282 | uintptr_t thread_id; // thread this heap belongs too |
283 | uintptr_t cookie; |
284 | uintptr_t random; // random number used for secure allocation |
285 | size_t page_count; // total number of pages in the `pages` queues. |
286 | bool no_reclaim; // `true` if this heap should not reclaim abandoned pages |
287 | }; |
288 | |
289 | |
290 | |
291 | // ------------------------------------------------------ |
292 | // Debug |
293 | // ------------------------------------------------------ |
294 | |
295 | #define MI_DEBUG_UNINIT (0xD0) |
296 | #define MI_DEBUG_FREED (0xDF) |
297 | |
298 | |
299 | #if (MI_DEBUG) |
300 | // use our own assertion to print without memory allocation |
301 | void _mi_assert_fail(const char* assertion, const char* fname, unsigned int line, const char* func ); |
302 | #define mi_assert(expr) ((expr) ? (void)0 : _mi_assert_fail(#expr,__FILE__,__LINE__,__func__)) |
303 | #else |
304 | #define mi_assert(x) |
305 | #endif |
306 | |
307 | #if (MI_DEBUG>1) |
308 | #define mi_assert_internal mi_assert |
309 | #else |
310 | #define mi_assert_internal(x) |
311 | #endif |
312 | |
313 | #if (MI_DEBUG>2) |
314 | #define mi_assert_expensive mi_assert |
315 | #else |
316 | #define mi_assert_expensive(x) |
317 | #endif |
318 | |
319 | // ------------------------------------------------------ |
320 | // Statistics |
321 | // ------------------------------------------------------ |
322 | |
323 | #ifndef MI_STAT |
324 | #if (MI_DEBUG>0) |
325 | #define MI_STAT 2 |
326 | #else |
327 | #define MI_STAT 0 |
328 | #endif |
329 | #endif |
330 | |
331 | typedef struct mi_stat_count_s { |
332 | int64_t allocated; |
333 | int64_t freed; |
334 | int64_t peak; |
335 | int64_t current; |
336 | } mi_stat_count_t; |
337 | |
338 | typedef struct mi_stat_counter_s { |
339 | int64_t total; |
340 | int64_t count; |
341 | } mi_stat_counter_t; |
342 | |
343 | typedef struct mi_stats_s { |
344 | mi_stat_count_t segments; |
345 | mi_stat_count_t pages; |
346 | mi_stat_count_t reserved; |
347 | mi_stat_count_t committed; |
348 | mi_stat_count_t reset; |
349 | mi_stat_count_t page_committed; |
350 | mi_stat_count_t segments_abandoned; |
351 | mi_stat_count_t pages_abandoned; |
352 | mi_stat_count_t threads; |
353 | mi_stat_count_t huge; |
354 | mi_stat_count_t giant; |
355 | mi_stat_count_t malloc; |
356 | mi_stat_count_t segments_cache; |
357 | mi_stat_counter_t pages_extended; |
358 | mi_stat_counter_t mmap_calls; |
359 | mi_stat_counter_t commit_calls; |
360 | mi_stat_counter_t page_no_retire; |
361 | mi_stat_counter_t searches; |
362 | mi_stat_counter_t huge_count; |
363 | mi_stat_counter_t giant_count; |
364 | #if MI_STAT>1 |
365 | mi_stat_count_t normal[MI_BIN_HUGE+1]; |
366 | #endif |
367 | } mi_stats_t; |
368 | |
369 | |
370 | void _mi_stat_increase(mi_stat_count_t* stat, size_t amount); |
371 | void _mi_stat_decrease(mi_stat_count_t* stat, size_t amount); |
372 | void _mi_stat_counter_increase(mi_stat_counter_t* stat, size_t amount); |
373 | |
374 | #if (MI_STAT) |
375 | #define mi_stat_increase(stat,amount) _mi_stat_increase( &(stat), amount) |
376 | #define mi_stat_decrease(stat,amount) _mi_stat_decrease( &(stat), amount) |
377 | #define mi_stat_counter_increase(stat,amount) _mi_stat_counter_increase( &(stat), amount) |
378 | #else |
379 | #define mi_stat_increase(stat,amount) (void)0 |
380 | #define mi_stat_decrease(stat,amount) (void)0 |
381 | #define mi_stat_counter_increase(stat,amount) (void)0 |
382 | #endif |
383 | |
384 | #define mi_heap_stat_increase(heap,stat,amount) mi_stat_increase( (heap)->tld->stats.stat, amount) |
385 | #define mi_heap_stat_decrease(heap,stat,amount) mi_stat_decrease( (heap)->tld->stats.stat, amount) |
386 | |
387 | |
388 | // ------------------------------------------------------ |
389 | // Thread Local data |
390 | // ------------------------------------------------------ |
391 | |
392 | // Queue of segments |
393 | typedef struct mi_segment_queue_s { |
394 | mi_segment_t* first; |
395 | mi_segment_t* last; |
396 | } mi_segment_queue_t; |
397 | |
398 | |
399 | // Segments thread local data |
400 | typedef struct mi_segments_tld_s { |
401 | mi_segment_queue_t small_free; // queue of segments with free small pages |
402 | mi_segment_queue_t medium_free; // queue of segments with free medium pages |
403 | size_t count; // current number of segments; |
404 | size_t peak_count; // peak number of segments |
405 | size_t current_size; // current size of all segments |
406 | size_t peak_size; // peak size of all segments |
407 | size_t cache_count; // number of segments in the cache |
408 | size_t cache_size; // total size of all segments in the cache |
409 | mi_segment_t* cache; // (small) cache of segments |
410 | mi_stats_t* stats; // points to tld stats |
411 | } mi_segments_tld_t; |
412 | |
413 | // OS thread local data |
414 | typedef struct mi_os_tld_s { |
415 | size_t region_idx; // start point for next allocation |
416 | mi_stats_t* stats; // points to tld stats |
417 | } mi_os_tld_t; |
418 | |
419 | // Thread local data |
420 | struct mi_tld_s { |
421 | unsigned long long heartbeat; // monotonic heartbeat count |
422 | bool recurse; // true if deferred was called; used to prevent infinite recursion. |
423 | mi_heap_t* heap_backing; // backing heap of this thread (cannot be deleted) |
424 | mi_segments_tld_t segments; // segment tld |
425 | mi_os_tld_t os; // os tld |
426 | mi_stats_t stats; // statistics |
427 | }; |
428 | |
429 | #endif |
430 | |