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