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