Implement THROTTLED priority semantics.

net/base/network_throttle_manager_impl.cc

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