Update comment now that we have per-gen weak pointer lists.
[ghc.git] / rts / sm / MarkWeak.c
1 /* -----------------------------------------------------------------------------
2 *
3 * (c) The GHC Team 1998-2008
4 *
5 * Weak pointers and weak-like things in the GC
6 *
7 * Documentation on the architecture of the Garbage Collector can be
8 * found in the online commentary:
9 *
10 * http://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/GC
11 *
12 * ---------------------------------------------------------------------------*/
13
14 #include "PosixSource.h"
15 #include "Rts.h"
16
17 #include "MarkWeak.h"
18 #include "GC.h"
19 #include "GCThread.h"
20 #include "GCTDecl.h"
21 #include "Evac.h"
22 #include "Trace.h"
23 #include "Schedule.h"
24 #include "Weak.h"
25 #include "Storage.h"
26 #include "Threads.h"
27
28 /* -----------------------------------------------------------------------------
29 Weak Pointers
30
31 traverse_weak_ptr_list is called possibly many times during garbage
32 collection. It returns a flag indicating whether it did any work
33 (i.e. called evacuate on any live pointers).
34
35 Invariant: traverse_weak_ptr_list is called when the heap is in an
36 idempotent state. That means that there are no pending
37 evacuate/scavenge operations. This invariant helps the weak
38 pointer code decide which weak pointers are dead - if there are no
39 new live weak pointers, then all the currently unreachable ones are
40 dead.
41
42 For generational GC: we don't try to finalize weak pointers in
43 older generations than the one we're collecting.
44
45 There are three distinct stages to processing weak pointers:
46
47 - weak_stage == WeakPtrs
48
49 We process all the weak pointers whos keys are alive (evacuate
50 their values and finalizers), and repeat until we can find no new
51 live keys. If no live keys are found in this pass, then we
52 evacuate the finalizers of all the dead weak pointers in order to
53 run them.
54
55 - weak_stage == WeakThreads
56
57 Now, we discover which *threads* are still alive. Pointers to
58 threads from the all_threads and main thread lists are the
59 weakest of all: a pointers from the finalizer of a dead weak
60 pointer can keep a thread alive. Any threads found to be unreachable
61 are evacuated and placed on the resurrected_threads list so we
62 can send them a signal later.
63
64 - weak_stage == WeakDone
65
66 No more evacuation is done.
67
68 -------------------------------------------------------------------------- */
69
70 /* Which stage of processing various kinds of weak pointer are we at?
71 * (see traverse_weak_ptr_list() below for discussion).
72 */
73 typedef enum { WeakPtrs, WeakThreads, WeakDone } WeakStage;
74 static WeakStage weak_stage;
75
76 // List of weak pointers whose key is dead
77 StgWeak *dead_weak_ptr_list;
78
79 // List of threads found to be unreachable
80 StgTSO *resurrected_threads;
81
82 static void collectDeadWeakPtrs (generation *gen);
83 static rtsBool tidyWeakList (generation *gen);
84 static rtsBool resurrectUnreachableThreads (generation *gen);
85 static void tidyThreadList (generation *gen);
86
87 void
88 initWeakForGC(void)
89 {
90 nat g;
91
92 for (g = 0; g <= N; g++) {
93 generation *gen = &generations[g];
94 gen->old_weak_ptr_list = gen->weak_ptr_list;
95 gen->weak_ptr_list = NULL;
96 }
97
98 weak_stage = WeakThreads;
99 dead_weak_ptr_list = NULL;
100 resurrected_threads = END_TSO_QUEUE;
101 }
102
103 rtsBool
104 traverseWeakPtrList(void)
105 {
106 rtsBool flag = rtsFalse;
107
108 switch (weak_stage) {
109
110 case WeakDone:
111 return rtsFalse;
112
113 case WeakThreads:
114 /* Now deal with the gen->threads lists, which behave somewhat like
115 * the weak ptr list. If we discover any threads that are about to
116 * become garbage, we wake them up and administer an exception.
117 */
118 {
119 nat g;
120
121 for (g = 0; g <= N; g++) {
122 tidyThreadList(&generations[g]);
123 }
124
125 // Use weak pointer relationships (value is reachable if
126 // key is reachable):
127 for (g = 0; g <= N; g++) {
128 if (tidyWeakList(&generations[g])) {
129 flag = rtsTrue;
130 }
131 }
132
133 // if we evacuated anything new, we must scavenge thoroughly
134 // before we can determine which threads are unreachable.
135 if (flag) return rtsTrue;
136
137 // Resurrect any threads which were unreachable
138 for (g = 0; g <= N; g++) {
139 if (resurrectUnreachableThreads(&generations[g])) {
140 flag = rtsTrue;
141 }
142 }
143
144 // Next, move to the WeakPtrs stage after fully
145 // scavenging the finalizers we've just evacuated.
146 weak_stage = WeakPtrs;
147
148 // if we evacuated anything new, we must scavenge thoroughly
149 // before entering the WeakPtrs stage.
150 if (flag) return rtsTrue;
151
152 // otherwise, fall through...
153 }
154
155 case WeakPtrs:
156 {
157 nat g;
158
159 // resurrecting threads might have made more weak pointers
160 // alive, so traverse those lists again:
161 for (g = 0; g <= N; g++) {
162 if (tidyWeakList(&generations[g])) {
163 flag = rtsTrue;
164 }
165 }
166
167 /* If we didn't make any changes, then we can go round and kill all
168 * the dead weak pointers. The dead_weak_ptr list is used as a list
169 * of pending finalizers later on.
170 */
171 if (flag == rtsFalse) {
172 for (g = 0; g <= N; g++) {
173 collectDeadWeakPtrs(&generations[g]);
174 }
175
176 weak_stage = WeakDone; // *now* we're done,
177 }
178
179 return rtsTrue; // but one more round of scavenging, please
180 }
181
182 default:
183 barf("traverse_weak_ptr_list");
184 return rtsTrue;
185 }
186 }
187
188 static void collectDeadWeakPtrs (generation *gen)
189 {
190 StgWeak *w, *next_w;
191 for (w = gen->old_weak_ptr_list; w != NULL; w = next_w) {
192 evacuate(&w->finalizer);
193 next_w = w->link;
194 w->link = dead_weak_ptr_list;
195 dead_weak_ptr_list = w;
196 }
197 }
198
199 static rtsBool resurrectUnreachableThreads (generation *gen)
200 {
201 StgTSO *t, *tmp, *next;
202 rtsBool flag = rtsFalse;
203
204 for (t = gen->old_threads; t != END_TSO_QUEUE; t = next) {
205 next = t->global_link;
206
207 // ThreadFinished and ThreadComplete: we have to keep
208 // these on the all_threads list until they
209 // become garbage, because they might get
210 // pending exceptions.
211 switch (t->what_next) {
212 case ThreadKilled:
213 case ThreadComplete:
214 continue;
215 default:
216 tmp = t;
217 evacuate((StgClosure **)&tmp);
218 tmp->global_link = resurrected_threads;
219 resurrected_threads = tmp;
220 flag = rtsTrue;
221 }
222 }
223 return flag;
224 }
225
226 static rtsBool tidyWeakList(generation *gen)
227 {
228 StgWeak *w, **last_w, *next_w;
229 const StgInfoTable *info;
230 StgClosure *new;
231 rtsBool flag = rtsFalse;
232 last_w = &gen->old_weak_ptr_list;
233 for (w = gen->old_weak_ptr_list; w != NULL; w = next_w) {
234
235 /* There might be a DEAD_WEAK on the list if finalizeWeak# was
236 * called on a live weak pointer object. Just remove it.
237 */
238 if (w->header.info == &stg_DEAD_WEAK_info) {
239 next_w = w->link;
240 *last_w = next_w;
241 continue;
242 }
243
244 info = get_itbl((StgClosure *)w);
245 switch (info->type) {
246
247 case WEAK:
248 /* Now, check whether the key is reachable.
249 */
250 new = isAlive(w->key);
251 if (new != NULL) {
252 generation *new_gen;
253
254 w->key = new;
255
256 // Find out which generation this weak ptr is in, and
257 // move it onto the weak ptr list of that generation.
258
259 new_gen = Bdescr((P_)w)->gen;
260 gct->evac_gen_no = new_gen->no;
261
262 // evacuate the value and finalizer
263 evacuate(&w->value);
264 evacuate(&w->finalizer);
265 // remove this weak ptr from the old_weak_ptr list
266 *last_w = w->link;
267 next_w = w->link;
268
269 // and put it on the correct weak ptr list.
270 w->link = new_gen->weak_ptr_list;
271 new_gen->weak_ptr_list = w;
272 flag = rtsTrue;
273
274 if (gen->no != new_gen->no) {
275 debugTrace(DEBUG_weak,
276 "moving weak pointer %p from %d to %d",
277 w, gen->no, new_gen->no);
278 }
279
280
281 debugTrace(DEBUG_weak,
282 "weak pointer still alive at %p -> %p",
283 w, w->key);
284 continue;
285 }
286 else {
287 last_w = &(w->link);
288 next_w = w->link;
289 continue;
290 }
291
292 default:
293 barf("tidyWeakList: not WEAK: %d, %p", info->type, w);
294 }
295 }
296
297 return flag;
298 }
299
300 static void tidyThreadList (generation *gen)
301 {
302 StgTSO *t, *tmp, *next, **prev;
303
304 prev = &gen->old_threads;
305
306 for (t = gen->old_threads; t != END_TSO_QUEUE; t = next) {
307
308 tmp = (StgTSO *)isAlive((StgClosure *)t);
309
310 if (tmp != NULL) {
311 t = tmp;
312 }
313
314 ASSERT(get_itbl((StgClosure *)t)->type == TSO);
315 next = t->global_link;
316
317 // if the thread is not masking exceptions but there are
318 // pending exceptions on its queue, then something has gone
319 // wrong. However, pending exceptions are OK if there is an
320 // FFI call.
321 ASSERT(t->blocked_exceptions == END_BLOCKED_EXCEPTIONS_QUEUE
322 || t->why_blocked == BlockedOnCCall
323 || t->why_blocked == BlockedOnCCall_Interruptible
324 || (t->flags & TSO_BLOCKEX));
325
326 if (tmp == NULL) {
327 // not alive (yet): leave this thread on the
328 // old_all_threads list.
329 prev = &(t->global_link);
330 }
331 else {
332 // alive
333 *prev = next;
334
335 // move this thread onto the correct threads list.
336 generation *new_gen;
337 new_gen = Bdescr((P_)t)->gen;
338 t->global_link = new_gen->threads;
339 new_gen->threads = t;
340 }
341 }
342 }
343
344 /* -----------------------------------------------------------------------------
345 Evacuate every weak pointer object on the weak_ptr_list, and update
346 the link fields.
347 -------------------------------------------------------------------------- */
348
349 void
350 markWeakPtrList ( void )
351 {
352 nat g;
353
354 for (g = 0; g <= N; g++) {
355 generation *gen = &generations[g];
356 StgWeak *w, **last_w;
357
358 last_w = &gen->weak_ptr_list;
359 for (w = gen->weak_ptr_list; w != NULL; w = w->link) {
360 // w might be WEAK, EVACUATED, or DEAD_WEAK (actually CON_STATIC) here
361
362 #ifdef DEBUG
363 { // careful to do this assertion only reading the info ptr
364 // once, because during parallel GC it might change under our feet.
365 const StgInfoTable *info;
366 info = w->header.info;
367 ASSERT(IS_FORWARDING_PTR(info)
368 || info == &stg_DEAD_WEAK_info
369 || INFO_PTR_TO_STRUCT(info)->type == WEAK);
370 }
371 #endif
372
373 evacuate((StgClosure **)last_w);
374 w = *last_w;
375 if (w->header.info == &stg_DEAD_WEAK_info) {
376 last_w = &(w->link);
377 } else {
378 last_w = &(w->link);
379 }
380 }
381 }
382 }
383