Fix #650: use a card table to mark dirty sections of mutable arrays

The card table is an array of bytes, placed directly following the
actual array data.  This means that array reading is unaffected, but
array writing needs to read the array size from the header in order to
find the card table.

We use a bytemap rather than a bitmap, because updating the card table
must be multi-thread safe.  Each byte refers to 128 entries of the
array, but this is tunable by changing the constant
MUT_ARR_PTRS_CARD_BITS in includes/Constants.h.

6 files changed, 45 insertions, 1 deletions

diff --git a/includes/Cmm.h b/includes/Cmm.h
index 69b5acc5fc..ff91146745 100644
--- a/includes/Cmm.h
+++ b/includes/Cmm.h
@@ -463,6 +463,9 @@
 #define StgFunInfoExtra_bitmap(i)     StgFunInfoExtraFwd_bitmap(i)
 #endif
 
+#define mutArrPtrsCardWords(n) \
+    ROUNDUP_BYTES_TO_WDS(((n) + (1 << MUT_ARR_PTRS_CARD_BITS) - 1) >> MUT_ARR_PTRS_CARD_BITS)
+
 /* -----------------------------------------------------------------------------
    Voluntary Yields/Blocks
 
diff --git a/includes/HaskellConstants.hs b/includes/HaskellConstants.hs
index 1c1bb4891a..4555b474bf 100644
--- a/includes/HaskellConstants.hs
+++ b/includes/HaskellConstants.hs
@@ -62,6 +62,9 @@ mIN_CHARLIKE, mAX_CHARLIKE :: Int
 mIN_CHARLIKE = MIN_CHARLIKE
 mAX_CHARLIKE = MAX_CHARLIKE
 
+mUT_ARR_PTRS_CARD_BITS :: Int
+mUT_ARR_PTRS_CARD_BITS = MUT_ARR_PTRS_CARD_BITS
+
 -- A section of code-generator-related MAGIC CONSTANTS.
 
 mAX_Vanilla_REG :: Int
diff --git a/includes/mkDerivedConstants.c b/includes/mkDerivedConstants.c
index 0f1962cbbc..344b4265cb 100644
--- a/includes/mkDerivedConstants.c
+++ b/includes/mkDerivedConstants.c
@@ -279,6 +279,7 @@ main(int argc, char *argv[])
 
     closure_size(StgMutArrPtrs);
     closure_field(StgMutArrPtrs, ptrs);
+    closure_field(StgMutArrPtrs, size);
 
     closure_size(StgArrWords);
     closure_field(StgArrWords, words);
diff --git a/includes/rts/Constants.h b/includes/rts/Constants.h
index 8ebe16a662..0aee60aa83 100644
--- a/includes/rts/Constants.h
+++ b/includes/rts/Constants.h
@@ -66,6 +66,13 @@
 #define MAX_CHARLIKE		255
 #define MIN_CHARLIKE		0
 
+/* Each byte in the card table for an StgMutaArrPtrs covers
+ * (1<<MUT_ARR_PTRS_CARD_BITS) elements in the array.  To find a good
+ * value for this, I used the benchmarks nofib/gc/hash,
+ * nofib/gc/graph, and nofib/gc/gc_bench.
+ */
+#define MUT_ARR_PTRS_CARD_BITS 7
+
 /* -----------------------------------------------------------------------------
    STG Registers.
 
diff --git a/includes/rts/storage/ClosureMacros.h b/includes/rts/storage/ClosureMacros.h
index 458960f3f7..f73d2c5ccd 100644
--- a/includes/rts/storage/ClosureMacros.h
+++ b/includes/rts/storage/ClosureMacros.h
@@ -278,7 +278,7 @@ INLINE_HEADER StgOffset arr_words_sizeW( StgArrWords* x )
 { return sizeofW(StgArrWords) + x->words; }
 
 INLINE_HEADER StgOffset mut_arr_ptrs_sizeW( StgMutArrPtrs* x )
-{ return sizeofW(StgMutArrPtrs) + x->ptrs; }
+{ return sizeofW(StgMutArrPtrs) + x->size; }
 
 INLINE_HEADER StgWord tso_sizeW ( StgTSO *tso )
 { return TSO_STRUCT_SIZEW + tso->stack_size; }
@@ -392,4 +392,32 @@ INLINE_HEADER StgWord stack_frame_sizeW( StgClosure *frame )
     }
 }
 
+/* -----------------------------------------------------------------------------
+   StgMutArrPtrs macros
+
+   An StgMutArrPtrs has a card table to indicate which elements are
+   dirty for the generational GC.  The card table is an array of
+   bytes, where each byte covers (1 << MUT_ARR_PTRS_CARD_BITS)
+   elements.  The card table is directly after the array data itself.
+   -------------------------------------------------------------------------- */
+
+// The number of card bytes needed
+INLINE_HEADER lnat mutArrPtrsCards (lnat elems)
+{
+    return (lnat)((elems + (1 << MUT_ARR_PTRS_CARD_BITS) - 1)
+                           >> MUT_ARR_PTRS_CARD_BITS);
+}
+
+// The number of words in the card table
+INLINE_HEADER lnat mutArrPtrsCardTableSize (lnat elems)
+{
+    return ROUNDUP_BYTES_TO_WDS(mutArrPtrsCards(elems));
+}
+
+// The address of the card for a particular card number
+INLINE_HEADER StgWord8 *mutArrPtrsCard (StgMutArrPtrs *a, lnat n)
+{
+    return ((StgWord8 *)&(a->payload[a->ptrs]) + n);
+}
+
 #endif /* RTS_STORAGE_CLOSUREMACROS_H */
diff --git a/includes/rts/storage/Closures.h b/includes/rts/storage/Closures.h
index 6e06e57f3c..892826842e 100644
--- a/includes/rts/storage/Closures.h
+++ b/includes/rts/storage/Closures.h
@@ -136,7 +136,9 @@ typedef struct {
 typedef struct {
     StgHeader   header;
     StgWord     ptrs;
+    StgWord     size; // ptrs plus card table
     StgClosure *payload[FLEXIBLE_ARRAY];
+    // see also: StgMutArrPtrs macros in ClosureMacros.h
 } StgMutArrPtrs;
 
 typedef struct {