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 372
