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
QueuePriorityToSelectorLogic(TaskQueue::QueuePriority priority)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.
ReportTaskSelectionLogic(TaskQueueSelectorLogic selector_logic)42 void ReportTaskSelectionLogic(TaskQueueSelectorLogic selector_logic) {
43 UMA_HISTOGRAM_ENUMERATION("TaskQueueSelector.TaskServicedPerSelectorLogic",
44 selector_logic, TaskQueueSelectorLogic::kCount);
45 }
46
47 } // namespace
48
TaskQueueSelector()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
AddQueue(internal::TaskQueueImpl * queue)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
RemoveQueue(internal::TaskQueueImpl * queue)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
EnableQueue(internal::TaskQueueImpl * queue)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
DisableQueue(internal::TaskQueueImpl * queue)80 void TaskQueueSelector::DisableQueue(internal::TaskQueueImpl* queue) {
81 DCHECK(main_thread_checker_.CalledOnValidThread());
82 DCHECK(!queue->IsQueueEnabled());
83 prioritizing_selector_.RemoveQueue(queue);
84 }
85
SetQueuePriority(internal::TaskQueueImpl * queue,TaskQueue::QueuePriority priority)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
NextPriority(TaskQueue::QueuePriority priority)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
PrioritizingSelector(TaskQueueSelector * task_queue_selector,const char * name)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
AddQueue(internal::TaskQueueImpl * queue,TaskQueue::QueuePriority priority)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
ChangeSetIndex(internal::TaskQueueImpl * queue,TaskQueue::QueuePriority priority)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
RemoveQueue(internal::TaskQueueImpl * queue)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::
ChooseOldestImmediateTaskWithPriority(TaskQueue::QueuePriority priority,WorkQueue ** out_work_queue) const156 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::
ChooseOldestDelayedTaskWithPriority(TaskQueue::QueuePriority priority,WorkQueue ** out_work_queue) const163 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::
ChooseOldestImmediateOrDelayedTaskWithPriority(TaskQueue::QueuePriority priority,bool * out_chose_delayed_over_immediate,WorkQueue ** out_work_queue) const169 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
ChooseOldestWithPriority(TaskQueue::QueuePriority priority,bool * out_chose_delayed_over_immediate,WorkQueue ** out_work_queue) const196 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
SelectWorkQueueToService(TaskQueue::QueuePriority max_priority,WorkQueue ** out_work_queue,bool * out_chose_delayed_over_immediate)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)
CheckContainsQueueForTest(const internal::TaskQueueImpl * queue) const276 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
SelectWorkQueueToService(WorkQueue ** out_work_queue)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
DidSelectQueueWithPriority(TaskQueue::QueuePriority priority,bool chose_delayed_over_immediate)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
AsValueInto(trace_event::TracedValue * state) const362 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
SetTaskQueueSelectorObserver(Observer * observer)373 void TaskQueueSelector::SetTaskQueueSelectorObserver(Observer* observer) {
374 task_queue_selector_observer_ = observer;
375 }
376
AllEnabledWorkQueuesAreEmpty() const377 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
SetImmediateStarvationCountForTest(size_t immediate_starvation_count)392 void TaskQueueSelector::SetImmediateStarvationCountForTest(
393 size_t immediate_starvation_count) {
394 immediate_starvation_count_ = immediate_starvation_count;
395 }
396
HasTasksWithPriority(TaskQueue::QueuePriority priority)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