1/* ----------------------------------------------------------------------------
2Copyright (c) 2018, Microsoft Research, Daan Leijen
3This is free software; you can redistribute it and/or modify it under the
4terms 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.)
128typedef uintptr_t mi_encoded_t;
129
130// free lists contain blocks
131typedef 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
137typedef 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.
147typedef 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
157typedef 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
177typedef 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
216typedef 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.
226typedef 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
265typedef struct mi_tld_s mi_tld_t;
266
267// Pages of a certain block size are held in a queue.
268typedef 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.
277struct 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
301void _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
331typedef 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
338typedef struct mi_stat_counter_s {
339 int64_t total;
340 int64_t count;
341} mi_stat_counter_t;
342
343typedef 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
370void _mi_stat_increase(mi_stat_count_t* stat, size_t amount);
371void _mi_stat_decrease(mi_stat_count_t* stat, size_t amount);
372void _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
393typedef 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
400typedef 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
414typedef 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
420struct 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