| 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 #ifndef NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ | 5 #ifndef NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ |
| 6 #define NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ | 6 #define NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ |
| 7 | 7 |
| 8 #include <stdint.h> |
| 9 |
| 8 #include <set> | 10 #include <set> |
| 9 #include <utility> | 11 #include <utility> |
| 10 #include <vector> | 12 #include <vector> |
| 11 | 13 |
| 12 #include "base/basictypes.h" | 14 #include "base/macros.h" |
| 13 #include "base/memory/scoped_ptr.h" | 15 #include "base/memory/scoped_ptr.h" |
| 14 #include "net/base/net_export.h" | 16 #include "net/base/net_export.h" |
| 15 | 17 |
| 16 namespace net { | 18 namespace net { |
| 17 | 19 |
| 18 // InsertStatus enum values cannot be changed, they need to be stable. | 20 // InsertStatus enum values cannot be changed, they need to be stable. |
| 19 enum InsertStatus { | 21 enum InsertStatus { |
| 20 NONCE_OK = 0, | 22 NONCE_OK = 0, |
| 21 // The default error value for nonce verification failures from strike | 23 // The default error value for nonce verification failures from strike |
| 22 // register (covers old strike registers and unknown failures). | 24 // register (covers old strike registers and unknown failures). |
| (...skipping 59 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 82 // quiescent period). | 84 // quiescent period). |
| 83 DENY_REQUESTS_AT_STARTUP, | 85 DENY_REQUESTS_AT_STARTUP, |
| 84 // NO_STARTUP_PERIOD_NEEDED indicates that no quiescent period is required. | 86 // NO_STARTUP_PERIOD_NEEDED indicates that no quiescent period is required. |
| 85 // This may be because the strike-register is using an orbit randomly | 87 // This may be because the strike-register is using an orbit randomly |
| 86 // generated at startup and therefore nonces accepted by the previous | 88 // generated at startup and therefore nonces accepted by the previous |
| 87 // instance of the strike-register are invalid for that reason. | 89 // instance of the strike-register are invalid for that reason. |
| 88 NO_STARTUP_PERIOD_NEEDED, | 90 NO_STARTUP_PERIOD_NEEDED, |
| 89 }; | 91 }; |
| 90 | 92 |
| 91 // An external node takes 24 bytes as we don't record the orbit. | 93 // An external node takes 24 bytes as we don't record the orbit. |
| 92 static const uint32 kExternalNodeSize; | 94 static const uint32_t kExternalNodeSize; |
| 93 | 95 |
| 94 // We address the nodes by their index in the array. This means that 0 is a | 96 // We address the nodes by their index in the array. This means that 0 is a |
| 95 // valid index. Therefore this is our invalid index. It also has a one bit | 97 // valid index. Therefore this is our invalid index. It also has a one bit |
| 96 // in the LSB position because we tend to store indexes shifted up 8 bits | 98 // in the LSB position because we tend to store indexes shifted up 8 bits |
| 97 // and this distinguishes kNil from (kExternalFlag | 0) << 8. | 99 // and this distinguishes kNil from (kExternalFlag | 0) << 8. |
| 98 static const uint32 kNil; | 100 static const uint32_t kNil; |
| 99 | 101 |
| 100 // Our pointers from internal nodes can either point to an internal or | 102 // Our pointers from internal nodes can either point to an internal or |
| 101 // external node. We flag the 24th bit to mark a pointer as external. | 103 // external node. We flag the 24th bit to mark a pointer as external. |
| 102 static const uint32 kExternalFlag; | 104 static const uint32_t kExternalFlag; |
| 103 | 105 |
| 104 // Allows early validation before a strike register is created. | 106 // Allows early validation before a strike register is created. |
| 105 static void ValidateStrikeRegisterConfig(unsigned max_entries); | 107 static void ValidateStrikeRegisterConfig(unsigned max_entries); |
| 106 | 108 |
| 107 // Construct a new set which can hold, at most, |max_entries| (which must be | 109 // Construct a new set which can hold, at most, |max_entries| (which must be |
| 108 // less than 2**23). See the comments around StartupType about initial | 110 // less than 2**23). See the comments around StartupType about initial |
| 109 // behaviour. Otherwise, all nonces that are outside +/- |window_secs| from | 111 // behaviour. Otherwise, all nonces that are outside +/- |window_secs| from |
| 110 // the current time will be rejected. Additionally, all nonces that have an | 112 // the current time will be rejected. Additionally, all nonces that have an |
| 111 // orbit value other than |orbit| will be rejected. | 113 // orbit value other than |orbit| will be rejected. |
| 112 // | 114 // |
| 113 // (Note that this code is independent of the actual units of time used, but | 115 // (Note that this code is independent of the actual units of time used, but |
| 114 // you should use seconds.) | 116 // you should use seconds.) |
| 115 StrikeRegister(unsigned max_entries, | 117 StrikeRegister(unsigned max_entries, |
| 116 uint32 current_time_external, | 118 uint32_t current_time_external, |
| 117 uint32 window_secs, | 119 uint32_t window_secs, |
| 118 const uint8 orbit[8], | 120 const uint8_t orbit[8], |
| 119 StartupType startup); | 121 StartupType startup); |
| 120 | 122 |
| 121 ~StrikeRegister(); | 123 ~StrikeRegister(); |
| 122 | 124 |
| 123 void Reset(); | 125 void Reset(); |
| 124 | 126 |
| 125 // |Insert| queries to see if |nonce| is | 127 // |Insert| queries to see if |nonce| is |
| 126 // a) for the wrong orbit | 128 // a) for the wrong orbit |
| 127 // b) before the current horizon | 129 // b) before the current horizon |
| 128 // c) outside of the valid time window | 130 // c) outside of the valid time window |
| 129 // d) already in the set of observed nonces | 131 // d) already in the set of observed nonces |
| 130 // and returns the failure reason if any of these are true. It is also free to | 132 // and returns the failure reason if any of these are true. It is also free to |
| 131 // return failure reason for other reasons as it's always safe to reject an | 133 // return failure reason for other reasons as it's always safe to reject an |
| 132 // nonce. | 134 // nonce. |
| 133 // | 135 // |
| 134 // nonces are: | 136 // nonces are: |
| 135 // 4 bytes of timestamp (UNIX epoch seconds) | 137 // 4 bytes of timestamp (UNIX epoch seconds) |
| 136 // 8 bytes of orbit value (a cluster id) | 138 // 8 bytes of orbit value (a cluster id) |
| 137 // 20 bytes of random data | 139 // 20 bytes of random data |
| 138 // | 140 // |
| 139 // Otherwise, it inserts |nonce| into the observed set and returns NONCE_OK. | 141 // Otherwise, it inserts |nonce| into the observed set and returns NONCE_OK. |
| 140 InsertStatus Insert(const uint8 nonce[32], uint32 current_time); | 142 InsertStatus Insert(const uint8_t nonce[32], uint32_t current_time); |
| 141 | 143 |
| 142 // orbit returns a pointer to the 8-byte orbit value for this | 144 // orbit returns a pointer to the 8-byte orbit value for this |
| 143 // strike-register. | 145 // strike-register. |
| 144 const uint8* orbit() const; | 146 const uint8_t* orbit() const; |
| 145 | 147 |
| 146 // Time window for which the strike register has complete information. | 148 // Time window for which the strike register has complete information. |
| 147 uint32 GetCurrentValidWindowSecs(uint32 current_time_external) const; | 149 uint32_t GetCurrentValidWindowSecs(uint32_t current_time_external) const; |
| 148 | 150 |
| 149 // This is a debugging aid which checks the tree for sanity. | 151 // This is a debugging aid which checks the tree for sanity. |
| 150 void Validate(); | 152 void Validate(); |
| 151 | 153 |
| 152 private: | 154 private: |
| 153 class InternalNode; | 155 class InternalNode; |
| 154 | 156 |
| 155 // TimeFromBytes returns a big-endian uint32 from |d|. | 157 // TimeFromBytes returns a big-endian uint32_t from |d|. |
| 156 static uint32 TimeFromBytes(const uint8 d[4]); | 158 static uint32_t TimeFromBytes(const uint8_t d[4]); |
| 157 | 159 |
| 158 // Range of internal times for which the strike register has | 160 // Range of internal times for which the strike register has |
| 159 // complete information. A nonce is within the valid range of the | 161 // complete information. A nonce is within the valid range of the |
| 160 // strike register if: | 162 // strike register if: |
| 161 // valid_range.first <= nonce_time_internal <= valid_range.second | 163 // valid_range.first <= nonce_time_internal <= valid_range.second |
| 162 std::pair<uint32, uint32> GetValidRange(uint32 current_time_internal) const; | 164 std::pair<uint32_t, uint32_t> GetValidRange( |
| 165 uint32_t current_time_internal) const; |
| 163 | 166 |
| 164 // ExternalTimeToInternal converts an external time value into an internal | 167 // ExternalTimeToInternal converts an external time value into an internal |
| 165 // time value using |internal_epoch_|. | 168 // time value using |internal_epoch_|. |
| 166 uint32 ExternalTimeToInternal(uint32 external_time) const; | 169 uint32_t ExternalTimeToInternal(uint32_t external_time) const; |
| 167 | 170 |
| 168 // BestMatch returns either kNil, or an external node index which could | 171 // BestMatch returns either kNil, or an external node index which could |
| 169 // possibly match |v|. | 172 // possibly match |v|. |
| 170 uint32 BestMatch(const uint8 v[24]) const; | 173 uint32_t BestMatch(const uint8_t v[24]) const; |
| 171 | 174 |
| 172 // external_node_next_ptr returns the 'next' pointer embedded in external | 175 // external_node_next_ptr returns the 'next' pointer embedded in external |
| 173 // node |i|. This is used to thread a free list through the external nodes. | 176 // node |i|. This is used to thread a free list through the external nodes. |
| 174 uint32& external_node_next_ptr(unsigned i); | 177 uint32_t& external_node_next_ptr(unsigned i); |
| 175 | 178 |
| 176 uint8* external_node(unsigned i); | 179 uint8_t* external_node(unsigned i); |
| 177 | 180 |
| 178 uint32 GetFreeExternalNode(); | 181 uint32_t GetFreeExternalNode(); |
| 179 | 182 |
| 180 uint32 GetFreeInternalNode(); | 183 uint32_t GetFreeInternalNode(); |
| 181 | 184 |
| 182 // DropOldestNode removes the oldest node in the tree and updates |horizon_| | 185 // DropOldestNode removes the oldest node in the tree and updates |horizon_| |
| 183 // accordingly. | 186 // accordingly. |
| 184 void DropOldestNode(); | 187 void DropOldestNode(); |
| 185 | 188 |
| 186 void FreeExternalNode(uint32 index); | 189 void FreeExternalNode(uint32_t index); |
| 187 | 190 |
| 188 void FreeInternalNode(uint32 index); | 191 void FreeInternalNode(uint32_t index); |
| 189 | 192 |
| 190 void ValidateTree(uint32 internal_node, | 193 void ValidateTree(uint32_t internal_node, |
| 191 int last_bit, | 194 int last_bit, |
| 192 const std::vector<std::pair<unsigned, bool>>& bits, | 195 const std::vector<std::pair<unsigned, bool>>& bits, |
| 193 const std::set<uint32>& free_internal_nodes, | 196 const std::set<uint32_t>& free_internal_nodes, |
| 194 const std::set<uint32>& free_external_nodes, | 197 const std::set<uint32_t>& free_external_nodes, |
| 195 std::set<uint32>* used_internal_nodes, | 198 std::set<uint32_t>* used_internal_nodes, |
| 196 std::set<uint32>* used_external_nodes); | 199 std::set<uint32_t>* used_external_nodes); |
| 197 | 200 |
| 198 const uint32 max_entries_; | 201 const uint32_t max_entries_; |
| 199 const uint32 window_secs_; | 202 const uint32_t window_secs_; |
| 200 // internal_epoch_ contains the external time value of the start of internal | 203 // internal_epoch_ contains the external time value of the start of internal |
| 201 // time. | 204 // time. |
| 202 const uint32 internal_epoch_; | 205 const uint32_t internal_epoch_; |
| 203 uint8 orbit_[8]; | 206 uint8_t orbit_[8]; |
| 204 // The strike register will reject nonces with internal times < |horizon_| . | 207 // The strike register will reject nonces with internal times < |horizon_| . |
| 205 uint32 horizon_; | 208 uint32_t horizon_; |
| 206 | 209 |
| 207 uint32 internal_node_free_head_; | 210 uint32_t internal_node_free_head_; |
| 208 uint32 external_node_free_head_; | 211 uint32_t external_node_free_head_; |
| 209 uint32 internal_node_head_; | 212 uint32_t internal_node_head_; |
| 210 // internal_nodes_ can't be a scoped_ptr because the type isn't defined in | 213 // internal_nodes_ can't be a scoped_ptr because the type isn't defined in |
| 211 // this header. | 214 // this header. |
| 212 InternalNode* internal_nodes_; | 215 InternalNode* internal_nodes_; |
| 213 scoped_ptr<uint8[]> external_nodes_; | 216 scoped_ptr<uint8_t[]> external_nodes_; |
| 214 | 217 |
| 215 DISALLOW_COPY_AND_ASSIGN(StrikeRegister); | 218 DISALLOW_COPY_AND_ASSIGN(StrikeRegister); |
| 216 }; | 219 }; |
| 217 | 220 |
| 218 } // namespace net | 221 } // namespace net |
| 219 | 222 |
| 220 #endif // NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ | 223 #endif // NET_QUIC_CRYPTO_STRIKE_REGISTER_H_ |
| OLD | NEW |