gfe-relnote: Move LifoWriteScheduler from gfe/gfe2/spdy/ to third_party/spdy/core to allow QUIC to use it. No functional change expected, no flag protected.
PiperOrigin-RevId: 261692309
Change-Id: I2960c067af53ed2de07a69f9f927018193c7c857
diff --git a/spdy/core/lifo_write_scheduler.h b/spdy/core/lifo_write_scheduler.h
new file mode 100644
index 0000000..ed734f3
--- /dev/null
+++ b/spdy/core/lifo_write_scheduler.h
@@ -0,0 +1,207 @@
+// Copyright (c) 2019 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_SPDY_CORE_LIFO_WRITE_SCHEDULER_H_
+#define QUICHE_SPDY_CORE_LIFO_WRITE_SCHEDULER_H_
+
+#include <map>
+#include <set>
+
+#include "net/third_party/quiche/src/spdy/core/write_scheduler.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_containers.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_utils.h"
+
+namespace spdy {
+
+namespace test {
+
+template <typename StreamIdType>
+class LifoWriteSchedulerPeer;
+
+} // namespace test
+
+// Create a write scheduler where the stream added last will have the highest
+// priority.
+template <typename StreamIdType>
+class LifoWriteScheduler : public WriteScheduler<StreamIdType> {
+ public:
+ using typename WriteScheduler<StreamIdType>::StreamPrecedenceType;
+
+ LifoWriteScheduler() = default;
+
+ void RegisterStream(StreamIdType stream_id,
+ const StreamPrecedenceType& /*precedence*/) override;
+
+ void UnregisterStream(StreamIdType stream_id) override;
+
+ bool StreamRegistered(StreamIdType stream_id) const override {
+ return registered_streams_.find(stream_id) != registered_streams_.end();
+ }
+
+ // Stream precedence is not supported by this scheduler.
+ StreamPrecedenceType GetStreamPrecedence(
+ StreamIdType /*stream_id*/) const override {
+ return StreamPrecedenceType(kV3LowestPriority);
+ }
+
+ void UpdateStreamPrecedence(
+ StreamIdType /*stream_id*/,
+ const StreamPrecedenceType& /*precedence*/) override {}
+
+ std::vector<StreamIdType> GetStreamChildren(
+ StreamIdType /*stream_id*/) const override {
+ return std::vector<StreamIdType>();
+ }
+
+ void RecordStreamEventTime(StreamIdType stream_id,
+ int64_t now_in_usec) override;
+
+ int64_t GetLatestEventWithPrecedence(StreamIdType stream_id) const override;
+
+ StreamIdType PopNextReadyStream() override;
+
+ std::tuple<StreamIdType, StreamPrecedenceType>
+ PopNextReadyStreamAndPrecedence() override {
+ return std::make_tuple(PopNextReadyStream(),
+ StreamPrecedenceType(kV3LowestPriority));
+ }
+
+ bool ShouldYield(StreamIdType stream_id) const override {
+ return !ready_streams_.empty() && stream_id < *ready_streams_.rbegin();
+ }
+
+ void MarkStreamReady(StreamIdType stream_id, bool /*add_to_front*/) override;
+
+ void MarkStreamNotReady(StreamIdType stream_id) override;
+
+ bool HasReadyStreams() const override { return !ready_streams_.empty(); }
+ size_t NumReadyStreams() const override { return ready_streams_.size(); }
+ bool IsStreamReady(StreamIdType stream_id) const override;
+ size_t NumRegisteredStreams() const override;
+ string DebugString() const override;
+
+ private:
+ friend class test::LifoWriteSchedulerPeer<StreamIdType>;
+
+ std::set<StreamIdType> ready_streams_;
+ std::map<StreamIdType, int64_t> registered_streams_;
+};
+
+template <typename StreamIdType>
+void LifoWriteScheduler<StreamIdType>::RegisterStream(
+ StreamIdType stream_id,
+ const StreamPrecedenceType& /*precedence*/) {
+ if (StreamRegistered(stream_id)) {
+ SPDY_BUG << "Stream " << stream_id << " already registered";
+ return;
+ }
+ registered_streams_.emplace_hint(registered_streams_.end(), stream_id, 0);
+}
+
+template <typename StreamIdType>
+void LifoWriteScheduler<StreamIdType>::UnregisterStream(
+ StreamIdType stream_id) {
+ if (!StreamRegistered(stream_id)) {
+ SPDY_BUG << "Stream " << stream_id << " is not registered";
+ return;
+ }
+ registered_streams_.erase(stream_id);
+ ready_streams_.erase(stream_id);
+}
+
+template <typename StreamIdType>
+void LifoWriteScheduler<StreamIdType>::RecordStreamEventTime(
+ StreamIdType stream_id,
+ int64_t now_in_usec) {
+ auto it = registered_streams_.find(stream_id);
+ if (it != registered_streams_.end()) {
+ it->second = now_in_usec;
+ } else {
+ SPDY_BUG << "Stream " << stream_id << " is not registered";
+ }
+}
+
+template <typename StreamIdType>
+int64_t LifoWriteScheduler<StreamIdType>::GetLatestEventWithPrecedence(
+ StreamIdType stream_id) const {
+ if (!StreamRegistered(stream_id)) {
+ SPDY_BUG << "Stream " << stream_id << " is not registered";
+ return 0;
+ }
+ int64_t latest_event_time_us = 0;
+ for (auto it = registered_streams_.rbegin(); it != registered_streams_.rend();
+ ++it) {
+ if (stream_id < it->first) {
+ if (it->second > latest_event_time_us) {
+ latest_event_time_us = it->second;
+ }
+ } else {
+ break;
+ }
+ }
+ return latest_event_time_us;
+}
+
+template <typename StreamIdType>
+StreamIdType LifoWriteScheduler<StreamIdType>::PopNextReadyStream() {
+ if (ready_streams_.empty()) {
+ SPDY_BUG << "No ready streams available";
+ return 0;
+ }
+ auto it = --ready_streams_.end();
+ StreamIdType id = *it;
+ ready_streams_.erase(it);
+ return id;
+}
+
+template <typename StreamIdType>
+void LifoWriteScheduler<StreamIdType>::MarkStreamReady(StreamIdType stream_id,
+ bool /*add_to_front*/) {
+ if (!StreamRegistered(stream_id)) {
+ SPDY_BUG << "Stream " << stream_id << " is not registered";
+ return;
+ }
+ if (ready_streams_.find(stream_id) != ready_streams_.end()) {
+ SPDY_VLOG(1) << "Stream already exists in the list";
+ return;
+ }
+ ready_streams_.insert(stream_id);
+}
+
+template <typename StreamIdType>
+void LifoWriteScheduler<StreamIdType>::MarkStreamNotReady(
+ StreamIdType stream_id) {
+ auto it = ready_streams_.find(stream_id);
+ if (it == ready_streams_.end()) {
+ SPDY_VLOG(1) << "Try to remove a stream that is not on list";
+ return;
+ }
+ ready_streams_.erase(it);
+}
+
+template <typename StreamIdType>
+bool LifoWriteScheduler<StreamIdType>::IsStreamReady(
+ StreamIdType stream_id) const {
+ if (!StreamRegistered(stream_id)) {
+ SPDY_BUG << "Stream " << stream_id << " is not registered";
+ return false;
+ }
+ return ready_streams_.find(stream_id) != ready_streams_.end();
+}
+
+template <typename StreamIdType>
+size_t LifoWriteScheduler<StreamIdType>::NumRegisteredStreams() const {
+ return registered_streams_.size();
+}
+
+template <typename StreamIdType>
+SpdyString LifoWriteScheduler<StreamIdType>::DebugString() const {
+ return SpdyStrCat(
+ "LifoWriteScheduler {num_streams=", registered_streams_.size(),
+ " num_ready_streams=", NumReadyStreams(), "}");
+}
+
+} // namespace spdy
+
+#endif // QUICHE_SPDY_CORE_LIFO_WRITE_SCHEDULER_H_
diff --git a/spdy/core/lifo_write_scheduler_test.cc b/spdy/core/lifo_write_scheduler_test.cc
new file mode 100644
index 0000000..c9acc11
--- /dev/null
+++ b/spdy/core/lifo_write_scheduler_test.cc
@@ -0,0 +1,156 @@
+// Copyright (c) 2019 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 "net/third_party/quiche/src/spdy/core/lifo_write_scheduler.h"
+
+#include "net/third_party/quiche/src/spdy/core/spdy_protocol.h"
+#include "net/third_party/quiche/src/spdy/core/spdy_test_utils.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_test.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_test_helpers.h"
+
+namespace spdy {
+
+namespace test {
+
+template <typename StreamIdType>
+class LifoWriteSchedulerPeer {
+ public:
+ explicit LifoWriteSchedulerPeer(LifoWriteScheduler<StreamIdType>* scheduler)
+ : scheduler_(scheduler) {}
+
+ size_t NumRegisteredListStreams() const {
+ return scheduler_->registered_streams_.size();
+ }
+
+ std::set<StreamIdType>* GetReadyList() const {
+ return &scheduler_->ready_streams_;
+ }
+
+ private:
+ LifoWriteScheduler<StreamIdType>* scheduler_;
+};
+
+// Test add and remove from ready list.
+TEST(LifoWriteSchedulerTest, ReadyListTest) {
+ LifoWriteScheduler<SpdyStreamId> lifo;
+ LifoWriteSchedulerPeer<SpdyStreamId> peer(&lifo);
+
+ EXPECT_SPDY_BUG(
+ EXPECT_EQ(0u, std::get<0>(lifo.PopNextReadyStreamAndPrecedence())),
+ "No ready streams available");
+ EXPECT_SPDY_BUG(EXPECT_EQ(0u, lifo.PopNextReadyStream()),
+ "No ready streams available");
+ EXPECT_FALSE(lifo.HasReadyStreams());
+ EXPECT_SPDY_BUG(lifo.MarkStreamReady(9, true), "Stream 9 is not registered");
+ EXPECT_SPDY_BUG(lifo.IsStreamReady(9), "Stream 9 is not registered");
+ SpdyStreamPrecedence precedence(1);
+ lifo.RegisterStream(3, precedence);
+ EXPECT_FALSE(lifo.IsStreamReady(3));
+ lifo.RegisterStream(7, precedence);
+ lifo.RegisterStream(9, precedence);
+ lifo.RegisterStream(11, precedence);
+ lifo.RegisterStream(13, precedence);
+ lifo.RegisterStream(15, precedence);
+ lifo.RegisterStream(17, precedence);
+ lifo.MarkStreamReady(9, true);
+ lifo.MarkStreamReady(15, true);
+ lifo.MarkStreamReady(7, true);
+ lifo.MarkStreamReady(13, true);
+ lifo.MarkStreamReady(11, true);
+ lifo.MarkStreamReady(3, true);
+ EXPECT_TRUE(lifo.IsStreamReady(3));
+ lifo.MarkStreamReady(17, true);
+ EXPECT_TRUE(lifo.HasReadyStreams());
+ EXPECT_EQ(7u, lifo.NumReadyStreams());
+
+ // Verify MarkStream(Not)Ready() can be called multiple times for the same
+ // stream.
+ lifo.MarkStreamReady(11, true);
+ lifo.MarkStreamNotReady(5);
+ lifo.MarkStreamNotReady(21);
+
+ EXPECT_EQ(17u, lifo.PopNextReadyStream());
+ EXPECT_EQ(15u, std::get<0>(lifo.PopNextReadyStreamAndPrecedence()));
+ EXPECT_TRUE(lifo.ShouldYield(9));
+ EXPECT_FALSE(lifo.ShouldYield(13));
+ EXPECT_FALSE(lifo.ShouldYield(15));
+
+ lifo.MarkStreamNotReady(3);
+ EXPECT_TRUE(peer.GetReadyList()->find(3) == peer.GetReadyList()->end());
+ lifo.MarkStreamNotReady(13);
+ EXPECT_TRUE(peer.GetReadyList()->find(13) == peer.GetReadyList()->end());
+ lifo.MarkStreamNotReady(7);
+ EXPECT_TRUE(peer.GetReadyList()->find(7) == peer.GetReadyList()->end());
+ EXPECT_EQ(2u, lifo.NumReadyStreams());
+
+ lifo.MarkStreamNotReady(9);
+ lifo.MarkStreamNotReady(11);
+ EXPECT_FALSE(lifo.ShouldYield(1));
+}
+
+// Test add and remove from registered list.
+TEST(LifoWriteSchedulerTest, RegisterListTest) {
+ LifoWriteScheduler<SpdyStreamId> lifo;
+ LifoWriteSchedulerPeer<SpdyStreamId> peer(&lifo);
+ SpdyStreamPrecedence precedence(1);
+ EXPECT_EQ(0u, lifo.NumRegisteredStreams());
+ lifo.RegisterStream(3, precedence);
+ lifo.RegisterStream(5, precedence);
+ lifo.RegisterStream(7, precedence);
+ lifo.RegisterStream(9, precedence);
+ lifo.RegisterStream(11, precedence);
+ EXPECT_EQ(5u, lifo.NumRegisteredStreams());
+
+ EXPECT_TRUE(lifo.StreamRegistered(3));
+ EXPECT_TRUE(lifo.StreamRegistered(5));
+ EXPECT_TRUE(lifo.StreamRegistered(7));
+ EXPECT_TRUE(lifo.StreamRegistered(9));
+ EXPECT_TRUE(lifo.StreamRegistered(11));
+ EXPECT_SPDY_BUG(lifo.RegisterStream(11, precedence),
+ "Stream 11 already registered");
+ EXPECT_EQ(5u, peer.NumRegisteredListStreams());
+
+ lifo.UnregisterStream(3);
+ EXPECT_EQ(4u, lifo.NumRegisteredStreams());
+ EXPECT_FALSE(lifo.StreamRegistered(3));
+ EXPECT_SPDY_BUG(lifo.UnregisterStream(3), "Stream 3 is not registered");
+ EXPECT_SPDY_BUG(lifo.UnregisterStream(13), "Stream 13 is not registered");
+ lifo.UnregisterStream(11);
+ EXPECT_FALSE(lifo.StreamRegistered(11));
+ lifo.UnregisterStream(7);
+ EXPECT_EQ(2u, lifo.NumRegisteredStreams());
+ EXPECT_FALSE(lifo.StreamRegistered(7));
+ EXPECT_TRUE(lifo.StreamRegistered(5));
+ EXPECT_TRUE(lifo.StreamRegistered(9));
+}
+
+// Test mark latest event time.
+TEST(LifoWriteSchedulerTest, GetLatestEventTest) {
+ LifoWriteScheduler<SpdyStreamId> lifo;
+ LifoWriteSchedulerPeer<SpdyStreamId> peer(&lifo);
+ SpdyStreamPrecedence precedence(1);
+ lifo.RegisterStream(1, precedence);
+ lifo.RegisterStream(3, precedence);
+ lifo.RegisterStream(5, precedence);
+ lifo.RegisterStream(7, precedence);
+ lifo.RegisterStream(9, precedence);
+ lifo.RecordStreamEventTime(1, 1);
+ lifo.RecordStreamEventTime(3, 8);
+ lifo.RecordStreamEventTime(5, 4);
+ lifo.RecordStreamEventTime(7, 2);
+ lifo.RecordStreamEventTime(9, 3);
+ EXPECT_SPDY_BUG(lifo.RecordStreamEventTime(11, 1),
+ "Stream 11 is not registered");
+ EXPECT_EQ(0, lifo.GetLatestEventWithPrecedence(9));
+ EXPECT_EQ(3, lifo.GetLatestEventWithPrecedence(7));
+ EXPECT_EQ(3, lifo.GetLatestEventWithPrecedence(5));
+ EXPECT_EQ(4, lifo.GetLatestEventWithPrecedence(3));
+ EXPECT_EQ(8, lifo.GetLatestEventWithPrecedence(1));
+ EXPECT_SPDY_BUG(lifo.GetLatestEventWithPrecedence(11),
+ "Stream 11 is not registered");
+}
+
+} // namespace test
+
+} // namespace spdy
