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_sent_packet_manager_peer.h"
   9 #include "net/quic/test_tools/quic_test_utils.h"
  10 #include "testing/gmock/include/gmock/gmock.h"
  11 #include "testing/gtest/include/gtest/gtest.h"
  12
  13 using std::vector;
  14 using testing::_;
  15 using testing::Return;
  16 using testing::StrictMock;
  17
  18 namespace net {
  19 namespace test {
  20 namespace {
  21
  22 class MockHelper : public QuicSentPacketManager::HelperInterface {
  23  public:
  24   MOCK_METHOD0(GetNextPacketSequenceNumber, QuicPacketSequenceNumber());
  25 };
  26
  27 class QuicSentPacketManagerTest : public ::testing::TestWithParam<bool> {
  28  protected:
  29   QuicSentPacketManagerTest()
  30       : manager_(true, &helper_, &clock_, kFixRate),
  31         send_algorithm_(new StrictMock<MockSendAlgorithm>) {
  32     QuicSentPacketManagerPeer::SetSendAlgorithm(&manager_, send_algorithm_);
  33     // Disable tail loss probes for most tests.
  34     QuicSentPacketManagerPeer::SetMaxTailLossProbes(&manager_, 0);
  35     // Advance the time 1s so the send times are never QuicTime::Zero.
  36     clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(1000));
  37   }
  38
  39   ~QuicSentPacketManagerTest() {
  40     STLDeleteElements(&packets_);
  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_.GetNumRetransmittablePackets());
  48       return;
  49     }
  50
  51     EXPECT_TRUE(manager_.HasUnackedPackets());
  52     EXPECT_EQ(packets[0], manager_.GetLeastUnackedSentPacket());
  53     for (size_t i = 0; i < num_packets; ++i) {
  54       EXPECT_TRUE(manager_.IsUnacked(packets[i])) << packets[i];
  55     }
  56   }
  57
  58   void VerifyRetransmittablePackets(QuicPacketSequenceNumber* packets,
  59                                     size_t num_packets) {
  60     SequenceNumberSet unacked = manager_.GetUnackedPackets();
  61     for (size_t i = 0; i < num_packets; ++i) {
  62       EXPECT_TRUE(ContainsKey(unacked, packets[i])) << packets[i];
  63     }
  64     size_t num_retransmittable = 0;
  65     for (SequenceNumberSet::const_iterator it = unacked.begin();
  66          it != unacked.end(); ++it) {
  67       if (manager_.HasRetransmittableFrames(*it)) {
  68         ++num_retransmittable;
  69       }
  70     }
  71     EXPECT_EQ(num_packets, manager_.GetNumRetransmittablePackets());
  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     QuicSentPacketManagerPeer::MarkForRetransmission(
  92         &manager_, old_sequence_number, NACK_RETRANSMISSION);
  93     EXPECT_TRUE(manager_.HasPendingRetransmissions());
  94     QuicSentPacketManager::PendingRetransmission next_retransmission =
  95         manager_.NextPendingRetransmission();
  96     EXPECT_EQ(old_sequence_number, next_retransmission.sequence_number);
  97     EXPECT_EQ(NACK_RETRANSMISSION, next_retransmission.transmission_type);
  98     manager_.OnRetransmittedPacket(old_sequence_number, new_sequence_number);
  99     EXPECT_TRUE(QuicSentPacketManagerPeer::IsRetransmission(
 100         &manager_, new_sequence_number));
 101   }
 102
 103   void RetransmitAndSendPacket(QuicPacketSequenceNumber old_sequence_number,
 104                                QuicPacketSequenceNumber new_sequence_number) {
 105     RetransmitPacket(old_sequence_number, new_sequence_number);
 106     EXPECT_CALL(*send_algorithm_, OnPacketSent(_, new_sequence_number, _, _, _))
 107         .WillOnce(Return(true));
 108     manager_.OnPacketSent(new_sequence_number, clock_.Now(),
 109                           1000, NACK_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA);
 110   }
 111
 112   SerializedPacket CreateDataPacket(QuicPacketSequenceNumber sequence_number) {
 113     return CreatePacket(sequence_number, true);
 114   }
 115
 116   SerializedPacket CreatePacket(QuicPacketSequenceNumber sequence_number,
 117                                 bool retransmittable) {
 118     packets_.push_back(QuicPacket::NewDataPacket(
 119         NULL, 1000, false, PACKET_8BYTE_GUID, false,
 120         PACKET_6BYTE_SEQUENCE_NUMBER));
 121     return SerializedPacket(
 122         sequence_number, PACKET_6BYTE_SEQUENCE_NUMBER,
 123         packets_.back(), 0u,
 124         retransmittable ? new RetransmittableFrames() : NULL);
 125   }
 126
 127   SerializedPacket CreateFecPacket(QuicPacketSequenceNumber sequence_number) {
 128     packets_.push_back(QuicPacket::NewFecPacket(
 129         NULL, 1000, false, PACKET_8BYTE_GUID, false,
 130         PACKET_6BYTE_SEQUENCE_NUMBER));
 131     return SerializedPacket(sequence_number, PACKET_6BYTE_SEQUENCE_NUMBER,
 132                             packets_.back(), 0u, NULL);
 133   }
 134
 135   void SendDataPacket(QuicPacketSequenceNumber sequence_number) {
 136     EXPECT_CALL(*send_algorithm_, OnPacketSent(_, sequence_number, _, _, _))
 137                     .Times(1).WillOnce(Return(true));
 138     SerializedPacket packet(CreateDataPacket(sequence_number));
 139     manager_.OnSerializedPacket(packet);
 140     manager_.OnPacketSent(sequence_number, clock_.Now(),
 141                           packet.packet->length(), NOT_RETRANSMISSION,
 142                           HAS_RETRANSMITTABLE_DATA);
 143   }
 144
 145   void SendCryptoPacket(QuicPacketSequenceNumber sequence_number) {
 146     EXPECT_CALL(*send_algorithm_, OnPacketSent(_, sequence_number, _, _, _))
 147                     .Times(1).WillOnce(Return(true));
 148     SerializedPacket packet(CreateDataPacket(sequence_number));
 149     packet.retransmittable_frames->AddStreamFrame(
 150         new QuicStreamFrame(1, false, 0, IOVector()));
 151     manager_.OnSerializedPacket(packet);
 152     manager_.OnPacketSent(sequence_number, clock_.ApproximateNow(),
 153                           packet.packet->length(), NOT_RETRANSMISSION,
 154                           HAS_RETRANSMITTABLE_DATA);
 155   }
 156
 157   // Based on QuicConnection's WritePendingRetransmissions.
 158   void RetransmitNextPacket(
 159       QuicPacketSequenceNumber retransmission_sequence_number) {
 160     EXPECT_TRUE(manager_.HasPendingRetransmissions());
 161     EXPECT_CALL(*send_algorithm_,
 162                 OnPacketSent(_, retransmission_sequence_number, _, _, _))
 163                     .Times(1).WillOnce(Return(true));
 164     const QuicSentPacketManager::PendingRetransmission pending =
 165         manager_.NextPendingRetransmission();
 166     manager_.OnRetransmittedPacket(
 167         pending.sequence_number, retransmission_sequence_number);
 168     manager_.OnPacketSent(retransmission_sequence_number,
 169                           clock_.ApproximateNow(), 1000,
 170                           pending.transmission_type, HAS_RETRANSMITTABLE_DATA);
 171   }
 172
 173   testing::StrictMock<MockHelper> helper_;
 174   QuicSentPacketManager manager_;
 175   vector<QuicPacket*> packets_;
 176   MockClock clock_;
 177   MockSendAlgorithm* send_algorithm_;
 178 };
 179
 180 TEST_F(QuicSentPacketManagerTest, IsUnacked) {
 181   VerifyUnackedPackets(NULL, 0);
 182
 183   SerializedPacket serialized_packet(CreateDataPacket(1));
 184
 185   manager_.OnSerializedPacket(serialized_packet);
 186
 187   QuicPacketSequenceNumber unacked[] = { 1 };
 188   VerifyUnackedPackets(unacked, arraysize(unacked));
 189   QuicPacketSequenceNumber retransmittable[] = { 1 };
 190   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 191 }
 192
 193 TEST_F(QuicSentPacketManagerTest, IsUnAckedRetransmit) {
 194   SerializedPacket serialized_packet(CreateDataPacket(1));
 195
 196   manager_.OnSerializedPacket(serialized_packet);
 197   RetransmitPacket(1, 2);
 198
 199   EXPECT_TRUE(QuicSentPacketManagerPeer::IsRetransmission(&manager_, 2));
 200   QuicPacketSequenceNumber unacked[] = { 1, 2 };
 201   VerifyUnackedPackets(unacked, arraysize(unacked));
 202   QuicPacketSequenceNumber retransmittable[] = { 2 };
 203   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 204 }
 205
 206 TEST_F(QuicSentPacketManagerTest, RetransmitThenAck) {
 207   SerializedPacket serialized_packet(CreateDataPacket(1));
 208
 209   manager_.OnSerializedPacket(serialized_packet);
 210   RetransmitPacket(1, 2);
 211
 212   // Ack 2 but not 1.
 213   ReceivedPacketInfo received_info;
 214   received_info.largest_observed = 2;
 215   received_info.missing_packets.insert(1);
 216   manager_.OnIncomingAck(received_info, QuicTime::Zero());
 217
 218   // No unacked packets remain.
 219   VerifyUnackedPackets(NULL, 0);
 220   VerifyRetransmittablePackets(NULL, 0);
 221 }
 222
 223 TEST_F(QuicSentPacketManagerTest, RetransmitThenAckBeforeSend) {
 224   SerializedPacket serialized_packet(CreateDataPacket(1));
 225
 226   manager_.OnSerializedPacket(serialized_packet);
 227   QuicSentPacketManagerPeer::MarkForRetransmission(
 228       &manager_, 1, NACK_RETRANSMISSION);
 229   EXPECT_TRUE(manager_.HasPendingRetransmissions());
 230
 231   // Ack 1.
 232   ReceivedPacketInfo received_info;
 233   received_info.largest_observed = 1;
 234   manager_.OnIncomingAck(received_info, QuicTime::Zero());
 235
 236   // There should no longer be a pending retransmission.
 237   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 238
 239   // No unacked packets remain.
 240   VerifyUnackedPackets(NULL, 0);
 241   VerifyRetransmittablePackets(NULL, 0);
 242 }
 243
 244 TEST_F(QuicSentPacketManagerTest, RetransmitThenAckPrevious) {
 245   SendDataPacket(1);
 246   RetransmitPacket(1, 2);
 247   QuicTime::Delta rtt = QuicTime::Delta::FromMilliseconds(15);
 248   clock_.AdvanceTime(rtt);
 249
 250   // Ack 1 but not 2.
 251   EXPECT_CALL(*send_algorithm_, UpdateRtt(rtt));
 252   EXPECT_CALL(*send_algorithm_, OnPacketAcked(1, _));
 253   ReceivedPacketInfo received_info;
 254   received_info.largest_observed = 1;
 255   EXPECT_TRUE(manager_.OnIncomingAck(received_info, clock_.ApproximateNow()));
 256
 257   // 2 remains unacked, but no packets have retransmittable data.
 258   QuicPacketSequenceNumber unacked[] = { 2 };
 259   VerifyUnackedPackets(unacked, arraysize(unacked));
 260   EXPECT_FALSE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 261   VerifyRetransmittablePackets(NULL, 0);
 262
 263   // Verify that the retransmission alarm would not fire,
 264   // since there is no retransmittable data outstanding.
 265   EXPECT_EQ(QuicTime::Zero(), manager_.GetRetransmissionTime());
 266 }
 267
 268 TEST_F(QuicSentPacketManagerTest, RetransmitThenAckPreviousThenNackRetransmit) {
 269   SendDataPacket(1);
 270   RetransmitPacket(1, 2);
 271   EXPECT_CALL(*send_algorithm_, OnPacketSent(_, 2, _, _, _))
 272       .WillOnce(Return(true));
 273   manager_.OnPacketSent(2, clock_.ApproximateNow(), 1000,
 274                         NACK_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA);
 275   QuicTime::Delta rtt = QuicTime::Delta::FromMilliseconds(15);
 276   clock_.AdvanceTime(rtt);
 277
 278   // First, ACK packet 1 which makes packet 2 non-retransmittable.
 279   EXPECT_CALL(*send_algorithm_, UpdateRtt(rtt));
 280   EXPECT_CALL(*send_algorithm_, OnPacketAcked(1, _));
 281   ReceivedPacketInfo received_info;
 282   received_info.largest_observed = 1;
 283   EXPECT_TRUE(manager_.OnIncomingAck(received_info, clock_.ApproximateNow()));
 284
 285   SendDataPacket(3);
 286   SendDataPacket(4);
 287   SendDataPacket(5);
 288   clock_.AdvanceTime(rtt);
 289
 290   // Next, NACK packet 2 three times.
 291   received_info.largest_observed = 3;
 292   received_info.missing_packets.insert(2);
 293   EXPECT_CALL(*send_algorithm_, UpdateRtt(rtt));
 294   EXPECT_CALL(*send_algorithm_, OnPacketAcked(3, _));
 295   EXPECT_TRUE(manager_.OnIncomingAck(received_info, clock_.ApproximateNow()));
 296
 297   received_info.largest_observed = 4;
 298   EXPECT_CALL(*send_algorithm_, UpdateRtt(rtt));
 299   EXPECT_CALL(*send_algorithm_, OnPacketAcked(4, _));
 300   EXPECT_TRUE(manager_.OnIncomingAck(received_info, clock_.ApproximateNow()));
 301
 302   received_info.largest_observed = 5;
 303   EXPECT_CALL(*send_algorithm_, UpdateRtt(rtt));
 304   EXPECT_CALL(*send_algorithm_, OnPacketAcked(5, _));
 305   EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(2, _));
 306   EXPECT_CALL(*send_algorithm_, OnPacketLost(2, _));
 307   EXPECT_TRUE(manager_.OnIncomingAck(received_info, clock_.ApproximateNow()));
 308
 309   // No packets remain unacked.
 310   VerifyUnackedPackets(NULL, 0);
 311   EXPECT_FALSE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 312   VerifyRetransmittablePackets(NULL, 0);
 313
 314   // Verify that the retransmission alarm would not fire,
 315   // since there is no retransmittable data outstanding.
 316   EXPECT_EQ(QuicTime::Zero(), manager_.GetRetransmissionTime());
 317 }
 318
 319 TEST_F(QuicSentPacketManagerTest, RetransmitTwiceThenAckPreviousBeforeSend) {
 320   SendDataPacket(1);
 321   RetransmitAndSendPacket(1, 2);
 322
 323   // Fire the RTO, which will mark 2 for retransmission (but will not send it).
 324   EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout(true));
 325   manager_.OnRetransmissionTimeout();
 326   EXPECT_TRUE(manager_.HasPendingRetransmissions());
 327
 328   // Ack 1 but not 2, before 2 is able to be sent.
 329   // Since 1 has been retransmitted, it has already been lost, and so the
 330   // send algorithm is not informed that it has been ACK'd.
 331   ReceivedPacketInfo received_info;
 332   received_info.largest_observed = 1;
 333   EXPECT_CALL(*send_algorithm_, UpdateRtt(QuicTime::Delta::Zero()));
 334   EXPECT_TRUE(manager_.OnIncomingAck(received_info, clock_.ApproximateNow()));
 335
 336   // Since 2 was marked for retransmit, when 1 is acked, 2 is discarded.
 337   VerifyUnackedPackets(NULL, 0);
 338   EXPECT_FALSE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 339   VerifyRetransmittablePackets(NULL, 0);
 340
 341   // Verify that the retransmission alarm would not fire,
 342   // since there is no retransmittable data outstanding.
 343   EXPECT_EQ(QuicTime::Zero(), manager_.GetRetransmissionTime());
 344 }
 345
 346 TEST_F(QuicSentPacketManagerTest, RetransmitTwiceThenAckFirst) {
 347   SendDataPacket(1);
 348   RetransmitPacket(1, 2);
 349   RetransmitPacket(2, 3);
 350   QuicTime::Delta rtt = QuicTime::Delta::FromMilliseconds(15);
 351   clock_.AdvanceTime(rtt);
 352
 353   // Ack 1 but not 2 or 3.
 354   EXPECT_CALL(*send_algorithm_, UpdateRtt(rtt));
 355   EXPECT_CALL(*send_algorithm_, OnPacketAcked(1, _));
 356   ReceivedPacketInfo received_info;
 357   received_info.largest_observed = 1;
 358   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 359
 360   // 3 remains unacked, but no packets have retransmittable data.
 361   QuicPacketSequenceNumber unacked[] = { 3 };
 362   VerifyUnackedPackets(unacked, arraysize(unacked));
 363   EXPECT_FALSE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 364   VerifyRetransmittablePackets(NULL, 0);
 365
 366   // Verify that the retransmission alarm would not fire to abandon packet 3.
 367   EXPECT_EQ(QuicTime::Zero(), manager_.GetRetransmissionTime());
 368 }
 369
 370 TEST_F(QuicSentPacketManagerTest, TruncatedAck) {
 371   SerializedPacket serialized_packet(CreateDataPacket(1));
 372
 373   manager_.OnSerializedPacket(serialized_packet);
 374   RetransmitPacket(1, 2);
 375   RetransmitPacket(2, 3);
 376   RetransmitPacket(3, 4);
 377
 378   // Truncated ack with 2 NACKs
 379   ReceivedPacketInfo received_info;
 380   received_info.largest_observed = 2;
 381   received_info.missing_packets.insert(1);
 382   received_info.missing_packets.insert(2);
 383   received_info.is_truncated = true;
 384   manager_.OnIncomingAck(received_info, QuicTime::Zero());
 385
 386   // High water mark will be raised.
 387   QuicPacketSequenceNumber unacked[] = { 2, 3, 4 };
 388   VerifyUnackedPackets(unacked, arraysize(unacked));
 389   QuicPacketSequenceNumber retransmittable[] = { 4 };
 390   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 391 }
 392
 393 TEST_F(QuicSentPacketManagerTest, AckPreviousTransmissionThenTruncatedAck) {
 394   SerializedPacket serialized_packet(CreateDataPacket(1));
 395
 396   manager_.OnSerializedPacket(serialized_packet);
 397   RetransmitPacket(1, 2);
 398   RetransmitPacket(2, 3);
 399   RetransmitPacket(3, 4);
 400   manager_.OnSerializedPacket(CreateDataPacket(5));
 401   manager_.OnSerializedPacket(CreateDataPacket(6));
 402   manager_.OnSerializedPacket(CreateDataPacket(7));
 403   manager_.OnSerializedPacket(CreateDataPacket(8));
 404   manager_.OnSerializedPacket(CreateDataPacket(9));
 405
 406   // Ack previous transmission
 407   {
 408     ReceivedPacketInfo received_info;
 409     received_info.largest_observed = 2;
 410     received_info.missing_packets.insert(1);
 411     manager_.OnIncomingAck(received_info, QuicTime::Zero());
 412     EXPECT_TRUE(manager_.IsUnacked(4));
 413   }
 414
 415   // Truncated ack with 4 NACKs
 416   {
 417     ReceivedPacketInfo received_info;
 418     received_info.largest_observed = 6;
 419     received_info.missing_packets.insert(3);
 420     received_info.missing_packets.insert(4);
 421     received_info.missing_packets.insert(5);
 422     received_info.missing_packets.insert(6);
 423     received_info.is_truncated = true;
 424     manager_.OnIncomingAck(received_info, QuicTime::Zero());
 425   }
 426
 427   // High water mark will be raised.
 428   QuicPacketSequenceNumber unacked[] = { 5, 6, 7, 8, 9 };
 429   VerifyUnackedPackets(unacked, arraysize(unacked));
 430   QuicPacketSequenceNumber retransmittable[] = { 5, 6, 7, 8, 9 };
 431   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 432 }
 433
 434 TEST_F(QuicSentPacketManagerTest, SendDropAckRetransmitManyPackets) {
 435   manager_.OnSerializedPacket(CreateDataPacket(1));
 436   manager_.OnSerializedPacket(CreateDataPacket(2));
 437   manager_.OnSerializedPacket(CreateDataPacket(3));
 438
 439   {
 440     // Ack packets 1 and 3.
 441     ReceivedPacketInfo received_info;
 442     received_info.largest_observed = 3;
 443     received_info.missing_packets.insert(2);
 444     manager_.OnIncomingAck(received_info, QuicTime::Zero());
 445
 446     QuicPacketSequenceNumber unacked[] = { 2 };
 447     VerifyUnackedPackets(unacked, arraysize(unacked));
 448     QuicPacketSequenceNumber retransmittable[] = { 2 };
 449     VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 450   }
 451
 452   manager_.OnSerializedPacket(CreateDataPacket(4));
 453   manager_.OnSerializedPacket(CreateDataPacket(5));
 454
 455   {
 456     // Ack packets 5.
 457     ReceivedPacketInfo received_info;
 458     received_info.largest_observed = 5;
 459     received_info.missing_packets.insert(2);
 460     received_info.missing_packets.insert(4);
 461     manager_.OnIncomingAck(received_info, QuicTime::Zero());
 462
 463     QuicPacketSequenceNumber unacked[] = { 2, 4 };
 464     VerifyUnackedPackets(unacked, arraysize(unacked));
 465     QuicPacketSequenceNumber retransmittable[] = { 2, 4 };
 466     VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 467   }
 468
 469   manager_.OnSerializedPacket(CreateDataPacket(6));
 470   manager_.OnSerializedPacket(CreateDataPacket(7));
 471
 472   {
 473     // Ack packets 7.
 474     ReceivedPacketInfo received_info;
 475     received_info.largest_observed = 7;
 476     received_info.missing_packets.insert(2);
 477     received_info.missing_packets.insert(4);
 478     received_info.missing_packets.insert(6);
 479     manager_.OnIncomingAck(received_info, QuicTime::Zero());
 480
 481     QuicPacketSequenceNumber unacked[] = { 2, 4, 6 };
 482     VerifyUnackedPackets(unacked, arraysize(unacked));
 483     QuicPacketSequenceNumber retransmittable[] = { 2, 4, 6 };
 484     VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 485   }
 486
 487   RetransmitPacket(2, 8);
 488   manager_.OnSerializedPacket(CreateDataPacket(9));
 489   manager_.OnSerializedPacket(CreateDataPacket(10));
 490
 491   {
 492     // Ack packet 10.
 493     ReceivedPacketInfo received_info;
 494     received_info.largest_observed = 10;
 495     received_info.missing_packets.insert(2);
 496     received_info.missing_packets.insert(4);
 497     received_info.missing_packets.insert(6);
 498     received_info.missing_packets.insert(8);
 499     received_info.missing_packets.insert(9);
 500     manager_.OnIncomingAck(received_info, QuicTime::Zero());
 501
 502     QuicPacketSequenceNumber unacked[] = { 2, 4, 6, 8, 9 };
 503     VerifyUnackedPackets(unacked, arraysize(unacked));
 504     QuicPacketSequenceNumber retransmittable[] = { 4, 6, 8, 9 };
 505     VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 506   }
 507
 508
 509   RetransmitPacket(4, 11);
 510   manager_.OnSerializedPacket(CreateDataPacket(12));
 511   manager_.OnSerializedPacket(CreateDataPacket(13));
 512
 513   {
 514     // Ack packet 13.
 515     ReceivedPacketInfo received_info;
 516     received_info.largest_observed = 13;
 517     received_info.missing_packets.insert(2);
 518     received_info.missing_packets.insert(4);
 519     received_info.missing_packets.insert(6);
 520     received_info.missing_packets.insert(8);
 521     received_info.missing_packets.insert(9);
 522     received_info.missing_packets.insert(11);
 523     received_info.missing_packets.insert(12);
 524     manager_.OnIncomingAck(received_info, QuicTime::Zero());
 525
 526     QuicPacketSequenceNumber unacked[] = { 2, 4, 6, 8, 9, 11, 12 };
 527     VerifyUnackedPackets(unacked, arraysize(unacked));
 528     QuicPacketSequenceNumber retransmittable[] = { 6, 8, 9, 11, 12 };
 529     VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 530   }
 531
 532   RetransmitPacket(6, 14);
 533   manager_.OnSerializedPacket(CreateDataPacket(15));
 534   manager_.OnSerializedPacket(CreateDataPacket(16));
 535
 536   {
 537     // Ack packet 16.
 538     ReceivedPacketInfo received_info;
 539     received_info.largest_observed = 13;
 540     received_info.missing_packets.insert(2);
 541     received_info.missing_packets.insert(4);
 542     received_info.missing_packets.insert(6);
 543     received_info.missing_packets.insert(8);
 544     received_info.missing_packets.insert(9);
 545     received_info.missing_packets.insert(11);
 546     received_info.missing_packets.insert(12);
 547     received_info.is_truncated = true;
 548     manager_.OnIncomingAck(received_info, QuicTime::Zero());
 549
 550     // Truncated ack raises the high water mark by clearing out 2, 4, and 6.
 551     QuicPacketSequenceNumber unacked[] = { 8, 9, 11, 12, 14, 15, 16 };
 552     VerifyUnackedPackets(unacked, arraysize(unacked));
 553     QuicPacketSequenceNumber retransmittable[] = { 8, 9, 11, 12, 14, 15, 16 };
 554     VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 555   }
 556 }
 557
 558 TEST_F(QuicSentPacketManagerTest, GetLeastUnackedSentPacket) {
 559   EXPECT_CALL(helper_, GetNextPacketSequenceNumber()).WillOnce(Return(1u));
 560   EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
 561 }
 562
 563 TEST_F(QuicSentPacketManagerTest, GetLeastUnackedSentPacketUnacked) {
 564   SerializedPacket serialized_packet(CreateDataPacket(1));
 565
 566   manager_.OnSerializedPacket(serialized_packet);
 567   EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
 568 }
 569
 570 TEST_F(QuicSentPacketManagerTest, GetLeastUnackedSentPacketUnackedFec) {
 571   SerializedPacket serialized_packet(CreateFecPacket(1));
 572
 573   manager_.OnSerializedPacket(serialized_packet);
 574   EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
 575 }
 576
 577 TEST_F(QuicSentPacketManagerTest, GetLeastUnackedSentPacketDiscardUnacked) {
 578   SerializedPacket serialized_packet(CreateDataPacket(1));
 579
 580   manager_.OnSerializedPacket(serialized_packet);
 581   manager_.DiscardUnackedPacket(1u);
 582   EXPECT_CALL(helper_, GetNextPacketSequenceNumber()).WillOnce(Return(2u));
 583   EXPECT_EQ(2u, manager_.GetLeastUnackedSentPacket());
 584 }
 585
 586 TEST_F(QuicSentPacketManagerTest, GetLeastUnackedPacketAndDiscard) {
 587   VerifyUnackedPackets(NULL, 0);
 588
 589   SerializedPacket serialized_packet(CreateFecPacket(1));
 590   manager_.OnSerializedPacket(serialized_packet);
 591   EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
 592
 593   SerializedPacket serialized_packet2(CreateFecPacket(2));
 594   manager_.OnSerializedPacket(serialized_packet2);
 595   EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
 596
 597   SerializedPacket serialized_packet3(CreateFecPacket(3));
 598   manager_.OnSerializedPacket(serialized_packet3);
 599   EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
 600
 601   QuicPacketSequenceNumber unacked[] = { 1, 2, 3 };
 602   VerifyUnackedPackets(unacked, arraysize(unacked));
 603   VerifyRetransmittablePackets(NULL, 0);
 604
 605   manager_.DiscardUnackedPacket(1);
 606   EXPECT_EQ(2u, manager_.GetLeastUnackedSentPacket());
 607
 608   // Ack 2.
 609   ReceivedPacketInfo received_info;
 610   received_info.largest_observed = 2;
 611   manager_.OnIncomingAck(received_info, QuicTime::Zero());
 612
 613   EXPECT_EQ(3u, manager_.GetLeastUnackedSentPacket());
 614
 615   // Discard the 3rd packet and ensure there are no FEC packets.
 616   manager_.DiscardUnackedPacket(3);
 617   EXPECT_FALSE(manager_.HasUnackedPackets());
 618 }
 619
 620 TEST_F(QuicSentPacketManagerTest, GetSentTime) {
 621   VerifyUnackedPackets(NULL, 0);
 622
 623   SerializedPacket serialized_packet(CreateFecPacket(1));
 624   manager_.OnSerializedPacket(serialized_packet);
 625   EXPECT_CALL(*send_algorithm_, OnPacketSent(_, 1, _, _, _))
 626                   .Times(1).WillOnce(Return(true));
 627   manager_.OnPacketSent(
 628       1, QuicTime::Zero(), 0, NOT_RETRANSMISSION, NO_RETRANSMITTABLE_DATA);
 629
 630   SerializedPacket serialized_packet2(CreateFecPacket(2));
 631   QuicTime sent_time = QuicTime::Zero().Add(QuicTime::Delta::FromSeconds(1));
 632   manager_.OnSerializedPacket(serialized_packet2);
 633   EXPECT_CALL(*send_algorithm_, OnPacketSent(_, 2, _, _, _))
 634                   .Times(1).WillOnce(Return(true));
 635   manager_.OnPacketSent(
 636       2, sent_time, 0, NOT_RETRANSMISSION, NO_RETRANSMITTABLE_DATA);
 637
 638   QuicPacketSequenceNumber unacked[] = { 1, 2 };
 639   VerifyUnackedPackets(unacked, arraysize(unacked));
 640   VerifyRetransmittablePackets(NULL, 0);
 641
 642   EXPECT_TRUE(manager_.HasUnackedPackets());
 643   EXPECT_EQ(QuicTime::Zero(),
 644             QuicSentPacketManagerPeer::GetSentTime(&manager_, 1));
 645   EXPECT_EQ(sent_time, QuicSentPacketManagerPeer::GetSentTime(&manager_, 2));
 646 }
 647
 648 TEST_F(QuicSentPacketManagerTest, NackRetransmit1Packet) {
 649   const size_t kNumSentPackets = 4;
 650   // Transmit 4 packets.
 651   for (size_t i = 1; i <= kNumSentPackets; ++i) {
 652     SendDataPacket(i);
 653   }
 654   EXPECT_FALSE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
 655
 656   // Nack the first packet 3 times with increasing largest observed.
 657   ReceivedPacketInfo received_info;
 658   received_info.delta_time_largest_observed =
 659       QuicTime::Delta::FromMilliseconds(5);
 660   received_info.missing_packets.insert(1);
 661   for (QuicPacketSequenceNumber i = 1; i <= 3; ++i) {
 662     received_info.largest_observed = i + 1;
 663     EXPECT_CALL(*send_algorithm_, UpdateRtt(_));
 664     EXPECT_CALL(*send_algorithm_, OnPacketAcked(i + 1, _)).Times(1);
 665     if (i == 3) {
 666       EXPECT_CALL(*send_algorithm_, OnPacketLost(1, _)).Times(1);
 667       EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(1, _)).Times(1);
 668     }
 669     manager_.OnIncomingAck(received_info, clock_.Now());
 670     EXPECT_EQ(
 671         i == 3 ? 1u : 0u,
 672         QuicSentPacketManagerPeer::GetPendingRetransmissionCount(&manager_));
 673     EXPECT_EQ(i, QuicSentPacketManagerPeer::GetNackCount(&manager_, 1));
 674   }
 675 }
 676
 677 // A stretch ack is an ack that covers more than 1 packet of previously
 678 // unacknowledged data.
 679 TEST_F(QuicSentPacketManagerTest, NackRetransmit1PacketWith1StretchAck) {
 680   const size_t kNumSentPackets = 4;
 681   // Transmit 4 packets.
 682   for (size_t i = 1; i <= kNumSentPackets; ++i) {
 683     SendDataPacket(i);
 684   }
 685
 686   // Nack the first packet 3 times in a single StretchAck.
 687   ReceivedPacketInfo received_info;
 688   received_info.delta_time_largest_observed =
 689         QuicTime::Delta::FromMilliseconds(5);
 690   received_info.missing_packets.insert(1);
 691   received_info.largest_observed = kNumSentPackets;
 692   EXPECT_CALL(*send_algorithm_, UpdateRtt(_));
 693   EXPECT_CALL(*send_algorithm_, OnPacketAcked(_, _)).Times(3);
 694   EXPECT_CALL(*send_algorithm_, OnPacketLost(1, _)).Times(1);
 695   EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(1, _)).Times(1);
 696   manager_.OnIncomingAck(received_info, clock_.Now());
 697   EXPECT_EQ(
 698       1u, QuicSentPacketManagerPeer::GetPendingRetransmissionCount(&manager_));
 699   EXPECT_EQ(3u, QuicSentPacketManagerPeer::GetNackCount(&manager_, 1));
 700 }
 701
 702 // Ack a packet 3 packets ahead, causing a retransmit.
 703 TEST_F(QuicSentPacketManagerTest, NackRetransmit1PacketSingleAck) {
 704   const size_t kNumSentPackets = 5;
 705   // Transmit 5 packets.
 706   for (size_t i = 1; i <= kNumSentPackets; ++i) {
 707     SendDataPacket(i);
 708   }
 709
 710   // Nack the first packet 3 times in an AckFrame with three missing packets.
 711   ReceivedPacketInfo received_info;
 712   received_info.delta_time_largest_observed =
 713         QuicTime::Delta::FromMilliseconds(5);
 714   received_info.missing_packets.insert(1);
 715   received_info.missing_packets.insert(2);
 716   received_info.missing_packets.insert(3);
 717   received_info.largest_observed = 4;
 718   EXPECT_CALL(*send_algorithm_, UpdateRtt(_));
 719   EXPECT_CALL(*send_algorithm_, OnPacketAcked(4, _)).Times(1);
 720   EXPECT_CALL(*send_algorithm_, OnPacketLost(1, _)).Times(1);
 721   EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(1, _)).Times(1);
 722   manager_.OnIncomingAck(received_info, clock_.Now());
 723   EXPECT_EQ(
 724       1u, QuicSentPacketManagerPeer::GetPendingRetransmissionCount(&manager_));
 725   EXPECT_EQ(3u, QuicSentPacketManagerPeer::GetNackCount(&manager_, 1));
 726 }
 727
 728 TEST_F(QuicSentPacketManagerTest, EarlyRetransmit1Packet) {
 729   const size_t kNumSentPackets = 2;
 730   // Transmit 2 packets.
 731   for (size_t i = 1; i <= kNumSentPackets; ++i) {
 732     SendDataPacket(i);
 733   }
 734
 735   // Early retransmit when the final packet gets acked and the first is nacked.
 736   ReceivedPacketInfo received_info;
 737   received_info.delta_time_largest_observed =
 738       QuicTime::Delta::FromMilliseconds(5);
 739   received_info.missing_packets.insert(1);
 740   received_info.largest_observed = kNumSentPackets;
 741   EXPECT_CALL(*send_algorithm_, UpdateRtt(_));
 742   EXPECT_CALL(*send_algorithm_, OnPacketAcked(kNumSentPackets, _)).Times(1);
 743   EXPECT_CALL(*send_algorithm_, OnPacketLost(1, _)).Times(1);
 744   EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(1, _)).Times(1);
 745   manager_.OnIncomingAck(received_info, clock_.Now());
 746   EXPECT_EQ(
 747       1u, QuicSentPacketManagerPeer::GetPendingRetransmissionCount(&manager_));
 748   EXPECT_EQ(1u, QuicSentPacketManagerPeer::GetNackCount(&manager_, 1));
 749 }
 750
 751 TEST_F(QuicSentPacketManagerTest, DontEarlyRetransmitPacket) {
 752   const size_t kNumSentPackets = 5;
 753   for (size_t i = 1; i <= kNumSentPackets; ++i) {
 754     SendDataPacket(i);
 755   }
 756
 757   // Fast retransmit when the final packet gets acked, but don't early
 758   // retransmit as well, because there are 4 packets outstanding when the ack
 759   // arrives.
 760   ReceivedPacketInfo received_info;
 761   received_info.delta_time_largest_observed =
 762       QuicTime::Delta::FromMilliseconds(5);
 763   received_info.missing_packets.insert(1);
 764   received_info.missing_packets.insert(2);
 765   received_info.missing_packets.insert(3);
 766   received_info.missing_packets.insert(4);
 767   received_info.largest_observed = kNumSentPackets;
 768   EXPECT_CALL(*send_algorithm_, UpdateRtt(_));
 769   EXPECT_CALL(*send_algorithm_, OnPacketAcked(5, _)).Times(1);
 770   EXPECT_CALL(*send_algorithm_, OnPacketLost(_, _)).Times(2);
 771   EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(_, _)).Times(2);
 772   manager_.OnIncomingAck(received_info, clock_.Now());
 773   EXPECT_EQ(
 774       2u, QuicSentPacketManagerPeer::GetPendingRetransmissionCount(&manager_));
 775   EXPECT_EQ(4u, QuicSentPacketManagerPeer::GetNackCount(&manager_, 1));
 776 }
 777
 778 TEST_F(QuicSentPacketManagerTest, NackRetransmit2Packets) {
 779   const size_t kNumSentPackets = 20;
 780   // Transmit 20 packets.
 781   for (QuicPacketSequenceNumber i = 1; i <= kNumSentPackets; ++i) {
 782     SendDataPacket(i);
 783   }
 784
 785   // Nack the first 19 packets 3 times.
 786   ReceivedPacketInfo received_info;
 787   received_info.largest_observed = kNumSentPackets;
 788   received_info.delta_time_largest_observed =
 789       QuicTime::Delta::FromMilliseconds(5);
 790   for (size_t i = 1; i < kNumSentPackets; ++i) {
 791     received_info.missing_packets.insert(i);
 792   }
 793   EXPECT_CALL(*send_algorithm_, UpdateRtt(_));
 794   EXPECT_CALL(*send_algorithm_,
 795               OnPacketAcked(kNumSentPackets, _)).Times(1);
 796   EXPECT_CALL(*send_algorithm_, OnPacketLost(_, _)).Times(2);
 797   EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(_, _)).Times(2);
 798   manager_.OnIncomingAck(received_info, clock_.Now());
 799   EXPECT_EQ(
 800       2u, QuicSentPacketManagerPeer::GetPendingRetransmissionCount(&manager_));
 801   for (size_t i = 1; i < kNumSentPackets; ++i) {
 802     EXPECT_EQ(kNumSentPackets - i,
 803               QuicSentPacketManagerPeer::GetNackCount(&manager_, i));
 804   }
 805 }
 806
 807 TEST_F(QuicSentPacketManagerTest, NackRetransmit2PacketsAlternateAcks) {
 808   const size_t kNumSentPackets = 30;
 809   // Transmit 15 packets of data and 15 ack packets.  The send algorithm will
 810   // inform the congestion manager not to save the acks by returning false.
 811   for (QuicPacketSequenceNumber i = 1; i <= kNumSentPackets; ++i) {
 812     EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _))
 813                     .Times(1).WillOnce(Return(i % 2 == 0 ? false : true));
 814     SerializedPacket packet(CreatePacket(i, i % 2 == 1));
 815     manager_.OnSerializedPacket(packet);
 816     manager_.OnPacketSent(
 817         i, clock_.Now(), 1000, NOT_RETRANSMISSION,
 818         i % 2 == 0 ? NO_RETRANSMITTABLE_DATA : HAS_RETRANSMITTABLE_DATA);
 819   }
 820
 821   // Nack the first 29 packets 3 times.
 822   ReceivedPacketInfo received_info;
 823   received_info.largest_observed = kNumSentPackets;
 824   received_info.delta_time_largest_observed =
 825       QuicTime::Delta::FromMilliseconds(5);
 826   for (size_t i = 1; i < kNumSentPackets; ++i) {
 827     received_info.missing_packets.insert(i);
 828   }
 829   // We never actually get an ack call, since the kNumSentPackets packet was
 830   // not saved.
 831   EXPECT_CALL(*send_algorithm_, OnPacketLost(_, _)).Times(2);
 832   EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(_, _)).Times(2);
 833   manager_.OnIncomingAck(received_info, clock_.Now());
 834   ASSERT_EQ(
 835       2u, QuicSentPacketManagerPeer::GetPendingRetransmissionCount(&manager_));
 836   // Only non-ack packets have a nack count.
 837   for (size_t i = 1; i < kNumSentPackets; i += 2) {
 838     EXPECT_EQ(kNumSentPackets - i,
 839               QuicSentPacketManagerPeer::GetNackCount(&manager_, i));
 840   }
 841
 842   // Ensure only the odd packets were retransmitted, since the others were not
 843   // retransmittable(ie: acks).
 844   EXPECT_EQ(1u, manager_.NextPendingRetransmission().sequence_number);
 845   manager_.OnRetransmittedPacket(1u, kNumSentPackets + 1);
 846   EXPECT_EQ(3u, manager_.NextPendingRetransmission().sequence_number);
 847 }
 848
 849 TEST_F(QuicSentPacketManagerTest, NackTwiceThenAck) {
 850   // Transmit 4 packets.
 851   for (QuicPacketSequenceNumber i = 1; i <= 4; ++i) {
 852     SendDataPacket(i);
 853   }
 854
 855   // Nack the first packet 2 times, then ack it.
 856   ReceivedPacketInfo received_info;
 857   received_info.missing_packets.insert(1);
 858   for (size_t i = 1; i <= 3; ++i) {
 859     if (i == 3) {
 860       received_info.missing_packets.clear();
 861     }
 862     received_info.largest_observed = i + 1;
 863     received_info.delta_time_largest_observed =
 864         QuicTime::Delta::FromMilliseconds(5);
 865     EXPECT_CALL(*send_algorithm_, UpdateRtt(_));
 866     EXPECT_CALL(*send_algorithm_,
 867                 OnPacketAcked(_, _)).Times(i == 3 ? 2 : 1);
 868     manager_.OnIncomingAck(received_info, clock_.Now());
 869     EXPECT_FALSE(manager_.HasPendingRetransmissions());
 870     // The nack count remains at 2 when the packet is acked.
 871     EXPECT_EQ(i == 3 ? 2u : i,
 872               QuicSentPacketManagerPeer::GetNackCount(&manager_, 1));
 873   }
 874 }
 875
 876 TEST_F(QuicSentPacketManagerTest, Rtt) {
 877   QuicPacketSequenceNumber sequence_number = 1;
 878   QuicTime::Delta expected_rtt = QuicTime::Delta::FromMilliseconds(15);
 879   SendDataPacket(sequence_number);
 880   clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(20));
 881
 882   EXPECT_CALL(*send_algorithm_, UpdateRtt(expected_rtt));
 883   EXPECT_CALL(*send_algorithm_,
 884               OnPacketAcked(sequence_number, _)).Times(1);
 885   ReceivedPacketInfo received_info;
 886   received_info.largest_observed = sequence_number;
 887   received_info.delta_time_largest_observed =
 888       QuicTime::Delta::FromMilliseconds(5);
 889   manager_.OnIncomingAck(received_info, clock_.Now());
 890   EXPECT_EQ(expected_rtt, QuicSentPacketManagerPeer::rtt(&manager_));
 891 }
 892
 893 TEST_F(QuicSentPacketManagerTest, RttWithInvalidDelta) {
 894   // Expect that the RTT is equal to the local time elapsed, since the
 895   // delta_time_largest_observed is larger than the local time elapsed
 896   // and is hence invalid.
 897   QuicPacketSequenceNumber sequence_number = 1;
 898   QuicTime::Delta expected_rtt = QuicTime::Delta::FromMilliseconds(10);
 899   SendDataPacket(sequence_number);
 900   clock_.AdvanceTime(expected_rtt);
 901
 902   EXPECT_CALL(*send_algorithm_, UpdateRtt(expected_rtt));
 903   EXPECT_CALL(*send_algorithm_,
 904               OnPacketAcked(sequence_number, _)).Times(1);
 905   ReceivedPacketInfo received_info;
 906   received_info.largest_observed = sequence_number;
 907   received_info.delta_time_largest_observed =
 908       QuicTime::Delta::FromMilliseconds(11);
 909   manager_.OnIncomingAck(received_info, clock_.Now());
 910   EXPECT_EQ(expected_rtt, QuicSentPacketManagerPeer::rtt(&manager_));
 911 }
 912
 913 TEST_F(QuicSentPacketManagerTest, RttWithInfiniteDelta) {
 914   // Expect that the RTT is equal to the local time elapsed, since the
 915   // delta_time_largest_observed is infinite, and is hence invalid.
 916   QuicPacketSequenceNumber sequence_number = 1;
 917   QuicTime::Delta expected_rtt = QuicTime::Delta::FromMilliseconds(10);
 918   SendDataPacket(sequence_number);
 919   clock_.AdvanceTime(expected_rtt);
 920
 921   EXPECT_CALL(*send_algorithm_, UpdateRtt(expected_rtt));
 922   EXPECT_CALL(*send_algorithm_,
 923               OnPacketAcked(sequence_number, _)).Times(1);
 924   ReceivedPacketInfo received_info;
 925   received_info.largest_observed = sequence_number;
 926   received_info.delta_time_largest_observed = QuicTime::Delta::Infinite();
 927   manager_.OnIncomingAck(received_info, clock_.Now());
 928   EXPECT_EQ(expected_rtt, QuicSentPacketManagerPeer::rtt(&manager_));
 929 }
 930
 931 TEST_F(QuicSentPacketManagerTest, RttZeroDelta) {
 932   // Expect that the RTT is the time between send and receive since the
 933   // delta_time_largest_observed is zero.
 934   QuicPacketSequenceNumber sequence_number = 1;
 935   QuicTime::Delta expected_rtt = QuicTime::Delta::FromMilliseconds(10);
 936   SendDataPacket(sequence_number);
 937   clock_.AdvanceTime(expected_rtt);
 938
 939   EXPECT_CALL(*send_algorithm_, UpdateRtt(expected_rtt));
 940   EXPECT_CALL(*send_algorithm_, OnPacketAcked(sequence_number, _))
 941       .Times(1);
 942   ReceivedPacketInfo received_info;
 943   received_info.largest_observed = sequence_number;
 944   received_info.delta_time_largest_observed = QuicTime::Delta::Zero();
 945   manager_.OnIncomingAck(received_info, clock_.Now());
 946   EXPECT_EQ(expected_rtt, QuicSentPacketManagerPeer::rtt(&manager_));
 947 }
 948
 949 TEST_F(QuicSentPacketManagerTest, TailLossProbeTimeout) {
 950   QuicSentPacketManagerPeer::SetMaxTailLossProbes(&manager_, 2);
 951
 952   // Send 1 packet.
 953   QuicPacketSequenceNumber sequence_number = 1;
 954   SendDataPacket(sequence_number);
 955
 956   // The first tail loss probe retransmits 1 packet.
 957   manager_.OnRetransmissionTimeout();
 958   RetransmitNextPacket(2);
 959   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 960
 961   // The second tail loss probe retransmits 1 packet.
 962   manager_.OnRetransmissionTimeout();
 963   RetransmitNextPacket(3);
 964   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 965
 966   // Ack the third and ensure the first two are considered lost, but they were
 967   // already abandoned, so that won't occur again.
 968   EXPECT_CALL(*send_algorithm_, UpdateRtt(_));
 969   EXPECT_CALL(*send_algorithm_, OnPacketAcked(3, _));
 970   EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(_, _)).Times(2);
 971   EXPECT_CALL(*send_algorithm_, OnPacketLost(_, _)).Times(2);
 972   ReceivedPacketInfo received_info;
 973   received_info.largest_observed = 3;
 974   received_info.missing_packets.insert(1);
 975   received_info.missing_packets.insert(2);
 976   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 977
 978   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 979 }
 980
 981 TEST_F(QuicSentPacketManagerTest, TailLossProbeThenRTO) {
 982   QuicSentPacketManagerPeer::SetMaxTailLossProbes(&manager_, 2);
 983
 984   // Send 100 packets.
 985   const size_t kNumSentPackets = 100;
 986   for (size_t i = 1; i <= kNumSentPackets; ++i) {
 987     SendDataPacket(i);
 988   }
 989
 990   // The first tail loss probe retransmits 1 packet.
 991   manager_.OnRetransmissionTimeout();
 992   RetransmitNextPacket(101);
 993   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 994
 995   // The second tail loss probe retransmits 1 packet.
 996   manager_.OnRetransmissionTimeout();
 997   RetransmitNextPacket(102);
 998   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 999
1000   // Advance the time enough to ensure all packets are RTO'd.
1001   clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(1000));
1002
1003   // The final RTO abandons all of them.
1004   EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout(true));
1005   manager_.OnRetransmissionTimeout();
1006   EXPECT_TRUE(manager_.HasPendingRetransmissions());
1007 }
1008
1009 TEST_F(QuicSentPacketManagerTest, CryptoHandshakeTimeout) {
1010   // Send 2 crypto packets and 3 data packets.
1011   const size_t kNumSentCryptoPackets = 2;
1012   for (size_t i = 1; i <= kNumSentCryptoPackets; ++i) {
1013     SendCryptoPacket(i);
1014   }
1015   const size_t kNumSentDataPackets = 3;
1016   for (size_t i = 1; i <= kNumSentDataPackets; ++i) {
1017     SendDataPacket(kNumSentCryptoPackets + i);
1018   }
1019   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
1020
1021   // The first retransmits 2 packets.
1022   EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(_, _)).Times(2);
1023   manager_.OnRetransmissionTimeout();
1024   RetransmitNextPacket(6);
1025   RetransmitNextPacket(7);
1026   EXPECT_FALSE(manager_.HasPendingRetransmissions());
1027   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
1028
1029   // The second retransmits 2 packets.
1030   EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(_, _)).Times(2);
1031   manager_.OnRetransmissionTimeout();
1032   RetransmitNextPacket(8);
1033   RetransmitNextPacket(9);
1034   EXPECT_FALSE(manager_.HasPendingRetransmissions());
1035   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
1036
1037   // Now ack the two crypto packets and the speculatively encrypted request,
1038   // and ensure the first four crypto packets get abandoned, but not lost.
1039   EXPECT_CALL(*send_algorithm_, UpdateRtt(_));
1040   EXPECT_CALL(*send_algorithm_, OnPacketAcked(_, _)).Times(5);
1041   ReceivedPacketInfo received_info;
1042   received_info.largest_observed = 9;
1043   received_info.missing_packets.insert(1);
1044   received_info.missing_packets.insert(2);
1045   received_info.missing_packets.insert(6);
1046   received_info.missing_packets.insert(7);
1047   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
1048
1049   EXPECT_FALSE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
1050 }
1051
1052 TEST_F(QuicSentPacketManagerTest, CryptoHandshakeTimeoutUnsentDataPacket) {
1053   // Send 2 crypto packets and serialize 1 data packet.
1054   const size_t kNumSentCryptoPackets = 2;
1055   for (size_t i = 1; i <= kNumSentCryptoPackets; ++i) {
1056     SendCryptoPacket(i);
1057   }
1058   SerializedPacket packet(CreateDataPacket(3));
1059   manager_.OnSerializedPacket(packet);
1060   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
1061
1062   // Retransmit 2 crypto packets, but not the serialized packet.
1063   EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(_, _)).Times(2);
1064   manager_.OnRetransmissionTimeout();
1065   RetransmitNextPacket(6);
1066   RetransmitNextPacket(7);
1067   EXPECT_FALSE(manager_.HasPendingRetransmissions());
1068   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
1069 }
1070
1071 TEST_F(QuicSentPacketManagerTest, TailLossProbeTimeoutUnsentDataPacket) {
1072   QuicSentPacketManagerPeer::SetMaxTailLossProbes(&manager_, 2);
1073   // Serialize two data packets and send the latter.
1074   SerializedPacket packet(CreateDataPacket(1));
1075   manager_.OnSerializedPacket(packet);
1076   SendDataPacket(2);
1077   EXPECT_FALSE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
1078   EXPECT_TRUE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
1079
1080   // Retransmit 1 unacked packets, but not the first serialized packet.
1081   manager_.OnRetransmissionTimeout();
1082   RetransmitNextPacket(3);
1083   EXPECT_FALSE(manager_.HasPendingRetransmissions());
1084   EXPECT_FALSE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
1085   EXPECT_TRUE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
1086 }
1087
1088 TEST_F(QuicSentPacketManagerTest, RetransmissionTimeout) {
1089   // Send 100 packets and then ensure all are abandoned when the RTO fires.
1090   const size_t kNumSentPackets = 100;
1091   for (size_t i = 1; i <= kNumSentPackets; ++i) {
1092     SendDataPacket(i);
1093   }
1094
1095   EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout(true));
1096   manager_.OnRetransmissionTimeout();
1097 }
1098
1099 TEST_F(QuicSentPacketManagerTest, GetTransmissionTime) {
1100   EXPECT_EQ(QuicTime::Zero(), manager_.GetRetransmissionTime());
1101 }
1102
1103 TEST_F(QuicSentPacketManagerTest, GetTransmissionTimeCryptoHandshake) {
1104   SendCryptoPacket(1);
1105
1106   // Check the min.
1107   EXPECT_CALL(*send_algorithm_, SmoothedRtt())
1108       .WillRepeatedly(Return(QuicTime::Delta::FromMilliseconds(1)));
1109   EXPECT_EQ(clock_.Now().Add(QuicTime::Delta::FromMilliseconds(10)),
1110             manager_.GetRetransmissionTime());
1111
1112   // Test with a standard smoothed RTT.
1113   EXPECT_CALL(*send_algorithm_, SmoothedRtt())
1114       .WillRepeatedly(Return(QuicTime::Delta::FromMilliseconds(100)));
1115
1116   QuicTime::Delta srtt = manager_.SmoothedRtt();
1117   QuicTime expected_time = clock_.Now().Add(QuicTime::Delta::FromMilliseconds(
1118       static_cast<int64>(1.5 * srtt.ToMilliseconds())));
1119   EXPECT_EQ(expected_time, manager_.GetRetransmissionTime());
1120
1121   // Retransmit the packet by invoking the retransmission timeout.
1122   clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(
1123       static_cast<int64>(1.5 * srtt.ToMilliseconds())));
1124   EXPECT_CALL(*send_algorithm_, OnPacketAbandoned(_, _));
1125   manager_.OnRetransmissionTimeout();
1126   RetransmitNextPacket(2);
1127
1128   // The retransmission time should now be twice as far in the future.
1129   expected_time = clock_.Now().Add(QuicTime::Delta::FromMilliseconds(
1130         static_cast<int64>(2 * 1.5 * srtt.ToMilliseconds())));
1131   EXPECT_EQ(expected_time, manager_.GetRetransmissionTime());
1132 }
1133
1134 TEST_F(QuicSentPacketManagerTest, GetTransmissionTimeTailLossProbe) {
1135   QuicSentPacketManagerPeer::SetMaxTailLossProbes(&manager_, 2);
1136   SendDataPacket(1);
1137   SendDataPacket(2);
1138
1139   // Check the min.
1140   EXPECT_CALL(*send_algorithm_, SmoothedRtt())
1141       .WillRepeatedly(Return(QuicTime::Delta::FromMilliseconds(1)));
1142   EXPECT_EQ(clock_.Now().Add(QuicTime::Delta::FromMilliseconds(10)),
1143             manager_.GetRetransmissionTime());
1144
1145   // Test with a standard smoothed RTT.
1146   EXPECT_CALL(*send_algorithm_, SmoothedRtt())
1147       .WillRepeatedly(Return(QuicTime::Delta::FromMilliseconds(100)));
1148   QuicTime::Delta srtt = manager_.SmoothedRtt();
1149   QuicTime::Delta expected_tlp_delay = QuicTime::Delta::FromMilliseconds(
1150       static_cast<int64>(2 * srtt.ToMilliseconds()));
1151   QuicTime expected_time = clock_.Now().Add(expected_tlp_delay);
1152   EXPECT_EQ(expected_time, manager_.GetRetransmissionTime());
1153
1154   // Retransmit the packet by invoking the retransmission timeout.
1155   clock_.AdvanceTime(expected_tlp_delay);
1156   manager_.OnRetransmissionTimeout();
1157   RetransmitNextPacket(3);
1158   EXPECT_FALSE(manager_.HasPendingRetransmissions());
1159
1160   expected_time = clock_.Now().Add(expected_tlp_delay);
1161   EXPECT_EQ(expected_time, manager_.GetRetransmissionTime());
1162 }
1163
1164 TEST_F(QuicSentPacketManagerTest, GetTransmissionTimeRTO) {
1165   EXPECT_CALL(*send_algorithm_, SmoothedRtt())
1166       .WillRepeatedly(Return(QuicTime::Delta::FromMilliseconds(100)));
1167
1168   SendDataPacket(1);
1169   SendDataPacket(2);
1170
1171   QuicTime::Delta expected_rto_delay = QuicTime::Delta::FromMilliseconds(500);
1172   EXPECT_CALL(*send_algorithm_, RetransmissionDelay())
1173       .WillRepeatedly(Return(expected_rto_delay));
1174   QuicTime expected_time = clock_.Now().Add(expected_rto_delay);
1175   EXPECT_EQ(expected_time, manager_.GetRetransmissionTime());
1176
1177   // Retransmit the packet by invoking the retransmission timeout.
1178   EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout(true));
1179   clock_.AdvanceTime(expected_rto_delay);
1180   manager_.OnRetransmissionTimeout();
1181   RetransmitNextPacket(3);
1182   RetransmitNextPacket(4);
1183   EXPECT_FALSE(manager_.HasPendingRetransmissions());
1184
1185   // The delay should double the second time.
1186   expected_time = clock_.Now().Add(expected_rto_delay).Add(expected_rto_delay);
1187   EXPECT_EQ(expected_time, manager_.GetRetransmissionTime());
1188
1189   // Ack a packet and ensure the RTO goes back to the original value.
1190   ReceivedPacketInfo received_info;
1191   received_info.largest_observed = 2;
1192   received_info.missing_packets.insert(1);
1193   EXPECT_CALL(*send_algorithm_, UpdateRtt(_));
1194   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
1195
1196   expected_time = clock_.Now().Add(expected_rto_delay);
1197   EXPECT_EQ(expected_time, manager_.GetRetransmissionTime());
1198 }
1199
1200 TEST_F(QuicSentPacketManagerTest, GetTransmissionDelayMin) {
1201   EXPECT_CALL(*send_algorithm_, RetransmissionDelay())
1202       .WillOnce(Return(QuicTime::Delta::FromMilliseconds(1)));
1203
1204   EXPECT_EQ(QuicTime::Delta::FromMilliseconds(200),
1205             QuicSentPacketManagerPeer::GetRetransmissionDelay(&manager_));
1206 }
1207
1208 TEST_F(QuicSentPacketManagerTest, GetTransmissionDelayMax) {
1209   EXPECT_CALL(*send_algorithm_, RetransmissionDelay())
1210       .WillOnce(Return(QuicTime::Delta::FromSeconds(500)));
1211
1212   EXPECT_EQ(QuicTime::Delta::FromSeconds(60),
1213             QuicSentPacketManagerPeer::GetRetransmissionDelay(&manager_));
1214 }
1215
1216 TEST_F(QuicSentPacketManagerTest, GetTransmissionDelay) {
1217   SendDataPacket(1);
1218   QuicTime::Delta delay = QuicTime::Delta::FromMilliseconds(500);
1219   EXPECT_CALL(*send_algorithm_, RetransmissionDelay())
1220       .WillRepeatedly(Return(delay));
1221
1222   // Delay should back off exponentially.
1223   for (int i = 0; i < 5; ++i) {
1224     EXPECT_EQ(delay,
1225               QuicSentPacketManagerPeer::GetRetransmissionDelay(&manager_));
1226     delay = delay.Add(delay);
1227     EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout(true));
1228     manager_.OnRetransmissionTimeout();
1229     RetransmitNextPacket(i + 2);
1230   }
1231 }
1232
1233 }  // namespace
1234 }  // namespace test
1235 }  // namespace net