GC.c 50.8 KB
Newer Older
1 2
/* -----------------------------------------------------------------------------
 *
3
 * (c) The GHC Team 1998-2008
4 5 6
 *
 * Generational garbage collector
 *
7 8 9 10 11
 * Documentation on the architecture of the Garbage Collector can be
 * found in the online commentary:
 * 
 *   http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/GC
 *
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 18
#include "HsFFI.h"

#include "Storage.h"
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
#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"
#if defined(RTS_GTK_FRONTPANEL)
#include "FrontPanel.h"
#endif
#include "Trace.h"
#include "RetainerProfile.h"
Simon Marlow's avatar
Simon Marlow committed
36
#include "LdvProfile.h"
37
#include "RaiseAsync.h"
38
#include "Papi.h"
Simon Marlow's avatar
Simon Marlow committed
39
#include "Stable.h"
40 41

#include "GC.h"
42
#include "GCThread.h"
43 44 45 46 47
#include "Compact.h"
#include "Evac.h"
#include "Scav.h"
#include "GCUtils.h"
#include "MarkWeak.h"
Simon Marlow's avatar
Simon Marlow committed
48
#include "Sparks.h"
49
#include "Sweep.h"
50 51

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

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

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

/* Data used for allocation area sizing.
 */
static lnat g0s0_pcnt_kept = 30; // percentage of g0s0 live at last minor GC 

/* Mut-list stats */
#ifdef DEBUG
nat mutlist_MUTVARS,
    mutlist_MUTARRS,
109
    mutlist_MVARS,
110 111 112
    mutlist_OTHERS;
#endif

113 114
/* Thread-local data for each GC thread
 */
115
gc_thread **gc_threads = NULL;
116 117 118 119

#if !defined(THREADED_RTS)
StgWord8 the_gc_thread[sizeof(gc_thread) + 64 * sizeof(step_workspace)];
#endif
120

121 122 123 124
// Number of threads running in *this* GC.  Affects how many
// step->todos[] lists we have to look in to find work.
nat n_gc_threads;

125 126 127
// For stats:
long copied;        // *words* copied & scavenged during this GC

128 129
rtsBool work_stealing;

130 131
DECLARE_GCT

132 133 134 135
/* -----------------------------------------------------------------------------
   Static function declarations
   -------------------------------------------------------------------------- */

136
static void mark_root               (void *user, StgClosure **root);
137
static void zero_static_object_list (StgClosure* first_static);
138
static nat  initialise_N            (rtsBool force_major_gc);
139 140 141 142 143 144
static void init_collected_gen      (nat g, nat threads);
static void init_uncollected_gen    (nat g, nat threads);
static void init_gc_thread          (gc_thread *t);
static void update_task_list        (void);
static void resize_generations      (void);
static void resize_nursery          (void);
Simon Marlow's avatar
Simon Marlow committed
145
static void start_gc_threads        (void);
146
static void scavenge_until_all_done (void);
147 148
static StgWord inc_running          (void);
static StgWord dec_running          (void);
149 150
static void wakeup_gc_threads       (nat n_threads, nat me);
static void shutdown_gc_threads     (nat n_threads, nat me);
151 152

#if 0 && defined(DEBUG)
153
static void gcCAFs                  (void);
154 155 156
#endif

/* -----------------------------------------------------------------------------
157
   The mark bitmap & stack.
158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
   -------------------------------------------------------------------------- */

#define MARK_STACK_BLOCKS 4

bdescr *mark_stack_bdescr;
StgPtr *mark_stack;
StgPtr *mark_sp;
StgPtr *mark_splim;

// Flag and pointers used for falling back to a linear scan when the
// mark stack overflows.
rtsBool mark_stack_overflowed;
bdescr *oldgen_scan_bd;
StgPtr  oldgen_scan;

/* -----------------------------------------------------------------------------
174
   GarbageCollect: the main entry point to the garbage collector.
175 176 177 178 179

   Locks held: all capabilities are held throughout GarbageCollect().
   -------------------------------------------------------------------------- */

void
180 181
GarbageCollect (rtsBool force_major_gc, 
                nat gc_type USED_IF_THREADS,
182
                Capability *cap)
183 184 185
{
  bdescr *bd;
  step *stp;
186
  lnat live, allocated, max_copied, avg_copied, slop;
187
  gc_thread *saved_gct;
188
  nat g, s, t, n;
189

190 191 192
  // necessary if we stole a callee-saves register for gct:
  saved_gct = gct;

193 194 195 196
#ifdef PROFILING
  CostCentreStack *prev_CCS;
#endif

197 198
  ACQUIRE_SM_LOCK;

199
#if defined(RTS_USER_SIGNALS)
200 201 202 203
  if (RtsFlags.MiscFlags.install_signal_handlers) {
    // block signals
    blockUserSignals();
  }
204 205
#endif

206 207 208
  ASSERT(sizeof(step_workspace) == 16 * sizeof(StgWord));
  // otherwise adjust the padding in step_workspace.

209 210 211
  // tell the stats department that we've started a GC 
  stat_startGC();

simonmar@microsoft.com's avatar
simonmar@microsoft.com committed
212 213 214
  // tell the STM to discard any cached closures it's hoping to re-use
  stmPreGCHook();

215 216 217
  // lock the StablePtr table
  stablePtrPreGC();

218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236
#ifdef DEBUG
  mutlist_MUTVARS = 0;
  mutlist_MUTARRS = 0;
  mutlist_OTHERS = 0;
#endif

  // attribute any costs to CCS_GC 
#ifdef PROFILING
  prev_CCS = CCCS;
  CCCS = CCS_GC;
#endif

  /* Approximate how much we allocated.  
   * Todo: only when generating stats? 
   */
  allocated = calcAllocated();

  /* Figure out which generation to collect
   */
237
  n = initialise_N(force_major_gc);
238

239 240 241 242 243 244 245 246 247 248 249 250 251
#if defined(THREADED_RTS)
  work_stealing = RtsFlags.ParFlags.parGcLoadBalancing;
      // 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
      // (this effect can be quite significant). 
      //
      // 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
252 253 254 255
  /* Start threads, so they can be spinning up while we finish initialisation.
   */
  start_gc_threads();

256
#if defined(THREADED_RTS)
257
  /* How many threads will be participating in this GC?
258 259
   * We don't try to parallelise minor GCs (unless the user asks for
   * it with +RTS -gn0), or mark/compact/sweep GC.
260
   */
261 262
  if (gc_type == PENDING_GC_PAR) {
      n_gc_threads = RtsFlags.ParFlags.nNodes;
263
  } else {
264
      n_gc_threads = 1;
265
  }
266
#else
267
  n_gc_threads = 1;
268
#endif
269

Simon Marlow's avatar
Simon Marlow committed
270
  debugTrace(DEBUG_gc, "GC (gen %d): %d KB to collect, %ld MB in use, using %d thread(s)",
271
        N, n * (BLOCK_SIZE / 1024), mblocks_allocated, n_gc_threads);
272 273 274 275 276 277 278

#ifdef RTS_GTK_FRONTPANEL
  if (RtsFlags.GcFlags.frontpanel) {
      updateFrontPanelBeforeGC(N);
  }
#endif

279 280 281 282 283
#ifdef DEBUG
  // check for memory leaks if DEBUG is on 
  memInventory(traceClass(DEBUG_gc));
#endif

284
  // check stack sanity *before* GC
285
  IF_DEBUG(sanity, checkFreeListSanity());
Simon Marlow's avatar
Simon Marlow committed
286
  IF_DEBUG(sanity, checkMutableLists(rtsTrue));
287

288 289 290 291 292
  // Initialise all our gc_thread structures
  for (t = 0; t < n_gc_threads; t++) {
      init_gc_thread(gc_threads[t]);
  }

293
  // Initialise all the generations/steps that we're collecting.
294
  for (g = 0; g <= N; g++) {
295
      init_collected_gen(g,n_gc_threads);
296
  }
297 298
  
  // Initialise all the generations/steps that we're *not* collecting.
299
  for (g = N+1; g < RtsFlags.GcFlags.generations; g++) {
300
      init_uncollected_gen(g,n_gc_threads);
301 302 303 304
  }

  /* Allocate a mark stack if we're doing a major collection.
   */
305
  if (major_gc && oldest_gen->steps[0].mark) {
306 307 308 309
      nat mark_stack_blocks;
      mark_stack_blocks = stg_max(MARK_STACK_BLOCKS, 
                                  oldest_gen->steps[0].n_old_blocks / 100);
      mark_stack_bdescr = allocGroup(mark_stack_blocks);
310 311
      mark_stack = (StgPtr *)mark_stack_bdescr->start;
      mark_sp    = mark_stack;
312
      mark_splim = mark_stack + (mark_stack_blocks * BLOCK_SIZE_W);
313 314 315 316
  } else {
      mark_stack_bdescr = NULL;
  }

Simon Marlow's avatar
Simon Marlow committed
317
  // this is the main thread
318 319
#ifdef THREADED_RTS
  if (n_gc_threads == 1) {
320
      SET_GCT(gc_threads[0]);
321
  } else {
322
      SET_GCT(gc_threads[cap->no]);
323 324
  }
#else
325
SET_GCT(gc_threads[0]);
326
#endif
327 328 329 330

  /* -----------------------------------------------------------------------
   * follow all the roots that we know about:
   */
331 332 333 334 335 336

  // 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();
337
  wakeup_gc_threads(n_gc_threads, gct->thread_index);
338

339 340 341 342 343 344
  // Mutable lists from each generation > N
  // we want to *scavenge* these roots, not evacuate them: they're not
  // going to move in this GC.
  // Also do them in reverse generation order, for the usual reason:
  // namely to reduce the likelihood of spurious old->new pointers.
  //
345
  for (g = RtsFlags.GcFlags.generations-1; g > N; g--) {
346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361
      scavenge_mutable_list(generations[g].saved_mut_list, &generations[g]);
      freeChain_sync(generations[g].saved_mut_list);
      generations[g].saved_mut_list = NULL;

  }

  // 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++) {
          scavenge_capability_mut_lists(&capabilities[n]);
      }
  } else {
      scavenge_capability_mut_lists(&capabilities[gct->thread_index]);
362 363
  }

364
  // follow roots from the CAF list (used by GHCi)
365
  gct->evac_step = 0;
366
  markCAFs(mark_root, gct);
367

368
  // follow all the roots that the application knows about.
369
  gct->evac_step = 0;
370 371
  markSomeCapabilities(mark_root, gct, gct->thread_index, n_gc_threads,
                       rtsTrue/*prune sparks*/);
372

373 374
#if defined(RTS_USER_SIGNALS)
  // mark the signal handlers (signals should be already blocked)
375
  markSignalHandlers(mark_root, gct);
376 377
#endif

378
  // Mark the weak pointer list, and prepare to detect dead weak pointers.
379 380 381
  markWeakPtrList();
  initWeakForGC();

382
  // Mark the stable pointer table.
383
  markStablePtrTable(mark_root, gct);
384 385 386 387 388

  /* -------------------------------------------------------------------------
   * Repeatedly scavenge all the areas we know about until there's no
   * more scavenging to be done.
   */
Simon Marlow's avatar
Simon Marlow committed
389 390
  for (;;)
  {
391
      scavenge_until_all_done();
Simon Marlow's avatar
Simon Marlow committed
392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407
      // The other threads are now stopped.  We might recurse back to
      // here, but from now on this is the only thread.
      
      // if any blackholes are alive, make the threads that wait on
      // them alive too.
      if (traverseBlackholeQueue()) {
	  inc_running(); 
	  continue;
      }
  
      // must be last...  invariant is that everything is fully
      // scavenged at this point.
      if (traverseWeakPtrList()) { // returns rtsTrue if evaced something 
	  inc_running();
	  continue;
      }
408

Simon Marlow's avatar
Simon Marlow committed
409 410
      // If we get to here, there's really nothing left to do.
      break;
411 412
  }

413
  shutdown_gc_threads(n_gc_threads, gct->thread_index);
414

415 416
  // Update pointers from the Task list
  update_task_list();
417 418 419 420 421 422 423 424 425 426 427 428 429 430

  // Now see which stable names are still alive.
  gcStablePtrTable();

#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
      || RtsFlags.ProfFlags.bioSelector != NULL)
    LdvCensusForDead(N);
#endif

  // NO MORE EVACUATION AFTER THIS POINT!

431 432 433 434 435 436 437 438 439 440
  // Two-space collector: free the old to-space.
  // g0s0->old_blocks is the old nursery
  // g0s0->blocks is to-space from the previous GC
  if (RtsFlags.GcFlags.generations == 1) {
      if (g0s0->blocks != NULL) {
	  freeChain(g0s0->blocks);
	  g0s0->blocks = NULL;
      }
  }

441
  // For each workspace, in each thread, move the copied blocks to the step
442 443 444
  {
      gc_thread *thr;
      step_workspace *ws;
445
      bdescr *prev, *next;
446

447
      for (t = 0; t < n_gc_threads; t++) {
448 449 450
	  thr = gc_threads[t];

          // not step 0
451 452 453 454 455 456
          if (RtsFlags.GcFlags.generations == 1) {
              s = 0;
          } else {
              s = 1;
          }
          for (; s < total_steps; s++) {
457 458 459
              ws = &thr->steps[s];

              // Push the final block
460 461 462 463 464
              if (ws->todo_bd) { 
                  push_scanned_block(ws->todo_bd, ws);
              }

              ASSERT(gct->scan_bd == NULL);
465 466
              ASSERT(countBlocks(ws->scavd_list) == ws->n_scavd_blocks);
              
467 468
              prev = NULL;
              for (bd = ws->scavd_list; bd != NULL; bd = bd->link) {
469
                  ws->step->n_words += bd->free - bd->start;
470 471 472
                  prev = bd;
              }
              if (prev != NULL) {
473 474 475 476
                  prev->link = ws->step->blocks;
                  ws->step->blocks = ws->scavd_list;
              } 
              ws->step->n_blocks += ws->n_scavd_blocks;
477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493
          }
      }

      // Add all the partial blocks *after* we've added all the full
      // blocks.  This is so that we can grab the partial blocks back
      // again and try to fill them up in the next GC.
      for (t = 0; t < n_gc_threads; t++) {
	  thr = gc_threads[t];

          // not step 0
          if (RtsFlags.GcFlags.generations == 1) {
              s = 0;
          } else {
              s = 1;
          }
          for (; s < total_steps; s++) {
              ws = &thr->steps[s];
494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509

              prev = NULL;
              for (bd = ws->part_list; bd != NULL; bd = next) {
                  next = bd->link;
                  if (bd->free == bd->start) {
                      if (prev == NULL) {
                          ws->part_list = next;
                      } else {
                          prev->link = next;
                      }
                      freeGroup(bd);
                      ws->n_part_blocks--;
                  } else {
                      ws->step->n_words += bd->free - bd->start;
                      prev = bd;
                  }
510
              }
511 512
              if (prev != NULL) {
                  prev->link = ws->step->blocks;
513 514 515
                  ws->step->blocks = ws->part_list;
              }
              ws->step->n_blocks += ws->n_part_blocks;
516

517
              ASSERT(countBlocks(ws->step->blocks) == ws->step->n_blocks);
518
              ASSERT(countOccupied(ws->step->blocks) == ws->step->n_words);
519 520 521 522
	  }
      }
  }

523 524 525 526 527 528
  // Finally: compact or sweep the oldest generation.
  if (major_gc && oldest_gen->steps[0].mark) {
      if (oldest_gen->steps[0].compact) 
          compact(gct->scavenged_static_objects);
      else
          sweep(&oldest_gen->steps[0]);
529 530
  }

531 532
  /* run through all the generations/steps and tidy up 
   */
533
  copied = 0;
534 535
  max_copied = 0;
  avg_copied = 0;
536 537 538
  { 
      nat i;
      for (i=0; i < n_gc_threads; i++) {
539
          if (n_gc_threads > 1) {
Simon Marlow's avatar
Simon Marlow committed
540 541 542 543 544 545
              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);
546 547
          }
          copied += gc_threads[i]->copied;
548 549 550 551 552 553 554
          max_copied = stg_max(gc_threads[i]->copied, max_copied);
      }
      if (n_gc_threads == 1) {
          max_copied = 0;
          avg_copied = 0;
      } else {
          avg_copied = copied;
555 556 557
      }
  }

558 559
  for (g = 0; g < RtsFlags.GcFlags.generations; g++) {

560
    if (g == N) {
561
      generations[g].collections++; // for stats 
562
      if (n_gc_threads > 1) generations[g].par_collections++;
563 564 565 566 567 568 569 570 571
    }

    // Count the mutable list as bytes "copied" for the purposes of
    // stats.  Every mutable list is copied during every GC.
    if (g > 0) {
	nat mut_list_size = 0;
	for (bd = generations[g].mut_list; bd != NULL; bd = bd->link) {
	    mut_list_size += bd->free - bd->start;
	}
572 573 574 575 576 577
        for (n = 0; n < n_capabilities; n++) {
            for (bd = capabilities[n].mut_lists[g]; 
                 bd != NULL; bd = bd->link) {
                mut_list_size += bd->free - bd->start;
            }
        }
578 579 580
	copied +=  mut_list_size;

	debugTrace(DEBUG_gc,
581
		   "mut_list_size: %lu (%d vars, %d arrays, %d MVARs, %d others)",
582
		   (unsigned long)(mut_list_size * sizeof(W_)),
583
		   mutlist_MUTVARS, mutlist_MUTARRS, mutlist_MVARS, mutlist_OTHERS);
584 585 586
    }

    for (s = 0; s < generations[g].n_steps; s++) {
587
      bdescr *next, *prev;
588 589 590 591 592 593 594 595 596
      stp = &generations[g].steps[s];

      // for generations we collected... 
      if (g <= N) {

	/* free old memory and shift to-space into from-space for all
	 * the collected steps (except the allocation area).  These
	 * freed blocks will probaby be quickly recycled.
	 */
597
	if (!(g == 0 && s == 0 && RtsFlags.GcFlags.generations > 1)) {
598
	    if (stp->mark)
599
            {
600 601
		// tack the new blocks on the end of the existing blocks
		if (stp->old_blocks != NULL) {
602 603

                    prev = NULL;
604
		    for (bd = stp->old_blocks; bd != NULL; bd = next) {
605 606 607 608 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

                        next = bd->link;

                        if (!(bd->flags & BF_MARKED))
                        {
                            if (prev == NULL) {
                                stp->old_blocks = next;
                            } else {
                                prev->link = next;
                            }
                            freeGroup(bd);
                            stp->n_old_blocks--;
                        }
                        else
                        {
                            stp->n_words += bd->free - bd->start;

                            // 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;
                            
                            // between GCs, all blocks in the heap except
                            // for the nursery have the BF_EVACUATED flag set.
                            bd->flags |= BF_EVACUATED;

                            prev = bd;
                        }
634
		    }
635 636 637 638 639

                    if (prev != NULL) {
                        prev->link = stp->blocks;
                        stp->blocks = stp->old_blocks;
                    }
640 641 642 643
		}
		// add the new blocks to the block tally
		stp->n_blocks += stp->n_old_blocks;
		ASSERT(countBlocks(stp->blocks) == stp->n_blocks);
644
                ASSERT(countOccupied(stp->blocks) == stp->n_words);
645 646 647
	    }
	    else // not copacted
	    {
648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667
		freeChain(stp->old_blocks);
	    }
	    stp->old_blocks = NULL;
	    stp->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
	 * large_objects list are therefore dead, so we free them here.
	 */
	for (bd = stp->large_objects; bd != NULL; bd = next) {
	  next = bd->link;
	  freeGroup(bd);
	  bd = next;
	}

	stp->large_objects  = stp->scavenged_large_objects;
	stp->n_large_blocks = stp->n_scavenged_large_blocks;

668 669 670
      }
      else // for older generations... 
      {
671 672 673 674 675 676 677 678 679 680 681 682 683 684 685
	/* 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 = stp->scavenged_large_objects; bd; bd = next) {
	  next = bd->link;
	  dbl_link_onto(bd, &stp->large_objects);
	}

	// add the new blocks we promoted during this GC 
	stp->n_large_blocks += stp->n_scavenged_large_blocks;
      }
    }
  }

686 687 688
  // update the max size of older generations after a major GC
  resize_generations();
  
689 690
  // Calculate the amount of live data for stats.
  live = calcLiveWords();
691

692 693
  // Free the small objects allocated via allocate(), since this will
  // all have been copied into G0S1 now.  
694 695 696 697 698 699
  if (RtsFlags.GcFlags.generations > 1) {
      if (g0s0->blocks != NULL) {
          freeChain(g0s0->blocks);
          g0s0->blocks = NULL;
      }
      g0s0->n_blocks = 0;
700
      g0s0->n_words = 0;
701 702 703 704 705 706 707
  }
  alloc_blocks = 0;
  alloc_blocks_lim = RtsFlags.GcFlags.minAllocAreaSize;

  // Start a new pinned_object_block
  pinned_object_block = NULL;

708
  // Free the mark stack.
709 710 711 712
  if (mark_stack_bdescr != NULL) {
      freeGroup(mark_stack_bdescr);
  }

713
  // Free any bitmaps.
714 715 716 717 718 719 720 721 722 723
  for (g = 0; g <= N; g++) {
      for (s = 0; s < generations[g].n_steps; s++) {
	  stp = &generations[g].steps[s];
	  if (stp->bitmap != NULL) {
	      freeGroup(stp->bitmap);
	      stp->bitmap = NULL;
	  }
      }
  }

724
  resize_nursery();
725 726 727 728 729 730 731 732 733

 // mark the garbage collected CAFs as dead 
#if 0 && defined(DEBUG) // doesn't work at the moment 
  if (major_gc) { gcCAFs(); }
#endif
  
#ifdef PROFILING
  // resetStaticObjectForRetainerProfiling() must be called before
  // zeroing below.
734 735 736 737 738
  if (n_gc_threads > 1) {
      barf("profiling is currently broken with multi-threaded GC");
      // ToDo: fix the gct->scavenged_static_objects below
  }
  resetStaticObjectForRetainerProfiling(gct->scavenged_static_objects);
739 740 741 742
#endif

  // zero the scavenged static object list 
  if (major_gc) {
743 744 745 746
      nat i;
      for (i = 0; i < n_gc_threads; i++) {
          zero_static_object_list(gc_threads[i]->scavenged_static_objects);
      }
747 748 749 750 751 752 753
  }

  // Reset the nursery
  resetNurseries();

  // start any pending finalizers 
  RELEASE_SM_LOCK;
754
  scheduleFinalizers(cap, old_weak_ptr_list);
755 756 757 758 759
  ACQUIRE_SM_LOCK;
  
  // send exceptions to any threads which were about to die 
  RELEASE_SM_LOCK;
  resurrectThreads(resurrected_threads);
760
  performPendingThrowTos(exception_threads);
761 762 763 764 765 766 767 768 769
  ACQUIRE_SM_LOCK;

  // Update the stable pointer hash table.
  updateStablePtrTable(major_gc);

  // check sanity after GC 
  IF_DEBUG(sanity, checkSanity());

  // extra GC trace info 
Simon Marlow's avatar
Simon Marlow committed
770
  IF_DEBUG(gc, statDescribeGens());
771 772 773 774 775 776 777 778 779 780 781 782 783

#ifdef DEBUG
  // symbol-table based profiling 
  /*  heapCensus(to_blocks); */ /* ToDo */
#endif

  // restore enclosing cost centre 
#ifdef PROFILING
  CCCS = prev_CCS;
#endif

#ifdef DEBUG
  // check for memory leaks if DEBUG is on 
784
  memInventory(traceClass(DEBUG_gc));
785 786 787 788 789 790 791 792 793
#endif

#ifdef RTS_GTK_FRONTPANEL
  if (RtsFlags.GcFlags.frontpanel) {
      updateFrontPanelAfterGC( N, live );
  }
#endif

  // ok, GC over: tell the stats department what happened. 
794 795
  slop = calcLiveBlocks() * BLOCK_SIZE_W - live;
  stat_endGC(allocated, live, copied, N, max_copied, avg_copied, slop);
796

797 798 799
  // unlock the StablePtr table
  stablePtrPostGC();

800 801 802
  // Guess which generation we'll collect *next* time
  initialise_N(force_major_gc);

803
#if defined(RTS_USER_SIGNALS)
804 805 806 807
  if (RtsFlags.MiscFlags.install_signal_handlers) {
    // unblock signals again
    unblockUserSignals();
  }
808 809 810
#endif

  RELEASE_SM_LOCK;
811

812
  SET_GCT(saved_gct);
813 814
}

815 816
/* -----------------------------------------------------------------------------
   Figure out which generation to collect, initialise N and major_gc.
817 818 819

   Also returns the total number of blocks in generations that will be
   collected.
820 821
   -------------------------------------------------------------------------- */

822
static nat
823 824
initialise_N (rtsBool force_major_gc)
{
825 826 827 828 829
    int g;
    nat s, blocks, blocks_total;

    blocks = 0;
    blocks_total = 0;
830 831

    if (force_major_gc) {
832
        N = RtsFlags.GcFlags.generations - 1;
833
    } else {
834
        N = 0;
835
    }
836 837 838 839

    for (g = RtsFlags.GcFlags.generations - 1; g >= 0; g--) {
        blocks = 0;
        for (s = 0; s < generations[g].n_steps; s++) {
840
            blocks += generations[g].steps[s].n_words / BLOCK_SIZE_W;
841 842 843 844 845 846 847 848 849 850 851 852 853 854
            blocks += generations[g].steps[s].n_large_blocks;
        }
        if (blocks >= generations[g].max_blocks) {
            N = stg_max(N,g);
        }
        if ((nat)g <= N) {
            blocks_total += blocks;
        }
    }

    blocks_total += countNurseryBlocks();

    major_gc = (N == RtsFlags.GcFlags.generations-1);
    return blocks_total;
855 856 857 858 859 860
}

/* -----------------------------------------------------------------------------
   Initialise the gc_thread structures.
   -------------------------------------------------------------------------- */

861 862 863 864 865
#define GC_THREAD_INACTIVE             0
#define GC_THREAD_STANDING_BY          1
#define GC_THREAD_RUNNING              2
#define GC_THREAD_WAITING_TO_CONTINUE  3

866 867
static void
new_gc_thread (nat n, gc_thread *t)
868
{
869
    nat s;
870 871
    step_workspace *ws;

Simon Marlow's avatar
Simon Marlow committed
872 873
#ifdef THREADED_RTS
    t->id = 0;
874 875 876 877
    initSpinLock(&t->gc_spin);
    initSpinLock(&t->mut_spin);
    ACQUIRE_SPIN_LOCK(&t->gc_spin);
    t->wakeup = GC_THREAD_INACTIVE;  // starts true, so we can wait for the
878
                          // thread to start up, see wakeup_gc_threads
Simon Marlow's avatar
Simon Marlow committed
879 880
#endif

881 882 883 884 885 886
    t->thread_index = n;
    t->free_blocks = NULL;
    t->gc_count = 0;

    init_gc_thread(t);
    
887 888 889 890
#ifdef USE_PAPI
    t->papi_events = -1;
#endif

891
    for (s = 0; s < total_steps; s++)
892
    {
893
        ws = &t->steps[s];
894 895
        ws->step = &all_steps[s];
        ASSERT(s == ws->step->abs_no);
896
        ws->my_gct = t;
897 898
        
        ws->todo_bd = NULL;
899 900 901
        ws->todo_q = newWSDeque(128);
        ws->todo_overflow = NULL;
        ws->n_todo_overflow = 0;
902
        
903 904 905
        ws->part_list = NULL;
        ws->n_part_blocks = 0;

906 907
        ws->scavd_list = NULL;
        ws->n_scavd_blocks = 0;
908 909 910 911
    }
}


912 913
void
initGcThreads (void)
914 915 916 917
{
    if (gc_threads == NULL) {
#if defined(THREADED_RTS)
        nat i;
918
	gc_threads = stgMallocBytes (RtsFlags.ParFlags.nNodes * 
919
				     sizeof(gc_thread*), 
920 921
				     "alloc_gc_threads");

922
	for (i = 0; i < RtsFlags.ParFlags.nNodes; i++) {
923 924 925 926 927
            gc_threads[i] = 
                stgMallocBytes(sizeof(gc_thread) + total_steps * sizeof(step_workspace),
                               "alloc_gc_threads");

            new_gc_thread(i, gc_threads[i]);
928 929
	}
#else
930 931 932
        gc_threads = stgMallocBytes (sizeof(gc_thread*),"alloc_gc_threads");
	gc_threads[0] = gct;
        new_gc_thread(0,gc_threads[0]);
933 934 935 936
#endif
    }
}

937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953
void
freeGcThreads (void)
{
    if (gc_threads != NULL) {
#if defined(THREADED_RTS)
        nat i;
	for (i = 0; i < RtsFlags.ParFlags.nNodes; i++) {
            stgFree (gc_threads[i]);
	}
        stgFree (gc_threads);
#else
        stgFree (gc_threads);
#endif
        gc_threads = NULL;
    }
}

Simon Marlow's avatar
Simon Marlow committed
954 955 956 957
/* ----------------------------------------------------------------------------
   Start GC threads
   ------------------------------------------------------------------------- */

958
static volatile StgWord gc_running_threads;
Simon Marlow's avatar
Simon Marlow committed
959

960
static StgWord
Simon Marlow's avatar
Simon Marlow committed
961 962
inc_running (void)
{
963 964 965 966
    StgWord new;
    new = atomic_inc(&gc_running_threads);
    ASSERT(new <= n_gc_threads);
    return new;
Simon Marlow's avatar
Simon Marlow committed
967 968
}

969
static StgWord
Simon Marlow's avatar
Simon Marlow committed
970 971
dec_running (void)
{
972 973
    ASSERT(gc_running_threads != 0);
    return atomic_dec(&gc_running_threads);
Simon Marlow's avatar
Simon Marlow committed
974 975
}

976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000
static rtsBool
any_work (void)
{
    int s;
    step_workspace *ws;

    gct->any_work++;

    write_barrier();

    // scavenge objects in compacted generation
    if (mark_stack_overflowed || oldgen_scan_bd != NULL ||
	(mark_stack_bdescr != NULL && !mark_stack_empty())) {
	return rtsTrue;
    }
    
    // Check for global work in any step.  We don't need to check for
    // local work, because we have already exited scavenge_loop(),
    // which means there is no local work for this thread.
    for (s = total_steps-1; s >= 0; s--) {
        if (s == 0 && RtsFlags.GcFlags.generations > 1) { 
            continue; 
        }
        ws = &gct->steps[s];
        if (ws->todo_large_objects) return rtsTrue;
1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015
        if (!looksEmptyWSDeque(ws->todo_q)) return rtsTrue;
        if (ws->todo_overflow) return rtsTrue;
    }

#if defined(THREADED_RTS)
    if (work_stealing) {
        nat n;
        // look for work to steal
        for (n = 0; n < n_gc_threads; n++) {
            if (n == gct->thread_index) continue;
            for (s = total_steps-1; s >= 0; s--) {
                ws = &gc_threads[n]->steps[s];
                if (!looksEmptyWSDeque(ws->todo_q)) return rtsTrue;
            }
        }
1016
    }
1017
#endif
1018 1019 1020 1021 1022 1023

    gct->no_work++;

    return rtsFalse;
}    

Simon Marlow's avatar
Simon Marlow committed
1024
static void
1025
scavenge_until_all_done (void)
Simon Marlow's avatar
Simon Marlow committed
1026 1027 1028 1029 1030 1031
{
    nat r;
	
    debugTrace(DEBUG_gc, "GC thread %d working", gct->thread_index);

loop:
1032 1033 1034 1035 1036 1037 1038
#if defined(THREADED_RTS)
    if (n_gc_threads > 1) {
        scavenge_loop();
    } else {
        scavenge_loop1();
    }
#else
Simon Marlow's avatar
Simon Marlow committed
1039
    scavenge_loop();
1040 1041
#endif

Simon Marlow's avatar
Simon Marlow committed
1042 1043 1044 1045
    // scavenge_loop() only exits when there's no work to do
    r = dec_running();
    
    debugTrace(DEBUG_gc, "GC thread %d idle (%d still running)", 
1046 1047
               gct->thread_index, r);
    
Simon Marlow's avatar
Simon Marlow committed
1048
    while (gc_running_threads != 0) {
1049
        // usleep(1);
1050 1051 1052 1053 1054 1055 1056 1057
        if (any_work()) {
            inc_running();
            goto loop;
        }
        // any_work() does not remove the work from the queue, it
        // just checks for the presence of work.  If we find any,
        // then we increment gc_running_threads and go back to 
        // scavenge_loop() to perform any pending work.
Simon Marlow's avatar
Simon Marlow committed
1058 1059 1060 1061 1062 1063 1064
    }
    
    // All threads are now stopped
    debugTrace(DEBUG_gc, "GC thread %d finished.", gct->thread_index);
}

#if defined(THREADED_RTS)
1065 1066 1067

void
gcWorkerThread (Capability *cap)
1068
{
1069 1070 1071 1072
    cap->in_gc = rtsTrue;

    gct = gc_threads[cap->no];
    gct->id = osThreadId();
1073

1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087
    // Wait until we're told to wake up
    RELEASE_SPIN_LOCK(&gct->mut_spin);
    gct->wakeup = GC_THREAD_STANDING_BY;
    debugTrace(DEBUG_gc, "GC thread %d standing by...", gct->thread_index);
    ACQUIRE_SPIN_LOCK(&gct->gc_spin);
    
#ifdef USE_PAPI
    // start performance counters in this thread...
    if (gct->papi_events == -1) {
        papi_init_eventset(&gct->papi_events);
    }
    papi_thread_start_gc1_count(gct->papi_events);
#endif
    
1088 1089
    // Every thread evacuates some roots.
    gct->evac_step = 0;
1090 1091
    markSomeCapabilities(mark_root, gct, gct->thread_index, n_gc_threads,
                         rtsTrue/*prune sparks*/);
1092
    scavenge_capability_mut_lists(&capabilities[gct->thread_index]);
1093 1094

    scavenge_until_all_done();
1095
    
1096
#ifdef USE_PAPI
1097 1098
    // count events in this thread towards the GC totals
    papi_thread_stop_gc1_count(gct->papi_events);
1099 1100
#endif

1101 1102 1103 1104 1105 1106 1107 1108
    // Wait until we're told to continue
    RELEASE_SPIN_LOCK(&gct->gc_spin);
    gct->wakeup = GC_THREAD_WAITING_TO_CONTINUE;
    debugTrace(DEBUG_gc, "GC thread %d waiting to continue...", 
               gct->thread_index);
    ACQUIRE_SPIN_LOCK(&gct->mut_spin);
    debugTrace(DEBUG_gc, "GC thread %d on my way...", gct->thread_index);
}
1109

Simon Marlow's avatar
Simon Marlow committed
1110 1111
#endif

Simon Marlow's avatar
Simon Marlow committed
1112 1113
#if defined(THREADED_RTS)

1114 1115
void
waitForGcThreads (Capability *cap USED_IF_THREADS)
Simon Marlow's avatar
Simon Marlow committed
1116
{
1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142
    nat n_threads = RtsFlags.ParFlags.nNodes;
    nat me = cap->no;
    nat i, j;
    rtsBool retry = rtsTrue;

    while(retry) {
        for (i=0; i < n_threads; i++) {
            if (i == me) continue;
            if (gc_threads[i]->wakeup != GC_THREAD_STANDING_BY) {
                prodCapability(&capabilities[i], cap->running_task);
            }
        }
        for (j=0; j < 10000000; j++) {
            retry = rtsFalse;
            for (i=0; i < n_threads; i++) {
                if (i == me) continue;
                write_barrier();
                setContextSwitches();
                if (gc_threads[i]->wakeup != GC_THREAD_STANDING_BY) {
                    retry = rtsTrue;
                }
            }
            if (!retry) break;
        }
    }
}
Simon Marlow's avatar
Simon Marlow committed
1143

Simon Marlow's avatar
Simon Marlow committed
1144 1145
#endif // THREADED_RTS

Simon Marlow's avatar
Simon Marlow committed
1146 1147 1148 1149 1150 1151 1152 1153 1154
static void
start_gc_threads (void)
{
#if defined(THREADED_RTS)
    gc_running_threads = 0;
#endif
}

static void
1155
wakeup_gc_threads (nat n_threads USED_IF_THREADS, nat me USED_IF_THREADS)
Simon Marlow's avatar
Simon Marlow committed
1156 1157 1158
{
#if defined(THREADED_RTS)
    nat i;
1159 1160
    for (i=0; i < n_threads; i++) {
        if (i == me) continue;
Simon Marlow's avatar
Simon Marlow committed
1161
	inc_running();
1162
        debugTrace(DEBUG_gc, "waking up gc thread %d", i);
1163 1164 1165 1166 1167
        if (gc_threads[i]->wakeup != GC_THREAD_STANDING_BY) barf("wakeup_gc_threads");

	gc_threads[i]->wakeup = GC_THREAD_RUNNING;
        ACQUIRE_SPIN_LOCK(&gc_threads[i]->mut_spin);
        RELEASE_SPIN_LOCK(&gc_threads[i]->gc_spin);
Simon Marlow's avatar
Simon Marlow committed
1168 1169 1170 1171
    }
#endif
}

1172 1173 1174 1175
// After GC is complete, we must wait for all GC threads to enter the
// standby state, otherwise they may still be executing inside
// any_work(), and may even remain awake until the next GC starts.
static void
1176
shutdown_gc_threads (nat n_threads USED_IF_THREADS, nat me USED_IF_THREADS)
1177 1178 1179
{
#if defined(THREADED_RTS)
    nat i;
1180 1181 1182 1183 1184 1185 1186
    for (i=0; i < n_threads; i++) {
        if (i == me) continue;
        while (gc_threads[i]->wakeup != GC_THREAD_WAITING_TO_CONTINUE) { write_barrier(); }
    }
#endif
}

Simon Marlow's avatar
Simon Marlow committed
1187
#if defined(THREADED_RTS)
1188 1189
void
releaseGCThreads (Capability *cap USED_IF_THREADS)
1190
{
1191 1192
    nat n_threads = RtsFlags.ParFlags.nNodes;
    nat me = cap->no;
1193 1194 1195
    nat i;
    for (i=0; i < n_threads; i++) {
        if (i == me) continue;
1196 1197
        if (gc_threads[i]->wakeup != GC_THREAD_WAITING_TO_CONTINUE) 
            barf("releaseGCThreads");
1198 1199 1200 1201
        
        gc_threads[i]->wakeup = GC_THREAD_INACTIVE;
        ACQUIRE_SPIN_LOCK(&gc_threads[i]->gc_spin);
        RELEASE_SPIN_LOCK(&gc_threads[i]->mut_spin);
1202 1203
    }
}
Simon Marlow's avatar
Simon Marlow committed
1204
#endif
1205

1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231
/* ----------------------------------------------------------------------------
   Initialise a generation that is to be collected 
   ------------------------------------------------------------------------- */

static void
init_collected_gen (nat g, nat n_threads)
{
    nat s, t, i;
    step_workspace *ws;
    step *stp;
    bdescr *bd;

    // Throw away the current mutable list.  Invariant: the mutable
    // list always has at least one block; this means we can avoid a
    // check for NULL in recordMutable().
    if (g != 0) {
	freeChain(generations[g].mut_list);
	generations[g].mut_list = allocBlock();
	for (i = 0; i < n_capabilities; i++) {
	    freeChain(capabilities[i].mut_lists[g]);
	    capabilities[i].mut_lists[g] = allocBlock();
	}
    }

    for (s = 0; s < generations[g].n_steps; s++) {

1232 1233 1234 1235 1236 1237 1238 1239
	stp = &generations[g].steps[s];
	ASSERT(stp->gen_no == g);

        // we'll construct a new list of threads in this step
        // during GC, throw away the current list.
        stp->old_threads = stp->threads;
        stp->threads = END_TSO_QUEUE;

1240 1241 1242 1243 1244 1245 1246 1247 1248 1249
	// generation 0, step 0 doesn't need to-space 
	if (g == 0 && s == 0 && RtsFlags.GcFlags.generations > 1) { 
	    continue; 
	}
	
	// deprecate the existing blocks
	stp->old_blocks   = stp->blocks;
	stp->n_old_blocks = stp->n_blocks;
	stp->blocks       = NULL;
	stp->n_blocks     = 0;
1250
	stp->n_words      = 0;
1251
	stp->live_estimate = 0;
1252 1253 1254 1255 1256

	// initialise the large object queues.
	stp->scavenged_large_objects = NULL;
	stp->n_scavenged_large_blocks = 0;

1257 1258 1259 1260 1261 1262
	// mark the small objects as from-space
	for (bd = stp->old_blocks; bd; bd = bd->link) {
	    bd->flags &= ~BF_EVACUATED;
	}

	// mark the large objects as from-space
1263 1264 1265 1266 1267
	for (bd = stp->large_objects; bd; bd = bd->link) {
	    bd->flags &= ~BF_EVACUATED;
	}

	// for a compacted step, we need to allocate the bitmap
1268
	if (stp->mark) {
1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292
	    nat bitmap_size; // in bytes
	    bdescr *bitmap_bdescr;
	    StgWord *bitmap;
	    
	    bitmap_size = stp->n_old_blocks * BLOCK_SIZE / (sizeof(W_)*BITS_PER_BYTE);
	    
	    if (bitmap_size > 0) {
		bitmap_bdescr = allocGroup((lnat)BLOCK_ROUND_UP(bitmap_size) 
					   / BLOCK_SIZE);
		stp->bitmap = bitmap_bdescr;
		bitmap = bitmap_bdescr->start;
		
		debugTrace(DEBUG_gc, "bitmap_size: %d, bitmap: %p",
			   bitmap_size, bitmap);
		
		// don't forget to fill it with zeros!
		memset(bitmap, 0, bitmap_size);
		
		// For each block in this step, point to its bitmap from the
		// block descriptor.
		for (bd=stp->old_blocks; bd != NULL; bd = bd->link) {
		    bd->u.bitmap = bitmap;
		    bitmap += BLOCK_SIZE_W / (sizeof(W_)*BITS_PER_BYTE);
		    
1293
		    // Also at this point we set the BF_MARKED flag
1294
		    // for this block.  The invariant is that
1295
		    // BF_MARKED is always unset, except during GC
1296 1297
		    // when it is set on those blocks which will be
		    // compacted.
1298 1299 1300
                    if (!(bd->flags & BF_FRAGMENTED)) {
                        bd->flags |= BF_MARKED;
                    }
1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314
		}
	    }
	}
    }

    // For each GC thread, for each step, allocate a "todo" block to
    // store evacuated objects to be scavenged, and a block to store
    // evacuated objects that do not need to be scavenged.
    for (t = 0; t < n_threads; t++) {
	for (s = 0; s < generations[g].n_steps; s++) {

	    // we don't copy objects into g0s0, unless -G0
	    if (g==0 && s==0 && RtsFlags.GcFlags.generations > 1) continue;

1315
	    ws = &gc_threads[t]->steps[g * RtsFlags.GcFlags.steps + s];
1316 1317 1318

	    ws->todo_large_objects = NULL;

1319 1320 1321
            ws->part_list = NULL;
            ws->n_part_blocks = 0;

1322 1323 1324
	    // allocate the first to-space block; extra blocks will be
	    // chained on as necessary.
	    ws->todo_bd = NULL;
1325
            ASSERT(looksEmptyWSDeque(ws->todo_q));
1326
	    alloc_todo_block(ws,0);
1327

1328 1329 1330
            ws->todo_overflow = NULL;
            ws->n_todo_overflow = 0;

1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344
	    ws->scavd_list = NULL;
	    ws->n_scavd_blocks = 0;
	}
    }
}


/* ----------------------------------------------------------------------------
   Initialise a generation that is *not* to be collected 
   ------------------------------------------------------------------------- */

static void
init_uncollected_gen (nat g, nat threads)
{
1345
    nat s, t, n;
1346 1347 1348 1349
    step_workspace *ws;
    step *stp;
    bdescr *bd;

1350 1351 1352 1353 1354 1355 1356 1357 1358 1359
    // save the current mutable lists for this generation, and
    // allocate a fresh block for each one.  We'll traverse these
    // mutable lists as roots early on in the GC.
    generations[g].saved_mut_list = generations[g].mut_list;
    generations[g].mut_list = allocBlock(); 
    for (n = 0; n < n_capabilities; n++) {
        capabilities[n].saved_mut_lists[g] = capabilities[n].mut_lists[g];
        capabilities[n].mut_lists[g] = allocBlock();
    }

1360 1361 1362 1363 1364 1365
    for (s = 0; s < generations[g].n_steps; s++) {
	stp = &generations[g].steps[s];
	stp->scavenged_large_objects = NULL;
	stp->n_scavenged_large_blocks = 0;
    }
    
1366
    for (s = 0; s < generations[g].n_steps; s++) {
1367
	    
1368 1369 1370
        stp = &generations[g].steps[s];

        for (t = 0; t < threads; t++) {
1371
	    ws = &gc_threads[t]->steps[g * RtsFlags.GcFlags.steps + s];
1372
	    
1373
            ASSERT(looksEmptyWSDeque(ws->todo_q));
1374 1375
	    ws->todo_large_objects = NULL;

1376 1377 1378
            ws->part_list = NULL;
            ws->n_part_blocks = 0;

1379 1380 1381
	    ws->scavd_list = NULL;
	    ws->n_scavd_blocks = 0;

1382 1383
	    // If the block at the head of the list in this generation
	    // is less than 3/4 full, then use it as a todo block.