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.

3 files changed, 110 insertions, 0 deletions

diff --git a/rts/sm/NonMoving.c b/rts/sm/NonMoving.c
index ede1fe2138..2e767e2ec4 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
@@ -684,6 +685,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);