1 files changed, 388 insertions, 0 deletions
diff --git a/chromium/third_party/blink/renderer/platform/scheduler/base/task_queue_selector.cc b/chromium/third_party/blink/renderer/platform/scheduler/base/task_queue_selector.cc
new file mode 100644
index 00000000000..46883b04c24
--- /dev/null
+++ b/chromium/third_party/blink/renderer/platform/scheduler/base/task_queue_selector.cc
@@ -0,0 +1,388 @@
+// Copyright 2014 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 "third_party/blink/renderer/platform/scheduler/base/task_queue_selector.h"
+
+#include "base/logging.h"
+#include "base/metrics/histogram_macros.h"
+#include "base/trace_event/trace_event_argument.h"
+#include "third_party/blink/renderer/platform/scheduler/base/task_queue_impl.h"
+#include "third_party/blink/renderer/platform/scheduler/base/work_queue.h"
+
+namespace blink {
+namespace scheduler {
+namespace internal {
+
+namespace {
+
+TaskQueueSelectorLogic QueuePriorityToSelectorLogic(
+    TaskQueue::QueuePriority priority) {
+  switch (priority) {
+    case TaskQueue::kControlPriority:
+      return TaskQueueSelectorLogic::kControlPriorityLogic;
+    case TaskQueue::kHighestPriority:
+      return TaskQueueSelectorLogic::kHighestPriorityLogic;
+    case TaskQueue::kHighPriority:
+      return TaskQueueSelectorLogic::kHighPriorityLogic;
+    case TaskQueue::kNormalPriority:
+      return TaskQueueSelectorLogic::kNormalPriorityLogic;
+    case TaskQueue::kLowPriority:
+      return TaskQueueSelectorLogic::kLowPriorityLogic;
+    case TaskQueue::kBestEffortPriority:
+      return TaskQueueSelectorLogic::kBestEffortPriorityLogic;
+    default:
+      NOTREACHED();
+      return TaskQueueSelectorLogic::kCount;
+  }
+}
+
+// Helper function used to report the number of times a selector logic is
+// trigerred. This will create a histogram for the enumerated data.
+void ReportTaskSelectionLogic(TaskQueueSelectorLogic selector_logic) {
+  UMA_HISTOGRAM_ENUMERATION("TaskQueueSelector.TaskServicedPerSelectorLogic",
+                            selector_logic, TaskQueueSelectorLogic::kCount);
+}
+
+}  // namespace
+
+TaskQueueSelector::TaskQueueSelector()
+    : prioritizing_selector_(this, "enabled"),
+      immediate_starvation_count_(0),
+      high_priority_starvation_score_(0),
+      normal_priority_starvation_score_(0),
+      low_priority_starvation_score_(0),
+      task_queue_selector_observer_(nullptr) {}
+
+TaskQueueSelector::~TaskQueueSelector() = default;
+
+void TaskQueueSelector::AddQueue(internal::TaskQueueImpl* queue) {
+  DCHECK(main_thread_checker_.CalledOnValidThread());
+  DCHECK(queue->IsQueueEnabled());
+  prioritizing_selector_.AddQueue(queue, TaskQueue::kNormalPriority);
+}
+
+void TaskQueueSelector::RemoveQueue(internal::TaskQueueImpl* queue) {
+  DCHECK(main_thread_checker_.CalledOnValidThread());
+  if (queue->IsQueueEnabled()) {
+    prioritizing_selector_.RemoveQueue(queue);
+  }
+}
+
+void TaskQueueSelector::EnableQueue(internal::TaskQueueImpl* queue) {
+  DCHECK(main_thread_checker_.CalledOnValidThread());
+  DCHECK(queue->IsQueueEnabled());
+  prioritizing_selector_.AddQueue(queue, queue->GetQueuePriority());
+  if (task_queue_selector_observer_)
+    task_queue_selector_observer_->OnTaskQueueEnabled(queue);
+}
+
+void TaskQueueSelector::DisableQueue(internal::TaskQueueImpl* queue) {
+  DCHECK(main_thread_checker_.CalledOnValidThread());
+  DCHECK(!queue->IsQueueEnabled());
+  prioritizing_selector_.RemoveQueue(queue);
+}
+
+void TaskQueueSelector::SetQueuePriority(internal::TaskQueueImpl* queue,
+                                         TaskQueue::QueuePriority priority) {
+  DCHECK_LT(priority, TaskQueue::kQueuePriorityCount);
+  DCHECK(main_thread_checker_.CalledOnValidThread());
+  if (queue->IsQueueEnabled()) {
+    prioritizing_selector_.ChangeSetIndex(queue, priority);
+  } else {
+    // Disabled queue is not in any set so we can't use ChangeSetIndex here
+    // and have to assign priority for the queue itself.
+    queue->delayed_work_queue()->AssignSetIndex(priority);
+    queue->immediate_work_queue()->AssignSetIndex(priority);
+  }
+  DCHECK_EQ(priority, queue->GetQueuePriority());
+}
+
+TaskQueue::QueuePriority TaskQueueSelector::NextPriority(
+    TaskQueue::QueuePriority priority) {
+  DCHECK(priority < TaskQueue::kQueuePriorityCount);
+  return static_cast<TaskQueue::QueuePriority>(static_cast<int>(priority) + 1);
+}
+
+TaskQueueSelector::PrioritizingSelector::PrioritizingSelector(
+    TaskQueueSelector* task_queue_selector,
+    const char* name)
+    : task_queue_selector_(task_queue_selector),
+      delayed_work_queue_sets_(TaskQueue::kQueuePriorityCount, name),
+      immediate_work_queue_sets_(TaskQueue::kQueuePriorityCount, name) {}
+
+void TaskQueueSelector::PrioritizingSelector::AddQueue(
+    internal::TaskQueueImpl* queue,
+    TaskQueue::QueuePriority priority) {
+#if DCHECK_IS_ON()
+  DCHECK(!CheckContainsQueueForTest(queue));
+#endif
+  delayed_work_queue_sets_.AddQueue(queue->delayed_work_queue(), priority);
+  immediate_work_queue_sets_.AddQueue(queue->immediate_work_queue(), priority);
+#if DCHECK_IS_ON()
+  DCHECK(CheckContainsQueueForTest(queue));
+#endif
+}
+
+void TaskQueueSelector::PrioritizingSelector::ChangeSetIndex(
+    internal::TaskQueueImpl* queue,
+    TaskQueue::QueuePriority priority) {
+#if DCHECK_IS_ON()
+  DCHECK(CheckContainsQueueForTest(queue));
+#endif
+  delayed_work_queue_sets_.ChangeSetIndex(queue->delayed_work_queue(),
+                                          priority);
+  immediate_work_queue_sets_.ChangeSetIndex(queue->immediate_work_queue(),
+                                            priority);
+#if DCHECK_IS_ON()
+  DCHECK(CheckContainsQueueForTest(queue));
+#endif
+}
+
+void TaskQueueSelector::PrioritizingSelector::RemoveQueue(
+    internal::TaskQueueImpl* queue) {
+#if DCHECK_IS_ON()
+  DCHECK(CheckContainsQueueForTest(queue));
+#endif
+  delayed_work_queue_sets_.RemoveQueue(queue->delayed_work_queue());
+  immediate_work_queue_sets_.RemoveQueue(queue->immediate_work_queue());
+
+#if DCHECK_IS_ON()
+  DCHECK(!CheckContainsQueueForTest(queue));
+#endif
+}
+
+bool TaskQueueSelector::PrioritizingSelector::
+    ChooseOldestImmediateTaskWithPriority(TaskQueue::QueuePriority priority,
+                                          WorkQueue** out_work_queue) const {
+  return immediate_work_queue_sets_.GetOldestQueueInSet(priority,
+                                                        out_work_queue);
+}
+
+bool TaskQueueSelector::PrioritizingSelector::
+    ChooseOldestDelayedTaskWithPriority(TaskQueue::QueuePriority priority,
+                                        WorkQueue** out_work_queue) const {
+  return delayed_work_queue_sets_.GetOldestQueueInSet(priority, out_work_queue);
+}
+
+bool TaskQueueSelector::PrioritizingSelector::
+    ChooseOldestImmediateOrDelayedTaskWithPriority(
+        TaskQueue::QueuePriority priority,
+        bool* out_chose_delayed_over_immediate,
+        WorkQueue** out_work_queue) const {
+  WorkQueue* immediate_queue;
+  DCHECK_EQ(*out_chose_delayed_over_immediate, false);
+  EnqueueOrder immediate_enqueue_order;
+  if (immediate_work_queue_sets_.GetOldestQueueAndEnqueueOrderInSet(
+          priority, &immediate_queue, &immediate_enqueue_order)) {
+    WorkQueue* delayed_queue;
+    EnqueueOrder delayed_enqueue_order;
+    if (delayed_work_queue_sets_.GetOldestQueueAndEnqueueOrderInSet(
+            priority, &delayed_queue, &delayed_enqueue_order)) {
+      if (immediate_enqueue_order < delayed_enqueue_order) {
+        *out_work_queue = immediate_queue;
+      } else {
+        *out_chose_delayed_over_immediate = true;
+        *out_work_queue = delayed_queue;
+      }
+    } else {
+      *out_work_queue = immediate_queue;
+    }
+    return true;
+  }
+  return delayed_work_queue_sets_.GetOldestQueueInSet(priority, out_work_queue);
+}
+
+bool TaskQueueSelector::PrioritizingSelector::ChooseOldestWithPriority(
+    TaskQueue::QueuePriority priority,
+    bool* out_chose_delayed_over_immediate,
+    WorkQueue** out_work_queue) const {
+  // Select an immediate work queue if we are starving immediate tasks.
+  if (task_queue_selector_->immediate_starvation_count_ >=
+      kMaxDelayedStarvationTasks) {
+    if (ChooseOldestImmediateTaskWithPriority(priority, out_work_queue))
+      return true;
+    return ChooseOldestDelayedTaskWithPriority(priority, out_work_queue);
+  }
+  return ChooseOldestImmediateOrDelayedTaskWithPriority(
+      priority, out_chose_delayed_over_immediate, out_work_queue);
+}
+
+bool TaskQueueSelector::PrioritizingSelector::SelectWorkQueueToService(
+    TaskQueue::QueuePriority max_priority,
+    WorkQueue** out_work_queue,
+    bool* out_chose_delayed_over_immediate) {
+  DCHECK(task_queue_selector_->main_thread_checker_.CalledOnValidThread());
+  DCHECK_EQ(*out_chose_delayed_over_immediate, false);
+
+  // Always service the control queue if it has any work.
+  if (max_priority > TaskQueue::kControlPriority &&
+      ChooseOldestWithPriority(TaskQueue::kControlPriority,
+                               out_chose_delayed_over_immediate,
+                               out_work_queue)) {
+    ReportTaskSelectionLogic(TaskQueueSelectorLogic::kControlPriorityLogic);
+    return true;
+  }
+
+  // Select from the low priority queue if we are starving it.
+  if (max_priority > TaskQueue::kLowPriority &&
+      task_queue_selector_->low_priority_starvation_score_ >=
+          kMaxLowPriorityStarvationScore &&
+      ChooseOldestWithPriority(TaskQueue::kLowPriority,
+                               out_chose_delayed_over_immediate,
+                               out_work_queue)) {
+    ReportTaskSelectionLogic(
+        TaskQueueSelectorLogic::kLowPriorityStarvationLogic);
+    return true;
+  }
+
+  // Select from the normal priority queue if we are starving it.
+  if (max_priority > TaskQueue::kNormalPriority &&
+      task_queue_selector_->normal_priority_starvation_score_ >=
+          kMaxNormalPriorityStarvationScore &&
+      ChooseOldestWithPriority(TaskQueue::kNormalPriority,
+                               out_chose_delayed_over_immediate,
+                               out_work_queue)) {
+    ReportTaskSelectionLogic(
+        TaskQueueSelectorLogic::kNormalPriorityStarvationLogic);
+    return true;
+  }
+
+  // Select from the high priority queue if we are starving it.
+  if (max_priority > TaskQueue::kHighPriority &&
+      task_queue_selector_->high_priority_starvation_score_ >=
+          kMaxHighPriorityStarvationScore &&
+      ChooseOldestWithPriority(TaskQueue::kHighPriority,
+                               out_chose_delayed_over_immediate,
+                               out_work_queue)) {
+    ReportTaskSelectionLogic(
+        TaskQueueSelectorLogic::kHighPriorityStarvationLogic);
+    return true;
+  }
+
+  // Otherwise choose in priority order.
+  for (TaskQueue::QueuePriority priority = TaskQueue::kHighestPriority;
+       priority < max_priority; priority = NextPriority(priority)) {
+    if (ChooseOldestWithPriority(priority, out_chose_delayed_over_immediate,
+                                 out_work_queue)) {
+      ReportTaskSelectionLogic(QueuePriorityToSelectorLogic(priority));
+      return true;
+    }
+  }
+  return false;
+}
+
+#if DCHECK_IS_ON() || !defined(NDEBUG)
+bool TaskQueueSelector::PrioritizingSelector::CheckContainsQueueForTest(
+    const internal::TaskQueueImpl* queue) const {
+  bool contains_delayed_work_queue =
+      delayed_work_queue_sets_.ContainsWorkQueueForTest(
+          queue->delayed_work_queue());
+
+  bool contains_immediate_work_queue =
+      immediate_work_queue_sets_.ContainsWorkQueueForTest(
+          queue->immediate_work_queue());
+
+  DCHECK_EQ(contains_delayed_work_queue, contains_immediate_work_queue);
+  return contains_delayed_work_queue;
+}
+#endif
+
+bool TaskQueueSelector::SelectWorkQueueToService(WorkQueue** out_work_queue) {
+  DCHECK(main_thread_checker_.CalledOnValidThread());
+  bool chose_delayed_over_immediate = false;
+  bool found_queue = prioritizing_selector_.SelectWorkQueueToService(
+      TaskQueue::kQueuePriorityCount, out_work_queue,
+      &chose_delayed_over_immediate);
+  if (!found_queue)
+    return false;
+
+  // We could use |(*out_work_queue)->task_queue()->GetQueuePriority()| here but
+  // for re-queued non-nestable tasks |task_queue()| returns null.
+  DidSelectQueueWithPriority(static_cast<TaskQueue::QueuePriority>(
+                                 (*out_work_queue)->work_queue_set_index()),
+                             chose_delayed_over_immediate);
+  return true;
+}
+
+void TaskQueueSelector::DidSelectQueueWithPriority(
+    TaskQueue::QueuePriority priority,
+    bool chose_delayed_over_immediate) {
+  switch (priority) {
+    case TaskQueue::kControlPriority:
+      break;
+    case TaskQueue::kHighestPriority:
+      low_priority_starvation_score_ +=
+          kSmallScoreIncrementForLowPriorityStarvation;
+      normal_priority_starvation_score_ +=
+          kSmallScoreIncrementForNormalPriorityStarvation;
+      high_priority_starvation_score_ +=
+          kSmallScoreIncrementForHighPriorityStarvation;
+      break;
+    case TaskQueue::kHighPriority:
+      low_priority_starvation_score_ +=
+          kLargeScoreIncrementForLowPriorityStarvation;
+      normal_priority_starvation_score_ +=
+          kLargeScoreIncrementForNormalPriorityStarvation;
+      high_priority_starvation_score_ = 0;
+      break;
+    case TaskQueue::kNormalPriority:
+      low_priority_starvation_score_ +=
+          kLargeScoreIncrementForLowPriorityStarvation;
+      normal_priority_starvation_score_ = 0;
+      break;
+    case TaskQueue::kLowPriority:
+    case TaskQueue::kBestEffortPriority:
+      low_priority_starvation_score_ = 0;
+      high_priority_starvation_score_ = 0;
+      normal_priority_starvation_score_ = 0;
+      break;
+    default:
+      NOTREACHED();
+  }
+  if (chose_delayed_over_immediate) {
+    immediate_starvation_count_++;
+  } else {
+    immediate_starvation_count_ = 0;
+  }
+}
+
+void TaskQueueSelector::AsValueInto(
+    base::trace_event::TracedValue* state) const {
+  DCHECK(main_thread_checker_.CalledOnValidThread());
+  state->SetInteger("high_priority_starvation_score",
+                    high_priority_starvation_score_);
+  state->SetInteger("normal_priority_starvation_score",
+                    normal_priority_starvation_score_);
+  state->SetInteger("low_priority_starvation_score",
+                    low_priority_starvation_score_);
+  state->SetInteger("immediate_starvation_count", immediate_starvation_count_);
+}
+
+void TaskQueueSelector::SetTaskQueueSelectorObserver(Observer* observer) {
+  task_queue_selector_observer_ = observer;
+}
+
+bool TaskQueueSelector::AllEnabledWorkQueuesAreEmpty() const {
+  DCHECK(main_thread_checker_.CalledOnValidThread());
+  for (TaskQueue::QueuePriority priority = TaskQueue::kControlPriority;
+       priority < TaskQueue::kQueuePriorityCount;
+       priority = NextPriority(priority)) {
+    if (!prioritizing_selector_.delayed_work_queue_sets()->IsSetEmpty(
+            priority) ||
+        !prioritizing_selector_.immediate_work_queue_sets()->IsSetEmpty(
+            priority)) {
+      return false;
+    }
+  }
+  return true;
+}
+
+void TaskQueueSelector::SetImmediateStarvationCountForTest(
+    size_t immediate_starvation_count) {
+  immediate_starvation_count_ = immediate_starvation_count;
+}
+
+}  // namespace internal
+}  // namespace scheduler
+}  // namespace blink