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