GC.c 53.4 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"

Simon Marlow's avatar
Simon Marlow committed
31
#include "Storage.h"
32 33 34 35 36 37 38 39 40 41 42 43 44 45
#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
46
#include "LdvProfile.h"
47
#include "RaiseAsync.h"
Simon Marlow's avatar
Simon Marlow committed
48
#include "Stable.h"
49
#include "CheckUnload.h"
gcampax's avatar
gcampax committed
50
#include "CNF.h"
51 52

#include <string.h> // for memset()
53
#include <unistd.h>
54

55 56 57 58
/* -----------------------------------------------------------------------------
   Global variables
   -------------------------------------------------------------------------- */

59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
/* 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
76
 * shouldn't matter).
77 78 79 80 81
 *
 * 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
82
 * means that we have to mark the end of the list with '1', not NULL.
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
 *
 * 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.
 */

/* 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.
 */
99
uint32_t N;
Ben Gamari's avatar
Ben Gamari committed
100
bool major_gc;
101 102 103

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

/* Mut-list stats */
#ifdef DEBUG
108
uint32_t mutlist_MUTVARS,
109
    mutlist_MUTARRS,
110
    mutlist_MVARS,
111 112 113 114 115 116
    mutlist_TVAR,
    mutlist_TVAR_WATCH_QUEUE,
    mutlist_TREC_CHUNK,
    mutlist_TREC_HEADER,
    mutlist_ATOMIC_INVARIANT,
    mutlist_INVARIANT_CHECK_QUEUE,
117 118 119
    mutlist_OTHERS;
#endif

120 121
/* Thread-local data for each GC thread
 */
122
gc_thread **gc_threads = NULL;
123 124

#if !defined(THREADED_RTS)
Simon Marlow's avatar
Simon Marlow committed
125
StgWord8 the_gc_thread[sizeof(gc_thread) + 64 * sizeof(gen_workspace)];
126
#endif
127

128 129
// Number of threads running in *this* GC.  Affects how many
// step->todos[] lists we have to look in to find work.
130
uint32_t n_gc_threads;
131

132
// For stats:
133
static long copied;        // *words* copied & scavenged during this GC
134

Ben Gamari's avatar
Ben Gamari committed
135
bool work_stealing;
136

137 138
uint32_t static_flag = STATIC_FLAG_B;
uint32_t prev_static_flag = STATIC_FLAG_A;
139

140 141
DECLARE_GCT

142 143 144 145
/* -----------------------------------------------------------------------------
   Static function declarations
   -------------------------------------------------------------------------- */

146
static void mark_root               (void *user, StgClosure **root);
Simon Marlow's avatar
Simon Marlow committed
147 148
static void prepare_collected_gen   (generation *gen);
static void prepare_uncollected_gen (generation *gen);
149 150 151
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
152
static void start_gc_threads        (void);
153
static void scavenge_until_all_done (void);
154 155
static StgWord inc_running          (void);
static StgWord dec_running          (void);
Ben Gamari's avatar
Ben Gamari committed
156 157
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
158
static void collect_gct_blocks      (void);
159
static void collect_pinned_object_blocks (void);
160

161
#if defined(DEBUG)
162
static void gcCAFs                  (void);
163 164 165
#endif

/* -----------------------------------------------------------------------------
166
   The mark stack.
167 168
   -------------------------------------------------------------------------- */

169 170 171
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
172 173

/* -----------------------------------------------------------------------------
174
   GarbageCollect: the main entry point to the garbage collector.
175

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

178 179 180 181
   Locks held: all capabilities are held throughout GarbageCollect().
   -------------------------------------------------------------------------- */

void
182
GarbageCollect (uint32_t collect_gen,
Ben Gamari's avatar
Ben Gamari committed
183
                bool do_heap_census,
184
                uint32_t gc_type USED_IF_THREADS,
185
                Capability *cap,
Ben Gamari's avatar
Ben Gamari committed
186
                bool idle_cap[])
187 188
{
  bdescr *bd;
Simon Marlow's avatar
Simon Marlow committed
189
  generation *gen;
Simon Marlow's avatar
Simon Marlow committed
190
  StgWord live_blocks, live_words, par_max_copied;
Ian Lynagh's avatar
Ian Lynagh committed
191
#if defined(THREADED_RTS)
192
  gc_thread *saved_gct;
Ian Lynagh's avatar
Ian Lynagh committed
193
#endif
194
  uint32_t g, n;
195

196
  // necessary if we stole a callee-saves register for gct:
Ian Lynagh's avatar
Ian Lynagh committed
197
#if defined(THREADED_RTS)
198
  saved_gct = gct;
Ian Lynagh's avatar
Ian Lynagh committed
199
#endif
200

201
#ifdef PROFILING
202
  CostCentreStack *save_CCS[n_capabilities];
203 204
#endif

205 206
  ACQUIRE_SM_LOCK;

207
#if defined(RTS_USER_SIGNALS)
208 209 210 211
  if (RtsFlags.MiscFlags.install_signal_handlers) {
    // block signals
    blockUserSignals();
  }
212 213
#endif

Simon Marlow's avatar
Simon Marlow committed
214 215
  ASSERT(sizeof(gen_workspace) == 16 * sizeof(StgWord));
  // otherwise adjust the padding in gen_workspace.
216

Simon Marlow's avatar
Simon Marlow committed
217 218
  // this is the main thread
  SET_GCT(gc_threads[cap->no]);
219

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

223
  // lock the StablePtr table
224
  stableLock();
225

226 227 228
#ifdef DEBUG
  mutlist_MUTVARS = 0;
  mutlist_MUTARRS = 0;
229 230 231 232 233 234 235
  mutlist_MVARS = 0;
  mutlist_TVAR = 0;
  mutlist_TVAR_WATCH_QUEUE = 0;
  mutlist_TREC_CHUNK = 0;
  mutlist_TREC_HEADER = 0;
  mutlist_ATOMIC_INVARIANT = 0;
  mutlist_INVARIANT_CHECK_QUEUE = 0;
236 237 238
  mutlist_OTHERS = 0;
#endif

thoughtpolice's avatar
thoughtpolice committed
239
  // attribute any costs to CCS_GC
240
#ifdef PROFILING
241
  for (n = 0; n < n_capabilities; n++) {
242 243
      save_CCS[n] = capabilities[n]->r.rCCCS;
      capabilities[n]->r.rCCCS = CCS_GC;
244
  }
245 246 247 248
#endif

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

252 253 254 255 256 257
  if (major_gc) {
      prev_static_flag = static_flag;
      static_flag =
          static_flag == STATIC_FLAG_A ? STATIC_FLAG_B : STATIC_FLAG_A;
  }

258
#if defined(THREADED_RTS)
259 260
  work_stealing = RtsFlags.ParFlags.parGcLoadBalancingEnabled &&
                  N >= RtsFlags.ParFlags.parGcLoadBalancingGen;
261 262 263
      // 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
264
      // (this effect can be quite significant).
265 266 267 268 269 270 271
      //
      // 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
272 273 274 275
  /* Start threads, so they can be spinning up while we finish initialisation.
   */
  start_gc_threads();

276
#if defined(THREADED_RTS)
277
  /* How many threads will be participating in this GC?
278 279
   * We don't try to parallelise minor GCs (unless the user asks for
   * it with +RTS -gn0), or mark/compact/sweep GC.
280
   */
281
  if (gc_type == SYNC_GC_PAR) {
282
      n_gc_threads = n_capabilities;
283
  } else {
284
      n_gc_threads = 1;
285
  }
286
#else
287
  n_gc_threads = 1;
288
#endif
289

290 291
  debugTrace(DEBUG_gc, "GC (gen %d, using %d thread(s))",
             N, n_gc_threads);
292

293
#ifdef DEBUG
thoughtpolice's avatar
thoughtpolice committed
294
  // check for memory leaks if DEBUG is on
295
  memInventory(DEBUG_gc);
296 297
#endif

298 299 300
  // do this *before* we start scavenging
  collectFreshWeakPtrs();

301
  // check sanity *before* GC
Ben Gamari's avatar
Ben Gamari committed
302
  IF_DEBUG(sanity, checkSanity(false /* before GC */, major_gc));
303

304 305
  // gather blocks allocated using allocatePinned() from each capability
  // and put them on the g0->large_object list.
306
  collect_pinned_object_blocks();
307

Simon Marlow's avatar
Simon Marlow committed
308
  // Initialise all the generations that we're collecting.
309
  for (g = 0; g <= N; g++) {
Simon Marlow's avatar
Simon Marlow committed
310
      prepare_collected_gen(&generations[g]);
311
  }
Simon Marlow's avatar
Simon Marlow committed
312
  // Initialise all the generations that we're *not* collecting.
313
  for (g = N+1; g < RtsFlags.GcFlags.generations; g++) {
Simon Marlow's avatar
Simon Marlow committed
314
      prepare_uncollected_gen(&generations[g]);
315 316
  }

Simon Marlow's avatar
Simon Marlow committed
317 318 319
  // Prepare this gc_thread
  init_gc_thread(gct);

320 321
  /* Allocate a mark stack if we're doing a major collection.
   */
Simon Marlow's avatar
Simon Marlow committed
322
  if (major_gc && oldest_gen->mark) {
323 324 325 326 327
      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;
328
  } else {
329 330 331
      mark_stack_bd     = NULL;
      mark_stack_top_bd = NULL;
      mark_sp           = NULL;
332 333 334 335 336
  }

  /* -----------------------------------------------------------------------
   * follow all the roots that we know about:
   */
337 338 339 340 341 342

  // 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();
343
  wakeup_gc_threads(gct->thread_index, idle_cap);
Simon Marlow's avatar
Simon Marlow committed
344 345

  traceEventGcWork(gct->cap);
346

347 348 349 350 351 352
  // 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
353
#if defined(THREADED_RTS)
354
          scavenge_capability_mut_Lists1(capabilities[n]);
Simon Marlow's avatar
Simon Marlow committed
355
#else
356
          scavenge_capability_mut_lists(capabilities[n]);
Simon Marlow's avatar
Simon Marlow committed
357
#endif
358 359
      }
  } else {
Simon Marlow's avatar
Simon Marlow committed
360
      scavenge_capability_mut_lists(gct->cap);
361
      for (n = 0; n < n_capabilities; n++) {
362
          if (idle_cap[n]) {
363
              markCapability(mark_root, gct, capabilities[n],
Ben Gamari's avatar
Ben Gamari committed
364
                             true/*don't mark sparks*/);
365
              scavenge_capability_mut_lists(capabilities[n]);
366 367
          }
      }
368 369
  }

370
  // follow roots from the CAF list (used by GHCi)
Simon Marlow's avatar
Simon Marlow committed
371
  gct->evac_gen_no = 0;
372
  markCAFs(mark_root, gct);
373

374
  // follow all the roots that the application knows about.
Simon Marlow's avatar
Simon Marlow committed
375
  gct->evac_gen_no = 0;
Simon Marlow's avatar
Simon Marlow committed
376 377
  if (n_gc_threads == 1) {
      for (n = 0; n < n_capabilities; n++) {
378
          markCapability(mark_root, gct, capabilities[n],
Ben Gamari's avatar
Ben Gamari committed
379
                         true/*don't mark sparks*/);
Simon Marlow's avatar
Simon Marlow committed
380 381
      }
  } else {
Ben Gamari's avatar
Ben Gamari committed
382
      markCapability(mark_root, gct, cap, true/*don't mark sparks*/);
Simon Marlow's avatar
Simon Marlow committed
383 384 385
  }

  markScheduler(mark_root, gct);
386

387 388
#if defined(RTS_USER_SIGNALS)
  // mark the signal handlers (signals should be already blocked)
389
  markSignalHandlers(mark_root, gct);
390 391
#endif

392
  // Mark the weak pointer list, and prepare to detect dead weak pointers.
393 394 395
  markWeakPtrList();
  initWeakForGC();

396
  // Mark the stable pointer table.
397
  markStableTables(mark_root, gct);
398 399 400 401 402

  /* -------------------------------------------------------------------------
   * Repeatedly scavenge all the areas we know about until there's no
   * more scavenging to be done.
   */
Simon Marlow's avatar
Simon Marlow committed
403 404
  for (;;)
  {
405
      scavenge_until_all_done();
Simon Marlow's avatar
Simon Marlow committed
406 407
      // 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
408

Simon Marlow's avatar
Simon Marlow committed
409 410
      // must be last...  invariant is that everything is fully
      // scavenged at this point.
Ben Gamari's avatar
Ben Gamari committed
411
      if (traverseWeakPtrList()) { // returns true if evaced something
Austin Seipp's avatar
Austin Seipp committed
412 413
          inc_running();
          continue;
Simon Marlow's avatar
Simon Marlow committed
414
      }
415

Simon Marlow's avatar
Simon Marlow committed
416 417
      // If we get to here, there's really nothing left to do.
      break;
418 419
  }

420
  shutdown_gc_threads(gct->thread_index, idle_cap);
421

422
  // Now see which stable names are still alive.
423
  gcStableTables();
424

425 426 427
#ifdef THREADED_RTS
  if (n_gc_threads == 1) {
      for (n = 0; n < n_capabilities; n++) {
428
          pruneSparkQueue(capabilities[n]);
429 430
      }
  } else {
431
      for (n = 0; n < n_capabilities; n++) {
432
          if (n == cap->no || idle_cap[n]) {
433
              pruneSparkQueue(capabilities[n]);
434 435
         }
      }
436 437 438
  }
#endif

439 440 441 442
#ifdef PROFILING
  // We call processHeapClosureForDead() on every closure destroyed during
  // the current garbage collection, so we invoke LdvCensusForDead().
  if (RtsFlags.ProfFlags.doHeapProfile == HEAP_BY_LDV
443 444 445 446 447
      || RtsFlags.ProfFlags.bioSelector != NULL) {
      RELEASE_SM_LOCK; // LdvCensusForDead may need to take the lock
      LdvCensusForDead(N);
      ACQUIRE_SM_LOCK;
  }
448 449 450 451
#endif

  // NO MORE EVACUATION AFTER THIS POINT!

452
  // Finally: compact or sweep the oldest generation.
Simon Marlow's avatar
Simon Marlow committed
453
  if (major_gc && oldest_gen->mark) {
thoughtpolice's avatar
thoughtpolice committed
454
      if (oldest_gen->compact)
455 456
          compact(gct->scavenged_static_objects);
      else
Simon Marlow's avatar
Simon Marlow committed
457
          sweep(oldest_gen);
458 459
  }

460
  copied = 0;
461
  par_max_copied = 0;
thoughtpolice's avatar
thoughtpolice committed
462
  {
463
      uint32_t i;
464
      for (i=0; i < n_gc_threads; i++) {
465
          if (n_gc_threads > 1) {
Simon Marlow's avatar
Simon Marlow committed
466 467 468 469 470 471
              debugTrace(DEBUG_gc,"thread %d:", i);
              debugTrace(DEBUG_gc,"   copied           %ld", gc_threads[i]->copied * sizeof(W_));
              debugTrace(DEBUG_gc,"   scanned          %ld", gc_threads[i]->scanned * sizeof(W_));
              debugTrace(DEBUG_gc,"   any_work         %ld", gc_threads[i]->any_work);
              debugTrace(DEBUG_gc,"   no_work          %ld", gc_threads[i]->no_work);
              debugTrace(DEBUG_gc,"   scav_find_work %ld",   gc_threads[i]->scav_find_work);
472 473
          }
          copied += gc_threads[i]->copied;
474
          par_max_copied = stg_max(gc_threads[i]->copied, par_max_copied);
475 476
      }
      if (n_gc_threads == 1) {
477
          par_max_copied = 0;
478 479 480
      }
  }

Simon Marlow's avatar
Simon Marlow committed
481
  // Run through all the generations and tidy up.
Simon Marlow's avatar
Simon Marlow committed
482 483 484 485 486 487 488 489 490
  // 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;

491 492
  for (g = 0; g < RtsFlags.GcFlags.generations; g++) {

493
    if (g == N) {
thoughtpolice's avatar
thoughtpolice committed
494
      generations[g].collections++; // for stats
495
      if (n_gc_threads > 1) generations[g].par_collections++;
496 497 498 499 500
    }

    // 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
501
        W_ mut_list_size = 0;
502
        for (n = 0; n < n_capabilities; n++) {
503
            mut_list_size += countOccupied(capabilities[n]->mut_lists[g]);
504
        }
Austin Seipp's avatar
Austin Seipp committed
505
        copied +=  mut_list_size;
506

Austin Seipp's avatar
Austin Seipp committed
507 508 509
        debugTrace(DEBUG_gc,
                   "mut_list_size: %lu (%d vars, %d arrays, %d MVARs, %d TVARs, %d TVAR_WATCH_QUEUEs, %d TREC_CHUNKs, %d TREC_HEADERs, %d ATOMIC_INVARIANTs, %d INVARIANT_CHECK_QUEUEs, %d others)",
                   (unsigned long)(mut_list_size * sizeof(W_)),
510 511 512 513 514 515
                   mutlist_MUTVARS, mutlist_MUTARRS, mutlist_MVARS,
                   mutlist_TVAR, mutlist_TVAR_WATCH_QUEUE,
                   mutlist_TREC_CHUNK, mutlist_TREC_HEADER,
                   mutlist_ATOMIC_INVARIANT,
                   mutlist_INVARIANT_CHECK_QUEUE,
                   mutlist_OTHERS);
516 517
    }

Simon Marlow's avatar
Simon Marlow committed
518 519
    bdescr *next, *prev;
    gen = &generations[g];
520

thoughtpolice's avatar
thoughtpolice committed
521
    // for generations we collected...
Simon Marlow's avatar
Simon Marlow committed
522
    if (g <= N) {
523

Austin Seipp's avatar
Austin Seipp committed
524
        /* free old memory and shift to-space into from-space for all
Simon Marlow's avatar
Simon Marlow committed
525
         * the collected generations (except the allocation area).  These
Austin Seipp's avatar
Austin Seipp committed
526 527
         * freed blocks will probaby be quickly recycled.
         */
Simon Marlow's avatar
Simon Marlow committed
528 529 530 531
        if (gen->mark)
        {
            // tack the new blocks on the end of the existing blocks
            if (gen->old_blocks != NULL) {
thoughtpolice's avatar
thoughtpolice committed
532

Simon Marlow's avatar
Simon Marlow committed
533 534
                prev = NULL;
                for (bd = gen->old_blocks; bd != NULL; bd = next) {
thoughtpolice's avatar
thoughtpolice committed
535

Simon Marlow's avatar
Simon Marlow committed
536
                    next = bd->link;
thoughtpolice's avatar
thoughtpolice committed
537

Simon Marlow's avatar
Simon Marlow committed
538 539 540 541 542 543
                    if (!(bd->flags & BF_MARKED))
                    {
                        if (prev == NULL) {
                            gen->old_blocks = next;
                        } else {
                            prev->link = next;
544
                        }
Simon Marlow's avatar
Simon Marlow committed
545 546
                        freeGroup(bd);
                        gen->n_old_blocks--;
547
                    }
Simon Marlow's avatar
Simon Marlow committed
548 549 550
                    else
                    {
                        gen->n_words += bd->free - bd->start;
thoughtpolice's avatar
thoughtpolice committed
551

Simon Marlow's avatar
Simon Marlow committed
552 553 554 555 556
                        // 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
557

Simon Marlow's avatar
Simon Marlow committed
558 559 560
                        // 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
561

Simon Marlow's avatar
Simon Marlow committed
562 563 564
                        prev = bd;
                    }
                }
565

Simon Marlow's avatar
Simon Marlow committed
566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591
                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;
592
        gen->n_large_words  = countOccupied(gen->large_objects);
593
        gen->n_new_large_words = 0;
gcampax's avatar
gcampax committed
594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610

        /* 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
611 612 613
    }
    else // for generations > N
    {
Austin Seipp's avatar
Austin Seipp committed
614 615 616 617 618
        /* 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
619 620
            next = bd->link;
            dbl_link_onto(bd, &gen->large_objects);
621 622
            gen->n_large_words += bd->free - bd->start;
        }
thoughtpolice's avatar
thoughtpolice committed
623

gcampax's avatar
gcampax committed
624 625 626 627 628 629
        // 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
630 631
        // add the new blocks we promoted during this GC
        gen->n_large_blocks += gen->n_scavenged_large_blocks;
gcampax's avatar
gcampax committed
632
        gen->n_compact_blocks += gen->n_live_compact_blocks;
Simon Marlow's avatar
Simon Marlow committed
633 634 635
    }

    ASSERT(countBlocks(gen->large_objects) == gen->n_large_blocks);
636
    ASSERT(countOccupied(gen->large_objects) == gen->n_large_words);
gcampax's avatar
gcampax committed
637 638 639
    // 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
640 641 642

    gen->scavenged_large_objects = NULL;
    gen->n_scavenged_large_blocks = 0;
gcampax's avatar
gcampax committed
643 644
    gen->live_compact_objects = NULL;
    gen->n_live_compact_blocks = 0;
Simon Marlow's avatar
Simon Marlow committed
645 646 647 648 649

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

650
    // add in the partial blocks in the gen_workspaces
Simon Marlow's avatar
Simon Marlow committed
651
    {
652
        uint32_t i;
Simon Marlow's avatar
Simon Marlow committed
653 654 655 656
        for (i = 0; i < n_capabilities; i++) {
            live_words  += gcThreadLiveWords(i, gen->no);
            live_blocks += gcThreadLiveBlocks(i, gen->no);
        }
657
    }
Simon Marlow's avatar
Simon Marlow committed
658
  } // for all generations
659

660 661
  // update the max size of older generations after a major GC
  resize_generations();
thoughtpolice's avatar
thoughtpolice committed
662

663
  // Free the mark stack.
664 665 666 667
  if (mark_stack_top_bd != NULL) {
      debugTrace(DEBUG_gc, "mark stack: %d blocks",
                 countBlocks(mark_stack_top_bd));
      freeChain(mark_stack_top_bd);
668 669
  }

670
  // Free any bitmaps.
671
  for (g = 0; g <= N; g++) {
Simon Marlow's avatar
Simon Marlow committed
672 673 674 675
      gen = &generations[g];
      if (gen->bitmap != NULL) {
          freeGroup(gen->bitmap);
          gen->bitmap = NULL;
676 677 678
      }
  }

679
  resize_nursery();
680

681 682 683
  resetNurseries();

 // mark the garbage collected CAFs as dead
684
#if defined(DEBUG)
685 686
  if (major_gc) { gcCAFs(); }
#endif
thoughtpolice's avatar
thoughtpolice committed
687

688 689 690 691 692 693 694 695 696
  // 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.
697 698 699 700
  if (major_gc) {
      checkUnload (gct->scavenged_static_objects);
  }

701 702 703
#ifdef PROFILING
  // resetStaticObjectForRetainerProfiling() must be called before
  // zeroing below.
704 705

  // ToDo: fix the gct->scavenged_static_objects below
706
  resetStaticObjectForRetainerProfiling(gct->scavenged_static_objects);
707 708
#endif

709
  // Start any pending finalizers.  Must be after
710
  // updateStableTables() and stableUnlock() (see #4221).
711
  RELEASE_SM_LOCK;
712
  scheduleFinalizers(cap, dead_weak_ptr_list);
713 714
  ACQUIRE_SM_LOCK;

Simon Marlow's avatar
Simon Marlow committed
715 716 717 718
  // 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
719
  IF_DEBUG(sanity, checkSanity(true /* after GC */, major_gc));
Simon Marlow's avatar
Simon Marlow committed
720

721 722 723 724 725 726
  // 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");
727
      RELEASE_SM_LOCK;
Ian Lynagh's avatar
Ian Lynagh committed
728
      heapCensus(gct->gc_start_cpu);
729
      ACQUIRE_SM_LOCK;
730 731
  }

Simon Marlow's avatar
Simon Marlow committed
732 733 734 735 736
  // send exceptions to any threads which were about to die
  RELEASE_SM_LOCK;
  resurrectThreads(resurrected_threads);
  ACQUIRE_SM_LOCK;

737
  if (major_gc) {
Simon Marlow's avatar
Simon Marlow committed
738
      W_ need, got;
739 740 741 742 743 744 745 746 747 748 749
      need = BLOCKS_TO_MBLOCKS(n_alloc_blocks);
      got = mblocks_allocated;
      /* If the amount of data remains constant, next major GC we'll
         require (F+1)*need. We leave (F+2)*need in order to reduce
         repeated deallocation and reallocation. */
      need = (RtsFlags.GcFlags.oldGenFactor + 2) * need;
      if (got > need) {
          returnMemoryToOS(got - need);
      }
  }

Simon Marlow's avatar
Simon Marlow committed
750
  // extra GC trace info
Simon Marlow's avatar
Simon Marlow committed
751
  IF_DEBUG(gc, statDescribeGens());
752 753

#ifdef DEBUG
thoughtpolice's avatar
thoughtpolice committed
754
  // symbol-table based profiling
755 756 757
  /*  heapCensus(to_blocks); */ /* ToDo */
#endif

thoughtpolice's avatar
thoughtpolice committed
758
  // restore enclosing cost centre
759
#ifdef PROFILING
760
  for (n = 0; n < n_capabilities; n++) {
761
      capabilities[n]->r.rCCCS = save_CCS[n];
762
  }
763 764 765
#endif

#ifdef DEBUG
thoughtpolice's avatar
thoughtpolice committed
766
  // check for memory leaks if DEBUG is on
767
  memInventory(DEBUG_gc);
768 769
#endif

thoughtpolice's avatar
thoughtpolice committed
770
  // ok, GC over: tell the stats department what happened.
771
  stat_endGC(cap, gct, live_words, copied,
772
             live_blocks * BLOCK_SIZE_W - live_words /* slop */,
Simon Marlow's avatar
Simon Marlow committed
773
             N, n_gc_threads, par_max_copied);
774 775

#if defined(RTS_USER_SIGNALS)
776 777 778 779
  if (RtsFlags.MiscFlags.install_signal_handlers) {
    // unblock signals again
    unblockUserSignals();
  }
780 781 782
#endif

  RELEASE_SM_LOCK;
783

784
  SET_GCT(saved_gct);
785 786
}

787 788 789 790
/* -----------------------------------------------------------------------------
   Initialise the gc_thread structures.
   -------------------------------------------------------------------------- */

791 792 793 794 795
#define GC_THREAD_INACTIVE             0
#define GC_THREAD_STANDING_BY          1
#define GC_THREAD_RUNNING              2
#define GC_THREAD_WAITING_TO_CONTINUE  3

796
static void
797
new_gc_thread (uint32_t n, gc_thread *t)
798
{
799
    uint32_t g;
Simon Marlow's avatar
Simon Marlow committed
800
    gen_workspace *ws;
801

802
    t->cap = capabilities[n];
Simon Marlow's avatar
Simon Marlow committed
803

Simon Marlow's avatar
Simon Marlow committed
804 805
#ifdef THREADED_RTS
    t->id = 0;
806 807 808
    initSpinLock(&t->gc_spin);
    initSpinLock(&t->mut_spin);
    ACQUIRE_SPIN_LOCK(&t->gc_spin);
809
    ACQUIRE_SPIN_LOCK(&t->mut_spin);
810
    t->wakeup = GC_THREAD_INACTIVE;  // starts true, so we can wait for the
811
                          // thread to start up, see wakeup_gc_threads
Simon Marlow's avatar
Simon Marlow committed
812 813
#endif

814 815 816 817 818
    t->thread_index = n;
    t->free_blocks = NULL;
    t->gc_count = 0;

    init_gc_thread(t);
thoughtpolice's avatar
thoughtpolice committed
819

Simon Marlow's avatar
Simon Marlow committed
820
    for (g = 0; g < RtsFlags.GcFlags.generations; g++)
821
    {
Simon Marlow's avatar
Simon Marlow committed
822 823 824
        ws = &t->gens[g];
        ws->gen = &generations[g];
        ASSERT(g == ws->gen->no);
825
        ws->my_gct = t;
thoughtpolice's avatar
thoughtpolice committed
826

Simon Marlow's avatar
Simon Marlow committed
827 828 829 830 831
        // We want to call
        //   alloc_todo_block(ws,0);
        // but can't, because it uses gct which isn't set up at this point.
        // Hence, allocate a block for todo_bd manually:
        {
Simon Marlow's avatar
Simon Marlow committed
832 833
            bdescr *bd = allocBlockOnNode(capNoToNumaNode(n));
                // no lock, locks aren't initialised yet
Simon Marlow's avatar
Simon Marlow committed
834 835 836 837 838 839 840 841 842
            initBdescr(bd, ws->gen, ws->gen->to);
            bd->flags = BF_EVACUATED;
            bd->u.scan = bd->free = bd->start;

            ws->todo_bd = bd;
            ws->todo_free = bd->free;
            ws->todo_lim = bd->start + BLOCK_SIZE_W;
        }

843 844 845