1 // Copyright 2013 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 NET_QUIC_QUIC_SENT_PACKET_MANAGER_H_ 6 #define NET_QUIC_QUIC_SENT_PACKET_MANAGER_H_ 7 8 #include <deque> 9 #include <list> 10 #include <map> 11 #include <queue> 12 #include <set> 13 #include <utility> 14 #include <vector> 15 16 #include "base/containers/hash_tables.h" 17 #include "net/base/linked_hash_map.h" 18 #include "net/quic/congestion_control/send_algorithm_interface.h" 19 #include "net/quic/quic_ack_notifier_manager.h" 20 #include "net/quic/quic_protocol.h" 21 22 NET_EXPORT_PRIVATE extern bool FLAGS_track_retransmission_history; 23 NET_EXPORT_PRIVATE extern bool FLAGS_limit_rto_increase_for_tests; 24 NET_EXPORT_PRIVATE extern bool FLAGS_enable_quic_pacing; 25 26 namespace net { 27 28 namespace test { 29 class QuicConnectionPeer; 30 class QuicSentPacketManagerPeer; 31 } // namespace test 32 33 class QuicClock; 34 class QuicConfig; 35 36 // Class which tracks the set of packets sent on a QUIC connection and contains 37 // a send algorithm to decide when to send new packets. It keeps track of any 38 // retransmittable data associated with each packet. If a packet is 39 // retransmitted, it will keep track of each version of a packet so that if a 40 // previous transmission is acked, the data will not be retransmitted. 41 class NET_EXPORT_PRIVATE QuicSentPacketManager { 42 public: 43 // Struct to store the pending retransmission information. 44 struct PendingRetransmission { PendingRetransmissionPendingRetransmission45 PendingRetransmission(QuicPacketSequenceNumber sequence_number, 46 TransmissionType transmission_type, 47 const RetransmittableFrames& retransmittable_frames, 48 QuicSequenceNumberLength sequence_number_length) 49 : sequence_number(sequence_number), 50 transmission_type(transmission_type), 51 retransmittable_frames(retransmittable_frames), 52 sequence_number_length(sequence_number_length) { 53 } 54 55 QuicPacketSequenceNumber sequence_number; 56 TransmissionType transmission_type; 57 const RetransmittableFrames& retransmittable_frames; 58 QuicSequenceNumberLength sequence_number_length; 59 }; 60 61 // Interface which provides callbacks that the manager needs. 62 class NET_EXPORT_PRIVATE HelperInterface { 63 public: 64 virtual ~HelperInterface(); 65 66 // Called to return the sequence number of the next packet to be sent. 67 virtual QuicPacketSequenceNumber GetNextPacketSequenceNumber() = 0; 68 }; 69 70 QuicSentPacketManager(bool is_server, 71 HelperInterface* helper, 72 const QuicClock* clock, 73 CongestionFeedbackType congestion_type); 74 virtual ~QuicSentPacketManager(); 75 76 virtual void SetFromConfig(const QuicConfig& config); 77 78 virtual void SetMaxPacketSize(QuicByteCount max_packet_size); 79 80 // Called when a new packet is serialized. If the packet contains 81 // retransmittable data, it will be added to the unacked packet map. 82 void OnSerializedPacket(const SerializedPacket& serialized_packet); 83 84 // Called when a packet is retransmitted with a new sequence number. 85 // Replaces the old entry in the unacked packet map with the new 86 // sequence number. 87 void OnRetransmittedPacket(QuicPacketSequenceNumber old_sequence_number, 88 QuicPacketSequenceNumber new_sequence_number); 89 90 // Processes the incoming ack and returns true if the retransmission or ack 91 // alarm should be reset. 92 bool OnIncomingAck(const ReceivedPacketInfo& received_info, 93 QuicTime ack_receive_time); 94 95 // Discards any information for the packet corresponding to |sequence_number|. 96 // If this packet has been retransmitted, information on those packets 97 // will be discarded as well. 98 void DiscardUnackedPacket(QuicPacketSequenceNumber sequence_number); 99 100 // Returns true if the non-FEC packet |sequence_number| is unacked. 101 bool IsUnacked(QuicPacketSequenceNumber sequence_number) const; 102 103 // Requests retransmission of all unacked packets of |retransmission_type|. 104 void RetransmitUnackedPackets(RetransmissionType retransmission_type); 105 106 // Returns true if the unacked packet |sequence_number| has retransmittable 107 // frames. This will only return false if the packet has been acked, if a 108 // previous transmission of this packet was ACK'd, or if this packet has been 109 // retransmitted as with different sequence number. 110 bool HasRetransmittableFrames(QuicPacketSequenceNumber sequence_number) const; 111 112 // Returns true if there are pending retransmissions. 113 bool HasPendingRetransmissions() const; 114 115 // Retrieves the next pending retransmission. 116 PendingRetransmission NextPendingRetransmission(); 117 118 bool HasUnackedPackets() const; 119 120 // Returns the number of unacked packets which have retransmittable frames. 121 size_t GetNumRetransmittablePackets() const; 122 123 // Returns the smallest sequence number of a sent packet which has not been 124 // acked by the peer. Excludes any packets which have been retransmitted 125 // with a new sequence number. If all packets have been acked, returns the 126 // sequence number of the next packet that will be sent. 127 QuicPacketSequenceNumber GetLeastUnackedSentPacket() const; 128 129 // Returns the set of sequence numbers of all unacked packets. 130 // Test only. 131 SequenceNumberSet GetUnackedPackets() const; 132 133 // Returns true if |sequence_number| is a previous transmission of packet. 134 bool IsPreviousTransmission(QuicPacketSequenceNumber sequence_number) const; 135 136 // TODO(ianswett): Combine the congestion control related methods below with 137 // some of the methods above and cleanup the resulting code. 138 // Called when we have received an ack frame from peer. 139 // Returns a set containing all the sequence numbers to be nack retransmitted 140 // as a result of the ack. 141 virtual SequenceNumberSet OnIncomingAckFrame( 142 const ReceivedPacketInfo& received_info, 143 const QuicTime& ack_receive_time); 144 145 // Called when a congestion feedback frame is received from peer. 146 virtual void OnIncomingQuicCongestionFeedbackFrame( 147 const QuicCongestionFeedbackFrame& frame, 148 const QuicTime& feedback_receive_time); 149 150 // Called when we have sent bytes to the peer. This informs the manager both 151 // the number of bytes sent and if they were retransmitted. 152 virtual void OnPacketSent(QuicPacketSequenceNumber sequence_number, 153 QuicTime sent_time, 154 QuicByteCount bytes, 155 TransmissionType transmission_type, 156 HasRetransmittableData has_retransmittable_data); 157 158 // Called when the retransmission timer expires. 159 virtual void OnRetransmissionTimeout(); 160 161 // Called when a packet is timed out, such as an RTO. Removes the bytes from 162 // the congestion manager, but does not change the congestion window size. 163 virtual void OnPacketAbandoned(QuicPacketSequenceNumber sequence_number); 164 165 // Calculate the time until we can send the next packet to the wire. 166 // Note 1: When kUnknownWaitTime is returned, there is no need to poll 167 // TimeUntilSend again until we receive an OnIncomingAckFrame event. 168 // Note 2: Send algorithms may or may not use |retransmit| in their 169 // calculations. 170 virtual QuicTime::Delta TimeUntilSend(QuicTime now, 171 TransmissionType transmission_type, 172 HasRetransmittableData retransmittable, 173 IsHandshake handshake); 174 175 // Returns amount of time for delayed ack timer. 176 const QuicTime::Delta DelayedAckTime(); 177 178 // Returns the current RTO delay. 179 const QuicTime::Delta GetRetransmissionDelay() const; 180 181 // Returns the estimated smoothed RTT calculated by the congestion algorithm. 182 const QuicTime::Delta SmoothedRtt() const; 183 184 // Returns the estimated bandwidth calculated by the congestion algorithm. 185 QuicBandwidth BandwidthEstimate() const; 186 187 // Returns the size of the current congestion window in bytes. Note, this is 188 // not the *available* window. Some send algorithms may not use a congestion 189 // window and will return 0. 190 QuicByteCount GetCongestionWindow() const; 191 192 // Enables pacing if it has not already been enabled, and if 193 // FLAGS_enable_quic_pacing is set. 194 void MaybeEnablePacing(); 195 using_pacing()196 bool using_pacing() const { return using_pacing_; } 197 198 199 private: 200 friend class test::QuicConnectionPeer; 201 friend class test::QuicSentPacketManagerPeer; 202 203 struct TransmissionInfo { TransmissionInfoTransmissionInfo204 TransmissionInfo() 205 : retransmittable_frames(NULL), 206 sequence_number_length(PACKET_1BYTE_SEQUENCE_NUMBER), 207 sent_time(QuicTime::Zero()), 208 previous_transmissions(NULL) { } TransmissionInfoTransmissionInfo209 TransmissionInfo(RetransmittableFrames* retransmittable_frames, 210 QuicSequenceNumberLength sequence_number_length) 211 : retransmittable_frames(retransmittable_frames), 212 sequence_number_length(sequence_number_length), 213 sent_time(QuicTime::Zero()), 214 previous_transmissions(NULL) { 215 } 216 217 RetransmittableFrames* retransmittable_frames; 218 QuicSequenceNumberLength sequence_number_length; 219 // Zero when the packet is serialized, non-zero once it's sent. 220 QuicTime sent_time; 221 // Stores all previous transmissions if the packet has been retransmitted, 222 // and is NULL otherwise. 223 SequenceNumberSet* previous_transmissions; 224 }; 225 226 typedef linked_hash_map<QuicPacketSequenceNumber, 227 TransmissionInfo> UnackedPacketMap; 228 typedef linked_hash_map<QuicPacketSequenceNumber, 229 TransmissionType> PendingRetransmissionMap; 230 typedef base::hash_map<QuicPacketSequenceNumber, SequenceNumberSet*> 231 PreviousTransmissionMap; 232 233 // Process the incoming ack looking for newly ack'd data packets. 234 void HandleAckForSentPackets(const ReceivedPacketInfo& received_info); 235 236 // Update the RTT if the ack is for the largest acked sequence number. 237 void MaybeUpdateRTT(const ReceivedPacketInfo& received_info, 238 const QuicTime& ack_receive_time); 239 240 // Marks |sequence_number| as having been seen by the peer. Returns an 241 // iterator to the next remaining unacked packet. 242 UnackedPacketMap::iterator MarkPacketReceivedByPeer( 243 QuicPacketSequenceNumber sequence_number); 244 245 // Simply removes the entries, if any, from the unacked packet map 246 // and the retransmission map. 247 void DiscardPacket(QuicPacketSequenceNumber sequence_number); 248 249 // Request that |sequence_number| be retransmitted after the other pending 250 // retransmissions. Returns false if there are no retransmittable frames for 251 // |sequence_number| and true if it will be retransmitted. 252 bool MarkForRetransmission(QuicPacketSequenceNumber sequence_number, 253 TransmissionType transmission_type); 254 255 // Returns the length of the serialized sequence number for 256 // the packet |sequence_number|. 257 QuicSequenceNumberLength GetSequenceNumberLength( 258 QuicPacketSequenceNumber sequence_number) const; 259 260 // Clears up to |num_to_clear| previous transmissions in order to make room 261 // in the ack frame for new acks. 262 void ClearPreviousRetransmissions(size_t num_to_clear); 263 264 void CleanupPacketHistory(); 265 266 // Newly serialized retransmittable and fec packets are added to this map, 267 // which contains owning pointers to any contained frames. If a packet is 268 // retransmitted, this map will contain entries for both the old and the new 269 // packet. The old packet's retransmittable frames entry will be NULL, while 270 // the new packet's entry will contain the frames to retransmit. 271 // If the old packet is acked before the new packet, then the old entry will 272 // be removed from the map and the new entry's retransmittable frames will be 273 // set to NULL. 274 UnackedPacketMap unacked_packets_; 275 276 // Pending retransmissions which have not been packetized and sent yet. 277 PendingRetransmissionMap pending_retransmissions_; 278 279 // Tracks if the connection was created by the server. 280 bool is_server_; 281 282 HelperInterface* helper_; 283 284 // An AckNotifier can register to be informed when ACKs have been received for 285 // all packets that a given block of data was sent in. The AckNotifierManager 286 // maintains the currently active notifiers. 287 AckNotifierManager ack_notifier_manager_; 288 289 const QuicClock* clock_; 290 scoped_ptr<SendAlgorithmInterface> send_algorithm_; 291 // Tracks the send time, size, and nack count of sent packets. Packets are 292 // removed after 5 seconds and they've been removed from pending_packets_. 293 SendAlgorithmInterface::SentPacketsMap packet_history_map_; 294 // Packets that are outstanding and have not been abandoned or lost. 295 SequenceNumberSet pending_packets_; 296 QuicTime::Delta rtt_sample_; // RTT estimate from the most recent ACK. 297 // Number of times the RTO timer has fired in a row without receiving an ack. 298 size_t consecutive_rto_count_; 299 bool using_pacing_; 300 301 DISALLOW_COPY_AND_ASSIGN(QuicSentPacketManager); 302 }; 303 304 } // namespace net 305 306 #endif // NET_QUIC_QUIC_SENT_PACKET_MANAGER_H_ 307