1 // Copyright 2016 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/thread_pool/delayed_priority_queue.h"
6
7 #include <memory>
8 #include <utility>
9
10 #include "base/functional/callback_helpers.h"
11 #include "base/memory/ptr_util.h"
12 #include "base/memory/ref_counted.h"
13 #include "base/task/task_traits.h"
14 #include "base/task/thread_pool/sequence.h"
15 #include "base/task/thread_pool/task.h"
16 #include "base/test/gtest_util.h"
17 #include "base/test/task_environment.h"
18 #include "testing/gtest/include/gtest/gtest.h"
19
20 namespace base::internal {
21
22 namespace {
23
24 class DelayedPriorityQueueWithSequencesTest : public testing::Test {
25 protected:
MakeSequenceWithDelayedTask(TimeDelta delayed_run_time)26 scoped_refptr<Sequence> MakeSequenceWithDelayedTask(
27 TimeDelta delayed_run_time) {
28 // FastForward time to ensure that queue order between task sources is well
29 // defined.
30 task_environment.FastForwardBy(Microseconds(1));
31 scoped_refptr<Sequence> sequence = MakeRefCounted<Sequence>(
32 TaskTraits(), nullptr, TaskSourceExecutionMode::kParallel);
33 sequence->BeginTransaction().PushDelayedTask(
34 Task(FROM_HERE, DoNothing(), TimeTicks::Now(), delayed_run_time));
35 return sequence;
36 }
37
Push(scoped_refptr<Sequence> task_source)38 void Push(scoped_refptr<Sequence> task_source) {
39 auto delayed_sort_key = task_source->GetDelayedSortKey();
40 pq.Push(std::move(task_source), delayed_sort_key);
41 }
42
43 test::TaskEnvironment task_environment{
44 test::TaskEnvironment::TimeSource::MOCK_TIME};
45
46 scoped_refptr<Sequence> sequence_a =
47 MakeSequenceWithDelayedTask(Milliseconds(90));
48 TimeTicks sort_key_a = sequence_a->GetDelayedSortKey();
49
50 scoped_refptr<Sequence> sequence_b =
51 MakeSequenceWithDelayedTask(Milliseconds(70));
52 TimeTicks sort_key_b = sequence_b->GetDelayedSortKey();
53
54 scoped_refptr<Sequence> sequence_c =
55 MakeSequenceWithDelayedTask(Milliseconds(80));
56 TimeTicks sort_key_c = sequence_c->GetDelayedSortKey();
57
58 scoped_refptr<Sequence> sequence_d =
59 MakeSequenceWithDelayedTask(Milliseconds(100));
60 TimeTicks sort_key_d = sequence_d->GetDelayedSortKey();
61
62 DelayedPriorityQueue pq;
63 };
64
65 } // namespace
66
TEST_F(DelayedPriorityQueueWithSequencesTest,PushPopPeek)67 TEST_F(DelayedPriorityQueueWithSequencesTest, PushPopPeek) {
68 EXPECT_TRUE(pq.IsEmpty());
69
70 // Push |sequence_a| in the DelayedPriorityQueue. It becomes the sequence with
71 // the earliest delayed runtime.
72 Push(sequence_a);
73 EXPECT_EQ(sort_key_a, pq.PeekDelayedSortKey());
74
75 // Push |sequence_b| in the DelayedPriorityQueue. It becomes the sequence with
76 // the earliest delayed runtime.
77 Push(sequence_b);
78 EXPECT_EQ(sort_key_b, pq.PeekDelayedSortKey());
79
80 // Push |sequence_c| in the DelayedPriorityQueue. |sequence_b| is still the
81 // sequence with the earliest delayed runtime.
82 Push(sequence_c);
83 EXPECT_EQ(sort_key_b, pq.PeekDelayedSortKey());
84
85 // Push |sequence_d| in the DelayedPriorityQueue. |sequence_b| is still the
86 // sequence with the earliest delayed runtime.
87 Push(sequence_d);
88 EXPECT_EQ(sort_key_b, pq.PeekDelayedSortKey());
89
90 // Pop |sequence_b| from the DelayedPriorityQueue. |sequence_c| becomes the
91 // sequence with the earliest delayed runtime.
92 EXPECT_EQ(sequence_b, pq.PopTaskSource());
93 EXPECT_EQ(sort_key_c, pq.PeekDelayedSortKey());
94
95 // Pop |sequence_c| from the DelayedPriorityQueue. |sequence_a| becomes the
96 // sequence with the earliest delayed runtime.
97 EXPECT_EQ(sequence_c, pq.PopTaskSource());
98 EXPECT_EQ(sort_key_a, pq.PeekDelayedSortKey());
99
100 // Pop |sequence_a| from the DelayedPriorityQueue. |sequence_d| becomes the
101 // sequence with the earliest delayed runtime.
102 EXPECT_EQ(sequence_a, pq.PopTaskSource());
103 EXPECT_EQ(sort_key_d, pq.PeekDelayedSortKey());
104
105 // Pop |sequence_d| from the DelayedPriorityQueue. It is now empty.
106 EXPECT_EQ(sequence_d, pq.PopTaskSource());
107 EXPECT_TRUE(pq.IsEmpty());
108 }
109
TEST_F(DelayedPriorityQueueWithSequencesTest,RemoveSequence)110 TEST_F(DelayedPriorityQueueWithSequencesTest, RemoveSequence) {
111 EXPECT_TRUE(pq.IsEmpty());
112
113 // Push all test Sequences into the PriorityQueue. |sequence_b|
114 // will be the sequence with the highest priority.
115 Push(sequence_a);
116 Push(sequence_b);
117 Push(sequence_c);
118 Push(sequence_d);
119 EXPECT_EQ(sort_key_b, pq.PeekDelayedSortKey());
120
121 // Remove |sequence_a| from the PriorityQueue. |sequence_b| is still the
122 // sequence with the highest priority.
123 EXPECT_TRUE(pq.RemoveTaskSource(sequence_a));
124 EXPECT_EQ(sort_key_b, pq.PeekDelayedSortKey());
125
126 // RemoveTaskSource() should return false if called on a sequence not in the
127 // PriorityQueue.
128 EXPECT_FALSE(pq.RemoveTaskSource(sequence_a));
129
130 // Remove |sequence_b| from the PriorityQueue. |sequence_c| becomes the
131 // sequence with the highest priority.
132 EXPECT_TRUE(pq.RemoveTaskSource(sequence_b));
133 EXPECT_EQ(sort_key_c, pq.PeekDelayedSortKey());
134
135 // Remove |sequence_d| from the PriorityQueue. |sequence_c| is still the
136 // sequence with the highest priority.
137 EXPECT_TRUE(pq.RemoveTaskSource(sequence_d));
138 EXPECT_EQ(sort_key_c, pq.PeekDelayedSortKey());
139
140 // Remove |sequence_c| from the PriorityQueue, making it empty.
141 EXPECT_TRUE(pq.RemoveTaskSource(sequence_c));
142 EXPECT_TRUE(pq.IsEmpty());
143
144 // Return false if RemoveTaskSource() is called on an empty PriorityQueue.
145 EXPECT_FALSE(pq.RemoveTaskSource(sequence_c));
146 }
147
148 // Test that when the top of a task source changes, the delayed queue is
149 // appropriately rearranged
TEST_F(DelayedPriorityQueueWithSequencesTest,UpdateDelayedSortKey)150 TEST_F(DelayedPriorityQueueWithSequencesTest, UpdateDelayedSortKey) {
151 EXPECT_TRUE(pq.IsEmpty());
152
153 // Push all test Sequences into the PriorityQueue. |sequence_b| becomes the
154 // sequence with the highest priority.
155 Push(sequence_a);
156 Push(sequence_b);
157 Push(sequence_c);
158 Push(sequence_d);
159 EXPECT_EQ(sort_key_b, pq.PeekDelayedSortKey());
160
161 {
162 // Push a new delayed task earlier than pq's top into sequence_c.
163 // |sequence_c| becomes the sequence on top of the delayed priority queue.
164 sequence_c->BeginTransaction().PushDelayedTask(
165 Task(FROM_HERE, DoNothing(), TimeTicks::Now(), Milliseconds(60)));
166
167 sort_key_c = sequence_c->GetDelayedSortKey();
168 pq.UpdateDelayedSortKey(sequence_c);
169 EXPECT_EQ(sort_key_c, pq.PeekDelayedSortKey());
170 }
171
172 {
173 // Push a new delayed task earlier than pq's top into sequence_d.
174 // |sequence_d| becomes the sequence on top of the delayed priority queue.
175 sequence_d->BeginTransaction().PushDelayedTask(
176 Task(FROM_HERE, DoNothing(), TimeTicks::Now(), Milliseconds(50)));
177
178 sort_key_d = sequence_d->GetDelayedSortKey();
179 pq.UpdateDelayedSortKey(sequence_d);
180 EXPECT_EQ(sort_key_d, pq.PeekDelayedSortKey());
181
182 // Pop top task source and verify that it is |sequence_d|
183 EXPECT_EQ(sequence_d, pq.PopTaskSource());
184 // New top should be |sequence_c|
185 EXPECT_EQ(sort_key_c, pq.PeekDelayedSortKey());
186 }
187
188 {
189 EXPECT_EQ(sequence_c, pq.PopTaskSource());
190 EXPECT_EQ(sequence_b, pq.PopTaskSource());
191 EXPECT_EQ(sequence_a, pq.PopTaskSource());
192 }
193
194 {
195 // No-op if UpdateSortKey() is called on an empty PriorityQueue.
196 pq.UpdateDelayedSortKey(sequence_b);
197 EXPECT_TRUE(pq.IsEmpty());
198 }
199 }
200
201 } // namespace base::internal
202