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