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