net/quic/quic_unacked_packet_map_test.cc

   1 // Copyright 2014 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_unacked_packet_map.h"
   6
   7 #include "net/quic/quic_ack_notifier_manager.h"
   8 #include "net/quic/quic_flags.h"
   9 #include "net/quic/quic_utils.h"
  10 #include "net/quic/test_tools/quic_test_utils.h"
  11 #include "testing/gtest/include/gtest/gtest.h"
  12
  13 using std::min;
  14 using std::vector;
  15
  16 namespace net {
  17 namespace test {
  18 namespace {
  19
  20 // Default packet length.
  21 const uint32 kDefaultAckLength = 50;
  22 const uint32 kDefaultLength = 1000;
  23
  24 class QuicUnackedPacketMapTest : public ::testing::Test {
  25  protected:
  26   QuicUnackedPacketMapTest()
  27       : unacked_packets_(&ack_notifier_manager_),
  28         now_(QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(1000))) {}
  29
  30   ~QuicUnackedPacketMapTest() override {
  31     STLDeleteElements(&packets_);
  32   }
  33
  34   SerializedPacket CreateRetransmittablePacket(
  35       QuicPacketSequenceNumber sequence_number) {
  36     packets_.push_back(new QuicEncryptedPacket(nullptr, kDefaultLength));
  37     return SerializedPacket(sequence_number, PACKET_1BYTE_SEQUENCE_NUMBER,
  38                             packets_.back(), 0,
  39                             new RetransmittableFrames(ENCRYPTION_NONE));
  40   }
  41
  42   SerializedPacket CreateRetransmittablePacketForStream(
  43       QuicPacketSequenceNumber sequence_number,
  44       QuicStreamId stream_id) {
  45     packets_.push_back(new QuicEncryptedPacket(nullptr, kDefaultLength));
  46     RetransmittableFrames* frames = new RetransmittableFrames(ENCRYPTION_NONE);
  47     QuicStreamFrame* frame = new QuicStreamFrame();
  48     frame->stream_id = stream_id;
  49     frames->AddFrame(QuicFrame(frame));
  50     return SerializedPacket(sequence_number, PACKET_1BYTE_SEQUENCE_NUMBER,
  51                             packets_.back(), 0, frames);
  52   }
  53
  54   SerializedPacket CreateNonRetransmittablePacket(
  55       QuicPacketSequenceNumber sequence_number) {
  56     packets_.push_back(new QuicEncryptedPacket(nullptr, kDefaultLength));
  57     return SerializedPacket(sequence_number, PACKET_1BYTE_SEQUENCE_NUMBER,
  58                             packets_.back(), 0, nullptr);
  59   }
  60
  61   void VerifyInFlightPackets(QuicPacketSequenceNumber* packets,
  62                              size_t num_packets) {
  63     unacked_packets_.RemoveObsoletePackets();
  64     if (num_packets == 0) {
  65       EXPECT_FALSE(unacked_packets_.HasInFlightPackets());
  66       EXPECT_FALSE(unacked_packets_.HasMultipleInFlightPackets());
  67       return;
  68     }
  69     if (num_packets == 1) {
  70       EXPECT_TRUE(unacked_packets_.HasInFlightPackets());
  71       EXPECT_FALSE(unacked_packets_.HasMultipleInFlightPackets());
  72       ASSERT_TRUE(unacked_packets_.IsUnacked(packets[0]));
  73       EXPECT_TRUE(unacked_packets_.GetTransmissionInfo(packets[0]).in_flight);
  74     }
  75     for (size_t i = 0; i < num_packets; ++i) {
  76       ASSERT_TRUE(unacked_packets_.IsUnacked(packets[i]));
  77       EXPECT_TRUE(unacked_packets_.GetTransmissionInfo(packets[i]).in_flight);
  78     }
  79     size_t in_flight_count = 0;
  80     for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
  81          it != unacked_packets_.end(); ++it) {
  82       if (it->in_flight) {
  83         ++in_flight_count;
  84       }
  85     }
  86     EXPECT_EQ(num_packets, in_flight_count);
  87   }
  88
  89   void VerifyUnackedPackets(QuicPacketSequenceNumber* packets,
  90                             size_t num_packets) {
  91     unacked_packets_.RemoveObsoletePackets();
  92     if (num_packets == 0) {
  93       EXPECT_FALSE(unacked_packets_.HasUnackedPackets());
  94       EXPECT_FALSE(unacked_packets_.HasUnackedRetransmittableFrames());
  95       return;
  96     }
  97     EXPECT_TRUE(unacked_packets_.HasUnackedPackets());
  98     for (size_t i = 0; i < num_packets; ++i) {
  99       EXPECT_TRUE(unacked_packets_.IsUnacked(packets[i])) << packets[i];
 100     }
 101     EXPECT_EQ(num_packets, unacked_packets_.GetNumUnackedPacketsDebugOnly());
 102   }
 103
 104   void VerifyRetransmittablePackets(QuicPacketSequenceNumber* packets,
 105                                     size_t num_packets) {
 106     unacked_packets_.RemoveObsoletePackets();
 107     size_t num_retransmittable_packets = 0;
 108     for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 109          it != unacked_packets_.end(); ++it) {
 110       if (it->retransmittable_frames != nullptr) {
 111         ++num_retransmittable_packets;
 112       }
 113     }
 114     EXPECT_EQ(num_packets, num_retransmittable_packets);
 115     for (size_t i = 0; i < num_packets; ++i) {
 116       EXPECT_TRUE(unacked_packets_.HasRetransmittableFrames(packets[i]))
 117           << " packets[" << i << "]:" << packets[i];
 118     }
 119   }
 120   vector<QuicEncryptedPacket*> packets_;
 121   AckNotifierManager ack_notifier_manager_;
 122   QuicUnackedPacketMap unacked_packets_;
 123   QuicTime now_;
 124 };
 125
 126 TEST_F(QuicUnackedPacketMapTest, RttOnly) {
 127   // Acks are only tracked for RTT measurement purposes.
 128   unacked_packets_.AddSentPacket(CreateNonRetransmittablePacket(1), 0,
 129                                  NOT_RETRANSMISSION, now_, kDefaultAckLength,
 130                                  false);
 131
 132   QuicPacketSequenceNumber unacked[] = { 1 };
 133   VerifyUnackedPackets(unacked, arraysize(unacked));
 134   VerifyInFlightPackets(nullptr, 0);
 135   VerifyRetransmittablePackets(nullptr, 0);
 136
 137   unacked_packets_.IncreaseLargestObserved(1);
 138   VerifyUnackedPackets(nullptr, 0);
 139   VerifyInFlightPackets(nullptr, 0);
 140   VerifyRetransmittablePackets(nullptr, 0);
 141 }
 142
 143 TEST_F(QuicUnackedPacketMapTest, RetransmittableInflightAndRtt) {
 144   // Simulate a retransmittable packet being sent and acked.
 145   unacked_packets_.AddSentPacket(CreateRetransmittablePacket(1), 0,
 146                                  NOT_RETRANSMISSION, now_, kDefaultLength,
 147                                  true);
 148
 149   QuicPacketSequenceNumber unacked[] = { 1 };
 150   VerifyUnackedPackets(unacked, arraysize(unacked));
 151   VerifyInFlightPackets(unacked, arraysize(unacked));
 152   VerifyRetransmittablePackets(unacked, arraysize(unacked));
 153
 154   unacked_packets_.RemoveRetransmittability(1);
 155   VerifyUnackedPackets(unacked, arraysize(unacked));
 156   VerifyInFlightPackets(unacked, arraysize(unacked));
 157   VerifyRetransmittablePackets(nullptr, 0);
 158
 159   unacked_packets_.IncreaseLargestObserved(1);
 160   VerifyUnackedPackets(unacked, arraysize(unacked));
 161   VerifyInFlightPackets(unacked, arraysize(unacked));
 162   VerifyRetransmittablePackets(nullptr, 0);
 163
 164   unacked_packets_.RemoveFromInFlight(1);
 165   VerifyUnackedPackets(nullptr, 0);
 166   VerifyInFlightPackets(nullptr, 0);
 167   VerifyRetransmittablePackets(nullptr, 0);
 168 }
 169
 170 TEST_F(QuicUnackedPacketMapTest, StopRetransmission) {
 171   const QuicStreamId stream_id = 2;
 172   unacked_packets_.AddSentPacket(
 173       CreateRetransmittablePacketForStream(1, stream_id), 0, NOT_RETRANSMISSION,
 174       now_, kDefaultLength, true);
 175
 176   QuicPacketSequenceNumber unacked[] = {1};
 177   VerifyUnackedPackets(unacked, arraysize(unacked));
 178   VerifyInFlightPackets(unacked, arraysize(unacked));
 179   QuicPacketSequenceNumber retransmittable[] = {1};
 180   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 181
 182   unacked_packets_.CancelRetransmissionsForStream(stream_id);
 183   VerifyUnackedPackets(unacked, arraysize(unacked));
 184   VerifyInFlightPackets(unacked, arraysize(unacked));
 185   VerifyRetransmittablePackets(nullptr, 0);
 186 }
 187
 188 TEST_F(QuicUnackedPacketMapTest, StopRetransmissionOnOtherStream) {
 189   const QuicStreamId stream_id = 2;
 190   unacked_packets_.AddSentPacket(
 191       CreateRetransmittablePacketForStream(1, stream_id), 0, NOT_RETRANSMISSION,
 192       now_, kDefaultLength, true);
 193
 194   QuicPacketSequenceNumber unacked[] = {1};
 195   VerifyUnackedPackets(unacked, arraysize(unacked));
 196   VerifyInFlightPackets(unacked, arraysize(unacked));
 197   QuicPacketSequenceNumber retransmittable[] = {1};
 198   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 199
 200   // Stop retransmissions on another stream and verify the packet is unchanged.
 201   unacked_packets_.CancelRetransmissionsForStream(stream_id + 2);
 202   VerifyUnackedPackets(unacked, arraysize(unacked));
 203   VerifyInFlightPackets(unacked, arraysize(unacked));
 204   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 205 }
 206
 207 TEST_F(QuicUnackedPacketMapTest, StopRetransmissionAfterRetransmission) {
 208   const QuicStreamId stream_id = 2;
 209   unacked_packets_.AddSentPacket(
 210       CreateRetransmittablePacketForStream(1, stream_id), 0, NOT_RETRANSMISSION,
 211       now_, kDefaultLength, true);
 212   unacked_packets_.AddSentPacket(CreateNonRetransmittablePacket(2), 1,
 213                                  LOSS_RETRANSMISSION, now_, kDefaultLength,
 214                                  true);
 215
 216   QuicPacketSequenceNumber unacked[] = {1, 2};
 217   VerifyUnackedPackets(unacked, arraysize(unacked));
 218   VerifyInFlightPackets(unacked, arraysize(unacked));
 219   QuicPacketSequenceNumber retransmittable[] = {2};
 220   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 221
 222   unacked_packets_.CancelRetransmissionsForStream(stream_id);
 223   VerifyUnackedPackets(unacked, arraysize(unacked));
 224   VerifyInFlightPackets(unacked, arraysize(unacked));
 225   VerifyRetransmittablePackets(nullptr, 0);
 226 }
 227
 228 TEST_F(QuicUnackedPacketMapTest, RetransmittedPacket) {
 229   // Simulate a retransmittable packet being sent, retransmitted, and the first
 230   // transmission being acked.
 231   unacked_packets_.AddSentPacket(CreateRetransmittablePacket(1), 0,
 232                                  NOT_RETRANSMISSION, now_, kDefaultLength,
 233                                  true);
 234   unacked_packets_.AddSentPacket(CreateNonRetransmittablePacket(2), 1,
 235                                  LOSS_RETRANSMISSION, now_, kDefaultLength,
 236                                  true);
 237
 238   QuicPacketSequenceNumber unacked[] = { 1, 2 };
 239   VerifyUnackedPackets(unacked, arraysize(unacked));
 240   VerifyInFlightPackets(unacked, arraysize(unacked));
 241   QuicPacketSequenceNumber retransmittable[] = { 2 };
 242   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 243
 244   unacked_packets_.RemoveRetransmittability(1);
 245   VerifyUnackedPackets(unacked, arraysize(unacked));
 246   VerifyInFlightPackets(unacked, arraysize(unacked));
 247   VerifyRetransmittablePackets(nullptr, 0);
 248
 249   unacked_packets_.IncreaseLargestObserved(2);
 250   VerifyUnackedPackets(unacked, arraysize(unacked));
 251   VerifyInFlightPackets(unacked, arraysize(unacked));
 252   VerifyRetransmittablePackets(nullptr, 0);
 253
 254   unacked_packets_.RemoveFromInFlight(2);
 255   QuicPacketSequenceNumber unacked2[] = { 1 };
 256   VerifyUnackedPackets(unacked2, arraysize(unacked2));
 257   VerifyInFlightPackets(unacked2, arraysize(unacked2));
 258   VerifyRetransmittablePackets(nullptr, 0);
 259
 260   unacked_packets_.RemoveFromInFlight(1);
 261   VerifyUnackedPackets(nullptr, 0);
 262   VerifyInFlightPackets(nullptr, 0);
 263   VerifyRetransmittablePackets(nullptr, 0);
 264 }
 265
 266 TEST_F(QuicUnackedPacketMapTest, RetransmitThreeTimes) {
 267   // Simulate a retransmittable packet being sent and retransmitted twice.
 268   unacked_packets_.AddSentPacket(CreateRetransmittablePacket(1), 0,
 269                                  NOT_RETRANSMISSION, now_, kDefaultLength,
 270                                  true);
 271   unacked_packets_.AddSentPacket(CreateRetransmittablePacket(2), 0,
 272                                  NOT_RETRANSMISSION, now_, kDefaultLength,
 273                                  true);
 274
 275   QuicPacketSequenceNumber unacked[] = { 1, 2 };
 276   VerifyUnackedPackets(unacked, arraysize(unacked));
 277   VerifyInFlightPackets(unacked, arraysize(unacked));
 278   QuicPacketSequenceNumber retransmittable[] = { 1, 2 };
 279   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 280
 281   // Early retransmit 1 as 3 and send new data as 4.
 282   unacked_packets_.IncreaseLargestObserved(2);
 283   unacked_packets_.RemoveFromInFlight(2);
 284   unacked_packets_.RemoveRetransmittability(2);
 285   unacked_packets_.RemoveFromInFlight(1);
 286   unacked_packets_.AddSentPacket(CreateNonRetransmittablePacket(3), 1,
 287                                  LOSS_RETRANSMISSION, now_, kDefaultLength,
 288                                  true);
 289   unacked_packets_.AddSentPacket(CreateRetransmittablePacket(4), 0,
 290                                  NOT_RETRANSMISSION, now_, kDefaultLength,
 291                                  true);
 292
 293   QuicPacketSequenceNumber unacked2[] = { 1, 3, 4 };
 294   VerifyUnackedPackets(unacked2, arraysize(unacked2));
 295   QuicPacketSequenceNumber pending2[] = { 3, 4, };
 296   VerifyInFlightPackets(pending2, arraysize(pending2));
 297   QuicPacketSequenceNumber retransmittable2[] = { 3, 4 };
 298   VerifyRetransmittablePackets(retransmittable2, arraysize(retransmittable2));
 299
 300   // Early retransmit 3 (formerly 1) as 5, and remove 1 from unacked.
 301   unacked_packets_.IncreaseLargestObserved(4);
 302   unacked_packets_.RemoveFromInFlight(4);
 303   unacked_packets_.RemoveRetransmittability(4);
 304   unacked_packets_.AddSentPacket(CreateNonRetransmittablePacket(5), 3,
 305                                  LOSS_RETRANSMISSION, now_, kDefaultLength,
 306                                  true);
 307   unacked_packets_.AddSentPacket(CreateRetransmittablePacket(6), 0,
 308                                  NOT_RETRANSMISSION, now_, kDefaultLength,
 309                                  true);
 310
 311   QuicPacketSequenceNumber unacked3[] = { 3, 5, 6 };
 312   VerifyUnackedPackets(unacked3, arraysize(unacked3));
 313   QuicPacketSequenceNumber pending3[] = { 3, 5, 6 };
 314   VerifyInFlightPackets(pending3, arraysize(pending3));
 315   QuicPacketSequenceNumber retransmittable3[] = { 5, 6 };
 316   VerifyRetransmittablePackets(retransmittable3, arraysize(retransmittable3));
 317
 318   // Early retransmit 5 as 7 and ensure in flight packet 3 is not removed.
 319   unacked_packets_.IncreaseLargestObserved(6);
 320   unacked_packets_.RemoveFromInFlight(6);
 321   unacked_packets_.RemoveRetransmittability(6);
 322   unacked_packets_.AddSentPacket(CreateNonRetransmittablePacket(7), 5,
 323                                  LOSS_RETRANSMISSION, now_, kDefaultLength,
 324                                  true);
 325
 326   QuicPacketSequenceNumber unacked4[] = { 3, 5, 7 };
 327   VerifyUnackedPackets(unacked4, arraysize(unacked4));
 328   QuicPacketSequenceNumber pending4[] = { 3, 5, 7 };
 329   VerifyInFlightPackets(pending4, arraysize(pending4));
 330   QuicPacketSequenceNumber retransmittable4[] = { 7 };
 331   VerifyRetransmittablePackets(retransmittable4, arraysize(retransmittable4));
 332
 333   // Remove the older two transmissions from in flight.
 334   unacked_packets_.RemoveFromInFlight(3);
 335   unacked_packets_.RemoveFromInFlight(5);
 336   QuicPacketSequenceNumber pending5[] = { 7 };
 337   VerifyInFlightPackets(pending5, arraysize(pending5));
 338
 339   // Now test ClearAllPreviousTransmissions, leaving one packet.
 340   unacked_packets_.ClearAllPreviousRetransmissions();
 341   QuicPacketSequenceNumber unacked5[] = { 7 };
 342   VerifyUnackedPackets(unacked5, arraysize(unacked5));
 343   QuicPacketSequenceNumber retransmittable5[] = { 7 };
 344   VerifyRetransmittablePackets(retransmittable5, arraysize(retransmittable5));
 345 }
 346
 347 TEST_F(QuicUnackedPacketMapTest, RetransmitFourTimes) {
 348   // Simulate a retransmittable packet being sent and retransmitted twice.
 349   unacked_packets_.AddSentPacket(CreateRetransmittablePacket(1), 0,
 350                                  NOT_RETRANSMISSION, now_, kDefaultLength,
 351                                  true);
 352   unacked_packets_.AddSentPacket(CreateRetransmittablePacket(2), 0,
 353                                  NOT_RETRANSMISSION, now_, kDefaultLength,
 354                                  true);
 355
 356   QuicPacketSequenceNumber unacked[] = { 1, 2 };
 357   VerifyUnackedPackets(unacked, arraysize(unacked));
 358   VerifyInFlightPackets(unacked, arraysize(unacked));
 359   QuicPacketSequenceNumber retransmittable[] = { 1, 2 };
 360   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 361
 362   // Early retransmit 1 as 3.
 363   unacked_packets_.IncreaseLargestObserved(2);
 364   unacked_packets_.RemoveFromInFlight(2);
 365   unacked_packets_.RemoveRetransmittability(2);
 366   unacked_packets_.RemoveFromInFlight(1);
 367   unacked_packets_.AddSentPacket(CreateNonRetransmittablePacket(3), 1,
 368                                  LOSS_RETRANSMISSION, now_, kDefaultLength,
 369                                  true);
 370
 371   QuicPacketSequenceNumber unacked2[] = { 1, 3 };
 372   VerifyUnackedPackets(unacked2, arraysize(unacked2));
 373   QuicPacketSequenceNumber pending2[] = { 3 };
 374   VerifyInFlightPackets(pending2, arraysize(pending2));
 375   QuicPacketSequenceNumber retransmittable2[] = { 3 };
 376   VerifyRetransmittablePackets(retransmittable2, arraysize(retransmittable2));
 377
 378   // TLP 3 (formerly 1) as 4, and don't remove 1 from unacked.
 379   unacked_packets_.AddSentPacket(CreateNonRetransmittablePacket(4), 3,
 380                                  TLP_RETRANSMISSION, now_, kDefaultLength,
 381                                  true);
 382   unacked_packets_.AddSentPacket(CreateRetransmittablePacket(5), 0,
 383                                  NOT_RETRANSMISSION, now_, kDefaultLength,
 384                                  true);
 385
 386   QuicPacketSequenceNumber unacked3[] = { 1, 3, 4, 5 };
 387   VerifyUnackedPackets(unacked3, arraysize(unacked3));
 388   QuicPacketSequenceNumber pending3[] = { 3, 4, 5 };
 389   VerifyInFlightPackets(pending3, arraysize(pending3));
 390   QuicPacketSequenceNumber retransmittable3[] = { 4, 5 };
 391   VerifyRetransmittablePackets(retransmittable3, arraysize(retransmittable3));
 392
 393   // Early retransmit 4 as 6 and ensure in flight packet 3 is removed.
 394   unacked_packets_.IncreaseLargestObserved(5);
 395   unacked_packets_.RemoveFromInFlight(5);
 396   unacked_packets_.RemoveRetransmittability(5);
 397   unacked_packets_.RemoveFromInFlight(3);
 398   unacked_packets_.RemoveFromInFlight(4);
 399   unacked_packets_.AddSentPacket(CreateNonRetransmittablePacket(6), 4,
 400                                  LOSS_RETRANSMISSION, now_, kDefaultLength,
 401                                  true);
 402
 403   QuicPacketSequenceNumber unacked4[] = { 4, 6 };
 404   VerifyUnackedPackets(unacked4, arraysize(unacked4));
 405   QuicPacketSequenceNumber pending4[] = { 6 };
 406   VerifyInFlightPackets(pending4, arraysize(pending4));
 407   QuicPacketSequenceNumber retransmittable4[] = { 6 };
 408   VerifyRetransmittablePackets(retransmittable4, arraysize(retransmittable4));
 409 }
 410
 411 TEST_F(QuicUnackedPacketMapTest, SendWithGap) {
 412   // Simulate a retransmittable packet being sent, retransmitted, and the first
 413   // transmission being acked.
 414   unacked_packets_.AddSentPacket(CreateRetransmittablePacket(1), 0,
 415                                  NOT_RETRANSMISSION, now_, kDefaultLength,
 416                                  true);
 417   unacked_packets_.AddSentPacket(CreateRetransmittablePacket(3), 0,
 418                                  NOT_RETRANSMISSION, now_, kDefaultLength,
 419                                  true);
 420   unacked_packets_.AddSentPacket(CreateNonRetransmittablePacket(5), 3,
 421                                  LOSS_RETRANSMISSION, now_, kDefaultLength,
 422                                  true);
 423
 424   EXPECT_EQ(1u, unacked_packets_.GetLeastUnacked());
 425   EXPECT_TRUE(unacked_packets_.IsUnacked(1));
 426   EXPECT_FALSE(unacked_packets_.IsUnacked(2));
 427   EXPECT_TRUE(unacked_packets_.IsUnacked(3));
 428   EXPECT_FALSE(unacked_packets_.IsUnacked(4));
 429   EXPECT_TRUE(unacked_packets_.IsUnacked(5));
 430   EXPECT_EQ(5u, unacked_packets_.largest_sent_packet());
 431 }
 432
 433 }  // namespace
 434 }  // namespace test
 435 }  // namespace net