[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 "base/logging.h"
+#include "base/memory/ptr_util.h"
+#include "base/optional.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"
 
 namespace blink {
 namespace scheduler {
 
-ThrottlingHelper::ThrottlingHelper(RendererSchedulerImpl* renderer_scheduler,
-                                   const char* tracing_category)
+namespace {
+const base::TimeDelta kMaxTimeBudget = base::TimeDelta::FromSeconds(1);

[Sami, 2016/09/07 15:20:43]

No static global non-pod constructors please.

[altimin, 2016/09/09 15:43:58]

Done.

+}
+
+TaskQueueThrottler::TimeBudgetPool::TimeBudgetPool(
+    TaskQueueThrottler* task_queue_throttler,
+    base::TimeTicks now)
+    : task_queue_throttler_(task_queue_throttler),
+      last_checkpoint_(now),
+      cpu_percentage_(1) {}
+
+TaskQueueThrottler::TimeBudgetPool::~TimeBudgetPool() {}
+
+void TaskQueueThrottler::TimeBudgetPool::SetTimeBudget(double cpu_percentage) {
+  cpu_percentage_ = cpu_percentage;
+  current_budget_level_ = base::TimeDelta();
+}
+
+void TaskQueueThrottler::TimeBudgetPool::AddQueue(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;

[Sami, 2016/09/07 15:20:43]

Do we need to disable the queue if the budget has run out?

[altimin, 2016/09/09 15:43:58]

Done.

+}
+
+void TaskQueueThrottler::TimeBudgetPool::RemoveQueue(TaskQueue* queue) {
+  DCHECK_EQ(task_queue_throttler_->time_budget_pool_for_queue_[queue], this);
+  task_queue_throttler_->time_budget_pool_for_queue_.erase(queue);

[Sami, 2016/09/07 15:20:43]

Do we need to re-enable the queue?

[altimin, 2016/09/09 15:43:58]

Done.

+}
+
+void TaskQueueThrottler::TimeBudgetPool::Close() {
+  task_queue_throttler_->time_budget_pools_.erase(this);
+}
+
+bool TaskQueueThrottler::TimeBudgetPool::IsAllowedToRun(base::TimeTicks now) {
+  if (now > last_checkpoint_) {
+    current_budget_level_ = std::min(
+        current_budget_level_ + cpu_percentage_ * (now - last_checkpoint_),
+        kMaxTimeBudget);
+    last_checkpoint_ = now;
+  }
+
+  return current_budget_level_.InMicroseconds() >= 0;
+}
+
+base::TimeTicks TaskQueueThrottler::TimeBudgetPool::NextAllowedRunTime() {
+  if (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) {
+  current_budget_level_ -= task_run_time;
+}
+
+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()) {
         OnTimeDomainHasImmediateWork();
       } else {
         OnTimeDomainHasDelayedWork();
       }
     }
   } 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);
   }
 }
 
-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");
   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);
+}
+
+}  // namespace
+
+void TaskQueueThrottler::PumpThrottledTasks() {
+  TRACE_EVENT0(tracing_category_, "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 = time_budget_pool_for_queue_[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);
+      continue;

[Sami, 2016/09/07 15:20:43]

Should we add a trace event here so we can see when things get throttled?

For bonus points please also add a call from RendererSchedulerImpl::AsValue() to
here so we can see the remaining budgets of each queue. Basically I want make it
as easy as possible to debug any mysterious failures that come our way once this
lands.

[altimin, 2016/09/09 15:43:57]

Done.

+    }
+
     task_queue->SetQueueEnabled(true);
     task_queue->InsertFence();
+
+    base::TimeTicks wakeup;

[Sami, 2016/09/07 15:20:43]

nit: wake_up

[altimin, 2016/09/09 15:43:58]

Done.

+    if (task_queue->NextScheduledWakeUp(&wakeup)) {
+      next_scheduled_delayed_task = Min(next_scheduled_delayed_task, wakeup);
+    }
   }
-  // Make sure NextScheduledRunTime gives us an up-to date result.
-  time_domain_->ClearExpiredWakeups();

[Sami, 2016/09/07 15:20:43]

Do we need to remove this?

[altimin, 2016/09/09 15:43:57]

Yes, now we don't rely on TimeDomain::NextScheduledRunTime — we get more
fine-grained results from each queue.

 
-  base::TimeTicks next_scheduled_delayed_task;
-  // Maybe schedule a call to ThrottlingHelper::PumpThrottledTasks if there is

[Sami, 2016/09/07 15:20:43]

Is this comment still valid?

[altimin, 2016/09/09 15:43:58]

Done.

-  // 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);
+  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() {
+  TimeBudgetPool* time_budget_pool =
+      new TimeBudgetPool(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) {
+  auto find_it = throttled_queues_.find(task_queue);
+  if (find_it == throttled_queues_.end()) {
+    return;
+  }
+
+  TimeBudgetPool* time_budget_pool = time_budget_pool_for_queue_[task_queue];
+  if (time_budget_pool) {

[Sami, 2016/09/07 15:20:43]

Can this ever be null?

[altimin, 2016/09/09 15:43:58]

Done.

+    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);
+
+      base::TimeTicks now = tick_clock_->NowTicks();

[Sami, 2016/09/07 15:20:43]

Could we just use end_time for this? If not, move this inside the 'if'?

[altimin, 2016/09/09 15:43:58]

Done.

+
+      if (task_queue->HasPendingImmediateWork()) {
+        MaybeSchedulePumpThrottledTasks(
+            FROM_HERE, now,
+            std::max(now, time_budget_pool->NextAllowedRunTime()));
+      }
+    }
+  }
+}
+
 }  // namespace scheduler
 }  // namespace blink