quic_unacked_packet_map.cc revision 03b57e008b61dfcb1fbad3aea950ae0e001748b0 
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  // Only keep one transmission older than largest observed, because only the
78  // most recent is expected to possibly be a spurious retransmission.
79  if (transmission_info->all_transmissions->size() > 1 &&
80      *(++transmission_info->all_transmissions->begin()) < largest_observed_) {
81    QuicPacketSequenceNumber old_transmission =
82        *transmission_info->all_transmissions->begin();
83    TransmissionInfo* old_transmission_info =
84        FindOrNull(unacked_packets_, old_transmission);
85    // Don't remove old packets if they're still in flight.
86    if (old_transmission_info == NULL || !old_transmission_info->in_flight) {
87      transmission_info->all_transmissions->erase(old_transmission);
88      unacked_packets_.erase(old_transmission);
89    }
90  }
91  unacked_packets_[new_sequence_number] =
92      TransmissionInfo(frames,
93                       new_sequence_number,
94                       transmission_info->sequence_number_length,
95                       transmission_type,
96                       transmission_info->all_transmissions);
97}
98
99void QuicUnackedPacketMap::ClearPreviousRetransmissions(size_t num_to_clear) {
100  UnackedPacketMap::iterator it = unacked_packets_.begin();
101  while (it != unacked_packets_.end() && num_to_clear > 0) {
102    QuicPacketSequenceNumber sequence_number = it->first;
103    // If this packet is in flight, or has retransmittable data, then there is
104    // no point in clearing out any further packets, because they would not
105    // affect the high water mark.
106    if (it->second.in_flight || it->second.retransmittable_frames != NULL) {
107      break;
108    }
109
110    it->second.all_transmissions->erase(sequence_number);
111    LOG_IF(DFATAL, it->second.all_transmissions->empty())
112        << "Previous retransmissions must have a newer transmission.";
113    ++it;
114    unacked_packets_.erase(sequence_number);
115    --num_to_clear;
116  }
117}
118
119bool QuicUnackedPacketMap::HasRetransmittableFrames(
120    QuicPacketSequenceNumber sequence_number) const {
121  const TransmissionInfo* transmission_info =
122      FindOrNull(unacked_packets_, sequence_number);
123  if (transmission_info == NULL) {
124    return false;
125  }
126
127  return transmission_info->retransmittable_frames != NULL;
128}
129
130void QuicUnackedPacketMap::NackPacket(QuicPacketSequenceNumber sequence_number,
131                                      size_t min_nacks) {
132  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
133  if (it == unacked_packets_.end()) {
134    LOG(DFATAL) << "NackPacket called for packet that is not unacked: "
135                << sequence_number;
136    return;
137  }
138
139  it->second.nack_count = max(min_nacks, it->second.nack_count);
140}
141
142void QuicUnackedPacketMap::RemoveRetransmittability(
143    QuicPacketSequenceNumber sequence_number) {
144  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
145  if (it == unacked_packets_.end()) {
146    DVLOG(1) << "packet is not in unacked_packets: " << sequence_number;
147    return;
148  }
149  SequenceNumberSet* all_transmissions = it->second.all_transmissions;
150  // TODO(ianswett): Consider optimizing this for lone packets.
151  // TODO(ianswett): Consider adding a check to ensure there are retransmittable
152  // frames associated with this packet.
153  for (SequenceNumberSet::reverse_iterator it = all_transmissions->rbegin();
154       it != all_transmissions->rend(); ++it) {
155    TransmissionInfo* transmission_info = FindOrNull(unacked_packets_, *it);
156    if (transmission_info == NULL) {
157      LOG(DFATAL) << "All transmissions in all_transmissions must be present "
158                  << "in the unacked packet map.";
159      continue;
160    }
161    MaybeRemoveRetransmittableFrames(transmission_info);
162    if (*it <= largest_observed_ && !transmission_info->in_flight) {
163      unacked_packets_.erase(*it);
164    } else {
165      transmission_info->all_transmissions = new SequenceNumberSet();
166      transmission_info->all_transmissions->insert(*it);
167    }
168  }
169
170  delete all_transmissions;
171}
172
173void QuicUnackedPacketMap::MaybeRemoveRetransmittableFrames(
174    TransmissionInfo* transmission_info) {
175  if (transmission_info->retransmittable_frames != NULL) {
176    if (transmission_info->retransmittable_frames->HasCryptoHandshake()
177            == IS_HANDSHAKE) {
178      --pending_crypto_packet_count_;
179    }
180    delete transmission_info->retransmittable_frames;
181    transmission_info->retransmittable_frames = NULL;
182  }
183}
184
185void QuicUnackedPacketMap::IncreaseLargestObserved(
186    QuicPacketSequenceNumber largest_observed) {
187  DCHECK_LE(largest_observed_, largest_observed);
188  largest_observed_ = largest_observed;
189  UnackedPacketMap::iterator it = unacked_packets_.begin();
190  while (it != unacked_packets_.end() && it->first <= largest_observed_) {
191    if (!IsPacketUseless(it)) {
192      ++it;
193      continue;
194    }
195    delete it->second.all_transmissions;
196    QuicPacketSequenceNumber sequence_number = it->first;
197    ++it;
198    unacked_packets_.erase(sequence_number);
199  }
200}
201
202bool QuicUnackedPacketMap::IsPacketUseless(
203    UnackedPacketMap::const_iterator it) const {
204  return it->first <= largest_observed_ &&
205      !it->second.in_flight &&
206      it->second.retransmittable_frames == NULL &&
207      it->second.all_transmissions->size() == 1;
208}
209
210bool QuicUnackedPacketMap::IsUnacked(
211    QuicPacketSequenceNumber sequence_number) const {
212  return ContainsKey(unacked_packets_, sequence_number);
213}
214
215void QuicUnackedPacketMap::RemoveFromInFlight(
216    QuicPacketSequenceNumber sequence_number) {
217  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
218  if (it == unacked_packets_.end()) {
219    LOG(DFATAL) << "RemoveFromFlight called for packet that is not unacked: "
220                << sequence_number;
221    return;
222  }
223  if (it->second.in_flight) {
224    LOG_IF(DFATAL, bytes_in_flight_ < it->second.bytes_sent);
225    bytes_in_flight_ -= it->second.bytes_sent;
226    it->second.in_flight = false;
227  }
228  if (IsPacketUseless(it)) {
229    delete it->second.all_transmissions;
230    unacked_packets_.erase(it);
231  }
232}
233
234bool QuicUnackedPacketMap::HasUnackedPackets() const {
235  return !unacked_packets_.empty();
236}
237
238bool QuicUnackedPacketMap::HasInFlightPackets() const {
239  return bytes_in_flight_ > 0;
240}
241
242const TransmissionInfo& QuicUnackedPacketMap::GetTransmissionInfo(
243    QuicPacketSequenceNumber sequence_number) const {
244  return unacked_packets_.find(sequence_number)->second;
245}
246
247QuicTime QuicUnackedPacketMap::GetLastPacketSentTime() const {
248  UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
249  while (it != unacked_packets_.rend()) {
250    if (it->second.in_flight) {
251      LOG_IF(DFATAL, it->second.sent_time == QuicTime::Zero())
252          << "Sent time can never be zero for a packet in flight.";
253      return it->second.sent_time;
254    }
255    ++it;
256  }
257  LOG(DFATAL) << "GetLastPacketSentTime requires in flight packets.";
258  return QuicTime::Zero();
259}
260
261QuicTime QuicUnackedPacketMap::GetFirstInFlightPacketSentTime() const {
262  UnackedPacketMap::const_iterator it = unacked_packets_.begin();
263  while (it != unacked_packets_.end() && !it->second.in_flight) {
264    ++it;
265  }
266  if (it == unacked_packets_.end()) {
267    LOG(DFATAL) << "GetFirstInFlightPacketSentTime requires in flight packets.";
268    return QuicTime::Zero();
269  }
270  return it->second.sent_time;
271}
272
273size_t QuicUnackedPacketMap::GetNumUnackedPackets() const {
274  return unacked_packets_.size();
275}
276
277bool QuicUnackedPacketMap::HasMultipleInFlightPackets() const {
278  size_t num_in_flight = 0;
279  for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
280       it != unacked_packets_.rend(); ++it) {
281    if (it->second.in_flight) {
282      ++num_in_flight;
283    }
284    if (num_in_flight > 1) {
285      return true;
286    }
287  }
288  return false;
289}
290
291bool QuicUnackedPacketMap::HasPendingCryptoPackets() const {
292  return pending_crypto_packet_count_ > 0;
293}
294
295bool QuicUnackedPacketMap::HasUnackedRetransmittableFrames() const {
296  for (UnackedPacketMap::const_reverse_iterator it =
297           unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) {
298    if (it->second.in_flight && it->second.retransmittable_frames) {
299      return true;
300    }
301  }
302  return false;
303}
304
305QuicPacketSequenceNumber
306QuicUnackedPacketMap::GetLeastUnackedSentPacket() const {
307  if (unacked_packets_.empty()) {
308    // If there are no unacked packets, return 0.
309    return 0;
310  }
311
312  return unacked_packets_.begin()->first;
313}
314
315void QuicUnackedPacketMap::SetSent(QuicPacketSequenceNumber sequence_number,
316                                   QuicTime sent_time,
317                                   QuicByteCount bytes_sent,
318                                   bool set_in_flight) {
319  DCHECK_LT(0u, sequence_number);
320  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
321  if (it == unacked_packets_.end()) {
322    LOG(DFATAL) << "OnPacketSent called for packet that is not unacked: "
323                << sequence_number;
324    return;
325  }
326  DCHECK(!it->second.in_flight);
327
328  largest_sent_packet_ = max(sequence_number, largest_sent_packet_);
329  it->second.sent_time = sent_time;
330  if (set_in_flight) {
331    bytes_in_flight_ += bytes_sent;
332    it->second.bytes_sent = bytes_sent;
333    it->second.in_flight = true;
334  }
335}
336
337void QuicUnackedPacketMap::RestoreInFlight(
338    QuicPacketSequenceNumber sequence_number) {
339  DCHECK_LT(0u, sequence_number);
340  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
341  if (it == unacked_packets_.end()) {
342    LOG(DFATAL) << "OnPacketSent called for packet that is not unacked: "
343                << sequence_number;
344    return;
345  }
346  DCHECK(!it->second.in_flight);
347  DCHECK_NE(0u, it->second.bytes_sent);
348  DCHECK(it->second.sent_time.IsInitialized());
349
350  bytes_in_flight_ += it->second.bytes_sent;
351  it->second.in_flight = true;
352}
353
354}  // namespace net
355