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