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 <gmock/gmock.h>
10 #include <gtest/gtest.h>
11 
12 #include <quic/common/test/TestUtils.h>
13 
14 #include <quic/QuicConstants.h>
15 #include <quic/api/test/Mocks.h>
16 #include <quic/fizz/server/handshake/FizzServerQuicHandshakeContext.h>
17 #include <quic/logging/test/Mocks.h>
18 #include <quic/server/state/ServerStateMachine.h>
19 #include <quic/state/AckHandlers.h>
20 #include <quic/state/StateData.h>
21 #include <quic/state/test/Mocks.h>
22 
23 #include <numeric>
24 
25 using namespace testing;
26 
27 namespace quic {
28 namespace test {
29 
30 class AckHandlersTest : public TestWithParam<PacketNumberSpace> {};
31 
testLossHandler(std::vector<PacketNum> & lostPackets)32 auto testLossHandler(std::vector<PacketNum>& lostPackets) -> decltype(auto) {
33   return [&lostPackets](QuicConnectionStateBase&, auto& packet, bool) {
34     auto packetNum = packet.header.getPacketSequenceNum();
35     lostPackets.push_back(packetNum);
36   };
37 }
38 
emplacePackets(QuicServerConnectionState & conn,PacketNum lastPacketNum,TimePoint startTime,PacketNumberSpace pnSpace)39 auto emplacePackets(
40     QuicServerConnectionState& conn,
41     PacketNum lastPacketNum,
42     TimePoint startTime,
43     PacketNumberSpace pnSpace) {
44   PacketNum packetNum = 0;
45   StreamId streamid = 0;
46   TimePoint sentTime;
47   std::vector<TimePoint> packetRcvTime;
48   while (packetNum < lastPacketNum) {
49     auto regularPacket = createNewPacket(packetNum, pnSpace);
50     WriteStreamFrame frame(streamid++, 0, 0, true);
51     regularPacket.frames.emplace_back(frame);
52     sentTime = startTime + std::chrono::milliseconds(packetNum);
53     packetRcvTime.emplace_back(sentTime);
54     conn.outstandings
55         .packetCount[regularPacket.header.getPacketNumberSpace()]++;
56     OutstandingPacket sentPacket(
57         std::move(regularPacket),
58         sentTime,
59         1,
60         0,
61         false /* handshake */,
62         packetNum,
63         0,
64         packetNum + 1,
65         packetNum + 1,
66         quic::LossState(),
67         0);
68     conn.outstandings.packets.emplace_back(sentPacket);
69     packetNum++;
70   }
71 }
72 
TEST_P(AckHandlersTest,TestAckMultipleSequentialBlocks)73 TEST_P(AckHandlersTest, TestAckMultipleSequentialBlocks) {
74   QuicServerConnectionState conn(
75       FizzServerQuicHandshakeContext::Builder().build());
76   conn.lossState.reorderingThreshold = 85;
77   auto mockCongestionController = std::make_unique<MockCongestionController>();
78   auto rawCongestionController = mockCongestionController.get();
79   conn.congestionController = std::move(mockCongestionController);
80   // Get the time based loss detection out of the way
81   conn.lossState.srtt = 10s;
82 
83   StreamId currentStreamId = 10;
84   auto sentTime = Clock::now();
85   for (PacketNum packetNum = 10; packetNum <= 101; packetNum++) {
86     RegularQuicWritePacket regularPacket =
87         createNewPacket(packetNum, GetParam());
88     WriteStreamFrame frame(currentStreamId++, 0, 0, true);
89     regularPacket.frames.emplace_back(std::move(frame));
90     conn.outstandings
91         .packetCount[regularPacket.header.getPacketNumberSpace()]++;
92     conn.outstandings.packets.emplace_back(OutstandingPacket(
93         std::move(regularPacket),
94         sentTime,
95         1,
96         0,
97         false,
98         packetNum,
99         0,
100         0,
101         0,
102         LossState(),
103         0));
104   }
105   ReadAckFrame ackFrame;
106   ackFrame.largestAcked = 101;
107   // ACK packet ranges 21 - 101
108   for (PacketNum packetNum = 101; packetNum > 30; packetNum -= 20) {
109     ackFrame.ackBlocks.emplace_back(packetNum - 20, packetNum);
110   }
111 
112   std::vector<WriteStreamFrame> streams;
113   std::vector<PacketNum> lostPackets;
114   uint64_t expectedAckedBytes = 81;
115   uint64_t expectedAckedPackets = expectedAckedBytes; // each packet size is 1
116   size_t lostPacketsCounter = 0;
117   EXPECT_CALL(*rawCongestionController, onPacketAckOrLoss(_, _))
118       .WillRepeatedly(Invoke([&](auto ack, auto loss) {
119         if (ack) {
120           EXPECT_EQ(101, *ack->largestAckedPacket);
121           EXPECT_EQ(expectedAckedBytes, ack->ackedBytes);
122           EXPECT_EQ(expectedAckedPackets, ack->ackedPackets.size());
123         }
124         if (loss) {
125           lostPacketsCounter++;
126         }
127       }));
128   processAckFrame(
129       conn,
130       GetParam(),
131       ackFrame,
132       [&](const auto&, const auto& packetFrame, const ReadAckFrame&) {
133         auto& stream = *packetFrame.asWriteStreamFrame();
134         streams.emplace_back(stream);
135       },
136       testLossHandler(lostPackets),
137       Clock::now());
138   EXPECT_EQ(lostPacketsCounter, lostPackets.empty() ? 0 : 1);
139 
140   StreamId start = currentStreamId - 1;
141   for (auto& stream : streams) {
142     EXPECT_EQ(stream.streamId, start);
143     start--;
144   }
145   // only unacked packets should be remaining
146   auto numDeclaredLost = std::count_if(
147       conn.outstandings.packets.begin(),
148       conn.outstandings.packets.end(),
149       [](auto& op) { return op.declaredLost; });
150   EXPECT_GT(numDeclaredLost, 0);
151   EXPECT_EQ(numDeclaredLost, lostPackets.size());
152   EXPECT_EQ(numDeclaredLost, conn.outstandings.declaredLostCount);
153   EXPECT_EQ(conn.outstandings.packets.size(), numDeclaredLost + 5);
154 }
155 
TEST_P(AckHandlersTest,TestAckMultipleSequentialBlocksLoss)156 TEST_P(AckHandlersTest, TestAckMultipleSequentialBlocksLoss) {
157   QuicServerConnectionState conn(
158       FizzServerQuicHandshakeContext::Builder().build());
159   conn.lossState.reorderingThreshold = 85;
160   auto mockCongestionController = std::make_unique<MockCongestionController>();
161   auto rawCongestionController = mockCongestionController.get();
162   conn.congestionController = std::move(mockCongestionController);
163   // Get the time based loss detection out of the way
164   conn.lossState.srtt = 10s;
165 
166   StreamId currentStreamId = 10;
167   auto sentTime = Clock::now();
168   for (PacketNum packetNum = 10; packetNum <= 101; packetNum++) {
169     RegularQuicWritePacket regularPacket =
170         createNewPacket(packetNum, GetParam());
171     WriteStreamFrame frame(currentStreamId++, 0, 0, true);
172     regularPacket.frames.emplace_back(std::move(frame));
173     conn.outstandings
174         .packetCount[regularPacket.header.getPacketNumberSpace()]++;
175     conn.outstandings.packets.emplace_back(OutstandingPacket(
176         std::move(regularPacket),
177         sentTime,
178         1,
179         0,
180         false,
181         packetNum,
182         0,
183         0,
184         0,
185         LossState(),
186         0));
187   }
188   ReadAckFrame ackFrame;
189   ackFrame.largestAcked = 101;
190   // ACK packet ranges 21 - 101
191   for (PacketNum packetNum = 101; packetNum > 30; packetNum -= 20) {
192     ackFrame.ackBlocks.emplace_back(packetNum - 20, packetNum);
193   }
194 
195   std::vector<WriteStreamFrame> streams;
196   std::vector<PacketNum> lostPackets;
197   uint64_t expectedAckedBytes = 81;
198   uint64_t expectedAckedPackets = expectedAckedBytes; // each packet size is 1
199   size_t lostPacketsCounter = 0;
200   EXPECT_CALL(*rawCongestionController, onPacketAckOrLoss(_, _))
201       .Times(3)
202       .WillOnce(Invoke([&](auto ack, auto loss) {
203         if (ack) {
204           EXPECT_EQ(101, *ack->largestAckedPacket);
205           EXPECT_EQ(expectedAckedBytes, ack->ackedBytes);
206           EXPECT_EQ(expectedAckedPackets, ack->ackedPackets.size());
207         }
208         if (loss) {
209           lostPacketsCounter++;
210         }
211       }))
212       .WillRepeatedly(Invoke([](auto, auto) {}));
213   processAckFrame(
214       conn,
215       GetParam(),
216       ackFrame,
217       [&](const auto&, const auto& packetFrame, const ReadAckFrame&) {
218         auto& stream = *packetFrame.asWriteStreamFrame();
219         streams.emplace_back(stream);
220       },
221       testLossHandler(lostPackets),
222       Clock::now());
223   EXPECT_EQ(lostPacketsCounter, lostPackets.empty() ? 0 : 1);
224 
225   StreamId start = currentStreamId - 1;
226   for (auto& stream : streams) {
227     EXPECT_EQ(stream.streamId, start);
228     start--;
229   }
230   // only unacked packets should be remaining
231   auto numDeclaredLost = std::count_if(
232       conn.outstandings.packets.begin(),
233       conn.outstandings.packets.end(),
234       [](auto& op) { return op.declaredLost; });
235   EXPECT_GT(numDeclaredLost, 0);
236   EXPECT_EQ(numDeclaredLost, lostPackets.size());
237   EXPECT_EQ(numDeclaredLost, conn.outstandings.declaredLostCount);
238   EXPECT_EQ(conn.outstandings.packets.size(), numDeclaredLost + 5);
239   PacketNum lostPackt = 10;
240   for (auto& pkt : lostPackets) {
241     EXPECT_EQ(pkt, lostPackt++);
242   }
243   PacketNum packetNum = 16;
244   for (auto& packet : conn.outstandings.packets) {
245     if (packet.declaredLost) {
246       continue;
247     }
248     auto currentPacketNum = packet.packet.header.getPacketSequenceNum();
249     EXPECT_EQ(currentPacketNum, packetNum);
250     packetNum++;
251   }
252 
253   // 15 is lost, 16 is not, if we get an ack covering both both should be
254   // cleared.
255   auto itr = std::find_if(
256       conn.outstandings.packets.begin(),
257       conn.outstandings.packets.end(),
258       [](auto& op) {
259         return op.packet.header.getPacketSequenceNum() == 15 ||
260             op.packet.header.getPacketSequenceNum() == 16;
261       });
262   EXPECT_TRUE(itr != conn.outstandings.packets.end());
263   EXPECT_TRUE(itr->declaredLost);
264   EXPECT_EQ(itr->packet.header.getPacketSequenceNum(), 15);
265   itr++;
266   EXPECT_TRUE(itr != conn.outstandings.packets.end());
267   EXPECT_FALSE(itr->declaredLost);
268   EXPECT_EQ(itr->packet.header.getPacketSequenceNum(), 16);
269   EXPECT_EQ(conn.lossState.totalPacketsSpuriouslyMarkedLost, 0);
270   ackFrame.ackBlocks.emplace_back(15, 16);
271   processAckFrame(
272       conn,
273       GetParam(),
274       ackFrame,
275       [](auto, auto, auto) {},
276       [](auto&, auto&, auto) {},
277       Clock::now());
278   itr = std::find_if(
279       conn.outstandings.packets.begin(),
280       conn.outstandings.packets.end(),
281       [](auto& op) {
282         return op.packet.header.getPacketSequenceNum() == 15 ||
283             op.packet.header.getPacketSequenceNum() == 16;
284       });
285   EXPECT_TRUE(itr == conn.outstandings.packets.end());
286 
287   // Duplicate ACK much later, should clear out declared lost.
288   processAckFrame(
289       conn,
290       GetParam(),
291       ackFrame,
292       [](auto, auto, auto) {},
293       [](auto&, auto&, auto) {},
294       Clock::now() + 2 * calculatePTO(conn));
295 
296   numDeclaredLost = std::count_if(
297       conn.outstandings.packets.begin(),
298       conn.outstandings.packets.end(),
299       [](auto& op) { return op.declaredLost; });
300   EXPECT_EQ(numDeclaredLost, 0);
301   EXPECT_EQ(numDeclaredLost, conn.outstandings.declaredLostCount);
302   EXPECT_EQ(conn.lossState.totalPacketsSpuriouslyMarkedLost, 1);
303 }
304 
TEST_P(AckHandlersTest,TestAckBlocksWithGaps)305 TEST_P(AckHandlersTest, TestAckBlocksWithGaps) {
306   QuicServerConnectionState conn(
307       FizzServerQuicHandshakeContext::Builder().build());
308   conn.lossState.reorderingThreshold = 30;
309   auto mockCongestionController = std::make_unique<MockCongestionController>();
310   auto rawCongestionController = mockCongestionController.get();
311   conn.congestionController = std::move(mockCongestionController);
312   // Get the time based loss detection out of the way
313   conn.lossState.srtt = 10s;
314 
315   StreamId currentStreamId = 10;
316   for (PacketNum packetNum = 10; packetNum < 51; packetNum++) {
317     auto regularPacket = createNewPacket(packetNum, GetParam());
318     WriteStreamFrame frame(currentStreamId++, 0, 0, true);
319     regularPacket.frames.emplace_back(std::move(frame));
320     conn.outstandings
321         .packetCount[regularPacket.header.getPacketNumberSpace()]++;
322     conn.outstandings.packets.emplace_back(OutstandingPacket(
323         std::move(regularPacket),
324         Clock::now(),
325         1,
326         0,
327         false,
328         packetNum,
329         0,
330         0,
331         0,
332         LossState(),
333         0));
334   }
335 
336   ReadAckFrame ackFrame;
337   ackFrame.largestAcked = 45;
338   ackFrame.ackBlocks.emplace_back(45, 45);
339   ackFrame.ackBlocks.emplace_back(33, 44);
340   ackFrame.ackBlocks.emplace_back(12, 21);
341 
342   std::vector<WriteStreamFrame> streams;
343   std::vector<PacketNum> lostPackets;
344   uint64_t expectedAckedBytes = 21 - 12 + 1 + 44 - 33 + 1 + 45 - 45 + 1;
345   uint64_t expectedAckedPackets = expectedAckedBytes; // each packet size is 1
346   size_t lostPacketsCounter = 0;
347   EXPECT_CALL(*rawCongestionController, onPacketAckOrLoss(_, _))
348       .WillRepeatedly(Invoke([&](auto ack, auto loss) {
349         if (ack) {
350           EXPECT_EQ(45, *ack->largestAckedPacket);
351           EXPECT_EQ(expectedAckedBytes, ack->ackedBytes);
352           EXPECT_EQ(expectedAckedPackets, ack->ackedPackets.size());
353         }
354         if (loss) {
355           lostPacketsCounter++;
356         }
357       }));
358   processAckFrame(
359       conn,
360       GetParam(),
361       ackFrame,
362       [&](const auto&, const auto& packetFrame, const ReadAckFrame&) {
363         auto& stream = *packetFrame.asWriteStreamFrame();
364         streams.emplace_back(stream);
365       },
366       testLossHandler(lostPackets),
367       Clock::now());
368   EXPECT_EQ(lostPacketsCounter, lostPackets.empty() ? 0 : 1);
369 
370   StreamId start = 45;
371   std::vector<StreamId> ids(45 - 33 + 1);
372   std::generate(ids.begin(), ids.end(), [&]() { return start--; });
373   EXPECT_TRUE(std::equal(
374       streams.begin(),
375       streams.begin() + (45 - 33 + 1),
376       ids.begin(),
377       ids.end(),
378       [](const auto& frame, auto id) { return frame.streamId == id; }));
379 
380   start = 21;
381   std::vector<StreamId> ids2(10);
382   std::generate(ids2.begin(), ids2.end(), [&]() { return start--; });
383   EXPECT_TRUE(std::equal(
384       streams.begin() + (45 - 33 + 1),
385       streams.end(),
386       ids2.begin(),
387       ids2.end(),
388       [](const auto& frame, auto id) { return frame.streamId == id; }));
389 
390   std::vector<PacketNum> remainingPackets(11 + 5);
391   std::iota(remainingPackets.begin(), remainingPackets.begin() + 11, 22);
392   std::iota(remainingPackets.begin() + 11, remainingPackets.end(), 46);
393 
394   std::vector<PacketNum> actualPacketNumbers;
395   for (auto& op : conn.outstandings.packets) {
396     if (!op.declaredLost) {
397       actualPacketNumbers.push_back(op.packet.header.getPacketSequenceNum());
398     }
399   }
400   EXPECT_TRUE(std::equal(
401       actualPacketNumbers.begin(),
402       actualPacketNumbers.end(),
403       remainingPackets.begin(),
404       remainingPackets.end()));
405 
406   std::vector<PacketNum> actualLostPackets = {10, 11};
407 
408   EXPECT_TRUE(std::equal(
409       actualLostPackets.begin(),
410       actualLostPackets.end(),
411       lostPackets.begin(),
412       lostPackets.end()));
413 }
414 
TEST_P(AckHandlersTest,TestNonSequentialPacketNumbers)415 TEST_P(AckHandlersTest, TestNonSequentialPacketNumbers) {
416   QuicServerConnectionState conn(
417       FizzServerQuicHandshakeContext::Builder().build());
418   conn.lossState.reorderingThreshold = 10;
419   auto mockCongestionController = std::make_unique<MockCongestionController>();
420   auto rawCongestionController = mockCongestionController.get();
421   conn.congestionController = std::move(mockCongestionController);
422   // Get the time based loss detection out of the way
423   conn.lossState.srtt = 10s;
424 
425   StreamId current = 10;
426   for (PacketNum packetNum = 10; packetNum < 20; packetNum++) {
427     auto regularPacket = createNewPacket(packetNum, GetParam());
428     WriteStreamFrame frame(current++, 0, 0, true);
429     regularPacket.frames.emplace_back(std::move(frame));
430     conn.outstandings
431         .packetCount[regularPacket.header.getPacketNumberSpace()]++;
432     conn.outstandings.packets.emplace_back(OutstandingPacket(
433         std::move(regularPacket),
434         Clock::now(),
435         1,
436         0,
437         false,
438         packetNum,
439         0,
440         0,
441         0,
442         LossState(),
443         0));
444   }
445 
446   for (PacketNum packetNum = 20; packetNum < 40; packetNum += 3) {
447     auto regularPacket = createNewPacket(packetNum, GetParam());
448     WriteStreamFrame frame(current, 0, 0, true);
449     current += 3;
450     regularPacket.frames.emplace_back(std::move(frame));
451     conn.outstandings
452         .packetCount[regularPacket.header.getPacketNumberSpace()]++;
453     conn.outstandings.packets.emplace_back(OutstandingPacket(
454         std::move(regularPacket),
455         Clock::now(),
456         1,
457         0,
458         false,
459         packetNum,
460         0,
461         0,
462         0,
463         LossState(),
464         0));
465   }
466 
467   ReadAckFrame ackFrame;
468   ackFrame.largestAcked = 26;
469   ackFrame.ackBlocks.emplace_back(26, 26);
470   // This intentionally acks an unsent packet. When we start enforcing
471   // unsent packets then disable this.
472   ackFrame.ackBlocks.emplace_back(5, 20);
473 
474   std::vector<WriteStreamFrame> streams;
475   std::vector<PacketNum> lostPackets;
476   // Only 26 and [10, 20] are acked:
477   uint64_t expectedAckedBytes = 20 - 10 + 1 + 1;
478   uint64_t expectedAckedPackets = expectedAckedBytes; // each packet size is 1
479   EXPECT_CALL(*rawCongestionController, onPacketAckOrLoss(_, _))
480       .Times(1)
481       .WillOnce(Invoke([&](auto ackEvent, auto) {
482         EXPECT_EQ(26, *ackEvent->largestAckedPacket);
483         EXPECT_EQ(expectedAckedBytes, ackEvent->ackedBytes);
484         EXPECT_EQ(expectedAckedPackets, ackEvent->ackedPackets.size());
485       }));
486   processAckFrame(
487       conn,
488       GetParam(),
489       ackFrame,
490       [&](const auto&, const auto& packetFrame, const ReadAckFrame&) {
491         auto& stream = *packetFrame.asWriteStreamFrame();
492         streams.emplace_back(stream);
493       },
494       testLossHandler(lostPackets),
495       Clock::now());
496 
497   EXPECT_EQ(26, streams.begin()->streamId);
498 
499   StreamId start = 20;
500   std::vector<StreamId> ids(20 - 10 + 1);
501   std::generate(ids.begin(), ids.end(), [&]() { return start--; });
502   EXPECT_TRUE(std::equal(
503       streams.begin() + 1,
504       streams.end(),
505       ids.begin(),
506       ids.end(),
507       [](const auto& frame, auto id) { return frame.streamId == id; }));
508 
509   std::vector<PacketNum> remainingPackets(5);
510   remainingPackets[0] = 23;
511   int remainingIdx = 1;
512   for (PacketNum num = 29; num < 40; num += 3) {
513     remainingPackets[remainingIdx++] = num;
514   }
515 
516   std::vector<PacketNum> actualPacketNumbers;
517   std::transform(
518       conn.outstandings.packets.begin(),
519       conn.outstandings.packets.end(),
520       std::back_insert_iterator<decltype(actualPacketNumbers)>(
521           actualPacketNumbers),
522       [](const auto& packet) {
523         return packet.packet.header.getPacketSequenceNum();
524       });
525 
526   EXPECT_TRUE(std::equal(
527       actualPacketNumbers.begin(),
528       actualPacketNumbers.end(),
529       remainingPackets.begin(),
530       remainingPackets.end()));
531 }
532 
TEST_P(AckHandlersTest,AckVisitorForAckTest)533 TEST_P(AckHandlersTest, AckVisitorForAckTest) {
534   QuicServerConnectionState conn(
535       FizzServerQuicHandshakeContext::Builder().build());
536   conn.connectionTime = Clock::now();
537   auto firstPacket = createNewPacket(100 /* packetNum */, GetParam());
538   WriteAckFrame firstAckFrame;
539   firstAckFrame.ackBlocks.emplace_back(900, 1000);
540   firstAckFrame.ackBlocks.emplace_back(500, 700);
541   conn.ackStates.appDataAckState.acks.insert(900, 1000);
542   conn.ackStates.appDataAckState.acks.insert(500, 700);
543   firstPacket.frames.emplace_back(std::move(firstAckFrame));
544   conn.outstandings.packetCount[firstPacket.header.getPacketNumberSpace()]++;
545   conn.outstandings.packets.emplace_back(OutstandingPacket(
546       std::move(firstPacket),
547       Clock::now(),
548       0,
549       0,
550       false,
551       0,
552       0,
553       0,
554       0,
555       LossState(),
556       0));
557 
558   auto secondPacket = createNewPacket(101 /* packetNum */, GetParam());
559   WriteAckFrame secondAckFrame;
560   secondAckFrame.ackBlocks.emplace_back(1100, 2000);
561   secondAckFrame.ackBlocks.emplace_back(1002, 1090);
562   conn.ackStates.appDataAckState.acks.insert(1100, 2000);
563   conn.ackStates.appDataAckState.acks.insert(1002, 1090);
564   secondPacket.frames.emplace_back(std::move(secondAckFrame));
565   conn.outstandings.packetCount[secondPacket.header.getPacketNumberSpace()]++;
566   conn.outstandings.packets.emplace_back(OutstandingPacket(
567       std::move(secondPacket),
568       Clock::now(),
569       0,
570       0,
571       false,
572       0,
573       0,
574       0,
575       0,
576       LossState(),
577       0));
578 
579   ReadAckFrame firstReceivedAck;
580   firstReceivedAck.largestAcked = 100;
581   firstReceivedAck.ackBlocks.emplace_back(100, 100);
582   processAckFrame(
583       conn,
584       GetParam(),
585       firstReceivedAck,
586       [&](const auto& outstandingPacket,
587           const auto& packetFrame,
588           const ReadAckFrame&) {
589         auto ackedPacketNum =
590             outstandingPacket.packet.header.getPacketSequenceNum();
591         EXPECT_EQ(ackedPacketNum, firstReceivedAck.largestAcked);
592         const WriteAckFrame* frame = packetFrame.asWriteAckFrame();
593         if (frame) {
594           commonAckVisitorForAckFrame(conn.ackStates.appDataAckState, *frame);
595         }
596       },
597       [](auto& /* conn */, auto& /* packet */, bool /* processed */
598       ) {},
599       Clock::now());
600   EXPECT_EQ(2, conn.ackStates.appDataAckState.acks.size());
601   EXPECT_EQ(
602       Interval<PacketNum>(1002, 1090),
603       conn.ackStates.appDataAckState.acks.front());
604   EXPECT_EQ(
605       Interval<PacketNum>(1100, 2000),
606       conn.ackStates.appDataAckState.acks.back());
607 
608   ReadAckFrame secondReceivedAck;
609   secondReceivedAck.largestAcked = 101;
610   secondReceivedAck.ackBlocks.emplace_back(101, 101);
611   processAckFrame(
612       conn,
613       GetParam(),
614       secondReceivedAck,
615       [&](const auto&, const auto& packetFrame, const ReadAckFrame&) {
616         const WriteAckFrame* frame = packetFrame.asWriteAckFrame();
617         if (frame) {
618           commonAckVisitorForAckFrame(conn.ackStates.appDataAckState, *frame);
619         }
620       },
621       [](auto& /* conn */, auto& /* packet */, bool /* processed */
622       ) {},
623       Clock::now());
624   EXPECT_TRUE(conn.ackStates.appDataAckState.acks.empty());
625 }
626 
TEST_P(AckHandlersTest,NoNewAckedPacket)627 TEST_P(AckHandlersTest, NoNewAckedPacket) {
628   QuicServerConnectionState conn(
629       FizzServerQuicHandshakeContext::Builder().build());
630   auto mockController = std::make_unique<MockCongestionController>();
631   auto rawController = mockController.get();
632   conn.congestionController = std::move(mockController);
633 
634   conn.lossState.ptoCount = 1;
635   PacketNum packetAfterRtoNum = 10;
636   auto packetAfterRto = createNewPacket(packetAfterRtoNum, GetParam());
637   conn.outstandings.packetCount[packetAfterRto.header.getPacketNumberSpace()]++;
638   conn.outstandings.packets.emplace_back(OutstandingPacket(
639       std::move(packetAfterRto),
640       Clock::now(),
641       0,
642       0,
643       false,
644       0,
645       0,
646       0,
647       0,
648       LossState(),
649       0));
650 
651   ReadAckFrame ackFrame;
652   ackFrame.largestAcked = 5;
653   EXPECT_CALL(*rawController, onPacketAckOrLoss(_, _)).Times(0);
654   processAckFrame(
655       conn,
656       GetParam(),
657       ackFrame,
658       [](const auto&, const auto&, const auto&) {},
659       [](auto&, auto&, bool) {},
660       Clock::now());
661   EXPECT_TRUE(conn.pendingEvents.setLossDetectionAlarm);
662   EXPECT_EQ(conn.lossState.ptoCount, 1);
663   EXPECT_TRUE(!conn.ackStates.appDataAckState.largestAckedByPeer.has_value());
664 }
665 
TEST_P(AckHandlersTest,LossByAckedRecovered)666 TEST_P(AckHandlersTest, LossByAckedRecovered) {
667   QuicServerConnectionState conn(
668       FizzServerQuicHandshakeContext::Builder().build());
669   auto mockController = std::make_unique<MockCongestionController>();
670   conn.congestionController = std::move(mockController);
671 
672   ReadAckFrame ackFrame;
673   ackFrame.largestAcked = 10;
674   ackFrame.ackBlocks.emplace_back(5, 10);
675   processAckFrame(
676       conn,
677       GetParam(),
678       ackFrame,
679       [](const auto&, const auto&, const auto&) {},
680       [](auto&, auto&, bool) {},
681       Clock::now());
682 }
683 
TEST_P(AckHandlersTest,AckPacketNumDoesNotExist)684 TEST_P(AckHandlersTest, AckPacketNumDoesNotExist) {
685   QuicServerConnectionState conn(
686       FizzServerQuicHandshakeContext::Builder().build());
687   auto mockController = std::make_unique<MockCongestionController>();
688   conn.congestionController = std::move(mockController);
689   // Get the time based loss detection out of the way
690   conn.lossState.srtt = 10s;
691 
692   PacketNum packetNum1 = 9;
693   auto regularPacket1 = createNewPacket(packetNum1, GetParam());
694   conn.outstandings.packetCount[regularPacket1.header.getPacketNumberSpace()]++;
695   conn.outstandings.packets.emplace_back(
696       std::move(regularPacket1),
697       Clock::now(),
698       0,
699       0,
700       false,
701       0,
702       0,
703       0,
704       0,
705       LossState(),
706       0);
707 
708   PacketNum packetNum2 = 10;
709   auto regularPacket2 = createNewPacket(packetNum2, GetParam());
710   conn.outstandings.packetCount[regularPacket2.header.getPacketNumberSpace()]++;
711   conn.outstandings.packets.emplace_back(
712       std::move(regularPacket2),
713       Clock::now(),
714       0,
715       0,
716       false,
717       0,
718       0,
719       0,
720       0,
721       LossState(),
722       0);
723 
724   // Ack a packet one higher than the packet so that we don't trigger reordering
725   // threshold.
726   ReadAckFrame ackFrame;
727   ackFrame.largestAcked = 1000;
728   ackFrame.ackBlocks.emplace_back(1000, 1000);
729   ackFrame.ackBlocks.emplace_back(10, 10);
730   processAckFrame(
731       conn,
732       GetParam(),
733       ackFrame,
734       [](const auto&, const auto&, const auto&) {},
735       [](auto&, auto&, bool) {},
736       Clock::now());
737   EXPECT_EQ(1, conn.outstandings.packets.size());
738 }
739 
TEST_P(AckHandlersTest,TestHandshakeCounterUpdate)740 TEST_P(AckHandlersTest, TestHandshakeCounterUpdate) {
741   QuicServerConnectionState conn(
742       FizzServerQuicHandshakeContext::Builder().build());
743   StreamId stream = 1;
744   for (PacketNum packetNum = 0; packetNum < 10; packetNum++) {
745     auto regularPacket = createNewPacket(
746         packetNum, (packetNum % 2 ? GetParam() : PacketNumberSpace::AppData));
747     WriteStreamFrame frame(
748         stream, 100 * packetNum + 0, 100 * packetNum + 100, false);
749     regularPacket.frames.emplace_back(std::move(frame));
750     conn.outstandings
751         .packetCount[regularPacket.header.getPacketNumberSpace()]++;
752     conn.outstandings.packets.emplace_back(
753         std::move(regularPacket),
754         Clock::now(),
755         0,
756         0,
757         packetNum % 2 && GetParam() != PacketNumberSpace::AppData,
758         packetNum / 2,
759         0,
760         0,
761         0,
762         LossState(),
763         0);
764   }
765 
766   ReadAckFrame ackFrame;
767   ackFrame.largestAcked = 9;
768   ackFrame.ackBlocks.emplace_back(3, 7);
769 
770   std::vector<PacketNum> lostPackets;
771   processAckFrame(
772       conn,
773       GetParam(),
774       ackFrame,
775       [&](const auto&, const auto&, const ReadAckFrame&) {},
776       testLossHandler(lostPackets),
777       Clock::now());
778   // When [3, 7] are acked, [0, 2] may also be marked loss if they are in the
779   // same packet number space, due to reordering threshold
780   auto numDeclaredLost = std::count_if(
781       conn.outstandings.packets.begin(),
782       conn.outstandings.packets.end(),
783       [](auto& op) { return op.declaredLost; });
784   EXPECT_EQ(numDeclaredLost, conn.outstandings.declaredLostCount);
785   if (GetParam() == PacketNumberSpace::Initial) {
786     EXPECT_EQ(numDeclaredLost, 1);
787     EXPECT_EQ(1, conn.outstandings.packetCount[PacketNumberSpace::Initial]);
788     // AppData packets won't be acked by an ack in Initial space:
789     // So 0, 2, 4, 6, 8 and 9 are left in OP list
790     EXPECT_EQ(numDeclaredLost + 6, conn.outstandings.packets.size());
791   } else if (GetParam() == PacketNumberSpace::Handshake) {
792     EXPECT_EQ(numDeclaredLost, 1);
793     EXPECT_EQ(1, conn.outstandings.packetCount[PacketNumberSpace::Handshake]);
794     // AppData packets won't be acked by an ack in Handshake space:
795     // So 0, 2, 4, 6, 8 and 9 are left in OP list
796     EXPECT_EQ(numDeclaredLost + 6, conn.outstandings.packets.size());
797   } else {
798     EXPECT_EQ(numDeclaredLost + 2, conn.outstandings.packets.size());
799   }
800 }
801 
TEST_P(AckHandlersTest,PurgeAcks)802 TEST_P(AckHandlersTest, PurgeAcks) {
803   QuicServerConnectionState conn(
804       FizzServerQuicHandshakeContext::Builder().build());
805   WriteAckFrame ackFrame;
806   ackFrame.ackBlocks.emplace_back(900, 1000);
807   ackFrame.ackBlocks.emplace_back(500, 700);
808   conn.ackStates.initialAckState.acks.insert(900, 1200);
809   conn.ackStates.initialAckState.acks.insert(500, 800);
810   auto expectedTime = Clock::now();
811   conn.ackStates.initialAckState.largestRecvdPacketTime = expectedTime;
812   commonAckVisitorForAckFrame(conn.ackStates.initialAckState, ackFrame);
813   // We should have purged old packets in ack state
814   EXPECT_EQ(conn.ackStates.initialAckState.acks.size(), 1);
815   EXPECT_EQ(conn.ackStates.initialAckState.acks.front().start, 1001);
816   EXPECT_EQ(conn.ackStates.initialAckState.acks.front().end, 1200);
817   EXPECT_EQ(
818       expectedTime, *conn.ackStates.initialAckState.largestRecvdPacketTime);
819 }
820 
TEST_P(AckHandlersTest,NoSkipAckVisitor)821 TEST_P(AckHandlersTest, NoSkipAckVisitor) {
822   QuicServerConnectionState conn(
823       FizzServerQuicHandshakeContext::Builder().build());
824   auto mockCongestionController = std::make_unique<MockCongestionController>();
825   auto rawCongestionController = mockCongestionController.get();
826   conn.congestionController = std::move(mockCongestionController);
827   EXPECT_CALL(*rawCongestionController, onPacketAckOrLoss(_, _))
828       .Times(1)
829       .WillOnce(Invoke([&](auto ackEvent, auto) {
830         EXPECT_EQ(1, ackEvent->ackedPackets.size());
831         EXPECT_EQ(1, ackEvent->ackedPackets.front().encodedSize);
832         EXPECT_EQ(1, ackEvent->ackedPackets.front().totalBytesSentThen);
833       }));
834 
835   PacketNum packetNum = 0;
836   auto regularPacket = createNewPacket(packetNum, GetParam());
837   // We need to at least have one frame to trigger ackVisitor
838   WriteStreamFrame frame(0, 0, 0, true);
839   regularPacket.frames.emplace_back(std::move(frame));
840   conn.outstandings.packetCount[regularPacket.header.getPacketNumberSpace()]++;
841   conn.outstandings.packets.emplace_back(OutstandingPacket(
842       std::move(regularPacket),
843       Clock::now(),
844       1,
845       0,
846       false,
847       1,
848       0,
849       0,
850       0,
851       LossState(),
852       0));
853   ReadAckFrame ackFrame;
854   ackFrame.largestAcked = 0;
855   ackFrame.ackBlocks.emplace_back(0, 0);
856   uint16_t ackVisitorCounter = 0;
857   // A counting ack visitor
858   auto countingAckVisitor = [&](const auto& /* outstandingPacket */,
859                                 const auto& /* packetFrame */,
860                                 const auto& /* readAckFrame */) {
861     ackVisitorCounter++;
862   };
863   processAckFrame(
864       conn,
865       GetParam(),
866       ackFrame,
867       countingAckVisitor,
868       [&](auto& /*conn*/, auto& /* packet */, bool /* processed */
869       ) { /* no-op lossVisitor */ },
870       Clock::now());
871   EXPECT_EQ(1, ackVisitorCounter);
872 }
873 
TEST_P(AckHandlersTest,SkipAckVisitor)874 TEST_P(AckHandlersTest, SkipAckVisitor) {
875   QuicServerConnectionState conn(
876       FizzServerQuicHandshakeContext::Builder().build());
877   auto mockCongestionController = std::make_unique<MockCongestionController>();
878   auto rawCongestionController = mockCongestionController.get();
879   conn.congestionController = std::move(mockCongestionController);
880   EXPECT_CALL(*rawCongestionController, onPacketAckOrLoss(_, _))
881       .Times(1)
882       .WillOnce(Invoke([&](auto ackEvent, auto) {
883         EXPECT_EQ(1, ackEvent->ackedPackets.size());
884         EXPECT_EQ(1, ackEvent->ackedPackets.front().encodedSize);
885         EXPECT_EQ(1, ackEvent->ackedPackets.front().totalBytesSentThen);
886       }));
887 
888   PacketNum packetNum = 0;
889   auto regularPacket = createNewPacket(packetNum, GetParam());
890   // We need to at least have one frame to trigger ackVisitor
891   WriteStreamFrame frame(0, 0, 0, true);
892   regularPacket.frames.emplace_back(std::move(frame));
893   OutstandingPacket outstandingPacket(
894       std::move(regularPacket),
895       Clock::now(),
896       1,
897       0,
898       false,
899       1,
900       0,
901       0,
902       0,
903       LossState(),
904       0);
905   // Give this outstandingPacket an associatedEvent that's not in
906   // outstandings.packetEvents
907   outstandingPacket.associatedEvent.emplace(GetParam(), 0);
908   conn.outstandings.packets.push_back(std::move(outstandingPacket));
909   conn.outstandings.clonedPacketCount[GetParam()]++;
910 
911   ReadAckFrame ackFrame;
912   ackFrame.largestAcked = 0;
913   ackFrame.ackBlocks.emplace_back(0, 0);
914   uint16_t ackVisitorCounter = 0;
915   // A counting ack visitor
916   auto countingAckVisitor = [&](const auto& /* outstandingPacket */,
917                                 const auto& /* packetFrame */,
918                                 const auto& /* readAckFrame */) {
919     ackVisitorCounter++;
920   };
921   processAckFrame(
922       conn,
923       GetParam(),
924       ackFrame,
925       countingAckVisitor,
926       [&](auto& /*conn*/, auto& /* packet */, bool /* processed */
927       ) { /* no-op lossVisitor */ },
928       Clock::now());
929   EXPECT_EQ(0, ackVisitorCounter);
930 }
931 
TEST_P(AckHandlersTest,NoDoubleProcess)932 TEST_P(AckHandlersTest, NoDoubleProcess) {
933   QuicServerConnectionState conn(
934       FizzServerQuicHandshakeContext::Builder().build());
935   conn.congestionController.reset();
936 
937   WriteStreamFrame frame(0, 0, 0, true);
938   PacketNum packetNum1 = 0, packetNum2 = 1;
939   auto regularPacket1 = createNewPacket(packetNum1, GetParam()),
940        regularPacket2 = createNewPacket(packetNum2, GetParam());
941   regularPacket1.frames.push_back(frame);
942   regularPacket2.frames.push_back(frame);
943 
944   OutstandingPacket outstandingPacket1(
945       std::move(regularPacket1),
946       Clock::now(),
947       1,
948       0,
949       false,
950       1,
951       0,
952       0,
953       0,
954       LossState(),
955       0);
956   outstandingPacket1.associatedEvent.emplace(GetParam(), packetNum1);
957 
958   OutstandingPacket outstandingPacket2(
959       std::move(regularPacket2),
960       Clock::now(),
961       1,
962       0,
963       false,
964       1,
965       0,
966       0,
967       0,
968       LossState(),
969       0);
970   // The seconds packet has the same PacketEvent
971   outstandingPacket2.associatedEvent.emplace(GetParam(), packetNum1);
972 
973   conn.outstandings.packetCount[GetParam()]++;
974   conn.outstandings.packets.push_back(std::move(outstandingPacket1));
975   conn.outstandings.packets.push_back(std::move(outstandingPacket2));
976   conn.outstandings.clonedPacketCount[GetParam()] += 2;
977   conn.outstandings.packetEvents.emplace(GetParam(), packetNum1);
978 
979   // A counting ack visitor
980   uint16_t ackVisitorCounter = 0;
981   auto countingAckVisitor = [&](const auto& /* outstandingPacket */,
982                                 const auto& /* packetFrame */,
983                                 const auto& /* readAckFrame */) {
984     ackVisitorCounter++;
985   };
986 
987   // First ack. This will ack first packet, and trigger a ack visiting.
988   ReadAckFrame ackFrame1;
989   ackFrame1.largestAcked = 0;
990   ackFrame1.ackBlocks.emplace_back(0, 0);
991   processAckFrame(
992       conn,
993       GetParam(),
994       ackFrame1,
995       countingAckVisitor,
996       [&](auto& /*conn*/, auto& /* packet */, bool /* processed */
997       ) { /* no-op lossVisitor */ },
998       Clock::now());
999   EXPECT_EQ(1, ackVisitorCounter);
1000 
1001   // Second ack that acks the second packet.  This won't trigger a visit.
1002   ReadAckFrame ackFrame2;
1003   ackFrame2.largestAcked = 1;
1004   ackFrame2.ackBlocks.emplace_back(1, 1);
1005   processAckFrame(
1006       conn,
1007       GetParam(),
1008       ackFrame2,
1009       countingAckVisitor,
1010       [&](auto& /* conn */, auto& /* packet */, bool /* processed */
1011       ) { /* no-op */ },
1012       Clock::now());
1013   EXPECT_EQ(1, ackVisitorCounter);
1014 }
1015 
TEST_P(AckHandlersTest,ClonedPacketsCounter)1016 TEST_P(AckHandlersTest, ClonedPacketsCounter) {
1017   QuicServerConnectionState conn(
1018       FizzServerQuicHandshakeContext::Builder().build());
1019   conn.congestionController = nullptr;
1020   WriteStreamFrame frame(0, 0, 0, true);
1021   auto packetNum1 = conn.ackStates.appDataAckState.nextPacketNum;
1022   auto regularPacket1 = createNewPacket(packetNum1, GetParam());
1023   regularPacket1.frames.push_back(frame);
1024   OutstandingPacket outstandingPacket1(
1025       std::move(regularPacket1),
1026       Clock::now(),
1027       1,
1028       0,
1029       false,
1030       1,
1031       0,
1032       0,
1033       0,
1034       LossState(),
1035       0);
1036   outstandingPacket1.associatedEvent.emplace(GetParam(), packetNum1);
1037 
1038   conn.ackStates.appDataAckState.nextPacketNum++;
1039   auto packetNum2 = conn.ackStates.appDataAckState.nextPacketNum;
1040   auto regularPacket2 = createNewPacket(packetNum2, GetParam());
1041   regularPacket2.frames.push_back(frame);
1042   OutstandingPacket outstandingPacket2(
1043       std::move(regularPacket2),
1044       Clock::now(),
1045       1,
1046       0,
1047       false,
1048       1,
1049       0,
1050       0,
1051       0,
1052       LossState(),
1053       0);
1054 
1055   conn.outstandings
1056       .packetCount[outstandingPacket1.packet.header.getPacketNumberSpace()]++;
1057   conn.outstandings
1058       .packetCount[outstandingPacket2.packet.header.getPacketNumberSpace()]++;
1059   conn.outstandings.packets.push_back(std::move(outstandingPacket1));
1060   conn.outstandings.packets.push_back(std::move(outstandingPacket2));
1061   conn.outstandings.clonedPacketCount[GetParam()] = 1;
1062   conn.outstandings.packetEvents.emplace(GetParam(), packetNum1);
1063 
1064   ReadAckFrame ackFrame;
1065   ackFrame.largestAcked = packetNum2;
1066   ackFrame.ackBlocks.emplace_back(packetNum1, packetNum2);
1067 
1068   uint16_t ackVisitorCounter = 0;
1069   auto countingAckVisitor = [&](const auto& /* outstandingPacket */,
1070                                 const auto& /* packetFrame */,
1071                                 const auto& /* readAckFrame */) {
1072     ackVisitorCounter++;
1073   };
1074   processAckFrame(
1075       conn,
1076       GetParam(),
1077       ackFrame,
1078       countingAckVisitor,
1079       [&](auto& /* conn */, auto& /* packet */, bool /* processed */
1080       ) { /* no-op */ },
1081       Clock::now());
1082   EXPECT_EQ(2, ackVisitorCounter);
1083   EXPECT_EQ(0, conn.outstandings.numClonedPackets());
1084 }
1085 
TEST_P(AckHandlersTest,UpdateMaxAckDelay)1086 TEST_P(AckHandlersTest, UpdateMaxAckDelay) {
1087   QuicServerConnectionState conn(
1088       FizzServerQuicHandshakeContext::Builder().build());
1089   conn.congestionController = nullptr;
1090   conn.lossState.mrtt = 200us;
1091   PacketNum packetNum = 0;
1092   auto regularPacket = createNewPacket(packetNum, GetParam());
1093   auto sentTime = Clock::now();
1094   conn.outstandings.packetCount[regularPacket.header.getPacketNumberSpace()]++;
1095   conn.outstandings.packets.emplace_back(OutstandingPacket(
1096       std::move(regularPacket),
1097       sentTime,
1098       1,
1099       0,
1100       false,
1101       1,
1102       0,
1103       0,
1104       0,
1105       LossState(),
1106       0));
1107 
1108   ReadAckFrame ackFrame;
1109   // ackDelay has no effect on mrtt
1110   ackFrame.ackDelay = 50us;
1111   ackFrame.largestAcked = 0;
1112   ackFrame.ackBlocks.emplace_back(0, 0);
1113 
1114   auto receiveTime = sentTime + 10us;
1115   processAckFrame(
1116       conn,
1117       GetParam(),
1118       ackFrame,
1119       [&](const auto&, const auto&, const auto&) { /* ackVisitor */ },
1120       [&](auto&, auto&, bool) { /* lossVisitor */ },
1121       receiveTime);
1122   EXPECT_EQ(10us, conn.lossState.mrtt);
1123 }
1124 
1125 // Ack only acks packets aren't outstanding, but TimeReordering still finds loss
TEST_P(AckHandlersTest,AckNotOutstandingButLoss)1126 TEST_P(AckHandlersTest, AckNotOutstandingButLoss) {
1127   QuicServerConnectionState conn(
1128       FizzServerQuicHandshakeContext::Builder().build());
1129   auto mockQLogger = std::make_shared<MockQLogger>(VantagePoint::Server);
1130   conn.qLogger = mockQLogger;
1131 
1132   conn.lossState.srtt = 200ms;
1133   conn.lossState.lrtt = 150ms;
1134   // Packet 2 has been sent and acked:
1135   if (GetParam() == PacketNumberSpace::Initial) {
1136     conn.ackStates.initialAckState.largestAckedByPeer = 2;
1137   } else if (GetParam() == PacketNumberSpace::Handshake) {
1138     conn.ackStates.handshakeAckState.largestAckedByPeer = 2;
1139   } else {
1140     conn.ackStates.appDataAckState.largestAckedByPeer = 2;
1141   }
1142   auto mockCongestionController = std::make_unique<MockCongestionController>();
1143   auto rawCongestionController = mockCongestionController.get();
1144   conn.congestionController = std::move(mockCongestionController);
1145   EXPECT_CALL(*rawCongestionController, onPacketAckOrLoss(_, _))
1146       .Times(1)
1147       .WillOnce(Invoke(
1148           [&](folly::Optional<CongestionController::AckEvent> ackEvent,
1149               folly::Optional<CongestionController::LossEvent> lossEvent) {
1150             EXPECT_FALSE(ackEvent->largestAckedPacket.has_value());
1151             EXPECT_TRUE(lossEvent->largestLostPacketNum.has_value());
1152           }));
1153 
1154   // But packet 1 has been outstanding for longer than delayUntilLost:
1155   PacketNum packetNum = 1;
1156   auto regularPacket = createNewPacket(packetNum, GetParam());
1157   // We need to at least have one frame to trigger ackVisitor
1158   WriteStreamFrame frame(0, 0, 0, true);
1159   regularPacket.frames.emplace_back(std::move(frame));
1160   auto delayUntilLost = 200ms *
1161       conn.transportSettings.timeReorderingThreshDividend /
1162       conn.transportSettings.timeReorderingThreshDivisor;
1163   OutstandingPacket outstandingPacket(
1164       std::move(regularPacket),
1165       Clock::now() - delayUntilLost - 20ms,
1166       1,
1167       0,
1168       false,
1169       1,
1170       0,
1171       0,
1172       0,
1173       LossState(),
1174       0);
1175   conn.outstandings.packets.push_back(std::move(outstandingPacket));
1176   conn.outstandings.packetCount[GetParam()]++;
1177 
1178   EXPECT_CALL(*mockQLogger, addPacketsLost(1, 1, 1));
1179 
1180   // Peer acks 2 again:
1181   ReadAckFrame ackFrame;
1182   ackFrame.largestAcked = 2;
1183   ackFrame.ackBlocks.emplace_back(2, 2);
1184   uint16_t ackVisitorCounter = 0;
1185   conn.lossState.largestSent = 2;
1186   // A counting ack visitor
1187   auto countingAckVisitor = [&](const auto& /* outstandingPacket */,
1188                                 const auto& /* packetFrame */,
1189                                 const auto& /* readAckFrame */) {
1190     ackVisitorCounter++;
1191   };
1192   processAckFrame(
1193       conn,
1194       GetParam(),
1195       ackFrame,
1196       countingAckVisitor,
1197       [&](auto& /*conn*/, auto& /* packet */, bool /* processed */
1198       ) { /* no-op lossVisitor */ },
1199       Clock::now());
1200   EXPECT_EQ(0, ackVisitorCounter);
1201 }
1202 
TEST_P(AckHandlersTest,UpdatePendingAckStates)1203 TEST_P(AckHandlersTest, UpdatePendingAckStates) {
1204   QuicServerConnectionState conn(
1205       FizzServerQuicHandshakeContext::Builder().build());
1206   conn.congestionController = nullptr;
1207   conn.lossState.totalBytesSent = 2468;
1208   conn.lossState.totalBodyBytesSent = 2000;
1209   conn.lossState.totalBytesAcked = 1357;
1210   conn.lossState.totalBodyBytesAcked = 1000;
1211   PacketNum packetNum = 0;
1212   auto regularPacket = createNewPacket(packetNum, GetParam());
1213   auto sentTime = Clock::now() - 1500ms;
1214   conn.outstandings.packetCount[regularPacket.header.getPacketNumberSpace()]++;
1215   conn.outstandings.packets.emplace_back(OutstandingPacket(
1216       std::move(regularPacket),
1217       sentTime,
1218       111,
1219       100,
1220       false,
1221       conn.lossState.totalBytesSent + 111,
1222       conn.lossState.totalBodyBytesSent + 100,
1223       0,
1224       0,
1225       LossState(),
1226       0));
1227   conn.lossState.totalBytesSent += 111;
1228   conn.lossState.totalBodyBytesSent += 100;
1229 
1230   ReadAckFrame ackFrame;
1231   ackFrame.largestAcked = 0;
1232   ackFrame.ackBlocks.emplace_back(0, 0);
1233 
1234   auto receiveTime = Clock::now() - 200ms;
1235   processAckFrame(
1236       conn,
1237       GetParam(),
1238       ackFrame,
1239       [&](auto, auto, auto) { /* ackVisitor */ },
1240       [&](auto&, auto&, auto) { /* lossVisitor */ },
1241       receiveTime);
1242   EXPECT_EQ(2468 + 111, conn.lossState.totalBytesSentAtLastAck);
1243   EXPECT_EQ(1357 + 111, conn.lossState.totalBytesAckedAtLastAck);
1244   EXPECT_EQ(sentTime, *conn.lossState.lastAckedPacketSentTime);
1245   EXPECT_EQ(receiveTime, *conn.lossState.lastAckedTime);
1246   EXPECT_EQ(111 + 1357, conn.lossState.totalBytesAcked);
1247   EXPECT_EQ(100 + 1000, conn.lossState.totalBodyBytesAcked);
1248 }
1249 
TEST_P(AckHandlersTest,AckEventCreation)1250 TEST_P(AckHandlersTest, AckEventCreation) {
1251   QuicServerConnectionState conn(
1252       FizzServerQuicHandshakeContext::Builder().build());
1253   auto mockCongestionController = std::make_unique<MockCongestionController>();
1254   auto rawCongestionController = mockCongestionController.get();
1255   conn.congestionController = std::move(mockCongestionController);
1256 
1257   PacketNum packetNum = 0;
1258   StreamId streamid = 0;
1259   TimePoint largestSentTime;
1260   while (packetNum < 10) {
1261     auto regularPacket = createNewPacket(packetNum, GetParam());
1262     WriteStreamFrame frame(streamid++, 0, 0, true);
1263     regularPacket.frames.emplace_back(std::move(frame));
1264     largestSentTime =
1265         Clock::now() - 100ms + std::chrono::milliseconds(packetNum);
1266     conn.outstandings
1267         .packetCount[regularPacket.header.getPacketNumberSpace()]++;
1268     OutstandingPacket sentPacket(
1269         std::move(regularPacket),
1270         largestSentTime,
1271         1,
1272         0,
1273         false /* handshake */,
1274         packetNum,
1275         0,
1276         0,
1277         0,
1278         LossState(),
1279         0);
1280     sentPacket.isAppLimited = (packetNum % 2);
1281     conn.outstandings.packets.emplace_back(sentPacket);
1282     packetNum++;
1283   }
1284 
1285   ReadAckFrame ackFrame;
1286   ackFrame.largestAcked = 9;
1287   ackFrame.ackBlocks.emplace_back(0, 9);
1288   auto ackTime = Clock::now() + 10ms;
1289   EXPECT_CALL(*rawCongestionController, onPacketAckOrLoss(_, _))
1290       .Times(1)
1291       .WillOnce(Invoke([&](auto ack, auto /* loss */) {
1292         EXPECT_EQ(ackTime, ack->ackTime);
1293         EXPECT_EQ(9, ack->largestAckedPacket.value());
1294         EXPECT_EQ(largestSentTime, ack->largestAckedPacketSentTime);
1295         EXPECT_EQ(10, ack->ackedBytes);
1296         EXPECT_TRUE(ack->largestAckedPacketAppLimited);
1297         EXPECT_EQ(
1298             std::chrono::ceil<std::chrono::microseconds>(
1299                 ackTime - largestSentTime),
1300             ack->mrttSample.value());
1301       }));
1302 
1303   processAckFrame(
1304       conn,
1305       GetParam(),
1306       ackFrame,
1307       [](const auto&, const auto&, const auto&) {},
1308       [](auto&, auto&, bool) {},
1309       ackTime);
1310 }
1311 
TEST_P(AckHandlersTest,ImplictAckEventCreation)1312 TEST_P(AckHandlersTest, ImplictAckEventCreation) {
1313   QuicServerConnectionState conn(
1314       FizzServerQuicHandshakeContext::Builder().build());
1315   auto mockCongestionController = std::make_unique<MockCongestionController>();
1316   auto rawCongestionController = mockCongestionController.get();
1317   conn.congestionController = std::move(mockCongestionController);
1318 
1319   PacketNum packetNum = 0;
1320   StreamId streamid = 0;
1321   TimePoint largestSentTime;
1322   while (packetNum < 10) {
1323     auto regularPacket = createNewPacket(packetNum, GetParam());
1324     WriteStreamFrame frame(streamid++, 0, 0, true);
1325     regularPacket.frames.emplace_back(std::move(frame));
1326     largestSentTime =
1327         Clock::now() - 100ms + std::chrono::milliseconds(packetNum);
1328     conn.outstandings
1329         .packetCount[regularPacket.header.getPacketNumberSpace()]++;
1330     OutstandingPacket sentPacket(
1331         std::move(regularPacket),
1332         largestSentTime,
1333         1,
1334         0,
1335         false /* handshake */,
1336         packetNum,
1337         0,
1338         packetNum + 1,
1339         0,
1340         LossState(),
1341         0);
1342     sentPacket.isAppLimited = (packetNum % 2);
1343     conn.outstandings.packets.emplace_back(sentPacket);
1344     packetNum++;
1345   }
1346 
1347   auto srttBefore = conn.lossState.srtt;
1348   ReadAckFrame ackFrame;
1349   ackFrame.largestAcked = 9;
1350   ackFrame.ackBlocks.emplace_back(0, 9);
1351   ackFrame.implicit = true;
1352   auto ackTime = Clock::now() + 10ms;
1353   EXPECT_CALL(*rawCongestionController, onPacketAckOrLoss(_, _))
1354       .Times(1)
1355       .WillOnce(Invoke([&](auto ack, auto /* loss */) {
1356         EXPECT_EQ(ackTime, ack->ackTime);
1357         EXPECT_EQ(9, ack->largestAckedPacket.value());
1358         EXPECT_EQ(largestSentTime, ack->largestAckedPacketSentTime);
1359         EXPECT_EQ(10, ack->ackedBytes);
1360         EXPECT_TRUE(ack->largestAckedPacketAppLimited);
1361         EXPECT_TRUE(ack->implicit);
1362         EXPECT_FALSE(ack->mrttSample.has_value());
1363         EXPECT_EQ(srttBefore, conn.lossState.srtt);
1364       }));
1365 
1366   processAckFrame(
1367       conn,
1368       GetParam(),
1369       ackFrame,
1370       [](const auto&, const auto&, const auto&) {},
1371       [](auto&, auto&, bool) {},
1372       ackTime);
1373 }
1374 
TEST_P(AckHandlersTest,TestRTTPacketObserverCallback)1375 TEST_P(AckHandlersTest, TestRTTPacketObserverCallback) {
1376   QuicServerConnectionState conn(
1377       FizzServerQuicHandshakeContext::Builder().build());
1378   auto mockCongestionController = std::make_unique<MockCongestionController>();
1379   conn.congestionController = std::move(mockCongestionController);
1380 
1381   // Register 1 observer
1382   Observer::Config config = {};
1383   config.rttSamples = true;
1384   auto ib = MockObserver(config);
1385 
1386   auto observers = std::make_shared<ObserverVec>();
1387   observers->emplace_back(&ib);
1388   conn.observers = observers;
1389 
1390   PacketNum packetNum = 0;
1391   StreamId streamid = 0;
1392   TimePoint sentTime;
1393   std::vector<TimePoint> packetRcvTime;
1394   while (packetNum < 30) {
1395     auto regularPacket = createNewPacket(packetNum, GetParam());
1396     WriteStreamFrame frame(streamid++, 0, 0, true);
1397     regularPacket.frames.emplace_back(std::move(frame));
1398     sentTime = Clock::now() - 100ms + std::chrono::milliseconds(packetNum);
1399     packetRcvTime.emplace_back(sentTime);
1400     conn.outstandings
1401         .packetCount[regularPacket.header.getPacketNumberSpace()]++;
1402     OutstandingPacket sentPacket(
1403         std::move(regularPacket),
1404         sentTime,
1405         1,
1406         0,
1407         false /* handshake */,
1408         packetNum,
1409         0,
1410         packetNum + 1,
1411         0,
1412         LossState(),
1413         0);
1414     sentPacket.isAppLimited = false;
1415     conn.outstandings.packets.emplace_back(sentPacket);
1416     packetNum++;
1417   }
1418 
1419   struct ackPacketData {
1420     PacketNum startSeq, endSeq;
1421     std::chrono::milliseconds ackDelay;
1422     TimePoint ackTime;
1423     ReadAckFrame ackFrame;
1424 
1425     explicit ackPacketData(
1426         PacketNum startSeqIn,
1427         PacketNum endSeqIn,
1428         std::chrono::milliseconds ackDelayIn)
1429         : startSeq(startSeqIn),
1430           endSeq(endSeqIn),
1431           ackDelay(ackDelayIn),
1432           ackTime(Clock::now() + 5ms) {
1433       ackFrame.largestAcked = endSeq;
1434       ackFrame.ackDelay = ackDelay;
1435       ackFrame.ackBlocks.emplace_back(startSeq, endSeq);
1436     }
1437   };
1438 
1439   // See each emplace as the ACK Block [X, Y] with size (Y-X+1)
1440   std::vector<ackPacketData> ackVec;
1441   // Sequential test
1442   ackVec.emplace_back(0, 5, 4ms); // +1 callback
1443   ackVec.emplace_back(6, 10, 5ms); // +1
1444   ackVec.emplace_back(11, 15, 6ms); // +1
1445   // Out-of-order test
1446   //
1447   // Its important to check the if
1448   // largestAcked - currentPacketNum > reorderingThreshold (currently 3)
1449   // else it can trigger Observer::packetLossDetected
1450   // and increase the number of callbacks
1451   ackVec.emplace_back(18, 18, 0ms); // +1
1452   ackVec.emplace_back(16, 17, 2ms); // +1
1453   ackVec.emplace_back(19, 29, 12ms); // +1 = 6 callbacks
1454 
1455   // 0 pending callbacks
1456   EXPECT_EQ(0, size(conn.pendingCallbacks));
1457 
1458   for (const auto ackData : ackVec) {
1459     processAckFrame(
1460         conn,
1461         GetParam(),
1462         ackData.ackFrame,
1463         [](const auto&, const auto&, const auto&) {},
1464         [](auto&, auto&, bool) {},
1465         ackData.ackTime);
1466   }
1467 
1468   // see above
1469   EXPECT_EQ(6, size(conn.pendingCallbacks));
1470 
1471   for (const auto ackData : ackVec) {
1472     auto rttSample = std::chrono::ceil<std::chrono::microseconds>(
1473         ackData.ackTime - packetRcvTime[ackData.endSeq]);
1474     EXPECT_CALL(
1475         ib,
1476         rttSampleGenerated(
1477             nullptr,
1478             AllOf(
1479                 Field(&Observer::PacketRTT::rcvTime, ackData.ackTime),
1480                 Field(&Observer::PacketRTT::rttSample, rttSample),
1481                 Field(&Observer::PacketRTT::ackDelay, ackData.ackDelay),
1482                 Field(
1483                     &Observer::PacketRTT::metadata,
1484                     Field(
1485                         &quic::OutstandingPacketMetadata::inflightBytes,
1486                         ackData.endSeq + 1)))));
1487   }
1488 
1489   for (auto& callback : conn.pendingCallbacks) {
1490     callback(nullptr);
1491   }
1492 }
1493 
TEST_P(AckHandlersTest,TestSpuriousObserverReorder)1494 TEST_P(AckHandlersTest, TestSpuriousObserverReorder) {
1495   QuicServerConnectionState conn(
1496       FizzServerQuicHandshakeContext::Builder().build());
1497   auto mockCongestionController = std::make_unique<MockCongestionController>();
1498   conn.congestionController = std::move(mockCongestionController);
1499 
1500   // Register 1 observer
1501   Observer::Config config = {};
1502   config.spuriousLossEvents = true;
1503   config.lossEvents = true;
1504   auto ib = MockObserver(config);
1505 
1506   auto observers = std::make_shared<ObserverVec>();
1507   observers->emplace_back(&ib);
1508   conn.observers = observers;
1509   auto noopLossVisitor = [](auto&, auto&, bool) {};
1510 
1511   TimePoint startTime = Clock::now();
1512   emplacePackets(conn, 10, startTime, GetParam());
1513 
1514   // from [0, 9], [3, 4] already acked
1515   auto beginPacket = getFirstOutstandingPacket(conn, GetParam());
1516   conn.outstandings.packets.erase(beginPacket + 3, beginPacket + 5);
1517   conn.outstandings.packetCount[GetParam()] -= 4;
1518 
1519   // setting a very low reordering threshold to force loss by reorder
1520   conn.lossState.reorderingThreshold = 1;
1521   // setting time out parameters higher than the time at which detectLossPackets
1522   // is called to make sure there are no losses by timeout
1523   conn.lossState.srtt = 400ms;
1524   conn.lossState.lrtt = 350ms;
1525   conn.transportSettings.timeReorderingThreshDividend = 1.0;
1526   conn.transportSettings.timeReorderingThreshDivisor = 1.0;
1527   TimePoint checkTime = startTime + 20ms;
1528 
1529   detectLossPackets(conn, 4, noopLossVisitor, checkTime, GetParam());
1530 
1531   // expecting 1 callback to be stacked
1532   EXPECT_EQ(1, size(conn.pendingCallbacks));
1533 
1534   EXPECT_CALL(
1535       ib,
1536       packetLossDetected(
1537           nullptr,
1538           Field(
1539               &Observer::LossEvent::lostPackets,
1540               UnorderedElementsAre(
1541                   MockObserver::getLossPacketMatcher(0, true, false),
1542                   MockObserver::getLossPacketMatcher(1, true, false),
1543                   MockObserver::getLossPacketMatcher(2, true, false)))))
1544       .Times(1);
1545 
1546   // Here we receive the spurious loss packets in a late ack
1547   {
1548     ReadAckFrame ackFrame;
1549     ackFrame.largestAcked = 2;
1550     ackFrame.ackBlocks.emplace_back(0, 2);
1551 
1552     processAckFrame(
1553         conn,
1554         GetParam(),
1555         ackFrame,
1556         [](const auto&, const auto&, const auto&) {},
1557         [](auto&, auto&, bool) {},
1558         startTime + 30ms);
1559   }
1560 
1561   // Spurious loss observer call added
1562   EXPECT_EQ(2, size(conn.pendingCallbacks));
1563 
1564   EXPECT_CALL(
1565       ib,
1566       spuriousLossDetected(
1567           nullptr,
1568           Field(
1569               &Observer::SpuriousLossEvent::spuriousPackets,
1570               UnorderedElementsAre(
1571                   MockObserver::getLossPacketMatcher(0, true, false),
1572                   MockObserver::getLossPacketMatcher(1, true, false),
1573                   MockObserver::getLossPacketMatcher(2, true, false)))))
1574       .Times(1);
1575 
1576   for (auto& callback : conn.pendingCallbacks) {
1577     callback(nullptr);
1578   }
1579 }
1580 
TEST_P(AckHandlersTest,TestSpuriousObserverTimeout)1581 TEST_P(AckHandlersTest, TestSpuriousObserverTimeout) {
1582   QuicServerConnectionState conn(
1583       FizzServerQuicHandshakeContext::Builder().build());
1584   auto mockCongestionController = std::make_unique<MockCongestionController>();
1585   conn.congestionController = std::move(mockCongestionController);
1586 
1587   // Register 1 observer
1588   Observer::Config config = {};
1589   config.spuriousLossEvents = true;
1590   config.lossEvents = true;
1591   auto ib = MockObserver(config);
1592 
1593   auto observers = std::make_shared<ObserverVec>();
1594   observers->emplace_back(&ib);
1595   conn.observers = observers;
1596   auto noopLossVisitor = [](auto&, auto&, bool) {};
1597 
1598   TimePoint startTime = Clock::now();
1599   emplacePackets(conn, 10, startTime, GetParam());
1600 
1601   // from [0, 9], [0, 4] already acked
1602   auto beginPacket = getFirstOutstandingPacket(conn, GetParam());
1603   conn.outstandings.packets.erase(beginPacket, beginPacket + 5);
1604   conn.outstandings.packetCount[GetParam()] -= 5;
1605 
1606   // setting a very high reordering threshold to force loss by timeout only
1607   conn.lossState.reorderingThreshold = 100;
1608   // setting time out parameters lower than the time at which detectLossPackets
1609   // is called to make sure all packets timeout
1610   conn.lossState.srtt = 400ms;
1611   conn.lossState.lrtt = 350ms;
1612   conn.transportSettings.timeReorderingThreshDividend = 1.0;
1613   conn.transportSettings.timeReorderingThreshDivisor = 1.0;
1614   TimePoint checkTime = startTime + 500ms;
1615 
1616   detectLossPackets(conn, 10, noopLossVisitor, checkTime, GetParam());
1617 
1618   // expecting 1 callback to be stacked
1619   EXPECT_EQ(1, size(conn.pendingCallbacks));
1620 
1621   EXPECT_CALL(
1622       ib,
1623       packetLossDetected(
1624           nullptr,
1625           Field(
1626               &Observer::LossEvent::lostPackets,
1627               UnorderedElementsAre(
1628                   MockObserver::getLossPacketMatcher(5, false, true),
1629                   MockObserver::getLossPacketMatcher(6, false, true),
1630                   MockObserver::getLossPacketMatcher(7, false, true),
1631                   MockObserver::getLossPacketMatcher(8, false, true),
1632                   MockObserver::getLossPacketMatcher(9, false, true)))))
1633       .Times(1);
1634 
1635   // Here we receive the spurious loss packets in a late ack
1636   {
1637     ReadAckFrame ackFrame;
1638     ackFrame.largestAcked = 9;
1639     ackFrame.ackBlocks.emplace_back(5, 9);
1640 
1641     processAckFrame(
1642         conn,
1643         GetParam(),
1644         ackFrame,
1645         [](const auto&, const auto&, const auto&) {},
1646         [](auto&, auto&, bool) {},
1647         startTime + 510ms);
1648   }
1649 
1650   // Spurious loss observer call added
1651   EXPECT_EQ(2, size(conn.pendingCallbacks));
1652 
1653   EXPECT_CALL(
1654       ib,
1655       spuriousLossDetected(
1656           nullptr,
1657           Field(
1658               &Observer::SpuriousLossEvent::spuriousPackets,
1659               UnorderedElementsAre(
1660                   MockObserver::getLossPacketMatcher(5, false, true),
1661                   MockObserver::getLossPacketMatcher(6, false, true),
1662                   MockObserver::getLossPacketMatcher(7, false, true),
1663                   MockObserver::getLossPacketMatcher(8, false, true),
1664                   MockObserver::getLossPacketMatcher(9, false, true)))))
1665       .Times(1);
1666 
1667   for (auto& callback : conn.pendingCallbacks) {
1668     callback(nullptr);
1669   }
1670 }
1671 
TEST_P(AckHandlersTest,SubMicrosecondRTT)1672 TEST_P(AckHandlersTest, SubMicrosecondRTT) {
1673   // Verify that an ackReceive timestamp that is less than 1 us
1674   // after the packet send timestamp results in an rtt sample rounded up to 1 us
1675   // rather than rounded down to 0. <1 us differences could occur because we
1676   // mix socket-provided timestamps for incoming packets (which can move
1677   // backwards) with steady_clock timestamps for outgoing packets. Clock
1678   // adjustments are more likely to result in < 1us differences when the clients
1679   // are close.
1680   QuicServerConnectionState conn(
1681       FizzServerQuicHandshakeContext::Builder().build());
1682 
1683   auto packetSendTime = Clock::now();
1684   auto packet = createNewPacket(5, GetParam());
1685   conn.outstandings.packetCount[packet.header.getPacketNumberSpace()]++;
1686   conn.outstandings.packets.emplace_back(OutstandingPacket(
1687       std::move(packet),
1688       packetSendTime,
1689       0,
1690       0,
1691       false,
1692       0,
1693       0,
1694       0,
1695       0,
1696       LossState(),
1697       0));
1698 
1699   ReadAckFrame ackFrame;
1700   auto ackReceiveTime = packetSendTime + 400ns;
1701   ackFrame.largestAcked = 5;
1702   ackFrame.ackBlocks.emplace_back(5, 5);
1703   processAckFrame(
1704       conn,
1705       GetParam(),
1706       ackFrame,
1707       [](const auto&, const auto&, const auto&) {},
1708       [](auto&, auto&, bool) {},
1709       ackReceiveTime);
1710   EXPECT_EQ(conn.lossState.lrtt, 1us);
1711 }
1712 
1713 INSTANTIATE_TEST_CASE_P(
1714     AckHandlersTests,
1715     AckHandlersTest,
1716     Values(
1717         PacketNumberSpace::Initial,
1718         PacketNumberSpace::Handshake,
1719         PacketNumberSpace::AppData));
1720 } // namespace test
1721 } // namespace quic
1722