[73abe95] | 1 | // |
---|
[c4f68dc] | 2 | // Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo |
---|
| 3 | // |
---|
| 4 | // The contents of this file are covered under the licence agreement in the |
---|
| 5 | // file "LICENCE" distributed with Cforall. |
---|
[73abe95] | 6 | // |
---|
| 7 | // heap.c -- |
---|
| 8 | // |
---|
[c4f68dc] | 9 | // Author : Peter A. Buhr |
---|
| 10 | // Created On : Tue Dec 19 21:58:35 2017 |
---|
| 11 | // Last Modified By : Peter A. Buhr |
---|
[bcb14b5] | 12 | // Last Modified On : Thu Aug 23 06:11:44 2018 |
---|
| 13 | // Update Count : 511 |
---|
[73abe95] | 14 | // |
---|
[c4f68dc] | 15 | |
---|
| 16 | #include <unistd.h> // sbrk, sysconf |
---|
| 17 | #include <stdbool.h> // true, false |
---|
| 18 | #include <stdio.h> // snprintf, fileno |
---|
| 19 | #include <errno.h> // errno |
---|
| 20 | extern "C" { |
---|
| 21 | #include <sys/mman.h> // mmap, munmap |
---|
| 22 | } // extern "C" |
---|
| 23 | |
---|
[b6830d74] | 24 | // #comment TD : Many of these should be merged into math I believe |
---|
[bcb14b5] | 25 | #include "bits/align.hfa" // libPow2 |
---|
| 26 | #include "bits/defs.hfa" // likely, unlikely |
---|
| 27 | #include "bits/locks.hfa" // __spinlock_t |
---|
[73abe95] | 28 | #include "startup.hfa" // STARTUP_PRIORITY_MEMORY |
---|
[bcb14b5] | 29 | #include "stdlib.hfa" // bsearchl |
---|
[c4f68dc] | 30 | #include "malloc.h" |
---|
| 31 | |
---|
| 32 | |
---|
| 33 | enum { |
---|
| 34 | __CFA_DEFAULT_MMAP_START__ = (512 * 1024 + 1), |
---|
| 35 | __CFA_DEFAULT_HEAP_EXPANSION__ = (1 * 1024 * 1024), |
---|
| 36 | }; |
---|
| 37 | |
---|
| 38 | size_t default_mmap_start() __attribute__(( weak )) { |
---|
[b6830d74] | 39 | return __CFA_DEFAULT_MMAP_START__; |
---|
[c4f68dc] | 40 | } // default_mmap_start |
---|
| 41 | |
---|
| 42 | size_t default_heap_expansion() __attribute__(( weak )) { |
---|
[b6830d74] | 43 | return __CFA_DEFAULT_HEAP_EXPANSION__; |
---|
[c4f68dc] | 44 | } // default_heap_expansion |
---|
| 45 | |
---|
| 46 | |
---|
| 47 | // supported mallopt options |
---|
| 48 | #ifndef M_MMAP_THRESHOLD |
---|
| 49 | #define M_MMAP_THRESHOLD (-1) |
---|
| 50 | #endif // M_TOP_PAD |
---|
| 51 | #ifndef M_TOP_PAD |
---|
| 52 | #define M_TOP_PAD (-2) |
---|
| 53 | #endif // M_TOP_PAD |
---|
| 54 | |
---|
| 55 | #define FASTLOOKUP |
---|
| 56 | #define __STATISTICS__ |
---|
| 57 | |
---|
| 58 | #define SPINLOCK 0 |
---|
| 59 | #define LOCKFREE 1 |
---|
| 60 | #define BUCKETLOCK SPINLOCK |
---|
| 61 | #if BUCKETLOCK == LOCKFREE |
---|
| 62 | #include <uStackLF.h> |
---|
| 63 | #endif // LOCKFREE |
---|
| 64 | |
---|
[b6830d74] | 65 | // #comment TD : This defined is significantly different from the __ALIGN__ define from locks.hfa |
---|
[c4f68dc] | 66 | #define ALIGN 16 |
---|
| 67 | |
---|
| 68 | // enum { NoBucketSizes = 93, // number of buckets sizes |
---|
| 69 | // #ifdef FASTLOOKUP |
---|
| 70 | // LookupSizes = 65536, // number of fast lookup sizes |
---|
| 71 | // #endif // FASTLOOKUP |
---|
| 72 | // }; |
---|
| 73 | #define NoBucketSizes 93 // number of buckets sizes |
---|
| 74 | #ifdef FASTLOOKUP |
---|
| 75 | #define LookupSizes 65536 // number of fast lookup sizes |
---|
| 76 | #endif // FASTLOOKUP |
---|
| 77 | |
---|
| 78 | |
---|
[93c2e0a] | 79 | static bool traceHeap = false; |
---|
[d46ed6e] | 80 | |
---|
[93c2e0a] | 81 | inline bool traceHeap() { |
---|
[d46ed6e] | 82 | return traceHeap; |
---|
| 83 | } // traceHeap |
---|
| 84 | |
---|
[93c2e0a] | 85 | bool traceHeapOn() { |
---|
| 86 | bool temp = traceHeap; |
---|
[d46ed6e] | 87 | traceHeap = true; |
---|
| 88 | return temp; |
---|
| 89 | } // traceHeapOn |
---|
| 90 | |
---|
[93c2e0a] | 91 | bool traceHeapOff() { |
---|
| 92 | bool temp = traceHeap; |
---|
[d46ed6e] | 93 | traceHeap = false; |
---|
| 94 | return temp; |
---|
| 95 | } // traceHeapOff |
---|
| 96 | |
---|
| 97 | |
---|
[93c2e0a] | 98 | static bool checkFree = false; |
---|
[d46ed6e] | 99 | |
---|
[93c2e0a] | 100 | inline bool checkFree() { |
---|
[5d4fa18] | 101 | return checkFree; |
---|
| 102 | } // checkFree |
---|
| 103 | |
---|
[93c2e0a] | 104 | bool checkFreeOn() { |
---|
| 105 | bool temp = checkFree; |
---|
[5d4fa18] | 106 | checkFree = true; |
---|
| 107 | return temp; |
---|
| 108 | } // checkFreeOn |
---|
| 109 | |
---|
[93c2e0a] | 110 | bool checkFreeOff() { |
---|
| 111 | bool temp = checkFree; |
---|
[5d4fa18] | 112 | checkFree = false; |
---|
| 113 | return temp; |
---|
| 114 | } // checkFreeOff |
---|
| 115 | |
---|
| 116 | |
---|
[93c2e0a] | 117 | // static bool traceHeapTerm = false; |
---|
[5d4fa18] | 118 | |
---|
[93c2e0a] | 119 | // inline bool traceHeapTerm() { |
---|
[5d4fa18] | 120 | // return traceHeapTerm; |
---|
| 121 | // } // traceHeapTerm |
---|
[d46ed6e] | 122 | |
---|
[93c2e0a] | 123 | // bool traceHeapTermOn() { |
---|
| 124 | // bool temp = traceHeapTerm; |
---|
[5d4fa18] | 125 | // traceHeapTerm = true; |
---|
[d46ed6e] | 126 | // return temp; |
---|
[5d4fa18] | 127 | // } // traceHeapTermOn |
---|
[d46ed6e] | 128 | |
---|
[93c2e0a] | 129 | // bool traceHeapTermOff() { |
---|
| 130 | // bool temp = traceHeapTerm; |
---|
[5d4fa18] | 131 | // traceHeapTerm = false; |
---|
[d46ed6e] | 132 | // return temp; |
---|
[5d4fa18] | 133 | // } // traceHeapTermOff |
---|
[d46ed6e] | 134 | |
---|
| 135 | |
---|
[f0b3f51] | 136 | #ifdef __CFA_DEBUG__ |
---|
[93c2e0a] | 137 | static unsigned int allocFree; // running total of allocations minus frees |
---|
[d46ed6e] | 138 | |
---|
| 139 | static void checkUnfreed() { |
---|
[b6830d74] | 140 | if ( allocFree != 0 ) { |
---|
[d46ed6e] | 141 | // DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT. |
---|
| 142 | // char helpText[512]; |
---|
[93c2e0a] | 143 | // int len = snprintf( helpText, sizeof(helpText), "CFA warning (UNIX pid:%ld) : program terminating with %u(0x%x) bytes of storage allocated but not freed.\n" |
---|
[d46ed6e] | 144 | // "Possible cause is unfreed storage allocated by the program or system/library routines called from the program.\n", |
---|
[93c2e0a] | 145 | // (long int)getpid(), allocFree, allocFree ); // always print the UNIX pid |
---|
[d46ed6e] | 146 | // __cfaabi_dbg_bits_write( helpText, len ); |
---|
[b6830d74] | 147 | } // if |
---|
[d46ed6e] | 148 | } // checkUnfreed |
---|
| 149 | |
---|
| 150 | extern "C" { |
---|
[bcb14b5] | 151 | void heapAppStart() { // called by __cfaabi_appready_startup |
---|
| 152 | allocFree = 0; |
---|
| 153 | } // heapAppStart |
---|
| 154 | |
---|
| 155 | void heapAppStop() { // called by __cfaabi_appready_startdown |
---|
| 156 | fclose( stdin ); fclose( stdout ); |
---|
| 157 | checkUnfreed(); |
---|
| 158 | } // heapAppStop |
---|
[d46ed6e] | 159 | } // extern "C" |
---|
| 160 | #endif // __CFA_DEBUG__ |
---|
| 161 | |
---|
| 162 | |
---|
[c4f68dc] | 163 | struct HeapManager { |
---|
| 164 | // struct FreeHeader; // forward declaration |
---|
| 165 | |
---|
| 166 | struct Storage { |
---|
[bcb14b5] | 167 | struct Header { // header |
---|
[c4f68dc] | 168 | union Kind { |
---|
| 169 | struct RealHeader { |
---|
| 170 | union { |
---|
[bcb14b5] | 171 | struct { // 4-byte word => 8-byte header, 8-byte word => 16-byte header |
---|
[f0b3f51] | 172 | #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ && __SIZEOF_POINTER__ == 4 |
---|
[c4f68dc] | 173 | uint32_t padding; // unused, force home/blocksize to overlay alignment in fake header |
---|
[bcb14b5] | 174 | #endif // __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ && __SIZEOF_POINTER__ == 4 |
---|
[c4f68dc] | 175 | |
---|
| 176 | union { |
---|
| 177 | // FreeHeader * home; // allocated block points back to home locations (must overlay alignment) |
---|
| 178 | void * home; // allocated block points back to home locations (must overlay alignment) |
---|
| 179 | size_t blockSize; // size for munmap (must overlay alignment) |
---|
| 180 | #if BUCKLOCK == SPINLOCK |
---|
| 181 | Storage * next; // freed block points next freed block of same size |
---|
| 182 | #endif // SPINLOCK |
---|
| 183 | }; |
---|
| 184 | |
---|
[f0b3f51] | 185 | #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ && __SIZEOF_POINTER__ == 4 |
---|
[c4f68dc] | 186 | uint32_t padding; // unused, force home/blocksize to overlay alignment in fake header |
---|
[bcb14b5] | 187 | #endif // __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ && __SIZEOF_POINTER__ == 4 |
---|
[c4f68dc] | 188 | }; |
---|
[bcb14b5] | 189 | // future code |
---|
[c4f68dc] | 190 | #if BUCKLOCK == LOCKFREE |
---|
| 191 | Stack<Storage>::Link next; // freed block points next freed block of same size (double-wide) |
---|
| 192 | #endif // LOCKFREE |
---|
| 193 | }; |
---|
[93c2e0a] | 194 | } real; // RealHeader |
---|
[c4f68dc] | 195 | struct FakeHeader { |
---|
| 196 | #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ |
---|
| 197 | uint32_t alignment; // low-order bits of home/blockSize used for tricks |
---|
[f0b3f51] | 198 | #endif // __ORDER_LITTLE_ENDIAN__ |
---|
[c4f68dc] | 199 | |
---|
| 200 | uint32_t offset; |
---|
| 201 | |
---|
| 202 | #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ |
---|
| 203 | uint32_t alignment; // low-order bits of home/blockSize used for tricks |
---|
[f0b3f51] | 204 | #endif // __ORDER_BIG_ENDIAN__ |
---|
[93c2e0a] | 205 | } fake; // FakeHeader |
---|
| 206 | } kind; // Kind |
---|
[bcb14b5] | 207 | } header; // Header |
---|
| 208 | char pad[ALIGN - sizeof( Header )]; |
---|
| 209 | char data[0]; // storage |
---|
[c4f68dc] | 210 | }; // Storage |
---|
| 211 | |
---|
| 212 | static_assert( ALIGN >= sizeof( Storage ), "ALIGN < sizeof( Storage )" ); |
---|
| 213 | |
---|
| 214 | struct FreeHeader { |
---|
| 215 | #if BUCKLOCK == SPINLOCK |
---|
[bcb14b5] | 216 | __spinlock_t lock; // must be first field for alignment |
---|
| 217 | Storage * freeList; |
---|
[c4f68dc] | 218 | #elif BUCKLOCK == LOCKFREE |
---|
[bcb14b5] | 219 | // future code |
---|
| 220 | StackLF<Storage> freeList; |
---|
[c4f68dc] | 221 | #else |
---|
[bcb14b5] | 222 | #error undefined lock type for bucket lock |
---|
[c4f68dc] | 223 | #endif // SPINLOCK |
---|
[bcb14b5] | 224 | size_t blockSize; // size of allocations on this list |
---|
[c4f68dc] | 225 | }; // FreeHeader |
---|
| 226 | |
---|
| 227 | // must be first fields for alignment |
---|
| 228 | __spinlock_t extlock; // protects allocation-buffer extension |
---|
| 229 | FreeHeader freeLists[NoBucketSizes]; // buckets for different allocation sizes |
---|
| 230 | |
---|
| 231 | void * heapBegin; // start of heap |
---|
| 232 | void * heapEnd; // logical end of heap |
---|
| 233 | size_t heapRemaining; // amount of storage not allocated in the current chunk |
---|
| 234 | }; // HeapManager |
---|
| 235 | |
---|
[5d4fa18] | 236 | static inline size_t getKey( const HeapManager.FreeHeader & freeheader ) { return freeheader.blockSize; } |
---|
| 237 | // statically allocated variables => zero filled. |
---|
| 238 | |
---|
| 239 | |
---|
| 240 | static size_t pageSize; // architecture pagesize |
---|
| 241 | static size_t heapExpand; // sbrk advance |
---|
| 242 | static size_t mmapStart; // cross over point for mmap |
---|
| 243 | static unsigned int maxBucketsUsed; // maximum number of buckets in use |
---|
| 244 | |
---|
| 245 | // Powers of 2 are common allocation sizes, so make powers of 2 generate the minimum required size. |
---|
[bcb14b5] | 246 | static const unsigned int bucketSizes[NoBucketSizes] @= { // different bucket sizes |
---|
[b6830d74] | 247 | 16, 32, 48, 64, |
---|
| 248 | 64 + sizeof(HeapManager.Storage), 96, 112, 128, 128 + sizeof(HeapManager.Storage), 160, 192, 224, |
---|
| 249 | 256 + sizeof(HeapManager.Storage), 320, 384, 448, 512 + sizeof(HeapManager.Storage), 640, 768, 896, |
---|
| 250 | 1_024 + sizeof(HeapManager.Storage), 1_536, 2_048 + sizeof(HeapManager.Storage), 2_560, 3_072, 3_584, 4_096 + sizeof(HeapManager.Storage), 6_144, |
---|
| 251 | 8_192 + sizeof(HeapManager.Storage), 9_216, 10_240, 11_264, 12_288, 13_312, 14_336, 15_360, |
---|
| 252 | 16_384 + sizeof(HeapManager.Storage), 18_432, 20_480, 22_528, 24_576, 26_624, 28_672, 30_720, |
---|
| 253 | 32_768 + sizeof(HeapManager.Storage), 36_864, 40_960, 45_056, 49_152, 53_248, 57_344, 61_440, |
---|
| 254 | 65_536 + sizeof(HeapManager.Storage), 73_728, 81_920, 90_112, 98_304, 106_496, 114_688, 122_880, |
---|
| 255 | 131_072 + sizeof(HeapManager.Storage), 147_456, 163_840, 180_224, 196_608, 212_992, 229_376, 245_760, |
---|
| 256 | 262_144 + sizeof(HeapManager.Storage), 294_912, 327_680, 360_448, 393_216, 425_984, 458_752, 491_520, |
---|
| 257 | 524_288 + sizeof(HeapManager.Storage), 655_360, 786_432, 917_504, 1_048_576 + sizeof(HeapManager.Storage), 1_179_648, 1_310_720, 1_441_792, |
---|
| 258 | 1_572_864, 1_703_936, 1_835_008, 1_966_080, 2_097_152 + sizeof(HeapManager.Storage), 2_621_440, 3_145_728, 3_670_016, |
---|
| 259 | 4_194_304 + sizeof(HeapManager.Storage) |
---|
[5d4fa18] | 260 | }; |
---|
| 261 | #ifdef FASTLOOKUP |
---|
| 262 | static unsigned char lookup[LookupSizes]; // O(1) lookup for small sizes |
---|
| 263 | #endif // FASTLOOKUP |
---|
| 264 | static int mmapFd = -1; // fake or actual fd for anonymous file |
---|
| 265 | |
---|
| 266 | |
---|
| 267 | #ifdef __CFA_DEBUG__ |
---|
[93c2e0a] | 268 | static bool heapBoot = 0; // detect recursion during boot |
---|
[5d4fa18] | 269 | #endif // __CFA_DEBUG__ |
---|
| 270 | static HeapManager heapManager __attribute__(( aligned (128) )) @= {}; // size of cache line to prevent false sharing |
---|
| 271 | |
---|
[b6830d74] | 272 | // #comment TD : The return type of this function should be commented |
---|
[93c2e0a] | 273 | static inline bool setMmapStart( size_t value ) { |
---|
[bcb14b5] | 274 | if ( value < pageSize || bucketSizes[NoBucketSizes - 1] < value ) return true; |
---|
[b6830d74] | 275 | mmapStart = value; // set global |
---|
| 276 | |
---|
| 277 | // find the closest bucket size less than or equal to the mmapStart size |
---|
| 278 | maxBucketsUsed = bsearchl( (unsigned int)mmapStart, bucketSizes, NoBucketSizes ); // binary search |
---|
| 279 | assert( maxBucketsUsed < NoBucketSizes ); // subscript failure ? |
---|
| 280 | assert( mmapStart <= bucketSizes[maxBucketsUsed] ); // search failure ? |
---|
| 281 | return false; |
---|
[d46ed6e] | 282 | } // setMmapStart |
---|
| 283 | |
---|
| 284 | |
---|
| 285 | static void ?{}( HeapManager & manager ) with ( manager ) { |
---|
[b6830d74] | 286 | pageSize = sysconf( _SC_PAGESIZE ); |
---|
[73abe95] | 287 | |
---|
[b6830d74] | 288 | for ( unsigned int i = 0; i < NoBucketSizes; i += 1 ) { // initialize the free lists |
---|
[d46ed6e] | 289 | freeLists[i].blockSize = bucketSizes[i]; |
---|
[b6830d74] | 290 | } // for |
---|
[d46ed6e] | 291 | |
---|
| 292 | #ifdef FASTLOOKUP |
---|
[b6830d74] | 293 | unsigned int idx = 0; |
---|
| 294 | for ( unsigned int i = 0; i < LookupSizes; i += 1 ) { |
---|
[d46ed6e] | 295 | if ( i > bucketSizes[idx] ) idx += 1; |
---|
| 296 | lookup[i] = idx; |
---|
[b6830d74] | 297 | } // for |
---|
[d46ed6e] | 298 | #endif // FASTLOOKUP |
---|
| 299 | |
---|
[b6830d74] | 300 | if ( setMmapStart( default_mmap_start() ) ) { |
---|
[d46ed6e] | 301 | abort( "HeapManager : internal error, mmap start initialization failure." ); |
---|
[b6830d74] | 302 | } // if |
---|
| 303 | heapExpand = default_heap_expansion(); |
---|
[d46ed6e] | 304 | |
---|
[b6830d74] | 305 | char * End = (char *)sbrk( 0 ); |
---|
| 306 | sbrk( (char *)libCeiling( (long unsigned int)End, libAlign() ) - End ); // move start of heap to multiple of alignment |
---|
| 307 | heapBegin = heapEnd = sbrk( 0 ); // get new start point |
---|
[bcb14b5] | 308 | } // HeapManager |
---|
[d46ed6e] | 309 | |
---|
| 310 | |
---|
| 311 | static void ^?{}( HeapManager & ) { |
---|
| 312 | #ifdef __STATISTICS__ |
---|
[5d4fa18] | 313 | // if ( traceHeapTerm() ) { |
---|
[d46ed6e] | 314 | // printStats(); |
---|
[5d4fa18] | 315 | // if ( checkfree() ) checkFree( heapManager, true ); |
---|
[d46ed6e] | 316 | // } // if |
---|
| 317 | #endif // __STATISTICS__ |
---|
[bcb14b5] | 318 | } // ~HeapManager |
---|
[d46ed6e] | 319 | |
---|
| 320 | |
---|
| 321 | static void memory_startup( void ) __attribute__(( constructor( STARTUP_PRIORITY_MEMORY ) )); |
---|
| 322 | void memory_startup( void ) { |
---|
| 323 | #ifdef __CFA_DEBUG__ |
---|
[bcb14b5] | 324 | if ( unlikely( heapBoot ) ) { // check for recursion during system boot |
---|
[d46ed6e] | 325 | // DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT. |
---|
| 326 | abort( "boot() : internal error, recursively invoked during system boot." ); |
---|
| 327 | } // if |
---|
| 328 | heapBoot = true; |
---|
| 329 | #endif // __CFA_DEBUG__ |
---|
[c4f68dc] | 330 | |
---|
[bcb14b5] | 331 | assert( heapManager.heapBegin == 0 ); // always perform check, done once |
---|
[d46ed6e] | 332 | heapManager{}; |
---|
| 333 | } // memory_startup |
---|
[c4f68dc] | 334 | |
---|
[d46ed6e] | 335 | static void memory_shutdown( void ) __attribute__(( destructor( STARTUP_PRIORITY_MEMORY ) )); |
---|
| 336 | void memory_shutdown( void ) { |
---|
| 337 | ^heapManager{}; |
---|
| 338 | } // memory_shutdown |
---|
| 339 | |
---|
[c4f68dc] | 340 | |
---|
| 341 | #ifdef __STATISTICS__ |
---|
[d46ed6e] | 342 | static unsigned long long int mmap_storage; // heap statistics counters |
---|
[c4f68dc] | 343 | static unsigned int mmap_calls; |
---|
| 344 | static unsigned long long int munmap_storage; |
---|
| 345 | static unsigned int munmap_calls; |
---|
| 346 | static unsigned long long int sbrk_storage; |
---|
| 347 | static unsigned int sbrk_calls; |
---|
| 348 | static unsigned long long int malloc_storage; |
---|
| 349 | static unsigned int malloc_calls; |
---|
| 350 | static unsigned long long int free_storage; |
---|
| 351 | static unsigned int free_calls; |
---|
| 352 | static unsigned long long int calloc_storage; |
---|
| 353 | static unsigned int calloc_calls; |
---|
| 354 | static unsigned long long int memalign_storage; |
---|
| 355 | static unsigned int memalign_calls; |
---|
| 356 | static unsigned long long int cmemalign_storage; |
---|
| 357 | static unsigned int cmemalign_calls; |
---|
| 358 | static unsigned long long int realloc_storage; |
---|
| 359 | static unsigned int realloc_calls; |
---|
[d46ed6e] | 360 | |
---|
| 361 | static int statfd; // statistics file descriptor (changed by malloc_stats_fd) |
---|
[c4f68dc] | 362 | |
---|
| 363 | |
---|
| 364 | // Use "write" because streams may be shutdown when calls are made. |
---|
[d46ed6e] | 365 | static void printStats() { |
---|
[b6830d74] | 366 | char helpText[512]; |
---|
[93c2e0a] | 367 | __cfaabi_dbg_bits_print_buffer( helpText, sizeof(helpText), |
---|
[bcb14b5] | 368 | "\nHeap statistics:\n" |
---|
| 369 | " malloc: calls %u / storage %llu\n" |
---|
| 370 | " calloc: calls %u / storage %llu\n" |
---|
| 371 | " memalign: calls %u / storage %llu\n" |
---|
| 372 | " cmemalign: calls %u / storage %llu\n" |
---|
| 373 | " realloc: calls %u / storage %llu\n" |
---|
| 374 | " free: calls %u / storage %llu\n" |
---|
| 375 | " mmap: calls %u / storage %llu\n" |
---|
| 376 | " munmap: calls %u / storage %llu\n" |
---|
| 377 | " sbrk: calls %u / storage %llu\n", |
---|
| 378 | malloc_calls, malloc_storage, |
---|
| 379 | calloc_calls, calloc_storage, |
---|
| 380 | memalign_calls, memalign_storage, |
---|
| 381 | cmemalign_calls, cmemalign_storage, |
---|
| 382 | realloc_calls, realloc_storage, |
---|
| 383 | free_calls, free_storage, |
---|
| 384 | mmap_calls, mmap_storage, |
---|
| 385 | munmap_calls, munmap_storage, |
---|
| 386 | sbrk_calls, sbrk_storage |
---|
[c4f68dc] | 387 | ); |
---|
[d46ed6e] | 388 | } // printStats |
---|
[c4f68dc] | 389 | |
---|
[bcb14b5] | 390 | static int printStatsXML( FILE * stream ) { // see malloc_info |
---|
[b6830d74] | 391 | char helpText[512]; |
---|
| 392 | int len = snprintf( helpText, sizeof(helpText), |
---|
[c4f68dc] | 393 | "<malloc version=\"1\">\n" |
---|
| 394 | "<heap nr=\"0\">\n" |
---|
| 395 | "<sizes>\n" |
---|
| 396 | "</sizes>\n" |
---|
| 397 | "<total type=\"malloc\" count=\"%u\" size=\"%llu\"/>\n" |
---|
| 398 | "<total type=\"calloc\" count=\"%u\" size=\"%llu\"/>\n" |
---|
| 399 | "<total type=\"memalign\" count=\"%u\" size=\"%llu\"/>\n" |
---|
| 400 | "<total type=\"cmemalign\" count=\"%u\" size=\"%llu\"/>\n" |
---|
| 401 | "<total type=\"realloc\" count=\"%u\" size=\"%llu\"/>\n" |
---|
| 402 | "<total type=\"free\" count=\"%u\" size=\"%llu\"/>\n" |
---|
| 403 | "<total type=\"mmap\" count=\"%u\" size=\"%llu\"/>\n" |
---|
| 404 | "<total type=\"munmap\" count=\"%u\" size=\"%llu\"/>\n" |
---|
| 405 | "<total type=\"sbrk\" count=\"%u\" size=\"%llu\"/>\n" |
---|
| 406 | "</malloc>", |
---|
| 407 | malloc_calls, malloc_storage, |
---|
| 408 | calloc_calls, calloc_storage, |
---|
| 409 | memalign_calls, memalign_storage, |
---|
| 410 | cmemalign_calls, cmemalign_storage, |
---|
| 411 | realloc_calls, realloc_storage, |
---|
| 412 | free_calls, free_storage, |
---|
| 413 | mmap_calls, mmap_storage, |
---|
| 414 | munmap_calls, munmap_storage, |
---|
| 415 | sbrk_calls, sbrk_storage |
---|
| 416 | ); |
---|
[b6830d74] | 417 | return write( fileno( stream ), helpText, len ); // -1 => error |
---|
[d46ed6e] | 418 | } // printStatsXML |
---|
[c4f68dc] | 419 | #endif // __STATISTICS__ |
---|
| 420 | |
---|
[b6830d74] | 421 | // #comment TD : Is this the samething as Out-of-Memory? |
---|
[c4f68dc] | 422 | static inline void noMemory() { |
---|
[b6830d74] | 423 | abort( "Heap memory exhausted at %zu bytes.\n" |
---|
[bcb14b5] | 424 | "Possible cause is very large memory allocation and/or large amount of unfreed storage allocated by the program or system/library routines.", |
---|
| 425 | ((char *)(sbrk( 0 )) - (char *)(heapManager.heapBegin)) ); |
---|
[c4f68dc] | 426 | } // noMemory |
---|
| 427 | |
---|
| 428 | |
---|
| 429 | static inline void checkAlign( size_t alignment ) { |
---|
[b6830d74] | 430 | if ( alignment < sizeof(void *) || ! libPow2( alignment ) ) { |
---|
[c4f68dc] | 431 | abort( "Alignment %zu for memory allocation is less than sizeof(void *) and/or not a power of 2.", alignment ); |
---|
[b6830d74] | 432 | } // if |
---|
[c4f68dc] | 433 | } // checkAlign |
---|
| 434 | |
---|
| 435 | |
---|
[93c2e0a] | 436 | static inline bool setHeapExpand( size_t value ) { |
---|
[bcb14b5] | 437 | if ( heapExpand < pageSize ) return true; |
---|
[b6830d74] | 438 | heapExpand = value; |
---|
| 439 | return false; |
---|
[c4f68dc] | 440 | } // setHeapExpand |
---|
| 441 | |
---|
| 442 | |
---|
[93c2e0a] | 443 | static inline void checkHeader( bool check, const char * name, void * addr ) { |
---|
[b6830d74] | 444 | if ( unlikely( check ) ) { // bad address ? |
---|
[c4f68dc] | 445 | abort( "Attempt to %s storage %p with address outside the heap.\n" |
---|
[bcb14b5] | 446 | "Possible cause is duplicate free on same block or overwriting of memory.", |
---|
| 447 | name, addr ); |
---|
[b6830d74] | 448 | } // if |
---|
[c4f68dc] | 449 | } // checkHeader |
---|
| 450 | |
---|
[b6830d74] | 451 | // #comment TD : function should be commented and/or have a more evocative name |
---|
| 452 | // this isn't either a check or a constructor which is what I would expect this function to be |
---|
[c4f68dc] | 453 | static inline void fakeHeader( HeapManager.Storage.Header *& header, size_t & size, size_t & alignment ) { |
---|
[b6830d74] | 454 | if ( unlikely( (header->kind.fake.alignment & 1) == 1 ) ) { // fake header ? |
---|
[c4f68dc] | 455 | size_t offset = header->kind.fake.offset; |
---|
| 456 | alignment = header->kind.fake.alignment & -2; // remove flag from value |
---|
| 457 | #ifdef __CFA_DEBUG__ |
---|
| 458 | checkAlign( alignment ); // check alignment |
---|
| 459 | #endif // __CFA_DEBUG__ |
---|
| 460 | header = (HeapManager.Storage.Header *)((char *)header - offset); |
---|
[b6830d74] | 461 | } // if |
---|
[c4f68dc] | 462 | } // fakeHeader |
---|
| 463 | |
---|
[b6830d74] | 464 | // #comment TD : Why is this a define |
---|
[c4f68dc] | 465 | #define headerAddr( addr ) ((HeapManager.Storage.Header *)( (char *)addr - sizeof(HeapManager.Storage) )) |
---|
| 466 | |
---|
[93c2e0a] | 467 | static inline bool headers( const char * name, void * addr, HeapManager.Storage.Header *& header, HeapManager.FreeHeader *& freeElem, size_t & size, size_t & alignment ) with ( heapManager ) { |
---|
[b6830d74] | 468 | header = headerAddr( addr ); |
---|
[c4f68dc] | 469 | |
---|
[b6830d74] | 470 | if ( unlikely( heapEnd < addr ) ) { // mmapped ? |
---|
[c4f68dc] | 471 | fakeHeader( header, size, alignment ); |
---|
| 472 | size = header->kind.real.blockSize & -3; // mmap size |
---|
| 473 | return true; |
---|
[b6830d74] | 474 | } // if |
---|
[c4f68dc] | 475 | |
---|
| 476 | #ifdef __CFA_DEBUG__ |
---|
[bcb14b5] | 477 | checkHeader( addr < heapBegin || header < (HeapManager.Storage.Header *)heapBegin, name, addr ); // bad low address ? |
---|
[c4f68dc] | 478 | #endif // __CFA_DEBUG__ |
---|
[b6830d74] | 479 | |
---|
| 480 | // #comment TD : This code looks weird... |
---|
| 481 | // It's called as the first statement of both branches of the last if, with the same parameters in all cases |
---|
| 482 | |
---|
[bcb14b5] | 483 | // header may be safe to dereference |
---|
| 484 | fakeHeader( header, size, alignment ); |
---|
[c4f68dc] | 485 | #ifdef __CFA_DEBUG__ |
---|
[bcb14b5] | 486 | checkHeader( header < (HeapManager.Storage.Header *)heapBegin || (HeapManager.Storage.Header *)heapEnd < header, name, addr ); // bad address ? (offset could be + or -) |
---|
[c4f68dc] | 487 | #endif // __CFA_DEBUG__ |
---|
| 488 | |
---|
[bcb14b5] | 489 | freeElem = (HeapManager.FreeHeader *)((size_t)header->kind.real.home & -3); |
---|
[c4f68dc] | 490 | #ifdef __CFA_DEBUG__ |
---|
[bcb14b5] | 491 | if ( freeElem < &freeLists[0] || &freeLists[NoBucketSizes] <= freeElem ) { |
---|
| 492 | abort( "Attempt to %s storage %p with corrupted header.\n" |
---|
| 493 | "Possible cause is duplicate free on same block or overwriting of header information.", |
---|
| 494 | name, addr ); |
---|
| 495 | } // if |
---|
[c4f68dc] | 496 | #endif // __CFA_DEBUG__ |
---|
[bcb14b5] | 497 | size = freeElem->blockSize; |
---|
| 498 | return false; |
---|
[c4f68dc] | 499 | } // headers |
---|
| 500 | |
---|
| 501 | |
---|
| 502 | static inline void * extend( size_t size ) with ( heapManager ) { |
---|
[b6830d74] | 503 | lock( extlock __cfaabi_dbg_ctx2 ); |
---|
| 504 | ptrdiff_t rem = heapRemaining - size; |
---|
| 505 | if ( rem < 0 ) { |
---|
[c4f68dc] | 506 | // If the size requested is bigger than the current remaining storage, increase the size of the heap. |
---|
| 507 | |
---|
| 508 | size_t increase = libCeiling( size > heapExpand ? size : heapExpand, libAlign() ); |
---|
| 509 | if ( sbrk( increase ) == (void *)-1 ) { |
---|
| 510 | unlock( extlock ); |
---|
| 511 | errno = ENOMEM; |
---|
| 512 | return 0; |
---|
| 513 | } // if |
---|
[bcb14b5] | 514 | #ifdef __STATISTICS__ |
---|
[c4f68dc] | 515 | sbrk_calls += 1; |
---|
| 516 | sbrk_storage += increase; |
---|
[bcb14b5] | 517 | #endif // __STATISTICS__ |
---|
| 518 | #ifdef __CFA_DEBUG__ |
---|
[c4f68dc] | 519 | // Set new memory to garbage so subsequent uninitialized usages might fail. |
---|
| 520 | memset( (char *)heapEnd + heapRemaining, '\377', increase ); |
---|
[bcb14b5] | 521 | #endif // __CFA_DEBUG__ |
---|
[c4f68dc] | 522 | rem = heapRemaining + increase - size; |
---|
[b6830d74] | 523 | } // if |
---|
[c4f68dc] | 524 | |
---|
[b6830d74] | 525 | HeapManager.Storage * block = (HeapManager.Storage *)heapEnd; |
---|
| 526 | heapRemaining = rem; |
---|
| 527 | heapEnd = (char *)heapEnd + size; |
---|
| 528 | unlock( extlock ); |
---|
| 529 | return block; |
---|
[c4f68dc] | 530 | } // extend |
---|
| 531 | |
---|
| 532 | |
---|
| 533 | static inline void * doMalloc( size_t size ) with ( heapManager ) { |
---|
[b6830d74] | 534 | HeapManager.Storage * block; |
---|
[c4f68dc] | 535 | |
---|
[b6830d74] | 536 | // Look up size in the size list. Make sure the user request includes space for the header that must be allocated |
---|
| 537 | // along with the block and is a multiple of the alignment size. |
---|
[c4f68dc] | 538 | |
---|
[b6830d74] | 539 | size_t tsize = size + sizeof(HeapManager.Storage); |
---|
| 540 | if ( likely( tsize < mmapStart ) ) { // small size => sbrk |
---|
[c4f68dc] | 541 | HeapManager.FreeHeader * freeElem = |
---|
| 542 | #ifdef FASTLOOKUP |
---|
| 543 | tsize < LookupSizes ? &freeLists[lookup[tsize]] : |
---|
| 544 | #endif // FASTLOOKUP |
---|
| 545 | bsearchl( tsize, freeLists, (size_t)maxBucketsUsed ); // binary search |
---|
| 546 | assert( freeElem <= &freeLists[maxBucketsUsed] ); // subscripting error ? |
---|
| 547 | assert( tsize <= freeElem->blockSize ); // search failure ? |
---|
| 548 | tsize = freeElem->blockSize; // total space needed for request |
---|
| 549 | |
---|
| 550 | // Spin until the lock is acquired for this particular size of block. |
---|
| 551 | |
---|
| 552 | #if defined( SPINLOCK ) |
---|
[bcb14b5] | 553 | lock( freeElem->lock __cfaabi_dbg_ctx2 ); |
---|
| 554 | block = freeElem->freeList; // remove node from stack |
---|
[c4f68dc] | 555 | #else |
---|
[bcb14b5] | 556 | block = freeElem->freeList.pop(); |
---|
[c4f68dc] | 557 | #endif // SPINLOCK |
---|
| 558 | if ( unlikely( block == 0 ) ) { // no free block ? |
---|
| 559 | #if defined( SPINLOCK ) |
---|
| 560 | unlock( freeElem->lock ); |
---|
| 561 | #endif // SPINLOCK |
---|
[bcb14b5] | 562 | |
---|
[c4f68dc] | 563 | // Freelist for that size was empty, so carve it out of the heap if there's enough left, or get some more |
---|
| 564 | // and then carve it off. |
---|
| 565 | |
---|
| 566 | block = (HeapManager.Storage *)extend( tsize ); // mutual exclusion on call |
---|
[bcb14b5] | 567 | if ( unlikely( block == 0 ) ) return 0; |
---|
[c4f68dc] | 568 | #if defined( SPINLOCK ) |
---|
| 569 | } else { |
---|
| 570 | freeElem->freeList = block->header.kind.real.next; |
---|
| 571 | unlock( freeElem->lock ); |
---|
| 572 | #endif // SPINLOCK |
---|
| 573 | } // if |
---|
| 574 | |
---|
| 575 | block->header.kind.real.home = freeElem; // pointer back to free list of apropriate size |
---|
[bcb14b5] | 576 | } else { // large size => mmap |
---|
[c4f68dc] | 577 | tsize = libCeiling( tsize, pageSize ); // must be multiple of page size |
---|
| 578 | #ifdef __STATISTICS__ |
---|
[bcb14b5] | 579 | __atomic_add_fetch( &mmap_calls, 1, __ATOMIC_SEQ_CST ); |
---|
| 580 | __atomic_add_fetch( &mmap_storage, tsize, __ATOMIC_SEQ_CST ); |
---|
[c4f68dc] | 581 | #endif // __STATISTICS__ |
---|
| 582 | block = (HeapManager.Storage *)mmap( 0, tsize, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, mmapFd, 0 ); |
---|
| 583 | if ( block == (HeapManager.Storage *)MAP_FAILED ) { |
---|
| 584 | // Do not call strerror( errno ) as it may call malloc. |
---|
| 585 | abort( "(HeapManager &)0x%p.doMalloc() : internal error, mmap failure, size:%zu error:%d.", &heapManager, tsize, errno ); |
---|
| 586 | } // if |
---|
[bcb14b5] | 587 | #ifdef __CFA_DEBUG__ |
---|
[c4f68dc] | 588 | // Set new memory to garbage so subsequent uninitialized usages might fail. |
---|
| 589 | memset( block, '\377', tsize ); |
---|
[bcb14b5] | 590 | #endif // __CFA_DEBUG__ |
---|
[c4f68dc] | 591 | block->header.kind.real.blockSize = tsize; // storage size for munmap |
---|
[bcb14b5] | 592 | } // if |
---|
[c4f68dc] | 593 | |
---|
[bcb14b5] | 594 | void * area = &(block->data); // adjust off header to user bytes |
---|
[c4f68dc] | 595 | |
---|
| 596 | #ifdef __CFA_DEBUG__ |
---|
[bcb14b5] | 597 | assert( ((uintptr_t)area & (libAlign() - 1)) == 0 ); // minimum alignment ? |
---|
| 598 | __atomic_add_fetch( &allocFree, tsize, __ATOMIC_SEQ_CST ); |
---|
| 599 | if ( traceHeap() ) { |
---|
| 600 | enum { BufferSize = 64 }; |
---|
| 601 | char helpText[BufferSize]; |
---|
| 602 | int len = snprintf( helpText, BufferSize, "%p = Malloc( %zu ) (allocated %zu)\n", area, size, tsize ); |
---|
| 603 | // int len = snprintf( helpText, BufferSize, "Malloc %p %zu\n", area, size ); |
---|
| 604 | __cfaabi_dbg_bits_write( helpText, len ); |
---|
| 605 | } // if |
---|
[c4f68dc] | 606 | #endif // __CFA_DEBUG__ |
---|
| 607 | |
---|
[b6830d74] | 608 | return area; |
---|
[c4f68dc] | 609 | } // doMalloc |
---|
| 610 | |
---|
| 611 | |
---|
| 612 | static inline void doFree( void * addr ) with ( heapManager ) { |
---|
| 613 | #ifdef __CFA_DEBUG__ |
---|
[bcb14b5] | 614 | if ( unlikely( heapManager.heapBegin == 0 ) ) { |
---|
| 615 | abort( "doFree( %p ) : internal error, called before heap is initialized.", addr ); |
---|
| 616 | } // if |
---|
[c4f68dc] | 617 | #endif // __CFA_DEBUG__ |
---|
| 618 | |
---|
[b6830d74] | 619 | HeapManager.Storage.Header * header; |
---|
| 620 | HeapManager.FreeHeader * freeElem; |
---|
| 621 | size_t size, alignment; // not used (see realloc) |
---|
[c4f68dc] | 622 | |
---|
[b6830d74] | 623 | if ( headers( "free", addr, header, freeElem, size, alignment ) ) { // mmapped ? |
---|
[c4f68dc] | 624 | #ifdef __STATISTICS__ |
---|
[bcb14b5] | 625 | __atomic_add_fetch( &munmap_calls, 1, __ATOMIC_SEQ_CST ); |
---|
| 626 | __atomic_add_fetch( &munmap_storage, size, __ATOMIC_SEQ_CST ); |
---|
[c4f68dc] | 627 | #endif // __STATISTICS__ |
---|
| 628 | if ( munmap( header, size ) == -1 ) { |
---|
| 629 | #ifdef __CFA_DEBUG__ |
---|
| 630 | abort( "Attempt to deallocate storage %p not allocated or with corrupt header.\n" |
---|
[bcb14b5] | 631 | "Possible cause is invalid pointer.", |
---|
| 632 | addr ); |
---|
[c4f68dc] | 633 | #endif // __CFA_DEBUG__ |
---|
| 634 | } // if |
---|
[bcb14b5] | 635 | } else { |
---|
[c4f68dc] | 636 | #ifdef __CFA_DEBUG__ |
---|
[bcb14b5] | 637 | // Set free memory to garbage so subsequent usages might fail. |
---|
| 638 | memset( ((HeapManager.Storage *)header)->data, '\377', freeElem->blockSize - sizeof( HeapManager.Storage ) ); |
---|
[c4f68dc] | 639 | #endif // __CFA_DEBUG__ |
---|
| 640 | |
---|
| 641 | #ifdef __STATISTICS__ |
---|
[bcb14b5] | 642 | free_storage += size; |
---|
[c4f68dc] | 643 | #endif // __STATISTICS__ |
---|
| 644 | #if defined( SPINLOCK ) |
---|
[bcb14b5] | 645 | lock( freeElem->lock __cfaabi_dbg_ctx2 ); // acquire spin lock |
---|
| 646 | header->kind.real.next = freeElem->freeList; // push on stack |
---|
| 647 | freeElem->freeList = (HeapManager.Storage *)header; |
---|
| 648 | unlock( freeElem->lock ); // release spin lock |
---|
[c4f68dc] | 649 | #else |
---|
[bcb14b5] | 650 | freeElem->freeList.push( *(HeapManager.Storage *)header ); |
---|
[c4f68dc] | 651 | #endif // SPINLOCK |
---|
[bcb14b5] | 652 | } // if |
---|
[c4f68dc] | 653 | |
---|
| 654 | #ifdef __CFA_DEBUG__ |
---|
[bcb14b5] | 655 | __atomic_add_fetch( &allocFree, -size, __ATOMIC_SEQ_CST ); |
---|
| 656 | if ( traceHeap() ) { |
---|
| 657 | char helpText[64]; |
---|
| 658 | int len = snprintf( helpText, sizeof(helpText), "Free( %p ) size:%zu\n", addr, size ); |
---|
| 659 | __cfaabi_dbg_bits_write( helpText, len ); |
---|
| 660 | } // if |
---|
[c4f68dc] | 661 | #endif // __CFA_DEBUG__ |
---|
| 662 | } // doFree |
---|
| 663 | |
---|
| 664 | |
---|
[5d4fa18] | 665 | size_t checkFree( HeapManager & manager ) with ( manager ) { |
---|
[b6830d74] | 666 | size_t total = 0; |
---|
[c4f68dc] | 667 | #ifdef __STATISTICS__ |
---|
[bcb14b5] | 668 | __cfaabi_dbg_bits_acquire(); |
---|
| 669 | __cfaabi_dbg_bits_print_nolock( "\nBin lists (bin size : free blocks on list)\n" ); |
---|
[c4f68dc] | 670 | #endif // __STATISTICS__ |
---|
[b6830d74] | 671 | for ( unsigned int i = 0; i < maxBucketsUsed; i += 1 ) { |
---|
[d46ed6e] | 672 | size_t size = freeLists[i].blockSize; |
---|
| 673 | #ifdef __STATISTICS__ |
---|
| 674 | unsigned int N = 0; |
---|
| 675 | #endif // __STATISTICS__ |
---|
[b6830d74] | 676 | |
---|
[d46ed6e] | 677 | #if defined( SPINLOCK ) |
---|
| 678 | for ( HeapManager.Storage * p = freeLists[i].freeList; p != 0; p = p->header.kind.real.next ) { |
---|
| 679 | #else |
---|
| 680 | for ( HeapManager.Storage * p = freeLists[i].freeList.top(); p != 0; p = p->header.kind.real.next.top ) { |
---|
| 681 | #endif // SPINLOCK |
---|
| 682 | total += size; |
---|
| 683 | #ifdef __STATISTICS__ |
---|
| 684 | N += 1; |
---|
| 685 | #endif // __STATISTICS__ |
---|
[b6830d74] | 686 | } // for |
---|
| 687 | |
---|
[d46ed6e] | 688 | #ifdef __STATISTICS__ |
---|
[bcb14b5] | 689 | __cfaabi_dbg_bits_print_nolock( "%7zu, %-7u ", size, N ); |
---|
| 690 | if ( (i + 1) % 8 == 0 ) __cfaabi_dbg_bits_print_nolock( "\n" ); |
---|
[d46ed6e] | 691 | #endif // __STATISTICS__ |
---|
| 692 | } // for |
---|
| 693 | #ifdef __STATISTICS__ |
---|
[bcb14b5] | 694 | __cfaabi_dbg_bits_print_nolock( "\ntotal free blocks:%zu\n", total ); |
---|
| 695 | __cfaabi_dbg_bits_release(); |
---|
[d46ed6e] | 696 | #endif // __STATISTICS__ |
---|
| 697 | return (char *)heapEnd - (char *)heapBegin - total; |
---|
| 698 | } // checkFree |
---|
[c4f68dc] | 699 | |
---|
[bcb14b5] | 700 | |
---|
| 701 | static inline void * mallocNoStats( size_t size ) { // necessary for malloc statistics |
---|
[f0b3f51] | 702 | assert( heapManager.heapBegin != 0 ); |
---|
[b6830d74] | 703 | void * area = doMalloc( size ); |
---|
| 704 | if ( unlikely( area == 0 ) ) errno = ENOMEM; // POSIX |
---|
| 705 | return area; |
---|
[bcb14b5] | 706 | } // mallocNoStats |
---|
[c4f68dc] | 707 | |
---|
| 708 | |
---|
[bcb14b5] | 709 | static inline void * memalignNoStats( size_t alignment, size_t size ) { // necessary for malloc statistics |
---|
| 710 | #ifdef __CFA_DEBUG__ |
---|
[b6830d74] | 711 | checkAlign( alignment ); // check alignment |
---|
[bcb14b5] | 712 | #endif // __CFA_DEBUG__ |
---|
[c4f68dc] | 713 | |
---|
[b6830d74] | 714 | // if alignment <= default alignment, do normal malloc as two headers are unnecessary |
---|
[bcb14b5] | 715 | if ( unlikely( alignment <= libAlign() ) ) return mallocNoStats( size ); |
---|
[b6830d74] | 716 | |
---|
| 717 | // Allocate enough storage to guarantee an address on the alignment boundary, and sufficient space before it for |
---|
| 718 | // administrative storage. NOTE, WHILE THERE ARE 2 HEADERS, THE FIRST ONE IS IMPLICITLY CREATED BY DOMALLOC. |
---|
| 719 | // .-------------v-----------------v----------------v----------, |
---|
| 720 | // | Real Header | ... padding ... | Fake Header | data ... | |
---|
| 721 | // `-------------^-----------------^-+--------------^----------' |
---|
| 722 | // |<--------------------------------' offset/align |<-- alignment boundary |
---|
| 723 | |
---|
| 724 | // subtract libAlign() because it is already the minimum alignment |
---|
| 725 | // add sizeof(Storage) for fake header |
---|
[bcb14b5] | 726 | // #comment TD : this is the only place that calls doMalloc without calling mallocNoStats, why ? |
---|
[b6830d74] | 727 | char * area = (char *)doMalloc( size + alignment - libAlign() + sizeof(HeapManager.Storage) ); |
---|
[bcb14b5] | 728 | if ( unlikely( area == 0 ) ) return area; |
---|
[b6830d74] | 729 | |
---|
| 730 | // address in the block of the "next" alignment address |
---|
| 731 | char * user = (char *)libCeiling( (uintptr_t)(area + sizeof(HeapManager.Storage)), alignment ); |
---|
| 732 | |
---|
| 733 | // address of header from malloc |
---|
| 734 | HeapManager.Storage.Header * realHeader = headerAddr( area ); |
---|
| 735 | // address of fake header * before* the alignment location |
---|
| 736 | HeapManager.Storage.Header * fakeHeader = headerAddr( user ); |
---|
| 737 | // SKULLDUGGERY: insert the offset to the start of the actual storage block and remember alignment |
---|
| 738 | fakeHeader->kind.fake.offset = (char *)fakeHeader - (char *)realHeader; |
---|
| 739 | // SKULLDUGGERY: odd alignment imples fake header |
---|
| 740 | fakeHeader->kind.fake.alignment = alignment | 1; |
---|
| 741 | |
---|
| 742 | return user; |
---|
[bcb14b5] | 743 | } // memalignNoStats |
---|
[c4f68dc] | 744 | |
---|
| 745 | |
---|
| 746 | extern "C" { |
---|
[bcb14b5] | 747 | // The malloc() function allocates size bytes and returns a pointer to the allocated memory. The memory is not |
---|
| 748 | // initialized. If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be |
---|
| 749 | // successfully passed to free(). |
---|
[b6830d74] | 750 | void * malloc( size_t size ) { |
---|
[c4f68dc] | 751 | #ifdef __STATISTICS__ |
---|
[bcb14b5] | 752 | __atomic_add_fetch( &malloc_calls, 1, __ATOMIC_SEQ_CST ); |
---|
| 753 | __atomic_add_fetch( &malloc_storage, size, __ATOMIC_SEQ_CST ); |
---|
[c4f68dc] | 754 | #endif // __STATISTICS__ |
---|
| 755 | |
---|
[bcb14b5] | 756 | return mallocNoStats( size ); |
---|
| 757 | } // malloc |
---|
[c4f68dc] | 758 | |
---|
[bcb14b5] | 759 | // The calloc() function allocates memory for an array of nmemb elements of size bytes each and returns a pointer to |
---|
| 760 | // the allocated memory. The memory is set to zero. If nmemb or size is 0, then calloc() returns either NULL, or a |
---|
| 761 | // unique pointer value that can later be successfully passed to free(). |
---|
| 762 | void * calloc( size_t noOfElems, size_t elemSize ) { |
---|
[c4f68dc] | 763 | size_t size = noOfElems * elemSize; |
---|
| 764 | #ifdef __STATISTICS__ |
---|
[bcb14b5] | 765 | __atomic_add_fetch( &calloc_calls, 1, __ATOMIC_SEQ_CST ); |
---|
| 766 | __atomic_add_fetch( &calloc_storage, size, __ATOMIC_SEQ_CST ); |
---|
[c4f68dc] | 767 | #endif // __STATISTICS__ |
---|
| 768 | |
---|
[bcb14b5] | 769 | char * area = (char *)mallocNoStats( size ); |
---|
| 770 | if ( unlikely( area == 0 ) ) return 0; |
---|
[b6830d74] | 771 | |
---|
[c4f68dc] | 772 | HeapManager.Storage.Header * header; |
---|
| 773 | HeapManager.FreeHeader * freeElem; |
---|
| 774 | size_t asize, alignment; |
---|
[93c2e0a] | 775 | bool mapped __attribute__(( unused )) = headers( "calloc", area, header, freeElem, asize, alignment ); |
---|
[c4f68dc] | 776 | #ifndef __CFA_DEBUG__ |
---|
[73abe95] | 777 | // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero. |
---|
[c4f68dc] | 778 | if ( ! mapped ) |
---|
| 779 | #endif // __CFA_DEBUG__ |
---|
| 780 | memset( area, '\0', asize - sizeof(HeapManager.Storage) ); // set to zeros |
---|
[b6830d74] | 781 | |
---|
[bcb14b5] | 782 | header->kind.real.blockSize |= 2; // mark as zero filled |
---|
[c4f68dc] | 783 | return area; |
---|
[bcb14b5] | 784 | } // calloc |
---|
[c4f68dc] | 785 | |
---|
[b6830d74] | 786 | // #comment TD : Document this function |
---|
| 787 | void * cmemalign( size_t alignment, size_t noOfElems, size_t elemSize ) { |
---|
[c4f68dc] | 788 | size_t size = noOfElems * elemSize; |
---|
| 789 | #ifdef __STATISTICS__ |
---|
[bcb14b5] | 790 | __atomic_add_fetch( &cmemalign_calls, 1, __ATOMIC_SEQ_CST ); |
---|
| 791 | __atomic_add_fetch( &cmemalign_storage, size, __ATOMIC_SEQ_CST ); |
---|
[c4f68dc] | 792 | #endif // __STATISTICS__ |
---|
| 793 | |
---|
[bcb14b5] | 794 | char * area = (char *)memalignNoStats( alignment, size ); |
---|
| 795 | if ( unlikely( area == 0 ) ) return 0; |
---|
[c4f68dc] | 796 | HeapManager.Storage.Header * header; |
---|
| 797 | HeapManager.FreeHeader * freeElem; |
---|
| 798 | size_t asize; |
---|
[93c2e0a] | 799 | bool mapped __attribute__(( unused )) = headers( "cmemalign", area, header, freeElem, asize, alignment ); |
---|
[c4f68dc] | 800 | #ifndef __CFA_DEBUG__ |
---|
[73abe95] | 801 | // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero. |
---|
[c4f68dc] | 802 | if ( ! mapped ) |
---|
[bcb14b5] | 803 | #endif // __CFA_DEBUG__ |
---|
[c4f68dc] | 804 | memset( area, '\0', asize - ( (char *)area - (char *)header ) ); // set to zeros |
---|
| 805 | header->kind.real.blockSize |= 2; // mark as zero filled |
---|
| 806 | |
---|
| 807 | return area; |
---|
[bcb14b5] | 808 | } // cmemalign |
---|
| 809 | |
---|
| 810 | // The realloc() function changes the size of the memory block pointed to by ptr to size bytes. The contents will be |
---|
| 811 | // unchanged in the range from the start of the region up to the minimum of the old and new sizes. If the new size |
---|
| 812 | // is larger than the old size, the added memory will not be initialized. If ptr is NULL, then the call is |
---|
| 813 | // equivalent to malloc(size), for all values of size; if size is equal to zero, and ptr is not NULL, then the call |
---|
| 814 | // is equivalent to free(ptr). Unless ptr is NULL, it must have been returned by an earlier call to malloc(), |
---|
| 815 | // calloc() or realloc(). If the area pointed to was moved, a free(ptr) is done. |
---|
| 816 | void * realloc( void * addr, size_t size ) { |
---|
[c4f68dc] | 817 | #ifdef __STATISTICS__ |
---|
[bcb14b5] | 818 | __atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST ); |
---|
[c4f68dc] | 819 | #endif // __STATISTICS__ |
---|
| 820 | |
---|
[bcb14b5] | 821 | if ( unlikely( addr == 0 ) ) return mallocNoStats( size ); // special cases |
---|
| 822 | if ( unlikely( size == 0 ) ) { free( addr ); return 0; } |
---|
[c4f68dc] | 823 | |
---|
| 824 | HeapManager.Storage.Header * header; |
---|
| 825 | HeapManager.FreeHeader * freeElem; |
---|
| 826 | size_t asize, alignment = 0; |
---|
| 827 | headers( "realloc", addr, header, freeElem, asize, alignment ); |
---|
| 828 | |
---|
| 829 | size_t usize = asize - ( (char *)addr - (char *)header ); // compute the amount of user storage in the block |
---|
| 830 | if ( usize >= size ) { // already sufficient storage |
---|
| 831 | // This case does not result in a new profiler entry because the previous one still exists and it must match with |
---|
| 832 | // the free for this memory. Hence, this realloc does not appear in the profiler output. |
---|
| 833 | return addr; |
---|
| 834 | } // if |
---|
| 835 | |
---|
| 836 | #ifdef __STATISTICS__ |
---|
[bcb14b5] | 837 | __atomic_add_fetch( &realloc_storage, size, __ATOMIC_SEQ_CST ); |
---|
[c4f68dc] | 838 | #endif // __STATISTICS__ |
---|
| 839 | |
---|
| 840 | void * area; |
---|
| 841 | if ( unlikely( alignment != 0 ) ) { // previous request memalign? |
---|
| 842 | area = memalign( alignment, size ); // create new area |
---|
| 843 | } else { |
---|
[bcb14b5] | 844 | area = mallocNoStats( size ); // create new area |
---|
[c4f68dc] | 845 | } // if |
---|
[bcb14b5] | 846 | if ( unlikely( area == 0 ) ) return 0; |
---|
[c4f68dc] | 847 | if ( unlikely( header->kind.real.blockSize & 2 ) ) { // previous request zero fill (calloc/cmemalign) ? |
---|
| 848 | assert( (header->kind.real.blockSize & 1) == 0 ); |
---|
[93c2e0a] | 849 | bool mapped __attribute__(( unused )) = headers( "realloc", area, header, freeElem, asize, alignment ); |
---|
[c4f68dc] | 850 | #ifndef __CFA_DEBUG__ |
---|
[73abe95] | 851 | // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero. |
---|
[c4f68dc] | 852 | if ( ! mapped ) |
---|
[bcb14b5] | 853 | #endif // __CFA_DEBUG__ |
---|
[c4f68dc] | 854 | memset( (char *)area + usize, '\0', asize - ( (char *)area - (char *)header ) - usize ); // zero-fill back part |
---|
| 855 | header->kind.real.blockSize |= 2; // mark new request as zero fill |
---|
| 856 | } // if |
---|
| 857 | memcpy( area, addr, usize ); // copy bytes |
---|
| 858 | free( addr ); |
---|
| 859 | return area; |
---|
[b6830d74] | 860 | } // realloc |
---|
[c4f68dc] | 861 | |
---|
| 862 | |
---|
[bcb14b5] | 863 | // The obsolete function memalign() allocates size bytes and returns a pointer to the allocated memory. The memory |
---|
| 864 | // address will be a multiple of alignment, which must be a power of two. |
---|
| 865 | void * memalign( size_t alignment, size_t size ) { |
---|
[c4f68dc] | 866 | #ifdef __STATISTICS__ |
---|
| 867 | __atomic_add_fetch( &memalign_calls, 1, __ATOMIC_SEQ_CST ); |
---|
| 868 | __atomic_add_fetch( &memalign_storage, size, __ATOMIC_SEQ_CST ); |
---|
| 869 | #endif // __STATISTICS__ |
---|
| 870 | |
---|
[bcb14b5] | 871 | void * area = memalignNoStats( alignment, size ); |
---|
[c4f68dc] | 872 | |
---|
| 873 | return area; |
---|
[bcb14b5] | 874 | } // memalign |
---|
[c4f68dc] | 875 | |
---|
[bcb14b5] | 876 | // The function aligned_alloc() is the same as memalign(), except for the added restriction that size should be a |
---|
| 877 | // multiple of alignment. |
---|
[b6830d74] | 878 | void * aligned_alloc( size_t alignment, size_t size ) { |
---|
[c4f68dc] | 879 | return memalign( alignment, size ); |
---|
[b6830d74] | 880 | } // aligned_alloc |
---|
[c4f68dc] | 881 | |
---|
| 882 | |
---|
[bcb14b5] | 883 | // The function posix_memalign() allocates size bytes and places the address of the allocated memory in *memptr. The |
---|
| 884 | // address of the allocated memory will be a multiple of alignment, which must be a power of two and a multiple of |
---|
| 885 | // sizeof(void *). If size is 0, then posix_memalign() returns either NULL, or a unique pointer value that can later |
---|
| 886 | // be successfully passed to free(3). |
---|
[b6830d74] | 887 | int posix_memalign( void ** memptr, size_t alignment, size_t size ) { |
---|
[bcb14b5] | 888 | if ( alignment < sizeof(void *) || ! libPow2( alignment ) ) return EINVAL; // check alignment |
---|
[c4f68dc] | 889 | * memptr = memalign( alignment, size ); |
---|
[bcb14b5] | 890 | if ( unlikely( * memptr == 0 ) ) return ENOMEM; |
---|
[c4f68dc] | 891 | return 0; |
---|
[b6830d74] | 892 | } // posix_memalign |
---|
[c4f68dc] | 893 | |
---|
[bcb14b5] | 894 | // The obsolete function valloc() allocates size bytes and returns a pointer to the allocated memory. The memory |
---|
| 895 | // address will be a multiple of the page size. It is equivalent to memalign(sysconf(_SC_PAGESIZE),size). |
---|
[b6830d74] | 896 | void * valloc( size_t size ) { |
---|
[c4f68dc] | 897 | return memalign( pageSize, size ); |
---|
[b6830d74] | 898 | } // valloc |
---|
[c4f68dc] | 899 | |
---|
| 900 | |
---|
[bcb14b5] | 901 | // The free() function frees the memory space pointed to by ptr, which must have been returned by a previous call to |
---|
| 902 | // malloc(), calloc() or realloc(). Otherwise, or if free(ptr) has already been called before, undefined behavior |
---|
| 903 | // occurs. If ptr is NULL, no operation is performed. |
---|
[b6830d74] | 904 | void free( void * addr ) { |
---|
[c4f68dc] | 905 | #ifdef __STATISTICS__ |
---|
[bcb14b5] | 906 | __atomic_add_fetch( &free_calls, 1, __ATOMIC_SEQ_CST ); |
---|
[c4f68dc] | 907 | #endif // __STATISTICS__ |
---|
| 908 | |
---|
[b6830d74] | 909 | // #comment TD : To decrease nesting I would but the special case in the |
---|
| 910 | // else instead, plus it reads more naturally to have the |
---|
| 911 | // short / normal case instead |
---|
[c4f68dc] | 912 | if ( unlikely( addr == 0 ) ) { // special case |
---|
[d46ed6e] | 913 | #ifdef __CFA_DEBUG__ |
---|
[bcb14b5] | 914 | if ( traceHeap() ) { |
---|
| 915 | #define nullmsg "Free( 0x0 ) size:0\n" |
---|
| 916 | // Do not debug print free( 0 ), as it can cause recursive entry from sprintf. |
---|
| 917 | __cfaabi_dbg_bits_write( nullmsg, sizeof(nullmsg) - 1 ); |
---|
| 918 | } // if |
---|
[d46ed6e] | 919 | #endif // __CFA_DEBUG__ |
---|
[c4f68dc] | 920 | return; |
---|
| 921 | } // exit |
---|
| 922 | |
---|
| 923 | doFree( addr ); |
---|
[b6830d74] | 924 | } // free |
---|
[93c2e0a] | 925 | |
---|
[bcb14b5] | 926 | // The mallopt() function adjusts parameters that control the behavior of the memory-allocation functions (see |
---|
| 927 | // malloc(3)). The param argument specifies the parameter to be modified, and value specifies the new value for that |
---|
[b6830d74] | 928 | // parameter. |
---|
[bcb14b5] | 929 | int mallopt( int option, int value ) { |
---|
[c4f68dc] | 930 | choose( option ) { |
---|
[bcb14b5] | 931 | case M_TOP_PAD: |
---|
| 932 | if ( setHeapExpand( value ) ) fallthru default; |
---|
| 933 | case M_MMAP_THRESHOLD: |
---|
| 934 | if ( setMmapStart( value ) ) fallthru default; |
---|
| 935 | default: |
---|
| 936 | // #comment TD : 1 for unsopported feels wrong |
---|
| 937 | return 1; // success, or unsupported |
---|
[c4f68dc] | 938 | } // switch |
---|
| 939 | return 0; // error |
---|
[b6830d74] | 940 | } // mallopt |
---|
[c4f68dc] | 941 | |
---|
[bcb14b5] | 942 | // The malloc_trim() function attempts to release free memory at the top of the heap (by calling sbrk(2) with a |
---|
| 943 | // suitable argument). |
---|
[c4f68dc] | 944 | int malloc_trim( size_t ) { |
---|
| 945 | return 0; // => impossible to release memory |
---|
| 946 | } // malloc_trim |
---|
| 947 | |
---|
[bcb14b5] | 948 | // The malloc_usable_size() function returns the number of usable bytes in the block pointed to by ptr, a pointer to |
---|
| 949 | // a block of memory allocated by malloc(3) or a related function. |
---|
| 950 | size_t malloc_usable_size( void * addr ) { |
---|
| 951 | if ( unlikely( addr == 0 ) ) return 0; // null allocation has 0 size |
---|
[b6830d74] | 952 | |
---|
[c4f68dc] | 953 | HeapManager.Storage.Header * header; |
---|
| 954 | HeapManager.FreeHeader * freeElem; |
---|
| 955 | size_t size, alignment; |
---|
| 956 | |
---|
| 957 | headers( "malloc_usable_size", addr, header, freeElem, size, alignment ); |
---|
| 958 | size_t usize = size - ( (char *)addr - (char *)header ); // compute the amount of user storage in the block |
---|
| 959 | return usize; |
---|
[b6830d74] | 960 | } // malloc_usable_size |
---|
[c4f68dc] | 961 | |
---|
| 962 | |
---|
[bcb14b5] | 963 | // The malloc_alignment() function returns the alignment of the allocation. |
---|
[b6830d74] | 964 | size_t malloc_alignment( void * addr ) { |
---|
[bcb14b5] | 965 | if ( unlikely( addr == 0 ) ) return libAlign(); // minimum alignment |
---|
[c4f68dc] | 966 | HeapManager.Storage.Header * header = (HeapManager.Storage.Header *)( (char *)addr - sizeof(HeapManager.Storage) ); |
---|
| 967 | if ( (header->kind.fake.alignment & 1) == 1 ) { // fake header ? |
---|
| 968 | return header->kind.fake.alignment & -2; // remove flag from value |
---|
| 969 | } else { |
---|
| 970 | return libAlign (); // minimum alignment |
---|
| 971 | } // if |
---|
[bcb14b5] | 972 | } // malloc_alignment |
---|
[c4f68dc] | 973 | |
---|
| 974 | |
---|
[bcb14b5] | 975 | // The malloc_zero_fill() function returns true if the allocation is zero filled, i.e., initially allocated by calloc(). |
---|
[b6830d74] | 976 | bool malloc_zero_fill( void * addr ) { |
---|
[bcb14b5] | 977 | if ( unlikely( addr == 0 ) ) return false; // null allocation is not zero fill |
---|
[b6830d74] | 978 | |
---|
[c4f68dc] | 979 | HeapManager.Storage.Header * header = (HeapManager.Storage.Header *)( (char *)addr - sizeof(HeapManager.Storage) ); |
---|
| 980 | if ( (header->kind.fake.alignment & 1) == 1 ) { // fake header ? |
---|
| 981 | header = (HeapManager.Storage.Header *)((char *)header - header->kind.fake.offset); |
---|
| 982 | } // if |
---|
| 983 | return (header->kind.real.blockSize & 2) != 0; // zero filled (calloc/cmemalign) ? |
---|
[bcb14b5] | 984 | } // malloc_zero_fill |
---|
[c4f68dc] | 985 | |
---|
| 986 | |
---|
[bcb14b5] | 987 | // The malloc_stats() function prints (on default standard error) statistics about memory allocated by malloc(3) and |
---|
| 988 | // related functions. |
---|
[b6830d74] | 989 | void malloc_stats( void ) { |
---|
[c4f68dc] | 990 | #ifdef __STATISTICS__ |
---|
[bcb14b5] | 991 | printStats(); |
---|
| 992 | if ( checkFree() ) checkFree( heapManager ); |
---|
[c4f68dc] | 993 | #endif // __STATISTICS__ |
---|
[bcb14b5] | 994 | } // malloc_stats |
---|
[c4f68dc] | 995 | |
---|
[bcb14b5] | 996 | // The malloc_stats_fd() function changes the file descripter where malloc_stats() writes the statistics. |
---|
| 997 | int malloc_stats_fd( int fd ) { |
---|
[c4f68dc] | 998 | #ifdef __STATISTICS__ |
---|
[bcb14b5] | 999 | int temp = statfd; |
---|
| 1000 | statfd = fd; |
---|
| 1001 | return temp; |
---|
[c4f68dc] | 1002 | #else |
---|
[bcb14b5] | 1003 | return -1; |
---|
[c4f68dc] | 1004 | #endif // __STATISTICS__ |
---|
[bcb14b5] | 1005 | } // malloc_stats_fd |
---|
[c4f68dc] | 1006 | |
---|
[bcb14b5] | 1007 | // The malloc_info() function exports an XML string that describes the current state of the memory-allocation |
---|
| 1008 | // implementation in the caller. The string is printed on the file stream stream. The exported string includes |
---|
| 1009 | // information about all arenas (see malloc(3)). |
---|
[c4f68dc] | 1010 | int malloc_info( int options, FILE * stream ) { |
---|
[d46ed6e] | 1011 | return printStatsXML( stream ); |
---|
[c4f68dc] | 1012 | } // malloc_info |
---|
| 1013 | |
---|
| 1014 | |
---|
[bcb14b5] | 1015 | // The malloc_get_state() function records the current state of all malloc(3) internal bookkeeping variables (but |
---|
| 1016 | // not the actual contents of the heap or the state of malloc_hook(3) functions pointers). The state is recorded in |
---|
| 1017 | // a system-dependent opaque data structure dynamically allocated via malloc(3), and a pointer to that data |
---|
| 1018 | // structure is returned as the function result. (It is the caller's responsibility to free(3) this memory.) |
---|
[c4f68dc] | 1019 | void * malloc_get_state( void ) { |
---|
[bcb14b5] | 1020 | return 0; // unsupported |
---|
[c4f68dc] | 1021 | } // malloc_get_state |
---|
| 1022 | |
---|
[bcb14b5] | 1023 | |
---|
| 1024 | // The malloc_set_state() function restores the state of all malloc(3) internal bookkeeping variables to the values |
---|
| 1025 | // recorded in the opaque data structure pointed to by state. |
---|
[c4f68dc] | 1026 | int malloc_set_state( void * ptr ) { |
---|
[bcb14b5] | 1027 | return 0; // unsupported |
---|
[c4f68dc] | 1028 | } // malloc_set_state |
---|
| 1029 | } // extern "C" |
---|
| 1030 | |
---|
| 1031 | |
---|
| 1032 | // Local Variables: // |
---|
| 1033 | // tab-width: 4 // |
---|
| 1034 | // compile-command: "cfa -nodebug -O2 heap.c" // |
---|
| 1035 | // End: // |
---|