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(¬ifier_);
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(¬ifier_);
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(¬ifier_);
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(¬ifier_);
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