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 <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_