diff options
Diffstat (limited to 'net')
| -rw-r--r-- | net/base/backoff_entry.cc | 119 | ||||
| -rw-r--r-- | net/base/backoff_entry.h | 94 | ||||
| -rw-r--r-- | net/base/backoff_entry_unittest.cc | 203 | ||||
| -rw-r--r-- | net/net.gyp | 3 | ||||
| -rw-r--r-- | net/url_request/url_request_throttler_entry.cc | 152 | ||||
| -rw-r--r-- | net/url_request/url_request_throttler_entry.h | 48 | ||||
| -rw-r--r-- | net/url_request/url_request_throttler_entry_interface.h | 4 | ||||
| -rw-r--r-- | net/url_request/url_request_throttler_header_adapter.h | 1 | ||||
| -rw-r--r-- | net/url_request/url_request_throttler_manager.h | 1 | ||||
| -rw-r--r-- | net/url_request/url_request_throttler_unittest.cc | 109 |
10 files changed, 526 insertions, 208 deletions
diff --git a/net/base/backoff_entry.cc b/net/base/backoff_entry.cc new file mode 100644 index 0000000..830eca4 --- /dev/null +++ b/net/base/backoff_entry.cc @@ -0,0 +1,119 @@ +// Copyright (c) 2011 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 "net/base/backoff_entry.h" + +#include <algorithm> +#include <cmath> + +#include "base/logging.h" +#include "base/rand_util.h" + +namespace net { + +BackoffEntry::BackoffEntry(const BackoffEntry::Policy* const policy) + : failure_count_(0), + policy_(policy) { + DCHECK(policy_); + + // Can't use GetTimeNow() as it's virtual. + exponential_backoff_release_time_ = base::TimeTicks::Now(); +} + +BackoffEntry::~BackoffEntry() { + // TODO(joi): Remove this once our clients (e.g. URLRequestThrottlerManager) + // always destroy from the I/O thread; at the moment we may be destroyed + // from the main thread (during AtExit processing). + DetachFromThread(); +} + +void BackoffEntry::InformOfRequest(bool succeeded) { + if (!succeeded) { + failure_count_++; + exponential_backoff_release_time_ = CalculateReleaseTime(); + } else { + failure_count_ = 0; + + // The reason why we are not just cutting the release time to GetTimeNow() + // is on the one hand, it would unset a release time set by + // SetCustomReleaseTime and on the other we would like to push every + // request up to our "horizon" when dealing with multiple in-flight + // requests. Ex: If we send three requests and we receive 2 failures and + // 1 success. The success that follows those failures will not reset the + // release time, further requests will then need to wait the delay caused + // by the 2 failures. + exponential_backoff_release_time_ = std::max( + GetTimeNow(), exponential_backoff_release_time_); + } +} + +bool BackoffEntry::ShouldRejectRequest() const { + return exponential_backoff_release_time_ > GetTimeNow(); +} + +base::TimeTicks BackoffEntry::GetReleaseTime() const { + return exponential_backoff_release_time_; +} + +void BackoffEntry::SetCustomReleaseTime(const base::TimeTicks& release_time) { + exponential_backoff_release_time_ = release_time; +} + +bool BackoffEntry::CanDiscard() const { + if (policy_->entry_lifetime_ms == -1) + return false; + + base::TimeTicks now = GetTimeNow(); + + int64 unused_since_ms = + (now - exponential_backoff_release_time_).InMilliseconds(); + + // Release time is further than now, we are managing it. + if (unused_since_ms < 0) + return false; + + if (failure_count_ > 0) { + // Need to keep track of failures until maximum back-off period + // has passed (since further failures can add to back-off). + return unused_since_ms >= std::max(policy_->maximum_backoff_ms, + policy_->entry_lifetime_ms); + } + + // Otherwise, consider the entry is outdated if it hasn't been used for the + // specified lifetime period. + return unused_since_ms >= policy_->entry_lifetime_ms; +} + +base::TimeTicks BackoffEntry::GetTimeNow() const { + return base::TimeTicks::Now(); +} + +base::TimeTicks BackoffEntry::CalculateReleaseTime() const { + int effective_failure_count = + std::max(0, failure_count_ - policy_->num_errors_to_ignore); + if (effective_failure_count == 0) { + // Never reduce previously set release horizon, e.g. due to Retry-After + // header. + return std::max(GetTimeNow(), exponential_backoff_release_time_); + } + + // The delay is calculated with this formula: + // delay = initial_backoff * multiply_factor^( + // effective_failure_count - 1) * Uniform(1 - jitter_factor, 1] + double delay = policy_->initial_backoff_ms; + delay *= pow(policy_->multiply_factor, effective_failure_count - 1); + delay -= base::RandDouble() * policy_->jitter_factor * delay; + + // Ensure that we do not exceed maximum delay. + int64 delay_int = static_cast<int64>(delay + 0.5); + delay_int = std::min(delay_int, + static_cast<int64>(policy_->maximum_backoff_ms)); + + // Never reduce previously set release horizon, e.g. due to Retry-After + // header. + return std::max(GetTimeNow() + base::TimeDelta::FromMilliseconds(delay_int), + exponential_backoff_release_time_); +} + +} // namespace net diff --git a/net/base/backoff_entry.h b/net/base/backoff_entry.h new file mode 100644 index 0000000..6cf164d --- /dev/null +++ b/net/base/backoff_entry.h @@ -0,0 +1,94 @@ +// Copyright (c) 2011 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_BACKOFF_ITEM_H_ +#define NET_BASE_BACKOFF_ITEM_H_ +#pragma once + +#include "base/threading/non_thread_safe.h" +#include "base/time.h" + +namespace net { + +// Provides the core logic needed for randomized exponential back-off +// on requests to a given resource, given a back-off policy. +// +// This utility class knows nothing about network specifics; it is +// intended for reuse in various networking scenarios. +class BackoffEntry : public base::NonThreadSafe { + public: + // The set of parameters that define a back-off policy. + struct Policy { + // Number of initial errors (in sequence) to ignore before applying + // exponential back-off rules. + int num_errors_to_ignore; + + // Initial delay for exponential back-off. + int initial_backoff_ms; + + // Factor by which the waiting time will be multiplied. + double multiply_factor; + + // Fuzzing percentage. ex: 10% will spread requests randomly + // between 90%-100% of the calculated time. + double jitter_factor; + + // Maximum amount of time we are willing to delay our request. + int maximum_backoff_ms; + + // Time to keep an entry from being discarded even when it + // has no significant state, -1 to never discard. + int entry_lifetime_ms; + }; + + // Lifetime of policy must enclose lifetime of BackoffEntry. The + // pointer must be valid but is not dereferenced during construction. + explicit BackoffEntry(const Policy* const policy); + virtual ~BackoffEntry(); + + // Inform this item that a request for the network resource it is + // tracking was made, and whether it failed or succeeded. + void InformOfRequest(bool succeeded); + + // Returns true if a request for the resource this item tracks should + // be rejected at the present time due to exponential back-off policy. + bool ShouldRejectRequest() const; + + // Returns the absolute time after which this entry (given its present + // state) will no longer reject requests. + base::TimeTicks GetReleaseTime() const; + + // Causes this object reject requests until the specified absolute time. + // This can be used to e.g. implement support for a Retry-After header. + void SetCustomReleaseTime(const base::TimeTicks& release_time); + + // Returns true if this object has no significant state (i.e. you could + // just as well start with a fresh BackoffEntry object), and hasn't + // had for Policy::entry_lifetime_ms_. + bool CanDiscard() const; + + protected: + // Equivalent to TimeTicks::Now(), virtual so unit tests can override. + // TODO(joi): Switch to constructor-time dependency injection? + virtual base::TimeTicks GetTimeNow() const; + + private: + // Calculates when requests should again be allowed through. + base::TimeTicks CalculateReleaseTime() const; + + // Timestamp calculated by the exponential back-off algorithm at which we are + // allowed to start sending requests again. + base::TimeTicks exponential_backoff_release_time_; + + // Counts request errors; reset on success. + int failure_count_; + + const Policy* const policy_; + + DISALLOW_COPY_AND_ASSIGN(BackoffEntry); +}; + +} // namespace net + +#endif // NET_BASE_BACKOFF_ITEM_H_ diff --git a/net/base/backoff_entry_unittest.cc b/net/base/backoff_entry_unittest.cc new file mode 100644 index 0000000..cad40a6 --- /dev/null +++ b/net/base/backoff_entry_unittest.cc @@ -0,0 +1,203 @@ +// Copyright (c) 2011 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 "net/base/backoff_entry.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace { + +using base::TimeDelta; +using base::TimeTicks; +using net::BackoffEntry; + +BackoffEntry::Policy base_policy = { 0, 1000, 2.0, 0.0, 20000, 2000 }; + +class TestBackoffEntry : public BackoffEntry { + public: + explicit TestBackoffEntry(const Policy* const policy) + : BackoffEntry(policy), + now_(TimeTicks()) { + // Work around initialization in constructor not picking up + // fake time. + SetCustomReleaseTime(TimeTicks()); + } + + virtual ~TestBackoffEntry() {} + + virtual TimeTicks GetTimeNow() const { + return now_; + } + + void set_now(const TimeTicks& now) { + now_ = now; + } + + private: + TimeTicks now_; + + DISALLOW_COPY_AND_ASSIGN(TestBackoffEntry); +}; + +TEST(BackoffEntryTest, BaseTest) { + TestBackoffEntry entry(&base_policy); + EXPECT_FALSE(entry.ShouldRejectRequest()); + + entry.InformOfRequest(false); + EXPECT_TRUE(entry.ShouldRejectRequest()); +} + +TEST(BackoffEntryTest, CanDiscardNeverExpires) { + BackoffEntry::Policy never_expires_policy = base_policy; + never_expires_policy.entry_lifetime_ms = -1; + TestBackoffEntry never_expires(&never_expires_policy); + EXPECT_FALSE(never_expires.CanDiscard()); + never_expires.set_now(TimeTicks() + TimeDelta::FromDays(100)); + EXPECT_FALSE(never_expires.CanDiscard()); +} + +TEST(BackoffEntryTest, CanDiscard) { + TestBackoffEntry entry(&base_policy); + // Because lifetime is non-zero, we shouldn't be able to discard yet. + EXPECT_FALSE(entry.CanDiscard()); + + // Test the "being used" case. + entry.InformOfRequest(false); + EXPECT_FALSE(entry.CanDiscard()); + + // Test the case where there are errors but we can time out. + entry.set_now( + entry.GetReleaseTime() + TimeDelta::FromMilliseconds(1)); + EXPECT_FALSE(entry.CanDiscard()); + entry.set_now(entry.GetReleaseTime() + TimeDelta::FromMilliseconds( + base_policy.maximum_backoff_ms + 1)); + EXPECT_TRUE(entry.CanDiscard()); + + // Test the final case (no errors, dependent only on specified lifetime). + entry.set_now(entry.GetReleaseTime() + TimeDelta::FromMilliseconds( + base_policy.entry_lifetime_ms - 1)); + entry.InformOfRequest(true); + EXPECT_FALSE(entry.CanDiscard()); + entry.set_now(entry.GetReleaseTime() + TimeDelta::FromMilliseconds( + base_policy.entry_lifetime_ms)); + EXPECT_TRUE(entry.CanDiscard()); +} + +TEST(BackoffEntryTest, CanDiscardNotStored) { + BackoffEntry::Policy no_store_policy = base_policy; + no_store_policy.entry_lifetime_ms = 0; + TestBackoffEntry not_stored(&no_store_policy); + EXPECT_TRUE(not_stored.CanDiscard()); +} + +TEST(BackoffEntryTest, ShouldIgnoreFirstTwo) { + BackoffEntry::Policy lenient_policy = base_policy; + lenient_policy.num_errors_to_ignore = 2; + + BackoffEntry entry(&lenient_policy); + entry.InformOfRequest(false); + EXPECT_FALSE(entry.ShouldRejectRequest()); + entry.InformOfRequest(false); + EXPECT_FALSE(entry.ShouldRejectRequest()); + entry.InformOfRequest(false); + EXPECT_TRUE(entry.ShouldRejectRequest()); +} + +TEST(BackoffEntryTest, ReleaseTimeCalculation) { + TestBackoffEntry entry(&base_policy); + + // With zero errors, should return "now". + TimeTicks result = entry.GetReleaseTime(); + EXPECT_EQ(entry.GetTimeNow(), result); + + // 1 error. + entry.InformOfRequest(false); + result = entry.GetReleaseTime(); + EXPECT_EQ(entry.GetTimeNow() + TimeDelta::FromMilliseconds(1000), result); + + // 2 errors. + entry.InformOfRequest(false); + result = entry.GetReleaseTime(); + EXPECT_EQ(entry.GetTimeNow() + TimeDelta::FromMilliseconds(2000), result); + + // 3 errors. + entry.InformOfRequest(false); + result = entry.GetReleaseTime(); + EXPECT_EQ(entry.GetTimeNow() + TimeDelta::FromMilliseconds(4000), result); + + // 6 errors (to check it doesn't pass maximum). + entry.InformOfRequest(false); + entry.InformOfRequest(false); + entry.InformOfRequest(false); + result = entry.GetReleaseTime(); + EXPECT_EQ(entry.GetTimeNow() + TimeDelta::FromMilliseconds(20000), result); +} + +TEST(BackoffEntryTest, ReleaseTimeCalculationWithJitter) { + for (int i = 0; i < 10; ++i) { + BackoffEntry::Policy jittery_policy = base_policy; + jittery_policy.jitter_factor = 0.2; + + TestBackoffEntry entry(&jittery_policy); + + entry.InformOfRequest(false); + entry.InformOfRequest(false); + entry.InformOfRequest(false); + TimeTicks result = entry.GetReleaseTime(); + EXPECT_LE(entry.GetTimeNow() + TimeDelta::FromMilliseconds(3200), result); + EXPECT_GE(entry.GetTimeNow() + TimeDelta::FromMilliseconds(4000), result); + } +} + +TEST(BackoffEntryTest, FailureThenSuccess) { + TestBackoffEntry entry(&base_policy); + + // Failure count 1, establishes horizon. + entry.InformOfRequest(false); + TimeTicks release_time = entry.GetReleaseTime(); + EXPECT_EQ(TimeTicks() + TimeDelta::FromMilliseconds(1000), release_time); + + // Success, failure count 0, should not advance past + // the horizon that was already set. + entry.set_now(release_time - TimeDelta::FromMilliseconds(200)); + entry.InformOfRequest(true); + EXPECT_EQ(release_time, entry.GetReleaseTime()); + + // Failure, failure count 1. + entry.InformOfRequest(false); + EXPECT_EQ(release_time + TimeDelta::FromMilliseconds(800), + entry.GetReleaseTime()); +} + +TEST(BackoffEntryTest, RetainCustomHorizon) { + TestBackoffEntry custom(&base_policy); + TimeTicks custom_horizon = TimeTicks() + TimeDelta::FromDays(3); + custom.SetCustomReleaseTime(custom_horizon); + custom.InformOfRequest(false); + custom.InformOfRequest(true); + custom.set_now(TimeTicks() + TimeDelta::FromDays(2)); + custom.InformOfRequest(false); + custom.InformOfRequest(true); + EXPECT_EQ(custom_horizon, custom.GetReleaseTime()); + + // Now check that once we are at or past the custom horizon, + // we get normal behavior. + custom.set_now(TimeTicks() + TimeDelta::FromDays(3)); + custom.InformOfRequest(false); + EXPECT_EQ( + TimeTicks() + TimeDelta::FromDays(3) + TimeDelta::FromMilliseconds(1000), + custom.GetReleaseTime()); +} + +TEST(BackoffEntryTest, RetainCustomHorizonWhenInitialErrorsIgnored) { + // Regression test for a bug discovered during code review. + BackoffEntry::Policy lenient_policy = base_policy; + lenient_policy.num_errors_to_ignore = 1; + TestBackoffEntry custom(&lenient_policy); + TimeTicks custom_horizon = TimeTicks() + TimeDelta::FromDays(3); + custom.SetCustomReleaseTime(custom_horizon); + custom.InformOfRequest(false); // This must not reset the horizon. + EXPECT_EQ(custom_horizon, custom.GetReleaseTime()); +} + +} // namespace diff --git a/net/net.gyp b/net/net.gyp index 5d3ca045..3443c83 100644 --- a/net/net.gyp +++ b/net/net.gyp @@ -29,6 +29,8 @@ 'base/address_list_net_log_param.h', 'base/auth.cc', 'base/auth.h', + 'base/backoff_entry.cc', + 'base/backoff_entry.h', 'base/bandwidth_metrics.cc', 'base/bandwidth_metrics.h', 'base/cache_type.h', @@ -870,6 +872,7 @@ 'msvs_guid': 'E99DA267-BE90-4F45-88A1-6919DB2C7567', 'sources': [ 'base/address_list_unittest.cc', + 'base/backoff_entry_unittest.cc', 'base/cert_database_nss_unittest.cc', 'base/cert_verifier_unittest.cc', 'base/cookie_monster_unittest.cc', diff --git a/net/url_request/url_request_throttler_entry.cc b/net/url_request/url_request_throttler_entry.cc index 033787b..05b2af2 100644 --- a/net/url_request/url_request_throttler_entry.cc +++ b/net/url_request/url_request_throttler_entry.cc @@ -16,7 +16,6 @@ namespace net { const int URLRequestThrottlerEntry::kDefaultSlidingWindowPeriodMs = 2000; const int URLRequestThrottlerEntry::kDefaultMaxSendThreshold = 20; const int URLRequestThrottlerEntry::kDefaultInitialBackoffMs = 700; -const int URLRequestThrottlerEntry::kDefaultAdditionalConstantMs = 100; const double URLRequestThrottlerEntry::kDefaultMultiplyFactor = 1.4; const double URLRequestThrottlerEntry::kDefaultJitterFactor = 0.4; const int URLRequestThrottlerEntry::kDefaultMaximumBackoffMs = 60 * 60 * 1000; @@ -27,12 +26,7 @@ URLRequestThrottlerEntry::URLRequestThrottlerEntry() : sliding_window_period_( base::TimeDelta::FromMilliseconds(kDefaultSlidingWindowPeriodMs)), max_send_threshold_(kDefaultMaxSendThreshold), - initial_backoff_ms_(kDefaultInitialBackoffMs), - additional_constant_ms_(kDefaultAdditionalConstantMs), - multiply_factor_(kDefaultMultiplyFactor), - jitter_factor_(kDefaultJitterFactor), - maximum_backoff_ms_(kDefaultMaximumBackoffMs), - entry_lifetime_ms_(kDefaultEntryLifetimeMs) { + backoff_entry_(&backoff_policy_) { Initialize(); } @@ -40,77 +34,54 @@ URLRequestThrottlerEntry::URLRequestThrottlerEntry( int sliding_window_period_ms, int max_send_threshold, int initial_backoff_ms, - int additional_constant_ms, double multiply_factor, double jitter_factor, int maximum_backoff_ms) : sliding_window_period_( base::TimeDelta::FromMilliseconds(sliding_window_period_ms)), max_send_threshold_(max_send_threshold), - initial_backoff_ms_(initial_backoff_ms), - additional_constant_ms_(additional_constant_ms), - multiply_factor_(multiply_factor), - jitter_factor_(jitter_factor), - maximum_backoff_ms_(maximum_backoff_ms), - entry_lifetime_ms_(-1) { + backoff_entry_(&backoff_policy_) { DCHECK_GT(sliding_window_period_ms, 0); DCHECK_GT(max_send_threshold_, 0); - DCHECK_GE(initial_backoff_ms_, 0); - DCHECK_GE(additional_constant_ms_, 0); - DCHECK_GT(multiply_factor_, 0); - DCHECK_GE(jitter_factor_, 0); - DCHECK_LT(jitter_factor_, 1); - DCHECK_GE(maximum_backoff_ms_, 0); + DCHECK_GE(initial_backoff_ms, 0); + DCHECK_GT(multiply_factor, 0); + DCHECK_GE(jitter_factor, 0.0); + DCHECK_LT(jitter_factor, 1.0); + DCHECK_GE(maximum_backoff_ms, 0); Initialize(); + backoff_policy_.initial_backoff_ms = initial_backoff_ms; + backoff_policy_.multiply_factor = multiply_factor; + backoff_policy_.jitter_factor = jitter_factor; + backoff_policy_.maximum_backoff_ms = maximum_backoff_ms; + backoff_policy_.entry_lifetime_ms = -1; } bool URLRequestThrottlerEntry::IsEntryOutdated() const { - CHECK(this); // to help track crbug.com/71721 - if (entry_lifetime_ms_ == -1) - return false; - - base::TimeTicks now = GetTimeNow(); - // If there are send events in the sliding window period, we still need this // entry. if (!send_log_.empty() && - send_log_.back() + sliding_window_period_ > now) { + send_log_.back() + sliding_window_period_ > GetTimeNow()) { return false; } - int64 unused_since_ms = - (now - exponential_backoff_release_time_).InMilliseconds(); - - // Release time is further than now, we are managing it. - if (unused_since_ms < 0) - return false; - - // latest_response_was_failure_ is true indicates that the latest one or - // more requests encountered server errors or had malformed response bodies. - // In that case, we don't want to collect the entry unless it hasn't been used - // for longer than the maximum allowed back-off. - if (latest_response_was_failure_) - return unused_since_ms > std::max(maximum_backoff_ms_, entry_lifetime_ms_); - - // Otherwise, consider the entry is outdated if it hasn't been used for the - // specified lifetime period. - return unused_since_ms > entry_lifetime_ms_; + return GetBackoffEntry()->CanDiscard(); } bool URLRequestThrottlerEntry::IsDuringExponentialBackoff() const { - return exponential_backoff_release_time_ > GetTimeNow(); + return GetBackoffEntry()->ShouldRejectRequest(); } int64 URLRequestThrottlerEntry::ReserveSendingTimeForNextRequest( const base::TimeTicks& earliest_time) { base::TimeTicks now = GetTimeNow(); + // If a lot of requests were successfully made recently, // sliding_window_release_time_ may be greater than // exponential_backoff_release_time_. base::TimeTicks recommended_sending_time = std::max(std::max(now, earliest_time), - std::max(exponential_backoff_release_time_, + std::max(GetBackoffEntry()->GetReleaseTime(), sliding_window_release_time_)); DCHECK(send_log_.empty() || @@ -138,34 +109,15 @@ int64 URLRequestThrottlerEntry::ReserveSendingTimeForNextRequest( base::TimeTicks URLRequestThrottlerEntry::GetExponentialBackoffReleaseTime() const { - return exponential_backoff_release_time_; + return GetBackoffEntry()->GetReleaseTime(); } void URLRequestThrottlerEntry::UpdateWithResponse( const URLRequestThrottlerHeaderInterface* response) { if (response->GetResponseCode() >= 500) { - failure_count_++; - latest_response_was_failure_ = true; - exponential_backoff_release_time_ = - CalculateExponentialBackoffReleaseTime(); + GetBackoffEntry()->InformOfRequest(false); } else { - // We slowly decay the number of times delayed instead of resetting it to 0 - // in order to stay stable if we received lots of requests with - // malformed bodies at the same time. - if (failure_count_ > 0) - failure_count_--; - - latest_response_was_failure_ = false; - - // The reason why we are not just cutting the release time to GetTimeNow() - // is on the one hand, it would unset delay put by our custom retry-after - // header and on the other we would like to push every request up to our - // "horizon" when dealing with multiple in-flight requests. Ex: If we send - // three requests and we receive 2 failures and 1 success. The success that - // follows those failures will not reset the release time, further requests - // will then need to wait the delay caused by the 2 failures. - exponential_backoff_release_time_ = std::max( - GetTimeNow(), exponential_backoff_release_time_); + GetBackoffEntry()->InformOfRequest(true); std::string retry_header = response->GetNormalizedValue(kRetryHeaderName); if (!retry_header.empty()) @@ -174,49 +126,26 @@ void URLRequestThrottlerEntry::UpdateWithResponse( } void URLRequestThrottlerEntry::ReceivedContentWasMalformed() { - // For any response that is marked as malformed now, we have probably - // considered it as a success when receiving it and decreased the failure - // count by 1. As a result, we increase the failure count by 2 here to undo - // the effect and record a failure. + // We keep this simple and just count it as a single error. // - // Please note that this may lead to a larger failure count than expected, - // because we don't decrease the failure count for successful responses when - // it has already reached 0. - failure_count_ += 2; - latest_response_was_failure_ = true; - exponential_backoff_release_time_ = CalculateExponentialBackoffReleaseTime(); -} - -void URLRequestThrottlerEntry::SetEntryLifetimeMsForTest(int lifetime_ms) { - entry_lifetime_ms_ = lifetime_ms; + // If we wanted to get fancy, we would count two errors here, and decrease + // the error count only by one when we receive a successful (by status + // code) response. Instead, we keep things simple by always resetting the + // error count on success, and therefore counting only a single error here. + GetBackoffEntry()->InformOfRequest(false); } URLRequestThrottlerEntry::~URLRequestThrottlerEntry() { } void URLRequestThrottlerEntry::Initialize() { - // Since this method is called by the constructors, GetTimeNow() (a virtual - // method) is not used. - exponential_backoff_release_time_ = base::TimeTicks::Now(); - failure_count_ = 0; - latest_response_was_failure_ = false; - sliding_window_release_time_ = base::TimeTicks::Now(); -} - -base::TimeTicks - URLRequestThrottlerEntry::CalculateExponentialBackoffReleaseTime() { - double delay = initial_backoff_ms_; - delay *= pow(multiply_factor_, failure_count_); - delay += additional_constant_ms_; - delay -= base::RandDouble() * jitter_factor_ * delay; - - // Ensure that we do not exceed maximum delay. - int64 delay_int = static_cast<int64>(delay + 0.5); - delay_int = std::min(delay_int, static_cast<int64>(maximum_backoff_ms_)); - - return std::max(GetTimeNow() + base::TimeDelta::FromMilliseconds(delay_int), - exponential_backoff_release_time_); + backoff_policy_.num_errors_to_ignore = 0; + backoff_policy_.initial_backoff_ms = kDefaultInitialBackoffMs; + backoff_policy_.multiply_factor = kDefaultMultiplyFactor; + backoff_policy_.jitter_factor = kDefaultJitterFactor; + backoff_policy_.maximum_backoff_ms = kDefaultMaximumBackoffMs; + backoff_policy_.entry_lifetime_ms = kDefaultEntryLifetimeMs; } base::TimeTicks URLRequestThrottlerEntry::GetTimeNow() const { @@ -236,12 +165,21 @@ void URLRequestThrottlerEntry::HandleCustomRetryAfter( // We must use an int value later so we transform this in milliseconds. int64 value_ms = static_cast<int64>(0.5 + time_in_sec * 1000); - if (maximum_backoff_ms_ < value_ms || value_ms < 0) + // We do not check for an upper bound; the server can set any Retry-After it + // desires. Recovery from error would involve restarting the browser. + if (value_ms < 0) return; - exponential_backoff_release_time_ = std::max( - (GetTimeNow() + base::TimeDelta::FromMilliseconds(value_ms)), - exponential_backoff_release_time_); + GetBackoffEntry()->SetCustomReleaseTime( + GetTimeNow() + base::TimeDelta::FromMilliseconds(value_ms)); +} + +const BackoffEntry* URLRequestThrottlerEntry::GetBackoffEntry() const { + return &backoff_entry_; +} + +BackoffEntry* URLRequestThrottlerEntry::GetBackoffEntry() { + return &backoff_entry_; } } // namespace net diff --git a/net/url_request/url_request_throttler_entry.h b/net/url_request/url_request_throttler_entry.h index cefe8d2..ddea919 100644 --- a/net/url_request/url_request_throttler_entry.h +++ b/net/url_request/url_request_throttler_entry.h @@ -4,11 +4,13 @@ #ifndef NET_URL_REQUEST_URL_REQUEST_THROTTLER_ENTRY_H_ #define NET_URL_REQUEST_URL_REQUEST_THROTTLER_ENTRY_H_ +#pragma once #include <queue> #include <string> #include "base/basictypes.h" +#include "net/base/backoff_entry.h" #include "net/url_request/url_request_throttler_entry_interface.h" namespace net { @@ -35,9 +37,6 @@ class URLRequestThrottlerEntry : public URLRequestThrottlerEntryInterface { // Initial delay for exponential back-off. static const int kDefaultInitialBackoffMs; - // Additional constant to adjust back-off. - static const int kDefaultAdditionalConstantMs; - // Factor by which the waiting time will be multiplied. static const double kDefaultMultiplyFactor; @@ -63,7 +62,6 @@ class URLRequestThrottlerEntry : public URLRequestThrottlerEntryInterface { URLRequestThrottlerEntry(int sliding_window_period_ms, int max_send_threshold, int initial_backoff_ms, - int additional_constant_ms, double multiply_factor, double jitter_factor, int maximum_backoff_ms); @@ -80,27 +78,22 @@ class URLRequestThrottlerEntry : public URLRequestThrottlerEntryInterface { virtual void UpdateWithResponse( const URLRequestThrottlerHeaderInterface* response); virtual void ReceivedContentWasMalformed(); - virtual void SetEntryLifetimeMsForTest(int lifetime_ms); protected: virtual ~URLRequestThrottlerEntry(); void Initialize(); - // Calculates the release time for exponential back-off. - base::TimeTicks CalculateExponentialBackoffReleaseTime(); - // Equivalent to TimeTicks::Now(), virtual to be mockable for testing purpose. virtual base::TimeTicks GetTimeNow() const; // Used internally to increase release time following a retry-after header. void HandleCustomRetryAfter(const std::string& header_value); - // Used by tests. - void set_exponential_backoff_release_time( - const base::TimeTicks& release_time) { - exponential_backoff_release_time_ = release_time; - } + // Retrieves the backoff entry object we're using. Used to enable a + // unit testing seam for dependency injection in tests. + virtual const BackoffEntry* GetBackoffEntry() const; + virtual BackoffEntry* GetBackoffEntry(); // Used by tests. base::TimeTicks sliding_window_release_time() const { @@ -112,25 +105,10 @@ class URLRequestThrottlerEntry : public URLRequestThrottlerEntryInterface { sliding_window_release_time_ = release_time; } - // Used by tests. - void set_failure_count(int failure_count) { - failure_count_ = failure_count; - } + // Valid and immutable after construction time. + BackoffEntry::Policy backoff_policy_; private: - // Timestamp calculated by the exponential back-off algorithm at which we are - // allowed to start sending requests again. - base::TimeTicks exponential_backoff_release_time_; - - // Number of times we encounter server errors or malformed response bodies. - int failure_count_; - - // If true, the last request response was a failure. - // Note that this member can be false at the same time as failure_count_ can - // be greater than 0, since we gradually decrease failure_count_, instead of - // resetting it to 0 directly, when we receive successful responses. - bool latest_response_was_failure_; - // Timestamp calculated by the sliding window algorithm for when we advise // clients the next request should be made, at the earliest. Advisory only, // not used to deny requests. @@ -142,13 +120,9 @@ class URLRequestThrottlerEntry : public URLRequestThrottlerEntryInterface { const base::TimeDelta sliding_window_period_; const int max_send_threshold_; - const int initial_backoff_ms_; - const int additional_constant_ms_; - const double multiply_factor_; - const double jitter_factor_; - const int maximum_backoff_ms_; - // Set to -1 if the entry never expires. - int entry_lifetime_ms_; + + // Access it through GetBackoffEntry() to allow a unit test seam. + BackoffEntry backoff_entry_; DISALLOW_COPY_AND_ASSIGN(URLRequestThrottlerEntry); }; diff --git a/net/url_request/url_request_throttler_entry_interface.h b/net/url_request/url_request_throttler_entry_interface.h index e3fc5ba..63dd14c 100644 --- a/net/url_request/url_request_throttler_entry_interface.h +++ b/net/url_request/url_request_throttler_entry_interface.h @@ -4,6 +4,7 @@ #ifndef NET_URL_REQUEST_URL_REQUEST_THROTTLER_ENTRY_INTERFACE_H_ #define NET_URL_REQUEST_URL_REQUEST_THROTTLER_ENTRY_INTERFACE_H_ +#pragma once #include "base/basictypes.h" #include "base/ref_counted.h" @@ -50,9 +51,6 @@ class URLRequestThrottlerEntryInterface // the request, i.e. it will count as a failure. virtual void ReceivedContentWasMalformed() = 0; - // For unit testing only. - virtual void SetEntryLifetimeMsForTest(int lifetime_ms) = 0; - protected: friend class base::RefCountedThreadSafe<URLRequestThrottlerEntryInterface>; virtual ~URLRequestThrottlerEntryInterface() {} diff --git a/net/url_request/url_request_throttler_header_adapter.h b/net/url_request/url_request_throttler_header_adapter.h index 35d363e..a360747 100644 --- a/net/url_request/url_request_throttler_header_adapter.h +++ b/net/url_request/url_request_throttler_header_adapter.h @@ -4,6 +4,7 @@ #ifndef NET_URL_REQUEST_URL_REQUEST_THROTTLER_HEADER_ADAPTER_H_ #define NET_URL_REQUEST_URL_REQUEST_THROTTLER_HEADER_ADAPTER_H_ +#pragma once #include <string> diff --git a/net/url_request/url_request_throttler_manager.h b/net/url_request/url_request_throttler_manager.h index d1ede1d..1cd2b5c 100644 --- a/net/url_request/url_request_throttler_manager.h +++ b/net/url_request/url_request_throttler_manager.h @@ -4,6 +4,7 @@ #ifndef NET_URL_REQUEST_URL_REQUEST_THROTTLER_MANAGER_H_ #define NET_URL_REQUEST_URL_REQUEST_THROTTLER_MANAGER_H_ +#pragma once #include <map> #include <string> diff --git a/net/url_request/url_request_throttler_unittest.cc b/net/url_request/url_request_throttler_unittest.cc index 7d4e739..4aed38c 100644 --- a/net/url_request/url_request_throttler_unittest.cc +++ b/net/url_request/url_request_throttler_unittest.cc @@ -19,23 +19,61 @@ using base::TimeTicks; namespace { class MockURLRequestThrottlerManager; +class MockBackoffEntry : public net::BackoffEntry { + public: + explicit MockBackoffEntry(const net::BackoffEntry::Policy* const policy) + : net::BackoffEntry(policy), fake_now_(TimeTicks()) { + } + + virtual ~MockBackoffEntry() {} + + TimeTicks GetTimeNow() const { + return fake_now_; + } + + void SetFakeNow(TimeTicks now) { + fake_now_ = now; + } + + private: + TimeTicks fake_now_; +}; + class MockURLRequestThrottlerEntry : public net::URLRequestThrottlerEntry { public : - MockURLRequestThrottlerEntry() {} + MockURLRequestThrottlerEntry() : mock_backoff_entry_(&backoff_policy_) { + // Some tests become flaky if we have jitter. + backoff_policy_.jitter_factor = 0.0; + } MockURLRequestThrottlerEntry( const TimeTicks& exponential_backoff_release_time, const TimeTicks& sliding_window_release_time, const TimeTicks& fake_now) - : fake_time_now_(fake_now) { + : fake_time_now_(fake_now), + mock_backoff_entry_(&backoff_policy_) { + // Some tests become flaky if we have jitter. + backoff_policy_.jitter_factor = 0.0; + + mock_backoff_entry_.SetFakeNow(fake_now); set_exponential_backoff_release_time(exponential_backoff_release_time); set_sliding_window_release_time(sliding_window_release_time); } virtual ~MockURLRequestThrottlerEntry() {} + const net::BackoffEntry* GetBackoffEntry() const { + return &mock_backoff_entry_; + } + + net::BackoffEntry* GetBackoffEntry() { + return &mock_backoff_entry_; + } + void ResetToBlank(const TimeTicks& time_now) { fake_time_now_ = time_now; - set_exponential_backoff_release_time(time_now); - set_failure_count(0); + mock_backoff_entry_.SetFakeNow(time_now); + + GetBackoffEntry()->InformOfRequest(true); // Sets failure count to 0. + GetBackoffEntry()->SetCustomReleaseTime(time_now); set_sliding_window_release_time(time_now); } @@ -44,8 +82,7 @@ class MockURLRequestThrottlerEntry : public net::URLRequestThrottlerEntry { void set_exponential_backoff_release_time( const base::TimeTicks& release_time) { - net::URLRequestThrottlerEntry::set_exponential_backoff_release_time( - release_time); + GetBackoffEntry()->SetCustomReleaseTime(release_time); } base::TimeTicks sliding_window_release_time() const { @@ -59,6 +96,7 @@ class MockURLRequestThrottlerEntry : public net::URLRequestThrottlerEntry { } TimeTicks fake_time_now_; + MockBackoffEntry mock_backoff_entry_; }; class MockURLRequestThrottlerHeaderAdapter @@ -226,7 +264,8 @@ TEST_F(URLRequestThrottlerEntryTest, IsEntryReallyOutdated) { TimeAndBool(now_, false, __LINE__), TimeAndBool(now_ - kFiveMs, false, __LINE__), TimeAndBool(now_ + kFiveMs, false, __LINE__), - TimeAndBool(now_ - lifetime, false, __LINE__), + TimeAndBool(now_ - (lifetime - kFiveMs), false, __LINE__), + TimeAndBool(now_ - lifetime, true, __LINE__), TimeAndBool(now_ - (lifetime + kFiveMs), true, __LINE__)}; for (unsigned int i = 0; i < arraysize(test_values); ++i) { @@ -352,59 +391,7 @@ TEST(URLRequestThrottlerManager, IsHostBeingRegistered) { EXPECT_EQ(3, manager.GetNumberOfEntries()); } -class DummyResponseHeaders : public net::URLRequestThrottlerHeaderInterface { - public: - DummyResponseHeaders(int response_code) : response_code_(response_code) {} - - std::string GetNormalizedValue(const std::string& key) const { - return ""; - } - - // Returns the HTTP response code associated with the request. - int GetResponseCode() const { - return response_code_; - } - - private: - int response_code_; -}; - -TEST(URLRequestThrottlerManager, StressTest) { - MockURLRequestThrottlerManager manager; - - for (int i = 0; i < 10000; ++i) { - // Make some entries duplicates or triplicates. - int entry_number = i + 2; - if (i % 17 == 0) { - entry_number = i - 1; - } else if ((i - 1) % 17 == 0) { - entry_number = i - 2; - } else if (i % 13 == 0) { - entry_number = i - 1; - } - - scoped_refptr<net::URLRequestThrottlerEntryInterface> entry = - manager.RegisterRequestUrl(GURL(StringPrintf( - "http://bingourl.com/%d", entry_number))); - entry->IsDuringExponentialBackoff(); - entry->GetExponentialBackoffReleaseTime(); - - DummyResponseHeaders headers(i % 7 == 0 ? 500 : 200); - entry->UpdateWithResponse(&headers); - entry->SetEntryLifetimeMsForTest(1); - - entry->IsDuringExponentialBackoff(); - entry->GetExponentialBackoffReleaseTime(); - entry->ReserveSendingTimeForNextRequest(base::TimeTicks::Now()); - - if (i % 11 == 0) { - manager.DoGarbageCollectEntries(); - } - } -} - -// TODO(joi): Remove the debug-only condition after M11 branch point. -#if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG) +#if defined(GTEST_HAS_DEATH_TEST) TEST(URLRequestThrottlerManager, NullHandlingTest) { MockURLRequestThrottlerManager manager; manager.OverrideEntryForTests(GURL("http://www.foo.com/"), NULL); @@ -412,4 +399,4 @@ TEST(URLRequestThrottlerManager, NullHandlingTest) { manager.DoGarbageCollectEntries(); }, ""); } -#endif // defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG) +#endif // defined(GTEST_HAS_DEATH_TEST) |