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
|
// 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/rand_util.h"
namespace net {
BackoffEntry::BackoffEntry(const BackoffEntry::Policy* const policy)
: policy_(policy) {
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
// ImplGetTimeNow() 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(
ImplGetTimeNow() + delay, exponential_backoff_release_time_);
}
}
bool BackoffEntry::ShouldRejectRequest() const {
return exponential_backoff_release_time_ > ImplGetTimeNow();
}
base::TimeDelta BackoffEntry::GetTimeUntilRelease() const {
base::TimeTicks now = ImplGetTimeNow();
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 = ImplGetTimeNow();
int64 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;
// We leave exponential_backoff_release_time_ unset, meaning 0. We could
// initialize to ImplGetTimeNow() but because it's a virtual method it's
// not safe to call in the constructor (and the constructor calls Reset()).
// The effects are the same, i.e. ShouldRejectRequest() will return false
// right after Reset().
exponential_backoff_release_time_ = base::TimeTicks();
}
base::TimeTicks BackoffEntry::ImplGetTimeNow() const {
return base::TimeTicks::Now();
}
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(ImplGetTimeNow(), 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]
double delay = policy_->initial_delay_ms;
delay *= pow(policy_->multiply_factor, effective_failure_count - 1);
delay -= base::RandDouble() * policy_->jitter_factor * delay;
const int64 kMaxInt64 = std::numeric_limits<int64>::max();
int64 delay_int = (delay > kMaxInt64) ?
kMaxInt64 : static_cast<int64>(delay + 0.5);
// Ensure that we do not exceed maximum delay.
if (policy_->maximum_backoff_ms >= 0)
delay_int = std::min(delay_int, policy_->maximum_backoff_ms);
// Never reduce previously set release horizon, e.g. due to Retry-After
// header.
return std::max(
ImplGetTimeNow() + base::TimeDelta::FromMilliseconds(delay_int),
exponential_backoff_release_time_);
}
} // namespace net
|
