Overhaul of Compact Regions (#12455)

Summary:
This commit makes various improvements and addresses some issues with
Compact Regions (aka Compact Normal Forms).

This was the most important thing I wanted to fix.  Compaction
previously prevented GC from running until it was complete, which
would be a problem in a multicore setting.  Now, we compact using a
hand-written Cmm routine that can be interrupted at any point.  When a
GC is triggered during a sharing-enabled compaction, the GC has to
traverse and update the hash table, so this hash table is now stored
in the StgCompactNFData object.

Previously, compaction consisted of a deepseq using the NFData class,
followed by a traversal in C code to copy the data.  This is now done
in a single pass with hand-written Cmm (see rts/Compact.cmm). We no
longer use the NFData instances, instead the Cmm routine evaluates
components directly as it compacts.

The new compaction is about 50% faster than the old one with no
sharing, and a little faster on average with sharing (the cost of the
hash table dominates when we're doing sharing).

Static objects that don't (transitively) refer to any CAFs don't need
to be copied into the compact region.  In particular this means we
often avoid copying Char values and small Int values, because these
are static closures in the runtime.

Each Compact# object can support a single compactAdd# operation at any
given time, so the Data.Compact library now enforces mutual exclusion
using an MVar stored in the Compact object.

We now get exceptions rather than killing everything with a barf()
when we encounter an object that cannot be compacted (a function, or a
mutable object).  We now also detect pinned objects, which can't be
compacted either.

The Data.Compact API has been refactored and cleaned up.  A new
compactSize operation returns the size (in bytes) of the compact
object.

Most of the documentation is in the Haddock docs for the compact
library, which I've expanded and improved here.

Various comments in the code have been improved, especially the main
Note [Compact Normal Forms] in rts/sm/CNF.c.

I've added a few tests, and expanded a few of the tests that were
there.  We now also run the tests with GHCi, and in a new test way
that enables sanity checking (+RTS -DS).

There's a benchmark in libraries/compact/tests/compact_bench.hs for
measuring compaction speed and comparing sharing vs. no sharing.

The field totalDataW in StgCompactNFData was unnecessary.

Test Plan:
* new unit tests
* validate
* tested manually that we can compact Data.Aeson data

Reviewers: gcampax, bgamari, ezyang, austin, niteria, hvr, erikd

Subscribers: thomie, simonpj

Differential Revision: https://phabricator.haskell.org/D2751

GHC Trac Issues: #12455

4 files changed, 55 insertions, 44 deletions

diff --git a/includes/rts/Flags.h b/includes/rts/Flags.h
index 21ff2ab1c5..62d0800e68 100644
--- a/includes/rts/Flags.h
+++ b/includes/rts/Flags.h
@@ -95,6 +95,7 @@ typedef struct _DEBUG_FLAGS {
     bool hpc;            /* 'c' coverage */
     bool sparks;         /* 'r' */
     bool numa;           /* '--debug-numa' */
+    bool compact;        /* 'C' */
 } DEBUG_FLAGS;
 
 /* See Note [Synchronization of flags and base APIs] */
diff --git a/includes/rts/storage/ClosureMacros.h b/includes/rts/storage/ClosureMacros.h
index f5ca5cd850..90198f20e8 100644
--- a/includes/rts/storage/ClosureMacros.h
+++ b/includes/rts/storage/ClosureMacros.h
@@ -421,12 +421,6 @@ closure_sizeW_ (const StgClosure *p, const StgInfoTable *info)
         return bco_sizeW((StgBCO *)p);
     case TREC_CHUNK:
         return sizeofW(StgTRecChunk);
-    case COMPACT_NFDATA:
-        // Nothing should ever call closure_sizeW() on a StgCompactNFData
-        // because CompactNFData is a magical object/list-of-objects that
-        // requires special paths pretty much everywhere in the GC
-        barf("closure_sizeW() called on a StgCompactNFData. "
-             "This should never happen.");
     default:
         return sizeW_fromITBL(info);
     }
diff --git a/includes/rts/storage/Closures.h b/includes/rts/storage/Closures.h
index 4dda0a7f3a..2c62552b2f 100644
--- a/includes/rts/storage/Closures.h
+++ b/includes/rts/storage/Closures.h
@@ -419,49 +419,61 @@ typedef struct MessageBlackHole_ {
     StgClosure *bh;
 } MessageBlackHole;
 
-// This is not a closure, it a bare
-// structure that lives at the beginning of
-// each consecutive block group in a
-// compact structure
+/* ----------------------------------------------------------------------------
+   Compact Regions
+   ------------------------------------------------------------------------- */
+
+//
+// A compact region is a list of blocks.  Each block starts with an
+// StgCompactNFDataBlock structure, and the list is chained through the next
+// field of these structs.  (the link field of the bdescr is used to chain
+// together multiple compact region on the compact_objects field of a
+// generation).
 //
 // See Note [Compact Normal Forms] for details
+//
 typedef struct StgCompactNFDataBlock_ {
-    struct StgCompactNFDataBlock_ *self; // the address of this block
-                                         // this is copied over to the receiving
-                                         // end when serializing a compact, so
-                                         // the receiving end can allocate the
-                                         // block at best as it can, and then
-                                         // verify if pointer adjustment is
-                                         // needed or not by comparing self with
-                                         // the actual address; the same data
-                                         // is sent over as SerializedCompact
-                                         // metadata, but having it here
-                                         // simplifies the fixup implementation
-    struct StgCompactNFData_ *owner; // the closure who owns this
-                                     // block (used in objectGetCompact)
-    struct StgCompactNFDataBlock_ *next; // chain of blocks used for
-                                         // serialization and freeing
+    struct StgCompactNFDataBlock_ *self;
+       // the address of this block this is copied over to the
+       // receiving end when serializing a compact, so the receiving
+       // end can allocate the block at best as it can, and then
+       // verify if pointer adjustment is needed or not by comparing
+       // self with the actual address; the same data is sent over as
+       // SerializedCompact metadata, but having it here simplifies
+       // the fixup implementation.
+    struct StgCompactNFData_ *owner;
+       // the closure who owns this block (used in objectGetCompact)
+    struct StgCompactNFDataBlock_ *next;
+       // chain of blocks used for serialization and freeing
 } StgCompactNFDataBlock;
 
+//
+// This is the Compact# primitive object.
+//
 typedef struct StgCompactNFData_ {
-    StgHeader              header; // for sanity and other checks in practice,
-                                   // nothing should ever need the compact info
-                                   // pointer (we don't even need fwding
-                                   // pointers because it's a large object)
-    StgWord                totalW; // for proper accounting in evac, includes
-                                   // slop, and removes the first block in
-                                   // larger than megablock allocation
-                                   // essentially meaningless, but if we got it
-                                   // wrong sanity would complain loudly
-    StgWord                totalDataW; // for stats/profiling only, it's the
-                                       // full amount of memory used by this
-                                       // compact, including the portions not
-                                       // yet used
-    StgWord                autoBlockW; // size of automatically appended blocks
-    StgCompactNFDataBlock *nursery; // where to (try to) allocate from when
-                                    // appending
-    StgCompactNFDataBlock *last; // the last block of the chain (to know where
-                                 // to append new blocks for resize)
+    StgHeader header;
+      // for sanity and other checks in practice, nothing should ever
+      // need the compact info pointer (we don't even need fwding
+      // pointers because it's a large object)
+    StgWord totalW;
+      // Total number of words in all blocks in the compact
+    StgWord autoBlockW;
+      // size of automatically appended blocks
+    StgPtr hp, hpLim;
+      // the beginning and end of the free area in the nursery block.  This is
+      // just a convenience so that we can avoid multiple indirections through
+      // the nursery pointer below during compaction.
+    StgCompactNFDataBlock *nursery;
+      // where to (try to) allocate from when appending
+    StgCompactNFDataBlock *last;
+      // the last block of the chain (to know where to append new
+      // blocks for resize)
+    struct hashtable *hash;
+      // the hash table for the current compaction, or NULL if
+      // there's no (sharing-preserved) compaction in progress.
+    StgClosure *result;
+      // Used temporarily to store the result of compaction.  Doesn't need to be
+      // a GC root.
 } StgCompactNFData;
 
 
diff --git a/includes/stg/MiscClosures.h b/includes/stg/MiscClosures.h
index 07a7752ed2..65562b2c4b 100644
--- a/includes/stg/MiscClosures.h
+++ b/includes/stg/MiscClosures.h
@@ -151,7 +151,8 @@ RTS_ENTRY(stg_END_STM_WATCH_QUEUE);
 RTS_ENTRY(stg_END_INVARIANT_CHECK_QUEUE);
 RTS_ENTRY(stg_END_STM_CHUNK_LIST);
 RTS_ENTRY(stg_NO_TREC);
-RTS_ENTRY(stg_COMPACT_NFDATA);
+RTS_ENTRY(stg_COMPACT_NFDATA_CLEAN);
+RTS_ENTRY(stg_COMPACT_NFDATA_DIRTY);
 
 /* closures */
 
@@ -411,6 +412,8 @@ RTS_FUN_DECL(stg_makeStableNamezh);
 RTS_FUN_DECL(stg_makeStablePtrzh);
 RTS_FUN_DECL(stg_deRefStablePtrzh);
 
+RTS_FUN_DECL(stg_compactAddzh);
+RTS_FUN_DECL(stg_compactAddWithSharingzh);
 RTS_FUN_DECL(stg_compactNewzh);
 RTS_FUN_DECL(stg_compactAppendzh);
 RTS_FUN_DECL(stg_compactResizzezh);
@@ -421,6 +424,7 @@ RTS_FUN_DECL(stg_compactGetFirstBlockzh);
 RTS_FUN_DECL(stg_compactGetNextBlockzh);
 RTS_FUN_DECL(stg_compactAllocateBlockzh);
 RTS_FUN_DECL(stg_compactFixupPointerszh);
+RTS_FUN_DECL(stg_compactSizzezh);
 
 RTS_FUN_DECL(stg_forkzh);
 RTS_FUN_DECL(stg_forkOnzh);