15d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Copyright 2014 The Chromium Authors. All rights reserved. 25d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// found in the LICENSE file. 45d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 55d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "cc/resources/task_graph_runner.h" 65d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 75d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include <algorithm> 85d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 95d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "base/debug/trace_event.h" 105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "base/strings/stringprintf.h" 115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "base/threading/thread_restrictions.h" 125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)namespace cc { 145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)namespace { 155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Helper class for iterating over all dependents of a task. 175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)class DependentIterator { 185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) public: 195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DependentIterator(TaskGraph* graph, const Task* task) 20116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch : graph_(graph), 21116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch task_(task), 22116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch current_index_(static_cast<size_t>(-1)), 23116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch current_node_(NULL) { 245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ++(*this); 255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskGraph::Node& operator->() const { 285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LT(current_index_, graph_->edges.size()); 295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(graph_->edges[current_index_].task, task_); 305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(current_node_); 315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return *current_node_; 325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskGraph::Node& operator*() const { 355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LT(current_index_, graph_->edges.size()); 365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(graph_->edges[current_index_].task, task_); 375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(current_node_); 385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return *current_node_; 395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Note: Performance can be improved by keeping edges sorted. 425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DependentIterator& operator++() { 435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Find next dependency edge for |task_|. 445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) do { 455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ++current_index_; 465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (current_index_ == graph_->edges.size()) 475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return *this; 485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } while (graph_->edges[current_index_].task != task_); 495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Now find the node for the dependent of this edge. 515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskGraph::Node::Vector::iterator it = 525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::find_if(graph_->nodes.begin(), 535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) graph_->nodes.end(), 545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskGraph::Node::TaskComparator( 555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) graph_->edges[current_index_].dependent)); 565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(it != graph_->nodes.end()); 575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) current_node_ = &(*it); 585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return *this; 605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) operator bool() const { return current_index_ < graph_->edges.size(); } 635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) private: 655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskGraph* graph_; 665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const Task* task_; 675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) size_t current_index_; 685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskGraph::Node* current_node_; 695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)}; 705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)class DependencyMismatchComparator { 725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) public: 735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) explicit DependencyMismatchComparator(const TaskGraph* graph) 745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) : graph_(graph) {} 755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool operator()(const TaskGraph::Node& node) const { 775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return static_cast<size_t>(std::count_if(graph_->edges.begin(), 785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) graph_->edges.end(), 795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DependentComparator(node.task))) != 805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) node.dependencies; 815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) private: 845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) class DependentComparator { 855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) public: 865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) explicit DependentComparator(const Task* dependent) 875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) : dependent_(dependent) {} 885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool operator()(const TaskGraph::Edge& edge) const { 905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return edge.dependent == dependent_; 915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) private: 945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const Task* dependent_; 955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) }; 965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const TaskGraph* graph_; 985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)}; 995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} // namespace 1015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1020529e5d033099cbfc42635f6f6183833b09dff6eBen MurdochTask::Task() : will_run_(false), did_run_(false) { 1030529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch} 1045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1050529e5d033099cbfc42635f6f6183833b09dff6eBen MurdochTask::~Task() { 1060529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch DCHECK(!will_run_); 1070529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch} 1085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void Task::WillRun() { 1100529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch DCHECK(!will_run_); 1115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(!did_run_); 1120529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch will_run_ = true; 1135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1150529e5d033099cbfc42635f6f6183833b09dff6eBen Murdochvoid Task::DidRun() { 1160529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch DCHECK(will_run_); 1170529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch will_run_ = false; 1180529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch did_run_ = true; 1190529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch} 1205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)bool Task::HasFinishedRunning() const { return did_run_; } 1225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)TaskGraph::TaskGraph() {} 1245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)TaskGraph::~TaskGraph() {} 1265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void TaskGraph::Swap(TaskGraph* other) { 1285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) nodes.swap(other->nodes); 1295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) edges.swap(other->edges); 1305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void TaskGraph::Reset() { 1335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) nodes.clear(); 1345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) edges.clear(); 1355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 137a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)TaskGraphRunner::TaskNamespace::TaskNamespace() {} 1385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)TaskGraphRunner::TaskNamespace::~TaskNamespace() {} 1405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 141a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)TaskGraphRunner::TaskGraphRunner() 1425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) : lock_(), 1435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) has_ready_to_run_tasks_cv_(&lock_), 1445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) has_namespaces_with_finished_running_tasks_cv_(&lock_), 1455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) next_namespace_id_(1), 146a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) shutdown_(false) {} 1475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)TaskGraphRunner::~TaskGraphRunner() { 1495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) { 1505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::AutoLock lock(lock_); 1515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(0u, ready_to_run_namespaces_.size()); 1535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(0u, namespaces_.size()); 1545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 1555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)NamespaceToken TaskGraphRunner::GetNamespaceToken() { 1585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::AutoLock lock(lock_); 1595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) NamespaceToken token(next_namespace_id_++); 1615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(namespaces_.find(token.id_) == namespaces_.end()); 1625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return token; 1635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 165a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void TaskGraphRunner::ScheduleTasks(NamespaceToken token, TaskGraph* graph) { 1665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TRACE_EVENT2("cc", 167a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) "TaskGraphRunner::ScheduleTasks", 1685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) "num_nodes", 1695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) graph->nodes.size(), 1705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) "num_edges", 1715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) graph->edges.size()); 1725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(token.IsValid()); 1745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(std::find_if(graph->nodes.begin(), 1755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) graph->nodes.end(), 1765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DependencyMismatchComparator(graph)) == 1775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) graph->nodes.end()); 1785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) { 1805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::AutoLock lock(lock_); 1815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(!shutdown_); 1835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskNamespace& task_namespace = namespaces_[token.id_]; 1855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // First adjust number of dependencies to reflect completed tasks. 1875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (Task::Vector::iterator it = task_namespace.completed_tasks.begin(); 1885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) it != task_namespace.completed_tasks.end(); 1895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ++it) { 1905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (DependentIterator node_it(graph, it->get()); node_it; ++node_it) { 1915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskGraph::Node& node = *node_it; 1925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LT(0u, node.dependencies); 1935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) node.dependencies--; 1945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 1955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 1965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Build new "ready to run" queue and remove nodes from old graph. 1985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task_namespace.ready_to_run_tasks.clear(); 1995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (TaskGraph::Node::Vector::iterator it = graph->nodes.begin(); 2005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) it != graph->nodes.end(); 2015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ++it) { 2025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskGraph::Node& node = *it; 2035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Remove any old nodes that are associated with this task. The result is 205a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // that the old graph is left with all nodes not present in this graph, 206a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // which we use below to determine what tasks need to be canceled. 2075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskGraph::Node::Vector::iterator old_it = 2085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::find_if(task_namespace.graph.nodes.begin(), 2095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task_namespace.graph.nodes.end(), 2105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskGraph::Node::TaskComparator(node.task)); 2115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (old_it != task_namespace.graph.nodes.end()) { 2125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::swap(*old_it, task_namespace.graph.nodes.back()); 2135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task_namespace.graph.nodes.pop_back(); 2145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 2155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Task is not ready to run if dependencies are not yet satisfied. 2175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (node.dependencies) 2185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 2195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Skip if already finished running task. 2215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (node.task->HasFinishedRunning()) 2225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 2235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Skip if already running. 225a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (std::find(task_namespace.running_tasks.begin(), 226a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) task_namespace.running_tasks.end(), 227a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) node.task) != task_namespace.running_tasks.end()) 2285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 2295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task_namespace.ready_to_run_tasks.push_back( 2315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) PrioritizedTask(node.task, node.priority)); 2325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 2335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 234a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Rearrange the elements in |ready_to_run_tasks| in such a way that they 235a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // form a heap. 2365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::make_heap(task_namespace.ready_to_run_tasks.begin(), 2375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task_namespace.ready_to_run_tasks.end(), 2385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) CompareTaskPriority); 2395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Swap task graph. 2415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task_namespace.graph.Swap(graph); 2425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Determine what tasks in old graph need to be canceled. 2445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (TaskGraph::Node::Vector::iterator it = graph->nodes.begin(); 2455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) it != graph->nodes.end(); 2465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ++it) { 2475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskGraph::Node& node = *it; 2485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Skip if already finished running task. 2505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (node.task->HasFinishedRunning()) 2515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 2525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Skip if already running. 254a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (std::find(task_namespace.running_tasks.begin(), 255a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) task_namespace.running_tasks.end(), 256a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) node.task) != task_namespace.running_tasks.end()) 2575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 2585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(std::find(task_namespace.completed_tasks.begin(), 2605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task_namespace.completed_tasks.end(), 2615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) node.task) == task_namespace.completed_tasks.end()); 2625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task_namespace.completed_tasks.push_back(node.task); 2635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 2645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Build new "ready to run" task namespaces queue. 2665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ready_to_run_namespaces_.clear(); 2675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (TaskNamespaceMap::iterator it = namespaces_.begin(); 2685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) it != namespaces_.end(); 2695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ++it) { 2705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!it->second.ready_to_run_tasks.empty()) 2715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ready_to_run_namespaces_.push_back(&it->second); 2725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 2735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 274a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Rearrange the task namespaces in |ready_to_run_namespaces_| in such a way 275a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // that they form a heap. 2765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::make_heap(ready_to_run_namespaces_.begin(), 2775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ready_to_run_namespaces_.end(), 2785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) CompareTaskNamespacePriority); 2795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 2805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // If there is more work available, wake up worker thread. 2815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!ready_to_run_namespaces_.empty()) 2825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) has_ready_to_run_tasks_cv_.Signal(); 2835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 2845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 2855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 286a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void TaskGraphRunner::WaitForTasksToFinishRunning(NamespaceToken token) { 287a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) TRACE_EVENT0("cc", "TaskGraphRunner::WaitForTasksToFinishRunning"); 288a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 289a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DCHECK(token.IsValid()); 290a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 291a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) { 292a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) base::AutoLock lock(lock_); 293a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 294a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) TaskNamespaceMap::const_iterator it = namespaces_.find(token.id_); 295a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) if (it == namespaces_.end()) 296a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) return; 297a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 298a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) const TaskNamespace& task_namespace = it->second; 299a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 300a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) while (!HasFinishedRunningTasksInNamespace(&task_namespace)) 301a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) has_namespaces_with_finished_running_tasks_cv_.Wait(); 302a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 303a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // There may be other namespaces that have finished running tasks, so wake 304a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // up another origin thread. 305a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) has_namespaces_with_finished_running_tasks_cv_.Signal(); 306a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) } 307a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 308a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 3095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void TaskGraphRunner::CollectCompletedTasks(NamespaceToken token, 3105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) Task::Vector* completed_tasks) { 3115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TRACE_EVENT0("cc", "TaskGraphRunner::CollectCompletedTasks"); 3125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(token.IsValid()); 3145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) { 3165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::AutoLock lock(lock_); 3175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskNamespaceMap::iterator it = namespaces_.find(token.id_); 3195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (it == namespaces_.end()) 3205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return; 3215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskNamespace& task_namespace = it->second; 3235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(0u, completed_tasks->size()); 3255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) completed_tasks->swap(task_namespace.completed_tasks); 3265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!HasFinishedRunningTasksInNamespace(&task_namespace)) 3275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return; 3285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Remove namespace if finished running tasks. 3305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(0u, task_namespace.completed_tasks.size()); 3315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_EQ(0u, task_namespace.ready_to_run_tasks.size()); 332a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DCHECK_EQ(0u, task_namespace.running_tasks.size()); 3335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) namespaces_.erase(it); 3345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 3355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 337a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void TaskGraphRunner::Shutdown() { 3385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::AutoLock lock(lock_); 3395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 340a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DCHECK_EQ(0u, ready_to_run_namespaces_.size()); 341a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DCHECK_EQ(0u, namespaces_.size()); 3425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 343a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DCHECK(!shutdown_); 344a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) shutdown_ = true; 345a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 346a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Wake up a worker so it knows it should exit. This will cause all workers 347a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // to exit as each will wake up another worker before exiting. 348a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) has_ready_to_run_tasks_cv_.Signal(); 3495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void TaskGraphRunner::Run() { 3525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::AutoLock lock(lock_); 3535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) while (true) { 3555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (ready_to_run_namespaces_.empty()) { 3565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Exit when shutdown is set and no more tasks are pending. 3575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (shutdown_) 3585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) break; 3595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Wait for more tasks. 3615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) has_ready_to_run_tasks_cv_.Wait(); 3625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) continue; 3635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 3645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 365a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) RunTaskWithLockAcquired(); 3665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 3675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // We noticed we should exit. Wake up the next worker so it knows it should 3695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // exit as well (because the Shutdown() code only signals once). 3705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) has_ready_to_run_tasks_cv_.Signal(); 3715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 3725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 373a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void TaskGraphRunner::RunUntilIdle() { 374a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) base::AutoLock lock(lock_); 375a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 376a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) while (!ready_to_run_namespaces_.empty()) 377a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) RunTaskWithLockAcquired(); 378a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)} 379a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) 380a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)void TaskGraphRunner::RunTaskWithLockAcquired() { 38123730a6e56a168d1879203e4b3819bb36e3d8f1fTorne (Richard Coles) TRACE_EVENT0("toplevel", "TaskGraphRunner::RunTask"); 3825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) lock_.AssertAcquired(); 3845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(!ready_to_run_namespaces_.empty()); 3855d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Take top priority TaskNamespace from |ready_to_run_namespaces_|. 3875d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::pop_heap(ready_to_run_namespaces_.begin(), 3885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ready_to_run_namespaces_.end(), 3895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) CompareTaskNamespacePriority); 3905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskNamespace* task_namespace = ready_to_run_namespaces_.back(); 3915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ready_to_run_namespaces_.pop_back(); 3925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(!task_namespace->ready_to_run_tasks.empty()); 3935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 3945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Take top priority task from |ready_to_run_tasks|. 3955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::pop_heap(task_namespace->ready_to_run_tasks.begin(), 3965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task_namespace->ready_to_run_tasks.end(), 3975d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) CompareTaskPriority); 3985d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) scoped_refptr<Task> task(task_namespace->ready_to_run_tasks.back().task); 3995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task_namespace->ready_to_run_tasks.pop_back(); 4005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 401a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Add task namespace back to |ready_to_run_namespaces_| if not empty after 402a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // taking top priority task. 4035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!task_namespace->ready_to_run_tasks.empty()) { 4045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ready_to_run_namespaces_.push_back(task_namespace); 4055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::push_heap(ready_to_run_namespaces_.begin(), 4065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ready_to_run_namespaces_.end(), 4075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) CompareTaskNamespacePriority); 4085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 4095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 410a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Add task to |running_tasks|. 411a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) task_namespace->running_tasks.push_back(task.get()); 4125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // There may be more work available, so wake up another worker thread. 4145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) has_ready_to_run_tasks_cv_.Signal(); 4155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Call WillRun() before releasing |lock_| and running task. 4175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task->WillRun(); 4185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) { 4205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::AutoUnlock unlock(lock_); 4215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 422a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) task->RunOnWorkerThread(); 4235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 4245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // This will mark task as finished running. 4265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task->DidRun(); 4275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 428a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) // Remove task from |running_tasks|. 429a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) TaskVector::iterator it = std::find(task_namespace->running_tasks.begin(), 430a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) task_namespace->running_tasks.end(), 431a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) task.get()); 432a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) DCHECK(it != task_namespace->running_tasks.end()); 433a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) std::swap(*it, task_namespace->running_tasks.back()); 434a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles) task_namespace->running_tasks.pop_back(); 4355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Now iterate over all dependents to decrement dependencies and check if they 4375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // are ready to run. 4385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool ready_to_run_namespaces_has_heap_properties = true; 4395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (DependentIterator it(&task_namespace->graph, task.get()); it; ++it) { 4405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) TaskGraph::Node& dependent_node = *it; 4415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LT(0u, dependent_node.dependencies); 4435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) dependent_node.dependencies--; 4445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Task is ready if it has no dependencies. Add it to |ready_to_run_tasks_|. 4455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!dependent_node.dependencies) { 4465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) bool was_empty = task_namespace->ready_to_run_tasks.empty(); 4475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task_namespace->ready_to_run_tasks.push_back( 4485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) PrioritizedTask(dependent_node.task, dependent_node.priority)); 4495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::push_heap(task_namespace->ready_to_run_tasks.begin(), 4505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task_namespace->ready_to_run_tasks.end(), 4515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) CompareTaskPriority); 4525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Task namespace is ready if it has at least one ready to run task. Add 4535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // it to |ready_to_run_namespaces_| if it just become ready. 4545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (was_empty) { 4555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK(std::find(ready_to_run_namespaces_.begin(), 4565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ready_to_run_namespaces_.end(), 4575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task_namespace) == ready_to_run_namespaces_.end()); 4585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ready_to_run_namespaces_.push_back(task_namespace); 4595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 4605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ready_to_run_namespaces_has_heap_properties = false; 4615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 4625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 4635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Rearrange the task namespaces in |ready_to_run_namespaces_| in such a way 4655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // that they yet again form a heap. 4665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (!ready_to_run_namespaces_has_heap_properties) { 4675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::make_heap(ready_to_run_namespaces_.begin(), 4685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) ready_to_run_namespaces_.end(), 4695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) CompareTaskNamespacePriority); 4705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 4715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Finally add task to |completed_tasks_|. 4735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) task_namespace->completed_tasks.push_back(task); 4745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // If namespace has finished running all tasks, wake up origin thread. 4765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (HasFinishedRunningTasksInNamespace(task_namespace)) 4775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) has_namespaces_with_finished_running_tasks_cv_.Signal(); 4785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 4795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} // namespace cc 481