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..830fdf4ab69d6aee0e7c208a65d76e1aacf5f34f
--- /dev/null
+++ b/net/base/network_throttle_manager_impl.cc
@@ -0,0 +1,306 @@
+// 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;

[Charlie Harrison, 2016/09/01 18:17:52]

Brief comment where you get this number would be helpful. Histogram?

[Randy Smith (Not in Mondays), 2016/09/18 19:12:34]

You have more faith in me than is valid--this number came out of the air :-}. 
Do you know of a histogram tracking request/transaction lifetimes?  I poked
around a bit in the code and didn't find anything.

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

Can you use Net.RequestTime2.Success? Median looks like 274.4ms to me but it
also includes cached requests.

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

Done, though since the distribution was bi-modal I arbitrarily assumed the fast
bump was cached requests, excluded them, and took the median of the rest (for
stable channel).  Let me know if you find something (egregiously :-}) wrong with
my fast-and-loose statistics.

I'll note that I winced at referring to a histogram generated at a layer above
this one in the code base, but decided that as explanation for a hard-coded
value I could live with it.

+
+NetworkThrottleManagerImpl::ThrottleImpl::ThrottleImpl(
+    bool blocked,
+    RequestPriority priority,
+    NetworkThrottleManager::ThrottleDelegate* delegate,
+    NetworkThrottleManagerImpl* manager,
+    QueuePointer queue_pointer)
+    : blocked_(blocked),
+      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 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::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_(50, kInitialMedianInMs),

[Charlie Harrison, 2016/09/01 18:17:52]

Magic numbers scare me. As a reader it would be nice to either have
documentation here what 50 is or give the number a name. Otherwise I have to go
to the estimate constructor to see what the param is.

[Randy Smith (Not in Mondays), 2016/09/18 19:12:34]

Done.

+      start_time_ordering_set_(
+          &NetworkThrottleManagerImpl::CompareThrottlesForCreationTime),
+      num_throttles_blocked_(0u),
+      num_effective_outstanding_(0u),
+      outstanding_recomputation_timer_(false /* retain_user_task */,
+                                       false /* is_repeating */),
+      tick_clock_(new base::DefaultTickClock()) {
+  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()));
+
+  ThrottleImpl::ThrottleList* throttle_list =
+      ListForThrottle(blocked, priority);
+
+  throttle->set_queue_pointer(
+      throttle_list->insert(throttle_list->end(), throttle.get()));
+  if (blocked)
+    ++num_throttles_blocked_;
+  else
+    start_time_ordering_set_.insert(throttle.get());
+
+  // Can only have increased the outstanding count (decreases due to aging out
+  // would be caught by timer) so a MaybeUnblockThrottles() isn't needed.
+  RecomputeOutstanding();
+  DCHECK_EQ(num_throttles_blocked_, NumberBlockedThrottles());

[mmenke, 2016/09/01 19:14:23]

If !blocked(), this doesn't get us anything, does it?  In fact, this is only
useful if start_time_ordering_set_.length() == 1 (after adding the new throttle)
and not blocked, right?  I'm not sure about the overhead of needlessly updating
a timer, but I'd guess that each time we do it, we end up posting an extra task
with a weak pointer that's cleared when we post such a task again.

Or could just make RecomputeOutstanding do nothing if the timer is already
running (Only potential issue is if the IOThread is busy, so the timer hasn't
triggered yet, I think?)

[Randy Smith (Not in Mondays), 2016/09/18 19:12:34]

RecomputeOustanding() does two things: It modifies the outstanding count, and it
sets a timer for the earliest possible time when we could need to age a throttle
out of the outstanding set (== start_time_ordering_set_).  If the timer's
already running, then it's set for <= the time this call to
RecomputeOutstanding() (less than if the request that originally had the timer
set has completed).  

So based on that analysis, yes, if the new throttle is blocked, this call
doesn't get us anything, but if it isn't blocked, there's some value even if
it's not the only element in the start_time_ordering_set_.  However, given your
analysis of the cost of a timer update, I'm inclined to say that that's not
worth worrying about.  Instead, I'm going to do the following things:
* Try and pull *all* the logic about what updates do or do not need to happen
into RecomputeOustanding() (so it's all in one place)
* Clear the timer if there are no outstanding requests.
* Not worry about pushing the timer out if it's already running and will fire at
or before the point at which we'd ideally like it to.

+
+  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();
+  }
+}
+
+bool NetworkThrottleManagerImpl::CompareThrottlesForCreationTime(

[mmenke, 2016/09/01 19:14:22]

ForCreationTime -> ByCreationTime?

Also kind wonder about "compare" - I generally associate it with returning an
int, with 0 meaning ==, instead of a bool.

[Randy Smith (Not in Mondays), 2016/09/18 19:12:34]

Your question about "compare" got me chasing what the the function parameter to
the std::set constructor was named, and it is "compare".  So I'd be happy with
CompareThrottleByCreationTime, but based on your confusion and the std::set
constructor tie-in, I'm trying CreationTimeSetCompare (i.e. compare as a noun). 
But I'm happy to do CompareThrottleBy... or something else if you prefer.

+    ThrottleImpl* throttle1,
+    ThrottleImpl* throttle2) {
+  // No throttle should be in the CreationOrderingSet 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) {
+  ThrottleImpl::ThrottleList* old_throttle_list =
+      ListForThrottle(throttle->IsBlocked(), old_priority);
+  DCHECK(std::find(old_throttle_list->begin(), old_throttle_list->end(),
+                   throttle) != old_throttle_list->end());
+
+  old_throttle_list->erase(throttle->queue_pointer());
+
+  // Check to see if this priority change is changing blocking state.
+  // Currently the only possible transition is from THROTTLED/blocked
+  // to UNTHROTTLED/blocked, so just check for that.
+  bool unblocking = (old_priority == THROTTLED && new_priority != THROTTLED &&
+                     throttle->IsBlocked());
+  ThrottleImpl::ThrottleList* new_throttle_list =
+      ListForThrottle(unblocking ? false : throttle->IsBlocked(), new_priority);
+
+  throttle->set_queue_pointer(
+      new_throttle_list->insert(new_throttle_list->end(), throttle));
+
+  // There is no need to call |MaybeUnblockThrottles()| because
+  // changing a throttle priority will not have decreased the number of
+  // outstanding throttles.
+
+  if (unblocking) {

[mmenke, 2016/09/01 19:14:22]

Can this just call UnblockThrottle?

[Randy Smith (Not in Mondays), 2016/09/18 19:12:34]

UnblockThrottles does queue management which is related to but not the same as
the queue management done above this point.  Having said that, yeah, it sure
seems like there should be some sharable infrastructure here.  I'll take a look
at that when I go through the whole design with an eye on your complexity
issues.  

+    // 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->set_start_time(tick_clock_->NowTicks());
+    start_time_ordering_set_.insert(throttle);
+    throttle->NotifyUnblocked();
+  }
+  DCHECK_EQ(num_throttles_blocked_, NumberBlockedThrottles());
+}
+
+void NetworkThrottleManagerImpl::OnThrottleDestroyed(ThrottleImpl* throttle) {
+  // If the throttle has a start time, register its lifetime.
+  if (!throttle->IsBlocked()) {
+    DCHECK_NE(throttle->start_time(), base::TimeTicks());
+
+    lifetime_median_estimate_.AddSample(
+        (tick_clock_->NowTicks() - throttle->start_time())
+            .InMillisecondsRoundedUp());
+  }
+
+  ThrottleImpl::ThrottleList* throttle_list = ListForThrottle(throttle);
+  DCHECK(std::find(throttle_list->begin(), throttle_list->end(), throttle) !=
+         throttle_list->end());
+  throttle_list->erase(throttle->queue_pointer());
+  if (throttle->IsBlocked()) {
+    --num_throttles_blocked_;
+  } else {
+    size_t items_erased = start_time_ordering_set_.erase(throttle);
+    DCHECK_EQ(1u, items_erased);
+  }
+
+  // TODO(rdsmith): Via PostTask so there aren't upcalls from within
+  // destructors?

[mmenke, 2016/09/01 19:14:23]

+1

[Randy Smith (Not in Mondays), 2016/09/18 19:12:34]

Done.

+  MaybeUnblockThrottles();
+  DCHECK_EQ(num_throttles_blocked_, NumberBlockedThrottles());
+}
+
+void NetworkThrottleManagerImpl::RecomputeOutstanding() {
+  DCHECK_EQ(num_throttles_blocked_, NumberBlockedThrottles());
+  outstanding_recomputation_timer_.Stop();
+
+  num_effective_outstanding_ = start_time_ordering_set_.size();
+  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| times the lifetime median
+  // estimate.
+  int median_estimate_in_ms = lifetime_median_estimate_.current_estimate();
+  if (median_estimate_in_ms == 0)
+    median_estimate_in_ms = 1;
+
+  base::TimeTicks age_horizon(
+      tick_clock_->NowTicks() -
+      (kMedianLifetimeMultiple *
+       base::TimeDelta::FromMilliseconds(median_estimate_in_ms)));
+  for (const auto* throttle : start_time_ordering_set_) {
+    DCHECK_NE(throttle->start_time(), base::TimeTicks());
+    if (throttle->start_time() > age_horizon) {
+      // The earliest we might need to re-evaluate the outstanding count
+      // and blocked status is the amount of time it will take the current
+      // element to age out of the effective set.
+      outstanding_recomputation_timer_.Start(
+          FROM_HERE, 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)));
+      break;
+    }
+
+    // Throttles before the age_horizon have aged out of being counted
+    // as outstanding.
+    num_effective_outstanding_--;
+  }
+}
+
+void NetworkThrottleManagerImpl::UnblockThrottle(ThrottleImpl* throttle) {
+  DCHECK(throttle->IsBlocked());
+
+  ThrottleImpl::ThrottleList* throttle_list = ListForThrottle(throttle);
+  RequestPriority priority = throttle->priority();
+
+  DCHECK(std::find(throttle_list->begin(), throttle_list->end(), throttle) !=
+         throttle_list->end());
+  ListForThrottle(throttle)->erase(throttle->queue_pointer());
+
+  throttle->set_queue_pointer(unblocked_requests_[priority].insert(
+      unblocked_requests_[priority].end(), throttle));
+
+  throttle->set_start_time(tick_clock_->NowTicks());
+  start_time_ordering_set_.insert(throttle);
+
+  // No need to call RecomputeOutstanding() here as we know the just
+  // unblocked throttle counts as outstanding, because the start time
+  // is NowTicks().
+  ++num_effective_outstanding_;
+  --num_throttles_blocked_;
+
+  // May result in re-entrant calls into this class.
+  throttle->NotifyUnblocked();
+}
+
+void NetworkThrottleManagerImpl::MaybeUnblockThrottles() {
+  RecomputeOutstanding();
+
+  while (num_effective_outstanding_ < kActiveRequestThrottlingLimit &&
+         !blocked_requests_[THROTTLED].empty()) {
+    // NOTE: This call may result in reentrant calls into
+    // NetworkThrottleManagerImpl; no state should be assumed to be
+    // persistent across this call.
+    UnblockThrottle(blocked_requests_[THROTTLED].front());
+  }
+  DCHECK_EQ(num_throttles_blocked_, NumberBlockedThrottles());
+}
+
+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());
+}
+
+size_t NetworkThrottleManagerImpl::NumberBlockedThrottles() const {
+  size_t blocked_count = 0u;
+  for (int i = 0; i < NUM_PRIORITIES; ++i)
+    blocked_count += blocked_requests_[i].size();
+  return blocked_count;
+}
+
+}  // namespace net