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, 88 insertions, 73 deletions

diff --git a/rts/StgMiscClosures.cmm b/rts/StgMiscClosures.cmm
index f111875760..830bde5665 100644
--- a/rts/StgMiscClosures.cmm
+++ b/rts/StgMiscClosures.cmm
@@ -283,96 +283,105 @@ INFO_TABLE(stg_IND_OLDGEN_PERM,1,0,IND_OLDGEN_PERM,"IND_OLDGEN_PERM","IND_OLDGEN
    waiting for the evaluation of the closure to finish.
    ------------------------------------------------------------------------- */
 
-/* Note: a BLACKHOLE must be big enough to be
- * overwritten with an indirection/evacuee/catch.  Thus we claim it
- * has 1 non-pointer word of payload. 
- */
-INFO_TABLE(stg_BLACKHOLE,0,1,BLACKHOLE,"BLACKHOLE","BLACKHOLE")
+INFO_TABLE(stg_BLACKHOLE,1,0,BLACKHOLE,"BLACKHOLE","BLACKHOLE")
 {
-    TICK_ENT_BH();
-
-#ifdef THREADED_RTS
-    // foreign "C" debugBelch("BLACKHOLE entry\n");
-#endif
-
-    /* Actually this is not necessary because R1 is about to be destroyed. */
-    LDV_ENTER(R1);
+    W_ r, p, info, bq, msg, owner, bd;
 
-#if defined(THREADED_RTS)
-    ACQUIRE_LOCK(sched_mutex "ptr");
-    // released in stg_block_blackhole_finally
-#endif
-
-    /* Put ourselves on the blackhole queue */
-    StgTSO__link(CurrentTSO) = W_[blackhole_queue];
-    W_[blackhole_queue] = CurrentTSO;
-
-    /* jot down why and on what closure we are blocked */
-    StgTSO_why_blocked(CurrentTSO) = BlockedOnBlackHole::I16;
-    StgTSO_block_info(CurrentTSO) = R1;
+    TICK_ENT_DYN_IND();	/* tick */
 
-    jump stg_block_blackhole;
+retry:
+    p = StgInd_indirectee(R1);
+    if (GETTAG(p) != 0) {
+        R1 = p;
+        jump %ENTRY_CODE(Sp(0));
+    }
+
+    info = StgHeader_info(p);
+    if (info == stg_IND_info) {
+        // This could happen, if e.g. we got a BLOCKING_QUEUE that has
+        // just been replaced with an IND by another thread in
+        // wakeBlockingQueue().
+        goto retry;
+    }
+
+    if (info == stg_TSO_info ||
+        info == stg_BLOCKING_QUEUE_CLEAN_info ||
+        info == stg_BLOCKING_QUEUE_DIRTY_info)
+    {
+        ("ptr" msg) = foreign "C" allocate(MyCapability() "ptr", 
+                                           BYTES_TO_WDS(SIZEOF_MessageBlackHole)) [R1];
+        
+        StgHeader_info(msg) = stg_MSG_BLACKHOLE_info;
+        MessageBlackHole_tso(msg) = CurrentTSO;
+        MessageBlackHole_bh(msg) = R1;
+               
+        (r) = foreign "C" messageBlackHole(MyCapability() "ptr", msg "ptr") [R1];
+
+        if (r == 0) {
+            goto retry;
+        } else {
+            StgTSO_why_blocked(CurrentTSO) = BlockedOnBlackHole::I16;
+            StgTSO_block_info(CurrentTSO) = msg;
+            jump stg_block_blackhole;
+        }
+    }
+    else
+    {
+        R1 = p;
+        ENTER();
+    }
 }
 
-/* identical to BLACKHOLEs except for the infotag */
-INFO_TABLE(stg_CAF_BLACKHOLE,0,1,CAF_BLACKHOLE,"CAF_BLACKHOLE","CAF_BLACKHOLE")
+INFO_TABLE(__stg_EAGER_BLACKHOLE,1,0,BLACKHOLE,"BLACKHOLE","BLACKHOLE")
 {
-    TICK_ENT_BH();
-    LDV_ENTER(R1);
-
-#if defined(THREADED_RTS)
-    // foreign "C" debugBelch("BLACKHOLE entry\n");
-#endif
-
-#if defined(THREADED_RTS)
-    ACQUIRE_LOCK(sched_mutex "ptr");
-    // released in stg_block_blackhole_finally
-#endif
-
-    /* Put ourselves on the blackhole queue */
-    StgTSO__link(CurrentTSO) = W_[blackhole_queue];
-    W_[blackhole_queue] = CurrentTSO;
-
-    /* jot down why and on what closure we are blocked */
-    StgTSO_why_blocked(CurrentTSO) = BlockedOnBlackHole::I16;
-    StgTSO_block_info(CurrentTSO) = R1;
-
-    jump stg_block_blackhole;
+    jump ENTRY_LBL(stg_BLACKHOLE);
 }
 
-INFO_TABLE(__stg_EAGER_BLACKHOLE,0,1,BLACKHOLE,"EAGER_BLACKHOLE","EAGER_BLACKHOLE")
+// CAF_BLACKHOLE is allocated when entering a CAF.  The reason it is
+// distinct from BLACKHOLE is so that we can tell the difference
+// between an update frame on the stack that points to a CAF under
+// evaluation, and one that points to a closure that is under
+// evaluation by another thread (a BLACKHOLE).  See threadPaused().
+//
+INFO_TABLE(stg_CAF_BLACKHOLE,1,0,BLACKHOLE,"BLACKHOLE","BLACKHOLE")
 {
-    TICK_ENT_BH();
-
-#ifdef THREADED_RTS
-    // foreign "C" debugBelch("BLACKHOLE entry\n");
-#endif
-
-    /* Actually this is not necessary because R1 is about to be destroyed. */
-    LDV_ENTER(R1);
-
-#if defined(THREADED_RTS)
-    ACQUIRE_LOCK(sched_mutex "ptr");
-    // released in stg_block_blackhole_finally
-#endif
-
-    /* Put ourselves on the blackhole queue */
-    StgTSO__link(CurrentTSO) = W_[blackhole_queue];
-    W_[blackhole_queue] = CurrentTSO;
+    jump ENTRY_LBL(stg_BLACKHOLE);
+}
 
-    /* jot down why and on what closure we are blocked */
-    StgTSO_why_blocked(CurrentTSO) = BlockedOnBlackHole::I16;
-    StgTSO_block_info(CurrentTSO) = R1;
+INFO_TABLE(stg_BLOCKING_QUEUE_CLEAN,4,0,BLOCKING_QUEUE,"BLOCKING_QUEUE","BLOCKING_QUEUE")
+{ foreign "C" barf("BLOCKING_QUEUE_CLEAN object entered!") never returns; }
+    
 
-    jump stg_block_blackhole;
-}
+INFO_TABLE(stg_BLOCKING_QUEUE_DIRTY,4,0,BLOCKING_QUEUE,"BLOCKING_QUEUE","BLOCKING_QUEUE")
+{ foreign "C" barf("BLOCKING_QUEUE_DIRTY object entered!") never returns; }
+    
 
 /* ----------------------------------------------------------------------------
    Whiteholes are used for the "locked" state of a closure (see lockClosure())
    ------------------------------------------------------------------------- */
 
 INFO_TABLE(stg_WHITEHOLE, 0,0, WHITEHOLE, "WHITEHOLE", "WHITEHOLE")
-{ foreign "C" barf("WHITEHOLE object entered!") never returns; }
+{ 
+#if defined(THREADED_RTS)
+    W_ info, i;
+
+    i = 0;
+loop:
+    // spin until the WHITEHOLE is updated
+    info = StgHeader_info(R1);
+    if (info == stg_WHITEHOLE_info) {
+        i = i + 1;
+        if (i == SPIN_COUNT) {
+            i = 0;
+            foreign "C" yieldThread() [R1];
+        }
+        goto loop;
+    }
+    jump %ENTRY_CODE(info);
+#else
+    foreign "C" barf("WHITEHOLE object entered!") never returns;
+#endif
+}
 
 /* ----------------------------------------------------------------------------
    Some static info tables for things that don't get entered, and
@@ -485,9 +494,15 @@ CLOSURE(stg_NO_TREC_closure,stg_NO_TREC);
 INFO_TABLE_CONSTR(stg_MSG_WAKEUP,2,0,0,PRIM,"MSG_WAKEUP","MSG_WAKEUP")
 { foreign "C" barf("MSG_WAKEUP object entered!") never returns; }
 
+INFO_TABLE_CONSTR(stg_MSG_TRY_WAKEUP,2,0,0,PRIM,"MSG_TRY_WAKEUP","MSG_TRY_WAKEUP")
+{ foreign "C" barf("MSG_TRY_WAKEUP object entered!") never returns; }
+
 INFO_TABLE_CONSTR(stg_MSG_THROWTO,4,0,0,PRIM,"MSG_THROWTO","MSG_THROWTO")
 { foreign "C" barf("MSG_THROWTO object entered!") never returns; }
 
+INFO_TABLE_CONSTR(stg_MSG_BLACKHOLE,3,0,0,PRIM,"MSG_BLACKHOLE","MSG_BLACKHOLE")
+{ foreign "C" barf("MSG_BLACKHOLE object entered!") never returns; }
+
 /* ----------------------------------------------------------------------------
    END_TSO_QUEUE