Changeset 7a2057a for libcfa/src

Timestamp:

Oct 30, 2022, 3:58:39 PM (18 months ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, ast-experimental, master

Children:

c7f12a4

Parents:

0b1ca47

Message:

remove unused BUCKETLOCK, restructure OWNERSHIP and RETURNSPIN

File:

• libcfa/src/heap.cfa (modified) (20 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 : Thu Oct 13 22:21:52 2022
-// Update Count     : 1557
+// Last Modified On : Sun Oct 30 15:33:13 2022
+// Update Count     : 1580
 //
 
@@ -43 +43 @@
 
 #define FASTLOOKUP                                                                              // use O(1) table lookup from allocation size to bucket size
-#define RETURNSPIN                                                                              // toggle spinlock / lockfree stack
 #define OWNERSHIP                                                                               // return freed memory to owner thread
+#define RETURNSPIN                                                                              // toggle spinlock / lockfree queue
+#if ! defined( OWNERSHIP ) && defined( RETURNSPIN )
+#warning "RETURNSPIN is ignored without OWNERSHIP; suggest commenting out RETURNSPIN"
+#endif // ! OWNERSHIP && RETURNSPIN
 
 #define CACHE_ALIGN 64
@@ -109 +112 @@
 
 
-//######################### Spin Lock #########################
+//######################### Helpers #########################
+
+
+// generic Bsearchl does not inline, so substitute with hand-coded binary-search.
+inline __attribute__((always_inline))
+static 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
 
 
@@ -206 +225 @@
 
 
-#define SPINLOCK 0
-#define LOCKFREE 1
-#define BUCKETLOCK SPINLOCK
-#if BUCKETLOCK == SPINLOCK
-#elif BUCKETLOCK == LOCKFREE
-#include <containers/lockfree.hfa>
-#else
-        #error undefined lock type for bucket lock
-#endif // LOCKFREE
-
 // Recursive definitions: HeapManager needs size of bucket array and bucket area needs sizeof HeapManager storage.
 // Break recursion by hardcoding number of buckets and statically checking number is correct after bucket array defined.
@@ -232 +241 @@
                                                                 void * home;                    // allocated block points back to home locations (must overlay alignment)
                                                                 size_t blockSize;               // size for munmap (must overlay alignment)
-                                                                #if BUCKETLOCK == SPINLOCK
                                                                 Storage * next;                 // freed block points to next freed block of same size
-                                                                #endif // SPINLOCK
                                                         };
                                                         size_t size;                            // allocation size in bytes
                                                 };
-                                                #if BUCKETLOCK == LOCKFREE
-                                                Link(Storage) next;                             // freed block points next freed block of same size (double-wide)
-                                                #endif // LOCKFREE
                                         };
                                 } real; // RealHeader
@@ -259 +263 @@
         struct __attribute__(( aligned (8) )) FreeHeader {
                 size_t blockSize __attribute__(( aligned(8) )); // size of allocations on this list
-                #if BUCKETLOCK == SPINLOCK
                 #ifdef OWNERSHIP
                 #ifdef RETURNSPIN
@@ -266 +269 @@
                 Storage * returnList;                                                   // other thread return list
                 #endif // OWNERSHIP
+
                 Storage * freeList;                                                             // thread free list
-                #else
-                StackLF(Storage) freeList;
-                #endif // BUCKETLOCK
                 Heap * homeManager;                                                             // heap owner (free storage to bucket, from bucket to heap)
         }; // FreeHeader
@@ -290 +291 @@
         #endif // __STATISTICS__
 }; // Heap
-
-#if BUCKETLOCK == LOCKFREE
-inline __attribute__((always_inline))
-static {
-        Link(Heap.Storage) * ?`next( Heap.Storage * this ) { return &this->header.kind.real.next; }
-        void ?{}( Heap.FreeHeader & ) {}
-        void ^?{}( Heap.FreeHeader & ) {}
-} // distribution
-#endif // LOCKFREE
 
 
@@ -385 +377 @@
 
 
-// generic Bsearchl does not inline, so substitute with hand-coded binary-search.
-inline __attribute__((always_inline))
-static 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
-
-
 void heapMasterCtor() with( heapMaster ) {
         // Singleton pattern to initialize heap master
@@ -409 +385 @@
         __map_prot = PROT_READ | PROT_WRITE | PROT_EXEC;
 
-        ?{}( extLock );
-        ?{}( mgrLock );
+        extLock = 0;
+        mgrLock = 0;
 
         char * end = (char *)sbrk( 0 );
@@ -497 +473 @@
                                 #ifdef OWNERSHIP
                                 #ifdef RETURNSPIN
-                                ?{}( freeLists[j].returnLock );
+                                freeLists[j].returnLock = 0;
+                                freeLists[j].returnList = 0p;
                                 #endif // RETURNSPIN
-                                freeLists[j].returnList = 0p;
                                 #endif // OWNERSHIP
+
                                 freeLists[j].freeList = 0p;
                                 freeLists[j].homeManager = heap;
@@ -710 +687 @@
         // find the closest bucket size less than or equal to the mmapStart size
         maxBucketsUsed = Bsearchl( mmapStart, bucketSizes, NoBucketSizes ); // binary search
+
         verify( maxBucketsUsed < NoBucketSizes );                       // subscript failure ?
         verify( mmapStart <= bucketSizes[maxBucketsUsed] ); // search failure ?
@@ -971 +949 @@
                 #endif // __STATISTICS__
 
-                // Spin until the lock is acquired for this particular size of block.
-
-                #if BUCKETLOCK == SPINLOCK
                 block = freeHead->freeList;                                             // remove node from stack
-                #else
-                block = pop( freeHead->freeList );
-                #endif // BUCKETLOCK
                 if ( unlikely( block == 0p ) ) {                                // no free block ?
+                        // Freelist for this size is empty, so check return list (OWNERSHIP), carve it out of the heap, if there
+                        // is enough left, or get some more heap storage and carve it off.
                         #ifdef OWNERSHIP
-                        // Freelist for that size is empty, so carve it out of the heap, if there is enough left, or get some more
-                        // and then carve it off.
-                        #ifdef RETURNSPIN
-                        #if BUCKETLOCK == SPINLOCK
-                        lock( freeHead->returnLock );
-                        block = freeHead->returnList;
-                        freeHead->returnList = 0p;
-                        unlock( freeHead->returnLock );
-                        #else
-                        block = __atomic_exchange_n( &freeHead->returnList, nullptr, __ATOMIC_SEQ_CST );
-                        #endif // RETURNSPIN
-
-                        if ( likely( block == 0p ) ) {                  // return list also empty?
+                        if ( unlikely( freeHead->returnList ) ) {       // race, get next time if lose race
+                                #ifdef RETURNSPIN
+                                lock( freeHead->returnLock );
+                                block = freeHead->returnList;
+                                freeHead->returnList = 0p;
+                                unlock( freeHead->returnLock );
+                                #else
+                                block = __atomic_exchange_n( &freeHead->returnList, 0p, __ATOMIC_SEQ_CST );
+                                #endif // RETURNSPIN
+
+                                verify( block );
+                                #ifdef __STATISTICS__
+                                stats.return_pulls += 1;
+                                #endif // __STATISTICS__
+
+                                // OK TO BE PREEMPTED HERE AS heapManager IS NO LONGER ACCESSED.
+
+                                freeHead->freeList = block->header.kind.real.next; // merge returnList into freeHead
+                        } else {
                         #endif // OWNERSHIP
                                 // Do not leave kernel thread as manager_extend accesses heapManager.
@@ -1002 +982 @@
 
                                 #ifdef __CFA_DEBUG__
-                                // Scrub new memory so subsequent uninitialized usages might fail. Only scrub the first 1024 bytes.
+                                // Scrub new memory so subsequent uninitialized usages might fail. Only scrub the first SCRUB_SIZE bytes.
                                 memset( block->data, SCRUB, min( SCRUB_SIZE, tsize - sizeof(Heap.Storage) ) );
                                 #endif // __CFA_DEBUG__
-                        #endif // BUCKETLOCK
                         #ifdef OWNERSHIP
-                        } else {                                                                        // merge returnList into freeHead
-                                #ifdef __STATISTICS__
-                                stats.return_pulls += 1;
-                                #endif // __STATISTICS__
-
-                                // OK TO BE PREEMPTED HERE AS heapManager IS NO LONGER ACCESSED.
-
-                                freeHead->freeList = block->header.kind.real.next;
                         } // if
                         #endif // OWNERSHIP
@@ -1026 +997 @@
   if ( unlikely( size > ULONG_MAX - __page_size ) ) return 0p;
                 tsize = ceiling2( tsize, __page_size );                 // must be multiple of page size
+
                 #ifdef __STATISTICS__
                 stats.counters[STAT_NAME].alloc += tsize;
@@ -1042 +1014 @@
                         if ( errno == ENOMEM ) abort( NO_MEMORY_MSG, tsize ); // no memory
                         // Do not call strerror( errno ) as it may call malloc.
-                        abort( "**** Error **** attempt to allocate large object (> %zu) of size %zu bytes and mmap failed with errno %d.", size, heapMaster.mmapStart, errno );
+                        abort( "**** Error **** attempt to allocate large object (> %zu) of size %zu bytes and mmap failed with errno %d.",
+                                   size, heapMaster.mmapStart, errno );
                 } // if
                 block->header.kind.real.blockSize = MarkMmappedBit( tsize ); // storage size for munmap
 
                 #ifdef __CFA_DEBUG__
-                // Scrub new memory so subsequent uninitialized usages might fail. Only scrub the first 1024 bytes.  The rest of
-                // the storage set to 0 by mmap.
+                // Scrub new memory so subsequent uninitialized usages might fail. Only scrub the first SCRUB_SIZE bytes. The
+                // rest of the storage set to 0 by mmap.
                 memset( block->data, SCRUB, min( SCRUB_SIZE, tsize - sizeof(Heap.Storage) ) );
                 #endif // __CFA_DEBUG__
@@ -1126 +1099 @@
                 #endif // __CFA_DEBUG__
 
+                #ifdef OWNERSHIP
                 if ( likely( heapManager == freeHead->homeManager ) ) { // belongs to this thread
                         header->kind.real.next = freeHead->freeList; // push on stack
@@ -1132 +1106 @@
                         verify( heapManager );
 
-                        #ifdef OWNERSHIP
                         #ifdef RETURNSPIN
                         lock( freeHead->returnLock );
@@ -1141 +1114 @@
                         header->kind.real.next = freeHead->returnList; // link new node to top node
                         // CAS resets header->kind.real.next = freeHead->returnList on failure
-                        while ( ! __atomic_compare_exchange_n( &freeHead->returnList, &header->kind.real.next, header,
+                        while ( ! __atomic_compare_exchange_n( &freeHead->returnList, &header->kind.real.next, (Heap.Storage *)header,
                                                                                                    false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) );
                         #endif // RETURNSPIN
-
-                        #else                                                                           // no OWNERSHIP
-
-                        freeHead = &heap->freeLists[ClearStickyBits( header->kind.real.home ) - &freeHead->homeManager->freeLists[0]];
-                        header->kind.real.next = freeHead->freeList; // push on stack
-                        freeHead->freeList = (Heap.Storage *)header;
-                        #endif // ! OWNERSHIP
-
-                        #ifdef __U_STATISTICS__
-                        stats.return_pushes += 1;
-                        stats.return_storage_request += rsize;
-                        stats.return_storage_alloc += size;
-                        #endif // __U_STATISTICS__
-
-                        // OK TO BE PREEMPTED HERE AS heapManager IS NO LONGER ACCESSED.
-                } // if
+                } // if
+
+                #else                                                                                   // no OWNERSHIP
+
+                // kind.real.home is address in owner thread's freeLists, so compute the equivalent position in this thread's freeList.
+                freeHead = &freeLists[ClearStickyBits( (Heap.FreeHeader *)(header->kind.real.home) ) - &freeHead->homeManager->freeLists[0]];
+                header->kind.real.next = freeHead->freeList;    // push on stack
+                freeHead->freeList = (Heap.Storage *)header;
+                #endif // ! OWNERSHIP
+
+                #ifdef __U_STATISTICS__
+                stats.return_pushes += 1;
+                stats.return_storage_request += rsize;
+                stats.return_storage_alloc += size;
+                #endif // __U_STATISTICS__
+
+                // OK TO BE PREEMPTED HERE AS heapManager IS NO LONGER ACCESSED.
         } // if
 
@@ -1186 +1160 @@
                 #endif // __STATISTICS__
 
-                #if BUCKETLOCK == SPINLOCK
                 for ( Heap.Storage * p = freeLists[i].freeList; p != 0p; p = p->header.kind.real.next ) {
-                #else
-                        for(;;) {
-//              for ( Heap.Storage * p = top( freeLists[i].freeList ); p != 0p; p = (p)`next->top ) {
-//              for ( Heap.Storage * p = top( freeLists[i].freeList ); p != 0p; /* p = getNext( p )->top */) {
-//                      Heap.Storage * temp = p->header.kind.real.next.top; // FIX ME: direct assignent fails, initialization works`
-//                      typeof(p) temp = (( p )`next)->top;                     // FIX ME: direct assignent fails, initialization works`
-//                      p = temp;
-                #endif // BUCKETLOCK
                         total += size;
                         #ifdef __STATISTICS__