src/cc/resources/task_graph_runner.h

   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 <string>
  10 #include <vector>
  11
  12 #include "base/memory/ref_counted.h"
  13 #include "base/synchronization/condition_variable.h"
  14 #include "base/threading/simple_thread.h"
  15 #include "cc/base/cc_export.h"
  16 #include "cc/base/scoped_ptr_deque.h"
  17
  18 namespace cc {
  19 namespace internal {
  20
  21 class CC_EXPORT Task : public base::RefCountedThreadSafe<Task> {
  22  public:
  23   typedef std::vector<scoped_refptr<Task> > Vector;
  24
  25   virtual void RunOnWorkerThread(unsigned thread_index) = 0;
  26
  27   void WillRun();
  28   void DidRun();
  29   bool HasFinishedRunning() const;
  30
  31  protected:
  32   friend class base::RefCountedThreadSafe<Task>;
  33
  34   Task();
  35   virtual ~Task();
  36
  37   bool did_run_;
  38 };
  39
  40 // Dependencies are represented as edges in a task graph. Each graph node
  41 // is assigned a priority and a run count that matches the number of
  42 // dependencies.
  43 struct CC_EXPORT TaskGraph {
  44   struct Node {
  45     class TaskComparator {
  46      public:
  47       explicit TaskComparator(const Task* task) : task_(task) {}
  48
  49       bool operator()(const Node& node) const { return node.task == task_; }
  50
  51      private:
  52       const Task* task_;
  53     };
  54
  55     typedef std::vector<Node> Vector;
  56
  57     Node(Task* task, unsigned priority, size_t dependencies)
  58         : task(task), priority(priority), dependencies(dependencies) {}
  59
  60     Task* task;
  61     unsigned priority;
  62     size_t dependencies;
  63   };
  64
  65   struct Edge {
  66     typedef std::vector<Edge> Vector;
  67
  68     Edge(const Task* task, Task* dependent)
  69         : task(task), dependent(dependent) {}
  70
  71     const Task* task;
  72     Task* dependent;
  73   };
  74
  75   TaskGraph();
  76   ~TaskGraph();
  77
  78   void Swap(TaskGraph* other);
  79   void Reset();
  80
  81   Node::Vector nodes;
  82   Edge::Vector edges;
  83 };
  84
  85 class TaskGraphRunner;
  86
  87 // Opaque identifier that defines a namespace of tasks.
  88 class CC_EXPORT NamespaceToken {
  89  public:
  90   NamespaceToken() : id_(0) {}
  91   ~NamespaceToken() {}
  92
  93   bool IsValid() const { return id_ != 0; }
  94
  95  private:
  96   friend class TaskGraphRunner;
  97
  98   explicit NamespaceToken(int id) : id_(id) {}
  99
 100   int id_;
 101 };
 102
 103 // A worker thread pool that runs tasks provided by task graph. Destructor
 104 // might block and should not be used on a thread that needs to be responsive.
 105 class CC_EXPORT TaskGraphRunner : public base::DelegateSimpleThread::Delegate {
 106  public:
 107   TaskGraphRunner(size_t num_threads, const std::string& thread_name_prefix);
 108   virtual ~TaskGraphRunner();
 109
 110   // Returns a unique token that can be used to pass a task graph to
 111   // SetTaskGraph(). Valid tokens are always nonzero.
 112   NamespaceToken GetNamespaceToken();
 113
 114   // Schedule running of tasks in |graph|. Tasks previously scheduled but
 115   // no longer needed will be canceled unless already running. Canceled
 116   // tasks are moved to |completed_tasks| without being run. The result
 117   // is that once scheduled, a task is guaranteed to end up in the
 118   // |completed_tasks| queue even if it later gets canceled by another
 119   // call to SetTaskGraph().
 120   void SetTaskGraph(NamespaceToken token, TaskGraph* graph);
 121
 122   // Wait for all scheduled tasks to finish running.
 123   void WaitForTasksToFinishRunning(NamespaceToken token);
 124
 125   // Collect all completed tasks in |completed_tasks|.
 126   void CollectCompletedTasks(NamespaceToken token,
 127                              Task::Vector* completed_tasks);
 128
 129   // Run one task on current thread. Returns false if no tasks are ready
 130   // to run. This should only be used by tests.
 131   bool RunTaskForTesting();
 132
 133  private:
 134   struct PrioritizedTask {
 135     typedef std::vector<PrioritizedTask> Vector;
 136
 137     PrioritizedTask(Task* task, unsigned priority)
 138         : task(task), priority(priority) {}
 139
 140     Task* task;
 141     unsigned priority;
 142   };
 143
 144   struct TaskNamespace {
 145     typedef std::vector<TaskNamespace*> Vector;
 146
 147     TaskNamespace();
 148     ~TaskNamespace();
 149
 150     // Current task graph.
 151     TaskGraph graph;
 152
 153     // Ordered set of tasks that are ready to run.
 154     PrioritizedTask::Vector ready_to_run_tasks;
 155
 156     // Completed tasks not yet collected by origin thread.
 157     Task::Vector completed_tasks;
 158
 159     // Number of currently running tasks.
 160     size_t num_running_tasks;
 161   };
 162
 163   typedef std::map<int, TaskNamespace> TaskNamespaceMap;
 164
 165   static bool CompareTaskPriority(const PrioritizedTask& a,
 166                                   const PrioritizedTask& b) {
 167     // In this system, numerically lower priority is run first.
 168     return a.priority > b.priority;
 169   }
 170
 171   static bool CompareTaskNamespacePriority(const TaskNamespace* a,
 172                                            const TaskNamespace* b) {
 173     DCHECK(!a->ready_to_run_tasks.empty());
 174     DCHECK(!b->ready_to_run_tasks.empty());
 175
 176     // Compare based on task priority of the ready_to_run_tasks heap
 177     // .front() will hold the max element of the heap,
 178     // except after pop_heap, when max element is moved to .back().
 179     return CompareTaskPriority(a->ready_to_run_tasks.front(),
 180                                b->ready_to_run_tasks.front());
 181   }
 182
 183   static bool HasFinishedRunningTasksInNamespace(
 184       const TaskNamespace* task_namespace) {
 185     return !task_namespace->num_running_tasks &&
 186            task_namespace->ready_to_run_tasks.empty();
 187   }
 188
 189   // Overridden from base::DelegateSimpleThread:
 190   virtual void Run() OVERRIDE;
 191
 192   // Run next task. Caller must acquire |lock_| prior to calling this
 193   // function and make sure at least one task is ready to run.
 194   void RunTaskWithLockAcquired(int thread_index);
 195
 196   // This lock protects all members of this class. Do not read or modify
 197   // anything without holding this lock. Do not block while holding this
 198   // lock.
 199   mutable base::Lock lock_;
 200
 201   // Condition variable that is waited on by worker threads until new
 202   // tasks are ready to run or shutdown starts.
 203   base::ConditionVariable has_ready_to_run_tasks_cv_;
 204
 205   // Condition variable that is waited on by origin threads until a
 206   // namespace has finished running all associated tasks.
 207   base::ConditionVariable has_namespaces_with_finished_running_tasks_cv_;
 208
 209   // Provides a unique id to each NamespaceToken.
 210   int next_namespace_id_;
 211
 212   // This set contains all namespaces with pending, running or completed
 213   // tasks not yet collected.
 214   TaskNamespaceMap namespaces_;
 215
 216   // Ordered set of task namespaces that have ready to run tasks.
 217   TaskNamespace::Vector ready_to_run_namespaces_;
 218
 219   // Provides each running thread loop with a unique index. First thread
 220   // loop index is 0.
 221   unsigned next_thread_index_;
 222
 223   // This set contains all currently running tasks.
 224   typedef std::vector<const Task*> TaskVector;
 225   TaskVector running_tasks_;
 226
 227   // Set during shutdown. Tells workers to exit when no more tasks
 228   // are pending.
 229   bool shutdown_;
 230
 231   ScopedPtrDeque<base::DelegateSimpleThread> workers_;
 232
 233   DISALLOW_COPY_AND_ASSIGN(TaskGraphRunner);
 234 };
 235
 236 }  // namespace internal
 237 }  // namespace cc
 238
 239 #endif  // CC_RESOURCES_TASK_GRAPH_RUNNER_H_