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) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/rand_util.h" 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace net { 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BackoffEntry::BackoffEntry(const BackoffEntry::Policy* const policy) 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : policy_(policy) { 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(policy_); 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Reset(); 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BackoffEntry::~BackoffEntry() { 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO(joi): Remove this once our clients (e.g. URLRequestThrottlerManager) 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // always destroy from the I/O thread. 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DetachFromThread(); 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BackoffEntry::InformOfRequest(bool succeeded) { 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!succeeded) { 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++failure_count_; 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) exponential_backoff_release_time_ = CalculateReleaseTime(); 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We slowly decay the number of times delayed instead of 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // resetting it to 0 in order to stay stable if we receive 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // successes interleaved between lots of failures. Note that in 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the normal case, the calculated release time (in the next 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // statement) will be in the past once the method returns. 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (failure_count_ > 0) 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --failure_count_; 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The reason why we are not just cutting the release time to 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ImplGetTimeNow() is on the one hand, it would unset a release 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // time set by SetCustomReleaseTime and on the other we would like 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to push every request up to our "horizon" when dealing with 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // multiple in-flight requests. Ex: If we send three requests and 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // we receive 2 failures and 1 success. The success that follows 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // those failures will not reset the release time, further 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // requests will then need to wait the delay caused by the 2 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // failures. 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::TimeDelta delay; 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (policy_->always_use_initial_delay) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delay = base::TimeDelta::FromMilliseconds(policy_->initial_delay_ms); 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) exponential_backoff_release_time_ = std::max( 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ImplGetTimeNow() + delay, exponential_backoff_release_time_); 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool BackoffEntry::ShouldRejectRequest() const { 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return exponential_backoff_release_time_ > ImplGetTimeNow(); 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)base::TimeDelta BackoffEntry::GetTimeUntilRelease() const { 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::TimeTicks now = ImplGetTimeNow(); 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (exponential_backoff_release_time_ <= now) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return base::TimeDelta(); 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return exponential_backoff_release_time_ - now; 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)base::TimeTicks BackoffEntry::GetReleaseTime() const { 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return exponential_backoff_release_time_; 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BackoffEntry::SetCustomReleaseTime(const base::TimeTicks& release_time) { 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) exponential_backoff_release_time_ = release_time; 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool BackoffEntry::CanDiscard() const { 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (policy_->entry_lifetime_ms == -1) 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::TimeTicks now = ImplGetTimeNow(); 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 unused_since_ms = 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (now - exponential_backoff_release_time_).InMilliseconds(); 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Release time is further than now, we are managing it. 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (unused_since_ms < 0) 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (failure_count_ > 0) { 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Need to keep track of failures until maximum back-off period 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // has passed (since further failures can add to back-off). 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return unused_since_ms >= std::max(policy_->maximum_backoff_ms, 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) policy_->entry_lifetime_ms); 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Otherwise, consider the entry is outdated if it hasn't been used for the 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // specified lifetime period. 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return unused_since_ms >= policy_->entry_lifetime_ms; 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BackoffEntry::Reset() { 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) failure_count_ = 0; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We leave exponential_backoff_release_time_ unset, meaning 0. We could 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // initialize to ImplGetTimeNow() but because it's a virtual method it's 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // not safe to call in the constructor (and the constructor calls Reset()). 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The effects are the same, i.e. ShouldRejectRequest() will return false 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // right after Reset(). 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) exponential_backoff_release_time_ = base::TimeTicks(); 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)base::TimeTicks BackoffEntry::ImplGetTimeNow() const { 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return base::TimeTicks::Now(); 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)base::TimeTicks BackoffEntry::CalculateReleaseTime() const { 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int effective_failure_count = 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::max(0, failure_count_ - policy_->num_errors_to_ignore); 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If always_use_initial_delay is true, it's equivalent to 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the effective_failure_count always being one greater than when it's false. 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (policy_->always_use_initial_delay) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++effective_failure_count; 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (effective_failure_count == 0) { 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Never reduce previously set release horizon, e.g. due to Retry-After 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // header. 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return std::max(ImplGetTimeNow(), exponential_backoff_release_time_); 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The delay is calculated with this formula: 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // delay = initial_backoff * multiply_factor^( 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // effective_failure_count - 1) * Uniform(1 - jitter_factor, 1] 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double delay = policy_->initial_delay_ms; 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delay *= pow(policy_->multiply_factor, effective_failure_count - 1); 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delay -= base::RandDouble() * policy_->jitter_factor * delay; 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int64 kMaxInt64 = std::numeric_limits<int64>::max(); 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 delay_int = (delay > kMaxInt64) ? 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) kMaxInt64 : static_cast<int64>(delay + 0.5); 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Ensure that we do not exceed maximum delay. 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (policy_->maximum_backoff_ms >= 0) 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delay_int = std::min(delay_int, policy_->maximum_backoff_ms); 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Never reduce previously set release horizon, e.g. due to Retry-After 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // header. 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return std::max( 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ImplGetTimeNow() + base::TimeDelta::FromMilliseconds(delay_int), 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) exponential_backoff_release_time_); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace net 155