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