No public description PiperOrigin-RevId: 688315629
diff --git a/build/source_list.bzl b/build/source_list.bzl index 4f150d5..36c38a7 100644 --- a/build/source_list.bzl +++ b/build/source_list.bzl
@@ -271,7 +271,9 @@ "quic/core/proto/cached_network_parameters_proto.h", "quic/core/proto/crypto_server_config_proto.h", "quic/core/proto/source_address_token_proto.h", + "quic/core/qpack/new_qpack_blocking_manager.h", "quic/core/qpack/qpack_blocking_manager.h", + "quic/core/qpack/qpack_blocking_manager_shim.h", "quic/core/qpack/qpack_decoded_headers_accumulator.h", "quic/core/qpack/qpack_decoder.h", "quic/core/qpack/qpack_decoder_stream_receiver.h", @@ -604,6 +606,7 @@ "quic/core/http/web_transport_stream_adapter.cc", "quic/core/internet_checksum.cc", "quic/core/legacy_quic_stream_id_manager.cc", + "quic/core/qpack/new_qpack_blocking_manager.cc", "quic/core/qpack/qpack_blocking_manager.cc", "quic/core/qpack/qpack_decoded_headers_accumulator.cc", "quic/core/qpack/qpack_decoder.cc", @@ -1240,6 +1243,7 @@ "quic/core/internet_checksum_test.cc", "quic/core/legacy_quic_stream_id_manager_test.cc", "quic/core/packet_number_indexed_queue_test.cc", + "quic/core/qpack/new_qpack_blocking_manager_test.cc", "quic/core/qpack/qpack_blocking_manager_test.cc", "quic/core/qpack/qpack_decoded_headers_accumulator_test.cc", "quic/core/qpack/qpack_decoder_stream_receiver_test.cc",
diff --git a/build/source_list.gni b/build/source_list.gni index 977a2eb..747ebdb 100644 --- a/build/source_list.gni +++ b/build/source_list.gni
@@ -271,7 +271,9 @@ "src/quiche/quic/core/proto/cached_network_parameters_proto.h", "src/quiche/quic/core/proto/crypto_server_config_proto.h", "src/quiche/quic/core/proto/source_address_token_proto.h", + "src/quiche/quic/core/qpack/new_qpack_blocking_manager.h", "src/quiche/quic/core/qpack/qpack_blocking_manager.h", + "src/quiche/quic/core/qpack/qpack_blocking_manager_shim.h", "src/quiche/quic/core/qpack/qpack_decoded_headers_accumulator.h", "src/quiche/quic/core/qpack/qpack_decoder.h", "src/quiche/quic/core/qpack/qpack_decoder_stream_receiver.h", @@ -604,6 +606,7 @@ "src/quiche/quic/core/http/web_transport_stream_adapter.cc", "src/quiche/quic/core/internet_checksum.cc", "src/quiche/quic/core/legacy_quic_stream_id_manager.cc", + "src/quiche/quic/core/qpack/new_qpack_blocking_manager.cc", "src/quiche/quic/core/qpack/qpack_blocking_manager.cc", "src/quiche/quic/core/qpack/qpack_decoded_headers_accumulator.cc", "src/quiche/quic/core/qpack/qpack_decoder.cc", @@ -1241,6 +1244,7 @@ "src/quiche/quic/core/internet_checksum_test.cc", "src/quiche/quic/core/legacy_quic_stream_id_manager_test.cc", "src/quiche/quic/core/packet_number_indexed_queue_test.cc", + "src/quiche/quic/core/qpack/new_qpack_blocking_manager_test.cc", "src/quiche/quic/core/qpack/qpack_blocking_manager_test.cc", "src/quiche/quic/core/qpack/qpack_decoded_headers_accumulator_test.cc", "src/quiche/quic/core/qpack/qpack_decoder_stream_receiver_test.cc",
diff --git a/build/source_list.json b/build/source_list.json index 0ebf8f2..b651255 100644 --- a/build/source_list.json +++ b/build/source_list.json
@@ -270,7 +270,9 @@ "quiche/quic/core/proto/cached_network_parameters_proto.h", "quiche/quic/core/proto/crypto_server_config_proto.h", "quiche/quic/core/proto/source_address_token_proto.h", + "quiche/quic/core/qpack/new_qpack_blocking_manager.h", "quiche/quic/core/qpack/qpack_blocking_manager.h", + "quiche/quic/core/qpack/qpack_blocking_manager_shim.h", "quiche/quic/core/qpack/qpack_decoded_headers_accumulator.h", "quiche/quic/core/qpack/qpack_decoder.h", "quiche/quic/core/qpack/qpack_decoder_stream_receiver.h", @@ -603,6 +605,7 @@ "quiche/quic/core/http/web_transport_stream_adapter.cc", "quiche/quic/core/internet_checksum.cc", "quiche/quic/core/legacy_quic_stream_id_manager.cc", + "quiche/quic/core/qpack/new_qpack_blocking_manager.cc", "quiche/quic/core/qpack/qpack_blocking_manager.cc", "quiche/quic/core/qpack/qpack_decoded_headers_accumulator.cc", "quiche/quic/core/qpack/qpack_decoder.cc", @@ -1240,6 +1243,7 @@ "quiche/quic/core/internet_checksum_test.cc", "quiche/quic/core/legacy_quic_stream_id_manager_test.cc", "quiche/quic/core/packet_number_indexed_queue_test.cc", + "quiche/quic/core/qpack/new_qpack_blocking_manager_test.cc", "quiche/quic/core/qpack/qpack_blocking_manager_test.cc", "quiche/quic/core/qpack/qpack_decoded_headers_accumulator_test.cc", "quiche/quic/core/qpack/qpack_decoder_stream_receiver_test.cc",
diff --git a/quiche/common/quiche_feature_flags_list.h b/quiche/common/quiche_feature_flags_list.h index 009fef7..4285e06 100755 --- a/quiche/common/quiche_feature_flags_list.h +++ b/quiche/common/quiche_feature_flags_list.h
@@ -59,6 +59,7 @@ QUICHE_FLAG(bool, quiche_restart_flag_quic_support_release_time_for_gso, false, false, "If true, QuicGsoBatchWriter will support release time if it is available and the process has the permission to do so.") QUICHE_FLAG(bool, quiche_restart_flag_quic_testonly_default_false, false, false, "A testonly restart flag that will always default to false.") QUICHE_FLAG(bool, quiche_restart_flag_quic_testonly_default_true, true, true, "A testonly restart flag that will always default to true.") +QUICHE_FLAG(bool, quiche_restart_flag_quic_use_new_qpack_blocking_manager, false, false, "If true, QUIC will use NewQpackBlockingManager instead of QpackBlockingManager.") #endif // clang-format on
diff --git a/quiche/quic/core/qpack/new_qpack_blocking_manager.cc b/quiche/quic/core/qpack/new_qpack_blocking_manager.cc new file mode 100644 index 0000000..abe85f3 --- /dev/null +++ b/quiche/quic/core/qpack/new_qpack_blocking_manager.cc
@@ -0,0 +1,237 @@ +// Copyright (c) 2024 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 "quiche/quic/core/qpack/new_qpack_blocking_manager.h" + +#include <cstdint> +#include <initializer_list> +#include <limits> +#include <memory> +#include <utility> + +#include "absl/container/flat_hash_set.h" +#include "quiche/quic/core/quic_types.h" +#include "quiche/quic/platform/api/quic_bug_tracker.h" +#include "quiche/common/platform/api/quiche_logging.h" + +namespace quic { + +NewQpackBlockingManager::IndexSet::IndexSet( + std::initializer_list<uint64_t> indices) { + for (const uint64_t index : indices) { + insert(index); + } +} + +void NewQpackBlockingManager::IndexSet::insert(uint64_t index) { + if (index > max_index_) { + max_index_ = index; + } + if (index < min_index_) { + min_index_ = index; + } +} + +uint64_t NewQpackBlockingManager::IndexSet::RequiredInsertCount() const { + if (empty()) { + QUIC_BUG(qpack_blocking_manager_required_insert_count_on_empty_set) + << "RequiredInsertCount called on an empty IndexSet."; + return 0; + } + return max_index_ + 1; +} + +uint64_t NewQpackBlockingManager::StreamRecord::MaxRequiredInsertCount() const { + uint64_t result = 0; + for (const IndexSet& header_block : header_blocks) { + uint64_t required_insert_count = header_block.RequiredInsertCount(); + if (required_insert_count > result) { + result = required_insert_count; + } + } + return result; +} + +bool NewQpackBlockingManager::OnHeaderAcknowledgement(QuicStreamId stream_id) { + auto it = stream_map_.find(stream_id); + if (it == stream_map_.end()) { + return false; + } + + if (it->second->header_blocks.empty()) { + QUIC_BUG(qpack_blocking_manager_no_unacked_header_blocks_in_stream) + << "OnHeaderAcknowledgement is called on a stream with no " + "unacked header blocks. stream_id:" + << stream_id; + return false; + } + + { + // Scoped to prevent accidental access to |acked_header_block| after + // it is erased right after the scope. + const IndexSet& acked_header_block = it->second->header_blocks.front(); + if (known_received_count_ < acked_header_block.RequiredInsertCount()) { + IncreaseKnownReceivedCount(acked_header_block.RequiredInsertCount()); + } + DecMinIndexReferenceCounts(acked_header_block.min_index()); + } + it->second->header_blocks.erase(it->second->header_blocks.begin()); + + bool ok = true; + if (it->second->header_blocks.empty()) { + if (blocked_streams_.is_linked(it->second.get())) { + // header_blocks.empty() means all header blocks in the stream are acked, + // thus the stream should not be blocked. + QUIC_BUG(qpack_blocking_manager_stream_blocked_unexpectedly) + << "Stream is blocked unexpectedly. stream_id:" << stream_id; + ok = false; + UpdateBlockedListForStream(*it->second); + } + stream_map_.erase(it); + } + return ok; +} + +void NewQpackBlockingManager::IncreaseKnownReceivedCount( + uint64_t new_known_received_count) { + if (new_known_received_count <= known_received_count_) { + QUIC_BUG(qpack_blocking_manager_known_received_count_not_increased) + << "new_known_received_count:" << new_known_received_count + << ", known_received_count_:" << known_received_count_; + return; + } + + known_received_count_ = new_known_received_count; + + // Go through blocked streams and remove those that are no longer blocked. + for (auto it = blocked_streams_.begin(); it != blocked_streams_.end();) { + if (it->MaxRequiredInsertCount() > known_received_count_) { + // Stream is still blocked. + ++it; + continue; + } + + // Stream is no longer blocked. + it = blocked_streams_.erase(it); + num_blocked_streams_--; + } +} + +void NewQpackBlockingManager::OnStreamCancellation(QuicStreamId stream_id) { + auto it = stream_map_.find(stream_id); + if (it == stream_map_.end()) { + return; + } + + for (const IndexSet& header_block : it->second->header_blocks) { + DecMinIndexReferenceCounts(header_block.min_index()); + } + + // header_blocks.clear() cause StreamRecord.MaxRequiredInsertCount() to return + // zero, thus UpdateBlockedListForStream will remove it from blocked_streams_. + it->second->header_blocks.clear(); + UpdateBlockedListForStream(*it->second); + + stream_map_.erase(it); +} + +bool NewQpackBlockingManager::OnInsertCountIncrement(uint64_t increment) { + if (increment > + std::numeric_limits<uint64_t>::max() - known_received_count_) { + return false; + } + + IncreaseKnownReceivedCount(known_received_count_ + increment); + return true; +} + +void NewQpackBlockingManager::OnHeaderBlockSent( + QuicStreamId stream_id, IndexSet indices, uint64_t required_insert_count) { + if (indices.empty()) { + QUIC_BUG(qpack_blocking_manager_empty_indices) + << "OnHeaderBlockSent must not be called with empty indices. stream_id:" + << stream_id; + return; + } + + IncMinIndexReferenceCounts(indices.min_index()); + + QUICHE_DCHECK_EQ(required_insert_count, indices.RequiredInsertCount()); + auto it = stream_map_.find(stream_id); + if (it == stream_map_.end()) { + it = + stream_map_.insert({stream_id, std::make_unique<StreamRecord>()}).first; + } + it->second->header_blocks.push_back(std::move(indices)); + + UpdateBlockedListForStream(*it->second); +} + +void NewQpackBlockingManager::UpdateBlockedListForStream( + StreamRecord& stream_record) { + if (stream_record.MaxRequiredInsertCount() > known_received_count_) { + // Stream is blocked. + if (!blocked_streams_.is_linked(&stream_record)) { + blocked_streams_.push_back(&stream_record); + num_blocked_streams_++; + } + } else { + // Stream is not blocked. + if (blocked_streams_.is_linked(&stream_record)) { + blocked_streams_.erase(&stream_record); + num_blocked_streams_--; + } + } +} + +bool NewQpackBlockingManager::stream_is_blocked(QuicStreamId stream_id) const { + auto it = stream_map_.find(stream_id); + return it != stream_map_.end() && + blocked_streams_.is_linked(it->second.get()); +} + +bool NewQpackBlockingManager::blocking_allowed_on_stream( + QuicStreamId stream_id, uint64_t maximum_blocked_streams) const { + if (num_blocked_streams_ < maximum_blocked_streams) { + // Whether |stream_id| is currently blocked or not, blocking on it will not + // exceed |maximum_blocked_streams|. + return true; + } + + // We've reached |maximum_blocked_streams| so no _new_ blocked streams are + // allowed. Return true iff |stream_id| is already blocked. + return stream_is_blocked(stream_id); +} + +uint64_t NewQpackBlockingManager::smallest_blocking_index() const { + return min_index_reference_counts_.empty() + ? std::numeric_limits<uint64_t>::max() + : min_index_reference_counts_.begin()->first; +} + +// static +uint64_t NewQpackBlockingManager::RequiredInsertCount(const IndexSet& indices) { + return indices.RequiredInsertCount(); +} + +void NewQpackBlockingManager::IncMinIndexReferenceCounts(uint64_t min_index) { + min_index_reference_counts_[min_index]++; +} + +void NewQpackBlockingManager::DecMinIndexReferenceCounts(uint64_t min_index) { + auto it = min_index_reference_counts_.find(min_index); + if (it == min_index_reference_counts_.end()) { + QUIC_BUG(qpack_blocking_manager_removing_non_existent_min_index) + << "Removing min index:" << min_index + << " which do not exist in min_index_reference_counts_."; + return; + } + if (it->second == 1) { + min_index_reference_counts_.erase(it); + } else { + it->second--; + } +} + +} // namespace quic
diff --git a/quiche/quic/core/qpack/new_qpack_blocking_manager.h b/quiche/quic/core/qpack/new_qpack_blocking_manager.h new file mode 100644 index 0000000..e4942df --- /dev/null +++ b/quiche/quic/core/qpack/new_qpack_blocking_manager.h
@@ -0,0 +1,129 @@ +// Copyright (c) 2024 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_NEW_QPACK_BLOCKING_MANAGER_H_ +#define QUICHE_QUIC_CORE_QPACK_NEW_QPACK_BLOCKING_MANAGER_H_ + +#include <cstddef> +#include <cstdint> +#include <initializer_list> +#include <limits> +#include <memory> + +#include "absl/container/btree_map.h" +#include "absl/container/flat_hash_map.h" +#include "absl/container/inlined_vector.h" +#include "quiche/quic/core/quic_types.h" +#include "quiche/common/platform/api/quiche_export.h" +#include "quiche/common/quiche_intrusive_list.h" + +namespace quic { + +// Class to keep track of blocked streams and blocking dynamic table entries: +// https://rfc-editor.org/rfc/rfc9204.html#section-2.2.1. +// https://rfc-editor.org/rfc/rfc9204.html#section-2.1.2 +class QUICHE_EXPORT NewQpackBlockingManager { + public: + // "IndexSet" is a misnomer. It actually keeps track of the min and max of a + // set of indices. + class IndexSet { + public: + IndexSet() = default; + IndexSet(std::initializer_list<uint64_t> indices); // Test only. + + void insert(uint64_t index); + + bool empty() const { return min_index_ > max_index_; } + + uint64_t min_index() const { return min_index_; } + uint64_t max_index() const { return max_index_; } + + uint64_t RequiredInsertCount() const; + + private: + // The minimum and maximum index of the set. + uint64_t min_index_ = std::numeric_limits<uint64_t>::max(); + uint64_t max_index_ = 0; + }; + + // 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. Returns true if Known Received Count is successfully + // updated. Returns false on overflow. + bool 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, + uint64_t required_insert_count); + + // Whether |stream_id| is currently blocked. + bool stream_is_blocked(QuicStreamId stream_id) const; + + // Returns true if sending blocking references on stream |stream_id| would not + // increase the total number of blocked streams above + // |maximum_blocked_streams|. Note that if |stream_id| is already blocked + // then it is always allowed to send more blocking references on it. + // Behavior is undefined if |maximum_blocked_streams| is smaller than number + // of currently blocked streams. + bool blocking_allowed_on_stream(QuicStreamId stream_id, + uint64_t maximum_blocked_streams) 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://rfc-editor.org/rfc/rfc9204.html#section-2.1.4. + 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: + // Internal representation of a stream. + struct StreamRecord : quiche::QuicheIntrusiveLink<StreamRecord> { + // Returns the maximum "Required Insert Count" over all |header_blocks|. + uint64_t MaxRequiredInsertCount() const; + + absl::InlinedVector<IndexSet, 2> header_blocks; + }; + + // Updates the membership of |stream_record| in |blocked_streams_|. + void UpdateBlockedListForStream(StreamRecord& stream_record); + + // Increases |known_received_count_| to |new_known_received_count|, then + // removes streams from |blocked_streams_| that are no longer blocked. + void IncreaseKnownReceivedCount(uint64_t new_known_received_count); + + // Increase or decrease the reference counts in |min_index_reference_counts_|. + void IncMinIndexReferenceCounts(uint64_t min_index); + void DecMinIndexReferenceCounts(uint64_t min_index); + + // Map from stream ID to its StreamRecord, for all streams with unacked header + // blocks. The subset of "blocked streams" are in |blocked_streams_|. + absl::flat_hash_map<QuicStreamId, std::unique_ptr<StreamRecord>> stream_map_; + + // List of blocked streams. + quiche::QuicheIntrusiveList<StreamRecord> blocked_streams_; + size_t num_blocked_streams_ = 0; + + // Map from "min index" to the number of HeaderBlock(s) having that min index. + // This is needed to provide smallest_blocking_index(). + absl::btree_map<uint64_t, uint64_t> min_index_reference_counts_; + + uint64_t known_received_count_ = 0; +}; + +} // namespace quic + +#endif // QUICHE_QUIC_CORE_QPACK_NEW_QPACK_BLOCKING_MANAGER_H_
diff --git a/quiche/quic/core/qpack/new_qpack_blocking_manager_test.cc b/quiche/quic/core/qpack/new_qpack_blocking_manager_test.cc new file mode 100644 index 0000000..304ec91 --- /dev/null +++ b/quiche/quic/core/qpack/new_qpack_blocking_manager_test.cc
@@ -0,0 +1,348 @@ +// Copyright (c) 2024 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 "quiche/quic/core/qpack/new_qpack_blocking_manager.h" + +#include <limits> + +#include "quiche/quic/core/quic_types.h" +#include "quiche/quic/platform/api/quic_test.h" + +namespace quic { +namespace test { + +namespace { + +class NewQpackBlockingManagerTest : public QuicTest { + protected: + NewQpackBlockingManagerTest() = default; + ~NewQpackBlockingManagerTest() override = default; + + bool stream_is_blocked(QuicStreamId stream_id) const { + return manager_.stream_is_blocked(stream_id); + } + + NewQpackBlockingManager manager_; +}; + +TEST_F(NewQpackBlockingManagerTest, Empty) { + 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(NewQpackBlockingManagerTest, NotBlockedByInsertCountIncrement) { + EXPECT_TRUE(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}, 2); + EXPECT_FALSE(stream_is_blocked(0)); +} + +TEST_F(NewQpackBlockingManagerTest, UnblockedByInsertCountIncrement) { + manager_.OnHeaderBlockSent(0, {1, 0}, 2); + EXPECT_TRUE(stream_is_blocked(0)); + + EXPECT_TRUE(manager_.OnInsertCountIncrement(2)); + EXPECT_FALSE(stream_is_blocked(0)); +} + +TEST_F(NewQpackBlockingManagerTest, NotBlockedByHeaderAcknowledgement) { + manager_.OnHeaderBlockSent(0, {2, 1, 1}, 3); + EXPECT_TRUE(stream_is_blocked(0)); + + EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0)); + EXPECT_FALSE(stream_is_blocked(0)); + + // Stream 1 is not blocked, because it only references entries that are + // already acknowledged by a Header Acknowledgement instruction. + manager_.OnHeaderBlockSent(1, {2, 2}, 3); + EXPECT_FALSE(stream_is_blocked(1)); +} + +TEST_F(NewQpackBlockingManagerTest, UnblockedByHeaderAcknowledgement) { + manager_.OnHeaderBlockSent(0, {2, 1, 1}, 3); + manager_.OnHeaderBlockSent(1, {2, 2}, 3); + EXPECT_TRUE(stream_is_blocked(0)); + EXPECT_TRUE(stream_is_blocked(1)); + + EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0)); + EXPECT_FALSE(stream_is_blocked(0)); + EXPECT_FALSE(stream_is_blocked(1)); +} + +TEST_F(NewQpackBlockingManagerTest, KnownReceivedCount) { + EXPECT_EQ(0u, manager_.known_received_count()); + + // Sending a header block does not change Known Received Count. + manager_.OnHeaderBlockSent(0, {0}, 1); + EXPECT_EQ(0u, manager_.known_received_count()); + + manager_.OnHeaderBlockSent(1, {1}, 2); + 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}, 6); + 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. + EXPECT_TRUE(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}, 4); + 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}, 6); + EXPECT_EQ(6u, manager_.known_received_count()); + + EXPECT_TRUE(manager_.OnHeaderAcknowledgement(1)); + EXPECT_EQ(6u, manager_.known_received_count()); +} + +TEST_F(NewQpackBlockingManagerTest, SmallestBlockingIndex) { + EXPECT_EQ(std::numeric_limits<uint64_t>::max(), + manager_.smallest_blocking_index()); + + manager_.OnHeaderBlockSent(0, {0}, 1); + EXPECT_EQ(0u, manager_.smallest_blocking_index()); + + manager_.OnHeaderBlockSent(1, {2}, 3); + EXPECT_EQ(0u, manager_.smallest_blocking_index()); + + EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0)); + EXPECT_EQ(2u, manager_.smallest_blocking_index()); + + manager_.OnHeaderBlockSent(1, {1}, 2); + 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. + EXPECT_TRUE(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(NewQpackBlockingManagerTest, + SmallestBlockingIndexWithMinIndexReferredMoreThanOnce) { + manager_.OnHeaderBlockSent(1, {1, 2, 3, 4}, 5); + manager_.OnHeaderBlockSent(1, {2, 3, 4, 5}, 6); + manager_.OnHeaderBlockSent(1, {3, 4, 5, 6}, 7); + manager_.OnHeaderBlockSent(1, {4, 5, 6, 7}, 8); + + manager_.OnHeaderBlockSent(2, {2, 4, 6}, 7); + manager_.OnHeaderBlockSent(2, {3, 5, 7}, 8); + manager_.OnHeaderBlockSent(2, {2, 5, 8}, 9); + + // min_index_reference_counts_: {1:1, 2:3, 3:2, 4:1} + ASSERT_EQ(1u, manager_.smallest_blocking_index()); + + manager_.OnHeaderAcknowledgement(1); + // min_index_reference_counts_: {2:3, 3:2, 4:1} + EXPECT_EQ(2u, manager_.smallest_blocking_index()); + + manager_.OnHeaderAcknowledgement(1); + // min_index_reference_counts_: {2:2, 3:2, 4:1} + EXPECT_EQ(2u, manager_.smallest_blocking_index()); + + manager_.OnStreamCancellation(2); + // min_index_reference_counts_: {3:1, 4:1} + EXPECT_EQ(3u, manager_.smallest_blocking_index()); + + manager_.OnHeaderAcknowledgement(1); + // min_index_reference_counts_: {4:1} + EXPECT_EQ(4u, manager_.smallest_blocking_index()); + + manager_.OnHeaderAcknowledgement(1); + // min_index_reference_counts_: {} + EXPECT_EQ(std::numeric_limits<uint64_t>::max(), + manager_.smallest_blocking_index()); +} + +TEST_F(NewQpackBlockingManagerTest, HeaderAcknowledgementsOnSingleStream) { + EXPECT_EQ(0u, manager_.known_received_count()); + EXPECT_EQ(std::numeric_limits<uint64_t>::max(), + manager_.smallest_blocking_index()); + + manager_.OnHeaderBlockSent(0, {2, 1, 1}, 3); + EXPECT_EQ(0u, manager_.known_received_count()); + EXPECT_TRUE(stream_is_blocked(0)); + EXPECT_EQ(1u, manager_.smallest_blocking_index()); + + manager_.OnHeaderBlockSent(0, {1, 0}, 2); + EXPECT_EQ(0u, manager_.known_received_count()); + EXPECT_TRUE(stream_is_blocked(0)); + EXPECT_EQ(0u, manager_.smallest_blocking_index()); + + EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0)); + EXPECT_EQ(3u, manager_.known_received_count()); + EXPECT_FALSE(stream_is_blocked(0)); + EXPECT_EQ(0u, manager_.smallest_blocking_index()); + + manager_.OnHeaderBlockSent(0, {3}, 4); + EXPECT_EQ(3u, manager_.known_received_count()); + EXPECT_TRUE(stream_is_blocked(0)); + EXPECT_EQ(0u, manager_.smallest_blocking_index()); + + EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0)); + EXPECT_EQ(3u, manager_.known_received_count()); + EXPECT_TRUE(stream_is_blocked(0)); + EXPECT_EQ(3u, manager_.smallest_blocking_index()); + + EXPECT_TRUE(manager_.OnHeaderAcknowledgement(0)); + EXPECT_EQ(4u, manager_.known_received_count()); + EXPECT_FALSE(stream_is_blocked(0)); + EXPECT_EQ(std::numeric_limits<uint64_t>::max(), + manager_.smallest_blocking_index()); + + EXPECT_FALSE(manager_.OnHeaderAcknowledgement(0)); +} + +TEST_F(NewQpackBlockingManagerTest, CancelStream) { + manager_.OnHeaderBlockSent(0, {3}, 4); + EXPECT_TRUE(stream_is_blocked(0)); + EXPECT_EQ(3u, manager_.smallest_blocking_index()); + + manager_.OnHeaderBlockSent(0, {2}, 3); + EXPECT_TRUE(stream_is_blocked(0)); + EXPECT_EQ(2u, manager_.smallest_blocking_index()); + + manager_.OnHeaderBlockSent(1, {4}, 5); + EXPECT_TRUE(stream_is_blocked(0)); + EXPECT_TRUE(stream_is_blocked(1)); + EXPECT_EQ(2u, manager_.smallest_blocking_index()); + + manager_.OnStreamCancellation(0); + EXPECT_FALSE(stream_is_blocked(0)); + EXPECT_TRUE(stream_is_blocked(1)); + EXPECT_EQ(4u, manager_.smallest_blocking_index()); + + manager_.OnStreamCancellation(1); + EXPECT_FALSE(stream_is_blocked(0)); + EXPECT_FALSE(stream_is_blocked(1)); + EXPECT_EQ(std::numeric_limits<uint64_t>::max(), + manager_.smallest_blocking_index()); +} + +TEST_F(NewQpackBlockingManagerTest, BlockingAllowedOnStream) { + const QuicStreamId kStreamId1 = 1; + const QuicStreamId kStreamId2 = 2; + const QuicStreamId kStreamId3 = 3; + + // No stream can block if limit is 0. + EXPECT_FALSE(manager_.blocking_allowed_on_stream(kStreamId1, 0)); + EXPECT_FALSE(manager_.blocking_allowed_on_stream(kStreamId2, 0)); + + // Either stream can block if limit is larger. + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId1, 1)); + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId2, 1)); + + // Doubly block first stream. + manager_.OnHeaderBlockSent(kStreamId1, {0}, 1); + manager_.OnHeaderBlockSent(kStreamId1, {1}, 2); + + // First stream is already blocked so it can carry more blocking references. + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId1, 1)); + // Second stream is not allowed to block if limit is already reached. + EXPECT_FALSE(manager_.blocking_allowed_on_stream(kStreamId2, 1)); + + // Either stream can block if limit is larger than number of blocked streams. + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId1, 2)); + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId2, 2)); + + // Block second stream. + manager_.OnHeaderBlockSent(kStreamId2, {2}, 3); + + // Streams are already blocked so either can carry more blocking references. + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId1, 2)); + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId2, 2)); + + // Third, unblocked stream is not allowed to block unless limit is strictly + // larger than number of blocked streams. + EXPECT_FALSE(manager_.blocking_allowed_on_stream(kStreamId3, 2)); + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId3, 3)); + + // Acknowledge decoding of first header block on first stream. + // Stream is still blocked on its second header block. + manager_.OnHeaderAcknowledgement(kStreamId1); + + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId1, 2)); + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId2, 2)); + + // Acknowledge decoding of second header block on first stream. + // This unblocks the stream. + manager_.OnHeaderAcknowledgement(kStreamId1); + + // First stream is not allowed to block if limit is already reached. + EXPECT_FALSE(manager_.blocking_allowed_on_stream(kStreamId1, 1)); + // Second stream is already blocked so it can carry more blocking references. + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId2, 1)); + + // Either stream can block if limit is larger than number of blocked streams. + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId1, 2)); + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId2, 2)); + + // Unblock second stream. + manager_.OnHeaderAcknowledgement(kStreamId2); + + // No stream can block if limit is 0. + EXPECT_FALSE(manager_.blocking_allowed_on_stream(kStreamId1, 0)); + EXPECT_FALSE(manager_.blocking_allowed_on_stream(kStreamId2, 0)); + + // Either stream can block if limit is larger. + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId1, 1)); + EXPECT_TRUE(manager_.blocking_allowed_on_stream(kStreamId2, 1)); +} + +TEST_F(NewQpackBlockingManagerTest, InsertCountIncrementOverflow) { + EXPECT_TRUE(manager_.OnInsertCountIncrement(10)); + EXPECT_EQ(10u, manager_.known_received_count()); + + EXPECT_FALSE(manager_.OnInsertCountIncrement( + std::numeric_limits<uint64_t>::max() - 5)); +} + +TEST_F(NewQpackBlockingManagerTest, IndexSet) { + NewQpackBlockingManager::IndexSet set1, set2; + + EXPECT_TRUE(set1.empty()); + set1.insert(0); + EXPECT_FALSE(set1.empty()); + + EXPECT_TRUE(set2.empty()); + set2.insert(0); + EXPECT_FALSE(set2.empty()); +} + +} // namespace +} // namespace test +} // namespace quic
diff --git a/quiche/quic/core/qpack/qpack_blocking_manager_shim.h b/quiche/quic/core/qpack/qpack_blocking_manager_shim.h new file mode 100644 index 0000000..6dc3783 --- /dev/null +++ b/quiche/quic/core/qpack/qpack_blocking_manager_shim.h
@@ -0,0 +1,174 @@ +// Copyright (c) 2024 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_SHIM_H_ +#define QUICHE_QUIC_CORE_QPACK_QPACK_BLOCKING_MANAGER_SHIM_H_ + +#include <cstdint> +#include <utility> + +#include "absl/types/variant.h" +#include "quiche/quic/core/qpack/new_qpack_blocking_manager.h" +#include "quiche/quic/core/qpack/qpack_blocking_manager.h" +#include "quiche/quic/core/quic_types.h" +#include "quiche/quic/platform/api/quic_flag_utils.h" +#include "quiche/quic/platform/api/quic_flags.h" +#include "quiche/common/platform/api/quiche_export.h" +#include "quiche/common/platform/api/quiche_logging.h" + +namespace quic { + +class QUICHE_EXPORT QpackBlockingManagerShim { + public: + struct IndexSet : absl::variant<QpackBlockingManager::IndexSet, + NewQpackBlockingManager::IndexSet> { + IndexSet() { + if (use_new_qpack_blocking_manager()) { + emplace<NewQpackBlockingManager::IndexSet>(); + } else { + emplace<QpackBlockingManager::IndexSet>(); + } + } + + QpackBlockingManager::IndexSet& old_variant() { + QUICHE_DCHECK(!use_new_qpack_blocking_manager()); + return absl::get<QpackBlockingManager::IndexSet>(*this); + } + + const QpackBlockingManager::IndexSet& old_variant() const { + QUICHE_DCHECK(!use_new_qpack_blocking_manager()); + return absl::get<QpackBlockingManager::IndexSet>(*this); + } + + NewQpackBlockingManager::IndexSet& new_variant() { + QUICHE_DCHECK(use_new_qpack_blocking_manager()); + return absl::get<NewQpackBlockingManager::IndexSet>(*this); + } + + const NewQpackBlockingManager::IndexSet& new_variant() const { + QUICHE_DCHECK(use_new_qpack_blocking_manager()); + return absl::get<NewQpackBlockingManager::IndexSet>(*this); + } + + void insert(uint64_t index) { + if (use_new_qpack_blocking_manager()) { + new_variant().insert(index); + } else { + old_variant().insert(index); + } + } + + bool empty() const { + if (use_new_qpack_blocking_manager()) { + return new_variant().empty(); + } + return old_variant().empty(); + } + }; + + QpackBlockingManagerShim() { + if (use_new_qpack_blocking_manager()) { + manager_.emplace<NewQpackBlockingManager>(); + } else { + manager_.emplace<QpackBlockingManager>(); + } + } + + bool OnHeaderAcknowledgement(QuicStreamId stream_id) { + if (use_new_qpack_blocking_manager()) { + return new_manager().OnHeaderAcknowledgement(stream_id); + } + return old_manager().OnHeaderAcknowledgement(stream_id); + } + + void OnStreamCancellation(QuicStreamId stream_id) { + if (use_new_qpack_blocking_manager()) { + new_manager().OnStreamCancellation(stream_id); + } else { + old_manager().OnStreamCancellation(stream_id); + } + } + + bool OnInsertCountIncrement(uint64_t increment) { + if (use_new_qpack_blocking_manager()) { + return new_manager().OnInsertCountIncrement(increment); + } + return old_manager().OnInsertCountIncrement(increment); + } + + void OnHeaderBlockSent(QuicStreamId stream_id, IndexSet indices, + uint64_t required_insert_count) { + if (use_new_qpack_blocking_manager()) { + new_manager().OnHeaderBlockSent( + stream_id, std::move(indices.new_variant()), required_insert_count); + } else { + old_manager().OnHeaderBlockSent( + stream_id, std::move(indices.old_variant()), required_insert_count); + } + } + + bool blocking_allowed_on_stream(QuicStreamId stream_id, + uint64_t maximum_blocked_streams) const { + if (use_new_qpack_blocking_manager()) { + return new_manager().blocking_allowed_on_stream(stream_id, + maximum_blocked_streams); + } + return old_manager().blocking_allowed_on_stream(stream_id, + maximum_blocked_streams); + } + + uint64_t smallest_blocking_index() const { + if (use_new_qpack_blocking_manager()) { + return new_manager().smallest_blocking_index(); + } + return old_manager().smallest_blocking_index(); + } + + uint64_t known_received_count() const { + if (use_new_qpack_blocking_manager()) { + return new_manager().known_received_count(); + } + return old_manager().known_received_count(); + } + + static uint64_t RequiredInsertCount(const IndexSet& indices) { + if (use_new_qpack_blocking_manager()) { + return NewQpackBlockingManager::RequiredInsertCount( + indices.new_variant()); + } + return QpackBlockingManager::RequiredInsertCount(indices.old_variant()); + } + + private: + static bool use_new_qpack_blocking_manager() { + static bool use_new = []() { + bool value = GetQuicRestartFlag(quic_use_new_qpack_blocking_manager); + if (value) { + QUIC_RESTART_FLAG_COUNT(quic_use_new_qpack_blocking_manager); + } + return value; + }(); + return use_new; + } + + QpackBlockingManager& old_manager() { + return absl::get<QpackBlockingManager>(manager_); + } + const QpackBlockingManager& old_manager() const { + return absl::get<QpackBlockingManager>(manager_); + } + + NewQpackBlockingManager& new_manager() { + return absl::get<NewQpackBlockingManager>(manager_); + } + const NewQpackBlockingManager& new_manager() const { + return absl::get<NewQpackBlockingManager>(manager_); + } + + absl::variant<QpackBlockingManager, NewQpackBlockingManager> manager_; +}; + +} // namespace quic + +#endif // QUICHE_QUIC_CORE_QPACK_QPACK_BLOCKING_MANAGER_SHIM_H_
diff --git a/quiche/quic/core/qpack/qpack_encoder.cc b/quiche/quic/core/qpack/qpack_encoder.cc index 2ed6290..59dd991 100644 --- a/quiche/quic/core/qpack/qpack_encoder.cc +++ b/quiche/quic/core/qpack/qpack_encoder.cc
@@ -51,7 +51,7 @@ // static QpackEncoder::Representation QpackEncoder::EncodeIndexedHeaderField( bool is_static, uint64_t index, - QpackBlockingManager::IndexSet* referred_indices) { + QpackBlockingManagerShim::IndexSet* referred_indices) { // Add |index| to |*referred_indices| only if entry is in the dynamic table. if (!is_static) { referred_indices->insert(index); @@ -63,7 +63,7 @@ QpackEncoder::Representation QpackEncoder::EncodeLiteralHeaderFieldWithNameReference( bool is_static, uint64_t index, absl::string_view value, - QpackBlockingManager::IndexSet* referred_indices) { + QpackBlockingManagerShim::IndexSet* referred_indices) { // Add |index| to |*referred_indices| only if entry is in the dynamic table. if (!is_static) { referred_indices->insert(index); @@ -80,7 +80,7 @@ QpackEncoder::Representations QpackEncoder::FirstPassEncode( QuicStreamId stream_id, const quiche::HttpHeaderBlock& header_list, - QpackBlockingManager::IndexSet* referred_indices, + QpackBlockingManagerShim::IndexSet* referred_indices, QuicByteCount* encoder_stream_sent_byte_count) { // If previous instructions are buffered in |encoder_stream_sender_|, // do not count them towards the current header block. @@ -395,7 +395,7 @@ QuicByteCount* encoder_stream_sent_byte_count) { // Keep track of all dynamic table indices that this header block refers to so // that it can be passed to QpackBlockingManager. - QpackBlockingManager::IndexSet referred_indices; + QpackBlockingManagerShim::IndexSet referred_indices; // First pass: encode into |representations|. Representations representations = @@ -405,7 +405,7 @@ const uint64_t required_insert_count = referred_indices.empty() ? 0 - : QpackBlockingManager::RequiredInsertCount(referred_indices); + : QpackBlockingManagerShim::RequiredInsertCount(referred_indices); if (!referred_indices.empty()) { blocking_manager_.OnHeaderBlockSent(stream_id, std::move(referred_indices), required_insert_count);
diff --git a/quiche/quic/core/qpack/qpack_encoder.h b/quiche/quic/core/qpack/qpack_encoder.h index 492bbbe..afb7a55 100644 --- a/quiche/quic/core/qpack/qpack_encoder.h +++ b/quiche/quic/core/qpack/qpack_encoder.h
@@ -11,7 +11,7 @@ #include <vector> #include "absl/strings/string_view.h" -#include "quiche/quic/core/qpack/qpack_blocking_manager.h" +#include "quiche/quic/core/qpack/qpack_blocking_manager_shim.h" #include "quiche/quic/core/qpack/qpack_decoder_stream_receiver.h" #include "quiche/quic/core/qpack/qpack_encoder_stream_sender.h" #include "quiche/quic/core/qpack/qpack_header_table.h" @@ -115,13 +115,13 @@ // and optionally update |*referred_indices|. static Representation EncodeIndexedHeaderField( bool is_static, uint64_t index, - QpackBlockingManager::IndexSet* referred_indices); + QpackBlockingManagerShim::IndexSet* referred_indices); // Generate literal header field with name reference representation // and optionally update |*referred_indices|. static Representation EncodeLiteralHeaderFieldWithNameReference( bool is_static, uint64_t index, absl::string_view value, - QpackBlockingManager::IndexSet* referred_indices); + QpackBlockingManagerShim::IndexSet* referred_indices); // Generate literal header field representation. static Representation EncodeLiteralHeaderField(absl::string_view name, @@ -140,7 +140,7 @@ // absl::string_views pointing to strings owned by |*header_list|. Representations FirstPassEncode( QuicStreamId stream_id, const quiche::HttpHeaderBlock& header_list, - QpackBlockingManager::IndexSet* referred_indices, + QpackBlockingManagerShim::IndexSet* referred_indices, QuicByteCount* encoder_stream_sent_byte_count); // Performs second pass of two-pass encoding: serializes representations @@ -156,7 +156,7 @@ QpackEncoderStreamSender encoder_stream_sender_; QpackEncoderHeaderTable header_table_; uint64_t maximum_blocked_streams_; - QpackBlockingManager blocking_manager_; + QpackBlockingManagerShim blocking_manager_; int header_list_count_; };