Changeset 9c438546

Timestamp:

May 17, 2020, 9:06:28 PM (4 years ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

893da07

Parents:

2223c80

Message:

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

Location:

libcfa/src

Files:

• containers/stackLockFree.hfa (added)
• heap.cfa (modified) (24 diffs)

libcfa/src/heap.cfa

@@ -10 +10 @@
 // Created On       : Tue Dec 19 21:58:35 2017
 // Last Modified By : Peter A. Buhr
-// Last Modified On : Wed May  6 17:29:26 2020
-// Update Count     : 727
+// Last Modified On : Sun May 17 20:58:17 2020
+// Update Count     : 762
 //
 
@@ -128 +128 @@
 #define LOCKFREE 1
 #define BUCKETLOCK SPINLOCK
-#if BUCKETLOCK == LOCKFREE
-#include <uStackLF.h>
+#if BUCKETLOCK == SPINLOCK
+#elif BUCKETLOCK == LOCKFREE
+#include <stackLockFree.hfa>
+#else
+        #error undefined lock type for bucket lock
 #endif // LOCKFREE
 
@@ -137 +140 @@
 
 struct HeapManager {
-//      struct FreeHeader;                                                                      // forward declaration
-
         struct Storage {
                 struct Header {                                                                 // header
@@ -146 +147 @@
                                                 struct {                                                // 4-byte word => 8-byte header, 8-byte word => 16-byte header
                                                         #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ && __SIZEOF_POINTER__ == 4
-                                                        uint32_t padding;                       // unused, force home/blocksize to overlay alignment in fake header
+                                                        uint64_t padding;                       // unused, force home/blocksize to overlay alignment in fake header
                                                         #endif // __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ && __SIZEOF_POINTER__ == 4
 
                                                         union {
-//                                                              FreeHeader * home;              // allocated block points back to home locations (must overlay alignment)
+                                                                // 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)
-                                                                #if BUCKLOCK == SPINLOCK
+                                                                #if BUCKETLOCK == SPINLOCK
                                                                 Storage * next;                 // freed block points next freed block of same size
                                                                 #endif // SPINLOCK
                                                         };
+                                                        size_t size;                            // allocation size in bytes
 
                                                         #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ && __SIZEOF_POINTER__ == 4
-                                                        uint32_t padding;                       // unused, force home/blocksize to overlay alignment in fake header
+                                                        uint64_t padding;                       // unused, force home/blocksize to overlay alignment in fake header
                                                         #endif // __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ && __SIZEOF_POINTER__ == 4
                                                 };
-                                                // future code
-                                                #if BUCKLOCK == LOCKFREE
-                                                Stack<Storage>::Link next;              // freed block points next freed block of same size (double-wide)
+                                                #if BUCKETLOCK == LOCKFREE
+                                                Link(Storage) next;                             // freed block points next freed block of same size (double-wide)
                                                 #endif // LOCKFREE
                                         };
                                 } real; // RealHeader
+
                                 struct FakeHeader {
                                         #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
-                                        // 1st low-order bit => fake header & alignment
-                                        uint32_t alignment;
+                                        uint32_t alignment;                                     // 1st low-order bit => fake header & alignment
                                         #endif // __ORDER_LITTLE_ENDIAN__
 
@@ -182 +183 @@
                                 } fake; // FakeHeader
                         } kind; // Kind
-                        size_t size;                                                            // allocation size in bytes
                 } header; // Header
                 char pad[libAlign() - sizeof( Header )];
@@ -191 +191 @@
 
         struct FreeHeader {
-                #if BUCKLOCK == SPINLOCK
+                #if BUCKETLOCK == SPINLOCK
                 __spinlock_t lock;                                                              // must be first field for alignment
                 Storage * freeList;
-                #elif BUCKLOCK == LOCKFREE
-                // future code
-                StackLF<Storage> freeList;
                 #else
-                        #error undefined lock type for bucket lock
-                #endif // SPINLOCK
+                StackLF(Storage) freeList;
+                #endif // BUCKETLOCK
                 size_t blockSize;                                                               // size of allocations on this list
         }; // FreeHeader
@@ -211 +208 @@
         size_t heapRemaining;                                                           // amount of storage not allocated in the current chunk
 }; // HeapManager
+
+#if BUCKETLOCK == LOCKFREE
+static inline Link(HeapManager.Storage) * getNext( HeapManager.Storage * this ) { return &this->header.kind.real.next; }
+static inline void ?{}( HeapManager.FreeHeader & ) {}
+static inline void ^?{}( HeapManager.FreeHeader & ) {}
+#endif // LOCKFREE
 
 static inline size_t getKey( const HeapManager.FreeHeader & freeheader ) { return freeheader.blockSize; }
@@ -251 +254 @@
 static bool heapBoot = 0;                                                               // detect recursion during boot
 #endif // __CFA_DEBUG__
+
+// The constructor for heapManager is called explicitly in memory_startup.
 static HeapManager heapManager __attribute__(( aligned (128) )) @= {}; // size of cache line to prevent false sharing
 
@@ -354 +359 @@
 
 
-// static inline void noMemory() {
-//      abort( "Heap memory exhausted at %zu bytes.\n"
-//                 "Possible cause is very large memory allocation and/or large amount of unfreed storage allocated by the program or system/library routines.",
-//                 ((char *)(sbrk( 0 )) - (char *)(heapManager.heapBegin)) );
-// } // noMemory
-
-
 // thunk problem
 size_t Bsearchl( unsigned int key, const unsigned int * vals, size_t dim ) {
@@ -406 +404 @@
 
 
+// static inline void noMemory() {
+//      abort( "Heap memory exhausted at %zu bytes.\n"
+//                 "Possible cause is very large memory allocation and/or large amount of unfreed storage allocated by the program or system/library routines.",
+//                 ((char *)(sbrk( 0 )) - (char *)(heapManager.heapBegin)) );
+// } // noMemory
+
+
 static inline void checkAlign( size_t alignment ) {
         if ( alignment < libAlign() || ! libPow2( alignment ) ) {
@@ -433 +438 @@
 
 
-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 ) {
+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 );
 
@@ -465 +471 @@
 
 
-static inline void * extend( size_t size ) with ( heapManager ) {
+static inline void * extend( size_t size ) with( heapManager ) {
         lock( extlock __cfaabi_dbg_ctx2 );
         ptrdiff_t rem = heapRemaining - size;
@@ -496 +502 @@
 
 
-static inline void * doMalloc( size_t size ) with ( heapManager ) {
+static inline void * doMalloc( size_t size ) with( heapManager ) {
         HeapManager.Storage * block;                                            // pointer to new block of storage
 
@@ -529 +535 @@
                 // Spin until the lock is acquired for this particular size of block.
 
-                #if defined( SPINLOCK )
+                #if BUCKETLOCK == SPINLOCK
                 lock( freeElem->lock __cfaabi_dbg_ctx2 );
                 block = freeElem->freeList;                                             // remove node from stack
                 #else
-                block = freeElem->freeList.pop();
-                #endif // SPINLOCK
+                block = pop( freeElem->freeList );
+                #endif // BUCKETLOCK
                 if ( unlikely( block == 0p ) ) {                                // no free block ?
-                        #if defined( SPINLOCK )
+                        #if BUCKETLOCK == SPINLOCK
                         unlock( freeElem->lock );
-                        #endif // SPINLOCK
+                        #endif // BUCKETLOCK
 
                         // Freelist for that size was empty, so carve it out of the heap if there's enough left, or get some more
@@ -544 +550 @@
 
                         block = (HeapManager.Storage *)extend( tsize ); // mutual exclusion on call
-  if ( unlikely( block == 0p ) ) return 0p;
-                #if defined( SPINLOCK )
+        if ( unlikely( block == 0p ) ) return 0p;
+                #if BUCKETLOCK == SPINLOCK
                 } else {
                         freeElem->freeList = block->header.kind.real.next;
                         unlock( freeElem->lock );
-                #endif // SPINLOCK
+                #endif // BUCKETLOCK
                 } // if
 
@@ -572 +578 @@
         } // if
 
-        block->header.size = size;                                                      // store allocation size
+        block->header.kind.real.size = size;                            // store allocation size
         void * addr = &(block->data);                                           // adjust off header to user bytes
 
@@ -591 +597 @@
 
 
-static inline void doFree( void * addr ) with ( heapManager ) {
+static inline void doFree( void * addr ) with( heapManager ) {
         #ifdef __CFA_DEBUG__
         if ( unlikely( heapManager.heapBegin == 0p ) ) {
@@ -623 +629 @@
                 free_storage += size;
                 #endif // __STATISTICS__
-                #if defined( SPINLOCK )
+                #if BUCKETLOCK == SPINLOCK
                 lock( freeElem->lock __cfaabi_dbg_ctx2 );               // acquire spin lock
                 header->kind.real.next = freeElem->freeList;    // push on stack
@@ -629 +635 @@
                 unlock( freeElem->lock );                                               // release spin lock
                 #else
-                freeElem->freeList.push( *(HeapManager.Storage *)header );
-                #endif // SPINLOCK
+                push( freeElem->freeList, *(HeapManager.Storage *)header );
+                #endif // BUCKETLOCK
         } // if
 
@@ -645 +651 @@
 
 
-size_t prtFree( HeapManager & manager ) with ( manager ) {
+size_t prtFree( HeapManager & manager ) with( manager ) {
         size_t total = 0;
         #ifdef __STATISTICS__
@@ -657 +663 @@
                 #endif // __STATISTICS__
 
-                #if defined( SPINLOCK )
+                #if BUCKETLOCK == SPINLOCK
                 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 != 0p; p = p->header.kind.real.next.top ) {
-                #endif // SPINLOCK
+                for ( HeapManager.Storage * p = top( freeLists[i].freeList ); p != 0p; /* p = getNext( p )->top */) {
+                        typeof(p) temp = getNext( p )->top;                     // FIX ME: direct assignent fails, initialization works
+                        p = temp;
+                #endif // BUCKETLOCK
                         total += size;
                         #ifdef __STATISTICS__
@@ -681 +689 @@
 
 
-static void ?{}( HeapManager & manager ) with ( manager ) {
+static void ?{}( HeapManager & manager ) with( manager ) {
         pageSize = sysconf( _SC_PAGESIZE );
 
@@ -1095 +1103 @@
                         header = realHeader( header );                          // backup from fake to real header
                 } // if
-                return header->size;
+                return header->kind.real.size;
         } // malloc_size
 
@@ -1105 +1113 @@
                         header = realHeader( header );                          // backup from fake to real header
                 } // if
-                size_t ret = header->size;
-                header->size = size;
+                size_t ret = header->kind.real.size;
+                header->kind.real.size = size;
                 return ret;
         } // $malloc_size_set