1 // Copyright 2013 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "quiche/quic/core/quic_received_packet_manager.h"
6 
7 #include <algorithm>
8 #include <cstddef>
9 #include <ostream>
10 #include <vector>
11 
12 #include "quiche/quic/core/congestion_control/rtt_stats.h"
13 #include "quiche/quic/core/crypto/crypto_protocol.h"
14 #include "quiche/quic/core/quic_connection_stats.h"
15 #include "quiche/quic/core/quic_constants.h"
16 #include "quiche/quic/core/quic_types.h"
17 #include "quiche/quic/platform/api/quic_expect_bug.h"
18 #include "quiche/quic/platform/api/quic_flags.h"
19 #include "quiche/quic/platform/api/quic_test.h"
20 #include "quiche/quic/test_tools/mock_clock.h"
21 
22 namespace quic {
23 namespace test {
24 
25 class QuicReceivedPacketManagerPeer {
26  public:
SetOneImmediateAck(QuicReceivedPacketManager * manager,bool one_immediate_ack)27   static void SetOneImmediateAck(QuicReceivedPacketManager* manager,
28                                  bool one_immediate_ack) {
29     manager->one_immediate_ack_ = one_immediate_ack;
30   }
31 
SetAckDecimationDelay(QuicReceivedPacketManager * manager,float ack_decimation_delay)32   static void SetAckDecimationDelay(QuicReceivedPacketManager* manager,
33                                     float ack_decimation_delay) {
34     manager->ack_decimation_delay_ = ack_decimation_delay;
35   }
36 };
37 
38 namespace {
39 
40 const bool kInstigateAck = true;
41 const QuicTime::Delta kMinRttMs = QuicTime::Delta::FromMilliseconds(40);
42 const QuicTime::Delta kDelayedAckTime =
43     QuicTime::Delta::FromMilliseconds(kDefaultDelayedAckTimeMs);
44 
45 class QuicReceivedPacketManagerTest : public QuicTest {
46  protected:
QuicReceivedPacketManagerTest()47   QuicReceivedPacketManagerTest() : received_manager_(&stats_) {
48     clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
49     rtt_stats_.UpdateRtt(kMinRttMs, QuicTime::Delta::Zero(), QuicTime::Zero());
50     received_manager_.set_save_timestamps(true, false);
51   }
52 
RecordPacketReceipt(uint64_t packet_number)53   void RecordPacketReceipt(uint64_t packet_number) {
54     RecordPacketReceipt(packet_number, QuicTime::Zero());
55   }
56 
RecordPacketReceipt(uint64_t packet_number,QuicTime receipt_time)57   void RecordPacketReceipt(uint64_t packet_number, QuicTime receipt_time) {
58     RecordPacketReceipt(packet_number, receipt_time, ECN_NOT_ECT);
59   }
60 
RecordPacketReceipt(uint64_t packet_number,QuicTime receipt_time,QuicEcnCodepoint ecn_codepoint)61   void RecordPacketReceipt(uint64_t packet_number, QuicTime receipt_time,
62                            QuicEcnCodepoint ecn_codepoint) {
63     QuicPacketHeader header;
64     header.packet_number = QuicPacketNumber(packet_number);
65     received_manager_.RecordPacketReceived(header, receipt_time, ecn_codepoint);
66   }
67 
HasPendingAck()68   bool HasPendingAck() {
69     return received_manager_.ack_timeout().IsInitialized();
70   }
71 
MaybeUpdateAckTimeout(bool should_last_packet_instigate_acks,uint64_t last_received_packet_number)72   void MaybeUpdateAckTimeout(bool should_last_packet_instigate_acks,
73                              uint64_t last_received_packet_number) {
74     received_manager_.MaybeUpdateAckTimeout(
75         should_last_packet_instigate_acks,
76         QuicPacketNumber(last_received_packet_number),
77         /*last_packet_receipt_time=*/clock_.ApproximateNow(),
78         /*now=*/clock_.ApproximateNow(), &rtt_stats_);
79   }
80 
CheckAckTimeout(QuicTime time)81   void CheckAckTimeout(QuicTime time) {
82     QUICHE_DCHECK(HasPendingAck());
83     QUICHE_DCHECK_EQ(received_manager_.ack_timeout(), time);
84     if (time <= clock_.ApproximateNow()) {
85       // ACK timeout expires, send an ACK.
86       received_manager_.ResetAckStates();
87       QUICHE_DCHECK(!HasPendingAck());
88     }
89   }
90 
91   MockClock clock_;
92   RttStats rtt_stats_;
93   QuicConnectionStats stats_;
94   QuicReceivedPacketManager received_manager_;
95 };
96 
TEST_F(QuicReceivedPacketManagerTest,DontWaitForPacketsBefore)97 TEST_F(QuicReceivedPacketManagerTest, DontWaitForPacketsBefore) {
98   QuicPacketHeader header;
99   header.packet_number = QuicPacketNumber(2u);
100   received_manager_.RecordPacketReceived(header, QuicTime::Zero(), ECN_NOT_ECT);
101   header.packet_number = QuicPacketNumber(7u);
102   received_manager_.RecordPacketReceived(header, QuicTime::Zero(), ECN_NOT_ECT);
103   EXPECT_TRUE(received_manager_.IsAwaitingPacket(QuicPacketNumber(3u)));
104   EXPECT_TRUE(received_manager_.IsAwaitingPacket(QuicPacketNumber(6u)));
105   received_manager_.DontWaitForPacketsBefore(QuicPacketNumber(4));
106   EXPECT_FALSE(received_manager_.IsAwaitingPacket(QuicPacketNumber(3u)));
107   EXPECT_TRUE(received_manager_.IsAwaitingPacket(QuicPacketNumber(6u)));
108 }
109 
TEST_F(QuicReceivedPacketManagerTest,GetUpdatedAckFrame)110 TEST_F(QuicReceivedPacketManagerTest, GetUpdatedAckFrame) {
111   QuicPacketHeader header;
112   header.packet_number = QuicPacketNumber(2u);
113   QuicTime two_ms = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(2);
114   EXPECT_FALSE(received_manager_.ack_frame_updated());
115   received_manager_.RecordPacketReceived(header, two_ms, ECN_NOT_ECT);
116   EXPECT_TRUE(received_manager_.ack_frame_updated());
117 
118   QuicFrame ack = received_manager_.GetUpdatedAckFrame(QuicTime::Zero());
119   received_manager_.ResetAckStates();
120   EXPECT_FALSE(received_manager_.ack_frame_updated());
121   // When UpdateReceivedPacketInfo with a time earlier than the time of the
122   // largest observed packet, make sure that the delta is 0, not negative.
123   EXPECT_EQ(QuicTime::Delta::Zero(), ack.ack_frame->ack_delay_time);
124   EXPECT_EQ(1u, ack.ack_frame->received_packet_times.size());
125 
126   QuicTime four_ms = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(4);
127   ack = received_manager_.GetUpdatedAckFrame(four_ms);
128   received_manager_.ResetAckStates();
129   EXPECT_FALSE(received_manager_.ack_frame_updated());
130   // When UpdateReceivedPacketInfo after not having received a new packet,
131   // the delta should still be accurate.
132   EXPECT_EQ(QuicTime::Delta::FromMilliseconds(2),
133             ack.ack_frame->ack_delay_time);
134   // And received packet times won't have change.
135   EXPECT_EQ(1u, ack.ack_frame->received_packet_times.size());
136 
137   header.packet_number = QuicPacketNumber(999u);
138   received_manager_.RecordPacketReceived(header, two_ms, ECN_NOT_ECT);
139   header.packet_number = QuicPacketNumber(4u);
140   received_manager_.RecordPacketReceived(header, two_ms, ECN_NOT_ECT);
141   header.packet_number = QuicPacketNumber(1000u);
142   received_manager_.RecordPacketReceived(header, two_ms, ECN_NOT_ECT);
143   EXPECT_TRUE(received_manager_.ack_frame_updated());
144   ack = received_manager_.GetUpdatedAckFrame(two_ms);
145   received_manager_.ResetAckStates();
146   EXPECT_FALSE(received_manager_.ack_frame_updated());
147   // UpdateReceivedPacketInfo should discard any times which can't be
148   // expressed on the wire.
149   EXPECT_EQ(2u, ack.ack_frame->received_packet_times.size());
150 }
151 
TEST_F(QuicReceivedPacketManagerTest,UpdateReceivedConnectionStats)152 TEST_F(QuicReceivedPacketManagerTest, UpdateReceivedConnectionStats) {
153   EXPECT_FALSE(received_manager_.ack_frame_updated());
154   RecordPacketReceipt(1);
155   EXPECT_TRUE(received_manager_.ack_frame_updated());
156   RecordPacketReceipt(6);
157   RecordPacketReceipt(2,
158                       QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(1));
159 
160   EXPECT_EQ(4u, stats_.max_sequence_reordering);
161   EXPECT_EQ(1000, stats_.max_time_reordering_us);
162   EXPECT_EQ(1u, stats_.packets_reordered);
163 }
164 
TEST_F(QuicReceivedPacketManagerTest,LimitAckRanges)165 TEST_F(QuicReceivedPacketManagerTest, LimitAckRanges) {
166   received_manager_.set_max_ack_ranges(10);
167   EXPECT_FALSE(received_manager_.ack_frame_updated());
168   for (int i = 0; i < 100; ++i) {
169     RecordPacketReceipt(1 + 2 * i);
170     EXPECT_TRUE(received_manager_.ack_frame_updated());
171     received_manager_.GetUpdatedAckFrame(QuicTime::Zero());
172     EXPECT_GE(10u, received_manager_.ack_frame().packets.NumIntervals());
173     EXPECT_EQ(QuicPacketNumber(1u + 2 * i),
174               received_manager_.ack_frame().packets.Max());
175     for (int j = 0; j < std::min(10, i + 1); ++j) {
176       ASSERT_GE(i, j);
177       EXPECT_TRUE(received_manager_.ack_frame().packets.Contains(
178           QuicPacketNumber(1 + (i - j) * 2)));
179       if (i > j) {
180         EXPECT_FALSE(received_manager_.ack_frame().packets.Contains(
181             QuicPacketNumber((i - j) * 2)));
182       }
183     }
184   }
185 }
186 
TEST_F(QuicReceivedPacketManagerTest,TrimAckRangesEarly)187 TEST_F(QuicReceivedPacketManagerTest, TrimAckRangesEarly) {
188   const size_t kMaxAckRanges = 10;
189   received_manager_.set_max_ack_ranges(kMaxAckRanges);
190   for (size_t i = 0; i < kMaxAckRanges + 10; ++i) {
191     RecordPacketReceipt(1 + 2 * i);
192     if (i < kMaxAckRanges) {
193       EXPECT_EQ(i + 1, received_manager_.ack_frame().packets.NumIntervals());
194     } else {
195       EXPECT_EQ(kMaxAckRanges,
196                 received_manager_.ack_frame().packets.NumIntervals());
197     }
198   }
199 }
200 
TEST_F(QuicReceivedPacketManagerTest,IgnoreOutOfOrderTimestamps)201 TEST_F(QuicReceivedPacketManagerTest, IgnoreOutOfOrderTimestamps) {
202   EXPECT_FALSE(received_manager_.ack_frame_updated());
203   RecordPacketReceipt(1, QuicTime::Zero());
204   EXPECT_TRUE(received_manager_.ack_frame_updated());
205   EXPECT_EQ(1u, received_manager_.ack_frame().received_packet_times.size());
206   RecordPacketReceipt(2,
207                       QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(1));
208   EXPECT_EQ(2u, received_manager_.ack_frame().received_packet_times.size());
209   RecordPacketReceipt(3, QuicTime::Zero());
210   EXPECT_EQ(2u, received_manager_.ack_frame().received_packet_times.size());
211 }
212 
TEST_F(QuicReceivedPacketManagerTest,IgnoreOutOfOrderPackets)213 TEST_F(QuicReceivedPacketManagerTest, IgnoreOutOfOrderPackets) {
214   received_manager_.set_save_timestamps(true, true);
215   EXPECT_FALSE(received_manager_.ack_frame_updated());
216   RecordPacketReceipt(1, QuicTime::Zero());
217   EXPECT_TRUE(received_manager_.ack_frame_updated());
218   EXPECT_EQ(1u, received_manager_.ack_frame().received_packet_times.size());
219   RecordPacketReceipt(4,
220                       QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(1));
221   EXPECT_EQ(2u, received_manager_.ack_frame().received_packet_times.size());
222 
223   RecordPacketReceipt(3,
224                       QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(3));
225   EXPECT_EQ(2u, received_manager_.ack_frame().received_packet_times.size());
226 }
227 
TEST_F(QuicReceivedPacketManagerTest,HasMissingPackets)228 TEST_F(QuicReceivedPacketManagerTest, HasMissingPackets) {
229   EXPECT_QUIC_BUG(received_manager_.PeerFirstSendingPacketNumber(),
230                   "No packets have been received yet");
231   RecordPacketReceipt(4, QuicTime::Zero());
232   EXPECT_EQ(QuicPacketNumber(4),
233             received_manager_.PeerFirstSendingPacketNumber());
234   EXPECT_FALSE(received_manager_.HasMissingPackets());
235   RecordPacketReceipt(3, QuicTime::Zero());
236   EXPECT_FALSE(received_manager_.HasMissingPackets());
237   EXPECT_EQ(QuicPacketNumber(3),
238             received_manager_.PeerFirstSendingPacketNumber());
239   RecordPacketReceipt(1, QuicTime::Zero());
240   EXPECT_EQ(QuicPacketNumber(1),
241             received_manager_.PeerFirstSendingPacketNumber());
242   EXPECT_TRUE(received_manager_.HasMissingPackets());
243   RecordPacketReceipt(2, QuicTime::Zero());
244   EXPECT_EQ(QuicPacketNumber(1),
245             received_manager_.PeerFirstSendingPacketNumber());
246   EXPECT_FALSE(received_manager_.HasMissingPackets());
247 }
248 
TEST_F(QuicReceivedPacketManagerTest,OutOfOrderReceiptCausesAckSent)249 TEST_F(QuicReceivedPacketManagerTest, OutOfOrderReceiptCausesAckSent) {
250   EXPECT_FALSE(HasPendingAck());
251 
252   RecordPacketReceipt(3, clock_.ApproximateNow());
253   MaybeUpdateAckTimeout(kInstigateAck, 3);
254   // Delayed ack is scheduled.
255   CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
256 
257   RecordPacketReceipt(5, clock_.ApproximateNow());
258   MaybeUpdateAckTimeout(kInstigateAck, 5);
259   // Immediate ack is sent.
260   CheckAckTimeout(clock_.ApproximateNow());
261 
262   RecordPacketReceipt(6, clock_.ApproximateNow());
263   MaybeUpdateAckTimeout(kInstigateAck, 6);
264   // Immediate ack is scheduled, because 4 is still missing.
265   CheckAckTimeout(clock_.ApproximateNow());
266 
267   RecordPacketReceipt(2, clock_.ApproximateNow());
268   MaybeUpdateAckTimeout(kInstigateAck, 2);
269   CheckAckTimeout(clock_.ApproximateNow());
270 
271   RecordPacketReceipt(1, clock_.ApproximateNow());
272   MaybeUpdateAckTimeout(kInstigateAck, 1);
273   // Should ack immediately, since this fills the last hole.
274   CheckAckTimeout(clock_.ApproximateNow());
275 
276   RecordPacketReceipt(7, clock_.ApproximateNow());
277   MaybeUpdateAckTimeout(kInstigateAck, 7);
278   // Immediate ack is scheduled, because 4 is still missing.
279   CheckAckTimeout(clock_.ApproximateNow());
280 }
281 
TEST_F(QuicReceivedPacketManagerTest,OutOfOrderReceiptCausesAckSent1Ack)282 TEST_F(QuicReceivedPacketManagerTest, OutOfOrderReceiptCausesAckSent1Ack) {
283   QuicReceivedPacketManagerPeer::SetOneImmediateAck(&received_manager_, true);
284   EXPECT_FALSE(HasPendingAck());
285 
286   RecordPacketReceipt(3, clock_.ApproximateNow());
287   MaybeUpdateAckTimeout(kInstigateAck, 3);
288   // Delayed ack is scheduled.
289   CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
290 
291   RecordPacketReceipt(5, clock_.ApproximateNow());
292   MaybeUpdateAckTimeout(kInstigateAck, 5);
293   // Immediate ack is sent.
294   CheckAckTimeout(clock_.ApproximateNow());
295 
296   RecordPacketReceipt(6, clock_.ApproximateNow());
297   MaybeUpdateAckTimeout(kInstigateAck, 6);
298   // Delayed ack is scheduled.
299   CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
300 
301   RecordPacketReceipt(2, clock_.ApproximateNow());
302   MaybeUpdateAckTimeout(kInstigateAck, 2);
303   CheckAckTimeout(clock_.ApproximateNow());
304 
305   RecordPacketReceipt(1, clock_.ApproximateNow());
306   MaybeUpdateAckTimeout(kInstigateAck, 1);
307   // Should ack immediately, since this fills the last hole.
308   CheckAckTimeout(clock_.ApproximateNow());
309 
310   RecordPacketReceipt(7, clock_.ApproximateNow());
311   MaybeUpdateAckTimeout(kInstigateAck, 7);
312   // Delayed ack is scheduled, even though 4 is still missing.
313   CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
314 }
315 
TEST_F(QuicReceivedPacketManagerTest,OutOfOrderAckReceiptCausesNoAck)316 TEST_F(QuicReceivedPacketManagerTest, OutOfOrderAckReceiptCausesNoAck) {
317   EXPECT_FALSE(HasPendingAck());
318 
319   RecordPacketReceipt(2, clock_.ApproximateNow());
320   MaybeUpdateAckTimeout(!kInstigateAck, 2);
321   EXPECT_FALSE(HasPendingAck());
322 
323   RecordPacketReceipt(1, clock_.ApproximateNow());
324   MaybeUpdateAckTimeout(!kInstigateAck, 1);
325   EXPECT_FALSE(HasPendingAck());
326 }
327 
TEST_F(QuicReceivedPacketManagerTest,AckReceiptCausesAckSend)328 TEST_F(QuicReceivedPacketManagerTest, AckReceiptCausesAckSend) {
329   EXPECT_FALSE(HasPendingAck());
330 
331   RecordPacketReceipt(1, clock_.ApproximateNow());
332   MaybeUpdateAckTimeout(!kInstigateAck, 1);
333   EXPECT_FALSE(HasPendingAck());
334 
335   RecordPacketReceipt(2, clock_.ApproximateNow());
336   MaybeUpdateAckTimeout(!kInstigateAck, 2);
337   EXPECT_FALSE(HasPendingAck());
338 
339   RecordPacketReceipt(3, clock_.ApproximateNow());
340   MaybeUpdateAckTimeout(kInstigateAck, 3);
341   // Delayed ack is scheduled.
342   CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
343   clock_.AdvanceTime(kDelayedAckTime);
344   CheckAckTimeout(clock_.ApproximateNow());
345 
346   RecordPacketReceipt(4, clock_.ApproximateNow());
347   MaybeUpdateAckTimeout(!kInstigateAck, 4);
348   EXPECT_FALSE(HasPendingAck());
349 
350   RecordPacketReceipt(5, clock_.ApproximateNow());
351   MaybeUpdateAckTimeout(!kInstigateAck, 5);
352   EXPECT_FALSE(HasPendingAck());
353 }
354 
TEST_F(QuicReceivedPacketManagerTest,AckSentEveryNthPacket)355 TEST_F(QuicReceivedPacketManagerTest, AckSentEveryNthPacket) {
356   EXPECT_FALSE(HasPendingAck());
357   received_manager_.set_ack_frequency(3);
358 
359   // Receives packets 1 - 39.
360   for (size_t i = 1; i <= 39; ++i) {
361     RecordPacketReceipt(i, clock_.ApproximateNow());
362     MaybeUpdateAckTimeout(kInstigateAck, i);
363     if (i % 3 == 0) {
364       CheckAckTimeout(clock_.ApproximateNow());
365     } else {
366       CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
367     }
368   }
369 }
370 
TEST_F(QuicReceivedPacketManagerTest,AckDecimationReducesAcks)371 TEST_F(QuicReceivedPacketManagerTest, AckDecimationReducesAcks) {
372   EXPECT_FALSE(HasPendingAck());
373 
374   // Start ack decimation from 10th packet.
375   received_manager_.set_min_received_before_ack_decimation(10);
376 
377   // Receives packets 1 - 29.
378   for (size_t i = 1; i <= 29; ++i) {
379     RecordPacketReceipt(i, clock_.ApproximateNow());
380     MaybeUpdateAckTimeout(kInstigateAck, i);
381     if (i <= 10) {
382       // For packets 1-10, ack every 2 packets.
383       if (i % 2 == 0) {
384         CheckAckTimeout(clock_.ApproximateNow());
385       } else {
386         CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
387       }
388       continue;
389     }
390     // ack at 20.
391     if (i == 20) {
392       CheckAckTimeout(clock_.ApproximateNow());
393     } else {
394       CheckAckTimeout(clock_.ApproximateNow() + kMinRttMs * 0.25);
395     }
396   }
397 
398   // We now receive the 30th packet, and so we send an ack.
399   RecordPacketReceipt(30, clock_.ApproximateNow());
400   MaybeUpdateAckTimeout(kInstigateAck, 30);
401   CheckAckTimeout(clock_.ApproximateNow());
402 }
403 
TEST_F(QuicReceivedPacketManagerTest,SendDelayedAckDecimation)404 TEST_F(QuicReceivedPacketManagerTest, SendDelayedAckDecimation) {
405   EXPECT_FALSE(HasPendingAck());
406   // The ack time should be based on min_rtt * 1/4, since it's less than the
407   // default delayed ack time.
408   QuicTime ack_time = clock_.ApproximateNow() + kMinRttMs * 0.25;
409 
410   // Process all the packets in order so there aren't missing packets.
411   uint64_t kFirstDecimatedPacket = 101;
412   for (uint64_t i = 1; i < kFirstDecimatedPacket; ++i) {
413     RecordPacketReceipt(i, clock_.ApproximateNow());
414     MaybeUpdateAckTimeout(kInstigateAck, i);
415     if (i % 2 == 0) {
416       // Ack every 2 packets by default.
417       CheckAckTimeout(clock_.ApproximateNow());
418     } else {
419       CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
420     }
421   }
422 
423   RecordPacketReceipt(kFirstDecimatedPacket, clock_.ApproximateNow());
424   MaybeUpdateAckTimeout(kInstigateAck, kFirstDecimatedPacket);
425   CheckAckTimeout(ack_time);
426 
427   // The 10th received packet causes an ack to be sent.
428   for (uint64_t i = 1; i < 10; ++i) {
429     RecordPacketReceipt(kFirstDecimatedPacket + i, clock_.ApproximateNow());
430     MaybeUpdateAckTimeout(kInstigateAck, kFirstDecimatedPacket + i);
431   }
432   CheckAckTimeout(clock_.ApproximateNow());
433 }
434 
TEST_F(QuicReceivedPacketManagerTest,SendDelayedAckDecimationMin1ms)435 TEST_F(QuicReceivedPacketManagerTest, SendDelayedAckDecimationMin1ms) {
436   EXPECT_FALSE(HasPendingAck());
437   // Seed the min_rtt with a kAlarmGranularity signal.
438   rtt_stats_.UpdateRtt(kAlarmGranularity, QuicTime::Delta::Zero(),
439                        clock_.ApproximateNow());
440   // The ack time should be based on kAlarmGranularity, since the RTT is 1ms.
441   QuicTime ack_time = clock_.ApproximateNow() + kAlarmGranularity;
442 
443   // Process all the packets in order so there aren't missing packets.
444   uint64_t kFirstDecimatedPacket = 101;
445   for (uint64_t i = 1; i < kFirstDecimatedPacket; ++i) {
446     RecordPacketReceipt(i, clock_.ApproximateNow());
447     MaybeUpdateAckTimeout(kInstigateAck, i);
448     if (i % 2 == 0) {
449       // Ack every 2 packets by default.
450       CheckAckTimeout(clock_.ApproximateNow());
451     } else {
452       CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
453     }
454   }
455 
456   RecordPacketReceipt(kFirstDecimatedPacket, clock_.ApproximateNow());
457   MaybeUpdateAckTimeout(kInstigateAck, kFirstDecimatedPacket);
458   CheckAckTimeout(ack_time);
459 
460   // The 10th received packet causes an ack to be sent.
461   for (uint64_t i = 1; i < 10; ++i) {
462     RecordPacketReceipt(kFirstDecimatedPacket + i, clock_.ApproximateNow());
463     MaybeUpdateAckTimeout(kInstigateAck, kFirstDecimatedPacket + i);
464   }
465   CheckAckTimeout(clock_.ApproximateNow());
466 }
467 
TEST_F(QuicReceivedPacketManagerTest,SendDelayedAckDecimationUnlimitedAggregation)468 TEST_F(QuicReceivedPacketManagerTest,
469        SendDelayedAckDecimationUnlimitedAggregation) {
470   EXPECT_FALSE(HasPendingAck());
471   QuicConfig config;
472   QuicTagVector connection_options;
473   // No limit on the number of packets received before sending an ack.
474   connection_options.push_back(kAKDU);
475   config.SetConnectionOptionsToSend(connection_options);
476   received_manager_.SetFromConfig(config, Perspective::IS_CLIENT);
477 
478   // The ack time should be based on min_rtt/4, since it's less than the
479   // default delayed ack time.
480   QuicTime ack_time = clock_.ApproximateNow() + kMinRttMs * 0.25;
481 
482   // Process all the initial packets in order so there aren't missing packets.
483   uint64_t kFirstDecimatedPacket = 101;
484   for (uint64_t i = 1; i < kFirstDecimatedPacket; ++i) {
485     RecordPacketReceipt(i, clock_.ApproximateNow());
486     MaybeUpdateAckTimeout(kInstigateAck, i);
487     if (i % 2 == 0) {
488       // Ack every 2 packets by default.
489       CheckAckTimeout(clock_.ApproximateNow());
490     } else {
491       CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
492     }
493   }
494 
495   RecordPacketReceipt(kFirstDecimatedPacket, clock_.ApproximateNow());
496   MaybeUpdateAckTimeout(kInstigateAck, kFirstDecimatedPacket);
497   CheckAckTimeout(ack_time);
498 
499   // 18 packets will not cause an ack to be sent.  19 will because when
500   // stop waiting frames are in use, we ack every 20 packets no matter what.
501   for (int i = 1; i <= 18; ++i) {
502     RecordPacketReceipt(kFirstDecimatedPacket + i, clock_.ApproximateNow());
503     MaybeUpdateAckTimeout(kInstigateAck, kFirstDecimatedPacket + i);
504   }
505   CheckAckTimeout(ack_time);
506 }
507 
TEST_F(QuicReceivedPacketManagerTest,SendDelayedAckDecimationEighthRtt)508 TEST_F(QuicReceivedPacketManagerTest, SendDelayedAckDecimationEighthRtt) {
509   EXPECT_FALSE(HasPendingAck());
510   QuicReceivedPacketManagerPeer::SetAckDecimationDelay(&received_manager_,
511                                                        0.125);
512 
513   // The ack time should be based on min_rtt/8, since it's less than the
514   // default delayed ack time.
515   QuicTime ack_time = clock_.ApproximateNow() + kMinRttMs * 0.125;
516 
517   // Process all the packets in order so there aren't missing packets.
518   uint64_t kFirstDecimatedPacket = 101;
519   for (uint64_t i = 1; i < kFirstDecimatedPacket; ++i) {
520     RecordPacketReceipt(i, clock_.ApproximateNow());
521     MaybeUpdateAckTimeout(kInstigateAck, i);
522     if (i % 2 == 0) {
523       // Ack every 2 packets by default.
524       CheckAckTimeout(clock_.ApproximateNow());
525     } else {
526       CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
527     }
528   }
529 
530   RecordPacketReceipt(kFirstDecimatedPacket, clock_.ApproximateNow());
531   MaybeUpdateAckTimeout(kInstigateAck, kFirstDecimatedPacket);
532   CheckAckTimeout(ack_time);
533 
534   // The 10th received packet causes an ack to be sent.
535   for (uint64_t i = 1; i < 10; ++i) {
536     RecordPacketReceipt(kFirstDecimatedPacket + i, clock_.ApproximateNow());
537     MaybeUpdateAckTimeout(kInstigateAck, kFirstDecimatedPacket + i);
538   }
539   CheckAckTimeout(clock_.ApproximateNow());
540 }
541 
TEST_F(QuicReceivedPacketManagerTest,UpdateMaxAckDelayAndAckFrequencyFromAckFrequencyFrame)542 TEST_F(QuicReceivedPacketManagerTest,
543        UpdateMaxAckDelayAndAckFrequencyFromAckFrequencyFrame) {
544   EXPECT_FALSE(HasPendingAck());
545 
546   QuicAckFrequencyFrame frame;
547   frame.max_ack_delay = QuicTime::Delta::FromMilliseconds(10);
548   frame.packet_tolerance = 5;
549   received_manager_.OnAckFrequencyFrame(frame);
550 
551   for (int i = 1; i <= 50; ++i) {
552     RecordPacketReceipt(i, clock_.ApproximateNow());
553     MaybeUpdateAckTimeout(kInstigateAck, i);
554     if (i % frame.packet_tolerance == 0) {
555       CheckAckTimeout(clock_.ApproximateNow());
556     } else {
557       CheckAckTimeout(clock_.ApproximateNow() + frame.max_ack_delay);
558     }
559   }
560 }
561 
TEST_F(QuicReceivedPacketManagerTest,DisableOutOfOrderAckByIgnoreOrderFromAckFrequencyFrame)562 TEST_F(QuicReceivedPacketManagerTest,
563        DisableOutOfOrderAckByIgnoreOrderFromAckFrequencyFrame) {
564   EXPECT_FALSE(HasPendingAck());
565 
566   QuicAckFrequencyFrame frame;
567   frame.max_ack_delay = kDelayedAckTime;
568   frame.packet_tolerance = 2;
569   frame.ignore_order = true;
570   received_manager_.OnAckFrequencyFrame(frame);
571 
572   RecordPacketReceipt(4, clock_.ApproximateNow());
573   MaybeUpdateAckTimeout(kInstigateAck, 4);
574   CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
575   RecordPacketReceipt(5, clock_.ApproximateNow());
576   MaybeUpdateAckTimeout(kInstigateAck, 5);
577   // Immediate ack is sent as this is the 2nd packet of every two packets.
578   CheckAckTimeout(clock_.ApproximateNow());
579 
580   RecordPacketReceipt(3, clock_.ApproximateNow());
581   MaybeUpdateAckTimeout(kInstigateAck, 3);
582   // Don't ack as ignore_order is set by AckFrequencyFrame.
583   CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
584 
585   RecordPacketReceipt(2, clock_.ApproximateNow());
586   MaybeUpdateAckTimeout(kInstigateAck, 2);
587   // Immediate ack is sent as this is the 2nd packet of every two packets.
588   CheckAckTimeout(clock_.ApproximateNow());
589 
590   RecordPacketReceipt(1, clock_.ApproximateNow());
591   MaybeUpdateAckTimeout(kInstigateAck, 1);
592   // Don't ack as ignore_order is set by AckFrequencyFrame.
593   CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
594 }
595 
TEST_F(QuicReceivedPacketManagerTest,DisableMissingPaketsAckByIgnoreOrderFromAckFrequencyFrame)596 TEST_F(QuicReceivedPacketManagerTest,
597        DisableMissingPaketsAckByIgnoreOrderFromAckFrequencyFrame) {
598   EXPECT_FALSE(HasPendingAck());
599   QuicConfig config;
600   config.SetConnectionOptionsToSend({kAFFE});
601   received_manager_.SetFromConfig(config, Perspective::IS_CLIENT);
602 
603   QuicAckFrequencyFrame frame;
604   frame.max_ack_delay = kDelayedAckTime;
605   frame.packet_tolerance = 2;
606   frame.ignore_order = true;
607   received_manager_.OnAckFrequencyFrame(frame);
608 
609   RecordPacketReceipt(1, clock_.ApproximateNow());
610   MaybeUpdateAckTimeout(kInstigateAck, 1);
611   CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
612   RecordPacketReceipt(2, clock_.ApproximateNow());
613   MaybeUpdateAckTimeout(kInstigateAck, 2);
614   // Immediate ack is sent as this is the 2nd packet of every two packets.
615   CheckAckTimeout(clock_.ApproximateNow());
616 
617   RecordPacketReceipt(4, clock_.ApproximateNow());
618   MaybeUpdateAckTimeout(kInstigateAck, 4);
619   // Don't ack even if packet 3 is newly missing as ignore_order is set by
620   // AckFrequencyFrame.
621   CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
622 
623   RecordPacketReceipt(5, clock_.ApproximateNow());
624   MaybeUpdateAckTimeout(kInstigateAck, 5);
625   // Immediate ack is sent as this is the 2nd packet of every two packets.
626   CheckAckTimeout(clock_.ApproximateNow());
627 
628   RecordPacketReceipt(7, clock_.ApproximateNow());
629   MaybeUpdateAckTimeout(kInstigateAck, 7);
630   // Don't ack even if packet 6 is newly missing as ignore_order is set by
631   // AckFrequencyFrame.
632   CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
633 }
634 
TEST_F(QuicReceivedPacketManagerTest,AckDecimationDisabledWhenAckFrequencyFrameIsReceived)635 TEST_F(QuicReceivedPacketManagerTest,
636        AckDecimationDisabledWhenAckFrequencyFrameIsReceived) {
637   EXPECT_FALSE(HasPendingAck());
638 
639   QuicAckFrequencyFrame frame;
640   frame.max_ack_delay = kDelayedAckTime;
641   frame.packet_tolerance = 3;
642   frame.ignore_order = true;
643   received_manager_.OnAckFrequencyFrame(frame);
644 
645   // Process all the packets in order so there aren't missing packets.
646   uint64_t kFirstDecimatedPacket = 101;
647   uint64_t FiftyPacketsAfterAckDecimation = kFirstDecimatedPacket + 50;
648   for (uint64_t i = 1; i < FiftyPacketsAfterAckDecimation; ++i) {
649     RecordPacketReceipt(i, clock_.ApproximateNow());
650     MaybeUpdateAckTimeout(kInstigateAck, i);
651     if (i % 3 == 0) {
652       // Ack every 3 packets as decimation is disabled.
653       CheckAckTimeout(clock_.ApproximateNow());
654     } else {
655       // Ack at default delay as decimation is disabled.
656       CheckAckTimeout(clock_.ApproximateNow() + kDelayedAckTime);
657     }
658   }
659 }
660 
TEST_F(QuicReceivedPacketManagerTest,UpdateAckTimeoutOnPacketReceiptTime)661 TEST_F(QuicReceivedPacketManagerTest, UpdateAckTimeoutOnPacketReceiptTime) {
662   EXPECT_FALSE(HasPendingAck());
663 
664   // Received packets 3 and 4.
665   QuicTime packet_receipt_time3 = clock_.ApproximateNow();
666   // Packet 3 gets processed after 10ms.
667   clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(10));
668   RecordPacketReceipt(3, packet_receipt_time3);
669   received_manager_.MaybeUpdateAckTimeout(
670       kInstigateAck, QuicPacketNumber(3),
671       /*last_packet_receipt_time=*/packet_receipt_time3,
672       clock_.ApproximateNow(), &rtt_stats_);
673   // Make sure ACK timeout is based on receipt time.
674   CheckAckTimeout(packet_receipt_time3 + kDelayedAckTime);
675 
676   RecordPacketReceipt(4, clock_.ApproximateNow());
677   MaybeUpdateAckTimeout(kInstigateAck, 4);
678   // Immediate ack is sent.
679   CheckAckTimeout(clock_.ApproximateNow());
680 }
681 
TEST_F(QuicReceivedPacketManagerTest,UpdateAckTimeoutOnPacketReceiptTimeLongerQueuingTime)682 TEST_F(QuicReceivedPacketManagerTest,
683        UpdateAckTimeoutOnPacketReceiptTimeLongerQueuingTime) {
684   EXPECT_FALSE(HasPendingAck());
685 
686   // Received packets 3 and 4.
687   QuicTime packet_receipt_time3 = clock_.ApproximateNow();
688   // Packet 3 gets processed after 100ms.
689   clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(100));
690   RecordPacketReceipt(3, packet_receipt_time3);
691   received_manager_.MaybeUpdateAckTimeout(
692       kInstigateAck, QuicPacketNumber(3),
693       /*last_packet_receipt_time=*/packet_receipt_time3,
694       clock_.ApproximateNow(), &rtt_stats_);
695   // Given 100ms > ack delay, verify immediate ACK.
696   CheckAckTimeout(clock_.ApproximateNow());
697 }
698 
TEST_F(QuicReceivedPacketManagerTest,CountEcnPackets)699 TEST_F(QuicReceivedPacketManagerTest, CountEcnPackets) {
700   EXPECT_FALSE(HasPendingAck());
701   RecordPacketReceipt(3, QuicTime::Zero(), ECN_NOT_ECT);
702   RecordPacketReceipt(4, QuicTime::Zero(), ECN_ECT0);
703   RecordPacketReceipt(5, QuicTime::Zero(), ECN_ECT1);
704   RecordPacketReceipt(6, QuicTime::Zero(), ECN_CE);
705   QuicFrame ack = received_manager_.GetUpdatedAckFrame(QuicTime::Zero());
706   EXPECT_TRUE(ack.ack_frame->ecn_counters.has_value());
707   EXPECT_EQ(ack.ack_frame->ecn_counters->ect0, 1);
708   EXPECT_EQ(ack.ack_frame->ecn_counters->ect1, 1);
709   EXPECT_EQ(ack.ack_frame->ecn_counters->ce, 1);
710 }
711 
712 }  // namespace
713 }  // namespace test
714 }  // namespace quic
715