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
18namespace net {
19
20using base::StringPiece;
21using std::distance;
22using std::string;
23
24namespace test {
25
26class 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
76namespace {
77
78class 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
143TEST_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
163TEST_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
201TEST_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
267TEST_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
301TEST_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
318TEST_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.
331TEST_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.
346TEST_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.
373TEST_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.
395TEST_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
411TEST_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
420TEST_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
429TEST_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
439TEST_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
451