Narrow the strike register window in both directions when tracking many

net/quic/crypto/strike_register.cc

 // Copyright (c) 2013 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/quic/crypto/strike_register.h"
 
+#include <limits>
+
 #include "base/logging.h"
 
+using std::make_pair;
+using std::max;
 using std::min;
 using std::pair;
 using std::set;
 using std::vector;
 
 namespace net {
 
 namespace {
 
 uint32 GetInitialHorizon(uint32 current_time_internal,
@@ skipping 51 matching lines @@
   //   <24 bits> left child
   //   <8 bits> crit-byte
   //   <24 bits> right child
   //   <8 bits> other-bits
   uint32 data_[2];
 };
 
 // kCreationTimeFromInternalEpoch contains the number of seconds between the
 // start of the internal epoch and the creation time. This allows us
 // to consider times that are before the creation time.
-static const uint32 kCreationTimeFromInternalEpoch = 63115200.0;  // 2 years.
+static const uint32 kCreationTimeFromInternalEpoch = 63115200;  // 2 years.
 
 void StrikeRegister::ValidateStrikeRegisterConfig(unsigned max_entries) {
   // We only have 23 bits of index available.
   CHECK_LT(max_entries, 1u << 23);
   CHECK_GT(max_entries, 1u);           // There must be at least two entries.
   CHECK_EQ(sizeof(InternalNode), 8u);  // in case of compiler changes.
 }
 
 StrikeRegister::StrikeRegister(unsigned max_entries,
                                uint32 current_time,
@@ skipping 29 matching lines @@
   external_node_free_head_ = 0;
   for (unsigned i = 0; i < max_entries_ - 1; i++)
     external_node_next_ptr(i) = i + 1;
   external_node_next_ptr(max_entries_ - 1) = kNil;
 
   // This is the root of the tree.
   internal_node_head_ = kNil;
 }
 
 bool StrikeRegister::Insert(const uint8 nonce[32],
-                            const uint32 current_time_external) {
+                            uint32 current_time_external) {
   // Make space for the insertion if the strike register is full.
   while (external_node_free_head_ == kNil ||
          internal_node_free_head_ == kNil) {
     DropOldestNode();
   }
 
   const uint32 current_time = ExternalTimeToInternal(current_time_external);
 
   // Check to see if the orbit is correct.
   if (memcmp(nonce + sizeof(current_time), orbit_, sizeof(orbit_))) {
     return false;
   }
+
   const uint32 nonce_time = ExternalTimeToInternal(TimeFromBytes(nonce));
-  // We have dropped one or more nonces with a time value of |horizon_ - 1|, so
-  // we have to reject anything with a timestamp less than or equal to that.
-  if (nonce_time < horizon_) {
+
+  // Check that the timestamp is in the valid range.
+  pair<uint32, uint32> valid_range =
+      StrikeRegister::GetValidRange(current_time);
+  if (nonce_time < valid_range.first || nonce_time > valid_range.second) {
     return false;
   }
 
-  // Check that the timestamp is in the current window.
-  if ((current_time > window_secs_ &&
-       nonce_time < (current_time - window_secs_)) ||
-      nonce_time > (current_time + window_secs_)) {
-    return false;
-  }
-
   // We strip the orbit out of the nonce.
   uint8 value[24];
   memcpy(value, nonce, sizeof(nonce_time));
   memcpy(value + sizeof(nonce_time),
          nonce + sizeof(nonce_time) + sizeof(orbit_),
          sizeof(value) - sizeof(nonce_time));
 
   // Find the best match to |value| in the crit-bit tree. The best match is
   // simply the value which /could/ match |value|, if any does, so we still
   // need a memcmp to check.
@@ skipping 96 matching lines @@
   *where_index = (*where_index & 0xff) | (internal_node_index << 8);
 
   DCHECK_LE(horizon_, nonce_time);
   return true;
 }
 
 const uint8* StrikeRegister::orbit() const {
   return orbit_;
 }
 
-uint32 StrikeRegister::EffectiveWindowSecs(
-    const uint32 current_time_external) const {
-  const uint32 future_horizon =
-      ExternalTimeToInternal(current_time_external) + window_secs_;
-
-  if (horizon_ >= future_horizon) {
+uint32 StrikeRegister::GetCurrentValidWindowSecs(
+    uint32 current_time_external) const {
+  uint32 current_time = ExternalTimeToInternal(current_time_external);
+  pair<uint32, uint32> valid_range = StrikeRegister::GetValidRange(
+      current_time);
+  if (valid_range.second >= valid_range.first) {
+    return valid_range.second - current_time + 1;
+  } else {
     return 0;
   }
-  return min(future_horizon - horizon_, 2 * window_secs_);
 }
 
 void StrikeRegister::Validate() {
   set<uint32> free_internal_nodes;
   for (uint32 i = internal_node_free_head_; i != kNil;
        i = internal_nodes_[i].next()) {
     CHECK_LT(i, max_entries_);
     CHECK_EQ(free_internal_nodes.count(i), 0u);
     free_internal_nodes.insert(i);
   }
@@ skipping 19 matching lines @@
 }
 
 // static
 uint32 StrikeRegister::TimeFromBytes(const uint8 d[4]) {
   return static_cast<uint32>(d[0]) << 24 |
          static_cast<uint32>(d[1]) << 16 |
          static_cast<uint32>(d[2]) << 8 |
          static_cast<uint32>(d[3]);
 }
 
+pair<uint32, uint32> StrikeRegister::GetValidRange(
+    uint32 current_time_internal) const {
+  if (current_time_internal < horizon_) {
+    // Empty valid range.
+    return make_pair(std::numeric_limits<uint32>::max(), 0);
+  }
+
+  uint32 lower_bound;
+  if (current_time_internal >= window_secs_) {
+    lower_bound = max(horizon_, current_time_internal - window_secs_);
+  } else {
+    lower_bound = horizon_;
+  }
+
+  // Also limit the upper range based on horizon_.  This makes the
+  // strike register reject inserts that are far in the future and
+  // would consume strike register resources for a long time.  This
+  // allows the strike server to degrade optimally in cases where the
+  // insert rate exceeds |max_entries_ / (2 * window_secs_)| entries
+  // per second.
+  uint32 upper_bound =
+      current_time_internal + min(current_time_internal - horizon_,
+                                  window_secs_);
+
+  return make_pair(lower_bound, upper_bound);
+}
+
 uint32 StrikeRegister::ExternalTimeToInternal(uint32 external_time) const {
   return external_time - internal_epoch_;
 }
 
 uint32 StrikeRegister::BestMatch(const uint8 v[24]) const {
   if (internal_node_head_ == kNil) {
     return kNil;
   }
 
   uint32 next = internal_node_head_ >> 8;
@@ skipping 152 matching lines @@
       CHECK_EQ(free_internal_nodes.count(inter), 0u);
       CHECK_EQ(used_internal_nodes->count(inter), 0u);
       used_internal_nodes->insert(inter);
       ValidateTree(inter, bit, bits, free_internal_nodes, free_external_nodes,
                    used_internal_nodes, used_external_nodes);
     }
   }
 }
 
 }  // namespace net