This source file includes following definitions.
- SetChild
- SetCritByte
- SetOtherBits
- SetNextPtr
- next
- child
- critbyte
- otherbits
- ValidateStrikeRegisterConfig
- horizon_valid_
- Reset
- Insert
- orbit
- Validate
- TimeFromBytes
- ExternalTimeToInternal
- BestMatch
- external_node_next_ptr
- external_node
- GetFreeExternalNode
- GetFreeInternalNode
- DropNode
- FreeExternalNode
- FreeInternalNode
- ValidateTree
#include "net/quic/crypto/strike_register.h"
#include "base/logging.h"
using std::pair;
using std::set;
using std::vector;
namespace net {
const uint32 StrikeRegister::kExternalNodeSize = 24;
const uint32 StrikeRegister::kNil = (1 << 31) | 1;
const uint32 StrikeRegister::kExternalFlag = 1 << 23;
class StrikeRegister::InternalNode {
public:
void SetChild(unsigned direction, uint32 child) {
data_[direction] = (data_[direction] & 0xff) | (child << 8);
}
void SetCritByte(uint8 critbyte) {
data_[0] &= 0xffffff00;
data_[0] |= critbyte;
}
void SetOtherBits(uint8 otherbits) {
data_[1] &= 0xffffff00;
data_[1] |= 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]; }
uint32 data_[2];
};
static const uint32 kCreationTimeFromInternalEpoch = 63115200.0;
void StrikeRegister::ValidateStrikeRegisterConfig(unsigned max_entries) {
CHECK_LT(max_entries, 1u << 23);
CHECK_GT(max_entries, 1u);
CHECK_EQ(sizeof(InternalNode), 8u);
}
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_(ExternalTimeToInternal(current_time) + window_secs),
horizon_valid_(startup == DENY_REQUESTS_AT_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() {
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);
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;
internal_node_head_ = kNil;
}
bool StrikeRegister::Insert(const uint8 nonce[32],
const uint32 current_time_external) {
const uint32 current_time = ExternalTimeToInternal(current_time_external);
if (memcmp(nonce + sizeof(current_time), orbit_, sizeof(orbit_))) {
return false;
}
const uint32 nonce_time = ExternalTimeToInternal(TimeFromBytes(nonce));
if (horizon_valid_ && nonce_time <= horizon_) {
return false;
}
if ((current_time > window_secs_ &&
nonce_time < (current_time - window_secs_)) ||
nonce_time > (current_time + window_secs_)) {
return false;
}
uint8 value[24];
memcpy(value, &nonce_time, sizeof(nonce_time));
memcpy(value + sizeof(nonce_time),
nonce + sizeof(nonce_time) + sizeof(orbit_),
sizeof(value) - sizeof(nonce_time));
uint32 best_match_index = BestMatch(value);
if (best_match_index == kNil) {
uint32 index = GetFreeExternalNode();
memcpy(external_node(index), value, sizeof(value));
internal_node_head_ = (index | kExternalFlag) << 8;
return true;
}
const uint8* best_match = external_node(best_match_index);
if (memcmp(best_match, value, sizeof(value)) == 0) {
return false;
}
uint32 internal_node_index = GetFreeInternalNode();
uint32 external_node_index = GetFreeExternalNode();
if (external_node_index == best_match_index) {
best_match_index = BestMatch(value);
best_match = external_node(best_match_index);
}
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;
}
}
new_other_bits |= new_other_bits >> 1;
new_other_bits |= new_other_bits >> 2;
new_other_bits |= new_other_bits >> 4;
new_other_bits = (new_other_bits & ~(new_other_bits >> 1)) ^ 255;
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);
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);
return true;
}
const uint8* StrikeRegister::orbit() const {
return orbit_;
}
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);
}
}
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]);
}
uint32 StrikeRegister::ExternalTimeToInternal(uint32 external_time) {
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_;
if (index == kNil) {
DropNode();
return GetFreeExternalNode();
}
external_node_free_head_ = external_node_next_ptr(index);
return index;
}
uint32 StrikeRegister::GetFreeInternalNode() {
uint32 index = internal_node_free_head_;
if (index == kNil) {
DropNode();
return GetFreeInternalNode();
}
internal_node_free_head_ = internal_nodes_[index].next();
return index;
}
void StrikeRegister::DropNode() {
DCHECK(internal_node_head_ != kNil);
uint32 p = internal_node_head_ >> 8, *wherep = &internal_node_head_,
*whereq = NULL;
while ((p & kExternalFlag) == 0) {
whereq = wherep;
InternalNode* inode = &internal_nodes_[p];
wherep = &inode->data_[0];
p = (*wherep) >> 8;
}
const uint32 ext_index = p & ~kExternalFlag;
const uint8* ext_node = external_node(ext_index);
horizon_ = TimeFromBytes(ext_node);
if (!whereq) {
internal_node_head_ = kNil;
FreeExternalNode(ext_index);
return;
}
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);
}
}
}
}