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/loss_detection_interface.h"
20#include "net/quic/congestion_control/rtt_stats.h"
21#include "net/quic/congestion_control/send_algorithm_interface.h"
22#include "net/quic/quic_ack_notifier_manager.h"
23#include "net/quic/quic_protocol.h"
24#include "net/quic/quic_unacked_packet_map.h"
25
26namespace net {
27
28namespace test {
29class QuicConnectionPeer;
30class QuicSentPacketManagerPeer;
31}  // namespace test
32
33class QuicClock;
34class QuicConfig;
35struct 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.
42class NET_EXPORT_PRIVATE QuicSentPacketManager {
43 public:
44  // Interface which gets callbacks from the QuicSentPacketManager at
45  // interesting points.  Implementations must not mutate the state of
46  // the packet manager or connection as a result of these callbacks.
47  class NET_EXPORT_PRIVATE DebugDelegate {
48   public:
49    virtual ~DebugDelegate() {}
50
51    // Called when a spurious retransmission is detected.
52    virtual void OnSpuriousPacketRetransmition(
53        TransmissionType transmission_type,
54        QuicByteCount byte_size) {}
55  };
56
57  // Struct to store the pending retransmission information.
58  struct PendingRetransmission {
59    PendingRetransmission(QuicPacketSequenceNumber sequence_number,
60                          TransmissionType transmission_type,
61                          const RetransmittableFrames& retransmittable_frames,
62                          QuicSequenceNumberLength sequence_number_length)
63            : sequence_number(sequence_number),
64              transmission_type(transmission_type),
65              retransmittable_frames(retransmittable_frames),
66              sequence_number_length(sequence_number_length) {
67        }
68
69        QuicPacketSequenceNumber sequence_number;
70        TransmissionType transmission_type;
71        const RetransmittableFrames& retransmittable_frames;
72        QuicSequenceNumberLength sequence_number_length;
73  };
74
75  QuicSentPacketManager(bool is_server,
76                        const QuicClock* clock,
77                        QuicConnectionStats* stats,
78                        CongestionFeedbackType congestion_type,
79                        LossDetectionType loss_type);
80  virtual ~QuicSentPacketManager();
81
82  virtual void SetFromConfig(const QuicConfig& config);
83
84  // Called when a new packet is serialized.  If the packet contains
85  // retransmittable data, it will be added to the unacked packet map.
86  void OnSerializedPacket(const SerializedPacket& serialized_packet);
87
88  // Called when a packet is retransmitted with a new sequence number.
89  // Replaces the old entry in the unacked packet map with the new
90  // sequence number.
91  void OnRetransmittedPacket(QuicPacketSequenceNumber old_sequence_number,
92                             QuicPacketSequenceNumber new_sequence_number);
93
94  // Processes the incoming ack.
95  void OnIncomingAck(const ReceivedPacketInfo& received_info,
96                     QuicTime ack_receive_time);
97
98  // Returns true if the non-FEC packet |sequence_number| is unacked.
99  bool IsUnacked(QuicPacketSequenceNumber sequence_number) const;
100
101  // Requests retransmission of all unacked packets of |retransmission_type|.
102  void RetransmitUnackedPackets(RetransmissionType retransmission_type);
103
104  // Retransmits the oldest pending packet there is still a tail loss probe
105  // pending.  Invoked after OnRetransmissionTimeout.
106  bool MaybeRetransmitTailLossProbe();
107
108  // Removes the retransmittable frames from all unencrypted packets to ensure
109  // they don't get retransmitted.
110  void NeuterUnencryptedPackets();
111
112  // Returns true if the unacked packet |sequence_number| has retransmittable
113  // frames.  This will only return false if the packet has been acked, if a
114  // previous transmission of this packet was ACK'd, or if this packet has been
115  // retransmitted as with different sequence number.
116  bool HasRetransmittableFrames(QuicPacketSequenceNumber sequence_number) const;
117
118  // Returns true if there are pending retransmissions.
119  bool HasPendingRetransmissions() const;
120
121  // Retrieves the next pending retransmission.
122  PendingRetransmission NextPendingRetransmission();
123
124  bool HasUnackedPackets() const;
125
126  // Returns the smallest sequence number of a serialized packet which has not
127  // been acked by the peer.  If there are no unacked packets, returns 0.
128  QuicPacketSequenceNumber GetLeastUnackedSentPacket() const;
129
130  // Called when a congestion feedback frame is received from peer.
131  virtual void OnIncomingQuicCongestionFeedbackFrame(
132      const QuicCongestionFeedbackFrame& frame,
133      const QuicTime& feedback_receive_time);
134
135  // Called when we have sent bytes to the peer.  This informs the manager both
136  // the number of bytes sent and if they were retransmitted.  Returns true if
137  // the sender should reset the retransmission timer.
138  virtual bool OnPacketSent(QuicPacketSequenceNumber sequence_number,
139                            QuicTime sent_time,
140                            QuicByteCount bytes,
141                            TransmissionType transmission_type,
142                            HasRetransmittableData has_retransmittable_data);
143
144  // Called when the retransmission timer expires.
145  virtual void OnRetransmissionTimeout();
146
147  // Calculate the time until we can send the next packet to the wire.
148  // Note 1: When kUnknownWaitTime is returned, there is no need to poll
149  // TimeUntilSend again until we receive an OnIncomingAckFrame event.
150  // Note 2: Send algorithms may or may not use |retransmit| in their
151  // calculations.
152  virtual QuicTime::Delta TimeUntilSend(QuicTime now,
153                                        HasRetransmittableData retransmittable);
154
155  // Returns amount of time for delayed ack timer.
156  const QuicTime::Delta DelayedAckTime() const;
157
158  // Returns the current delay for the retransmission timer, which may send
159  // either a tail loss probe or do a full RTO.  Returns QuicTime::Zero() if
160  // there are no retransmittable packets.
161  const QuicTime GetRetransmissionTime() const;
162
163  const RttStats* GetRttStats() const;
164
165  // Returns the estimated bandwidth calculated by the congestion algorithm.
166  QuicBandwidth BandwidthEstimate() const;
167
168  // Returns the size of the current congestion window in bytes.  Note, this is
169  // not the *available* window.  Some send algorithms may not use a congestion
170  // window and will return 0.
171  QuicByteCount GetCongestionWindow() const;
172
173  // Enables pacing if it has not already been enabled, and if
174  // FLAGS_enable_quic_pacing is set.
175  void MaybeEnablePacing();
176
177  bool using_pacing() const { return using_pacing_; }
178
179  void set_debug_delegate(DebugDelegate* debug_delegate) {
180    debug_delegate_ = debug_delegate;
181  }
182
183 private:
184  friend class test::QuicConnectionPeer;
185  friend class test::QuicSentPacketManagerPeer;
186
187  // The retransmission timer is a single timer which switches modes depending
188  // upon connection state.
189  enum RetransmissionTimeoutMode {
190    // A conventional TCP style RTO.
191    RTO_MODE,
192    // A tail loss probe.  By default, QUIC sends up to two before RTOing.
193    TLP_MODE,
194    // Retransmission of handshake packets prior to handshake completion.
195    HANDSHAKE_MODE,
196    // Re-invoke the loss detection when a packet is not acked before the
197    // loss detection algorithm expects.
198    LOSS_MODE,
199  };
200
201  typedef linked_hash_map<QuicPacketSequenceNumber,
202                          TransmissionType> PendingRetransmissionMap;
203
204  // Process the incoming ack looking for newly ack'd data packets.
205  void HandleAckForSentPackets(const ReceivedPacketInfo& received_info);
206
207  // Returns the current retransmission mode.
208  RetransmissionTimeoutMode GetRetransmissionMode() const;
209
210  // Retransmits all crypto stream packets.
211  void RetransmitCryptoPackets();
212
213  // Retransmits all the packets and abandons by invoking a full RTO.
214  void RetransmitAllPackets();
215
216  // Returns the timer for retransmitting crypto handshake packets.
217  const QuicTime::Delta GetCryptoRetransmissionDelay() const;
218
219  // Returns the timer for a new tail loss probe.
220  const QuicTime::Delta GetTailLossProbeDelay() const;
221
222  // Returns the retransmission timeout, after which a full RTO occurs.
223  const QuicTime::Delta GetRetransmissionDelay() const;
224
225  // Update the RTT if the ack is for the largest acked sequence number.
226  // Returns true if the rtt was updated.
227  bool MaybeUpdateRTT(const ReceivedPacketInfo& received_info,
228                      const QuicTime& ack_receive_time);
229
230  // Invokes the loss detection algorithm and loses and retransmits packets if
231  // necessary.
232  void InvokeLossDetection(QuicTime time);
233
234  // Invokes OnCongestionEvent if |rtt_updated| is true, there are pending acks,
235  // or pending losses.  Clears pending acks and pending losses afterwards.
236  // |bytes_in_flight| is the number of bytes in flight before the losses or
237  // acks.
238  void MaybeInvokeCongestionEvent(bool rtt_updated,
239                                  QuicByteCount bytes_in_flight);
240
241  // Marks |sequence_number| as having been revived by the peer, but not
242  // received, so the packet remains pending if it is and the congestion control
243  // does not consider the packet acked.
244  void MarkPacketRevived(QuicPacketSequenceNumber sequence_number,
245                         QuicTime::Delta delta_largest_observed);
246
247  // Removes the retransmittability and pending properties from the packet at
248  // |it| due to receipt by the peer.  Returns an iterator to the next remaining
249  // unacked packet.
250  QuicUnackedPacketMap::const_iterator MarkPacketHandled(
251      QuicUnackedPacketMap::const_iterator it,
252      QuicTime::Delta delta_largest_observed);
253
254  // Request that |sequence_number| be retransmitted after the other pending
255  // retransmissions.  Does not add it to the retransmissions if it's already
256  // a pending retransmission.
257  void MarkForRetransmission(QuicPacketSequenceNumber sequence_number,
258                             TransmissionType transmission_type);
259
260  // Notify observers about spurious retransmits.
261  void RecordSpuriousRetransmissions(
262      const SequenceNumberSet& all_transmissions,
263      QuicPacketSequenceNumber acked_sequence_number);
264
265  // Newly serialized retransmittable and fec packets are added to this map,
266  // which contains owning pointers to any contained frames.  If a packet is
267  // retransmitted, this map will contain entries for both the old and the new
268  // packet. The old packet's retransmittable frames entry will be NULL, while
269  // the new packet's entry will contain the frames to retransmit.
270  // If the old packet is acked before the new packet, then the old entry will
271  // be removed from the map and the new entry's retransmittable frames will be
272  // set to NULL.
273  QuicUnackedPacketMap unacked_packets_;
274
275  // Pending retransmissions which have not been packetized and sent yet.
276  PendingRetransmissionMap pending_retransmissions_;
277
278  // Tracks if the connection was created by the server.
279  bool is_server_;
280
281  // An AckNotifier can register to be informed when ACKs have been received for
282  // all packets that a given block of data was sent in. The AckNotifierManager
283  // maintains the currently active notifiers.
284  AckNotifierManager ack_notifier_manager_;
285
286  const QuicClock* clock_;
287  QuicConnectionStats* stats_;
288  DebugDelegate* debug_delegate_;
289  RttStats rtt_stats_;
290  scoped_ptr<SendAlgorithmInterface> send_algorithm_;
291  scoped_ptr<LossDetectionInterface> loss_algorithm_;
292
293  QuicPacketSequenceNumber largest_observed_;  // From the most recent ACK.
294  // Number of times the RTO timer has fired in a row without receiving an ack.
295  size_t consecutive_rto_count_;
296  // Number of times the tail loss probe has been sent.
297  size_t consecutive_tlp_count_;
298  // Number of times the crypto handshake has been retransmitted.
299  size_t consecutive_crypto_retransmission_count_;
300  // Whether a tlp packet can be sent even if the send algorithm says not to.
301  bool pending_tlp_transmission_;
302  // Maximum number of tail loss probes to send before firing an RTO.
303  size_t max_tail_loss_probes_;
304  bool using_pacing_;
305
306  // Sets of packets acked and lost as a result of the last congestion event.
307  SendAlgorithmInterface::CongestionMap packets_acked_;
308  SendAlgorithmInterface::CongestionMap packets_lost_;
309
310  DISALLOW_COPY_AND_ASSIGN(QuicSentPacketManager);
311};
312
313}  // namespace net
314
315#endif  // NET_QUIC_QUIC_SENT_PACKET_MANAGER_H_
316