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