Changeset 6f774be for libcfa/src/concurrency

Timestamp:

Jun 1, 2023, 11:58:50 AM (19 months ago)

Author:

caparson <caparson@…>

Branches:

ast-experimental, master

Children:

8421d3f

Parents:

8913de4

Message:

fixed bug where waituntil deadlock could occur

Location:

libcfa/src/concurrency

Files:

• channel.hfa (modified) (5 diffs)
• select.hfa (modified) (2 diffs)

libcfa/src/concurrency/channel.hfa

@@ -341 +341 @@
 }
 
+// special case of __handle_waituntil_OR, that does some work to avoid starvation/deadlock case
+static inline bool __handle_pending( dlist( select_node ) & queue, select_node & mine ) {
+    while ( !queue`isEmpty ) {
+        // if node not a special OR case or if we win the special OR case race break
+        if ( !queue`first.clause_status || queue`first.park_counter || __pending_set_other( queue`first, mine, ((unsigned long int)(&(queue`first))) ) )
+            return true;
+        
+        // our node lost the race when toggling in __pending_set_other
+        if ( *mine.clause_status != __SELECT_PENDING ) 
+            return false;
+
+        // otherwise we lost the special OR race so discard node
+        try_pop_front( queue );
+    }
+    return false;
+}
+
 // type used by select statement to capture a chan read as the selected operation
 struct chan_read {
@@ -374 +391 @@
                 return false;
             }
-            
-            if ( __handle_waituntil_OR( prods ) ) {
+
+            if ( __handle_pending( prods, node ) ) {
                 __prods_handoff( chan, ret );
                 __make_select_node_sat( node ); // need to to mark SAT now that we know operation is done or else threads could get stuck in __mark_select_node
@@ -381 +398 @@
                 return true;
             }
-            __make_select_node_unsat( node );
+            if ( *node.clause_status == __SELECT_PENDING )
+                __make_select_node_unsat( node );
         }
         // check if we can complete operation. If so race to establish winner in special OR case
@@ -464 +482 @@
                 return false;
             }
-            
-            if ( __handle_waituntil_OR( cons ) ) {
+
+            if ( __handle_pending( cons, node ) ) {
                 __cons_handoff( chan, elem );
                 __make_select_node_sat( node ); // need to to mark SAT now that we know operation is done or else threads could get stuck in __mark_select_node
@@ -471 +489 @@
                 return true;
             }
-            __make_select_node_unsat( node );
+            if ( *node.clause_status == __SELECT_PENDING )
+                __make_select_node_unsat( node );
         }
         // check if we can complete operation. If so race to establish winner in special OR case

libcfa/src/concurrency/select.hfa

@@ -103 +103 @@
 //=============================================================================================
 
+static inline void __make_select_node_unsat( select_node & this ) with( this ) {
+    __atomic_store_n( clause_status, __SELECT_UNSAT, __ATOMIC_SEQ_CST );
+}
+static inline void __make_select_node_sat( select_node & this ) with( this ) {
+    __atomic_store_n( clause_status, __SELECT_SAT, __ATOMIC_SEQ_CST );
+}
+
 // used for the 2-stage avail needed by the special OR case
 static inline bool __mark_select_node( select_node & this, unsigned long int val ) with( this ) {
@@ -116 +123 @@
 }
 
-static inline void __make_select_node_unsat( select_node & this ) with( this ) {
-    __atomic_store_n( clause_status, __SELECT_UNSAT, __ATOMIC_SEQ_CST );
-}
-static inline void __make_select_node_sat( select_node & this ) with( this ) {
-    __atomic_store_n( clause_status, __SELECT_SAT, __ATOMIC_SEQ_CST );
+// used for the 2-stage avail by the thread who owns a pending node
+static inline bool __pending_set_other( select_node & other, select_node & mine, unsigned long int val ) with( other ) {
+    /* paranoid */ verify( park_counter == 0p );
+    /* paranoid */ verify( clause_status != 0p );
+
+    unsigned long int cmp_status = __SELECT_UNSAT;
+    while( !__atomic_compare_exchange_n( clause_status, &cmp_status, val, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) {
+        if ( cmp_status != __SELECT_PENDING )
+            return false;
+
+        // toggle current status flag to avoid starvation/deadlock
+        __make_select_node_unsat( mine );
+        cmp_status = __SELECT_UNSAT;
+        if ( !__atomic_compare_exchange_n( mine.clause_status, &cmp_status, __SELECT_PENDING, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) )
+            return false;
+        cmp_status = __SELECT_UNSAT;
+    }
+    return true;
 }