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/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 "base/time/time.h"
19 #include "testing/gtest/include/gtest/gtest.h"
20
21 namespace base {
22 namespace internal {
23
24 namespace {
25
26 class PriorityQueueWithSequencesTest : public testing::Test {
27 protected:
ExpectNumSequences(size_t num_best_effort,size_t num_user_visible,size_t num_user_blocking)28 void ExpectNumSequences(size_t num_best_effort,
29 size_t num_user_visible,
30 size_t num_user_blocking) {
31 EXPECT_EQ(pq.GetNumTaskSourcesWithPriority(TaskPriority::BEST_EFFORT),
32 num_best_effort);
33 EXPECT_EQ(pq.GetNumTaskSourcesWithPriority(TaskPriority::USER_VISIBLE),
34 num_user_visible);
35 EXPECT_EQ(pq.GetNumTaskSourcesWithPriority(TaskPriority::USER_BLOCKING),
36 num_user_blocking);
37 }
38
MakeSequenceWithTraitsAndTask(const TaskTraits & traits)39 scoped_refptr<TaskSource> MakeSequenceWithTraitsAndTask(
40 const TaskTraits& traits) {
41 // FastForward time to ensure that queue order between task sources is well
42 // defined.
43 task_environment.FastForwardBy(Microseconds(1));
44 scoped_refptr<Sequence> sequence = MakeRefCounted<Sequence>(
45 traits, nullptr, TaskSourceExecutionMode::kParallel);
46 auto transaction = sequence->BeginTransaction();
47 transaction.WillPushImmediateTask();
48 transaction.PushImmediateTask(
49 Task(FROM_HERE, DoNothing(), TimeTicks::Now(), TimeDelta()));
50 return sequence;
51 }
52
Push(scoped_refptr<TaskSource> task_source)53 void Push(scoped_refptr<TaskSource> task_source) {
54 auto sort_key = task_source->GetSortKey();
55 pq.Push(RegisteredTaskSource::CreateForTesting(std::move(task_source)),
56 sort_key);
57 }
58
59 test::TaskEnvironment task_environment{
60 test::TaskEnvironment::TimeSource::MOCK_TIME};
61
62 scoped_refptr<TaskSource> sequence_a =
63 MakeSequenceWithTraitsAndTask(TaskTraits(TaskPriority::USER_VISIBLE));
64 TaskSourceSortKey sort_key_a = sequence_a->GetSortKey();
65
66 scoped_refptr<TaskSource> sequence_b =
67 MakeSequenceWithTraitsAndTask(TaskTraits(TaskPriority::USER_BLOCKING));
68 TaskSourceSortKey sort_key_b = sequence_b->GetSortKey();
69
70 scoped_refptr<TaskSource> sequence_c =
71 MakeSequenceWithTraitsAndTask(TaskTraits(TaskPriority::USER_BLOCKING));
72 TaskSourceSortKey sort_key_c = sequence_c->GetSortKey();
73
74 scoped_refptr<TaskSource> sequence_d =
75 MakeSequenceWithTraitsAndTask(TaskTraits(TaskPriority::BEST_EFFORT));
76 TaskSourceSortKey sort_key_d = sequence_d->GetSortKey();
77
78 PriorityQueue pq;
79 };
80
81 } // namespace
82
TEST_F(PriorityQueueWithSequencesTest,PushPopPeek)83 TEST_F(PriorityQueueWithSequencesTest, PushPopPeek) {
84 EXPECT_TRUE(pq.IsEmpty());
85 ExpectNumSequences(0U, 0U, 0U);
86
87 // Push |sequence_a| in the PriorityQueue. It becomes the sequence with the
88 // highest priority.
89 Push(sequence_a);
90 EXPECT_EQ(sort_key_a, pq.PeekSortKey());
91 ExpectNumSequences(0U, 1U, 0U);
92
93 // Push |sequence_b| in the PriorityQueue. It becomes the sequence with the
94 // highest priority.
95 Push(sequence_b);
96 EXPECT_EQ(sort_key_b, pq.PeekSortKey());
97 ExpectNumSequences(0U, 1U, 1U);
98
99 // Push |sequence_c| in the PriorityQueue. |sequence_b| is still the sequence
100 // with the highest priority.
101 Push(sequence_c);
102 EXPECT_EQ(sort_key_b, pq.PeekSortKey());
103 ExpectNumSequences(0U, 1U, 2U);
104
105 // Push |sequence_d| in the PriorityQueue. |sequence_b| is still the sequence
106 // with the highest priority.
107 Push(sequence_d);
108 EXPECT_EQ(sort_key_b, pq.PeekSortKey());
109 ExpectNumSequences(1U, 1U, 2U);
110
111 // Pop |sequence_b| from the PriorityQueue. |sequence_c| becomes the sequence
112 // with the highest priority.
113 EXPECT_EQ(sequence_b, pq.PopTaskSource().Unregister());
114 EXPECT_EQ(sort_key_c, pq.PeekSortKey());
115 ExpectNumSequences(1U, 1U, 1U);
116
117 // Pop |sequence_c| from the PriorityQueue. |sequence_a| becomes the sequence
118 // with the highest priority.
119 EXPECT_EQ(sequence_c, pq.PopTaskSource().Unregister());
120 EXPECT_EQ(sort_key_a, pq.PeekSortKey());
121 ExpectNumSequences(1U, 1U, 0U);
122
123 // Pop |sequence_a| from the PriorityQueue. |sequence_d| becomes the sequence
124 // with the highest priority.
125 EXPECT_EQ(sequence_a, pq.PopTaskSource().Unregister());
126 EXPECT_EQ(sort_key_d, pq.PeekSortKey());
127 ExpectNumSequences(1U, 0U, 0U);
128
129 // Pop |sequence_d| from the PriorityQueue. It is now empty.
130 EXPECT_EQ(sequence_d, pq.PopTaskSource().Unregister());
131 EXPECT_TRUE(pq.IsEmpty());
132 ExpectNumSequences(0U, 0U, 0U);
133 }
134
TEST_F(PriorityQueueWithSequencesTest,RemoveSequence)135 TEST_F(PriorityQueueWithSequencesTest, RemoveSequence) {
136 EXPECT_TRUE(pq.IsEmpty());
137
138 // Push all test Sequences into the PriorityQueue. |sequence_b|
139 // will be the sequence with the highest priority.
140 Push(sequence_a);
141 Push(sequence_b);
142 Push(sequence_c);
143 Push(sequence_d);
144 EXPECT_EQ(sort_key_b, pq.PeekSortKey());
145 ExpectNumSequences(1U, 1U, 2U);
146
147 // Remove |sequence_a| from the PriorityQueue. |sequence_b| is still the
148 // sequence with the highest priority.
149 EXPECT_TRUE(pq.RemoveTaskSource(*sequence_a).Unregister());
150 EXPECT_EQ(sort_key_b, pq.PeekSortKey());
151 ExpectNumSequences(1U, 0U, 2U);
152
153 // RemoveTaskSource() should return false if called on a sequence not in the
154 // PriorityQueue.
155 EXPECT_FALSE(pq.RemoveTaskSource(*sequence_a).Unregister());
156 ExpectNumSequences(1U, 0U, 2U);
157
158 // Remove |sequence_b| from the PriorityQueue. |sequence_c| becomes the
159 // sequence with the highest priority.
160 EXPECT_TRUE(pq.RemoveTaskSource(*sequence_b).Unregister());
161 EXPECT_EQ(sort_key_c, pq.PeekSortKey());
162 ExpectNumSequences(1U, 0U, 1U);
163
164 // Remove |sequence_d| from the PriorityQueue. |sequence_c| is still the
165 // sequence with the highest priority.
166 EXPECT_TRUE(pq.RemoveTaskSource(*sequence_d).Unregister());
167 EXPECT_EQ(sort_key_c, pq.PeekSortKey());
168 ExpectNumSequences(0U, 0U, 1U);
169
170 // Remove |sequence_c| from the PriorityQueue, making it empty.
171 EXPECT_TRUE(pq.RemoveTaskSource(*sequence_c).Unregister());
172 EXPECT_TRUE(pq.IsEmpty());
173 ExpectNumSequences(0U, 0U, 0U);
174
175 // Return false if RemoveTaskSource() is called on an empty PriorityQueue.
176 EXPECT_FALSE(pq.RemoveTaskSource(*sequence_c).Unregister());
177 ExpectNumSequences(0U, 0U, 0U);
178 }
179
TEST_F(PriorityQueueWithSequencesTest,UpdateSortKey)180 TEST_F(PriorityQueueWithSequencesTest, UpdateSortKey) {
181 EXPECT_TRUE(pq.IsEmpty());
182
183 // Push all test Sequences into the PriorityQueue. |sequence_b| becomes the
184 // sequence with the highest priority.
185 Push(sequence_a);
186 Push(sequence_b);
187 Push(sequence_c);
188 Push(sequence_d);
189 EXPECT_EQ(sort_key_b, pq.PeekSortKey());
190 ExpectNumSequences(1U, 1U, 2U);
191
192 {
193 // Downgrade |sequence_b| from USER_BLOCKING to BEST_EFFORT. |sequence_c|
194 // (USER_BLOCKING priority) becomes the sequence with the highest priority.
195 auto sequence_b_transaction = sequence_b->BeginTransaction();
196 sequence_b_transaction.UpdatePriority(TaskPriority::BEST_EFFORT);
197
198 pq.UpdateSortKey(*sequence_b, sequence_b->GetSortKey());
199 EXPECT_EQ(sort_key_c, pq.PeekSortKey());
200 ExpectNumSequences(2U, 1U, 1U);
201 }
202
203 {
204 // Update |sequence_c|'s sort key to one with the same priority.
205 // |sequence_c| (USER_BLOCKING priority) is still the sequence with the
206 // highest priority.
207 auto sequence_c_transaction = sequence_c->BeginTransaction();
208 sequence_c_transaction.UpdatePriority(TaskPriority::USER_BLOCKING);
209
210 pq.UpdateSortKey(*sequence_c, sequence_c->GetSortKey());
211 ExpectNumSequences(2U, 1U, 1U);
212
213 // Note: |sequence_c| is popped for comparison as |sort_key_c| becomes
214 // obsolete. |sequence_a| (USER_VISIBLE priority) becomes the sequence with
215 // the highest priority.
216 EXPECT_EQ(sequence_c, pq.PopTaskSource().Unregister());
217 EXPECT_EQ(sort_key_a, pq.PeekSortKey());
218 ExpectNumSequences(2U, 1U, 0U);
219 }
220
221 {
222 // Upgrade |sequence_d| from BEST_EFFORT to USER_BLOCKING. |sequence_d|
223 // becomes the sequence with the highest priority.
224 auto sequence_d_and_transaction = sequence_d->BeginTransaction();
225 sequence_d_and_transaction.UpdatePriority(TaskPriority::USER_BLOCKING);
226
227 pq.UpdateSortKey(*sequence_d, sequence_d->GetSortKey());
228 ExpectNumSequences(1U, 1U, 1U);
229
230 // Note: |sequence_d| is popped for comparison as |sort_key_d| becomes
231 // obsolete.
232 EXPECT_EQ(sequence_d, pq.PopTaskSource().Unregister());
233 // No-op if UpdateSortKey() is called on a Sequence not in the
234 // PriorityQueue.
235 EXPECT_EQ(sort_key_a, pq.PeekSortKey());
236 ExpectNumSequences(1U, 1U, 0U);
237 }
238
239 {
240 pq.UpdateSortKey(*sequence_d, sequence_d->GetSortKey());
241 ExpectNumSequences(1U, 1U, 0U);
242 EXPECT_EQ(sequence_a, pq.PopTaskSource().Unregister());
243 ExpectNumSequences(1U, 0U, 0U);
244 EXPECT_EQ(sequence_b, pq.PopTaskSource().Unregister());
245 ExpectNumSequences(0U, 0U, 0U);
246 }
247
248 {
249 // No-op if UpdateSortKey() is called on an empty PriorityQueue.
250 pq.UpdateSortKey(*sequence_b, sequence_b->GetSortKey());
251 EXPECT_TRUE(pq.IsEmpty());
252 ExpectNumSequences(0U, 0U, 0U);
253 }
254 }
255
256 } // namespace internal
257 } // namespace base
258