Implementation of SequencedTaskRunner based on SequencedWorkerPool.

base/test/sequenced_task_runner_test_template.h

+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// This class defines tests that implementations of SequencedTaskRunner should
+// pass in order to be conformant.  Here's how you use it to test your
+// implementation.
+//
+// See task_runner_test_template.h for a description of how to use the
+// constructs in this file; these work the same.
+
+#ifndef BASE_SEQUENCED_TASK_RUNNER_TEST_TEMPLATE_H_
+#define BASE_SEQUENCED_TASK_RUNNER_TEST_TEMPLATE_H_
+#pragma once
+
+#include <cstddef>
+
+#include <vector>
+
+#include "base/basictypes.h"
+#include "base/bind.h"
+#include "base/memory/ref_counted.h"
+#include "base/sequenced_task_runner.h"
+#include "base/synchronization/lock.h"
+#include "base/synchronization/waitable_event.h"
+#include "base/tracked_objects.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace base {
+
+namespace internal {
+
+// Utility class used in the tests below.
+class SequencedTaskTracker : public RefCountedThreadSafe<SequencedTaskTracker> {
+ public:
+  // Keeps track of a task's run status. I.e. whether it has run to completion
+  // and whether its predecessor had run to completion by the time it started
+  // running.
+  class TaskStatus {
+   public:
+    TaskStatus();
+    TaskStatus(const TaskStatus& ts);
+    TaskStatus& operator=(const TaskStatus& ts);
+    bool operator==(const TaskStatus& ts) const;
+
+    // Claims ownership of this task status for a task.
+    bool Claim();
+    // Whether the owning task has started running yet.
+    bool Started() const;
+    // Whether the owning task has run to completion yet.
+    bool Completed() const;
+    // Whether the previous task had started by the time this one did.
+    bool PrevStartedBefore() const;
+    // Whether the previous task (the one which owns the preceding position in
+    // the task status vector) had finished by the time this one started.
+    bool PrevCompletedBefore() const;
+    // Declares that the owning task has started running.
+    void SetStarted();
+    // Declares that the owning task has run to completion.
+    void SetCompleted();
+    // Declares that the previous task had started by the time the owning task
+    // started.
+    void SetPrevStartedBefore(bool b);
+    // Declares that the previous task had run to completion by the time the
+    // owning task started.
+    void SetPrevCompletedBefore(bool b);
+
+   private:
+    // An output operator is required to make a failed gtest assertion print
+    // human-readable information.
+    friend std::ostream& operator<<(std::ostream&, const TaskStatus&);
+
+    mutable Lock lock_;
+    // Used to prevent task_i from checking task_i-1.Started() before task_i-1
+    // has had a chance to signal that it has started. There would otherwise
+    // be a race between the top of the task function and the line where it
+    // calls SetStarted().
+    mutable WaitableEvent start_event_;
+    // Whether this status slot has been claimed by a task yet.
+    bool claimed_;
+    bool started_;
+    bool completed_;
+    bool prev_started_;
+    bool prev_completed_;
+  };
+
+  typedef std::vector<TaskStatus> TaskStatuses;
+
+  SequencedTaskTracker();
+
+  // Pre-allocates memory for the non-nestable task statuses.
+  void SetNonNestableTaskCount(std::size_t task_count);
+
+  // Pre-allocates memory for the nestable task statuses.
+  void SetNestableTaskCount(std::size_t task_count);
+
+  const TaskStatuses& GetNonNestableTaskStatuses() const;
+  const TaskStatuses& GetNestableTaskStatuses() const;
+
+  // A fast, non-nestable task.
+  void FastNonNestableTask(int base_status_i);
+
+  // A fast, nestable task.
+  void FastNestableTask(int parent_task_status_slot);
+
+  // A slow, non-nestable task (sleeps for 1 second).
+  void SlowNonNestableTask(int base_status_i);
+
+  // A slow, nestable task (sleeps for 1 second).
+  void SlowNestableTask(int base_status_i);
+
+  // Posts a fast, non-nestable task from a slow, non-nestable one.
+  void PostFastNonNestableFromSlowNonNestable(
+      scoped_refptr<SequencedTaskRunner> task_runner,
+      const int base_status_i,
+      const int child_count);
+
+  // Posts a fast, nestable task from a slow, non-nestable one.
+  void PostFastNestableFromSlowNonNestable(
+      scoped_refptr<SequencedTaskRunner> task_runner,
+      const int base_status_i,
+      const int child_count);
+
+ private:
+  friend class RefCountedThreadSafe<SequencedTaskTracker>;
+
+  ~SequencedTaskTracker();
+
+  // Finds the lowest-numbered non-nestable task status object, beginning at
+  // position |search_from|, which has not yet been claimed.
+  int ClaimNonNestableTaskStatus(const int search_from);
+
+  // Finds the lowest-numbered nestable task status object, beginning at
+  // position |search_from|, which has not yet been claimed.
+  int ClaimNestableTaskStatus(const int search_from);
+
+  TaskStatuses nestable_statuses_;
+  TaskStatuses non_nestable_statuses_;
+
+  DISALLOW_COPY_AND_ASSIGN(SequencedTaskTracker);
+};
+
+// An output operator is required to make a failed gtest assertion print
+// human-readable information.
+std::ostream& operator<<(std::ostream& os,
+                         const SequencedTaskTracker::TaskStatus& ts);
+
+}  // namespace internal
+
+template <typename TaskRunnerTestDelegate>
+class SequencedTaskRunnerTest : public testing::Test {
+ protected:
+  SequencedTaskRunnerTest()
+  : task_tracker_(new internal::SequencedTaskTracker()) {
+    good_task_status_prototype_.SetStarted();
+    good_task_status_prototype_.SetPrevStartedBefore(true);
+    good_task_status_prototype_.SetPrevCompletedBefore(true);
+    good_task_status_prototype_.SetCompleted();
+  }
+
+  const scoped_refptr<internal::SequencedTaskTracker> task_tracker_;
+  TaskRunnerTestDelegate delegate_;
+  internal::SequencedTaskTracker::TaskStatus good_task_status_prototype_;
+};
+
+TYPED_TEST_CASE_P(SequencedTaskRunnerTest);
+
+// This test posts N non-nestable tasks in sequence, and expects them to run
+// in FIFO order, with no part of any two tasks' execution overlapping.
+//
+// It checks that task0 was done by the time task1 started, and task2 only
+// started after task1 had executed to completion, etc.
+//
+// The first task it starts is a slow one which runs for a second, giving the
+// subsequent ones plenty of time to run if the implementation fails to
+// enforce the non-nestable property.
+TYPED_TEST_P(SequencedTaskRunnerTest, SequentialNonNestable) {
+  const int task_count = 1000;
+
+  this->task_tracker_->SetNonNestableTaskCount(task_count);
+  internal::SequencedTaskTracker::TaskStatuses expected_statuses(
+      task_count,
+      this->good_task_status_prototype_);
+
+  this->delegate_.StartTaskRunner();
+  scoped_refptr<SequencedTaskRunner> task_runner =
+      this->delegate_.GetTaskRunner();
+
+  for (int i = 0; i < task_count; ++i) {
+    Closure task;
+    if (i == 0) {
+      task = Bind(&internal::SequencedTaskTracker::SlowNonNestableTask,
+                  this->task_tracker_, i);
+    } else {
+      task = Bind(&internal::SequencedTaskTracker::FastNonNestableTask,
+                  this->task_tracker_, i);
+    }
+    task_runner->PostNonNestableTask(FROM_HERE, task);
+  }
+
+  this->delegate_.StopTaskRunner();
+
+  EXPECT_EQ(expected_statuses,
+            this->task_tracker_->GetNonNestableTaskStatuses());
+}
+
+// This test posts N nestable tasks in sequence, and expects them to run in
+// FIFO order; overlapping execution is allowed.
+//
+// It checks only that task_i had started by the time task_i+1 started, for
+// increasing values of i. Thus it verifies the SequencedTaskRunner guarantee
+// that nested tasks are run in FIFO order.
+//
+// The first task it starts is a slow one which runs for a second, giving the
+// subsequent ones plenty of time to run in if the implementation fails to
+// enforce the FIFO property for nestable tasks.
+TYPED_TEST_P(SequencedTaskRunnerTest, SequentialNestable) {
+  const int task_count = 1000;
+
+  this->task_tracker_->SetNestableTaskCount(task_count);
+  internal::SequencedTaskTracker::TaskStatuses expected_statuses(
+      task_count,
+      this->good_task_status_prototype_);
+
+  this->delegate_.StartTaskRunner();
+  scoped_refptr<SequencedTaskRunner> task_runner =
+      this->delegate_.GetTaskRunner();
+
+  for (int i = 0; i < task_count; ++i) {
+    Closure task;
+    if (i == 0) {
+      task = Bind(&internal::SequencedTaskTracker::SlowNestableTask,
+                  this->task_tracker_, i);
+    } else {
+      task = Bind(&internal::SequencedTaskTracker::FastNestableTask,
+                  this->task_tracker_, i);
+    }
+    task_runner->PostTask(FROM_HERE, task);
+  }
+
+  this->delegate_.StopTaskRunner();
+
+  EXPECT_EQ(expected_statuses,
+            this->task_tracker_->GetNestableTaskStatuses());
+}
+
+// This test posts non-nestable tasks in order of increasing delay, and checks
+// that that the tasks are run in FIFO order and that there is no execution
+// overlap whatsoever between any two tasks.
+//
+// If there are 10 tasks, task1 is posted first with a delay of zero, followed
+// by task2 with a delay of, say, 1, and so forth, until task10 is posted with
+// a delay of 10. It then checks that task2 started after task1, and only
+// after task1 had finished, and so forth.
+TYPED_TEST_P(SequencedTaskRunnerTest, SequentialDelayedNonNestable) {
+  if (!this->delegate_.TaskRunnerHandlesNonZeroDelays()) {
+    DLOG(INFO) << "This SequencedTaskRunner doesn't handle "
+        "non-zero delays; skipping";
+    return;
+  }
+
+  const int task_count = 20;
+  const int delay_increment_ms = 50;
+
+  this->task_tracker_->SetNonNestableTaskCount(task_count);
+  internal::SequencedTaskTracker::TaskStatuses expected_statuses(
+      task_count,
+      this->good_task_status_prototype_);
+
+  this->delegate_.StartTaskRunner();
+  scoped_refptr<SequencedTaskRunner> task_runner =
+      this->delegate_.GetTaskRunner();
+
+  for (int i = 0; i < task_count; ++i) {
+    Closure task = Bind(&internal::SequencedTaskTracker::FastNonNestableTask,
+                        this->task_tracker_, i);
+    task_runner->PostNonNestableDelayedTask(
+        FROM_HERE,
+        task,
+        TimeDelta::FromMilliseconds(delay_increment_ms * i));
+  }
+
+  this->delegate_.StopTaskRunner();
+
+  EXPECT_EQ(expected_statuses,
+            this->task_tracker_->GetNonNestableTaskStatuses());
+}
+
+// This test posts a fast, non-nestable task from within each of a number of
+// slow, non-nestable tasks and checks that they all run in the sequence they
+// were posted in and that there is no execution overlap whatsoever.
+TYPED_TEST_P(SequencedTaskRunnerTest,
+             NonNestablePostFromNonNestableTask) {
+  const int parent_count = 1000;
+  const int children_per_parent = 2;
+  const int task_count = parent_count * (children_per_parent + 1);
+
+  this->task_tracker_->SetNonNestableTaskCount(task_count);
+  internal::SequencedTaskTracker::TaskStatuses expected_statuses(
+      task_count,
+      this->good_task_status_prototype_);
+
+  this->delegate_.StartTaskRunner();
+  scoped_refptr<SequencedTaskRunner> task_runner =
+      this->delegate_.GetTaskRunner();
+
+  const int end = parent_count;
+  for (int i = 0; i < end; ++i) {
+    Closure task = Bind(
+        &internal::SequencedTaskTracker::PostFastNonNestableFromSlowNonNestable,
+        this->task_tracker_,
+        task_runner,
+        i,
+        children_per_parent);
+    task_runner->PostNonNestableTask(FROM_HERE, task);
+  }
+
+  this->delegate_.StopTaskRunner();
+
+  EXPECT_EQ(expected_statuses,
+            this->task_tracker_->GetNonNestableTaskStatuses());
+}
+
+// This test posts a number of fast, nestable tasks from within each of a
+// number of slow, non-nestable tasks and checks that the non-nestable ones
+// all run in the sequence they were posted in and that there is no execution
+// overlap whatsoever.
+TYPED_TEST_P(SequencedTaskRunnerTest,
+             NestablePostFromNonNestableTask) {
+  const int parent_count = 500;
+  const int children_per_parent = 2;
+
+  this->task_tracker_->SetNonNestableTaskCount(parent_count);
+  internal::SequencedTaskTracker::TaskStatuses expected_non_nestable_statuses(
+      parent_count,
+      this->good_task_status_prototype_);
+  this->task_tracker_->SetNestableTaskCount(children_per_parent * parent_count);
+  internal::SequencedTaskTracker::TaskStatuses expected_nestable_statuses(
+      children_per_parent * parent_count,
+      this->good_task_status_prototype_);
+
+  this->delegate_.StartTaskRunner();
+  scoped_refptr<SequencedTaskRunner> task_runner =
+      this->delegate_.GetTaskRunner();
+
+  const int end = parent_count;
+  for (int i = 0; i < end; ++i) {
+    Closure task = Bind(
+        &internal::SequencedTaskTracker::PostFastNestableFromSlowNonNestable,
+        this->task_tracker_,
+        task_runner,
+        i,
+        children_per_parent);
+    task_runner->PostNonNestableTask(FROM_HERE, task);
+  }
+
+  this->delegate_.StopTaskRunner();
+
+  EXPECT_EQ(expected_non_nestable_statuses,
+            this->task_tracker_->GetNonNestableTaskStatuses());
+  EXPECT_EQ(expected_nestable_statuses,
+            this->task_tracker_->GetNestableTaskStatuses());
+}
+
+// TODO(francoisk777@gmail.com) Add a test, similiar to the above, which which
+// runs some tasked nestedly (which should be implemented in the test
+// delegate). Also add, to the the test delegate, a predicate which checks
+// whether the implementation supports nested tasks.
+
+REGISTER_TYPED_TEST_CASE_P(SequencedTaskRunnerTest,
+                           SequentialNonNestable,
+                           SequentialNestable,
+                           SequentialDelayedNonNestable,
+                           NonNestablePostFromNonNestableTask,
+                           NestablePostFromNonNestableTask);
+
+}  // namespace base
+
+#endif  // BASE_TASK_RUNNER_TEST_TEMPLATE_H_