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/third_party/quiche/src/quic/core/quic_received_packet_manager.h"
6
7 #include <algorithm>
8 #include <limits>
9 #include <utility>
10
11 #include "net/third_party/quiche/src/quic/core/congestion_control/rtt_stats.h"
12 #include "net/third_party/quiche/src/quic/core/crypto/crypto_protocol.h"
13 #include "net/third_party/quiche/src/quic/core/quic_connection_stats.h"
14 #include "net/third_party/quiche/src/quic/platform/api/quic_bug_tracker.h"
15 #include "net/third_party/quiche/src/quic/platform/api/quic_flags.h"
16 #include "net/third_party/quiche/src/quic/platform/api/quic_logging.h"
17
18 namespace quic {
19
20 namespace {
21
22 // The maximum number of packets to ack immediately after a missing packet for
23 // fast retransmission to kick in at the sender. This limit is created to
24 // reduce the number of acks sent that have no benefit for fast retransmission.
25 // Set to the number of nacks needed for fast retransmit plus one for protection
26 // against an ack loss
27 const size_t kMaxPacketsAfterNewMissing = 4;
28
29 // One quarter RTT delay when doing ack decimation.
30 const float kAckDecimationDelay = 0.25;
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 stats_(stats),
44 ack_mode_(GetQuicReloadableFlag(quic_enable_ack_decimation)
45 ? ACK_DECIMATION
46 : TCP_ACKING),
47 num_retransmittable_packets_received_since_last_ack_sent_(0),
48 min_received_before_ack_decimation_(kMinReceivedBeforeAckDecimation),
49 ack_frequency_before_ack_decimation_(
50 kDefaultRetransmittablePacketsBeforeAck),
51 ack_decimation_delay_(kAckDecimationDelay),
52 unlimited_ack_decimation_(false),
53 fast_ack_after_quiescence_(false),
54 one_immediate_ack_(false),
55 local_max_ack_delay_(
56 QuicTime::Delta::FromMilliseconds(kDefaultDelayedAckTimeMs)),
57 ack_timeout_(QuicTime::Zero()),
58 time_of_previous_received_packet_(QuicTime::Zero()),
59 was_last_packet_missing_(false) {
60 if (ack_mode_ == ACK_DECIMATION) {
61 QUIC_RELOADABLE_FLAG_COUNT(quic_enable_ack_decimation);
62 }
63 }
64
~QuicReceivedPacketManager()65 QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
66
SetFromConfig(const QuicConfig & config,Perspective perspective)67 void QuicReceivedPacketManager::SetFromConfig(const QuicConfig& config,
68 Perspective perspective) {
69 if (GetQuicReloadableFlag(quic_enable_ack_decimation) &&
70 config.HasClientSentConnectionOption(kACD0, perspective)) {
71 ack_mode_ = TCP_ACKING;
72 }
73 if (config.HasClientSentConnectionOption(kACKD, perspective)) {
74 ack_mode_ = ACK_DECIMATION;
75 }
76 if (config.HasClientSentConnectionOption(kAKD2, perspective)) {
77 ack_mode_ = ACK_DECIMATION_WITH_REORDERING;
78 }
79 if (config.HasClientSentConnectionOption(kAKD3, perspective)) {
80 ack_mode_ = ACK_DECIMATION;
81 ack_decimation_delay_ = kShortAckDecimationDelay;
82 }
83 if (config.HasClientSentConnectionOption(kAKD4, perspective)) {
84 ack_mode_ = ACK_DECIMATION_WITH_REORDERING;
85 ack_decimation_delay_ = kShortAckDecimationDelay;
86 }
87 if (config.HasClientSentConnectionOption(kAKDU, perspective)) {
88 unlimited_ack_decimation_ = true;
89 }
90 if (config.HasClientSentConnectionOption(kACKQ, perspective)) {
91 fast_ack_after_quiescence_ = true;
92 }
93 if (config.HasClientSentConnectionOption(k1ACK, perspective)) {
94 one_immediate_ack_ = true;
95 }
96 }
97
RecordPacketReceived(const QuicPacketHeader & header,QuicTime receipt_time)98 void QuicReceivedPacketManager::RecordPacketReceived(
99 const QuicPacketHeader& header,
100 QuicTime receipt_time) {
101 const QuicPacketNumber packet_number = header.packet_number;
102 DCHECK(IsAwaitingPacket(packet_number)) << " packet_number:" << packet_number;
103 was_last_packet_missing_ = IsMissing(packet_number);
104 if (!ack_frame_updated_) {
105 ack_frame_.received_packet_times.clear();
106 }
107 ack_frame_updated_ = true;
108
109 if (LargestAcked(ack_frame_).IsInitialized() &&
110 LargestAcked(ack_frame_) > packet_number) {
111 // Record how out of order stats.
112 ++stats_->packets_reordered;
113 stats_->max_sequence_reordering =
114 std::max(stats_->max_sequence_reordering,
115 LargestAcked(ack_frame_) - packet_number);
116 int64_t reordering_time_us =
117 (receipt_time - time_largest_observed_).ToMicroseconds();
118 stats_->max_time_reordering_us =
119 std::max(stats_->max_time_reordering_us, reordering_time_us);
120 }
121 if (!LargestAcked(ack_frame_).IsInitialized() ||
122 packet_number > LargestAcked(ack_frame_)) {
123 ack_frame_.largest_acked = packet_number;
124 time_largest_observed_ = receipt_time;
125 }
126 ack_frame_.packets.Add(packet_number);
127
128 if (save_timestamps_) {
129 // The timestamp format only handles packets in time order.
130 if (!ack_frame_.received_packet_times.empty() &&
131 ack_frame_.received_packet_times.back().second > receipt_time) {
132 QUIC_LOG(WARNING)
133 << "Receive time went backwards from: "
134 << ack_frame_.received_packet_times.back().second.ToDebuggingValue()
135 << " to " << receipt_time.ToDebuggingValue();
136 } else {
137 ack_frame_.received_packet_times.push_back(
138 std::make_pair(packet_number, receipt_time));
139 }
140 }
141
142 if (least_received_packet_number_.IsInitialized()) {
143 least_received_packet_number_ =
144 std::min(least_received_packet_number_, packet_number);
145 } else {
146 least_received_packet_number_ = packet_number;
147 }
148 }
149
IsMissing(QuicPacketNumber packet_number)150 bool QuicReceivedPacketManager::IsMissing(QuicPacketNumber packet_number) {
151 return LargestAcked(ack_frame_).IsInitialized() &&
152 packet_number < LargestAcked(ack_frame_) &&
153 !ack_frame_.packets.Contains(packet_number);
154 }
155
IsAwaitingPacket(QuicPacketNumber packet_number) const156 bool QuicReceivedPacketManager::IsAwaitingPacket(
157 QuicPacketNumber packet_number) const {
158 return quic::IsAwaitingPacket(ack_frame_, packet_number,
159 peer_least_packet_awaiting_ack_);
160 }
161
GetUpdatedAckFrame(QuicTime approximate_now)162 const QuicFrame QuicReceivedPacketManager::GetUpdatedAckFrame(
163 QuicTime approximate_now) {
164 if (time_largest_observed_ == QuicTime::Zero()) {
165 // We have received no packets.
166 ack_frame_.ack_delay_time = QuicTime::Delta::Infinite();
167 } else {
168 // Ensure the delta is zero if approximate now is "in the past".
169 ack_frame_.ack_delay_time = approximate_now < time_largest_observed_
170 ? QuicTime::Delta::Zero()
171 : approximate_now - time_largest_observed_;
172 }
173 while (max_ack_ranges_ > 0 &&
174 ack_frame_.packets.NumIntervals() > max_ack_ranges_) {
175 ack_frame_.packets.RemoveSmallestInterval();
176 }
177 // Clear all packet times if any are too far from largest observed.
178 // It's expected this is extremely rare.
179 for (auto it = ack_frame_.received_packet_times.begin();
180 it != ack_frame_.received_packet_times.end();) {
181 if (LargestAcked(ack_frame_) - it->first >=
182 std::numeric_limits<uint8_t>::max()) {
183 it = ack_frame_.received_packet_times.erase(it);
184 } else {
185 ++it;
186 }
187 }
188
189 return QuicFrame(&ack_frame_);
190 }
191
DontWaitForPacketsBefore(QuicPacketNumber least_unacked)192 void QuicReceivedPacketManager::DontWaitForPacketsBefore(
193 QuicPacketNumber least_unacked) {
194 if (!least_unacked.IsInitialized()) {
195 return;
196 }
197 // ValidateAck() should fail if peer_least_packet_awaiting_ack shrinks.
198 DCHECK(!peer_least_packet_awaiting_ack_.IsInitialized() ||
199 peer_least_packet_awaiting_ack_ <= least_unacked);
200 if (!peer_least_packet_awaiting_ack_.IsInitialized() ||
201 least_unacked > peer_least_packet_awaiting_ack_) {
202 peer_least_packet_awaiting_ack_ = least_unacked;
203 bool packets_updated = ack_frame_.packets.RemoveUpTo(least_unacked);
204 if (packets_updated) {
205 // Ack frame gets updated because packets set is updated because of stop
206 // waiting frame.
207 ack_frame_updated_ = true;
208 }
209 }
210 DCHECK(ack_frame_.packets.Empty() ||
211 !peer_least_packet_awaiting_ack_.IsInitialized() ||
212 ack_frame_.packets.Min() >= peer_least_packet_awaiting_ack_);
213 }
214
MaybeUpdateAckTimeout(bool should_last_packet_instigate_acks,QuicPacketNumber last_received_packet_number,QuicTime time_of_last_received_packet,QuicTime now,const RttStats * rtt_stats)215 void QuicReceivedPacketManager::MaybeUpdateAckTimeout(
216 bool should_last_packet_instigate_acks,
217 QuicPacketNumber last_received_packet_number,
218 QuicTime time_of_last_received_packet,
219 QuicTime now,
220 const RttStats* rtt_stats) {
221 if (!ack_frame_updated_) {
222 // ACK frame has not been updated, nothing to do.
223 return;
224 }
225
226 if (was_last_packet_missing_ && last_sent_largest_acked_.IsInitialized() &&
227 last_received_packet_number < last_sent_largest_acked_) {
228 // Only ack immediately if an ACK frame was sent with a larger largest acked
229 // than the newly received packet number.
230 ack_timeout_ = now;
231 return;
232 }
233
234 if (!should_last_packet_instigate_acks) {
235 return;
236 }
237
238 ++num_retransmittable_packets_received_since_last_ack_sent_;
239 if (ack_mode_ != TCP_ACKING &&
240 last_received_packet_number >= PeerFirstSendingPacketNumber() +
241 min_received_before_ack_decimation_) {
242 // Ack up to 10 packets at once unless ack decimation is unlimited.
243 if (!unlimited_ack_decimation_ &&
244 num_retransmittable_packets_received_since_last_ack_sent_ >=
245 kMaxRetransmittablePacketsBeforeAck) {
246 ack_timeout_ = now;
247 return;
248 }
249 // Wait for the minimum of the ack decimation delay or the delayed ack time
250 // before sending an ack.
251 QuicTime::Delta ack_delay = std::min(
252 local_max_ack_delay_, rtt_stats->min_rtt() * ack_decimation_delay_);
253 if (GetQuicReloadableFlag(quic_ack_delay_alarm_granularity)) {
254 QUIC_RELOADABLE_FLAG_COUNT(quic_ack_delay_alarm_granularity);
255 ack_delay = std::max(ack_delay, kAlarmGranularity);
256 }
257 if (fast_ack_after_quiescence_ && now - time_of_previous_received_packet_ >
258 rtt_stats->SmoothedOrInitialRtt()) {
259 // Ack the first packet out of queiscence faster, because QUIC does
260 // not pace the first few packets and commonly these may be handshake
261 // or TLP packets, which we'd like to acknowledge quickly.
262 ack_delay = kAlarmGranularity;
263 }
264 MaybeUpdateAckTimeoutTo(now + ack_delay);
265 } else {
266 // Ack with a timer or every 2 packets by default.
267 if (num_retransmittable_packets_received_since_last_ack_sent_ >=
268 ack_frequency_before_ack_decimation_) {
269 ack_timeout_ = now;
270 } else if (fast_ack_after_quiescence_ &&
271 (now - time_of_previous_received_packet_) >
272 rtt_stats->SmoothedOrInitialRtt()) {
273 // Ack the first packet out of queiscence faster, because QUIC does
274 // not pace the first few packets and commonly these may be handshake
275 // or TLP packets, which we'd like to acknowledge quickly.
276 MaybeUpdateAckTimeoutTo(now + kAlarmGranularity);
277 } else {
278 MaybeUpdateAckTimeoutTo(now + local_max_ack_delay_);
279 }
280 }
281
282 // If there are new missing packets to report, send an ack immediately.
283 if (HasNewMissingPackets()) {
284 if (ack_mode_ == ACK_DECIMATION_WITH_REORDERING) {
285 // Wait the minimum of an eighth min_rtt and the existing ack time.
286 QuicTime ack_time = now + kShortAckDecimationDelay * rtt_stats->min_rtt();
287 MaybeUpdateAckTimeoutTo(ack_time);
288 } else {
289 ack_timeout_ = now;
290 }
291 }
292
293 if (fast_ack_after_quiescence_) {
294 time_of_previous_received_packet_ = time_of_last_received_packet;
295 }
296 }
297
ResetAckStates()298 void QuicReceivedPacketManager::ResetAckStates() {
299 ack_frame_updated_ = false;
300 ack_timeout_ = QuicTime::Zero();
301 num_retransmittable_packets_received_since_last_ack_sent_ = 0;
302 last_sent_largest_acked_ = LargestAcked(ack_frame_);
303 }
304
MaybeUpdateAckTimeoutTo(QuicTime time)305 void QuicReceivedPacketManager::MaybeUpdateAckTimeoutTo(QuicTime time) {
306 if (!ack_timeout_.IsInitialized() || ack_timeout_ > time) {
307 ack_timeout_ = time;
308 }
309 }
310
HasMissingPackets() const311 bool QuicReceivedPacketManager::HasMissingPackets() const {
312 if (ack_frame_.packets.Empty()) {
313 return false;
314 }
315 if (ack_frame_.packets.NumIntervals() > 1) {
316 return true;
317 }
318 return peer_least_packet_awaiting_ack_.IsInitialized() &&
319 ack_frame_.packets.Min() > peer_least_packet_awaiting_ack_;
320 }
321
HasNewMissingPackets() const322 bool QuicReceivedPacketManager::HasNewMissingPackets() const {
323 if (one_immediate_ack_) {
324 return HasMissingPackets() && ack_frame_.packets.LastIntervalLength() == 1;
325 }
326 return HasMissingPackets() &&
327 ack_frame_.packets.LastIntervalLength() <= kMaxPacketsAfterNewMissing;
328 }
329
ack_frame_updated() const330 bool QuicReceivedPacketManager::ack_frame_updated() const {
331 return ack_frame_updated_;
332 }
333
GetLargestObserved() const334 QuicPacketNumber QuicReceivedPacketManager::GetLargestObserved() const {
335 return LargestAcked(ack_frame_);
336 }
337
PeerFirstSendingPacketNumber() const338 QuicPacketNumber QuicReceivedPacketManager::PeerFirstSendingPacketNumber()
339 const {
340 if (!least_received_packet_number_.IsInitialized()) {
341 QUIC_BUG << "No packets have been received yet";
342 return QuicPacketNumber(1);
343 }
344 return least_received_packet_number_;
345 }
346
IsAckFrameEmpty() const347 bool QuicReceivedPacketManager::IsAckFrameEmpty() const {
348 return ack_frame_.packets.Empty();
349 }
350
351 } // namespace quic
352