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