Initial vogl checkin

[vogl] / src / voglcore / stb_malloc.h

/**************************************************************************
 *
 * Copyright 2013-2014 RAD Game Tools and Valve Software
 * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
 * All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 *
 **************************************************************************/

// stb_malloc.h 0.01 -- public domain multi-heap malloc -- Sean Barrett, 2012\r
//\r
// WARNING -- IN THIS VERSION THE STBM_TC STUFF IS UNTESTED AND\r
// CROSS-THREAD FREES AREN'T CODED -- IGGY DOESN'T USE THOSE FEATURES\r
// AND THAT'S ALL I'VE CODED/TESTED\r
//\r
// A malloc "implementation" that you need to do a bit of configuring\r
// on to actually make a malloc.\r
//\r
// Usage:\r
//\r
// Define the preprocessor macros STB_MALLOC_IMPLEMENTATION\r
// in *one* .c/.cpp file before #including this file, e.g.:\r
//\r
//      #define STB_MALLOC_IMPLEMENTATION\r
//      #include "stb_malloc.h"\r
//\r
// Also optionally define the symbols listed in the section\r
// "Optional definitions" below.\r
//\r
//\r
// Features:\r
//   - TLSF for mid-sized allocations for O(1) allocation & freeing\r
//   - large allocations go to user-defined "system allocator"\r
//   - small allocations (<= pointer-sized) slab-allocated (no coalescing)\r
//   - no constraints on system allocator (e.g. page-aligned NOT required)\r
//   - multiple separate heaps which don't interfragment\r
//     - can free heap all-at-once without freeing individual allocations\r
//     - can free without specifying which heap it came from\r
//   - "thread"-cache\r
//     - must create one thread cache per thread per heap that you want cached\r
//     - you must create/manage any thread-local variables yourself\r
//   - almost every allocation offers a 16-bit user-defined "header" field\r
//   - overhead of 8 bytes in 32-bit, 16 bytes in 64-bit\r
//     - half that for allocations of 4 bytes in 32-bit, 8 bytes in 64-bit\r
//       - but they get no 16-bit user field\r
//     - plus overhead for allocations that aren't multiples of alignment\r
//   - all configuration at run-time\r
//     - choose per-heap minimum alignment at heap creation\r
//     - provide mutex handles or not for thread-safety / non-safety\r
//     - enable file/line recording on the fly (mixed in one heap)\r
//     - enable trailing guard bytes on the fly (mixed in one heap)\r
//     - enable variable-sized user-defined debug data on the fly (mixed)\r
//     - all on-the-fly-enables incur significant extra size in malloc header\r
//   - compile time configuration of platform features\r
//     - definition of a mutex handle and operations to lock/unlock it\r
//     - definition of a compare-and-swap for faster cross-thread frees\r
//\r
// Four possible models:\r
//     - create single-thread-only heaps without mutexes for fast performance\r
//     - create mutexed heap with per-thread thread cache for "global" malloc\r
//       that shares memory between threads\r
//     - create per-thread single-thread-only heap with cross-thread mutex for\r
//       fast "global" malloc without sharing memory (no false sharing)\r
//     - create M heaps for N threads with per-thread thread caches and\r
//       primary mutexes and cross-thread-mutexes\r
//\r
// Optional definitions:\r
//\r
//      STBM_MUTEX_HANDLE\r
//         The type of a handle to a mutex. It must be comparable against\r
//         0 to mean "is it null". These should be as-efficient-as-possible\r
//         process-private mutexes, not cross-process mutexes. If not\r
//         defined, allocation heaps are not thread-safe.\r
//\r
//      STBM_MUTEX_ACQUIRE\r
//         "Lock" a mutex handle. A single thread of stb_malloc will\r
//         never lock more than one mutex at a time, nor try to lock\r
//         the same mutex twice (they are not "reentrant"). Must be\r
//         defined if STBM_MUTEX_HANDLE is defined.\r
//\r
//      STBM_MUTEX_RELEASE\r
//         Release a previously acquired mutex, as above.\r
//\r
//      STBM_COMPARE_AND_SWAP32\r
//         Define a function that performs an atomic compare-and-swap on\r
//         a 32-bit value. (To be specified, since it's unimplemented so far.)\r
//         Only used if STBM_MUTEX_HANDLE is defined and a cross-thread\r
//         mutex is defined for a given heap.\r
//\r
//      STBM_UINT32\r
//      STBM_UINTPTR\r
//      STBM_POINTER_SIZE\r
//         If your compiler is C99, you do not need to define these.\r
//         Otherwise, stb_malloc will try default (32-bit) assignments\r
//         for them and validate them at compile time. If they are\r
//         incorrect, you will get compile errors, and will need to\r
//         define them yourself. STBM_POINTER_SIZE should be 32 or 64.\r
//\r
//     STBM_LOG2_32BIT(x)\r
//         Compute floor of log2 of a 32-bit number, or -1 if 0, i.e.\r
//         "31-count_leading_zeroes32(x)". This function is important to\r
//         high-performance of the allocator; it is used for computing block\r
//         "sizeclasses" and for TLSF O(1) scans. If you do not define it,\r
//         stb_malloc uses a small binary tree and a small table lookup.\r
//\r
//     STBM_ASSERT\r
//         If you don't define this, stb_malloc uses assert.h and assert().\r
//         This is the only C standard library function used by stb_malloc.\r
//\r
//     STBM_MEMSET\r
//         You can define this to 'memset' or your own memset replacement;\r
//         if not, stb_malloc uses a naive (possibly less efficient)\r
//         implementation.\r
//\r
//     STBM_MEMCPY\r
//         You can define this to 'memcpy' or your own memcpy replacement;\r
//         if not, stb_malloc uses a naive (probably inefficient)\r
//         implementation.\r
//\r
//     STBM_FAIL(s)\r
//         This function (which takes a char*) is called when there is an\r
//         extraordinary failure: a corrupt header is detected, guard bytes\r
//         are overwritten, or the API is used incorrectly. It is NOT called\r
//         if an allocation fails, which is considered a normal behavior.\r
//         If not defined, defaults to STBM_ASSERT(0).\r
//\r
//     STBM_CALLBACK\r
//         Defines an attribute applied to any callback functions, useful\r
//         for special linkage conventions.\r
//\r
//     STBM_NO_TYPEDEF\r
//         If defined, supresses the stbm_heap typedef for compilers that\r
//         don't like to see duplicate identical typedefs.\r
//\r
//     STBM_STATIC\r
//         If defined, declares all functions as static, so they can only\r
//         be accessed from the file that creates the implementation.\r
//\r
//     STBM_DEBUGCHECK\r
//         If defined, enables internal automatic calls to iggy_heap_check\r
//         to validate the heap after every operation (slow).\r
//\r
//\r
// On The Design Of stb_malloc.h\r
//\r
//   I've written many allocators (google for 'satoria smalloc' for the 1st).\r
//   stb_malloc.h is my most refined, the collision of seven central ideas:\r
//\r
//    - feature: multiple heaps, with heap-independent freeing\r
//    - design: overhead mostly proportional to used memory\r
//    - design: reuse-oriented API/implementation (i.e. stb_-library-style)\r
//    - design: all malloc options available without compile-time switches\r
//    - algorithm: TLSF (two-level segregated fit) for O(1) allocation\r
//    - algorithm: boundary-tag coalescing for O(1) frees\r
//    - algorithm: thread-caching inspired by TCMalloc\r
//\r
// Implementation information appears after the header section.\r
\r
#ifndef INCLUDE_STB_MALLOC_H\r
#define INCLUDE_STB_MALLOC_H\r
\r
// #define STBM_MUTEX_HANDLE to be the datatype of a pointer\r
// to a mutex or else the code will not be thread-safe\r
#ifndef STBM_MUTEX_HANDLE\r
// create a dummy pointer as the handle type\r
#define STBM_MUTEX_HANDLE void *\r
#define STBM__NO_MUTEX_HANDLE\r
#endif\r
\r
#ifdef STBM_STATIC\r
#define STBM__API static\r
#else\r
#define STBM__API extern\r
#endif\r
\r
#ifdef __cplusplus\r
extern "C" {\r
#endif\r
\r
#include <stdlib.h> // size_t\r
\r
typedef struct stbm_heap stbm_heap;\r
typedef struct stbm_tc stbm_tc;\r
\r
STBM__API void *stbm_alloc(stbm_tc *tc, stbm_heap *heap, size_t size, unsigned short userdata16);\r
// allocate a block of memory of 'size' bytes from the heap 'heap';\r
// userdata16 is an arbitrary 16-bit number stored in the allocation.\r
//\r
// For small blocks, the efficient storage format is only used\r
// if userdata16 == 0.\r
//\r
// if tc is not NULL, tc may not be accessed by any other thread at\r
// the same time, and the function may allocate from tc and cache\r
// additional blocks into tc\r
//\r
// If heap does not have an allocation mutex, then this function\r
// is allowed to manipulate it without taking any mutexes.\r
\r
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
// allocate a block of memory of 'size' bytes from the heap 'heap'\r
// which is aligned to a multiple of 'alignment' (which must be a\r
// power of two).\r
//\r
// userdata16 is an arbitrary 16-bit number stored in the allocation.\r
//\r
// if tc is not NULL, tc may not be accessed by any other thread at\r
// the same time, and the function may allocate from tc and cache\r
// additional blocks into tc\r
//\r
// If heap does not have an allocation mutex, then this function\r
// is allowed to manipulate it without taking any mutexes.\r
\r
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
// allocate a block of memory of 'size' bytes from the heap 'heap';\r
// userdata16 is an arbitrary 16-bit number stored in the allocation.\r
// an additional 'extra_debug_size' bytes are allocated which are\r
// separate from the main block, accessible through stbm_get_debug_data.\r
//\r
// if tc is not NULL, tc may not be accessed by any other thread at\r
// the same time, and the function may allocate from tc and cache\r
// additional blocks into tc\r
//\r
// If heap does not have an allocation mutex, then this function\r
// is allowed to manipulate it without taking any mutexes.\r
\r
STBM__API void *stbm_alloc_fileline(stbm_tc *tc, stbm_heap *heap, size_t size, unsigned short userdata16, char *file, int line);\r
// allocate a block of memory of 'size' bytes from the heap 'heap';\r
// userdata16 is an arbitrary 16-bit number stored in the allocation.\r
//\r
// if stbm_heapconfig_capture_file_line() has been enabled for this\r
// heap, then extra data is allocated in the block and the file/line\r
// are recorded; otherwise file/line are ignored\r
//\r
// For small blocks, the efficient storage format is only used\r
// if userdata16 == 0 and stbm_heapconfig_capture_file_line is not\r
// enabled.\r
//\r
// if tc is not NULL, tc may not be accessed by any other thread at\r
// the same time, and the function may allocate from tc and cache\r
// additional blocks into tc\r
//\r
// If heap does not have an allocation mutex, then this function\r
// is allowed to manipulate it without taking any mutexes.\r
\r
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
// allocate a block of memory of 'size' bytes from the heap 'heap'\r
// which is aligned to a multiple of 'alignment' (which must be a\r
// power of two).\r
//\r
// if stbm_heapconfig_capture_file_line() has been enabled for this\r
// heap, then extra data is allocated in the block and the file/line\r
// are recorded; otherwise file/line are ignored\r
//\r
// userdata16 is an arbitrary 16-bit number stored in the allocation.\r
//\r
// if tc is not NULL, tc may not be accessed by any other thread at\r
// the same time, and the function may allocate from tc and cache\r
// additional blocks into tc\r
//\r
// If heap does not have an allocation mutex, then this function\r
// is allowed to manipulate it without taking any mutexes.\r
\r
STBM__API void stbm_free(stbm_tc *tc, stbm_heap *preferred_heap, void *ptr);\r
// frees a previously-allocated block of memory addressed by 'ptr' from\r
// whichever heap it was allocated from.\r
//\r
// if tc is non-NULL and associated with the heap the ptr was\r
// allocated from, the block may be cached in tc.\r
//\r
// If the allocation came from preferred_heap, it will be properly freed\r
// into the general allocation pool for preferred_heap. Otherwise, it will\r
// be added to the cross-heap free list for the source heap, where it will\r
// only be fully freed the next time an allocation is made from that heap.\r
//\r
// If preferred_heap does not have an allocation mutex, then this function\r
// is allowed to manipulate preferred_heap without taking any mutexes.\r
\r
STBM__API void stbm_tc_flush(stbm_tc *tc, stbm_heap *preferred_heap, void *ptr);\r
// any pointers cached in tc are flushed back to the relevant heap, using\r
// the same locking logic described for stbm_free.\r
\r
STBM__API void *stbm_realloc(stbm_tc *tc, stbm_heap *heap, void *ptr, size_t newsize, unsigned short userdata16);\r
// "resizes" a block of memory, effectively equivalent to a call to stbm_alloc/stbm_alloc_tc\r
// and a call to stbm_free_tc/stbm_free, all using tc & heap.\r
//\r
// Note that this function will allocate from heap, so heap must be a "preferred"\r
// heap.\r
\r
STBM__API size_t stbm_get_allocation_size(void *ptr);\r
// query the available memory pointed to by the pointer\r
\r
STBM__API unsigned short stbm_get_userdata(void *ptr);\r
// query the arbitrary 16-bit identifier associated with the pointer\r
\r
STBM__API stbm_heap *stbm_get_heap(void *ptr);\r
// determine which heap it was allocated from\r
\r
STBM__API int stbm_get_fileline(void *ptr, char **file);\r
// get the stored file & line, or 0 if none stored\r
\r
STBM__API size_t stbm_get_debug_data(void *ptr, void **data);\r
// get a pointer to the extra data specified by stbm_alloc_debug\r
\r
#ifndef STBM_CALLBACK\r
#define STBM_CALLBACK\r
#endif\r
\r
typedef void *STBM_CALLBACK stbm_system_alloc(void *user_context, size_t size_requested, size_t *size_provided);\r
typedef void STBM_CALLBACK stbm_system_free(void *user_context, void *ptr, size_t size);\r
\r
#define STBM_TC_SIZEOF (sizeof(void *) * 2 * 32 + 64 + 64 + sizeof(void *) + 4 * 4 + 257 + sizeof(void *))\r
\r
STBM__API stbm_tc *stbm_tc_init(void *storage, size_t storage_bytes, stbm_heap *heap);\r
// initialize a new thread-cache referring to 'heap';\r
// storage_size_in_bytes must be as large as the minimum\r
// thread cache size.\r
\r
STBM__API void stbm_heap_free(stbm_heap *);\r
// Frees all system allocations made by this heap back to the\r
// system allocator. Any outstanding allocations from this heap\r
// become invalid. (For example, outstanding cached allocations\r
// in any corresponding stbm_tc's.) The heap itself becomes\r
// invalid (you must init it to use it again).\r
\r
STBM__API void *stbm_get_heap_user_context(stbm_heap *);\r
// get back the user context set in the creation\r
\r
typedef struct\r
{\r
    // You pass in allocators which are used to get additional storage.\r
    // If they are NULL, only the storage passed in above is used to satisfy\r
    // allocations, but also allocations larger than 1MB are NOT supported.\r
    stbm_system_alloc *system_alloc;\r
    stbm_system_free *system_free;\r
    void *user_context;\r
\r
    // All allocations have a default alignment of 8 (32-bit) or 16 (64-bit).\r
    // You can choose a higher power-of-two default alignment here.\r
    size_t minimum_alignment;\r
\r
    // If you do not set the following flag, then blocks which are smaller\r
    // than the requested minimum alignment may get a smaller alignment\r
    // (namely, the original default 8/16 alignment). If you set this flag,\r
    // then EVERY allocation, not matter how small, will get the alignment.\r
    // Currently this disables the smallest-block optimizations and will waste\r
    // lots of memory for those, but has no effect on intermediate sizes.\r
    int align_all_blocks_to_minimum;\r
\r
    // This mutex is used to prevent multiple threads from manipulating\r
    // the heap data structure atstbm_heap_free the same time. It should be non-NULL if\r
    // you will have multiple thread allocating from this heap. If only\r
    // one thread will be allocating from the heap it can be null.\r
    STBM_MUTEX_HANDLE allocation_mutex;\r
\r
    // If this mutex is provided, then frees which do not have the correct\r
    // heap passed to the free call will be put on a special 'crossthread'\r
    // free list. This prevents them from contending with threads that are\r
    // allocating using the allocation mutex, and also allows cross-thread\r
    // freeing even if there is no allocation mutex.\r
    STBM_MUTEX_HANDLE crossthread_free_mutex;\r
} stbm_heap_config;\r
\r
STBM__API stbm_heap *stbm_heap_init(void *storage, size_t storage_bytes, stbm_heap_config *hc);\r
// initialize a new heap from memory you provide which must be\r
// at least STBM_HEAP_SIZEOF; the data in the stbm_heap_config\r
// is copied, so you don't need to preserve it after this returns.\r
\r
#define STBM_HEAP_SIZEOF \\r
(\\r
/* alignment     */ 60 \\r
/* ct_free_stack */ + sizeof(void *) * 16 + 64 \\r
/* ct_free_list  */ + 64 \\r
/* alloc_lock    */ + sizeof(STBM_MUTEX_HANDLE) \\r
/* configuration */ + 3 * sizeof(size_t) + 6 * 4 \\r
/* system_alloc  */ + 5 * sizeof(void *) + 3 * sizeof(void *) \\r
/* stats         */ + 2 * 4 + 4 * sizeof(void *) \\r
/* small         */ + 2 * (6 * sizeof(void *) + 2 * 4) + sizeof(void *) \\r
/* medium        */ + 3 * 4 + 13 * 4 + 13 * 32 * sizeof(void *) + 4 * sizeof(void *)\\r
)\r
\r
STBM__API void stbm_heapconfig_set_trailing_guard_bytes(stbm_heap *heap, size_t num_bytes, unsigned char value);\r
STBM__API void stbm_heapconfig_capture_file_line(stbm_heap *heap, int enable_capture);\r
STBM__API void stbm_heapconfig_gather_full_stats(stbm_heap *heap);\r
STBM__API void stbm_heapconfig_set_largealloc_threshhold(stbm_heap *heap, size_t threshhold);\r
STBM__API void stbm_heapconfig_set_medium_chunk_size(stbm_heap *heap, size_t cur_size, size_t max_size);\r
STBM__API void stbm_heapconfig_set_small_chunk_size(stbm_heap *heap, size_t size);\r
STBM__API void stbm_heap_check(stbm_heap *heap);\r
\r
#define STBM_MEDIUM_CACHE_none 0\r
#define STBM_MEDIUM_CACHE_one 1\r
#define STBM_MEDIUM_CACHE_all 2\r
\r
STBM__API void stbm_heapconfig_cache_medium_chunks(stbm_heap *heap, int cache_mode);\r
\r
typedef struct\r
{\r
    void *ptr;\r
    unsigned short userdata;\r
    size_t size;\r
    int is_aligned;\r
    char *file;\r
    int line;\r
    void *extra_data;\r
    int extra_data_bytes;\r
} stbm_alloc_info;\r
\r
typedef void STBM_CALLBACK stbm_debug_iterate_func(void *usercontext, stbm_alloc_info *data);\r
\r
STBM__API void stbm_debug_iterate(stbm_heap *heap, stbm_debug_iterate_func *callback, void *user_context);\r
\r
#ifdef __cplusplus\r
}\r
#endif\r
\r
#endif //INCLUDE_STB_MALLOC_H\r