| // 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 <brillo/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 brillo { |
| |
| 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 brillo |