Implement THROTTLED priority semantics.

net/base/network_throttle_manager_impl.h

+// 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 priority 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.
+  void ConditionallyTriggerTimerForTesting();
+
+ private:
+  class ThrottleImpl;
+  using ThrottleList = std::list<ThrottleImpl*>;
+
+  // Comparison function used to define the ordering relationship
+  // for |CreationTimeOrderedSet| below.
+  static bool CreationTimeSetCompare(ThrottleImpl* throttle1,

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

Appologies, I believe I suggested this name, but I was confused at the time. 
This is actually start_time, not creation_time, right?

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

*chuckle*  Right you are--I missed that too.  Thank you; done.

+                                     ThrottleImpl* throttle2);
+
+  using CreationTimeOrderedSet =
+      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()).
+  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.
+  base::Timer outstanding_recomputation_timer_;
+
+  // Contains only OUTSTANDING throttles.
+  CreationTimeOrderedSet outstanding_throttles_;
+
+  // FIFO list of BLOCKED throttles.  This is a list so that the
+  // throttles can store iterators to themselves.
+  ThrottleList blocked_throttles_;
+
+  // Used to detect changes in the oustanding set that should lead to a
+  // timer refresh.  void* because this value should be used only for
+  // comparison and not indirected through; it may refer to a freed throttle.
+  void* first_outstanding_throttle_;
+
+  // 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_