OLD | NEW |
---|---|
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 1 // Copyright 2014 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 "cc/resources/task_graph_runner.h" | 5 #include "cc/resources/task_graph_runner.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 | 8 |
9 #include "base/containers/hash_tables.h" | |
10 #include "base/debug/trace_event.h" | 9 #include "base/debug/trace_event.h" |
11 #include "base/strings/stringprintf.h" | 10 #include "base/strings/stringprintf.h" |
12 #include "base/threading/thread_restrictions.h" | 11 #include "base/threading/thread_restrictions.h" |
13 | 12 |
14 namespace cc { | 13 namespace cc { |
15 namespace internal { | 14 namespace internal { |
15 namespace { | |
16 | |
17 class DependentIterator { | |
18 public: | |
19 DependentIterator(TaskGraph* graph, const Task* task) | |
20 : graph_(graph), task_(task), current_index_(-1), current_node_(NULL) { | |
21 ++(*this); | |
22 } | |
23 | |
24 TaskGraph::Node& operator->() const { | |
25 DCHECK_LT(current_index_, graph_->edges.size()); | |
26 DCHECK_EQ(graph_->edges[current_index_].task, task_); | |
27 DCHECK(current_node_); | |
28 return *current_node_; | |
29 } | |
30 | |
31 TaskGraph::Node& operator*() const { | |
32 DCHECK_LT(current_index_, graph_->edges.size()); | |
33 DCHECK_EQ(graph_->edges[current_index_].task, task_); | |
34 DCHECK(current_node_); | |
35 return *current_node_; | |
36 } | |
37 | |
38 // Note: Performance can be improved by keeping edges sorted. | |
39 DependentIterator& operator++() { | |
vmpstr
2014/02/06 19:44:37
Can you put some comments in this function?
From
reveman
2014/02/06 20:51:52
Done. Not sure the comments add much though. PTAL.
| |
40 do { | |
41 ++current_index_; | |
42 if (current_index_ == graph_->edges.size()) | |
43 return *this; | |
44 } while (graph_->edges[current_index_].task != task_); | |
45 | |
46 TaskGraph::Node::Vector::iterator it = | |
47 std::find_if(graph_->nodes.begin(), | |
48 graph_->nodes.end(), | |
49 TaskGraph::Node::TaskComparator( | |
50 graph_->edges[current_index_].dependent)); | |
51 DCHECK(it != graph_->nodes.end()); | |
52 current_node_ = &(*it); | |
53 | |
54 return *this; | |
55 } | |
56 | |
57 operator bool() const { return current_index_ < graph_->edges.size(); } | |
58 | |
59 private: | |
60 TaskGraph* graph_; | |
61 const Task* task_; | |
62 size_t current_index_; | |
63 TaskGraph::Node* current_node_; | |
64 }; | |
65 | |
66 } // namespace | |
16 | 67 |
17 Task::Task() : did_run_(false) {} | 68 Task::Task() : did_run_(false) {} |
18 | 69 |
19 Task::~Task() {} | 70 Task::~Task() {} |
20 | 71 |
21 void Task::WillRun() { | 72 void Task::WillRun() { |
22 DCHECK(!did_run_); | 73 DCHECK(!did_run_); |
23 } | 74 } |
24 | 75 |
25 void Task::DidRun() { did_run_ = true; } | 76 void Task::DidRun() { did_run_ = true; } |
26 | 77 |
27 bool Task::HasFinishedRunning() const { return did_run_; } | 78 bool Task::HasFinishedRunning() const { return did_run_; } |
28 | 79 |
29 GraphNode::GraphNode(Task* task, unsigned priority) | 80 TaskGraph::TaskGraph() {} |
30 : task_(task), priority_(priority), num_dependencies_(0) {} | |
31 | 81 |
32 GraphNode::~GraphNode() {} | 82 TaskGraph::~TaskGraph() {} |
33 | 83 |
34 TaskGraphRunner::TaskNamespace::TaskNamespace() {} | 84 void TaskGraph::Swap(TaskGraph* other) { |
85 nodes.swap(other->nodes); | |
86 edges.swap(other->edges); | |
87 } | |
88 | |
89 void TaskGraph::Reset() { | |
90 nodes.clear(); | |
91 edges.clear(); | |
92 } | |
93 | |
94 TaskGraphRunner::TaskNamespace::TaskNamespace() : num_running_tasks(0u) {} | |
35 | 95 |
36 TaskGraphRunner::TaskNamespace::~TaskNamespace() {} | 96 TaskGraphRunner::TaskNamespace::~TaskNamespace() {} |
37 | 97 |
38 TaskGraphRunner::TaskGraphRunner(size_t num_threads, | 98 TaskGraphRunner::TaskGraphRunner(size_t num_threads, |
39 const std::string& thread_name_prefix) | 99 const std::string& thread_name_prefix) |
40 : lock_(), | 100 : lock_(), |
41 has_ready_to_run_tasks_cv_(&lock_), | 101 has_ready_to_run_tasks_cv_(&lock_), |
42 has_namespaces_with_finished_running_tasks_cv_(&lock_), | 102 has_namespaces_with_finished_running_tasks_cv_(&lock_), |
43 next_namespace_id_(1), | 103 next_namespace_id_(1), |
44 next_thread_index_(0u), | 104 next_thread_index_(0u), |
105 running_tasks_(num_threads + 1u, NULL), | |
enne (OOO)
2014/02/06 18:49:14
Why +1? Can you explain/leave a comment?
reveman
2014/02/06 20:51:52
Done.
| |
45 shutdown_(false) { | 106 shutdown_(false) { |
46 base::AutoLock lock(lock_); | 107 base::AutoLock lock(lock_); |
47 | 108 |
48 while (workers_.size() < num_threads) { | 109 while (workers_.size() < num_threads) { |
49 scoped_ptr<base::DelegateSimpleThread> worker = | 110 scoped_ptr<base::DelegateSimpleThread> worker = |
50 make_scoped_ptr(new base::DelegateSimpleThread( | 111 make_scoped_ptr(new base::DelegateSimpleThread( |
51 this, | 112 this, |
52 thread_name_prefix + | 113 thread_name_prefix + |
53 base::StringPrintf("Worker%u", | 114 base::StringPrintf("Worker%u", |
54 static_cast<unsigned>(workers_.size() + 1)) | 115 static_cast<unsigned>(workers_.size() + 1)) |
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
86 | 147 |
87 NamespaceToken TaskGraphRunner::GetNamespaceToken() { | 148 NamespaceToken TaskGraphRunner::GetNamespaceToken() { |
88 base::AutoLock lock(lock_); | 149 base::AutoLock lock(lock_); |
89 | 150 |
90 NamespaceToken token(next_namespace_id_++); | 151 NamespaceToken token(next_namespace_id_++); |
91 DCHECK(namespaces_.find(token.id_) == namespaces_.end()); | 152 DCHECK(namespaces_.find(token.id_) == namespaces_.end()); |
92 return token; | 153 return token; |
93 } | 154 } |
94 | 155 |
95 void TaskGraphRunner::WaitForTasksToFinishRunning(NamespaceToken token) { | 156 void TaskGraphRunner::WaitForTasksToFinishRunning(NamespaceToken token) { |
96 base::AutoLock lock(lock_); | 157 TRACE_EVENT0("cc", "TaskGraphRunner::WaitForTasksToFinishRunning"); |
97 | 158 |
98 DCHECK(token.IsValid()); | 159 DCHECK(token.IsValid()); |
99 TaskNamespaceMap::iterator it = namespaces_.find(token.id_); | |
100 if (it == namespaces_.end()) | |
101 return; | |
102 | 160 |
103 TaskNamespace* task_namespace = it->second; | 161 { |
104 while (!HasFinishedRunningTasksInNamespace(task_namespace)) | 162 base::AutoLock lock(lock_); |
105 has_namespaces_with_finished_running_tasks_cv_.Wait(); | |
106 | 163 |
107 // There may be other namespaces that have finished running | 164 TaskNamespaceMap::iterator it = namespaces_.find(token.id_); |
108 // tasks, so wake up another origin thread. | 165 if (it == namespaces_.end()) |
109 has_namespaces_with_finished_running_tasks_cv_.Signal(); | 166 return; |
167 | |
168 TaskNamespace* task_namespace = it->second; | |
169 | |
170 while (!HasFinishedRunningTasksInNamespace(task_namespace)) | |
171 has_namespaces_with_finished_running_tasks_cv_.Wait(); | |
172 | |
173 // There may be other namespaces that have finished running | |
174 // tasks, so wake up another origin thread. | |
175 has_namespaces_with_finished_running_tasks_cv_.Signal(); | |
176 } | |
110 } | 177 } |
111 | 178 |
112 void TaskGraphRunner::SetTaskGraph(NamespaceToken token, TaskGraph* graph) { | 179 void TaskGraphRunner::SetTaskGraph(NamespaceToken token, TaskGraph* graph) { |
180 TRACE_EVENT2("cc", | |
181 "TaskGraphRunner::SetTaskGraph", | |
182 "num_nodes", | |
183 graph->nodes.size(), | |
184 "num_edges", | |
185 graph->edges.size()); | |
186 | |
113 DCHECK(token.IsValid()); | 187 DCHECK(token.IsValid()); |
114 | 188 |
115 TaskGraph new_pending_tasks; | |
116 TaskGraph new_running_tasks; | |
117 | |
118 new_pending_tasks.swap(*graph); | |
119 | |
120 { | 189 { |
121 base::AutoLock lock(lock_); | 190 base::AutoLock lock(lock_); |
122 | 191 |
123 DCHECK(!shutdown_); | 192 DCHECK(!shutdown_); |
124 | 193 |
125 scoped_ptr<TaskNamespace> task_namespace = | 194 scoped_ptr<TaskNamespace> task_namespace = |
126 namespaces_.take_and_erase(token.id_); | 195 namespaces_.take_and_erase(token.id_); |
127 | 196 |
128 // Create task namespace if it doesn't exist. | 197 // Create task namespace if it doesn't exist. |
129 if (!task_namespace) | 198 if (!task_namespace) |
130 task_namespace.reset(new TaskNamespace); | 199 task_namespace.reset(new TaskNamespace); |
131 | 200 |
132 // First remove all completed tasks from |new_pending_tasks| and | 201 // First adjust number of dependencies to reflect completed tasks. |
133 // adjust number of dependencies. | |
134 for (Task::Vector::iterator it = task_namespace->completed_tasks.begin(); | 202 for (Task::Vector::iterator it = task_namespace->completed_tasks.begin(); |
135 it != task_namespace->completed_tasks.end(); | 203 it != task_namespace->completed_tasks.end(); |
136 ++it) { | 204 ++it) { |
137 Task* task = it->get(); | 205 for (DependentIterator node_it(graph, it->get()); node_it; ++node_it) { |
138 | 206 TaskGraph::Node& node = *node_it; |
139 scoped_ptr<GraphNode> node = new_pending_tasks.take_and_erase(task); | 207 DCHECK_LT(0u, node.dependencies); |
140 if (node) { | 208 node.dependencies--; |
141 for (GraphNode::Vector::const_iterator it = node->dependents().begin(); | |
142 it != node->dependents().end(); | |
143 ++it) { | |
144 GraphNode* dependent_node = *it; | |
145 dependent_node->remove_dependency(); | |
146 } | |
147 } | 209 } |
148 } | 210 } |
149 | 211 |
150 // Build new running task set. | 212 // Build new "ready to run" queue and remove nodes from old graph. |
151 for (TaskGraph::iterator it = task_namespace->running_tasks.begin(); | 213 task_namespace->ready_to_run_tasks.clear(); |
152 it != task_namespace->running_tasks.end(); | 214 for (TaskGraph::Node::Vector::iterator it = graph->nodes.begin(); |
215 it != graph->nodes.end(); | |
153 ++it) { | 216 ++it) { |
154 Task* task = it->first; | 217 TaskGraph::Node& node = *it; |
155 // Transfer scheduled task value from |new_pending_tasks| to | |
156 // |new_running_tasks| if currently running. Value must be set to | |
157 // NULL if |new_pending_tasks| doesn't contain task. This does | |
158 // the right in both cases. | |
159 new_running_tasks.set(task, new_pending_tasks.take_and_erase(task)); | |
160 } | |
161 | 218 |
162 // Build new "ready to run" tasks queue. | 219 // Remove any old nodes that are associated with this task. The result is |
163 task_namespace->ready_to_run_tasks.clear(); | 220 // that the old graph is left all nodes not present in this graph, which |
164 for (TaskGraph::iterator it = new_pending_tasks.begin(); | 221 // we use below to determine what tasks need to be canceled. |
165 it != new_pending_tasks.end(); | 222 TaskGraph::Node::Vector::iterator old_it = |
166 ++it) { | 223 std::find_if(task_namespace->graph.nodes.begin(), |
167 Task* task = it->first; | 224 task_namespace->graph.nodes.end(), |
168 DCHECK(task); | 225 TaskGraph::Node::TaskComparator(node.task)); |
169 GraphNode* node = it->second; | 226 if (old_it != task_namespace->graph.nodes.end()) { |
227 std::swap(*old_it, task_namespace->graph.nodes.back()); | |
228 task_namespace->graph.nodes.pop_back(); | |
229 } | |
170 | 230 |
171 // Completed tasks should not exist in |new_pending_tasks|. | 231 // Task is not ready to run if dependencies are not yet satisfied. |
172 DCHECK(!task->HasFinishedRunning()); | 232 if (node.dependencies) |
233 continue; | |
173 | 234 |
174 if (!node->num_dependencies()) | 235 // Skip if already finished running task. |
175 task_namespace->ready_to_run_tasks.push_back(node); | 236 if (node.task->HasFinishedRunning()) |
237 continue; | |
176 | 238 |
177 // Erase the task from old pending tasks. | 239 // Skip if already running. |
178 task_namespace->pending_tasks.erase(task); | 240 if (std::find(running_tasks_.begin(), running_tasks_.end(), node.task) != |
241 running_tasks_.end()) | |
242 continue; | |
243 | |
244 task_namespace->ready_to_run_tasks.push_back( | |
245 PrioritizedTask(node.task, node.priority)); | |
179 } | 246 } |
180 | 247 |
181 // Rearrange the elements in |ready_to_run_tasks| in such a way that | 248 // Rearrange the elements in |ready_to_run_tasks| in such a way that |
182 // they form a heap. | 249 // they form a heap. |
183 std::make_heap(task_namespace->ready_to_run_tasks.begin(), | 250 std::make_heap(task_namespace->ready_to_run_tasks.begin(), |
184 task_namespace->ready_to_run_tasks.end(), | 251 task_namespace->ready_to_run_tasks.end(), |
185 CompareTaskPriority); | 252 CompareTaskPriority); |
186 | 253 |
187 task_namespace->completed_tasks.reserve( | 254 // Swap task graph. |
188 task_namespace->completed_tasks.size() + | 255 task_namespace->graph.Swap(graph); |
189 task_namespace->pending_tasks.size()); | |
190 | 256 |
191 // The items left in |pending_tasks| need to be canceled. | 257 // Determine what tasks in old graph need to be canceled. |
192 for (TaskGraph::const_iterator it = task_namespace->pending_tasks.begin(); | 258 for (TaskGraph::Node::Vector::iterator it = graph->nodes.begin(); |
193 it != task_namespace->pending_tasks.end(); | 259 it != graph->nodes.end(); |
194 ++it) { | 260 ++it) { |
195 task_namespace->completed_tasks.push_back(it->first); | 261 TaskGraph::Node& node = *it; |
262 | |
263 // Skip if already finished running task. | |
264 if (node.task->HasFinishedRunning()) | |
265 continue; | |
266 | |
267 // Skip if already running. | |
268 if (std::find(running_tasks_.begin(), running_tasks_.end(), node.task) != | |
269 running_tasks_.end()) | |
270 continue; | |
271 | |
272 task_namespace->completed_tasks.push_back(node.task); | |
196 } | 273 } |
197 | 274 |
198 // Swap task sets. | 275 namespaces_.set(token.id_, task_namespace.Pass()); |
199 // Note: old tasks are intentionally destroyed after releasing |lock_|. | |
200 task_namespace->pending_tasks.swap(new_pending_tasks); | |
201 task_namespace->running_tasks.swap(new_running_tasks); | |
202 | |
203 // If |ready_to_run_tasks| is empty, it means we either have | |
204 // running tasks, or we have no pending tasks. | |
205 DCHECK(!task_namespace->ready_to_run_tasks.empty() || | |
206 (task_namespace->pending_tasks.empty() || | |
207 !task_namespace->running_tasks.empty())); | |
208 | |
209 // Add task namespace if not empty. | |
210 if (!task_namespace->pending_tasks.empty() || | |
211 !task_namespace->running_tasks.empty() || | |
212 !task_namespace->completed_tasks.empty()) { | |
213 namespaces_.set(token.id_, task_namespace.Pass()); | |
214 } | |
215 | 276 |
216 // Build new "ready to run" task namespaces queue. | 277 // Build new "ready to run" task namespaces queue. |
217 ready_to_run_namespaces_.clear(); | 278 ready_to_run_namespaces_.clear(); |
218 for (TaskNamespaceMap::iterator it = namespaces_.begin(); | 279 for (TaskNamespaceMap::iterator it = namespaces_.begin(); |
219 it != namespaces_.end(); | 280 it != namespaces_.end(); |
220 ++it) { | 281 ++it) { |
221 if (!it->second->ready_to_run_tasks.empty()) | 282 if (!it->second->ready_to_run_tasks.empty()) |
222 ready_to_run_namespaces_.push_back(it->second); | 283 ready_to_run_namespaces_.push_back(it->second); |
223 } | 284 } |
224 | 285 |
225 // Rearrange the task namespaces in |ready_to_run_namespaces_| | 286 // Rearrange the task namespaces in |ready_to_run_namespaces_| |
226 // in such a way that they form a heap. | 287 // in such a way that they form a heap. |
227 std::make_heap(ready_to_run_namespaces_.begin(), | 288 std::make_heap(ready_to_run_namespaces_.begin(), |
228 ready_to_run_namespaces_.end(), | 289 ready_to_run_namespaces_.end(), |
229 CompareTaskNamespacePriority); | 290 CompareTaskNamespacePriority); |
230 | 291 |
231 // If there is more work available, wake up worker thread. | 292 // If there is more work available, wake up worker thread. |
232 if (!ready_to_run_namespaces_.empty()) | 293 if (!ready_to_run_namespaces_.empty()) |
233 has_ready_to_run_tasks_cv_.Signal(); | 294 has_ready_to_run_tasks_cv_.Signal(); |
234 } | 295 } |
235 } | 296 } |
236 | 297 |
237 void TaskGraphRunner::CollectCompletedTasks(NamespaceToken token, | 298 void TaskGraphRunner::CollectCompletedTasks(NamespaceToken token, |
238 Task::Vector* completed_tasks) { | 299 Task::Vector* completed_tasks) { |
239 base::AutoLock lock(lock_); | 300 TRACE_EVENT0("cc", "TaskGraphRunner::CollectCompletedTasks"); |
240 | 301 |
241 DCHECK(token.IsValid()); | 302 DCHECK(token.IsValid()); |
242 TaskNamespaceMap::iterator it = namespaces_.find(token.id_); | |
243 if (it == namespaces_.end()) | |
244 return; | |
245 | 303 |
246 TaskNamespace* task_namespace = it->second; | 304 { |
305 base::AutoLock lock(lock_); | |
247 | 306 |
248 DCHECK_EQ(0u, completed_tasks->size()); | 307 TaskNamespaceMap::iterator it = namespaces_.find(token.id_); |
249 completed_tasks->swap(task_namespace->completed_tasks); | 308 if (it == namespaces_.end()) |
250 if (!HasFinishedRunningTasksInNamespace(task_namespace)) | 309 return; |
251 return; | |
252 | 310 |
253 // Remove namespace if finished running tasks. | 311 TaskNamespace* task_namespace = it->second; |
254 DCHECK_EQ(0u, task_namespace->pending_tasks.size()); | 312 |
255 DCHECK_EQ(0u, task_namespace->running_tasks.size()); | 313 DCHECK_EQ(0u, completed_tasks->size()); |
256 DCHECK_EQ(0u, task_namespace->completed_tasks.size()); | 314 completed_tasks->swap(task_namespace->completed_tasks); |
257 DCHECK_EQ(0u, task_namespace->ready_to_run_tasks.size()); | 315 if (!HasFinishedRunningTasksInNamespace(task_namespace)) |
258 namespaces_.erase(it); | 316 return; |
317 | |
318 // Remove namespace if finished running tasks. | |
319 DCHECK_EQ(0u, task_namespace->completed_tasks.size()); | |
320 DCHECK_EQ(0u, task_namespace->ready_to_run_tasks.size()); | |
321 DCHECK_EQ(0u, task_namespace->num_running_tasks); | |
322 namespaces_.erase(it); | |
323 } | |
259 } | 324 } |
260 | 325 |
261 bool TaskGraphRunner::RunTaskForTesting() { | 326 bool TaskGraphRunner::RunTaskForTesting() { |
262 base::AutoLock lock(lock_); | 327 base::AutoLock lock(lock_); |
263 | 328 |
264 if (ready_to_run_namespaces_.empty()) | 329 if (ready_to_run_namespaces_.empty()) |
265 return false; | 330 return false; |
266 | 331 |
267 RunTaskWithLockAcquired(0); | 332 RunTaskWithLockAcquired(0); |
268 return true; | 333 return true; |
(...skipping 18 matching lines...) Expand all Loading... | |
287 | 352 |
288 RunTaskWithLockAcquired(thread_index); | 353 RunTaskWithLockAcquired(thread_index); |
289 } | 354 } |
290 | 355 |
291 // We noticed we should exit. Wake up the next worker so it knows it should | 356 // We noticed we should exit. Wake up the next worker so it knows it should |
292 // exit as well (because the Shutdown() code only signals once). | 357 // exit as well (because the Shutdown() code only signals once). |
293 has_ready_to_run_tasks_cv_.Signal(); | 358 has_ready_to_run_tasks_cv_.Signal(); |
294 } | 359 } |
295 | 360 |
296 void TaskGraphRunner::RunTaskWithLockAcquired(int thread_index) { | 361 void TaskGraphRunner::RunTaskWithLockAcquired(int thread_index) { |
362 TRACE_EVENT1("cc", "TaskGraphRunner::RunTask", "thread_index", thread_index); | |
363 | |
297 lock_.AssertAcquired(); | 364 lock_.AssertAcquired(); |
298 DCHECK(!ready_to_run_namespaces_.empty()); | 365 DCHECK(!ready_to_run_namespaces_.empty()); |
299 | 366 |
300 // Take top priority TaskNamespace from |ready_to_run_namespaces_|. | 367 // Take top priority TaskNamespace from |ready_to_run_namespaces_|. |
301 std::pop_heap(ready_to_run_namespaces_.begin(), | 368 std::pop_heap(ready_to_run_namespaces_.begin(), |
302 ready_to_run_namespaces_.end(), | 369 ready_to_run_namespaces_.end(), |
303 CompareTaskNamespacePriority); | 370 CompareTaskNamespacePriority); |
304 TaskNamespace* task_namespace = ready_to_run_namespaces_.back(); | 371 TaskNamespace* task_namespace = ready_to_run_namespaces_.back(); |
305 ready_to_run_namespaces_.pop_back(); | 372 ready_to_run_namespaces_.pop_back(); |
306 DCHECK(!task_namespace->ready_to_run_tasks.empty()); | 373 DCHECK(!task_namespace->ready_to_run_tasks.empty()); |
307 | 374 |
308 // Take top priority task from |ready_to_run_tasks|. | 375 // Take top priority task from |ready_to_run_tasks|. |
309 std::pop_heap(task_namespace->ready_to_run_tasks.begin(), | 376 std::pop_heap(task_namespace->ready_to_run_tasks.begin(), |
310 task_namespace->ready_to_run_tasks.end(), | 377 task_namespace->ready_to_run_tasks.end(), |
311 CompareTaskPriority); | 378 CompareTaskPriority); |
312 scoped_refptr<Task> task(task_namespace->ready_to_run_tasks.back()->task()); | 379 scoped_refptr<Task> task(task_namespace->ready_to_run_tasks.back().task); |
313 task_namespace->ready_to_run_tasks.pop_back(); | 380 task_namespace->ready_to_run_tasks.pop_back(); |
314 | 381 |
315 // Add task namespace back to |ready_to_run_namespaces_| if not | 382 // Add task namespace back to |ready_to_run_namespaces_| if not |
316 // empty after taking top priority task. | 383 // empty after taking top priority task. |
317 if (!task_namespace->ready_to_run_tasks.empty()) { | 384 if (!task_namespace->ready_to_run_tasks.empty()) { |
318 ready_to_run_namespaces_.push_back(task_namespace); | 385 ready_to_run_namespaces_.push_back(task_namespace); |
319 std::push_heap(ready_to_run_namespaces_.begin(), | 386 std::push_heap(ready_to_run_namespaces_.begin(), |
320 ready_to_run_namespaces_.end(), | 387 ready_to_run_namespaces_.end(), |
321 CompareTaskNamespacePriority); | 388 CompareTaskNamespacePriority); |
322 } | 389 } |
323 | 390 |
324 // Move task from |pending_tasks| to |running_tasks|. | 391 // Add task to |running_tasks_|. |
325 DCHECK(task_namespace->pending_tasks.contains(task.get())); | 392 DCHECK_LT(static_cast<size_t>(thread_index), running_tasks_.size()); |
326 DCHECK(!task_namespace->running_tasks.contains(task.get())); | 393 DCHECK(!running_tasks_[thread_index]); |
327 task_namespace->running_tasks.set( | 394 running_tasks_[thread_index] = task.get(); |
328 task.get(), task_namespace->pending_tasks.take_and_erase(task.get())); | 395 |
396 // Increment running task count for task namespace. | |
397 task_namespace->num_running_tasks++; | |
329 | 398 |
330 // There may be more work available, so wake up another worker thread. | 399 // There may be more work available, so wake up another worker thread. |
331 has_ready_to_run_tasks_cv_.Signal(); | 400 has_ready_to_run_tasks_cv_.Signal(); |
332 | 401 |
333 // Call WillRun() before releasing |lock_| and running task. | 402 // Call WillRun() before releasing |lock_| and running task. |
334 task->WillRun(); | 403 task->WillRun(); |
335 | 404 |
336 { | 405 { |
337 base::AutoUnlock unlock(lock_); | 406 base::AutoUnlock unlock(lock_); |
338 | 407 |
339 task->RunOnWorkerThread(thread_index); | 408 task->RunOnWorkerThread(thread_index); |
340 } | 409 } |
341 | 410 |
342 // This will mark task as finished running. | 411 // This will mark task as finished running. |
343 task->DidRun(); | 412 task->DidRun(); |
344 | 413 |
345 // Now iterate over all dependents to remove dependency and check | 414 // Decrement running task count for task namespace. |
346 // if they are ready to run. | 415 DCHECK_LT(0u, task_namespace->num_running_tasks); |
347 scoped_ptr<GraphNode> node = | 416 task_namespace->num_running_tasks--; |
348 task_namespace->running_tasks.take_and_erase(task.get()); | |
349 if (node) { | |
350 bool ready_to_run_namespaces_has_heap_properties = true; | |
351 | 417 |
352 for (GraphNode::Vector::const_iterator it = node->dependents().begin(); | 418 // Remove task from |running_tasks_|. |
353 it != node->dependents().end(); | 419 running_tasks_[thread_index] = NULL; |
354 ++it) { | |
355 GraphNode* dependent_node = *it; | |
356 | 420 |
357 dependent_node->remove_dependency(); | 421 // Now iterate over all dependents to decrement dependencies and check if they |
358 // Task is ready if it has no dependencies. Add it to | 422 // are ready to run. |
359 // |ready_to_run_tasks_|. | 423 bool ready_to_run_namespaces_has_heap_properties = true; |
360 if (!dependent_node->num_dependencies()) { | 424 for (DependentIterator it(&task_namespace->graph, task.get()); it; ++it) { |
361 bool was_empty = task_namespace->ready_to_run_tasks.empty(); | 425 TaskGraph::Node& dependent_node = *it; |
362 task_namespace->ready_to_run_tasks.push_back(dependent_node); | 426 |
363 std::push_heap(task_namespace->ready_to_run_tasks.begin(), | 427 DCHECK_LT(0u, dependent_node.dependencies); |
364 task_namespace->ready_to_run_tasks.end(), | 428 dependent_node.dependencies--; |
365 CompareTaskPriority); | 429 // Task is ready if it has no dependencies. Add it to |ready_to_run_tasks_|. |
366 // Task namespace is ready if it has at least one ready | 430 if (!dependent_node.dependencies) { |
367 // to run task. Add it to |ready_to_run_namespaces_| if | 431 bool was_empty = task_namespace->ready_to_run_tasks.empty(); |
368 // it just become ready. | 432 task_namespace->ready_to_run_tasks.push_back( |
369 if (was_empty) { | 433 PrioritizedTask(dependent_node.task, dependent_node.priority)); |
370 DCHECK(std::find(ready_to_run_namespaces_.begin(), | 434 std::push_heap(task_namespace->ready_to_run_tasks.begin(), |
371 ready_to_run_namespaces_.end(), | 435 task_namespace->ready_to_run_tasks.end(), |
372 task_namespace) == ready_to_run_namespaces_.end()); | 436 CompareTaskPriority); |
373 ready_to_run_namespaces_.push_back(task_namespace); | 437 // Task namespace is ready if it has at least one ready to run task. Add |
374 } | 438 // it to |ready_to_run_namespaces_| if it just become ready. |
375 ready_to_run_namespaces_has_heap_properties = false; | 439 if (was_empty) { |
440 DCHECK(std::find(ready_to_run_namespaces_.begin(), | |
441 ready_to_run_namespaces_.end(), | |
442 task_namespace) == ready_to_run_namespaces_.end()); | |
443 ready_to_run_namespaces_.push_back(task_namespace); | |
376 } | 444 } |
377 } | 445 ready_to_run_namespaces_has_heap_properties = false; |
378 | |
379 // Rearrange the task namespaces in |ready_to_run_namespaces_| | |
380 // in such a way that they yet again form a heap. | |
381 if (!ready_to_run_namespaces_has_heap_properties) { | |
382 std::make_heap(ready_to_run_namespaces_.begin(), | |
383 ready_to_run_namespaces_.end(), | |
384 CompareTaskNamespacePriority); | |
385 } | 446 } |
386 } | 447 } |
387 | 448 |
449 // Rearrange the task namespaces in |ready_to_run_namespaces_| in such a way | |
450 // that they yet again form a heap. | |
451 if (!ready_to_run_namespaces_has_heap_properties) { | |
452 std::make_heap(ready_to_run_namespaces_.begin(), | |
453 ready_to_run_namespaces_.end(), | |
454 CompareTaskNamespacePriority); | |
455 } | |
456 | |
388 // Finally add task to |completed_tasks_|. | 457 // Finally add task to |completed_tasks_|. |
389 task_namespace->completed_tasks.push_back(task); | 458 task_namespace->completed_tasks.push_back(task); |
390 | 459 |
391 // If namespace has finished running all tasks, wake up origin thread. | 460 // If namespace has finished running all tasks, wake up origin thread. |
392 if (HasFinishedRunningTasksInNamespace(task_namespace)) | 461 if (HasFinishedRunningTasksInNamespace(task_namespace)) |
393 has_namespaces_with_finished_running_tasks_cv_.Signal(); | 462 has_namespaces_with_finished_running_tasks_cv_.Signal(); |
394 } | 463 } |
395 | 464 |
396 } // namespace internal | 465 } // namespace internal |
397 } // namespace cc | 466 } // namespace cc |
OLD | NEW |