blob: 0af250efd32de4ca5efe8b485c1d3f313bd3123e [file] [log] [blame]
// Copyright (c) 2018 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "quic/core/qpack/qpack_header_table.h"
#include <utility>
#include "absl/base/macros.h"
#include "absl/strings/string_view.h"
#include "quic/core/qpack/qpack_static_table.h"
#include "quic/platform/api/quic_test.h"
#include "spdy/core/hpack/hpack_entry.h"
using ::testing::Mock;
using ::testing::StrictMock;
namespace quic {
namespace test {
namespace {
const uint64_t kMaximumDynamicTableCapacityForTesting = 1024 * 1024;
class MockObserver : public QpackHeaderTable::Observer {
public:
~MockObserver() override = default;
MOCK_METHOD(void, OnInsertCountReachedThreshold, (), (override));
MOCK_METHOD(void, Cancel, (), (override));
};
class QpackHeaderTableTest : public QuicTest {
protected:
QpackHeaderTableTest() {
table_.SetMaximumDynamicTableCapacity(
kMaximumDynamicTableCapacityForTesting);
table_.SetDynamicTableCapacity(kMaximumDynamicTableCapacityForTesting);
}
~QpackHeaderTableTest() override = default;
void ExpectEntryAtIndex(bool is_static,
uint64_t index,
absl::string_view expected_name,
absl::string_view expected_value) const {
const auto* entry = table_.LookupEntry(is_static, index);
ASSERT_TRUE(entry);
EXPECT_EQ(expected_name, entry->name());
EXPECT_EQ(expected_value, entry->value());
}
void ExpectNoEntryAtIndex(bool is_static, uint64_t index) const {
EXPECT_FALSE(table_.LookupEntry(is_static, index));
}
void ExpectMatch(absl::string_view name,
absl::string_view value,
QpackHeaderTable::MatchType expected_match_type,
bool expected_is_static,
uint64_t expected_index) const {
// Initialize outparams to a value different from the expected to ensure
// that FindHeaderField() sets them.
bool is_static = !expected_is_static;
uint64_t index = expected_index + 1;
QpackHeaderTable::MatchType matchtype =
table_.FindHeaderField(name, value, &is_static, &index);
EXPECT_EQ(expected_match_type, matchtype) << name << ": " << value;
EXPECT_EQ(expected_is_static, is_static) << name << ": " << value;
EXPECT_EQ(expected_index, index) << name << ": " << value;
}
void ExpectNoMatch(absl::string_view name, absl::string_view value) const {
bool is_static = false;
uint64_t index = 0;
QpackHeaderTable::MatchType matchtype =
table_.FindHeaderField(name, value, &is_static, &index);
EXPECT_EQ(QpackHeaderTable::MatchType::kNoMatch, matchtype)
<< name << ": " << value;
}
bool EntryFitsDynamicTableCapacity(absl::string_view name,
absl::string_view value) const {
return table_.EntryFitsDynamicTableCapacity(name, value);
}
void InsertEntry(absl::string_view name, absl::string_view value) {
table_.InsertEntry(name, value);
}
bool SetDynamicTableCapacity(uint64_t capacity) {
return table_.SetDynamicTableCapacity(capacity);
}
void RegisterObserver(uint64_t required_insert_count,
QpackHeaderTable::Observer* observer) {
table_.RegisterObserver(required_insert_count, observer);
}
void UnregisterObserver(uint64_t required_insert_count,
QpackHeaderTable::Observer* observer) {
table_.UnregisterObserver(required_insert_count, observer);
}
uint64_t max_entries() const { return table_.max_entries(); }
uint64_t inserted_entry_count() const {
return table_.inserted_entry_count();
}
uint64_t dropped_entry_count() const { return table_.dropped_entry_count(); }
private:
QpackHeaderTable table_;
};
TEST_F(QpackHeaderTableTest, LookupStaticEntry) {
ExpectEntryAtIndex(/* is_static = */ true, 0, ":authority", "");
ExpectEntryAtIndex(/* is_static = */ true, 1, ":path", "/");
// 98 is the last entry.
ExpectEntryAtIndex(/* is_static = */ true, 98, "x-frame-options",
"sameorigin");
ASSERT_EQ(99u, QpackStaticTableVector().size());
ExpectNoEntryAtIndex(/* is_static = */ true, 99);
}
TEST_F(QpackHeaderTableTest, InsertAndLookupDynamicEntry) {
// Dynamic table is initially entry.
ExpectNoEntryAtIndex(/* is_static = */ false, 0);
ExpectNoEntryAtIndex(/* is_static = */ false, 1);
ExpectNoEntryAtIndex(/* is_static = */ false, 2);
ExpectNoEntryAtIndex(/* is_static = */ false, 3);
// Insert one entry.
InsertEntry("foo", "bar");
ExpectEntryAtIndex(/* is_static = */ false, 0, "foo", "bar");
ExpectNoEntryAtIndex(/* is_static = */ false, 1);
ExpectNoEntryAtIndex(/* is_static = */ false, 2);
ExpectNoEntryAtIndex(/* is_static = */ false, 3);
// Insert a different entry.
InsertEntry("baz", "bing");
ExpectEntryAtIndex(/* is_static = */ false, 0, "foo", "bar");
ExpectEntryAtIndex(/* is_static = */ false, 1, "baz", "bing");
ExpectNoEntryAtIndex(/* is_static = */ false, 2);
ExpectNoEntryAtIndex(/* is_static = */ false, 3);
// Insert an entry identical to the most recently inserted one.
InsertEntry("baz", "bing");
ExpectEntryAtIndex(/* is_static = */ false, 0, "foo", "bar");
ExpectEntryAtIndex(/* is_static = */ false, 1, "baz", "bing");
ExpectEntryAtIndex(/* is_static = */ false, 2, "baz", "bing");
ExpectNoEntryAtIndex(/* is_static = */ false, 3);
}
TEST_F(QpackHeaderTableTest, FindStaticHeaderField) {
// A header name that has multiple entries with different values.
ExpectMatch(":method", "GET", QpackHeaderTable::MatchType::kNameAndValue,
true, 17u);
ExpectMatch(":method", "POST", QpackHeaderTable::MatchType::kNameAndValue,
true, 20u);
ExpectMatch(":method", "TRACE", QpackHeaderTable::MatchType::kName, true,
15u);
// A header name that has a single entry with non-empty value.
ExpectMatch("accept-encoding", "gzip, deflate, br",
QpackHeaderTable::MatchType::kNameAndValue, true, 31u);
ExpectMatch("accept-encoding", "compress", QpackHeaderTable::MatchType::kName,
true, 31u);
ExpectMatch("accept-encoding", "", QpackHeaderTable::MatchType::kName, true,
31u);
// A header name that has a single entry with empty value.
ExpectMatch("location", "", QpackHeaderTable::MatchType::kNameAndValue, true,
12u);
ExpectMatch("location", "foo", QpackHeaderTable::MatchType::kName, true, 12u);
// No matching header name.
ExpectNoMatch("foo", "");
ExpectNoMatch("foo", "bar");
}
TEST_F(QpackHeaderTableTest, FindDynamicHeaderField) {
// Dynamic table is initially entry.
ExpectNoMatch("foo", "bar");
ExpectNoMatch("foo", "baz");
// Insert one entry.
InsertEntry("foo", "bar");
// Match name and value.
ExpectMatch("foo", "bar", QpackHeaderTable::MatchType::kNameAndValue, false,
0u);
// Match name only.
ExpectMatch("foo", "baz", QpackHeaderTable::MatchType::kName, false, 0u);
// Insert an identical entry. FindHeaderField() should return the index of
// the most recently inserted matching entry.
InsertEntry("foo", "bar");
// Match name and value.
ExpectMatch("foo", "bar", QpackHeaderTable::MatchType::kNameAndValue, false,
1u);
// Match name only.
ExpectMatch("foo", "baz", QpackHeaderTable::MatchType::kName, false, 1u);
}
TEST_F(QpackHeaderTableTest, FindHeaderFieldPrefersStaticTable) {
// Insert an entry to the dynamic table that exists in the static table.
InsertEntry(":method", "GET");
// Insertion works.
ExpectEntryAtIndex(/* is_static = */ false, 0, ":method", "GET");
// FindHeaderField() prefers static table if both have name-and-value match.
ExpectMatch(":method", "GET", QpackHeaderTable::MatchType::kNameAndValue,
true, 17u);
// FindHeaderField() prefers static table if both have name match but no value
// match, and prefers the first entry with matching name.
ExpectMatch(":method", "TRACE", QpackHeaderTable::MatchType::kName, true,
15u);
// Add new entry to the dynamic table.
InsertEntry(":method", "TRACE");
// FindHeaderField prefers name-and-value match in dynamic table over name
// only match in static table.
ExpectMatch(":method", "TRACE", QpackHeaderTable::MatchType::kNameAndValue,
false, 1u);
}
// MaxEntries is determined by maximum dynamic table capacity,
// which is set at construction time.
TEST_F(QpackHeaderTableTest, MaxEntries) {
QpackHeaderTable table1;
table1.SetMaximumDynamicTableCapacity(1024);
EXPECT_EQ(32u, table1.max_entries());
QpackHeaderTable table2;
table2.SetMaximumDynamicTableCapacity(500);
EXPECT_EQ(15u, table2.max_entries());
}
TEST_F(QpackHeaderTableTest, SetDynamicTableCapacity) {
// Dynamic table capacity does not affect MaxEntries.
EXPECT_TRUE(SetDynamicTableCapacity(1024));
EXPECT_EQ(32u * 1024, max_entries());
EXPECT_TRUE(SetDynamicTableCapacity(500));
EXPECT_EQ(32u * 1024, max_entries());
// Dynamic table capacity cannot exceed maximum dynamic table capacity.
EXPECT_FALSE(
SetDynamicTableCapacity(2 * kMaximumDynamicTableCapacityForTesting));
}
TEST_F(QpackHeaderTableTest, EvictByInsertion) {
EXPECT_TRUE(SetDynamicTableCapacity(40));
// Entry size is 3 + 3 + 32 = 38.
InsertEntry("foo", "bar");
EXPECT_EQ(1u, inserted_entry_count());
EXPECT_EQ(0u, dropped_entry_count());
ExpectMatch("foo", "bar", QpackHeaderTable::MatchType::kNameAndValue,
/* expected_is_static = */ false, 0u);
// Inserting second entry evicts the first one.
InsertEntry("baz", "qux");
EXPECT_EQ(2u, inserted_entry_count());
EXPECT_EQ(1u, dropped_entry_count());
ExpectNoMatch("foo", "bar");
ExpectMatch("baz", "qux", QpackHeaderTable::MatchType::kNameAndValue,
/* expected_is_static = */ false, 1u);
}
TEST_F(QpackHeaderTableTest, EvictByUpdateTableSize) {
// Entry size is 3 + 3 + 32 = 38.
InsertEntry("foo", "bar");
InsertEntry("baz", "qux");
EXPECT_EQ(2u, inserted_entry_count());
EXPECT_EQ(0u, dropped_entry_count());
ExpectMatch("foo", "bar", QpackHeaderTable::MatchType::kNameAndValue,
/* expected_is_static = */ false, 0u);
ExpectMatch("baz", "qux", QpackHeaderTable::MatchType::kNameAndValue,
/* expected_is_static = */ false, 1u);
EXPECT_TRUE(SetDynamicTableCapacity(40));
EXPECT_EQ(2u, inserted_entry_count());
EXPECT_EQ(1u, dropped_entry_count());
ExpectNoMatch("foo", "bar");
ExpectMatch("baz", "qux", QpackHeaderTable::MatchType::kNameAndValue,
/* expected_is_static = */ false, 1u);
EXPECT_TRUE(SetDynamicTableCapacity(20));
EXPECT_EQ(2u, inserted_entry_count());
EXPECT_EQ(2u, dropped_entry_count());
ExpectNoMatch("foo", "bar");
ExpectNoMatch("baz", "qux");
}
TEST_F(QpackHeaderTableTest, EvictOldestOfIdentical) {
EXPECT_TRUE(SetDynamicTableCapacity(80));
// Entry size is 3 + 3 + 32 = 38.
// Insert same entry twice.
InsertEntry("foo", "bar");
InsertEntry("foo", "bar");
EXPECT_EQ(2u, inserted_entry_count());
EXPECT_EQ(0u, dropped_entry_count());
// Find most recently inserted entry.
ExpectMatch("foo", "bar", QpackHeaderTable::MatchType::kNameAndValue,
/* expected_is_static = */ false, 1u);
// Inserting third entry evicts the first one, not the second.
InsertEntry("baz", "qux");
EXPECT_EQ(3u, inserted_entry_count());
EXPECT_EQ(1u, dropped_entry_count());
ExpectMatch("foo", "bar", QpackHeaderTable::MatchType::kNameAndValue,
/* expected_is_static = */ false, 1u);
ExpectMatch("baz", "qux", QpackHeaderTable::MatchType::kNameAndValue,
/* expected_is_static = */ false, 2u);
}
TEST_F(QpackHeaderTableTest, EvictOldestOfSameName) {
EXPECT_TRUE(SetDynamicTableCapacity(80));
// Entry size is 3 + 3 + 32 = 38.
// Insert two entries with same name but different values.
InsertEntry("foo", "bar");
InsertEntry("foo", "baz");
EXPECT_EQ(2u, inserted_entry_count());
EXPECT_EQ(0u, dropped_entry_count());
// Find most recently inserted entry with matching name.
ExpectMatch("foo", "foo", QpackHeaderTable::MatchType::kName,
/* expected_is_static = */ false, 1u);
// Inserting third entry evicts the first one, not the second.
InsertEntry("baz", "qux");
EXPECT_EQ(3u, inserted_entry_count());
EXPECT_EQ(1u, dropped_entry_count());
ExpectMatch("foo", "foo", QpackHeaderTable::MatchType::kName,
/* expected_is_static = */ false, 1u);
ExpectMatch("baz", "qux", QpackHeaderTable::MatchType::kNameAndValue,
/* expected_is_static = */ false, 2u);
}
// Returns the size of the largest entry that could be inserted into the
// dynamic table without evicting entry |index|.
TEST_F(QpackHeaderTableTest, MaxInsertSizeWithoutEvictingGivenEntry) {
const uint64_t dynamic_table_capacity = 100;
QpackHeaderTable table;
table.SetMaximumDynamicTableCapacity(dynamic_table_capacity);
EXPECT_TRUE(table.SetDynamicTableCapacity(dynamic_table_capacity));
// Empty table can take an entry up to its capacity.
EXPECT_EQ(dynamic_table_capacity,
table.MaxInsertSizeWithoutEvictingGivenEntry(0));
const uint64_t entry_size1 = QpackEntry::Size("foo", "bar");
table.InsertEntry("foo", "bar");
EXPECT_EQ(dynamic_table_capacity - entry_size1,
table.MaxInsertSizeWithoutEvictingGivenEntry(0));
// Table can take an entry up to its capacity if all entries are allowed to be
// evicted.
EXPECT_EQ(dynamic_table_capacity,
table.MaxInsertSizeWithoutEvictingGivenEntry(1));
const uint64_t entry_size2 = QpackEntry::Size("baz", "foobar");
table.InsertEntry("baz", "foobar");
// Table can take an entry up to its capacity if all entries are allowed to be
// evicted.
EXPECT_EQ(dynamic_table_capacity,
table.MaxInsertSizeWithoutEvictingGivenEntry(2));
// Second entry must stay.
EXPECT_EQ(dynamic_table_capacity - entry_size2,
table.MaxInsertSizeWithoutEvictingGivenEntry(1));
// First and second entry must stay.
EXPECT_EQ(dynamic_table_capacity - entry_size2 - entry_size1,
table.MaxInsertSizeWithoutEvictingGivenEntry(0));
// Third entry evicts first one.
const uint64_t entry_size3 = QpackEntry::Size("last", "entry");
table.InsertEntry("last", "entry");
EXPECT_EQ(1u, table.dropped_entry_count());
// Table can take an entry up to its capacity if all entries are allowed to be
// evicted.
EXPECT_EQ(dynamic_table_capacity,
table.MaxInsertSizeWithoutEvictingGivenEntry(3));
// Third entry must stay.
EXPECT_EQ(dynamic_table_capacity - entry_size3,
table.MaxInsertSizeWithoutEvictingGivenEntry(2));
// Second and third entry must stay.
EXPECT_EQ(dynamic_table_capacity - entry_size3 - entry_size2,
table.MaxInsertSizeWithoutEvictingGivenEntry(1));
}
TEST_F(QpackHeaderTableTest, RegisterObserver) {
StrictMock<MockObserver> observer1;
RegisterObserver(1, &observer1);
EXPECT_CALL(observer1, OnInsertCountReachedThreshold);
InsertEntry("foo", "bar");
EXPECT_EQ(1u, inserted_entry_count());
Mock::VerifyAndClearExpectations(&observer1);
// Registration order does not matter.
StrictMock<MockObserver> observer2;
StrictMock<MockObserver> observer3;
RegisterObserver(3, &observer3);
RegisterObserver(2, &observer2);
EXPECT_CALL(observer2, OnInsertCountReachedThreshold);
InsertEntry("foo", "bar");
EXPECT_EQ(2u, inserted_entry_count());
Mock::VerifyAndClearExpectations(&observer3);
EXPECT_CALL(observer3, OnInsertCountReachedThreshold);
InsertEntry("foo", "bar");
EXPECT_EQ(3u, inserted_entry_count());
Mock::VerifyAndClearExpectations(&observer2);
// Multiple observers with identical |required_insert_count| should all be
// notified.
StrictMock<MockObserver> observer4;
StrictMock<MockObserver> observer5;
RegisterObserver(4, &observer4);
RegisterObserver(4, &observer5);
EXPECT_CALL(observer4, OnInsertCountReachedThreshold);
EXPECT_CALL(observer5, OnInsertCountReachedThreshold);
InsertEntry("foo", "bar");
EXPECT_EQ(4u, inserted_entry_count());
Mock::VerifyAndClearExpectations(&observer4);
Mock::VerifyAndClearExpectations(&observer5);
}
TEST_F(QpackHeaderTableTest, UnregisterObserver) {
StrictMock<MockObserver> observer1;
StrictMock<MockObserver> observer2;
StrictMock<MockObserver> observer3;
StrictMock<MockObserver> observer4;
RegisterObserver(1, &observer1);
RegisterObserver(2, &observer2);
RegisterObserver(2, &observer3);
RegisterObserver(3, &observer4);
UnregisterObserver(2, &observer3);
EXPECT_CALL(observer1, OnInsertCountReachedThreshold);
EXPECT_CALL(observer2, OnInsertCountReachedThreshold);
EXPECT_CALL(observer4, OnInsertCountReachedThreshold);
InsertEntry("foo", "bar");
InsertEntry("foo", "bar");
InsertEntry("foo", "bar");
EXPECT_EQ(3u, inserted_entry_count());
}
TEST_F(QpackHeaderTableTest, DrainingIndex) {
QpackHeaderTable table;
table.SetMaximumDynamicTableCapacity(kMaximumDynamicTableCapacityForTesting);
EXPECT_TRUE(
table.SetDynamicTableCapacity(4 * QpackEntry::Size("foo", "bar")));
// Empty table: no draining entry.
EXPECT_EQ(0u, table.draining_index(0.0));
EXPECT_EQ(0u, table.draining_index(1.0));
// Table with one entry.
table.InsertEntry("foo", "bar");
// Any entry can be referenced if none of the table is draining.
EXPECT_EQ(0u, table.draining_index(0.0));
// No entry can be referenced if all of the table is draining.
EXPECT_EQ(1u, table.draining_index(1.0));
// Table with two entries is at half capacity.
table.InsertEntry("foo", "bar");
// Any entry can be referenced if at most half of the table is draining,
// because current entries only take up half of total capacity.
EXPECT_EQ(0u, table.draining_index(0.0));
EXPECT_EQ(0u, table.draining_index(0.5));
// No entry can be referenced if all of the table is draining.
EXPECT_EQ(2u, table.draining_index(1.0));
// Table with four entries is full.
table.InsertEntry("foo", "bar");
table.InsertEntry("foo", "bar");
// Any entry can be referenced if none of the table is draining.
EXPECT_EQ(0u, table.draining_index(0.0));
// In a full table with identically sized entries, |draining_fraction| of all
// entries are draining.
EXPECT_EQ(2u, table.draining_index(0.5));
// No entry can be referenced if all of the table is draining.
EXPECT_EQ(4u, table.draining_index(1.0));
}
TEST_F(QpackHeaderTableTest, Cancel) {
StrictMock<MockObserver> observer;
auto table = std::make_unique<QpackHeaderTable>();
table->RegisterObserver(1, &observer);
EXPECT_CALL(observer, Cancel);
table.reset();
}
TEST_F(QpackHeaderTableTest, EntryFitsDynamicTableCapacity) {
EXPECT_TRUE(SetDynamicTableCapacity(39));
EXPECT_TRUE(EntryFitsDynamicTableCapacity("foo", "bar"));
EXPECT_TRUE(EntryFitsDynamicTableCapacity("foo", "bar2"));
EXPECT_FALSE(EntryFitsDynamicTableCapacity("foo", "bar12"));
}
} // namespace
} // namespace test
} // namespace quic