Implement THROTTLED priority semantics.

net/base/network_throttle_manager_impl.h

Index: net/base/network_throttle_manager_impl.h
diff --git a/net/base/network_throttle_manager_impl.h b/net/base/network_throttle_manager_impl.h
new file mode 100644
index 0000000000000000000000000000000000000000..bc52768a52c2cdb986a245d29e0d22d4ec10c385
--- /dev/null
+++ b/net/base/network_throttle_manager_impl.h
@@ -0,0 +1,159 @@
+// 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.
+
+#ifndef NET_BASE_NETWORK_THROTTLE_MANAGER_IMPL_H_
+#define NET_BASE_NETWORK_THROTTLE_MANAGER_IMPL_H_
+
+#include <list>
+#include <memory>
+#include <set>
+
+#include "base/memory/weak_ptr.h"
+#include "base/time/tick_clock.h"
+#include "base/time/time.h"
+#include "base/timer/timer.h"
+#include "net/base/network_throttle_manager.h"
+#include "net/base/percentile_estimator.h"
+
+namespace net {
+
+// The NetworkThrottleManagerImpl implements the following semantics:
+// * All throttles of priority above THROTTLED are created unblocked.
+// * Throttles of priority THROTTLED are created unblocked, unless
+//   there are |kActiveRequestThrottlingLimit| or more throttles active,
+//   in which case they are created blocked.
+//   When that condition is no longer true, throttles of priority
+//   THROTTLED are unblocked, in FIFO order.
+// * Throttles that have been alive for more than |kMedianLifetimeMultiple|
+//   times the current estimate of the throttle median lifetime do
+//   not count against the |kActiveRequestThrottlingLimit| limit.
+class NET_EXPORT NetworkThrottleManagerImpl : public NetworkThrottleManager {
+ public:
+  // Maximum number of active requests before new THROTTLED throttles
+  // are created blocked.  Throttles are unblocked as the active requests
+  // fall below this limit.
+  static const size_t kActiveRequestThrottlingLimit;
+
+  // Note that the following constants are implementation details exposed in the
+  // header file only for testing, and should not be relied on by consumers.
+
+  // Constants used for the running estimate of the median lifetime
+  // for throttles created by this class.  That estimate is used to detect
+  // throttles that are "unusually old" and hence may represent hanging GETs
+  // or long-running streams.  Such throttles should not be considered
+  // "active" for the purposes of determining whether THROTTLED throttles
+  // should be created in a blocked state.
+  // Note that the precise details of this algorithm aren't very important;
+  // specifically, if it takes a while for the median estimate to reach the
+  // "actual" median of a request stream, the consequence is either a bit more
+  // of a delay in unblocking THROTTLED requests or more THROTTLED requests
+  // being unblocked than would be ideal (i.e. performance tweaks at
+  // the margins).
+
+  // Multiple of the current median lifetime beyond which a throttle is
+  // considered "unusually old" and not considered in counting active
+  // requests. This is used instead of a percentile estimate because the goal
+  // is eliminating requests that are qualitatively different
+  // (e.g. hanging gets, streams), and the percentage of all requests
+  // that are in that category can vary greatly.
+  static const int kMedianLifetimeMultiple;
+
+  // The median lifetime estimate starts at class creation at
+  // |kInitialMedianInMs|.
+  static const int kInitialMedianInMs;
+
+  NetworkThrottleManagerImpl();
+  ~NetworkThrottleManagerImpl() override;
+
+  // NetworkThrottleManager:
+  std::unique_ptr<Throttle> CreateThrottle(ThrottleDelegate* delegate,
+                                           RequestPriority priority,
+                                           bool ignore_limits) override;
+
+  void SetTickClockForTesting(std::unique_ptr<base::TickClock> tick_clock);
+
+  // If the |NowTicks()| value of |tick_clock_| is greater than the
+  // time the outstanding_recomputation_timer_ has set to go off, Stop()
+  // the timer and manually run the associated user task.  This is to allow
+  // "fast-forwarding" of the clock for testing by working around
+  // base::Timer's direct use of base::TimeTicks rather than a base::TickClock.
+  //
+  // Note specifically that base::Timer::Start takes a time delta into the
+  // future and adds it to base::TimeTicks::Now() to get
+  // base::Timer::desired_run_time(), which is what this method compares
+  // |tick_clock_->NowTicks()| against.  So tests should be written so that
+  // the timer Start() routine whose callback should be run is called
+  // with |tick_clock_| in accord with wallclock time.  This routine can then
+  // be called with |tick_clock_| set into the future.
+  //
+  // Returns true if there was a timer running and it was triggerred
+  // (|tick_clock_->NowTicks() >
+  //   outstanding_recomputation_timer_.desired_run_time()|).
+  bool ConditionallyTriggerTimerForTesting();
+
+ private:
+  class ThrottleImpl;
+  using ThrottleList = std::list<ThrottleImpl*>;
+
+  // Comparison function used to define the ordering relationship
+  // for |StartTimeOrderedSet| below.
+  static bool StartTimeSetCompare(ThrottleImpl* throttle1,
+                                  ThrottleImpl* throttle2);
+
+  using StartTimeOrderedSet =
+      std::set<ThrottleImpl*, bool (*)(ThrottleImpl*, ThrottleImpl*)>;
+
+  void OnThrottlePriorityChanged(ThrottleImpl* throttle,
+                                 RequestPriority old_priority,
+                                 RequestPriority new_priority);
+  void OnThrottleDestroyed(ThrottleImpl* throttle);
+
+  // Recompute how many requests count as outstanding (i.e.
+  // are not older than kMedianLifetimeMultiple * MedianThrottleLifetime()).
+  // If outstanding_recomputation_timer_ is not set, it will be set
+  // to the earliest a throttle might "age out" of the outstanding list.
+  void RecomputeOutstanding();
+
+  // Unblock the specified throttle.  May result in re-entrant calls
+  // into NetworkThrottleManagerImpl.
+  void UnblockThrottle(ThrottleImpl* throttle);
+
+  // Recomputes how many requests count as outstanding, checks to see
+  // if any currently blocked throttles should be unblocked,
+  // and unblock them if so.  Note that unblocking may result in
+  // re-entrant calls to this class, so no assumptions about state persistence
+  // should be made across this call.
+  void MaybeUnblockThrottles();
+
+  PercentileEstimator lifetime_median_estimate_;
+
+  // base::Timer controlling outstanding request recomputation.
+  //
+  // This is started whenever it is not running and a new throttle is
+  // added to |outstanding_throttles_|, and is never cleared except by
+  // execution, which re-starts it if there are any
+  // outstanding_throttles_.  So it should always be running if any
+  // throttles are outstanding.  This guarantees that the class will
+  // eventually detect aging out of outstanding throttles and unblock
+  // throttles blocked on those outstanding throttles.
+  base::Timer outstanding_recomputation_timer_;
+
+  // Contains only OUTSTANDING throttles.
+  StartTimeOrderedSet outstanding_throttles_;

[mmenke, 2016/10/12 15:39:12]

Do we get anything from making this a set, and ThrottleList a list?

They're both containers in which order doesn't change, we only append to the
end, we only read from the start (After which, we also remove from the start),
and we remove random ThrottleImpls from.

Given that the set of operations is identical, why aren't we using the same
structure?  I guess reprioritization only affects blocked_throttles_, but I
don't think that warrants a different data structure?

Conveniently, if we use the same data structure, we'd either need to make
blocked_queue_pointer_ point to an oustanding queue position instead, and would
have a sane value to initialize it to, at least.  Or if we made them both sorted
sets, we could do away with it entirely.

[Randy Smith (Not in Mondays), 2016/10/18 21:41:05]

Ah, good point; for historical reasons (shift of time ordering to start time
from creation time) I had missed that the two data structures were
semi-equivalent.  I certainly agree that it would be simple if they were the
same data structure.  If I made them both ordered sets, I'd need to create some
key to order the blocked throttles (I could make it creation time, but that
seems artificial, since I'm not doing that anywhere else).  I think erasing an
element is the same cost in both (it's "amortized constant" for a set, and O(#
elements erased) for a list), and I think the list is less costly in terms of
space (no need to store the key, tree implementation of a set would have two
pointers, as would a doubly linked list).  So I'll go with implementing them
both as a list.

ETA: This doesn't remove the "We're using the null value as the .end() result
from a list unrelated to the throttle" problem as we still need to null the
throttle queue pointer for AGED throttles.  However, this simplifies the code a
bit and I think has better space usage (slightly), so I'm going with it anyway. 
Let me know what you think.

+
+  // FIFO list of BLOCKED throttles.  This is a list so that the
+  // throttles can store iterators to themselves.
+  ThrottleList blocked_throttles_;
+
+  // For testing.
+  std::unique_ptr<base::TickClock> tick_clock_;
+
+  base::WeakPtrFactory<NetworkThrottleManagerImpl> weak_ptr_factory_;
+
+  DISALLOW_COPY_AND_ASSIGN(NetworkThrottleManagerImpl);
+};
+
+}  // namespace net
+
+#endif  // NET_BASE_NETWORK_THROTTLE_MANAGER_IMPL_H_