Change the representation of the MVar blocked queue

The list of threads blocked on an MVar is now represented as a list of
separately allocated objects rather than being linked through the TSOs
themselves.  This lets us remove a TSO from the list in O(1) time
rather than O(n) time, by marking the list object.  Removing this
linear component fixes some pathalogical performance cases where many
threads were blocked on an MVar and became unreachable simultaneously
(nofib/smp/threads007), or when sending an asynchronous exception to a
TSO in a long list of thread blocked on an MVar.

MVar performance has actually improved by a few percent as a result of
this change, slightly to my surprise.

This is the final cleanup in the sequence, which let me remove the old
way of waking up threads (unblockOne(), MSG_WAKEUP) in favour of the
new way (tryWakeupThread and MSG_TRY_WAKEUP, which is idempotent).  It
is now the case that only the Capability that owns a TSO may modify
its state (well, almost), and this simplifies various things.  More of
the RTS is based on message-passing between Capabilities now.

6 files changed, 26 insertions, 13 deletions

diff --git a/includes/mkDerivedConstants.c b/includes/mkDerivedConstants.c
index 92685cae3a..7efcf47d48 100644
--- a/includes/mkDerivedConstants.c
+++ b/includes/mkDerivedConstants.c
@@ -372,6 +372,10 @@ main(int argc, char *argv[])
     closure_field(StgMVar,tail);
     closure_field(StgMVar,value);
 
+    closure_size(StgMVarTSOQueue);
+    closure_field(StgMVarTSOQueue, link);
+    closure_field(StgMVarTSOQueue, tso);
+
     closure_size(StgBCO);
     closure_field(StgBCO, instrs);
     closure_field(StgBCO, literals);
diff --git a/includes/rts/Constants.h b/includes/rts/Constants.h
index bfc77fa361..354abbbdd9 100644
--- a/includes/rts/Constants.h
+++ b/includes/rts/Constants.h
@@ -227,8 +227,12 @@
    /* same as above but don't unblock async exceptions in resumeThread() */
 
 /* Involved in a message sent to tso->msg_cap */
-#define BlockedOnMsgWakeup  12
-#define BlockedOnMsgThrowTo 13
+#define BlockedOnMsgThrowTo 12
+
+/* The thread is not on any run queues, but can be woken up 
+   by tryWakeupThread() */
+#define ThreadMigrating     13
+
 /*
  * These constants are returned to the scheduler by a thread that has
  * stopped for one reason or another.  See typedef StgThreadReturnCode
diff --git a/includes/rts/storage/Block.h b/includes/rts/storage/Block.h
index 3114bea014..d6a4d4c487 100644
--- a/includes/rts/storage/Block.h
+++ b/includes/rts/storage/Block.h
@@ -109,7 +109,8 @@ typedef struct bdescr_ {
 
 #else
 
-INLINE_HEADER bdescr *Bdescr(StgPtr p)
+EXTERN_INLINE bdescr *Bdescr(StgPtr p);
+EXTERN_INLINE bdescr *Bdescr(StgPtr p)
 {
   return (bdescr *)
     ((((W_)p &  MBLOCK_MASK & ~BLOCK_MASK) >> (BLOCK_SHIFT-BDESCR_SHIFT)) 
diff --git a/includes/rts/storage/Closures.h b/includes/rts/storage/Closures.h
index 802746868c..a0ff738aa7 100644
--- a/includes/rts/storage/Closures.h
+++ b/includes/rts/storage/Closures.h
@@ -305,11 +305,17 @@ typedef struct {
 
 /* Concurrent communication objects */
 
+typedef struct StgMVarTSOQueue_ {
+    StgHeader                header;
+    struct StgMVarTSOQueue_ *link;
+    struct StgTSO_          *tso;
+} StgMVarTSOQueue;
+
 typedef struct {
-  StgHeader       header;
-  struct StgTSO_ *head;
-  struct StgTSO_ *tail;
-  StgClosure*     value;
+    StgHeader                header;
+    struct StgMVarTSOQueue_ *head;
+    struct StgMVarTSOQueue_ *tail;
+    StgClosure*              value;
 } StgMVar;
 
 
diff --git a/includes/rts/storage/TSO.h b/includes/rts/storage/TSO.h
index abe621564d..0e9883f1a6 100644
--- a/includes/rts/storage/TSO.h
+++ b/includes/rts/storage/TSO.h
@@ -82,7 +82,6 @@ typedef struct StgTSO_ {
     /*
       Currently used for linking TSOs on:
       * cap->run_queue_{hd,tl}
-      * MVAR queue
       * (non-THREADED_RTS); the blocked_queue
       * and pointing to the relocated version of a ThreadRelocated
 
diff --git a/includes/stg/MiscClosures.h b/includes/stg/MiscClosures.h
index 4abb67dc55..0aa6f99675 100644
--- a/includes/stg/MiscClosures.h
+++ b/includes/stg/MiscClosures.h
@@ -42,10 +42,10 @@
 #  define RTS_FUN(f)      RTS_FUN_INFO(f##_info)
 #  define RTS_THUNK(f)    RTS_THUNK_INFO(f##_info)
 #else
-#  define RTS_RET(f)      RTS_INFO(f##_info)  RTS_FUN_DECL(f##_ret)
-#  define RTS_ENTRY(f)    RTS_INFO(f##_info)  RTS_FUN_DECL(f##_entry)
-#  define RTS_FUN(f)      RTS_FUN_INFO(f##_info) RTS_FUN_DECL(f##_entry)
-#  define RTS_THUNK(f)    RTS_THUNK_INFO(f##_info) RTS_FUN_DECL(f##_entry)
+#  define RTS_RET(f)      RTS_INFO(f##_info);  RTS_FUN_DECL(f##_ret)
+#  define RTS_ENTRY(f)    RTS_INFO(f##_info);  RTS_FUN_DECL(f##_entry)
+#  define RTS_FUN(f)      RTS_FUN_INFO(f##_info); RTS_FUN_DECL(f##_entry)
+#  define RTS_THUNK(f)    RTS_THUNK_INFO(f##_info); RTS_FUN_DECL(f##_entry)
 #endif
 
 /* Stack frames */
@@ -109,7 +109,6 @@ RTS_ENTRY(stg_MUT_ARR_PTRS_FROZEN0);
 RTS_ENTRY(stg_MUT_VAR_CLEAN);
 RTS_ENTRY(stg_MUT_VAR_DIRTY);
 RTS_ENTRY(stg_END_TSO_QUEUE);
-RTS_ENTRY(stg_MSG_WAKEUP);
 RTS_ENTRY(stg_MSG_TRY_WAKEUP);
 RTS_ENTRY(stg_MSG_THROWTO);
 RTS_ENTRY(stg_MSG_BLACKHOLE);