Index: libcfa/src/heap.cfa =================================================================== --- libcfa/src/heap.cfa (revision 0a25c347642e7431f93ca325d0c1043a69fc91f5) +++ libcfa/src/heap.cfa (revision 95eb7cfe800ca3bc7760457356d3848fdc56cc93) @@ -10,6 +10,6 @@ // Created On : Tue Dec 19 21:58:35 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Fri Oct 18 07:42:09 2019 -// Update Count : 556 +// Last Modified On : Fri Nov 22 14:16:30 2019 +// Update Count : 626 // @@ -30,4 +30,5 @@ #include "malloc.h" +#define MIN(x, y) (y > x ? x : y) static bool traceHeap = false; @@ -50,21 +51,21 @@ -static bool checkFree = false; - -inline bool checkFree() { - return checkFree; -} // checkFree - -bool checkFreeOn() { - bool temp = checkFree; - checkFree = true; +static bool prtFree = false; + +inline bool prtFree() { + return prtFree; +} // prtFree + +bool prtFreeOn() { + bool temp = prtFree; + prtFree = true; return temp; -} // checkFreeOn - -bool checkFreeOff() { - bool temp = checkFree; - checkFree = false; +} // prtFreeOn + +bool prtFreeOff() { + bool temp = prtFree; + prtFree = false; return temp; -} // checkFreeOff +} // prtFreeOff @@ -105,5 +106,5 @@ static unsigned int allocFree; // running total of allocations minus frees -static void checkUnfreed() { +static void prtUnfreed() { if ( allocFree != 0 ) { // DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT. @@ -112,7 +113,7 @@ // "Possible cause is unfreed storage allocated by the program or system/library routines called from the program.\n", // (long int)getpid(), allocFree, allocFree ); // always print the UNIX pid - // __cfaabi_dbg_bits_write( helpText, len ); - } // if -} // checkUnfreed + // __cfaabi_dbg_bits_write( STDERR_FILENO, helpText, len ); // print debug/nodebug + } // if +} // prtUnfreed extern "C" { @@ -123,5 +124,5 @@ void heapAppStop() { // called by __cfaabi_appready_startdown fclose( stdin ); fclose( stdout ); - checkUnfreed(); + prtUnfreed(); } // heapAppStop } // extern "C" @@ -134,7 +135,4 @@ static unsigned int maxBucketsUsed; // maximum number of buckets in use - -// #comment TD : This defined is significantly different from the __ALIGN__ define from locks.hfa -#define ALIGN 16 #define SPINLOCK 0 @@ -147,5 +145,5 @@ // Recursive definitions: HeapManager needs size of bucket array and bucket area needs sizeof HeapManager storage. // Break recusion by hardcoding number of buckets and statically checking number is correct after bucket array defined. -enum { NoBucketSizes = 93 }; // number of buckets sizes +enum { NoBucketSizes = 91 }; // number of buckets sizes struct HeapManager { @@ -194,9 +192,9 @@ } kind; // Kind } header; // Header - char pad[ALIGN - sizeof( Header )]; + char pad[libAlign() - sizeof( Header )]; char data[0]; // storage }; // Storage - static_assert( ALIGN >= sizeof( Storage ), "ALIGN < sizeof( Storage )" ); + static_assert( libAlign() >= sizeof( Storage ), "libAlign() < sizeof( Storage )" ); struct FreeHeader { @@ -230,17 +228,21 @@ // Powers of 2 are common allocation sizes, so make powers of 2 generate the minimum required size. static const unsigned int bucketSizes[] @= { // different bucket sizes - 16, 32, 48, 64, - 64 + sizeof(HeapManager.Storage), 96, 112, 128, 128 + sizeof(HeapManager.Storage), 160, 192, 224, - 256 + sizeof(HeapManager.Storage), 320, 384, 448, 512 + sizeof(HeapManager.Storage), 640, 768, 896, - 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, - 8_192 + sizeof(HeapManager.Storage), 9_216, 10_240, 11_264, 12_288, 13_312, 14_336, 15_360, - 16_384 + sizeof(HeapManager.Storage), 18_432, 20_480, 22_528, 24_576, 26_624, 28_672, 30_720, - 32_768 + sizeof(HeapManager.Storage), 36_864, 40_960, 45_056, 49_152, 53_248, 57_344, 61_440, - 65_536 + sizeof(HeapManager.Storage), 73_728, 81_920, 90_112, 98_304, 106_496, 114_688, 122_880, - 131_072 + sizeof(HeapManager.Storage), 147_456, 163_840, 180_224, 196_608, 212_992, 229_376, 245_760, - 262_144 + sizeof(HeapManager.Storage), 294_912, 327_680, 360_448, 393_216, 425_984, 458_752, 491_520, - 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, - 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, - 4_194_304 + sizeof(HeapManager.Storage) + 16, 32, 48, 64 + sizeof(HeapManager.Storage), // 4 + 96, 112, 128 + sizeof(HeapManager.Storage), // 3 + 160, 192, 224, 256 + sizeof(HeapManager.Storage), // 4 + 320, 384, 448, 512 + sizeof(HeapManager.Storage), // 4 + 640, 768, 896, 1_024 + sizeof(HeapManager.Storage), // 4 + 1_536, 2_048 + sizeof(HeapManager.Storage), // 2 + 2_560, 3_072, 3_584, 4_096 + sizeof(HeapManager.Storage), // 4 + 6_144, 8_192 + sizeof(HeapManager.Storage), // 2 + 9_216, 10_240, 11_264, 12_288, 13_312, 14_336, 15_360, 16_384 + sizeof(HeapManager.Storage), // 8 + 18_432, 20_480, 22_528, 24_576, 26_624, 28_672, 30_720, 32_768 + sizeof(HeapManager.Storage), // 8 + 36_864, 40_960, 45_056, 49_152, 53_248, 57_344, 61_440, 65_536 + sizeof(HeapManager.Storage), // 8 + 73_728, 81_920, 90_112, 98_304, 106_496, 114_688, 122_880, 131_072 + sizeof(HeapManager.Storage), // 8 + 147_456, 163_840, 180_224, 196_608, 212_992, 229_376, 245_760, 262_144 + sizeof(HeapManager.Storage), // 8 + 294_912, 327_680, 360_448, 393_216, 425_984, 458_752, 491_520, 524_288 + sizeof(HeapManager.Storage), // 8 + 655_360, 786_432, 917_504, 1_048_576 + sizeof(HeapManager.Storage), // 4 + 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(HeapManager.Storage), // 8 + 2_621_440, 3_145_728, 3_670_016, 4_194_304 + sizeof(HeapManager.Storage), // 4 }; @@ -251,7 +253,6 @@ static unsigned char lookup[LookupSizes]; // O(1) lookup for small sizes #endif // FASTLOOKUP + static int mmapFd = -1; // fake or actual fd for anonymous file - - #ifdef __CFA_DEBUG__ static bool heapBoot = 0; // detect recursion during boot @@ -259,76 +260,8 @@ static HeapManager heapManager __attribute__(( aligned (128) )) @= {}; // size of cache line to prevent false sharing -// #comment TD : The return type of this function should be commented -static inline bool setMmapStart( size_t value ) { - if ( value < pageSize || bucketSizes[NoBucketSizes - 1] < value ) return true; - mmapStart = value; // set global - - // find the closest bucket size less than or equal to the mmapStart size - maxBucketsUsed = bsearchl( (unsigned int)mmapStart, bucketSizes, NoBucketSizes ); // binary search - assert( maxBucketsUsed < NoBucketSizes ); // subscript failure ? - assert( mmapStart <= bucketSizes[maxBucketsUsed] ); // search failure ? - return false; -} // setMmapStart - - -static void ?{}( HeapManager & manager ) with ( manager ) { - pageSize = sysconf( _SC_PAGESIZE ); - - for ( unsigned int i = 0; i < NoBucketSizes; i += 1 ) { // initialize the free lists - freeLists[i].blockSize = bucketSizes[i]; - } // for - - #ifdef FASTLOOKUP - unsigned int idx = 0; - for ( unsigned int i = 0; i < LookupSizes; i += 1 ) { - if ( i > bucketSizes[idx] ) idx += 1; - lookup[i] = idx; - } // for - #endif // FASTLOOKUP - - if ( setMmapStart( default_mmap_start() ) ) { - abort( "HeapManager : internal error, mmap start initialization failure." ); - } // if - heapExpand = default_heap_expansion(); - - char * End = (char *)sbrk( 0 ); - sbrk( (char *)libCeiling( (long unsigned int)End, libAlign() ) - End ); // move start of heap to multiple of alignment - heapBegin = heapEnd = sbrk( 0 ); // get new start point -} // HeapManager - - -static void ^?{}( HeapManager & ) { - #ifdef __STATISTICS__ - // if ( traceHeapTerm() ) { - // printStats(); - // if ( checkfree() ) checkFree( heapManager, true ); - // } // if - #endif // __STATISTICS__ -} // ~HeapManager - - -static void memory_startup( void ) __attribute__(( constructor( STARTUP_PRIORITY_MEMORY ) )); -void memory_startup( void ) { - #ifdef __CFA_DEBUG__ - if ( unlikely( heapBoot ) ) { // check for recursion during system boot - // DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT. - abort( "boot() : internal error, recursively invoked during system boot." ); - } // if - heapBoot = true; - #endif // __CFA_DEBUG__ - - //assert( heapManager.heapBegin != 0 ); - //heapManager{}; - if ( heapManager.heapBegin == 0 ) heapManager{}; -} // memory_startup - -static void memory_shutdown( void ) __attribute__(( destructor( STARTUP_PRIORITY_MEMORY ) )); -void memory_shutdown( void ) { - ^heapManager{}; -} // memory_shutdown - #ifdef __STATISTICS__ -static unsigned long long int mmap_storage; // heap statistics counters +// Heap statistics counters. +static unsigned long long int mmap_storage; static unsigned int mmap_calls; static unsigned long long int munmap_storage; @@ -348,12 +281,11 @@ static unsigned long long int realloc_storage; static unsigned int realloc_calls; - -static int statfd; // statistics file descriptor (changed by malloc_stats_fd) - +// Statistics file descriptor (changed by malloc_stats_fd). +static int statfd = STDERR_FILENO; // default stderr // Use "write" because streams may be shutdown when calls are made. static void printStats() { char helpText[512]; - __cfaabi_dbg_bits_print_buffer( helpText, sizeof(helpText), + __cfaabi_bits_print_buffer( STDERR_FILENO, helpText, sizeof(helpText), "\nHeap statistics:\n" " malloc: calls %u / storage %llu\n" @@ -405,7 +337,9 @@ sbrk_calls, sbrk_storage ); - return write( fileno( stream ), helpText, len ); // -1 => error + __cfaabi_bits_write( fileno( stream ), helpText, len ); // ensures all bytes written or exit + return len; } // printStatsXML #endif // __STATISTICS__ + // #comment TD : Is this the samething as Out-of-Memory? @@ -418,6 +352,6 @@ static inline void checkAlign( size_t alignment ) { - if ( alignment < sizeof(void *) || ! libPow2( alignment ) ) { - abort( "Alignment %zu for memory allocation is less than sizeof(void *) and/or not a power of 2.", alignment ); + if ( alignment < libAlign() || ! libPow2( alignment ) ) { + abort( "Alignment %zu for memory allocation is less than %d and/or not a power of 2.", alignment, libAlign() ); } // if } // checkAlign @@ -431,4 +365,16 @@ +static inline bool setMmapStart( size_t value ) { // true => mmapped, false => sbrk + if ( value < pageSize || bucketSizes[NoBucketSizes - 1] < value ) return true; + mmapStart = value; // set global + + // find the closest bucket size less than or equal to the mmapStart size + maxBucketsUsed = bsearchl( (unsigned int)mmapStart, bucketSizes, NoBucketSizes ); // binary search + assert( maxBucketsUsed < NoBucketSizes ); // subscript failure ? + assert( mmapStart <= bucketSizes[maxBucketsUsed] ); // search failure ? + return false; +} // setMmapStart + + static inline void checkHeader( bool check, const char * name, void * addr ) { if ( unlikely( check ) ) { // bad address ? @@ -439,7 +385,6 @@ } // checkHeader -// #comment TD : function should be commented and/or have a more evocative name -// this isn't either a check or a constructor which is what I would expect this function to be -static inline void fakeHeader( HeapManager.Storage.Header *& header, size_t & size, size_t & alignment ) { + +static inline void fakeHeader( HeapManager.Storage.Header *& header, size_t & alignment ) { if ( unlikely( (header->kind.fake.alignment & 1) == 1 ) ) { // fake header ? size_t offset = header->kind.fake.offset; @@ -452,12 +397,27 @@ } // fakeHeader -// #comment TD : Why is this a define + +// <-------+----------------------------------------------------> bsize (bucket size) +// |header |addr +//================================================================================== +// | alignment +// <-----------------<------------+-----------------------------> bsize (bucket size) +// |fake-header | addr #define headerAddr( addr ) ((HeapManager.Storage.Header *)( (char *)addr - sizeof(HeapManager.Storage) )) -static inline bool headers( const char * name, void * addr, HeapManager.Storage.Header *& header, HeapManager.FreeHeader *& freeElem, size_t & size, size_t & alignment ) with ( heapManager ) { +// <-------<<--------------------- dsize ---------------------->> bsize (bucket size) +// |header |addr +//================================================================================== +// | alignment +// <------------------------------<<---------- dsize --------->>> bsize (bucket size) +// |fake-header |addr +#define dataStorage( bsize, addr, header ) (bsize - ( (char *)addr - (char *)header )) + + +static inline bool headers( const char * name __attribute__(( unused )), void * addr, HeapManager.Storage.Header *& header, HeapManager.FreeHeader *& freeElem, size_t & size, size_t & alignment ) with ( heapManager ) { header = headerAddr( addr ); if ( unlikely( heapEnd < addr ) ) { // mmapped ? - fakeHeader( header, size, alignment ); + fakeHeader( header, alignment ); size = header->kind.real.blockSize & -3; // mmap size return true; @@ -468,9 +428,6 @@ #endif // __CFA_DEBUG__ - // #comment TD : This code looks weird... - // It's called as the first statement of both branches of the last if, with the same parameters in all cases - // header may be safe to dereference - fakeHeader( header, size, alignment ); + fakeHeader( header, alignment ); #ifdef __CFA_DEBUG__ checkHeader( header < (HeapManager.Storage.Header *)heapBegin || (HeapManager.Storage.Header *)heapEnd < header, name, addr ); // bad address ? (offset could be + or -) @@ -500,5 +457,5 @@ unlock( extlock ); errno = ENOMEM; - return 0; + return 0p; } // if #ifdef __STATISTICS__ @@ -541,5 +498,5 @@ // along with the block and is a multiple of the alignment size. - if ( unlikely( size > ~0ul - sizeof(HeapManager.Storage) ) ) return 0; + if ( unlikely( size > ~0ul - sizeof(HeapManager.Storage) ) ) return 0p; size_t tsize = size + sizeof(HeapManager.Storage); if ( likely( tsize < mmapStart ) ) { // small size => sbrk @@ -574,5 +531,5 @@ block = freeElem->freeList.pop(); #endif // SPINLOCK - if ( unlikely( block == 0 ) ) { // no free block ? + if ( unlikely( block == 0p ) ) { // no free block ? #if defined( SPINLOCK ) unlock( freeElem->lock ); @@ -583,5 +540,5 @@ block = (HeapManager.Storage *)extend( tsize ); // mutual exclusion on call - if ( unlikely( block == 0 ) ) return 0; + if ( unlikely( block == 0p ) ) return 0p; #if defined( SPINLOCK ) } else { @@ -593,5 +550,5 @@ block->header.kind.real.home = freeElem; // pointer back to free list of apropriate size } else { // large size => mmap - if ( unlikely( size > ~0ul - pageSize ) ) return 0; + if ( unlikely( size > ~0ul - pageSize ) ) return 0p; tsize = libCeiling( tsize, pageSize ); // must be multiple of page size #ifdef __STATISTICS__ @@ -611,19 +568,19 @@ } // if - void * area = &(block->data); // adjust off header to user bytes + void * addr = &(block->data); // adjust off header to user bytes #ifdef __CFA_DEBUG__ - assert( ((uintptr_t)area & (libAlign() - 1)) == 0 ); // minimum alignment ? + assert( ((uintptr_t)addr & (libAlign() - 1)) == 0 ); // minimum alignment ? __atomic_add_fetch( &allocFree, tsize, __ATOMIC_SEQ_CST ); if ( traceHeap() ) { enum { BufferSize = 64 }; char helpText[BufferSize]; - int len = snprintf( helpText, BufferSize, "%p = Malloc( %zu ) (allocated %zu)\n", area, size, tsize ); - // int len = snprintf( helpText, BufferSize, "Malloc %p %zu\n", area, size ); - __cfaabi_dbg_bits_write( helpText, len ); + int len = snprintf( helpText, BufferSize, "%p = Malloc( %zu ) (allocated %zu)\n", addr, size, tsize ); + // int len = snprintf( helpText, BufferSize, "Malloc %p %zu\n", addr, size ); + __cfaabi_bits_write( STDERR_FILENO, helpText, len ); // print debug/nodebug } // if #endif // __CFA_DEBUG__ - return area; + return addr; } // doMalloc @@ -631,5 +588,5 @@ static inline void doFree( void * addr ) with ( heapManager ) { #ifdef __CFA_DEBUG__ - if ( unlikely( heapManager.heapBegin == 0 ) ) { + if ( unlikely( heapManager.heapBegin == 0p ) ) { abort( "doFree( %p ) : internal error, called before heap is initialized.", addr ); } // if @@ -677,5 +634,5 @@ char helpText[BufferSize]; int len = snprintf( helpText, sizeof(helpText), "Free( %p ) size:%zu\n", addr, size ); - __cfaabi_dbg_bits_write( helpText, len ); + __cfaabi_bits_write( STDERR_FILENO, helpText, len ); // print debug/nodebug } // if #endif // __CFA_DEBUG__ @@ -683,9 +640,9 @@ -size_t checkFree( HeapManager & manager ) with ( manager ) { +size_t prtFree( HeapManager & manager ) with ( manager ) { size_t total = 0; #ifdef __STATISTICS__ - __cfaabi_dbg_bits_acquire(); - __cfaabi_dbg_bits_print_nolock( "\nBin lists (bin size : free blocks on list)\n" ); + __cfaabi_bits_acquire(); + __cfaabi_bits_print_nolock( STDERR_FILENO, "\nBin lists (bin size : free blocks on list)\n" ); #endif // __STATISTICS__ for ( unsigned int i = 0; i < maxBucketsUsed; i += 1 ) { @@ -696,7 +653,7 @@ #if defined( SPINLOCK ) - for ( HeapManager.Storage * p = freeLists[i].freeList; p != 0; p = p->header.kind.real.next ) { + for ( HeapManager.Storage * p = freeLists[i].freeList; p != 0p; p = p->header.kind.real.next ) { #else - for ( HeapManager.Storage * p = freeLists[i].freeList.top(); p != 0; p = p->header.kind.real.next.top ) { + for ( HeapManager.Storage * p = freeLists[i].freeList.top(); p != 0p; p = p->header.kind.real.next.top ) { #endif // SPINLOCK total += size; @@ -707,23 +664,103 @@ #ifdef __STATISTICS__ - __cfaabi_dbg_bits_print_nolock( "%7zu, %-7u ", size, N ); - if ( (i + 1) % 8 == 0 ) __cfaabi_dbg_bits_print_nolock( "\n" ); + __cfaabi_bits_print_nolock( STDERR_FILENO, "%7zu, %-7u ", size, N ); + if ( (i + 1) % 8 == 0 ) __cfaabi_bits_print_nolock( STDERR_FILENO, "\n" ); #endif // __STATISTICS__ } // for #ifdef __STATISTICS__ - __cfaabi_dbg_bits_print_nolock( "\ntotal free blocks:%zu\n", total ); - __cfaabi_dbg_bits_release(); + __cfaabi_bits_print_nolock( STDERR_FILENO, "\ntotal free blocks:%zu\n", total ); + __cfaabi_bits_release(); #endif // __STATISTICS__ return (char *)heapEnd - (char *)heapBegin - total; -} // checkFree +} // prtFree + + +static void ?{}( HeapManager & manager ) with ( manager ) { + pageSize = sysconf( _SC_PAGESIZE ); + + for ( unsigned int i = 0; i < NoBucketSizes; i += 1 ) { // initialize the free lists + freeLists[i].blockSize = bucketSizes[i]; + } // for + + #ifdef FASTLOOKUP + unsigned int idx = 0; + for ( unsigned int i = 0; i < LookupSizes; i += 1 ) { + if ( i > bucketSizes[idx] ) idx += 1; + lookup[i] = idx; + } // for + #endif // FASTLOOKUP + + if ( setMmapStart( default_mmap_start() ) ) { + abort( "HeapManager : internal error, mmap start initialization failure." ); + } // if + heapExpand = default_heap_expansion(); + + char * End = (char *)sbrk( 0 ); + sbrk( (char *)libCeiling( (long unsigned int)End, libAlign() ) - End ); // move start of heap to multiple of alignment + heapBegin = heapEnd = sbrk( 0 ); // get new start point +} // HeapManager + + +static void ^?{}( HeapManager & ) { + #ifdef __STATISTICS__ + // if ( traceHeapTerm() ) { + // printStats(); + // if ( prtfree() ) prtFree( heapManager, true ); + // } // if + #endif // __STATISTICS__ +} // ~HeapManager + + +static void memory_startup( void ) __attribute__(( constructor( STARTUP_PRIORITY_MEMORY ) )); +void memory_startup( void ) { + #ifdef __CFA_DEBUG__ + if ( unlikely( heapBoot ) ) { // check for recursion during system boot + // DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT. + abort( "boot() : internal error, recursively invoked during system boot." ); + } // if + heapBoot = true; + #endif // __CFA_DEBUG__ + + //assert( heapManager.heapBegin != 0 ); + //heapManager{}; + if ( heapManager.heapBegin == 0p ) heapManager{}; +} // memory_startup + +static void memory_shutdown( void ) __attribute__(( destructor( STARTUP_PRIORITY_MEMORY ) )); +void memory_shutdown( void ) { + ^heapManager{}; +} // memory_shutdown static inline void * mallocNoStats( size_t size ) { // necessary for malloc statistics //assert( heapManager.heapBegin != 0 ); - if ( unlikely( heapManager.heapBegin == 0 ) ) heapManager{}; // called before memory_startup ? - void * area = doMalloc( size ); - if ( unlikely( area == 0 ) ) errno = ENOMEM; // POSIX - return area; + if ( unlikely( heapManager.heapBegin == 0p ) ) heapManager{}; // called before memory_startup ? + void * addr = doMalloc( size ); + if ( unlikely( addr == 0p ) ) errno = ENOMEM; // POSIX + return addr; } // mallocNoStats + + +static inline void * callocNoStats( size_t noOfElems, size_t elemSize ) { + size_t size = noOfElems * elemSize; + char * addr = (char *)mallocNoStats( size ); + if ( unlikely( addr == 0p ) ) return 0p; + + HeapManager.Storage.Header * header; + HeapManager.FreeHeader * freeElem; + size_t bsize, alignment; + bool mapped __attribute__(( unused )) = headers( "calloc", addr, header, freeElem, bsize, alignment ); + #ifndef __CFA_DEBUG__ + // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero. + if ( ! mapped ) + #endif // __CFA_DEBUG__ + // Zero entire data space even when > than size => realloc without a new allocation and zero fill works. + // <-------00000000000000000000000000000000000000000000000000000> bsize (bucket size) + // `-header`-addr `-size + memset( addr, '\0', bsize - sizeof(HeapManager.Storage) ); // set to zeros + + header->kind.real.blockSize |= 2; // mark as zero filled + return addr; +} // callocNoStats @@ -745,13 +782,12 @@ // subtract libAlign() because it is already the minimum alignment // add sizeof(Storage) for fake header - // #comment TD : this is the only place that calls doMalloc without calling mallocNoStats, why ? - char * area = (char *)doMalloc( size + alignment - libAlign() + sizeof(HeapManager.Storage) ); - if ( unlikely( area == 0 ) ) return area; + char * addr = (char *)mallocNoStats( size + alignment - libAlign() + sizeof(HeapManager.Storage) ); + if ( unlikely( addr == 0p ) ) return addr; // address in the block of the "next" alignment address - char * user = (char *)libCeiling( (uintptr_t)(area + sizeof(HeapManager.Storage)), alignment ); + char * user = (char *)libCeiling( (uintptr_t)(addr + sizeof(HeapManager.Storage)), alignment ); // address of header from malloc - HeapManager.Storage.Header * realHeader = headerAddr( area ); + HeapManager.Storage.Header * realHeader = headerAddr( addr ); // address of fake header * before* the alignment location HeapManager.Storage.Header * fakeHeader = headerAddr( user ); @@ -763,4 +799,23 @@ return user; } // memalignNoStats + + +static inline void * cmemalignNoStats( size_t alignment, size_t noOfElems, size_t elemSize ) { + size_t size = noOfElems * elemSize; + char * addr = (char *)memalignNoStats( alignment, size ); + if ( unlikely( addr == 0p ) ) return 0p; + HeapManager.Storage.Header * header; + HeapManager.FreeHeader * freeElem; + size_t bsize; + bool mapped __attribute__(( unused )) = headers( "cmemalign", addr, header, freeElem, bsize, alignment ); + #ifndef __CFA_DEBUG__ + // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero. + if ( ! mapped ) + #endif // __CFA_DEBUG__ + memset( addr, '\0', dataStorage( bsize, addr, header ) ); // set to zeros + header->kind.real.blockSize |= 2; // mark as zero filled + + return addr; +} // cmemalignNoStats @@ -776,5 +831,5 @@ extern "C" { // The malloc() function allocates size bytes and returns a pointer to the allocated memory. The memory is not - // initialized. If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be + // initialized. If size is 0, then malloc() returns either 0p, or a unique pointer value that can later be // successfully passed to free(). void * malloc( size_t size ) { @@ -788,78 +843,42 @@ // The calloc() function allocates memory for an array of nmemb elements of size bytes each and returns a pointer to - // the allocated memory. The memory is set to zero. If nmemb or size is 0, then calloc() returns either NULL, or a + // the allocated memory. The memory is set to zero. If nmemb or size is 0, then calloc() returns either 0p, or a // unique pointer value that can later be successfully passed to free(). void * calloc( size_t noOfElems, size_t elemSize ) { - size_t size = noOfElems * elemSize; #ifdef __STATISTICS__ __atomic_add_fetch( &calloc_calls, 1, __ATOMIC_SEQ_CST ); - __atomic_add_fetch( &calloc_storage, size, __ATOMIC_SEQ_CST ); - #endif // __STATISTICS__ - - char * area = (char *)mallocNoStats( size ); - if ( unlikely( area == 0 ) ) return 0; + __atomic_add_fetch( &calloc_storage, noOfElems * elemSize, __ATOMIC_SEQ_CST ); + #endif // __STATISTICS__ + + return callocNoStats( noOfElems, elemSize ); + } // calloc + + // The realloc() function changes the size of the memory block pointed to by ptr to size bytes. The contents will be + // unchanged in the range from the start of the region up to the minimum of the old and new sizes. If the new size + // is larger than the old size, the added memory will not be initialized. If ptr is 0p, then the call is + // equivalent to malloc(size), for all values of size; if size is equal to zero, and ptr is not 0p, then the call + // is equivalent to free(ptr). Unless ptr is 0p, it must have been returned by an earlier call to malloc(), + // calloc() or realloc(). If the area pointed to was moved, a free(ptr) is done. + void * realloc( void * oaddr, size_t size ) { + #ifdef __STATISTICS__ + __atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST ); + #endif // __STATISTICS__ + + if ( unlikely( size == 0 ) ) { free( oaddr ); return 0p; } // special cases + if ( unlikely( oaddr == 0p ) ) return mallocNoStats( size ); HeapManager.Storage.Header * header; HeapManager.FreeHeader * freeElem; - size_t asize, alignment; - bool mapped __attribute__(( unused )) = headers( "calloc", area, header, freeElem, asize, alignment ); - #ifndef __CFA_DEBUG__ - // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero. - if ( ! mapped ) - #endif // __CFA_DEBUG__ - memset( area, '\0', asize - sizeof(HeapManager.Storage) ); // set to zeros - - header->kind.real.blockSize |= 2; // mark as zero filled - return area; - } // calloc - - // #comment TD : Document this function - void * cmemalign( size_t alignment, size_t noOfElems, size_t elemSize ) { - size_t size = noOfElems * elemSize; - #ifdef __STATISTICS__ - __atomic_add_fetch( &cmemalign_calls, 1, __ATOMIC_SEQ_CST ); - __atomic_add_fetch( &cmemalign_storage, size, __ATOMIC_SEQ_CST ); - #endif // __STATISTICS__ - - char * area = (char *)memalignNoStats( alignment, size ); - if ( unlikely( area == 0 ) ) return 0; - HeapManager.Storage.Header * header; - HeapManager.FreeHeader * freeElem; - size_t asize; - bool mapped __attribute__(( unused )) = headers( "cmemalign", area, header, freeElem, asize, alignment ); - #ifndef __CFA_DEBUG__ - // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero. - if ( ! mapped ) - #endif // __CFA_DEBUG__ - memset( area, '\0', asize - ( (char *)area - (char *)header ) ); // set to zeros - header->kind.real.blockSize |= 2; // mark as zero filled - - return area; - } // cmemalign - - // The realloc() function changes the size of the memory block pointed to by ptr to size bytes. The contents will be - // unchanged in the range from the start of the region up to the minimum of the old and new sizes. If the new size - // is larger than the old size, the added memory will not be initialized. If ptr is NULL, then the call is - // equivalent to malloc(size), for all values of size; if size is equal to zero, and ptr is not NULL, then the call - // is equivalent to free(ptr). Unless ptr is NULL, it must have been returned by an earlier call to malloc(), - // calloc() or realloc(). If the area pointed to was moved, a free(ptr) is done. - void * realloc( void * addr, size_t size ) { - #ifdef __STATISTICS__ - __atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST ); - #endif // __STATISTICS__ - - if ( unlikely( addr == 0 ) ) return mallocNoStats( size ); // special cases - if ( unlikely( size == 0 ) ) { free( addr ); return 0; } - - HeapManager.Storage.Header * header; - HeapManager.FreeHeader * freeElem; - size_t asize, alignment = 0; - headers( "realloc", addr, header, freeElem, asize, alignment ); - - size_t usize = asize - ( (char *)addr - (char *)header ); // compute the amount of user storage in the block - if ( usize >= size ) { // already sufficient storage + size_t bsize, oalign = 0; + headers( "realloc", oaddr, header, freeElem, bsize, oalign ); + + size_t odsize = dataStorage( bsize, oaddr, header ); // data storage available in bucket + if ( size <= odsize && odsize <= size * 2 ) { // allow up to 50% wasted storage in smaller size + // Do not know size of original allocation => cannot do 0 fill for any additional space because do not know + // where to start filling, i.e., do not overwrite existing values in space. + // // This case does not result in a new profiler entry because the previous one still exists and it must match with // the free for this memory. Hence, this realloc does not appear in the profiler output. - return addr; + return oaddr; } // if @@ -868,24 +887,27 @@ #endif // __STATISTICS__ - void * area; - if ( unlikely( alignment != 0 ) ) { // previous request memalign? - area = memalign( alignment, size ); // create new aligned area + // change size and copy old content to new storage + + void * naddr; + if ( unlikely( oalign != 0 ) ) { // previous request memalign? + if ( unlikely( header->kind.real.blockSize & 2 ) ) { // previous request zero fill + naddr = cmemalignNoStats( oalign, 1, size ); // create new aligned area + } else { + naddr = memalignNoStats( oalign, size ); // create new aligned area + } // if } else { - area = mallocNoStats( size ); // create new area + if ( unlikely( header->kind.real.blockSize & 2 ) ) { // previous request zero fill + naddr = callocNoStats( 1, size ); // create new area + } else { + naddr = mallocNoStats( size ); // create new area + } // if } // if - if ( unlikely( area == 0 ) ) return 0; - if ( unlikely( header->kind.real.blockSize & 2 ) ) { // previous request zero fill (calloc/cmemalign) ? - assert( (header->kind.real.blockSize & 1) == 0 ); - bool mapped __attribute__(( unused )) = headers( "realloc", area, header, freeElem, asize, alignment ); - #ifndef __CFA_DEBUG__ - // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero. - if ( ! mapped ) - #endif // __CFA_DEBUG__ - memset( (char *)area + usize, '\0', asize - ( (char *)area - (char *)header ) - usize ); // zero-fill back part - header->kind.real.blockSize |= 2; // mark new request as zero fill - } // if - memcpy( area, addr, usize ); // copy bytes - free( addr ); - return area; + if ( unlikely( naddr == 0p ) ) return 0p; + headers( "realloc", naddr, header, freeElem, bsize, oalign ); + size_t ndsize = dataStorage( bsize, naddr, header ); // data storage avilable in bucket + // To preserve prior fill, the entire bucket must be copied versus the size. + memcpy( naddr, oaddr, MIN( odsize, ndsize ) ); // copy bytes + free( oaddr ); + return naddr; } // realloc @@ -898,8 +920,17 @@ #endif // __STATISTICS__ - void * area = memalignNoStats( alignment, size ); - - return area; + return memalignNoStats( alignment, size ); } // memalign + + + // The cmemalign() function is the same as calloc() with memory alignment. + void * cmemalign( size_t alignment, size_t noOfElems, size_t elemSize ) { + #ifdef __STATISTICS__ + __atomic_add_fetch( &cmemalign_calls, 1, __ATOMIC_SEQ_CST ); + __atomic_add_fetch( &cmemalign_storage, noOfElems * elemSize, __ATOMIC_SEQ_CST ); + #endif // __STATISTICS__ + + return cmemalignNoStats( alignment, noOfElems, elemSize ); + } // cmemalign // The function aligned_alloc() is the same as memalign(), except for the added restriction that size should be a @@ -912,10 +943,10 @@ // The function posix_memalign() allocates size bytes and places the address of the allocated memory in *memptr. The // address of the allocated memory will be a multiple of alignment, which must be a power of two and a multiple of - // sizeof(void *). If size is 0, then posix_memalign() returns either NULL, or a unique pointer value that can later + // sizeof(void *). If size is 0, then posix_memalign() returns either 0p, or a unique pointer value that can later // be successfully passed to free(3). int posix_memalign( void ** memptr, size_t alignment, size_t size ) { if ( alignment < sizeof(void *) || ! libPow2( alignment ) ) return EINVAL; // check alignment * memptr = memalign( alignment, size ); - if ( unlikely( * memptr == 0 ) ) return ENOMEM; + if ( unlikely( * memptr == 0p ) ) return ENOMEM; return 0; } // posix_memalign @@ -930,5 +961,5 @@ // The free() function frees the memory space pointed to by ptr, which must have been returned by a previous call to // malloc(), calloc() or realloc(). Otherwise, or if free(ptr) has already been called before, undefined behavior - // occurs. If ptr is NULL, no operation is performed. + // occurs. If ptr is 0p, no operation is performed. void free( void * addr ) { #ifdef __STATISTICS__ @@ -936,15 +967,12 @@ #endif // __STATISTICS__ - // #comment TD : To decrease nesting I would but the special case in the - // else instead, plus it reads more naturally to have the - // short / normal case instead - if ( unlikely( addr == 0 ) ) { // special case - #ifdef __CFA_DEBUG__ - if ( traceHeap() ) { - #define nullmsg "Free( 0x0 ) size:0\n" - // Do not debug print free( 0 ), as it can cause recursive entry from sprintf. - __cfaabi_dbg_bits_write( nullmsg, sizeof(nullmsg) - 1 ); - } // if - #endif // __CFA_DEBUG__ + if ( unlikely( addr == 0p ) ) { // special case + // #ifdef __CFA_DEBUG__ + // if ( traceHeap() ) { + // #define nullmsg "Free( 0x0 ) size:0\n" + // // Do not debug print free( 0 ), as it can cause recursive entry from sprintf. + // __cfaabi_dbg_write( nullmsg, sizeof(nullmsg) - 1 ); + // } // if + // #endif // __CFA_DEBUG__ return; } // exit @@ -953,44 +981,8 @@ } // free - // The mallopt() function adjusts parameters that control the behavior of the memory-allocation functions (see - // malloc(3)). The param argument specifies the parameter to be modified, and value specifies the new value for that - // parameter. - int mallopt( int option, int value ) { - choose( option ) { - case M_TOP_PAD: - if ( setHeapExpand( value ) ) fallthru default; - case M_MMAP_THRESHOLD: - if ( setMmapStart( value ) ) fallthru default; - default: - // #comment TD : 1 for unsopported feels wrong - return 1; // success, or unsupported - } // switch - return 0; // error - } // mallopt - - // The malloc_trim() function attempts to release free memory at the top of the heap (by calling sbrk(2) with a - // suitable argument). - int malloc_trim( size_t ) { - return 0; // => impossible to release memory - } // malloc_trim - - // The malloc_usable_size() function returns the number of usable bytes in the block pointed to by ptr, a pointer to - // a block of memory allocated by malloc(3) or a related function. - size_t malloc_usable_size( void * addr ) { - if ( unlikely( addr == 0 ) ) return 0; // null allocation has 0 size - - HeapManager.Storage.Header * header; - HeapManager.FreeHeader * freeElem; - size_t size, alignment; - - headers( "malloc_usable_size", addr, header, freeElem, size, alignment ); - size_t usize = size - ( (char *)addr - (char *)header ); // compute the amount of user storage in the block - return usize; - } // malloc_usable_size - // The malloc_alignment() function returns the alignment of the allocation. size_t malloc_alignment( void * addr ) { - if ( unlikely( addr == 0 ) ) return libAlign(); // minimum alignment + if ( unlikely( addr == 0p ) ) return libAlign(); // minimum alignment HeapManager.Storage.Header * header = headerAddr( addr ); if ( (header->kind.fake.alignment & 1) == 1 ) { // fake header ? @@ -1004,5 +996,5 @@ // The malloc_zero_fill() function returns true if the allocation is zero filled, i.e., initially allocated by calloc(). bool malloc_zero_fill( void * addr ) { - if ( unlikely( addr == 0 ) ) return false; // null allocation is not zero fill + if ( unlikely( addr == 0p ) ) return false; // null allocation is not zero fill HeapManager.Storage.Header * header = headerAddr( addr ); if ( (header->kind.fake.alignment & 1) == 1 ) { // fake header ? @@ -1013,4 +1005,17 @@ + // The malloc_usable_size() function returns the number of usable bytes in the block pointed to by ptr, a pointer to + // a block of memory allocated by malloc(3) or a related function. + size_t malloc_usable_size( void * addr ) { + if ( unlikely( addr == 0p ) ) return 0; // null allocation has 0 size + HeapManager.Storage.Header * header; + HeapManager.FreeHeader * freeElem; + size_t bsize, alignment; + + headers( "malloc_usable_size", addr, header, freeElem, bsize, alignment ); + return dataStorage( bsize, addr, header ); // data storage in bucket + } // malloc_usable_size + + // The malloc_stats() function prints (on default standard error) statistics about memory allocated by malloc(3) and // related functions. @@ -1018,10 +1023,10 @@ #ifdef __STATISTICS__ printStats(); - if ( checkFree() ) checkFree( heapManager ); + if ( prtFree() ) prtFree( heapManager ); #endif // __STATISTICS__ } // malloc_stats // The malloc_stats_fd() function changes the file descripter where malloc_stats() writes the statistics. - int malloc_stats_fd( int fd ) { + int malloc_stats_fd( int fd __attribute__(( unused )) ) { #ifdef __STATISTICS__ int temp = statfd; @@ -1033,8 +1038,30 @@ } // malloc_stats_fd + + // The mallopt() function adjusts parameters that control the behavior of the memory-allocation functions (see + // malloc(3)). The param argument specifies the parameter to be modified, and value specifies the new value for that + // parameter. + int mallopt( int option, int value ) { + choose( option ) { + case M_TOP_PAD: + if ( setHeapExpand( value ) ) return 1; + case M_MMAP_THRESHOLD: + if ( setMmapStart( value ) ) return 1; + } // switch + return 0; // error, unsupported + } // mallopt + + // The malloc_trim() function attempts to release free memory at the top of the heap (by calling sbrk(2) with a + // suitable argument). + int malloc_trim( size_t ) { + return 0; // => impossible to release memory + } // malloc_trim + + // The malloc_info() function exports an XML string that describes the current state of the memory-allocation // implementation in the caller. The string is printed on the file stream stream. The exported string includes // information about all arenas (see malloc(3)). int malloc_info( int options, FILE * stream ) { + if ( options != 0 ) { errno = EINVAL; return -1; } return printStatsXML( stream ); } // malloc_info @@ -1046,5 +1073,5 @@ // structure is returned as the function result. (It is the caller's responsibility to free(3) this memory.) void * malloc_get_state( void ) { - return 0; // unsupported + return 0p; // unsupported } // malloc_get_state @@ -1058,4 +1085,51 @@ +// Must have CFA linkage to overload with C linkage realloc. +void * realloc( void * oaddr, size_t nalign, size_t size ) { + #ifdef __STATISTICS__ + __atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST ); + #endif // __STATISTICS__ + + if ( unlikely( size == 0 ) ) { free( oaddr ); return 0p; } // special cases + if ( unlikely( oaddr == 0p ) ) return mallocNoStats( size ); + + if ( unlikely( nalign == 0 ) ) nalign = libAlign(); // reset alignment to minimum + #ifdef __CFA_DEBUG__ + else + checkAlign( nalign ); // check alignment + #endif // __CFA_DEBUG__ + + HeapManager.Storage.Header * header; + HeapManager.FreeHeader * freeElem; + size_t bsize, oalign = 0; + headers( "realloc", oaddr, header, freeElem, bsize, oalign ); + + size_t odsize = dataStorage( bsize, oaddr, header ); // data storage available in bucket + + if ( oalign != 0 && (uintptr_t)oaddr % nalign == 0 ) { // has alignment and just happens to work out + headerAddr( oaddr )->kind.fake.alignment = nalign | 1; // update alignment (could be the same) + return realloc( oaddr, size ); + } // if + + #ifdef __STATISTICS__ + __atomic_add_fetch( &realloc_storage, size, __ATOMIC_SEQ_CST ); + #endif // __STATISTICS__ + + // change size and copy old content to new storage + + void * naddr; + if ( unlikely( header->kind.real.blockSize & 2 ) ) { // previous request zero fill + naddr = cmemalignNoStats( nalign, 1, size ); // create new aligned area + } else { + naddr = memalignNoStats( nalign, size ); // create new aligned area + } // if + size_t ndsize = dataStorage( bsize, naddr, header ); // data storage avilable in bucket + // To preserve prior fill, the entire bucket must be copied versus the size. + memcpy( naddr, oaddr, MIN( odsize, ndsize ) ); // copy bytes + free( oaddr ); + return naddr; +} // realloc + + // Local Variables: // // tab-width: 4 //