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