X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=rts%2Fsm%2FScav.c;h=4fa0a220e0dc8a8ff74d436f4baba6f2d3585691;hb=4207605cc8e035e05f651334ef1be90b098d305d;hp=814744fdb9454feedff86803b07ccdd95c2a13c0;hpb=f86e7206ea94b48b94fb61007a1c5d55b8c60f45;p=ghc-hetmet.git diff --git a/rts/sm/Scav.c b/rts/sm/Scav.c index 814744f..4fa0a22 100644 --- a/rts/sm/Scav.c +++ b/rts/sm/Scav.c @@ -1,6 +1,6 @@ /* ----------------------------------------------------------------------------- * - * (c) The GHC Team 1998-2006 + * (c) The GHC Team 1998-2008 * * Generational garbage collector: scavenging functions * @@ -11,20 +11,22 @@ * * ---------------------------------------------------------------------------*/ +#include "PosixSource.h" #include "Rts.h" -#include "RtsFlags.h" + #include "Storage.h" -#include "MBlock.h" #include "GC.h" #include "GCThread.h" #include "GCUtils.h" #include "Compact.h" +#include "MarkStack.h" #include "Evac.h" #include "Scav.h" #include "Apply.h" #include "Trace.h" -#include "LdvProfile.h" #include "Sanity.h" +#include "Capability.h" +#include "LdvProfile.h" static void scavenge_stack (StgPtr p, StgPtr stack_end); @@ -32,6 +34,179 @@ static void scavenge_large_bitmap (StgPtr p, StgLargeBitmap *large_bitmap, nat size ); +#if defined(THREADED_RTS) && !defined(PARALLEL_GC) +# define evacuate(a) evacuate1(a) +# define recordMutableGen_GC(a,b) recordMutableGen(a,b) +# define scavenge_loop(a) scavenge_loop1(a) +# define scavenge_block(a) scavenge_block1(a) +# define scavenge_mutable_list(bd,g) scavenge_mutable_list1(bd,g) +# define scavenge_capability_mut_lists(cap) scavenge_capability_mut_Lists1(cap) +#endif + +/* ----------------------------------------------------------------------------- + Scavenge a TSO. + -------------------------------------------------------------------------- */ + +STATIC_INLINE void +scavenge_TSO_link (StgTSO *tso) +{ + // We don't always chase the link field: TSOs on the blackhole + // queue are not automatically alive, so the link field is a + // "weak" pointer in that case. + if (tso->why_blocked != BlockedOnBlackHole) { + evacuate((StgClosure **)&tso->_link); + } +} + +static void +scavengeTSO (StgTSO *tso) +{ + rtsBool saved_eager; + + if (tso->what_next == ThreadRelocated) { + // the only way this can happen is if the old TSO was on the + // mutable list. We might have other links to this defunct + // TSO, so we must update its link field. + evacuate((StgClosure**)&tso->_link); + return; + } + + debugTrace(DEBUG_gc,"scavenging thread %d",(int)tso->id); + + // update the pointer from the Task. + if (tso->bound != NULL) { + tso->bound->tso = tso; + } + + saved_eager = gct->eager_promotion; + gct->eager_promotion = rtsFalse; + + if ( tso->why_blocked == BlockedOnMVar + || tso->why_blocked == BlockedOnBlackHole + || tso->why_blocked == BlockedOnException + ) { + evacuate(&tso->block_info.closure); + } + evacuate((StgClosure **)&tso->blocked_exceptions); + + // scavange current transaction record + evacuate((StgClosure **)&tso->trec); + + // scavenge this thread's stack + scavenge_stack(tso->sp, &(tso->stack[tso->stack_size])); + + if (gct->failed_to_evac) { + tso->dirty = 1; + scavenge_TSO_link(tso); + } else { + tso->dirty = 0; + scavenge_TSO_link(tso); + if (gct->failed_to_evac) { + tso->flags |= TSO_LINK_DIRTY; + } else { + tso->flags &= ~TSO_LINK_DIRTY; + } + } + + gct->eager_promotion = saved_eager; +} + +/* ----------------------------------------------------------------------------- + Blocks of function args occur on the stack (at the top) and + in PAPs. + -------------------------------------------------------------------------- */ + +STATIC_INLINE StgPtr +scavenge_arg_block (StgFunInfoTable *fun_info, StgClosure **args) +{ + StgPtr p; + StgWord bitmap; + nat size; + + p = (StgPtr)args; + switch (fun_info->f.fun_type) { + case ARG_GEN: + bitmap = BITMAP_BITS(fun_info->f.b.bitmap); + size = BITMAP_SIZE(fun_info->f.b.bitmap); + goto small_bitmap; + case ARG_GEN_BIG: + size = GET_FUN_LARGE_BITMAP(fun_info)->size; + scavenge_large_bitmap(p, GET_FUN_LARGE_BITMAP(fun_info), size); + p += size; + break; + default: + bitmap = BITMAP_BITS(stg_arg_bitmaps[fun_info->f.fun_type]); + size = BITMAP_SIZE(stg_arg_bitmaps[fun_info->f.fun_type]); + small_bitmap: + while (size > 0) { + if ((bitmap & 1) == 0) { + evacuate((StgClosure **)p); + } + p++; + bitmap = bitmap >> 1; + size--; + } + break; + } + return p; +} + +STATIC_INLINE GNUC_ATTR_HOT StgPtr +scavenge_PAP_payload (StgClosure *fun, StgClosure **payload, StgWord size) +{ + StgPtr p; + StgWord bitmap; + StgFunInfoTable *fun_info; + + fun_info = get_fun_itbl(UNTAG_CLOSURE(fun)); + ASSERT(fun_info->i.type != PAP); + p = (StgPtr)payload; + + switch (fun_info->f.fun_type) { + case ARG_GEN: + bitmap = BITMAP_BITS(fun_info->f.b.bitmap); + goto small_bitmap; + case ARG_GEN_BIG: + scavenge_large_bitmap(p, GET_FUN_LARGE_BITMAP(fun_info), size); + p += size; + break; + case ARG_BCO: + scavenge_large_bitmap((StgPtr)payload, BCO_BITMAP(fun), size); + p += size; + break; + default: + bitmap = BITMAP_BITS(stg_arg_bitmaps[fun_info->f.fun_type]); + small_bitmap: + while (size > 0) { + if ((bitmap & 1) == 0) { + evacuate((StgClosure **)p); + } + p++; + bitmap = bitmap >> 1; + size--; + } + break; + } + return p; +} + +STATIC_INLINE GNUC_ATTR_HOT StgPtr +scavenge_PAP (StgPAP *pap) +{ + evacuate(&pap->fun); + return scavenge_PAP_payload (pap->fun, pap->payload, pap->n_args); +} + +STATIC_INLINE StgPtr +scavenge_AP (StgAP *ap) +{ + evacuate(&ap->fun); + return scavenge_PAP_payload (ap->fun, ap->payload, ap->n_args); +} + +/* ----------------------------------------------------------------------------- + Scavenge SRTs + -------------------------------------------------------------------------- */ /* Similar to scavenge_large_bitmap(), but we don't write back the * pointers we get back from evacuate(). @@ -66,7 +241,7 @@ scavenge_large_srt_bitmap( StgLargeSRT *large_srt ) * srt field in the info table. That's ok, because we'll * never dereference it. */ -STATIC_INLINE void +STATIC_INLINE GNUC_ATTR_HOT void scavenge_srt (StgClosure **srt, nat srt_bitmap) { nat bitmap; @@ -92,7 +267,7 @@ scavenge_srt (StgClosure **srt, nat srt_bitmap) // If the SRT entry hasn't got bit 0 set, the SRT entry points to a // closure that's fixed at link-time, and no extra magic is required. if ( (unsigned long)(*srt) & 0x1 ) { - evacuate(stgCast(StgClosure**,(stgCast(unsigned long, *srt) & ~0x1))); + evacuate( (StgClosure**) ((unsigned long) (*srt) & ~0x1)); } else { evacuate(p); } @@ -106,7 +281,7 @@ scavenge_srt (StgClosure **srt, nat srt_bitmap) } -STATIC_INLINE void +STATIC_INLINE GNUC_ATTR_HOT void scavenge_thunk_srt(const StgInfoTable *info) { StgThunkInfoTable *thunk_info; @@ -117,7 +292,7 @@ scavenge_thunk_srt(const StgInfoTable *info) scavenge_srt((StgClosure **)GET_SRT(thunk_info), thunk_info->i.srt_bitmap); } -STATIC_INLINE void +STATIC_INLINE GNUC_ATTR_HOT void scavenge_fun_srt(const StgInfoTable *info) { StgFunInfoTable *fun_info; @@ -129,148 +304,431 @@ scavenge_fun_srt(const StgInfoTable *info) } /* ----------------------------------------------------------------------------- - Scavenge a TSO. + Scavenge a block from the given scan pointer up to bd->free. + + evac_gen is set by the caller to be either zero (for a step in a + generation < N) or G where G is the generation of the step being + scavenged. + + We sometimes temporarily change evac_gen back to zero if we're + scavenging a mutable object where eager promotion isn't such a good + idea. -------------------------------------------------------------------------- */ -static void -scavengeTSO (StgTSO *tso) -{ - rtsBool saved_eager; +static GNUC_ATTR_HOT void +scavenge_block (bdescr *bd) +{ + StgPtr p, q; + StgInfoTable *info; + generation *saved_evac_gen; + rtsBool saved_eager_promotion; + gen_workspace *ws; + + debugTrace(DEBUG_gc, "scavenging block %p (gen %d) @ %p", + bd->start, bd->gen_no, bd->u.scan); + + gct->scan_bd = bd; + gct->evac_gen = bd->gen; + saved_evac_gen = gct->evac_gen; + saved_eager_promotion = gct->eager_promotion; + gct->failed_to_evac = rtsFalse; + + ws = &gct->gens[bd->gen->no]; + + p = bd->u.scan; + + // 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)) { + + ASSERT(bd->link == NULL); + ASSERT(LOOKS_LIKE_CLOSURE_PTR(p)); + info = get_itbl((StgClosure *)p); + + ASSERT(gct->thunk_selector_depth == 0); + + q = p; + switch (info->type) { + + case MVAR_CLEAN: + case MVAR_DIRTY: + { + StgMVar *mvar = ((StgMVar *)p); + gct->eager_promotion = rtsFalse; + 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; + } + + case FUN_2_0: + scavenge_fun_srt(info); + evacuate(&((StgClosure *)p)->payload[1]); + evacuate(&((StgClosure *)p)->payload[0]); + p += sizeofW(StgHeader) + 2; + break; + + case THUNK_2_0: + scavenge_thunk_srt(info); + evacuate(&((StgThunk *)p)->payload[1]); + evacuate(&((StgThunk *)p)->payload[0]); + p += sizeofW(StgThunk) + 2; + break; + + case CONSTR_2_0: + evacuate(&((StgClosure *)p)->payload[1]); + evacuate(&((StgClosure *)p)->payload[0]); + p += sizeofW(StgHeader) + 2; + break; + + case THUNK_1_0: + scavenge_thunk_srt(info); + evacuate(&((StgThunk *)p)->payload[0]); + p += sizeofW(StgThunk) + 1; + break; + + case FUN_1_0: + scavenge_fun_srt(info); + case CONSTR_1_0: + evacuate(&((StgClosure *)p)->payload[0]); + p += sizeofW(StgHeader) + 1; + break; + + case THUNK_0_1: + scavenge_thunk_srt(info); + p += sizeofW(StgThunk) + 1; + break; + + case FUN_0_1: + scavenge_fun_srt(info); + case CONSTR_0_1: + p += sizeofW(StgHeader) + 1; + break; + + case THUNK_0_2: + scavenge_thunk_srt(info); + p += sizeofW(StgThunk) + 2; + break; + + case FUN_0_2: + scavenge_fun_srt(info); + case CONSTR_0_2: + p += sizeofW(StgHeader) + 2; + break; + + case THUNK_1_1: + scavenge_thunk_srt(info); + evacuate(&((StgThunk *)p)->payload[0]); + p += sizeofW(StgThunk) + 2; + break; + + case FUN_1_1: + scavenge_fun_srt(info); + case CONSTR_1_1: + evacuate(&((StgClosure *)p)->payload[0]); + p += sizeofW(StgHeader) + 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); + } + p += info->layout.payload.nptrs; + break; + } + + gen_obj: + case CONSTR: + case WEAK: + case STABLE_NAME: + { + 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; + } + + case BCO: { + StgBCO *bco = (StgBCO *)p; + evacuate((StgClosure **)&bco->instrs); + evacuate((StgClosure **)&bco->literals); + evacuate((StgClosure **)&bco->ptrs); + p += bco_sizeW(bco); + break; + } + + case IND_PERM: + if (bd->gen_no != 0) { +#ifdef PROFILING + // @LDV profiling + // No need to call LDV_recordDead_FILL_SLOP_DYNAMIC() because an + // IND_OLDGEN_PERM closure is larger than an IND_PERM closure. + LDV_recordDead((StgClosure *)p, sizeofW(StgInd)); +#endif + // + // Todo: maybe use SET_HDR() and remove LDV_RECORD_CREATE()? + // + SET_INFO(((StgClosure *)p), &stg_IND_OLDGEN_PERM_info); + + // We pretend that p has just been created. + LDV_RECORD_CREATE((StgClosure *)p); + } + // fall through + case IND_OLDGEN_PERM: + evacuate(&((StgInd *)p)->indirectee); + p += sizeofW(StgInd); + break; + + case MUT_VAR_CLEAN: + case MUT_VAR_DIRTY: + gct->eager_promotion = rtsFalse; + 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; + + case CAF_BLACKHOLE: + case BLACKHOLE: + p += BLACKHOLE_sizeW(); + break; + + case THUNK_SELECTOR: + { + StgSelector *s = (StgSelector *)p; + evacuate(&s->selectee); + p += THUNK_SELECTOR_sizeW(); + 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); + p = (StgPtr)ap->payload + ap->size; + break; + } + + case PAP: + p = scavenge_PAP((StgPAP *)p); + break; + + case AP: + p = scavenge_AP((StgAP *)p); + break; + + case ARR_WORDS: + // nothing to follow + p += arr_words_sizeW((StgArrWords *)p); + break; + + case MUT_ARR_PTRS_CLEAN: + case 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. + gct->eager_promotion = rtsFalse; + next = p + mut_arr_ptrs_sizeW((StgMutArrPtrs*)p); + for (p = (P_)((StgMutArrPtrs *)p)->payload; p < next; p++) { + evacuate((StgClosure **)p); + } + gct->eager_promotion = saved_eager_promotion; + + 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; + } - if (tso->what_next == ThreadRelocated) { - // the only way this can happen is if the old TSO was on the - // mutable list. We might have other links to this defunct - // TSO, so we must update its link field. - evacuate((StgClosure**)&tso->_link); - return; + gct->failed_to_evac = rtsTrue; // always put it on the mutable list. + break; } - saved_eager = gct->eager_promotion; - gct->eager_promotion = rtsFalse; + case MUT_ARR_PTRS_FROZEN: + case MUT_ARR_PTRS_FROZEN0: + // follow everything + { + StgPtr next; - if ( tso->why_blocked == BlockedOnMVar - || tso->why_blocked == BlockedOnBlackHole - || tso->why_blocked == BlockedOnException - ) { - evacuate(&tso->block_info.closure); - } - evacuate((StgClosure **)&tso->blocked_exceptions); - - // We don't always chase the link field: TSOs on the blackhole - // queue are not automatically alive, so the link field is a - // "weak" pointer in that case. - if (tso->why_blocked != BlockedOnBlackHole) { - evacuate((StgClosure **)&tso->link); - } + next = p + mut_arr_ptrs_sizeW((StgMutArrPtrs*)p); + for (p = (P_)((StgMutArrPtrs *)p)->payload; p < next; p++) { + evacuate((StgClosure **)p); + } - // scavange current transaction record - evacuate((StgClosure **)&tso->trec); - - // scavenge this thread's stack - scavenge_stack(tso->sp, &(tso->stack[tso->stack_size])); + // If we're going to put this object on the mutable list, then + // set its info ptr to MUT_ARR_PTRS_FROZEN0 to indicate that. + if (gct->failed_to_evac) { + ((StgClosure *)q)->header.info = &stg_MUT_ARR_PTRS_FROZEN0_info; + } else { + ((StgClosure *)q)->header.info = &stg_MUT_ARR_PTRS_FROZEN_info; + } + break; + } - if (gct->failed_to_evac) { - tso->flags |= TSO_DIRTY; - } else { - tso->flags &= ~TSO_DIRTY; + case TSO: + { + StgTSO *tso = (StgTSO *)p; + scavengeTSO(tso); + p += tso_sizeW(tso); + break; } - gct->eager_promotion = saved_eager; -} + case TVAR_WATCH_QUEUE: + { + StgTVarWatchQueue *wq = ((StgTVarWatchQueue *) p); + gct->evac_gen = 0; + evacuate((StgClosure **)&wq->closure); + evacuate((StgClosure **)&wq->next_queue_entry); + evacuate((StgClosure **)&wq->prev_queue_entry); + gct->evac_gen = saved_evac_gen; + gct->failed_to_evac = rtsTrue; // mutable + p += sizeofW(StgTVarWatchQueue); + break; + } -/* ----------------------------------------------------------------------------- - Blocks of function args occur on the stack (at the top) and - in PAPs. - -------------------------------------------------------------------------- */ + case TVAR: + { + StgTVar *tvar = ((StgTVar *) p); + gct->evac_gen = 0; + evacuate((StgClosure **)&tvar->current_value); + evacuate((StgClosure **)&tvar->first_watch_queue_entry); + gct->evac_gen = saved_evac_gen; + gct->failed_to_evac = rtsTrue; // mutable + p += sizeofW(StgTVar); + break; + } -STATIC_INLINE StgPtr -scavenge_arg_block (StgFunInfoTable *fun_info, StgClosure **args) -{ - StgPtr p; - StgWord bitmap; - nat size; + case TREC_HEADER: + { + StgTRecHeader *trec = ((StgTRecHeader *) p); + gct->evac_gen = 0; + evacuate((StgClosure **)&trec->enclosing_trec); + evacuate((StgClosure **)&trec->current_chunk); + evacuate((StgClosure **)&trec->invariants_to_check); + gct->evac_gen = saved_evac_gen; + gct->failed_to_evac = rtsTrue; // mutable + p += sizeofW(StgTRecHeader); + break; + } - p = (StgPtr)args; - switch (fun_info->f.fun_type) { - case ARG_GEN: - bitmap = BITMAP_BITS(fun_info->f.b.bitmap); - size = BITMAP_SIZE(fun_info->f.b.bitmap); - goto small_bitmap; - case ARG_GEN_BIG: - size = GET_FUN_LARGE_BITMAP(fun_info)->size; - scavenge_large_bitmap(p, GET_FUN_LARGE_BITMAP(fun_info), size); - p += size; - break; - default: - bitmap = BITMAP_BITS(stg_arg_bitmaps[fun_info->f.fun_type]); - size = BITMAP_SIZE(stg_arg_bitmaps[fun_info->f.fun_type]); - small_bitmap: - while (size > 0) { - if ((bitmap & 1) == 0) { - evacuate((StgClosure **)p); - } - p++; - bitmap = bitmap >> 1; - size--; + case TREC_CHUNK: + { + StgWord i; + StgTRecChunk *tc = ((StgTRecChunk *) p); + TRecEntry *e = &(tc -> entries[0]); + gct->evac_gen = 0; + 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->evac_gen = saved_evac_gen; + gct->failed_to_evac = rtsTrue; // mutable + p += sizeofW(StgTRecChunk); break; - } - return p; -} + } -STATIC_INLINE StgPtr -scavenge_PAP_payload (StgClosure *fun, StgClosure **payload, StgWord size) -{ - StgPtr p; - StgWord bitmap; - StgFunInfoTable *fun_info; - - fun_info = get_fun_itbl(UNTAG_CLOSURE(fun)); - ASSERT(fun_info->i.type != PAP); - p = (StgPtr)payload; + case ATOMIC_INVARIANT: + { + StgAtomicInvariant *invariant = ((StgAtomicInvariant *) p); + gct->evac_gen = 0; + evacuate(&invariant->code); + evacuate((StgClosure **)&invariant->last_execution); + gct->evac_gen = saved_evac_gen; + gct->failed_to_evac = rtsTrue; // mutable + p += sizeofW(StgAtomicInvariant); + break; + } + + case INVARIANT_CHECK_QUEUE: + { + StgInvariantCheckQueue *queue = ((StgInvariantCheckQueue *) p); + gct->evac_gen = 0; + evacuate((StgClosure **)&queue->invariant); + evacuate((StgClosure **)&queue->my_execution); + evacuate((StgClosure **)&queue->next_queue_entry); + gct->evac_gen = saved_evac_gen; + gct->failed_to_evac = rtsTrue; // mutable + p += sizeofW(StgInvariantCheckQueue); + break; + } - switch (fun_info->f.fun_type) { - case ARG_GEN: - bitmap = BITMAP_BITS(fun_info->f.b.bitmap); - goto small_bitmap; - case ARG_GEN_BIG: - scavenge_large_bitmap(p, GET_FUN_LARGE_BITMAP(fun_info), size); - p += size; - break; - case ARG_BCO: - scavenge_large_bitmap((StgPtr)payload, BCO_BITMAP(fun), size); - p += size; - break; default: - bitmap = BITMAP_BITS(stg_arg_bitmaps[fun_info->f.fun_type]); - small_bitmap: - while (size > 0) { - if ((bitmap & 1) == 0) { - evacuate((StgClosure **)p); - } - p++; - bitmap = bitmap >> 1; - size--; + barf("scavenge: unimplemented/strange closure type %d @ %p", + info->type, p); + } + + /* + * We need to record the current object on the mutable list if + * (a) It is actually mutable, or + * (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) { + gct->failed_to_evac = rtsFalse; + if (bd->gen_no > 0) { + recordMutableGen_GC((StgClosure *)q, bd->gen_no); } - break; } - return p; -} + } -STATIC_INLINE StgPtr -scavenge_PAP (StgPAP *pap) -{ - evacuate(&pap->fun); - return scavenge_PAP_payload (pap->fun, pap->payload, pap->n_args); -} + if (p > bd->free) { + gct->copied += ws->todo_free - bd->free; + bd->free = p; + } -STATIC_INLINE StgPtr -scavenge_AP (StgAP *ap) -{ - evacuate(&ap->fun); - return scavenge_PAP_payload (ap->fun, ap->payload, ap->n_args); -} + 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; +} /* ----------------------------------------------------------------------------- Scavenge everything on the mark stack. @@ -284,20 +742,18 @@ scavenge_mark_stack(void) { StgPtr p, q; StgInfoTable *info; - step *saved_evac_step; + generation *saved_evac_gen; - gct->evac_step = &oldest_gen->steps[0]; - saved_evac_step = gct->evac_step; + gct->evac_gen = oldest_gen; + saved_evac_gen = gct->evac_gen; -linear_scan: - while (!mark_stack_empty()) { - p = pop_mark_stack(); + while ((p = pop_mark_stack())) { ASSERT(LOOKS_LIKE_CLOSURE_PTR(p)); info = get_itbl((StgClosure *)p); q = p; - switch (((volatile StgWord *)info)[1] & 0xffff) { + switch (info->type) { case MVAR_CLEAN: case MVAR_DIRTY: @@ -433,8 +889,6 @@ linear_scan: } case CAF_BLACKHOLE: - case SE_CAF_BLACKHOLE: - case SE_BLACKHOLE: case BLACKHOLE: case ARR_WORDS: break; @@ -517,18 +971,17 @@ linear_scan: case TSO: { scavengeTSO((StgTSO*)p); - gct->failed_to_evac = rtsTrue; // always on the mutable list break; } case TVAR_WATCH_QUEUE: { StgTVarWatchQueue *wq = ((StgTVarWatchQueue *) p); - gct->evac_step = 0; + gct->evac_gen = 0; evacuate((StgClosure **)&wq->closure); evacuate((StgClosure **)&wq->next_queue_entry); evacuate((StgClosure **)&wq->prev_queue_entry); - gct->evac_step = saved_evac_step; + gct->evac_gen = saved_evac_gen; gct->failed_to_evac = rtsTrue; // mutable break; } @@ -536,10 +989,10 @@ linear_scan: case TVAR: { StgTVar *tvar = ((StgTVar *) p); - gct->evac_step = 0; + gct->evac_gen = 0; evacuate((StgClosure **)&tvar->current_value); evacuate((StgClosure **)&tvar->first_watch_queue_entry); - gct->evac_step = saved_evac_step; + gct->evac_gen = saved_evac_gen; gct->failed_to_evac = rtsTrue; // mutable break; } @@ -549,14 +1002,14 @@ linear_scan: StgWord i; StgTRecChunk *tc = ((StgTRecChunk *) p); TRecEntry *e = &(tc -> entries[0]); - gct->evac_step = 0; + gct->evac_gen = 0; 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->evac_step = saved_evac_step; + gct->evac_gen = saved_evac_gen; gct->failed_to_evac = rtsTrue; // mutable break; } @@ -564,11 +1017,11 @@ linear_scan: case TREC_HEADER: { StgTRecHeader *trec = ((StgTRecHeader *) p); - gct->evac_step = 0; + gct->evac_gen = 0; evacuate((StgClosure **)&trec->enclosing_trec); evacuate((StgClosure **)&trec->current_chunk); evacuate((StgClosure **)&trec->invariants_to_check); - gct->evac_step = saved_evac_step; + gct->evac_gen = saved_evac_gen; gct->failed_to_evac = rtsTrue; // mutable break; } @@ -576,10 +1029,10 @@ linear_scan: case ATOMIC_INVARIANT: { StgAtomicInvariant *invariant = ((StgAtomicInvariant *) p); - gct->evac_step = 0; + gct->evac_gen = 0; evacuate(&invariant->code); evacuate((StgClosure **)&invariant->last_execution); - gct->evac_step = saved_evac_step; + gct->evac_gen = saved_evac_gen; gct->failed_to_evac = rtsTrue; // mutable break; } @@ -587,11 +1040,11 @@ linear_scan: case INVARIANT_CHECK_QUEUE: { StgInvariantCheckQueue *queue = ((StgInvariantCheckQueue *) p); - gct->evac_step = 0; + gct->evac_gen = 0; evacuate((StgClosure **)&queue->invariant); evacuate((StgClosure **)&queue->my_execution); evacuate((StgClosure **)&queue->next_queue_entry); - gct->evac_step = saved_evac_step; + gct->evac_gen = saved_evac_gen; gct->failed_to_evac = rtsTrue; // mutable break; } @@ -603,53 +1056,11 @@ linear_scan: if (gct->failed_to_evac) { gct->failed_to_evac = rtsFalse; - if (gct->evac_step) { - recordMutableGen_GC((StgClosure *)q, gct->evac_step->gen); - } - } - - // mark the next bit to indicate "scavenged" - mark(q+1, Bdescr(q)); - - } // while (!mark_stack_empty()) - - // start a new linear scan if the mark stack overflowed at some point - if (mark_stack_overflowed && oldgen_scan_bd == NULL) { - debugTrace(DEBUG_gc, "scavenge_mark_stack: starting linear scan"); - mark_stack_overflowed = rtsFalse; - oldgen_scan_bd = oldest_gen->steps[0].old_blocks; - oldgen_scan = oldgen_scan_bd->start; - } - - if (oldgen_scan_bd) { - // push a new thing on the mark stack - loop: - // find a closure that is marked but not scavenged, and start - // from there. - while (oldgen_scan < oldgen_scan_bd->free - && !is_marked(oldgen_scan,oldgen_scan_bd)) { - oldgen_scan++; - } - - if (oldgen_scan < oldgen_scan_bd->free) { - - // already scavenged? - if (is_marked(oldgen_scan+1,oldgen_scan_bd)) { - oldgen_scan += sizeofW(StgHeader) + MIN_PAYLOAD_SIZE; - goto loop; + if (gct->evac_gen) { + recordMutableGen_GC((StgClosure *)q, gct->evac_gen->no); } - push_mark_stack(oldgen_scan); - // ToDo: bump the linear scan by the actual size of the object - oldgen_scan += sizeofW(StgHeader) + MIN_PAYLOAD_SIZE; - goto linear_scan; } - - oldgen_scan_bd = oldgen_scan_bd->link; - if (oldgen_scan_bd != NULL) { - oldgen_scan = oldgen_scan_bd->start; - goto loop; - } - } + } // while (p = pop_mark_stack()) } /* ----------------------------------------------------------------------------- @@ -664,7 +1075,7 @@ static rtsBool scavenge_one(StgPtr p) { const StgInfoTable *info; - step *saved_evac_step = gct->evac_step; + generation *saved_evac_gen = gct->evac_gen; rtsBool no_luck; ASSERT(LOOKS_LIKE_CLOSURE_PTR(p)); @@ -750,8 +1161,6 @@ scavenge_one(StgPtr p) } case CAF_BLACKHOLE: - case SE_CAF_BLACKHOLE: - case SE_BLACKHOLE: case BLACKHOLE: break; @@ -837,18 +1246,17 @@ scavenge_one(StgPtr p) case TSO: { scavengeTSO((StgTSO*)p); - gct->failed_to_evac = rtsTrue; // always on the mutable list break; } case TVAR_WATCH_QUEUE: { StgTVarWatchQueue *wq = ((StgTVarWatchQueue *) p); - gct->evac_step = 0; + gct->evac_gen = 0; evacuate((StgClosure **)&wq->closure); evacuate((StgClosure **)&wq->next_queue_entry); evacuate((StgClosure **)&wq->prev_queue_entry); - gct->evac_step = saved_evac_step; + gct->evac_gen = saved_evac_gen; gct->failed_to_evac = rtsTrue; // mutable break; } @@ -856,10 +1264,10 @@ scavenge_one(StgPtr p) case TVAR: { StgTVar *tvar = ((StgTVar *) p); - gct->evac_step = 0; + gct->evac_gen = 0; evacuate((StgClosure **)&tvar->current_value); evacuate((StgClosure **)&tvar->first_watch_queue_entry); - gct->evac_step = saved_evac_step; + gct->evac_gen = saved_evac_gen; gct->failed_to_evac = rtsTrue; // mutable break; } @@ -867,11 +1275,11 @@ scavenge_one(StgPtr p) case TREC_HEADER: { StgTRecHeader *trec = ((StgTRecHeader *) p); - gct->evac_step = 0; + gct->evac_gen = 0; evacuate((StgClosure **)&trec->enclosing_trec); evacuate((StgClosure **)&trec->current_chunk); evacuate((StgClosure **)&trec->invariants_to_check); - gct->evac_step = saved_evac_step; + gct->evac_gen = saved_evac_gen; gct->failed_to_evac = rtsTrue; // mutable break; } @@ -881,14 +1289,14 @@ scavenge_one(StgPtr p) StgWord i; StgTRecChunk *tc = ((StgTRecChunk *) p); TRecEntry *e = &(tc -> entries[0]); - gct->evac_step = 0; + gct->evac_gen = 0; 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->evac_step = saved_evac_step; + gct->evac_gen = saved_evac_gen; gct->failed_to_evac = rtsTrue; // mutable break; } @@ -896,10 +1304,10 @@ scavenge_one(StgPtr p) case ATOMIC_INVARIANT: { StgAtomicInvariant *invariant = ((StgAtomicInvariant *) p); - gct->evac_step = 0; + gct->evac_gen = 0; evacuate(&invariant->code); evacuate((StgClosure **)&invariant->last_execution); - gct->evac_step = saved_evac_step; + gct->evac_gen = saved_evac_gen; gct->failed_to_evac = rtsTrue; // mutable break; } @@ -907,32 +1315,23 @@ scavenge_one(StgPtr p) case INVARIANT_CHECK_QUEUE: { StgInvariantCheckQueue *queue = ((StgInvariantCheckQueue *) p); - gct->evac_step = 0; + gct->evac_gen = 0; evacuate((StgClosure **)&queue->invariant); evacuate((StgClosure **)&queue->my_execution); evacuate((StgClosure **)&queue->next_queue_entry); - gct->evac_step = saved_evac_step; + gct->evac_gen = saved_evac_gen; gct->failed_to_evac = rtsTrue; // mutable break; } + case IND: + // IND can happen, for example, when the interpreter allocates + // a gigantic AP closure (more than one block), which ends up + // on the large-object list and then gets updated. See #3424. case IND_OLDGEN: case IND_OLDGEN_PERM: case IND_STATIC: - { - /* Careful here: a THUNK can be on the mutable list because - * it contains pointers to young gen objects. If such a thunk - * is updated, the IND_OLDGEN will be added to the mutable - * list again, and we'll scavenge it twice. evacuate() - * doesn't check whether the object has already been - * evacuated, so we perform that check here. - */ - StgClosure *q = ((StgInd *)p)->indirectee; - if (HEAP_ALLOCED(q) && Bdescr((StgPtr)q)->flags & BF_EVACUATED) { - break; - } evacuate(&((StgInd *)p)->indirectee); - } #if 0 && defined(DEBUG) if (RtsFlags.DebugFlags.gc) @@ -940,21 +1339,21 @@ scavenge_one(StgPtr p) * promoted */ { - StgPtr start = gen->steps[0].scan; - bdescr *start_bd = gen->steps[0].scan_bd; + StgPtr start = gen->scan; + bdescr *start_bd = gen->scan_bd; nat size = 0; - scavenge(&gen->steps[0]); - if (start_bd != gen->steps[0].scan_bd) { + scavenge(&gen); + if (start_bd != gen->scan_bd) { size += (P_)BLOCK_ROUND_UP(start) - start; start_bd = start_bd->link; - while (start_bd != gen->steps[0].scan_bd) { + while (start_bd != gen->scan_bd) { size += BLOCK_SIZE_W; start_bd = start_bd->link; } - size += gen->steps[0].scan - - (P_)BLOCK_ROUND_DOWN(gen->steps[0].scan); + size += gen->scan - + (P_)BLOCK_ROUND_DOWN(gen->scan); } else { - size = gen->steps[0].scan - start; + size = gen->scan - start; } debugBelch("evac IND_OLDGEN: %ld bytes", size * sizeof(W_)); } @@ -979,14 +1378,11 @@ scavenge_one(StgPtr p) -------------------------------------------------------------------------- */ void -scavenge_mutable_list(generation *gen) +scavenge_mutable_list(bdescr *bd, generation *gen) { - bdescr *bd; StgPtr p, q; - bd = gen->saved_mut_list; - - gct->evac_step = &gen->steps[0]; + gct->evac_gen = gen; for (; bd != NULL; bd = bd->link) { for (q = bd->start; q < bd->free; q++) { p = (StgPtr)*q; @@ -1016,24 +1412,27 @@ scavenge_mutable_list(generation *gen) // definitely doesn't point into a young generation. // Clean objects don't need to be scavenged. Some clean // objects (MUT_VAR_CLEAN) are not kept on the mutable - // list at all; others, such as MUT_ARR_PTRS_CLEAN and - // TSO, are always on the mutable list. + // list at all; others, such as MUT_ARR_PTRS_CLEAN + // are always on the mutable list. // switch (get_itbl((StgClosure *)p)->type) { case MUT_ARR_PTRS_CLEAN: - recordMutableGen_GC((StgClosure *)p,gen); + recordMutableGen_GC((StgClosure *)p,gen->no); continue; case TSO: { StgTSO *tso = (StgTSO *)p; - if ((tso->flags & TSO_DIRTY) == 0) { - // A clean TSO: we don't have to traverse its - // stack. However, we *do* follow the link field: - // we don't want to have to mark a TSO dirty just - // because we put it on a different queue. - if (tso->why_blocked != BlockedOnBlackHole) { - evacuate((StgClosure **)&tso->link); - } - recordMutableGen_GC((StgClosure *)p,gen); + if (tso->dirty == 0) { + // Must be on the mutable list because its link + // field is dirty. + ASSERT(tso->flags & TSO_LINK_DIRTY); + + scavenge_TSO_link(tso); + if (gct->failed_to_evac) { + recordMutableGen_GC((StgClosure *)p,gen->no); + gct->failed_to_evac = rtsFalse; + } else { + tso->flags &= ~TSO_LINK_DIRTY; + } continue; } } @@ -1044,14 +1443,28 @@ scavenge_mutable_list(generation *gen) if (scavenge_one(p)) { // didn't manage to promote everything, so put the // object back on the list. - recordMutableGen_GC((StgClosure *)p,gen); + recordMutableGen_GC((StgClosure *)p,gen->no); } } } +} + +void +scavenge_capability_mut_lists (Capability *cap) +{ + nat g; - // free the old mut_list - freeChain_sync(gen->saved_mut_list); - gen->saved_mut_list = NULL; + /* 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. + */ + for (g = RtsFlags.GcFlags.generations-1; g > N; g--) { + scavenge_mutable_list(cap->saved_mut_lists[g], &generations[g]); + freeChain_sync(cap->saved_mut_lists[g]); + cap->saved_mut_lists[g] = NULL; + } } /* ----------------------------------------------------------------------------- @@ -1072,7 +1485,7 @@ scavenge_static(void) /* Always evacuate straight to the oldest generation for static * objects */ - gct->evac_step = &oldest_gen->steps[0]; + gct->evac_gen = oldest_gen; /* keep going until we've scavenged all the objects on the linked list... */ @@ -1117,7 +1530,7 @@ scavenge_static(void) */ if (gct->failed_to_evac) { gct->failed_to_evac = rtsFalse; - recordMutableGen_GC((StgClosure *)p,oldest_gen); + recordMutableGen_GC((StgClosure *)p,oldest_gen->no); } break; } @@ -1237,19 +1650,34 @@ scavenge_stack(StgPtr p, StgPtr stack_end) // the indirection into an IND_PERM, so that evacuate will // copy the indirection into the old generation instead of // discarding it. + // + // Note [upd-black-hole] + // One slight hiccup is that the THUNK_SELECTOR machinery can + // overwrite the updatee with an IND. In parallel GC, this + // could even be happening concurrently, so we can't check for + // the IND. Fortunately if we assume that blackholing is + // happening (either lazy or eager), then we can be sure that + // the updatee is never a THUNK_SELECTOR and we're ok. + // NB. this is a new invariant: blackholing is not optional. { nat type; - type = get_itbl(((StgUpdateFrame *)p)->updatee)->type; - if (type == IND) { - ((StgUpdateFrame *)p)->updatee->header.info = - (StgInfoTable *)&stg_IND_PERM_info; - } else if (type == IND_OLDGEN) { - ((StgUpdateFrame *)p)->updatee->header.info = - (StgInfoTable *)&stg_IND_OLDGEN_PERM_info; - } - evacuate(&((StgUpdateFrame *)p)->updatee); - p += sizeofW(StgUpdateFrame); - continue; + const StgInfoTable *i; + StgClosure *updatee; + + updatee = ((StgUpdateFrame *)p)->updatee; + i = updatee->header.info; + if (!IS_FORWARDING_PTR(i)) { + type = get_itbl(updatee)->type; + if (type == IND) { + updatee->header.info = &stg_IND_PERM_info; + } else if (type == IND_OLDGEN) { + updatee->header.info = &stg_IND_OLDGEN_PERM_info; + } + } + evacuate(&((StgUpdateFrame *)p)->updatee); + ASSERT(GET_CLOSURE_TAG(((StgUpdateFrame *)p)->updatee) == 0); + p += sizeofW(StgUpdateFrame); + continue; } // small bitmap (< 32 entries, or 64 on a 64-bit machine) @@ -1344,19 +1772,19 @@ scavenge_stack(StgPtr p, StgPtr stack_end) /*----------------------------------------------------------------------------- scavenge the large object list. - evac_step set by caller; similar games played with evac_step as with + evac_gen set by caller; similar games played with evac_gen as with scavenge() - see comment at the top of scavenge(). Most large - objects are (repeatedly) mutable, so most of the time evac_step will + objects are (repeatedly) mutable, so most of the time evac_gen will be zero. --------------------------------------------------------------------------- */ static void -scavenge_large (step_workspace *ws) +scavenge_large (gen_workspace *ws) { bdescr *bd; StgPtr p; - gct->evac_step = ws->step; + gct->evac_gen = ws->gen; bd = ws->todo_large_objects; @@ -1368,15 +1796,15 @@ scavenge_large (step_workspace *ws) // the front when evacuating. ws->todo_large_objects = bd->link; - ACQUIRE_SPIN_LOCK(&ws->step->sync_large_objects); - dbl_link_onto(bd, &ws->step->scavenged_large_objects); - ws->step->n_scavenged_large_blocks += bd->blocks; - RELEASE_SPIN_LOCK(&ws->step->sync_large_objects); + ACQUIRE_SPIN_LOCK(&ws->gen->sync_large_objects); + dbl_link_onto(bd, &ws->gen->scavenged_large_objects); + ws->gen->n_scavenged_large_blocks += bd->blocks; + RELEASE_SPIN_LOCK(&ws->gen->sync_large_objects); p = bd->start; if (scavenge_one(p)) { - if (ws->step->gen_no > 0) { - recordMutableGen_GC((StgClosure *)p, ws->step->gen); + if (ws->gen->no > 0) { + recordMutableGen_GC((StgClosure *)p, ws->gen->no); } } @@ -1386,18 +1814,9 @@ scavenge_large (step_workspace *ws) } /* ---------------------------------------------------------------------------- - Scavenge a block - ------------------------------------------------------------------------- */ - -#define PARALLEL_GC -#include "Scav.c-inc" -#undef PARALLEL_GC -#include "Scav.c-inc" - -/* ---------------------------------------------------------------------------- Look for work to do. - We look for the oldest step that has either a todo block that can + We look for the oldest gen that has either a todo block that can be scanned, or a block of work on the global queue that we can scan. @@ -1416,8 +1835,8 @@ scavenge_large (step_workspace *ws) static rtsBool scavenge_find_work (void) { - int s; - step_workspace *ws; + int g; + gen_workspace *ws; rtsBool did_something, did_anything; bdescr *bd; @@ -1427,11 +1846,8 @@ scavenge_find_work (void) loop: did_something = rtsFalse; - for (s = total_steps-1; s >= 0; s--) { - if (s == 0 && RtsFlags.GcFlags.generations > 1) { - continue; - } - ws = &gct->steps[s]; + for (g = RtsFlags.GcFlags.generations-1; g >= 0; g--) { + ws = &gct->gens[g]; gct->scan_bd = NULL; @@ -1439,11 +1855,7 @@ loop: // scavenge everything up to the free pointer. if (ws->todo_bd->u.scan < ws->todo_free) { - if (n_gc_threads == 1) { - scavenge_block1(ws->todo_bd); - } else { - scavenge_block(ws->todo_bd); - } + scavenge_block(ws->todo_bd); did_something = rtsTrue; break; } @@ -1455,12 +1867,8 @@ loop: break; } - if ((bd = grab_todo_block(ws)) != NULL) { - if (n_gc_threads == 1) { - scavenge_block1(bd); - } else { - scavenge_block(bd); - } + if ((bd = grab_local_todo_block(ws)) != NULL) { + scavenge_block(bd); did_something = rtsTrue; break; } @@ -1470,6 +1878,25 @@ loop: did_anything = rtsTrue; goto loop; } + +#if defined(THREADED_RTS) + if (work_stealing) { + // look for work to steal + for (g = RtsFlags.GcFlags.generations-1; g >= 0; g--) { + if ((bd = steal_todo_block(g)) != NULL) { + scavenge_block(bd); + did_something = rtsTrue; + break; + } + } + + if (did_something) { + did_anything = rtsTrue; + goto loop; + } + } +#endif + // only return when there is no more work to do return did_anything; @@ -1494,8 +1921,7 @@ loop: } // scavenge objects in compacted generation - if (mark_stack_overflowed || oldgen_scan_bd != NULL || - (mark_stack_bdescr != NULL && !mark_stack_empty())) { + if (mark_stack_bd != NULL && !mark_stack_empty()) { scavenge_mark_stack(); work_to_do = rtsTrue; } @@ -1510,35 +1936,3 @@ loop: if (work_to_do) goto loop; } -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; - if (ws->step->todos) return rtsTrue; - } - - gct->no_work++; - - return rtsFalse; -}