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..d0371a7d3d3ca746d5ed49113855ce24de6dff4b
--- /dev/null
+++ b/net/base/network_throttle_manager_impl.h
@@ -0,0 +1,208 @@
+// 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/time/tick_clock.h"
+#include "base/time/time.h"
+#include "base/timer/timer.h"
+#include "net/base/network_throttle_manager.h"
+#include "net/base/quantile_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.
+  static const int kMedianLifetimeMultiple;

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

Why not just implement the algorithm that calculates e.g. 95th percentile? Is
there a reason you prefer constant*median? It seems less intuitive to me.

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

I want things that are qualitatively different to age out.  There are contexts
in which I think we should track all requests (no hanging gets, no downloads)
and I don't want the boundary shifted if there are a lot of those things going
on.  I think a percentile measurement will be less consistent about leaving out
"strange things" than median*multiple.  

I've added a sentence saying basically the same thing to the comments, but I
think the main question is whether you find the rationale satisfying or not--let
me know if you don't.

+
+  // 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 : public NetworkThrottleManager::Throttle {
+   public:
+    using ThrottleList = std::list<ThrottleImpl*>;
+    using QueuePointer = ThrottleList::iterator;
+
+    // Caller must arrange that |*delegate| and |*manager| outlive
+    // the ThrottleImpl class.
+    ThrottleImpl(bool blocked,
+                 RequestPriority priority,
+                 ThrottleDelegate* delegate,
+                 NetworkThrottleManagerImpl* manager,
+                 QueuePointer queue_pointer);
+
+    ~ThrottleImpl() override;
+
+    // Throttle:
+    bool IsBlocked() const override;
+    RequestPriority Priority() const override;
+    void SetPriority(RequestPriority priority) override;
+
+    RequestPriority priority() const { return priority_; }
+    QueuePointer queue_pointer() const { return queue_pointer_; }
+    void set_queue_pointer(const QueuePointer& pointer) {
+      queue_pointer_ = pointer;
+    }
+    base::TimeTicks start_time() const { return start_time_; }
+    void set_start_time(base::TimeTicks start_time) {
+      start_time_ = start_time;
+    }
+
+    // Note that this call calls the delegate, and hence
+    // 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:
+    bool blocked_;
+    RequestPriority priority_;
+    ThrottleDelegate* const delegate_;
+    NetworkThrottleManagerImpl* const manager_;
+
+    base::TimeTicks start_time_;
+
+    // For deletion from owning queue.
+    QueuePointer queue_pointer_;
+
+    DISALLOW_COPY_AND_ASSIGN(ThrottleImpl);
+  };
+
+  // Comparison function used to define the ordering relationship
+  // for |CreationOrderingSet| below.
+  static bool CompareThrottlesForCreationTime(ThrottleImpl* throttle1,
+                                              ThrottleImpl* throttle2);

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

This does need to be in this file, right?

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

It needs access to the start time of the throttles passed to it, and those are
methods on a private nested class of NetworkThrottleManagerImpl.  To access that
class, it needs to be a member or friend of NetworkThrottleManagerImpl.  If any
of those dependencies change, I could move it.  

Thinking about that question, I don't think ThrottleImpl needs to be in the
header file, except as a forward decl.  I'll explore moving it to the .cc file
(not doing so inline as I want to engage with your philosophical issues before I
dig into details).

ETA: ThrottleImpl is now in the .cc file.

+
+  using CreationOrderingSet =

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

CreationTimeOrderedSet?  This it's better to name a set after what it contains /
what is is, not what it does on insertion.

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

Done.

+      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();
+
+  // Convenience functions to determine which of the ThrottleLists
+  // from {blocked,unblocked}_requests_ apply to a given
+  // throttle/(blocked, priority) pair.
+  ThrottleImpl::ThrottleList* ListForThrottle(bool blocked,

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

Technically not really the list for a throttle, but a list for a (blocked,
priority) tuple. I don't have a great suggestion but I think changing these both
to be GetThrottleList() may better.

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

Done.

+                                              RequestPriority priority);
+  ThrottleImpl::ThrottleList* ListForThrottle(ThrottleImpl* throttle);
+
+  // For DCHECK assertions: Could the number of blocked throttles.
+  size_t NumberBlockedThrottles() const;
+
+  QuantileEstimator lifetime_median_estimate_;
+
+  // Only contains unblocked throttles; blocked throttles haven't started
+  // and hence don't have a start time.
+  CreationOrderingSet start_time_ordering_set_;
+
+  size_t num_throttles_blocked_;
+
+  // Count of throttles that are considered as outstanding.  Throttles that
+  // are too old or blocked are not counted.
+  size_t num_effective_outstanding_;
+
+  // base::Timer controlling outstanding request recomputation.
+  base::Timer outstanding_recomputation_timer_;
+
+  // Lists of blocked/unblocked request at each priority level.
+  // It is safe to store a raw pointer in these lists because the
+  // manager will be notified by OnThrottleDestroyed before a ThrottleImpl
+  // is destroyed, and will remove the pointer from the appropriate list
+  // at that point.
+  ThrottleImpl::ThrottleList blocked_requests_[NUM_PRIORITIES];
+  ThrottleImpl::ThrottleList unblocked_requests_[NUM_PRIORITIES];
+
+  // For testing.
+  std::unique_ptr<base::TickClock> tick_clock_;
+
+  DISALLOW_COPY_AND_ASSIGN(NetworkThrottleManagerImpl);
+};
+
+}  // namespace net
+
+#endif  // NET_BASE_NETWORK_THROTTLE_MANAGER_IMPL_H_