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..a667b8b217f81a7d62770db5e9e2f6eed97f6739
--- /dev/null
+++ b/net/base/network_throttle_manager_impl.h
@@ -0,0 +1,161 @@
+// 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"
+
+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 NetworkThrottleManagerImpl : public NetworkThrottleManager {
+ public:
+  static const size_t kActiveRequestThrottlingLimit;
+  static const double kMedianEstimatorDeltaMS;
+  static const int kInitialMedianInMS;
+  static const int kMedianLifetimeMultiple;
+
+  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 creation_time() const { return creation_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 creation_time_;
+
+    // For deletion from owning queue.
+    QueuePointer queue_pointer_;
+
+    DISALLOW_COPY_AND_ASSIGN(ThrottleImpl);
+  };
+
+  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 the classes clock_ is greater than the

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

nit: s/classes clock/|tick_clock_/

I almost suggested the possessive "class's", but that's kind of horrible.

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

Done.
I thought when a word ended with "s" one just appended an apostrophe for
possession, i.e. "the class' clock".  But now that I right it out, it looks
wrong.  Ah, well, I don't mind referencing private variables (and thus breaking
the class abstraction barrier) in a testing method description :-}.

+  // 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 TickClock.

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

Be consistent about prefacing with base:: or don't do it at all.

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

Whoops, sorry.  Took a scan through for Timer, TimeTicks, and TickClock; let me
know if I missed something. 

+  void ConditionallyTriggerTimerForTesting();
+
+ private:
+  // Comparison function used to define the ordering relationship
+  // for |CreationOrderingSet| below.
+  static bool CompareThrottlesForCreationTime(ThrottleImpl* throttle1,
+                                              ThrottleImpl* throttle2);
+
+  using CreationOrderingSet =
+      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();
+
+  // 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 std::list<ThrottleImpl*>s
+  // from {blocked,unblocked}_requests_ apply to a give

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

s/give/given

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

Done.

+  // throttle/(blocked, priority) pair.
+  std::list<ThrottleImpl*>* ListForThrottle(bool blocked,
+                                            RequestPriority priority);
+  std::list<ThrottleImpl*>* ListForThrottle(ThrottleImpl* throttle);
+
+  base::TimeDelta lifetime_median_estimate_;
+  CreationOrderingSet creation_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_;
+
+  // 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.
+  std::list<ThrottleImpl*> blocked_requests_[NUM_PRIORITIES];
+  std::list<ThrottleImpl*> 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_