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..430c4db7cc9834b94423652ccc118041721592f5
--- /dev/null
+++ b/net/base/network_throttle_manager_impl.h
@@ -0,0 +1,148 @@
+// 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/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 kMedianEstimatorLearningParameter;
+  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

[Charlie Harrison, 2016/07/07 20:17:26]

nit: Throttle:

[Randy Smith (Not in Mondays), 2016/07/08 20:54:24]

Done.

+    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::Time 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::Time creation_time_;
+
+    // For deletion from owning queue.
+    QueuePointer queue_pointer_;
+
+    DISALLOW_COPY_AND_ASSIGN(ThrottleImpl);
+  };
+
+  NetworkThrottleManagerImpl();
+  ~NetworkThrottleManagerImpl() override;
+
+  // NetworkThrottleManager

[Charlie Harrison, 2016/07/07 20:17:26]

nit: NetworkThrottleManager:

[Randy Smith (Not in Mondays), 2016/07/08 20:54:24]

Done.

+  std::unique_ptr<Throttle> CreateThrottle(ThrottleDelegate* delegate,
+                                           RequestPriority priority,
+                                           bool ignore_limits) override;
+
+  void SetClockForTesting(std::unique_ptr<base::Clock> clock);

[Charlie Harrison, 2016/07/07 20:17:26]

Can this be protected?

[Randy Smith (Not in Mondays), 2016/07/08 20:54:24]

So I think of there as being a couple of ways to do this type of "test only"
interface.  Relying on the "ForTesting()" idiom is one, and I think there's some
script support to make sure that's only called from test files.  The other is to
friend the test fixture and make the method private (or just reach in and tweak
the variables).  I don't like that just because it makes less clear what the
interface surface the test is targeting.  But if you have a strong preference in
that direction, I'm willing to shift to it.  (Or if there's some other direction
you'd like me to explore, I'm happy to, but you'll need to give me a clearer
pointer.)

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

Actually, I think I prefer ForTesting too.

+
+ private:
+  static bool CompareThrottlesForCreationTime(ThrottleImpl* throttle1,

[Charlie Harrison, 2016/07/07 20:17:26]

Can you document this method and its relation to the CreationOrderingSet?

[Randy Smith (Not in Mondays), 2016/07/08 20:54:24]

Good point, done.

+                                              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();
+
+  // Check 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 MaybeUnblock();
+
+  std::list<ThrottleImpl*>* ListForThrottle(bool blocked,

[Charlie Harrison, 2016/07/07 20:17:26]

Can you document these too?

[Randy Smith (Not in Mondays), 2016/07/08 20:54:24]

Done.

+                                            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::Clock> clock_;
+
+  DISALLOW_COPY_AND_ASSIGN(NetworkThrottleManagerImpl);
+};
+
+}  // namespace net
+
+#endif  // NET_BASE_NETWORK_THROTTLE_MANAGER_IMPL_H_