Home | History | Annotate | Download | only in brillo 
      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:
     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 
     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 
     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 
     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 
     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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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