1 /**************************************************************************
3 * Copyright 2013-2014 RAD Game Tools and Valve Software
4 * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 **************************************************************************/
27 // stb_malloc.h 0.01 -- public domain multi-heap malloc -- Sean Barrett, 2012
\r
29 // WARNING -- IN THIS VERSION THE STBM_TC STUFF IS UNTESTED AND
\r
30 // CROSS-THREAD FREES AREN'T CODED -- IGGY DOESN'T USE THOSE FEATURES
\r
31 // AND THAT'S ALL I'VE CODED/TESTED
\r
33 // A malloc "implementation" that you need to do a bit of configuring
\r
34 // on to actually make a malloc.
\r
38 // Define the preprocessor macros STB_MALLOC_IMPLEMENTATION
\r
39 // in *one* .c/.cpp file before #including this file, e.g.:
\r
41 // #define STB_MALLOC_IMPLEMENTATION
\r
42 // #include "stb_malloc.h"
\r
44 // Also optionally define the symbols listed in the section
\r
45 // "Optional definitions" below.
\r
49 // - TLSF for mid-sized allocations for O(1) allocation & freeing
\r
50 // - large allocations go to user-defined "system allocator"
\r
51 // - small allocations (<= pointer-sized) slab-allocated (no coalescing)
\r
52 // - no constraints on system allocator (e.g. page-aligned NOT required)
\r
53 // - multiple separate heaps which don't interfragment
\r
54 // - can free heap all-at-once without freeing individual allocations
\r
55 // - can free without specifying which heap it came from
\r
57 // - must create one thread cache per thread per heap that you want cached
\r
58 // - you must create/manage any thread-local variables yourself
\r
59 // - almost every allocation offers a 16-bit user-defined "header" field
\r
60 // - overhead of 8 bytes in 32-bit, 16 bytes in 64-bit
\r
61 // - half that for allocations of 4 bytes in 32-bit, 8 bytes in 64-bit
\r
62 // - but they get no 16-bit user field
\r
63 // - plus overhead for allocations that aren't multiples of alignment
\r
64 // - all configuration at run-time
\r
65 // - choose per-heap minimum alignment at heap creation
\r
66 // - provide mutex handles or not for thread-safety / non-safety
\r
67 // - enable file/line recording on the fly (mixed in one heap)
\r
68 // - enable trailing guard bytes on the fly (mixed in one heap)
\r
69 // - enable variable-sized user-defined debug data on the fly (mixed)
\r
70 // - all on-the-fly-enables incur significant extra size in malloc header
\r
71 // - compile time configuration of platform features
\r
72 // - definition of a mutex handle and operations to lock/unlock it
\r
73 // - definition of a compare-and-swap for faster cross-thread frees
\r
75 // Four possible models:
\r
76 // - create single-thread-only heaps without mutexes for fast performance
\r
77 // - create mutexed heap with per-thread thread cache for "global" malloc
\r
78 // that shares memory between threads
\r
79 // - create per-thread single-thread-only heap with cross-thread mutex for
\r
80 // fast "global" malloc without sharing memory (no false sharing)
\r
81 // - create M heaps for N threads with per-thread thread caches and
\r
82 // primary mutexes and cross-thread-mutexes
\r
84 // Optional definitions:
\r
86 // STBM_MUTEX_HANDLE
\r
87 // The type of a handle to a mutex. It must be comparable against
\r
88 // 0 to mean "is it null". These should be as-efficient-as-possible
\r
89 // process-private mutexes, not cross-process mutexes. If not
\r
90 // defined, allocation heaps are not thread-safe.
\r
92 // STBM_MUTEX_ACQUIRE
\r
93 // "Lock" a mutex handle. A single thread of stb_malloc will
\r
94 // never lock more than one mutex at a time, nor try to lock
\r
95 // the same mutex twice (they are not "reentrant"). Must be
\r
96 // defined if STBM_MUTEX_HANDLE is defined.
\r
98 // STBM_MUTEX_RELEASE
\r
99 // Release a previously acquired mutex, as above.
\r
101 // STBM_COMPARE_AND_SWAP32
\r
102 // Define a function that performs an atomic compare-and-swap on
\r
103 // a 32-bit value. (To be specified, since it's unimplemented so far.)
\r
104 // Only used if STBM_MUTEX_HANDLE is defined and a cross-thread
\r
105 // mutex is defined for a given heap.
\r
109 // STBM_POINTER_SIZE
\r
110 // If your compiler is C99, you do not need to define these.
\r
111 // Otherwise, stb_malloc will try default (32-bit) assignments
\r
112 // for them and validate them at compile time. If they are
\r
113 // incorrect, you will get compile errors, and will need to
\r
114 // define them yourself. STBM_POINTER_SIZE should be 32 or 64.
\r
116 // STBM_LOG2_32BIT(x)
\r
117 // Compute floor of log2 of a 32-bit number, or -1 if 0, i.e.
\r
118 // "31-count_leading_zeroes32(x)". This function is important to
\r
119 // high-performance of the allocator; it is used for computing block
\r
120 // "sizeclasses" and for TLSF O(1) scans. If you do not define it,
\r
121 // stb_malloc uses a small binary tree and a small table lookup.
\r
124 // If you don't define this, stb_malloc uses assert.h and assert().
\r
125 // This is the only C standard library function used by stb_malloc.
\r
128 // You can define this to 'memset' or your own memset replacement;
\r
129 // if not, stb_malloc uses a naive (possibly less efficient)
\r
133 // You can define this to 'memcpy' or your own memcpy replacement;
\r
134 // if not, stb_malloc uses a naive (probably inefficient)
\r
138 // This function (which takes a char*) is called when there is an
\r
139 // extraordinary failure: a corrupt header is detected, guard bytes
\r
140 // are overwritten, or the API is used incorrectly. It is NOT called
\r
141 // if an allocation fails, which is considered a normal behavior.
\r
142 // If not defined, defaults to STBM_ASSERT(0).
\r
145 // Defines an attribute applied to any callback functions, useful
\r
146 // for special linkage conventions.
\r
149 // If defined, supresses the stbm_heap typedef for compilers that
\r
150 // don't like to see duplicate identical typedefs.
\r
153 // If defined, declares all functions as static, so they can only
\r
154 // be accessed from the file that creates the implementation.
\r
157 // If defined, enables internal automatic calls to iggy_heap_check
\r
158 // to validate the heap after every operation (slow).
\r
161 // On The Design Of stb_malloc.h
\r
163 // I've written many allocators (google for 'satoria smalloc' for the 1st).
\r
164 // stb_malloc.h is my most refined, the collision of seven central ideas:
\r
166 // - feature: multiple heaps, with heap-independent freeing
\r
167 // - design: overhead mostly proportional to used memory
\r
168 // - design: reuse-oriented API/implementation (i.e. stb_-library-style)
\r
169 // - design: all malloc options available without compile-time switches
\r
170 // - algorithm: TLSF (two-level segregated fit) for O(1) allocation
\r
171 // - algorithm: boundary-tag coalescing for O(1) frees
\r
172 // - algorithm: thread-caching inspired by TCMalloc
\r
174 // Implementation information appears after the header section.
\r
176 #ifndef INCLUDE_STB_MALLOC_H
\r
177 #define INCLUDE_STB_MALLOC_H
\r
179 // #define STBM_MUTEX_HANDLE to be the datatype of a pointer
\r
180 // to a mutex or else the code will not be thread-safe
\r
181 #ifndef STBM_MUTEX_HANDLE
\r
182 // create a dummy pointer as the handle type
\r
183 #define STBM_MUTEX_HANDLE void *
\r
184 #define STBM__NO_MUTEX_HANDLE
\r
188 #define STBM__API static
\r
190 #define STBM__API extern
\r
197 #include <stdlib.h> // size_t
\r
199 typedef struct stbm_heap stbm_heap;
\r
200 typedef struct stbm_tc stbm_tc;
\r
202 STBM__API void *stbm_alloc(stbm_tc *tc, stbm_heap *heap, size_t size, unsigned short userdata16);
\r
203 // allocate a block of memory of 'size' bytes from the heap 'heap';
\r
204 // userdata16 is an arbitrary 16-bit number stored in the allocation.
\r
206 // For small blocks, the efficient storage format is only used
\r
207 // if userdata16 == 0.
\r
209 // if tc is not NULL, tc may not be accessed by any other thread at
\r
210 // the same time, and the function may allocate from tc and cache
\r
211 // additional blocks into tc
\r
213 // If heap does not have an allocation mutex, then this function
\r
214 // is allowed to manipulate it without taking any mutexes.
\r
216 STBM__API void *stbm_alloc_align(stbm_tc *tc, stbm_heap *heap, size_t size, unsigned short userdata16, size_t alignment, size_t align_offset);
\r
217 // allocate a block of memory of 'size' bytes from the heap 'heap'
\r
218 // which is aligned to a multiple of 'alignment' (which must be a
\r
221 // userdata16 is an arbitrary 16-bit number stored in the allocation.
\r
223 // if tc is not NULL, tc may not be accessed by any other thread at
\r
224 // the same time, and the function may allocate from tc and cache
\r
225 // additional blocks into tc
\r
227 // If heap does not have an allocation mutex, then this function
\r
228 // is allowed to manipulate it without taking any mutexes.
\r
230 STBM__API void *stbm_alloc_debug(stbm_tc *tc, stbm_heap *heap, size_t size, unsigned short userdata16, size_t alignment, size_t align_offset, char *file, int line, size_t extra_debug_size);
\r
231 // allocate a block of memory of 'size' bytes from the heap 'heap';
\r
232 // userdata16 is an arbitrary 16-bit number stored in the allocation.
\r
233 // an additional 'extra_debug_size' bytes are allocated which are
\r
234 // separate from the main block, accessible through stbm_get_debug_data.
\r
236 // if tc is not NULL, tc may not be accessed by any other thread at
\r
237 // the same time, and the function may allocate from tc and cache
\r
238 // additional blocks into tc
\r
240 // If heap does not have an allocation mutex, then this function
\r
241 // is allowed to manipulate it without taking any mutexes.
\r
243 STBM__API void *stbm_alloc_fileline(stbm_tc *tc, stbm_heap *heap, size_t size, unsigned short userdata16, char *file, int line);
\r
244 // allocate a block of memory of 'size' bytes from the heap 'heap';
\r
245 // userdata16 is an arbitrary 16-bit number stored in the allocation.
\r
247 // if stbm_heapconfig_capture_file_line() has been enabled for this
\r
248 // heap, then extra data is allocated in the block and the file/line
\r
249 // are recorded; otherwise file/line are ignored
\r
251 // For small blocks, the efficient storage format is only used
\r
252 // if userdata16 == 0 and stbm_heapconfig_capture_file_line is not
\r
255 // if tc is not NULL, tc may not be accessed by any other thread at
\r
256 // the same time, and the function may allocate from tc and cache
\r
257 // additional blocks into tc
\r
259 // If heap does not have an allocation mutex, then this function
\r
260 // is allowed to manipulate it without taking any mutexes.
\r
262 STBM__API void *stbm_alloc_align_fileline(stbm_tc *tc, stbm_heap *heap, size_t size, unsigned short userdata16, size_t alignment, size_t align_offset, char *file, int line);
\r
263 // allocate a block of memory of 'size' bytes from the heap 'heap'
\r
264 // which is aligned to a multiple of 'alignment' (which must be a
\r
267 // if stbm_heapconfig_capture_file_line() has been enabled for this
\r
268 // heap, then extra data is allocated in the block and the file/line
\r
269 // are recorded; otherwise file/line are ignored
\r
271 // userdata16 is an arbitrary 16-bit number stored in the allocation.
\r
273 // if tc is not NULL, tc may not be accessed by any other thread at
\r
274 // the same time, and the function may allocate from tc and cache
\r
275 // additional blocks into tc
\r
277 // If heap does not have an allocation mutex, then this function
\r
278 // is allowed to manipulate it without taking any mutexes.
\r
280 STBM__API void stbm_free(stbm_tc *tc, stbm_heap *preferred_heap, void *ptr);
\r
281 // frees a previously-allocated block of memory addressed by 'ptr' from
\r
282 // whichever heap it was allocated from.
\r
284 // if tc is non-NULL and associated with the heap the ptr was
\r
285 // allocated from, the block may be cached in tc.
\r
287 // If the allocation came from preferred_heap, it will be properly freed
\r
288 // into the general allocation pool for preferred_heap. Otherwise, it will
\r
289 // be added to the cross-heap free list for the source heap, where it will
\r
290 // only be fully freed the next time an allocation is made from that heap.
\r
292 // If preferred_heap does not have an allocation mutex, then this function
\r
293 // is allowed to manipulate preferred_heap without taking any mutexes.
\r
295 STBM__API void stbm_tc_flush(stbm_tc *tc, stbm_heap *preferred_heap, void *ptr);
\r
296 // any pointers cached in tc are flushed back to the relevant heap, using
\r
297 // the same locking logic described for stbm_free.
\r
299 STBM__API void *stbm_realloc(stbm_tc *tc, stbm_heap *heap, void *ptr, size_t newsize, unsigned short userdata16);
\r
300 // "resizes" a block of memory, effectively equivalent to a call to stbm_alloc/stbm_alloc_tc
\r
301 // and a call to stbm_free_tc/stbm_free, all using tc & heap.
\r
303 // Note that this function will allocate from heap, so heap must be a "preferred"
\r
306 STBM__API size_t stbm_get_allocation_size(void *ptr);
\r
307 // query the available memory pointed to by the pointer
\r
309 STBM__API unsigned short stbm_get_userdata(void *ptr);
\r
310 // query the arbitrary 16-bit identifier associated with the pointer
\r
312 STBM__API stbm_heap *stbm_get_heap(void *ptr);
\r
313 // determine which heap it was allocated from
\r
315 STBM__API int stbm_get_fileline(void *ptr, char **file);
\r
316 // get the stored file & line, or 0 if none stored
\r
318 STBM__API size_t stbm_get_debug_data(void *ptr, void **data);
\r
319 // get a pointer to the extra data specified by stbm_alloc_debug
\r
321 #ifndef STBM_CALLBACK
\r
322 #define STBM_CALLBACK
\r
325 typedef void *STBM_CALLBACK stbm_system_alloc(void *user_context, size_t size_requested, size_t *size_provided);
\r
326 typedef void STBM_CALLBACK stbm_system_free(void *user_context, void *ptr, size_t size);
\r
328 #define STBM_TC_SIZEOF (sizeof(void *) * 2 * 32 + 64 + 64 + sizeof(void *) + 4 * 4 + 257 + sizeof(void *))
\r
330 STBM__API stbm_tc *stbm_tc_init(void *storage, size_t storage_bytes, stbm_heap *heap);
\r
331 // initialize a new thread-cache referring to 'heap';
\r
332 // storage_size_in_bytes must be as large as the minimum
\r
333 // thread cache size.
\r
335 STBM__API void stbm_heap_free(stbm_heap *);
\r
336 // Frees all system allocations made by this heap back to the
\r
337 // system allocator. Any outstanding allocations from this heap
\r
338 // become invalid. (For example, outstanding cached allocations
\r
339 // in any corresponding stbm_tc's.) The heap itself becomes
\r
340 // invalid (you must init it to use it again).
\r
342 STBM__API void *stbm_get_heap_user_context(stbm_heap *);
\r
343 // get back the user context set in the creation
\r
347 // You pass in allocators which are used to get additional storage.
\r
348 // If they are NULL, only the storage passed in above is used to satisfy
\r
349 // allocations, but also allocations larger than 1MB are NOT supported.
\r
350 stbm_system_alloc *system_alloc;
\r
351 stbm_system_free *system_free;
\r
352 void *user_context;
\r
354 // All allocations have a default alignment of 8 (32-bit) or 16 (64-bit).
\r
355 // You can choose a higher power-of-two default alignment here.
\r
356 size_t minimum_alignment;
\r
358 // If you do not set the following flag, then blocks which are smaller
\r
359 // than the requested minimum alignment may get a smaller alignment
\r
360 // (namely, the original default 8/16 alignment). If you set this flag,
\r
361 // then EVERY allocation, not matter how small, will get the alignment.
\r
362 // Currently this disables the smallest-block optimizations and will waste
\r
363 // lots of memory for those, but has no effect on intermediate sizes.
\r
364 int align_all_blocks_to_minimum;
\r
366 // This mutex is used to prevent multiple threads from manipulating
\r
367 // the heap data structure atstbm_heap_free the same time. It should be non-NULL if
\r
368 // you will have multiple thread allocating from this heap. If only
\r
369 // one thread will be allocating from the heap it can be null.
\r
370 STBM_MUTEX_HANDLE allocation_mutex;
\r
372 // If this mutex is provided, then frees which do not have the correct
\r
373 // heap passed to the free call will be put on a special 'crossthread'
\r
374 // free list. This prevents them from contending with threads that are
\r
375 // allocating using the allocation mutex, and also allows cross-thread
\r
376 // freeing even if there is no allocation mutex.
\r
377 STBM_MUTEX_HANDLE crossthread_free_mutex;
\r
378 } stbm_heap_config;
\r
380 STBM__API stbm_heap *stbm_heap_init(void *storage, size_t storage_bytes, stbm_heap_config *hc);
\r
381 // initialize a new heap from memory you provide which must be
\r
382 // at least STBM_HEAP_SIZEOF; the data in the stbm_heap_config
\r
383 // is copied, so you don't need to preserve it after this returns.
\r
385 #define STBM_HEAP_SIZEOF \
\r
387 /* alignment */ 60 \
\r
388 /* ct_free_stack */ + sizeof(void *) * 16 + 64 \
\r
389 /* ct_free_list */ + 64 \
\r
390 /* alloc_lock */ + sizeof(STBM_MUTEX_HANDLE) \
\r
391 /* configuration */ + 3 * sizeof(size_t) + 6 * 4 \
\r
392 /* system_alloc */ + 5 * sizeof(void *) + 3 * sizeof(void *) \
\r
393 /* stats */ + 2 * 4 + 4 * sizeof(void *) \
\r
394 /* small */ + 2 * (6 * sizeof(void *) + 2 * 4) + sizeof(void *) \
\r
395 /* medium */ + 3 * 4 + 13 * 4 + 13 * 32 * sizeof(void *) + 4 * sizeof(void *)\
\r
398 STBM__API void stbm_heapconfig_set_trailing_guard_bytes(stbm_heap *heap, size_t num_bytes, unsigned char value);
\r
399 STBM__API void stbm_heapconfig_capture_file_line(stbm_heap *heap, int enable_capture);
\r
400 STBM__API void stbm_heapconfig_gather_full_stats(stbm_heap *heap);
\r
401 STBM__API void stbm_heapconfig_set_largealloc_threshhold(stbm_heap *heap, size_t threshhold);
\r
402 STBM__API void stbm_heapconfig_set_medium_chunk_size(stbm_heap *heap, size_t cur_size, size_t max_size);
\r
403 STBM__API void stbm_heapconfig_set_small_chunk_size(stbm_heap *heap, size_t size);
\r
404 STBM__API void stbm_heap_check(stbm_heap *heap);
\r
406 #define STBM_MEDIUM_CACHE_none 0
\r
407 #define STBM_MEDIUM_CACHE_one 1
\r
408 #define STBM_MEDIUM_CACHE_all 2
\r
410 STBM__API void stbm_heapconfig_cache_medium_chunks(stbm_heap *heap, int cache_mode);
\r
415 unsigned short userdata;
\r
421 int extra_data_bytes;
\r
424 typedef void STBM_CALLBACK stbm_debug_iterate_func(void *usercontext, stbm_alloc_info *data);
\r
426 STBM__API void stbm_debug_iterate(stbm_heap *heap, stbm_debug_iterate_func *callback, void *user_context);
\r
432 #endif //INCLUDE_STB_MALLOC_H
\r