rts/sm/GCThread.h

   1 /* -----------------------------------------------------------------------------
   2  *
   3  * (c) The GHC Team 1998-2008
   4  *
   5  * Generational garbage collector
   6  *
   7  * Documentation on the architecture of the Garbage Collector can be
   8  * found in the online commentary:
   9  *
  10  *   http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/GC
  11  *
  12  * ---------------------------------------------------------------------------*/
  13
  14 #ifndef SM_GCTHREAD_H
  15 #define SM_GCTHREAD_H
  16
  17 #include "WSDeque.h"
  18
  19 /* -----------------------------------------------------------------------------
  20    General scheme
  21
  22    ToDo: move this to the wiki when the implementation is done.
  23
  24    We're only going to try to parallelise the copying GC for now.  The
  25    Plan is as follows.
  26
  27    Each thread has a gc_thread structure (see below) which holds its
  28    thread-local data.  We'll keep a pointer to this in a thread-local
  29    variable, or possibly in a register.
  30
  31    In the gc_thread structure is a step_workspace for each step.  The
  32    primary purpose of the step_workspace is to hold evacuated objects;
  33    when an object is evacuated, it is copied to the "todo" block in
  34    the thread's workspace for the appropriate step.  When the todo
  35    block is full, it is pushed to the global step->todos list, which
  36    is protected by a lock.  (in fact we intervene a one-place buffer
  37    here to reduce contention).
  38
  39    A thread repeatedly grabs a block of work from one of the
  40    step->todos lists, scavenges it, and keeps the scavenged block on
  41    its own ws->scavd_list (this is to avoid unnecessary contention
  42    returning the completed buffers back to the step: we can just
  43    collect them all later).
  44
  45    When there is no global work to do, we start scavenging the todo
  46    blocks in the workspaces.  This is where the scan_bd field comes
  47    in: we can scan the contents of the todo block, when we have
  48    scavenged the contents of the todo block (up to todo_bd->free), we
  49    don't want to move this block immediately to the scavd_list,
  50    because it is probably only partially full.  So we remember that we
  51    have scanned up to this point by saving the block in ws->scan_bd,
  52    with the current scan pointer in ws->scan.  Later, when more
  53    objects have been copied to this block, we can come back and scan
  54    the rest.  When we visit this workspace again in the future,
  55    scan_bd may still be the same as todo_bd, or it might be different:
  56    if enough objects were copied into this block that it filled up,
  57    then we will have allocated a new todo block, but *not* pushed the
  58    old one to the step, because it is partially scanned.
  59
  60    The reason to leave scanning the todo blocks until last is that we
  61    want to deal with full blocks as far as possible.
  62    ------------------------------------------------------------------------- */
  63
  64
  65 /* -----------------------------------------------------------------------------
  66    Step Workspace
  67
  68    A step workspace exists for each step for each GC thread. The GC
  69    thread takes a block from the todos list of the step into the
  70    scanbd and then scans it.  Objects referred to by those in the scan
  71    block are copied into the todo or scavd blocks of the relevant step.
  72
  73    ------------------------------------------------------------------------- */
  74
  75 typedef struct step_workspace_ {
  76     step * step;                // the step for this workspace
  77     struct gc_thread_ * my_gct; // the gc_thread that contains this workspace
  78
  79     // where objects to be scavenged go
  80     bdescr *     todo_bd;
  81     StgPtr       todo_free;            // free ptr for todo_bd
  82     StgPtr       todo_lim;             // lim for todo_bd
  83
  84     WSDeque *    todo_q;
  85     bdescr *     todo_overflow;
  86     nat          n_todo_overflow;
  87
  88     // where large objects to be scavenged go
  89     bdescr *     todo_large_objects;
  90
  91     // Objects that have already been scavenged.
  92     bdescr *     scavd_list;
  93     nat          n_scavd_blocks;     // count of blocks in this list
  94
  95     // Partially-full, scavenged, blocks
  96     bdescr *     part_list;
  97     unsigned int n_part_blocks;      // count of above
  98
  99     StgWord pad[3];
 100
 101 } step_workspace ATTRIBUTE_ALIGNED(64);
 102 // align so that computing gct->steps[n] is a shift, not a multiply
 103 // fails if the size is <64, which is why we need the pad above
 104
 105 /* ----------------------------------------------------------------------------
 106    GC thread object
 107
 108    Every GC thread has one of these. It contains all the step specific
 109    workspaces and other GC thread local information. At some later
 110    point it maybe useful to move this other into the TLS store of the
 111    GC threads
 112    ------------------------------------------------------------------------- */
 113
 114 typedef struct gc_thread_ {
 115 #ifdef THREADED_RTS
 116     OSThreadId id;                 // The OS thread that this struct belongs to
 117     SpinLock   gc_spin;
 118     SpinLock   mut_spin;
 119     volatile rtsBool wakeup;
 120 #endif
 121     nat thread_index;              // a zero based index identifying the thread
 122
 123     bdescr * free_blocks;          // a buffer of free blocks for this thread
 124                                    //  during GC without accessing the block
 125                                    //   allocators spin lock.
 126
 127     StgClosure* static_objects;      // live static objects
 128     StgClosure* scavenged_static_objects;   // static objects scavenged so far
 129
 130     lnat gc_count;                 // number of GCs this thread has done
 131
 132     // block that is currently being scanned
 133     bdescr *     scan_bd;
 134
 135     // Remembered sets on this CPU.  Each GC thread has its own
 136     // private per-generation remembered sets, so it can add an item
 137     // to the remembered set without taking a lock.  The mut_lists
 138     // array on a gc_thread is the same as the one on the
 139     // corresponding Capability; we stash it here too for easy access
 140     // during GC; see recordMutableGen_GC().
 141     bdescr **    mut_lists;
 142
 143     // --------------------
 144     // evacuate flags
 145
 146     step *evac_step;               // Youngest generation that objects
 147                                    // should be evacuated to in
 148                                    // evacuate().  (Logically an
 149                                    // argument to evacuate, but it's
 150                                    // static a lot of the time so we
 151                                    // optimise it into a per-thread
 152                                    // variable).
 153
 154     rtsBool failed_to_evac;        // failure to evacuate an object typically
 155                                    // Causes it to be recorded in the mutable
 156                                    // object list
 157
 158     rtsBool eager_promotion;       // forces promotion to the evac gen
 159                                    // instead of the to-space
 160                                    // corresponding to the object
 161
 162     lnat thunk_selector_depth;     // ummm.... not used as of now
 163
 164 #ifdef USE_PAPI
 165     int papi_events;
 166 #endif
 167
 168     // -------------------
 169     // stats
 170
 171     lnat copied;
 172     lnat scanned;
 173     lnat any_work;
 174     lnat no_work;
 175     lnat scav_find_work;
 176
 177     // -------------------
 178     // workspaces
 179
 180     // array of workspaces, indexed by stp->abs_no.  This is placed
 181     // directly at the end of the gc_thread structure so that we can get from
 182     // the gc_thread pointer to a workspace using only pointer
 183     // arithmetic, no memory access.  This happens in the inner loop
 184     // of the GC, see Evac.c:alloc_for_copy().
 185     step_workspace steps[];
 186 } gc_thread;
 187
 188
 189 extern nat n_gc_threads;
 190
 191 /* -----------------------------------------------------------------------------
 192    The gct variable is thread-local and points to the current thread's
 193    gc_thread structure.  It is heavily accessed, so we try to put gct
 194    into a global register variable if possible; if we don't have a
 195    register then use gcc's __thread extension to create a thread-local
 196    variable.
 197
 198    Even on x86 where registers are scarce, it is worthwhile using a
 199    register variable here: I measured about a 2-5% slowdown with the
 200    __thread version.
 201    -------------------------------------------------------------------------- */
 202
 203 extern gc_thread **gc_threads;
 204
 205 #if defined(THREADED_RTS)
 206
 207 #define GLOBAL_REG_DECL(type,name,reg) register type name REG(reg);
 208
 209 #define SET_GCT(to) gct = (to)
 210
 211
 212
 213 #if (defined(i386_HOST_ARCH) && defined(linux_HOST_OS))
 214 // Using __thread is better than stealing a register on x86/Linux, because
 215 // we have too few registers available.  In my tests it was worth
 216 // about 5% in GC performance, but of course that might change as gcc
 217 // improves. -- SDM 2009/04/03
 218
 219 extern __thread gc_thread* gct;
 220 #define DECLARE_GCT __thread gc_thread* gct;
 221
 222
 223 #elif defined(sparc_TARGET_ARCH)
 224 // On SPARC we can't pin gct to a register. Names like %l1 are just offsets
 225 //      into the register window, which change on each function call.
 226 //
 227 //      There are eight global (non-window) registers, but they're used for other purposes.
 228 //      %g0     -- always zero
 229 //      %g1     -- volatile over function calls, used by the linker
 230 //      %g2-%g3 -- used as scratch regs by the C compiler (caller saves)
 231 //      %g4     -- volatile over function calls, used by the linker
 232 //      %g5-%g7 -- reserved by the OS
 233
 234 extern __thread gc_thread* gct;
 235 #define DECLARE_GCT __thread gc_thread* gct;
 236
 237
 238 #elif defined(REG_Base) && !defined(i386_HOST_ARCH)
 239 // on i386, REG_Base is %ebx which is also used for PIC, so we don't
 240 // want to steal it
 241
 242 GLOBAL_REG_DECL(gc_thread*, gct, REG_Base)
 243 #define DECLARE_GCT /* nothing */
 244
 245
 246 #elif defined(REG_R1)
 247
 248 GLOBAL_REG_DECL(gc_thread*, gct, REG_R1)
 249 #define DECLARE_GCT /* nothing */
 250
 251
 252 #elif defined(__GNUC__)
 253
 254 extern __thread gc_thread* gct;
 255 #define DECLARE_GCT __thread gc_thread* gct;
 256
 257 #else
 258
 259 #error Cannot find a way to declare the thread-local gct
 260
 261 #endif
 262
 263 #else  // not the threaded RTS
 264
 265 extern StgWord8 the_gc_thread[];
 266
 267 #define gct ((gc_thread*)&the_gc_thread)
 268 #define SET_GCT(to) /*nothing*/
 269 #define DECLARE_GCT /*nothing*/
 270
 271 #endif
 272
 273 #endif // SM_GCTHREAD_H
 274