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