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