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 #include <deque> 11 12 #include "net/third_party/quiche/src/quic/core/quic_circular_deque.h" 13 #include "net/third_party/quiche/src/quic/core/quic_packets.h" 14 #include "net/third_party/quiche/src/quic/core/quic_transmission_info.h" 15 #include "net/third_party/quiche/src/quic/core/session_notifier_interface.h" 16 #include "net/third_party/quiche/src/quic/platform/api/quic_export.h" 17 #include "net/third_party/quiche/src/quic/platform/api/quic_flags.h" 18 19 namespace quic { 20 21 namespace test { 22 class QuicUnackedPacketMapPeer; 23 } // namespace test 24 25 // Class which tracks unacked packets for three purposes: 26 // 1) Track retransmittable data, including multiple transmissions of frames. 27 // 2) Track packets and bytes in flight for congestion control. 28 // 3) Track sent time of packets to provide RTT measurements from acks. 29 class QUIC_EXPORT_PRIVATE QuicUnackedPacketMap { 30 public: 31 QuicUnackedPacketMap(Perspective perspective); 32 QuicUnackedPacketMap(const QuicUnackedPacketMap&) = delete; 33 QuicUnackedPacketMap& operator=(const QuicUnackedPacketMap&) = delete; 34 ~QuicUnackedPacketMap(); 35 36 // Adds |mutable_packet| to the map and marks it as sent at |sent_time|. 37 // Marks the packet as in flight if |set_in_flight| is true. 38 // Packets marked as in flight are expected to be marked as missing when they 39 // don't arrive, indicating the need for retransmission. 40 // Any retransmittible_frames in |mutable_packet| are swapped from 41 // |mutable_packet| into the QuicTransmissionInfo. 42 void AddSentPacket(SerializedPacket* mutable_packet, 43 TransmissionType transmission_type, 44 QuicTime sent_time, 45 bool set_in_flight, 46 bool measure_rtt); 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, 55 QuicTime receive_timestamp); 56 57 // Notifies session_notifier that frames in |info| are considered as lost. 58 void NotifyFramesLost(const QuicTransmissionInfo& info, 59 TransmissionType type); 60 61 // Notifies session_notifier to retransmit frames in |info| with 62 // |transmission_type|. 63 void RetransmitFrames(const QuicTransmissionInfo& info, 64 TransmissionType type); 65 66 // Marks |info| as no longer in flight. 67 void RemoveFromInFlight(QuicTransmissionInfo* info); 68 69 // Marks |packet_number| as no longer in flight. 70 void RemoveFromInFlight(QuicPacketNumber packet_number); 71 72 // Called to neuter all unencrypted packets to ensure they do not get 73 // retransmitted. Returns a vector of neutered packet numbers. 74 QuicInlinedVector<QuicPacketNumber, 2> NeuterUnencryptedPackets(); 75 76 // Called to neuter packets in handshake packet number space to ensure they do 77 // not get retransmitted. Returns a vector of neutered packet numbers. 78 // TODO(fayang): Consider to combine this with NeuterUnencryptedPackets. 79 QuicInlinedVector<QuicPacketNumber, 2> NeuterHandshakePackets(); 80 81 // Returns true if |packet_number| has retransmittable frames. This will 82 // return false if all frames of this packet are either non-retransmittable or 83 // have been acked. 84 bool HasRetransmittableFrames(QuicPacketNumber packet_number) const; 85 86 // Returns true if |info| has retransmittable frames. This will return false 87 // if all frames of this packet are either non-retransmittable or have been 88 // acked. 89 bool HasRetransmittableFrames(const QuicTransmissionInfo& info) const; 90 91 // Returns true if there are any unacked packets which have retransmittable 92 // frames. 93 bool HasUnackedRetransmittableFrames() const; 94 95 // Returns true if there are no packets present in the unacked packet map. empty()96 bool empty() const { return unacked_packets_empty(); } 97 use_circular_deque()98 bool use_circular_deque() const { return use_circular_deque_; } 99 100 // Returns the largest packet number that has been sent. largest_sent_packet()101 QuicPacketNumber largest_sent_packet() const { return largest_sent_packet_; } 102 largest_sent_largest_acked()103 QuicPacketNumber largest_sent_largest_acked() const { 104 return largest_sent_largest_acked_; 105 } 106 107 // Returns the largest packet number that has been acked. largest_acked()108 QuicPacketNumber largest_acked() const { return largest_acked_; } 109 110 // Returns the sum of bytes from all packets in flight. bytes_in_flight()111 QuicByteCount bytes_in_flight() const { return bytes_in_flight_; } packets_in_flight()112 QuicPacketCount packets_in_flight() const { return packets_in_flight_; } 113 114 // Returns the smallest packet number of a serialized packet which has not 115 // been acked by the peer. If there are no unacked packets, returns 0. 116 QuicPacketNumber GetLeastUnacked() const; 117 118 template <typename Itr1, typename Itr2> 119 class QUIC_EXPORT_PRIVATE IteratorWrapper { 120 public: IteratorWrapper(Itr1 itr1)121 explicit IteratorWrapper(Itr1 itr1) { 122 itr_.template emplace<0>(std::move(itr1)); 123 } IteratorWrapper(Itr2 itr2)124 explicit IteratorWrapper(Itr2 itr2) { 125 itr_.template emplace<1>(std::move(itr2)); 126 } 127 128 auto& operator*() const { 129 return absl::visit( 130 [](const auto& itr) -> auto& { return *itr; }, itr_); 131 } 132 133 auto* operator->() const { 134 return absl::visit([](const auto& itr) { return &*itr; }, itr_); 135 } 136 137 IteratorWrapper& operator++() { 138 absl::visit([](auto& itr) { ++itr; }, itr_); 139 return *this; 140 } 141 142 IteratorWrapper& operator+=(int difference) { 143 absl::visit([difference](auto& itr) { itr += difference; }, itr_); 144 return *this; 145 } 146 147 IteratorWrapper operator++(int) { 148 return absl::visit([](auto& itr) { IteratorWrapper(itr++); }, itr_); 149 } 150 151 bool operator!=(const IteratorWrapper& other) const { 152 return itr_ != other.itr_; 153 } 154 155 private: 156 absl::variant<Itr1, Itr2> itr_; 157 }; 158 159 using const_iterator = 160 IteratorWrapper<std::deque<QuicTransmissionInfo>::const_iterator, 161 QuicCircularDeque<QuicTransmissionInfo>::const_iterator>; 162 using const_reverse_iterator = IteratorWrapper< 163 std::deque<QuicTransmissionInfo>::const_reverse_iterator, 164 QuicCircularDeque<QuicTransmissionInfo>::const_reverse_iterator>; 165 using iterator = 166 IteratorWrapper<std::deque<QuicTransmissionInfo>::iterator, 167 QuicCircularDeque<QuicTransmissionInfo>::iterator>; 168 begin()169 const_iterator begin() const { 170 return use_circular_deque_ ? const_iterator(unacked_packets_.begin()) 171 : const_iterator(unacked_packets_deque_.begin()); 172 } end()173 const_iterator end() const { 174 return use_circular_deque_ ? const_iterator(unacked_packets_.end()) 175 : const_iterator(unacked_packets_deque_.end()); 176 } rbegin()177 const_reverse_iterator rbegin() const { 178 return use_circular_deque_ 179 ? const_reverse_iterator(unacked_packets_.rbegin()) 180 : const_reverse_iterator(unacked_packets_deque_.rbegin()); 181 } rend()182 const_reverse_iterator rend() const { 183 return use_circular_deque_ 184 ? const_reverse_iterator(unacked_packets_.rend()) 185 : const_reverse_iterator(unacked_packets_deque_.rend()); 186 } begin()187 iterator begin() { 188 return use_circular_deque_ ? iterator(unacked_packets_.begin()) 189 : iterator(unacked_packets_deque_.begin()); 190 } end()191 iterator end() { 192 return use_circular_deque_ ? iterator(unacked_packets_.end()) 193 : iterator(unacked_packets_deque_.end()); 194 } 195 196 // Returns true if there are unacked packets that are in flight. 197 bool HasInFlightPackets() const; 198 199 // Returns the QuicTransmissionInfo associated with |packet_number|, which 200 // must be unacked. 201 const QuicTransmissionInfo& GetTransmissionInfo( 202 QuicPacketNumber packet_number) const; 203 204 // Returns mutable QuicTransmissionInfo associated with |packet_number|, which 205 // must be unacked. 206 QuicTransmissionInfo* GetMutableTransmissionInfo( 207 QuicPacketNumber packet_number); 208 209 // Returns the time that the last unacked packet was sent. 210 QuicTime GetLastInFlightPacketSentTime() const; 211 212 // Returns the time that the last unacked crypto packet was sent. 213 QuicTime GetLastCryptoPacketSentTime() const; 214 215 // Returns the number of unacked packets. 216 size_t GetNumUnackedPacketsDebugOnly() const; 217 218 // Returns true if there are multiple packets in flight. 219 // TODO(fayang): Remove this method and use packets_in_flight_ instead. 220 bool HasMultipleInFlightPackets() const; 221 222 // Returns true if there are any pending crypto packets. 223 bool HasPendingCryptoPackets() const; 224 225 // Returns true if there is any unacked non-crypto stream data. HasUnackedStreamData()226 bool HasUnackedStreamData() const { 227 return session_notifier_->HasUnackedStreamData(); 228 } 229 230 // Removes any retransmittable frames from this transmission or an associated 231 // transmission. It removes now useless transmissions, and disconnects any 232 // other packets from other transmissions. 233 void RemoveRetransmittability(QuicTransmissionInfo* info); 234 235 // Looks up the QuicTransmissionInfo by |packet_number| and calls 236 // RemoveRetransmittability. 237 void RemoveRetransmittability(QuicPacketNumber packet_number); 238 239 // Increases the largest acked. Any packets less or equal to 240 // |largest_acked| are discarded if they are only for the RTT purposes. 241 void IncreaseLargestAcked(QuicPacketNumber largest_acked); 242 243 // Called when |packet_number| gets acked. Maybe increase the largest acked of 244 // |packet_number_space|. 245 void MaybeUpdateLargestAckedOfPacketNumberSpace( 246 PacketNumberSpace packet_number_space, 247 QuicPacketNumber packet_number); 248 249 // Remove any packets no longer needed for retransmission, congestion, or 250 // RTT measurement purposes. 251 void RemoveObsoletePackets(); 252 253 // Try to aggregate acked contiguous stream frames. For noncontiguous stream 254 // frames or control frames, notify the session notifier they get acked 255 // immediately. 256 void MaybeAggregateAckedStreamFrame(const QuicTransmissionInfo& info, 257 QuicTime::Delta ack_delay, 258 QuicTime receive_timestamp); 259 260 // Notify the session notifier of any stream data aggregated in 261 // aggregated_stream_frame_. No effect if the stream frame has an invalid 262 // stream id. 263 void NotifyAggregatedStreamFrameAcked(QuicTime::Delta ack_delay); 264 265 // Returns packet number space that |packet_number| belongs to. Please use 266 // GetPacketNumberSpace(EncryptionLevel) whenever encryption level is 267 // available. 268 PacketNumberSpace GetPacketNumberSpace(QuicPacketNumber packet_number) const; 269 270 // Returns packet number space of |encryption_level|. 271 PacketNumberSpace GetPacketNumberSpace( 272 EncryptionLevel encryption_level) const; 273 274 // Returns largest acked packet number of |packet_number_space|. 275 QuicPacketNumber GetLargestAckedOfPacketNumberSpace( 276 PacketNumberSpace packet_number_space) const; 277 278 // Returns largest sent retransmittable packet number of 279 // |packet_number_space|. 280 QuicPacketNumber GetLargestSentRetransmittableOfPacketNumberSpace( 281 PacketNumberSpace packet_number_space) const; 282 283 // Returns largest sent packet number of |encryption_level|. 284 QuicPacketNumber GetLargestSentPacketOfPacketNumberSpace( 285 EncryptionLevel encryption_level) const; 286 287 // Returns last in flight packet sent time of |packet_number_space|. 288 QuicTime GetLastInFlightPacketSentTime( 289 PacketNumberSpace packet_number_space) const; 290 291 // Returns TransmissionInfo of the first in flight packet. 292 const QuicTransmissionInfo* GetFirstInFlightTransmissionInfo() const; 293 294 // Returns TransmissionInfo of first in flight packet in 295 // |packet_number_space|. 296 const QuicTransmissionInfo* GetFirstInFlightTransmissionInfoOfSpace( 297 PacketNumberSpace packet_number_space) const; 298 299 void SetSessionNotifier(SessionNotifierInterface* session_notifier); 300 301 void EnableMultiplePacketNumberSpacesSupport(); 302 303 // Returns a bitfield of retransmittable frames of last packet in 304 // unacked_packets_. For example, if the packet contains STREAM_FRAME, content 305 // & (1 << STREAM_FRAME) would be set. Returns max uint32_t if 306 // unacked_packets_ is empty. 307 int32_t GetLastPacketContent() const; 308 perspective()309 Perspective perspective() const { return perspective_; } 310 supports_multiple_packet_number_spaces()311 bool supports_multiple_packet_number_spaces() const { 312 return supports_multiple_packet_number_spaces_; 313 } 314 ReserveInitialCapacity(size_t initial_capacity)315 void ReserveInitialCapacity(size_t initial_capacity) { 316 if (use_circular_deque_) { 317 unacked_packets_.reserve(initial_capacity); 318 } 319 } 320 321 private: 322 friend class test::QuicUnackedPacketMapPeer; 323 324 // TODO(haoyuewang) Remove these methods when deprecate 325 // quic_use_circular_deque_for_unacked_packets flag. unacked_packets_size()326 size_t unacked_packets_size() const { 327 return use_circular_deque_ ? unacked_packets_.size() 328 : unacked_packets_deque_.size(); 329 } 330 unacked_packets_at(int index)331 const QuicTransmissionInfo& unacked_packets_at(int index) const { 332 return use_circular_deque_ ? unacked_packets_[index] 333 : unacked_packets_deque_[index]; 334 } 335 unacked_packets_at(int index)336 QuicTransmissionInfo& unacked_packets_at(int index) { 337 return use_circular_deque_ ? unacked_packets_[index] 338 : unacked_packets_deque_[index]; 339 } 340 unacked_packets_front()341 const QuicTransmissionInfo& unacked_packets_front() const { 342 return use_circular_deque_ ? unacked_packets_.front() 343 : unacked_packets_deque_.front(); 344 } 345 unacked_packets_front()346 QuicTransmissionInfo& unacked_packets_front() { 347 return use_circular_deque_ ? unacked_packets_.front() 348 : unacked_packets_deque_.front(); 349 } 350 unacked_packets_back()351 const QuicTransmissionInfo& unacked_packets_back() const { 352 return use_circular_deque_ ? unacked_packets_.back() 353 : unacked_packets_deque_.back(); 354 } 355 unacked_packets_back()356 QuicTransmissionInfo& unacked_packets_back() { 357 return use_circular_deque_ ? unacked_packets_.back() 358 : unacked_packets_deque_.back(); 359 } 360 unacked_packets_push_back(QuicTransmissionInfo info)361 void unacked_packets_push_back(QuicTransmissionInfo info) { 362 if (use_circular_deque_) { 363 unacked_packets_.push_back(std::move(info)); 364 } else { 365 unacked_packets_deque_.push_back(std::move(info)); 366 } 367 } 368 unacked_packets_pop_front()369 void unacked_packets_pop_front() { 370 if (use_circular_deque_) { 371 unacked_packets_.pop_front(); 372 } else { 373 unacked_packets_deque_.pop_front(); 374 } 375 } 376 unacked_packets_empty()377 bool unacked_packets_empty() const { 378 return use_circular_deque_ ? unacked_packets_.empty() 379 : unacked_packets_deque_.empty(); 380 } 381 382 // Returns true if packet may be useful for an RTT measurement. 383 bool IsPacketUsefulForMeasuringRtt(QuicPacketNumber packet_number, 384 const QuicTransmissionInfo& info) const; 385 386 // Returns true if packet may be useful for congestion control purposes. 387 bool IsPacketUsefulForCongestionControl( 388 const QuicTransmissionInfo& info) const; 389 390 // Returns true if packet may be associated with retransmittable data 391 // directly or through retransmissions. 392 bool IsPacketUsefulForRetransmittableData( 393 const QuicTransmissionInfo& info) const; 394 395 // Returns true if the packet no longer has a purpose in the map. 396 bool IsPacketUseless(QuicPacketNumber packet_number, 397 const QuicTransmissionInfo& info) const; 398 399 const Perspective perspective_; 400 401 QuicPacketNumber largest_sent_packet_; 402 // The largest sent packet we expect to receive an ack for per packet number 403 // space. 404 QuicPacketNumber 405 largest_sent_retransmittable_packets_[NUM_PACKET_NUMBER_SPACES]; 406 // The largest sent largest_acked in an ACK frame. 407 QuicPacketNumber largest_sent_largest_acked_; 408 // The largest received largest_acked from an ACK frame. 409 QuicPacketNumber largest_acked_; 410 // The largest received largest_acked from ACK frame per packet number space. 411 QuicPacketNumber largest_acked_packets_[NUM_PACKET_NUMBER_SPACES]; 412 413 // Newly serialized retransmittable packets are added to this map, which 414 // contains owning pointers to any contained frames. If a packet is 415 // retransmitted, this map will contain entries for both the old and the new 416 // packet. The old packet's retransmittable frames entry will be nullptr, 417 // while the new packet's entry will contain the frames to retransmit. 418 // If the old packet is acked before the new packet, then the old entry will 419 // be removed from the map and the new entry's retransmittable frames will be 420 // set to nullptr. 421 QuicCircularDeque<QuicTransmissionInfo> unacked_packets_; 422 std::deque<QuicTransmissionInfo> unacked_packets_deque_; 423 424 const bool use_circular_deque_ = 425 GetQuicReloadableFlag(quic_use_circular_deque_for_unacked_packets); 426 427 // The packet at the 0th index of unacked_packets_. 428 QuicPacketNumber least_unacked_; 429 430 QuicByteCount bytes_in_flight_; 431 // Bytes in flight per packet number space. 432 QuicByteCount 433 bytes_in_flight_per_packet_number_space_[NUM_PACKET_NUMBER_SPACES]; 434 QuicPacketCount packets_in_flight_; 435 436 // Time that the last inflight packet was sent. 437 QuicTime last_inflight_packet_sent_time_; 438 // Time that the last in flight packet was sent per packet number space. 439 QuicTime last_inflight_packets_sent_time_[NUM_PACKET_NUMBER_SPACES]; 440 441 // Time that the last unacked crypto packet was sent. 442 QuicTime last_crypto_packet_sent_time_; 443 444 // Aggregates acked stream data across multiple acked sent packets to save CPU 445 // by reducing the number of calls to the session notifier. 446 QuicStreamFrame aggregated_stream_frame_; 447 448 // Receives notifications of frames being retransmitted or acknowledged. 449 SessionNotifierInterface* session_notifier_; 450 451 // If true, supports multiple packet number spaces. 452 bool supports_multiple_packet_number_spaces_; 453 454 // Latched value of the quic_simple_inflight_time flag. 455 bool simple_inflight_time_; 456 }; 457 458 } // namespace quic 459 460 #endif // QUICHE_QUIC_CORE_QUIC_UNACKED_PACKET_MAP_H_ 461