GCThread.h 7.87 KB
Newer Older
1 2
/* -----------------------------------------------------------------------------
 *
3
 * (c) The GHC Team 1998-2008
4 5 6 7 8 9 10 11 12 13
 *
 * Generational garbage collector
 *
 * Documentation on the architecture of the Garbage Collector can be
 * found in the online commentary:
 * 
 *   http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/GC
 *
 * ---------------------------------------------------------------------------*/

Simon Marlow's avatar
Simon Marlow committed
14 15
#ifndef SM_GCTHREAD_H
#define SM_GCTHREAD_H
16

17
#include "WSDeque.h"
Simon Marlow's avatar
Simon Marlow committed
18
#include "GetTime.h" // for Ticks
19

20
#include "BeginPrivate.h"
21

22 23 24 25 26 27 28 29 30 31 32 33
/* -----------------------------------------------------------------------------
   General scheme
   
   ToDo: move this to the wiki when the implementation is done.

   We're only going to try to parallelise the copying GC for now.  The
   Plan is as follows.

   Each thread has a gc_thread structure (see below) which holds its
   thread-local data.  We'll keep a pointer to this in a thread-local
   variable, or possibly in a register.

Simon Marlow's avatar
Simon Marlow committed
34 35
   In the gc_thread structure is a gen_workspace for each generation.  The
   primary purpose of the gen_workspace is to hold evacuated objects;
36
   when an object is evacuated, it is copied to the "todo" block in
Simon Marlow's avatar
Simon Marlow committed
37 38
   the thread's workspace for the appropriate generation.  When the todo
   block is full, it is pushed to the global gen->todos list, which
39 40 41 42
   is protected by a lock.  (in fact we intervene a one-place buffer
   here to reduce contention).

   A thread repeatedly grabs a block of work from one of the
Simon Marlow's avatar
Simon Marlow committed
43
   gen->todos lists, scavenges it, and keeps the scavenged block on
44
   its own ws->scavd_list (this is to avoid unnecessary contention
Simon Marlow's avatar
Simon Marlow committed
45
   returning the completed buffers back to the generation: we can just
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
   collect them all later).

   When there is no global work to do, we start scavenging the todo
   blocks in the workspaces.  This is where the scan_bd field comes
   in: we can scan the contents of the todo block, when we have
   scavenged the contents of the todo block (up to todo_bd->free), we
   don't want to move this block immediately to the scavd_list,
   because it is probably only partially full.  So we remember that we
   have scanned up to this point by saving the block in ws->scan_bd,
   with the current scan pointer in ws->scan.  Later, when more
   objects have been copied to this block, we can come back and scan
   the rest.  When we visit this workspace again in the future,
   scan_bd may still be the same as todo_bd, or it might be different:
   if enough objects were copied into this block that it filled up,
   then we will have allocated a new todo block, but *not* pushed the
Simon Marlow's avatar
Simon Marlow committed
61
   old one to the generation, because it is partially scanned.
62 63 64 65 66 67 68

   The reason to leave scanning the todo blocks until last is that we
   want to deal with full blocks as far as possible.
   ------------------------------------------------------------------------- */


/* -----------------------------------------------------------------------------
Simon Marlow's avatar
Simon Marlow committed
69
   Generation Workspace
70
  
Simon Marlow's avatar
Simon Marlow committed
71 72 73 74 75
   A generation workspace exists for each generation for each GC
   thread. The GC thread takes a block from the todos list of the
   generation into the scanbd and then scans it.  Objects referred to
   by those in the scan block are copied into the todo or scavd blocks
   of the relevant generation.
76 77 78
  
   ------------------------------------------------------------------------- */

Simon Marlow's avatar
Simon Marlow committed
79 80
typedef struct gen_workspace_ {
    generation * gen;		// the gen for this workspace 
81
    struct gc_thread_ * my_gct; // the gc_thread that contains this workspace
82 83 84 85 86 87

    // where objects to be scavenged go
    bdescr *     todo_bd;
    StgPtr       todo_free;            // free ptr for todo_bd
    StgPtr       todo_lim;             // lim for todo_bd

88 89 90
    WSDeque *    todo_q;
    bdescr *     todo_overflow;
    nat          n_todo_overflow;
91 92 93 94

    // where large objects to be scavenged go
    bdescr *     todo_large_objects;

95
    // Objects that have already been scavenged.
96 97 98 99 100 101 102
    bdescr *     scavd_list;
    nat          n_scavd_blocks;     // count of blocks in this list

    // Partially-full, scavenged, blocks
    bdescr *     part_list;
    unsigned int n_part_blocks;      // count of above

103
    StgWord pad[3];
104

Simon Marlow's avatar
Simon Marlow committed
105 106
} gen_workspace ATTRIBUTE_ALIGNED(64);
// align so that computing gct->gens[n] is a shift, not a multiply
107
// fails if the size is <64, which is why we need the pad above
108 109 110 111

/* ----------------------------------------------------------------------------
   GC thread object

Simon Marlow's avatar
Simon Marlow committed
112 113 114 115
   Every GC thread has one of these. It contains all the generation
   specific workspaces and other GC thread local information. At some
   later point it maybe useful to move this other into the TLS store
   of the GC threads
116 117 118
   ------------------------------------------------------------------------- */

typedef struct gc_thread_ {
Simon Marlow's avatar
Simon Marlow committed
119 120
    Capability *cap;

121 122
#ifdef THREADED_RTS
    OSThreadId id;                 // The OS thread that this struct belongs to
123 124 125
    SpinLock   gc_spin;
    SpinLock   mut_spin;
    volatile rtsBool wakeup;
126 127
#endif
    nat thread_index;              // a zero based index identifying the thread
128
    rtsBool idle;                  // sitting out of this GC cycle
129 130 131 132 133 134 135 136

    bdescr * free_blocks;          // a buffer of free blocks for this thread
                                   //  during GC without accessing the block
                                   //   allocators spin lock. 

    StgClosure* static_objects;      // live static objects
    StgClosure* scavenged_static_objects;   // static objects scavenged so far

137
    W_ gc_count;                 // number of GCs this thread has done
138 139 140 141

    // block that is currently being scanned
    bdescr *     scan_bd;

142 143 144 145 146 147 148 149
    // Remembered sets on this CPU.  Each GC thread has its own
    // private per-generation remembered sets, so it can add an item
    // to the remembered set without taking a lock.  The mut_lists
    // array on a gc_thread is the same as the one on the
    // corresponding Capability; we stash it here too for easy access
    // during GC; see recordMutableGen_GC().
    bdescr **    mut_lists;

150 151 152
    // --------------------
    // evacuate flags

Simon Marlow's avatar
Simon Marlow committed
153
    nat evac_gen_no;               // Youngest generation that objects
154 155 156 157 158 159 160 161 162 163 164 165 166 167 168
                                   // should be evacuated to in
                                   // evacuate().  (Logically an
                                   // argument to evacuate, but it's
                                   // static a lot of the time so we
                                   // optimise it into a per-thread
                                   // variable).

    rtsBool failed_to_evac;        // failure to evacuate an object typically 
                                   // Causes it to be recorded in the mutable 
                                   // object list

    rtsBool eager_promotion;       // forces promotion to the evac gen
                                   // instead of the to-space
                                   // corresponding to the object

169
    W_ thunk_selector_depth;     // used to avoid unbounded recursion in 
Simon Marlow's avatar
Simon Marlow committed
170
                                   // evacuate() for THUNK_SELECTOR
171 172 173 174 175 176 177 178

#ifdef USE_PAPI
    int papi_events;
#endif

    // -------------------
    // stats

179 180 181 182 183 184
    W_ allocated;          // result of clearNursery()
    W_ copied;
    W_ scanned;
    W_ any_work;
    W_ no_work;
    W_ scav_find_work;
185

Simon Marlow's avatar
Simon Marlow committed
186 187 188
    Time gc_start_cpu;   // process CPU time
    Time gc_start_elapsed;  // process elapsed time
    Time gc_start_thread_cpu; // thread CPU time
189
    W_ gc_start_faults;
Simon Marlow's avatar
Simon Marlow committed
190

191 192 193
    // -------------------
    // workspaces

Simon Marlow's avatar
Simon Marlow committed
194
    // array of workspaces, indexed by gen->abs_no.  This is placed
195 196 197 198
    // directly at the end of the gc_thread structure so that we can get from
    // the gc_thread pointer to a workspace using only pointer
    // arithmetic, no memory access.  This happens in the inner loop
    // of the GC, see Evac.c:alloc_for_copy().
Simon Marlow's avatar
Simon Marlow committed
199
    gen_workspace gens[];
200 201 202 203 204
} gc_thread;


extern nat n_gc_threads;

205 206
extern gc_thread **gc_threads;

207
#include "EndPrivate.h"
208

Simon Marlow's avatar
Simon Marlow committed
209
#endif // SM_GCTHREAD_H
210