OLD | NEW |
1 // Copyright 2015 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "platform/scheduler/base/work_queue.h" | 5 #include "platform/scheduler/base/work_queue.h" |
6 | 6 |
7 #include "platform/scheduler/base/work_queue_sets.h" | 7 #include "platform/scheduler/base/work_queue_sets.h" |
8 | 8 |
9 namespace blink { | 9 namespace blink { |
10 namespace scheduler { | 10 namespace scheduler { |
11 namespace internal { | 11 namespace internal { |
12 | 12 |
13 WorkQueue::WorkQueue(TaskQueueImpl* task_queue, | 13 WorkQueue::WorkQueue(TaskQueueImpl* task_queue, const char* name) |
14 const char* name, | 14 : work_queue_sets_(nullptr), |
15 TaskQueueImpl::Task::ComparatorFn comparator) | |
16 : work_queue_(comparator), | |
17 work_queue_sets_(nullptr), | |
18 task_queue_(task_queue), | 15 task_queue_(task_queue), |
19 work_queue_set_index_(0), | 16 work_queue_set_index_(0), |
20 name_(name), | 17 name_(name), |
21 fence_(0) {} | 18 fence_(0) {} |
22 | 19 |
23 void WorkQueue::AsValueInto(base::trace_event::TracedValue* state) const { | 20 void WorkQueue::AsValueInto(base::trace_event::TracedValue* state) const { |
24 for (const TaskQueueImpl::Task& task : work_queue_) { | 21 // Remove const to search |work_queue_| in the destructive manner. Restore the |
25 TaskQueueImpl::TaskAsValueInto(task, state); | 22 // content from |visited| later. |
| 23 std::queue<TaskQueueImpl::Task>* mutable_queue = |
| 24 const_cast<std::queue<TaskQueueImpl::Task>*>(&work_queue_); |
| 25 std::queue<TaskQueueImpl::Task> visited; |
| 26 while (!mutable_queue->empty()) { |
| 27 TaskQueueImpl::TaskAsValueInto(mutable_queue->front(), state); |
| 28 visited.push(std::move(mutable_queue->front())); |
| 29 mutable_queue->pop(); |
26 } | 30 } |
| 31 *mutable_queue = std::move(visited); |
27 } | 32 } |
28 | 33 |
29 WorkQueue::~WorkQueue() { | 34 WorkQueue::~WorkQueue() { |
30 DCHECK(!work_queue_sets_) << task_queue_->GetName() << " : " | 35 DCHECK(!work_queue_sets_) << task_queue_->GetName() << " : " |
31 << work_queue_sets_->name() << " : " << name_; | 36 << work_queue_sets_->name() << " : " << name_; |
32 } | 37 } |
33 | 38 |
34 const TaskQueueImpl::Task* WorkQueue::GetFrontTask() const { | 39 const TaskQueueImpl::Task* WorkQueue::GetFrontTask() const { |
35 if (work_queue_.empty()) | 40 if (work_queue_.empty()) |
36 return nullptr; | 41 return nullptr; |
37 return &*work_queue_.begin(); | 42 return &work_queue_.front(); |
38 } | 43 } |
39 | 44 |
40 const TaskQueueImpl::Task* WorkQueue::GetBackTask() const { | 45 const TaskQueueImpl::Task* WorkQueue::GetBackTask() const { |
41 if (work_queue_.empty()) | 46 if (work_queue_.empty()) |
42 return nullptr; | 47 return nullptr; |
43 return &*work_queue_.rbegin(); | 48 return &work_queue_.back(); |
44 } | 49 } |
45 | 50 |
46 bool WorkQueue::BlockedByFence() const { | 51 bool WorkQueue::BlockedByFence() const { |
47 if (!fence_) | 52 if (!fence_) |
48 return false; | 53 return false; |
49 | 54 |
50 // If the queue is empty then any future tasks will have a higher enqueue | 55 // If the queue is empty then any future tasks will have a higher enqueue |
51 // order and will be blocked. The queue is also blocked if the head is past | 56 // order and will be blocked. The queue is also blocked if the head is past |
52 // the fence. | 57 // the fence. |
53 return work_queue_.empty() || work_queue_.begin()->enqueue_order() > fence_; | 58 return work_queue_.empty() || work_queue_.front().enqueue_order() > fence_; |
54 } | 59 } |
55 | 60 |
56 bool WorkQueue::GetFrontTaskEnqueueOrder(EnqueueOrder* enqueue_order) const { | 61 bool WorkQueue::GetFrontTaskEnqueueOrder(EnqueueOrder* enqueue_order) const { |
57 if (work_queue_.empty() || BlockedByFence()) | 62 if (work_queue_.empty() || BlockedByFence()) |
58 return false; | 63 return false; |
59 // Quick sanity check. | 64 // Quick sanity check. |
60 DCHECK_LE(work_queue_.begin()->enqueue_order(), | 65 DCHECK_LE(work_queue_.front().enqueue_order(), |
61 work_queue_.rbegin()->enqueue_order()) | 66 work_queue_.back().enqueue_order()) |
62 << task_queue_->GetName() << " : " | 67 << task_queue_->GetName() << " : " << work_queue_sets_->name() << " : " |
63 << work_queue_sets_->name() << " : " << name_; | 68 << name_; |
64 *enqueue_order = work_queue_.begin()->enqueue_order(); | 69 *enqueue_order = work_queue_.front().enqueue_order(); |
65 return true; | 70 return true; |
66 } | 71 } |
67 | 72 |
68 void WorkQueue::Push(TaskQueueImpl::Task task) { | 73 void WorkQueue::Push(TaskQueueImpl::Task task) { |
69 bool was_empty = work_queue_.empty(); | 74 bool was_empty = work_queue_.empty(); |
70 #ifndef NDEBUG | 75 #ifndef NDEBUG |
71 DCHECK(task.enqueue_order_set()); | 76 DCHECK(task.enqueue_order_set()); |
72 #endif | 77 #endif |
73 | 78 |
74 // We expect |task| to be inserted at the end. Amoritized O(1). | 79 // Amoritized O(1). |
75 work_queue_.insert(work_queue_.end(), std::move(task)); | 80 work_queue_.push(std::move(task)); |
76 DCHECK_EQ(task.enqueue_order(), work_queue_.rbegin()->enqueue_order()) | |
77 << task_queue_->GetName() << " : " | |
78 << work_queue_sets_->name() << " : " << name_ | |
79 << "task [scheduled_run_time_" << task.delayed_run_time << ", " | |
80 << task.sequence_num << | |
81 "] rbegin() [" << work_queue_.rbegin()->delayed_run_time << ", " | |
82 << work_queue_.rbegin()->sequence_num << "]"; | |
83 | 81 |
84 if (!was_empty) | 82 if (!was_empty) |
85 return; | 83 return; |
86 | 84 |
87 // If we hit the fence, pretend to WorkQueueSets that we're empty. | 85 // If we hit the fence, pretend to WorkQueueSets that we're empty. |
88 if (work_queue_sets_ && !BlockedByFence()) | 86 if (work_queue_sets_ && !BlockedByFence()) |
89 work_queue_sets_->OnPushQueue(this); | 87 work_queue_sets_->OnPushQueue(this); |
90 } | 88 } |
91 | 89 |
92 bool WorkQueue::CancelTask(const TaskQueueImpl::Task& key) { | |
93 TaskQueueImpl::ComparatorQueue::iterator it = work_queue_.find(key); | |
94 if (it == work_queue_.end()) | |
95 return false; | |
96 | |
97 if (it == work_queue_.begin()) { | |
98 EnqueueOrder erased_task_enqueue_order = it->enqueue_order(); | |
99 work_queue_.erase(it); | |
100 // We can't guarantee this WorkQueue is the lowest value in the WorkQueueSet | |
101 // so we need to use OnQueueHeadChanged instead of OnPopQueue for | |
102 // correctness. | |
103 if (!BlockedByFence()) | |
104 work_queue_sets_->OnQueueHeadChanged(this, erased_task_enqueue_order); | |
105 } else { | |
106 work_queue_.erase(it); | |
107 } | |
108 task_queue_->TraceQueueSize(false); | |
109 return true; | |
110 } | |
111 | |
112 bool WorkQueue::IsTaskPending(const TaskQueueImpl::Task& key) const { | |
113 return work_queue_.find(key) != work_queue_.end(); | |
114 } | |
115 | |
116 void WorkQueue::PopTaskForTest() { | 90 void WorkQueue::PopTaskForTest() { |
117 if (work_queue_.empty()) | 91 if (work_queue_.empty()) |
118 return; | 92 return; |
119 work_queue_.erase(work_queue_.begin()); | 93 work_queue_.pop(); |
120 } | 94 } |
121 | 95 |
122 void WorkQueue::SwapLocked(TaskQueueImpl::ComparatorQueue& incoming_queue) { | 96 void WorkQueue::SwapLocked(std::queue<TaskQueueImpl::Task>& incoming_queue) { |
123 DCHECK(work_queue_.empty()); | 97 DCHECK(work_queue_.empty()); |
124 std::swap(work_queue_, incoming_queue); | 98 std::swap(work_queue_, incoming_queue); |
125 if (work_queue_.empty()) | 99 if (work_queue_.empty()) |
126 return; | 100 return; |
127 // If we hit the fence, pretend to WorkQueueSets that we're empty. | 101 // If we hit the fence, pretend to WorkQueueSets that we're empty. |
128 if (work_queue_sets_ && !BlockedByFence()) | 102 if (work_queue_sets_ && !BlockedByFence()) |
129 work_queue_sets_->OnPushQueue(this); | 103 work_queue_sets_->OnPushQueue(this); |
130 } | 104 } |
131 | 105 |
132 TaskQueueImpl::Task WorkQueue::TakeTaskFromWorkQueue() { | 106 TaskQueueImpl::Task WorkQueue::TakeTaskFromWorkQueue() { |
133 DCHECK(work_queue_sets_); | 107 DCHECK(work_queue_sets_); |
134 DCHECK(!work_queue_.empty()); | 108 DCHECK(!work_queue_.empty()); |
135 TaskQueueImpl::ComparatorQueue::iterator it = work_queue_.begin(); | 109 |
| 110 // Skip over canceled tasks, except for the last one since we always return |
| 111 // something. |
| 112 while (work_queue_.size() > 1u && work_queue_.front().task.IsCancelled()) { |
| 113 work_queue_.pop(); |
| 114 } |
| 115 |
136 TaskQueueImpl::Task pending_task = | 116 TaskQueueImpl::Task pending_task = |
137 std::move(const_cast<TaskQueueImpl::Task&>(*it)); | 117 std::move(const_cast<TaskQueueImpl::Task&>(work_queue_.front())); |
138 work_queue_.erase(it); | 118 work_queue_.pop(); |
139 work_queue_sets_->OnPopQueue(this); | 119 work_queue_sets_->OnPopQueue(this); |
140 task_queue_->TraceQueueSize(false); | 120 task_queue_->TraceQueueSize(false); |
141 return pending_task; | 121 return pending_task; |
142 } | 122 } |
143 | 123 |
144 void WorkQueue::AssignToWorkQueueSets(WorkQueueSets* work_queue_sets) { | 124 void WorkQueue::AssignToWorkQueueSets(WorkQueueSets* work_queue_sets) { |
145 work_queue_sets_ = work_queue_sets; | 125 work_queue_sets_ = work_queue_sets; |
146 } | 126 } |
147 | 127 |
148 void WorkQueue::AssignSetIndex(size_t work_queue_set_index) { | 128 void WorkQueue::AssignSetIndex(size_t work_queue_set_index) { |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
182 bool have_other_task = | 162 bool have_other_task = |
183 other_queue->GetFrontTaskEnqueueOrder(&other_enqueue_order); | 163 other_queue->GetFrontTaskEnqueueOrder(&other_enqueue_order); |
184 DCHECK(have_task); | 164 DCHECK(have_task); |
185 DCHECK(have_other_task); | 165 DCHECK(have_other_task); |
186 return enqueue_order < other_enqueue_order; | 166 return enqueue_order < other_enqueue_order; |
187 } | 167 } |
188 | 168 |
189 } // namespace internal | 169 } // namespace internal |
190 } // namespace scheduler | 170 } // namespace scheduler |
191 } // namespace blink | 171 } // namespace blink |
OLD | NEW |