rts/ProfHeap.c

   1 /* ----------------------------------------------------------------------------
   2  *
   3  * (c) The GHC Team, 1998-2003
   4  *
   5  * Support for heap profiling
   6  *
   7  * --------------------------------------------------------------------------*/
   8
   9 #include "PosixSource.h"
  10 #include "Rts.h"
  11 #include "RtsUtils.h"
  12 #include "RtsFlags.h"
  13 #include "Profiling.h"
  14 #include "ProfHeap.h"
  15 #include "Stats.h"
  16 #include "Hash.h"
  17 #include "RetainerProfile.h"
  18 #include "LdvProfile.h"
  19 #include "Arena.h"
  20 #include "Printer.h"
  21
  22 #include <string.h>
  23 #include <stdlib.h>
  24 #include <math.h>
  25
  26 /* -----------------------------------------------------------------------------
  27  * era stores the current time period.  It is the same as the
  28  * number of censuses that have been performed.
  29  *
  30  * RESTRICTION:
  31  *   era must be no longer than LDV_SHIFT (15 or 30) bits.
  32  * Invariants:
  33  *   era is initialized to 1 in initHeapProfiling().
  34  *
  35  * max_era is initialized to 2^LDV_SHIFT in initHeapProfiling().
  36  * When era reaches max_era, the profiling stops because a closure can
  37  * store only up to (max_era - 1) as its creation or last use time.
  38  * -------------------------------------------------------------------------- */
  39 unsigned int era;
  40 static nat max_era;
  41
  42 /* -----------------------------------------------------------------------------
  43  * Counters
  44  *
  45  * For most heap profiles each closure identity gets a simple count
  46  * of live words in the heap at each census.  However, if we're
  47  * selecting by biography, then we have to keep the various
  48  * lag/drag/void counters for each identity.
  49  * -------------------------------------------------------------------------- */
  50 typedef struct _counter {
  51     void *identity;
  52     union {
  53         nat resid;
  54         struct {
  55             int prim;     // total size of 'inherently used' closures
  56             int not_used; // total size of 'never used' closures
  57             int used;     // total size of 'used at least once' closures
  58             int void_total;  // current total size of 'destroyed without being used' closures
  59             int drag_total;  // current total size of 'used at least once and waiting to die'
  60         } ldv;
  61     } c;
  62     struct _counter *next;
  63 } counter;
  64
  65 STATIC_INLINE void
  66 initLDVCtr( counter *ctr )
  67 {
  68     ctr->c.ldv.prim = 0;
  69     ctr->c.ldv.not_used = 0;
  70     ctr->c.ldv.used = 0;
  71     ctr->c.ldv.void_total = 0;
  72     ctr->c.ldv.drag_total = 0;
  73 }
  74
  75 typedef struct {
  76     double      time;    // the time in MUT time when the census is made
  77     HashTable * hash;
  78     counter   * ctrs;
  79     Arena     * arena;
  80
  81     // for LDV profiling, when just displaying by LDV
  82     int       prim;
  83     int       not_used;
  84     int       used;
  85     int       void_total;
  86     int       drag_total;
  87 } Census;
  88
  89 static Census *censuses = NULL;
  90 static nat n_censuses = 0;
  91
  92 #ifdef PROFILING
  93 static void aggregateCensusInfo( void );
  94 #endif
  95
  96 static void dumpCensus( Census *census );
  97
  98 /* ----------------------------------------------------------------------------
  99    Closure Type Profiling;
 100    ------------------------------------------------------------------------- */
 101
 102 #ifndef PROFILING
 103 static char *type_names[] = {
 104     "INVALID_OBJECT",
 105     "CONSTR",
 106     "CONSTR_1_0",
 107     "CONSTR_0_1",
 108     "CONSTR_2_0",
 109     "CONSTR_1_1",
 110     "CONSTR_0_2",
 111     "CONSTR_STATIC",
 112     "CONSTR_NOCAF_STATIC",
 113     "FUN",
 114     "FUN_1_0",
 115     "FUN_0_1",
 116     "FUN_2_0",
 117     "FUN_1_1",
 118     "FUN_0_2",
 119     "FUN_STATIC",
 120     "THUNK",
 121     "THUNK_1_0",
 122     "THUNK_0_1",
 123     "THUNK_2_0",
 124     "THUNK_1_1",
 125     "THUNK_0_2",
 126     "THUNK_STATIC",
 127     "THUNK_SELECTOR",
 128     "BCO",
 129     "AP",
 130     "PAP",
 131     "AP_STACK",
 132     "IND",
 133     "IND_OLDGEN",
 134     "IND_PERM",
 135     "IND_OLDGEN_PERM",
 136     "IND_STATIC",
 137     "RET_BCO",
 138     "RET_SMALL",
 139     "RET_BIG",
 140     "RET_DYN",
 141     "RET_FUN",
 142     "UPDATE_FRAME",
 143     "CATCH_FRAME",
 144     "STOP_FRAME",
 145     "CAF_BLACKHOLE",
 146     "BLACKHOLE",
 147     "SE_BLACKHOLE",
 148     "SE_CAF_BLACKHOLE",
 149     "MVAR",
 150     "ARR_WORDS",
 151     "MUT_ARR_PTRS_CLEAN",
 152     "MUT_ARR_PTRS_DIRTY",
 153     "MUT_ARR_PTRS_FROZEN0",
 154     "MUT_ARR_PTRS_FROZEN",
 155     "MUT_VAR_CLEAN",
 156     "MUT_VAR_DIRTY",
 157     "WEAK",
 158     "STABLE_NAME",
 159     "TSO",
 160     "BLOCKED_FETCH",
 161     "FETCH_ME",
 162     "FETCH_ME_BQ",
 163     "RBH",
 164     "EVACUATED",
 165     "REMOTE_REF",
 166     "TVAR_WATCH_QUEUE",
 167     "INVARIANT_CHECK_QUEUE",
 168     "ATOMIC_INVARIANT",
 169     "TVAR",
 170     "TREC_CHUNK",
 171     "TREC_HEADER",
 172     "ATOMICALLY_FRAME",
 173     "CATCH_RETRY_FRAME",
 174     "CATCH_STM_FRAME",
 175     "N_CLOSURE_TYPES"
 176   };
 177 #endif
 178
 179 /* ----------------------------------------------------------------------------
 180  * Find the "closure identity", which is a unique pointer reresenting
 181  * the band to which this closure's heap space is attributed in the
 182  * heap profile.
 183  * ------------------------------------------------------------------------- */
 184 STATIC_INLINE void *
 185 closureIdentity( StgClosure *p )
 186 {
 187     switch (RtsFlags.ProfFlags.doHeapProfile) {
 188
 189 #ifdef PROFILING
 190     case HEAP_BY_CCS:
 191         return p->header.prof.ccs;
 192     case HEAP_BY_MOD:
 193         return p->header.prof.ccs->cc->module;
 194     case HEAP_BY_DESCR:
 195         return GET_PROF_DESC(get_itbl(p));
 196     case HEAP_BY_TYPE:
 197         return GET_PROF_TYPE(get_itbl(p));
 198     case HEAP_BY_RETAINER:
 199         // AFAIK, the only closures in the heap which might not have a
 200         // valid retainer set are DEAD_WEAK closures.
 201         if (isRetainerSetFieldValid(p))
 202             return retainerSetOf(p);
 203         else
 204             return NULL;
 205
 206 #else
 207     case HEAP_BY_CLOSURE_TYPE:
 208     {
 209         StgInfoTable *info;
 210         info = get_itbl(p);
 211         switch (info->type) {
 212         case CONSTR:
 213         case CONSTR_1_0:
 214         case CONSTR_0_1:
 215         case CONSTR_2_0:
 216         case CONSTR_1_1:
 217         case CONSTR_0_2:
 218         case CONSTR_STATIC:
 219         case CONSTR_NOCAF_STATIC:
 220             return GET_CON_DESC(itbl_to_con_itbl(info));
 221         default:
 222             return type_names[info->type];
 223         }
 224     }
 225
 226 #endif
 227     default:
 228         barf("closureIdentity");
 229     }
 230 }
 231
 232 /* --------------------------------------------------------------------------
 233  * Profiling type predicates
 234  * ----------------------------------------------------------------------- */
 235 #ifdef PROFILING
 236 STATIC_INLINE rtsBool
 237 doingLDVProfiling( void )
 238 {
 239     return (RtsFlags.ProfFlags.doHeapProfile == HEAP_BY_LDV
 240             || RtsFlags.ProfFlags.bioSelector != NULL);
 241 }
 242
 243 STATIC_INLINE rtsBool
 244 doingRetainerProfiling( void )
 245 {
 246     return (RtsFlags.ProfFlags.doHeapProfile == HEAP_BY_RETAINER
 247             || RtsFlags.ProfFlags.retainerSelector != NULL);
 248 }
 249 #endif /* PROFILING */
 250
 251 // Precesses a closure 'c' being destroyed whose size is 'size'.
 252 // Make sure that LDV_recordDead() is not invoked on 'inherently used' closures
 253 // such as TSO; they should not be involved in computing dragNew or voidNew.
 254 //
 255 // Even though era is checked in both LdvCensusForDead() and
 256 // LdvCensusKillAll(), we still need to make sure that era is > 0 because
 257 // LDV_recordDead() may be called from elsewhere in the runtime system. E.g.,
 258 // when a thunk is replaced by an indirection object.
 259
 260 #ifdef PROFILING
 261 void
 262 LDV_recordDead( StgClosure *c, nat size )
 263 {
 264     void *id;
 265     nat t;
 266     counter *ctr;
 267
 268     if (era > 0 && closureSatisfiesConstraints(c)) {
 269         size -= sizeofW(StgProfHeader);
 270         ASSERT(LDVW(c) != 0);
 271         if ((LDVW((c)) & LDV_STATE_MASK) == LDV_STATE_CREATE) {
 272             t = (LDVW((c)) & LDV_CREATE_MASK) >> LDV_SHIFT;
 273             if (t < era) {
 274                 if (RtsFlags.ProfFlags.bioSelector == NULL) {
 275                     censuses[t].void_total   += (int)size;
 276                     censuses[era].void_total -= (int)size;
 277                     ASSERT(censuses[t].void_total < censuses[t].not_used);
 278                 } else {
 279                     id = closureIdentity(c);
 280                     ctr = lookupHashTable(censuses[t].hash, (StgWord)id);
 281                     ASSERT( ctr != NULL );
 282                     ctr->c.ldv.void_total += (int)size;
 283                     ctr = lookupHashTable(censuses[era].hash, (StgWord)id);
 284                     if (ctr == NULL) {
 285                         ctr = arenaAlloc(censuses[era].arena, sizeof(counter));
 286                         initLDVCtr(ctr);
 287                         insertHashTable(censuses[era].hash, (StgWord)id, ctr);
 288                         ctr->identity = id;
 289                         ctr->next = censuses[era].ctrs;
 290                         censuses[era].ctrs = ctr;
 291                     }
 292                     ctr->c.ldv.void_total -= (int)size;
 293                 }
 294             }
 295         } else {
 296             t = LDVW((c)) & LDV_LAST_MASK;
 297             if (t + 1 < era) {
 298                 if (RtsFlags.ProfFlags.bioSelector == NULL) {
 299                     censuses[t+1].drag_total += size;
 300                     censuses[era].drag_total -= size;
 301                 } else {
 302                     void *id;
 303                     id = closureIdentity(c);
 304                     ctr = lookupHashTable(censuses[t+1].hash, (StgWord)id);
 305                     ASSERT( ctr != NULL );
 306                     ctr->c.ldv.drag_total += (int)size;
 307                     ctr = lookupHashTable(censuses[era].hash, (StgWord)id);
 308                     if (ctr == NULL) {
 309                         ctr = arenaAlloc(censuses[era].arena, sizeof(counter));
 310                         initLDVCtr(ctr);
 311                         insertHashTable(censuses[era].hash, (StgWord)id, ctr);
 312                         ctr->identity = id;
 313                         ctr->next = censuses[era].ctrs;
 314                         censuses[era].ctrs = ctr;
 315                     }
 316                     ctr->c.ldv.drag_total -= (int)size;
 317                 }
 318             }
 319         }
 320     }
 321 }
 322 #endif
 323
 324 /* --------------------------------------------------------------------------
 325  * Initialize censuses[era];
 326  * ----------------------------------------------------------------------- */
 327
 328 STATIC_INLINE void
 329 initEra(Census *census)
 330 {
 331     census->hash  = allocHashTable();
 332     census->ctrs  = NULL;
 333     census->arena = newArena();
 334
 335     census->not_used   = 0;
 336     census->used       = 0;
 337     census->prim       = 0;
 338     census->void_total = 0;
 339     census->drag_total = 0;
 340 }
 341
 342 STATIC_INLINE void
 343 freeEra(Census *census)
 344 {
 345     if (RtsFlags.ProfFlags.bioSelector != NULL)
 346         // when bioSelector==NULL, these are freed in heapCensus()
 347     {
 348         arenaFree(census->arena);
 349         freeHashTable(census->hash, NULL);
 350     }
 351 }
 352
 353 /* --------------------------------------------------------------------------
 354  * Increases era by 1 and initialize census[era].
 355  * Reallocates gi[] and increases its size if needed.
 356  * ----------------------------------------------------------------------- */
 357
 358 static void
 359 nextEra( void )
 360 {
 361 #ifdef PROFILING
 362     if (doingLDVProfiling()) {
 363         era++;
 364
 365         if (era == max_era) {
 366             errorBelch("maximum number of censuses reached; use +RTS -i to reduce");
 367             stg_exit(EXIT_FAILURE);
 368         }
 369
 370         if (era == n_censuses) {
 371             n_censuses *= 2;
 372             censuses = stgReallocBytes(censuses, sizeof(Census) * n_censuses,
 373                                        "nextEra");
 374         }
 375     }
 376 #endif /* PROFILING */
 377
 378     initEra( &censuses[era] );
 379 }
 380
 381 /* ----------------------------------------------------------------------------
 382  * Heap profiling by info table
 383  * ------------------------------------------------------------------------- */
 384
 385 #if !defined(PROFILING)
 386 FILE *hp_file;
 387 static char *hp_filename;
 388
 389 void initProfiling1 (void)
 390 {
 391 }
 392
 393 void freeProfiling1 (void)
 394 {
 395 }
 396
 397 void initProfiling2 (void)
 398 {
 399   if (RtsFlags.ProfFlags.doHeapProfile) {
 400     /* Initialise the log file name */
 401     hp_filename = stgMallocBytes(strlen(prog_name) + 6, "hpFileName");
 402     sprintf(hp_filename, "%s.hp", prog_name);
 403
 404     /* open the log file */
 405     if ((hp_file = fopen(hp_filename, "w")) == NULL) {
 406       debugBelch("Can't open profiling report file %s\n",
 407               hp_filename);
 408       RtsFlags.ProfFlags.doHeapProfile = 0;
 409       return;
 410     }
 411   }
 412
 413   initHeapProfiling();
 414 }
 415
 416 void endProfiling( void )
 417 {
 418   endHeapProfiling();
 419 }
 420 #endif /* !PROFILING */
 421
 422 static void
 423 printSample(rtsBool beginSample, StgDouble sampleValue)
 424 {
 425     StgDouble fractionalPart, integralPart;
 426     fractionalPart = modf(sampleValue, &integralPart);
 427     fprintf(hp_file, "%s %" FMT_Word64 ".%02" FMT_Word64 "\n",
 428             (beginSample ? "BEGIN_SAMPLE" : "END_SAMPLE"),
 429             (StgWord64)integralPart, (StgWord64)(fractionalPart * 100));
 430 }
 431
 432 /* --------------------------------------------------------------------------
 433  * Initialize the heap profilier
 434  * ----------------------------------------------------------------------- */
 435 nat
 436 initHeapProfiling(void)
 437 {
 438     if (! RtsFlags.ProfFlags.doHeapProfile) {
 439         return 0;
 440     }
 441
 442 #ifdef PROFILING
 443     if (doingLDVProfiling() && doingRetainerProfiling()) {
 444         errorBelch("cannot mix -hb and -hr");
 445         stg_exit(EXIT_FAILURE);
 446     }
 447 #endif
 448
 449     // we only count eras if we're doing LDV profiling.  Otherwise era
 450     // is fixed at zero.
 451 #ifdef PROFILING
 452     if (doingLDVProfiling()) {
 453         era = 1;
 454     } else
 455 #endif
 456     {
 457         era = 0;
 458     }
 459
 460     {   // max_era = 2^LDV_SHIFT
 461         nat p;
 462         max_era = 1;
 463         for (p = 0; p < LDV_SHIFT; p++)
 464             max_era *= 2;
 465     }
 466
 467     n_censuses = 32;
 468     censuses = stgMallocBytes(sizeof(Census) * n_censuses, "initHeapProfiling");
 469
 470     initEra( &censuses[era] );
 471
 472     /* initProfilingLogFile(); */
 473     fprintf(hp_file, "JOB \"%s", prog_name);
 474
 475 #ifdef PROFILING
 476     {
 477         int count;
 478         for(count = 1; count < prog_argc; count++)
 479             fprintf(hp_file, " %s", prog_argv[count]);
 480         fprintf(hp_file, " +RTS");
 481         for(count = 0; count < rts_argc; count++)
 482             fprintf(hp_file, " %s", rts_argv[count]);
 483     }
 484 #endif /* PROFILING */
 485
 486     fprintf(hp_file, "\"\n" );
 487
 488     fprintf(hp_file, "DATE \"%s\"\n", time_str());
 489
 490     fprintf(hp_file, "SAMPLE_UNIT \"seconds\"\n");
 491     fprintf(hp_file, "VALUE_UNIT \"bytes\"\n");
 492
 493     printSample(rtsTrue, 0);
 494     printSample(rtsFalse, 0);
 495
 496 #ifdef PROFILING
 497     if (doingRetainerProfiling()) {
 498         initRetainerProfiling();
 499     }
 500 #endif
 501
 502     return 0;
 503 }
 504
 505 void
 506 endHeapProfiling(void)
 507 {
 508     StgDouble seconds;
 509
 510     if (! RtsFlags.ProfFlags.doHeapProfile) {
 511         return;
 512     }
 513
 514 #ifdef PROFILING
 515     if (doingRetainerProfiling()) {
 516         endRetainerProfiling();
 517     }
 518 #endif
 519
 520 #ifdef PROFILING
 521     if (doingLDVProfiling()) {
 522         nat t;
 523         LdvCensusKillAll();
 524         aggregateCensusInfo();
 525         for (t = 1; t < era; t++) {
 526             dumpCensus( &censuses[t] );
 527         }
 528     }
 529 #endif
 530
 531 #ifdef PROFILING
 532     if (doingLDVProfiling()) {
 533         nat t;
 534         for (t = 1; t <= era; t++) {
 535             freeEra( &censuses[t] );
 536         }
 537     } else {
 538         freeEra( &censuses[0] );
 539     }
 540 #else
 541     freeEra( &censuses[0] );
 542 #endif
 543
 544     stgFree(censuses);
 545
 546     seconds = mut_user_time();
 547     printSample(rtsTrue, seconds);
 548     printSample(rtsFalse, seconds);
 549     fclose(hp_file);
 550 }
 551
 552
 553
 554 #ifdef PROFILING
 555 static size_t
 556 buf_append(char *p, const char *q, char *end)
 557 {
 558     int m;
 559
 560     for (m = 0; p < end; p++, q++, m++) {
 561         *p = *q;
 562         if (*q == '\0') { break; }
 563     }
 564     return m;
 565 }
 566
 567 static void
 568 fprint_ccs(FILE *fp, CostCentreStack *ccs, nat max_length)
 569 {
 570     char buf[max_length+1], *p, *buf_end;
 571
 572     // MAIN on its own gets printed as "MAIN", otherwise we ignore MAIN.
 573     if (ccs == CCS_MAIN) {
 574         fprintf(fp, "MAIN");
 575         return;
 576     }
 577
 578     fprintf(fp, "(%ld)", ccs->ccsID);
 579
 580     p = buf;
 581     buf_end = buf + max_length + 1;
 582
 583     // keep printing components of the stack until we run out of space
 584     // in the buffer.  If we run out of space, end with "...".
 585     for (; ccs != NULL && ccs != CCS_MAIN; ccs = ccs->prevStack) {
 586
 587         // CAF cost centres print as M.CAF, but we leave the module
 588         // name out of all the others to save space.
 589         if (!strcmp(ccs->cc->label,"CAF")) {
 590             p += buf_append(p, ccs->cc->module, buf_end);
 591             p += buf_append(p, ".CAF", buf_end);
 592         } else {
 593             p += buf_append(p, ccs->cc->label, buf_end);
 594             if (ccs->prevStack != NULL && ccs->prevStack != CCS_MAIN) {
 595                 p += buf_append(p, "/", buf_end);
 596             }
 597         }
 598
 599         if (p >= buf_end) {
 600             sprintf(buf+max_length-4, "...");
 601             break;
 602         }
 603     }
 604     fprintf(fp, "%s", buf);
 605 }
 606 #endif /* PROFILING */
 607
 608 rtsBool
 609 strMatchesSelector( char* str, char* sel )
 610 {
 611    char* p;
 612    // debugBelch("str_matches_selector %s %s\n", str, sel);
 613    while (1) {
 614        // Compare str against wherever we've got to in sel.
 615        p = str;
 616        while (*p != '\0' && *sel != ',' && *sel != '\0' && *p == *sel) {
 617            p++; sel++;
 618        }
 619        // Match if all of str used and have reached the end of a sel fragment.
 620        if (*p == '\0' && (*sel == ',' || *sel == '\0'))
 621            return rtsTrue;
 622
 623        // No match.  Advance sel to the start of the next elem.
 624        while (*sel != ',' && *sel != '\0') sel++;
 625        if (*sel == ',') sel++;
 626
 627        /* Run out of sel ?? */
 628        if (*sel == '\0') return rtsFalse;
 629    }
 630 }
 631
 632 /* -----------------------------------------------------------------------------
 633  * Figure out whether a closure should be counted in this census, by
 634  * testing against all the specified constraints.
 635  * -------------------------------------------------------------------------- */
 636 rtsBool
 637 closureSatisfiesConstraints( StgClosure* p )
 638 {
 639 #if !defined(PROFILING)
 640     (void)p;   /* keep gcc -Wall happy */
 641     return rtsTrue;
 642 #else
 643    rtsBool b;
 644
 645    // The CCS has a selected field to indicate whether this closure is
 646    // deselected by not being mentioned in the module, CC, or CCS
 647    // selectors.
 648    if (!p->header.prof.ccs->selected) {
 649        return rtsFalse;
 650    }
 651
 652    if (RtsFlags.ProfFlags.descrSelector) {
 653        b = strMatchesSelector( (GET_PROF_DESC(get_itbl((StgClosure *)p))),
 654                                  RtsFlags.ProfFlags.descrSelector );
 655        if (!b) return rtsFalse;
 656    }
 657    if (RtsFlags.ProfFlags.typeSelector) {
 658        b = strMatchesSelector( (GET_PROF_TYPE(get_itbl((StgClosure *)p))),
 659                                 RtsFlags.ProfFlags.typeSelector );
 660        if (!b) return rtsFalse;
 661    }
 662    if (RtsFlags.ProfFlags.retainerSelector) {
 663        RetainerSet *rs;
 664        nat i;
 665        // We must check that the retainer set is valid here.  One
 666        // reason it might not be valid is if this closure is a
 667        // a newly deceased weak pointer (i.e. a DEAD_WEAK), since
 668        // these aren't reached by the retainer profiler's traversal.
 669        if (isRetainerSetFieldValid((StgClosure *)p)) {
 670            rs = retainerSetOf((StgClosure *)p);
 671            if (rs != NULL) {
 672                for (i = 0; i < rs->num; i++) {
 673                    b = strMatchesSelector( rs->element[i]->cc->label,
 674                                            RtsFlags.ProfFlags.retainerSelector );
 675                    if (b) return rtsTrue;
 676                }
 677            }
 678        }
 679        return rtsFalse;
 680    }
 681    return rtsTrue;
 682 #endif /* PROFILING */
 683 }
 684
 685 /* -----------------------------------------------------------------------------
 686  * Aggregate the heap census info for biographical profiling
 687  * -------------------------------------------------------------------------- */
 688 #ifdef PROFILING
 689 static void
 690 aggregateCensusInfo( void )
 691 {
 692     HashTable *acc;
 693     nat t;
 694     counter *c, *d, *ctrs;
 695     Arena *arena;
 696
 697     if (!doingLDVProfiling()) return;
 698
 699     // Aggregate the LDV counters when displaying by biography.
 700     if (RtsFlags.ProfFlags.doHeapProfile == HEAP_BY_LDV) {
 701         int void_total, drag_total;
 702
 703         // Now we compute void_total and drag_total for each census
 704         // After the program has finished, the void_total field of
 705         // each census contains the count of words that were *created*
 706         // in this era and were eventually void.  Conversely, if a
 707         // void closure was destroyed in this era, it will be
 708         // represented by a negative count of words in void_total.
 709         //
 710         // To get the count of live words that are void at each
 711         // census, just propagate the void_total count forwards:
 712
 713         void_total = 0;
 714         drag_total = 0;
 715         for (t = 1; t < era; t++) { // note: start at 1, not 0
 716             void_total += censuses[t].void_total;
 717             drag_total += censuses[t].drag_total;
 718             censuses[t].void_total = void_total;
 719             censuses[t].drag_total = drag_total;
 720
 721             ASSERT( censuses[t].void_total <= censuses[t].not_used );
 722             // should be true because: void_total is the count of
 723             // live words that are void at this census, which *must*
 724             // be less than the number of live words that have not
 725             // been used yet.
 726
 727             ASSERT( censuses[t].drag_total <= censuses[t].used );
 728             // similar reasoning as above.
 729         }
 730
 731         return;
 732     }
 733
 734     // otherwise... we're doing a heap profile that is restricted to
 735     // some combination of lag, drag, void or use.  We've kept all the
 736     // census info for all censuses so far, but we still need to
 737     // aggregate the counters forwards.
 738
 739     arena = newArena();
 740     acc = allocHashTable();
 741     ctrs = NULL;
 742
 743     for (t = 1; t < era; t++) {
 744
 745         // first look through all the counters we're aggregating
 746         for (c = ctrs; c != NULL; c = c->next) {
 747             // if one of the totals is non-zero, then this closure
 748             // type must be present in the heap at this census time...
 749             d = lookupHashTable(censuses[t].hash, (StgWord)c->identity);
 750
 751             if (d == NULL) {
 752                 // if this closure identity isn't present in the
 753                 // census for this time period, then our running
 754                 // totals *must* be zero.
 755                 ASSERT(c->c.ldv.void_total == 0 && c->c.ldv.drag_total == 0);
 756
 757                 // debugCCS(c->identity);
 758                 // debugBelch(" census=%d void_total=%d drag_total=%d\n",
 759                 //         t, c->c.ldv.void_total, c->c.ldv.drag_total);
 760             } else {
 761                 d->c.ldv.void_total += c->c.ldv.void_total;
 762                 d->c.ldv.drag_total += c->c.ldv.drag_total;
 763                 c->c.ldv.void_total =  d->c.ldv.void_total;
 764                 c->c.ldv.drag_total =  d->c.ldv.drag_total;
 765
 766                 ASSERT( c->c.ldv.void_total >= 0 );
 767                 ASSERT( c->c.ldv.drag_total >= 0 );
 768             }
 769         }
 770
 771         // now look through the counters in this census to find new ones
 772         for (c = censuses[t].ctrs; c != NULL; c = c->next) {
 773             d = lookupHashTable(acc, (StgWord)c->identity);
 774             if (d == NULL) {
 775                 d = arenaAlloc( arena, sizeof(counter) );
 776                 initLDVCtr(d);
 777                 insertHashTable( acc, (StgWord)c->identity, d );
 778                 d->identity = c->identity;
 779                 d->next = ctrs;
 780                 ctrs = d;
 781                 d->c.ldv.void_total = c->c.ldv.void_total;
 782                 d->c.ldv.drag_total = c->c.ldv.drag_total;
 783             }
 784             ASSERT( c->c.ldv.void_total >= 0 );
 785             ASSERT( c->c.ldv.drag_total >= 0 );
 786         }
 787     }
 788
 789     freeHashTable(acc, NULL);
 790     arenaFree(arena);
 791 }
 792 #endif
 793
 794 /* -----------------------------------------------------------------------------
 795  * Print out the results of a heap census.
 796  * -------------------------------------------------------------------------- */
 797 static void
 798 dumpCensus( Census *census )
 799 {
 800     counter *ctr;
 801     int count;
 802
 803     printSample(rtsTrue, census->time);
 804
 805 #ifdef PROFILING
 806     if (RtsFlags.ProfFlags.doHeapProfile == HEAP_BY_LDV) {
 807       fprintf(hp_file, "VOID\t%lu\n", (unsigned long)(census->void_total) * sizeof(W_));
 808         fprintf(hp_file, "LAG\t%lu\n",
 809                 (unsigned long)(census->not_used - census->void_total) * sizeof(W_));
 810         fprintf(hp_file, "USE\t%lu\n",
 811                 (unsigned long)(census->used - census->drag_total) * sizeof(W_));
 812         fprintf(hp_file, "INHERENT_USE\t%lu\n",
 813                 (unsigned long)(census->prim) * sizeof(W_));
 814         fprintf(hp_file, "DRAG\t%lu\n",
 815                 (unsigned long)(census->drag_total) * sizeof(W_));
 816         printSample(rtsFalse, census->time);
 817         return;
 818     }
 819 #endif
 820
 821     for (ctr = census->ctrs; ctr != NULL; ctr = ctr->next) {
 822
 823 #ifdef PROFILING
 824         if (RtsFlags.ProfFlags.bioSelector != NULL) {
 825             count = 0;
 826             if (strMatchesSelector("lag", RtsFlags.ProfFlags.bioSelector))
 827                 count += ctr->c.ldv.not_used - ctr->c.ldv.void_total;
 828             if (strMatchesSelector("drag", RtsFlags.ProfFlags.bioSelector))
 829                 count += ctr->c.ldv.drag_total;
 830             if (strMatchesSelector("void", RtsFlags.ProfFlags.bioSelector))
 831                 count += ctr->c.ldv.void_total;
 832             if (strMatchesSelector("use", RtsFlags.ProfFlags.bioSelector))
 833                 count += ctr->c.ldv.used - ctr->c.ldv.drag_total;
 834         } else
 835 #endif
 836         {
 837             count = ctr->c.resid;
 838         }
 839
 840         ASSERT( count >= 0 );
 841
 842         if (count == 0) continue;
 843
 844 #if !defined(PROFILING)
 845         switch (RtsFlags.ProfFlags.doHeapProfile) {
 846         case HEAP_BY_CLOSURE_TYPE:
 847             fprintf(hp_file, "%s", (char *)ctr->identity);
 848             break;
 849         }
 850 #endif
 851
 852 #ifdef PROFILING
 853         switch (RtsFlags.ProfFlags.doHeapProfile) {
 854         case HEAP_BY_CCS:
 855             fprint_ccs(hp_file, (CostCentreStack *)ctr->identity, RtsFlags.ProfFlags.ccsLength);
 856             break;
 857         case HEAP_BY_MOD:
 858         case HEAP_BY_DESCR:
 859         case HEAP_BY_TYPE:
 860             fprintf(hp_file, "%s", (char *)ctr->identity);
 861             break;
 862         case HEAP_BY_RETAINER:
 863         {
 864             RetainerSet *rs = (RetainerSet *)ctr->identity;
 865
 866             // it might be the distinguished retainer set rs_MANY:
 867             if (rs == &rs_MANY) {
 868                 fprintf(hp_file, "MANY");
 869                 break;
 870             }
 871
 872             // Mark this retainer set by negating its id, because it
 873             // has appeared in at least one census.  We print the
 874             // values of all such retainer sets into the log file at
 875             // the end.  A retainer set may exist but not feature in
 876             // any censuses if it arose as the intermediate retainer
 877             // set for some closure during retainer set calculation.
 878             if (rs->id > 0)
 879                 rs->id = -(rs->id);
 880
 881             // report in the unit of bytes: * sizeof(StgWord)
 882             printRetainerSetShort(hp_file, rs);
 883             break;
 884         }
 885         default:
 886             barf("dumpCensus; doHeapProfile");
 887         }
 888 #endif
 889
 890         fprintf(hp_file, "\t%lu\n", (unsigned long)count * sizeof(W_));
 891     }
 892
 893     printSample(rtsFalse, census->time);
 894 }
 895
 896 /* -----------------------------------------------------------------------------
 897  * Code to perform a heap census.
 898  * -------------------------------------------------------------------------- */
 899 static void
 900 heapCensusChain( Census *census, bdescr *bd )
 901 {
 902     StgPtr p;
 903     StgInfoTable *info;
 904     void *identity;
 905     nat size;
 906     counter *ctr;
 907     nat real_size;
 908     rtsBool prim;
 909
 910     for (; bd != NULL; bd = bd->link) {
 911
 912         // HACK: ignore pinned blocks, because they contain gaps.
 913         // It's not clear exactly what we'd like to do here, since we
 914         // can't tell which objects in the block are actually alive.
 915         // Perhaps the whole block should be counted as SYSTEM memory.
 916         if (bd->flags & BF_PINNED) {
 917             continue;
 918         }
 919
 920         p = bd->start;
 921         while (p < bd->free) {
 922             info = get_itbl((StgClosure *)p);
 923             prim = rtsFalse;
 924
 925             switch (info->type) {
 926
 927             case THUNK:
 928                 size = thunk_sizeW_fromITBL(info);
 929                 break;
 930
 931             case THUNK_1_1:
 932             case THUNK_0_2:
 933             case THUNK_2_0:
 934                 size = sizeofW(StgThunkHeader) + 2;
 935                 break;
 936
 937             case THUNK_1_0:
 938             case THUNK_0_1:
 939             case THUNK_SELECTOR:
 940                 size = sizeofW(StgThunkHeader) + 1;
 941                 break;
 942
 943             case CONSTR:
 944             case FUN:
 945             case IND_PERM:
 946             case IND_OLDGEN:
 947             case IND_OLDGEN_PERM:
 948             case CAF_BLACKHOLE:
 949             case SE_CAF_BLACKHOLE:
 950             case SE_BLACKHOLE:
 951             case BLACKHOLE:
 952             case FUN_1_0:
 953             case FUN_0_1:
 954             case FUN_1_1:
 955             case FUN_0_2:
 956             case FUN_2_0:
 957             case CONSTR_1_0:
 958             case CONSTR_0_1:
 959             case CONSTR_1_1:
 960             case CONSTR_0_2:
 961             case CONSTR_2_0:
 962                 size = sizeW_fromITBL(info);
 963                 break;
 964
 965             case IND:
 966                 // Special case/Delicate Hack: INDs don't normally
 967                 // appear, since we're doing this heap census right
 968                 // after GC.  However, GarbageCollect() also does
 969                 // resurrectThreads(), which can update some
 970                 // blackholes when it calls raiseAsync() on the
 971                 // resurrected threads.  So we know that any IND will
 972                 // be the size of a BLACKHOLE.
 973                 size = BLACKHOLE_sizeW();
 974                 break;
 975
 976             case BCO:
 977                 prim = rtsTrue;
 978                 size = bco_sizeW((StgBCO *)p);
 979                 break;
 980
 981             case MVAR:
 982             case WEAK:
 983             case STABLE_NAME:
 984             case MUT_VAR_CLEAN:
 985             case MUT_VAR_DIRTY:
 986                 prim = rtsTrue;
 987                 size = sizeW_fromITBL(info);
 988                 break;
 989
 990             case AP:
 991                 size = ap_sizeW((StgAP *)p);
 992                 break;
 993
 994             case PAP:
 995                 size = pap_sizeW((StgPAP *)p);
 996                 break;
 997
 998             case AP_STACK:
 999                 size = ap_stack_sizeW((StgAP_STACK *)p);
1000                 break;
1001
1002             case ARR_WORDS:
1003                 prim = rtsTrue;
1004                 size = arr_words_sizeW(stgCast(StgArrWords*,p));
1005                 break;
1006
1007             case MUT_ARR_PTRS_CLEAN:
1008             case MUT_ARR_PTRS_DIRTY:
1009             case MUT_ARR_PTRS_FROZEN:
1010             case MUT_ARR_PTRS_FROZEN0:
1011                 prim = rtsTrue;
1012                 size = mut_arr_ptrs_sizeW((StgMutArrPtrs *)p);
1013                 break;
1014
1015             case TSO:
1016                 prim = rtsTrue;
1017 #ifdef PROFILING
1018                 if (RtsFlags.ProfFlags.includeTSOs) {
1019                     size = tso_sizeW((StgTSO *)p);
1020                     break;
1021                 } else {
1022                     // Skip this TSO and move on to the next object
1023                     p += tso_sizeW((StgTSO *)p);
1024                     continue;
1025                 }
1026 #else
1027                 size = tso_sizeW((StgTSO *)p);
1028                 break;
1029 #endif
1030
1031             case TREC_HEADER:
1032                 prim = rtsTrue;
1033                 size = sizeofW(StgTRecHeader);
1034                 break;
1035
1036             case TVAR_WATCH_QUEUE:
1037                 prim = rtsTrue;
1038                 size = sizeofW(StgTVarWatchQueue);
1039                 break;
1040
1041             case INVARIANT_CHECK_QUEUE:
1042                 prim = rtsTrue;
1043                 size = sizeofW(StgInvariantCheckQueue);
1044                 break;
1045
1046             case ATOMIC_INVARIANT:
1047                 prim = rtsTrue;
1048                 size = sizeofW(StgAtomicInvariant);
1049                 break;
1050
1051             case TVAR:
1052                 prim = rtsTrue;
1053                 size = sizeofW(StgTVar);
1054                 break;
1055
1056             case TREC_CHUNK:
1057                 prim = rtsTrue;
1058                 size = sizeofW(StgTRecChunk);
1059                 break;
1060
1061             default:
1062                 barf("heapCensus, unknown object: %d", info->type);
1063             }
1064
1065             identity = NULL;
1066
1067 #ifdef PROFILING
1068             // subtract the profiling overhead
1069             real_size = size - sizeofW(StgProfHeader);
1070 #else
1071             real_size = size;
1072 #endif
1073
1074             if (closureSatisfiesConstraints((StgClosure*)p)) {
1075 #ifdef PROFILING
1076                 if (RtsFlags.ProfFlags.doHeapProfile == HEAP_BY_LDV) {
1077                     if (prim)
1078                         census->prim += real_size;
1079                     else if ((LDVW(p) & LDV_STATE_MASK) == LDV_STATE_CREATE)
1080                         census->not_used += real_size;
1081                     else
1082                         census->used += real_size;
1083                 } else
1084 #endif
1085                 {
1086                     identity = closureIdentity((StgClosure *)p);
1087
1088                     if (identity != NULL) {
1089                         ctr = lookupHashTable( census->hash, (StgWord)identity );
1090                         if (ctr != NULL) {
1091 #ifdef PROFILING
1092                             if (RtsFlags.ProfFlags.bioSelector != NULL) {
1093                                 if (prim)
1094                                     ctr->c.ldv.prim += real_size;
1095                                 else if ((LDVW(p) & LDV_STATE_MASK) == LDV_STATE_CREATE)
1096                                     ctr->c.ldv.not_used += real_size;
1097                                 else
1098                                     ctr->c.ldv.used += real_size;
1099                             } else
1100 #endif
1101                             {
1102                                 ctr->c.resid += real_size;
1103                             }
1104                         } else {
1105                             ctr = arenaAlloc( census->arena, sizeof(counter) );
1106                             initLDVCtr(ctr);
1107                             insertHashTable( census->hash, (StgWord)identity, ctr );
1108                             ctr->identity = identity;
1109                             ctr->next = census->ctrs;
1110                             census->ctrs = ctr;
1111
1112 #ifdef PROFILING
1113                             if (RtsFlags.ProfFlags.bioSelector != NULL) {
1114                                 if (prim)
1115                                     ctr->c.ldv.prim = real_size;
1116                                 else if ((LDVW(p) & LDV_STATE_MASK) == LDV_STATE_CREATE)
1117                                     ctr->c.ldv.not_used = real_size;
1118                                 else
1119                                     ctr->c.ldv.used = real_size;
1120                             } else
1121 #endif
1122                             {
1123                                 ctr->c.resid = real_size;
1124                             }
1125                         }
1126                     }
1127                 }
1128             }
1129
1130             p += size;
1131         }
1132     }
1133 }
1134
1135 void
1136 heapCensus( void )
1137 {
1138   nat g, s;
1139   Census *census;
1140
1141   census = &censuses[era];
1142   census->time  = mut_user_time();
1143
1144   // calculate retainer sets if necessary
1145 #ifdef PROFILING
1146   if (doingRetainerProfiling()) {
1147       retainerProfile();
1148   }
1149 #endif
1150
1151 #ifdef PROFILING
1152   stat_startHeapCensus();
1153 #endif
1154
1155   // Traverse the heap, collecting the census info
1156
1157   // First the small_alloc_list: we have to fix the free pointer at
1158   // the end by calling tidyAllocatedLists() first.
1159   tidyAllocateLists();
1160   heapCensusChain( census, small_alloc_list );
1161
1162   // Now traverse the heap in each generation/step.
1163   if (RtsFlags.GcFlags.generations == 1) {
1164       heapCensusChain( census, g0s0->blocks );
1165   } else {
1166       for (g = 0; g < RtsFlags.GcFlags.generations; g++) {
1167           for (s = 0; s < generations[g].n_steps; s++) {
1168               heapCensusChain( census, generations[g].steps[s].blocks );
1169               // Are we interested in large objects?  might be
1170               // confusing to include the stack in a heap profile.
1171               heapCensusChain( census, generations[g].steps[s].large_objects );
1172           }
1173       }
1174   }
1175
1176   // dump out the census info
1177 #ifdef PROFILING
1178     // We can't generate any info for LDV profiling until
1179     // the end of the run...
1180     if (!doingLDVProfiling())
1181         dumpCensus( census );
1182 #else
1183     dumpCensus( census );
1184 #endif
1185
1186
1187   // free our storage, unless we're keeping all the census info for
1188   // future restriction by biography.
1189 #ifdef PROFILING
1190   if (RtsFlags.ProfFlags.bioSelector == NULL)
1191   {
1192       freeHashTable( census->hash, NULL/* don't free the elements */ );
1193       arenaFree( census->arena );
1194       census->hash = NULL;
1195       census->arena = NULL;
1196   }
1197 #endif
1198
1199   // we're into the next time period now
1200   nextEra();
1201
1202 #ifdef PROFILING
1203   stat_endHeapCensus();
1204 #endif
1205 }
1206