Templatize PriorityWriteScheduler.
This allows it to store a QuicStreamPriority object for each registered stream,
so that the incremental bit can be accessed by QuicWriteBlockedList. Otherwise
no behavioral change is introduced.
Also change QuicStreamPriority::urgency type from uint8_t to int to match the
type of QuicStreamPriority::kMinimumUrgency,
QuicStreamPriority::kMaximumUrgency, QuicStreamPriority::kDefaultUrgency,
spdy::SpdyPriority, PriorityWriteScheduler::kHighestPriority and
PriorityWriteScheduler::kLowestPriority.
PiperOrigin-RevId: 502978569
diff --git a/quiche/http2/core/priority_write_scheduler.h b/quiche/http2/core/priority_write_scheduler.h
index 54181f3..4e32b90 100644
--- a/quiche/http2/core/priority_write_scheduler.h
+++ b/quiche/http2/core/priority_write_scheduler.h
@@ -29,11 +29,20 @@
class PriorityWriteSchedulerPeer;
}
+// SpdyPriority is an integer type, so this functor can be used both as
+// PriorityTypeToInt and as IntToPriorityType.
+struct QUICHE_EXPORT SpdyPriorityToSpdyPriority {
+ spdy::SpdyPriority operator()(spdy::SpdyPriority priority) {
+ return priority;
+ }
+};
+
// PriorityWriteScheduler manages the order in which HTTP/2 or HTTP/3 streams
-// are written. Each stream has a priority, which is an integer between 0 and 7.
-// Higher priority (lower integer value) streams are always given precedence
-// over lower priority (higher value) streams, as long as the higher priority
-// stream is not blocked.
+// are written. Each stream has a priority of type PriorityType. This includes
+// an integer between 0 and 7, and optionally other information that is stored
+// but otherwise ignored by this class. Higher priority (lower integer value)
+// streams are always given precedence over lower priority (higher value)
+// streams, as long as the higher priority stream is not blocked.
//
// Each stream can be in one of two states: ready or not ready (for writing).
// Ready state is changed by calling the MarkStreamReady() and
@@ -41,11 +50,11 @@
// by PopNextReadyStream(). When returned by that method, the stream's state
// changes to not ready.
//
-template <typename StreamIdType>
+template <typename StreamIdType, typename PriorityType = spdy::SpdyPriority,
+ typename PriorityTypeToInt = SpdyPriorityToSpdyPriority,
+ typename IntToPriorityType = SpdyPriorityToSpdyPriority>
class QUICHE_EXPORT PriorityWriteScheduler {
public:
- using PriorityType = spdy::SpdyPriority;
-
static constexpr int kHighestPriority = 0;
static constexpr int kLowestPriority = 7;
@@ -57,8 +66,8 @@
//
// Preconditions: `stream_id` should be unregistered.
void RegisterStream(StreamIdType stream_id, PriorityType priority) {
- auto stream_info =
- std::make_unique<StreamInfo>(StreamInfo{priority, stream_id, false});
+ auto stream_info = std::make_unique<StreamInfo>(
+ StreamInfo{std::move(priority), stream_id, false});
bool inserted =
stream_infos_.insert(std::make_pair(stream_id, std::move(stream_info)))
.second;
@@ -78,8 +87,10 @@
}
const StreamInfo* const stream_info = it->second.get();
if (stream_info->ready) {
- bool erased = Erase(&priority_infos_[stream_info->priority].ready_list,
- stream_info);
+ bool erased =
+ Erase(&priority_infos_[PriorityTypeToInt()(stream_info->priority)]
+ .ready_list,
+ stream_info);
QUICHE_DCHECK(erased);
}
stream_infos_.erase(it);
@@ -97,7 +108,7 @@
auto it = stream_infos_.find(stream_id);
if (it == stream_infos_.end()) {
QUICHE_DVLOG(1) << "Stream " << stream_id << " not registered";
- return kLowestPriority;
+ return IntToPriorityType()(kLowestPriority);
}
return it->second->priority;
}
@@ -112,18 +123,30 @@
QUICHE_DVLOG(1) << "Stream " << stream_id << " not registered";
return;
}
+
StreamInfo* const stream_info = it->second.get();
if (stream_info->priority == priority) {
return;
}
- if (stream_info->ready) {
- bool erased = Erase(&priority_infos_[stream_info->priority].ready_list,
- stream_info);
+
+ // Only move `stream_info` to a different bucket if the integral priority
+ // value changes.
+ if (PriorityTypeToInt()(stream_info->priority) !=
+ PriorityTypeToInt()(priority) &&
+ stream_info->ready) {
+ bool erased =
+ Erase(&priority_infos_[PriorityTypeToInt()(stream_info->priority)]
+ .ready_list,
+ stream_info);
QUICHE_DCHECK(erased);
- priority_infos_[priority].ready_list.push_back(stream_info);
+ priority_infos_[PriorityTypeToInt()(priority)].ready_list.push_back(
+ stream_info);
++num_ready_streams_;
}
- stream_info->priority = priority;
+
+ // But override `priority` for the stream regardless of the integral value,
+ // because it might contain additional information.
+ stream_info->priority = std::move(priority);
}
// Records time (in microseconds) of a read/write event for the given
@@ -136,7 +159,8 @@
QUICHE_BUG(spdy_bug_19_4) << "Stream " << stream_id << " not registered";
return;
}
- PriorityInfo& priority_info = priority_infos_[it->second->priority];
+ PriorityInfo& priority_info =
+ priority_infos_[PriorityTypeToInt()(it->second->priority)];
priority_info.last_event_time_usec =
std::max(priority_info.last_event_time_usec, now_in_usec);
}
@@ -154,7 +178,8 @@
}
int64_t last_event_time_usec = 0;
const StreamInfo* const stream_info = it->second.get();
- for (PriorityType p = kHighestPriority; p < stream_info->priority; ++p) {
+ for (int p = kHighestPriority;
+ p < PriorityTypeToInt()(stream_info->priority); ++p) {
last_event_time_usec = std::max(last_event_time_usec,
priority_infos_[p].last_event_time_usec);
}
@@ -176,7 +201,7 @@
//
// Preconditions: `HasReadyStreams() == true`
std::tuple<StreamIdType, PriorityType> PopNextReadyStreamAndPriority() {
- for (PriorityType p = kHighestPriority; p <= kLowestPriority; ++p) {
+ for (int p = kHighestPriority; p <= kLowestPriority; ++p) {
ReadyList& ready_list = priority_infos_[p].ready_list;
if (!ready_list.empty()) {
StreamInfo* const info = ready_list.front();
@@ -190,7 +215,7 @@
}
}
QUICHE_BUG(spdy_bug_19_6) << "No ready streams available";
- return std::make_tuple(0, kLowestPriority);
+ return std::make_tuple(0, IntToPriorityType()(kLowestPriority));
}
// Returns true if there's another stream ahead of the given stream in the
@@ -207,7 +232,8 @@
// If there's a higher priority stream, this stream should yield.
const StreamInfo* const stream_info = it->second.get();
- for (PriorityType p = kHighestPriority; p < stream_info->priority; ++p) {
+ for (int p = kHighestPriority;
+ p < PriorityTypeToInt()(stream_info->priority); ++p) {
if (!priority_infos_[p].ready_list.empty()) {
return true;
}
@@ -215,7 +241,8 @@
// If this priority level is empty, or this stream is the next up, there's
// no need to yield.
- const auto& ready_list = priority_infos_[it->second->priority].ready_list;
+ const auto& ready_list =
+ priority_infos_[PriorityTypeToInt()(it->second->priority)].ready_list;
if (ready_list.empty() || ready_list.front()->stream_id == stream_id) {
return false;
}
@@ -240,7 +267,8 @@
if (stream_info->ready) {
return;
}
- ReadyList& ready_list = priority_infos_[stream_info->priority].ready_list;
+ ReadyList& ready_list =
+ priority_infos_[PriorityTypeToInt()(stream_info->priority)].ready_list;
if (add_to_front) {
ready_list.push_front(stream_info);
} else {
@@ -264,8 +292,9 @@
if (!stream_info->ready) {
return;
}
- bool erased =
- Erase(&priority_infos_[stream_info->priority].ready_list, stream_info);
+ bool erased = Erase(
+ &priority_infos_[PriorityTypeToInt()(stream_info->priority)].ready_list,
+ stream_info);
QUICHE_DCHECK(erased);
stream_info->ready = false;
}
diff --git a/quiche/quic/core/quic_session.h b/quiche/quic/core/quic_session.h
index 4ef5579..5c97f1a 100644
--- a/quiche/quic/core/quic_session.h
+++ b/quiche/quic/core/quic_session.h
@@ -708,7 +708,7 @@
virtual bool ShouldProcessPendingStreamImmediately() const { return true; }
spdy::SpdyPriority GetSpdyPriorityofStream(QuicStreamId stream_id) const {
- return write_blocked_streams_.GetSpdyPriorityofStream(stream_id);
+ return write_blocked_streams_.GetPriorityofStream(stream_id).urgency;
}
size_t pending_streams_size() const { return pending_stream_map_.size(); }
diff --git a/quiche/quic/core/quic_stream_priority.h b/quiche/quic/core/quic_stream_priority.h
index 04db767..de2cce2 100644
--- a/quiche/quic/core/quic_stream_priority.h
+++ b/quiche/quic/core/quic_stream_priority.h
@@ -27,7 +27,7 @@
static constexpr absl::string_view kUrgencyKey = "u";
static constexpr absl::string_view kIncrementalKey = "i";
- uint8_t urgency = kDefaultUrgency;
+ int urgency = kDefaultUrgency;
bool incremental = kDefaultIncremental;
bool operator==(const QuicStreamPriority& other) const {
@@ -40,6 +40,19 @@
}
};
+// Functors to be used as template parameters for PriorityWriteScheduler.
+struct QUICHE_EXPORT QuicStreamPriorityToInt {
+ int operator()(const QuicStreamPriority& priority) {
+ return priority.urgency;
+ }
+};
+
+struct QUICHE_EXPORT IntToQuicStreamPriority {
+ QuicStreamPriority operator()(int urgency) {
+ return QuicStreamPriority{urgency};
+ }
+};
+
// Serializes the Priority Field Value for a PRIORITY_UPDATE frame.
QUICHE_EXPORT std::string SerializePriorityFieldValue(
QuicStreamPriority priority);
diff --git a/quiche/quic/core/quic_write_blocked_list.cc b/quiche/quic/core/quic_write_blocked_list.cc
index 473b154..2497907 100644
--- a/quiche/quic/core/quic_write_blocked_list.cc
+++ b/quiche/quic/core/quic_write_blocked_list.cc
@@ -38,7 +38,7 @@
const auto id_and_priority =
priority_write_scheduler_.PopNextReadyStreamAndPriority();
const QuicStreamId id = std::get<0>(id_and_priority);
- const spdy::SpdyPriority priority = std::get<1>(id_and_priority);
+ const spdy::SpdyPriority priority = std::get<1>(id_and_priority).urgency;
if (!priority_write_scheduler_.HasReadyStreams()) {
// If no streams are blocked, don't bother latching. This stream will be
@@ -65,7 +65,7 @@
return;
}
- priority_write_scheduler_.RegisterStream(stream_id, priority.urgency);
+ priority_write_scheduler_.RegisterStream(stream_id, priority);
}
void QuicWriteBlockedList::UnregisterStream(QuicStreamId stream_id,
@@ -80,8 +80,7 @@
void QuicWriteBlockedList::UpdateStreamPriority(
QuicStreamId stream_id, const QuicStreamPriority& new_priority) {
QUICHE_DCHECK(!static_stream_collection_.IsRegistered(stream_id));
- priority_write_scheduler_.UpdateStreamPriority(stream_id,
- new_priority.urgency);
+ priority_write_scheduler_.UpdateStreamPriority(stream_id, new_priority);
}
void QuicWriteBlockedList::UpdateBytesForStream(QuicStreamId stream_id,
diff --git a/quiche/quic/core/quic_write_blocked_list.h b/quiche/quic/core/quic_write_blocked_list.h
index 1bbff6e..0ad2c2d 100644
--- a/quiche/quic/core/quic_write_blocked_list.h
+++ b/quiche/quic/core/quic_write_blocked_list.h
@@ -50,7 +50,7 @@
bool ShouldYield(QuicStreamId id) const;
- spdy::SpdyPriority GetSpdyPriorityofStream(QuicStreamId id) const {
+ QuicStreamPriority GetPriorityofStream(QuicStreamId id) const {
return priority_write_scheduler_.GetStreamPriority(id);
}
@@ -83,7 +83,10 @@
bool IsStreamBlocked(QuicStreamId stream_id) const;
private:
- http2::PriorityWriteScheduler<QuicStreamId> priority_write_scheduler_;
+ http2::PriorityWriteScheduler<QuicStreamId, QuicStreamPriority,
+ QuicStreamPriorityToInt,
+ IntToQuicStreamPriority>
+ priority_write_scheduler_;
// If performing batch writes, this will be the stream ID of the stream doing
// batch writes for this priority level. We will allow this stream to write
diff --git a/quiche/quic/core/quic_write_blocked_list_test.cc b/quiche/quic/core/quic_write_blocked_list_test.cc
index 2acaa35..1847993 100644
--- a/quiche/quic/core/quic_write_blocked_list_test.cc
+++ b/quiche/quic/core/quic_write_blocked_list_test.cc
@@ -17,8 +17,7 @@
constexpr bool kStatic = true;
constexpr bool kNotStatic = false;
-// Default value for `incremental`, see RFC9218.
-// TODO(b/147306124): Add support and tests for `incremental` being true.
+constexpr bool kIncremental = true;
constexpr bool kNotIncremental = false;
class QuicWriteBlockedListTest : public QuicTest {
@@ -43,8 +42,8 @@
return write_blocked_list_.ShouldYield(id);
}
- spdy::SpdyPriority GetSpdyPriorityofStream(QuicStreamId id) const {
- return write_blocked_list_.GetSpdyPriorityofStream(id);
+ QuicStreamPriority GetPriorityofStream(QuicStreamId id) const {
+ return write_blocked_list_.GetPriorityofStream(id);
}
QuicStreamId PopFront() { return write_blocked_list_.PopFront(); }
@@ -83,14 +82,19 @@
// Mark streams blocked in roughly reverse priority order, and
// verify that streams are sorted.
RegisterStream(40, kNotStatic, {kV3LowestPriority, kNotIncremental});
- RegisterStream(23, kNotStatic, {kV3HighestPriority, kNotIncremental});
+ RegisterStream(23, kNotStatic, {kV3HighestPriority, kIncremental});
RegisterStream(17, kNotStatic, {kV3HighestPriority, kNotIncremental});
RegisterStream(1, kStatic, {kV3HighestPriority, kNotIncremental});
RegisterStream(3, kStatic, {kV3HighestPriority, kNotIncremental});
- EXPECT_EQ(kV3LowestPriority, GetSpdyPriorityofStream(40));
- EXPECT_EQ(kV3HighestPriority, GetSpdyPriorityofStream(23));
- EXPECT_EQ(kV3HighestPriority, GetSpdyPriorityofStream(17));
+ EXPECT_EQ(kV3LowestPriority, GetPriorityofStream(40).urgency);
+ EXPECT_EQ(kNotIncremental, GetPriorityofStream(40).incremental);
+
+ EXPECT_EQ(kV3HighestPriority, GetPriorityofStream(23).urgency);
+ EXPECT_EQ(kIncremental, GetPriorityofStream(23).incremental);
+
+ EXPECT_EQ(kV3HighestPriority, GetPriorityofStream(17).urgency);
+ EXPECT_EQ(kNotIncremental, GetPriorityofStream(17).incremental);
AddStream(40);
EXPECT_TRUE(IsStreamBlocked(40));
@@ -302,22 +306,32 @@
TEST_F(QuicWriteBlockedListTest, UpdateStreamPriority) {
RegisterStream(40, kNotStatic, {kV3LowestPriority, kNotIncremental});
- RegisterStream(23, kNotStatic, {6, kNotIncremental});
+ RegisterStream(23, kNotStatic, {6, kIncremental});
RegisterStream(17, kNotStatic, {kV3HighestPriority, kNotIncremental});
RegisterStream(1, kStatic, {2, kNotIncremental});
RegisterStream(3, kStatic, {kV3HighestPriority, kNotIncremental});
- EXPECT_EQ(kV3LowestPriority, GetSpdyPriorityofStream(40));
- EXPECT_EQ(6, GetSpdyPriorityofStream(23));
- EXPECT_EQ(kV3HighestPriority, GetSpdyPriorityofStream(17));
+ EXPECT_EQ(kV3LowestPriority, GetPriorityofStream(40).urgency);
+ EXPECT_EQ(kNotIncremental, GetPriorityofStream(40).incremental);
- UpdateStreamPriority(40, {3, kNotIncremental});
+ EXPECT_EQ(6, GetPriorityofStream(23).urgency);
+ EXPECT_EQ(kIncremental, GetPriorityofStream(23).incremental);
+
+ EXPECT_EQ(kV3HighestPriority, GetPriorityofStream(17).urgency);
+ EXPECT_EQ(kNotIncremental, GetPriorityofStream(17).incremental);
+
+ UpdateStreamPriority(40, {3, kIncremental});
UpdateStreamPriority(23, {kV3HighestPriority, kNotIncremental});
UpdateStreamPriority(17, {5, kNotIncremental});
- EXPECT_EQ(3, GetSpdyPriorityofStream(40));
- EXPECT_EQ(kV3HighestPriority, GetSpdyPriorityofStream(23));
- EXPECT_EQ(5, GetSpdyPriorityofStream(17));
+ EXPECT_EQ(3, GetPriorityofStream(40).urgency);
+ EXPECT_EQ(kIncremental, GetPriorityofStream(40).incremental);
+
+ EXPECT_EQ(kV3HighestPriority, GetPriorityofStream(23).urgency);
+ EXPECT_EQ(kNotIncremental, GetPriorityofStream(23).incremental);
+
+ EXPECT_EQ(5, GetPriorityofStream(17).urgency);
+ EXPECT_EQ(kNotIncremental, GetPriorityofStream(17).incremental);
AddStream(40);
AddStream(23);
@@ -340,8 +354,9 @@
"IsRegistered");
}
-// TODO(bnc): Test that incremental bit can be changed if urgency is the same.
-TEST_F(QuicWriteBlockedListTest, UpdateStreamPrioritySame) {
+TEST_F(QuicWriteBlockedListTest, UpdateStreamPrioritySameUrgency) {
+ // Streams with same urgency are returned by PopFront() in the order they were
+ // added by AddStream().
RegisterStream(1, kNotStatic, {6, kNotIncremental});
RegisterStream(2, kNotStatic, {6, kNotIncremental});
@@ -351,12 +366,18 @@
EXPECT_EQ(1u, PopFront());
EXPECT_EQ(2u, PopFront());
+ // Calling UpdateStreamPriority() on the first stream does not change the
+ // order.
RegisterStream(3, kNotStatic, {6, kNotIncremental});
RegisterStream(4, kNotStatic, {6, kNotIncremental});
- EXPECT_EQ(6, GetSpdyPriorityofStream(3));
- UpdateStreamPriority(3, {6, kNotIncremental});
- EXPECT_EQ(6, GetSpdyPriorityofStream(3));
+ EXPECT_EQ(6, GetPriorityofStream(3).urgency);
+ EXPECT_EQ(kNotIncremental, GetPriorityofStream(3).incremental);
+
+ UpdateStreamPriority(3, {6, kIncremental});
+
+ EXPECT_EQ(6, GetPriorityofStream(3).urgency);
+ EXPECT_EQ(kIncremental, GetPriorityofStream(3).incremental);
AddStream(3);
AddStream(4);
@@ -364,12 +385,18 @@
EXPECT_EQ(3u, PopFront());
EXPECT_EQ(4u, PopFront());
- RegisterStream(5, kNotStatic, {6, kNotIncremental});
- RegisterStream(6, kNotStatic, {6, kNotIncremental});
+ // Calling UpdateStreamPriority() on the second stream does not change the
+ // order.
+ RegisterStream(5, kNotStatic, {6, kIncremental});
+ RegisterStream(6, kNotStatic, {6, kIncremental});
- EXPECT_EQ(6, GetSpdyPriorityofStream(6));
+ EXPECT_EQ(6, GetPriorityofStream(6).urgency);
+ EXPECT_EQ(kIncremental, GetPriorityofStream(6).incremental);
+
UpdateStreamPriority(6, {6, kNotIncremental});
- EXPECT_EQ(6, GetSpdyPriorityofStream(6));
+
+ EXPECT_EQ(6, GetPriorityofStream(6).urgency);
+ EXPECT_EQ(kNotIncremental, GetPriorityofStream(6).incremental);
AddStream(5);
AddStream(6);
