diff options
Diffstat (limited to 'chromium/third_party/blink/renderer/platform/scheduler/base/task_queue_selector.cc')
-rw-r--r-- | chromium/third_party/blink/renderer/platform/scheduler/base/task_queue_selector.cc | 388 |
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 |