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