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 <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;
+const int NetworkThrottleManagerImpl::kInitialMedianInMs = 100;
+
+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;
+
+  // Change the throttle's state to AGED.  The previous
+  // state must be OUTSTANDING.
+  void SetAged();
+  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;
+  }
+  base::TimeTicks start_time() const { return start_time_; }
+  void set_start_time(base::TimeTicks start_time) { start_time_ = start_time; }

[Charlie Harrison, 2016/09/19 16:35:35]

Could this logic be moved to NotifyUnblocked so we don't need to expose this
setter?

[Randy Smith (Not in Mondays), 2016/09/22 21:52:26]

So I like this idea in terms of layering (the ThrottleImpl is responsible for
setting the start_time_ on Unblocked construction, shouldn't it be when the
state transition occurs?) but the start time needs to be set before insertion in
the outstanding_throttles_ set (because that set is ordered by start time) and
the throttle needs to be inserted in that set before NotifyUnblocked() is called
(because that does an upcall, which could do *anything*, and our data needs to
be in a finite state before that point).  So I left this the way it is.  Let me
know if you see another option.

+
+  // 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.
+  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);
+}
+
+NetworkThrottleManagerImpl::NetworkThrottleManagerImpl()
+    : lifetime_median_estimate_(QuantileEstimator::kMedianQuantile,
+                                kInitialMedianInMs),
+      outstanding_recomputation_timer_(false /* retain_user_task */,
+                                       false /* is_repeating */),
+      outstanding_throttles_(
+          &NetworkThrottleManagerImpl::CreationTimeSetCompare),
+      tick_clock_(new base::DefaultTickClock()),
+      weak_ptr_factory_(this) {
+  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 &&
+       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();
+
+  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();
+  }
+}
+

[Charlie Harrison, 2016/09/19 16:35:36]

nit: // static

[Randy Smith (Not in Mondays), 2016/09/22 21:52:27]

Done.

+bool NetworkThrottleManagerImpl::CreationTimeSetCompare(
+    ThrottleImpl* throttle1,
+    ThrottleImpl* throttle2) {
+  // No throttle should be in the CreationTimeOrderedSet 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() && old_priority == THROTTLED &&

[Charlie Harrison, 2016/09/19 16:35:36]

Doesn't throttle->IsBlocked() imply old_priority == THROTTLED?

[Randy Smith (Not in Mondays), 2016/09/22 21:52:26]

Yes, though it probably won't be true in the next CL.  Having said that, I've
already committed to only doing the code that I need for this CL.  Replaced with
a comment. 

+      new_priority != THROTTLED) {
+    // May result in re-entrant calls into this class.
+    UnblockThrottle(throttle);
+  }
+  RecomputeOutstanding();
+}
+
+void NetworkThrottleManagerImpl::OnThrottleDestroyed(ThrottleImpl* throttle) {
+  switch (throttle->state()) {
+    case ThrottleImpl::BLOCKED:
+      DCHECK(throttle->queue_pointer() != blocked_throttles_.end());
+      blocked_throttles_.erase(throttle->queue_pointer());
+      break;
+    case ThrottleImpl::OUTSTANDING: {

[Charlie Harrison, 2016/09/19 16:35:36]

Why do you wrap this case in {} but not the others?

[Randy Smith (Not in Mondays), 2016/09/22 21:52:26]

I needed the scope of items_erased to be restricted to this case, so that I
didn't get warnings about bypassing variable initialization when the AGED case
is used.

+      size_t items_erased = outstanding_throttles_.erase(throttle);
+      DCHECK_EQ(1u, items_erased);
+    }
+    // Fall through
+    case ThrottleImpl::AGED:
+      DCHECK_NE(throttle->start_time(), base::TimeTicks());
+      lifetime_median_estimate_.AddSample(
+          (tick_clock_->NowTicks() - throttle->start_time())
+              .InMillisecondsRoundedUp());

[mmenke, 2016/09/19 15:26:16]

This includes cancellations and failures, as long as they happen after a request
is started.  Maybe not worth worrying about?

[Randy Smith (Not in Mondays), 2016/09/22 21:52:26]

I'm inclined not to worry about it.  My thought is that our request failure rate
is O(10%) on bad networks, which will end up pulling down the median somewhat,
but I don't think substantially, and an overestimate of the number of hanging
gets won't hurt us badly (it'll let a few more THROTTLED requests through than
we normally would).  And plumbing to avoid cancellations and failures would be a
PITA.  Let me know if you have a different perspective or see gotchas I've
missed.

+      break;
+  }
+
+  // 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()));
+}
+
+void NetworkThrottleManagerImpl::RecomputeOutstanding() {
+  if (outstanding_throttles_.empty())
+    // No changes needed.

[mmenke, 2016/09/19 15:26:16]

nit:  Use braces or move comment before the if.

[Randy Smith (Not in Mondays), 2016/09/22 21:52:27]

Looking at this in light of your comment, I think my code is wrong. 
Specifically, RecomputeOutstanding should be making minimal assumptions about
the reason it's called, and if it's called because of a throttle destruction, it
may need to nuke the timer.  And when I look at that, that's handled by the just
falling through to the next two chunks of code.  So I just removed this entire
conditional (which may mean an extra call to NowTicks() in some circumstances).

+    return;
+
+  // Remove all throttles that have aged out of the outstanding set.
+  base::TimeTicks age_horizon(
+      tick_clock_->NowTicks() -
+      base::TimeDelta::FromMilliseconds(
+          (kMedianLifetimeMultiple *
+           lifetime_median_estimate_.current_estimate())));
+  while (!outstanding_throttles_.empty()) {

[mmenke, 2016/09/19 15:26:16]

Where's this declared?  Am I missing something obvious?

[Randy Smith (Not in Mondays), 2016/09/22 21:52:26]

I think so?  It's a data member in the class declaration in
network_throttle_manager_impl.h.  Remember I completely rejiggered the class
state for this PS.

[mmenke, 2016/09/22 21:57:39]

Weird, I searched the header for it multiple times with Ctrl-F, and could not
find it.  Now I can.  Hrm...

+    ThrottleImpl* throttle = *outstanding_throttles_.begin();
+    if (throttle->start_time() > age_horizon)
+      break;
+
+    outstanding_throttles_.erase(throttle);
+    throttle->SetAged();
+  }
+
+  // If the set's now empty, we don't need a timer.

[mmenke, 2016/09/19 15:26:16]

nit:  --we

[Randy Smith (Not in Mondays), 2016/09/22 21:52:26]

Ooops.  Done.

+  if (outstanding_throttles_.empty()) {

[mmenke, 2016/09/19 15:26:17]

This seems too fragile to me - if we marked all outstanding throttles as aged,
and still have any blocked throttles, we're in trouble.

Let's consider where this is called from
1) If we're called from MaybeUnblockThrottle, we're about to check blocked
throttles, this should be fine.
2) If we're called from CreateThrottle, and max_age isn't really tiny, and the
thread isn't hung for a long time, this should hopefully be fine.
3) If we're called from RecomputeOutstanding, I really have no idea.

So..erm, in summary, could we maybe check if num_throttles_blocked_ is 0 as
well?

[Randy Smith (Not in Mondays), 2016/09/22 21:52:26]

So I think of this in terms of routine responsibilities.  This routine is
responsible for recomputing the outstanding throttle state and managing the
timer around that state; "whatever calls it" is responsible for unblocking
throttles if that's necessary.  Following that logic and your comment, I decided
that CreateThrottle() and OnThrottlePriorityChanged() (which I think is what you
meant by "called from RecomputeOustanding()") really should be calling
MaybeUnblockThrottles().  So I made that change, and put in a comment explaining
it.  

I debated pulling the code from RecomputeOustanding() up into
MaybeUnblockThrottles() (since now MUT is now the only caller) but decided
against since I think what the two routines do is different enough that the code
is easier to understand with two functions.  Other perspectives welcome.

(Summary: Thank you for pointing out a bug, and I think I've fixed it, but
totally not in the way you suggested :-}.)

+    outstanding_recomputation_timer_.Stop();
+    return;
+  }
+
+  // The earliest we'll need to recompute is when the earliest timer

[mmenke, 2016/09/19 15:26:16]

--we

[Randy Smith (Not in Mondays), 2016/09/22 21:52:26]

Done.

+  // ages out of the set.  This isn't precise because the median estimate
+  // changes over time, but this is a heuristic and doesn't need to be
+  // precise.
+  // TODO(rdsmith): Under that same "not precise" rubric, worthwhile avoiding
+  // resetting the timer if it's "close"?
+  ThrottleImpl* first_throttle = *outstanding_throttles_.begin();
+  base::TimeTicks new_timer_start =
+      base::TimeTicks::Now() + (first_throttle->start_time() - age_horizon);

[Charlie Harrison, 2016/09/19 16:35:35]

Why not use tick_clock_->NowTicks() here?

[Randy Smith (Not in Mondays), 2016/09/22 21:52:26]

So the basic answer is "We could, but it won't help" :-}.  The problem is that
the base::Timer class uses the system clock, and there's nothing we can do about
it.  So any test (which is what tick_clock_ is for) that is trying to test what
the timer does is going to fail.   I've added a comment about that to the test.

ETA: Though I've just noticed that we call tick_clock_->NowTicks() at the
beginning of this routine, which is probably what you meant, and is bogus. 
Fixed.

+  if (!outstanding_recomputation_timer_.user_task().is_null() &&
+      outstanding_recomputation_timer_.desired_run_time() == new_timer_start) {

[Charlie Harrison, 2016/09/19 16:35:35]

When will these be equal? Seeing as you just called base::TimeTicks::Now() to
initialize new_timer_start this seems like it will be extremely rare.

[Randy Smith (Not in Mondays), 2016/09/22 21:52:26]

Consider the case where we call RecomputeOustanding twice in a row, with some D
ticks in between but no change in the median estimate.  In the first call:
 
age_horizon = T1  - 5 * MedianEstimate
TimerTrigger = T1 + (ThrottleStart - (T1 - 5 * MedianEstimate) = ThrottleStart +
5 * MedianEstimate

In the second call:

age_horizon = T1 + D - 5 * MedianEstimate
TimerTrigger = T1 + D + (ThrottleStart - (T1 + D - 5 * MedianEstimate) =
ThrottleStart + 5 * MedianEstimate

I.e. they should be equal.

Now having said that, there are a couple of things I'm not sure about: a) noise
in the system, and b) what kind of slop is worth tolerating about when the timer
goes off in order to avoid resetting the timer.  I elected not to worry about it
too much, but if you want I can put some small ranges in so that we don't reset
timers too often.  

Having said *that* I do think it's worthwhile reducing noise by only calling
TimeTicks::Now() once in this routine, which I've done.

[Charlie Harrison, 2016/09/23 15:11:12]

Calling TimeTicks::Now() gets you halfway, but desired_run_time() is implemented
in Timer and calls TimeTicks::Now() sometime after Start(). I suspect it will be
very rare that the numbers align to perfect equality at the microsecond level.

[Randy Smith (Not in Mondays), 2016/09/23 22:16:49]

Ok, after reading through the code carefully, I agree with you.  Given that, I'm
inclined to nuke this test, and have done so.  

(In reading through that code I also noted that timer won't bother to reschedule
on Start() if there's already a timer call scheduled for an earlier time, which
amuses me but is *a* protection against Matt's concern about the performance
cost of doing too much rescheduling.)

So the basic question here is, how much would it gain us to avoid resetting the
timer when the "effective time" it's triggered for hasn't changed, and is it
worth the plumbing?  It occurs to me that that optimization could be implemented
by caching the timer at the beginning of outstanding_throttles_ and just testing
at this point in the code if it's changed.  I guess I'm inclined in favor; I'm
really not sure how often RecomputeOutstanding()/MaybeUnblockThrottles() will be
called, and I've designed it to be something that can be called casually after
any call that's changes relevant state.   Done.

+    return;
+  }
+
+  outstanding_recomputation_timer_.Start(
+      FROM_HERE, first_throttle->start_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)));
+}
+
+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);
+
+  // 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