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 #ifndef CC_RASTER_TASK_GRAPH_RUNNER_H_ | 5 #ifndef CC_RASTER_TASK_GRAPH_RUNNER_H_ |
6 #define CC_RASTER_TASK_GRAPH_RUNNER_H_ | 6 #define CC_RASTER_TASK_GRAPH_RUNNER_H_ |
7 | 7 |
| 8 #include <algorithm> |
8 #include <map> | 9 #include <map> |
9 #include <vector> | 10 #include <vector> |
10 | 11 |
11 #include "base/logging.h" | 12 #include "base/logging.h" |
12 #include "base/memory/ref_counted.h" | 13 #include "base/memory/ref_counted.h" |
13 #include "base/synchronization/condition_variable.h" | 14 #include "base/memory/scoped_ptr.h" |
14 #include "cc/base/cc_export.h" | 15 #include "cc/base/cc_export.h" |
15 | 16 |
16 namespace cc { | 17 namespace cc { |
17 | 18 |
| 19 class TaskGraphRunner; |
| 20 |
| 21 // A task which can be run by a TaskGraphRunner. To run a Task, it should be |
| 22 // inserted into a TaskGraph, which can then be scheduled on the |
| 23 // TaskGraphRunner. |
18 class CC_EXPORT Task : public base::RefCountedThreadSafe<Task> { | 24 class CC_EXPORT Task : public base::RefCountedThreadSafe<Task> { |
19 public: | 25 public: |
20 typedef std::vector<scoped_refptr<Task>> Vector; | 26 typedef std::vector<scoped_refptr<Task>> Vector; |
21 | 27 |
| 28 // Subclasses should implement this method. RunOnWorkerThread may be called |
| 29 // on any thread, and subclasses are responsible for locking and thread |
| 30 // safety. |
22 virtual void RunOnWorkerThread() = 0; | 31 virtual void RunOnWorkerThread() = 0; |
23 | 32 |
24 void WillRun(); | 33 void WillRun(); |
25 void DidRun(); | 34 void DidRun(); |
26 bool HasFinishedRunning() const; | 35 bool HasFinishedRunning() const; |
27 | 36 |
28 protected: | 37 protected: |
29 friend class base::RefCountedThreadSafe<Task>; | 38 friend class base::RefCountedThreadSafe<Task>; |
30 | 39 |
31 Task(); | 40 Task(); |
32 virtual ~Task(); | 41 virtual ~Task(); |
33 | 42 |
34 bool will_run_; | 43 bool will_run_; |
35 bool did_run_; | 44 bool did_run_; |
36 }; | 45 }; |
37 | 46 |
38 // Dependencies are represented as edges in a task graph. Each graph node is | 47 // A task dependency graph describes the order in which to execute a set |
39 // assigned a priority and a run count that matches the number of dependencies. | 48 // of tasks. Dependencies are represented as edges. Each node is assigned |
40 // Priority range from 0 (most favorable scheduling) to UINT_MAX (least | 49 // a priority and a run count that matches the number of dependencies. |
41 // favorable). | 50 // Priority range from 0 (most favorable scheduling) to UINT_MAX |
| 51 // (least favorable). |
42 struct CC_EXPORT TaskGraph { | 52 struct CC_EXPORT TaskGraph { |
43 struct Node { | 53 struct Node { |
44 class TaskComparator { | |
45 public: | |
46 explicit TaskComparator(const Task* task) : task_(task) {} | |
47 | |
48 bool operator()(const Node& node) const { return node.task == task_; } | |
49 | |
50 private: | |
51 const Task* task_; | |
52 }; | |
53 | |
54 typedef std::vector<Node> Vector; | 54 typedef std::vector<Node> Vector; |
55 | 55 |
56 Node(Task* task, size_t priority, size_t dependencies) | 56 Node(Task* task, size_t priority, size_t dependencies) |
57 : task(task), priority(priority), dependencies(dependencies) {} | 57 : task(task), priority(priority), dependencies(dependencies) {} |
58 | 58 |
59 Task* task; | 59 Task* task; |
60 size_t priority; | 60 size_t priority; |
61 size_t dependencies; | 61 size_t dependencies; |
62 }; | 62 }; |
63 | 63 |
(...skipping 10 matching lines...) Expand all Loading... |
74 TaskGraph(); | 74 TaskGraph(); |
75 ~TaskGraph(); | 75 ~TaskGraph(); |
76 | 76 |
77 void Swap(TaskGraph* other); | 77 void Swap(TaskGraph* other); |
78 void Reset(); | 78 void Reset(); |
79 | 79 |
80 Node::Vector nodes; | 80 Node::Vector nodes; |
81 Edge::Vector edges; | 81 Edge::Vector edges; |
82 }; | 82 }; |
83 | 83 |
84 class TaskGraphRunner; | |
85 | |
86 // Opaque identifier that defines a namespace of tasks. | 84 // Opaque identifier that defines a namespace of tasks. |
87 class CC_EXPORT NamespaceToken { | 85 class CC_EXPORT NamespaceToken { |
88 public: | 86 public: |
89 NamespaceToken() : id_(0) {} | 87 NamespaceToken() : id_(0) {} |
90 ~NamespaceToken() {} | 88 ~NamespaceToken() {} |
91 | 89 |
92 bool IsValid() const { return id_ != 0; } | 90 bool IsValid() const { return id_ != 0; } |
93 | 91 |
94 private: | 92 private: |
95 friend class TaskGraphRunner; | 93 friend class TaskGraphWorkQueue; |
96 | 94 |
97 explicit NamespaceToken(int id) : id_(id) {} | 95 explicit NamespaceToken(int id) : id_(id) {} |
98 | 96 |
99 int id_; | 97 int id_; |
100 }; | 98 }; |
101 | 99 |
102 // A TaskGraphRunner is used to process tasks with dependencies. There can | 100 // A TaskGraphRunner is an object that runs a set of tasks in the |
103 // be any number of TaskGraphRunner instances per thread. Tasks can be scheduled | 101 // order defined by a dependency graph. The TaskGraphRunner interface |
104 // from any thread and they can be run on any thread. | 102 // provides a way of decoupling task scheduling from the mechanics of |
| 103 // how each task will be run. TaskGraphRunner provides the following |
| 104 // guarantees: |
| 105 // |
| 106 // - Scheduled tasks will not run synchronously. That is, the |
| 107 // ScheduleTasks() method will not call Task::Run() directly. |
| 108 // |
| 109 // - Scheduled tasks are guaranteed to run in the order defined by |
| 110 // dependency graph. |
| 111 // |
| 112 // - Once scheduled, a task is guaranteed to end up in the |
| 113 // |completed_tasks| vector populated by CollectCompletedTasks(), |
| 114 // even if it later gets canceled by another call to ScheduleTasks(). |
| 115 // |
| 116 // TaskGraphRunner does not guarantee that a task with high priority |
| 117 // runs after a task with low priority. The priority is just a hint |
| 118 // and a valid TaskGraphRunner might ignore it. Also it does not |
| 119 // guarantee a memory model for shared data between tasks. (In other |
| 120 // words, you should use your own synchronization/locking primitives if |
| 121 // you need to share data between tasks.) |
| 122 // |
| 123 // Implementations of TaskGraphRunner should be thread-safe in that all |
| 124 // methods must be safe to call on any thread. |
| 125 // |
| 126 // Some theoretical implementations of TaskGraphRunner: |
| 127 // |
| 128 // - A TaskGraphRunner that uses a thread pool to run scheduled tasks. |
| 129 // |
| 130 // - A TaskGraphRunner that has a method Run() that runs each task. |
105 class CC_EXPORT TaskGraphRunner { | 131 class CC_EXPORT TaskGraphRunner { |
106 public: | 132 public: |
107 TaskGraphRunner(); | |
108 virtual ~TaskGraphRunner(); | |
109 | |
110 // Returns a unique token that can be used to pass a task graph to | 133 // Returns a unique token that can be used to pass a task graph to |
111 // ScheduleTasks(). Valid tokens are always nonzero. | 134 // ScheduleTasks(). Valid tokens are always nonzero. |
112 NamespaceToken GetNamespaceToken(); | 135 virtual NamespaceToken GetNamespaceToken() = 0; |
113 | 136 |
114 // Schedule running of tasks in |graph|. Tasks previously scheduled but no | 137 // Schedule running of tasks in |graph|. Tasks previously scheduled but no |
115 // longer needed will be canceled unless already running. Canceled tasks are | 138 // longer needed will be canceled unless already running. Canceled tasks are |
116 // moved to |completed_tasks| without being run. The result is that once | 139 // moved to |completed_tasks| without being run. The result is that once |
117 // scheduled, a task is guaranteed to end up in the |completed_tasks| queue | 140 // scheduled, a task is guaranteed to end up in the |completed_tasks| queue |
118 // even if it later gets canceled by another call to ScheduleTasks(). | 141 // even if it later gets canceled by another call to ScheduleTasks(). |
119 void ScheduleTasks(NamespaceToken token, TaskGraph* graph); | 142 virtual void ScheduleTasks(NamespaceToken token, TaskGraph* graph) = 0; |
120 | 143 |
121 // Wait for all scheduled tasks to finish running. | 144 // Wait for all scheduled tasks to finish running. |
122 void WaitForTasksToFinishRunning(NamespaceToken token); | 145 virtual void WaitForTasksToFinishRunning(NamespaceToken token) = 0; |
123 | 146 |
124 // Collect all completed tasks in |completed_tasks|. | 147 // Collect all completed tasks in |completed_tasks|. |
125 void CollectCompletedTasks(NamespaceToken token, | 148 virtual void CollectCompletedTasks(NamespaceToken token, |
126 Task::Vector* completed_tasks); | 149 Task::Vector* completed_tasks) = 0; |
127 | 150 |
128 // Run tasks until Shutdown() is called. | 151 protected: |
129 void Run(); | 152 virtual ~TaskGraphRunner() {} |
| 153 }; |
130 | 154 |
131 // Process all pending tasks, but don't wait/sleep. Return as soon as all | 155 // Helper class for iterating over all dependents of a task. |
132 // tasks that can be run are taken care of. | 156 class DependentIterator { |
133 void RunUntilIdle(); | 157 public: |
| 158 DependentIterator(TaskGraph* graph, const Task* task) |
| 159 : graph_(graph), |
| 160 task_(task), |
| 161 current_index_(static_cast<size_t>(-1)), |
| 162 current_node_(NULL) { |
| 163 ++(*this); |
| 164 } |
134 | 165 |
135 // Signals the Run method to return when it becomes idle. It will continue to | 166 TaskGraph::Node& operator->() const { |
136 // process tasks and future tasks as long as they are scheduled. | 167 DCHECK_LT(current_index_, graph_->edges.size()); |
137 // Warning: if the TaskGraphRunner remains busy, it may never quit. | 168 DCHECK_EQ(graph_->edges[current_index_].task, task_); |
138 void Shutdown(); | 169 DCHECK(current_node_); |
| 170 return *current_node_; |
| 171 } |
139 | 172 |
140 // Wait for all the tasks to finish running on all the namespaces. | 173 TaskGraph::Node& operator*() const { |
141 void FlushForTesting(); | 174 DCHECK_LT(current_index_, graph_->edges.size()); |
| 175 DCHECK_EQ(graph_->edges[current_index_].task, task_); |
| 176 DCHECK(current_node_); |
| 177 return *current_node_; |
| 178 } |
| 179 |
| 180 // Note: Performance can be improved by keeping edges sorted. |
| 181 DependentIterator& operator++() { |
| 182 // Find next dependency edge for |task_|. |
| 183 do { |
| 184 ++current_index_; |
| 185 if (current_index_ == graph_->edges.size()) |
| 186 return *this; |
| 187 } while (graph_->edges[current_index_].task != task_); |
| 188 |
| 189 // Now find the node for the dependent of this edge. |
| 190 TaskGraph::Node::Vector::iterator it = std::find_if( |
| 191 graph_->nodes.begin(), graph_->nodes.end(), |
| 192 [this](const TaskGraph::Node& node) { |
| 193 return node.task == graph_->edges[current_index_].dependent; |
| 194 }); |
| 195 DCHECK(it != graph_->nodes.end()); |
| 196 current_node_ = &(*it); |
| 197 |
| 198 return *this; |
| 199 } |
| 200 |
| 201 operator bool() const { return current_index_ < graph_->edges.size(); } |
142 | 202 |
143 private: | 203 private: |
144 struct PrioritizedTask { | 204 TaskGraph* graph_; |
145 typedef std::vector<PrioritizedTask> Vector; | 205 const Task* task_; |
146 | 206 size_t current_index_; |
147 PrioritizedTask(Task* task, size_t priority) | 207 TaskGraph::Node* current_node_; |
148 : task(task), priority(priority) {} | |
149 | |
150 Task* task; | |
151 size_t priority; | |
152 }; | |
153 | |
154 typedef std::vector<const Task*> TaskVector; | |
155 | |
156 struct TaskNamespace { | |
157 typedef std::vector<TaskNamespace*> Vector; | |
158 | |
159 TaskNamespace(); | |
160 ~TaskNamespace(); | |
161 | |
162 // Current task graph. | |
163 TaskGraph graph; | |
164 | |
165 // Ordered set of tasks that are ready to run. | |
166 PrioritizedTask::Vector ready_to_run_tasks; | |
167 | |
168 // Completed tasks not yet collected by origin thread. | |
169 Task::Vector completed_tasks; | |
170 | |
171 // This set contains all currently running tasks. | |
172 TaskVector running_tasks; | |
173 }; | |
174 | |
175 typedef std::map<int, TaskNamespace> TaskNamespaceMap; | |
176 | |
177 static bool CompareTaskPriority(const PrioritizedTask& a, | |
178 const PrioritizedTask& b) { | |
179 // In this system, numerically lower priority is run first. | |
180 return a.priority > b.priority; | |
181 } | |
182 | |
183 static bool CompareTaskNamespacePriority(const TaskNamespace* a, | |
184 const TaskNamespace* b) { | |
185 DCHECK(!a->ready_to_run_tasks.empty()); | |
186 DCHECK(!b->ready_to_run_tasks.empty()); | |
187 | |
188 // Compare based on task priority of the ready_to_run_tasks heap .front() | |
189 // will hold the max element of the heap, except after pop_heap, when max | |
190 // element is moved to .back(). | |
191 return CompareTaskPriority(a->ready_to_run_tasks.front(), | |
192 b->ready_to_run_tasks.front()); | |
193 } | |
194 | |
195 static bool HasFinishedRunningTasksInNamespace( | |
196 const TaskNamespace* task_namespace) { | |
197 return task_namespace->running_tasks.empty() && | |
198 task_namespace->ready_to_run_tasks.empty(); | |
199 } | |
200 | |
201 // Run next task. Caller must acquire |lock_| prior to calling this function | |
202 // and make sure at least one task is ready to run. | |
203 void RunTaskWithLockAcquired(); | |
204 | |
205 // This lock protects all members of this class. Do not read or modify | |
206 // anything without holding this lock. Do not block while holding this lock. | |
207 mutable base::Lock lock_; | |
208 | |
209 // Condition variable that is waited on by Run() until new tasks are ready to | |
210 // run or shutdown starts. | |
211 base::ConditionVariable has_ready_to_run_tasks_cv_; | |
212 | |
213 // Condition variable that is waited on by origin threads until a namespace | |
214 // has finished running all associated tasks. | |
215 base::ConditionVariable has_namespaces_with_finished_running_tasks_cv_; | |
216 | |
217 // Provides a unique id to each NamespaceToken. | |
218 int next_namespace_id_; | |
219 | |
220 // This set contains all namespaces with pending, running or completed tasks | |
221 // not yet collected. | |
222 TaskNamespaceMap namespaces_; | |
223 | |
224 // Ordered set of task namespaces that have ready to run tasks. | |
225 TaskNamespace::Vector ready_to_run_namespaces_; | |
226 | |
227 // Set during shutdown. Tells Run() to return when no more tasks are pending. | |
228 bool shutdown_; | |
229 | |
230 DISALLOW_COPY_AND_ASSIGN(TaskGraphRunner); | |
231 }; | 208 }; |
232 | 209 |
233 } // namespace cc | 210 } // namespace cc |
234 | 211 |
235 #endif // CC_RASTER_TASK_GRAPH_RUNNER_H_ | 212 #endif // CC_RASTER_TASK_GRAPH_RUNNER_H_ |
OLD | NEW |