| // 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 "base/task/sequence_manager/task_queue_selector.h" |
| |
| #include <utility> |
| |
| #include "base/logging.h" |
| #include "base/metrics/histogram_macros.h" |
| #include "base/task/sequence_manager/associated_thread_id.h" |
| #include "base/task/sequence_manager/task_queue_impl.h" |
| #include "base/task/sequence_manager/work_queue.h" |
| #include "base/threading/thread_checker.h" |
| #include "base/trace_event/trace_event_argument.h" |
| |
| namespace base { |
| namespace sequence_manager { |
| 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( |
| scoped_refptr<AssociatedThreadId> associated_thread) |
| : associated_thread_(std::move(associated_thread)), |
| 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_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker); |
| DCHECK(queue->IsQueueEnabled()); |
| prioritizing_selector_.AddQueue(queue, TaskQueue::kNormalPriority); |
| } |
| |
| void TaskQueueSelector::RemoveQueue(internal::TaskQueueImpl* queue) { |
| DCHECK_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker); |
| if (queue->IsQueueEnabled()) { |
| prioritizing_selector_.RemoveQueue(queue); |
| } |
| } |
| |
| void TaskQueueSelector::EnableQueue(internal::TaskQueueImpl* queue) { |
| DCHECK_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker); |
| 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_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker); |
| DCHECK(!queue->IsQueueEnabled()); |
| prioritizing_selector_.RemoveQueue(queue); |
| } |
| |
| void TaskQueueSelector::SetQueuePriority(internal::TaskQueueImpl* queue, |
| TaskQueue::QueuePriority priority) { |
| DCHECK_LT(priority, TaskQueue::kQueuePriorityCount); |
| DCHECK_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker); |
| 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_CALLED_ON_VALID_THREAD( |
| task_queue_selector_->associated_thread_->thread_checker); |
| 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_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker); |
| 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_ += |
| HasTasksWithPriority(TaskQueue::kLowPriority) |
| ? kSmallScoreIncrementForLowPriorityStarvation |
| : 0; |
| normal_priority_starvation_score_ += |
| HasTasksWithPriority(TaskQueue::kNormalPriority) |
| ? kSmallScoreIncrementForNormalPriorityStarvation |
| : 0; |
| high_priority_starvation_score_ += |
| HasTasksWithPriority(TaskQueue::kHighPriority) |
| ? kSmallScoreIncrementForHighPriorityStarvation |
| : 0; |
| break; |
| case TaskQueue::kHighPriority: |
| low_priority_starvation_score_ += |
| HasTasksWithPriority(TaskQueue::kLowPriority) |
| ? kLargeScoreIncrementForLowPriorityStarvation |
| : 0; |
| normal_priority_starvation_score_ += |
| HasTasksWithPriority(TaskQueue::kNormalPriority) |
| ? kLargeScoreIncrementForNormalPriorityStarvation |
| : 0; |
| high_priority_starvation_score_ = 0; |
| break; |
| case TaskQueue::kNormalPriority: |
| low_priority_starvation_score_ += |
| HasTasksWithPriority(TaskQueue::kLowPriority) |
| ? kLargeScoreIncrementForLowPriorityStarvation |
| : 0; |
| 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(trace_event::TracedValue* state) const { |
| DCHECK_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker); |
| 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_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker); |
| 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; |
| } |
| |
| bool TaskQueueSelector::HasTasksWithPriority( |
| TaskQueue::QueuePriority priority) { |
| return !prioritizing_selector_.delayed_work_queue_sets()->IsSetEmpty( |
| priority) || |
| !prioritizing_selector_.immediate_work_queue_sets()->IsSetEmpty( |
| priority); |
| } |
| |
| } // namespace internal |
| } // namespace sequence_manager |
| } // namespace base |
