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());
