Backoff: Respect maximum delay in face of float overflow

net/base/backoff_entry.cc

 // Copyright (c) 2012 The Chromium 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 "net/base/backoff_entry.h"
 
 #include <algorithm>
 #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 {
 
 BackoffEntry::BackoffEntry(const BackoffEntry::Policy* const policy)
     : policy_(policy) {
   DCHECK(policy_);
   Reset();
 }
 
@@ skipping 103 matching lines @@
 
   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]
-  double delay = policy_->initial_delay_ms;
-  delay *= pow(policy_->multiply_factor, effective_failure_count - 1);
-  delay -= base::RandDouble() * policy_->jitter_factor * delay;
+  // 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;
 
-  const int64 kMaxInt64 = std::numeric_limits<int64>::max();
-  int64 delay_int = (delay > kMaxInt64) ?
-      kMaxInt64 : static_cast<int64>(delay + 0.5);
+  // 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.
-  if (policy_->maximum_backoff_ms >= 0)
-    delay_int = std::min(delay_int, policy_->maximum_backoff_ms);
+  // 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_);
 }
 
 }  // namespace net