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