Index: net/base/network_throttle_manager_impl.cc |
diff --git a/net/base/network_throttle_manager_impl.cc b/net/base/network_throttle_manager_impl.cc |
new file mode 100644 |
index 0000000000000000000000000000000000000000..81da24d80edf3188c4d60573dd8abc32c74a4ed0 |
--- /dev/null |
+++ b/net/base/network_throttle_manager_impl.cc |
@@ -0,0 +1,274 @@ |
+// Copyright 2016 The Chromium Authors. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#include "net/base/network_throttle_manager_impl.h" |
+ |
+#include "base/logging.h" |
+#include "base/message_loop/message_loop.h" |
+#include "base/time/default_tick_clock.h" |
+ |
+namespace net { |
+ |
+// Maximum number of active requests before new THROTTLED throttles |
+// are created blocked. Throttles are unblocked as the active requests |
+// fall below this limit. |
+const size_t NetworkThrottleManagerImpl::kActiveRequestThrottlingLimit = 2; |
+ |
+// Constants used for the running estimate of the median lifetime |
+// for throttles created by this class. That estimate is used to detect |
+// throttles that are "unusually old" and hence may represent hanging GETs |
+// or long-running streams. Such throttles should not be considered |
+// "active" for the purposes of determining whether THROTTLED throttles |
+// should be created in a blocked state. |
+// Note that the precise details of this algorithm aren't very important; |
+// specifically, if it takes a while for the median estimate to reach the |
+// "actual" median of a request stream, the consequence is either a bit more |
+// of a delay in unblocking THROTTLED requests or more THROTTLED requests |
+// being unblocked than would be ideal (i.e. performance tweaks at |
+// the margins). |
+ |
+// Multiple of the current median lifetime beyond which a throttle is |
+// considered "unusually old" and not considered in counting active |
+// requests. |
+const int NetworkThrottleManagerImpl::kMedianLifetimeMultiple = 5; |
+ |
+// The median lifetime estimate starts at class creation at |
+// |kInitialMedianInMS|. When a throttle completes, the median is adjusted |
+// upwards or downwards by |kMedianEstimatorDeltaMS| milliseconds. |
+// |kMedianEstimatorDeltaMS| was chosen for simplicity, as per |
+// "precise details aren't very important", above. |
+const int NetworkThrottleManagerImpl::kInitialMedianInMS = 100; |
+const double NetworkThrottleManagerImpl::kMedianEstimatorDeltaMS = 1; |
+ |
+NetworkThrottleManagerImpl::ThrottleImpl::ThrottleImpl( |
+ bool blocked, |
+ RequestPriority priority, |
+ NetworkThrottleManager::ThrottleDelegate* delegate, |
+ NetworkThrottleManagerImpl* manager, |
+ QueuePointer queue_pointer) |
+ : blocked_(blocked), |
+ priority_(priority), |
+ delegate_(delegate), |
+ manager_(manager), |
+ creation_time_(manager->tick_clock_->NowTicks()), |
+ queue_pointer_(queue_pointer) { |
+ DCHECK(delegate); |
+} |
+ |
+NetworkThrottleManagerImpl::ThrottleImpl::~ThrottleImpl() { |
+ manager_->OnThrottleDestroyed(this); |
+} |
+ |
+bool NetworkThrottleManagerImpl::ThrottleImpl::IsBlocked() const { |
+ return blocked_; |
+} |
+ |
+RequestPriority NetworkThrottleManagerImpl::ThrottleImpl::Priority() const { |
+ return priority_; |
+} |
+ |
+void NetworkThrottleManagerImpl::ThrottleImpl::SetPriority( |
+ RequestPriority new_priority) { |
+ RequestPriority old_priority(priority_); |
+ priority_ = new_priority; |
+ manager_->OnThrottlePriorityChanged(this, old_priority, new_priority); |
+} |
+ |
+void NetworkThrottleManagerImpl::ThrottleImpl::NotifyUnblocked() { |
+ // This methods should only be called once, and only if the |
+ // current state is blocked. |
+ DCHECK(blocked_); |
+ blocked_ = false; |
+ delegate_->OnThrottleStateChanged(this); |
+} |
+ |
+NetworkThrottleManagerImpl::NetworkThrottleManagerImpl() |
+ : lifetime_median_estimate_( |
+ base::TimeDelta::FromMilliseconds(kInitialMedianInMS)), |
+ creation_ordering_set_( |
+ &NetworkThrottleManagerImpl::CompareThrottlesForCreationTime), |
+ num_throttles_blocked_(0u), |
+ num_effective_outstanding_(0u), |
+ outstanding_recomputation_timer_(false /* retain_user_task */, |
+ false /* is_repeating */), |
+ tick_clock_(new base::DefaultTickClock()) { |
+ outstanding_recomputation_timer_.SetTaskRunner( |
+ base::MessageLoop::current()->task_runner()); |
+} |
+ |
+NetworkThrottleManagerImpl::~NetworkThrottleManagerImpl() {} |
+ |
+std::unique_ptr<NetworkThrottleManager::Throttle> |
+NetworkThrottleManagerImpl::CreateThrottle( |
+ NetworkThrottleManager::ThrottleDelegate* delegate, |
+ RequestPriority priority, |
+ bool ignore_limits) { |
+ bool blocked = (!ignore_limits && priority == THROTTLED && |
+ num_effective_outstanding_ >= kActiveRequestThrottlingLimit); |
+ |
+ std::unique_ptr<NetworkThrottleManagerImpl::ThrottleImpl> throttle( |
+ new ThrottleImpl(blocked, priority, delegate, this, |
+ // Just to have a meaningful default value |
+ unblocked_requests_[priority].end())); |
+ |
+ std::list<ThrottleImpl*>* throttle_list = ListForThrottle(blocked, priority); |
+ |
+ throttle->set_queue_pointer( |
+ throttle_list->insert(throttle_list->end(), throttle.get())); |
+ creation_ordering_set_.insert(throttle.get()); |
+ if (blocked) |
+ ++num_throttles_blocked_; |
+ |
+ // Can only have increased the outstanding count (decreases due to aging out |
+ // would be caught by timer) so a MaybeUnblockThrottles() isn't needed. |
+ RecomputeOutstanding(); |
+ |
+ return std::move(throttle); |
+} |
+ |
+void NetworkThrottleManagerImpl::SetTickClockForTesting( |
+ std::unique_ptr<base::TickClock> tick_clock) { |
+ tick_clock_ = std::move(tick_clock); |
+} |
+ |
+void NetworkThrottleManagerImpl::ConditionallyTriggerTimerForTesting() { |
+ // Relies on |!retain_user_task| in timer constructor. |
+ if (!outstanding_recomputation_timer_.user_task().is_null() && |
+ (tick_clock_->NowTicks() > |
+ outstanding_recomputation_timer_.desired_run_time())) { |
+ base::Closure timer_callback(outstanding_recomputation_timer_.user_task()); |
+ outstanding_recomputation_timer_.Stop(); |
+ timer_callback.Run(); |
+ } |
+} |
+ |
+bool NetworkThrottleManagerImpl::CompareThrottlesForCreationTime( |
+ ThrottleImpl* throttle1, |
+ ThrottleImpl* throttle2) { |
+ return (throttle1->creation_time() < throttle2->creation_time() || |
+ // So different throttles don't look equal to the comparison |
+ // function. |
+ (throttle1->creation_time() == throttle2->creation_time() && |
+ throttle1 < throttle2)); |
+} |
+ |
+void NetworkThrottleManagerImpl::OnThrottlePriorityChanged( |
+ NetworkThrottleManagerImpl::ThrottleImpl* throttle, |
+ RequestPriority old_priority, |
+ RequestPriority new_priority) { |
+ ListForThrottle(throttle->IsBlocked(), old_priority) |
+ ->erase(throttle->queue_pointer()); |
+ |
+ std::list<ThrottleImpl*>* new_throttle_list = |
+ ListForThrottle(throttle->IsBlocked(), new_priority); |
+ |
+ throttle->set_queue_pointer( |
+ new_throttle_list->insert(new_throttle_list->end(), throttle)); |
+ |
+ // There is no need to call |MaybeUnblockThrottles()| because |
+ // changing a throttle priority will not have decreased the number of |
+ // outstanding throttles. But if the throttle whose priority was changed |
+ // was transitioned away from THROTTLED then it may need to be unblocked. |
+ if (old_priority == THROTTLED && new_priority != THROTTLED && |
+ throttle->IsBlocked()) { |
+ // NOTE: This call may result in reentrant calls into |
+ // NetworkThrottleManagerImpl; no state should be assumed to be |
+ // persistent across this call. |
+ --num_throttles_blocked_; |
+ throttle->NotifyUnblocked(); |
+ } |
+} |
+ |
+void NetworkThrottleManagerImpl::OnThrottleDestroyed(ThrottleImpl* throttle) { |
+ // Adjust median estimate. Algorithm from |
+ // http://arxiv.org/pdf/1407.1121v1.pdf (Algorithm 1). |
+ bool older_than_median = |
+ (tick_clock_->NowTicks() - throttle->creation_time() > |
+ lifetime_median_estimate_); |
+ |
+ lifetime_median_estimate_ += base::TimeDelta::FromMilliseconds( |
+ kMedianEstimatorDeltaMS * (older_than_median ? 1 : -1)); |
+ |
+ if (lifetime_median_estimate_ < base::TimeDelta::FromMilliseconds(1)) |
+ lifetime_median_estimate_ = base::TimeDelta::FromMilliseconds(1); |
+ |
+ ListForThrottle(throttle)->erase(throttle->queue_pointer()); |
+ size_t items_erased = creation_ordering_set_.erase(throttle); |
+ DCHECK_EQ(1u, items_erased); |
+ if (throttle->IsBlocked()) |
+ --num_throttles_blocked_; |
+ |
+ // TODO(rdsmith): Via PostTask so there aren't upcalls from within |
+ // destructors? |
+ MaybeUnblockThrottles(); |
+} |
+ |
+void NetworkThrottleManagerImpl::RecomputeOutstanding() { |
+ num_effective_outstanding_ = |
+ creation_ordering_set_.size() - num_throttles_blocked_; |
+ if (num_effective_outstanding_ == 0) { |
+ outstanding_recomputation_timer_.Stop(); |
+ return; |
+ } |
+ |
+ // The number of throttles that "count" as outstanding is the |
+ // total number of throttles minus all throttles that are |
+ // older than |kMedianLifetimeMultiple * lifetime_median_estimate_|. |
+ base::TimeTicks age_horizon(tick_clock_->NowTicks() - |
+ kMedianLifetimeMultiple * |
+ lifetime_median_estimate_); |
+ for (const auto* throttle : creation_ordering_set_) { |
+ if (throttle->creation_time() > age_horizon) { |
+ // The earliest we might need to re-evaluate the outstanding count |
+ // and blocked status is the amount of time it will take the current |
+ // element to age out of the effective set. |
+ outstanding_recomputation_timer_.Start( |
+ FROM_HERE, throttle->creation_time() - age_horizon, |
+ // Unretained use of |this| is safe because the timer is |
+ // owned by this object, and will be torn down if this object |
+ // is destroyed. |
+ base::Bind(&NetworkThrottleManagerImpl::MaybeUnblockThrottles, |
+ base::Unretained(this))); |
+ break; |
+ } |
+ // Only unblocked throttles are considered outstanding, so only those |
+ // throttles need to be subtracted out due to aging. |
+ if (!throttle->IsBlocked()) |
+ --num_effective_outstanding_; |
+ } |
+} |
+ |
+void NetworkThrottleManagerImpl::MaybeUnblockThrottles() { |
+ RecomputeOutstanding(); |
+ |
+ while (num_effective_outstanding_ < kActiveRequestThrottlingLimit && |
+ !blocked_requests_[THROTTLED].empty()) { |
+ ThrottleImpl* to_unblock = blocked_requests_[THROTTLED].front(); |
+ blocked_requests_[THROTTLED].pop_front(); |
+ |
+ to_unblock->set_queue_pointer(unblocked_requests_[THROTTLED].insert( |
+ unblocked_requests_[THROTTLED].end(), to_unblock)); |
+ |
+ ++num_effective_outstanding_; |
+ --num_throttles_blocked_; |
+ |
+ // NOTE: This call may result in reentrant calls into |
+ // NetworkThrottleManagerImpl; no state should be assumed to be |
+ // persistent across this call. |
+ to_unblock->NotifyUnblocked(); |
+ } |
+} |
+ |
+std::list<NetworkThrottleManagerImpl::ThrottleImpl*>* |
+NetworkThrottleManagerImpl::ListForThrottle(bool blocked, |
+ RequestPriority priority) { |
+ return &((blocked ? blocked_requests_ : unblocked_requests_)[priority]); |
+} |
+ |
+std::list<NetworkThrottleManagerImpl::ThrottleImpl*>* |
+NetworkThrottleManagerImpl::ListForThrottle(ThrottleImpl* throttle) { |
+ return ListForThrottle(throttle->IsBlocked(), throttle->priority()); |
+} |
+ |
+} // namespace net |