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
