rts: Introduce non-moving heap census

This introduces a simple census of the non-moving heap (not to be
confused with the heap census used by the heap profiler). This
collects basic heap usage information (number of allocated and free
blocks) which is useful when characterising fragmentation of the
nonmoving heap.

4 files changed, 111 insertions, 0 deletions

diff --git a/rts/rts.cabal.in b/rts/rts.cabal.in
index 2c28426d75..a53c166849 100644
--- a/rts/rts.cabal.in
+++ b/rts/rts.cabal.in
@@ -467,6 +467,7 @@ library
                sm/MBlock.c
                sm/MarkWeak.c
                sm/NonMoving.c
+               sm/NonMovingCensus.c
                sm/NonMovingMark.c
                sm/NonMovingScav.c
                sm/NonMovingSweep.c
diff --git a/rts/sm/NonMoving.c b/rts/sm/NonMoving.c
index 36df09692b..1d504bd0fc 100644
--- a/rts/sm/NonMoving.c
+++ b/rts/sm/NonMoving.c
@@ -21,6 +21,7 @@
 #include "NonMoving.h"
 #include "NonMovingMark.h"
 #include "NonMovingSweep.h"
+#include "NonMovingCensus.h"
 #include "StablePtr.h" // markStablePtrTable
 #include "Schedule.h" // markScheduler
 #include "Weak.h" // dead_weak_ptr_list
@@ -747,6 +748,10 @@ static void nonmovingMark_(MarkQueue *mark_queue, StgWeak **dead_weaks, StgTSO *
     ASSERT(nonmovingHeap.sweep_list == NULL);
     debugTrace(DEBUG_nonmoving_gc, "Finished sweeping.");
     traceConcSweepEnd();
+#if defined(DEBUG)
+    if (RtsFlags.DebugFlags.nonmoving_gc)
+        nonmovingPrintAllocatorCensus();
+#endif
 
     // TODO: Remainder of things done by GarbageCollect (update stats)
 
diff --git a/rts/sm/NonMovingCensus.c b/rts/sm/NonMovingCensus.c
new file mode 100644
index 0000000000..349ac77054
--- /dev/null
+++ b/rts/sm/NonMovingCensus.c
@@ -0,0 +1,94 @@
+/* -----------------------------------------------------------------------------
+ *
+ * (c) The GHC Team, 1998-2018
+ *
+ * Non-moving garbage collector and allocator: Accounting census
+ *
+ * This is a simple space accounting census useful for characterising
+ * fragmentation in the nonmoving heap.
+ *
+ * ---------------------------------------------------------------------------*/
+
+#include "Rts.h"
+#include "NonMoving.h"
+#include "Trace.h"
+#include "NonMovingCensus.h"
+
+struct NonmovingAllocCensus {
+    uint32_t n_active_segs;
+    uint32_t n_filled_segs;
+    uint32_t n_live_blocks;
+    uint32_t n_live_words;
+};
+
+// N.B. This may miss segments in the event of concurrent mutation (e.g. if a
+// mutator retires its current segment to the filled list).
+static struct NonmovingAllocCensus
+nonmovingAllocatorCensus(struct NonmovingAllocator *alloc)
+{
+    struct NonmovingAllocCensus census = {0, 0, 0, 0};
+
+    for (struct NonmovingSegment *seg = alloc->filled;
+         seg != NULL;
+         seg = seg->link)
+    {
+        census.n_filled_segs++;
+        census.n_live_blocks += nonmovingSegmentBlockCount(seg);
+        unsigned int n = nonmovingSegmentBlockCount(seg);
+        for (unsigned int i=0; i < n; i++) {
+            StgClosure *c = (StgClosure *) nonmovingSegmentGetBlock(seg, i);
+            census.n_live_words += closure_sizeW(c);
+        }
+    }
+
+    for (struct NonmovingSegment *seg = alloc->active;
+         seg != NULL;
+         seg = seg->link)
+    {
+        census.n_active_segs++;
+        unsigned int n = nonmovingSegmentBlockCount(seg);
+        for (unsigned int i=0; i < n; i++) {
+            if (nonmovingGetMark(seg, i)) {
+                StgClosure *c = (StgClosure *) nonmovingSegmentGetBlock(seg, i);
+                census.n_live_words += closure_sizeW(c);
+                census.n_live_blocks++;
+            }
+        }
+    }
+
+    for (unsigned int cap=0; cap < n_capabilities; cap++)
+    {
+        struct NonmovingSegment *seg = alloc->current[cap];
+        unsigned int n = nonmovingSegmentBlockCount(seg);
+        for (unsigned int i=0; i < n; i++) {
+            if (nonmovingGetMark(seg, i)) {
+                StgClosure *c = (StgClosure *) nonmovingSegmentGetBlock(seg, i);
+                census.n_live_words += closure_sizeW(c);
+                census.n_live_blocks++;
+            }
+        }
+    }
+    return census;
+}
+
+void nonmovingPrintAllocatorCensus()
+{
+    for (int i=0; i < NONMOVING_ALLOCA_CNT; i++) {
+        struct NonmovingAllocCensus census =
+            nonmovingAllocatorCensus(nonmovingHeap.allocators[i]);
+
+        uint32_t blk_size = 1 << (i + NONMOVING_ALLOCA0);
+        // We define occupancy as the fraction of space that is used for useful
+        // data (that is, live and not slop).
+        double occupancy = 100.0 * census.n_live_words * sizeof(W_)
+            / (census.n_live_blocks * blk_size);
+        if (census.n_live_blocks == 0) occupancy = 100;
+        (void) occupancy; // silence warning if !DEBUG
+        debugTrace(DEBUG_nonmoving_gc, "Allocator %d (%d bytes - %d bytes): "
+                   "%d active segs, %d filled segs, %d live blocks, %d live words "
+                   "(%2.1f%% occupancy)",
+                   i, 1 << (i + NONMOVING_ALLOCA0 - 1), 1 << (i + NONMOVING_ALLOCA0),
+                   census.n_active_segs, census.n_filled_segs, census.n_live_blocks, census.n_live_words,
+                   occupancy);
+    }
+}
diff --git a/rts/sm/NonMovingCensus.h b/rts/sm/NonMovingCensus.h
new file mode 100644
index 0000000000..a4f84c4dff
--- /dev/null
+++ b/rts/sm/NonMovingCensus.h
@@ -0,0 +1,11 @@
+/* -----------------------------------------------------------------------------
+ *
+ * (c) The GHC Team, 1998-2018
+ *
+ * Non-moving garbage collector and allocator: Accounting census
+ *
+ * ---------------------------------------------------------------------------*/
+
+#pragma once
+
+void nonmovingPrintAllocatorCensus(void);