1 // Copyright 2012 The Chromium Authors
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 "base/time/tick_clock.h"
8 #include "base/time/time.h"
9 #include "testing/gtest/include/gtest/gtest.h"
10
11 namespace net {
12
13 namespace {
14
15 using base::TimeTicks;
16
17 BackoffEntry::Policy base_policy = { 0, 1000, 2.0, 0.0, 20000, 2000, false };
18
19 class TestTickClock : public base::TickClock {
20 public:
21 TestTickClock() = default;
22 TestTickClock(const TestTickClock&) = delete;
23 TestTickClock& operator=(const TestTickClock&) = delete;
24 ~TestTickClock() override = default;
25
NowTicks() const26 TimeTicks NowTicks() const override { return now_ticks_; }
set_now(TimeTicks now)27 void set_now(TimeTicks now) { now_ticks_ = now; }
28
29 private:
30 TimeTicks now_ticks_;
31 };
32
TEST(BackoffEntryTest,BaseTest)33 TEST(BackoffEntryTest, BaseTest) {
34 TestTickClock now_ticks;
35 BackoffEntry entry(&base_policy, &now_ticks);
36 EXPECT_FALSE(entry.ShouldRejectRequest());
37 EXPECT_EQ(base::TimeDelta(), entry.GetTimeUntilRelease());
38
39 entry.InformOfRequest(false);
40 EXPECT_TRUE(entry.ShouldRejectRequest());
41 EXPECT_EQ(base::Milliseconds(1000), entry.GetTimeUntilRelease());
42 }
43
TEST(BackoffEntryTest,CanDiscardNeverExpires)44 TEST(BackoffEntryTest, CanDiscardNeverExpires) {
45 BackoffEntry::Policy never_expires_policy = base_policy;
46 never_expires_policy.entry_lifetime_ms = -1;
47 TestTickClock now_ticks;
48 BackoffEntry never_expires(&never_expires_policy, &now_ticks);
49 EXPECT_FALSE(never_expires.CanDiscard());
50 now_ticks.set_now(TimeTicks() + base::Days(100));
51 EXPECT_FALSE(never_expires.CanDiscard());
52 }
53
TEST(BackoffEntryTest,CanDiscard)54 TEST(BackoffEntryTest, CanDiscard) {
55 TestTickClock now_ticks;
56 BackoffEntry entry(&base_policy, &now_ticks);
57 // Because lifetime is non-zero, we shouldn't be able to discard yet.
58 EXPECT_FALSE(entry.CanDiscard());
59
60 // Test the "being used" case.
61 entry.InformOfRequest(false);
62 EXPECT_FALSE(entry.CanDiscard());
63
64 // Test the case where there are errors but we can time out.
65 now_ticks.set_now(entry.GetReleaseTime() + base::Milliseconds(1));
66 EXPECT_FALSE(entry.CanDiscard());
67 now_ticks.set_now(entry.GetReleaseTime() +
68 base::Milliseconds(base_policy.maximum_backoff_ms + 1));
69 EXPECT_TRUE(entry.CanDiscard());
70
71 // Test the final case (no errors, dependent only on specified lifetime).
72 now_ticks.set_now(entry.GetReleaseTime() +
73 base::Milliseconds(base_policy.entry_lifetime_ms - 1));
74 entry.InformOfRequest(true);
75 EXPECT_FALSE(entry.CanDiscard());
76 now_ticks.set_now(entry.GetReleaseTime() +
77 base::Milliseconds(base_policy.entry_lifetime_ms));
78 EXPECT_TRUE(entry.CanDiscard());
79 }
80
TEST(BackoffEntryTest,CanDiscardAlwaysDelay)81 TEST(BackoffEntryTest, CanDiscardAlwaysDelay) {
82 BackoffEntry::Policy always_delay_policy = base_policy;
83 always_delay_policy.always_use_initial_delay = true;
84 always_delay_policy.entry_lifetime_ms = 0;
85
86 TestTickClock now_ticks;
87 BackoffEntry entry(&always_delay_policy, &now_ticks);
88
89 // Because lifetime is non-zero, we shouldn't be able to discard yet.
90 now_ticks.set_now(entry.GetReleaseTime() + base::Milliseconds(2000));
91 EXPECT_TRUE(entry.CanDiscard());
92
93 // Even with no failures, we wait until the delay before we allow discard.
94 entry.InformOfRequest(true);
95 EXPECT_FALSE(entry.CanDiscard());
96
97 // Wait until the delay expires, and we can discard the entry again.
98 now_ticks.set_now(entry.GetReleaseTime() + base::Milliseconds(1000));
99 EXPECT_TRUE(entry.CanDiscard());
100 }
101
TEST(BackoffEntryTest,CanDiscardNotStored)102 TEST(BackoffEntryTest, CanDiscardNotStored) {
103 BackoffEntry::Policy no_store_policy = base_policy;
104 no_store_policy.entry_lifetime_ms = 0;
105 TestTickClock now_ticks;
106 BackoffEntry not_stored(&no_store_policy, &now_ticks);
107 EXPECT_TRUE(not_stored.CanDiscard());
108 }
109
TEST(BackoffEntryTest,ShouldIgnoreFirstTwo)110 TEST(BackoffEntryTest, ShouldIgnoreFirstTwo) {
111 BackoffEntry::Policy lenient_policy = base_policy;
112 lenient_policy.num_errors_to_ignore = 2;
113
114 BackoffEntry entry(&lenient_policy);
115
116 entry.InformOfRequest(false);
117 EXPECT_FALSE(entry.ShouldRejectRequest());
118
119 entry.InformOfRequest(false);
120 EXPECT_FALSE(entry.ShouldRejectRequest());
121
122 entry.InformOfRequest(false);
123 EXPECT_TRUE(entry.ShouldRejectRequest());
124 }
125
TEST(BackoffEntryTest,ReleaseTimeCalculation)126 TEST(BackoffEntryTest, ReleaseTimeCalculation) {
127 TestTickClock now_ticks;
128 BackoffEntry entry(&base_policy, &now_ticks);
129
130 // With zero errors, should return "now".
131 TimeTicks result = entry.GetReleaseTime();
132 EXPECT_EQ(now_ticks.NowTicks(), result);
133
134 // 1 error.
135 entry.InformOfRequest(false);
136 result = entry.GetReleaseTime();
137 EXPECT_EQ(now_ticks.NowTicks() + base::Milliseconds(1000), result);
138 EXPECT_EQ(base::Milliseconds(1000), entry.GetTimeUntilRelease());
139
140 // 2 errors.
141 entry.InformOfRequest(false);
142 result = entry.GetReleaseTime();
143 EXPECT_EQ(now_ticks.NowTicks() + base::Milliseconds(2000), result);
144 EXPECT_EQ(base::Milliseconds(2000), entry.GetTimeUntilRelease());
145
146 // 3 errors.
147 entry.InformOfRequest(false);
148 result = entry.GetReleaseTime();
149 EXPECT_EQ(now_ticks.NowTicks() + base::Milliseconds(4000), result);
150 EXPECT_EQ(base::Milliseconds(4000), entry.GetTimeUntilRelease());
151
152 // 6 errors (to check it doesn't pass maximum).
153 entry.InformOfRequest(false);
154 entry.InformOfRequest(false);
155 entry.InformOfRequest(false);
156 result = entry.GetReleaseTime();
157 EXPECT_EQ(now_ticks.NowTicks() + base::Milliseconds(20000), result);
158 }
159
TEST(BackoffEntryTest,ReleaseTimeCalculationAlwaysDelay)160 TEST(BackoffEntryTest, ReleaseTimeCalculationAlwaysDelay) {
161 BackoffEntry::Policy always_delay_policy = base_policy;
162 always_delay_policy.always_use_initial_delay = true;
163 always_delay_policy.num_errors_to_ignore = 2;
164
165 TestTickClock now_ticks;
166 BackoffEntry entry(&always_delay_policy, &now_ticks);
167
168 // With previous requests, should return "now".
169 TimeTicks result = entry.GetReleaseTime();
170 EXPECT_EQ(base::TimeDelta(), entry.GetTimeUntilRelease());
171
172 // 1 error.
173 entry.InformOfRequest(false);
174 EXPECT_EQ(base::Milliseconds(1000), entry.GetTimeUntilRelease());
175
176 // 2 errors.
177 entry.InformOfRequest(false);
178 EXPECT_EQ(base::Milliseconds(1000), entry.GetTimeUntilRelease());
179
180 // 3 errors, exponential backoff starts.
181 entry.InformOfRequest(false);
182 EXPECT_EQ(base::Milliseconds(2000), entry.GetTimeUntilRelease());
183
184 // 4 errors.
185 entry.InformOfRequest(false);
186 EXPECT_EQ(base::Milliseconds(4000), entry.GetTimeUntilRelease());
187
188 // 8 errors (to check it doesn't pass maximum).
189 entry.InformOfRequest(false);
190 entry.InformOfRequest(false);
191 entry.InformOfRequest(false);
192 entry.InformOfRequest(false);
193 result = entry.GetReleaseTime();
194 EXPECT_EQ(base::Milliseconds(20000), entry.GetTimeUntilRelease());
195 }
196
TEST(BackoffEntryTest,ReleaseTimeCalculationWithJitter)197 TEST(BackoffEntryTest, ReleaseTimeCalculationWithJitter) {
198 for (int i = 0; i < 10; ++i) {
199 BackoffEntry::Policy jittery_policy = base_policy;
200 jittery_policy.jitter_factor = 0.2;
201
202 TestTickClock now_ticks;
203 BackoffEntry entry(&jittery_policy, &now_ticks);
204
205 entry.InformOfRequest(false);
206 entry.InformOfRequest(false);
207 entry.InformOfRequest(false);
208 TimeTicks result = entry.GetReleaseTime();
209 EXPECT_LE(now_ticks.NowTicks() + base::Milliseconds(3200), result);
210 EXPECT_GE(now_ticks.NowTicks() + base::Milliseconds(4000), result);
211 }
212 }
213
TEST(BackoffEntryTest,FailureThenSuccess)214 TEST(BackoffEntryTest, FailureThenSuccess) {
215 TestTickClock now_ticks;
216 BackoffEntry entry(&base_policy, &now_ticks);
217
218 // Failure count 1, establishes horizon.
219 entry.InformOfRequest(false);
220 TimeTicks release_time = entry.GetReleaseTime();
221 EXPECT_EQ(TimeTicks() + base::Milliseconds(1000), release_time);
222
223 // Success, failure count 0, should not advance past
224 // the horizon that was already set.
225 now_ticks.set_now(release_time - base::Milliseconds(200));
226 entry.InformOfRequest(true);
227 EXPECT_EQ(release_time, entry.GetReleaseTime());
228
229 // Failure, failure count 1.
230 entry.InformOfRequest(false);
231 EXPECT_EQ(release_time + base::Milliseconds(800), entry.GetReleaseTime());
232 }
233
TEST(BackoffEntryTest,FailureThenSuccessAlwaysDelay)234 TEST(BackoffEntryTest, FailureThenSuccessAlwaysDelay) {
235 BackoffEntry::Policy always_delay_policy = base_policy;
236 always_delay_policy.always_use_initial_delay = true;
237 always_delay_policy.num_errors_to_ignore = 1;
238
239 TestTickClock now_ticks;
240 BackoffEntry entry(&always_delay_policy, &now_ticks);
241
242 // Failure count 1.
243 entry.InformOfRequest(false);
244 EXPECT_EQ(base::Milliseconds(1000), entry.GetTimeUntilRelease());
245
246 // Failure count 2.
247 entry.InformOfRequest(false);
248 EXPECT_EQ(base::Milliseconds(2000), entry.GetTimeUntilRelease());
249 now_ticks.set_now(entry.GetReleaseTime() + base::Milliseconds(2000));
250
251 // Success. We should go back to the original delay.
252 entry.InformOfRequest(true);
253 EXPECT_EQ(base::Milliseconds(1000), entry.GetTimeUntilRelease());
254
255 // Failure count reaches 2 again. We should increase the delay once more.
256 entry.InformOfRequest(false);
257 EXPECT_EQ(base::Milliseconds(2000), entry.GetTimeUntilRelease());
258 now_ticks.set_now(entry.GetReleaseTime() + base::Milliseconds(2000));
259 }
260
TEST(BackoffEntryTest,RetainCustomHorizon)261 TEST(BackoffEntryTest, RetainCustomHorizon) {
262 TestTickClock now_ticks;
263 BackoffEntry custom(&base_policy, &now_ticks);
264 TimeTicks custom_horizon = TimeTicks() + base::Days(3);
265 custom.SetCustomReleaseTime(custom_horizon);
266 custom.InformOfRequest(false);
267 custom.InformOfRequest(true);
268 now_ticks.set_now(TimeTicks() + base::Days(2));
269 custom.InformOfRequest(false);
270 custom.InformOfRequest(true);
271 EXPECT_EQ(custom_horizon, custom.GetReleaseTime());
272
273 // Now check that once we are at or past the custom horizon,
274 // we get normal behavior.
275 now_ticks.set_now(TimeTicks() + base::Days(3));
276 custom.InformOfRequest(false);
277 EXPECT_EQ(TimeTicks() + base::Days(3) + base::Milliseconds(1000),
278 custom.GetReleaseTime());
279 }
280
TEST(BackoffEntryTest,RetainCustomHorizonWhenInitialErrorsIgnored)281 TEST(BackoffEntryTest, RetainCustomHorizonWhenInitialErrorsIgnored) {
282 // Regression test for a bug discovered during code review.
283 BackoffEntry::Policy lenient_policy = base_policy;
284 lenient_policy.num_errors_to_ignore = 1;
285 TestTickClock now_ticks;
286 BackoffEntry custom(&lenient_policy, &now_ticks);
287 TimeTicks custom_horizon = TimeTicks() + base::Days(3);
288 custom.SetCustomReleaseTime(custom_horizon);
289 custom.InformOfRequest(false); // This must not reset the horizon.
290 EXPECT_EQ(custom_horizon, custom.GetReleaseTime());
291 }
292
TEST(BackoffEntryTest,OverflowProtection)293 TEST(BackoffEntryTest, OverflowProtection) {
294 BackoffEntry::Policy large_multiply_policy = base_policy;
295 large_multiply_policy.multiply_factor = 256;
296 TestTickClock now_ticks;
297 BackoffEntry custom(&large_multiply_policy, &now_ticks);
298
299 // Trigger enough failures such that more than 11 bits of exponent are used
300 // to represent the exponential backoff intermediate values. Given a multiply
301 // factor of 256 (2^8), 129 iterations is enough: 2^(8*(129-1)) = 2^1024.
302 for (int i = 0; i < 129; ++i) {
303 now_ticks.set_now(now_ticks.NowTicks() + custom.GetTimeUntilRelease());
304 custom.InformOfRequest(false);
305 ASSERT_TRUE(custom.ShouldRejectRequest());
306 }
307
308 // Max delay should still be respected.
309 EXPECT_EQ(20000, custom.GetTimeUntilRelease().InMilliseconds());
310 }
311
312 } // namespace
313
314 } // namespace net
315