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