components/scheduler/child/task_queue_selector_unittest.cc

   1 // Copyright 2015 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 "components/scheduler/child/task_queue_selector.h"
   6
   7 #include "base/bind.h"
   8 #include "base/memory/scoped_ptr.h"
   9 #include "base/memory/scoped_vector.h"
  10 #include "base/pending_task.h"
  11 #include "components/scheduler/child/task_queue_impl.h"
  12 #include "components/scheduler/child/task_queue_sets.h"
  13 #include "testing/gmock/include/gmock/gmock.h"
  14 #include "testing/gtest/include/gtest/gtest.h"
  15
  16 namespace scheduler {
  17 namespace internal {
  18
  19 class MockObserver : public TaskQueueSelector::Observer {
  20  public:
  21   MockObserver() {}
  22   virtual ~MockObserver() {}
  23
  24   MOCK_METHOD0(OnTaskQueueEnabled, void());
  25
  26  private:
  27   DISALLOW_COPY_AND_ASSIGN(MockObserver);
  28 };
  29
  30 class TaskQueueSelectorTest : public testing::Test {
  31  public:
  32   TaskQueueSelectorTest()
  33       : test_closure_(base::Bind(&TaskQueueSelectorTest::TestFunction)) {}
  34   ~TaskQueueSelectorTest() override {}
  35
  36   std::vector<base::PendingTask> GetTasks(int count) {
  37     std::vector<base::PendingTask> tasks;
  38     for (int i = 0; i < count; i++) {
  39       base::PendingTask task = base::PendingTask(FROM_HERE, test_closure_);
  40       task.sequence_num = i;
  41       tasks.push_back(task);
  42     }
  43     return tasks;
  44   }
  45
  46   void PushTasks(const std::vector<base::PendingTask>& tasks,
  47                  const size_t queue_indices[]) {
  48     std::set<size_t> changed_queue_set;
  49     for (size_t i = 0; i < tasks.size(); i++) {
  50       changed_queue_set.insert(queue_indices[i]);
  51       task_queues_[queue_indices[i]]->PushTaskOntoWorkQueueForTest(tasks[i]);
  52     }
  53     for (size_t queue_index : changed_queue_set) {
  54       selector_.GetTaskQueueSets()->OnPushQueue(
  55           task_queues_[queue_index].get());
  56     }
  57   }
  58
  59   std::vector<size_t> PopTasks() {
  60     std::vector<size_t> order;
  61     internal::TaskQueueImpl* chosen_queue;
  62     while (selector_.SelectQueueToService(&chosen_queue)) {
  63       size_t chosen_queue_index =
  64           queue_to_index_map_.find(chosen_queue)->second;
  65       order.push_back(chosen_queue_index);
  66       chosen_queue->PopTaskFromWorkQueueForTest();
  67       selector_.GetTaskQueueSets()->OnPopQueue(chosen_queue);
  68     }
  69     return order;
  70   }
  71
  72   static void TestFunction() {}
  73
  74  protected:
  75   void SetUp() final {
  76     for (size_t i = 0; i < kTaskQueueCount; i++) {
  77       scoped_refptr<internal::TaskQueueImpl> task_queue =
  78           make_scoped_refptr(new internal::TaskQueueImpl(
  79               nullptr, TaskQueue::Spec("test queue"), "test", "test"));
  80       selector_.AddQueue(task_queue.get());
  81       task_queues_.push_back(task_queue);
  82     }
  83     for (size_t i = 0; i < kTaskQueueCount; i++) {
  84       EXPECT_TRUE(selector_.IsQueueEnabled(task_queues_[i].get())) << i;
  85       queue_to_index_map_.insert(std::make_pair(task_queues_[i].get(), i));
  86     }
  87   }
  88
  89   const size_t kTaskQueueCount = 5;
  90   base::Closure test_closure_;
  91   TaskQueueSelector selector_;
  92   std::vector<scoped_refptr<internal::TaskQueueImpl>> task_queues_;
  93   std::map<internal::TaskQueueImpl*, size_t> queue_to_index_map_;
  94 };
  95
  96 TEST_F(TaskQueueSelectorTest, TestDefaultPriority) {
  97   std::vector<base::PendingTask> tasks = GetTasks(5);
  98   size_t queue_order[] = {4, 3, 2, 1, 0};
  99   PushTasks(tasks, queue_order);
 100   EXPECT_THAT(PopTasks(), testing::ElementsAre(4, 3, 2, 1, 0));
 101 }
 102
 103 TEST_F(TaskQueueSelectorTest, TestHighPriority) {
 104   std::vector<base::PendingTask> tasks = GetTasks(5);
 105   size_t queue_order[] = {0, 1, 2, 3, 4};
 106   PushTasks(tasks, queue_order);
 107   selector_.SetQueuePriority(task_queues_[2].get(), TaskQueue::HIGH_PRIORITY);
 108   EXPECT_THAT(PopTasks(), testing::ElementsAre(2, 0, 1, 3, 4));
 109 }
 110
 111 TEST_F(TaskQueueSelectorTest, TestBestEffortPriority) {
 112   std::vector<base::PendingTask> tasks = GetTasks(5);
 113   size_t queue_order[] = {0, 1, 2, 3, 4};
 114   PushTasks(tasks, queue_order);
 115   selector_.SetQueuePriority(task_queues_[0].get(),
 116                              TaskQueue::BEST_EFFORT_PRIORITY);
 117   selector_.SetQueuePriority(task_queues_[2].get(), TaskQueue::HIGH_PRIORITY);
 118   EXPECT_THAT(PopTasks(), testing::ElementsAre(2, 1, 3, 4, 0));
 119 }
 120
 121 TEST_F(TaskQueueSelectorTest, TestControlPriority) {
 122   std::vector<base::PendingTask> tasks = GetTasks(5);
 123   size_t queue_order[] = {0, 1, 2, 3, 4};
 124   PushTasks(tasks, queue_order);
 125   selector_.SetQueuePriority(task_queues_[4].get(),
 126                              TaskQueue::CONTROL_PRIORITY);
 127   EXPECT_TRUE(selector_.IsQueueEnabled(task_queues_[4].get()));
 128   selector_.SetQueuePriority(task_queues_[2].get(), TaskQueue::HIGH_PRIORITY);
 129   EXPECT_TRUE(selector_.IsQueueEnabled(task_queues_[2].get()));
 130   EXPECT_THAT(PopTasks(), testing::ElementsAre(4, 2, 0, 1, 3));
 131 }
 132
 133 TEST_F(TaskQueueSelectorTest, TestObserverWithSetQueuePriority) {
 134   selector_.SetQueuePriority(task_queues_[1].get(),
 135                              TaskQueue::DISABLED_PRIORITY);
 136   MockObserver mock_observer;
 137   selector_.SetTaskQueueSelectorObserver(&mock_observer);
 138   EXPECT_CALL(mock_observer, OnTaskQueueEnabled()).Times(1);
 139   selector_.SetQueuePriority(task_queues_[1].get(), TaskQueue::NORMAL_PRIORITY);
 140 }
 141
 142 TEST_F(TaskQueueSelectorTest,
 143        TestObserverWithSetQueuePriorityAndQueueAlreadyEnabed) {
 144   selector_.SetQueuePriority(task_queues_[1].get(), TaskQueue::NORMAL_PRIORITY);
 145   MockObserver mock_observer;
 146   selector_.SetTaskQueueSelectorObserver(&mock_observer);
 147   EXPECT_CALL(mock_observer, OnTaskQueueEnabled()).Times(0);
 148   selector_.SetQueuePriority(task_queues_[1].get(), TaskQueue::NORMAL_PRIORITY);
 149 }
 150
 151 TEST_F(TaskQueueSelectorTest, TestDisableEnable) {
 152   MockObserver mock_observer;
 153   selector_.SetTaskQueueSelectorObserver(&mock_observer);
 154
 155   std::vector<base::PendingTask> tasks = GetTasks(5);
 156   size_t queue_order[] = {0, 1, 2, 3, 4};
 157   PushTasks(tasks, queue_order);
 158   selector_.SetQueuePriority(task_queues_[2].get(),
 159                              TaskQueue::DISABLED_PRIORITY);
 160   EXPECT_FALSE(selector_.IsQueueEnabled(task_queues_[2].get()));
 161   selector_.SetQueuePriority(task_queues_[4].get(),
 162                              TaskQueue::DISABLED_PRIORITY);
 163   EXPECT_FALSE(selector_.IsQueueEnabled(task_queues_[4].get()));
 164   EXPECT_THAT(PopTasks(), testing::ElementsAre(0, 1, 3));
 165
 166   EXPECT_CALL(mock_observer, OnTaskQueueEnabled()).Times(2);
 167   selector_.SetQueuePriority(task_queues_[2].get(),
 168                              TaskQueue::BEST_EFFORT_PRIORITY);
 169   EXPECT_THAT(PopTasks(), testing::ElementsAre(2));
 170   selector_.SetQueuePriority(task_queues_[4].get(), TaskQueue::NORMAL_PRIORITY);
 171   EXPECT_THAT(PopTasks(), testing::ElementsAre(4));
 172 }
 173
 174 TEST_F(TaskQueueSelectorTest, TestEmptyQueues) {
 175   internal::TaskQueueImpl* chosen_queue = nullptr;
 176   EXPECT_FALSE(selector_.SelectQueueToService(&chosen_queue));
 177
 178   // Test only disabled queues.
 179   std::vector<base::PendingTask> tasks = GetTasks(1);
 180   size_t queue_order[] = {0};
 181   PushTasks(tasks, queue_order);
 182   selector_.SetQueuePriority(task_queues_[0].get(),
 183                              TaskQueue::DISABLED_PRIORITY);
 184   EXPECT_FALSE(selector_.IsQueueEnabled(task_queues_[0].get()));
 185   EXPECT_FALSE(selector_.SelectQueueToService(&chosen_queue));
 186 }
 187
 188 TEST_F(TaskQueueSelectorTest, TestSequenceNumber) {
 189   std::vector<base::PendingTask> tasks = GetTasks(5);
 190   tasks[0].sequence_num = 10;
 191   tasks[3].sequence_num = 9;
 192   size_t queue_order[] = {0, 1, 2, 3, 4};
 193   PushTasks(tasks, queue_order);
 194   EXPECT_THAT(PopTasks(), testing::ElementsAre(1, 2, 4, 3, 0));
 195 }
 196
 197 TEST_F(TaskQueueSelectorTest, TestControlStarvesOthers) {
 198   std::vector<base::PendingTask> tasks = GetTasks(4);
 199   size_t queue_order[] = {0, 1, 2, 3};
 200   PushTasks(tasks, queue_order);
 201   selector_.SetQueuePriority(task_queues_[3].get(),
 202                              TaskQueue::CONTROL_PRIORITY);
 203   selector_.SetQueuePriority(task_queues_[2].get(), TaskQueue::HIGH_PRIORITY);
 204   selector_.SetQueuePriority(task_queues_[1].get(),
 205                              TaskQueue::BEST_EFFORT_PRIORITY);
 206   for (int i = 0; i < 100; i++) {
 207     internal::TaskQueueImpl* chosen_queue = nullptr;
 208     EXPECT_TRUE(selector_.SelectQueueToService(&chosen_queue));
 209     EXPECT_EQ(task_queues_[3].get(), chosen_queue);
 210     // Don't remove task from queue to simulate all queues still being full.
 211   }
 212 }
 213
 214 TEST_F(TaskQueueSelectorTest, TestHighPriorityDoesNotStarveNormal) {
 215   std::vector<base::PendingTask> tasks = GetTasks(3);
 216   size_t queue_order[] = {0, 1, 2};
 217   PushTasks(tasks, queue_order);
 218   selector_.SetQueuePriority(task_queues_[2].get(), TaskQueue::HIGH_PRIORITY);
 219   selector_.SetQueuePriority(task_queues_[1].get(),
 220                              TaskQueue::BEST_EFFORT_PRIORITY);
 221   size_t counts[] = {0, 0, 0};
 222   for (int i = 0; i < 100; i++) {
 223     internal::TaskQueueImpl* chosen_queue = nullptr;
 224     EXPECT_TRUE(selector_.SelectQueueToService(&chosen_queue));
 225     size_t chosen_queue_index = queue_to_index_map_.find(chosen_queue)->second;
 226     counts[chosen_queue_index]++;
 227     // Don't remove task from queue to simulate all queues still being full.
 228   }
 229   EXPECT_GT(counts[0], 0ul);        // Check high doesn't starve normal.
 230   EXPECT_GT(counts[2], counts[0]);  // Check high gets more chance to run.
 231   EXPECT_EQ(0ul, counts[1]);        // Check best effort is starved.
 232 }
 233
 234 TEST_F(TaskQueueSelectorTest, TestBestEffortGetsStarved) {
 235   std::vector<base::PendingTask> tasks = GetTasks(2);
 236   size_t queue_order[] = {0, 1};
 237   PushTasks(tasks, queue_order);
 238   selector_.SetQueuePriority(task_queues_[0].get(),
 239                              TaskQueue::BEST_EFFORT_PRIORITY);
 240   selector_.SetQueuePriority(task_queues_[1].get(), TaskQueue::NORMAL_PRIORITY);
 241   internal::TaskQueueImpl* chosen_queue = nullptr;
 242   for (int i = 0; i < 100; i++) {
 243     EXPECT_TRUE(selector_.SelectQueueToService(&chosen_queue));
 244     EXPECT_EQ(task_queues_[1].get(), chosen_queue);
 245     // Don't remove task from queue to simulate all queues still being full.
 246   }
 247   selector_.SetQueuePriority(task_queues_[1].get(), TaskQueue::HIGH_PRIORITY);
 248   for (int i = 0; i < 100; i++) {
 249     EXPECT_TRUE(selector_.SelectQueueToService(&chosen_queue));
 250     EXPECT_EQ(task_queues_[1].get(), chosen_queue);
 251     // Don't remove task from queue to simulate all queues still being full.
 252   }
 253   selector_.SetQueuePriority(task_queues_[1].get(),
 254                              TaskQueue::CONTROL_PRIORITY);
 255   for (int i = 0; i < 100; i++) {
 256     EXPECT_TRUE(selector_.SelectQueueToService(&chosen_queue));
 257     EXPECT_EQ(task_queues_[1].get(), chosen_queue);
 258     // Don't remove task from queue to simulate all queues still being full.
 259   }
 260 }
 261
 262 TEST_F(TaskQueueSelectorTest, DisabledPriorityIsPenultimate) {
 263   EXPECT_EQ(TaskQueue::QUEUE_PRIORITY_COUNT, TaskQueue::DISABLED_PRIORITY + 1);
 264 }
 265
 266 }  // namespace internal
 267 }  // namespace scheduler