src/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 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   void RecordPacketRevived(QuicPacketSequenceNumber sequence_number) {
 206     received_manager_.RecordPacketRevived(sequence_number);
 207   }
 208
 209   QuicConnectionStats stats_;
 210   QuicReceivedPacketManager received_manager_;
 211 };
 212
 213 TEST_F(QuicReceivedPacketManagerTest, ReceivedPacketEntropyHash) {
 214   vector<pair<QuicPacketSequenceNumber, QuicPacketEntropyHash> > entropies;
 215   entropies.push_back(make_pair(1, 12));
 216   entropies.push_back(make_pair(7, 1));
 217   entropies.push_back(make_pair(2, 33));
 218   entropies.push_back(make_pair(5, 3));
 219   entropies.push_back(make_pair(8, 34));
 220
 221   for (size_t i = 0; i < entropies.size(); ++i) {
 222     RecordPacketReceipt(entropies[i].first, entropies[i].second);
 223   }
 224
 225   sort(entropies.begin(), entropies.end());
 226
 227   QuicPacketEntropyHash hash = 0;
 228   size_t index = 0;
 229   for (size_t i = 1; i <= (*entropies.rbegin()).first; ++i) {
 230     if (entropies[index].first == i) {
 231       hash ^= entropies[index].second;
 232       ++index;
 233     }
 234     if (i < 3) continue;
 235     EXPECT_EQ(hash, received_manager_.EntropyHash(i));
 236   }
 237   // Reorder by 5 when 2 is received after 7.
 238   EXPECT_EQ(5u, stats_.max_sequence_reordering);
 239   EXPECT_EQ(0u, stats_.max_time_reordering_us);
 240   EXPECT_EQ(2u, stats_.packets_reordered);
 241 }
 242
 243 TEST_F(QuicReceivedPacketManagerTest, EntropyHashBelowLeastObserved) {
 244   EXPECT_EQ(0, received_manager_.EntropyHash(0));
 245   RecordPacketReceipt(4, 5);
 246   EXPECT_EQ(0, received_manager_.EntropyHash(3));
 247 }
 248
 249 TEST_F(QuicReceivedPacketManagerTest, EntropyHashAboveLargestObserved) {
 250   EXPECT_EQ(0, received_manager_.EntropyHash(0));
 251   RecordPacketReceipt(4, 5);
 252   EXPECT_EQ(0, received_manager_.EntropyHash(3));
 253 }
 254
 255 TEST_F(QuicReceivedPacketManagerTest, SetCumulativeEntropyUpTo) {
 256   vector<pair<QuicPacketSequenceNumber, QuicPacketEntropyHash> > entropies;
 257   entropies.push_back(make_pair(1, 12));
 258   entropies.push_back(make_pair(2, 1));
 259   entropies.push_back(make_pair(3, 33));
 260   entropies.push_back(make_pair(4, 3));
 261   entropies.push_back(make_pair(6, 34));
 262   entropies.push_back(make_pair(7, 29));
 263
 264   QuicPacketEntropyHash entropy_hash = 0;
 265   for (size_t i = 0; i < entropies.size(); ++i) {
 266     RecordPacketReceipt(entropies[i].first, entropies[i].second);
 267     entropy_hash ^= entropies[i].second;
 268   }
 269   EXPECT_EQ(entropy_hash, received_manager_.EntropyHash(7));
 270
 271   // Now set the entropy hash up to 5 to be 100.
 272   entropy_hash ^= 100;
 273   for (size_t i = 0; i < 4; ++i) {
 274     entropy_hash ^= entropies[i].second;
 275   }
 276   QuicReceivedPacketManagerPeer::SetCumulativeEntropyUpTo(
 277       &received_manager_, 5, 100);
 278   EXPECT_EQ(entropy_hash, received_manager_.EntropyHash(7));
 279
 280   QuicReceivedPacketManagerPeer::SetCumulativeEntropyUpTo(
 281       &received_manager_, 1, 50);
 282   EXPECT_EQ(entropy_hash, received_manager_.EntropyHash(7));
 283
 284   // No reordering.
 285   EXPECT_EQ(0u, stats_.max_sequence_reordering);
 286   EXPECT_EQ(0u, stats_.max_time_reordering_us);
 287   EXPECT_EQ(0u, stats_.packets_reordered);
 288 }
 289
 290 TEST_F(QuicReceivedPacketManagerTest, DontWaitForPacketsBefore) {
 291   QuicPacketHeader header;
 292   header.packet_sequence_number = 2u;
 293   received_manager_.RecordPacketReceived(0u, header, QuicTime::Zero());
 294   header.packet_sequence_number = 7u;
 295   received_manager_.RecordPacketReceived(0u, header, QuicTime::Zero());
 296   EXPECT_TRUE(received_manager_.IsAwaitingPacket(3u));
 297   EXPECT_TRUE(received_manager_.IsAwaitingPacket(6u));
 298   EXPECT_TRUE(QuicReceivedPacketManagerPeer::DontWaitForPacketsBefore(
 299       &received_manager_, 4));
 300   EXPECT_FALSE(received_manager_.IsAwaitingPacket(3u));
 301   EXPECT_TRUE(received_manager_.IsAwaitingPacket(6u));
 302 }
 303
 304 TEST_F(QuicReceivedPacketManagerTest, UpdateReceivedPacketInfo) {
 305   QuicPacketHeader header;
 306   header.packet_sequence_number = 2u;
 307   QuicTime two_ms = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(2));
 308   received_manager_.RecordPacketReceived(0u, header, two_ms);
 309
 310   QuicAckFrame ack;
 311   received_manager_.UpdateReceivedPacketInfo(&ack, QuicTime::Zero());
 312   // When UpdateReceivedPacketInfo with a time earlier than the time of the
 313   // largest observed packet, make sure that the delta is 0, not negative.
 314   EXPECT_EQ(QuicTime::Delta::Zero(), ack.delta_time_largest_observed);
 315
 316   QuicTime four_ms = QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(4));
 317   received_manager_.UpdateReceivedPacketInfo(&ack, four_ms);
 318   // When UpdateReceivedPacketInfo after not having received a new packet,
 319   // the delta should still be accurate.
 320   EXPECT_EQ(QuicTime::Delta::FromMilliseconds(2),
 321             ack.delta_time_largest_observed);
 322 }
 323
 324 TEST_F(QuicReceivedPacketManagerTest, UpdateReceivedConnectionStats) {
 325   RecordPacketReceipt(1, 0);
 326   RecordPacketReceipt(6, 0);
 327   RecordPacketReceipt(
 328       2, 0, QuicTime::Zero().Add(QuicTime::Delta::FromMilliseconds(1)));
 329
 330   EXPECT_EQ(4u, stats_.max_sequence_reordering);
 331   EXPECT_EQ(1000u, stats_.max_time_reordering_us);
 332   EXPECT_EQ(1u, stats_.packets_reordered);
 333 }
 334
 335 TEST_F(QuicReceivedPacketManagerTest, RevivedPacket) {
 336   RecordPacketReceipt(1, 0);
 337   RecordPacketReceipt(3, 0);
 338   RecordPacketRevived(2);
 339
 340   QuicAckFrame ack;
 341   received_manager_.UpdateReceivedPacketInfo(&ack, QuicTime::Zero());
 342   EXPECT_EQ(1u, ack.missing_packets.size());
 343   EXPECT_EQ(2u, *ack.missing_packets.begin());
 344   EXPECT_EQ(1u, ack.revived_packets.size());
 345   EXPECT_EQ(2u, *ack.missing_packets.begin());
 346 }
 347
 348 TEST_F(QuicReceivedPacketManagerTest, PacketRevivedThenReceived) {
 349   RecordPacketReceipt(1, 0);
 350   RecordPacketReceipt(3, 0);
 351   RecordPacketRevived(2);
 352   RecordPacketReceipt(2, 0);
 353
 354   QuicAckFrame ack;
 355   received_manager_.UpdateReceivedPacketInfo(&ack, QuicTime::Zero());
 356   EXPECT_TRUE(ack.missing_packets.empty());
 357   EXPECT_TRUE(ack.revived_packets.empty());
 358 }
 359
 360
 361 }  // namespace
 362 }  // namespace test
 363 }  // namespace net