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