1 // Copyright 2015 The Chromium Authors
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.h"
6
7 #include <stddef.h>
8 #include <memory>
9
10 #include "base/functional/bind.h"
11 #include "base/task/common/lazy_now.h"
12 #include "base/task/sequence_manager/enqueue_order.h"
13 #include "base/task/sequence_manager/fence.h"
14 #include "base/task/sequence_manager/sequence_manager.h"
15 #include "base/task/sequence_manager/task_order.h"
16 #include "base/task/sequence_manager/task_queue_impl.h"
17 #include "base/task/sequence_manager/work_queue_sets.h"
18 #include "base/time/time.h"
19 #include "testing/gmock/include/gmock/gmock.h"
20 #include "third_party/abseil-cpp/absl/types/optional.h"
21
22 namespace base {
23 namespace sequence_manager {
24 namespace internal {
25
26 namespace {
27
28 class MockObserver : public WorkQueueSets::Observer {
29 MOCK_METHOD1(WorkQueueSetBecameEmpty, void(size_t set_index));
30 MOCK_METHOD1(WorkQueueSetBecameNonEmpty, void(size_t set_index));
31 };
32
NopTask()33 void NopTask() {}
34
35 struct Cancelable {
Cancelablebase::sequence_manager::internal::__anona3dd0ee70111::Cancelable36 Cancelable() {}
37
NopTaskbase::sequence_manager::internal::__anona3dd0ee70111::Cancelable38 void NopTask() {}
39
40 WeakPtrFactory<Cancelable> weak_ptr_factory{this};
41 };
42
43 } // namespace
44
45 class WorkQueueTest : public testing::Test {
46 public:
WorkQueueTest()47 WorkQueueTest() : WorkQueueTest(WorkQueue::QueueType::kImmediate) {}
48
WorkQueueTest(WorkQueue::QueueType queue_type)49 explicit WorkQueueTest(WorkQueue::QueueType queue_type)
50 : queue_type_(queue_type) {}
51
SetUp()52 void SetUp() override {
53 task_queue_ = std::make_unique<TaskQueueImpl>(
54 /*sequence_manager=*/nullptr, /*wake_up_queue=*/nullptr,
55 TaskQueue::Spec(QueueName::TEST_TQ));
56
57 work_queue_ =
58 std::make_unique<WorkQueue>(task_queue_.get(), "test", queue_type_);
59 mock_observer_ = std::make_unique<MockObserver>();
60 work_queue_sets_ = std::make_unique<WorkQueueSets>(
61 "test", mock_observer_.get(), SequenceManager::Settings());
62 work_queue_sets_->AddQueue(work_queue_.get(), 0);
63 }
64
TearDown()65 void TearDown() override {
66 work_queue_sets_->RemoveQueue(work_queue_.get());
67 task_queue_->UnregisterTaskQueue();
68 }
69
70 protected:
FakeCancelableTaskWithEnqueueOrder(int enqueue_order,WeakPtr<Cancelable> weak_ptr)71 Task FakeCancelableTaskWithEnqueueOrder(int enqueue_order,
72 WeakPtr<Cancelable> weak_ptr) {
73 Task fake_task(PostedTask(nullptr, BindOnce(&Cancelable::NopTask, weak_ptr),
74 FROM_HERE),
75 EnqueueOrder(),
76 EnqueueOrder::FromIntForTesting(enqueue_order));
77 return fake_task;
78 }
79
FakeTaskWithEnqueueOrder(int enqueue_order)80 Task FakeTaskWithEnqueueOrder(int enqueue_order) {
81 Task fake_task(PostedTask(nullptr, BindOnce(&NopTask), FROM_HERE),
82 EnqueueOrder(),
83 EnqueueOrder::FromIntForTesting(enqueue_order));
84 return fake_task;
85 }
86
FakeNonNestableTaskWithEnqueueOrder(int enqueue_order)87 Task FakeNonNestableTaskWithEnqueueOrder(int enqueue_order) {
88 Task fake_task(PostedTask(nullptr, BindOnce(&NopTask), FROM_HERE),
89 EnqueueOrder(),
90 EnqueueOrder::FromIntForTesting(enqueue_order));
91 fake_task.nestable = Nestable::kNonNestable;
92 return fake_task;
93 }
94
FakeTaskWithTaskOrder(TaskOrder task_order)95 Task FakeTaskWithTaskOrder(TaskOrder task_order) {
96 Task fake_task(PostedTask(nullptr, BindOnce(&NopTask), FROM_HERE,
97 task_order.delayed_run_time(),
98 subtle::DelayPolicy::kFlexibleNoSooner),
99 EnqueueOrder::FromIntForTesting(task_order.sequence_num()),
100 task_order.enqueue_order(), TimeTicks() + Milliseconds(1));
101 return fake_task;
102 }
103
CreateFenceWithEnqueueOrder(int enqueue_order)104 Fence CreateFenceWithEnqueueOrder(int enqueue_order) {
105 return Fence(TaskOrder::CreateForTesting(
106 EnqueueOrder::FromIntForTesting(enqueue_order)));
107 }
108
GetOldestQueueInSet(int set)109 WorkQueue* GetOldestQueueInSet(int set) {
110 if (auto queue_and_task_order =
111 work_queue_sets_->GetOldestQueueAndTaskOrderInSet(set)) {
112 return queue_and_task_order->queue;
113 }
114 return nullptr;
115 }
116
117 std::unique_ptr<MockObserver> mock_observer_;
118 std::unique_ptr<TaskQueueImpl> task_queue_;
119 std::unique_ptr<WorkQueue> work_queue_;
120 std::unique_ptr<WorkQueueSets> work_queue_sets_;
121 std::unique_ptr<TaskQueueImpl::TaskDeque> incoming_queue_;
122
123 private:
124 const WorkQueue::QueueType queue_type_;
125 };
126
127 class DelayedWorkQueueTest : public WorkQueueTest {
128 public:
DelayedWorkQueueTest()129 DelayedWorkQueueTest() : WorkQueueTest(WorkQueue::QueueType::kDelayed) {}
130 };
131
TEST_F(WorkQueueTest,Empty)132 TEST_F(WorkQueueTest, Empty) {
133 EXPECT_TRUE(work_queue_->Empty());
134 work_queue_->Push(FakeTaskWithEnqueueOrder(1));
135 EXPECT_FALSE(work_queue_->Empty());
136 }
137
TEST_F(WorkQueueTest,Empty_IgnoresFences)138 TEST_F(WorkQueueTest, Empty_IgnoresFences) {
139 work_queue_->Push(FakeTaskWithEnqueueOrder(1));
140 work_queue_->InsertFence(Fence::BlockingFence());
141 EXPECT_FALSE(work_queue_->Empty());
142 }
143
TEST_F(WorkQueueTest,GetFrontTaskOrderQueueEmpty)144 TEST_F(WorkQueueTest, GetFrontTaskOrderQueueEmpty) {
145 EXPECT_FALSE(work_queue_->GetFrontTaskOrder());
146 }
147
TEST_F(WorkQueueTest,GetFrontTaskOrder)148 TEST_F(WorkQueueTest, GetFrontTaskOrder) {
149 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
150 work_queue_->Push(FakeTaskWithEnqueueOrder(3));
151 work_queue_->Push(FakeTaskWithEnqueueOrder(4));
152
153 absl::optional<TaskOrder> task_order = work_queue_->GetFrontTaskOrder();
154 EXPECT_TRUE(task_order);
155 EXPECT_EQ(2ull, task_order->enqueue_order());
156 }
157
TEST_F(WorkQueueTest,GetFrontTaskQueueEmpty)158 TEST_F(WorkQueueTest, GetFrontTaskQueueEmpty) {
159 EXPECT_EQ(nullptr, work_queue_->GetFrontTask());
160 }
161
TEST_F(WorkQueueTest,GetFrontTask)162 TEST_F(WorkQueueTest, GetFrontTask) {
163 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
164 work_queue_->Push(FakeTaskWithEnqueueOrder(3));
165 work_queue_->Push(FakeTaskWithEnqueueOrder(4));
166
167 ASSERT_NE(nullptr, work_queue_->GetFrontTask());
168 EXPECT_EQ(2ull, work_queue_->GetFrontTask()->enqueue_order());
169 }
170
TEST_F(WorkQueueTest,GetBackTask_Empty)171 TEST_F(WorkQueueTest, GetBackTask_Empty) {
172 EXPECT_EQ(nullptr, work_queue_->GetBackTask());
173 }
174
TEST_F(WorkQueueTest,GetBackTask)175 TEST_F(WorkQueueTest, GetBackTask) {
176 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
177 work_queue_->Push(FakeTaskWithEnqueueOrder(3));
178 work_queue_->Push(FakeTaskWithEnqueueOrder(4));
179
180 ASSERT_NE(nullptr, work_queue_->GetBackTask());
181 EXPECT_EQ(4ull, work_queue_->GetBackTask()->enqueue_order());
182 }
183
TEST_F(WorkQueueTest,Push)184 TEST_F(WorkQueueTest, Push) {
185 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
186
187 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
188 EXPECT_EQ(work_queue_.get(), GetOldestQueueInSet(0));
189 }
190
TEST_F(WorkQueueTest,PushMultiple)191 TEST_F(WorkQueueTest, PushMultiple) {
192 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
193
194 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
195 work_queue_->Push(FakeTaskWithEnqueueOrder(3));
196 work_queue_->Push(FakeTaskWithEnqueueOrder(4));
197 EXPECT_EQ(work_queue_.get(), GetOldestQueueInSet(0));
198 EXPECT_EQ(2ull, work_queue_->GetFrontTask()->enqueue_order());
199 EXPECT_EQ(4ull, work_queue_->GetBackTask()->enqueue_order());
200 }
201
TEST_F(WorkQueueTest,PushAfterFenceHit)202 TEST_F(WorkQueueTest, PushAfterFenceHit) {
203 work_queue_->InsertFence(Fence::BlockingFence());
204 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
205
206 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
207 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
208 }
209
TEST_F(WorkQueueTest,CreateTaskPusherNothingPushed)210 TEST_F(WorkQueueTest, CreateTaskPusherNothingPushed) {
211 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
212 { WorkQueue::TaskPusher task_pusher(work_queue_->CreateTaskPusher()); }
213 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
214 }
215
TEST_F(WorkQueueTest,CreateTaskPusherOneTask)216 TEST_F(WorkQueueTest, CreateTaskPusherOneTask) {
217 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
218 {
219 WorkQueue::TaskPusher task_pusher(work_queue_->CreateTaskPusher());
220 Task task = FakeTaskWithEnqueueOrder(2);
221 task_pusher.Push(std::move(task));
222 }
223 EXPECT_EQ(work_queue_.get(), GetOldestQueueInSet(0));
224 }
225
TEST_F(WorkQueueTest,CreateTaskPusherThreeTasks)226 TEST_F(WorkQueueTest, CreateTaskPusherThreeTasks) {
227 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
228 {
229 WorkQueue::TaskPusher task_pusher(work_queue_->CreateTaskPusher());
230 task_pusher.Push(FakeTaskWithEnqueueOrder(2));
231 task_pusher.Push(FakeTaskWithEnqueueOrder(3));
232 task_pusher.Push(FakeTaskWithEnqueueOrder(4));
233 }
234 EXPECT_EQ(work_queue_.get(), GetOldestQueueInSet(0));
235 EXPECT_EQ(2ull, work_queue_->GetFrontTask()->enqueue_order());
236 EXPECT_EQ(4ull, work_queue_->GetBackTask()->enqueue_order());
237 }
238
TEST_F(WorkQueueTest,CreateTaskPusherAfterFenceHit)239 TEST_F(WorkQueueTest, CreateTaskPusherAfterFenceHit) {
240 work_queue_->InsertFence(Fence::BlockingFence());
241 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
242 {
243 WorkQueue::TaskPusher task_pusher(work_queue_->CreateTaskPusher());
244 task_pusher.Push(FakeTaskWithEnqueueOrder(2));
245 task_pusher.Push(FakeTaskWithEnqueueOrder(3));
246 task_pusher.Push(FakeTaskWithEnqueueOrder(4));
247 }
248 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
249 }
250
TEST_F(WorkQueueTest,PushNonNestableTaskToFront)251 TEST_F(WorkQueueTest, PushNonNestableTaskToFront) {
252 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
253
254 work_queue_->PushNonNestableTaskToFront(
255 FakeNonNestableTaskWithEnqueueOrder(3));
256 EXPECT_EQ(work_queue_.get(), GetOldestQueueInSet(0));
257
258 work_queue_->PushNonNestableTaskToFront(
259 FakeNonNestableTaskWithEnqueueOrder(2));
260 EXPECT_EQ(2ull, work_queue_->GetFrontTask()->enqueue_order());
261 EXPECT_EQ(3ull, work_queue_->GetBackTask()->enqueue_order());
262 }
263
TEST_F(WorkQueueTest,PushNonNestableTaskToFrontAfterFenceHit)264 TEST_F(WorkQueueTest, PushNonNestableTaskToFrontAfterFenceHit) {
265 work_queue_->InsertFence(Fence::BlockingFence());
266 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
267
268 work_queue_->PushNonNestableTaskToFront(
269 FakeNonNestableTaskWithEnqueueOrder(2));
270 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
271 }
272
TEST_F(WorkQueueTest,PushNonNestableTaskToFrontBeforeFenceHit)273 TEST_F(WorkQueueTest, PushNonNestableTaskToFrontBeforeFenceHit) {
274 work_queue_->InsertFence(CreateFenceWithEnqueueOrder(3));
275 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
276
277 work_queue_->PushNonNestableTaskToFront(
278 FakeNonNestableTaskWithEnqueueOrder(2));
279 EXPECT_EQ(work_queue_.get(), GetOldestQueueInSet(0));
280 }
281
TEST_F(WorkQueueTest,TakeImmediateIncomingQueueTasks)282 TEST_F(WorkQueueTest, TakeImmediateIncomingQueueTasks) {
283 task_queue_->PushImmediateIncomingTaskForTest(FakeTaskWithEnqueueOrder(2));
284 task_queue_->PushImmediateIncomingTaskForTest(FakeTaskWithEnqueueOrder(3));
285 task_queue_->PushImmediateIncomingTaskForTest(FakeTaskWithEnqueueOrder(4));
286 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
287 EXPECT_TRUE(work_queue_->Empty());
288
289 work_queue_->TakeImmediateIncomingQueueTasks();
290 EXPECT_EQ(work_queue_.get(), GetOldestQueueInSet(0));
291 EXPECT_FALSE(work_queue_->Empty());
292
293 ASSERT_NE(nullptr, work_queue_->GetFrontTask());
294 EXPECT_EQ(2ull, work_queue_->GetFrontTask()->enqueue_order());
295
296 ASSERT_NE(nullptr, work_queue_->GetBackTask());
297 EXPECT_EQ(4ull, work_queue_->GetBackTask()->enqueue_order());
298 }
299
TEST_F(WorkQueueTest,TakeImmediateIncomingQueueTasksAfterFenceHit)300 TEST_F(WorkQueueTest, TakeImmediateIncomingQueueTasksAfterFenceHit) {
301 work_queue_->InsertFence(Fence::BlockingFence());
302 task_queue_->PushImmediateIncomingTaskForTest(FakeTaskWithEnqueueOrder(2));
303 task_queue_->PushImmediateIncomingTaskForTest(FakeTaskWithEnqueueOrder(3));
304 task_queue_->PushImmediateIncomingTaskForTest(FakeTaskWithEnqueueOrder(4));
305 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
306 EXPECT_TRUE(work_queue_->Empty());
307
308 work_queue_->TakeImmediateIncomingQueueTasks();
309 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
310 EXPECT_FALSE(work_queue_->Empty());
311
312 ASSERT_NE(nullptr, work_queue_->GetFrontTask());
313 EXPECT_EQ(2ull, work_queue_->GetFrontTask()->enqueue_order());
314
315 ASSERT_NE(nullptr, work_queue_->GetBackTask());
316 EXPECT_EQ(4ull, work_queue_->GetBackTask()->enqueue_order());
317 }
318
TEST_F(WorkQueueTest,TakeTaskFromWorkQueue)319 TEST_F(WorkQueueTest, TakeTaskFromWorkQueue) {
320 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
321 work_queue_->Push(FakeTaskWithEnqueueOrder(3));
322 work_queue_->Push(FakeTaskWithEnqueueOrder(4));
323 EXPECT_EQ(work_queue_.get(), GetOldestQueueInSet(0));
324 EXPECT_FALSE(work_queue_->Empty());
325
326 EXPECT_EQ(2ull, work_queue_->TakeTaskFromWorkQueue().enqueue_order());
327 EXPECT_EQ(3ull, work_queue_->TakeTaskFromWorkQueue().enqueue_order());
328 EXPECT_EQ(4ull, work_queue_->TakeTaskFromWorkQueue().enqueue_order());
329
330 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
331 EXPECT_TRUE(work_queue_->Empty());
332 }
333
TEST_F(WorkQueueTest,TakeTaskFromWorkQueue_HitFence)334 TEST_F(WorkQueueTest, TakeTaskFromWorkQueue_HitFence) {
335 work_queue_->InsertFence(CreateFenceWithEnqueueOrder(3));
336 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
337 work_queue_->Push(FakeTaskWithEnqueueOrder(4));
338 EXPECT_FALSE(work_queue_->BlockedByFence());
339
340 EXPECT_EQ(work_queue_.get(), GetOldestQueueInSet(0));
341 EXPECT_FALSE(work_queue_->Empty());
342 EXPECT_FALSE(work_queue_->BlockedByFence());
343
344 EXPECT_EQ(2ull, work_queue_->TakeTaskFromWorkQueue().enqueue_order());
345 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
346 EXPECT_FALSE(work_queue_->Empty());
347 EXPECT_TRUE(work_queue_->BlockedByFence());
348 }
349
TEST_F(WorkQueueTest,InsertFenceBeforeEnqueueing)350 TEST_F(WorkQueueTest, InsertFenceBeforeEnqueueing) {
351 EXPECT_FALSE(work_queue_->InsertFence(Fence::BlockingFence()));
352 EXPECT_TRUE(work_queue_->BlockedByFence());
353
354 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
355 work_queue_->Push(FakeTaskWithEnqueueOrder(3));
356 work_queue_->Push(FakeTaskWithEnqueueOrder(4));
357
358 EXPECT_FALSE(work_queue_->GetFrontTaskOrder());
359 }
360
TEST_F(WorkQueueTest,InsertFenceAfterEnqueueingNonBlocking)361 TEST_F(WorkQueueTest, InsertFenceAfterEnqueueingNonBlocking) {
362 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
363 work_queue_->Push(FakeTaskWithEnqueueOrder(3));
364 work_queue_->Push(FakeTaskWithEnqueueOrder(4));
365
366 EXPECT_FALSE(work_queue_->InsertFence(CreateFenceWithEnqueueOrder(5)));
367 EXPECT_FALSE(work_queue_->BlockedByFence());
368
369 EXPECT_TRUE(work_queue_->GetFrontTaskOrder());
370 EXPECT_EQ(2ull, work_queue_->TakeTaskFromWorkQueue().enqueue_order());
371 }
372
TEST_F(WorkQueueTest,InsertFenceAfterEnqueueing)373 TEST_F(WorkQueueTest, InsertFenceAfterEnqueueing) {
374 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
375 work_queue_->Push(FakeTaskWithEnqueueOrder(3));
376 work_queue_->Push(FakeTaskWithEnqueueOrder(4));
377
378 // NB in reality a fence will always be greater than any currently enqueued
379 // tasks.
380 EXPECT_FALSE(work_queue_->InsertFence(Fence::BlockingFence()));
381 EXPECT_TRUE(work_queue_->BlockedByFence());
382
383 EXPECT_FALSE(work_queue_->GetFrontTaskOrder());
384 }
385
TEST_F(WorkQueueTest,InsertNewFence)386 TEST_F(WorkQueueTest, InsertNewFence) {
387 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
388 work_queue_->Push(FakeTaskWithEnqueueOrder(4));
389 work_queue_->Push(FakeTaskWithEnqueueOrder(5));
390
391 EXPECT_FALSE(work_queue_->InsertFence(CreateFenceWithEnqueueOrder(3)));
392 EXPECT_FALSE(work_queue_->BlockedByFence());
393
394 // Note until TakeTaskFromWorkQueue() is called we don't hit the fence.
395 absl::optional<TaskOrder> task_order = work_queue_->GetFrontTaskOrder();
396 EXPECT_TRUE(task_order);
397 EXPECT_EQ(2ull, task_order->enqueue_order());
398
399 EXPECT_EQ(2ull, work_queue_->TakeTaskFromWorkQueue().enqueue_order());
400 EXPECT_FALSE(work_queue_->GetFrontTaskOrder());
401 EXPECT_TRUE(work_queue_->BlockedByFence());
402
403 // Inserting the new fence should temporarily unblock the queue until the new
404 // one is hit.
405 EXPECT_TRUE(work_queue_->InsertFence(CreateFenceWithEnqueueOrder(6)));
406 EXPECT_FALSE(work_queue_->BlockedByFence());
407
408 task_order = work_queue_->GetFrontTaskOrder();
409 EXPECT_TRUE(task_order);
410 EXPECT_EQ(4ull, task_order->enqueue_order());
411 EXPECT_EQ(4ull, work_queue_->TakeTaskFromWorkQueue().enqueue_order());
412 EXPECT_TRUE(work_queue_->GetFrontTaskOrder());
413 EXPECT_FALSE(work_queue_->BlockedByFence());
414 }
415
TEST_F(WorkQueueTest,PushWithNonEmptyQueueDoesNotHitFence)416 TEST_F(WorkQueueTest, PushWithNonEmptyQueueDoesNotHitFence) {
417 work_queue_->Push(FakeTaskWithEnqueueOrder(1));
418 EXPECT_FALSE(work_queue_->InsertFence(CreateFenceWithEnqueueOrder(2)));
419 work_queue_->Push(FakeTaskWithEnqueueOrder(3));
420 EXPECT_FALSE(work_queue_->BlockedByFence());
421 }
422
TEST_F(WorkQueueTest,RemoveFence)423 TEST_F(WorkQueueTest, RemoveFence) {
424 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
425 work_queue_->Push(FakeTaskWithEnqueueOrder(4));
426 work_queue_->Push(FakeTaskWithEnqueueOrder(5));
427 work_queue_->InsertFence(CreateFenceWithEnqueueOrder(3));
428 EXPECT_EQ(work_queue_.get(), GetOldestQueueInSet(0));
429 EXPECT_FALSE(work_queue_->Empty());
430
431 EXPECT_EQ(2ull, work_queue_->TakeTaskFromWorkQueue().enqueue_order());
432 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
433 EXPECT_FALSE(work_queue_->Empty());
434 EXPECT_TRUE(work_queue_->BlockedByFence());
435
436 EXPECT_TRUE(work_queue_->RemoveFence());
437 EXPECT_EQ(4ull, work_queue_->TakeTaskFromWorkQueue().enqueue_order());
438 EXPECT_EQ(work_queue_.get(), GetOldestQueueInSet(0));
439 EXPECT_FALSE(work_queue_->BlockedByFence());
440 }
441
TEST_F(WorkQueueTest,RemoveFenceButNoFence)442 TEST_F(WorkQueueTest, RemoveFenceButNoFence) {
443 EXPECT_FALSE(work_queue_->RemoveFence());
444 }
445
TEST_F(WorkQueueTest,RemoveFenceNothingUnblocked)446 TEST_F(WorkQueueTest, RemoveFenceNothingUnblocked) {
447 EXPECT_FALSE(work_queue_->InsertFence(Fence::BlockingFence()));
448 EXPECT_TRUE(work_queue_->BlockedByFence());
449
450 EXPECT_FALSE(work_queue_->RemoveFence());
451 EXPECT_FALSE(work_queue_->BlockedByFence());
452 }
453
TEST_F(WorkQueueTest,BlockedByFence)454 TEST_F(WorkQueueTest, BlockedByFence) {
455 EXPECT_FALSE(work_queue_->BlockedByFence());
456 EXPECT_FALSE(work_queue_->InsertFence(Fence::BlockingFence()));
457 EXPECT_TRUE(work_queue_->BlockedByFence());
458 }
459
TEST_F(WorkQueueTest,BlockedByFencePopBecomesEmpty)460 TEST_F(WorkQueueTest, BlockedByFencePopBecomesEmpty) {
461 work_queue_->Push(FakeTaskWithEnqueueOrder(1));
462 EXPECT_FALSE(work_queue_->InsertFence(CreateFenceWithEnqueueOrder(2)));
463 EXPECT_FALSE(work_queue_->BlockedByFence());
464
465 EXPECT_EQ(1ull, work_queue_->TakeTaskFromWorkQueue().enqueue_order());
466 EXPECT_TRUE(work_queue_->BlockedByFence());
467 }
468
TEST_F(WorkQueueTest,BlockedByFencePop)469 TEST_F(WorkQueueTest, BlockedByFencePop) {
470 work_queue_->Push(FakeTaskWithEnqueueOrder(1));
471 EXPECT_FALSE(work_queue_->InsertFence(CreateFenceWithEnqueueOrder(2)));
472 EXPECT_FALSE(work_queue_->BlockedByFence());
473
474 work_queue_->Push(FakeTaskWithEnqueueOrder(3));
475 EXPECT_FALSE(work_queue_->BlockedByFence());
476
477 EXPECT_EQ(1ull, work_queue_->TakeTaskFromWorkQueue().enqueue_order());
478 EXPECT_TRUE(work_queue_->BlockedByFence());
479 }
480
TEST_F(WorkQueueTest,InitiallyEmptyBlockedByFenceNewFenceUnblocks)481 TEST_F(WorkQueueTest, InitiallyEmptyBlockedByFenceNewFenceUnblocks) {
482 EXPECT_FALSE(work_queue_->InsertFence(Fence::BlockingFence()));
483 EXPECT_TRUE(work_queue_->BlockedByFence());
484
485 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
486 EXPECT_TRUE(work_queue_->InsertFence(CreateFenceWithEnqueueOrder(3)));
487 EXPECT_FALSE(work_queue_->BlockedByFence());
488 }
489
TEST_F(WorkQueueTest,BlockedByFenceNewFenceUnblocks)490 TEST_F(WorkQueueTest, BlockedByFenceNewFenceUnblocks) {
491 work_queue_->Push(FakeTaskWithEnqueueOrder(1));
492 EXPECT_FALSE(work_queue_->InsertFence(CreateFenceWithEnqueueOrder(2)));
493 EXPECT_FALSE(work_queue_->BlockedByFence());
494
495 work_queue_->Push(FakeTaskWithEnqueueOrder(3));
496 EXPECT_FALSE(work_queue_->BlockedByFence());
497
498 EXPECT_EQ(1ull, work_queue_->TakeTaskFromWorkQueue().enqueue_order());
499 EXPECT_TRUE(work_queue_->BlockedByFence());
500
501 EXPECT_TRUE(work_queue_->InsertFence(CreateFenceWithEnqueueOrder(4)));
502 EXPECT_FALSE(work_queue_->BlockedByFence());
503 }
504
TEST_F(WorkQueueTest,InsertFenceAfterEnqueuing)505 TEST_F(WorkQueueTest, InsertFenceAfterEnqueuing) {
506 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
507 work_queue_->Push(FakeTaskWithEnqueueOrder(3));
508 work_queue_->Push(FakeTaskWithEnqueueOrder(4));
509 EXPECT_FALSE(work_queue_->BlockedByFence());
510
511 EXPECT_FALSE(work_queue_->InsertFence(Fence::BlockingFence()));
512 EXPECT_TRUE(work_queue_->BlockedByFence());
513
514 EXPECT_FALSE(work_queue_->GetFrontTaskOrder());
515 }
516
TEST_F(WorkQueueTest,RemoveAllCanceledTasksFromFront)517 TEST_F(WorkQueueTest, RemoveAllCanceledTasksFromFront) {
518 {
519 Cancelable cancelable;
520 work_queue_->Push(FakeCancelableTaskWithEnqueueOrder(
521 2, cancelable.weak_ptr_factory.GetWeakPtr()));
522 work_queue_->Push(FakeCancelableTaskWithEnqueueOrder(
523 3, cancelable.weak_ptr_factory.GetWeakPtr()));
524 work_queue_->Push(FakeCancelableTaskWithEnqueueOrder(
525 4, cancelable.weak_ptr_factory.GetWeakPtr()));
526 work_queue_->Push(FakeTaskWithEnqueueOrder(5));
527 }
528 EXPECT_TRUE(work_queue_->RemoveAllCanceledTasksFromFront());
529
530 absl::optional<TaskOrder> task_order = work_queue_->GetFrontTaskOrder();
531 EXPECT_TRUE(task_order);
532 EXPECT_EQ(5ull, task_order->enqueue_order());
533 }
534
TEST_F(WorkQueueTest,RemoveAllCanceledTasksFromFrontTasksNotCanceled)535 TEST_F(WorkQueueTest, RemoveAllCanceledTasksFromFrontTasksNotCanceled) {
536 {
537 Cancelable cancelable;
538 work_queue_->Push(FakeCancelableTaskWithEnqueueOrder(
539 2, cancelable.weak_ptr_factory.GetWeakPtr()));
540 work_queue_->Push(FakeCancelableTaskWithEnqueueOrder(
541 3, cancelable.weak_ptr_factory.GetWeakPtr()));
542 work_queue_->Push(FakeCancelableTaskWithEnqueueOrder(
543 4, cancelable.weak_ptr_factory.GetWeakPtr()));
544 work_queue_->Push(FakeTaskWithEnqueueOrder(5));
545 EXPECT_FALSE(work_queue_->RemoveAllCanceledTasksFromFront());
546
547 absl::optional<TaskOrder> task_order = work_queue_->GetFrontTaskOrder();
548 EXPECT_TRUE(task_order);
549 EXPECT_EQ(2ull, task_order->enqueue_order());
550 }
551 }
552
TEST_F(WorkQueueTest,RemoveAllCanceledTasksFromFrontQueueBlockedByFence)553 TEST_F(WorkQueueTest, RemoveAllCanceledTasksFromFrontQueueBlockedByFence) {
554 {
555 Cancelable cancelable;
556 work_queue_->Push(FakeCancelableTaskWithEnqueueOrder(
557 2, cancelable.weak_ptr_factory.GetWeakPtr()));
558 work_queue_->Push(FakeCancelableTaskWithEnqueueOrder(
559 3, cancelable.weak_ptr_factory.GetWeakPtr()));
560 work_queue_->Push(FakeCancelableTaskWithEnqueueOrder(
561 4, cancelable.weak_ptr_factory.GetWeakPtr()));
562 work_queue_->Push(FakeTaskWithEnqueueOrder(5));
563 }
564
565 EXPECT_FALSE(work_queue_->InsertFence(Fence::BlockingFence()));
566 EXPECT_TRUE(work_queue_->BlockedByFence());
567
568 EXPECT_TRUE(work_queue_->RemoveAllCanceledTasksFromFront());
569
570 EXPECT_FALSE(work_queue_->GetFrontTaskOrder());
571 }
572
TEST_F(WorkQueueTest,CollectTasksOlderThan)573 TEST_F(WorkQueueTest, CollectTasksOlderThan) {
574 work_queue_->Push(FakeTaskWithEnqueueOrder(2));
575 work_queue_->Push(FakeTaskWithEnqueueOrder(3));
576 work_queue_->Push(FakeTaskWithEnqueueOrder(4));
577
578 std::vector<const Task*> result;
579 work_queue_->CollectTasksOlderThan(
580 TaskOrder::CreateForTesting(EnqueueOrder::FromIntForTesting(4),
581 TimeTicks(), 0),
582 &result);
583
584 ASSERT_EQ(2u, result.size());
585 EXPECT_EQ(2u, result[0]->enqueue_order());
586 EXPECT_EQ(3u, result[1]->enqueue_order());
587 }
588
TEST_F(DelayedWorkQueueTest,PushMultipleWithSameEnqueueOrder)589 TEST_F(DelayedWorkQueueTest, PushMultipleWithSameEnqueueOrder) {
590 const EnqueueOrder kEnqueueOrder = EnqueueOrder::FromIntForTesting(5);
591 TaskOrder task_orders[3] = {
592 TaskOrder::CreateForTesting(kEnqueueOrder, TimeTicks() + Seconds(1),
593 /*sequence_num=*/4),
594 TaskOrder::CreateForTesting(kEnqueueOrder, TimeTicks() + Seconds(2),
595 /*sequence_num=*/3),
596 TaskOrder::CreateForTesting(kEnqueueOrder, TimeTicks() + Seconds(3),
597 /*sequence_num=*/2),
598 };
599
600 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
601 for (auto& task_order : task_orders) {
602 work_queue_->Push(FakeTaskWithTaskOrder(task_order));
603 }
604
605 EXPECT_TRUE(task_orders[0] == work_queue_->GetFrontTaskOrder());
606 EXPECT_TRUE(task_orders[0] == work_queue_->GetFrontTask()->task_order());
607
608 EXPECT_TRUE(task_orders[2] == work_queue_->GetBackTask()->task_order());
609 }
610
TEST_F(DelayedWorkQueueTest,DelayedFenceInDelayedTaskGroup)611 TEST_F(DelayedWorkQueueTest, DelayedFenceInDelayedTaskGroup) {
612 const EnqueueOrder kEnqueueOrder = EnqueueOrder::FromIntForTesting(5);
613
614 TaskOrder task_orders[3] = {
615 TaskOrder::CreateForTesting(kEnqueueOrder, TimeTicks() + Seconds(1),
616 /*sequence_num=*/4),
617 TaskOrder::CreateForTesting(kEnqueueOrder, TimeTicks() + Seconds(2),
618 /*sequence_num=*/3),
619 TaskOrder::CreateForTesting(kEnqueueOrder, TimeTicks() + Seconds(3),
620 /*sequence_num=*/2),
621 };
622
623 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
624 for (auto& task_order : task_orders) {
625 work_queue_->Push(FakeTaskWithTaskOrder(task_order));
626 }
627
628 work_queue_->InsertFence(Fence(task_orders[2]));
629
630 EXPECT_FALSE(work_queue_->BlockedByFence());
631 EXPECT_EQ(work_queue_.get(), GetOldestQueueInSet(0));
632 EXPECT_FALSE(work_queue_->Empty());
633 EXPECT_TRUE(task_orders[0] ==
634 work_queue_->TakeTaskFromWorkQueue().task_order());
635
636 EXPECT_FALSE(work_queue_->BlockedByFence());
637 EXPECT_EQ(work_queue_.get(), GetOldestQueueInSet(0));
638 EXPECT_FALSE(work_queue_->Empty());
639 EXPECT_TRUE(task_orders[1] ==
640 work_queue_->TakeTaskFromWorkQueue().task_order());
641
642 EXPECT_TRUE(work_queue_->BlockedByFence());
643 EXPECT_EQ(nullptr, GetOldestQueueInSet(0));
644 EXPECT_FALSE(work_queue_->Empty());
645 }
646
647 } // namespace internal
648 } // namespace sequence_manager
649 } // namespace base
650