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