| // Copyright 2013 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "net/third_party/quic/core/quic_received_packet_manager.h" |
| |
| #include <algorithm> |
| #include <limits> |
| #include <utility> |
| |
| #include "net/third_party/quic/core/congestion_control/rtt_stats.h" |
| #include "net/third_party/quic/core/crypto/crypto_protocol.h" |
| #include "net/third_party/quic/core/quic_connection_stats.h" |
| #include "net/third_party/quic/platform/api/quic_bug_tracker.h" |
| #include "net/third_party/quic/platform/api/quic_logging.h" |
| |
| namespace quic { |
| |
| namespace { |
| |
| // The maximum number of packets to ack immediately after a missing packet for |
| // fast retransmission to kick in at the sender. This limit is created to |
| // reduce the number of acks sent that have no benefit for fast retransmission. |
| // Set to the number of nacks needed for fast retransmit plus one for protection |
| // against an ack loss |
| const size_t kMaxPacketsAfterNewMissing = 4; |
| |
| // Maximum number of retransmittable packets received before sending an ack. |
| const QuicPacketCount kDefaultRetransmittablePacketsBeforeAck = 2; |
| // Minimum number of packets received before ack decimation is enabled. |
| // This intends to avoid the beginning of slow start, when CWNDs may be |
| // rapidly increasing. |
| const QuicPacketCount kMinReceivedBeforeAckDecimation = 100; |
| // Wait for up to 10 retransmittable packets before sending an ack. |
| const QuicPacketCount kMaxRetransmittablePacketsBeforeAck = 10; |
| // One quarter RTT delay when doing ack decimation. |
| const float kAckDecimationDelay = 0.25; |
| // One eighth RTT delay when doing ack decimation. |
| const float kShortAckDecimationDelay = 0.125; |
| } // namespace |
| |
| QuicReceivedPacketManager::QuicReceivedPacketManager(QuicConnectionStats* stats) |
| : ack_frame_updated_(false), |
| max_ack_ranges_(0), |
| time_largest_observed_(QuicTime::Zero()), |
| save_timestamps_(false), |
| stats_(stats), |
| ack_mode_(GetQuicReloadableFlag(quic_enable_ack_decimation) |
| ? ACK_DECIMATION |
| : TCP_ACKING), |
| num_retransmittable_packets_received_since_last_ack_sent_(0), |
| min_received_before_ack_decimation_(kMinReceivedBeforeAckDecimation), |
| ack_frequency_before_ack_decimation_( |
| kDefaultRetransmittablePacketsBeforeAck), |
| ack_decimation_delay_(kAckDecimationDelay), |
| unlimited_ack_decimation_(false), |
| fast_ack_after_quiescence_(false), |
| ack_timeout_(QuicTime::Zero()), |
| time_of_previous_received_packet_(QuicTime::Zero()), |
| was_last_packet_missing_(false), |
| decide_when_to_send_acks_( |
| GetQuicReloadableFlag(quic_deprecate_ack_bundling_mode) && |
| GetQuicReloadableFlag(quic_rpm_decides_when_to_send_acks)) {} |
| |
| QuicReceivedPacketManager::~QuicReceivedPacketManager() {} |
| |
| void QuicReceivedPacketManager::SetFromConfig(const QuicConfig& config, |
| Perspective perspective) { |
| DCHECK(decide_when_to_send_acks_); |
| if (GetQuicReloadableFlag(quic_enable_ack_decimation) && |
| config.HasClientSentConnectionOption(kACD0, perspective)) { |
| ack_mode_ = TCP_ACKING; |
| } |
| if (config.HasClientSentConnectionOption(kACKD, perspective)) { |
| ack_mode_ = ACK_DECIMATION; |
| } |
| if (config.HasClientSentConnectionOption(kAKD2, perspective)) { |
| ack_mode_ = ACK_DECIMATION_WITH_REORDERING; |
| } |
| if (config.HasClientSentConnectionOption(kAKD3, perspective)) { |
| ack_mode_ = ACK_DECIMATION; |
| ack_decimation_delay_ = kShortAckDecimationDelay; |
| } |
| if (config.HasClientSentConnectionOption(kAKD4, perspective)) { |
| ack_mode_ = ACK_DECIMATION_WITH_REORDERING; |
| ack_decimation_delay_ = kShortAckDecimationDelay; |
| } |
| if (config.HasClientSentConnectionOption(kAKDU, perspective)) { |
| unlimited_ack_decimation_ = true; |
| } |
| if (config.HasClientSentConnectionOption(kACKQ, perspective)) { |
| fast_ack_after_quiescence_ = true; |
| } |
| } |
| |
| void QuicReceivedPacketManager::RecordPacketReceived( |
| const QuicPacketHeader& header, |
| QuicTime receipt_time) { |
| const QuicPacketNumber packet_number = header.packet_number; |
| DCHECK(IsAwaitingPacket(packet_number)) << " packet_number:" << packet_number; |
| if (decide_when_to_send_acks_) { |
| was_last_packet_missing_ = IsMissing(packet_number); |
| } |
| if (!ack_frame_updated_) { |
| ack_frame_.received_packet_times.clear(); |
| } |
| ack_frame_updated_ = true; |
| |
| if (LargestAcked(ack_frame_).IsInitialized() && |
| LargestAcked(ack_frame_) > packet_number) { |
| // Record how out of order stats. |
| ++stats_->packets_reordered; |
| stats_->max_sequence_reordering = |
| std::max(stats_->max_sequence_reordering, |
| LargestAcked(ack_frame_) - packet_number); |
| int64_t reordering_time_us = |
| (receipt_time - time_largest_observed_).ToMicroseconds(); |
| stats_->max_time_reordering_us = |
| std::max(stats_->max_time_reordering_us, reordering_time_us); |
| } |
| if (!LargestAcked(ack_frame_).IsInitialized() || |
| packet_number > LargestAcked(ack_frame_)) { |
| ack_frame_.largest_acked = packet_number; |
| time_largest_observed_ = receipt_time; |
| } |
| ack_frame_.packets.Add(packet_number); |
| |
| if (save_timestamps_) { |
| // The timestamp format only handles packets in time order. |
| if (!ack_frame_.received_packet_times.empty() && |
| ack_frame_.received_packet_times.back().second > receipt_time) { |
| LOG(WARNING) |
| << "Receive time went backwards from: " |
| << ack_frame_.received_packet_times.back().second.ToDebuggingValue() |
| << " to " << receipt_time.ToDebuggingValue(); |
| } else { |
| ack_frame_.received_packet_times.push_back( |
| std::make_pair(packet_number, receipt_time)); |
| } |
| } |
| |
| if (least_received_packet_number_.IsInitialized()) { |
| least_received_packet_number_ = |
| std::min(least_received_packet_number_, packet_number); |
| } else { |
| least_received_packet_number_ = packet_number; |
| } |
| } |
| |
| bool QuicReceivedPacketManager::IsMissing(QuicPacketNumber packet_number) { |
| return LargestAcked(ack_frame_).IsInitialized() && |
| packet_number < LargestAcked(ack_frame_) && |
| !ack_frame_.packets.Contains(packet_number); |
| } |
| |
| bool QuicReceivedPacketManager::IsAwaitingPacket( |
| QuicPacketNumber packet_number) { |
| return quic::IsAwaitingPacket(ack_frame_, packet_number, |
| peer_least_packet_awaiting_ack_); |
| } |
| |
| const QuicFrame QuicReceivedPacketManager::GetUpdatedAckFrame( |
| QuicTime approximate_now) { |
| if (!decide_when_to_send_acks_) { |
| ack_frame_updated_ = false; |
| } |
| if (time_largest_observed_ == QuicTime::Zero()) { |
| // We have received no packets. |
| ack_frame_.ack_delay_time = QuicTime::Delta::Infinite(); |
| } else { |
| // Ensure the delta is zero if approximate now is "in the past". |
| ack_frame_.ack_delay_time = approximate_now < time_largest_observed_ |
| ? QuicTime::Delta::Zero() |
| : approximate_now - time_largest_observed_; |
| } |
| while (max_ack_ranges_ > 0 && |
| ack_frame_.packets.NumIntervals() > max_ack_ranges_) { |
| ack_frame_.packets.RemoveSmallestInterval(); |
| } |
| // Clear all packet times if any are too far from largest observed. |
| // It's expected this is extremely rare. |
| for (auto it = ack_frame_.received_packet_times.begin(); |
| it != ack_frame_.received_packet_times.end();) { |
| if (LargestAcked(ack_frame_) - it->first >= |
| std::numeric_limits<uint8_t>::max()) { |
| it = ack_frame_.received_packet_times.erase(it); |
| } else { |
| ++it; |
| } |
| } |
| |
| return QuicFrame(&ack_frame_); |
| } |
| |
| void QuicReceivedPacketManager::DontWaitForPacketsBefore( |
| QuicPacketNumber least_unacked) { |
| if (!least_unacked.IsInitialized()) { |
| return; |
| } |
| // ValidateAck() should fail if peer_least_packet_awaiting_ack shrinks. |
| DCHECK(!peer_least_packet_awaiting_ack_.IsInitialized() || |
| peer_least_packet_awaiting_ack_ <= least_unacked); |
| if (!peer_least_packet_awaiting_ack_.IsInitialized() || |
| least_unacked > peer_least_packet_awaiting_ack_) { |
| peer_least_packet_awaiting_ack_ = least_unacked; |
| bool packets_updated = ack_frame_.packets.RemoveUpTo(least_unacked); |
| if (packets_updated) { |
| // Ack frame gets updated because packets set is updated because of stop |
| // waiting frame. |
| ack_frame_updated_ = true; |
| } |
| } |
| DCHECK(ack_frame_.packets.Empty() || |
| !peer_least_packet_awaiting_ack_.IsInitialized() || |
| ack_frame_.packets.Min() >= peer_least_packet_awaiting_ack_); |
| } |
| |
| void QuicReceivedPacketManager::MaybeUpdateAckTimeout( |
| bool should_last_packet_instigate_acks, |
| QuicPacketNumber last_received_packet_number, |
| QuicTime time_of_last_received_packet, |
| QuicTime now, |
| const RttStats* rtt_stats, |
| QuicTime::Delta delayed_ack_time) { |
| DCHECK(decide_when_to_send_acks_); |
| if (!ack_frame_updated_) { |
| // ACK frame has not been updated, nothing to do. |
| return; |
| } |
| |
| if (was_last_packet_missing_ && last_sent_largest_acked_.IsInitialized() && |
| last_received_packet_number < last_sent_largest_acked_) { |
| // Only ack immediately if an ACK frame was sent with a larger largest acked |
| // than the newly received packet number. |
| ack_timeout_ = now; |
| return; |
| } |
| |
| if (!should_last_packet_instigate_acks) { |
| return; |
| } |
| |
| ++num_retransmittable_packets_received_since_last_ack_sent_; |
| if (ack_mode_ != TCP_ACKING && |
| last_received_packet_number >= PeerFirstSendingPacketNumber() + |
| min_received_before_ack_decimation_) { |
| // Ack up to 10 packets at once unless ack decimation is unlimited. |
| if (!unlimited_ack_decimation_ && |
| num_retransmittable_packets_received_since_last_ack_sent_ >= |
| kMaxRetransmittablePacketsBeforeAck) { |
| ack_timeout_ = now; |
| return; |
| } |
| // Wait for the minimum of the ack decimation delay or the delayed ack time |
| // before sending an ack. |
| QuicTime::Delta ack_delay = std::min( |
| delayed_ack_time, rtt_stats->min_rtt() * ack_decimation_delay_); |
| if (fast_ack_after_quiescence_ && now - time_of_previous_received_packet_ > |
| rtt_stats->SmoothedOrInitialRtt()) { |
| // Ack the first packet out of queiscence faster, because QUIC does |
| // not pace the first few packets and commonly these may be handshake |
| // or TLP packets, which we'd like to acknowledge quickly. |
| ack_delay = QuicTime::Delta::FromMilliseconds(1); |
| } |
| MaybeUpdateAckTimeoutTo(now + ack_delay); |
| } else { |
| // Ack with a timer or every 2 packets by default. |
| if (num_retransmittable_packets_received_since_last_ack_sent_ >= |
| ack_frequency_before_ack_decimation_) { |
| ack_timeout_ = now; |
| } else if (fast_ack_after_quiescence_ && |
| (now - time_of_previous_received_packet_) > |
| rtt_stats->SmoothedOrInitialRtt()) { |
| // Ack the first packet out of queiscence faster, because QUIC does |
| // not pace the first few packets and commonly these may be handshake |
| // or TLP packets, which we'd like to acknowledge quickly. |
| MaybeUpdateAckTimeoutTo(now + QuicTime::Delta::FromMilliseconds(1)); |
| } else { |
| MaybeUpdateAckTimeoutTo(now + delayed_ack_time); |
| } |
| } |
| |
| // If there are new missing packets to report, send an ack immediately. |
| if (HasNewMissingPackets()) { |
| if (ack_mode_ == ACK_DECIMATION_WITH_REORDERING) { |
| // Wait the minimum of an eighth min_rtt and the existing ack time. |
| QuicTime ack_time = now + kShortAckDecimationDelay * rtt_stats->min_rtt(); |
| MaybeUpdateAckTimeoutTo(ack_time); |
| } else { |
| ack_timeout_ = now; |
| } |
| } |
| |
| if (fast_ack_after_quiescence_) { |
| time_of_previous_received_packet_ = time_of_last_received_packet; |
| } |
| } |
| |
| void QuicReceivedPacketManager::ResetAckStates() { |
| DCHECK(decide_when_to_send_acks_); |
| ack_frame_updated_ = false; |
| ack_timeout_ = QuicTime::Zero(); |
| num_retransmittable_packets_received_since_last_ack_sent_ = 0; |
| last_sent_largest_acked_ = LargestAcked(ack_frame_); |
| } |
| |
| void QuicReceivedPacketManager::MaybeUpdateAckTimeoutTo(QuicTime time) { |
| DCHECK(decide_when_to_send_acks_); |
| if (!ack_timeout_.IsInitialized() || ack_timeout_ > time) { |
| ack_timeout_ = time; |
| } |
| } |
| |
| bool QuicReceivedPacketManager::HasMissingPackets() const { |
| if (ack_frame_.packets.Empty()) { |
| return false; |
| } |
| if (ack_frame_.packets.NumIntervals() > 1) { |
| return true; |
| } |
| if (!GetQuicRestartFlag(quic_enable_accept_random_ipn)) { |
| return ack_frame_.packets.Min() > |
| (peer_least_packet_awaiting_ack_.IsInitialized() |
| ? peer_least_packet_awaiting_ack_ |
| : QuicPacketNumber(1)); |
| } |
| return peer_least_packet_awaiting_ack_.IsInitialized() && |
| ack_frame_.packets.Min() > peer_least_packet_awaiting_ack_; |
| } |
| |
| bool QuicReceivedPacketManager::HasNewMissingPackets() const { |
| return HasMissingPackets() && |
| ack_frame_.packets.LastIntervalLength() <= kMaxPacketsAfterNewMissing; |
| } |
| |
| bool QuicReceivedPacketManager::ack_frame_updated() const { |
| return ack_frame_updated_; |
| } |
| |
| QuicPacketNumber QuicReceivedPacketManager::GetLargestObserved() const { |
| return LargestAcked(ack_frame_); |
| } |
| |
| QuicPacketNumber QuicReceivedPacketManager::PeerFirstSendingPacketNumber() |
| const { |
| if (!GetQuicRestartFlag(quic_enable_accept_random_ipn)) { |
| return QuicPacketNumber(1); |
| } |
| if (!least_received_packet_number_.IsInitialized()) { |
| QUIC_BUG << "No packets have been received yet"; |
| return QuicPacketNumber(1); |
| } |
| return least_received_packet_number_; |
| } |
| |
| } // namespace quic |