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*>;

[Charlie Harrison, 2016/09/23 15:11:12]

Can you use a deque? I think it will have better cache performance and memory
overhead.

[Randy Smith (Not in Mondays), 2016/09/23 22:16:49]

So I considered using a deque, but didn't because the cost of removing things
from the middle of the list (as happens on cancels) would be O(N).   I agree it
would have better memory overhead, but can you give me the cache argument?  From
my perspective, this list is going to be accessed occasionally in a see of a lot
of other accesses having to do with the whole stack of the network request, and
never (?) going to be gone through sequentially, element by element.  So I'm not
sure cache performance arguments apply.

[Charlie Harrison, 2016/09/26 22:27:27]

There are a few times when I could (maybe) see cache locality of the deque
benefit us:
1. <body> tag hit -> Blink mass reprioritizes requests and unblocks them in a
tight loop. Tab foregrounding could do the same.
2. Document is detached, stop all requests in a tight loop. This will happen if
we navigate away from a loading page or close a loading tab.

In these cases we will be removing / accessing potentially hundreds of elements
all at once to either destroy them or mass move them from container to
container. I'm not quite sure how the code will look for that but it might make
things a bit better.

In any case, you're right, random deletion from the list will have better
performance. This is the best benchmark I could find:
http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

Note: random removal searches in the linked list removal case, so probably best
to assume that random removal is equivalent to push_back for our list (since we
know the iterator beforehand).

I'm pretty happy with whatever you choose, std::list<small thing> just throws a
red flag for me due to dynamic allocation and >= 3x memory overhead for node
management.

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

Yeah, unless we have batch IPCs for those and plumb them all the way down into
the stack, my gut says the cache is going to be pretty trashed each time around
the loop.  A "tight loop" on the renderer with browser elements is still a lot
of code to execute.  
Um ... the spec guarantees complexity O(elements removed), not O(size of list),
so I don't think it searches.  I agree it's equivalent to push_back, which I'd
expect to be O(1).  See http://www.cplusplus.com/reference/list/list/erase/,
"Complexity".
Yeah; to be fair, I think the 3x memory overhead is real and worth worrying
about.  It's not a *lot* of memory overhead given that it's per-request, and
URLRequest is pretty big all on its own (and there's per-request overhead in the
browser that isn't URLRequest).  So I'm not inclined to worry about it in this
CL.  Having said that, I do agree it's making a bad problem a little worse, and
you could push me towards a deque for that reason if that bothered you.  But I'm
not (yet) buying the cache argument.

[Charlie Harrison, 2016/10/03 20:53:48]

That's what I am hoping we end up doing (i.e. batch the IPCs). Otherwise we can
end up sending IPCs in a tight loop on the renderer, causing context thrashing
and descheds.
 
Sorry, I was referencing the benchmark, where I believe they traversed the list
to find the iterator first.
SGTM. The cache argument isn't valid unless we do batching IPC.

+
+  // Comparison function used to define the ordering relationship
+  // for |CreationTimeOrderedSet| below.
+  static bool CreationTimeSetCompare(ThrottleImpl* throttle1,
+                                     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_;
+
+  // 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_