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