| // 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, |
| uint32 window_secs, |
| StrikeRegister::StartupType startup) { |
| if (startup == StrikeRegister::DENY_REQUESTS_AT_STARTUP) { |
| // The horizon is initially set |window_secs| into the future because, if |
| // we just crashed, then we may have accepted nonces in the span |
| // [current_time...current_time+window_secs] and so we conservatively |
| // reject the whole timespan unless |startup| tells us otherwise. |
| return current_time_internal + window_secs + 1; |
| } else { // startup == StrikeRegister::NO_STARTUP_PERIOD_NEEDED |
| // The orbit can be assumed to be globally unique. Use a horizon |
| // in the past. |
| return 0; |
| } |
| } |
| |
| } // namespace |
| |
| // static |
| const uint32 StrikeRegister::kExternalNodeSize = 24; |
| // static |
| const uint32 StrikeRegister::kNil = (1u << 31) | 1; |
| // static |
| const uint32 StrikeRegister::kExternalFlag = 1 << 23; |
| |
| // InternalNode represents a non-leaf node in the critbit tree. See the comment |
| // in the .h file for details. |
| class StrikeRegister::InternalNode { |
| public: |
| void SetChild(unsigned direction, uint32 child) { |
| data_[direction] = (data_[direction] & 0xff) | (child << 8); |
| } |
| |
| void SetCritByte(uint8 critbyte) { |
| data_[0] = (data_[0] & 0xffffff00) | critbyte; |
| } |
| |
| void SetOtherBits(uint8 otherbits) { |
| data_[1] = (data_[1] & 0xffffff00) | otherbits; |
| } |
| |
| void SetNextPtr(uint32 next) { data_[0] = next; } |
| |
| uint32 next() const { return data_[0]; } |
| |
| uint32 child(unsigned n) const { return data_[n] >> 8; } |
| |
| uint8 critbyte() const { return data_[0]; } |
| |
| uint8 otherbits() const { return data_[1]; } |
| |
| // These bytes are organised thus: |
| // <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; // 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, |
| uint32 window_secs, |
| const uint8 orbit[8], |
| StartupType startup) |
| : max_entries_(max_entries), |
| window_secs_(window_secs), |
| internal_epoch_(current_time > kCreationTimeFromInternalEpoch |
| ? current_time - kCreationTimeFromInternalEpoch |
| : 0), |
| horizon_(GetInitialHorizon( |
| ExternalTimeToInternal(current_time), window_secs, startup)) { |
| memcpy(orbit_, orbit, sizeof(orbit_)); |
| |
| ValidateStrikeRegisterConfig(max_entries); |
| internal_nodes_ = new InternalNode[max_entries]; |
| external_nodes_.reset(new uint8[kExternalNodeSize * max_entries]); |
| |
| Reset(); |
| } |
| |
| StrikeRegister::~StrikeRegister() { delete[] internal_nodes_; } |
| |
| void StrikeRegister::Reset() { |
| // Thread a free list through all of the internal nodes. |
| internal_node_free_head_ = 0; |
| for (unsigned i = 0; i < max_entries_ - 1; i++) |
| internal_nodes_[i].SetNextPtr(i + 1); |
| internal_nodes_[max_entries_ - 1].SetNextPtr(kNil); |
| |
| // Also thread a free list through the external nodes. |
| 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; |
| } |
| |
| InsertStatus StrikeRegister::Insert(const uint8 nonce[32], |
| 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 NONCE_INVALID_ORBIT_FAILURE; |
| } |
| |
| const uint32 nonce_time = ExternalTimeToInternal(TimeFromBytes(nonce)); |
| |
| // 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 NONCE_INVALID_TIME_FAILURE; |
| } |
| |
| // 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. |
| uint32 best_match_index = BestMatch(value); |
| if (best_match_index == kNil) { |
| // Empty tree. Just insert the new value at the root. |
| uint32 index = GetFreeExternalNode(); |
| memcpy(external_node(index), value, sizeof(value)); |
| internal_node_head_ = (index | kExternalFlag) << 8; |
| DCHECK_LE(horizon_, nonce_time); |
| return NONCE_OK; |
| } |
| |
| const uint8* best_match = external_node(best_match_index); |
| if (memcmp(best_match, value, sizeof(value)) == 0) { |
| // We found the value in the tree. |
| return NONCE_NOT_UNIQUE_FAILURE; |
| } |
| |
| // We are going to insert a new entry into the tree, so get the nodes now. |
| uint32 internal_node_index = GetFreeInternalNode(); |
| uint32 external_node_index = GetFreeExternalNode(); |
| |
| // If we just evicted the best match, then we have to try and match again. |
| // We know that we didn't just empty the tree because we require that |
| // max_entries_ >= 2. Also, we know that it doesn't match because, if it |
| // did, it would have been returned previously. |
| if (external_node_index == best_match_index) { |
| best_match_index = BestMatch(value); |
| best_match = external_node(best_match_index); |
| } |
| |
| // Now we need to find the first bit where we differ from |best_match|. |
| unsigned differing_byte; |
| uint8 new_other_bits; |
| for (differing_byte = 0; differing_byte < sizeof(value); differing_byte++) { |
| new_other_bits = value[differing_byte] ^ best_match[differing_byte]; |
| if (new_other_bits) { |
| break; |
| } |
| } |
| |
| // Once we have the XOR the of first differing byte in new_other_bits we need |
| // to find the most significant differing bit. We could do this with a simple |
| // for loop, testing bits 7..0. Instead we fold the bits so that we end up |
| // with a byte where all the bits below the most significant one, are set. |
| new_other_bits |= new_other_bits >> 1; |
| new_other_bits |= new_other_bits >> 2; |
| new_other_bits |= new_other_bits >> 4; |
| // Now this bit trick results in all the bits set, except the original |
| // most-significant one. |
| new_other_bits = (new_other_bits & ~(new_other_bits >> 1)) ^ 255; |
| |
| // Consider the effect of ORing against |new_other_bits|. If |value| did not |
| // have the critical bit set, the result is the same as |new_other_bits|. If |
| // it did, the result is all ones. |
| |
| unsigned newdirection; |
| if ((new_other_bits | value[differing_byte]) == 0xff) { |
| newdirection = 1; |
| } else { |
| newdirection = 0; |
| } |
| |
| memcpy(external_node(external_node_index), value, sizeof(value)); |
| InternalNode* inode = &internal_nodes_[internal_node_index]; |
| |
| inode->SetChild(newdirection, external_node_index | kExternalFlag); |
| inode->SetCritByte(differing_byte); |
| inode->SetOtherBits(new_other_bits); |
| |
| // |where_index| is a pointer to the uint32 which needs to be updated in |
| // order to insert the new internal node into the tree. The internal nodes |
| // store the child indexes in the top 24-bits of a 32-bit word and, to keep |
| // the code simple, we define that |internal_node_head_| is organised the |
| // same way. |
| DCHECK_EQ(internal_node_head_ & 0xff, 0u); |
| uint32* where_index = &internal_node_head_; |
| while (((*where_index >> 8) & kExternalFlag) == 0) { |
| InternalNode* node = &internal_nodes_[*where_index >> 8]; |
| if (node->critbyte() > differing_byte) { |
| break; |
| } |
| if (node->critbyte() == differing_byte && |
| node->otherbits() > new_other_bits) { |
| break; |
| } |
| if (node->critbyte() == differing_byte && |
| node->otherbits() == new_other_bits) { |
| CHECK(false); |
| } |
| |
| uint8 c = value[node->critbyte()]; |
| const int direction = |
| (1 + static_cast<unsigned>(node->otherbits() | c)) >> 8; |
| where_index = &node->data_[direction]; |
| } |
| |
| inode->SetChild(newdirection ^ 1, *where_index >> 8); |
| *where_index = (*where_index & 0xff) | (internal_node_index << 8); |
| |
| DCHECK_LE(horizon_, nonce_time); |
| return NONCE_OK; |
| } |
| |
| const uint8* StrikeRegister::orbit() const { |
| return orbit_; |
| } |
| |
| 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; |
| } |
| } |
| |
| 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); |
| } |
| |
| set<uint32> free_external_nodes; |
| for (uint32 i = external_node_free_head_; i != kNil; |
| i = external_node_next_ptr(i)) { |
| CHECK_LT(i, max_entries_); |
| CHECK_EQ(free_external_nodes.count(i), 0u); |
| free_external_nodes.insert(i); |
| } |
| |
| set<uint32> used_external_nodes; |
| set<uint32> used_internal_nodes; |
| |
| if (internal_node_head_ != kNil && |
| ((internal_node_head_ >> 8) & kExternalFlag) == 0) { |
| vector<pair<unsigned, bool> > bits; |
| ValidateTree(internal_node_head_ >> 8, -1, bits, free_internal_nodes, |
| free_external_nodes, &used_internal_nodes, |
| &used_external_nodes); |
| } |
| } |
| |
| // 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; |
| while ((next & kExternalFlag) == 0) { |
| InternalNode* node = &internal_nodes_[next]; |
| uint8 b = v[node->critbyte()]; |
| unsigned direction = |
| (1 + static_cast<unsigned>(node->otherbits() | b)) >> 8; |
| next = node->child(direction); |
| } |
| |
| return next & ~kExternalFlag; |
| } |
| |
| uint32& StrikeRegister::external_node_next_ptr(unsigned i) { |
| return *reinterpret_cast<uint32*>(&external_nodes_[i * kExternalNodeSize]); |
| } |
| |
| uint8* StrikeRegister::external_node(unsigned i) { |
| return &external_nodes_[i * kExternalNodeSize]; |
| } |
| |
| uint32 StrikeRegister::GetFreeExternalNode() { |
| uint32 index = external_node_free_head_; |
| DCHECK(index != kNil); |
| external_node_free_head_ = external_node_next_ptr(index); |
| return index; |
| } |
| |
| uint32 StrikeRegister::GetFreeInternalNode() { |
| uint32 index = internal_node_free_head_; |
| DCHECK(index != kNil); |
| internal_node_free_head_ = internal_nodes_[index].next(); |
| return index; |
| } |
| |
| void StrikeRegister::DropOldestNode() { |
| // DropOldestNode should never be called on an empty tree. |
| DCHECK(internal_node_head_ != kNil); |
| |
| // An internal node in a crit-bit tree always has exactly two children. |
| // This means that, if we are removing an external node (which is one of |
| // those children), then we also need to remove an internal node. In order |
| // to do that we keep pointers to the parent (wherep) and grandparent |
| // (whereq) when walking down the tree. |
| |
| uint32 p = internal_node_head_ >> 8, *wherep = &internal_node_head_, |
| *whereq = NULL; |
| while ((p & kExternalFlag) == 0) { |
| whereq = wherep; |
| InternalNode* inode = &internal_nodes_[p]; |
| // We always go left, towards the smallest element, exploiting the fact |
| // that the timestamp is big-endian and at the start of the value. |
| wherep = &inode->data_[0]; |
| p = (*wherep) >> 8; |
| } |
| |
| const uint32 ext_index = p & ~kExternalFlag; |
| const uint8* ext_node = external_node(ext_index); |
| uint32 new_horizon = ExternalTimeToInternal(TimeFromBytes(ext_node)) + 1; |
| DCHECK_LE(horizon_, new_horizon); |
| horizon_ = new_horizon; |
| |
| if (!whereq) { |
| // We are removing the last element in a tree. |
| internal_node_head_ = kNil; |
| FreeExternalNode(ext_index); |
| return; |
| } |
| |
| // |wherep| points to the left child pointer in the parent so we can add |
| // one and dereference to get the right child. |
| const uint32 other_child = wherep[1]; |
| FreeInternalNode((*whereq) >> 8); |
| *whereq = (*whereq & 0xff) | (other_child & 0xffffff00); |
| FreeExternalNode(ext_index); |
| } |
| |
| void StrikeRegister::FreeExternalNode(uint32 index) { |
| external_node_next_ptr(index) = external_node_free_head_; |
| external_node_free_head_ = index; |
| } |
| |
| void StrikeRegister::FreeInternalNode(uint32 index) { |
| internal_nodes_[index].SetNextPtr(internal_node_free_head_); |
| internal_node_free_head_ = index; |
| } |
| |
| void StrikeRegister::ValidateTree( |
| uint32 internal_node, |
| int last_bit, |
| const vector<pair<unsigned, bool> >& bits, |
| const set<uint32>& free_internal_nodes, |
| const set<uint32>& free_external_nodes, |
| set<uint32>* used_internal_nodes, |
| set<uint32>* used_external_nodes) { |
| CHECK_LT(internal_node, max_entries_); |
| const InternalNode* i = &internal_nodes_[internal_node]; |
| unsigned bit = 0; |
| switch (i->otherbits()) { |
| case 0xff & ~(1 << 7): |
| bit = 0; |
| break; |
| case 0xff & ~(1 << 6): |
| bit = 1; |
| break; |
| case 0xff & ~(1 << 5): |
| bit = 2; |
| break; |
| case 0xff & ~(1 << 4): |
| bit = 3; |
| break; |
| case 0xff & ~(1 << 3): |
| bit = 4; |
| break; |
| case 0xff & ~(1 << 2): |
| bit = 5; |
| break; |
| case 0xff & ~(1 << 1): |
| bit = 6; |
| break; |
| case 0xff & ~1: |
| bit = 7; |
| break; |
| default: |
| CHECK(false); |
| } |
| |
| bit += 8 * i->critbyte(); |
| if (last_bit > -1) { |
| CHECK_GT(bit, static_cast<unsigned>(last_bit)); |
| } |
| |
| CHECK_EQ(free_internal_nodes.count(internal_node), 0u); |
| |
| for (unsigned child = 0; child < 2; child++) { |
| if (i->child(child) & kExternalFlag) { |
| uint32 ext = i->child(child) & ~kExternalFlag; |
| CHECK_EQ(free_external_nodes.count(ext), 0u); |
| CHECK_EQ(used_external_nodes->count(ext), 0u); |
| used_external_nodes->insert(ext); |
| const uint8* bytes = external_node(ext); |
| for (vector<pair<unsigned, bool> >::const_iterator i = bits.begin(); |
| i != bits.end(); i++) { |
| unsigned byte = i->first / 8; |
| DCHECK_LE(byte, 0xffu); |
| unsigned bit = i->first % 8; |
| static const uint8 kMasks[8] = |
| {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01}; |
| CHECK_EQ((bytes[byte] & kMasks[bit]) != 0, i->second); |
| } |
| } else { |
| uint32 inter = i->child(child); |
| vector<pair<unsigned, bool> > new_bits(bits); |
| new_bits.push_back(pair<unsigned, bool>(bit, child != 0)); |
| 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 |