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

quic/core/qpack/qpack_blocking_manager.cc

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);

quic/core/qpack/qpack_blocking_manager.h

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_;

quic/core/qpack/qpack_blocking_manager_test.cc

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