net/base/backoff_entry_unittest.cc

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