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
16namespace net {
17
18BackoffEntry::BackoffEntry(const BackoffEntry::Policy* const policy)
19    : policy_(policy) {
20  DCHECK(policy_);
21  Reset();
22}
23
24BackoffEntry::~BackoffEntry() {
25  // TODO(joi): Remove this once our clients (e.g. URLRequestThrottlerManager)
26  // always destroy from the I/O thread.
27  DetachFromThread();
28}
29
30void 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
60bool BackoffEntry::ShouldRejectRequest() const {
61  return exponential_backoff_release_time_ > ImplGetTimeNow();
62}
63
64base::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
71base::TimeTicks BackoffEntry::GetReleaseTime() const {
72  return exponential_backoff_release_time_;
73}
74
75void BackoffEntry::SetCustomReleaseTime(const base::TimeTicks& release_time) {
76  exponential_backoff_release_time_ = release_time;
77}
78
79bool 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
104void 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
115base::TimeTicks BackoffEntry::ImplGetTimeNow() const {
116  return base::TimeTicks::Now();
117}
118
119base::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