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 "base/logging.h" |
| 8 #include "base/message_loop/message_loop.h" |
| 9 #include "base/time/default_tick_clock.h" |
| 10 |
| 11 namespace net { |
| 12 |
| 13 // Maximum number of active requests before new THROTTLED throttles |
| 14 // are created blocked. Throttles are unblocked as the active requests |
| 15 // fall below this limit. |
| 16 const size_t NetworkThrottleManagerImpl::kActiveRequestThrottlingLimit = 2; |
| 17 |
| 18 // Constants used for the running estimate of the median lifetime |
| 19 // for throttles created by this class. That estimate is used to detect |
| 20 // throttles that are "unusually old" and hence may represent hanging GETs |
| 21 // or long-running streams. Such throttles should not be considered |
| 22 // "active" for the purposes of determining whether THROTTLED throttles |
| 23 // should be created in a blocked state. |
| 24 // Note that the precise details of this algorithm aren't very important; |
| 25 // specifically, if it takes a while for the median estimate to reach the |
| 26 // "actual" median of a request stream, the consequence is either a bit more |
| 27 // of a delay in unblocking THROTTLED requests or more THROTTLED requests |
| 28 // being unblocked than would be ideal (i.e. performance tweaks at |
| 29 // the margins). |
| 30 |
| 31 // Multiple of the current median lifetime beyond which a throttle is |
| 32 // considered "unusually old" and not considered in counting active |
| 33 // requests. |
| 34 const int NetworkThrottleManagerImpl::kMedianLifetimeMultiple = 5; |
| 35 |
| 36 // The median lifetime estimate starts at class creation at |
| 37 // |kInitialMedianInMS|. When a throttle completes, the median is adjusted |
| 38 // upwards or downwards by |kMedianEstimatorDeltaMS| milliseconds. |
| 39 // |kMedianEstimatorDeltaMS| was chosen for simplicity, as per |
| 40 // "precise details aren't very important", above. |
| 41 const int NetworkThrottleManagerImpl::kInitialMedianInMS = 100; |
| 42 const double NetworkThrottleManagerImpl::kMedianEstimatorDeltaMS = 1; |
| 43 |
| 44 NetworkThrottleManagerImpl::ThrottleImpl::ThrottleImpl( |
| 45 bool blocked, |
| 46 RequestPriority priority, |
| 47 NetworkThrottleManager::ThrottleDelegate* delegate, |
| 48 NetworkThrottleManagerImpl* manager, |
| 49 QueuePointer queue_pointer) |
| 50 : blocked_(blocked), |
| 51 priority_(priority), |
| 52 delegate_(delegate), |
| 53 manager_(manager), |
| 54 creation_time_(manager->tick_clock_->NowTicks()), |
| 55 queue_pointer_(queue_pointer) { |
| 56 DCHECK(delegate); |
| 57 } |
| 58 |
| 59 NetworkThrottleManagerImpl::ThrottleImpl::~ThrottleImpl() { |
| 60 manager_->OnThrottleDestroyed(this); |
| 61 } |
| 62 |
| 63 bool NetworkThrottleManagerImpl::ThrottleImpl::IsBlocked() const { |
| 64 return blocked_; |
| 65 } |
| 66 |
| 67 RequestPriority NetworkThrottleManagerImpl::ThrottleImpl::Priority() const { |
| 68 return priority_; |
| 69 } |
| 70 |
| 71 void NetworkThrottleManagerImpl::ThrottleImpl::SetPriority( |
| 72 RequestPriority new_priority) { |
| 73 RequestPriority old_priority(priority_); |
| 74 priority_ = new_priority; |
| 75 manager_->OnThrottlePriorityChanged(this, old_priority, new_priority); |
| 76 } |
| 77 |
| 78 void NetworkThrottleManagerImpl::ThrottleImpl::NotifyUnblocked() { |
| 79 // This methods should only be called once, and only if the |
| 80 // current state is blocked. |
| 81 DCHECK(blocked_); |
| 82 blocked_ = false; |
| 83 delegate_->OnThrottleStateChanged(this); |
| 84 } |
| 85 |
| 86 NetworkThrottleManagerImpl::NetworkThrottleManagerImpl() |
| 87 : lifetime_median_estimate_( |
| 88 base::TimeDelta::FromMilliseconds(kInitialMedianInMS)), |
| 89 creation_ordering_set_( |
| 90 &NetworkThrottleManagerImpl::CompareThrottlesForCreationTime), |
| 91 num_throttles_blocked_(0u), |
| 92 num_effective_outstanding_(0u), |
| 93 outstanding_recomputation_timer_(false /* retain_user_task */, |
| 94 false /* is_repeating */), |
| 95 tick_clock_(new base::DefaultTickClock()) { |
| 96 outstanding_recomputation_timer_.SetTaskRunner( |
| 97 base::MessageLoop::current()->task_runner()); |
| 98 } |
| 99 |
| 100 NetworkThrottleManagerImpl::~NetworkThrottleManagerImpl() {} |
| 101 |
| 102 std::unique_ptr<NetworkThrottleManager::Throttle> |
| 103 NetworkThrottleManagerImpl::CreateThrottle( |
| 104 NetworkThrottleManager::ThrottleDelegate* delegate, |
| 105 RequestPriority priority, |
| 106 bool ignore_limits) { |
| 107 bool blocked = (!ignore_limits && priority == THROTTLED && |
| 108 num_effective_outstanding_ >= kActiveRequestThrottlingLimit); |
| 109 |
| 110 std::unique_ptr<NetworkThrottleManagerImpl::ThrottleImpl> throttle( |
| 111 new ThrottleImpl(blocked, priority, delegate, this, |
| 112 // Just to have a meaningful default value |
| 113 unblocked_requests_[priority].end())); |
| 114 |
| 115 std::list<ThrottleImpl*>* throttle_list = ListForThrottle(blocked, priority); |
| 116 |
| 117 throttle->set_queue_pointer( |
| 118 throttle_list->insert(throttle_list->end(), throttle.get())); |
| 119 creation_ordering_set_.insert(throttle.get()); |
| 120 if (blocked) |
| 121 ++num_throttles_blocked_; |
| 122 |
| 123 // Can only have increased the outstanding count (decreases due to aging out |
| 124 // would be caught by timer) so a MaybeUnblockThrottles() isn't needed. |
| 125 RecomputeOutstanding(); |
| 126 |
| 127 return std::move(throttle); |
| 128 } |
| 129 |
| 130 void NetworkThrottleManagerImpl::SetTickClockForTesting( |
| 131 std::unique_ptr<base::TickClock> tick_clock) { |
| 132 tick_clock_ = std::move(tick_clock); |
| 133 } |
| 134 |
| 135 void NetworkThrottleManagerImpl::ConditionallyTriggerTimerForTesting() { |
| 136 // Relies on |!retain_user_task| in timer constructor. |
| 137 if (!outstanding_recomputation_timer_.user_task().is_null() && |
| 138 (tick_clock_->NowTicks() > |
| 139 outstanding_recomputation_timer_.desired_run_time())) { |
| 140 base::Closure timer_callback(outstanding_recomputation_timer_.user_task()); |
| 141 outstanding_recomputation_timer_.Stop(); |
| 142 timer_callback.Run(); |
| 143 } |
| 144 } |
| 145 |
| 146 bool NetworkThrottleManagerImpl::CompareThrottlesForCreationTime( |
| 147 ThrottleImpl* throttle1, |
| 148 ThrottleImpl* throttle2) { |
| 149 return (throttle1->creation_time() < throttle2->creation_time() || |
| 150 // So different throttles don't look equal to the comparison |
| 151 // function. |
| 152 (throttle1->creation_time() == throttle2->creation_time() && |
| 153 throttle1 < throttle2)); |
| 154 } |
| 155 |
| 156 void NetworkThrottleManagerImpl::OnThrottlePriorityChanged( |
| 157 NetworkThrottleManagerImpl::ThrottleImpl* throttle, |
| 158 RequestPriority old_priority, |
| 159 RequestPriority new_priority) { |
| 160 ListForThrottle(throttle->IsBlocked(), old_priority) |
| 161 ->erase(throttle->queue_pointer()); |
| 162 |
| 163 std::list<ThrottleImpl*>* new_throttle_list = |
| 164 ListForThrottle(throttle->IsBlocked(), new_priority); |
| 165 |
| 166 throttle->set_queue_pointer( |
| 167 new_throttle_list->insert(new_throttle_list->end(), throttle)); |
| 168 |
| 169 // There is no need to call |MaybeUnblockThrottles()| because |
| 170 // changing a throttle priority will not have decreased the number of |
| 171 // outstanding throttles. But if the throttle whose priority was changed |
| 172 // was transitioned away from THROTTLED then it may need to be unblocked. |
| 173 if (old_priority == THROTTLED && new_priority != THROTTLED && |
| 174 throttle->IsBlocked()) { |
| 175 // NOTE: This call may result in reentrant calls into |
| 176 // NetworkThrottleManagerImpl; no state should be assumed to be |
| 177 // persistent across this call. |
| 178 --num_throttles_blocked_; |
| 179 throttle->NotifyUnblocked(); |
| 180 } |
| 181 } |
| 182 |
| 183 void NetworkThrottleManagerImpl::OnThrottleDestroyed(ThrottleImpl* throttle) { |
| 184 // Adjust median estimate. Algorithm from |
| 185 // http://arxiv.org/pdf/1407.1121v1.pdf (Algorithm 1). |
| 186 bool older_than_median = |
| 187 (tick_clock_->NowTicks() - throttle->creation_time() > |
| 188 lifetime_median_estimate_); |
| 189 |
| 190 lifetime_median_estimate_ += base::TimeDelta::FromMilliseconds( |
| 191 kMedianEstimatorDeltaMS * (older_than_median ? 1 : -1)); |
| 192 |
| 193 if (lifetime_median_estimate_ < base::TimeDelta::FromMilliseconds(1)) |
| 194 lifetime_median_estimate_ = base::TimeDelta::FromMilliseconds(1); |
| 195 |
| 196 ListForThrottle(throttle)->erase(throttle->queue_pointer()); |
| 197 size_t items_erased = creation_ordering_set_.erase(throttle); |
| 198 DCHECK_EQ(1u, items_erased); |
| 199 if (throttle->IsBlocked()) |
| 200 --num_throttles_blocked_; |
| 201 |
| 202 // TODO(rdsmith): Via PostTask so there aren't upcalls from within |
| 203 // destructors? |
| 204 MaybeUnblockThrottles(); |
| 205 } |
| 206 |
| 207 void NetworkThrottleManagerImpl::RecomputeOutstanding() { |
| 208 num_effective_outstanding_ = |
| 209 creation_ordering_set_.size() - num_throttles_blocked_; |
| 210 if (num_effective_outstanding_ == 0) { |
| 211 outstanding_recomputation_timer_.Stop(); |
| 212 return; |
| 213 } |
| 214 |
| 215 // The number of throttles that "count" as outstanding is the |
| 216 // total number of throttles minus all throttles that are |
| 217 // older than |kMedianLifetimeMultiple * lifetime_median_estimate_|. |
| 218 base::TimeTicks age_horizon(tick_clock_->NowTicks() - |
| 219 kMedianLifetimeMultiple * |
| 220 lifetime_median_estimate_); |
| 221 for (const auto* throttle : creation_ordering_set_) { |
| 222 if (throttle->creation_time() > age_horizon) { |
| 223 // The earliest we might need to re-evaluate the outstanding count |
| 224 // and blocked status is the amount of time it will take the current |
| 225 // element to age out of the effective set. |
| 226 outstanding_recomputation_timer_.Start( |
| 227 FROM_HERE, throttle->creation_time() - age_horizon, |
| 228 // Unretained use of |this| is safe because the timer is |
| 229 // owned by this object, and will be torn down if this object |
| 230 // is destroyed. |
| 231 base::Bind(&NetworkThrottleManagerImpl::MaybeUnblockThrottles, |
| 232 base::Unretained(this))); |
| 233 break; |
| 234 } |
| 235 // Only unblocked throttles are considered outstanding, so only those |
| 236 // throttles need to be subtracted out due to aging. |
| 237 if (!throttle->IsBlocked()) |
| 238 --num_effective_outstanding_; |
| 239 } |
| 240 } |
| 241 |
| 242 void NetworkThrottleManagerImpl::MaybeUnblockThrottles() { |
| 243 RecomputeOutstanding(); |
| 244 |
| 245 while (num_effective_outstanding_ < kActiveRequestThrottlingLimit && |
| 246 !blocked_requests_[THROTTLED].empty()) { |
| 247 ThrottleImpl* to_unblock = blocked_requests_[THROTTLED].front(); |
| 248 blocked_requests_[THROTTLED].pop_front(); |
| 249 |
| 250 to_unblock->set_queue_pointer(unblocked_requests_[THROTTLED].insert( |
| 251 unblocked_requests_[THROTTLED].end(), to_unblock)); |
| 252 |
| 253 ++num_effective_outstanding_; |
| 254 --num_throttles_blocked_; |
| 255 |
| 256 // NOTE: This call may result in reentrant calls into |
| 257 // NetworkThrottleManagerImpl; no state should be assumed to be |
| 258 // persistent across this call. |
| 259 to_unblock->NotifyUnblocked(); |
| 260 } |
| 261 } |
| 262 |
| 263 std::list<NetworkThrottleManagerImpl::ThrottleImpl*>* |
| 264 NetworkThrottleManagerImpl::ListForThrottle(bool blocked, |
| 265 RequestPriority priority) { |
| 266 return &((blocked ? blocked_requests_ : unblocked_requests_)[priority]); |
| 267 } |
| 268 |
| 269 std::list<NetworkThrottleManagerImpl::ThrottleImpl*>* |
| 270 NetworkThrottleManagerImpl::ListForThrottle(ThrottleImpl* throttle) { |
| 271 return ListForThrottle(throttle->IsBlocked(), throttle->priority()); |
| 272 } |
| 273 |
| 274 } // namespace net |
OLD | NEW |