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/logging.h"
  12 #include "base/rand_util.h"
  13
  14 namespace net {
  15
  16 BackoffEntry::BackoffEntry(const BackoffEntry::Policy* const policy)
  17     : policy_(policy) {
  18   DCHECK(policy_);
  19   Reset();
  20 }
  21
  22 BackoffEntry::~BackoffEntry() {
  23   // TODO(joi): Remove this once our clients (e.g. URLRequestThrottlerManager)
  24   // always destroy from the I/O thread.
  25   DetachFromThread();
  26 }
  27
  28 void BackoffEntry::InformOfRequest(bool succeeded) {
  29   if (!succeeded) {
  30     ++failure_count_;
  31     exponential_backoff_release_time_ = CalculateReleaseTime();
  32   } else {
  33     // We slowly decay the number of times delayed instead of
  34     // resetting it to 0 in order to stay stable if we receive
  35     // successes interleaved between lots of failures.  Note that in
  36     // the normal case, the calculated release time (in the next
  37     // statement) will be in the past once the method returns.
  38     if (failure_count_ > 0)
  39       --failure_count_;
  40
  41     // The reason why we are not just cutting the release time to
  42     // ImplGetTimeNow() is on the one hand, it would unset a release
  43     // time set by SetCustomReleaseTime and on the other we would like
  44     // to push every request up to our "horizon" when dealing with
  45     // multiple in-flight requests. Ex: If we send three requests and
  46     // we receive 2 failures and 1 success. The success that follows
  47     // those failures will not reset the release time, further
  48     // requests will then need to wait the delay caused by the 2
  49     // failures.
  50     base::TimeDelta delay;
  51     if (policy_->always_use_initial_delay)
  52       delay = base::TimeDelta::FromMilliseconds(policy_->initial_delay_ms);
  53     exponential_backoff_release_time_ = std::max(
  54         ImplGetTimeNow() + delay, exponential_backoff_release_time_);
  55   }
  56 }
  57
  58 bool BackoffEntry::ShouldRejectRequest() const {
  59   return exponential_backoff_release_time_ > ImplGetTimeNow();
  60 }
  61
  62 base::TimeDelta BackoffEntry::GetTimeUntilRelease() const {
  63   base::TimeTicks now = ImplGetTimeNow();
  64   if (exponential_backoff_release_time_ <= now)
  65     return base::TimeDelta();
  66   return exponential_backoff_release_time_ - now;
  67 }
  68
  69 base::TimeTicks BackoffEntry::GetReleaseTime() const {
  70   return exponential_backoff_release_time_;
  71 }
  72
  73 void BackoffEntry::SetCustomReleaseTime(const base::TimeTicks& release_time) {
  74   exponential_backoff_release_time_ = release_time;
  75 }
  76
  77 bool BackoffEntry::CanDiscard() const {
  78   if (policy_->entry_lifetime_ms == -1)
  79     return false;
  80
  81   base::TimeTicks now = ImplGetTimeNow();
  82
  83   int64 unused_since_ms =
  84       (now - exponential_backoff_release_time_).InMilliseconds();
  85
  86   // Release time is further than now, we are managing it.
  87   if (unused_since_ms < 0)
  88     return false;
  89
  90   if (failure_count_ > 0) {
  91     // Need to keep track of failures until maximum back-off period
  92     // has passed (since further failures can add to back-off).
  93     return unused_since_ms >= std::max(policy_->maximum_backoff_ms,
  94                                        policy_->entry_lifetime_ms);
  95   }
  96
  97   // Otherwise, consider the entry is outdated if it hasn't been used for the
  98   // specified lifetime period.
  99   return unused_since_ms >= policy_->entry_lifetime_ms;
 100 }
 101
 102 void BackoffEntry::Reset() {
 103   failure_count_ = 0;
 104
 105   // We leave exponential_backoff_release_time_ unset, meaning 0. We could
 106   // initialize to ImplGetTimeNow() but because it's a virtual method it's
 107   // not safe to call in the constructor (and the constructor calls Reset()).
 108   // The effects are the same, i.e. ShouldRejectRequest() will return false
 109   // right after Reset().
 110   exponential_backoff_release_time_ = base::TimeTicks();
 111 }
 112
 113 base::TimeTicks BackoffEntry::ImplGetTimeNow() const {
 114   return base::TimeTicks::Now();
 115 }
 116
 117 base::TimeTicks BackoffEntry::CalculateReleaseTime() const {
 118   int effective_failure_count =
 119       std::max(0, failure_count_ - policy_->num_errors_to_ignore);
 120
 121   // If always_use_initial_delay is true, it's equivalent to
 122   // the effective_failure_count always being one greater than when it's false.
 123   if (policy_->always_use_initial_delay)
 124     ++effective_failure_count;
 125
 126   if (effective_failure_count == 0) {
 127     // Never reduce previously set release horizon, e.g. due to Retry-After
 128     // header.
 129     return std::max(ImplGetTimeNow(), exponential_backoff_release_time_);
 130   }
 131
 132   // The delay is calculated with this formula:
 133   // delay = initial_backoff * multiply_factor^(
 134   //     effective_failure_count - 1) * Uniform(1 - jitter_factor, 1]
 135   double delay = policy_->initial_delay_ms;
 136   delay *= pow(policy_->multiply_factor, effective_failure_count - 1);
 137   delay -= base::RandDouble() * policy_->jitter_factor * delay;
 138
 139   const int64 kMaxInt64 = std::numeric_limits<int64>::max();
 140   int64 delay_int = (delay > kMaxInt64) ?
 141       kMaxInt64 : static_cast<int64>(delay + 0.5);
 142
 143   // Ensure that we do not exceed maximum delay.
 144   if (policy_->maximum_backoff_ms >= 0)
 145     delay_int = std::min(delay_int, policy_->maximum_backoff_ms);
 146
 147   // Never reduce previously set release horizon, e.g. due to Retry-After
 148   // header.
 149   return std::max(
 150       ImplGetTimeNow() + base::TimeDelta::FromMilliseconds(delay_int),
 151       exponential_backoff_release_time_);
 152 }
 153
 154 }  // namespace net