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