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