1 // Copyright (c) 2012 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.
4
5 #include "net/quic/quic_utils.h"
6
7 #include <ctype.h>
8
9 #include <algorithm>
10
11 #include "base/basictypes.h"
12 #include "base/logging.h"
13 #include "base/port.h"
14 #include "base/strings/stringprintf.h"
15 #include "base/strings/string_number_conversions.h"
16 #include "net/quic/quic_write_blocked_list.h"
17
18 using base::StringPiece;
19 using std::string;
20
21 namespace net {
22
23 // static
FNV1a_64_Hash(const char * data,int len)24 uint64 QuicUtils::FNV1a_64_Hash(const char* data, int len) {
25 static const uint64 kOffset = GG_UINT64_C(14695981039346656037);
26 static const uint64 kPrime = GG_UINT64_C(1099511628211);
27
28 const uint8* octets = reinterpret_cast<const uint8*>(data);
29
30 uint64 hash = kOffset;
31
32 for (int i = 0; i < len; ++i) {
33 hash = hash ^ octets[i];
34 hash = hash * kPrime;
35 }
36
37 return hash;
38 }
39
40 // static
FNV1a_128_Hash(const char * data,int len)41 uint128 QuicUtils::FNV1a_128_Hash(const char* data, int len) {
42 // The following two constants are defined as part of the hash algorithm.
43 // see http://www.isthe.com/chongo/tech/comp/fnv/
44 // 309485009821345068724781371
45 const uint128 kPrime(16777216, 315);
46 // 144066263297769815596495629667062367629
47 const uint128 kOffset(GG_UINT64_C(7809847782465536322),
48 GG_UINT64_C(7113472399480571277));
49
50 const uint8* octets = reinterpret_cast<const uint8*>(data);
51
52 uint128 hash = kOffset;
53
54 for (int i = 0; i < len; ++i) {
55 hash = hash ^ uint128(0, octets[i]);
56 hash = hash * kPrime;
57 }
58
59 return hash;
60 }
61
62 // static
FindMutualTag(const QuicTagVector & our_tags_vector,const QuicTag * their_tags,size_t num_their_tags,Priority priority,QuicTag * out_result,size_t * out_index)63 bool QuicUtils::FindMutualTag(const QuicTagVector& our_tags_vector,
64 const QuicTag* their_tags,
65 size_t num_their_tags,
66 Priority priority,
67 QuicTag* out_result,
68 size_t* out_index) {
69 if (our_tags_vector.empty()) {
70 return false;
71 }
72 const size_t num_our_tags = our_tags_vector.size();
73 const QuicTag* our_tags = &our_tags_vector[0];
74
75 size_t num_priority_tags, num_inferior_tags;
76 const QuicTag* priority_tags;
77 const QuicTag* inferior_tags;
78 if (priority == LOCAL_PRIORITY) {
79 num_priority_tags = num_our_tags;
80 priority_tags = our_tags;
81 num_inferior_tags = num_their_tags;
82 inferior_tags = their_tags;
83 } else {
84 num_priority_tags = num_their_tags;
85 priority_tags = their_tags;
86 num_inferior_tags = num_our_tags;
87 inferior_tags = our_tags;
88 }
89
90 for (size_t i = 0; i < num_priority_tags; i++) {
91 for (size_t j = 0; j < num_inferior_tags; j++) {
92 if (priority_tags[i] == inferior_tags[j]) {
93 *out_result = priority_tags[i];
94 if (out_index) {
95 if (priority == LOCAL_PRIORITY) {
96 *out_index = j;
97 } else {
98 *out_index = i;
99 }
100 }
101 return true;
102 }
103 }
104 }
105
106 return false;
107 }
108
109 // static
SerializeUint128(uint128 v,uint8 * out)110 void QuicUtils::SerializeUint128(uint128 v, uint8* out) {
111 const uint64 lo = Uint128Low64(v);
112 const uint64 hi = Uint128High64(v);
113 // This assumes that the system is little-endian.
114 memcpy(out, &lo, sizeof(lo));
115 memcpy(out + sizeof(lo), &hi, sizeof(hi));
116 }
117
118 // static
SerializeUint128Short(uint128 v,uint8 * out)119 void QuicUtils::SerializeUint128Short(uint128 v, uint8* out) {
120 const uint64 lo = Uint128Low64(v);
121 const uint64 hi = Uint128High64(v);
122 // This assumes that the system is little-endian.
123 memcpy(out, &lo, sizeof(lo));
124 memcpy(out + sizeof(lo), &hi, sizeof(hi) / 2);
125 }
126
127 #define RETURN_STRING_LITERAL(x) \
128 case x: \
129 return #x;
130
131 // static
StreamErrorToString(QuicRstStreamErrorCode error)132 const char* QuicUtils::StreamErrorToString(QuicRstStreamErrorCode error) {
133 switch (error) {
134 RETURN_STRING_LITERAL(QUIC_STREAM_NO_ERROR);
135 RETURN_STRING_LITERAL(QUIC_STREAM_CONNECTION_ERROR);
136 RETURN_STRING_LITERAL(QUIC_ERROR_PROCESSING_STREAM);
137 RETURN_STRING_LITERAL(QUIC_MULTIPLE_TERMINATION_OFFSETS);
138 RETURN_STRING_LITERAL(QUIC_BAD_APPLICATION_PAYLOAD);
139 RETURN_STRING_LITERAL(QUIC_STREAM_PEER_GOING_AWAY);
140 RETURN_STRING_LITERAL(QUIC_STREAM_CANCELLED);
141 RETURN_STRING_LITERAL(QUIC_RST_FLOW_CONTROL_ACCOUNTING);
142 RETURN_STRING_LITERAL(QUIC_STREAM_LAST_ERROR);
143 }
144 // Return a default value so that we return this when |error| doesn't match
145 // any of the QuicRstStreamErrorCodes. This can happen when the RstStream
146 // frame sent by the peer (attacker) has invalid error code.
147 return "INVALID_RST_STREAM_ERROR_CODE";
148 }
149
150 // static
ErrorToString(QuicErrorCode error)151 const char* QuicUtils::ErrorToString(QuicErrorCode error) {
152 switch (error) {
153 RETURN_STRING_LITERAL(QUIC_NO_ERROR);
154 RETURN_STRING_LITERAL(QUIC_INTERNAL_ERROR);
155 RETURN_STRING_LITERAL(QUIC_STREAM_DATA_AFTER_TERMINATION);
156 RETURN_STRING_LITERAL(QUIC_INVALID_PACKET_HEADER);
157 RETURN_STRING_LITERAL(QUIC_INVALID_FRAME_DATA);
158 RETURN_STRING_LITERAL(QUIC_MISSING_PAYLOAD);
159 RETURN_STRING_LITERAL(QUIC_INVALID_FEC_DATA);
160 RETURN_STRING_LITERAL(QUIC_INVALID_STREAM_DATA);
161 RETURN_STRING_LITERAL(QUIC_UNENCRYPTED_STREAM_DATA);
162 RETURN_STRING_LITERAL(QUIC_INVALID_RST_STREAM_DATA);
163 RETURN_STRING_LITERAL(QUIC_INVALID_CONNECTION_CLOSE_DATA);
164 RETURN_STRING_LITERAL(QUIC_INVALID_GOAWAY_DATA);
165 RETURN_STRING_LITERAL(QUIC_INVALID_WINDOW_UPDATE_DATA);
166 RETURN_STRING_LITERAL(QUIC_INVALID_BLOCKED_DATA);
167 RETURN_STRING_LITERAL(QUIC_INVALID_STOP_WAITING_DATA);
168 RETURN_STRING_LITERAL(QUIC_INVALID_ACK_DATA);
169 RETURN_STRING_LITERAL(QUIC_INVALID_CONGESTION_FEEDBACK_DATA);
170 RETURN_STRING_LITERAL(QUIC_INVALID_VERSION_NEGOTIATION_PACKET);
171 RETURN_STRING_LITERAL(QUIC_INVALID_PUBLIC_RST_PACKET);
172 RETURN_STRING_LITERAL(QUIC_DECRYPTION_FAILURE);
173 RETURN_STRING_LITERAL(QUIC_ENCRYPTION_FAILURE);
174 RETURN_STRING_LITERAL(QUIC_PACKET_TOO_LARGE);
175 RETURN_STRING_LITERAL(QUIC_PACKET_FOR_NONEXISTENT_STREAM);
176 RETURN_STRING_LITERAL(QUIC_PEER_GOING_AWAY);
177 RETURN_STRING_LITERAL(QUIC_HANDSHAKE_FAILED);
178 RETURN_STRING_LITERAL(QUIC_CRYPTO_TAGS_OUT_OF_ORDER);
179 RETURN_STRING_LITERAL(QUIC_CRYPTO_TOO_MANY_ENTRIES);
180 RETURN_STRING_LITERAL(QUIC_CRYPTO_TOO_MANY_REJECTS);
181 RETURN_STRING_LITERAL(QUIC_CRYPTO_INVALID_VALUE_LENGTH)
182 RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_AFTER_HANDSHAKE_COMPLETE);
183 RETURN_STRING_LITERAL(QUIC_CRYPTO_INTERNAL_ERROR);
184 RETURN_STRING_LITERAL(QUIC_CRYPTO_VERSION_NOT_SUPPORTED);
185 RETURN_STRING_LITERAL(QUIC_CRYPTO_NO_SUPPORT);
186 RETURN_STRING_LITERAL(QUIC_INVALID_CRYPTO_MESSAGE_TYPE);
187 RETURN_STRING_LITERAL(QUIC_INVALID_CRYPTO_MESSAGE_PARAMETER);
188 RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_PARAMETER_NOT_FOUND);
189 RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_PARAMETER_NO_OVERLAP);
190 RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_INDEX_NOT_FOUND);
191 RETURN_STRING_LITERAL(QUIC_INVALID_STREAM_ID);
192 RETURN_STRING_LITERAL(QUIC_INVALID_PRIORITY);
193 RETURN_STRING_LITERAL(QUIC_TOO_MANY_OPEN_STREAMS);
194 RETURN_STRING_LITERAL(QUIC_TOO_MANY_UNFINISHED_STREAMS);
195 RETURN_STRING_LITERAL(QUIC_PUBLIC_RESET);
196 RETURN_STRING_LITERAL(QUIC_INVALID_VERSION);
197 RETURN_STRING_LITERAL(QUIC_INVALID_HEADER_ID);
198 RETURN_STRING_LITERAL(QUIC_INVALID_NEGOTIATED_VALUE);
199 RETURN_STRING_LITERAL(QUIC_DECOMPRESSION_FAILURE);
200 RETURN_STRING_LITERAL(QUIC_CONNECTION_TIMED_OUT);
201 RETURN_STRING_LITERAL(QUIC_CONNECTION_OVERALL_TIMED_OUT);
202 RETURN_STRING_LITERAL(QUIC_ERROR_MIGRATING_ADDRESS);
203 RETURN_STRING_LITERAL(QUIC_PACKET_WRITE_ERROR);
204 RETURN_STRING_LITERAL(QUIC_PACKET_READ_ERROR);
205 RETURN_STRING_LITERAL(QUIC_INVALID_STREAM_FRAME);
206 RETURN_STRING_LITERAL(QUIC_INVALID_HEADERS_STREAM_DATA);
207 RETURN_STRING_LITERAL(QUIC_FLOW_CONTROL_RECEIVED_TOO_MUCH_DATA);
208 RETURN_STRING_LITERAL(QUIC_FLOW_CONTROL_SENT_TOO_MUCH_DATA);
209 RETURN_STRING_LITERAL(QUIC_FLOW_CONTROL_INVALID_WINDOW);
210 RETURN_STRING_LITERAL(QUIC_CONNECTION_IP_POOLED);
211 RETURN_STRING_LITERAL(QUIC_PROOF_INVALID);
212 RETURN_STRING_LITERAL(QUIC_CRYPTO_DUPLICATE_TAG);
213 RETURN_STRING_LITERAL(QUIC_CRYPTO_ENCRYPTION_LEVEL_INCORRECT);
214 RETURN_STRING_LITERAL(QUIC_CRYPTO_SERVER_CONFIG_EXPIRED);
215 RETURN_STRING_LITERAL(QUIC_INVALID_CHANNEL_ID_SIGNATURE);
216 RETURN_STRING_LITERAL(QUIC_CRYPTO_SYMMETRIC_KEY_SETUP_FAILED);
217 RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_WHILE_VALIDATING_CLIENT_HELLO);
218 RETURN_STRING_LITERAL(QUIC_CRYPTO_UPDATE_BEFORE_HANDSHAKE_COMPLETE);
219 RETURN_STRING_LITERAL(QUIC_VERSION_NEGOTIATION_MISMATCH);
220 RETURN_STRING_LITERAL(QUIC_LAST_ERROR);
221 // Intentionally have no default case, so we'll break the build
222 // if we add errors and don't put them here.
223 }
224 // Return a default value so that we return this when |error| doesn't match
225 // any of the QuicErrorCodes. This can happen when the ConnectionClose
226 // frame sent by the peer (attacker) has invalid error code.
227 return "INVALID_ERROR_CODE";
228 }
229
230 // static
EncryptionLevelToString(EncryptionLevel level)231 const char* QuicUtils::EncryptionLevelToString(EncryptionLevel level) {
232 switch (level) {
233 RETURN_STRING_LITERAL(ENCRYPTION_NONE);
234 RETURN_STRING_LITERAL(ENCRYPTION_INITIAL);
235 RETURN_STRING_LITERAL(ENCRYPTION_FORWARD_SECURE);
236 RETURN_STRING_LITERAL(NUM_ENCRYPTION_LEVELS);
237 }
238 return "INVALID_ENCRYPTION_LEVEL";
239 }
240
241 // static
TransmissionTypeToString(TransmissionType type)242 const char* QuicUtils::TransmissionTypeToString(TransmissionType type) {
243 switch (type) {
244 RETURN_STRING_LITERAL(NOT_RETRANSMISSION);
245 RETURN_STRING_LITERAL(HANDSHAKE_RETRANSMISSION);
246 RETURN_STRING_LITERAL(LOSS_RETRANSMISSION);
247 RETURN_STRING_LITERAL(ALL_UNACKED_RETRANSMISSION);
248 RETURN_STRING_LITERAL(ALL_INITIAL_RETRANSMISSION);
249 RETURN_STRING_LITERAL(RTO_RETRANSMISSION);
250 RETURN_STRING_LITERAL(TLP_RETRANSMISSION);
251 }
252 return "INVALID_TRANSMISSION_TYPE";
253 }
254
255 // static
TagToString(QuicTag tag)256 string QuicUtils::TagToString(QuicTag tag) {
257 char chars[4];
258 bool ascii = true;
259 const QuicTag orig_tag = tag;
260
261 for (size_t i = 0; i < sizeof(chars); i++) {
262 chars[i] = tag;
263 if ((chars[i] == 0 || chars[i] == '\xff') && i == 3) {
264 chars[i] = ' ';
265 }
266 if (!isprint(static_cast<unsigned char>(chars[i]))) {
267 ascii = false;
268 break;
269 }
270 tag >>= 8;
271 }
272
273 if (ascii) {
274 return string(chars, sizeof(chars));
275 }
276
277 return base::UintToString(orig_tag);
278 }
279
280 // static
StringToHexASCIIDump(StringPiece in_buffer)281 string QuicUtils::StringToHexASCIIDump(StringPiece in_buffer) {
282 int offset = 0;
283 const int kBytesPerLine = 16; // Max bytes dumped per line
284 const char* buf = in_buffer.data();
285 int bytes_remaining = in_buffer.size();
286 string s; // our output
287 const char* p = buf;
288 while (bytes_remaining > 0) {
289 const int line_bytes = std::min(bytes_remaining, kBytesPerLine);
290 base::StringAppendF(&s, "0x%04x: ", offset); // Do the line header
291 for (int i = 0; i < kBytesPerLine; ++i) {
292 if (i < line_bytes) {
293 base::StringAppendF(&s, "%02x", static_cast<unsigned char>(p[i]));
294 } else {
295 s += " "; // two-space filler instead of two-space hex digits
296 }
297 if (i % 2) s += ' ';
298 }
299 s += ' ';
300 for (int i = 0; i < line_bytes; ++i) { // Do the ASCII dump
301 s+= (p[i] > 32 && p[i] < 127) ? p[i] : '.';
302 }
303
304 bytes_remaining -= line_bytes;
305 offset += line_bytes;
306 p += line_bytes;
307 s += '\n';
308 }
309 return s;
310 }
311
312 // static
LowestPriority()313 QuicPriority QuicUtils::LowestPriority() {
314 return QuicWriteBlockedList::kLowestPriority;
315 }
316
317 // static
HighestPriority()318 QuicPriority QuicUtils::HighestPriority() {
319 return QuicWriteBlockedList::kHighestPriority;
320 }
321
322 } // namespace net
323