cc/raster/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_RASTER_TASK_GRAPH_RUNNER_H_
   6 #define CC_RASTER_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, size_t priority, size_t dependencies)
  57         : task(task), priority(priority), dependencies(dependencies) {}
  58
  59     Task* task;
  60     size_t 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   // Wait for all the tasks to finish running on all the namespaces.
 141   void FlushForTesting();
 142
 143  private:
 144   struct PrioritizedTask {
 145     typedef std::vector<PrioritizedTask> Vector;
 146
 147     PrioritizedTask(Task* task, size_t priority)
 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 };
 232
 233 }  // namespace cc
 234
 235 #endif  // CC_RASTER_TASK_GRAPH_RUNNER_H_