backoff_entry.cc 7.2 KB

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