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