Changeset 1b143de

Timestamp:

May 12, 2020, 4:26:07 PM (4 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

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

Children:

2f1cb37, 9da5a50

Parents:

4fa44e7

Message:

Several fixes to relaxed_ready queue

Location:

libcfa/src/concurrency

Files:

• invoke.h (modified) (1 diff)
• io.cfa (modified) (1 diff)
• monitor.cfa (modified) (1 diff)
• ready_queue.cfa (modified) (16 diffs)

libcfa/src/concurrency/invoke.h

@@ -166 +166 @@
                 struct $thread * next;
                 struct $thread * prev;
-                unsigned long long ts;
+                volatile unsigned long long ts;
         };
 

libcfa/src/concurrency/io.cfa

@@ -357 +357 @@
                                         // The thread was preempted and now it is on the ready queue
                                         /* paranoid */ verify( thrd.state == Active );           // The thread better be in this state
-                                        /* paranoid */ verify( thrd.next == 1p );                // The thread should be the last on the list
+                                        /* paranoid */ verify( thrd.next != 0p );                // The thread should be the last on the list
                                         /* paranoid */ verify( this.ready_queue.head == &thrd ); // The thread should be the only thing on the list
 

libcfa/src/concurrency/monitor.cfa

@@ -907 +907 @@
         // For each thread in the entry-queue
         for(    $thread ** thrd_it = &entry_queue.head;
-                *thrd_it;
+                (*thrd_it) != 1p;
                 thrd_it = &(*thrd_it)->link.next
         ) {

libcfa/src/concurrency/ready_queue.cfa

@@ -15 +15 @@
 
 #define __cforall_thread__
-#define __CFA_DEBUG_PRINT_READY_QUEUE__
+// #define __CFA_DEBUG_PRINT_READY_QUEUE__
 
 #include "bits/defs.hfa"
@@ -112 +112 @@
 // Helpers used by extract
 // (_mask_bitsidx() & X) returns a bit index valid for a __cfa_readyQ_mask_t, where X is any integer
-static inline __cfa_readyQ_mask_t _mask_bitsidx () { return (8 * sizeof(__cfa_readyQ_mask_t)) - 1; }
+static inline __cfa_readyQ_mask_t _mask_bitsidx () __attribute__ ((const)) { return (8 * sizeof(__cfa_readyQ_mask_t)) - 1; }
 
 // (X >> _mask_shiftidx()) retuns an index into an array of __cfa_readyQ_mask_t
-static inline __cfa_readyQ_mask_t _mask_shiftidx() { return (8 * sizeof(__cfa_readyQ_mask_t)) - __builtin_clzl(_mask_bitsidx()); }
+static inline __cfa_readyQ_mask_t _mask_shiftidx() __attribute__ ((const)) { return (8 * sizeof(__cfa_readyQ_mask_t)) - __builtin_clzl(_mask_bitsidx()); }
 
 
@@ -121 +121 @@
 // Given an index into the large mask, returns the bit index and which __cfa_readyQ_mask_t index in the array
 static inline [__cfa_readyQ_mask_t, __cfa_readyQ_mask_t] extract(__cfa_readyQ_mask_t idx) {
-        __cfa_readyQ_mask_t word = idx >> _mask_bitsidx();
-        __cfa_readyQ_mask_t bit  = idx &  _mask_shiftidx();
+        __cfa_readyQ_mask_t word = idx >> _mask_shiftidx();
+        __cfa_readyQ_mask_t bit  = idx &  _mask_bitsidx();
         return [bit, word];
 }
@@ -188 +188 @@
         }
 
-        __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p done, id %u\n", proc, n);
+        __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p done, id %lu\n", proc, n);
 
         // Return new spot.
@@ -304 +304 @@
         /* paranoid */ verifyf(((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128));
 
-        /* paranoid */ verifyf(_mask_shiftidx() == 6 , "%zu", _mask_shiftidx());
-        /* paranoid */ verifyf(_mask_bitsidx () == 63, "%zu", _mask_bitsidx());
+        /* paranoid */ verifyf(_mask_shiftidx() == 6 , "%llu", _mask_shiftidx());
+        /* paranoid */ verifyf(_mask_bitsidx () == 63, "%llu", _mask_bitsidx());
 }
 
@@ -422 +422 @@
 // Check whether or not list is empty
 static inline bool is_empty(__intrusive_lane_t & this) {
-        verify( (this.before.link.ts == 0) == (this.count == 0) );
+        // Cannot verify here since it may not be locked
         return this.before.link.ts == 0;
 }
@@ -428 +428 @@
 // Return the timestamp
 static inline unsigned long long ts(__intrusive_lane_t & this) {
-        verify( this.before.link.ts == this.before.link.next->link.ts );
+        // Cannot verify here since it may not be locked
         return this.before.link.ts;
 }
@@ -520 +520 @@
         [bit, word] = extract(index);
 
+        __cfadbg_print_safe(ready_queue, "Kernel : Ready queue extracted index %u as [bit %llu, word %llu]\n", index, bit, word);
+
         // Conditional check
         verifyf(
@@ -552 +554 @@
         // Conditional check
         verifyf(
-                strict == STRICT && // Conditional check if it was expected to be set
+                strict != STRICT || // Conditional check if it was expected to be set
                 ((mask[word] & (1ull << bit)) != 0),
                 "Before clear %llu:%llu (%u), %llx & %llx", word, bit, index, mask[word], (1ull << bit)
@@ -562 +564 @@
         // Conditional check
         verifyf(
-                strict == STRICT && // Conditional check if it was expected to be cleared
+                strict != STRICT || // Conditional check if it was expected to be cleared
                 ret,
                 "Bit was set but btr returned false"
@@ -576 +578 @@
 //-----------------------------------------------------------------------
 __attribute__((hot)) bool push(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) {
+        __cfadbg_print_safe(ready_queue, "Kernel : Pushing %p on cluster %p (mask %llu)\n", thrd, cltr, used.mask[0]);
+
         // write timestamp
         thrd->link.ts = rdtscl();
@@ -605 +609 @@
         // If this lane used to be empty we need to do more
         if(lane_first) {
+                // Update the bit mask
+                mask_set((__cfa_readyQ_mask_t *)used.mask, i, STRICT);
+
                 // Update the global count
                 size_t ret = __atomic_fetch_add( &used.count, 1z, __ATOMIC_SEQ_CST);
@@ -610 +617 @@
                 // Check if the entire queue used to be empty
                 first = (ret == 0);
-
-                // Update the bit mask
-                mask_set((__cfa_readyQ_mask_t *)used.mask, i, STRICT);
         }
 
@@ -624 +628 @@
         // Unlock and return
         __atomic_unlock( &lanes.data[i].lock );
+
+        __cfadbg_print_safe(ready_queue, "Kernel : Pushed %p on cluster %p (idx: %u, mask %llu, first %d)\n", thrd, cltr, i, used.mask[0], lane_first);
 
         // Update statistics
@@ -807 +813 @@
 
                                 if(sl.before.link.ts == 0l) {
-                                        assert(tail(sl)->link.next == 0p);
                                         assert(tail(sl)->link.prev == head(sl));
                                         assert(head(sl)->link.next == tail(sl));
-                                        assert(head(sl)->link.prev == 0p);
+                                } else {
+                                        assert(tail(sl)->link.prev != head(sl));
+                                        assert(head(sl)->link.next != tail(sl));
                                 }
                         }
@@ -917 +924 @@
                 for( idx; (size_t)lanes.count ~ ocount) {
                         // Lock is not strictly needed but makes checking invariants much easier
-                        bool locked = __atomic_try_acquire(&lanes.data[idx].lock);
+                        __attribute__((unused)) bool locked = __atomic_try_acquire(&lanes.data[idx].lock);
                         verify(locked);