rts: Use weaker cas in WSDeque

The algorithm described in the referenced paper uses this slightly
weaker atomic op.

This is the first "exotic" cas we're using. I've added a macro in the
<ORDERING>_OP style to match existing ones.

2 files changed, 26 insertions, 1 deletions

diff --git a/includes/stg/SMP.h b/includes/stg/SMP.h
index 389dd95c88..589bde8266 100644
--- a/includes/stg/SMP.h
+++ b/includes/stg/SMP.h
@@ -52,6 +52,13 @@ EXTERN_INLINE StgWord cas(StgVolatilePtr p, StgWord o, StgWord n);
 EXTERN_INLINE StgWord8 cas_word8(StgWord8 *volatile p, StgWord8 o, StgWord8 n);
 
 /*
+ * Compare-and-swap
+ * this uses a seq_cst success memory order and a relaxed failure memory order
+ */
+EXTERN_INLINE StgWord cas_seq_cst_relaxed(StgVolatilePtr p, StgWord o, StgWord n);
+
+
+/*
  * Atomic addition by the provided quantity
  *
  * atomic_inc(p, n) {
@@ -304,6 +311,17 @@ cas_word8(StgWord8 *volatile p, StgWord8 o, StgWord8 n)
 #endif
 }
 
+EXTERN_INLINE StgWord
+cas_seq_cst_relaxed(StgVolatilePtr p, StgWord o, StgWord n) {
+#if defined(HAVE_C11_ATOMICS)
+    __atomic_compare_exchange_n(p, &o, n, 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED);
+    return o;
+#else
+    return __sync_val_compare_and_swap(p, o, n);
+#endif
+
+}
+
 // RRN: Generalized to arbitrary increments to enable fetch-and-add in
 // Haskell code (fetchAddIntArray#).
 // PT: add-and-fetch, returns new value
@@ -454,6 +472,9 @@ load_load_barrier(void) {
 // Non-atomic addition for "approximate" counters that can be lossy
 #define NONATOMIC_ADD(ptr,val) RELAXED_STORE(ptr, RELAXED_LOAD(ptr) + val)
 
+// compare-and-swap atomic operations
+#define SEQ_CST_RELAXED_CAS(p,o,n) cas_seq_cst_relaxed(p,o,n)
+
 // Explicit fences
 //
 // These are typically necessary only in very specific cases (e.g. WSDeque)
@@ -489,6 +510,9 @@ EXTERN_INLINE void load_load_barrier () {} /* nothing */
 // Non-atomic addition for "approximate" counters that can be lossy
 #define NONATOMIC_ADD(ptr,val) *ptr += val
 
+// compare-and-swap atomic operations
+#define SEQ_CST_RELAXED_CAS(p,o,n) cas(p,o,n)
+
 // Fences
 #define RELEASE_FENCE()
 #define SEQ_CST_FENCE()
diff --git a/rts/WSDeque.c b/rts/WSDeque.c
index d930d848a4..4974dfa7a7 100644
--- a/rts/WSDeque.c
+++ b/rts/WSDeque.c
@@ -56,7 +56,8 @@
 static inline bool
 cas_top(WSDeque *q, StgInt old, StgInt new)
 {
-    return (StgWord) old == cas((StgPtr) &q->top, (StgWord) old, (StgWord) new);
+    return (StgWord) old == SEQ_CST_RELAXED_CAS((StgPtr) &q->top,
+                                                (StgWord) old, (StgWord) new);
 }