1 files changed, 286 insertions, 0 deletions
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<ParallelMarkTask> 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<ParallelMarkTaskList&>(waitingTasks.ref())
+      .ElementProbablyInList(const_cast<ParallelMarkTask*>(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);
+}