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#include "net/quic/quic_unacked_packet_map.h"
6
7#include "base/logging.h"
8#include "base/stl_util.h"
9#include "net/quic/quic_connection_stats.h"
10#include "net/quic/quic_utils_chromium.h"
11
12using std::max;
13
14namespace net {
15
16QuicUnackedPacketMap::QuicUnackedPacketMap()
17    : largest_sent_packet_(0),
18      largest_observed_(0),
19      bytes_in_flight_(0),
20      pending_crypto_packet_count_(0) {
21}
22
23QuicUnackedPacketMap::~QuicUnackedPacketMap() {
24  for (UnackedPacketMap::iterator it = unacked_packets_.begin();
25       it != unacked_packets_.end(); ++it) {
26    delete it->second.retransmittable_frames;
27    // Only delete all_transmissions once, for the newest packet.
28    if (it->first == *it->second.all_transmissions->rbegin()) {
29      delete it->second.all_transmissions;
30    }
31  }
32}
33
34// TODO(ianswett): Combine this method with OnPacketSent once packets are always
35// sent in order and the connection tracks RetransmittableFrames for longer.
36void QuicUnackedPacketMap::AddPacket(
37    const SerializedPacket& serialized_packet) {
38  if (!unacked_packets_.empty()) {
39    bool is_old_packet = unacked_packets_.rbegin()->first >=
40        serialized_packet.sequence_number;
41    LOG_IF(DFATAL, is_old_packet) << "Old packet serialized: "
42                                  << serialized_packet.sequence_number
43                                  << " vs: "
44                                  << unacked_packets_.rbegin()->first;
45  }
46
47  unacked_packets_[serialized_packet.sequence_number] =
48      TransmissionInfo(serialized_packet.retransmittable_frames,
49                       serialized_packet.sequence_number,
50                       serialized_packet.sequence_number_length);
51  if (serialized_packet.retransmittable_frames != NULL &&
52      serialized_packet.retransmittable_frames->HasCryptoHandshake()
53          == IS_HANDSHAKE) {
54    ++pending_crypto_packet_count_;
55  }
56}
57
58void QuicUnackedPacketMap::OnRetransmittedPacket(
59    QuicPacketSequenceNumber old_sequence_number,
60    QuicPacketSequenceNumber new_sequence_number,
61    TransmissionType transmission_type) {
62  DCHECK(ContainsKey(unacked_packets_, old_sequence_number));
63  DCHECK(unacked_packets_.empty() ||
64         unacked_packets_.rbegin()->first < new_sequence_number);
65
66  // TODO(ianswett): Discard and lose the packet lazily instead of immediately.
67  TransmissionInfo* transmission_info =
68      FindOrNull(unacked_packets_, old_sequence_number);
69  RetransmittableFrames* frames = transmission_info->retransmittable_frames;
70  LOG_IF(DFATAL, frames == NULL) << "Attempt to retransmit packet with no "
71                                 << "retransmittable frames: "
72                                 << old_sequence_number;
73
74  // We keep the old packet in the unacked packet list until it, or one of
75  // the retransmissions of it are acked.
76  transmission_info->retransmittable_frames = NULL;
77  unacked_packets_[new_sequence_number] =
78      TransmissionInfo(frames,
79                       new_sequence_number,
80                       transmission_info->sequence_number_length,
81                       transmission_type,
82                       transmission_info->all_transmissions);
83}
84
85void QuicUnackedPacketMap::ClearPreviousRetransmissions(size_t num_to_clear) {
86  UnackedPacketMap::iterator it = unacked_packets_.begin();
87  while (it != unacked_packets_.end() && num_to_clear > 0) {
88    QuicPacketSequenceNumber sequence_number = it->first;
89    // If this packet is in flight, or has retransmittable data, then there is
90    // no point in clearing out any further packets, because they would not
91    // affect the high water mark.
92    if (it->second.in_flight || it->second.retransmittable_frames != NULL) {
93      break;
94    }
95
96    it->second.all_transmissions->erase(sequence_number);
97    LOG_IF(DFATAL, it->second.all_transmissions->empty())
98        << "Previous retransmissions must have a newer transmission.";
99    ++it;
100    unacked_packets_.erase(sequence_number);
101    --num_to_clear;
102  }
103}
104
105bool QuicUnackedPacketMap::HasRetransmittableFrames(
106    QuicPacketSequenceNumber sequence_number) const {
107  const TransmissionInfo* transmission_info =
108      FindOrNull(unacked_packets_, sequence_number);
109  if (transmission_info == NULL) {
110    return false;
111  }
112
113  return transmission_info->retransmittable_frames != NULL;
114}
115
116void QuicUnackedPacketMap::NackPacket(QuicPacketSequenceNumber sequence_number,
117                                      size_t min_nacks) {
118  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
119  if (it == unacked_packets_.end()) {
120    LOG(DFATAL) << "NackPacket called for packet that is not unacked: "
121                << sequence_number;
122    return;
123  }
124
125  it->second.nack_count = max(min_nacks, it->second.nack_count);
126}
127
128void QuicUnackedPacketMap::RemoveRetransmittability(
129    QuicPacketSequenceNumber sequence_number) {
130  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
131  if (it == unacked_packets_.end()) {
132    DVLOG(1) << "packet is not in unacked_packets: " << sequence_number;
133    return;
134  }
135  SequenceNumberSet* all_transmissions = it->second.all_transmissions;
136  // TODO(ianswett): Consider optimizing this for lone packets.
137  // TODO(ianswett): Consider adding a check to ensure there are retransmittable
138  // frames associated with this packet.
139  for (SequenceNumberSet::reverse_iterator it = all_transmissions->rbegin();
140       it != all_transmissions->rend(); ++it) {
141    TransmissionInfo* transmission_info = FindOrNull(unacked_packets_, *it);
142    if (transmission_info == NULL) {
143      LOG(DFATAL) << "All transmissions in all_transmissions must be present "
144                  << "in the unacked packet map.";
145      continue;
146    }
147    MaybeRemoveRetransmittableFrames(transmission_info);
148    if (*it <= largest_observed_ && !transmission_info->in_flight) {
149      unacked_packets_.erase(*it);
150    } else {
151      transmission_info->all_transmissions = new SequenceNumberSet();
152      transmission_info->all_transmissions->insert(*it);
153    }
154  }
155
156  delete all_transmissions;
157}
158
159void QuicUnackedPacketMap::MaybeRemoveRetransmittableFrames(
160    TransmissionInfo* transmission_info) {
161  if (transmission_info->retransmittable_frames != NULL) {
162    if (transmission_info->retransmittable_frames->HasCryptoHandshake()
163            == IS_HANDSHAKE) {
164      --pending_crypto_packet_count_;
165    }
166    delete transmission_info->retransmittable_frames;
167    transmission_info->retransmittable_frames = NULL;
168  }
169}
170
171void QuicUnackedPacketMap::IncreaseLargestObserved(
172    QuicPacketSequenceNumber largest_observed) {
173  DCHECK_LT(largest_observed_, largest_observed);
174  largest_observed_ = largest_observed;
175  UnackedPacketMap::iterator it = unacked_packets_.begin();
176  while (it != unacked_packets_.end() && it->first <= largest_observed_) {
177    if (!IsPacketUseless(it)) {
178      ++it;
179      continue;
180    }
181    delete it->second.all_transmissions;
182    QuicPacketSequenceNumber sequence_number = it->first;
183    ++it;
184    unacked_packets_.erase(sequence_number);
185  }
186}
187
188bool QuicUnackedPacketMap::IsPacketUseless(
189    UnackedPacketMap::const_iterator it) const {
190  return it->first <= largest_observed_ &&
191      !it->second.in_flight &&
192      it->second.retransmittable_frames == NULL &&
193      it->second.all_transmissions->size() == 1;
194}
195
196bool QuicUnackedPacketMap::IsUnacked(
197    QuicPacketSequenceNumber sequence_number) const {
198  return ContainsKey(unacked_packets_, sequence_number);
199}
200
201void QuicUnackedPacketMap::RemoveFromInFlight(
202    QuicPacketSequenceNumber sequence_number) {
203  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
204  if (it == unacked_packets_.end()) {
205    LOG(DFATAL) << "RemoveFromFlight called for packet that is not unacked: "
206                << sequence_number;
207    return;
208  }
209  if (it->second.in_flight) {
210    LOG_IF(DFATAL, bytes_in_flight_ < it->second.bytes_sent);
211    bytes_in_flight_ -= it->second.bytes_sent;
212    it->second.in_flight = false;
213  }
214  if (IsPacketUseless(it)) {
215    delete it->second.all_transmissions;
216    unacked_packets_.erase(it);
217  }
218}
219
220bool QuicUnackedPacketMap::HasUnackedPackets() const {
221  return !unacked_packets_.empty();
222}
223
224bool QuicUnackedPacketMap::HasInFlightPackets() const {
225  return bytes_in_flight_ > 0;
226}
227
228const TransmissionInfo& QuicUnackedPacketMap::GetTransmissionInfo(
229    QuicPacketSequenceNumber sequence_number) const {
230  return unacked_packets_.find(sequence_number)->second;
231}
232
233QuicTime QuicUnackedPacketMap::GetLastPacketSentTime() const {
234  UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
235  while (it != unacked_packets_.rend()) {
236    if (it->second.in_flight) {
237      LOG_IF(DFATAL, it->second.sent_time == QuicTime::Zero())
238          << "Sent time can never be zero for a packet in flight.";
239      return it->second.sent_time;
240    }
241    ++it;
242  }
243  LOG(DFATAL) << "GetLastPacketSentTime requires in flight packets.";
244  return QuicTime::Zero();
245}
246
247QuicTime QuicUnackedPacketMap::GetFirstInFlightPacketSentTime() const {
248  UnackedPacketMap::const_iterator it = unacked_packets_.begin();
249  while (it != unacked_packets_.end() && !it->second.in_flight) {
250    ++it;
251  }
252  if (it == unacked_packets_.end()) {
253    LOG(DFATAL) << "GetFirstInFlightPacketSentTime requires in flight packets.";
254    return QuicTime::Zero();
255  }
256  return it->second.sent_time;
257}
258
259size_t QuicUnackedPacketMap::GetNumUnackedPackets() const {
260  return unacked_packets_.size();
261}
262
263bool QuicUnackedPacketMap::HasMultipleInFlightPackets() const {
264  size_t num_in_flight = 0;
265  for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
266       it != unacked_packets_.rend(); ++it) {
267    if (it->second.in_flight) {
268      ++num_in_flight;
269    }
270    if (num_in_flight > 1) {
271      return true;
272    }
273  }
274  return false;
275}
276
277bool QuicUnackedPacketMap::HasPendingCryptoPackets() const {
278  return pending_crypto_packet_count_ > 0;
279}
280
281bool QuicUnackedPacketMap::HasUnackedRetransmittableFrames() const {
282  for (UnackedPacketMap::const_reverse_iterator it =
283           unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) {
284    if (it->second.in_flight && it->second.retransmittable_frames) {
285      return true;
286    }
287  }
288  return false;
289}
290
291QuicPacketSequenceNumber
292QuicUnackedPacketMap::GetLeastUnackedSentPacket() const {
293  if (unacked_packets_.empty()) {
294    // If there are no unacked packets, return 0.
295    return 0;
296  }
297
298  return unacked_packets_.begin()->first;
299}
300
301void QuicUnackedPacketMap::SetSent(QuicPacketSequenceNumber sequence_number,
302                                   QuicTime sent_time,
303                                   QuicByteCount bytes_sent,
304                                   bool set_in_flight) {
305  DCHECK_LT(0u, sequence_number);
306  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
307  if (it == unacked_packets_.end()) {
308    LOG(DFATAL) << "OnPacketSent called for packet that is not unacked: "
309                << sequence_number;
310    return;
311  }
312  DCHECK(!it->second.in_flight);
313
314  largest_sent_packet_ = max(sequence_number, largest_sent_packet_);
315  it->second.sent_time = sent_time;
316  if (set_in_flight) {
317    bytes_in_flight_ += bytes_sent;
318    it->second.bytes_sent = bytes_sent;
319    it->second.in_flight = true;
320  }
321}
322
323}  // namespace net
324