Implement MoQT priority calculation.
The scheme implements priority assignment that follows the semantics of https://github.com/moq-wg/moq-transport/pull/470 and is compatible with how WebTransport scheduling works.
PiperOrigin-RevId: 651476056
diff --git a/build/source_list.bzl b/build/source_list.bzl
index c93905d..34b592f 100644
--- a/build/source_list.bzl
+++ b/build/source_list.bzl
@@ -1512,6 +1512,7 @@
"quic/moqt/moqt_messages.h",
"quic/moqt/moqt_outgoing_queue.h",
"quic/moqt/moqt_parser.h",
+ "quic/moqt/moqt_priority.h",
"quic/moqt/moqt_session.h",
"quic/moqt/moqt_subscribe_windows.h",
"quic/moqt/moqt_track.h",
@@ -1530,6 +1531,8 @@
"quic/moqt/moqt_outgoing_queue_test.cc",
"quic/moqt/moqt_parser.cc",
"quic/moqt/moqt_parser_test.cc",
+ "quic/moqt/moqt_priority.cc",
+ "quic/moqt/moqt_priority_test.cc",
"quic/moqt/moqt_session.cc",
"quic/moqt/moqt_session_test.cc",
"quic/moqt/moqt_subscribe_windows.cc",
diff --git a/build/source_list.gni b/build/source_list.gni
index 634b199..23437ab 100644
--- a/build/source_list.gni
+++ b/build/source_list.gni
@@ -1516,6 +1516,7 @@
"src/quiche/quic/moqt/moqt_messages.h",
"src/quiche/quic/moqt/moqt_outgoing_queue.h",
"src/quiche/quic/moqt/moqt_parser.h",
+ "src/quiche/quic/moqt/moqt_priority.h",
"src/quiche/quic/moqt/moqt_session.h",
"src/quiche/quic/moqt/moqt_subscribe_windows.h",
"src/quiche/quic/moqt/moqt_track.h",
@@ -1534,6 +1535,8 @@
"src/quiche/quic/moqt/moqt_outgoing_queue_test.cc",
"src/quiche/quic/moqt/moqt_parser.cc",
"src/quiche/quic/moqt/moqt_parser_test.cc",
+ "src/quiche/quic/moqt/moqt_priority.cc",
+ "src/quiche/quic/moqt/moqt_priority_test.cc",
"src/quiche/quic/moqt/moqt_session.cc",
"src/quiche/quic/moqt/moqt_session_test.cc",
"src/quiche/quic/moqt/moqt_subscribe_windows.cc",
diff --git a/build/source_list.json b/build/source_list.json
index dc343b0..1b9a333 100644
--- a/build/source_list.json
+++ b/build/source_list.json
@@ -1515,6 +1515,7 @@
"quiche/quic/moqt/moqt_messages.h",
"quiche/quic/moqt/moqt_outgoing_queue.h",
"quiche/quic/moqt/moqt_parser.h",
+ "quiche/quic/moqt/moqt_priority.h",
"quiche/quic/moqt/moqt_session.h",
"quiche/quic/moqt/moqt_subscribe_windows.h",
"quiche/quic/moqt/moqt_track.h",
@@ -1533,6 +1534,8 @@
"quiche/quic/moqt/moqt_outgoing_queue_test.cc",
"quiche/quic/moqt/moqt_parser.cc",
"quiche/quic/moqt/moqt_parser_test.cc",
+ "quiche/quic/moqt/moqt_priority.cc",
+ "quiche/quic/moqt/moqt_priority_test.cc",
"quiche/quic/moqt/moqt_session.cc",
"quiche/quic/moqt/moqt_session_test.cc",
"quiche/quic/moqt/moqt_subscribe_windows.cc",
diff --git a/quiche/quic/moqt/moqt_priority.cc b/quiche/quic/moqt/moqt_priority.cc
new file mode 100644
index 0000000..5528079
--- /dev/null
+++ b/quiche/quic/moqt/moqt_priority.cc
@@ -0,0 +1,70 @@
+// 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/moqt/moqt_priority.h"
+
+#include <cstdint>
+#include <limits>
+
+#include "quiche/web_transport/web_transport.h"
+
+namespace moqt {
+
+namespace {
+template <uint64_t NumBits>
+constexpr uint64_t Flip(uint64_t number) {
+ static_assert(NumBits <= 63);
+ return (1ull << NumBits) - 1 - number;
+}
+template <uint64_t N>
+constexpr uint64_t OnlyLowestNBits(uint64_t value) {
+ static_assert(N <= 62);
+ return value & ((1ull << (N + 1)) - 1);
+}
+} // namespace
+
+// The send order is packed into a signed 64-bit integer as follows:
+// 63: always zero to indicate a positive number
+// 62: 0 for data streams, 1 for control streams
+// 54-61: subscriber priority
+// 46-53: publisher priority
+// (if stream-per-group)
+// 0-45: group ID
+// (if stream-per-object)
+// 20-45: group ID
+// 0-19: object ID
+
+webtransport::SendOrder SendOrderForStream(MoqtPriority subscriber_priority,
+ MoqtPriority publisher_priority,
+ uint64_t group_id,
+ MoqtDeliveryOrder delivery_order) {
+ const int64_t track_bits = (Flip<8>(subscriber_priority) << 54) |
+ (Flip<8>(publisher_priority) << 46);
+ group_id = OnlyLowestNBits<46>(group_id);
+ if (delivery_order == MoqtDeliveryOrder::kAscending) {
+ group_id = Flip<46>(group_id);
+ }
+ return track_bits | group_id;
+}
+
+webtransport::SendOrder SendOrderForStream(MoqtPriority subscriber_priority,
+ MoqtPriority publisher_priority,
+ uint64_t group_id,
+ uint64_t object_id,
+ MoqtDeliveryOrder delivery_order) {
+ const int64_t track_bits = (Flip<8>(subscriber_priority) << 54) |
+ (Flip<8>(publisher_priority) << 46);
+ group_id = OnlyLowestNBits<26>(group_id);
+ object_id = OnlyLowestNBits<20>(object_id);
+ if (delivery_order == MoqtDeliveryOrder::kAscending) {
+ group_id = Flip<26>(group_id);
+ }
+ object_id = Flip<20>(object_id); // Object ID is always ascending.
+ return track_bits | (group_id << 20) | object_id;
+}
+
+const webtransport::SendOrder kMoqtControlStreamSendOrder =
+ std::numeric_limits<webtransport::SendOrder>::max();
+
+} // namespace moqt
diff --git a/quiche/quic/moqt/moqt_priority.h b/quiche/quic/moqt/moqt_priority.h
new file mode 100644
index 0000000..f8c8ad9
--- /dev/null
+++ b/quiche/quic/moqt/moqt_priority.h
@@ -0,0 +1,40 @@
+// 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_MOQT_MOQT_PRIORITY_H_
+#define QUICHE_QUIC_MOQT_MOQT_PRIORITY_H_
+
+#include <cstdint>
+
+#include "quiche/common/platform/api/quiche_export.h"
+#include "quiche/web_transport/web_transport.h"
+
+namespace moqt {
+
+// Priority that can be assigned to a track or individual streams associated
+// with the track by either the publisher or the subscriber.
+using MoqtPriority = uint8_t;
+
+// Indicates the desired order of delivering groups associated with a given
+// track.
+enum class MoqtDeliveryOrder : uint8_t {
+ kAscending,
+ kDescending,
+};
+
+// Computes WebTransport send order for an MoQT data stream with the specified
+// parameters.
+QUICHE_EXPORT webtransport::SendOrder SendOrderForStream(
+ MoqtPriority subscriber_priority, MoqtPriority publisher_priority,
+ uint64_t group_id, MoqtDeliveryOrder delivery_order);
+QUICHE_EXPORT webtransport::SendOrder SendOrderForStream(
+ MoqtPriority subscriber_priority, MoqtPriority publisher_priority,
+ uint64_t group_id, uint64_t object_id, MoqtDeliveryOrder delivery_order);
+
+// WebTransport send order set on the MoQT control stream.
+QUICHE_EXPORT extern const webtransport::SendOrder kMoqtControlStreamSendOrder;
+
+} // namespace moqt
+
+#endif // QUICHE_QUIC_MOQT_MOQT_PRIORITY_H_
diff --git a/quiche/quic/moqt/moqt_priority_test.cc b/quiche/quic/moqt/moqt_priority_test.cc
new file mode 100644
index 0000000..d30c07c
--- /dev/null
+++ b/quiche/quic/moqt/moqt_priority_test.cc
@@ -0,0 +1,59 @@
+// 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/moqt/moqt_priority.h"
+
+#include "quiche/common/platform/api/quiche_test.h"
+
+namespace moqt {
+namespace {
+
+TEST(MoqtPrioirtyTest, TrackPriorities) {
+ // MoQT track priorities are descending (0 is highest), but WebTransport send
+ // order is ascending.
+ EXPECT_GT(SendOrderForStream(0x10, 0x80, 0, MoqtDeliveryOrder::kAscending),
+ SendOrderForStream(0x80, 0x80, 0, MoqtDeliveryOrder::kAscending));
+ EXPECT_GT(SendOrderForStream(0x80, 0x10, 0, MoqtDeliveryOrder::kAscending),
+ SendOrderForStream(0x80, 0x80, 0, MoqtDeliveryOrder::kAscending));
+ // Subscriber priority takes precedence over the sender priority.
+ EXPECT_GT(SendOrderForStream(0x10, 0x80, 0, MoqtDeliveryOrder::kAscending),
+ SendOrderForStream(0x80, 0x10, 0, MoqtDeliveryOrder::kAscending));
+ // Test extreme priority values (0x00 and 0xff).
+ EXPECT_GT(SendOrderForStream(0x00, 0x80, 0, MoqtDeliveryOrder::kAscending),
+ SendOrderForStream(0xff, 0x80, 0, MoqtDeliveryOrder::kAscending));
+ EXPECT_GT(SendOrderForStream(0x80, 0x00, 0, MoqtDeliveryOrder::kAscending),
+ SendOrderForStream(0x80, 0xff, 0, MoqtDeliveryOrder::kAscending));
+}
+
+TEST(MoqtPrioirtyTest, ControlStream) {
+ EXPECT_GT(kMoqtControlStreamSendOrder,
+ SendOrderForStream(0x00, 0x00, 0, MoqtDeliveryOrder::kAscending));
+}
+
+TEST(MoqtPriorityTest, StreamPerGroup) {
+ EXPECT_GT(SendOrderForStream(0x80, 0x80, 0, MoqtDeliveryOrder::kAscending),
+ SendOrderForStream(0x80, 0x80, 1, MoqtDeliveryOrder::kAscending));
+ EXPECT_GT(SendOrderForStream(0x80, 0x80, 1, MoqtDeliveryOrder::kDescending),
+ SendOrderForStream(0x80, 0x80, 0, MoqtDeliveryOrder::kDescending));
+}
+
+TEST(MoqtPriorityTest, StreamPerObject) {
+ // Objects within the same group.
+ EXPECT_GT(
+ SendOrderForStream(0x80, 0x80, 0, 0, MoqtDeliveryOrder::kAscending),
+ SendOrderForStream(0x80, 0x80, 0, 1, MoqtDeliveryOrder::kAscending));
+ EXPECT_GT(
+ SendOrderForStream(0x80, 0x80, 0, 0, MoqtDeliveryOrder::kDescending),
+ SendOrderForStream(0x80, 0x80, 0, 1, MoqtDeliveryOrder::kDescending));
+ // Objects of different groups.
+ EXPECT_GT(
+ SendOrderForStream(0x80, 0x80, 0, 1, MoqtDeliveryOrder::kAscending),
+ SendOrderForStream(0x80, 0x80, 1, 0, MoqtDeliveryOrder::kAscending));
+ EXPECT_GT(
+ SendOrderForStream(0x80, 0x80, 1, 1, MoqtDeliveryOrder::kDescending),
+ SendOrderForStream(0x80, 0x80, 0, 0, MoqtDeliveryOrder::kDescending));
+}
+
+} // namespace
+} // namespace moqt
