Index: libcfa/src/heap.cfa =================================================================== --- libcfa/src/heap.cfa (revision 613030442f362a4878b5e0a61072d35233a565ed) +++ libcfa/src/heap.cfa (revision 83b52f10c32ca12f8f96a9532884e06dd2d083dd) @@ -10,6 +10,6 @@ // Created On : Tue Dec 19 21:58:35 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu May 9 16:29:12 2019 -// Update Count : 516 +// Last Modified On : Tue Jul 23 14:13:13 2019 +// Update Count : 549 // @@ -31,50 +31,4 @@ -enum { - __CFA_DEFAULT_MMAP_START__ = (512 * 1024 + 1), - __CFA_DEFAULT_HEAP_EXPANSION__ = (1 * 1024 * 1024), -}; - -size_t default_mmap_start() __attribute__(( weak )) { - return __CFA_DEFAULT_MMAP_START__; -} // default_mmap_start - -size_t default_heap_expansion() __attribute__(( weak )) { - return __CFA_DEFAULT_HEAP_EXPANSION__; -} // default_heap_expansion - - -// supported mallopt options -#ifndef M_MMAP_THRESHOLD -#define M_MMAP_THRESHOLD (-1) -#endif // M_TOP_PAD -#ifndef M_TOP_PAD -#define M_TOP_PAD (-2) -#endif // M_TOP_PAD - -#define FASTLOOKUP -#define __STATISTICS__ - -#define SPINLOCK 0 -#define LOCKFREE 1 -#define BUCKETLOCK SPINLOCK -#if BUCKETLOCK == LOCKFREE -#include -#endif // LOCKFREE - -// #comment TD : This defined is significantly different from the __ALIGN__ define from locks.hfa -#define ALIGN 16 - -// enum { NoBucketSizes = 93, // number of buckets sizes -// #ifdef FASTLOOKUP -// LookupSizes = 65536, // number of fast lookup sizes -// #endif // FASTLOOKUP -// }; -#define NoBucketSizes 93 // number of buckets sizes -#ifdef FASTLOOKUP -#define LookupSizes 65536 // number of fast lookup sizes -#endif // FASTLOOKUP - - static bool traceHeap = false; @@ -132,4 +86,18 @@ // return temp; // } // traceHeapTermOff + + +enum { + __CFA_DEFAULT_MMAP_START__ = (512 * 1024 + 1), + __CFA_DEFAULT_HEAP_EXPANSION__ = (1 * 1024 * 1024), +}; + +size_t default_mmap_start() __attribute__(( weak )) { + return __CFA_DEFAULT_MMAP_START__; +} // default_mmap_start + +size_t default_heap_expansion() __attribute__(( weak )) { + return __CFA_DEFAULT_HEAP_EXPANSION__; +} // default_heap_expansion @@ -160,4 +128,24 @@ #endif // __CFA_DEBUG__ +// statically allocated variables => zero filled. +static size_t pageSize; // architecture pagesize +static size_t heapExpand; // sbrk advance +static size_t mmapStart; // cross over point for mmap +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 +#define LOCKFREE 1 +#define BUCKETLOCK SPINLOCK +#if BUCKETLOCK == LOCKFREE +#include +#endif // LOCKFREE + +// 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 struct HeapManager { @@ -234,15 +222,12 @@ }; // HeapManager - static inline size_t getKey( const HeapManager.FreeHeader & freeheader ) { return freeheader.blockSize; } -// statically allocated variables => zero filled. -static size_t pageSize; // architecture pagesize -static size_t heapExpand; // sbrk advance -static size_t mmapStart; // cross over point for mmap -static unsigned int maxBucketsUsed; // maximum number of buckets in use + +#define FASTLOOKUP +#define __STATISTICS__ // Powers of 2 are common allocation sizes, so make powers of 2 generate the minimum required size. -static const unsigned int bucketSizes[NoBucketSizes] @= { // different bucket sizes +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, @@ -259,5 +244,10 @@ 4_194_304 + sizeof(HeapManager.Storage) }; + +static_assert( NoBucketSizes == sizeof(bucketSizes) / sizeof(bucketSizes[0]), "size of bucket array wrong" ); + #ifdef FASTLOOKUP +static_assert( 16 == sizeof(HeapManager.Storage), "size of HeapManager Storage wrong" ); // FIX ME +enum { LookupSizes = 65_536 + 16 }; // number of fast lookup sizes static unsigned char lookup[LookupSizes]; // O(1) lookup for small sizes #endif // FASTLOOKUP @@ -532,4 +522,18 @@ +size_t Bsearchl( unsigned int key, const unsigned int * vals, size_t dim ) { + size_t l = 0, m, h = dim; + while ( l < h ) { + m = (l + h) / 2; + if ( (unsigned int &)(vals[m]) < key ) { // cast away const + l = m + 1; + } else { + h = m; + } // if + } // while + return l; +} // Bsearchl + + static inline void * doMalloc( size_t size ) with ( heapManager ) { HeapManager.Storage * block; // pointer to new block of storage @@ -540,9 +544,22 @@ size_t tsize = size + sizeof(HeapManager.Storage); if ( likely( tsize < mmapStart ) ) { // small size => sbrk - HeapManager.FreeHeader * freeElem = - #ifdef FASTLOOKUP - tsize < LookupSizes ? &freeLists[lookup[tsize]] : - #endif // FASTLOOKUP - bsearchl( tsize, freeLists, (size_t)maxBucketsUsed ); // binary search + size_t posn; + #ifdef FASTLOOKUP + if ( tsize < LookupSizes ) posn = lookup[tsize]; + else + #endif // FASTLOOKUP + posn = Bsearchl( (unsigned int)tsize, bucketSizes, (size_t)maxBucketsUsed ); + HeapManager.FreeHeader * freeElem = &freeLists[posn]; + // #ifdef FASTLOOKUP + // if ( tsize < LookupSizes ) + // freeElem = &freeLists[lookup[tsize]]; + // else + // #endif // FASTLOOKUP + // freeElem = bsearchl( tsize, freeLists, (size_t)maxBucketsUsed ); // binary search + // HeapManager.FreeHeader * freeElem = + // #ifdef FASTLOOKUP + // tsize < LookupSizes ? &freeLists[lookup[tsize]] : + // #endif // FASTLOOKUP + // bsearchl( tsize, freeLists, (size_t)maxBucketsUsed ); // binary search assert( freeElem <= &freeLists[maxBucketsUsed] ); // subscripting error ? assert( tsize <= freeElem->blockSize ); // search failure ? @@ -747,4 +764,13 @@ +// supported mallopt options +#ifndef M_MMAP_THRESHOLD +#define M_MMAP_THRESHOLD (-1) +#endif // M_TOP_PAD +#ifndef M_TOP_PAD +#define M_TOP_PAD (-2) +#endif // M_TOP_PAD + + extern "C" { // The malloc() function allocates size bytes and returns a pointer to the allocated memory. The memory is not @@ -843,5 +869,5 @@ void * area; if ( unlikely( alignment != 0 ) ) { // previous request memalign? - area = memalign( alignment, size ); // create new area + area = memalign( alignment, size ); // create new aligned area } else { area = mallocNoStats( size ); // create new area Index: libcfa/src/stdlib.hfa =================================================================== --- libcfa/src/stdlib.hfa (revision 613030442f362a4878b5e0a61072d35233a565ed) +++ libcfa/src/stdlib.hfa (revision 83b52f10c32ca12f8f96a9532884e06dd2d083dd) @@ -10,6 +10,6 @@ // Created On : Thu Jan 28 17:12:35 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Wed Apr 24 17:35:43 2019 -// Update Count : 352 +// Last Modified On : Tue Jul 23 14:14:59 2019 +// Update Count : 373 // @@ -17,6 +17,8 @@ #include "bits/defs.hfa" +#include "bits/align.hfa" #include // *alloc, strto*, ato* + extern "C" { void * memalign( size_t align, size_t size ); // malloc.h @@ -39,12 +41,15 @@ T * malloc( void ) { - return (T *)(void *)malloc( (size_t)sizeof(T) ); // C malloc + if ( _Alignof(T) <= libAlign() ) return (T *)(void *)malloc( (size_t)sizeof(T) ); // C malloc + else return (T *)memalign( _Alignof(T), sizeof(T) ); } // malloc T * calloc( size_t dim ) { - return (T *)(void *)calloc( dim, sizeof(T) ); // C calloc + if ( _Alignof(T) <= libAlign() )return (T *)(void *)calloc( dim, sizeof(T) ); // C calloc + else return (T *)cmemalign( _Alignof(T), dim, sizeof(T) ); } // calloc T * realloc( T * ptr, size_t size ) { + if ( unlikely( ptr == 0 ) ) return malloc(); return (T *)(void *)realloc( (void *)ptr, size ); } // realloc @@ -66,28 +71,27 @@ T * alloc( void ) { - return (T *)(void *)malloc( (size_t)sizeof(T) ); // C malloc + return malloc(); } // alloc T * alloc( char fill ) { - T * ptr = (T *)(void *)malloc( (size_t)sizeof(T) ); // C malloc + T * ptr; + if ( _Alignof(T) <= libAlign() ) ptr = (T *)(void *)malloc( (size_t)sizeof(T) ); // C malloc + else ptr = (T *)memalign( _Alignof(T), sizeof(T) ); return (T *)memset( ptr, (int)fill, sizeof(T) ); // initialize with fill value } // alloc T * alloc( size_t dim ) { - return (T *)(void *)malloc( dim * (size_t)sizeof(T) ); // C malloc + if ( _Alignof(T) <= libAlign() ) return (T *)(void *)malloc( dim * (size_t)sizeof(T) ); // C malloc + else return (T *)memalign( _Alignof(T), dim * sizeof(T) ); } // alloc T * alloc( size_t dim, char fill ) { - T * ptr = (T *)(void *)malloc( dim * (size_t)sizeof(T) ); // C calloc - return (T *)memset( ptr, (int)fill, dim * sizeof(T) ); // initialize with fill value + return (T *)memset( (T *)alloc( dim ), (int)fill, dim * sizeof(T) ); // initialize with fill value } // alloc T * alloc( T ptr[], size_t dim ) { - return (T *)(void *)realloc( (void *)ptr, dim * (size_t)sizeof(T) ); // C realloc - } // alloc -} // distribution - - -forall( dtype T | sized(T) ) T * alloc( T ptr[], size_t dim, char fill ); + return realloc( ptr, dim * sizeof(T) ); + } // alloc +} // distribution @@ -107,14 +111,13 @@ T * align_alloc( size_t align, size_t dim, char fill ) { - T * ptr; if ( fill == '\0' ) { - ptr = (T *)cmemalign( align, dim, sizeof(T) ); + return (T *)cmemalign( align, dim, sizeof(T) ); } else { - ptr = (T *)memalign( align, dim * sizeof(T) ); - return (T *)memset( ptr, (int)fill, dim * sizeof(T) ); + return (T *)memset( (T *)memalign( align, dim * sizeof(T) ), (int)fill, dim * sizeof(T) ); } // if - return ptr; - } // align_alloc -} // distribution + } // align_alloc +} // distribution + +forall( dtype T | sized(T) ) T * alloc( T ptr[], size_t dim, char fill );