New implementation of BLACKHOLEs

This replaces the global blackhole_queue with a clever scheme that
enables us to queue up blocked threads on the closure that they are
blocked on, while still avoiding atomic instructions in the common
case.

Advantages:

 - gets rid of a locked global data structure and some tricky GC code
   (replacing it with some per-thread data structures and different
   tricky GC code :)

 - wakeups are more prompt: parallel/concurrent performance should
   benefit.  I haven't seen anything dramatic in the parallel
   benchmarks so far, but a couple of threading benchmarks do improve
   a bit.

 - waking up a thread blocked on a blackhole is now O(1) (e.g. if
   it is the target of throwTo).

 - less sharing and better separation of Capabilities: communication
   is done with messages, the data structures are strictly owned by a
   Capability and cannot be modified except by sending messages.

 - this change will utlimately enable us to do more intelligent
   scheduling when threads block on each other.  This is what started
   off the whole thing, but it isn't done yet (#3838).

I'll be documenting all this on the wiki in due course.

1 files changed, 38 insertions, 28 deletions

diff --git a/rts/ThreadPaused.c b/rts/ThreadPaused.c
index 75712b04d6..7aee59dcd5 100644
--- a/rts/ThreadPaused.c
+++ b/rts/ThreadPaused.c
@@ -14,6 +14,7 @@
 #include "Updates.h"
 #include "RaiseAsync.h"
 #include "Trace.h"
+#include "Threads.h"
 
 #include <string.h> // for memmove()
 
@@ -75,7 +76,7 @@ stackSqueeze(Capability *cap, StgTSO *tso, StgPtr bottom)
 		 * screw us up if we don't check.
 		 */
 		if (upd->updatee != updatee && !closure_IND(upd->updatee)) {
-		    UPD_IND(cap, upd->updatee, updatee);
+                    updateThunk(cap, tso, upd->updatee, updatee);
 		}
 
 		// now mark this update frame as a stack gap.  The gap
@@ -196,7 +197,7 @@ threadPaused(Capability *cap, StgTSO *tso)
     maybePerformBlockedException (cap, tso);
     if (tso->what_next == ThreadKilled) { return; }
 
-    // NB. Blackholing is *not* optional, we must either do lazy
+    // NB. Blackholing is *compulsory*, we must either do lazy
     // blackholing, or eager blackholing consistently.  See Note
     // [upd-black-hole] in sm/Scav.c.
 
@@ -229,8 +230,9 @@ threadPaused(Capability *cap, StgTSO *tso)
 #ifdef THREADED_RTS
         retry:
 #endif
-	    if (closure_flags[INFO_PTR_TO_STRUCT(bh_info)->type] & _IND
-                || bh_info == &stg_BLACKHOLE_info) {
+	    if (bh_info == &stg_BLACKHOLE_info ||
+                bh_info == &stg_WHITEHOLE_info)
+            {
 		debugTrace(DEBUG_squeeze,
 			   "suspending duplicate work: %ld words of stack",
 			   (long)((StgPtr)frame - tso->sp));
@@ -245,6 +247,7 @@ threadPaused(Capability *cap, StgTSO *tso)
 		// the value to the frame underneath:
 		tso->sp = (StgPtr)frame + sizeofW(StgUpdateFrame) - 2;
 		tso->sp[1] = (StgWord)bh;
+                ASSERT(bh->header.info != &stg_TSO_info);
 		tso->sp[0] = (W_)&stg_enter_info;
 
 		// And continue with threadPaused; there might be
@@ -254,33 +257,40 @@ threadPaused(Capability *cap, StgTSO *tso)
                 continue;
 	    }
 
-	    if (bh->header.info != &stg_CAF_BLACKHOLE_info) {
-		// zero out the slop so that the sanity checker can tell
-		// where the next closure is.
-		DEBUG_FILL_SLOP(bh);
-#ifdef PROFILING
-		// @LDV profiling
-		// We pretend that bh is now dead.
-		LDV_recordDead_FILL_SLOP_DYNAMIC((StgClosure *)bh);
-#endif
-                // an EAGER_BLACKHOLE gets turned into a BLACKHOLE here.
+            // zero out the slop so that the sanity checker can tell
+            // where the next closure is.
+            DEBUG_FILL_SLOP(bh);
+
+            // @LDV profiling
+            // We pretend that bh is now dead.
+            LDV_RECORD_DEAD_FILL_SLOP_DYNAMIC((StgClosure *)bh);
+
+            // an EAGER_BLACKHOLE or CAF_BLACKHOLE gets turned into a
+            // BLACKHOLE here.
 #ifdef THREADED_RTS
-                cur_bh_info = (const StgInfoTable *)
-                    cas((StgVolatilePtr)&bh->header.info, 
-                        (StgWord)bh_info, 
-                        (StgWord)&stg_BLACKHOLE_info);
-
-                if (cur_bh_info != bh_info) {
-                    bh_info = cur_bh_info;
-                    goto retry;
-                }
-#else
-		SET_INFO(bh,&stg_BLACKHOLE_info);
+            // first we turn it into a WHITEHOLE to claim it, and if
+            // successful we write our TSO and then the BLACKHOLE info pointer.
+            cur_bh_info = (const StgInfoTable *)
+                cas((StgVolatilePtr)&bh->header.info, 
+                    (StgWord)bh_info, 
+                    (StgWord)&stg_WHITEHOLE_info);
+            
+            if (cur_bh_info != bh_info) {
+                bh_info = cur_bh_info;
+                goto retry;
+            }
 #endif
 
-		// We pretend that bh has just been created.
-		LDV_RECORD_CREATE(bh);
-	    }
+            // The payload of the BLACKHOLE points to the TSO
+            ((StgInd *)bh)->indirectee = (StgClosure *)tso;
+            write_barrier();
+            SET_INFO(bh,&stg_BLACKHOLE_info);
+
+            // .. and we need a write barrier, since we just mutated the closure:
+            recordClosureMutated(cap,bh);
+
+            // We pretend that bh has just been created.
+            LDV_RECORD_CREATE(bh);
 	    
 	    frame = (StgClosure *) ((StgUpdateFrame *)frame + 1);
 	    if (prev_was_update_frame) {