1 /*
2 * Copyright (c) Facebook, Inc. and its affiliates.
3 *
4 * This source code is licensed under the MIT license found in the
5 * LICENSE file in the root directory of this source tree.
6 *
7 */
8
9 #include <folly/portability/GMock.h>
10 #include <folly/portability/GTest.h>
11
12 #include <folly/io/async/test/MockAsyncUDPSocket.h>
13 #include <folly/io/async/test/MockTimeoutManager.h>
14 #include <quic/api/QuicTransportFunctions.h>
15 #include <quic/api/test/Mocks.h>
16 #include <quic/client/state/ClientStateMachine.h>
17 #include <quic/codec/DefaultConnectionIdAlgo.h>
18 #include <quic/common/test/TestUtils.h>
19 #include <quic/d6d/test/Mocks.h>
20 #include <quic/dsr/Types.h>
21 #include <quic/dsr/test/Mocks.h>
22 #include <quic/fizz/client/handshake/FizzClientQuicHandshakeContext.h>
23 #include <quic/fizz/server/handshake/FizzServerQuicHandshakeContext.h>
24 #include <quic/logging/test/Mocks.h>
25 #include <quic/loss/QuicLossFunctions.h>
26 #include <quic/server/state/ServerStateMachine.h>
27 #include <quic/state/stream/StreamSendHandlers.h>
28 #include <quic/state/test/MockQuicStats.h>
29 #include <quic/state/test/Mocks.h>
30
31 using namespace folly::test;
32 using namespace testing;
33 using namespace folly;
34
35 namespace {
getOutstandingPacketMatcher(quic::PacketNum packetNum,bool lostByReorder,bool lostByTimeout)36 auto getOutstandingPacketMatcher(
37 quic::PacketNum packetNum,
38 bool lostByReorder,
39 bool lostByTimeout) {
40 return AllOf(
41 testing::Field(
42 &quic::OutstandingPacket::lostByReorder, testing::Eq(lostByReorder)),
43 testing::Field(
44 &quic::OutstandingPacket::lostByTimeout, testing::Eq(lostByTimeout)),
45 testing::Field(
46 &quic::OutstandingPacket::packet,
47 testing::Field(
48 &quic::RegularPacket::header,
49 testing::Property(
50 &quic::PacketHeader::getPacketSequenceNum, packetNum))));
51 }
52 } // namespace
53
54 namespace quic {
55 namespace test {
56
57 class MockLossTimeout {
58 public:
59 MOCK_METHOD0(cancelLossTimeout, void());
60 MOCK_METHOD1(scheduleLossTimeout, void(std::chrono::milliseconds));
61 MOCK_METHOD0(isLossTimeoutScheduled, bool());
62 };
63
64 enum class PacketType {
65 Initial,
66 Handshake,
67 ZeroRtt,
68 OneRtt,
69 };
70
71 struct PMTUBlackholeDetectionTestFixture; // Forward declaration
72
73 class QuicLossFunctionsTest : public TestWithParam<PacketNumberSpace> {
74 public:
SetUp()75 void SetUp() override {
76 aead = createNoOpAead();
77 headerCipher = createNoOpHeaderCipher();
78 transportInfoCb_ = std::make_unique<MockQuicStats>();
79 connIdAlgo_ = std::make_unique<DefaultConnectionIdAlgo>();
80 }
81
82 PacketNum sendPacket(
83 QuicConnectionStateBase& conn,
84 TimePoint time,
85 folly::Optional<PacketEvent> associatedEvent,
86 PacketType packetType,
87 bool isD6DProbe = false,
88 folly::Optional<uint16_t> forcedSize = folly::none);
89
createConn()90 std::unique_ptr<QuicServerConnectionState> createConn() {
91 auto conn = std::make_unique<QuicServerConnectionState>(
92 FizzServerQuicHandshakeContext::Builder().build());
93 conn->clientConnectionId = getTestConnectionId();
94 conn->version = QuicVersion::MVFST;
95 conn->ackStates.initialAckState.nextPacketNum = 1;
96 conn->ackStates.handshakeAckState.nextPacketNum = 1;
97 conn->ackStates.appDataAckState.nextPacketNum = 1;
98 conn->flowControlState.peerAdvertisedInitialMaxStreamOffsetBidiLocal =
99 kDefaultStreamWindowSize;
100 conn->flowControlState.peerAdvertisedInitialMaxStreamOffsetBidiRemote =
101 kDefaultStreamWindowSize;
102 conn->flowControlState.peerAdvertisedInitialMaxStreamOffsetUni =
103 kDefaultStreamWindowSize;
104 conn->flowControlState.peerAdvertisedMaxOffset =
105 kDefaultConnectionWindowSize;
106 conn->streamManager->setMaxLocalBidirectionalStreams(
107 kDefaultMaxStreamsBidirectional);
108 conn->streamManager->setMaxLocalUnidirectionalStreams(
109 kDefaultMaxStreamsUnidirectional);
110 conn->statsCallback = transportInfoCb_.get();
111 // create a serverConnectionId that is different from the client connId
112 // with bits for processId and workerId set to 0
113 ServerConnectionIdParams params(0, 0, 0);
114 conn->connIdAlgo = connIdAlgo_.get();
115 conn->serverConnectionId = *connIdAlgo_->encodeConnectionId(params);
116 // for canSetLossTimerForAppData()
117 conn->oneRttWriteCipher = createNoOpAead();
118 conn->observers = std::make_shared<ObserverVec>();
119 return conn;
120 }
121
createClientConn()122 std::unique_ptr<QuicClientConnectionState> createClientConn() {
123 auto conn = std::make_unique<QuicClientConnectionState>(
124 FizzClientQuicHandshakeContext::Builder().build());
125 conn->clientConnectionId = getTestConnectionId();
126 conn->version = QuicVersion::MVFST;
127 conn->ackStates.initialAckState.nextPacketNum = 1;
128 conn->ackStates.handshakeAckState.nextPacketNum = 1;
129 conn->ackStates.appDataAckState.nextPacketNum = 1;
130 conn->flowControlState.peerAdvertisedInitialMaxStreamOffsetBidiLocal =
131 kDefaultStreamWindowSize;
132 conn->flowControlState.peerAdvertisedInitialMaxStreamOffsetBidiRemote =
133 kDefaultStreamWindowSize;
134 conn->flowControlState.peerAdvertisedInitialMaxStreamOffsetUni =
135 kDefaultStreamWindowSize;
136 conn->flowControlState.peerAdvertisedMaxOffset =
137 kDefaultConnectionWindowSize;
138 conn->statsCallback = transportInfoCb_.get();
139 // create a serverConnectionId that is different from the client connId
140 // with bits for processId and workerId set to 0
141 ServerConnectionIdParams params(0, 0, 0);
142 conn->serverConnectionId = *connIdAlgo_.get()->encodeConnectionId(params);
143 return conn;
144 }
145
146 void runDetectPMTUBlackholeTest(
147 QuicConnectionStateBase* conn,
148 PMTUBlackholeDetectionTestFixture fixture);
149
150 EventBase evb;
151 std::unique_ptr<Aead> aead;
152 std::unique_ptr<PacketNumberCipher> headerCipher;
153 MockLossTimeout timeout;
154 std::unique_ptr<MockQuicStats> transportInfoCb_;
155 std::unique_ptr<ConnectionIdAlgo> connIdAlgo_;
156
getLossPacketMatcher(PacketNum packetNum,bool lossByReorder,bool lossByTimeout)157 auto getLossPacketMatcher(
158 PacketNum packetNum,
159 bool lossByReorder,
160 bool lossByTimeout) {
161 return MockObserver::getLossPacketMatcher(
162 packetNum, lossByReorder, lossByTimeout);
163 }
164 };
165
testingLossMarkFunc(std::vector<PacketNum> & lostPackets)166 auto testingLossMarkFunc(std::vector<PacketNum>& lostPackets) {
167 return [&lostPackets](auto& /* conn */, auto& packet, bool processed) {
168 if (!processed) {
169 auto packetNum = packet.header.getPacketSequenceNum();
170 lostPackets.push_back(packetNum);
171 }
172 };
173 }
174
sendPacket(QuicConnectionStateBase & conn,TimePoint time,folly::Optional<PacketEvent> associatedEvent,PacketType packetType,bool isD6DProbe,folly::Optional<uint16_t> forcedSize)175 PacketNum QuicLossFunctionsTest::sendPacket(
176 QuicConnectionStateBase& conn,
177 TimePoint time,
178 folly::Optional<PacketEvent> associatedEvent,
179 PacketType packetType,
180 bool isD6DProbe,
181 folly::Optional<uint16_t> forcedSize) {
182 folly::Optional<PacketHeader> header;
183 bool isHandshake = false;
184 switch (packetType) {
185 case PacketType::Initial:
186 header = LongHeader(
187 LongHeader::Types::Initial,
188 *conn.clientConnectionId,
189 *conn.serverConnectionId,
190 conn.ackStates.initialAckState.nextPacketNum,
191 *conn.version);
192 isHandshake = true;
193 break;
194 case PacketType::Handshake:
195 header = LongHeader(
196 LongHeader::Types::Handshake,
197 *conn.clientConnectionId,
198 *conn.serverConnectionId,
199 conn.ackStates.handshakeAckState.nextPacketNum,
200 *conn.version);
201 isHandshake = true;
202 break;
203 case PacketType::ZeroRtt:
204 header = LongHeader(
205 LongHeader::Types::ZeroRtt,
206 *conn.clientConnectionId,
207 *conn.serverConnectionId,
208 conn.ackStates.appDataAckState.nextPacketNum,
209 *conn.version);
210 break;
211 case PacketType::OneRtt:
212 header = ShortHeader(
213 ProtectionType::KeyPhaseZero,
214 *conn.serverConnectionId,
215 conn.ackStates.appDataAckState.nextPacketNum);
216 break;
217 }
218 PacketNumberSpace packetNumberSpace;
219 auto shortHeader = header->asShort();
220 if (shortHeader) {
221 packetNumberSpace = shortHeader->getPacketNumberSpace();
222 } else {
223 packetNumberSpace = header->asLong()->getPacketNumberSpace();
224 }
225 RegularQuicPacketBuilder builder(
226 conn.udpSendPacketLen,
227 std::move(*header),
228 getAckState(conn, packetNumberSpace).largestAckedByPeer.value_or(0));
229 builder.encodePacketHeader();
230 EXPECT_TRUE(builder.canBuildPacket());
231 auto packet = std::move(builder).buildPacket();
232 if (forcedSize) {
233 RegularSizeEnforcedPacketBuilder sizeEnforcedBuilder(
234 std::move(packet), *forcedSize, aead->getCipherOverhead());
235 EXPECT_TRUE(sizeEnforcedBuilder.canBuildPacket());
236 packet = std::move(sizeEnforcedBuilder).buildPacket();
237 }
238 uint32_t encodedSize = 0;
239 uint32_t encodedBodySize = 0;
240 if (packet.header) {
241 encodedSize += packet.header->computeChainDataLength();
242 }
243 if (packet.body) {
244 encodedSize += packet.body->computeChainDataLength();
245 encodedBodySize += packet.body->computeChainDataLength();
246 }
247 auto outstandingPacket = OutstandingPacket(
248 packet.packet,
249 time,
250 encodedSize,
251 encodedBodySize,
252 isHandshake,
253 isD6DProbe,
254 encodedSize,
255 encodedBodySize,
256 0,
257 0,
258 LossState(),
259 0);
260 outstandingPacket.associatedEvent = associatedEvent;
261 conn.lossState.lastRetransmittablePacketSentTime = time;
262 if (conn.congestionController) {
263 conn.congestionController->onPacketSent(outstandingPacket);
264 }
265 if (associatedEvent) {
266 conn.outstandings.clonedPacketCount[packetNumberSpace]++;
267 // Simulates what the real writer does.
268 auto it = std::find_if(
269 conn.outstandings.packets.begin(),
270 conn.outstandings.packets.end(),
271 [&associatedEvent](const auto& packet) {
272 auto packetNum = packet.packet.header.getPacketSequenceNum();
273 auto packetNumSpace = packet.packet.header.getPacketNumberSpace();
274 return packetNum == associatedEvent->packetNumber &&
275 packetNumSpace == associatedEvent->packetNumberSpace;
276 });
277 if (it != conn.outstandings.packets.end()) {
278 if (!it->associatedEvent) {
279 conn.outstandings.packetEvents.emplace(*associatedEvent);
280 conn.outstandings.clonedPacketCount[packetNumberSpace]++;
281 it->associatedEvent = *associatedEvent;
282 }
283 }
284 } else {
285 conn.outstandings.packetCount[packetNumberSpace]++;
286 }
287 conn.outstandings.packets.emplace_back(std::move(outstandingPacket));
288 conn.lossState.largestSent = getNextPacketNum(conn, packetNumberSpace);
289 increaseNextPacketNum(conn, packetNumberSpace);
290 conn.pendingEvents.setLossDetectionAlarm = true;
291 if (isD6DProbe) {
292 ++conn.d6d.outstandingProbes;
293 conn.d6d.lastProbe =
294 D6DProbePacket(encodedSize, conn.lossState.largestSent.value());
295 }
296 return conn.lossState.largestSent.value();
297 }
298
TEST_F(QuicLossFunctionsTest,AllPacketsProcessed)299 TEST_F(QuicLossFunctionsTest, AllPacketsProcessed) {
300 auto conn = createConn();
301 EXPECT_CALL(*transportInfoCb_, onPTO()).Times(0);
302 PacketEvent packetEvent1(
303 PacketNumberSpace::AppData,
304 conn->ackStates.appDataAckState.nextPacketNum);
305 sendPacket(*conn, Clock::now(), packetEvent1, PacketType::OneRtt);
306 PacketEvent packetEvent2(
307 PacketNumberSpace::AppData,
308 conn->ackStates.appDataAckState.nextPacketNum);
309 sendPacket(*conn, Clock::now(), packetEvent2, PacketType::OneRtt);
310 PacketEvent packetEvent3(
311 PacketNumberSpace::AppData,
312 conn->ackStates.appDataAckState.nextPacketNum);
313 sendPacket(*conn, Clock::now(), packetEvent3, PacketType::OneRtt);
314 EXPECT_CALL(timeout, cancelLossTimeout()).Times(1);
315 setLossDetectionAlarm(*conn, timeout);
316 EXPECT_FALSE(conn->pendingEvents.setLossDetectionAlarm);
317 }
318
TEST_F(QuicLossFunctionsTest,HasDataToWrite)319 TEST_F(QuicLossFunctionsTest, HasDataToWrite) {
320 auto conn = createConn();
321 // There needs to be at least one outstanding packet.
322 sendPacket(*conn, Clock::now(), folly::none, PacketType::OneRtt);
323 conn->streamManager->addLoss(1);
324 conn->pendingEvents.setLossDetectionAlarm = true;
325 EXPECT_CALL(timeout, cancelLossTimeout()).Times(2);
326 EXPECT_CALL(timeout, scheduleLossTimeout(_)).Times(1);
327 setLossDetectionAlarm(*conn, timeout);
328 EXPECT_FALSE(conn->pendingEvents.setLossDetectionAlarm);
329 }
330
TEST_F(QuicLossFunctionsTest,D6DProbeDoesNotSetLossDetectionAlarms)331 TEST_F(QuicLossFunctionsTest, D6DProbeDoesNotSetLossDetectionAlarms) {
332 auto conn = createConn();
333 sendPacket(*conn, Clock::now(), folly::none, PacketType::OneRtt, true);
334 conn->pendingEvents.setLossDetectionAlarm = true;
335 EXPECT_CALL(timeout, cancelLossTimeout()).Times(1);
336 EXPECT_CALL(timeout, scheduleLossTimeout(_)).Times(0);
337 setLossDetectionAlarm(*conn, timeout);
338 EXPECT_FALSE(conn->pendingEvents.setLossDetectionAlarm);
339 }
340
TEST_F(QuicLossFunctionsTest,D6DProbeExcludedInLossEvent)341 TEST_F(QuicLossFunctionsTest, D6DProbeExcludedInLossEvent) {
342 auto conn = createConn();
343 // 0 rtt means all packets are automatically lost upon sending
344 conn->lossState.srtt = 0s;
345 conn->lossState.lrtt = 0s;
346 auto currentTime = Clock::now();
347 auto firstPacketNum =
348 sendPacket(*conn, currentTime, folly::none, PacketType::OneRtt, true);
349 auto secondPacketNum =
350 sendPacket(*conn, currentTime, folly::none, PacketType::OneRtt, true);
351 ASSERT_GT(secondPacketNum, firstPacketNum);
352 ASSERT_EQ(2, conn->outstandings.packets.size());
353 auto lossVisitor = [](auto&, auto&, bool) { ASSERT_FALSE(true); };
354 auto lossEvent = detectLossPackets(
355 *conn,
356 secondPacketNum,
357 lossVisitor,
358 Clock::now(),
359 PacketNumberSpace::AppData);
360 // We should not set loss timer for un-acked d6d probes
361 ASSERT_FALSE(earliestLossTimer(*conn).first.has_value());
362 ASSERT_FALSE(lossEvent);
363 }
364
TEST_F(QuicLossFunctionsTest,NonExclusiveD6DProbeLossIncludedInLossEvent)365 TEST_F(QuicLossFunctionsTest, NonExclusiveD6DProbeLossIncludedInLossEvent) {
366 auto conn = createConn();
367 // 0 rtt means all packets are automatically lost upon sending
368 conn->lossState.srtt = 0s;
369 conn->lossState.lrtt = 0s;
370 conn->d6d.raiser = std::make_unique<MockProbeSizeRaiser>();
371 auto currentTime = Clock::now();
372 auto firstPacketNum =
373 sendPacket(*conn, currentTime, folly::none, PacketType::OneRtt, true);
374 auto secondPacketNum =
375 sendPacket(*conn, currentTime, folly::none, PacketType::OneRtt, false);
376 ASSERT_GT(secondPacketNum, firstPacketNum);
377 ASSERT_EQ(2, conn->outstandings.packets.size());
378 auto lossVisitor = [&](auto&, auto& packet, bool) {
379 EXPECT_EQ(packet.header.getPacketSequenceNum(), secondPacketNum);
380 };
381 auto lossEvent = detectLossPackets(
382 *conn,
383 secondPacketNum + 1,
384 lossVisitor,
385 Clock::now(),
386 PacketNumberSpace::AppData);
387 // We should not set loss timer for un-acked d6d probes
388 ASSERT_TRUE(lossEvent.hasValue());
389 ASSERT_FALSE(earliestLossTimer(*conn).first.has_value());
390 ASSERT_EQ(lossEvent->lostPackets, 1);
391 }
392
393 struct PMTUBlackholeDetectionTestFixture {
394 uint32_t beginPMTU;
395 uint32_t endPMTU;
396 size_t threshold;
397 bool hasLossEvent;
398 uint64_t lostBytes;
399 uint32_t lostPackets;
400 std::chrono::seconds window;
401 PacketNum largestAckedPacketNum;
402 std::chrono::microseconds detectLossTimeDelta;
403 std::chrono::microseconds largestLostTimeDelta;
404 std::chrono::microseconds smallestLostTimeDelta;
405 D6DMachineState beginState;
406 D6DMachineState endState;
407
408 struct PacketSpec {
409 std::chrono::microseconds timeDelta;
410 bool isD6DProbe;
411 uint32_t encodedSize;
412 };
413 std::vector<PacketSpec> packetSpecs;
414 };
415
runDetectPMTUBlackholeTest(QuicConnectionStateBase * conn,PMTUBlackholeDetectionTestFixture fixture)416 void QuicLossFunctionsTest::runDetectPMTUBlackholeTest(
417 QuicConnectionStateBase* conn,
418 PMTUBlackholeDetectionTestFixture fixture) {
419 // 0 rtt means all packets are automatically lost upon sending
420 conn->lossState.srtt = 0s;
421 conn->lossState.lrtt = 0s;
422 conn->d6d.state = D6DMachineState::BASE;
423 conn->d6d.currentProbeSize = fixture.beginPMTU;
424 conn->udpSendPacketLen = fixture.beginPMTU;
425 conn->d6d.thresholdCounter =
426 std::make_unique<WindowedCounter<uint64_t, uint64_t>>(
427 std::chrono::microseconds(fixture.window).count(), fixture.threshold);
428 conn->d6d.raiser = std::make_unique<MockProbeSizeRaiser>();
429 conn->d6d.state = fixture.beginState;
430 auto currentTime = Clock::now();
431 for (auto& spec : fixture.packetSpecs) {
432 sendPacket(
433 *conn,
434 currentTime + spec.timeDelta,
435 folly::none,
436 PacketType::OneRtt,
437 spec.isD6DProbe,
438 spec.encodedSize);
439 }
440 auto lossVisitor = [](auto&, auto&, bool) {};
441 ASSERT_EQ(conn->outstandings.packets.size(), fixture.packetSpecs.size());
442 auto lossEvent = detectLossPackets(
443 *conn,
444 fixture.largestAckedPacketNum,
445 lossVisitor,
446 currentTime + fixture.detectLossTimeDelta,
447 PacketNumberSpace::AppData);
448 EXPECT_EQ(lossEvent.has_value(), fixture.hasLossEvent);
449 if (fixture.hasLossEvent) {
450 EXPECT_EQ(lossEvent->lostPackets, fixture.lostPackets);
451 EXPECT_EQ(lossEvent->lostBytes, fixture.lostBytes);
452 EXPECT_EQ(
453 lossEvent->largestLostSentTime.value(),
454 currentTime + fixture.largestLostTimeDelta);
455 EXPECT_EQ(
456 lossEvent->smallestLostSentTime.value(),
457 currentTime + fixture.smallestLostTimeDelta);
458 EXPECT_EQ(conn->d6d.state, fixture.endState);
459 EXPECT_EQ(conn->d6d.currentProbeSize, fixture.endPMTU);
460 EXPECT_EQ(conn->udpSendPacketLen, fixture.endPMTU);
461 }
462 }
463
TEST_F(QuicLossFunctionsTest,DetectPMTUBlackholeAllNonProbes)464 TEST_F(QuicLossFunctionsTest, DetectPMTUBlackholeAllNonProbes) {
465 // clang-format off
466 PMTUBlackholeDetectionTestFixture fixture {
467 1400, // beginPMTU
468 kDefaultUDPSendPacketLen, // endPMTU
469 3, // threshold
470 true, // hasLossEvent
471 1400 * 3, // lostBytes
472 3, // lostPackets
473 10s, // window
474 3 + kReorderingThreshold, // largestAckedPacketNum
475 11s, // detectLossTimeDelta
476 10s, // largestLostTimeDelta
477 0s, // smallestLostTimeDelta
478 D6DMachineState::SEARCH_COMPLETE, // beginState
479 D6DMachineState::BASE, // beginState
480 { // packetSpecs
481 {0s, false, 1400},
482 {1s, false, 1400},
483 {10s, false, 1400},
484 }
485 };
486 // clang-format on
487 auto conn = createConn();
488 runDetectPMTUBlackholeTest(conn.get(), fixture);
489 }
490
TEST_F(QuicLossFunctionsTest,DetectPMTUBlackholeAllProbes)491 TEST_F(QuicLossFunctionsTest, DetectPMTUBlackholeAllProbes) {
492 // clang-format off
493 PMTUBlackholeDetectionTestFixture fixture {
494 1400, // beginPMTU
495 1400, // endPMTU
496 3, // threshold
497 false, // hasLossEvent
498 0, // lostBytes
499 0, // lostPackets
500 10s, // window
501 3 + kReorderingThreshold, // largestAckedPacketNum
502 11s, // detectLossTimeDelta
503 10s, // largestLostTimeDelta
504 0s, // smallestLostTimeDelta
505 D6DMachineState::SEARCH_COMPLETE, // beginState
506 D6DMachineState::SEARCH_COMPLETE, // beginState
507 { // packetSpecs
508 {0s, true, 1400},
509 {1s, true, 1400},
510 {10s, true, 1400},
511 }
512 };
513 // clang-format on
514 auto conn = createConn();
515 runDetectPMTUBlackholeTest(conn.get(), fixture);
516 }
517
TEST_F(QuicLossFunctionsTest,DetectPMTUBlackholeSparseProbes)518 TEST_F(QuicLossFunctionsTest, DetectPMTUBlackholeSparseProbes) {
519 // clang-format off
520 PMTUBlackholeDetectionTestFixture fixture {
521 1400, // beginPMTU
522 1400, // endPMTU
523 3, // threshold
524 true, // hasLossEvent
525 1400 * 5 + 200, // lostBytes
526 6, // lostPackets
527 10s, // window
528 6 + kReorderingThreshold, // largestAckedPacketNum
529 23s, // detectLossTimeDelta
530 22s, // largestLostTimeDelta
531 0s, // smallestLostTimeDelta
532 D6DMachineState::SEARCH_COMPLETE, // beginState
533 D6DMachineState::SEARCH_COMPLETE, // beginState
534 { // packetSpecs
535 {0s, false, 1400},
536 {1s, false, 1400},
537 {11s, false, 1400},
538 {10s, false, 200},
539 {12s, false, 1400},
540 {22s, false, 1400}
541 }
542 };
543 // clang-format on
544 auto conn = createConn();
545 runDetectPMTUBlackholeTest(conn.get(), fixture);
546 }
547
TEST_F(QuicLossFunctionsTest,DetectPMTUBlackholeRandomData)548 TEST_F(QuicLossFunctionsTest, DetectPMTUBlackholeRandomData) {
549 // clang-format off
550 PMTUBlackholeDetectionTestFixture fixture {
551 1400, // beginPMTU
552 1400, // endPMTU
553 3, // threshold
554 true, // hasLossEvent
555 876 + 249 + 1291 + 1400 * 4 + 1109, // lostBytes
556 8, // lostPackets
557 10s, // window
558 9 + kReorderingThreshold, // largestAckedPacketNum
559 90s, // detectLossTimeDelta
560 83s, // largestLostTimeDelta
561 5s, // smallestLostTimeDelta
562 D6DMachineState::SEARCHING, // beginState
563 D6DMachineState::SEARCHING, // beginState
564 { // packetSpecs
565 { 5s, false, 876 },
566 { 15s, false, 249 },
567 { 19s, false, 1291 },
568 { 31s, false, 1400 },
569 { 40s, true, 1400 },
570 { 51s, false, 1400 },
571 { 61s, false, 1400 },
572 { 73s, false, 1400 },
573 { 83s, false, 1109 },
574 { 85s, true, 1400 }
575 }
576 };
577 // clang-format on
578 auto conn = createConn();
579 runDetectPMTUBlackholeTest(conn.get(), fixture);
580 }
581
TEST_F(QuicLossFunctionsTest,ClearEarlyRetranTimer)582 TEST_F(QuicLossFunctionsTest, ClearEarlyRetranTimer) {
583 auto conn = createConn();
584 // make delayUntilLoss relatively large
585 conn->lossState.srtt = 1s;
586 conn->lossState.lrtt = 1s;
587 auto currentTime = Clock::now();
588 auto firstPacketNum =
589 sendPacket(*conn, currentTime, folly::none, PacketType::Initial);
590 auto secondPacketNum =
591 sendPacket(*conn, currentTime, folly::none, PacketType::Initial);
592 ASSERT_GT(secondPacketNum, firstPacketNum);
593 ASSERT_EQ(2, conn->outstandings.packets.size());
594 // detectLossPackets will set lossTime on Initial space.
595 auto lossVisitor = [](auto&, auto&, bool) { ASSERT_FALSE(true); };
596 detectLossPackets(
597 *conn,
598 secondPacketNum,
599 lossVisitor,
600 Clock::now(),
601 PacketNumberSpace::Initial);
602 ASSERT_TRUE(earliestLossTimer(*conn).first.has_value());
603 ASSERT_EQ(PacketNumberSpace::Initial, earliestLossTimer(*conn).second);
604 conn->pendingEvents.setLossDetectionAlarm = true;
605
606 // Schedule a loss timer
607 EXPECT_CALL(timeout, isLossTimeoutScheduled()).WillRepeatedly(Return(false));
608 EXPECT_CALL(timeout, cancelLossTimeout()).Times(1);
609 EXPECT_CALL(timeout, scheduleLossTimeout(_)).Times(1);
610 setLossDetectionAlarm(*conn, timeout);
611 EXPECT_EQ(
612 LossState::AlarmMethod::EarlyRetransmitOrReordering,
613 conn->lossState.currentAlarmMethod);
614
615 // Ack the initial packets
616 ReadAckFrame ackFrame;
617 ackFrame.largestAcked = secondPacketNum;
618 ackFrame.ackBlocks.emplace_back(firstPacketNum, secondPacketNum);
619 // Ack won't cancel loss timer
620 EXPECT_CALL(timeout, cancelLossTimeout()).Times(0);
621 processAckFrame(
622 *conn,
623 PacketNumberSpace::Initial,
624 ackFrame,
625 [&](auto&, auto&, auto&) {},
626 lossVisitor,
627 Clock::now());
628
629 // Send out a AppData packet that isn't retransmittable
630 sendPacket(*conn, Clock::now(), folly::none, PacketType::OneRtt);
631 conn->pendingEvents.setLossDetectionAlarm = false;
632
633 // setLossDetectionAlarm will cancel loss timer, and not schedule another one.
634 EXPECT_CALL(timeout, isLossTimeoutScheduled())
635 .Times(1)
636 .WillOnce(Return(false));
637 EXPECT_CALL(timeout, cancelLossTimeout()).Times(1);
638 EXPECT_CALL(timeout, scheduleLossTimeout(_)).Times(0);
639 setLossDetectionAlarm(*conn, timeout);
640 }
641
TEST_F(QuicLossFunctionsTest,TestOnLossDetectionAlarm)642 TEST_F(QuicLossFunctionsTest, TestOnLossDetectionAlarm) {
643 auto conn = createConn();
644 auto mockCongestionController = std::make_unique<MockCongestionController>();
645 auto rawCongestionController = mockCongestionController.get();
646 conn->congestionController = std::move(mockCongestionController);
647 EXPECT_CALL(*rawCongestionController, onPacketSent(_))
648 .WillRepeatedly(Return());
649
650 sendPacket(*conn, Clock::now(), folly::none, PacketType::OneRtt);
651 MockClock::mockNow = []() { return TimePoint(123ms); };
652 std::vector<PacketNum> lostPacket;
653 MockClock::mockNow = []() { return TimePoint(23ms); };
654 EXPECT_CALL(*transportInfoCb_, onPTO());
655 setLossDetectionAlarm<decltype(timeout), MockClock>(*conn, timeout);
656 EXPECT_EQ(LossState::AlarmMethod::PTO, conn->lossState.currentAlarmMethod);
657 onLossDetectionAlarm<decltype(testingLossMarkFunc(lostPacket)), MockClock>(
658 *conn, testingLossMarkFunc(lostPacket));
659 EXPECT_EQ(conn->lossState.ptoCount, 1);
660 EXPECT_TRUE(conn->pendingEvents.setLossDetectionAlarm);
661 // PTO shouldn't mark loss
662 EXPECT_TRUE(lostPacket.empty());
663
664 MockClock::mockNow = []() { return TimePoint(3ms); };
665 EXPECT_CALL(*transportInfoCb_, onPTO());
666 sendPacket(*conn, TimePoint(), folly::none, PacketType::OneRtt);
667 setLossDetectionAlarm<decltype(timeout), MockClock>(*conn, timeout);
668 EXPECT_CALL(*rawCongestionController, onPacketAckOrLoss(_, _)).Times(0);
669 onLossDetectionAlarm<decltype(testingLossMarkFunc(lostPacket)), MockClock>(
670 *conn, testingLossMarkFunc(lostPacket));
671 EXPECT_EQ(conn->lossState.ptoCount, 2);
672 // PTO doesn't take anything out of outstandings.packets
673 EXPECT_FALSE(conn->outstandings.packets.empty());
674 EXPECT_TRUE(conn->pendingEvents.setLossDetectionAlarm);
675 // PTO shouldn't mark loss
676 EXPECT_TRUE(lostPacket.empty());
677 }
678
TEST_F(QuicLossFunctionsTest,TestOnPTOSkipProcessed)679 TEST_F(QuicLossFunctionsTest, TestOnPTOSkipProcessed) {
680 auto conn = createConn();
681 auto mockCongestionController = std::make_unique<MockCongestionController>();
682 auto rawCongestionController = mockCongestionController.get();
683 conn->congestionController = std::move(mockCongestionController);
684 EXPECT_CALL(*rawCongestionController, onPacketSent(_))
685 .WillRepeatedly(Return());
686 // By adding an associatedEvent that doesn't exist in the
687 // outstandings.packetEvents, they are all processed and will skip lossVisitor
688 for (auto i = 0; i < 10; i++) {
689 PacketEvent packetEvent(PacketNumberSpace::AppData, i);
690 sendPacket(*conn, TimePoint(), packetEvent, PacketType::OneRtt);
691 }
692 EXPECT_EQ(10, conn->outstandings.packets.size());
693 std::vector<PacketNum> lostPackets;
694 EXPECT_CALL(*rawCongestionController, onRemoveBytesFromInflight(_)).Times(0);
695 EXPECT_CALL(*transportInfoCb_, onPTO());
696 onPTOAlarm(*conn);
697 EXPECT_EQ(10, conn->outstandings.packets.size());
698 EXPECT_TRUE(lostPackets.empty());
699 }
700
TEST_F(QuicLossFunctionsTest,TestMarkPacketLoss)701 TEST_F(QuicLossFunctionsTest, TestMarkPacketLoss) {
702 folly::EventBase evb;
703 MockAsyncUDPSocket socket(&evb);
704 auto conn = createConn();
705 EXPECT_CALL(*transportInfoCb_, onNewQuicStream()).Times(2);
706 auto stream1Id =
707 conn->streamManager->createNextBidirectionalStream().value()->id;
708 auto stream2Id =
709 conn->streamManager->createNextBidirectionalStream().value()->id;
710 auto stream1 = conn->streamManager->findStream(stream1Id);
711 auto stream2 = conn->streamManager->findStream(stream2Id);
712 auto buf = buildRandomInputData(20);
713 writeDataToQuicStream(*stream1, buf->clone(), true);
714 writeDataToQuicStream(*stream2, buf->clone(), true);
715
716 auto packetSeqNum = conn->ackStates.handshakeAckState.nextPacketNum;
717 LongHeader header(
718 LongHeader::Types::Handshake,
719 *conn->clientConnectionId,
720 *conn->serverConnectionId,
721 packetSeqNum,
722 *conn->version);
723 writeQuicDataToSocket(
724 socket,
725 *conn,
726 *conn->clientConnectionId,
727 *conn->serverConnectionId,
728 *aead,
729 *headerCipher,
730 *conn->version,
731 conn->transportSettings.writeConnectionDataPacketsLimit);
732
733 EXPECT_EQ(1, conn->outstandings.packets.size());
734 auto& packet =
735 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData)->packet;
736 markPacketLoss(*conn, packet, false);
737 EXPECT_EQ(stream1->retransmissionBuffer.size(), 0);
738 EXPECT_EQ(stream2->retransmissionBuffer.size(), 0);
739 EXPECT_EQ(stream1->lossBuffer.size(), 1);
740 EXPECT_EQ(stream2->lossBuffer.size(), 1);
741
742 auto& buffer = stream1->lossBuffer.front();
743 EXPECT_EQ(buffer.offset, 0);
744 IOBufEqualTo eq;
745 EXPECT_TRUE(eq(buf, buffer.data.move()));
746 }
747
TEST_F(QuicLossFunctionsTest,TestMarkPacketLossMerge)748 TEST_F(QuicLossFunctionsTest, TestMarkPacketLossMerge) {
749 folly::EventBase evb;
750 MockAsyncUDPSocket socket(&evb);
751 auto conn = createConn();
752 EXPECT_CALL(*transportInfoCb_, onNewQuicStream()).Times(1);
753 auto stream1Id =
754 conn->streamManager->createNextBidirectionalStream().value()->id;
755 auto stream1 = conn->streamManager->findStream(stream1Id);
756
757 auto buf1 = buildRandomInputData(20);
758 writeDataToQuicStream(*stream1, buf1->clone(), false);
759 writeQuicDataToSocket(
760 socket,
761 *conn,
762 *conn->clientConnectionId,
763 *conn->serverConnectionId,
764 *aead,
765 *headerCipher,
766 *conn->version,
767 conn->transportSettings.writeConnectionDataPacketsLimit);
768 EXPECT_EQ(1, conn->outstandings.packets.size());
769
770 auto buf2 = buildRandomInputData(20);
771 writeDataToQuicStream(*stream1, buf2->clone(), false);
772 writeQuicDataToSocket(
773 socket,
774 *conn,
775 *conn->clientConnectionId,
776 *conn->serverConnectionId,
777 *aead,
778 *headerCipher,
779 *conn->version,
780 conn->transportSettings.writeConnectionDataPacketsLimit);
781 EXPECT_EQ(2, conn->outstandings.packets.size());
782
783 auto& packet1 =
784 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData)->packet;
785 auto packetNum = packet1.header.getPacketSequenceNum();
786 markPacketLoss(*conn, packet1, false);
787 EXPECT_EQ(stream1->retransmissionBuffer.size(), 1);
788 EXPECT_EQ(stream1->lossBuffer.size(), 1);
789 auto& packet2 =
790 getLastOutstandingPacket(*conn, PacketNumberSpace::AppData)->packet;
791 packetNum = packet2.header.getPacketSequenceNum();
792 markPacketLoss(*conn, packet2, false);
793 EXPECT_EQ(stream1->retransmissionBuffer.size(), 0);
794 EXPECT_EQ(stream1->lossBuffer.size(), 1);
795
796 auto combined = buf1->clone();
797 combined->prependChain(buf2->clone());
798 auto& buffer = stream1->lossBuffer.front();
799 EXPECT_EQ(buffer.offset, 0);
800 IOBufEqualTo eq;
801 EXPECT_TRUE(eq(combined, buffer.data.move()));
802 }
803
TEST_F(QuicLossFunctionsTest,TestMarkPacketLossNoMerge)804 TEST_F(QuicLossFunctionsTest, TestMarkPacketLossNoMerge) {
805 folly::EventBase evb;
806 MockAsyncUDPSocket socket(&evb);
807 auto conn = createConn();
808 EXPECT_CALL(*transportInfoCb_, onNewQuicStream()).Times(1);
809 auto stream1Id =
810 conn->streamManager->createNextBidirectionalStream().value()->id;
811 auto stream1 = conn->streamManager->findStream(stream1Id);
812
813 auto buf1 = buildRandomInputData(20);
814 writeDataToQuicStream(*stream1, buf1->clone(), false);
815 writeQuicDataToSocket(
816 socket,
817 *conn,
818 *conn->clientConnectionId,
819 *conn->serverConnectionId,
820 *aead,
821 *headerCipher,
822 *conn->version,
823 conn->transportSettings.writeConnectionDataPacketsLimit);
824 EXPECT_EQ(1, conn->outstandings.packets.size());
825
826 auto buf2 = buildRandomInputData(20);
827 writeDataToQuicStream(*stream1, buf2->clone(), false);
828 writeQuicDataToSocket(
829 socket,
830 *conn,
831 *conn->clientConnectionId,
832 *conn->serverConnectionId,
833 *aead,
834 *headerCipher,
835 *conn->version,
836 conn->transportSettings.writeConnectionDataPacketsLimit);
837 EXPECT_EQ(2, conn->outstandings.packets.size());
838
839 auto buf3 = buildRandomInputData(20);
840 writeDataToQuicStream(*stream1, buf3->clone(), false);
841 writeQuicDataToSocket(
842 socket,
843 *conn,
844 *conn->clientConnectionId,
845 *conn->serverConnectionId,
846 *aead,
847 *headerCipher,
848 *conn->version,
849 conn->transportSettings.writeConnectionDataPacketsLimit);
850 EXPECT_EQ(3, conn->outstandings.packets.size());
851
852 auto& packet1 =
853 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData)->packet;
854 auto packetNum = packet1.header.getPacketSequenceNum();
855 markPacketLoss(*conn, packet1, false);
856 EXPECT_EQ(stream1->retransmissionBuffer.size(), 2);
857 EXPECT_EQ(stream1->lossBuffer.size(), 1);
858 auto& packet3 =
859 getLastOutstandingPacket(*conn, PacketNumberSpace::AppData)->packet;
860 packetNum = packet3.header.getPacketSequenceNum();
861 markPacketLoss(*conn, packet3, false);
862 EXPECT_EQ(stream1->retransmissionBuffer.size(), 1);
863 EXPECT_EQ(stream1->lossBuffer.size(), 2);
864
865 auto& buffer1 = stream1->lossBuffer[0];
866 EXPECT_EQ(buffer1.offset, 0);
867 IOBufEqualTo eq;
868 EXPECT_TRUE(eq(buf1, buffer1.data.move()));
869
870 auto& buffer3 = stream1->lossBuffer[1];
871 EXPECT_EQ(buffer3.offset, 40);
872 EXPECT_TRUE(eq(buf3, buffer3.data.move()));
873 }
874
TEST_F(QuicLossFunctionsTest,RetxBufferSortedAfterLoss)875 TEST_F(QuicLossFunctionsTest, RetxBufferSortedAfterLoss) {
876 folly::EventBase evb;
877 MockAsyncUDPSocket socket(&evb);
878 auto conn = createConn();
879 auto stream = conn->streamManager->createNextBidirectionalStream().value();
880 auto buf1 = IOBuf::copyBuffer("Worse case scenario");
881 auto buf2 = IOBuf::copyBuffer("The hard problem");
882 auto buf3 = IOBuf::copyBuffer("And then we had a flash of insight...");
883 writeQuicPacket(
884 *conn,
885 *conn->clientConnectionId,
886 *conn->serverConnectionId,
887 socket,
888 *stream,
889 *buf1);
890 writeQuicPacket(
891 *conn,
892 *conn->clientConnectionId,
893 *conn->serverConnectionId,
894 socket,
895 *stream,
896 *buf2);
897 writeQuicPacket(
898 *conn,
899 *conn->clientConnectionId,
900 *conn->serverConnectionId,
901 socket,
902 *stream,
903 *buf3);
904 EXPECT_EQ(3, stream->retransmissionBuffer.size());
905 EXPECT_EQ(3, conn->outstandings.packets.size());
906 auto packet = conn->outstandings.packets[folly::Random::rand32() % 3];
907 markPacketLoss(*conn, packet.packet, false);
908 EXPECT_EQ(2, stream->retransmissionBuffer.size());
909 }
910
TEST_F(QuicLossFunctionsTest,TestMarkPacketLossAfterStreamReset)911 TEST_F(QuicLossFunctionsTest, TestMarkPacketLossAfterStreamReset) {
912 folly::EventBase evb;
913 MockAsyncUDPSocket socket(&evb);
914 auto conn = createConn();
915 auto stream1 = conn->streamManager->createNextBidirectionalStream().value();
916 auto buf = buildRandomInputData(20);
917
918 auto packet = writeQuicPacket(
919 *conn,
920 *conn->clientConnectionId,
921 *conn->serverConnectionId,
922 socket,
923 *stream1,
924 *buf,
925 true);
926 sendRstSMHandler(*stream1, GenericApplicationErrorCode::UNKNOWN);
927
928 markPacketLoss(*conn, packet, false);
929
930 EXPECT_TRUE(stream1->lossBuffer.empty());
931 EXPECT_TRUE(stream1->retransmissionBuffer.empty());
932 EXPECT_TRUE(stream1->writeBuffer.empty());
933 }
934
TEST_F(QuicLossFunctionsTest,TestReorderingThreshold)935 TEST_F(QuicLossFunctionsTest, TestReorderingThreshold) {
936 std::vector<PacketNum> lostPacket;
937 auto conn = createConn();
938
939 auto mockCongestionController = std::make_unique<MockCongestionController>();
940 auto rawCongestionController = mockCongestionController.get();
941 conn->congestionController = std::move(mockCongestionController);
942 EXPECT_CALL(*rawCongestionController, onPacketSent(_))
943 .WillRepeatedly(Return());
944
945 auto testingLossMarkFunc = [&lostPacket](auto& /*conn*/, auto& packet, bool) {
946 auto packetNum = packet.header.getPacketSequenceNum();
947 lostPacket.push_back(packetNum);
948 };
949 for (int i = 0; i < 6; ++i) {
950 sendPacket(*conn, Clock::now(), folly::none, PacketType::Handshake);
951 }
952 EXPECT_EQ(6, conn->outstandings.packetCount[PacketNumberSpace::Handshake]);
953 // Assume some packets are already acked
954 for (auto iter =
955 getFirstOutstandingPacket(*conn, PacketNumberSpace::Handshake) + 2;
956 iter <
957 getFirstOutstandingPacket(*conn, PacketNumberSpace::Handshake) + 5;
958 iter++) {
959 if (iter->metadata.isHandshake) {
960 conn->outstandings.packetCount[PacketNumberSpace::Handshake]--;
961 }
962 }
963 auto firstHandshakeOpIter =
964 getFirstOutstandingPacket(*conn, PacketNumberSpace::Handshake);
965 conn->outstandings.packets.erase(
966 firstHandshakeOpIter + 2, firstHandshakeOpIter + 5);
967 // Ack for packet 9 arrives
968 auto lossEvent = detectLossPackets<decltype(testingLossMarkFunc)>(
969 *conn,
970 9,
971 testingLossMarkFunc,
972 TimePoint(90ms),
973 PacketNumberSpace::Handshake);
974 EXPECT_EQ(2, lossEvent->largestLostPacketNum.value());
975 EXPECT_EQ(TimePoint(90ms), lossEvent->lossTime);
976 // Packet 1,2 should be marked as loss
977 EXPECT_EQ(lostPacket.size(), 2);
978 EXPECT_EQ(lostPacket.front(), 1);
979 EXPECT_EQ(lostPacket.back(), 2);
980
981 // Packet 6 is the only thing remaining inflight, it is a handshake pkt
982 EXPECT_EQ(1, conn->outstandings.packetCount[PacketNumberSpace::Handshake]);
983
984 // Packet 6 should remain in packet as the delta is less than threshold
985 auto numDeclaredLost = std::count_if(
986 conn->outstandings.packets.begin(),
987 conn->outstandings.packets.end(),
988 [](auto& op) { return op.declaredLost; });
989 EXPECT_EQ(conn->outstandings.packets.size(), 1 + numDeclaredLost);
990 auto first = getFirstOutstandingPacket(*conn, PacketNumberSpace::Handshake);
991 auto packetNum = first->packet.header.getPacketSequenceNum();
992 EXPECT_EQ(packetNum, 6);
993 }
994
TEST_F(QuicLossFunctionsTest,TestHandleAckForLoss)995 TEST_F(QuicLossFunctionsTest, TestHandleAckForLoss) {
996 auto conn = createConn();
997 auto mockQLogger = std::make_shared<MockQLogger>(VantagePoint::Server);
998 conn->qLogger = mockQLogger;
999 conn->lossState.ptoCount = 100;
1000 conn->lossState.reorderingThreshold = 10;
1001
1002 LongHeader longHeader(
1003 LongHeader::Types::Handshake,
1004 *conn->clientConnectionId,
1005 *conn->serverConnectionId,
1006 conn->ackStates.handshakeAckState.nextPacketNum++,
1007 conn->version.value());
1008 RegularQuicWritePacket outstandingRegularPacket(std::move(longHeader));
1009 auto now = Clock::now();
1010 conn->outstandings.packets.emplace_back(OutstandingPacket(
1011 outstandingRegularPacket, now, 0, 0, false, 0, 0, 0, 0, LossState(), 0));
1012 conn->outstandings.packetCount[PacketNumberSpace::Handshake]++;
1013
1014 bool testLossMarkFuncCalled = false;
1015 auto testLossMarkFunc = [&](auto& /* conn */, auto&, bool) {
1016 testLossMarkFuncCalled = true;
1017 };
1018 EXPECT_CALL(*mockQLogger, addPacketsLost(1, 0, 1));
1019
1020 CongestionController::AckEvent ackEvent;
1021 ackEvent.ackTime = now;
1022 ackEvent.largestAckedPacket = 1000;
1023 handleAckForLoss(
1024 *conn, testLossMarkFunc, ackEvent, PacketNumberSpace::Handshake);
1025
1026 auto numDeclaredLost = std::count_if(
1027 conn->outstandings.packets.begin(),
1028 conn->outstandings.packets.end(),
1029 [](auto& op) { return op.declaredLost; });
1030 EXPECT_EQ(1, numDeclaredLost);
1031 EXPECT_EQ(0, conn->lossState.ptoCount);
1032 EXPECT_EQ(numDeclaredLost, conn->outstandings.packets.size());
1033 EXPECT_FALSE(conn->pendingEvents.setLossDetectionAlarm);
1034 EXPECT_TRUE(testLossMarkFuncCalled);
1035 }
1036
TEST_F(QuicLossFunctionsTest,TestHandleAckedPacket)1037 TEST_F(QuicLossFunctionsTest, TestHandleAckedPacket) {
1038 auto conn = createConn();
1039 auto mockQLogger = std::make_shared<MockQLogger>(VantagePoint::Server);
1040 conn->qLogger = mockQLogger;
1041 conn->lossState.ptoCount = 10;
1042 conn->lossState.reorderingThreshold = 10;
1043
1044 sendPacket(*conn, TimePoint(), folly::none, PacketType::OneRtt);
1045
1046 ReadAckFrame ackFrame;
1047 ackFrame.largestAcked = conn->lossState.largestSent.value_or(0);
1048 ackFrame.ackBlocks.emplace_back(
1049 conn->lossState.largestSent.value_or(0),
1050 conn->lossState.largestSent.value_or(0));
1051
1052 bool testLossMarkFuncCalled = false;
1053 auto testLossMarkFunc = [&](auto& /* conn */, auto&, bool) {
1054 testLossMarkFuncCalled = true;
1055 };
1056
1057 auto ackVisitor = [&](auto&, auto&, auto&) {};
1058
1059 // process and remove the acked packet.
1060 processAckFrame(
1061 *conn,
1062 PacketNumberSpace::AppData,
1063 ackFrame,
1064 ackVisitor,
1065 testLossMarkFunc,
1066 Clock::now());
1067
1068 EXPECT_EQ(0, conn->lossState.ptoCount);
1069 EXPECT_TRUE(conn->outstandings.packets.empty());
1070 EXPECT_FALSE(conn->pendingEvents.setLossDetectionAlarm);
1071 EXPECT_FALSE(testLossMarkFuncCalled);
1072 ASSERT_TRUE(conn->outstandings.packets.empty());
1073
1074 setLossDetectionAlarm<decltype(timeout), MockClock>(*conn, timeout);
1075 EXPECT_FALSE(conn->pendingEvents.setLossDetectionAlarm);
1076 }
1077
TEST_F(QuicLossFunctionsTest,TestMarkRstLoss)1078 TEST_F(QuicLossFunctionsTest, TestMarkRstLoss) {
1079 auto conn = createConn();
1080 folly::EventBase evb;
1081 MockAsyncUDPSocket socket(&evb);
1082
1083 auto stream = conn->streamManager->createNextBidirectionalStream().value();
1084 auto currentOffset = stream->currentWriteOffset;
1085 RstStreamFrame rstFrame(
1086 stream->id, GenericApplicationErrorCode::UNKNOWN, currentOffset);
1087 conn->pendingEvents.resets.insert({stream->id, rstFrame});
1088 writeQuicDataToSocket(
1089 socket,
1090 *conn,
1091 *conn->clientConnectionId,
1092 *conn->serverConnectionId,
1093 *aead,
1094 *headerCipher,
1095 *conn->version,
1096 conn->transportSettings.writeConnectionDataPacketsLimit);
1097
1098 EXPECT_EQ(conn->outstandings.packets.size(), 1);
1099 EXPECT_TRUE(conn->pendingEvents.resets.empty());
1100 auto& packet =
1101 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData)->packet;
1102 markPacketLoss(*conn, packet, false);
1103
1104 EXPECT_EQ(1, conn->pendingEvents.resets.size());
1105 EXPECT_EQ(1, conn->pendingEvents.resets.count(stream->id));
1106 auto& retxRstFrame = conn->pendingEvents.resets.at(stream->id);
1107 EXPECT_EQ(stream->id, retxRstFrame.streamId);
1108 EXPECT_EQ(GenericApplicationErrorCode::UNKNOWN, retxRstFrame.errorCode);
1109 EXPECT_EQ(currentOffset, retxRstFrame.offset);
1110
1111 // write again:
1112 writeQuicDataToSocket(
1113 socket,
1114 *conn,
1115 *conn->clientConnectionId,
1116 *conn->serverConnectionId,
1117 *aead,
1118 *headerCipher,
1119 *conn->version,
1120 conn->transportSettings.writeConnectionDataPacketsLimit);
1121 EXPECT_TRUE(conn->pendingEvents.resets.empty());
1122 auto& packet2 =
1123 getLastOutstandingPacket(*conn, PacketNumberSpace::AppData)->packet;
1124 bool rstFound = false;
1125 for (auto& frame : packet2.frames) {
1126 auto resetFrame = frame.asRstStreamFrame();
1127 if (!resetFrame) {
1128 continue;
1129 }
1130 EXPECT_EQ(stream->id, resetFrame->streamId);
1131 EXPECT_EQ(GenericApplicationErrorCode::UNKNOWN, resetFrame->errorCode);
1132 EXPECT_EQ(currentOffset, resetFrame->offset);
1133 rstFound = true;
1134 }
1135 EXPECT_TRUE(rstFound);
1136 }
1137
TEST_F(QuicLossFunctionsTest,ReorderingThresholdChecksSamePacketNumberSpace)1138 TEST_F(QuicLossFunctionsTest, ReorderingThresholdChecksSamePacketNumberSpace) {
1139 auto conn = createConn();
1140 uint16_t lossVisitorCount = 0;
1141 auto countingLossVisitor =
1142 [&](auto& /* conn */, auto& /* packet */, bool processed) {
1143 if (!processed) {
1144 lossVisitorCount++;
1145 }
1146 };
1147 PacketNum latestSent = 0;
1148 for (size_t i = 0; i < conn->lossState.reorderingThreshold + 1; i++) {
1149 latestSent =
1150 sendPacket(*conn, Clock::now(), folly::none, PacketType::Handshake);
1151 }
1152
1153 detectLossPackets(
1154 *conn,
1155 latestSent + 1,
1156 countingLossVisitor,
1157 Clock::now(),
1158 PacketNumberSpace::AppData);
1159 EXPECT_EQ(0, lossVisitorCount);
1160
1161 detectLossPackets(
1162 *conn,
1163 latestSent + 1,
1164 countingLossVisitor,
1165 Clock::now(),
1166 PacketNumberSpace::Handshake);
1167 EXPECT_GT(lossVisitorCount, 0);
1168 }
1169
TEST_F(QuicLossFunctionsTest,TestMarkWindowUpdateLoss)1170 TEST_F(QuicLossFunctionsTest, TestMarkWindowUpdateLoss) {
1171 auto conn = createConn();
1172 folly::EventBase evb;
1173 MockAsyncUDPSocket socket(&evb);
1174
1175 auto stream = conn->streamManager->createNextBidirectionalStream().value();
1176 conn->streamManager->queueWindowUpdate(stream->id);
1177 writeQuicDataToSocket(
1178 socket,
1179 *conn,
1180 *conn->clientConnectionId,
1181 *conn->serverConnectionId,
1182 *aead,
1183 *headerCipher,
1184 *conn->version,
1185 conn->transportSettings.writeConnectionDataPacketsLimit);
1186 EXPECT_FALSE(conn->streamManager->hasWindowUpdates());
1187
1188 EXPECT_EQ(1, conn->outstandings.packets.size());
1189 auto& packet =
1190 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData)->packet;
1191
1192 markPacketLoss(*conn, packet, false);
1193 EXPECT_TRUE(conn->streamManager->pendingWindowUpdate(stream->id));
1194 }
1195
TEST_F(QuicLossFunctionsTest,TestTimeReordering)1196 TEST_F(QuicLossFunctionsTest, TestTimeReordering) {
1197 std::vector<PacketNum> lostPacket;
1198 auto conn = createConn();
1199 auto mockCongestionController = std::make_unique<MockCongestionController>();
1200 auto rawCongestionController = mockCongestionController.get();
1201 conn->congestionController = std::move(mockCongestionController);
1202 EXPECT_CALL(*rawCongestionController, onPacketSent(_))
1203 .WillRepeatedly(Return());
1204
1205 PacketNum largestSent = 0;
1206 for (int i = 0; i < 7; ++i) {
1207 largestSent = sendPacket(
1208 *conn, TimePoint(i * 100ms), folly::none, PacketType::OneRtt);
1209 }
1210 // Some packets are already acked
1211 conn->lossState.srtt = 400ms;
1212 conn->lossState.lrtt = 350ms;
1213 conn->outstandings.packets.erase(
1214 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData) + 2,
1215 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData) + 5);
1216 auto lossEvent = detectLossPackets<decltype(testingLossMarkFunc(lostPacket))>(
1217 *conn,
1218 largestSent,
1219 testingLossMarkFunc(lostPacket),
1220 TimePoint(900ms),
1221 PacketNumberSpace::AppData);
1222 EXPECT_EQ(2, lossEvent->largestLostPacketNum.value());
1223 EXPECT_EQ(TimePoint(900ms), lossEvent->lossTime);
1224 // Packet 1,2 should be marked as loss
1225 auto numDeclaredLost = std::count_if(
1226 conn->outstandings.packets.begin(),
1227 conn->outstandings.packets.end(),
1228 [](auto& op) { return op.declaredLost; });
1229 EXPECT_EQ(lostPacket.size(), 2);
1230 EXPECT_EQ(numDeclaredLost, lostPacket.size());
1231 EXPECT_EQ(lostPacket.front(), 1);
1232 EXPECT_EQ(lostPacket.back(), 2);
1233
1234 // Packet 6, 7 should remain in outstanding packet list
1235 EXPECT_EQ(2 + numDeclaredLost, conn->outstandings.packets.size());
1236 auto packetNum = getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData)
1237 ->packet.header.getPacketSequenceNum();
1238 EXPECT_EQ(packetNum, 6);
1239 EXPECT_TRUE(conn->lossState.lossTimes[PacketNumberSpace::AppData]);
1240 }
1241
TEST_F(QuicLossFunctionsTest,LossTimePreemptsCryptoTimer)1242 TEST_F(QuicLossFunctionsTest, LossTimePreemptsCryptoTimer) {
1243 std::vector<PacketNum> lostPackets;
1244 auto conn = createConn();
1245 conn->lossState.srtt = 100ms;
1246 conn->lossState.lrtt = 100ms;
1247 auto expectedDelayUntilLost =
1248 500ms / conn->transportSettings.timeReorderingThreshDivisor;
1249 auto sendTime = Clock::now();
1250 // Send two:
1251 sendPacket(*conn, sendTime, folly::none, PacketType::Handshake);
1252 PacketNum second =
1253 sendPacket(*conn, sendTime + 1ms, folly::none, PacketType::Handshake);
1254 auto lossTime = sendTime + 50ms;
1255 detectLossPackets<decltype(testingLossMarkFunc(lostPackets))>(
1256 *conn,
1257 second,
1258 testingLossMarkFunc(lostPackets),
1259 lossTime,
1260 PacketNumberSpace::Handshake);
1261 EXPECT_TRUE(lostPackets.empty());
1262 EXPECT_TRUE(
1263 conn->lossState.lossTimes[PacketNumberSpace::Handshake].has_value());
1264 EXPECT_EQ(
1265 expectedDelayUntilLost + sendTime,
1266 conn->lossState.lossTimes[PacketNumberSpace::Handshake].value());
1267
1268 MockClock::mockNow = [=]() { return sendTime; };
1269 auto alarm = calculateAlarmDuration<MockClock>(*conn);
1270 EXPECT_EQ(
1271 folly::chrono::ceil<std::chrono::milliseconds>(expectedDelayUntilLost),
1272 alarm.first);
1273 EXPECT_EQ(LossState::AlarmMethod::EarlyRetransmitOrReordering, alarm.second);
1274 // Manual set lossState. Calling setLossDetectionAlarm requries a Timeout
1275 conn->lossState.currentAlarmMethod = alarm.second;
1276
1277 // Second packet gets acked:
1278 getAckState(*conn, PacketNumberSpace::Handshake).largestAckedByPeer = second;
1279 conn->outstandings.packets.pop_back();
1280 MockClock::mockNow = [=]() { return sendTime + expectedDelayUntilLost + 5s; };
1281 onLossDetectionAlarm<decltype(testingLossMarkFunc(lostPackets)), MockClock>(
1282 *conn, testingLossMarkFunc(lostPackets));
1283 auto numDeclaredLost = std::count_if(
1284 conn->outstandings.packets.begin(),
1285 conn->outstandings.packets.end(),
1286 [](auto& op) { return op.declaredLost; });
1287 EXPECT_EQ(1, lostPackets.size());
1288 EXPECT_EQ(numDeclaredLost, lostPackets.size());
1289 EXPECT_FALSE(
1290 conn->lossState.lossTimes[PacketNumberSpace::Handshake].has_value());
1291 EXPECT_EQ(numDeclaredLost, conn->outstandings.packets.size());
1292 }
1293
TEST_F(QuicLossFunctionsTest,PTONoLongerMarksPacketsToBeRetransmitted)1294 TEST_F(QuicLossFunctionsTest, PTONoLongerMarksPacketsToBeRetransmitted) {
1295 auto conn = createConn();
1296 auto mockCongestionController = std::make_unique<MockCongestionController>();
1297 auto rawCongestionController = mockCongestionController.get();
1298 conn->congestionController = std::move(mockCongestionController);
1299 EXPECT_CALL(*rawCongestionController, onPacketSent(_))
1300 .WillRepeatedly(Return());
1301
1302 TimePoint startTime(123ms);
1303 MockClock::mockNow = [&]() { return startTime; };
1304 std::vector<PacketNum> lostPackets;
1305 for (auto i = 0; i < kPacketToSendForPTO + 10; i++) {
1306 sendPacket(*conn, startTime, folly::none, PacketType::OneRtt);
1307 setLossDetectionAlarm<decltype(timeout), MockClock>(*conn, timeout);
1308 startTime += 1ms;
1309 }
1310 EXPECT_CALL(*rawCongestionController, onPacketAckOrLoss(_, _)).Times(0);
1311 EXPECT_CALL(*transportInfoCb_, onPTO());
1312 onLossDetectionAlarm<decltype(testingLossMarkFunc(lostPackets)), MockClock>(
1313 *conn, testingLossMarkFunc(lostPackets));
1314 EXPECT_EQ(1, conn->lossState.ptoCount);
1315 // Hey PTOs are not losses either from now on
1316 EXPECT_TRUE(lostPackets.empty());
1317 }
1318
TEST_F(QuicLossFunctionsTest,PTOWithHandshakePackets)1319 TEST_F(QuicLossFunctionsTest, PTOWithHandshakePackets) {
1320 auto conn = createConn();
1321 conn->handshakeWriteCipher = createNoOpAead();
1322 conn->handshakeWriteHeaderCipher = createNoOpHeaderCipher();
1323 auto mockQLogger = std::make_shared<MockQLogger>(VantagePoint::Server);
1324 conn->qLogger = mockQLogger;
1325 auto mockCongestionController = std::make_unique<MockCongestionController>();
1326 auto rawCongestionController = mockCongestionController.get();
1327 conn->congestionController = std::move(mockCongestionController);
1328 EXPECT_CALL(*rawCongestionController, onPacketSent(_))
1329 .WillRepeatedly(Return());
1330 EXPECT_CALL(*mockQLogger, addLossAlarm(_, _, _, _));
1331 std::vector<PacketNum> lostPackets;
1332 PacketNum expectedLargestLostNum = 0;
1333 conn->lossState.currentAlarmMethod = LossState::AlarmMethod::PTO;
1334 for (auto i = 0; i < 10; i++) {
1335 // Half are handshakes
1336 auto sentPacketNum = sendPacket(
1337 *conn,
1338 TimePoint(100ms),
1339 folly::none,
1340 (i % 2 ? PacketType::OneRtt : PacketType::Handshake));
1341 expectedLargestLostNum = std::max(
1342 expectedLargestLostNum, i % 2 ? sentPacketNum : expectedLargestLostNum);
1343 }
1344 EXPECT_CALL(*transportInfoCb_, onPTO());
1345 // Verify packet count doesn't change across PTO.
1346 auto originalPacketCount = conn->outstandings.packetCount;
1347 onLossDetectionAlarm<decltype(testingLossMarkFunc(lostPackets)), Clock>(
1348 *conn, testingLossMarkFunc(lostPackets));
1349 EXPECT_EQ(originalPacketCount, conn->outstandings.packetCount);
1350
1351 EXPECT_EQ(0, lostPackets.size());
1352 EXPECT_EQ(1, conn->lossState.ptoCount);
1353 EXPECT_EQ(0, conn->lossState.timeoutBasedRtxCount);
1354 EXPECT_EQ(
1355 conn->pendingEvents.numProbePackets[PacketNumberSpace::Handshake],
1356 kPacketToSendForPTO);
1357 EXPECT_EQ(
1358 conn->pendingEvents.numProbePackets[PacketNumberSpace::AppData],
1359 kPacketToSendForPTO);
1360 EXPECT_EQ(0, conn->lossState.rtxCount);
1361 }
1362
TEST_F(QuicLossFunctionsTest,EmptyOutstandingNoTimeout)1363 TEST_F(QuicLossFunctionsTest, EmptyOutstandingNoTimeout) {
1364 auto conn = createConn();
1365 EXPECT_CALL(timeout, cancelLossTimeout()).Times(1);
1366 setLossDetectionAlarm(*conn, timeout);
1367 }
1368
TEST_F(QuicLossFunctionsTest,AlarmDurationHasLossTime)1369 TEST_F(QuicLossFunctionsTest, AlarmDurationHasLossTime) {
1370 auto conn = createConn();
1371 TimePoint lastPacketSentTime = Clock::now();
1372 auto thisMoment = lastPacketSentTime;
1373 MockClock::mockNow = [=]() { return thisMoment; };
1374 conn->lossState.lossTimes[PacketNumberSpace::AppData] = thisMoment + 100ms;
1375 conn->lossState.srtt = 200ms;
1376 conn->lossState.lrtt = 150ms;
1377
1378 sendPacket(*conn, lastPacketSentTime, folly::none, PacketType::OneRtt);
1379 auto duration = calculateAlarmDuration<MockClock>(*conn);
1380 EXPECT_EQ(100ms, duration.first);
1381 EXPECT_EQ(
1382 duration.second, LossState::AlarmMethod::EarlyRetransmitOrReordering);
1383 }
1384
TEST_F(QuicLossFunctionsTest,AlarmDurationLossTimeIsZero)1385 TEST_F(QuicLossFunctionsTest, AlarmDurationLossTimeIsZero) {
1386 // The timer could be delayed a bit, so this tests that the alarm will return
1387 // a timer of 0 if we are in the loss time case.
1388 auto conn = createConn();
1389 TimePoint lastPacketSentTime = Clock::now();
1390 auto thisMoment = lastPacketSentTime + 200ms;
1391 MockClock::mockNow = [=]() { return thisMoment; };
1392 conn->lossState.lossTimes[PacketNumberSpace::AppData] =
1393 lastPacketSentTime + 100ms;
1394 conn->lossState.srtt = 200ms;
1395 conn->lossState.lrtt = 150ms;
1396
1397 sendPacket(*conn, lastPacketSentTime, folly::none, PacketType::OneRtt);
1398 auto duration = calculateAlarmDuration<MockClock>(*conn);
1399 EXPECT_EQ(0ms, duration.first);
1400 EXPECT_EQ(
1401 duration.second, LossState::AlarmMethod::EarlyRetransmitOrReordering);
1402 }
1403
TEST_F(QuicLossFunctionsTest,AlarmDurationNonHandshakeOutstanding)1404 TEST_F(QuicLossFunctionsTest, AlarmDurationNonHandshakeOutstanding) {
1405 auto conn = createConn();
1406 conn->lossState.srtt = 4ms;
1407 conn->lossState.rttvar = 10ms;
1408 conn->lossState.maxAckDelay = 25ms;
1409 TimePoint lastPacketSentTime = Clock::now();
1410 MockClock::mockNow = [=]() { return lastPacketSentTime; };
1411 sendPacket(*conn, lastPacketSentTime, folly::none, PacketType::OneRtt);
1412 auto duration = calculateAlarmDuration<MockClock>(*conn);
1413 EXPECT_EQ(duration.second, LossState::AlarmMethod::PTO);
1414 setLossDetectionAlarm<decltype(timeout), MockClock>(*conn, timeout);
1415 EXPECT_EQ(conn->lossState.currentAlarmMethod, LossState::AlarmMethod::PTO);
1416
1417 conn->lossState.ptoCount = 2;
1418 auto newDuration = calculateAlarmDuration<MockClock>(*conn);
1419 EXPECT_EQ(duration.second, LossState::AlarmMethod::PTO);
1420 EXPECT_LT(duration.first, newDuration.first);
1421 }
1422
TEST_F(QuicLossFunctionsTest,NoSkipLossVisitor)1423 TEST_F(QuicLossFunctionsTest, NoSkipLossVisitor) {
1424 auto conn = createConn();
1425 conn->congestionController.reset();
1426 // make srtt large so delayUntilLost won't kick in
1427 conn->lossState.srtt = 1000000000us;
1428 uint16_t lossVisitorCount = 0;
1429 auto countingLossVisitor =
1430 [&](auto& /* conn */, auto& /* packet */, bool processed) {
1431 if (!processed) {
1432 lossVisitorCount++;
1433 }
1434 };
1435 // Send 5 packets, so when we ack the last one, we mark the first one loss
1436 PacketNum lastSent;
1437 for (size_t i = 0; i < 5; i++) {
1438 lastSent = sendPacket(*conn, Clock::now(), folly::none, PacketType::OneRtt);
1439 }
1440 detectLossPackets(
1441 *conn,
1442 lastSent,
1443 countingLossVisitor,
1444 TimePoint(100ms),
1445 PacketNumberSpace::AppData);
1446 EXPECT_EQ(1, lossVisitorCount);
1447 }
1448
TEST_F(QuicLossFunctionsTest,SkipLossVisitor)1449 TEST_F(QuicLossFunctionsTest, SkipLossVisitor) {
1450 auto conn = createConn();
1451 conn->congestionController.reset();
1452 // make srtt large so delayUntilLost won't kick in
1453 conn->lossState.srtt = 1000000000us;
1454 uint16_t lossVisitorCount = 0;
1455 auto countingLossVisitor =
1456 [&](auto& /* conn */, auto& /* packet */, bool processed) {
1457 if (!processed) {
1458 lossVisitorCount++;
1459 }
1460 };
1461 // Send 5 packets, so when we ack the last one, we mark the first one loss
1462 PacketNum lastSent;
1463 for (size_t i = 0; i < 5; i++) {
1464 lastSent = conn->ackStates.appDataAckState.nextPacketNum;
1465 PacketEvent packetEvent(PacketNumberSpace::AppData, lastSent);
1466 sendPacket(*conn, Clock::now(), packetEvent, PacketType::OneRtt);
1467 }
1468 detectLossPackets(
1469 *conn,
1470 lastSent,
1471 countingLossVisitor,
1472 TimePoint(100ms),
1473 PacketNumberSpace::AppData);
1474 EXPECT_EQ(0, lossVisitorCount);
1475 }
1476
TEST_F(QuicLossFunctionsTest,NoDoubleProcess)1477 TEST_F(QuicLossFunctionsTest, NoDoubleProcess) {
1478 auto conn = createConn();
1479 conn->congestionController.reset();
1480 // make srtt large so delayUntilLost won't kick in
1481 conn->lossState.srtt = 1000000000us;
1482
1483 uint16_t lossVisitorCount = 0;
1484 auto countingLossVisitor =
1485 [&](auto& /* conn */, auto& /* packet */, bool processed) {
1486 if (!processed) {
1487 lossVisitorCount++;
1488 }
1489 };
1490 // Send 6 packets, so when we ack the last one, we mark the first two loss
1491 EXPECT_EQ(1, conn->ackStates.appDataAckState.nextPacketNum);
1492 PacketNum lastSent;
1493 lastSent = sendPacket(*conn, Clock::now(), folly::none, PacketType::OneRtt);
1494 EXPECT_EQ(1, conn->outstandings.packetCount[PacketNumberSpace::AppData]);
1495 PacketEvent event(PacketNumberSpace::AppData, lastSent);
1496 for (size_t i = 0; i < 6; i++) {
1497 lastSent = sendPacket(*conn, Clock::now(), event, PacketType::OneRtt);
1498 }
1499 EXPECT_EQ(7, conn->outstandings.packets.size());
1500 EXPECT_EQ(1, conn->outstandings.packetCount[PacketNumberSpace::AppData]);
1501 // Add the PacketEvent to the outstandings.packetEvents set
1502 conn->outstandings.packetEvents.insert(event);
1503
1504 // Ack the last sent packet. Despite three losses, lossVisitor only visit one
1505 // packet
1506 detectLossPackets(
1507 *conn,
1508 lastSent,
1509 countingLossVisitor,
1510 TimePoint(100ms),
1511 PacketNumberSpace::AppData);
1512 auto numDeclaredLost = std::count_if(
1513 conn->outstandings.packets.begin(),
1514 conn->outstandings.packets.end(),
1515 [](auto& op) { return op.declaredLost; });
1516 EXPECT_EQ(3, numDeclaredLost);
1517 EXPECT_EQ(1, lossVisitorCount);
1518 EXPECT_EQ(4 + numDeclaredLost, conn->outstandings.packets.size());
1519 }
1520
TEST_F(QuicLossFunctionsTest,DetectPacketLossClonedPacketsCounter)1521 TEST_F(QuicLossFunctionsTest, DetectPacketLossClonedPacketsCounter) {
1522 auto conn = createConn();
1523 PacketEvent packetEvent1(
1524 PacketNumberSpace::AppData,
1525 conn->ackStates.appDataAckState.nextPacketNum);
1526 sendPacket(*conn, Clock::now(), packetEvent1, PacketType::OneRtt);
1527 sendPacket(*conn, Clock::now(), folly::none, PacketType::OneRtt);
1528 sendPacket(*conn, Clock::now(), folly::none, PacketType::OneRtt);
1529 sendPacket(*conn, Clock::now(), folly::none, PacketType::OneRtt);
1530 auto ackedPacket =
1531 sendPacket(*conn, Clock::now(), folly::none, PacketType::OneRtt);
1532 auto noopLossMarker = [](auto&, auto&, bool) {};
1533 detectLossPackets<decltype(noopLossMarker)>(
1534 *conn,
1535 ackedPacket,
1536 noopLossMarker,
1537 Clock::now(),
1538 PacketNumberSpace::AppData);
1539 EXPECT_EQ(0, conn->outstandings.numClonedPackets());
1540 }
1541
TEST_F(QuicLossFunctionsTest,TestMarkPacketLossProcessedPacket)1542 TEST_F(QuicLossFunctionsTest, TestMarkPacketLossProcessedPacket) {
1543 MockAsyncUDPSocket socket(&evb);
1544 auto conn = createConn();
1545 ASSERT_TRUE(conn->outstandings.packets.empty());
1546 ASSERT_TRUE(conn->outstandings.packetEvents.empty());
1547 auto stream1Id =
1548 conn->streamManager->createNextBidirectionalStream().value()->id;
1549 auto buf = folly::IOBuf::copyBuffer("I wrestled by the sea.");
1550 auto stream2Id =
1551 conn->streamManager->createNextBidirectionalStream().value()->id;
1552 conn->streamManager->queueWindowUpdate(stream2Id);
1553 conn->pendingEvents.connWindowUpdate = true;
1554 // writeQuicPacket will call writeQuicDataToSocket which will also take care
1555 // of sending the MaxStreamDataFrame for stream2
1556 auto stream1 = conn->streamManager->findStream(stream1Id);
1557 auto stream2 = conn->streamManager->findStream(stream2Id);
1558 auto packet = writeQuicPacket(
1559 *conn,
1560 *conn->clientConnectionId,
1561 *conn->serverConnectionId,
1562 socket,
1563 *stream1,
1564 *buf,
1565 true);
1566 EXPECT_FALSE(conn->streamManager->pendingWindowUpdate(stream2->id));
1567 EXPECT_FALSE(conn->pendingEvents.connWindowUpdate);
1568 ASSERT_EQ(1, conn->outstandings.packets.size());
1569 ASSERT_TRUE(conn->outstandings.packetEvents.empty());
1570 uint32_t streamDataCounter = 0, streamWindowUpdateCounter = 0,
1571 connWindowUpdateCounter = 0;
1572 for (const auto& frame :
1573 getLastOutstandingPacket(*conn, PacketNumberSpace::AppData)
1574 ->packet.frames) {
1575 switch (frame.type()) {
1576 case QuicWriteFrame::Type::WriteStreamFrame:
1577 streamDataCounter++;
1578 break;
1579 case QuicWriteFrame::Type::MaxStreamDataFrame:
1580 streamWindowUpdateCounter++;
1581 break;
1582 case QuicWriteFrame::Type::MaxDataFrame:
1583 connWindowUpdateCounter++;
1584 break;
1585 default:
1586 CHECK(false) << "unexpected frame=" << (int)frame.type();
1587 }
1588 }
1589 EXPECT_EQ(1, streamDataCounter);
1590 EXPECT_EQ(1, streamWindowUpdateCounter);
1591 EXPECT_EQ(1, connWindowUpdateCounter);
1592 // Force this packet to be a processed clone
1593 markPacketLoss(*conn, packet, true);
1594 EXPECT_EQ(1, stream1->retransmissionBuffer.size());
1595 EXPECT_TRUE(stream1->lossBuffer.empty());
1596
1597 // Window update though, will still be marked loss
1598 EXPECT_TRUE(conn->streamManager->pendingWindowUpdate(stream2->id));
1599 EXPECT_TRUE(conn->pendingEvents.connWindowUpdate);
1600 }
1601
TEST_F(QuicLossFunctionsTest,TestTotalPTOCount)1602 TEST_F(QuicLossFunctionsTest, TestTotalPTOCount) {
1603 auto conn = createConn();
1604 auto mockQLogger = std::make_shared<MockQLogger>(VantagePoint::Server);
1605 conn->qLogger = mockQLogger;
1606 conn->lossState.totalPTOCount = 100;
1607 EXPECT_CALL(*mockQLogger, addLossAlarm(0, 1, 0, kPtoAlarm));
1608 EXPECT_CALL(*transportInfoCb_, onPTO());
1609 onPTOAlarm(*conn);
1610 EXPECT_EQ(101, conn->lossState.totalPTOCount);
1611 }
1612
TEST_F(QuicLossFunctionsTest,TestExceedsMaxPTOThrows)1613 TEST_F(QuicLossFunctionsTest, TestExceedsMaxPTOThrows) {
1614 auto conn = createConn();
1615 auto mockQLogger = std::make_shared<MockQLogger>(VantagePoint::Server);
1616 conn->qLogger = mockQLogger;
1617 conn->transportSettings.maxNumPTOs = 3;
1618 for (int i = 1; i <= 3; i++) {
1619 EXPECT_CALL(*mockQLogger, addLossAlarm(0, i, 0, kPtoAlarm));
1620 }
1621 EXPECT_CALL(*transportInfoCb_, onPTO()).Times(3);
1622 onPTOAlarm(*conn);
1623 onPTOAlarm(*conn);
1624 EXPECT_THROW(onPTOAlarm(*conn), QuicInternalException);
1625 }
1626
TEST_F(QuicLossFunctionsTest,TotalLossCount)1627 TEST_F(QuicLossFunctionsTest, TotalLossCount) {
1628 auto conn = createConn();
1629 conn->congestionController = nullptr;
1630 PacketNum largestSent = 0;
1631 for (int i = 0; i < 10; i++) {
1632 largestSent =
1633 sendPacket(*conn, Clock::now(), folly::none, PacketType::OneRtt);
1634 }
1635 EXPECT_EQ(10, conn->outstandings.packets.size());
1636 uint32_t lostPackets = 0;
1637 auto countingLossVisitor =
1638 [&](auto& /* conn */, auto& /* packet */, bool processed) {
1639 if (!processed) {
1640 lostPackets++;
1641 }
1642 };
1643
1644 conn->lossState.rtxCount = 135;
1645 detectLossPackets(
1646 *conn,
1647 largestSent,
1648 countingLossVisitor,
1649 TimePoint(100ms),
1650 PacketNumberSpace::AppData);
1651 EXPECT_EQ(135 + lostPackets, conn->lossState.rtxCount);
1652 }
1653
TEST_F(QuicLossFunctionsTest,TestZeroRttRejected)1654 TEST_F(QuicLossFunctionsTest, TestZeroRttRejected) {
1655 auto conn = createConn();
1656 auto mockCongestionController = std::make_unique<MockCongestionController>();
1657 auto rawCongestionController = mockCongestionController.get();
1658 conn->congestionController = std::move(mockCongestionController);
1659 EXPECT_CALL(*rawCongestionController, onPacketSent(_))
1660 .WillRepeatedly(Return());
1661 // By adding an associatedEvent that doesn't exist in the
1662 // outstandings.packetEvents, they are all processed and will skip lossVisitor
1663 for (auto i = 0; i < 2; i++) {
1664 sendPacket(*conn, TimePoint(), folly::none, PacketType::OneRtt);
1665 sendPacket(*conn, TimePoint(), folly::none, PacketType::ZeroRtt);
1666 }
1667 EXPECT_FALSE(conn->outstandings.packets.empty());
1668 EXPECT_EQ(4, conn->outstandings.packets.size());
1669 std::vector<bool> lostPackets;
1670 // onRemoveBytesFromInflight should still happen
1671 EXPECT_CALL(*rawCongestionController, onRemoveBytesFromInflight(_)).Times(1);
1672 markZeroRttPacketsLost(*conn, [&lostPackets](auto&, auto&, bool processed) {
1673 lostPackets.emplace_back(processed);
1674 });
1675 EXPECT_EQ(2, conn->outstandings.packets.size());
1676 EXPECT_EQ(lostPackets.size(), 2);
1677 for (auto lostPacket : lostPackets) {
1678 EXPECT_FALSE(lostPacket);
1679 }
1680 for (size_t i = 0; i < conn->outstandings.packets.size(); ++i) {
1681 auto longHeader = conn->outstandings.packets[i].packet.header.asLong();
1682 EXPECT_FALSE(
1683 longHeader &&
1684 longHeader->getProtectionType() == ProtectionType::ZeroRtt);
1685 }
1686 EXPECT_EQ(2, conn->lossState.rtxCount);
1687 }
1688
TEST_F(QuicLossFunctionsTest,TestZeroRttRejectedWithClones)1689 TEST_F(QuicLossFunctionsTest, TestZeroRttRejectedWithClones) {
1690 auto conn = createConn();
1691 auto mockCongestionController = std::make_unique<MockCongestionController>();
1692 auto rawCongestionController = mockCongestionController.get();
1693 conn->congestionController = std::move(mockCongestionController);
1694 EXPECT_CALL(*rawCongestionController, onPacketSent(_))
1695 .WillRepeatedly(Return());
1696 // By adding an associatedEvent that doesn't exist in the
1697 // outstandings.packetEvents, they are all processed and will skip lossVisitor
1698 std::set<PacketNum> zeroRttPackets;
1699 folly::Optional<PacketEvent> lastPacketEvent;
1700 for (auto i = 0; i < 2; i++) {
1701 auto packetNum =
1702 sendPacket(*conn, TimePoint(), lastPacketEvent, PacketType::ZeroRtt);
1703 lastPacketEvent = PacketEvent(PacketNumberSpace::AppData, packetNum);
1704 zeroRttPackets.emplace(packetNum);
1705 }
1706 zeroRttPackets.emplace(
1707 sendPacket(*conn, TimePoint(), folly::none, PacketType::ZeroRtt));
1708 for (auto zeroRttPacketNum : zeroRttPackets) {
1709 PacketEvent zeroRttPacketEvent(
1710 PacketNumberSpace::AppData, zeroRttPacketNum);
1711 sendPacket(*conn, TimePoint(), zeroRttPacketEvent, PacketType::OneRtt);
1712 }
1713
1714 EXPECT_EQ(6, conn->outstandings.packets.size());
1715 ASSERT_EQ(conn->outstandings.numClonedPackets(), 6);
1716 ASSERT_EQ(conn->outstandings.packetEvents.size(), 2);
1717 ASSERT_EQ(2, conn->outstandings.packetCount[PacketNumberSpace::AppData]);
1718
1719 std::vector<bool> lostPackets;
1720 // onRemoveBytesFromInflight should still happen
1721 EXPECT_CALL(*rawCongestionController, onRemoveBytesFromInflight(_)).Times(1);
1722 markZeroRttPacketsLost(*conn, [&lostPackets](auto&, auto&, bool processed) {
1723 lostPackets.emplace_back(processed);
1724 });
1725 ASSERT_EQ(conn->outstandings.packetEvents.size(), 0);
1726 EXPECT_EQ(3, conn->outstandings.packets.size());
1727 EXPECT_EQ(lostPackets.size(), 3);
1728 ASSERT_EQ(conn->outstandings.numClonedPackets(), 3);
1729 size_t numProcessed = 0;
1730 for (auto lostPacket : lostPackets) {
1731 numProcessed += lostPacket;
1732 }
1733 EXPECT_EQ(numProcessed, 1);
1734 for (size_t i = 0; i < conn->outstandings.packets.size(); ++i) {
1735 auto longHeader = conn->outstandings.packets[i].packet.header.asLong();
1736 EXPECT_FALSE(
1737 longHeader &&
1738 longHeader->getProtectionType() == ProtectionType::ZeroRtt);
1739 }
1740 }
1741
TEST_F(QuicLossFunctionsTest,PTOLargerThanMaxDelay)1742 TEST_F(QuicLossFunctionsTest, PTOLargerThanMaxDelay) {
1743 QuicConnectionStateBase conn(QuicNodeType::Client);
1744 conn.lossState.srtt = 1ms;
1745 conn.lossState.maxAckDelay = 20s;
1746 EXPECT_GE(calculatePTO(conn), 20s);
1747 }
1748
TEST_F(QuicLossFunctionsTest,InitialPTOs)1749 TEST_F(QuicLossFunctionsTest, InitialPTOs) {
1750 QuicConnectionStateBase conn(QuicNodeType::Client);
1751 conn.transportSettings.initialRtt = 20ms;
1752 EXPECT_EQ(40ms, calculatePTO(conn));
1753 }
1754
TEST_F(QuicLossFunctionsTest,TimeThreshold)1755 TEST_F(QuicLossFunctionsTest, TimeThreshold) {
1756 auto conn = createConn();
1757 conn->lossState.srtt = 10ms;
1758 auto referenceTime = Clock::now();
1759 auto packet1 =
1760 sendPacket(*conn, referenceTime - 10ms, folly::none, PacketType::OneRtt);
1761 auto packet2 = sendPacket(
1762 *conn,
1763 referenceTime + conn->lossState.srtt / 2,
1764 folly::none,
1765 PacketType::OneRtt);
1766 auto lossVisitor = [&](const auto& /*conn*/, const auto& packet, bool) {
1767 EXPECT_EQ(packet1, packet.header.getPacketSequenceNum());
1768 };
1769 detectLossPackets<decltype(lossVisitor)>(
1770 *conn,
1771 packet2,
1772 lossVisitor,
1773 referenceTime + conn->lossState.srtt * 9 / 8 + 5ms,
1774 PacketNumberSpace::AppData);
1775 }
1776
TEST_F(QuicLossFunctionsTest,OutstandingInitialCounting)1777 TEST_F(QuicLossFunctionsTest, OutstandingInitialCounting) {
1778 auto conn = createConn();
1779 // Simplify the test by never triggering timer threshold
1780 conn->lossState.srtt = 100s;
1781 PacketNum largestSent = 0;
1782 while (largestSent < 10) {
1783 largestSent =
1784 sendPacket(*conn, Clock::now(), folly::none, PacketType::Initial);
1785 }
1786 EXPECT_EQ(10, conn->outstandings.packetCount[PacketNumberSpace::Initial]);
1787 auto noopLossVisitor =
1788 [&](auto& /* conn */, auto& /* packet */, bool /* processed */
1789 ) {};
1790 detectLossPackets(
1791 *conn,
1792 largestSent,
1793 noopLossVisitor,
1794 TimePoint(100ms),
1795 PacketNumberSpace::Initial);
1796 // [1, 6] are removed, [7, 10] are still in OP list
1797 EXPECT_EQ(4, conn->outstandings.packetCount[PacketNumberSpace::Initial]);
1798 }
1799
TEST_F(QuicLossFunctionsTest,OutstandingHandshakeCounting)1800 TEST_F(QuicLossFunctionsTest, OutstandingHandshakeCounting) {
1801 auto conn = createConn();
1802 // Simplify the test by never triggering timer threshold
1803 conn->lossState.srtt = 100s;
1804 PacketNum largestSent = 0;
1805 while (largestSent < 10) {
1806 largestSent =
1807 sendPacket(*conn, Clock::now(), folly::none, PacketType::Handshake);
1808 }
1809 EXPECT_EQ(10, conn->outstandings.packetCount[PacketNumberSpace::Handshake]);
1810 auto noopLossVisitor =
1811 [&](auto& /* conn */, auto& /* packet */, bool /* processed */
1812 ) {};
1813 detectLossPackets(
1814 *conn,
1815 largestSent,
1816 noopLossVisitor,
1817 TimePoint(100ms),
1818 PacketNumberSpace::Handshake);
1819 // [1, 6] are removed, [7, 10] are still in OP list
1820 EXPECT_EQ(4, conn->outstandings.packetCount[PacketNumberSpace::Handshake]);
1821 }
1822
TEST_P(QuicLossFunctionsTest,CappedShiftNoCrash)1823 TEST_P(QuicLossFunctionsTest, CappedShiftNoCrash) {
1824 auto conn = createConn();
1825 conn->outstandings.packetCount[PacketNumberSpace::Handshake] = 0;
1826 conn->outstandings.packets.clear();
1827 conn->lossState.ptoCount =
1828 std::numeric_limits<decltype(conn->lossState.ptoCount)>::max();
1829 sendPacket(*conn, Clock::now(), folly::none, PacketType::OneRtt);
1830 calculateAlarmDuration(*conn);
1831 }
1832
TEST_F(QuicLossFunctionsTest,PersistentCongestion)1833 TEST_F(QuicLossFunctionsTest, PersistentCongestion) {
1834 // Test cases copied over from PersistentCongestion above.
1835 auto conn = createConn();
1836 auto currentTime = Clock::now();
1837 conn->lossState.srtt = 1s;
1838
1839 CongestionController::AckEvent ack;
1840
1841 EXPECT_TRUE(isPersistentCongestion(
1842 calculatePTO(*conn), currentTime - 10s, currentTime, ack));
1843 EXPECT_TRUE(isPersistentCongestion(
1844 calculatePTO(*conn), currentTime - 3s, currentTime, ack));
1845 EXPECT_TRUE(isPersistentCongestion(
1846 calculatePTO(*conn),
1847 currentTime - (1s * kPersistentCongestionThreshold),
1848 currentTime,
1849 ack));
1850 EXPECT_FALSE(isPersistentCongestion(
1851 calculatePTO(*conn),
1852 currentTime - (1s * kPersistentCongestionThreshold) + 1us,
1853 currentTime,
1854 ack));
1855 EXPECT_FALSE(isPersistentCongestion(
1856 calculatePTO(*conn), currentTime - 2s, currentTime, ack));
1857 EXPECT_FALSE(isPersistentCongestion(
1858 calculatePTO(*conn), currentTime - 100ms, currentTime, ack));
1859
1860 conn->lossState.rttvar = 2s;
1861 conn->lossState.maxAckDelay = 5s;
1862 EXPECT_TRUE(isPersistentCongestion(
1863 calculatePTO(*conn), currentTime - 42s, currentTime, ack));
1864 EXPECT_TRUE(isPersistentCongestion(
1865 calculatePTO(*conn), currentTime - 43s, currentTime, ack));
1866 EXPECT_FALSE(isPersistentCongestion(
1867 calculatePTO(*conn), currentTime - 42s + 1ms, currentTime, ack));
1868 EXPECT_FALSE(isPersistentCongestion(
1869 calculatePTO(*conn), currentTime - 100us, currentTime, ack));
1870 }
1871
TEST_F(QuicLossFunctionsTest,PersistentCongestionAckOutsideWindow)1872 TEST_F(QuicLossFunctionsTest, PersistentCongestionAckOutsideWindow) {
1873 auto conn = createConn();
1874 auto currentTime = Clock::now();
1875 conn->lossState.srtt = 1s;
1876
1877 CongestionController::AckEvent ack;
1878
1879 ack.ackedPackets.push_back(
1880 CongestionController::AckEvent::AckPacket::Builder()
1881 .setSentTime(currentTime + 12s)
1882 .build());
1883
1884 EXPECT_TRUE(isPersistentCongestion(
1885 calculatePTO(*conn), currentTime + 1s, currentTime + 8s, ack));
1886 }
1887
TEST_F(QuicLossFunctionsTest,PersistentCongestionAckInsideWindow)1888 TEST_F(QuicLossFunctionsTest, PersistentCongestionAckInsideWindow) {
1889 auto conn = createConn();
1890 auto currentTime = Clock::now();
1891 conn->lossState.srtt = 1s;
1892
1893 CongestionController::AckEvent ack;
1894
1895 ack.ackedPackets.push_back(
1896 CongestionController::AckEvent::AckPacket::Builder()
1897 .setSentTime(currentTime + 4s)
1898 .build());
1899
1900 EXPECT_FALSE(isPersistentCongestion(
1901 calculatePTO(*conn), currentTime + 1s, currentTime + 8s, ack));
1902 }
1903
TEST_F(QuicLossFunctionsTest,PersistentCongestionNoPTO)1904 TEST_F(QuicLossFunctionsTest, PersistentCongestionNoPTO) {
1905 auto conn = createConn();
1906 auto currentTime = Clock::now();
1907
1908 CongestionController::AckEvent ack;
1909
1910 ack.ackedPackets.push_back(
1911 CongestionController::AckEvent::AckPacket::Builder()
1912 .setSentTime(currentTime + 12s)
1913 .build());
1914
1915 EXPECT_FALSE(isPersistentCongestion(
1916 folly::none, currentTime + 1s, currentTime + 8s, ack));
1917 }
1918
TEST_F(QuicLossFunctionsTest,TestReorderLossObserverCallback)1919 TEST_F(QuicLossFunctionsTest, TestReorderLossObserverCallback) {
1920 auto observers = std::make_shared<ObserverVec>();
1921 Observer::Config config = {};
1922 config.lossEvents = true;
1923 auto ib = MockObserver(config);
1924 auto conn = createConn();
1925 // Register 1 observer
1926 observers->emplace_back(&ib);
1927 conn->observers = observers;
1928 auto noopLossVisitor = [](auto&, auto&, bool) {};
1929
1930 PacketNum largestSent = 0;
1931 for (int i = 0; i < 7; ++i) {
1932 largestSent =
1933 sendPacket(*conn, TimePoint(i * 10ms), folly::none, PacketType::OneRtt);
1934 }
1935 // Some packets are already acked
1936 conn->outstandings.packets.erase(
1937 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData) + 2,
1938 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData) + 5);
1939
1940 // setting a very low reordering threshold to force loss by reorder
1941 conn->lossState.reorderingThreshold = 1;
1942 // setting time out parameters higher than the time at which detectLossPackets
1943 // is called to make sure there are no losses by timeout
1944 conn->lossState.srtt = 400ms;
1945 conn->lossState.lrtt = 350ms;
1946 conn->transportSettings.timeReorderingThreshDividend = 1.0;
1947 conn->transportSettings.timeReorderingThreshDivisor = 1.0;
1948 TimePoint checkTime = TimePoint(200ms);
1949
1950 detectLossPackets(
1951 *conn,
1952 largestSent + 1,
1953 noopLossVisitor,
1954 checkTime,
1955 PacketNumberSpace::AppData);
1956
1957 // expecting 1 callback to be stacked
1958 EXPECT_EQ(1, size(conn->pendingCallbacks));
1959
1960 // Out of 1, 2, 3, 4, 5, 6, 7 -- we deleted (acked) 3,4,5.
1961 // 1, 2 and 6 are "lost" due to reodering. None lost due to timeout
1962 EXPECT_THAT(
1963 conn->outstandings.packets,
1964 UnorderedElementsAre(
1965 getOutstandingPacketMatcher(1, true, false),
1966 getOutstandingPacketMatcher(2, true, false),
1967 getOutstandingPacketMatcher(6, true, false),
1968 getOutstandingPacketMatcher(7, false, false)));
1969 EXPECT_CALL(
1970 ib,
1971 packetLossDetected(
1972 nullptr,
1973 Field(
1974 &Observer::LossEvent::lostPackets,
1975 UnorderedElementsAre(
1976 getLossPacketMatcher(1, true, false),
1977 getLossPacketMatcher(2, true, false),
1978 getLossPacketMatcher(6, true, false)))))
1979 .Times(1);
1980
1981 for (auto& callback : conn->pendingCallbacks) {
1982 callback(nullptr);
1983 }
1984 }
1985
TEST_F(QuicLossFunctionsTest,TestTimeoutLossObserverCallback)1986 TEST_F(QuicLossFunctionsTest, TestTimeoutLossObserverCallback) {
1987 auto observers = std::make_shared<ObserverVec>();
1988 Observer::Config config = {};
1989 config.lossEvents = true;
1990 auto ib = MockObserver(config);
1991 auto conn = createConn();
1992 // Register 1 observer
1993 observers->emplace_back(&ib);
1994 conn->observers = observers;
1995 auto noopLossVisitor = [](auto&, auto&, bool) {};
1996
1997 PacketNum largestSent = 0;
1998
1999 // send 7 packets
2000 for (int i = 0; i < 7; ++i) {
2001 largestSent =
2002 sendPacket(*conn, TimePoint(i * 10ms), folly::none, PacketType::OneRtt);
2003 }
2004
2005 // setting a very high reordering threshold to force loss by timeout only
2006 conn->lossState.reorderingThreshold = 100;
2007 // setting time out parameters lower than the time at which detectLossPackets
2008 // is called to make sure all packets timeout
2009 conn->lossState.srtt = 400ms;
2010 conn->lossState.lrtt = 350ms;
2011 conn->transportSettings.timeReorderingThreshDividend = 1.0;
2012 conn->transportSettings.timeReorderingThreshDivisor = 1.0;
2013 TimePoint checkTime = TimePoint(500ms);
2014
2015 detectLossPackets(
2016 *conn,
2017 largestSent + 1,
2018 noopLossVisitor,
2019 checkTime,
2020 PacketNumberSpace::AppData);
2021
2022 // expecting 1 callback to be stacked
2023 EXPECT_EQ(1, size(conn->pendingCallbacks));
2024
2025 // expecting all packets to be lost due to timeout
2026 EXPECT_THAT(
2027 conn->outstandings.packets,
2028 UnorderedElementsAre(
2029 getOutstandingPacketMatcher(1, false, true),
2030 getOutstandingPacketMatcher(2, false, true),
2031 getOutstandingPacketMatcher(3, false, true),
2032 getOutstandingPacketMatcher(4, false, true),
2033 getOutstandingPacketMatcher(5, false, true),
2034 getOutstandingPacketMatcher(6, false, true),
2035 getOutstandingPacketMatcher(7, false, true)));
2036
2037 EXPECT_CALL(
2038 ib,
2039 packetLossDetected(
2040 nullptr,
2041 Field(
2042 &Observer::LossEvent::lostPackets,
2043 UnorderedElementsAre(
2044 getLossPacketMatcher(1, false, true),
2045 getLossPacketMatcher(2, false, true),
2046 getLossPacketMatcher(3, false, true),
2047 getLossPacketMatcher(4, false, true),
2048 getLossPacketMatcher(5, false, true),
2049 getLossPacketMatcher(6, false, true),
2050 getLossPacketMatcher(7, false, true)))))
2051 .Times(1);
2052
2053 for (auto& callback : conn->pendingCallbacks) {
2054 callback(nullptr);
2055 }
2056 }
2057
TEST_F(QuicLossFunctionsTest,TestTimeoutAndReorderLossObserverCallback)2058 TEST_F(QuicLossFunctionsTest, TestTimeoutAndReorderLossObserverCallback) {
2059 auto observers = std::make_shared<ObserverVec>();
2060 Observer::Config config = {};
2061 config.lossEvents = true;
2062 auto ib = MockObserver(config);
2063 auto conn = createConn();
2064 // Register 1 observer
2065 observers->emplace_back(&ib);
2066 conn->observers = observers;
2067 auto noopLossVisitor = [](auto&, auto&, bool) {};
2068
2069 PacketNum largestSent = 0;
2070 for (int i = 0; i < 7; ++i) {
2071 largestSent =
2072 sendPacket(*conn, TimePoint(i * 10ms), folly::none, PacketType::OneRtt);
2073 }
2074
2075 // Some packets are already acked
2076 conn->outstandings.packets.erase(
2077 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData) + 2,
2078 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData) + 5);
2079
2080 // setting a low reorder threshold
2081 conn->lossState.reorderingThreshold = 1;
2082
2083 // setting time out parameters lower than the time at which detectLossPackets
2084 // is called to make sure all packets timeout
2085 conn->lossState.srtt = 400ms;
2086 conn->lossState.lrtt = 350ms;
2087 conn->transportSettings.timeReorderingThreshDividend = 1.0;
2088 conn->transportSettings.timeReorderingThreshDivisor = 1.0;
2089 TimePoint checkTime = TimePoint(500ms);
2090
2091 detectLossPackets(
2092 *conn,
2093 largestSent + 1,
2094 noopLossVisitor,
2095 checkTime,
2096 PacketNumberSpace::AppData);
2097
2098 // expecting 1 callback to be stacked
2099 EXPECT_EQ(1, size(conn->pendingCallbacks));
2100
2101 // Out of 1, 2, 3, 4, 5, 6, 7 -- we deleted (acked) 3,4,5.
2102 // 1, 2, 6 are lost due to reodering and timeout.
2103 // 7 just timed out
2104 EXPECT_THAT(
2105 conn->outstandings.packets,
2106 UnorderedElementsAre(
2107 getOutstandingPacketMatcher(1, true, true),
2108 getOutstandingPacketMatcher(2, true, true),
2109 getOutstandingPacketMatcher(6, true, true),
2110 getOutstandingPacketMatcher(7, false, true)));
2111 EXPECT_CALL(
2112 ib,
2113 packetLossDetected(
2114 nullptr,
2115 Field(
2116 &Observer::LossEvent::lostPackets,
2117 UnorderedElementsAre(
2118 getLossPacketMatcher(1, true, true),
2119 getLossPacketMatcher(2, true, true),
2120 getLossPacketMatcher(6, true, true),
2121 getLossPacketMatcher(7, false, true)))))
2122 .Times(1);
2123
2124 for (auto& callback : conn->pendingCallbacks) {
2125 callback(nullptr);
2126 }
2127 }
2128
TEST_F(QuicLossFunctionsTest,TestNoObserverCallback)2129 TEST_F(QuicLossFunctionsTest, TestNoObserverCallback) {
2130 auto conn = createConn();
2131 auto noopLossVisitor = [](auto&, auto&, bool) {};
2132
2133 PacketNum largestSent = 0;
2134 for (int i = 0; i < 7; ++i) {
2135 largestSent =
2136 sendPacket(*conn, TimePoint(i * 10ms), folly::none, PacketType::OneRtt);
2137 }
2138
2139 // Some packets are already acked
2140 conn->outstandings.packets.erase(
2141 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData) + 2,
2142 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData) + 5);
2143
2144 // setting a low reorder threshold
2145 conn->lossState.reorderingThreshold = 1;
2146
2147 // setting time out parameters lower than the time at which detectLossPackets
2148 // is called to make sure all packets timeout
2149 conn->lossState.srtt = 400ms;
2150 conn->lossState.lrtt = 350ms;
2151 conn->transportSettings.timeReorderingThreshDividend = 1.0;
2152 conn->transportSettings.timeReorderingThreshDivisor = 1.0;
2153 TimePoint checkTime = TimePoint(500ms);
2154
2155 detectLossPackets(
2156 *conn,
2157 largestSent + 1,
2158 noopLossVisitor,
2159 checkTime,
2160 PacketNumberSpace::AppData);
2161
2162 // expecting 0 callbacks to be queued
2163 EXPECT_EQ(0, size(conn->pendingCallbacks));
2164 }
2165
TEST_F(QuicLossFunctionsTest,TotalPacketsMarkedLostByReordering)2166 TEST_F(QuicLossFunctionsTest, TotalPacketsMarkedLostByReordering) {
2167 auto conn = createConn();
2168 auto noopLossVisitor = [](auto&, auto&, bool) {};
2169
2170 // send 7 packets
2171 PacketNum largestSent = 0;
2172 for (int i = 0; i < 7; ++i) {
2173 largestSent =
2174 sendPacket(*conn, TimePoint(i * 10ms), folly::none, PacketType::OneRtt);
2175 }
2176
2177 // Some packets are already acked
2178 conn->outstandings.packets.erase(
2179 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData) + 2,
2180 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData) + 5);
2181
2182 // setting a very low reordering threshold to force loss by reorder
2183 conn->lossState.reorderingThreshold = 1;
2184 // setting time out parameters higher than the time at which detectLossPackets
2185 // is called to make sure there are no losses by timeout
2186 conn->lossState.srtt = 400ms;
2187 conn->lossState.lrtt = 350ms;
2188 conn->transportSettings.timeReorderingThreshDividend = 1.0;
2189 conn->transportSettings.timeReorderingThreshDivisor = 1.0;
2190 TimePoint checkTime = TimePoint(200ms);
2191
2192 detectLossPackets(
2193 *conn,
2194 largestSent + 1,
2195 noopLossVisitor,
2196 checkTime,
2197 PacketNumberSpace::AppData);
2198
2199 // Sent 7 packets, out of 0, 1, 2, 3, 4, 5, 6 -- we deleted (acked) 2,3,4
2200 // 0, 1, and 5 should be marked lost due to reordering, none due to timeout
2201 // 6 is outstanding / on the wire still (no determination made)
2202 EXPECT_EQ(3, conn->lossState.totalPacketsMarkedLost);
2203 EXPECT_EQ(0, conn->lossState.totalPacketsMarkedLostByPto);
2204 EXPECT_EQ(3, conn->lossState.totalPacketsMarkedLostByReorderingThreshold);
2205 }
2206
TEST_F(QuicLossFunctionsTest,TotalPacketsMarkedLostByPto)2207 TEST_F(QuicLossFunctionsTest, TotalPacketsMarkedLostByPto) {
2208 auto conn = createConn();
2209 auto noopLossVisitor = [](auto&, auto&, bool) {};
2210
2211 // send 7 packets
2212 PacketNum largestSent = 0;
2213 for (int i = 0; i < 7; ++i) {
2214 largestSent =
2215 sendPacket(*conn, TimePoint(i * 10ms), folly::none, PacketType::OneRtt);
2216 }
2217
2218 // setting a very high reordering threshold to force loss by timeout only
2219 conn->lossState.reorderingThreshold = 100;
2220 // setting time out parameters lower than the time at which detectLossPackets
2221 // is called to make sure all packets timeout
2222 conn->lossState.srtt = 400ms;
2223 conn->lossState.lrtt = 350ms;
2224 conn->transportSettings.timeReorderingThreshDividend = 1.0;
2225 conn->transportSettings.timeReorderingThreshDivisor = 1.0;
2226 TimePoint checkTime = TimePoint(500ms);
2227
2228 detectLossPackets(
2229 *conn,
2230 largestSent + 1,
2231 noopLossVisitor,
2232 checkTime,
2233 PacketNumberSpace::AppData);
2234
2235 // All 7 packets should be marked as lost by PTO
2236 EXPECT_EQ(7, conn->lossState.totalPacketsMarkedLost);
2237 EXPECT_EQ(7, conn->lossState.totalPacketsMarkedLostByPto);
2238 EXPECT_EQ(0, conn->lossState.totalPacketsMarkedLostByReorderingThreshold);
2239 }
2240
TEST_F(QuicLossFunctionsTest,TotalPacketsMarkedLostByPtoPartial)2241 TEST_F(QuicLossFunctionsTest, TotalPacketsMarkedLostByPtoPartial) {
2242 auto conn = createConn();
2243 auto noopLossVisitor = [](auto&, auto&, bool) {};
2244
2245 // send 7 packets
2246 PacketNum largestSent = 0;
2247 for (int i = 0; i < 7; ++i) {
2248 largestSent =
2249 sendPacket(*conn, TimePoint(i * 10ms), folly::none, PacketType::OneRtt);
2250 }
2251
2252 // Some packets are already acked
2253 conn->outstandings.packets.erase(
2254 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData) + 2,
2255 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData) + 5);
2256
2257 // setting a very high reordering threshold to force loss by timeout only
2258 conn->lossState.reorderingThreshold = 100;
2259 // setting time out parameters lower than the time at which detectLossPackets
2260 // is called to make sure all packets timeout
2261 conn->lossState.srtt = 400ms;
2262 conn->lossState.lrtt = 350ms;
2263 conn->transportSettings.timeReorderingThreshDividend = 1.0;
2264 conn->transportSettings.timeReorderingThreshDivisor = 1.0;
2265 TimePoint checkTime = TimePoint(500ms);
2266
2267 detectLossPackets(
2268 *conn,
2269 largestSent + 1,
2270 noopLossVisitor,
2271 checkTime,
2272 PacketNumberSpace::AppData);
2273
2274 // Sent 7 packets, out of 0, 1, 2, 3, 4, 5, 6 -- we deleted (acked) 2,3,4
2275 // 0, 1, 5, and 6 should be marked lost due to timeout, none due to reordering
2276 EXPECT_EQ(4, conn->lossState.totalPacketsMarkedLost);
2277 EXPECT_EQ(4, conn->lossState.totalPacketsMarkedLostByPto);
2278 EXPECT_EQ(0, conn->lossState.totalPacketsMarkedLostByReorderingThreshold);
2279 }
2280
TEST_F(QuicLossFunctionsTest,TotalPacketsMarkedLostByPtoAndReordering)2281 TEST_F(QuicLossFunctionsTest, TotalPacketsMarkedLostByPtoAndReordering) {
2282 auto conn = createConn();
2283 auto noopLossVisitor = [](auto&, auto&, bool) {};
2284
2285 // send 7 packets
2286 PacketNum largestSent = 0;
2287 for (int i = 0; i < 7; ++i) {
2288 largestSent =
2289 sendPacket(*conn, TimePoint(i * 10ms), folly::none, PacketType::OneRtt);
2290 }
2291
2292 // Some packets are already acked
2293 conn->outstandings.packets.erase(
2294 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData) + 2,
2295 getFirstOutstandingPacket(*conn, PacketNumberSpace::AppData) + 5);
2296
2297 // setting a low reorder threshold
2298 conn->lossState.reorderingThreshold = 1;
2299
2300 // setting time out parameters lower than the time at which detectLossPackets
2301 // is called to make sure all packets timeout
2302 conn->lossState.srtt = 400ms;
2303 conn->lossState.lrtt = 350ms;
2304 conn->transportSettings.timeReorderingThreshDividend = 1.0;
2305 conn->transportSettings.timeReorderingThreshDivisor = 1.0;
2306 TimePoint checkTime = TimePoint(500ms);
2307
2308 detectLossPackets(
2309 *conn,
2310 largestSent + 1,
2311 noopLossVisitor,
2312 checkTime,
2313 PacketNumberSpace::AppData);
2314
2315 // Sent 7 packets, out of 0, 1, 2, 3, 4, 5, 6 -- we deleted (acked) 2,3,4
2316 // 0, 1, and 5 should be marked lost due to reordering AND timeout
2317 // 6 should be marked as lost due to timeout only
2318 EXPECT_EQ(4, conn->lossState.totalPacketsMarkedLost);
2319 EXPECT_EQ(4, conn->lossState.totalPacketsMarkedLostByPto);
2320 EXPECT_EQ(3, conn->lossState.totalPacketsMarkedLostByReorderingThreshold);
2321 }
2322
TEST_F(QuicLossFunctionsTest,LossVisitorDSRTest)2323 TEST_F(QuicLossFunctionsTest, LossVisitorDSRTest) {
2324 auto conn = createConn();
2325 auto* stream = conn->streamManager->createNextBidirectionalStream().value();
2326 stream->dsrSender = std::make_unique<MockDSRPacketizationRequestSender>();
2327 writeDataToQuicStream(*stream, folly::IOBuf::copyBuffer("grape"), false);
2328 writeBufMetaToQuicStream(*stream, BufferMeta(1000), true);
2329 auto bufMetaStartingOffset = stream->writeBufMeta.offset;
2330 ASSERT_EQ(1000, stream->writeBufMeta.length);
2331 ASSERT_TRUE(stream->writeBufMeta.eof);
2332 ASSERT_EQ(bufMetaStartingOffset + 1000, *stream->finalWriteOffset);
2333 // Send real data
2334 handleStreamWritten(
2335 *conn,
2336 *stream,
2337 0,
2338 bufMetaStartingOffset,
2339 false,
2340 0 /* PacketNum */,
2341 PacketNumberSpace::AppData);
2342 ASSERT_EQ(0, stream->writeBuffer.chainLength());
2343 auto retxIter = stream->retransmissionBuffer.find(0);
2344 ASSERT_NE(stream->retransmissionBuffer.end(), retxIter);
2345 ASSERT_EQ(0, retxIter->second->offset);
2346 ASSERT_FALSE(retxIter->second->eof);
2347 ASSERT_TRUE(folly::IOBufEqualTo()(
2348 *folly::IOBuf::copyBuffer("grape"), *retxIter->second->data.front()));
2349 ASSERT_EQ(stream->currentWriteOffset, bufMetaStartingOffset);
2350
2351 // Send BufMeta in 3 chunks:
2352 handleStreamBufMetaWritten(
2353 *conn,
2354 *stream,
2355 bufMetaStartingOffset,
2356 200,
2357 false,
2358 1 /* PacketNum */,
2359 PacketNumberSpace::AppData);
2360 ASSERT_EQ(800, stream->writeBufMeta.length);
2361 ASSERT_TRUE(stream->writeBufMeta.eof);
2362 ASSERT_EQ(bufMetaStartingOffset + 200, stream->writeBufMeta.offset);
2363 auto retxBufMetaIter =
2364 stream->retransmissionBufMetas.find(bufMetaStartingOffset);
2365 ASSERT_NE(stream->retransmissionBufMetas.end(), retxBufMetaIter);
2366 ASSERT_EQ(bufMetaStartingOffset, retxBufMetaIter->second.offset);
2367 ASSERT_EQ(200, retxBufMetaIter->second.length);
2368 ASSERT_FALSE(retxBufMetaIter->second.eof);
2369 conn->streamManager->updateWritableStreams(*stream);
2370 conn->streamManager->updateLossStreams(*stream);
2371 EXPECT_FALSE(conn->streamManager->hasLoss());
2372 EXPECT_FALSE(conn->streamManager->writableDSRStreams().empty());
2373
2374 handleStreamBufMetaWritten(
2375 *conn,
2376 *stream,
2377 bufMetaStartingOffset + 200,
2378 400,
2379 false,
2380 2 /* PacketNum */,
2381 PacketNumberSpace::AppData);
2382 ASSERT_EQ(400, stream->writeBufMeta.length);
2383 ASSERT_TRUE(stream->writeBufMeta.eof);
2384 ASSERT_EQ(bufMetaStartingOffset + 600, stream->writeBufMeta.offset);
2385 retxBufMetaIter =
2386 stream->retransmissionBufMetas.find(bufMetaStartingOffset + 200);
2387 ASSERT_NE(stream->retransmissionBufMetas.end(), retxBufMetaIter);
2388 ASSERT_EQ(bufMetaStartingOffset + 200, retxBufMetaIter->second.offset);
2389 ASSERT_EQ(400, retxBufMetaIter->second.length);
2390 ASSERT_FALSE(retxBufMetaIter->second.eof);
2391 conn->streamManager->updateWritableStreams(*stream);
2392 conn->streamManager->updateLossStreams(*stream);
2393 EXPECT_FALSE(conn->streamManager->hasLoss());
2394 EXPECT_FALSE(conn->streamManager->writableDSRStreams().empty());
2395
2396 handleStreamBufMetaWritten(
2397 *conn,
2398 *stream,
2399 bufMetaStartingOffset + 600,
2400 400,
2401 true,
2402 3 /* PacketNum */,
2403 PacketNumberSpace::AppData);
2404 ASSERT_EQ(0, stream->writeBufMeta.length);
2405 ASSERT_TRUE(stream->writeBufMeta.eof);
2406 ASSERT_EQ(bufMetaStartingOffset + 1000 + 1, stream->writeBufMeta.offset);
2407 retxBufMetaIter =
2408 stream->retransmissionBufMetas.find(bufMetaStartingOffset + 600);
2409 ASSERT_NE(stream->retransmissionBufMetas.end(), retxBufMetaIter);
2410 ASSERT_EQ(bufMetaStartingOffset + 600, retxBufMetaIter->second.offset);
2411 ASSERT_EQ(400, retxBufMetaIter->second.length);
2412 ASSERT_TRUE(retxBufMetaIter->second.eof);
2413 conn->streamManager->updateWritableStreams(*stream);
2414 conn->streamManager->updateLossStreams(*stream);
2415 EXPECT_FALSE(conn->streamManager->hasLoss());
2416 EXPECT_TRUE(conn->streamManager->writableDSRStreams().empty());
2417
2418 // Lose the 1st dsr packet:
2419 RegularQuicWritePacket packet1(PacketHeader(ShortHeader(
2420 ProtectionType::KeyPhaseZero, conn->serverConnectionId.value(), 1)));
2421 WriteStreamFrame frame1(stream->id, bufMetaStartingOffset, 200, false);
2422 frame1.fromBufMeta = true;
2423 packet1.frames.push_back(frame1);
2424 markPacketLoss(*conn, packet1, false /* processed */);
2425 EXPECT_EQ(1, stream->lossBufMetas.size());
2426 const auto& lostBufMeta1 = stream->lossBufMetas.front();
2427 EXPECT_EQ(bufMetaStartingOffset, lostBufMeta1.offset);
2428 EXPECT_EQ(200, lostBufMeta1.length);
2429 EXPECT_FALSE(lostBufMeta1.eof);
2430 EXPECT_EQ(2, stream->retransmissionBufMetas.size());
2431 EXPECT_TRUE(conn->streamManager->hasLoss());
2432 EXPECT_FALSE(conn->streamManager->writableDSRStreams().empty());
2433
2434 // Lose the 3rd dsr packet:
2435 RegularQuicWritePacket packet3(PacketHeader(ShortHeader(
2436 ProtectionType::KeyPhaseZero, conn->serverConnectionId.value(), 3)));
2437 WriteStreamFrame frame3(stream->id, bufMetaStartingOffset + 600, 400, true);
2438 frame3.fromBufMeta = true;
2439 packet3.frames.push_back(frame3);
2440 markPacketLoss(*conn, packet3, false /* processed */);
2441 EXPECT_EQ(2, stream->lossBufMetas.size());
2442 const auto& lostBufMeta2 = stream->lossBufMetas.back();
2443 EXPECT_EQ(bufMetaStartingOffset + 600, lostBufMeta2.offset);
2444 EXPECT_EQ(400, lostBufMeta2.length);
2445 EXPECT_TRUE(lostBufMeta2.eof);
2446 EXPECT_EQ(1, stream->retransmissionBufMetas.size());
2447 EXPECT_TRUE(conn->streamManager->hasLoss());
2448 EXPECT_FALSE(conn->streamManager->writableDSRStreams().empty());
2449
2450 // Lose the 3nd dsr packet, it should be merged together with the first
2451 // element in the lossBufMetas:
2452 RegularQuicWritePacket packet2(PacketHeader(ShortHeader(
2453 ProtectionType::KeyPhaseZero, conn->serverConnectionId.value(), 2)));
2454 WriteStreamFrame frame2(stream->id, bufMetaStartingOffset + 200, 400, false);
2455 frame2.fromBufMeta = true;
2456 packet2.frames.push_back(frame2);
2457 markPacketLoss(*conn, packet2, false /* processed */);
2458 EXPECT_EQ(2, stream->lossBufMetas.size());
2459 const auto& lostBufMeta3 = stream->lossBufMetas.front();
2460 EXPECT_EQ(bufMetaStartingOffset, lostBufMeta3.offset);
2461 EXPECT_EQ(600, lostBufMeta3.length);
2462 EXPECT_FALSE(lostBufMeta3.eof);
2463 EXPECT_EQ(0, stream->retransmissionBufMetas.size());
2464 EXPECT_TRUE(conn->streamManager->hasLoss());
2465 EXPECT_FALSE(conn->streamManager->writableDSRStreams().empty());
2466 }
2467
2468 INSTANTIATE_TEST_CASE_P(
2469 QuicLossFunctionsTests,
2470 QuicLossFunctionsTest,
2471 Values(
2472 PacketNumberSpace::Initial,
2473 PacketNumberSpace::Handshake,
2474 PacketNumberSpace::AppData));
2475
2476 } // namespace test
2477 } // namespace quic
2478