diff options
| -rw-r--r-- | rts/RtsFlags.c | 3 | ||||
| -rw-r--r-- | rts/include/rts/Flags.h | 1 | ||||
| -rw-r--r-- | rts/sm/NonMoving.c | 7 | ||||
| -rw-r--r-- | rts/sm/NonMoving.h | 4 | ||||
| -rw-r--r-- | rts/sm/NonMovingMark.c | 466 | ||||
| -rw-r--r-- | rts/sm/NonMovingMark.h | 6 |
6 files changed, 486 insertions, 1 deletions
diff --git a/rts/RtsFlags.c b/rts/RtsFlags.c index 778f49c13b..9a944841b4 100644 --- a/rts/RtsFlags.c +++ b/rts/RtsFlags.c @@ -2123,6 +2123,9 @@ static void read_debug_flags(const char* arg) case 'n': RtsFlags.DebugFlags.nonmoving_gc = true; break; + case 'N': + RtsFlags.DebugFlags.nonmoving_mark_check = true; + break; case 'b': RtsFlags.DebugFlags.block_alloc = true; break; diff --git a/rts/include/rts/Flags.h b/rts/include/rts/Flags.h index 11e7bfdaa7..35ec38d997 100644 --- a/rts/include/rts/Flags.h +++ b/rts/include/rts/Flags.h @@ -101,6 +101,7 @@ typedef struct _DEBUG_FLAGS { bool gccafs; /* 'G' */ bool gc; /* 'g' */ bool nonmoving_gc; /* 'n' */ + bool nonmoving_mark_check; /* 'N' warning: quite expensive! */ bool block_alloc; /* 'b' */ bool sanity; /* 'S' warning: might be expensive! */ bool zero_on_gc; /* 'Z' */ diff --git a/rts/sm/NonMoving.c b/rts/sm/NonMoving.c index b92bf2276e..9b7978b777 100644 --- a/rts/sm/NonMoving.c +++ b/rts/sm/NonMoving.c @@ -236,6 +236,9 @@ Mutex concurrent_coll_finished_lock; * how we use the DIRTY flags associated with MUT_VARs and TVARs to improve * barrier efficiency. * + * - Note [Non-moving mark check] (NonMovingMark.c) describes the mark-checking + * facility useful for sanity-checking the collector implementation. + * * [ueno 2016]: * Katsuhiro Ueno and Atsushi Ohori. 2016. A fully concurrent garbage * collector for functional programs on multicore processors. SIGPLAN Not. 51, @@ -1196,6 +1199,10 @@ static void nonmovingMark_(MarkQueue *mark_queue, StgWeak **dead_weaks, StgTSO * oldest_gen->n_old_blocks = 0; resizeGenerations(); + if (RtsFlags.DebugFlags.nonmoving_mark_check) { + nonmovingMarkCheck(); + } + /**************************************************** * Sweep ****************************************************/ diff --git a/rts/sm/NonMoving.h b/rts/sm/NonMoving.h index 6eabcb8493..ef9710bc24 100644 --- a/rts/sm/NonMoving.h +++ b/rts/sm/NonMoving.h @@ -27,6 +27,10 @@ // In blocks #define NONMOVING_SEGMENT_BLOCKS (NONMOVING_SEGMENT_SIZE / BLOCK_SIZE) +#if defined(DEBUG) +#define NONMOVING_MARK_CHECK +#endif + _Static_assert(NONMOVING_SEGMENT_SIZE % BLOCK_SIZE == 0, "non-moving segment size must be multiple of block size"); diff --git a/rts/sm/NonMovingMark.c b/rts/sm/NonMovingMark.c index 1fc292769d..2c2a083115 100644 --- a/rts/sm/NonMovingMark.c +++ b/rts/sm/NonMovingMark.c @@ -15,6 +15,7 @@ #include "NonMoving.h" #include "BlockAlloc.h" /* for countBlocks */ #include "HeapAlloc.h" +#include "Hash.h" #include "Task.h" #include "Trace.h" #include "HeapUtils.h" @@ -24,6 +25,7 @@ #include "Stats.h" #include "STM.h" #include "MarkWeak.h" +#include "StablePtr.h" // markStablePtrTable #include "sm/Storage.h" #include "CNF.h" @@ -1469,7 +1471,6 @@ mark_closure (MarkQueue *queue, const StgClosure *p0, StgClosure **origin) gen_obj: case CONSTR: case CONSTR_NOCAF: - case WEAK: case PRIM: { for (StgWord i = 0; i < info->layout.payload.ptrs; i++) { @@ -1479,6 +1480,17 @@ mark_closure (MarkQueue *queue, const StgClosure *p0, StgClosure **origin) break; } + case WEAK: + { + StgWeak *w = (StgWeak *) p; + if (nonmovingIsAlive(w->key)) { + PUSH_FIELD(w, value); + PUSH_FIELD(w, cfinalizers); + PUSH_FIELD(w, finalizer); + } + break; + } + case BCO: { StgBCO *bco = (StgBCO *)p; PUSH_FIELD(bco, instrs); @@ -1947,6 +1959,458 @@ void nonmovingResurrectThreads (struct MarkQueue_ *queue, StgTSO **resurrected_t } } +#if defined(NONMOVING_MARK_CHECK) + +#define CLOSURE_SET_SEGMENT_OPT 0 + +typedef struct { + HashTable *other_objs; // Map ClosureAddr () +#if CLOSURE_SET_SEGMENT_OPT + HashTable *segments; // Map BlockAddr BitMap +#endif +} ClosureSet; + +static void closureSetInit(ClosureSet *cs) { + cs->other_objs = allocHashTable(); +#if CLOSURE_SET_SEGMENT_OPT + cs->segments = allocHashTable(); +#endif +} + +static void closureSetFree(ClosureSet *cs) { + freeHashTable(cs->other_objs, NULL); +#if CLOSURE_SET_SEGMENT_OPT + freeHashTable(cs->segments); +#endif +} + +static bool closureSetLookup(ClosureSet *cs, StgClosure *p) { +#if CLOSURE_SET_SEGMENT_OPT + bdescr *bd = Bdescr(c); + if (HEAP_ALLOCED(p) && bd->flags & BF_NONMOVING) { + nonmoving_block_idx idx = nonmovingGetBlockIdx(p); + char *bitmap = lookupHashTable(cs->segments, (StgWord) p) != NULL; + if (bitmap) { + return bitmap[idx]; + } else { + return false; + } + } +#endif + + return lookupHashTable(cs->other_objs, (StgWord) p) != NULL; +} + +static void closureSetInsert(ClosureSet *cs, StgClosure *p) { +#if CLOSURE_SET_SEGMENT_OPT + abort(); // TOOD +#endif + + insertHashTable(cs->other_objs, (StgWord) p, (const void *) 1); +} + +static void mark_check_static_object(StgClosure *c, StgClosure **link_field) { + StgWord link = RELAXED_LOAD((StgWord*) link_field); + + // See Note [STATIC_LINK fields] for how the link field bits work + if ((link & STATIC_BITS) != static_flag) { + barf("mark_check_closure: static closure %p not marked", c); + } +} + +static void mark_check_closure(ClosureSet *checked, MarkQueue *queue, StgClosure *p) { + p = UNTAG_CLOSURE(p); + + if (closureSetLookup(checked, p)) { + return; // We have already checked this closure + } + + closureSetInsert(checked, p); + + const StgInfoTable *info = get_itbl(p); + const bdescr *bd = Bdescr((StgPtr) p); + + // N.B. We use push_closure here since we want to trace all closures, even + // those outside of the nonmoving heap. +# define PUSH_FIELD(obj, field) \ + push_closure(queue, \ + (StgClosure *) (obj)->field, \ + (StgClosure **) &(obj)->field) + + if (HEAP_ALLOCED_GC(p)) { + if (bd->flags & BF_LARGE && bd->flags & BF_NONMOVING_SWEEPING) { + if (!(bd->flags & BF_MARKED)) { + barf("mark_check_closure: %p not marked", p); + } + } + else if (bd->flags & BF_NONMOVING \ + && bd->flags & BF_NONMOVING_SWEEPING \ + && ! nonmovingClosureMarkedThisCycle((StgPtr) p)) + { + barf("mark_check_closure: %p not marked", p); + } + } else { + switch (info->type) { + + case THUNK_STATIC: + if (info->srt != 0) { + mark_check_static_object(p, THUNK_STATIC_LINK((StgClosure *)p)); + } + break; + + case FUN_STATIC: + if (info->srt != 0 || info->layout.payload.ptrs != 0) { + mark_check_static_object(p, STATIC_LINK(info,(StgClosure *)p)); + } + break; + + case IND_STATIC: + /* If q->saved_info != NULL, then it's a revertible CAF - it'll be + * on the CAF list, so don't do anything with it here (we'll + * scavenge it later). + */ + mark_check_static_object(p, IND_STATIC_LINK((StgClosure *)p)); + break; + + case CONSTR: + case CONSTR_1_0: + case CONSTR_2_0: + case CONSTR_1_1: + mark_check_static_object(p, STATIC_LINK(info,(StgClosure *)p)); + break; + + case CONSTR_0_1: + case CONSTR_0_2: + case CONSTR_NOCAF: + /* no need to put these on the static linked list, they don't need + * to be scavenged. + */ + break; + + default: + barf("evacuate(static): strange closure type %d", (int)(info->type)); + } + } + + ///////////////////////////////////////////////////// + // Trace pointers + ///////////////////////////////////////////////////// + + switch (info->type) { + + case MVAR_CLEAN: + case MVAR_DIRTY: { + StgMVar *mvar = (StgMVar *) p; + PUSH_FIELD(mvar, head); + PUSH_FIELD(mvar, tail); + PUSH_FIELD(mvar, value); + break; + } + + case TVAR: { + StgTVar *tvar = ((StgTVar *)p); + PUSH_FIELD(tvar, current_value); + PUSH_FIELD(tvar, first_watch_queue_entry); + break; + } + + case FUN_2_0: + markQueuePushFunSrt(queue, info); + PUSH_FIELD(p, payload[1]); + PUSH_FIELD(p, payload[0]); + break; + + case THUNK_2_0: { + StgThunk *thunk = (StgThunk *) p; + markQueuePushThunkSrt(queue, info); + PUSH_FIELD(thunk, payload[1]); + PUSH_FIELD(thunk, payload[0]); + break; + } + + case THUNK_1_0: + markQueuePushThunkSrt(queue, info); + PUSH_FIELD((StgThunk *) p, payload[0]); + break; + + case FUN_1_0: + markQueuePushFunSrt(queue, info); + PUSH_FIELD(p, payload[0]); + break; + + case CONSTR_1_0: + case CONSTR_1_1: + PUSH_FIELD(p, payload[0]); + break; + + case THUNK_0_1: + markQueuePushThunkSrt(queue, info); + break; + + case FUN_0_1: + markQueuePushFunSrt(queue, info); + break; + + case CONSTR_0_1: + case CONSTR_0_2: + break; + + case THUNK_0_2: + markQueuePushThunkSrt(queue, info); + break; + + case FUN_0_2: + markQueuePushFunSrt(queue, info); + break; + + case THUNK_1_1: + markQueuePushThunkSrt(queue, info); + PUSH_FIELD((StgThunk *) p, payload[0]); + break; + + case FUN_1_1: + markQueuePushFunSrt(queue, info); + PUSH_FIELD(p, payload[0]); + break; + + case CONSTR_2_0: + PUSH_FIELD(p, payload[1]); + PUSH_FIELD(p, payload[0]); + break; + + case FUN: + markQueuePushFunSrt(queue, info); + goto gen_obj; + + case THUNK: { + markQueuePushThunkSrt(queue, info); + for (StgWord i = 0; i < info->layout.payload.ptrs; i++) { + StgClosure **field = &((StgThunk *) p)->payload[i]; + markQueuePushClosure(queue, *field, field); + } + break; + } + + gen_obj: + case CONSTR: + case CONSTR_NOCAF: + case WEAK: + case PRIM: + { + for (StgWord i = 0; i < info->layout.payload.ptrs; i++) { + StgClosure **field = &((StgClosure *) p)->payload[i]; + markQueuePushClosure(queue, *field, field); + } + break; + } + + case BCO: { + StgBCO *bco = (StgBCO *)p; + PUSH_FIELD(bco, instrs); + PUSH_FIELD(bco, literals); + PUSH_FIELD(bco, ptrs); + break; + } + + + case THUNK_STATIC: + markQueuePushThunkSrt(queue, info); + break; + + case FUN_STATIC: + if (info->srt != 0 || info->layout.payload.ptrs != 0) { + markQueuePushThunkSrt(queue, info); + // a FUN_STATIC can also be an SRT, so it may have pointer + // fields. See Note [SRTs] in CmmBuildInfoTables, specifically + // the [FUN] optimisation. + // TODO (osa) I don't understand this comment + for (StgHalfWord i = 0; i < info->layout.payload.ptrs; ++i) { + PUSH_FIELD(p, payload[i]); + } + } + break; + + case IND_STATIC: + PUSH_FIELD((StgInd *) p, indirectee); + break; + + case IND: + case BLACKHOLE: { + PUSH_FIELD((StgInd *) p, indirectee); + break; + } + + case MUT_VAR_CLEAN: + case MUT_VAR_DIRTY: + PUSH_FIELD((StgMutVar *)p, var); + break; + + case BLOCKING_QUEUE: { + StgBlockingQueue *bq = (StgBlockingQueue *)p; + PUSH_FIELD(bq, bh); + PUSH_FIELD(bq, owner); + PUSH_FIELD(bq, queue); + PUSH_FIELD(bq, link); + break; + } + + case THUNK_SELECTOR: + PUSH_FIELD((StgSelector *) p, selectee); + break; + + case AP_STACK: { + StgAP_STACK *ap = (StgAP_STACK *)p; + PUSH_FIELD(ap, fun); + trace_stack_(queue, (StgPtr) ap->payload, (StgPtr) ap->payload + ap->size); + break; + } + + case PAP: { + StgPAP *pap = (StgPAP *) p; + PUSH_FIELD(pap, fun); + trace_PAP_payload(queue, pap->fun, pap->payload, pap->n_args); + break; + } + + case AP: { + StgAP *ap = (StgAP *) p; + PUSH_FIELD(ap, fun); + trace_PAP_payload(queue, ap->fun, ap->payload, ap->n_args); + break; + } + + case ARR_WORDS: + // nothing to follow + break; + + case MUT_ARR_PTRS_CLEAN: + case MUT_ARR_PTRS_DIRTY: + case MUT_ARR_PTRS_FROZEN_CLEAN: + case MUT_ARR_PTRS_FROZEN_DIRTY: + markQueuePushArray(queue, (StgMutArrPtrs *) p, 0); + break; + + case SMALL_MUT_ARR_PTRS_CLEAN: + case SMALL_MUT_ARR_PTRS_DIRTY: + case SMALL_MUT_ARR_PTRS_FROZEN_CLEAN: + case SMALL_MUT_ARR_PTRS_FROZEN_DIRTY: { + StgSmallMutArrPtrs *arr = (StgSmallMutArrPtrs *) p; + for (StgWord i = 0; i < arr->ptrs; i++) { + StgClosure **field = &arr->payload[i]; + markQueuePushClosure(queue, *field, field); + } + break; + } + + case TSO: + trace_tso(queue, (StgTSO *) p); + break; + + case STACK: { + // See Note [StgStack dirtiness flags and concurrent marking] + StgStack *stack = (StgStack *) p; + trace_stack(queue, stack); + break; + } + + case MUT_PRIM: { + for (StgHalfWord p_idx = 0; p_idx < info->layout.payload.ptrs; ++p_idx) { + StgClosure **field = &p->payload[p_idx]; + markQueuePushClosure(queue, *field, field); + } + break; + } + + case TREC_CHUNK: + trace_trec_chunk(queue, (StgTRecChunk *) p); + break; + + case WHITEHOLE: + barf("mark_check_closure: WHITEHOLE"); + + case COMPACT_NFDATA: + break; + + default: + barf("mark_check_closure: unimplemented/strange closure type %d @ %p", + info->type, p); + } + +# undef PUSH_FIELD +} + +/* + * Note [Non-moving mark check] + * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + * To ease debugging, the non-moving collector includes a sanity-checking + * facility called mark-checking. When enabled (using -DN) the collector will + * perform a second round of heap tracing during the sync pause, asserting that + * all reachable objects in the non-moving heap snapshot have been marked. This + * will often catch bugs (e.g. missing write barriers) long before they turn + * into a segmentation fault. + * + * To avoid affecting the heap state the mark check logic uses an out-of-band + * ClosureSet to record which closures it has already visited. + */ + +/* Verify that all live objects are marked. May only be called during the sync pause. */ +void nonmovingMarkCheck() { + MarkQueue queue; + initMarkQueue(&queue); + + ClosureSet checked; + closureSetInit(&checked); + + /* Push roots */ + /* TODO: other roots? */ + markCAFs((evac_fn)markQueueAddRoot, &queue); + markStablePtrTable((evac_fn)markQueueAddRoot, &queue); + markScheduler((evac_fn)markQueueAddRoot, &queue); + for (unsigned int n = 0; n < n_capabilities; ++n) { + markCapability((evac_fn)markQueueAddRoot, &queue, + capabilities[n], true/*don't mark sparks*/); + } + for (uint32_t g = 0; g < RtsFlags.GcFlags.generations; g++) { + for (StgTSO *t = generations[g].threads; t != END_TSO_QUEUE; t = t->global_link) { + trace_tso(&queue, t); + } + } + + /* Verify */ + while (true) { + MarkQueueEnt ent = markQueuePop(&queue); + + switch (nonmovingMarkQueueEntryType(&ent)) { + case MARK_CLOSURE: + mark_check_closure(&checked, &queue, ent.mark_closure.p); + break; + case MARK_ARRAY: { + const StgMutArrPtrs *arr = (const StgMutArrPtrs *) + UNTAG_CLOSURE((StgClosure *) ent.mark_array.array); + StgWord start = ent.mark_array.start_index; + StgWord end = start + MARK_ARRAY_CHUNK_LENGTH; + if (end < arr->ptrs) { + // There is more to be marked after this chunk. + markQueuePushArray(&queue, arr, end); + } else { + end = arr->ptrs; + } + for (StgWord i = start; i < end; i++) { + mark_check_closure(&checked, &queue, arr->payload[i]); + } + break; + } + case NULL_ENTRY: + return; + } + } + + freeMarkQueue(&queue); + closureSetFree(&checked); +} + +#endif /* defined(NONMOVING_MARK_CHECK) */ + #if defined(DEBUG) void printMarkQueueEntry (MarkQueueEnt *ent) diff --git a/rts/sm/NonMovingMark.h b/rts/sm/NonMovingMark.h index 0938e2775a..17cfc246cb 100644 --- a/rts/sm/NonMovingMark.h +++ b/rts/sm/NonMovingMark.h @@ -184,6 +184,12 @@ INLINE_HEADER bool markQueueIsEmpty(MarkQueue *q) return (q->blocks == NULL) || (q->top->head == 0 && q->blocks->link == NULL); } +#if defined(NONMOVING_MARK_CHECK) +void nonmovingMarkCheck(void); +#else +INLINE_HEADER void nonmovingMarkCheck(void) {} +#endif + #if defined(DEBUG) void printMarkQueueEntry(MarkQueueEnt *ent); |