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