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..430fa3560b914f84afc6ddb2532fccdd7e9abea1
--- /dev/null
+++ b/net/base/network_throttle_manager_impl.cc
@@ -0,0 +1,337 @@
+// 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;

[mmenke, 2016/10/07 16:51:47]

kTimerSlopMs?  kTimerBonus[Epsilon/Delta]Ms?  Want a name indicating this is a
bit of a fudge factor.

[Charlie Harrison, 2016/10/11 14:50:51]

Hm...2ms is very small for CPUs with bad clocks. If
base::TimeTicks::IsHighResolution returns false our clock resolution could be
~15ms.

It isn't a huge deal but it probably warrants a comment because this is a red
flag for me.

[mmenke, 2016/10/11 14:54:05]

I think it's worth noting correctness of this class no longer depends on timing
being perfect, so at worst, we'll post an extra task or two.

[Randy Smith (Not in Mondays), 2016/10/11 21:43:34]

I decided to change it anyway because of the fear image that posting a task with
a delay less than the resolution of the timer clock could result in the task
running instantly, putting us into an infinite loop situation until the time
actually expires.

[Randy Smith (Not in Mondays), 2016/10/11 21:43:34]

Changed to 17 and commented on why, along with a comment along Matt's lines
below about accuracy not being necessary for correctness. 

[Randy Smith (Not in Mondays), 2016/10/11 21:43:35]

kTimerFudgeInMs.

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

[Charlie Harrison, 2016/10/11 14:50:52]

Can this be an enum class?

[Randy Smith (Not in Mondays), 2016/10/11 21:43:35]

Sure :-}.

+    // 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 BlockedQueuePointer =
+      NetworkThrottleManagerImpl::ThrottleList::iterator;
+
+  // Caller must arrange that |*delegate| and |*manager| outlive
+  // the ThrottleImpl class.
+  ThrottleImpl(bool blocked,
+               RequestPriority priority,
+               ThrottleDelegate* delegate,
+               NetworkThrottleManagerImpl* manager,
+               BlockedQueuePointer blocked_queue_pointer);
+
+  ~ThrottleImpl() override;
+
+  // Throttle:
+  bool IsBlocked() const override;
+  RequestPriority Priority() const override;

[mmenke, 2016/10/07 16:51:47]

Having both Priority() and priority() seems silly.  If you want potential inline
/ non-virtual perf benefits, I think you can just make this one final, and get
rid of the other?

Or could remove the virtual one.  I think it's only used in tests?

[Randy Smith (Not in Mondays), 2016/10/11 21:43:35]

That's totally a typo; thanks for noticing.  Removed the lower case one.

+  void SetPriority(RequestPriority priority) override;
+
+  State state() const { return state_; }
+
+  RequestPriority priority() const { return priority_; }
+
+  BlockedQueuePointer blocked_queue_pointer() const {
+    return blocked_queue_pointer_;
+  }
+  void set_blocked_queue_pointer(const BlockedQueuePointer& pointer) {
+    blocked_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

[Charlie Harrison, 2016/10/11 14:50:52]

nit: reflow comment.

[Randy Smith (Not in Mondays), 2016/10/11 21:43:34]

Done.

+  // 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_;
+
+  // To allow deletion from the blocked queue (when the throttle is

[Charlie Harrison, 2016/10/11 14:50:51]

nit: reflow comment.

[Randy Smith (Not in Mondays), 2016/10/11 21:43:34]

Done.

+  // in the blocked queue).
+  BlockedQueuePointer blocked_queue_pointer_;
+
+  DISALLOW_COPY_AND_ASSIGN(ThrottleImpl);
+};
+
+NetworkThrottleManagerImpl::ThrottleImpl::ThrottleImpl(
+    bool blocked,
+    RequestPriority priority,
+    NetworkThrottleManager::ThrottleDelegate* delegate,
+    NetworkThrottleManagerImpl* manager,
+    BlockedQueuePointer blocked_queue_pointer)
+    : state_(blocked ? BLOCKED : OUTSTANDING),
+      priority_(priority),
+      delegate_(delegate),
+      manager_(manager),
+      blocked_queue_pointer_(blocked_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

[Charlie Harrison, 2016/10/11 14:50:51]

nit: reflow comment.

[Randy Smith (Not in Mondays), 2016/10/11 21:43:35]

You pick the nit of reflowing the comment, and don't call me out on the improper
plural??  :-}  Done (both).

Note that if "git cl format" puts the comments back, I won't notice, and I won't
change them back if you ask me :-}.

+  // current state is blocked.
+  DCHECK_EQ(BLOCKED, state_);
+  state_ = OUTSTANDING;
+  delegate_->OnThrottleUnblocked(this);
+}
+
+NetworkThrottleManagerImpl::NetworkThrottleManagerImpl()
+    : lifetime_median_estimate_(PercentileEstimator::kMedianPercentile,
+                                kInitialMedianInMs),
+      outstanding_recomputation_timer_(false /* retain_user_task */,
+                                       false /* is_repeating */),
+      outstanding_throttles_(&NetworkThrottleManagerImpl::StartTimeSetCompare),
+      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()));

[mmenke, 2016/10/07 16:51:47]

I don't think we need the last parameter here - can just use the default
constructor.

[Randy Smith (Not in Mondays), 2016/10/11 21:43:34]

I'd rather not.  The problem here is that default construction constructs it to
an undefined value; the comparisons on the web are to declaring |int* x;|. 
That's ok if there are no problems with the code, but it means if we want to
assert that it has (or hasn't) had something assigned to it, we don't have a way
to do that.  And we do have such an assertion later on in the code.  So I'd like
to keep this initialized to a defined, known invalid, value.  But I'll yield if
you ask again (and yank the relevant DCHECK).

[mmenke, 2016/10/11 21:48:28]

Setting something to blah.end() seems really weird to me.  Is there something
less weird we can agree on?

[Randy Smith (Not in Mondays), 2016/10/11 22:04:17]

I'm happy to change it to pretty much anything you want--I agree that blah.end()
is weird.  My line is just that, based on the doc I've seen on the net, I'm not
willing to assume that two default constructed iterator objects will compare
equivalent to each other, so I'm not comfortable keeping the current DCHECK
functionality using default constructed objects.  But if you feel like the
weirdness of the idiom (sic :-}) outweighs the value of the DCHECK, I'm happy to
nuke it.

+
+  if (blocked) {
+    throttle->set_blocked_queue_pointer(
+        blocked_throttles_.insert(blocked_throttles_.end(), throttle.get()));
+  } else {
+    outstanding_throttles_.insert(throttle.get());
+    // Setup timer if outstanding_throttles_ was empty.

[mmenke, 2016/10/07 16:51:47]

"Set up"  (Setup is a noun)

[Randy Smith (Not in Mondays), 2016/10/11 21:43:35]

Done.

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

[mmenke, 2016/10/07 16:51:47]

IsRunning()

[Randy Smith (Not in Mondays), 2016/10/11 21:43:35]

Huh.  Not sure how I missed that.  Done (here and at other use of is_null()).

+      (tick_clock_->NowTicks() >
+       outstanding_recomputation_timer_.desired_run_time())) {

[mmenke, 2016/10/07 16:51:47]

optional:  Should the second condition be a DCHECK instead?  Seems like tests
shouldn't be running this if it isn't yet time?  Could optionally replace the
first condition with another testing method, if you wanted.

[Randy Smith (Not in Mondays), 2016/10/11 21:43:34]

I'd argue against.  When the timer was set for is a choice of the code under
test, and this method, despite being part of the class, is testing code.  It
shouldn't make assumptions about the correctness of when code under test set the
timer for.  

Instead, I changed this method to return a boolean as to whether the timer was
triggered or not, and included that boolean in test expectations; let me know if
that addresses your thoughts/concerns.

[mmenke, 2016/10/11 21:48:28]

That works for me.

+    base::Closure timer_callback(outstanding_recomputation_timer_.user_task());
+    outstanding_recomputation_timer_.Stop();
+    timer_callback.Run();

[mmenke, 2016/10/07 16:51:47]

Think early exit is generally preferred in this sort of situation (Method
expected to do absolutely nothing, if preconditions aren't met)

[Randy Smith (Not in Mondays), 2016/10/11 21:43:34]

Good point.  Done.

+  }
+}
+
+// static
+bool NetworkThrottleManagerImpl::StartTimeSetCompare(ThrottleImpl* throttle1,
+                                                     ThrottleImpl* throttle2) {
+  // No throttle should be in the StartTimeOrderedSet with a null start

[Charlie Harrison, 2016/10/11 14:50:51]

nit: I think this comment can all fit on one line.

[Randy Smith (Not in Mondays), 2016/10/11 21:43:35]

Done.

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

[Charlie Harrison, 2016/10/11 14:50:51]

Optional: This comment is a bit redundant with the above one. Maybe merge them?

[Randy Smith (Not in Mondays), 2016/10/11 21:43:35]

Done, though it didn't save any space to keep all the information I wanted to
keep.  (Not an argument, a signal to you that if you care you might want to look
at the result.)

+      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->blocked_queue_pointer() != blocked_throttles_.end());
+      DCHECK(std::find(blocked_throttles_.begin(), blocked_throttles_.end(),
+                       throttle) != blocked_throttles_.end());

[mmenke, 2016/10/07 16:51:47]

Replace the second "!= blocked_throttles_.end()" with "==
throttle->blocked_queue_pointer()"?  It's a more precise condition.

[Charlie Harrison, 2016/10/11 14:50:51]

Related, how does DCHECK_EQ work with iterators?

[Randy Smith (Not in Mondays), 2016/10/11 21:43:34]

It doesn't.  My rule of thumb is that if it doesn't make sense to pass to
LOG(ERROR) <<, it probably won't work with DCHECK_<op> (for pretty much the same
reason).

[Randy Smith (Not in Mondays), 2016/10/11 21:43:34]

Done.

+      blocked_throttles_.erase(throttle->blocked_queue_pointer());
+      break;
+    case ThrottleImpl::OUTSTANDING: {
+      size_t items_erased = outstanding_throttles_.erase(throttle);
+      DCHECK_EQ(1u, items_erased);
+    }
+    // Fall through
+    case ThrottleImpl::AGED:
+      DCHECK(!throttle->start_time().is_null());
+      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());

[mmenke, 2016/10/07 16:51:47]

I assume these can't use DCHECK_NE?  Can never remember what weird cases it
supports, and what ones it does not.

[Charlie Harrison, 2016/10/11 14:50:52]

Do you mean DCHECK_EQ?

[Randy Smith (Not in Mondays), 2016/10/11 21:43:34]

There are a whole lot of related DCHECK_XX: DCHECK_EQ, DCHECK_NE, DCHECK_LT,
DCHECK_GT, DCHECK_GE, DCHECK_LE.  I abbreviate the whole set as DCHECK_<op>().

[Randy Smith (Not in Mondays), 2016/10/11 21:43:35]

Nope.  I believe (my rule of thumb?) is that if you can pass something to
LOG(ERROR) <<, you can have it as an individual argument for DCHECK_<op>().  Not
clear how to print an iterator.

+
+  // Unblock the throttles if there's some chance there's a throttle to
+  // unblock.
+  if (outstanding_throttles_.size() < kActiveRequestThrottlingLimit &&
+      !blocked_throttles_.empty()) {
+    // 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() + age_horizon >= now)
+      break;
+
+    outstanding_throttles_.erase(throttle);
+    throttle->SetAged();
+  }
+
+  if (outstanding_throttles_.empty())
+    return;
+
+  // Start the timer if it's not started and there are outstanding throttles
+  // that might need to age out.  If there are blocked throttles that might
+  // need to be unblocked, that will have been taken care of by a previously
+  // queued timer.
+  if (outstanding_recomputation_timer_.user_task().is_null()) {

[mmenke, 2016/10/07 16:51:47]

outstanding_recomputation_timer_.IsRunning()?

[mmenke, 2016/10/07 16:51:47]

optional:  Maybe switch to early return?  Think this case is a bit ambiguous
which should be preferred.

[Randy Smith (Not in Mondays), 2016/10/11 21:43:34]

Done.

[Randy Smith (Not in Mondays), 2016/10/11 21:43:35]

Done.

+    ThrottleImpl* first_throttle(*outstanding_throttles_.begin());
+    DCHECK_GE(first_throttle->start_time() + age_horizon, now);
+    outstanding_recomputation_timer_.Start(
+        FROM_HERE, ((first_throttle->start_time() + age_horizon) - now +
+                    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->blocked_queue_pointer());
+  throttle->set_blocked_queue_pointer(blocked_throttles_.end());

[mmenke, 2016/10/07 16:51:47]

blocked_throttles_.end() ->
NetworkThrottleManagerImpl::ThrottleList::iterator()?  I think setting things to
"blocked_throttles_.end()" doesn't say "Arr!  This thar iterator now be NULL!"
as clearly.

[Randy Smith (Not in Mondays), 2016/10/11 21:43:35]

As noted above, I haven't been able to convince myself that the default
constructor for an iterator sets to a value which can be compared against.  I'm
specifically looking at 

http://stackoverflow.com/questions/3395180/what-is-an-iterators-default-value

and the chain of links starting at 

http://www.cplusplus.com/reference/iterator/BidirectionalIterator/

If I was convinced that the default construction would produce a unique value,
I'd completely agree with this change (and the implied other changes).

+  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