Implement THROTTLED priority semantics.

net/base/network_throttle_manager_impl.cc

+// 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.

[mmenke, 2016/07/11 17:17:20]

Docs should be with declaration, not definition.

[Randy Smith (Not in Mondays), 2016/08/29 19:44:52]

So, I'll call out that I think these constants (other than
kActiveRequestThrottlingLimit, which totally should be doc'd in the .h file) are
pretty close to implementation details and the only reason I'm exporting them in
the .h file is so that the tests can play with the values.  But I do agree that
they're part of the interface, for all that they're a pretty trivial part that I
really hope no consumers rely on, and I'll move all the docs to the .h file.

+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;

[mmenke, 2016/07/11 17:17:20]

nit:  Ms (x2)

[mmenke, 2016/07/11 17:17:20]

There doesn't seem to be any reason for kMedianEstimatorDeltaMS to be a double,
is there?  You're just multiplying it by -1 or 1, and then creating a TimeDelta.

[Randy Smith (Not in Mondays), 2016/08/29 19:44:52]

Yes, but moot; it's gone.

[Randy Smith (Not in Mondays), 2016/08/29 19:44:52]

One done, the other is moot and has been removed.

+
+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_ =

[mmenke, 2016/07/11 17:17:20]

This doesn't seem like it should be a class variable - we recompute it from
scratch for every time we access it (Either just before using it, or just
after), so doesn't seem to make any sense as a class member.

[Randy Smith (Not in Mondays), 2016/08/29 19:44:52]

Hmmm.  I started to do this refactor, and I think there's a problem with it. 
MaybeUnblockThrottles() unblocks throttles while num_effective_outstanding_ is
below the kActiveRequestThrottlingLimit.  The tweak that UnblockThrottle
(originally the contents of the while loop of MayeUnblockThrottles) does during
that is simple, and could be raised into MaybeUnblockThrottles() and made a
local variable.  However, UnblockThrottle() always calls
ThrottleImpl::NotifyUnblocked(), which does an upcall, and may or may not result
in reentrant calls into NetworkThrottleManagerImpl, which may or may not result
in changes to num_effective_outstanding_.  So if I do this change I think I need
to call RecomputeOutstanding on every loop in MaybeUnblockThrottles, as opposed
to just at the beginning, which I don't think is worth it to save a class
variable.  Do you see a way around that?

ETA: Ok, I'm now more torn.  When a throttle is unblocked, it might be a good
idea to reset the timer (which is done in RecomputeOustanding()) since if that
transition goes from 0->1 active requests, we need to set the timer.  If there
was already an active request, the timer is likely to be already set (since with
this PS we're tracking the start time (== first unblocked time) of a throttle,
not the creation time) of the throttle.  But testing if there are active
requests seems a bit baroque and implementation dependent, so maybe I really
should just call RecomputeOustanding() each time through the loop, in which case
I could get rid of the object data member.  Any opinions as to the right path
forward?

+      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()) {

[mmenke, 2016/07/11 17:17:20]

I'd suggest making a method:

UnblockThrottle(ThrottleImpl*).

[Randy Smith (Not in Mondays), 2016/08/29 19:44:52]

Done, though I'm not convinced it's a win because the routine needs to be a bit
more abstract than the functionality actually required (handle arbitrary
priorities and locations in the list as opposed to always the front() of the
THROTTLED list).

+    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