Home | History | Annotate | Download | only in sequence_manager 
      1 // Copyright 2014 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "base/task/sequence_manager/task_queue_selector.h"
      6 
      7 #include "base/logging.h"
      8 #include "base/metrics/histogram_macros.h"
      9 #include "base/task/sequence_manager/task_queue_impl.h"
     10 #include "base/task/sequence_manager/work_queue.h"
     11 #include "base/trace_event/trace_event_argument.h"
     12 
     13 namespace base {
     14 namespace sequence_manager {
     15 namespace internal {
     16 
     17 namespace {
     18 
     19 TaskQueueSelectorLogic QueuePriorityToSelectorLogic(
     20     TaskQueue::QueuePriority priority) {
     21   switch (priority) {
     22     case TaskQueue::kControlPriority:
     23       return TaskQueueSelectorLogic::kControlPriorityLogic;
     24     case TaskQueue::kHighestPriority:
     25       return TaskQueueSelectorLogic::kHighestPriorityLogic;
     26     case TaskQueue::kHighPriority:
     27       return TaskQueueSelectorLogic::kHighPriorityLogic;
     28     case TaskQueue::kNormalPriority:
     29       return TaskQueueSelectorLogic::kNormalPriorityLogic;
     30     case TaskQueue::kLowPriority:
     31       return TaskQueueSelectorLogic::kLowPriorityLogic;
     32     case TaskQueue::kBestEffortPriority:
     33       return TaskQueueSelectorLogic::kBestEffortPriorityLogic;
     34     default:
     35       NOTREACHED();
     36       return TaskQueueSelectorLogic::kCount;
     37   }
     38 }
     39 
     40 // Helper function used to report the number of times a selector logic is
     41 // trigerred. This will create a histogram for the enumerated data.
     42 void ReportTaskSelectionLogic(TaskQueueSelectorLogic selector_logic) {
     43   UMA_HISTOGRAM_ENUMERATION("TaskQueueSelector.TaskServicedPerSelectorLogic",
     44                             selector_logic, TaskQueueSelectorLogic::kCount);
     45 }
     46 
     47 }  // namespace
     48 
     49 TaskQueueSelector::TaskQueueSelector()
     50     : prioritizing_selector_(this, "enabled"),
     51       immediate_starvation_count_(0),
     52       high_priority_starvation_score_(0),
     53       normal_priority_starvation_score_(0),
     54       low_priority_starvation_score_(0),
     55       task_queue_selector_observer_(nullptr) {}
     56 
     57 TaskQueueSelector::~TaskQueueSelector() = default;
     58 
     59 void TaskQueueSelector::AddQueue(internal::TaskQueueImpl* queue) {
     60   DCHECK(main_thread_checker_.CalledOnValidThread());
     61   DCHECK(queue->IsQueueEnabled());
     62   prioritizing_selector_.AddQueue(queue, TaskQueue::kNormalPriority);
     63 }
     64 
     65 void TaskQueueSelector::RemoveQueue(internal::TaskQueueImpl* queue) {
     66   DCHECK(main_thread_checker_.CalledOnValidThread());
     67   if (queue->IsQueueEnabled()) {
     68     prioritizing_selector_.RemoveQueue(queue);
     69   }
     70 }
     71 
     72 void TaskQueueSelector::EnableQueue(internal::TaskQueueImpl* queue) {
     73   DCHECK(main_thread_checker_.CalledOnValidThread());
     74   DCHECK(queue->IsQueueEnabled());
     75   prioritizing_selector_.AddQueue(queue, queue->GetQueuePriority());
     76   if (task_queue_selector_observer_)
     77     task_queue_selector_observer_->OnTaskQueueEnabled(queue);
     78 }
     79 
     80 void TaskQueueSelector::DisableQueue(internal::TaskQueueImpl* queue) {
     81   DCHECK(main_thread_checker_.CalledOnValidThread());
     82   DCHECK(!queue->IsQueueEnabled());
     83   prioritizing_selector_.RemoveQueue(queue);
     84 }
     85 
     86 void TaskQueueSelector::SetQueuePriority(internal::TaskQueueImpl* queue,
     87                                          TaskQueue::QueuePriority priority) {
     88   DCHECK_LT(priority, TaskQueue::kQueuePriorityCount);
     89   DCHECK(main_thread_checker_.CalledOnValidThread());
     90   if (queue->IsQueueEnabled()) {
     91     prioritizing_selector_.ChangeSetIndex(queue, priority);
     92   } else {
     93     // Disabled queue is not in any set so we can't use ChangeSetIndex here
     94     // and have to assign priority for the queue itself.
     95     queue->delayed_work_queue()->AssignSetIndex(priority);
     96     queue->immediate_work_queue()->AssignSetIndex(priority);
     97   }
     98   DCHECK_EQ(priority, queue->GetQueuePriority());
     99 }
    100 
    101 TaskQueue::QueuePriority TaskQueueSelector::NextPriority(
    102     TaskQueue::QueuePriority priority) {
    103   DCHECK(priority < TaskQueue::kQueuePriorityCount);
    104   return static_cast<TaskQueue::QueuePriority>(static_cast<int>(priority) + 1);
    105 }
    106 
    107 TaskQueueSelector::PrioritizingSelector::PrioritizingSelector(
    108     TaskQueueSelector* task_queue_selector,
    109     const char* name)
    110     : task_queue_selector_(task_queue_selector),
    111       delayed_work_queue_sets_(TaskQueue::kQueuePriorityCount, name),
    112       immediate_work_queue_sets_(TaskQueue::kQueuePriorityCount, name) {}
    113 
    114 void TaskQueueSelector::PrioritizingSelector::AddQueue(
    115     internal::TaskQueueImpl* queue,
    116     TaskQueue::QueuePriority priority) {
    117 #if DCHECK_IS_ON()
    118   DCHECK(!CheckContainsQueueForTest(queue));
    119 #endif
    120   delayed_work_queue_sets_.AddQueue(queue->delayed_work_queue(), priority);
    121   immediate_work_queue_sets_.AddQueue(queue->immediate_work_queue(), priority);
    122 #if DCHECK_IS_ON()
    123   DCHECK(CheckContainsQueueForTest(queue));
    124 #endif
    125 }
    126 
    127 void TaskQueueSelector::PrioritizingSelector::ChangeSetIndex(
    128     internal::TaskQueueImpl* queue,
    129     TaskQueue::QueuePriority priority) {
    130 #if DCHECK_IS_ON()
    131   DCHECK(CheckContainsQueueForTest(queue));
    132 #endif
    133   delayed_work_queue_sets_.ChangeSetIndex(queue->delayed_work_queue(),
    134                                           priority);
    135   immediate_work_queue_sets_.ChangeSetIndex(queue->immediate_work_queue(),
    136                                             priority);
    137 #if DCHECK_IS_ON()
    138   DCHECK(CheckContainsQueueForTest(queue));
    139 #endif
    140 }
    141 
    142 void TaskQueueSelector::PrioritizingSelector::RemoveQueue(
    143     internal::TaskQueueImpl* queue) {
    144 #if DCHECK_IS_ON()
    145   DCHECK(CheckContainsQueueForTest(queue));
    146 #endif
    147   delayed_work_queue_sets_.RemoveQueue(queue->delayed_work_queue());
    148   immediate_work_queue_sets_.RemoveQueue(queue->immediate_work_queue());
    149 
    150 #if DCHECK_IS_ON()
    151   DCHECK(!CheckContainsQueueForTest(queue));
    152 #endif
    153 }
    154 
    155 bool TaskQueueSelector::PrioritizingSelector::
    156     ChooseOldestImmediateTaskWithPriority(TaskQueue::QueuePriority priority,
    157                                           WorkQueue** out_work_queue) const {
    158   return immediate_work_queue_sets_.GetOldestQueueInSet(priority,
    159                                                         out_work_queue);
    160 }
    161 
    162 bool TaskQueueSelector::PrioritizingSelector::
    163     ChooseOldestDelayedTaskWithPriority(TaskQueue::QueuePriority priority,
    164                                         WorkQueue** out_work_queue) const {
    165   return delayed_work_queue_sets_.GetOldestQueueInSet(priority, out_work_queue);
    166 }
    167 
    168 bool TaskQueueSelector::PrioritizingSelector::
    169     ChooseOldestImmediateOrDelayedTaskWithPriority(
    170         TaskQueue::QueuePriority priority,
    171         bool* out_chose_delayed_over_immediate,
    172         WorkQueue** out_work_queue) const {
    173   WorkQueue* immediate_queue;
    174   DCHECK_EQ(*out_chose_delayed_over_immediate, false);
    175   EnqueueOrder immediate_enqueue_order;
    176   if (immediate_work_queue_sets_.GetOldestQueueAndEnqueueOrderInSet(
    177           priority, &immediate_queue, &immediate_enqueue_order)) {
    178     WorkQueue* delayed_queue;
    179     EnqueueOrder delayed_enqueue_order;
    180     if (delayed_work_queue_sets_.GetOldestQueueAndEnqueueOrderInSet(
    181             priority, &delayed_queue, &delayed_enqueue_order)) {
    182       if (immediate_enqueue_order < delayed_enqueue_order) {
    183         *out_work_queue = immediate_queue;
    184       } else {
    185         *out_chose_delayed_over_immediate = true;
    186         *out_work_queue = delayed_queue;
    187       }
    188     } else {
    189       *out_work_queue = immediate_queue;
    190     }
    191     return true;
    192   }
    193   return delayed_work_queue_sets_.GetOldestQueueInSet(priority, out_work_queue);
    194 }
    195 
    196 bool TaskQueueSelector::PrioritizingSelector::ChooseOldestWithPriority(
    197     TaskQueue::QueuePriority priority,
    198     bool* out_chose_delayed_over_immediate,
    199     WorkQueue** out_work_queue) const {
    200   // Select an immediate work queue if we are starving immediate tasks.
    201   if (task_queue_selector_->immediate_starvation_count_ >=
    202       kMaxDelayedStarvationTasks) {
    203     if (ChooseOldestImmediateTaskWithPriority(priority, out_work_queue))
    204       return true;
    205     return ChooseOldestDelayedTaskWithPriority(priority, out_work_queue);
    206   }
    207   return ChooseOldestImmediateOrDelayedTaskWithPriority(
    208       priority, out_chose_delayed_over_immediate, out_work_queue);
    209 }
    210 
    211 bool TaskQueueSelector::PrioritizingSelector::SelectWorkQueueToService(
    212     TaskQueue::QueuePriority max_priority,
    213     WorkQueue** out_work_queue,
    214     bool* out_chose_delayed_over_immediate) {
    215   DCHECK(task_queue_selector_->main_thread_checker_.CalledOnValidThread());
    216   DCHECK_EQ(*out_chose_delayed_over_immediate, false);
    217 
    218   // Always service the control queue if it has any work.
    219   if (max_priority > TaskQueue::kControlPriority &&
    220       ChooseOldestWithPriority(TaskQueue::kControlPriority,
    221                                out_chose_delayed_over_immediate,
    222                                out_work_queue)) {
    223     ReportTaskSelectionLogic(TaskQueueSelectorLogic::kControlPriorityLogic);
    224     return true;
    225   }
    226 
    227   // Select from the low priority queue if we are starving it.
    228   if (max_priority > TaskQueue::kLowPriority &&
    229       task_queue_selector_->low_priority_starvation_score_ >=
    230           kMaxLowPriorityStarvationScore &&
    231       ChooseOldestWithPriority(TaskQueue::kLowPriority,
    232                                out_chose_delayed_over_immediate,
    233                                out_work_queue)) {
    234     ReportTaskSelectionLogic(
    235         TaskQueueSelectorLogic::kLowPriorityStarvationLogic);
    236     return true;
    237   }
    238 
    239   // Select from the normal priority queue if we are starving it.
    240   if (max_priority > TaskQueue::kNormalPriority &&
    241       task_queue_selector_->normal_priority_starvation_score_ >=
    242           kMaxNormalPriorityStarvationScore &&
    243       ChooseOldestWithPriority(TaskQueue::kNormalPriority,
    244                                out_chose_delayed_over_immediate,
    245                                out_work_queue)) {
    246     ReportTaskSelectionLogic(
    247         TaskQueueSelectorLogic::kNormalPriorityStarvationLogic);
    248     return true;
    249   }
    250 
    251   // Select from the high priority queue if we are starving it.
    252   if (max_priority > TaskQueue::kHighPriority &&
    253       task_queue_selector_->high_priority_starvation_score_ >=
    254           kMaxHighPriorityStarvationScore &&
    255       ChooseOldestWithPriority(TaskQueue::kHighPriority,
    256                                out_chose_delayed_over_immediate,
    257                                out_work_queue)) {
    258     ReportTaskSelectionLogic(
    259         TaskQueueSelectorLogic::kHighPriorityStarvationLogic);
    260     return true;
    261   }
    262 
    263   // Otherwise choose in priority order.
    264   for (TaskQueue::QueuePriority priority = TaskQueue::kHighestPriority;
    265        priority < max_priority; priority = NextPriority(priority)) {
    266     if (ChooseOldestWithPriority(priority, out_chose_delayed_over_immediate,
    267                                  out_work_queue)) {
    268       ReportTaskSelectionLogic(QueuePriorityToSelectorLogic(priority));
    269       return true;
    270     }
    271   }
    272   return false;
    273 }
    274 
    275 #if DCHECK_IS_ON() || !defined(NDEBUG)
    276 bool TaskQueueSelector::PrioritizingSelector::CheckContainsQueueForTest(
    277     const internal::TaskQueueImpl* queue) const {
    278   bool contains_delayed_work_queue =
    279       delayed_work_queue_sets_.ContainsWorkQueueForTest(
    280           queue->delayed_work_queue());
    281 
    282   bool contains_immediate_work_queue =
    283       immediate_work_queue_sets_.ContainsWorkQueueForTest(
    284           queue->immediate_work_queue());
    285 
    286   DCHECK_EQ(contains_delayed_work_queue, contains_immediate_work_queue);
    287   return contains_delayed_work_queue;
    288 }
    289 #endif
    290 
    291 bool TaskQueueSelector::SelectWorkQueueToService(WorkQueue** out_work_queue) {
    292   DCHECK(main_thread_checker_.CalledOnValidThread());
    293   bool chose_delayed_over_immediate = false;
    294   bool found_queue = prioritizing_selector_.SelectWorkQueueToService(
    295       TaskQueue::kQueuePriorityCount, out_work_queue,
    296       &chose_delayed_over_immediate);
    297   if (!found_queue)
    298     return false;
    299 
    300   // We could use |(*out_work_queue)->task_queue()->GetQueuePriority()| here but
    301   // for re-queued non-nestable tasks |task_queue()| returns null.
    302   DidSelectQueueWithPriority(static_cast<TaskQueue::QueuePriority>(
    303                                  (*out_work_queue)->work_queue_set_index()),
    304                              chose_delayed_over_immediate);
    305   return true;
    306 }
    307 
    308 void TaskQueueSelector::DidSelectQueueWithPriority(
    309     TaskQueue::QueuePriority priority,
    310     bool chose_delayed_over_immediate) {
    311   switch (priority) {
    312     case TaskQueue::kControlPriority:
    313       break;
    314     case TaskQueue::kHighestPriority:
    315       low_priority_starvation_score_ +=
    316           HasTasksWithPriority(TaskQueue::kLowPriority)
    317               ? kSmallScoreIncrementForLowPriorityStarvation
    318               : 0;
    319       normal_priority_starvation_score_ +=
    320           HasTasksWithPriority(TaskQueue::kNormalPriority)
    321               ? kSmallScoreIncrementForNormalPriorityStarvation
    322               : 0;
    323       high_priority_starvation_score_ +=
    324           HasTasksWithPriority(TaskQueue::kHighPriority)
    325               ? kSmallScoreIncrementForHighPriorityStarvation
    326               : 0;
    327       break;
    328     case TaskQueue::kHighPriority:
    329       low_priority_starvation_score_ +=
    330           HasTasksWithPriority(TaskQueue::kLowPriority)
    331               ? kLargeScoreIncrementForLowPriorityStarvation
    332               : 0;
    333       normal_priority_starvation_score_ +=
    334           HasTasksWithPriority(TaskQueue::kNormalPriority)
    335               ? kLargeScoreIncrementForNormalPriorityStarvation
    336               : 0;
    337       high_priority_starvation_score_ = 0;
    338       break;
    339     case TaskQueue::kNormalPriority:
    340       low_priority_starvation_score_ +=
    341           HasTasksWithPriority(TaskQueue::kLowPriority)
    342               ? kLargeScoreIncrementForLowPriorityStarvation
    343               : 0;
    344       normal_priority_starvation_score_ = 0;
    345       break;
    346     case TaskQueue::kLowPriority:
    347     case TaskQueue::kBestEffortPriority:
    348       low_priority_starvation_score_ = 0;
    349       high_priority_starvation_score_ = 0;
    350       normal_priority_starvation_score_ = 0;
    351       break;
    352     default:
    353       NOTREACHED();
    354   }
    355   if (chose_delayed_over_immediate) {
    356     immediate_starvation_count_++;
    357   } else {
    358     immediate_starvation_count_ = 0;
    359   }
    360 }
    361 
    362 void TaskQueueSelector::AsValueInto(trace_event::TracedValue* state) const {
    363   DCHECK(main_thread_checker_.CalledOnValidThread());
    364   state->SetInteger("high_priority_starvation_score",
    365                     high_priority_starvation_score_);
    366   state->SetInteger("normal_priority_starvation_score",
    367                     normal_priority_starvation_score_);
    368   state->SetInteger("low_priority_starvation_score",
    369                     low_priority_starvation_score_);
    370   state->SetInteger("immediate_starvation_count", immediate_starvation_count_);
    371 }
    372 
    373 void TaskQueueSelector::SetTaskQueueSelectorObserver(Observer* observer) {
    374   task_queue_selector_observer_ = observer;
    375 }
    376 
    377 bool TaskQueueSelector::AllEnabledWorkQueuesAreEmpty() const {
    378   DCHECK(main_thread_checker_.CalledOnValidThread());
    379   for (TaskQueue::QueuePriority priority = TaskQueue::kControlPriority;
    380        priority < TaskQueue::kQueuePriorityCount;
    381        priority = NextPriority(priority)) {
    382     if (!prioritizing_selector_.delayed_work_queue_sets()->IsSetEmpty(
    383             priority) ||
    384         !prioritizing_selector_.immediate_work_queue_sets()->IsSetEmpty(
    385             priority)) {
    386       return false;
    387     }
    388   }
    389   return true;
    390 }
    391 
    392 void TaskQueueSelector::SetImmediateStarvationCountForTest(
    393     size_t immediate_starvation_count) {
    394   immediate_starvation_count_ = immediate_starvation_count;
    395 }
    396 
    397 bool TaskQueueSelector::HasTasksWithPriority(
    398     TaskQueue::QueuePriority priority) {
    399   return !prioritizing_selector_.delayed_work_queue_sets()->IsSetEmpty(
    400              priority) ||
    401          !prioritizing_selector_.immediate_work_queue_sets()->IsSetEmpty(
    402              priority);
    403 }
    404 
    405 }  // namespace internal
    406 }  // namespace sequence_manager
    407 }  // namespace base
    408