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_constants.h"
  15 #include "net/spdy/hpack_entry.h"
  16 #include "testing/gtest/include/gtest/gtest.h"
  17
  18 namespace net {
  19
  20 using base::StringPiece;
  21 using std::distance;
  22 using std::string;
  23
  24 namespace test {
  25
  26 class HpackHeaderTablePeer {
  27  public:
  28   explicit HpackHeaderTablePeer(HpackHeaderTable* table)
  29       : table_(table) {}
  30
  31   const HpackHeaderTable::EntryTable& dynamic_entries() {
  32     return table_->dynamic_entries_;
  33   }
  34   const HpackHeaderTable::EntryTable& static_entries() {
  35     return table_->static_entries_;
  36   }
  37   size_t index_size() {
  38     return table_->static_index_.size() + table_->dynamic_index_.size();
  39   }
  40   std::vector<HpackEntry*> EvictionSet(StringPiece name, StringPiece value) {
  41     HpackHeaderTable::EntryTable::iterator begin, end;
  42     table_->EvictionSet(name, value, &begin, &end);
  43     std::vector<HpackEntry*> result;
  44     for (; begin != end; ++begin) {
  45       result.push_back(&(*begin));
  46     }
  47     return result;
  48   }
  49   size_t total_insertions() {
  50     return table_->total_insertions_;
  51   }
  52   size_t dynamic_entries_count() {
  53     return table_->dynamic_entries_.size();
  54   }
  55   size_t EvictionCountForEntry(StringPiece name, StringPiece value) {
  56     return table_->EvictionCountForEntry(name, value);
  57   }
  58   size_t EvictionCountToReclaim(size_t reclaim_size) {
  59     return table_->EvictionCountToReclaim(reclaim_size);
  60   }
  61   void Evict(size_t count) {
  62     return table_->Evict(count);
  63   }
  64
  65   void AddDynamicEntry(StringPiece name, StringPiece value) {
  66     table_->dynamic_entries_.push_back(
  67         HpackEntry(name, value, false, table_->total_insertions_++));
  68   }
  69
  70  private:
  71   HpackHeaderTable* table_;
  72 };
  73
  74 }  // namespace test
  75
  76 namespace {
  77
  78 class HpackHeaderTableTest : public ::testing::Test {
  79  protected:
  80   typedef std::vector<HpackEntry> HpackEntryVector;
  81
  82   HpackHeaderTableTest() : table_(), peer_(&table_) {}
  83
  84   // Returns an entry whose Size() is equal to the given one.
  85   static HpackEntry MakeEntryOfSize(uint32 size) {
  86     EXPECT_GE(size, HpackEntry::kSizeOverhead);
  87     string name((size - HpackEntry::kSizeOverhead) / 2, 'n');
  88     string value(size - HpackEntry::kSizeOverhead - name.size(), 'v');
  89     HpackEntry entry(name, value);
  90     EXPECT_EQ(size, entry.Size());
  91     return entry;
  92   }
  93
  94   // Returns a vector of entries whose total size is equal to the given
  95   // one.
  96   static HpackEntryVector MakeEntriesOfTotalSize(uint32 total_size) {
  97     EXPECT_GE(total_size, HpackEntry::kSizeOverhead);
  98     uint32 entry_size = HpackEntry::kSizeOverhead;
  99     uint32 remaining_size = total_size;
 100     HpackEntryVector entries;
 101     while (remaining_size > 0) {
 102       EXPECT_LE(entry_size, remaining_size);
 103       entries.push_back(MakeEntryOfSize(entry_size));
 104       remaining_size -= entry_size;
 105       entry_size = std::min(remaining_size, entry_size + 32);
 106     }
 107     return entries;
 108   }
 109
 110   // Adds the given vector of entries to the given header table,
 111   // expecting no eviction to happen.
 112   void AddEntriesExpectNoEviction(const HpackEntryVector& entries) {
 113     for (HpackEntryVector::const_iterator it = entries.begin();
 114          it != entries.end(); ++it) {
 115       HpackHeaderTable::EntryTable::iterator begin, end;
 116
 117       table_.EvictionSet(it->name(), it->value(), &begin, &end);
 118       EXPECT_EQ(0, distance(begin, end));
 119
 120       const HpackEntry* entry = table_.TryAddEntry(it->name(), it->value());
 121       EXPECT_NE(entry, static_cast<HpackEntry*>(NULL));
 122     }
 123
 124     for (size_t i = 0; i != entries.size(); ++i) {
 125       // Static table has 61 entries, dynamic entries follow those.
 126       size_t index = 61 + entries.size() - i;
 127       const HpackEntry* entry = table_.GetByIndex(index);
 128       EXPECT_EQ(entries[i].name(), entry->name());
 129       EXPECT_EQ(entries[i].value(), entry->value());
 130       EXPECT_EQ(index, table_.IndexOf(entry));
 131     }
 132   }
 133
 134   HpackEntry DynamicEntry(string name, string value) {
 135     peer_.AddDynamicEntry(name, value);
 136     return peer_.dynamic_entries().back();
 137   }
 138
 139   HpackHeaderTable table_;
 140   test::HpackHeaderTablePeer peer_;
 141 };
 142
 143 TEST_F(HpackHeaderTableTest, StaticTableInitialization) {
 144   EXPECT_EQ(0u, table_.size());
 145   EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.max_size());
 146   EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound());
 147
 148   EXPECT_EQ(0u, peer_.dynamic_entries_count());
 149   EXPECT_EQ(peer_.static_entries().size(), peer_.total_insertions());
 150
 151   // Static entries have been populated and inserted into the table & index.
 152   EXPECT_NE(0u, peer_.static_entries().size());
 153   EXPECT_EQ(peer_.index_size(), peer_.static_entries().size());
 154   for (size_t i = 0; i != peer_.static_entries().size(); ++i) {
 155     const HpackEntry* entry = &peer_.static_entries()[i];
 156
 157     EXPECT_TRUE(entry->IsStatic());
 158     EXPECT_EQ(entry, table_.GetByIndex(i + 1));
 159     EXPECT_EQ(entry, table_.GetByNameAndValue(entry->name(), entry->value()));
 160   }
 161 }
 162
 163 TEST_F(HpackHeaderTableTest, BasicDynamicEntryInsertionAndEviction) {
 164   size_t static_count = peer_.total_insertions();
 165   const HpackEntry* first_static_entry = table_.GetByIndex(1);
 166
 167   EXPECT_EQ(1u, table_.IndexOf(first_static_entry));
 168
 169   const HpackEntry* entry = table_.TryAddEntry("header-key", "Header Value");
 170   EXPECT_EQ("header-key", entry->name());
 171   EXPECT_EQ("Header Value", entry->value());
 172   EXPECT_FALSE(entry->IsStatic());
 173
 174   // Table counts were updated appropriately.
 175   EXPECT_EQ(entry->Size(), table_.size());
 176   EXPECT_EQ(1u, peer_.dynamic_entries_count());
 177   EXPECT_EQ(peer_.dynamic_entries().size(), peer_.dynamic_entries_count());
 178   EXPECT_EQ(static_count + 1, peer_.total_insertions());
 179   EXPECT_EQ(static_count + 1, peer_.index_size());
 180
 181   // Index() of entries reflects the insertion.
 182   EXPECT_EQ(1u, table_.IndexOf(first_static_entry));
 183   // Static table has 61 entries.
 184   EXPECT_EQ(62u, table_.IndexOf(entry));
 185   EXPECT_EQ(first_static_entry, table_.GetByIndex(1));
 186   EXPECT_EQ(entry, table_.GetByIndex(62));
 187
 188   // Evict |entry|. Table counts are again updated appropriately.
 189   peer_.Evict(1);
 190   EXPECT_EQ(0u, table_.size());
 191   EXPECT_EQ(0u, peer_.dynamic_entries_count());
 192   EXPECT_EQ(peer_.dynamic_entries().size(), peer_.dynamic_entries_count());
 193   EXPECT_EQ(static_count + 1, peer_.total_insertions());
 194   EXPECT_EQ(static_count, peer_.index_size());
 195
 196   // Index() of |first_static_entry| reflects the eviction.
 197   EXPECT_EQ(1u, table_.IndexOf(first_static_entry));
 198   EXPECT_EQ(first_static_entry, table_.GetByIndex(1));
 199 }
 200
 201 TEST_F(HpackHeaderTableTest, EntryIndexing) {
 202   const HpackEntry* first_static_entry = table_.GetByIndex(1);
 203
 204   // Static entries are queryable by name & value.
 205   EXPECT_EQ(first_static_entry, table_.GetByName(first_static_entry->name()));
 206   EXPECT_EQ(first_static_entry, table_.GetByNameAndValue(
 207         first_static_entry->name(), first_static_entry->value()));
 208
 209   // Create a mix of entries which duplicate names, and names & values of both
 210   // dynamic and static entries.
 211   const HpackEntry* entry1 = table_.TryAddEntry(first_static_entry->name(),
 212                                                 first_static_entry->value());
 213   const HpackEntry* entry2 =
 214       table_.TryAddEntry(first_static_entry->name(), "Value Four");
 215   const HpackEntry* entry3 = table_.TryAddEntry("key-1", "Value One");
 216   const HpackEntry* entry4 = table_.TryAddEntry("key-2", "Value Three");
 217   const HpackEntry* entry5 = table_.TryAddEntry("key-1", "Value Two");
 218   const HpackEntry* entry6 = table_.TryAddEntry("key-2", "Value Three");
 219   const HpackEntry* entry7 = table_.TryAddEntry("key-2", "Value Four");
 220
 221   // Entries are queryable under their current index.
 222   EXPECT_EQ(entry7, table_.GetByIndex(62));
 223   EXPECT_EQ(entry6, table_.GetByIndex(63));
 224   EXPECT_EQ(entry5, table_.GetByIndex(64));
 225   EXPECT_EQ(entry4, table_.GetByIndex(65));
 226   EXPECT_EQ(entry3, table_.GetByIndex(66));
 227   EXPECT_EQ(entry2, table_.GetByIndex(67));
 228   EXPECT_EQ(entry1, table_.GetByIndex(68));
 229   EXPECT_EQ(first_static_entry, table_.GetByIndex(1));
 230
 231   // Querying by name returns the lowest-value matching entry.
 232   EXPECT_EQ(entry3, table_.GetByName("key-1"));
 233   EXPECT_EQ(entry7, table_.GetByName("key-2"));
 234   EXPECT_EQ(entry2->name(),
 235             table_.GetByName(first_static_entry->name())->name());
 236   EXPECT_EQ(NULL, table_.GetByName("not-present"));
 237
 238   // Querying by name & value returns the lowest-index matching entry among
 239   // static entries, and the highest-index one among dynamic entries.
 240   EXPECT_EQ(entry3, table_.GetByNameAndValue("key-1", "Value One"));
 241   EXPECT_EQ(entry5, table_.GetByNameAndValue("key-1", "Value Two"));
 242   EXPECT_EQ(entry4, table_.GetByNameAndValue("key-2", "Value Three"));
 243   EXPECT_EQ(entry7, table_.GetByNameAndValue("key-2", "Value Four"));
 244   EXPECT_EQ(first_static_entry,
 245             table_.GetByNameAndValue(first_static_entry->name(),
 246                                      first_static_entry->value()));
 247   EXPECT_EQ(entry2, table_.GetByNameAndValue(first_static_entry->name(),
 248                                              "Value Four"));
 249   EXPECT_EQ(NULL, table_.GetByNameAndValue("key-1", "Not Present"));
 250   EXPECT_EQ(NULL, table_.GetByNameAndValue("not-present", "Value One"));
 251
 252   // Evict |entry1|. Queries for its name & value now return the static entry.
 253   // |entry2| remains queryable.
 254   peer_.Evict(1);
 255   EXPECT_EQ(first_static_entry,
 256       table_.GetByNameAndValue(first_static_entry->name(),
 257                                first_static_entry->value()));
 258   EXPECT_EQ(entry2, table_.GetByNameAndValue(first_static_entry->name(),
 259                                              "Value Four"));
 260
 261   // Evict |entry2|. Queries by its name & value are not found.
 262   peer_.Evict(1);
 263   EXPECT_EQ(NULL, table_.GetByNameAndValue(first_static_entry->name(),
 264                                            "Value Four"));
 265 }
 266
 267 TEST_F(HpackHeaderTableTest, SetSizes) {
 268   string key = "key", value = "value";
 269   const HpackEntry* entry1 = table_.TryAddEntry(key, value);
 270   const HpackEntry* entry2 = table_.TryAddEntry(key, value);
 271   const HpackEntry* entry3 = table_.TryAddEntry(key, value);
 272
 273   // Set exactly large enough. No Evictions.
 274   size_t max_size = entry1->Size() + entry2->Size() + entry3->Size();
 275   table_.SetMaxSize(max_size);
 276   EXPECT_EQ(3u, peer_.dynamic_entries().size());
 277
 278   // Set just too small. One eviction.
 279   max_size = entry1->Size() + entry2->Size() + entry3->Size() - 1;
 280   table_.SetMaxSize(max_size);
 281   EXPECT_EQ(2u, peer_.dynamic_entries().size());
 282
 283   // Changing SETTINGS_HEADER_TABLE_SIZE doesn't affect table_.max_size(),
 284   // iff SETTINGS_HEADER_TABLE_SIZE >= |max_size|.
 285   EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound());
 286   table_.SetSettingsHeaderTableSize(kDefaultHeaderTableSizeSetting*2);
 287   EXPECT_EQ(max_size, table_.max_size());
 288   table_.SetSettingsHeaderTableSize(max_size + 1);
 289   EXPECT_EQ(max_size, table_.max_size());
 290   EXPECT_EQ(2u, peer_.dynamic_entries().size());
 291
 292   // SETTINGS_HEADER_TABLE_SIZE upper-bounds |table_.max_size()|,
 293   // and will force evictions.
 294   max_size = entry3->Size() - 1;
 295   table_.SetSettingsHeaderTableSize(max_size);
 296   EXPECT_EQ(max_size, table_.max_size());
 297   EXPECT_EQ(max_size, table_.settings_size_bound());
 298   EXPECT_EQ(0u, peer_.dynamic_entries().size());
 299 }
 300
 301 TEST_F(HpackHeaderTableTest, EvictionCountForEntry) {
 302   string key = "key", value = "value";
 303   const HpackEntry* entry1 = table_.TryAddEntry(key, value);
 304   const HpackEntry* entry2 = table_.TryAddEntry(key, value);
 305   size_t entry3_size = HpackEntry::Size(key, value);
 306
 307   // Just enough capacity for third entry.
 308   table_.SetMaxSize(entry1->Size() + entry2->Size() + entry3_size);
 309   EXPECT_EQ(0u, peer_.EvictionCountForEntry(key, value));
 310   EXPECT_EQ(1u, peer_.EvictionCountForEntry(key, value + "x"));
 311
 312   // No extra capacity. Third entry would force evictions.
 313   table_.SetMaxSize(entry1->Size() + entry2->Size());
 314   EXPECT_EQ(1u, peer_.EvictionCountForEntry(key, value));
 315   EXPECT_EQ(2u, peer_.EvictionCountForEntry(key, value + "x"));
 316 }
 317
 318 TEST_F(HpackHeaderTableTest, EvictionCountToReclaim) {
 319   string key = "key", value = "value";
 320   const HpackEntry* entry1 = table_.TryAddEntry(key, value);
 321   const HpackEntry* entry2 = table_.TryAddEntry(key, value);
 322
 323   EXPECT_EQ(1u, peer_.EvictionCountToReclaim(1));
 324   EXPECT_EQ(1u, peer_.EvictionCountToReclaim(entry1->Size()));
 325   EXPECT_EQ(2u, peer_.EvictionCountToReclaim(entry1->Size() + 1));
 326   EXPECT_EQ(2u, peer_.EvictionCountToReclaim(entry1->Size() + entry2->Size()));
 327 }
 328
 329 // Fill a header table with entries. Make sure the entries are in
 330 // reverse order in the header table.
 331 TEST_F(HpackHeaderTableTest, TryAddEntryBasic) {
 332   EXPECT_EQ(0u, table_.size());
 333   EXPECT_EQ(table_.settings_size_bound(), table_.max_size());
 334
 335   HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size());
 336
 337   // Most of the checks are in AddEntriesExpectNoEviction().
 338   AddEntriesExpectNoEviction(entries);
 339   EXPECT_EQ(table_.max_size(), table_.size());
 340   EXPECT_EQ(table_.settings_size_bound(), table_.size());
 341 }
 342
 343 // Fill a header table with entries, and then ramp the table's max
 344 // size down to evict an entry one at a time. Make sure the eviction
 345 // happens as expected.
 346 TEST_F(HpackHeaderTableTest, SetMaxSize) {
 347   HpackEntryVector entries = MakeEntriesOfTotalSize(
 348       kDefaultHeaderTableSizeSetting / 2);
 349   AddEntriesExpectNoEviction(entries);
 350
 351   for (HpackEntryVector::iterator it = entries.begin();
 352        it != entries.end(); ++it) {
 353     size_t expected_count = distance(it, entries.end());
 354     EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
 355
 356     table_.SetMaxSize(table_.size() + 1);
 357     EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
 358
 359     table_.SetMaxSize(table_.size());
 360     EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
 361
 362     --expected_count;
 363     table_.SetMaxSize(table_.size() - 1);
 364     EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
 365   }
 366   EXPECT_EQ(0u, table_.size());
 367 }
 368
 369 // Fill a header table with entries, and then add an entry just big
 370 // enough to cause eviction of all but one entry. Make sure the
 371 // eviction happens as expected and the long entry is inserted into
 372 // the table.
 373 TEST_F(HpackHeaderTableTest, TryAddEntryEviction) {
 374   HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size());
 375   AddEntriesExpectNoEviction(entries);
 376
 377   const HpackEntry* survivor_entry = table_.GetByIndex(61 + 1);
 378   HpackEntry long_entry =
 379       MakeEntryOfSize(table_.max_size() - survivor_entry->Size());
 380
 381   // All dynamic entries but the first are to be evicted.
 382   EXPECT_EQ(peer_.dynamic_entries().size() - 1, peer_.EvictionSet(
 383       long_entry.name(), long_entry.value()).size());
 384
 385   const HpackEntry* new_entry =
 386       table_.TryAddEntry(long_entry.name(), long_entry.value());
 387   EXPECT_EQ(62u, table_.IndexOf(new_entry));
 388   EXPECT_EQ(2u, peer_.dynamic_entries().size());
 389   EXPECT_EQ(table_.GetByIndex(63), survivor_entry);
 390   EXPECT_EQ(table_.GetByIndex(62), new_entry);
 391 }
 392
 393 // Fill a header table with entries, and then add an entry bigger than
 394 // the entire table. Make sure no entry remains in the table.
 395 TEST_F(HpackHeaderTableTest, TryAddTooLargeEntry) {
 396   HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size());
 397   AddEntriesExpectNoEviction(entries);
 398
 399   const HpackEntry long_entry = MakeEntryOfSize(table_.max_size() + 1);
 400
 401   // All entries are to be evicted.
 402   EXPECT_EQ(peer_.dynamic_entries().size(), peer_.EvictionSet(
 403       long_entry.name(), long_entry.value()).size());
 404
 405   const HpackEntry* new_entry =
 406       table_.TryAddEntry(long_entry.name(), long_entry.value());
 407   EXPECT_EQ(new_entry, static_cast<HpackEntry*>(NULL));
 408   EXPECT_EQ(0u, peer_.dynamic_entries().size());
 409 }
 410
 411 TEST_F(HpackHeaderTableTest, ComparatorNameOrdering) {
 412   HpackEntry entry1("header", "value");
 413   HpackEntry entry2("HEADER", "value");
 414
 415   HpackHeaderTable::EntryComparator comparator;
 416   EXPECT_FALSE(comparator(&entry1, &entry2));
 417   EXPECT_TRUE(comparator(&entry2, &entry1));
 418 }
 419
 420 TEST_F(HpackHeaderTableTest, ComparatorValueOrdering) {
 421   HpackEntry entry1("header", "value");
 422   HpackEntry entry2("header", "VALUE");
 423
 424   HpackHeaderTable::EntryComparator comparator;
 425   EXPECT_FALSE(comparator(&entry1, &entry2));
 426   EXPECT_TRUE(comparator(&entry2, &entry1));
 427 }
 428
 429 TEST_F(HpackHeaderTableTest, ComparatorIndexOrdering) {
 430   HpackHeaderTable::EntryComparator comparator;
 431   HpackEntry entry1(DynamicEntry("name", "value"));
 432   HpackEntry entry2(DynamicEntry("name", "value"));
 433
 434   // |entry1| has lower insertion index than |entry2|.
 435   EXPECT_TRUE(comparator(&entry1, &entry2));
 436   EXPECT_FALSE(comparator(&entry2, &entry1));
 437 }
 438
 439 TEST_F(HpackHeaderTableTest, ComparatorEqualityOrdering) {
 440   HpackEntry entry1("name", "value");
 441   HpackEntry entry2(DynamicEntry("name", "value"));
 442
 443   HpackHeaderTable::EntryComparator comparator;
 444   EXPECT_FALSE(comparator(&entry1, &entry1));
 445   EXPECT_FALSE(comparator(&entry2, &entry2));
 446 }
 447
 448 }  // namespace
 449
 450 }  // namespace net