1 // Copyright 2013 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_received_packet_manager.h"
6
7 #include <algorithm>
8 #include <vector>
9
10 #include "net/quic/quic_connection_stats.h"
11 #include "net/quic/test_tools/quic_received_packet_manager_peer.h"
12 #include "testing/gmock/include/gmock/gmock.h"
13 #include "testing/gtest/include/gtest/gtest.h"
14
15 using std::make_pair;
16 using std::pair;
17 using std::vector;
18
19 namespace net {
20 namespace test {
21
22 class EntropyTrackerPeer {
23 public:
first_gap(const QuicReceivedPacketManager::EntropyTracker & tracker)24 static QuicPacketSequenceNumber first_gap(
25 const QuicReceivedPacketManager::EntropyTracker& tracker) {
26 return tracker.first_gap_;
27 }
largest_observed(const QuicReceivedPacketManager::EntropyTracker & tracker)28 static QuicPacketSequenceNumber largest_observed(
29 const QuicReceivedPacketManager::EntropyTracker& tracker) {
30 return tracker.largest_observed_;
31 }
packets_entropy_size(const QuicReceivedPacketManager::EntropyTracker & tracker)32 static int packets_entropy_size(
33 const QuicReceivedPacketManager::EntropyTracker& tracker) {
34 return tracker.packets_entropy_.size();
35 }
IsTrackingPacket(const QuicReceivedPacketManager::EntropyTracker & tracker,QuicPacketSequenceNumber sequence_number)36 static bool IsTrackingPacket(
37 const QuicReceivedPacketManager::EntropyTracker& tracker,
38 QuicPacketSequenceNumber sequence_number) {
39 return sequence_number >= tracker.first_gap_ &&
40 sequence_number <
41 (tracker.first_gap_ + tracker.packets_entropy_.size()) &&
42 tracker.packets_entropy_[sequence_number - tracker.first_gap_].second;
43 }
44 };
45
46 namespace {
47
48 // Entropy of individual packets is not tracked if there are no gaps.
TEST(EntropyTrackerTest,NoGaps)49 TEST(EntropyTrackerTest, NoGaps) {
50 QuicReceivedPacketManager::EntropyTracker tracker;
51
52 tracker.RecordPacketEntropyHash(1, 23);
53 tracker.RecordPacketEntropyHash(2, 42);
54
55 EXPECT_EQ(23 ^ 42, tracker.EntropyHash(2));
56 EXPECT_EQ(3u, EntropyTrackerPeer::first_gap(tracker));
57
58 EXPECT_EQ(2u, EntropyTrackerPeer::largest_observed(tracker));
59 EXPECT_EQ(0, EntropyTrackerPeer::packets_entropy_size(tracker));
60 EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 1));
61 EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 2));
62 }
63
64 // Entropy of individual packets is tracked as long as there are gaps.
65 // Filling the first gap results in entropy getting garbage collected.
TEST(EntropyTrackerTest,FillGaps)66 TEST(EntropyTrackerTest, FillGaps) {
67 QuicReceivedPacketManager::EntropyTracker tracker;
68
69 tracker.RecordPacketEntropyHash(2, 5);
70 tracker.RecordPacketEntropyHash(5, 17);
71 tracker.RecordPacketEntropyHash(6, 23);
72 tracker.RecordPacketEntropyHash(9, 42);
73
74 EXPECT_EQ(1u, EntropyTrackerPeer::first_gap(tracker));
75 EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
76 EXPECT_EQ(9, EntropyTrackerPeer::packets_entropy_size(tracker));
77
78 EXPECT_EQ(5, tracker.EntropyHash(2));
79 EXPECT_EQ(5 ^ 17, tracker.EntropyHash(5));
80 EXPECT_EQ(5 ^ 17 ^ 23, tracker.EntropyHash(6));
81 EXPECT_EQ(5 ^ 17 ^ 23 ^ 42, tracker.EntropyHash(9));
82
83 EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 1));
84 EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 2));
85 EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 5));
86 EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 6));
87 EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 9));
88
89 // Fill the gap at 1.
90 tracker.RecordPacketEntropyHash(1, 2);
91
92 EXPECT_EQ(3u, EntropyTrackerPeer::first_gap(tracker));
93 EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
94 EXPECT_EQ(7, EntropyTrackerPeer::packets_entropy_size(tracker));
95
96 EXPECT_EQ(2 ^ 5 ^ 17, tracker.EntropyHash(5));
97 EXPECT_EQ(2 ^ 5 ^ 17 ^ 23, tracker.EntropyHash(6));
98 EXPECT_EQ(2 ^ 5 ^ 17 ^ 23 ^ 42, tracker.EntropyHash(9));
99
100 EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 1));
101 EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 2));
102 EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 5));
103 EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 6));
104 EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 9));
105
106 // Fill the gap at 4.
107 tracker.RecordPacketEntropyHash(4, 2);
108
109 EXPECT_EQ(3u, EntropyTrackerPeer::first_gap(tracker));
110 EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
111 EXPECT_EQ(7, EntropyTrackerPeer::packets_entropy_size(tracker));
112
113 EXPECT_EQ(5, tracker.EntropyHash(4));
114 EXPECT_EQ(5 ^ 17, tracker.EntropyHash(5));
115 EXPECT_EQ(5 ^ 17 ^ 23, tracker.EntropyHash(6));
116 EXPECT_EQ(5 ^ 17 ^ 23 ^ 42, tracker.EntropyHash(9));
117
118 EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 3));
119 EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 4));
120 EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 5));
121 EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 6));
122 EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 9));
123
124 // Fill the gap at 3. Entropy for packets 3 to 6 are forgotten.
125 tracker.RecordPacketEntropyHash(3, 2);
126
127 EXPECT_EQ(7u, EntropyTrackerPeer::first_gap(tracker));
128 EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
129 EXPECT_EQ(3, EntropyTrackerPeer::packets_entropy_size(tracker));
130
131 EXPECT_EQ(2 ^ 5 ^ 17 ^ 23 ^ 42, tracker.EntropyHash(9));
132
133 EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 3));
134 EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 4));
135 EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 5));
136 EXPECT_FALSE(EntropyTrackerPeer::IsTrackingPacket(tracker, 6));
137 EXPECT_TRUE(EntropyTrackerPeer::IsTrackingPacket(tracker, 9));
138
139 // Fill in the rest.
140 tracker.RecordPacketEntropyHash(7, 2);
141 tracker.RecordPacketEntropyHash(8, 2);
142
143 EXPECT_EQ(10u, EntropyTrackerPeer::first_gap(tracker));
144 EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
145 EXPECT_EQ(0, EntropyTrackerPeer::packets_entropy_size(tracker));
146
147 EXPECT_EQ(2 ^ 5 ^ 17 ^ 23 ^ 42, tracker.EntropyHash(9));
148 }
149
TEST(EntropyTrackerTest,SetCumulativeEntropyUpTo)150 TEST(EntropyTrackerTest, SetCumulativeEntropyUpTo) {
151 QuicReceivedPacketManager::EntropyTracker tracker;
152
153 tracker.RecordPacketEntropyHash(2, 5);
154 tracker.RecordPacketEntropyHash(5, 17);
155 tracker.RecordPacketEntropyHash(6, 23);
156 tracker.RecordPacketEntropyHash(9, 42);
157
158 EXPECT_EQ(1u, EntropyTrackerPeer::first_gap(tracker));
159 EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
160 EXPECT_EQ(9, EntropyTrackerPeer::packets_entropy_size(tracker));
161
162 // Inform the tracker about value of the hash at a gap.
163 tracker.SetCumulativeEntropyUpTo(3, 7);
164 EXPECT_EQ(3u, EntropyTrackerPeer::first_gap(tracker));
165 EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
166 EXPECT_EQ(7, EntropyTrackerPeer::packets_entropy_size(tracker));
167
168 EXPECT_EQ(7 ^ 17, tracker.EntropyHash(5));
169 EXPECT_EQ(7 ^ 17 ^ 23, tracker.EntropyHash(6));
170 EXPECT_EQ(7 ^ 17 ^ 23 ^ 42, tracker.EntropyHash(9));
171
172 // Inform the tracker about value of the hash at a known location.
173 tracker.SetCumulativeEntropyUpTo(6, 1);
174 EXPECT_EQ(7u, EntropyTrackerPeer::first_gap(tracker));
175 EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
176 EXPECT_EQ(3, EntropyTrackerPeer::packets_entropy_size(tracker));
177
178 EXPECT_EQ(1 ^ 23 ^ 42, tracker.EntropyHash(9));
179
180 // Inform the tracker about value of the hash at the last location.
181 tracker.SetCumulativeEntropyUpTo(9, 21);
182 EXPECT_EQ(10u, EntropyTrackerPeer::first_gap(tracker));
183 EXPECT_EQ(9u, EntropyTrackerPeer::largest_observed(tracker));
184 EXPECT_EQ(0, EntropyTrackerPeer::packets_entropy_size(tracker));
185
186 EXPECT_EQ(42 ^ 21, tracker.EntropyHash(9));
187 }
188
189 class QuicReceivedPacketManagerTest : public ::testing::Test {
190 protected:
QuicReceivedPacketManagerTest()191 QuicReceivedPacketManagerTest() : received_manager_(&stats_) {}
192
RecordPacketReceipt(QuicPacketSequenceNumber sequence_number,QuicPacketEntropyHash entropy_hash)193 void RecordPacketReceipt(QuicPacketSequenceNumber sequence_number,
194 QuicPacketEntropyHash entropy_hash) {
195 RecordPacketReceipt(sequence_number, entropy_hash, QuicTime::Zero());
196 }
197
RecordPacketReceipt(QuicPacketSequenceNumber sequence_number,QuicPacketEntropyHash entropy_hash,QuicTime receipt_time)198 void RecordPacketReceipt(QuicPacketSequenceNumber sequence_number,
199 QuicPacketEntropyHash entropy_hash,
200 QuicTime receipt_time) {
201 QuicPacketHeader header;
202 header.packet_sequence_number = sequence_number;
203 header.entropy_hash = entropy_hash;
204 received_manager_.RecordPacketReceived(0u, header, receipt_time);
205 }
206
RecordPacketRevived(QuicPacketSequenceNumber sequence_number)207 void RecordPacketRevived(QuicPacketSequenceNumber sequence_number) {
208 received_manager_.RecordPacketRevived(sequence_number);
209 }
210
211 QuicConnectionStats stats_;
212 QuicReceivedPacketManager received_manager_;
213 };
214
TEST_F(QuicReceivedPacketManagerTest,ReceivedPacketEntropyHash)215 TEST_F(QuicReceivedPacketManagerTest, ReceivedPacketEntropyHash) {
216 vector<pair<QuicPacketSequenceNumber, QuicPacketEntropyHash> > entropies;
217 entropies.push_back(make_pair(1, 12));
218 entropies.push_back(make_pair(7, 1));
219 entropies.push_back(make_pair(2, 33));
220 entropies.push_back(make_pair(5, 3));
221 entropies.push_back(make_pair(8, 34));
222
223 for (size_t i = 0; i < entropies.size(); ++i) {
224 RecordPacketReceipt(entropies[i].first, entropies[i].second);
225 }
226
227 sort(entropies.begin(), entropies.end());
228
229 QuicPacketEntropyHash hash = 0;
230 size_t index = 0;
231 for (size_t i = 1; i <= (*entropies.rbegin()).first; ++i) {
232 if (entropies[index].first == i) {
233 hash ^= entropies[index].second;
234 ++index;
235 }
236 if (i < 3) continue;
237 EXPECT_EQ(hash, received_manager_.EntropyHash(i));
238 }
239 // Reorder by 5 when 2 is received after 7.
240 EXPECT_EQ(5u, stats_.max_sequence_reordering);
241 EXPECT_EQ(0u, stats_.max_time_reordering_us);
242 EXPECT_EQ(2u, stats_.packets_reordered);
243 }
244
TEST_F(QuicReceivedPacketManagerTest,EntropyHashBelowLeastObserved)245 TEST_F(QuicReceivedPacketManagerTest, EntropyHashBelowLeastObserved) {
246 EXPECT_EQ(0, received_manager_.EntropyHash(0));
247 RecordPacketReceipt(4, 5);
248 EXPECT_EQ(0, received_manager_.EntropyHash(3));
249 }
250
TEST_F(QuicReceivedPacketManagerTest,EntropyHashAboveLargestObserved)251 TEST_F(QuicReceivedPacketManagerTest, EntropyHashAboveLargestObserved) {
252 EXPECT_EQ(0, received_manager_.EntropyHash(0));
253 RecordPacketReceipt(4, 5);
254 EXPECT_EQ(0, received_manager_.EntropyHash(3));
255 }
256
TEST_F(QuicReceivedPacketManagerTest,SetCumulativeEntropyUpTo)257 TEST_F(QuicReceivedPacketManagerTest, SetCumulativeEntropyUpTo) {
258 vector<pair<QuicPacketSequenceNumber, QuicPacketEntropyHash> > entropies;
259 entropies.push_back(make_pair(1, 12));
260 entropies.push_back(make_pair(2, 1));
261 entropies.push_back(make_pair(3, 33));
262 entropies.push_back(make_pair(4, 3));
263 entropies.push_back(make_pair(6, 34));
264 entropies.push_back(make_pair(7, 29));
265
266 QuicPacketEntropyHash entropy_hash = 0;
267 for (size_t i = 0; i < entropies.size(); ++i) {
268 RecordPacketReceipt(entropies[i].first, entropies[i].second);
269 entropy_hash ^= entropies[i].second;
270 }
271 EXPECT_EQ(entropy_hash, received_manager_.EntropyHash(7));
272
273 // Now set the entropy hash up to 5 to be 100.
274 entropy_hash ^= 100;
275 for (size_t i = 0; i < 4; ++i) {
276 entropy_hash ^= entropies[i].second;
277 }
278 QuicReceivedPacketManagerPeer::SetCumulativeEntropyUpTo(
279 &received_manager_, 5, 100);
280 EXPECT_EQ(entropy_hash, received_manager_.EntropyHash(7));
281
282 QuicReceivedPacketManagerPeer::SetCumulativeEntropyUpTo(
283 &received_manager_, 1, 50);
284 EXPECT_EQ(entropy_hash, received_manager_.EntropyHash(7));
285
286 // No reordering.
287 EXPECT_EQ(0u, stats_.max_sequence_reordering);
288 EXPECT_EQ(0u, stats_.max_time_reordering_us);
289 EXPECT_EQ(0u, stats_.packets_reordered);
290 }
291
TEST_F(QuicReceivedPacketManagerTest,DontWaitForPacketsBefore)292 TEST_F(QuicReceivedPacketManagerTest, DontWaitForPacketsBefore) {
293 QuicPacketHeader header;
294 header.packet_sequence_number = 2u;
295 received_manager_.RecordPacketReceived(0u, header, QuicTime::Zero());
296 header.packet_sequence_number = 7u;
297 received_manager_.RecordPacketReceived(0u, header, QuicTime::Zero());
298 EXPECT_TRUE(received_manager_.IsAwaitingPacket(3u));
299 EXPECT_TRUE(received_manager_.IsAwaitingPacket(6u));
300 EXPECT_TRUE(QuicReceivedPacketManagerPeer::DontWaitForPacketsBefore(
301 &received_manager_, 4));
302 EXPECT_FALSE(received_manager_.IsAwaitingPacket(3u));
303 EXPECT_TRUE(received_manager_.IsAwaitingPacket(6u));
304 }
305
TEST_F(QuicReceivedPacketManagerTest,UpdateReceivedPacketInfo)306 TEST_F(QuicReceivedPacketManagerTest, UpdateReceivedPacketInfo) {
307 QuicPacketHeader header;
308 header.packet_sequence_number = 2u;
309 QuicTime two_ms = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(2));
310 received_manager_.RecordPacketReceived(0u, header, two_ms);
311
312 QuicAckFrame ack;
313 received_manager_.UpdateReceivedPacketInfo(&ack, QuicTime::Zero());
314 // When UpdateReceivedPacketInfo with a time earlier than the time of the
315 // largest observed packet, make sure that the delta is 0, not negative.
316 EXPECT_EQ(QuicTime::Delta::Zero(), ack.delta_time_largest_observed);
317
318 QuicTime four_ms = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(4));
319 received_manager_.UpdateReceivedPacketInfo(&ack, four_ms);
320 // When UpdateReceivedPacketInfo after not having received a new packet,
321 // the delta should still be accurate.
322 EXPECT_EQ(QuicTime::Delta::FromMilliseconds(2),
323 ack.delta_time_largest_observed);
324 }
325
TEST_F(QuicReceivedPacketManagerTest,UpdateReceivedConnectionStats)326 TEST_F(QuicReceivedPacketManagerTest, UpdateReceivedConnectionStats) {
327 RecordPacketReceipt(1, 0);
328 RecordPacketReceipt(6, 0);
329 RecordPacketReceipt(
330 2, 0, QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(1)));
331
332 EXPECT_EQ(4u, stats_.max_sequence_reordering);
333 EXPECT_EQ(1000u, stats_.max_time_reordering_us);
334 EXPECT_EQ(1u, stats_.packets_reordered);
335 }
336
TEST_F(QuicReceivedPacketManagerTest,RevivedPacket)337 TEST_F(QuicReceivedPacketManagerTest, RevivedPacket) {
338 RecordPacketReceipt(1, 0);
339 RecordPacketReceipt(3, 0);
340 RecordPacketRevived(2);
341
342 QuicAckFrame ack;
343 received_manager_.UpdateReceivedPacketInfo(&ack, QuicTime::Zero());
344 EXPECT_EQ(1u, ack.missing_packets.size());
345 EXPECT_EQ(2u, *ack.missing_packets.begin());
346 EXPECT_EQ(1u, ack.revived_packets.size());
347 EXPECT_EQ(2u, *ack.missing_packets.begin());
348 }
349
TEST_F(QuicReceivedPacketManagerTest,PacketRevivedThenReceived)350 TEST_F(QuicReceivedPacketManagerTest, PacketRevivedThenReceived) {
351 RecordPacketReceipt(1, 0);
352 RecordPacketReceipt(3, 0);
353 RecordPacketRevived(2);
354 RecordPacketReceipt(2, 0);
355
356 QuicAckFrame ack;
357 received_manager_.UpdateReceivedPacketInfo(&ack, QuicTime::Zero());
358 EXPECT_TRUE(ack.missing_packets.empty());
359 EXPECT_TRUE(ack.revived_packets.empty());
360 }
361
362
363 } // namespace
364 } // namespace test
365 } // namespace net
366