src/net/quic/quic_sent_packet_manager_test.cc

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