src/net/quic/quic_sent_packet_manager_test.cc

   1 // Copyright 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "net/quic/quic_sent_packet_manager.h"
   6
   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"
  11
  12 using std::vector;
  13 using testing::_;
  14 using testing::Return;
  15 using testing::StrictMock;
  16
  17 namespace net {
  18 namespace test {
  19 namespace {
  20
  21 class MockHelper : public QuicSentPacketManager::HelperInterface {
  22  public:
  23   MOCK_METHOD0(GetNextPacketSequenceNumber, QuicPacketSequenceNumber());
  24   MOCK_METHOD2(OnPacketNacked, void(QuicPacketSequenceNumber sequence_number,
  25                                     size_t nack_count));
  26 };
  27
  28 class QuicSentPacketManagerTest : public ::testing::TestWithParam<bool> {
  29  protected:
  30   QuicSentPacketManagerTest()
  31       : manager_(true, &helper_) {
  32   }
  33
  34   void SetUp() {
  35     FLAGS_track_retransmission_history = GetParam();
  36   }
  37
  38   ~QuicSentPacketManagerTest() {
  39     STLDeleteElements(&packets_);
  40   }
  41
  42
  43   void VerifyUnackedPackets(QuicPacketSequenceNumber* packets,
  44                             size_t num_packets) {
  45     if (num_packets == 0) {
  46       EXPECT_FALSE(manager_.HasUnackedPackets());
  47       EXPECT_EQ(0u, manager_.GetNumUnackedPackets());
  48       EXPECT_TRUE(manager_.GetUnackedPackets().empty());
  49       return;
  50     }
  51
  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];
  56     }
  57   }
  58
  59   void VerifyRetransmittablePackets(QuicPacketSequenceNumber* packets,
  60                                     size_t num_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];
  64     }
  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;
  70       }
  71     }
  72     EXPECT_EQ(num_packets, num_retransmittable);
  73   }
  74
  75   void VerifyAckedPackets(QuicPacketSequenceNumber* expected,
  76                           size_t num_expected,
  77                           const SequenceNumberSet& actual) {
  78     if (num_expected == 0) {
  79       EXPECT_TRUE(actual.empty());
  80       return;
  81     }
  82
  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];
  86     }
  87   }
  88
  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));
  99   }
 100
 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());
 107   }
 108
 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);
 115   }
 116
 117   testing::StrictMock<MockHelper> helper_;
 118   QuicSentPacketManager manager_;
 119   vector<QuicPacket*> packets_;
 120 };
 121
 122 INSTANTIATE_TEST_CASE_P(TrackRetransmissionHistory,
 123                         QuicSentPacketManagerTest,
 124                         ::testing::Values(false, true));
 125
 126 TEST_P(QuicSentPacketManagerTest, IsUnacked) {
 127   VerifyUnackedPackets(NULL, 0);
 128
 129   SerializedPacket serialized_packet(CreatePacket(1));
 130
 131   manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
 132
 133   QuicPacketSequenceNumber unacked[] = { 1 };
 134   VerifyUnackedPackets(unacked, arraysize(unacked));
 135   QuicPacketSequenceNumber retransmittable[] = { 1 };
 136   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 137 }
 138
 139 TEST_P(QuicSentPacketManagerTest, IsUnAckedRetransmit) {
 140   if (!FLAGS_track_retransmission_history) {
 141     // This tests restransmission tracking specifically.
 142     return;
 143   }
 144   SerializedPacket serialized_packet(CreatePacket(1));
 145
 146   manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
 147   RetransmitPacket(1, 2);
 148
 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));
 154
 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));
 161 }
 162
 163 TEST_P(QuicSentPacketManagerTest, RetransmitThenAck) {
 164   SerializedPacket serialized_packet(CreatePacket(1));
 165
 166   manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
 167   RetransmitPacket(1, 2);
 168
 169   // Ack 2 but not 1.
 170   ReceivedPacketInfo received_info;
 171   received_info.largest_observed = 2;
 172   received_info.missing_packets.insert(1);
 173   manager_.OnIncomingAck(received_info, false);
 174
 175   // No unacked packets remain.
 176   VerifyUnackedPackets(NULL, 0);
 177   VerifyRetransmittablePackets(NULL, 0);
 178 }
 179
 180 TEST_P(QuicSentPacketManagerTest, RetransmitThenAckBeforeSend) {
 181   SerializedPacket serialized_packet(CreatePacket(1));
 182
 183   manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
 184   manager_.MarkForRetransmission(1, NACK_RETRANSMISSION);
 185   EXPECT_TRUE(manager_.HasPendingRetransmissions());
 186
 187   // Ack 1.
 188   ReceivedPacketInfo received_info;
 189   received_info.largest_observed = 1;
 190   manager_.OnIncomingAck(received_info, false);
 191
 192   // There should no longer be a pending retransmission.
 193   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 194
 195   // No unacked packets remain.
 196   VerifyUnackedPackets(NULL, 0);
 197   VerifyRetransmittablePackets(NULL, 0);
 198 }
 199
 200 TEST_P(QuicSentPacketManagerTest, RetransmitThenAckPrevious) {
 201   if (!FLAGS_track_retransmission_history) {
 202     // This tests restransmission tracking specifically.
 203     return;
 204   }
 205   SerializedPacket serialized_packet(CreatePacket(1));
 206
 207   manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
 208   RetransmitPacket(1, 2);
 209
 210   // Ack 1 but not 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);
 216
 217   // 2 remains unacked, but no packets have retransmittable data.
 218   QuicPacketSequenceNumber unacked[] = { 2 };
 219   VerifyUnackedPackets(unacked, arraysize(unacked));
 220   VerifyRetransmittablePackets(NULL, 0);
 221 }
 222
 223 TEST_P(QuicSentPacketManagerTest, TruncatedAck) {
 224   if (!FLAGS_track_retransmission_history) {
 225     // This tests restransmission tracking specifically.
 226     return;
 227   }
 228   SerializedPacket serialized_packet(CreatePacket(1));
 229
 230   manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
 231   RetransmitPacket(1, 2);
 232   RetransmitPacket(2, 3);
 233   RetransmitPacket(3, 4);
 234
 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);
 241
 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));
 247 }
 248
 249 TEST_P(QuicSentPacketManagerTest, SendDropAckRetransmitManyPackets) {
 250   if (!FLAGS_track_retransmission_history) {
 251     // This tests restransmission tracking specifically.
 252     return;
 253   }
 254   manager_.OnSerializedPacket(CreatePacket(1), QuicTime::Zero());
 255   manager_.OnSerializedPacket(CreatePacket(2), QuicTime::Zero());
 256   manager_.OnSerializedPacket(CreatePacket(3), QuicTime::Zero());
 257
 258   {
 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);
 265
 266     QuicPacketSequenceNumber unacked[] = { 2 };
 267     VerifyUnackedPackets(unacked, arraysize(unacked));
 268     QuicPacketSequenceNumber retransmittable[] = { 2 };
 269     VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 270   }
 271
 272   manager_.OnSerializedPacket(CreatePacket(4), QuicTime::Zero());
 273   manager_.OnSerializedPacket(CreatePacket(5), QuicTime::Zero());
 274
 275   {
 276     // Ack packets 5.
 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);
 284
 285     QuicPacketSequenceNumber unacked[] = { 2, 4 };
 286     VerifyUnackedPackets(unacked, arraysize(unacked));
 287     QuicPacketSequenceNumber retransmittable[] = { 2, 4 };
 288     VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 289   }
 290
 291   manager_.OnSerializedPacket(CreatePacket(6), QuicTime::Zero());
 292   manager_.OnSerializedPacket(CreatePacket(7), QuicTime::Zero());
 293
 294   {
 295     // Ack packets 7.
 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);
 305
 306     QuicPacketSequenceNumber unacked[] = { 2, 4, 6 };
 307     VerifyUnackedPackets(unacked, arraysize(unacked));
 308     QuicPacketSequenceNumber retransmittable[] = { 2, 4, 6 };
 309     VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 310   }
 311
 312   RetransmitPacket(2, 8);
 313   manager_.OnSerializedPacket(CreatePacket(9), QuicTime::Zero());
 314   manager_.OnSerializedPacket(CreatePacket(10), QuicTime::Zero());
 315
 316   {
 317     // Ack packet 10.
 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);
 330
 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));
 335   }
 336
 337
 338   RetransmitPacket(4, 11);
 339   manager_.OnSerializedPacket(CreatePacket(12), QuicTime::Zero());
 340   manager_.OnSerializedPacket(CreatePacket(13), QuicTime::Zero());
 341
 342   {
 343     // Ack packet 13.
 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);
 359
 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));
 364   }
 365
 366   RetransmitPacket(6, 14);
 367   manager_.OnSerializedPacket(CreatePacket(15), QuicTime::Zero());
 368   manager_.OnSerializedPacket(CreatePacket(16), QuicTime::Zero());
 369
 370   {
 371     // Ack packet 16.
 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);
 386
 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));
 392   }
 393 }
 394
 395 TEST_P(QuicSentPacketManagerTest, GetLeastUnackedSentPacket) {
 396   EXPECT_CALL(helper_, GetNextPacketSequenceNumber()).WillOnce(Return(1u));
 397   EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
 398 }
 399
 400 TEST_P(QuicSentPacketManagerTest, GetLeastUnackedSentPacketUnacked) {
 401   SerializedPacket serialized_packet(CreatePacket(1));
 402
 403   manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
 404   EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
 405 }
 406
 407 TEST_P(QuicSentPacketManagerTest, GetLeastUnackedSentPacketUnackedFec) {
 408   SerializedPacket serialized_packet(CreateFecPacket(1));
 409
 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());
 414 }
 415
 416 TEST_P(QuicSentPacketManagerTest, GetLeastUnackedSentPacketDiscardUnacked) {
 417   SerializedPacket serialized_packet(CreatePacket(1));
 418
 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());
 423 }
 424
 425 TEST_P(QuicSentPacketManagerTest, GetLeastUnackedFecPacketAndDiscard) {
 426   VerifyUnackedPackets(NULL, 0);
 427
 428   SerializedPacket serialized_packet(CreateFecPacket(1));
 429   manager_.OnSerializedPacket(serialized_packet, QuicTime::Zero());
 430   EXPECT_EQ(1u, manager_.GetLeastUnackedFecPacket());
 431
 432   SerializedPacket serialized_packet2(CreateFecPacket(2));
 433   manager_.OnSerializedPacket(serialized_packet2, QuicTime::Zero());
 434   EXPECT_EQ(1u, manager_.GetLeastUnackedFecPacket());
 435
 436   SerializedPacket serialized_packet3(CreateFecPacket(3));
 437   manager_.OnSerializedPacket(serialized_packet3, QuicTime::Zero());
 438   EXPECT_EQ(1u, manager_.GetLeastUnackedFecPacket());
 439
 440   VerifyUnackedPackets(NULL, 0);
 441   VerifyRetransmittablePackets(NULL, 0);
 442
 443   manager_.DiscardFecPacket(1);
 444   EXPECT_EQ(2u, manager_.GetLeastUnackedFecPacket());
 445
 446   // Ack 2.
 447   ReceivedPacketInfo received_info;
 448   received_info.largest_observed = 2;
 449   manager_.OnIncomingAck(received_info, false);
 450
 451   EXPECT_EQ(3u, manager_.GetLeastUnackedFecPacket());
 452
 453   // Discard the 3rd packet and ensure there are no FEC packets.
 454   manager_.DiscardFecPacket(3);
 455   EXPECT_FALSE(manager_.HasUnackedFecPackets());
 456 }
 457
 458 TEST_P(QuicSentPacketManagerTest, GetFecSentTime) {
 459   VerifyUnackedPackets(NULL, 0);
 460
 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);
 466
 467   VerifyUnackedPackets(NULL, 0);
 468   VerifyRetransmittablePackets(NULL, 0);
 469
 470   EXPECT_TRUE(manager_.HasUnackedFecPackets());
 471   EXPECT_EQ(QuicTime::Zero(), manager_.GetFecSentTime(1));
 472   EXPECT_EQ(sent_time, manager_.GetFecSentTime(2));
 473 }
 474
 475 }  // namespace
 476 }  // namespace test
 477 }  // namespace net