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 "quiche/spdy/core/hpack/hpack_header_table.h"
6
7 #include <algorithm>
8 #include <cstddef>
9 #include <cstdint>
10 #include <string>
11 #include <vector>
12
13 #include "absl/strings/string_view.h"
14 #include "quiche/common/platform/api/quiche_test.h"
15 #include "quiche/spdy/core/hpack/hpack_constants.h"
16 #include "quiche/spdy/core/hpack/hpack_entry.h"
17 #include "quiche/spdy/core/hpack/hpack_static_table.h"
18
19 namespace spdy {
20
21 using std::distance;
22
23 namespace test {
24
25 class HpackHeaderTablePeer {
26 public:
HpackHeaderTablePeer(HpackHeaderTable * table)27 explicit HpackHeaderTablePeer(HpackHeaderTable* table) : table_(table) {}
28
dynamic_entries()29 const HpackHeaderTable::DynamicEntryTable& dynamic_entries() {
30 return table_->dynamic_entries_;
31 }
static_entries()32 const HpackHeaderTable::StaticEntryTable& static_entries() {
33 return table_->static_entries_;
34 }
GetFirstStaticEntry()35 const HpackEntry* GetFirstStaticEntry() {
36 return &table_->static_entries_.front();
37 }
GetLastStaticEntry()38 const HpackEntry* GetLastStaticEntry() {
39 return &table_->static_entries_.back();
40 }
EvictionSet(absl::string_view name,absl::string_view value)41 std::vector<HpackEntry*> EvictionSet(absl::string_view name,
42 absl::string_view value) {
43 HpackHeaderTable::DynamicEntryTable::iterator begin, end;
44 table_->EvictionSet(name, value, &begin, &end);
45 std::vector<HpackEntry*> result;
46 for (; begin != end; ++begin) {
47 result.push_back(begin->get());
48 }
49 return result;
50 }
dynamic_table_insertions()51 size_t dynamic_table_insertions() {
52 return table_->dynamic_table_insertions_;
53 }
EvictionCountForEntry(absl::string_view name,absl::string_view value)54 size_t EvictionCountForEntry(absl::string_view name,
55 absl::string_view value) {
56 return table_->EvictionCountForEntry(name, value);
57 }
EvictionCountToReclaim(size_t reclaim_size)58 size_t EvictionCountToReclaim(size_t reclaim_size) {
59 return table_->EvictionCountToReclaim(reclaim_size);
60 }
Evict(size_t count)61 void Evict(size_t count) { return table_->Evict(count); }
62
63 private:
64 HpackHeaderTable* table_;
65 };
66
67 } // namespace test
68
69 namespace {
70
71 class HpackHeaderTableTest : public quiche::test::QuicheTest {
72 protected:
73 typedef std::vector<HpackEntry> HpackEntryVector;
74
HpackHeaderTableTest()75 HpackHeaderTableTest() : table_(), peer_(&table_) {}
76
77 // Returns an entry whose Size() is equal to the given one.
MakeEntryOfSize(uint32_t size)78 static HpackEntry MakeEntryOfSize(uint32_t size) {
79 EXPECT_GE(size, kHpackEntrySizeOverhead);
80 std::string name((size - kHpackEntrySizeOverhead) / 2, 'n');
81 std::string value(size - kHpackEntrySizeOverhead - 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.
MakeEntriesOfTotalSize(uint32_t total_size)89 static HpackEntryVector MakeEntriesOfTotalSize(uint32_t total_size) {
90 EXPECT_GE(total_size, kHpackEntrySizeOverhead);
91 uint32_t entry_size = kHpackEntrySizeOverhead;
92 uint32_t 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.
AddEntriesExpectNoEviction(const HpackEntryVector & entries)105 void AddEntriesExpectNoEviction(const HpackEntryVector& entries) {
106 for (auto it = entries.begin(); it != entries.end(); ++it) {
107 HpackHeaderTable::DynamicEntryTable::iterator begin, end;
108
109 table_.EvictionSet(it->name(), it->value(), &begin, &end);
110 EXPECT_EQ(0, distance(begin, end));
111
112 const HpackEntry* entry = table_.TryAddEntry(it->name(), it->value());
113 EXPECT_NE(entry, static_cast<HpackEntry*>(nullptr));
114 }
115 }
116
117 HpackHeaderTable table_;
118 test::HpackHeaderTablePeer peer_;
119 };
120
TEST_F(HpackHeaderTableTest,StaticTableInitialization)121 TEST_F(HpackHeaderTableTest, StaticTableInitialization) {
122 EXPECT_EQ(0u, table_.size());
123 EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.max_size());
124 EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound());
125
126 EXPECT_EQ(0u, peer_.dynamic_entries().size());
127 EXPECT_EQ(0u, peer_.dynamic_table_insertions());
128
129 // Static entries have been populated and inserted into the table & index.
130 const HpackHeaderTable::StaticEntryTable& static_entries =
131 peer_.static_entries();
132 EXPECT_EQ(kStaticTableSize, static_entries.size());
133 // HPACK indexing scheme is 1-based.
134 size_t index = 1;
135 for (const HpackEntry& entry : static_entries) {
136 EXPECT_EQ(index, table_.GetByNameAndValue(entry.name(), entry.value()));
137 index++;
138 }
139 }
140
TEST_F(HpackHeaderTableTest,BasicDynamicEntryInsertionAndEviction)141 TEST_F(HpackHeaderTableTest, BasicDynamicEntryInsertionAndEviction) {
142 EXPECT_EQ(kStaticTableSize, peer_.static_entries().size());
143
144 const HpackEntry* first_static_entry = peer_.GetFirstStaticEntry();
145 const HpackEntry* last_static_entry = peer_.GetLastStaticEntry();
146
147 const HpackEntry* entry = table_.TryAddEntry("header-key", "Header Value");
148 EXPECT_EQ("header-key", entry->name());
149 EXPECT_EQ("Header Value", entry->value());
150
151 // Table counts were updated appropriately.
152 EXPECT_EQ(entry->Size(), table_.size());
153 EXPECT_EQ(1u, peer_.dynamic_entries().size());
154 EXPECT_EQ(kStaticTableSize, peer_.static_entries().size());
155
156 EXPECT_EQ(62u, table_.GetByNameAndValue("header-key", "Header Value"));
157
158 // Index of static entries does not change.
159 EXPECT_EQ(first_static_entry, peer_.GetFirstStaticEntry());
160 EXPECT_EQ(last_static_entry, peer_.GetLastStaticEntry());
161
162 // Evict |entry|. Table counts are again updated appropriately.
163 peer_.Evict(1);
164 EXPECT_EQ(0u, table_.size());
165 EXPECT_EQ(0u, peer_.dynamic_entries().size());
166 EXPECT_EQ(kStaticTableSize, peer_.static_entries().size());
167
168 // Index of static entries does not change.
169 EXPECT_EQ(first_static_entry, peer_.GetFirstStaticEntry());
170 EXPECT_EQ(last_static_entry, peer_.GetLastStaticEntry());
171 }
172
TEST_F(HpackHeaderTableTest,EntryIndexing)173 TEST_F(HpackHeaderTableTest, EntryIndexing) {
174 const HpackEntry* first_static_entry = peer_.GetFirstStaticEntry();
175 const HpackEntry* last_static_entry = peer_.GetLastStaticEntry();
176
177 // Static entries are queryable by name & value.
178 EXPECT_EQ(1u, table_.GetByName(first_static_entry->name()));
179 EXPECT_EQ(1u, table_.GetByNameAndValue(first_static_entry->name(),
180 first_static_entry->value()));
181
182 // Create a mix of entries which duplicate names, and names & values of both
183 // dynamic and static entries.
184 table_.TryAddEntry(first_static_entry->name(), first_static_entry->value());
185 table_.TryAddEntry(first_static_entry->name(), "Value Four");
186 table_.TryAddEntry("key-1", "Value One");
187 table_.TryAddEntry("key-2", "Value Three");
188 table_.TryAddEntry("key-1", "Value Two");
189 table_.TryAddEntry("key-2", "Value Three");
190 table_.TryAddEntry("key-2", "Value Four");
191
192 // The following entry is identical to the one at index 68. The smaller index
193 // is returned by GetByNameAndValue().
194 EXPECT_EQ(1u, table_.GetByNameAndValue(first_static_entry->name(),
195 first_static_entry->value()));
196 EXPECT_EQ(67u,
197 table_.GetByNameAndValue(first_static_entry->name(), "Value Four"));
198 EXPECT_EQ(66u, table_.GetByNameAndValue("key-1", "Value One"));
199 EXPECT_EQ(64u, table_.GetByNameAndValue("key-1", "Value Two"));
200 // The following entry is identical to the one at index 65. The smaller index
201 // is returned by GetByNameAndValue().
202 EXPECT_EQ(63u, table_.GetByNameAndValue("key-2", "Value Three"));
203 EXPECT_EQ(62u, table_.GetByNameAndValue("key-2", "Value Four"));
204
205 // Index of static entries does not change.
206 EXPECT_EQ(first_static_entry, peer_.GetFirstStaticEntry());
207 EXPECT_EQ(last_static_entry, peer_.GetLastStaticEntry());
208
209 // Querying by name returns the most recently added matching entry.
210 EXPECT_EQ(64u, table_.GetByName("key-1"));
211 EXPECT_EQ(62u, table_.GetByName("key-2"));
212 EXPECT_EQ(1u, table_.GetByName(first_static_entry->name()));
213 EXPECT_EQ(kHpackEntryNotFound, table_.GetByName("not-present"));
214
215 // Querying by name & value returns the lowest-index matching entry among
216 // static entries, and the highest-index one among dynamic entries.
217 EXPECT_EQ(66u, table_.GetByNameAndValue("key-1", "Value One"));
218 EXPECT_EQ(64u, table_.GetByNameAndValue("key-1", "Value Two"));
219 EXPECT_EQ(63u, table_.GetByNameAndValue("key-2", "Value Three"));
220 EXPECT_EQ(62u, table_.GetByNameAndValue("key-2", "Value Four"));
221 EXPECT_EQ(1u, table_.GetByNameAndValue(first_static_entry->name(),
222 first_static_entry->value()));
223 EXPECT_EQ(67u,
224 table_.GetByNameAndValue(first_static_entry->name(), "Value Four"));
225 EXPECT_EQ(kHpackEntryNotFound,
226 table_.GetByNameAndValue("key-1", "Not Present"));
227 EXPECT_EQ(kHpackEntryNotFound,
228 table_.GetByNameAndValue("not-present", "Value One"));
229
230 // Evict |entry1|. Queries for its name & value now return the static entry.
231 // |entry2| remains queryable.
232 peer_.Evict(1);
233 EXPECT_EQ(1u, table_.GetByNameAndValue(first_static_entry->name(),
234 first_static_entry->value()));
235 EXPECT_EQ(67u,
236 table_.GetByNameAndValue(first_static_entry->name(), "Value Four"));
237
238 // Evict |entry2|. Queries by its name & value are not found.
239 peer_.Evict(1);
240 EXPECT_EQ(kHpackEntryNotFound,
241 table_.GetByNameAndValue(first_static_entry->name(), "Value Four"));
242
243 // Index of static entries does not change.
244 EXPECT_EQ(first_static_entry, peer_.GetFirstStaticEntry());
245 EXPECT_EQ(last_static_entry, peer_.GetLastStaticEntry());
246 }
247
TEST_F(HpackHeaderTableTest,SetSizes)248 TEST_F(HpackHeaderTableTest, SetSizes) {
249 std::string key = "key", value = "value";
250 const HpackEntry* entry1 = table_.TryAddEntry(key, value);
251 const HpackEntry* entry2 = table_.TryAddEntry(key, value);
252 const HpackEntry* entry3 = table_.TryAddEntry(key, value);
253
254 // Set exactly large enough. No Evictions.
255 size_t max_size = entry1->Size() + entry2->Size() + entry3->Size();
256 table_.SetMaxSize(max_size);
257 EXPECT_EQ(3u, peer_.dynamic_entries().size());
258
259 // Set just too small. One eviction.
260 max_size = entry1->Size() + entry2->Size() + entry3->Size() - 1;
261 table_.SetMaxSize(max_size);
262 EXPECT_EQ(2u, peer_.dynamic_entries().size());
263
264 // Changing SETTINGS_HEADER_TABLE_SIZE.
265 EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound());
266 // In production, the size passed to SetSettingsHeaderTableSize is never
267 // larger than table_.settings_size_bound().
268 table_.SetSettingsHeaderTableSize(kDefaultHeaderTableSizeSetting * 3 + 1);
269 EXPECT_EQ(kDefaultHeaderTableSizeSetting * 3 + 1, table_.max_size());
270
271 // SETTINGS_HEADER_TABLE_SIZE upper-bounds |table_.max_size()|,
272 // and will force evictions.
273 max_size = entry3->Size() - 1;
274 table_.SetSettingsHeaderTableSize(max_size);
275 EXPECT_EQ(max_size, table_.max_size());
276 EXPECT_EQ(max_size, table_.settings_size_bound());
277 EXPECT_EQ(0u, peer_.dynamic_entries().size());
278 }
279
TEST_F(HpackHeaderTableTest,EvictionCountForEntry)280 TEST_F(HpackHeaderTableTest, EvictionCountForEntry) {
281 std::string key = "key", value = "value";
282 const HpackEntry* entry1 = table_.TryAddEntry(key, value);
283 const HpackEntry* entry2 = table_.TryAddEntry(key, value);
284 size_t entry3_size = HpackEntry::Size(key, value);
285
286 // Just enough capacity for third entry.
287 table_.SetMaxSize(entry1->Size() + entry2->Size() + entry3_size);
288 EXPECT_EQ(0u, peer_.EvictionCountForEntry(key, value));
289 EXPECT_EQ(1u, peer_.EvictionCountForEntry(key, value + "x"));
290
291 // No extra capacity. Third entry would force evictions.
292 table_.SetMaxSize(entry1->Size() + entry2->Size());
293 EXPECT_EQ(1u, peer_.EvictionCountForEntry(key, value));
294 EXPECT_EQ(2u, peer_.EvictionCountForEntry(key, value + "x"));
295 }
296
TEST_F(HpackHeaderTableTest,EvictionCountToReclaim)297 TEST_F(HpackHeaderTableTest, EvictionCountToReclaim) {
298 std::string key = "key", value = "value";
299 const HpackEntry* entry1 = table_.TryAddEntry(key, value);
300 const HpackEntry* entry2 = table_.TryAddEntry(key, value);
301
302 EXPECT_EQ(1u, peer_.EvictionCountToReclaim(1));
303 EXPECT_EQ(1u, peer_.EvictionCountToReclaim(entry1->Size()));
304 EXPECT_EQ(2u, peer_.EvictionCountToReclaim(entry1->Size() + 1));
305 EXPECT_EQ(2u, peer_.EvictionCountToReclaim(entry1->Size() + entry2->Size()));
306 }
307
308 // Fill a header table with entries. Make sure the entries are in
309 // reverse order in the header table.
TEST_F(HpackHeaderTableTest,TryAddEntryBasic)310 TEST_F(HpackHeaderTableTest, TryAddEntryBasic) {
311 EXPECT_EQ(0u, table_.size());
312 EXPECT_EQ(table_.settings_size_bound(), table_.max_size());
313
314 HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size());
315
316 // Most of the checks are in AddEntriesExpectNoEviction().
317 AddEntriesExpectNoEviction(entries);
318 EXPECT_EQ(table_.max_size(), table_.size());
319 EXPECT_EQ(table_.settings_size_bound(), table_.size());
320 }
321
322 // Fill a header table with entries, and then ramp the table's max
323 // size down to evict an entry one at a time. Make sure the eviction
324 // happens as expected.
TEST_F(HpackHeaderTableTest,SetMaxSize)325 TEST_F(HpackHeaderTableTest, SetMaxSize) {
326 HpackEntryVector entries =
327 MakeEntriesOfTotalSize(kDefaultHeaderTableSizeSetting / 2);
328 AddEntriesExpectNoEviction(entries);
329
330 for (auto it = entries.begin(); it != entries.end(); ++it) {
331 size_t expected_count = distance(it, entries.end());
332 EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
333
334 table_.SetMaxSize(table_.size() + 1);
335 EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
336
337 table_.SetMaxSize(table_.size());
338 EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
339
340 --expected_count;
341 table_.SetMaxSize(table_.size() - 1);
342 EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
343 }
344 EXPECT_EQ(0u, table_.size());
345 }
346
347 // Fill a header table with entries, and then add an entry just big
348 // enough to cause eviction of all but one entry. Make sure the
349 // eviction happens as expected and the long entry is inserted into
350 // the table.
TEST_F(HpackHeaderTableTest,TryAddEntryEviction)351 TEST_F(HpackHeaderTableTest, TryAddEntryEviction) {
352 HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size());
353 AddEntriesExpectNoEviction(entries);
354
355 // The first entry in the dynamic table.
356 const HpackEntry* survivor_entry = peer_.dynamic_entries().front().get();
357
358 HpackEntry long_entry =
359 MakeEntryOfSize(table_.max_size() - survivor_entry->Size());
360
361 // All dynamic entries but the first are to be evicted.
362 EXPECT_EQ(peer_.dynamic_entries().size() - 1,
363 peer_.EvictionSet(long_entry.name(), long_entry.value()).size());
364
365 table_.TryAddEntry(long_entry.name(), long_entry.value());
366 EXPECT_EQ(2u, peer_.dynamic_entries().size());
367 EXPECT_EQ(63u, table_.GetByNameAndValue(survivor_entry->name(),
368 survivor_entry->value()));
369 EXPECT_EQ(62u,
370 table_.GetByNameAndValue(long_entry.name(), long_entry.value()));
371 }
372
373 // Fill a header table with entries, and then add an entry bigger than
374 // the entire table. Make sure no entry remains in the table.
TEST_F(HpackHeaderTableTest,TryAddTooLargeEntry)375 TEST_F(HpackHeaderTableTest, TryAddTooLargeEntry) {
376 HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size());
377 AddEntriesExpectNoEviction(entries);
378
379 const HpackEntry long_entry = MakeEntryOfSize(table_.max_size() + 1);
380
381 // All entries are to be evicted.
382 EXPECT_EQ(peer_.dynamic_entries().size(),
383 peer_.EvictionSet(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(new_entry, static_cast<HpackEntry*>(nullptr));
388 EXPECT_EQ(0u, peer_.dynamic_entries().size());
389 }
390
391 } // namespace
392
393 } // namespace spdy
394