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: 24 static QuicPacketSequenceNumber first_gap( 25 const QuicReceivedPacketManager::EntropyTracker& tracker) { 26 return tracker.first_gap_; 27 } 28 static QuicPacketSequenceNumber largest_observed( 29 const QuicReceivedPacketManager::EntropyTracker& tracker) { 30 return tracker.largest_observed_; 31 } 32 static int packets_entropy_size( 33 const QuicReceivedPacketManager::EntropyTracker& tracker) { 34 return tracker.packets_entropy_.size(); 35 } 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. 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. 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 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: 191 QuicReceivedPacketManagerTest() : received_manager_(&stats_) {} 192 193 void RecordPacketReceipt(QuicPacketSequenceNumber sequence_number, 194 QuicPacketEntropyHash entropy_hash) { 195 RecordPacketReceipt(sequence_number, entropy_hash, QuicTime::Zero()); 196 } 197 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 207 void RecordPacketRevived(QuicPacketSequenceNumber sequence_number) { 208 received_manager_.RecordPacketRevived(sequence_number); 209 } 210 211 QuicConnectionStats stats_; 212 QuicReceivedPacketManager received_manager_; 213 }; 214 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 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 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 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 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 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 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 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 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
