Use background tasks for the compiler dispatcher

src/compiler-dispatcher/compiler-dispatcher.cc

 // Copyright 2016 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler-dispatcher/compiler-dispatcher.h"
 
 #include "include/v8-platform.h"
 #include "include/v8.h"
 #include "src/base/platform/time.h"
 #include "src/cancelable-task.h"
@@ skipping 48 matching lines @@
     try_catch.ReThrow();
   }
   return job->status() != CompileJobStatus::kFailed;
 }
 
 bool IsFinished(CompilerDispatcherJob* job) {
   return job->status() == CompileJobStatus::kDone ||
          job->status() == CompileJobStatus::kFailed;
 }
 
+bool CanRunOnAnyThread(CompilerDispatcherJob* job) {
+  return (job->status() == CompileJobStatus::kReadyToParse &&
+          job->can_parse_on_background_thread()) ||
+         (job->status() == CompileJobStatus::kReadyToCompile &&
+          job->can_compile_on_background_thread());
+}
+
+void DoNextStepOnBackgroundThread(CompilerDispatcherJob* job) {
+  DCHECK(CanRunOnAnyThread(job));
+  switch (job->status()) {
+    case CompileJobStatus::kReadyToParse:
+      job->Parse();
+      break;
+
+    case CompileJobStatus::kReadyToCompile:
+      job->Compile();
+      break;
+
+    default:
+      UNREACHABLE();
+  }
+}
+
 // Theoretically we get 50ms of idle time max, however it's unlikely that
 // we'll get all of it so try to be a conservative.
 const double kMaxIdleTimeToExpectInMs = 40;
 
 }  // namespace
 
+class CompilerDispatcher::BackgroundTask : public CancelableTask {
+ public:
+  BackgroundTask(Isolate* isolate, CompilerDispatcher* dispatcher);
+  ~BackgroundTask() override;
+
+  // CancelableTask implementation.
+  void RunInternal() override;
+
+ private:
+  CompilerDispatcher* dispatcher_;
+
+  DISALLOW_COPY_AND_ASSIGN(BackgroundTask);
+};
+
+CompilerDispatcher::BackgroundTask::BackgroundTask(
+    Isolate* isolate, CompilerDispatcher* dispatcher)
+    : CancelableTask(isolate), dispatcher_(dispatcher) {}
+
+CompilerDispatcher::BackgroundTask::~BackgroundTask() {}
+
+void CompilerDispatcher::BackgroundTask::RunInternal() {
+  dispatcher_->DoBackgroundWork();
+}
+
 class CompilerDispatcher::IdleTask : public CancelableIdleTask {
  public:
   IdleTask(Isolate* isolate, CompilerDispatcher* dispatcher);
   ~IdleTask() override;
 
   // CancelableIdleTask implementation.
   void RunInternal(double deadline_in_seconds) override;
 
  private:
   CompilerDispatcher* dispatcher_;
@@ skipping 10 matching lines @@
 void CompilerDispatcher::IdleTask::RunInternal(double deadline_in_seconds) {
   dispatcher_->DoIdleWork(deadline_in_seconds);
 }
 
 CompilerDispatcher::CompilerDispatcher(Isolate* isolate, Platform* platform,
                                        size_t max_stack_size)
     : isolate_(isolate),
       platform_(platform),
       max_stack_size_(max_stack_size),
       tracer_(new CompilerDispatcherTracer(isolate_)),
-      idle_task_scheduled_(false) {}
+      idle_task_scheduled_(false),
+      num_scheduled_background_tasks_(0),
+      main_thread_blocking_on_job_(nullptr) {}
 
 CompilerDispatcher::~CompilerDispatcher() {
   // To avoid crashing in unit tests due to unfished jobs.
   AbortAll(BlockingBehavior::kBlock);
 }
 
 bool CompilerDispatcher::Enqueue(Handle<SharedFunctionInfo> function) {
   if (!IsEnabled()) return false;
 
   // We only handle functions (no eval / top-level code / wasm) that are
@@ skipping 15 matching lines @@
 
 bool CompilerDispatcher::IsEnabled() const {
   v8::Isolate* v8_isolate = reinterpret_cast<v8::Isolate*>(isolate_);
   return FLAG_compiler_dispatcher && platform_->IdleTasksEnabled(v8_isolate);
 }
 
 bool CompilerDispatcher::IsEnqueued(Handle<SharedFunctionInfo> function) const {
   return GetJobFor(function) != jobs_.end();
 }
 
+void CompilerDispatcher::EnsureNotOnBackground(CompilerDispatcherJob* job) {

[marja, 2017/01/03 10:42:41]

This function name is confusing. I had to read it several times to understand
what it does...

So, what it does: if a job is currently running on background, it waits until
it's done. "BlockIfJobIsRunningOnBackground"? "WaitForJobIfRunningOnBackground"?

[jochen (gone - plz use gerrit), 2017/01/03 12:59:35]

done

+  base::LockGuard<base::Mutex> lock(&mutex_);
+  if (running_background_jobs_.find(job) == running_background_jobs_.end()) {
+    pending_background_jobs_.erase(job);
+    return;
+  }
+  DCHECK_NULL(main_thread_blocking_on_job_);
+  main_thread_blocking_on_job_ = job;
+  while (main_thread_blocking_on_job_ != nullptr) {
+    main_thread_blocking_signal_.Wait(&mutex_);
+  }
+  DCHECK(pending_background_jobs_.find(job) == pending_background_jobs_.end());

[vogelheim, 2017/01/03 10:32:37]

Also the same DCHECK(...), with running_background_jobs?

The post-condition is that job is in neither of those queues, right?

[jochen (gone - plz use gerrit), 2017/01/03 12:59:36]

done

+}
+
 bool CompilerDispatcher::FinishNow(Handle<SharedFunctionInfo> function) {
   JobMap::const_iterator job = GetJobFor(function);
   CHECK(job != jobs_.end());
 
-  // TODO(jochen): Check if there's an in-flight background task working on this
-  // job.
+  EnsureNotOnBackground(job->second.get());
   while (!IsFinished(job->second.get())) {
     DoNextStepOnMainThread(isolate_, job->second.get(),
                            ExceptionHandling::kThrow);
   }
   bool result = job->second->status() != CompileJobStatus::kFailed;
   job->second->ResetOnMainThread();
   jobs_.erase(job);
   return result;
 }
 
-void CompilerDispatcher::Abort(Handle<SharedFunctionInfo> function,
-                               BlockingBehavior blocking) {
-  USE(blocking);
-  JobMap::const_iterator job = GetJobFor(function);
-  CHECK(job != jobs_.end());
-
-  // TODO(jochen): Check if there's an in-flight background task working on this
-  // job.
-  job->second->ResetOnMainThread();
-  jobs_.erase(job);
-}
-
 void CompilerDispatcher::AbortAll(BlockingBehavior blocking) {
-  USE(blocking);
-  // TODO(jochen): Check if there's an in-flight background task working on this
-  // job.
+  // TODO(jochen): Implement support for non-blocking abort.
+  DCHECK(blocking == BlockingBehavior::kBlock);

[vogelheim, 2017/01/03 10:32:37]

DCHECK_EQ ?

[jochen (gone - plz use gerrit), 2017/01/03 12:59:36]

doesn't work with enum classes

   for (auto& kv : jobs_) {
+    EnsureNotOnBackground(kv.second.get());
     kv.second->ResetOnMainThread();
   }
   jobs_.clear();
 }
 
 CompilerDispatcher::JobMap::const_iterator CompilerDispatcher::GetJobFor(
     Handle<SharedFunctionInfo> shared) const {
   if (!shared->script()->IsScript()) return jobs_.end();
   std::pair<int, int> key(Script::cast(shared->script())->id(),
                           shared->function_literal_id());
   auto range = jobs_.equal_range(key);
   for (auto job = range.first; job != range.second; ++job) {
     if (job->second->IsAssociatedWith(shared)) return job;
   }
   return jobs_.end();
 }
 
-void CompilerDispatcher::ScheduleIdleTaskIfNeeded() {
+void CompilerDispatcher::ScheduleIdleTaskFromAnyThread() {
   v8::Isolate* v8_isolate = reinterpret_cast<v8::Isolate*>(isolate_);
   DCHECK(platform_->IdleTasksEnabled(v8_isolate));
-  if (idle_task_scheduled_) return;
-  if (jobs_.empty()) return;
-  idle_task_scheduled_ = true;
+  {
+    base::LockGuard<base::Mutex> lock(&mutex_);
+    if (idle_task_scheduled_) return;
+    idle_task_scheduled_ = true;
+  }
   platform_->CallIdleOnForegroundThread(v8_isolate,
                                         new IdleTask(isolate_, this));
 }
 
+void CompilerDispatcher::ScheduleIdleTaskIfNeeded() {
+  if (jobs_.empty()) return;
+  ScheduleIdleTaskFromAnyThread();
+}
+
+void CompilerDispatcher::ConsiderJobForBackgroundProcessing(
+    CompilerDispatcherJob* job) {
+  if (!CanRunOnAnyThread(job)) return;
+  {
+    base::LockGuard<base::Mutex> lock(&mutex_);
+    pending_background_jobs_.insert(job);
+  }
+  ScheduleMoreBackgroundTasksIfNeeded();
+}
+
+void CompilerDispatcher::ScheduleMoreBackgroundTasksIfNeeded() {
+  if (FLAG_single_threaded) return;

[vogelheim, 2017/01/03 10:32:37]

Hmm. So if --single_threaded, ConsiderJobForBackgroundProcessing might put a job
into pending_background_job_, and they'd just linger there until the main thread
needs it and will FinishNow(job)?

[jochen (gone - plz use gerrit), 2017/01/03 12:59:36]

if the job is too big for idle time. Since the DoIdleWork() iterates over jobs_,
it'll still process pending_background_jobs_ if it can

+  {
+    base::LockGuard<base::Mutex> lock(&mutex_);
+    if (pending_background_jobs_.empty()) return;
+    if (platform_->NumberOfAvailableBackgroundThreads() <=
+        num_scheduled_background_tasks_) {
+      return;
+    }
+    ++num_scheduled_background_tasks_;
+  }
+  platform_->CallOnBackgroundThread(new BackgroundTask(isolate_, this),
+                                    v8::Platform::kShortRunningTask);
+}
+
+void CompilerDispatcher::DoBackgroundWork() {
+  CompilerDispatcherJob* job = nullptr;

[marja, 2017/01/03 10:43:41]

Can you add an assert (somewhere, maybe here) that the size of
running_background_jobs_ doesn't exceed the number of available threads?

[jochen (gone - plz use gerrit), 2017/01/03 12:59:35]

that assert will not necessarily hold: the embedder can spawn as many threads as
it likes (available threads is just a hint)

[marja, 2017/01/03 13:14:57]

Hmm, I'm missing something...

ScheduleMoreBackgroundTasksIfNeeded doesn't schedule more concurrent tasks than
NumberOfAvailableBackgroundThreads(), and the only way to put things into
running_background_jobs_ is to have a background task which does
DoBackgroundWork. What's the other mechanism bypassing that?

[jochen (gone - plz use gerrit), 2017/01/03 14:01:44]

assume that each task counts down num_scheduled_background_tasks & inserts
itself in running_background_jobs_ and then starves. The main thread will then
continue to schedule new jobs that all could suffer the same faith.

[marja, 2017/01/03 14:22:45]

Ah I see

It's slightly unintuitive though that num_scheduled_background_tasks_ is not the
number of tasks in flight, since there can be many which are currently doing
their work... oh well. The name says "scheduled" though so it's good.

+  {
+    base::LockGuard<base::Mutex> lock(&mutex_);
+    --num_scheduled_background_tasks_;
+    if (!pending_background_jobs_.empty()) {
+      auto it = pending_background_jobs_.begin();
+      job = *it;
+      pending_background_jobs_.erase(it);
+      running_background_jobs_.insert(job);
+    }
+  }
+  if (job == nullptr) return;
+  DoNextStepOnBackgroundThread(job);
+  {
+    base::LockGuard<base::Mutex> lock(&mutex_);
+    running_background_jobs_.erase(job);
+
+    if (main_thread_blocking_on_job_ == job) {
+      main_thread_blocking_on_job_ = nullptr;
+      main_thread_blocking_signal_.NotifyOne();
+    }
+  }
+  ScheduleMoreBackgroundTasksIfNeeded();
+  ScheduleIdleTaskFromAnyThread();

[vogelheim, 2017/01/03 10:32:37]

ScheduleIdleTaskFromAnyThread unconditionally schedules the idle thread. Why do
we know that we need one here? Is it because any background-compile always needs
at least one main-thread step to finish?

[jochen (gone - plz use gerrit), 2017/01/03 12:59:36]

correct. Added a comment

+}
+
 void CompilerDispatcher::DoIdleWork(double deadline_in_seconds) {
-  idle_task_scheduled_ = false;
+  {
+    base::LockGuard<base::Mutex> lock(&mutex_);
+    idle_task_scheduled_ = false;
+  }
 
   // Number of jobs that are unlikely to make progress during any idle callback
   // due to their estimated duration.
   size_t too_long_jobs = 0;
 
   // Iterate over all available jobs & remaining time. For each job, decide
   // whether to 1) skip it (if it would take too long), 2) erase it (if it's
   // finished), or 3) make progress on it.
   double idle_time_in_seconds =
       deadline_in_seconds - platform_->MonotonicallyIncreasingTime();
   for (auto job = jobs_.begin();
        job != jobs_.end() && idle_time_in_seconds > 0.0;
        idle_time_in_seconds =
            deadline_in_seconds - platform_->MonotonicallyIncreasingTime()) {
+    {
+      // Don't work on jobs that are being worked on by background tasks.
+      // Similarly, remove jobs we work on from the set of available background
+      // jobs.
+      base::LockGuard<base::Mutex> lock(&mutex_);
+      if (running_background_jobs_.find(job->second.get()) !=
+          running_background_jobs_.end()) {
+        ++job;
+        continue;
+      }
+      auto it = pending_background_jobs_.find(job->second.get());

[marja, 2017/01/03 10:42:41]

This is kinda weird... here we erase the job from pending_background_jobs and
then we potentially insert it again if it's too big to complete now.

So once we're running out of idle time, we might go through the whole
pending_background_jobs_ structure, taking each job out and putting it back in.
That feels weird...

How about taking the job out of pending_background_jobs_ only if we're going to
work on it?

[jochen (gone - plz use gerrit), 2017/01/03 12:59:36]

we're always working on it in the sense that we invoke methods on the job. If I
don't take the job out of the pending set, a background thread might race and
start processing it, resulting in non-mutex protected accesses to the job

[marja, 2017/01/03 13:14:57]

If the job is too big (or the amount of idle time too low), we don't work on it.

Ofc the decision needs to be protected by the mutex, so, I meant something like
this:

grab mutex
decide if we're going to work on the task
if yes, remove it from the set
release mutex
do the work

Or maybe even something like this:
grab mutex
find a task to work on (so, possibly loop over tasks here)
remove it
release mutex
do the work

[jochen (gone - plz use gerrit), 2017/01/03 14:01:44]

what about this?

+      if (it != pending_background_jobs_.end()) {
+        pending_background_jobs_.erase(it);
+      }
+    }
     double estimate_in_ms = job->second->EstimateRuntimeOfNextStepInMs();
     if (idle_time_in_seconds <
         (estimate_in_ms /
          static_cast<double>(base::Time::kMillisecondsPerSecond))) {
       // If there's not enough time left, try to estimate whether we would
       // have managed to finish the job in a large idle task to assess
       // whether we should ask for another idle callback.
       if (estimate_in_ms > kMaxIdleTimeToExpectInMs) ++too_long_jobs;
+      ConsiderJobForBackgroundProcessing(job->second.get());

[marja, 2017/01/03 10:42:40]

This is somewhat surprising... so we only push those jobs which are too long to
complete (now) for background processing. Why is that?

[jochen (gone - plz use gerrit), 2017/01/03 12:59:36]

the other cases are:

- the job is finished (no need to push it)
- we're doing a step with the job (and continue working on it)

only if it's not yet finished, but we don't have enough time to work on it, we
need to put it on the bg thread

[marja, 2017/01/03 13:14:57]

But if there are a zillion of small tasks and several cores, don't we want the
main thread and the background thread work on them simultaneously?

(Guarantees / assumptions like that are not documented explicitly, so I'm
continuously confused by the compiler dispatcher, since I assume it does
something / gives a guarantee and then it does something else :) Could you add a
top level comment into the header which would explain how this is supposed to
work on a high level?)

[jochen (gone - plz use gerrit), 2017/01/03 14:01:44]

added a lengthy comment

       ++job;
     } else if (IsFinished(job->second.get())) {
       job->second->ResetOnMainThread();
       job = jobs_.erase(job);
       break;
     } else {
       // Do one step, and keep processing the job (as we don't advance the
       // iterator).
       DoNextStepOnMainThread(isolate_, job->second.get(),
                              ExceptionHandling::kSwallow);
     }
   }
   if (jobs_.size() > too_long_jobs) ScheduleIdleTaskIfNeeded();
 }
 
 }  // namespace internal
 }  // namespace v8