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..0985084be8ebd73cb9a3aa6e11f0813f7d468126
--- /dev/null
+++ b/net/base/network_throttle_manager_impl.cc
@@ -0,0 +1,234 @@
+// 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_clock.h"
+
+namespace net {
+
+const size_t NetworkThrottleManagerImpl::kActiveRequestThrottlingLimit = 2;

[Charlie Harrison, 2016/07/07 20:17:26]

Please document these constants. They frighten me.

[Randy Smith (Not in Mondays), 2016/07/08 20:54:23]

What could possibly be frightening about a couple of unassuming, mild-mannered
constants???  :-}

Completely reasonable request.   Done; please let me know what you think of the
comments.

+const double NetworkThrottleManagerImpl::kMedianEstimatorLearningParameter = 1;
+const int NetworkThrottleManagerImpl::kInitialMedianInMS = 100;
+const int NetworkThrottleManagerImpl::kMedianLifetimeMultiple = 5;
+
+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->clock_->Now()),
+      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_(true, false),

[Charlie Harrison, 2016/07/07 20:17:26]

Do you mind saying:
outstanding_recomputation_timer_(true /* retain_user_task */, false /*
is_repeating */)?

Very few people reading the code will know the constructor to base::Timer :)

[Randy Smith (Not in Mondays), 2016/07/08 20:54:23]

Done.

+      clock_(new base::DefaultClock()) {

[Charlie Harrison, 2016/07/07 20:17:25]

This clock uses wall time. Shouldn't you use monotonic time instead (timeticks)?

[Randy Smith (Not in Mondays), 2016/07/08 20:54:24]

Good catch.  Done.

+  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_;
+
+  RecomputeOutstanding();
+  // Can only have increased the outstanding count (decreases due to

[Charlie Harrison, 2016/07/07 20:17:26]

nit: You can fit more words on this comment line.

[Randy Smith (Not in Mondays), 2016/07/08 20:54:23]

Done but if git format changes it back I'm not going to notice (or care, really
:-}).

[Charlie Harrison, 2016/07/08 22:36:05]

The problem with git cl format is that it happily breaks lines that are too
long, but it won't merge lines that are too short. This always gets me.

+  // aging out would be caught by timer) so a MaybeUnthrottle() isn't needed.

[Charlie Harrison, 2016/07/07 20:17:26]

s/MaybeUnthrottle/MaybeUnblock/

[Randy Smith (Not in Mondays), 2016/07/08 20:54:23]

Ooops.  Query replace failure.  Done.

+
+  return std::move(throttle);
+}
+
+void NetworkThrottleManagerImpl::SetClockForTesting(
+    std::unique_ptr<base::Clock> clock) {
+  clock_ = std::move(clock);
+}
+
+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)

[Charlie Harrison, 2016/07/07 20:17:26]

Can you either:
1. DCHECK in the throttle impl that the priority is really changing.
2. Don't swap lists if the priority isn't really changing.

[Randy Smith (Not in Mondays), 2016/07/08 20:54:24]

So possibly the fact that you and Matt have called out this issue separately on
separate reviews should make me rethink my position, but so far I'm going with
being stubborn :-}.  The issue is, what behavior do we *want* if
URLRequest::SetPriority() is called to change the priority to the same priority
whatever it currently is?  The (implicit) contract for SetPriority() currently
is "change priority and put the request at the end of the queue for the new
priority" (in terms of determining which requests will be dequeued first if they
are blocked).  If you accept that contract, I'd argue that a
SetPriority(current_priority) *should* have the result of moving the request to
the end of the queue.

Now, at the moment (given the implementation of NetworkThrottleManagerImpl) it's
a moot point, since the only time this is relevant is when transitioning a
request/throttle THROTTLED->THROTTLED (THROTTLED-> anywhere else unblocks, and
anywhere else->THROTTLED comes in unblocked and stays that way).  And arguably
if a client is doing an N->N transition they don't know what they're doing and
we should tell them that.  But I could imagine situations in which they really
want the "put this at the end of the queue" behavior, and failing other
concerns, I'd like to expose that.

But feel free to come back and tell me I'm crazy--as I say, I'm standing alone
on this one ATM.

[Charlie Harrison, 2016/07/08 22:36:05]

You raise a good point, but I think my mind has not changed. If consumers want
an API to "requeue in current priority bucket" it feels reasonable to expose a
"Requeue()" method on the Throttle. This feels like a fringe feature so it makes
sense to expose it only when necessary.

In my view, the current semantics will more often than not lead to mistakes and
unintended consequences by consumers who  accidentally reprioritize to the same
priority.

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

Ok, I yield.  Done (no-op if priority is the same, documented in the header for
Throttle).

+      ->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));
+
+  // |MaybeUnblock()|, below, only checks the THROTTLED priority; if |throttle|

[Charlie Harrison, 2016/07/07 20:17:26]

nit: Remove the commas and replace the semicolon with a period. Also, the second
sentence is a bit unclear. By this point you've already unblocked the throttle.
I would say "If |throttle| was moved from the THROTTLED list above then it needs
to be notified that it has been unblocked".

[Randy Smith (Not in Mondays), 2016/07/08 20:54:23]

Done.
Not as I read the code.  Specifically, throttle->IsBlocked() is still true (see
conditional leading in); NotifyUnblocked() changes that and does the upcall. 
It's been moved off the blocked *list* but not actually unblocked.  Given that,
do you still want a rephrase?

+  // was transitioned away from that priority 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();
+  }
+
+  MaybeUnblock();

[Charlie Harrison, 2016/07/07 20:17:26]

I don't really like this method name but I can't come up with alternatives :)

I think I want something like "RecomputeBlockedThrottledThrottles", but that's
horrible.

[Randy Smith (Not in Mondays), 2016/07/08 20:54:23]

Horrible enough to be funny, at least :-}.

I think changing to MaybeUnblockThrottles() aids understanding without going
crazy, so I've done that; let me know if you think it's useless or harmful
verbiage.  (I'm somewhat going with keeping the method names a level of
abstraction above the implementations; i.e. at some point in the future we might
be unblocking other priority levels, so I don't think that mentioned the
THROTTLED priority level makes sense.)

+}
+
+void NetworkThrottleManagerImpl::OnThrottleDestroyed(ThrottleImpl* throttle) {
+  // Adjust median estimate.  Algorithm from
+  // http://stackoverflow.com/questions/1309263/rolling-median-algorithm-in-c

[Charlie Harrison, 2016/07/07 20:17:26]

Better link: this paper has the algorithm and explanation (Algorithm 1):
http://arxiv.org/pdf/1407.1121v1.pdf

Estimating any quartile just requires one more bit to be persisted if you want
to do that. This way you don't have to do a constant * median_estimate. You can
just estimate the rolling 95th percentile, etc.

Also: can you split the computation into two steps, and note how you landed on
kMedianEstimatorLearningParameter to be 1?

[Randy Smith (Not in Mondays), 2016/07/08 20:54:23]

Wow.  Nice reference.  I think estimating the rolling 95th percentile is a good
way to go, though I'm concerned about having to use randomization functions,
just because they're often trickier than expected.  And this would definitely
require pulling the estimation algorithm out into its own class.  Hmmph.  I'll
probably do it, but in this comment I'm just going to replace the reference
pointer and split the computation.
You mean which ear I pulled it out of?  :-} :-|.  I've added a note about that
at the comment for that constant.

+  lifetime_median_estimate_ += base::TimeDelta::FromMilliseconds(
+      kMedianEstimatorLearningParameter *
+      (clock_->Now() - throttle->creation_time() > lifetime_median_estimate_
+           ? 1
+           : -1));
+
+  if (lifetime_median_estimate_ < base::TimeDelta::FromMilliseconds(1))
+    lifetime_median_estimate_ = base::TimeDelta::FromMilliseconds(1);
+
+  ListForThrottle(throttle)->erase(throttle->queue_pointer());
+  creation_ordering_set_.erase(throttle);

[Charlie Harrison, 2016/07/07 20:17:26]

Can you DCHECK(creation_ordering_set_.erase(throttle))?

[Randy Smith (Not in Mondays), 2016/07/08 20:54:23]

Yes, conceptually, but I don't want the erase inside the DCHECK in case the
compiler just elides DCHECKs; the erase needs to happen in production code too. 
Done.

+  if (throttle->IsBlocked())
+    --num_throttles_blocked_;
+  RecomputeOutstanding();
+
+  // TODO(rdsmith): Via PostTask so there aren't upcalls from within
+  // destructors?
+  MaybeUnblock();
+}
+
+void NetworkThrottleManagerImpl::RecomputeOutstanding() {
+  num_effective_outstanding_ =
+      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::Time age_horizon(clock_->Now() -
+                         kMedianLifetimeMultiple * lifetime_median_estimate_);
+  for (auto it = creation_ordering_set_.begin();

[Charlie Harrison, 2016/07/07 20:17:26]

Can you just use a range for loop here?

[Randy Smith (Not in Mondays), 2016/07/08 20:54:24]

Fair point; done.

+       it != creation_ordering_set_.end(); ++it) {
+    if ((*it)->creation_time() > age_horizon) {
+      // The earliest we might need to recompute the outstanding count
+      // is the amount of time it will take the current element to age
+      // out of the effective set.
+      outstanding_recomputation_timer_.Start(
+          FROM_HERE, (*it)->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::RecomputeOutstanding,

[Charlie Harrison, 2016/07/07 20:17:25]

Don't we need to recompute outstanding AND maybe unblock when the timer fires?
I'm not sure how things progress if we have a bunch of hanging gets and
MaybeUnblock only happens for reprioritization and throttle destruction.

[Randy Smith (Not in Mondays), 2016/07/08 20:54:24]

Good catch.  This requires a test case, which I'm afraid I'm solving by adding a
new "ForTesting()" method so that we can effectively "fast forward" timer calls.
 So another break in the abstraction barrier you may want to review.  

Done.

+                     base::Unretained(this)));
+      break;
+    }
+
+    // Only unblocked throttles are considered outstanding, so only those
+    // throttles need to be subtracted out due to aging.
+    if (!(*it)->IsBlocked())
+      --num_effective_outstanding_;
+  }
+}
+
+void NetworkThrottleManagerImpl::MaybeUnblock() {
+  while (num_effective_outstanding_ < kActiveRequestThrottlingLimit &&
+         !blocked_requests_[THROTTLED].empty()) {
+    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