Add diagnostics_writer.cc to the list of files allowed to printf.
[chromium-blink-merge.git] / net / spdy / hpack_header_table_test.cc
blob14c2c184e2b631cd80c4d6a0f70967a89ccc806d
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.
5 #include "net/spdy/hpack_header_table.h"
7 #include <algorithm>
8 #include <set>
9 #include <string>
10 #include <vector>
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"
18 namespace net {
20 using base::StringPiece;
21 using std::distance;
22 using std::string;
24 namespace test {
26 class HpackHeaderTablePeer {
27 public:
28 explicit HpackHeaderTablePeer(HpackHeaderTable* table)
29 : table_(table) {}
31 const HpackHeaderTable::EntryTable& dynamic_entries() {
32 return table_->dynamic_entries_;
34 const HpackHeaderTable::EntryTable& static_entries() {
35 return table_->static_entries_;
37 const HpackHeaderTable::OrderedEntrySet& index() {
38 return table_->index_;
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));
47 return result;
49 size_t total_insertions() {
50 return table_->total_insertions_;
52 size_t dynamic_entries_count() {
53 return table_->dynamic_entries_.size();
55 size_t EvictionCountForEntry(StringPiece name, StringPiece value) {
56 return table_->EvictionCountForEntry(name, value);
58 size_t EvictionCountToReclaim(size_t reclaim_size) {
59 return table_->EvictionCountToReclaim(reclaim_size);
61 void Evict(size_t count) {
62 return table_->Evict(count);
65 void AddStaticEntry(StringPiece name, StringPiece value) {
66 table_->static_entries_.push_back(
67 HpackEntry(name, value, true, table_->total_insertions_++));
70 void AddDynamicEntry(StringPiece name, StringPiece value) {
71 table_->dynamic_entries_.push_back(
72 HpackEntry(name, value, false, table_->total_insertions_++));
75 private:
76 HpackHeaderTable* table_;
79 } // namespace test
81 namespace {
83 class HpackHeaderTableTest : public ::testing::Test {
84 protected:
85 typedef std::vector<HpackEntry> HpackEntryVector;
87 HpackHeaderTableTest()
88 : table_(),
89 peer_(&table_),
90 name_("header-name"),
91 value_("header value") {}
93 // Returns an entry whose Size() is equal to the given one.
94 static HpackEntry MakeEntryOfSize(uint32 size) {
95 EXPECT_GE(size, HpackEntry::kSizeOverhead);
96 string name((size - HpackEntry::kSizeOverhead) / 2, 'n');
97 string value(size - HpackEntry::kSizeOverhead - name.size(), 'v');
98 HpackEntry entry(name, value);
99 EXPECT_EQ(size, entry.Size());
100 return entry;
103 // Returns a vector of entries whose total size is equal to the given
104 // one.
105 static HpackEntryVector MakeEntriesOfTotalSize(uint32 total_size) {
106 EXPECT_GE(total_size, HpackEntry::kSizeOverhead);
107 uint32 entry_size = HpackEntry::kSizeOverhead;
108 uint32 remaining_size = total_size;
109 HpackEntryVector entries;
110 while (remaining_size > 0) {
111 EXPECT_LE(entry_size, remaining_size);
112 entries.push_back(MakeEntryOfSize(entry_size));
113 remaining_size -= entry_size;
114 entry_size = std::min(remaining_size, entry_size + 32);
116 return entries;
119 // Adds the given vector of entries to the given header table,
120 // expecting no eviction to happen.
121 void AddEntriesExpectNoEviction(const HpackEntryVector& entries) {
122 for (HpackEntryVector::const_iterator it = entries.begin();
123 it != entries.end(); ++it) {
124 HpackHeaderTable::EntryTable::iterator begin, end;
126 table_.EvictionSet(it->name(), it->value(), &begin, &end);
127 EXPECT_EQ(0, distance(begin, end));
129 HpackEntry* entry = table_.TryAddEntry(it->name(), it->value());
130 EXPECT_NE(entry, static_cast<HpackEntry*>(NULL));
133 for (size_t i = 0; i != entries.size(); ++i) {
134 size_t index = entries.size() - i;
135 HpackEntry* entry = table_.GetByIndex(index);
136 EXPECT_EQ(entries[i].name(), entry->name());
137 EXPECT_EQ(entries[i].value(), entry->value());
138 EXPECT_EQ(index, table_.IndexOf(entry));
142 HpackEntry StaticEntry() {
143 peer_.AddStaticEntry(name_, value_);
144 return peer_.static_entries().back();
146 HpackEntry DynamicEntry() {
147 peer_.AddDynamicEntry(name_, value_);
148 return peer_.dynamic_entries().back();
151 HpackHeaderTable table_;
152 test::HpackHeaderTablePeer peer_;
153 string name_, value_;
156 TEST_F(HpackHeaderTableTest, StaticTableInitialization) {
157 EXPECT_EQ(0u, table_.size());
158 EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.max_size());
159 EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound());
161 EXPECT_EQ(0u, peer_.dynamic_entries_count());
162 EXPECT_EQ(0u, table_.reference_set().size());
163 EXPECT_EQ(peer_.static_entries().size(), peer_.total_insertions());
165 // Static entries have been populated and inserted into the table & index.
166 EXPECT_NE(0u, peer_.static_entries().size());
167 EXPECT_EQ(peer_.index().size(), peer_.static_entries().size());
168 for (size_t i = 0; i != peer_.static_entries().size(); ++i) {
169 const HpackEntry* entry = &peer_.static_entries()[i];
171 EXPECT_TRUE(entry->IsStatic());
172 EXPECT_EQ(entry, table_.GetByIndex(i + 1));
173 EXPECT_EQ(entry, table_.GetByNameAndValue(entry->name(), entry->value()));
177 TEST_F(HpackHeaderTableTest, BasicDynamicEntryInsertionAndEviction) {
178 size_t static_count = peer_.total_insertions();
179 HpackEntry* first_static_entry = table_.GetByIndex(1);
181 EXPECT_EQ(1u, table_.IndexOf(first_static_entry));
183 HpackEntry* entry = table_.TryAddEntry("header-key", "Header Value");
184 EXPECT_EQ("header-key", entry->name());
185 EXPECT_EQ("Header Value", entry->value());
186 EXPECT_FALSE(entry->IsStatic());
188 // Table counts were updated appropriately.
189 EXPECT_EQ(entry->Size(), table_.size());
190 EXPECT_EQ(1u, peer_.dynamic_entries_count());
191 EXPECT_EQ(peer_.dynamic_entries().size(), peer_.dynamic_entries_count());
192 EXPECT_EQ(static_count + 1, peer_.total_insertions());
193 EXPECT_EQ(static_count + 1, peer_.index().size());
195 // Index() of entries reflects the insertion.
196 EXPECT_EQ(1u, table_.IndexOf(entry));
197 EXPECT_EQ(2u, table_.IndexOf(first_static_entry));
198 EXPECT_EQ(entry, table_.GetByIndex(1));
199 EXPECT_EQ(first_static_entry, table_.GetByIndex(2));
201 // Evict |entry|. Table counts are again updated appropriately.
202 peer_.Evict(1);
203 EXPECT_EQ(0u, table_.size());
204 EXPECT_EQ(0u, peer_.dynamic_entries_count());
205 EXPECT_EQ(peer_.dynamic_entries().size(), peer_.dynamic_entries_count());
206 EXPECT_EQ(static_count + 1, peer_.total_insertions());
207 EXPECT_EQ(static_count, peer_.index().size());
209 // Index() of |first_static_entry| reflects the eviction.
210 EXPECT_EQ(1u, table_.IndexOf(first_static_entry));
211 EXPECT_EQ(first_static_entry, table_.GetByIndex(1));
214 TEST_F(HpackHeaderTableTest, EntryIndexing) {
215 HpackEntry* first_static_entry = table_.GetByIndex(1);
217 // Static entries are queryable by name & value.
218 EXPECT_EQ(first_static_entry, table_.GetByName(first_static_entry->name()));
219 EXPECT_EQ(first_static_entry, table_.GetByNameAndValue(
220 first_static_entry->name(), first_static_entry->value()));
222 // Create a mix of entries which duplicate names, and names & values of both
223 // dynamic and static entries.
224 HpackEntry* entry1 = table_.TryAddEntry(first_static_entry->name(),
225 first_static_entry->value());
226 HpackEntry* entry2 = table_.TryAddEntry(first_static_entry->name(),
227 "Value Four");
228 HpackEntry* entry3 = table_.TryAddEntry("key-1", "Value One");
229 HpackEntry* entry4 = table_.TryAddEntry("key-2", "Value Three");
230 HpackEntry* entry5 = table_.TryAddEntry("key-1", "Value Two");
231 HpackEntry* entry6 = table_.TryAddEntry("key-2", "Value Three");
232 HpackEntry* entry7 = table_.TryAddEntry("key-2", "Value Four");
234 // Entries are queryable under their current index.
235 EXPECT_EQ(entry7, table_.GetByIndex(1));
236 EXPECT_EQ(entry6, table_.GetByIndex(2));
237 EXPECT_EQ(entry5, table_.GetByIndex(3));
238 EXPECT_EQ(entry4, table_.GetByIndex(4));
239 EXPECT_EQ(entry3, table_.GetByIndex(5));
240 EXPECT_EQ(entry2, table_.GetByIndex(6));
241 EXPECT_EQ(entry1, table_.GetByIndex(7));
242 EXPECT_EQ(first_static_entry, table_.GetByIndex(8));
244 // Querying by name returns the lowest-value matching entry.
245 EXPECT_EQ(entry3, table_.GetByName("key-1"));
246 EXPECT_EQ(entry7, table_.GetByName("key-2"));
247 EXPECT_EQ(entry2->name(),
248 table_.GetByName(first_static_entry->name())->name());
249 EXPECT_EQ(NULL, table_.GetByName("not-present"));
251 // Querying by name & value returns the lowest-index matching entry.
252 EXPECT_EQ(entry3, table_.GetByNameAndValue("key-1", "Value One"));
253 EXPECT_EQ(entry5, table_.GetByNameAndValue("key-1", "Value Two"));
254 EXPECT_EQ(entry6, table_.GetByNameAndValue("key-2", "Value Three"));
255 EXPECT_EQ(entry7, table_.GetByNameAndValue("key-2", "Value Four"));
256 EXPECT_EQ(entry1, 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 EXPECT_EQ(NULL, table_.GetByNameAndValue("key-1", "Not Present"));
261 EXPECT_EQ(NULL, table_.GetByNameAndValue("not-present", "Value One"));
263 // Evict |entry1|. Queries for its name & value now return the static entry.
264 // |entry2| remains queryable.
265 peer_.Evict(1);
266 EXPECT_EQ(first_static_entry,
267 table_.GetByNameAndValue(first_static_entry->name(),
268 first_static_entry->value()));
269 EXPECT_EQ(entry2, table_.GetByNameAndValue(first_static_entry->name(),
270 "Value Four"));
272 // Evict |entry2|. Queries by its name & value are not found.
273 peer_.Evict(1);
274 EXPECT_EQ(NULL, table_.GetByNameAndValue(first_static_entry->name(),
275 "Value Four"));
278 TEST_F(HpackHeaderTableTest, SetSizes) {
279 string key = "key", value = "value";
280 HpackEntry* entry1 = table_.TryAddEntry(key, value);
281 HpackEntry* entry2 = table_.TryAddEntry(key, value);
282 HpackEntry* entry3 = table_.TryAddEntry(key, value);
284 // Set exactly large enough. No Evictions.
285 size_t max_size = entry1->Size() + entry2->Size() + entry3->Size();
286 table_.SetMaxSize(max_size);
287 EXPECT_EQ(3u, peer_.dynamic_entries().size());
289 // Set just too small. One eviction.
290 max_size = entry1->Size() + entry2->Size() + entry3->Size() - 1;
291 table_.SetMaxSize(max_size);
292 EXPECT_EQ(2u, peer_.dynamic_entries().size());
294 // Changing SETTINGS_HEADER_TABLE_SIZE doesn't affect table_.max_size(),
295 // iff SETTINGS_HEADER_TABLE_SIZE >= |max_size|.
296 EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound());
297 table_.SetSettingsHeaderTableSize(kDefaultHeaderTableSizeSetting*2);
298 EXPECT_EQ(max_size, table_.max_size());
299 table_.SetSettingsHeaderTableSize(max_size + 1);
300 EXPECT_EQ(max_size, table_.max_size());
301 EXPECT_EQ(2u, peer_.dynamic_entries().size());
303 // SETTINGS_HEADER_TABLE_SIZE upper-bounds |table_.max_size()|,
304 // and will force evictions.
305 max_size = entry3->Size() - 1;
306 table_.SetSettingsHeaderTableSize(max_size);
307 EXPECT_EQ(max_size, table_.max_size());
308 EXPECT_EQ(max_size, table_.settings_size_bound());
309 EXPECT_EQ(0u, peer_.dynamic_entries().size());
312 TEST_F(HpackHeaderTableTest, ToggleReferenceSet) {
313 HpackEntry* entry1 = table_.TryAddEntry("key-1", "Value One");
314 HpackEntry* entry2 = table_.TryAddEntry("key-2", "Value Two");
316 // Entries must be explictly toggled after creation.
317 EXPECT_EQ(0u, table_.reference_set().size());
319 // Add |entry1|.
320 EXPECT_TRUE(table_.Toggle(entry1));
321 EXPECT_EQ(1u, table_.reference_set().size());
322 EXPECT_EQ(1u, table_.reference_set().count(entry1));
323 EXPECT_EQ(0u, table_.reference_set().count(entry2));
325 // Add |entry2|.
326 EXPECT_TRUE(table_.Toggle(entry2));
327 EXPECT_EQ(2u, table_.reference_set().size());
328 EXPECT_EQ(1u, table_.reference_set().count(entry1));
329 EXPECT_EQ(1u, table_.reference_set().count(entry2));
331 // Remove |entry2|.
332 EXPECT_FALSE(table_.Toggle(entry2));
333 EXPECT_EQ(1u, table_.reference_set().size());
334 EXPECT_EQ(0u, table_.reference_set().count(entry2));
336 // Evict |entry1|. Implicit removal from reference set.
337 peer_.Evict(1);
338 EXPECT_EQ(0u, table_.reference_set().size());
341 TEST_F(HpackHeaderTableTest, ClearReferenceSet) {
342 HpackEntry* entry1 = table_.TryAddEntry("key-1", "Value One");
343 EXPECT_TRUE(table_.Toggle(entry1));
344 entry1->set_state(123);
346 // |entry1| state is cleared, and removed from the reference set.
347 table_.ClearReferenceSet();
348 EXPECT_EQ(0u, entry1->state());
349 EXPECT_EQ(0u, table_.reference_set().size());
352 TEST_F(HpackHeaderTableTest, EvictionCountForEntry) {
353 string key = "key", value = "value";
354 HpackEntry* entry1 = table_.TryAddEntry(key, value);
355 HpackEntry* entry2 = table_.TryAddEntry(key, value);
356 size_t entry3_size = HpackEntry::Size(key, value);
358 // Just enough capacity for third entry.
359 table_.SetMaxSize(entry1->Size() + entry2->Size() + entry3_size);
360 EXPECT_EQ(0u, peer_.EvictionCountForEntry(key, value));
361 EXPECT_EQ(1u, peer_.EvictionCountForEntry(key, value + "x"));
363 // No extra capacity. Third entry would force evictions.
364 table_.SetMaxSize(entry1->Size() + entry2->Size());
365 EXPECT_EQ(1u, peer_.EvictionCountForEntry(key, value));
366 EXPECT_EQ(2u, peer_.EvictionCountForEntry(key, value + "x"));
369 TEST_F(HpackHeaderTableTest, EvictionCountToReclaim) {
370 string key = "key", value = "value";
371 HpackEntry* entry1 = table_.TryAddEntry(key, value);
372 HpackEntry* entry2 = table_.TryAddEntry(key, value);
374 EXPECT_EQ(1u, peer_.EvictionCountToReclaim(1));
375 EXPECT_EQ(1u, peer_.EvictionCountToReclaim(entry1->Size()));
376 EXPECT_EQ(2u, peer_.EvictionCountToReclaim(entry1->Size() + 1));
377 EXPECT_EQ(2u, peer_.EvictionCountToReclaim(entry1->Size() + entry2->Size()));
380 // Fill a header table with entries. Make sure the entries are in
381 // reverse order in the header table.
382 TEST_F(HpackHeaderTableTest, TryAddEntryBasic) {
383 EXPECT_EQ(0u, table_.size());
384 EXPECT_EQ(table_.settings_size_bound(), table_.max_size());
386 HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size());
388 // Most of the checks are in AddEntriesExpectNoEviction().
389 AddEntriesExpectNoEviction(entries);
390 EXPECT_EQ(table_.max_size(), table_.size());
391 EXPECT_EQ(table_.settings_size_bound(), table_.size());
394 // Fill a header table with entries, and then ramp the table's max
395 // size down to evict an entry one at a time. Make sure the eviction
396 // happens as expected.
397 TEST_F(HpackHeaderTableTest, SetMaxSize) {
398 HpackEntryVector entries = MakeEntriesOfTotalSize(
399 kDefaultHeaderTableSizeSetting / 2);
400 AddEntriesExpectNoEviction(entries);
402 for (HpackEntryVector::iterator it = entries.begin();
403 it != entries.end(); ++it) {
404 size_t expected_count = distance(it, entries.end());
405 EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
407 table_.SetMaxSize(table_.size() + 1);
408 EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
410 table_.SetMaxSize(table_.size());
411 EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
413 --expected_count;
414 table_.SetMaxSize(table_.size() - 1);
415 EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
417 EXPECT_EQ(0u, table_.size());
420 // Fill a header table with entries, and then add an entry just big
421 // enough to cause eviction of all but one entry. Make sure the
422 // eviction happens as expected and the long entry is inserted into
423 // the table.
424 TEST_F(HpackHeaderTableTest, TryAddEntryEviction) {
425 HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size());
426 AddEntriesExpectNoEviction(entries);
428 HpackEntry* survivor_entry = table_.GetByIndex(1);
429 HpackEntry long_entry =
430 MakeEntryOfSize(table_.max_size() - survivor_entry->Size());
432 // All entries but the first are to be evicted.
433 EXPECT_EQ(peer_.dynamic_entries().size() - 1, peer_.EvictionSet(
434 long_entry.name(), long_entry.value()).size());
436 HpackEntry* new_entry = table_.TryAddEntry(long_entry.name(),
437 long_entry.value());
438 EXPECT_EQ(1u, table_.IndexOf(new_entry));
439 EXPECT_EQ(2u, peer_.dynamic_entries().size());
440 EXPECT_EQ(table_.GetByIndex(2), survivor_entry);
441 EXPECT_EQ(table_.GetByIndex(1), new_entry);
444 // Fill a header table with entries, and then add an entry bigger than
445 // the entire table. Make sure no entry remains in the table.
446 TEST_F(HpackHeaderTableTest, TryAddTooLargeEntry) {
447 HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size());
448 AddEntriesExpectNoEviction(entries);
450 HpackEntry long_entry = MakeEntryOfSize(table_.max_size() + 1);
452 // All entries are to be evicted.
453 EXPECT_EQ(peer_.dynamic_entries().size(), peer_.EvictionSet(
454 long_entry.name(), long_entry.value()).size());
456 HpackEntry* new_entry = table_.TryAddEntry(long_entry.name(),
457 long_entry.value());
458 EXPECT_EQ(new_entry, static_cast<HpackEntry*>(NULL));
459 EXPECT_EQ(0u, peer_.dynamic_entries().size());
462 TEST_F(HpackHeaderTableTest, ComparatorNameOrdering) {
463 HpackEntry entry1(StaticEntry());
464 name_[0]--;
465 HpackEntry entry2(StaticEntry());
467 HpackHeaderTable::EntryComparator comparator(&table_);
468 EXPECT_FALSE(comparator(&entry1, &entry2));
469 EXPECT_TRUE(comparator(&entry2, &entry1));
472 TEST_F(HpackHeaderTableTest, ComparatorValueOrdering) {
473 HpackEntry entry1(StaticEntry());
474 value_[0]--;
475 HpackEntry entry2(StaticEntry());
477 HpackHeaderTable::EntryComparator comparator(&table_);
478 EXPECT_FALSE(comparator(&entry1, &entry2));
479 EXPECT_TRUE(comparator(&entry2, &entry1));
482 TEST_F(HpackHeaderTableTest, ComparatorIndexOrdering) {
483 HpackEntry entry1(StaticEntry());
484 HpackEntry entry2(StaticEntry());
486 HpackHeaderTable::EntryComparator comparator(&table_);
487 EXPECT_TRUE(comparator(&entry1, &entry2));
488 EXPECT_FALSE(comparator(&entry2, &entry1));
490 HpackEntry entry3(DynamicEntry());
491 HpackEntry entry4(DynamicEntry());
493 // |entry4| has lower index than |entry3|.
494 EXPECT_TRUE(comparator(&entry4, &entry3));
495 EXPECT_FALSE(comparator(&entry3, &entry4));
497 // |entry3| has lower index than |entry1|.
498 EXPECT_TRUE(comparator(&entry3, &entry1));
499 EXPECT_FALSE(comparator(&entry1, &entry3));
501 // |entry1| & |entry2| ordering is preserved, though each Index() has changed.
502 EXPECT_TRUE(comparator(&entry1, &entry2));
503 EXPECT_FALSE(comparator(&entry2, &entry1));
506 TEST_F(HpackHeaderTableTest, ComparatorEqualityOrdering) {
507 HpackEntry entry1(StaticEntry());
508 HpackEntry entry2(DynamicEntry());
510 HpackHeaderTable::EntryComparator comparator(&table_);
511 EXPECT_FALSE(comparator(&entry1, &entry1));
512 EXPECT_FALSE(comparator(&entry2, &entry2));
515 } // namespace
517 } // namespace net