1 // Copyright 2015 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/work_queue.h"
6
7 #include "base/task/sequence_manager/work_queue_sets.h"
8
9 namespace base {
10 namespace sequence_manager {
11 namespace internal {
12
WorkQueue(TaskQueueImpl * task_queue,const char * name,QueueType queue_type)13 WorkQueue::WorkQueue(TaskQueueImpl* task_queue,
14 const char* name,
15 QueueType queue_type)
16 : task_queue_(task_queue), name_(name), queue_type_(queue_type) {}
17
AsValueInto(TimeTicks now,trace_event::TracedValue * state) const18 void WorkQueue::AsValueInto(TimeTicks now,
19 trace_event::TracedValue* state) const {
20 for (const TaskQueueImpl::Task& task : tasks_) {
21 TaskQueueImpl::TaskAsValueInto(task, now, state);
22 }
23 }
24
~WorkQueue()25 WorkQueue::~WorkQueue() {
26 DCHECK(!work_queue_sets_) << task_queue_->GetName() << " : "
27 << work_queue_sets_->GetName() << " : " << name_;
28 }
29
GetFrontTask() const30 const TaskQueueImpl::Task* WorkQueue::GetFrontTask() const {
31 if (tasks_.empty())
32 return nullptr;
33 return &tasks_.front();
34 }
35
GetBackTask() const36 const TaskQueueImpl::Task* WorkQueue::GetBackTask() const {
37 if (tasks_.empty())
38 return nullptr;
39 return &tasks_.back();
40 }
41
BlockedByFence() const42 bool WorkQueue::BlockedByFence() const {
43 if (!fence_)
44 return false;
45
46 // If the queue is empty then any future tasks will have a higher enqueue
47 // order and will be blocked. The queue is also blocked if the head is past
48 // the fence.
49 return tasks_.empty() || tasks_.front().enqueue_order() >= fence_;
50 }
51
GetFrontTaskEnqueueOrder(EnqueueOrder * enqueue_order) const52 bool WorkQueue::GetFrontTaskEnqueueOrder(EnqueueOrder* enqueue_order) const {
53 if (tasks_.empty() || BlockedByFence())
54 return false;
55 // Quick sanity check.
56 DCHECK_LE(tasks_.front().enqueue_order(), tasks_.back().enqueue_order())
57 << task_queue_->GetName() << " : " << work_queue_sets_->GetName() << " : "
58 << name_;
59 *enqueue_order = tasks_.front().enqueue_order();
60 return true;
61 }
62
Push(TaskQueueImpl::Task task)63 void WorkQueue::Push(TaskQueueImpl::Task task) {
64 bool was_empty = tasks_.empty();
65 #ifndef NDEBUG
66 DCHECK(task.enqueue_order_set());
67 #endif
68
69 // Make sure the |enqueue_order()| is monotonically increasing.
70 DCHECK(was_empty || tasks_.rbegin()->enqueue_order() < task.enqueue_order());
71
72 // Amoritized O(1).
73 tasks_.push_back(std::move(task));
74
75 if (!was_empty)
76 return;
77
78 // If we hit the fence, pretend to WorkQueueSets that we're empty.
79 if (work_queue_sets_ && !BlockedByFence())
80 work_queue_sets_->OnTaskPushedToEmptyQueue(this);
81 }
82
PushNonNestableTaskToFront(TaskQueueImpl::Task task)83 void WorkQueue::PushNonNestableTaskToFront(TaskQueueImpl::Task task) {
84 DCHECK(task.nestable == Nestable::kNonNestable);
85
86 bool was_empty = tasks_.empty();
87 bool was_blocked = BlockedByFence();
88 #ifndef NDEBUG
89 DCHECK(task.enqueue_order_set());
90 #endif
91
92 if (!was_empty) {
93 // Make sure the |enqueue_order()| is monotonically increasing.
94 DCHECK_LE(task.enqueue_order(), tasks_.front().enqueue_order())
95 << task_queue_->GetName() << " : " << work_queue_sets_->GetName()
96 << " : " << name_;
97 }
98
99 // Amoritized O(1).
100 tasks_.push_front(std::move(task));
101
102 if (!work_queue_sets_)
103 return;
104
105 // Pretend to WorkQueueSets that nothing has changed if we're blocked.
106 if (BlockedByFence())
107 return;
108
109 // Pushing task to front may unblock the fence.
110 if (was_empty || was_blocked) {
111 work_queue_sets_->OnTaskPushedToEmptyQueue(this);
112 } else {
113 work_queue_sets_->OnFrontTaskChanged(this);
114 }
115 }
116
ReloadEmptyImmediateQueue()117 void WorkQueue::ReloadEmptyImmediateQueue() {
118 DCHECK(tasks_.empty());
119
120 task_queue_->ReloadEmptyImmediateQueue(&tasks_);
121 if (tasks_.empty())
122 return;
123
124 // If we hit the fence, pretend to WorkQueueSets that we're empty.
125 if (work_queue_sets_ && !BlockedByFence())
126 work_queue_sets_->OnTaskPushedToEmptyQueue(this);
127 }
128
TakeTaskFromWorkQueue()129 TaskQueueImpl::Task WorkQueue::TakeTaskFromWorkQueue() {
130 DCHECK(work_queue_sets_);
131 DCHECK(!tasks_.empty());
132
133 TaskQueueImpl::Task pending_task = std::move(tasks_.front());
134 tasks_.pop_front();
135 // NB immediate tasks have a different pipeline to delayed ones.
136 if (queue_type_ == QueueType::kImmediate && tasks_.empty()) {
137 // Short-circuit the queue reload so that OnPopQueue does the right thing.
138 task_queue_->ReloadEmptyImmediateQueue(&tasks_);
139 }
140
141 // OnPopQueue calls GetFrontTaskEnqueueOrder which checks BlockedByFence() so
142 // we don't need to here.
143 work_queue_sets_->OnPopQueue(this);
144 task_queue_->TraceQueueSize();
145 return pending_task;
146 }
147
RemoveAllCanceledTasksFromFront()148 bool WorkQueue::RemoveAllCanceledTasksFromFront() {
149 DCHECK(work_queue_sets_);
150 bool task_removed = false;
151 while (!tasks_.empty() &&
152 (!tasks_.front().task || tasks_.front().task.IsCancelled())) {
153 tasks_.pop_front();
154 task_removed = true;
155 }
156 if (task_removed) {
157 // NB immediate tasks have a different pipeline to delayed ones.
158 if (queue_type_ == QueueType::kImmediate && tasks_.empty()) {
159 // Short-circuit the queue reload so that OnPopQueue does the right thing.
160 task_queue_->ReloadEmptyImmediateQueue(&tasks_);
161 }
162 work_queue_sets_->OnPopQueue(this);
163 task_queue_->TraceQueueSize();
164 }
165 return task_removed;
166 }
167
AssignToWorkQueueSets(WorkQueueSets * work_queue_sets)168 void WorkQueue::AssignToWorkQueueSets(WorkQueueSets* work_queue_sets) {
169 work_queue_sets_ = work_queue_sets;
170 }
171
AssignSetIndex(size_t work_queue_set_index)172 void WorkQueue::AssignSetIndex(size_t work_queue_set_index) {
173 work_queue_set_index_ = work_queue_set_index;
174 }
175
InsertFenceImpl(EnqueueOrder fence)176 bool WorkQueue::InsertFenceImpl(EnqueueOrder fence) {
177 DCHECK_NE(fence, 0u);
178 DCHECK(fence >= fence_ || fence == EnqueueOrder::blocking_fence());
179 bool was_blocked_by_fence = BlockedByFence();
180 fence_ = fence;
181 return was_blocked_by_fence;
182 }
183
InsertFenceSilently(EnqueueOrder fence)184 void WorkQueue::InsertFenceSilently(EnqueueOrder fence) {
185 // Ensure that there is no fence present or a new one blocks queue completely.
186 DCHECK(!fence_ || fence_ == EnqueueOrder::blocking_fence());
187 InsertFenceImpl(fence);
188 }
189
InsertFence(EnqueueOrder fence)190 bool WorkQueue::InsertFence(EnqueueOrder fence) {
191 bool was_blocked_by_fence = InsertFenceImpl(fence);
192
193 // Moving the fence forward may unblock some tasks.
194 if (work_queue_sets_ && !tasks_.empty() && was_blocked_by_fence &&
195 !BlockedByFence()) {
196 work_queue_sets_->OnTaskPushedToEmptyQueue(this);
197 return true;
198 }
199 // Fence insertion may have blocked all tasks in this work queue.
200 if (BlockedByFence())
201 work_queue_sets_->OnQueueBlocked(this);
202 return false;
203 }
204
RemoveFence()205 bool WorkQueue::RemoveFence() {
206 bool was_blocked_by_fence = BlockedByFence();
207 fence_ = EnqueueOrder::none();
208 if (work_queue_sets_ && !tasks_.empty() && was_blocked_by_fence) {
209 work_queue_sets_->OnTaskPushedToEmptyQueue(this);
210 return true;
211 }
212 return false;
213 }
214
ShouldRunBefore(const WorkQueue * other_queue) const215 bool WorkQueue::ShouldRunBefore(const WorkQueue* other_queue) const {
216 DCHECK(!tasks_.empty());
217 DCHECK(!other_queue->tasks_.empty());
218 EnqueueOrder enqueue_order;
219 EnqueueOrder other_enqueue_order;
220 bool have_task = GetFrontTaskEnqueueOrder(&enqueue_order);
221 bool have_other_task =
222 other_queue->GetFrontTaskEnqueueOrder(&other_enqueue_order);
223 DCHECK(have_task);
224 DCHECK(have_other_task);
225 return enqueue_order < other_enqueue_order;
226 }
227
PopTaskForTesting()228 void WorkQueue::PopTaskForTesting() {
229 if (tasks_.empty())
230 return;
231 tasks_.pop_front();
232 }
233
234 } // namespace internal
235 } // namespace sequence_manager
236 } // namespace base
237