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