net/quic/quic_fec_group_test.cc

   1 // Copyright (c) 2012 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_fec_group.h"
   6
   7 #include <algorithm>
   8 #include <vector>
   9
  10 #include "base/basictypes.h"
  11 #include "base/logging.h"
  12 #include "base/memory/scoped_ptr.h"
  13 #include "testing/gmock/include/gmock/gmock.h"
  14
  15 using ::testing::_;
  16 using base::StringPiece;
  17 using std::string;
  18
  19 namespace net {
  20
  21 namespace {
  22
  23 // kData[] and kEntropyFlag[] are indexed by packet numbers, which
  24 // start at 1, so their first elements are dummy.
  25 const char* kData[] = {
  26     "",  // dummy
  27     // kData[1] must be at least as long as every element of kData[], because
  28     // it is used to calculate kDataMaxLen.
  29     "abc12345678",
  30     "987defg",
  31     "ghi12345",
  32     "987jlkmno",
  33     "mno4567890",
  34     "789pqrstuvw",
  35 };
  36 // The maximum length of an element of kData.
  37 const size_t kDataMaxLen = strlen(kData[1]);
  38 // A suitable test data string, whose length is kDataMaxLen.
  39 const char* kDataSingle = kData[1];
  40
  41 const bool kEntropyFlag[] = {
  42     false,  // dummy
  43     false,
  44     true,
  45     true,
  46     false,
  47     true,
  48     true,
  49 };
  50
  51 }  // namespace
  52
  53 class QuicFecGroupTest : public ::testing::Test {
  54  protected:
  55   void RunTest(size_t num_packets, size_t lost_packet, bool out_of_order) {
  56     // kData[] and kEntropyFlag[] are indexed by packet numbers, which
  57     // start at 1.
  58     DCHECK_GE(arraysize(kData), num_packets);
  59     scoped_ptr<char[]> redundancy(new char[kDataMaxLen]);
  60     for (size_t i = 0; i < kDataMaxLen; i++) {
  61       redundancy[i] = 0x00;
  62     }
  63     // XOR in the packets.
  64     for (size_t packet = 1; packet <= num_packets; ++packet) {
  65       for (size_t i = 0; i < kDataMaxLen; i++) {
  66         uint8 byte = i > strlen(kData[packet]) ? 0x00 : kData[packet][i];
  67         redundancy[i] = redundancy[i] ^ byte;
  68       }
  69     }
  70
  71     QuicFecGroup group;
  72
  73     // If we're out of order, send the FEC packet in the position of the
  74     // lost packet. Otherwise send all (non-missing) packets, then FEC.
  75     if (out_of_order) {
  76       // Update the FEC state for each non-lost packet.
  77       for (size_t packet = 1; packet <= num_packets; packet++) {
  78         if (packet == lost_packet) {
  79           ASSERT_FALSE(group.IsFinished());
  80           QuicFecData fec;
  81           fec.fec_group = 1u;
  82           fec.redundancy = StringPiece(redundancy.get(), kDataMaxLen);
  83           ASSERT_TRUE(
  84               group.UpdateFec(ENCRYPTION_FORWARD_SECURE, num_packets + 1, fec));
  85         } else {
  86           QuicPacketHeader header;
  87           header.packet_packet_number = packet;
  88           header.entropy_flag = kEntropyFlag[packet];
  89           ASSERT_TRUE(group.Update(ENCRYPTION_FORWARD_SECURE, header,
  90                                    kData[packet]));
  91         }
  92         ASSERT_TRUE(group.CanRevive() == (packet == num_packets));
  93       }
  94     } else {
  95       // Update the FEC state for each non-lost packet.
  96       for (size_t packet = 1; packet <= num_packets; packet++) {
  97         if (packet == lost_packet) {
  98           continue;
  99         }
 100
 101         QuicPacketHeader header;
 102         header.packet_packet_number = packet;
 103         header.entropy_flag = kEntropyFlag[packet];
 104         ASSERT_TRUE(group.Update(ENCRYPTION_FORWARD_SECURE, header,
 105                                  kData[packet]));
 106         ASSERT_FALSE(group.CanRevive());
 107       }
 108
 109       ASSERT_FALSE(group.IsFinished());
 110       // Attempt to revive the missing packet.
 111       QuicFecData fec;
 112       fec.fec_group = 1u;
 113       fec.redundancy = StringPiece(redundancy.get(), kDataMaxLen);
 114
 115       ASSERT_TRUE(
 116           group.UpdateFec(ENCRYPTION_FORWARD_SECURE, num_packets + 1, fec));
 117     }
 118     QuicPacketHeader header;
 119     char recovered[kMaxPacketSize];
 120     ASSERT_TRUE(group.CanRevive());
 121     size_t len = group.Revive(&header, recovered, arraysize(recovered));
 122     ASSERT_NE(0u, len)
 123         << "Failed to revive packet " << lost_packet << " out of "
 124         << num_packets;
 125     EXPECT_EQ(lost_packet, header.packet_packet_number)
 126         << "Failed to revive packet " << lost_packet << " out of "
 127         << num_packets;
 128     // Revived packets have an unknown entropy.
 129     EXPECT_FALSE(header.entropy_flag);
 130     ASSERT_GE(len, strlen(kData[lost_packet])) << "Incorrect length";
 131     for (size_t i = 0; i < strlen(kData[lost_packet]); i++) {
 132       EXPECT_EQ(kData[lost_packet][i], recovered[i]);
 133     }
 134     ASSERT_TRUE(group.IsFinished());
 135   }
 136 };
 137
 138 TEST_F(QuicFecGroupTest, UpdateAndRevive) {
 139   RunTest(2, 1, false);
 140   RunTest(2, 2, false);
 141
 142   RunTest(3, 1, false);
 143   RunTest(3, 2, false);
 144   RunTest(3, 3, false);
 145 }
 146
 147 TEST_F(QuicFecGroupTest, UpdateAndReviveOutOfOrder) {
 148   RunTest(2, 1, true);
 149   RunTest(2, 2, true);
 150
 151   RunTest(3, 1, true);
 152   RunTest(3, 2, true);
 153   RunTest(3, 3, true);
 154 }
 155
 156 TEST_F(QuicFecGroupTest, UpdateFecIfReceivedPacketIsNotCovered) {
 157   char data1[] = "abc123";
 158   char redundancy[arraysize(data1)];
 159   for (size_t i = 0; i < arraysize(data1); i++) {
 160     redundancy[i] = data1[i];
 161   }
 162
 163   QuicFecGroup group;
 164
 165   QuicPacketHeader header;
 166   header.packet_packet_number = 3;
 167   group.Update(ENCRYPTION_FORWARD_SECURE, header, data1);
 168
 169   QuicFecData fec;
 170   fec.fec_group = 1u;
 171   fec.redundancy = redundancy;
 172
 173   header.packet_packet_number = 2;
 174   ASSERT_FALSE(group.UpdateFec(ENCRYPTION_FORWARD_SECURE, 2, fec));
 175 }
 176
 177 TEST_F(QuicFecGroupTest, ProtectsPacketsBefore) {
 178   QuicPacketHeader header;
 179   header.packet_packet_number = 3;
 180
 181   QuicFecGroup group;
 182   ASSERT_TRUE(group.Update(ENCRYPTION_FORWARD_SECURE, header, kDataSingle));
 183
 184   EXPECT_FALSE(group.ProtectsPacketsBefore(1));
 185   EXPECT_FALSE(group.ProtectsPacketsBefore(2));
 186   EXPECT_FALSE(group.ProtectsPacketsBefore(3));
 187   EXPECT_TRUE(group.ProtectsPacketsBefore(4));
 188   EXPECT_TRUE(group.ProtectsPacketsBefore(5));
 189   EXPECT_TRUE(group.ProtectsPacketsBefore(50));
 190 }
 191
 192 TEST_F(QuicFecGroupTest, ProtectsPacketsBeforeWithSeveralPackets) {
 193   QuicPacketHeader header;
 194   header.packet_packet_number = 3;
 195
 196   QuicFecGroup group;
 197   ASSERT_TRUE(group.Update(ENCRYPTION_FORWARD_SECURE, header, kDataSingle));
 198
 199   header.packet_packet_number = 7;
 200   ASSERT_TRUE(group.Update(ENCRYPTION_FORWARD_SECURE, header, kDataSingle));
 201
 202   header.packet_packet_number = 5;
 203   ASSERT_TRUE(group.Update(ENCRYPTION_FORWARD_SECURE, header, kDataSingle));
 204
 205   EXPECT_FALSE(group.ProtectsPacketsBefore(1));
 206   EXPECT_FALSE(group.ProtectsPacketsBefore(2));
 207   EXPECT_FALSE(group.ProtectsPacketsBefore(3));
 208   EXPECT_TRUE(group.ProtectsPacketsBefore(4));
 209   EXPECT_TRUE(group.ProtectsPacketsBefore(5));
 210   EXPECT_TRUE(group.ProtectsPacketsBefore(6));
 211   EXPECT_TRUE(group.ProtectsPacketsBefore(7));
 212   EXPECT_TRUE(group.ProtectsPacketsBefore(8));
 213   EXPECT_TRUE(group.ProtectsPacketsBefore(9));
 214   EXPECT_TRUE(group.ProtectsPacketsBefore(50));
 215 }
 216
 217 TEST_F(QuicFecGroupTest, ProtectsPacketsBeforeWithFecData) {
 218   QuicFecData fec;
 219   fec.fec_group = 2u;
 220   fec.redundancy = kDataSingle;
 221
 222   QuicFecGroup group;
 223   ASSERT_TRUE(group.UpdateFec(ENCRYPTION_FORWARD_SECURE, 3, fec));
 224
 225   EXPECT_FALSE(group.ProtectsPacketsBefore(1));
 226   EXPECT_FALSE(group.ProtectsPacketsBefore(2));
 227   EXPECT_TRUE(group.ProtectsPacketsBefore(3));
 228   EXPECT_TRUE(group.ProtectsPacketsBefore(4));
 229   EXPECT_TRUE(group.ProtectsPacketsBefore(5));
 230   EXPECT_TRUE(group.ProtectsPacketsBefore(50));
 231 }
 232
 233 TEST_F(QuicFecGroupTest, EffectiveEncryptionLevel) {
 234   QuicFecGroup group;
 235   EXPECT_EQ(NUM_ENCRYPTION_LEVELS, group.effective_encryption_level());
 236
 237   QuicPacketHeader header;
 238   header.packet_packet_number = 5;
 239   ASSERT_TRUE(group.Update(ENCRYPTION_INITIAL, header, kDataSingle));
 240   EXPECT_EQ(ENCRYPTION_INITIAL, group.effective_encryption_level());
 241
 242   QuicFecData fec;
 243   fec.fec_group = 1u;
 244   fec.redundancy = kDataSingle;
 245   ASSERT_TRUE(group.UpdateFec(ENCRYPTION_FORWARD_SECURE, 7, fec));
 246   EXPECT_EQ(ENCRYPTION_INITIAL, group.effective_encryption_level());
 247
 248   header.packet_packet_number = 3;
 249   ASSERT_TRUE(group.Update(ENCRYPTION_NONE, header, kDataSingle));
 250   EXPECT_EQ(ENCRYPTION_NONE, group.effective_encryption_level());
 251 }
 252
 253 // Test the code assuming it is going to be operating in 128-bit chunks (which
 254 // is something that can happen if it is compiled with full vectorization).
 255 const QuicByteCount kWordSize = 128 / 8;
 256
 257 // A buffer which stores the data with the specified offset with respect to word
 258 // alignment boundary.
 259 class MisalignedBuffer {
 260  public:
 261   MisalignedBuffer(const string& original, size_t offset);
 262
 263   char* buffer() { return buffer_; }
 264   size_t size() { return size_; }
 265
 266   StringPiece AsStringPiece() { return StringPiece(buffer_, size_); }
 267
 268  private:
 269   char* buffer_;
 270   size_t size_;
 271
 272   scoped_ptr<char[]> allocation_;
 273 };
 274
 275 MisalignedBuffer::MisalignedBuffer(const string& original, size_t offset) {
 276   CHECK_LT(offset, kWordSize);
 277   size_ = original.size();
 278
 279   // Allocate aligned buffer two words larger than needed.
 280   const size_t aligned_buffer_size = size_ + 2 * kWordSize;
 281   allocation_.reset(new char[aligned_buffer_size]);
 282   char* aligned_buffer =
 283       allocation_.get() +
 284       (kWordSize - reinterpret_cast<uintptr_t>(allocation_.get()) % kWordSize);
 285   CHECK_EQ(0u, reinterpret_cast<uintptr_t>(aligned_buffer) % kWordSize);
 286
 287   buffer_ = aligned_buffer + offset;
 288   CHECK_EQ(offset, reinterpret_cast<uintptr_t>(buffer_) % kWordSize);
 289   memcpy(buffer_, original.data(), size_);
 290 }
 291
 292 // Checks whether XorBuffers works correctly with buffers aligned in various
 293 // ways.
 294 TEST(XorBuffersTest, XorBuffers) {
 295   const string longer_data =
 296       "Having to care about memory alignment can be incredibly frustrating.";
 297   const string shorter_data = "strict aliasing";
 298
 299   // Compute the reference XOR using simpler slow way.
 300   string output_reference;
 301   for (size_t i = 0; i < longer_data.size(); i++) {
 302     char shorter_byte = i < shorter_data.size() ? shorter_data[i] : 0;
 303     output_reference.push_back(longer_data[i] ^ shorter_byte);
 304   }
 305
 306   // Check whether XorBuffers works correctly for all possible misalignments.
 307   for (size_t offset_shorter = 0; offset_shorter < kWordSize;
 308        offset_shorter++) {
 309     for (size_t offset_longer = 0; offset_longer < kWordSize; offset_longer++) {
 310       // Prepare the misaligned buffer.
 311       MisalignedBuffer longer(longer_data, offset_longer);
 312       MisalignedBuffer shorter(shorter_data, offset_shorter);
 313
 314       // XOR the buffers and compare the result with the reference.
 315       QuicFecGroup::XorBuffers(shorter.buffer(), shorter.size(),
 316                                longer.buffer());
 317       EXPECT_EQ(output_reference, longer.AsStringPiece());
 318     }
 319   }
 320 }
 321
 322 }  // namespace net