libweave: Move backoff_entry from libchromeos into libweave
It's used by libweave only.
BUG=brillo:1257
TEST=`FEATURES=test emerge-gizmo libchromeos libweave`
Change-Id: I07aa30a9b758161bf29c8bce7a057550f565dc94
Reviewed-on: https://chromium-review.googlesource.com/293421
Reviewed-by: Alex Vakulenko <avakulenko@chromium.org>
Commit-Queue: Vitaly Buka <vitalybuka@chromium.org>
Tested-by: Vitaly Buka <vitalybuka@chromium.org>
diff --git a/libweave/libweave.gyp b/libweave/libweave.gyp
index 05fc5ca..e0287d7 100644
--- a/libweave/libweave.gyp
+++ b/libweave/libweave.gyp
@@ -27,6 +27,7 @@
'target_name': 'libweave_common',
'type': 'static_library',
'sources': [
+ 'src/backoff_entry.cc',
'src/base_api_handler.cc',
'src/buffet_config.cc',
'src/commands/cloud_command_proxy.cc',
@@ -119,6 +120,7 @@
'external/crypto/p224_spake_unittest.cc',
'external/crypto/p224_unittest.cc',
'external/crypto/sha2_unittest.cc',
+ 'src/backoff_entry_unittest.cc',
'src/base_api_handler_unittest.cc',
'src/buffet_config_unittest.cc',
'src/commands/cloud_command_proxy_unittest.cc',
diff --git a/libweave/src/backoff_entry.cc b/libweave/src/backoff_entry.cc
new file mode 100644
index 0000000..b9c5b8f
--- /dev/null
+++ b/libweave/src/backoff_entry.cc
@@ -0,0 +1,167 @@
+// Copyright 2015 The Chromium OS 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 "libweave/src/backoff_entry.h"
+
+#include <algorithm>
+#include <cmath>
+#include <limits>
+
+#include <base/logging.h>
+#include <base/numerics/safe_math.h>
+#include <base/rand_util.h>
+
+namespace weave {
+
+BackoffEntry::BackoffEntry(const BackoffEntry::Policy* const policy)
+ : policy_(policy) {
+ DCHECK(policy_);
+ Reset();
+}
+
+void BackoffEntry::InformOfRequest(bool succeeded) {
+ if (!succeeded) {
+ ++failure_count_;
+ exponential_backoff_release_time_ = CalculateReleaseTime();
+ } else {
+ // We slowly decay the number of times delayed instead of
+ // resetting it to 0 in order to stay stable if we receive
+ // successes interleaved between lots of failures. Note that in
+ // the normal case, the calculated release time (in the next
+ // statement) will be in the past once the method returns.
+ if (failure_count_ > 0)
+ --failure_count_;
+
+ // The reason why we are not just cutting the release time to
+ // ImplGetTimeNow() is on the one hand, it would unset a release
+ // time set by SetCustomReleaseTime and on the other we would like
+ // to push every request up to our "horizon" when dealing with
+ // multiple in-flight requests. Ex: If we send three requests and
+ // we receive 2 failures and 1 success. The success that follows
+ // those failures will not reset the release time, further
+ // requests will then need to wait the delay caused by the 2
+ // failures.
+ base::TimeDelta delay;
+ if (policy_->always_use_initial_delay)
+ delay = base::TimeDelta::FromMilliseconds(policy_->initial_delay_ms);
+ exponential_backoff_release_time_ =
+ std::max(ImplGetTimeNow() + delay, exponential_backoff_release_time_);
+ }
+}
+
+bool BackoffEntry::ShouldRejectRequest() const {
+ return exponential_backoff_release_time_ > ImplGetTimeNow();
+}
+
+base::TimeDelta BackoffEntry::GetTimeUntilRelease() const {
+ base::TimeTicks now = ImplGetTimeNow();
+ if (exponential_backoff_release_time_ <= now)
+ return base::TimeDelta();
+ return exponential_backoff_release_time_ - now;
+}
+
+base::TimeTicks BackoffEntry::GetReleaseTime() const {
+ return exponential_backoff_release_time_;
+}
+
+void BackoffEntry::SetCustomReleaseTime(const base::TimeTicks& release_time) {
+ exponential_backoff_release_time_ = release_time;
+}
+
+bool BackoffEntry::CanDiscard() const {
+ if (policy_->entry_lifetime_ms == -1)
+ return false;
+
+ base::TimeTicks now = ImplGetTimeNow();
+
+ int64 unused_since_ms =
+ (now - exponential_backoff_release_time_).InMilliseconds();
+
+ // Release time is further than now, we are managing it.
+ if (unused_since_ms < 0)
+ return false;
+
+ if (failure_count_ > 0) {
+ // Need to keep track of failures until maximum back-off period
+ // has passed (since further failures can add to back-off).
+ return unused_since_ms >=
+ std::max(policy_->maximum_backoff_ms, policy_->entry_lifetime_ms);
+ }
+
+ // Otherwise, consider the entry is outdated if it hasn't been used for the
+ // specified lifetime period.
+ return unused_since_ms >= policy_->entry_lifetime_ms;
+}
+
+void BackoffEntry::Reset() {
+ failure_count_ = 0;
+
+ // We leave exponential_backoff_release_time_ unset, meaning 0. We could
+ // initialize to ImplGetTimeNow() but because it's a virtual method it's
+ // not safe to call in the constructor (and the constructor calls Reset()).
+ // The effects are the same, i.e. ShouldRejectRequest() will return false
+ // right after Reset().
+ exponential_backoff_release_time_ = base::TimeTicks();
+}
+
+base::TimeTicks BackoffEntry::ImplGetTimeNow() const {
+ return base::TimeTicks::Now();
+}
+
+base::TimeTicks BackoffEntry::CalculateReleaseTime() const {
+ int effective_failure_count =
+ std::max(0, failure_count_ - policy_->num_errors_to_ignore);
+
+ // If always_use_initial_delay is true, it's equivalent to
+ // the effective_failure_count always being one greater than when it's false.
+ if (policy_->always_use_initial_delay)
+ ++effective_failure_count;
+
+ if (effective_failure_count == 0) {
+ // Never reduce previously set release horizon, e.g. due to Retry-After
+ // header.
+ return std::max(ImplGetTimeNow(), exponential_backoff_release_time_);
+ }
+
+ // The delay is calculated with this formula:
+ // delay = initial_backoff * multiply_factor^(
+ // effective_failure_count - 1) * Uniform(1 - jitter_factor, 1]
+ // Note: if the failure count is too high, |delay_ms| will become infinity
+ // after the exponential calculation, and then NaN after the jitter is
+ // accounted for. Both cases are handled by using CheckedNumeric<int64_t> to
+ // perform the conversion to integers.
+ double delay_ms = policy_->initial_delay_ms;
+ delay_ms *= pow(policy_->multiply_factor, effective_failure_count - 1);
+ delay_ms -= base::RandDouble() * policy_->jitter_factor * delay_ms;
+
+ // Do overflow checking in microseconds, the internal unit of TimeTicks.
+ const int64_t kTimeTicksNowUs =
+ (ImplGetTimeNow() - base::TimeTicks()).InMicroseconds();
+ base::internal::CheckedNumeric<int64_t> calculated_release_time_us =
+ delay_ms + 0.5;
+ calculated_release_time_us *= base::Time::kMicrosecondsPerMillisecond;
+ calculated_release_time_us += kTimeTicksNowUs;
+
+ const int64_t kMaxTime = std::numeric_limits<int64_t>::max();
+ base::internal::CheckedNumeric<int64_t> maximum_release_time_us = kMaxTime;
+ if (policy_->maximum_backoff_ms >= 0) {
+ maximum_release_time_us = policy_->maximum_backoff_ms;
+ maximum_release_time_us *= base::Time::kMicrosecondsPerMillisecond;
+ maximum_release_time_us += kTimeTicksNowUs;
+ }
+
+ // Decide between maximum release time and calculated release time, accounting
+ // for overflow with both.
+ int64 release_time_us =
+ std::min(calculated_release_time_us.ValueOrDefault(kMaxTime),
+ maximum_release_time_us.ValueOrDefault(kMaxTime));
+
+ // Never reduce previously set release horizon, e.g. due to Retry-After
+ // header.
+ return std::max(
+ base::TimeTicks() + base::TimeDelta::FromMicroseconds(release_time_us),
+ exponential_backoff_release_time_);
+}
+
+} // namespace weave
diff --git a/libweave/src/backoff_entry.h b/libweave/src/backoff_entry.h
new file mode 100644
index 0000000..3e7a036
--- /dev/null
+++ b/libweave/src/backoff_entry.h
@@ -0,0 +1,114 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef LIBWEAVE_SRC_BACKOFF_ENTRY_H_
+#define LIBWEAVE_SRC_BACKOFF_ENTRY_H_
+
+#include <base/time/time.h>
+
+namespace weave {
+
+// Provides the core logic needed for randomized exponential back-off
+// on requests to a given resource, given a back-off policy.
+//
+// This class is largely taken from net/base/backoff_entry.h from Chromium.
+// TODO(avakulenko): Consider packaging portions of Chrome's //net functionality
+// into the current libchrome library.
+class BackoffEntry {
+ public:
+ // The set of parameters that define a back-off policy.
+ struct Policy {
+ // Number of initial errors (in sequence) to ignore before applying
+ // exponential back-off rules.
+ int num_errors_to_ignore;
+
+ // Initial delay. The interpretation of this value depends on
+ // always_use_initial_delay. It's either how long we wait between
+ // requests before backoff starts, or how much we delay the first request
+ // after backoff starts.
+ int initial_delay_ms;
+
+ // Factor by which the waiting time will be multiplied.
+ double multiply_factor;
+
+ // Fuzzing percentage. ex: 10% will spread requests randomly
+ // between 90%-100% of the calculated time.
+ double jitter_factor;
+
+ // Maximum amount of time we are willing to delay our request, -1
+ // for no maximum.
+ int64 maximum_backoff_ms;
+
+ // Time to keep an entry from being discarded even when it
+ // has no significant state, -1 to never discard.
+ int64 entry_lifetime_ms;
+
+ // If true, we always use a delay of initial_delay_ms, even before
+ // we've seen num_errors_to_ignore errors. Otherwise, initial_delay_ms
+ // is the first delay once we start exponential backoff.
+ //
+ // So if we're ignoring 1 error, we'll see (N, N, Nm, Nm^2, ...) if true,
+ // and (0, 0, N, Nm, ...) when false, where N is initial_backoff_ms and
+ // m is multiply_factor, assuming we've already seen one success.
+ bool always_use_initial_delay;
+ };
+
+ // Lifetime of policy must enclose lifetime of BackoffEntry. The
+ // pointer must be valid but is not dereferenced during construction.
+ explicit BackoffEntry(const Policy* const policy);
+ virtual ~BackoffEntry() = default;
+
+ // Inform this item that a request for the network resource it is
+ // tracking was made, and whether it failed or succeeded.
+ void InformOfRequest(bool succeeded);
+
+ // Returns true if a request for the resource this item tracks should
+ // be rejected at the present time due to exponential back-off policy.
+ bool ShouldRejectRequest() const;
+
+ // Returns the absolute time after which this entry (given its present
+ // state) will no longer reject requests.
+ base::TimeTicks GetReleaseTime() const;
+
+ // Returns the time until a request can be sent.
+ base::TimeDelta GetTimeUntilRelease() const;
+
+ // Causes this object reject requests until the specified absolute time.
+ // This can be used to e.g. implement support for a Retry-After header.
+ void SetCustomReleaseTime(const base::TimeTicks& release_time);
+
+ // Returns true if this object has no significant state (i.e. you could
+ // just as well start with a fresh BackoffEntry object), and hasn't
+ // had for Policy::entry_lifetime_ms.
+ bool CanDiscard() const;
+
+ // Resets this entry to a fresh (as if just constructed) state.
+ void Reset();
+
+ // Returns the failure count for this entry.
+ int failure_count() const { return failure_count_; }
+
+ protected:
+ // Equivalent to TimeTicks::Now(), virtual so unit tests can override.
+ virtual base::TimeTicks ImplGetTimeNow() const;
+
+ private:
+ // Calculates when requests should again be allowed through.
+ base::TimeTicks CalculateReleaseTime() const;
+
+ // Timestamp calculated by the exponential back-off algorithm at which we are
+ // allowed to start sending requests again.
+ base::TimeTicks exponential_backoff_release_time_;
+
+ // Counts request errors; decremented on success.
+ int failure_count_;
+
+ const Policy* const policy_;
+
+ DISALLOW_COPY_AND_ASSIGN(BackoffEntry);
+};
+
+} // namespace weave
+
+#endif // LIBWEAVE_SRC_BACKOFF_ENTRY_H_
diff --git a/libweave/src/backoff_entry_unittest.cc b/libweave/src/backoff_entry_unittest.cc
new file mode 100644
index 0000000..5b198a0
--- /dev/null
+++ b/libweave/src/backoff_entry_unittest.cc
@@ -0,0 +1,309 @@
+// Copyright 2015 The Chromium OS 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 "libweave/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
diff --git a/libweave/src/commands/cloud_command_proxy.cc b/libweave/src/commands/cloud_command_proxy.cc
index 58da7d1..d38fa04 100644
--- a/libweave/src/commands/cloud_command_proxy.cc
+++ b/libweave/src/commands/cloud_command_proxy.cc
@@ -19,7 +19,7 @@
CommandInstance* command_instance,
CloudCommandUpdateInterface* cloud_command_updater,
StateChangeQueueInterface* state_change_queue,
- std::unique_ptr<chromeos::BackoffEntry> backoff_entry,
+ std::unique_ptr<BackoffEntry> backoff_entry,
TaskRunner* task_runner)
: command_instance_{command_instance},
cloud_command_updater_{cloud_command_updater},
diff --git a/libweave/src/commands/cloud_command_proxy.h b/libweave/src/commands/cloud_command_proxy.h
index 838b1ff..98a7c6c 100644
--- a/libweave/src/commands/cloud_command_proxy.h
+++ b/libweave/src/commands/cloud_command_proxy.h
@@ -13,10 +13,10 @@
#include <base/macros.h>
#include <base/memory/weak_ptr.h>
#include <base/scoped_observer.h>
-#include <chromeos/backoff_entry.h>
#include <weave/command.h>
#include <weave/task_runner.h>
+#include "libweave/src/backoff_entry.h"
#include "libweave/src/commands/cloud_command_update_interface.h"
#include "libweave/src/states/state_change_queue_interface.h"
@@ -30,7 +30,7 @@
CloudCommandProxy(CommandInstance* command_instance,
CloudCommandUpdateInterface* cloud_command_updater,
StateChangeQueueInterface* state_change_queue,
- std::unique_ptr<chromeos::BackoffEntry> backoff_entry,
+ std::unique_ptr<BackoffEntry> backoff_entry,
TaskRunner* task_runner);
~CloudCommandProxy() override = default;
@@ -73,7 +73,7 @@
TaskRunner* task_runner_{nullptr};
// Backoff for SendCommandUpdate() method.
- std::unique_ptr<chromeos::BackoffEntry> cloud_backoff_entry_;
+ std::unique_ptr<BackoffEntry> cloud_backoff_entry_;
// Set to true while a pending PATCH request is in flight to the server.
bool command_update_in_progress_{false};
diff --git a/libweave/src/commands/cloud_command_proxy_unittest.cc b/libweave/src/commands/cloud_command_proxy_unittest.cc
index 8bdbfd9..d98776a 100644
--- a/libweave/src/commands/cloud_command_proxy_unittest.cc
+++ b/libweave/src/commands/cloud_command_proxy_unittest.cc
@@ -58,15 +58,15 @@
};
// Test back-off entry that uses the test clock.
-class TestBackoffEntry : public chromeos::BackoffEntry {
+class TestBackoffEntry : public BackoffEntry {
public:
TestBackoffEntry(const Policy* const policy, base::Clock* clock)
- : chromeos::BackoffEntry{policy}, clock_{clock} {
+ : BackoffEntry{policy}, clock_{clock} {
creation_time_ = clock->Now();
}
private:
- // Override from chromeos::BackoffEntry to use the custom test clock for
+ // Override from BackoffEntry to use the custom test clock for
// the backoff calculations.
base::TimeTicks ImplGetTimeNow() const override {
return base::TimeTicks::FromInternalValue(clock_->Now().ToInternalValue());
@@ -143,8 +143,8 @@
CHECK(command_instance_.get());
// Backoff - start at 1s and double with each backoff attempt and no jitter.
- static const chromeos::BackoffEntry::Policy policy{
- 0, 1000, 2.0, 0.0, 20000, -1, false};
+ static const BackoffEntry::Policy policy{0, 1000, 2.0, 0.0,
+ 20000, -1, false};
std::unique_ptr<TestBackoffEntry> backoff{
new TestBackoffEntry{&policy, &clock_}};
diff --git a/libweave/src/device_registration_info.cc b/libweave/src/device_registration_info.cc
index f648337..bc738f6 100644
--- a/libweave/src/device_registration_info.cc
+++ b/libweave/src/device_registration_info.cc
@@ -222,7 +222,7 @@
config_{std::move(config)},
notifications_enabled_{notifications_enabled},
network_{network} {
- cloud_backoff_policy_.reset(new chromeos::BackoffEntry::Policy{});
+ cloud_backoff_policy_.reset(new BackoffEntry::Policy{});
cloud_backoff_policy_->num_errors_to_ignore = 0;
cloud_backoff_policy_->initial_delay_ms = 1000;
cloud_backoff_policy_->multiply_factor = 2.0;
@@ -230,10 +230,8 @@
cloud_backoff_policy_->maximum_backoff_ms = 30000;
cloud_backoff_policy_->entry_lifetime_ms = -1;
cloud_backoff_policy_->always_use_initial_delay = false;
- cloud_backoff_entry_.reset(
- new chromeos::BackoffEntry{cloud_backoff_policy_.get()});
- oauth2_backoff_entry_.reset(
- new chromeos::BackoffEntry{cloud_backoff_policy_.get()});
+ cloud_backoff_entry_.reset(new BackoffEntry{cloud_backoff_policy_.get()});
+ oauth2_backoff_entry_.reset(new BackoffEntry{cloud_backoff_policy_.get()});
command_manager_->AddOnCommandDefChanged(
base::Bind(&DeviceRegistrationInfo::OnCommandDefsChanged,
@@ -1102,8 +1100,8 @@
if (!command_manager_->FindCommand(command_instance->GetID())) {
LOG(INFO) << "New command '" << command_instance->GetName()
<< "' arrived, ID: " << command_instance->GetID();
- std::unique_ptr<chromeos::BackoffEntry> backoff_entry{
- new chromeos::BackoffEntry{cloud_backoff_policy_.get()}};
+ std::unique_ptr<BackoffEntry> backoff_entry{
+ new BackoffEntry{cloud_backoff_policy_.get()}};
std::unique_ptr<CloudCommandProxy> cloud_proxy{new CloudCommandProxy{
command_instance.get(), this, state_manager_->GetStateChangeQueue(),
std::move(backoff_entry), task_runner_}};
diff --git a/libweave/src/device_registration_info.h b/libweave/src/device_registration_info.h
index 62f2b65..fefc27c 100644
--- a/libweave/src/device_registration_info.h
+++ b/libweave/src/device_registration_info.h
@@ -18,7 +18,6 @@
#include <base/single_thread_task_runner.h>
#include <base/time/time.h>
#include <base/timer/timer.h>
-#include <chromeos/backoff_entry.h>
#include <chromeos/data_encoding.h>
#include <chromeos/errors/error.h>
#include <weave/cloud.h>
@@ -26,6 +25,7 @@
#include <weave/http_client.h>
#include <weave/task_runner.h>
+#include "libweave/src/backoff_entry.h"
#include "libweave/src/buffet_config.h"
#include "libweave/src/commands/cloud_command_update_interface.h"
#include "libweave/src/commands/command_manager.h"
@@ -311,9 +311,9 @@
std::unique_ptr<BuffetConfig> config_;
// Backoff manager for DoCloudRequest() method.
- std::unique_ptr<chromeos::BackoffEntry::Policy> cloud_backoff_policy_;
- std::unique_ptr<chromeos::BackoffEntry> cloud_backoff_entry_;
- std::unique_ptr<chromeos::BackoffEntry> oauth2_backoff_entry_;
+ std::unique_ptr<BackoffEntry::Policy> cloud_backoff_policy_;
+ std::unique_ptr<BackoffEntry> cloud_backoff_entry_;
+ std::unique_ptr<BackoffEntry> oauth2_backoff_entry_;
// Flag set to true while a device state update patch request is in flight
// to the cloud server.
diff --git a/libweave/src/notification/xmpp_channel.cc b/libweave/src/notification/xmpp_channel.cc
index b5aa425..7d0d5c6 100644
--- a/libweave/src/notification/xmpp_channel.cc
+++ b/libweave/src/notification/xmpp_channel.cc
@@ -7,11 +7,11 @@
#include <string>
#include <base/bind.h>
-#include <chromeos/backoff_entry.h>
#include <chromeos/data_encoding.h>
#include <weave/network.h>
#include <weave/task_runner.h>
+#include "libweave/src/backoff_entry.h"
#include "libweave/src/notification/notification_delegate.h"
#include "libweave/src/notification/notification_parser.h"
#include "libweave/src/notification/xml_node.h"
@@ -47,7 +47,7 @@
// Backoff policy.
// Note: In order to ensure a minimum of 20 seconds between server errors,
// we have a 30s +- 10s (33%) jitter initial backoff.
-const chromeos::BackoffEntry::Policy kDefaultBackoffPolicy = {
+const BackoffEntry::Policy kDefaultBackoffPolicy = {
// Number of initial errors (in sequence) to ignore before applying
// exponential back-off rules.
0,
diff --git a/libweave/src/notification/xmpp_channel.h b/libweave/src/notification/xmpp_channel.h
index 1e42c2c..d6ae529 100644
--- a/libweave/src/notification/xmpp_channel.h
+++ b/libweave/src/notification/xmpp_channel.h
@@ -13,9 +13,9 @@
#include <base/callback_forward.h>
#include <base/macros.h>
#include <base/memory/weak_ptr.h>
-#include <chromeos/backoff_entry.h>
#include <weave/stream.h>
+#include "libweave/src/backoff_entry.h"
#include "libweave/src/notification/notification_channel.h"
#include "libweave/src/notification/xmpp_iq_stanza_handler.h"
#include "libweave/src/notification/xmpp_stream_parser.h"
@@ -152,7 +152,7 @@
std::string host_;
uint16_t port_{0};
- chromeos::BackoffEntry backoff_entry_;
+ BackoffEntry backoff_entry_;
NotificationDelegate* delegate_{nullptr};
TaskRunner* task_runner_{nullptr};
XmppStreamParser stream_parser_{this};
