Index: libcfa/src/heap.cfa =================================================================== --- libcfa/src/heap.cfa (revision 20b461f6dfaa34bf6956e7c62dbbe5430a1fb554) +++ libcfa/src/heap.cfa (revision e7231002bcdfdd0362118b8f0aa1cdc1d9a7e312) @@ -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 : Fri Jul 19 16:07:46 2019 +// Update Count : 548 // @@ -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 ? @@ -745,4 +762,13 @@ return user; } // memalignNoStats + + +// 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