GC refactoring: change evac_gen to evac_step
[ghc.git] / 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 */