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 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 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 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 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 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 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 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 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 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 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 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 313 QuicPriority QuicUtils::LowestPriority() { 314 return QuicWriteBlockedList::kLowestPriority; 315 } 316 317 // static 318 QuicPriority QuicUtils::HighestPriority() { 319 return QuicWriteBlockedList::kHighestPriority; 320 } 321 322 } // namespace net 323
