1// Copyright 2014 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_UNACKED_PACKET_MAP_H_
6#define NET_QUIC_QUIC_UNACKED_PACKET_MAP_H_
7
8#include <deque>
9
10#include "net/quic/quic_protocol.h"
11
12namespace net {
13
14// Class which tracks unacked packets for three purposes:
15// 1) Track retransmittable data, including multiple transmissions of frames.
16// 2) Track packets and bytes in flight for congestion control.
17// 3) Track sent time of packets to provide RTT measurements from acks.
18class NET_EXPORT_PRIVATE QuicUnackedPacketMap {
19 public:
20  QuicUnackedPacketMap();
21  ~QuicUnackedPacketMap();
22
23  // Adds |serialized_packet| to the map.  Does not mark it in flight.
24  void AddPacket(const SerializedPacket& serialized_packet);
25
26  // Called when a packet is retransmitted with a new sequence number.
27  // |old_sequence_number| will remain unacked, but will have no
28  // retransmittable data associated with it. |new_sequence_number| will
29  // be both unacked and associated with retransmittable data.
30  void OnRetransmittedPacket(QuicPacketSequenceNumber old_sequence_number,
31                             QuicPacketSequenceNumber new_sequence_number,
32                             TransmissionType transmission_type);
33
34  // Returns true if the packet |sequence_number| is unacked.
35  bool IsUnacked(QuicPacketSequenceNumber sequence_number) const;
36
37  // Sets the nack count to the max of the current nack count and |min_nacks|.
38  void NackPacket(QuicPacketSequenceNumber sequence_number,
39                  size_t min_nacks);
40
41  // Marks |sequence_number| as no longer in flight.
42  void RemoveFromInFlight(QuicPacketSequenceNumber sequence_number);
43
44  // Returns true if the unacked packet |sequence_number| has retransmittable
45  // frames.  This will return false if the packet has been acked, if a
46  // previous transmission of this packet was ACK'd, or if this packet has been
47  // retransmitted as with different sequence number, or if the packet never
48  // had any retransmittable packets in the first place.
49  bool HasRetransmittableFrames(QuicPacketSequenceNumber sequence_number) const;
50
51  // Returns true if there are any unacked packets.
52  bool HasUnackedPackets() const;
53
54  // Returns true if there are any unacked packets which have retransmittable
55  // frames.
56  bool HasUnackedRetransmittableFrames() const;
57
58  // Returns the largest sequence number that has been sent.
59  QuicPacketSequenceNumber largest_sent_packet() const {
60    return largest_sent_packet_;
61  }
62
63  // Returns the largest sequence number that has been acked.
64  QuicPacketSequenceNumber largest_observed() const {
65    return largest_observed_;
66  }
67
68  // Returns the sum of bytes from all packets in flight.
69  QuicByteCount bytes_in_flight() const {
70    return bytes_in_flight_;
71  }
72
73  // Returns the smallest sequence number of a serialized packet which has not
74  // been acked by the peer.  If there are no unacked packets, returns 0.
75  QuicPacketSequenceNumber GetLeastUnacked() const;
76
77  // Sets a packet as sent with the sent time |sent_time|.  Marks the packet
78  // as in flight if |set_in_flight| is true.
79  // Packets marked as in flight are expected to be marked as missing when they
80  // don't arrive, indicating the need for retransmission.
81  void SetSent(QuicPacketSequenceNumber sequence_number,
82               QuicTime sent_time,
83               QuicByteCount bytes_sent,
84               bool set_in_flight);
85
86  // Restores the in flight status for a packet that was previously sent.
87  void RestoreInFlight(QuicPacketSequenceNumber sequence_number);
88
89  // Clears all previous transmissions in order to make room in the ack frame
90  // for newly acked packets.
91  void ClearAllPreviousRetransmissions();
92
93  typedef std::deque<TransmissionInfo> UnackedPacketMap;
94
95  typedef UnackedPacketMap::const_iterator const_iterator;
96
97  const_iterator begin() const { return unacked_packets_.begin(); }
98  const_iterator end() const { return unacked_packets_.end(); }
99
100  // Returns true if there are unacked packets that are in flight.
101  bool HasInFlightPackets() const;
102
103  // Returns the TransmissionInfo associated with |sequence_number|, which
104  // must be unacked.
105  const TransmissionInfo& GetTransmissionInfo(
106      QuicPacketSequenceNumber sequence_number) const;
107
108  // Returns the time that the last unacked packet was sent.
109  QuicTime GetLastPacketSentTime() const;
110
111  // Returns the time that the first in flight packet was sent.
112  QuicTime GetFirstInFlightPacketSentTime() const;
113
114  // Returns the number of unacked packets.
115  size_t GetNumUnackedPacketsDebugOnly() const;
116
117  // Returns true if there are multiple packets in flight.
118  bool HasMultipleInFlightPackets() const;
119
120  // Returns true if there are any pending crypto packets.
121  bool HasPendingCryptoPackets() const;
122
123  // Removes any retransmittable frames from this transmission or an associated
124  // transmission.  It removes now useless transmissions, and disconnects any
125  // other packets from other transmissions.
126  void RemoveRetransmittability(QuicPacketSequenceNumber sequence_number);
127
128  // Removes any other retransmissions and marks all transmissions unackable.
129  void RemoveAckability(TransmissionInfo* info);
130
131  // Increases the largest observed.  Any packets less or equal to
132  // |largest_acked_packet| are discarded if they are only for the RTT purposes.
133  void IncreaseLargestObserved(QuicPacketSequenceNumber largest_observed);
134
135  // Remove any packets no longer needed for retransmission, congestion, or
136  // RTT measurement purposes.
137  void RemoveObsoletePackets();
138
139 private:
140  void MaybeRemoveRetransmittableFrames(TransmissionInfo* transmission_info);
141
142  // Returns true if the packet no longer has a purpose in the map.
143  bool IsPacketUseless(QuicPacketSequenceNumber sequence_number,
144                       const TransmissionInfo& info) const;
145  // Returns true if the packet is useless or it's only purpose is RTT
146  // measurement, and it's old enough that is unlikely to ever happen.
147  bool IsPacketRemovable(QuicPacketSequenceNumber sequence_number,
148                         const TransmissionInfo& info) const;
149
150  QuicPacketSequenceNumber largest_sent_packet_;
151  QuicPacketSequenceNumber largest_observed_;
152
153  // Newly serialized retransmittable and fec packets are added to this map,
154  // which contains owning pointers to any contained frames.  If a packet is
155  // retransmitted, this map will contain entries for both the old and the new
156  // packet. The old packet's retransmittable frames entry will be NULL, while
157  // the new packet's entry will contain the frames to retransmit.
158  // If the old packet is acked before the new packet, then the old entry will
159  // be removed from the map and the new entry's retransmittable frames will be
160  // set to NULL.
161  UnackedPacketMap unacked_packets_;
162  // The packet at the 0th index of unacked_packets_.
163  QuicPacketSequenceNumber least_unacked_;
164
165  size_t bytes_in_flight_;
166  // Number of retransmittable crypto handshake packets.
167  size_t pending_crypto_packet_count_;
168
169  DISALLOW_COPY_AND_ASSIGN(QuicUnackedPacketMap);
170};
171
172}  // namespace net
173
174#endif  // NET_QUIC_QUIC_UNACKED_PACKET_MAP_H_
175