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