src/net/quic/quic_sent_packet_manager.h

   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_enable_quic_pacing;
  24
  25 namespace net {
  26
  27 namespace test {
  28 class QuicConnectionPeer;
  29 class QuicSentPacketManagerPeer;
  30 }  // namespace test
  31
  32 class QuicClock;
  33 class QuicConfig;
  34
  35 // Class which tracks the set of packets sent on a QUIC connection and contains
  36 // a send algorithm to decide when to send new packets.  It keeps track of any
  37 // retransmittable data associated with each packet. If a packet is
  38 // retransmitted, it will keep track of each version of a packet so that if a
  39 // previous transmission is acked, the data will not be retransmitted.
  40 class NET_EXPORT_PRIVATE QuicSentPacketManager {
  41  public:
  42   // Struct to store the pending retransmission information.
  43   struct PendingRetransmission {
  44     PendingRetransmission(QuicPacketSequenceNumber sequence_number,
  45                           TransmissionType transmission_type,
  46                           const RetransmittableFrames& retransmittable_frames,
  47                           QuicSequenceNumberLength sequence_number_length)
  48             : sequence_number(sequence_number),
  49               transmission_type(transmission_type),
  50               retransmittable_frames(retransmittable_frames),
  51               sequence_number_length(sequence_number_length) {
  52         }
  53
  54         QuicPacketSequenceNumber sequence_number;
  55         TransmissionType transmission_type;
  56         const RetransmittableFrames& retransmittable_frames;
  57         QuicSequenceNumberLength sequence_number_length;
  58   };
  59
  60   // Interface which provides callbacks that the manager needs.
  61   class NET_EXPORT_PRIVATE HelperInterface {
  62    public:
  63     virtual ~HelperInterface();
  64
  65     // Called to return the sequence number of the next packet to be sent.
  66     virtual QuicPacketSequenceNumber GetNextPacketSequenceNumber() = 0;
  67   };
  68
  69   QuicSentPacketManager(bool is_server,
  70                         HelperInterface* helper,
  71                         const QuicClock* clock,
  72                         CongestionFeedbackType congestion_type);
  73   virtual ~QuicSentPacketManager();
  74
  75   virtual void SetFromConfig(const QuicConfig& config);
  76
  77   virtual void SetMaxPacketSize(QuicByteCount max_packet_size);
  78
  79   // Called when a new packet is serialized.  If the packet contains
  80   // retransmittable data, it will be added to the unacked packet map.
  81   void OnSerializedPacket(const SerializedPacket& serialized_packet);
  82
  83   // Called when a packet is retransmitted with a new sequence number.
  84   // Replaces the old entry in the unacked packet map with the new
  85   // sequence number.
  86   void OnRetransmittedPacket(QuicPacketSequenceNumber old_sequence_number,
  87                              QuicPacketSequenceNumber new_sequence_number);
  88
  89   // Processes the incoming ack and returns true if the retransmission or ack
  90   // alarm should be reset.
  91   bool OnIncomingAck(const ReceivedPacketInfo& received_info,
  92                      QuicTime ack_receive_time);
  93
  94   // Discards any information for the packet corresponding to |sequence_number|.
  95   // If this packet has been retransmitted, information on those packets
  96   // will be discarded as well.  Also discards it from the congestion window if
  97   // it is present.
  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   // Called when a congestion feedback frame is received from peer.
 137   virtual void OnIncomingQuicCongestionFeedbackFrame(
 138       const QuicCongestionFeedbackFrame& frame,
 139       const QuicTime& feedback_receive_time);
 140
 141   // Called when we have sent bytes to the peer.  This informs the manager both
 142   // the number of bytes sent and if they were retransmitted.  Returns true if
 143   // the sender should reset the retransmission timer.
 144   virtual bool OnPacketSent(QuicPacketSequenceNumber sequence_number,
 145                             QuicTime sent_time,
 146                             QuicByteCount bytes,
 147                             TransmissionType transmission_type,
 148                             HasRetransmittableData has_retransmittable_data);
 149
 150   // Called when the retransmission timer expires.
 151   virtual void OnRetransmissionTimeout();
 152
 153   // Calculate the time until we can send the next packet to the wire.
 154   // Note 1: When kUnknownWaitTime is returned, there is no need to poll
 155   // TimeUntilSend again until we receive an OnIncomingAckFrame event.
 156   // Note 2: Send algorithms may or may not use |retransmit| in their
 157   // calculations.
 158   virtual QuicTime::Delta TimeUntilSend(QuicTime now,
 159                                         TransmissionType transmission_type,
 160                                         HasRetransmittableData retransmittable,
 161                                         IsHandshake handshake);
 162
 163   // Returns amount of time for delayed ack timer.
 164   const QuicTime::Delta DelayedAckTime() const;
 165
 166   // Returns the current delay for the retransmission timer, which may send
 167   // either a tail loss probe or do a full RTO.  Returns QuicTime::Zero() if
 168   // there are no retransmittable packets.
 169   const QuicTime GetRetransmissionTime() const;
 170
 171   // Returns the estimated smoothed RTT calculated by the congestion algorithm.
 172   const QuicTime::Delta SmoothedRtt() const;
 173
 174   // Returns the estimated bandwidth calculated by the congestion algorithm.
 175   QuicBandwidth BandwidthEstimate() const;
 176
 177   // Returns the size of the current congestion window in bytes.  Note, this is
 178   // not the *available* window.  Some send algorithms may not use a congestion
 179   // window and will return 0.
 180   QuicByteCount GetCongestionWindow() const;
 181
 182   // Enables pacing if it has not already been enabled, and if
 183   // FLAGS_enable_quic_pacing is set.
 184   void MaybeEnablePacing();
 185
 186   bool using_pacing() const { return using_pacing_; }
 187
 188
 189  private:
 190   friend class test::QuicConnectionPeer;
 191   friend class test::QuicSentPacketManagerPeer;
 192
 193   enum ReceivedByPeer {
 194     RECEIVED_BY_PEER,
 195     NOT_RECEIVED_BY_PEER,
 196   };
 197
 198   enum RetransmissionTimeoutMode {
 199     RTO_MODE,
 200     TLP_MODE,
 201     HANDSHAKE_MODE,
 202   };
 203
 204   struct TransmissionInfo {
 205     TransmissionInfo()
 206         : retransmittable_frames(NULL),
 207           sequence_number_length(PACKET_1BYTE_SEQUENCE_NUMBER),
 208           sent_time(QuicTime::Zero()),
 209           previous_transmissions(NULL),
 210           pending(false) { }
 211     TransmissionInfo(RetransmittableFrames* retransmittable_frames,
 212                      QuicSequenceNumberLength sequence_number_length)
 213         : retransmittable_frames(retransmittable_frames),
 214           sequence_number_length(sequence_number_length),
 215           sent_time(QuicTime::Zero()),
 216           previous_transmissions(NULL),
 217           pending(false) {
 218     }
 219
 220     RetransmittableFrames* retransmittable_frames;
 221     QuicSequenceNumberLength sequence_number_length;
 222     // Zero when the packet is serialized, non-zero once it's sent.
 223     QuicTime sent_time;
 224     // Stores all previous transmissions if the packet has been retransmitted,
 225     // and is NULL otherwise.
 226     SequenceNumberSet* previous_transmissions;
 227     // Pending packets have not been abandoned or lost.
 228     bool pending;
 229   };
 230
 231   typedef linked_hash_map<QuicPacketSequenceNumber,
 232                           TransmissionInfo> UnackedPacketMap;
 233   typedef linked_hash_map<QuicPacketSequenceNumber,
 234                           TransmissionType> PendingRetransmissionMap;
 235
 236   static bool HasCryptoHandshake(const TransmissionInfo& transmission_info);
 237
 238   // Returns true if there are unacked packets that are pending.
 239   bool HasPendingPackets() const;
 240
 241   // Process the incoming ack looking for newly ack'd data packets.
 242   void HandleAckForSentPackets(const ReceivedPacketInfo& received_info);
 243
 244   // Called when a packet is timed out, such as an RTO.  Removes the bytes from
 245   // the congestion manager, but does not change the congestion window size.
 246   virtual void OnPacketAbandoned(UnackedPacketMap::iterator it);
 247
 248   // Returns the current retransmission mode.
 249   RetransmissionTimeoutMode GetRetransmissionMode() const;
 250
 251   // Retransmits all crypto stream packets.
 252   void RetransmitCryptoPackets();
 253
 254   // Retransmits the oldest pending packet.
 255   void RetransmitOldestPacket();
 256
 257   // Retransmits all the packets and abandons by invoking a full RTO.
 258   void RetransmitAllPackets();
 259
 260   // Returns the timer for retransmitting crypto handshake packets.
 261   const QuicTime::Delta GetCryptoRetransmissionDelay() const;
 262
 263   // Returns the timer for a new tail loss probe.
 264   const QuicTime::Delta GetTailLossProbeDelay() const;
 265
 266   // Returns the retransmission timeout, after which a full RTO occurs.
 267   const QuicTime::Delta GetRetransmissionDelay() const;
 268
 269   // Update the RTT if the ack is for the largest acked sequence number.
 270   void MaybeUpdateRTT(const ReceivedPacketInfo& received_info,
 271                       const QuicTime& ack_receive_time);
 272
 273   // Chooses whether to nack retransmit any packets based on the receipt info.
 274   // All acks have been handled before this method is invoked.
 275   void MaybeRetransmitOnAckFrame(const ReceivedPacketInfo& received_info,
 276                                  const QuicTime& ack_receive_time);
 277
 278   // Marks |sequence_number| as being fully handled, either due to receipt
 279   // by the peer, or having been discarded as indecipherable.  Returns an
 280   // iterator to the next remaining unacked packet.
 281   UnackedPacketMap::iterator MarkPacketHandled(
 282       QuicPacketSequenceNumber sequence_number,
 283       ReceivedByPeer received_by_peer);
 284
 285   // Removes entries from the unacked packet map.
 286   void DiscardPacket(QuicPacketSequenceNumber sequence_number);
 287
 288   // Request that |sequence_number| be retransmitted after the other pending
 289   // retransmissions.  Does not add it to the retransmissions if it's already
 290   // a pending retransmission.
 291   void MarkForRetransmission(QuicPacketSequenceNumber sequence_number,
 292                              TransmissionType transmission_type);
 293
 294   // Clears up to |num_to_clear| previous transmissions in order to make room
 295   // in the ack frame for new acks.
 296   void ClearPreviousRetransmissions(size_t num_to_clear);
 297
 298   void CleanupPacketHistory();
 299
 300   // Removes |sequence_number| as a previous transmission of any other packets.
 301   void RemovePreviousTransmission(QuicPacketSequenceNumber sequence_number);
 302
 303   // Newly serialized retransmittable and fec packets are added to this map,
 304   // which contains owning pointers to any contained frames.  If a packet is
 305   // retransmitted, this map will contain entries for both the old and the new
 306   // packet. The old packet's retransmittable frames entry will be NULL, while
 307   // the new packet's entry will contain the frames to retransmit.
 308   // If the old packet is acked before the new packet, then the old entry will
 309   // be removed from the map and the new entry's retransmittable frames will be
 310   // set to NULL.
 311   UnackedPacketMap unacked_packets_;
 312
 313   // Pending retransmissions which have not been packetized and sent yet.
 314   PendingRetransmissionMap pending_retransmissions_;
 315
 316   // Tracks if the connection was created by the server.
 317   bool is_server_;
 318
 319   HelperInterface* helper_;
 320
 321   // An AckNotifier can register to be informed when ACKs have been received for
 322   // all packets that a given block of data was sent in. The AckNotifierManager
 323   // maintains the currently active notifiers.
 324   AckNotifierManager ack_notifier_manager_;
 325
 326   const QuicClock* clock_;
 327   scoped_ptr<SendAlgorithmInterface> send_algorithm_;
 328   // Tracks the send time, size, and nack count of sent packets.  Packets are
 329   // removed after 5 seconds and they've been removed from pending_packets_.
 330   SendAlgorithmInterface::SentPacketsMap packet_history_map_;
 331   QuicTime::Delta rtt_sample_;  // RTT estimate from the most recent ACK.
 332   // Number of outstanding crypto handshake packets.
 333   size_t pending_crypto_packet_count_;
 334   // Number of times the RTO timer has fired in a row without receiving an ack.
 335   size_t consecutive_rto_count_;
 336   // Number of times the tail loss probe has been sent.
 337   size_t consecutive_tlp_count_;
 338   // Number of times the crypto handshake has been retransmitted.
 339   size_t consecutive_crypto_retransmission_count_;
 340   // Maximum number of tail loss probes to send before firing an RTO.
 341   size_t max_tail_loss_probes_;
 342   bool using_pacing_;
 343
 344   DISALLOW_COPY_AND_ASSIGN(QuicSentPacketManager);
 345 };
 346
 347 }  // namespace net
 348
 349 #endif  // NET_QUIC_QUIC_SENT_PACKET_MANAGER_H_