quic_unacked_packet_map.cc revision e5d81f57cb97b3b6b7fccc9c5610d21eb81db09d 
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::TransmissionInfo::TransmissionInfo()
17    : retransmittable_frames(NULL),
18      sequence_number_length(PACKET_1BYTE_SEQUENCE_NUMBER),
19      sent_time(QuicTime::Zero()),
20      bytes_sent(0),
21      nack_count(0),
22      all_transmissions(NULL),
23      pending(false) { }
24
25QuicUnackedPacketMap::TransmissionInfo::TransmissionInfo(
26    RetransmittableFrames* retransmittable_frames,
27    QuicPacketSequenceNumber sequence_number,
28    QuicSequenceNumberLength sequence_number_length)
29    : retransmittable_frames(retransmittable_frames),
30      sequence_number_length(sequence_number_length),
31      sent_time(QuicTime::Zero()),
32      bytes_sent(0),
33      nack_count(0),
34      all_transmissions(new SequenceNumberSet),
35      pending(false) {
36  all_transmissions->insert(sequence_number);
37}
38
39QuicUnackedPacketMap::TransmissionInfo::TransmissionInfo(
40    RetransmittableFrames* retransmittable_frames,
41    QuicPacketSequenceNumber sequence_number,
42    QuicSequenceNumberLength sequence_number_length,
43    SequenceNumberSet* all_transmissions)
44    : retransmittable_frames(retransmittable_frames),
45      sequence_number_length(sequence_number_length),
46      sent_time(QuicTime::Zero()),
47      bytes_sent(0),
48      nack_count(0),
49      all_transmissions(all_transmissions),
50      pending(false) {
51  all_transmissions->insert(sequence_number);
52}
53
54QuicUnackedPacketMap::QuicUnackedPacketMap()
55    : largest_sent_packet_(0),
56      bytes_in_flight_(0),
57      pending_crypto_packet_count_(0) {
58}
59
60QuicUnackedPacketMap::~QuicUnackedPacketMap() {
61  for (UnackedPacketMap::iterator it = unacked_packets_.begin();
62       it != unacked_packets_.end(); ++it) {
63    delete it->second.retransmittable_frames;
64    // Only delete all_transmissions once, for the newest packet.
65    if (it->first == *it->second.all_transmissions->rbegin()) {
66      delete it->second.all_transmissions;
67    }
68  }
69}
70
71// TODO(ianswett): Combine this method with OnPacketSent once packets are always
72// sent in order and the connection tracks RetransmittableFrames for longer.
73void QuicUnackedPacketMap::AddPacket(
74    const SerializedPacket& serialized_packet) {
75  if (!unacked_packets_.empty()) {
76    bool is_old_packet = unacked_packets_.rbegin()->first >=
77        serialized_packet.sequence_number;
78    LOG_IF(DFATAL, is_old_packet) << "Old packet serialized: "
79                                  << serialized_packet.sequence_number
80                                  << " vs: "
81                                  << unacked_packets_.rbegin()->first;
82  }
83
84  unacked_packets_[serialized_packet.sequence_number] =
85      TransmissionInfo(serialized_packet.retransmittable_frames,
86                       serialized_packet.sequence_number,
87                       serialized_packet.sequence_number_length);
88  if (serialized_packet.retransmittable_frames != NULL &&
89      serialized_packet.retransmittable_frames->HasCryptoHandshake()
90          == IS_HANDSHAKE) {
91    ++pending_crypto_packet_count_;
92  }
93}
94
95void QuicUnackedPacketMap::OnRetransmittedPacket(
96    QuicPacketSequenceNumber old_sequence_number,
97    QuicPacketSequenceNumber new_sequence_number) {
98  DCHECK(ContainsKey(unacked_packets_, old_sequence_number));
99  DCHECK(unacked_packets_.empty() ||
100         unacked_packets_.rbegin()->first < new_sequence_number);
101
102  // TODO(ianswett): Discard and lose the packet lazily instead of immediately.
103  TransmissionInfo* transmission_info =
104      FindOrNull(unacked_packets_, old_sequence_number);
105  RetransmittableFrames* frames = transmission_info->retransmittable_frames;
106  LOG_IF(DFATAL, frames == NULL) << "Attempt to retransmit packet with no "
107                                 << "retransmittable frames: "
108                                 << old_sequence_number;
109
110  // We keep the old packet in the unacked packet list until it, or one of
111  // the retransmissions of it are acked.
112  transmission_info->retransmittable_frames = NULL;
113  unacked_packets_[new_sequence_number] =
114      TransmissionInfo(frames,
115                       new_sequence_number,
116                       transmission_info->sequence_number_length,
117                       transmission_info->all_transmissions);
118}
119
120void QuicUnackedPacketMap::ClearPreviousRetransmissions(size_t num_to_clear) {
121  UnackedPacketMap::iterator it = unacked_packets_.begin();
122  while (it != unacked_packets_.end() && num_to_clear > 0) {
123    QuicPacketSequenceNumber sequence_number = it->first;
124    // If this is a pending packet, or has retransmittable data, then there is
125    // no point in clearing out any further packets, because they would not
126    // affect the high water mark.
127    if (it->second.pending || it->second.retransmittable_frames != NULL) {
128      break;
129    }
130
131    ++it;
132    RemovePacket(sequence_number);
133    --num_to_clear;
134  }
135}
136
137bool QuicUnackedPacketMap::HasRetransmittableFrames(
138    QuicPacketSequenceNumber sequence_number) const {
139  const TransmissionInfo* transmission_info =
140      FindOrNull(unacked_packets_, sequence_number);
141  if (transmission_info == NULL) {
142    return false;
143  }
144
145  return transmission_info->retransmittable_frames != NULL;
146}
147
148void QuicUnackedPacketMap::NackPacket(QuicPacketSequenceNumber sequence_number,
149                                      size_t min_nacks) {
150  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
151  if (it == unacked_packets_.end()) {
152    LOG(DFATAL) << "NackPacket called for packet that is not unacked: "
153                << sequence_number;
154    return;
155  }
156
157  it->second.nack_count = max(min_nacks, it->second.nack_count);
158}
159
160void QuicUnackedPacketMap::RemovePacket(
161    QuicPacketSequenceNumber sequence_number) {
162  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
163  if (it == unacked_packets_.end()) {
164    LOG(DFATAL) << "packet is not unacked: " << sequence_number;
165    return;
166  }
167  const TransmissionInfo& transmission_info = it->second;
168  transmission_info.all_transmissions->erase(sequence_number);
169  if (transmission_info.all_transmissions->empty()) {
170    delete transmission_info.all_transmissions;
171  }
172  if (transmission_info.retransmittable_frames != NULL) {
173    if (transmission_info.retransmittable_frames->HasCryptoHandshake()
174            == IS_HANDSHAKE) {
175      --pending_crypto_packet_count_;
176    }
177    delete transmission_info.retransmittable_frames;
178  }
179  unacked_packets_.erase(it);
180}
181
182void QuicUnackedPacketMap::NeuterPacket(
183    QuicPacketSequenceNumber sequence_number) {
184  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
185  if (it == unacked_packets_.end()) {
186    LOG(DFATAL) << "packet is not unacked: " << sequence_number;
187    return;
188  }
189  TransmissionInfo* transmission_info = &it->second;
190  if (transmission_info->all_transmissions->size() > 1) {
191    transmission_info->all_transmissions->erase(sequence_number);
192    transmission_info->all_transmissions = new SequenceNumberSet();
193    transmission_info->all_transmissions->insert(sequence_number);
194  }
195  if (transmission_info->retransmittable_frames != NULL) {
196    delete transmission_info->retransmittable_frames;
197    transmission_info->retransmittable_frames = NULL;
198  }
199}
200
201// static
202bool QuicUnackedPacketMap::IsSentAndNotPending(
203    const TransmissionInfo& transmission_info) {
204  return !transmission_info.pending &&
205      transmission_info.sent_time != QuicTime::Zero() &&
206      transmission_info.bytes_sent == 0;
207}
208
209bool QuicUnackedPacketMap::IsUnacked(
210    QuicPacketSequenceNumber sequence_number) const {
211  return ContainsKey(unacked_packets_, sequence_number);
212}
213
214bool QuicUnackedPacketMap::IsPending(
215    QuicPacketSequenceNumber sequence_number) const {
216  const TransmissionInfo* transmission_info =
217      FindOrNull(unacked_packets_, sequence_number);
218  return transmission_info != NULL && transmission_info->pending;
219}
220
221void QuicUnackedPacketMap::SetNotPending(
222    QuicPacketSequenceNumber sequence_number) {
223  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
224  if (it == unacked_packets_.end()) {
225    LOG(DFATAL) << "SetNotPending called for packet that is not unacked: "
226                << sequence_number;
227    return;
228  }
229  if (it->second.pending) {
230    LOG_IF(DFATAL, bytes_in_flight_ < it->second.bytes_sent);
231    bytes_in_flight_ -= it->second.bytes_sent;
232    it->second.pending = false;
233  }
234}
235
236bool QuicUnackedPacketMap::HasUnackedPackets() const {
237  return !unacked_packets_.empty();
238}
239
240bool QuicUnackedPacketMap::HasPendingPackets() const {
241  for (UnackedPacketMap::const_reverse_iterator it =
242           unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) {
243    if (it->second.pending) {
244      return true;
245    }
246  }
247  return false;
248}
249
250const QuicUnackedPacketMap::TransmissionInfo&
251    QuicUnackedPacketMap::GetTransmissionInfo(
252        QuicPacketSequenceNumber sequence_number) const {
253  return unacked_packets_.find(sequence_number)->second;
254}
255
256QuicTime QuicUnackedPacketMap::GetLastPacketSentTime() const {
257  UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
258  while (it != unacked_packets_.rend() &&
259         (!it->second.pending ||
260          it->second.retransmittable_frames == NULL)) {
261    ++it;
262  }
263  if (it == unacked_packets_.rend()) {
264    LOG(DFATAL) << "Unable to find sent time.";
265    return QuicTime::Zero();
266  }
267  return it->second.sent_time;
268}
269
270QuicTime QuicUnackedPacketMap::GetFirstPendingPacketSentTime() const {
271  UnackedPacketMap::const_iterator it = unacked_packets_.begin();
272  while (it != unacked_packets_.end() && !it->second.pending) {
273    ++it;
274  }
275  if (it == unacked_packets_.end()) {
276    LOG(DFATAL) << "No pending packets";
277    return QuicTime::Zero();
278  }
279  return it->second.sent_time;
280}
281
282size_t QuicUnackedPacketMap::GetNumUnackedPackets() const {
283  return unacked_packets_.size();
284}
285
286bool QuicUnackedPacketMap::HasMultiplePendingPackets() const {
287  size_t num_pending = 0;
288  for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
289       it != unacked_packets_.rend(); ++it) {
290    if (it->second.pending) {
291      ++num_pending;
292    }
293    if (num_pending > 1) {
294      return true;
295    }
296  }
297  return false;
298}
299
300bool QuicUnackedPacketMap::HasPendingCryptoPackets() const {
301  return pending_crypto_packet_count_ > 0;
302}
303
304bool QuicUnackedPacketMap::HasUnackedRetransmittableFrames() const {
305  for (UnackedPacketMap::const_reverse_iterator it =
306           unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) {
307    if (it->second.pending && it->second.retransmittable_frames) {
308      return true;
309    }
310  }
311  return false;
312}
313
314size_t QuicUnackedPacketMap::GetNumRetransmittablePackets() const {
315  size_t num_unacked_packets = 0;
316  for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
317       it != unacked_packets_.end(); ++it) {
318    if (it->second.retransmittable_frames != NULL) {
319      ++num_unacked_packets;
320    }
321  }
322  return num_unacked_packets;
323}
324
325QuicPacketSequenceNumber
326QuicUnackedPacketMap::GetLeastUnackedSentPacket() const {
327  if (unacked_packets_.empty()) {
328    // If there are no unacked packets, return 0.
329    return 0;
330  }
331
332  return unacked_packets_.begin()->first;
333}
334
335SequenceNumberSet QuicUnackedPacketMap::GetUnackedPackets() const {
336  SequenceNumberSet unacked_packets;
337  for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
338       it != unacked_packets_.end(); ++it) {
339    unacked_packets.insert(it->first);
340  }
341  return unacked_packets;
342}
343
344void QuicUnackedPacketMap::SetSent(QuicPacketSequenceNumber sequence_number,
345                                   QuicTime sent_time,
346                                   QuicByteCount bytes_sent,
347                                   bool set_pending) {
348  DCHECK_LT(0u, sequence_number);
349  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
350  if (it == unacked_packets_.end()) {
351    LOG(DFATAL) << "OnPacketSent called for packet that is not unacked: "
352                << sequence_number;
353    return;
354  }
355  DCHECK(!it->second.pending);
356
357  largest_sent_packet_ = max(sequence_number, largest_sent_packet_);
358  it->second.sent_time = sent_time;
359  if (set_pending) {
360    bytes_in_flight_ += bytes_sent;
361    it->second.bytes_sent = bytes_sent;
362    it->second.pending = true;
363  }
364}
365
366}  // namespace net
367