1 // Copyright 2014 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 "net/third_party/quiche/src/quic/core/quic_unacked_packet_map.h"
6 #include <limits>
7 
8 #include "net/third_party/quiche/src/quic/core/frames/quic_stream_frame.h"
9 #include "net/third_party/quiche/src/quic/core/quic_transmission_info.h"
10 #include "net/third_party/quiche/src/quic/core/quic_utils.h"
11 #include "net/third_party/quiche/src/quic/platform/api/quic_test.h"
12 #include "net/third_party/quiche/src/quic/test_tools/quic_test_utils.h"
13 #include "net/third_party/quiche/src/quic/test_tools/quic_unacked_packet_map_peer.h"
14 #include "net/third_party/quiche/src/common/platform/api/quiche_arraysize.h"
15 
16 using testing::_;
17 using testing::Return;
18 using testing::StrictMock;
19 
20 namespace quic {
21 namespace test {
22 namespace {
23 
24 // Default packet length.
25 const uint32_t kDefaultLength = 1000;
26 
27 class QuicUnackedPacketMapTest : public QuicTestWithParam<Perspective> {
28  protected:
QuicUnackedPacketMapTest()29   QuicUnackedPacketMapTest()
30       : unacked_packets_(GetParam()),
31         now_(QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(1000)) {
32     unacked_packets_.SetSessionNotifier(&notifier_);
33     EXPECT_CALL(notifier_, IsFrameOutstanding(_)).WillRepeatedly(Return(true));
34     EXPECT_CALL(notifier_, OnStreamFrameRetransmitted(_))
35         .Times(testing::AnyNumber());
36   }
37 
~QuicUnackedPacketMapTest()38   ~QuicUnackedPacketMapTest() override {}
39 
CreateRetransmittablePacket(uint64_t packet_number)40   SerializedPacket CreateRetransmittablePacket(uint64_t packet_number) {
41     return CreateRetransmittablePacketForStream(
42         packet_number, QuicUtils::GetFirstBidirectionalStreamId(
43                            CurrentSupportedVersions()[0].transport_version,
44                            Perspective::IS_CLIENT));
45   }
46 
CreateRetransmittablePacketForStream(uint64_t packet_number,QuicStreamId stream_id)47   SerializedPacket CreateRetransmittablePacketForStream(
48       uint64_t packet_number,
49       QuicStreamId stream_id) {
50     SerializedPacket packet(QuicPacketNumber(packet_number),
51                             PACKET_1BYTE_PACKET_NUMBER, nullptr, kDefaultLength,
52                             false, false);
53     QuicStreamFrame frame;
54     frame.stream_id = stream_id;
55     packet.retransmittable_frames.push_back(QuicFrame(frame));
56     return packet;
57   }
58 
CreateNonRetransmittablePacket(uint64_t packet_number)59   SerializedPacket CreateNonRetransmittablePacket(uint64_t packet_number) {
60     return SerializedPacket(QuicPacketNumber(packet_number),
61                             PACKET_1BYTE_PACKET_NUMBER, nullptr, kDefaultLength,
62                             false, false);
63   }
64 
VerifyInFlightPackets(uint64_t * packets,size_t num_packets)65   void VerifyInFlightPackets(uint64_t* packets, size_t num_packets) {
66     unacked_packets_.RemoveObsoletePackets();
67     if (num_packets == 0) {
68       EXPECT_FALSE(unacked_packets_.HasInFlightPackets());
69       EXPECT_FALSE(unacked_packets_.HasMultipleInFlightPackets());
70       return;
71     }
72     if (num_packets == 1) {
73       EXPECT_TRUE(unacked_packets_.HasInFlightPackets());
74       EXPECT_FALSE(unacked_packets_.HasMultipleInFlightPackets());
75       ASSERT_TRUE(unacked_packets_.IsUnacked(QuicPacketNumber(packets[0])));
76       EXPECT_TRUE(
77           unacked_packets_.GetTransmissionInfo(QuicPacketNumber(packets[0]))
78               .in_flight);
79     }
80     for (size_t i = 0; i < num_packets; ++i) {
81       ASSERT_TRUE(unacked_packets_.IsUnacked(QuicPacketNumber(packets[i])));
82       EXPECT_TRUE(
83           unacked_packets_.GetTransmissionInfo(QuicPacketNumber(packets[i]))
84               .in_flight);
85     }
86     size_t in_flight_count = 0;
87     for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
88          it != unacked_packets_.end(); ++it) {
89       if (it->in_flight) {
90         ++in_flight_count;
91       }
92     }
93     EXPECT_EQ(num_packets, in_flight_count);
94   }
95 
VerifyUnackedPackets(uint64_t * packets,size_t num_packets)96   void VerifyUnackedPackets(uint64_t* packets, size_t num_packets) {
97     unacked_packets_.RemoveObsoletePackets();
98     if (num_packets == 0) {
99       EXPECT_TRUE(unacked_packets_.empty());
100       EXPECT_FALSE(unacked_packets_.HasUnackedRetransmittableFrames());
101       return;
102     }
103     EXPECT_FALSE(unacked_packets_.empty());
104     for (size_t i = 0; i < num_packets; ++i) {
105       EXPECT_TRUE(unacked_packets_.IsUnacked(QuicPacketNumber(packets[i])))
106           << packets[i];
107     }
108     EXPECT_EQ(num_packets, unacked_packets_.GetNumUnackedPacketsDebugOnly());
109   }
110 
VerifyRetransmittablePackets(uint64_t * packets,size_t num_packets)111   void VerifyRetransmittablePackets(uint64_t* packets, size_t num_packets) {
112     unacked_packets_.RemoveObsoletePackets();
113     size_t num_retransmittable_packets = 0;
114     for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
115          it != unacked_packets_.end(); ++it) {
116       if (unacked_packets_.HasRetransmittableFrames(*it)) {
117         ++num_retransmittable_packets;
118       }
119     }
120     EXPECT_EQ(num_packets, num_retransmittable_packets);
121     for (size_t i = 0; i < num_packets; ++i) {
122       EXPECT_TRUE(unacked_packets_.HasRetransmittableFrames(
123           QuicPacketNumber(packets[i])))
124           << " packets[" << i << "]:" << packets[i];
125     }
126   }
127 
UpdatePacketState(uint64_t packet_number,SentPacketState state)128   void UpdatePacketState(uint64_t packet_number, SentPacketState state) {
129     unacked_packets_
130         .GetMutableTransmissionInfo(QuicPacketNumber(packet_number))
131         ->state = state;
132   }
133 
RetransmitAndSendPacket(uint64_t old_packet_number,uint64_t new_packet_number,TransmissionType transmission_type)134   void RetransmitAndSendPacket(uint64_t old_packet_number,
135                                uint64_t new_packet_number,
136                                TransmissionType transmission_type) {
137     DCHECK(unacked_packets_.HasRetransmittableFrames(
138         QuicPacketNumber(old_packet_number)));
139     QuicTransmissionInfo* info = unacked_packets_.GetMutableTransmissionInfo(
140         QuicPacketNumber(old_packet_number));
141     QuicStreamId stream_id = QuicUtils::GetFirstBidirectionalStreamId(
142         CurrentSupportedVersions()[0].transport_version,
143         Perspective::IS_CLIENT);
144     for (const auto& frame : info->retransmittable_frames) {
145       if (frame.type == STREAM_FRAME) {
146         stream_id = frame.stream_frame.stream_id;
147         break;
148       }
149     }
150     UpdatePacketState(
151         old_packet_number,
152         QuicUtils::RetransmissionTypeToPacketState(transmission_type));
153     info->retransmission = QuicPacketNumber(new_packet_number);
154     SerializedPacket packet(
155         CreateRetransmittablePacketForStream(new_packet_number, stream_id));
156     unacked_packets_.AddSentPacket(&packet, transmission_type, now_, true);
157   }
158   QuicUnackedPacketMap unacked_packets_;
159   QuicTime now_;
160   StrictMock<MockSessionNotifier> notifier_;
161 };
162 
163 INSTANTIATE_TEST_SUITE_P(Tests,
164                          QuicUnackedPacketMapTest,
165                          ::testing::ValuesIn({Perspective::IS_CLIENT,
166                                               Perspective::IS_SERVER}),
167                          ::testing::PrintToStringParamName());
168 
TEST_P(QuicUnackedPacketMapTest,RttOnly)169 TEST_P(QuicUnackedPacketMapTest, RttOnly) {
170   // Acks are only tracked for RTT measurement purposes.
171   SerializedPacket packet(CreateNonRetransmittablePacket(1));
172   unacked_packets_.AddSentPacket(&packet, NOT_RETRANSMISSION, now_, false);
173 
174   uint64_t unacked[] = {1};
175   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
176   VerifyInFlightPackets(nullptr, 0);
177   VerifyRetransmittablePackets(nullptr, 0);
178 
179   unacked_packets_.IncreaseLargestAcked(QuicPacketNumber(1));
180   VerifyUnackedPackets(nullptr, 0);
181   VerifyInFlightPackets(nullptr, 0);
182   VerifyRetransmittablePackets(nullptr, 0);
183 }
184 
TEST_P(QuicUnackedPacketMapTest,RetransmittableInflightAndRtt)185 TEST_P(QuicUnackedPacketMapTest, RetransmittableInflightAndRtt) {
186   // Simulate a retransmittable packet being sent and acked.
187   SerializedPacket packet(CreateRetransmittablePacket(1));
188   unacked_packets_.AddSentPacket(&packet, NOT_RETRANSMISSION, now_, true);
189 
190   uint64_t unacked[] = {1};
191   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
192   VerifyInFlightPackets(unacked, QUICHE_ARRAYSIZE(unacked));
193   VerifyRetransmittablePackets(unacked, QUICHE_ARRAYSIZE(unacked));
194 
195   unacked_packets_.RemoveRetransmittability(QuicPacketNumber(1));
196   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
197   VerifyInFlightPackets(unacked, QUICHE_ARRAYSIZE(unacked));
198   VerifyRetransmittablePackets(nullptr, 0);
199 
200   unacked_packets_.IncreaseLargestAcked(QuicPacketNumber(1));
201   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
202   VerifyInFlightPackets(unacked, QUICHE_ARRAYSIZE(unacked));
203   VerifyRetransmittablePackets(nullptr, 0);
204 
205   unacked_packets_.RemoveFromInFlight(QuicPacketNumber(1));
206   VerifyUnackedPackets(nullptr, 0);
207   VerifyInFlightPackets(nullptr, 0);
208   VerifyRetransmittablePackets(nullptr, 0);
209 }
210 
TEST_P(QuicUnackedPacketMapTest,StopRetransmission)211 TEST_P(QuicUnackedPacketMapTest, StopRetransmission) {
212   const QuicStreamId stream_id = 2;
213   SerializedPacket packet(CreateRetransmittablePacketForStream(1, stream_id));
214   unacked_packets_.AddSentPacket(&packet, NOT_RETRANSMISSION, now_, true);
215 
216   uint64_t unacked[] = {1};
217   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
218   VerifyInFlightPackets(unacked, QUICHE_ARRAYSIZE(unacked));
219   uint64_t retransmittable[] = {1};
220   VerifyRetransmittablePackets(retransmittable,
221                                QUICHE_ARRAYSIZE(retransmittable));
222 
223   EXPECT_CALL(notifier_, IsFrameOutstanding(_)).WillRepeatedly(Return(false));
224   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
225   VerifyInFlightPackets(unacked, QUICHE_ARRAYSIZE(unacked));
226   VerifyRetransmittablePackets(nullptr, 0);
227 }
228 
TEST_P(QuicUnackedPacketMapTest,StopRetransmissionOnOtherStream)229 TEST_P(QuicUnackedPacketMapTest, StopRetransmissionOnOtherStream) {
230   const QuicStreamId stream_id = 2;
231   SerializedPacket packet(CreateRetransmittablePacketForStream(1, stream_id));
232   unacked_packets_.AddSentPacket(&packet, NOT_RETRANSMISSION, now_, true);
233 
234   uint64_t unacked[] = {1};
235   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
236   VerifyInFlightPackets(unacked, QUICHE_ARRAYSIZE(unacked));
237   uint64_t retransmittable[] = {1};
238   VerifyRetransmittablePackets(retransmittable,
239                                QUICHE_ARRAYSIZE(retransmittable));
240 
241   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
242   VerifyInFlightPackets(unacked, QUICHE_ARRAYSIZE(unacked));
243   VerifyRetransmittablePackets(retransmittable,
244                                QUICHE_ARRAYSIZE(retransmittable));
245 }
246 
TEST_P(QuicUnackedPacketMapTest,StopRetransmissionAfterRetransmission)247 TEST_P(QuicUnackedPacketMapTest, StopRetransmissionAfterRetransmission) {
248   const QuicStreamId stream_id = 2;
249   SerializedPacket packet1(CreateRetransmittablePacketForStream(1, stream_id));
250   unacked_packets_.AddSentPacket(&packet1, NOT_RETRANSMISSION, now_, true);
251   RetransmitAndSendPacket(1, 2, LOSS_RETRANSMISSION);
252 
253   uint64_t unacked[] = {1, 2};
254   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
255   VerifyInFlightPackets(unacked, QUICHE_ARRAYSIZE(unacked));
256   std::vector<uint64_t> retransmittable = {1, 2};
257   VerifyRetransmittablePackets(&retransmittable[0], retransmittable.size());
258 
259   EXPECT_CALL(notifier_, IsFrameOutstanding(_)).WillRepeatedly(Return(false));
260   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
261   VerifyInFlightPackets(unacked, QUICHE_ARRAYSIZE(unacked));
262   VerifyRetransmittablePackets(nullptr, 0);
263 }
264 
TEST_P(QuicUnackedPacketMapTest,RetransmittedPacket)265 TEST_P(QuicUnackedPacketMapTest, RetransmittedPacket) {
266   // Simulate a retransmittable packet being sent, retransmitted, and the first
267   // transmission being acked.
268   SerializedPacket packet1(CreateRetransmittablePacket(1));
269   unacked_packets_.AddSentPacket(&packet1, NOT_RETRANSMISSION, now_, true);
270   RetransmitAndSendPacket(1, 2, LOSS_RETRANSMISSION);
271 
272   uint64_t unacked[] = {1, 2};
273   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
274   VerifyInFlightPackets(unacked, QUICHE_ARRAYSIZE(unacked));
275   std::vector<uint64_t> retransmittable = {1, 2};
276   VerifyRetransmittablePackets(&retransmittable[0], retransmittable.size());
277 
278   EXPECT_CALL(notifier_, IsFrameOutstanding(_)).WillRepeatedly(Return(false));
279   unacked_packets_.RemoveRetransmittability(QuicPacketNumber(1));
280   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
281   VerifyInFlightPackets(unacked, QUICHE_ARRAYSIZE(unacked));
282   VerifyRetransmittablePackets(nullptr, 0);
283 
284   unacked_packets_.IncreaseLargestAcked(QuicPacketNumber(2));
285   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
286   VerifyInFlightPackets(unacked, QUICHE_ARRAYSIZE(unacked));
287   VerifyRetransmittablePackets(nullptr, 0);
288 
289   unacked_packets_.RemoveFromInFlight(QuicPacketNumber(2));
290   uint64_t unacked2[] = {1};
291   VerifyUnackedPackets(unacked2, QUICHE_ARRAYSIZE(unacked2));
292   VerifyInFlightPackets(unacked2, QUICHE_ARRAYSIZE(unacked2));
293   VerifyRetransmittablePackets(nullptr, 0);
294 
295   unacked_packets_.RemoveFromInFlight(QuicPacketNumber(1));
296   VerifyUnackedPackets(nullptr, 0);
297   VerifyInFlightPackets(nullptr, 0);
298   VerifyRetransmittablePackets(nullptr, 0);
299 }
300 
TEST_P(QuicUnackedPacketMapTest,RetransmitThreeTimes)301 TEST_P(QuicUnackedPacketMapTest, RetransmitThreeTimes) {
302   // Simulate a retransmittable packet being sent and retransmitted twice.
303   SerializedPacket packet1(CreateRetransmittablePacket(1));
304   unacked_packets_.AddSentPacket(&packet1, NOT_RETRANSMISSION, now_, true);
305   SerializedPacket packet2(CreateRetransmittablePacket(2));
306   unacked_packets_.AddSentPacket(&packet2, NOT_RETRANSMISSION, now_, true);
307 
308   uint64_t unacked[] = {1, 2};
309   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
310   VerifyInFlightPackets(unacked, QUICHE_ARRAYSIZE(unacked));
311   uint64_t retransmittable[] = {1, 2};
312   VerifyRetransmittablePackets(retransmittable,
313                                QUICHE_ARRAYSIZE(retransmittable));
314 
315   // Early retransmit 1 as 3 and send new data as 4.
316   unacked_packets_.IncreaseLargestAcked(QuicPacketNumber(2));
317   unacked_packets_.RemoveFromInFlight(QuicPacketNumber(2));
318   unacked_packets_.RemoveRetransmittability(QuicPacketNumber(2));
319   unacked_packets_.RemoveFromInFlight(QuicPacketNumber(1));
320   RetransmitAndSendPacket(1, 3, LOSS_RETRANSMISSION);
321   SerializedPacket packet4(CreateRetransmittablePacket(4));
322   unacked_packets_.AddSentPacket(&packet4, NOT_RETRANSMISSION, now_, true);
323 
324   uint64_t unacked2[] = {1, 3, 4};
325   VerifyUnackedPackets(unacked2, QUICHE_ARRAYSIZE(unacked2));
326   uint64_t pending2[] = {3, 4};
327   VerifyInFlightPackets(pending2, QUICHE_ARRAYSIZE(pending2));
328   std::vector<uint64_t> retransmittable2 = {1, 3, 4};
329   VerifyRetransmittablePackets(&retransmittable2[0], retransmittable2.size());
330 
331   // Early retransmit 3 (formerly 1) as 5, and remove 1 from unacked.
332   unacked_packets_.IncreaseLargestAcked(QuicPacketNumber(4));
333   unacked_packets_.RemoveFromInFlight(QuicPacketNumber(4));
334   unacked_packets_.RemoveRetransmittability(QuicPacketNumber(4));
335   RetransmitAndSendPacket(3, 5, LOSS_RETRANSMISSION);
336   SerializedPacket packet6(CreateRetransmittablePacket(6));
337   unacked_packets_.AddSentPacket(&packet6, NOT_RETRANSMISSION, now_, true);
338 
339   std::vector<uint64_t> unacked3 = {3, 5, 6};
340   std::vector<uint64_t> retransmittable3 = {3, 5, 6};
341   VerifyUnackedPackets(&unacked3[0], unacked3.size());
342   VerifyRetransmittablePackets(&retransmittable3[0], retransmittable3.size());
343   uint64_t pending3[] = {3, 5, 6};
344   VerifyInFlightPackets(pending3, QUICHE_ARRAYSIZE(pending3));
345 
346   // Early retransmit 5 as 7 and ensure in flight packet 3 is not removed.
347   unacked_packets_.IncreaseLargestAcked(QuicPacketNumber(6));
348   unacked_packets_.RemoveFromInFlight(QuicPacketNumber(6));
349   unacked_packets_.RemoveRetransmittability(QuicPacketNumber(6));
350   RetransmitAndSendPacket(5, 7, LOSS_RETRANSMISSION);
351 
352   std::vector<uint64_t> unacked4 = {3, 5, 7};
353   std::vector<uint64_t> retransmittable4 = {3, 5, 7};
354   VerifyUnackedPackets(&unacked4[0], unacked4.size());
355   VerifyRetransmittablePackets(&retransmittable4[0], retransmittable4.size());
356   uint64_t pending4[] = {3, 5, 7};
357   VerifyInFlightPackets(pending4, QUICHE_ARRAYSIZE(pending4));
358 
359   // Remove the older two transmissions from in flight.
360   unacked_packets_.RemoveFromInFlight(QuicPacketNumber(3));
361   unacked_packets_.RemoveFromInFlight(QuicPacketNumber(5));
362   uint64_t pending5[] = {7};
363   VerifyInFlightPackets(pending5, QUICHE_ARRAYSIZE(pending5));
364 }
365 
TEST_P(QuicUnackedPacketMapTest,RetransmitFourTimes)366 TEST_P(QuicUnackedPacketMapTest, RetransmitFourTimes) {
367   // Simulate a retransmittable packet being sent and retransmitted twice.
368   SerializedPacket packet1(CreateRetransmittablePacket(1));
369   unacked_packets_.AddSentPacket(&packet1, NOT_RETRANSMISSION, now_, true);
370   SerializedPacket packet2(CreateRetransmittablePacket(2));
371   unacked_packets_.AddSentPacket(&packet2, NOT_RETRANSMISSION, now_, true);
372 
373   uint64_t unacked[] = {1, 2};
374   VerifyUnackedPackets(unacked, QUICHE_ARRAYSIZE(unacked));
375   VerifyInFlightPackets(unacked, QUICHE_ARRAYSIZE(unacked));
376   uint64_t retransmittable[] = {1, 2};
377   VerifyRetransmittablePackets(retransmittable,
378                                QUICHE_ARRAYSIZE(retransmittable));
379 
380   // Early retransmit 1 as 3.
381   unacked_packets_.IncreaseLargestAcked(QuicPacketNumber(2));
382   unacked_packets_.RemoveFromInFlight(QuicPacketNumber(2));
383   unacked_packets_.RemoveRetransmittability(QuicPacketNumber(2));
384   unacked_packets_.RemoveFromInFlight(QuicPacketNumber(1));
385   RetransmitAndSendPacket(1, 3, LOSS_RETRANSMISSION);
386 
387   uint64_t unacked2[] = {1, 3};
388   VerifyUnackedPackets(unacked2, QUICHE_ARRAYSIZE(unacked2));
389   uint64_t pending2[] = {3};
390   VerifyInFlightPackets(pending2, QUICHE_ARRAYSIZE(pending2));
391   std::vector<uint64_t> retransmittable2 = {1, 3};
392   VerifyRetransmittablePackets(&retransmittable2[0], retransmittable2.size());
393 
394   // TLP 3 (formerly 1) as 4, and don't remove 1 from unacked.
395   RetransmitAndSendPacket(3, 4, TLP_RETRANSMISSION);
396   SerializedPacket packet5(CreateRetransmittablePacket(5));
397   unacked_packets_.AddSentPacket(&packet5, NOT_RETRANSMISSION, now_, true);
398 
399   uint64_t unacked3[] = {1, 3, 4, 5};
400   VerifyUnackedPackets(unacked3, QUICHE_ARRAYSIZE(unacked3));
401   uint64_t pending3[] = {3, 4, 5};
402   VerifyInFlightPackets(pending3, QUICHE_ARRAYSIZE(pending3));
403   std::vector<uint64_t> retransmittable3 = {1, 3, 4, 5};
404   VerifyRetransmittablePackets(&retransmittable3[0], retransmittable3.size());
405 
406   // Early retransmit 4 as 6 and ensure in flight packet 3 is removed.
407   unacked_packets_.IncreaseLargestAcked(QuicPacketNumber(5));
408   unacked_packets_.RemoveFromInFlight(QuicPacketNumber(5));
409   unacked_packets_.RemoveRetransmittability(QuicPacketNumber(5));
410   unacked_packets_.RemoveFromInFlight(QuicPacketNumber(3));
411   unacked_packets_.RemoveFromInFlight(QuicPacketNumber(4));
412   RetransmitAndSendPacket(4, 6, LOSS_RETRANSMISSION);
413 
414   std::vector<uint64_t> unacked4 = {4, 6};
415   VerifyUnackedPackets(&unacked4[0], unacked4.size());
416   uint64_t pending4[] = {6};
417   VerifyInFlightPackets(pending4, QUICHE_ARRAYSIZE(pending4));
418   std::vector<uint64_t> retransmittable4 = {4, 6};
419   VerifyRetransmittablePackets(&retransmittable4[0], retransmittable4.size());
420 }
421 
TEST_P(QuicUnackedPacketMapTest,SendWithGap)422 TEST_P(QuicUnackedPacketMapTest, SendWithGap) {
423   // Simulate a retransmittable packet being sent, retransmitted, and the first
424   // transmission being acked.
425   SerializedPacket packet1(CreateRetransmittablePacket(1));
426   unacked_packets_.AddSentPacket(&packet1, NOT_RETRANSMISSION, now_, true);
427   SerializedPacket packet3(CreateRetransmittablePacket(3));
428   unacked_packets_.AddSentPacket(&packet3, NOT_RETRANSMISSION, now_, true);
429   RetransmitAndSendPacket(3, 5, LOSS_RETRANSMISSION);
430 
431   EXPECT_EQ(QuicPacketNumber(1u), unacked_packets_.GetLeastUnacked());
432   EXPECT_TRUE(unacked_packets_.IsUnacked(QuicPacketNumber(1)));
433   EXPECT_FALSE(unacked_packets_.IsUnacked(QuicPacketNumber(2)));
434   EXPECT_TRUE(unacked_packets_.IsUnacked(QuicPacketNumber(3)));
435   EXPECT_FALSE(unacked_packets_.IsUnacked(QuicPacketNumber(4)));
436   EXPECT_TRUE(unacked_packets_.IsUnacked(QuicPacketNumber(5)));
437   EXPECT_EQ(QuicPacketNumber(5u), unacked_packets_.largest_sent_packet());
438 }
439 
TEST_P(QuicUnackedPacketMapTest,AggregateContiguousAckedStreamFrames)440 TEST_P(QuicUnackedPacketMapTest, AggregateContiguousAckedStreamFrames) {
441   testing::InSequence s;
442   EXPECT_CALL(notifier_, OnFrameAcked(_, _, _)).Times(0);
443   unacked_packets_.NotifyAggregatedStreamFrameAcked(QuicTime::Delta::Zero());
444 
445   QuicTransmissionInfo info1;
446   QuicStreamFrame stream_frame1(3, false, 0, 100);
447   info1.retransmittable_frames.push_back(QuicFrame(stream_frame1));
448 
449   QuicTransmissionInfo info2;
450   QuicStreamFrame stream_frame2(3, false, 100, 100);
451   info2.retransmittable_frames.push_back(QuicFrame(stream_frame2));
452 
453   QuicTransmissionInfo info3;
454   QuicStreamFrame stream_frame3(3, false, 200, 100);
455   info3.retransmittable_frames.push_back(QuicFrame(stream_frame3));
456 
457   QuicTransmissionInfo info4;
458   QuicStreamFrame stream_frame4(3, true, 300, 0);
459   info4.retransmittable_frames.push_back(QuicFrame(stream_frame4));
460 
461   // Verify stream frames are aggregated.
462   EXPECT_CALL(notifier_, OnFrameAcked(_, _, _)).Times(0);
463   unacked_packets_.MaybeAggregateAckedStreamFrame(
464       info1, QuicTime::Delta::Zero(), QuicTime::Zero());
465   EXPECT_CALL(notifier_, OnFrameAcked(_, _, _)).Times(0);
466   unacked_packets_.MaybeAggregateAckedStreamFrame(
467       info2, QuicTime::Delta::Zero(), QuicTime::Zero());
468   EXPECT_CALL(notifier_, OnFrameAcked(_, _, _)).Times(0);
469   unacked_packets_.MaybeAggregateAckedStreamFrame(
470       info3, QuicTime::Delta::Zero(), QuicTime::Zero());
471 
472   // Verify aggregated stream frame gets acked since fin is acked.
473   EXPECT_CALL(notifier_, OnFrameAcked(_, _, _)).Times(1);
474   unacked_packets_.MaybeAggregateAckedStreamFrame(
475       info4, QuicTime::Delta::Zero(), QuicTime::Zero());
476 }
477 
478 // Regression test for b/112930090.
TEST_P(QuicUnackedPacketMapTest,CannotAggregateIfDataLengthOverflow)479 TEST_P(QuicUnackedPacketMapTest, CannotAggregateIfDataLengthOverflow) {
480   QuicByteCount kMaxAggregatedDataLength =
481       std::numeric_limits<decltype(QuicStreamFrame().data_length)>::max();
482   QuicStreamId stream_id = 2;
483 
484   // acked_stream_length=512 covers the case where a frame will cause the
485   // aggregated frame length to be exactly 64K.
486   // acked_stream_length=1300 covers the case where a frame will cause the
487   // aggregated frame length to exceed 64K.
488   for (const QuicPacketLength acked_stream_length : {512, 1300}) {
489     ++stream_id;
490     QuicStreamOffset offset = 0;
491     // Expected length of the aggregated stream frame.
492     QuicByteCount aggregated_data_length = 0;
493 
494     while (offset < 1e6) {
495       QuicTransmissionInfo info;
496       QuicStreamFrame stream_frame(stream_id, false, offset,
497                                    acked_stream_length);
498       info.retransmittable_frames.push_back(QuicFrame(stream_frame));
499 
500       const QuicStreamFrame& aggregated_stream_frame =
501           QuicUnackedPacketMapPeer::GetAggregatedStreamFrame(unacked_packets_);
502       if (aggregated_stream_frame.data_length + acked_stream_length <=
503           kMaxAggregatedDataLength) {
504         // Verify the acked stream frame can be aggregated.
505         EXPECT_CALL(notifier_, OnFrameAcked(_, _, _)).Times(0);
506         unacked_packets_.MaybeAggregateAckedStreamFrame(
507             info, QuicTime::Delta::Zero(), QuicTime::Zero());
508         aggregated_data_length += acked_stream_length;
509         testing::Mock::VerifyAndClearExpectations(&notifier_);
510       } else {
511         // Verify the acked stream frame cannot be aggregated because
512         // data_length is overflow.
513         EXPECT_CALL(notifier_, OnFrameAcked(_, _, _)).Times(1);
514         unacked_packets_.MaybeAggregateAckedStreamFrame(
515             info, QuicTime::Delta::Zero(), QuicTime::Zero());
516         aggregated_data_length = acked_stream_length;
517         testing::Mock::VerifyAndClearExpectations(&notifier_);
518       }
519 
520       EXPECT_EQ(aggregated_data_length, aggregated_stream_frame.data_length);
521       offset += acked_stream_length;
522     }
523 
524     // Ack the last frame of the stream.
525     QuicTransmissionInfo info;
526     QuicStreamFrame stream_frame(stream_id, true, offset, acked_stream_length);
527     info.retransmittable_frames.push_back(QuicFrame(stream_frame));
528     EXPECT_CALL(notifier_, OnFrameAcked(_, _, _)).Times(1);
529     unacked_packets_.MaybeAggregateAckedStreamFrame(
530         info, QuicTime::Delta::Zero(), QuicTime::Zero());
531     testing::Mock::VerifyAndClearExpectations(&notifier_);
532   }
533 }
534 
TEST_P(QuicUnackedPacketMapTest,CannotAggregateAckedControlFrames)535 TEST_P(QuicUnackedPacketMapTest, CannotAggregateAckedControlFrames) {
536   testing::InSequence s;
537   QuicWindowUpdateFrame window_update(1, 5, 100);
538   QuicStreamFrame stream_frame1(3, false, 0, 100);
539   QuicStreamFrame stream_frame2(3, false, 100, 100);
540   QuicBlockedFrame blocked(2, 5);
541   QuicGoAwayFrame go_away(3, QUIC_PEER_GOING_AWAY, 5, "Going away.");
542 
543   QuicTransmissionInfo info1;
544   info1.retransmittable_frames.push_back(QuicFrame(&window_update));
545   info1.retransmittable_frames.push_back(QuicFrame(stream_frame1));
546   info1.retransmittable_frames.push_back(QuicFrame(stream_frame2));
547 
548   QuicTransmissionInfo info2;
549   info2.retransmittable_frames.push_back(QuicFrame(&blocked));
550   info2.retransmittable_frames.push_back(QuicFrame(&go_away));
551 
552   // Verify 2 contiguous stream frames are aggregated.
553   EXPECT_CALL(notifier_, OnFrameAcked(_, _, _)).Times(1);
554   unacked_packets_.MaybeAggregateAckedStreamFrame(
555       info1, QuicTime::Delta::Zero(), QuicTime::Zero());
556   // Verify aggregated stream frame gets acked.
557   EXPECT_CALL(notifier_, OnFrameAcked(_, _, _)).Times(3);
558   unacked_packets_.MaybeAggregateAckedStreamFrame(
559       info2, QuicTime::Delta::Zero(), QuicTime::Zero());
560 
561   EXPECT_CALL(notifier_, OnFrameAcked(_, _, _)).Times(0);
562   unacked_packets_.NotifyAggregatedStreamFrameAcked(QuicTime::Delta::Zero());
563 }
564 
TEST_P(QuicUnackedPacketMapTest,LargestSentPacketMultiplePacketNumberSpaces)565 TEST_P(QuicUnackedPacketMapTest, LargestSentPacketMultiplePacketNumberSpaces) {
566   unacked_packets_.EnableMultiplePacketNumberSpacesSupport();
567   EXPECT_FALSE(
568       unacked_packets_
569           .GetLargestSentRetransmittableOfPacketNumberSpace(INITIAL_DATA)
570           .IsInitialized());
571   // Send packet 1.
572   SerializedPacket packet1(CreateRetransmittablePacket(1));
573   packet1.encryption_level = ENCRYPTION_INITIAL;
574   unacked_packets_.AddSentPacket(&packet1, NOT_RETRANSMISSION, now_, true);
575   EXPECT_EQ(QuicPacketNumber(1u), unacked_packets_.largest_sent_packet());
576   EXPECT_EQ(QuicPacketNumber(1),
577             unacked_packets_.GetLargestSentRetransmittableOfPacketNumberSpace(
578                 INITIAL_DATA));
579   EXPECT_FALSE(
580       unacked_packets_
581           .GetLargestSentRetransmittableOfPacketNumberSpace(HANDSHAKE_DATA)
582           .IsInitialized());
583   // Send packet 2.
584   SerializedPacket packet2(CreateRetransmittablePacket(2));
585   packet2.encryption_level = ENCRYPTION_HANDSHAKE;
586   unacked_packets_.AddSentPacket(&packet2, NOT_RETRANSMISSION, now_, true);
587   EXPECT_EQ(QuicPacketNumber(2u), unacked_packets_.largest_sent_packet());
588   EXPECT_EQ(QuicPacketNumber(1),
589             unacked_packets_.GetLargestSentRetransmittableOfPacketNumberSpace(
590                 INITIAL_DATA));
591   EXPECT_EQ(QuicPacketNumber(2),
592             unacked_packets_.GetLargestSentRetransmittableOfPacketNumberSpace(
593                 HANDSHAKE_DATA));
594   EXPECT_FALSE(
595       unacked_packets_
596           .GetLargestSentRetransmittableOfPacketNumberSpace(APPLICATION_DATA)
597           .IsInitialized());
598   // Send packet 3.
599   SerializedPacket packet3(CreateRetransmittablePacket(3));
600   packet3.encryption_level = ENCRYPTION_ZERO_RTT;
601   unacked_packets_.AddSentPacket(&packet3, NOT_RETRANSMISSION, now_, true);
602   EXPECT_EQ(QuicPacketNumber(3u), unacked_packets_.largest_sent_packet());
603   EXPECT_EQ(QuicPacketNumber(1),
604             unacked_packets_.GetLargestSentRetransmittableOfPacketNumberSpace(
605                 INITIAL_DATA));
606   EXPECT_EQ(QuicPacketNumber(2),
607             unacked_packets_.GetLargestSentRetransmittableOfPacketNumberSpace(
608                 HANDSHAKE_DATA));
609   EXPECT_EQ(QuicPacketNumber(3),
610             unacked_packets_.GetLargestSentRetransmittableOfPacketNumberSpace(
611                 APPLICATION_DATA));
612   // Verify forward secure belongs to the same packet number space as encryption
613   // zero rtt.
614   EXPECT_EQ(QuicPacketNumber(3),
615             unacked_packets_.GetLargestSentRetransmittableOfPacketNumberSpace(
616                 APPLICATION_DATA));
617 
618   // Send packet 4.
619   SerializedPacket packet4(CreateRetransmittablePacket(4));
620   packet4.encryption_level = ENCRYPTION_FORWARD_SECURE;
621   unacked_packets_.AddSentPacket(&packet4, NOT_RETRANSMISSION, now_, true);
622   EXPECT_EQ(QuicPacketNumber(4u), unacked_packets_.largest_sent_packet());
623   EXPECT_EQ(QuicPacketNumber(1),
624             unacked_packets_.GetLargestSentRetransmittableOfPacketNumberSpace(
625                 INITIAL_DATA));
626   EXPECT_EQ(QuicPacketNumber(2),
627             unacked_packets_.GetLargestSentRetransmittableOfPacketNumberSpace(
628                 HANDSHAKE_DATA));
629   EXPECT_EQ(QuicPacketNumber(4),
630             unacked_packets_.GetLargestSentRetransmittableOfPacketNumberSpace(
631                 APPLICATION_DATA));
632   // Verify forward secure belongs to the same packet number space as encryption
633   // zero rtt.
634   EXPECT_EQ(QuicPacketNumber(4),
635             unacked_packets_.GetLargestSentRetransmittableOfPacketNumberSpace(
636                 APPLICATION_DATA));
637 }
638 
639 }  // namespace
640 }  // namespace test
641 }  // namespace quic
642