rts: Introduce non-moving heap census
authorBen Gamari <ben@well-typed.com>
Tue, 5 Feb 2019 16:52:13 +0000 (11:52 -0500)
committerBen Gamari <ben@smart-cactus.org>
Wed, 19 Jun 2019 01:41:21 +0000 (21:41 -0400)
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.

rts/sm/NonMoving.c
rts/sm/NonMovingCensus.c [new file with mode: 0644]
rts/sm/NonMovingCensus.h [new file with mode: 0644]

index 427c0c4..9191292 100644 (file)
@@ -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
@@ -724,6 +725,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 (file)
index 0000000..349ac77
--- /dev/null
@@ -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 (file)
index 0000000..a4f84c4
--- /dev/null
@@ -0,0 +1,11 @@
+/* -----------------------------------------------------------------------------
+ *
+ * (c) The GHC Team, 1998-2018
+ *
+ * Non-moving garbage collector and allocator: Accounting census
+ *
+ * ---------------------------------------------------------------------------*/
+
+#pragma once
+
+void nonmovingPrintAllocatorCensus(void);