| // Copyright 2014 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef CC_RESOURCES_TASK_GRAPH_RUNNER_H_ |
| #define CC_RESOURCES_TASK_GRAPH_RUNNER_H_ |
| |
| #include <map> |
| #include <vector> |
| |
| #include "base/logging.h" |
| #include "base/memory/ref_counted.h" |
| #include "base/synchronization/condition_variable.h" |
| #include "cc/base/cc_export.h" |
| |
| namespace cc { |
| |
| class CC_EXPORT Task : public base::RefCountedThreadSafe<Task> { |
| public: |
| typedef std::vector<scoped_refptr<Task> > Vector; |
| |
| virtual void RunOnWorkerThread() = 0; |
| |
| void WillRun(); |
| void DidRun(); |
| bool HasFinishedRunning() const; |
| |
| protected: |
| friend class base::RefCountedThreadSafe<Task>; |
| |
| Task(); |
| virtual ~Task(); |
| |
| bool will_run_; |
| bool did_run_; |
| }; |
| |
| // Dependencies are represented as edges in a task graph. Each graph node is |
| // assigned a priority and a run count that matches the number of dependencies. |
| // Priority range from 0 (most favorable scheduling) to UINT_MAX (least |
| // favorable). |
| struct CC_EXPORT TaskGraph { |
| struct Node { |
| class TaskComparator { |
| public: |
| explicit TaskComparator(const Task* task) : task_(task) {} |
| |
| bool operator()(const Node& node) const { return node.task == task_; } |
| |
| private: |
| const Task* task_; |
| }; |
| |
| typedef std::vector<Node> Vector; |
| |
| Node(Task* task, unsigned priority, size_t dependencies) |
| : task(task), priority(priority), dependencies(dependencies) {} |
| |
| Task* task; |
| unsigned priority; |
| size_t dependencies; |
| }; |
| |
| struct Edge { |
| typedef std::vector<Edge> Vector; |
| |
| Edge(const Task* task, Task* dependent) |
| : task(task), dependent(dependent) {} |
| |
| const Task* task; |
| Task* dependent; |
| }; |
| |
| TaskGraph(); |
| ~TaskGraph(); |
| |
| void Swap(TaskGraph* other); |
| void Reset(); |
| |
| Node::Vector nodes; |
| Edge::Vector edges; |
| }; |
| |
| class TaskGraphRunner; |
| |
| // Opaque identifier that defines a namespace of tasks. |
| class CC_EXPORT NamespaceToken { |
| public: |
| NamespaceToken() : id_(0) {} |
| ~NamespaceToken() {} |
| |
| bool IsValid() const { return id_ != 0; } |
| |
| private: |
| friend class TaskGraphRunner; |
| |
| explicit NamespaceToken(int id) : id_(id) {} |
| |
| int id_; |
| }; |
| |
| // A TaskGraphRunner is used to process tasks with dependencies. There can |
| // be any number of TaskGraphRunner instances per thread. Tasks can be scheduled |
| // from any thread and they can be run on any thread. |
| class CC_EXPORT TaskGraphRunner { |
| public: |
| TaskGraphRunner(); |
| virtual ~TaskGraphRunner(); |
| |
| // Returns a unique token that can be used to pass a task graph to |
| // ScheduleTasks(). Valid tokens are always nonzero. |
| NamespaceToken GetNamespaceToken(); |
| |
| // Schedule running of tasks in |graph|. Tasks previously scheduled but no |
| // longer needed will be canceled unless already running. Canceled tasks are |
| // moved to |completed_tasks| without being run. The result is that once |
| // scheduled, a task is guaranteed to end up in the |completed_tasks| queue |
| // even if it later gets canceled by another call to ScheduleTasks(). |
| void ScheduleTasks(NamespaceToken token, TaskGraph* graph); |
| |
| // Wait for all scheduled tasks to finish running. |
| void WaitForTasksToFinishRunning(NamespaceToken token); |
| |
| // Collect all completed tasks in |completed_tasks|. |
| void CollectCompletedTasks(NamespaceToken token, |
| Task::Vector* completed_tasks); |
| |
| // Run tasks until Shutdown() is called. |
| void Run(); |
| |
| // Process all pending tasks, but don't wait/sleep. Return as soon as all |
| // tasks that can be run are taken care of. |
| void RunUntilIdle(); |
| |
| // Signals the Run method to return when it becomes idle. It will continue to |
| // process tasks and future tasks as long as they are scheduled. |
| // Warning: if the TaskGraphRunner remains busy, it may never quit. |
| void Shutdown(); |
| |
| private: |
| struct PrioritizedTask { |
| typedef std::vector<PrioritizedTask> Vector; |
| |
| PrioritizedTask(Task* task, unsigned priority) |
| : task(task), priority(priority) {} |
| |
| Task* task; |
| unsigned priority; |
| }; |
| |
| typedef std::vector<const Task*> TaskVector; |
| |
| struct TaskNamespace { |
| typedef std::vector<TaskNamespace*> Vector; |
| |
| TaskNamespace(); |
| ~TaskNamespace(); |
| |
| // Current task graph. |
| TaskGraph graph; |
| |
| // Ordered set of tasks that are ready to run. |
| PrioritizedTask::Vector ready_to_run_tasks; |
| |
| // Completed tasks not yet collected by origin thread. |
| Task::Vector completed_tasks; |
| |
| // This set contains all currently running tasks. |
| TaskVector running_tasks; |
| }; |
| |
| typedef std::map<int, TaskNamespace> TaskNamespaceMap; |
| |
| static bool CompareTaskPriority(const PrioritizedTask& a, |
| const PrioritizedTask& b) { |
| // In this system, numerically lower priority is run first. |
| return a.priority > b.priority; |
| } |
| |
| static bool CompareTaskNamespacePriority(const TaskNamespace* a, |
| const TaskNamespace* b) { |
| DCHECK(!a->ready_to_run_tasks.empty()); |
| DCHECK(!b->ready_to_run_tasks.empty()); |
| |
| // Compare based on task priority of the ready_to_run_tasks heap .front() |
| // will hold the max element of the heap, except after pop_heap, when max |
| // element is moved to .back(). |
| return CompareTaskPriority(a->ready_to_run_tasks.front(), |
| b->ready_to_run_tasks.front()); |
| } |
| |
| static bool HasFinishedRunningTasksInNamespace( |
| const TaskNamespace* task_namespace) { |
| return task_namespace->running_tasks.empty() && |
| task_namespace->ready_to_run_tasks.empty(); |
| } |
| |
| // Run next task. Caller must acquire |lock_| prior to calling this function |
| // and make sure at least one task is ready to run. |
| void RunTaskWithLockAcquired(); |
| |
| // This lock protects all members of this class. Do not read or modify |
| // anything without holding this lock. Do not block while holding this lock. |
| mutable base::Lock lock_; |
| |
| // Condition variable that is waited on by Run() until new tasks are ready to |
| // run or shutdown starts. |
| base::ConditionVariable has_ready_to_run_tasks_cv_; |
| |
| // Condition variable that is waited on by origin threads until a namespace |
| // has finished running all associated tasks. |
| base::ConditionVariable has_namespaces_with_finished_running_tasks_cv_; |
| |
| // Provides a unique id to each NamespaceToken. |
| int next_namespace_id_; |
| |
| // This set contains all namespaces with pending, running or completed tasks |
| // not yet collected. |
| TaskNamespaceMap namespaces_; |
| |
| // Ordered set of task namespaces that have ready to run tasks. |
| TaskNamespace::Vector ready_to_run_namespaces_; |
| |
| // Set during shutdown. Tells Run() to return when no more tasks are pending. |
| bool shutdown_; |
| |
| DISALLOW_COPY_AND_ASSIGN(TaskGraphRunner); |
| }; |
| |
| } // namespace cc |
| |
| #endif // CC_RESOURCES_TASK_GRAPH_RUNNER_H_ |