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