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