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, |
14 const char* name, | 14 const char* name, |
15 TaskQueueImpl::Task::ComparatorFn comparator) | 15 TaskQueueImpl::Task::ComparatorFn comparator) |
16 : work_queue_(comparator), | 16 : work_queue_(comparator), |
17 work_queue_sets_(nullptr), | 17 work_queue_sets_(nullptr), |
18 task_queue_(task_queue), | 18 task_queue_(task_queue), |
19 work_queue_set_index_(0), | 19 work_queue_set_index_(0), |
20 name_(name) {} | 20 name_(name), |
| 21 fence_(0) {} |
21 | 22 |
22 void WorkQueue::AsValueInto(base::trace_event::TracedValue* state) const { | 23 void WorkQueue::AsValueInto(base::trace_event::TracedValue* state) const { |
23 for (const TaskQueueImpl::Task& task : work_queue_) { | 24 for (const TaskQueueImpl::Task& task : work_queue_) { |
24 TaskQueueImpl::TaskAsValueInto(task, state); | 25 TaskQueueImpl::TaskAsValueInto(task, state); |
25 } | 26 } |
26 } | 27 } |
27 | 28 |
28 WorkQueue::~WorkQueue() { | 29 WorkQueue::~WorkQueue() { |
29 DCHECK(!work_queue_sets_) << task_queue_->GetName() << " : " | 30 DCHECK(!work_queue_sets_) << task_queue_->GetName() << " : " |
30 << work_queue_sets_->name() << " : " << name_; | 31 << work_queue_sets_->name() << " : " << name_; |
31 } | 32 } |
32 | 33 |
33 const TaskQueueImpl::Task* WorkQueue::GetFrontTask() const { | 34 const TaskQueueImpl::Task* WorkQueue::GetFrontTask() const { |
34 if (work_queue_.empty()) | 35 if (work_queue_.empty()) |
35 return nullptr; | 36 return nullptr; |
36 return &*work_queue_.begin(); | 37 return &*work_queue_.begin(); |
37 } | 38 } |
38 | 39 |
| 40 const TaskQueueImpl::Task* WorkQueue::GetBackTask() const { |
| 41 if (work_queue_.empty()) |
| 42 return nullptr; |
| 43 return &*work_queue_.rbegin(); |
| 44 } |
| 45 |
| 46 bool WorkQueue::BlockedByFence() const { |
| 47 if (!fence_) |
| 48 return false; |
| 49 |
| 50 // 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 |
| 52 // the fence. |
| 53 return work_queue_.empty() || work_queue_.begin()->enqueue_order() > fence_; |
| 54 } |
| 55 |
39 bool WorkQueue::GetFrontTaskEnqueueOrder(EnqueueOrder* enqueue_order) const { | 56 bool WorkQueue::GetFrontTaskEnqueueOrder(EnqueueOrder* enqueue_order) const { |
40 if (work_queue_.empty()) | 57 if (work_queue_.empty() || BlockedByFence()) |
41 return false; | 58 return false; |
42 // Quick sanity check. | 59 // Quick sanity check. |
43 DCHECK_LE(work_queue_.begin()->enqueue_order(), | 60 DCHECK_LE(work_queue_.begin()->enqueue_order(), |
44 work_queue_.rbegin()->enqueue_order()) | 61 work_queue_.rbegin()->enqueue_order()) |
45 << task_queue_->GetName() << " : " | 62 << task_queue_->GetName() << " : " |
46 << work_queue_sets_->name() << " : " << name_; | 63 << work_queue_sets_->name() << " : " << name_; |
47 *enqueue_order = work_queue_.begin()->enqueue_order(); | 64 *enqueue_order = work_queue_.begin()->enqueue_order(); |
48 return true; | 65 return true; |
49 } | 66 } |
50 | 67 |
51 void WorkQueue::Push(TaskQueueImpl::Task task) { | 68 void WorkQueue::Push(TaskQueueImpl::Task task) { |
52 bool was_empty = work_queue_.empty(); | 69 bool was_empty = work_queue_.empty(); |
53 #ifndef NDEBUG | 70 #ifndef NDEBUG |
54 DCHECK(task.enqueue_order_set()); | 71 DCHECK(task.enqueue_order_set()); |
55 #endif | 72 #endif |
56 | 73 |
57 // We expect |task| to be inserted at the end. Amoritized O(1). | 74 // We expect |task| to be inserted at the end. Amoritized O(1). |
58 work_queue_.insert(work_queue_.end(), std::move(task)); | 75 work_queue_.insert(work_queue_.end(), std::move(task)); |
59 DCHECK_EQ(task.enqueue_order(), work_queue_.rbegin()->enqueue_order()) | 76 DCHECK_EQ(task.enqueue_order(), work_queue_.rbegin()->enqueue_order()) |
60 << task_queue_->GetName() << " : " | 77 << task_queue_->GetName() << " : " |
61 << work_queue_sets_->name() << " : " << name_ | 78 << work_queue_sets_->name() << " : " << name_ |
62 << "task [scheduled_run_time_" << task.delayed_run_time << ", " | 79 << "task [scheduled_run_time_" << task.delayed_run_time << ", " |
63 << task.sequence_num << | 80 << task.sequence_num << |
64 "] rbegin() [" << work_queue_.rbegin()->delayed_run_time << ", " | 81 "] rbegin() [" << work_queue_.rbegin()->delayed_run_time << ", " |
65 << work_queue_.rbegin()->sequence_num << "]"; | 82 << work_queue_.rbegin()->sequence_num << "]"; |
66 | 83 |
67 if (was_empty && work_queue_sets_) { | 84 if (!was_empty) |
| 85 return; |
| 86 |
| 87 // If we hit the fence, pretend to WorkQueueSets that we're empty. |
| 88 if (work_queue_sets_ && !BlockedByFence()) |
68 work_queue_sets_->OnPushQueue(this); | 89 work_queue_sets_->OnPushQueue(this); |
69 } | |
70 } | 90 } |
71 | 91 |
72 bool WorkQueue::CancelTask(const TaskQueueImpl::Task& key) { | 92 bool WorkQueue::CancelTask(const TaskQueueImpl::Task& key) { |
73 TaskQueueImpl::ComparatorQueue::iterator it = work_queue_.find(key); | 93 TaskQueueImpl::ComparatorQueue::iterator it = work_queue_.find(key); |
74 if (it == work_queue_.end()) | 94 if (it == work_queue_.end()) |
75 return false; | 95 return false; |
76 | 96 |
77 if (it == work_queue_.begin()) { | 97 if (it == work_queue_.begin()) { |
78 EnqueueOrder erased_task_enqueue_order = it->enqueue_order(); | 98 EnqueueOrder erased_task_enqueue_order = it->enqueue_order(); |
79 work_queue_.erase(it); | 99 work_queue_.erase(it); |
80 // We can't guarantee this WorkQueue is the lowest value in the WorkQueueSet | 100 // We can't guarantee this WorkQueue is the lowest value in the WorkQueueSet |
81 // so we need to use OnQueueHeadChanged instead of OnPopQueue for | 101 // so we need to use OnQueueHeadChanged instead of OnPopQueue for |
82 // correctness. | 102 // correctness. |
83 work_queue_sets_->OnQueueHeadChanged(this, erased_task_enqueue_order); | 103 if (!BlockedByFence()) |
| 104 work_queue_sets_->OnQueueHeadChanged(this, erased_task_enqueue_order); |
84 } else { | 105 } else { |
85 work_queue_.erase(it); | 106 work_queue_.erase(it); |
86 } | 107 } |
87 task_queue_->TraceQueueSize(false); | 108 task_queue_->TraceQueueSize(false); |
88 return true; | 109 return true; |
89 } | 110 } |
90 | 111 |
91 bool WorkQueue::IsTaskPending(const TaskQueueImpl::Task& key) const { | 112 bool WorkQueue::IsTaskPending(const TaskQueueImpl::Task& key) const { |
92 return work_queue_.find(key) != work_queue_.end(); | 113 return work_queue_.find(key) != work_queue_.end(); |
93 } | 114 } |
94 | 115 |
95 void WorkQueue::PopTaskForTest() { | 116 void WorkQueue::PopTaskForTest() { |
96 if (work_queue_.empty()) | 117 if (work_queue_.empty()) |
97 return; | 118 return; |
98 work_queue_.erase(work_queue_.begin()); | 119 work_queue_.erase(work_queue_.begin()); |
99 } | 120 } |
100 | 121 |
101 void WorkQueue::SwapLocked(TaskQueueImpl::ComparatorQueue& incoming_queue) { | 122 void WorkQueue::SwapLocked(TaskQueueImpl::ComparatorQueue& incoming_queue) { |
102 DCHECK(work_queue_.empty()); | 123 DCHECK(work_queue_.empty()); |
103 std::swap(work_queue_, incoming_queue); | 124 std::swap(work_queue_, incoming_queue); |
104 if (!work_queue_.empty() && work_queue_sets_) | 125 if (work_queue_.empty()) |
| 126 return; |
| 127 // If we hit the fence, pretend to WorkQueueSets that we're empty. |
| 128 if (work_queue_sets_ && !BlockedByFence()) |
105 work_queue_sets_->OnPushQueue(this); | 129 work_queue_sets_->OnPushQueue(this); |
106 task_queue_->TraceQueueSize(true); | |
107 } | 130 } |
108 | 131 |
109 TaskQueueImpl::Task WorkQueue::TakeTaskFromWorkQueue() { | 132 TaskQueueImpl::Task WorkQueue::TakeTaskFromWorkQueue() { |
110 DCHECK(work_queue_sets_); | 133 DCHECK(work_queue_sets_); |
111 DCHECK(!work_queue_.empty()); | 134 DCHECK(!work_queue_.empty()); |
112 TaskQueueImpl::ComparatorQueue::iterator it = work_queue_.begin(); | 135 TaskQueueImpl::ComparatorQueue::iterator it = work_queue_.begin(); |
113 TaskQueueImpl::Task pending_task = | 136 TaskQueueImpl::Task pending_task = |
114 std::move(const_cast<TaskQueueImpl::Task&>(*it)); | 137 std::move(const_cast<TaskQueueImpl::Task&>(*it)); |
115 work_queue_.erase(it); | 138 work_queue_.erase(it); |
116 work_queue_sets_->OnPopQueue(this); | 139 work_queue_sets_->OnPopQueue(this); |
117 task_queue_->TraceQueueSize(false); | 140 task_queue_->TraceQueueSize(false); |
118 return pending_task; | 141 return pending_task; |
119 } | 142 } |
120 | 143 |
121 void WorkQueue::AssignToWorkQueueSets(WorkQueueSets* work_queue_sets) { | 144 void WorkQueue::AssignToWorkQueueSets(WorkQueueSets* work_queue_sets) { |
122 work_queue_sets_ = work_queue_sets; | 145 work_queue_sets_ = work_queue_sets; |
123 } | 146 } |
124 | 147 |
125 void WorkQueue::AssignSetIndex(size_t work_queue_set_index) { | 148 void WorkQueue::AssignSetIndex(size_t work_queue_set_index) { |
126 work_queue_set_index_ = work_queue_set_index; | 149 work_queue_set_index_ = work_queue_set_index; |
127 } | 150 } |
128 | 151 |
| 152 bool WorkQueue::InsertFence(EnqueueOrder fence) { |
| 153 DCHECK_NE(fence, 0u); |
| 154 DCHECK_GE(fence, fence_); |
| 155 bool was_blocked_by_fence = BlockedByFence(); |
| 156 fence_ = fence; |
| 157 // Moving the fence forward may unblock some tasks. |
| 158 if (work_queue_sets_ && !work_queue_.empty() && was_blocked_by_fence && |
| 159 !BlockedByFence()) { |
| 160 work_queue_sets_->OnPushQueue(this); |
| 161 return true; |
| 162 } |
| 163 return false; |
| 164 } |
| 165 |
| 166 bool WorkQueue::RemoveFence() { |
| 167 bool was_blocked_by_fence = BlockedByFence(); |
| 168 fence_ = 0; |
| 169 if (work_queue_sets_ && !work_queue_.empty() && was_blocked_by_fence) { |
| 170 work_queue_sets_->OnPushQueue(this); |
| 171 return true; |
| 172 } |
| 173 return false; |
| 174 } |
| 175 |
129 bool WorkQueue::ShouldRunBefore(const WorkQueue* other_queue) const { | 176 bool WorkQueue::ShouldRunBefore(const WorkQueue* other_queue) const { |
130 DCHECK(!work_queue_.empty()); | 177 DCHECK(!work_queue_.empty()); |
131 DCHECK(!other_queue->work_queue_.empty()); | 178 DCHECK(!other_queue->work_queue_.empty()); |
132 EnqueueOrder enqueue_order = 0; | 179 EnqueueOrder enqueue_order = 0; |
133 EnqueueOrder other_enqueue_order = 0; | 180 EnqueueOrder other_enqueue_order = 0; |
134 bool have_task = GetFrontTaskEnqueueOrder(&enqueue_order); | 181 bool have_task = GetFrontTaskEnqueueOrder(&enqueue_order); |
135 bool have_other_task = | 182 bool have_other_task = |
136 other_queue->GetFrontTaskEnqueueOrder(&other_enqueue_order); | 183 other_queue->GetFrontTaskEnqueueOrder(&other_enqueue_order); |
137 DCHECK(have_task); | 184 DCHECK(have_task); |
138 DCHECK(have_other_task); | 185 DCHECK(have_other_task); |
139 return enqueue_order < other_enqueue_order; | 186 return enqueue_order < other_enqueue_order; |
140 } | 187 } |
141 | 188 |
142 } // namespace internal | 189 } // namespace internal |
143 } // namespace scheduler | 190 } // namespace scheduler |
144 } // namespace blink | 191 } // namespace blink |
OLD | NEW |