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