gfe-relnote: In QUIC bandwidth sampler, only remove packets when RemoveObsoletePackets is called. Protected by --gfe2_reloadable_flag_quic_bw_sampler_remove_packets_once_per_congestion_event. PiperOrigin-RevId: 285110271 Change-Id: I27567839a190136c03fef54a66261ab34d8c1f82
diff --git a/quic/core/congestion_control/bandwidth_sampler.cc b/quic/core/congestion_control/bandwidth_sampler.cc index cc90cb0..a4cdc33 100644 --- a/quic/core/congestion_control/bandwidth_sampler.cc +++ b/quic/core/congestion_control/bandwidth_sampler.cc
@@ -64,7 +64,12 @@ max_tracked_packets_(GetQuicFlag(FLAGS_quic_max_tracked_packet_count)), unacked_packet_map_(unacked_packet_map), max_ack_height_tracker_(max_height_tracker_window_length), - total_bytes_acked_after_last_ack_event_(0) {} + total_bytes_acked_after_last_ack_event_(0) { + if (remove_packets_once_per_congestion_event_) { + QUIC_RELOADABLE_FLAG_COUNT( + quic_bw_sampler_remove_packets_once_per_congestion_event); + } +} BandwidthSampler::~BandwidthSampler() {} @@ -115,8 +120,8 @@ } } - bool success = - connection_state_map_.Emplace(packet_number, sent_time, bytes, *this); + bool success = connection_state_map_.Emplace(packet_number, sent_time, bytes, + bytes_in_flight, *this); QUIC_BUG_IF(!success) << "BandwidthSampler failed to insert the packet " "into the map, most likely because it's already " "in it."; @@ -149,7 +154,9 @@ } BandwidthSample sample = OnPacketAcknowledgedInner(ack_time, packet_number, *sent_packet_pointer); - connection_state_map_.Remove(packet_number); + if (!remove_packets_once_per_congestion_event_) { + connection_state_map_.Remove(packet_number); + } return sample; } @@ -220,16 +227,27 @@ return sample; } -SendTimeState BandwidthSampler::OnPacketLost(QuicPacketNumber packet_number) { +SendTimeState BandwidthSampler::OnPacketLost(QuicPacketNumber packet_number, + QuicPacketLength bytes_lost) { // TODO(vasilvv): see the comment for the case of missing packets in // BandwidthSampler::OnPacketAcknowledged on why this does not raise a // QUIC_BUG when removal fails. SendTimeState send_time_state; - send_time_state.is_valid = connection_state_map_.Remove( - packet_number, [&](const ConnectionStateOnSentPacket& sent_packet) { - total_bytes_lost_ += sent_packet.size; - SentPacketToSendTimeState(sent_packet, &send_time_state); - }); + + if (remove_packets_once_per_congestion_event_) { + total_bytes_lost_ += bytes_lost; + ConnectionStateOnSentPacket* sent_packet_pointer = + connection_state_map_.GetEntry(packet_number); + if (sent_packet_pointer != nullptr) { + SentPacketToSendTimeState(*sent_packet_pointer, &send_time_state); + } + } else { + send_time_state.is_valid = connection_state_map_.Remove( + packet_number, [&](const ConnectionStateOnSentPacket& sent_packet) { + total_bytes_lost_ += sent_packet.size; + SentPacketToSendTimeState(sent_packet, &send_time_state); + }); + } return send_time_state; } @@ -251,6 +269,10 @@ // QuicSentPacketManager::RetransmitCryptoPackets retransmits a crypto packet, // the packet is removed from QuicUnackedPacketMap's inflight, but is not // marked as acked or lost in the BandwidthSampler. + if (remove_packets_once_per_congestion_event_) { + connection_state_map_.RemoveUpTo(least_unacked); + return; + } while (!connection_state_map_.IsEmpty() && connection_state_map_.first_packet() < least_unacked) { connection_state_map_.Remove(
diff --git a/quic/core/congestion_control/bandwidth_sampler.h b/quic/core/congestion_control/bandwidth_sampler.h index 51f5e87..c7c9862 100644 --- a/quic/core/congestion_control/bandwidth_sampler.h +++ b/quic/core/congestion_control/bandwidth_sampler.h
@@ -29,17 +29,20 @@ is_app_limited(false), total_bytes_sent(0), total_bytes_acked(0), - total_bytes_lost(0) {} + total_bytes_lost(0), + bytes_in_flight(0) {} SendTimeState(bool is_app_limited, QuicByteCount total_bytes_sent, QuicByteCount total_bytes_acked, - QuicByteCount total_bytes_lost) + QuicByteCount total_bytes_lost, + QuicByteCount bytes_in_flight) : is_valid(true), is_app_limited(is_app_limited), total_bytes_sent(total_bytes_sent), total_bytes_acked(total_bytes_acked), - total_bytes_lost(total_bytes_lost) {} + total_bytes_lost(total_bytes_lost), + bytes_in_flight(bytes_in_flight) {} SendTimeState(const SendTimeState& other) = default; @@ -60,6 +63,11 @@ // Total number of lost bytes at the time the packet was sent. QuicByteCount total_bytes_lost; + + // Total number of inflight bytes right before the time the packet was sent. + // It should be equal to |total_bytes_sent| minus the sum of + // |total_bytes_acked|, |total_bytes_lost| and total neutered bytes. + QuicByteCount bytes_in_flight; }; struct QUIC_EXPORT_PRIVATE BandwidthSample { @@ -148,7 +156,8 @@ // Informs the sampler that a packet is considered lost and it should no // longer keep track of it. - virtual SendTimeState OnPacketLost(QuicPacketNumber packet_number) = 0; + virtual SendTimeState OnPacketLost(QuicPacketNumber packet_number, + QuicPacketLength bytes_lost) = 0; // Informs the sampler that the connection is currently app-limited, causing // the sampler to enter the app-limited phase. The phase will expire by @@ -264,7 +273,8 @@ QuicPacketNumber packet_number) override; QuicByteCount OnAckEventEnd(QuicBandwidth bandwidth_estimate, QuicRoundTripCount round_trip_count); - SendTimeState OnPacketLost(QuicPacketNumber packet_number) override; + SendTimeState OnPacketLost(QuicPacketNumber packet_number, + QuicPacketLength bytes_lost) override; void OnAppLimited() override; @@ -293,6 +303,10 @@ max_ack_height_tracker_.Reset(new_height, new_time); } + bool remove_packets_once_per_congestion_event() const { + return remove_packets_once_per_congestion_event_; + } + private: friend class test::BandwidthSamplerPeer; @@ -325,8 +339,10 @@ // Snapshot constructor. Records the current state of the bandwidth // sampler. + // |prior_bytes_in_flight| is the bytes in flight before the packet is sent. ConnectionStateOnSentPacket(QuicTime sent_time, QuicByteCount size, + QuicByteCount prior_bytes_in_flight, const BandwidthSampler& sampler) : sent_time(sent_time), size(size), @@ -337,7 +353,10 @@ send_time_state(sampler.is_app_limited_, sampler.total_bytes_sent_, sampler.total_bytes_acked_, - sampler.total_bytes_lost_) {} + sampler.total_bytes_lost_, + sampler.remove_packets_once_per_congestion_event() + ? prior_bytes_in_flight + : 0) {} // Default constructor. Required to put this structure into // PacketNumberIndexedQueue. @@ -406,6 +425,10 @@ MaxAckHeightTracker max_ack_height_tracker_; QuicByteCount total_bytes_acked_after_last_ack_event_; + + // Latched value of quic_bw_sampler_remove_packets_once_per_congestion_event. + const bool remove_packets_once_per_congestion_event_ = GetQuicReloadableFlag( + quic_bw_sampler_remove_packets_once_per_congestion_event); }; } // namespace quic
diff --git a/quic/core/congestion_control/bandwidth_sampler_test.cc b/quic/core/congestion_control/bandwidth_sampler_test.cc index 59318a9..a2b858f 100644 --- a/quic/core/congestion_control/bandwidth_sampler_test.cc +++ b/quic/core/congestion_control/bandwidth_sampler_test.cc
@@ -85,7 +85,7 @@ sampler_, QuicPacketNumber(packet_number)); bytes_in_flight_ -= size; SendTimeState send_time_state = - sampler_.OnPacketLost(QuicPacketNumber(packet_number)); + sampler_.OnPacketLost(QuicPacketNumber(packet_number), size); EXPECT_TRUE(send_time_state.is_valid); return send_time_state; } @@ -133,6 +133,9 @@ QuicBandwidth current_sample = AckPacket(i); EXPECT_EQ(expected_bandwidth, current_sample); } + if (sampler_.remove_packets_once_per_congestion_event()) { + sampler_.RemoveObsoletePackets(QuicPacketNumber(25)); + } EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); EXPECT_EQ(0u, bytes_in_flight_); } @@ -211,6 +214,9 @@ EXPECT_EQ(expected_bandwidth, last_bandwidth); clock_.AdvanceTime(time_between_packets); } + if (sampler_.remove_packets_once_per_congestion_event()) { + sampler_.RemoveObsoletePackets(QuicPacketNumber(41)); + } EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); EXPECT_EQ(0u, bytes_in_flight_); } @@ -251,6 +257,9 @@ } clock_.AdvanceTime(time_between_packets); } + if (sampler_.remove_packets_once_per_congestion_event()) { + sampler_.RemoveObsoletePackets(QuicPacketNumber(41)); + } EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); EXPECT_EQ(0u, bytes_in_flight_); } @@ -299,6 +308,9 @@ clock_.AdvanceTime(time_between_packets); } + if (sampler_.remove_packets_once_per_congestion_event()) { + sampler_.RemoveObsoletePackets(QuicPacketNumber(41)); + } // Since only congestion controlled packets are entered into the map, it has // to be empty at this point. EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); @@ -327,6 +339,9 @@ clock_.AdvanceTime(ridiculously_small_time_delta); } EXPECT_EQ(expected_bandwidth, last_bandwidth); + if (sampler_.remove_packets_once_per_congestion_event()) { + sampler_.RemoveObsoletePackets(QuicPacketNumber(41)); + } EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); EXPECT_EQ(0u, bytes_in_flight_); } @@ -356,6 +371,9 @@ EXPECT_EQ(expected_bandwidth, last_bandwidth); clock_.AdvanceTime(time_between_packets); } + if (sampler_.remove_packets_once_per_congestion_event()) { + sampler_.RemoveObsoletePackets(QuicPacketNumber(61)); + } EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); EXPECT_EQ(0u, bytes_in_flight_); } @@ -406,6 +424,9 @@ clock_.AdvanceTime(time_between_packets); } + if (sampler_.remove_packets_once_per_congestion_event()) { + sampler_.RemoveObsoletePackets(QuicPacketNumber(81)); + } EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); EXPECT_EQ(0u, bytes_in_flight_); } @@ -458,9 +479,15 @@ EXPECT_EQ(5u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); sampler_.RemoveObsoletePackets(QuicPacketNumber(4)); EXPECT_EQ(2u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); - sampler_.OnPacketLost(QuicPacketNumber(4)); + sampler_.OnPacketLost(QuicPacketNumber(4), kRegularPacketSize); + if (sampler_.remove_packets_once_per_congestion_event()) { + sampler_.RemoveObsoletePackets(QuicPacketNumber(5)); + } EXPECT_EQ(1u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); AckPacket(5); + if (sampler_.remove_packets_once_per_congestion_event()) { + sampler_.RemoveObsoletePackets(QuicPacketNumber(6)); + } EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_)); }
diff --git a/quic/core/congestion_control/bbr2_misc.cc b/quic/core/congestion_control/bbr2_misc.cc index a527417..8b8e663 100644 --- a/quic/core/congestion_control/bbr2_misc.cc +++ b/quic/core/congestion_control/bbr2_misc.cc
@@ -156,18 +156,35 @@ } for (const LostPacket& packet : lost_packets) { - const SendTimeState send_time_state = - bandwidth_sampler_.OnPacketLost(packet.packet_number); + const SendTimeState send_time_state = bandwidth_sampler_.OnPacketLost( + packet.packet_number, packet.bytes_lost); if (send_time_state.is_valid) { congestion_event->last_lost_sample = {packet.packet_number, send_time_state}; } } - congestion_event->bytes_in_flight = bytes_in_flight(); + if (!bandwidth_sampler_.remove_packets_once_per_congestion_event()) { + congestion_event->bytes_in_flight = bytes_in_flight(); + } congestion_event->bytes_acked = total_bytes_acked() - prior_bytes_acked; congestion_event->bytes_lost = total_bytes_lost() - prior_bytes_lost; + if (bandwidth_sampler_.remove_packets_once_per_congestion_event()) { + if (congestion_event->prior_bytes_in_flight >= + congestion_event->bytes_acked + congestion_event->bytes_lost) { + congestion_event->bytes_in_flight = + congestion_event->prior_bytes_in_flight - + congestion_event->bytes_acked - congestion_event->bytes_lost; + } else { + QUIC_LOG_FIRST_N(ERROR, 1) + << "prior_bytes_in_flight:" << congestion_event->prior_bytes_in_flight + << " is smaller than the sum of bytes_acked:" + << congestion_event->bytes_acked + << " and bytes_lost:" << congestion_event->bytes_lost; + congestion_event->bytes_in_flight = 0; + } + } bytes_lost_in_round_ += congestion_event->bytes_lost; bandwidth_sampler_.OnAckEventEnd(BandwidthEstimate(), RoundTripCount());
diff --git a/quic/core/congestion_control/bbr2_misc.h b/quic/core/congestion_control/bbr2_misc.h index 8f08a58..760f4c9 100644 --- a/quic/core/congestion_control/bbr2_misc.h +++ b/quic/core/congestion_control/bbr2_misc.h
@@ -228,6 +228,9 @@ // The congestion window prior to the processing of the ack/loss events. QuicByteCount prior_cwnd; + // Total bytes inflight before the processing of the ack/loss events. + QuicByteCount prior_bytes_in_flight = 0; + // Total bytes inflight after the processing of the ack/loss events. QuicByteCount bytes_in_flight = 0; @@ -367,6 +370,7 @@ } QuicByteCount bytes_in_flight() const { + DCHECK(!bandwidth_sampler_.remove_packets_once_per_congestion_event()); return total_bytes_sent() - total_bytes_acked() - total_bytes_lost(); } @@ -500,6 +504,9 @@ QUIC_EXPORT_PRIVATE inline QuicByteCount BytesInFlight( const SendTimeState& send_state) { DCHECK(send_state.is_valid); + if (send_state.bytes_in_flight != 0) { + return send_state.bytes_in_flight; + } return send_state.total_bytes_sent - send_state.total_bytes_acked - send_state.total_bytes_lost; }
diff --git a/quic/core/congestion_control/bbr2_sender.cc b/quic/core/congestion_control/bbr2_sender.cc index 31bf299..3e707f3 100644 --- a/quic/core/congestion_control/bbr2_sender.cc +++ b/quic/core/congestion_control/bbr2_sender.cc
@@ -150,6 +150,7 @@ << " prior_cwnd:" << cwnd_ << " @ " << event_time; Bbr2CongestionEvent congestion_event; congestion_event.prior_cwnd = cwnd_; + congestion_event.prior_bytes_in_flight = prior_in_flight; congestion_event.is_probing_for_bandwidth = BBR2_MODE_DISPATCH(IsProbingForBandwidth()); @@ -193,7 +194,7 @@ << this << " END CongestionEvent(acked:" << acked_packets << ", lost:" << lost_packets.size() << ") " << ", Mode:" << mode_ << ", RttCount:" << model_.RoundTripCount() - << ", BytesInFlight:" << model_.bytes_in_flight() + << ", BytesInFlight:" << congestion_event.bytes_in_flight << ", PacingRate:" << PacingRate(0) << ", CWND:" << GetCongestionWindow() << ", PacingGain:" << model_.pacing_gain() << ", CwndGain:" << model_.cwnd_gain() @@ -274,7 +275,7 @@ HasRetransmittableData is_retransmittable) { QUIC_DVLOG(3) << this << " OnPacketSent: pkn:" << packet_number << ", bytes:" << bytes << ", cwnd:" << cwnd_ - << ", inflight:" << model_.bytes_in_flight() + bytes + << ", inflight:" << bytes_in_flight + bytes << ", total_sent:" << model_.total_bytes_sent() + bytes << ", total_acked:" << model_.total_bytes_acked() << ", total_lost:" << model_.total_bytes_lost() << " @ " @@ -327,7 +328,7 @@ if (flexible_app_limited_) { const bool is_pipe_sufficiently_full = IsPipeSufficientlyFull(); QUIC_DVLOG(3) << this << " CWND: " << GetCongestionWindow() - << ", inflight: " << model_.bytes_in_flight() + << ", inflight: " << unacked_packets_->bytes_in_flight() << ", pacing_rate: " << PacingRate(0) << ", flexible_app_limited_: true, ShouldSendProbingPacket: " << !is_pipe_sufficiently_full; @@ -338,20 +339,20 @@ } bool Bbr2Sender::IsPipeSufficientlyFull() const { + QuicByteCount bytes_in_flight = unacked_packets_->bytes_in_flight(); // See if we need more bytes in flight to see more bandwidth. if (mode_ == Bbr2Mode::STARTUP) { // STARTUP exits if it doesn't observe a 25% bandwidth increase, so the CWND // must be more than 25% above the target. - return model_.bytes_in_flight() >= GetTargetCongestionWindow(1.5); + return bytes_in_flight >= GetTargetCongestionWindow(1.5); } if (model_.pacing_gain() > 1) { // Super-unity PROBE_BW doesn't exit until 1.25 * BDP is achieved. - return model_.bytes_in_flight() >= - GetTargetCongestionWindow(model_.pacing_gain()); + return bytes_in_flight >= GetTargetCongestionWindow(model_.pacing_gain()); } // If bytes_in_flight are above the target congestion window, it should be // possible to observe the same or more bandwidth if it's available. - return model_.bytes_in_flight() >= GetTargetCongestionWindow(1.1); + return bytes_in_flight >= GetTargetCongestionWindow(1.1); } std::string Bbr2Sender::GetDebugState() const {
diff --git a/quic/core/congestion_control/bbr_sender.cc b/quic/core/congestion_control/bbr_sender.cc index 8441455..4973744 100644 --- a/quic/core/congestion_control/bbr_sender.cc +++ b/quic/core/congestion_control/bbr_sender.cc
@@ -495,7 +495,7 @@ void BbrSender::DiscardLostPackets(const LostPacketVector& lost_packets) { for (const LostPacket& packet : lost_packets) { - sampler_.OnPacketLost(packet.packet_number); + sampler_.OnPacketLost(packet.packet_number, packet.bytes_lost); if (mode_ == STARTUP) { if (stats_) { ++stats_->slowstart_packets_lost;
diff --git a/quic/core/packet_number_indexed_queue.h b/quic/core/packet_number_indexed_queue.h index 470a58c..269858f 100644 --- a/quic/core/packet_number_indexed_queue.h +++ b/quic/core/packet_number_indexed_queue.h
@@ -34,6 +34,8 @@ // just two entries will cause it to consume all of the memory available. // Because of that, it is not a general-purpose container and should not be used // as one. +// TODO(wub): Update the comments when deprecating +// --quic_bw_sampler_remove_packets_once_per_congestion_event. template <typename T> class QUIC_NO_EXPORT PacketNumberIndexedQueue { public: @@ -60,6 +62,9 @@ template <typename Function> bool Remove(QuicPacketNumber packet_number, Function f); + // Remove up to, but not including |packet_number|. + void RemoveUpTo(QuicPacketNumber packet_number); + bool IsEmpty() const { return number_of_present_entries_ == 0; } // Returns the number of entries in the queue. @@ -87,6 +92,9 @@ private: // Wrapper around T used to mark whether the entry is actually in the map. struct QUIC_NO_EXPORT EntryWrapper : T { + // NOTE(wub): When quic_bw_sampler_remove_packets_once_per_congestion_event + // is enabled, |present| is false if and only if this is a placeholder entry + // for holes in the parent's |entries|. bool present; EntryWrapper() : present(false) {} @@ -106,6 +114,9 @@ } QuicDeque<EntryWrapper> entries_; + // NOTE(wub): When --quic_bw_sampler_remove_packets_once_per_congestion_event + // is enabled, |number_of_present_entries_| only represents number of holes, + // which does not include number of acked or lost packets. size_t number_of_present_entries_; QuicPacketNumber first_packet_; }; @@ -189,6 +200,21 @@ } template <typename T> +void PacketNumberIndexedQueue<T>::RemoveUpTo(QuicPacketNumber packet_number) { + while (!entries_.empty() && first_packet_.IsInitialized() && + first_packet_ < packet_number) { + if (entries_.front().present) { + number_of_present_entries_--; + } + entries_.pop_front(); + first_packet_++; + } + if (entries_.empty()) { + first_packet_.Clear(); + } +} + +template <typename T> void PacketNumberIndexedQueue<T>::Cleanup() { while (!entries_.empty() && !entries_.front().present) { entries_.pop_front();
diff --git a/quic/core/packet_number_indexed_queue_test.cc b/quic/core/packet_number_indexed_queue_test.cc index c293133..e23df99 100644 --- a/quic/core/packet_number_indexed_queue_test.cc +++ b/quic/core/packet_number_indexed_queue_test.cc
@@ -8,6 +8,7 @@ #include <map> #include <string> +#include "net/third_party/quiche/src/quic/core/quic_packet_number.h" #include "net/third_party/quiche/src/quic/platform/api/quic_test.h" namespace quic { @@ -167,6 +168,29 @@ ASSERT_FALSE(queue_.Remove(QuicPacketNumber(1001))); } +TEST_F(PacketNumberIndexedQueueTest, RemoveUpTo) { + queue_.Emplace(QuicPacketNumber(1001), "one"); + queue_.Emplace(QuicPacketNumber(2001), "two"); + EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet()); + EXPECT_EQ(2u, queue_.number_of_present_entries()); + + queue_.RemoveUpTo(QuicPacketNumber(1001)); + EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet()); + EXPECT_EQ(2u, queue_.number_of_present_entries()); + + queue_.RemoveUpTo(QuicPacketNumber(1100)); + EXPECT_EQ(QuicPacketNumber(1100u), queue_.first_packet()); + EXPECT_EQ(1u, queue_.number_of_present_entries()); + + queue_.RemoveUpTo(QuicPacketNumber(2001)); + EXPECT_EQ(QuicPacketNumber(2001u), queue_.first_packet()); + EXPECT_EQ(1u, queue_.number_of_present_entries()); + + queue_.RemoveUpTo(QuicPacketNumber(2002)); + EXPECT_FALSE(queue_.first_packet().IsInitialized()); + EXPECT_EQ(0u, queue_.number_of_present_entries()); +} + TEST_F(PacketNumberIndexedQueueTest, ConstGetter) { queue_.Emplace(QuicPacketNumber(1001), "one"); const auto& const_queue = queue_;