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.
5 #include "net/quic/crypto/strike_register.h"
7 #include "base/logging.h"
16 const uint32 StrikeRegister::kExternalNodeSize = 24;
18 const uint32 StrikeRegister::kNil = (1 << 31) | 1;
20 const uint32 StrikeRegister::kExternalFlag = 1 << 23;
22 // InternalNode represents a non-leaf node in the critbit tree. See the comment
23 // in the .h file for details.
24 class StrikeRegister::InternalNode {
26 void SetChild(unsigned direction, uint32 child) {
27 data_[direction] = (data_[direction] & 0xff) | (child << 8);
30 void SetCritByte(uint8 critbyte) {
31 data_[0] &= 0xffffff00;
35 void SetOtherBits(uint8 otherbits) {
36 data_[1] &= 0xffffff00;
37 data_[1] |= otherbits;
40 void SetNextPtr(uint32 next) { data_[0] = next; }
42 uint32 next() const { return data_[0]; }
44 uint32 child(unsigned n) const { return data_[n] >> 8; }
46 uint8 critbyte() const { return data_[0]; }
48 uint8 otherbits() const { return data_[1]; }
50 // These bytes are organised thus:
51 // <24 bits> left child
53 // <24 bits> right child
54 // <8 bits> other-bits
58 // kCreationTimeFromInternalEpoch contains the number of seconds between the
59 // start of the internal epoch and the creation time. This allows us
60 // to consider times that are before the creation time.
61 static const uint32 kCreationTimeFromInternalEpoch = 63115200.0; // 2 years.
63 StrikeRegister::StrikeRegister(unsigned max_entries,
68 : max_entries_(max_entries),
69 window_secs_(window_secs),
70 internal_epoch_(current_time > kCreationTimeFromInternalEpoch
71 ? current_time - kCreationTimeFromInternalEpoch
73 // The horizon is initially set |window_secs| into the future because, if
74 // we just crashed, then we may have accepted nonces in the span
75 // [current_time...current_time+window_secs) and so we conservatively
76 // reject the whole timespan unless |startup| tells us otherwise.
77 horizon_(ExternalTimeToInternal(current_time) + window_secs),
78 horizon_valid_(startup == DENY_REQUESTS_AT_STARTUP) {
79 memcpy(orbit_, orbit, sizeof(orbit_));
81 // We only have 23 bits of index available.
82 CHECK_LT(max_entries, 1u << 23);
83 CHECK_GT(max_entries, 1u); // There must be at least two entries.
84 CHECK_EQ(sizeof(InternalNode), 8u); // in case of compiler changes.
85 internal_nodes_ = new InternalNode[max_entries];
86 external_nodes_.reset(new uint8[kExternalNodeSize * max_entries]);
91 StrikeRegister::~StrikeRegister() { delete[] internal_nodes_; }
93 void StrikeRegister::Reset() {
94 // Thread a free list through all of the internal nodes.
95 internal_node_free_head_ = 0;
96 for (unsigned i = 0; i < max_entries_ - 1; i++)
97 internal_nodes_[i].SetNextPtr(i + 1);
98 internal_nodes_[max_entries_ - 1].SetNextPtr(kNil);
100 // Also thread a free list through the external nodes.
101 external_node_free_head_ = 0;
102 for (unsigned i = 0; i < max_entries_ - 1; i++)
103 external_node_next_ptr(i) = i + 1;
104 external_node_next_ptr(max_entries_ - 1) = kNil;
106 // This is the root of the tree.
107 internal_node_head_ = kNil;
110 bool StrikeRegister::Insert(const uint8 nonce[32],
111 const uint32 current_time_external) {
112 const uint32 current_time = ExternalTimeToInternal(current_time_external);
114 // Check to see if the orbit is correct.
115 if (memcmp(nonce + sizeof(current_time), orbit_, sizeof(orbit_))) {
118 const uint32 nonce_time = ExternalTimeToInternal(TimeFromBytes(nonce));
119 // We have dropped one or more nonces with a time value of |horizon_|, so
120 // we have to reject anything with a timestamp less than or equal to that.
121 if (horizon_valid_ && nonce_time <= horizon_) {
125 // Check that the timestamp is in the current window.
126 if ((current_time > window_secs_ &&
127 nonce_time < (current_time - window_secs_)) ||
128 nonce_time > (current_time + window_secs_)) {
132 // We strip the orbit out of the nonce.
134 memcpy(value, &nonce_time, sizeof(nonce_time));
135 memcpy(value + sizeof(nonce_time),
136 nonce + sizeof(nonce_time) + sizeof(orbit_),
137 sizeof(value) - sizeof(nonce_time));
139 // Find the best match to |value| in the crit-bit tree. The best match is
140 // simply the value which /could/ match |value|, if any does, so we still
141 // need a memcmp to check.
142 uint32 best_match_index = BestMatch(value);
143 if (best_match_index == kNil) {
144 // Empty tree. Just insert the new value at the root.
145 uint32 index = GetFreeExternalNode();
146 memcpy(external_node(index), value, sizeof(value));
147 internal_node_head_ = (index | kExternalFlag) << 8;
151 const uint8* best_match = external_node(best_match_index);
152 if (memcmp(best_match, value, sizeof(value)) == 0) {
153 // We found the value in the tree.
157 // We are going to insert a new entry into the tree, so get the nodes now.
158 uint32 internal_node_index = GetFreeInternalNode();
159 uint32 external_node_index = GetFreeExternalNode();
161 // If we just evicted the best match, then we have to try and match again.
162 // We know that we didn't just empty the tree because we require that
163 // max_entries_ >= 2. Also, we know that it doesn't match because, if it
164 // did, it would have been returned previously.
165 if (external_node_index == best_match_index) {
166 best_match_index = BestMatch(value);
167 best_match = external_node(best_match_index);
170 // Now we need to find the first bit where we differ from |best_match|.
171 unsigned differing_byte;
172 uint8 new_other_bits;
173 for (differing_byte = 0; differing_byte < sizeof(value); differing_byte++) {
174 new_other_bits = value[differing_byte] ^ best_match[differing_byte];
175 if (new_other_bits) {
180 // Once we have the XOR the of first differing byte in new_other_bits we need
181 // to find the most significant differing bit. We could do this with a simple
182 // for loop, testing bits 7..0. Instead we fold the bits so that we end up
183 // with a byte where all the bits below the most significant one, are set.
184 new_other_bits |= new_other_bits >> 1;
185 new_other_bits |= new_other_bits >> 2;
186 new_other_bits |= new_other_bits >> 4;
187 // Now this bit trick results in all the bits set, except the original
188 // most-significant one.
189 new_other_bits = (new_other_bits & ~(new_other_bits >> 1)) ^ 255;
191 // Consider the effect of ORing against |new_other_bits|. If |value| did not
192 // have the critical bit set, the result is the same as |new_other_bits|. If
193 // it did, the result is all ones.
195 unsigned newdirection;
196 if ((new_other_bits | value[differing_byte]) == 0xff) {
202 memcpy(external_node(external_node_index), value, sizeof(value));
203 InternalNode* inode = &internal_nodes_[internal_node_index];
205 inode->SetChild(newdirection, external_node_index | kExternalFlag);
206 inode->SetCritByte(differing_byte);
207 inode->SetOtherBits(new_other_bits);
209 // |where_index| is a pointer to the uint32 which needs to be updated in
210 // order to insert the new internal node into the tree. The internal nodes
211 // store the child indexes in the top 24-bits of a 32-bit word and, to keep
212 // the code simple, we define that |internal_node_head_| is organised the
214 DCHECK_EQ(internal_node_head_ & 0xff, 0u);
215 uint32* where_index = &internal_node_head_;
216 while (((*where_index >> 8) & kExternalFlag) == 0) {
217 InternalNode* node = &internal_nodes_[*where_index >> 8];
218 if (node->critbyte() > differing_byte) {
221 if (node->critbyte() == differing_byte &&
222 node->otherbits() > new_other_bits) {
225 if (node->critbyte() == differing_byte &&
226 node->otherbits() == new_other_bits) {
230 uint8 c = value[node->critbyte()];
231 const int direction =
232 (1 + static_cast<unsigned>(node->otherbits() | c)) >> 8;
233 where_index = &node->data_[direction];
236 inode->SetChild(newdirection ^ 1, *where_index >> 8);
237 *where_index = (*where_index & 0xff) | (internal_node_index << 8);
242 const uint8* StrikeRegister::orbit() const {
246 void StrikeRegister::Validate() {
247 set<uint32> free_internal_nodes;
248 for (uint32 i = internal_node_free_head_; i != kNil;
249 i = internal_nodes_[i].next()) {
250 CHECK_LT(i, max_entries_);
251 CHECK_EQ(free_internal_nodes.count(i), 0u);
252 free_internal_nodes.insert(i);
255 set<uint32> free_external_nodes;
256 for (uint32 i = external_node_free_head_; i != kNil;
257 i = external_node_next_ptr(i)) {
258 CHECK_LT(i, max_entries_);
259 CHECK_EQ(free_external_nodes.count(i), 0u);
260 free_external_nodes.insert(i);
263 set<uint32> used_external_nodes;
264 set<uint32> used_internal_nodes;
266 if (internal_node_head_ != kNil &&
267 ((internal_node_head_ >> 8) & kExternalFlag) == 0) {
268 vector<pair<unsigned, bool> > bits;
269 ValidateTree(internal_node_head_ >> 8, -1, bits, free_internal_nodes,
270 free_external_nodes, &used_internal_nodes,
271 &used_external_nodes);
276 uint32 StrikeRegister::TimeFromBytes(const uint8 d[4]) {
277 return static_cast<uint32>(d[0]) << 24 |
278 static_cast<uint32>(d[1]) << 16 |
279 static_cast<uint32>(d[2]) << 8 |
280 static_cast<uint32>(d[3]);
283 uint32 StrikeRegister::ExternalTimeToInternal(uint32 external_time) {
284 return external_time - internal_epoch_;
287 uint32 StrikeRegister::BestMatch(const uint8 v[24]) const {
288 if (internal_node_head_ == kNil) {
292 uint32 next = internal_node_head_ >> 8;
293 while ((next & kExternalFlag) == 0) {
294 InternalNode* node = &internal_nodes_[next];
295 uint8 b = v[node->critbyte()];
297 (1 + static_cast<unsigned>(node->otherbits() | b)) >> 8;
298 next = node->child(direction);
301 return next & ~kExternalFlag;
304 uint32& StrikeRegister::external_node_next_ptr(unsigned i) {
305 return *reinterpret_cast<uint32*>(&external_nodes_[i * kExternalNodeSize]);
308 uint8* StrikeRegister::external_node(unsigned i) {
309 return &external_nodes_[i * kExternalNodeSize];
312 uint32 StrikeRegister::GetFreeExternalNode() {
313 uint32 index = external_node_free_head_;
316 return GetFreeExternalNode();
319 external_node_free_head_ = external_node_next_ptr(index);
323 uint32 StrikeRegister::GetFreeInternalNode() {
324 uint32 index = internal_node_free_head_;
327 return GetFreeInternalNode();
330 internal_node_free_head_ = internal_nodes_[index].next();
334 void StrikeRegister::DropNode() {
335 // DropNode should never be called on an empty tree.
336 DCHECK(internal_node_head_ != kNil);
338 // An internal node in a crit-bit tree always has exactly two children.
339 // This means that, if we are removing an external node (which is one of
340 // those children), then we also need to remove an internal node. In order
341 // to do that we keep pointers to the parent (wherep) and grandparent
342 // (whereq) when walking down the tree.
344 uint32 p = internal_node_head_ >> 8, *wherep = &internal_node_head_,
346 while ((p & kExternalFlag) == 0) {
348 InternalNode* inode = &internal_nodes_[p];
349 // We always go left, towards the smallest element, exploiting the fact
350 // that the timestamp is big-endian and at the start of the value.
351 wherep = &inode->data_[0];
355 const uint32 ext_index = p & ~kExternalFlag;
356 const uint8* ext_node = external_node(ext_index);
357 horizon_ = TimeFromBytes(ext_node);
360 // We are removing the last element in a tree.
361 internal_node_head_ = kNil;
362 FreeExternalNode(ext_index);
366 // |wherep| points to the left child pointer in the parent so we can add
367 // one and dereference to get the right child.
368 const uint32 other_child = wherep[1];
369 FreeInternalNode((*whereq) >> 8);
370 *whereq = (*whereq & 0xff) | (other_child & 0xffffff00);
371 FreeExternalNode(ext_index);
374 void StrikeRegister::FreeExternalNode(uint32 index) {
375 external_node_next_ptr(index) = external_node_free_head_;
376 external_node_free_head_ = index;
379 void StrikeRegister::FreeInternalNode(uint32 index) {
380 internal_nodes_[index].SetNextPtr(internal_node_free_head_);
381 internal_node_free_head_ = index;
384 void StrikeRegister::ValidateTree(
385 uint32 internal_node,
387 const vector<pair<unsigned, bool> >& bits,
388 const set<uint32>& free_internal_nodes,
389 const set<uint32>& free_external_nodes,
390 set<uint32>* used_internal_nodes,
391 set<uint32>* used_external_nodes) {
392 CHECK_LT(internal_node, max_entries_);
393 const InternalNode* i = &internal_nodes_[internal_node];
395 switch (i->otherbits()) {
396 case 0xff & ~(1 << 7):
399 case 0xff & ~(1 << 6):
402 case 0xff & ~(1 << 5):
405 case 0xff & ~(1 << 4):
408 case 0xff & ~(1 << 3):
411 case 0xff & ~(1 << 2):
414 case 0xff & ~(1 << 1):
424 bit += 8 * i->critbyte();
426 CHECK_GT(bit, static_cast<unsigned>(last_bit));
429 CHECK_EQ(free_internal_nodes.count(internal_node), 0u);
431 for (unsigned child = 0; child < 2; child++) {
432 if (i->child(child) & kExternalFlag) {
433 uint32 ext = i->child(child) & ~kExternalFlag;
434 CHECK_EQ(free_external_nodes.count(ext), 0u);
435 CHECK_EQ(used_external_nodes->count(ext), 0u);
436 used_external_nodes->insert(ext);
437 const uint8* bytes = external_node(ext);
438 for (vector<pair<unsigned, bool> >::const_iterator i = bits.begin();
439 i != bits.end(); i++) {
440 unsigned byte = i->first / 8;
441 DCHECK_LE(byte, 0xffu);
442 unsigned bit = i->first % 8;
443 static const uint8 kMasks[8] =
444 {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
445 CHECK_EQ((bytes[byte] & kMasks[bit]) != 0, i->second);
448 uint32 inter = i->child(child);
449 vector<pair<unsigned, bool> > new_bits(bits);
450 new_bits.push_back(pair<unsigned, bool>(bit, child != 0));
451 CHECK_EQ(free_internal_nodes.count(inter), 0u);
452 CHECK_EQ(used_internal_nodes->count(inter), 0u);
453 used_internal_nodes->insert(inter);
454 ValidateTree(inter, bit, bits, free_internal_nodes, free_external_nodes,
455 used_internal_nodes, used_external_nodes);