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 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 18 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 25 WorkQueue::~WorkQueue() { 26 DCHECK(!work_queue_sets_) << task_queue_->GetName() << " : " 27 << work_queue_sets_->GetName() << " : " << name_; 28 } 29 30 const TaskQueueImpl::Task* WorkQueue::GetFrontTask() const { 31 if (tasks_.empty()) 32 return nullptr; 33 return &tasks_.front(); 34 } 35 36 const TaskQueueImpl::Task* WorkQueue::GetBackTask() const { 37 if (tasks_.empty()) 38 return nullptr; 39 return &tasks_.back(); 40 } 41 42 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 52 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 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 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 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 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 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 168 void WorkQueue::AssignToWorkQueueSets(WorkQueueSets* work_queue_sets) { 169 work_queue_sets_ = work_queue_sets; 170 } 171 172 void WorkQueue::AssignSetIndex(size_t work_queue_set_index) { 173 work_queue_set_index_ = work_queue_set_index; 174 } 175 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 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 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 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 215 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 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