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 "quiche/quic/core/quic_received_packet_manager.h"
6
7 #include <algorithm>
8 #include <limits>
9 #include <utility>
10
11 #include "quiche/quic/core/congestion_control/rtt_stats.h"
12 #include "quiche/quic/core/crypto/crypto_protocol.h"
13 #include "quiche/quic/core/quic_config.h"
14 #include "quiche/quic/core/quic_connection_stats.h"
15 #include "quiche/quic/core/quic_types.h"
16 #include "quiche/quic/platform/api/quic_bug_tracker.h"
17 #include "quiche/quic/platform/api/quic_flag_utils.h"
18 #include "quiche/quic/platform/api/quic_flags.h"
19 #include "quiche/quic/platform/api/quic_logging.h"
20
21 namespace quic {
22
23 namespace {
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
30 const size_t kMaxPacketsAfterNewMissing = 4;
31
32 // One eighth RTT delay when doing ack decimation.
33 const float kShortAckDecimationDelay = 0.125;
34 } // namespace
35
QuicReceivedPacketManager()36 QuicReceivedPacketManager::QuicReceivedPacketManager()
37 : QuicReceivedPacketManager(nullptr) {}
38
QuicReceivedPacketManager(QuicConnectionStats * stats)39 QuicReceivedPacketManager::QuicReceivedPacketManager(QuicConnectionStats* stats)
40 : ack_frame_updated_(false),
41 max_ack_ranges_(0),
42 time_largest_observed_(QuicTime::Zero()),
43 save_timestamps_(false),
44 save_timestamps_for_in_order_packets_(false),
45 stats_(stats),
46 num_retransmittable_packets_received_since_last_ack_sent_(0),
47 min_received_before_ack_decimation_(kMinReceivedBeforeAckDecimation),
48 ack_frequency_(kDefaultRetransmittablePacketsBeforeAck),
49 ack_decimation_delay_(kAckDecimationDelay),
50 unlimited_ack_decimation_(false),
51 one_immediate_ack_(false),
52 ignore_order_(false),
53 local_max_ack_delay_(
54 QuicTime::Delta::FromMilliseconds(kDefaultDelayedAckTimeMs)),
55 ack_timeout_(QuicTime::Zero()),
56 time_of_previous_received_packet_(QuicTime::Zero()),
57 was_last_packet_missing_(false),
58 last_ack_frequency_frame_sequence_number_(-1) {}
59
~QuicReceivedPacketManager()60 QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
61
SetFromConfig(const QuicConfig & config,Perspective perspective)62 void QuicReceivedPacketManager::SetFromConfig(const QuicConfig& config,
63 Perspective perspective) {
64 if (config.HasClientSentConnectionOption(kAKD3, perspective)) {
65 ack_decimation_delay_ = kShortAckDecimationDelay;
66 }
67 if (config.HasClientSentConnectionOption(kAKDU, perspective)) {
68 unlimited_ack_decimation_ = true;
69 }
70 if (config.HasClientSentConnectionOption(k1ACK, perspective)) {
71 one_immediate_ack_ = true;
72 }
73 }
74
RecordPacketReceived(const QuicPacketHeader & header,QuicTime receipt_time,const QuicEcnCodepoint ecn)75 void QuicReceivedPacketManager::RecordPacketReceived(
76 const QuicPacketHeader& header, QuicTime receipt_time,
77 const QuicEcnCodepoint ecn) {
78 const QuicPacketNumber packet_number = header.packet_number;
79 QUICHE_DCHECK(IsAwaitingPacket(packet_number))
80 << " packet_number:" << packet_number;
81 was_last_packet_missing_ = IsMissing(packet_number);
82 if (!ack_frame_updated_) {
83 ack_frame_.received_packet_times.clear();
84 }
85 ack_frame_updated_ = true;
86
87 // Whether |packet_number| is received out of order.
88 bool packet_reordered = false;
89 if (LargestAcked(ack_frame_).IsInitialized() &&
90 LargestAcked(ack_frame_) > packet_number) {
91 // Record how out of order stats.
92 packet_reordered = true;
93 ++stats_->packets_reordered;
94 stats_->max_sequence_reordering =
95 std::max(stats_->max_sequence_reordering,
96 LargestAcked(ack_frame_) - packet_number);
97 int64_t reordering_time_us =
98 (receipt_time - time_largest_observed_).ToMicroseconds();
99 stats_->max_time_reordering_us =
100 std::max(stats_->max_time_reordering_us, reordering_time_us);
101 }
102 if (!LargestAcked(ack_frame_).IsInitialized() ||
103 packet_number > LargestAcked(ack_frame_)) {
104 ack_frame_.largest_acked = packet_number;
105 time_largest_observed_ = receipt_time;
106 }
107 ack_frame_.packets.Add(packet_number);
108 MaybeTrimAckRanges();
109
110 if (save_timestamps_) {
111 // The timestamp format only handles packets in time order.
112 if (save_timestamps_for_in_order_packets_ && packet_reordered) {
113 QUIC_DLOG(WARNING) << "Not saving receive timestamp for packet "
114 << packet_number;
115 } else if (!ack_frame_.received_packet_times.empty() &&
116 ack_frame_.received_packet_times.back().second > receipt_time) {
117 QUIC_LOG(WARNING)
118 << "Receive time went backwards from: "
119 << ack_frame_.received_packet_times.back().second.ToDebuggingValue()
120 << " to " << receipt_time.ToDebuggingValue();
121 } else {
122 ack_frame_.received_packet_times.push_back(
123 std::make_pair(packet_number, receipt_time));
124 }
125 }
126
127 if (GetQuicRestartFlag(quic_receive_ecn3) && ecn != ECN_NOT_ECT) {
128 QUIC_RESTART_FLAG_COUNT_N(quic_receive_ecn3, 1, 2);
129 if (!ack_frame_.ecn_counters.has_value()) {
130 ack_frame_.ecn_counters = QuicEcnCounts();
131 }
132 switch (ecn) {
133 case ECN_NOT_ECT:
134 QUICHE_NOTREACHED();
135 break; // It's impossible to get here, but the compiler complains.
136 case ECN_ECT0:
137 ack_frame_.ecn_counters->ect0++;
138 break;
139 case ECN_ECT1:
140 ack_frame_.ecn_counters->ect1++;
141 break;
142 case ECN_CE:
143 ack_frame_.ecn_counters->ce++;
144 break;
145 }
146 }
147
148 if (least_received_packet_number_.IsInitialized()) {
149 least_received_packet_number_ =
150 std::min(least_received_packet_number_, packet_number);
151 } else {
152 least_received_packet_number_ = packet_number;
153 }
154 }
155
MaybeTrimAckRanges()156 void QuicReceivedPacketManager::MaybeTrimAckRanges() {
157 while (max_ack_ranges_ > 0 &&
158 ack_frame_.packets.NumIntervals() > max_ack_ranges_) {
159 ack_frame_.packets.RemoveSmallestInterval();
160 }
161 }
162
IsMissing(QuicPacketNumber packet_number)163 bool QuicReceivedPacketManager::IsMissing(QuicPacketNumber packet_number) {
164 return LargestAcked(ack_frame_).IsInitialized() &&
165 packet_number < LargestAcked(ack_frame_) &&
166 !ack_frame_.packets.Contains(packet_number);
167 }
168
IsAwaitingPacket(QuicPacketNumber packet_number) const169 bool QuicReceivedPacketManager::IsAwaitingPacket(
170 QuicPacketNumber packet_number) const {
171 return quic::IsAwaitingPacket(ack_frame_, packet_number,
172 peer_least_packet_awaiting_ack_);
173 }
174
GetUpdatedAckFrame(QuicTime approximate_now)175 const QuicFrame QuicReceivedPacketManager::GetUpdatedAckFrame(
176 QuicTime approximate_now) {
177 if (time_largest_observed_ == QuicTime::Zero()) {
178 // We have received no packets.
179 ack_frame_.ack_delay_time = QuicTime::Delta::Infinite();
180 } else {
181 // Ensure the delta is zero if approximate now is "in the past".
182 ack_frame_.ack_delay_time = approximate_now < time_largest_observed_
183 ? QuicTime::Delta::Zero()
184 : approximate_now - time_largest_observed_;
185 }
186
187 const size_t initial_ack_ranges = ack_frame_.packets.NumIntervals();
188 uint64_t num_iterations = 0;
189 while (max_ack_ranges_ > 0 &&
190 ack_frame_.packets.NumIntervals() > max_ack_ranges_) {
191 num_iterations++;
192 QUIC_BUG_IF(quic_rpm_too_many_ack_ranges, (num_iterations % 100000) == 0)
193 << "Too many ack ranges to remove, possibly a dead loop. "
194 "initial_ack_ranges:"
195 << initial_ack_ranges << " max_ack_ranges:" << max_ack_ranges_
196 << ", current_ack_ranges:" << ack_frame_.packets.NumIntervals()
197 << " num_iterations:" << num_iterations;
198 ack_frame_.packets.RemoveSmallestInterval();
199 }
200 // Clear all packet times if any are too far from largest observed.
201 // It's expected this is extremely rare.
202 for (auto it = ack_frame_.received_packet_times.begin();
203 it != ack_frame_.received_packet_times.end();) {
204 if (LargestAcked(ack_frame_) - it->first >=
205 std::numeric_limits<uint8_t>::max()) {
206 it = ack_frame_.received_packet_times.erase(it);
207 } else {
208 ++it;
209 }
210 }
211
212 #if QUIC_FRAME_DEBUG
213 QuicFrame frame = QuicFrame(&ack_frame_);
214 frame.delete_forbidden = true;
215 return frame;
216 #else // QUIC_FRAME_DEBUG
217 return QuicFrame(&ack_frame_);
218 #endif // QUIC_FRAME_DEBUG
219 }
220
DontWaitForPacketsBefore(QuicPacketNumber least_unacked)221 void QuicReceivedPacketManager::DontWaitForPacketsBefore(
222 QuicPacketNumber least_unacked) {
223 if (!least_unacked.IsInitialized()) {
224 return;
225 }
226 // ValidateAck() should fail if peer_least_packet_awaiting_ack shrinks.
227 QUICHE_DCHECK(!peer_least_packet_awaiting_ack_.IsInitialized() ||
228 peer_least_packet_awaiting_ack_ <= least_unacked);
229 if (!peer_least_packet_awaiting_ack_.IsInitialized() ||
230 least_unacked > peer_least_packet_awaiting_ack_) {
231 peer_least_packet_awaiting_ack_ = least_unacked;
232 bool packets_updated = ack_frame_.packets.RemoveUpTo(least_unacked);
233 if (packets_updated) {
234 // Ack frame gets updated because packets set is updated because of stop
235 // waiting frame.
236 ack_frame_updated_ = true;
237 }
238 }
239 QUICHE_DCHECK(ack_frame_.packets.Empty() ||
240 !peer_least_packet_awaiting_ack_.IsInitialized() ||
241 ack_frame_.packets.Min() >= peer_least_packet_awaiting_ack_);
242 }
243
GetMaxAckDelay(QuicPacketNumber last_received_packet_number,const RttStats & rtt_stats) const244 QuicTime::Delta QuicReceivedPacketManager::GetMaxAckDelay(
245 QuicPacketNumber last_received_packet_number,
246 const RttStats& rtt_stats) const {
247 if (AckFrequencyFrameReceived() ||
248 last_received_packet_number < PeerFirstSendingPacketNumber() +
249 min_received_before_ack_decimation_) {
250 return local_max_ack_delay_;
251 }
252
253 // Wait for the minimum of the ack decimation delay or the delayed ack time
254 // before sending an ack.
255 QuicTime::Delta ack_delay = std::min(
256 local_max_ack_delay_, rtt_stats.min_rtt() * ack_decimation_delay_);
257 return std::max(ack_delay, kAlarmGranularity);
258 }
259
MaybeUpdateAckFrequency(QuicPacketNumber last_received_packet_number)260 void QuicReceivedPacketManager::MaybeUpdateAckFrequency(
261 QuicPacketNumber last_received_packet_number) {
262 if (AckFrequencyFrameReceived()) {
263 // Skip Ack Decimation below after receiving an AckFrequencyFrame from the
264 // other end point.
265 return;
266 }
267 if (last_received_packet_number <
268 PeerFirstSendingPacketNumber() + min_received_before_ack_decimation_) {
269 return;
270 }
271 ack_frequency_ = unlimited_ack_decimation_
272 ? std::numeric_limits<size_t>::max()
273 : kMaxRetransmittablePacketsBeforeAck;
274 }
275
MaybeUpdateAckTimeout(bool should_last_packet_instigate_acks,QuicPacketNumber last_received_packet_number,QuicTime last_packet_receipt_time,QuicTime now,const RttStats * rtt_stats)276 void QuicReceivedPacketManager::MaybeUpdateAckTimeout(
277 bool should_last_packet_instigate_acks,
278 QuicPacketNumber last_received_packet_number,
279 QuicTime last_packet_receipt_time, QuicTime now,
280 const RttStats* rtt_stats) {
281 if (!ack_frame_updated_) {
282 // ACK frame has not been updated, nothing to do.
283 return;
284 }
285
286 if (!ignore_order_ && was_last_packet_missing_ &&
287 last_sent_largest_acked_.IsInitialized() &&
288 last_received_packet_number < last_sent_largest_acked_) {
289 // Only ack immediately if an ACK frame was sent with a larger largest acked
290 // than the newly received packet number.
291 ack_timeout_ = now;
292 return;
293 }
294
295 if (!should_last_packet_instigate_acks) {
296 return;
297 }
298
299 ++num_retransmittable_packets_received_since_last_ack_sent_;
300
301 MaybeUpdateAckFrequency(last_received_packet_number);
302 if (num_retransmittable_packets_received_since_last_ack_sent_ >=
303 ack_frequency_) {
304 ack_timeout_ = now;
305 return;
306 }
307
308 if (!ignore_order_ && HasNewMissingPackets()) {
309 ack_timeout_ = now;
310 return;
311 }
312
313 const QuicTime updated_ack_time = std::max(
314 now, std::min(last_packet_receipt_time, now) +
315 GetMaxAckDelay(last_received_packet_number, *rtt_stats));
316 if (!ack_timeout_.IsInitialized() || ack_timeout_ > updated_ack_time) {
317 ack_timeout_ = updated_ack_time;
318 }
319 }
320
ResetAckStates()321 void QuicReceivedPacketManager::ResetAckStates() {
322 ack_frame_updated_ = false;
323 ack_timeout_ = QuicTime::Zero();
324 num_retransmittable_packets_received_since_last_ack_sent_ = 0;
325 last_sent_largest_acked_ = LargestAcked(ack_frame_);
326 }
327
HasMissingPackets() const328 bool QuicReceivedPacketManager::HasMissingPackets() const {
329 if (ack_frame_.packets.Empty()) {
330 return false;
331 }
332 if (ack_frame_.packets.NumIntervals() > 1) {
333 return true;
334 }
335 return peer_least_packet_awaiting_ack_.IsInitialized() &&
336 ack_frame_.packets.Min() > peer_least_packet_awaiting_ack_;
337 }
338
HasNewMissingPackets() const339 bool QuicReceivedPacketManager::HasNewMissingPackets() const {
340 if (one_immediate_ack_) {
341 return HasMissingPackets() && ack_frame_.packets.LastIntervalLength() == 1;
342 }
343 return HasMissingPackets() &&
344 ack_frame_.packets.LastIntervalLength() <= kMaxPacketsAfterNewMissing;
345 }
346
ack_frame_updated() const347 bool QuicReceivedPacketManager::ack_frame_updated() const {
348 return ack_frame_updated_;
349 }
350
GetLargestObserved() const351 QuicPacketNumber QuicReceivedPacketManager::GetLargestObserved() const {
352 return LargestAcked(ack_frame_);
353 }
354
PeerFirstSendingPacketNumber() const355 QuicPacketNumber QuicReceivedPacketManager::PeerFirstSendingPacketNumber()
356 const {
357 if (!least_received_packet_number_.IsInitialized()) {
358 QUIC_BUG(quic_bug_10849_1) << "No packets have been received yet";
359 return QuicPacketNumber(1);
360 }
361 return least_received_packet_number_;
362 }
363
IsAckFrameEmpty() const364 bool QuicReceivedPacketManager::IsAckFrameEmpty() const {
365 return ack_frame_.packets.Empty();
366 }
367
OnAckFrequencyFrame(const QuicAckFrequencyFrame & frame)368 void QuicReceivedPacketManager::OnAckFrequencyFrame(
369 const QuicAckFrequencyFrame& frame) {
370 int64_t new_sequence_number = frame.sequence_number;
371 if (new_sequence_number <= last_ack_frequency_frame_sequence_number_) {
372 // Ignore old ACK_FREQUENCY frames.
373 return;
374 }
375 last_ack_frequency_frame_sequence_number_ = new_sequence_number;
376 ack_frequency_ = frame.packet_tolerance;
377 local_max_ack_delay_ = frame.max_ack_delay;
378 ignore_order_ = frame.ignore_order;
379 }
380
381 } // namespace quic
382