Internal QUICHE change PiperOrigin-RevId: 340865909 Change-Id: I149591b5a141c48bb866c3e80b70cc2f1171259d
diff --git a/quic/core/quic_connection.cc b/quic/core/quic_connection.cc index a07314d..845e078 100644 --- a/quic/core/quic_connection.cc +++ b/quic/core/quic_connection.cc
@@ -382,6 +382,8 @@ // TODO(ianswett): Supply the NetworkChangeVisitor as a constructor argument // and make it required non-null, because it's always used. sent_packet_manager_.SetNetworkChangeVisitor(this); + sent_packet_manager_.ReserveUnackedPacketsInitialCapacity( + GetUnackedMapInitialCapacity()); if (GetQuicRestartFlag(quic_offload_pacing_to_usps2)) { sent_packet_manager_.SetPacingAlarmGranularity(QuicTime::Delta::Zero()); release_time_into_future_ =
diff --git a/quic/core/quic_connection.h b/quic/core/quic_connection.h index ee477a9..818c093 100644 --- a/quic/core/quic_connection.h +++ b/quic/core/quic_connection.h
@@ -38,6 +38,7 @@ #include "net/third_party/quiche/src/quic/core/quic_circular_deque.h" #include "net/third_party/quiche/src/quic/core/quic_connection_id.h" #include "net/third_party/quiche/src/quic/core/quic_connection_stats.h" +#include "net/third_party/quiche/src/quic/core/quic_constants.h" #include "net/third_party/quiche/src/quic/core/quic_framer.h" #include "net/third_party/quiche/src/quic/core/quic_idle_network_detector.h" #include "net/third_party/quiche/src/quic/core/quic_mtu_discovery.h" @@ -949,6 +950,10 @@ // connection ID lengths do not change. QuicPacketLength GetGuaranteedLargestMessagePayload() const; + virtual int GetUnackedMapInitialCapacity() const { + return kDefaultUnackedPacketsInitialCapacity; + } + // Returns the id of the cipher last used for decrypting packets. uint32_t cipher_id() const;
diff --git a/quic/core/quic_constants.h b/quic/core/quic_constants.h index 62c0e77..4cd6ba5 100644 --- a/quic/core/quic_constants.h +++ b/quic/core/quic_constants.h
@@ -104,6 +104,10 @@ // https://tools.ietf.org/html/draft-ietf-quic-transport-25#section-17.2.5 const size_t kRetryIntegrityTagLength = 16; +// By default, UnackedPacketsMap allocates buffer of 64 after the first packet +// is added. +const int kDefaultUnackedPacketsInitialCapacity = 64; + // Signifies that the QuicPacket will contain version of the protocol. const bool kIncludeVersion = true; // Signifies that the QuicPacket will include a diversification nonce.
diff --git a/quic/core/quic_flags_list.h b/quic/core/quic_flags_list.h index 90deddc..42c56a4 100644 --- a/quic/core/quic_flags_list.h +++ b/quic/core/quic_flags_list.h
@@ -73,6 +73,7 @@ QUIC_FLAG(FLAGS_quic_reloadable_flag_quic_testonly_default_false, false) QUIC_FLAG(FLAGS_quic_reloadable_flag_quic_testonly_default_true, true) QUIC_FLAG(FLAGS_quic_reloadable_flag_quic_unified_iw_options, false) +QUIC_FLAG(FLAGS_quic_reloadable_flag_quic_use_circular_deque_for_unacked_packets, false) QUIC_FLAG(FLAGS_quic_reloadable_flag_quic_use_encryption_level_context, false) QUIC_FLAG(FLAGS_quic_reloadable_flag_quic_use_fast_huffman_encoder, true) QUIC_FLAG(FLAGS_quic_reloadable_flag_quic_use_write_or_buffer_data_at_level, false)
diff --git a/quic/core/quic_sent_packet_manager.cc b/quic/core/quic_sent_packet_manager.cc index ace8d8d..592faa1 100644 --- a/quic/core/quic_sent_packet_manager.cc +++ b/quic/core/quic_sent_packet_manager.cc
@@ -16,6 +16,7 @@ #include "net/third_party/quiche/src/quic/core/quic_connection_stats.h" #include "net/third_party/quiche/src/quic/core/quic_constants.h" #include "net/third_party/quiche/src/quic/core/quic_packet_number.h" +#include "net/third_party/quiche/src/quic/core/quic_transmission_info.h" #include "net/third_party/quiche/src/quic/core/quic_types.h" #include "net/third_party/quiche/src/quic/core/quic_utils.h" #include "net/third_party/quiche/src/quic/platform/api/quic_bug_tracker.h" @@ -476,17 +477,40 @@ } void QuicSentPacketManager::MarkZeroRttPacketsForRetransmission() { - QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); - for (QuicUnackedPacketMap::iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++packet_number) { - if (it->encryption_level == ENCRYPTION_ZERO_RTT) { - if (it->in_flight) { - // Remove 0-RTT packets and packets of the wrong version from flight, - // because neither can be processed by the peer. - unacked_packets_.RemoveFromInFlight(&*it); + if (unacked_packets_.use_circular_deque()) { + if (unacked_packets_.empty()) { + return; + } + QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); + QuicPacketNumber largest_sent_packet = + unacked_packets_.largest_sent_packet(); + for (; packet_number <= largest_sent_packet; ++packet_number) { + QuicTransmissionInfo* transmission_info = + unacked_packets_.GetMutableTransmissionInfo(packet_number); + if (transmission_info->encryption_level == ENCRYPTION_ZERO_RTT) { + if (transmission_info->in_flight) { + // Remove 0-RTT packets and packets of the wrong version from flight, + // because neither can be processed by the peer. + unacked_packets_.RemoveFromInFlight(transmission_info); + } + if (unacked_packets_.HasRetransmittableFrames(*transmission_info)) { + MarkForRetransmission(packet_number, ALL_ZERO_RTT_RETRANSMISSION); + } } - if (unacked_packets_.HasRetransmittableFrames(*it)) { - MarkForRetransmission(packet_number, ALL_ZERO_RTT_RETRANSMISSION); + } + } else { + QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); + for (QuicUnackedPacketMap::iterator it = unacked_packets_.begin(); + it != unacked_packets_.end(); ++it, ++packet_number) { + if (it->encryption_level == ENCRYPTION_ZERO_RTT) { + if (it->in_flight) { + // Remove 0-RTT packets and packets of the wrong version from + // flight, because neither can be processed by the peer. + unacked_packets_.RemoveFromInFlight(&*it); + } + if (unacked_packets_.HasRetransmittableFrames(*it)) { + MarkForRetransmission(packet_number, ALL_ZERO_RTT_RETRANSMISSION); + } } } } @@ -607,6 +631,11 @@ HandleRetransmission(transmission_type, transmission_info); + // Get the latest transmission_info here as it can be invalidated after + // HandleRetransmission adding new sent packets into unacked_packets_. + transmission_info = + unacked_packets_.GetMutableTransmissionInfo(packet_number); + // Update packet state according to transmission type. transmission_info->state = QuicUtils::RetransmissionTypeToPacketState(transmission_type); @@ -850,19 +879,43 @@ DCHECK_EQ(HANDSHAKE_MODE, GetRetransmissionMode()); ++consecutive_crypto_retransmission_count_; bool packet_retransmitted = false; - QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); std::vector<QuicPacketNumber> crypto_retransmissions; - for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++packet_number) { - // Only retransmit frames which are in flight, and therefore have been sent. - if (!it->in_flight || it->state != OUTSTANDING || - !it->has_crypto_handshake || - !unacked_packets_.HasRetransmittableFrames(*it)) { - continue; + if (unacked_packets_.use_circular_deque()) { + if (!unacked_packets_.empty()) { + QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); + QuicPacketNumber largest_sent_packet = + unacked_packets_.largest_sent_packet(); + for (; packet_number <= largest_sent_packet; ++packet_number) { + QuicTransmissionInfo* transmission_info = + unacked_packets_.GetMutableTransmissionInfo(packet_number); + // Only retransmit frames which are in flight, and therefore have been + // sent. + if (!transmission_info->in_flight || + transmission_info->state != OUTSTANDING || + !transmission_info->has_crypto_handshake || + !unacked_packets_.HasRetransmittableFrames(*transmission_info)) { + continue; + } + packet_retransmitted = true; + crypto_retransmissions.push_back(packet_number); + ++pending_timer_transmission_count_; + } } - packet_retransmitted = true; - crypto_retransmissions.push_back(packet_number); - ++pending_timer_transmission_count_; + } else { + QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); + for (auto it = unacked_packets_.begin(); it != unacked_packets_.end(); + ++it, ++packet_number) { + // Only retransmit frames which are in flight, and therefore have been + // sent. + if (!it->in_flight || it->state != OUTSTANDING || + !it->has_crypto_handshake || + !unacked_packets_.HasRetransmittableFrames(*it)) { + continue; + } + packet_retransmitted = true; + crypto_retransmissions.push_back(packet_number); + ++pending_timer_transmission_count_; + } } DCHECK(packet_retransmitted) << "No crypto packets found to retransmit."; for (QuicPacketNumber retransmission : crypto_retransmissions) { @@ -882,16 +935,38 @@ } bool QuicSentPacketManager::MaybeRetransmitOldestPacket(TransmissionType type) { - QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); - for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++packet_number) { - // Only retransmit frames which are in flight, and therefore have been sent. - if (!it->in_flight || it->state != OUTSTANDING || - !unacked_packets_.HasRetransmittableFrames(*it)) { - continue; + if (unacked_packets_.use_circular_deque()) { + if (!unacked_packets_.empty()) { + QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); + QuicPacketNumber largest_sent_packet = + unacked_packets_.largest_sent_packet(); + for (; packet_number <= largest_sent_packet; ++packet_number) { + QuicTransmissionInfo* transmission_info = + unacked_packets_.GetMutableTransmissionInfo(packet_number); + // Only retransmit frames which are in flight, and therefore have been + // sent. + if (!transmission_info->in_flight || + transmission_info->state != OUTSTANDING || + !unacked_packets_.HasRetransmittableFrames(*transmission_info)) { + continue; + } + MarkForRetransmission(packet_number, type); + return true; + } } - MarkForRetransmission(packet_number, type); - return true; + } else { + QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); + for (auto it = unacked_packets_.begin(); it != unacked_packets_.end(); + ++it, ++packet_number) { + // Only retransmit frames which are in flight, and therefore have been + // sent. + if (!it->in_flight || it->state != OUTSTANDING || + !unacked_packets_.HasRetransmittableFrames(*it)) { + continue; + } + MarkForRetransmission(packet_number, type); + return true; + } } QUIC_DVLOG(1) << "No retransmittable packets, so RetransmitOldestPacket failed."; @@ -903,16 +978,35 @@ QUIC_BUG_IF(pending_timer_transmission_count_ > 0) << "Retransmissions already queued:" << pending_timer_transmission_count_; // Mark two packets for retransmission. - QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); std::vector<QuicPacketNumber> retransmissions; - for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++packet_number) { - if (it->state == OUTSTANDING && - unacked_packets_.HasRetransmittableFrames(*it) && - pending_timer_transmission_count_ < max_rto_packets_) { - DCHECK(it->in_flight); - retransmissions.push_back(packet_number); - ++pending_timer_transmission_count_; + if (unacked_packets_.use_circular_deque()) { + if (!unacked_packets_.empty()) { + QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); + QuicPacketNumber largest_sent_packet = + unacked_packets_.largest_sent_packet(); + for (; packet_number <= largest_sent_packet; ++packet_number) { + QuicTransmissionInfo* transmission_info = + unacked_packets_.GetMutableTransmissionInfo(packet_number); + if (transmission_info->state == OUTSTANDING && + unacked_packets_.HasRetransmittableFrames(*transmission_info) && + pending_timer_transmission_count_ < max_rto_packets_) { + DCHECK(transmission_info->in_flight); + retransmissions.push_back(packet_number); + ++pending_timer_transmission_count_; + } + } + } + } else { + QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); + for (auto it = unacked_packets_.begin(); it != unacked_packets_.end(); + ++it, ++packet_number) { + if (it->state == OUTSTANDING && + unacked_packets_.HasRetransmittableFrames(*it) && + pending_timer_transmission_count_ < max_rto_packets_) { + DCHECK(it->in_flight); + retransmissions.push_back(packet_number); + ++pending_timer_transmission_count_; + } } } if (pending_timer_transmission_count_ > 0) { @@ -948,19 +1042,42 @@ return; } } - QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); std::vector<QuicPacketNumber> probing_packets; - for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++packet_number) { - if (it->state == OUTSTANDING && - unacked_packets_.HasRetransmittableFrames(*it) && - (!supports_multiple_packet_number_spaces() || - unacked_packets_.GetPacketNumberSpace(it->encryption_level) == - packet_number_space)) { - DCHECK(it->in_flight); - probing_packets.push_back(packet_number); - if (probing_packets.size() == pending_timer_transmission_count_) { - break; + if (unacked_packets_.use_circular_deque()) { + if (!unacked_packets_.empty()) { + QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); + QuicPacketNumber largest_sent_packet = + unacked_packets_.largest_sent_packet(); + for (; packet_number <= largest_sent_packet; ++packet_number) { + QuicTransmissionInfo* transmission_info = + unacked_packets_.GetMutableTransmissionInfo(packet_number); + if (transmission_info->state == OUTSTANDING && + unacked_packets_.HasRetransmittableFrames(*transmission_info) && + (!supports_multiple_packet_number_spaces() || + unacked_packets_.GetPacketNumberSpace( + transmission_info->encryption_level) == packet_number_space)) { + DCHECK(transmission_info->in_flight); + probing_packets.push_back(packet_number); + if (probing_packets.size() == pending_timer_transmission_count_) { + break; + } + } + } + } + } else { + QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); + for (auto it = unacked_packets_.begin(); it != unacked_packets_.end(); + ++it, ++packet_number) { + if (it->state == OUTSTANDING && + unacked_packets_.HasRetransmittableFrames(*it) && + (!supports_multiple_packet_number_spaces() || + unacked_packets_.GetPacketNumberSpace(it->encryption_level) == + packet_number_space)) { + DCHECK(it->in_flight); + probing_packets.push_back(packet_number); + if (probing_packets.size() == pending_timer_transmission_count_) { + break; + } } } } @@ -1016,21 +1133,48 @@ // No in flight data of space. return; } - QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); - for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++packet_number) { - if (it->state == OUTSTANDING && - unacked_packets_.HasRetransmittableFrames(*it) && - unacked_packets_.GetPacketNumberSpace(it->encryption_level) == space) { - DCHECK(it->in_flight); - if (GetQuicReloadableFlag(quic_fix_pto_pending_timer_count) && - pending_timer_transmission_count_ == 0) { - QUIC_RELOADABLE_FLAG_COUNT(quic_fix_pto_pending_timer_count); - pending_timer_transmission_count_ = 1; - } - MarkForRetransmission(packet_number, PTO_RETRANSMISSION); + if (unacked_packets_.use_circular_deque()) { + if (unacked_packets_.empty()) { return; } + QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); + QuicPacketNumber largest_sent_packet = + unacked_packets_.largest_sent_packet(); + for (; packet_number <= largest_sent_packet; ++packet_number) { + QuicTransmissionInfo* transmission_info = + unacked_packets_.GetMutableTransmissionInfo(packet_number); + if (transmission_info->state == OUTSTANDING && + unacked_packets_.HasRetransmittableFrames(*transmission_info) && + unacked_packets_.GetPacketNumberSpace( + transmission_info->encryption_level) == space) { + DCHECK(transmission_info->in_flight); + if (GetQuicReloadableFlag(quic_fix_pto_pending_timer_count) && + pending_timer_transmission_count_ == 0) { + QUIC_RELOADABLE_FLAG_COUNT(quic_fix_pto_pending_timer_count); + pending_timer_transmission_count_ = 1; + } + MarkForRetransmission(packet_number, PTO_RETRANSMISSION); + return; + } + } + } else { + QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked(); + for (auto it = unacked_packets_.begin(); it != unacked_packets_.end(); + ++it, ++packet_number) { + if (it->state == OUTSTANDING && + unacked_packets_.HasRetransmittableFrames(*it) && + unacked_packets_.GetPacketNumberSpace(it->encryption_level) == + space) { + DCHECK(it->in_flight); + if (GetQuicReloadableFlag(quic_fix_pto_pending_timer_count) && + pending_timer_transmission_count_ == 0) { + QUIC_RELOADABLE_FLAG_COUNT(quic_fix_pto_pending_timer_count); + pending_timer_transmission_count_ = 1; + } + MarkForRetransmission(packet_number, PTO_RETRANSMISSION); + return; + } + } } }
diff --git a/quic/core/quic_sent_packet_manager.h b/quic/core/quic_sent_packet_manager.h index 64cd4c0..df18f2a 100644 --- a/quic/core/quic_sent_packet_manager.h +++ b/quic/core/quic_sent_packet_manager.h
@@ -125,6 +125,10 @@ virtual void SetFromConfig(const QuicConfig& config); + void ReserveUnackedPacketsInitialCapacity(int initial_capacity) { + unacked_packets_.ReserveInitialCapacity(initial_capacity); + } + void ApplyConnectionOptions(const QuicTagVector& connection_options); // Pass the CachedNetworkParameters to the send algorithm. @@ -514,7 +518,8 @@ // Request that |packet_number| be retransmitted after the other pending // retransmissions. Does not add it to the retransmissions if it's already - // a pending retransmission. + // a pending retransmission. Do not reuse iterator of the underlying + // unacked_packets_ after calling this function as it can be invalidated. void MarkForRetransmission(QuicPacketNumber packet_number, TransmissionType transmission_type);
diff --git a/quic/core/quic_unacked_packet_map.cc b/quic/core/quic_unacked_packet_map.cc index 3e377cf..852a0df 100644 --- a/quic/core/quic_unacked_packet_map.cc +++ b/quic/core/quic_unacked_packet_map.cc
@@ -4,10 +4,12 @@ #include "net/third_party/quiche/src/quic/core/quic_unacked_packet_map.h" +#include <cstddef> #include <limits> #include <type_traits> #include "net/third_party/quiche/src/quic/core/quic_connection_stats.h" +#include "net/third_party/quiche/src/quic/core/quic_packet_number.h" #include "net/third_party/quiche/src/quic/core/quic_utils.h" #include "net/third_party/quiche/src/quic/platform/api/quic_bug_tracker.h" #include "net/third_party/quiche/src/quic/platform/api/quic_flag_utils.h" @@ -120,11 +122,21 @@ {QuicTime::Zero()}}, last_crypto_packet_sent_time_(QuicTime::Zero()), session_notifier_(nullptr), - supports_multiple_packet_number_spaces_(false) {} + supports_multiple_packet_number_spaces_(false) { + if (use_circular_deque_) { + QUIC_RELOADABLE_FLAG_COUNT(quic_use_circular_deque_for_unacked_packets); + } +} QuicUnackedPacketMap::~QuicUnackedPacketMap() { - for (QuicTransmissionInfo& transmission_info : unacked_packets_) { - DeleteFrames(&(transmission_info.retransmittable_frames)); + if (use_circular_deque_) { + for (QuicTransmissionInfo& transmission_info : unacked_packets_) { + DeleteFrames(&(transmission_info.retransmittable_frames)); + } + } else { + for (QuicTransmissionInfo& transmission_info : unacked_packets_deque_) { + DeleteFrames(&(transmission_info.retransmittable_frames)); + } } } @@ -140,10 +152,10 @@ largest_sent_packet_ >= packet_number) << "largest_sent_packet_: " << largest_sent_packet_ << ", packet_number: " << packet_number; - DCHECK_GE(packet_number, least_unacked_ + unacked_packets_.size()); - while (least_unacked_ + unacked_packets_.size() < packet_number) { - unacked_packets_.push_back(QuicTransmissionInfo()); - unacked_packets_.back().state = NEVER_SENT; + DCHECK_GE(packet_number, least_unacked_ + unacked_packets_size()); + while (least_unacked_ + unacked_packets_size() < packet_number) { + unacked_packets_push_back(QuicTransmissionInfo()); + unacked_packets_back().state = NEVER_SENT; } const bool has_crypto_handshake = packet.has_crypto_handshake == IS_HANDSHAKE; @@ -170,7 +182,7 @@ last_inflight_packet_sent_time_ = sent_time; last_inflight_packets_sent_time_[packet_number_space] = sent_time; } - unacked_packets_.push_back(info); + unacked_packets_push_back(info); // Swap the retransmittable frames to avoid allocations. // TODO(ianswett): Could use emplace_back when Chromium can. if (has_crypto_handshake) { @@ -178,16 +190,16 @@ } mutable_packet->retransmittable_frames.swap( - unacked_packets_.back().retransmittable_frames); + unacked_packets_back().retransmittable_frames); } void QuicUnackedPacketMap::RemoveObsoletePackets() { - while (!unacked_packets_.empty()) { - if (!IsPacketUseless(least_unacked_, unacked_packets_.front())) { + while (!unacked_packets_empty()) { + if (!IsPacketUseless(least_unacked_, unacked_packets_front())) { break; } - DeleteFrames(&unacked_packets_.front().retransmittable_frames); - unacked_packets_.pop_front(); + DeleteFrames(&unacked_packets_front().retransmittable_frames); + unacked_packets_pop_front(); ++least_unacked_; } } @@ -195,9 +207,9 @@ bool QuicUnackedPacketMap::HasRetransmittableFrames( QuicPacketNumber packet_number) const { DCHECK_GE(packet_number, least_unacked_); - DCHECK_LT(packet_number, least_unacked_ + unacked_packets_.size()); + DCHECK_LT(packet_number, least_unacked_ + unacked_packets_size()); return HasRetransmittableFrames( - unacked_packets_[packet_number - least_unacked_]); + unacked_packets_at(packet_number - least_unacked_)); } bool QuicUnackedPacketMap::HasRetransmittableFrames( @@ -223,9 +235,9 @@ void QuicUnackedPacketMap::RemoveRetransmittability( QuicPacketNumber packet_number) { DCHECK_GE(packet_number, least_unacked_); - DCHECK_LT(packet_number, least_unacked_ + unacked_packets_.size()); + DCHECK_LT(packet_number, least_unacked_ + unacked_packets_size()); QuicTransmissionInfo* info = - &unacked_packets_[packet_number - least_unacked_]; + &unacked_packets_at(packet_number - least_unacked_); RemoveRetransmittability(info); } @@ -275,11 +287,11 @@ bool QuicUnackedPacketMap::IsUnacked(QuicPacketNumber packet_number) const { if (packet_number < least_unacked_ || - packet_number >= least_unacked_ + unacked_packets_.size()) { + packet_number >= least_unacked_ + unacked_packets_size()) { return false; } return !IsPacketUseless(packet_number, - unacked_packets_[packet_number - least_unacked_]); + unacked_packets_at(packet_number - least_unacked_)); } void QuicUnackedPacketMap::RemoveFromInFlight(QuicTransmissionInfo* info) { @@ -313,9 +325,9 @@ void QuicUnackedPacketMap::RemoveFromInFlight(QuicPacketNumber packet_number) { DCHECK_GE(packet_number, least_unacked_); - DCHECK_LT(packet_number, least_unacked_ + unacked_packets_.size()); + DCHECK_LT(packet_number, least_unacked_ + unacked_packets_size()); QuicTransmissionInfo* info = - &unacked_packets_[packet_number - least_unacked_]; + &unacked_packets_at(packet_number - least_unacked_); RemoveFromInFlight(info); } @@ -323,8 +335,8 @@ QuicUnackedPacketMap::NeuterUnencryptedPackets() { QuicInlinedVector<QuicPacketNumber, 2> neutered_packets; QuicPacketNumber packet_number = GetLeastUnacked(); - for (QuicUnackedPacketMap::iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++packet_number) { + for (QuicUnackedPacketMap::iterator it = begin(); it != end(); + ++it, ++packet_number) { if (!it->retransmittable_frames.empty() && it->encryption_level == ENCRYPTION_INITIAL) { QUIC_DVLOG(2) << "Neutering unencrypted packet " << packet_number; @@ -350,8 +362,8 @@ QuicUnackedPacketMap::NeuterHandshakePackets() { QuicInlinedVector<QuicPacketNumber, 2> neutered_packets; QuicPacketNumber packet_number = GetLeastUnacked(); - for (QuicUnackedPacketMap::iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++packet_number) { + for (QuicUnackedPacketMap::iterator it = begin(); it != end(); + ++it, ++packet_number) { if (!it->retransmittable_frames.empty() && GetPacketNumberSpace(it->encryption_level) == HANDSHAKE_DATA) { QUIC_DVLOG(2) << "Neutering handshake packet " << packet_number; @@ -375,12 +387,12 @@ const QuicTransmissionInfo& QuicUnackedPacketMap::GetTransmissionInfo( QuicPacketNumber packet_number) const { - return unacked_packets_[packet_number - least_unacked_]; + return unacked_packets_at(packet_number - least_unacked_); } QuicTransmissionInfo* QuicUnackedPacketMap::GetMutableTransmissionInfo( QuicPacketNumber packet_number) { - return &unacked_packets_[packet_number - least_unacked_]; + return &unacked_packets_at(packet_number - least_unacked_); } QuicTime QuicUnackedPacketMap::GetLastInFlightPacketSentTime() const { @@ -394,8 +406,7 @@ size_t QuicUnackedPacketMap::GetNumUnackedPacketsDebugOnly() const { size_t unacked_packet_count = 0; QuicPacketNumber packet_number = least_unacked_; - for (auto it = unacked_packets_.begin(); it != unacked_packets_.end(); - ++it, ++packet_number) { + for (auto it = begin(); it != end(); ++it, ++packet_number) { if (!IsPacketUseless(packet_number, *it)) { ++unacked_packet_count; } @@ -408,8 +419,7 @@ return true; } size_t num_in_flight = 0; - for (auto it = unacked_packets_.rbegin(); it != unacked_packets_.rend(); - ++it) { + for (auto it = rbegin(); it != rend(); ++it) { if (it->in_flight) { ++num_in_flight; } @@ -425,8 +435,7 @@ } bool QuicUnackedPacketMap::HasUnackedRetransmittableFrames() const { - for (auto it = unacked_packets_.rbegin(); it != unacked_packets_.rend(); - ++it) { + for (auto it = rbegin(); it != rend(); ++it) { if (it->in_flight && HasRetransmittableFrames(*it)) { return true; } @@ -584,7 +593,7 @@ const QuicTransmissionInfo* QuicUnackedPacketMap::GetFirstInFlightTransmissionInfo() const { DCHECK(HasInFlightPackets()); - for (auto it = unacked_packets_.begin(); it != unacked_packets_.end(); ++it) { + for (auto it = begin(); it != end(); ++it) { if (it->in_flight) { return &(*it); } @@ -598,7 +607,7 @@ PacketNumberSpace packet_number_space) const { // TODO(fayang): Optimize this part if arm 1st PTO with first in flight sent // time works. - for (auto it = unacked_packets_.begin(); it != unacked_packets_.end(); ++it) { + for (auto it = begin(); it != end(); ++it) { if (it->in_flight && GetPacketNumberSpace(it->encryption_level) == packet_number_space) { return &(*it); @@ -628,7 +637,7 @@ return -1; } int32_t content = 0; - const QuicTransmissionInfo& last_packet = unacked_packets_.back(); + const QuicTransmissionInfo& last_packet = unacked_packets_back(); for (const auto& frame : last_packet.retransmittable_frames) { content |= GetFrameTypeBitfield(frame.type); }
diff --git a/quic/core/quic_unacked_packet_map.h b/quic/core/quic_unacked_packet_map.h index 595f435..a6c0025 100644 --- a/quic/core/quic_unacked_packet_map.h +++ b/quic/core/quic_unacked_packet_map.h
@@ -6,12 +6,15 @@ #define QUICHE_QUIC_CORE_QUIC_UNACKED_PACKET_MAP_H_ #include <cstddef> +#include <cstdint> #include <deque> +#include "net/third_party/quiche/src/quic/core/quic_circular_deque.h" #include "net/third_party/quiche/src/quic/core/quic_packets.h" #include "net/third_party/quiche/src/quic/core/quic_transmission_info.h" #include "net/third_party/quiche/src/quic/core/session_notifier_interface.h" #include "net/third_party/quiche/src/quic/platform/api/quic_export.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_flags.h" namespace quic { @@ -90,7 +93,9 @@ bool HasUnackedRetransmittableFrames() const; // Returns true if there are no packets present in the unacked packet map. - bool empty() const { return unacked_packets_.empty(); } + bool empty() const { return unacked_packets_empty(); } + + bool use_circular_deque() const { return use_circular_deque_; } // Returns the largest packet number that has been sent. QuicPacketNumber largest_sent_packet() const { return largest_sent_packet_; } @@ -110,20 +115,79 @@ // been acked by the peer. If there are no unacked packets, returns 0. QuicPacketNumber GetLeastUnacked() const; - // This can not be a QuicCircularDeque since pointers into this are - // assumed to be stable. - typedef std::deque<QuicTransmissionInfo> UnackedPacketMap; + template <typename Itr1, typename Itr2> + class QUIC_EXPORT_PRIVATE IteratorWrapper { + public: + explicit IteratorWrapper(Itr1 itr1) : itr_(std::move(itr1)) {} + explicit IteratorWrapper(Itr2 itr2) : itr_(std::move(itr2)) {} - typedef UnackedPacketMap::const_iterator const_iterator; - typedef UnackedPacketMap::const_reverse_iterator const_reverse_iterator; - typedef UnackedPacketMap::iterator iterator; + auto& operator*() const { + return absl::visit( + [](const auto& itr) -> auto& { return *itr; }, itr_); + } - const_iterator begin() const { return unacked_packets_.begin(); } - const_iterator end() const { return unacked_packets_.end(); } - const_reverse_iterator rbegin() const { return unacked_packets_.rbegin(); } - const_reverse_iterator rend() const { return unacked_packets_.rend(); } - iterator begin() { return unacked_packets_.begin(); } - iterator end() { return unacked_packets_.end(); } + auto* operator->() const { + return absl::visit([](const auto& itr) { return &*itr; }, itr_); + } + + IteratorWrapper& operator++() { + absl::visit([](auto& itr) { ++itr; }, itr_); + return *this; + } + + IteratorWrapper& operator+=(int difference) { + absl::visit([difference](auto& itr) { itr += difference; }, itr_); + return *this; + } + + IteratorWrapper operator++(int) { + return absl::visit([](auto& itr) { IteratorWrapper(itr++); }, itr_); + } + + bool operator!=(const IteratorWrapper& other) const { + return itr_ != other.itr_; + } + + private: + absl::variant<Itr1, Itr2> itr_; + }; + + using const_iterator = + IteratorWrapper<std::deque<QuicTransmissionInfo>::const_iterator, + QuicCircularDeque<QuicTransmissionInfo>::const_iterator>; + using const_reverse_iterator = IteratorWrapper< + std::deque<QuicTransmissionInfo>::const_reverse_iterator, + QuicCircularDeque<QuicTransmissionInfo>::const_reverse_iterator>; + using iterator = + IteratorWrapper<std::deque<QuicTransmissionInfo>::iterator, + QuicCircularDeque<QuicTransmissionInfo>::iterator>; + + const_iterator begin() const { + return use_circular_deque_ ? const_iterator(unacked_packets_.begin()) + : const_iterator(unacked_packets_deque_.begin()); + } + const_iterator end() const { + return use_circular_deque_ ? const_iterator(unacked_packets_.end()) + : const_iterator(unacked_packets_deque_.end()); + } + const_reverse_iterator rbegin() const { + return use_circular_deque_ + ? const_reverse_iterator(unacked_packets_.rbegin()) + : const_reverse_iterator(unacked_packets_deque_.rbegin()); + } + const_reverse_iterator rend() const { + return use_circular_deque_ + ? const_reverse_iterator(unacked_packets_.rend()) + : const_reverse_iterator(unacked_packets_deque_.rend()); + } + iterator begin() { + return use_circular_deque_ ? iterator(unacked_packets_.begin()) + : iterator(unacked_packets_deque_.begin()); + } + iterator end() { + return use_circular_deque_ ? iterator(unacked_packets_.end()) + : iterator(unacked_packets_deque_.end()); + } // Returns true if there are unacked packets that are in flight. bool HasInFlightPackets() const; @@ -244,9 +308,73 @@ return supports_multiple_packet_number_spaces_; } + void ReserveInitialCapacity(size_t initial_capacity) { + if (use_circular_deque_) { + unacked_packets_.reserve(initial_capacity); + } + } + private: friend class test::QuicUnackedPacketMapPeer; + // TODO(haoyuewang) Remove these methods when deprecate + // quic_use_circular_deque_for_unacked_packets flag. + size_t unacked_packets_size() const { + return use_circular_deque_ ? unacked_packets_.size() + : unacked_packets_deque_.size(); + } + + const QuicTransmissionInfo& unacked_packets_at(int index) const { + return use_circular_deque_ ? unacked_packets_[index] + : unacked_packets_deque_[index]; + } + + QuicTransmissionInfo& unacked_packets_at(int index) { + return use_circular_deque_ ? unacked_packets_[index] + : unacked_packets_deque_[index]; + } + + const QuicTransmissionInfo& unacked_packets_front() const { + return use_circular_deque_ ? unacked_packets_.front() + : unacked_packets_deque_.front(); + } + + QuicTransmissionInfo& unacked_packets_front() { + return use_circular_deque_ ? unacked_packets_.front() + : unacked_packets_deque_.front(); + } + + const QuicTransmissionInfo& unacked_packets_back() const { + return use_circular_deque_ ? unacked_packets_.back() + : unacked_packets_deque_.back(); + } + + QuicTransmissionInfo& unacked_packets_back() { + return use_circular_deque_ ? unacked_packets_.back() + : unacked_packets_deque_.back(); + } + + void unacked_packets_push_back(QuicTransmissionInfo info) { + if (use_circular_deque_) { + unacked_packets_.push_back(std::move(info)); + } else { + unacked_packets_deque_.push_back(std::move(info)); + } + } + + void unacked_packets_pop_front() { + if (use_circular_deque_) { + unacked_packets_.pop_front(); + } else { + unacked_packets_deque_.pop_front(); + } + } + + bool unacked_packets_empty() const { + return use_circular_deque_ ? unacked_packets_.empty() + : unacked_packets_deque_.empty(); + } + // Returns true if packet may be useful for an RTT measurement. bool IsPacketUsefulForMeasuringRtt(QuicPacketNumber packet_number, const QuicTransmissionInfo& info) const; @@ -286,7 +414,12 @@ // If the old packet is acked before the new packet, then the old entry will // be removed from the map and the new entry's retransmittable frames will be // set to nullptr. - UnackedPacketMap unacked_packets_; + QuicCircularDeque<QuicTransmissionInfo> unacked_packets_; + std::deque<QuicTransmissionInfo> unacked_packets_deque_; + + const bool use_circular_deque_ = + GetQuicReloadableFlag(quic_use_circular_deque_for_unacked_packets); + // The packet at the 0th index of unacked_packets_. QuicPacketNumber least_unacked_;
diff --git a/quic/core/quic_unacked_packet_map_test.cc b/quic/core/quic_unacked_packet_map_test.cc index b81b3ea..0282108 100644 --- a/quic/core/quic_unacked_packet_map_test.cc +++ b/quic/core/quic_unacked_packet_map_test.cc
@@ -3,10 +3,12 @@ // found in the LICENSE file. #include "net/third_party/quiche/src/quic/core/quic_unacked_packet_map.h" +#include <cstddef> #include <limits> #include "absl/base/macros.h" #include "net/third_party/quiche/src/quic/core/frames/quic_stream_frame.h" +#include "net/third_party/quiche/src/quic/core/quic_packet_number.h" #include "net/third_party/quiche/src/quic/core/quic_transmission_info.h" #include "net/third_party/quiche/src/quic/core/quic_utils.h" #include "net/third_party/quiche/src/quic/platform/api/quic_test.h" @@ -84,8 +86,8 @@ .in_flight); } size_t in_flight_count = 0; - for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it) { + for (auto it = unacked_packets_.begin(); it != unacked_packets_.end(); + ++it) { if (it->in_flight) { ++in_flight_count; } @@ -111,8 +113,8 @@ void VerifyRetransmittablePackets(uint64_t* packets, size_t num_packets) { unacked_packets_.RemoveObsoletePackets(); size_t num_retransmittable_packets = 0; - for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it) { + for (auto it = unacked_packets_.begin(); it != unacked_packets_.end(); + ++it) { if (unacked_packets_.HasRetransmittableFrames(*it)) { ++num_retransmittable_packets; } @@ -655,6 +657,18 @@ EXPECT_FALSE(unacked_packets_.GetLastPacketContent() & (1 << ACK_FRAME)); } +TEST_P(QuicUnackedPacketMapTest, ReserveInitialCapacityTest) { + SetQuicReloadableFlag(quic_use_circular_deque_for_unacked_packets, true); + QuicUnackedPacketMap unacked_packets(GetParam()); + ASSERT_EQ(QuicUnackedPacketMapPeer::GetCapacity(unacked_packets), 0u); + unacked_packets.ReserveInitialCapacity(16); + QuicStreamId stream_id(1); + SerializedPacket packet(CreateRetransmittablePacketForStream(1, stream_id)); + unacked_packets.AddSentPacket(&packet, TransmissionType::NOT_RETRANSMISSION, + now_, true, true); + ASSERT_EQ(QuicUnackedPacketMapPeer::GetCapacity(unacked_packets), 16u); +} + } // namespace } // namespace test } // namespace quic
diff --git a/quic/test_tools/quic_unacked_packet_map_peer.cc b/quic/test_tools/quic_unacked_packet_map_peer.cc index 1ecc65f..fa3408c 100644 --- a/quic/test_tools/quic_unacked_packet_map_peer.cc +++ b/quic/test_tools/quic_unacked_packet_map_peer.cc
@@ -20,5 +20,11 @@ *const_cast<Perspective*>(&unacked_packets->perspective_) = perspective; } +// static +size_t QuicUnackedPacketMapPeer::GetCapacity( + const QuicUnackedPacketMap& unacked_packets) { + return unacked_packets.unacked_packets_.capacity(); +} + } // namespace test } // namespace quic
diff --git a/quic/test_tools/quic_unacked_packet_map_peer.h b/quic/test_tools/quic_unacked_packet_map_peer.h index 3bba0b6..17c88fe 100644 --- a/quic/test_tools/quic_unacked_packet_map_peer.h +++ b/quic/test_tools/quic_unacked_packet_map_peer.h
@@ -17,6 +17,8 @@ static void SetPerspective(QuicUnackedPacketMap* unacked_packets, Perspective perspective); + + static size_t GetCapacity(const QuicUnackedPacketMap& unacked_packets); }; } // namespace test