1// Copyright 2013 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_received_packet_manager.h"
6
7#include <limits>
8#include <utility>
9
10#include "base/logging.h"
11#include "base/stl_util.h"
12#include "net/base/linked_hash_map.h"
13#include "net/quic/crypto/crypto_protocol.h"
14#include "net/quic/quic_connection_stats.h"
15
16using std::make_pair;
17using std::max;
18using std::min;
19using std::numeric_limits;
20
21namespace net {
22
23namespace {
24
25// The maximum number of packets to ack immediately after a missing packet for
26// fast retransmission to kick in at the sender.  This limit is created to
27// reduce the number of acks sent that have no benefit for fast retransmission.
28// Set to the number of nacks needed for fast retransmit plus one for protection
29// against an ack loss
30const size_t kMaxPacketsAfterNewMissing = 4;
31
32}
33
34QuicReceivedPacketManager::EntropyTracker::EntropyTracker()
35    :  packets_entropy_hash_(0),
36       first_gap_(1),
37       largest_observed_(0) {
38}
39
40QuicReceivedPacketManager::EntropyTracker::~EntropyTracker() {}
41
42QuicPacketEntropyHash QuicReceivedPacketManager::EntropyTracker::EntropyHash(
43    QuicPacketSequenceNumber sequence_number) const {
44  DCHECK_LE(sequence_number, largest_observed_);
45  if (sequence_number == largest_observed_) {
46    return packets_entropy_hash_;
47  }
48
49  DCHECK_GE(sequence_number, first_gap_);
50  DCHECK_EQ(first_gap_ + packets_entropy_.size() - 1, largest_observed_);
51  QuicPacketEntropyHash hash = packets_entropy_hash_;
52  ReceivedEntropyHashes::const_reverse_iterator it = packets_entropy_.rbegin();
53  for (QuicPacketSequenceNumber i = 0;
54           i < (largest_observed_ - sequence_number); ++i, ++it) {
55    hash ^= it->first;
56  }
57  return hash;
58}
59
60void QuicReceivedPacketManager::EntropyTracker::RecordPacketEntropyHash(
61    QuicPacketSequenceNumber sequence_number,
62    QuicPacketEntropyHash entropy_hash) {
63  if (sequence_number < first_gap_) {
64    DVLOG(1) << "Ignoring received packet entropy for sequence_number:"
65             << sequence_number << " less than largest_peer_sequence_number:"
66             << first_gap_;
67    return;
68  }
69  // RecordPacketEntropyHash is only intended to be called once per packet.
70  DCHECK(sequence_number > largest_observed_ ||
71         !packets_entropy_[sequence_number - first_gap_].second);
72
73  packets_entropy_hash_ ^= entropy_hash;
74
75  // Optimize the typical case of no gaps.
76  if (sequence_number == largest_observed_ + 1 && packets_entropy_.empty()) {
77    ++first_gap_;
78    largest_observed_ = sequence_number;
79    return;
80  }
81  if (sequence_number > largest_observed_) {
82    for (QuicPacketSequenceNumber i = 0;
83         i < (sequence_number - largest_observed_ - 1); ++i) {
84      packets_entropy_.push_back(make_pair(0, false));
85    }
86    packets_entropy_.push_back(make_pair(entropy_hash, true));
87    largest_observed_ = sequence_number;
88  } else {
89    packets_entropy_[sequence_number - first_gap_] =
90        make_pair(entropy_hash, true);
91    AdvanceFirstGapAndGarbageCollectEntropyMap();
92  }
93
94  DVLOG(2) << "setting cumulative received entropy hash to: "
95           << static_cast<int>(packets_entropy_hash_)
96           << " updated with sequence number " << sequence_number
97           << " entropy hash: " << static_cast<int>(entropy_hash);
98}
99
100void QuicReceivedPacketManager::EntropyTracker::SetCumulativeEntropyUpTo(
101    QuicPacketSequenceNumber sequence_number,
102    QuicPacketEntropyHash entropy_hash) {
103  DCHECK_LE(sequence_number, largest_observed_);
104  if (sequence_number < first_gap_) {
105    DVLOG(1) << "Ignoring set entropy at:" << sequence_number
106             << " less than first_gap_:" << first_gap_;
107    return;
108  }
109  while (first_gap_ < sequence_number) {
110    ++first_gap_;
111    if (!packets_entropy_.empty()) {
112      packets_entropy_.pop_front();
113    }
114  }
115  // Compute the current entropy by XORing in all entropies received including
116  // and since sequence_number.
117  packets_entropy_hash_ = entropy_hash;
118  for (ReceivedEntropyHashes::const_iterator it = packets_entropy_.begin();
119           it != packets_entropy_.end(); ++it) {
120    packets_entropy_hash_ ^= it->first;
121  }
122
123  // Garbage collect entries from the beginning of the map.
124  AdvanceFirstGapAndGarbageCollectEntropyMap();
125}
126
127void QuicReceivedPacketManager::EntropyTracker::
128AdvanceFirstGapAndGarbageCollectEntropyMap() {
129  while (!packets_entropy_.empty() && packets_entropy_.front().second) {
130    ++first_gap_;
131    packets_entropy_.pop_front();
132  }
133}
134
135QuicReceivedPacketManager::QuicReceivedPacketManager(
136    QuicConnectionStats* stats)
137    : peer_least_packet_awaiting_ack_(0),
138      time_largest_observed_(QuicTime::Zero()),
139      receive_algorithm_(ReceiveAlgorithmInterface::Create(kTCP)),
140      stats_(stats) {
141  ack_frame_.largest_observed = 0;
142  ack_frame_.entropy_hash = 0;
143}
144
145QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
146
147void QuicReceivedPacketManager::RecordPacketReceived(
148    QuicByteCount bytes,
149    const QuicPacketHeader& header,
150    QuicTime receipt_time) {
151  QuicPacketSequenceNumber sequence_number = header.packet_sequence_number;
152  DCHECK(IsAwaitingPacket(sequence_number));
153
154  InsertMissingPacketsBetween(
155      &ack_frame_,
156      max(ack_frame_.largest_observed + 1, peer_least_packet_awaiting_ack_),
157      sequence_number);
158
159  if (ack_frame_.largest_observed > sequence_number) {
160    // We've gotten one of the out of order packets - remove it from our
161    // "missing packets" list.
162    DVLOG(1) << "Removing " << sequence_number << " from missing list";
163    ack_frame_.missing_packets.erase(sequence_number);
164
165    // Record how out of order stats.
166    ++stats_->packets_reordered;
167    uint32 sequence_gap = ack_frame_.largest_observed - sequence_number;
168    stats_->max_sequence_reordering =
169        max(stats_->max_sequence_reordering, sequence_gap);
170    uint32 reordering_time_us =
171        receipt_time.Subtract(time_largest_observed_).ToMicroseconds();
172    stats_->max_time_reordering_us = max(stats_->max_time_reordering_us,
173                                         reordering_time_us);
174  }
175  if (sequence_number > ack_frame_.largest_observed) {
176    ack_frame_.largest_observed = sequence_number;
177    time_largest_observed_ = receipt_time;
178  }
179  entropy_tracker_.RecordPacketEntropyHash(sequence_number,
180                                           header.entropy_hash);
181
182  receive_algorithm_->RecordIncomingPacket(
183      bytes, sequence_number, receipt_time);
184
185  received_packet_times_.push_back(
186      std::make_pair(sequence_number, receipt_time));
187
188  ack_frame_.revived_packets.erase(sequence_number);
189}
190
191void QuicReceivedPacketManager::RecordPacketRevived(
192    QuicPacketSequenceNumber sequence_number) {
193  LOG_IF(DFATAL, !IsAwaitingPacket(sequence_number));
194  ack_frame_.revived_packets.insert(sequence_number);
195}
196
197bool QuicReceivedPacketManager::IsMissing(
198    QuicPacketSequenceNumber sequence_number) {
199  return ContainsKey(ack_frame_.missing_packets, sequence_number);
200}
201
202bool QuicReceivedPacketManager::IsAwaitingPacket(
203    QuicPacketSequenceNumber sequence_number) {
204  return ::net::IsAwaitingPacket(ack_frame_, sequence_number);
205}
206
207namespace {
208struct isTooLarge {
209  explicit isTooLarge(QuicPacketSequenceNumber n) : largest_observed_(n) {}
210  QuicPacketSequenceNumber largest_observed_;
211
212  // Return true if the packet in p is too different from largest_observed_
213  // to express.
214  bool operator() (
215      const std::pair<QuicPacketSequenceNumber, QuicTime>& p) const {
216    return largest_observed_ - p.first >= numeric_limits<uint8>::max();
217  }
218};
219}  // namespace
220
221void QuicReceivedPacketManager::UpdateReceivedPacketInfo(
222    QuicAckFrame* ack_frame, QuicTime approximate_now) {
223  *ack_frame = ack_frame_;
224  ack_frame->entropy_hash = EntropyHash(ack_frame_.largest_observed);
225
226  if (time_largest_observed_ == QuicTime::Zero()) {
227    // We have received no packets.
228    ack_frame->delta_time_largest_observed = QuicTime::Delta::Infinite();
229    return;
230  }
231
232  if (approximate_now < time_largest_observed_) {
233    // Approximate now may well be "in the past".
234    ack_frame->delta_time_largest_observed = QuicTime::Delta::Zero();
235    return;
236  }
237
238  ack_frame->delta_time_largest_observed =
239      approximate_now.Subtract(time_largest_observed_);
240
241  // Remove all packets that are too far from largest_observed to express.
242  received_packet_times_.remove_if(isTooLarge(ack_frame_.largest_observed));
243
244  ack_frame->received_packet_times = received_packet_times_;
245  received_packet_times_.clear();
246}
247
248bool QuicReceivedPacketManager::GenerateCongestionFeedback(
249    QuicCongestionFeedbackFrame* feedback) {
250  return receive_algorithm_->GenerateCongestionFeedback(feedback);
251}
252
253QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash(
254    QuicPacketSequenceNumber sequence_number) const {
255  return entropy_tracker_.EntropyHash(sequence_number);
256}
257
258bool QuicReceivedPacketManager::DontWaitForPacketsBefore(
259    QuicPacketSequenceNumber least_unacked) {
260  ack_frame_.revived_packets.erase(
261      ack_frame_.revived_packets.begin(),
262      ack_frame_.revived_packets.lower_bound(least_unacked));
263  size_t missing_packets_count = ack_frame_.missing_packets.size();
264  ack_frame_.missing_packets.erase(
265      ack_frame_.missing_packets.begin(),
266      ack_frame_.missing_packets.lower_bound(least_unacked));
267  return missing_packets_count != ack_frame_.missing_packets.size();
268}
269
270void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer(
271    const QuicStopWaitingFrame& stop_waiting) {
272  // ValidateAck() should fail if peer_least_packet_awaiting_ack_ shrinks.
273  DCHECK_LE(peer_least_packet_awaiting_ack_, stop_waiting.least_unacked);
274  if (stop_waiting.least_unacked > peer_least_packet_awaiting_ack_) {
275    bool missed_packets = DontWaitForPacketsBefore(stop_waiting.least_unacked);
276    if (missed_packets) {
277      DVLOG(1) << "Updating entropy hashed since we missed packets";
278      // There were some missing packets that we won't ever get now. Recalculate
279      // the received entropy hash.
280      entropy_tracker_.SetCumulativeEntropyUpTo(stop_waiting.least_unacked,
281                                                stop_waiting.entropy_hash);
282    }
283    peer_least_packet_awaiting_ack_ = stop_waiting.least_unacked;
284  }
285  DCHECK(ack_frame_.missing_packets.empty() ||
286         *ack_frame_.missing_packets.begin() >=
287             peer_least_packet_awaiting_ack_);
288}
289
290bool QuicReceivedPacketManager::HasNewMissingPackets() {
291  return !ack_frame_.missing_packets.empty() &&
292      (ack_frame_.largest_observed -
293       *ack_frame_.missing_packets.rbegin()) <= kMaxPacketsAfterNewMissing;
294}
295
296}  // namespace net
297