Scav.c 63.4 KB
Newer Older
1 2
/* -----------------------------------------------------------------------------
 *
3
 * (c) The GHC Team 1998-2008
4 5 6
 *
 * Generational garbage collector: scavenging functions
 *
7 8
 * Documentation on the architecture of the Garbage Collector can be
 * found in the online commentary:
9
 *
10
 *   https://gitlab.haskell.org/ghc/ghc/wikis/commentary/rts/storage/gc
11
 *
12 13
 * ---------------------------------------------------------------------------*/

14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
/* ----------------------------------------------------------------------------
   We have two main scavenge functions:

   - scavenge_block(bdescr *bd)
   - scavenge_one(StgPtr p)

   As the names and parameters suggest, first one scavenges a whole block while
   the second one only scavenges one object. This however is not the only
   difference. scavenge_block scavenges all SRTs while scavenge_one only
   scavenges SRTs of stacks. The reason is because scavenge_one is called in two
   cases:

   - When scavenging a mut_list
   - When scavenging a large object

   We don't have to scavenge SRTs when scavenging a mut_list, because we only
   scavenge mut_lists in minor GCs, and static objects are only collected in
   major GCs.

   However, because scavenge_one is also used to scavenge large objects (which
   are scavenged even in major GCs), we need to deal with SRTs of large
   objects. We never allocate large FUNs and THUNKs, but we allocate large
   STACKs (e.g. in threadStackOverflow), and stack frames can have SRTs. So
   scavenge_one skips FUN and THUNK SRTs but scavenges stack frame SRTs.

   In summary, in a major GC:

   - scavenge_block() scavenges all SRTs
   - scavenge_one() scavenges only stack frame SRTs
   ------------------------------------------------------------------------- */

Simon Marlow's avatar
Simon Marlow committed
45
#include "PosixSource.h"
46
#include "Rts.h"
Simon Marlow's avatar
Simon Marlow committed
47

48 49
#include "Storage.h"
#include "GC.h"
50
#include "GCThread.h"
51
#include "GCUtils.h"
52
#include "Compact.h"
53
#include "MarkStack.h"
54 55 56 57
#include "Evac.h"
#include "Scav.h"
#include "Apply.h"
#include "Trace.h"
58
#include "Sanity.h"
59
#include "Capability.h"
Simon Marlow's avatar
Simon Marlow committed
60
#include "LdvProfile.h"
61
#include "HeapUtils.h"
62
#include "Hash.h"
63

64
#include "sm/MarkWeak.h"
65 66
#include "sm/NonMoving.h" // for nonmoving_set_closure_mark_bit
#include "sm/NonMovingScav.h"
67

68 69 70
static void scavenge_large_bitmap (StgPtr p,
                                   StgLargeBitmap *large_bitmap,
                                   StgWord size );
71

72 73
#if defined(THREADED_RTS) && !defined(PARALLEL_GC)
# define evacuate(a) evacuate1(a)
74
# define evacuate_BLACKHOLE(a) evacuate_BLACKHOLE1(a)
75
# define scavenge_loop(a) scavenge_loop1(a)
76
# define scavenge_block(a) scavenge_block1(a)
77 78
# define scavenge_mutable_list(bd,g) scavenge_mutable_list1(bd,g)
# define scavenge_capability_mut_lists(cap) scavenge_capability_mut_Lists1(cap)
79 80 81 82 83 84 85 86
# define scavengeTSO(tso) scavengeTSO1(tso)
# define scavenge_stack(p, stack_end) scavenge_stack1(p, stack_end)
# define scavenge_fun_srt(info) scavenge_fun_srt1(info)
# define scavenge_fun_srt(info) scavenge_fun_srt1(info)
# define scavenge_thunk_srt(info) scavenge_thunk_srt1(info)
# define scavenge_mut_arr_ptrs(info) scavenge_mut_arr_ptrs1(info)
# define scavenge_PAP(pap) scavenge_PAP1(pap)
# define scavenge_AP(ap) scavenge_AP1(ap)
87
# define scavenge_compact(str) scavenge_compact1(str)
88 89
#endif

90 91 92 93 94
static void do_evacuate(StgClosure **p, void *user STG_UNUSED)
{
    evacuate(p);
}

95 96 97 98
/* -----------------------------------------------------------------------------
   Scavenge a TSO.
   -------------------------------------------------------------------------- */

99
void
100 101
scavengeTSO (StgTSO *tso)
{
Ben Gamari's avatar
Ben Gamari committed
102
    bool saved_eager;
103

Simon Marlow's avatar
Simon Marlow committed
104
    debugTrace(DEBUG_gc,"scavenging thread %d",(int)tso->id);
105

Simon Marlow's avatar
Simon Marlow committed
106
    // update the pointer from the InCall.
107
    if (tso->bound != NULL) {
Simon Marlow's avatar
Simon Marlow committed
108 109 110 111 112 113
        // NB. We can't just set tso->bound->tso = tso, because this
        // might be an invalid copy the TSO resulting from multiple
        // threads evacuating the TSO simultaneously (see
        // Evac.c:copy_tag()).  Calling evacuate() on this pointer
        // will ensure that we update it to point to the correct copy.
        evacuate((StgClosure **)&tso->bound->tso);
114 115
    }

116
    saved_eager = gct->eager_promotion;
Ben Gamari's avatar
Ben Gamari committed
117
    gct->eager_promotion = false;
simonmar@microsoft.com's avatar
simonmar@microsoft.com committed
118

119 120
    evacuate((StgClosure **)&tso->blocked_exceptions);
    evacuate((StgClosure **)&tso->bq);
121

122 123 124
    // scavange current transaction record
    evacuate((StgClosure **)&tso->trec);

125
    evacuate((StgClosure **)&tso->stackobj);
126 127

    evacuate((StgClosure **)&tso->_link);
128
    if (   tso->why_blocked == BlockedOnMVar
129
        || tso->why_blocked == BlockedOnMVarRead
130 131
        || tso->why_blocked == BlockedOnBlackHole
        || tso->why_blocked == BlockedOnMsgThrowTo
132
        || tso->why_blocked == BlockedOnIOCompletion
133
        || tso->why_blocked == NotBlocked
134 135
        ) {
        evacuate(&tso->block_info.closure);
136
    }
Ben Gamari's avatar
Ben Gamari committed
137
#if defined(THREADED_RTS)
138 139 140 141 142 143 144 145 146
    // in the THREADED_RTS, block_info.closure must always point to a
    // valid closure, because we assume this in throwTo().  In the
    // non-threaded RTS it might be a FD (for
    // BlockedOnRead/BlockedOnWrite) or a time value (BlockedOnDelay)
    else {
        tso->block_info.closure = (StgClosure *)END_TSO_QUEUE;
    }
#endif

147
    tso->dirty = gct->failed_to_evac;
simonmar@microsoft.com's avatar
simonmar@microsoft.com committed
148 149

    gct->eager_promotion = saved_eager;
150 151
}

152 153 154 155
/* ----------------------------------------------------------------------------
   Scavenging compact objects
   ------------------------------------------------------------------------- */

156 157 158 159 160 161 162 163
typedef struct {
    // We must save gct when calling mapHashTable(), which is compiled
    // without GCThread.h and so uses a different calling convention.
    // See also GC.c:mark_root where we do a similar thing.
    gc_thread *saved_gct;
    HashTable *newHash;
} MapHashData;

164
static void
165
evacuate_hash_entry(MapHashData *dat, StgWord key, const void *value)
166 167
{
    StgClosure *p = (StgClosure*)key;
Ben Gamari's avatar
Ben Gamari committed
168
#if defined(THREADED_RTS)
169 170
    gc_thread *old_gct = gct;
#endif
171

172
    SET_GCT(dat->saved_gct);
173
    evacuate(&p);
174 175
    insertHashTable(dat->newHash, (StgWord)p, value);
    SET_GCT(old_gct);
176 177
}

178 179 180 181
/* Here we scavenge the sharing-preservation hash-table, which may contain keys
 * living in from-space.
 */
void
182 183 184 185 186 187 188
scavenge_compact(StgCompactNFData *str)
{
    bool saved_eager;
    saved_eager = gct->eager_promotion;
    gct->eager_promotion = false;

    if (str->hash) {
189 190
        MapHashData dat;
        dat.saved_gct = gct;
191
        HashTable *newHash = allocHashTable();
192 193
        dat.newHash = newHash;
        mapHashTable(str->hash, (void*)&dat, (MapHashFn)evacuate_hash_entry);
194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
        freeHashTable(str->hash, NULL);
        str->hash = newHash;
    }

    debugTrace(DEBUG_compact,
               "compact alive @%p, gen %d, %" FMT_Word " bytes",
               str, Bdescr((P_)str)->gen_no, str->totalW * sizeof(W_))

    gct->eager_promotion = saved_eager;
    if (gct->failed_to_evac) {
        ((StgClosure *)str)->header.info = &stg_COMPACT_NFDATA_DIRTY_info;
    } else {
        ((StgClosure *)str)->header.info = &stg_COMPACT_NFDATA_CLEAN_info;
    }
}

210 211 212 213
/* -----------------------------------------------------------------------------
   Mutable arrays of pointers
   -------------------------------------------------------------------------- */

214
StgPtr scavenge_mut_arr_ptrs (StgMutArrPtrs *a)
215
{
216
    W_ m;
Ben Gamari's avatar
Ben Gamari committed
217
    bool any_failed;
218 219
    StgPtr p, q;

Ben Gamari's avatar
Ben Gamari committed
220
    any_failed = false;
221 222 223 224 225 226 227 228
    p = (StgPtr)&a->payload[0];
    for (m = 0; (int)m < (int)mutArrPtrsCards(a->ptrs) - 1; m++)
    {
        q = p + (1 << MUT_ARR_PTRS_CARD_BITS);
        for (; p < q; p++) {
            evacuate((StgClosure**)p);
        }
        if (gct->failed_to_evac) {
Ben Gamari's avatar
Ben Gamari committed
229
            any_failed = true;
230
            *mutArrPtrsCard(a,m) = 1;
Ben Gamari's avatar
Ben Gamari committed
231
            gct->failed_to_evac = false;
232 233 234 235 236 237 238 239 240 241 242
        } else {
            *mutArrPtrsCard(a,m) = 0;
        }
    }

    q = (StgPtr)&a->payload[a->ptrs];
    if (p < q) {
        for (; p < q; p++) {
            evacuate((StgClosure**)p);
        }
        if (gct->failed_to_evac) {
Ben Gamari's avatar
Ben Gamari committed
243
            any_failed = true;
244
            *mutArrPtrsCard(a,m) = 1;
Ben Gamari's avatar
Ben Gamari committed
245
            gct->failed_to_evac = false;
246 247 248 249 250 251 252 253
        } else {
            *mutArrPtrsCard(a,m) = 0;
        }
    }

    gct->failed_to_evac = any_failed;
    return (StgPtr)a + mut_arr_ptrs_sizeW(a);
}
254

255 256 257
// scavenge only the marked areas of a MUT_ARR_PTRS
static StgPtr scavenge_mut_arr_ptrs_marked (StgMutArrPtrs *a)
{
258
    W_ m;
259
    StgPtr p, q;
Ben Gamari's avatar
Ben Gamari committed
260
    bool any_failed;
261

Ben Gamari's avatar
Ben Gamari committed
262
    any_failed = false;
263 264 265 266 267 268 269 270 271 272
    for (m = 0; m < mutArrPtrsCards(a->ptrs); m++)
    {
        if (*mutArrPtrsCard(a,m) != 0) {
            p = (StgPtr)&a->payload[m << MUT_ARR_PTRS_CARD_BITS];
            q = stg_min(p + (1 << MUT_ARR_PTRS_CARD_BITS),
                        (StgPtr)&a->payload[a->ptrs]);
            for (; p < q; p++) {
                evacuate((StgClosure**)p);
            }
            if (gct->failed_to_evac) {
Ben Gamari's avatar
Ben Gamari committed
273 274
                any_failed = true;
                gct->failed_to_evac = false;
275 276 277 278 279 280 281 282 283 284
            } else {
                *mutArrPtrsCard(a,m) = 0;
            }
        }
    }

    gct->failed_to_evac = any_failed;
    return (StgPtr)a + mut_arr_ptrs_sizeW(a);
}

285 286 287 288 289 290 291 292 293 294 295 296 297 298
STATIC_INLINE StgPtr
scavenge_small_bitmap (StgPtr p, StgWord size, StgWord bitmap)
{
    while (size > 0) {
        if ((bitmap & 1) == 0) {
            evacuate((StgClosure **)p);
        }
        p++;
        bitmap = bitmap >> 1;
        size--;
    }
    return p;
}

299 300 301 302 303 304
/* -----------------------------------------------------------------------------
   Blocks of function args occur on the stack (at the top) and
   in PAPs.
   -------------------------------------------------------------------------- */

STATIC_INLINE StgPtr
305
scavenge_arg_block (const StgFunInfoTable *fun_info, StgClosure **args)
306 307 308
{
    StgPtr p;
    StgWord bitmap;
309
    StgWord size;
310 311 312 313

    p = (StgPtr)args;
    switch (fun_info->f.fun_type) {
    case ARG_GEN:
314 315 316
        bitmap = BITMAP_BITS(fun_info->f.b.bitmap);
        size = BITMAP_SIZE(fun_info->f.b.bitmap);
        goto small_bitmap;
317
    case ARG_GEN_BIG:
318 319 320 321
        size = GET_FUN_LARGE_BITMAP(fun_info)->size;
        scavenge_large_bitmap(p, GET_FUN_LARGE_BITMAP(fun_info), size);
        p += size;
        break;
322
    default:
323 324
        bitmap = BITMAP_BITS(stg_arg_bitmaps[fun_info->f.fun_type]);
        size = BITMAP_SIZE(stg_arg_bitmaps[fun_info->f.fun_type]);
325
    small_bitmap:
326
        p = scavenge_small_bitmap(p, size, bitmap);
327
        break;
328 329 330 331
    }
    return p;
}

Simon Marlow's avatar
Simon Marlow committed
332
STATIC_INLINE GNUC_ATTR_HOT StgPtr
333 334 335 336
scavenge_PAP_payload (StgClosure *fun, StgClosure **payload, StgWord size)
{
    StgPtr p;
    StgWord bitmap;
337
    const StgFunInfoTable *fun_info;
338

339
    fun_info = get_fun_itbl(UNTAG_CONST_CLOSURE(fun));
340 341 342 343 344
    ASSERT(fun_info->i.type != PAP);
    p = (StgPtr)payload;

    switch (fun_info->f.fun_type) {
    case ARG_GEN:
345 346
        bitmap = BITMAP_BITS(fun_info->f.b.bitmap);
        goto small_bitmap;
347
    case ARG_GEN_BIG:
348 349 350
        scavenge_large_bitmap(p, GET_FUN_LARGE_BITMAP(fun_info), size);
        p += size;
        break;
351
    case ARG_BCO:
352 353 354
        scavenge_large_bitmap((StgPtr)payload, BCO_BITMAP(fun), size);
        p += size;
        break;
355
    default:
356
        bitmap = BITMAP_BITS(stg_arg_bitmaps[fun_info->f.fun_type]);
357
    small_bitmap:
358
        p = scavenge_small_bitmap(p, size, bitmap);
359
        break;
360 361 362 363
    }
    return p;
}

364
GNUC_ATTR_HOT StgPtr
365 366
scavenge_PAP (StgPAP *pap)
{
367
    evacuate(&pap->fun);
368 369 370
    return scavenge_PAP_payload (pap->fun, pap->payload, pap->n_args);
}

371
StgPtr
372 373
scavenge_AP (StgAP *ap)
{
374
    evacuate(&ap->fun);
375 376 377
    return scavenge_PAP_payload (ap->fun, ap->payload, ap->n_args);
}

378 379 380 381
/* -----------------------------------------------------------------------------
   Scavenge SRTs
   -------------------------------------------------------------------------- */

382
GNUC_ATTR_HOT void
383 384 385 386 387 388 389
scavenge_thunk_srt(const StgInfoTable *info)
{
    StgThunkInfoTable *thunk_info;

    if (!major_gc) return;

    thunk_info = itbl_to_thunk_itbl(info);
390
    if (thunk_info->i.srt) {
391 392
        StgClosure *srt = (StgClosure*)GET_SRT(thunk_info);
        evacuate(&srt);
393
    }
394 395
}

396
GNUC_ATTR_HOT void
397 398 399 400 401
scavenge_fun_srt(const StgInfoTable *info)
{
    StgFunInfoTable *fun_info;

    if (!major_gc) return;
402

403
    fun_info = itbl_to_fun_itbl(info);
404
    if (fun_info->i.srt) {
405 406
        StgClosure *srt = (StgClosure*)GET_FUN_SRT(fun_info);
        evacuate(&srt);
407
    }
408 409 410 411 412
}

/* -----------------------------------------------------------------------------
   Scavenge a block from the given scan pointer up to bd->free.

Simon Marlow's avatar
Simon Marlow committed
413
   evac_gen_no is set by the caller to be either zero (for a step in a
414
   generation < N) or G where G is the generation of the step being
415
   scavenged.
416

Simon Marlow's avatar
Simon Marlow committed
417
   We sometimes temporarily change evac_gen_no back to zero if we're
418
   scavenging a mutable object where eager promotion isn't such a good
419
   idea.
420 421
   -------------------------------------------------------------------------- */

Simon Marlow's avatar
Simon Marlow committed
422
static GNUC_ATTR_HOT void
423 424 425
scavenge_block (bdescr *bd)
{
  StgPtr p, q;
426
  const StgInfoTable *info;
Ben Gamari's avatar
Ben Gamari committed
427
  bool saved_eager_promotion;
428
  gen_workspace *ws;
429

430
  debugTrace(DEBUG_gc, "scavenging block %p (gen %d) @ %p",
431
             bd->start, bd->gen_no, bd->u.scan);
432 433

  gct->scan_bd = bd;
Simon Marlow's avatar
Simon Marlow committed
434
  gct->evac_gen_no = bd->gen_no;
435
  saved_eager_promotion = gct->eager_promotion;
Ben Gamari's avatar
Ben Gamari committed
436
  gct->failed_to_evac = false;
437

438
  ws = &gct->gens[bd->gen->no];
439 440

  p = bd->u.scan;
441

442 443 444 445 446
  // we might be evacuating into the very object that we're
  // scavenging, so we have to check the real bd->free pointer each
  // time around the loop.
  while (p < bd->free || (bd == ws->todo_bd && p < ws->todo_free)) {

447
    ASSERT(bd->link == NULL);
448 449
    ASSERT(LOOKS_LIKE_CLOSURE_PTR(p));
    info = get_itbl((StgClosure *)p);
450

451 452 453 454 455 456 457
    ASSERT(gct->thunk_selector_depth == 0);

    q = p;
    switch (info->type) {

    case MVAR_CLEAN:
    case MVAR_DIRTY:
458 459
    {
        StgMVar *mvar = ((StgMVar *)p);
Ben Gamari's avatar
Ben Gamari committed
460
        gct->eager_promotion = false;
461 462 463 464 465 466 467 468 469 470 471 472
        evacuate((StgClosure **)&mvar->head);
        evacuate((StgClosure **)&mvar->tail);
        evacuate((StgClosure **)&mvar->value);
        gct->eager_promotion = saved_eager_promotion;

        if (gct->failed_to_evac) {
            mvar->header.info = &stg_MVAR_DIRTY_info;
        } else {
            mvar->header.info = &stg_MVAR_CLEAN_info;
        }
        p += sizeofW(StgMVar);
        break;
473 474
    }

475 476
    case TVAR:
    {
477
        StgTVar *tvar = ((StgTVar *)p);
Ben Gamari's avatar
Ben Gamari committed
478
        gct->eager_promotion = false;
479 480
        evacuate((StgClosure **)&tvar->current_value);
        evacuate((StgClosure **)&tvar->first_watch_queue_entry);
481 482 483 484 485 486 487 488 489
        gct->eager_promotion = saved_eager_promotion;

        if (gct->failed_to_evac) {
            tvar->header.info = &stg_TVAR_DIRTY_info;
        } else {
            tvar->header.info = &stg_TVAR_CLEAN_info;
        }
        p += sizeofW(StgTVar);
        break;
490 491
    }

492
    case FUN_2_0:
493 494 495 496 497
        scavenge_fun_srt(info);
        evacuate(&((StgClosure *)p)->payload[1]);
        evacuate(&((StgClosure *)p)->payload[0]);
        p += sizeofW(StgHeader) + 2;
        break;
498 499

    case THUNK_2_0:
500 501 502 503 504
        scavenge_thunk_srt(info);
        evacuate(&((StgThunk *)p)->payload[1]);
        evacuate(&((StgThunk *)p)->payload[0]);
        p += sizeofW(StgThunk) + 2;
        break;
505 506

    case CONSTR_2_0:
507 508 509 510 511
        evacuate(&((StgClosure *)p)->payload[1]);
        evacuate(&((StgClosure *)p)->payload[0]);
        p += sizeofW(StgHeader) + 2;
        break;

512
    case THUNK_1_0:
513 514 515 516 517
        scavenge_thunk_srt(info);
        evacuate(&((StgThunk *)p)->payload[0]);
        p += sizeofW(StgThunk) + 1;
        break;

518
    case FUN_1_0:
519
        scavenge_fun_srt(info);
Ben Gamari's avatar
Ben Gamari committed
520
        FALLTHROUGH;
521
    case CONSTR_1_0:
522 523 524 525
        evacuate(&((StgClosure *)p)->payload[0]);
        p += sizeofW(StgHeader) + 1;
        break;

526
    case THUNK_0_1:
527 528 529 530
        scavenge_thunk_srt(info);
        p += sizeofW(StgThunk) + 1;
        break;

531
    case FUN_0_1:
532
        scavenge_fun_srt(info);
Ben Gamari's avatar
Ben Gamari committed
533
        FALLTHROUGH;
534
    case CONSTR_0_1:
535 536 537
        p += sizeofW(StgHeader) + 1;
        break;

538
    case THUNK_0_2:
539 540 541 542
        scavenge_thunk_srt(info);
        p += sizeofW(StgThunk) + 2;
        break;

543
    case FUN_0_2:
544
        scavenge_fun_srt(info);
Ben Gamari's avatar
Ben Gamari committed
545
        FALLTHROUGH;
546
    case CONSTR_0_2:
547 548 549
        p += sizeofW(StgHeader) + 2;
        break;

550
    case THUNK_1_1:
551 552 553 554
        scavenge_thunk_srt(info);
        evacuate(&((StgThunk *)p)->payload[0]);
        p += sizeofW(StgThunk) + 2;
        break;
555 556

    case FUN_1_1:
557
        scavenge_fun_srt(info);
Ben Gamari's avatar
Ben Gamari committed
558
        FALLTHROUGH;
559
    case CONSTR_1_1:
560 561 562 563
        evacuate(&((StgClosure *)p)->payload[0]);
        p += sizeofW(StgHeader) + 2;
        break;

564
    case FUN:
565 566
        scavenge_fun_srt(info);
        goto gen_obj;
567 568 569

    case THUNK:
    {
570 571 572 573 574 575 576 577 578
        StgPtr end;

        scavenge_thunk_srt(info);
        end = (P_)((StgThunk *)p)->payload + info->layout.payload.ptrs;
        for (p = (P_)((StgThunk *)p)->payload; p < end; p++) {
            evacuate((StgClosure **)p);
        }
        p += info->layout.payload.nptrs;
        break;
579
    }
580

581 582
    gen_obj:
    case CONSTR:
Simon Marlow's avatar
Simon Marlow committed
583
    case CONSTR_NOCAF:
584
    case WEAK:
585
    case PRIM:
586
    {
587 588 589 590 591 592 593 594
        StgPtr end;

        end = (P_)((StgClosure *)p)->payload + info->layout.payload.ptrs;
        for (p = (P_)((StgClosure *)p)->payload; p < end; p++) {
            evacuate((StgClosure **)p);
        }
        p += info->layout.payload.nptrs;
        break;
595 596 597
    }

    case BCO: {
598 599 600 601 602 603
        StgBCO *bco = (StgBCO *)p;
        evacuate((StgClosure **)&bco->instrs);
        evacuate((StgClosure **)&bco->literals);
        evacuate((StgClosure **)&bco->ptrs);
        p += bco_sizeW(bco);
        break;
604 605
    }

606
    case BLACKHOLE:
607 608 609
        evacuate(&((StgInd *)p)->indirectee);
        p += sizeofW(StgInd);
        break;
610 611 612

    case MUT_VAR_CLEAN:
    case MUT_VAR_DIRTY:
Ben Gamari's avatar
Ben Gamari committed
613
        gct->eager_promotion = false;
614 615 616 617 618 619 620 621 622 623
        evacuate(&((StgMutVar *)p)->var);
        gct->eager_promotion = saved_eager_promotion;

        if (gct->failed_to_evac) {
            ((StgClosure *)q)->header.info = &stg_MUT_VAR_DIRTY_info;
        } else {
            ((StgClosure *)q)->header.info = &stg_MUT_VAR_CLEAN_info;
        }
        p += sizeofW(StgMutVar);
        break;
624

625 626 627
    case BLOCKING_QUEUE:
    {
        StgBlockingQueue *bq = (StgBlockingQueue *)p;
628

Ben Gamari's avatar
Ben Gamari committed
629
        gct->eager_promotion = false;
630 631 632 633
        evacuate(&bq->bh);
        evacuate((StgClosure**)&bq->owner);
        evacuate((StgClosure**)&bq->queue);
        evacuate((StgClosure**)&bq->link);
634
        gct->eager_promotion = saved_eager_promotion;
635

636 637 638 639 640
        if (gct->failed_to_evac) {
            bq->header.info = &stg_BLOCKING_QUEUE_DIRTY_info;
        } else {
            bq->header.info = &stg_BLOCKING_QUEUE_CLEAN_info;
        }
641 642 643
        p += sizeofW(StgBlockingQueue);
        break;
    }
644 645

    case THUNK_SELECTOR:
646 647 648 649 650
    {
        StgSelector *s = (StgSelector *)p;
        evacuate(&s->selectee);
        p += THUNK_SELECTOR_sizeW();
        break;
651 652 653 654 655
    }

    // A chunk of stack saved in a heap object
    case AP_STACK:
    {
656
        StgAP_STACK *ap = (StgAP_STACK *)p;
657

658 659 660 661
        evacuate(&ap->fun);
        scavenge_stack((StgPtr)ap->payload, (StgPtr)ap->payload + ap->size);
        p = (StgPtr)ap->payload + ap->size;
        break;
662 663 664
    }

    case PAP:
665 666
        p = scavenge_PAP((StgPAP *)p);
        break;
667 668

    case AP:
669 670
        p = scavenge_AP((StgAP *)p);
        break;
671 672

    case ARR_WORDS:
673
        // nothing to follow
siddhanathan's avatar
siddhanathan committed
674
        p += arr_words_sizeW((StgArrBytes *)p);
675
        break;
676 677 678 679

    case MUT_ARR_PTRS_CLEAN:
    case MUT_ARR_PTRS_DIRTY:
    {
680 681 682 683
        // We don't eagerly promote objects pointed to by a mutable
        // array, but if we find the array only points to objects in
        // the same or an older generation, we mark it "clean" and
        // avoid traversing it during minor GCs.
Ben Gamari's avatar
Ben Gamari committed
684
        gct->eager_promotion = false;
685

686
        p = scavenge_mut_arr_ptrs((StgMutArrPtrs*)p);
687

688 689 690 691 692
        if (gct->failed_to_evac) {
            ((StgClosure *)q)->header.info = &stg_MUT_ARR_PTRS_DIRTY_info;
        } else {
            ((StgClosure *)q)->header.info = &stg_MUT_ARR_PTRS_CLEAN_info;
        }
693

694
        gct->eager_promotion = saved_eager_promotion;
Ben Gamari's avatar
Ben Gamari committed
695
        gct->failed_to_evac = true; // always put it on the mutable list.
696
        break;
697 698
    }

699 700
    case MUT_ARR_PTRS_FROZEN_CLEAN:
    case MUT_ARR_PTRS_FROZEN_DIRTY:
701
        // follow everything
702
    {
703
        p = scavenge_mut_arr_ptrs((StgMutArrPtrs*)p);
704

705
        if (gct->failed_to_evac) {
706
            ((StgClosure *)q)->header.info = &stg_MUT_ARR_PTRS_FROZEN_DIRTY_info;
707
        } else {
708
            ((StgClosure *)q)->header.info = &stg_MUT_ARR_PTRS_FROZEN_CLEAN_info;
709 710
        }
        break;
711 712
    }

713 714 715 716 717 718 719 720 721 722
    case SMALL_MUT_ARR_PTRS_CLEAN:
    case SMALL_MUT_ARR_PTRS_DIRTY:
        // follow everything
    {
        StgPtr next;

        // We don't eagerly promote objects pointed to by a mutable
        // array, but if we find the array only points to objects in
        // the same or an older generation, we mark it "clean" and
        // avoid traversing it during minor GCs.
Ben Gamari's avatar
Ben Gamari committed
723
        gct->eager_promotion = false;
724 725 726 727 728 729 730 731 732 733 734 735
        next = p + small_mut_arr_ptrs_sizeW((StgSmallMutArrPtrs*)p);
        for (p = (P_)((StgSmallMutArrPtrs *)p)->payload; p < next; p++) {
            evacuate((StgClosure **)p);
        }
        gct->eager_promotion = saved_eager_promotion;

        if (gct->failed_to_evac) {
            ((StgClosure *)q)->header.info = &stg_SMALL_MUT_ARR_PTRS_DIRTY_info;
        } else {
            ((StgClosure *)q)->header.info = &stg_SMALL_MUT_ARR_PTRS_CLEAN_info;
        }

Ben Gamari's avatar
Ben Gamari committed
736
        gct->failed_to_evac = true; // always put it on the mutable list.
737 738 739
        break;
    }

740 741
    case SMALL_MUT_ARR_PTRS_FROZEN_CLEAN:
    case SMALL_MUT_ARR_PTRS_FROZEN_DIRTY:
742 743 744 745 746 747 748 749 750 751
        // follow everything
    {
        StgPtr next;

        next = p + small_mut_arr_ptrs_sizeW((StgSmallMutArrPtrs*)p);
        for (p = (P_)((StgSmallMutArrPtrs *)p)->payload; p < next; p++) {
            evacuate((StgClosure **)p);
        }

        if (gct->failed_to_evac) {
752
            ((StgClosure *)q)->header.info = &stg_SMALL_MUT_ARR_PTRS_FROZEN_DIRTY_info;
753
        } else {
754
            ((StgClosure *)q)->header.info = &stg_SMALL_MUT_ARR_PTRS_FROZEN_CLEAN_info;
755 756 757 758
        }
        break;
    }

759
    case TSO:
760
    {
761 762
        scavengeTSO((StgTSO *)p);
        p += sizeofW(StgTSO);
763
        break;
764 765
    }

766 767 768 769
    case STACK:
    {
        StgStack *stack = (StgStack*)p;

Ben Gamari's avatar
Ben Gamari committed
770
        gct->eager_promotion = false;
771 772 773 774 775 776 777 778 779

        scavenge_stack(stack->sp, stack->stack + stack->stack_size);
        stack->dirty = gct->failed_to_evac;
        p += stack_sizeW(stack);

        gct->eager_promotion = saved_eager_promotion;
        break;
    }

780
    case MUT_PRIM:
781
      {
782
        StgPtr end;
783

Ben Gamari's avatar
Ben Gamari committed
784
        gct->eager_promotion = false;
785

786 787 788 789 790
        end = (P_)((StgClosure *)p)->payload + info->layout.payload.ptrs;
        for (p = (P_)((StgClosure *)p)->payload; p < end; p++) {
            evacuate((StgClosure **)p);
        }
        p += info->layout.payload.nptrs;
791

792
        gct->eager_promotion = saved_eager_promotion;
Ben Gamari's avatar
Ben Gamari committed
793
        gct->failed_to_evac = true; // mutable
794
        break;
795 796 797 798
      }

    case TREC_CHUNK:
      {
799 800 801
        StgWord i;
        StgTRecChunk *tc = ((StgTRecChunk *) p);
        TRecEntry *e = &(tc -> entries[0]);
Ben Gamari's avatar
Ben Gamari committed
802
        gct->eager_promotion = false;
803 804 805 806 807 808 809
        evacuate((StgClosure **)&tc->prev_chunk);
        for (i = 0; i < tc -> next_entry_idx; i ++, e++ ) {
          evacuate((StgClosure **)&e->tvar);
          evacuate((StgClosure **)&e->expected_value);
          evacuate((StgClosure **)&e->new_value);
        }
        gct->eager_promotion = saved_eager_promotion;
Ben Gamari's avatar
Ben Gamari committed
810
        gct->failed_to_evac = true; // mutable
811 812
        p += sizeofW(StgTRecChunk);
        break;
813 814 815
      }

    default:
816 817
        barf("scavenge: unimplemented/strange closure type %d @ %p",
             info->type, p);
818 819 820 821
    }

    /*
     * We need to record the current object on the mutable list if
822
     *  (a) It is actually mutable, or
823 824 825 826 827
     *  (b) It contains pointers to a younger generation.
     * Case (b) arises if we didn't manage to promote everything that
     * the current object points to into the current generation.
     */
    if (gct->failed_to_evac) {
Ben Gamari's avatar
Ben Gamari committed
828
        gct->failed_to_evac = false;
829 830 831
        if (bd->gen_no > 0) {
            recordMutableGen_GC((StgClosure *)q, bd->gen_no);
        }
832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854
    }
  }

  if (p > bd->free)  {
      gct->copied += ws->todo_free - bd->free;
      bd->free = p;
  }

  debugTrace(DEBUG_gc, "   scavenged %ld bytes",
             (unsigned long)((bd->free - bd->u.scan) * sizeof(W_)));

  // update stats: this is a block that has been scavenged
  gct->scanned += bd->free - bd->u.scan;
  bd->u.scan = bd->free;

  if (bd != ws->todo_bd) {
      // we're not going to evac any more objects into
      // this block, so push it now.
      push_scanned_block(bd, ws);
  }

  gct->scan_bd = NULL;
}
855 856 857 858 859 860 861 862
/* -----------------------------------------------------------------------------
   Scavenge everything on the mark stack.

   This is slightly different from scavenge():
      - we don't walk linearly through the objects, so the scavenger
        doesn't need to advance the pointer on to the next object.
   -------------------------------------------------------------------------- */

863
static void
864 865 866
scavenge_mark_stack(void)
{
    StgPtr p, q;
867
    const StgInfoTable *info;
Ben Gamari's avatar
Ben Gamari committed
868
    bool saved_eager_promotion;
869

Simon Marlow's avatar
Simon Marlow committed
870
    gct->evac_gen_no = oldest_gen->no;
871
    saved_eager_promotion = gct->eager_promotion;
872

873
    while ((p = pop_mark_stack())) {
874

875 876 877 878
        ASSERT(LOOKS_LIKE_CLOSURE_PTR(p));
        info = get_itbl((StgClosure *)p);

        q = p;
879
        switch (info->type) {
880

881 882
        case MVAR_CLEAN:
        case MVAR_DIRTY:
883
        {
884
            StgMVar *mvar = ((StgMVar *)p);
Ben Gamari's avatar
Ben Gamari committed
885
            gct->eager_promotion = false;
886 887 888
            evacuate((StgClosure **)&mvar->head);
            evacuate((StgClosure **)&mvar->tail);
            evacuate((StgClosure **)&mvar->value);
889
            gct->eager_promotion = saved_eager_promotion;
890

891
            if (gct->failed_to_evac) {
892 893 894 895 896 897
                mvar->header.info = &stg_MVAR_DIRTY_info;
            } else {
                mvar->header.info = &stg_MVAR_CLEAN_info;
            }
            break;
        }
898

899 900 901
        case TVAR:
        {
            StgTVar *tvar = ((StgTVar *)p);
Ben Gamari's avatar
Ben Gamari committed
902
            gct->eager_promotion = false;
903 904 905 906 907 908 909 910 911 912 913 914
            evacuate((StgClosure **)&tvar->current_value);
            evacuate((StgClosure **)&tvar->first_watch_queue_entry);
            gct->eager_promotion = saved_eager_promotion;

            if (gct->failed_to_evac) {
                tvar->header.info = &stg_TVAR_DIRTY_info;
            } else {
                tvar->header.info = &stg_TVAR_CLEAN_info;
            }
            break;
        }

915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980
        case FUN_2_0:
            scavenge_fun_srt(info);
            evacuate(&((StgClosure *)p)->payload[1]);
            evacuate(&((StgClosure *)p)->payload[0]);
            break;

        case THUNK_2_0:
            scavenge_thunk_srt(info);
            evacuate(&((StgThunk *)p)->payload[1]);
            evacuate(&((StgThunk *)p)->payload[0]);
            break;

        case CONSTR_2_0:
            evacuate(&((StgClosure *)p)->payload[1]);
            evacuate(&((StgClosure *)p)->payload[0]);
            break;

        case FUN_1_0:
        case FUN_1_1:
            scavenge_fun_srt(info);
            evacuate(&((StgClosure *)p)->payload[0]);
            break;

        case THUNK_1_0:
        case THUNK_1_1:
            scavenge_thunk_srt(info);
            evacuate(&((StgThunk *)p)->payload[0]);
            break;

        case CONSTR_1_0:
        case CONSTR_1_1:
            evacuate(&((StgClosure *)p)->payload[0]);
            break;

        case FUN_0_1:
        case FUN_0_2:
            scavenge_fun_srt(info);
            break;

        case THUNK_0_1:
        case THUNK_0_2:
            scavenge_thunk_srt(info);
            break;

        case CONSTR_0_1:
        case CONSTR_0_2:
            break;

        case FUN:
            scavenge_fun_srt(info);
            goto gen_obj;

        case THUNK:
        {
            StgPtr end;

            scavenge_thunk_srt(info);
            end = (P_)((StgThunk *)p)->payload + info->layout.payload.ptrs;
            for (p = (P_)((StgThunk *)p)->payload; p < end; p++) {
                evacuate((StgClosure **)p);
            }
            break;
        }

        gen_obj:
        case CONSTR:
Simon Marlow's avatar
Simon Marlow committed
981
        case CONSTR_NOCAF:
982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002
        case WEAK:
        case PRIM:
        {
            StgPtr end;

            end = (P_)((StgClosure *)p)->payload + info->layout.payload.ptrs;
            for (p = (P_)((StgClosure *)p)->payload; p < end; p++) {
                evacuate((StgClosure **)p);
            }
            break;
        }

        case BCO: {
            StgBCO *bco = (StgBCO *)p;
            evacuate((StgClosure **)&bco->instrs);
            evacuate((StgClosure **)&bco->literals);
            evacuate((StgClosure **)&bco->ptrs);
            break;
        }

        case IND:
1003
        case BLACKHOLE:
1004 1005 1006 1007 1008
            evacuate(&((StgInd *)p)->indirectee);
            break;

        case MUT_VAR_CLEAN:
        case MUT_VAR_DIRTY: {
Ben Gamari's avatar
Ben Gamari committed
1009
            gct->eager_promotion = false;
1010 1011 1012 1013 1014 1015 1016 1017 1018 1019
            evacuate(&((StgMutVar *)p)->var);
            gct->eager_promotion = saved_eager_promotion;

            if (gct->failed_to_evac) {
                ((StgClosure *)q)->header.info = &stg_MUT_VAR_DIRTY_info;
            } else {
                ((StgClosure *)q)->header.info = &stg_MUT_VAR_CLEAN_info;
            }
            break;
        }
1020

1021 1022 1023
        case BLOCKING_QUEUE:
        {
            StgBlockingQueue *bq = (StgBlockingQueue *)p;
1024

Ben Gamari's avatar
Ben Gamari committed
1025
            gct->eager_promotion = false;
1026 1027 1028 1029 1030
            evacuate(&bq->bh);
            evacuate((StgClosure**)&bq->owner);
            evacuate((StgClosure**)&bq->queue);
            evacuate((StgClosure**)&bq->link);
            gct->eager_promotion = saved_eager_promotion;
1031

1032 1033 1034 1035 1036 1037 1038 1039
            if (gct->failed_to_evac) {
                bq->header.info = &stg_BLOCKING_QUEUE_DIRTY_info;
            } else {
                bq->header.info = &stg_BLOCKING_QUEUE_CLEAN_info;
            }
            break;
        }

1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075
        case ARR_WORDS:
            break;

        case THUNK_SELECTOR:
        {
            StgSelector *s = (StgSelector *)p;
            evacuate(&s->selectee);
            break;
        }

        // A chunk of stack saved in a heap object
        case AP_STACK:
        {
            StgAP_STACK *ap = (StgAP_STACK *)p;

            evacuate(&ap->fun);
            scavenge_stack((StgPtr)ap->payload, (StgPtr)ap->payload + ap->size);
            break;
        }

        case PAP:
            scavenge_PAP((StgPAP *)p);
            break;

        case AP:
            scavenge_AP((StgAP *)p);
            break;

        case MUT_ARR_PTRS_CLEAN:
        case MUT_ARR_PTRS_DIRTY:
            // follow everything
        {
            // We don't eagerly promote objects pointed to by a mutable
            // array, but if we find the array only points to objects in
            // the same or an older generation, we mark it "clean" and
            // avoid traversing it during minor GCs.
Ben Gamari's avatar
Ben Gamari committed
1076
            gct->eager_promotion = false;
1077

1078 1079 1080 1081 1082 1083 1084
            scavenge_mut_arr_ptrs((StgMutArrPtrs *)p);

            if (gct->failed_to_evac) {
                ((StgClosure *)q)->header.info = &stg_MUT_ARR_PTRS_DIRTY_info;
            } else {
                ((StgClosure *)q)->header.info = &stg_MUT_ARR_PTRS_CLEAN_info;
            }
1085

1086
            gct->eager_promotion = saved_eager_promotion;
Ben Gamari's avatar
Ben Gamari committed
1087
            gct->failed_to_evac = true; // mutable anyhow.
1088 1089 1090
            break;
        }

1091 1092
        case MUT_ARR_PTRS_FROZEN_CLEAN:
        case MUT_ARR_PTRS_FROZEN_DIRTY:
1093 1094 1095 1096
            // follow everything
        {
            StgPtr q = p;

1097
            scavenge_mut_arr_ptrs((StgMutArrPtrs *)p);
1098

1099
            if (gct->failed_to_evac) {
1100
                ((StgClosure *)q)->header.info = &stg_MUT_ARR_PTRS_FROZEN_DIRTY_info;
1101
            } else {
1102
                ((StgClosure *)q)->header.info = &stg_MUT_ARR_PTRS_FROZEN_CLEAN_info;
1103 1104 1105
            }
            break;
        }
1106

1107 1108 1109 1110 1111
        case SMALL_MUT_ARR_PTRS_CLEAN:
        case SMALL_MUT_ARR_PTRS_DIRTY:
            // follow everything
        {
            StgPtr next;
Ben Gamari's avatar
Ben Gamari committed
1112
            bool saved_eager;
1113 1114 1115 1116 1117 1118

            // We don't eagerly promote objects pointed to by a mutable
            // array, but if we find the array only points to objects in
            // the same or an older generation, we mark it "clean" and
            // avoid traversing it during minor GCs.
            saved_eager = gct->eager_promotion;
Ben Gamari's avatar
Ben Gamari committed
1119
            gct->eager_promotion = false;
1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131
            next = p + small_mut_arr_ptrs_sizeW((StgSmallMutArrPtrs*)p);
            for (p = (P_)((StgSmallMutArrPtrs *)p)->payload; p < next; p++) {
                evacuate((StgClosure **)p);
            }
            gct->eager_promotion = saved_eager;

            if (gct->failed_to_evac) {
                ((StgClosure *)q)->header.info = &stg_SMALL_MUT_ARR_PTRS_DIRTY_info;
            } else {
                ((StgClosure *)q)->header.info = &stg_SMALL_MUT_ARR_PTRS_CLEAN_info;
            }

Ben Gamari's avatar
Ben Gamari committed
1132
            gct->failed_to_evac = true; // mutable anyhow.
1133 1134 1135
            break;
        }

1136 1137
        case SMALL_MUT_ARR_PTRS_FROZEN_CLEAN:
        case SMALL_MUT_ARR_PTRS_FROZEN_DIRTY:
1138 1139 1140
            // follow everything
        {
            StgPtr next, q = p;
1141

1142 1143 1144 1145 1146 1147
            next = p + small_mut_arr_ptrs_sizeW((StgSmallMutArrPtrs*)p);
            for (p = (P_)((StgSmallMutArrPtrs *)p)->payload; p < next; p++) {
                evacuate((StgClosure **)p);
            }

            if (gct->failed_to_evac) {
1148
                ((StgClosure *)q)->header.info = &stg_SMALL_MUT_ARR_PTRS_FROZEN_DIRTY_info;
1149
            } else {
1150
                ((StgClosure *)q)->header.info = &stg_SMALL_MUT_ARR_PTRS_FROZEN_CLEAN_info;
1151 1152 1153 1154
            }
            break;
        }

1155 1156
        case TSO:
        {
simonmar@microsoft.com's avatar
simonmar@microsoft.com committed
1157
            scavengeTSO((StgTSO*)p);
1158 1159
            break;
        }
1160

1161 1162 1163 1164
        case STACK:
        {
            StgStack *stack = (StgStack*)p;

Ben Gamari's avatar
Ben Gamari committed
1165
            gct->eager_promotion = false;
1166 1167 1168 1169 1170 1171 1172 1173

            scavenge_stack(stack->sp, stack->stack + stack->stack_size);
            stack->dirty = gct->failed_to_evac;

            gct->eager_promotion = saved_eager_promotion;
            break;
        }

1174 1175 1176
        case MUT_PRIM:
        {
            StgPtr end;
1177

Ben Gamari's avatar
Ben Gamari committed
1178
            gct->eager_promotion = false;
1179

1180 1181 1182 1183
            end = (P_)((StgClosure *)p)->payload + info->layout.payload.ptrs;
            for (p = (P_)((StgClosure *)p)->payload; p < end; p++) {
                evacuate((StgClosure **)p);
            }
1184 1185

            gct->eager_promotion = saved_eager_promotion;
Ben Gamari's avatar
Ben Gamari committed
1186
            gct->failed_to_evac = true; // mutable
1187 1188 1189 1190 1191 1192 1193 1194
            break;
        }

        case TREC_CHUNK:
          {
            StgWord i;
            StgTRecChunk *tc = ((StgTRecChunk *) p);
            TRecEntry *e = &(tc -> entries[0]);
Ben Gamari's avatar
Ben Gamari committed
1195
            gct->eager_promotion = false;