GC.c 57.9 KB
Newer Older
1 2
/* -----------------------------------------------------------------------------
 *
3
 * (c) The GHC Team 1998-2008
4 5 6
 *
 * Generational garbage collector
 *
7 8
 * Documentation on the architecture of the Garbage Collector can be
 * found in the online commentary:
thoughtpolice's avatar
thoughtpolice committed
9
 *
10
 *   http://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/GC
11
 *
12 13
 * ---------------------------------------------------------------------------*/

Simon Marlow's avatar
Simon Marlow committed
14
#include "PosixSource.h"
15
#include "Rts.h"
Simon Marlow's avatar
Simon Marlow committed
16 17
#include "HsFFI.h"

18 19 20 21 22 23 24 25 26 27 28 29 30
#include "GC.h"
#include "GCThread.h"
#include "GCTDecl.h"            // NB. before RtsSignals.h which
                                // clobbers REG_R1 on arm/Linux
#include "Compact.h"
#include "Evac.h"
#include "Scav.h"
#include "GCUtils.h"
#include "MarkStack.h"
#include "MarkWeak.h"
#include "Sparks.h"
#include "Sweep.h"

31
#include "Arena.h"
Simon Marlow's avatar
Simon Marlow committed
32
#include "Storage.h"
33 34 35 36 37 38 39 40 41 42 43 44 45 46
#include "RtsUtils.h"
#include "Apply.h"
#include "Updates.h"
#include "Stats.h"
#include "Schedule.h"
#include "Sanity.h"
#include "BlockAlloc.h"
#include "ProfHeap.h"
#include "Weak.h"
#include "Prelude.h"
#include "RtsSignals.h"
#include "STM.h"
#include "Trace.h"
#include "RetainerProfile.h"
Simon Marlow's avatar
Simon Marlow committed
47
#include "LdvProfile.h"
48
#include "RaiseAsync.h"
Simon Marlow's avatar
Simon Marlow committed
49
#include "Stable.h"
50
#include "CheckUnload.h"
gcampax's avatar
gcampax committed
51
#include "CNF.h"
Simon Marlow's avatar
Simon Marlow committed
52
#include "RtsFlags.h"
53

54 55 56 57
#if defined(PROFILING)
#include "RetainerProfile.h"
#endif

58
#include <string.h> // for memset()
59
#include <unistd.h>
60

61 62 63 64
/* -----------------------------------------------------------------------------
   Global variables
   -------------------------------------------------------------------------- */

65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
/* STATIC OBJECT LIST.
 *
 * During GC:
 * We maintain a linked list of static objects that are still live.
 * The requirements for this list are:
 *
 *  - we need to scan the list while adding to it, in order to
 *    scavenge all the static objects (in the same way that
 *    breadth-first scavenging works for dynamic objects).
 *
 *  - we need to be able to tell whether an object is already on
 *    the list, to break loops.
 *
 * Each static object has a "static link field", which we use for
 * linking objects on to the list.  We use a stack-type list, consing
 * objects on the front as they are added (this means that the
 * scavenge phase is depth-first, not breadth-first, but that
thoughtpolice's avatar
thoughtpolice committed
82
 * shouldn't matter).
83 84 85 86 87
 *
 * A separate list is kept for objects that have been scavenged
 * already - this is so that we can zero all the marks afterwards.
 *
 * An object is on the list if its static link field is non-zero; this
thoughtpolice's avatar
thoughtpolice committed
88
 * means that we have to mark the end of the list with '1', not NULL.
89 90 91 92 93 94 95 96 97
 *
 * Extra notes for generational GC:
 *
 * Each generation has a static object list associated with it.  When
 * collecting generations up to N, we treat the static object lists
 * from generations > N as roots.
 *
 * We build up a static object list while collecting generations 0..N,
 * which is then appended to the static object list of generation N+1.
Ben Gamari's avatar
Ben Gamari committed
98 99
 *
 * See also: Note [STATIC_LINK fields] in Storage.h.
100 101 102 103 104 105 106
 */

/* N is the oldest generation being collected, where the generations
 * are numbered starting at 0.  A major GC (indicated by the major_gc
 * flag) is when we're collecting all generations.  We only attempt to
 * deal with static objects and GC CAFs when doing a major GC.
 */
107
uint32_t N;
Ben Gamari's avatar
Ben Gamari committed
108
bool major_gc;
109 110 111

/* Data used for allocation area sizing.
 */
thoughtpolice's avatar
thoughtpolice committed
112
static W_ g0_pcnt_kept = 30; // percentage of g0 live at last minor GC
113 114

/* Mut-list stats */
Ben Gamari's avatar
Ben Gamari committed
115
#if defined(DEBUG)
116
uint32_t mutlist_MUTVARS,
117
    mutlist_MUTARRS,
118
    mutlist_MVARS,
119 120 121 122
    mutlist_TVAR,
    mutlist_TVAR_WATCH_QUEUE,
    mutlist_TREC_CHUNK,
    mutlist_TREC_HEADER,
123 124 125
    mutlist_OTHERS;
#endif

126 127
/* Thread-local data for each GC thread
 */
128
gc_thread **gc_threads = NULL;
129 130

#if !defined(THREADED_RTS)
131
StgWord8 the_gc_thread[sizeof(gc_thread) + 64 * sizeof(gen_workspace)];
132
#endif
133

134 135
// Number of threads running in *this* GC.  Affects how many
// step->todos[] lists we have to look in to find work.
136
uint32_t n_gc_threads;
137

138
// For stats:
139
static long copied;        // *words* copied & scavenged during this GC
140

Douglas Wilson's avatar
Douglas Wilson committed
141
#if defined(PROF_SPIN) && defined(THREADED_RTS)
142 143 144
// spin and yield counts for the quasi-SpinLock in waitForGcThreads
volatile StgWord64 waitForGcThreads_spin = 0;
volatile StgWord64 waitForGcThreads_yield = 0;
Douglas Wilson's avatar
Douglas Wilson committed
145 146 147
volatile StgWord64 whitehole_gc_spin = 0;
#endif

Ben Gamari's avatar
Ben Gamari committed
148
bool work_stealing;
149

150 151
uint32_t static_flag = STATIC_FLAG_B;
uint32_t prev_static_flag = STATIC_FLAG_A;
152

153 154
DECLARE_GCT

155 156 157 158
/* -----------------------------------------------------------------------------
   Static function declarations
   -------------------------------------------------------------------------- */

159
static void mark_root               (void *user, StgClosure **root);
Simon Marlow's avatar
Simon Marlow committed
160 161
static void prepare_collected_gen   (generation *gen);
static void prepare_uncollected_gen (generation *gen);
162 163 164
static void init_gc_thread          (gc_thread *t);
static void resize_generations      (void);
static void resize_nursery          (void);
Simon Marlow's avatar
Simon Marlow committed
165
static void start_gc_threads        (void);
166
static void scavenge_until_all_done (void);
167 168
static StgWord inc_running          (void);
static StgWord dec_running          (void);
Ben Gamari's avatar
Ben Gamari committed
169 170
static void wakeup_gc_threads       (uint32_t me, bool idle_cap[]);
static void shutdown_gc_threads     (uint32_t me, bool idle_cap[]);
Simon Marlow's avatar
Simon Marlow committed
171
static void collect_gct_blocks      (void);
172
static void collect_pinned_object_blocks (void);
173
static void heapOverflow            (void);
174

175
#if defined(DEBUG)
176
static void gcCAFs                  (void);
177 178 179
#endif

/* -----------------------------------------------------------------------------
180
   The mark stack.
181 182
   -------------------------------------------------------------------------- */

183 184 185
bdescr *mark_stack_top_bd; // topmost block in the mark stack
bdescr *mark_stack_bd;     // current block in the mark stack
StgPtr mark_sp;            // pointer to the next unallocated mark stack entry
186 187

/* -----------------------------------------------------------------------------
188
   GarbageCollect: the main entry point to the garbage collector.
189

Simon Marlow's avatar
tidy up  
Simon Marlow committed
190 191
   The collect_gen parameter is gotten by calling calcNeeded().

192 193 194 195
   Locks held: all capabilities are held throughout GarbageCollect().
   -------------------------------------------------------------------------- */

void
196
GarbageCollect (uint32_t collect_gen,
Ben Gamari's avatar
Ben Gamari committed
197
                bool do_heap_census,
198
                uint32_t gc_type USED_IF_THREADS,
199
                Capability *cap,
Ben Gamari's avatar
Ben Gamari committed
200
                bool idle_cap[])
201 202
{
  bdescr *bd;
Simon Marlow's avatar
Simon Marlow committed
203
  generation *gen;
204 205 206
  StgWord live_blocks, live_words, par_max_copied, par_balanced_copied,
      gc_spin_spin, gc_spin_yield, mut_spin_spin, mut_spin_yield,
      any_work, no_work, scav_find_work;
Ian Lynagh's avatar
Ian Lynagh committed
207
#if defined(THREADED_RTS)
208
  gc_thread *saved_gct;
Ian Lynagh's avatar
Ian Lynagh committed
209
#endif
210
  uint32_t g, n;
211

212
  // necessary if we stole a callee-saves register for gct:
Ian Lynagh's avatar
Ian Lynagh committed
213
#if defined(THREADED_RTS)
214
  saved_gct = gct;
Ian Lynagh's avatar
Ian Lynagh committed
215
#endif
216

Ben Gamari's avatar
Ben Gamari committed
217
#if defined(PROFILING)
218
  CostCentreStack *save_CCS[n_capabilities];
219 220
#endif

221 222
  ACQUIRE_SM_LOCK;

223
#if defined(RTS_USER_SIGNALS)
224 225 226 227
  if (RtsFlags.MiscFlags.install_signal_handlers) {
    // block signals
    blockUserSignals();
  }
228 229
#endif

Simon Marlow's avatar
Simon Marlow committed
230 231
  ASSERT(sizeof(gen_workspace) == 16 * sizeof(StgWord));
  // otherwise adjust the padding in gen_workspace.
232

Simon Marlow's avatar
Simon Marlow committed
233 234
  // this is the main thread
  SET_GCT(gc_threads[cap->no]);
235

thoughtpolice's avatar
thoughtpolice committed
236
  // tell the stats department that we've started a GC
237
  stat_startGC(cap, gct);
simonmar@microsoft.com's avatar
simonmar@microsoft.com committed
238

239
  // lock the StablePtr table
240
  stableLock();
241

Ben Gamari's avatar
Ben Gamari committed
242
#if defined(DEBUG)
243 244
  mutlist_MUTVARS = 0;
  mutlist_MUTARRS = 0;
245 246 247 248 249
  mutlist_MVARS = 0;
  mutlist_TVAR = 0;
  mutlist_TVAR_WATCH_QUEUE = 0;
  mutlist_TREC_CHUNK = 0;
  mutlist_TREC_HEADER = 0;
250 251 252
  mutlist_OTHERS = 0;
#endif

thoughtpolice's avatar
thoughtpolice committed
253
  // attribute any costs to CCS_GC
Ben Gamari's avatar
Ben Gamari committed
254
#if defined(PROFILING)
255
  for (n = 0; n < n_capabilities; n++) {
256 257
      save_CCS[n] = capabilities[n]->r.rCCCS;
      capabilities[n]->r.rCCCS = CCS_GC;
258
  }
259 260 261 262
#endif

  /* Figure out which generation to collect
   */
Simon Marlow's avatar
tidy up  
Simon Marlow committed
263
  N = collect_gen;
264
  major_gc = (N == RtsFlags.GcFlags.generations-1);
265

266 267 268 269 270 271
  if (major_gc) {
      prev_static_flag = static_flag;
      static_flag =
          static_flag == STATIC_FLAG_A ? STATIC_FLAG_B : STATIC_FLAG_A;
  }

272
#if defined(THREADED_RTS)
273 274
  work_stealing = RtsFlags.ParFlags.parGcLoadBalancingEnabled &&
                  N >= RtsFlags.ParFlags.parGcLoadBalancingGen;
275 276 277
      // It's not always a good idea to do load balancing in parallel
      // GC.  In particular, for a parallel program we don't want to
      // lose locality by moving cached data into another CPU's cache
thoughtpolice's avatar
thoughtpolice committed
278
      // (this effect can be quite significant).
279 280 281 282 283 284 285
      //
      // We could have a more complex way to deterimine whether to do
      // work stealing or not, e.g. it might be a good idea to do it
      // if the heap is big.  For now, we just turn it on or off with
      // a flag.
#endif

Simon Marlow's avatar
Simon Marlow committed
286 287 288 289
  /* Start threads, so they can be spinning up while we finish initialisation.
   */
  start_gc_threads();

290
#if defined(THREADED_RTS)
291
  /* How many threads will be participating in this GC?
292 293
   * We don't try to parallelise minor GCs (unless the user asks for
   * it with +RTS -gn0), or mark/compact/sweep GC.
294
   */
295
  if (gc_type == SYNC_GC_PAR) {
296
      n_gc_threads = n_capabilities;
297
  } else {
298
      n_gc_threads = 1;
299
  }
300
#else
301
  n_gc_threads = 1;
302
#endif
303

304 305
  debugTrace(DEBUG_gc, "GC (gen %d, using %d thread(s))",
             N, n_gc_threads);
306

Ben Gamari's avatar
Ben Gamari committed
307
#if defined(DEBUG)
thoughtpolice's avatar
thoughtpolice committed
308
  // check for memory leaks if DEBUG is on
309
  memInventory(DEBUG_gc);
310 311
#endif

312 313 314
  // do this *before* we start scavenging
  collectFreshWeakPtrs();

315
  // check sanity *before* GC
Ben Gamari's avatar
Ben Gamari committed
316
  IF_DEBUG(sanity, checkSanity(false /* before GC */, major_gc));
317

318 319
  // gather blocks allocated using allocatePinned() from each capability
  // and put them on the g0->large_object list.
320
  collect_pinned_object_blocks();
321

Simon Marlow's avatar
Simon Marlow committed
322
  // Initialise all the generations that we're collecting.
323
  for (g = 0; g <= N; g++) {
Simon Marlow's avatar
Simon Marlow committed
324
      prepare_collected_gen(&generations[g]);
325
  }
Simon Marlow's avatar
Simon Marlow committed
326
  // Initialise all the generations that we're *not* collecting.
327
  for (g = N+1; g < RtsFlags.GcFlags.generations; g++) {
Simon Marlow's avatar
Simon Marlow committed
328
      prepare_uncollected_gen(&generations[g]);
329 330
  }

Simon Marlow's avatar
Simon Marlow committed
331 332 333
  // Prepare this gc_thread
  init_gc_thread(gct);

334 335
  /* Allocate a mark stack if we're doing a major collection.
   */
Simon Marlow's avatar
Simon Marlow committed
336
  if (major_gc && oldest_gen->mark) {
337 338 339 340 341
      mark_stack_bd     = allocBlock();
      mark_stack_top_bd = mark_stack_bd;
      mark_stack_bd->link = NULL;
      mark_stack_bd->u.back = NULL;
      mark_sp           = mark_stack_bd->start;
342
  } else {
343 344 345
      mark_stack_bd     = NULL;
      mark_stack_top_bd = NULL;
      mark_sp           = NULL;
346 347 348 349 350
  }

  /* -----------------------------------------------------------------------
   * follow all the roots that we know about:
   */
351 352 353 354 355 356

  // the main thread is running: this prevents any other threads from
  // exiting prematurely, so we can start them now.
  // NB. do this after the mutable lists have been saved above, otherwise
  // the other GC threads will be writing into the old mutable lists.
  inc_running();
357
  wakeup_gc_threads(gct->thread_index, idle_cap);
Simon Marlow's avatar
Simon Marlow committed
358 359

  traceEventGcWork(gct->cap);
360

361 362 363 364 365 366
  // scavenge the capability-private mutable lists.  This isn't part
  // of markSomeCapabilities() because markSomeCapabilities() can only
  // call back into the GC via mark_root() (due to the gct register
  // variable).
  if (n_gc_threads == 1) {
      for (n = 0; n < n_capabilities; n++) {
Simon Marlow's avatar
Simon Marlow committed
367
#if defined(THREADED_RTS)
368
          scavenge_capability_mut_Lists1(capabilities[n]);
Simon Marlow's avatar
Simon Marlow committed
369
#else
370
          scavenge_capability_mut_lists(capabilities[n]);
Simon Marlow's avatar
Simon Marlow committed
371
#endif
372 373
      }
  } else {
Simon Marlow's avatar
Simon Marlow committed
374
      scavenge_capability_mut_lists(gct->cap);
375
      for (n = 0; n < n_capabilities; n++) {
376
          if (idle_cap[n]) {
377
              markCapability(mark_root, gct, capabilities[n],
Ben Gamari's avatar
Ben Gamari committed
378
                             true/*don't mark sparks*/);
379
              scavenge_capability_mut_lists(capabilities[n]);
380 381
          }
      }
382 383
  }

384
  // follow roots from the CAF list (used by GHCi)
Simon Marlow's avatar
Simon Marlow committed
385
  gct->evac_gen_no = 0;
386
  markCAFs(mark_root, gct);
387

388
  // follow all the roots that the application knows about.
Simon Marlow's avatar
Simon Marlow committed
389
  gct->evac_gen_no = 0;
Simon Marlow's avatar
Simon Marlow committed
390 391
  if (n_gc_threads == 1) {
      for (n = 0; n < n_capabilities; n++) {
392
          markCapability(mark_root, gct, capabilities[n],
Ben Gamari's avatar
Ben Gamari committed
393
                         true/*don't mark sparks*/);
Simon Marlow's avatar
Simon Marlow committed
394 395
      }
  } else {
Ben Gamari's avatar
Ben Gamari committed
396
      markCapability(mark_root, gct, cap, true/*don't mark sparks*/);
Simon Marlow's avatar
Simon Marlow committed
397 398 399
  }

  markScheduler(mark_root, gct);
400

401
  // Mark the weak pointer list, and prepare to detect dead weak pointers.
402 403 404
  markWeakPtrList();
  initWeakForGC();

405
  // Mark the stable pointer table.
406
  markStableTables(mark_root, gct);
407 408 409 410 411

  /* -------------------------------------------------------------------------
   * Repeatedly scavenge all the areas we know about until there's no
   * more scavenging to be done.
   */
Simon Marlow's avatar
Simon Marlow committed
412 413
  for (;;)
  {
414
      scavenge_until_all_done();
Simon Marlow's avatar
Simon Marlow committed
415 416
      // The other threads are now stopped.  We might recurse back to
      // here, but from now on this is the only thread.
thoughtpolice's avatar
thoughtpolice committed
417

Simon Marlow's avatar
Simon Marlow committed
418 419
      // must be last...  invariant is that everything is fully
      // scavenged at this point.
Ben Gamari's avatar
Ben Gamari committed
420
      if (traverseWeakPtrList()) { // returns true if evaced something
Austin Seipp's avatar
Austin Seipp committed
421 422
          inc_running();
          continue;
Simon Marlow's avatar
Simon Marlow committed
423
      }
424

Simon Marlow's avatar
Simon Marlow committed
425 426
      // If we get to here, there's really nothing left to do.
      break;
427 428
  }

429
  shutdown_gc_threads(gct->thread_index, idle_cap);
430

431
  // Now see which stable names are still alive.
432
  gcStableTables();
433

Ben Gamari's avatar
Ben Gamari committed
434
#if defined(THREADED_RTS)
435 436
  if (n_gc_threads == 1) {
      for (n = 0; n < n_capabilities; n++) {
437
          pruneSparkQueue(capabilities[n]);
438 439
      }
  } else {
440
      for (n = 0; n < n_capabilities; n++) {
441
          if (n == cap->no || idle_cap[n]) {
442
              pruneSparkQueue(capabilities[n]);
443 444
         }
      }
445 446 447
  }
#endif

Ben Gamari's avatar
Ben Gamari committed
448
#if defined(PROFILING)
449 450 451
  // We call processHeapClosureForDead() on every closure destroyed during
  // the current garbage collection, so we invoke LdvCensusForDead().
  if (RtsFlags.ProfFlags.doHeapProfile == HEAP_BY_LDV
452 453 454 455 456
      || RtsFlags.ProfFlags.bioSelector != NULL) {
      RELEASE_SM_LOCK; // LdvCensusForDead may need to take the lock
      LdvCensusForDead(N);
      ACQUIRE_SM_LOCK;
  }
457 458 459 460
#endif

  // NO MORE EVACUATION AFTER THIS POINT!

461
  // Finally: compact or sweep the oldest generation.
Simon Marlow's avatar
Simon Marlow committed
462
  if (major_gc && oldest_gen->mark) {
thoughtpolice's avatar
thoughtpolice committed
463
      if (oldest_gen->compact)
464 465
          compact(gct->scavenged_static_objects);
      else
Simon Marlow's avatar
Simon Marlow committed
466
          sweep(oldest_gen);
467 468
  }

469
  copied = 0;
470
  par_max_copied = 0;
471
  par_balanced_copied = 0;
472 473 474 475 476 477 478
  gc_spin_spin = 0;
  gc_spin_yield = 0;
  mut_spin_spin = 0;
  mut_spin_yield = 0;
  any_work = 0;
  no_work = 0;
  scav_find_work = 0;
thoughtpolice's avatar
thoughtpolice committed
479
  {
480
      uint32_t i;
481
      uint64_t par_balanced_copied_acc = 0;
482
      const gc_thread* thread;
483 484 485 486

      for (i=0; i < n_gc_threads; i++) {
          copied += gc_threads[i]->copied;
      }
487
      for (i=0; i < n_gc_threads; i++) {
488
          thread = gc_threads[i];
489
          if (n_gc_threads > 1) {
Simon Marlow's avatar
Simon Marlow committed
490
              debugTrace(DEBUG_gc,"thread %d:", i);
491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515
              debugTrace(DEBUG_gc,"   copied           %ld",
                         thread->copied * sizeof(W_));
              debugTrace(DEBUG_gc,"   scanned          %ld",
                         thread->scanned * sizeof(W_));
              debugTrace(DEBUG_gc,"   any_work         %ld",
                         thread->any_work);
              debugTrace(DEBUG_gc,"   no_work          %ld",
                         thread->no_work);
              debugTrace(DEBUG_gc,"   scav_find_work %ld",
                         thread->scav_find_work);

#if defined(THREADED_RTS) && defined(PROF_SPIN)
              gc_spin_spin += thread->gc_spin.spin;
              gc_spin_yield += thread->gc_spin.yield;
              mut_spin_spin += thread->mut_spin.spin;
              mut_spin_yield += thread->mut_spin.yield;
#endif

              any_work += thread->any_work;
              no_work += thread->no_work;
              scav_find_work += thread->scav_find_work;

              par_max_copied = stg_max(gc_threads[i]->copied, par_max_copied);
              par_balanced_copied_acc +=
                  stg_min(n_gc_threads * gc_threads[i]->copied, copied);
516
          }
517
      }
518
      if (n_gc_threads > 1) {
519 520 521 522
          // See Note [Work Balance] for an explanation of this computation
          par_balanced_copied =
              (par_balanced_copied_acc - copied + (n_gc_threads - 1) / 2) /
              (n_gc_threads - 1);
523 524 525
      }
  }

Simon Marlow's avatar
Simon Marlow committed
526
  // Run through all the generations and tidy up.
Simon Marlow's avatar
Simon Marlow committed
527 528 529 530 531 532 533 534 535
  // We're going to:
  //   - count the amount of "live" data (live_words, live_blocks)
  //   - count the amount of "copied" data in this GC (copied)
  //   - free from-space
  //   - make to-space the new from-space (set BF_EVACUATED on all blocks)
  //
  live_words = 0;
  live_blocks = 0;

536 537
  for (g = 0; g < RtsFlags.GcFlags.generations; g++) {

538
    if (g == N) {
thoughtpolice's avatar
thoughtpolice committed
539
      generations[g].collections++; // for stats
540
      if (n_gc_threads > 1) generations[g].par_collections++;
541 542 543 544 545
    }

    // Count the mutable list as bytes "copied" for the purposes of
    // stats.  Every mutable list is copied during every GC.
    if (g > 0) {
Simon Marlow's avatar
Simon Marlow committed
546
        W_ mut_list_size = 0;
547
        for (n = 0; n < n_capabilities; n++) {
548
            mut_list_size += countOccupied(capabilities[n]->mut_lists[g]);
549
        }
Austin Seipp's avatar
Austin Seipp committed
550
        copied +=  mut_list_size;
551

Austin Seipp's avatar
Austin Seipp committed
552
        debugTrace(DEBUG_gc,
553
                   "mut_list_size: %lu (%d vars, %d arrays, %d MVARs, %d TVARs, %d TVAR_WATCH_QUEUEs, %d TREC_CHUNKs, %d TREC_HEADERs, %d others)",
Austin Seipp's avatar
Austin Seipp committed
554
                   (unsigned long)(mut_list_size * sizeof(W_)),
555 556 557 558
                   mutlist_MUTVARS, mutlist_MUTARRS, mutlist_MVARS,
                   mutlist_TVAR, mutlist_TVAR_WATCH_QUEUE,
                   mutlist_TREC_CHUNK, mutlist_TREC_HEADER,
                   mutlist_OTHERS);
559 560
    }

Simon Marlow's avatar
Simon Marlow committed
561 562
    bdescr *next, *prev;
    gen = &generations[g];
563

thoughtpolice's avatar
thoughtpolice committed
564
    // for generations we collected...
Simon Marlow's avatar
Simon Marlow committed
565
    if (g <= N) {
566

Austin Seipp's avatar
Austin Seipp committed
567
        /* free old memory and shift to-space into from-space for all
Simon Marlow's avatar
Simon Marlow committed
568
         * the collected generations (except the allocation area).  These
Austin Seipp's avatar
Austin Seipp committed
569 570
         * freed blocks will probaby be quickly recycled.
         */
Simon Marlow's avatar
Simon Marlow committed
571 572 573 574
        if (gen->mark)
        {
            // tack the new blocks on the end of the existing blocks
            if (gen->old_blocks != NULL) {
thoughtpolice's avatar
thoughtpolice committed
575

Simon Marlow's avatar
Simon Marlow committed
576 577
                prev = NULL;
                for (bd = gen->old_blocks; bd != NULL; bd = next) {
thoughtpolice's avatar
thoughtpolice committed
578

Simon Marlow's avatar
Simon Marlow committed
579
                    next = bd->link;
thoughtpolice's avatar
thoughtpolice committed
580

Simon Marlow's avatar
Simon Marlow committed
581 582 583 584 585 586
                    if (!(bd->flags & BF_MARKED))
                    {
                        if (prev == NULL) {
                            gen->old_blocks = next;
                        } else {
                            prev->link = next;
587
                        }
Simon Marlow's avatar
Simon Marlow committed
588 589
                        freeGroup(bd);
                        gen->n_old_blocks--;
590
                    }
Simon Marlow's avatar
Simon Marlow committed
591 592 593
                    else
                    {
                        gen->n_words += bd->free - bd->start;
thoughtpolice's avatar
thoughtpolice committed
594

Simon Marlow's avatar
Simon Marlow committed
595 596 597 598 599
                        // NB. this step might not be compacted next
                        // time, so reset the BF_MARKED flags.
                        // They are set before GC if we're going to
                        // compact.  (search for BF_MARKED above).
                        bd->flags &= ~BF_MARKED;
thoughtpolice's avatar
thoughtpolice committed
600

Simon Marlow's avatar
Simon Marlow committed
601 602 603
                        // between GCs, all blocks in the heap except
                        // for the nursery have the BF_EVACUATED flag set.
                        bd->flags |= BF_EVACUATED;
thoughtpolice's avatar
thoughtpolice committed
604

Simon Marlow's avatar
Simon Marlow committed
605 606 607
                        prev = bd;
                    }
                }
608

Simon Marlow's avatar
Simon Marlow committed
609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634
                if (prev != NULL) {
                    prev->link = gen->blocks;
                    gen->blocks = gen->old_blocks;
                }
            }
            // add the new blocks to the block tally
            gen->n_blocks += gen->n_old_blocks;
            ASSERT(countBlocks(gen->blocks) == gen->n_blocks);
            ASSERT(countOccupied(gen->blocks) == gen->n_words);
        }
        else // not copacted
        {
            freeChain(gen->old_blocks);
        }

        gen->old_blocks = NULL;
        gen->n_old_blocks = 0;

        /* LARGE OBJECTS.  The current live large objects are chained on
         * scavenged_large, having been moved during garbage
         * collection from large_objects.  Any objects left on the
         * large_objects list are therefore dead, so we free them here.
         */
        freeChain(gen->large_objects);
        gen->large_objects  = gen->scavenged_large_objects;
        gen->n_large_blocks = gen->n_scavenged_large_blocks;
635
        gen->n_large_words  = countOccupied(gen->large_objects);
636
        gen->n_new_large_words = 0;
gcampax's avatar
gcampax committed
637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653

        /* COMPACT_NFDATA. The currently live compacts are chained
         * to live_compact_objects, quite like large objects. And
         * objects left on the compact_objects list are dead.
         *
         * We don't run a simple freeChain because want to give the
         * CNF module some chance to free memory that freeChain would
         * not see (namely blocks appended to a CNF through a compactResize).
         *
         * See Note [Compact Normal Forms] for details.
         */
        for (bd = gen->compact_objects; bd; bd = next) {
            next = bd->link;
            compactFree(((StgCompactNFDataBlock*)bd->start)->owner);
        }
        gen->compact_objects = gen->live_compact_objects;
        gen->n_compact_blocks = gen->n_live_compact_blocks;
Simon Marlow's avatar
Simon Marlow committed
654 655 656
    }
    else // for generations > N
    {
Austin Seipp's avatar
Austin Seipp committed
657 658 659 660 661
        /* For older generations, we need to append the
         * scavenged_large_object list (i.e. large objects that have been
         * promoted during this GC) to the large_object list for that step.
         */
        for (bd = gen->scavenged_large_objects; bd; bd = next) {
Simon Marlow's avatar
Simon Marlow committed
662 663
            next = bd->link;
            dbl_link_onto(bd, &gen->large_objects);
664 665
            gen->n_large_words += bd->free - bd->start;
        }
thoughtpolice's avatar
thoughtpolice committed
666

gcampax's avatar
gcampax committed
667 668 669 670 671 672
        // And same for compacts
        for (bd = gen->live_compact_objects; bd; bd = next) {
            next = bd->link;
            dbl_link_onto(bd, &gen->compact_objects);
        }

Austin Seipp's avatar
Austin Seipp committed
673 674
        // add the new blocks we promoted during this GC
        gen->n_large_blocks += gen->n_scavenged_large_blocks;
gcampax's avatar
gcampax committed
675
        gen->n_compact_blocks += gen->n_live_compact_blocks;
Simon Marlow's avatar
Simon Marlow committed
676 677 678
    }

    ASSERT(countBlocks(gen->large_objects) == gen->n_large_blocks);
679
    ASSERT(countOccupied(gen->large_objects) == gen->n_large_words);
gcampax's avatar
gcampax committed
680 681 682
    // We can run the same assertion on compact objects because there
    // is memory "the GC doesn't see" (directly), but which is still
    // accounted in gen->n_compact_blocks
Simon Marlow's avatar
Simon Marlow committed
683 684 685

    gen->scavenged_large_objects = NULL;
    gen->n_scavenged_large_blocks = 0;
gcampax's avatar
gcampax committed
686 687
    gen->live_compact_objects = NULL;
    gen->n_live_compact_blocks = 0;
Simon Marlow's avatar
Simon Marlow committed
688 689 690 691 692

    // Count "live" data
    live_words  += genLiveWords(gen);
    live_blocks += genLiveBlocks(gen);

693
    // add in the partial blocks in the gen_workspaces
Simon Marlow's avatar
Simon Marlow committed
694
    {
695
        uint32_t i;
Simon Marlow's avatar
Simon Marlow committed
696 697 698 699
        for (i = 0; i < n_capabilities; i++) {
            live_words  += gcThreadLiveWords(i, gen->no);
            live_blocks += gcThreadLiveBlocks(i, gen->no);
        }
700
    }
Simon Marlow's avatar
Simon Marlow committed
701
  } // for all generations
702

703 704
  // update the max size of older generations after a major GC
  resize_generations();
thoughtpolice's avatar
thoughtpolice committed
705

706
  // Free the mark stack.
707 708 709 710
  if (mark_stack_top_bd != NULL) {
      debugTrace(DEBUG_gc, "mark stack: %d blocks",
                 countBlocks(mark_stack_top_bd));
      freeChain(mark_stack_top_bd);
711 712
  }

713
  // Free any bitmaps.
714
  for (g = 0; g <= N; g++) {
Simon Marlow's avatar
Simon Marlow committed
715 716 717 718
      gen = &generations[g];
      if (gen->bitmap != NULL) {
          freeGroup(gen->bitmap);
          gen->bitmap = NULL;
719 720 721
      }
  }

722
  resize_nursery();
723

724 725 726
  resetNurseries();

 // mark the garbage collected CAFs as dead
727
#if defined(DEBUG)
728 729
  if (major_gc) { gcCAFs(); }
#endif
thoughtpolice's avatar
thoughtpolice committed
730

731 732 733 734 735 736 737 738 739
  // Update the stable pointer hash table.
  updateStableTables(major_gc);

  // unlock the StablePtr table.  Must be before scheduleFinalizers(),
  // because a finalizer may call hs_free_fun_ptr() or
  // hs_free_stable_ptr(), both of which access the StablePtr table.
  stableUnlock();

  // Must be after stableUnlock(), because it might free stable ptrs.
740 741 742 743
  if (major_gc) {
      checkUnload (gct->scavenged_static_objects);
  }

Ben Gamari's avatar
Ben Gamari committed
744
#if defined(PROFILING)
745 746
  // resetStaticObjectForRetainerProfiling() must be called before
  // zeroing below.
747 748

  // ToDo: fix the gct->scavenged_static_objects below
749
  resetStaticObjectForRetainerProfiling(gct->scavenged_static_objects);
750 751
#endif

752
  // Start any pending finalizers.  Must be after
753
  // updateStableTables() and stableUnlock() (see #4221).
754
  RELEASE_SM_LOCK;
755
  scheduleFinalizers(cap, dead_weak_ptr_list);
756 757
  ACQUIRE_SM_LOCK;

Simon Marlow's avatar
Simon Marlow committed
758 759 760 761
  // check sanity after GC
  // before resurrectThreads(), because that might overwrite some
  // closures, which will cause problems with THREADED where we don't
  // fill slop.
Ben Gamari's avatar
Ben Gamari committed
762
  IF_DEBUG(sanity, checkSanity(true /* after GC */, major_gc));
Simon Marlow's avatar
Simon Marlow committed
763

764 765 766 767 768 769
  // If a heap census is due, we need to do it before
  // resurrectThreads(), for the same reason as checkSanity above:
  // resurrectThreads() will overwrite some closures and leave slop
  // behind.
  if (do_heap_census) {
      debugTrace(DEBUG_sched, "performing heap census");
770
      RELEASE_SM_LOCK;
Ian Lynagh's avatar
Ian Lynagh committed
771
      heapCensus(gct->gc_start_cpu);
772
      ACQUIRE_SM_LOCK;
773 774
  }

Simon Marlow's avatar
Simon Marlow committed
775 776 777 778 779
  // send exceptions to any threads which were about to die
  RELEASE_SM_LOCK;
  resurrectThreads(resurrected_threads);
  ACQUIRE_SM_LOCK;

780
  if (major_gc) {
781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802
      W_ need_prealloc, need_live, need, got;
      uint32_t i;

      need_live = 0;
      for (i = 0; i < RtsFlags.GcFlags.generations; i++) {
          need_live += genLiveBlocks(&generations[i]);
      }
      need_live = stg_max(RtsFlags.GcFlags.minOldGenSize, need_live);

      need_prealloc = 0;
      for (i = 0; i < n_nurseries; i++) {
          need_prealloc += nurseries[i].n_blocks;
      }
      need_prealloc += RtsFlags.GcFlags.largeAllocLim;
      need_prealloc += countAllocdBlocks(exec_block);
      need_prealloc += arenaBlocks();
#if defined(PROFILING)
      if (RtsFlags.ProfFlags.doHeapProfile == HEAP_BY_RETAINER) {
          need_prealloc = retainerStackBlocks();
      }
#endif

803
      /* If the amount of data remains constant, next major GC we'll
804 805 806 807 808 809 810 811 812
       * require (F+1)*live + prealloc. We leave (F+2)*live + prealloc
       * in order to reduce repeated deallocation and reallocation. #14702
       */
      need = need_prealloc + (RtsFlags.GcFlags.oldGenFactor + 2) * need_live;

      /* Also, if user set heap size, do not drop below it.
       */
      need = stg_max(RtsFlags.GcFlags.heapSizeSuggestion, need);

813 814 815 816 817 818
      /* But with a large nursery, the above estimate might exceed
       * maxHeapSize.  A large resident set size might make the OS
       * kill this process, or swap unnecessarily.  Therefore we
       * ensure that our estimate does not exceed maxHeapSize.
       */
      if (RtsFlags.GcFlags.maxHeapSize != 0) {
819
          need = stg_min(RtsFlags.GcFlags.maxHeapSize, need);
820
      }
821 822 823 824 825

      need = BLOCKS_TO_MBLOCKS(need);

      got = mblocks_allocated;

826 827 828 829 830
      if (got > need) {
          returnMemoryToOS(got - need);
      }
  }

Simon Marlow's avatar
Simon Marlow committed
831
  // extra GC trace info
Simon Marlow's avatar
Simon Marlow committed
832
  IF_DEBUG(gc, statDescribeGens());
833

Ben Gamari's avatar
Ben Gamari committed
834
#if defined(DEBUG)
thoughtpolice's avatar
thoughtpolice committed
835
  // symbol-table based profiling
836 837 838
  /*  heapCensus(to_blocks); */ /* ToDo */
#endif

thoughtpolice's avatar
thoughtpolice committed
839
  // restore enclosing cost centre
Ben Gamari's avatar
Ben Gamari committed
840
#if defined(PROFILING)
841
  for (n = 0; n < n_capabilities; n++) {
842
      capabilities[n]->r.rCCCS = save_CCS[n];
843
  }
844 845
#endif

Ben Gamari's avatar
Ben Gamari committed
846
#if defined(DEBUG)
thoughtpolice's avatar
thoughtpolice committed
847
  // check for memory leaks if DEBUG is on
848
  memInventory(DEBUG_gc);
849 850
#endif

thoughtpolice's avatar
thoughtpolice committed
851
  // ok, GC over: tell the stats department what happened.
852
  stat_endGC(cap, gct, live_words, copied,
853
             live_blocks * BLOCK_SIZE_W - live_words /* slop */,
854 855 856
             N, n_gc_threads, par_max_copied, par_balanced_copied,
             gc_spin_spin, gc_spin_yield, mut_spin_spin, mut_spin_yield,
             any_work, no_work, scav_find_work);
857 858

#if defined(RTS_USER_SIGNALS)
859 860 861 862
  if (RtsFlags.MiscFlags.install_signal_handlers) {
    // unblock signals again
    unblockUserSignals();
  }
863 864 865
#endif

  RELEASE_SM_LOCK;
866

867
  SET_GCT(saved_gct);
868 869
}

870 871 872 873 874 875 876 877 878 879
/* -----------------------------------------------------------------------------
   Heap overflow is indicated by setting a flag that the caller of
   GarbageCollect can check.  (not ideal, TODO: better)
   -------------------------------------------------------------------------- */

static void heapOverflow(void)
{
    heap_overflow = true;
}

880 881 882 883
/* -----------------------------------------------------------------------------
   Initialise the gc_thread structures.
   -------------------------------------------------------------------------- */

884
static void
885
new_gc_thread (uint32_t n, gc_thread *t)
886
{
887
    uint32_t g;
Simon Marlow's avatar
Simon Marlow committed
888
    gen_workspace *ws;
889

890
    t->cap = capabilities[n];
Simon Marlow's avatar