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