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 #include "cc/resources/task_graph_runner.h" 6 7 #include <vector> 8 9 #include "base/bind.h" 10 #include "base/synchronization/lock.h" 11 #include "base/threading/simple_thread.h" 12 #include "cc/base/scoped_ptr_deque.h" 13 #include "testing/gtest/include/gtest/gtest.h" 14 15 namespace cc { 16 namespace { 17 18 const int kNamespaceCount = 3; 19 20 class TaskGraphRunnerTestBase { 21 public: 22 struct TaskInfo { 23 TaskInfo(int namespace_index, 24 unsigned id, 25 unsigned dependent_id, 26 unsigned dependent_count, 27 unsigned priority) 28 : namespace_index(namespace_index), 29 id(id), 30 dependent_id(dependent_id), 31 dependent_count(dependent_count), 32 priority(priority) {} 33 34 int namespace_index; 35 unsigned id; 36 unsigned dependent_id; 37 unsigned dependent_count; 38 unsigned priority; 39 }; 40 41 TaskGraphRunnerTestBase() : task_graph_runner_(new TaskGraphRunner) {} 42 43 void ResetIds(int namespace_index) { 44 run_task_ids_[namespace_index].clear(); 45 on_task_completed_ids_[namespace_index].clear(); 46 } 47 48 void RunAllTasks(int namespace_index) { 49 task_graph_runner_->WaitForTasksToFinishRunning( 50 namespace_token_[namespace_index]); 51 52 Task::Vector completed_tasks; 53 task_graph_runner_->CollectCompletedTasks(namespace_token_[namespace_index], 54 &completed_tasks); 55 for (Task::Vector::const_iterator it = completed_tasks.begin(); 56 it != completed_tasks.end(); 57 ++it) { 58 FakeTaskImpl* task = static_cast<FakeTaskImpl*>(it->get()); 59 task->CompleteOnOriginThread(); 60 } 61 } 62 63 void RunTaskOnWorkerThread(int namespace_index, unsigned id) { 64 base::AutoLock lock(run_task_ids_lock_); 65 run_task_ids_[namespace_index].push_back(id); 66 } 67 68 void OnTaskCompleted(int namespace_index, unsigned id) { 69 on_task_completed_ids_[namespace_index].push_back(id); 70 } 71 72 const std::vector<unsigned>& run_task_ids(int namespace_index) { 73 return run_task_ids_[namespace_index]; 74 } 75 76 const std::vector<unsigned>& on_task_completed_ids(int namespace_index) { 77 return on_task_completed_ids_[namespace_index]; 78 } 79 80 void ScheduleTasks(int namespace_index, const std::vector<TaskInfo>& tasks) { 81 Task::Vector new_tasks; 82 Task::Vector new_dependents; 83 TaskGraph new_graph; 84 85 for (std::vector<TaskInfo>::const_iterator it = tasks.begin(); 86 it != tasks.end(); 87 ++it) { 88 scoped_refptr<FakeTaskImpl> new_task( 89 new FakeTaskImpl(this, it->namespace_index, it->id)); 90 new_graph.nodes.push_back( 91 TaskGraph::Node(new_task.get(), it->priority, 0u)); 92 for (unsigned i = 0; i < it->dependent_count; ++i) { 93 scoped_refptr<FakeDependentTaskImpl> new_dependent_task( 94 new FakeDependentTaskImpl( 95 this, it->namespace_index, it->dependent_id)); 96 new_graph.nodes.push_back( 97 TaskGraph::Node(new_dependent_task.get(), it->priority, 1u)); 98 new_graph.edges.push_back( 99 TaskGraph::Edge(new_task.get(), new_dependent_task.get())); 100 101 new_dependents.push_back(new_dependent_task.get()); 102 } 103 104 new_tasks.push_back(new_task.get()); 105 } 106 107 task_graph_runner_->ScheduleTasks(namespace_token_[namespace_index], 108 &new_graph); 109 110 dependents_[namespace_index].swap(new_dependents); 111 tasks_[namespace_index].swap(new_tasks); 112 } 113 114 protected: 115 class FakeTaskImpl : public Task { 116 public: 117 FakeTaskImpl(TaskGraphRunnerTestBase* test, int namespace_index, int id) 118 : test_(test), namespace_index_(namespace_index), id_(id) {} 119 120 // Overridden from Task: 121 virtual void RunOnWorkerThread() OVERRIDE { 122 test_->RunTaskOnWorkerThread(namespace_index_, id_); 123 } 124 125 virtual void CompleteOnOriginThread() { 126 test_->OnTaskCompleted(namespace_index_, id_); 127 } 128 129 protected: 130 virtual ~FakeTaskImpl() {} 131 132 private: 133 TaskGraphRunnerTestBase* test_; 134 int namespace_index_; 135 int id_; 136 137 DISALLOW_COPY_AND_ASSIGN(FakeTaskImpl); 138 }; 139 140 class FakeDependentTaskImpl : public FakeTaskImpl { 141 public: 142 FakeDependentTaskImpl(TaskGraphRunnerTestBase* test, 143 int namespace_index, 144 int id) 145 : FakeTaskImpl(test, namespace_index, id) {} 146 147 // Overridden from FakeTaskImpl: 148 virtual void CompleteOnOriginThread() OVERRIDE {} 149 150 private: 151 virtual ~FakeDependentTaskImpl() {} 152 153 DISALLOW_COPY_AND_ASSIGN(FakeDependentTaskImpl); 154 }; 155 156 scoped_ptr<TaskGraphRunner> task_graph_runner_; 157 NamespaceToken namespace_token_[kNamespaceCount]; 158 Task::Vector tasks_[kNamespaceCount]; 159 Task::Vector dependents_[kNamespaceCount]; 160 std::vector<unsigned> run_task_ids_[kNamespaceCount]; 161 base::Lock run_task_ids_lock_; 162 std::vector<unsigned> on_task_completed_ids_[kNamespaceCount]; 163 }; 164 165 class TaskGraphRunnerTest : public TaskGraphRunnerTestBase, 166 public testing::TestWithParam<int>, 167 public base::DelegateSimpleThread::Delegate { 168 public: 169 // Overridden from testing::Test: 170 virtual void SetUp() OVERRIDE { 171 const size_t num_threads = GetParam(); 172 while (workers_.size() < num_threads) { 173 scoped_ptr<base::DelegateSimpleThread> worker = 174 make_scoped_ptr(new base::DelegateSimpleThread(this, "TestWorker")); 175 worker->Start(); 176 workers_.push_back(worker.Pass()); 177 } 178 179 for (int i = 0; i < kNamespaceCount; ++i) 180 namespace_token_[i] = task_graph_runner_->GetNamespaceToken(); 181 } 182 virtual void TearDown() OVERRIDE { 183 task_graph_runner_->Shutdown(); 184 while (workers_.size()) { 185 scoped_ptr<base::DelegateSimpleThread> worker = workers_.take_front(); 186 worker->Join(); 187 } 188 } 189 190 private: 191 // Overridden from base::DelegateSimpleThread::Delegate: 192 virtual void Run() OVERRIDE { task_graph_runner_->Run(); } 193 194 ScopedPtrDeque<base::DelegateSimpleThread> workers_; 195 }; 196 197 TEST_P(TaskGraphRunnerTest, Basic) { 198 for (int i = 0; i < kNamespaceCount; ++i) { 199 EXPECT_EQ(0u, run_task_ids(i).size()); 200 EXPECT_EQ(0u, on_task_completed_ids(i).size()); 201 202 ScheduleTasks(i, std::vector<TaskInfo>(1, TaskInfo(i, 0u, 0u, 0u, 0u))); 203 } 204 205 for (int i = 0; i < kNamespaceCount; ++i) { 206 RunAllTasks(i); 207 208 EXPECT_EQ(1u, run_task_ids(i).size()); 209 EXPECT_EQ(1u, on_task_completed_ids(i).size()); 210 } 211 212 for (int i = 0; i < kNamespaceCount; ++i) 213 ScheduleTasks(i, std::vector<TaskInfo>(1, TaskInfo(i, 0u, 0u, 1u, 0u))); 214 215 for (int i = 0; i < kNamespaceCount; ++i) { 216 RunAllTasks(i); 217 218 EXPECT_EQ(3u, run_task_ids(i).size()); 219 EXPECT_EQ(2u, on_task_completed_ids(i).size()); 220 } 221 222 for (int i = 0; i < kNamespaceCount; ++i) 223 ScheduleTasks(i, std::vector<TaskInfo>(1, TaskInfo(i, 0u, 0u, 2u, 0u))); 224 225 for (int i = 0; i < kNamespaceCount; ++i) { 226 RunAllTasks(i); 227 228 EXPECT_EQ(6u, run_task_ids(i).size()); 229 EXPECT_EQ(3u, on_task_completed_ids(i).size()); 230 } 231 } 232 233 TEST_P(TaskGraphRunnerTest, Dependencies) { 234 for (int i = 0; i < kNamespaceCount; ++i) { 235 ScheduleTasks(i, 236 std::vector<TaskInfo>(1, 237 TaskInfo(i, 238 0u, 239 1u, 240 1u, // 1 dependent 241 0u))); 242 } 243 244 for (int i = 0; i < kNamespaceCount; ++i) { 245 RunAllTasks(i); 246 247 // Check if task ran before dependent. 248 ASSERT_EQ(2u, run_task_ids(i).size()); 249 EXPECT_EQ(0u, run_task_ids(i)[0]); 250 EXPECT_EQ(1u, run_task_ids(i)[1]); 251 ASSERT_EQ(1u, on_task_completed_ids(i).size()); 252 EXPECT_EQ(0u, on_task_completed_ids(i)[0]); 253 } 254 255 for (int i = 0; i < kNamespaceCount; ++i) { 256 ScheduleTasks(i, 257 std::vector<TaskInfo>(1, 258 TaskInfo(i, 259 2u, 260 3u, 261 2u, // 2 dependents 262 0u))); 263 } 264 265 for (int i = 0; i < kNamespaceCount; ++i) { 266 RunAllTasks(i); 267 268 // Task should only run once. 269 ASSERT_EQ(5u, run_task_ids(i).size()); 270 EXPECT_EQ(2u, run_task_ids(i)[2]); 271 EXPECT_EQ(3u, run_task_ids(i)[3]); 272 EXPECT_EQ(3u, run_task_ids(i)[4]); 273 ASSERT_EQ(2u, on_task_completed_ids(i).size()); 274 EXPECT_EQ(2u, on_task_completed_ids(i)[1]); 275 } 276 } 277 278 INSTANTIATE_TEST_CASE_P(TaskGraphRunnerTests, 279 TaskGraphRunnerTest, 280 ::testing::Range(1, 5)); 281 282 class TaskGraphRunnerSingleThreadTest 283 : public TaskGraphRunnerTestBase, 284 public testing::Test, 285 public base::DelegateSimpleThread::Delegate { 286 public: 287 // Overridden from testing::Test: 288 virtual void SetUp() OVERRIDE { 289 worker_.reset(new base::DelegateSimpleThread(this, "TestWorker")); 290 worker_->Start(); 291 292 for (int i = 0; i < kNamespaceCount; ++i) 293 namespace_token_[i] = task_graph_runner_->GetNamespaceToken(); 294 } 295 virtual void TearDown() OVERRIDE { 296 task_graph_runner_->Shutdown(); 297 worker_->Join(); 298 } 299 300 private: 301 // Overridden from base::DelegateSimpleThread::Delegate: 302 virtual void Run() OVERRIDE { task_graph_runner_->Run(); } 303 304 scoped_ptr<base::DelegateSimpleThread> worker_; 305 }; 306 307 TEST_F(TaskGraphRunnerSingleThreadTest, Priority) { 308 for (int i = 0; i < kNamespaceCount; ++i) { 309 TaskInfo tasks[] = {TaskInfo(i, 0u, 2u, 1u, 1u), // Priority 1 310 TaskInfo(i, 1u, 3u, 1u, 0u) // Priority 0 311 }; 312 ScheduleTasks(i, std::vector<TaskInfo>(tasks, tasks + arraysize(tasks))); 313 } 314 315 for (int i = 0; i < kNamespaceCount; ++i) { 316 RunAllTasks(i); 317 318 // Check if tasks ran in order of priority. 319 ASSERT_EQ(4u, run_task_ids(i).size()); 320 EXPECT_EQ(1u, run_task_ids(i)[0]); 321 EXPECT_EQ(3u, run_task_ids(i)[1]); 322 EXPECT_EQ(0u, run_task_ids(i)[2]); 323 EXPECT_EQ(2u, run_task_ids(i)[3]); 324 ASSERT_EQ(2u, on_task_completed_ids(i).size()); 325 EXPECT_EQ(1u, on_task_completed_ids(i)[0]); 326 EXPECT_EQ(0u, on_task_completed_ids(i)[1]); 327 } 328 } 329 330 } // namespace 331 } // namespace cc 332
