OLD | NEW |
1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "net/quic/crypto/strike_register.h" | 5 #include "net/quic/crypto/strike_register.h" |
6 | 6 |
7 #include <limits> | 7 #include <limits> |
8 | 8 |
9 #include "base/logging.h" | 9 #include "base/logging.h" |
10 | 10 |
(...skipping 112 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
123 // Also thread a free list through the external nodes. | 123 // Also thread a free list through the external nodes. |
124 external_node_free_head_ = 0; | 124 external_node_free_head_ = 0; |
125 for (unsigned i = 0; i < max_entries_ - 1; i++) | 125 for (unsigned i = 0; i < max_entries_ - 1; i++) |
126 external_node_next_ptr(i) = i + 1; | 126 external_node_next_ptr(i) = i + 1; |
127 external_node_next_ptr(max_entries_ - 1) = kNil; | 127 external_node_next_ptr(max_entries_ - 1) = kNil; |
128 | 128 |
129 // This is the root of the tree. | 129 // This is the root of the tree. |
130 internal_node_head_ = kNil; | 130 internal_node_head_ = kNil; |
131 } | 131 } |
132 | 132 |
133 bool StrikeRegister::Insert(const uint8 nonce[32], | 133 InsertStatus StrikeRegister::Insert(const uint8 nonce[32], |
134 uint32 current_time_external) { | 134 uint32 current_time_external) { |
135 // Make space for the insertion if the strike register is full. | 135 // Make space for the insertion if the strike register is full. |
136 while (external_node_free_head_ == kNil || | 136 while (external_node_free_head_ == kNil || |
137 internal_node_free_head_ == kNil) { | 137 internal_node_free_head_ == kNil) { |
138 DropOldestNode(); | 138 DropOldestNode(); |
139 } | 139 } |
140 | 140 |
141 const uint32 current_time = ExternalTimeToInternal(current_time_external); | 141 const uint32 current_time = ExternalTimeToInternal(current_time_external); |
142 | 142 |
143 // Check to see if the orbit is correct. | 143 // Check to see if the orbit is correct. |
144 if (memcmp(nonce + sizeof(current_time), orbit_, sizeof(orbit_))) { | 144 if (memcmp(nonce + sizeof(current_time), orbit_, sizeof(orbit_))) { |
145 return false; | 145 return NONCE_INVALID_ORBIT_FAILURE; |
146 } | 146 } |
147 | 147 |
148 const uint32 nonce_time = ExternalTimeToInternal(TimeFromBytes(nonce)); | 148 const uint32 nonce_time = ExternalTimeToInternal(TimeFromBytes(nonce)); |
149 | 149 |
150 // Check that the timestamp is in the valid range. | 150 // Check that the timestamp is in the valid range. |
151 pair<uint32, uint32> valid_range = | 151 pair<uint32, uint32> valid_range = |
152 StrikeRegister::GetValidRange(current_time); | 152 StrikeRegister::GetValidRange(current_time); |
153 if (nonce_time < valid_range.first || nonce_time > valid_range.second) { | 153 if (nonce_time < valid_range.first || nonce_time > valid_range.second) { |
154 return false; | 154 return NONCE_INVALID_TIME_FAILURE; |
155 } | 155 } |
156 | 156 |
157 // We strip the orbit out of the nonce. | 157 // We strip the orbit out of the nonce. |
158 uint8 value[24]; | 158 uint8 value[24]; |
159 memcpy(value, nonce, sizeof(nonce_time)); | 159 memcpy(value, nonce, sizeof(nonce_time)); |
160 memcpy(value + sizeof(nonce_time), | 160 memcpy(value + sizeof(nonce_time), |
161 nonce + sizeof(nonce_time) + sizeof(orbit_), | 161 nonce + sizeof(nonce_time) + sizeof(orbit_), |
162 sizeof(value) - sizeof(nonce_time)); | 162 sizeof(value) - sizeof(nonce_time)); |
163 | 163 |
164 // Find the best match to |value| in the crit-bit tree. The best match is | 164 // Find the best match to |value| in the crit-bit tree. The best match is |
165 // simply the value which /could/ match |value|, if any does, so we still | 165 // simply the value which /could/ match |value|, if any does, so we still |
166 // need a memcmp to check. | 166 // need a memcmp to check. |
167 uint32 best_match_index = BestMatch(value); | 167 uint32 best_match_index = BestMatch(value); |
168 if (best_match_index == kNil) { | 168 if (best_match_index == kNil) { |
169 // Empty tree. Just insert the new value at the root. | 169 // Empty tree. Just insert the new value at the root. |
170 uint32 index = GetFreeExternalNode(); | 170 uint32 index = GetFreeExternalNode(); |
171 memcpy(external_node(index), value, sizeof(value)); | 171 memcpy(external_node(index), value, sizeof(value)); |
172 internal_node_head_ = (index | kExternalFlag) << 8; | 172 internal_node_head_ = (index | kExternalFlag) << 8; |
173 DCHECK_LE(horizon_, nonce_time); | 173 DCHECK_LE(horizon_, nonce_time); |
174 return true; | 174 return NONCE_OK; |
175 } | 175 } |
176 | 176 |
177 const uint8* best_match = external_node(best_match_index); | 177 const uint8* best_match = external_node(best_match_index); |
178 if (memcmp(best_match, value, sizeof(value)) == 0) { | 178 if (memcmp(best_match, value, sizeof(value)) == 0) { |
179 // We found the value in the tree. | 179 // We found the value in the tree. |
180 return false; | 180 return NONCE_NOT_UNIQUE_FAILURE; |
181 } | 181 } |
182 | 182 |
183 // We are going to insert a new entry into the tree, so get the nodes now. | 183 // We are going to insert a new entry into the tree, so get the nodes now. |
184 uint32 internal_node_index = GetFreeInternalNode(); | 184 uint32 internal_node_index = GetFreeInternalNode(); |
185 uint32 external_node_index = GetFreeExternalNode(); | 185 uint32 external_node_index = GetFreeExternalNode(); |
186 | 186 |
187 // If we just evicted the best match, then we have to try and match again. | 187 // If we just evicted the best match, then we have to try and match again. |
188 // We know that we didn't just empty the tree because we require that | 188 // We know that we didn't just empty the tree because we require that |
189 // max_entries_ >= 2. Also, we know that it doesn't match because, if it | 189 // max_entries_ >= 2. Also, we know that it doesn't match because, if it |
190 // did, it would have been returned previously. | 190 // did, it would have been returned previously. |
(...skipping 65 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
256 uint8 c = value[node->critbyte()]; | 256 uint8 c = value[node->critbyte()]; |
257 const int direction = | 257 const int direction = |
258 (1 + static_cast<unsigned>(node->otherbits() | c)) >> 8; | 258 (1 + static_cast<unsigned>(node->otherbits() | c)) >> 8; |
259 where_index = &node->data_[direction]; | 259 where_index = &node->data_[direction]; |
260 } | 260 } |
261 | 261 |
262 inode->SetChild(newdirection ^ 1, *where_index >> 8); | 262 inode->SetChild(newdirection ^ 1, *where_index >> 8); |
263 *where_index = (*where_index & 0xff) | (internal_node_index << 8); | 263 *where_index = (*where_index & 0xff) | (internal_node_index << 8); |
264 | 264 |
265 DCHECK_LE(horizon_, nonce_time); | 265 DCHECK_LE(horizon_, nonce_time); |
266 return true; | 266 return NONCE_OK; |
267 } | 267 } |
268 | 268 |
269 const uint8* StrikeRegister::orbit() const { | 269 const uint8* StrikeRegister::orbit() const { |
270 return orbit_; | 270 return orbit_; |
271 } | 271 } |
272 | 272 |
273 uint32 StrikeRegister::GetCurrentValidWindowSecs( | 273 uint32 StrikeRegister::GetCurrentValidWindowSecs( |
274 uint32 current_time_external) const { | 274 uint32 current_time_external) const { |
275 uint32 current_time = ExternalTimeToInternal(current_time_external); | 275 uint32 current_time = ExternalTimeToInternal(current_time_external); |
276 pair<uint32, uint32> valid_range = StrikeRegister::GetValidRange( | 276 pair<uint32, uint32> valid_range = StrikeRegister::GetValidRange( |
(...skipping 234 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
511 CHECK_EQ(free_internal_nodes.count(inter), 0u); | 511 CHECK_EQ(free_internal_nodes.count(inter), 0u); |
512 CHECK_EQ(used_internal_nodes->count(inter), 0u); | 512 CHECK_EQ(used_internal_nodes->count(inter), 0u); |
513 used_internal_nodes->insert(inter); | 513 used_internal_nodes->insert(inter); |
514 ValidateTree(inter, bit, bits, free_internal_nodes, free_external_nodes, | 514 ValidateTree(inter, bit, bits, free_internal_nodes, free_external_nodes, |
515 used_internal_nodes, used_external_nodes); | 515 used_internal_nodes, used_external_nodes); |
516 } | 516 } |
517 } | 517 } |
518 } | 518 } |
519 | 519 |
520 } // namespace net | 520 } // namespace net |
OLD | NEW |