OLD | NEW |
---|---|
(Empty) | |
1 // Copyright 2016 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/network_throttle_manager_impl.h" | |
6 | |
7 #include <algorithm> | |
8 | |
9 #include "base/logging.h" | |
10 #include "base/threading/thread_task_runner_handle.h" | |
11 #include "base/time/default_tick_clock.h" | |
12 | |
13 namespace net { | |
14 | |
15 const size_t NetworkThrottleManagerImpl::kActiveRequestThrottlingLimit = 2; | |
16 const int NetworkThrottleManagerImpl::kMedianLifetimeMultiple = 5; | |
17 | |
18 // Initial estimate based on the median in the | |
19 // Net.RequestTime2.Success histogram, excluding cached results by eye. | |
20 const int NetworkThrottleManagerImpl::kInitialMedianInMs = 400; | |
21 | |
22 // Set timers slightly further into the future than they need to be set, so | |
23 // that the algorithm isn't vulnerable to timer round off errors triggering | |
24 // the callback before the throttle would be considered aged out of the set. | |
25 // Set to 17 to hanlde systems with |!base::TimeTicks::IsHighResolution()|. | |
26 // Note that even if the timer goes off before it should, all that should cost | |
27 // is a second task; this class does not rely on timer accuracy for its | |
28 // correctness. | |
29 const int kTimerFudgeInMs = 17; | |
30 | |
31 class NetworkThrottleManagerImpl::ThrottleImpl | |
32 : public NetworkThrottleManager::Throttle { | |
33 public: | |
34 // Allowed state transitions are BLOCKED -> OUTSTANDING -> AGED. | |
35 // Throttles may be created in the BLOCKED or OUTSTANDING states. | |
36 enum class State { | |
37 // Not allowed to proceed by manager. | |
38 BLOCKED, | |
39 | |
40 // Allowed to proceed, counts as an "outstanding" request for | |
41 // manager accounting purposes. | |
42 OUTSTANDING, | |
43 | |
44 // Old enough to not count as "outstanding" anymore for | |
45 // manager accounting purposes. | |
46 AGED | |
47 }; | |
48 | |
49 using ThrottleListQueuePointer = | |
50 NetworkThrottleManagerImpl::ThrottleList::iterator; | |
51 | |
52 // Caller must arrange that |*delegate| and |*manager| outlive | |
53 // the ThrottleImpl class. | |
54 ThrottleImpl(bool blocked, | |
55 RequestPriority priority, | |
56 ThrottleDelegate* delegate, | |
57 NetworkThrottleManagerImpl* manager, | |
58 ThrottleListQueuePointer queue_pointer); | |
59 | |
60 ~ThrottleImpl() override; | |
61 | |
62 // Throttle: | |
63 bool IsBlocked() const override; | |
64 RequestPriority Priority() const override; | |
65 void SetPriority(RequestPriority priority) override; | |
66 | |
67 State state() const { return state_; } | |
68 | |
69 ThrottleListQueuePointer queue_pointer() const { return queue_pointer_; } | |
70 void set_queue_pointer(const ThrottleListQueuePointer& pointer) { | |
71 queue_pointer_ = pointer; | |
72 } | |
73 | |
74 void set_start_time(base::TimeTicks start_time) { start_time_ = start_time; } | |
75 base::TimeTicks start_time() const { return start_time_; } | |
76 | |
77 // Change the throttle's state to AGED. The previous | |
78 // state must be OUTSTANDING. | |
79 void SetAged(); | |
80 | |
81 // Note that this call calls the delegate, and hence may result in | |
82 // re-entrant calls into the manager or ThrottleImpl. The manager should | |
83 // not rely on any state other than its own existence being persistent | |
84 // across this call. | |
85 void NotifyUnblocked(); | |
86 | |
87 private: | |
88 State state_; | |
89 RequestPriority priority_; | |
90 ThrottleDelegate* const delegate_; | |
91 NetworkThrottleManagerImpl* const manager_; | |
92 | |
93 base::TimeTicks start_time_; | |
94 | |
95 // To allow deletion from the blocked queue (when the throttle is in the | |
96 // blocked queue). | |
97 ThrottleListQueuePointer queue_pointer_; | |
98 | |
99 DISALLOW_COPY_AND_ASSIGN(ThrottleImpl); | |
100 }; | |
101 | |
102 NetworkThrottleManagerImpl::ThrottleImpl::ThrottleImpl( | |
103 bool blocked, | |
104 RequestPriority priority, | |
105 NetworkThrottleManager::ThrottleDelegate* delegate, | |
106 NetworkThrottleManagerImpl* manager, | |
107 ThrottleListQueuePointer queue_pointer) | |
108 : state_(blocked ? State::BLOCKED : State::OUTSTANDING), | |
109 priority_(priority), | |
110 delegate_(delegate), | |
111 manager_(manager), | |
112 queue_pointer_(queue_pointer) { | |
113 DCHECK(delegate); | |
114 if (!blocked) | |
115 start_time_ = manager->tick_clock_->NowTicks(); | |
116 } | |
117 | |
118 NetworkThrottleManagerImpl::ThrottleImpl::~ThrottleImpl() { | |
119 manager_->OnThrottleDestroyed(this); | |
120 } | |
121 | |
122 bool NetworkThrottleManagerImpl::ThrottleImpl::IsBlocked() const { | |
123 return state_ == State::BLOCKED; | |
124 } | |
125 | |
126 RequestPriority NetworkThrottleManagerImpl::ThrottleImpl::Priority() const { | |
127 return priority_; | |
128 } | |
129 | |
130 void NetworkThrottleManagerImpl::ThrottleImpl::SetPriority( | |
131 RequestPriority new_priority) { | |
132 RequestPriority old_priority(priority_); | |
133 if (old_priority == new_priority) | |
134 return; | |
135 priority_ = new_priority; | |
136 manager_->OnThrottlePriorityChanged(this, old_priority, new_priority); | |
137 } | |
138 | |
139 void NetworkThrottleManagerImpl::ThrottleImpl::SetAged() { | |
140 DCHECK_EQ(State::OUTSTANDING, state_); | |
141 state_ = State::AGED; | |
142 } | |
143 | |
144 void NetworkThrottleManagerImpl::ThrottleImpl::NotifyUnblocked() { | |
145 // This method should only be called once, and only if the | |
146 // current state is blocked. | |
147 DCHECK_EQ(State::BLOCKED, state_); | |
148 state_ = State::OUTSTANDING; | |
149 delegate_->OnThrottleUnblocked(this); | |
150 } | |
151 | |
152 NetworkThrottleManagerImpl::NetworkThrottleManagerImpl() | |
153 : lifetime_median_estimate_(PercentileEstimator::kMedianPercentile, | |
154 kInitialMedianInMs), | |
155 outstanding_recomputation_timer_(false /* retain_user_task */, | |
156 false /* is_repeating */), | |
157 tick_clock_(new base::DefaultTickClock()), | |
158 weak_ptr_factory_(this) { | |
159 outstanding_recomputation_timer_.SetTaskRunner( | |
160 base::ThreadTaskRunnerHandle::Get()); | |
161 } | |
162 | |
163 NetworkThrottleManagerImpl::~NetworkThrottleManagerImpl() {} | |
164 | |
165 std::unique_ptr<NetworkThrottleManager::Throttle> | |
166 NetworkThrottleManagerImpl::CreateThrottle( | |
167 NetworkThrottleManager::ThrottleDelegate* delegate, | |
168 RequestPriority priority, | |
169 bool ignore_limits) { | |
170 bool blocked = | |
171 (!ignore_limits && priority == THROTTLED && | |
172 outstanding_throttles_.size() >= kActiveRequestThrottlingLimit); | |
173 | |
174 std::unique_ptr<NetworkThrottleManagerImpl::ThrottleImpl> throttle( | |
175 new ThrottleImpl(blocked, priority, delegate, this, | |
176 blocked_throttles_.end())); | |
177 | |
178 ThrottleList& insert_list(blocked ? blocked_throttles_ | |
179 : outstanding_throttles_); | |
180 | |
181 throttle->set_queue_pointer( | |
182 insert_list.insert(insert_list.end(), throttle.get())); | |
183 | |
184 // In case oustanding_throttles_ was empty, set up timer. | |
185 if (!blocked) | |
186 RecomputeOutstanding(); | |
187 | |
188 return std::move(throttle); | |
189 } | |
190 | |
191 void NetworkThrottleManagerImpl::SetTickClockForTesting( | |
192 std::unique_ptr<base::TickClock> tick_clock) { | |
193 tick_clock_ = std::move(tick_clock); | |
194 } | |
195 | |
196 bool NetworkThrottleManagerImpl::ConditionallyTriggerTimerForTesting() { | |
197 if (!outstanding_recomputation_timer_.IsRunning() || | |
198 (tick_clock_->NowTicks() < | |
199 outstanding_recomputation_timer_.desired_run_time())) { | |
200 return false; | |
201 } | |
202 | |
203 base::Closure timer_callback(outstanding_recomputation_timer_.user_task()); | |
204 outstanding_recomputation_timer_.Stop(); | |
205 timer_callback.Run(); | |
206 return true; | |
207 } | |
208 | |
209 void NetworkThrottleManagerImpl::OnThrottlePriorityChanged( | |
210 NetworkThrottleManagerImpl::ThrottleImpl* throttle, | |
211 RequestPriority old_priority, | |
212 RequestPriority new_priority) { | |
213 // The only case requiring a state change is if the priority change | |
214 // implies unblocking, which can only happen on a transition from blocked | |
215 // (implies THROTTLED) to non-THROTTLED. | |
216 if (throttle->IsBlocked() && new_priority != THROTTLED) { | |
217 // May result in re-entrant calls into this class. | |
218 UnblockThrottle(throttle); | |
219 } | |
220 } | |
221 | |
222 void NetworkThrottleManagerImpl::OnThrottleDestroyed(ThrottleImpl* throttle) { | |
223 switch (throttle->state()) { | |
224 case ThrottleImpl::State::BLOCKED: | |
225 DCHECK(throttle->queue_pointer() != blocked_throttles_.end()); | |
226 DCHECK(std::find(blocked_throttles_.begin(), blocked_throttles_.end(), | |
227 throttle) == throttle->queue_pointer()); | |
mmenke
2016/11/11 20:51:17
If we want to do this, it seems like we could just
Randy Smith (Not in Mondays)
2016/11/16 15:56:36
Good point; done.
mmenke
2016/11/16 16:02:08
I don't think you need to look into a queue?
DCHE
| |
228 blocked_throttles_.erase(throttle->queue_pointer()); | |
229 break; | |
230 case ThrottleImpl::State::OUTSTANDING: | |
231 DCHECK(throttle->queue_pointer() != outstanding_throttles_.end()); | |
232 DCHECK(std::find(outstanding_throttles_.begin(), | |
233 outstanding_throttles_.end(), | |
234 throttle) == throttle->queue_pointer()); | |
235 outstanding_throttles_.erase(throttle->queue_pointer()); | |
236 // Fall through | |
237 case ThrottleImpl::State::AGED: | |
238 DCHECK(!throttle->start_time().is_null()); | |
239 lifetime_median_estimate_.AddSample( | |
240 (tick_clock_->NowTicks() - throttle->start_time()) | |
241 .InMillisecondsRoundedUp()); | |
242 break; | |
243 } | |
244 | |
245 DCHECK(std::find(blocked_throttles_.begin(), blocked_throttles_.end(), | |
246 throttle) == blocked_throttles_.end()); | |
247 DCHECK(std::find(outstanding_throttles_.begin(), outstanding_throttles_.end(), | |
248 throttle) == outstanding_throttles_.end()); | |
249 | |
250 // Unblock the throttles if there's some chance there's a throttle to | |
251 // unblock. | |
252 if (outstanding_throttles_.size() < kActiveRequestThrottlingLimit && | |
253 !blocked_throttles_.empty()) { | |
254 // Via PostTask so there aren't upcalls from within destructors. | |
255 base::ThreadTaskRunnerHandle::Get()->PostTask( | |
256 FROM_HERE, | |
257 base::Bind(&NetworkThrottleManagerImpl::MaybeUnblockThrottles, | |
258 weak_ptr_factory_.GetWeakPtr())); | |
259 } | |
260 } | |
261 | |
262 void NetworkThrottleManagerImpl::RecomputeOutstanding() { | |
263 // Remove all throttles that have aged out of the outstanding set. | |
264 base::TimeTicks now(tick_clock_->NowTicks()); | |
265 base::TimeDelta age_horizon(base::TimeDelta::FromMilliseconds(( | |
266 kMedianLifetimeMultiple * lifetime_median_estimate_.current_estimate()))); | |
267 while (!outstanding_throttles_.empty()) { | |
268 ThrottleImpl* throttle = *outstanding_throttles_.begin(); | |
269 if (throttle->start_time() + age_horizon >= now) | |
270 break; | |
271 | |
272 outstanding_throttles_.erase(outstanding_throttles_.begin()); | |
273 throttle->SetAged(); | |
274 throttle->set_queue_pointer(outstanding_throttles_.end()); | |
275 } | |
276 | |
277 if (outstanding_throttles_.empty()) | |
278 return; | |
279 | |
280 // If the timer is already running, be conservative and leave it alone; | |
281 // the time for which it would be set will only be later than when it's | |
282 // currently set. | |
283 // This addresses, e.g., situations where a RecomputeOutstanding() races | |
284 // with a running timer which would unblock blocked throttles. | |
285 if (outstanding_recomputation_timer_.IsRunning()) | |
286 return; | |
287 | |
288 ThrottleImpl* first_throttle(*outstanding_throttles_.begin()); | |
289 DCHECK_GE(first_throttle->start_time() + age_horizon, now); | |
290 outstanding_recomputation_timer_.Start( | |
291 FROM_HERE, ((first_throttle->start_time() + age_horizon) - now + | |
292 base::TimeDelta::FromMilliseconds(kTimerFudgeInMs)), | |
293 // Unretained use of |this| is safe because the timer is | |
294 // owned by this object, and will be torn down if this object | |
295 // is destroyed. | |
296 base::Bind(&NetworkThrottleManagerImpl::MaybeUnblockThrottles, | |
297 base::Unretained(this))); | |
298 } | |
299 | |
300 void NetworkThrottleManagerImpl::UnblockThrottle(ThrottleImpl* throttle) { | |
301 DCHECK(throttle->IsBlocked()); | |
302 | |
303 blocked_throttles_.erase(throttle->queue_pointer()); | |
304 throttle->set_start_time(tick_clock_->NowTicks()); | |
305 throttle->set_queue_pointer( | |
306 outstanding_throttles_.insert(outstanding_throttles_.end(), throttle)); | |
307 | |
308 // Called in case |*throttle| was added to a null set. | |
309 RecomputeOutstanding(); | |
310 | |
311 // May result in re-entrant calls into this class. | |
312 throttle->NotifyUnblocked(); | |
313 } | |
314 | |
315 void NetworkThrottleManagerImpl::MaybeUnblockThrottles() { | |
316 RecomputeOutstanding(); | |
317 | |
318 while (outstanding_throttles_.size() < kActiveRequestThrottlingLimit && | |
319 !blocked_throttles_.empty()) { | |
320 // NOTE: This call may result in reentrant calls into | |
321 // NetworkThrottleManagerImpl; no state should be assumed to be | |
322 // persistent across this call. | |
323 UnblockThrottle(blocked_throttles_.front()); | |
324 } | |
325 } | |
326 | |
327 } // namespace net | |
OLD | NEW |