net/quic/quic_utils.cc

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