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