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 #ifndef QUICHE_QUIC_CORE_QUIC_UTILS_H_ 6 #define QUICHE_QUIC_CORE_QUIC_UTILS_H_ 7 8 #include <cstddef> 9 #include <cstdint> 10 #include <initializer_list> 11 #include <optional> 12 #include <string> 13 #include <type_traits> 14 15 #include "absl/numeric/bits.h" 16 #include "absl/numeric/int128.h" 17 #include "absl/strings/str_cat.h" 18 #include "absl/strings/string_view.h" 19 #include "absl/types/span.h" 20 #include "quiche/quic/core/crypto/quic_random.h" 21 #include "quiche/quic/core/frames/quic_frame.h" 22 #include "quiche/quic/core/quic_connection_id.h" 23 #include "quiche/quic/core/quic_error_codes.h" 24 #include "quiche/quic/core/quic_types.h" 25 #include "quiche/quic/core/quic_versions.h" 26 #include "quiche/quic/platform/api/quic_export.h" 27 #include "quiche/quic/platform/api/quic_socket_address.h" 28 #include "quiche/common/platform/api/quiche_mem_slice.h" 29 30 namespace quic { 31 32 class QUICHE_EXPORT QuicUtils { 33 public: 34 QuicUtils() = delete; 35 36 // Returns the 64 bit FNV1a hash of the data. See 37 // http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-param 38 static uint64_t FNV1a_64_Hash(absl::string_view data); 39 40 // Returns the 128 bit FNV1a hash of the data. See 41 // http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-param 42 static absl::uint128 FNV1a_128_Hash(absl::string_view data); 43 44 // Returns the 128 bit FNV1a hash of the two sequences of data. See 45 // http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-param 46 static absl::uint128 FNV1a_128_Hash_Two(absl::string_view data1, 47 absl::string_view data2); 48 49 // Returns the 128 bit FNV1a hash of the three sequences of data. See 50 // http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-param 51 static absl::uint128 FNV1a_128_Hash_Three(absl::string_view data1, 52 absl::string_view data2, 53 absl::string_view data3); 54 55 // SerializeUint128 writes the first 96 bits of |v| in little-endian form 56 // to |out|. 57 static void SerializeUint128Short(absl::uint128 v, uint8_t* out); 58 59 // Returns AddressChangeType as a string. 60 static std::string AddressChangeTypeToString(AddressChangeType type); 61 62 // Returns SentPacketState as a char*. 63 static const char* SentPacketStateToString(SentPacketState state); 64 65 // Returns QuicLongHeaderType as a char*. 66 static const char* QuicLongHeaderTypetoString(QuicLongHeaderType type); 67 68 // Returns AckResult as a char*. 69 static const char* AckResultToString(AckResult result); 70 71 // Determines and returns change type of address change from |old_address| to 72 // |new_address|. 73 static AddressChangeType DetermineAddressChangeType( 74 const QuicSocketAddress& old_address, 75 const QuicSocketAddress& new_address); 76 77 // Returns the opposite Perspective of the |perspective| passed in. InvertPerspective(Perspective perspective)78 static constexpr Perspective InvertPerspective(Perspective perspective) { 79 return perspective == Perspective::IS_CLIENT ? Perspective::IS_SERVER 80 : Perspective::IS_CLIENT; 81 } 82 83 // Returns true if a packet is ackable. A packet is unackable if it can never 84 // be acked. Occurs when a packet is never sent, after it is acknowledged 85 // once, or if it's a crypto packet we never expect to receive an ack for. 86 static bool IsAckable(SentPacketState state); 87 88 // Returns true if frame with |type| is retransmittable. A retransmittable 89 // frame should be retransmitted if it is detected as lost. 90 static bool IsRetransmittableFrame(QuicFrameType type); 91 92 // Returns true if |frame| is a handshake frame in version |version|. 93 static bool IsHandshakeFrame(const QuicFrame& frame, 94 QuicTransportVersion transport_version); 95 96 // Return true if any frame in |frames| is of |type|. 97 static bool ContainsFrameType(const QuicFrames& frames, QuicFrameType type); 98 99 // Returns packet state corresponding to |retransmission_type|. 100 static SentPacketState RetransmissionTypeToPacketState( 101 TransmissionType retransmission_type); 102 103 // Returns true if header with |first_byte| is considered as an IETF QUIC 104 // packet header. This only works on the server. 105 static bool IsIetfPacketHeader(uint8_t first_byte); 106 107 // Returns true if header with |first_byte| is considered as an IETF QUIC 108 // short packet header. 109 static bool IsIetfPacketShortHeader(uint8_t first_byte); 110 111 // Returns ID to denote an invalid stream of |version|. 112 static QuicStreamId GetInvalidStreamId(QuicTransportVersion version); 113 114 // Returns crypto stream ID of |version|. 115 static QuicStreamId GetCryptoStreamId(QuicTransportVersion version); 116 117 // Returns whether |id| is the stream ID for the crypto stream. If |version| 118 // is a version where crypto data doesn't go over stream frames, this function 119 // will always return false. 120 static bool IsCryptoStreamId(QuicTransportVersion version, QuicStreamId id); 121 122 // Returns headers stream ID of |version|. 123 static QuicStreamId GetHeadersStreamId(QuicTransportVersion version); 124 125 // Returns true if |id| is considered as client initiated stream ID. 126 static bool IsClientInitiatedStreamId(QuicTransportVersion version, 127 QuicStreamId id); 128 129 // Returns true if |id| is considered as server initiated stream ID. 130 static bool IsServerInitiatedStreamId(QuicTransportVersion version, 131 QuicStreamId id); 132 133 // Returns true if the stream ID represents a stream initiated by the 134 // provided perspective. 135 static bool IsOutgoingStreamId(ParsedQuicVersion version, QuicStreamId id, 136 Perspective perspective); 137 138 // Returns true if |id| is considered as bidirectional stream ID. Only used in 139 // v99. 140 static bool IsBidirectionalStreamId(QuicStreamId id, 141 ParsedQuicVersion version); 142 143 // Returns stream type. Either |perspective| or |peer_initiated| would be 144 // enough together with |id|. This method enforces that the three parameters 145 // are consistent. Only used in v99. 146 static StreamType GetStreamType(QuicStreamId id, Perspective perspective, 147 bool peer_initiated, 148 ParsedQuicVersion version); 149 150 // Returns the delta between consecutive stream IDs of the same type. 151 static QuicStreamId StreamIdDelta(QuicTransportVersion version); 152 153 // Returns the first initiated bidirectional stream ID of |perspective|. 154 static QuicStreamId GetFirstBidirectionalStreamId( 155 QuicTransportVersion version, Perspective perspective); 156 157 // Returns the first initiated unidirectional stream ID of |perspective|. 158 static QuicStreamId GetFirstUnidirectionalStreamId( 159 QuicTransportVersion version, Perspective perspective); 160 161 // Returns the largest possible client initiated bidirectional stream ID. 162 static QuicStreamId GetMaxClientInitiatedBidirectionalStreamId( 163 QuicTransportVersion version); 164 165 // Generates a random 64bit connection ID. 166 static QuicConnectionId CreateRandomConnectionId(); 167 168 // Generates a random 64bit connection ID using the provided QuicRandom. 169 static QuicConnectionId CreateRandomConnectionId(QuicRandom* random); 170 171 // Generates a random connection ID of the given length. 172 static QuicConnectionId CreateRandomConnectionId( 173 uint8_t connection_id_length); 174 175 // Generates a random connection ID of the given length using the provided 176 // QuicRandom. 177 static QuicConnectionId CreateRandomConnectionId(uint8_t connection_id_length, 178 QuicRandom* random); 179 180 // Returns true if the connection ID length is valid for this QUIC version. 181 static bool IsConnectionIdLengthValidForVersion( 182 size_t connection_id_length, QuicTransportVersion transport_version); 183 184 // Returns true if the connection ID is valid for this QUIC version. 185 static bool IsConnectionIdValidForVersion( 186 QuicConnectionId connection_id, QuicTransportVersion transport_version); 187 188 // Returns a connection ID suitable for QUIC use-cases that do not need the 189 // connection ID for multiplexing. If the version allows variable lengths, 190 // a connection of length zero is returned, otherwise 64bits set to zero. 191 static QuicConnectionId CreateZeroConnectionId(QuicTransportVersion version); 192 193 // Generates a 128bit stateless reset token based on a connection ID. 194 static StatelessResetToken GenerateStatelessResetToken( 195 QuicConnectionId connection_id); 196 197 // Determines packet number space from |encryption_level|. 198 static PacketNumberSpace GetPacketNumberSpace( 199 EncryptionLevel encryption_level); 200 201 // Determines encryption level to send ACK in |packet_number_space|. 202 static EncryptionLevel GetEncryptionLevelToSendAckofSpace( 203 PacketNumberSpace packet_number_space); 204 205 // Get the maximum value for a V99/IETF QUIC stream count. If a count 206 // exceeds this value, it will result in a stream ID that exceeds the 207 // implementation limit on stream ID size. 208 static QuicStreamCount GetMaxStreamCount(); 209 210 // Return true if this frame is an IETF probing frame. 211 static bool IsProbingFrame(QuicFrameType type); 212 213 // Return true if the two stateless reset tokens are equal. Performs the 214 // comparison in constant time. 215 static bool AreStatelessResetTokensEqual(const StatelessResetToken& token1, 216 const StatelessResetToken& token2); 217 218 // Return ture if this frame is an ack-eliciting frame. 219 static bool IsAckElicitingFrame(QuicFrameType type); 220 }; 221 222 // Returns true if the specific ID is a valid WebTransport session ID that our 223 // implementation can process. 224 bool IsValidWebTransportSessionId(WebTransportSessionId id, 225 ParsedQuicVersion transport_version); 226 227 QuicByteCount MemSliceSpanTotalSize(absl::Span<quiche::QuicheMemSlice> span); 228 229 // Computes a SHA-256 hash and returns the raw bytes of the hash. 230 QUICHE_EXPORT std::string RawSha256(absl::string_view input); 231 232 // BitMask<Index, Mask> is a set of elements of type `Index` represented as a 233 // bitmask of an underlying integer type `Mask` (uint64_t by default). The 234 // underlying type has to be large enough to fit all possible values of `Index`. 235 template <typename Index, typename Mask = uint64_t> 236 class QUICHE_EXPORT BitMask { 237 public: BitMask(std::initializer_list<Index> bits)238 explicit constexpr BitMask(std::initializer_list<Index> bits) { 239 for (Index bit : bits) { 240 mask_ |= MakeMask(bit); 241 } 242 } 243 244 BitMask() = default; 245 BitMask(const BitMask& other) = default; 246 BitMask& operator=(const BitMask& other) = default; 247 Set(Index bit)248 constexpr void Set(Index bit) { mask_ |= MakeMask(bit); } 249 Set(std::initializer_list<Index> bits)250 constexpr void Set(std::initializer_list<Index> bits) { 251 mask_ |= BitMask(bits).mask(); 252 } 253 IsSet(Index bit)254 constexpr bool IsSet(Index bit) const { return (MakeMask(bit) & mask_) != 0; } 255 ClearAll()256 constexpr void ClearAll() { mask_ = 0; } 257 258 // Returns true if any of the bits is set. Any()259 bool Any() const { return mask_ != 0; } 260 261 // Returns the highest bit set, or nullopt if the mask is all zeroes. Max()262 std::optional<Index> Max() const { 263 if (!Any()) { 264 return std::nullopt; 265 } 266 return static_cast<Index>(NumBits() - absl::countl_zero(mask_) - 1); 267 } 268 NumBits()269 static constexpr size_t NumBits() { return 8 * sizeof(Mask); } 270 271 friend bool operator==(const BitMask& lhs, const BitMask& rhs) { 272 return lhs.mask_ == rhs.mask_; 273 } 274 275 // Bitwise AND that can act as a set intersection between two bit masks. 276 BitMask<Index, Mask> operator&(const BitMask<Index, Mask>& rhs) const { 277 return BitMask<Index, Mask>(mask_ & rhs.mask_); 278 } 279 DebugString()280 std::string DebugString() const { 281 return absl::StrCat("0x", absl::Hex(mask_)); 282 } 283 mask()284 constexpr Mask mask() const { return mask_; } 285 286 private: BitMask(Mask mask)287 explicit constexpr BitMask(Mask mask) : mask_(mask) {} 288 289 template <typename Bit> MakeMask(Bit bit)290 static constexpr std::enable_if_t<std::is_enum_v<Bit>, Mask> MakeMask( 291 Bit bit) { 292 using IntType = typename std::underlying_type<Bit>::type; 293 return MakeMask(static_cast<IntType>(bit)); 294 } 295 296 template <typename Bit> MakeMask(Bit bit)297 static constexpr std::enable_if_t<!std::is_enum_v<Bit>, Mask> MakeMask( 298 Bit bit) { 299 // We can't use QUICHE_DCHECK_LT here, since it doesn't work with constexpr. 300 QUICHE_DCHECK(bit < static_cast<Bit>(NumBits())); 301 if constexpr (std::is_signed_v<Bit>) { 302 QUICHE_DCHECK(bit >= 0); 303 } 304 return Mask(1) << bit; 305 } 306 307 Mask mask_ = 0; 308 }; 309 310 // Ensure that the BitMask constructor can be evaluated as constexpr. 311 static_assert(BitMask<int>({1, 2, 3}).mask() == 0x0e); 312 313 } // namespace quic 314 315 #endif // QUICHE_QUIC_CORE_QUIC_UTILS_H_ 316