1 // Copyright 2013 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 #include "net/quic/quic_sent_packet_manager.h"
7 #include "base/stl_util.h"
8 #include "net/quic/test_tools/quic_test_utils.h"
9 #include "testing/gmock/include/gmock/gmock.h"
10 #include "testing/gtest/include/gtest/gtest.h"
14 using testing::Return;
15 using testing::StrictMock;
21 class MockHelper : public QuicSentPacketManager::HelperInterface {
23 MOCK_METHOD0(GetNextPacketSequenceNumber, QuicPacketSequenceNumber());
24 MOCK_METHOD2(OnPacketNacked, void(QuicPacketSequenceNumber sequence_number,
28 class QuicSentPacketManagerTest : public ::testing::TestWithParam<bool> {
30 QuicSentPacketManagerTest()
31 : manager_(true, &helper_) {
35 FLAGS_track_retransmission_history = GetParam();
38 ~QuicSentPacketManagerTest() {
39 STLDeleteElements(&packets_);
43 void VerifyUnackedPackets(QuicPacketSequenceNumber* packets,
45 if (num_packets == 0) {
46 EXPECT_FALSE(manager_.HasUnackedPackets());
47 EXPECT_EQ(0u, manager_.GetNumUnackedPackets());
48 EXPECT_TRUE(manager_.GetUnackedPackets().empty());
52 EXPECT_TRUE(manager_.HasUnackedPackets());
53 EXPECT_EQ(packets[0], manager_.GetLeastUnackedSentPacket());
54 for (size_t i = 0; i < num_packets; ++i) {
55 EXPECT_TRUE(manager_.IsUnacked(packets[i])) << packets[i];
59 void VerifyRetransmittablePackets(QuicPacketSequenceNumber* packets,
61 SequenceNumberSet unacked = manager_.GetUnackedPackets();
62 for (size_t i = 0; i < num_packets; ++i) {
63 EXPECT_TRUE(ContainsKey(unacked, packets[i])) << packets[i];
65 size_t num_retransmittable = 0;
66 for (SequenceNumberSet::const_iterator it = unacked.begin();
67 it != unacked.end(); ++it) {
68 if (manager_.HasRetransmittableFrames(*it)) {
69 ++num_retransmittable;
72 EXPECT_EQ(num_packets, num_retransmittable);
75 void VerifyAckedPackets(QuicPacketSequenceNumber* expected,
77 const SequenceNumberSet& actual) {
78 if (num_expected == 0) {
79 EXPECT_TRUE(actual.empty());
83 EXPECT_EQ(num_expected, actual.size());
84 for (size_t i = 0; i < num_expected; ++i) {
85 EXPECT_TRUE(ContainsKey(actual, expected[i])) << expected[i];
89 void RetransmitPacket(QuicPacketSequenceNumber old_sequence_number,
90 QuicPacketSequenceNumber new_sequence_number) {
91 manager_.MarkForRetransmission(old_sequence_number, NACK_RETRANSMISSION);
92 EXPECT_TRUE(manager_.HasPendingRetransmissions());
93 QuicSentPacketManager::PendingRetransmission next_retransmission =
94 manager_.NextPendingRetransmission();
95 EXPECT_EQ(old_sequence_number, next_retransmission.sequence_number);
96 EXPECT_EQ(NACK_RETRANSMISSION, next_retransmission.transmission_type);
97 manager_.OnRetransmittedPacket(old_sequence_number, new_sequence_number);
98 EXPECT_TRUE(manager_.IsRetransmission(new_sequence_number));
101 SerializedPacket CreatePacket(QuicPacketSequenceNumber sequence_number) {
102 packets_.push_back(QuicPacket::NewDataPacket(
103 NULL, 0, false, PACKET_8BYTE_GUID, false,
104 PACKET_6BYTE_SEQUENCE_NUMBER));
105 return SerializedPacket(sequence_number, PACKET_6BYTE_SEQUENCE_NUMBER,
106 packets_.back(), 0u, new RetransmittableFrames());
109 SerializedPacket CreateFecPacket(QuicPacketSequenceNumber sequence_number) {
110 packets_.push_back(QuicPacket::NewFecPacket(
111 NULL, 0, false, PACKET_8BYTE_GUID, false,
112 PACKET_6BYTE_SEQUENCE_NUMBER));
113 return SerializedPacket(sequence_number, PACKET_6BYTE_SEQUENCE_NUMBER,
114 packets_.back(), 0u, NULL);
117 testing::StrictMock<MockHelper> helper_;
118 QuicSentPacketManager manager_;
119 vector<QuicPacket*> packets_;
122 INSTANTIATE_TEST_CASE_P(TrackRetransmissionHistory,
123 QuicSentPacketManagerTest,
124 ::testing::Values(false, true));
126 TEST_P(QuicSentPacketManagerTest, IsUnacked) {
127 VerifyUnackedPackets(NULL, 0);
129 SerializedPacket serialized_packet(CreatePacket(1));
131 manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
133 QuicPacketSequenceNumber unacked[] = { 1 };
134 VerifyUnackedPackets(unacked, arraysize(unacked));
135 QuicPacketSequenceNumber retransmittable[] = { 1 };
136 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
139 TEST_P(QuicSentPacketManagerTest, IsUnAckedRetransmit) {
140 if (!FLAGS_track_retransmission_history) {
141 // This tests restransmission tracking specifically.
144 SerializedPacket serialized_packet(CreatePacket(1));
146 manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
147 RetransmitPacket(1, 2);
149 EXPECT_EQ(1u, manager_.GetRetransmissionCount(2));
150 QuicPacketSequenceNumber unacked[] = { 1, 2 };
151 VerifyUnackedPackets(unacked, arraysize(unacked));
152 QuicPacketSequenceNumber retransmittable[] = { 2 };
153 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
155 RetransmitPacket(2, 3);
156 EXPECT_EQ(2u, manager_.GetRetransmissionCount(3));
157 QuicPacketSequenceNumber unacked2[] = { 1, 2, 3 };
158 VerifyUnackedPackets(unacked2, arraysize(unacked2));
159 QuicPacketSequenceNumber retransmittable2[] = { 3 };
160 VerifyRetransmittablePackets(retransmittable2, arraysize(retransmittable2));
163 TEST_P(QuicSentPacketManagerTest, RetransmitThenAck) {
164 SerializedPacket serialized_packet(CreatePacket(1));
166 manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
167 RetransmitPacket(1, 2);
170 ReceivedPacketInfo received_info;
171 received_info.largest_observed = 2;
172 received_info.missing_packets.insert(1);
173 manager_.OnIncomingAck(received_info, false);
175 // No unacked packets remain.
176 VerifyUnackedPackets(NULL, 0);
177 VerifyRetransmittablePackets(NULL, 0);
180 TEST_P(QuicSentPacketManagerTest, RetransmitThenAckBeforeSend) {
181 SerializedPacket serialized_packet(CreatePacket(1));
183 manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
184 manager_.MarkForRetransmission(1, NACK_RETRANSMISSION);
185 EXPECT_TRUE(manager_.HasPendingRetransmissions());
188 ReceivedPacketInfo received_info;
189 received_info.largest_observed = 1;
190 manager_.OnIncomingAck(received_info, false);
192 // There should no longer be a pending retransmission.
193 EXPECT_FALSE(manager_.HasPendingRetransmissions());
195 // No unacked packets remain.
196 VerifyUnackedPackets(NULL, 0);
197 VerifyRetransmittablePackets(NULL, 0);
200 TEST_P(QuicSentPacketManagerTest, RetransmitThenAckPrevious) {
201 if (!FLAGS_track_retransmission_history) {
202 // This tests restransmission tracking specifically.
205 SerializedPacket serialized_packet(CreatePacket(1));
207 manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
208 RetransmitPacket(1, 2);
211 ReceivedPacketInfo received_info;
212 received_info.largest_observed = 2;
213 received_info.missing_packets.insert(2);
214 EXPECT_CALL(helper_, OnPacketNacked(2, 1)).Times(1);
215 manager_.OnIncomingAck(received_info, false);
217 // 2 remains unacked, but no packets have retransmittable data.
218 QuicPacketSequenceNumber unacked[] = { 2 };
219 VerifyUnackedPackets(unacked, arraysize(unacked));
220 VerifyRetransmittablePackets(NULL, 0);
223 TEST_P(QuicSentPacketManagerTest, TruncatedAck) {
224 if (!FLAGS_track_retransmission_history) {
225 // This tests restransmission tracking specifically.
228 SerializedPacket serialized_packet(CreatePacket(1));
230 manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
231 RetransmitPacket(1, 2);
232 RetransmitPacket(2, 3);
233 RetransmitPacket(3, 4);
235 // Truncated ack with 2 NACKs
236 ReceivedPacketInfo received_info;
237 received_info.largest_observed = 2;
238 received_info.missing_packets.insert(1);
239 received_info.missing_packets.insert(2);
240 manager_.OnIncomingAck(received_info, true);
242 // High water mark will be raised.
243 QuicPacketSequenceNumber unacked[] = { 2, 3, 4 };
244 VerifyUnackedPackets(unacked, arraysize(unacked));
245 QuicPacketSequenceNumber retransmittable[] = { 4 };
246 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
249 TEST_P(QuicSentPacketManagerTest, SendDropAckRetransmitManyPackets) {
250 if (!FLAGS_track_retransmission_history) {
251 // This tests restransmission tracking specifically.
254 manager_.OnSerializedPacket(CreatePacket(1), QuicTime::Zero());
255 manager_.OnSerializedPacket(CreatePacket(2), QuicTime::Zero());
256 manager_.OnSerializedPacket(CreatePacket(3), QuicTime::Zero());
259 // Ack packets 1 and 3.
260 ReceivedPacketInfo received_info;
261 received_info.largest_observed = 3;
262 received_info.missing_packets.insert(2);
263 EXPECT_CALL(helper_, OnPacketNacked(2, 1)).Times(1);
264 manager_.OnIncomingAck(received_info, false);
266 QuicPacketSequenceNumber unacked[] = { 2 };
267 VerifyUnackedPackets(unacked, arraysize(unacked));
268 QuicPacketSequenceNumber retransmittable[] = { 2 };
269 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
272 manager_.OnSerializedPacket(CreatePacket(4), QuicTime::Zero());
273 manager_.OnSerializedPacket(CreatePacket(5), QuicTime::Zero());
277 ReceivedPacketInfo received_info;
278 received_info.largest_observed = 5;
279 received_info.missing_packets.insert(2);
280 received_info.missing_packets.insert(4);
281 EXPECT_CALL(helper_, OnPacketNacked(2, 2)).Times(1);
282 EXPECT_CALL(helper_, OnPacketNacked(4, 1)).Times(1);
283 manager_.OnIncomingAck(received_info, false);
285 QuicPacketSequenceNumber unacked[] = { 2, 4 };
286 VerifyUnackedPackets(unacked, arraysize(unacked));
287 QuicPacketSequenceNumber retransmittable[] = { 2, 4 };
288 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
291 manager_.OnSerializedPacket(CreatePacket(6), QuicTime::Zero());
292 manager_.OnSerializedPacket(CreatePacket(7), QuicTime::Zero());
296 ReceivedPacketInfo received_info;
297 received_info.largest_observed = 7;
298 received_info.missing_packets.insert(2);
299 received_info.missing_packets.insert(4);
300 received_info.missing_packets.insert(6);
301 EXPECT_CALL(helper_, OnPacketNacked(2, 3)).Times(1);
302 EXPECT_CALL(helper_, OnPacketNacked(4, 2)).Times(1);
303 EXPECT_CALL(helper_, OnPacketNacked(6, 1)).Times(1);
304 manager_.OnIncomingAck(received_info, false);
306 QuicPacketSequenceNumber unacked[] = { 2, 4, 6 };
307 VerifyUnackedPackets(unacked, arraysize(unacked));
308 QuicPacketSequenceNumber retransmittable[] = { 2, 4, 6 };
309 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
312 RetransmitPacket(2, 8);
313 manager_.OnSerializedPacket(CreatePacket(9), QuicTime::Zero());
314 manager_.OnSerializedPacket(CreatePacket(10), QuicTime::Zero());
318 ReceivedPacketInfo received_info;
319 received_info.largest_observed = 10;
320 received_info.missing_packets.insert(2);
321 received_info.missing_packets.insert(4);
322 received_info.missing_packets.insert(6);
323 received_info.missing_packets.insert(8);
324 received_info.missing_packets.insert(9);
325 EXPECT_CALL(helper_, OnPacketNacked(4, 3)).Times(1);
326 EXPECT_CALL(helper_, OnPacketNacked(6, 2)).Times(1);
327 EXPECT_CALL(helper_, OnPacketNacked(8, 1)).Times(1);
328 EXPECT_CALL(helper_, OnPacketNacked(9, 1)).Times(1);
329 manager_.OnIncomingAck(received_info, false);
331 QuicPacketSequenceNumber unacked[] = { 2, 4, 6, 8, 9 };
332 VerifyUnackedPackets(unacked, arraysize(unacked));
333 QuicPacketSequenceNumber retransmittable[] = { 4, 6, 8, 9 };
334 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
338 RetransmitPacket(4, 11);
339 manager_.OnSerializedPacket(CreatePacket(12), QuicTime::Zero());
340 manager_.OnSerializedPacket(CreatePacket(13), QuicTime::Zero());
344 ReceivedPacketInfo received_info;
345 received_info.largest_observed = 13;
346 received_info.missing_packets.insert(2);
347 received_info.missing_packets.insert(4);
348 received_info.missing_packets.insert(6);
349 received_info.missing_packets.insert(8);
350 received_info.missing_packets.insert(9);
351 received_info.missing_packets.insert(11);
352 received_info.missing_packets.insert(12);
353 EXPECT_CALL(helper_, OnPacketNacked(6, 3)).Times(1);
354 EXPECT_CALL(helper_, OnPacketNacked(8, 2)).Times(1);
355 EXPECT_CALL(helper_, OnPacketNacked(9, 2)).Times(1);
356 EXPECT_CALL(helper_, OnPacketNacked(11, 1)).Times(1);
357 EXPECT_CALL(helper_, OnPacketNacked(12, 1)).Times(1);
358 manager_.OnIncomingAck(received_info, false);
360 QuicPacketSequenceNumber unacked[] = { 2, 4, 6, 8, 9, 11, 12 };
361 VerifyUnackedPackets(unacked, arraysize(unacked));
362 QuicPacketSequenceNumber retransmittable[] = { 6, 8, 9, 11, 12 };
363 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
366 RetransmitPacket(6, 14);
367 manager_.OnSerializedPacket(CreatePacket(15), QuicTime::Zero());
368 manager_.OnSerializedPacket(CreatePacket(16), QuicTime::Zero());
372 ReceivedPacketInfo received_info;
373 received_info.largest_observed = 13;
374 received_info.missing_packets.insert(2);
375 received_info.missing_packets.insert(4);
376 received_info.missing_packets.insert(6);
377 received_info.missing_packets.insert(8);
378 received_info.missing_packets.insert(9);
379 received_info.missing_packets.insert(11);
380 received_info.missing_packets.insert(12);
381 EXPECT_CALL(helper_, OnPacketNacked(8, 3)).Times(1);
382 EXPECT_CALL(helper_, OnPacketNacked(9, 3)).Times(1);
383 EXPECT_CALL(helper_, OnPacketNacked(11, 2)).Times(1);
384 EXPECT_CALL(helper_, OnPacketNacked(12, 2)).Times(1);
385 manager_.OnIncomingAck(received_info, true);
387 // Truncated ack raises the high water mark by clearing out 2, 4, and 6.
388 QuicPacketSequenceNumber unacked[] = { 8, 9, 11, 12, 14, 15, 16 };
389 VerifyUnackedPackets(unacked, arraysize(unacked));
390 QuicPacketSequenceNumber retransmittable[] = { 8, 9, 11, 12, 14, 15, 16 };
391 VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
395 TEST_P(QuicSentPacketManagerTest, GetLeastUnackedSentPacket) {
396 EXPECT_CALL(helper_, GetNextPacketSequenceNumber()).WillOnce(Return(1u));
397 EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
400 TEST_P(QuicSentPacketManagerTest, GetLeastUnackedSentPacketUnacked) {
401 SerializedPacket serialized_packet(CreatePacket(1));
403 manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
404 EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
407 TEST_P(QuicSentPacketManagerTest, GetLeastUnackedSentPacketUnackedFec) {
408 SerializedPacket serialized_packet(CreateFecPacket(1));
410 manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
411 // FEC packets do not count as "unacked".
412 EXPECT_CALL(helper_, GetNextPacketSequenceNumber()).WillOnce(Return(2u));
413 EXPECT_EQ(2u, manager_.GetLeastUnackedSentPacket());
416 TEST_P(QuicSentPacketManagerTest, GetLeastUnackedSentPacketDiscardUnacked) {
417 SerializedPacket serialized_packet(CreatePacket(1));
419 manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
420 manager_.DiscardUnackedPacket(1u);
421 EXPECT_CALL(helper_, GetNextPacketSequenceNumber()).WillOnce(Return(2u));
422 EXPECT_EQ(2u, manager_.GetLeastUnackedSentPacket());
425 TEST_P(QuicSentPacketManagerTest, GetLeastUnackedFecPacketAndDiscard) {
426 VerifyUnackedPackets(NULL, 0);
428 SerializedPacket serialized_packet(CreateFecPacket(1));
429 manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
430 EXPECT_EQ(1u, manager_.GetLeastUnackedFecPacket());
432 SerializedPacket serialized_packet2(CreateFecPacket(2));
433 manager_.OnSerializedPacket(serialized_packet2, QuicTime::Zero());
434 EXPECT_EQ(1u, manager_.GetLeastUnackedFecPacket());
436 SerializedPacket serialized_packet3(CreateFecPacket(3));
437 manager_.OnSerializedPacket(serialized_packet3, QuicTime::Zero());
438 EXPECT_EQ(1u, manager_.GetLeastUnackedFecPacket());
440 VerifyUnackedPackets(NULL, 0);
441 VerifyRetransmittablePackets(NULL, 0);
443 manager_.DiscardFecPacket(1);
444 EXPECT_EQ(2u, manager_.GetLeastUnackedFecPacket());
447 ReceivedPacketInfo received_info;
448 received_info.largest_observed = 2;
449 manager_.OnIncomingAck(received_info, false);
451 EXPECT_EQ(3u, manager_.GetLeastUnackedFecPacket());
453 // Discard the 3rd packet and ensure there are no FEC packets.
454 manager_.DiscardFecPacket(3);
455 EXPECT_FALSE(manager_.HasUnackedFecPackets());
458 TEST_P(QuicSentPacketManagerTest, GetFecSentTime) {
459 VerifyUnackedPackets(NULL, 0);
461 SerializedPacket serialized_packet(CreateFecPacket(1));
462 manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
463 SerializedPacket serialized_packet2(CreateFecPacket(2));
464 QuicTime sent_time = QuicTime::Zero().Add(QuicTime::Delta::FromSeconds(1));
465 manager_.OnSerializedPacket(serialized_packet2, sent_time);
467 VerifyUnackedPackets(NULL, 0);
468 VerifyRetransmittablePackets(NULL, 0);
470 EXPECT_TRUE(manager_.HasUnackedFecPackets());
471 EXPECT_EQ(QuicTime::Zero(), manager_.GetFecSentTime(1));
472 EXPECT_EQ(sent_time, manager_.GetFecSentTime(2));