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 "base/task/sequence_manager/work_queue_sets.h"
6
7 #include <stddef.h>
8
9 #include "base/memory/ptr_util.h"
10 #include "base/task/sequence_manager/work_queue.h"
11 #include "testing/gmock/include/gmock/gmock.h"
12
13 namespace base {
14 namespace sequence_manager {
15
16 class TimeDomain;
17
18 namespace internal {
19
20 class WorkQueueSetsTest : public testing::Test {
21 public:
SetUp()22 void SetUp() override {
23 work_queue_sets_.reset(new WorkQueueSets(kNumSets, "test"));
24 }
25
TearDown()26 void TearDown() override {
27 for (std::unique_ptr<WorkQueue>& work_queue : work_queues_) {
28 if (work_queue->work_queue_sets())
29 work_queue_sets_->RemoveQueue(work_queue.get());
30 }
31 }
32
33 protected:
34 enum {
35 kNumSets = 5 // An arbitary choice.
36 };
37
NewTaskQueue(const char * queue_name)38 WorkQueue* NewTaskQueue(const char* queue_name) {
39 WorkQueue* queue =
40 new WorkQueue(nullptr, "test", WorkQueue::QueueType::kImmediate);
41 work_queues_.push_back(WrapUnique(queue));
42 work_queue_sets_->AddQueue(queue, TaskQueue::kControlPriority);
43 return queue;
44 }
45
FakeTaskWithEnqueueOrder(int enqueue_order)46 TaskQueueImpl::Task FakeTaskWithEnqueueOrder(int enqueue_order) {
47 TaskQueueImpl::Task fake_task(
48 TaskQueue::PostedTask(BindOnce([] {}), FROM_HERE), TimeTicks(),
49 EnqueueOrder(), EnqueueOrder::FromIntForTesting(enqueue_order));
50 return fake_task;
51 }
52
FakeNonNestableTaskWithEnqueueOrder(int enqueue_order)53 TaskQueueImpl::Task FakeNonNestableTaskWithEnqueueOrder(int enqueue_order) {
54 TaskQueueImpl::Task fake_task(
55 TaskQueue::PostedTask(BindOnce([] {}), FROM_HERE), TimeTicks(),
56 EnqueueOrder(), EnqueueOrder::FromIntForTesting(enqueue_order));
57 fake_task.nestable = Nestable::kNonNestable;
58 return fake_task;
59 }
60
61 std::vector<std::unique_ptr<WorkQueue>> work_queues_;
62 std::unique_ptr<WorkQueueSets> work_queue_sets_;
63 };
64
TEST_F(WorkQueueSetsTest,ChangeSetIndex)65 TEST_F(WorkQueueSetsTest, ChangeSetIndex) {
66 WorkQueue* work_queue = NewTaskQueue("queue");
67 size_t set = TaskQueue::kNormalPriority;
68 work_queue_sets_->ChangeSetIndex(work_queue, set);
69
70 EXPECT_EQ(set, work_queue->work_queue_set_index());
71 }
72
TEST_F(WorkQueueSetsTest,GetOldestQueueInSet_QueueEmpty)73 TEST_F(WorkQueueSetsTest, GetOldestQueueInSet_QueueEmpty) {
74 WorkQueue* work_queue = NewTaskQueue("queue");
75 size_t set = TaskQueue::kNormalPriority;
76 work_queue_sets_->ChangeSetIndex(work_queue, set);
77
78 WorkQueue* selected_work_queue;
79 EXPECT_FALSE(
80 work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
81 }
82
TEST_F(WorkQueueSetsTest,OnTaskPushedToEmptyQueue)83 TEST_F(WorkQueueSetsTest, OnTaskPushedToEmptyQueue) {
84 WorkQueue* work_queue = NewTaskQueue("queue");
85 size_t set = TaskQueue::kNormalPriority;
86 work_queue_sets_->ChangeSetIndex(work_queue, set);
87
88 WorkQueue* selected_work_queue;
89 EXPECT_FALSE(
90 work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
91
92 // Calls OnTaskPushedToEmptyQueue.
93 work_queue->Push(FakeTaskWithEnqueueOrder(10));
94
95 EXPECT_TRUE(work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
96 EXPECT_EQ(work_queue, selected_work_queue);
97 }
98
TEST_F(WorkQueueSetsTest,GetOldestQueueInSet_SingleTaskInSet)99 TEST_F(WorkQueueSetsTest, GetOldestQueueInSet_SingleTaskInSet) {
100 WorkQueue* work_queue = NewTaskQueue("queue");
101 work_queue->Push(FakeTaskWithEnqueueOrder(10));
102 size_t set = 1;
103 work_queue_sets_->ChangeSetIndex(work_queue, set);
104
105 WorkQueue* selected_work_queue;
106 EXPECT_TRUE(work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
107 EXPECT_EQ(work_queue, selected_work_queue);
108 }
109
TEST_F(WorkQueueSetsTest,GetOldestQueueAndEnqueueOrderInSet)110 TEST_F(WorkQueueSetsTest, GetOldestQueueAndEnqueueOrderInSet) {
111 WorkQueue* work_queue = NewTaskQueue("queue");
112 work_queue->Push(FakeTaskWithEnqueueOrder(10));
113 size_t set = 1;
114 work_queue_sets_->ChangeSetIndex(work_queue, set);
115
116 WorkQueue* selected_work_queue;
117 EnqueueOrder enqueue_order;
118 EXPECT_TRUE(work_queue_sets_->GetOldestQueueAndEnqueueOrderInSet(
119 set, &selected_work_queue, &enqueue_order));
120 EXPECT_EQ(work_queue, selected_work_queue);
121 EXPECT_EQ(10u, enqueue_order);
122 }
123
TEST_F(WorkQueueSetsTest,GetOldestQueueInSet_MultipleAgesInSet)124 TEST_F(WorkQueueSetsTest, GetOldestQueueInSet_MultipleAgesInSet) {
125 WorkQueue* queue1 = NewTaskQueue("queue1");
126 WorkQueue* queue2 = NewTaskQueue("queue2");
127 WorkQueue* queue3 = NewTaskQueue("queue2");
128 queue1->Push(FakeTaskWithEnqueueOrder(6));
129 queue2->Push(FakeTaskWithEnqueueOrder(5));
130 queue3->Push(FakeTaskWithEnqueueOrder(4));
131 size_t set = 2;
132 work_queue_sets_->ChangeSetIndex(queue1, set);
133 work_queue_sets_->ChangeSetIndex(queue2, set);
134 work_queue_sets_->ChangeSetIndex(queue3, set);
135
136 WorkQueue* selected_work_queue;
137 EXPECT_TRUE(work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
138 EXPECT_EQ(queue3, selected_work_queue);
139 }
140
TEST_F(WorkQueueSetsTest,OnPopQueue)141 TEST_F(WorkQueueSetsTest, OnPopQueue) {
142 WorkQueue* queue1 = NewTaskQueue("queue1");
143 WorkQueue* queue2 = NewTaskQueue("queue2");
144 WorkQueue* queue3 = NewTaskQueue("queue3");
145 queue1->Push(FakeTaskWithEnqueueOrder(6));
146 queue2->Push(FakeTaskWithEnqueueOrder(1));
147 queue2->Push(FakeTaskWithEnqueueOrder(3));
148 queue3->Push(FakeTaskWithEnqueueOrder(4));
149 size_t set = 3;
150 work_queue_sets_->ChangeSetIndex(queue1, set);
151 work_queue_sets_->ChangeSetIndex(queue2, set);
152 work_queue_sets_->ChangeSetIndex(queue3, set);
153
154 WorkQueue* selected_work_queue;
155 EXPECT_TRUE(work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
156 EXPECT_EQ(queue2, selected_work_queue);
157
158 queue2->PopTaskForTesting();
159 work_queue_sets_->OnPopQueue(queue2);
160
161 EXPECT_TRUE(work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
162 EXPECT_EQ(queue2, selected_work_queue);
163 }
164
TEST_F(WorkQueueSetsTest,OnPopQueue_QueueBecomesEmpty)165 TEST_F(WorkQueueSetsTest, OnPopQueue_QueueBecomesEmpty) {
166 WorkQueue* queue1 = NewTaskQueue("queue1");
167 WorkQueue* queue2 = NewTaskQueue("queue2");
168 WorkQueue* queue3 = NewTaskQueue("queue3");
169 queue1->Push(FakeTaskWithEnqueueOrder(6));
170 queue2->Push(FakeTaskWithEnqueueOrder(5));
171 queue3->Push(FakeTaskWithEnqueueOrder(4));
172 size_t set = 4;
173 work_queue_sets_->ChangeSetIndex(queue1, set);
174 work_queue_sets_->ChangeSetIndex(queue2, set);
175 work_queue_sets_->ChangeSetIndex(queue3, set);
176
177 WorkQueue* selected_work_queue;
178 EXPECT_TRUE(work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
179 EXPECT_EQ(queue3, selected_work_queue);
180
181 queue3->PopTaskForTesting();
182 work_queue_sets_->OnPopQueue(queue3);
183
184 EXPECT_TRUE(work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
185 EXPECT_EQ(queue2, selected_work_queue);
186 }
187
TEST_F(WorkQueueSetsTest,GetOldestQueueInSet_MultipleAgesInSetIntegerRollover)188 TEST_F(WorkQueueSetsTest,
189 GetOldestQueueInSet_MultipleAgesInSetIntegerRollover) {
190 WorkQueue* queue1 = NewTaskQueue("queue1");
191 WorkQueue* queue2 = NewTaskQueue("queue2");
192 WorkQueue* queue3 = NewTaskQueue("queue3");
193 queue1->Push(FakeTaskWithEnqueueOrder(0x7ffffff1));
194 queue2->Push(FakeTaskWithEnqueueOrder(0x7ffffff0));
195 queue3->Push(FakeTaskWithEnqueueOrder(-0x7ffffff1));
196 size_t set = 1;
197 work_queue_sets_->ChangeSetIndex(queue1, set);
198 work_queue_sets_->ChangeSetIndex(queue2, set);
199 work_queue_sets_->ChangeSetIndex(queue3, set);
200
201 WorkQueue* selected_work_queue;
202 EXPECT_TRUE(work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
203 EXPECT_EQ(queue2, selected_work_queue);
204 }
205
TEST_F(WorkQueueSetsTest,GetOldestQueueInSet_MultipleAgesInSet_RemoveQueue)206 TEST_F(WorkQueueSetsTest, GetOldestQueueInSet_MultipleAgesInSet_RemoveQueue) {
207 WorkQueue* queue1 = NewTaskQueue("queue1");
208 WorkQueue* queue2 = NewTaskQueue("queue2");
209 WorkQueue* queue3 = NewTaskQueue("queue3");
210 queue1->Push(FakeTaskWithEnqueueOrder(6));
211 queue2->Push(FakeTaskWithEnqueueOrder(5));
212 queue3->Push(FakeTaskWithEnqueueOrder(4));
213 size_t set = 1;
214 work_queue_sets_->ChangeSetIndex(queue1, set);
215 work_queue_sets_->ChangeSetIndex(queue2, set);
216 work_queue_sets_->ChangeSetIndex(queue3, set);
217 work_queue_sets_->RemoveQueue(queue3);
218
219 WorkQueue* selected_work_queue;
220 EXPECT_TRUE(work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
221 EXPECT_EQ(queue2, selected_work_queue);
222 }
223
TEST_F(WorkQueueSetsTest,ChangeSetIndex_Complex)224 TEST_F(WorkQueueSetsTest, ChangeSetIndex_Complex) {
225 WorkQueue* queue1 = NewTaskQueue("queue1");
226 WorkQueue* queue2 = NewTaskQueue("queue2");
227 WorkQueue* queue3 = NewTaskQueue("queue3");
228 WorkQueue* queue4 = NewTaskQueue("queue4");
229 queue1->Push(FakeTaskWithEnqueueOrder(6));
230 queue2->Push(FakeTaskWithEnqueueOrder(5));
231 queue3->Push(FakeTaskWithEnqueueOrder(4));
232 queue4->Push(FakeTaskWithEnqueueOrder(3));
233 size_t set1 = 1;
234 size_t set2 = 2;
235 work_queue_sets_->ChangeSetIndex(queue1, set1);
236 work_queue_sets_->ChangeSetIndex(queue2, set1);
237 work_queue_sets_->ChangeSetIndex(queue3, set2);
238 work_queue_sets_->ChangeSetIndex(queue4, set2);
239
240 WorkQueue* selected_work_queue;
241 EXPECT_TRUE(
242 work_queue_sets_->GetOldestQueueInSet(set1, &selected_work_queue));
243 EXPECT_EQ(queue2, selected_work_queue);
244
245 EXPECT_TRUE(
246 work_queue_sets_->GetOldestQueueInSet(set2, &selected_work_queue));
247 EXPECT_EQ(queue4, selected_work_queue);
248
249 work_queue_sets_->ChangeSetIndex(queue4, set1);
250
251 EXPECT_TRUE(
252 work_queue_sets_->GetOldestQueueInSet(set1, &selected_work_queue));
253 EXPECT_EQ(queue4, selected_work_queue);
254
255 EXPECT_TRUE(
256 work_queue_sets_->GetOldestQueueInSet(set2, &selected_work_queue));
257 EXPECT_EQ(queue3, selected_work_queue);
258 }
259
TEST_F(WorkQueueSetsTest,IsSetEmpty_NoWork)260 TEST_F(WorkQueueSetsTest, IsSetEmpty_NoWork) {
261 size_t set = 2;
262 EXPECT_TRUE(work_queue_sets_->IsSetEmpty(set));
263
264 WorkQueue* work_queue = NewTaskQueue("queue");
265 work_queue_sets_->ChangeSetIndex(work_queue, set);
266 EXPECT_TRUE(work_queue_sets_->IsSetEmpty(set));
267 }
268
TEST_F(WorkQueueSetsTest,IsSetEmpty_Work)269 TEST_F(WorkQueueSetsTest, IsSetEmpty_Work) {
270 size_t set = 2;
271 EXPECT_TRUE(work_queue_sets_->IsSetEmpty(set));
272
273 WorkQueue* work_queue = NewTaskQueue("queue");
274 work_queue->Push(FakeTaskWithEnqueueOrder(1));
275 work_queue_sets_->ChangeSetIndex(work_queue, set);
276 EXPECT_FALSE(work_queue_sets_->IsSetEmpty(set));
277
278 work_queue->PopTaskForTesting();
279 work_queue_sets_->OnPopQueue(work_queue);
280 EXPECT_TRUE(work_queue_sets_->IsSetEmpty(set));
281 }
282
TEST_F(WorkQueueSetsTest,BlockQueuesByFence)283 TEST_F(WorkQueueSetsTest, BlockQueuesByFence) {
284 WorkQueue* queue1 = NewTaskQueue("queue1");
285 WorkQueue* queue2 = NewTaskQueue("queue2");
286
287 queue1->Push(FakeTaskWithEnqueueOrder(6));
288 queue2->Push(FakeTaskWithEnqueueOrder(7));
289 queue1->Push(FakeTaskWithEnqueueOrder(8));
290 queue2->Push(FakeTaskWithEnqueueOrder(9));
291
292 size_t set = TaskQueue::kControlPriority;
293
294 WorkQueue* selected_work_queue;
295 EXPECT_TRUE(work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
296 EXPECT_EQ(selected_work_queue, queue1);
297
298 queue1->InsertFence(EnqueueOrder::blocking_fence());
299
300 EXPECT_TRUE(work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
301 EXPECT_EQ(selected_work_queue, queue2);
302 }
303
TEST_F(WorkQueueSetsTest,PushNonNestableTaskToFront)304 TEST_F(WorkQueueSetsTest, PushNonNestableTaskToFront) {
305 WorkQueue* queue1 = NewTaskQueue("queue1");
306 WorkQueue* queue2 = NewTaskQueue("queue2");
307 WorkQueue* queue3 = NewTaskQueue("queue3");
308 queue1->Push(FakeTaskWithEnqueueOrder(6));
309 queue2->Push(FakeTaskWithEnqueueOrder(5));
310 queue3->Push(FakeTaskWithEnqueueOrder(4));
311 size_t set = 4;
312 work_queue_sets_->ChangeSetIndex(queue1, set);
313 work_queue_sets_->ChangeSetIndex(queue2, set);
314 work_queue_sets_->ChangeSetIndex(queue3, set);
315
316 WorkQueue* selected_work_queue;
317 EXPECT_TRUE(work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
318 EXPECT_EQ(queue3, selected_work_queue);
319
320 queue1->PushNonNestableTaskToFront(FakeNonNestableTaskWithEnqueueOrder(2));
321
322 EXPECT_TRUE(work_queue_sets_->GetOldestQueueInSet(set, &selected_work_queue));
323 EXPECT_EQ(queue1, selected_work_queue);
324 }
325
326 } // namespace internal
327 } // namespace sequence_manager
328 } // namespace base
329