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; | |
mmenke
2016/10/07 16:51:47
kTimerSlopMs? kTimerBonus[Epsilon/Delta]Ms? Want
Charlie Harrison
2016/10/11 14:50:51
Hm...2ms is very small for CPUs with bad clocks. I
mmenke
2016/10/11 14:54:05
I think it's worth noting correctness of this clas
Randy Smith (Not in Mondays)
2016/10/11 21:43:34
I decided to change it anyway because of the fear
Randy Smith (Not in Mondays)
2016/10/11 21:43:34
Changed to 17 and commented on why, along with a c
Randy Smith (Not in Mondays)
2016/10/11 21:43:35
kTimerFudgeInMs.
| |
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 { | |
Charlie Harrison
2016/10/11 14:50:52
Can this be an enum class?
Randy Smith (Not in Mondays)
2016/10/11 21:43:35
Sure :-}.
| |
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 BlockedQueuePointer = | |
46 NetworkThrottleManagerImpl::ThrottleList::iterator; | |
47 | |
48 // Caller must arrange that |*delegate| and |*manager| outlive | |
49 // the ThrottleImpl class. | |
50 ThrottleImpl(bool blocked, | |
51 RequestPriority priority, | |
52 ThrottleDelegate* delegate, | |
53 NetworkThrottleManagerImpl* manager, | |
54 BlockedQueuePointer blocked_queue_pointer); | |
55 | |
56 ~ThrottleImpl() override; | |
57 | |
58 // Throttle: | |
59 bool IsBlocked() const override; | |
60 RequestPriority Priority() const override; | |
mmenke
2016/10/07 16:51:47
Having both Priority() and priority() seems silly.
Randy Smith (Not in Mondays)
2016/10/11 21:43:35
That's totally a typo; thanks for noticing. Remov
| |
61 void SetPriority(RequestPriority priority) override; | |
62 | |
63 State state() const { return state_; } | |
64 | |
65 RequestPriority priority() const { return priority_; } | |
66 | |
67 BlockedQueuePointer blocked_queue_pointer() const { | |
68 return blocked_queue_pointer_; | |
69 } | |
70 void set_blocked_queue_pointer(const BlockedQueuePointer& pointer) { | |
71 blocked_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 | |
Charlie Harrison
2016/10/11 14:50:52
nit: reflow comment.
Randy Smith (Not in Mondays)
2016/10/11 21:43:34
Done.
| |
82 // may result in re-entrant calls into the manager or | |
83 // ThrottleImpl. The manager should not rely on | |
84 // any state other than its own existence being persistent | |
85 // across this call. | |
86 void NotifyUnblocked(); | |
87 | |
88 private: | |
89 State state_; | |
90 RequestPriority priority_; | |
91 ThrottleDelegate* const delegate_; | |
92 NetworkThrottleManagerImpl* const manager_; | |
93 | |
94 base::TimeTicks start_time_; | |
95 | |
96 // To allow deletion from the blocked queue (when the throttle is | |
Charlie Harrison
2016/10/11 14:50:51
nit: reflow comment.
Randy Smith (Not in Mondays)
2016/10/11 21:43:34
Done.
| |
97 // in the blocked queue). | |
98 BlockedQueuePointer blocked_queue_pointer_; | |
99 | |
100 DISALLOW_COPY_AND_ASSIGN(ThrottleImpl); | |
101 }; | |
102 | |
103 NetworkThrottleManagerImpl::ThrottleImpl::ThrottleImpl( | |
104 bool blocked, | |
105 RequestPriority priority, | |
106 NetworkThrottleManager::ThrottleDelegate* delegate, | |
107 NetworkThrottleManagerImpl* manager, | |
108 BlockedQueuePointer blocked_queue_pointer) | |
109 : state_(blocked ? BLOCKED : OUTSTANDING), | |
110 priority_(priority), | |
111 delegate_(delegate), | |
112 manager_(manager), | |
113 blocked_queue_pointer_(blocked_queue_pointer) { | |
114 DCHECK(delegate); | |
115 if (!blocked) | |
116 start_time_ = manager->tick_clock_->NowTicks(); | |
117 } | |
118 | |
119 NetworkThrottleManagerImpl::ThrottleImpl::~ThrottleImpl() { | |
120 manager_->OnThrottleDestroyed(this); | |
121 } | |
122 | |
123 bool NetworkThrottleManagerImpl::ThrottleImpl::IsBlocked() const { | |
124 return state_ == BLOCKED; | |
125 } | |
126 | |
127 RequestPriority NetworkThrottleManagerImpl::ThrottleImpl::Priority() const { | |
128 return priority_; | |
129 } | |
130 | |
131 void NetworkThrottleManagerImpl::ThrottleImpl::SetPriority( | |
132 RequestPriority new_priority) { | |
133 RequestPriority old_priority(priority_); | |
134 if (old_priority == new_priority) | |
135 return; | |
136 priority_ = new_priority; | |
137 manager_->OnThrottlePriorityChanged(this, old_priority, new_priority); | |
138 } | |
139 | |
140 void NetworkThrottleManagerImpl::ThrottleImpl::SetAged() { | |
141 DCHECK_EQ(OUTSTANDING, state_); | |
142 state_ = AGED; | |
143 } | |
144 | |
145 void NetworkThrottleManagerImpl::ThrottleImpl::NotifyUnblocked() { | |
146 // This methods should only be called once, and only if the | |
Charlie Harrison
2016/10/11 14:50:51
nit: reflow comment.
Randy Smith (Not in Mondays)
2016/10/11 21:43:35
You pick the nit of reflowing the comment, and don
| |
147 // current state is blocked. | |
148 DCHECK_EQ(BLOCKED, state_); | |
149 state_ = OUTSTANDING; | |
150 delegate_->OnThrottleUnblocked(this); | |
151 } | |
152 | |
153 NetworkThrottleManagerImpl::NetworkThrottleManagerImpl() | |
154 : lifetime_median_estimate_(PercentileEstimator::kMedianPercentile, | |
155 kInitialMedianInMs), | |
156 outstanding_recomputation_timer_(false /* retain_user_task */, | |
157 false /* is_repeating */), | |
158 outstanding_throttles_(&NetworkThrottleManagerImpl::StartTimeSetCompare), | |
159 tick_clock_(new base::DefaultTickClock()), | |
160 weak_ptr_factory_(this) { | |
161 outstanding_recomputation_timer_.SetTaskRunner( | |
162 base::MessageLoop::current()->task_runner()); | |
163 } | |
164 | |
165 NetworkThrottleManagerImpl::~NetworkThrottleManagerImpl() {} | |
166 | |
167 std::unique_ptr<NetworkThrottleManager::Throttle> | |
168 NetworkThrottleManagerImpl::CreateThrottle( | |
169 NetworkThrottleManager::ThrottleDelegate* delegate, | |
170 RequestPriority priority, | |
171 bool ignore_limits) { | |
172 bool blocked = | |
173 (!ignore_limits && priority == THROTTLED && | |
174 outstanding_throttles_.size() >= kActiveRequestThrottlingLimit); | |
175 | |
176 std::unique_ptr<NetworkThrottleManagerImpl::ThrottleImpl> throttle( | |
177 new ThrottleImpl(blocked, priority, delegate, this, | |
178 blocked_throttles_.end())); | |
mmenke
2016/10/07 16:51:47
I don't think we need the last parameter here - ca
Randy Smith (Not in Mondays)
2016/10/11 21:43:34
I'd rather not. The problem here is that default
mmenke
2016/10/11 21:48:28
Setting something to blah.end() seems really weird
Randy Smith (Not in Mondays)
2016/10/11 22:04:17
I'm happy to change it to pretty much anything you
| |
179 | |
180 if (blocked) { | |
181 throttle->set_blocked_queue_pointer( | |
182 blocked_throttles_.insert(blocked_throttles_.end(), throttle.get())); | |
183 } else { | |
184 outstanding_throttles_.insert(throttle.get()); | |
185 // Setup timer if outstanding_throttles_ was empty. | |
mmenke
2016/10/07 16:51:47
"Set up" (Setup is a noun)
Randy Smith (Not in Mondays)
2016/10/11 21:43:35
Done.
| |
186 RecomputeOutstanding(); | |
187 } | |
188 | |
189 return std::move(throttle); | |
190 } | |
191 | |
192 void NetworkThrottleManagerImpl::SetTickClockForTesting( | |
193 std::unique_ptr<base::TickClock> tick_clock) { | |
194 tick_clock_ = std::move(tick_clock); | |
195 } | |
196 | |
197 void NetworkThrottleManagerImpl::ConditionallyTriggerTimerForTesting() { | |
198 // Relies on |!retain_user_task| in timer constructor. | |
199 if (!outstanding_recomputation_timer_.user_task().is_null() && | |
mmenke
2016/10/07 16:51:47
IsRunning()
Randy Smith (Not in Mondays)
2016/10/11 21:43:35
Huh. Not sure how I missed that. Done (here and
| |
200 (tick_clock_->NowTicks() > | |
201 outstanding_recomputation_timer_.desired_run_time())) { | |
mmenke
2016/10/07 16:51:47
optional: Should the second condition be a DCHECK
Randy Smith (Not in Mondays)
2016/10/11 21:43:34
I'd argue against. When the timer was set for is
mmenke
2016/10/11 21:48:28
That works for me.
| |
202 base::Closure timer_callback(outstanding_recomputation_timer_.user_task()); | |
203 outstanding_recomputation_timer_.Stop(); | |
204 timer_callback.Run(); | |
mmenke
2016/10/07 16:51:47
Think early exit is generally preferred in this so
Randy Smith (Not in Mondays)
2016/10/11 21:43:34
Good point. Done.
| |
205 } | |
206 } | |
207 | |
208 // static | |
209 bool NetworkThrottleManagerImpl::StartTimeSetCompare(ThrottleImpl* throttle1, | |
210 ThrottleImpl* throttle2) { | |
211 // No throttle should be in the StartTimeOrderedSet with a null start | |
Charlie Harrison
2016/10/11 14:50:51
nit: I think this comment can all fit on one line.
Randy Smith (Not in Mondays)
2016/10/11 21:43:35
Done.
| |
212 // time. | |
213 DCHECK_NE(throttle1->start_time(), base::TimeTicks()); | |
214 DCHECK_NE(throttle2->start_time(), base::TimeTicks()); | |
215 return (throttle1->start_time() < throttle2->start_time() || | |
216 // So different throttles don't look equal to the comparison | |
217 // function. | |
218 (throttle1->start_time() == throttle2->start_time() && | |
219 throttle1 < throttle2)); | |
220 } | |
221 | |
222 void NetworkThrottleManagerImpl::OnThrottlePriorityChanged( | |
223 NetworkThrottleManagerImpl::ThrottleImpl* throttle, | |
224 RequestPriority old_priority, | |
225 RequestPriority new_priority) { | |
226 // The only case requiring a state change is if the priority change | |
227 // implies unblocking. | |
228 if (throttle->IsBlocked() && // Implies |old_priority == THROTTLED| | |
Charlie Harrison
2016/10/11 14:50:51
Optional: This comment is a bit redundant with the
Randy Smith (Not in Mondays)
2016/10/11 21:43:35
Done, though it didn't save any space to keep all
| |
229 new_priority != THROTTLED) { | |
230 // May result in re-entrant calls into this class. | |
231 UnblockThrottle(throttle); | |
232 } | |
233 } | |
234 | |
235 void NetworkThrottleManagerImpl::OnThrottleDestroyed(ThrottleImpl* throttle) { | |
236 switch (throttle->state()) { | |
237 case ThrottleImpl::BLOCKED: | |
238 DCHECK(throttle->blocked_queue_pointer() != blocked_throttles_.end()); | |
239 DCHECK(std::find(blocked_throttles_.begin(), blocked_throttles_.end(), | |
240 throttle) != blocked_throttles_.end()); | |
mmenke
2016/10/07 16:51:47
Replace the second "!= blocked_throttles_.end()" w
Charlie Harrison
2016/10/11 14:50:51
Related, how does DCHECK_EQ work with iterators?
Randy Smith (Not in Mondays)
2016/10/11 21:43:34
It doesn't. My rule of thumb is that if it doesn'
Randy Smith (Not in Mondays)
2016/10/11 21:43:34
Done.
| |
241 blocked_throttles_.erase(throttle->blocked_queue_pointer()); | |
242 break; | |
243 case ThrottleImpl::OUTSTANDING: { | |
244 size_t items_erased = outstanding_throttles_.erase(throttle); | |
245 DCHECK_EQ(1u, items_erased); | |
246 } | |
247 // Fall through | |
248 case ThrottleImpl::AGED: | |
249 DCHECK(!throttle->start_time().is_null()); | |
250 lifetime_median_estimate_.AddSample( | |
251 (tick_clock_->NowTicks() - throttle->start_time()) | |
252 .InMillisecondsRoundedUp()); | |
253 break; | |
254 } | |
255 | |
256 DCHECK(std::find(blocked_throttles_.begin(), blocked_throttles_.end(), | |
257 throttle) == blocked_throttles_.end()); | |
258 // Can't use std::set::count() as that uses the built in comparison | |
259 // function, which requires a possible null start time. | |
260 DCHECK(std::find(outstanding_throttles_.begin(), outstanding_throttles_.end(), | |
261 throttle) == outstanding_throttles_.end()); | |
mmenke
2016/10/07 16:51:47
I assume these can't use DCHECK_NE? Can never rem
Charlie Harrison
2016/10/11 14:50:52
Do you mean DCHECK_EQ?
Randy Smith (Not in Mondays)
2016/10/11 21:43:34
There are a whole lot of related DCHECK_XX: DCHECK
Randy Smith (Not in Mondays)
2016/10/11 21:43:35
Nope. I believe (my rule of thumb?) is that if yo
| |
262 | |
263 // Unblock the throttles if there's some chance there's a throttle to | |
264 // unblock. | |
265 if (outstanding_throttles_.size() < kActiveRequestThrottlingLimit && | |
266 !blocked_throttles_.empty()) { | |
267 // Via PostTask so there aren't upcalls from within destructors. | |
268 base::MessageLoop::current()->task_runner()->PostTask( | |
269 FROM_HERE, | |
270 base::Bind(&NetworkThrottleManagerImpl::MaybeUnblockThrottles, | |
271 weak_ptr_factory_.GetWeakPtr())); | |
272 } | |
273 } | |
274 | |
275 void NetworkThrottleManagerImpl::RecomputeOutstanding() { | |
276 // Remove all throttles that have aged out of the outstanding set. | |
277 base::TimeTicks now(tick_clock_->NowTicks()); | |
278 base::TimeDelta age_horizon(base::TimeDelta::FromMilliseconds(( | |
279 kMedianLifetimeMultiple * lifetime_median_estimate_.current_estimate()))); | |
280 while (!outstanding_throttles_.empty()) { | |
281 ThrottleImpl* throttle = *outstanding_throttles_.begin(); | |
282 if (throttle->start_time() + age_horizon >= now) | |
283 break; | |
284 | |
285 outstanding_throttles_.erase(throttle); | |
286 throttle->SetAged(); | |
287 } | |
288 | |
289 if (outstanding_throttles_.empty()) | |
290 return; | |
291 | |
292 // Start the timer if it's not started and there are outstanding throttles | |
293 // that might need to age out. If there are blocked throttles that might | |
294 // need to be unblocked, that will have been taken care of by a previously | |
295 // queued timer. | |
296 if (outstanding_recomputation_timer_.user_task().is_null()) { | |
mmenke
2016/10/07 16:51:47
outstanding_recomputation_timer_.IsRunning()?
mmenke
2016/10/07 16:51:47
optional: Maybe switch to early return? Think th
Randy Smith (Not in Mondays)
2016/10/11 21:43:34
Done.
Randy Smith (Not in Mondays)
2016/10/11 21:43:35
Done.
| |
297 ThrottleImpl* first_throttle(*outstanding_throttles_.begin()); | |
298 DCHECK_GE(first_throttle->start_time() + age_horizon, now); | |
299 outstanding_recomputation_timer_.Start( | |
300 FROM_HERE, ((first_throttle->start_time() + age_horizon) - now + | |
301 base::TimeDelta::FromMilliseconds(kTimerDelayInMs)), | |
302 // Unretained use of |this| is safe because the timer is | |
303 // owned by this object, and will be torn down if this object | |
304 // is destroyed. | |
305 base::Bind(&NetworkThrottleManagerImpl::MaybeUnblockThrottles, | |
306 base::Unretained(this))); | |
307 } | |
308 } | |
309 | |
310 void NetworkThrottleManagerImpl::UnblockThrottle(ThrottleImpl* throttle) { | |
311 DCHECK(throttle->IsBlocked()); | |
312 | |
313 blocked_throttles_.erase(throttle->blocked_queue_pointer()); | |
314 throttle->set_blocked_queue_pointer(blocked_throttles_.end()); | |
mmenke
2016/10/07 16:51:47
blocked_throttles_.end() -> NetworkThrottleManager
Randy Smith (Not in Mondays)
2016/10/11 21:43:35
As noted above, I haven't been able to convince my
| |
315 throttle->set_start_time(tick_clock_->NowTicks()); | |
316 outstanding_throttles_.insert(throttle); | |
317 | |
318 // Called in case |*throttle| was added to a null set. | |
319 RecomputeOutstanding(); | |
320 | |
321 // May result in re-entrant calls into this class. | |
322 throttle->NotifyUnblocked(); | |
323 } | |
324 | |
325 void NetworkThrottleManagerImpl::MaybeUnblockThrottles() { | |
326 RecomputeOutstanding(); | |
327 | |
328 while (outstanding_throttles_.size() < kActiveRequestThrottlingLimit && | |
329 !blocked_throttles_.empty()) { | |
330 // NOTE: This call may result in reentrant calls into | |
331 // NetworkThrottleManagerImpl; no state should be assumed to be | |
332 // persistent across this call. | |
333 UnblockThrottle(blocked_throttles_.front()); | |
334 } | |
335 } | |
336 | |
337 } // namespace net | |
OLD | NEW |