Experimental: Chrome side of killing the blink timer heap

content/renderer/scheduler/task_queue_manager.cc

Index: content/renderer/scheduler/task_queue_manager.cc
diff --git a/content/renderer/scheduler/task_queue_manager.cc b/content/renderer/scheduler/task_queue_manager.cc
index f98ef46417e60afda8ba81e6d929a1671e69c2a4..013974e4406f2ee472e2002838315c01cddd6625 100644
--- a/content/renderer/scheduler/task_queue_manager.cc
+++ b/content/renderer/scheduler/task_queue_manager.cc
@@ -5,6 +5,7 @@
 #include "content/renderer/scheduler/task_queue_manager.h"
 
 #include <queue>
+#include <set>
 
 #include "base/bind.h"
 #include "base/trace_event/trace_event.h"
@@ -42,7 +43,7 @@ class TaskQueue : public base::SingleThreadTaskRunner {
   void SetPumpPolicy(TaskQueueManager::PumpPolicy pump_policy);
   void PumpQueue();
 
-  bool UpdateWorkQueue(base::TimeTicks* next_pending_delayed_task,
+  bool UpdateWorkQueue(base::TimeTicks now,
                        const base::PendingTask* previous_task);
   base::PendingTask TakeTaskFromWorkQueue();
 
@@ -67,10 +68,18 @@ class TaskQueue : public base::SingleThreadTaskRunner {
                            base::TimeDelta delay,
                            TaskType task_type);
 
-  // Adds a task at the end of the incoming task queue and schedules a call to
-  // TaskQueueManager::DoWork() if the incoming queue was empty and automatic
-  // pumping is enabled. Can be called on an arbitrary thread.
-  void EnqueueTask(const base::PendingTask& pending_task);
+  // Delayed task posted to the chromium run loop, which calls
+  // ScheduleDelayedWorkLocked to enqueue any delayed timers which should be run
+  // now.
+  void KickDelayedTasks();
+
+  // Enqueues any delayed timers which should be run now, and (maybe) posts
+  // KickDelayedTasks if there isn't already a timer posted on the chromium
+  // runloop for the next task's scheduled run time.
+  bool ScheduleDelayedWorkLocked(base::TimeTicks now);
+
+  // Enqueues any delayed timers which should be run now.
+  void EnqueueReadyDelayedTasksLocked(base::TimeTicks now);
 
   void PumpQueueLocked();
   bool TaskIsOlderThanQueuedTasks(const base::PendingTask* task);
@@ -92,9 +101,8 @@ class TaskQueue : public base::SingleThreadTaskRunner {
   base::TaskQueue incoming_queue_;
   TaskQueueManager::PumpPolicy pump_policy_;
   const char* name_;
-  std::priority_queue<base::TimeTicks,
-                      std::vector<base::TimeTicks>,
-                      std::greater<base::TimeTicks>> delayed_task_run_times_;
+  base::DelayedTaskQueue delayed_task_queue_;
+  std::set<base::TimeTicks> in_flight_kick_delayed_tasks_;
 
   base::TaskQueue work_queue_;
 
@@ -114,6 +122,11 @@ TaskQueue::~TaskQueue() {
 void TaskQueue::WillDeleteTaskQueueManager() {
   base::AutoLock lock(lock_);
   task_queue_manager_ = nullptr;
+
+  // Clear all delayed tasks because we need them to be deleted before the blink
+  // heap goes away.
+  while (!delayed_task_queue_.empty())
+    delayed_task_queue_.pop();
 }
 
 bool TaskQueue::RunsTasksOnCurrentThread() const {
@@ -134,15 +147,56 @@ bool TaskQueue::PostDelayedTaskImpl(const tracked_objects::Location& from_here,
   task_queue_manager_->DidQueueTask(&pending_task);
 
   if (delay > base::TimeDelta()) {
-    pending_task.delayed_run_time = task_queue_manager_->Now() + delay;
-    delayed_task_run_times_.push(pending_task.delayed_run_time);
-    return task_queue_manager_->PostDelayedTask(
-        FROM_HERE, Bind(&TaskQueue::EnqueueTask, this, pending_task), delay);
+    base::TimeTicks now = task_queue_manager_->Now();
+    pending_task.delayed_run_time = now + delay;
+    delayed_task_queue_.push(pending_task);
+    // If we changed the topmost task, then it is time to reschedule.
+    if (delayed_task_queue_.top().task.Equals(pending_task.task))
+      return ScheduleDelayedWorkLocked(now);
+    return true;
   }
   EnqueueTaskLocked(pending_task);
   return true;
 }
 
+void TaskQueue::EnqueueReadyDelayedTasksLocked(base::TimeTicks now) {
+  lock_.AssertAcquired();
+  // Enqueue all delayed tasks that should be running now.
+  while (!delayed_task_queue_.empty() &&
+         delayed_task_queue_.top().delayed_run_time <= now) {
+    in_flight_kick_delayed_tasks_.erase(
+        delayed_task_queue_.top().delayed_run_time);
+    EnqueueTaskLocked(delayed_task_queue_.top());
+    delayed_task_queue_.pop();
+  }
+}
+
+bool TaskQueue::ScheduleDelayedWorkLocked(base::TimeTicks now) {
+  lock_.AssertAcquired();
+  EnqueueReadyDelayedTasksLocked(now);
+
+  // Any remaining tasks are in the future, so queue a task to kick them.
+  if (!delayed_task_queue_.empty()) {
+    base::TimeTicks next_run_time = delayed_task_queue_.top().delayed_run_time;
+    // Make sure we don't have more than one KickDelayedTasks posted for a
+    // particular scheduled run time (note it's fine to have multiple ones in
+    // flight for distinct run times).
+    if (in_flight_kick_delayed_tasks_.find(next_run_time) ==
+        in_flight_kick_delayed_tasks_.end()) {
+      in_flight_kick_delayed_tasks_.insert(next_run_time);
+      base::TimeDelta delay = next_run_time - now;
+      return task_queue_manager_->PostDelayedTask(
+          FROM_HERE, Bind(&TaskQueue::KickDelayedTasks, this), delay);
+    }
+  }
+  return true;
+}
+
+void TaskQueue::KickDelayedTasks() {
+  base::AutoLock lock(lock_);
+  ScheduleDelayedWorkLocked(task_queue_manager_->Now());
+}
+
 bool TaskQueue::IsQueueEmpty() const {
   if (!work_queue_.empty())
     return false;
@@ -188,18 +242,14 @@ bool TaskQueue::ShouldAutoPumpQueueLocked(
   return true;
 }
 
-bool TaskQueue::UpdateWorkQueue(
-    base::TimeTicks* next_pending_delayed_task,
-    const base::PendingTask* previous_task) {
+bool TaskQueue::UpdateWorkQueue(base::TimeTicks now,
+                                const base::PendingTask* previous_task) {
   if (!work_queue_.empty())
     return true;
 
   {
     base::AutoLock lock(lock_);
-    if (!delayed_task_run_times_.empty()) {
-      *next_pending_delayed_task =
-          std::min(*next_pending_delayed_task, delayed_task_run_times_.top());
-    }
+    EnqueueReadyDelayedTasksLocked(now);
     if (!ShouldAutoPumpQueueLocked(previous_task))
       return false;
     work_queue_.Swap(&incoming_queue_);
@@ -231,11 +281,6 @@ void TaskQueue::TraceQueueSize(bool is_locked) const {
     lock_.Release();
 }
 
-void TaskQueue::EnqueueTask(const base::PendingTask& pending_task) {
-  base::AutoLock lock(lock_);
-  EnqueueTaskLocked(pending_task);
-}
-
 void TaskQueue::EnqueueTaskLocked(const base::PendingTask& pending_task) {
   lock_.AssertAcquired();
   if (!task_queue_manager_)
@@ -246,11 +291,6 @@ void TaskQueue::EnqueueTaskLocked(const base::PendingTask& pending_task) {
   incoming_queue_.push(pending_task);
 
   if (!pending_task.delayed_run_time.is_null()) {
-    // Update the time of the next pending delayed task.
-    while (!delayed_task_run_times_.empty() &&
-           delayed_task_run_times_.top() <= pending_task.delayed_run_time) {
-      delayed_task_run_times_.pop();
-    }
     // Clear the delayed run time because we've already applied the delay
     // before getting here.
     incoming_queue_.back().delayed_run_time = base::TimeTicks();
@@ -269,6 +309,8 @@ void TaskQueue::SetPumpPolicy(TaskQueueManager::PumpPolicy pump_policy) {
 
 void TaskQueue::PumpQueueLocked() {
   lock_.AssertAcquired();
+  if (task_queue_manager_)
+    EnqueueReadyDelayedTasksLocked(task_queue_manager_->Now());
   while (!incoming_queue_.empty()) {
     work_queue_.push(incoming_queue_.front());
     incoming_queue_.pop();
@@ -404,7 +446,7 @@ void TaskQueueManager::PumpQueue(size_t queue_index) {
 }
 
 bool TaskQueueManager::UpdateWorkQueues(
-    base::TimeTicks* next_pending_delayed_task,
+    base::TimeTicks now,
     const base::PendingTask* previous_task) {
   // TODO(skyostil): This is not efficient when the number of queues grows very
   // large due to the number of locks taken. Consider optimizing when we get
@@ -412,8 +454,7 @@ bool TaskQueueManager::UpdateWorkQueues(
   DCHECK(main_thread_checker_.CalledOnValidThread());
   bool has_work = false;
   for (auto& queue : queues_) {
-    has_work |= queue->UpdateWorkQueue(next_pending_delayed_task,
-                                       previous_task);
+    has_work |= queue->UpdateWorkQueue(now, previous_task);
     if (!queue->work_queue().empty()) {
       // Currently we should not be getting tasks with delayed run times in any
       // of the work queues.
@@ -446,22 +487,14 @@ void TaskQueueManager::DoWork(bool posted_from_main_thread) {
   }
   DCHECK(main_thread_checker_.CalledOnValidThread());
 
-  base::TimeTicks next_pending_delayed_task(
-      base::TimeTicks::FromInternalValue(kMaxTimeTicks));
-
-  // Pass nullptr to UpdateWorkQueues here to prevent waking up an
+  // Pass nullptr to UpdateWorkQueues here to prevent waking up a
   // pump-after-wakeup queue.
-  if (!UpdateWorkQueues(&next_pending_delayed_task, nullptr))
+  if (!UpdateWorkQueues(Now(), nullptr))
     return;
 
   base::PendingTask previous_task((tracked_objects::Location()),
                                   (base::Closure()));
   for (int i = 0; i < work_batch_size_; i++) {
-    // Interrupt the work batch if we should run the next delayed task.
-    if (i > 0 && next_pending_delayed_task.ToInternalValue() != kMaxTimeTicks &&
-        Now() >= next_pending_delayed_task)
-      return;
-
     size_t queue_index;
     if (!SelectWorkQueueToService(&queue_index))
       return;
@@ -470,7 +503,7 @@ void TaskQueueManager::DoWork(bool posted_from_main_thread) {
     MaybePostDoWorkOnMainRunner();
     ProcessTaskFromWorkQueue(queue_index, i > 0, &previous_task);
 
-    if (!UpdateWorkQueues(&next_pending_delayed_task, &previous_task))
+    if (!UpdateWorkQueues(Now(), &previous_task))
       return;
   }
 }