Add QpackBlockingManager to track blocked streams and blocking entries.
gfe-relnote: n/a, change to QUIC v99-only code. Protected by existing disabled gfe2_reloadable_flag_quic_enable_version_99.
PiperOrigin-RevId: 260829566
Change-Id: I3f2f74384f213f3dfea8460a77f759b070a7d79c
diff --git a/quic/core/qpack/qpack_blocking_manager.cc b/quic/core/qpack/qpack_blocking_manager.cc
new file mode 100644
index 0000000..e8e4f87
--- /dev/null
+++ b/quic/core/qpack/qpack_blocking_manager.cc
@@ -0,0 +1,114 @@
+// Copyright (c) 2019 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 "net/third_party/quiche/src/quic/core/qpack/qpack_blocking_manager.h"
+
+#include <utility>
+
+namespace quic {
+
+QpackBlockingManager::QpackBlockingManager() : known_received_count_(0) {}
+
+bool QpackBlockingManager::OnHeaderAcknowledgement(QuicStreamId stream_id) {
+ auto it = header_blocks_.find(stream_id);
+ if (it == header_blocks_.end()) {
+ return false;
+ }
+
+ DCHECK(!it->second.empty());
+
+ const IndexSet& indices = it->second.front();
+ DCHECK(!indices.empty());
+
+ const uint64_t required_index_count = RequiredInsertCount(indices);
+ if (known_received_count_ < required_index_count) {
+ known_received_count_ = required_index_count;
+ }
+
+ DecreaseReferenceCounts(indices);
+
+ it->second.pop_front();
+ if (it->second.empty()) {
+ header_blocks_.erase(it);
+ }
+
+ return true;
+}
+
+void QpackBlockingManager::OnStreamCancellation(QuicStreamId stream_id) {
+ auto it = header_blocks_.find(stream_id);
+ if (it == header_blocks_.end()) {
+ return;
+ }
+
+ for (const IndexSet& indices : it->second) {
+ DecreaseReferenceCounts(indices);
+ }
+
+ header_blocks_.erase(it);
+}
+
+void QpackBlockingManager::OnInsertCountIncrement(uint64_t increment) {
+ known_received_count_ += increment;
+}
+
+void QpackBlockingManager::OnHeaderBlockSent(QuicStreamId stream_id,
+ IndexSet indices) {
+ DCHECK(!indices.empty());
+
+ IncreaseReferenceCounts(indices);
+ header_blocks_[stream_id].push_back(std::move(indices));
+}
+
+uint64_t QpackBlockingManager::blocked_stream_count() const {
+ uint64_t blocked_stream_count = 0;
+ for (const auto& header_blocks_for_stream : header_blocks_) {
+ for (const IndexSet& indices : header_blocks_for_stream.second) {
+ if (RequiredInsertCount(indices) > known_received_count_) {
+ ++blocked_stream_count;
+ break;
+ }
+ }
+ }
+
+ return blocked_stream_count;
+}
+
+uint64_t QpackBlockingManager::smallest_blocking_index() const {
+ return entry_reference_counts_.empty()
+ ? std::numeric_limits<uint64_t>::max()
+ : entry_reference_counts_.begin()->first;
+}
+
+// static
+uint64_t QpackBlockingManager::RequiredInsertCount(const IndexSet& indices) {
+ return *indices.rbegin() + 1;
+}
+
+void QpackBlockingManager::IncreaseReferenceCounts(const IndexSet& indices) {
+ for (const uint64_t index : indices) {
+ auto it = entry_reference_counts_.lower_bound(index);
+ if (it != entry_reference_counts_.end() && it->first == index) {
+ ++it->second;
+ } else {
+ entry_reference_counts_.insert(it, {index, 1});
+ }
+ }
+}
+
+void QpackBlockingManager::DecreaseReferenceCounts(const IndexSet& indices) {
+ for (const uint64_t index : indices) {
+ auto it = entry_reference_counts_.find(index);
+ DCHECK(it != entry_reference_counts_.end());
+ DCHECK_NE(0u, it->second);
+
+ if (it->second == 1) {
+ entry_reference_counts_.erase(it);
+ } else {
+ --it->second;
+ }
+ }
+}
+
+} // namespace quic
diff --git a/quic/core/qpack/qpack_blocking_manager.h b/quic/core/qpack/qpack_blocking_manager.h
new file mode 100644
index 0000000..3834d92
--- /dev/null
+++ b/quic/core/qpack/qpack_blocking_manager.h
@@ -0,0 +1,78 @@
+// Copyright (c) 2019 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.
+
+#ifndef QUICHE_QUIC_CORE_QPACK_QPACK_BLOCKING_MANAGER_H_
+#define QUICHE_QUIC_CORE_QPACK_QPACK_BLOCKING_MANAGER_H_
+
+#include <cstdint>
+#include <map>
+#include <set>
+
+#include "net/third_party/quiche/src/quic/core/quic_types.h"
+#include "net/third_party/quiche/src/quic/platform/api/quic_containers.h"
+#include "net/third_party/quiche/src/quic/platform/api/quic_export.h"
+
+namespace quic {
+
+// Class to keep track of blocked streams and blocking dynamic table entries:
+// https://quicwg.org/base-drafts/draft-ietf-quic-qpack.html#blocked-decoding
+// https://quicwg.org/base-drafts/draft-ietf-quic-qpack.html#blocked-insertion
+class QUIC_EXPORT_PRIVATE QpackBlockingManager {
+ public:
+ using IndexSet = std::multiset<uint64_t>;
+
+ QpackBlockingManager();
+
+ // Called when a Header Acknowledgement instruction is received on the decoder
+ // stream. Returns false if there are no outstanding header blocks to be
+ // acknowledged on |stream_id|.
+ bool OnHeaderAcknowledgement(QuicStreamId stream_id);
+
+ // Called when a Stream Cancellation instruction is received on the decoder
+ // stream.
+ void OnStreamCancellation(QuicStreamId stream_id);
+
+ // Called when an Insert Count Increment instruction is received on the
+ // decoder stream.
+ void OnInsertCountIncrement(uint64_t increment);
+
+ // Called when sending a header block containing references to dynamic table
+ // entries with |indices|. |indices| must not be empty.
+ void OnHeaderBlockSent(QuicStreamId stream_id, IndexSet indices);
+
+ // Returns the number of blocked streams.
+ uint64_t blocked_stream_count() const;
+
+ // Returns the index of the blocking entry with the smallest index,
+ // or std::numeric_limits<uint64_t>::max() if there are no blocking entries.
+ uint64_t smallest_blocking_index() const;
+
+ // Returns the Known Received Count as defined at
+ // https://quicwg.org/base-drafts/draft-ietf-quic-qpack.html#known-received-count.
+ uint64_t known_received_count() const { return known_received_count_; }
+
+ // Required Insert Count for set of indices.
+ static uint64_t RequiredInsertCount(const IndexSet& indices);
+
+ private:
+ using HeaderBlocksForStream = QuicDeque<IndexSet>;
+ using HeaderBlocks = QuicUnorderedMap<QuicStreamId, HeaderBlocksForStream>;
+
+ // Increase or decrease the reference count for each index in |indices|.
+ void IncreaseReferenceCounts(const IndexSet& indices);
+ void DecreaseReferenceCounts(const IndexSet& indices);
+
+ // Multiset of indices in each header block for each stream.
+ // Must not contain a stream id with an empty queue.
+ HeaderBlocks header_blocks_;
+
+ // Number of references in |header_blocks_| for each entry index.
+ std::map<uint64_t, uint64_t> entry_reference_counts_;
+
+ uint64_t known_received_count_;
+};
+
+} // namespace quic
+
+#endif // QUICHE_QUIC_CORE_QPACK_QPACK_BLOCKING_MANAGER_H_
diff --git a/quic/core/qpack/qpack_blocking_manager_test.cc b/quic/core/qpack/qpack_blocking_manager_test.cc
new file mode 100644
index 0000000..a7cba73
--- /dev/null
+++ b/quic/core/qpack/qpack_blocking_manager_test.cc
@@ -0,0 +1,211 @@
+// Copyright (c) 2019 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 "net/third_party/quiche/src/quic/core/qpack/qpack_blocking_manager.h"
+
+#include "net/third_party/quiche/src/quic/platform/api/quic_test.h"
+
+namespace quic {
+namespace test {
+namespace {
+
+class QpackBlockingManagerTest : public QuicTest {
+ protected:
+ QpackBlockingManagerTest() = default;
+ ~QpackBlockingManagerTest() override = default;
+
+ QpackBlockingManager manager_;
+};
+
+TEST_F(QpackBlockingManagerTest, Empty) {
+ EXPECT_EQ(0u, manager_.blocked_stream_count());
+ EXPECT_EQ(0u, manager_.known_received_count());
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ manager_.smallest_blocking_index());
+
+ EXPECT_FALSE(manager_.OnHeaderAcknowledgement(0));
+ EXPECT_FALSE(manager_.OnHeaderAcknowledgement(1));
+}
+
+TEST_F(QpackBlockingManagerTest, NotBlockedByInsertCountIncrement) {
+ manager_.OnInsertCountIncrement(2);
+
+ // Stream 0 is not blocked, because it only references entries that are
+ // already acknowledged by an Insert Count Increment instruction.
+ manager_.OnHeaderBlockSent(0, {1, 0});
+ EXPECT_EQ(0u, manager_.blocked_stream_count());
+}
+
+TEST_F(QpackBlockingManagerTest, UnblockedByInsertCountIncrement) {
+ manager_.OnHeaderBlockSent(0, {1, 0});
+ EXPECT_EQ(1u, manager_.blocked_stream_count());
+
+ manager_.OnInsertCountIncrement(2);
+ EXPECT_EQ(0u, manager_.blocked_stream_count());
+}
+
+TEST_F(QpackBlockingManagerTest, NotBlockedByHeaderAcknowledgement) {
+ manager_.OnHeaderBlockSent(0, {2, 1, 1});
+ EXPECT_EQ(1u, manager_.blocked_stream_count());
+
+ EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
+ EXPECT_EQ(0u, manager_.blocked_stream_count());
+
+ // Stream 1 is not blocked, because it only references entries that are
+ // already acknowledged by a Header Acknowledgement instruction.
+ manager_.OnHeaderBlockSent(1, {2, 2});
+ EXPECT_EQ(0u, manager_.blocked_stream_count());
+}
+
+TEST_F(QpackBlockingManagerTest, UnblockedByHeaderAcknowledgement) {
+ manager_.OnHeaderBlockSent(0, {2, 1, 1});
+ manager_.OnHeaderBlockSent(1, {2, 2});
+ EXPECT_EQ(2u, manager_.blocked_stream_count());
+
+ EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
+ EXPECT_EQ(0u, manager_.blocked_stream_count());
+}
+
+TEST_F(QpackBlockingManagerTest, KnownReceivedCount) {
+ EXPECT_EQ(0u, manager_.known_received_count());
+
+ // Sending a header block does not change Known Received Count.
+ manager_.OnHeaderBlockSent(0, {0});
+ EXPECT_EQ(0u, manager_.known_received_count());
+
+ manager_.OnHeaderBlockSent(1, {1});
+ EXPECT_EQ(0u, manager_.known_received_count());
+
+ // Header Acknowledgement might increase Known Received Count.
+ EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
+ EXPECT_EQ(1u, manager_.known_received_count());
+
+ manager_.OnHeaderBlockSent(2, {5});
+ EXPECT_EQ(1u, manager_.known_received_count());
+
+ EXPECT_TRUE(manager_.OnHeaderAcknowledgement(1));
+ EXPECT_EQ(2u, manager_.known_received_count());
+
+ // Insert Count Increment increases Known Received Count.
+ manager_.OnInsertCountIncrement(2);
+ EXPECT_EQ(4u, manager_.known_received_count());
+
+ EXPECT_TRUE(manager_.OnHeaderAcknowledgement(2));
+ EXPECT_EQ(6u, manager_.known_received_count());
+
+ // Stream Cancellation does not change Known Received Count.
+ manager_.OnStreamCancellation(0);
+ EXPECT_EQ(6u, manager_.known_received_count());
+
+ // Header Acknowledgement of a block with smaller Required Insert Count does
+ // not increase Known Received Count.
+ manager_.OnHeaderBlockSent(0, {3});
+ EXPECT_EQ(6u, manager_.known_received_count());
+
+ EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
+ EXPECT_EQ(6u, manager_.known_received_count());
+
+ // Header Acknowledgement of a block with equal Required Insert Count does not
+ // increase Known Received Count.
+ manager_.OnHeaderBlockSent(1, {5});
+ EXPECT_EQ(6u, manager_.known_received_count());
+
+ EXPECT_TRUE(manager_.OnHeaderAcknowledgement(1));
+ EXPECT_EQ(6u, manager_.known_received_count());
+}
+
+TEST_F(QpackBlockingManagerTest, SmallestBlockingIndex) {
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ manager_.smallest_blocking_index());
+
+ manager_.OnHeaderBlockSent(0, {0});
+ EXPECT_EQ(0u, manager_.smallest_blocking_index());
+
+ manager_.OnHeaderBlockSent(1, {2});
+ EXPECT_EQ(0u, manager_.smallest_blocking_index());
+
+ EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
+ EXPECT_EQ(2u, manager_.smallest_blocking_index());
+
+ manager_.OnHeaderBlockSent(1, {1});
+ EXPECT_EQ(1u, manager_.smallest_blocking_index());
+
+ EXPECT_TRUE(manager_.OnHeaderAcknowledgement(1));
+ EXPECT_EQ(1u, manager_.smallest_blocking_index());
+
+ // Insert Count Increment does not change smallest blocking index.
+ manager_.OnInsertCountIncrement(2);
+ EXPECT_EQ(1u, manager_.smallest_blocking_index());
+
+ manager_.OnStreamCancellation(1);
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ manager_.smallest_blocking_index());
+}
+
+TEST_F(QpackBlockingManagerTest, HeaderAcknowledgementsOnSingleStream) {
+ EXPECT_EQ(0u, manager_.known_received_count());
+ EXPECT_EQ(0u, manager_.blocked_stream_count());
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ manager_.smallest_blocking_index());
+
+ manager_.OnHeaderBlockSent(0, {2, 1, 1});
+ EXPECT_EQ(0u, manager_.known_received_count());
+ EXPECT_EQ(1u, manager_.blocked_stream_count());
+ EXPECT_EQ(1u, manager_.smallest_blocking_index());
+
+ manager_.OnHeaderBlockSent(0, {1, 0});
+ EXPECT_EQ(0u, manager_.known_received_count());
+ EXPECT_EQ(1u, manager_.blocked_stream_count());
+ EXPECT_EQ(0u, manager_.smallest_blocking_index());
+
+ EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
+ EXPECT_EQ(3u, manager_.known_received_count());
+ EXPECT_EQ(0u, manager_.blocked_stream_count());
+ EXPECT_EQ(0u, manager_.smallest_blocking_index());
+
+ manager_.OnHeaderBlockSent(0, {3});
+ EXPECT_EQ(3u, manager_.known_received_count());
+ EXPECT_EQ(1u, manager_.blocked_stream_count());
+ EXPECT_EQ(0u, manager_.smallest_blocking_index());
+
+ EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
+ EXPECT_EQ(3u, manager_.known_received_count());
+ EXPECT_EQ(1u, manager_.blocked_stream_count());
+ EXPECT_EQ(3u, manager_.smallest_blocking_index());
+
+ EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0));
+ EXPECT_EQ(4u, manager_.known_received_count());
+ EXPECT_EQ(0u, manager_.blocked_stream_count());
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ manager_.smallest_blocking_index());
+
+ EXPECT_FALSE(manager_.OnHeaderAcknowledgement(0));
+}
+
+TEST_F(QpackBlockingManagerTest, CancelStream) {
+ manager_.OnHeaderBlockSent(0, {3});
+ EXPECT_EQ(1u, manager_.blocked_stream_count());
+ EXPECT_EQ(3u, manager_.smallest_blocking_index());
+
+ manager_.OnHeaderBlockSent(0, {2});
+ EXPECT_EQ(1u, manager_.blocked_stream_count());
+ EXPECT_EQ(2u, manager_.smallest_blocking_index());
+
+ manager_.OnHeaderBlockSent(1, {4});
+ EXPECT_EQ(2u, manager_.blocked_stream_count());
+ EXPECT_EQ(2u, manager_.smallest_blocking_index());
+
+ manager_.OnStreamCancellation(0);
+ EXPECT_EQ(1u, manager_.blocked_stream_count());
+ EXPECT_EQ(4u, manager_.smallest_blocking_index());
+
+ manager_.OnStreamCancellation(1);
+ EXPECT_EQ(0u, manager_.blocked_stream_count());
+ EXPECT_EQ(std::numeric_limits<uint64_t>::max(),
+ manager_.smallest_blocking_index());
+}
+
+} // namespace
+} // namespace test
+} // namespace quic
