Changes in libcfa/src/heap.cfa [433905a:69ec0fb]
- File:
-
- 1 edited
-
libcfa/src/heap.cfa (modified) (10 diffs)
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/heap.cfa
r433905a r69ec0fb 10 10 // Created On : Tue Dec 19 21:58:35 2017 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Fri Apr 29 19:05:03202213 // Update Count : 11 6712 // Last Modified On : Mon Apr 25 18:51:36 2022 13 // Update Count : 1147 14 14 // 15 15 … … 87 87 88 88 89 //####################### Heap Statistics #################### 89 #ifdef __CFA_DEBUG__ 90 static size_t allocUnfreed; // running total of allocations minus frees 91 92 static void prtUnfreed() { 93 if ( allocUnfreed != 0 ) { 94 // DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT. 95 char helpText[512]; 96 int len = snprintf( helpText, sizeof(helpText), "CFA warning (UNIX pid:%ld) : program terminating with %zu(0x%zx) bytes of storage allocated but not freed.\n" 97 "Possible cause is unfreed storage allocated by the program or system/library routines called from the program.\n", 98 (long int)getpid(), allocUnfreed, allocUnfreed ); // always print the UNIX pid 99 __cfaabi_bits_write( STDERR_FILENO, helpText, len ); // print debug/nodebug 100 } // if 101 } // prtUnfreed 102 103 extern int cfa_main_returned; // from interpose.cfa 104 extern "C" { 105 void heapAppStart() { // called by __cfaabi_appready_startup 106 allocUnfreed = 0; 107 } // heapAppStart 108 109 void heapAppStop() { // called by __cfaabi_appready_startdown 110 fclose( stdin ); fclose( stdout ); 111 if ( cfa_main_returned ) prtUnfreed(); // do not check unfreed storage if exit called 112 } // heapAppStop 113 } // extern "C" 114 #endif // __CFA_DEBUG__ 115 116 117 // statically allocated variables => zero filled. 118 static size_t heapExpand; // sbrk advance 119 static size_t mmapStart; // cross over point for mmap 120 static unsigned int maxBucketsUsed; // maximum number of buckets in use 121 // extern visibility, used by runtime kernel 122 size_t __page_size; // architecture pagesize 123 int __map_prot; // common mmap/mprotect protection 124 125 126 #define SPINLOCK 0 127 #define LOCKFREE 1 128 #define BUCKETLOCK SPINLOCK 129 #if BUCKETLOCK == SPINLOCK 130 #elif BUCKETLOCK == LOCKFREE 131 #include <stackLockFree.hfa> 132 #else 133 #error undefined lock type for bucket lock 134 #endif // LOCKFREE 135 136 // Recursive definitions: HeapManager needs size of bucket array and bucket area needs sizeof HeapManager storage. 137 // Break recursion by hardcoding number of buckets and statically checking number is correct after bucket array defined. 138 enum { NoBucketSizes = 91 }; // number of buckets sizes 139 140 struct Heap { 141 struct Storage { 142 struct Header { // header 143 union Kind { 144 struct RealHeader { 145 union { 146 struct { // 4-byte word => 8-byte header, 8-byte word => 16-byte header 147 union { 148 // 2nd low-order bit => zero filled, 3rd low-order bit => mmapped 149 // FreeHeader * home; // allocated block points back to home locations (must overlay alignment) 150 void * home; // allocated block points back to home locations (must overlay alignment) 151 size_t blockSize; // size for munmap (must overlay alignment) 152 #if BUCKETLOCK == SPINLOCK 153 Storage * next; // freed block points to next freed block of same size 154 #endif // SPINLOCK 155 }; 156 size_t size; // allocation size in bytes 157 }; 158 #if BUCKETLOCK == LOCKFREE 159 Link(Storage) next; // freed block points next freed block of same size (double-wide) 160 #endif // LOCKFREE 161 }; 162 } real; // RealHeader 163 164 struct FakeHeader { 165 uintptr_t alignment; // 1st low-order bit => fake header & alignment 166 uintptr_t offset; 167 } fake; // FakeHeader 168 } kind; // Kind 169 } header; // Header 170 171 char pad[libAlign() - sizeof( Header )]; 172 char data[0]; // storage 173 }; // Storage 174 175 static_assert( libAlign() >= sizeof( Storage ), "minimum alignment < sizeof( Storage )" ); 176 177 struct FreeHeader { 178 #if BUCKETLOCK == SPINLOCK 179 __spinlock_t lock; // must be first field for alignment 180 Storage * freeList; 181 #else 182 StackLF(Storage) freeList; 183 #endif // BUCKETLOCK 184 size_t blockSize; // size of allocations on this list 185 }; // FreeHeader 186 187 // must be first fields for alignment 188 __spinlock_t extlock; // protects allocation-buffer extension 189 FreeHeader freeLists[NoBucketSizes]; // buckets for different allocation sizes 190 191 void * heapBegin; // start of heap 192 void * heapEnd; // logical end of heap 193 size_t heapRemaining; // amount of storage not allocated in the current chunk 194 }; // Heap 195 196 #if BUCKETLOCK == LOCKFREE 197 static inline { 198 Link(Heap.Storage) * ?`next( Heap.Storage * this ) { return &this->header.kind.real.next; } 199 void ?{}( Heap.FreeHeader & ) {} 200 void ^?{}( Heap.FreeHeader & ) {} 201 } // distribution 202 #endif // LOCKFREE 203 204 static inline size_t getKey( const Heap.FreeHeader & freeheader ) { return freeheader.blockSize; } 205 206 207 #ifdef FASTLOOKUP 208 enum { LookupSizes = 65_536 + sizeof(Heap.Storage) }; // number of fast lookup sizes 209 static unsigned char lookup[LookupSizes]; // O(1) lookup for small sizes 210 #endif // FASTLOOKUP 211 212 static const off_t mmapFd = -1; // fake or actual fd for anonymous file 213 #ifdef __CFA_DEBUG__ 214 static bool heapBoot = 0; // detect recursion during boot 215 #endif // __CFA_DEBUG__ 216 217 218 // Size of array must harmonize with NoBucketSizes and individual bucket sizes must be multiple of 16. 219 // Smaller multiples of 16 and powers of 2 are common allocation sizes, so make them generate the minimum required bucket size. 220 // malloc(0) returns 0p, so no bucket is necessary for 0 bytes returning an address that can be freed. 221 static const unsigned int bucketSizes[] @= { // different bucket sizes 222 16 + sizeof(Heap.Storage), 32 + sizeof(Heap.Storage), 48 + sizeof(Heap.Storage), 64 + sizeof(Heap.Storage), // 4 223 96 + sizeof(Heap.Storage), 112 + sizeof(Heap.Storage), 128 + sizeof(Heap.Storage), // 3 224 160, 192, 224, 256 + sizeof(Heap.Storage), // 4 225 320, 384, 448, 512 + sizeof(Heap.Storage), // 4 226 640, 768, 896, 1_024 + sizeof(Heap.Storage), // 4 227 1_536, 2_048 + sizeof(Heap.Storage), // 2 228 2_560, 3_072, 3_584, 4_096 + sizeof(Heap.Storage), // 4 229 6_144, 8_192 + sizeof(Heap.Storage), // 2 230 9_216, 10_240, 11_264, 12_288, 13_312, 14_336, 15_360, 16_384 + sizeof(Heap.Storage), // 8 231 18_432, 20_480, 22_528, 24_576, 26_624, 28_672, 30_720, 32_768 + sizeof(Heap.Storage), // 8 232 36_864, 40_960, 45_056, 49_152, 53_248, 57_344, 61_440, 65_536 + sizeof(Heap.Storage), // 8 233 73_728, 81_920, 90_112, 98_304, 106_496, 114_688, 122_880, 131_072 + sizeof(Heap.Storage), // 8 234 147_456, 163_840, 180_224, 196_608, 212_992, 229_376, 245_760, 262_144 + sizeof(Heap.Storage), // 8 235 294_912, 327_680, 360_448, 393_216, 425_984, 458_752, 491_520, 524_288 + sizeof(Heap.Storage), // 8 236 655_360, 786_432, 917_504, 1_048_576 + sizeof(Heap.Storage), // 4 237 1_179_648, 1_310_720, 1_441_792, 1_572_864, 1_703_936, 1_835_008, 1_966_080, 2_097_152 + sizeof(Heap.Storage), // 8 238 2_621_440, 3_145_728, 3_670_016, 4_194_304 + sizeof(Heap.Storage), // 4 239 }; 240 241 static_assert( NoBucketSizes == sizeof(bucketSizes) / sizeof(bucketSizes[0] ), "size of bucket array wrong" ); 242 243 // The constructor for heapManager is called explicitly in memory_startup. 244 static Heap heapManager __attribute__(( aligned (128) )) @= {}; // size of cache line to prevent false sharing 245 246 247 //####################### Memory Allocation Routines Helpers #################### 90 248 91 249 … … 149 307 return lhs; 150 308 } // ?+=? 151 #endif // __STATISTICS__ 152 153 154 #define SPINLOCK 0 155 #define LOCKFREE 1 156 #define BUCKETLOCK SPINLOCK 157 #if BUCKETLOCK == SPINLOCK 158 #elif BUCKETLOCK == LOCKFREE 159 #include <stackLockFree.hfa> 160 #else 161 #error undefined lock type for bucket lock 162 #endif // LOCKFREE 163 164 // Recursive definitions: HeapManager needs size of bucket array and bucket area needs sizeof HeapManager storage. 165 // Break recursion by hardcoding number of buckets and statically checking number is correct after bucket array defined. 166 enum { NoBucketSizes = 91 }; // number of buckets sizes 167 168 struct Heap { 169 struct Storage { 170 struct Header { // header 171 union Kind { 172 struct RealHeader { 173 union { 174 struct { // 4-byte word => 8-byte header, 8-byte word => 16-byte header 175 union { 176 // 2nd low-order bit => zero filled, 3rd low-order bit => mmapped 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 BUCKETLOCK == SPINLOCK 181 Storage * next; // freed block points to next freed block of same size 182 #endif // SPINLOCK 183 }; 184 size_t size; // allocation size in bytes 185 }; 186 #if BUCKETLOCK == LOCKFREE 187 Link(Storage) next; // freed block points next freed block of same size (double-wide) 188 #endif // LOCKFREE 189 }; 190 } real; // RealHeader 191 192 struct FakeHeader { 193 uintptr_t alignment; // 1st low-order bit => fake header & alignment 194 uintptr_t offset; 195 } fake; // FakeHeader 196 } kind; // Kind 197 } header; // Header 198 199 char pad[libAlign() - sizeof( Header )]; 200 char data[0]; // storage 201 }; // Storage 202 203 static_assert( libAlign() >= sizeof( Storage ), "minimum alignment < sizeof( Storage )" ); 204 205 struct FreeHeader { 206 size_t blockSize __attribute__(( aligned (8) )); // size of allocations on this list 207 #if BUCKETLOCK == SPINLOCK 208 __spinlock_t lock; 209 Storage * freeList; 210 #else 211 StackLF(Storage) freeList; 212 #endif // BUCKETLOCK 213 } __attribute__(( aligned (8) )); // FreeHeader 214 215 FreeHeader freeLists[NoBucketSizes]; // buckets for different allocation sizes 216 217 __spinlock_t extlock; // protects allocation-buffer extension 218 void * heapBegin; // start of heap 219 void * heapEnd; // logical end of heap 220 size_t heapRemaining; // amount of storage not allocated in the current chunk 221 }; // Heap 222 223 #if BUCKETLOCK == LOCKFREE 224 static inline { 225 Link(Heap.Storage) * ?`next( Heap.Storage * this ) { return &this->header.kind.real.next; } 226 void ?{}( Heap.FreeHeader & ) {} 227 void ^?{}( Heap.FreeHeader & ) {} 228 } // distribution 229 #endif // LOCKFREE 230 231 static inline size_t getKey( const Heap.FreeHeader & freeheader ) { return freeheader.blockSize; } 232 233 234 #ifdef FASTLOOKUP 235 enum { LookupSizes = 65_536 + sizeof(Heap.Storage) }; // number of fast lookup sizes 236 static unsigned char lookup[LookupSizes]; // O(1) lookup for small sizes 237 #endif // FASTLOOKUP 238 239 static const off_t mmapFd = -1; // fake or actual fd for anonymous file 240 #ifdef __CFA_DEBUG__ 241 static bool heapBoot = 0; // detect recursion during boot 242 #endif // __CFA_DEBUG__ 243 244 245 // Size of array must harmonize with NoBucketSizes and individual bucket sizes must be multiple of 16. 246 // Smaller multiples of 16 and powers of 2 are common allocation sizes, so make them generate the minimum required bucket size. 247 // malloc(0) returns 0p, so no bucket is necessary for 0 bytes returning an address that can be freed. 248 static const unsigned int bucketSizes[] @= { // different bucket sizes 249 16 + sizeof(Heap.Storage), 32 + sizeof(Heap.Storage), 48 + sizeof(Heap.Storage), 64 + sizeof(Heap.Storage), // 4 250 96 + sizeof(Heap.Storage), 112 + sizeof(Heap.Storage), 128 + sizeof(Heap.Storage), // 3 251 160, 192, 224, 256 + sizeof(Heap.Storage), // 4 252 320, 384, 448, 512 + sizeof(Heap.Storage), // 4 253 640, 768, 896, 1_024 + sizeof(Heap.Storage), // 4 254 1_536, 2_048 + sizeof(Heap.Storage), // 2 255 2_560, 3_072, 3_584, 4_096 + sizeof(Heap.Storage), // 4 256 6_144, 8_192 + sizeof(Heap.Storage), // 2 257 9_216, 10_240, 11_264, 12_288, 13_312, 14_336, 15_360, 16_384 + sizeof(Heap.Storage), // 8 258 18_432, 20_480, 22_528, 24_576, 26_624, 28_672, 30_720, 32_768 + sizeof(Heap.Storage), // 8 259 36_864, 40_960, 45_056, 49_152, 53_248, 57_344, 61_440, 65_536 + sizeof(Heap.Storage), // 8 260 73_728, 81_920, 90_112, 98_304, 106_496, 114_688, 122_880, 131_072 + sizeof(Heap.Storage), // 8 261 147_456, 163_840, 180_224, 196_608, 212_992, 229_376, 245_760, 262_144 + sizeof(Heap.Storage), // 8 262 294_912, 327_680, 360_448, 393_216, 425_984, 458_752, 491_520, 524_288 + sizeof(Heap.Storage), // 8 263 655_360, 786_432, 917_504, 1_048_576 + sizeof(Heap.Storage), // 4 264 1_179_648, 1_310_720, 1_441_792, 1_572_864, 1_703_936, 1_835_008, 1_966_080, 2_097_152 + sizeof(Heap.Storage), // 8 265 2_621_440, 3_145_728, 3_670_016, 4_194_304 + sizeof(Heap.Storage), // 4 266 }; 267 268 static_assert( NoBucketSizes == sizeof(bucketSizes) / sizeof(bucketSizes[0] ), "size of bucket array wrong" ); 269 270 // The constructor for heapManager is called explicitly in memory_startup. 271 static Heap heapManager __attribute__(( aligned (128) )) @= {}; // size of cache line to prevent false sharing 272 273 274 //####################### Memory Allocation Routines Helpers #################### 275 276 277 #ifdef __CFA_DEBUG__ 278 static size_t allocUnfreed; // running total of allocations minus frees 279 280 static void prtUnfreed() { 281 if ( allocUnfreed != 0 ) { 282 // DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT. 283 char helpText[512]; 284 __cfaabi_bits_print_buffer( STDERR_FILENO, helpText, sizeof(helpText), 285 "CFA warning (UNIX pid:%ld) : program terminating with %zu(0x%zx) bytes of storage allocated but not freed.\n" 286 "Possible cause is unfreed storage allocated by the program or system/library routines called from the program.\n", 287 (long int)getpid(), allocUnfreed, allocUnfreed ); // always print the UNIX pid 288 } // if 289 } // prtUnfreed 290 291 extern int cfa_main_returned; // from interpose.cfa 292 extern "C" { 293 void heapAppStart() { // called by __cfaabi_appready_startup 294 allocUnfreed = 0; 295 } // heapAppStart 296 297 void heapAppStop() { // called by __cfaabi_appready_startdown 298 fclose( stdin ); fclose( stdout ); 299 if ( cfa_main_returned ) prtUnfreed(); // do not check unfreed storage if exit called 300 } // heapAppStop 301 } // extern "C" 302 #endif // __CFA_DEBUG__ 303 304 305 #ifdef __STATISTICS__ 309 306 310 static HeapStatistics stats; // zero filled 307 311 static unsigned int sbrk_calls; … … 383 387 384 388 385 // statically allocated variables => zero filled.386 static size_t heapExpand; // sbrk advance387 static size_t mmapStart; // cross over point for mmap388 static unsigned int maxBucketsUsed; // maximum number of buckets in use389 // extern visibility, used by runtime kernel390 size_t __page_size; // architecture pagesize391 int __map_prot; // common mmap/mprotect protection392 393 394 389 // thunk problem 395 390 size_t Bsearchl( unsigned int key, const unsigned int * vals, size_t dim ) { … … 495 490 } else { 496 491 fakeHeader( header, alignment ); 497 if ( unlikely( MmappedBit( header ) ) ) { // mmapped ?498 verify( addr < heapBegin || heapEnd < addr );492 if ( unlikely( MmappedBit( header ) ) ) { 493 assert( addr < heapBegin || heapEnd < addr ); 499 494 size = ClearStickyBits( header->kind.real.blockSize ); // mmap size 500 495 return true; … … 508 503 checkHeader( header < (Heap.Storage.Header *)heapBegin || (Heap.Storage.Header *)heapEnd < header, name, addr ); // bad address ? (offset could be + or -) 509 504 510 Heap * homeManager; 511 if ( unlikely( freeHead == 0p || // freed and only free-list node => null link 512 // freed and link points at another free block not to a bucket in the bucket array. 513 freeHead < &freeLists[0] || &freeLists[NoBucketSizes] <= freeHead ) ) { 514 abort( "**** Error **** attempt to %s storage %p with corrupted header.\n" 515 "Possible cause is duplicate free on same block or overwriting of header information.", 516 name, addr ); 517 } // if 505 if ( freeHead < &freeLists[0] || &freeLists[NoBucketSizes] <= freeHead ) { 506 abort( "Attempt to %s storage %p with corrupted header.\n" 507 "Possible cause is duplicate free on same block or overwriting of header information.", 508 name, addr ); 509 } // if 518 510 #endif // __CFA_DEBUG__ 519 511 … … 568 560 sbrk_storage += increase; 569 561 #endif // __STATISTICS__ 570 571 562 #ifdef __CFA_DEBUG__ 572 563 // Set new memory to garbage so subsequent uninitialized usages might fail. … … 574 565 //Memset( (char *)heapEnd + heapRemaining, increase ); 575 566 #endif // __CFA_DEBUG__ 576 577 567 rem = heapRemaining + increase - size; 578 568 } // if … … 661 651 __atomic_add_fetch( &allocUnfreed, tsize, __ATOMIC_SEQ_CST ); 662 652 if ( traceHeap() ) { 663 char helpText[64]; 664 __cfaabi_bits_print_buffer( STDERR_FILENO, helpText, sizeof(helpText), 665 "%p = Malloc( %zu ) (allocated %zu)\n", addr, size, tsize ); // print debug/nodebug 653 enum { BufferSize = 64 }; 654 char helpText[BufferSize]; 655 int len = snprintf( helpText, BufferSize, "%p = Malloc( %zu ) (allocated %zu)\n", addr, size, tsize ); 656 __cfaabi_bits_write( STDERR_FILENO, helpText, len ); // print debug/nodebug 666 657 } // if 667 658 #endif // __CFA_DEBUG__ … … 720 711 if ( traceHeap() ) { 721 712 char helpText[64]; 722 __cfaabi_bits_print_buffer( STDERR_FILENO, helpText, sizeof(helpText),723 "Free( %p ) size:%zu\n", addr, size); // print debug/nodebug713 int len = snprintf( helpText, sizeof(helpText), "Free( %p ) size:%zu\n", addr, size ); 714 __cfaabi_bits_write( STDERR_FILENO, helpText, len ); // print debug/nodebug 724 715 } // if 725 716 #endif // __CFA_DEBUG__
Note:
See TracChangeset
for help on using the changeset viewer.
