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;
+
+// Initial estimate based on the median in the
+// Net.RequestTime2.Success histogram, excluding cached results by eye.
+const int NetworkThrottleManagerImpl::kInitialMedianInMs = 400;
+
+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();

[mmenke, 2016/09/26 17:31:44]

SetAged / NotifyUnblocked should probably be next to each other.  I'd also
suggest a similar naming scheme, though, admittedly, NotifyUnblocked does a lot
more, and is scarier.

[Randy Smith (Not in Mondays), 2016/10/03 01:06:48]

Moved but didn't change naming, for basically the reasons you mention (and
because I couldn't find a shared naming scheme that fit them both well; I guess
I could have gone with Age/Unblock, but that didn't seem quite right).  Let me
know if you want a different name, and if so, what name you think would work
better.

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

[mmenke, 2016/09/26 17:31:43]

Suggest a couple blank lines in this block, non-override methods generally have
blank lines between non-directly related methods. (i.e. blah() / set_blah()
don't have them)

[Randy Smith (Not in Mondays), 2016/10/03 01:06:48]

Done.

+
+  // 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_(PercentileEstimator::kMedianPercentile,
+                                kInitialMedianInMs),
+      outstanding_recomputation_timer_(false /* retain_user_task */,
+                                       false /* is_repeating */),
+      outstanding_throttles_(
+          &NetworkThrottleManagerImpl::CreationTimeSetCompare),
+      first_outstanding_throttle_(nullptr),
+      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());
+  }
+
+  // Throttles may need to be unblocked if the outstanding throttles
+  // that blocked them have aged out of the oustanding set since

[Charlie Harrison, 2016/09/26 22:27:28]

outstanding

[Randy Smith (Not in Mondays), 2016/10/03 01:06:48]

Why thank you!!

(:-}  Done.)

+  // the last entry to MaybeUnblockThrottles().
+  MaybeUnblockThrottles();

[mmenke, 2016/09/26 17:31:43]

Should we be calling RecomputeThrottles instead?  Think we may just need to call
it in the outstanding_throttles_ modified case?  See comment at end of file.

[Randy Smith (Not in Mondays), 2016/10/03 01:06:48]

Agreed.  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::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() &&  // Implies |old_priority == THROTTLED|
+      new_priority != THROTTLED) {
+    // May result in re-entrant calls into this class.
+    UnblockThrottle(throttle);
+  }
+
+  // In case timing has caused throttles to age out.

[mmenke, 2016/09/26 17:31:43]

If a throttle has aged out, I don't think this gets us anything, does it?  We'll
have a timer about to trigger, anyways.  We only need this in the case that
we're unblocking a throttle older than all members of outstanding_throttles_,
right?  And even then, only need to call Recompute, not MaybeUnblock, right? 
Calling MaybeUnblock with other stuff on the stack just seems like a bad idea to
me.

[Randy Smith (Not in Mondays), 2016/10/03 01:06:48]

A throttle doesn't start aging until it's unblocked; we don't treat blocking
time as part of a throttle's age.  So I think you're right, we don't need this
at all.  Removed.

+  MaybeUnblockThrottles();

[mmenke, 2016/09/26 17:31:43]

Also, is there a test that fails if we don't call this method here?  If not, we
should have one.

[Randy Smith (Not in Mondays), 2016/10/03 01:06:48]

That's only necessary if you believe this call actually does something useful,
which you've convinced me it doesn't :-}.  And no, no test failed when I removed
it.

+}
+
+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: {
+      size_t items_erased = outstanding_throttles_.erase(throttle);
+      DCHECK_EQ(1u, items_erased);

[mmenke, 2016/09/26 17:31:43]

Do a similar DCHECK for the blocked case, too?

[Randy Smith (Not in Mondays), 2016/10/03 01:06:48]

Done (std::find(), linear time, but in a DCHECK, so shouldn't matter).

+    }
+    // Fall through
+    case ThrottleImpl::AGED:
+      DCHECK_NE(throttle->start_time(), base::TimeTicks());
+      lifetime_median_estimate_.AddSample(
+          (tick_clock_->NowTicks() - throttle->start_time())
+              .InMillisecondsRoundedUp());
+      break;
+  }
+

[mmenke, 2016/09/26 17:31:43]

Maybe add:

DCHECK_EQ(0u, blocked_throttles_.count(throttle));
DCHECK_EQ(0u, outstanding_throttles_.count(throttle));

[Randy Smith (Not in Mondays), 2016/10/03 01:06:48]

Done, though note that std::list doesn't have a count() operator.

+  // 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() {
+  // 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)
+      break;
+
+    outstanding_throttles_.erase(throttle);
+    throttle->SetAged();
+  }
+
+  // If the set is now empty, no timer is needed.
+  if (outstanding_throttles_.empty()) {
+    outstanding_recomputation_timer_.Stop();
+    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();
+  if (first_outstanding_throttle_ == reinterpret_cast<void*>(first_throttle))
+    return;
+  first_outstanding_throttle_ = reinterpret_cast<void*>(first_throttle);

[mmenke, 2016/09/26 17:31:43]

For correctness, should clear this in OnThrottleDestroyed, if it matches the
doomed throttle.

Can then also DCHECK is nullptr in the destructor.

[Randy Smith (Not in Mondays), 2016/10/03 01:06:48]

Whoops, thank you. 
Done.

+
+  outstanding_recomputation_timer_.Start(
+      FROM_HERE, (first_throttle->start_time() + age_horizon) - now,
+      // 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() {

[mmenke, 2016/09/26 17:31:43]

We're strongly relying on the fact that if we do:

Blah() {
  PostDelayedTask(&Foo, Now() - target_time());
}

Then when Foo executes, Now() is at least target_time() (i.e., no rounding wait
times down, even to the microsecond).  Otherwise, this breaks.  Is that sometime
we can rely on?

A simple fix would be to, in MaybeUnblockThrottles, unconditionally unblock
first_outstanding_throttle_ if it's non-NULL and blocked (Erm...those are
conditions, actually, I mean just ignoring its start_time()).

[Charlie Harrison, 2016/09/26 22:27:28]

No, we can only (barely) rely on monotonicity. We could also for instance make
the age horizon trigger different from the timer (i.e. 5*median vs 4*median) to
ensure we don't hit this corner case.
I'm a bit confused by this, when would first_outstanding_throttle_ be blocked?

[mmenke, 2016/09/26 22:54:43]

Sory, unblock == mark as aged.

[Randy Smith (Not in Mondays), 2016/10/03 01:06:48]

I agree that that's a problem, and I should solve it, but I think it's only
(sic) going to be a performance problem.  The timer may go off a little before
when it should, check the outstanding_throttles_ list, and reset itself for a
very short time period in the future, and just go off again.  

I don't think there are any correctness problems if we just delay the timer by a
bit (we'll have a slightly more imperfect heuristic), so I'll toss in a 2ms
extra delay to make sure the timer triggers after the first throttle really has
aged out.  Does that address the issue you see?

[mmenke, 2016/10/04 15:31:54]

No, it does not.  The timer in RecomputeOutstanding isn't set if
first_outstanding_throttle_ isn't changed.  So it's possible we'll end up with
no timer running, despite having outstanding throttles.  And alternative
approach is to get rid of first_outstanding_throttle_, and only start the timer
when outstanding_recomputation_timer_ is not currently running instead...I think
that works?

[Randy Smith (Not in Mondays), 2016/10/04 15:46:39]

Ah, good point; sorry I missed that.  I'd like to modify your suggestion and an
|outstanding_timer_.IsRunning()| test into the conditional that bails if the
first throttle isn't set.  Is that ok?  (My goal is to make
RecomputeOustanding() correct no matter what state it's called with, so the
issue you raise strikes me as a pure bug.)

I'd rather not get rid of the first_outstanding_throttle_ check, since it's the
primary way I avoid the performance issue you raised earlier in the thread (of
resetting the timer when we don't need to.)

[Randy Smith (Not in Mondays), 2016/10/04 15:56:43]

Result of offline conversation: Matt pointed out to me that anything added to
the outstanding_throttles_ set will have a start time equal to or after the
first item in the set.  So the only way a running timer could be off is it if
went off too early, at which point we'd figure that out and reset properly.  For
that reason, it's safe to ditch the first_outstanding_throttle_ check, and just
not reset the timer if it's already running.  This has good behavior in the
batch case too.  I will do this (not yet done, wanting to summarize results of
conversation quickly).

+  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());
+  }

[mmenke, 2016/09/26 17:31:44]

Think this needs a RecomputeOutstanding() at the end of this method, if there
weren't any blocked throttles before.

May be simplest to just make UnblockThrottle call the method, though then we'd
potentially get some bad behavior if unblocking a bunch at once...Which
shouldn't generally happen, I think?

Better, just make anything that modifies outstanding_throttles_ directly call
that method.

We should have a test that requires this.

[Charlie Harrison, 2016/09/26 22:27:28]

Wont we likely unblock a lot of throttles when Blink decides to open the
floodgates (i.e. <body> tag hit)?

[mmenke, 2016/09/26 22:57:14]

Not as-is.  This code has no clue what a body tag is, and I assume it never
will.  It only has a maximum number of requests with priority == THROTTLED that
can continue at once, so it can only start one at a time.  If we're going to
open the floodgates with this current scheme, I assume it's going to rely on
adjusting priority, which can only be done one request at a time, anyways.

[Randy Smith (Not in Mondays), 2016/10/03 01:06:48]

[The only way I could make the original comment make sense is if I assumed you
meant if we didn't have any *outstanding* throttles before, rather than if we
didn't have any blocked throttles; please let me know if you were saying
something really subtle that I failed to follow.  ]

I've mused on the virtues of making a batch IPC for reprioritization, as the new
scheme will probably need it, but it'd still be done in a loop above the
netstack and so probably wouldn't be an issue here.  And canceling of requests
will result in an immediate PostTask to this function, so it should happen one
at a time there as well.  Having said that, I'm reluctant to rely on that
behavior just for code simplicity.  Having anything that modifies
outstanding_throttles_ directly call that method makes sense.  I'll add the test
and then make the change.

ETA: Done.  This means that RecomputeOutstanding() is now called from places
other than MaybeUnblockThrottles();

+}
+
+}  // namespace net