X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=ghc%2Frts%2FGC.c;h=6fa541605173d84e7b71846e380666c4bddbde10;hb=2ca1379641d1ffef330e48f124abaa4983837c9b;hp=6e6bd0751467f60f770823b5482d9958cc36fb40;hpb=87bfa396ca8cea3296e8a715766062dc4d2c1d9b;p=ghc-hetmet.git diff --git a/ghc/rts/GC.c b/ghc/rts/GC.c index 6e6bd07..6fa5416 100644 --- a/ghc/rts/GC.c +++ b/ghc/rts/GC.c @@ -1,5 +1,5 @@ /* ----------------------------------------------------------------------------- - * $Id: GC.c,v 1.147 2003/02/12 11:59:49 simonmar Exp $ + * $Id: GC.c,v 1.164 2003/11/26 12:14:26 simonmar Exp $ * * (c) The GHC Team 1998-2003 * @@ -20,7 +20,6 @@ #include "Sanity.h" #include "BlockAlloc.h" #include "MBlock.h" -#include "Main.h" #include "ProfHeap.h" #include "SchedAPI.h" #include "Weak.h" @@ -140,7 +139,14 @@ static lnat thunk_selector_depth = 0; static bdescr * gc_alloc_block ( step *stp ); static void mark_root ( StgClosure **root ); -static StgClosure * evacuate ( StgClosure *q ); + +// Use a register argument for evacuate, if available. +#if __GNUC__ >= 2 +static StgClosure * evacuate (StgClosure *q) __attribute__((regparm(1))); +#else +static StgClosure * evacuate (StgClosure *q); +#endif + static void zero_static_object_list ( StgClosure* first_static ); static void zero_mutable_list ( StgMutClosure *first ); @@ -184,31 +190,31 @@ static rtsBool mark_stack_overflowed; static bdescr *oldgen_scan_bd; static StgPtr oldgen_scan; -static inline rtsBool +STATIC_INLINE rtsBool mark_stack_empty(void) { return mark_sp == mark_stack; } -static inline rtsBool +STATIC_INLINE rtsBool mark_stack_full(void) { return mark_sp >= mark_splim; } -static inline void +STATIC_INLINE void reset_mark_stack(void) { mark_sp = mark_stack; } -static inline void +STATIC_INLINE void push_mark_stack(StgPtr p) { *mark_sp++ = p; } -static inline StgPtr +STATIC_INLINE StgPtr pop_mark_stack(void) { return *--mark_sp; @@ -304,7 +310,7 @@ GarbageCollect ( void (*get_roots)(evac_fn), rtsBool force_major_gc ) Now, Now)); #endif -#ifndef mingw32_TARGET_OS +#if defined(RTS_USER_SIGNALS) // block signals blockUserSignals(); #endif @@ -372,6 +378,7 @@ GarbageCollect ( void (*get_roots)(evac_fn), rtsBool force_major_gc ) if (RtsFlags.GcFlags.generations == 1) { old_to_blocks = g0s0->to_blocks; g0s0->to_blocks = NULL; + g0s0->n_to_blocks = 0; } /* Keep a count of how many new blocks we allocated during this GC @@ -415,7 +422,7 @@ GarbageCollect ( void (*get_roots)(evac_fn), rtsBool force_major_gc ) // mark the large objects as not evacuated yet for (bd = stp->large_objects; bd; bd = bd->link) { - bd->flags = BF_LARGE; + bd->flags &= ~BF_EVACUATED; } // for a compacted step, we need to allocate the bitmap @@ -745,6 +752,7 @@ GarbageCollect ( void (*get_roots)(evac_fn), rtsBool force_major_gc ) // onto the front of the now-compacted existing blocks. for (bd = stp->to_blocks; bd != NULL; bd = bd->link) { bd->flags &= ~BF_EVACUATED; // now from-space + bd->flags |= BF_COMPACTED; // compacted next time } // tack the new blocks on the end of the existing blocks if (stp->blocks == NULL) { @@ -1081,7 +1089,7 @@ GarbageCollect ( void (*get_roots)(evac_fn), rtsBool force_major_gc ) // ok, GC over: tell the stats department what happened. stat_endGC(allocated, collected, live, copied, N); -#ifndef mingw32_TARGET_OS +#if defined(RTS_USER_SIGNALS) // unblock signals again unblockUserSignals(); #endif @@ -1287,6 +1295,7 @@ traverse_weak_ptr_list(void) default: barf("traverse_weak_ptr_list"); + return rtsTrue; } } @@ -1367,7 +1376,7 @@ isAlive(StgClosure *p) } // check the mark bit for compacted steps - if (bd->step->is_compacted && is_marked((P_)p,bd)) { + if ((bd->flags & BF_COMPACTED) && is_marked((P_)p,bd)) { return p; } @@ -1406,7 +1415,7 @@ mark_root(StgClosure **root) *root = evacuate(*root); } -static __inline__ void +STATIC_INLINE void upd_evacuee(StgClosure *p, StgClosure *dest) { // Source object must be in from-space: @@ -1418,7 +1427,7 @@ upd_evacuee(StgClosure *p, StgClosure *dest) } -static __inline__ StgClosure * +STATIC_INLINE StgClosure * copy(StgClosure *src, nat size, step *stp) { P_ to, from, dest; @@ -1524,7 +1533,7 @@ copyPart(StgClosure *src, nat size_to_reserve, nat size_to_copy, step *stp) -------------------------------------------------------------------------- */ -static inline void +STATIC_INLINE void evacuate_large(StgPtr p) { bdescr *bd = Bdescr(p); @@ -1631,6 +1640,23 @@ mkMutCons(StgClosure *ptr, generation *gen) if M < evac_gen set failed_to_evac flag to indicate that we didn't manage to evacuate this object into evac_gen. + + OPTIMISATION NOTES: + + evacuate() is the single most important function performance-wise + in the GC. Various things have been tried to speed it up, but as + far as I can tell the code generated by gcc 3.2 with -O2 is about + as good as it's going to get. We pass the argument to evacuate() + in a register using the 'regparm' attribute (see the prototype for + evacuate() near the top of this file). + + Changing evacuate() to take an (StgClosure **) rather than + returning the new pointer seems attractive, because we can avoid + writing back the pointer when it hasn't changed (eg. for a static + object, or an object in a generation > N). However, I tried it and + it doesn't help. One reason is that the (StgClosure **) pointer + gets spilled to the stack inside evacuate(), resulting in far more + extra reads/writes than we save. -------------------------------------------------------------------------- */ static StgClosure * @@ -1675,7 +1701,7 @@ loop: /* If the object is in a step that we're compacting, then we * need to use an alternative evacuate procedure. */ - if (bd->step->is_compacted) { + if (bd->flags & BF_COMPACTED) { if (!is_marked((P_)q,bd)) { mark((P_)q,bd); if (mark_stack_full()) { @@ -1753,9 +1779,11 @@ loop: case WEAK: case FOREIGN: case STABLE_NAME: - case BCO: return copy(q,sizeW_fromITBL(info),stp); + case BCO: + return copy(q,bco_sizeW((StgBCO *)q),stp); + case CAF_BLACKHOLE: case SE_CAF_BLACKHOLE: case SE_BLACKHOLE: @@ -1802,7 +1830,7 @@ loop: goto loop; case THUNK_STATIC: - if (info->srt_len > 0 && major_gc && + if (info->srt_bitmap != 0 && major_gc && THUNK_STATIC_LINK((StgClosure *)q) == NULL) { THUNK_STATIC_LINK((StgClosure *)q) = static_objects; static_objects = (StgClosure *)q; @@ -1810,7 +1838,7 @@ loop: return q; case FUN_STATIC: - if (info->srt_len > 0 && major_gc && + if (info->srt_bitmap != 0 && major_gc && FUN_STATIC_LINK((StgClosure *)q) == NULL) { FUN_STATIC_LINK((StgClosure *)q) = static_objects; static_objects = (StgClosure *)q; @@ -1905,8 +1933,18 @@ loop: * list it contains. */ { - StgTSO *new_tso = (StgTSO *)copy((StgClosure *)tso,tso_sizeW(tso),stp); + StgTSO *new_tso; + StgPtr p, q; + + new_tso = (StgTSO *)copyPart((StgClosure *)tso, + tso_sizeW(tso), + sizeofW(StgTSO), stp); move_TSO(tso, new_tso); + for (p = tso->sp, q = new_tso->sp; + p < tso->stack+tso->stack_size;) { + *q++ = *p++; + } + return (StgClosure *)new_tso; } } @@ -1980,6 +2018,7 @@ eval_thunk_selector( nat field, StgSelector * p ) StgInfoTable *info; const StgInfoTable *info_ptr; StgClosure *selectee; + bdescr *bd; selectee = p->selectee; @@ -2001,6 +2040,40 @@ eval_thunk_selector( nat field, StgSelector * p ) selector_loop: + // We don't want to end up in to-space, because this causes + // problems when the GC later tries to evacuate the result of + // eval_thunk_selector(). There are various ways this could + // happen: + // + // 1. following an IND_STATIC + // + // 2. when the old generation is compacted, the mark phase updates + // from-space pointers to be to-space pointers, and we can't + // reliably tell which we're following (eg. from an IND_STATIC). + // + // 3. compacting GC again: if we're looking at a constructor in + // the compacted generation, it might point directly to objects + // in to-space. We must bale out here, otherwise doing the selection + // will result in a to-space pointer being returned. + // + // (1) is dealt with using a BF_EVACUATED test on the + // selectee. (2) and (3): we can tell if we're looking at an + // object in the compacted generation that might point to + // to-space objects by testing that (a) it is BF_COMPACTED, (b) + // the compacted generation is being collected, and (c) the + // object is marked. Only a marked object may have pointers that + // point to to-space objects, because that happens when + // scavenging. + // + bd = Bdescr((StgPtr)selectee); + if (HEAP_ALLOCED(selectee) && + ((bd->flags & BF_EVACUATED) + || ((bd->flags & BF_COMPACTED) && + bd->gen_no <= N && + is_marked((P_)selectee,bd)))) { + goto bale_out; + } + info = get_itbl(selectee); switch (info->type) { case CONSTR: @@ -2015,12 +2088,15 @@ selector_loop: ASSERT(field < (StgWord32)(info->layout.payload.ptrs + info->layout.payload.nptrs)); + // ToDo: shouldn't we test whether this pointer is in + // to-space? return selectee->payload[field]; case IND: case IND_PERM: case IND_OLDGEN: case IND_OLDGEN_PERM: + case IND_STATIC: selectee = ((StgInd *)selectee)->indirectee; goto selector_loop; @@ -2030,11 +2106,6 @@ selector_loop: // leaks by evaluating this selector thunk anyhow. break; - case IND_STATIC: - // We can't easily tell whether the indirectee is into - // from or to-space, so just bail out here. - break; - case THUNK_SELECTOR: { StgClosure *val; @@ -2078,6 +2149,7 @@ selector_loop: } case AP: + case AP_STACK: case THUNK: case THUNK_1_0: case THUNK_0_1: @@ -2107,6 +2179,7 @@ selector_loop: (int)(info->type)); } +bale_out: // We didn't manage to evaluate this thunk; restore the old info pointer SET_INFO(p, info_ptr); return NULL; @@ -2122,70 +2195,109 @@ move_TSO (StgTSO *src, StgTSO *dest) { ptrdiff_t diff; - // relocate the stack pointers... + // relocate the stack pointer... diff = (StgPtr)dest - (StgPtr)src; // In *words* dest->sp = (StgPtr)dest->sp + diff; } -/* evacuate the SRT. If srt_len is zero, then there isn't an +/* Similar to scavenge_large_bitmap(), but we don't write back the + * pointers we get back from evacuate(). + */ +static void +scavenge_large_srt_bitmap( StgLargeSRT *large_srt ) +{ + nat i, b, size; + StgWord bitmap; + StgClosure **p; + + b = 0; + bitmap = large_srt->l.bitmap[b]; + size = (nat)large_srt->l.size; + p = (StgClosure **)large_srt->srt; + for (i = 0; i < size; ) { + if ((bitmap & 1) != 0) { + evacuate(*p); + } + i++; + p++; + if (i % BITS_IN(W_) == 0) { + b++; + bitmap = large_srt->l.bitmap[b]; + } else { + bitmap = bitmap >> 1; + } + } +} + +/* evacuate the SRT. If srt_bitmap is zero, then there isn't an * srt field in the info table. That's ok, because we'll * never dereference it. */ -static inline void -scavenge_srt (StgClosure **srt, nat srt_len) +STATIC_INLINE void +scavenge_srt (StgClosure **srt, nat srt_bitmap) { - StgClosure **srt_end; + nat bitmap; + StgClosure **p; - srt_end = srt + srt_len; + bitmap = srt_bitmap; + p = srt; - for (; srt < srt_end; srt++) { - /* Special-case to handle references to closures hiding out in DLLs, since - double indirections required to get at those. The code generator knows - which is which when generating the SRT, so it stores the (indirect) - reference to the DLL closure in the table by first adding one to it. - We check for this here, and undo the addition before evacuating it. + if (bitmap == (StgHalfWord)(-1)) { + scavenge_large_srt_bitmap( (StgLargeSRT *)srt ); + return; + } - 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. - */ + while (bitmap != 0) { + if ((bitmap & 1) != 0) { #ifdef ENABLE_WIN32_DLL_SUPPORT - if ( (unsigned long)(*srt) & 0x1 ) { - evacuate(*stgCast(StgClosure**,(stgCast(unsigned long, *srt) & ~0x1))); - } else { - evacuate(*srt); - } + // Special-case to handle references to closures hiding out in DLLs, since + // double indirections required to get at those. The code generator knows + // which is which when generating the SRT, so it stores the (indirect) + // reference to the DLL closure in the table by first adding one to it. + // We check for this here, and undo the addition before evacuating it. + // + // 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))); + } else { + evacuate(*p); + } #else - evacuate(*srt); + evacuate(*p); #endif + } + p++; + bitmap = bitmap >> 1; } } -static inline void +STATIC_INLINE void scavenge_thunk_srt(const StgInfoTable *info) { StgThunkInfoTable *thunk_info; thunk_info = itbl_to_thunk_itbl(info); - scavenge_srt((StgClosure **)thunk_info->srt, thunk_info->i.srt_len); + scavenge_srt((StgClosure **)thunk_info->srt, thunk_info->i.srt_bitmap); } -static inline void +STATIC_INLINE void scavenge_fun_srt(const StgInfoTable *info) { StgFunInfoTable *fun_info; fun_info = itbl_to_fun_itbl(info); - scavenge_srt((StgClosure **)fun_info->srt, fun_info->i.srt_len); + scavenge_srt((StgClosure **)fun_info->srt, fun_info->i.srt_bitmap); } -static inline void +STATIC_INLINE void scavenge_ret_srt(const StgInfoTable *info) { StgRetInfoTable *ret_info; ret_info = itbl_to_ret_itbl(info); - scavenge_srt((StgClosure **)ret_info->srt, ret_info->i.srt_len); + scavenge_srt((StgClosure **)ret_info->srt, ret_info->i.srt_bitmap); } /* ----------------------------------------------------------------------------- @@ -2221,7 +2333,7 @@ scavengeTSO (StgTSO *tso) in PAPs. -------------------------------------------------------------------------- */ -static inline StgPtr +STATIC_INLINE StgPtr scavenge_arg_block (StgFunInfoTable *fun_info, StgClosure **args) { StgPtr p; @@ -2256,7 +2368,7 @@ scavenge_arg_block (StgFunInfoTable *fun_info, StgClosure **args) return p; } -static inline StgPtr +STATIC_INLINE StgPtr scavenge_PAP (StgPAP *pap) { StgPtr p; @@ -2345,7 +2457,7 @@ scavenge(step *stp) q = p; switch (info->type) { - + case MVAR: /* treat MVars specially, because we don't want to evacuate the * mut_link field in the middle of the closure. @@ -2439,7 +2551,6 @@ scavenge(step *stp) case WEAK: case FOREIGN: case STABLE_NAME: - case BCO: { StgPtr end; @@ -2451,6 +2562,16 @@ scavenge(step *stp) break; } + case BCO: { + StgBCO *bco = (StgBCO *)p; + (StgClosure *)bco->instrs = evacuate((StgClosure *)bco->instrs); + (StgClosure *)bco->literals = evacuate((StgClosure *)bco->literals); + (StgClosure *)bco->ptrs = evacuate((StgClosure *)bco->ptrs); + (StgClosure *)bco->itbls = evacuate((StgClosure *)bco->itbls); + p += bco_sizeW(bco); + break; + } + case IND_PERM: if (stp->gen->no != 0) { #ifdef PROFILING @@ -2563,6 +2684,11 @@ scavenge(step *stp) { StgPtr next; + // Set the mut_link field to NULL, so that we will put this + // array back on the mutable list if it is subsequently thawed + // by unsafeThaw#. + ((StgMutArrPtrs*)p)->mut_link = NULL; + next = p + mut_arr_ptrs_sizeW((StgMutArrPtrs*)p); for (p = (P_)((StgMutArrPtrs *)p)->payload; p < next; p++) { (StgClosure *)*p = evacuate((StgClosure *)*p); @@ -2768,7 +2894,6 @@ linear_scan: case WEAK: case FOREIGN: case STABLE_NAME: - case BCO: { StgPtr end; @@ -2779,6 +2904,15 @@ linear_scan: break; } + case BCO: { + StgBCO *bco = (StgBCO *)p; + (StgClosure *)bco->instrs = evacuate((StgClosure *)bco->instrs); + (StgClosure *)bco->literals = evacuate((StgClosure *)bco->literals); + (StgClosure *)bco->ptrs = evacuate((StgClosure *)bco->ptrs); + (StgClosure *)bco->itbls = evacuate((StgClosure *)bco->itbls); + break; + } + case IND_PERM: // don't need to do anything here: the only possible case // is that we're in a 1-space compacting collector, with @@ -2865,6 +2999,11 @@ linear_scan: { StgPtr next; + // Set the mut_link field to NULL, so that we will put this + // array on the mutable list if it is subsequently thawed + // by unsafeThaw#. + ((StgMutArrPtrs*)p)->mut_link = NULL; + next = p + mut_arr_ptrs_sizeW((StgMutArrPtrs*)p); for (p = (P_)((StgMutArrPtrs *)p)->payload; p < next; p++) { (StgClosure *)*p = evacuate((StgClosure *)*p); @@ -3087,6 +3226,11 @@ scavenge_one(StgPtr p) // follow everything StgPtr next; + // Set the mut_link field to NULL, so that we will put this + // array on the mutable list if it is subsequently thawed + // by unsafeThaw#. + ((StgMutArrPtrs*)p)->mut_link = NULL; + next = p + mut_arr_ptrs_sizeW((StgMutArrPtrs*)p); for (p = (P_)((StgMutArrPtrs *)p)->payload; p < next; p++) { (StgClosure *)*p = evacuate((StgClosure *)*p); @@ -3295,6 +3439,9 @@ scavenge_mutable_list(generation *gen) (StgClosure *)*q = evacuate((StgClosure *)*q); } evac_gen = 0; + // Set the mut_link field to NULL, so that we will put this + // array back on the mutable list if it is subsequently thawed + // by unsafeThaw#. p->mut_link = NULL; if (failed_to_evac) { failed_to_evac = rtsFalse; @@ -3544,7 +3691,7 @@ scavenge_large_bitmap( StgPtr p, StgLargeBitmap *large_bitmap, nat size ) } } -static inline StgPtr +STATIC_INLINE StgPtr scavenge_small_bitmap (StgPtr p, nat size, StgWord bitmap) { while (size > 0) { @@ -3603,7 +3750,7 @@ scavenge_stack(StgPtr p, StgPtr stack_end) p = scavenge_small_bitmap(p, size, bitmap); follow_srt: - scavenge_srt((StgClosure **)info->srt, info->i.srt_len); + scavenge_srt((StgClosure **)info->srt, info->i.srt_bitmap); continue; case RET_BCO: { @@ -3646,11 +3793,11 @@ scavenge_stack(StgPtr p, StgPtr stack_end) // traverse the bitmap first bitmap = GET_LIVENESS(dyn); p = (P_)&((StgRetDyn *)p)->payload[0]; - size = RET_DYN_SIZE; + size = RET_DYN_BITMAP_SIZE; p = scavenge_small_bitmap(p, size, bitmap); // skip over the non-ptr words - p += GET_NONPTRS(dyn); + p += GET_NONPTRS(dyn) + RET_DYN_NONPTR_REGS_SIZE; // follow the ptr words for (size = GET_PTRS(dyn); size > 0; size--) { @@ -4092,20 +4239,20 @@ done_traversing: void *gap_start, *next_gap_start, *gap_end; nat chunk_size; - next_gap_start = (void *)gap + sizeof(StgUpdateFrame); + next_gap_start = (void *)((unsigned char*)gap + sizeof(StgUpdateFrame)); sp = next_gap_start; while ((StgPtr)gap > tso->sp) { // we're working in *bytes* now... gap_start = next_gap_start; - gap_end = gap_start - gap->gap_size * sizeof(W_); + gap_end = (void*) ((unsigned char*)gap_start - gap->gap_size * sizeof(W_)); gap = gap->next_gap; - next_gap_start = (void *)gap + sizeof(StgUpdateFrame); + next_gap_start = (void *)((unsigned char*)gap + sizeof(StgUpdateFrame)); - chunk_size = gap_end - next_gap_start; - sp -= chunk_size; + chunk_size = (unsigned char*)gap_end - (unsigned char*)next_gap_start; + (unsigned char*)sp -= chunk_size; memmove(sp, next_gap_start, chunk_size); } @@ -4166,7 +4313,7 @@ printMutableList(generation *gen) fputc('\n', stderr); } -static inline rtsBool +STATIC_INLINE rtsBool maybeLarge(StgClosure *closure) { StgInfoTable *info = get_itbl(closure);