src/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
  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_STREAM_LAST_ERROR);
 142   }
 143   // Return a default value so that we return this when |error| doesn't match
 144   // any of the QuicRstStreamErrorCodes. This can happen when the RstStream
 145   // frame sent by the peer (attacker) has invalid error code.
 146   return "INVALID_RST_STREAM_ERROR_CODE";
 147 }
 148
 149 // static
 150 const char* QuicUtils::ErrorToString(QuicErrorCode error) {
 151   switch (error) {
 152     RETURN_STRING_LITERAL(QUIC_NO_ERROR);
 153     RETURN_STRING_LITERAL(QUIC_INTERNAL_ERROR);
 154     RETURN_STRING_LITERAL(QUIC_STREAM_DATA_AFTER_TERMINATION);
 155     RETURN_STRING_LITERAL(QUIC_INVALID_PACKET_HEADER);
 156     RETURN_STRING_LITERAL(QUIC_INVALID_FRAME_DATA);
 157     RETURN_STRING_LITERAL(QUIC_MISSING_PAYLOAD);
 158     RETURN_STRING_LITERAL(QUIC_INVALID_FEC_DATA);
 159     RETURN_STRING_LITERAL(QUIC_INVALID_STREAM_DATA);
 160     RETURN_STRING_LITERAL(QUIC_INVALID_RST_STREAM_DATA);
 161     RETURN_STRING_LITERAL(QUIC_INVALID_CONNECTION_CLOSE_DATA);
 162     RETURN_STRING_LITERAL(QUIC_INVALID_GOAWAY_DATA);
 163     RETURN_STRING_LITERAL(QUIC_INVALID_WINDOW_UPDATE_DATA);
 164     RETURN_STRING_LITERAL(QUIC_INVALID_BLOCKED_DATA);
 165     RETURN_STRING_LITERAL(QUIC_INVALID_STOP_WAITING_DATA);
 166     RETURN_STRING_LITERAL(QUIC_INVALID_ACK_DATA);
 167     RETURN_STRING_LITERAL(QUIC_INVALID_CONGESTION_FEEDBACK_DATA);
 168     RETURN_STRING_LITERAL(QUIC_INVALID_VERSION_NEGOTIATION_PACKET);
 169     RETURN_STRING_LITERAL(QUIC_INVALID_PUBLIC_RST_PACKET);
 170     RETURN_STRING_LITERAL(QUIC_DECRYPTION_FAILURE);
 171     RETURN_STRING_LITERAL(QUIC_ENCRYPTION_FAILURE);
 172     RETURN_STRING_LITERAL(QUIC_PACKET_TOO_LARGE);
 173     RETURN_STRING_LITERAL(QUIC_PACKET_FOR_NONEXISTENT_STREAM);
 174     RETURN_STRING_LITERAL(QUIC_PEER_GOING_AWAY);
 175     RETURN_STRING_LITERAL(QUIC_HANDSHAKE_FAILED);
 176     RETURN_STRING_LITERAL(QUIC_CRYPTO_TAGS_OUT_OF_ORDER);
 177     RETURN_STRING_LITERAL(QUIC_CRYPTO_TOO_MANY_ENTRIES);
 178     RETURN_STRING_LITERAL(QUIC_CRYPTO_TOO_MANY_REJECTS);
 179     RETURN_STRING_LITERAL(QUIC_CRYPTO_INVALID_VALUE_LENGTH)
 180     RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_AFTER_HANDSHAKE_COMPLETE);
 181     RETURN_STRING_LITERAL(QUIC_CRYPTO_INTERNAL_ERROR);
 182     RETURN_STRING_LITERAL(QUIC_CRYPTO_VERSION_NOT_SUPPORTED);
 183     RETURN_STRING_LITERAL(QUIC_CRYPTO_NO_SUPPORT);
 184     RETURN_STRING_LITERAL(QUIC_INVALID_CRYPTO_MESSAGE_TYPE);
 185     RETURN_STRING_LITERAL(QUIC_INVALID_CRYPTO_MESSAGE_PARAMETER);
 186     RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_PARAMETER_NOT_FOUND);
 187     RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_PARAMETER_NO_OVERLAP);
 188     RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_INDEX_NOT_FOUND);
 189     RETURN_STRING_LITERAL(QUIC_INVALID_STREAM_ID);
 190     RETURN_STRING_LITERAL(QUIC_INVALID_PRIORITY);
 191     RETURN_STRING_LITERAL(QUIC_TOO_MANY_OPEN_STREAMS);
 192     RETURN_STRING_LITERAL(QUIC_PUBLIC_RESET);
 193     RETURN_STRING_LITERAL(QUIC_INVALID_VERSION);
 194     RETURN_STRING_LITERAL(QUIC_INVALID_HEADER_ID);
 195     RETURN_STRING_LITERAL(QUIC_INVALID_NEGOTIATED_VALUE);
 196     RETURN_STRING_LITERAL(QUIC_DECOMPRESSION_FAILURE);
 197     RETURN_STRING_LITERAL(QUIC_CONNECTION_TIMED_OUT);
 198     RETURN_STRING_LITERAL(QUIC_ERROR_MIGRATING_ADDRESS);
 199     RETURN_STRING_LITERAL(QUIC_PACKET_WRITE_ERROR);
 200     RETURN_STRING_LITERAL(QUIC_PACKET_READ_ERROR);
 201     RETURN_STRING_LITERAL(QUIC_INVALID_STREAM_FRAME);
 202     RETURN_STRING_LITERAL(QUIC_INVALID_HEADERS_STREAM_DATA);
 203     RETURN_STRING_LITERAL(QUIC_FLOW_CONTROL_ERROR);
 204     RETURN_STRING_LITERAL(QUIC_PROOF_INVALID);
 205     RETURN_STRING_LITERAL(QUIC_CRYPTO_DUPLICATE_TAG);
 206     RETURN_STRING_LITERAL(QUIC_CRYPTO_ENCRYPTION_LEVEL_INCORRECT);
 207     RETURN_STRING_LITERAL(QUIC_CRYPTO_SERVER_CONFIG_EXPIRED);
 208     RETURN_STRING_LITERAL(QUIC_INVALID_CHANNEL_ID_SIGNATURE);
 209     RETURN_STRING_LITERAL(QUIC_CRYPTO_SYMMETRIC_KEY_SETUP_FAILED);
 210     RETURN_STRING_LITERAL(QUIC_CRYPTO_MESSAGE_WHILE_VALIDATING_CLIENT_HELLO);
 211     RETURN_STRING_LITERAL(QUIC_VERSION_NEGOTIATION_MISMATCH);
 212     RETURN_STRING_LITERAL(QUIC_LAST_ERROR);
 213     // Intentionally have no default case, so we'll break the build
 214     // if we add errors and don't put them here.
 215   }
 216   // Return a default value so that we return this when |error| doesn't match
 217   // any of the QuicErrorCodes. This can happen when the ConnectionClose
 218   // frame sent by the peer (attacker) has invalid error code.
 219   return "INVALID_ERROR_CODE";
 220 }
 221
 222 // static
 223 const char* QuicUtils::EncryptionLevelToString(EncryptionLevel level) {
 224   switch (level) {
 225     RETURN_STRING_LITERAL(ENCRYPTION_NONE);
 226     RETURN_STRING_LITERAL(ENCRYPTION_INITIAL);
 227     RETURN_STRING_LITERAL(ENCRYPTION_FORWARD_SECURE);
 228     RETURN_STRING_LITERAL(NUM_ENCRYPTION_LEVELS);
 229   }
 230   return "INVALID_ENCRYPTION_LEVEL";
 231 }
 232
 233 // static
 234 const char* QuicUtils::TransmissionTypeToString(TransmissionType type) {
 235   switch (type) {
 236     RETURN_STRING_LITERAL(NOT_RETRANSMISSION);
 237     RETURN_STRING_LITERAL(HANDSHAKE_RETRANSMISSION);
 238     RETURN_STRING_LITERAL(LOSS_RETRANSMISSION);
 239     RETURN_STRING_LITERAL(ALL_UNACKED_RETRANSMISSION);
 240     RETURN_STRING_LITERAL(RTO_RETRANSMISSION);
 241     RETURN_STRING_LITERAL(TLP_RETRANSMISSION);
 242   }
 243   return "INVALID_TRANSMISSION_TYPE";
 244 }
 245
 246 // static
 247 string QuicUtils::TagToString(QuicTag tag) {
 248   char chars[4];
 249   bool ascii = true;
 250   const QuicTag orig_tag = tag;
 251
 252   for (size_t i = 0; i < sizeof(chars); i++) {
 253     chars[i] = tag;
 254     if ((chars[i] == 0 || chars[i] == '\xff') && i == 3) {
 255       chars[i] = ' ';
 256     }
 257     if (!isprint(static_cast<unsigned char>(chars[i]))) {
 258       ascii = false;
 259       break;
 260     }
 261     tag >>= 8;
 262   }
 263
 264   if (ascii) {
 265     return string(chars, sizeof(chars));
 266   }
 267
 268   return base::UintToString(orig_tag);
 269 }
 270
 271 // static
 272 string QuicUtils::StringToHexASCIIDump(StringPiece in_buffer) {
 273   int offset = 0;
 274   const int kBytesPerLine = 16;   // Max bytes dumped per line
 275   const char* buf = in_buffer.data();
 276   int bytes_remaining = in_buffer.size();
 277   string s;   // our output
 278   const char* p = buf;
 279   while (bytes_remaining > 0) {
 280     const int line_bytes = std::min(bytes_remaining, kBytesPerLine);
 281     base::StringAppendF(&s, "0x%04x:  ", offset);  // Do the line header
 282     for (int i = 0; i < kBytesPerLine; ++i) {
 283       if (i < line_bytes) {
 284         base::StringAppendF(&s, "%02x", static_cast<unsigned char>(p[i]));
 285       } else {
 286         s += "  ";    // two-space filler instead of two-space hex digits
 287       }
 288       if (i % 2) s += ' ';
 289     }
 290     s += ' ';
 291     for (int i = 0; i < line_bytes; ++i) {  // Do the ASCII dump
 292       s+= (p[i] >  32 && p[i] < 127) ? p[i] : '.';
 293     }
 294
 295     bytes_remaining -= line_bytes;
 296     offset += line_bytes;
 297     p += line_bytes;
 298     s += '\n';
 299   }
 300   return s;
 301 }
 302
 303 // static
 304 QuicPriority QuicUtils::LowestPriority() {
 305   return QuicWriteBlockedList::kLowestPriority;
 306 }
 307
 308 // static
 309 QuicPriority QuicUtils::HighestPriority() {
 310   return QuicWriteBlockedList::kHighestPriority;
 311 }
 312
 313 }  // namespace net