diff options
| -rw-r--r-- | includes/Rts.h | 4 | ||||
| -rw-r--r-- | libraries/base/tests/all.T | 2 | ||||
| -rw-r--r-- | libraries/ghc-heap/tests/all.T | 6 | ||||
| -rw-r--r-- | rts/Schedule.c | 23 | ||||
| -rw-r--r-- | rts/sm/Evac.c | 67 | ||||
| -rw-r--r-- | rts/sm/GC.c | 35 | ||||
| -rw-r--r-- | rts/sm/GC.h | 9 | ||||
| -rw-r--r-- | rts/sm/GCAux.c | 4 | ||||
| -rw-r--r-- | rts/sm/NonMoving.c | 237 | ||||
| -rw-r--r-- | rts/sm/NonMoving.h | 47 | ||||
| -rw-r--r-- | rts/sm/NonMovingMark.c | 269 | ||||
| -rw-r--r-- | rts/sm/NonMovingMark.h | 44 | ||||
| -rw-r--r-- | rts/sm/NonMovingScav.c | 45 | ||||
| -rw-r--r-- | rts/sm/NonMovingSweep.c | 159 | ||||
| -rw-r--r-- | rts/sm/NonMovingSweep.h | 6 | ||||
| -rw-r--r-- | rts/sm/Storage.c | 70 | ||||
| -rw-r--r-- | testsuite/config/ghc | 12 | ||||
| -rw-r--r-- | testsuite/tests/codeGen/should_run/all.T | 11 | ||||
| -rw-r--r-- | testsuite/tests/concurrent/should_run/all.T | 14 | ||||
| -rw-r--r-- | testsuite/tests/perf/compiler/all.T | 4 | ||||
| -rw-r--r-- | testsuite/tests/rts/all.T | 15 |
21 files changed, 850 insertions, 233 deletions
diff --git a/includes/Rts.h b/includes/Rts.h index def06de90d..7ad6988f3b 100644 --- a/includes/Rts.h +++ b/includes/Rts.h @@ -74,6 +74,10 @@ extern "C" { #define RTS_UNREACHABLE abort() #endif +/* Prefetch primitives */ +#define prefetchForRead(ptr) __builtin_prefetch(ptr, 0) +#define prefetchForWrite(ptr) __builtin_prefetch(ptr, 1) + /* Fix for mingw stat problem (done here so it's early enough) */ #if defined(mingw32_HOST_OS) #define __MSVCRT__ 1 diff --git a/libraries/base/tests/all.T b/libraries/base/tests/all.T index 0b45c9aff2..0242ece32e 100644 --- a/libraries/base/tests/all.T +++ b/libraries/base/tests/all.T @@ -74,7 +74,7 @@ test('length001', # excessive amounts of stack space. So we specifically set a low # stack limit and mark it as failing under a few conditions. [extra_run_opts('+RTS -K8m -RTS'), - expect_fail_for(['normal', 'threaded1', 'llvm'])], + expect_fail_for(['normal', 'threaded1', 'llvm', 'nonmoving', 'nonmoving_thr', 'nonmoving_thr_ghc'])], compile_and_run, ['']) test('ratio001', normal, compile_and_run, ['']) diff --git a/libraries/ghc-heap/tests/all.T b/libraries/ghc-heap/tests/all.T index afa224fde7..89e6f47ecb 100644 --- a/libraries/ghc-heap/tests/all.T +++ b/libraries/ghc-heap/tests/all.T @@ -2,7 +2,11 @@ test('heap_all', [when(have_profiling(), extra_ways(['prof'])), # These ways produce slightly different heap representations. # Currently we don't test them. - omit_ways(['ghci', 'hpc']) + omit_ways(['ghci', 'hpc', + 'nonmoving', 'nonmoving_thr', 'nonmoving_thr_ghc']), + # The debug RTS initializes some fields with 0xaa and so + # this test spuriously fails. + when(compiler_debugged(), skip) ], compile_and_run, ['']) diff --git a/rts/Schedule.c b/rts/Schedule.c index f66a276602..5387bc615e 100644 --- a/rts/Schedule.c +++ b/rts/Schedule.c @@ -164,7 +164,8 @@ static void scheduleHandleThreadBlocked( StgTSO *t ); static bool scheduleHandleThreadFinished( Capability *cap, Task *task, StgTSO *t ); static bool scheduleNeedHeapProfile(bool ready_to_gc); -static void scheduleDoGC(Capability **pcap, Task *task, bool force_major); +static void scheduleDoGC( Capability **pcap, Task *task, + bool force_major, bool deadlock_detect ); static void deleteThread (StgTSO *tso); static void deleteAllThreads (void); @@ -264,7 +265,7 @@ schedule (Capability *initialCapability, Task *task) case SCHED_INTERRUPTING: debugTrace(DEBUG_sched, "SCHED_INTERRUPTING"); /* scheduleDoGC() deletes all the threads */ - scheduleDoGC(&cap,task,true); + scheduleDoGC(&cap,task,true,false); // after scheduleDoGC(), we must be shutting down. Either some // other Capability did the final GC, or we did it above, @@ -561,7 +562,7 @@ run_thread: } if (ready_to_gc || scheduleNeedHeapProfile(ready_to_gc)) { - scheduleDoGC(&cap,task,false); + scheduleDoGC(&cap,task,false,false); } } /* end of while() */ } @@ -935,7 +936,7 @@ scheduleDetectDeadlock (Capability **pcap, Task *task) // they are unreachable and will therefore be sent an // exception. Any threads thus released will be immediately // runnable. - scheduleDoGC (pcap, task, true/*force major GC*/); + scheduleDoGC (pcap, task, true/*force major GC*/, true/*deadlock detection*/); cap = *pcap; // when force_major == true. scheduleDoGC sets // recent_activity to ACTIVITY_DONE_GC and turns off the timer @@ -1005,7 +1006,7 @@ scheduleProcessInbox (Capability **pcap USED_IF_THREADS) while (!emptyInbox(cap)) { // Executing messages might use heap, so we should check for GC. if (doYouWantToGC(cap)) { - scheduleDoGC(pcap, cap->running_task, false); + scheduleDoGC(pcap, cap->running_task, false, false); cap = *pcap; } @@ -1552,9 +1553,11 @@ void releaseAllCapabilities(uint32_t n, Capability *keep_cap, Task *task) * Perform a garbage collection if necessary * -------------------------------------------------------------------------- */ +// N.B. See Note [Deadlock detection under nonmoving collector] for rationale +// behind deadlock_detect argument. static void scheduleDoGC (Capability **pcap, Task *task USED_IF_THREADS, - bool force_major) + bool force_major, bool deadlock_detect) { Capability *cap = *pcap; bool heap_census; @@ -1847,9 +1850,9 @@ delete_threads_and_gc: // emerge they don't immediately re-enter the GC. pending_sync = 0; signalCondition(&sync_finished_cond); - GarbageCollect(collect_gen, heap_census, gc_type, cap, idle_cap); + GarbageCollect(collect_gen, heap_census, deadlock_detect, gc_type, cap, idle_cap); #else - GarbageCollect(collect_gen, heap_census, 0, cap, NULL); + GarbageCollect(collect_gen, heap_census, deadlock_detect, 0, cap, NULL); #endif // If we're shutting down, don't leave any idle GC work to do. @@ -2717,7 +2720,7 @@ exitScheduler (bool wait_foreign USED_IF_THREADS) nonmovingStop(); Capability *cap = task->cap; waitForCapability(&cap,task); - scheduleDoGC(&cap,task,true); + scheduleDoGC(&cap,task,true,false); ASSERT(task->incall->tso == NULL); releaseCapability(cap); } @@ -2785,7 +2788,7 @@ performGC_(bool force_major) // TODO: do we need to traceTask*() here? waitForCapability(&cap,task); - scheduleDoGC(&cap,task,force_major); + scheduleDoGC(&cap,task,force_major,false); releaseCapability(cap); boundTaskExiting(task); } diff --git a/rts/sm/Evac.c b/rts/sm/Evac.c index c2aaaacffa..f8ee2630b6 100644 --- a/rts/sm/Evac.c +++ b/rts/sm/Evac.c @@ -69,12 +69,6 @@ alloc_for_copy (uint32_t size, uint32_t gen_no) { ASSERT(gen_no < RtsFlags.GcFlags.generations); - if (RtsFlags.GcFlags.useNonmoving && major_gc) { - // unconditionally promote to non-moving heap in major gc - gct->copied += size; - return nonmovingAllocate(gct->cap, size); - } - StgPtr to; gen_workspace *ws; @@ -91,9 +85,34 @@ alloc_for_copy (uint32_t size, uint32_t gen_no) } } - if (RtsFlags.GcFlags.useNonmoving && gen_no == oldest_gen->no) { - gct->copied += size; - return nonmovingAllocate(gct->cap, size); + if (RtsFlags.GcFlags.useNonmoving) { + /* See Note [Deadlock detection under nonmoving collector]. */ + if (deadlock_detect_gc) + gen_no = oldest_gen->no; + + if (gen_no == oldest_gen->no) { + gct->copied += size; + to = nonmovingAllocate(gct->cap, size); + + // Add segment to the todo list unless it's already there + // current->todo_link == NULL means not in todo list + struct NonmovingSegment *seg = nonmovingGetSegment(to); + if (!seg->todo_link) { + gen_workspace *ws = &gct->gens[oldest_gen->no]; + seg->todo_link = ws->todo_seg; + ws->todo_seg = seg; + } + + // The object which refers to this closure may have been aged (i.e. + // retained in a younger generation). Consequently, we must add the + // closure to the mark queue to ensure that it will be marked. + // + // However, if we are in a deadlock detection GC then we disable aging + // so there is no need. + if (major_gc && !deadlock_detect_gc) + markQueuePushClosureGC(&gct->cap->upd_rem_set.queue, (StgClosure *) to); + return to; + } } ws = &gct->gens[gen_no]; // zero memory references here @@ -312,9 +331,10 @@ evacuate_large(StgPtr p) */ new_gen_no = bd->dest_no; - if (RtsFlags.GcFlags.useNonmoving && major_gc) { + if (deadlock_detect_gc) { + /* See Note [Deadlock detection under nonmoving collector]. */ new_gen_no = oldest_gen->no; - } else if (new_gen_no < gct->evac_gen_no) { + } else if (new_gen_no < gct->evac_gen_no) { if (gct->eager_promotion) { new_gen_no = gct->evac_gen_no; } else { @@ -363,6 +383,13 @@ evacuate_large(StgPtr p) STATIC_INLINE void evacuate_static_object (StgClosure **link_field, StgClosure *q) { + if (RTS_UNLIKELY(RtsFlags.GcFlags.useNonmoving)) { + // See Note [Static objects under the nonmoving collector] in Storage.c. + if (major_gc && !deadlock_detect_gc) + markQueuePushClosureGC(&gct->cap->upd_rem_set.queue, q); + return; + } + StgWord link = (StgWord)*link_field; // See Note [STATIC_LINK fields] for how the link field bits work @@ -603,6 +630,8 @@ loop: // NOTE: large objects in nonmoving heap are also marked with // BF_NONMOVING. Those are moved to scavenged_large_objects list in // mark phase. + if (major_gc && !deadlock_detect_gc) + markQueuePushClosureGC(&gct->cap->upd_rem_set.queue, q); return; } @@ -629,6 +658,13 @@ loop: // they are not) if (bd->flags & BF_COMPACT) { evacuate_compact((P_)q); + + // We may have evacuated the block to the nonmoving generation. If so + // we need to make sure it is added to the mark queue since the only + // reference to it may be from the moving heap. + if (major_gc && bd->flags & BF_NONMOVING && !deadlock_detect_gc) { + markQueuePushClosureGC(&gct->cap->upd_rem_set.queue, q); + } return; } @@ -636,6 +672,13 @@ loop: */ if (bd->flags & BF_LARGE) { evacuate_large((P_)q); + + // We may have evacuated the block to the nonmoving generation. If so + // we need to make sure it is added to the mark queue since the only + // reference to it may be from the moving heap. + if (major_gc && bd->flags & BF_NONMOVING && !deadlock_detect_gc) { + markQueuePushClosureGC(&gct->cap->upd_rem_set.queue, q); + } return; } @@ -937,6 +980,8 @@ evacuate_BLACKHOLE(StgClosure **p) ASSERT((bd->flags & BF_COMPACT) == 0); if (bd->flags & BF_NONMOVING) { + if (major_gc && !deadlock_detect_gc) + markQueuePushClosureGC(&gct->cap->upd_rem_set.queue, q); return; } diff --git a/rts/sm/GC.c b/rts/sm/GC.c index 37f9811aaf..83e9c97bd9 100644 --- a/rts/sm/GC.c +++ b/rts/sm/GC.c @@ -104,6 +104,7 @@ */ uint32_t N; bool major_gc; +bool deadlock_detect_gc; /* Data used for allocation area sizing. */ @@ -194,6 +195,7 @@ StgPtr mark_sp; // pointer to the next unallocated mark stack entry void GarbageCollect (uint32_t collect_gen, const bool do_heap_census, + const bool deadlock_detect, uint32_t gc_type USED_IF_THREADS, Capability *cap, bool idle_cap[]) @@ -263,7 +265,25 @@ GarbageCollect (uint32_t collect_gen, N = collect_gen; major_gc = (N == RtsFlags.GcFlags.generations-1); - if (major_gc) { + /* See Note [Deadlock detection under nonmoving collector]. */ + deadlock_detect_gc = deadlock_detect; + +#if defined(THREADED_RTS) + if (major_gc && RtsFlags.GcFlags.useNonmoving && concurrent_coll_running) { + /* If there is already a concurrent major collection running then + * there is no benefit to starting another. + * TODO: Catch heap-size runaway. + */ + N--; + collect_gen--; + major_gc = false; + } +#endif + + /* N.B. The nonmoving collector works a bit differently. See + * Note [Static objects under the nonmoving collector]. + */ + if (major_gc && !RtsFlags.GcFlags.useNonmoving) { prev_static_flag = static_flag; static_flag = static_flag == STATIC_FLAG_A ? STATIC_FLAG_B : STATIC_FLAG_A; @@ -710,6 +730,14 @@ GarbageCollect (uint32_t collect_gen, } } // for all generations + // Flush the update remembered set. See Note [Eager update remembered set + // flushing] in NonMovingMark.c + if (RtsFlags.GcFlags.useNonmoving) { + RELEASE_SM_LOCK; + nonmovingAddUpdRemSetBlocks(&gct->cap->upd_rem_set.queue); + ACQUIRE_SM_LOCK; + } + // Mark and sweep the oldest generation. // N.B. This can only happen after we've moved // oldest_gen->scavenged_large_objects back to oldest_gen->large_objects. @@ -736,6 +764,11 @@ GarbageCollect (uint32_t collect_gen, // so we need to mark those too. // Note that in sequential case these lists will be appended with more // weaks and threads found to be dead in mark. +#if !defined(THREADED_RTS) + // In the non-threaded runtime this is the only time we push to the + // upd_rem_set + nonmovingAddUpdRemSetBlocks(&gct->cap->upd_rem_set.queue); +#endif nonmovingCollect(&dead_weak_ptr_list, &resurrected_threads); ACQUIRE_SM_LOCK; } diff --git a/rts/sm/GC.h b/rts/sm/GC.h index ed19b8bddf..bde006913b 100644 --- a/rts/sm/GC.h +++ b/rts/sm/GC.h @@ -17,9 +17,12 @@ #include "HeapAlloc.h" -void GarbageCollect (uint32_t force_major_gc, +void GarbageCollect (uint32_t collect_gen, bool do_heap_census, - uint32_t gc_type, Capability *cap, bool idle_cap[]); + bool deadlock_detect, + uint32_t gc_type, + Capability *cap, + bool idle_cap[]); typedef void (*evac_fn)(void *user, StgClosure **root); @@ -30,6 +33,8 @@ bool doIdleGCWork(Capability *cap, bool all); extern uint32_t N; extern bool major_gc; +/* See Note [Deadlock detection under nonmoving collector]. */ +extern bool deadlock_detect_gc; extern bdescr *mark_stack_bd; extern bdescr *mark_stack_top_bd; diff --git a/rts/sm/GCAux.c b/rts/sm/GCAux.c index 6076f61d6f..11080c1f22 100644 --- a/rts/sm/GCAux.c +++ b/rts/sm/GCAux.c @@ -148,14 +148,14 @@ markCAFs (evac_fn evac, void *user) StgIndStatic *c; for (c = dyn_caf_list; - c != (StgIndStatic*)END_OF_CAF_LIST; + ((StgWord) c | STATIC_FLAG_LIST) != (StgWord)END_OF_CAF_LIST; c = (StgIndStatic *)c->static_link) { c = (StgIndStatic *)UNTAG_STATIC_LIST_PTR(c); evac(user, &c->indirectee); } for (c = revertible_caf_list; - c != (StgIndStatic*)END_OF_CAF_LIST; + ((StgWord) c | STATIC_FLAG_LIST) != (StgWord)END_OF_CAF_LIST; c = (StgIndStatic *)c->static_link) { c = (StgIndStatic *)UNTAG_STATIC_LIST_PTR(c); diff --git a/rts/sm/NonMoving.c b/rts/sm/NonMoving.c index 1d504bd0fc..6dc1010d43 100644 --- a/rts/sm/NonMoving.c +++ b/rts/sm/NonMoving.c @@ -69,6 +69,113 @@ Mutex concurrent_coll_finished_lock; * stopAllCapabilitiesWith(SYNC_FLUSH_UPD_REM_SET). Capabilities are held * the final mark has concluded. * + * Note that possibility of concurrent minor and non-moving collections + * requires that we handle static objects a bit specially. See + * Note [Static objects under the nonmoving collector] in Storage.c + * for details. + * + * + * Note [Aging under the non-moving collector] + * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + * + * The initial design of the non-moving collector mandated that all live data + * be evacuated to the non-moving heap prior to a major collection. This + * simplified certain bits of implementation and eased reasoning. However, it + * was (unsurprisingly) also found to result in significant amounts of + * unnecessary copying. + * + * Consequently, we now allow aging. Aging allows the preparatory GC leading up + * to a major collection to evacuate some objects into the young generation. + * However, this introduces the following tricky case that might arise after + * we have finished the preparatory GC: + * + * moving heap ┆ non-moving heap + * ───────────────┆────────────────── + * ┆ + * B ←────────────── A ←─────────────── root + * │ ┆ ↖─────────────── gen1 mut_list + * ╰───────────────→ C + * ┆ + * + * In this case C is clearly live, but the non-moving collector can only see + * this by walking through B, which lives in the moving heap. However, doing so + * would require that we synchronize with the mutator/minor GC to ensure that it + * isn't in the middle of moving B. What to do? + * + * The solution we use here is to teach the preparatory moving collector to + * "evacuate" objects it encounters in the non-moving heap by adding them to + * the mark queue. This is implemented by pushing the object to the update + * remembered set of the capability held by the evacuating gc_thread + * (implemented by markQueuePushClosureGC) + * + * Consequently collection of the case above would proceed as follows: + * + * 1. Initial state: + * * A lives in the non-moving heap and is reachable from the root set + * * A is on the oldest generation's mut_list, since it contains a pointer + * to B, which lives in a younger generation + * * B lives in the moving collector's from space + * * C lives in the non-moving heap + * + * 2. Preparatory GC: Scavenging mut_lists: + * + * The mut_list of the oldest generation is scavenged, resulting in B being + * evacuated (aged) into the moving collector's to-space. + * + * 3. Preparatory GC: Scavenge B + * + * B (now in to-space) is scavenged, resulting in evacuation of C. + * evacuate(C) pushes a reference to C to the mark queue. + * + * 4. Non-moving GC: C is marked + * + * The non-moving collector will come to C in the mark queue and mark it. + * + * + * Note [Deadlock detection under the non-moving collector] + * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + * In GHC the garbage collector is responsible for identifying deadlocked + * programs. Providing for this responsibility is slightly tricky in the + * non-moving collector due to the existence of aging. In particular, the + * non-moving collector cannot traverse objects living in a young generation + * but reachable from the non-moving generation, as described in Note [Aging + * under the non-moving collector]. + * + * However, this can pose trouble for deadlock detection since it means that we + * may conservatively mark dead closures as live. Consider this case: + * + * moving heap ┆ non-moving heap + * ───────────────┆────────────────── + * ┆ + * MVAR_QUEUE ←───── TSO ←───────────── gen1 mut_list + * ↑ │ ╰────────↗ │ + * │ │ ┆ │ + * │ │ ┆ ↓ + * │ ╰──────────→ MVAR + * ╰─────────────────╯ + * ┆ + * + * In this case we have a TSO blocked on a dead MVar. Because the MVAR_TSO_QUEUE on + * which it is blocked lives in the moving heap, the TSO is necessarily on the + * oldest generation's mut_list. As in Note [Aging under the non-moving + * collector], the MVAR_TSO_QUEUE will be evacuated. If MVAR_TSO_QUEUE is aged + * (e.g. evacuated to the young generation) then the MVAR will be added to the + * mark queue. Consequently, we will falsely conclude that the MVAR is still + * alive and fail to spot the deadlock. + * + * To avoid this sort of situation we disable aging when we are starting a + * major GC specifically for deadlock detection (as done by + * scheduleDetectDeadlock). This condition is recorded by the + * deadlock_detect_gc global variable declared in GC.h. Setting this has a few + * effects on the preparatory GC: + * + * - Evac.c:alloc_for_copy forces evacuation to the non-moving generation. + * + * - The evacuation logic usually responsible for pushing objects living in + * the non-moving heap to the mark queue is disabled. This is safe because + * we know that all live objects will be in the non-moving heap by the end + * of the preparatory moving collection. + * * * Note [Live data accounting in nonmoving collector] * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -147,10 +254,26 @@ static struct NonmovingSegment *nonmovingPopFreeSegment(void) } } +unsigned int nonmovingBlockCountFromSize(uint8_t log_block_size) +{ + // We compute the overwhelmingly common size cases directly to avoid a very + // expensive integer division. + switch (log_block_size) { + case 3: return nonmovingBlockCount(3); + case 4: return nonmovingBlockCount(4); + case 5: return nonmovingBlockCount(5); + case 6: return nonmovingBlockCount(6); + case 7: return nonmovingBlockCount(7); + default: return nonmovingBlockCount(log_block_size); + } +} + /* * Request a fresh segment from the free segment list or allocate one of the * given node. * + * Caller must hold SM_MUTEX (although we take the gc_alloc_block_sync spinlock + * under the assumption that we are in a GC context). */ static struct NonmovingSegment *nonmovingAllocSegment(uint32_t node) { @@ -193,10 +316,12 @@ static inline unsigned long log2_ceil(unsigned long x) } // Advance a segment's next_free pointer. Returns true if segment if full. -static bool advance_next_free(struct NonmovingSegment *seg) +static bool advance_next_free(struct NonmovingSegment *seg, const unsigned int blk_count) { - uint8_t *bitmap = seg->bitmap; - unsigned int blk_count = nonmovingSegmentBlockCount(seg); + const uint8_t *bitmap = seg->bitmap; + ASSERT(blk_count == nonmovingSegmentBlockCount(seg)); +#if defined(NAIVE_ADVANCE_FREE) + // reference implementation for (unsigned int i = seg->next_free+1; i < blk_count; i++) { if (!bitmap[i]) { seg->next_free = i; @@ -205,6 +330,16 @@ static bool advance_next_free(struct NonmovingSegment *seg) } seg->next_free = blk_count; return true; +#else + const uint8_t *c = memchr(&bitmap[seg->next_free+1], 0, blk_count - seg->next_free - 1); + if (c == NULL) { + seg->next_free = blk_count; + return true; + } else { + seg->next_free = c - bitmap; + return false; + } +#endif } static struct NonmovingSegment *pop_active_segment(struct NonmovingAllocator *alloca) @@ -222,34 +357,27 @@ static struct NonmovingSegment *pop_active_segment(struct NonmovingAllocator *al } } -/* sz is in words */ +/* Allocate a block in the nonmoving heap. Caller must hold SM_MUTEX. sz is in words */ GNUC_ATTR_HOT void *nonmovingAllocate(Capability *cap, StgWord sz) { - unsigned int allocator_idx = log2_ceil(sz * sizeof(StgWord)) - NONMOVING_ALLOCA0; + unsigned int log_block_size = log2_ceil(sz * sizeof(StgWord)); + unsigned int block_count = nonmovingBlockCountFromSize(log_block_size); // The max we ever allocate is 3276 bytes (anything larger is a large // object and not moved) which is covered by allocator 9. - ASSERT(allocator_idx < NONMOVING_ALLOCA_CNT); + ASSERT(log_block_size < NONMOVING_ALLOCA0 + NONMOVING_ALLOCA_CNT); - struct NonmovingAllocator *alloca = nonmovingHeap.allocators[allocator_idx]; + struct NonmovingAllocator *alloca = nonmovingHeap.allocators[log_block_size - NONMOVING_ALLOCA0]; // Allocate into current segment struct NonmovingSegment *current = alloca->current[cap->no]; ASSERT(current); // current is never NULL - void *ret = nonmovingSegmentGetBlock(current, current->next_free); + void *ret = nonmovingSegmentGetBlock_(current, log_block_size, current->next_free); ASSERT(GET_CLOSURE_TAG(ret) == 0); // check alignment - // Add segment to the todo list unless it's already there - // current->todo_link == NULL means not in todo list - if (!current->todo_link) { - gen_workspace *ws = &gct->gens[oldest_gen->no]; - current->todo_link = ws->todo_seg; - ws->todo_seg = current; - } - // Advance the current segment's next_free or allocate a new segment if full - bool full = advance_next_free(current); + bool full = advance_next_free(current, block_count); if (full) { // Current segment is full: update live data estimate link it to // filled, take an active segment if one exists, otherwise allocate a @@ -257,8 +385,9 @@ void *nonmovingAllocate(Capability *cap, StgWord sz) // Update live data estimate. // See Note [Live data accounting in nonmoving collector]. - unsigned int new_blocks = nonmovingSegmentBlockCount(current) - current->next_free_snap; - atomic_inc(&oldest_gen->live_estimate, new_blocks * nonmovingSegmentBlockSize(current) / sizeof(W_)); + unsigned int new_blocks = block_count - current->next_free_snap; + unsigned int block_size = 1 << log_block_size; + atomic_inc(&oldest_gen->live_estimate, new_blocks * block_size / sizeof(W_)); // push the current segment to the filled list nonmovingPushFilledSegment(current); @@ -269,7 +398,7 @@ void *nonmovingAllocate(Capability *cap, StgWord sz) // there are no active segments, allocate new segment if (new_current == NULL) { new_current = nonmovingAllocSegment(cap->node); - nonmovingInitSegment(new_current, NONMOVING_ALLOCA0 + allocator_idx); + nonmovingInitSegment(new_current, log_block_size); } // make it current @@ -376,37 +505,23 @@ void nonmovingAddCapabilities(uint32_t new_n_caps) nonmovingHeap.n_caps = new_n_caps; } -static void nonmovingClearBitmap(struct NonmovingSegment *seg) +static inline void nonmovingClearBitmap(struct NonmovingSegment *seg) { unsigned int n = nonmovingSegmentBlockCount(seg); memset(seg->bitmap, 0, n); } -static void nonmovingClearSegmentBitmaps(struct NonmovingSegment *seg) -{ - while (seg) { - nonmovingClearBitmap(seg); - seg = seg->link; - } -} - -static void nonmovingClearAllBitmaps(void) -{ - for (int alloca_idx = 0; alloca_idx < NONMOVING_ALLOCA_CNT; ++alloca_idx) { - struct NonmovingAllocator *alloca = nonmovingHeap.allocators[alloca_idx]; - nonmovingClearSegmentBitmaps(alloca->filled); - } - - // Clear large object bits - for (bdescr *bd = nonmoving_large_objects; bd; bd = bd->link) { - bd->flags &= ~BF_MARKED; - } -} - /* Prepare the heap bitmaps and snapshot metadata for a mark */ static void nonmovingPrepareMark(void) { - nonmovingClearAllBitmaps(); + // See Note [Static objects under the nonmoving collector]. + prev_static_flag = static_flag; + static_flag = + static_flag == STATIC_FLAG_A ? STATIC_FLAG_B : STATIC_FLAG_A; + + // Should have been cleared by the last sweep + ASSERT(nonmovingHeap.sweep_list == NULL); + nonmovingBumpEpoch(); for (int alloca_idx = 0; alloca_idx < NONMOVING_ALLOCA_CNT; ++alloca_idx) { struct NonmovingAllocator *alloca = nonmovingHeap.allocators[alloca_idx]; @@ -417,11 +532,28 @@ static void nonmovingPrepareMark(void) seg->next_free_snap = seg->next_free; } - // Update filled segments' snapshot pointers - struct NonmovingSegment *seg = alloca->filled; - while (seg) { - seg->next_free_snap = seg->next_free; - seg = seg->link; + // Update filled segments' snapshot pointers and move to sweep_list + uint32_t n_filled = 0; + struct NonmovingSegment *const filled = alloca->filled; + alloca->filled = NULL; + if (filled) { + struct NonmovingSegment *seg = filled; + while (true) { + n_filled++; + prefetchForRead(seg->link); + // Clear bitmap + prefetchForWrite(seg->link->bitmap); + nonmovingClearBitmap(seg); + // Set snapshot + seg->next_free_snap = seg->next_free; + if (seg->link) + seg = seg->link; + else + break; + } + // add filled segments to sweep_list + seg->link = nonmovingHeap.sweep_list; + nonmovingHeap.sweep_list = filled; } // N.B. It's not necessary to update snapshot pointers of active segments; @@ -442,6 +574,12 @@ static void nonmovingPrepareMark(void) oldest_gen->n_large_blocks = 0; nonmoving_live_words = 0; + // Clear large object bits + for (bdescr *bd = nonmoving_large_objects; bd; bd = bd->link) { + bd->flags &= ~BF_MARKED; + } + + #if defined(DEBUG) debug_caf_list_snapshot = debug_caf_list; debug_caf_list = (StgIndStatic*)END_OF_CAF_LIST; @@ -492,7 +630,6 @@ void nonmovingCollect(StgWeak **dead_weaks, StgTSO **resurrected_threads) resizeGenerations(); nonmovingPrepareMark(); - nonmovingPrepareSweep(); // N.B. These should have been cleared at the end of the last sweep. ASSERT(nonmoving_marked_large_objects == NULL); @@ -689,7 +826,7 @@ static void nonmovingMark_(MarkQueue *mark_queue, StgWeak **dead_weaks, StgTSO * #if defined(DEBUG) // Zap CAFs that we will sweep - nonmovingGcCafs(mark_queue); + nonmovingGcCafs(); #endif ASSERT(mark_queue->top->head == 0); diff --git a/rts/sm/NonMoving.h b/rts/sm/NonMoving.h index 0f9cfa0e48..17adfd6666 100644 --- a/rts/sm/NonMoving.h +++ b/rts/sm/NonMoving.h @@ -93,6 +93,10 @@ extern struct NonmovingHeap nonmovingHeap; extern memcount nonmoving_live_words; +#if defined(THREADED_RTS) +extern bool concurrent_coll_running; +#endif + void nonmovingInit(void); void nonmovingStop(void); void nonmovingExit(void); @@ -161,22 +165,34 @@ INLINE_HEADER unsigned int nonmovingSegmentBlockSize(struct NonmovingSegment *se return 1 << seg->block_size; } -// How many blocks does the given segment contain? Also the size of the bitmap. -INLINE_HEADER unsigned int nonmovingSegmentBlockCount(struct NonmovingSegment *seg) +// How many blocks does a segment with the given block size have? +INLINE_HEADER unsigned int nonmovingBlockCount(uint8_t log_block_size) { - unsigned int sz = nonmovingSegmentBlockSize(seg); unsigned int segment_data_size = NONMOVING_SEGMENT_SIZE - sizeof(struct NonmovingSegment); segment_data_size -= segment_data_size % SIZEOF_VOID_P; - return segment_data_size / (sz + 1); + unsigned int blk_size = 1 << log_block_size; + // N.B. +1 accounts for the byte in the mark bitmap. + return segment_data_size / (blk_size + 1); } -// Get a pointer to the given block index -INLINE_HEADER void *nonmovingSegmentGetBlock(struct NonmovingSegment *seg, nonmoving_block_idx i) +unsigned int nonmovingBlockCountFromSize(uint8_t log_block_size); + +// How many blocks does the given segment contain? Also the size of the bitmap. +INLINE_HEADER unsigned int nonmovingSegmentBlockCount(struct NonmovingSegment *seg) +{ + return nonmovingBlockCountFromSize(seg->block_size); +} + +// Get a pointer to the given block index assuming that the block size is as +// given (avoiding a potential cache miss when this information is already +// available). The log_block_size argument must be equal to seg->block_size. +INLINE_HEADER void *nonmovingSegmentGetBlock_(struct NonmovingSegment *seg, uint8_t log_block_size, nonmoving_block_idx i) { + ASSERT(log_block_size == seg->block_size); // Block size in bytes - unsigned int blk_size = nonmovingSegmentBlockSize(seg); + unsigned int blk_size = 1 << log_block_size; // Bitmap size in bytes - W_ bitmap_size = nonmovingSegmentBlockCount(seg) * sizeof(uint8_t); + W_ bitmap_size = nonmovingBlockCountFromSize(log_block_size) * sizeof(uint8_t); // Where the actual data starts (address of the first block). // Use ROUNDUP_BYTES_TO_WDS to align to word size. Note that // ROUNDUP_BYTES_TO_WDS returns in _words_, not in _bytes_, so convert it back @@ -185,15 +201,26 @@ INLINE_HEADER void *nonmovingSegmentGetBlock(struct NonmovingSegment *seg, nonmo return (void*)(data + i*blk_size); } +// Get a pointer to the given block index. +INLINE_HEADER void *nonmovingSegmentGetBlock(struct NonmovingSegment *seg, nonmoving_block_idx i) +{ + return nonmovingSegmentGetBlock_(seg, seg->block_size, i); +} + // Get the segment which a closure resides in. Assumes that pointer points into // non-moving heap. -INLINE_HEADER struct NonmovingSegment *nonmovingGetSegment(StgPtr p) +INLINE_HEADER struct NonmovingSegment *nonmovingGetSegment_unchecked(StgPtr p) { - ASSERT(HEAP_ALLOCED_GC(p) && (Bdescr(p)->flags & BF_NONMOVING)); const uintptr_t mask = ~NONMOVING_SEGMENT_MASK; return (struct NonmovingSegment *) (((uintptr_t) p) & mask); } +INLINE_HEADER struct NonmovingSegment *nonmovingGetSegment(StgPtr p) +{ + ASSERT(HEAP_ALLOCED_GC(p) && (Bdescr(p)->flags & BF_NONMOVING)); + return nonmovingGetSegment_unchecked(p); +} + INLINE_HEADER nonmoving_block_idx nonmovingGetBlockIdx(StgPtr p) { ASSERT(HEAP_ALLOCED_GC(p) && (Bdescr(p)->flags & BF_NONMOVING)); diff --git a/rts/sm/NonMovingMark.c b/rts/sm/NonMovingMark.c index 050b7ca24f..bb5d72bbf1 100644 --- a/rts/sm/NonMovingMark.c +++ b/rts/sm/NonMovingMark.c @@ -131,6 +131,49 @@ StgIndStatic *debug_caf_list_snapshot = (StgIndStatic*)END_OF_CAF_LIST; * The mark phase is responsible for freeing update remembered set block * allocations. * + * Note that we eagerly flush update remembered sets during minor GCs as + * described in Note [Eager update remembered set flushing]. + * + * + * Note [Eager update remembered set flushing] + * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + * + * We eagerly flush update remembered sets during minor GCs to avoid scenarios + * like the following which could result in long sync pauses: + * + * 1. We start a major GC, all thread stacks are added to the mark queue. + * 2. The concurrent mark thread starts. + * 3. The mutator is allowed to resume. One mutator thread T is scheduled and marks its + * stack to its local update remembered set. + * 4. The mark thread eventually encounters the mutator thread's stack but + * sees that it has already been marked; skips it. + * 5. Thread T continues running but does not push enough to its update + * remembered set to require a flush. + * 6. Eventually the mark thread finished marking and requests a final sync. + * 7. The thread T flushes its update remembered set. + * 8. We find that a large fraction of the heap (namely the subset that is + * only reachable from the thread T's stack) needs to be marked, incurring + * a large sync pause + * + * We avoid this by periodically (during minor GC) forcing a flush of the + * update remembered set. + * + * A better (but more complex) approach that would be worthwhile trying in the + * future would be to rather do the following: + * + * 1. Concurrent mark phase is on-going + * 2. Mark thread runs out of things to mark + * 3. Mark thread sends a signal to capabilities requesting that they send + * their update remembered sets without suspending their execution + * 4. The mark thread marks everything it was sent; runs out of things to mark + * 5. Mark thread initiates a sync + * 6. Capabilities send their final update remembered sets and suspend execution + * 7. Mark thread marks everything is was sent + * 8. Mark thead allows capabilities to resume. + * + * However, this is obviously a fair amount of complexity and so far the + * periodic eager flushing approach has been sufficient. + * * * Note [Concurrent read barrier on deRefWeak#] * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -205,7 +248,7 @@ static void init_mark_queue_(MarkQueue *queue); * Really the argument type should be UpdRemSet* but this would be rather * inconvenient without polymorphism. */ -static void nonmovingAddUpdRemSetBlocks(MarkQueue *rset) +void nonmovingAddUpdRemSetBlocks(MarkQueue *rset) { if (markQueueIsEmpty(rset)) return; @@ -364,7 +407,7 @@ push (MarkQueue *q, const MarkQueueEnt *ent) } else { // allocate a fresh block. ACQUIRE_SM_LOCK; - bdescr *bd = allocGroup(1); + bdescr *bd = allocGroup(MARK_QUEUE_BLOCKS); bd->link = q->blocks; q->blocks = bd; q->top = (MarkQueueBlock *) bd->start; @@ -377,16 +420,49 @@ push (MarkQueue *q, const MarkQueueEnt *ent) q->top->head++; } +/* A variant of push to be used by the minor GC when it encounters a reference + * to an object in the non-moving heap. In contrast to the other push + * operations this uses the gc_alloc_block_sync spinlock instead of the + * SM_LOCK to allocate new blocks in the event that the mark queue is full. + */ +void +markQueuePushClosureGC (MarkQueue *q, StgClosure *p) +{ + /* We should not make it here if we are doing a deadlock detect GC. + * See Note [Deadlock detection under nonmoving collector]. + */ + ASSERT(!deadlock_detect_gc); + + // Are we at the end of the block? + if (q->top->head == MARK_QUEUE_BLOCK_ENTRIES) { + // Yes, this block is full. + // allocate a fresh block. + ACQUIRE_SPIN_LOCK(&gc_alloc_block_sync); + bdescr *bd = allocGroup(MARK_QUEUE_BLOCKS); + bd->link = q->blocks; + q->blocks = bd; + q->top = (MarkQueueBlock *) bd->start; + q->top->head = 0; + RELEASE_SPIN_LOCK(&gc_alloc_block_sync); + } + + MarkQueueEnt ent = { + .mark_closure = { + .p = UNTAG_CLOSURE(p), + .origin = NULL, + } + }; + q->top->entries[q->top->head] = ent; + q->top->head++; +} + static inline void push_closure (MarkQueue *q, StgClosure *p, StgClosure **origin) { - // TODO: Push this into callers where they already have the Bdescr - if (HEAP_ALLOCED_GC(p) && (Bdescr((StgPtr) p)->gen != oldest_gen)) - return; - #if defined(DEBUG) + ASSERT(!HEAP_ALLOCED_GC(p) || (Bdescr((StgPtr) p)->gen == oldest_gen)); ASSERT(LOOKS_LIKE_CLOSURE_PTR(p)); // Commenting out: too slow // if (RtsFlags.DebugFlags.sanity) { @@ -396,8 +472,12 @@ void push_closure (MarkQueue *q, // } #endif + // This must be true as origin points to a pointer and therefore must be + // word-aligned. However, we check this as otherwise we would confuse this + // with a mark_array entry + ASSERT(((uintptr_t) origin & 0x3) == 0); + MarkQueueEnt ent = { - .type = MARK_CLOSURE, .mark_closure = { .p = UNTAG_CLOSURE(p), .origin = origin, @@ -416,10 +496,9 @@ void push_array (MarkQueue *q, return; MarkQueueEnt ent = { - .type = MARK_ARRAY, .mark_array = { .array = array, - .start_index = start_index + .start_index = (start_index << 16) | 0x3, } }; push(q, &ent); @@ -496,15 +575,11 @@ void updateRemembSetPushThunkEager(Capability *cap, MarkQueue *queue = &cap->upd_rem_set.queue; push_thunk_srt(queue, &info->i); - // Don't record the origin of objects living outside of the nonmoving - // heap; we can't perform the selector optimisation on them anyways. - bool record_origin = check_in_nonmoving_heap((StgClosure*)thunk); - for (StgWord i = 0; i < info->i.layout.payload.ptrs; i++) { if (check_in_nonmoving_heap(thunk->payload[i])) { - push_closure(queue, - thunk->payload[i], - record_origin ? &thunk->payload[i] : NULL); + // Don't bother to push origin; it makes the barrier needlessly + // expensive with little benefit. + push_closure(queue, thunk->payload[i], NULL); } } break; @@ -513,7 +588,9 @@ void updateRemembSetPushThunkEager(Capability *cap, { MarkQueue *queue = &cap->upd_rem_set.queue; StgAP *ap = (StgAP *) thunk; - push_closure(queue, ap->fun, &ap->fun); + if (check_in_nonmoving_heap(ap->fun)) { + push_closure(queue, ap->fun, NULL); + } mark_PAP_payload(queue, ap->fun, ap->payload, ap->n_args); break; } @@ -534,9 +611,10 @@ void updateRemembSetPushThunk_(StgRegTable *reg, StgThunk *p) inline void updateRemembSetPushClosure(Capability *cap, StgClosure *p) { - if (!check_in_nonmoving_heap(p)) return; - MarkQueue *queue = &cap->upd_rem_set.queue; - push_closure(queue, p, NULL); + if (check_in_nonmoving_heap(p)) { + MarkQueue *queue = &cap->upd_rem_set.queue; + push_closure(queue, p, NULL); + } } void updateRemembSetPushClosure_(StgRegTable *reg, struct StgClosure_ *p) @@ -633,7 +711,10 @@ void markQueuePushClosure (MarkQueue *q, StgClosure *p, StgClosure **origin) { - push_closure(q, p, origin); + // TODO: Push this into callers where they already have the Bdescr + if (check_in_nonmoving_heap(p)) { + push_closure(q, p, origin); + } } /* TODO: Do we really never want to specify the origin here? */ @@ -670,7 +751,7 @@ void markQueuePushArray (MarkQueue *q, *********************************************************/ // Returns invalid MarkQueueEnt if queue is empty. -static MarkQueueEnt markQueuePop (MarkQueue *q) +static MarkQueueEnt markQueuePop_ (MarkQueue *q) { MarkQueueBlock *top; @@ -682,7 +763,7 @@ again: // Is this the first block of the queue? if (q->blocks->link == NULL) { // Yes, therefore queue is empty... - MarkQueueEnt none = { .type = NULL_ENTRY }; + MarkQueueEnt none = { .null_entry = { .p = NULL } }; return none; } else { // No, unwind to the previous block and try popping again... @@ -701,6 +782,47 @@ again: return ent; } +static MarkQueueEnt markQueuePop (MarkQueue *q) +{ +#if MARK_PREFETCH_QUEUE_DEPTH == 0 + return markQueuePop_(q); +#else + unsigned int i = q->prefetch_head; + while (nonmovingMarkQueueEntryType(&q->prefetch_queue[i]) == NULL_ENTRY) { + MarkQueueEnt new = markQueuePop_(q); + if (nonmovingMarkQueueEntryType(&new) == NULL_ENTRY) { + // Mark queue is empty; look for any valid entries in the prefetch + // queue + for (unsigned int j = (i+1) % MARK_PREFETCH_QUEUE_DEPTH; + j != i; + j = (j+1) % MARK_PREFETCH_QUEUE_DEPTH) + { + if (nonmovingMarkQueueEntryType(&q->prefetch_queue[j]) != NULL_ENTRY) { + i = j; + goto done; + } + } + return new; + } + + // The entry may not be a MARK_CLOSURE but it doesn't matter, our + // MarkQueueEnt encoding always places the pointer to the object to be + // marked first. + prefetchForRead(&new.mark_closure.p->header.info); + prefetchForRead(&nonmovingGetSegment_unchecked((StgPtr) new.mark_closure.p)->block_size); + q->prefetch_queue[i] = new; + i = (i + 1) % MARK_PREFETCH_QUEUE_DEPTH; + } + + done: + ; + MarkQueueEnt ret = q->prefetch_queue[i]; + q->prefetch_queue[i].null_entry.p = NULL; + q->prefetch_head = i; + return ret; +#endif +} + /********************************************************* * Creating and destroying MarkQueues and UpdRemSets *********************************************************/ @@ -708,17 +830,20 @@ again: /* Must hold sm_mutex. */ static void init_mark_queue_ (MarkQueue *queue) { - bdescr *bd = allocGroup(1); + bdescr *bd = allocGroup(MARK_QUEUE_BLOCKS); queue->blocks = bd; queue->top = (MarkQueueBlock *) bd->start; queue->top->head = 0; +#if MARK_PREFETCH_QUEUE_DEPTH > 0 + memset(&queue->prefetch_queue, 0, sizeof(queue->prefetch_queue)); + queue->prefetch_head = 0; +#endif } /* Must hold sm_mutex. */ void initMarkQueue (MarkQueue *queue) { init_mark_queue_(queue); - queue->marked_objects = allocHashTable(); queue->is_upd_rem_set = false; } @@ -726,8 +851,6 @@ void initMarkQueue (MarkQueue *queue) void init_upd_rem_set (UpdRemSet *rset) { init_mark_queue_(&rset->queue); - // Update remembered sets don't have to worry about static objects - rset->queue.marked_objects = NULL; rset->queue.is_upd_rem_set = true; } @@ -742,7 +865,6 @@ void reset_upd_rem_set (UpdRemSet *rset) void freeMarkQueue (MarkQueue *queue) { freeChain_lock(queue->blocks); - freeHashTable(queue->marked_objects, NULL); } #if defined(THREADED_RTS) && defined(DEBUG) @@ -989,12 +1111,32 @@ mark_stack (MarkQueue *queue, StgStack *stack) mark_stack_(queue, stack->sp, stack->stack + stack->stack_size); } +/* See Note [Static objects under the nonmoving collector]. + * + * Returns true if the object needs to be marked. + */ +static bool +bump_static_flag(StgClosure **link_field, StgClosure *q STG_UNUSED) +{ + while (1) { + StgWord link = (StgWord) *link_field; + StgWord new = (link & ~STATIC_BITS) | static_flag; + if ((link & STATIC_BITS) == static_flag) + return false; + else if (cas((StgVolatilePtr) link_field, link, new) == link) { + return true; + } + } +} + static GNUC_ATTR_HOT void mark_closure (MarkQueue *queue, StgClosure *p, StgClosure **origin) { (void)origin; // TODO: should be used for selector/thunk optimisations try_again: + ; + bdescr *bd = NULL; p = UNTAG_CLOSURE(p); # define PUSH_FIELD(obj, field) \ @@ -1012,45 +1154,46 @@ mark_closure (MarkQueue *queue, StgClosure *p, StgClosure **origin) return; } - if (lookupHashTable(queue->marked_objects, (W_)p)) { - // already marked - return; - } - - insertHashTable(queue->marked_objects, (W_)p, (P_)1); - switch (type) { case THUNK_STATIC: if (info->srt != 0) { - markQueuePushThunkSrt(queue, info); // TODO this function repeats the check above + if (bump_static_flag(THUNK_STATIC_LINK((StgClosure *)p), p)) { + markQueuePushThunkSrt(queue, info); // TODO this function repeats the check above + } } return; case FUN_STATIC: if (info->srt != 0 || info->layout.payload.ptrs != 0) { - markQueuePushFunSrt(queue, info); // TODO this function repeats the check above - - // 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]); + if (bump_static_flag(STATIC_LINK(info, (StgClosure *)p), p)) { + markQueuePushFunSrt(queue, info); // TODO this function repeats the check above + + // 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]); + } } } return; case IND_STATIC: - PUSH_FIELD((StgInd *) p, indirectee); + if (bump_static_flag(IND_STATIC_LINK((StgClosure *)p), p)) { + PUSH_FIELD((StgInd *) p, indirectee); + } return; case CONSTR: case CONSTR_1_0: case CONSTR_2_0: case CONSTR_1_1: - for (StgHalfWord i = 0; i < info->layout.payload.ptrs; ++i) { - PUSH_FIELD(p, payload[i]); + if (bump_static_flag(STATIC_LINK(info, (StgClosure *)p), p)) { + for (StgHalfWord i = 0; i < info->layout.payload.ptrs; ++i) { + PUSH_FIELD(p, payload[i]); + } } return; @@ -1064,19 +1207,17 @@ mark_closure (MarkQueue *queue, StgClosure *p, StgClosure **origin) } } - bdescr *bd = Bdescr((StgPtr) p); + bd = Bdescr((StgPtr) p); if (bd->gen != oldest_gen) { - // Here we have an object living outside of the non-moving heap. Since - // we moved everything to the non-moving heap before starting the major - // collection, we know that we don't need to trace it: it was allocated - // after we took our snapshot. -#if !defined(THREADED_RTS) - // This should never happen in the non-concurrent case - barf("Closure outside of non-moving heap: %p", p); -#else + // Here we have an object living outside of the non-moving heap. While + // we likely evacuated nearly everything to the nonmoving heap during + // preparation there are nevertheless a few ways in which we might trace + // a reference into younger generations: + // + // * a mutable object might have been updated + // * we might have aged an object return; -#endif } ASSERTM(LOOKS_LIKE_CLOSURE_PTR(p), "invalid closure, info=%p", p->header.info); @@ -1444,13 +1585,13 @@ nonmovingMark (MarkQueue *queue) count++; MarkQueueEnt ent = markQueuePop(queue); - switch (ent.type) { + switch (nonmovingMarkQueueEntryType(&ent)) { case MARK_CLOSURE: mark_closure(queue, ent.mark_closure.p, ent.mark_closure.origin); break; case MARK_ARRAY: { const StgMutArrPtrs *arr = ent.mark_array.array; - StgWord start = ent.mark_array.start_index; + StgWord start = ent.mark_array.start_index >> 16; StgWord end = start + MARK_ARRAY_CHUNK_LENGTH; if (end < arr->ptrs) { markQueuePushArray(queue, ent.mark_array.array, end); @@ -1696,13 +1837,17 @@ void nonmovingResurrectThreads (struct MarkQueue_ *queue, StgTSO **resurrected_t void printMarkQueueEntry (MarkQueueEnt *ent) { - if (ent->type == MARK_CLOSURE) { + switch(nonmovingMarkQueueEntryType(ent)) { + case MARK_CLOSURE: debugBelch("Closure: "); printClosure(ent->mark_closure.p); - } else if (ent->type == MARK_ARRAY) { + break; + case MARK_ARRAY: debugBelch("Array\n"); - } else { + break; + case NULL_ENTRY: debugBelch("End of mark\n"); + break; } } diff --git a/rts/sm/NonMovingMark.h b/rts/sm/NonMovingMark.h index 84b6642d6c..806776cdc5 100644 --- a/rts/sm/NonMovingMark.h +++ b/rts/sm/NonMovingMark.h @@ -43,21 +43,40 @@ enum EntryType { */ typedef struct { - enum EntryType type; - // All pointers should be untagged + // Which kind of mark queue entry we have is determined by the low bits of + // the second word: they must be zero in the case of a mark_closure entry + // (since the second word of a mark_closure entry points to a pointer and + // pointers must be word-aligned). In the case of a mark_array we set them + // to 0x3 (the value of start_index is shifted to the left to accomodate + // this). null_entry where p==NULL is used to indicate the end of the queue. union { struct { + void *p; // must be NULL + } null_entry; + struct { StgClosure *p; // the object to be marked StgClosure **origin; // field where this reference was found. // See Note [Origin references in the nonmoving collector] } mark_closure; struct { const StgMutArrPtrs *array; - StgWord start_index; + StgWord start_index; // start index is shifted to the left by 16 bits } mark_array; }; } MarkQueueEnt; +INLINE_HEADER enum EntryType nonmovingMarkQueueEntryType(MarkQueueEnt *ent) +{ + if (ent->null_entry.p == NULL) { + return NULL_ENTRY; + } else if (((uintptr_t) ent->mark_closure.origin & TAG_BITS) == 0) { + return MARK_CLOSURE; + } else { + ASSERT((ent->mark_array.start_index & TAG_BITS) == 0x3); + return MARK_ARRAY; + } +} + typedef struct { // index of first *unused* queue entry uint32_t head; @@ -65,6 +84,9 @@ typedef struct { MarkQueueEnt entries[]; } MarkQueueBlock; +// How far ahead in mark queue to prefetch? +#define MARK_PREFETCH_QUEUE_DEPTH 5 + /* The mark queue is not capable of concurrent read or write. * * invariants: @@ -83,9 +105,12 @@ typedef struct MarkQueue_ { // Is this a mark queue or a capability-local update remembered set? bool is_upd_rem_set; - // Marked objects outside of nonmoving heap, namely large and static - // objects. - HashTable *marked_objects; +#if MARK_PREFETCH_QUEUE_DEPTH > 0 + // A ring-buffer of entries which we will mark next + MarkQueueEnt prefetch_queue[MARK_PREFETCH_QUEUE_DEPTH]; + // The first free slot in prefetch_queue. + uint8_t prefetch_head; +#endif } MarkQueue; /* While it shares its representation with MarkQueue, UpdRemSet differs in @@ -97,8 +122,11 @@ typedef struct { MarkQueue queue; } UpdRemSet; +// Number of blocks to allocate for a mark queue +#define MARK_QUEUE_BLOCKS 16 + // The length of MarkQueueBlock.entries -#define MARK_QUEUE_BLOCK_ENTRIES ((BLOCK_SIZE - sizeof(MarkQueueBlock)) / sizeof(MarkQueueEnt)) +#define MARK_QUEUE_BLOCK_ENTRIES ((MARK_QUEUE_BLOCKS * BLOCK_SIZE - sizeof(MarkQueueBlock)) / sizeof(MarkQueueEnt)) extern bdescr *nonmoving_large_objects, *nonmoving_marked_large_objects; extern memcount n_nonmoving_large_blocks, n_nonmoving_marked_large_blocks; @@ -145,8 +173,10 @@ void nonmovingResurrectThreads(struct MarkQueue_ *queue, StgTSO **resurrected_th bool nonmovingIsAlive(StgClosure *p); void nonmovingMarkDeadWeak(struct MarkQueue_ *queue, StgWeak *w); void nonmovingMarkLiveWeak(struct MarkQueue_ *queue, StgWeak *w); +void nonmovingAddUpdRemSetBlocks(struct MarkQueue_ *rset); void markQueuePush(MarkQueue *q, const MarkQueueEnt *ent); +void markQueuePushClosureGC(MarkQueue *q, StgClosure *p); void markQueuePushClosure(MarkQueue *q, StgClosure *p, StgClosure **origin); diff --git a/rts/sm/NonMovingScav.c b/rts/sm/NonMovingScav.c index 850750b43b..0efbde688c 100644 --- a/rts/sm/NonMovingScav.c +++ b/rts/sm/NonMovingScav.c @@ -16,6 +16,7 @@ nonmovingScavengeOne (StgClosure *q) ASSERT(LOOKS_LIKE_CLOSURE_PTR(q)); StgPtr p = (StgPtr)q; const StgInfoTable *info = get_itbl(q); + const bool saved_eager_promotion = gct->eager_promotion; switch (info->type) { @@ -23,9 +24,11 @@ nonmovingScavengeOne (StgClosure *q) case MVAR_DIRTY: { StgMVar *mvar = ((StgMVar *)p); + gct->eager_promotion = false; 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 { @@ -37,8 +40,10 @@ nonmovingScavengeOne (StgClosure *q) case TVAR: { StgTVar *tvar = ((StgTVar *)p); + gct->eager_promotion = false; 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 { @@ -122,10 +127,21 @@ nonmovingScavengeOne (StgClosure *q) break; } + case WEAK: + { + // We must evacuate the key since it may refer to an object in the + // moving heap which may be long gone by the time we call + // nonmovingTidyWeaks. + StgWeak *weak = (StgWeak *) p; + gct->eager_promotion = true; + evacuate(&weak->key); + gct->eager_promotion = saved_eager_promotion; + goto gen_obj; + } + gen_obj: case CONSTR: case CONSTR_NOCAF: - case WEAK: case PRIM: { StgPtr end = (P_)((StgClosure *)p)->payload + info->layout.payload.ptrs; @@ -145,7 +161,9 @@ nonmovingScavengeOne (StgClosure *q) case MUT_VAR_CLEAN: case MUT_VAR_DIRTY: + gct->eager_promotion = false; 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 { @@ -157,10 +175,12 @@ nonmovingScavengeOne (StgClosure *q) { StgBlockingQueue *bq = (StgBlockingQueue *)p; + gct->eager_promotion = false; evacuate(&bq->bh); evacuate((StgClosure**)&bq->owner); evacuate((StgClosure**)&bq->queue); evacuate((StgClosure**)&bq->link); + gct->eager_promotion = saved_eager_promotion; if (gct->failed_to_evac) { bq->header.info = &stg_BLOCKING_QUEUE_DIRTY_info; @@ -202,11 +222,9 @@ nonmovingScavengeOne (StgClosure *q) case MUT_ARR_PTRS_CLEAN: case MUT_ARR_PTRS_DIRTY: { - // 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 = false; scavenge_mut_arr_ptrs((StgMutArrPtrs*)p); + gct->eager_promotion = saved_eager_promotion; if (gct->failed_to_evac) { ((StgClosure *)q)->header.info = &stg_MUT_ARR_PTRS_DIRTY_info; } else { @@ -234,14 +252,13 @@ nonmovingScavengeOne (StgClosure *q) case SMALL_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. StgPtr next = p + small_mut_arr_ptrs_sizeW((StgSmallMutArrPtrs*)p); + gct->eager_promotion = false; 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 { @@ -278,21 +295,21 @@ nonmovingScavengeOne (StgClosure *q) { StgStack *stack = (StgStack*)p; + gct->eager_promotion = false; scavenge_stack(stack->sp, stack->stack + stack->stack_size); + gct->eager_promotion = saved_eager_promotion; stack->dirty = gct->failed_to_evac; - // TODO (osa): There may be something special about stacks that we're - // missing. All other mut objects are marked by using a different info - // table except stacks. - break; } case MUT_PRIM: { StgPtr end = (P_)((StgClosure *)p)->payload + info->layout.payload.ptrs; + gct->eager_promotion = false; for (p = (P_)((StgClosure *)p)->payload; p < end; p++) { evacuate((StgClosure **)p); } + gct->eager_promotion = saved_eager_promotion; gct->failed_to_evac = true; // mutable break; } @@ -302,12 +319,14 @@ nonmovingScavengeOne (StgClosure *q) StgWord i; StgTRecChunk *tc = ((StgTRecChunk *) p); TRecEntry *e = &(tc -> entries[0]); + gct->eager_promotion = false; 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; gct->failed_to_evac = true; // mutable break; } diff --git a/rts/sm/NonMovingSweep.c b/rts/sm/NonMovingSweep.c index fa3e38cca4..7af5508afc 100644 --- a/rts/sm/NonMovingSweep.c +++ b/rts/sm/NonMovingSweep.c @@ -17,38 +17,6 @@ #include "Trace.h" #include "StableName.h" -static struct NonmovingSegment *pop_all_filled_segments(struct NonmovingAllocator *alloc) -{ - while (true) { - struct NonmovingSegment *head = alloc->filled; - if (cas((StgVolatilePtr) &alloc->filled, (StgWord) head, (StgWord) NULL) == (StgWord) head) - return head; - } -} - -void nonmovingPrepareSweep() -{ - ASSERT(nonmovingHeap.sweep_list == NULL); - - // Move blocks in the allocators' filled lists into sweep_list - for (unsigned int alloc_idx = 0; alloc_idx < NONMOVING_ALLOCA_CNT; alloc_idx++) - { - struct NonmovingAllocator *alloc = nonmovingHeap.allocators[alloc_idx]; - struct NonmovingSegment *filled = pop_all_filled_segments(alloc); - - // Link filled to sweep_list - if (filled) { - struct NonmovingSegment *filled_head = filled; - // Find end of filled list - while (filled->link) { - filled = filled->link; - } - filled->link = nonmovingHeap.sweep_list; - nonmovingHeap.sweep_list = filled_head; - } - } -} - // On which list should a particular segment be placed? enum SweepResult { SEGMENT_FREE, // segment is empty: place on free list @@ -102,7 +70,7 @@ nonmovingSweepSegment(struct NonmovingSegment *seg) #if defined(DEBUG) -void nonmovingGcCafs(struct MarkQueue_ *queue) +void nonmovingGcCafs() { uint32_t i = 0; StgIndStatic *next; @@ -116,7 +84,8 @@ void nonmovingGcCafs(struct MarkQueue_ *queue) const StgInfoTable *info = get_itbl((StgClosure*)caf); ASSERT(info->type == IND_STATIC); - if (lookupHashTable(queue->marked_objects, (StgWord) caf) == NULL) { + StgWord flag = ((StgWord) caf->static_link) & STATIC_BITS; + if (flag != 0 && flag != static_flag) { debugTrace(DEBUG_gccafs, "CAF gc'd at 0x%p", caf); SET_INFO((StgClosure*)caf, &stg_GCD_CAF_info); // stub it } else { @@ -184,6 +153,126 @@ GNUC_ATTR_HOT void nonmovingSweep(void) } } +/* Must a closure remain on the mutable list? + * + * A closure must remain if any of the following applies: + * + * 1. it contains references to a younger generation + * 2. it's a mutable closure (e.g. mutable array or MUT_PRIM) + */ +static bool is_closure_clean(StgClosure *p) +{ + const StgInfoTable *info = get_itbl(p); + +#define CLEAN(ptr) (!HEAP_ALLOCED((StgClosure*) ptr) || Bdescr((StgPtr) ptr)->gen == oldest_gen) + + switch (info->type) { + case MVAR_CLEAN: + case MVAR_DIRTY: + { + StgMVar *mvar = ((StgMVar *)p); + if (!CLEAN(mvar->head)) goto dirty_MVAR; + if (!CLEAN(mvar->tail)) goto dirty_MVAR; + if (!CLEAN(mvar->value)) goto dirty_MVAR; + mvar->header.info = &stg_MVAR_CLEAN_info; + return true; + +dirty_MVAR: + mvar->header.info = &stg_MVAR_DIRTY_info; + return false; + } + + case TVAR: + { + StgTVar *tvar = ((StgTVar *)p); + if (!CLEAN(tvar->current_value)) goto dirty_TVAR; + if (!CLEAN(tvar->first_watch_queue_entry)) goto dirty_TVAR; + tvar->header.info = &stg_TVAR_CLEAN_info; + return true; + +dirty_TVAR: + tvar->header.info = &stg_TVAR_DIRTY_info; + return false; + } + + case THUNK: + case THUNK_1_0: + case THUNK_0_1: + case THUNK_1_1: + case THUNK_0_2: + case THUNK_2_0: + { + StgPtr end = (StgPtr)((StgThunk *)p)->payload + info->layout.payload.ptrs; + for (StgPtr q = (StgPtr)((StgThunk *)p)->payload; q < end; q++) { + if (!CLEAN(*q)) return false; + } + return true; + } + + case FUN: + case FUN_1_0: // hardly worth specialising these guys + case FUN_0_1: + case FUN_1_1: + case FUN_0_2: + case FUN_2_0: + case CONSTR: + case CONSTR_NOCAF: + case CONSTR_1_0: + case CONSTR_0_1: + case CONSTR_1_1: + case CONSTR_0_2: + case CONSTR_2_0: + case PRIM: + { + StgPtr end = (StgPtr)((StgClosure *)p)->payload + info->layout.payload.ptrs; + for (StgPtr q = (StgPtr)((StgClosure *)p)->payload; q < end; q++) { + if (!CLEAN(*q)) return false; + } + return true; + } + + case WEAK: + return false; // TODO + + case MUT_VAR_CLEAN: + case MUT_VAR_DIRTY: + if (!CLEAN(((StgMutVar *)p)->var)) { + p->header.info = &stg_MUT_VAR_DIRTY_info; + return false; + } else { + p->header.info = &stg_MUT_VAR_CLEAN_info; + return true; + } + + case BLOCKING_QUEUE: + { + StgBlockingQueue *bq = (StgBlockingQueue *)p; + + if (!CLEAN(bq->bh)) goto dirty_BLOCKING_QUEUE; + if (!CLEAN(bq->owner)) goto dirty_BLOCKING_QUEUE; + if (!CLEAN(bq->queue)) goto dirty_BLOCKING_QUEUE; + if (!CLEAN(bq->link)) goto dirty_BLOCKING_QUEUE; + bq->header.info = &stg_BLOCKING_QUEUE_CLEAN_info; + return true; + +dirty_BLOCKING_QUEUE: + bq->header.info = &stg_BLOCKING_QUEUE_DIRTY_info; + return false; + } + + case THUNK_SELECTOR: + return CLEAN(((StgSelector *) p)->selectee); + + case ARR_WORDS: + return true; + + default: + // TODO: the rest + return false; + } +#undef CLEAN +} + /* N.B. This happens during the pause so we own all capabilities. */ void nonmovingSweepMutLists() { @@ -194,7 +283,7 @@ void nonmovingSweepMutLists() for (bdescr *bd = old_mut_list; bd; bd = bd->link) { for (StgPtr p = bd->start; p < bd->free; p++) { StgClosure **q = (StgClosure**)p; - if (nonmovingIsAlive(*q)) { + if (nonmovingIsAlive(*q) && !is_closure_clean(*q)) { recordMutableCap(*q, cap, oldest_gen->no); } } diff --git a/rts/sm/NonMovingSweep.h b/rts/sm/NonMovingSweep.h index de2d52acb5..5ae5b687e3 100644 --- a/rts/sm/NonMovingSweep.h +++ b/rts/sm/NonMovingSweep.h @@ -22,11 +22,7 @@ void nonmovingSweepLargeObjects(void); // Remove dead entries in the stable name table void nonmovingSweepStableNameTable(void); -// Collect the set of segments to be collected during a major GC into -// nonmovingHeap.sweep_list. -void nonmovingPrepareSweep(void); - #if defined(DEBUG) // The non-moving equivalent of the moving collector's gcCAFs. -void nonmovingGcCafs(struct MarkQueue_ *queue); +void nonmovingGcCafs(void); #endif diff --git a/rts/sm/Storage.c b/rts/sm/Storage.c index 44163a353f..f04b3c5929 100644 --- a/rts/sm/Storage.c +++ b/rts/sm/Storage.c @@ -321,7 +321,8 @@ freeStorage (bool free_heap) } /* ----------------------------------------------------------------------------- - Note [CAF management]. + Note [CAF management] + ~~~~~~~~~~~~~~~~~~~~~ The entry code for every CAF does the following: @@ -356,6 +357,7 @@ freeStorage (bool free_heap) ------------------ Note [atomic CAF entry] + ~~~~~~~~~~~~~~~~~~~~~~~ With THREADED_RTS, newCAF() is required to be atomic (see #5558). This is because if two threads happened to enter the same @@ -369,6 +371,7 @@ freeStorage (bool free_heap) ------------------ Note [GHCi CAFs] + ~~~~~~~~~~~~~~~~ For GHCI, we have additional requirements when dealing with CAFs: @@ -388,6 +391,51 @@ freeStorage (bool free_heap) -- SDM 29/1/01 + ------------------ + Note [Static objects under the nonmoving collector] + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + Static object management is a bit tricky under the nonmoving collector as we + need to maintain a bit more state than in the moving collector. In + particular, the moving collector uses the low bits of the STATIC_LINK field + to determine whether the object has been moved to the scavenger's work list + (see Note [STATIC_LINK fields] in Storage.h). + + However, the nonmoving collector also needs a place to keep its mark bit. + This is problematic as we therefore need at least three bits of state + but can assume only two bits are available in STATIC_LINK (due to 32-bit + systems). + + To accomodate this we move handling of static objects entirely to the + oldest generation when the nonmoving collector is in use. To do this safely + and efficiently we allocate the blackhole created by lockCAF() directly in + the non-moving heap. This means that the moving collector can completely + ignore static objects in minor collections since they are guaranteed not to + have any references into the moving heap. Of course, the blackhole itself + likely will contain a reference into the moving heap but this is + significantly easier to handle, being a heap-allocated object (see Note + [Aging under the non-moving collector] in NonMoving.c for details). + + During the moving phase of a major collection we treat static objects + as we do any other reference into the non-moving heap by pushing them + to the non-moving mark queue (see Note [Aging under the non-moving + collector]). + + This allows the non-moving collector to have full control over the flags + in STATIC_LINK, which it uses as described in Note [STATIC_LINK fields]). + This is implemented by NonMovingMark.c:bump_static_flag. + + In short, the plan is: + + - lockCAF allocates its blackhole in the nonmoving heap. This is important + to ensure that we do not need to place the static object on the mut_list + lest we would need somw way to ensure that it evacuate only once during + a moving collection. + + - evacuate_static_object adds merely pushes objects to the mark queue + + - the nonmoving collector uses the flags in STATIC_LINK as its mark bit. + -------------------------------------------------------------------------- */ STATIC_INLINE StgInd * @@ -441,7 +489,16 @@ lockCAF (StgRegTable *reg, StgIndStatic *caf) caf->saved_info = orig_info; // Allocate the blackhole indirection closure - bh = (StgInd *)allocate(cap, sizeofW(*bh)); + if (RtsFlags.GcFlags.useNonmoving) { + // See Note [Static objects under the nonmoving collector]. + ACQUIRE_SM_LOCK; + bh = (StgInd *)nonmovingAllocate(cap, sizeofW(*bh)); + RELEASE_SM_LOCK; + recordMutableCap((StgClosure*)bh, + regTableToCapability(reg), oldest_gen->no); + } else { + bh = (StgInd *)allocate(cap, sizeofW(*bh)); + } bh->indirectee = (StgClosure *)cap->r.rCurrentTSO; SET_HDR(bh, &stg_CAF_BLACKHOLE_info, caf->header.prof.ccs); // Ensure that above writes are visible before we introduce reference as CAF indirectee. @@ -483,7 +540,9 @@ newCAF(StgRegTable *reg, StgIndStatic *caf) else { // Put this CAF on the mutable list for the old generation. - if (oldest_gen->no != 0) { + // N.B. the nonmoving collector works a bit differently: see + // Note [Static objects under the nonmoving collector]. + if (oldest_gen->no != 0 && !RtsFlags.GcFlags.useNonmoving) { recordMutableCap((StgClosure*)caf, regTableToCapability(reg), oldest_gen->no); } @@ -560,7 +619,9 @@ StgInd* newGCdCAF (StgRegTable *reg, StgIndStatic *caf) if (!bh) return NULL; // Put this CAF on the mutable list for the old generation. - if (oldest_gen->no != 0) { + // N.B. the nonmoving collector works a bit differently: + // see Note [Static objects under the nonmoving collector]. + if (oldest_gen->no != 0 && !RtsFlags.GcFlags.useNonmoving) { recordMutableCap((StgClosure*)caf, regTableToCapability(reg), oldest_gen->no); } @@ -1520,6 +1581,7 @@ void flushExec (W_ len, AdjustorExecutable exec_addr) __clear_cache((void*)begin, (void*)end); # endif #elif defined(__GNUC__) + /* For all other platforms, fall back to a libgcc builtin. */ unsigned char* begin = (unsigned char*)exec_addr; unsigned char* end = begin + len; # if GCC_HAS_BUILTIN_CLEAR_CACHE diff --git a/testsuite/config/ghc b/testsuite/config/ghc index ec35ed0d8c..9a3459ea96 100644 --- a/testsuite/config/ghc +++ b/testsuite/config/ghc @@ -27,7 +27,9 @@ config.other_ways = ['prof', 'normal_h', 'debug', 'ghci-ext', 'ghci-ext-prof', 'ext-interp', - 'nonmoving'] + 'nonmoving', + 'nonmoving_thr', + 'nonmoving_thr_ghc'] if ghc_with_native_codegen: config.compile_ways.append('optasm') @@ -98,7 +100,9 @@ config.way_flags = { 'ghci-ext' : ['--interactive', '-v0', '-ignore-dot-ghci', '-fno-ghci-history', '-fexternal-interpreter', '+RTS', '-I0.1', '-RTS'], 'ghci-ext-prof' : ['--interactive', '-v0', '-ignore-dot-ghci', '-fno-ghci-history', '-fexternal-interpreter', '-prof', '+RTS', '-I0.1', '-RTS'], 'ext-interp' : ['-fexternal-interpreter'], - 'nonmoving' : ['-debug'], + 'nonmoving' : [], + 'nonmoving_thr': ['-threaded'], + 'nonmoving_thr_ghc': ['+RTS', '-xn', '-N2', '-RTS', '-threaded'], } config.way_rts_flags = { @@ -137,7 +141,9 @@ config.way_rts_flags = { 'ghci-ext' : [], 'ghci-ext-prof' : [], 'ext-interp' : [], - 'nonmoving' : ['-DS', '-xn'], + 'nonmoving' : ['-xn'], + 'nonmoving_thr' : ['-xn', '-N2'], + 'nonmoving_thr_ghc': ['-xn', '-N2'], } # Useful classes of ways that can be used with only_ways(), omit_ways() and diff --git a/testsuite/tests/codeGen/should_run/all.T b/testsuite/tests/codeGen/should_run/all.T index 0882f2b605..f96820de81 100644 --- a/testsuite/tests/codeGen/should_run/all.T +++ b/testsuite/tests/codeGen/should_run/all.T @@ -1,5 +1,6 @@ # Test +RTS -G1 here (it isn't tested anywhere else) -setTestOpts(unless(fast(), extra_ways(['g1']))) +# N.B. Nonmoving collector doesn't support -G1 +setTestOpts(unless(fast(), [ extra_ways(['g1']), omit_ways(['nonmoving', 'nonmoving_thr', 'nonmoving_thr_ghc'])])) test('cgrun001', normal, compile_and_run, ['']) test('cgrun002', normal, compile_and_run, ['']) @@ -194,9 +195,11 @@ test('T15696_3', normal, compile_and_run, ['-O']) test('T15892', [ ignore_stdout, - # we want to do lots of major GC to make the bug more likely to - # happen, so -G1 -A32k: - extra_run_opts('+RTS -G1 -A32k -RTS') ], + # -G1 is unsupported by the nonmoving GC + omit_ways(['nonmoving', 'nonmoving_thr', 'nonmoving_thr_ghc']), + # we want to do lots of major GC to make the bug more likely to + # happen, so -G1 -A32k: + extra_run_opts('+RTS -G1 -A32k -RTS') ], compile_and_run, ['-O']) test('T16617', normal, compile_and_run, ['']) test('T16449_2', exit_code(0), compile_and_run, ['']) diff --git a/testsuite/tests/concurrent/should_run/all.T b/testsuite/tests/concurrent/should_run/all.T index 467040223f..9297c5890e 100644 --- a/testsuite/tests/concurrent/should_run/all.T +++ b/testsuite/tests/concurrent/should_run/all.T @@ -7,7 +7,7 @@ test('conc027', normal, compile_and_run, ['']) test('conc051', normal, compile_and_run, ['']) if ('threaded1' in config.run_ways): - only_threaded_ways = only_ways(['ghci','threaded1','threaded2']) + only_threaded_ways = only_ways(['ghci','threaded1','threaded2', 'nonmoving_thr']) else: only_threaded_ways = skip @@ -203,8 +203,8 @@ test('foreignInterruptible', [when(fast(), skip), ], compile_and_run, ['']) -test('conc037', only_ways(['threaded1','threaded2']), compile_and_run, ['']) -test('conc038', only_ways(['threaded1','threaded2']), compile_and_run, ['']) +test('conc037', only_ways(['threaded1', 'threaded2', 'nonmoving_thr']), compile_and_run, ['']) +test('conc038', only_ways(['threaded1', 'threaded2', 'nonmoving_thr']), compile_and_run, ['']) # Omit for GHCi, uses foreign export # Omit for the threaded ways, because in this case the main thread is allowed to @@ -224,7 +224,7 @@ test('conc045', normal, compile_and_run, ['']) test('conc058', normal, compile_and_run, ['']) test('conc059', - [only_ways(['threaded1', 'threaded2']), + [only_ways(['threaded1', 'threaded2', 'nonmoving_thr']), pre_cmd('$MAKE -s --no-print-directory conc059_setup')], compile_and_run, ['conc059_c.c -no-hs-main']) @@ -243,7 +243,7 @@ test('conc067', ignore_stdout, compile_and_run, ['']) test('conc068', [ omit_ways(concurrent_ways), exit_code(1) ], compile_and_run, ['']) test('setnumcapabilities001', - [ only_ways(['threaded1','threaded2']), + [ only_ways(['threaded1','threaded2', 'nonmoving_thr']), extra_run_opts('8 12 2000'), req_smp ], compile_and_run, ['']) @@ -254,7 +254,7 @@ test('compareAndSwap', [omit_ways(['ghci','hpc']), reqlib('primitive')], compile test('hs_try_putmvar001', [ when(opsys('mingw32'),skip), # uses pthread APIs in the C code - only_ways(['threaded1','threaded2']), + only_ways(['threaded1', 'threaded2', 'nonmoving_thr']), extra_clean(['hs_try_putmvar001_c.o'])], compile_and_run, ['hs_try_putmvar001_c.c']) @@ -272,7 +272,7 @@ test('hs_try_putmvar003', [ when(opsys('mingw32'),skip), # uses pthread APIs in the C code pre_cmd('$MAKE -s --no-print-directory hs_try_putmvar003_setup'), - only_ways(['threaded1','threaded2']), + only_ways(['threaded1', 'threaded2', 'nonmoving_thr']), extra_clean(['hs_try_putmvar003_c.o']), extra_run_opts('1 16 32 100'), fragile_for(16361, ['threaded1']) diff --git a/testsuite/tests/perf/compiler/all.T b/testsuite/tests/perf/compiler/all.T index cfc860d0b0..72e240a4c5 100644 --- a/testsuite/tests/perf/compiler/all.T +++ b/testsuite/tests/perf/compiler/all.T @@ -385,7 +385,9 @@ test ('T9630', extra_clean(['T9630a.hi', 'T9630a.o']), # Use `+RTS -G1` for more stable residency measurements. Note [residency]. - extra_hc_opts('+RTS -G1 -RTS') + extra_hc_opts('+RTS -G1 -RTS'), + # The nonmoving collector does not support -G1 + omit_ways(['nonmoving', 'nonmoving_thr', 'nonmoving_thr_ghc']) ], multimod_compile, ['T9630', '-v0 -O']) diff --git a/testsuite/tests/rts/all.T b/testsuite/tests/rts/all.T index 9e20ba0b81..36f63c571e 100644 --- a/testsuite/tests/rts/all.T +++ b/testsuite/tests/rts/all.T @@ -12,7 +12,10 @@ test('testmblockalloc', # See bug #101, test requires +RTS -c (or equivalently +RTS -M<something>) # only GHCi triggers the bug, but we run the test all ways for completeness. -test('bug1010', normal, compile_and_run, ['+RTS -c -RTS']) +test('bug1010', + # Non-moving GC doesn't support -c + omit_ways(['nonmoving', 'nonmoving_thr', 'nonmoving_thr_ghc']), + compile_and_run, ['+RTS -c -RTS']) def normalise_address(str): return re.sub('Access violation in generated code when reading [0]+', @@ -67,8 +70,12 @@ test('outofmem', when(opsys('darwin'), skip), makefile_test, ['outofmem']) test('outofmem2', normal, makefile_test, ['outofmem2']) -test('T2047', [ignore_stdout, extra_run_opts('+RTS -c -RTS')], - compile_and_run, ['-package containers']) +test('T2047', + [ignore_stdout, + extra_run_opts('+RTS -c -RTS'), + # Non-moving collector doesn't support -c + omit_ways(['nonmoving', 'nonmoving_thr', 'nonmoving_thr_ghc'])], + compile_and_run, ['-package containers']) # Blackhole-detection test. # Skip GHCi due to #2786 @@ -183,7 +190,7 @@ test('T6006', [ omit_ways(prof_ways + ['ghci']), test('T7037', [], makefile_test, ['T7037']) test('T7087', exit_code(1), compile_and_run, ['']) -test('T7160', normal, compile_and_run, ['']) +test('T7160', omit_ways(['nonmoving_thr', 'nonmoving_thr_ghc']), compile_and_run, ['']) test('T7040', [omit_ways(['ghci'])], compile_and_run, ['T7040_c.c']) |