Strip parentheses in expressions contexts in error messages
[ghc.git] / rts / RetainerProfile.c
1 /* -----------------------------------------------------------------------------
2 *
3 * (c) The GHC Team, 2001
4 * Author: Sungwoo Park
5 *
6 * Retainer profiling.
7 *
8 * ---------------------------------------------------------------------------*/
9
10 #if defined(PROFILING)
11
12 #include "PosixSource.h"
13 #include "Rts.h"
14
15 #include "RetainerProfile.h"
16 #include "RetainerSet.h"
17 #include "TraverseHeap.h"
18 #include "Profiling.h"
19 #include "Stats.h"
20 #include "StablePtr.h" /* markStablePtrTable */
21 #include "StableName.h" /* rememberOldStableNameAddresses */
22 #include "sm/Storage.h"
23
24 /* Note [What is a retainer?]
25 ~~~~~~~~~~~~~~~~~~~~~~~~~~
26 Retainer profiling is a profiling technique that gives information why
27 objects can't be freed and lists the consumers that hold pointers to
28 the heap objects. It does not list all the objects that keep references
29 to the other, because then we would keep too much information that will
30 make the report unusable, for example the cons element of the list would keep
31 all the tail cells. As a result we are keeping only the objects of the
32 certain types, see 'isRetainer()' function for more discussion.
33
34 More formal definition of the retainer can be given the following way.
35
36 An object p is a retainer object of the object l, if all requirements
37 hold:
38
39 1. p can be a retainer (see `isRetainer()`)
40 2. l is reachable from p
41 3. There are no other retainers on the path from p to l.
42
43 Exact algorithm and additional information can be found the historical
44 document 'docs/storage-mgt/rp.tex'. Details that are related to the
45 RTS implementation may be out of date, but the general
46 information about the retainers is still applicable.
47 */
48
49
50 /*
51 Note: what to change in order to plug-in a new retainer profiling scheme?
52 (1) type retainer in ../includes/StgRetainerProf.h
53 (2) retainer function R(), i.e., getRetainerFrom()
54 (3) the two hashing functions, hashKeySingleton() and hashKeyAddElement(),
55 in RetainerSet.h, if needed.
56 (4) printRetainer() and printRetainerSetShort() in RetainerSet.c.
57 */
58
59 /* -----------------------------------------------------------------------------
60 * Declarations...
61 * -------------------------------------------------------------------------- */
62
63 static uint32_t retainerGeneration; // generation
64
65 static uint32_t numObjectVisited; // total number of objects visited
66 static uint32_t timesAnyObjectVisited; // number of times any objects are
67 // visited
68
69 /* -----------------------------------------------------------------------------
70 * Retainer stack - header
71 * Note:
72 * Although the retainer stack implementation could be separated *
73 * from the retainer profiling engine, there does not seem to be
74 * any advantage in doing that; retainer stack is an integral part
75 * of retainer profiling engine and cannot be use elsewhere at
76 * all.
77 * -------------------------------------------------------------------------- */
78
79 traverseState g_retainerTraverseState;
80
81 W_
82 retainerStackBlocks(void)
83 {
84 return traverseWorkStackBlocks(&g_retainerTraverseState);
85 }
86
87 /* -----------------------------------------------------------------------------
88 * RETAINER PROFILING ENGINE
89 * -------------------------------------------------------------------------- */
90
91 void
92 initRetainerProfiling( void )
93 {
94 initializeAllRetainerSet();
95 retainerGeneration = 0;
96 }
97
98 /* -----------------------------------------------------------------------------
99 * This function must be called before f-closing prof_file.
100 * -------------------------------------------------------------------------- */
101 void
102 endRetainerProfiling( void )
103 {
104 outputAllRetainerSet(prof_file);
105 }
106
107 /* -----------------------------------------------------------------------------
108 * Returns true if *c is a retainer.
109 * In general the retainers are the objects that may be the roots of the
110 * collection. Basically this roots represents programmers threads
111 * (TSO) with their stack and thunks.
112 *
113 * In addition we mark all mutable objects as a retainers, the reason for
114 * that decision is lost in time.
115 * -------------------------------------------------------------------------- */
116 STATIC_INLINE bool
117 isRetainer( const StgClosure *c )
118 {
119 switch (get_itbl(c)->type) {
120 //
121 // True case
122 //
123 // TSOs MUST be retainers: they constitute the set of roots.
124 case TSO:
125 case STACK:
126
127 // mutable objects
128 case MUT_PRIM:
129 case MVAR_CLEAN:
130 case MVAR_DIRTY:
131 case TVAR:
132 case MUT_VAR_CLEAN:
133 case MUT_VAR_DIRTY:
134 case MUT_ARR_PTRS_CLEAN:
135 case MUT_ARR_PTRS_DIRTY:
136 case SMALL_MUT_ARR_PTRS_CLEAN:
137 case SMALL_MUT_ARR_PTRS_DIRTY:
138 case BLOCKING_QUEUE:
139
140 // thunks are retainers.
141 case THUNK:
142 case THUNK_1_0:
143 case THUNK_0_1:
144 case THUNK_2_0:
145 case THUNK_1_1:
146 case THUNK_0_2:
147 case THUNK_SELECTOR:
148 case AP:
149 case AP_STACK:
150
151 // Static thunks, or CAFS, are obviously retainers.
152 case THUNK_STATIC:
153
154 // WEAK objects are roots; there is separate code in which traversing
155 // begins from WEAK objects.
156 case WEAK:
157 return true;
158
159 //
160 // False case
161 //
162
163 // constructors
164 case CONSTR:
165 case CONSTR_NOCAF:
166 case CONSTR_1_0:
167 case CONSTR_0_1:
168 case CONSTR_2_0:
169 case CONSTR_1_1:
170 case CONSTR_0_2:
171 // functions
172 case FUN:
173 case FUN_1_0:
174 case FUN_0_1:
175 case FUN_2_0:
176 case FUN_1_1:
177 case FUN_0_2:
178 // partial applications
179 case PAP:
180 // indirection
181 // IND_STATIC used to be an error, but at the moment it can happen
182 // as isAlive doesn't look through IND_STATIC as it ignores static
183 // closures. See trac #3956 for a program that hit this error.
184 case IND_STATIC:
185 case BLACKHOLE:
186 case WHITEHOLE:
187 // static objects
188 case FUN_STATIC:
189 // misc
190 case PRIM:
191 case BCO:
192 case ARR_WORDS:
193 case COMPACT_NFDATA:
194 // STM
195 case TREC_CHUNK:
196 // immutable arrays
197 case MUT_ARR_PTRS_FROZEN_CLEAN:
198 case MUT_ARR_PTRS_FROZEN_DIRTY:
199 case SMALL_MUT_ARR_PTRS_FROZEN_CLEAN:
200 case SMALL_MUT_ARR_PTRS_FROZEN_DIRTY:
201 return false;
202
203 //
204 // Error case
205 //
206 // Stack objects are invalid because they are never treated as
207 // legal objects during retainer profiling.
208 case UPDATE_FRAME:
209 case CATCH_FRAME:
210 case CATCH_RETRY_FRAME:
211 case CATCH_STM_FRAME:
212 case UNDERFLOW_FRAME:
213 case ATOMICALLY_FRAME:
214 case STOP_FRAME:
215 case RET_BCO:
216 case RET_SMALL:
217 case RET_BIG:
218 case RET_FUN:
219 // other cases
220 case IND:
221 case INVALID_OBJECT:
222 default:
223 barf("Invalid object in isRetainer(): %d", get_itbl(c)->type);
224 return false;
225 }
226 }
227
228 /* -----------------------------------------------------------------------------
229 * Returns the retainer function value for the closure *c, i.e., R(*c).
230 * This function does NOT return the retainer(s) of *c.
231 * Invariants:
232 * *c must be a retainer.
233 * -------------------------------------------------------------------------- */
234 STATIC_INLINE retainer
235 getRetainerFrom( StgClosure *c )
236 {
237 ASSERT(isRetainer(c));
238
239 return c->header.prof.ccs;
240 }
241
242 /* -----------------------------------------------------------------------------
243 * Associates the retainer set *s with the closure *c, that is, *s becomes
244 * the retainer set of *c.
245 * Invariants:
246 * c != NULL
247 * s != NULL
248 * -------------------------------------------------------------------------- */
249 STATIC_INLINE void
250 associate( StgClosure *c, RetainerSet *s )
251 {
252 // StgWord has the same size as pointers, so the following type
253 // casting is okay.
254 RSET(c) = (RetainerSet *)((StgWord)s | flip);
255 }
256
257 static bool
258 retainVisitClosure( StgClosure *c, const StgClosure *cp, const stackData data, const bool first_visit, stackData *out_data )
259 {
260 (void) first_visit;
261
262 retainer r = data.c_child_r;
263 RetainerSet *s, *retainerSetOfc;
264 retainerSetOfc = retainerSetOf(c);
265
266 timesAnyObjectVisited++;
267
268 // c = current closure under consideration,
269 // cp = current closure's parent,
270 // r = current closure's most recent retainer
271 //
272 // Loop invariants (on the meaning of c, cp, r, and their retainer sets):
273 // RSET(cp) and RSET(r) are valid.
274 // RSET(c) is valid only if c has been visited before.
275 //
276 // Loop invariants (on the relation between c, cp, and r)
277 // if cp is not a retainer, r belongs to RSET(cp).
278 // if cp is a retainer, r == cp.
279
280 // Now compute s:
281 // isRetainer(cp) == true => s == NULL
282 // isRetainer(cp) == false => s == cp.retainer
283 if (isRetainer(cp))
284 s = NULL;
285 else
286 s = retainerSetOf(cp);
287
288 // (c, cp, r, s) is available.
289
290 // (c, cp, r, s, R_r) is available, so compute the retainer set for *c.
291 if (retainerSetOfc == NULL) {
292 // This is the first visit to *c.
293 numObjectVisited++;
294
295 if (s == NULL)
296 associate(c, singleton(r));
297 else
298 // s is actually the retainer set of *c!
299 associate(c, s);
300
301 // compute c_child_r
302 out_data->c_child_r = isRetainer(c) ? getRetainerFrom(c) : r;
303 } else {
304 // This is not the first visit to *c.
305 if (isMember(r, retainerSetOfc))
306 return 0; // no need to process children
307
308 if (s == NULL)
309 associate(c, addElement(r, retainerSetOfc));
310 else {
311 // s is not NULL and cp is not a retainer. This means that
312 // each time *cp is visited, so is *c. Thus, if s has
313 // exactly one more element in its retainer set than c, s
314 // is also the new retainer set for *c.
315 if (s->num == retainerSetOfc->num + 1) {
316 associate(c, s);
317 }
318 // Otherwise, just add R_r to the current retainer set of *c.
319 else {
320 associate(c, addElement(r, retainerSetOfc));
321 }
322 }
323
324 if (isRetainer(c))
325 return 0; // no need to process children
326
327 // compute c_child_r
328 out_data->c_child_r = r;
329 }
330
331 // now, RSET() of all of *c, *cp, and *r is valid.
332 // (c, c_child_r) are available.
333
334 return 1; // do process children
335 }
336
337 /**
338 * Push every object reachable from *tl onto the traversal work stack.
339 */
340 static void
341 retainRoot(void *user, StgClosure **tl)
342 {
343 traverseState *ts = (traverseState*) user;
344 StgClosure *c;
345
346 // We no longer assume that only TSOs and WEAKs are roots; any closure can
347 // be a root.
348
349 c = UNTAG_CLOSURE(*tl);
350 traverseMaybeInitClosureData(c);
351 if (c != &stg_END_TSO_QUEUE_closure && isRetainer(c)) {
352 traversePushClosure(ts, c, c, (stackData)getRetainerFrom(c));
353 } else {
354 traversePushClosure(ts, c, c, (stackData)CCS_SYSTEM);
355 }
356
357 // NOT TRUE: ASSERT(isMember(getRetainerFrom(*tl), retainerSetOf(*tl)));
358 // *tl might be a TSO which is ThreadComplete, in which
359 // case we ignore it for the purposes of retainer profiling.
360 }
361
362 /* -----------------------------------------------------------------------------
363 * Compute the retainer set for each of the objects in the heap.
364 * -------------------------------------------------------------------------- */
365 static void
366 computeRetainerSet( traverseState *ts )
367 {
368 StgWeak *weak;
369 uint32_t g, n;
370
371 markCapabilities(retainRoot, (void*)ts); // for scheduler roots
372
373 // This function is called after a major GC, when key, value, and finalizer
374 // all are guaranteed to be valid, or reachable.
375 //
376 // The following code assumes that WEAK objects are considered to be roots
377 // for retainer profilng.
378 for (n = 0; n < n_capabilities; n++) {
379 // NB: after a GC, all nursery weak_ptr_lists have been migrated
380 // to the global lists living in the generations
381 ASSERT(capabilities[n]->weak_ptr_list_hd == NULL);
382 ASSERT(capabilities[n]->weak_ptr_list_tl == NULL);
383 }
384 for (g = 0; g < RtsFlags.GcFlags.generations; g++) {
385 for (weak = generations[g].weak_ptr_list; weak != NULL; weak = weak->link) {
386 // retainRoot((StgClosure *)weak);
387 retainRoot((void*)ts, (StgClosure **)&weak);
388 }
389 }
390
391 // Consider roots from the stable ptr table.
392 markStablePtrTable(retainRoot, (void*)ts);
393 // Remember old stable name addresses.
394 rememberOldStableNameAddresses ();
395
396 traverseWorkStack(ts, &retainVisitClosure);
397 }
398
399 /* -----------------------------------------------------------------------------
400 * Perform retainer profiling.
401 * N is the oldest generation being profilied, where the generations are
402 * numbered starting at 0.
403 * Invariants:
404 * Note:
405 * This function should be called only immediately after major garbage
406 * collection.
407 * ------------------------------------------------------------------------- */
408 void
409 retainerProfile(void)
410 {
411 stat_startRP();
412
413 numObjectVisited = 0;
414 timesAnyObjectVisited = 0;
415
416 /*
417 We initialize the traverse stack each time the retainer profiling is
418 performed (because the traverse stack size varies on each retainer profiling
419 and this operation is not costly anyhow). However, we just refresh the
420 retainer sets.
421 */
422 initializeTraverseStack(&g_retainerTraverseState);
423 initializeAllRetainerSet();
424 computeRetainerSet(&g_retainerTraverseState);
425
426 // post-processing
427 closeTraverseStack(&g_retainerTraverseState);
428 retainerGeneration++;
429
430 stat_endRP(
431 retainerGeneration - 1, // retainerGeneration has just been incremented!
432 getTraverseStackMaxSize(&g_retainerTraverseState),
433 (double)timesAnyObjectVisited / numObjectVisited);
434 }
435
436 #endif /* PROFILING */