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