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/quic_protocol.h"
  19
  20 NET_EXPORT_PRIVATE extern bool FLAGS_track_retransmission_history;
  21
  22 namespace net {
  23
  24 // Class which tracks the set of packets sent on a QUIC connection.
  25 // It keeps track of the retransmittable data ssociated with each
  26 // packets. If a packet is retransmitted, it will keep track of each
  27 // version of a packet so that if a previous transmission is acked,
  28 // the data will not be retransmitted.
  29 class NET_EXPORT_PRIVATE QuicSentPacketManager {
  30  public:
  31   // Struct to store the pending retransmission information.
  32   struct PendingRetransmission {
  33     PendingRetransmission(QuicPacketSequenceNumber sequence_number,
  34                           TransmissionType transmission_type,
  35                           const RetransmittableFrames& retransmittable_frames,
  36                           QuicSequenceNumberLength sequence_number_length)
  37             : sequence_number(sequence_number),
  38               transmission_type(transmission_type),
  39               retransmittable_frames(retransmittable_frames),
  40               sequence_number_length(sequence_number_length) {
  41         }
  42
  43         QuicPacketSequenceNumber sequence_number;
  44         TransmissionType transmission_type;
  45         const RetransmittableFrames& retransmittable_frames;
  46         QuicSequenceNumberLength sequence_number_length;
  47   };
  48
  49   // Interface which provides callbacks that the manager needs.
  50   class NET_EXPORT_PRIVATE HelperInterface {
  51    public:
  52     virtual ~HelperInterface();
  53
  54     // Called to return the sequence number of the next packet to be sent.
  55     virtual QuicPacketSequenceNumber GetNextPacketSequenceNumber() = 0;
  56
  57     // Called when a packet has been explicitly NACK'd.  If a packet
  58     // has been retransmitted with mutliple sequence numbers, this will
  59     // only be called for the sequence number (if any) associated with
  60     // retransmittable frames.
  61     virtual void OnPacketNacked(QuicPacketSequenceNumber sequence_number,
  62                                 size_t nack_count) = 0;
  63   };
  64
  65   QuicSentPacketManager(bool is_server, HelperInterface* helper);
  66   virtual ~QuicSentPacketManager();
  67
  68   // Called when a new packet is serialized.  If the packet contains
  69   // retransmittable data, it will be added to the unacked packet map.
  70   void OnSerializedPacket(const SerializedPacket& serialized_packet,
  71                           QuicTime serialized_time);
  72
  73   // Called when a packet is retransmitted with a new sequence number.
  74   // Replaces the old entry in the unacked packet map with the new
  75   // sequence number.
  76   void OnRetransmittedPacket(QuicPacketSequenceNumber old_sequence_number,
  77                              QuicPacketSequenceNumber new_sequence_number);
  78
  79   // Processes the ReceivedPacketInfo data from the incoming ack.
  80   void OnIncomingAck(const ReceivedPacketInfo& received_info,
  81                      bool is_truncated_ack,
  82                      SequenceNumberSet* acked_packets);
  83
  84   // Discards any information for the packet corresponding to |sequence_number|.
  85   // If this packet has been retransmitted, information on those packets
  86   // will be discarded as well.
  87   void DiscardUnackedPacket(QuicPacketSequenceNumber sequence_number);
  88
  89   // Discards all information about fec packet |sequence_number|.
  90   void DiscardFecPacket(QuicPacketSequenceNumber sequence_number);
  91
  92   // Returns true if |sequence_number| is a retransmission of a packet.
  93   bool IsRetransmission(QuicPacketSequenceNumber sequence_number) const;
  94
  95   // Returns the number of times the data in the packet |sequence_number|
  96   // has been transmitted.
  97   size_t GetRetransmissionCount(
  98       QuicPacketSequenceNumber sequence_number) const;
  99
 100   // Returns true if the non-FEC packet |sequence_number| is unacked.
 101   bool IsUnacked(QuicPacketSequenceNumber sequence_number) const;
 102
 103   // Returns true if the FEC packet |sequence_number| is unacked.
 104   bool IsFecUnacked(QuicPacketSequenceNumber sequence_number) const;
 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 the RetransmittableFrames for |sequence_number|.
 113   const RetransmittableFrames& GetRetransmittableFrames(
 114       QuicPacketSequenceNumber sequence_number) const;
 115
 116   // Request that |sequence_number| be retransmitted after the other pending
 117   // retransmissions.  Returns false if there are no retransmittable frames for
 118   // |sequence_number| and true if it will be retransmitted.
 119   bool MarkForRetransmission(QuicPacketSequenceNumber sequence_number,
 120                              TransmissionType transmission_type);
 121
 122   // Returns true if there are pending retransmissions.
 123   bool HasPendingRetransmissions() const;
 124
 125   // Retrieves the next pending retransmission.
 126   PendingRetransmission NextPendingRetransmission();
 127
 128   // Returns the time the fec packet was sent.
 129   QuicTime GetFecSentTime(QuicPacketSequenceNumber sequence_number) const;
 130
 131   // Returns true if there are any unacked packets.
 132   bool HasUnackedPackets() const;
 133
 134   // Returns the number of unacked packets.
 135   size_t GetNumUnackedPackets() const;
 136
 137   // Returns true if there are any unacked FEC packets.
 138   bool HasUnackedFecPackets() const;
 139
 140   // Returns the smallest sequence number of a sent packet which has not been
 141   // acked by the peer.  Excludes any packets which have been retransmitted
 142   // with a new sequence number. If all packets have been acked, returns the
 143   // sequence number of the next packet that will be sent.
 144   QuicPacketSequenceNumber GetLeastUnackedSentPacket() const;
 145
 146   // Returns the smallest sequence number of a sent fec packet which has not
 147   // been acked by the peer.  If all packets have been acked, returns the
 148   // sequence number of the next packet that will be sent.
 149   QuicPacketSequenceNumber GetLeastUnackedFecPacket() const;
 150
 151   // Returns the set of sequence numbers of all unacked packets.
 152   SequenceNumberSet GetUnackedPackets() const;
 153
 154   // Returns true if |sequence_number| is a previous transmission of packet.
 155   bool IsPreviousTransmission(QuicPacketSequenceNumber sequence_number) const;
 156
 157  private:
 158   struct RetransmissionInfo {
 159     RetransmissionInfo() {}
 160     explicit RetransmissionInfo(QuicPacketSequenceNumber sequence_number,
 161                                 QuicSequenceNumberLength sequence_number_length)
 162         : sequence_number(sequence_number),
 163           sequence_number_length(sequence_number_length),
 164           number_nacks(0),
 165           number_retransmissions(0) {
 166     }
 167
 168     QuicPacketSequenceNumber sequence_number;
 169     QuicSequenceNumberLength sequence_number_length;
 170     size_t number_nacks;
 171     // TODO(ianswett): I believe this is now obsolete, or could at least be
 172     // changed to a bool.
 173     size_t number_retransmissions;
 174   };
 175
 176   typedef linked_hash_map<QuicPacketSequenceNumber,
 177                           RetransmittableFrames*> UnackedPacketMap;
 178   typedef linked_hash_map<QuicPacketSequenceNumber,
 179                           QuicTime> UnackedFecPacketMap;
 180   typedef linked_hash_map<QuicPacketSequenceNumber,
 181                           TransmissionType> PendingRetransmissionMap;
 182   typedef base::hash_map<QuicPacketSequenceNumber,
 183                          RetransmissionInfo> RetransmissionMap;
 184   typedef base::hash_map<QuicPacketSequenceNumber, SequenceNumberSet*>
 185                          PreviousTransmissionMap;
 186
 187   // Process the incoming ack looking for newly ack'd data packets.
 188   void HandleAckForSentPackets(const ReceivedPacketInfo& received_info,
 189                                bool is_truncated_ack,
 190                                SequenceNumberSet* acked_packets);
 191
 192   // Process the incoming ack looking for newly ack'd FEC packets.
 193   void HandleAckForSentFecPackets(const ReceivedPacketInfo& received_info,
 194                                   SequenceNumberSet* acked_packets);
 195
 196   // Marks |sequence_number| as having been seen by the peer.  Returns an
 197   // iterator to the next remaining unacked packet.
 198   UnackedPacketMap::iterator MarkPacketReceivedByPeer(
 199       QuicPacketSequenceNumber sequence_number);
 200
 201   // Simply removes the entries, if any, from the unacked packet map
 202   // and the retransmission map.
 203   void DiscardPacket(QuicPacketSequenceNumber sequence_number);
 204
 205   // Returns the length of the serialized sequence number for
 206   // the packet |sequence_number|.
 207   QuicSequenceNumberLength GetSequenceNumberLength(
 208       QuicPacketSequenceNumber sequence_number) const;
 209
 210   // Returns the sequence number of the packet that |sequence_number| was
 211   // most recently transmitted as.
 212   QuicPacketSequenceNumber GetMostRecentTransmission(
 213       QuicPacketSequenceNumber sequence_number) const;
 214
 215   // When new packets are created which may be retransmitted, they are added
 216   // to this map, which contains owning pointers to the contained frames.  If
 217   // a packet is retransmitted, this map will contain entries for both the old
 218   // and the new packet.  The old packet's retransmittable frames entry will be
 219   // NULL, while the new packet's entry will contain the frames to retransmit.
 220   // If the old packet is acked before the new packet, then the old entry will
 221   // be removed from the map and the new entry's retransmittable frames will be
 222   // set to NULL.
 223   UnackedPacketMap unacked_packets_;
 224
 225   // Pending fec packets that have not been acked yet. These packets need to be
 226   // cleared out of the cgst_window after a timeout since FEC packets are never
 227   // retransmitted.
 228   UnackedFecPacketMap unacked_fec_packets_;
 229
 230   // Pending retransmissions which have not been packetized and sent yet.
 231   PendingRetransmissionMap pending_retransmissions_;
 232
 233   // Map from sequence number to the retransmission info for a packet.
 234   // This includes the retransmission timeout, and the NACK count.  Only
 235   // the new transmission of a packet will have entries in this map.
 236   RetransmissionMap retransmission_map_;
 237
 238   // Map from sequence number to set of all sequence number that this packet has
 239   // been transmitted as.  If a packet has not been retransmitted, it will not
 240   // have an entry in this map.  If any transmission of a packet has been acked
 241   // it will not have an entry in this map.
 242   PreviousTransmissionMap previous_transmissions_map_;
 243
 244   // Tracks if the connection was created by the server.
 245   bool is_server_;
 246
 247   HelperInterface* helper_;
 248
 249   DISALLOW_COPY_AND_ASSIGN(QuicSentPacketManager);
 250 };
 251
 252 }  // namespace net
 253
 254 #endif  // NET_QUIC_QUIC_SENT_PACKET_MANAGER_H_