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..0cc41cb2a79cb88f8ca761f3dfcafe0843b302dd
--- /dev/null
+++ b/net/base/network_throttle_manager_impl.cc
@@ -0,0 +1,340 @@
+// 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 <algorithm>
+
+#include "base/logging.h"
+#include "base/message_loop/message_loop.h"
+#include "base/time/default_tick_clock.h"
+
+namespace net {
+
+const size_t NetworkThrottleManagerImpl::kActiveRequestThrottlingLimit = 2;
+const int NetworkThrottleManagerImpl::kMedianLifetimeMultiple = 5;
+
+// Initial estimate based on the median in the
+// Net.RequestTime2.Success histogram, excluding cached results by eye.
+const int NetworkThrottleManagerImpl::kInitialMedianInMs = 400;
+
+// Set timers slightly further into the future than they need to be set, so
+// that the algorithm isn't vulnerable to timer round off errors triggering
+// the callback before the throttle would be considered aged out of the set.
+const int kTimerDelayInMs = 2;
+
+class NetworkThrottleManagerImpl::ThrottleImpl
+    : public NetworkThrottleManager::Throttle {
+ public:
+  // Allowed state transitions are BLOCKED -> OUTSTANDING -> AGED.
+  // Throttles may be created in the BLOCKED or OUTSTANDING states.
+  enum State {
+    // Not allowed to proceed by manager.
+    BLOCKED,
+
+    // Allowed to proceed, counts as an "outstanding" request for
+    // manager accounting purposes.
+    OUTSTANDING,
+
+    // Old enough to not count as "outstanding" anymore for
+    // manager accounting purposes.
+    AGED
+  };
+
+  using QueuePointer = NetworkThrottleManagerImpl::ThrottleList::iterator;
+
+  // Caller must arrange that |*delegate| and |*manager| outlive
+  // the ThrottleImpl class.
+  ThrottleImpl(bool blocked,
+               RequestPriority priority,
+               ThrottleDelegate* delegate,
+               NetworkThrottleManagerImpl* manager,
+               QueuePointer queue_pointer);
+
+  ~ThrottleImpl() override;
+
+  // Throttle:
+  bool IsBlocked() const override;
+  RequestPriority Priority() const override;
+  void SetPriority(RequestPriority priority) override;
+
+  State state() const { return state_; }
+
+  RequestPriority priority() const { return priority_; }
+
+  QueuePointer queue_pointer() const { return queue_pointer_; }
+  void set_queue_pointer(const QueuePointer& pointer) {
+    queue_pointer_ = pointer;
+  }
+
+  void set_start_time(base::TimeTicks start_time) { start_time_ = start_time; }
+  base::TimeTicks start_time() const { return start_time_; }
+
+  // Change the throttle's state to AGED.  The previous
+  // state must be OUTSTANDING.
+  void SetAged();
+
+  // Note that this call calls the delegate, and hence
+  // may result in re-entrant calls into the manager or
+  // ThrottleImpl.  The manager should not rely on
+  // any state other than its own existence being persistent
+  // across this call.
+  void NotifyUnblocked();
+
+ private:
+  State state_;
+  RequestPriority priority_;
+  ThrottleDelegate* const delegate_;
+  NetworkThrottleManagerImpl* const manager_;
+
+  base::TimeTicks start_time_;
+
+  // For deletion from owning queue.

[Charlie Harrison, 2016/10/03 20:53:49]

Can you clarify that this is only for tracking where the throttle is when it is
blocked? It is confusing that this is blocked_throttles_.end() when not in the
blocked throttles list.

[Randy Smith (Not in Mondays), 2016/10/06 20:50:24]

That's a really good point.  I've changed names and updated the comment; let me
know what you think.

+  QueuePointer queue_pointer_;
+
+  DISALLOW_COPY_AND_ASSIGN(ThrottleImpl);
+};
+
+NetworkThrottleManagerImpl::ThrottleImpl::ThrottleImpl(
+    bool blocked,
+    RequestPriority priority,
+    NetworkThrottleManager::ThrottleDelegate* delegate,
+    NetworkThrottleManagerImpl* manager,
+    QueuePointer queue_pointer)
+    : state_(blocked ? BLOCKED : OUTSTANDING),
+      priority_(priority),
+      delegate_(delegate),
+      manager_(manager),
+      queue_pointer_(queue_pointer) {
+  DCHECK(delegate);
+  if (!blocked)
+    start_time_ = manager->tick_clock_->NowTicks();
+}
+
+NetworkThrottleManagerImpl::ThrottleImpl::~ThrottleImpl() {
+  manager_->OnThrottleDestroyed(this);
+}
+
+bool NetworkThrottleManagerImpl::ThrottleImpl::IsBlocked() const {
+  return state_ == BLOCKED;
+}
+
+RequestPriority NetworkThrottleManagerImpl::ThrottleImpl::Priority() const {
+  return priority_;
+}
+
+void NetworkThrottleManagerImpl::ThrottleImpl::SetPriority(
+    RequestPriority new_priority) {
+  RequestPriority old_priority(priority_);
+  if (old_priority == new_priority)
+    return;
+  priority_ = new_priority;
+  manager_->OnThrottlePriorityChanged(this, old_priority, new_priority);
+}
+
+void NetworkThrottleManagerImpl::ThrottleImpl::SetAged() {
+  DCHECK_EQ(OUTSTANDING, state_);
+  state_ = AGED;
+}
+
+void NetworkThrottleManagerImpl::ThrottleImpl::NotifyUnblocked() {
+  // This methods should only be called once, and only if the
+  // current state is blocked.
+  DCHECK_EQ(BLOCKED, state_);
+  state_ = OUTSTANDING;
+  delegate_->OnThrottleStateChanged(this);

[Charlie Harrison, 2016/10/03 20:53:48]

This is the only time we notify OnThrottleStateChanged, do you have plans to add
more places we call this? If not, renaming the delegate method to
OnThrottleUnblocked might be clearer.

[Randy Smith (Not in Mondays), 2016/10/06 20:50:24]

Yeah, this gets into the whole question about how much to plan for the future. 
Having said that, the only possible throttle state changes are between blocked
and unblocked, and adding an unblocked->blocked transition will be work well
dwarfing changing the name back.  Done.

+}
+
+NetworkThrottleManagerImpl::NetworkThrottleManagerImpl()
+    : lifetime_median_estimate_(PercentileEstimator::kMedianPercentile,
+                                kInitialMedianInMs),
+      outstanding_recomputation_timer_(false /* retain_user_task */,
+                                       false /* is_repeating */),
+      outstanding_throttles_(&NetworkThrottleManagerImpl::StartTimeSetCompare),
+      first_outstanding_throttle_(nullptr),
+      tick_clock_(new base::DefaultTickClock()),
+      weak_ptr_factory_(this) {
+  outstanding_recomputation_timer_.SetTaskRunner(
+      base::MessageLoop::current()->task_runner());
+}
+
+NetworkThrottleManagerImpl::~NetworkThrottleManagerImpl() {
+  DCHECK(!first_outstanding_throttle_);
+}
+
+std::unique_ptr<NetworkThrottleManager::Throttle>
+NetworkThrottleManagerImpl::CreateThrottle(
+    NetworkThrottleManager::ThrottleDelegate* delegate,
+    RequestPriority priority,
+    bool ignore_limits) {
+  bool blocked =
+      (!ignore_limits && priority == THROTTLED &&
+       outstanding_throttles_.size() >= kActiveRequestThrottlingLimit);
+
+  std::unique_ptr<NetworkThrottleManagerImpl::ThrottleImpl> throttle(
+      new ThrottleImpl(blocked, priority, delegate, this,
+                       blocked_throttles_.end()));
+
+  if (blocked) {
+    throttle->set_queue_pointer(
+        blocked_throttles_.insert(blocked_throttles_.end(), throttle.get()));
+  } else {
+    outstanding_throttles_.insert(throttle.get());
+    RecomputeOutstanding();

[Charlie Harrison, 2016/10/03 20:53:48]

It might be worth a comment to explain why this is needed. I think the only
reason we need it is to jumpstart the timer?

[Randy Smith (Not in Mondays), 2016/10/06 20:50:24]

Meaning when this is the first outstanding throttle? Done.

+  }
+
+  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();
+  }
+}
+
+// static
+bool NetworkThrottleManagerImpl::StartTimeSetCompare(ThrottleImpl* throttle1,
+                                                     ThrottleImpl* throttle2) {
+  // No throttle should be in the StartTimeOrderedSet with a null start
+  // time.
+  DCHECK_NE(throttle1->start_time(), base::TimeTicks());
+  DCHECK_NE(throttle2->start_time(), base::TimeTicks());
+  return (throttle1->start_time() < throttle2->start_time() ||
+          // So different throttles don't look equal to the comparison
+          // function.
+          (throttle1->start_time() == throttle2->start_time() &&
+           throttle1 < throttle2));
+}
+
+void NetworkThrottleManagerImpl::OnThrottlePriorityChanged(
+    NetworkThrottleManagerImpl::ThrottleImpl* throttle,
+    RequestPriority old_priority,
+    RequestPriority new_priority) {
+  // The only case requiring a state change is if the priority change
+  // implies unblocking.
+  if (throttle->IsBlocked() &&  // Implies |old_priority == THROTTLED|
+      new_priority != THROTTLED) {
+    // May result in re-entrant calls into this class.
+    UnblockThrottle(throttle);
+  }
+}
+
+void NetworkThrottleManagerImpl::OnThrottleDestroyed(ThrottleImpl* throttle) {
+  switch (throttle->state()) {
+    case ThrottleImpl::BLOCKED:
+      DCHECK(throttle->queue_pointer() != blocked_throttles_.end());
+      DCHECK(std::find(blocked_throttles_.begin(), blocked_throttles_.end(),
+                       throttle) != blocked_throttles_.end());
+      blocked_throttles_.erase(throttle->queue_pointer());
+      break;
+    case ThrottleImpl::OUTSTANDING: {
+      size_t items_erased = outstanding_throttles_.erase(throttle);
+      if (reinterpret_cast<void*>(throttle) == first_outstanding_throttle_) {
+        first_outstanding_throttle_ =
+            (outstanding_throttles_.empty()
+                 ? nullptr
+                 : reinterpret_cast<void*>(*outstanding_throttles_.begin()));
+      }
+      DCHECK_EQ(1u, items_erased);
+    }
+    // Fall through
+    case ThrottleImpl::AGED:
+      DCHECK_NE(throttle->start_time(), base::TimeTicks());

[Charlie Harrison, 2016/10/03 20:53:48]

nit: DCHECK(!throttle->start_time().is_null()) is a bit clearer.

[Randy Smith (Not in Mondays), 2016/10/06 20:50:24]

Done.

+      lifetime_median_estimate_.AddSample(
+          (tick_clock_->NowTicks() - throttle->start_time())
+              .InMillisecondsRoundedUp());
+      break;
+  }
+
+  DCHECK(std::find(blocked_throttles_.begin(), blocked_throttles_.end(),
+                   throttle) == blocked_throttles_.end());
+  // Can't use std::set::count() as that uses the built in comparison
+  // function, which requires a possible null start time.
+  DCHECK(std::find(outstanding_throttles_.begin(), outstanding_throttles_.end(),
+                   throttle) == outstanding_throttles_.end());
+
+  // Via PostTask so there aren't upcalls from within destructors.
+  base::MessageLoop::current()->task_runner()->PostTask(
+      FROM_HERE, base::Bind(&NetworkThrottleManagerImpl::MaybeUnblockThrottles,
+                            weak_ptr_factory_.GetWeakPtr()));

[mmenke, 2016/10/04 16:31:40]

Should we duplicate the check in MaybeUnblockThrottles() here (And maybe it a
const function?  NeedUnblockThrottle?).  Don't consider it a huge deal, just not
sure how often it will be true/false.

[Randy Smith (Not in Mondays), 2016/10/06 20:50:24]

Done.

+}
+
+void NetworkThrottleManagerImpl::RecomputeOutstanding() {
+  // Remove all throttles that have aged out of the outstanding set.
+  base::TimeTicks now(tick_clock_->NowTicks());
+  base::TimeDelta age_horizon(base::TimeDelta::FromMilliseconds((
+      kMedianLifetimeMultiple * lifetime_median_estimate_.current_estimate())));
+  while (!outstanding_throttles_.empty()) {
+    ThrottleImpl* throttle = *outstanding_throttles_.begin();
+    if (throttle->start_time() > now - age_horizon)

[Charlie Harrison, 2016/10/03 20:53:49]

throttle->start_time() + age_horizon > now

This aligns better with the (start_time() + age_horizon) - now at the bottom of
this method.

[Randy Smith (Not in Mondays), 2016/10/06 20:50:24]

Done.

[Randy Smith (Not in Mondays), 2016/10/06 20:50:24]

Done.

+      break;
+
+    outstanding_throttles_.erase(throttle);
+    throttle->SetAged();
+  }
+
+  // If the set is now empty, no timer is needed.
+  if (outstanding_throttles_.empty()) {
+    first_outstanding_throttle_ = nullptr;
+    outstanding_recomputation_timer_.Stop();

[mmenke, 2016/10/04 16:31:40]

I think stopping the timer is actually incorrect - if the timer's about to
trigger, and we call RecomputeOutstanding() from a location other than
MaybeUnblockThrottles(), and then we age out all the outstanding_throttles_,
we'll still want to call MaybeUnblockThrottles, so it can resume throttles.

Perhaps we should have a test for that.  Create 3 throttles, one blocked, as
usual.  Wait (Without spinning the message loop) until two of the throttles are
aged out.  Then add another throttle, which is also blocked (Or not, suppose it
doesn't really matter).  Then we should have no outstanding throttles, because
of the RecomputeOutstanding() call, but the timer should still be running, and
when you run the message loop, the throttled requests should start.

[Charlie Harrison, 2016/10/04 16:41:44]

It feels like what we really want is the be calling MaybeUnblockThrottles in
those cases then. The only problem with that is the UnblockThrottle case to
bootstrap the timer (where we would get stack overflow).

That could be solved by having UnblockThrottle not call RecomputeOutstanding,
and just call RecomputeOutstanding again after the loop in
MaybeUnblockThrottles, and in OnThrottlePriorityChanged.

[mmenke, 2016/10/04 16:53:58]

I'm more concerned about calling UnblockThrottle with stuff on the stack.  It
means we're relying on the embedder either not doing weird stuff synchronously,
or being called asynchronously, which sounds like a very tenuous contract, with
no enforcement.  Also, embedders just love to do weird stuff.
That's not enough - we need to have CreateThrottle start the timer.  Otherwise,
we'd never start the timer in the first place, so hung throttles are never aged
out.

[Charlie Harrison, 2016/10/04 16:56:44]

Fair point that's a valid concern.
I was thinking that CreateThrottle would call MaybeUnblockThrottles.

[mmenke, 2016/10/04 18:59:47]

Maybe just a method to start the timer if need be (The timer's not running and
there's a blocked throttle?  Could also check if outstanding_throttles_.size() <
kActiveRequestThrottlingLimit, to remove a couple unecessary invocations).  The
use it on throttle creation, and in RecomputeOutstanding.

Could even get fancier and make it figure out if a throttle can currently be
unblocked, and have it set no delay in that case.  If we go with that, would
call it at the end of MaybeUnblockThrottles instead of in RecomputeOutstanding,
and replace the PostTask with it as well.

[Randy Smith (Not in Mondays), 2016/10/06 20:50:24]

Documenting offline conversation: Given the forward march of time, if the timer
is set, this code will never need to make the timer trigger earlier (since the
timer is always age_horizon after oldest existing throttle start, which can only
increase).  So I'll document that RecomputeOustanding() will *only* set the
timer if it's not set, and not do anything else.  This may result in some extra
timer triggers, but there shouldn't be very many.

Matt's suggested test doesn't work because in all cases in which
RecomputeOutstanding() races with a timer invocation of MaybeUnblockThrottles()
the RecomputeOutstanding() is immediately preceded by an insertion into the
outsanding_throttles_ set; i.e. there are no such cases in which
RecomputeOutstanding() might result in a null outstanding_throttles_ set.

+    return;
+  }
+
+  // If the initial throttle hasn't changed, neither has the
+  // right timing for the timer (modulo changes in lifetime_median_estimate_,
+  // which should change slowly enough that we don't need to track it
+  // exactly for a heuristic).
+  ThrottleImpl* first_throttle = *outstanding_throttles_.begin();

[Charlie Harrison, 2016/10/03 20:53:48]

DCHECK that the timer is running?

[Charlie Harrison, 2016/10/04 16:41:44]

nevermind...

[Randy Smith (Not in Mondays), 2016/10/06 20:50:24]

I'm killing first_outstanding_throttle_ anyway.

+  if (first_outstanding_throttle_ == reinterpret_cast<void*>(first_throttle))
+    return;
+  first_outstanding_throttle_ = reinterpret_cast<void*>(first_throttle);
+
+  outstanding_recomputation_timer_.Start(
+      FROM_HERE, ((first_throttle->start_time() + age_horizon) - now +

[Charlie Harrison, 2016/10/03 20:53:49]

Optional: DCHECK that start_time() + age_horizon > now?

[Randy Smith (Not in Mondays), 2016/10/06 20:50:24]

Done.

+                  base::TimeDelta::FromMilliseconds(kTimerDelayInMs)),
+      // 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)));
+}
+
+void NetworkThrottleManagerImpl::UnblockThrottle(ThrottleImpl* throttle) {
+  DCHECK(throttle->IsBlocked());
+
+  blocked_throttles_.erase(throttle->queue_pointer());
+  throttle->set_queue_pointer(blocked_throttles_.end());
+  throttle->set_start_time(tick_clock_->NowTicks());
+  outstanding_throttles_.insert(throttle);
+
+  // Called in case |*throttle| was added to a null set.
+  RecomputeOutstanding();
+
+  // May result in re-entrant calls into this class.
+  throttle->NotifyUnblocked();
+}
+
+void NetworkThrottleManagerImpl::MaybeUnblockThrottles() {
+  RecomputeOutstanding();
+
+  while (outstanding_throttles_.size() < kActiveRequestThrottlingLimit &&
+         !blocked_throttles_.empty()) {
+    // NOTE: This call may result in reentrant calls into
+    // NetworkThrottleManagerImpl; no state should be assumed to be
+    // persistent across this call.
+    UnblockThrottle(blocked_throttles_.front());
+  }
+}
+
+}  // namespace net