Add QpackHeaderTable::draining_index().
gfe-relnote: n/a, change to QUIC v99-only code. Protected by existing disabled
gfe2_reloadable_flag_quic_enable_version_99.
PiperOrigin-RevId: 259954990
Change-Id: I896a5b039f2d61e7b4e9f97299b9ebb2234e2820
diff --git a/quic/core/qpack/qpack_header_table.cc b/quic/core/qpack/qpack_header_table.cc
index 6fa6412..92eb072 100644
--- a/quic/core/qpack/qpack_header_table.cc
+++ b/quic/core/qpack/qpack_header_table.cc
@@ -173,6 +173,31 @@
observers_.push({observer, required_insert_count});
}
+uint64_t QpackHeaderTable::draining_index(float draining_fraction) const {
+ DCHECK_LE(0.0, draining_fraction);
+ DCHECK_LE(draining_fraction, 1.0);
+
+ const uint64_t required_space = draining_fraction * dynamic_table_capacity_;
+ uint64_t space_above_draining_index =
+ dynamic_table_capacity_ - dynamic_table_size_;
+
+ if (dynamic_entries_.empty() ||
+ space_above_draining_index >= required_space) {
+ return dropped_entry_count_;
+ }
+
+ auto it = dynamic_entries_.begin();
+ while (space_above_draining_index < required_space) {
+ space_above_draining_index += it->Size();
+ ++it;
+ if (it == dynamic_entries_.end()) {
+ return inserted_entry_count();
+ }
+ }
+
+ return it->InsertionIndex();
+}
+
bool QpackHeaderTable::ObserverWithThreshold::operator>(
const ObserverWithThreshold& other) const {
return required_insert_count > other.required_insert_count;
diff --git a/quic/core/qpack/qpack_header_table.h b/quic/core/qpack/qpack_header_table.h
index 39d7326..54b0829 100644
--- a/quic/core/qpack/qpack_header_table.h
+++ b/quic/core/qpack/qpack_header_table.h
@@ -99,6 +99,14 @@
// The number of entries dropped from the dynamic table.
uint64_t dropped_entry_count() const { return dropped_entry_count_; }
+ // Returns the draining index described at
+ // https://quicwg.org/base-drafts/draft-ietf-quic-qpack.html#avoiding-blocked-insertions.
+ // Entries with an index larger than or equal to the draining index take up
+ // approximately |1.0 - draining_fraction| of dynamic table capacity. The
+ // remaining capacity is taken up by draining entries and unused space.
+ // The returned index might not be the index of a valid entry.
+ uint64_t draining_index(float draining_fraction) const;
+
private:
// Evict entries from the dynamic table until table size is less than or equal
// to current value of |dynamic_table_capacity_|.
diff --git a/quic/core/qpack/qpack_header_table_test.cc b/quic/core/qpack/qpack_header_table_test.cc
index ff7ef48..7d1044b 100644
--- a/quic/core/qpack/qpack_header_table_test.cc
+++ b/quic/core/qpack/qpack_header_table_test.cc
@@ -404,6 +404,42 @@
Mock::VerifyAndClearExpectations(&observer5);
}
+TEST_F(QpackHeaderTableTest, DrainingIndex) {
+ QpackHeaderTable table;
+ table.SetMaximumDynamicTableCapacity(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.
+ EXPECT_TRUE(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.
+ EXPECT_TRUE(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.
+ EXPECT_TRUE(table.InsertEntry("foo", "bar"));
+ EXPECT_TRUE(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));
+}
+
} // namespace
} // namespace test
} // namespace quic
