components/scheduler/child/prioritizing_task_queue_selector.cc

   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 "components/scheduler/child/prioritizing_task_queue_selector.h"
   6
   7 #include "base/logging.h"
   8 #include "base/pending_task.h"
   9 #include "base/trace_event/trace_event_argument.h"
  10
  11 namespace scheduler {
  12
  13 PrioritizingTaskQueueSelector::PrioritizingTaskQueueSelector()
  14     : starvation_count_(0), task_queue_selector_observer_(nullptr) {
  15 }
  16
  17 PrioritizingTaskQueueSelector::~PrioritizingTaskQueueSelector() {
  18 }
  19
  20 void PrioritizingTaskQueueSelector::RegisterWorkQueues(
  21     const std::vector<const base::TaskQueue*>& work_queues) {
  22   DCHECK(main_thread_checker_.CalledOnValidThread());
  23   work_queues_ = work_queues;
  24   for (auto& queue_priority : queue_priorities_) {
  25     queue_priority.clear();
  26   }
  27
  28   // By default, all work queues are set to normal priority.
  29   for (size_t i = 0; i < work_queues.size(); i++) {
  30     queue_priorities_[NORMAL_PRIORITY].insert(i);
  31   }
  32 }
  33
  34 void PrioritizingTaskQueueSelector::SetQueuePriority(size_t queue_index,
  35                                                      QueuePriority priority) {
  36   DCHECK(main_thread_checker_.CalledOnValidThread());
  37   DCHECK_LT(queue_index, work_queues_.size());
  38   DCHECK_LT(priority, QUEUE_PRIORITY_COUNT);
  39   bool previously_enabled = DisableQueueInternal(queue_index);
  40   queue_priorities_[priority].insert(queue_index);
  41   if (task_queue_selector_observer_ && !previously_enabled)
  42     task_queue_selector_observer_->OnTaskQueueEnabled();
  43 }
  44
  45 void PrioritizingTaskQueueSelector::EnableQueue(size_t queue_index,
  46                                                 QueuePriority priority) {
  47   SetQueuePriority(queue_index, priority);
  48 }
  49
  50 void PrioritizingTaskQueueSelector::DisableQueue(size_t queue_index) {
  51   DisableQueueInternal(queue_index);
  52 }
  53
  54 bool PrioritizingTaskQueueSelector::DisableQueueInternal(size_t queue_index) {
  55   DCHECK(main_thread_checker_.CalledOnValidThread());
  56   DCHECK_LT(queue_index, work_queues_.size());
  57   bool previously_enabled = false;
  58   for (auto& queue_priority : queue_priorities_) {
  59     if (queue_priority.erase(queue_index))
  60       previously_enabled = true;
  61   }
  62   return previously_enabled;
  63 }
  64
  65 bool PrioritizingTaskQueueSelector::IsQueueEnabled(size_t queue_index) const {
  66   DCHECK(main_thread_checker_.CalledOnValidThread());
  67   DCHECK_LT(queue_index, work_queues_.size());
  68   for (const auto& queue_priority : queue_priorities_) {
  69     if (queue_priority.find(queue_index) != queue_priority.end())
  70       return true;
  71   }
  72   return false;
  73 }
  74
  75 bool PrioritizingTaskQueueSelector::IsOlder(const base::TaskQueue* queueA,
  76                                             const base::TaskQueue* queueB) {
  77   // Note: the comparison is correct due to the fact that the PendingTask
  78   // operator inverts its comparison operation in order to work well in a heap
  79   // based priority queue.
  80   return queueB->front() < queueA->front();
  81 }
  82
  83 PrioritizingTaskQueueSelector::QueuePriority
  84 PrioritizingTaskQueueSelector::NextPriority(QueuePriority priority) {
  85   DCHECK(priority < QUEUE_PRIORITY_COUNT);
  86   return static_cast<QueuePriority>(static_cast<int>(priority) + 1);
  87 }
  88
  89 bool PrioritizingTaskQueueSelector::ChooseOldestWithPriority(
  90     QueuePriority priority,
  91     size_t* out_queue_index) const {
  92   bool found_non_empty_queue = false;
  93   size_t chosen_queue = 0;
  94   for (int queue_index : queue_priorities_[priority]) {
  95     if (work_queues_[queue_index]->empty()) {
  96       continue;
  97     }
  98     if (!found_non_empty_queue ||
  99         IsOlder(work_queues_[queue_index], work_queues_[chosen_queue])) {
 100       found_non_empty_queue = true;
 101       chosen_queue = queue_index;
 102     }
 103   }
 104
 105   if (found_non_empty_queue) {
 106     *out_queue_index = chosen_queue;
 107   }
 108   return found_non_empty_queue;
 109 }
 110
 111 bool PrioritizingTaskQueueSelector::SelectWorkQueueToService(
 112     size_t* out_queue_index) {
 113   DCHECK(main_thread_checker_.CalledOnValidThread());
 114   DCHECK(work_queues_.size());
 115   // Always service the control queue if it has any work.
 116   if (ChooseOldestWithPriority(CONTROL_PRIORITY, out_queue_index)) {
 117     DidSelectQueueWithPriority(CONTROL_PRIORITY);
 118     return true;
 119   }
 120   // Select from the normal priority queue if we are starving it.
 121   if (starvation_count_ >= kMaxStarvationTasks &&
 122       ChooseOldestWithPriority(NORMAL_PRIORITY, out_queue_index)) {
 123     DidSelectQueueWithPriority(NORMAL_PRIORITY);
 124     return true;
 125   }
 126   // Otherwise choose in priority order.
 127   for (QueuePriority priority = HIGH_PRIORITY; priority < QUEUE_PRIORITY_COUNT;
 128        priority = NextPriority(priority)) {
 129     if (ChooseOldestWithPriority(priority, out_queue_index)) {
 130       DidSelectQueueWithPriority(priority);
 131       return true;
 132     }
 133   }
 134   return false;
 135 }
 136
 137 void PrioritizingTaskQueueSelector::DidSelectQueueWithPriority(
 138     QueuePriority priority) {
 139   switch (priority) {
 140     case CONTROL_PRIORITY:
 141       break;
 142     case HIGH_PRIORITY:
 143       starvation_count_++;
 144       break;
 145     case NORMAL_PRIORITY:
 146     case BEST_EFFORT_PRIORITY:
 147       starvation_count_ = 0;
 148       break;
 149     default:
 150       NOTREACHED();
 151   }
 152 }
 153
 154 // static
 155 const char* PrioritizingTaskQueueSelector::PriorityToString(
 156     QueuePriority priority) {
 157   switch (priority) {
 158     case CONTROL_PRIORITY:
 159       return "control";
 160     case HIGH_PRIORITY:
 161       return "high";
 162     case NORMAL_PRIORITY:
 163       return "normal";
 164     case BEST_EFFORT_PRIORITY:
 165       return "best_effort";
 166     default:
 167       NOTREACHED();
 168       return nullptr;
 169   }
 170 }
 171
 172 void PrioritizingTaskQueueSelector::AsValueInto(
 173     base::trace_event::TracedValue* state) const {
 174   DCHECK(main_thread_checker_.CalledOnValidThread());
 175   state->BeginDictionary("priorities");
 176   for (QueuePriority priority = FIRST_QUEUE_PRIORITY;
 177        priority < QUEUE_PRIORITY_COUNT; priority = NextPriority(priority)) {
 178     state->BeginArray(PriorityToString(priority));
 179     for (size_t queue_index : queue_priorities_[priority])
 180       state->AppendInteger(queue_index);
 181     state->EndArray();
 182   }
 183   state->EndDictionary();
 184   state->SetInteger("starvation_count", starvation_count_);
 185 }
 186
 187 void PrioritizingTaskQueueSelector::SetTaskQueueSelectorObserver(
 188     Observer* observer) {
 189   task_queue_selector_observer_ = observer;
 190 }
 191
 192 }  // namespace scheduler