Home | History | Annotate | Download | only in base 
      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