Support reordering_threshold > 1. Protected by FLAGS_quic_reloadable_flag_quic_receive_ack_frequency. PiperOrigin-RevId: 777678089
diff --git a/quiche/quic/core/frames/quic_ack_frame.cc b/quiche/quic/core/frames/quic_ack_frame.cc index b2f7a58..b274672 100644 --- a/quiche/quic/core/frames/quic_ack_frame.cc +++ b/quiche/quic/core/frames/quic_ack_frame.cc
@@ -7,10 +7,9 @@ #include <ostream> #include <utility> -#include "quiche/quic/core/quic_constants.h" #include "quiche/quic/core/quic_interval.h" +#include "quiche/quic/core/quic_packet_number.h" #include "quiche/quic/platform/api/quic_bug_tracker.h" -#include "quiche/quic/platform/api/quic_flag_utils.h" namespace quic { @@ -150,6 +149,11 @@ return packet_number_intervals_.rend(); } +PacketNumberQueue::const_iterator PacketNumberQueue::LowerBound( + QuicPacketNumber packet_number) const { + return packet_number_intervals_.LowerBound(packet_number); +} + QuicPacketCount PacketNumberQueue::LastIntervalLength() const { QUICHE_DCHECK(!Empty()); return packet_number_intervals_.rbegin()->Length();
diff --git a/quiche/quic/core/frames/quic_ack_frame.h b/quiche/quic/core/frames/quic_ack_frame.h index bafc755..d4ccb66 100644 --- a/quiche/quic/core/frames/quic_ack_frame.h +++ b/quiche/quic/core/frames/quic_ack_frame.h
@@ -7,11 +7,10 @@ #include <ostream> -#include "quiche/quic/core/quic_interval.h" #include "quiche/quic/core/quic_interval_set.h" +#include "quiche/quic/core/quic_packet_number.h" #include "quiche/quic/core/quic_types.h" -#include "quiche/quic/platform/api/quic_export.h" -#include "quiche/quic/platform/api/quic_flags.h" +#include "quiche/common/platform/api/quiche_export.h" namespace quic { @@ -80,6 +79,9 @@ const_iterator end() const; const_reverse_iterator rbegin() const; const_reverse_iterator rend() const; + // Returns the iterator to the first interval that contains or is greater than + // |packet_number|. + const_iterator LowerBound(QuicPacketNumber packet_number) const; friend QUICHE_EXPORT std::ostream& operator<<(std::ostream& os, const PacketNumberQueue& q);
diff --git a/quiche/quic/core/quic_received_packet_manager.cc b/quiche/quic/core/quic_received_packet_manager.cc index 5e18cab..6bca5a9 100644 --- a/quiche/quic/core/quic_received_packet_manager.cc +++ b/quiche/quic/core/quic_received_packet_manager.cc
@@ -6,12 +6,15 @@ #include <algorithm> #include <limits> +#include <optional> #include <utility> #include "quiche/quic/core/congestion_control/rtt_stats.h" #include "quiche/quic/core/crypto/crypto_protocol.h" #include "quiche/quic/core/quic_config.h" #include "quiche/quic/core/quic_connection_stats.h" +#include "quiche/quic/core/quic_constants.h" +#include "quiche/quic/core/quic_packet_number.h" #include "quiche/quic/core/quic_time.h" #include "quiche/quic/core/quic_types.h" #include "quiche/quic/platform/api/quic_bug_tracker.h" @@ -292,9 +295,11 @@ return; } - // TODO(martinduke): If a missing packet is received, do we send it when - // reordering_threshold_ == 0? - if (was_last_packet_missing_ && last_sent_largest_acked_.IsInitialized() && + // Limiting this to reordering_threshold_ > 0 is not compliant with + // draft-ietf-quic-ack-frequency-11, but there is an issue to add this + // behavior. + if (reordering_threshold_ > 0 && was_last_packet_missing_ && + last_sent_largest_acked_.IsInitialized() && last_received_packet_number < last_sent_largest_acked_) { // Ack immediately if an ACK frame was sent with a larger largest acked than // the newly received packet number. @@ -321,9 +326,25 @@ return; } - if (reordering_threshold_ == 1 && HasNewMissingPackets()) { // Fast path. - ack_timeout_ = now; - return; + if (reordering_threshold_ == 1) { + // Default behavior, not updated by ACK_FREQUENCY. + if (HasNewMissingPackets()) { + ack_timeout_ = now; + return; + } + } else { + if (ack_frame_.packets.NumIntervals() == max_ack_ranges_ && + (!last_sent_largest_acked_.IsInitialized() || + last_sent_largest_acked_ < ack_frame_.packets.begin()->max() - 1)) { + // If the lowest ACK range has not yet been reported, and might be trimmed + // on the next packet arrival, send an ACK. + ack_timeout_ = now; + return; + } + if (ReorderingExceedsThreshold()) { + ack_timeout_ = now; + return; + } } const QuicTime updated_ack_time = std::max( @@ -360,6 +381,54 @@ ack_frame_.packets.LastIntervalLength() <= kMaxPacketsAfterNewMissing; } +bool QuicReceivedPacketManager::ReorderingExceedsThreshold() const { + if (reordering_threshold_ <= 1) { // flag is not enabled, or there is no + // threshold. + return false; + } + if (!HasMissingPackets() || + GetLargestObserved() < QuicPacketNumber(reordering_threshold_)) { + return false; + } + // Find the next missing packet. + QuicPacketNumber smallest_unreported_missing; + if (last_sent_largest_acked_.IsInitialized() && + last_sent_largest_acked_ >= QuicPacketNumber(reordering_threshold_)) { + smallest_unreported_missing = + last_sent_largest_acked_ - reordering_threshold_ + 1; + } + // All ACK ranges before peer_least_packet_awaiting_ack_ have already been + // deleted, so this is the lowest packet number that has receive state. + if (peer_least_packet_awaiting_ack_.IsInitialized() && + (!smallest_unreported_missing.IsInitialized() || + smallest_unreported_missing < peer_least_packet_awaiting_ack_)) { + smallest_unreported_missing = peer_least_packet_awaiting_ack_; + if (!least_unacked_plus_1_) { + ++smallest_unreported_missing; + } + } + if (smallest_unreported_missing.IsInitialized()) { + auto it = ack_frame_.packets.LowerBound(smallest_unreported_missing); + if (it == ack_frame_.packets.end()) { + QUIC_BUG(quic_bug_764939479) + << "Checking reordering with improper ACK state"; + return false; + } + if (it->Contains(smallest_unreported_missing)) { + smallest_unreported_missing = it->max(); + } + } else { + // No ACK has been sent. Since HasMissingPackets() is true, there must be at + // least two ranges. Per RFC9000, ignore the range from zero to the first + // observed packet. Smallest_unreported_missing is therefore the max of the + // first range. + QUICHE_DCHECK(ack_frame_.packets.NumIntervals() > 1); + smallest_unreported_missing = ack_frame_.packets.begin()->max(); + } + return smallest_unreported_missing <= + (GetLargestObserved() - reordering_threshold_); +} + bool QuicReceivedPacketManager::ack_frame_updated() const { return ack_frame_updated_; }
diff --git a/quiche/quic/core/quic_received_packet_manager.h b/quiche/quic/core/quic_received_packet_manager.h index 404d46d..221b16a 100644 --- a/quiche/quic/core/quic_received_packet_manager.h +++ b/quiche/quic/core/quic_received_packet_manager.h
@@ -11,6 +11,7 @@ #include "quiche/quic/core/frames/quic_ack_frequency_frame.h" #include "quiche/quic/core/quic_config.h" #include "quiche/quic/core/quic_constants.h" +#include "quiche/quic/core/quic_packet_number.h" #include "quiche/quic/core/quic_packets.h" #include "quiche/quic/core/quic_time.h" #include "quiche/quic/core/quic_types.h" @@ -86,6 +87,13 @@ // packets of the largest observed. virtual bool HasNewMissingPackets() const; + // Returns true if the lowest packet number beyond largest_acked_ is more + // than reordering_threshold_ behind largest_unacked. Used only when + // reordering_threshold_ > 1. + // TODO(martinduke): This code can be used for reordering_threshold_ == 1 + // as well, once we have full confidence in it. + bool ReorderingExceedsThreshold() const; + virtual bool ack_frame_updated() const; QuicPacketNumber GetLargestObserved() const; @@ -225,6 +233,9 @@ // should set the ack timeout to now. bool ack_now_ = false; + // Latch for the flag. + bool least_unacked_plus_1_ = GetQuicReloadableFlag(quic_least_unacked_plus_1); + // Last sent largest acked, which gets updated when ACK was successfully sent. QuicPacketNumber last_sent_largest_acked_;
diff --git a/quiche/quic/core/quic_received_packet_manager_test.cc b/quiche/quic/core/quic_received_packet_manager_test.cc index 97f00c5..352614b 100644 --- a/quiche/quic/core/quic_received_packet_manager_test.cc +++ b/quiche/quic/core/quic_received_packet_manager_test.cc
@@ -11,6 +11,7 @@ #include "quiche/quic/core/crypto/crypto_protocol.h" #include "quiche/quic/core/quic_connection_stats.h" #include "quiche/quic/core/quic_constants.h" +#include "quiche/quic/core/quic_packet_number.h" #include "quiche/quic/core/quic_time.h" #include "quiche/quic/core/quic_types.h" #include "quiche/quic/platform/api/quic_expect_bug.h" @@ -578,18 +579,18 @@ RecordPacketReceipt(3, clock_.ApproximateNow()); MaybeUpdateAckTimeout(kInstigateAck, 3); - // Ack, since missing packets are always acknowledged. - CheckAckTimeout(clock_.ApproximateNow()); - - RecordPacketReceipt(7, clock_.ApproximateNow()); - MaybeUpdateAckTimeout(kInstigateAck, 10); - // No ack, as the frame says to ignore ordering. + // Don't ack as ignore_order is set by AckFrequencyFrame. CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime); - RecordPacketReceipt(1, clock_.ApproximateNow()); - MaybeUpdateAckTimeout(kInstigateAck, 11); - // It's the second packet in a row, ack it. + RecordPacketReceipt(2, clock_.ApproximateNow()); + MaybeUpdateAckTimeout(kInstigateAck, 2); + // Immediate ack is sent as this is the 2nd packet of every two packets. CheckAckTimeout(clock_.ApproximateNow()); + + RecordPacketReceipt(1, clock_.ApproximateNow()); + MaybeUpdateAckTimeout(kInstigateAck, 1); + // Don't ack as ignore_order is set by AckFrequencyFrame. + CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime); } TEST_F(QuicReceivedPacketManagerTest, @@ -627,6 +628,100 @@ } TEST_F(QuicReceivedPacketManagerTest, + AckFrequencyFrameChangesReorderingThreshold) { + EXPECT_FALSE(HasPendingAck()); + QuicConfig config; + received_manager_.SetFromConfig(config, Perspective::IS_CLIENT); + + QuicAckFrequencyFrame frame; + frame.sequence_number = 0; + frame.requested_max_ack_delay = kDelayedAckTime; + frame.ack_eliciting_threshold = 10; // No non-reordering acks. + frame.reordering_threshold = 2; + received_manager_.OnAckFrequencyFrame(frame); + RecordPacketReceipt(0, clock_.ApproximateNow()); + MaybeUpdateAckTimeout(kInstigateAck, 0); + CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime); + // No ack after gap. + RecordPacketReceipt(2, clock_.ApproximateNow()); + MaybeUpdateAckTimeout(kInstigateAck, 2); + CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime); + // Hit the reordering threshold, send ACK. + RecordPacketReceipt(3, clock_.ApproximateNow()); + MaybeUpdateAckTimeout(kInstigateAck, 3); + CheckAckTimeout(clock_.ApproximateNow()); + // Already reported, do not ack again. + RecordPacketReceipt(4, clock_.ApproximateNow()); + MaybeUpdateAckTimeout(kInstigateAck, 4); + CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime); + // Filling the hole is acked. + RecordPacketReceipt(1, clock_.ApproximateNow()); + MaybeUpdateAckTimeout(kInstigateAck, 1); + CheckAckTimeout(clock_.ApproximateNow()); +} + +// There is a different code path if there is no ACK range before the missing +// packet. +TEST_F(QuicReceivedPacketManagerTest, ReorderingThresholdNoRangeBeforeMissing) { + EXPECT_FALSE(HasPendingAck()); + QuicConfig config; + received_manager_.SetFromConfig(config, Perspective::IS_CLIENT); + + QuicAckFrequencyFrame frame; + frame.sequence_number = 0; + frame.requested_max_ack_delay = kDelayedAckTime; + frame.ack_eliciting_threshold = 10; // No non-reordering acks. + frame.reordering_threshold = 2; + received_manager_.OnAckFrequencyFrame(frame); + if (GetQuicReloadableFlag(quic_least_unacked_plus_1)) { + received_manager_.DontWaitForPacketsBefore(QuicPacketNumber(2)); + } else { + received_manager_.DontWaitForPacketsBefore(QuicPacketNumber(1)); + } + // No ack after gap. + RecordPacketReceipt(3, clock_.ApproximateNow()); + MaybeUpdateAckTimeout(kInstigateAck, 3); + CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime); + // Hit the reordering threshold, send ACK. + RecordPacketReceipt(4, clock_.ApproximateNow()); + MaybeUpdateAckTimeout(kInstigateAck, 4); + CheckAckTimeout(clock_.ApproximateNow()); + // Second packet ignored. + RecordPacketReceipt(5, clock_.ApproximateNow()); + MaybeUpdateAckTimeout(kInstigateAck, 5); + CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime); + // Filling the hole is acked. + RecordPacketReceipt(2, clock_.ApproximateNow()); + MaybeUpdateAckTimeout(kInstigateAck, 2); + CheckAckTimeout(clock_.ApproximateNow()); +} + +TEST_F(QuicReceivedPacketManagerTest, MaxAckRangesPromptsAck) { + EXPECT_FALSE(HasPendingAck()); + QuicConfig config; + received_manager_.SetFromConfig(config, Perspective::IS_CLIENT); + + QuicAckFrequencyFrame frame; + frame.sequence_number = 0; + frame.requested_max_ack_delay = kDelayedAckTime; + frame.ack_eliciting_threshold = 1000; + frame.reordering_threshold = 1000; + received_manager_.OnAckFrequencyFrame(frame); + const int max_ack_ranges = 10; + received_manager_.set_max_ack_ranges(max_ack_ranges); + // create ack ranges + for (int i = 0; i < (max_ack_ranges - 1); ++i) { + RecordPacketReceipt(2 * i, clock_.ApproximateNow()); + MaybeUpdateAckTimeout(kInstigateAck, 2 * i); + CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime); + } + // Send the max, forcing an ack. + RecordPacketReceipt(max_ack_ranges * 2, clock_.ApproximateNow()); + MaybeUpdateAckTimeout(kInstigateAck, 2 * max_ack_ranges - 1); + CheckAckTimeout(clock_.ApproximateNow()); +} + +TEST_F(QuicReceivedPacketManagerTest, AckDecimationDisabledWhenAckFrequencyFrameIsReceived) { EXPECT_FALSE(HasPendingAck());