[scheduler] Implement time-based cpu throttling.

third_party/WebKit/Source/platform/scheduler/renderer/task_queue_throttler.cc

 // Copyright 2015 The Chromium 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 "platform/scheduler/renderer/throttling_helper.h"
+#include "platform/scheduler/renderer/task_queue_throttler.h"
 
+#include <cstdint>
+
+#include "base/format_macros.h"
 #include "base/logging.h"
+#include "base/memory/ptr_util.h"
+#include "base/optional.h"
+#include "base/strings/stringprintf.h"
 #include "platform/scheduler/base/real_time_domain.h"
 #include "platform/scheduler/child/scheduler_tqm_delegate.h"
 #include "platform/scheduler/renderer/auto_advancing_virtual_time_domain.h"
 #include "platform/scheduler/renderer/renderer_scheduler_impl.h"
 #include "platform/scheduler/renderer/throttled_time_domain.h"
 #include "platform/scheduler/renderer/web_frame_scheduler_impl.h"
 #include "public/platform/WebFrameScheduler.h"
 
+#include <iostream>  // FIXME
+
 namespace blink {
 namespace scheduler {
 
-ThrottlingHelper::ThrottlingHelper(RendererSchedulerImpl* renderer_scheduler,
-                                   const char* tracing_category)
+namespace {
+const int kMaxBudgetLevelInSeconds = 1;
+}
+
+TaskQueueThrottler::TimeBudgetPool::TimeBudgetPool(
+    const char* name,
+    TaskQueueThrottler* task_queue_throttler,
+    base::TimeTicks now)
+    : name_(name),
+      task_queue_throttler_(task_queue_throttler),
+      max_budget_level_(base::TimeDelta::FromSeconds(kMaxBudgetLevelInSeconds)),
+      last_checkpoint_(now),
+      cpu_percentage_(1),
+      is_enabled_(true) {}
+
+TaskQueueThrottler::TimeBudgetPool::~TimeBudgetPool() {}
+
+void TaskQueueThrottler::TimeBudgetPool::SetTimeBudget(base::TimeTicks now,
+                                                       double cpu_percentage) {
+  Advance(now);
+  cpu_percentage_ = cpu_percentage;
+}
+
+void TaskQueueThrottler::TimeBudgetPool::AddQueue(base::TimeTicks now,
+                                                  TaskQueue* queue) {
+  DCHECK(task_queue_throttler_->time_budget_pool_for_queue_.find(queue) ==
+         task_queue_throttler_->time_budget_pool_for_queue_.end());
+  task_queue_throttler_->time_budget_pool_for_queue_[queue] = this;
+
+  associated_task_queues_.insert(queue);
+
+  if (!task_queue_throttler_->IsThrottled(queue))
+    return;
+
+  queue->SetQueueEnabled(false);
+
+  task_queue_throttler_->MaybeSchedulePumpQueue(FROM_HERE, now, queue,
+                                                NextAllowedRunTime());
+}
+
+void TaskQueueThrottler::TimeBudgetPool::RemoveQueue(base::TimeTicks now,
+                                                     TaskQueue* queue) {
+  DCHECK_EQ(task_queue_throttler_->time_budget_pool_for_queue_[queue], this);
+  task_queue_throttler_->time_budget_pool_for_queue_.erase(queue);
+
+  associated_task_queues_.erase(queue);
+
+  if (!task_queue_throttler_->IsThrottled(queue))
+    return;
+
+  task_queue_throttler_->MaybeSchedulePumpQueue(FROM_HERE, now, queue);
+}
+
+void TaskQueueThrottler::TimeBudgetPool::Enable(LazyNow* lazy_now) {
+  if (is_enabled_)
+    return;
+  is_enabled_ = true;
+
+  for (TaskQueue* queue : associated_task_queues_) {
+    if (!task_queue_throttler_->IsThrottled(queue))
+      continue;
+
+    queue->SetQueueEnabled(false);
+
+    task_queue_throttler_->MaybeSchedulePumpQueue(FROM_HERE, lazy_now->Now(),
+                                                  queue, NextAllowedRunTime());
+  }
+}
+
+void TaskQueueThrottler::TimeBudgetPool::Disable(LazyNow* lazy_now) {
+  if (!is_enabled_)
+    return;
+  is_enabled_ = false;
+
+  for (TaskQueue* queue : associated_task_queues_) {
+    if (!task_queue_throttler_->IsThrottled(queue))
+      continue;
+
+    task_queue_throttler_->MaybeSchedulePumpQueue(FROM_HERE, lazy_now->Now(),
+                                                  queue);
+  }
+}
+
+bool TaskQueueThrottler::TimeBudgetPool::IsEnabled() const {
+  return is_enabled_;
+}
+
+void TaskQueueThrottler::TimeBudgetPool::Close() {
+  DCHECK_EQ(0u, associated_task_queues_.size());
+
+  task_queue_throttler_->time_budget_pools_.erase(this);
+}
+
+bool TaskQueueThrottler::TimeBudgetPool::IsAllowedToRun(base::TimeTicks now) {
+  Advance(now);
+  return !is_enabled_ || current_budget_level_.InMicroseconds() >= 0;
+}
+
+base::TimeTicks TaskQueueThrottler::TimeBudgetPool::NextAllowedRunTime() {
+  if (!is_enabled_ || current_budget_level_.InMicroseconds() >= 0) {
+    return last_checkpoint_;
+  } else {
+    // Subtract because current_budget is negative.
+    return last_checkpoint_ - current_budget_level_ / cpu_percentage_;
+  }
+}
+
+void TaskQueueThrottler::TimeBudgetPool::RecordTaskRunTime(
+    base::TimeDelta task_run_time) {
+  if (is_enabled_) {
+    current_budget_level_ -= task_run_time;
+  }
+}
+
+const char* TaskQueueThrottler::TimeBudgetPool::Name() const {
+  return name_;
+}
+
+void TaskQueueThrottler::TimeBudgetPool::AsValueInto(
+    base::trace_event::TracedValue* state,
+    base::TimeTicks now) const {
+  state->BeginDictionary();
+
+  state->SetString("name", name_);
+  state->SetDouble("time_budget", cpu_percentage_);
+  state->SetDouble("time_budget_level_in_seconds",
+                   current_budget_level_.InSecondsF());
+  state->SetDouble("last_checkpoint_seconds_ago",
+                   (now - last_checkpoint_).InSecondsF());
+
+  state->BeginArray("task_queues");
+  for (TaskQueue* queue : associated_task_queues_) {
+    state->AppendString(base::StringPrintf(
+        "%" PRIx64, static_cast<uint64_t>(reinterpret_cast<uintptr_t>(queue))));
+  }
+  state->EndArray();
+
+  state->EndDictionary();
+}
+
+void TaskQueueThrottler::TimeBudgetPool::Advance(base::TimeTicks now) {
+  if (now > last_checkpoint_) {
+    if (is_enabled_) {
+      current_budget_level_ = std::min(
+          current_budget_level_ + cpu_percentage_ * (now - last_checkpoint_),
+          max_budget_level_);
+    }
+    last_checkpoint_ = now;
+  }
+}
+
+TaskQueueThrottler::TaskQueueThrottler(
+    RendererSchedulerImpl* renderer_scheduler,
+    const char* tracing_category)
     : task_runner_(renderer_scheduler->ControlTaskRunner()),
       renderer_scheduler_(renderer_scheduler),
       tick_clock_(renderer_scheduler->tick_clock()),
       tracing_category_(tracing_category),
       time_domain_(new ThrottledTimeDomain(this, tracing_category)),
       virtual_time_(false),
       weak_factory_(this) {
   pump_throttled_tasks_closure_.Reset(base::Bind(
-      &ThrottlingHelper::PumpThrottledTasks, weak_factory_.GetWeakPtr()));
+      &TaskQueueThrottler::PumpThrottledTasks, weak_factory_.GetWeakPtr()));
   forward_immediate_work_closure_ =
-      base::Bind(&ThrottlingHelper::OnTimeDomainHasImmediateWork,
+      base::Bind(&TaskQueueThrottler::OnTimeDomainHasImmediateWork,
                  weak_factory_.GetWeakPtr());
 
   renderer_scheduler_->RegisterTimeDomain(time_domain_.get());
 }
 
-ThrottlingHelper::~ThrottlingHelper() {
+TaskQueueThrottler::~TaskQueueThrottler() {
   // It's possible for queues to be still throttled, so we need to tidy up
   // before unregistering the time domain.
   for (const TaskQueueMap::value_type& map_entry : throttled_queues_) {
     TaskQueue* task_queue = map_entry.first;
     task_queue->SetTimeDomain(renderer_scheduler_->real_time_domain());
     task_queue->RemoveFence();
   }
 
   renderer_scheduler_->UnregisterTimeDomain(time_domain_.get());
 }
 
-void ThrottlingHelper::SetQueueEnabled(TaskQueue* task_queue, bool enabled) {
+void TaskQueueThrottler::SetQueueEnabled(TaskQueue* task_queue, bool enabled) {
   TaskQueueMap::iterator find_it = throttled_queues_.find(task_queue);
 
   if (find_it == throttled_queues_.end()) {
     task_queue->SetQueueEnabled(enabled);
     return;
   }
 
   find_it->second.enabled = enabled;
 
   // We don't enable the queue here because it's throttled and there might be
   // tasks in it's work queue that would execute immediatly rather than after
   // PumpThrottledTasks runs.
   if (!enabled)
     task_queue->SetQueueEnabled(false);
 }
 
-void ThrottlingHelper::IncreaseThrottleRefCount(TaskQueue* task_queue) {
+void TaskQueueThrottler::IncreaseThrottleRefCount(TaskQueue* task_queue) {
   DCHECK_NE(task_queue, task_runner_.get());
 
   if (virtual_time_)
     return;
 
   std::pair<TaskQueueMap::iterator, bool> insert_result =
       throttled_queues_.insert(std::make_pair(
           task_queue, Metadata(1, task_queue->IsQueueEnabled())));
 
   if (insert_result.second) {
-    // The insert was succesful so we need to throttle the queue.
+    // The insert was successful so we need to throttle the queue.
     task_queue->SetTimeDomain(time_domain_.get());
     task_queue->RemoveFence();
     task_queue->SetQueueEnabled(false);
 
-    if (!task_queue->IsEmpty()) {
-      if (task_queue->HasPendingImmediateWork()) {

[alex clarke (OOO till 29th), 2016/09/14 12:36:34]

Do we need to change this?

[altimin, 2016/09/14 18:34:49]

Done.

-        OnTimeDomainHasImmediateWork();
-      } else {
-        OnTimeDomainHasDelayedWork();
-      }
+    base::Optional<base::TimeTicks> next_run_time =
+        task_queue->GetNextTaskRunTime();
+
+    if (next_run_time) {
+      MaybeSchedulePumpThrottledTasks(FROM_HERE, tick_clock_->NowTicks(),
+                                      next_run_time.value());
+
+      TRACE_EVENT1(tracing_category_, "TaskQueueThrottler_TaskQueueThrottled",
+                   "task_queue", task_queue);
     }
   } else {
     // An entry already existed in the map so we need to increment the refcount.
     insert_result.first->second.throttling_ref_count++;
   }
 }
 
-void ThrottlingHelper::DecreaseThrottleRefCount(TaskQueue* task_queue) {
+void TaskQueueThrottler::DecreaseThrottleRefCount(TaskQueue* task_queue) {
   if (virtual_time_)
     return;
 
   TaskQueueMap::iterator iter = throttled_queues_.find(task_queue);
 
   if (iter != throttled_queues_.end() &&
       --iter->second.throttling_ref_count == 0) {
     bool enabled = iter->second.enabled;
     // The refcount has become zero, we need to unthrottle the queue.
     throttled_queues_.erase(iter);
 
     task_queue->SetTimeDomain(renderer_scheduler_->real_time_domain());
     task_queue->RemoveFence();
     task_queue->SetQueueEnabled(enabled);
+
+    TRACE_EVENT1(tracing_category_, "TaskQueueThrottler_TaskQueueUntrottled",
+                 "task_queue", task_queue);
   }
 }
 
-bool ThrottlingHelper::IsThrottled(TaskQueue* task_queue) const {
+bool TaskQueueThrottler::IsThrottled(TaskQueue* task_queue) const {
   return throttled_queues_.find(task_queue) != throttled_queues_.end();
 }
 
-void ThrottlingHelper::UnregisterTaskQueue(TaskQueue* task_queue) {
+void TaskQueueThrottler::UnregisterTaskQueue(TaskQueue* task_queue) {
   throttled_queues_.erase(task_queue);
 }
 
-void ThrottlingHelper::OnTimeDomainHasImmediateWork() {
+void TaskQueueThrottler::OnTimeDomainHasImmediateWork() {
   // Forward to the main thread if called from another thread.
   if (!task_runner_->RunsTasksOnCurrentThread()) {
     task_runner_->PostTask(FROM_HERE, forward_immediate_work_closure_);
     return;
   }
   TRACE_EVENT0(tracing_category_,
-               "ThrottlingHelper::OnTimeDomainHasImmediateWork");
+               "TaskQueueThrottler::OnTimeDomainHasImmediateWork");
   base::TimeTicks now = tick_clock_->NowTicks();
-  MaybeSchedulePumpThrottledTasksLocked(FROM_HERE, now, now);
+  MaybeSchedulePumpThrottledTasks(FROM_HERE, now, now);
 }
 
-void ThrottlingHelper::OnTimeDomainHasDelayedWork() {
+void TaskQueueThrottler::OnTimeDomainHasDelayedWork() {
   TRACE_EVENT0(tracing_category_,
-               "ThrottlingHelper::OnTimeDomainHasDelayedWork");
+               "TaskQueueThrottler::OnTimeDomainHasDelayedWork");
+  // TODO(altimin): Consider using TaskQueue::GetNextTaskRunTime here.
+  // to avoid unnecessary wakeups. Currently it's not possible because
+  // GetNextTaskRunTime requires a lock on the queue and
+  // OnTimeDomainHasDelayedWork can be called from TaskQueueImpl::SetTimeDomain,
+  // which acquires lock.
   base::TimeTicks next_scheduled_delayed_task;
   bool has_delayed_task =
       time_domain_->NextScheduledRunTime(&next_scheduled_delayed_task);
   DCHECK(has_delayed_task);
   base::TimeTicks now = tick_clock_->NowTicks();
-  MaybeSchedulePumpThrottledTasksLocked(FROM_HERE, now,
-                                        next_scheduled_delayed_task);
+  MaybeSchedulePumpThrottledTasks(FROM_HERE, now, next_scheduled_delayed_task);
 }
 
-void ThrottlingHelper::PumpThrottledTasks() {
-  TRACE_EVENT0(tracing_category_, "ThrottlingHelper::PumpThrottledTasks");
-  pending_pump_throttled_tasks_runtime_ = base::TimeTicks();
+namespace {
 
-  LazyNow lazy_low(tick_clock_);
+template <class T>
+T Min(const base::Optional<T>& optional, const T& value) {
+  if (!optional) {
+    return value;
+  }
+  return std::min(optional.value(), value);
+}
+
+template <class T>
+base::Optional<T> Min(const base::Optional<T>& a, const base::Optional<T>& b) {
+  if (!b)
+    return a;
+  if (!a)
+    return b;
+  return std::min(a.value(), b.value());
+}
+
+template <class T>
+base::Optional<T> Max(const base::Optional<T>& a, const base::Optional<T>& b) {
+  if (!b)
+    return a;
+  if (!a)
+    return b;
+  return std::max(a.value(), b.value());
+}
+
+}  // namespace
+
+void TaskQueueThrottler::PumpThrottledTasks() {
+  TRACE_EVENT0("renderer.scheduler", "TaskQueueThrottler::PumpThrottledTasks");
+  pending_pump_throttled_tasks_runtime_.reset();
+
+  LazyNow lazy_now(tick_clock_);
+  base::Optional<base::TimeTicks> next_scheduled_delayed_task;
+
   for (const TaskQueueMap::value_type& map_entry : throttled_queues_) {
     TaskQueue* task_queue = map_entry.first;
     if (!map_entry.second.enabled || task_queue->IsEmpty())
       continue;
 
+    TimeBudgetPool* time_budget_pool = GetTimeBudgetPoolForQueue(task_queue);
+    if (time_budget_pool && !time_budget_pool->IsAllowedToRun(lazy_now.Now())) {
+      base::TimeTicks next_run_time =
+          std::max(time_budget_pool->NextAllowedRunTime(), lazy_now.Now());
+
+      next_scheduled_delayed_task =
+          Min(next_scheduled_delayed_task, next_run_time);
+
+      TRACE_EVENT1(
+          "renderer.scheduler",
+          "TaskQueueThrottler::PumpThrottledTasks_ExpensiveTaskThrottled",
+          "throttle_time_in_seconds",
+          (next_run_time - lazy_now.Now()).InSecondsF());
+
+      renderer_scheduler_->CreateTraceEventObjectSnapshot();
+
+      continue;
+    }
+
+    base::Optional<base::TimeTicks> wake_up =
+        task_queue->GetNextScheduledWakeUp();
+    next_scheduled_delayed_task = Min(next_scheduled_delayed_task, wake_up);
+
+    // GetNextScheduledWakeUp() moves delayed tasks from incoming queue to work
+    // queue, so InsertFence() should be called after it in order to move
+    // ready tasks to delayed work queue before installing a fence.
     task_queue->SetQueueEnabled(true);
     task_queue->InsertFence();
   }
-  // Make sure NextScheduledRunTime gives us an up-to date result.
-  time_domain_->ClearExpiredWakeups();
 
-  base::TimeTicks next_scheduled_delayed_task;
-  // Maybe schedule a call to ThrottlingHelper::PumpThrottledTasks if there is
-  // a pending delayed task. NOTE posting a non-delayed task in the future will
-  // result in ThrottlingHelper::OnTimeDomainHasImmediateWork being called.
-  if (time_domain_->NextScheduledRunTime(&next_scheduled_delayed_task)) {
-    MaybeSchedulePumpThrottledTasksLocked(FROM_HERE, lazy_low.Now(),
-                                          next_scheduled_delayed_task);
+  // Maybe schedule a call to TaskQueueThrottler::PumpThrottledTasks if there is
+  // a pending delayed task or a throttled task ready to run.
+  // NOTE: posting a non-delayed task in the future will result in
+  // TaskQueueThrottler::OnTimeDomainHasImmediateWork being called.
+  if (next_scheduled_delayed_task) {
+    MaybeSchedulePumpThrottledTasks(FROM_HERE, lazy_now.Now(),
+                                    *next_scheduled_delayed_task);
   }
 }
 
 /* static */
-base::TimeTicks ThrottlingHelper::ThrottledRunTime(
+base::TimeTicks TaskQueueThrottler::AlignedThrottledRunTime(
     base::TimeTicks unthrottled_runtime) {
   const base::TimeDelta one_second = base::TimeDelta::FromSeconds(1);
   return unthrottled_runtime + one_second -
          ((unthrottled_runtime - base::TimeTicks()) % one_second);
 }
 
-void ThrottlingHelper::MaybeSchedulePumpThrottledTasksLocked(
+void TaskQueueThrottler::MaybeSchedulePumpThrottledTasks(
     const tracked_objects::Location& from_here,
     base::TimeTicks now,
-    base::TimeTicks unthrottled_runtime) {
+    base::TimeTicks runtime) {
   if (virtual_time_)
     return;
 
-  base::TimeTicks throttled_runtime =
-      ThrottledRunTime(std::max(now, unthrottled_runtime));
+  runtime = std::max(now, AlignedThrottledRunTime(runtime));
+
   // If there is a pending call to PumpThrottledTasks and it's sooner than
-  // |unthrottled_runtime| then return.
-  if (!pending_pump_throttled_tasks_runtime_.is_null() &&
-      throttled_runtime >= pending_pump_throttled_tasks_runtime_) {
+  // |runtime| then return.
+  if (pending_pump_throttled_tasks_runtime_ &&
+      runtime >= pending_pump_throttled_tasks_runtime_.value()) {
     return;
   }
 
-  pending_pump_throttled_tasks_runtime_ = throttled_runtime;
+  pending_pump_throttled_tasks_runtime_ = runtime;
 
   pump_throttled_tasks_closure_.Cancel();
 
-  base::TimeDelta delay = pending_pump_throttled_tasks_runtime_ - now;
+  base::TimeDelta delay = pending_pump_throttled_tasks_runtime_.value() - now;
   TRACE_EVENT1(tracing_category_,
-               "ThrottlingHelper::MaybeSchedulePumpThrottledTasksLocked",
+               "TaskQueueThrottler::MaybeSchedulePumpThrottledTasks",
                "delay_till_next_pump_ms", delay.InMilliseconds());
   task_runner_->PostDelayedTask(
       from_here, pump_throttled_tasks_closure_.callback(), delay);
 }
 
-void ThrottlingHelper::EnableVirtualTime() {
+void TaskQueueThrottler::EnableVirtualTime() {
   virtual_time_ = true;
 
   pump_throttled_tasks_closure_.Cancel();
 
   while (!throttled_queues_.empty()) {
     TaskQueue* task_queue = throttled_queues_.begin()->first;
     bool enabled = throttled_queues_.begin()->second.enabled;
 
     throttled_queues_.erase(throttled_queues_.begin());
 
     task_queue->SetTimeDomain(renderer_scheduler_->GetVirtualTimeDomain());
     task_queue->RemoveFence();
     task_queue->SetQueueEnabled(enabled);
   }
 }
 
+TaskQueueThrottler::TimeBudgetPool* TaskQueueThrottler::CreateTimeBudgetPool(
+    const char* name) {
+  TimeBudgetPool* time_budget_pool =
+      new TimeBudgetPool(name, this, tick_clock_->NowTicks());
+  time_budget_pools_[time_budget_pool] = base::WrapUnique(time_budget_pool);
+  return time_budget_pool;
+}
+
+void TaskQueueThrottler::OnTaskRunTimeReported(TaskQueue* task_queue,
+                                               base::TimeTicks start_time,
+                                               base::TimeTicks end_time) {
+  if (!IsThrottled(task_queue))
+    return;
+
+  TimeBudgetPool* time_budget_pool = GetTimeBudgetPoolForQueue(task_queue);
+  if (time_budget_pool) {
+    time_budget_pool->RecordTaskRunTime(end_time - start_time);
+    if (!time_budget_pool->IsAllowedToRun(end_time)) {
+      // This task was too expensive and all following tasks are throttled
+      // until explicitly allowed.
+      task_queue->SetQueueEnabled(false);
+
+      if (task_queue->HasPendingImmediateWork()) {
+        MaybeSchedulePumpThrottledTasks(
+            FROM_HERE, end_time,
+            std::max(end_time, time_budget_pool->NextAllowedRunTime()));
+      }
+    }
+  }
+}
+
+void TaskQueueThrottler::AsValueInto(base::trace_event::TracedValue* state,
+                                     base::TimeTicks now) const {
+  if (pending_pump_throttled_tasks_runtime_) {
+    state->SetDouble(
+        "next_throttled_tasks_pump_in_seconds",
+        (pending_pump_throttled_tasks_runtime_.value() - now).InSecondsF());
+  }
+
+  state->BeginDictionary("time_budget_pools");
+
+  for (const auto& map_entry : time_budget_pools_) {
+    TaskQueueThrottler::TimeBudgetPool* pool = map_entry.first;
+    pool->AsValueInto(state, now);
+  }
+
+  state->EndDictionary();
+}
+
+TaskQueueThrottler::TimeBudgetPool*
+TaskQueueThrottler::GetTimeBudgetPoolForQueue(TaskQueue* queue) {
+  auto find_it = time_budget_pool_for_queue_.find(queue);
+  if (find_it == time_budget_pool_for_queue_.end()) {
+    return nullptr;
+  } else {
+    TimeBudgetPool* result = find_it->second;
+    DCHECK(result);
+    return result;
+  }
+}
+
+void TaskQueueThrottler::MaybeSchedulePumpQueue(
+    const tracked_objects::Location& from_here,
+    base::TimeTicks now,
+    TaskQueue* queue,
+    base::Optional<base::TimeTicks> next_possible_run_time) {
+  base::Optional<base::TimeTicks> next_run_time =
+      Max(queue->GetNextTaskRunTime(), next_possible_run_time);
+
+  if (next_run_time) {
+    MaybeSchedulePumpThrottledTasks(from_here, now, next_run_time.value());
+  }
+}
+
 }  // namespace scheduler
 }  // namespace blink