Changeset 9c43854


Ignore:
Timestamp:
May 17, 2020, 9:06:28 PM (16 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast, new-ast-unique-expr
Children:
893da07
Parents:
2223c80
Message:

move allocation "size" field, allow alternative lock-free stack for bucket free-list

Location:
libcfa/src
Files:
1 added
1 edited

Legend:

Unmodified
Added
Removed
  • libcfa/src/heap.cfa

    r2223c80 r9c43854  
    1010// Created On       : Tue Dec 19 21:58:35 2017
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Wed May  6 17:29:26 2020
    13 // Update Count     : 727
     12// Last Modified On : Sun May 17 20:58:17 2020
     13// Update Count     : 762
    1414//
    1515
     
    128128#define LOCKFREE 1
    129129#define BUCKETLOCK SPINLOCK
    130 #if BUCKETLOCK == LOCKFREE
    131 #include <uStackLF.h>
     130#if BUCKETLOCK == SPINLOCK
     131#elif BUCKETLOCK == LOCKFREE
     132#include <stackLockFree.hfa>
     133#else
     134        #error undefined lock type for bucket lock
    132135#endif // LOCKFREE
    133136
     
    137140
    138141struct HeapManager {
    139 //      struct FreeHeader;                                                                      // forward declaration
    140 
    141142        struct Storage {
    142143                struct Header {                                                                 // header
     
    146147                                                struct {                                                // 4-byte word => 8-byte header, 8-byte word => 16-byte header
    147148                                                        #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ && __SIZEOF_POINTER__ == 4
    148                                                         uint32_t padding;                       // unused, force home/blocksize to overlay alignment in fake header
     149                                                        uint64_t padding;                       // unused, force home/blocksize to overlay alignment in fake header
    149150                                                        #endif // __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ && __SIZEOF_POINTER__ == 4
    150151
    151152                                                        union {
    152 //                                                              FreeHeader * home;              // allocated block points back to home locations (must overlay alignment)
     153                                                                // FreeHeader * home;           // allocated block points back to home locations (must overlay alignment)
    153154                                                                // 2nd low-order bit => zero filled
    154155                                                                void * home;                    // allocated block points back to home locations (must overlay alignment)
    155156                                                                size_t blockSize;               // size for munmap (must overlay alignment)
    156                                                                 #if BUCKLOCK == SPINLOCK
     157                                                                #if BUCKETLOCK == SPINLOCK
    157158                                                                Storage * next;                 // freed block points next freed block of same size
    158159                                                                #endif // SPINLOCK
    159160                                                        };
     161                                                        size_t size;                            // allocation size in bytes
    160162
    161163                                                        #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ && __SIZEOF_POINTER__ == 4
    162                                                         uint32_t padding;                       // unused, force home/blocksize to overlay alignment in fake header
     164                                                        uint64_t padding;                       // unused, force home/blocksize to overlay alignment in fake header
    163165                                                        #endif // __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ && __SIZEOF_POINTER__ == 4
    164166                                                };
    165                                                 // future code
    166                                                 #if BUCKLOCK == LOCKFREE
    167                                                 Stack<Storage>::Link next;              // freed block points next freed block of same size (double-wide)
     167                                                #if BUCKETLOCK == LOCKFREE
     168                                                Link(Storage) next;                             // freed block points next freed block of same size (double-wide)
    168169                                                #endif // LOCKFREE
    169170                                        };
    170171                                } real; // RealHeader
     172
    171173                                struct FakeHeader {
    172174                                        #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
    173                                         // 1st low-order bit => fake header & alignment
    174                                         uint32_t alignment;
     175                                        uint32_t alignment;                                     // 1st low-order bit => fake header & alignment
    175176                                        #endif // __ORDER_LITTLE_ENDIAN__
    176177
     
    182183                                } fake; // FakeHeader
    183184                        } kind; // Kind
    184                         size_t size;                                                            // allocation size in bytes
    185185                } header; // Header
    186186                char pad[libAlign() - sizeof( Header )];
     
    191191
    192192        struct FreeHeader {
    193                 #if BUCKLOCK == SPINLOCK
     193                #if BUCKETLOCK == SPINLOCK
    194194                __spinlock_t lock;                                                              // must be first field for alignment
    195195                Storage * freeList;
    196                 #elif BUCKLOCK == LOCKFREE
    197                 // future code
    198                 StackLF<Storage> freeList;
    199196                #else
    200                         #error undefined lock type for bucket lock
    201                 #endif // SPINLOCK
     197                StackLF(Storage) freeList;
     198                #endif // BUCKETLOCK
    202199                size_t blockSize;                                                               // size of allocations on this list
    203200        }; // FreeHeader
     
    211208        size_t heapRemaining;                                                           // amount of storage not allocated in the current chunk
    212209}; // HeapManager
     210
     211#if BUCKETLOCK == LOCKFREE
     212static inline Link(HeapManager.Storage) * getNext( HeapManager.Storage * this ) { return &this->header.kind.real.next; }
     213static inline void ?{}( HeapManager.FreeHeader & ) {}
     214static inline void ^?{}( HeapManager.FreeHeader & ) {}
     215#endif // LOCKFREE
    213216
    214217static inline size_t getKey( const HeapManager.FreeHeader & freeheader ) { return freeheader.blockSize; }
     
    251254static bool heapBoot = 0;                                                               // detect recursion during boot
    252255#endif // __CFA_DEBUG__
     256
     257// The constructor for heapManager is called explicitly in memory_startup.
    253258static HeapManager heapManager __attribute__(( aligned (128) )) @= {}; // size of cache line to prevent false sharing
    254259
     
    354359
    355360
    356 // static inline void noMemory() {
    357 //      abort( "Heap memory exhausted at %zu bytes.\n"
    358 //                 "Possible cause is very large memory allocation and/or large amount of unfreed storage allocated by the program or system/library routines.",
    359 //                 ((char *)(sbrk( 0 )) - (char *)(heapManager.heapBegin)) );
    360 // } // noMemory
    361 
    362 
    363361// thunk problem
    364362size_t Bsearchl( unsigned int key, const unsigned int * vals, size_t dim ) {
     
    406404
    407405
     406// static inline void noMemory() {
     407//      abort( "Heap memory exhausted at %zu bytes.\n"
     408//                 "Possible cause is very large memory allocation and/or large amount of unfreed storage allocated by the program or system/library routines.",
     409//                 ((char *)(sbrk( 0 )) - (char *)(heapManager.heapBegin)) );
     410// } // noMemory
     411
     412
    408413static inline void checkAlign( size_t alignment ) {
    409414        if ( alignment < libAlign() || ! libPow2( alignment ) ) {
     
    433438
    434439
    435 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 ) {
     440static inline bool headers( const char name[] __attribute__(( unused )), void * addr, HeapManager.Storage.Header *& header, HeapManager.FreeHeader *& freeElem,
     441                                                        size_t & size, size_t & alignment ) with( heapManager ) {
    436442        header = headerAddr( addr );
    437443
     
    465471
    466472
    467 static inline void * extend( size_t size ) with ( heapManager ) {
     473static inline void * extend( size_t size ) with( heapManager ) {
    468474        lock( extlock __cfaabi_dbg_ctx2 );
    469475        ptrdiff_t rem = heapRemaining - size;
     
    496502
    497503
    498 static inline void * doMalloc( size_t size ) with ( heapManager ) {
     504static inline void * doMalloc( size_t size ) with( heapManager ) {
    499505        HeapManager.Storage * block;                                            // pointer to new block of storage
    500506
     
    529535                // Spin until the lock is acquired for this particular size of block.
    530536
    531                 #if defined( SPINLOCK )
     537                #if BUCKETLOCK == SPINLOCK
    532538                lock( freeElem->lock __cfaabi_dbg_ctx2 );
    533539                block = freeElem->freeList;                                             // remove node from stack
    534540                #else
    535                 block = freeElem->freeList.pop();
    536                 #endif // SPINLOCK
     541                block = pop( freeElem->freeList );
     542                #endif // BUCKETLOCK
    537543                if ( unlikely( block == 0p ) ) {                                // no free block ?
    538                         #if defined( SPINLOCK )
     544                        #if BUCKETLOCK == SPINLOCK
    539545                        unlock( freeElem->lock );
    540                         #endif // SPINLOCK
     546                        #endif // BUCKETLOCK
    541547
    542548                        // Freelist for that size was empty, so carve it out of the heap if there's enough left, or get some more
     
    544550
    545551                        block = (HeapManager.Storage *)extend( tsize ); // mutual exclusion on call
    546   if ( unlikely( block == 0p ) ) return 0p;
    547                 #if defined( SPINLOCK )
     552        if ( unlikely( block == 0p ) ) return 0p;
     553                #if BUCKETLOCK == SPINLOCK
    548554                } else {
    549555                        freeElem->freeList = block->header.kind.real.next;
    550556                        unlock( freeElem->lock );
    551                 #endif // SPINLOCK
     557                #endif // BUCKETLOCK
    552558                } // if
    553559
     
    572578        } // if
    573579
    574         block->header.size = size;                                                      // store allocation size
     580        block->header.kind.real.size = size;                            // store allocation size
    575581        void * addr = &(block->data);                                           // adjust off header to user bytes
    576582
     
    591597
    592598
    593 static inline void doFree( void * addr ) with ( heapManager ) {
     599static inline void doFree( void * addr ) with( heapManager ) {
    594600        #ifdef __CFA_DEBUG__
    595601        if ( unlikely( heapManager.heapBegin == 0p ) ) {
     
    623629                free_storage += size;
    624630                #endif // __STATISTICS__
    625                 #if defined( SPINLOCK )
     631                #if BUCKETLOCK == SPINLOCK
    626632                lock( freeElem->lock __cfaabi_dbg_ctx2 );               // acquire spin lock
    627633                header->kind.real.next = freeElem->freeList;    // push on stack
     
    629635                unlock( freeElem->lock );                                               // release spin lock
    630636                #else
    631                 freeElem->freeList.push( *(HeapManager.Storage *)header );
    632                 #endif // SPINLOCK
     637                push( freeElem->freeList, *(HeapManager.Storage *)header );
     638                #endif // BUCKETLOCK
    633639        } // if
    634640
     
    645651
    646652
    647 size_t prtFree( HeapManager & manager ) with ( manager ) {
     653size_t prtFree( HeapManager & manager ) with( manager ) {
    648654        size_t total = 0;
    649655        #ifdef __STATISTICS__
     
    657663                #endif // __STATISTICS__
    658664
    659                 #if defined( SPINLOCK )
     665                #if BUCKETLOCK == SPINLOCK
    660666                for ( HeapManager.Storage * p = freeLists[i].freeList; p != 0p; p = p->header.kind.real.next ) {
    661667                #else
    662                 for ( HeapManager.Storage * p = freeLists[i].freeList.top(); p != 0p; p = p->header.kind.real.next.top ) {
    663                 #endif // SPINLOCK
     668                for ( HeapManager.Storage * p = top( freeLists[i].freeList ); p != 0p; /* p = getNext( p )->top */) {
     669                        typeof(p) temp = getNext( p )->top;                     // FIX ME: direct assignent fails, initialization works
     670                        p = temp;
     671                #endif // BUCKETLOCK
    664672                        total += size;
    665673                        #ifdef __STATISTICS__
     
    681689
    682690
    683 static void ?{}( HeapManager & manager ) with ( manager ) {
     691static void ?{}( HeapManager & manager ) with( manager ) {
    684692        pageSize = sysconf( _SC_PAGESIZE );
    685693
     
    10951103                        header = realHeader( header );                          // backup from fake to real header
    10961104                } // if
    1097                 return header->size;
     1105                return header->kind.real.size;
    10981106        } // malloc_size
    10991107
     
    11051113                        header = realHeader( header );                          // backup from fake to real header
    11061114                } // if
    1107                 size_t ret = header->size;
    1108                 header->size = size;
     1115                size_t ret = header->kind.real.size;
     1116                header->kind.real.size = size;
    11091117                return ret;
    11101118        } // $malloc_size_set
Note: See TracChangeset for help on using the changeset viewer.