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      least_unacked_(1),
20      bytes_in_flight_(0),
21      pending_crypto_packet_count_(0) {
22}
23
24QuicUnackedPacketMap::~QuicUnackedPacketMap() {
25  QuicPacketSequenceNumber index = least_unacked_;
26  for (UnackedPacketMap::iterator it = unacked_packets_.begin();
27       it != unacked_packets_.end(); ++it, ++index) {
28    delete it->retransmittable_frames;
29    // Only delete all_transmissions once, for the newest packet.
30    if (it->all_transmissions != NULL &&
31        index == *it->all_transmissions->rbegin()) {
32      delete it->all_transmissions;
33    }
34  }
35}
36
37// TODO(ianswett): Combine this method with OnPacketSent once packets are always
38// sent in order and the connection tracks RetransmittableFrames for longer.
39void QuicUnackedPacketMap::AddPacket(
40    const SerializedPacket& serialized_packet) {
41  DCHECK_GE(serialized_packet.sequence_number,
42            least_unacked_ + unacked_packets_.size());
43  while (least_unacked_ + unacked_packets_.size() <
44         serialized_packet.sequence_number) {
45    unacked_packets_.push_back(TransmissionInfo());
46    unacked_packets_.back().is_unackable = true;
47  }
48  unacked_packets_.push_back(
49      TransmissionInfo(serialized_packet.retransmittable_frames,
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::RemoveObsoletePackets() {
59  while (!unacked_packets_.empty()) {
60    if (!IsPacketRemovable(least_unacked_, unacked_packets_.front())) {
61      break;
62    }
63    unacked_packets_.pop_front();
64    ++least_unacked_;
65  }
66}
67
68void QuicUnackedPacketMap::OnRetransmittedPacket(
69    QuicPacketSequenceNumber old_sequence_number,
70    QuicPacketSequenceNumber new_sequence_number,
71    TransmissionType transmission_type) {
72  DCHECK_GE(old_sequence_number, least_unacked_);
73  DCHECK_LT(old_sequence_number, least_unacked_ + unacked_packets_.size());
74  DCHECK_GE(new_sequence_number, least_unacked_ + unacked_packets_.size());
75  while (least_unacked_ + unacked_packets_.size() < new_sequence_number) {
76    unacked_packets_.push_back(TransmissionInfo());
77    unacked_packets_.back().is_unackable = true;
78  }
79
80  // TODO(ianswett): Discard and lose the packet lazily instead of immediately.
81  TransmissionInfo* transmission_info =
82      &unacked_packets_.at(old_sequence_number - least_unacked_);
83  RetransmittableFrames* frames = transmission_info->retransmittable_frames;
84  LOG_IF(DFATAL, frames == NULL) << "Attempt to retransmit packet with no "
85                                 << "retransmittable frames: "
86                                 << old_sequence_number;
87
88  // We keep the old packet in the unacked packet list until it, or one of
89  // the retransmissions of it are acked.
90  transmission_info->retransmittable_frames = NULL;
91  // Only keep one transmission older than largest observed, because only the
92  // most recent is expected to possibly be a spurious retransmission.
93  while (transmission_info->all_transmissions != NULL &&
94         transmission_info->all_transmissions->size() > 1 &&
95         *(++transmission_info->all_transmissions->begin())
96             < largest_observed_) {
97    QuicPacketSequenceNumber old_transmission =
98        *transmission_info->all_transmissions->begin();
99    TransmissionInfo* old_info =
100        &unacked_packets_[old_transmission - least_unacked_];
101    // Don't remove old packets if they're still in flight.
102    if (old_info->in_flight) {
103      break;
104    }
105    old_info->all_transmissions->pop_front();
106    // This will cause the packet be removed in RemoveObsoletePackets.
107    old_info->all_transmissions = NULL;
108  }
109  // Don't link old transmissions to new ones when version or
110  // encryption changes.
111  if (transmission_type == ALL_INITIAL_RETRANSMISSION ||
112      transmission_type == ALL_UNACKED_RETRANSMISSION) {
113    RemoveAckability(transmission_info);
114  } else {
115    if (transmission_info->all_transmissions == NULL) {
116      transmission_info->all_transmissions = new SequenceNumberList();
117      transmission_info->all_transmissions->push_back(old_sequence_number);
118    }
119    transmission_info->all_transmissions->push_back(new_sequence_number);
120  }
121  unacked_packets_.push_back(
122      TransmissionInfo(frames,
123                       transmission_info->sequence_number_length,
124                       transmission_type,
125                       transmission_info->all_transmissions));
126  RemoveObsoletePackets();
127}
128
129void QuicUnackedPacketMap::ClearAllPreviousRetransmissions() {
130  while (!unacked_packets_.empty() && least_unacked_ < largest_observed_) {
131    // If this packet is in flight, or has retransmittable data, then there is
132    // no point in clearing out any further packets, because they would not
133    // affect the high water mark.
134    TransmissionInfo* info = &unacked_packets_.front();
135    if (info->in_flight || info->retransmittable_frames != NULL) {
136      break;
137    }
138
139    if (info->all_transmissions != NULL) {
140      if (info->all_transmissions->size() < 2) {
141        LOG(DFATAL) << "all_transmissions must be NULL or have multiple "
142                    << "elements.  size:" << info->all_transmissions->size();
143        delete info->all_transmissions;
144      } else {
145        info->all_transmissions->pop_front();
146        if (info->all_transmissions->size() == 1) {
147          // Set the newer transmission's 'all_transmissions' entry to NULL.
148          QuicPacketSequenceNumber new_transmission =
149              info->all_transmissions->front();
150          TransmissionInfo* new_info =
151              &unacked_packets_.at(new_transmission - least_unacked_);
152          delete new_info->all_transmissions;
153          new_info->all_transmissions = NULL;
154        }
155      }
156    }
157    unacked_packets_.pop_front();
158    ++least_unacked_;
159  }
160}
161
162bool QuicUnackedPacketMap::HasRetransmittableFrames(
163    QuicPacketSequenceNumber sequence_number) const {
164  DCHECK_GE(sequence_number, least_unacked_);
165  DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size());
166  return unacked_packets_[
167      sequence_number - least_unacked_].retransmittable_frames != NULL;
168}
169
170void QuicUnackedPacketMap::NackPacket(QuicPacketSequenceNumber sequence_number,
171                                      size_t min_nacks) {
172  DCHECK_GE(sequence_number, least_unacked_);
173  DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size());
174  unacked_packets_[sequence_number - least_unacked_].nack_count =
175      max(min_nacks,
176          unacked_packets_[sequence_number - least_unacked_].nack_count);
177}
178
179void QuicUnackedPacketMap::RemoveRetransmittability(
180    QuicPacketSequenceNumber sequence_number) {
181  DCHECK_GE(sequence_number, least_unacked_);
182  DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size());
183  TransmissionInfo* info = &unacked_packets_[sequence_number - least_unacked_];
184  SequenceNumberList* all_transmissions = info->all_transmissions;
185  if (all_transmissions == NULL) {
186    MaybeRemoveRetransmittableFrames(info);
187    return;
188  }
189  // TODO(ianswett): Consider adding a check to ensure there are retransmittable
190  // frames associated with this packet.
191  for (SequenceNumberList::const_iterator it = all_transmissions->begin();
192       it != all_transmissions->end(); ++it) {
193    TransmissionInfo* transmission_info =
194        &unacked_packets_[*it - least_unacked_];
195    MaybeRemoveRetransmittableFrames(transmission_info);
196    transmission_info->all_transmissions = NULL;
197  }
198  delete all_transmissions;
199}
200
201void QuicUnackedPacketMap::RemoveAckability(TransmissionInfo* info) {
202  DCHECK(info->retransmittable_frames == NULL);
203  info->is_unackable = true;
204  SequenceNumberList* all_transmissions = info->all_transmissions;
205  if (all_transmissions == NULL) {
206    return;
207  }
208  for (SequenceNumberList::const_iterator it = all_transmissions->begin();
209       it != all_transmissions->end(); ++it) {
210    TransmissionInfo* transmission_info =
211        &unacked_packets_[*it - least_unacked_];
212    transmission_info->all_transmissions = NULL;
213    transmission_info->is_unackable = true;
214  }
215  delete all_transmissions;
216}
217
218void QuicUnackedPacketMap::MaybeRemoveRetransmittableFrames(
219    TransmissionInfo* transmission_info) {
220  if (transmission_info->retransmittable_frames != NULL) {
221    if (transmission_info->retransmittable_frames->HasCryptoHandshake()
222            == IS_HANDSHAKE) {
223      --pending_crypto_packet_count_;
224    }
225    delete transmission_info->retransmittable_frames;
226    transmission_info->retransmittable_frames = NULL;
227  }
228}
229
230void QuicUnackedPacketMap::IncreaseLargestObserved(
231    QuicPacketSequenceNumber largest_observed) {
232  DCHECK_LE(largest_observed_, largest_observed);
233  largest_observed_ = largest_observed;
234}
235
236bool QuicUnackedPacketMap::IsPacketUseless(
237    QuicPacketSequenceNumber sequence_number,
238    const TransmissionInfo& info) const {
239  return (info.is_unackable || sequence_number <= largest_observed_) &&
240      !info.in_flight &&
241      info.retransmittable_frames == NULL &&
242      info.all_transmissions == NULL;
243}
244
245bool QuicUnackedPacketMap::IsPacketRemovable(
246    QuicPacketSequenceNumber sequence_number,
247    const TransmissionInfo& info) const {
248  return (info.is_unackable ||
249          sequence_number <= largest_observed_ ||
250          unacked_packets_.size() > kMaxTcpCongestionWindow) &&
251      !info.in_flight &&
252      info.retransmittable_frames == NULL &&
253      info.all_transmissions == NULL;
254}
255
256bool QuicUnackedPacketMap::IsUnacked(
257    QuicPacketSequenceNumber sequence_number) const {
258  if (sequence_number < least_unacked_ ||
259      sequence_number >= least_unacked_ + unacked_packets_.size()) {
260    return false;
261  }
262  return !IsPacketUseless(sequence_number,
263                          unacked_packets_[sequence_number - least_unacked_]);
264}
265
266void QuicUnackedPacketMap::RemoveFromInFlight(
267    QuicPacketSequenceNumber sequence_number) {
268  DCHECK_GE(sequence_number, least_unacked_);
269  DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size());
270  TransmissionInfo* info = &unacked_packets_[sequence_number - least_unacked_];
271  if (info->in_flight) {
272    LOG_IF(DFATAL, bytes_in_flight_ < info->bytes_sent);
273    bytes_in_flight_ -= info->bytes_sent;
274    info->in_flight = false;
275  }
276}
277
278bool QuicUnackedPacketMap::HasUnackedPackets() const {
279  return !unacked_packets_.empty();
280}
281
282bool QuicUnackedPacketMap::HasInFlightPackets() const {
283  return bytes_in_flight_ > 0;
284}
285
286const TransmissionInfo& QuicUnackedPacketMap::GetTransmissionInfo(
287    QuicPacketSequenceNumber sequence_number) const {
288  return unacked_packets_[sequence_number - least_unacked_];
289}
290
291QuicTime QuicUnackedPacketMap::GetLastPacketSentTime() const {
292  UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
293  while (it != unacked_packets_.rend()) {
294    if (it->in_flight) {
295      LOG_IF(DFATAL, it->sent_time == QuicTime::Zero())
296          << "Sent time can never be zero for a packet in flight.";
297      return it->sent_time;
298    }
299    ++it;
300  }
301  LOG(DFATAL) << "GetLastPacketSentTime requires in flight packets.";
302  return QuicTime::Zero();
303}
304
305QuicTime QuicUnackedPacketMap::GetFirstInFlightPacketSentTime() const {
306  UnackedPacketMap::const_iterator it = unacked_packets_.begin();
307  while (it != unacked_packets_.end() && !it->in_flight) {
308    ++it;
309  }
310  if (it == unacked_packets_.end()) {
311    LOG(DFATAL) << "GetFirstInFlightPacketSentTime requires in flight packets.";
312    return QuicTime::Zero();
313  }
314  return it->sent_time;
315}
316
317size_t QuicUnackedPacketMap::GetNumUnackedPacketsDebugOnly() const {
318  size_t unacked_packet_count = 0;
319  QuicPacketSequenceNumber sequence_number = least_unacked_;
320  for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
321       it != unacked_packets_.end(); ++it, ++sequence_number) {
322    if (!IsPacketUseless(sequence_number, *it)) {
323      ++unacked_packet_count;
324    }
325  }
326  return unacked_packet_count;
327}
328
329bool QuicUnackedPacketMap::HasMultipleInFlightPackets() const {
330  size_t num_in_flight = 0;
331  for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
332       it != unacked_packets_.rend(); ++it) {
333    if (it->in_flight) {
334      ++num_in_flight;
335    }
336    if (num_in_flight > 1) {
337      return true;
338    }
339  }
340  return false;
341}
342
343bool QuicUnackedPacketMap::HasPendingCryptoPackets() const {
344  return pending_crypto_packet_count_ > 0;
345}
346
347bool QuicUnackedPacketMap::HasUnackedRetransmittableFrames() const {
348  for (UnackedPacketMap::const_reverse_iterator it =
349           unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) {
350    if (it->in_flight && it->retransmittable_frames) {
351      return true;
352    }
353  }
354  return false;
355}
356
357QuicPacketSequenceNumber
358QuicUnackedPacketMap::GetLeastUnacked() const {
359  return least_unacked_;
360}
361
362void QuicUnackedPacketMap::SetSent(QuicPacketSequenceNumber sequence_number,
363                                   QuicTime sent_time,
364                                   QuicByteCount bytes_sent,
365                                   bool set_in_flight) {
366  DCHECK_GE(sequence_number, least_unacked_);
367  DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size());
368  TransmissionInfo* info = &unacked_packets_[sequence_number - least_unacked_];
369  DCHECK(!info->in_flight);
370
371  DCHECK_LT(largest_sent_packet_, sequence_number);
372  largest_sent_packet_ = max(sequence_number, largest_sent_packet_);
373  info->sent_time = sent_time;
374  if (set_in_flight) {
375    bytes_in_flight_ += bytes_sent;
376    info->bytes_sent = bytes_sent;
377    info->in_flight = true;
378  }
379}
380
381void QuicUnackedPacketMap::RestoreInFlight(
382    QuicPacketSequenceNumber sequence_number) {
383  DCHECK_GE(sequence_number, least_unacked_);
384  DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size());
385  TransmissionInfo* info = &unacked_packets_[sequence_number - least_unacked_];
386  DCHECK(!info->in_flight);
387  DCHECK_NE(0u, info->bytes_sent);
388  DCHECK(info->sent_time.IsInitialized());
389
390  bytes_in_flight_ += info->bytes_sent;
391  info->in_flight = true;
392}
393
394}  // namespace net
395