Index: libcfa/src/heap.cfa =================================================================== --- libcfa/src/heap.cfa (revision f586539f2394d91afc6e6cdba2aa9a2bd43a876b) +++ libcfa/src/heap.cfa (revision cfbc703dfdcd257acc2437311c5a25ee33932766) @@ -10,6 +10,6 @@ // Created On : Tue Dec 19 21:58:35 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Fri Mar 6 10:14:52 2020 -// Update Count : 650 +// Last Modified On : Wed Apr 1 15:59:53 2020 +// Update Count : 692 // @@ -150,4 +150,5 @@ union { // FreeHeader * home; // allocated block points back to home locations (must overlay alignment) + // 2nd low-order bit => zero filled void * home; // allocated block points back to home locations (must overlay alignment) size_t blockSize; // size for munmap (must overlay alignment) @@ -169,5 +170,6 @@ struct FakeHeader { #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ - uint32_t alignment; // low-order bits of home/blockSize used for tricks + // 1st low-order bit => fake header & alignment + uint32_t alignment; #endif // __ORDER_LITTLE_ENDIAN__ @@ -179,4 +181,5 @@ } fake; // FakeHeader } kind; // Kind + uint32_t dimension; // used by calloc-like to remember number of array elements } header; // Header char pad[libAlign() - sizeof( Header )]; @@ -268,4 +271,6 @@ static unsigned long long int cmemalign_storage; static unsigned int cmemalign_calls; +static unsigned long long int resize_storage; +static unsigned int resize_calls; static unsigned long long int realloc_storage; static unsigned int realloc_calls; @@ -282,4 +287,5 @@ " memalign: calls %u / storage %llu\n" " cmemalign: calls %u / storage %llu\n" + " resize: calls %u / storage %llu\n" " realloc: calls %u / storage %llu\n" " free: calls %u / storage %llu\n" @@ -291,4 +297,5 @@ memalign_calls, memalign_storage, cmemalign_calls, cmemalign_storage, + resize_calls, resize_storage, realloc_calls, realloc_storage, free_calls, free_storage, @@ -310,4 +317,5 @@ "\n" "\n" + "\n" "\n" "\n" @@ -320,4 +328,5 @@ memalign_calls, memalign_storage, cmemalign_calls, cmemalign_storage, + resize_calls, resize_storage, realloc_calls, realloc_storage, free_calls, free_storage, @@ -339,11 +348,4 @@ -static inline void checkAlign( size_t 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 - - static inline bool setHeapExpand( size_t value ) { if ( heapExpand < pageSize ) return true; @@ -380,4 +382,29 @@ +// <-------+----------------------------------------------------> bsize (bucket size) +// |header |addr +//================================================================================== +// align/offset | +// <-----------------<------------+-----------------------------> bsize (bucket size) +// |fake-header | addr +#define headerAddr( addr ) ((HeapManager.Storage.Header *)( (char *)addr - sizeof(HeapManager.Storage) )) +#define realHeader( header ) ((HeapManager.Storage.Header *)((char *)header - header->kind.fake.offset)) + +// <-------<<--------------------- dsize ---------------------->> bsize (bucket size) +// |header |addr +//================================================================================== +// align/offset | +// <------------------------------<<---------- dsize --------->>> bsize (bucket size) +// |fake-header |addr +#define dataStorage( bsize, addr, header ) (bsize - ( (char *)addr - (char *)header )) + + +static inline void checkAlign( size_t 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 + + static inline void checkHeader( bool check, const char name[], void * addr ) { if ( unlikely( check ) ) { // bad address ? @@ -391,29 +418,11 @@ 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; alignment = header->kind.fake.alignment & -2; // remove flag from value #ifdef __CFA_DEBUG__ checkAlign( alignment ); // check alignment #endif // __CFA_DEBUG__ - header = (HeapManager.Storage.Header *)((char *)header - offset); + header = realHeader( header ); // backup from fake to real header } // if } // fakeHeader - - -// <-------+----------------------------------------------------> bsize (bucket size) -// |header |addr -//================================================================================== -// | alignment -// <-----------------<------------+-----------------------------> bsize (bucket size) -// |fake-header | addr -#define headerAddr( addr ) ((HeapManager.Storage.Header *)( (char *)addr - sizeof(HeapManager.Storage) )) - -// <-------<<--------------------- dsize ---------------------->> bsize (bucket size) -// |header |addr -//================================================================================== -// | alignment -// <------------------------------<<---------- dsize --------->>> bsize (bucket size) -// |fake-header |addr -#define dataStorage( bsize, addr, header ) (bsize - ( (char *)addr - (char *)header )) @@ -749,4 +758,6 @@ memset( addr, '\0', bsize - sizeof(HeapManager.Storage) ); // set to zeros + assert( noOfElems <= UINT32_MAX ); + header->dimension = noOfElems; // store number of array elements header->kind.real.blockSize |= 2; // mark as zero filled return addr; @@ -803,6 +814,8 @@ #endif // __CFA_DEBUG__ memset( addr, '\0', dataStorage( bsize, addr, header ) ); // set to zeros - header->kind.real.blockSize |= 2; // mark as zero filled - + + assert( noOfElems <= UINT32_MAX ); + header->dimension = noOfElems; // store initial array size + header->kind.real.blockSize |= 2; // mark as zero filled return addr; } // cmemalignNoStats @@ -842,13 +855,44 @@ } // calloc - // Change the size of the memory block pointed to by ptr to size bytes. The contents shall 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 shall 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. + // Change the size of the memory block pointed to by ptr to size bytes. The contents are undefined. 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 * resize( void * oaddr, size_t size ) { + #ifdef __STATISTICS__ + __atomic_add_fetch( &resize_calls, 1, __ATOMIC_SEQ_CST ); + __atomic_add_fetch( &resize_storage, size, __ATOMIC_SEQ_CST ); + #endif // __STATISTICS__ + + // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned. + if ( unlikely( size == 0 ) ) { free( oaddr ); return mallocNoStats( size ); } // special cases + if ( unlikely( oaddr == 0p ) ) return mallocNoStats( size ); + + HeapManager.Storage.Header * header; + HeapManager.FreeHeader * freeElem; + size_t bsize, oalign = 0; + headers( "resize", oaddr, header, freeElem, bsize, oalign ); + size_t odsize = dataStorage( bsize, oaddr, header ); // data storage available in bucket + + // same size, DO NOT preserve STICKY PROPERTIES. + if ( oalign == 0 && size <= odsize && odsize <= size * 2 ) { // allow 50% wasted storage for smaller size + header->kind.real.blockSize &= -2; // no alignment and turn off 0 fill + return oaddr; + } // if + + // change size, DO NOT preserve STICKY PROPERTIES. + void * naddr = mallocNoStats( size ); // create new area + free( oaddr ); + return naddr; + } // resize + + + // Same as resize but the contents shall be unchanged in the range from the start of the region up to the minimum of + // the old and new sizes. void * realloc( void * oaddr, size_t size ) { #ifdef __STATISTICS__ __atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST ); + __atomic_add_fetch( &realloc_storage, size, __ATOMIC_SEQ_CST ); #endif // __STATISTICS__ @@ -866,13 +910,6 @@ // 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 oaddr; } // if - - #ifdef __STATISTICS__ - __atomic_add_fetch( &realloc_storage, size, __ATOMIC_SEQ_CST ); - #endif // __STATISTICS__ // change size and copy old content to new storage @@ -985,5 +1022,5 @@ return header->kind.fake.alignment & -2; // remove flag from value } else { - return libAlign (); // minimum alignment + return libAlign(); // minimum alignment } // if } // malloc_alignment @@ -995,7 +1032,18 @@ HeapManager.Storage.Header * header = headerAddr( addr ); if ( (header->kind.fake.alignment & 1) == 1 ) { // fake header ? - header = (HeapManager.Storage.Header *)((char *)header - header->kind.fake.offset); + header = realHeader( header ); // backup from fake to real header } // if return (header->kind.real.blockSize & 2) != 0; // zero filled (calloc/cmemalign) ? + } // malloc_zero_fill + + + // Returns number of elements if the allocation is for an array, i.e., by calloc(). + size_t malloc_dimension( void * addr ) { + 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 ? + header = realHeader( header ); // backup from fake to real header + } // if + return header->dimension; // array (calloc/cmemalign) } // malloc_zero_fill @@ -1079,12 +1127,14 @@ // Must have CFA linkage to overload with C linkage realloc. -void * realloc( void * oaddr, size_t nalign, size_t size ) { +void * resize( void * oaddr, size_t nalign, size_t size ) { #ifdef __STATISTICS__ - __atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST ); + __atomic_add_fetch( &resize_calls, 1, __ATOMIC_SEQ_CST ); + __atomic_add_fetch( &resize_storage, size, __ATOMIC_SEQ_CST ); #endif // __STATISTICS__ // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned. - if ( unlikely( size == 0 ) ) { free( oaddr ); return mallocNoStats( size ); } // special cases - if ( unlikely( oaddr == 0p ) ) return mallocNoStats( size ); + if ( unlikely( size == 0 ) ) { free( oaddr ); return memalignNoStats( nalign, size ); } // special cases + if ( unlikely( oaddr == 0p ) ) return memalignNoStats( nalign, size ); + if ( unlikely( nalign == 0 ) ) nalign = libAlign(); // reset alignment to minimum @@ -1097,17 +1147,18 @@ HeapManager.FreeHeader * freeElem; size_t bsize, oalign = 0; - headers( "realloc", oaddr, header, freeElem, bsize, oalign ); + headers( "resize", 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 + if ( oalign <= nalign && (uintptr_t)oaddr % nalign == 0 ) { // <= alignment and new alignment happens to match + if ( oalign >= libAlign() ) { // fake header ? + headerAddr( oaddr )->kind.fake.alignment = nalign | 1; // update alignment (could be the same) + } // if + if ( size <= odsize && odsize <= size * 2 ) { // allow 50% wasted storage for smaller size + header->kind.real.blockSize &= -2; // turn off 0 fill + return oaddr; + } // if + } // if + + // change size void * naddr; @@ -1118,6 +1169,49 @@ } // if + free( oaddr ); + return naddr; +} // resize + + +void * realloc( void * oaddr, size_t nalign, size_t 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 <= nalign && (uintptr_t)oaddr % nalign == 0 ) { // <= alignment and new alignment happens to match + if ( oalign >= libAlign() ) { // fake header ? + headerAddr( oaddr )->kind.fake.alignment = nalign | 1; // update alignment (could be the same) + } // if + return realloc( oaddr, size ); + } // if + + // change size and copy old content to new storage + + #ifdef __STATISTICS__ + __atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST ); + __atomic_add_fetch( &realloc_storage, size, __ATOMIC_SEQ_CST ); + #endif // __STATISTICS__ + + // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned. + if ( unlikely( size == 0 ) ) { free( oaddr ); return memalignNoStats( nalign, size ); } // special cases + if ( unlikely( oaddr == 0p ) ) return memalignNoStats( nalign, size ); + + 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 + headers( "realloc", naddr, header, freeElem, bsize, oalign ); - size_t ndsize = dataStorage( bsize, naddr, header ); // data storage avilable in bucket + size_t ndsize = dataStorage( bsize, naddr, header ); // data storage available in bucket // To preserve prior fill, the entire bucket must be copied versus the size. memcpy( naddr, oaddr, MIN( odsize, ndsize ) ); // copy bytes Index: libcfa/src/stdhdr/malloc.h =================================================================== --- libcfa/src/stdhdr/malloc.h (revision f586539f2394d91afc6e6cdba2aa9a2bd43a876b) +++ libcfa/src/stdhdr/malloc.h (revision cfbc703dfdcd257acc2437311c5a25ee33932766) @@ -10,6 +10,6 @@ // Created On : Thu Jul 20 15:58:16 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Sat Aug 11 09:06:31 2018 -// Update Count : 10 +// Last Modified On : Sun Mar 8 10:01:20 2020 +// Update Count : 11 // @@ -31,8 +31,9 @@ extern "C" { +void * cmemalign( size_t alignment, size_t noOfElems, size_t elemSize ); size_t malloc_alignment( void * ); bool malloc_zero_fill( void * ); +size_t malloc_dimension( void * ); int malloc_stats_fd( int fd ); -void * cmemalign( size_t alignment, size_t noOfElems, size_t elemSize ); } // extern "C" Index: libcfa/src/stdlib.cfa =================================================================== --- libcfa/src/stdlib.cfa (revision f586539f2394d91afc6e6cdba2aa9a2bd43a876b) +++ libcfa/src/stdlib.cfa (revision cfbc703dfdcd257acc2437311c5a25ee33932766) @@ -10,6 +10,6 @@ // Created On : Thu Jan 28 17:10:29 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Feb 4 08:27:08 2020 -// Update Count : 486 +// Last Modified On : Tue Mar 31 13:26:46 2020 +// Update Count : 495 // @@ -20,5 +20,4 @@ #define _XOPEN_SOURCE 600 // posix_memalign, *rand48 #include // memcpy, memset -#include // malloc_usable_size //#include // fabsf, fabs, fabsl #include // _Complex_I @@ -38,4 +37,14 @@ } // alloc_set + T * alloc_set( T ptr[], size_t dim, T fill ) { // realloc array with fill + size_t olen = malloc_usable_size( ptr ); // current allocation + void * nptr = (void *)realloc( (void *)ptr, dim * sizeof(T) ); // C realloc + size_t nlen = malloc_usable_size( nptr ); // new allocation + if ( nlen > olen ) { // larger ? + for ( i; dim ) { memcpy( &ptr[i], &fill, sizeof(T) ); } // initialize with fill value + } // if + return (T *)nptr; + } // alloc_align_set + T * alloc_align_set( T ptr[], size_t align, char fill ) { // aligned realloc with fill size_t olen = malloc_usable_size( ptr ); // current allocation @@ -45,4 +54,15 @@ if ( nlen > olen ) { // larger ? memset( (char *)nptr + olen, (int)fill, nlen - olen ); // initialize added storage + } // if + return (T *)nptr; + } // alloc_align_set + + T * alloc_align_set( T ptr[], size_t align, size_t dim, T fill ) { // aligned realloc with fill + size_t olen = malloc_usable_size( ptr ); // current allocation + void * nptr = (void *)realloc( (void *)ptr, align, sizeof(T) ); // CFA realloc + // char * nptr = alloc_align( ptr, align ); + size_t nlen = malloc_usable_size( nptr ); // new allocation + if ( nlen > olen ) { // larger ? + for ( i; dim ) { memcpy( &ptr[i], &fill, sizeof(T) ); } // initialize with fill value } // if return (T *)nptr; Index: libcfa/src/stdlib.hfa =================================================================== --- libcfa/src/stdlib.hfa (revision f586539f2394d91afc6e6cdba2aa9a2bd43a876b) +++ libcfa/src/stdlib.hfa (revision cfbc703dfdcd257acc2437311c5a25ee33932766) @@ -10,6 +10,6 @@ // Created On : Thu Jan 28 17:12:35 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Mar 5 11:29:06 2020 -// Update Count : 407 +// Last Modified On : Wed Apr 1 18:38:41 2020 +// Update Count : 429 // @@ -24,9 +24,12 @@ extern "C" { void * memalign( size_t align, size_t size ); // malloc.h - void * cmemalign( size_t alignment, size_t noOfElems, size_t elemSize ); // CFA heap + size_t malloc_usable_size( void * ptr ); // malloc.h + void * cmemalign( size_t alignment, size_t noOfElems, size_t elemSize ); // CFA heap void * memset( void * dest, int fill, size_t size ); // string.h void * memcpy( void * dest, const void * src, size_t size ); // string.h + void * resize( void * oaddr, size_t size ); // CFA heap } // extern "C" +void * resize( void * oaddr, size_t nalign, size_t size ); // CFA heap void * realloc( void * oaddr, size_t nalign, size_t size ); // CFA heap @@ -72,5 +75,7 @@ return posix_memalign( (void **)ptr, align, sizeof(T) ); // C posix_memalign } // posix_memalign - +} // distribution + +static inline forall( dtype T | sized(T) ) { // Cforall safe general allocation, fill, resize, array @@ -84,6 +89,23 @@ } // alloc - T * alloc( T ptr[], size_t dim ) { // realloc - return (T *)(void *)realloc( (void *)ptr, dim * sizeof(T) ); // C realloc + forall( dtype S | sized(S) ) + T * alloc( S ptr[], size_t dim = 1 ) { // singleton/array resize + size_t len = malloc_usable_size( ptr ); // current bucket size + if ( sizeof(T) * dim > len ) { // not enough space ? + T * temp = alloc( dim ); // new storage + free( ptr ); // free old storage + return temp; + } else { + return (T *)ptr; + } // if + } // alloc + + T * alloc( T ptr[], size_t dim, bool copy = true ) { + if ( copy ) { // realloc + return (T *)(void *)realloc( (void *)ptr, dim * sizeof(T) ); // C realloc + } else { + struct __Unknown {}; + return alloc( (__Unknown *)ptr, dim ); // reuse, cheat making T/S different types + } // if } // alloc @@ -113,4 +135,5 @@ forall( dtype T | sized(T) ) { T * alloc_set( T ptr[], size_t dim, char fill ); // realloc array with fill + T * alloc_set( T ptr[], size_t dim, T fill ); // realloc array with fill } // distribution @@ -126,4 +149,9 @@ T * alloc_align( T ptr[], size_t align ) { // aligned realloc array return (T *)(void *)realloc( (void *)ptr, align, sizeof(T) ); // CFA realloc + } // alloc_align + + forall( dtype S | sized(S) ) + T * alloc_align( S ptr[], size_t align ) { // aligned reuse array + return (T *)(void *)resize( (void *)ptr, align, sizeof(T) ); // CFA realloc } // alloc_align @@ -156,5 +184,8 @@ forall( dtype T | sized(T) ) { + T * alloc_align_set( T ptr[], size_t align, char fill ); // aligned realloc with fill + T * alloc_align_set( T ptr[], size_t align, T fill ); // aligned realloc with fill T * alloc_align_set( T ptr[], size_t align, size_t dim, char fill ); // aligned realloc array with fill + T * alloc_align_set( T ptr[], size_t align, size_t dim, T fill ); // aligned realloc array with fill } // distribution