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 
      7 #include <algorithm>
      8 #include <cmath>
      9 #include <limits>
     10 
     11 #include <base/logging.h>
     12 #include <base/numerics/safe_math.h>
     13 #include <base/rand_util.h>
     14 
     15 namespace brillo {
     16 
     17 BackoffEntry::BackoffEntry(const BackoffEntry::Policy* const policy)
     18     : policy_(policy) {
     19   DCHECK(policy_);
     20   Reset();
     21 }
     22 
     23 void BackoffEntry::InformOfRequest(bool succeeded) {
     24   if (!succeeded) {
     25     ++failure_count_;
     26     exponential_backoff_release_time_ = CalculateReleaseTime();
     27   } else {
     28     // We slowly decay the number of times delayed instead of
     29     // resetting it to 0 in order to stay stable if we receive
     30     // successes interleaved between lots of failures.  Note that in
     31     // the normal case, the calculated release time (in the next
     32     // statement) will be in the past once the method returns.
     33     if (failure_count_ > 0)
     34       --failure_count_;
     35 
     36     // The reason why we are not just cutting the release time to
     37     // ImplGetTimeNow() is on the one hand, it would unset a release
     38     // time set by SetCustomReleaseTime and on the other we would like
     39     // to push every request up to our "horizon" when dealing with
     40     // multiple in-flight requests. Ex: If we send three requests and
     41     // we receive 2 failures and 1 success. The success that follows
     42     // those failures will not reset the release time, further
     43     // requests will then need to wait the delay caused by the 2
     44     // failures.
     45     base::TimeDelta delay;
     46     if (policy_->always_use_initial_delay)
     47       delay = base::TimeDelta::FromMilliseconds(policy_->initial_delay_ms);
     48     exponential_backoff_release_time_ = std::max(
     49         ImplGetTimeNow() + delay, exponential_backoff_release_time_);
     50   }
     51 }
     52 
     53 bool BackoffEntry::ShouldRejectRequest() const {
     54   return exponential_backoff_release_time_ > ImplGetTimeNow();
     55 }
     56 
     57 base::TimeDelta BackoffEntry::GetTimeUntilRelease() const {
     58   base::TimeTicks now = ImplGetTimeNow();
     59   if (exponential_backoff_release_time_ <= now)
     60     return base::TimeDelta();
     61   return exponential_backoff_release_time_ - now;
     62 }
     63 
     64 base::TimeTicks BackoffEntry::GetReleaseTime() const {
     65   return exponential_backoff_release_time_;
     66 }
     67 
     68 void BackoffEntry::SetCustomReleaseTime(const base::TimeTicks& release_time) {
     69   exponential_backoff_release_time_ = release_time;
     70 }
     71 
     72 bool BackoffEntry::CanDiscard() const {
     73   if (policy_->entry_lifetime_ms == -1)
     74     return false;
     75 
     76   base::TimeTicks now = ImplGetTimeNow();
     77 
     78   int64_t unused_since_ms =
     79       (now - exponential_backoff_release_time_).InMilliseconds();
     80 
     81   // Release time is further than now, we are managing it.
     82   if (unused_since_ms < 0)
     83     return false;
     84 
     85   if (failure_count_ > 0) {
     86     // Need to keep track of failures until maximum back-off period
     87     // has passed (since further failures can add to back-off).
     88     return unused_since_ms >= std::max(policy_->maximum_backoff_ms,
     89                                        policy_->entry_lifetime_ms);
     90   }
     91 
     92   // Otherwise, consider the entry is outdated if it hasn't been used for the
     93   // specified lifetime period.
     94   return unused_since_ms >= policy_->entry_lifetime_ms;
     95 }
     96 
     97 void BackoffEntry::Reset() {
     98   failure_count_ = 0;
     99 
    100   // We leave exponential_backoff_release_time_ unset, meaning 0. We could
    101   // initialize to ImplGetTimeNow() but because it's a virtual method it's
    102   // not safe to call in the constructor (and the constructor calls Reset()).
    103   // The effects are the same, i.e. ShouldRejectRequest() will return false
    104   // right after Reset().
    105   exponential_backoff_release_time_ = base::TimeTicks();
    106 }
    107 
    108 base::TimeTicks BackoffEntry::ImplGetTimeNow() const {
    109   return base::TimeTicks::Now();
    110 }
    111 
    112 base::TimeTicks BackoffEntry::CalculateReleaseTime() const {
    113   int effective_failure_count =
    114       std::max(0, failure_count_ - policy_->num_errors_to_ignore);
    115 
    116   // If always_use_initial_delay is true, it's equivalent to
    117   // the effective_failure_count always being one greater than when it's false.
    118   if (policy_->always_use_initial_delay)
    119     ++effective_failure_count;
    120 
    121   if (effective_failure_count == 0) {
    122     // Never reduce previously set release horizon, e.g. due to Retry-After
    123     // header.
    124     return std::max(ImplGetTimeNow(), exponential_backoff_release_time_);
    125   }
    126 
    127   // The delay is calculated with this formula:
    128   // delay = initial_backoff * multiply_factor^(
    129   //     effective_failure_count - 1) * Uniform(1 - jitter_factor, 1]
    130   // Note: if the failure count is too high, |delay_ms| will become infinity
    131   // after the exponential calculation, and then NaN after the jitter is
    132   // accounted for. Both cases are handled by using CheckedNumeric<int64_t> to
    133   // perform the conversion to integers.
    134   double delay_ms = policy_->initial_delay_ms;
    135   delay_ms *= pow(policy_->multiply_factor, effective_failure_count - 1);
    136   delay_ms -= base::RandDouble() * policy_->jitter_factor * delay_ms;
    137 
    138   // Do overflow checking in microseconds, the internal unit of TimeTicks.
    139   const int64_t kTimeTicksNowUs =
    140       (ImplGetTimeNow() - base::TimeTicks()).InMicroseconds();
    141   base::internal::CheckedNumeric<int64_t> calculated_release_time_us =
    142       delay_ms + 0.5;
    143   calculated_release_time_us *= base::Time::kMicrosecondsPerMillisecond;
    144   calculated_release_time_us += kTimeTicksNowUs;
    145 
    146   const int64_t kMaxTime = std::numeric_limits<int64_t>::max();
    147   base::internal::CheckedNumeric<int64_t> maximum_release_time_us = kMaxTime;
    148   if (policy_->maximum_backoff_ms >= 0) {
    149     maximum_release_time_us = policy_->maximum_backoff_ms;
    150     maximum_release_time_us *= base::Time::kMicrosecondsPerMillisecond;
    151     maximum_release_time_us += kTimeTicksNowUs;
    152   }
    153 
    154   // Decide between maximum release time and calculated release time, accounting
    155   // for overflow with both.
    156   int64_t release_time_us = std::min(
    157       calculated_release_time_us.ValueOrDefault(kMaxTime),
    158       maximum_release_time_us.ValueOrDefault(kMaxTime));
    159 
    160   // Never reduce previously set release horizon, e.g. due to Retry-After
    161   // header.
    162   return std::max(
    163       base::TimeTicks() + base::TimeDelta::FromMicroseconds(release_time_us),
    164       exponential_backoff_release_time_);
    165 }
    166 
    167 }  // namespace brillo
    168