15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "net/base/backoff_entry.h" 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <cmath> 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <limits> 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include "base/basictypes.h" 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 13f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles)#include "base/numerics/safe_math.h" 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/rand_util.h" 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace net { 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BackoffEntry::BackoffEntry(const BackoffEntry::Policy* const policy) 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : policy_(policy) { 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(policy_); 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Reset(); 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BackoffEntry::~BackoffEntry() { 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO(joi): Remove this once our clients (e.g. URLRequestThrottlerManager) 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // always destroy from the I/O thread. 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DetachFromThread(); 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BackoffEntry::InformOfRequest(bool succeeded) { 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!succeeded) { 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++failure_count_; 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) exponential_backoff_release_time_ = CalculateReleaseTime(); 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We slowly decay the number of times delayed instead of 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // resetting it to 0 in order to stay stable if we receive 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // successes interleaved between lots of failures. Note that in 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the normal case, the calculated release time (in the next 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // statement) will be in the past once the method returns. 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (failure_count_ > 0) 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --failure_count_; 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The reason why we are not just cutting the release time to 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ImplGetTimeNow() is on the one hand, it would unset a release 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // time set by SetCustomReleaseTime and on the other we would like 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to push every request up to our "horizon" when dealing with 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // multiple in-flight requests. Ex: If we send three requests and 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // we receive 2 failures and 1 success. The success that follows 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // those failures will not reset the release time, further 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // requests will then need to wait the delay caused by the 2 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // failures. 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::TimeDelta delay; 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (policy_->always_use_initial_delay) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delay = base::TimeDelta::FromMilliseconds(policy_->initial_delay_ms); 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) exponential_backoff_release_time_ = std::max( 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ImplGetTimeNow() + delay, exponential_backoff_release_time_); 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool BackoffEntry::ShouldRejectRequest() const { 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return exponential_backoff_release_time_ > ImplGetTimeNow(); 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)base::TimeDelta BackoffEntry::GetTimeUntilRelease() const { 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::TimeTicks now = ImplGetTimeNow(); 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (exponential_backoff_release_time_ <= now) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return base::TimeDelta(); 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return exponential_backoff_release_time_ - now; 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)base::TimeTicks BackoffEntry::GetReleaseTime() const { 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return exponential_backoff_release_time_; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BackoffEntry::SetCustomReleaseTime(const base::TimeTicks& release_time) { 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) exponential_backoff_release_time_ = release_time; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool BackoffEntry::CanDiscard() const { 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (policy_->entry_lifetime_ms == -1) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::TimeTicks now = ImplGetTimeNow(); 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 unused_since_ms = 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (now - exponential_backoff_release_time_).InMilliseconds(); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Release time is further than now, we are managing it. 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (unused_since_ms < 0) 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (failure_count_ > 0) { 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Need to keep track of failures until maximum back-off period 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // has passed (since further failures can add to back-off). 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return unused_since_ms >= std::max(policy_->maximum_backoff_ms, 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) policy_->entry_lifetime_ms); 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Otherwise, consider the entry is outdated if it hasn't been used for the 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // specified lifetime period. 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return unused_since_ms >= policy_->entry_lifetime_ms; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BackoffEntry::Reset() { 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) failure_count_ = 0; 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We leave exponential_backoff_release_time_ unset, meaning 0. We could 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // initialize to ImplGetTimeNow() but because it's a virtual method it's 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // not safe to call in the constructor (and the constructor calls Reset()). 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The effects are the same, i.e. ShouldRejectRequest() will return false 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // right after Reset(). 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) exponential_backoff_release_time_ = base::TimeTicks(); 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)base::TimeTicks BackoffEntry::ImplGetTimeNow() const { 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return base::TimeTicks::Now(); 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)base::TimeTicks BackoffEntry::CalculateReleaseTime() const { 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int effective_failure_count = 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::max(0, failure_count_ - policy_->num_errors_to_ignore); 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If always_use_initial_delay is true, it's equivalent to 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the effective_failure_count always being one greater than when it's false. 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (policy_->always_use_initial_delay) 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++effective_failure_count; 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (effective_failure_count == 0) { 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Never reduce previously set release horizon, e.g. due to Retry-After 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // header. 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return std::max(ImplGetTimeNow(), exponential_backoff_release_time_); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The delay is calculated with this formula: 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // delay = initial_backoff * multiply_factor^( 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // effective_failure_count - 1) * Uniform(1 - jitter_factor, 1] 137f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // Note: if the failure count is too high, |delay_ms| will become infinity 138f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // after the exponential calculation, and then NaN after the jitter is 139f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // accounted for. Both cases are handled by using CheckedNumeric<int64> to 140f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // perform the conversion to integers. 141f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) double delay_ms = policy_->initial_delay_ms; 142f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) delay_ms *= pow(policy_->multiply_factor, effective_failure_count - 1); 143f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) delay_ms -= base::RandDouble() * policy_->jitter_factor * delay_ms; 144f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 145f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // Do overflow checking in microseconds, the internal unit of TimeTicks. 146f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) const int64 kTimeTicksNowUs = 147f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) (ImplGetTimeNow() - base::TimeTicks()).InMicroseconds(); 148f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) base::internal::CheckedNumeric<int64> calculated_release_time_us = 149f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) delay_ms + 0.5; 150f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) calculated_release_time_us *= base::Time::kMicrosecondsPerMillisecond; 151f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) calculated_release_time_us += kTimeTicksNowUs; 152f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) 153f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) base::internal::CheckedNumeric<int64> maximum_release_time_us = kint64max; 154f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) if (policy_->maximum_backoff_ms >= 0) { 155f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) maximum_release_time_us = policy_->maximum_backoff_ms; 156f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) maximum_release_time_us *= base::Time::kMicrosecondsPerMillisecond; 157f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) maximum_release_time_us += kTimeTicksNowUs; 158f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 160f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // Decide between maximum release time and calculated release time, accounting 161f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) // for overflow with both. 162f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) int64 release_time_us = std::min( 163f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) calculated_release_time_us.ValueOrDefault(kint64max), 164f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) maximum_release_time_us.ValueOrDefault(kint64max)); 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Never reduce previously set release horizon, e.g. due to Retry-After 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // header. 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return std::max( 169f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) base::TimeTicks() + base::TimeDelta::FromMicroseconds(release_time_us), 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) exponential_backoff_release_time_); 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace net 174