1 // Copyright 2019 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "quiche/quic/core/congestion_control/uber_loss_algorithm.h"
6
7 #include <memory>
8 #include <optional>
9 #include <utility>
10
11 #include "quiche/quic/core/congestion_control/rtt_stats.h"
12 #include "quiche/quic/core/crypto/crypto_protocol.h"
13 #include "quiche/quic/core/quic_types.h"
14 #include "quiche/quic/core/quic_utils.h"
15 #include "quiche/quic/platform/api/quic_test.h"
16 #include "quiche/quic/test_tools/mock_clock.h"
17 #include "quiche/quic/test_tools/quic_unacked_packet_map_peer.h"
18
19 namespace quic {
20 namespace test {
21 namespace {
22
23 // Default packet length.
24 const uint32_t kDefaultLength = 1000;
25
26 class UberLossAlgorithmTest : public QuicTest {
27 protected:
UberLossAlgorithmTest()28 UberLossAlgorithmTest() {
29 unacked_packets_ =
30 std::make_unique<QuicUnackedPacketMap>(Perspective::IS_CLIENT);
31 rtt_stats_.UpdateRtt(QuicTime::Delta::FromMilliseconds(100),
32 QuicTime::Delta::Zero(), clock_.Now());
33 EXPECT_LT(0, rtt_stats_.smoothed_rtt().ToMicroseconds());
34 }
35
SendPacket(uint64_t packet_number,EncryptionLevel encryption_level)36 void SendPacket(uint64_t packet_number, EncryptionLevel encryption_level) {
37 QuicStreamFrame frame;
38 QuicTransportVersion version =
39 CurrentSupportedVersions()[0].transport_version;
40 frame.stream_id = QuicUtils::GetFirstBidirectionalStreamId(
41 version, Perspective::IS_CLIENT);
42 if (encryption_level == ENCRYPTION_INITIAL) {
43 if (QuicVersionUsesCryptoFrames(version)) {
44 frame.stream_id = QuicUtils::GetFirstBidirectionalStreamId(
45 version, Perspective::IS_CLIENT);
46 } else {
47 frame.stream_id = QuicUtils::GetCryptoStreamId(version);
48 }
49 }
50 SerializedPacket packet(QuicPacketNumber(packet_number),
51 PACKET_1BYTE_PACKET_NUMBER, nullptr, kDefaultLength,
52 false, false);
53 packet.encryption_level = encryption_level;
54 packet.retransmittable_frames.push_back(QuicFrame(frame));
55 unacked_packets_->AddSentPacket(&packet, NOT_RETRANSMISSION, clock_.Now(),
56 true, true, ECN_NOT_ECT);
57 }
58
AckPackets(const std::vector<uint64_t> & packets_acked)59 void AckPackets(const std::vector<uint64_t>& packets_acked) {
60 packets_acked_.clear();
61 for (uint64_t acked : packets_acked) {
62 unacked_packets_->RemoveFromInFlight(QuicPacketNumber(acked));
63 packets_acked_.push_back(AckedPacket(
64 QuicPacketNumber(acked), kMaxOutgoingPacketSize, QuicTime::Zero()));
65 }
66 }
67
VerifyLosses(uint64_t largest_newly_acked,const AckedPacketVector & packets_acked,const std::vector<uint64_t> & losses_expected)68 void VerifyLosses(uint64_t largest_newly_acked,
69 const AckedPacketVector& packets_acked,
70 const std::vector<uint64_t>& losses_expected) {
71 return VerifyLosses(largest_newly_acked, packets_acked, losses_expected,
72 std::nullopt);
73 }
74
VerifyLosses(uint64_t largest_newly_acked,const AckedPacketVector & packets_acked,const std::vector<uint64_t> & losses_expected,std::optional<QuicPacketCount> max_sequence_reordering_expected)75 void VerifyLosses(
76 uint64_t largest_newly_acked, const AckedPacketVector& packets_acked,
77 const std::vector<uint64_t>& losses_expected,
78 std::optional<QuicPacketCount> max_sequence_reordering_expected) {
79 LostPacketVector lost_packets;
80 LossDetectionInterface::DetectionStats stats = loss_algorithm_.DetectLosses(
81 *unacked_packets_, clock_.Now(), rtt_stats_,
82 QuicPacketNumber(largest_newly_acked), packets_acked, &lost_packets);
83 if (max_sequence_reordering_expected.has_value()) {
84 EXPECT_EQ(stats.sent_packets_max_sequence_reordering,
85 max_sequence_reordering_expected.value());
86 }
87 ASSERT_EQ(losses_expected.size(), lost_packets.size());
88 for (size_t i = 0; i < losses_expected.size(); ++i) {
89 EXPECT_EQ(lost_packets[i].packet_number,
90 QuicPacketNumber(losses_expected[i]));
91 }
92 }
93
94 MockClock clock_;
95 std::unique_ptr<QuicUnackedPacketMap> unacked_packets_;
96 RttStats rtt_stats_;
97 UberLossAlgorithm loss_algorithm_;
98 AckedPacketVector packets_acked_;
99 };
100
TEST_F(UberLossAlgorithmTest,ScenarioA)101 TEST_F(UberLossAlgorithmTest, ScenarioA) {
102 // This test mimics a scenario: client sends 1-CHLO, 2-0RTT, 3-0RTT,
103 // timeout and retransmits 4-CHLO. Server acks packet 1 (ack gets lost).
104 // Server receives and buffers packets 2 and 3. Server receives packet 4 and
105 // processes handshake asynchronously, so server acks 4 and cannot process
106 // packets 2 and 3.
107 SendPacket(1, ENCRYPTION_INITIAL);
108 SendPacket(2, ENCRYPTION_ZERO_RTT);
109 SendPacket(3, ENCRYPTION_ZERO_RTT);
110 unacked_packets_->RemoveFromInFlight(QuicPacketNumber(1));
111 SendPacket(4, ENCRYPTION_INITIAL);
112
113 AckPackets({1, 4});
114 unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace(
115 HANDSHAKE_DATA, QuicPacketNumber(4));
116 // Verify no packet is detected lost.
117 VerifyLosses(4, packets_acked_, std::vector<uint64_t>{}, 0);
118 EXPECT_EQ(QuicTime::Zero(), loss_algorithm_.GetLossTimeout());
119 }
120
TEST_F(UberLossAlgorithmTest,ScenarioB)121 TEST_F(UberLossAlgorithmTest, ScenarioB) {
122 // This test mimics a scenario: client sends 3-0RTT, 4-0RTT, receives SHLO,
123 // sends 5-1RTT, 6-1RTT.
124 SendPacket(3, ENCRYPTION_ZERO_RTT);
125 SendPacket(4, ENCRYPTION_ZERO_RTT);
126 SendPacket(5, ENCRYPTION_FORWARD_SECURE);
127 SendPacket(6, ENCRYPTION_FORWARD_SECURE);
128
129 AckPackets({4});
130 unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace(
131 APPLICATION_DATA, QuicPacketNumber(4));
132 // No packet loss by acking 4.
133 VerifyLosses(4, packets_acked_, std::vector<uint64_t>{}, 1);
134 EXPECT_EQ(clock_.Now() + 1.25 * rtt_stats_.smoothed_rtt(),
135 loss_algorithm_.GetLossTimeout());
136
137 // Acking 6 causes 3 to be detected loss.
138 AckPackets({6});
139 unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace(
140 APPLICATION_DATA, QuicPacketNumber(6));
141 VerifyLosses(6, packets_acked_, std::vector<uint64_t>{3}, 3);
142 EXPECT_EQ(clock_.Now() + 1.25 * rtt_stats_.smoothed_rtt(),
143 loss_algorithm_.GetLossTimeout());
144 packets_acked_.clear();
145
146 clock_.AdvanceTime(1.25 * rtt_stats_.latest_rtt());
147 // Verify 5 will be early retransmitted.
148 VerifyLosses(6, packets_acked_, {5}, 1);
149 }
150
TEST_F(UberLossAlgorithmTest,ScenarioC)151 TEST_F(UberLossAlgorithmTest, ScenarioC) {
152 // This test mimics a scenario: server sends 1-SHLO, 2-1RTT, 3-1RTT, 4-1RTT
153 // and retransmit 4-SHLO. Client receives and buffers packet 4. Client
154 // receives packet 5 and processes 4.
155 QuicUnackedPacketMapPeer::SetPerspective(unacked_packets_.get(),
156 Perspective::IS_SERVER);
157 SendPacket(1, ENCRYPTION_ZERO_RTT);
158 SendPacket(2, ENCRYPTION_FORWARD_SECURE);
159 SendPacket(3, ENCRYPTION_FORWARD_SECURE);
160 SendPacket(4, ENCRYPTION_FORWARD_SECURE);
161 unacked_packets_->RemoveFromInFlight(QuicPacketNumber(1));
162 SendPacket(5, ENCRYPTION_ZERO_RTT);
163
164 AckPackets({4, 5});
165 unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace(
166 APPLICATION_DATA, QuicPacketNumber(4));
167 unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace(
168 HANDSHAKE_DATA, QuicPacketNumber(5));
169 // No packet loss by acking 5.
170 VerifyLosses(5, packets_acked_, std::vector<uint64_t>{}, 2);
171 EXPECT_EQ(clock_.Now() + 1.25 * rtt_stats_.smoothed_rtt(),
172 loss_algorithm_.GetLossTimeout());
173 packets_acked_.clear();
174
175 clock_.AdvanceTime(1.25 * rtt_stats_.latest_rtt());
176 // Verify 2 and 3 will be early retransmitted.
177 VerifyLosses(5, packets_acked_, std::vector<uint64_t>{2, 3}, 2);
178 }
179
180 // Regression test for b/133771183.
TEST_F(UberLossAlgorithmTest,PacketInLimbo)181 TEST_F(UberLossAlgorithmTest, PacketInLimbo) {
182 // This test mimics a scenario: server sends 1-SHLO, 2-1RTT, 3-1RTT,
183 // 4-retransmit SHLO. Client receives and ACKs packets 1, 3 and 4.
184 QuicUnackedPacketMapPeer::SetPerspective(unacked_packets_.get(),
185 Perspective::IS_SERVER);
186
187 SendPacket(1, ENCRYPTION_ZERO_RTT);
188 SendPacket(2, ENCRYPTION_FORWARD_SECURE);
189 SendPacket(3, ENCRYPTION_FORWARD_SECURE);
190 SendPacket(4, ENCRYPTION_ZERO_RTT);
191
192 SendPacket(5, ENCRYPTION_FORWARD_SECURE);
193 AckPackets({1, 3, 4});
194 unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace(
195 APPLICATION_DATA, QuicPacketNumber(3));
196 unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace(
197 HANDSHAKE_DATA, QuicPacketNumber(4));
198 // No packet loss detected.
199 VerifyLosses(4, packets_acked_, std::vector<uint64_t>{});
200
201 SendPacket(6, ENCRYPTION_FORWARD_SECURE);
202 AckPackets({5, 6});
203 unacked_packets_->MaybeUpdateLargestAckedOfPacketNumberSpace(
204 APPLICATION_DATA, QuicPacketNumber(6));
205 // Verify packet 2 is detected lost.
206 VerifyLosses(6, packets_acked_, std::vector<uint64_t>{2});
207 }
208
209 class TestLossTuner : public LossDetectionTunerInterface {
210 public:
TestLossTuner(bool forced_start_result,LossDetectionParameters forced_parameters)211 TestLossTuner(bool forced_start_result,
212 LossDetectionParameters forced_parameters)
213 : forced_start_result_(forced_start_result),
214 forced_parameters_(std::move(forced_parameters)) {}
215
216 ~TestLossTuner() override = default;
217
Start(LossDetectionParameters * params)218 bool Start(LossDetectionParameters* params) override {
219 start_called_ = true;
220 *params = forced_parameters_;
221 return forced_start_result_;
222 }
223
Finish(const LossDetectionParameters &)224 void Finish(const LossDetectionParameters& /*params*/) override {}
225
start_called() const226 bool start_called() const { return start_called_; }
227
228 private:
229 bool forced_start_result_;
230 LossDetectionParameters forced_parameters_;
231 bool start_called_ = false;
232 };
233
234 // Verify the parameters are changed if first call SetFromConfig(), then call
235 // OnMinRttAvailable().
TEST_F(UberLossAlgorithmTest,LossDetectionTuning_SetFromConfigFirst)236 TEST_F(UberLossAlgorithmTest, LossDetectionTuning_SetFromConfigFirst) {
237 const int old_reordering_shift = loss_algorithm_.GetPacketReorderingShift();
238 const QuicPacketCount old_reordering_threshold =
239 loss_algorithm_.GetPacketReorderingThreshold();
240
241 loss_algorithm_.OnUserAgentIdKnown();
242
243 // Not owned.
244 TestLossTuner* test_tuner = new TestLossTuner(
245 /*forced_start_result=*/true,
246 LossDetectionParameters{
247 /*reordering_shift=*/old_reordering_shift + 1,
248 /*reordering_threshold=*/old_reordering_threshold * 2});
249 loss_algorithm_.SetLossDetectionTuner(
250 std::unique_ptr<LossDetectionTunerInterface>(test_tuner));
251
252 QuicConfig config;
253 QuicTagVector connection_options;
254 connection_options.push_back(kELDT);
255 config.SetInitialReceivedConnectionOptions(connection_options);
256 loss_algorithm_.SetFromConfig(config, Perspective::IS_SERVER);
257
258 // MinRtt was not available when SetFromConfig was called.
259 EXPECT_FALSE(test_tuner->start_called());
260 EXPECT_EQ(old_reordering_shift, loss_algorithm_.GetPacketReorderingShift());
261 EXPECT_EQ(old_reordering_threshold,
262 loss_algorithm_.GetPacketReorderingThreshold());
263
264 // MinRtt available. Tuner should not start yet because no reordering yet.
265 loss_algorithm_.OnMinRttAvailable();
266 EXPECT_FALSE(test_tuner->start_called());
267
268 // Reordering happened. Tuner should start now.
269 loss_algorithm_.OnReorderingDetected();
270 EXPECT_TRUE(test_tuner->start_called());
271 EXPECT_NE(old_reordering_shift, loss_algorithm_.GetPacketReorderingShift());
272 EXPECT_NE(old_reordering_threshold,
273 loss_algorithm_.GetPacketReorderingThreshold());
274 }
275
276 // Verify the parameters are changed if first call OnMinRttAvailable(), then
277 // call SetFromConfig().
TEST_F(UberLossAlgorithmTest,LossDetectionTuning_OnMinRttAvailableFirst)278 TEST_F(UberLossAlgorithmTest, LossDetectionTuning_OnMinRttAvailableFirst) {
279 const int old_reordering_shift = loss_algorithm_.GetPacketReorderingShift();
280 const QuicPacketCount old_reordering_threshold =
281 loss_algorithm_.GetPacketReorderingThreshold();
282
283 loss_algorithm_.OnUserAgentIdKnown();
284
285 // Not owned.
286 TestLossTuner* test_tuner = new TestLossTuner(
287 /*forced_start_result=*/true,
288 LossDetectionParameters{
289 /*reordering_shift=*/old_reordering_shift + 1,
290 /*reordering_threshold=*/old_reordering_threshold * 2});
291 loss_algorithm_.SetLossDetectionTuner(
292 std::unique_ptr<LossDetectionTunerInterface>(test_tuner));
293
294 loss_algorithm_.OnMinRttAvailable();
295 EXPECT_FALSE(test_tuner->start_called());
296 EXPECT_EQ(old_reordering_shift, loss_algorithm_.GetPacketReorderingShift());
297 EXPECT_EQ(old_reordering_threshold,
298 loss_algorithm_.GetPacketReorderingThreshold());
299
300 // Pretend a reodering has happened.
301 loss_algorithm_.OnReorderingDetected();
302 EXPECT_FALSE(test_tuner->start_called());
303
304 QuicConfig config;
305 QuicTagVector connection_options;
306 connection_options.push_back(kELDT);
307 config.SetInitialReceivedConnectionOptions(connection_options);
308 // Should start tuning since MinRtt is available.
309 loss_algorithm_.SetFromConfig(config, Perspective::IS_SERVER);
310
311 EXPECT_TRUE(test_tuner->start_called());
312 EXPECT_NE(old_reordering_shift, loss_algorithm_.GetPacketReorderingShift());
313 EXPECT_NE(old_reordering_threshold,
314 loss_algorithm_.GetPacketReorderingThreshold());
315 }
316
317 // Verify the parameters are not changed if Tuner.Start() returns false.
TEST_F(UberLossAlgorithmTest,LossDetectionTuning_StartFailed)318 TEST_F(UberLossAlgorithmTest, LossDetectionTuning_StartFailed) {
319 const int old_reordering_shift = loss_algorithm_.GetPacketReorderingShift();
320 const QuicPacketCount old_reordering_threshold =
321 loss_algorithm_.GetPacketReorderingThreshold();
322
323 loss_algorithm_.OnUserAgentIdKnown();
324
325 // Not owned.
326 TestLossTuner* test_tuner = new TestLossTuner(
327 /*forced_start_result=*/false,
328 LossDetectionParameters{
329 /*reordering_shift=*/old_reordering_shift + 1,
330 /*reordering_threshold=*/old_reordering_threshold * 2});
331 loss_algorithm_.SetLossDetectionTuner(
332 std::unique_ptr<LossDetectionTunerInterface>(test_tuner));
333
334 QuicConfig config;
335 QuicTagVector connection_options;
336 connection_options.push_back(kELDT);
337 config.SetInitialReceivedConnectionOptions(connection_options);
338 loss_algorithm_.SetFromConfig(config, Perspective::IS_SERVER);
339
340 // MinRtt was not available when SetFromConfig was called.
341 EXPECT_FALSE(test_tuner->start_called());
342 EXPECT_EQ(old_reordering_shift, loss_algorithm_.GetPacketReorderingShift());
343 EXPECT_EQ(old_reordering_threshold,
344 loss_algorithm_.GetPacketReorderingThreshold());
345
346 // Pretend a reodering has happened.
347 loss_algorithm_.OnReorderingDetected();
348 EXPECT_FALSE(test_tuner->start_called());
349
350 // Parameters should not change since test_tuner->Start() returns false.
351 loss_algorithm_.OnMinRttAvailable();
352 EXPECT_TRUE(test_tuner->start_called());
353 EXPECT_EQ(old_reordering_shift, loss_algorithm_.GetPacketReorderingShift());
354 EXPECT_EQ(old_reordering_threshold,
355 loss_algorithm_.GetPacketReorderingThreshold());
356 }
357
358 } // namespace
359 } // namespace test
360 } // namespace quic
361