[scheduler] Implement time-based cpu throttling.

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

Index: third_party/WebKit/Source/platform/scheduler/renderer/task_queue_throttler.h
diff --git a/third_party/WebKit/Source/platform/scheduler/renderer/throttling_helper.h b/third_party/WebKit/Source/platform/scheduler/renderer/task_queue_throttler.h
similarity index 45%
rename from third_party/WebKit/Source/platform/scheduler/renderer/throttling_helper.h
rename to third_party/WebKit/Source/platform/scheduler/renderer/task_queue_throttler.h
index c78266c55f731dfa24454e33ade47f1d41c66845..db5957bdb06ec7c4abcd4a661a81519f6c44fb0e 100644
--- a/third_party/WebKit/Source/platform/scheduler/renderer/throttling_helper.h
+++ b/third_party/WebKit/Source/platform/scheduler/renderer/task_queue_throttler.h
@@ -6,8 +6,13 @@
 #define THIRD_PARTY_WEBKIT_SOURCE_PLATFORM_SCHEDULER_RENDERER_THROTTLING_HELPER_H_
 
 #include <set>
+#include <map>
+#include <unordered_map>
 
+#include "base/logging.h"
 #include "base/macros.h"
+#include "base/optional.h"
+#include "base/threading/thread_checker.h"
 #include "platform/scheduler/base/cancelable_closure_holder.h"
 #include "platform/scheduler/base/time_domain.h"
 #include "public/platform/WebViewScheduler.h"
@@ -19,28 +24,88 @@ class RendererSchedulerImpl;
 class ThrottledTimeDomain;
 class WebFrameSchedulerImpl;
 
-// The job of the ThrottlingHelper is to run tasks posted on throttled queues at
-// most once per second. This is done by disabling throttled queues and running
+// The job of the TaskQueueThrottler is to control tasks posted on throttled
+// queues. TaskQueueThrottler
+// - runs throttled tasks once per second,
+// - controls time budget for task queues grouped in TimeBudgetPools.
+// This is done by disabling throttled queues and running
 // a special "heart beat" function |PumpThrottledTasks| which when run
 // temporarily enables throttled queues and inserts a fence to ensure tasks
 // posted from a throttled task run next time the queue is pumped.
 //
-// Of course the ThrottlingHelper isn't the only sub-system that wants to enable
-// or disable queues. E.g. RendererSchedulerImpl also does this for policy
-// reasons.  To prevent the systems from fighting, clients of ThrottlingHelper
-// must use SetQueueEnabled rather than calling the function directly on the
-// queue.
+// Of course the TaskQueueThrottler isn't the only sub-system that wants to
+// enable or disable queues. E.g. RendererSchedulerImpl also does this for
+// policy reasons. To prevent the systems from fighting, clients of
+// TaskQueueThrottler must use SetQueueEnabled rather than calling the function
+// directly on the queue.
 //
 // There may be more than one system that wishes to throttle a queue (e.g.
-// renderer suspension vs tab level suspension) so the ThrottlingHelper keeps a
-// count of the number of systems that wish a queue to be throttled.
+// renderer suspension vs tab level suspension) so the TaskQueueThrottler keeps
+// a count of the number of systems that wish a queue to be throttled.
 // See IncreaseThrottleRefCount & DecreaseThrottleRefCount.
-class BLINK_PLATFORM_EXPORT ThrottlingHelper : public TimeDomain::Observer {
+class BLINK_PLATFORM_EXPORT TaskQueueThrottler : public TimeDomain::Observer {
  public:
-  ThrottlingHelper(RendererSchedulerImpl* renderer_scheduler,
-                   const char* tracing_category);
+  // This class is main-thread only.

[alex clarke (OOO till 29th), 2016/09/12 17:45:27]

The TaskQueueThrottler (nee-ThrottlingHelper) is main thread only so consider
moving this comment to the top level.

If we're worried some of the calls may come from the wrong thread, consider
adding a debug-only checker.

[altimin, 2016/09/14 11:23:18]

Done.

+  class TimeBudgetPool {

[alex clarke (OOO till 29th), 2016/09/12 17:45:27]

Do we even want this API to be public?

[alex clarke (OOO till 29th), 2016/09/12 17:45:27]

Please add an overview comment explaining what the job of TimeBudgetPool is.

[altimin, 2016/09/14 11:23:18]

Done.

[altimin, 2016/09/14 11:23:18]

It's public inside scheduler and I think we want to keep it this way — it was
our explicit goal to provide a basis for a number of interventions.

+   public:
+    ~TimeBudgetPool();
 
-  ~ThrottlingHelper() override;
+    // Throttle task queues from this time budget pool if tasks are running
+    // for more than |cpu_percentage| per cent of wall time.
+    // This function does not affect internal time budget level.
+    void SetTimeBudget(base::TimeTicks now, double cpu_percentage);
+
+    void AddQueue(base::TimeTicks now, TaskQueue* queue);

[alex clarke (OOO till 29th), 2016/09/12 17:45:27]

Please document these.  Side effects such |queue| getting disabled are a bit
surprising to me given the name.   

Note without seeing the code that uses this I can't tell if this is a problem
with the name or the functionality yet.

[Sami, 2016/09/12 17:49:10]

We should probably document the side-effects here (queue gets disabled etc.)

[altimin, 2016/09/14 11:23:17]

Done.

[altimin, 2016/09/14 11:23:17]

Done.

+    void RemoveQueue(base::TimeTicks now, TaskQueue* queue);
+
+    void RecordTaskRunTime(base::TimeDelta task_run_time);

[Sami, 2016/09/12 17:49:10]

Does all of this functionality need to be public or could we move the parts that
only the throttler needs to be private?

Alternatively should we make this class private and just provide the few
entrypoints we need in the TaskQueueThrottler public API?

[altimin, 2016/09/14 11:23:18]

Done.

+
+    bool IsAllowedToRun(base::TimeTicks now);
+    base::TimeTicks NextAllowedRunTime();
+
+    void Enable(base::TimeTicks now);

[alex clarke (OOO till 29th), 2016/09/12 17:45:27]

Please document Enable & Disable.

[Sami, 2016/09/12 17:49:10]

What do enable/disable mean for a budget pool? Maybe there's a more descriptive
operation name we could use?

[altimin, 2016/09/14 11:23:17]

Done.

[altimin, 2016/09/14 11:23:18]

It means "activate this pool and start throttling queues associated with it".
Main use case is when renderer is backgrounded/foregrounded we want to
enable/disable time budget pool corresponding to throttling background tabs.

+    void Disable(base::TimeTicks now);
+    bool IsEnabled() const;
+
+    const char* Name() const;
+
+    // All queues should be removed before calling Close().
+    void Close();

[alex clarke (OOO till 29th), 2016/09/12 17:45:27]

This only seems to be called by test code, is that expected?  Makes it hard to
understand the lifetime of this object.

[altimin, 2016/09/14 11:23:17]

For the moment — yes, it's expected.
Lifetime is simple — it's deleted when Close() is called or when
TaskQueueThrottler (and RendererScheduler) is deleted.

+
+   private:
+    friend class TaskQueueThrottler;
+
+    TimeBudgetPool(const char* name,
+                   TaskQueueThrottler* task_queue_throttler,
+                   base::TimeTicks now);
+
+    // Advances |last_checkpoint_| to |now| if needed and recalculates
+    // budget level.
+    void Advance(base::TimeTicks now);
+
+    // Returns state for tracing.
+    void AsValueInto(base::trace_event::TracedValue* state,
+                     base::TimeTicks now) const;
+
+    const char* name_;  // NOT OWNED
+
+    TaskQueueThrottler* task_queue_throttler_;
+
+    base::TimeDelta current_budget_level_;
+    base::TimeDelta max_budget_level_;
+    base::TimeTicks last_checkpoint_;
+    double cpu_percentage_;
+    bool is_enabled_;
+
+    std::unordered_set<TaskQueue*> assosiated_task_queues_;

[Sami, 2016/09/12 17:49:10]

typo: associated.

Also I think we need to make these refpointers to make sure the queues don't get
deleted from under us?

[altimin, 2016/09/14 11:23:17]

Done.

+
+    DISALLOW_COPY_AND_ASSIGN(TimeBudgetPool);
+  };
+
+  TaskQueueThrottler(RendererSchedulerImpl* renderer_scheduler,
+                     const char* tracing_category);
+
+  ~TaskQueueThrottler() override;
 
   // TimeDomain::Observer implementation:
   void OnTimeDomainHasImmediateWork() override;
@@ -48,7 +113,7 @@ class BLINK_PLATFORM_EXPORT ThrottlingHelper : public TimeDomain::Observer {
 
   // The purpose of this method is to make sure throttling doesn't conflict with
   // enabling/disabling the queue for policy reasons.
-  // If |task_queue| is throttled then the ThrottlingHelper remembers the
+  // If |task_queue| is throttled then the TaskQueueThrottler remembers the
   // |enabled| setting.  In addition if |enabled| is false then the queue is
   // immediatly disabled.  Otherwise if |task_queue| not throttled then
   // TaskQueue::SetEnabled(enabled) is called.
@@ -69,16 +134,27 @@ class BLINK_PLATFORM_EXPORT ThrottlingHelper : public TimeDomain::Observer {
   // Returns true if the |task_queue| is throttled.
   bool IsThrottled(TaskQueue* task_queue) const;
 
-  // Tells the ThrottlingHelper we're using virtual time, which disables all
+  // Tells the TaskQueueThrottler we're using virtual time, which disables all
   // throttling.
   void EnableVirtualTime();
 
   const ThrottledTimeDomain* time_domain() const { return time_domain_.get(); }
 
-  static base::TimeTicks ThrottledRunTime(base::TimeTicks unthrottled_runtime);
+  static base::TimeTicks AlignedThrottledRunTime(
+      base::TimeTicks unthrottled_runtime);
 
   const scoped_refptr<TaskQueue>& task_runner() const { return task_runner_; }
 
+  // Returned object is owned by |TaskQueueThrottler|.
+  TimeBudgetPool* CreateTimeBudgetPool(const char* name);

[alex clarke (OOO till 29th), 2016/09/12 17:45:26]

This only seems to be called by tests, is that expected?

[altimin, 2016/09/14 11:23:18]

For the moment yes, but it will change in the next patch.

+
+  void OnTaskRunTimeReported(TaskQueue* task_queue,
+                             base::TimeTicks start_time,
+                             base::TimeTicks end_time);
+
+  void AsValueInto(base::trace_event::TracedValue* state,
+                   base::TimeTicks now) const;
+
  private:
   struct Metadata {
     Metadata() : throttling_ref_count(0), enabled(false) {}
@@ -96,10 +172,22 @@ class BLINK_PLATFORM_EXPORT ThrottlingHelper : public TimeDomain::Observer {
   // Note |unthrottled_runtime| might be in the past. When this happens we
   // compute the delay to the next runtime based on now rather than
   // unthrottled_runtime.
-  void MaybeSchedulePumpThrottledTasksLocked(
+  void MaybeSchedulePumpThrottledTasks(
       const tracked_objects::Location& from_here,
       base::TimeTicks now,
-      base::TimeTicks unthrottled_runtime);
+      base::TimeTicks runtime);
+
+  TimeBudgetPool* GetTimeBudgetPoolForQueue(TaskQueue* queue);
+
+  // Schedule pumping because of given task queue.
+  void MaybeSchedulePumpQueue(const tracked_objects::Location& from_here,
+                              base::TimeTicks now,
+                              TaskQueue* queue);
+  void MaybeSchedulePumpQueueWithBudget(
+      const tracked_objects::Location& from_here,
+      base::TimeTicks now,
+      TaskQueue* queue,
+      TimeBudgetPool* budget);
 
   TaskQueueMap throttled_queues_;
   base::Closure forward_immediate_work_closure_;
@@ -110,12 +198,16 @@ class BLINK_PLATFORM_EXPORT ThrottlingHelper : public TimeDomain::Observer {
   std::unique_ptr<ThrottledTimeDomain> time_domain_;
 
   CancelableClosureHolder pump_throttled_tasks_closure_;
-  base::TimeTicks pending_pump_throttled_tasks_runtime_;
+  base::Optional<base::TimeTicks> pending_pump_throttled_tasks_runtime_;
   bool virtual_time_;
 
-  base::WeakPtrFactory<ThrottlingHelper> weak_factory_;
+  std::unordered_map<TimeBudgetPool*, std::unique_ptr<TimeBudgetPool>>
+      time_budget_pools_;

[alex clarke (OOO till 29th), 2016/09/12 17:45:27]

This construct gives me pause for thought.  I can't tell what the lifecycle of
TimeBudgetPool is outside of tests yet, but this makes me wonder if is should
actually be ref counted?

[altimin, 2016/09/14 11:23:18]

My understanding was that TaskQueueThrottler (and RendererScheduler) outlive
pretty much everything in renderer. If this is correct, this approach should be
fine.

+  std::unordered_map<TaskQueue*, TimeBudgetPool*> time_budget_pool_for_queue_;

[alex clarke (OOO till 29th), 2016/09/12 17:45:27]

Can we instead move TimeBudgetPool* into struct Metadata?

[altimin, 2016/09/14 11:23:17]

It will break the assumption that queue is throttled when it is in
throttled_queues_. I'm not sure if we want to do it.

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

I don't see why we'd want to have multiple maps (the map itself has overhead).
Instead I think we can simply add a is_throttled bool to Metadata.

+
+  base::WeakPtrFactory<TaskQueueThrottler> weak_factory_;
 
-  DISALLOW_COPY_AND_ASSIGN(ThrottlingHelper);
+  DISALLOW_COPY_AND_ASSIGN(TaskQueueThrottler);
 };
 
 }  // namespace scheduler