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