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