diff options
author | rtenneti <rtenneti@chromium.org> | 2014-08-29 16:53:34 -0700 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2014-08-29 23:56:44 +0000 |
commit | 00f180a54e0ebf53bcadebc9983ee406818f232b (patch) | |
tree | 1f264b9435617559bc0df93f40d63e576ceea5ea | |
parent | 15c487676ac5c50e1f59461d3c7c3f89cf27838d (diff) | |
download | chromium_src-00f180a54e0ebf53bcadebc9983ee406818f232b.zip chromium_src-00f180a54e0ebf53bcadebc9983ee406818f232b.tar.gz chromium_src-00f180a54e0ebf53bcadebc9983ee406818f232b.tar.bz2 |
Revert of Landing Recent QUIC Changes. (patchset #1 id:1 of https://codereview.chromium.org/515303003/)
Reason for revert:
Reverting to see if it fixes the following issue. Crash rate has gone up by 10 times.
BUG=409191
Original issue's description:
> Landing Recent QUIC Changes.
>
> Nest a QUIC SerializedPacket inside a QUIC QueuedPacket.
>
> Merge internal change: 74239145
> https://codereview.chromium.org/509203003/
>
>
> Remove PacketType from QUIC because the QUEUED type is not used and the
> other types can be reduced to a bool.
>
> Merge internal change: 74148481
> https://codereview.chromium.org/515003003/
>
>
> Don't send a QUIC SCUP message until after handshake confirmed.
>
> A server config update was occasionally being sent before the crypto
> handshake was complete, causing the client to close the connection.
>
> Merge internal change: 74132773
> https://codereview.chromium.org/516713002/
>
>
> Change TransmissionInfo's all_transmissions SequenceNumberSet* to
> default to NULL, and only be present if there are multiple transmissions.
>
> Estimated to save ~2% of CPU.
>
> Merge internal change: 74076012
> https://codereview.chromium.org/509073004/
>
>
> Log the quic version for internal server tracing.
> Not used in production.
>
> Merge internal change: 74069715
> https://codereview.chromium.org/514043002/
>
>
> Optimize QuicUnackedPacketMap by changing from a LinkedHashMap to a
> deque.
>
> Estimated to save ~3% of CPU based on pprof profiling of 100 large gets
> on tools/quic/end_to_end_test.cc.
>
> Merge internal change: 74054196
> https://codereview.chromium.org/514033002/
>
>
> Unit test for empty packet closes QUIC connection bug.
>
> Merge internal change: 74041239
> https://codereview.chromium.org/495423011/
>
>
> Log the QUIC transmission type in QUIC internal server trace visitor.
> Not used in production.
>
> Merge internal change: 73895739
> https://codereview.chromium.org/514023002/
>
>
> Not used in production. Log whether a QUIC packet sent was a crypto
> packet or not for internal server side tracing.
>
> Merge internal change: 73894063
> https://codereview.chromium.org/515003002/
>
>
> Fix a QUIC bug in which PING frames were not being ACK'd.
>
> Merge internal change: 73837644
> https://codereview.chromium.org/512933005/
>
> R=rch@chromium.org
>
> Committed: https://chromium.googlesource.com/chromium/src/+/27f3f1894f09a96112df50fddd32895b4677f949
TBR=rch@chromium.org
NOTREECHECKS=true
NOTRY=true
Review URL: https://codereview.chromium.org/523813003
Cr-Commit-Position: refs/heads/master@{#292722}
-rw-r--r-- | net/quic/congestion_control/tcp_loss_algorithm.cc | 21 | ||||
-rw-r--r-- | net/quic/congestion_control/time_loss_algorithm.cc | 12 | ||||
-rw-r--r-- | net/quic/quic_connection.cc | 155 | ||||
-rw-r--r-- | net/quic/quic_connection.h | 20 | ||||
-rw-r--r-- | net/quic/quic_connection_logger.h | 3 | ||||
-rw-r--r-- | net/quic/quic_connection_test.cc | 184 | ||||
-rw-r--r-- | net/quic/quic_crypto_server_stream.cc | 3 | ||||
-rw-r--r-- | net/quic/quic_crypto_server_stream_test.cc | 6 | ||||
-rw-r--r-- | net/quic/quic_protocol.cc | 14 | ||||
-rw-r--r-- | net/quic/quic_protocol.h | 7 | ||||
-rw-r--r-- | net/quic/quic_sent_entropy_manager.cc | 2 | ||||
-rw-r--r-- | net/quic/quic_sent_packet_manager.cc | 148 | ||||
-rw-r--r-- | net/quic/quic_sent_packet_manager.h | 17 | ||||
-rw-r--r-- | net/quic/quic_sent_packet_manager_test.cc | 4 | ||||
-rw-r--r-- | net/quic/quic_unacked_packet_map.cc | 263 | ||||
-rw-r--r-- | net/quic/quic_unacked_packet_map.h | 19 | ||||
-rw-r--r-- | net/quic/quic_unacked_packet_map_test.cc | 14 | ||||
-rw-r--r-- | net/quic/test_tools/quic_sent_packet_manager_peer.cc | 4 | ||||
-rw-r--r-- | net/tools/quic/quic_client_session_test.cc | 38 |
19 files changed, 505 insertions, 429 deletions
diff --git a/net/quic/congestion_control/tcp_loss_algorithm.cc b/net/quic/congestion_control/tcp_loss_algorithm.cc index 557681e..8dad3f1 100644 --- a/net/quic/congestion_control/tcp_loss_algorithm.cc +++ b/net/quic/congestion_control/tcp_loss_algorithm.cc @@ -37,34 +37,33 @@ SequenceNumberSet TCPLossAlgorithm::DetectLostPackets( loss_detection_timeout_ = QuicTime::Zero(); QuicTime::Delta loss_delay = rtt_stats.SmoothedRtt().Multiply(kEarlyRetransmitLossDelayMultiplier); - QuicPacketSequenceNumber sequence_number = unacked_packets.GetLeastUnacked(); + for (QuicUnackedPacketMap::const_iterator it = unacked_packets.begin(); - it != unacked_packets.end() && sequence_number <= largest_observed; - ++it, ++sequence_number) { - if (!it->in_flight) { + it != unacked_packets.end() && it->first <= largest_observed; ++it) { + if (!it->second.in_flight) { continue; } - LOG_IF(DFATAL, it->nack_count == 0) + LOG_IF(DFATAL, it->second.nack_count == 0) << "All packets less than largest observed should have been nacked."; - if (it->nack_count >= kNumberOfNacksBeforeRetransmission) { - lost_packets.insert(sequence_number); + if (it->second.nack_count >= kNumberOfNacksBeforeRetransmission) { + lost_packets.insert(it->first); continue; } // Only early retransmit(RFC5827) when the last packet gets acked and // there are retransmittable packets in flight. // This also implements a timer-protected variant of FACK. - if (it->retransmittable_frames && + if (it->second.retransmittable_frames && unacked_packets.largest_sent_packet() == largest_observed) { // Early retransmit marks the packet as lost once 1.25RTTs have passed // since the packet was sent and otherwise sets an alarm. - if (time >= it->sent_time.Add(loss_delay)) { - lost_packets.insert(sequence_number); + if (time >= it->second.sent_time.Add(loss_delay)) { + lost_packets.insert(it->first); } else { // Set the timeout for the earliest retransmittable packet where early // retransmit applies. - loss_detection_timeout_ = it->sent_time.Add(loss_delay); + loss_detection_timeout_ = it->second.sent_time.Add(loss_delay); break; } } diff --git a/net/quic/congestion_control/time_loss_algorithm.cc b/net/quic/congestion_control/time_loss_algorithm.cc index 3a7b42d..d23dead 100644 --- a/net/quic/congestion_control/time_loss_algorithm.cc +++ b/net/quic/congestion_control/time_loss_algorithm.cc @@ -39,24 +39,22 @@ SequenceNumberSet TimeLossAlgorithm::DetectLostPackets( QuicTime::Delta::Max(rtt_stats.SmoothedRtt(), rtt_stats.latest_rtt()) .Multiply(kLossDelayMultiplier)); - QuicPacketSequenceNumber sequence_number = unacked_packets.GetLeastUnacked(); for (QuicUnackedPacketMap::const_iterator it = unacked_packets.begin(); - it != unacked_packets.end() && sequence_number <= largest_observed; - ++it, ++sequence_number) { - if (!it->in_flight) { + it != unacked_packets.end() && it->first <= largest_observed; ++it) { + if (!it->second.in_flight) { continue; } - LOG_IF(DFATAL, it->nack_count == 0) + LOG_IF(DFATAL, it->second.nack_count == 0) << "All packets less than largest observed should have been nacked."; // Packets are sent in order, so break when we haven't waited long enough // to lose any more packets and leave the loss_time_ set for the timeout. - QuicTime when_lost = it->sent_time.Add(loss_delay); + QuicTime when_lost = it->second.sent_time.Add(loss_delay); if (time < when_lost) { loss_detection_timeout_ = when_lost; break; } - lost_packets.insert(sequence_number); + lost_packets.insert(it->first); } return lost_packets; diff --git a/net/quic/quic_connection.cc b/net/quic/quic_connection.cc index 872c435..ab1e0fe 100644 --- a/net/quic/quic_connection.cc +++ b/net/quic/quic_connection.cc @@ -154,14 +154,35 @@ class PingAlarm : public QuicAlarm::Delegate { DISALLOW_COPY_AND_ASSIGN(PingAlarm); }; +QuicConnection::PacketType GetPacketType( + const RetransmittableFrames* retransmittable_frames) { + if (!retransmittable_frames) { + return QuicConnection::NORMAL; + } + for (size_t i = 0; i < retransmittable_frames->frames().size(); ++i) { + if (retransmittable_frames->frames()[i].type == CONNECTION_CLOSE_FRAME) { + return QuicConnection::CONNECTION_CLOSE; + } + } + return QuicConnection::NORMAL; +} + } // namespace QuicConnection::QueuedPacket::QueuedPacket(SerializedPacket packet, EncryptionLevel level, TransmissionType transmission_type) - : serialized_packet(packet), + : sequence_number(packet.sequence_number), + packet(packet.packet), encryption_level(level), - transmission_type(transmission_type) { + transmission_type(transmission_type), + retransmittable((transmission_type != NOT_RETRANSMISSION || + packet.retransmittable_frames != NULL) ? + HAS_RETRANSMITTABLE_DATA : NO_RETRANSMITTABLE_DATA), + handshake(packet.retransmittable_frames == NULL ? + NOT_HANDSHAKE : packet.retransmittable_frames->HasCryptoHandshake()), + type(GetPacketType(packet.retransmittable_frames)), + length(packet.packet->length()) { } #define ENDPOINT (is_server_ ? "Server: " : " Client: ") @@ -241,7 +262,7 @@ QuicConnection::~QuicConnection() { STLDeleteValues(&group_map_); for (QueuedPacketList::iterator it = queued_packets_.begin(); it != queued_packets_.end(); ++it) { - delete it->serialized_packet.packet; + delete it->packet; } } @@ -279,15 +300,13 @@ void QuicConnection::OnError(QuicFramer* framer) { void QuicConnection::OnPacket() { DCHECK(last_stream_frames_.empty() && - last_ack_frames_.empty() && - last_congestion_frames_.empty() && - last_stop_waiting_frames_.empty() && - last_rst_frames_.empty() && last_goaway_frames_.empty() && last_window_update_frames_.empty() && last_blocked_frames_.empty() && - last_ping_frames_.empty() && - last_close_frames_.empty()); + last_rst_frames_.empty() && + last_ack_frames_.empty() && + last_congestion_frames_.empty() && + last_stop_waiting_frames_.empty()); } void QuicConnection::OnPublicResetPacket( @@ -344,9 +363,6 @@ bool QuicConnection::OnProtocolVersionMismatch(QuicVersion received_version) { version_negotiation_state_ = NEGOTIATED_VERSION; visitor_->OnSuccessfulVersionNegotiation(received_version); - if (debug_visitor_.get() != NULL) { - debug_visitor_->OnSuccessfulVersionNegotiation(received_version); - } DVLOG(1) << ENDPOINT << "version negotiated " << received_version; // Store the new version. @@ -473,9 +489,6 @@ bool QuicConnection::OnPacketHeader(const QuicPacketHeader& header) { DCHECK_EQ(header.public_header.versions[0], version()); version_negotiation_state_ = NEGOTIATED_VERSION; visitor_->OnSuccessfulVersionNegotiation(version()); - if (debug_visitor_.get() != NULL) { - debug_visitor_->OnSuccessfulVersionNegotiation(version()); - } } } else { DCHECK(!header.public_header.version_flag); @@ -484,9 +497,6 @@ bool QuicConnection::OnPacketHeader(const QuicPacketHeader& header) { packet_generator_.StopSendingVersion(); version_negotiation_state_ = NEGOTIATED_VERSION; visitor_->OnSuccessfulVersionNegotiation(version()); - if (debug_visitor_.get() != NULL) { - debug_visitor_->OnSuccessfulVersionNegotiation(version()); - } } } @@ -607,7 +617,6 @@ bool QuicConnection::OnPingFrame(const QuicPingFrame& frame) { if (debug_visitor_.get() != NULL) { debug_visitor_->OnPingFrame(frame); } - last_ping_frames_.push_back(frame); return true; } @@ -769,17 +778,17 @@ void QuicConnection::OnPacketComplete() { DVLOG(1) << ENDPOINT << (last_packet_revived_ ? "Revived" : "Got") << " packet " << last_header_.packet_sequence_number - << " with " << last_stream_frames_.size()<< " stream frames " - << last_ack_frames_.size() << " acks, " + << " with " << last_ack_frames_.size() << " acks, " << last_congestion_frames_.size() << " congestions, " << last_stop_waiting_frames_.size() << " stop_waiting, " - << last_rst_frames_.size() << " rsts, " << last_goaway_frames_.size() << " goaways, " << last_window_update_frames_.size() << " window updates, " << last_blocked_frames_.size() << " blocked, " - << last_ping_frames_.size() << " pings, " + << last_rst_frames_.size() << " rsts, " << last_close_frames_.size() << " closes, " - << "for " << last_header_.public_header.connection_id; + << last_stream_frames_.size() + << " stream frames for " + << last_header_.public_header.connection_id; // Call MaybeQueueAck() before recording the received packet, since we want // to trigger an ack if the newly received packet was previously missing. @@ -872,15 +881,13 @@ void QuicConnection::MaybeQueueAck() { void QuicConnection::ClearLastFrames() { last_stream_frames_.clear(); - last_ack_frames_.clear(); - last_congestion_frames_.clear(); - last_stop_waiting_frames_.clear(); - last_rst_frames_.clear(); last_goaway_frames_.clear(); last_window_update_frames_.clear(); last_blocked_frames_.clear(); - last_ping_frames_.clear(); - last_close_frames_.clear(); + last_rst_frames_.clear(); + last_ack_frames_.clear(); + last_stop_waiting_frames_.clear(); + last_congestion_frames_.clear(); } QuicAckFrame* QuicConnection::CreateAckFrame() { @@ -906,8 +913,7 @@ bool QuicConnection::ShouldLastPacketInstigateAck() const { !last_goaway_frames_.empty() || !last_rst_frames_.empty() || !last_window_update_frames_.empty() || - !last_blocked_frames_.empty() || - !last_ping_frames_.empty()) { + !last_blocked_frames_.empty()) { return true; } @@ -1209,7 +1215,7 @@ void QuicConnection::WriteQueuedPackets() { while (!writer_->IsWriteBlocked() && packet_iterator != queued_packets_.end()) { if (WritePacket(*packet_iterator)) { - delete packet_iterator->serialized_packet.packet; + delete packet_iterator->packet; packet_iterator = queued_packets_.erase(packet_iterator); } else { // Continue, because some queued packets may still be writable. @@ -1225,7 +1231,8 @@ void QuicConnection::WritePendingRetransmissions() { while (sent_packet_manager_.HasPendingRetransmissions()) { const QuicSentPacketManager::PendingRetransmission pending = sent_packet_manager_.NextPendingRetransmission(); - if (!CanWrite(HAS_RETRANSMITTABLE_DATA)) { + if (GetPacketType(&pending.retransmittable_frames) == NORMAL && + !CanWrite(HAS_RETRANSMITTABLE_DATA)) { break; } @@ -1310,24 +1317,31 @@ bool QuicConnection::CanWrite(HasRetransmittableData retransmittable) { } bool QuicConnection::WritePacket(QueuedPacket packet) { - QuicPacketSequenceNumber sequence_number = - packet.serialized_packet.sequence_number; + QuicPacketSequenceNumber sequence_number = packet.sequence_number; if (ShouldDiscardPacket(packet.encryption_level, sequence_number, - IsRetransmittable(packet))) { + packet.retransmittable)) { ++stats_.packets_discarded; return true; } + // If the packet is CONNECTION_CLOSE, we need to try to send it immediately + // and encrypt it to hand it off to TimeWaitListManager. + // If the packet is QUEUED, we don't re-consult the congestion control. + // This ensures packets are sent in sequence number order. + // TODO(ianswett): The congestion control should have been consulted before + // serializing the packet, so this could be turned into a LOG_IF(DFATAL). + if (packet.type == NORMAL && !CanWrite(packet.retransmittable)) { + return false; + } + // Some encryption algorithms require the packet sequence numbers not be // repeated. DCHECK_LE(sequence_number_of_last_sent_packet_, sequence_number); sequence_number_of_last_sent_packet_ = sequence_number; QuicEncryptedPacket* encrypted = framer_.EncryptPacket( - packet.encryption_level, - sequence_number, - *packet.serialized_packet.packet); + packet.encryption_level, sequence_number, *packet.packet); if (encrypted == NULL) { LOG(DFATAL) << ENDPOINT << "Failed to encrypt packet number " << sequence_number; @@ -1339,7 +1353,7 @@ bool QuicConnection::WritePacket(QueuedPacket packet) { // Connection close packets are eventually owned by TimeWaitListManager. // Others are deleted at the end of this call. scoped_ptr<QuicEncryptedPacket> encrypted_deleter; - if (IsConnectionClose(packet)) { + if (packet.type == CONNECTION_CLOSE) { DCHECK(connection_close_packet_.get() == NULL); connection_close_packet_.reset(encrypted); // This assures we won't try to write *forced* packets when blocked. @@ -1356,19 +1370,16 @@ bool QuicConnection::WritePacket(QueuedPacket packet) { DCHECK_LE(encrypted->length(), kMaxPacketSize); } DCHECK_LE(encrypted->length(), packet_generator_.max_packet_length()); - DVLOG(1) << ENDPOINT << "Sending packet " << sequence_number << " : " - << (packet.serialized_packet.packet->is_fec_packet() ? "FEC " : - (IsRetransmittable(packet) == HAS_RETRANSMITTABLE_DATA - ? "data bearing " : " ack only ")) + DVLOG(1) << ENDPOINT << "Sending packet " << sequence_number + << " : " << (packet.packet->is_fec_packet() ? "FEC " : + (packet.retransmittable == HAS_RETRANSMITTABLE_DATA + ? "data bearing " : " ack only ")) << ", encryption level: " << QuicUtils::EncryptionLevelToString(packet.encryption_level) - << ", length:" - << packet.serialized_packet.packet->length() - << ", encrypted length:" + << ", length:" << packet.packet->length() << ", encrypted length:" << encrypted->length(); DVLOG(2) << ENDPOINT << "packet(" << sequence_number << "): " << std::endl - << QuicUtils::StringToHexASCIIDump( - packet.serialized_packet.packet->AsStringPiece()); + << QuicUtils::StringToHexASCIIDump(packet.packet->AsStringPiece()); WriteResult result = writer_->WritePacket(encrypted->data(), encrypted->length(), @@ -1411,12 +1422,12 @@ bool QuicConnection::WritePacket(QueuedPacket packet) { sent_packet_manager_.least_packet_awaited_by_peer(), sent_packet_manager_.GetCongestionWindow()); - bool reset_retransmission_alarm = sent_packet_manager_.OnPacketSent( - sequence_number, - now, - encrypted->length(), - packet.transmission_type, - IsRetransmittable(packet)); + bool reset_retransmission_alarm = + sent_packet_manager_.OnPacketSent(sequence_number, + now, + encrypted->length(), + packet.transmission_type, + packet.retransmittable); if (reset_retransmission_alarm || !retransmission_alarm_->IsSet()) { retransmission_alarm_->Update(sent_packet_manager_.GetRetransmissionTime(), @@ -1512,7 +1523,6 @@ void QuicConnection::OnHandshakeComplete() { bool QuicConnection::SendOrQueuePacket(EncryptionLevel level, const SerializedPacket& packet, TransmissionType transmission_type) { - // The caller of this function is responsible for checking CanWrite(). if (packet.packet == NULL) { LOG(DFATAL) << "NULL packet passed in to SendOrQueuePacket"; return true; @@ -1523,12 +1533,12 @@ bool QuicConnection::SendOrQueuePacket(EncryptionLevel level, QueuedPacket queued_packet(packet, level, transmission_type); // If there are already queued packets, put this at the end, // unless it's ConnectionClose, in which case it is written immediately. - if ((IsConnectionClose(queued_packet) - || queued_packets_.empty()) && + if ((queued_packet.type == CONNECTION_CLOSE || queued_packets_.empty()) && WritePacket(queued_packet)) { delete packet.packet; return true; } + queued_packet.type = QUEUED; queued_packets_.push_back(queued_packet); return false; } @@ -1981,31 +1991,4 @@ QuicConnection::ScopedPacketBundler::~ScopedPacketBundler() { connection_->packet_generator_.InBatchMode()); } -HasRetransmittableData QuicConnection::IsRetransmittable( - QueuedPacket packet) { - // TODO(cyr): Understand why the first check here is necessary. Without it, - // DiscardRetransmit test fails. - if (packet.transmission_type != NOT_RETRANSMISSION || - packet.serialized_packet.retransmittable_frames != NULL) { - return HAS_RETRANSMITTABLE_DATA; - } else { - return NO_RETRANSMITTABLE_DATA; - } -} - -bool QuicConnection::IsConnectionClose( - QueuedPacket packet) { - RetransmittableFrames* retransmittable_frames = - packet.serialized_packet.retransmittable_frames; - if (!retransmittable_frames) { - return false; - } - for (size_t i = 0; i < retransmittable_frames->frames().size(); ++i) { - if (retransmittable_frames->frames()[i].type == CONNECTION_CLOSE_FRAME) { - return true; - } - } - return false; -} - } // namespace net diff --git a/net/quic/quic_connection.h b/net/quic/quic_connection.h index 3b84205..0f08353 100644 --- a/net/quic/quic_connection.h +++ b/net/quic/quic_connection.h @@ -204,9 +204,6 @@ class NET_EXPORT_PRIVATE QuicConnectionDebugVisitor // Called when the connection is closed. virtual void OnConnectionClosed(QuicErrorCode error, bool from_peer) {} - - // Called when the version negotiation is successful. - virtual void OnSuccessfulVersionNegotiation(const QuicVersion& version) {} }; class NET_EXPORT_PRIVATE QuicConnectionHelperInterface { @@ -231,6 +228,12 @@ class NET_EXPORT_PRIVATE QuicConnection public QuicPacketGenerator::DelegateInterface, public QuicSentPacketManager::NetworkChangeVisitor { public: + enum PacketType { + NORMAL, + QUEUED, + CONNECTION_CLOSE + }; + enum AckBundling { NO_ACK = 0, SEND_ACK = 1, @@ -564,9 +567,14 @@ class NET_EXPORT_PRIVATE QuicConnection EncryptionLevel level, TransmissionType transmission_type); - SerializedPacket serialized_packet; + QuicPacketSequenceNumber sequence_number; + QuicPacket* packet; const EncryptionLevel encryption_level; TransmissionType transmission_type; + HasRetransmittableData retransmittable; + IsHandshake handshake; + PacketType type; + QuicByteCount length; }; typedef std::list<QueuedPacket> QueuedPacketList; @@ -657,9 +665,6 @@ class NET_EXPORT_PRIVATE QuicConnection void CheckForAddressMigration(const IPEndPoint& self_address, const IPEndPoint& peer_address); - HasRetransmittableData IsRetransmittable(QueuedPacket packet); - bool IsConnectionClose(QueuedPacket packet); - QuicFramer framer_; QuicConnectionHelperInterface* helper_; // Not owned. QuicPacketWriter* writer_; // Owned or not depending on |owns_writer_|. @@ -688,7 +693,6 @@ class NET_EXPORT_PRIVATE QuicConnection std::vector<QuicGoAwayFrame> last_goaway_frames_; std::vector<QuicWindowUpdateFrame> last_window_update_frames_; std::vector<QuicBlockedFrame> last_blocked_frames_; - std::vector<QuicPingFrame> last_ping_frames_; std::vector<QuicConnectionCloseFrame> last_close_frames_; QuicCongestionFeedbackFrame outgoing_congestion_feedback_; diff --git a/net/quic/quic_connection_logger.h b/net/quic/quic_connection_logger.h index 8e81dd9..afb6043 100644 --- a/net/quic/quic_connection_logger.h +++ b/net/quic/quic_connection_logger.h @@ -68,13 +68,12 @@ class NET_EXPORT_PRIVATE QuicConnectionLogger virtual void OnRevivedPacket(const QuicPacketHeader& revived_header, base::StringPiece payload) OVERRIDE; virtual void OnConnectionClosed(QuicErrorCode error, bool from_peer) OVERRIDE; - virtual void OnSuccessfulVersionNegotiation( - const QuicVersion& version) OVERRIDE; void OnCryptoHandshakeMessageReceived( const CryptoHandshakeMessage& message); void OnCryptoHandshakeMessageSent( const CryptoHandshakeMessage& message); + void OnSuccessfulVersionNegotiation(const QuicVersion& version); void UpdateReceivedFrameCounts(QuicStreamId stream_id, int num_frames_received, int num_duplicate_frames_received); diff --git a/net/quic/quic_connection_test.cc b/net/quic/quic_connection_test.cc index 986cf45..5befba7 100644 --- a/net/quic/quic_connection_test.cc +++ b/net/quic/quic_connection_test.cc @@ -733,13 +733,6 @@ class QuicConnectionTest : public ::testing::TestWithParam<QuicVersion> { return encrypted->length(); } - void ProcessPingPacket(QuicPacketSequenceNumber number) { - scoped_ptr<QuicPacket> packet(ConstructPingPacket(number)); - scoped_ptr<QuicEncryptedPacket> encrypted(framer_.EncryptPacket( - ENCRYPTION_NONE, number, *packet)); - connection_.ProcessUdpPacket(IPEndPoint(), IPEndPoint(), *encrypted); - } - void ProcessClosePacket(QuicPacketSequenceNumber number, QuicFecGroupNumber fec_group) { scoped_ptr<QuicPacket> packet(ConstructClosePacket(number, fec_group)); @@ -879,27 +872,6 @@ class QuicConnectionTest : public ::testing::TestWithParam<QuicVersion> { return packet; } - QuicPacket* ConstructPingPacket(QuicPacketSequenceNumber number) { - header_.public_header.connection_id = connection_id_; - header_.packet_sequence_number = number; - header_.public_header.reset_flag = false; - header_.public_header.version_flag = false; - header_.entropy_flag = false; - header_.fec_flag = false; - header_.is_in_fec_group = NOT_IN_FEC_GROUP; - header_.fec_group = 0; - - QuicPingFrame ping; - - QuicFrames frames; - QuicFrame frame(&ping); - frames.push_back(frame); - QuicPacket* packet = - BuildUnsizedDataPacket(&framer_, header_, frames).packet; - EXPECT_TRUE(packet != NULL); - return packet; - } - QuicPacket* ConstructClosePacket(QuicPacketSequenceNumber number, QuicFecGroupNumber fec_group) { header_.public_header.connection_id = connection_id_; @@ -1400,10 +1372,7 @@ TEST_P(QuicConnectionTest, SendingDifferentSequenceNumberLengthsBandwidth) { writer_->header().public_header.sequence_number_length); } -// TODO(ianswett): Re-enable this test by finding a good way to test different -// sequence number lengths without sending packets with giant gaps. -TEST_P(QuicConnectionTest, - DISABLED_SendingDifferentSequenceNumberLengthsUnackedDelta) { +TEST_P(QuicConnectionTest, SendingDifferentSequenceNumberLengthsUnackedDelta) { QuicPacketSequenceNumber last_packet; QuicPacketCreator* creator = QuicConnectionPeer::GetPacketCreator(&connection_); @@ -2742,21 +2711,162 @@ TEST_P(QuicConnectionTest, TimeoutAfterSend) { TEST_P(QuicConnectionTest, SendScheduler) { // Test that if we send a packet without delay, it is not queued. QuicPacket* packet = ConstructDataPacket(1, 0, !kEntropyFlag); + EXPECT_CALL(*send_algorithm_, + TimeUntilSend(_, _, _)).WillOnce( + testing::Return(QuicTime::Delta::Zero())); EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)); connection_.SendPacket( ENCRYPTION_NONE, 1, packet, kTestEntropyHash, HAS_RETRANSMITTABLE_DATA); EXPECT_EQ(0u, connection_.NumQueuedPackets()); } +TEST_P(QuicConnectionTest, SendSchedulerDelay) { + // Test that if we send a packet with a delay, it ends up queued. + QuicPacket* packet = ConstructDataPacket(1, 0, !kEntropyFlag); + EXPECT_CALL(*send_algorithm_, + TimeUntilSend(_, _, _)).WillOnce( + testing::Return(QuicTime::Delta::FromMicroseconds(1))); + EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, 1, _, _)).Times(0); + connection_.SendPacket( + ENCRYPTION_NONE, 1, packet, kTestEntropyHash, HAS_RETRANSMITTABLE_DATA); + EXPECT_EQ(1u, connection_.NumQueuedPackets()); +} + TEST_P(QuicConnectionTest, SendSchedulerEAGAIN) { QuicPacket* packet = ConstructDataPacket(1, 0, !kEntropyFlag); BlockOnNextWrite(); + EXPECT_CALL(*send_algorithm_, + TimeUntilSend(_, _, _)).WillOnce( + testing::Return(QuicTime::Delta::Zero())); EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, 1, _, _)).Times(0); connection_.SendPacket( ENCRYPTION_NONE, 1, packet, kTestEntropyHash, HAS_RETRANSMITTABLE_DATA); EXPECT_EQ(1u, connection_.NumQueuedPackets()); } +TEST_P(QuicConnectionTest, SendSchedulerDelayThenSend) { + // Test that if we send a packet with a delay, it ends up queued. + QuicPacket* packet = ConstructDataPacket(1, 0, !kEntropyFlag); + EXPECT_CALL(*send_algorithm_, + TimeUntilSend(_, _, _)).WillOnce( + testing::Return(QuicTime::Delta::FromMicroseconds(1))); + connection_.SendPacket( + ENCRYPTION_NONE, 1, packet, kTestEntropyHash, HAS_RETRANSMITTABLE_DATA); + EXPECT_EQ(1u, connection_.NumQueuedPackets()); + + // Advance the clock to fire the alarm, and configure the scheduler + // to permit the packet to be sent. + EXPECT_CALL(*send_algorithm_, + TimeUntilSend(_, _, _)).WillRepeatedly( + testing::Return(QuicTime::Delta::Zero())); + clock_.AdvanceTime(QuicTime::Delta::FromMicroseconds(1)); + EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)); + connection_.GetSendAlarm()->Fire(); + EXPECT_EQ(0u, connection_.NumQueuedPackets()); +} + +TEST_P(QuicConnectionTest, SendSchedulerDelayThenRetransmit) { + CongestionUnblockWrites(); + EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, 1, _, _)); + connection_.SendStreamDataWithString(3, "foo", 0, !kFin, NULL); + EXPECT_EQ(0u, connection_.NumQueuedPackets()); + // Advance the time for retransmission of lost packet. + clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(501)); + // Test that if we send a retransmit with a delay, it ends up queued in the + // sent packet manager, but not yet serialized. + EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout(true)); + CongestionBlockWrites(); + connection_.GetRetransmissionAlarm()->Fire(); + EXPECT_EQ(0u, connection_.NumQueuedPackets()); + + // Advance the clock to fire the alarm, and configure the scheduler + // to permit the packet to be sent. + CongestionUnblockWrites(); + + // Ensure the scheduler is notified this is a retransmit. + EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)); + clock_.AdvanceTime(QuicTime::Delta::FromMicroseconds(1)); + connection_.GetSendAlarm()->Fire(); + EXPECT_EQ(0u, connection_.NumQueuedPackets()); +} + +TEST_P(QuicConnectionTest, SendSchedulerDelayAndQueue) { + QuicPacket* packet = ConstructDataPacket(1, 0, !kEntropyFlag); + EXPECT_CALL(*send_algorithm_, + TimeUntilSend(_, _, _)).WillOnce( + testing::Return(QuicTime::Delta::FromMicroseconds(1))); + connection_.SendPacket( + ENCRYPTION_NONE, 1, packet, kTestEntropyHash, HAS_RETRANSMITTABLE_DATA); + EXPECT_EQ(1u, connection_.NumQueuedPackets()); + + // Attempt to send another packet and make sure that it gets queued. + packet = ConstructDataPacket(2, 0, !kEntropyFlag); + connection_.SendPacket( + ENCRYPTION_NONE, 2, packet, kTestEntropyHash, HAS_RETRANSMITTABLE_DATA); + EXPECT_EQ(2u, connection_.NumQueuedPackets()); +} + +TEST_P(QuicConnectionTest, SendSchedulerDelayThenAckAndSend) { + EXPECT_CALL(visitor_, OnSuccessfulVersionNegotiation(_)); + QuicPacket* packet = ConstructDataPacket(1, 0, !kEntropyFlag); + EXPECT_CALL(*send_algorithm_, + TimeUntilSend(_, _, _)).WillOnce( + testing::Return(QuicTime::Delta::FromMicroseconds(10))); + connection_.SendPacket( + ENCRYPTION_NONE, 1, packet, kTestEntropyHash, HAS_RETRANSMITTABLE_DATA); + EXPECT_EQ(1u, connection_.NumQueuedPackets()); + + // Now send non-retransmitting information, that we're not going to + // retransmit 3. The far end should stop waiting for it. + QuicAckFrame frame = InitAckFrame(0); + EXPECT_CALL(*send_algorithm_, + TimeUntilSend(_, _, _)).WillRepeatedly( + testing::Return(QuicTime::Delta::Zero())); + EXPECT_CALL(*send_algorithm_, + OnPacketSent(_, _, _, _, _)); + ProcessAckPacket(&frame); + + EXPECT_EQ(0u, connection_.NumQueuedPackets()); + // Ensure alarm is not set + EXPECT_FALSE(connection_.GetSendAlarm()->IsSet()); +} + +TEST_P(QuicConnectionTest, SendSchedulerDelayThenAckAndHold) { + EXPECT_CALL(visitor_, OnSuccessfulVersionNegotiation(_)); + QuicPacket* packet = ConstructDataPacket(1, 0, !kEntropyFlag); + EXPECT_CALL(*send_algorithm_, + TimeUntilSend(_, _, _)).WillOnce( + testing::Return(QuicTime::Delta::FromMicroseconds(10))); + connection_.SendPacket( + ENCRYPTION_NONE, 1, packet, kTestEntropyHash, HAS_RETRANSMITTABLE_DATA); + EXPECT_EQ(1u, connection_.NumQueuedPackets()); + + // Now send non-retransmitting information, that we're not going to + // retransmit 3. The far end should stop waiting for it. + QuicAckFrame frame = InitAckFrame(0); + EXPECT_CALL(*send_algorithm_, + TimeUntilSend(_, _, _)).WillOnce( + testing::Return(QuicTime::Delta::FromMicroseconds(1))); + ProcessAckPacket(&frame); + + EXPECT_EQ(1u, connection_.NumQueuedPackets()); +} + +TEST_P(QuicConnectionTest, SendSchedulerDelayThenOnCanWrite) { + // TODO(ianswett): This test is unrealistic, because we would not serialize + // new data if the send algorithm said not to. + QuicPacket* packet = ConstructDataPacket(1, 0, !kEntropyFlag); + CongestionBlockWrites(); + connection_.SendPacket( + ENCRYPTION_NONE, 1, packet, kTestEntropyHash, HAS_RETRANSMITTABLE_DATA); + EXPECT_EQ(1u, connection_.NumQueuedPackets()); + + // OnCanWrite should send the packet, because it won't consult the send + // algorithm for queued packets. + connection_.OnCanWrite(); + EXPECT_EQ(0u, connection_.NumQueuedPackets()); +} + TEST_P(QuicConnectionTest, TestQueueLimitsOnSendStreamData) { // All packets carry version info till version is negotiated. size_t payload_length; @@ -2857,16 +2967,6 @@ TEST_P(QuicConnectionTest, SendDelayedAckOnSecondPacket) { EXPECT_FALSE(connection_.GetAckAlarm()->IsSet()); } -TEST_P(QuicConnectionTest, SendDelayedAckForPing) { - if (version() < QUIC_VERSION_18) { - return; - } - EXPECT_CALL(visitor_, OnSuccessfulVersionNegotiation(_)); - EXPECT_FALSE(connection_.GetAckAlarm()->IsSet()); - ProcessPingPacket(1); - EXPECT_TRUE(connection_.GetAckAlarm()->IsSet()); -} - TEST_P(QuicConnectionTest, NoAckOnOldNacks) { EXPECT_CALL(visitor_, OnSuccessfulVersionNegotiation(_)); // Drop one packet, triggering a sequence of acks. diff --git a/net/quic/quic_crypto_server_stream.cc b/net/quic/quic_crypto_server_stream.cc index 8bd1ae2..abf4bee 100644 --- a/net/quic/quic_crypto_server_stream.cc +++ b/net/quic/quic_crypto_server_stream.cc @@ -158,8 +158,7 @@ void QuicCryptoServerStream::FinishProcessingHandshakeMessage( void QuicCryptoServerStream::SendServerConfigUpdate( const CachedNetworkParameters* cached_network_params) { - if (session()->connection()->version() <= QUIC_VERSION_21 || - !handshake_confirmed_) { + if (session()->connection()->version() <= QUIC_VERSION_21) { return; } diff --git a/net/quic/quic_crypto_server_stream_test.cc b/net/quic/quic_crypto_server_stream_test.cc index 7c529af..98492f1 100644 --- a/net/quic/quic_crypto_server_stream_test.cc +++ b/net/quic/quic_crypto_server_stream_test.cc @@ -275,12 +275,6 @@ TEST_P(QuicCryptoServerStreamTest, ChannelIDAsync) { EXPECT_TRUE(stream_.handshake_confirmed()); } -TEST_P(QuicCryptoServerStreamTest, OnlySendSCUPAfterHandshakeComplete) { - // An attempt to send a SCUP before completing handshake should fail. - stream_.SendServerConfigUpdate(NULL); - EXPECT_EQ(0, stream_.num_server_config_update_messages_sent()); -} - } // namespace } // namespace test } // namespace net diff --git a/net/quic/quic_protocol.cc b/net/quic/quic_protocol.cc index 545d8ec..314f0ff 100644 --- a/net/quic/quic_protocol.cc +++ b/net/quic/quic_protocol.cc @@ -726,6 +726,7 @@ TransmissionInfo::TransmissionInfo() TransmissionInfo::TransmissionInfo( RetransmittableFrames* retransmittable_frames, + QuicPacketSequenceNumber sequence_number, QuicSequenceNumberLength sequence_number_length) : retransmittable_frames(retransmittable_frames), sequence_number_length(sequence_number_length), @@ -733,14 +734,17 @@ TransmissionInfo::TransmissionInfo( bytes_sent(0), nack_count(0), transmission_type(NOT_RETRANSMISSION), - all_transmissions(NULL), - in_flight(false) {} + all_transmissions(new SequenceNumberSet), + in_flight(false) { + all_transmissions->insert(sequence_number); +} TransmissionInfo::TransmissionInfo( RetransmittableFrames* retransmittable_frames, + QuicPacketSequenceNumber sequence_number, QuicSequenceNumberLength sequence_number_length, TransmissionType transmission_type, - SequenceNumberList* all_transmissions) + SequenceNumberSet* all_transmissions) : retransmittable_frames(retransmittable_frames), sequence_number_length(sequence_number_length), sent_time(QuicTime::Zero()), @@ -748,6 +752,8 @@ TransmissionInfo::TransmissionInfo( nack_count(0), transmission_type(transmission_type), all_transmissions(all_transmissions), - in_flight(false) {} + in_flight(false) { + all_transmissions->insert(sequence_number); +} } // namespace net diff --git a/net/quic/quic_protocol.h b/net/quic/quic_protocol.h index a15c912..0d9fb84 100644 --- a/net/quic/quic_protocol.h +++ b/net/quic/quic_protocol.h @@ -647,7 +647,6 @@ struct NET_EXPORT_PRIVATE QuicStreamFrame { // TODO(ianswett): Re-evaluate the trade-offs of hash_set vs set when framing // is finalized. typedef std::set<QuicPacketSequenceNumber> SequenceNumberSet; -typedef std::list<QuicPacketSequenceNumber> SequenceNumberList; typedef std::list<std::pair<QuicPacketSequenceNumber, QuicTime>> PacketTimeList; @@ -1054,14 +1053,16 @@ struct NET_EXPORT_PRIVATE TransmissionInfo { // Constructs a Transmission with a new all_tranmissions set // containing |sequence_number|. TransmissionInfo(RetransmittableFrames* retransmittable_frames, + QuicPacketSequenceNumber sequence_number, QuicSequenceNumberLength sequence_number_length); // Constructs a Transmission with the specified |all_tranmissions| set // and inserts |sequence_number| into it. TransmissionInfo(RetransmittableFrames* retransmittable_frames, + QuicPacketSequenceNumber sequence_number, QuicSequenceNumberLength sequence_number_length, TransmissionType transmission_type, - SequenceNumberList* all_transmissions); + SequenceNumberSet* all_transmissions); RetransmittableFrames* retransmittable_frames; QuicSequenceNumberLength sequence_number_length; @@ -1074,7 +1075,7 @@ struct NET_EXPORT_PRIVATE TransmissionInfo { TransmissionType transmission_type; // Stores the sequence numbers of all transmissions of this packet. // Can never be null. - SequenceNumberList* all_transmissions; + SequenceNumberSet* all_transmissions; // In flight packets have not been abandoned or lost. bool in_flight; }; diff --git a/net/quic/quic_sent_entropy_manager.cc b/net/quic/quic_sent_entropy_manager.cc index 206a9ff..ff19a02 100644 --- a/net/quic/quic_sent_entropy_manager.cc +++ b/net/quic/quic_sent_entropy_manager.cc @@ -48,7 +48,7 @@ void QuicSentEntropyManager::RecordPacketEntropyHash( // Ensure packets always are recorded in order. // Every packet's entropy is recorded, even if it's not sent, so there // are not sequence number gaps. - DCHECK_EQ(GetLargestPacketWithEntropy() + 1, sequence_number); + DCHECK_LT(GetLargestPacketWithEntropy(), sequence_number); } packets_entropy_.push_back(entropy_hash); DVLOG(2) << "Recorded sequence number " << sequence_number diff --git a/net/quic/quic_sent_packet_manager.cc b/net/quic/quic_sent_packet_manager.cc index c592e133..21a4fbc 100644 --- a/net/quic/quic_sent_packet_manager.cc +++ b/net/quic/quic_sent_packet_manager.cc @@ -144,11 +144,8 @@ void QuicSentPacketManager::OnSerializedPacket( if (serialized_packet.retransmittable_frames) { ack_notifier_manager_.OnSerializedPacket(serialized_packet); } - unacked_packets_.AddPacket(serialized_packet); - if (debug_delegate_ != NULL) { - debug_delegate_->OnSerializedPacket(serialized_packet); - } + unacked_packets_.AddPacket(serialized_packet); } void QuicSentPacketManager::OnRetransmittedPacket( @@ -197,7 +194,6 @@ void QuicSentPacketManager::OnIncomingAck(const QuicAckFrame& ack_frame, HandleAckForSentPackets(ack_frame); InvokeLossDetection(ack_receive_time); MaybeInvokeCongestionEvent(largest_observed_acked, bytes_in_flight); - unacked_packets_.RemoveObsoletePackets(); sustained_bandwidth_recorder_.RecordEstimate( send_algorithm_->InRecovery(), @@ -261,15 +257,15 @@ void QuicSentPacketManager::HandleAckForSentPackets( // incoming_ack shows they've been seen by the peer. QuicTime::Delta delta_largest_observed = ack_frame.delta_time_largest_observed; - QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked(); - for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++sequence_number) { + QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); + while (it != unacked_packets_.end()) { + QuicPacketSequenceNumber sequence_number = it->first; if (sequence_number > ack_frame.largest_observed) { // These packets are still in flight. break; } - if (ContainsKey(ack_frame.missing_packets, sequence_number)) { + if (IsAwaitingPacket(ack_frame, sequence_number)) { // Consider it multiple nacks when there is a gap between the missing // packet and the largest observed, since the purpose of a nack // threshold is to tolerate re-ordering. This handles both StretchAcks @@ -281,16 +277,17 @@ void QuicSentPacketManager::HandleAckForSentPackets( min_nacks = 1; } unacked_packets_.NackPacket(sequence_number, min_nacks); + ++it; continue; } // Packet was acked, so remove it from our unacked packet list. DVLOG(1) << ENDPOINT << "Got an ack for packet " << sequence_number; // If data is associated with the most recent transmission of this // packet, then inform the caller. - if (it->in_flight) { - packets_acked_[sequence_number] = *it; + if (it->second.in_flight) { + packets_acked_[sequence_number] = it->second; } - MarkPacketHandled(sequence_number, *it, delta_largest_observed); + it = MarkPacketHandled(it, delta_largest_observed); } // Discard any retransmittable frames associated with revived packets. @@ -308,25 +305,26 @@ bool QuicSentPacketManager::HasRetransmittableFrames( void QuicSentPacketManager::RetransmitUnackedPackets( RetransmissionType retransmission_type) { - QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked(); - for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++sequence_number) { - const RetransmittableFrames* frames = it->retransmittable_frames; + QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); + while (it != unacked_packets_.end()) { + const RetransmittableFrames* frames = it->second.retransmittable_frames; // TODO(ianswett): Consider adding a new retransmission type which removes // all these old packets from unacked and retransmits them as new sequence // numbers with no connection to the previous ones. if (frames != NULL && (retransmission_type == ALL_PACKETS || frames->encryption_level() == ENCRYPTION_INITIAL)) { - MarkForRetransmission(sequence_number, ALL_UNACKED_RETRANSMISSION); + MarkForRetransmission(it->first, ALL_UNACKED_RETRANSMISSION); } + ++it; } } void QuicSentPacketManager::NeuterUnencryptedPackets() { - QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked(); - for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++sequence_number) { - const RetransmittableFrames* frames = it->retransmittable_frames; + QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); + while (it != unacked_packets_.end()) { + const RetransmittableFrames* frames = it->second.retransmittable_frames; + QuicPacketSequenceNumber sequence_number = it->first; + ++it; if (frames != NULL && frames->encryption_level() == ENCRYPTION_NONE) { // Once you're forward secure, no unencrypted packets will be sent, crypto // or otherwise. Unencrypted packets are neutered and abandoned, to ensure @@ -334,6 +332,8 @@ void QuicSentPacketManager::NeuterUnencryptedPackets() { // perspective. pending_retransmissions_.erase(sequence_number); unacked_packets_.RemoveFromInFlight(sequence_number); + // RemoveRetransmittibility is safe because only the newest sequence + // number can have frames. unacked_packets_.RemoveRetransmittability(sequence_number); } } @@ -358,7 +358,7 @@ void QuicSentPacketManager::MarkForRetransmission( } void QuicSentPacketManager::RecordSpuriousRetransmissions( - const SequenceNumberList& all_transmissions, + const SequenceNumberSet& all_transmissions, QuicPacketSequenceNumber acked_sequence_number) { if (acked_sequence_number < first_rto_transmission_) { // Cancel all pending RTO transmissions and restore their in flight status. @@ -376,9 +376,11 @@ void QuicSentPacketManager::RecordSpuriousRetransmissions( first_rto_transmission_ = 0; ++stats_->spurious_rto_count; } - for (SequenceNumberList::const_reverse_iterator it = - all_transmissions.rbegin(); - it != all_transmissions.rend() && *it > acked_sequence_number; ++it) { + for (SequenceNumberSet::const_iterator + it = all_transmissions.upper_bound(acked_sequence_number), + end = all_transmissions.end(); + it != end; + ++it) { const TransmissionInfo& retransmit_info = unacked_packets_.GetTransmissionInfo(*it); @@ -436,8 +438,7 @@ void QuicSentPacketManager::MarkPacketRevived( const TransmissionInfo& transmission_info = unacked_packets_.GetTransmissionInfo(sequence_number); QuicPacketSequenceNumber newest_transmission = - transmission_info.all_transmissions == NULL ? - sequence_number : *transmission_info.all_transmissions->rbegin(); + *transmission_info.all_transmissions->rbegin(); // This packet has been revived at the receiver. If we were going to // retransmit it, do not retransmit it anymore. pending_retransmissions_.erase(newest_transmission); @@ -452,36 +453,53 @@ void QuicSentPacketManager::MarkPacketRevived( unacked_packets_.RemoveRetransmittability(sequence_number); } -void QuicSentPacketManager::MarkPacketHandled( - QuicPacketSequenceNumber sequence_number, - const TransmissionInfo& info, +QuicUnackedPacketMap::const_iterator QuicSentPacketManager::MarkPacketHandled( + QuicUnackedPacketMap::const_iterator it, QuicTime::Delta delta_largest_observed) { + LOG_IF(DFATAL, it == unacked_packets_.end()) + << "MarkPacketHandled must be passed a valid iterator entry."; + const QuicPacketSequenceNumber sequence_number = it->first; + const TransmissionInfo& transmission_info = it->second; + QuicPacketSequenceNumber newest_transmission = - info.all_transmissions == NULL ? - sequence_number : *info.all_transmissions->rbegin(); + *transmission_info.all_transmissions->rbegin(); // Remove the most recent packet, if it is pending retransmission. pending_retransmissions_.erase(newest_transmission); - // The AckNotifierManager needs to be notified about the most recent - // transmission, since that's the one only one it tracks. - ack_notifier_manager_.OnPacketAcked(newest_transmission, - delta_largest_observed); - if (newest_transmission != sequence_number) { - RecordSpuriousRetransmissions(*info.all_transmissions, sequence_number); - // Remove the most recent packet from flight if it's a crypto handshake - // packet, since they won't be acked now that one has been processed. - // Other crypto handshake packets won't be in flight, only the newest - // transmission of a crypto packet is in flight at once. - // TODO(ianswett): Instead of handling all crypto packets special, - // only handle NULL encrypted packets in a special way. - if (HasCryptoHandshake( - unacked_packets_.GetTransmissionInfo(newest_transmission))) { - unacked_packets_.RemoveFromInFlight(newest_transmission); + // Notify observers about the ACKed packet. + { + // The AckNotifierManager needs to be notified about the most recent + // transmission, since that's the one only one it tracks. + ack_notifier_manager_.OnPacketAcked(newest_transmission, + delta_largest_observed); + if (newest_transmission != sequence_number) { + RecordSpuriousRetransmissions(*transmission_info.all_transmissions, + sequence_number); } } + // Two cases for MarkPacketHandled: + // 1) Handle the most recent or a crypto packet, so remove all transmissions. + // 2) Handle old transmission, keep all other pending transmissions, + // but disassociate them from one another. + + // If it's a crypto handshake packet, discard it and all retransmissions, + // since they won't be acked now that one has been processed. + // TODO(ianswett): Instead of handling all crypto packets in a special way, + // only handle NULL encrypted packets in a special way. + if (HasCryptoHandshake( + unacked_packets_.GetTransmissionInfo(newest_transmission))) { + unacked_packets_.RemoveFromInFlight(newest_transmission); + } unacked_packets_.RemoveFromInFlight(sequence_number); unacked_packets_.RemoveRetransmittability(sequence_number); + + QuicUnackedPacketMap::const_iterator next_unacked = unacked_packets_.begin(); + while (next_unacked != unacked_packets_.end() && + next_unacked->first <= sequence_number) { + ++next_unacked; + } + return next_unacked; } bool QuicSentPacketManager::IsUnacked( @@ -495,7 +513,7 @@ bool QuicSentPacketManager::HasUnackedPackets() const { QuicPacketSequenceNumber QuicSentPacketManager::GetLeastUnackedSentPacket() const { - return unacked_packets_.GetLeastUnacked(); + return unacked_packets_.GetLeastUnackedSentPacket(); } bool QuicSentPacketManager::OnPacketSent( @@ -529,8 +547,7 @@ bool QuicSentPacketManager::OnPacketSent( unacked_packets_.SetSent(sequence_number, sent_time, bytes, in_flight); if (debug_delegate_ != NULL) { - debug_delegate_->OnSentPacket( - sequence_number, sent_time, bytes, transmission_type); + debug_delegate_->OnSentPacket(sequence_number, sent_time, bytes); } // Reset the retransmission timer anytime a pending packet is sent. @@ -580,12 +597,13 @@ void QuicSentPacketManager::RetransmitCryptoPackets() { min(kMaxHandshakeRetransmissionBackoffs, consecutive_crypto_retransmission_count_ + 1); bool packet_retransmitted = false; - QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked(); for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++sequence_number) { + it != unacked_packets_.end(); ++it) { + QuicPacketSequenceNumber sequence_number = it->first; + const RetransmittableFrames* frames = it->second.retransmittable_frames; // Only retransmit frames which are in flight, and therefore have been sent. - if (!it->in_flight || it->retransmittable_frames == NULL || - it->retransmittable_frames->HasCryptoHandshake() != IS_HANDSHAKE) { + if (!it->second.in_flight || frames == NULL || + frames->HasCryptoHandshake() != IS_HANDSHAKE) { continue; } packet_retransmitted = true; @@ -599,15 +617,16 @@ bool QuicSentPacketManager::MaybeRetransmitTailLossProbe() { if (pending_timer_transmission_count_ == 0) { return false; } - QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked(); for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++sequence_number) { + it != unacked_packets_.end(); ++it) { + QuicPacketSequenceNumber sequence_number = it->first; + const RetransmittableFrames* frames = it->second.retransmittable_frames; // Only retransmit frames which are in flight, and therefore have been sent. - if (!it->in_flight || it->retransmittable_frames == NULL) { + if (!it->second.in_flight || frames == NULL) { continue; } if (!handshake_confirmed_) { - DCHECK_NE(IS_HANDSHAKE, it->retransmittable_frames->HasCryptoHandshake()); + DCHECK_NE(IS_HANDSHAKE, frames->HasCryptoHandshake()); } MarkForRetransmission(sequence_number, TLP_RETRANSMISSION); return true; @@ -619,17 +638,18 @@ bool QuicSentPacketManager::MaybeRetransmitTailLossProbe() { void QuicSentPacketManager::RetransmitAllPackets() { DVLOG(1) << "RetransmitAllPackets() called with " - << unacked_packets_.GetNumUnackedPacketsDebugOnly() - << " unacked packets."; + << unacked_packets_.GetNumUnackedPackets() << " unacked packets."; // Request retransmission of all retransmittable packets when the RTO // fires, and let the congestion manager decide how many to send // immediately and the remaining packets will be queued. // Abandon any non-retransmittable packets that are sufficiently old. bool packets_retransmitted = false; - QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked(); - for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++sequence_number) { - if (it->retransmittable_frames != NULL) { + QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); + while (it != unacked_packets_.end()) { + const RetransmittableFrames* frames = it->second.retransmittable_frames; + QuicPacketSequenceNumber sequence_number = it->first; + ++it; + if (frames != NULL) { packets_retransmitted = true; MarkForRetransmission(sequence_number, RTO_RETRANSMISSION); } else { diff --git a/net/quic/quic_sent_packet_manager.h b/net/quic/quic_sent_packet_manager.h index 84294d1..342dd3d 100644 --- a/net/quic/quic_sent_packet_manager.h +++ b/net/quic/quic_sent_packet_manager.h @@ -5,7 +5,10 @@ #ifndef NET_QUIC_QUIC_SENT_PACKET_MANAGER_H_ #define NET_QUIC_QUIC_SENT_PACKET_MANAGER_H_ +#include <deque> +#include <list> #include <map> +#include <queue> #include <set> #include <utility> #include <vector> @@ -54,8 +57,7 @@ class NET_EXPORT_PRIVATE QuicSentPacketManager { virtual void OnSentPacket( QuicPacketSequenceNumber sequence_number, QuicTime sent_time, - QuicByteCount bytes, - TransmissionType transmission_type) {} + QuicByteCount bytes) {} virtual void OnRetransmittedPacket( QuicPacketSequenceNumber old_sequence_number, @@ -69,9 +71,6 @@ class NET_EXPORT_PRIVATE QuicSentPacketManager { QuicPacketSequenceNumber largest_observed, bool largest_observed_acked, QuicPacketSequenceNumber least_unacked_sent_packet) {} - - virtual void OnSerializedPacket( - const SerializedPacket& packet) {} }; // Interface which gets callbacks from the QuicSentPacketManager when @@ -315,9 +314,9 @@ class NET_EXPORT_PRIVATE QuicSentPacketManager { // Removes the retransmittability and pending properties from the packet at // |it| due to receipt by the peer. Returns an iterator to the next remaining // unacked packet. - void MarkPacketHandled(QuicPacketSequenceNumber sequence_number, - const TransmissionInfo& info, - QuicTime::Delta delta_largest_observed); + QuicUnackedPacketMap::const_iterator MarkPacketHandled( + QuicUnackedPacketMap::const_iterator it, + QuicTime::Delta delta_largest_observed); // Request that |sequence_number| be retransmitted after the other pending // retransmissions. Does not add it to the retransmissions if it's already @@ -327,7 +326,7 @@ class NET_EXPORT_PRIVATE QuicSentPacketManager { // Notify observers about spurious retransmits. void RecordSpuriousRetransmissions( - const SequenceNumberList& all_transmissions, + const SequenceNumberSet& all_transmissions, QuicPacketSequenceNumber acked_sequence_number); // Newly serialized retransmittable and fec packets are added to this map, diff --git a/net/quic/quic_sent_packet_manager_test.cc b/net/quic/quic_sent_packet_manager_test.cc index d00ea09..4054f9b 100644 --- a/net/quic/quic_sent_packet_manager_test.cc +++ b/net/quic/quic_sent_packet_manager_test.cc @@ -1025,8 +1025,8 @@ TEST_F(QuicSentPacketManagerTest, CryptoHandshakeTimeoutUnsentDataPacket) { // Retransmit 2 crypto packets, but not the serialized packet. manager_.OnRetransmissionTimeout(); - RetransmitNextPacket(4); - RetransmitNextPacket(5); + RetransmitNextPacket(6); + RetransmitNextPacket(7); EXPECT_FALSE(manager_.HasPendingRetransmissions()); EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_)); } diff --git a/net/quic/quic_unacked_packet_map.cc b/net/quic/quic_unacked_packet_map.cc index 0640c29..359f2d1 100644 --- a/net/quic/quic_unacked_packet_map.cc +++ b/net/quic/quic_unacked_packet_map.cc @@ -16,20 +16,17 @@ namespace net { QuicUnackedPacketMap::QuicUnackedPacketMap() : largest_sent_packet_(0), largest_observed_(0), - least_unacked_(1), bytes_in_flight_(0), pending_crypto_packet_count_(0) { } QuicUnackedPacketMap::~QuicUnackedPacketMap() { - QuicPacketSequenceNumber index = least_unacked_; for (UnackedPacketMap::iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++index) { - delete it->retransmittable_frames; + it != unacked_packets_.end(); ++it) { + delete it->second.retransmittable_frames; // Only delete all_transmissions once, for the newest packet. - if (it->all_transmissions != NULL && - index == *it->all_transmissions->rbegin()) { - delete it->all_transmissions; + if (it->first == *it->second.all_transmissions->rbegin()) { + delete it->second.all_transmissions; } } } @@ -38,11 +35,19 @@ QuicUnackedPacketMap::~QuicUnackedPacketMap() { // sent in order and the connection tracks RetransmittableFrames for longer. void QuicUnackedPacketMap::AddPacket( const SerializedPacket& serialized_packet) { - DCHECK_EQ(least_unacked_ + unacked_packets_.size(), - serialized_packet.sequence_number); - unacked_packets_.push_back( + if (!unacked_packets_.empty()) { + bool is_old_packet = unacked_packets_.rbegin()->first >= + serialized_packet.sequence_number; + LOG_IF(DFATAL, is_old_packet) << "Old packet serialized: " + << serialized_packet.sequence_number + << " vs: " + << unacked_packets_.rbegin()->first; + } + + unacked_packets_[serialized_packet.sequence_number] = TransmissionInfo(serialized_packet.retransmittable_frames, - serialized_packet.sequence_number_length)); + serialized_packet.sequence_number, + serialized_packet.sequence_number_length); if (serialized_packet.retransmittable_frames != NULL && serialized_packet.retransmittable_frames->HasCryptoHandshake() == IS_HANDSHAKE) { @@ -50,28 +55,17 @@ void QuicUnackedPacketMap::AddPacket( } } -void QuicUnackedPacketMap::RemoveObsoletePackets() { - while (!unacked_packets_.empty()) { - if (!IsPacketUseless(least_unacked_, unacked_packets_.front())) { - break; - } - delete unacked_packets_.front().all_transmissions; - unacked_packets_.pop_front(); - ++least_unacked_; - } -} - void QuicUnackedPacketMap::OnRetransmittedPacket( QuicPacketSequenceNumber old_sequence_number, QuicPacketSequenceNumber new_sequence_number, TransmissionType transmission_type) { - DCHECK_GE(old_sequence_number, least_unacked_); - DCHECK_LT(old_sequence_number, least_unacked_ + unacked_packets_.size()); - DCHECK_EQ(least_unacked_ + unacked_packets_.size(), new_sequence_number); + DCHECK(ContainsKey(unacked_packets_, old_sequence_number)); + DCHECK(unacked_packets_.empty() || + unacked_packets_.rbegin()->first < new_sequence_number); // TODO(ianswett): Discard and lose the packet lazily instead of immediately. TransmissionInfo* transmission_info = - &unacked_packets_.at(old_sequence_number - least_unacked_); + FindOrNull(unacked_packets_, old_sequence_number); RetransmittableFrames* frames = transmission_info->retransmittable_frames; LOG_IF(DFATAL, frames == NULL) << "Attempt to retransmit packet with no " << "retransmittable frames: " @@ -82,86 +76,97 @@ void QuicUnackedPacketMap::OnRetransmittedPacket( transmission_info->retransmittable_frames = NULL; // Only keep one transmission older than largest observed, because only the // most recent is expected to possibly be a spurious retransmission. - if (transmission_info->all_transmissions != NULL && + if (transmission_info->all_transmissions->size() > 1 && *(++transmission_info->all_transmissions->begin()) < largest_observed_) { QuicPacketSequenceNumber old_transmission = *transmission_info->all_transmissions->begin(); - TransmissionInfo* old_info = - &unacked_packets_[old_transmission - least_unacked_]; + TransmissionInfo* old_transmission_info = + FindOrNull(unacked_packets_, old_transmission); // Don't remove old packets if they're still in flight. - if (!old_info->in_flight) { - old_info->all_transmissions->pop_front(); - // This will cause the packet be removed in RemoveObsoletePackets. - old_info->all_transmissions = NULL; + if (old_transmission_info == NULL || !old_transmission_info->in_flight) { + transmission_info->all_transmissions->erase(old_transmission); + unacked_packets_.erase(old_transmission); } } - if (transmission_info->all_transmissions == NULL) { - transmission_info->all_transmissions = new SequenceNumberList(); - transmission_info->all_transmissions->push_back(old_sequence_number); - } - transmission_info->all_transmissions->push_back(new_sequence_number); - unacked_packets_.push_back( + unacked_packets_[new_sequence_number] = TransmissionInfo(frames, + new_sequence_number, transmission_info->sequence_number_length, transmission_type, - transmission_info->all_transmissions)); + transmission_info->all_transmissions); } void QuicUnackedPacketMap::ClearPreviousRetransmissions(size_t num_to_clear) { - while (!unacked_packets_.empty() && num_to_clear > 0) { + UnackedPacketMap::iterator it = unacked_packets_.begin(); + while (it != unacked_packets_.end() && num_to_clear > 0) { + QuicPacketSequenceNumber sequence_number = it->first; // If this packet is in flight, or has retransmittable data, then there is // no point in clearing out any further packets, because they would not // affect the high water mark. - TransmissionInfo* info = &unacked_packets_.front(); - if (info->in_flight || info->retransmittable_frames != NULL) { + if (it->second.in_flight || it->second.retransmittable_frames != NULL) { break; } - info->all_transmissions->pop_front(); - LOG_IF(DFATAL, info->all_transmissions->empty()) + it->second.all_transmissions->erase(sequence_number); + LOG_IF(DFATAL, it->second.all_transmissions->empty()) << "Previous retransmissions must have a newer transmission."; - unacked_packets_.pop_front(); - ++least_unacked_; + ++it; + unacked_packets_.erase(sequence_number); --num_to_clear; } } bool QuicUnackedPacketMap::HasRetransmittableFrames( QuicPacketSequenceNumber sequence_number) const { - DCHECK_GE(sequence_number, least_unacked_); - DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size()); - return unacked_packets_[ - sequence_number - least_unacked_].retransmittable_frames != NULL; + const TransmissionInfo* transmission_info = + FindOrNull(unacked_packets_, sequence_number); + if (transmission_info == NULL) { + return false; + } + + return transmission_info->retransmittable_frames != NULL; } void QuicUnackedPacketMap::NackPacket(QuicPacketSequenceNumber sequence_number, size_t min_nacks) { - DCHECK_GE(sequence_number, least_unacked_); - DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size()); - unacked_packets_[sequence_number - least_unacked_].nack_count = - max(min_nacks, - unacked_packets_[sequence_number - least_unacked_].nack_count); + UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number); + if (it == unacked_packets_.end()) { + LOG(DFATAL) << "NackPacket called for packet that is not unacked: " + << sequence_number; + return; + } + + it->second.nack_count = max(min_nacks, it->second.nack_count); } void QuicUnackedPacketMap::RemoveRetransmittability( QuicPacketSequenceNumber sequence_number) { - DCHECK_GE(sequence_number, least_unacked_); - DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size()); - TransmissionInfo* info = &unacked_packets_[sequence_number - least_unacked_]; - SequenceNumberList* all_transmissions = info->all_transmissions; - if (all_transmissions == NULL) { - MaybeRemoveRetransmittableFrames(info); + UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number); + if (it == unacked_packets_.end()) { + DVLOG(1) << "packet is not in unacked_packets: " << sequence_number; return; } + SequenceNumberSet* all_transmissions = it->second.all_transmissions; + // TODO(ianswett): Consider optimizing this for lone packets. // TODO(ianswett): Consider adding a check to ensure there are retransmittable // frames associated with this packet. - for (SequenceNumberList::const_iterator it = all_transmissions->begin(); - it != all_transmissions->end(); ++it) { - TransmissionInfo* transmission_info = - &unacked_packets_[*it - least_unacked_]; + for (SequenceNumberSet::reverse_iterator it = all_transmissions->rbegin(); + it != all_transmissions->rend(); ++it) { + TransmissionInfo* transmission_info = FindOrNull(unacked_packets_, *it); + if (transmission_info == NULL) { + LOG(DFATAL) << "All transmissions in all_transmissions must be present " + << "in the unacked packet map."; + continue; + } MaybeRemoveRetransmittableFrames(transmission_info); - transmission_info->all_transmissions = NULL; + if (*it <= largest_observed_ && !transmission_info->in_flight) { + unacked_packets_.erase(*it); + } else { + transmission_info->all_transmissions = new SequenceNumberSet(); + transmission_info->all_transmissions->insert(*it); + } } + delete all_transmissions; } @@ -181,36 +186,48 @@ void QuicUnackedPacketMap::IncreaseLargestObserved( QuicPacketSequenceNumber largest_observed) { DCHECK_LE(largest_observed_, largest_observed); largest_observed_ = largest_observed; + UnackedPacketMap::iterator it = unacked_packets_.begin(); + while (it != unacked_packets_.end() && it->first <= largest_observed_) { + if (!IsPacketUseless(it)) { + ++it; + continue; + } + delete it->second.all_transmissions; + QuicPacketSequenceNumber sequence_number = it->first; + ++it; + unacked_packets_.erase(sequence_number); + } } bool QuicUnackedPacketMap::IsPacketUseless( - QuicPacketSequenceNumber sequence_number, - const TransmissionInfo& info) const { - return sequence_number <= largest_observed_ && - !info.in_flight && - info.retransmittable_frames == NULL && - info.all_transmissions == NULL; + UnackedPacketMap::const_iterator it) const { + return it->first <= largest_observed_ && + !it->second.in_flight && + it->second.retransmittable_frames == NULL && + it->second.all_transmissions->size() == 1; } bool QuicUnackedPacketMap::IsUnacked( QuicPacketSequenceNumber sequence_number) const { - if (sequence_number < least_unacked_ || - sequence_number >= least_unacked_ + unacked_packets_.size()) { - return false; - } - return !IsPacketUseless(sequence_number, - unacked_packets_[sequence_number - least_unacked_]); + return ContainsKey(unacked_packets_, sequence_number); } void QuicUnackedPacketMap::RemoveFromInFlight( QuicPacketSequenceNumber sequence_number) { - DCHECK_GE(sequence_number, least_unacked_); - DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size()); - TransmissionInfo* info = &unacked_packets_[sequence_number - least_unacked_]; - if (info->in_flight) { - LOG_IF(DFATAL, bytes_in_flight_ < info->bytes_sent); - bytes_in_flight_ -= info->bytes_sent; - info->in_flight = false; + UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number); + if (it == unacked_packets_.end()) { + LOG(DFATAL) << "RemoveFromFlight called for packet that is not unacked: " + << sequence_number; + return; + } + if (it->second.in_flight) { + LOG_IF(DFATAL, bytes_in_flight_ < it->second.bytes_sent); + bytes_in_flight_ -= it->second.bytes_sent; + it->second.in_flight = false; + } + if (IsPacketUseless(it)) { + delete it->second.all_transmissions; + unacked_packets_.erase(it); } } @@ -224,16 +241,16 @@ bool QuicUnackedPacketMap::HasInFlightPackets() const { const TransmissionInfo& QuicUnackedPacketMap::GetTransmissionInfo( QuicPacketSequenceNumber sequence_number) const { - return unacked_packets_[sequence_number - least_unacked_]; + return unacked_packets_.find(sequence_number)->second; } QuicTime QuicUnackedPacketMap::GetLastPacketSentTime() const { UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin(); while (it != unacked_packets_.rend()) { - if (it->in_flight) { - LOG_IF(DFATAL, it->sent_time == QuicTime::Zero()) + if (it->second.in_flight) { + LOG_IF(DFATAL, it->second.sent_time == QuicTime::Zero()) << "Sent time can never be zero for a packet in flight."; - return it->sent_time; + return it->second.sent_time; } ++it; } @@ -243,33 +260,25 @@ QuicTime QuicUnackedPacketMap::GetLastPacketSentTime() const { QuicTime QuicUnackedPacketMap::GetFirstInFlightPacketSentTime() const { UnackedPacketMap::const_iterator it = unacked_packets_.begin(); - while (it != unacked_packets_.end() && !it->in_flight) { + while (it != unacked_packets_.end() && !it->second.in_flight) { ++it; } if (it == unacked_packets_.end()) { LOG(DFATAL) << "GetFirstInFlightPacketSentTime requires in flight packets."; return QuicTime::Zero(); } - return it->sent_time; + return it->second.sent_time; } -size_t QuicUnackedPacketMap::GetNumUnackedPacketsDebugOnly() const { - size_t unacked_packet_count = 0; - QuicPacketSequenceNumber sequence_number = least_unacked_; - for (UnackedPacketMap::const_iterator it = unacked_packets_.begin(); - it != unacked_packets_.end(); ++it, ++sequence_number) { - if (!IsPacketUseless(sequence_number, *it)) { - ++unacked_packet_count; - } - } - return unacked_packet_count; +size_t QuicUnackedPacketMap::GetNumUnackedPackets() const { + return unacked_packets_.size(); } bool QuicUnackedPacketMap::HasMultipleInFlightPackets() const { size_t num_in_flight = 0; for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) { - if (it->in_flight) { + if (it->second.in_flight) { ++num_in_flight; } if (num_in_flight > 1) { @@ -286,7 +295,7 @@ bool QuicUnackedPacketMap::HasPendingCryptoPackets() const { bool QuicUnackedPacketMap::HasUnackedRetransmittableFrames() const { for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) { - if (it->in_flight && it->retransmittable_frames) { + if (it->second.in_flight && it->second.retransmittable_frames) { return true; } } @@ -294,44 +303,52 @@ bool QuicUnackedPacketMap::HasUnackedRetransmittableFrames() const { } QuicPacketSequenceNumber -QuicUnackedPacketMap::GetLeastUnacked() const { +QuicUnackedPacketMap::GetLeastUnackedSentPacket() const { if (unacked_packets_.empty()) { // If there are no unacked packets, return 0. return 0; } - return least_unacked_; + + return unacked_packets_.begin()->first; } void QuicUnackedPacketMap::SetSent(QuicPacketSequenceNumber sequence_number, QuicTime sent_time, QuicByteCount bytes_sent, bool set_in_flight) { - DCHECK_GE(sequence_number, least_unacked_); - DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size()); - TransmissionInfo* info = &unacked_packets_[sequence_number - least_unacked_]; - DCHECK(!info->in_flight); + DCHECK_LT(0u, sequence_number); + UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number); + if (it == unacked_packets_.end()) { + LOG(DFATAL) << "OnPacketSent called for packet that is not unacked: " + << sequence_number; + return; + } + DCHECK(!it->second.in_flight); - DCHECK_LT(largest_sent_packet_, sequence_number); largest_sent_packet_ = max(sequence_number, largest_sent_packet_); - info->sent_time = sent_time; + it->second.sent_time = sent_time; if (set_in_flight) { bytes_in_flight_ += bytes_sent; - info->bytes_sent = bytes_sent; - info->in_flight = true; + it->second.bytes_sent = bytes_sent; + it->second.in_flight = true; } } void QuicUnackedPacketMap::RestoreInFlight( QuicPacketSequenceNumber sequence_number) { - DCHECK_GE(sequence_number, least_unacked_); - DCHECK_LT(sequence_number, least_unacked_ + unacked_packets_.size()); - TransmissionInfo* info = &unacked_packets_[sequence_number - least_unacked_]; - DCHECK(!info->in_flight); - DCHECK_NE(0u, info->bytes_sent); - DCHECK(info->sent_time.IsInitialized()); - - bytes_in_flight_ += info->bytes_sent; - info->in_flight = true; + DCHECK_LT(0u, sequence_number); + UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number); + if (it == unacked_packets_.end()) { + LOG(DFATAL) << "OnPacketSent called for packet that is not unacked: " + << sequence_number; + return; + } + DCHECK(!it->second.in_flight); + DCHECK_NE(0u, it->second.bytes_sent); + DCHECK(it->second.sent_time.IsInitialized()); + + bytes_in_flight_ += it->second.bytes_sent; + it->second.in_flight = true; } } // namespace net diff --git a/net/quic/quic_unacked_packet_map.h b/net/quic/quic_unacked_packet_map.h index 293c7b6..3c367f6 100644 --- a/net/quic/quic_unacked_packet_map.h +++ b/net/quic/quic_unacked_packet_map.h @@ -5,8 +5,7 @@ #ifndef NET_QUIC_QUIC_UNACKED_PACKET_MAP_H_ #define NET_QUIC_QUIC_UNACKED_PACKET_MAP_H_ -#include <deque> - +#include "net/base/linked_hash_map.h" #include "net/quic/quic_protocol.h" namespace net { @@ -72,7 +71,7 @@ class NET_EXPORT_PRIVATE QuicUnackedPacketMap { // Returns the smallest sequence number of a serialized packet which has not // been acked by the peer. If there are no unacked packets, returns 0. - QuicPacketSequenceNumber GetLeastUnacked() const; + QuicPacketSequenceNumber GetLeastUnackedSentPacket() const; // Sets a packet as sent with the sent time |sent_time|. Marks the packet // as in flight if |set_in_flight| is true. @@ -90,7 +89,8 @@ class NET_EXPORT_PRIVATE QuicUnackedPacketMap { // in the ack frame for new acks. void ClearPreviousRetransmissions(size_t num_to_clear); - typedef std::deque<TransmissionInfo> UnackedPacketMap; + typedef linked_hash_map<QuicPacketSequenceNumber, + TransmissionInfo> UnackedPacketMap; typedef UnackedPacketMap::const_iterator const_iterator; @@ -112,7 +112,7 @@ class NET_EXPORT_PRIVATE QuicUnackedPacketMap { QuicTime GetFirstInFlightPacketSentTime() const; // Returns the number of unacked packets. - size_t GetNumUnackedPacketsDebugOnly() const; + size_t GetNumUnackedPackets() const; // Returns true if there are multiple packets in flight. bool HasMultipleInFlightPackets() const; @@ -129,16 +129,11 @@ class NET_EXPORT_PRIVATE QuicUnackedPacketMap { // |largest_acked_packet| are discarded if they are only for the RTT purposes. void IncreaseLargestObserved(QuicPacketSequenceNumber largest_observed); - // Remove any packets no longer needed for retransmission, congestion, or - // RTT measurement purposes. - void RemoveObsoletePackets(); - private: void MaybeRemoveRetransmittableFrames(TransmissionInfo* transmission_info); // Returns true if the packet no longer has a purpose in the map. - bool IsPacketUseless(QuicPacketSequenceNumber sequence_number, - const TransmissionInfo& info) const; + bool IsPacketUseless(UnackedPacketMap::const_iterator it) const; QuicPacketSequenceNumber largest_sent_packet_; QuicPacketSequenceNumber largest_observed_; @@ -152,8 +147,6 @@ class NET_EXPORT_PRIVATE QuicUnackedPacketMap { // be removed from the map and the new entry's retransmittable frames will be // set to NULL. UnackedPacketMap unacked_packets_; - // The packet at the 0th index of unacked_packets_. - QuicPacketSequenceNumber least_unacked_; size_t bytes_in_flight_; // Number of retransmittable crypto handshake packets. diff --git a/net/quic/quic_unacked_packet_map_test.cc b/net/quic/quic_unacked_packet_map_test.cc index 16d1df2..6e680de 100644 --- a/net/quic/quic_unacked_packet_map_test.cc +++ b/net/quic/quic_unacked_packet_map_test.cc @@ -35,7 +35,6 @@ class QuicUnackedPacketMapTest : public ::testing::Test { void VerifyInFlightPackets(QuicPacketSequenceNumber* packets, size_t num_packets) { - unacked_packets_.RemoveObsoletePackets(); if (num_packets == 0) { EXPECT_FALSE(unacked_packets_.HasInFlightPackets()); EXPECT_FALSE(unacked_packets_.HasMultipleInFlightPackets()); @@ -54,7 +53,7 @@ class QuicUnackedPacketMapTest : public ::testing::Test { size_t in_flight_count = 0; for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); it != unacked_packets_.end(); ++it) { - if (it->in_flight) { + if (it->second.in_flight) { ++in_flight_count; } } @@ -63,7 +62,6 @@ class QuicUnackedPacketMapTest : public ::testing::Test { void VerifyUnackedPackets(QuicPacketSequenceNumber* packets, size_t num_packets) { - unacked_packets_.RemoveObsoletePackets(); if (num_packets == 0) { EXPECT_FALSE(unacked_packets_.HasUnackedPackets()); EXPECT_FALSE(unacked_packets_.HasUnackedRetransmittableFrames()); @@ -73,16 +71,20 @@ class QuicUnackedPacketMapTest : public ::testing::Test { for (size_t i = 0; i < num_packets; ++i) { EXPECT_TRUE(unacked_packets_.IsUnacked(packets[i])) << packets[i]; } - EXPECT_EQ(num_packets, unacked_packets_.GetNumUnackedPacketsDebugOnly()); + size_t unacked_count = 0; + for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); + it != unacked_packets_.end(); ++it) { + ++unacked_count; + } + EXPECT_EQ(num_packets, unacked_count); } void VerifyRetransmittablePackets(QuicPacketSequenceNumber* 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) { - if (it->retransmittable_frames != NULL) { + if (it->second.retransmittable_frames != NULL) { ++num_retransmittable_packets; } } diff --git a/net/quic/test_tools/quic_sent_packet_manager_peer.cc b/net/quic/test_tools/quic_sent_packet_manager_peer.cc index 8092852..94e4607 100644 --- a/net/quic/test_tools/quic_sent_packet_manager_peer.cc +++ b/net/quic/test_tools/quic_sent_packet_manager_peer.cc @@ -89,7 +89,7 @@ bool QuicSentPacketManagerPeer::IsRetransmission( DCHECK(sent_packet_manager->HasRetransmittableFrames(sequence_number)); return sent_packet_manager->HasRetransmittableFrames(sequence_number) && sent_packet_manager->unacked_packets_.GetTransmissionInfo( - sequence_number).all_transmissions != NULL; + sequence_number).all_transmissions->size() > 1; } // static @@ -120,7 +120,7 @@ size_t QuicSentPacketManagerPeer::GetNumRetransmittablePackets( for (QuicUnackedPacketMap::const_iterator it = sent_packet_manager->unacked_packets_.begin(); it != sent_packet_manager->unacked_packets_.end(); ++it) { - if (it->retransmittable_frames != NULL) { + if (it->second.retransmittable_frames != NULL) { ++num_unacked_packets; } } diff --git a/net/tools/quic/quic_client_session_test.cc b/net/tools/quic/quic_client_session_test.cc index 96460d4..6f8136f 100644 --- a/net/tools/quic/quic_client_session_test.cc +++ b/net/tools/quic/quic_client_session_test.cc @@ -13,7 +13,6 @@ #include "net/quic/test_tools/quic_session_peer.h" #include "net/quic/test_tools/quic_test_utils.h" #include "net/tools/quic/quic_spdy_client_stream.h" -#include "net/tools/quic/test_tools/quic_test_utils.h" #include "testing/gtest/include/gtest/gtest.h" using net::test::CryptoTestUtils; @@ -21,11 +20,7 @@ using net::test::DefaultQuicConfig; using net::test::PacketSavingConnection; using net::test::QuicSessionPeer; using net::test::SupportedVersions; -using net::test::TestPeerIPAddress; using net::test::ValueRestore; -using net::test::kTestPort; -using net::tools::test::MockConnection; -using testing::Invoke; using testing::_; namespace net { @@ -114,39 +109,6 @@ TEST_P(ToolsQuicClientSessionTest, SetFecProtectionFromConfig) { EXPECT_EQ(FEC_PROTECT_OPTIONAL, stream->fec_policy()); } -TEST_P(ToolsQuicClientSessionTest, EmptyPacketReceived) { - // This test covers broken behavior that empty packets cause QUIC connection - // broken. - - // Create Packet with 0 length. - QuicEncryptedPacket invalid_packet(nullptr, 0, false); - IPEndPoint server_address(TestPeerIPAddress(), kTestPort); - IPEndPoint client_address(TestPeerIPAddress(), kTestPort); - - EXPECT_CALL(*reinterpret_cast<MockConnection*>(session_->connection()), - ProcessUdpPacket(server_address, client_address, _)) - .WillRepeatedly( - Invoke(reinterpret_cast<MockConnection*>(session_->connection()), - &MockConnection::ReallyProcessUdpPacket)); - - // Expect call to close connection with error QUIC_INVALID_PACKET_HEADER. - // TODO(b/17206611): Correct behavior: packet should get dropped and - // connection should remain open. - EXPECT_CALL(*connection_, SendConnectionCloseWithDetails( - QUIC_INVALID_PACKET_HEADER, _)).Times(1); - session_->connection()->ProcessUdpPacket(client_address, server_address, - invalid_packet); - - // Create a packet that causes DecryptPacket failed. The packet will get - // dropped without closing connection. This is a correct behavior. - char buf[2] = {0x00, 0x01}; - QuicEncryptedPacket valid_packet(buf, 2, false); - // Close connection shouldn't be called. - EXPECT_CALL(*connection_, SendConnectionCloseWithDetails(_, _)).Times(0); - session_->connection()->ProcessUdpPacket(client_address, server_address, - valid_packet); -} - } // namespace } // namespace test } // namespace tools |