net/spdy/hpack_header_table_test.cc

   1 // Copyright 2014 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/spdy/hpack_header_table.h"
   6
   7 #include <algorithm>
   8 #include <set>
   9 #include <string>
  10 #include <vector>
  11
  12 #include "base/basictypes.h"
  13 #include "base/macros.h"
  14 #include "net/spdy/hpack_entry.h"
  15 #include "testing/gtest/include/gtest/gtest.h"
  16
  17 namespace net {
  18
  19 namespace {
  20
  21 using std::string;
  22
  23 typedef std::vector<HpackEntry> HpackEntryVector;
  24
  25 // Returns an entry whose Size() is equal to the given one.
  26 HpackEntry MakeEntryOfSize(uint32 size) {
  27   EXPECT_GE(size, HpackEntry::kSizeOverhead);
  28   string name((size - HpackEntry::kSizeOverhead) / 2, 'n');
  29   string value(size - HpackEntry::kSizeOverhead - name.size(), 'v');
  30   HpackEntry entry(name, value);
  31   EXPECT_EQ(size, entry.Size());
  32   return entry;
  33 }
  34
  35 // Returns a vector of entries whose total size is equal to the given
  36 // one.
  37 HpackEntryVector MakeEntriesOfTotalSize(uint32 total_size) {
  38   EXPECT_GE(total_size, HpackEntry::kSizeOverhead);
  39   uint32 entry_size = HpackEntry::kSizeOverhead;
  40   uint32 remaining_size = total_size;
  41   HpackEntryVector entries;
  42   while (remaining_size > 0) {
  43     EXPECT_LE(entry_size, remaining_size);
  44     entries.push_back(MakeEntryOfSize(entry_size));
  45     remaining_size -= entry_size;
  46     entry_size = std::min(remaining_size, entry_size + 32);
  47   }
  48   return entries;
  49 }
  50
  51 // Adds the given vector of entries to the given header table,
  52 // expecting no eviction to happen.
  53 void AddEntriesExpectNoEviction(const HpackEntryVector& entries,
  54                                 HpackHeaderTable* header_table) {
  55   unsigned start_entry_count = header_table->GetEntryCount();
  56   for (HpackEntryVector::const_iterator it = entries.begin();
  57        it != entries.end(); ++it) {
  58     uint32 index = 0;
  59     std::vector<uint32> removed_referenced_indices;
  60     header_table->TryAddEntry(*it, &index, &removed_referenced_indices);
  61     EXPECT_EQ(1u, index);
  62     EXPECT_TRUE(removed_referenced_indices.empty());
  63     EXPECT_EQ(start_entry_count + (it - entries.begin()) + 1u,
  64               header_table->GetEntryCount());
  65   }
  66
  67   for (HpackEntryVector::const_iterator it = entries.begin();
  68        it != entries.end(); ++it) {
  69     uint32 index = header_table->GetEntryCount() - (it - entries.begin());
  70     HpackEntry entry = header_table->GetEntry(index);
  71     EXPECT_TRUE(it->Equals(entry))
  72         << "it = " << it->GetDebugString() << " != entry = "
  73         << entry.GetDebugString();
  74   }
  75 }
  76
  77 // Returns the set of all indices in header_table that are in that
  78 // table's reference set.
  79 std::set<uint32> GetReferenceSet(const HpackHeaderTable& header_table) {
  80   std::set<uint32> reference_set;
  81   for (uint32 i = 1; i <= header_table.GetEntryCount(); ++i) {
  82     if (header_table.GetEntry(i).IsReferenced()) {
  83       reference_set.insert(i);
  84     }
  85   }
  86   return reference_set;
  87 }
  88
  89 // Fill a header table with entries. Make sure the entries are in
  90 // reverse order in the header table.
  91 TEST(HpackHeaderTableTest, TryAddEntryBasic) {
  92   HpackHeaderTable header_table;
  93   EXPECT_EQ(0u, header_table.size());
  94
  95   HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size());
  96
  97   // Most of the checks are in AddEntriesExpectNoEviction().
  98   AddEntriesExpectNoEviction(entries, &header_table);
  99   EXPECT_EQ(header_table.max_size(), header_table.size());
 100 }
 101
 102 // Fill a header table with entries, and then ramp the table's max
 103 // size down to evict an entry one at a time. Make sure the eviction
 104 // happens as expected.
 105 TEST(HpackHeaderTableTest, SetMaxSize) {
 106   HpackHeaderTable header_table;
 107
 108   HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size());
 109   AddEntriesExpectNoEviction(entries, &header_table);
 110
 111   for (HpackEntryVector::const_iterator it = entries.begin();
 112        it != entries.end(); ++it) {
 113     uint32 expected_count = entries.end() - it;
 114     EXPECT_EQ(expected_count, header_table.GetEntryCount());
 115
 116     header_table.SetMaxSize(header_table.size() + 1);
 117     EXPECT_EQ(expected_count, header_table.GetEntryCount());
 118
 119     header_table.SetMaxSize(header_table.size());
 120     EXPECT_EQ(expected_count, header_table.GetEntryCount());
 121
 122     --expected_count;
 123     header_table.SetMaxSize(header_table.size() - 1);
 124     EXPECT_EQ(expected_count, header_table.GetEntryCount());
 125   }
 126
 127   EXPECT_EQ(0u, header_table.size());
 128 }
 129
 130 // Setting the max size of a header table to zero should clear its
 131 // reference set.
 132 TEST(HpackHeaderTableTest, SetMaxSizeZeroClearsReferenceSet) {
 133   HpackHeaderTable header_table;
 134
 135   HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size());
 136   AddEntriesExpectNoEviction(entries, &header_table);
 137
 138   std::set<uint32> expected_reference_set;
 139   for (uint32 i = 1; i <= header_table.GetEntryCount(); ++i) {
 140     header_table.GetMutableEntry(i)->SetReferenced(true);
 141     expected_reference_set.insert(i);
 142   }
 143   EXPECT_EQ(expected_reference_set, GetReferenceSet(header_table));
 144
 145   header_table.SetMaxSize(0);
 146   EXPECT_TRUE(GetReferenceSet(header_table).empty());
 147 }
 148
 149 // Fill a header table with entries, and then add an entry just big
 150 // enough to cause eviction of all but one entry. Make sure the
 151 // eviction happens as expected and the long entry is inserted into
 152 // the table.
 153 TEST(HpackHeaderTableTest, TryAddEntryEviction) {
 154   HpackHeaderTable header_table;
 155
 156   HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size());
 157   AddEntriesExpectNoEviction(entries, &header_table);
 158
 159   EXPECT_EQ(entries.size(), header_table.GetEntryCount());
 160   HpackEntry first_entry = header_table.GetEntry(1);
 161   HpackEntry long_entry =
 162       MakeEntryOfSize(header_table.size() - first_entry.Size());
 163
 164   header_table.SetMaxSize(header_table.size());
 165   EXPECT_EQ(entries.size(), header_table.GetEntryCount());
 166
 167   std::set<uint32> expected_reference_set;
 168   for (uint32 i = 2; i <= header_table.GetEntryCount(); ++i) {
 169     header_table.GetMutableEntry(i)->SetReferenced(true);
 170     expected_reference_set.insert(i);
 171   }
 172   EXPECT_EQ(expected_reference_set, GetReferenceSet(header_table));
 173
 174   uint32 index = 0;
 175   std::vector<uint32> removed_referenced_indices;
 176   header_table.TryAddEntry(long_entry, &index, &removed_referenced_indices);
 177
 178   EXPECT_EQ(1u, index);
 179   EXPECT_EQ(expected_reference_set,
 180             std::set<uint32>(removed_referenced_indices.begin(),
 181                              removed_referenced_indices.end()));
 182   EXPECT_TRUE(GetReferenceSet(header_table).empty());
 183   EXPECT_EQ(2u, header_table.GetEntryCount());
 184   EXPECT_TRUE(header_table.GetEntry(1).Equals(long_entry));
 185   EXPECT_TRUE(header_table.GetEntry(2).Equals(first_entry));
 186 }
 187
 188 // Fill a header table with entries, and then add an entry bigger than
 189 // the entire table. Make sure no entry remains in the table.
 190 TEST(HpackHeaderTableTest, TryAddTooLargeEntry) {
 191   HpackHeaderTable header_table;
 192
 193   HpackEntryVector entries = MakeEntriesOfTotalSize(header_table.max_size());
 194   AddEntriesExpectNoEviction(entries, &header_table);
 195
 196   header_table.SetMaxSize(header_table.size());
 197   EXPECT_EQ(entries.size(), header_table.GetEntryCount());
 198
 199   std::set<uint32> expected_removed_referenced_indices;
 200   for (uint32 i = 1; i <= header_table.GetEntryCount(); ++i) {
 201     header_table.GetMutableEntry(i)->SetReferenced(true);
 202     expected_removed_referenced_indices.insert(i);
 203   }
 204
 205   HpackEntry long_entry = MakeEntryOfSize(header_table.size() + 1);
 206   uint32 index = 0;
 207   std::vector<uint32> removed_referenced_indices;
 208   header_table.TryAddEntry(long_entry, &index, &removed_referenced_indices);
 209
 210   EXPECT_EQ(0u, index);
 211   EXPECT_EQ(expected_removed_referenced_indices,
 212             std::set<uint32>(removed_referenced_indices.begin(),
 213                              removed_referenced_indices.end()));
 214   EXPECT_EQ(0u, header_table.GetEntryCount());
 215 }
 216
 217 }  // namespace
 218
 219 }  // namespace net