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/quic_flags.h"
   9 #include "net/quic/test_tools/quic_config_peer.h"
  10 #include "net/quic/test_tools/quic_sent_packet_manager_peer.h"
  11 #include "net/quic/test_tools/quic_test_utils.h"
  12 #include "testing/gmock/include/gmock/gmock.h"
  13 #include "testing/gtest/include/gtest/gtest.h"
  14
  15 using std::vector;
  16 using testing::ElementsAre;
  17 using testing::Pair;
  18 using testing::Pointwise;
  19 using testing::Return;
  20 using testing::StrictMock;
  21 using testing::_;
  22
  23 namespace net {
  24 namespace test {
  25 namespace {
  26
  27 // Default packet length.
  28 const uint32 kDefaultLength = 1000;
  29
  30 // Matcher to check the key of the key-value pair it receives as first argument
  31 // equals its second argument.
  32 MATCHER(KeyEq, "") {
  33   return std::tr1::get<0>(arg).first == std::tr1::get<1>(arg);
  34 }
  35
  36 class MockDebugDelegate : public QuicSentPacketManager::DebugDelegate {
  37  public:
  38   MOCK_METHOD2(OnSpuriousPacketRetransmition,
  39                void(TransmissionType transmission_type,
  40                     QuicByteCount byte_size));
  41 };
  42
  43 class QuicSentPacketManagerTest : public ::testing::TestWithParam<bool> {
  44  protected:
  45   QuicSentPacketManagerTest()
  46       : manager_(true, &clock_, &stats_, kFixRate, kNack),
  47         send_algorithm_(new StrictMock<MockSendAlgorithm>) {
  48     QuicSentPacketManagerPeer::SetSendAlgorithm(&manager_, send_algorithm_);
  49     // Disable tail loss probes for most tests.
  50     QuicSentPacketManagerPeer::SetMaxTailLossProbes(&manager_, 0);
  51     // Advance the time 1s so the send times are never QuicTime::Zero.
  52     clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(1000));
  53   }
  54
  55   virtual ~QuicSentPacketManagerTest() OVERRIDE {
  56     STLDeleteElements(&packets_);
  57   }
  58
  59   QuicByteCount BytesInFlight() {
  60     return QuicSentPacketManagerPeer::GetBytesInFlight(&manager_);
  61   }
  62   void VerifyUnackedPackets(QuicPacketSequenceNumber* packets,
  63                             size_t num_packets) {
  64     if (num_packets == 0) {
  65       EXPECT_FALSE(manager_.HasUnackedPackets());
  66       EXPECT_EQ(0u, QuicSentPacketManagerPeer::GetNumRetransmittablePackets(
  67           &manager_));
  68       return;
  69     }
  70
  71     EXPECT_TRUE(manager_.HasUnackedPackets());
  72     EXPECT_EQ(packets[0], manager_.GetLeastUnackedSentPacket());
  73     for (size_t i = 0; i < num_packets; ++i) {
  74       EXPECT_TRUE(manager_.IsUnacked(packets[i])) << packets[i];
  75     }
  76   }
  77
  78   void VerifyRetransmittablePackets(QuicPacketSequenceNumber* packets,
  79                                     size_t num_packets) {
  80     EXPECT_EQ(num_packets,
  81               QuicSentPacketManagerPeer::GetNumRetransmittablePackets(
  82                   &manager_));
  83     for (size_t i = 0; i < num_packets; ++i) {
  84       EXPECT_TRUE(manager_.HasRetransmittableFrames(packets[i]))
  85           << " packets[" << i << "]:" << packets[i];
  86     }
  87   }
  88
  89   void ExpectAck(QuicPacketSequenceNumber largest_observed) {
  90     EXPECT_CALL(*send_algorithm_, OnCongestionEvent(
  91         true, _, ElementsAre(Pair(largest_observed, _)), _));
  92   }
  93
  94   void ExpectUpdatedRtt(QuicPacketSequenceNumber largest_observed) {
  95     EXPECT_CALL(*send_algorithm_,
  96                 OnCongestionEvent(true, _, _, _));
  97   }
  98
  99   void ExpectAckAndLoss(bool rtt_updated,
 100                         QuicPacketSequenceNumber largest_observed,
 101                         QuicPacketSequenceNumber lost_packet) {
 102     EXPECT_CALL(*send_algorithm_, OnCongestionEvent(
 103         rtt_updated, _, ElementsAre(Pair(largest_observed, _)),
 104         ElementsAre(Pair(lost_packet, _))));
 105   }
 106
 107   // |packets_acked| and |packets_lost| should be in sequence number order.
 108   void ExpectAcksAndLosses(bool rtt_updated,
 109                            QuicPacketSequenceNumber* packets_acked,
 110                            size_t num_packets_acked,
 111                            QuicPacketSequenceNumber* packets_lost,
 112                            size_t num_packets_lost) {
 113     vector<QuicPacketSequenceNumber> ack_vector;
 114     for (size_t i = 0; i < num_packets_acked; ++i) {
 115       ack_vector.push_back(packets_acked[i]);
 116     }
 117     vector<QuicPacketSequenceNumber> lost_vector;
 118     for (size_t i = 0; i < num_packets_lost; ++i) {
 119       lost_vector.push_back(packets_lost[i]);
 120     }
 121     EXPECT_CALL(*send_algorithm_,
 122                 OnCongestionEvent(rtt_updated, _,
 123                                   Pointwise(KeyEq(), ack_vector),
 124                                   Pointwise(KeyEq(), lost_vector)));
 125   }
 126
 127   // Retransmits a packet as though it was a TLP retransmission, because TLP
 128   // leaves the |old_sequence_number| pending.
 129   // TODO(ianswett): Test with transmission types besides TLP.
 130   void RetransmitPacket(QuicPacketSequenceNumber old_sequence_number,
 131                         QuicPacketSequenceNumber new_sequence_number) {
 132     QuicSentPacketManagerPeer::MarkForRetransmission(
 133         &manager_, old_sequence_number, TLP_RETRANSMISSION);
 134     EXPECT_TRUE(manager_.HasPendingRetransmissions());
 135     QuicSentPacketManager::PendingRetransmission next_retransmission =
 136         manager_.NextPendingRetransmission();
 137     EXPECT_EQ(old_sequence_number, next_retransmission.sequence_number);
 138     EXPECT_EQ(TLP_RETRANSMISSION,
 139               next_retransmission.transmission_type);
 140     manager_.OnRetransmittedPacket(old_sequence_number,
 141                                    new_sequence_number);
 142     EXPECT_TRUE(QuicSentPacketManagerPeer::IsRetransmission(
 143         &manager_, new_sequence_number));
 144   }
 145
 146   void RetransmitAndSendPacket(QuicPacketSequenceNumber old_sequence_number,
 147                                QuicPacketSequenceNumber new_sequence_number) {
 148     RetransmitPacket(old_sequence_number, new_sequence_number);
 149
 150     EXPECT_CALL(*send_algorithm_,
 151                 OnPacketSent(_, BytesInFlight(), new_sequence_number,
 152                              kDefaultLength, HAS_RETRANSMITTABLE_DATA))
 153         .WillOnce(Return(true));
 154     manager_.OnPacketSent(new_sequence_number,
 155                           clock_.Now(),
 156                           kDefaultLength,
 157                           LOSS_RETRANSMISSION,
 158                           HAS_RETRANSMITTABLE_DATA);
 159   }
 160
 161   SerializedPacket CreateDataPacket(QuicPacketSequenceNumber sequence_number) {
 162     return CreatePacket(sequence_number, true);
 163   }
 164
 165   SerializedPacket CreatePacket(QuicPacketSequenceNumber sequence_number,
 166                                 bool retransmittable) {
 167     packets_.push_back(QuicPacket::NewDataPacket(
 168         NULL, kDefaultLength, false, PACKET_8BYTE_CONNECTION_ID, false,
 169         PACKET_6BYTE_SEQUENCE_NUMBER));
 170     return SerializedPacket(
 171         sequence_number, PACKET_6BYTE_SEQUENCE_NUMBER,
 172         packets_.back(), 0u,
 173         retransmittable ? new RetransmittableFrames() : NULL);
 174   }
 175
 176   SerializedPacket CreateFecPacket(QuicPacketSequenceNumber sequence_number) {
 177     packets_.push_back(QuicPacket::NewFecPacket(
 178         NULL, kDefaultLength, false, PACKET_8BYTE_CONNECTION_ID, false,
 179         PACKET_6BYTE_SEQUENCE_NUMBER));
 180     return SerializedPacket(sequence_number, PACKET_6BYTE_SEQUENCE_NUMBER,
 181                             packets_.back(), 0u, NULL);
 182   }
 183
 184   void SendDataPacket(QuicPacketSequenceNumber sequence_number) {
 185     EXPECT_CALL(*send_algorithm_,
 186                 OnPacketSent(_, BytesInFlight(), sequence_number, _, _))
 187                     .Times(1).WillOnce(Return(true));
 188     SerializedPacket packet(CreateDataPacket(sequence_number));
 189     manager_.OnSerializedPacket(packet);
 190     manager_.OnPacketSent(sequence_number, clock_.Now(),
 191                           packet.packet->length(), NOT_RETRANSMISSION,
 192                           HAS_RETRANSMITTABLE_DATA);
 193   }
 194
 195   void SendCryptoPacket(QuicPacketSequenceNumber sequence_number) {
 196     EXPECT_CALL(*send_algorithm_,
 197                 OnPacketSent(_, BytesInFlight(), sequence_number,
 198                              kDefaultLength, HAS_RETRANSMITTABLE_DATA))
 199                     .Times(1).WillOnce(Return(true));
 200     SerializedPacket packet(CreateDataPacket(sequence_number));
 201     packet.retransmittable_frames->AddStreamFrame(
 202         new QuicStreamFrame(1, false, 0, IOVector()));
 203     packet.retransmittable_frames->set_encryption_level(ENCRYPTION_NONE);
 204     manager_.OnSerializedPacket(packet);
 205     manager_.OnPacketSent(sequence_number, clock_.ApproximateNow(),
 206                           packet.packet->length(), NOT_RETRANSMISSION,
 207                           HAS_RETRANSMITTABLE_DATA);
 208   }
 209
 210   void SendFecPacket(QuicPacketSequenceNumber sequence_number) {
 211     EXPECT_CALL(*send_algorithm_,
 212                 OnPacketSent(_, BytesInFlight(), sequence_number,
 213                              kDefaultLength, NO_RETRANSMITTABLE_DATA))
 214                     .Times(1).WillOnce(Return(true));
 215     SerializedPacket packet(CreateFecPacket(sequence_number));
 216     manager_.OnSerializedPacket(packet);
 217     manager_.OnPacketSent(sequence_number, clock_.ApproximateNow(),
 218                           packet.packet->length(), NOT_RETRANSMISSION,
 219                           NO_RETRANSMITTABLE_DATA);
 220   }
 221
 222   void SendAckPacket(QuicPacketSequenceNumber sequence_number) {
 223     EXPECT_CALL(*send_algorithm_,
 224                 OnPacketSent(_, BytesInFlight(), sequence_number,
 225                              kDefaultLength, NO_RETRANSMITTABLE_DATA))
 226                     .Times(1).WillOnce(Return(false));
 227     SerializedPacket packet(CreatePacket(sequence_number, false));
 228     manager_.OnSerializedPacket(packet);
 229     manager_.OnPacketSent(sequence_number, clock_.Now(),
 230                           packet.packet->length(), NOT_RETRANSMISSION,
 231                           NO_RETRANSMITTABLE_DATA);
 232   }
 233
 234   // Based on QuicConnection's WritePendingRetransmissions.
 235   void RetransmitNextPacket(
 236       QuicPacketSequenceNumber retransmission_sequence_number) {
 237     EXPECT_TRUE(manager_.HasPendingRetransmissions());
 238     EXPECT_CALL(*send_algorithm_,
 239                 OnPacketSent(_, _, retransmission_sequence_number,
 240                              kDefaultLength, HAS_RETRANSMITTABLE_DATA))
 241                     .Times(1).WillOnce(Return(true));
 242     const QuicSentPacketManager::PendingRetransmission pending =
 243         manager_.NextPendingRetransmission();
 244     manager_.OnRetransmittedPacket(pending.sequence_number,
 245                                    retransmission_sequence_number);
 246     manager_.OnPacketSent(retransmission_sequence_number, clock_.Now(),
 247                           kDefaultLength, pending.transmission_type,
 248                           HAS_RETRANSMITTABLE_DATA);
 249   }
 250
 251   QuicSentPacketManager manager_;
 252   vector<QuicPacket*> packets_;
 253   MockClock clock_;
 254   QuicConnectionStats stats_;
 255   MockSendAlgorithm* send_algorithm_;
 256 };
 257
 258 TEST_F(QuicSentPacketManagerTest, IsUnacked) {
 259   VerifyUnackedPackets(NULL, 0);
 260
 261   SerializedPacket serialized_packet(CreateDataPacket(1));
 262
 263   manager_.OnSerializedPacket(serialized_packet);
 264
 265   QuicPacketSequenceNumber unacked[] = { 1 };
 266   VerifyUnackedPackets(unacked, arraysize(unacked));
 267   QuicPacketSequenceNumber retransmittable[] = { 1 };
 268   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 269 }
 270
 271 TEST_F(QuicSentPacketManagerTest, IsUnAckedRetransmit) {
 272   SendDataPacket(1);
 273   RetransmitPacket(1, 2);
 274
 275   EXPECT_TRUE(QuicSentPacketManagerPeer::IsRetransmission(&manager_, 2));
 276   QuicPacketSequenceNumber unacked[] = { 1, 2 };
 277   VerifyUnackedPackets(unacked, arraysize(unacked));
 278   QuicPacketSequenceNumber retransmittable[] = { 2 };
 279   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 280 }
 281
 282 TEST_F(QuicSentPacketManagerTest, RetransmitThenAck) {
 283   SendDataPacket(1);
 284   RetransmitAndSendPacket(1, 2);
 285
 286   // Ack 2 but not 1.
 287   ReceivedPacketInfo received_info;
 288   received_info.largest_observed = 2;
 289   received_info.missing_packets.insert(1);
 290   ExpectAck(2);
 291   manager_.OnIncomingAck(received_info, clock_.Now());
 292
 293   // Packet 1 is unacked, pending, but not retransmittable.
 294   QuicPacketSequenceNumber unacked[] = { 1 };
 295   VerifyUnackedPackets(unacked, arraysize(unacked));
 296   EXPECT_TRUE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 297   VerifyRetransmittablePackets(NULL, 0);
 298 }
 299
 300 TEST_F(QuicSentPacketManagerTest, RetransmitThenAckBeforeSend) {
 301   SendDataPacket(1);
 302   QuicSentPacketManagerPeer::MarkForRetransmission(
 303       &manager_, 1, TLP_RETRANSMISSION);
 304   EXPECT_TRUE(manager_.HasPendingRetransmissions());
 305
 306   // Ack 1.
 307   ReceivedPacketInfo received_info;
 308   received_info.largest_observed = 1;
 309   ExpectAck(1);
 310   manager_.OnIncomingAck(received_info, clock_.Now());
 311
 312   // There should no longer be a pending retransmission.
 313   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 314
 315   // No unacked packets remain.
 316   VerifyUnackedPackets(NULL, 0);
 317   VerifyRetransmittablePackets(NULL, 0);
 318   EXPECT_EQ(0u, stats_.packets_spuriously_retransmitted);
 319 }
 320
 321 TEST_F(QuicSentPacketManagerTest, RetransmitThenAckPrevious) {
 322   SendDataPacket(1);
 323   RetransmitPacket(1, 2);
 324   QuicTime::Delta rtt = QuicTime::Delta::FromMilliseconds(15);
 325   clock_.AdvanceTime(rtt);
 326
 327   // Ack 1 but not 2.
 328   ExpectAck(1);
 329   ReceivedPacketInfo received_info;
 330   received_info.largest_observed = 1;
 331   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 332
 333   // 2 should be unacked, since it may provide an RTT measurement.
 334   QuicPacketSequenceNumber unacked[] = { 2 };
 335   VerifyUnackedPackets(unacked, arraysize(unacked));
 336   EXPECT_FALSE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 337   VerifyRetransmittablePackets(NULL, 0);
 338
 339   // Verify that the retransmission alarm would not fire,
 340   // since there is no retransmittable data outstanding.
 341   EXPECT_EQ(QuicTime::Zero(), manager_.GetRetransmissionTime());
 342   EXPECT_EQ(1u, stats_.packets_spuriously_retransmitted);
 343 }
 344
 345 TEST_F(QuicSentPacketManagerTest, RetransmitAndSendThenAckPrevious) {
 346   SendDataPacket(1);
 347   RetransmitAndSendPacket(1, 2);
 348   QuicTime::Delta rtt = QuicTime::Delta::FromMilliseconds(15);
 349   clock_.AdvanceTime(rtt);
 350
 351   // Ack 1 but not 2.
 352   ExpectAck(1);
 353   ReceivedPacketInfo received_info;
 354   received_info.largest_observed = 1;
 355   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 356
 357   // 2 remains unacked, but no packets have retransmittable data.
 358   QuicPacketSequenceNumber unacked[] = { 2 };
 359   VerifyUnackedPackets(unacked, arraysize(unacked));
 360   EXPECT_TRUE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 361   VerifyRetransmittablePackets(NULL, 0);
 362
 363   EXPECT_EQ(1u, stats_.packets_spuriously_retransmitted);
 364 }
 365
 366 TEST_F(QuicSentPacketManagerTest, RetransmitThenAckPreviousThenNackRetransmit) {
 367   SendDataPacket(1);
 368   RetransmitPacket(1, 2);
 369   EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, 2, _, _))
 370       .WillOnce(Return(true));
 371   manager_.OnPacketSent(2, clock_.ApproximateNow(), kDefaultLength,
 372                         LOSS_RETRANSMISSION, HAS_RETRANSMITTABLE_DATA);
 373   QuicTime::Delta rtt = QuicTime::Delta::FromMilliseconds(15);
 374   clock_.AdvanceTime(rtt);
 375
 376   // First, ACK packet 1 which makes packet 2 non-retransmittable.
 377   ExpectAck(1);
 378   ReceivedPacketInfo received_info;
 379   received_info.largest_observed = 1;
 380   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 381
 382   SendDataPacket(3);
 383   SendDataPacket(4);
 384   SendDataPacket(5);
 385   clock_.AdvanceTime(rtt);
 386
 387   // Next, NACK packet 2 three times.
 388   received_info.largest_observed = 3;
 389   received_info.missing_packets.insert(2);
 390   ExpectAck(3);
 391   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 392
 393   received_info.largest_observed = 4;
 394   ExpectAck(4);
 395   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 396
 397   received_info.largest_observed = 5;
 398   ExpectAckAndLoss(true, 5, 2);
 399   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 400
 401   // No packets remain unacked.
 402   VerifyUnackedPackets(NULL, 0);
 403   EXPECT_FALSE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 404   VerifyRetransmittablePackets(NULL, 0);
 405
 406   // Verify that the retransmission alarm would not fire,
 407   // since there is no retransmittable data outstanding.
 408   EXPECT_EQ(QuicTime::Zero(), manager_.GetRetransmissionTime());
 409 }
 410
 411 TEST_F(QuicSentPacketManagerTest, RetransmitTwiceThenAckPreviousBeforeSend) {
 412   SendDataPacket(1);
 413   RetransmitAndSendPacket(1, 2);
 414
 415   // Fire the RTO, which will mark 2 for retransmission (but will not send it).
 416   EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout(true));
 417   manager_.OnRetransmissionTimeout();
 418   EXPECT_TRUE(manager_.HasPendingRetransmissions());
 419
 420   // Ack 1 but not 2, before 2 is able to be sent.
 421   // Since 1 has been retransmitted, it has already been lost, and so the
 422   // send algorithm is not informed that it has been ACK'd.
 423   ReceivedPacketInfo received_info;
 424   received_info.largest_observed = 1;
 425   ExpectUpdatedRtt(1);
 426   EXPECT_CALL(*send_algorithm_, RevertRetransmissionTimeout());
 427   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 428
 429   // Since 2 was marked for retransmit, when 1 is acked, 2 is kept for RTT.
 430   QuicPacketSequenceNumber unacked[] = { 2 };
 431   VerifyUnackedPackets(unacked, arraysize(unacked));
 432   EXPECT_FALSE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 433   VerifyRetransmittablePackets(NULL, 0);
 434
 435   // Verify that the retransmission alarm would not fire,
 436   // since there is no retransmittable data outstanding.
 437   EXPECT_EQ(QuicTime::Zero(), manager_.GetRetransmissionTime());
 438 }
 439
 440 TEST_F(QuicSentPacketManagerTest, RetransmitTwiceThenAckFirst) {
 441   StrictMock<MockDebugDelegate> debug_delegate;
 442   EXPECT_CALL(debug_delegate, OnSpuriousPacketRetransmition(
 443       TLP_RETRANSMISSION, kDefaultLength)).Times(2);
 444   manager_.set_debug_delegate(&debug_delegate);
 445
 446   SendDataPacket(1);
 447   RetransmitAndSendPacket(1, 2);
 448   RetransmitAndSendPacket(2, 3);
 449   QuicTime::Delta rtt = QuicTime::Delta::FromMilliseconds(15);
 450   clock_.AdvanceTime(rtt);
 451
 452   // Ack 1 but not 2 or 3.
 453   ExpectAck(1);
 454   ReceivedPacketInfo received_info;
 455   received_info.largest_observed = 1;
 456   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 457
 458   // 2 and 3 remain unacked, but no packets have retransmittable data.
 459   QuicPacketSequenceNumber unacked[] = { 2, 3 };
 460   VerifyUnackedPackets(unacked, arraysize(unacked));
 461   EXPECT_TRUE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 462   VerifyRetransmittablePackets(NULL, 0);
 463
 464   // Ensure packet 2 is lost when 4 is sent and 3 and 4 are acked.
 465   SendDataPacket(4);
 466   received_info.largest_observed = 4;
 467   received_info.missing_packets.insert(2);
 468   QuicPacketSequenceNumber acked[] = { 3, 4 };
 469   ExpectAcksAndLosses(true, acked, arraysize(acked), NULL, 0);
 470   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 471
 472   QuicPacketSequenceNumber unacked2[] = { 2 };
 473   VerifyUnackedPackets(unacked2, arraysize(unacked2));
 474   EXPECT_TRUE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 475
 476   SendDataPacket(5);
 477   received_info.largest_observed = 5;
 478   ExpectAckAndLoss(true, 5, 2);
 479   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 480
 481   VerifyUnackedPackets(NULL, 0);
 482   EXPECT_FALSE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 483   EXPECT_EQ(2u, stats_.packets_spuriously_retransmitted);
 484 }
 485
 486 TEST_F(QuicSentPacketManagerTest, LoseButDontRetransmitRevivedPacket) {
 487   SendDataPacket(1);
 488   SendDataPacket(2);
 489   SendFecPacket(3);
 490   SendDataPacket(4);
 491
 492   // Ack 2 and 3, and mark 1 as revived.
 493   ReceivedPacketInfo received_info;
 494   received_info.largest_observed = 3;
 495   received_info.missing_packets.insert(1);
 496   received_info.revived_packets.insert(1);
 497   QuicPacketSequenceNumber acked[] = { 2, 3 };
 498   ExpectAcksAndLosses(true, acked, arraysize(acked), NULL, 0);
 499   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 500
 501   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 502   QuicPacketSequenceNumber unacked[] = { 1, 4 };
 503   VerifyUnackedPackets(unacked, arraysize(unacked));
 504   EXPECT_TRUE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 505   QuicPacketSequenceNumber retransmittable[] = { 4 };
 506   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 507
 508   // Ack the 4th packet and expect the 1st to be considered lost.
 509   received_info.largest_observed = 4;
 510   ExpectAckAndLoss(true, 4, 1);
 511   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 512
 513   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 514   VerifyRetransmittablePackets(NULL, 0);
 515 }
 516
 517 TEST_F(QuicSentPacketManagerTest, MarkLostThenReviveAndDontRetransmitPacket) {
 518   SendDataPacket(1);
 519   SendDataPacket(2);
 520   SendDataPacket(3);
 521   SendDataPacket(4);
 522   SendFecPacket(5);
 523
 524   // Ack 2, 3, and 4, and expect the 1st to be considered lost.
 525   ReceivedPacketInfo received_info;
 526   received_info.largest_observed = 4;
 527   received_info.missing_packets.insert(1);
 528   QuicPacketSequenceNumber acked[] = { 2, 3, 4 };
 529   QuicPacketSequenceNumber lost[] = { 1 };
 530   ExpectAcksAndLosses(true, acked, arraysize(acked), lost, arraysize(lost));
 531   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 532
 533   EXPECT_TRUE(manager_.HasPendingRetransmissions());
 534   QuicPacketSequenceNumber unacked[] = { 1, 5 };
 535   VerifyUnackedPackets(unacked, arraysize(unacked));
 536   QuicPacketSequenceNumber retransmittable[] = { 1 };
 537   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 538
 539   // Ack 5th packet (FEC) and revive 1st packet. 1st packet should now be
 540   // removed from pending retransmissions map.
 541   received_info.largest_observed = 5;
 542   received_info.revived_packets.insert(1);
 543   ExpectAck(5);
 544   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 545
 546   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 547   VerifyRetransmittablePackets(NULL, 0);
 548 }
 549
 550 TEST_F(QuicSentPacketManagerTest, TruncatedAck) {
 551   SendDataPacket(1);
 552   RetransmitAndSendPacket(1, 2);
 553   RetransmitAndSendPacket(2, 3);
 554   RetransmitAndSendPacket(3, 4);
 555   RetransmitAndSendPacket(4, 5);
 556
 557   // Truncated ack with 4 NACKs, so the first packet is lost.
 558   ReceivedPacketInfo received_info;
 559   received_info.largest_observed = 4;
 560   received_info.missing_packets.insert(1);
 561   received_info.missing_packets.insert(2);
 562   received_info.missing_packets.insert(3);
 563   received_info.missing_packets.insert(4);
 564   received_info.is_truncated = true;
 565
 566   QuicPacketSequenceNumber lost[] = { 1 };
 567   ExpectAcksAndLosses(true, NULL, 0, lost, arraysize(lost));
 568   manager_.OnIncomingAck(received_info, clock_.Now());
 569
 570   // High water mark will be raised.
 571   QuicPacketSequenceNumber unacked[] = { 2, 3, 4, 5 };
 572   VerifyUnackedPackets(unacked, arraysize(unacked));
 573   QuicPacketSequenceNumber retransmittable[] = { 5 };
 574   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 575 }
 576
 577 TEST_F(QuicSentPacketManagerTest, AckPreviousTransmissionThenTruncatedAck) {
 578   SendDataPacket(1);
 579   RetransmitAndSendPacket(1, 2);
 580   RetransmitAndSendPacket(2, 3);
 581   RetransmitAndSendPacket(3, 4);
 582   manager_.OnSerializedPacket(CreateDataPacket(5));
 583   manager_.OnSerializedPacket(CreateDataPacket(6));
 584   manager_.OnSerializedPacket(CreateDataPacket(7));
 585   manager_.OnSerializedPacket(CreateDataPacket(8));
 586   manager_.OnSerializedPacket(CreateDataPacket(9));
 587
 588   // Ack previous transmission
 589   {
 590     ReceivedPacketInfo received_info;
 591     received_info.largest_observed = 2;
 592     received_info.missing_packets.insert(1);
 593     ExpectAck(2);
 594     manager_.OnIncomingAck(received_info, clock_.Now());
 595     EXPECT_TRUE(manager_.IsUnacked(4));
 596   }
 597
 598   // Truncated ack with 4 NACKs
 599   {
 600     ReceivedPacketInfo received_info;
 601     received_info.largest_observed = 6;
 602     received_info.missing_packets.insert(3);
 603     received_info.missing_packets.insert(4);
 604     received_info.missing_packets.insert(5);
 605     received_info.missing_packets.insert(6);
 606     received_info.is_truncated = true;
 607     ExpectAckAndLoss(false, 1, 3);
 608     manager_.OnIncomingAck(received_info, clock_.Now());
 609   }
 610
 611   // High water mark will be raised.
 612   QuicPacketSequenceNumber unacked[] = { 4, 5, 6, 7, 8, 9 };
 613   VerifyUnackedPackets(unacked, arraysize(unacked));
 614   QuicPacketSequenceNumber retransmittable[] = { 5, 6, 7, 8, 9 };
 615   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 616 }
 617
 618 TEST_F(QuicSentPacketManagerTest, GetLeastUnackedSentPacket) {
 619   EXPECT_EQ(0u, manager_.GetLeastUnackedSentPacket());
 620 }
 621
 622 TEST_F(QuicSentPacketManagerTest, GetLeastUnackedSentPacketUnacked) {
 623   SerializedPacket serialized_packet(CreateDataPacket(1));
 624
 625   manager_.OnSerializedPacket(serialized_packet);
 626   EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
 627 }
 628
 629 TEST_F(QuicSentPacketManagerTest, GetLeastUnackedSentPacketUnackedFec) {
 630   SerializedPacket serialized_packet(CreateFecPacket(1));
 631
 632   manager_.OnSerializedPacket(serialized_packet);
 633   EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
 634 }
 635
 636 TEST_F(QuicSentPacketManagerTest, GetLeastUnackedPacketAndDiscard) {
 637   VerifyUnackedPackets(NULL, 0);
 638
 639   SerializedPacket serialized_packet(CreateFecPacket(1));
 640   manager_.OnSerializedPacket(serialized_packet);
 641   EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
 642
 643   SerializedPacket serialized_packet2(CreateFecPacket(2));
 644   manager_.OnSerializedPacket(serialized_packet2);
 645   EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
 646
 647   SerializedPacket serialized_packet3(CreateFecPacket(3));
 648   manager_.OnSerializedPacket(serialized_packet3);
 649   EXPECT_EQ(1u, manager_.GetLeastUnackedSentPacket());
 650
 651   QuicPacketSequenceNumber unacked[] = { 1, 2, 3 };
 652   VerifyUnackedPackets(unacked, arraysize(unacked));
 653   VerifyRetransmittablePackets(NULL, 0);
 654
 655   // Ack 2, which has never been sent, so there's no rtt update.
 656   ReceivedPacketInfo received_info;
 657   received_info.largest_observed = 2;
 658   manager_.OnIncomingAck(received_info, clock_.Now());
 659
 660   EXPECT_EQ(3u, manager_.GetLeastUnackedSentPacket());
 661 }
 662
 663 TEST_F(QuicSentPacketManagerTest, GetSentTime) {
 664   VerifyUnackedPackets(NULL, 0);
 665
 666   SerializedPacket serialized_packet(CreateFecPacket(1));
 667   manager_.OnSerializedPacket(serialized_packet);
 668   EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, 1, _, _))
 669                   .Times(1).WillOnce(Return(true));
 670   manager_.OnPacketSent(1, QuicTime::Zero(), kDefaultLength, NOT_RETRANSMISSION,
 671                         NO_RETRANSMITTABLE_DATA);
 672
 673   SerializedPacket serialized_packet2(CreateFecPacket(2));
 674   QuicTime sent_time = QuicTime::Zero().Add(QuicTime::Delta::FromSeconds(1));
 675   manager_.OnSerializedPacket(serialized_packet2);
 676   EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, 2, _, _))
 677                   .Times(1).WillOnce(Return(true));
 678   manager_.OnPacketSent(2, sent_time, kDefaultLength, NOT_RETRANSMISSION,
 679                         NO_RETRANSMITTABLE_DATA);
 680
 681   QuicPacketSequenceNumber unacked[] = { 1, 2 };
 682   VerifyUnackedPackets(unacked, arraysize(unacked));
 683   VerifyRetransmittablePackets(NULL, 0);
 684
 685   EXPECT_TRUE(manager_.HasUnackedPackets());
 686   EXPECT_EQ(QuicTime::Zero(),
 687             QuicSentPacketManagerPeer::GetSentTime(&manager_, 1));
 688   EXPECT_EQ(sent_time, QuicSentPacketManagerPeer::GetSentTime(&manager_, 2));
 689 }
 690
 691 TEST_F(QuicSentPacketManagerTest, AckAckAndUpdateRtt) {
 692   SendDataPacket(1);
 693   SendAckPacket(2);
 694
 695   // Now ack the ack and expect an RTT update.
 696   ReceivedPacketInfo received_info;
 697   received_info.largest_observed = 2;
 698   received_info.delta_time_largest_observed =
 699       QuicTime::Delta::FromMilliseconds(5);
 700
 701   ExpectAck(1);
 702   manager_.OnIncomingAck(received_info, clock_.Now());
 703
 704   SendAckPacket(3);
 705
 706   // Now ack the ack and expect only an RTT update.
 707   received_info.largest_observed = 3;
 708   ExpectUpdatedRtt(3);
 709   manager_.OnIncomingAck(received_info, clock_.Now());
 710 }
 711
 712 TEST_F(QuicSentPacketManagerTest, Rtt) {
 713   QuicPacketSequenceNumber sequence_number = 1;
 714   QuicTime::Delta expected_rtt = QuicTime::Delta::FromMilliseconds(15);
 715   SendDataPacket(sequence_number);
 716   clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(20));
 717
 718   ExpectAck(sequence_number);
 719   ReceivedPacketInfo received_info;
 720   received_info.largest_observed = sequence_number;
 721   received_info.delta_time_largest_observed =
 722       QuicTime::Delta::FromMilliseconds(5);
 723   manager_.OnIncomingAck(received_info, clock_.Now());
 724   EXPECT_EQ(expected_rtt,
 725             QuicSentPacketManagerPeer::GetRttStats(&manager_)->latest_rtt());
 726 }
 727
 728 TEST_F(QuicSentPacketManagerTest, RttWithInvalidDelta) {
 729   // Expect that the RTT is equal to the local time elapsed, since the
 730   // delta_time_largest_observed is larger than the local time elapsed
 731   // and is hence invalid.
 732   QuicPacketSequenceNumber sequence_number = 1;
 733   QuicTime::Delta expected_rtt = QuicTime::Delta::FromMilliseconds(10);
 734   SendDataPacket(sequence_number);
 735   clock_.AdvanceTime(expected_rtt);
 736
 737   ExpectAck(sequence_number);
 738   ReceivedPacketInfo received_info;
 739   received_info.largest_observed = sequence_number;
 740   received_info.delta_time_largest_observed =
 741       QuicTime::Delta::FromMilliseconds(11);
 742   manager_.OnIncomingAck(received_info, clock_.Now());
 743   EXPECT_EQ(expected_rtt,
 744             QuicSentPacketManagerPeer::GetRttStats(&manager_)->latest_rtt());
 745 }
 746
 747 TEST_F(QuicSentPacketManagerTest, RttWithInfiniteDelta) {
 748   // Expect that the RTT is equal to the local time elapsed, since the
 749   // delta_time_largest_observed is infinite, and is hence invalid.
 750   QuicPacketSequenceNumber sequence_number = 1;
 751   QuicTime::Delta expected_rtt = QuicTime::Delta::FromMilliseconds(10);
 752   SendDataPacket(sequence_number);
 753   clock_.AdvanceTime(expected_rtt);
 754
 755   ExpectAck(sequence_number);
 756   ReceivedPacketInfo received_info;
 757   received_info.largest_observed = sequence_number;
 758   received_info.delta_time_largest_observed = QuicTime::Delta::Infinite();
 759   manager_.OnIncomingAck(received_info, clock_.Now());
 760   EXPECT_EQ(expected_rtt,
 761             QuicSentPacketManagerPeer::GetRttStats(&manager_)->latest_rtt());
 762 }
 763
 764 TEST_F(QuicSentPacketManagerTest, RttZeroDelta) {
 765   // Expect that the RTT is the time between send and receive since the
 766   // delta_time_largest_observed is zero.
 767   QuicPacketSequenceNumber sequence_number = 1;
 768   QuicTime::Delta expected_rtt = QuicTime::Delta::FromMilliseconds(10);
 769   SendDataPacket(sequence_number);
 770   clock_.AdvanceTime(expected_rtt);
 771
 772   ExpectAck(sequence_number);
 773   ReceivedPacketInfo received_info;
 774   received_info.largest_observed = sequence_number;
 775   received_info.delta_time_largest_observed = QuicTime::Delta::Zero();
 776   manager_.OnIncomingAck(received_info, clock_.Now());
 777   EXPECT_EQ(expected_rtt,
 778             QuicSentPacketManagerPeer::GetRttStats(&manager_)->latest_rtt());
 779 }
 780
 781 TEST_F(QuicSentPacketManagerTest, TailLossProbeTimeout) {
 782   QuicSentPacketManagerPeer::SetMaxTailLossProbes(&manager_, 2);
 783
 784   // Send 1 packet.
 785   QuicPacketSequenceNumber sequence_number = 1;
 786   SendDataPacket(sequence_number);
 787
 788   // The first tail loss probe retransmits 1 packet.
 789   manager_.OnRetransmissionTimeout();
 790   EXPECT_EQ(QuicTime::Delta::Zero(),
 791             manager_.TimeUntilSend(clock_.Now(), HAS_RETRANSMITTABLE_DATA));
 792   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 793   manager_.MaybeRetransmitTailLossProbe();
 794   EXPECT_TRUE(manager_.HasPendingRetransmissions());
 795   RetransmitNextPacket(2);
 796   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 797
 798   // The second tail loss probe retransmits 1 packet.
 799   manager_.OnRetransmissionTimeout();
 800   EXPECT_EQ(QuicTime::Delta::Zero(),
 801             manager_.TimeUntilSend(clock_.Now(), HAS_RETRANSMITTABLE_DATA));
 802   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 803   manager_.MaybeRetransmitTailLossProbe();
 804   EXPECT_TRUE(manager_.HasPendingRetransmissions());
 805   RetransmitNextPacket(3);
 806   EXPECT_CALL(*send_algorithm_, TimeUntilSend(_, _, _)).WillOnce(Return(
 807       QuicTime::Delta::Infinite()));
 808   EXPECT_EQ(QuicTime::Delta::Infinite(),
 809             manager_.TimeUntilSend(clock_.Now(), HAS_RETRANSMITTABLE_DATA));
 810   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 811
 812   // Ack the third and ensure the first two are still pending.
 813   ExpectAck(3);
 814   ReceivedPacketInfo received_info;
 815   received_info.largest_observed = 3;
 816   received_info.missing_packets.insert(1);
 817   received_info.missing_packets.insert(2);
 818   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 819
 820   EXPECT_TRUE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 821
 822   // Acking two more packets will lose both of them due to nacks.
 823   received_info.largest_observed = 5;
 824   QuicPacketSequenceNumber lost[] = { 1, 2 };
 825   ExpectAcksAndLosses(false, NULL, 0, lost, arraysize(lost));
 826   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 827
 828   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 829   EXPECT_FALSE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
 830   EXPECT_EQ(2u, stats_.tlp_count);
 831   EXPECT_EQ(0u, stats_.rto_count);
 832 }
 833
 834 TEST_F(QuicSentPacketManagerTest, TailLossProbeThenRTO) {
 835   QuicSentPacketManagerPeer::SetMaxTailLossProbes(&manager_, 2);
 836
 837   // Send 100 packets.
 838   const size_t kNumSentPackets = 100;
 839   for (size_t i = 1; i <= kNumSentPackets; ++i) {
 840     SendDataPacket(i);
 841   }
 842
 843   // The first tail loss probe retransmits 1 packet.
 844   manager_.OnRetransmissionTimeout();
 845   EXPECT_EQ(QuicTime::Delta::Zero(),
 846             manager_.TimeUntilSend(clock_.Now(), HAS_RETRANSMITTABLE_DATA));
 847   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 848   manager_.MaybeRetransmitTailLossProbe();
 849   EXPECT_TRUE(manager_.HasPendingRetransmissions());
 850   RetransmitNextPacket(101);
 851   EXPECT_CALL(*send_algorithm_, TimeUntilSend(_, _, _)).WillOnce(Return(
 852       QuicTime::Delta::Infinite()));
 853   EXPECT_EQ(QuicTime::Delta::Infinite(),
 854             manager_.TimeUntilSend(clock_.Now(), HAS_RETRANSMITTABLE_DATA));
 855   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 856
 857   // The second tail loss probe retransmits 1 packet.
 858   manager_.OnRetransmissionTimeout();
 859   EXPECT_EQ(QuicTime::Delta::Zero(),
 860             manager_.TimeUntilSend(clock_.Now(), HAS_RETRANSMITTABLE_DATA));
 861   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 862   EXPECT_TRUE(manager_.MaybeRetransmitTailLossProbe());
 863   EXPECT_TRUE(manager_.HasPendingRetransmissions());
 864   RetransmitNextPacket(102);
 865   EXPECT_CALL(*send_algorithm_, TimeUntilSend(_, _, _)).WillOnce(Return(
 866       QuicTime::Delta::Infinite()));
 867   EXPECT_EQ(QuicTime::Delta::Infinite(),
 868             manager_.TimeUntilSend(clock_.Now(), HAS_RETRANSMITTABLE_DATA));
 869
 870   // Advance the time enough to ensure all packets are RTO'd.
 871   clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(1000));
 872
 873   // The final RTO abandons all of them.
 874   EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout(true));
 875   manager_.OnRetransmissionTimeout();
 876   EXPECT_TRUE(manager_.HasPendingRetransmissions());
 877   EXPECT_EQ(2u, stats_.tlp_count);
 878   EXPECT_EQ(1u, stats_.rto_count);
 879 }
 880
 881 TEST_F(QuicSentPacketManagerTest, CryptoHandshakeTimeout) {
 882   // Send 2 crypto packets and 3 data packets.
 883   const size_t kNumSentCryptoPackets = 2;
 884   for (size_t i = 1; i <= kNumSentCryptoPackets; ++i) {
 885     SendCryptoPacket(i);
 886   }
 887   const size_t kNumSentDataPackets = 3;
 888   for (size_t i = 1; i <= kNumSentDataPackets; ++i) {
 889     SendDataPacket(kNumSentCryptoPackets + i);
 890   }
 891   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
 892
 893   // The first retransmits 2 packets.
 894   manager_.OnRetransmissionTimeout();
 895   RetransmitNextPacket(6);
 896   RetransmitNextPacket(7);
 897   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 898   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
 899
 900   // The second retransmits 2 packets.
 901   manager_.OnRetransmissionTimeout();
 902   RetransmitNextPacket(8);
 903   RetransmitNextPacket(9);
 904   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 905   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
 906
 907   // Now ack the two crypto packets and the speculatively encrypted request,
 908   // and ensure the first four crypto packets get abandoned, but not lost.
 909   QuicPacketSequenceNumber acked[] = { 3, 4, 5, 8, 9 };
 910   ExpectAcksAndLosses(true, acked, arraysize(acked), NULL, 0);
 911   ReceivedPacketInfo received_info;
 912   received_info.largest_observed = 9;
 913   received_info.missing_packets.insert(1);
 914   received_info.missing_packets.insert(2);
 915   received_info.missing_packets.insert(6);
 916   received_info.missing_packets.insert(7);
 917   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 918
 919   EXPECT_FALSE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
 920 }
 921
 922 TEST_F(QuicSentPacketManagerTest, CryptoHandshakeTimeoutVersionNegotiation) {
 923   // Send 2 crypto packets and 3 data packets.
 924   const size_t kNumSentCryptoPackets = 2;
 925   for (size_t i = 1; i <= kNumSentCryptoPackets; ++i) {
 926     SendCryptoPacket(i);
 927   }
 928   const size_t kNumSentDataPackets = 3;
 929   for (size_t i = 1; i <= kNumSentDataPackets; ++i) {
 930     SendDataPacket(kNumSentCryptoPackets + i);
 931   }
 932   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
 933
 934   // The first retransmission timeout retransmits 2 crypto packets.
 935   manager_.OnRetransmissionTimeout();
 936   RetransmitNextPacket(6);
 937   RetransmitNextPacket(7);
 938   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 939   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
 940
 941   // Now act like a version negotiation packet arrived, which would cause all
 942   // unacked packets to be retransmitted.
 943   manager_.RetransmitUnackedPackets(ALL_PACKETS);
 944
 945   // Ensure the first two pending packets are the crypto retransmits.
 946   ASSERT_TRUE(manager_.HasPendingRetransmissions());
 947   EXPECT_EQ(6u, manager_.NextPendingRetransmission().sequence_number);
 948   RetransmitNextPacket(8);
 949   EXPECT_EQ(7u, manager_.NextPendingRetransmission().sequence_number);
 950   RetransmitNextPacket(9);
 951
 952   EXPECT_TRUE(manager_.HasPendingRetransmissions());
 953 }
 954
 955 TEST_F(QuicSentPacketManagerTest, CryptoHandshakeSpuriousRetransmission) {
 956   // Send 1 crypto packet.
 957   SendCryptoPacket(1);
 958   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
 959
 960   // Retransmit the crypto packet as 2.
 961   manager_.OnRetransmissionTimeout();
 962   RetransmitNextPacket(2);
 963
 964   // Retransmit the crypto packet as 3.
 965   manager_.OnRetransmissionTimeout();
 966   RetransmitNextPacket(3);
 967
 968   // Now ack the second crypto packet, and ensure the first gets removed, but
 969   // the third does not.
 970   ExpectUpdatedRtt(2);
 971   ReceivedPacketInfo received_info;
 972   received_info.largest_observed = 2;
 973   received_info.missing_packets.insert(1);
 974   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
 975
 976   EXPECT_FALSE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
 977   QuicPacketSequenceNumber unacked[] = { 3 };
 978   VerifyUnackedPackets(unacked, arraysize(unacked));
 979 }
 980
 981 TEST_F(QuicSentPacketManagerTest, CryptoHandshakeTimeoutUnsentDataPacket) {
 982   // Send 2 crypto packets and serialize 1 data packet.
 983   const size_t kNumSentCryptoPackets = 2;
 984   for (size_t i = 1; i <= kNumSentCryptoPackets; ++i) {
 985     SendCryptoPacket(i);
 986   }
 987   SerializedPacket packet(CreateDataPacket(3));
 988   manager_.OnSerializedPacket(packet);
 989   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
 990
 991   // Retransmit 2 crypto packets, but not the serialized packet.
 992   manager_.OnRetransmissionTimeout();
 993   RetransmitNextPacket(6);
 994   RetransmitNextPacket(7);
 995   EXPECT_FALSE(manager_.HasPendingRetransmissions());
 996   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
 997 }
 998
 999 TEST_F(QuicSentPacketManagerTest,
1000        CryptoHandshakeRetransmissionThenRetransmitAll) {
1001   // Send 1 crypto packet.
1002   SendCryptoPacket(1);
1003   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
1004
1005   // Retransmit the crypto packet as 2.
1006   manager_.OnRetransmissionTimeout();
1007   RetransmitNextPacket(2);
1008
1009   // Now retransmit all the unacked packets, which occurs when there is a
1010   // version negotiation.
1011   manager_.RetransmitUnackedPackets(ALL_PACKETS);
1012   QuicPacketSequenceNumber unacked[] = { 1, 2 };
1013   VerifyUnackedPackets(unacked, arraysize(unacked));
1014   EXPECT_TRUE(manager_.HasPendingRetransmissions());
1015   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
1016   EXPECT_FALSE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
1017 }
1018
1019 TEST_F(QuicSentPacketManagerTest,
1020        CryptoHandshakeRetransmissionThenNeuterAndAck) {
1021   // Send 1 crypto packet.
1022   SendCryptoPacket(1);
1023   EXPECT_TRUE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
1024
1025   // Retransmit the crypto packet as 2.
1026   manager_.OnRetransmissionTimeout();
1027   RetransmitNextPacket(2);
1028
1029   // Retransmit the crypto packet as 3.
1030   manager_.OnRetransmissionTimeout();
1031   RetransmitNextPacket(3);
1032
1033   // Now neuter all unacked unencrypted packets, which occurs when the
1034   // connection goes forward secure.
1035   manager_.NeuterUnencryptedPackets();
1036   QuicPacketSequenceNumber unacked[] = { 1, 2, 3};
1037   VerifyUnackedPackets(unacked, arraysize(unacked));
1038   VerifyRetransmittablePackets(NULL, 0);
1039   EXPECT_FALSE(manager_.HasPendingRetransmissions());
1040   EXPECT_FALSE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
1041   EXPECT_FALSE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
1042
1043   // Ensure both packets get discarded when packet 2 is acked.
1044   ReceivedPacketInfo received_info;
1045   received_info.largest_observed = 3;
1046   received_info.missing_packets.insert(1);
1047   received_info.missing_packets.insert(2);
1048   ExpectUpdatedRtt(3);
1049   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
1050   VerifyUnackedPackets(NULL, 0);
1051   VerifyRetransmittablePackets(NULL, 0);
1052 }
1053
1054 TEST_F(QuicSentPacketManagerTest, TailLossProbeTimeoutUnsentDataPacket) {
1055   QuicSentPacketManagerPeer::SetMaxTailLossProbes(&manager_, 2);
1056   // Serialize two data packets and send the latter.
1057   SerializedPacket packet(CreateDataPacket(1));
1058   manager_.OnSerializedPacket(packet);
1059   SendDataPacket(2);
1060   EXPECT_FALSE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
1061   EXPECT_TRUE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
1062
1063   // Retransmit 1 unacked packets, but not the first serialized packet.
1064   manager_.OnRetransmissionTimeout();
1065   EXPECT_EQ(QuicTime::Delta::Zero(),
1066             manager_.TimeUntilSend(clock_.Now(), HAS_RETRANSMITTABLE_DATA));
1067   EXPECT_FALSE(manager_.HasPendingRetransmissions());
1068   manager_.MaybeRetransmitTailLossProbe();
1069   EXPECT_TRUE(manager_.HasPendingRetransmissions());
1070   RetransmitNextPacket(3);
1071   EXPECT_CALL(*send_algorithm_, TimeUntilSend(_, _, _)).WillOnce(Return(
1072       QuicTime::Delta::Infinite()));
1073   EXPECT_EQ(QuicTime::Delta::Infinite(),
1074             manager_.TimeUntilSend(clock_.Now(), HAS_RETRANSMITTABLE_DATA));
1075   EXPECT_FALSE(manager_.HasPendingRetransmissions());
1076   EXPECT_FALSE(QuicSentPacketManagerPeer::HasUnackedCryptoPackets(&manager_));
1077   EXPECT_TRUE(QuicSentPacketManagerPeer::HasPendingPackets(&manager_));
1078 }
1079
1080 TEST_F(QuicSentPacketManagerTest, ResetRecentMinRTTWithEmptyWindow) {
1081   QuicTime::Delta min_rtt = QuicTime::Delta::FromMilliseconds(50);
1082   QuicSentPacketManagerPeer::GetRttStats(&manager_)->UpdateRtt(
1083       min_rtt, QuicTime::Delta::Zero(), QuicTime::Zero());
1084   EXPECT_EQ(min_rtt,
1085             QuicSentPacketManagerPeer::GetRttStats(&manager_)->min_rtt());
1086   EXPECT_EQ(min_rtt,
1087             QuicSentPacketManagerPeer::GetRttStats(
1088                 &manager_)->recent_min_rtt());
1089
1090   // Send two packets with no prior bytes in flight.
1091   SendDataPacket(1);
1092   SendDataPacket(2);
1093
1094   clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(100));
1095   // Ack two packets with 100ms RTT observations.
1096   ReceivedPacketInfo received_info;
1097   received_info.delta_time_largest_observed = QuicTime::Delta::Zero();
1098   received_info.largest_observed = 1;
1099   ExpectAck(1);
1100   manager_.OnIncomingAck(received_info, clock_.Now());
1101
1102   // First ack does not change recent min rtt.
1103   EXPECT_EQ(min_rtt,
1104             QuicSentPacketManagerPeer::GetRttStats(
1105                 &manager_)->recent_min_rtt());
1106
1107   received_info.largest_observed = 2;
1108   ExpectAck(2);
1109   manager_.OnIncomingAck(received_info, clock_.Now());
1110
1111   EXPECT_EQ(min_rtt,
1112             QuicSentPacketManagerPeer::GetRttStats(&manager_)->min_rtt());
1113   EXPECT_EQ(QuicTime::Delta::FromMilliseconds(100),
1114             QuicSentPacketManagerPeer::GetRttStats(
1115                 &manager_)->recent_min_rtt());
1116 }
1117
1118 TEST_F(QuicSentPacketManagerTest, RetransmissionTimeout) {
1119   // Send 100 packets and then ensure all are abandoned when the RTO fires.
1120   const size_t kNumSentPackets = 100;
1121   for (size_t i = 1; i <= kNumSentPackets; ++i) {
1122     SendDataPacket(i);
1123   }
1124
1125   EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout(true));
1126   EXPECT_FALSE(manager_.MaybeRetransmitTailLossProbe());
1127   manager_.OnRetransmissionTimeout();
1128 }
1129
1130 TEST_F(QuicSentPacketManagerTest, GetTransmissionTime) {
1131   EXPECT_EQ(QuicTime::Zero(), manager_.GetRetransmissionTime());
1132 }
1133
1134 TEST_F(QuicSentPacketManagerTest, GetTransmissionTimeCryptoHandshake) {
1135   SendCryptoPacket(1);
1136
1137   // Check the min.
1138   QuicSentPacketManagerPeer::GetRttStats(&manager_)->set_initial_rtt_us(
1139       1 * base::Time::kMicrosecondsPerMillisecond);
1140   EXPECT_EQ(clock_.Now().Add(QuicTime::Delta::FromMilliseconds(10)),
1141             manager_.GetRetransmissionTime());
1142
1143   // Test with a standard smoothed RTT.
1144   QuicSentPacketManagerPeer::GetRttStats(&manager_)->set_initial_rtt_us(
1145       100 * base::Time::kMicrosecondsPerMillisecond);
1146
1147   QuicTime::Delta srtt = manager_.GetRttStats()->SmoothedRtt();
1148   QuicTime expected_time = clock_.Now().Add(srtt.Multiply(1.5));
1149   EXPECT_EQ(expected_time, manager_.GetRetransmissionTime());
1150
1151   // Retransmit the packet by invoking the retransmission timeout.
1152   clock_.AdvanceTime(srtt.Multiply(1.5));
1153   manager_.OnRetransmissionTimeout();
1154   RetransmitNextPacket(2);
1155
1156   // The retransmission time should now be twice as far in the future.
1157   expected_time = clock_.Now().Add(srtt.Multiply(2).Multiply(1.5));
1158   EXPECT_EQ(expected_time, manager_.GetRetransmissionTime());
1159 }
1160
1161 TEST_F(QuicSentPacketManagerTest, GetTransmissionTimeTailLossProbe) {
1162   QuicSentPacketManagerPeer::SetMaxTailLossProbes(&manager_, 2);
1163   SendDataPacket(1);
1164   SendDataPacket(2);
1165
1166   // Check the min.
1167   QuicSentPacketManagerPeer::GetRttStats(&manager_)->set_initial_rtt_us(
1168       1 * base::Time::kMicrosecondsPerMillisecond);
1169   EXPECT_EQ(clock_.Now().Add(QuicTime::Delta::FromMilliseconds(10)),
1170             manager_.GetRetransmissionTime());
1171
1172   // Test with a standard smoothed RTT.
1173   QuicSentPacketManagerPeer::GetRttStats(&manager_)->set_initial_rtt_us(
1174       100 * base::Time::kMicrosecondsPerMillisecond);
1175   QuicTime::Delta srtt = manager_.GetRttStats()->SmoothedRtt();
1176   QuicTime::Delta expected_tlp_delay = srtt.Multiply(2);
1177   QuicTime expected_time = clock_.Now().Add(expected_tlp_delay);
1178   EXPECT_EQ(expected_time, manager_.GetRetransmissionTime());
1179
1180   // Retransmit the packet by invoking the retransmission timeout.
1181   clock_.AdvanceTime(expected_tlp_delay);
1182   manager_.OnRetransmissionTimeout();
1183   EXPECT_EQ(QuicTime::Delta::Zero(),
1184             manager_.TimeUntilSend(clock_.Now(), HAS_RETRANSMITTABLE_DATA));
1185   EXPECT_FALSE(manager_.HasPendingRetransmissions());
1186   EXPECT_TRUE(manager_.MaybeRetransmitTailLossProbe());
1187   EXPECT_TRUE(manager_.HasPendingRetransmissions());
1188   RetransmitNextPacket(3);
1189   EXPECT_CALL(*send_algorithm_, TimeUntilSend(_, _, _)).WillOnce(Return(
1190       QuicTime::Delta::Infinite()));
1191   EXPECT_EQ(QuicTime::Delta::Infinite(),
1192             manager_.TimeUntilSend(clock_.Now(), HAS_RETRANSMITTABLE_DATA));
1193   EXPECT_FALSE(manager_.HasPendingRetransmissions());
1194
1195   expected_time = clock_.Now().Add(expected_tlp_delay);
1196   EXPECT_EQ(expected_time, manager_.GetRetransmissionTime());
1197 }
1198
1199 TEST_F(QuicSentPacketManagerTest, GetTransmissionTimeRTO) {
1200   QuicSentPacketManagerPeer::GetRttStats(&manager_)->UpdateRtt(
1201       QuicTime::Delta::FromMilliseconds(100),
1202       QuicTime::Delta::Zero(),
1203       QuicTime::Zero());
1204
1205   SendDataPacket(1);
1206   SendDataPacket(2);
1207   SendDataPacket(3);
1208   SendDataPacket(4);
1209
1210   QuicTime::Delta expected_rto_delay = QuicTime::Delta::FromMilliseconds(500);
1211   EXPECT_CALL(*send_algorithm_, RetransmissionDelay())
1212       .WillRepeatedly(Return(expected_rto_delay));
1213   QuicTime expected_time = clock_.Now().Add(expected_rto_delay);
1214   EXPECT_EQ(expected_time, manager_.GetRetransmissionTime());
1215
1216   // Retransmit the packet by invoking the retransmission timeout.
1217   EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout(true));
1218   clock_.AdvanceTime(expected_rto_delay);
1219   manager_.OnRetransmissionTimeout();
1220   EXPECT_EQ(0u, QuicSentPacketManagerPeer::GetBytesInFlight(&manager_));
1221   RetransmitNextPacket(5);
1222   RetransmitNextPacket(6);
1223   EXPECT_EQ(2 * kDefaultLength,
1224             QuicSentPacketManagerPeer::GetBytesInFlight(&manager_));
1225   EXPECT_TRUE(manager_.HasPendingRetransmissions());
1226
1227   // The delay should double the second time.
1228   expected_time = clock_.Now().Add(expected_rto_delay).Add(expected_rto_delay);
1229   EXPECT_EQ(expected_time, manager_.GetRetransmissionTime());
1230
1231   // Ack a packet and ensure the RTO goes back to the original value.
1232   ReceivedPacketInfo received_info;
1233   received_info.largest_observed = 2;
1234   received_info.missing_packets.insert(1);
1235   ExpectUpdatedRtt(2);
1236   EXPECT_CALL(*send_algorithm_, RevertRetransmissionTimeout());
1237   manager_.OnIncomingAck(received_info, clock_.ApproximateNow());
1238   EXPECT_FALSE(manager_.HasPendingRetransmissions());
1239   EXPECT_EQ(4 * kDefaultLength,
1240             QuicSentPacketManagerPeer::GetBytesInFlight(&manager_));
1241
1242   // Wait 2RTTs from now for the RTO, since it's the max of the RTO time
1243   // and the TLP time.  In production, there would always be two TLP's first.
1244   expected_time = clock_.Now().Add(QuicTime::Delta::FromMilliseconds(200));
1245   EXPECT_EQ(expected_time, manager_.GetRetransmissionTime());
1246 }
1247
1248 TEST_F(QuicSentPacketManagerTest, GetTransmissionDelayMin) {
1249   SendDataPacket(1);
1250   EXPECT_CALL(*send_algorithm_, RetransmissionDelay())
1251       .WillRepeatedly(Return(QuicTime::Delta::FromMilliseconds(1)));
1252   QuicTime::Delta delay = QuicTime::Delta::FromMilliseconds(200);
1253
1254   // If the delay is smaller than the min, ensure it exponentially backs off
1255   // from the min.
1256   for (int i = 0; i < 5; ++i) {
1257     EXPECT_EQ(delay,
1258               QuicSentPacketManagerPeer::GetRetransmissionDelay(&manager_));
1259     delay = delay.Add(delay);
1260     EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout(true));
1261     manager_.OnRetransmissionTimeout();
1262     RetransmitNextPacket(i + 2);
1263   }
1264 }
1265
1266 TEST_F(QuicSentPacketManagerTest, GetTransmissionDelayMax) {
1267   EXPECT_CALL(*send_algorithm_, RetransmissionDelay())
1268       .WillOnce(Return(QuicTime::Delta::FromSeconds(500)));
1269
1270   EXPECT_EQ(QuicTime::Delta::FromSeconds(60),
1271             QuicSentPacketManagerPeer::GetRetransmissionDelay(&manager_));
1272 }
1273
1274 TEST_F(QuicSentPacketManagerTest, GetTransmissionDelay) {
1275   SendDataPacket(1);
1276   QuicTime::Delta delay = QuicTime::Delta::FromMilliseconds(500);
1277   EXPECT_CALL(*send_algorithm_, RetransmissionDelay())
1278       .WillRepeatedly(Return(delay));
1279
1280   // Delay should back off exponentially.
1281   for (int i = 0; i < 5; ++i) {
1282     EXPECT_EQ(delay,
1283               QuicSentPacketManagerPeer::GetRetransmissionDelay(&manager_));
1284     delay = delay.Add(delay);
1285     EXPECT_CALL(*send_algorithm_, OnRetransmissionTimeout(true));
1286     manager_.OnRetransmissionTimeout();
1287     RetransmitNextPacket(i + 2);
1288   }
1289 }
1290
1291 TEST_F(QuicSentPacketManagerTest, GetLossDelay) {
1292   MockLossAlgorithm* loss_algorithm = new MockLossAlgorithm();
1293   QuicSentPacketManagerPeer::SetLossAlgorithm(&manager_, loss_algorithm);
1294
1295   EXPECT_CALL(*loss_algorithm, GetLossTimeout())
1296       .WillRepeatedly(Return(QuicTime::Zero()));
1297   SendDataPacket(1);
1298   SendDataPacket(2);
1299
1300   // Handle an ack which causes the loss algorithm to be evaluated and
1301   // set the loss timeout.
1302   ExpectAck(2);
1303   EXPECT_CALL(*loss_algorithm, DetectLostPackets(_, _, _, _))
1304       .WillOnce(Return(SequenceNumberSet()));
1305   ReceivedPacketInfo received_info;
1306   received_info.largest_observed = 2;
1307   received_info.missing_packets.insert(1);
1308   manager_.OnIncomingAck(received_info, clock_.Now());
1309
1310   QuicTime timeout(clock_.Now().Add(QuicTime::Delta::FromMilliseconds(10)));
1311   EXPECT_CALL(*loss_algorithm, GetLossTimeout())
1312       .WillRepeatedly(Return(timeout));
1313   EXPECT_EQ(timeout, manager_.GetRetransmissionTime());
1314
1315   // Fire the retransmission timeout and ensure the loss detection algorithm
1316   // is invoked.
1317   EXPECT_CALL(*loss_algorithm, DetectLostPackets(_, _, _, _))
1318       .WillOnce(Return(SequenceNumberSet()));
1319   manager_.OnRetransmissionTimeout();
1320 }
1321
1322 TEST_F(QuicSentPacketManagerTest, NegotiateTimeLossDetection) {
1323   EXPECT_EQ(kNack,
1324             QuicSentPacketManagerPeer::GetLossAlgorithm(
1325                 &manager_)->GetLossDetectionType());
1326
1327   QuicConfig config;
1328   QuicConfigPeer::SetReceivedLossDetection(&config, kTIME);
1329   EXPECT_CALL(*send_algorithm_, SetFromConfig(_, _));
1330   manager_.SetFromConfig(config);
1331
1332   EXPECT_EQ(kTime,
1333             QuicSentPacketManagerPeer::GetLossAlgorithm(
1334                 &manager_)->GetLossDetectionType());
1335 }
1336
1337 TEST_F(QuicSentPacketManagerTest, NegotiateTimeLossDetectionFromOptions) {
1338   EXPECT_EQ(kNack,
1339             QuicSentPacketManagerPeer::GetLossAlgorithm(
1340                 &manager_)->GetLossDetectionType());
1341
1342   QuicConfig config;
1343   QuicTagVector options;
1344   options.push_back(kTIME);
1345   QuicConfigPeer::SetReceivedConnectionOptions(&config, options);
1346   EXPECT_CALL(*send_algorithm_, SetFromConfig(_, _));
1347   manager_.SetFromConfig(config);
1348
1349   EXPECT_EQ(kTime,
1350             QuicSentPacketManagerPeer::GetLossAlgorithm(
1351                 &manager_)->GetLossDetectionType());
1352 }
1353
1354 TEST_F(QuicSentPacketManagerTest, NegotiatePacingFromOptions) {
1355   ValueRestore<bool> old_flag(&FLAGS_enable_quic_pacing, true);
1356   EXPECT_FALSE(manager_.using_pacing());
1357
1358   QuicConfig config;
1359   QuicTagVector options;
1360   options.push_back(kPACE);
1361   QuicConfigPeer::SetReceivedConnectionOptions(&config, options);
1362   EXPECT_CALL(*send_algorithm_, SetFromConfig(_, _));
1363   manager_.SetFromConfig(config);
1364
1365   EXPECT_TRUE(manager_.using_pacing());
1366 }
1367
1368 }  // namespace
1369 }  // namespace test
1370 }  // namespace net