Backoff: Respect maximum delay in face of float overflow

net/base/backoff_entry.cc

Index: net/base/backoff_entry.cc
diff --git a/net/base/backoff_entry.cc b/net/base/backoff_entry.cc
index b1826b7af469b4d72cfccd6ad849173ceb1f24fe..f2753935620e20f662426a87bc79a82d82554a50 100644
--- a/net/base/backoff_entry.cc
+++ b/net/base/backoff_entry.cc
@@ -8,7 +8,9 @@
 #include <cmath>
 #include <limits>
 
+#include "base/basictypes.h"
 #include "base/logging.h"
+#include "base/numerics/safe_math.h"
 #include "base/rand_util.h"
 
 namespace net {
@@ -132,22 +134,36 @@ base::TimeTicks BackoffEntry::CalculateReleaseTime() const {
   // The delay is calculated with this formula:
   // delay = initial_backoff * multiply_factor^(
   //     effective_failure_count - 1) * Uniform(1 - jitter_factor, 1]
-  double delay = policy_->initial_delay_ms;
-  delay *= pow(policy_->multiply_factor, effective_failure_count - 1);
-  delay -= base::RandDouble() * policy_->jitter_factor * delay;
-
-  const int64 kMaxInt64 = std::numeric_limits<int64>::max();
-  int64 delay_int = (delay > kMaxInt64) ?
-      kMaxInt64 : static_cast<int64>(delay + 0.5);
-
-  // Ensure that we do not exceed maximum delay.
-  if (policy_->maximum_backoff_ms >= 0)
-    delay_int = std::min(delay_int, policy_->maximum_backoff_ms);
+  // 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> 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 kTimeTicksNowUs =
+      (ImplGetTimeNow() - base::TimeTicks()).InMicroseconds();
+  base::internal::CheckedNumeric<int64> checked_release_time_us =

[cbentzel, 2014/06/16 21:08:32]

NaN to integer conversion is undefined, not sure if we want to do this. I
_think_ what is happening here from reading CheckedNumeric is that first the
double operation (delay_ms + 0.5) happens, followed by the implicit integral
conversion (which is potentially undefined), followed by the CheckedNumeric
constructor call. 

[Nicolas Zea, 2014/06/17 00:33:29]

CheckedNumeric, from my understanding of the code, uses template specialization
to handle the casts from float to integer and vice versa (see the comment about
implicitly converting and overloading arithmetic).

Looking at the code, the double(NaN) assignment is handled by the copy
constructor for CheckedNumericState, which is itself templated based on the src
type, and therefore invokes the DstRangeRelationToSrcRange functions, which are
themselves specialized.

[Ryan Sleevi, 2014/06/17 20:02:12]

I believe Nicolas is correct.

That is, it invokes

template <typename Src = double> CheckedNumeric<int64>::CheckedNumeric(double
arg);

which initializes
template <typename Src = double>
CheckedNumericState<int64>::CheckedNumericState(double arg);

It then will static_cast<int64>(arg), and set validity_ to
DstRangeRelationToSrcRange<int64, float>(arg)

+      delay_ms + 0.5;
+  checked_release_time_us *= base::Time::kMicrosecondsPerMillisecond;
+  checked_release_time_us += kTimeTicksNowUs;
+
+  // Ensure that we do not exceed maximum delay once overflow is accounted for.
+  int64 release_time_us = (policy_->maximum_backoff_ms >= 0
+                               ? kTimeTicksNowUs +
+                                     base::Time::kMicrosecondsPerMillisecond *
+                                         policy_->maximum_backoff_ms

[Ryan Sleevi, 2014/06/16 22:12:47]

Can't this still overflow?

[Nicolas Zea, 2014/06/17 00:33:29]

Hmm, I suppose if a developer gives a massive/invalid maximum backoff. That
seems like an error in the policy though, and better enforced by having
constraints on what valid max backoff values are allowed, rather than here.
WDYT?

[Ryan Sleevi, 2014/06/17 20:02:12]

*shrug* I agree, it's likely an error in policy, but that policy is dependent
upon what you do with maximum_backoff_ms (which, in this case, is added to
kTimeTicksNowUs), so it feels like the check should be here.

[Nicolas Zea, 2014/06/17 21:31:43]

Done.

+                               : kint64max);
+  release_time_us =
+      std::min(checked_release_time_us.ValueOrDefault(release_time_us),
+               release_time_us);
 
   // Never reduce previously set release horizon, e.g. due to Retry-After
   // header.
   return std::max(
-      ImplGetTimeNow() + base::TimeDelta::FromMilliseconds(delay_int),
+      base::TimeTicks() + base::TimeDelta::FromMicroseconds(release_time_us),

[Ryan Sleevi, 2014/06/16 22:12:47]

Can't this still overflow?

[Nicolas Zea, 2014/06/17 00:33:29]

base::TimeTicks() is a 0 value, this is just for creating a TimeTicks object,
not doing any actual arithmetic. Similarly, TimeTicks/TimeDelta use int64
microseconds internally, so this isn't converting to different units.

       exponential_backoff_release_time_);
 }