src/backoff_entry_unittest.cc

// Copyright 2015 The Weave Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/backoff_entry.h"

#include <gtest/gtest.h>

using base::TimeDelta;
using base::TimeTicks;

namespace weave {

BackoffEntry::Policy base_policy = {0, 1000, 2.0, 0.0, 20000, 2000, false};

class TestBackoffEntry : public BackoffEntry {
 public:
  explicit TestBackoffEntry(const Policy* const policy)
      : BackoffEntry(policy), now_(TimeTicks()) {
    // Work around initialization in constructor not picking up
    // fake time.
    SetCustomReleaseTime(TimeTicks());
  }

  ~TestBackoffEntry() override {}

  TimeTicks ImplGetTimeNow() const override { return now_; }

  void set_now(const TimeTicks& now) { now_ = now; }

 private:
  TimeTicks now_;

  DISALLOW_COPY_AND_ASSIGN(TestBackoffEntry);
};

TEST(BackoffEntryTest, BaseTest) {
  TestBackoffEntry entry(&base_policy);
  EXPECT_FALSE(entry.ShouldRejectRequest());
  EXPECT_EQ(TimeDelta(), entry.GetTimeUntilRelease());

  entry.InformOfRequest(false);
  EXPECT_TRUE(entry.ShouldRejectRequest());
  EXPECT_EQ(TimeDelta::FromMilliseconds(1000), entry.GetTimeUntilRelease());
}

TEST(BackoffEntryTest, CanDiscardNeverExpires) {
  BackoffEntry::Policy never_expires_policy = base_policy;
  never_expires_policy.entry_lifetime_ms = -1;
  TestBackoffEntry never_expires(&never_expires_policy);
  EXPECT_FALSE(never_expires.CanDiscard());
  never_expires.set_now(TimeTicks() + TimeDelta::FromDays(100));
  EXPECT_FALSE(never_expires.CanDiscard());
}

TEST(BackoffEntryTest, CanDiscard) {
  TestBackoffEntry entry(&base_policy);
  // Because lifetime is non-zero, we shouldn't be able to discard yet.
  EXPECT_FALSE(entry.CanDiscard());

  // Test the "being used" case.
  entry.InformOfRequest(false);
  EXPECT_FALSE(entry.CanDiscard());

  // Test the case where there are errors but we can time out.
  entry.set_now(entry.GetReleaseTime() + TimeDelta::FromMilliseconds(1));
  EXPECT_FALSE(entry.CanDiscard());
  entry.set_now(
      entry.GetReleaseTime() +
      TimeDelta::FromMilliseconds(base_policy.maximum_backoff_ms + 1));
  EXPECT_TRUE(entry.CanDiscard());

  // Test the final case (no errors, dependent only on specified lifetime).
  entry.set_now(entry.GetReleaseTime() +
                TimeDelta::FromMilliseconds(base_policy.entry_lifetime_ms - 1));
  entry.InformOfRequest(true);
  EXPECT_FALSE(entry.CanDiscard());
  entry.set_now(entry.GetReleaseTime() +
                TimeDelta::FromMilliseconds(base_policy.entry_lifetime_ms));
  EXPECT_TRUE(entry.CanDiscard());
}

TEST(BackoffEntryTest, CanDiscardAlwaysDelay) {
  BackoffEntry::Policy always_delay_policy = base_policy;
  always_delay_policy.always_use_initial_delay = true;
  always_delay_policy.entry_lifetime_ms = 0;

  TestBackoffEntry entry(&always_delay_policy);

  // Because lifetime is non-zero, we shouldn't be able to discard yet.
  entry.set_now(entry.GetReleaseTime() + TimeDelta::FromMilliseconds(2000));
  EXPECT_TRUE(entry.CanDiscard());

  // Even with no failures, we wait until the delay before we allow discard.
  entry.InformOfRequest(true);
  EXPECT_FALSE(entry.CanDiscard());

  // Wait until the delay expires, and we can discard the entry again.
  entry.set_now(entry.GetReleaseTime() + TimeDelta::FromMilliseconds(1000));
  EXPECT_TRUE(entry.CanDiscard());
}

TEST(BackoffEntryTest, CanDiscardNotStored) {
  BackoffEntry::Policy no_store_policy = base_policy;
  no_store_policy.entry_lifetime_ms = 0;
  TestBackoffEntry not_stored(&no_store_policy);
  EXPECT_TRUE(not_stored.CanDiscard());
}

TEST(BackoffEntryTest, ShouldIgnoreFirstTwo) {
  BackoffEntry::Policy lenient_policy = base_policy;
  lenient_policy.num_errors_to_ignore = 2;

  BackoffEntry entry(&lenient_policy);

  entry.InformOfRequest(false);
  EXPECT_FALSE(entry.ShouldRejectRequest());

  entry.InformOfRequest(false);
  EXPECT_FALSE(entry.ShouldRejectRequest());

  entry.InformOfRequest(false);
  EXPECT_TRUE(entry.ShouldRejectRequest());
}

TEST(BackoffEntryTest, ReleaseTimeCalculation) {
  TestBackoffEntry entry(&base_policy);

  // With zero errors, should return "now".
  TimeTicks result = entry.GetReleaseTime();
  EXPECT_EQ(entry.ImplGetTimeNow(), result);

  // 1 error.
  entry.InformOfRequest(false);
  result = entry.GetReleaseTime();
  EXPECT_EQ(entry.ImplGetTimeNow() + TimeDelta::FromMilliseconds(1000), result);
  EXPECT_EQ(TimeDelta::FromMilliseconds(1000), entry.GetTimeUntilRelease());

  // 2 errors.
  entry.InformOfRequest(false);
  result = entry.GetReleaseTime();
  EXPECT_EQ(entry.ImplGetTimeNow() + TimeDelta::FromMilliseconds(2000), result);
  EXPECT_EQ(TimeDelta::FromMilliseconds(2000), entry.GetTimeUntilRelease());

  // 3 errors.
  entry.InformOfRequest(false);
  result = entry.GetReleaseTime();
  EXPECT_EQ(entry.ImplGetTimeNow() + TimeDelta::FromMilliseconds(4000), result);
  EXPECT_EQ(TimeDelta::FromMilliseconds(4000), entry.GetTimeUntilRelease());

  // 6 errors (to check it doesn't pass maximum).
  entry.InformOfRequest(false);
  entry.InformOfRequest(false);
  entry.InformOfRequest(false);
  result = entry.GetReleaseTime();
  EXPECT_EQ(entry.ImplGetTimeNow() + TimeDelta::FromMilliseconds(20000),
            result);
}

TEST(BackoffEntryTest, ReleaseTimeCalculationAlwaysDelay) {
  BackoffEntry::Policy always_delay_policy = base_policy;
  always_delay_policy.always_use_initial_delay = true;
  always_delay_policy.num_errors_to_ignore = 2;

  TestBackoffEntry entry(&always_delay_policy);

  // With previous requests, should return "now".
  TimeTicks result = entry.GetReleaseTime();
  EXPECT_EQ(TimeDelta(), entry.GetTimeUntilRelease());

  // 1 error.
  entry.InformOfRequest(false);
  EXPECT_EQ(TimeDelta::FromMilliseconds(1000), entry.GetTimeUntilRelease());

  // 2 errors.
  entry.InformOfRequest(false);
  EXPECT_EQ(TimeDelta::FromMilliseconds(1000), entry.GetTimeUntilRelease());

  // 3 errors, exponential backoff starts.
  entry.InformOfRequest(false);
  EXPECT_EQ(TimeDelta::FromMilliseconds(2000), entry.GetTimeUntilRelease());

  // 4 errors.
  entry.InformOfRequest(false);
  EXPECT_EQ(TimeDelta::FromMilliseconds(4000), entry.GetTimeUntilRelease());

  // 8 errors (to check it doesn't pass maximum).
  entry.InformOfRequest(false);
  entry.InformOfRequest(false);
  entry.InformOfRequest(false);
  entry.InformOfRequest(false);
  result = entry.GetReleaseTime();
  EXPECT_EQ(TimeDelta::FromMilliseconds(20000), entry.GetTimeUntilRelease());
}

TEST(BackoffEntryTest, ReleaseTimeCalculationWithJitter) {
  for (int i = 0; i < 10; ++i) {
    BackoffEntry::Policy jittery_policy = base_policy;
    jittery_policy.jitter_factor = 0.2;

    TestBackoffEntry entry(&jittery_policy);

    entry.InformOfRequest(false);
    entry.InformOfRequest(false);
    entry.InformOfRequest(false);
    TimeTicks result = entry.GetReleaseTime();
    EXPECT_LE(entry.ImplGetTimeNow() + TimeDelta::FromMilliseconds(3200),
              result);
    EXPECT_GE(entry.ImplGetTimeNow() + TimeDelta::FromMilliseconds(4000),
              result);
  }
}

TEST(BackoffEntryTest, FailureThenSuccess) {
  TestBackoffEntry entry(&base_policy);

  // Failure count 1, establishes horizon.
  entry.InformOfRequest(false);
  TimeTicks release_time = entry.GetReleaseTime();
  EXPECT_EQ(TimeTicks() + TimeDelta::FromMilliseconds(1000), release_time);

  // Success, failure count 0, should not advance past
  // the horizon that was already set.
  entry.set_now(release_time - TimeDelta::FromMilliseconds(200));
  entry.InformOfRequest(true);
  EXPECT_EQ(release_time, entry.GetReleaseTime());

  // Failure, failure count 1.
  entry.InformOfRequest(false);
  EXPECT_EQ(release_time + TimeDelta::FromMilliseconds(800),
            entry.GetReleaseTime());
}

TEST(BackoffEntryTest, FailureThenSuccessAlwaysDelay) {
  BackoffEntry::Policy always_delay_policy = base_policy;
  always_delay_policy.always_use_initial_delay = true;
  always_delay_policy.num_errors_to_ignore = 1;

  TestBackoffEntry entry(&always_delay_policy);

  // Failure count 1.
  entry.InformOfRequest(false);
  EXPECT_EQ(TimeDelta::FromMilliseconds(1000), entry.GetTimeUntilRelease());

  // Failure count 2.
  entry.InformOfRequest(false);
  EXPECT_EQ(TimeDelta::FromMilliseconds(2000), entry.GetTimeUntilRelease());
  entry.set_now(entry.GetReleaseTime() + TimeDelta::FromMilliseconds(2000));

  // Success.  We should go back to the original delay.
  entry.InformOfRequest(true);
  EXPECT_EQ(TimeDelta::FromMilliseconds(1000), entry.GetTimeUntilRelease());

  // Failure count reaches 2 again.  We should increase the delay once more.
  entry.InformOfRequest(false);
  EXPECT_EQ(TimeDelta::FromMilliseconds(2000), entry.GetTimeUntilRelease());
  entry.set_now(entry.GetReleaseTime() + TimeDelta::FromMilliseconds(2000));
}

TEST(BackoffEntryTest, RetainCustomHorizon) {
  TestBackoffEntry custom(&base_policy);
  TimeTicks custom_horizon = TimeTicks() + TimeDelta::FromDays(3);
  custom.SetCustomReleaseTime(custom_horizon);
  custom.InformOfRequest(false);
  custom.InformOfRequest(true);
  custom.set_now(TimeTicks() + TimeDelta::FromDays(2));
  custom.InformOfRequest(false);
  custom.InformOfRequest(true);
  EXPECT_EQ(custom_horizon, custom.GetReleaseTime());

  // Now check that once we are at or past the custom horizon,
  // we get normal behavior.
  custom.set_now(TimeTicks() + TimeDelta::FromDays(3));
  custom.InformOfRequest(false);
  EXPECT_EQ(
      TimeTicks() + TimeDelta::FromDays(3) + TimeDelta::FromMilliseconds(1000),
      custom.GetReleaseTime());
}

TEST(BackoffEntryTest, RetainCustomHorizonWhenInitialErrorsIgnored) {
  // Regression test for a bug discovered during code review.
  BackoffEntry::Policy lenient_policy = base_policy;
  lenient_policy.num_errors_to_ignore = 1;
  TestBackoffEntry custom(&lenient_policy);
  TimeTicks custom_horizon = TimeTicks() + TimeDelta::FromDays(3);
  custom.SetCustomReleaseTime(custom_horizon);
  custom.InformOfRequest(false);  // This must not reset the horizon.
  EXPECT_EQ(custom_horizon, custom.GetReleaseTime());
}

TEST(BackoffEntryTest, OverflowProtection) {
  BackoffEntry::Policy large_multiply_policy = base_policy;
  large_multiply_policy.multiply_factor = 256;
  TestBackoffEntry custom(&large_multiply_policy);

  // Trigger enough failures such that more than 11 bits of exponent are used
  // to represent the exponential backoff intermediate values. Given a multiply
  // factor of 256 (2^8), 129 iterations is enough: 2^(8*(129-1)) = 2^1024.
  for (int i = 0; i < 129; ++i) {
    custom.set_now(custom.ImplGetTimeNow() + custom.GetTimeUntilRelease());
    custom.InformOfRequest(false);
    ASSERT_TRUE(custom.ShouldRejectRequest());
  }

  // Max delay should still be respected.
  EXPECT_EQ(20000, custom.GetTimeUntilRelease().InMilliseconds());
}

}  // namespace weave