From 43a97878ce14b72f0981164f87f2e35e14151312 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 11:22:09 +0200 Subject: Adding upstream version 110.0.1. Signed-off-by: Daniel Baumann --- js/src/gc/ParallelMarking.cpp | 286 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 286 insertions(+) create mode 100644 js/src/gc/ParallelMarking.cpp (limited to 'js/src/gc/ParallelMarking.cpp') diff --git a/js/src/gc/ParallelMarking.cpp b/js/src/gc/ParallelMarking.cpp new file mode 100644 index 0000000000..e10c98cc74 --- /dev/null +++ b/js/src/gc/ParallelMarking.cpp @@ -0,0 +1,286 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- + * vim: set ts=8 sts=2 et sw=2 tw=80: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "gc/ParallelMarking.h" + +#include "gc/GCLock.h" +#include "gc/ParallelWork.h" + +using namespace js; +using namespace js::gc; + +ParallelMarker::ParallelMarker(GCRuntime* gc) : gc(gc) {} + +size_t ParallelMarker::workerCount() const { return gc->markers.length(); } + +bool ParallelMarker::mark(SliceBudget& sliceBudget) { + if (markOneColor(MarkColor::Black, sliceBudget) == NotFinished) { + return false; + } + MOZ_ASSERT(!hasWork(MarkColor::Black)); + + if (markOneColor(MarkColor::Gray, sliceBudget) == NotFinished) { + return false; + } + MOZ_ASSERT(!hasWork(MarkColor::Gray)); + + // Handle any delayed marking, which is not performed in parallel. + if (gc->hasDelayedMarking()) { + gc->markAllDelayedChildren(ReportMarkTime); + } + + return true; +} + +bool ParallelMarker::markOneColor(MarkColor color, SliceBudget& sliceBudget) { + // Run a marking slice and return whether the stack is now empty. + + if (!hasWork(color)) { + return true; + } + + MOZ_ASSERT(workerCount() <= MaxParallelWorkers); + mozilla::Maybe tasks[MaxParallelWorkers]; + + for (size_t i = 0; i < workerCount(); i++) { + GCMarker* marker = gc->markers[i].get(); + tasks[i].emplace(this, marker, color, sliceBudget); + + // Attempt to populate empty mark stacks. + // + // TODO: When supporting more than two markers we will need a more + // sophisticated approach. + if (!marker->hasEntries(color) && gc->marker().hasEntries(color)) { + marker->stealWorkFrom(&gc->marker()); + } + } + + { + AutoLockGC lock(gc); + + activeTasks = 0; + for (size_t i = 0; i < workerCount(); i++) { + ParallelMarkTask& task = *tasks[i]; + if (task.hasWork()) { + incActiveTasks(&task, lock); + } + } + } + + { + AutoLockHelperThreadState lock; + + for (size_t i = 0; i < workerCount(); i++) { + gc->startTask(*tasks[i], lock); + } + + for (size_t i = 0; i < workerCount(); i++) { + gc->joinTask(*tasks[i], lock); + } + } + +#ifdef DEBUG + { + AutoLockGC lock(gc); + MOZ_ASSERT(waitingTasks.ref().isEmpty()); + MOZ_ASSERT(waitingTaskCount == 0); + MOZ_ASSERT(activeTasks == 0); + } +#endif + + return !hasWork(color); +} + +bool ParallelMarker::hasWork(MarkColor color) const { + for (const auto& marker : gc->markers) { + if (marker->hasEntries(color)) { + return true; + } + } + + return false; +} + +ParallelMarkTask::ParallelMarkTask(ParallelMarker* pm, GCMarker* marker, + MarkColor color, const SliceBudget& budget) + : GCParallelTask(pm->gc, gcstats::PhaseKind::MARK, GCUse::Marking), + pm(pm), + marker(marker), + color(*marker, color), + budget(budget) { + marker->enterParallelMarkingMode(pm); +} + +ParallelMarkTask::~ParallelMarkTask() { + MOZ_ASSERT(!isWaiting.refNoCheck()); + marker->leaveParallelMarkingMode(); +} + +bool ParallelMarkTask::hasWork() const { + return marker->hasEntries(marker->markColor()); +} + +void ParallelMarkTask::run(AutoLockHelperThreadState& lock) { + AutoUnlockHelperThreadState unlock(lock); + + { + AutoLockGC gcLock(pm->gc); + + markOrSteal(gcLock); + + MOZ_ASSERT(!isWaiting); + if (hasWork()) { + pm->decActiveTasks(this, gcLock); + } + } +} + +void ParallelMarkTask::markOrSteal(AutoLockGC& lock) { + for (;;) { + if (hasWork() && !tryMarking(lock)) { + return; + } + + while (!hasWork()) { + if (!tryStealing(lock)) { + return; + } + } + } +} + +bool ParallelMarkTask::tryMarking(AutoLockGC& lock) { + MOZ_ASSERT(hasWork()); + MOZ_ASSERT(marker->isParallelMarking()); + + // Mark until budget exceeded or we run out of work. + { + AutoUnlockGC unlock(lock); + marker->markCurrentColorInParallel(budget); + } + + if (!hasWork()) { + pm->decActiveTasks(this, lock); + } + + return !budget.isOverBudget(); +} + +bool ParallelMarkTask::tryStealing(AutoLockGC& lock) { + MOZ_ASSERT(!hasWork()); + + if (!pm->hasActiveTasks(lock)) { + return false; // All other tasks are empty. We're finished. + } + + budget.stepAndForceCheck(); + if (budget.isOverBudget()) { + return false; // Over budget or interrupted. + } + + // Add ourselves to the waiting list and wait for another task to give us + // work. The task with work calls ParallelMarker::stealWorkFrom. + waitUntilResumed(lock); + + if (hasWork()) { + pm->incActiveTasks(this, lock); + } + + return true; +} + +void ParallelMarkTask::waitUntilResumed(AutoLockGC& lock) { + pm->addTaskToWaitingList(this, lock); + + // Set isWaiting flag and wait for another thread to clear it and resume us. + MOZ_ASSERT(!isWaiting); + isWaiting = true; + do { + MOZ_ASSERT(pm->hasActiveTasks(lock)); + resumed.wait(lock.guard()); + } while (isWaiting); + + MOZ_ASSERT(!pm->isTaskInWaitingList(this, lock)); +} + +void ParallelMarkTask::resume(const AutoLockGC& lock) { + MOZ_ASSERT(isWaiting); + + isWaiting = false; + resumed.notify_all(); +} + +void ParallelMarker::addTaskToWaitingList(ParallelMarkTask* task, + const AutoLockGC& lock) { + MOZ_ASSERT(!task->hasWork()); + MOZ_ASSERT(hasActiveTasks(lock)); + MOZ_ASSERT(!isTaskInWaitingList(task, lock)); + MOZ_ASSERT(waitingTaskCount < workerCount() - 1); + + waitingTasks.ref().pushBack(task); + waitingTaskCount++; +} + +#ifdef DEBUG +bool ParallelMarker::isTaskInWaitingList(const ParallelMarkTask* task, + const AutoLockGC& lock) const { + // The const cast is because ElementProbablyInList is not const. + return const_cast(waitingTasks.ref()) + .ElementProbablyInList(const_cast(task)); +} +#endif + +void ParallelMarker::incActiveTasks(ParallelMarkTask* task, + const AutoLockGC& lock) { + MOZ_ASSERT(task->hasWork()); + MOZ_ASSERT(activeTasks < workerCount()); + + activeTasks++; +} + +void ParallelMarker::decActiveTasks(ParallelMarkTask* task, + const AutoLockGC& lock) { + MOZ_ASSERT(activeTasks != 0); + + activeTasks--; + + if (activeTasks == 0) { + // We're finished. Wake up any tasks waiting for work. + activeTasksAvailable.ref().notify_all(); + + while (!waitingTasks.ref().isEmpty()) { + ParallelMarkTask* task = waitingTasks.ref().popFront(); + MOZ_ASSERT(waitingTaskCount != 0); + waitingTaskCount--; + task->resume(lock); + } + } +} + +void ParallelMarker::stealWorkFrom(GCMarker* victim) { + AutoLockGC lock(gc); + + // Check there are tasks waiting for work while holding the lock. + if (waitingTaskCount == 0) { + return; + } + + // Take the first waiting task off the list. + ParallelMarkTask* task = waitingTasks.ref().popFront(); + waitingTaskCount--; + + // |task| is not running so it's safe to move work to it. + MOZ_ASSERT(task->isWaiting); + + // TODO: When using more than two marking threads it may be better to + // release the lock while we steal. + + // Move some work from this thread's mark stack to the waiting task. + task->marker->stealWorkFrom(victim); + + // Resume waiting task. + task->resume(lock); +} -- cgit v1.2.3