Refactoring of the GC in preparation for parallel GC

  
This patch localises the state of the GC into a gc_thread structure,
and reorganises the inner loop of the GC to scavenge one block at a
time from global work lists in each "step".  The gc_thread structure
has a "workspace" for each step, in which it collects evacuated
objects until it has a full block to push out to the step's global
list.  Details of the algorithm will be on the wiki in due course.

At the moment, THREADED_RTS does not compile, but the single-threaded
GC works (and is 10-20% slower than before).

2 files changed, 60 insertions, 40 deletions

diff --git a/includes/RtsFlags.h b/includes/RtsFlags.h
index 88a6346098..bc36ebdb8f 100644
--- a/includes/RtsFlags.h
+++ b/includes/RtsFlags.h
@@ -175,6 +175,7 @@ struct PAR_FLAGS {
   rtsBool        migrate;        /* migrate threads between capabilities */
   rtsBool        wakeupMigrate;  /* migrate a thread on wakeup */
   unsigned int	 maxLocalSparks;
+  nat            gcThreads;      /* number of threads for parallel GC */
 };
 #endif /* THREADED_RTS */
 
diff --git a/includes/Storage.h b/includes/Storage.h
index af4b9bb498..48b7ec307e 100644
--- a/includes/Storage.h
+++ b/includes/Storage.h
@@ -11,6 +11,7 @@
 
 #include <stddef.h>
 #include "OSThreads.h"
+#include "SMP.h"
 
 /* -----------------------------------------------------------------------------
  * Generational GC
@@ -52,49 +53,58 @@
  * ------------------------------------------------------------------------- */
 
 typedef struct step_ {
-  unsigned int         no;		/* step number */
-  bdescr *             blocks;		/* blocks in this step */
-  unsigned int         n_blocks;	/* number of blocks */
-  struct step_ *       to;		/* destination step for live objects */
-  struct generation_ * gen;		/* generation this step belongs to */
-  unsigned int         gen_no;          /* generation number (cached) */
-  bdescr *             large_objects;	/* large objects (doubly linked) */
-  unsigned int         n_large_blocks;  /* no. of blocks used by large objs */
-  int                  is_compacted;	/* compact this step? (old gen only) */
-
-  /* During GC, if we are collecting this step, blocks and n_blocks
-   * are copied into the following two fields.  After GC, these blocks
-   * are freed. */
-  bdescr *     old_blocks;	        /* bdescr of first from-space block */
-  unsigned int n_old_blocks;		/* number of blocks in from-space */
-
-  /* temporary use during GC: */
-  StgPtr       hp;			/* next free locn in to-space */
-  StgPtr       hpLim;			/* end of current to-space block */
-  bdescr *     hp_bd;			/* bdescr of current to-space block */
-  StgPtr       scavd_hp;		/* ... same as above, but already */
-  StgPtr       scavd_hpLim;		/*     scavenged.  */
-  bdescr *     scan_bd;			/* block currently being scanned */
-  StgPtr       scan;			/* scan pointer in current block */
-  bdescr *     new_large_objects;    	/* large objects collected so far */
-  bdescr *     scavenged_large_objects; /* live large objs after GC (d-link) */
-  unsigned int n_scavenged_large_blocks;/* size of above */
-  bdescr *     bitmap;  		/* bitmap for compacting collection */
+    unsigned int         no;		// step number
+    int                  is_compacted;	// compact this step? (old gen only)
+
+    struct generation_ * gen;		// generation this step belongs to
+    unsigned int         gen_no;        // generation number (cached)
+
+    bdescr *             blocks;	// blocks in this step
+    unsigned int         n_blocks;	// number of blocks
+
+    struct step_ *       to;		// destination step for live objects
+
+    bdescr *             large_objects;	 // large objects (doubly linked)
+    unsigned int         n_large_blocks; // no. of blocks used by large objs
+
+    // ------------------------------------
+    // Fields below are used during GC only
+
+    // During GC, if we are collecting this step, blocks and n_blocks
+    // are copied into the following two fields.  After GC, these blocks
+    // are freed.
+    bdescr *     old_blocks;	        // bdescr of first from-space block
+    unsigned int n_old_blocks;		// number of blocks in from-space
+    
+    bdescr *     todos;		        // blocks waiting to be scavenged
+    unsigned int n_todos;               // count of above
+
+#if defined(THREADED_RTS)
+    SpinLock     sync_todo;             // lock for todos
+    SpinLock     sync_large_objects;    // lock for large_objects
+                                        //    and scavenged_large_objects
+#endif
+
+    bdescr *     scavenged_large_objects;  // live large objs after GC (d-link)
+    unsigned int n_scavenged_large_blocks; // size (not count) of above
+
+    bdescr *     bitmap;  		// bitmap for compacting collection
 } step;
 
+
 typedef struct generation_ {
-  unsigned int   no;			/* generation number */
-  step *         steps;			/* steps */
-  unsigned int   n_steps;		/* number of steps */
-  unsigned int   max_blocks;		/* max blocks in step 0 */
-  bdescr        *mut_list;      	/* mut objects in this gen (not G0)*/
-
-  /* temporary use during GC: */
-  bdescr        *saved_mut_list;
-
-  /* stats information */
-  unsigned int collections;
-  unsigned int failed_promotions;
+    unsigned int   no;			// generation number
+    step *         steps;		// steps
+    unsigned int   n_steps;		// number of steps
+    unsigned int   max_blocks;		// max blocks in step 0
+    bdescr        *mut_list;      	// mut objects in this gen (not G0)
+    
+    // stats information
+    unsigned int collections;
+    unsigned int failed_promotions;
+
+    // temporary use during GC:
+    bdescr        *saved_mut_list;
 } generation;
 
 extern generation * RTS_VAR(generations);
@@ -214,6 +224,7 @@ extern void GarbageCollect(rtsBool force_major_gc);
 #if defined(THREADED_RTS)
 extern Mutex sm_mutex;
 extern Mutex atomic_modify_mutvar_mutex;
+extern SpinLock recordMutableGen_sync;
 #endif
 
 #if defined(THREADED_RTS)
@@ -252,6 +263,14 @@ recordMutableGenLock(StgClosure *p, generation *gen)
 }
 
 INLINE_HEADER void
+recordMutableGen_GC(StgClosure *p, generation *gen)
+{
+    ACQUIRE_SPIN_LOCK(&recordMutableGen_sync);
+    recordMutableGen(p,gen);
+    RELEASE_SPIN_LOCK(&recordMutableGen_sync);
+}
+
+INLINE_HEADER void
 recordMutable(StgClosure *p)
 {
     bdescr *bd;