Track unacknowledged references on the encoder stream in QpackBlockingManager.
gfe-relnote: n/a, change to QUIC v99-only code. Protected by existing disabled gfe2_reloadable_flag_quic_enable_version_99.
PiperOrigin-RevId: 263116461
Change-Id: I928d3b06dfbc8de7ad8995b739f49c65856237b2
diff --git a/quic/core/qpack/qpack_blocking_manager.cc b/quic/core/qpack/qpack_blocking_manager.cc
index e8e4f87..04d824f 100644
--- a/quic/core/qpack/qpack_blocking_manager.cc
+++ b/quic/core/qpack/qpack_blocking_manager.cc
@@ -23,7 +23,7 @@
const uint64_t required_index_count = RequiredInsertCount(indices);
if (known_received_count_ < required_index_count) {
- known_received_count_ = required_index_count;
+ IncreaseKnownReceivedCountTo(required_index_count);
}
DecreaseReferenceCounts(indices);
@@ -50,7 +50,7 @@
}
void QpackBlockingManager::OnInsertCountIncrement(uint64_t increment) {
- known_received_count_ += increment;
+ IncreaseKnownReceivedCountTo(known_received_count_ + increment);
}
void QpackBlockingManager::OnHeaderBlockSent(QuicStreamId stream_id,
@@ -61,6 +61,16 @@
header_blocks_[stream_id].push_back(std::move(indices));
}
+void QpackBlockingManager::OnReferenceSentOnEncoderStream(
+ uint64_t inserted_index,
+ uint64_t referred_index) {
+ auto result = unacked_encoder_stream_references_.insert(
+ {inserted_index, referred_index});
+ // Each dynamic table entry can refer to at most one |referred_index|.
+ DCHECK(result.second);
+ IncreaseReferenceCounts({referred_index});
+}
+
uint64_t QpackBlockingManager::blocked_stream_count() const {
uint64_t blocked_stream_count = 0;
for (const auto& header_blocks_for_stream : header_blocks_) {
@@ -86,6 +96,26 @@
return *indices.rbegin() + 1;
}
+void QpackBlockingManager::IncreaseKnownReceivedCountTo(
+ uint64_t new_known_received_count) {
+ DCHECK_GT(new_known_received_count, known_received_count_);
+
+ known_received_count_ = new_known_received_count;
+
+ // Remove referred indices with key less than new Known Received Count from
+ // |unacked_encoder_stream_references_| and |entry_reference_counts_|.
+ IndexSet acknowledged_references;
+ auto it = unacked_encoder_stream_references_.begin();
+ while (it != unacked_encoder_stream_references_.end() &&
+ it->first < known_received_count_) {
+ acknowledged_references.insert(it->second);
+ ++it;
+ }
+ unacked_encoder_stream_references_.erase(
+ unacked_encoder_stream_references_.begin(), it);
+ DecreaseReferenceCounts(acknowledged_references);
+}
+
void QpackBlockingManager::IncreaseReferenceCounts(const IndexSet& indices) {
for (const uint64_t index : indices) {
auto it = entry_reference_counts_.lower_bound(index);
diff --git a/quic/core/qpack/qpack_blocking_manager.h b/quic/core/qpack/qpack_blocking_manager.h
index 00669af..7acfd5a 100644
--- a/quic/core/qpack/qpack_blocking_manager.h
+++ b/quic/core/qpack/qpack_blocking_manager.h
@@ -41,6 +41,12 @@
// entries with |indices|. |indices| must not be empty.
void OnHeaderBlockSent(QuicStreamId stream_id, IndexSet indices);
+ // Called when sending Insert With Name Reference or Duplicate instruction on
+ // encoder stream, inserting entry |inserted_index| referring to
+ // |referred_index|.
+ void OnReferenceSentOnEncoderStream(uint64_t inserted_index,
+ uint64_t referred_index);
+
// Returns the number of blocked streams.
uint64_t blocked_stream_count() const;
@@ -64,6 +70,11 @@
using HeaderBlocksForStream = std::list<IndexSet>;
using HeaderBlocks = QuicUnorderedMap<QuicStreamId, HeaderBlocksForStream>;
+ // Increases |known_received_count_| to |new_known_received_count|, which must
+ // me larger than |known_received_count_|. Removes acknowledged references
+ // from |unacked_encoder_stream_references_|.
+ void IncreaseKnownReceivedCountTo(uint64_t new_known_received_count);
+
// Increase or decrease the reference count for each index in |indices|.
void IncreaseReferenceCounts(const IndexSet& indices);
void DecreaseReferenceCounts(const IndexSet& indices);
@@ -72,7 +83,13 @@
// Must not contain a stream id with an empty queue.
HeaderBlocks header_blocks_;
- // Number of references in |header_blocks_| for each entry index.
+ // Unacknowledged references on the encoder stream.
+ // The key is the absolute index of the inserted entry,
+ // the mapped value is the absolute index of the entry referred.
+ std::map<uint64_t, uint64_t> unacked_encoder_stream_references_;
+
+ // Number of references in |header_blocks_| and
+ // |unacked_encoder_stream_references_| for each entry index.
std::map<uint64_t, uint64_t> entry_reference_counts_;
uint64_t known_received_count_;
diff --git a/quic/core/qpack/qpack_blocking_manager_test.cc b/quic/core/qpack/qpack_blocking_manager_test.cc
index a7cba73..6f78d87 100644
--- a/quic/core/qpack/qpack_blocking_manager_test.cc
+++ b/quic/core/qpack/qpack_blocking_manager_test.cc
@@ -206,6 +206,88 @@
manager_.smallest_blocking_index());
}
+TEST_F(QpackBlockingManagerTest,
+ ReferenceOnEncoderStreamUnblockedByInsertCountIncrement) {
+ EXPECT_EQ(0u, manager_.known_received_count());
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ manager_.smallest_blocking_index());
+
+ // Entry 1 refers to entry 0.
+ manager_.OnReferenceSentOnEncoderStream(1, 0);
+ // Entry 2 also refers to entry 0.
+ manager_.OnReferenceSentOnEncoderStream(2, 0);
+
+ EXPECT_EQ(0u, manager_.known_received_count());
+ EXPECT_EQ(0u, manager_.smallest_blocking_index());
+
+ // Acknowledging entry 1 still leaves one unacknowledged reference to entry 0.
+ manager_.OnInsertCountIncrement(2);
+
+ EXPECT_EQ(2u, manager_.known_received_count());
+ EXPECT_EQ(0u, manager_.smallest_blocking_index());
+
+ // Entry 3 also refers to entry 2.
+ manager_.OnReferenceSentOnEncoderStream(3, 2);
+
+ EXPECT_EQ(2u, manager_.known_received_count());
+ EXPECT_EQ(0u, manager_.smallest_blocking_index());
+
+ // Acknowledging entry 2 removes last reference to entry 0.
+ manager_.OnInsertCountIncrement(1);
+
+ EXPECT_EQ(3u, manager_.known_received_count());
+ EXPECT_EQ(2u, manager_.smallest_blocking_index());
+
+ // Acknowledging entry 4 (and implicitly 3) removes reference to entry 2.
+ manager_.OnInsertCountIncrement(2);
+
+ EXPECT_EQ(5u, manager_.known_received_count());
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ manager_.smallest_blocking_index());
+}
+
+TEST_F(QpackBlockingManagerTest,
+ ReferenceOnEncoderStreamUnblockedByHeaderAcknowledgement) {
+ EXPECT_EQ(0u, manager_.known_received_count());
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ manager_.smallest_blocking_index());
+
+ // Entry 1 refers to entry 0.
+ manager_.OnReferenceSentOnEncoderStream(1, 0);
+ // Entry 2 also refers to entry 0.
+ manager_.OnReferenceSentOnEncoderStream(2, 0);
+
+ EXPECT_EQ(0u, manager_.known_received_count());
+ EXPECT_EQ(0u, manager_.smallest_blocking_index());
+
+ // Acknowledging a header block with entries up to 1 still leave one
+ // unacknowledged reference to entry 0.
+ manager_.OnHeaderBlockSent(/* stream_id = */ 0, {0, 1});
+ manager_.OnHeaderAcknowledgement(/* stream_id = */ 0);
+
+ EXPECT_EQ(2u, manager_.known_received_count());
+ EXPECT_EQ(0u, manager_.smallest_blocking_index());
+
+ // Entry 3 also refers to entry 2.
+ manager_.OnReferenceSentOnEncoderStream(3, 2);
+
+ // Acknowledging a header block with entries up to 2 removes last reference to
+ // entry 0.
+ manager_.OnHeaderBlockSent(/* stream_id = */ 0, {2, 0, 2});
+ manager_.OnHeaderAcknowledgement(/* stream_id = */ 0);
+
+ EXPECT_EQ(3u, manager_.known_received_count());
+ EXPECT_EQ(2u, manager_.smallest_blocking_index());
+
+ // Acknowledging entry 4 (and implicitly 3) removes reference to entry 2.
+ manager_.OnHeaderBlockSent(/* stream_id = */ 0, {1, 4, 2, 0});
+ manager_.OnHeaderAcknowledgement(/* stream_id = */ 0);
+
+ EXPECT_EQ(5u, manager_.known_received_count());
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ manager_.smallest_blocking_index());
+}
+
} // namespace
} // namespace test
} // namespace quic
