1 // Copyright 2014 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_UNACKED_PACKET_MAP_H_ 6 #define QUICHE_QUIC_CORE_QUIC_UNACKED_PACKET_MAP_H_ 7 8 #include <cstddef> 9 #include <cstdint> 10 11 #include "absl/container/inlined_vector.h" 12 #include "absl/strings/str_cat.h" 13 #include "quiche/quic/core/quic_packets.h" 14 #include "quiche/quic/core/quic_transmission_info.h" 15 #include "quiche/quic/core/session_notifier_interface.h" 16 #include "quiche/quic/platform/api/quic_export.h" 17 #include "quiche/quic/platform/api/quic_flags.h" 18 #include "quiche/common/quiche_circular_deque.h" 19 20 namespace quic { 21 22 namespace test { 23 class QuicUnackedPacketMapPeer; 24 } // namespace test 25 26 // Class which tracks unacked packets for three purposes: 27 // 1) Track retransmittable data, including multiple transmissions of frames. 28 // 2) Track packets and bytes in flight for congestion control. 29 // 3) Track sent time of packets to provide RTT measurements from acks. 30 class QUICHE_EXPORT QuicUnackedPacketMap { 31 public: 32 QuicUnackedPacketMap(Perspective perspective); 33 QuicUnackedPacketMap(const QuicUnackedPacketMap&) = delete; 34 QuicUnackedPacketMap& operator=(const QuicUnackedPacketMap&) = delete; 35 ~QuicUnackedPacketMap(); 36 37 // Adds |mutable_packet| to the map and marks it as sent at |sent_time|. 38 // Marks the packet as in flight if |set_in_flight| is true. 39 // Packets marked as in flight are expected to be marked as missing when they 40 // don't arrive, indicating the need for retransmission. 41 // Any retransmittible_frames in |mutable_packet| are swapped from 42 // |mutable_packet| into the QuicTransmissionInfo. 43 void AddSentPacket(SerializedPacket* mutable_packet, 44 TransmissionType transmission_type, QuicTime sent_time, 45 bool set_in_flight, bool measure_rtt, 46 QuicEcnCodepoint ecn_codepoint); 47 48 // Returns true if the packet |packet_number| is unacked. 49 bool IsUnacked(QuicPacketNumber packet_number) const; 50 51 // Notifies session_notifier that frames have been acked. Returns true if any 52 // new data gets acked, returns false otherwise. 53 bool NotifyFramesAcked(const QuicTransmissionInfo& info, 54 QuicTime::Delta ack_delay, QuicTime receive_timestamp); 55 56 // Notifies session_notifier that frames in |info| are considered as lost. 57 void NotifyFramesLost(const QuicTransmissionInfo& info, 58 TransmissionType type); 59 60 // Notifies session_notifier to retransmit frames with |transmission_type|. 61 // Returns true if all data gets retransmitted. 62 bool RetransmitFrames(const QuicFrames& frames, TransmissionType type); 63 64 // Marks |info| as no longer in flight. 65 void RemoveFromInFlight(QuicTransmissionInfo* info); 66 67 // Marks |packet_number| as no longer in flight. 68 void RemoveFromInFlight(QuicPacketNumber packet_number); 69 70 // Called to neuter all unencrypted packets to ensure they do not get 71 // retransmitted. Returns a vector of neutered packet numbers. 72 absl::InlinedVector<QuicPacketNumber, 2> NeuterUnencryptedPackets(); 73 74 // Called to neuter packets in handshake packet number space to ensure they do 75 // not get retransmitted. Returns a vector of neutered packet numbers. 76 // TODO(fayang): Consider to combine this with NeuterUnencryptedPackets. 77 absl::InlinedVector<QuicPacketNumber, 2> NeuterHandshakePackets(); 78 79 // Returns true if |packet_number| has retransmittable frames. This will 80 // return false if all frames of this packet are either non-retransmittable or 81 // have been acked. 82 bool HasRetransmittableFrames(QuicPacketNumber packet_number) const; 83 84 // Returns true if |info| has retransmittable frames. This will return false 85 // if all frames of this packet are either non-retransmittable or have been 86 // acked. 87 bool HasRetransmittableFrames(const QuicTransmissionInfo& info) const; 88 89 // Returns true if there are any unacked packets which have retransmittable 90 // frames. 91 bool HasUnackedRetransmittableFrames() const; 92 93 // Returns true if there are no packets present in the unacked packet map. empty()94 bool empty() const { return unacked_packets_.empty(); } 95 96 // Returns the largest packet number that has been sent. largest_sent_packet()97 QuicPacketNumber largest_sent_packet() const { return largest_sent_packet_; } 98 largest_sent_largest_acked()99 QuicPacketNumber largest_sent_largest_acked() const { 100 return largest_sent_largest_acked_; 101 } 102 103 // Returns the largest packet number that has been acked. largest_acked()104 QuicPacketNumber largest_acked() const { return largest_acked_; } 105 106 // Returns the sum of bytes from all packets in flight. bytes_in_flight()107 QuicByteCount bytes_in_flight() const { return bytes_in_flight_; } packets_in_flight()108 QuicPacketCount packets_in_flight() const { return packets_in_flight_; } 109 110 // Returns the smallest packet number of a serialized packet which has not 111 // been acked by the peer. If there are no unacked packets, returns 0. 112 QuicPacketNumber GetLeastUnacked() const; 113 114 using const_iterator = 115 quiche::QuicheCircularDeque<QuicTransmissionInfo>::const_iterator; 116 using const_reverse_iterator = 117 quiche::QuicheCircularDeque<QuicTransmissionInfo>::const_reverse_iterator; 118 using iterator = quiche::QuicheCircularDeque<QuicTransmissionInfo>::iterator; 119 begin()120 const_iterator begin() const { return unacked_packets_.begin(); } end()121 const_iterator end() const { return unacked_packets_.end(); } rbegin()122 const_reverse_iterator rbegin() const { return unacked_packets_.rbegin(); } rend()123 const_reverse_iterator rend() const { return unacked_packets_.rend(); } begin()124 iterator begin() { return unacked_packets_.begin(); } end()125 iterator end() { return unacked_packets_.end(); } 126 127 // Returns true if there are unacked packets that are in flight. 128 bool HasInFlightPackets() const; 129 130 // Returns the QuicTransmissionInfo associated with |packet_number|, which 131 // must be unacked. 132 const QuicTransmissionInfo& GetTransmissionInfo( 133 QuicPacketNumber packet_number) const; 134 135 // Returns mutable QuicTransmissionInfo associated with |packet_number|, which 136 // must be unacked. 137 QuicTransmissionInfo* GetMutableTransmissionInfo( 138 QuicPacketNumber packet_number); 139 140 // Returns the time that the last unacked packet was sent. 141 QuicTime GetLastInFlightPacketSentTime() const; 142 143 // Returns the time that the last unacked crypto packet was sent. 144 QuicTime GetLastCryptoPacketSentTime() const; 145 146 // Returns the number of unacked packets. 147 size_t GetNumUnackedPacketsDebugOnly() const; 148 149 // Returns true if there are multiple packets in flight. 150 // TODO(fayang): Remove this method and use packets_in_flight_ instead. 151 bool HasMultipleInFlightPackets() const; 152 153 // Returns true if there are any pending crypto packets. 154 bool HasPendingCryptoPackets() const; 155 156 // Returns true if there is any unacked non-crypto stream data. HasUnackedStreamData()157 bool HasUnackedStreamData() const { 158 return session_notifier_->HasUnackedStreamData(); 159 } 160 161 // Removes any retransmittable frames from this transmission or an associated 162 // transmission. It removes now useless transmissions, and disconnects any 163 // other packets from other transmissions. 164 void RemoveRetransmittability(QuicTransmissionInfo* info); 165 166 // Looks up the QuicTransmissionInfo by |packet_number| and calls 167 // RemoveRetransmittability. 168 void RemoveRetransmittability(QuicPacketNumber packet_number); 169 170 // Increases the largest acked. Any packets less or equal to 171 // |largest_acked| are discarded if they are only for the RTT purposes. 172 void IncreaseLargestAcked(QuicPacketNumber largest_acked); 173 174 // Called when |packet_number| gets acked. Maybe increase the largest acked of 175 // |packet_number_space|. 176 void MaybeUpdateLargestAckedOfPacketNumberSpace( 177 PacketNumberSpace packet_number_space, QuicPacketNumber packet_number); 178 179 // Remove any packets no longer needed for retransmission, congestion, or 180 // RTT measurement purposes. 181 void RemoveObsoletePackets(); 182 183 // Try to aggregate acked contiguous stream frames. For noncontiguous stream 184 // frames or control frames, notify the session notifier they get acked 185 // immediately. 186 void MaybeAggregateAckedStreamFrame(const QuicTransmissionInfo& info, 187 QuicTime::Delta ack_delay, 188 QuicTime receive_timestamp); 189 190 // Notify the session notifier of any stream data aggregated in 191 // aggregated_stream_frame_. No effect if the stream frame has an invalid 192 // stream id. 193 void NotifyAggregatedStreamFrameAcked(QuicTime::Delta ack_delay); 194 195 // Returns packet number space that |packet_number| belongs to. Please use 196 // GetPacketNumberSpace(EncryptionLevel) whenever encryption level is 197 // available. 198 PacketNumberSpace GetPacketNumberSpace(QuicPacketNumber packet_number) const; 199 200 // Returns packet number space of |encryption_level|. 201 PacketNumberSpace GetPacketNumberSpace( 202 EncryptionLevel encryption_level) const; 203 204 // Returns largest acked packet number of |packet_number_space|. 205 QuicPacketNumber GetLargestAckedOfPacketNumberSpace( 206 PacketNumberSpace packet_number_space) const; 207 208 // Returns largest sent retransmittable packet number of 209 // |packet_number_space|. 210 QuicPacketNumber GetLargestSentRetransmittableOfPacketNumberSpace( 211 PacketNumberSpace packet_number_space) const; 212 213 // Returns largest sent packet number of |encryption_level|. 214 QuicPacketNumber GetLargestSentPacketOfPacketNumberSpace( 215 EncryptionLevel encryption_level) const; 216 217 // Returns last in flight packet sent time of |packet_number_space|. 218 QuicTime GetLastInFlightPacketSentTime( 219 PacketNumberSpace packet_number_space) const; 220 221 // Returns TransmissionInfo of the first in flight packet. 222 const QuicTransmissionInfo* GetFirstInFlightTransmissionInfo() const; 223 224 // Returns TransmissionInfo of first in flight packet in 225 // |packet_number_space|. 226 const QuicTransmissionInfo* GetFirstInFlightTransmissionInfoOfSpace( 227 PacketNumberSpace packet_number_space) const; 228 229 void SetSessionNotifier(SessionNotifierInterface* session_notifier); 230 231 void EnableMultiplePacketNumberSpacesSupport(); 232 233 // Returns a bitfield of retransmittable frames of last packet in 234 // unacked_packets_. For example, if the packet contains STREAM_FRAME, content 235 // & (1 << STREAM_FRAME) would be set. Returns max uint32_t if 236 // unacked_packets_ is empty. 237 int32_t GetLastPacketContent() const; 238 perspective()239 Perspective perspective() const { return perspective_; } 240 supports_multiple_packet_number_spaces()241 bool supports_multiple_packet_number_spaces() const { 242 return supports_multiple_packet_number_spaces_; 243 } 244 ReserveInitialCapacity(size_t initial_capacity)245 void ReserveInitialCapacity(size_t initial_capacity) { 246 unacked_packets_.reserve(initial_capacity); 247 } 248 DebugString()249 std::string DebugString() const { 250 return absl::StrCat( 251 "{size: ", unacked_packets_.size(), 252 ", least_unacked: ", least_unacked_.ToString(), 253 ", largest_sent_packet: ", largest_sent_packet_.ToString(), 254 ", largest_acked: ", largest_acked_.ToString(), 255 ", bytes_in_flight: ", bytes_in_flight_, 256 ", packets_in_flight: ", packets_in_flight_, "}"); 257 } 258 259 private: 260 friend class test::QuicUnackedPacketMapPeer; 261 262 // Returns true if packet may be useful for an RTT measurement. 263 bool IsPacketUsefulForMeasuringRtt(QuicPacketNumber packet_number, 264 const QuicTransmissionInfo& info) const; 265 266 // Returns true if packet may be useful for congestion control purposes. 267 bool IsPacketUsefulForCongestionControl( 268 const QuicTransmissionInfo& info) const; 269 270 // Returns true if packet may be associated with retransmittable data 271 // directly or through retransmissions. 272 bool IsPacketUsefulForRetransmittableData( 273 const QuicTransmissionInfo& info) const; 274 275 // Returns true if the packet no longer has a purpose in the map. 276 bool IsPacketUseless(QuicPacketNumber packet_number, 277 const QuicTransmissionInfo& info) const; 278 279 const Perspective perspective_; 280 281 QuicPacketNumber largest_sent_packet_; 282 // The largest sent packet we expect to receive an ack for per packet number 283 // space. 284 QuicPacketNumber 285 largest_sent_retransmittable_packets_[NUM_PACKET_NUMBER_SPACES]; 286 // The largest sent largest_acked in an ACK frame. 287 QuicPacketNumber largest_sent_largest_acked_; 288 // The largest received largest_acked from an ACK frame. 289 QuicPacketNumber largest_acked_; 290 // The largest received largest_acked from ACK frame per packet number space. 291 QuicPacketNumber largest_acked_packets_[NUM_PACKET_NUMBER_SPACES]; 292 293 // Newly serialized retransmittable packets are added to this map, which 294 // contains owning pointers to any contained frames. If a packet is 295 // retransmitted, this map will contain entries for both the old and the new 296 // packet. The old packet's retransmittable frames entry will be nullptr, 297 // while the new packet's entry will contain the frames to retransmit. 298 // If the old packet is acked before the new packet, then the old entry will 299 // be removed from the map and the new entry's retransmittable frames will be 300 // set to nullptr. 301 quiche::QuicheCircularDeque<QuicTransmissionInfo> unacked_packets_; 302 303 // The packet at the 0th index of unacked_packets_. 304 QuicPacketNumber least_unacked_; 305 306 QuicByteCount bytes_in_flight_; 307 // Bytes in flight per packet number space. 308 QuicByteCount 309 bytes_in_flight_per_packet_number_space_[NUM_PACKET_NUMBER_SPACES]; 310 QuicPacketCount packets_in_flight_; 311 312 // Time that the last inflight packet was sent. 313 QuicTime last_inflight_packet_sent_time_; 314 // Time that the last in flight packet was sent per packet number space. 315 QuicTime last_inflight_packets_sent_time_[NUM_PACKET_NUMBER_SPACES]; 316 317 // Time that the last unacked crypto packet was sent. 318 QuicTime last_crypto_packet_sent_time_; 319 320 // Aggregates acked stream data across multiple acked sent packets to save CPU 321 // by reducing the number of calls to the session notifier. 322 QuicStreamFrame aggregated_stream_frame_; 323 324 // Receives notifications of frames being retransmitted or acknowledged. 325 SessionNotifierInterface* session_notifier_; 326 327 // If true, supports multiple packet number spaces. 328 bool supports_multiple_packet_number_spaces_; 329 330 // Latched value of the quic_simple_inflight_time flag. 331 bool simple_inflight_time_; 332 }; 333 334 } // namespace quic 335 336 #endif // QUICHE_QUIC_CORE_QUIC_UNACKED_PACKET_MAP_H_ 337