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 #ifndef NET_BASE_PRIORITIZED_TASK_RUNNER_H_
6 #define NET_BASE_PRIORITIZED_TASK_RUNNER_H_
7
8 #include <stdint.h>
9 #include <utility>
10 #include <vector>
11
12 #include "base/functional/bind.h"
13 #include "base/functional/callback.h"
14 #include "base/location.h"
15 #include "base/memory/ref_counted.h"
16 #include "base/synchronization/lock.h"
17 #include "base/task/post_task_and_reply_with_result_internal.h"
18 #include "base/task/task_traits.h"
19 #include "net/base/net_export.h"
20
21 namespace base {
22 class TaskRunner;
23 } // namespace base
24
25 namespace net {
26
27 namespace internal {
28 template <typename ReturnType>
ReturnAsParamAdapter(base::OnceCallback<ReturnType ()> func,ReturnType * result)29 void ReturnAsParamAdapter(base::OnceCallback<ReturnType()> func,
30 ReturnType* result) {
31 *result = std::move(func).Run();
32 }
33
34 // Adapts a T* result to a callblack that expects a T.
35 template <typename TaskReturnType, typename ReplyArgType>
ReplyAdapter(base::OnceCallback<void (ReplyArgType)> callback,TaskReturnType * result)36 void ReplyAdapter(base::OnceCallback<void(ReplyArgType)> callback,
37 TaskReturnType* result) {
38 std::move(callback).Run(std::move(*result));
39 }
40 } // namespace internal
41
42 // PrioritizedTaskRunner allows for prioritization of posted tasks and their
43 // replies. It provides up to 2^32 priority levels. All tasks posted via the
44 // PrioritizedTaskRunner will run in priority order. All replies from
45 // PostTaskAndReply will also run in priority order. Be careful, as it is
46 // possible to starve a task.
47 class NET_EXPORT_PRIVATE PrioritizedTaskRunner
48 : public base::RefCountedThreadSafe<PrioritizedTaskRunner> {
49 public:
50 enum class ReplyRunnerType { kStandard, kPrioritized };
51 explicit PrioritizedTaskRunner(const base::TaskTraits& task_traits);
52 PrioritizedTaskRunner(const PrioritizedTaskRunner&) = delete;
53 PrioritizedTaskRunner& operator=(const PrioritizedTaskRunner&) = delete;
54
55 // Similar to TaskRunner::PostTaskAndReply, except that the task runs at
56 // |priority|. Priority 0 is the highest priority and will run before other
57 // priority values. Multiple tasks with the same |priority| value are run in
58 // order of posting. The replies are also run in prioritized order on the
59 // calling taskrunner.
60 void PostTaskAndReply(const base::Location& from_here,
61 base::OnceClosure task,
62 base::OnceClosure reply,
63 uint32_t priority);
64
65 // Similar to TaskRunner::PostTaskAndReplyWithResult, except that the task
66 // runs at |priority|. See PostTaskAndReply for a description of |priority|.
67 template <typename TaskReturnType, typename ReplyArgType>
PostTaskAndReplyWithResult(const base::Location & from_here,base::OnceCallback<TaskReturnType ()> task,base::OnceCallback<void (ReplyArgType)> reply,uint32_t priority)68 void PostTaskAndReplyWithResult(const base::Location& from_here,
69 base::OnceCallback<TaskReturnType()> task,
70 base::OnceCallback<void(ReplyArgType)> reply,
71 uint32_t priority) {
72 TaskReturnType* result = new TaskReturnType();
73 return PostTaskAndReply(
74 from_here,
75 BindOnce(&internal::ReturnAsParamAdapter<TaskReturnType>,
76 std::move(task), result),
77 BindOnce(&internal::ReplyAdapter<TaskReturnType, ReplyArgType>,
78 std::move(reply), base::Owned(result)),
79 priority);
80 }
81
SetTaskRunnerForTesting(scoped_refptr<base::TaskRunner> task_runner)82 void SetTaskRunnerForTesting(scoped_refptr<base::TaskRunner> task_runner) {
83 task_runner_for_testing_ = std::move(task_runner);
84 }
85
86 private:
87 friend class base::RefCountedThreadSafe<PrioritizedTaskRunner>;
88
89 struct Job {
90 Job(const base::Location& from_here,
91 base::OnceClosure task,
92 base::OnceClosure reply,
93 uint32_t priority,
94 uint32_t task_count);
95 Job();
96 Job(const Job&) = delete;
97 Job& operator=(const Job&) = delete;
98 ~Job();
99
100 Job(Job&& other);
101 Job& operator=(Job&& other);
102
103 base::Location from_here;
104 base::OnceClosure task;
105 base::OnceClosure reply;
106 uint32_t priority = 0;
107 uint32_t task_count = 0;
108 };
109
110 struct JobComparer {
operatorJobComparer111 bool operator()(const Job& left, const Job& right) {
112 if (left.priority == right.priority)
113 return left.task_count > right.task_count;
114 return left.priority > right.priority;
115 }
116 };
117
118 void RunTaskAndPostReply();
119 void RunReply();
120
121 ~PrioritizedTaskRunner();
122
123 // TODO(jkarlin): Replace the heaps with std::priority_queue once it
124 // supports move-only types.
125 // Accessed on both task_runner_ and the reply task runner.
126 std::vector<Job> task_job_heap_;
127 base::Lock task_job_heap_lock_;
128 std::vector<Job> reply_job_heap_;
129 base::Lock reply_job_heap_lock_;
130
131 const base::TaskTraits task_traits_;
132 scoped_refptr<base::TaskRunner> task_runner_for_testing_;
133
134 // Used to preserve order of jobs of equal priority. This can overflow and
135 // cause periodic priority inversion. This should be infrequent enough to be
136 // of negligible impact.
137 uint32_t task_count_ = 0;
138 };
139
140 } // namespace net
141
142 #endif // NET_BASE_PRIORITIZED_TASK_RUNNER_H_
143