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

spdy/core/lifo_write_scheduler.h

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_

spdy/core/lifo_write_scheduler_test.cc

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