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