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, NULL,
  29                             0, new RetransmittableFrames());
  30   }
  31
  32   SerializedPacket CreateNonRetransmittablePacket(
  33       QuicPacketSequenceNumber sequence_number) {
  34     return SerializedPacket(
  35         sequence_number, PACKET_1BYTE_SEQUENCE_NUMBER, NULL, 0, NULL);
  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 != NULL) {
  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_.AddPacket(CreateNonRetransmittablePacket(1));
 105   unacked_packets_.SetSent(1, now_, kDefaultAckLength, false);
 106
 107   QuicPacketSequenceNumber unacked[] = { 1 };
 108   VerifyUnackedPackets(unacked, arraysize(unacked));
 109   VerifyInFlightPackets(NULL, 0);
 110   VerifyRetransmittablePackets(NULL, 0);
 111
 112   unacked_packets_.IncreaseLargestObserved(1);
 113   VerifyUnackedPackets(NULL, 0);
 114   VerifyInFlightPackets(NULL, 0);
 115   VerifyRetransmittablePackets(NULL, 0);
 116 }
 117
 118 TEST_F(QuicUnackedPacketMapTest, DiscardOldRttOnly) {
 119   // Acks are only tracked for RTT measurement purposes, and are discarded
 120   // when more than 200 accumulate.
 121   const size_t kNumUnackedPackets = 200;
 122   for (size_t i = 1; i < 400; ++i) {
 123     unacked_packets_.AddPacket(CreateNonRetransmittablePacket(i));
 124     unacked_packets_.SetSent(i, now_, kDefaultAckLength, false);
 125     unacked_packets_.RemoveObsoletePackets();
 126     EXPECT_EQ(min(i, kNumUnackedPackets),
 127               unacked_packets_.GetNumUnackedPacketsDebugOnly());
 128   }
 129 }
 130
 131 TEST_F(QuicUnackedPacketMapTest, RetransmittableInflightAndRtt) {
 132   // Simulate a retransmittable packet being sent and acked.
 133   unacked_packets_.AddPacket(CreateRetransmittablePacket(1));
 134   unacked_packets_.SetSent(1, now_, kDefaultLength, true);
 135
 136   QuicPacketSequenceNumber unacked[] = { 1 };
 137   VerifyUnackedPackets(unacked, arraysize(unacked));
 138   VerifyInFlightPackets(unacked, arraysize(unacked));
 139   VerifyRetransmittablePackets(unacked, arraysize(unacked));
 140
 141   unacked_packets_.RemoveRetransmittability(1);
 142   VerifyUnackedPackets(unacked, arraysize(unacked));
 143   VerifyInFlightPackets(unacked, arraysize(unacked));
 144   VerifyRetransmittablePackets(NULL, 0);
 145
 146   unacked_packets_.IncreaseLargestObserved(1);
 147   VerifyUnackedPackets(unacked, arraysize(unacked));
 148   VerifyInFlightPackets(unacked, arraysize(unacked));
 149   VerifyRetransmittablePackets(NULL, 0);
 150
 151   unacked_packets_.RemoveFromInFlight(1);
 152   VerifyUnackedPackets(NULL, 0);
 153   VerifyInFlightPackets(NULL, 0);
 154   VerifyRetransmittablePackets(NULL, 0);
 155 }
 156
 157 TEST_F(QuicUnackedPacketMapTest, RetransmittedPacket) {
 158   // Simulate a retransmittable packet being sent, retransmitted, and the first
 159   // transmission being acked.
 160   unacked_packets_.AddPacket(CreateRetransmittablePacket(1));
 161   unacked_packets_.SetSent(1, now_, kDefaultLength, true);
 162   unacked_packets_.OnRetransmittedPacket(1, 2, LOSS_RETRANSMISSION);
 163   unacked_packets_.SetSent(2, now_, kDefaultLength, true);
 164
 165   QuicPacketSequenceNumber unacked[] = { 1, 2 };
 166   VerifyUnackedPackets(unacked, arraysize(unacked));
 167   VerifyInFlightPackets(unacked, arraysize(unacked));
 168   QuicPacketSequenceNumber retransmittable[] = { 2 };
 169   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 170
 171   unacked_packets_.RemoveRetransmittability(1);
 172   VerifyUnackedPackets(unacked, arraysize(unacked));
 173   VerifyInFlightPackets(unacked, arraysize(unacked));
 174   VerifyRetransmittablePackets(NULL, 0);
 175
 176   unacked_packets_.IncreaseLargestObserved(2);
 177   VerifyUnackedPackets(unacked, arraysize(unacked));
 178   VerifyInFlightPackets(unacked, arraysize(unacked));
 179   VerifyRetransmittablePackets(NULL, 0);
 180
 181   unacked_packets_.RemoveFromInFlight(2);
 182   QuicPacketSequenceNumber unacked2[] = { 1 };
 183   VerifyUnackedPackets(unacked, arraysize(unacked2));
 184   VerifyInFlightPackets(unacked, arraysize(unacked2));
 185   VerifyRetransmittablePackets(NULL, 0);
 186
 187   unacked_packets_.RemoveFromInFlight(1);
 188   VerifyUnackedPackets(NULL, 0);
 189   VerifyInFlightPackets(NULL, 0);
 190   VerifyRetransmittablePackets(NULL, 0);
 191 }
 192
 193 TEST_F(QuicUnackedPacketMapTest, RetransmitThreeTimes) {
 194   // Simulate a retransmittable packet being sent and retransmitted twice.
 195   unacked_packets_.AddPacket(CreateRetransmittablePacket(1));
 196   unacked_packets_.SetSent(1, now_, kDefaultLength, true);
 197   unacked_packets_.AddPacket(CreateRetransmittablePacket(2));
 198   unacked_packets_.SetSent(2, now_, kDefaultLength, true);
 199
 200   QuicPacketSequenceNumber unacked[] = { 1, 2 };
 201   VerifyUnackedPackets(unacked, arraysize(unacked));
 202   VerifyInFlightPackets(unacked, arraysize(unacked));
 203   QuicPacketSequenceNumber retransmittable[] = { 1, 2 };
 204   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 205
 206   // Early retransmit 1 as 3 and send new data as 4.
 207   unacked_packets_.IncreaseLargestObserved(2);
 208   unacked_packets_.RemoveFromInFlight(2);
 209   unacked_packets_.RemoveRetransmittability(2);
 210   unacked_packets_.RemoveFromInFlight(1);
 211   unacked_packets_.OnRetransmittedPacket(1, 3, LOSS_RETRANSMISSION);
 212   unacked_packets_.SetSent(3, now_, kDefaultLength, true);
 213   unacked_packets_.AddPacket(CreateRetransmittablePacket(4));
 214   unacked_packets_.SetSent(4, now_, kDefaultLength, true);
 215
 216   QuicPacketSequenceNumber unacked2[] = { 1, 3, 4 };
 217   VerifyUnackedPackets(unacked2, arraysize(unacked2));
 218   QuicPacketSequenceNumber pending2[] = { 3, 4, };
 219   VerifyInFlightPackets(pending2, arraysize(pending2));
 220   QuicPacketSequenceNumber retransmittable2[] = { 3, 4 };
 221   VerifyRetransmittablePackets(retransmittable2, arraysize(retransmittable2));
 222
 223   // Early retransmit 3 (formerly 1) as 5, and remove 1 from unacked.
 224   unacked_packets_.IncreaseLargestObserved(4);
 225   unacked_packets_.RemoveFromInFlight(4);
 226   unacked_packets_.RemoveRetransmittability(4);
 227   unacked_packets_.OnRetransmittedPacket(3, 5, LOSS_RETRANSMISSION);
 228   unacked_packets_.SetSent(5, now_, kDefaultLength, true);
 229   unacked_packets_.AddPacket(CreateRetransmittablePacket(6));
 230   unacked_packets_.SetSent(6, now_, kDefaultLength, true);
 231
 232   QuicPacketSequenceNumber unacked3[] = { 3, 5, 6 };
 233   VerifyUnackedPackets(unacked3, arraysize(unacked3));
 234   QuicPacketSequenceNumber pending3[] = { 3, 5, 6 };
 235   VerifyInFlightPackets(pending3, arraysize(pending3));
 236   QuicPacketSequenceNumber retransmittable3[] = { 5, 6 };
 237   VerifyRetransmittablePackets(retransmittable3, arraysize(retransmittable3));
 238
 239   // Early retransmit 5 as 7 and ensure in flight packet 3 is not removed.
 240   unacked_packets_.IncreaseLargestObserved(6);
 241   unacked_packets_.RemoveFromInFlight(6);
 242   unacked_packets_.RemoveRetransmittability(6);
 243   unacked_packets_.OnRetransmittedPacket(5, 7, LOSS_RETRANSMISSION);
 244   unacked_packets_.SetSent(7, now_, kDefaultLength, true);
 245
 246   QuicPacketSequenceNumber unacked4[] = { 3, 5, 7 };
 247   VerifyUnackedPackets(unacked4, arraysize(unacked4));
 248   QuicPacketSequenceNumber pending4[] = { 3, 5, 7 };
 249   VerifyInFlightPackets(pending4, arraysize(pending4));
 250   QuicPacketSequenceNumber retransmittable4[] = { 7 };
 251   VerifyRetransmittablePackets(retransmittable4, arraysize(retransmittable4));
 252
 253   // Remove the older two transmissions from in flight.
 254   unacked_packets_.RemoveFromInFlight(3);
 255   unacked_packets_.RemoveFromInFlight(5);
 256   QuicPacketSequenceNumber pending5[] = { 7 };
 257   VerifyInFlightPackets(pending5, arraysize(pending5));
 258
 259   // Now test ClearAllPreviousTransmissions, leaving one packet.
 260   unacked_packets_.ClearAllPreviousRetransmissions();
 261   QuicPacketSequenceNumber unacked5[] = { 7 };
 262   VerifyUnackedPackets(unacked5, arraysize(unacked5));
 263   QuicPacketSequenceNumber retransmittable5[] = { 7 };
 264   VerifyRetransmittablePackets(retransmittable5, arraysize(retransmittable5));
 265 }
 266
 267 TEST_F(QuicUnackedPacketMapTest, RetransmitFourTimes) {
 268   // Simulate a retransmittable packet being sent and retransmitted twice.
 269   unacked_packets_.AddPacket(CreateRetransmittablePacket(1));
 270   unacked_packets_.SetSent(1, now_, kDefaultLength, true);
 271   unacked_packets_.AddPacket(CreateRetransmittablePacket(2));
 272   unacked_packets_.SetSent(2, now_, kDefaultLength, true);
 273
 274   QuicPacketSequenceNumber unacked[] = { 1, 2 };
 275   VerifyUnackedPackets(unacked, arraysize(unacked));
 276   VerifyInFlightPackets(unacked, arraysize(unacked));
 277   QuicPacketSequenceNumber retransmittable[] = { 1, 2 };
 278   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 279
 280   // Early retransmit 1 as 3.
 281   unacked_packets_.IncreaseLargestObserved(2);
 282   unacked_packets_.RemoveFromInFlight(2);
 283   unacked_packets_.RemoveRetransmittability(2);
 284   unacked_packets_.RemoveFromInFlight(1);
 285   unacked_packets_.OnRetransmittedPacket(1, 3, LOSS_RETRANSMISSION);
 286   unacked_packets_.SetSent(3, now_, kDefaultLength, true);
 287
 288   QuicPacketSequenceNumber unacked2[] = { 1, 3 };
 289   VerifyUnackedPackets(unacked2, arraysize(unacked2));
 290   QuicPacketSequenceNumber pending2[] = { 3 };
 291   VerifyInFlightPackets(pending2, arraysize(pending2));
 292   QuicPacketSequenceNumber retransmittable2[] = { 3 };
 293   VerifyRetransmittablePackets(retransmittable2, arraysize(retransmittable2));
 294
 295   // TLP 3 (formerly 1) as 4, and don't remove 1 from unacked.
 296   unacked_packets_.OnRetransmittedPacket(3, 4, TLP_RETRANSMISSION);
 297   unacked_packets_.SetSent(4, now_, kDefaultLength, true);
 298   unacked_packets_.AddPacket(CreateRetransmittablePacket(5));
 299   unacked_packets_.SetSent(5, now_, kDefaultLength, true);
 300
 301   QuicPacketSequenceNumber unacked3[] = { 1, 3, 4, 5 };
 302   VerifyUnackedPackets(unacked3, arraysize(unacked3));
 303   QuicPacketSequenceNumber pending3[] = { 3, 4, 5 };
 304   VerifyInFlightPackets(pending3, arraysize(pending3));
 305   QuicPacketSequenceNumber retransmittable3[] = { 4, 5 };
 306   VerifyRetransmittablePackets(retransmittable3, arraysize(retransmittable3));
 307
 308   // Early retransmit 4 as 6 and ensure in flight packet 3 is removed.
 309   unacked_packets_.IncreaseLargestObserved(5);
 310   unacked_packets_.RemoveFromInFlight(5);
 311   unacked_packets_.RemoveRetransmittability(5);
 312   unacked_packets_.RemoveFromInFlight(3);
 313   unacked_packets_.RemoveFromInFlight(4);
 314   unacked_packets_.OnRetransmittedPacket(4, 6, LOSS_RETRANSMISSION);
 315   unacked_packets_.SetSent(6, now_, kDefaultLength, true);
 316
 317   QuicPacketSequenceNumber unacked4[] = { 4, 6 };
 318   VerifyUnackedPackets(unacked4, arraysize(unacked4));
 319   QuicPacketSequenceNumber pending4[] = { 6 };
 320   VerifyInFlightPackets(pending4, arraysize(pending4));
 321   QuicPacketSequenceNumber retransmittable4[] = { 6 };
 322   VerifyRetransmittablePackets(retransmittable4, arraysize(retransmittable4));
 323 }
 324
 325 TEST_F(QuicUnackedPacketMapTest, RestoreInflight) {
 326   // Simulate a retransmittable packet being sent, retransmitted, and the first
 327   // transmission being acked.
 328   unacked_packets_.AddPacket(CreateRetransmittablePacket(1));
 329   unacked_packets_.SetSent(1, now_, kDefaultLength, true);
 330   unacked_packets_.OnRetransmittedPacket(1, 2, RTO_RETRANSMISSION);
 331   unacked_packets_.RemoveFromInFlight(1);
 332   unacked_packets_.SetSent(2, now_, kDefaultLength, true);
 333
 334   QuicPacketSequenceNumber unacked[] = { 1, 2 };
 335   VerifyUnackedPackets(unacked, arraysize(unacked));
 336   QuicPacketSequenceNumber retransmittable[] = { 2 };
 337   VerifyInFlightPackets(retransmittable, arraysize(retransmittable));
 338   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 339   EXPECT_EQ(kDefaultLength, unacked_packets_.bytes_in_flight());
 340
 341   // Simulate an F-RTO, and restore 1 to flight.
 342   unacked_packets_.RestoreInFlight(1);
 343   VerifyUnackedPackets(unacked, arraysize(unacked));
 344   VerifyInFlightPackets(unacked, arraysize(unacked));
 345   VerifyRetransmittablePackets(retransmittable, arraysize(retransmittable));
 346   EXPECT_EQ(2 * kDefaultLength, unacked_packets_.bytes_in_flight());
 347 }
 348
 349 TEST_F(QuicUnackedPacketMapTest, SendWithGap) {
 350   // Simulate a retransmittable packet being sent, retransmitted, and the first
 351   // transmission being acked.
 352   unacked_packets_.AddPacket(CreateRetransmittablePacket(1));
 353   unacked_packets_.SetSent(1, now_, kDefaultLength, true);
 354   unacked_packets_.AddPacket(CreateRetransmittablePacket(3));
 355   unacked_packets_.SetSent(3, now_, kDefaultLength, true);
 356   unacked_packets_.OnRetransmittedPacket(1, 5, LOSS_RETRANSMISSION);
 357   unacked_packets_.SetSent(5, now_, kDefaultLength, true);
 358
 359   EXPECT_EQ(1u, unacked_packets_.GetLeastUnacked());
 360   EXPECT_TRUE(unacked_packets_.IsUnacked(1));
 361   EXPECT_FALSE(unacked_packets_.IsUnacked(2));
 362   EXPECT_TRUE(unacked_packets_.IsUnacked(3));
 363   EXPECT_FALSE(unacked_packets_.IsUnacked(4));
 364   EXPECT_TRUE(unacked_packets_.IsUnacked(5));
 365   EXPECT_EQ(5u, unacked_packets_.largest_sent_packet());
 366 }
 367
 368
 369 }  // namespace
 370 }  // namespace test
 371 }  // namespace net