1 // Copyright 2018 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 "net/base/prioritized_task_runner.h"
6
7 #include <algorithm>
8 #include <limits>
9 #include <string>
10 #include <vector>
11
12 #include "base/functional/bind.h"
13 #include "base/functional/callback_helpers.h"
14 #include "base/location.h"
15 #include "base/rand_util.h"
16 #include "base/run_loop.h"
17 #include "base/strings/string_number_conversions.h"
18 #include "base/strings/string_util.h"
19 #include "base/synchronization/lock.h"
20 #include "base/synchronization/waitable_event.h"
21 #include "base/task/sequenced_task_runner.h"
22 #include "base/task/thread_pool.h"
23 #include "base/test/task_environment.h"
24 #include "base/threading/thread_restrictions.h"
25 #include "testing/gtest/include/gtest/gtest.h"
26
27 namespace net {
28 namespace {
29
30 class PrioritizedTaskRunnerTest : public testing::Test {
31 public:
32 PrioritizedTaskRunnerTest() = default;
33 PrioritizedTaskRunnerTest(const PrioritizedTaskRunnerTest&) = delete;
34 PrioritizedTaskRunnerTest& operator=(const PrioritizedTaskRunnerTest&) =
35 delete;
36
PushName(const std::string & task_name)37 void PushName(const std::string& task_name) {
38 base::AutoLock auto_lock(callback_names_lock_);
39 callback_names_.push_back(task_name);
40 }
41
PushNameWithResult(const std::string & task_name)42 std::string PushNameWithResult(const std::string& task_name) {
43 PushName(task_name);
44 std::string reply_name = task_name;
45 base::ReplaceSubstringsAfterOffset(&reply_name, 0, "Task", "Reply");
46 return reply_name;
47 }
48
TaskOrder()49 std::vector<std::string> TaskOrder() {
50 std::vector<std::string> out;
51 for (const std::string& name : callback_names_) {
52 if (base::StartsWith(name, "Task", base::CompareCase::SENSITIVE))
53 out.push_back(name);
54 }
55 return out;
56 }
57
ReplyOrder()58 std::vector<std::string> ReplyOrder() {
59 std::vector<std::string> out;
60 for (const std::string& name : callback_names_) {
61 if (base::StartsWith(name, "Reply", base::CompareCase::SENSITIVE))
62 out.push_back(name);
63 }
64 return out;
65 }
66
67 // Adds a task to the task runner and waits for it to execute.
ProcessTaskRunner(base::TaskRunner * task_runner)68 void ProcessTaskRunner(base::TaskRunner* task_runner) {
69 // Use a waitable event instead of a run loop as we need to be careful not
70 // to run any tasks on this task runner while waiting.
71 base::WaitableEvent waitable_event;
72
73 task_runner->PostTask(FROM_HERE,
74 base::BindOnce(
75 [](base::WaitableEvent* waitable_event) {
76 waitable_event->Signal();
77 },
78 &waitable_event));
79
80 base::ScopedAllowBaseSyncPrimitivesForTesting sync;
81 waitable_event.Wait();
82 }
83
84 // Adds a task to the |task_runner|, forcing it to wait for a conditional.
85 // Call ReleaseTaskRunner to continue.
BlockTaskRunner(base::TaskRunner * task_runner)86 void BlockTaskRunner(base::TaskRunner* task_runner) {
87 waitable_event_.Reset();
88
89 auto wait_function = [](base::WaitableEvent* waitable_event) {
90 base::ScopedAllowBaseSyncPrimitivesForTesting sync;
91 waitable_event->Wait();
92 };
93 task_runner->PostTask(FROM_HERE,
94 base::BindOnce(wait_function, &waitable_event_));
95 }
96
97 // Signals the task runner's conditional so that it can continue after calling
98 // BlockTaskRunner.
ReleaseTaskRunner()99 void ReleaseTaskRunner() { waitable_event_.Signal(); }
100
101 protected:
102 base::test::TaskEnvironment task_environment_;
103
104 std::vector<std::string> callback_names_;
105 base::Lock callback_names_lock_;
106 base::WaitableEvent waitable_event_;
107 };
108
TEST_F(PrioritizedTaskRunnerTest,PostTaskAndReplyThreadCheck)109 TEST_F(PrioritizedTaskRunnerTest, PostTaskAndReplyThreadCheck) {
110 auto task_runner = base::ThreadPool::CreateSequencedTaskRunner({});
111 auto prioritized_task_runner =
112 base::MakeRefCounted<PrioritizedTaskRunner>(base::TaskTraits());
113 prioritized_task_runner->SetTaskRunnerForTesting(task_runner);
114
115 base::RunLoop run_loop;
116
117 auto thread_check =
118 [](scoped_refptr<base::SequencedTaskRunner> expected_task_runner,
119 base::OnceClosure callback) {
120 EXPECT_TRUE(expected_task_runner->RunsTasksInCurrentSequence());
121 std::move(callback).Run();
122 };
123
124 prioritized_task_runner->PostTaskAndReply(
125 FROM_HERE, base::BindOnce(thread_check, task_runner, base::DoNothing()),
126 base::BindOnce(thread_check, task_environment_.GetMainThreadTaskRunner(),
127 run_loop.QuitClosure()),
128 0);
129
130 run_loop.Run();
131 }
132
TEST_F(PrioritizedTaskRunnerTest,PostTaskAndReplyRunsBothTasks)133 TEST_F(PrioritizedTaskRunnerTest, PostTaskAndReplyRunsBothTasks) {
134 auto task_runner = base::ThreadPool::CreateSequencedTaskRunner({});
135 auto prioritized_task_runner =
136 base::MakeRefCounted<PrioritizedTaskRunner>(base::TaskTraits());
137 prioritized_task_runner->SetTaskRunnerForTesting(task_runner);
138
139 prioritized_task_runner->PostTaskAndReply(
140 FROM_HERE,
141 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
142 base::Unretained(this), "Task"),
143 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
144 base::Unretained(this), "Reply"),
145 0);
146
147 // Run the TaskRunner and both the Task and Reply should run.
148 task_environment_.RunUntilIdle();
149 EXPECT_EQ((std::vector<std::string>{"Task", "Reply"}), callback_names_);
150 }
151
TEST_F(PrioritizedTaskRunnerTest,PostTaskAndReplyTestPriority)152 TEST_F(PrioritizedTaskRunnerTest, PostTaskAndReplyTestPriority) {
153 auto task_runner = base::ThreadPool::CreateSequencedTaskRunner({});
154 auto prioritized_task_runner =
155 base::MakeRefCounted<PrioritizedTaskRunner>(base::TaskTraits());
156 prioritized_task_runner->SetTaskRunnerForTesting(task_runner);
157
158 BlockTaskRunner(task_runner.get());
159 prioritized_task_runner->PostTaskAndReply(
160 FROM_HERE,
161 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
162 base::Unretained(this), "Task5"),
163 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
164 base::Unretained(this), "Reply5"),
165 5);
166
167 prioritized_task_runner->PostTaskAndReply(
168 FROM_HERE,
169 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
170 base::Unretained(this), "Task0"),
171 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
172 base::Unretained(this), "Reply0"),
173 0);
174
175 prioritized_task_runner->PostTaskAndReply(
176 FROM_HERE,
177 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
178 base::Unretained(this), "Task7"),
179 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
180 base::Unretained(this), "Reply7"),
181 7);
182 ReleaseTaskRunner();
183
184 // Run the TaskRunner and all of the tasks and replies should have run, in
185 // priority order.
186 task_environment_.RunUntilIdle();
187 EXPECT_EQ((std::vector<std::string>{"Task0", "Task5", "Task7"}), TaskOrder());
188 EXPECT_EQ((std::vector<std::string>{"Reply0", "Reply5", "Reply7"}),
189 ReplyOrder());
190 }
191
192 // Ensure that replies are run in priority order.
TEST_F(PrioritizedTaskRunnerTest,PostTaskAndReplyTestReplyPriority)193 TEST_F(PrioritizedTaskRunnerTest, PostTaskAndReplyTestReplyPriority) {
194 auto task_runner = base::ThreadPool::CreateSequencedTaskRunner({});
195 auto prioritized_task_runner =
196 base::MakeRefCounted<PrioritizedTaskRunner>(base::TaskTraits());
197 prioritized_task_runner->SetTaskRunnerForTesting(task_runner);
198
199 // Add a couple of tasks to run right away, but don't run their replies yet.
200 BlockTaskRunner(task_runner.get());
201 prioritized_task_runner->PostTaskAndReply(
202 FROM_HERE,
203 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
204 base::Unretained(this), "Task2"),
205 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
206 base::Unretained(this), "Reply2"),
207 2);
208
209 prioritized_task_runner->PostTaskAndReply(
210 FROM_HERE,
211 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
212 base::Unretained(this), "Task1"),
213 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
214 base::Unretained(this), "Reply1"),
215 1);
216 ReleaseTaskRunner();
217
218 // Run the current tasks (but not their replies).
219 ProcessTaskRunner(task_runner.get());
220
221 // Now post task 0 (highest priority) and run it. None of the replies have
222 // been processed yet, so its reply should skip to the head of the queue.
223 prioritized_task_runner->PostTaskAndReply(
224 FROM_HERE,
225 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
226 base::Unretained(this), "Task0"),
227 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
228 base::Unretained(this), "Reply0"),
229 0);
230 ProcessTaskRunner(task_runner.get());
231
232 // Run the replies.
233 task_environment_.RunUntilIdle();
234
235 EXPECT_EQ((std::vector<std::string>{"Task1", "Task2", "Task0"}), TaskOrder());
236 EXPECT_EQ((std::vector<std::string>{"Reply0", "Reply1", "Reply2"}),
237 ReplyOrder());
238 }
239
TEST_F(PrioritizedTaskRunnerTest,PriorityOverflow)240 TEST_F(PrioritizedTaskRunnerTest, PriorityOverflow) {
241 auto task_runner = base::ThreadPool::CreateSequencedTaskRunner({});
242 auto prioritized_task_runner =
243 base::MakeRefCounted<PrioritizedTaskRunner>(base::TaskTraits());
244 prioritized_task_runner->SetTaskRunnerForTesting(task_runner);
245
246 const uint32_t kMaxPriority = std::numeric_limits<uint32_t>::max();
247
248 BlockTaskRunner(task_runner.get());
249 prioritized_task_runner->PostTaskAndReply(
250 FROM_HERE,
251 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
252 base::Unretained(this), "TaskMinus1"),
253 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
254 base::Unretained(this), "ReplyMinus1"),
255 kMaxPriority - 1);
256
257 prioritized_task_runner->PostTaskAndReply(
258 FROM_HERE,
259 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
260 base::Unretained(this), "TaskMax"),
261 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
262 base::Unretained(this), "ReplyMax"),
263 kMaxPriority);
264
265 prioritized_task_runner->PostTaskAndReply(
266 FROM_HERE,
267 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
268 base::Unretained(this), "TaskMaxPlus1"),
269 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
270 base::Unretained(this), "ReplyMaxPlus1"),
271 kMaxPriority + 1);
272 ReleaseTaskRunner();
273
274 // Run the TaskRunner and all of the tasks and replies should have run, in
275 // priority order.
276 task_environment_.RunUntilIdle();
277 EXPECT_EQ((std::vector<std::string>{"TaskMaxPlus1", "TaskMinus1", "TaskMax"}),
278 TaskOrder());
279 EXPECT_EQ(
280 (std::vector<std::string>{"ReplyMaxPlus1", "ReplyMinus1", "ReplyMax"}),
281 ReplyOrder());
282 }
283
TEST_F(PrioritizedTaskRunnerTest,PostTaskAndReplyWithResultRunsBothTasks)284 TEST_F(PrioritizedTaskRunnerTest, PostTaskAndReplyWithResultRunsBothTasks) {
285 auto task_runner = base::ThreadPool::CreateSequencedTaskRunner({});
286 auto prioritized_task_runner =
287 base::MakeRefCounted<PrioritizedTaskRunner>(base::TaskTraits());
288 prioritized_task_runner->SetTaskRunnerForTesting(task_runner);
289
290 prioritized_task_runner->PostTaskAndReplyWithResult(
291 FROM_HERE,
292 base::BindOnce(&PrioritizedTaskRunnerTest::PushNameWithResult,
293 base::Unretained(this), "Task"),
294 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
295 base::Unretained(this)),
296 0);
297
298 // Run the TaskRunner and both the Task and Reply should run.
299 task_environment_.RunUntilIdle();
300 EXPECT_EQ((std::vector<std::string>{"Task", "Reply"}), callback_names_);
301 }
302
TEST_F(PrioritizedTaskRunnerTest,PostTaskAndReplyWithResultTestPriority)303 TEST_F(PrioritizedTaskRunnerTest, PostTaskAndReplyWithResultTestPriority) {
304 auto task_runner = base::ThreadPool::CreateSequencedTaskRunner({});
305 auto prioritized_task_runner =
306 base::MakeRefCounted<PrioritizedTaskRunner>(base::TaskTraits());
307 prioritized_task_runner->SetTaskRunnerForTesting(task_runner);
308
309 BlockTaskRunner(task_runner.get());
310 prioritized_task_runner->PostTaskAndReplyWithResult(
311 FROM_HERE,
312 base::BindOnce(&PrioritizedTaskRunnerTest::PushNameWithResult,
313 base::Unretained(this), "Task0"),
314 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
315 base::Unretained(this)),
316 0);
317
318 prioritized_task_runner->PostTaskAndReplyWithResult(
319 FROM_HERE,
320 base::BindOnce(&PrioritizedTaskRunnerTest::PushNameWithResult,
321 base::Unretained(this), "Task7"),
322 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
323 base::Unretained(this)),
324 7);
325
326 prioritized_task_runner->PostTaskAndReplyWithResult(
327 FROM_HERE,
328 base::BindOnce(&PrioritizedTaskRunnerTest::PushNameWithResult,
329 base::Unretained(this), "Task3"),
330 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
331 base::Unretained(this)),
332 3);
333 ReleaseTaskRunner();
334
335 // Run the TaskRunner and both the Task and Reply should run.
336 task_environment_.RunUntilIdle();
337 EXPECT_EQ((std::vector<std::string>{"Task0", "Task3", "Task7"}), TaskOrder());
338 EXPECT_EQ((std::vector<std::string>{"Reply0", "Reply3", "Reply7"}),
339 ReplyOrder());
340 }
341
TEST_F(PrioritizedTaskRunnerTest,OrderSamePriorityByPostOrder)342 TEST_F(PrioritizedTaskRunnerTest, OrderSamePriorityByPostOrder) {
343 auto task_runner = base::ThreadPool::CreateSequencedTaskRunner({});
344 auto prioritized_task_runner =
345 base::MakeRefCounted<PrioritizedTaskRunner>(base::TaskTraits());
346 prioritized_task_runner->SetTaskRunnerForTesting(task_runner);
347
348 std::vector<int> expected;
349
350 // Create 1000 tasks with random priorities between 1 and 3. Those that have
351 // the same priorities should run in posting order.
352 BlockTaskRunner(task_runner.get());
353 for (int i = 0; i < 1000; i++) {
354 int priority = base::RandInt(0, 2);
355 int id = (priority * 1000) + i;
356
357 expected.push_back(id);
358 prioritized_task_runner->PostTaskAndReply(
359 FROM_HERE,
360 base::BindOnce(&PrioritizedTaskRunnerTest::PushName,
361 base::Unretained(this), base::NumberToString(id)),
362 base::DoNothing(), priority);
363 }
364 ReleaseTaskRunner();
365
366 // This is the order the tasks should run on the queue.
367 std::sort(expected.begin(), expected.end());
368
369 task_environment_.RunUntilIdle();
370
371 // This is the order that the tasks ran on the queue.
372 std::vector<int> results;
373 for (const std::string& result : callback_names_) {
374 int result_id;
375 EXPECT_TRUE(base::StringToInt(result, &result_id));
376 results.push_back(result_id);
377 }
378
379 EXPECT_EQ(expected, results);
380 }
381
382 } // namespace
383 } // namespace net
384