quic_received_packet_manager.cc revision d57369da7c6519fef57db42085f7b42d4c8845c1 
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 "base/logging.h"
8#include "base/stl_util.h"
9#include "net/base/linked_hash_map.h"
10
11using std::make_pair;
12using std::max;
13using std::min;
14
15namespace net {
16
17namespace {
18
19// The maximum number of packets to ack immediately after a missing packet for
20// fast retransmission to kick in at the sender.  This limit is created to
21// reduce the number of acks sent that have no benefit for fast retransmission.
22// Set to the number of nacks needed for fast retransmit plus one for protection
23// against an ack loss
24const size_t kMaxPacketsAfterNewMissing = 4;
25
26}
27
28QuicReceivedPacketManager::QuicReceivedPacketManager(
29    CongestionFeedbackType congestion_type)
30    : packets_entropy_hash_(0),
31      largest_sequence_number_(0),
32      peer_largest_observed_packet_(0),
33      least_packet_awaited_by_peer_(1),
34      peer_least_packet_awaiting_ack_(0),
35      time_largest_observed_(QuicTime::Zero()),
36      receive_algorithm_(ReceiveAlgorithmInterface::Create(congestion_type)) {
37  received_info_.largest_observed = 0;
38  received_info_.entropy_hash = 0;
39}
40
41QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
42
43void QuicReceivedPacketManager::RecordPacketReceived(
44    QuicByteCount bytes,
45    const QuicPacketHeader& header,
46    QuicTime receipt_time,
47    bool revived) {
48  QuicPacketSequenceNumber sequence_number = header.packet_sequence_number;
49  DCHECK(IsAwaitingPacket(sequence_number));
50
51  InsertMissingPacketsBetween(
52      &received_info_,
53      max(received_info_.largest_observed + 1, peer_least_packet_awaiting_ack_),
54      header.packet_sequence_number);
55
56  if (received_info_.largest_observed > header.packet_sequence_number) {
57    // We've gotten one of the out of order packets - remove it from our
58    // "missing packets" list.
59    DVLOG(1) << "Removing " << sequence_number << " from missing list";
60    received_info_.missing_packets.erase(sequence_number);
61  }
62  if (header.packet_sequence_number > received_info_.largest_observed) {
63    received_info_.largest_observed = header.packet_sequence_number;
64    time_largest_observed_ = receipt_time;
65  }
66  RecordPacketEntropyHash(sequence_number, header.entropy_hash);
67
68  // Don't update the receive algorithm for revived packets.
69  if (!revived) {
70    receive_algorithm_->RecordIncomingPacket(
71        bytes, sequence_number, receipt_time, revived);
72  }
73}
74
75bool QuicReceivedPacketManager::IsMissing(
76    QuicPacketSequenceNumber sequence_number) {
77  return ContainsKey(received_info_.missing_packets, sequence_number);
78}
79
80bool QuicReceivedPacketManager::IsAwaitingPacket(
81    QuicPacketSequenceNumber sequence_number) {
82  return ::net::IsAwaitingPacket(received_info_, sequence_number);
83}
84
85void QuicReceivedPacketManager::UpdateReceivedPacketInfo(
86    ReceivedPacketInfo* received_info,
87    QuicTime approximate_now) {
88  *received_info = received_info_;
89  received_info->entropy_hash = EntropyHash(received_info_.largest_observed);
90
91  if (time_largest_observed_ == QuicTime::Zero()) {
92    // We have received no packets.
93    received_info->delta_time_largest_observed = QuicTime::Delta::Infinite();
94    return;
95  }
96
97  if (approximate_now < time_largest_observed_) {
98    // Approximate now may well be "in the past".
99    received_info->delta_time_largest_observed = QuicTime::Delta::Zero();
100    return;
101  }
102
103  received_info->delta_time_largest_observed =
104      approximate_now.Subtract(time_largest_observed_);
105}
106
107void QuicReceivedPacketManager::RecordPacketEntropyHash(
108    QuicPacketSequenceNumber sequence_number,
109    QuicPacketEntropyHash entropy_hash) {
110  if (sequence_number < largest_sequence_number_) {
111    DVLOG(1) << "Ignoring received packet entropy for sequence_number:"
112               << sequence_number << " less than largest_peer_sequence_number:"
113               << largest_sequence_number_;
114    return;
115  }
116  packets_entropy_.insert(make_pair(sequence_number, entropy_hash));
117  packets_entropy_hash_ ^= entropy_hash;
118  DVLOG(2) << "setting cumulative received entropy hash to: "
119           << static_cast<int>(packets_entropy_hash_)
120           << " updated with sequence number " << sequence_number
121           << " entropy hash: " << static_cast<int>(entropy_hash);
122}
123
124bool QuicReceivedPacketManager::GenerateCongestionFeedback(
125    QuicCongestionFeedbackFrame* feedback) {
126  return receive_algorithm_->GenerateCongestionFeedback(feedback);
127}
128
129QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash(
130    QuicPacketSequenceNumber sequence_number) const {
131  DCHECK_LE(sequence_number, received_info_.largest_observed);
132  DCHECK_GE(sequence_number, largest_sequence_number_);
133  if (sequence_number == received_info_.largest_observed) {
134    return packets_entropy_hash_;
135  }
136
137  ReceivedEntropyMap::const_iterator it =
138      packets_entropy_.upper_bound(sequence_number);
139  // When this map is empty we should only query entropy for
140  // received_info_.largest_observed, since no other entropy can be correctly
141  // calculated, because we're not storing the entropy for any prior packets.
142  // TODO(rtenneti): add support for LOG_IF_EVERY_N_SEC to chromium.
143  // LOG_IF_EVERY_N_SEC(DFATAL, it == packets_entropy_.end(), 10)
144  LOG_IF(DFATAL, it == packets_entropy_.end())
145      << "EntropyHash may be unknown. largest_received: "
146      << received_info_.largest_observed
147      << " sequence_number: " << sequence_number;
148
149  // TODO(satyamshekhar): Make this O(1).
150  QuicPacketEntropyHash hash = packets_entropy_hash_;
151  for (; it != packets_entropy_.end(); ++it) {
152    hash ^= it->second;
153  }
154  return hash;
155}
156
157void QuicReceivedPacketManager::RecalculateEntropyHash(
158    QuicPacketSequenceNumber peer_least_unacked,
159    QuicPacketEntropyHash entropy_hash) {
160  DCHECK_LE(peer_least_unacked, received_info_.largest_observed);
161  if (peer_least_unacked < largest_sequence_number_) {
162    DVLOG(1) << "Ignoring received peer_least_unacked:" << peer_least_unacked
163               << " less than largest_peer_sequence_number:"
164               << largest_sequence_number_;
165    return;
166  }
167  largest_sequence_number_ = peer_least_unacked;
168  packets_entropy_hash_ = entropy_hash;
169  ReceivedEntropyMap::iterator it =
170      packets_entropy_.lower_bound(peer_least_unacked);
171  // TODO(satyamshekhar): Make this O(1).
172  for (; it != packets_entropy_.end(); ++it) {
173    packets_entropy_hash_ ^= it->second;
174  }
175  // Discard entropies before least unacked.
176  packets_entropy_.erase(
177      packets_entropy_.begin(),
178      packets_entropy_.lower_bound(
179          min(peer_least_unacked, received_info_.largest_observed)));
180}
181
182void QuicReceivedPacketManager::UpdatePacketInformationReceivedByPeer(
183    const QuicAckFrame& incoming_ack) {
184  // ValidateAck should fail if largest_observed ever shrinks.
185  DCHECK_LE(peer_largest_observed_packet_,
186            incoming_ack.received_info.largest_observed);
187  peer_largest_observed_packet_ = incoming_ack.received_info.largest_observed;
188
189  if (incoming_ack.received_info.missing_packets.empty()) {
190    least_packet_awaited_by_peer_ = peer_largest_observed_packet_ + 1;
191  } else {
192    least_packet_awaited_by_peer_ =
193        *(incoming_ack.received_info.missing_packets.begin());
194  }
195}
196
197bool QuicReceivedPacketManager::DontWaitForPacketsBefore(
198    QuicPacketSequenceNumber least_unacked) {
199  size_t missing_packets_count = received_info_.missing_packets.size();
200  received_info_.missing_packets.erase(
201      received_info_.missing_packets.begin(),
202      received_info_.missing_packets.lower_bound(least_unacked));
203  return missing_packets_count != received_info_.missing_packets.size();
204}
205
206void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer(
207    const QuicAckFrame& incoming_ack) {
208  // ValidateAck() should fail if peer_least_packet_awaiting_ack_ shrinks.
209  DCHECK_LE(peer_least_packet_awaiting_ack_,
210            incoming_ack.sent_info.least_unacked);
211  if (incoming_ack.sent_info.least_unacked > peer_least_packet_awaiting_ack_) {
212    bool missed_packets =
213        DontWaitForPacketsBefore(incoming_ack.sent_info.least_unacked);
214    if (missed_packets || incoming_ack.sent_info.least_unacked >
215            received_info_.largest_observed + 1) {
216      DVLOG(1) << "Updating entropy hashed since we missed packets";
217      // There were some missing packets that we won't ever get now. Recalculate
218      // the received entropy hash.
219      RecalculateEntropyHash(incoming_ack.sent_info.least_unacked,
220                             incoming_ack.sent_info.entropy_hash);
221    }
222    peer_least_packet_awaiting_ack_ = incoming_ack.sent_info.least_unacked;
223  }
224  DCHECK(received_info_.missing_packets.empty() ||
225         *received_info_.missing_packets.begin() >=
226             peer_least_packet_awaiting_ack_);
227}
228
229bool QuicReceivedPacketManager::HasMissingPackets() {
230  return !received_info_.missing_packets.empty();
231}
232
233bool QuicReceivedPacketManager::HasNewMissingPackets() {
234  return HasMissingPackets() &&
235      (received_info_.largest_observed -
236       *received_info_.missing_packets.rbegin()) <= kMaxPacketsAfterNewMissing;
237}
238
239}  // namespace net
240