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