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
