tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

ParallelMarking.cpp (10515B)

      1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
      2 * vim: set ts=8 sts=2 et sw=2 tw=80:
      3 * This Source Code Form is subject to the terms of the Mozilla Public
      4 * License, v. 2.0. If a copy of the MPL was not distributed with this
      5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
      6 
      7 #include "gc/ParallelMarking.h"
      8 
      9 #include "gc/GCInternals.h"
     10 #include "gc/GCLock.h"
     11 #include "vm/GeckoProfiler.h"
     12 #include "vm/HelperThreadState.h"
     13 #include "vm/Runtime.h"
     14 
     15 using namespace js;
     16 using namespace js::gc;
     17 
     18 using mozilla::TimeDuration;
     19 using mozilla::TimeStamp;
     20 
     21 using JS::SliceBudget;
     22 
     23 class AutoAddTimeDuration {
     24  TimeStamp start_;
     25  TimeDuration& result_;
     26 
     27 public:
     28  explicit AutoAddTimeDuration(TimeDuration& result)
     29      : start_(TimeStamp::Now()), result_(result) {}
     30  TimeStamp start() const { return start_; }
     31  ~AutoAddTimeDuration() { result_ += TimeSince(start_); }
     32 };
     33 
     34 /* static */
     35 bool ParallelMarker::mark(GCRuntime* gc, const SliceBudget& sliceBudget) {
     36  if (!markOneColor(gc, MarkColor::Black, sliceBudget) ||
     37      !markOneColor(gc, MarkColor::Gray, sliceBudget)) {
     38    return false;
     39  }
     40 
     41  // Handle any delayed marking, which is not performed in parallel.
     42  if (gc->hasDelayedMarking()) {
     43    gc->markAllDelayedChildren(ReportMarkTime);
     44  }
     45 
     46  return true;
     47 }
     48 
     49 /* static */
     50 bool ParallelMarker::markOneColor(GCRuntime* gc, MarkColor color,
     51                                  const SliceBudget& sliceBudget) {
     52  ParallelMarker pm(gc, color);
     53  return pm.mark(sliceBudget);
     54 }
     55 
     56 ParallelMarker::ParallelMarker(GCRuntime* gc, MarkColor color)
     57    : gc(gc), color(color) {
     58  // There should always be enough parallel tasks to run our marking work.
     59  MOZ_ASSERT(workerCount() <= gc->getMaxParallelThreads());
     60 }
     61 
     62 size_t ParallelMarker::workerCount() const { return gc->markers.length(); }
     63 
     64 bool ParallelMarker::mark(const SliceBudget& sliceBudget) {
     65  // Run a marking slice for a single color and return whether the stack is now
     66  // empty.
     67 
     68  if (!hasWork(color)) {
     69    return true;
     70  }
     71 
     72  gcstats::AutoPhase ap(gc->stats(), gcstats::PhaseKind::PARALLEL_MARK);
     73 
     74  MOZ_ASSERT(workerCount() <= MaxParallelWorkers);
     75 
     76  for (size_t i = 0; i < workerCount(); i++) {
     77    GCMarker* marker = gc->markers[i].get();
     78    tasks[i].emplace(this, marker, color, i, sliceBudget);
     79 
     80    // Attempt to populate empty mark stacks.
     81    //
     82    // TODO: When tuning for more than two markers we may need to adopt a more
     83    // sophisticated approach.
     84    if (!marker->hasEntriesForCurrentColor() && gc->marker().canDonateWork()) {
     85      GCMarker::moveWork(marker, &gc->marker(), false);
     86    }
     87  }
     88 
     89  AutoLockHelperThreadState lock;
     90 
     91  MOZ_ASSERT(!hasActiveTasks(lock));
     92  for (size_t i = 0; i < workerCount(); i++) {
     93    ParallelMarkTask& task = *tasks[i];
     94    if (task.hasWork()) {
     95      setTaskActive(&task, lock);
     96    }
     97  }
     98 
     99  // Run the parallel tasks, using the main thread for the first one.
    100  for (size_t i = 1; i < workerCount(); i++) {
    101    gc->startTask(*tasks[i], lock);
    102  }
    103  tasks[0]->runFromMainThread(lock);
    104  tasks[0]->recordDuration();  // Record stats as if it used a helper thread.
    105  for (size_t i = 1; i < workerCount(); i++) {
    106    gc->joinTask(*tasks[i], lock);
    107  }
    108 
    109  MOZ_ASSERT(!hasWaitingTasks());
    110  MOZ_ASSERT(!hasActiveTasks(lock));
    111 
    112  return !hasWork(color);
    113 }
    114 
    115 bool ParallelMarker::hasWork(MarkColor color) const {
    116  for (const auto& marker : gc->markers) {
    117    if (marker->hasEntries(color)) {
    118      return true;
    119    }
    120  }
    121 
    122  return false;
    123 }
    124 
    125 ParallelMarkTask::ParallelMarkTask(ParallelMarker* pm, GCMarker* marker,
    126                                   MarkColor color, uint32_t id,
    127                                   const SliceBudget& budget)
    128    : GCParallelTask(pm->gc, gcstats::PhaseKind::PARALLEL_MARK, GCUse::Marking),
    129      pm(pm),
    130      marker(marker),
    131      color(*marker, color),
    132      budget(budget),
    133      id(id) {
    134  marker->enterParallelMarkingMode();
    135 }
    136 
    137 ParallelMarkTask::~ParallelMarkTask() {
    138  MOZ_ASSERT(!isWaiting.refNoCheck());
    139  marker->leaveParallelMarkingMode();
    140 }
    141 
    142 bool ParallelMarkTask::hasWork() const {
    143  return marker->hasEntriesForCurrentColor();
    144 }
    145 
    146 void ParallelMarkTask::recordDuration() {
    147  // Record times separately to avoid double counting when these are summed.
    148  gc->stats().recordParallelPhase(gcstats::PhaseKind::PARALLEL_MARK_MARK,
    149                                  markTime.ref());
    150  gc->stats().recordParallelPhase(gcstats::PhaseKind::PARALLEL_MARK_WAIT,
    151                                  waitTime.ref());
    152  TimeDuration other = duration() - markTime.ref() - waitTime.ref();
    153  if (other < TimeDuration::Zero()) {
    154    other = TimeDuration::Zero();
    155  }
    156  gc->stats().recordParallelPhase(gcstats::PhaseKind::PARALLEL_MARK_OTHER,
    157                                  other);
    158 }
    159 
    160 void ParallelMarkTask::run(AutoLockHelperThreadState& lock) {
    161  AutoUpdateMarkStackRanges updateRanges(*marker);
    162 
    163  for (;;) {
    164    if (hasWork()) {
    165      if (!tryMarking(lock)) {
    166        return;
    167      }
    168    } else {
    169      if (!requestWork(lock)) {
    170        return;
    171      }
    172    }
    173  }
    174 
    175  MOZ_ASSERT(!isWaiting);
    176 }
    177 
    178 bool ParallelMarkTask::tryMarking(AutoLockHelperThreadState& lock) {
    179  MOZ_ASSERT(hasWork());
    180  MOZ_ASSERT(marker->isParallelMarking());
    181 
    182  // Mark until budget exceeded or we run out of work.
    183  bool finished;
    184  {
    185    AutoUnlockHelperThreadState unlock(lock);
    186 
    187    AutoAddTimeDuration time(markTime.ref());
    188    finished = marker->markCurrentColorInParallel(this, budget);
    189 
    190    GeckoProfilerRuntime& profiler = gc->rt->geckoProfiler();
    191    if (profiler.enabled()) {
    192      profiler.markInterval("Parallel marking ran", time.start(), nullptr,
    193                            JS::ProfilingCategoryPair::GCCC);
    194    }
    195  }
    196 
    197  MOZ_ASSERT_IF(finished, !hasWork());
    198  pm->setTaskInactive(this, lock);
    199 
    200  return finished;
    201 }
    202 
    203 bool ParallelMarkTask::requestWork(AutoLockHelperThreadState& lock) {
    204  MOZ_ASSERT(!hasWork());
    205 
    206  if (!pm->hasActiveTasks(lock)) {
    207    return false;  // All other tasks are empty. We're finished.
    208  }
    209 
    210  budget.forceCheck();
    211  if (budget.isOverBudget()) {
    212    return false;  // Over budget or interrupted.
    213  }
    214 
    215  // Add ourselves to the waiting list and wait for another task to give us
    216  // work. The task with work calls ParallelMarker::donateWorkFrom.
    217  waitUntilResumed(lock);
    218 
    219  return true;
    220 }
    221 
    222 void ParallelMarkTask::waitUntilResumed(AutoLockHelperThreadState& lock) {
    223  AutoAddTimeDuration time(waitTime.ref());
    224 
    225  pm->addTaskToWaitingList(this, lock);
    226 
    227  // Set isWaiting flag and wait for another thread to clear it and resume us.
    228  MOZ_ASSERT(!isWaiting);
    229  isWaiting = true;
    230 
    231  do {
    232    MOZ_ASSERT(pm->hasActiveTasks(lock));
    233    resumed.wait(lock);
    234  } while (isWaiting);
    235 
    236  MOZ_ASSERT(!pm->isTaskInWaitingList(this, lock));
    237 
    238  GeckoProfilerRuntime& profiler = gc->rt->geckoProfiler();
    239  if (profiler.enabled()) {
    240    char details[32];
    241    SprintfLiteral(details, "markers=%zu", pm->workerCount());
    242    profiler.markInterval("Parallel marking wait", time.start(), details,
    243                          JS::ProfilingCategoryPair::GCCC);
    244  }
    245 }
    246 
    247 void ParallelMarkTask::resume() {
    248  {
    249    AutoLockHelperThreadState lock;
    250    MOZ_ASSERT(isWaiting);
    251 
    252    isWaiting = false;
    253 
    254    // Increment the active task count before donateWorkFrom() returns so this
    255    // can't reach zero before the waiting task runs again.
    256    if (hasWork()) {
    257      pm->setTaskActive(this, lock);
    258    }
    259  }
    260 
    261  resumed.notify_all();
    262 }
    263 
    264 void ParallelMarkTask::resumeOnFinish(const AutoLockHelperThreadState& lock) {
    265  MOZ_ASSERT(isWaiting);
    266  MOZ_ASSERT(!hasWork());
    267 
    268  isWaiting = false;
    269  resumed.notify_all();
    270 }
    271 
    272 void ParallelMarker::addTaskToWaitingList(
    273    ParallelMarkTask* task, const AutoLockHelperThreadState& lock) {
    274  MOZ_ASSERT(!task->hasWork());
    275  MOZ_ASSERT(hasActiveTasks(lock));
    276  MOZ_ASSERT(!isTaskInWaitingList(task, lock));
    277 
    278  uint32_t id = task->id;
    279  MOZ_ASSERT(id < workerCount());
    280  MOZ_ASSERT(!waitingTasks[id]);
    281  waitingTasks[id] = true;
    282 }
    283 
    284 #ifdef DEBUG
    285 bool ParallelMarker::isTaskInWaitingList(
    286    const ParallelMarkTask* task, const AutoLockHelperThreadState& lock) const {
    287  uint32_t id = task->id;
    288  MOZ_ASSERT(id < workerCount());
    289  return waitingTasks[id];
    290 }
    291 #endif
    292 
    293 ParallelMarkTask* ParallelMarker::takeWaitingTask() {
    294  MOZ_ASSERT(hasWaitingTasks());
    295  uint32_t id = waitingTasks.FindFirst();
    296  MOZ_ASSERT(id < workerCount());
    297 
    298  MOZ_ASSERT(waitingTasks[id]);
    299  waitingTasks[id] = false;
    300  return &*tasks[id];
    301 }
    302 
    303 void ParallelMarker::setTaskActive(ParallelMarkTask* task,
    304                                   const AutoLockHelperThreadState& lock) {
    305  MOZ_ASSERT(task->hasWork());
    306 
    307  uint32_t id = task->id;
    308  MOZ_ASSERT(id < workerCount());
    309  MOZ_ASSERT(!activeTasks.ref()[id]);
    310  activeTasks.ref()[id] = true;
    311 }
    312 
    313 void ParallelMarker::setTaskInactive(ParallelMarkTask* task,
    314                                     const AutoLockHelperThreadState& lock) {
    315  MOZ_ASSERT(hasActiveTasks(lock));
    316 
    317  uint32_t id = task->id;
    318  MOZ_ASSERT(id < workerCount());
    319  MOZ_ASSERT(activeTasks.ref()[id]);
    320  activeTasks.ref()[id] = false;
    321 
    322  if (!hasActiveTasks(lock)) {
    323    while (hasWaitingTasks()) {
    324      takeWaitingTask()->resumeOnFinish(lock);
    325    }
    326  }
    327 }
    328 
    329 void ParallelMarkTask::donateWork() { pm->donateWorkFrom(marker); }
    330 
    331 void ParallelMarker::donateWorkFrom(GCMarker* src) {
    332  GeckoProfilerRuntime& profiler = gc->rt->geckoProfiler();
    333 
    334  if (!gHelperThreadLock.tryLock()) {
    335    if (profiler.enabled()) {
    336      profiler.markEvent("Parallel marking donate failed", "lock already held");
    337    }
    338    return;
    339  }
    340 
    341  // Check there are tasks waiting for work while holding the lock.
    342  if (!hasWaitingTasks()) {
    343    gHelperThreadLock.unlock();
    344    if (profiler.enabled()) {
    345      profiler.markEvent("Parallel marking donate failed", "no tasks waiting");
    346    }
    347    return;
    348  }
    349 
    350  // Take a waiting task off the list.
    351  ParallelMarkTask* waitingTask = takeWaitingTask();
    352 
    353  // |task| is not running so it's safe to move work to it.
    354  MOZ_ASSERT(waitingTask->isWaiting);
    355 
    356  gHelperThreadLock.unlock();
    357 
    358  // Move some work from this thread's mark stack to the waiting task.
    359  MOZ_ASSERT(!waitingTask->hasWork());
    360  size_t wordsMoved = GCMarker::moveWork(waitingTask->marker, src, true);
    361 
    362  gc->stats().count(gcstats::COUNT_PARALLEL_MARK_INTERRUPTIONS);
    363 
    364  if (profiler.enabled()) {
    365    char details[32];
    366    SprintfLiteral(details, "words=%zu", wordsMoved);
    367    profiler.markEvent("Parallel marking donated work", details,
    368                       JS::ProfilingCategoryPair::GCCC);
    369  }
    370 
    371  // Resume waiting task.
    372  waitingTask->resume();
    373 }