| // Copyright 2019 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "quiche/quic/core/congestion_control/uber_loss_algorithm.h" |
| |
| #include <memory> |
| #include <utility> |
| |
| #include "absl/types/optional.h" |
| #include "quiche/quic/core/congestion_control/rtt_stats.h" |
| #include "quiche/quic/core/crypto/crypto_protocol.h" |
| #include "quiche/quic/core/quic_types.h" |
| #include "quiche/quic/core/quic_utils.h" |
| #include "quiche/quic/platform/api/quic_test.h" |
| #include "quiche/quic/test_tools/mock_clock.h" |
| #include "quiche/quic/test_tools/quic_unacked_packet_map_peer.h" |
| |
| namespace quic { |
| namespace test { |
| namespace { |
| |
| // Default packet length. |
| const uint32_t kDefaultLength = 1000; |
| |
| class UberLossAlgorithmTest : public QuicTest { |
| protected: |
| UberLossAlgorithmTest() { |
| unacked_packets_ = |
| std::make_unique<QuicUnackedPacketMap>(Perspective::IS_CLIENT); |
| rtt_stats_.UpdateRtt(QuicTime::Delta::FromMilliseconds(100), |
| QuicTime::Delta::Zero(), clock_.Now()); |
| EXPECT_LT(0, rtt_stats_.smoothed_rtt().ToMicroseconds()); |
| } |
| |
| void SendPacket(uint64_t packet_number, EncryptionLevel encryption_level) { |
| QuicStreamFrame frame; |
| QuicTransportVersion version = |
| CurrentSupportedVersions()[0].transport_version; |
| frame.stream_id = QuicUtils::GetFirstBidirectionalStreamId( |
| version, Perspective::IS_CLIENT); |
| if (encryption_level == ENCRYPTION_INITIAL) { |
| if (QuicVersionUsesCryptoFrames(version)) { |
| frame.stream_id = QuicUtils::GetFirstBidirectionalStreamId( |
| version, Perspective::IS_CLIENT); |
| } else { |
| frame.stream_id = QuicUtils::GetCryptoStreamId(version); |
| } |
| } |
| SerializedPacket packet(QuicPacketNumber(packet_number), |
| PACKET_1BYTE_PACKET_NUMBER, nullptr, kDefaultLength, |
| false, false); |
| packet.encryption_level = encryption_level; |
| packet.retransmittable_frames.push_back(QuicFrame(frame)); |
| unacked_packets_->AddSentPacket(&packet, NOT_RETRANSMISSION, clock_.Now(), |
| true, true); |
| } |
| |
| void AckPackets(const std::vector<uint64_t>& packets_acked) { |
| packets_acked_.clear(); |
| for (uint64_t acked : packets_acked) { |
| unacked_packets_->RemoveFromInFlight(QuicPacketNumber(acked)); |
| packets_acked_.push_back(AckedPacket( |
| QuicPacketNumber(acked), kMaxOutgoingPacketSize, QuicTime::Zero())); |
| } |
| } |
| |
| void VerifyLosses(uint64_t largest_newly_acked, |
| const AckedPacketVector& packets_acked, |
| const std::vector<uint64_t>& losses_expected) { |
| return VerifyLosses(largest_newly_acked, packets_acked, losses_expected, |
| absl::nullopt); |
| } |
| |
| void VerifyLosses( |
| uint64_t largest_newly_acked, const AckedPacketVector& packets_acked, |
| const std::vector<uint64_t>& losses_expected, |
| absl::optional<QuicPacketCount> max_sequence_reordering_expected) { |
| LostPacketVector lost_packets; |
| LossDetectionInterface::DetectionStats stats = loss_algorithm_.DetectLosses( |
| *unacked_packets_, clock_.Now(), rtt_stats_, |
| QuicPacketNumber(largest_newly_acked), packets_acked, &lost_packets); |
| if (max_sequence_reordering_expected.has_value()) { |
| EXPECT_EQ(stats.sent_packets_max_sequence_reordering, |
| max_sequence_reordering_expected.value()); |
| } |
| ASSERT_EQ(losses_expected.size(), lost_packets.size()); |
| for (size_t i = 0; i < losses_expected.size(); ++i) { |
| EXPECT_EQ(lost_packets[i].packet_number, |
| QuicPacketNumber(losses_expected[i])); |
| } |
| } |
| |
| MockClock clock_; |
| std::unique_ptr<QuicUnackedPacketMap> unacked_packets_; |
| RttStats rtt_stats_; |
| UberLossAlgorithm loss_algorithm_; |
| AckedPacketVector packets_acked_; |
| }; |
| |
| TEST_F(UberLossAlgorithmTest, ScenarioA) { |
| // This test mimics a scenario: client sends 1-CHLO, 2-0RTT, 3-0RTT, |
| // timeout and retransmits 4-CHLO. Server acks packet 1 (ack gets lost). |
| // Server receives and buffers packets 2 and 3. Server receives packet 4 and |
| // processes handshake asynchronously, so server acks 4 and cannot process |
| // packets 2 and 3. |
| SendPacket(1, ENCRYPTION_INITIAL); |
| SendPacket(2, ENCRYPTION_ZERO_RTT); |
| SendPacket(3, ENCRYPTION_ZERO_RTT); |
| unacked_packets_->RemoveFromInFlight(QuicPacketNumber(1)); |
| SendPacket(4, ENCRYPTION_INITIAL); |
| |
| AckPackets({1, 4}); |
| unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace( |
| HANDSHAKE_DATA, QuicPacketNumber(4)); |
| // Verify no packet is detected lost. |
| VerifyLosses(4, packets_acked_, std::vector<uint64_t>{}, 0); |
| EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout()); |
| } |
| |
| TEST_F(UberLossAlgorithmTest, ScenarioB) { |
| // This test mimics a scenario: client sends 3-0RTT, 4-0RTT, receives SHLO, |
| // sends 5-1RTT, 6-1RTT. |
| SendPacket(3, ENCRYPTION_ZERO_RTT); |
| SendPacket(4, ENCRYPTION_ZERO_RTT); |
| SendPacket(5, ENCRYPTION_FORWARD_SECURE); |
| SendPacket(6, ENCRYPTION_FORWARD_SECURE); |
| |
| AckPackets({4}); |
| unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace( |
| APPLICATION_DATA, QuicPacketNumber(4)); |
| // No packet loss by acking 4. |
| VerifyLosses(4, packets_acked_, std::vector<uint64_t>{}, 1); |
| EXPECT_EQ(clock_.Now() + 1.25 * rtt_stats_.smoothed_rtt(), |
| loss_algorithm_.GetLossTimeout()); |
| |
| // Acking 6 causes 3 to be detected loss. |
| AckPackets({6}); |
| unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace( |
| APPLICATION_DATA, QuicPacketNumber(6)); |
| VerifyLosses(6, packets_acked_, std::vector<uint64_t>{3}, 3); |
| EXPECT_EQ(clock_.Now() + 1.25 * rtt_stats_.smoothed_rtt(), |
| loss_algorithm_.GetLossTimeout()); |
| packets_acked_.clear(); |
| |
| clock_.AdvanceTime(1.25 * rtt_stats_.latest_rtt()); |
| // Verify 5 will be early retransmitted. |
| VerifyLosses(6, packets_acked_, {5}, 1); |
| } |
| |
| TEST_F(UberLossAlgorithmTest, ScenarioC) { |
| // This test mimics a scenario: server sends 1-SHLO, 2-1RTT, 3-1RTT, 4-1RTT |
| // and retransmit 4-SHLO. Client receives and buffers packet 4. Client |
| // receives packet 5 and processes 4. |
| QuicUnackedPacketMapPeer::SetPerspective(unacked_packets_.get(), |
| Perspective::IS_SERVER); |
| SendPacket(1, ENCRYPTION_ZERO_RTT); |
| SendPacket(2, ENCRYPTION_FORWARD_SECURE); |
| SendPacket(3, ENCRYPTION_FORWARD_SECURE); |
| SendPacket(4, ENCRYPTION_FORWARD_SECURE); |
| unacked_packets_->RemoveFromInFlight(QuicPacketNumber(1)); |
| SendPacket(5, ENCRYPTION_ZERO_RTT); |
| |
| AckPackets({4, 5}); |
| unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace( |
| APPLICATION_DATA, QuicPacketNumber(4)); |
| unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace( |
| HANDSHAKE_DATA, QuicPacketNumber(5)); |
| // No packet loss by acking 5. |
| VerifyLosses(5, packets_acked_, std::vector<uint64_t>{}, 2); |
| EXPECT_EQ(clock_.Now() + 1.25 * rtt_stats_.smoothed_rtt(), |
| loss_algorithm_.GetLossTimeout()); |
| packets_acked_.clear(); |
| |
| clock_.AdvanceTime(1.25 * rtt_stats_.latest_rtt()); |
| // Verify 2 and 3 will be early retransmitted. |
| VerifyLosses(5, packets_acked_, std::vector<uint64_t>{2, 3}, 2); |
| } |
| |
| // Regression test for b/133771183. |
| TEST_F(UberLossAlgorithmTest, PacketInLimbo) { |
| // This test mimics a scenario: server sends 1-SHLO, 2-1RTT, 3-1RTT, |
| // 4-retransmit SHLO. Client receives and ACKs packets 1, 3 and 4. |
| QuicUnackedPacketMapPeer::SetPerspective(unacked_packets_.get(), |
| Perspective::IS_SERVER); |
| |
| SendPacket(1, ENCRYPTION_ZERO_RTT); |
| SendPacket(2, ENCRYPTION_FORWARD_SECURE); |
| SendPacket(3, ENCRYPTION_FORWARD_SECURE); |
| SendPacket(4, ENCRYPTION_ZERO_RTT); |
| |
| SendPacket(5, ENCRYPTION_FORWARD_SECURE); |
| AckPackets({1, 3, 4}); |
| unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace( |
| APPLICATION_DATA, QuicPacketNumber(3)); |
| unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace( |
| HANDSHAKE_DATA, QuicPacketNumber(4)); |
| // No packet loss detected. |
| VerifyLosses(4, packets_acked_, std::vector<uint64_t>{}); |
| |
| SendPacket(6, ENCRYPTION_FORWARD_SECURE); |
| AckPackets({5, 6}); |
| unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace( |
| APPLICATION_DATA, QuicPacketNumber(6)); |
| // Verify packet 2 is detected lost. |
| VerifyLosses(6, packets_acked_, std::vector<uint64_t>{2}); |
| } |
| |
| class TestLossTuner : public LossDetectionTunerInterface { |
| public: |
| TestLossTuner(bool forced_start_result, |
| LossDetectionParameters forced_parameters) |
| : forced_start_result_(forced_start_result), |
| forced_parameters_(std::move(forced_parameters)) {} |
| |
| ~TestLossTuner() override = default; |
| |
| bool Start(LossDetectionParameters* params) override { |
| start_called_ = true; |
| *params = forced_parameters_; |
| return forced_start_result_; |
| } |
| |
| void Finish(const LossDetectionParameters& /*params*/) override {} |
| |
| bool start_called() const { return start_called_; } |
| |
| private: |
| bool forced_start_result_; |
| LossDetectionParameters forced_parameters_; |
| bool start_called_ = false; |
| }; |
| |
| // Verify the parameters are changed if first call SetFromConfig(), then call |
| // OnMinRttAvailable(). |
| TEST_F(UberLossAlgorithmTest, LossDetectionTuning_SetFromConfigFirst) { |
| const int old_reordering_shift = loss_algorithm_.GetPacketReorderingShift(); |
| const QuicPacketCount old_reordering_threshold = |
| loss_algorithm_.GetPacketReorderingThreshold(); |
| |
| loss_algorithm_.OnUserAgentIdKnown(); |
| |
| // Not owned. |
| TestLossTuner* test_tuner = new TestLossTuner( |
| /*forced_start_result=*/true, |
| LossDetectionParameters{ |
| /*reordering_shift=*/old_reordering_shift + 1, |
| /*reordering_threshold=*/old_reordering_threshold * 2}); |
| loss_algorithm_.SetLossDetectionTuner( |
| std::unique_ptr<LossDetectionTunerInterface>(test_tuner)); |
| |
| QuicConfig config; |
| QuicTagVector connection_options; |
| connection_options.push_back(kELDT); |
| config.SetInitialReceivedConnectionOptions(connection_options); |
| loss_algorithm_.SetFromConfig(config, Perspective::IS_SERVER); |
| |
| // MinRtt was not available when SetFromConfig was called. |
| EXPECT_FALSE(test_tuner->start_called()); |
| EXPECT_EQ(old_reordering_shift, loss_algorithm_.GetPacketReorderingShift()); |
| EXPECT_EQ(old_reordering_threshold, |
| loss_algorithm_.GetPacketReorderingThreshold()); |
| |
| // MinRtt available. Tuner should not start yet because no reordering yet. |
| loss_algorithm_.OnMinRttAvailable(); |
| EXPECT_FALSE(test_tuner->start_called()); |
| |
| // Reordering happened. Tuner should start now. |
| loss_algorithm_.OnReorderingDetected(); |
| EXPECT_TRUE(test_tuner->start_called()); |
| EXPECT_NE(old_reordering_shift, loss_algorithm_.GetPacketReorderingShift()); |
| EXPECT_NE(old_reordering_threshold, |
| loss_algorithm_.GetPacketReorderingThreshold()); |
| } |
| |
| // Verify the parameters are changed if first call OnMinRttAvailable(), then |
| // call SetFromConfig(). |
| TEST_F(UberLossAlgorithmTest, LossDetectionTuning_OnMinRttAvailableFirst) { |
| const int old_reordering_shift = loss_algorithm_.GetPacketReorderingShift(); |
| const QuicPacketCount old_reordering_threshold = |
| loss_algorithm_.GetPacketReorderingThreshold(); |
| |
| loss_algorithm_.OnUserAgentIdKnown(); |
| |
| // Not owned. |
| TestLossTuner* test_tuner = new TestLossTuner( |
| /*forced_start_result=*/true, |
| LossDetectionParameters{ |
| /*reordering_shift=*/old_reordering_shift + 1, |
| /*reordering_threshold=*/old_reordering_threshold * 2}); |
| loss_algorithm_.SetLossDetectionTuner( |
| std::unique_ptr<LossDetectionTunerInterface>(test_tuner)); |
| |
| loss_algorithm_.OnMinRttAvailable(); |
| EXPECT_FALSE(test_tuner->start_called()); |
| EXPECT_EQ(old_reordering_shift, loss_algorithm_.GetPacketReorderingShift()); |
| EXPECT_EQ(old_reordering_threshold, |
| loss_algorithm_.GetPacketReorderingThreshold()); |
| |
| // Pretend a reodering has happened. |
| loss_algorithm_.OnReorderingDetected(); |
| EXPECT_FALSE(test_tuner->start_called()); |
| |
| QuicConfig config; |
| QuicTagVector connection_options; |
| connection_options.push_back(kELDT); |
| config.SetInitialReceivedConnectionOptions(connection_options); |
| // Should start tuning since MinRtt is available. |
| loss_algorithm_.SetFromConfig(config, Perspective::IS_SERVER); |
| |
| EXPECT_TRUE(test_tuner->start_called()); |
| EXPECT_NE(old_reordering_shift, loss_algorithm_.GetPacketReorderingShift()); |
| EXPECT_NE(old_reordering_threshold, |
| loss_algorithm_.GetPacketReorderingThreshold()); |
| } |
| |
| // Verify the parameters are not changed if Tuner.Start() returns false. |
| TEST_F(UberLossAlgorithmTest, LossDetectionTuning_StartFailed) { |
| const int old_reordering_shift = loss_algorithm_.GetPacketReorderingShift(); |
| const QuicPacketCount old_reordering_threshold = |
| loss_algorithm_.GetPacketReorderingThreshold(); |
| |
| loss_algorithm_.OnUserAgentIdKnown(); |
| |
| // Not owned. |
| TestLossTuner* test_tuner = new TestLossTuner( |
| /*forced_start_result=*/false, |
| LossDetectionParameters{ |
| /*reordering_shift=*/old_reordering_shift + 1, |
| /*reordering_threshold=*/old_reordering_threshold * 2}); |
| loss_algorithm_.SetLossDetectionTuner( |
| std::unique_ptr<LossDetectionTunerInterface>(test_tuner)); |
| |
| QuicConfig config; |
| QuicTagVector connection_options; |
| connection_options.push_back(kELDT); |
| config.SetInitialReceivedConnectionOptions(connection_options); |
| loss_algorithm_.SetFromConfig(config, Perspective::IS_SERVER); |
| |
| // MinRtt was not available when SetFromConfig was called. |
| EXPECT_FALSE(test_tuner->start_called()); |
| EXPECT_EQ(old_reordering_shift, loss_algorithm_.GetPacketReorderingShift()); |
| EXPECT_EQ(old_reordering_threshold, |
| loss_algorithm_.GetPacketReorderingThreshold()); |
| |
| // Pretend a reodering has happened. |
| loss_algorithm_.OnReorderingDetected(); |
| EXPECT_FALSE(test_tuner->start_called()); |
| |
| // Parameters should not change since test_tuner->Start() returns false. |
| loss_algorithm_.OnMinRttAvailable(); |
| EXPECT_TRUE(test_tuner->start_called()); |
| EXPECT_EQ(old_reordering_shift, loss_algorithm_.GetPacketReorderingShift()); |
| EXPECT_EQ(old_reordering_threshold, |
| loss_algorithm_.GetPacketReorderingThreshold()); |
| } |
| |
| } // namespace |
| } // namespace test |
| } // namespace quic |