net/quic/crypto/strike_register.cc

   1 // Copyright (c) 2013 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
   5 #include "net/quic/crypto/strike_register.h"
   6
   7 #include <limits>
   8
   9 #include "base/logging.h"
  10
  11 using std::max;
  12 using std::min;
  13 using std::pair;
  14 using std::set;
  15 using std::vector;
  16
  17 namespace net {
  18
  19 namespace {
  20
  21 uint32 GetInitialHorizon(uint32 current_time_internal,
  22                          uint32 window_secs,
  23                          StrikeRegister::StartupType startup) {
  24   if (startup == StrikeRegister::DENY_REQUESTS_AT_STARTUP) {
  25     // The horizon is initially set |window_secs| into the future because, if
  26     // we just crashed, then we may have accepted nonces in the span
  27     // [current_time...current_time+window_secs] and so we conservatively
  28     // reject the whole timespan unless |startup| tells us otherwise.
  29     return current_time_internal + window_secs + 1;
  30   } else {  // startup == StrikeRegister::NO_STARTUP_PERIOD_NEEDED
  31     // The orbit can be assumed to be globally unique.  Use a horizon
  32     // in the past.
  33     return 0;
  34   }
  35 }
  36
  37 }  // namespace
  38
  39 // static
  40 const uint32 StrikeRegister::kExternalNodeSize = 24;
  41 // static
  42 const uint32 StrikeRegister::kNil = (1u << 31) | 1;
  43 // static
  44 const uint32 StrikeRegister::kExternalFlag = 1 << 23;
  45
  46 // InternalNode represents a non-leaf node in the critbit tree. See the comment
  47 // in the .h file for details.
  48 class StrikeRegister::InternalNode {
  49  public:
  50   void SetChild(unsigned direction, uint32 child) {
  51     data_[direction] = (data_[direction] & 0xff) | (child << 8);
  52   }
  53
  54   void SetCritByte(uint8 critbyte) {
  55     data_[0] = (data_[0] & 0xffffff00) | critbyte;
  56   }
  57
  58   void SetOtherBits(uint8 otherbits) {
  59     data_[1] = (data_[1] & 0xffffff00) | otherbits;
  60   }
  61
  62   void SetNextPtr(uint32 next) { data_[0] = next; }
  63
  64   uint32 next() const { return data_[0]; }
  65
  66   uint32 child(unsigned n) const { return data_[n] >> 8; }
  67
  68   uint8 critbyte() const { return static_cast<uint8>(data_[0]); }
  69
  70   uint8 otherbits() const { return static_cast<uint8>(data_[1]); }
  71
  72   // These bytes are organised thus:
  73   //   <24 bits> left child
  74   //   <8 bits> crit-byte
  75   //   <24 bits> right child
  76   //   <8 bits> other-bits
  77   uint32 data_[2];
  78 };
  79
  80 // kCreationTimeFromInternalEpoch contains the number of seconds between the
  81 // start of the internal epoch and the creation time. This allows us
  82 // to consider times that are before the creation time.
  83 static const uint32 kCreationTimeFromInternalEpoch = 63115200;  // 2 years.
  84
  85 void StrikeRegister::ValidateStrikeRegisterConfig(unsigned max_entries) {
  86   // We only have 23 bits of index available.
  87   CHECK_LT(max_entries, 1u << 23);
  88   CHECK_GT(max_entries, 1u);           // There must be at least two entries.
  89   CHECK_EQ(sizeof(InternalNode), 8u);  // in case of compiler changes.
  90 }
  91
  92 StrikeRegister::StrikeRegister(unsigned max_entries,
  93                                uint32 current_time,
  94                                uint32 window_secs,
  95                                const uint8 orbit[8],
  96                                StartupType startup)
  97     : max_entries_(max_entries),
  98       window_secs_(window_secs),
  99       internal_epoch_(current_time > kCreationTimeFromInternalEpoch
 100                           ? current_time - kCreationTimeFromInternalEpoch
 101                           : 0),
 102       horizon_(GetInitialHorizon(
 103           ExternalTimeToInternal(current_time), window_secs, startup)) {
 104   memcpy(orbit_, orbit, sizeof(orbit_));
 105
 106   ValidateStrikeRegisterConfig(max_entries);
 107   internal_nodes_ = new InternalNode[max_entries];
 108   external_nodes_.reset(new uint8[kExternalNodeSize * max_entries]);
 109
 110   Reset();
 111 }
 112
 113 StrikeRegister::~StrikeRegister() { delete[] internal_nodes_; }
 114
 115 void StrikeRegister::Reset() {
 116   // Thread a free list through all of the internal nodes.
 117   internal_node_free_head_ = 0;
 118   for (unsigned i = 0; i < max_entries_ - 1; i++) {
 119     internal_nodes_[i].SetNextPtr(i + 1);
 120   }
 121   internal_nodes_[max_entries_ - 1].SetNextPtr(kNil);
 122
 123   // Also thread a free list through the external nodes.
 124   external_node_free_head_ = 0;
 125   for (unsigned i = 0; i < max_entries_ - 1; i++) {
 126     external_node_next_ptr(i) = i + 1;
 127   }
 128   external_node_next_ptr(max_entries_ - 1) = kNil;
 129
 130   // This is the root of the tree.
 131   internal_node_head_ = kNil;
 132 }
 133
 134 InsertStatus StrikeRegister::Insert(const uint8 nonce[32],
 135                                     uint32 current_time_external) {
 136   // Make space for the insertion if the strike register is full.
 137   while (external_node_free_head_ == kNil ||
 138          internal_node_free_head_ == kNil) {
 139     DropOldestNode();
 140   }
 141
 142   const uint32 current_time = ExternalTimeToInternal(current_time_external);
 143
 144   // Check to see if the orbit is correct.
 145   if (memcmp(nonce + sizeof(current_time), orbit_, sizeof(orbit_))) {
 146     return NONCE_INVALID_ORBIT_FAILURE;
 147   }
 148
 149   const uint32 nonce_time = ExternalTimeToInternal(TimeFromBytes(nonce));
 150
 151   // Check that the timestamp is in the valid range.
 152   pair<uint32, uint32> valid_range =
 153       StrikeRegister::GetValidRange(current_time);
 154   if (nonce_time < valid_range.first || nonce_time > valid_range.second) {
 155     return NONCE_INVALID_TIME_FAILURE;
 156   }
 157
 158   // We strip the orbit out of the nonce.
 159   uint8 value[24];
 160   memcpy(value, nonce, sizeof(nonce_time));
 161   memcpy(value + sizeof(nonce_time),
 162          nonce + sizeof(nonce_time) + sizeof(orbit_),
 163          sizeof(value) - sizeof(nonce_time));
 164
 165   // Find the best match to |value| in the crit-bit tree. The best match is
 166   // simply the value which /could/ match |value|, if any does, so we still
 167   // need a memcmp to check.
 168   uint32 best_match_index = BestMatch(value);
 169   if (best_match_index == kNil) {
 170     // Empty tree. Just insert the new value at the root.
 171     uint32 index = GetFreeExternalNode();
 172     memcpy(external_node(index), value, sizeof(value));
 173     internal_node_head_ = (index | kExternalFlag) << 8;
 174     DCHECK_LE(horizon_, nonce_time);
 175     return NONCE_OK;
 176   }
 177
 178   const uint8* best_match = external_node(best_match_index);
 179   if (memcmp(best_match, value, sizeof(value)) == 0) {
 180     // We found the value in the tree.
 181     return NONCE_NOT_UNIQUE_FAILURE;
 182   }
 183
 184   // We are going to insert a new entry into the tree, so get the nodes now.
 185   uint32 internal_node_index = GetFreeInternalNode();
 186   uint32 external_node_index = GetFreeExternalNode();
 187
 188   // If we just evicted the best match, then we have to try and match again.
 189   // We know that we didn't just empty the tree because we require that
 190   // max_entries_ >= 2. Also, we know that it doesn't match because, if it
 191   // did, it would have been returned previously.
 192   if (external_node_index == best_match_index) {
 193     best_match_index = BestMatch(value);
 194     best_match = external_node(best_match_index);
 195   }
 196
 197   // Now we need to find the first bit where we differ from |best_match|.
 198   uint8 differing_byte;
 199   uint8 new_other_bits;
 200   for (differing_byte = 0; differing_byte < arraysize(value);
 201        differing_byte++) {
 202     new_other_bits = value[differing_byte] ^ best_match[differing_byte];
 203     if (new_other_bits) {
 204       break;
 205     }
 206   }
 207
 208   // Once we have the XOR the of first differing byte in new_other_bits we need
 209   // to find the most significant differing bit. We could do this with a simple
 210   // for loop, testing bits 7..0. Instead we fold the bits so that we end up
 211   // with a byte where all the bits below the most significant one, are set.
 212   new_other_bits |= new_other_bits >> 1;
 213   new_other_bits |= new_other_bits >> 2;
 214   new_other_bits |= new_other_bits >> 4;
 215   // Now this bit trick results in all the bits set, except the original
 216   // most-significant one.
 217   new_other_bits = (new_other_bits & ~(new_other_bits >> 1)) ^ 255;
 218
 219   // Consider the effect of ORing against |new_other_bits|. If |value| did not
 220   // have the critical bit set, the result is the same as |new_other_bits|. If
 221   // it did, the result is all ones.
 222
 223   unsigned newdirection;
 224   if ((new_other_bits | value[differing_byte]) == 0xff) {
 225     newdirection = 1;
 226   } else {
 227     newdirection = 0;
 228   }
 229
 230   memcpy(external_node(external_node_index), value, sizeof(value));
 231   InternalNode* inode = &internal_nodes_[internal_node_index];
 232
 233   inode->SetChild(newdirection, external_node_index | kExternalFlag);
 234   inode->SetCritByte(differing_byte);
 235   inode->SetOtherBits(new_other_bits);
 236
 237   // |where_index| is a pointer to the uint32 which needs to be updated in
 238   // order to insert the new internal node into the tree. The internal nodes
 239   // store the child indexes in the top 24-bits of a 32-bit word and, to keep
 240   // the code simple, we define that |internal_node_head_| is organised the
 241   // same way.
 242   DCHECK_EQ(internal_node_head_ & 0xff, 0u);
 243   uint32* where_index = &internal_node_head_;
 244   while (((*where_index >> 8) & kExternalFlag) == 0) {
 245     InternalNode* node = &internal_nodes_[*where_index >> 8];
 246     if (node->critbyte() > differing_byte) {
 247       break;
 248     }
 249     if (node->critbyte() == differing_byte &&
 250         node->otherbits() > new_other_bits) {
 251       break;
 252     }
 253     if (node->critbyte() == differing_byte &&
 254         node->otherbits() == new_other_bits) {
 255       CHECK(false);
 256     }
 257
 258     uint8 c = value[node->critbyte()];
 259     const int direction =
 260         (1 + static_cast<unsigned>(node->otherbits() | c)) >> 8;
 261     where_index = &node->data_[direction];
 262   }
 263
 264   inode->SetChild(newdirection ^ 1, *where_index >> 8);
 265   *where_index = (*where_index & 0xff) | (internal_node_index << 8);
 266
 267   DCHECK_LE(horizon_, nonce_time);
 268   return NONCE_OK;
 269 }
 270
 271 const uint8* StrikeRegister::orbit() const {
 272   return orbit_;
 273 }
 274
 275 uint32 StrikeRegister::GetCurrentValidWindowSecs(
 276     uint32 current_time_external) const {
 277   uint32 current_time = ExternalTimeToInternal(current_time_external);
 278   pair<uint32, uint32> valid_range = StrikeRegister::GetValidRange(
 279       current_time);
 280   if (valid_range.second >= valid_range.first) {
 281     return valid_range.second - current_time + 1;
 282   } else {
 283     return 0;
 284   }
 285 }
 286
 287 void StrikeRegister::Validate() {
 288   set<uint32> free_internal_nodes;
 289   for (uint32 i = internal_node_free_head_; i != kNil;
 290        i = internal_nodes_[i].next()) {
 291     CHECK_LT(i, max_entries_);
 292     CHECK_EQ(free_internal_nodes.count(i), 0u);
 293     free_internal_nodes.insert(i);
 294   }
 295
 296   set<uint32> free_external_nodes;
 297   for (uint32 i = external_node_free_head_; i != kNil;
 298        i = external_node_next_ptr(i)) {
 299     CHECK_LT(i, max_entries_);
 300     CHECK_EQ(free_external_nodes.count(i), 0u);
 301     free_external_nodes.insert(i);
 302   }
 303
 304   set<uint32> used_external_nodes;
 305   set<uint32> used_internal_nodes;
 306
 307   if (internal_node_head_ != kNil &&
 308       ((internal_node_head_ >> 8) & kExternalFlag) == 0) {
 309     vector<pair<unsigned, bool>> bits;
 310     ValidateTree(internal_node_head_ >> 8, -1, bits, free_internal_nodes,
 311                  free_external_nodes, &used_internal_nodes,
 312                  &used_external_nodes);
 313   }
 314 }
 315
 316 // static
 317 uint32 StrikeRegister::TimeFromBytes(const uint8 d[4]) {
 318   return static_cast<uint32>(d[0]) << 24 |
 319          static_cast<uint32>(d[1]) << 16 |
 320          static_cast<uint32>(d[2]) << 8 |
 321          static_cast<uint32>(d[3]);
 322 }
 323
 324 pair<uint32, uint32> StrikeRegister::GetValidRange(
 325     uint32 current_time_internal) const {
 326   if (current_time_internal < horizon_) {
 327     // Empty valid range.
 328     return std::make_pair(std::numeric_limits<uint32>::max(), 0);
 329   }
 330
 331   uint32 lower_bound;
 332   if (current_time_internal >= window_secs_) {
 333     lower_bound = max(horizon_, current_time_internal - window_secs_);
 334   } else {
 335     lower_bound = horizon_;
 336   }
 337
 338   // Also limit the upper range based on horizon_.  This makes the
 339   // strike register reject inserts that are far in the future and
 340   // would consume strike register resources for a long time.  This
 341   // allows the strike server to degrade optimally in cases where the
 342   // insert rate exceeds |max_entries_ / (2 * window_secs_)| entries
 343   // per second.
 344   uint32 upper_bound =
 345       current_time_internal + min(current_time_internal - horizon_,
 346                                   window_secs_);
 347
 348   return std::make_pair(lower_bound, upper_bound);
 349 }
 350
 351 uint32 StrikeRegister::ExternalTimeToInternal(uint32 external_time) const {
 352   return external_time - internal_epoch_;
 353 }
 354
 355 uint32 StrikeRegister::BestMatch(const uint8 v[24]) const {
 356   if (internal_node_head_ == kNil) {
 357     return kNil;
 358   }
 359
 360   uint32 next = internal_node_head_ >> 8;
 361   while ((next & kExternalFlag) == 0) {
 362     InternalNode* node = &internal_nodes_[next];
 363     uint8 b = v[node->critbyte()];
 364     unsigned direction =
 365         (1 + static_cast<unsigned>(node->otherbits() | b)) >> 8;
 366     next = node->child(direction);
 367   }
 368
 369   return next & ~kExternalFlag;
 370 }
 371
 372 uint32& StrikeRegister::external_node_next_ptr(unsigned i) {
 373   return *reinterpret_cast<uint32*>(&external_nodes_[i * kExternalNodeSize]);
 374 }
 375
 376 uint8* StrikeRegister::external_node(unsigned i) {
 377   return &external_nodes_[i * kExternalNodeSize];
 378 }
 379
 380 uint32 StrikeRegister::GetFreeExternalNode() {
 381   uint32 index = external_node_free_head_;
 382   DCHECK(index != kNil);
 383   external_node_free_head_ = external_node_next_ptr(index);
 384   return index;
 385 }
 386
 387 uint32 StrikeRegister::GetFreeInternalNode() {
 388   uint32 index = internal_node_free_head_;
 389   DCHECK(index != kNil);
 390   internal_node_free_head_ = internal_nodes_[index].next();
 391   return index;
 392 }
 393
 394 void StrikeRegister::DropOldestNode() {
 395   // DropOldestNode should never be called on an empty tree.
 396   DCHECK(internal_node_head_ != kNil);
 397
 398   // An internal node in a crit-bit tree always has exactly two children.
 399   // This means that, if we are removing an external node (which is one of
 400   // those children), then we also need to remove an internal node. In order
 401   // to do that we keep pointers to the parent (wherep) and grandparent
 402   // (whereq) when walking down the tree.
 403
 404   uint32 p = internal_node_head_ >> 8, *wherep = &internal_node_head_,
 405          *whereq = nullptr;
 406   while ((p & kExternalFlag) == 0) {
 407     whereq = wherep;
 408     InternalNode* inode = &internal_nodes_[p];
 409     // We always go left, towards the smallest element, exploiting the fact
 410     // that the timestamp is big-endian and at the start of the value.
 411     wherep = &inode->data_[0];
 412     p = (*wherep) >> 8;
 413   }
 414
 415   const uint32 ext_index = p & ~kExternalFlag;
 416   const uint8* ext_node = external_node(ext_index);
 417   uint32 new_horizon = ExternalTimeToInternal(TimeFromBytes(ext_node)) + 1;
 418   DCHECK_LE(horizon_, new_horizon);
 419   horizon_ = new_horizon;
 420
 421   if (!whereq) {
 422     // We are removing the last element in a tree.
 423     internal_node_head_ = kNil;
 424     FreeExternalNode(ext_index);
 425     return;
 426   }
 427
 428   // |wherep| points to the left child pointer in the parent so we can add
 429   // one and dereference to get the right child.
 430   const uint32 other_child = wherep[1];
 431   FreeInternalNode((*whereq) >> 8);
 432   *whereq = (*whereq & 0xff) | (other_child & 0xffffff00);
 433   FreeExternalNode(ext_index);
 434 }
 435
 436 void StrikeRegister::FreeExternalNode(uint32 index) {
 437   external_node_next_ptr(index) = external_node_free_head_;
 438   external_node_free_head_ = index;
 439 }
 440
 441 void StrikeRegister::FreeInternalNode(uint32 index) {
 442   internal_nodes_[index].SetNextPtr(internal_node_free_head_);
 443   internal_node_free_head_ = index;
 444 }
 445
 446 void StrikeRegister::ValidateTree(uint32 internal_node,
 447                                   int last_bit,
 448                                   const vector<pair<unsigned, bool>>& bits,
 449                                   const set<uint32>& free_internal_nodes,
 450                                   const set<uint32>& free_external_nodes,
 451                                   set<uint32>* used_internal_nodes,
 452                                   set<uint32>* used_external_nodes) {
 453   CHECK_LT(internal_node, max_entries_);
 454   const InternalNode* i = &internal_nodes_[internal_node];
 455   unsigned bit = 0;
 456   switch (i->otherbits()) {
 457     case 0xff & ~(1 << 7):
 458       bit = 0;
 459       break;
 460     case 0xff & ~(1 << 6):
 461       bit = 1;
 462       break;
 463     case 0xff & ~(1 << 5):
 464       bit = 2;
 465       break;
 466     case 0xff & ~(1 << 4):
 467       bit = 3;
 468       break;
 469     case 0xff & ~(1 << 3):
 470       bit = 4;
 471       break;
 472     case 0xff & ~(1 << 2):
 473       bit = 5;
 474       break;
 475     case 0xff & ~(1 << 1):
 476       bit = 6;
 477       break;
 478     case 0xff & ~1:
 479       bit = 7;
 480       break;
 481     default:
 482       CHECK(false);
 483   }
 484
 485   bit += 8 * i->critbyte();
 486   if (last_bit > -1) {
 487     CHECK_GT(bit, static_cast<unsigned>(last_bit));
 488   }
 489
 490   CHECK_EQ(free_internal_nodes.count(internal_node), 0u);
 491
 492   for (unsigned child = 0; child < 2; child++) {
 493     if (i->child(child) & kExternalFlag) {
 494       uint32 ext = i->child(child) & ~kExternalFlag;
 495       CHECK_EQ(free_external_nodes.count(ext), 0u);
 496       CHECK_EQ(used_external_nodes->count(ext), 0u);
 497       used_external_nodes->insert(ext);
 498       const uint8* bytes = external_node(ext);
 499       for (const pair<unsigned, bool>& pair : bits) {
 500         unsigned byte = pair.first / 8;
 501         DCHECK_LE(byte, 0xffu);
 502         unsigned bit_new = pair.first % 8;
 503         static const uint8 kMasks[8] =
 504             {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
 505         CHECK_EQ((bytes[byte] & kMasks[bit_new]) != 0, pair.second);
 506       }
 507     } else {
 508       uint32 inter = i->child(child);
 509       vector<pair<unsigned, bool>> new_bits(bits);
 510       new_bits.push_back(pair<unsigned, bool>(bit, child != 0));
 511       CHECK_EQ(free_internal_nodes.count(inter), 0u);
 512       CHECK_EQ(used_internal_nodes->count(inter), 0u);
 513       used_internal_nodes->insert(inter);
 514       ValidateTree(inter, bit, bits, free_internal_nodes, free_external_nodes,
 515                    used_internal_nodes, used_external_nodes);
 516     }
 517   }
 518 }
 519
 520 }  // namespace net