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