1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "net/base/backoff_entry.h" 6 7 #include <algorithm> 8 #include <cmath> 9 #include <limits> 10 11 #include "base/basictypes.h" 12 #include "base/logging.h" 13 #include "base/numerics/safe_math.h" 14 #include "base/rand_util.h" 15 16 namespace net { 17 18 BackoffEntry::BackoffEntry(const BackoffEntry::Policy* const policy) 19 : policy_(policy) { 20 DCHECK(policy_); 21 Reset(); 22 } 23 24 BackoffEntry::~BackoffEntry() { 25 // TODO(joi): Remove this once our clients (e.g. URLRequestThrottlerManager) 26 // always destroy from the I/O thread. 27 DetachFromThread(); 28 } 29 30 void BackoffEntry::InformOfRequest(bool succeeded) { 31 if (!succeeded) { 32 ++failure_count_; 33 exponential_backoff_release_time_ = CalculateReleaseTime(); 34 } else { 35 // We slowly decay the number of times delayed instead of 36 // resetting it to 0 in order to stay stable if we receive 37 // successes interleaved between lots of failures. Note that in 38 // the normal case, the calculated release time (in the next 39 // statement) will be in the past once the method returns. 40 if (failure_count_ > 0) 41 --failure_count_; 42 43 // The reason why we are not just cutting the release time to 44 // ImplGetTimeNow() is on the one hand, it would unset a release 45 // time set by SetCustomReleaseTime and on the other we would like 46 // to push every request up to our "horizon" when dealing with 47 // multiple in-flight requests. Ex: If we send three requests and 48 // we receive 2 failures and 1 success. The success that follows 49 // those failures will not reset the release time, further 50 // requests will then need to wait the delay caused by the 2 51 // failures. 52 base::TimeDelta delay; 53 if (policy_->always_use_initial_delay) 54 delay = base::TimeDelta::FromMilliseconds(policy_->initial_delay_ms); 55 exponential_backoff_release_time_ = std::max( 56 ImplGetTimeNow() + delay, exponential_backoff_release_time_); 57 } 58 } 59 60 bool BackoffEntry::ShouldRejectRequest() const { 61 return exponential_backoff_release_time_ > ImplGetTimeNow(); 62 } 63 64 base::TimeDelta BackoffEntry::GetTimeUntilRelease() const { 65 base::TimeTicks now = ImplGetTimeNow(); 66 if (exponential_backoff_release_time_ <= now) 67 return base::TimeDelta(); 68 return exponential_backoff_release_time_ - now; 69 } 70 71 base::TimeTicks BackoffEntry::GetReleaseTime() const { 72 return exponential_backoff_release_time_; 73 } 74 75 void BackoffEntry::SetCustomReleaseTime(const base::TimeTicks& release_time) { 76 exponential_backoff_release_time_ = release_time; 77 } 78 79 bool BackoffEntry::CanDiscard() const { 80 if (policy_->entry_lifetime_ms == -1) 81 return false; 82 83 base::TimeTicks now = ImplGetTimeNow(); 84 85 int64 unused_since_ms = 86 (now - exponential_backoff_release_time_).InMilliseconds(); 87 88 // Release time is further than now, we are managing it. 89 if (unused_since_ms < 0) 90 return false; 91 92 if (failure_count_ > 0) { 93 // Need to keep track of failures until maximum back-off period 94 // has passed (since further failures can add to back-off). 95 return unused_since_ms >= std::max(policy_->maximum_backoff_ms, 96 policy_->entry_lifetime_ms); 97 } 98 99 // Otherwise, consider the entry is outdated if it hasn't been used for the 100 // specified lifetime period. 101 return unused_since_ms >= policy_->entry_lifetime_ms; 102 } 103 104 void BackoffEntry::Reset() { 105 failure_count_ = 0; 106 107 // We leave exponential_backoff_release_time_ unset, meaning 0. We could 108 // initialize to ImplGetTimeNow() but because it's a virtual method it's 109 // not safe to call in the constructor (and the constructor calls Reset()). 110 // The effects are the same, i.e. ShouldRejectRequest() will return false 111 // right after Reset(). 112 exponential_backoff_release_time_ = base::TimeTicks(); 113 } 114 115 base::TimeTicks BackoffEntry::ImplGetTimeNow() const { 116 return base::TimeTicks::Now(); 117 } 118 119 base::TimeTicks BackoffEntry::CalculateReleaseTime() const { 120 int effective_failure_count = 121 std::max(0, failure_count_ - policy_->num_errors_to_ignore); 122 123 // If always_use_initial_delay is true, it's equivalent to 124 // the effective_failure_count always being one greater than when it's false. 125 if (policy_->always_use_initial_delay) 126 ++effective_failure_count; 127 128 if (effective_failure_count == 0) { 129 // Never reduce previously set release horizon, e.g. due to Retry-After 130 // header. 131 return std::max(ImplGetTimeNow(), exponential_backoff_release_time_); 132 } 133 134 // The delay is calculated with this formula: 135 // delay = initial_backoff * multiply_factor^( 136 // effective_failure_count - 1) * Uniform(1 - jitter_factor, 1] 137 // Note: if the failure count is too high, |delay_ms| will become infinity 138 // after the exponential calculation, and then NaN after the jitter is 139 // accounted for. Both cases are handled by using CheckedNumeric<int64> to 140 // perform the conversion to integers. 141 double delay_ms = policy_->initial_delay_ms; 142 delay_ms *= pow(policy_->multiply_factor, effective_failure_count - 1); 143 delay_ms -= base::RandDouble() * policy_->jitter_factor * delay_ms; 144 145 // Do overflow checking in microseconds, the internal unit of TimeTicks. 146 const int64 kTimeTicksNowUs = 147 (ImplGetTimeNow() - base::TimeTicks()).InMicroseconds(); 148 base::internal::CheckedNumeric<int64> calculated_release_time_us = 149 delay_ms + 0.5; 150 calculated_release_time_us *= base::Time::kMicrosecondsPerMillisecond; 151 calculated_release_time_us += kTimeTicksNowUs; 152 153 base::internal::CheckedNumeric<int64> maximum_release_time_us = kint64max; 154 if (policy_->maximum_backoff_ms >= 0) { 155 maximum_release_time_us = policy_->maximum_backoff_ms; 156 maximum_release_time_us *= base::Time::kMicrosecondsPerMillisecond; 157 maximum_release_time_us += kTimeTicksNowUs; 158 } 159 160 // Decide between maximum release time and calculated release time, accounting 161 // for overflow with both. 162 int64 release_time_us = std::min( 163 calculated_release_time_us.ValueOrDefault(kint64max), 164 maximum_release_time_us.ValueOrDefault(kint64max)); 165 166 // Never reduce previously set release horizon, e.g. due to Retry-After 167 // header. 168 return std::max( 169 base::TimeTicks() + base::TimeDelta::FromMicroseconds(release_time_us), 170 exponential_backoff_release_time_); 171 } 172 173 } // namespace net 174