Home | History | Annotate | Download | only in quic
      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