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