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"
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"
20 using base::StringPiece
;
26 class HpackHeaderTablePeer
{
28 explicit HpackHeaderTablePeer(HpackHeaderTable
* 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
));
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_
++));
76 HpackHeaderTable
* table_
;
83 class HpackHeaderTableTest
: public ::testing::Test
{
85 typedef std::vector
<HpackEntry
> HpackEntryVector
;
87 HpackHeaderTableTest()
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());
103 // Returns a vector of entries whose total size is equal to the given
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);
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.
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(),
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(),
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.
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(),
272 // Evict |entry2|. Queries by its name & value are not found.
274 EXPECT_EQ(NULL
, table_
.GetByNameAndValue(first_static_entry
->name(),
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());
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
));
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
));
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.
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());
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
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(),
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(),
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());
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());
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
));