1 // Copyright (c) 2018 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/quic/core/qpack/qpack_header_table.h"
6
7 #include <utility>
8
9 #include "absl/base/macros.h"
10 #include "absl/strings/string_view.h"
11 #include "quiche/quic/core/qpack/qpack_static_table.h"
12 #include "quiche/quic/platform/api/quic_test.h"
13 #include "quiche/spdy/core/hpack/hpack_entry.h"
14
15 using ::testing::Mock;
16 using ::testing::StrictMock;
17
18 namespace quic {
19 namespace test {
20 namespace {
21
22 const uint64_t kMaximumDynamicTableCapacityForTesting = 1024 * 1024;
23
24 template <typename T>
25 class QpackHeaderTableTest : public QuicTest {
26 protected:
27 ~QpackHeaderTableTest() override = default;
28
SetUp()29 void SetUp() override {
30 ASSERT_TRUE(table_.SetMaximumDynamicTableCapacity(
31 kMaximumDynamicTableCapacityForTesting));
32 ASSERT_TRUE(
33 table_.SetDynamicTableCapacity(kMaximumDynamicTableCapacityForTesting));
34 }
35
EntryFitsDynamicTableCapacity(absl::string_view name,absl::string_view value) const36 bool EntryFitsDynamicTableCapacity(absl::string_view name,
37 absl::string_view value) const {
38 return table_.EntryFitsDynamicTableCapacity(name, value);
39 }
40
InsertEntry(absl::string_view name,absl::string_view value)41 void InsertEntry(absl::string_view name, absl::string_view value) {
42 table_.InsertEntry(name, value);
43 }
44
SetDynamicTableCapacity(uint64_t capacity)45 bool SetDynamicTableCapacity(uint64_t capacity) {
46 return table_.SetDynamicTableCapacity(capacity);
47 }
48
max_entries() const49 uint64_t max_entries() const { return table_.max_entries(); }
inserted_entry_count() const50 uint64_t inserted_entry_count() const {
51 return table_.inserted_entry_count();
52 }
dropped_entry_count() const53 uint64_t dropped_entry_count() const { return table_.dropped_entry_count(); }
54
55 T table_;
56 };
57
58 using MyTypes =
59 ::testing::Types<QpackEncoderHeaderTable, QpackDecoderHeaderTable>;
60 TYPED_TEST_SUITE(QpackHeaderTableTest, MyTypes);
61
62 // MaxEntries is determined by maximum dynamic table capacity,
63 // which is set at construction time.
TYPED_TEST(QpackHeaderTableTest,MaxEntries)64 TYPED_TEST(QpackHeaderTableTest, MaxEntries) {
65 TypeParam table1;
66 table1.SetMaximumDynamicTableCapacity(1024);
67 EXPECT_EQ(32u, table1.max_entries());
68
69 TypeParam table2;
70 table2.SetMaximumDynamicTableCapacity(500);
71 EXPECT_EQ(15u, table2.max_entries());
72 }
73
TYPED_TEST(QpackHeaderTableTest,SetDynamicTableCapacity)74 TYPED_TEST(QpackHeaderTableTest, SetDynamicTableCapacity) {
75 // Dynamic table capacity does not affect MaxEntries.
76 EXPECT_TRUE(this->SetDynamicTableCapacity(1024));
77 EXPECT_EQ(32u * 1024, this->max_entries());
78
79 EXPECT_TRUE(this->SetDynamicTableCapacity(500));
80 EXPECT_EQ(32u * 1024, this->max_entries());
81
82 // Dynamic table capacity cannot exceed maximum dynamic table capacity.
83 EXPECT_FALSE(this->SetDynamicTableCapacity(
84 2 * kMaximumDynamicTableCapacityForTesting));
85 }
86
TYPED_TEST(QpackHeaderTableTest,EntryFitsDynamicTableCapacity)87 TYPED_TEST(QpackHeaderTableTest, EntryFitsDynamicTableCapacity) {
88 EXPECT_TRUE(this->SetDynamicTableCapacity(39));
89
90 EXPECT_TRUE(this->EntryFitsDynamicTableCapacity("foo", "bar"));
91 EXPECT_TRUE(this->EntryFitsDynamicTableCapacity("foo", "bar2"));
92 EXPECT_FALSE(this->EntryFitsDynamicTableCapacity("foo", "bar12"));
93 }
94
95 class QpackEncoderHeaderTableTest
96 : public QpackHeaderTableTest<QpackEncoderHeaderTable> {
97 protected:
98 ~QpackEncoderHeaderTableTest() override = default;
99
ExpectMatch(absl::string_view name,absl::string_view value,QpackEncoderHeaderTable::MatchType expected_match_type,bool expected_is_static,uint64_t expected_index) const100 void ExpectMatch(absl::string_view name, absl::string_view value,
101 QpackEncoderHeaderTable::MatchType expected_match_type,
102 bool expected_is_static, uint64_t expected_index) const {
103 // Initialize outparams to a value different from the expected to ensure
104 // that FindHeaderField() sets them.
105 bool is_static = !expected_is_static;
106 uint64_t index = expected_index + 1;
107
108 QpackEncoderHeaderTable::MatchType matchtype =
109 table_.FindHeaderField(name, value, &is_static, &index);
110
111 EXPECT_EQ(expected_match_type, matchtype) << name << ": " << value;
112 EXPECT_EQ(expected_is_static, is_static) << name << ": " << value;
113 EXPECT_EQ(expected_index, index) << name << ": " << value;
114 }
115
ExpectNoMatch(absl::string_view name,absl::string_view value) const116 void ExpectNoMatch(absl::string_view name, absl::string_view value) const {
117 bool is_static = false;
118 uint64_t index = 0;
119
120 QpackEncoderHeaderTable::MatchType matchtype =
121 table_.FindHeaderField(name, value, &is_static, &index);
122
123 EXPECT_EQ(QpackEncoderHeaderTable::MatchType::kNoMatch, matchtype)
124 << name << ": " << value;
125 }
126
MaxInsertSizeWithoutEvictingGivenEntry(uint64_t index) const127 uint64_t MaxInsertSizeWithoutEvictingGivenEntry(uint64_t index) const {
128 return table_.MaxInsertSizeWithoutEvictingGivenEntry(index);
129 }
130
draining_index(float draining_fraction) const131 uint64_t draining_index(float draining_fraction) const {
132 return table_.draining_index(draining_fraction);
133 }
134 };
135
TEST_F(QpackEncoderHeaderTableTest,FindStaticHeaderField)136 TEST_F(QpackEncoderHeaderTableTest, FindStaticHeaderField) {
137 // A header name that has multiple entries with different values.
138 ExpectMatch(":method", "GET",
139 QpackEncoderHeaderTable::MatchType::kNameAndValue, true, 17u);
140
141 ExpectMatch(":method", "POST",
142 QpackEncoderHeaderTable::MatchType::kNameAndValue, true, 20u);
143
144 ExpectMatch(":method", "TRACE", QpackEncoderHeaderTable::MatchType::kName,
145 true, 15u);
146
147 // A header name that has a single entry with non-empty value.
148 ExpectMatch("accept-encoding", "gzip, deflate, br",
149 QpackEncoderHeaderTable::MatchType::kNameAndValue, true, 31u);
150
151 ExpectMatch("accept-encoding", "compress",
152 QpackEncoderHeaderTable::MatchType::kName, true, 31u);
153
154 ExpectMatch("accept-encoding", "", QpackEncoderHeaderTable::MatchType::kName,
155 true, 31u);
156
157 // A header name that has a single entry with empty value.
158 ExpectMatch("location", "", QpackEncoderHeaderTable::MatchType::kNameAndValue,
159 true, 12u);
160
161 ExpectMatch("location", "foo", QpackEncoderHeaderTable::MatchType::kName,
162 true, 12u);
163
164 // No matching header name.
165 ExpectNoMatch("foo", "");
166 ExpectNoMatch("foo", "bar");
167 }
168
TEST_F(QpackEncoderHeaderTableTest,FindDynamicHeaderField)169 TEST_F(QpackEncoderHeaderTableTest, FindDynamicHeaderField) {
170 // Dynamic table is initially entry.
171 ExpectNoMatch("foo", "bar");
172 ExpectNoMatch("foo", "baz");
173
174 // Insert one entry.
175 InsertEntry("foo", "bar");
176
177 // Match name and value.
178 ExpectMatch("foo", "bar", QpackEncoderHeaderTable::MatchType::kNameAndValue,
179 false, 0u);
180
181 // Match name only.
182 ExpectMatch("foo", "baz", QpackEncoderHeaderTable::MatchType::kName, false,
183 0u);
184
185 // Insert an identical entry. FindHeaderField() should return the index of
186 // the most recently inserted matching entry.
187 InsertEntry("foo", "bar");
188
189 // Match name and value.
190 ExpectMatch("foo", "bar", QpackEncoderHeaderTable::MatchType::kNameAndValue,
191 false, 1u);
192
193 // Match name only.
194 ExpectMatch("foo", "baz", QpackEncoderHeaderTable::MatchType::kName, false,
195 1u);
196 }
197
TEST_F(QpackEncoderHeaderTableTest,FindHeaderFieldPrefersStaticTable)198 TEST_F(QpackEncoderHeaderTableTest, FindHeaderFieldPrefersStaticTable) {
199 // Insert an entry to the dynamic table that exists in the static table.
200 InsertEntry(":method", "GET");
201
202 // FindHeaderField() prefers static table if both have name-and-value match.
203 ExpectMatch(":method", "GET",
204 QpackEncoderHeaderTable::MatchType::kNameAndValue, true, 17u);
205
206 // FindHeaderField() prefers static table if both have name match but no value
207 // match, and prefers the first entry with matching name.
208 ExpectMatch(":method", "TRACE", QpackEncoderHeaderTable::MatchType::kName,
209 true, 15u);
210
211 // Add new entry to the dynamic table.
212 InsertEntry(":method", "TRACE");
213
214 // FindHeaderField prefers name-and-value match in dynamic table over name
215 // only match in static table.
216 ExpectMatch(":method", "TRACE",
217 QpackEncoderHeaderTable::MatchType::kNameAndValue, false, 1u);
218 }
219
TEST_F(QpackEncoderHeaderTableTest,EvictByInsertion)220 TEST_F(QpackEncoderHeaderTableTest, EvictByInsertion) {
221 EXPECT_TRUE(SetDynamicTableCapacity(40));
222
223 // Entry size is 3 + 3 + 32 = 38.
224 InsertEntry("foo", "bar");
225 EXPECT_EQ(1u, inserted_entry_count());
226 EXPECT_EQ(0u, dropped_entry_count());
227
228 ExpectMatch("foo", "bar", QpackEncoderHeaderTable::MatchType::kNameAndValue,
229 /* expected_is_static = */ false, 0u);
230
231 // Inserting second entry evicts the first one.
232 InsertEntry("baz", "qux");
233 EXPECT_EQ(2u, inserted_entry_count());
234 EXPECT_EQ(1u, dropped_entry_count());
235
236 ExpectNoMatch("foo", "bar");
237 ExpectMatch("baz", "qux", QpackEncoderHeaderTable::MatchType::kNameAndValue,
238 /* expected_is_static = */ false, 1u);
239 }
240
TEST_F(QpackEncoderHeaderTableTest,EvictByUpdateTableSize)241 TEST_F(QpackEncoderHeaderTableTest, EvictByUpdateTableSize) {
242 // Entry size is 3 + 3 + 32 = 38.
243 InsertEntry("foo", "bar");
244 InsertEntry("baz", "qux");
245 EXPECT_EQ(2u, inserted_entry_count());
246 EXPECT_EQ(0u, dropped_entry_count());
247
248 ExpectMatch("foo", "bar", QpackEncoderHeaderTable::MatchType::kNameAndValue,
249 /* expected_is_static = */ false, 0u);
250 ExpectMatch("baz", "qux", QpackEncoderHeaderTable::MatchType::kNameAndValue,
251 /* expected_is_static = */ false, 1u);
252
253 EXPECT_TRUE(SetDynamicTableCapacity(40));
254 EXPECT_EQ(2u, inserted_entry_count());
255 EXPECT_EQ(1u, dropped_entry_count());
256
257 ExpectNoMatch("foo", "bar");
258 ExpectMatch("baz", "qux", QpackEncoderHeaderTable::MatchType::kNameAndValue,
259 /* expected_is_static = */ false, 1u);
260
261 EXPECT_TRUE(SetDynamicTableCapacity(20));
262 EXPECT_EQ(2u, inserted_entry_count());
263 EXPECT_EQ(2u, dropped_entry_count());
264
265 ExpectNoMatch("foo", "bar");
266 ExpectNoMatch("baz", "qux");
267 }
268
TEST_F(QpackEncoderHeaderTableTest,EvictOldestOfIdentical)269 TEST_F(QpackEncoderHeaderTableTest, EvictOldestOfIdentical) {
270 EXPECT_TRUE(SetDynamicTableCapacity(80));
271
272 // Entry size is 3 + 3 + 32 = 38.
273 // Insert same entry twice.
274 InsertEntry("foo", "bar");
275 InsertEntry("foo", "bar");
276 EXPECT_EQ(2u, inserted_entry_count());
277 EXPECT_EQ(0u, dropped_entry_count());
278
279 // Find most recently inserted entry.
280 ExpectMatch("foo", "bar", QpackEncoderHeaderTable::MatchType::kNameAndValue,
281 /* expected_is_static = */ false, 1u);
282
283 // Inserting third entry evicts the first one, not the second.
284 InsertEntry("baz", "qux");
285 EXPECT_EQ(3u, inserted_entry_count());
286 EXPECT_EQ(1u, dropped_entry_count());
287
288 ExpectMatch("foo", "bar", QpackEncoderHeaderTable::MatchType::kNameAndValue,
289 /* expected_is_static = */ false, 1u);
290 ExpectMatch("baz", "qux", QpackEncoderHeaderTable::MatchType::kNameAndValue,
291 /* expected_is_static = */ false, 2u);
292 }
293
TEST_F(QpackEncoderHeaderTableTest,EvictOldestOfSameName)294 TEST_F(QpackEncoderHeaderTableTest, EvictOldestOfSameName) {
295 EXPECT_TRUE(SetDynamicTableCapacity(80));
296
297 // Entry size is 3 + 3 + 32 = 38.
298 // Insert two entries with same name but different values.
299 InsertEntry("foo", "bar");
300 InsertEntry("foo", "baz");
301 EXPECT_EQ(2u, inserted_entry_count());
302 EXPECT_EQ(0u, dropped_entry_count());
303
304 // Find most recently inserted entry with matching name.
305 ExpectMatch("foo", "foo", QpackEncoderHeaderTable::MatchType::kName,
306 /* expected_is_static = */ false, 1u);
307
308 // Inserting third entry evicts the first one, not the second.
309 InsertEntry("baz", "qux");
310 EXPECT_EQ(3u, inserted_entry_count());
311 EXPECT_EQ(1u, dropped_entry_count());
312
313 ExpectMatch("foo", "foo", QpackEncoderHeaderTable::MatchType::kName,
314 /* expected_is_static = */ false, 1u);
315 ExpectMatch("baz", "qux", QpackEncoderHeaderTable::MatchType::kNameAndValue,
316 /* expected_is_static = */ false, 2u);
317 }
318
319 // Returns the size of the largest entry that could be inserted into the
320 // dynamic table without evicting entry |index|.
TEST_F(QpackEncoderHeaderTableTest,MaxInsertSizeWithoutEvictingGivenEntry)321 TEST_F(QpackEncoderHeaderTableTest, MaxInsertSizeWithoutEvictingGivenEntry) {
322 const uint64_t dynamic_table_capacity = 100;
323 EXPECT_TRUE(SetDynamicTableCapacity(dynamic_table_capacity));
324
325 // Empty table can take an entry up to its capacity.
326 EXPECT_EQ(dynamic_table_capacity, MaxInsertSizeWithoutEvictingGivenEntry(0));
327
328 const uint64_t entry_size1 = QpackEntry::Size("foo", "bar");
329 InsertEntry("foo", "bar");
330 EXPECT_EQ(dynamic_table_capacity - entry_size1,
331 MaxInsertSizeWithoutEvictingGivenEntry(0));
332 // Table can take an entry up to its capacity if all entries are allowed to be
333 // evicted.
334 EXPECT_EQ(dynamic_table_capacity, MaxInsertSizeWithoutEvictingGivenEntry(1));
335
336 const uint64_t entry_size2 = QpackEntry::Size("baz", "foobar");
337 InsertEntry("baz", "foobar");
338 // Table can take an entry up to its capacity if all entries are allowed to be
339 // evicted.
340 EXPECT_EQ(dynamic_table_capacity, MaxInsertSizeWithoutEvictingGivenEntry(2));
341 // Second entry must stay.
342 EXPECT_EQ(dynamic_table_capacity - entry_size2,
343 MaxInsertSizeWithoutEvictingGivenEntry(1));
344 // First and second entry must stay.
345 EXPECT_EQ(dynamic_table_capacity - entry_size2 - entry_size1,
346 MaxInsertSizeWithoutEvictingGivenEntry(0));
347
348 // Third entry evicts first one.
349 const uint64_t entry_size3 = QpackEntry::Size("last", "entry");
350 InsertEntry("last", "entry");
351 EXPECT_EQ(1u, dropped_entry_count());
352 // Table can take an entry up to its capacity if all entries are allowed to be
353 // evicted.
354 EXPECT_EQ(dynamic_table_capacity, MaxInsertSizeWithoutEvictingGivenEntry(3));
355 // Third entry must stay.
356 EXPECT_EQ(dynamic_table_capacity - entry_size3,
357 MaxInsertSizeWithoutEvictingGivenEntry(2));
358 // Second and third entry must stay.
359 EXPECT_EQ(dynamic_table_capacity - entry_size3 - entry_size2,
360 MaxInsertSizeWithoutEvictingGivenEntry(1));
361 }
362
TEST_F(QpackEncoderHeaderTableTest,DrainingIndex)363 TEST_F(QpackEncoderHeaderTableTest, DrainingIndex) {
364 EXPECT_TRUE(SetDynamicTableCapacity(4 * QpackEntry::Size("foo", "bar")));
365
366 // Empty table: no draining entry.
367 EXPECT_EQ(0u, draining_index(0.0));
368 EXPECT_EQ(0u, draining_index(1.0));
369
370 // Table with one entry.
371 InsertEntry("foo", "bar");
372 // Any entry can be referenced if none of the table is draining.
373 EXPECT_EQ(0u, draining_index(0.0));
374 // No entry can be referenced if all of the table is draining.
375 EXPECT_EQ(1u, draining_index(1.0));
376
377 // Table with two entries is at half capacity.
378 InsertEntry("foo", "bar");
379 // Any entry can be referenced if at most half of the table is draining,
380 // because current entries only take up half of total capacity.
381 EXPECT_EQ(0u, draining_index(0.0));
382 EXPECT_EQ(0u, draining_index(0.5));
383 // No entry can be referenced if all of the table is draining.
384 EXPECT_EQ(2u, draining_index(1.0));
385
386 // Table with four entries is full.
387 InsertEntry("foo", "bar");
388 InsertEntry("foo", "bar");
389 // Any entry can be referenced if none of the table is draining.
390 EXPECT_EQ(0u, draining_index(0.0));
391 // In a full table with identically sized entries, |draining_fraction| of all
392 // entries are draining.
393 EXPECT_EQ(2u, draining_index(0.5));
394 // No entry can be referenced if all of the table is draining.
395 EXPECT_EQ(4u, draining_index(1.0));
396 }
397
398 class MockObserver : public QpackDecoderHeaderTable::Observer {
399 public:
400 ~MockObserver() override = default;
401
402 MOCK_METHOD(void, OnInsertCountReachedThreshold, (), (override));
403 MOCK_METHOD(void, Cancel, (), (override));
404 };
405
406 class QpackDecoderHeaderTableTest
407 : public QpackHeaderTableTest<QpackDecoderHeaderTable> {
408 protected:
409 ~QpackDecoderHeaderTableTest() override = default;
410
ExpectEntryAtIndex(bool is_static,uint64_t index,absl::string_view expected_name,absl::string_view expected_value) const411 void ExpectEntryAtIndex(bool is_static, uint64_t index,
412 absl::string_view expected_name,
413 absl::string_view expected_value) const {
414 const auto* entry = table_.LookupEntry(is_static, index);
415 ASSERT_TRUE(entry);
416 EXPECT_EQ(expected_name, entry->name());
417 EXPECT_EQ(expected_value, entry->value());
418 }
419
ExpectNoEntryAtIndex(bool is_static,uint64_t index) const420 void ExpectNoEntryAtIndex(bool is_static, uint64_t index) const {
421 EXPECT_FALSE(table_.LookupEntry(is_static, index));
422 }
423
RegisterObserver(uint64_t required_insert_count,QpackDecoderHeaderTable::Observer * observer)424 void RegisterObserver(uint64_t required_insert_count,
425 QpackDecoderHeaderTable::Observer* observer) {
426 table_.RegisterObserver(required_insert_count, observer);
427 }
428
UnregisterObserver(uint64_t required_insert_count,QpackDecoderHeaderTable::Observer * observer)429 void UnregisterObserver(uint64_t required_insert_count,
430 QpackDecoderHeaderTable::Observer* observer) {
431 table_.UnregisterObserver(required_insert_count, observer);
432 }
433 };
434
TEST_F(QpackDecoderHeaderTableTest,LookupStaticEntry)435 TEST_F(QpackDecoderHeaderTableTest, LookupStaticEntry) {
436 ExpectEntryAtIndex(/* is_static = */ true, 0, ":authority", "");
437
438 ExpectEntryAtIndex(/* is_static = */ true, 1, ":path", "/");
439
440 // 98 is the last entry.
441 ExpectEntryAtIndex(/* is_static = */ true, 98, "x-frame-options",
442 "sameorigin");
443
444 ASSERT_EQ(99u, QpackStaticTableVector().size());
445 ExpectNoEntryAtIndex(/* is_static = */ true, 99);
446 }
447
TEST_F(QpackDecoderHeaderTableTest,InsertAndLookupDynamicEntry)448 TEST_F(QpackDecoderHeaderTableTest, InsertAndLookupDynamicEntry) {
449 // Dynamic table is initially entry.
450 ExpectNoEntryAtIndex(/* is_static = */ false, 0);
451 ExpectNoEntryAtIndex(/* is_static = */ false, 1);
452 ExpectNoEntryAtIndex(/* is_static = */ false, 2);
453 ExpectNoEntryAtIndex(/* is_static = */ false, 3);
454
455 // Insert one entry.
456 InsertEntry("foo", "bar");
457
458 ExpectEntryAtIndex(/* is_static = */ false, 0, "foo", "bar");
459
460 ExpectNoEntryAtIndex(/* is_static = */ false, 1);
461 ExpectNoEntryAtIndex(/* is_static = */ false, 2);
462 ExpectNoEntryAtIndex(/* is_static = */ false, 3);
463
464 // Insert a different entry.
465 InsertEntry("baz", "bing");
466
467 ExpectEntryAtIndex(/* is_static = */ false, 0, "foo", "bar");
468
469 ExpectEntryAtIndex(/* is_static = */ false, 1, "baz", "bing");
470
471 ExpectNoEntryAtIndex(/* is_static = */ false, 2);
472 ExpectNoEntryAtIndex(/* is_static = */ false, 3);
473
474 // Insert an entry identical to the most recently inserted one.
475 InsertEntry("baz", "bing");
476
477 ExpectEntryAtIndex(/* is_static = */ false, 0, "foo", "bar");
478
479 ExpectEntryAtIndex(/* is_static = */ false, 1, "baz", "bing");
480
481 ExpectEntryAtIndex(/* is_static = */ false, 2, "baz", "bing");
482
483 ExpectNoEntryAtIndex(/* is_static = */ false, 3);
484 }
485
TEST_F(QpackDecoderHeaderTableTest,EvictByInsertion)486 TEST_F(QpackDecoderHeaderTableTest, EvictByInsertion) {
487 EXPECT_TRUE(SetDynamicTableCapacity(40));
488
489 // Entry size is 3 + 3 + 32 = 38.
490 InsertEntry("foo", "bar");
491 EXPECT_EQ(1u, inserted_entry_count());
492 EXPECT_EQ(0u, dropped_entry_count());
493
494 ExpectEntryAtIndex(/* is_static = */ false, 0u, "foo", "bar");
495
496 // Inserting second entry evicts the first one.
497 InsertEntry("baz", "qux");
498 EXPECT_EQ(2u, inserted_entry_count());
499 EXPECT_EQ(1u, dropped_entry_count());
500
501 ExpectNoEntryAtIndex(/* is_static = */ false, 0u);
502 ExpectEntryAtIndex(/* is_static = */ false, 1u, "baz", "qux");
503 }
504
TEST_F(QpackDecoderHeaderTableTest,EvictByUpdateTableSize)505 TEST_F(QpackDecoderHeaderTableTest, EvictByUpdateTableSize) {
506 ExpectNoEntryAtIndex(/* is_static = */ false, 0u);
507 ExpectNoEntryAtIndex(/* is_static = */ false, 1u);
508
509 // Entry size is 3 + 3 + 32 = 38.
510 InsertEntry("foo", "bar");
511 InsertEntry("baz", "qux");
512 EXPECT_EQ(2u, inserted_entry_count());
513 EXPECT_EQ(0u, dropped_entry_count());
514
515 ExpectEntryAtIndex(/* is_static = */ false, 0u, "foo", "bar");
516 ExpectEntryAtIndex(/* is_static = */ false, 1u, "baz", "qux");
517
518 EXPECT_TRUE(SetDynamicTableCapacity(40));
519 EXPECT_EQ(2u, inserted_entry_count());
520 EXPECT_EQ(1u, dropped_entry_count());
521
522 ExpectNoEntryAtIndex(/* is_static = */ false, 0u);
523 ExpectEntryAtIndex(/* is_static = */ false, 1u, "baz", "qux");
524
525 EXPECT_TRUE(SetDynamicTableCapacity(20));
526 EXPECT_EQ(2u, inserted_entry_count());
527 EXPECT_EQ(2u, dropped_entry_count());
528
529 ExpectNoEntryAtIndex(/* is_static = */ false, 0u);
530 ExpectNoEntryAtIndex(/* is_static = */ false, 1u);
531 }
532
TEST_F(QpackDecoderHeaderTableTest,EvictOldestOfIdentical)533 TEST_F(QpackDecoderHeaderTableTest, EvictOldestOfIdentical) {
534 EXPECT_TRUE(SetDynamicTableCapacity(80));
535
536 // Entry size is 3 + 3 + 32 = 38.
537 // Insert same entry twice.
538 InsertEntry("foo", "bar");
539 InsertEntry("foo", "bar");
540 EXPECT_EQ(2u, inserted_entry_count());
541 EXPECT_EQ(0u, dropped_entry_count());
542
543 ExpectEntryAtIndex(/* is_static = */ false, 0u, "foo", "bar");
544 ExpectEntryAtIndex(/* is_static = */ false, 1u, "foo", "bar");
545 ExpectNoEntryAtIndex(/* is_static = */ false, 2u);
546
547 // Inserting third entry evicts the first one, not the second.
548 InsertEntry("baz", "qux");
549 EXPECT_EQ(3u, inserted_entry_count());
550 EXPECT_EQ(1u, dropped_entry_count());
551
552 ExpectNoEntryAtIndex(/* is_static = */ false, 0u);
553 ExpectEntryAtIndex(/* is_static = */ false, 1u, "foo", "bar");
554 ExpectEntryAtIndex(/* is_static = */ false, 2u, "baz", "qux");
555 }
556
TEST_F(QpackDecoderHeaderTableTest,EvictOldestOfSameName)557 TEST_F(QpackDecoderHeaderTableTest, EvictOldestOfSameName) {
558 EXPECT_TRUE(SetDynamicTableCapacity(80));
559
560 // Entry size is 3 + 3 + 32 = 38.
561 // Insert two entries with same name but different values.
562 InsertEntry("foo", "bar");
563 InsertEntry("foo", "baz");
564 EXPECT_EQ(2u, inserted_entry_count());
565 EXPECT_EQ(0u, dropped_entry_count());
566
567 ExpectEntryAtIndex(/* is_static = */ false, 0u, "foo", "bar");
568 ExpectEntryAtIndex(/* is_static = */ false, 1u, "foo", "baz");
569 ExpectNoEntryAtIndex(/* is_static = */ false, 2u);
570
571 // Inserting third entry evicts the first one, not the second.
572 InsertEntry("baz", "qux");
573 EXPECT_EQ(3u, inserted_entry_count());
574 EXPECT_EQ(1u, dropped_entry_count());
575
576 ExpectNoEntryAtIndex(/* is_static = */ false, 0u);
577 ExpectEntryAtIndex(/* is_static = */ false, 1u, "foo", "baz");
578 ExpectEntryAtIndex(/* is_static = */ false, 2u, "baz", "qux");
579 }
580
TEST_F(QpackDecoderHeaderTableTest,RegisterObserver)581 TEST_F(QpackDecoderHeaderTableTest, RegisterObserver) {
582 StrictMock<MockObserver> observer1;
583 RegisterObserver(1, &observer1);
584 EXPECT_CALL(observer1, OnInsertCountReachedThreshold);
585 InsertEntry("foo", "bar");
586 EXPECT_EQ(1u, inserted_entry_count());
587 Mock::VerifyAndClearExpectations(&observer1);
588
589 // Registration order does not matter.
590 StrictMock<MockObserver> observer2;
591 StrictMock<MockObserver> observer3;
592 RegisterObserver(3, &observer3);
593 RegisterObserver(2, &observer2);
594
595 EXPECT_CALL(observer2, OnInsertCountReachedThreshold);
596 InsertEntry("foo", "bar");
597 EXPECT_EQ(2u, inserted_entry_count());
598 Mock::VerifyAndClearExpectations(&observer3);
599
600 EXPECT_CALL(observer3, OnInsertCountReachedThreshold);
601 InsertEntry("foo", "bar");
602 EXPECT_EQ(3u, inserted_entry_count());
603 Mock::VerifyAndClearExpectations(&observer2);
604
605 // Multiple observers with identical |required_insert_count| should all be
606 // notified.
607 StrictMock<MockObserver> observer4;
608 StrictMock<MockObserver> observer5;
609 RegisterObserver(4, &observer4);
610 RegisterObserver(4, &observer5);
611
612 EXPECT_CALL(observer4, OnInsertCountReachedThreshold);
613 EXPECT_CALL(observer5, OnInsertCountReachedThreshold);
614 InsertEntry("foo", "bar");
615 EXPECT_EQ(4u, inserted_entry_count());
616 Mock::VerifyAndClearExpectations(&observer4);
617 Mock::VerifyAndClearExpectations(&observer5);
618 }
619
TEST_F(QpackDecoderHeaderTableTest,UnregisterObserver)620 TEST_F(QpackDecoderHeaderTableTest, UnregisterObserver) {
621 StrictMock<MockObserver> observer1;
622 StrictMock<MockObserver> observer2;
623 StrictMock<MockObserver> observer3;
624 StrictMock<MockObserver> observer4;
625 RegisterObserver(1, &observer1);
626 RegisterObserver(2, &observer2);
627 RegisterObserver(2, &observer3);
628 RegisterObserver(3, &observer4);
629
630 UnregisterObserver(2, &observer3);
631
632 EXPECT_CALL(observer1, OnInsertCountReachedThreshold);
633 EXPECT_CALL(observer2, OnInsertCountReachedThreshold);
634 EXPECT_CALL(observer4, OnInsertCountReachedThreshold);
635 InsertEntry("foo", "bar");
636 InsertEntry("foo", "bar");
637 InsertEntry("foo", "bar");
638 EXPECT_EQ(3u, inserted_entry_count());
639 }
640
TEST_F(QpackDecoderHeaderTableTest,Cancel)641 TEST_F(QpackDecoderHeaderTableTest, Cancel) {
642 StrictMock<MockObserver> observer;
643 auto table = std::make_unique<QpackDecoderHeaderTable>();
644 table->RegisterObserver(1, &observer);
645
646 EXPECT_CALL(observer, Cancel);
647 table.reset();
648 }
649
650 } // namespace
651 } // namespace test
652 } // namespace quic
653