1// Copyright 2016 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/compiler-dispatcher/lazy-compile-dispatcher.h"
6
7#include <atomic>
8
9#include "include/v8-platform.h"
10#include "src/ast/ast.h"
11#include "src/base/platform/mutex.h"
12#include "src/base/platform/time.h"
13#include "src/codegen/compiler.h"
14#include "src/common/globals.h"
15#include "src/execution/isolate.h"
16#include "src/flags/flags.h"
17#include "src/handles/global-handles-inl.h"
18#include "src/heap/parked-scope.h"
19#include "src/logging/counters.h"
20#include "src/logging/runtime-call-stats-scope.h"
21#include "src/numbers/hash-seed-inl.h"
22#include "src/objects/instance-type.h"
23#include "src/objects/objects-inl.h"
24#include "src/parsing/parse-info.h"
25#include "src/parsing/parser.h"
26#include "src/roots/roots.h"
27#include "src/sandbox/external-pointer.h"
28#include "src/tasks/cancelable-task.h"
29#include "src/tasks/task-utils.h"
30#include "src/zone/zone-list-inl.h"  // crbug.com/v8/8816
31
32namespace v8 {
33namespace internal {
34
35// The maximum amount of time we should allow a single function's FinishNow to
36// spend opportunistically finalizing other finalizable jobs.
37static constexpr int kMaxOpportunisticFinalizeTimeMs = 1;
38
39class LazyCompileDispatcher::JobTask : public v8::JobTask {
40 public:
41  explicit JobTask(LazyCompileDispatcher* lazy_compile_dispatcher)
42      : lazy_compile_dispatcher_(lazy_compile_dispatcher) {}
43
44  void Run(JobDelegate* delegate) final {
45    lazy_compile_dispatcher_->DoBackgroundWork(delegate);
46  }
47
48  size_t GetMaxConcurrency(size_t worker_count) const final {
49    size_t n = lazy_compile_dispatcher_->num_jobs_for_background_.load(
50        std::memory_order_relaxed);
51    if (FLAG_lazy_compile_dispatcher_max_threads == 0) return n;
52    return std::min(
53        n, static_cast<size_t>(FLAG_lazy_compile_dispatcher_max_threads));
54  }
55
56 private:
57  LazyCompileDispatcher* lazy_compile_dispatcher_;
58};
59
60LazyCompileDispatcher::Job::Job(std::unique_ptr<BackgroundCompileTask> task)
61    : task(std::move(task)), state(Job::State::kPending) {}
62
63LazyCompileDispatcher::Job::~Job() = default;
64
65LazyCompileDispatcher::LazyCompileDispatcher(Isolate* isolate,
66                                             Platform* platform,
67                                             size_t max_stack_size)
68    : isolate_(isolate),
69      worker_thread_runtime_call_stats_(
70          isolate->counters()->worker_thread_runtime_call_stats()),
71      background_compile_timer_(
72          isolate->counters()->compile_function_on_background()),
73      taskrunner_(platform->GetForegroundTaskRunner(
74          reinterpret_cast<v8::Isolate*>(isolate))),
75      platform_(platform),
76      max_stack_size_(max_stack_size),
77      trace_compiler_dispatcher_(FLAG_trace_compiler_dispatcher),
78      idle_task_manager_(new CancelableTaskManager()),
79      idle_task_scheduled_(false),
80      num_jobs_for_background_(0),
81      main_thread_blocking_on_job_(nullptr),
82      block_for_testing_(false),
83      semaphore_for_testing_(0) {
84  job_handle_ = platform_->PostJob(TaskPriority::kUserVisible,
85                                   std::make_unique<JobTask>(this));
86}
87
88LazyCompileDispatcher::~LazyCompileDispatcher() {
89  // AbortAll must be called before LazyCompileDispatcher is destroyed.
90  CHECK(!job_handle_->IsValid());
91}
92
93namespace {
94
95// If the SharedFunctionInfo's UncompiledData has a job slot, then write into
96// it. Otherwise, allocate a new UncompiledData with a job slot, and then write
97// into that. Since we have two optional slots (preparse data and job), this
98// gets a little messy.
99void SetUncompiledDataJobPointer(LocalIsolate* isolate,
100                                 Handle<SharedFunctionInfo> shared_info,
101                                 Address job_address) {
102  UncompiledData uncompiled_data = shared_info->uncompiled_data();
103  switch (uncompiled_data.map(isolate).instance_type()) {
104    // The easy cases -- we already have a job slot, so can write into it and
105    // return.
106    case UNCOMPILED_DATA_WITH_PREPARSE_DATA_AND_JOB_TYPE:
107      UncompiledDataWithPreparseDataAndJob::cast(uncompiled_data)
108          .set_job(job_address);
109      break;
110    case UNCOMPILED_DATA_WITHOUT_PREPARSE_DATA_WITH_JOB_TYPE:
111      UncompiledDataWithoutPreparseDataWithJob::cast(uncompiled_data)
112          .set_job(job_address);
113      break;
114
115    // Otherwise, we'll have to allocate a new UncompiledData (with or without
116    // preparse data as appropriate), set the job pointer on that, and update
117    // the SharedFunctionInfo to use the new UncompiledData
118    case UNCOMPILED_DATA_WITH_PREPARSE_DATA_TYPE: {
119      Handle<String> inferred_name(uncompiled_data.inferred_name(), isolate);
120      Handle<PreparseData> preparse_data(
121          UncompiledDataWithPreparseData::cast(uncompiled_data).preparse_data(),
122          isolate);
123      Handle<UncompiledDataWithPreparseDataAndJob> new_uncompiled_data =
124          isolate->factory()->NewUncompiledDataWithPreparseDataAndJob(
125              inferred_name, uncompiled_data.start_position(),
126              uncompiled_data.end_position(), preparse_data);
127
128      new_uncompiled_data->set_job(job_address);
129      shared_info->set_uncompiled_data(*new_uncompiled_data);
130      break;
131    }
132    case UNCOMPILED_DATA_WITHOUT_PREPARSE_DATA_TYPE: {
133      DCHECK(uncompiled_data.IsUncompiledDataWithoutPreparseData());
134      Handle<String> inferred_name(uncompiled_data.inferred_name(), isolate);
135      Handle<UncompiledDataWithoutPreparseDataWithJob> new_uncompiled_data =
136          isolate->factory()->NewUncompiledDataWithoutPreparseDataWithJob(
137              inferred_name, uncompiled_data.start_position(),
138              uncompiled_data.end_position());
139
140      new_uncompiled_data->set_job(job_address);
141      shared_info->set_uncompiled_data(*new_uncompiled_data);
142      break;
143    }
144
145    default:
146      UNREACHABLE();
147  }
148}
149
150}  // namespace
151
152void LazyCompileDispatcher::Enqueue(
153    LocalIsolate* isolate, Handle<SharedFunctionInfo> shared_info,
154    std::unique_ptr<Utf16CharacterStream> character_stream) {
155  TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.compile"),
156               "V8.LazyCompilerDispatcherEnqueue");
157  RCS_SCOPE(isolate, RuntimeCallCounterId::kCompileEnqueueOnDispatcher);
158
159  Job* job = new Job(std::make_unique<BackgroundCompileTask>(
160      isolate_, shared_info, std::move(character_stream),
161      worker_thread_runtime_call_stats_, background_compile_timer_,
162      static_cast<int>(max_stack_size_)));
163
164  SetUncompiledDataJobPointer(isolate, shared_info,
165                              reinterpret_cast<Address>(job));
166
167  // Post a a background worker task to perform the compilation on the worker
168  // thread.
169  {
170    base::MutexGuard lock(&mutex_);
171    if (trace_compiler_dispatcher_) {
172      PrintF("LazyCompileDispatcher: enqueued job for ");
173      shared_info->ShortPrint();
174      PrintF("\n");
175    }
176
177#ifdef DEBUG
178    all_jobs_.insert(job);
179#endif
180    pending_background_jobs_.push_back(job);
181    NotifyAddedBackgroundJob(lock);
182  }
183  // This is not in NotifyAddedBackgroundJob to avoid being inside the mutex.
184  job_handle_->NotifyConcurrencyIncrease();
185}
186
187bool LazyCompileDispatcher::IsEnqueued(
188    Handle<SharedFunctionInfo> function) const {
189  Job* job = nullptr;
190  Object function_data = function->function_data(kAcquireLoad);
191  if (function_data.IsUncompiledDataWithPreparseDataAndJob()) {
192    job = reinterpret_cast<Job*>(
193        UncompiledDataWithPreparseDataAndJob::cast(function_data).job());
194  } else if (function_data.IsUncompiledDataWithoutPreparseDataWithJob()) {
195    job = reinterpret_cast<Job*>(
196        UncompiledDataWithoutPreparseDataWithJob::cast(function_data).job());
197  }
198  return job != nullptr;
199}
200
201void LazyCompileDispatcher::WaitForJobIfRunningOnBackground(
202    Job* job, const base::MutexGuard& lock) {
203  TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.compile"),
204               "V8.LazyCompilerDispatcherWaitForBackgroundJob");
205  RCS_SCOPE(isolate_, RuntimeCallCounterId::kCompileWaitForDispatcher);
206
207  if (!job->is_running_on_background()) {
208    if (job->state == Job::State::kPending) {
209      DCHECK_EQ(std::count(pending_background_jobs_.begin(),
210                           pending_background_jobs_.end(), job),
211                1);
212
213      // TODO(leszeks): Remove from pending jobs without walking the whole
214      // vector.
215      pending_background_jobs_.erase(
216          std::remove(pending_background_jobs_.begin(),
217                      pending_background_jobs_.end(), job));
218      job->state = Job::State::kPendingToRunOnForeground;
219      NotifyRemovedBackgroundJob(lock);
220    } else {
221      DCHECK_EQ(job->state, Job::State::kReadyToFinalize);
222      DCHECK_EQ(
223          std::count(finalizable_jobs_.begin(), finalizable_jobs_.end(), job),
224          1);
225
226      // TODO(leszeks): Remove from finalizable jobs without walking the whole
227      // vector.
228      finalizable_jobs_.erase(
229          std::remove(finalizable_jobs_.begin(), finalizable_jobs_.end(), job));
230      job->state = Job::State::kFinalizingNow;
231    }
232    return;
233  }
234  DCHECK_NULL(main_thread_blocking_on_job_);
235  main_thread_blocking_on_job_ = job;
236  while (main_thread_blocking_on_job_ != nullptr) {
237    main_thread_blocking_signal_.Wait(&mutex_);
238  }
239
240  DCHECK_EQ(job->state, Job::State::kReadyToFinalize);
241  DCHECK_EQ(std::count(finalizable_jobs_.begin(), finalizable_jobs_.end(), job),
242            1);
243
244  // TODO(leszeks): Remove from finalizable jobs without walking the whole
245  // vector.
246  finalizable_jobs_.erase(
247      std::remove(finalizable_jobs_.begin(), finalizable_jobs_.end(), job));
248  job->state = Job::State::kFinalizingNow;
249}
250
251bool LazyCompileDispatcher::FinishNow(Handle<SharedFunctionInfo> function) {
252  TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.compile"),
253               "V8.LazyCompilerDispatcherFinishNow");
254  RCS_SCOPE(isolate_, RuntimeCallCounterId::kCompileFinishNowOnDispatcher);
255  if (trace_compiler_dispatcher_) {
256    PrintF("LazyCompileDispatcher: finishing ");
257    function->ShortPrint();
258    PrintF(" now\n");
259  }
260
261  Job* job;
262
263  {
264    base::MutexGuard lock(&mutex_);
265    job = GetJobFor(function, lock);
266    WaitForJobIfRunningOnBackground(job, lock);
267  }
268
269  if (job->state == Job::State::kPendingToRunOnForeground) {
270    job->task->RunOnMainThread(isolate_);
271    job->state = Job::State::kFinalizingNow;
272  }
273
274  if (DEBUG_BOOL) {
275    base::MutexGuard lock(&mutex_);
276    DCHECK_EQ(std::count(pending_background_jobs_.begin(),
277                         pending_background_jobs_.end(), job),
278              0);
279    DCHECK_EQ(
280        std::count(finalizable_jobs_.begin(), finalizable_jobs_.end(), job), 0);
281    DCHECK_EQ(job->state, Job::State::kFinalizingNow);
282  }
283
284  bool success = Compiler::FinalizeBackgroundCompileTask(
285      job->task.get(), isolate_, Compiler::KEEP_EXCEPTION);
286  job->state = Job::State::kFinalized;
287
288  DCHECK_NE(success, isolate_->has_pending_exception());
289  DeleteJob(job);
290
291  // Opportunistically finalize all other jobs for a maximum time of
292  // kMaxOpportunisticFinalizeTimeMs.
293  double deadline_in_seconds = platform_->MonotonicallyIncreasingTime() +
294                               kMaxOpportunisticFinalizeTimeMs / 1000.0;
295  while (deadline_in_seconds > platform_->MonotonicallyIncreasingTime()) {
296    if (!FinalizeSingleJob()) break;
297  }
298
299  return success;
300}
301
302void LazyCompileDispatcher::AbortJob(Handle<SharedFunctionInfo> shared_info) {
303  if (trace_compiler_dispatcher_) {
304    PrintF("LazyCompileDispatcher: aborting job for ");
305    shared_info->ShortPrint();
306    PrintF("\n");
307  }
308  base::LockGuard<base::Mutex> lock(&mutex_);
309
310  Job* job = GetJobFor(shared_info, lock);
311  if (job->is_running_on_background()) {
312    // Job is currently running on the background thread, wait until it's done
313    // and remove job then.
314    job->state = Job::State::kAbortRequested;
315  } else {
316    if (job->state == Job::State::kPending) {
317      DCHECK_EQ(std::count(pending_background_jobs_.begin(),
318                           pending_background_jobs_.end(), job),
319                1);
320
321      pending_background_jobs_.erase(
322          std::remove(pending_background_jobs_.begin(),
323                      pending_background_jobs_.end(), job));
324      job->state = Job::State::kAbortingNow;
325      NotifyRemovedBackgroundJob(lock);
326    } else if (job->state == Job::State::kReadyToFinalize) {
327      DCHECK_EQ(
328          std::count(finalizable_jobs_.begin(), finalizable_jobs_.end(), job),
329          1);
330
331      finalizable_jobs_.erase(
332          std::remove(finalizable_jobs_.begin(), finalizable_jobs_.end(), job));
333      job->state = Job::State::kAbortingNow;
334    } else {
335      UNREACHABLE();
336    }
337    job->task->AbortFunction();
338    job->state = Job::State::kFinalized;
339    DeleteJob(job, lock);
340  }
341}
342
343void LazyCompileDispatcher::AbortAll() {
344  idle_task_manager_->TryAbortAll();
345  job_handle_->Cancel();
346
347  {
348    base::MutexGuard lock(&mutex_);
349    for (Job* job : pending_background_jobs_) {
350      job->task->AbortFunction();
351      job->state = Job::State::kFinalized;
352      DeleteJob(job, lock);
353    }
354    pending_background_jobs_.clear();
355    for (Job* job : finalizable_jobs_) {
356      job->task->AbortFunction();
357      job->state = Job::State::kFinalized;
358      DeleteJob(job, lock);
359    }
360    finalizable_jobs_.clear();
361    for (Job* job : jobs_to_dispose_) {
362      delete job;
363    }
364    jobs_to_dispose_.clear();
365
366    DCHECK_EQ(all_jobs_.size(), 0);
367    num_jobs_for_background_ = 0;
368    VerifyBackgroundTaskCount(lock);
369  }
370
371  idle_task_manager_->CancelAndWait();
372}
373
374LazyCompileDispatcher::Job* LazyCompileDispatcher::GetJobFor(
375    Handle<SharedFunctionInfo> shared, const base::MutexGuard&) const {
376  Object function_data = shared->function_data(kAcquireLoad);
377  if (function_data.IsUncompiledDataWithPreparseDataAndJob()) {
378    return reinterpret_cast<Job*>(
379        UncompiledDataWithPreparseDataAndJob::cast(function_data).job());
380  } else if (function_data.IsUncompiledDataWithoutPreparseDataWithJob()) {
381    return reinterpret_cast<Job*>(
382        UncompiledDataWithoutPreparseDataWithJob::cast(function_data).job());
383  }
384  return nullptr;
385}
386
387void LazyCompileDispatcher::ScheduleIdleTaskFromAnyThread(
388    const base::MutexGuard&) {
389  if (!taskrunner_->IdleTasksEnabled()) return;
390  if (idle_task_scheduled_) return;
391
392  idle_task_scheduled_ = true;
393  // TODO(leszeks): Using a full task manager for a single cancellable task is
394  // overkill, we could probably do the cancelling ourselves.
395  taskrunner_->PostIdleTask(MakeCancelableIdleTask(
396      idle_task_manager_.get(),
397      [this](double deadline_in_seconds) { DoIdleWork(deadline_in_seconds); }));
398}
399
400void LazyCompileDispatcher::DoBackgroundWork(JobDelegate* delegate) {
401  TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.compile"),
402               "V8.LazyCompileDispatcherDoBackgroundWork");
403
404  LocalIsolate isolate(isolate_, ThreadKind::kBackground);
405  UnparkedScope unparked_scope(&isolate);
406  LocalHandleScope handle_scope(&isolate);
407
408  ReusableUnoptimizedCompileState reusable_state(&isolate);
409
410  while (!delegate->ShouldYield()) {
411    Job* job = nullptr;
412    {
413      base::MutexGuard lock(&mutex_);
414
415      if (pending_background_jobs_.empty()) break;
416      job = pending_background_jobs_.back();
417      pending_background_jobs_.pop_back();
418      DCHECK_EQ(job->state, Job::State::kPending);
419
420      job->state = Job::State::kRunning;
421    }
422
423    if (V8_UNLIKELY(block_for_testing_.Value())) {
424      block_for_testing_.SetValue(false);
425      semaphore_for_testing_.Wait();
426    }
427
428    if (trace_compiler_dispatcher_) {
429      PrintF("LazyCompileDispatcher: doing background work\n");
430    }
431
432    job->task->Run(&isolate, &reusable_state);
433
434    {
435      base::MutexGuard lock(&mutex_);
436      if (job->state == Job::State::kRunning) {
437        job->state = Job::State::kReadyToFinalize;
438        // Schedule an idle task to finalize the compilation on the main thread
439        // if the job has a shared function info registered.
440      } else {
441        DCHECK_EQ(job->state, Job::State::kAbortRequested);
442        job->state = Job::State::kAborted;
443      }
444      finalizable_jobs_.push_back(job);
445      NotifyRemovedBackgroundJob(lock);
446
447      if (main_thread_blocking_on_job_ == job) {
448        main_thread_blocking_on_job_ = nullptr;
449        main_thread_blocking_signal_.NotifyOne();
450      } else {
451        ScheduleIdleTaskFromAnyThread(lock);
452      }
453    }
454  }
455
456  while (!delegate->ShouldYield()) {
457    Job* job = nullptr;
458    {
459      base::MutexGuard lock(&mutex_);
460      if (jobs_to_dispose_.empty()) break;
461      job = jobs_to_dispose_.back();
462      jobs_to_dispose_.pop_back();
463      if (jobs_to_dispose_.empty()) {
464        num_jobs_for_background_--;
465      }
466    }
467    delete job;
468  }
469
470  // Don't touch |this| anymore after this point, as it might have been
471  // deleted.
472}
473
474LazyCompileDispatcher::Job* LazyCompileDispatcher::PopSingleFinalizeJob() {
475  base::MutexGuard lock(&mutex_);
476
477  if (finalizable_jobs_.empty()) return nullptr;
478
479  Job* job = finalizable_jobs_.back();
480  finalizable_jobs_.pop_back();
481  DCHECK(job->state == Job::State::kReadyToFinalize ||
482         job->state == Job::State::kAborted);
483  if (job->state == Job::State::kReadyToFinalize) {
484    job->state = Job::State::kFinalizingNow;
485  } else {
486    DCHECK_EQ(job->state, Job::State::kAborted);
487    job->state = Job::State::kAbortingNow;
488  }
489  return job;
490}
491
492bool LazyCompileDispatcher::FinalizeSingleJob() {
493  Job* job = PopSingleFinalizeJob();
494  if (job == nullptr) return false;
495
496  if (trace_compiler_dispatcher_) {
497    PrintF("LazyCompileDispatcher: idle finalizing job\n");
498  }
499
500  if (job->state == Job::State::kFinalizingNow) {
501    HandleScope scope(isolate_);
502    Compiler::FinalizeBackgroundCompileTask(job->task.get(), isolate_,
503                                            Compiler::CLEAR_EXCEPTION);
504  } else {
505    DCHECK_EQ(job->state, Job::State::kAbortingNow);
506    job->task->AbortFunction();
507  }
508  job->state = Job::State::kFinalized;
509  DeleteJob(job);
510  return true;
511}
512
513void LazyCompileDispatcher::DoIdleWork(double deadline_in_seconds) {
514  TRACE_EVENT0(TRACE_DISABLED_BY_DEFAULT("v8.compile"),
515               "V8.LazyCompilerDispatcherDoIdleWork");
516  {
517    base::MutexGuard lock(&mutex_);
518    idle_task_scheduled_ = false;
519  }
520
521  if (trace_compiler_dispatcher_) {
522    PrintF("LazyCompileDispatcher: received %0.1lfms of idle time\n",
523           (deadline_in_seconds - platform_->MonotonicallyIncreasingTime()) *
524               static_cast<double>(base::Time::kMillisecondsPerSecond));
525  }
526  while (deadline_in_seconds > platform_->MonotonicallyIncreasingTime()) {
527    // Find a job which is pending finalization and has a shared function info
528    auto there_was_a_job = FinalizeSingleJob();
529    if (!there_was_a_job) return;
530  }
531
532  // We didn't return above so there still might be jobs to finalize.
533  {
534    base::MutexGuard lock(&mutex_);
535    ScheduleIdleTaskFromAnyThread(lock);
536  }
537}
538
539void LazyCompileDispatcher::DeleteJob(Job* job) {
540  DCHECK(job->state == Job::State::kFinalized);
541  base::MutexGuard lock(&mutex_);
542  DeleteJob(job, lock);
543}
544
545void LazyCompileDispatcher::DeleteJob(Job* job, const base::MutexGuard&) {
546  DCHECK(job->state == Job::State::kFinalized);
547#ifdef DEBUG
548  all_jobs_.erase(job);
549#endif
550  jobs_to_dispose_.push_back(job);
551  if (jobs_to_dispose_.size() == 1) {
552    num_jobs_for_background_++;
553  }
554}
555
556#ifdef DEBUG
557void LazyCompileDispatcher::VerifyBackgroundTaskCount(const base::MutexGuard&) {
558  size_t pending_jobs = 0;
559  size_t running_jobs = 0;
560  size_t finalizable_jobs = 0;
561
562  for (Job* job : all_jobs_) {
563    switch (job->state) {
564      case Job::State::kPending:
565        pending_jobs++;
566        break;
567      case Job::State::kRunning:
568      case Job::State::kAbortRequested:
569        running_jobs++;
570        break;
571      case Job::State::kReadyToFinalize:
572      case Job::State::kAborted:
573        finalizable_jobs++;
574        break;
575      case Job::State::kPendingToRunOnForeground:
576      case Job::State::kFinalizingNow:
577      case Job::State::kAbortingNow:
578      case Job::State::kFinalized:
579        // Ignore.
580        break;
581    }
582  }
583
584  CHECK_EQ(pending_background_jobs_.size(), pending_jobs);
585  CHECK_EQ(finalizable_jobs_.size(), finalizable_jobs);
586  CHECK_EQ(num_jobs_for_background_.load(),
587           pending_jobs + running_jobs + (jobs_to_dispose_.empty() ? 0 : 1));
588}
589#endif
590
591}  // namespace internal
592}  // namespace v8
593