net/base/backoff_entry.cc

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