X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=rts%2Fparallel%2FWSDeque.c;h=acecb85e5f8fe8fe0360652c0ec037f8b8669a76;hb=a11662957fa688997e6c4befff44e7efe94c2db8;hp=ec34a8ca25d359fa4a98c9d789a26576768bdafe;hpb=894864ea401b799833bcd107d9c8eb4cc943ae90;p=ghc-hetmet.git

diff --git a/rts/parallel/WSDeque.c b/rts/parallel/WSDeque.c
index ec34a8c..acecb85 100644
--- a/rts/parallel/WSDeque.c
+++ b/rts/parallel/WSDeque.c
@@ -30,7 +30,11 @@
  * are synchronised without a lock, based on a cas of the top
  * position. One reader wins, the others return NULL for a failure.
  * 
- * Both popBottom and steal also return NULL when the queue is empty.
+ * Both popWSDeque and stealWSDeque also return NULL when the queue is empty.
+ *
+ * Testing: see testsuite/tests/ghc-regress/rts/testwsdeque.c.  If
+ * there's anything wrong with the deque implementation, this test
+ * will probably catch it.
  * 
  * ---------------------------------------------------------------------------*/
 
@@ -39,8 +43,6 @@
 #include "WSDeque.h"
 #include "SMP.h" // for cas
 
-#if defined(THREADED_RTS)
-
 #define CASTOP(addr,old,new) ((old) == cas(((StgPtr)addr),(old),(new)))
 
 /* -----------------------------------------------------------------------------
@@ -118,28 +120,37 @@ popWSDeque (WSDeque *q)
     /* also a bit tricky, has to avoid concurrent steal() calls by
        accessing top with cas, when there is only one element left */
     StgWord t, b;
-    void ** pos;
     long  currSize;
     void * removed;
     
     ASSERT_WSDEQUE_INVARIANTS(q); 
     
     b = q->bottom;
-    /* "decrement b as a test, see what happens" */
-    q->bottom = --b; 
-    pos = (q->elements) + (b & (q->moduloSize));
+
+    // "decrement b as a test, see what happens"
+    b--;
+    q->bottom = b;
+
+    // very important that the following read of q->top does not occur
+    // before the earlier write to q->bottom.
+    store_load_barrier();
+
     t = q->top; /* using topBound would give an *upper* bound, we
                    need a lower bound. We use the real top here, but
                    can update the topBound value */
     q->topBound = t;
-    currSize = b - t;
+    currSize = (long)b - (long)t;
     if (currSize < 0) { /* was empty before decrementing b, set b
                            consistently and abort */
         q->bottom = t;
         return NULL;
     }
-    removed = *pos;
+
+    // read the element at b
+    removed = q->elements[b & q->moduloSize];
+
     if (currSize > 0) { /* no danger, still elements in buffer after b-- */
+        // debugBelch("popWSDeque: t=%ld b=%ld = %ld\n", t, b, removed);
         return removed;
     } 
     /* otherwise, has someone meanwhile stolen the same (last) element?
@@ -153,6 +164,8 @@ popWSDeque (WSDeque *q)
     ASSERT_WSDEQUE_INVARIANTS(q); 
     ASSERT(q->bottom >= q->top);
     
+    // debugBelch("popWSDeque: t=%ld b=%ld = %ld\n", t, b, removed);
+
     return removed;
 }
 
@@ -163,29 +176,27 @@ popWSDeque (WSDeque *q)
 void *
 stealWSDeque_ (WSDeque *q)
 {
-    void ** pos;
-    void ** arraybase;
-    StgWord sz;
     void * stolen;
     StgWord b,t; 
     
 // Can't do this on someone else's spark pool:
 // ASSERT_WSDEQUE_INVARIANTS(q); 
     
-    b = q->bottom;
+    // NB. these loads must be ordered, otherwise there is a race
+    // between steal and pop.
     t = q->top;
+    load_load_barrier();
+    b = q->bottom;
     
     // NB. b and t are unsigned; we need a signed value for the test
-    // below.
+    // below, because it is possible that t > b during a
+    // concurrent popWSQueue() operation.
     if ((long)b - (long)t <= 0 ) { 
         return NULL; /* already looks empty, abort */
   }
     
     /* now access array, see pushBottom() */
-    arraybase = q->elements;
-    sz = q->moduloSize;
-    pos = arraybase + (t & sz);  
-    stolen = *pos;
+    stolen = q->elements[t & q->moduloSize];
     
     /* now decide whether we have won */
     if ( !(CASTOP(&(q->top),t,t+1)) ) {
@@ -193,6 +204,8 @@ stealWSDeque_ (WSDeque *q)
         return NULL;
     }  /* else: OK, top has been incremented by the cas call */
 
+    // debugBelch("stealWSDeque_: t=%d b=%d\n", t, b);
+
 // Can't do this on someone else's spark pool:
 // ASSERT_WSDEQUE_INVARIANTS(q); 
     
@@ -211,6 +224,9 @@ stealWSDeque (WSDeque *q)
     return stolen;
 }
 
+/* -----------------------------------------------------------------------------
+ * pushWSQueue
+ * -------------------------------------------------------------------------- */
 
 #define DISCARD_NEW
 
@@ -220,9 +236,8 @@ rtsBool
 pushWSDeque (WSDeque* q, void * elem)
 {
     StgWord t;
-    void ** pos;
+    StgWord b;
     StgWord sz = q->moduloSize; 
-    StgWord b = q->bottom;
     
     ASSERT_WSDEQUE_INVARIANTS(q); 
     
@@ -230,6 +245,7 @@ pushWSDeque (WSDeque* q, void * elem)
        q->topBound (accessed only by writer) instead. 
        This is why we do not just call empty(q) here.
     */
+    b = q->bottom;
     t = q->topBound;
     if ( (StgInt)b - (StgInt)t >= (StgInt)sz ) { 
         /* NB. 1. sz == q->size - 1, thus ">="
@@ -260,12 +276,10 @@ pushWSDeque (WSDeque* q, void * elem)
 #endif
         }
     }
-    pos = (q->elements) + (b & sz);
-    *pos = elem;
-    (q->bottom)++;
+
+    q->elements[b & sz] = elem;
+    q->bottom = b + 1;
     
     ASSERT_WSDEQUE_INVARIANTS(q); 
     return rtsTrue;
 }
-
-#endif