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
15namespace cc {
16namespace {
17
18const int kNamespaceCount = 3;
19
20class 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
165class 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
197TEST_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
233TEST_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
278INSTANTIATE_TEST_CASE_P(TaskGraphRunnerTests,
279                        TaskGraphRunnerTest,
280                        ::testing::Range(1, 5));
281
282class 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
307TEST_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