rts/sm/GC.h

   1 /* -----------------------------------------------------------------------------
   2  *
   3  * (c) The GHC Team 1998-2006
   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 GC_H
  15 #define GC_H
  16
  17 #include "OSThreads.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 * stp;                 // the step for this workspace
  77     struct gc_thread_ * gct;    // the gc_thread that contains this workspace
  78
  79     // block that is currently being scanned
  80     bdescr *     scan_bd;
  81     StgPtr       scan;               // the scan pointer
  82
  83     // where objects to be scavenged go
  84     bdescr *     todo_bd;
  85     bdescr *     buffer_todo_bd;     // buffer to reduce contention
  86                                      // on the step's todos list
  87
  88     // where large objects to be scavenged go
  89     bdescr *     todo_large_objects;
  90
  91     // Objects that need not be, or have already been, scavenged.  The
  92     // block at the front of the list is special: objects that don't
  93     // need to be scavenged are copied directly to this block.
  94     // Completed scan blocks also go on this list; but we put them
  95     // after the head block.
  96     bdescr *     scavd_list;
  97     lnat         n_scavd_blocks;     // count of blocks in this list
  98
  99 } step_workspace;
 100
 101 /* ----------------------------------------------------------------------------
 102    GC thread object
 103
 104    Every GC thread has one of these. It contains all the step specific
 105    workspaces and other GC thread loacl information. At some later
 106    point it maybe useful to move this other into the TLS store of the
 107    GC threads
 108    ------------------------------------------------------------------------- */
 109
 110 typedef struct gc_thread_ {
 111 #ifdef THREADED_RTS
 112     OSThreadId id;                 // The OS thread that this struct belongs to
 113     Mutex      wake_mutex;
 114     Condition  wake_cond;          // So we can go to sleep between GCs
 115     rtsBool    wakeup;
 116     rtsBool    exit;
 117 #endif
 118     nat thread_index;              // a zero based index identifying the thread
 119
 120     step_workspace ** steps;       // 2-d array (gen,step) of workspaces
 121
 122     bdescr * free_blocks;          // a buffer of free blocks for this thread
 123                                    //  during GC without accessing the block
 124                                    //   allocators spin lock.
 125
 126     lnat gc_count;                 // number of gc's this thread has done
 127
 128     // --------------------
 129     // evacuate flags
 130
 131     step *evac_step;               // Youngest generation that objects
 132                                    // should be evacuated to in
 133                                    // evacuate().  (Logically an
 134                                    // argument to evacuate, but it's
 135                                    // static a lot of the time so we
 136                                    // optimise it into a per-thread
 137                                    // variable).
 138
 139     rtsBool failed_to_evac;        // failue to evacuate an object typically
 140                                    //  causes it to be recorded in the mutable
 141                                    //  object list
 142
 143     rtsBool eager_promotion;       // forces promotion to the evac gen
 144                                    // instead of the to-space
 145                                    // corresponding to the object
 146
 147     lnat thunk_selector_depth;     // ummm.... not used as of now
 148
 149 } gc_thread;
 150
 151 extern nat N;
 152 extern rtsBool major_gc;
 153
 154 extern gc_thread *gc_threads;
 155 register gc_thread *gct __asm__("%rbx");
 156 // extern gc_thread *gct;  // this thread's gct TODO: make thread-local
 157
 158 extern StgClosure* static_objects;
 159 extern StgClosure* scavenged_static_objects;
 160
 161 extern bdescr *mark_stack_bdescr;
 162 extern StgPtr *mark_stack;
 163 extern StgPtr *mark_sp;
 164 extern StgPtr *mark_splim;
 165
 166 extern rtsBool mark_stack_overflowed;
 167 extern bdescr *oldgen_scan_bd;
 168 extern StgPtr  oldgen_scan;
 169
 170 extern long copied;
 171 extern long scavd_copied;
 172
 173 #ifdef THREADED_RTS
 174 extern SpinLock static_objects_sync;
 175 #endif
 176
 177 #ifdef DEBUG
 178 extern nat mutlist_MUTVARS, mutlist_MUTARRS, mutlist_MVARS, mutlist_OTHERS;
 179 #endif
 180
 181 StgClosure * isAlive(StgClosure *p);
 182
 183 #endif /* GC_H */