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