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/message_loop/message_loop.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 const int kTimerDelayInMs = 2; | |
26 | |
27 class NetworkThrottleManagerImpl::ThrottleImpl | |
28 : public NetworkThrottleManager::Throttle { | |
29 public: | |
30 // Allowed state transitions are BLOCKED -> OUTSTANDING -> AGED. | |
31 // Throttles may be created in the BLOCKED or OUTSTANDING states. | |
32 enum State { | |
33 // Not allowed to proceed by manager. | |
34 BLOCKED, | |
35 | |
36 // Allowed to proceed, counts as an "outstanding" request for | |
37 // manager accounting purposes. | |
38 OUTSTANDING, | |
39 | |
40 // Old enough to not count as "outstanding" anymore for | |
41 // manager accounting purposes. | |
42 AGED | |
43 }; | |
44 | |
45 using QueuePointer = NetworkThrottleManagerImpl::ThrottleList::iterator; | |
46 | |
47 // Caller must arrange that |*delegate| and |*manager| outlive | |
48 // the ThrottleImpl class. | |
49 ThrottleImpl(bool blocked, | |
50 RequestPriority priority, | |
51 ThrottleDelegate* delegate, | |
52 NetworkThrottleManagerImpl* manager, | |
53 QueuePointer queue_pointer); | |
54 | |
55 ~ThrottleImpl() override; | |
56 | |
57 // Throttle: | |
58 bool IsBlocked() const override; | |
59 RequestPriority Priority() const override; | |
60 void SetPriority(RequestPriority priority) override; | |
61 | |
62 State state() const { return state_; } | |
63 | |
64 RequestPriority priority() const { return priority_; } | |
65 | |
66 QueuePointer queue_pointer() const { return queue_pointer_; } | |
67 void set_queue_pointer(const QueuePointer& pointer) { | |
68 queue_pointer_ = pointer; | |
69 } | |
70 | |
71 void set_start_time(base::TimeTicks start_time) { start_time_ = start_time; } | |
72 base::TimeTicks start_time() const { return start_time_; } | |
73 | |
74 // Change the throttle's state to AGED. The previous | |
75 // state must be OUTSTANDING. | |
76 void SetAged(); | |
77 | |
78 // Note that this call calls the delegate, and hence | |
79 // may result in re-entrant calls into the manager or | |
80 // ThrottleImpl. The manager should not rely on | |
81 // any state other than its own existence being persistent | |
82 // across this call. | |
83 void NotifyUnblocked(); | |
84 | |
85 private: | |
86 State state_; | |
87 RequestPriority priority_; | |
88 ThrottleDelegate* const delegate_; | |
89 NetworkThrottleManagerImpl* const manager_; | |
90 | |
91 base::TimeTicks start_time_; | |
92 | |
93 // For deletion from owning queue. | |
Charlie Harrison
2016/10/03 20:53:49
Can you clarify that this is only for tracking whe
Randy Smith (Not in Mondays)
2016/10/06 20:50:24
That's a really good point. I've changed names an
| |
94 QueuePointer queue_pointer_; | |
95 | |
96 DISALLOW_COPY_AND_ASSIGN(ThrottleImpl); | |
97 }; | |
98 | |
99 NetworkThrottleManagerImpl::ThrottleImpl::ThrottleImpl( | |
100 bool blocked, | |
101 RequestPriority priority, | |
102 NetworkThrottleManager::ThrottleDelegate* delegate, | |
103 NetworkThrottleManagerImpl* manager, | |
104 QueuePointer queue_pointer) | |
105 : state_(blocked ? BLOCKED : OUTSTANDING), | |
106 priority_(priority), | |
107 delegate_(delegate), | |
108 manager_(manager), | |
109 queue_pointer_(queue_pointer) { | |
110 DCHECK(delegate); | |
111 if (!blocked) | |
112 start_time_ = manager->tick_clock_->NowTicks(); | |
113 } | |
114 | |
115 NetworkThrottleManagerImpl::ThrottleImpl::~ThrottleImpl() { | |
116 manager_->OnThrottleDestroyed(this); | |
117 } | |
118 | |
119 bool NetworkThrottleManagerImpl::ThrottleImpl::IsBlocked() const { | |
120 return state_ == BLOCKED; | |
121 } | |
122 | |
123 RequestPriority NetworkThrottleManagerImpl::ThrottleImpl::Priority() const { | |
124 return priority_; | |
125 } | |
126 | |
127 void NetworkThrottleManagerImpl::ThrottleImpl::SetPriority( | |
128 RequestPriority new_priority) { | |
129 RequestPriority old_priority(priority_); | |
130 if (old_priority == new_priority) | |
131 return; | |
132 priority_ = new_priority; | |
133 manager_->OnThrottlePriorityChanged(this, old_priority, new_priority); | |
134 } | |
135 | |
136 void NetworkThrottleManagerImpl::ThrottleImpl::SetAged() { | |
137 DCHECK_EQ(OUTSTANDING, state_); | |
138 state_ = AGED; | |
139 } | |
140 | |
141 void NetworkThrottleManagerImpl::ThrottleImpl::NotifyUnblocked() { | |
142 // This methods should only be called once, and only if the | |
143 // current state is blocked. | |
144 DCHECK_EQ(BLOCKED, state_); | |
145 state_ = OUTSTANDING; | |
146 delegate_->OnThrottleStateChanged(this); | |
Charlie Harrison
2016/10/03 20:53:48
This is the only time we notify OnThrottleStateCha
Randy Smith (Not in Mondays)
2016/10/06 20:50:24
Yeah, this gets into the whole question about how
| |
147 } | |
148 | |
149 NetworkThrottleManagerImpl::NetworkThrottleManagerImpl() | |
150 : lifetime_median_estimate_(PercentileEstimator::kMedianPercentile, | |
151 kInitialMedianInMs), | |
152 outstanding_recomputation_timer_(false /* retain_user_task */, | |
153 false /* is_repeating */), | |
154 outstanding_throttles_(&NetworkThrottleManagerImpl::StartTimeSetCompare), | |
155 first_outstanding_throttle_(nullptr), | |
156 tick_clock_(new base::DefaultTickClock()), | |
157 weak_ptr_factory_(this) { | |
158 outstanding_recomputation_timer_.SetTaskRunner( | |
159 base::MessageLoop::current()->task_runner()); | |
160 } | |
161 | |
162 NetworkThrottleManagerImpl::~NetworkThrottleManagerImpl() { | |
163 DCHECK(!first_outstanding_throttle_); | |
164 } | |
165 | |
166 std::unique_ptr<NetworkThrottleManager::Throttle> | |
167 NetworkThrottleManagerImpl::CreateThrottle( | |
168 NetworkThrottleManager::ThrottleDelegate* delegate, | |
169 RequestPriority priority, | |
170 bool ignore_limits) { | |
171 bool blocked = | |
172 (!ignore_limits && priority == THROTTLED && | |
173 outstanding_throttles_.size() >= kActiveRequestThrottlingLimit); | |
174 | |
175 std::unique_ptr<NetworkThrottleManagerImpl::ThrottleImpl> throttle( | |
176 new ThrottleImpl(blocked, priority, delegate, this, | |
177 blocked_throttles_.end())); | |
178 | |
179 if (blocked) { | |
180 throttle->set_queue_pointer( | |
181 blocked_throttles_.insert(blocked_throttles_.end(), throttle.get())); | |
182 } else { | |
183 outstanding_throttles_.insert(throttle.get()); | |
184 RecomputeOutstanding(); | |
Charlie Harrison
2016/10/03 20:53:48
It might be worth a comment to explain why this is
Randy Smith (Not in Mondays)
2016/10/06 20:50:24
Meaning when this is the first outstanding throttl
| |
185 } | |
186 | |
187 return std::move(throttle); | |
188 } | |
189 | |
190 void NetworkThrottleManagerImpl::SetTickClockForTesting( | |
191 std::unique_ptr<base::TickClock> tick_clock) { | |
192 tick_clock_ = std::move(tick_clock); | |
193 } | |
194 | |
195 void NetworkThrottleManagerImpl::ConditionallyTriggerTimerForTesting() { | |
196 // Relies on |!retain_user_task| in timer constructor. | |
197 if (!outstanding_recomputation_timer_.user_task().is_null() && | |
198 (tick_clock_->NowTicks() > | |
199 outstanding_recomputation_timer_.desired_run_time())) { | |
200 base::Closure timer_callback(outstanding_recomputation_timer_.user_task()); | |
201 outstanding_recomputation_timer_.Stop(); | |
202 timer_callback.Run(); | |
203 } | |
204 } | |
205 | |
206 // static | |
207 bool NetworkThrottleManagerImpl::StartTimeSetCompare(ThrottleImpl* throttle1, | |
208 ThrottleImpl* throttle2) { | |
209 // No throttle should be in the StartTimeOrderedSet with a null start | |
210 // time. | |
211 DCHECK_NE(throttle1->start_time(), base::TimeTicks()); | |
212 DCHECK_NE(throttle2->start_time(), base::TimeTicks()); | |
213 return (throttle1->start_time() < throttle2->start_time() || | |
214 // So different throttles don't look equal to the comparison | |
215 // function. | |
216 (throttle1->start_time() == throttle2->start_time() && | |
217 throttle1 < throttle2)); | |
218 } | |
219 | |
220 void NetworkThrottleManagerImpl::OnThrottlePriorityChanged( | |
221 NetworkThrottleManagerImpl::ThrottleImpl* throttle, | |
222 RequestPriority old_priority, | |
223 RequestPriority new_priority) { | |
224 // The only case requiring a state change is if the priority change | |
225 // implies unblocking. | |
226 if (throttle->IsBlocked() && // Implies |old_priority == THROTTLED| | |
227 new_priority != THROTTLED) { | |
228 // May result in re-entrant calls into this class. | |
229 UnblockThrottle(throttle); | |
230 } | |
231 } | |
232 | |
233 void NetworkThrottleManagerImpl::OnThrottleDestroyed(ThrottleImpl* throttle) { | |
234 switch (throttle->state()) { | |
235 case ThrottleImpl::BLOCKED: | |
236 DCHECK(throttle->queue_pointer() != blocked_throttles_.end()); | |
237 DCHECK(std::find(blocked_throttles_.begin(), blocked_throttles_.end(), | |
238 throttle) != blocked_throttles_.end()); | |
239 blocked_throttles_.erase(throttle->queue_pointer()); | |
240 break; | |
241 case ThrottleImpl::OUTSTANDING: { | |
242 size_t items_erased = outstanding_throttles_.erase(throttle); | |
243 if (reinterpret_cast<void*>(throttle) == first_outstanding_throttle_) { | |
244 first_outstanding_throttle_ = | |
245 (outstanding_throttles_.empty() | |
246 ? nullptr | |
247 : reinterpret_cast<void*>(*outstanding_throttles_.begin())); | |
248 } | |
249 DCHECK_EQ(1u, items_erased); | |
250 } | |
251 // Fall through | |
252 case ThrottleImpl::AGED: | |
253 DCHECK_NE(throttle->start_time(), base::TimeTicks()); | |
Charlie Harrison
2016/10/03 20:53:48
nit: DCHECK(!throttle->start_time().is_null()) is
Randy Smith (Not in Mondays)
2016/10/06 20:50:24
Done.
| |
254 lifetime_median_estimate_.AddSample( | |
255 (tick_clock_->NowTicks() - throttle->start_time()) | |
256 .InMillisecondsRoundedUp()); | |
257 break; | |
258 } | |
259 | |
260 DCHECK(std::find(blocked_throttles_.begin(), blocked_throttles_.end(), | |
261 throttle) == blocked_throttles_.end()); | |
262 // Can't use std::set::count() as that uses the built in comparison | |
263 // function, which requires a possible null start time. | |
264 DCHECK(std::find(outstanding_throttles_.begin(), outstanding_throttles_.end(), | |
265 throttle) == outstanding_throttles_.end()); | |
266 | |
267 // Via PostTask so there aren't upcalls from within destructors. | |
268 base::MessageLoop::current()->task_runner()->PostTask( | |
269 FROM_HERE, base::Bind(&NetworkThrottleManagerImpl::MaybeUnblockThrottles, | |
270 weak_ptr_factory_.GetWeakPtr())); | |
mmenke
2016/10/04 16:31:40
Should we duplicate the check in MaybeUnblockThrot
Randy Smith (Not in Mondays)
2016/10/06 20:50:24
Done.
| |
271 } | |
272 | |
273 void NetworkThrottleManagerImpl::RecomputeOutstanding() { | |
274 // Remove all throttles that have aged out of the outstanding set. | |
275 base::TimeTicks now(tick_clock_->NowTicks()); | |
276 base::TimeDelta age_horizon(base::TimeDelta::FromMilliseconds(( | |
277 kMedianLifetimeMultiple * lifetime_median_estimate_.current_estimate()))); | |
278 while (!outstanding_throttles_.empty()) { | |
279 ThrottleImpl* throttle = *outstanding_throttles_.begin(); | |
280 if (throttle->start_time() > now - age_horizon) | |
Charlie Harrison
2016/10/03 20:53:49
throttle->start_time() + age_horizon > now
This a
mmenke
2016/10/04 16:31:40
>=? That's the time we're actually aiming at with
Randy Smith (Not in Mondays)
2016/10/06 20:50:24
Done.
Randy Smith (Not in Mondays)
2016/10/06 20:50:24
Done.
| |
281 break; | |
282 | |
283 outstanding_throttles_.erase(throttle); | |
284 throttle->SetAged(); | |
285 } | |
286 | |
287 // If the set is now empty, no timer is needed. | |
288 if (outstanding_throttles_.empty()) { | |
289 first_outstanding_throttle_ = nullptr; | |
290 outstanding_recomputation_timer_.Stop(); | |
mmenke
2016/10/04 16:31:40
I think stopping the timer is actually incorrect -
Charlie Harrison
2016/10/04 16:41:44
It feels like what we really want is the be callin
mmenke
2016/10/04 16:53:58
I'm more concerned about calling UnblockThrottle w
Charlie Harrison
2016/10/04 16:56:44
Fair point that's a valid concern.
mmenke
2016/10/04 18:59:47
Maybe just a method to start the timer if need be
Randy Smith (Not in Mondays)
2016/10/06 20:50:24
Documenting offline conversation: Given the forwar
| |
291 return; | |
292 } | |
293 | |
294 // If the initial throttle hasn't changed, neither has the | |
295 // right timing for the timer (modulo changes in lifetime_median_estimate_, | |
296 // which should change slowly enough that we don't need to track it | |
297 // exactly for a heuristic). | |
298 ThrottleImpl* first_throttle = *outstanding_throttles_.begin(); | |
Charlie Harrison
2016/10/03 20:53:48
DCHECK that the timer is running?
Charlie Harrison
2016/10/04 16:41:44
nevermind...
Randy Smith (Not in Mondays)
2016/10/06 20:50:24
I'm killing first_outstanding_throttle_ anyway.
| |
299 if (first_outstanding_throttle_ == reinterpret_cast<void*>(first_throttle)) | |
300 return; | |
301 first_outstanding_throttle_ = reinterpret_cast<void*>(first_throttle); | |
302 | |
303 outstanding_recomputation_timer_.Start( | |
304 FROM_HERE, ((first_throttle->start_time() + age_horizon) - now + | |
Charlie Harrison
2016/10/03 20:53:49
Optional: DCHECK that start_time() + age_horizon >
Randy Smith (Not in Mondays)
2016/10/06 20:50:24
Done.
| |
305 base::TimeDelta::FromMilliseconds(kTimerDelayInMs)), | |
306 // Unretained use of |this| is safe because the timer is | |
307 // owned by this object, and will be torn down if this object | |
308 // is destroyed. | |
309 base::Bind(&NetworkThrottleManagerImpl::MaybeUnblockThrottles, | |
310 base::Unretained(this))); | |
311 } | |
312 | |
313 void NetworkThrottleManagerImpl::UnblockThrottle(ThrottleImpl* throttle) { | |
314 DCHECK(throttle->IsBlocked()); | |
315 | |
316 blocked_throttles_.erase(throttle->queue_pointer()); | |
317 throttle->set_queue_pointer(blocked_throttles_.end()); | |
318 throttle->set_start_time(tick_clock_->NowTicks()); | |
319 outstanding_throttles_.insert(throttle); | |
320 | |
321 // Called in case |*throttle| was added to a null set. | |
322 RecomputeOutstanding(); | |
323 | |
324 // May result in re-entrant calls into this class. | |
325 throttle->NotifyUnblocked(); | |
326 } | |
327 | |
328 void NetworkThrottleManagerImpl::MaybeUnblockThrottles() { | |
329 RecomputeOutstanding(); | |
330 | |
331 while (outstanding_throttles_.size() < kActiveRequestThrottlingLimit && | |
332 !blocked_throttles_.empty()) { | |
333 // NOTE: This call may result in reentrant calls into | |
334 // NetworkThrottleManagerImpl; no state should be assumed to be | |
335 // persistent across this call. | |
336 UnblockThrottle(blocked_throttles_.front()); | |
337 } | |
338 } | |
339 | |
340 } // namespace net | |
OLD | NEW |