Make HpackEntry::insertion_index_ start from 0 for dynamic entries.
Adding a constant offset of 61 does not add any value. The calculation of
the HPACK index (which is 61 for the most recently added entry and growing for
older entries) involves a subtraction in GetByName() and GetByNameAndValue(),
and this offset cancels between total_insertion_ and entry->InsertionIndex(),
that's why that formula does not change with this CL.
Also add a couple of CHECKs involving InsertionIndex() to validate the formula
that will be used in the next CL which removes InsertionIndex().
PiperOrigin-RevId: 363924862
Change-Id: Ieea5a0a906229427f4af2c14f57074cf1e299b63
diff --git a/quic/core/qpack/qpack_header_table.cc b/quic/core/qpack/qpack_header_table.cc
index 36dddfc..9c12524 100644
--- a/quic/core/qpack/qpack_header_table.cc
+++ b/quic/core/qpack/qpack_header_table.cc
@@ -163,10 +163,14 @@
// Initialize to current available capacity.
uint64_t max_insert_size = dynamic_table_capacity_ - dynamic_table_size_;
+ uint64_t entry_index = dropped_entry_count_;
for (const auto& entry : dynamic_entries_) {
+ // TODO(b/182789212): Remove InsertionIndex(), use entry_index instead.
+ QUICHE_CHECK_EQ(entry_index, entry.InsertionIndex());
if (entry.InsertionIndex() >= index) {
break;
}
+ ++entry_index;
max_insert_size += entry.Size();
}
@@ -232,14 +236,18 @@
}
auto it = dynamic_entries_.begin();
+ uint64_t entry_index = dropped_entry_count_;
while (space_above_draining_index < required_space) {
space_above_draining_index += it->Size();
+ QUICHE_CHECK_EQ(entry_index, it->InsertionIndex());
++it;
+ ++entry_index;
if (it == dynamic_entries_.end()) {
return inserted_entry_count();
}
}
+ // TODO(b/182789212): Remove InsertionIndex(), use entry_index instead.
return it->InsertionIndex();
}
@@ -248,11 +256,15 @@
QUICHE_DCHECK(!dynamic_entries_.empty());
QpackEntry* const entry = &dynamic_entries_.front();
- const uint64_t entry_size = entry->Size();
+ const uint64_t entry_size = entry->Size();
QUICHE_DCHECK_GE(dynamic_table_size_, entry_size);
dynamic_table_size_ -= entry_size;
+ // TODO(b/182789212): Remove InsertionIndex(), use dropped_entry_count_
+ // instead.
+ QUICHE_CHECK_EQ(dropped_entry_count_, entry->InsertionIndex());
+
auto index_it = dynamic_index_.find({entry->name(), entry->value()});
// Remove |dynamic_index_| entry only if it points to the same
// QpackEntry in |dynamic_entries_|.
diff --git a/spdy/core/hpack/hpack_entry.h b/spdy/core/hpack/hpack_entry.h
index fb37640..1db5297 100644
--- a/spdy/core/hpack/hpack_entry.h
+++ b/spdy/core/hpack/hpack_entry.h
@@ -43,9 +43,9 @@
class QUICHE_EXPORT_PRIVATE HpackEntry {
public:
// Copies |name| and |value| in the constructor.
- // |insertion_index| is this entry's index in the total set of entries ever
- // inserted into the header table (including static entries). This allows an
- // HpackEntryTable to determine the index of an HpackEntry in O(1) time.
+ // TODO(b/182789212): Remove |insertion_index|.
+ // |insertion_index| starts from 0, separately for static entries and dynamic
+ // entries.
HpackEntry(absl::string_view name,
absl::string_view value,
size_t insertion_index);
@@ -75,8 +75,9 @@
std::string name_;
std::string value_;
- // The entry's index in the total set of entries ever inserted into the header
- // table.
+ // TODO(b/182789212): Remove |insertion_index_|.
+ // |insertion_index_| starts from 0, separately for static entries and dynamic
+ // entries.
size_t insertion_index_;
};
diff --git a/spdy/core/hpack/hpack_header_table.cc b/spdy/core/hpack/hpack_header_table.cc
index be8cef9..0f0fafc 100644
--- a/spdy/core/hpack/hpack_header_table.cc
+++ b/spdy/core/hpack/hpack_header_table.cc
@@ -21,7 +21,7 @@
settings_size_bound_(kDefaultHeaderTableSizeSetting),
size_(0),
max_size_(kDefaultHeaderTableSizeSetting),
- total_insertions_(kStaticTableSize) {}
+ dynamic_table_insertions_(0) {}
HpackHeaderTable::~HpackHeaderTable() = default;
@@ -50,7 +50,7 @@
{
NameToEntryMap::const_iterator it = dynamic_name_index_.find(name);
if (it != dynamic_name_index_.end()) {
- return total_insertions_ - it->second->InsertionIndex() +
+ return dynamic_table_insertions_ - it->second->InsertionIndex() +
kStaticTableSize;
}
}
@@ -69,7 +69,7 @@
{
auto it = dynamic_index_.find(query);
if (it != dynamic_index_.end()) {
- return total_insertions_ - it->second->InsertionIndex() +
+ return dynamic_table_insertions_ - it->second->InsertionIndex() +
kStaticTableSize;
}
}
@@ -125,6 +125,9 @@
for (size_t i = 0; i != count; ++i) {
QUICHE_CHECK(!dynamic_entries_.empty());
HpackEntry* entry = &dynamic_entries_.back();
+ // TODO(b/182789212): Remove InsertionIndex().
+ QUICHE_CHECK_EQ(dynamic_table_insertions_ - dynamic_entries_.size(),
+ entry->InsertionIndex());
size_ -= entry->Size();
auto it = dynamic_index_.find({entry->name(), entry->value()});
@@ -161,7 +164,7 @@
QUICHE_DCHECK_EQ(0u, size_);
return nullptr;
}
- dynamic_entries_.emplace_front(name, value, total_insertions_);
+ dynamic_entries_.emplace_front(name, value, dynamic_table_insertions_);
HpackEntry* new_entry = &dynamic_entries_.front();
auto index_result = dynamic_index_.insert(std::make_pair(
HpackLookupEntry{new_entry->name(), new_entry->value()}, new_entry));
@@ -196,7 +199,7 @@
}
size_ += entry_size;
- ++total_insertions_;
+ ++dynamic_table_insertions_;
return &dynamic_entries_.front();
}
diff --git a/spdy/core/hpack/hpack_header_table.h b/spdy/core/hpack/hpack_header_table.h
index d82676e..1022d11 100644
--- a/spdy/core/hpack/hpack_header_table.h
+++ b/spdy/core/hpack/hpack_header_table.h
@@ -153,9 +153,9 @@
size_t size_;
size_t max_size_;
- // Total number of table insertions which have occurred,
- // including initial static table insertions.
- size_t total_insertions_;
+ // Total number of dynamic table insertions so far
+ // (including entries that have been evicted).
+ size_t dynamic_table_insertions_;
};
} // namespace spdy
diff --git a/spdy/core/hpack/hpack_header_table_test.cc b/spdy/core/hpack/hpack_header_table_test.cc
index 8dc6c3d..78d22cc 100644
--- a/spdy/core/hpack/hpack_header_table_test.cc
+++ b/spdy/core/hpack/hpack_header_table_test.cc
@@ -31,6 +31,7 @@
const HpackHeaderTable::EntryTable& static_entries() {
return table_->static_entries_;
}
+ // TODO(b/182789212): Remove this method, because it does not add any value.
size_t index_size() {
return table_->static_index_.size() + table_->dynamic_index_.size();
}
@@ -44,7 +45,10 @@
}
return result;
}
- size_t total_insertions() { return table_->total_insertions_; }
+ size_t dynamic_table_insertions() {
+ return table_->dynamic_table_insertions_;
+ }
+ // TODO(b/182789212): Inline this method.
size_t dynamic_entries_count() { return table_->dynamic_entries_.size(); }
size_t EvictionCountForEntry(absl::string_view name,
absl::string_view value) {
@@ -127,10 +131,10 @@
EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound());
EXPECT_EQ(0u, peer_.dynamic_entries_count());
- EXPECT_EQ(peer_.static_entries().size(), peer_.total_insertions());
+ EXPECT_EQ(0u, peer_.dynamic_table_insertions());
// Static entries have been populated and inserted into the table & index.
- EXPECT_NE(0u, peer_.static_entries().size());
+ EXPECT_EQ(kStaticTableSize, peer_.static_entries().size());
EXPECT_EQ(peer_.index_size(), peer_.static_entries().size());
for (size_t i = 0; i != peer_.static_entries().size(); ++i) {
const HpackEntry* entry = &peer_.static_entries()[i];
@@ -142,8 +146,6 @@
}
TEST_F(HpackHeaderTableTest, BasicDynamicEntryInsertionAndEviction) {
- size_t static_count = peer_.total_insertions();
-
const HpackEntry* first_static_entry = table_.GetByIndex(1);
EXPECT_EQ(first_static_entry, table_.GetByIndex(1));
@@ -155,8 +157,7 @@
EXPECT_EQ(entry->Size(), table_.size());
EXPECT_EQ(1u, peer_.dynamic_entries_count());
EXPECT_EQ(peer_.dynamic_entries().size(), peer_.dynamic_entries_count());
- EXPECT_EQ(static_count + 1, peer_.total_insertions());
- EXPECT_EQ(static_count + 1, peer_.index_size());
+ EXPECT_EQ(kStaticTableSize + 1, peer_.index_size());
EXPECT_EQ(entry, table_.GetByIndex(62));
@@ -168,8 +169,7 @@
EXPECT_EQ(0u, table_.size());
EXPECT_EQ(0u, peer_.dynamic_entries_count());
EXPECT_EQ(peer_.dynamic_entries().size(), peer_.dynamic_entries_count());
- EXPECT_EQ(static_count + 1, peer_.total_insertions());
- EXPECT_EQ(static_count, peer_.index_size());
+ EXPECT_EQ(kStaticTableSize, peer_.index_size());
// Index of |first_static_entry| does not change.
EXPECT_EQ(first_static_entry, table_.GetByIndex(1));
