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 3 // found in the LICENSE file. 4 5 #ifndef CC_RESOURCES_TASK_GRAPH_RUNNER_H_ 6 #define CC_RESOURCES_TASK_GRAPH_RUNNER_H_ 7 8 #include <map> 9 #include <vector> 10 11 #include "base/logging.h" 12 #include "base/memory/ref_counted.h" 13 #include "base/synchronization/condition_variable.h" 14 #include "cc/base/cc_export.h" 15 16 namespace cc { 17 18 class CC_EXPORT Task : public base::RefCountedThreadSafe<Task> { 19 public: 20 typedef std::vector<scoped_refptr<Task> > Vector; 21 22 virtual void RunOnWorkerThread() = 0; 23 24 void WillRun(); 25 void DidRun(); 26 bool HasFinishedRunning() const; 27 28 protected: 29 friend class base::RefCountedThreadSafe<Task>; 30 31 Task(); 32 virtual ~Task(); 33 34 bool will_run_; 35 bool did_run_; 36 }; 37 38 // Dependencies are represented as edges in a task graph. Each graph node is 39 // assigned a priority and a run count that matches the number of dependencies. 40 // Priority range from 0 (most favorable scheduling) to UINT_MAX (least 41 // favorable). 42 struct CC_EXPORT TaskGraph { 43 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; 55 56 Node(Task* task, unsigned priority, size_t dependencies) 57 : task(task), priority(priority), dependencies(dependencies) {} 58 59 Task* task; 60 unsigned priority; 61 size_t dependencies; 62 }; 63 64 struct Edge { 65 typedef std::vector<Edge> Vector; 66 67 Edge(const Task* task, Task* dependent) 68 : task(task), dependent(dependent) {} 69 70 const Task* task; 71 Task* dependent; 72 }; 73 74 TaskGraph(); 75 ~TaskGraph(); 76 77 void Swap(TaskGraph* other); 78 void Reset(); 79 80 Node::Vector nodes; 81 Edge::Vector edges; 82 }; 83 84 class TaskGraphRunner; 85 86 // Opaque identifier that defines a namespace of tasks. 87 class CC_EXPORT NamespaceToken { 88 public: 89 NamespaceToken() : id_(0) {} 90 ~NamespaceToken() {} 91 92 bool IsValid() const { return id_ != 0; } 93 94 private: 95 friend class TaskGraphRunner; 96 97 explicit NamespaceToken(int id) : id_(id) {} 98 99 int id_; 100 }; 101 102 // A TaskGraphRunner is used to process tasks with dependencies. There can 103 // be any number of TaskGraphRunner instances per thread. Tasks can be scheduled 104 // from any thread and they can be run on any thread. 105 class CC_EXPORT TaskGraphRunner { 106 public: 107 TaskGraphRunner(); 108 virtual ~TaskGraphRunner(); 109 110 // Returns a unique token that can be used to pass a task graph to 111 // ScheduleTasks(). Valid tokens are always nonzero. 112 NamespaceToken GetNamespaceToken(); 113 114 // Schedule running of tasks in |graph|. Tasks previously scheduled but no 115 // longer needed will be canceled unless already running. Canceled tasks are 116 // 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 118 // even if it later gets canceled by another call to ScheduleTasks(). 119 void ScheduleTasks(NamespaceToken token, TaskGraph* graph); 120 121 // Wait for all scheduled tasks to finish running. 122 void WaitForTasksToFinishRunning(NamespaceToken token); 123 124 // Collect all completed tasks in |completed_tasks|. 125 void CollectCompletedTasks(NamespaceToken token, 126 Task::Vector* completed_tasks); 127 128 // Run tasks until Shutdown() is called. 129 void Run(); 130 131 // Process all pending tasks, but don't wait/sleep. Return as soon as all 132 // tasks that can be run are taken care of. 133 void RunUntilIdle(); 134 135 // Signals the Run method to return when it becomes idle. It will continue to 136 // process tasks and future tasks as long as they are scheduled. 137 // Warning: if the TaskGraphRunner remains busy, it may never quit. 138 void Shutdown(); 139 140 private: 141 struct PrioritizedTask { 142 typedef std::vector<PrioritizedTask> Vector; 143 144 PrioritizedTask(Task* task, unsigned priority) 145 : task(task), priority(priority) {} 146 147 Task* task; 148 unsigned priority; 149 }; 150 151 typedef std::vector<const Task*> TaskVector; 152 153 struct TaskNamespace { 154 typedef std::vector<TaskNamespace*> Vector; 155 156 TaskNamespace(); 157 ~TaskNamespace(); 158 159 // Current task graph. 160 TaskGraph graph; 161 162 // Ordered set of tasks that are ready to run. 163 PrioritizedTask::Vector ready_to_run_tasks; 164 165 // Completed tasks not yet collected by origin thread. 166 Task::Vector completed_tasks; 167 168 // This set contains all currently running tasks. 169 TaskVector running_tasks; 170 }; 171 172 typedef std::map<int, TaskNamespace> TaskNamespaceMap; 173 174 static bool CompareTaskPriority(const PrioritizedTask& a, 175 const PrioritizedTask& b) { 176 // In this system, numerically lower priority is run first. 177 return a.priority > b.priority; 178 } 179 180 static bool CompareTaskNamespacePriority(const TaskNamespace* a, 181 const TaskNamespace* b) { 182 DCHECK(!a->ready_to_run_tasks.empty()); 183 DCHECK(!b->ready_to_run_tasks.empty()); 184 185 // Compare based on task priority of the ready_to_run_tasks heap .front() 186 // will hold the max element of the heap, except after pop_heap, when max 187 // element is moved to .back(). 188 return CompareTaskPriority(a->ready_to_run_tasks.front(), 189 b->ready_to_run_tasks.front()); 190 } 191 192 static bool HasFinishedRunningTasksInNamespace( 193 const TaskNamespace* task_namespace) { 194 return task_namespace->running_tasks.empty() && 195 task_namespace->ready_to_run_tasks.empty(); 196 } 197 198 // Run next task. Caller must acquire |lock_| prior to calling this function 199 // and make sure at least one task is ready to run. 200 void RunTaskWithLockAcquired(); 201 202 // This lock protects all members of this class. Do not read or modify 203 // anything without holding this lock. Do not block while holding this lock. 204 mutable base::Lock lock_; 205 206 // Condition variable that is waited on by Run() until new tasks are ready to 207 // run or shutdown starts. 208 base::ConditionVariable has_ready_to_run_tasks_cv_; 209 210 // Condition variable that is waited on by origin threads until a namespace 211 // has finished running all associated tasks. 212 base::ConditionVariable has_namespaces_with_finished_running_tasks_cv_; 213 214 // Provides a unique id to each NamespaceToken. 215 int next_namespace_id_; 216 217 // This set contains all namespaces with pending, running or completed tasks 218 // not yet collected. 219 TaskNamespaceMap namespaces_; 220 221 // Ordered set of task namespaces that have ready to run tasks. 222 TaskNamespace::Vector ready_to_run_namespaces_; 223 224 // Set during shutdown. Tells Run() to return when no more tasks are pending. 225 bool shutdown_; 226 227 DISALLOW_COPY_AND_ASSIGN(TaskGraphRunner); 228 }; 229 230 } // namespace cc 231 232 #endif // CC_RESOURCES_TASK_GRAPH_RUNNER_H_ 233