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, 66 insertions, 34 deletions

diff --git a/rts/Updates.cmm b/rts/Updates.cmm
index e0fd7c30d5..7af59657c1 100644
--- a/rts/Updates.cmm
+++ b/rts/Updates.cmm
@@ -16,10 +16,11 @@
 
 #include "Updates.h"
 
-/* on entry to the update code
-   (1) R1 points to the closure being returned
-   (2) Sp points to the update frame
-*/
+#if defined(PROFILING)
+#define UPD_FRAME_PARAMS W_ unused1, W_ unused2, P_ unused3
+#else
+#define UPD_FRAME_PARAMS P_ unused1
+#endif
 
 /* The update fragment has been tuned so as to generate good
    code with gcc, which accounts for some of the strangeness in the
@@ -30,38 +31,69 @@
    code), since we don't mind duplicating this jump.
 */
 
-#define UPD_FRAME_ENTRY_TEMPLATE					\
-	{								\
-          W_ updatee;							\
-									\
-          updatee = StgUpdateFrame_updatee(Sp);				\
-									\
-	  /* remove the update frame from the stack */			\
-	  Sp = Sp + SIZEOF_StgUpdateFrame;				\
-									\
-	  /* ToDo: it might be a PAP, so we should check... */  	\
-	  TICK_UPD_CON_IN_NEW(sizeW_fromITBL(%GET_STD_INFO(updatee)));  \
-									\
-          updateWithIndirection(stg_IND_direct_info,                    \
-			        updatee,                                \
-			        R1,                                     \
-			        jump %ENTRY_CODE(Sp(0)));               \
-	}
-
-#if defined(PROFILING)
-#define UPD_FRAME_PARAMS W_ unused1, W_ unused2, P_ unused3
-#else
-#define UPD_FRAME_PARAMS P_ unused1
-#endif
-
-/* this bitmap indicates that the first word of an update frame is a
- * non-pointer - this is the update frame link.  (for profiling,
- * there's a cost-centre-stack in there too).
- */
+/* on entry to the update code
+   (1) R1 points to the closure being returned
+   (2) Sp points to the update frame
+*/
 
 INFO_TABLE_RET( stg_upd_frame, UPDATE_FRAME, UPD_FRAME_PARAMS)
-UPD_FRAME_ENTRY_TEMPLATE
+{
+    W_ updatee;
+    
+    updatee = StgUpdateFrame_updatee(Sp);
+    
+    /* remove the update frame from the stack */
+    Sp = Sp + SIZEOF_StgUpdateFrame;
+    
+    /* ToDo: it might be a PAP, so we should check... */
+    TICK_UPD_CON_IN_NEW(sizeW_fromITBL(%GET_STD_INFO(updatee)));
+    
+    updateWithIndirection(updatee,
+                          R1,
+                          jump %ENTRY_CODE(Sp(0)));
+}
 
 
 INFO_TABLE_RET( stg_marked_upd_frame, UPDATE_FRAME, UPD_FRAME_PARAMS)
-UPD_FRAME_ENTRY_TEMPLATE
+{
+    W_ updatee, v, i, tso, link;
+
+    // we know the closure is a BLACKHOLE
+    updatee = StgUpdateFrame_updatee(Sp);
+    v = StgInd_indirectee(updatee);
+
+    // remove the update frame from the stack
+    Sp = Sp + SIZEOF_StgUpdateFrame;
+    
+    if (GETTAG(v) != 0) {
+        // updated by someone else: discard our value and use the
+        // other one to increase sharing, but check the blocking
+        // queues to see if any threads were waiting on this BLACKHOLE.
+        R1 = v;
+        foreign "C" checkBlockingQueues(MyCapability() "ptr",
+                                        CurrentTSO "ptr") [R1];
+        jump %ENTRY_CODE(Sp(0));
+    }
+
+    // common case: it is still our BLACKHOLE
+    if (v == CurrentTSO) {
+        updateWithIndirection(updatee,
+                              R1,
+                              jump %ENTRY_CODE(Sp(0)));
+    }
+
+    // The other cases are all handled by the generic code
+    foreign "C" updateThunk (MyCapability() "ptr", CurrentTSO "ptr", 
+                             updatee "ptr", R1 "ptr") [R1];
+
+    jump %ENTRY_CODE(Sp(0));
+}
+
+// Special update frame code for CAFs and eager-blackholed thunks: it
+// knows how to update blackholes, but is distinct from
+// stg_marked_upd_frame so that lazy blackholing won't treat it as the
+// high watermark.
+INFO_TABLE_RET (stg_bh_upd_frame, UPDATE_FRAME, UPD_FRAME_PARAMS)
+{
+    jump stg_marked_upd_frame_info;
+}