RetainerProfile.c 13.5 KB
Newer Older
1 2 3 4 5 6 7 8 9
/* -----------------------------------------------------------------------------
 *
 * (c) The GHC Team, 2001
 * Author: Sungwoo Park
 *
 * Retainer profiling.
 *
 * ---------------------------------------------------------------------------*/

10
#if defined(PROFILING)
11

12
#include "PosixSource.h"
13
#include "Rts.h"
14

15 16
#include "RetainerProfile.h"
#include "RetainerSet.h"
17
#include "TraverseHeap.h"
18 19
#include "Profiling.h"
#include "Stats.h"
David Feuer's avatar
David Feuer committed
20 21
#include "StablePtr.h" /* markStablePtrTable */
#include "StableName.h" /* rememberOldStableNameAddresses */
22
#include "sm/Storage.h"
23

24 25
/* Note [What is a retainer?]
   ~~~~~~~~~~~~~~~~~~~~~~~~~~
26 27
Retainer profiling is a profiling technique that gives information why
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
to the other, because then we would keep too much information that will
make the report unusable, for example the cons element of the list would keep
all the tail cells. As a result we are keeping only the objects of the
certain types, see 'isRetainer()' function for more discussion.

More formal definition of the retainer can be given the following way.

An object p is a retainer object of the object l, if all requirements
hold:

  1. p can be a retainer (see `isRetainer()`)
  2. l is reachable from p
  3. There are no other retainers on the path from p to l.

Exact algorithm and additional information can be found the historical
document 'docs/storage-mgt/rp.tex'. Details that are related to the
RTS implementation may be out of date, but the general
information about the retainers is still applicable.
47 48 49
*/


50 51 52 53 54 55 56 57 58 59 60 61 62
/*
  Note: what to change in order to plug-in a new retainer profiling scheme?
    (1) type retainer in ../includes/StgRetainerProf.h
    (2) retainer function R(), i.e., getRetainerFrom()
    (3) the two hashing functions, hashKeySingleton() and hashKeyAddElement(),
        in RetainerSet.h, if needed.
    (4) printRetainer() and printRetainerSetShort() in RetainerSet.c.
 */

/* -----------------------------------------------------------------------------
 * Declarations...
 * -------------------------------------------------------------------------- */

63
static uint32_t retainerGeneration;  // generation
64

65 66 67
static uint32_t numObjectVisited;    // total number of objects visited
static uint32_t timesAnyObjectVisited;  // number of times any objects are
                                        // visited
68 69 70 71 72 73 74 75 76 77 78

/* -----------------------------------------------------------------------------
 * Retainer stack - header
 *   Note:
 *     Although the retainer stack implementation could be separated *
 *     from the retainer profiling engine, there does not seem to be
 *     any advantage in doing that; retainer stack is an integral part
 *     of retainer profiling engine and cannot be use elsewhere at
 *     all.
 * -------------------------------------------------------------------------- */

79 80
traverseState g_retainerTraverseState;

81 82 83 84 85 86
W_
retainerStackBlocks(void)
{
    return traverseWorkStackBlocks(&g_retainerTraverseState);
}

87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
/* -----------------------------------------------------------------------------
 * RETAINER PROFILING ENGINE
 * -------------------------------------------------------------------------- */

void
initRetainerProfiling( void )
{
    initializeAllRetainerSet();
    retainerGeneration = 0;
}

/* -----------------------------------------------------------------------------
 *  This function must be called before f-closing prof_file.
 * -------------------------------------------------------------------------- */
void
endRetainerProfiling( void )
{
    outputAllRetainerSet(prof_file);
}

/* -----------------------------------------------------------------------------
Ben Gamari's avatar
Ben Gamari committed
108
 * Returns true if *c is a retainer.
109 110 111 112 113 114
 * In general the retainers are the objects that may be the roots of the
 * collection. Basically this roots represents programmers threads
 * (TSO) with their stack and thunks.
 *
 * In addition we mark all mutable objects as a retainers, the reason for
 * 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 122 123
        //
        //  True case
        //
        // 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 130
    case MVAR_CLEAN:
    case MVAR_DIRTY:
131
    case TVAR:
132 133
    case MUT_VAR_CLEAN:
    case MUT_VAR_DIRTY:
134 135
    case MUT_ARR_PTRS_CLEAN:
    case MUT_ARR_PTRS_DIRTY:
136 137 138
    case SMALL_MUT_ARR_PTRS_CLEAN:
    case SMALL_MUT_ARR_PTRS_DIRTY:
    case BLOCKING_QUEUE:
139

140
        // thunks are retainers.
141 142 143 144 145 146 147
    case THUNK:
    case THUNK_1_0:
    case THUNK_0_1:
    case THUNK_2_0:
    case THUNK_1_1:
    case THUNK_0_2:
    case THUNK_SELECTOR:
148 149
    case AP:
    case AP_STACK:
150

151
        // Static thunks, or CAFS, are obviously retainers.
152 153
    case THUNK_STATIC:

154 155
        // WEAK objects are roots; there is separate code in which traversing
        // begins from WEAK objects.
156
    case WEAK:
Ben Gamari's avatar
Ben Gamari committed
157
        return true;
158

159 160 161
        //
        // False case
        //
162

163
        // constructors
164
    case CONSTR:
Simon Marlow's avatar
Simon Marlow committed
165
    case CONSTR_NOCAF:
166 167 168 169 170
    case CONSTR_1_0:
    case CONSTR_0_1:
    case CONSTR_2_0:
    case CONSTR_1_1:
    case CONSTR_0_2:
171
        // functions
172 173 174 175 176 177
    case FUN:
    case FUN_1_0:
    case FUN_0_1:
    case FUN_2_0:
    case FUN_1_1:
    case FUN_0_2:
178
        // partial applications
179
    case PAP:
180
        // indirection
181 182 183 184
    // IND_STATIC used to be an error, but at the moment it can happen
    // as isAlive doesn't look through IND_STATIC as it ignores static
    // closures. See trac #3956 for a program that hit this error.
    case IND_STATIC:
185
    case BLACKHOLE:
186
    case WHITEHOLE:
187
        // static objects
188
    case FUN_STATIC:
189
        // misc
190
    case PRIM:
191 192
    case BCO:
    case ARR_WORDS:
193
    case COMPACT_NFDATA:
194
        // STM
195
    case TREC_CHUNK:
196
        // immutable arrays
197 198 199 200
    case MUT_ARR_PTRS_FROZEN_CLEAN:
    case MUT_ARR_PTRS_FROZEN_DIRTY:
    case SMALL_MUT_ARR_PTRS_FROZEN_CLEAN:
    case SMALL_MUT_ARR_PTRS_FROZEN_DIRTY:
Ben Gamari's avatar
Ben Gamari committed
201
        return false;
202

203 204 205 206 207
        //
        // Error case
        //
        // Stack objects are invalid because they are never treated as
        // legal objects during retainer profiling.
208 209
    case UPDATE_FRAME:
    case CATCH_FRAME:
210 211
    case CATCH_RETRY_FRAME:
    case CATCH_STM_FRAME:
212
    case UNDERFLOW_FRAME:
213
    case ATOMICALLY_FRAME:
214 215 216 217
    case STOP_FRAME:
    case RET_BCO:
    case RET_SMALL:
    case RET_BIG:
218
    case RET_FUN:
219
        // other cases
220 221 222
    case IND:
    case INVALID_OBJECT:
    default:
223
        barf("Invalid object in isRetainer(): %d", get_itbl(c)->type);
Ben Gamari's avatar
Ben Gamari committed
224
        return false;
225 226 227 228 229 230 231 232 233
    }
}

/* -----------------------------------------------------------------------------
 *  Returns the retainer function value for the closure *c, i.e., R(*c).
 *  This function does NOT return the retainer(s) of *c.
 *  Invariants:
 *    *c must be a retainer.
 * -------------------------------------------------------------------------- */
234
STATIC_INLINE retainer
235 236 237 238 239 240 241 242 243 244 245 246 247 248
getRetainerFrom( StgClosure *c )
{
    ASSERT(isRetainer(c));

    return c->header.prof.ccs;
}

/* -----------------------------------------------------------------------------
 *  Associates the retainer set *s with the closure *c, that is, *s becomes
 *  the retainer set of *c.
 *  Invariants:
 *    c != NULL
 *    s != NULL
 * -------------------------------------------------------------------------- */
249
STATIC_INLINE void
250
associate( StgClosure *c, RetainerSet *s )
251 252 253 254 255 256
{
    // StgWord has the same size as pointers, so the following type
    // casting is okay.
    RSET(c) = (RetainerSet *)((StgWord)s | flip);
}

257
static bool
258
retainVisitClosure( StgClosure *c, const StgClosure *cp, const stackData data, const bool first_visit, stackData *out_data )
259
{
260 261
    (void) first_visit;

262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305
    retainer r = data.c_child_r;
    RetainerSet *s, *retainerSetOfc;
    retainerSetOfc = retainerSetOf(c);

    timesAnyObjectVisited++;

    // c  = current closure under consideration,
    // cp = current closure's parent,
    // r  = current closure's most recent retainer
    //
    // Loop invariants (on the meaning of c, cp, r, and their retainer sets):
    //   RSET(cp) and RSET(r) are valid.
    //   RSET(c) is valid only if c has been visited before.
    //
    // Loop invariants (on the relation between c, cp, and r)
    //   if cp is not a retainer, r belongs to RSET(cp).
    //   if cp is a retainer, r == cp.

    // Now compute s:
    //    isRetainer(cp) == true => s == NULL
    //    isRetainer(cp) == false => s == cp.retainer
    if (isRetainer(cp))
        s = NULL;
    else
        s = retainerSetOf(cp);

    // (c, cp, r, s) is available.

    // (c, cp, r, s, R_r) is available, so compute the retainer set for *c.
    if (retainerSetOfc == NULL) {
        // This is the first visit to *c.
        numObjectVisited++;

        if (s == NULL)
            associate(c, singleton(r));
        else
            // s is actually the retainer set of *c!
            associate(c, s);

        // compute c_child_r
        out_data->c_child_r = isRetainer(c) ? getRetainerFrom(c) : r;
    } else {
        // This is not the first visit to *c.
        if (isMember(r, retainerSetOfc))
306
            return 0;          // no need to process children
307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324

        if (s == NULL)
            associate(c, addElement(r, retainerSetOfc));
        else {
            // s is not NULL and cp is not a retainer. This means that
            // each time *cp is visited, so is *c. Thus, if s has
            // exactly one more element in its retainer set than c, s
            // is also the new retainer set for *c.
            if (s->num == retainerSetOfc->num + 1) {
                associate(c, s);
            }
            // Otherwise, just add R_r to the current retainer set of *c.
            else {
                associate(c, addElement(r, retainerSetOfc));
            }
        }

        if (isRetainer(c))
325
            return 0;          // no need to process children
326 327 328 329 330 331 332 333

        // compute c_child_r
        out_data->c_child_r = r;
    }

    // now, RSET() of all of *c, *cp, and *r is valid.
    // (c, c_child_r) are available.

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;
Simon Marlow's avatar
Simon Marlow committed
344 345
    StgClosure *c;

346 347 348
    // We no longer assume that only TSOs and WEAKs are roots; any closure can
    // be a root.

Simon Marlow's avatar
Simon Marlow committed
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 358 359 360 361 362 363 364 365

    // NOT TRUE: ASSERT(isMember(getRetainerFrom(*tl), retainerSetOf(*tl)));
    // *tl might be a TSO which is ThreadComplete, in which
    // case we ignore it for the purposes of retainer profiling.
}

/* -----------------------------------------------------------------------------
 *  Compute the retainer set for each of the objects in the heap.
 * -------------------------------------------------------------------------- */
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 374 375 376 377

    // This function is called after a major GC, when key, value, and finalizer
    // all are guaranteed to be valid, or reachable.
    //
    // The following code assumes that WEAK objects are considered to be roots
    // for retainer profilng.
378 379 380 381 382 383
    for (n = 0; n < n_capabilities; n++) {
        // NB: after a GC, all nursery weak_ptr_lists have been migrated
        // to the global lists living in the generations
        ASSERT(capabilities[n]->weak_ptr_list_hd == NULL);
        ASSERT(capabilities[n]->weak_ptr_list_tl == NULL);
    }
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);
David Feuer's avatar
David Feuer committed
393 394
    // Remember old stable name addresses.
    rememberOldStableNameAddresses ();
395

396
    traverseWorkStack(ts, &retainVisitClosure);
397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421
}

/* -----------------------------------------------------------------------------
 * Perform retainer profiling.
 * N is the oldest generation being profilied, where the generations are
 * numbered starting at 0.
 * Invariants:
 * Note:
 *   This function should be called only immediately after major garbage
 *   collection.
 * ------------------------------------------------------------------------- */
void
retainerProfile(void)
{
  stat_startRP();

  numObjectVisited = 0;
  timesAnyObjectVisited = 0;

  /*
    We initialize the traverse stack each time the retainer profiling is
    performed (because the traverse stack size varies on each retainer profiling
    and this operation is not costly anyhow). However, we just refresh the
    retainer sets.
   */
422
  initializeTraverseStack(&g_retainerTraverseState);
423
  initializeAllRetainerSet();
424
  computeRetainerSet(&g_retainerTraverseState);
425 426

  // post-processing
427
  closeTraverseStack(&g_retainerTraverseState);
428 429 430 431
  retainerGeneration++;

  stat_endRP(
    retainerGeneration - 1,   // retainerGeneration has just been incremented!
432
    getTraverseStackMaxSize(&g_retainerTraverseState),
433
    (double)timesAnyObjectVisited / numObjectVisited);
434 435 436
}

#endif /* PROFILING */