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
8 using base::TimeDelta;
9 using base::TimeTicks;
10
11 namespace brillo {
12
13 BackoffEntry::Policy base_policy = { 0, 1000, 2.0, 0.0, 20000, 2000, false };
14
15 class TestBackoffEntry : public BackoffEntry {
16 public:
TestBackoffEntry(const Policy * const policy)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
~TestBackoffEntry()25 ~TestBackoffEntry() override {}
26
ImplGetTimeNow() const27 TimeTicks ImplGetTimeNow() const override { return now_; }
28
set_now(const TimeTicks & now)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
TEST(BackoffEntryTest,BaseTest)39 TEST(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
TEST(BackoffEntryTest,CanDiscardNeverExpires)49 TEST(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
TEST(BackoffEntryTest,CanDiscard)58 TEST(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
TEST(BackoffEntryTest,CanDiscardAlwaysDelay)85 TEST(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
TEST(BackoffEntryTest,CanDiscardNotStored)105 TEST(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
TEST(BackoffEntryTest,ShouldIgnoreFirstTwo)112 TEST(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
TEST(BackoffEntryTest,ReleaseTimeCalculation)128 TEST(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
TEST(BackoffEntryTest,ReleaseTimeCalculationAlwaysDelay)162 TEST(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
TEST(BackoffEntryTest,ReleaseTimeCalculationWithJitter)198 TEST(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
TEST(BackoffEntryTest,FailureThenSuccess)216 TEST(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
TEST(BackoffEntryTest,FailureThenSuccessAlwaysDelay)236 TEST(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
TEST(BackoffEntryTest,RetainCustomHorizon)262 TEST(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
TEST(BackoffEntryTest,RetainCustomHorizonWhenInitialErrorsIgnored)282 TEST(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
TEST(BackoffEntryTest,OverflowProtection)293 TEST(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