net/quic/quic_received_packet_manager_test.cc

   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