blob: 47afcc46ffa10298a473aa54f115512c938a43ed [file] [log] [blame]
// 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.
#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 FIFO 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 {
// 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() 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.
// Returns true if there was a timer running and it was triggerred
// (|tick_clock_->NowTicks() >
// outstanding_recomputation_timer_.desired_run_time()|).
bool ConditionallyTriggerTimerForTesting();
class ThrottleImpl;
using ThrottleList = std::list<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()).
// If outstanding_recomputation_timer_ is not set, it will be set
// to the earliest a throttle might "age out" of the outstanding list.
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.
// This is started whenever it is not running and a new throttle is
// added to |outstanding_throttles_|, and is never cleared except by
// execution, which re-starts it if there are any
// outstanding_throttles_. So it should always be running if any
// throttles are outstanding. This guarantees that the class will
// eventually detect aging out of outstanding throttles and unblock
// throttles blocked on those outstanding throttles.
base::Timer outstanding_recomputation_timer_;
// FIFO of OUTSTANDING throttles (ordered by time of entry into the
// OUTSTANDING state).
ThrottleList 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_;
} // namespace net