Implement QuicWriteBlockedList version that supports WebTransport priority scheme. The resulting scheduler can handle both HTTP/3 priorities for HTTP streams, and WebTransport priorities for WebTransport data streams. PiperOrigin-RevId: 633604441
diff --git a/build/source_list.bzl b/build/source_list.bzl index 67a610a..b04eb4c 100644 --- a/build/source_list.bzl +++ b/build/source_list.bzl
@@ -357,6 +357,7 @@ "quic/core/uber_received_packet_manager.h", "quic/core/web_transport_interface.h", "quic/core/web_transport_stats.h", + "quic/core/web_transport_write_blocked_list.h", "quic/platform/api/quic_bug_tracker.h", "quic/platform/api/quic_client_stats.h", "quic/platform/api/quic_export.h", @@ -674,6 +675,7 @@ "quic/core/uber_quic_stream_id_manager.cc", "quic/core/uber_received_packet_manager.cc", "quic/core/web_transport_stats.cc", + "quic/core/web_transport_write_blocked_list.cc", "quic/platform/api/quic_socket_address.cc", "spdy/core/array_output_buffer.cc", "spdy/core/hpack/hpack_constants.cc", @@ -1303,6 +1305,7 @@ "quic/core/tls_server_handshaker_test.cc", "quic/core/uber_quic_stream_id_manager_test.cc", "quic/core/uber_received_packet_manager_test.cc", + "quic/core/web_transport_write_blocked_list_test.cc", "quic/platform/api/quic_socket_address_test.cc", "quic/test_tools/crypto_test_utils_test.cc", "quic/test_tools/quic_test_utils_test.cc",
diff --git a/build/source_list.gni b/build/source_list.gni index afc2300..9af07f6 100644 --- a/build/source_list.gni +++ b/build/source_list.gni
@@ -357,6 +357,7 @@ "src/quiche/quic/core/uber_received_packet_manager.h", "src/quiche/quic/core/web_transport_interface.h", "src/quiche/quic/core/web_transport_stats.h", + "src/quiche/quic/core/web_transport_write_blocked_list.h", "src/quiche/quic/platform/api/quic_bug_tracker.h", "src/quiche/quic/platform/api/quic_client_stats.h", "src/quiche/quic/platform/api/quic_export.h", @@ -674,6 +675,7 @@ "src/quiche/quic/core/uber_quic_stream_id_manager.cc", "src/quiche/quic/core/uber_received_packet_manager.cc", "src/quiche/quic/core/web_transport_stats.cc", + "src/quiche/quic/core/web_transport_write_blocked_list.cc", "src/quiche/quic/platform/api/quic_socket_address.cc", "src/quiche/spdy/core/array_output_buffer.cc", "src/quiche/spdy/core/hpack/hpack_constants.cc", @@ -1304,6 +1306,7 @@ "src/quiche/quic/core/tls_server_handshaker_test.cc", "src/quiche/quic/core/uber_quic_stream_id_manager_test.cc", "src/quiche/quic/core/uber_received_packet_manager_test.cc", + "src/quiche/quic/core/web_transport_write_blocked_list_test.cc", "src/quiche/quic/platform/api/quic_socket_address_test.cc", "src/quiche/quic/test_tools/crypto_test_utils_test.cc", "src/quiche/quic/test_tools/quic_test_utils_test.cc",
diff --git a/build/source_list.json b/build/source_list.json index b49530e..09f6d11 100644 --- a/build/source_list.json +++ b/build/source_list.json
@@ -356,6 +356,7 @@ "quiche/quic/core/uber_received_packet_manager.h", "quiche/quic/core/web_transport_interface.h", "quiche/quic/core/web_transport_stats.h", + "quiche/quic/core/web_transport_write_blocked_list.h", "quiche/quic/platform/api/quic_bug_tracker.h", "quiche/quic/platform/api/quic_client_stats.h", "quiche/quic/platform/api/quic_export.h", @@ -673,6 +674,7 @@ "quiche/quic/core/uber_quic_stream_id_manager.cc", "quiche/quic/core/uber_received_packet_manager.cc", "quiche/quic/core/web_transport_stats.cc", + "quiche/quic/core/web_transport_write_blocked_list.cc", "quiche/quic/platform/api/quic_socket_address.cc", "quiche/spdy/core/array_output_buffer.cc", "quiche/spdy/core/hpack/hpack_constants.cc", @@ -1303,6 +1305,7 @@ "quiche/quic/core/tls_server_handshaker_test.cc", "quiche/quic/core/uber_quic_stream_id_manager_test.cc", "quiche/quic/core/uber_received_packet_manager_test.cc", + "quiche/quic/core/web_transport_write_blocked_list_test.cc", "quiche/quic/platform/api/quic_socket_address_test.cc", "quiche/quic/test_tools/crypto_test_utils_test.cc", "quiche/quic/test_tools/quic_test_utils_test.cc",
diff --git a/quiche/common/btree_scheduler.h b/quiche/common/btree_scheduler.h index 75312a3..753eda2 100644 --- a/quiche/common/btree_scheduler.h +++ b/quiche/common/btree_scheduler.h
@@ -49,6 +49,8 @@ bool HasScheduled() const { return !schedule_.empty(); } // Returns the number of currently scheduled streams. size_t NumScheduled() const { return schedule_.size(); } + // Returns the total number of currently registered streams. + size_t NumRegistered() const { return streams_.size(); } // Counts the number of scheduled entries in the range [min, max]. If either // min or max is omitted, negative or positive infinity is assumed.
diff --git a/quiche/quic/core/quic_stream_priority.h b/quiche/quic/core/quic_stream_priority.h index 8b1df3c..4065662 100644 --- a/quiche/quic/core/quic_stream_priority.h +++ b/quiche/quic/core/quic_stream_priority.h
@@ -15,6 +15,7 @@ #include "quiche/quic/core/quic_types.h" #include "quiche/common/platform/api/quiche_bug_tracker.h" #include "quiche/common/platform/api/quiche_export.h" +#include "quiche/web_transport/web_transport.h" namespace quic { @@ -42,27 +43,22 @@ } }; -// Represents WebTransport priorities as defined by +// Represents the priorities of WebTransport nested data streams as defined in // <https://w3c.github.io/webtransport/>. struct QUICHE_EXPORT WebTransportStreamPriority { - enum class StreamType : uint8_t { - // WebTransport data streams. - kData = 0, - // Regular HTTP traffic. Since we're currently only supporting dedicated - // HTTP/3 transport, this means that all HTTP traffic is control traffic, - // and thus should always go first. - kHttp = 1, - // Streams that the QUIC stack declares as static. - kStatic = 2, - }; - - // Allows prioritizing control streams over the data streams. - StreamType stream_type = StreamType::kData; + // The stream ID of the control stream for the WebTransport session to which + // this data stream belongs. + QuicStreamId session_id = 0; + // Number of the send group with which the stream is associated; see + // https://w3c.github.io/webtransport/#dom-webtransportsendstreamoptions-sendgroup + uint64_t send_group_number = 0; // https://w3c.github.io/webtransport/#dom-webtransportsendstreamoptions-sendorder - int64_t send_order = 0; + webtransport::SendOrder send_order = 0; bool operator==(const WebTransportStreamPriority& other) const { - return stream_type == other.stream_type && send_order == other.send_order; + return session_id == other.session_id && + send_group_number == other.send_group_number && + send_order == other.send_order; } bool operator!=(const WebTransportStreamPriority& other) const { return !(*this == other);
diff --git a/quiche/quic/core/quic_stream_priority_test.cc b/quiche/quic/core/quic_stream_priority_test.cc index 53f3312..e0e77b4 100644 --- a/quiche/quic/core/quic_stream_priority_test.cc +++ b/quiche/quic/core/quic_stream_priority_test.cc
@@ -34,21 +34,18 @@ TEST(WebTransportStreamPriority, DefaultConstructed) { WebTransportStreamPriority priority; - EXPECT_EQ(priority.stream_type, - WebTransportStreamPriority::StreamType::kData); + EXPECT_EQ(priority.session_id, 0); + EXPECT_EQ(priority.send_group_number, 0); EXPECT_EQ(priority.send_order, 0); } TEST(WebTransportStreamPriority, Equals) { EXPECT_EQ(WebTransportStreamPriority(), - (WebTransportStreamPriority{ - WebTransportStreamPriority::StreamType::kData, 0})); + (WebTransportStreamPriority{0, 0, 0})); EXPECT_NE(WebTransportStreamPriority(), - (WebTransportStreamPriority{ - WebTransportStreamPriority::StreamType::kData, 1})); + (WebTransportStreamPriority{1, 2, 3})); EXPECT_NE(WebTransportStreamPriority(), - (WebTransportStreamPriority{ - WebTransportStreamPriority::StreamType::kHttp, 0})); + (WebTransportStreamPriority{0, 0, 1})); } TEST(QuicStreamPriority, Default) {
diff --git a/quiche/quic/core/quic_write_blocked_list.h b/quiche/quic/core/quic_write_blocked_list.h index 3c3645f..1a72c82 100644 --- a/quiche/quic/core/quic_write_blocked_list.h +++ b/quiche/quic/core/quic_write_blocked_list.h
@@ -13,6 +13,7 @@ #include "quiche/http2/core/priority_write_scheduler.h" #include "quiche/quic/core/quic_packets.h" #include "quiche/quic/core/quic_stream_priority.h" +#include "quiche/quic/core/quic_types.h" #include "quiche/quic/platform/api/quic_bug_tracker.h" #include "quiche/quic/platform/api/quic_export.h" #include "quiche/quic/platform/api/quic_flags.h"
diff --git a/quiche/quic/core/web_transport_write_blocked_list.cc b/quiche/quic/core/web_transport_write_blocked_list.cc new file mode 100644 index 0000000..0e526d8 --- /dev/null +++ b/quiche/quic/core/web_transport_write_blocked_list.cc
@@ -0,0 +1,297 @@ +// Copyright 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/web_transport_write_blocked_list.h" + +#include <cstddef> +#include <optional> +#include <string> + +#include "absl/status/status.h" +#include "absl/status/statusor.h" +#include "absl/strings/str_format.h" +#include "quiche/quic/core/quic_stream_priority.h" +#include "quiche/quic/core/quic_types.h" +#include "quiche/common/platform/api/quiche_bug_tracker.h" +#include "quiche/common/platform/api/quiche_logging.h" + +namespace quic { + +bool WebTransportWriteBlockedList::HasWriteBlockedDataStreams() const { + return main_schedule_.NumScheduledInPriorityRange( + std::nullopt, RemapUrgency(HttpStreamPriority::kMaximumUrgency, + /*is_http=*/true)) > 0; +} + +size_t WebTransportWriteBlockedList::NumBlockedSpecialStreams() const { + return main_schedule_.NumScheduledInPriorityRange( + RemapUrgency(kStaticUrgency, /*is_http=*/false), std::nullopt); +} + +size_t WebTransportWriteBlockedList::NumBlockedStreams() const { + size_t num_streams = main_schedule_.NumScheduled(); + for (const auto& [key, scheduler] : web_transport_session_schedulers_) { + if (scheduler.HasScheduled()) { + num_streams += scheduler.NumScheduled(); + // Account for the fact that the group itself has an entry in the main + // scheduler that does not correspond to any actual stream. + QUICHE_DCHECK(main_schedule_.IsScheduled(key)); + --num_streams; + } + } + return num_streams; +} + +void WebTransportWriteBlockedList::RegisterStream( + QuicStreamId stream_id, bool is_static_stream, + const QuicStreamPriority& raw_priority) { + QuicStreamPriority priority = + is_static_stream + ? QuicStreamPriority(HttpStreamPriority{kStaticUrgency, true}) + : raw_priority; + auto [unused, success] = priorities_.emplace(stream_id, priority); + if (!success) { + QUICHE_BUG(WTWriteBlocked_RegisterStream_already_registered) + << "Tried to register stream " << stream_id + << " that is already registered"; + return; + } + + if (priority.type() == QuicPriorityType::kHttp) { + absl::Status status = main_schedule_.Register( + ScheduleKey::HttpStream(stream_id), + RemapUrgency(priority.http().urgency, /*is_http=*/true)); + QUICHE_BUG_IF(WTWriteBlocked_RegisterStream_http_scheduler, !status.ok()) + << status; + return; + } + + QUICHE_DCHECK_EQ(priority.type(), QuicPriorityType::kWebTransport); + ScheduleKey group_key = ScheduleKey::WebTransportSession(priority); + auto [it, created_new] = + web_transport_session_schedulers_.try_emplace(group_key); + absl::Status status = + it->second.Register(stream_id, priority.web_transport().send_order); + QUICHE_BUG_IF(WTWriteBlocked_RegisterStream_data_scheduler, !status.ok()) + << status; + + // If the group is new, register it with the main scheduler. + if (created_new) { + // The IETF draft requires the priority of data streams associated with an + // individual session to be equivalent to the priority of the control + // stream. + auto session_priority_it = + priorities_.find(priority.web_transport().session_id); + // It is possible for a stream to be (re-)registered while the control + // stream is already gone. + QUICHE_DLOG_IF(WARNING, session_priority_it == priorities_.end()) + << "Stream " << stream_id << " is associated with session ID " + << priority.web_transport().session_id + << ", but the session control stream is not registered; assuming " + "default urgency."; + QuicStreamPriority session_priority = + session_priority_it != priorities_.end() + ? session_priority_it->second + : QuicStreamPriority::Default(QuicPriorityType::kHttp); + + status = main_schedule_.Register( + group_key, + RemapUrgency(session_priority.http().urgency, /*is_http=*/false)); + QUICHE_BUG_IF(WTWriteBlocked_RegisterStream_main_scheduler, !status.ok()) + << status; + } +} + +void WebTransportWriteBlockedList::UnregisterStream(QuicStreamId stream_id) { + auto map_it = priorities_.find(stream_id); + if (map_it == priorities_.end()) { + QUICHE_BUG(WTWriteBlocked_UnregisterStream_not_found) + << "Stream " << stream_id << " not found"; + return; + } + QuicStreamPriority priority = map_it->second; + priorities_.erase(map_it); + + if (priority.type() != QuicPriorityType::kWebTransport) { + absl::Status status = + main_schedule_.Unregister(ScheduleKey::HttpStream(stream_id)); + QUICHE_BUG_IF(WTWriteBlocked_UnregisterStream_http, !status.ok()) << status; + return; + } + + ScheduleKey key = ScheduleKey::WebTransportSession(priority); + auto subscheduler_it = web_transport_session_schedulers_.find(key); + if (subscheduler_it == web_transport_session_schedulers_.end()) { + QUICHE_BUG(WTWriteBlocked_UnregisterStream_no_subscheduler) + << "Stream " << stream_id + << " is a WebTransport data stream, but has no scheduler for the " + "associated group"; + return; + } + Subscheduler& subscheduler = subscheduler_it->second; + absl::Status status = subscheduler.Unregister(stream_id); + QUICHE_BUG_IF(WTWriteBlocked_UnregisterStream_subscheduler_stream_failed, + !status.ok()) + << status; + + // If this is the last stream associated with the group, remove the group. + if (!subscheduler.HasRegistered()) { + status = main_schedule_.Unregister(key); + QUICHE_BUG_IF(WTWriteBlocked_UnregisterStream_subscheduler_failed, + !status.ok()) + << status; + + web_transport_session_schedulers_.erase(subscheduler_it); + } +} + +void WebTransportWriteBlockedList::UpdateStreamPriority( + QuicStreamId stream_id, const QuicStreamPriority& new_priority) { + UnregisterStream(stream_id); + RegisterStream(stream_id, /*is_static_stream=*/false, new_priority); + + if (new_priority.type() == QuicPriorityType::kHttp) { + for (auto& [key, subscheduler] : web_transport_session_schedulers_) { + QUICHE_DCHECK(key.has_group()); + if (key.stream() == stream_id) { + absl::Status status = + main_schedule_.UpdatePriority(key, new_priority.http().urgency); + QUICHE_BUG_IF(WTWriteBlocked_UpdateStreamPriority_subscheduler_failed, + !status.ok()) + << status; + } + } + } +} + +QuicStreamId WebTransportWriteBlockedList::PopFront() { + absl::StatusOr<ScheduleKey> main_key = main_schedule_.PopFront(); + if (!main_key.ok()) { + QUICHE_BUG(WTWriteBlocked_PopFront_no_streams) + << "PopFront() called when no streams scheduled: " << main_key.status(); + return 0; + } + if (!main_key->has_group()) { + return main_key->stream(); + } + + auto it = web_transport_session_schedulers_.find(*main_key); + if (it == web_transport_session_schedulers_.end()) { + QUICHE_BUG(WTWriteBlocked_PopFront_no_subscheduler) + << "Subscheduler for WebTransport group " << main_key->DebugString() + << " not found"; + return 0; + } + Subscheduler& subscheduler = it->second; + absl::StatusOr<QuicStreamId> result = subscheduler.PopFront(); + if (!result.ok()) { + QUICHE_BUG(WTWriteBlocked_PopFront_subscheduler_empty) + << "Subscheduler for group " << main_key->DebugString() + << " is empty while in the main schedule"; + return 0; + } + if (subscheduler.HasScheduled()) { + absl::Status status = main_schedule_.Schedule(*main_key); + QUICHE_BUG_IF(WTWriteBlocked_PopFront_reschedule_group, !status.ok()) + << status; + } + return *result; +} + +void WebTransportWriteBlockedList::AddStream(QuicStreamId stream_id) { + QuicStreamPriority priority = GetPriorityOfStream(stream_id); + absl::Status status; + switch (priority.type()) { + case QuicPriorityType::kHttp: + status = main_schedule_.Schedule(ScheduleKey::HttpStream(stream_id)); + QUICHE_BUG_IF(WTWriteBlocked_AddStream_http, !status.ok()) << status; + break; + case QuicPriorityType::kWebTransport: + status = + main_schedule_.Schedule(ScheduleKey::WebTransportSession(priority)); + QUICHE_BUG_IF(WTWriteBlocked_AddStream_wt_main, !status.ok()) << status; + + auto it = web_transport_session_schedulers_.find( + ScheduleKey::WebTransportSession(priority)); + if (it == web_transport_session_schedulers_.end()) { + QUICHE_BUG(WTWriteBlocked_AddStream_no_subscheduler) + << ScheduleKey::WebTransportSession(priority); + return; + } + Subscheduler& subscheduler = it->second; + status = subscheduler.Schedule(stream_id); + QUICHE_BUG_IF(WTWriteBlocked_AddStream_wt_sub, !status.ok()) << status; + break; + } +} + +bool WebTransportWriteBlockedList::IsStreamBlocked( + QuicStreamId stream_id) const { + QuicStreamPriority priority = GetPriorityOfStream(stream_id); + switch (priority.type()) { + case QuicPriorityType::kHttp: + return main_schedule_.IsScheduled(ScheduleKey::HttpStream(stream_id)); + break; + case QuicPriorityType::kWebTransport: + auto it = web_transport_session_schedulers_.find( + ScheduleKey::WebTransportSession(priority)); + if (it == web_transport_session_schedulers_.end()) { + QUICHE_BUG(WTWriteBlocked_IsStreamBlocked_no_subscheduler) + << ScheduleKey::WebTransportSession(priority); + return false; + } + const Subscheduler& subscheduler = it->second; + return subscheduler.IsScheduled(stream_id); + } +} + +QuicStreamPriority WebTransportWriteBlockedList::GetPriorityOfStream( + QuicStreamId id) const { + auto it = priorities_.find(id); + if (it == priorities_.end()) { + QUICHE_BUG(WTWriteBlocked_GetPriorityOfStream_not_found) + << "Stream " << id << " not found"; + return QuicStreamPriority::Default(QuicPriorityType::kHttp); + } + return it->second; +} + +std::string WebTransportWriteBlockedList::ScheduleKey::DebugString() const { + return absl::StrFormat("(%d, %d)", stream_, group_); +} + +bool WebTransportWriteBlockedList::ShouldYield(QuicStreamId id) const { + QuicStreamPriority priority = GetPriorityOfStream(id); + if (priority.type() == QuicPriorityType::kHttp) { + absl::StatusOr<bool> should_yield = + main_schedule_.ShouldYield(ScheduleKey::HttpStream(id)); + QUICHE_BUG_IF(WTWriteBlocked_ShouldYield_http, !should_yield.ok()) + << should_yield.status(); + return *should_yield; + } + QUICHE_DCHECK_EQ(priority.type(), QuicPriorityType::kWebTransport); + absl::StatusOr<bool> should_yield = + main_schedule_.ShouldYield(ScheduleKey::WebTransportSession(priority)); + QUICHE_BUG_IF(WTWriteBlocked_ShouldYield_wt_main, !should_yield.ok()) + << should_yield.status(); + if (*should_yield) { + return true; + } + + auto it = web_transport_session_schedulers_.find( + ScheduleKey::WebTransportSession(priority)); + if (it == web_transport_session_schedulers_.end()) { + QUICHE_BUG(WTWriteBlocked_ShouldYield_subscheduler_not_found) + << "Subscheduler not found for " + << ScheduleKey::WebTransportSession(priority); + return false; + } + const Subscheduler& subscheduler = it->second; + + should_yield = subscheduler.ShouldYield(id); + QUICHE_BUG_IF(WTWriteBlocked_ShouldYield_wt_subscheduler, !should_yield.ok()) + << should_yield.status(); + return *should_yield; +} +} // namespace quic
diff --git a/quiche/quic/core/web_transport_write_blocked_list.h b/quiche/quic/core/web_transport_write_blocked_list.h new file mode 100644 index 0000000..8cf294b --- /dev/null +++ b/quiche/quic/core/web_transport_write_blocked_list.h
@@ -0,0 +1,156 @@ +// Copyright 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_WEB_TRANSPORT_WRITE_BLOCKED_LIST_H_ +#define QUICHE_QUIC_CORE_WEB_TRANSPORT_WRITE_BLOCKED_LIST_H_ + +#include <cstddef> +#include <limits> +#include <ostream> +#include <string> + +#include "absl/container/flat_hash_map.h" +#include "quiche/quic/core/quic_stream_priority.h" +#include "quiche/quic/core/quic_types.h" +#include "quiche/quic/core/quic_write_blocked_list.h" +#include "quiche/common/btree_scheduler.h" +#include "quiche/common/platform/api/quiche_export.h" +#include "quiche/web_transport/web_transport.h" + +namespace quic { + +// Scheduler that is capable of handling both regular HTTP/3 priorities and +// WebTransport priorities for multiple sessions at the same time. +// +// Here is a brief overview of the scheme: +// - At the top, there are HTTP/3 streams that are ordered by urgency as +// defined in RFC 9218. +// - The HTTP/3 connection can be a host to multiple WebTransport sessions. +// Those are identified by the ID of the HTTP/3 control stream that created +// the session; they also inherit the priority from that stream. +// - The sessions consist of send groups that all have equal priority. +// - The send groups have individual WebTransport data streams; each data +// stream has a send order, which is a strict priority expressed as int64. +// +// To simplify the implementation of an already excessively complex scheme, this +// class makes a couple of affordances: +// - Instead of first scheduling an individual session, then scheduling a +// group within it, it schedules session-group pairs at the top level. This +// is technically allowed by the spec, but it does mean that sessions with +// more groups may get more bandwidth. +// - Incremental priorities are not currently supported. +class QUICHE_EXPORT WebTransportWriteBlockedList + : public QuicWriteBlockedListInterface { + public: + // Handle static streams by treating them as streams of priority MAX + 1. + static constexpr int kStaticUrgency = HttpStreamPriority::kMaximumUrgency + 1; + + // QuicWriteBlockedListInterface implementation. + bool HasWriteBlockedDataStreams() const override; + size_t NumBlockedSpecialStreams() const override; + size_t NumBlockedStreams() const override; + + void RegisterStream(QuicStreamId stream_id, bool is_static_stream, + const QuicStreamPriority& raw_priority) override; + void UnregisterStream(QuicStreamId stream_id) override; + void UpdateStreamPriority(QuicStreamId stream_id, + const QuicStreamPriority& new_priority) override; + + bool ShouldYield(QuicStreamId id) const override; + QuicStreamPriority GetPriorityOfStream(QuicStreamId id) const override; + QuicStreamId PopFront() override; + void UpdateBytesForStream(QuicStreamId /*stream_id*/, + size_t /*bytes*/) override {} + void AddStream(QuicStreamId stream_id) override; + bool IsStreamBlocked(QuicStreamId stream_id) const override; + + size_t NumRegisteredGroups() const { + return web_transport_session_schedulers_.size(); + } + size_t NumRegisteredHttpStreams() const { + return main_schedule_.NumRegistered() - NumRegisteredGroups(); + } + + private: + // ScheduleKey represents anything that can be put into the main scheduler, + // which is either: + // - an HTTP/3 stream, or + // - an individual WebTransport session-send group pair. + class QUICHE_EXPORT ScheduleKey { + public: + static ScheduleKey HttpStream(QuicStreamId id) { + return ScheduleKey(id, kNoSendGroup); + } + static ScheduleKey WebTransportSession(QuicStreamId session_id, + webtransport::SendGroupId group_id) { + return ScheduleKey(session_id, group_id); + } + static ScheduleKey WebTransportSession(const QuicStreamPriority& priority) { + return ScheduleKey(priority.web_transport().session_id, + priority.web_transport().send_group_number); + } + + bool operator==(const ScheduleKey& other) const { + return stream_ == other.stream_ && group_ == other.group_; + } + bool operator!=(const ScheduleKey& other) const { + return !(*this == other); + } + + template <typename H> + friend H AbslHashValue(H h, const ScheduleKey& key) { + return H::combine(std::move(h), key.stream_, key.group_); + } + + bool has_group() const { return group_ != kNoSendGroup; } + quic::QuicStreamId stream() const { return stream_; } + + std::string DebugString() const; + + friend inline std::ostream& operator<<(std::ostream& os, + const ScheduleKey& key) { + os << key.DebugString(); + return os; + } + + private: + static constexpr webtransport::SendGroupId kNoSendGroup = + std::numeric_limits<webtransport::SendGroupId>::max(); + + explicit ScheduleKey(quic::QuicStreamId stream, + webtransport::SendGroupId group) + : stream_(stream), group_(group) {} + + quic::QuicStreamId stream_; + webtransport::SendGroupId group_; + }; + + // WebTransport requires individual sessions to have the same urgency as their + // control streams; in a naive implementation, that would mean that both would + // get the same urgency N, but we also want for the control streams to have + // higher priority than WebTransport user data. In order to achieve that, we + // enter control streams at urgency 2 * N + 1, and data streams at urgency + // 2 * N. + static constexpr int RemapUrgency(int urgency, bool is_http) { + return urgency * 2 + (is_http ? 1 : 0); + } + + // Scheduler for individual WebTransport send groups. + using Subscheduler = + quiche::BTreeScheduler<QuicStreamId, webtransport::SendOrder>; + + // Top-level scheduler used to multiplex WebTransport sessions and individual + // HTTP/3 streams. + quiche::BTreeScheduler<ScheduleKey, int> main_schedule_; + // Records of priority for every stream; used when looking up WebTransport + // session associated with an individual stream. + absl::flat_hash_map<QuicStreamId, QuicStreamPriority> priorities_; + // Schedulers for individual WebTransport send groups. + absl::flat_hash_map<ScheduleKey, Subscheduler> + web_transport_session_schedulers_; +}; + +} // namespace quic + +#endif // QUICHE_QUIC_CORE_WEB_TRANSPORT_WRITE_BLOCKED_LIST_H_
diff --git a/quiche/quic/core/web_transport_write_blocked_list_test.cc b/quiche/quic/core/web_transport_write_blocked_list_test.cc new file mode 100644 index 0000000..f65450f --- /dev/null +++ b/quiche/quic/core/web_transport_write_blocked_list_test.cc
@@ -0,0 +1,515 @@ +// Copyright 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/web_transport_write_blocked_list.h" + +#include <algorithm> +#include <array> +#include <cstddef> +#include <iterator> +#include <vector> + +#include "absl/algorithm/container.h" +#include "quiche/quic/core/quic_stream_priority.h" +#include "quiche/quic/core/quic_types.h" +#include "quiche/quic/test_tools/quic_test_utils.h" +#include "quiche/common/platform/api/quiche_expect_bug.h" +#include "quiche/common/platform/api/quiche_test.h" + +namespace quic::test { +namespace { + +using ::testing::ElementsAre; +using ::testing::ElementsAreArray; + +class WebTransportWriteBlockedListTest : public ::quiche::test::QuicheTest { + protected: + void RegisterStaticStream(QuicStreamId id) { + list_.RegisterStream(id, /*is_static_stream=*/true, + QuicStreamPriority::Default(QuicPriorityType::kHttp)); + } + void RegisterHttpStream(QuicStreamId id, + int urgency = HttpStreamPriority::kDefaultUrgency) { + HttpStreamPriority priority; + priority.urgency = urgency; + list_.RegisterStream(id, /*is_static_stream=*/false, + QuicStreamPriority(priority)); + } + void RegisterWebTransportDataStream(QuicStreamId id, + WebTransportStreamPriority priority) { + list_.RegisterStream(id, /*is_static_stream=*/false, + QuicStreamPriority(priority)); + } + + std::vector<QuicStreamId> PopAll() { + std::vector<QuicStreamId> result; + size_t expected_count = list_.NumBlockedStreams(); + while (list_.NumBlockedStreams() > 0) { + EXPECT_TRUE(list_.HasWriteBlockedDataStreams() || + list_.HasWriteBlockedSpecialStream()); + result.push_back(list_.PopFront()); + EXPECT_EQ(list_.NumBlockedStreams(), --expected_count); + } + return result; + } + + WebTransportWriteBlockedList list_; +}; + +TEST_F(WebTransportWriteBlockedListTest, BasicHttpStreams) { + RegisterHttpStream(1); + RegisterHttpStream(2); + RegisterHttpStream(3, HttpStreamPriority::kDefaultUrgency + 1); + RegisterStaticStream(4); + + EXPECT_EQ(list_.GetPriorityOfStream(1), + QuicStreamPriority::Default(QuicPriorityType::kHttp)); + EXPECT_EQ(list_.GetPriorityOfStream(2), + QuicStreamPriority::Default(QuicPriorityType::kHttp)); + EXPECT_EQ(list_.GetPriorityOfStream(3).http().urgency, 4); + + EXPECT_EQ(list_.NumBlockedStreams(), 0); + EXPECT_EQ(list_.NumBlockedSpecialStreams(), 0); + list_.AddStream(1); + list_.AddStream(2); + list_.AddStream(3); + list_.AddStream(4); + EXPECT_EQ(list_.NumBlockedStreams(), 4); + EXPECT_EQ(list_.NumBlockedSpecialStreams(), 1); + + EXPECT_THAT(PopAll(), ElementsAre(4, 3, 1, 2)); + EXPECT_EQ(list_.NumBlockedStreams(), 0); + EXPECT_EQ(list_.NumBlockedSpecialStreams(), 0); + + list_.AddStream(2); + list_.AddStream(3); + list_.AddStream(4); + list_.AddStream(1); + EXPECT_THAT(PopAll(), ElementsAre(4, 3, 2, 1)); +} + +TEST_F(WebTransportWriteBlockedListTest, RegisterDuplicateStream) { + RegisterHttpStream(1); + EXPECT_QUICHE_BUG(RegisterHttpStream(1), "already registered"); +} + +TEST_F(WebTransportWriteBlockedListTest, UnregisterMissingStream) { + EXPECT_QUICHE_BUG(list_.UnregisterStream(1), "not found"); +} + +TEST_F(WebTransportWriteBlockedListTest, GetPriorityMissingStream) { + EXPECT_QUICHE_BUG(list_.GetPriorityOfStream(1), "not found"); +} + +TEST_F(WebTransportWriteBlockedListTest, PopFrontMissing) { + RegisterHttpStream(1); + list_.AddStream(1); + EXPECT_EQ(list_.PopFront(), 1); + EXPECT_QUICHE_BUG(list_.PopFront(), "no streams scheduled"); +} + +TEST_F(WebTransportWriteBlockedListTest, HasWriteBlockedDataStreams) { + RegisterStaticStream(1); + RegisterHttpStream(2); + + EXPECT_FALSE(list_.HasWriteBlockedDataStreams()); + list_.AddStream(1); + EXPECT_FALSE(list_.HasWriteBlockedDataStreams()); + list_.AddStream(2); + EXPECT_TRUE(list_.HasWriteBlockedDataStreams()); + EXPECT_EQ(list_.PopFront(), 1); + EXPECT_TRUE(list_.HasWriteBlockedDataStreams()); + EXPECT_EQ(list_.PopFront(), 2); + EXPECT_FALSE(list_.HasWriteBlockedDataStreams()); +} + +TEST_F(WebTransportWriteBlockedListTest, NestedStreams) { + RegisterHttpStream(1); + RegisterHttpStream(2); + RegisterWebTransportDataStream(3, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(4, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(5, WebTransportStreamPriority{2, 0, 0}); + RegisterWebTransportDataStream(6, WebTransportStreamPriority{2, 0, 0}); + EXPECT_EQ(list_.NumBlockedStreams(), 0); + + list_.AddStream(3); + list_.AddStream(5); + list_.AddStream(4); + list_.AddStream(6); + EXPECT_EQ(list_.NumBlockedStreams(), 4); + EXPECT_THAT(PopAll(), ElementsAre(3, 5, 4, 6)); + EXPECT_EQ(list_.NumBlockedStreams(), 0); + + list_.AddStream(3); + list_.AddStream(4); + list_.AddStream(5); + EXPECT_EQ(list_.NumBlockedStreams(), 3); + EXPECT_THAT(PopAll(), ElementsAre(3, 5, 4)); + EXPECT_EQ(list_.NumBlockedStreams(), 0); + + list_.AddStream(4); + list_.AddStream(5); + list_.AddStream(6); + EXPECT_EQ(list_.NumBlockedStreams(), 3); + EXPECT_THAT(PopAll(), ElementsAre(4, 5, 6)); + EXPECT_EQ(list_.NumBlockedStreams(), 0); + + list_.AddStream(6); + list_.AddStream(3); + list_.AddStream(4); + list_.AddStream(5); + EXPECT_EQ(list_.NumBlockedStreams(), 4); + EXPECT_THAT(PopAll(), ElementsAre(6, 3, 5, 4)); + EXPECT_EQ(list_.NumBlockedStreams(), 0); + + list_.AddStream(6); + list_.AddStream(5); + list_.AddStream(4); + list_.AddStream(3); + EXPECT_EQ(list_.NumBlockedStreams(), 4); + EXPECT_THAT(PopAll(), ElementsAre(6, 4, 5, 3)); + EXPECT_EQ(list_.NumBlockedStreams(), 0); +} + +TEST_F(WebTransportWriteBlockedListTest, NestedStreamsWithHigherPriorityGroup) { + RegisterHttpStream(1, HttpStreamPriority::kDefaultUrgency + 1); + RegisterHttpStream(2); + RegisterWebTransportDataStream(3, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(4, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(5, WebTransportStreamPriority{2, 0, 0}); + RegisterWebTransportDataStream(6, WebTransportStreamPriority{2, 0, 0}); + EXPECT_EQ(list_.NumBlockedStreams(), 0); + + list_.AddStream(3); + list_.AddStream(5); + list_.AddStream(4); + list_.AddStream(6); + EXPECT_EQ(list_.NumBlockedStreams(), 4); + EXPECT_THAT(PopAll(), ElementsAre(3, 4, 5, 6)); + EXPECT_EQ(list_.NumBlockedStreams(), 0); + + list_.AddStream(3); + list_.AddStream(4); + list_.AddStream(5); + EXPECT_EQ(list_.NumBlockedStreams(), 3); + EXPECT_THAT(PopAll(), ElementsAre(3, 4, 5)); + EXPECT_EQ(list_.NumBlockedStreams(), 0); + + list_.AddStream(4); + list_.AddStream(5); + list_.AddStream(6); + EXPECT_EQ(list_.NumBlockedStreams(), 3); + EXPECT_THAT(PopAll(), ElementsAre(4, 5, 6)); + EXPECT_EQ(list_.NumBlockedStreams(), 0); + + list_.AddStream(6); + list_.AddStream(3); + list_.AddStream(4); + list_.AddStream(5); + EXPECT_EQ(list_.NumBlockedStreams(), 4); + EXPECT_THAT(PopAll(), ElementsAre(3, 4, 6, 5)); + EXPECT_EQ(list_.NumBlockedStreams(), 0); + + list_.AddStream(6); + list_.AddStream(5); + list_.AddStream(4); + list_.AddStream(3); + EXPECT_EQ(list_.NumBlockedStreams(), 4); + EXPECT_THAT(PopAll(), ElementsAre(4, 3, 6, 5)); + EXPECT_EQ(list_.NumBlockedStreams(), 0); +} + +TEST_F(WebTransportWriteBlockedListTest, NestedStreamVsControlStream) { + RegisterHttpStream(1); + RegisterWebTransportDataStream(2, WebTransportStreamPriority{1, 0, 0}); + + list_.AddStream(2); + list_.AddStream(1); + EXPECT_THAT(PopAll(), ElementsAre(1, 2)); + + list_.AddStream(1); + list_.AddStream(2); + EXPECT_THAT(PopAll(), ElementsAre(1, 2)); +} + +TEST_F(WebTransportWriteBlockedListTest, NestedStreamsSendOrder) { + RegisterHttpStream(1); + RegisterWebTransportDataStream(2, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(3, WebTransportStreamPriority{1, 0, 100}); + RegisterWebTransportDataStream(4, WebTransportStreamPriority{1, 0, -100}); + + list_.AddStream(4); + list_.AddStream(3); + list_.AddStream(2); + list_.AddStream(1); + EXPECT_THAT(PopAll(), ElementsAre(1, 3, 2, 4)); +} + +TEST_F(WebTransportWriteBlockedListTest, NestedStreamsDifferentGroups) { + RegisterHttpStream(1); + RegisterWebTransportDataStream(2, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(3, WebTransportStreamPriority{1, 1, 100}); + RegisterWebTransportDataStream(4, WebTransportStreamPriority{1, 7, -100}); + + list_.AddStream(4); + list_.AddStream(3); + list_.AddStream(2); + list_.AddStream(1); + EXPECT_THAT(PopAll(), ElementsAre(1, 4, 3, 2)); + + list_.AddStream(1); + list_.AddStream(2); + list_.AddStream(3); + list_.AddStream(4); + EXPECT_THAT(PopAll(), ElementsAre(1, 2, 3, 4)); +} + +TEST_F(WebTransportWriteBlockedListTest, NestedStreamsDifferentSession) { + RegisterWebTransportDataStream(1, WebTransportStreamPriority{10, 0, 0}); + RegisterWebTransportDataStream(2, WebTransportStreamPriority{11, 0, 100}); + RegisterWebTransportDataStream(3, WebTransportStreamPriority{12, 0, -100}); + + list_.AddStream(3); + list_.AddStream(2); + list_.AddStream(1); + EXPECT_THAT(PopAll(), ElementsAre(3, 2, 1)); + + list_.AddStream(1); + list_.AddStream(2); + list_.AddStream(3); + EXPECT_THAT(PopAll(), ElementsAre(1, 2, 3)); +} + +TEST_F(WebTransportWriteBlockedListTest, UnregisterScheduledStreams) { + RegisterHttpStream(1); + RegisterHttpStream(2); + RegisterWebTransportDataStream(3, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(4, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(5, WebTransportStreamPriority{2, 0, 0}); + RegisterWebTransportDataStream(6, WebTransportStreamPriority{2, 0, 0}); + + EXPECT_EQ(list_.NumBlockedStreams(), 0); + for (QuicStreamId id : {1, 2, 3, 4, 5, 6}) { + list_.AddStream(id); + } + EXPECT_EQ(list_.NumBlockedStreams(), 6); + + list_.UnregisterStream(1); + EXPECT_EQ(list_.NumBlockedStreams(), 5); + list_.UnregisterStream(3); + EXPECT_EQ(list_.NumBlockedStreams(), 4); + list_.UnregisterStream(4); + EXPECT_EQ(list_.NumBlockedStreams(), 3); + list_.UnregisterStream(5); + EXPECT_EQ(list_.NumBlockedStreams(), 2); + list_.UnregisterStream(6); + EXPECT_EQ(list_.NumBlockedStreams(), 1); + list_.UnregisterStream(2); + EXPECT_EQ(list_.NumBlockedStreams(), 0); +} + +TEST_F(WebTransportWriteBlockedListTest, UnregisterUnscheduledStreams) { + RegisterHttpStream(1); + RegisterHttpStream(2); + RegisterWebTransportDataStream(3, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(4, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(5, WebTransportStreamPriority{2, 0, 0}); + RegisterWebTransportDataStream(6, WebTransportStreamPriority{2, 0, 0}); + + EXPECT_EQ(list_.NumRegisteredHttpStreams(), 2); + EXPECT_EQ(list_.NumRegisteredGroups(), 2); + list_.UnregisterStream(1); + EXPECT_EQ(list_.NumRegisteredHttpStreams(), 1); + EXPECT_EQ(list_.NumRegisteredGroups(), 2); + list_.UnregisterStream(3); + EXPECT_EQ(list_.NumRegisteredHttpStreams(), 1); + EXPECT_EQ(list_.NumRegisteredGroups(), 2); + list_.UnregisterStream(4); + EXPECT_EQ(list_.NumRegisteredHttpStreams(), 1); + EXPECT_EQ(list_.NumRegisteredGroups(), 1); + + list_.UnregisterStream(5); + EXPECT_EQ(list_.NumRegisteredHttpStreams(), 1); + EXPECT_EQ(list_.NumRegisteredGroups(), 1); + list_.UnregisterStream(6); + EXPECT_EQ(list_.NumRegisteredHttpStreams(), 1); + EXPECT_EQ(list_.NumRegisteredGroups(), 0); + list_.UnregisterStream(2); + EXPECT_EQ(list_.NumRegisteredHttpStreams(), 0); + EXPECT_EQ(list_.NumRegisteredGroups(), 0); + + RegisterHttpStream(1); + RegisterHttpStream(2); + RegisterWebTransportDataStream(3, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(4, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(5, WebTransportStreamPriority{2, 0, 0}); + RegisterWebTransportDataStream(6, WebTransportStreamPriority{2, 0, 0}); +} + +TEST_F(WebTransportWriteBlockedListTest, IsStreamBlocked) { + RegisterHttpStream(1); + RegisterWebTransportDataStream(2, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(3, WebTransportStreamPriority{9, 0, 0}); + + EXPECT_FALSE(list_.IsStreamBlocked(1)); + EXPECT_FALSE(list_.IsStreamBlocked(2)); + EXPECT_FALSE(list_.IsStreamBlocked(3)); + + list_.AddStream(3); + EXPECT_FALSE(list_.IsStreamBlocked(1)); + EXPECT_FALSE(list_.IsStreamBlocked(2)); + EXPECT_TRUE(list_.IsStreamBlocked(3)); + + list_.AddStream(1); + EXPECT_TRUE(list_.IsStreamBlocked(1)); + EXPECT_FALSE(list_.IsStreamBlocked(2)); + EXPECT_TRUE(list_.IsStreamBlocked(3)); + + ASSERT_EQ(list_.PopFront(), 1); + EXPECT_FALSE(list_.IsStreamBlocked(1)); + EXPECT_FALSE(list_.IsStreamBlocked(2)); + EXPECT_TRUE(list_.IsStreamBlocked(3)); +} + +TEST_F(WebTransportWriteBlockedListTest, UpdatePriorityHttp) { + RegisterHttpStream(1); + RegisterHttpStream(2); + RegisterHttpStream(3); + + list_.AddStream(1); + list_.AddStream(2); + list_.AddStream(3); + EXPECT_THAT(PopAll(), ElementsAre(1, 2, 3)); + + list_.UpdateStreamPriority( + 2, QuicStreamPriority( + HttpStreamPriority{HttpStreamPriority::kMaximumUrgency, false})); + + list_.AddStream(1); + list_.AddStream(2); + list_.AddStream(3); + EXPECT_THAT(PopAll(), ElementsAre(2, 1, 3)); +} + +TEST_F(WebTransportWriteBlockedListTest, UpdatePriorityWebTransport) { + RegisterWebTransportDataStream(1, WebTransportStreamPriority{0, 0, 0}); + RegisterWebTransportDataStream(2, WebTransportStreamPriority{0, 0, 0}); + RegisterWebTransportDataStream(3, WebTransportStreamPriority{0, 0, 0}); + + list_.AddStream(1); + list_.AddStream(2); + list_.AddStream(3); + EXPECT_THAT(PopAll(), ElementsAre(1, 2, 3)); + + list_.UpdateStreamPriority( + 2, QuicStreamPriority(WebTransportStreamPriority{0, 0, 1})); + + list_.AddStream(1); + list_.AddStream(2); + list_.AddStream(3); + EXPECT_THAT(PopAll(), ElementsAre(2, 1, 3)); +} + +TEST_F(WebTransportWriteBlockedListTest, UpdatePriorityControlStream) { + RegisterHttpStream(1); + RegisterHttpStream(2); + RegisterWebTransportDataStream(3, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(4, WebTransportStreamPriority{2, 0, 0}); + + list_.AddStream(3); + list_.AddStream(4); + EXPECT_THAT(PopAll(), ElementsAre(3, 4)); + list_.AddStream(4); + list_.AddStream(3); + EXPECT_THAT(PopAll(), ElementsAre(4, 3)); + + list_.UpdateStreamPriority( + 2, QuicStreamPriority( + HttpStreamPriority{HttpStreamPriority::kMaximumUrgency, false})); + + list_.AddStream(3); + list_.AddStream(4); + EXPECT_THAT(PopAll(), ElementsAre(4, 3)); + list_.AddStream(4); + list_.AddStream(3); + EXPECT_THAT(PopAll(), ElementsAre(4, 3)); +} + +TEST_F(WebTransportWriteBlockedListTest, ShouldYield) { + RegisterHttpStream(1); + RegisterWebTransportDataStream(2, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(3, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(4, WebTransportStreamPriority{1, 0, 10}); + + EXPECT_FALSE(list_.ShouldYield(1)); + EXPECT_FALSE(list_.ShouldYield(2)); + EXPECT_FALSE(list_.ShouldYield(3)); + EXPECT_FALSE(list_.ShouldYield(4)); + + list_.AddStream(1); + EXPECT_FALSE(list_.ShouldYield(1)); + EXPECT_TRUE(list_.ShouldYield(2)); + EXPECT_TRUE(list_.ShouldYield(3)); + EXPECT_TRUE(list_.ShouldYield(4)); + PopAll(); + + list_.AddStream(2); + EXPECT_FALSE(list_.ShouldYield(1)); + EXPECT_FALSE(list_.ShouldYield(2)); + EXPECT_TRUE(list_.ShouldYield(3)); + EXPECT_FALSE(list_.ShouldYield(4)); + PopAll(); + + list_.AddStream(4); + EXPECT_FALSE(list_.ShouldYield(1)); + EXPECT_TRUE(list_.ShouldYield(2)); + EXPECT_TRUE(list_.ShouldYield(3)); + EXPECT_FALSE(list_.ShouldYield(4)); + PopAll(); +} + +TEST_F(WebTransportWriteBlockedListTest, RandomizedTest) { + RegisterHttpStream(1); + RegisterHttpStream(2, HttpStreamPriority::kMinimumUrgency); + RegisterHttpStream(3, HttpStreamPriority::kMaximumUrgency); + RegisterWebTransportDataStream(4, WebTransportStreamPriority{1, 0, 0}); + RegisterWebTransportDataStream(5, WebTransportStreamPriority{2, 0, +1}); + RegisterWebTransportDataStream(6, WebTransportStreamPriority{2, 0, -1}); + RegisterWebTransportDataStream(7, WebTransportStreamPriority{3, 8, 0}); + RegisterWebTransportDataStream(8, WebTransportStreamPriority{3, 8, 100}); + RegisterWebTransportDataStream(9, WebTransportStreamPriority{3, 8, 20000}); + RegisterHttpStream(10, HttpStreamPriority::kDefaultUrgency + 1); + // The priorities of the streams above are arranged so that the priorities of + // all streams above are strictly ordered (i.e. there are no streams that + // would be round-robined). + constexpr std::array<QuicStreamId, 10> order = {3, 9, 8, 7, 10, + 1, 4, 2, 5, 6}; + + SimpleRandom random; + for (int i = 0; i < 1000; ++i) { + // Shuffle the streams. + std::vector<QuicStreamId> pushed_streams(order.begin(), order.end()); + for (int j = pushed_streams.size() - 1; j > 0; --j) { + std::swap(pushed_streams[j], + pushed_streams[random.RandUint64() % (j + 1)]); + } + + size_t stream_count = 1 + random.RandUint64() % order.size(); + pushed_streams.resize(stream_count); + + for (QuicStreamId id : pushed_streams) { + list_.AddStream(id); + } + + std::vector<QuicStreamId> expected_streams; + absl::c_copy_if( + order, std::back_inserter(expected_streams), [&](QuicStreamId id) { + return absl::c_find(pushed_streams, id) != pushed_streams.end(); + }); + ASSERT_THAT(PopAll(), ElementsAreArray(expected_streams)); + } +} + +} // namespace +} // namespace quic::test