src/cc/resources/task_graph_runner_unittest.cc

   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