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);