From d5bd3e829c47c03157cf41cad581d2df44dfd81b Mon Sep 17 00:00:00 2001 From: Simon Marlow Date: Wed, 31 Oct 2007 12:51:36 +0000 Subject: 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). --- includes/RtsFlags.h | 1 + includes/Storage.h | 99 +++++++++++++++++++++++++++++++---------------------- 2 files changed, 60 insertions(+), 40 deletions(-) (limited to 'includes') 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 #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) @@ -251,6 +262,14 @@ recordMutableGenLock(StgClosure *p, generation *gen) RELEASE_SM_LOCK; } +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) { -- cgit v1.2.1