James Robinson | 646469d | 2014-10-03 15:33:28 -0700 | [diff] [blame] | 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: |
James Robinson | e1b30cf | 2014-10-21 12:25:40 -0700 | [diff] [blame] | 121 | void RunOnWorkerThread() override { |
James Robinson | 646469d | 2014-10-03 15:33:28 -0700 | [diff] [blame] | 122 | test_->RunTaskOnWorkerThread(namespace_index_, id_); |
| 123 | } |
| 124 | |
| 125 | virtual void CompleteOnOriginThread() { |
| 126 | test_->OnTaskCompleted(namespace_index_, id_); |
| 127 | } |
| 128 | |
| 129 | protected: |
James Robinson | e1b30cf | 2014-10-21 12:25:40 -0700 | [diff] [blame] | 130 | ~FakeTaskImpl() override {} |
James Robinson | 646469d | 2014-10-03 15:33:28 -0700 | [diff] [blame] | 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: |
James Robinson | e1b30cf | 2014-10-21 12:25:40 -0700 | [diff] [blame] | 148 | void CompleteOnOriginThread() override {} |
James Robinson | 646469d | 2014-10-03 15:33:28 -0700 | [diff] [blame] | 149 | |
| 150 | private: |
James Robinson | e1b30cf | 2014-10-21 12:25:40 -0700 | [diff] [blame] | 151 | ~FakeDependentTaskImpl() override {} |
James Robinson | 646469d | 2014-10-03 15:33:28 -0700 | [diff] [blame] | 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: |
Benjamin Lerman | 5799890 | 2014-11-18 16:06:02 +0100 | [diff] [blame] | 170 | void SetUp() override { |
James Robinson | 646469d | 2014-10-03 15:33:28 -0700 | [diff] [blame] | 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 | } |
Benjamin Lerman | 5799890 | 2014-11-18 16:06:02 +0100 | [diff] [blame] | 182 | void TearDown() override { |
James Robinson | 646469d | 2014-10-03 15:33:28 -0700 | [diff] [blame] | 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: |
James Robinson | e1b30cf | 2014-10-21 12:25:40 -0700 | [diff] [blame] | 192 | void Run() override { task_graph_runner_->Run(); } |
James Robinson | 646469d | 2014-10-03 15:33:28 -0700 | [diff] [blame] | 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: |
Benjamin Lerman | 5799890 | 2014-11-18 16:06:02 +0100 | [diff] [blame] | 288 | void SetUp() override { |
James Robinson | 646469d | 2014-10-03 15:33:28 -0700 | [diff] [blame] | 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 | } |
Benjamin Lerman | 5799890 | 2014-11-18 16:06:02 +0100 | [diff] [blame] | 295 | void TearDown() override { |
James Robinson | 646469d | 2014-10-03 15:33:28 -0700 | [diff] [blame] | 296 | task_graph_runner_->Shutdown(); |
| 297 | worker_->Join(); |
| 298 | } |
| 299 | |
| 300 | private: |
| 301 | // Overridden from base::DelegateSimpleThread::Delegate: |
James Robinson | e1b30cf | 2014-10-21 12:25:40 -0700 | [diff] [blame] | 302 | void Run() override { task_graph_runner_->Run(); } |
James Robinson | 646469d | 2014-10-03 15:33:28 -0700 | [diff] [blame] | 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 |