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
8namespace {
9
10using base::TimeDelta;
11using base::TimeTicks;
12using net::BackoffEntry;
13
14BackoffEntry::Policy base_policy = { 0, 1000, 2.0, 0.0, 20000, 2000, false };
15
16class TestBackoffEntry : public BackoffEntry {
17 public:
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
26  virtual ~TestBackoffEntry() {}
27
28  virtual TimeTicks ImplGetTimeNow() const OVERRIDE {
29    return now_;
30  }
31
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
42TEST(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
52TEST(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
61TEST(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
88TEST(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
108TEST(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
115TEST(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
131TEST(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
165TEST(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
201TEST(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
219TEST(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
239TEST(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
265TEST(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
285TEST(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
296TEST(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