nonmoving: Fix collection of sparks

Previously sparks living in the non-moving heap would be promptly GC'd
by the minor collector since pruneSparkQueue uses the BF_EVACUATED flag,
which non-moving heap blocks do not have set.

Fix this by implementing proper support in pruneSparkQueue for
determining reachability in the non-moving heap. The story is told in
Note [Spark management in the nonmoving heap].

4 files changed, 53 insertions, 6 deletions

diff --git a/rts/Sparks.c b/rts/Sparks.c
index 4022691da2..2012b0682b 100644
--- a/rts/Sparks.c
+++ b/rts/Sparks.c
@@ -15,6 +15,7 @@
 #include "Prelude.h"
 #include "Sparks.h"
 #include "ThreadLabels.h"
+#include "sm/NonMovingMark.h"
 #include "sm/HeapAlloc.h"
 
 #if defined(THREADED_RTS)
@@ -86,7 +87,7 @@ newSpark (StgRegTable *reg, StgClosure *p)
  * -------------------------------------------------------------------------- */
 
 void
-pruneSparkQueue (Capability *cap)
+pruneSparkQueue (bool nonmovingMarkFinished, Capability *cap)
 {
     SparkPool *pool;
     StgClosurePtr spark, tmp, *elements;
@@ -196,7 +197,26 @@ pruneSparkQueue (Capability *cap)
                   traceEventSparkFizzle(cap);
               }
           } else if (HEAP_ALLOCED(spark)) {
-              if ((Bdescr((P_)spark)->flags & BF_EVACUATED)) {
+              bdescr *spark_bd = Bdescr((P_) spark);
+              bool is_alive = false;
+              if (nonmovingMarkFinished) {
+                  // See Note [Spark management under the nonmoving collector]
+                  // in NonMoving.c.
+                  // If we just concluded concurrent marking then we can rely
+                  // on the mark bitmap to reflect whether sparks living in the
+                  // non-moving heap have died.
+                  if (spark_bd->flags & BF_NONMOVING) {
+                      is_alive = nonmovingIsAlive(spark);
+                  } else {
+                      // The nonmoving collector doesn't collect anything
+                      // outside of the non-moving heap.
+                      is_alive = true;
+                  }
+              } else if (spark_bd->flags & (BF_EVACUATED | BF_NONMOVING)) {
+                  is_alive = true;
+              }
+
+              if (is_alive) {
                   if (closure_SHOULD_SPARK(spark)) {
                       elements[botInd] = spark; // keep entry (new address)
                       botInd++;
diff --git a/rts/Sparks.h b/rts/Sparks.h
index d87d03076d..58817b80af 100644
--- a/rts/Sparks.h
+++ b/rts/Sparks.h
@@ -45,7 +45,7 @@ INLINE_HEADER bool         fizzledSpark  (StgClosure *);
 void         freeSparkPool     (SparkPool *pool);
 void         createSparkThread (Capability *cap);
 void         traverseSparkQueue(evac_fn evac, void *user, Capability *cap);
-void         pruneSparkQueue   (Capability *cap);
+void         pruneSparkQueue   (bool nonmovingMarkFinished, Capability *cap);
 
 INLINE_HEADER void discardSparks  (SparkPool *pool);
 INLINE_HEADER long sparkPoolSize  (SparkPool *pool);
diff --git a/rts/sm/GC.c b/rts/sm/GC.c
index 16d8c77453..f6698f5b9e 100644
--- a/rts/sm/GC.c
+++ b/rts/sm/GC.c
@@ -470,12 +470,12 @@ GarbageCollect (uint32_t collect_gen,
 #if defined(THREADED_RTS)
   if (n_gc_threads == 1) {
       for (n = 0; n < n_capabilities; n++) {
-          pruneSparkQueue(capabilities[n]);
+          pruneSparkQueue(false, capabilities[n]);
       }
   } else {
       for (n = 0; n < n_capabilities; n++) {
           if (n == cap->no || idle_cap[n]) {
-              pruneSparkQueue(capabilities[n]);
+              pruneSparkQueue(false, capabilities[n]);
          }
       }
   }
@@ -1250,7 +1250,7 @@ gcWorkerThread (Capability *cap)
     // non-deterministic whether a spark will be retained if it is
     // only reachable via weak pointers.  To fix this problem would
     // require another GC barrier, which is too high a price.
-    pruneSparkQueue(cap);
+    pruneSparkQueue(false, cap);
 #endif
 
     // Wait until we're told to continue
diff --git a/rts/sm/NonMoving.c b/rts/sm/NonMoving.c
index 2dd201f0f9..fe9d22b479 100644
--- a/rts/sm/NonMoving.c
+++ b/rts/sm/NonMoving.c
@@ -9,6 +9,7 @@
 #include "Rts.h"
 #include "RtsUtils.h"
 #include "Capability.h"
+#include "Sparks.h"
 #include "Printer.h"
 #include "Storage.h"
 // We call evacuate, which expects the thread-local gc_thread to be valid;
@@ -368,6 +369,24 @@ Mutex concurrent_coll_finished_lock;
  * approximate due to concurrent collection and ultimately seems more costly
  * than the problem demands.
  *
+ * Note [Spark management under the nonmoving collector]
+ * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ * Every GC, both minor and major, prunes the spark queue (using
+ * Sparks.c:pruneSparkQueue) of sparks which are no longer reachable.
+ * Doing this with concurrent collection is a tad subtle since the minor
+ * collections cannot rely on the mark bitmap to accurately reflect the
+ * reachability of a spark.
+ *
+ * We use a conservative reachability approximation:
+ *
+ *  - Minor collections assume that all sparks living in the non-moving heap
+ *    are reachable.
+ *
+ *  - Major collections prune the spark queue during the final sync. This pruning
+ *    assumes that all sparks in the young generations are reachable (since the
+ *    BF_EVACUATED flag won't be set on the nursery blocks) and will consequently
+ *    only prune dead sparks living in the non-moving heap.
+ *
  */
 
 memcount nonmoving_live_words = 0;
@@ -1056,6 +1075,14 @@ static void nonmovingMark_(MarkQueue *mark_queue, StgWeak **dead_weaks, StgTSO *
         nonmoving_old_weak_ptr_list = NULL;
     }
 
+    // Prune spark lists
+    // See Note [Spark management under the nonmoving collector].
+#if defined(THREADED_RTS)
+    for (uint32_t n = 0; n < n_capabilities; n++) {
+        pruneSparkQueue(true, capabilities[n]);
+    }
+#endif
+
     // Everything has been marked; allow the mutators to proceed
 #if defined(THREADED_RTS)
     nonmoving_write_barrier_enabled = false;