gfe-relnote: Add a FifoWriteScheduler where the stream with the smallest stream ID will have the highest priority. Not used in prod, not protected.

PiperOrigin-RevId: 260922889
Change-Id: Id7af765ee6e69821b560b0f4c028ac9e8f2840db

spdy/core/fifo_write_scheduler.h

diff --git a/spdy/core/fifo_write_scheduler.h b/spdy/core/fifo_write_scheduler.h
new file mode 100644
index 0000000..e972a2b
--- /dev/null
+++ b/spdy/core/fifo_write_scheduler.h
@@ -0,0 +1,219 @@
+// 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_FIFO_WRITE_SCHEDULER_H_
+#define QUICHE_SPDY_CORE_FIFO_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_string_utils.h"
+
+namespace spdy {
+
+// A write scheduler where the stream with the smallest stream ID will have the
+// highest priority.
+template <typename StreamIdType>
+class FifoWriteScheduler : public WriteScheduler<StreamIdType> {
+ public:
+  using typename WriteScheduler<StreamIdType>::StreamPrecedenceType;
+
+  FifoWriteScheduler() = default;
+
+  // WriteScheduler methods
+  void RegisterStream(StreamIdType stream_id,
+                      const StreamPrecedenceType& precedence) override;
+  void UnregisterStream(StreamIdType stream_id) override;
+  bool StreamRegistered(StreamIdType stream_id) const override;
+  StreamPrecedenceType GetStreamPrecedence(
+      StreamIdType stream_id) const override;
+  void UpdateStreamPrecedence(StreamIdType stream_id,
+                              const StreamPrecedenceType& precedence) override;
+  std::vector<StreamIdType> GetStreamChildren(
+      StreamIdType stream_id) const override;
+  void RecordStreamEventTime(StreamIdType stream_id,
+                             int64_t now_in_usec) override;
+  int64_t GetLatestEventWithPrecedence(StreamIdType stream_id) const override;
+  bool ShouldYield(StreamIdType stream_id) const override;
+  void MarkStreamReady(StreamIdType stream_id, bool add_to_front) override;
+  void MarkStreamNotReady(StreamIdType stream_id) override;
+  bool HasReadyStreams() const override;
+  StreamIdType PopNextReadyStream() override;
+  std::tuple<StreamIdType, StreamPrecedenceType>
+  PopNextReadyStreamAndPrecedence() override;
+  size_t NumReadyStreams() const override;
+  bool IsStreamReady(StreamIdType stream_id) const override;
+  size_t NumRegisteredStreams() const override;
+  SpdyString DebugString() const override;
+
+ private:
+  std::set<StreamIdType> ready_streams_;
+  // This map maps stream ID to read/write event time (us since Unix epoch).
+  std::map<StreamIdType, int64_t> registered_streams_;
+};
+
+template <typename StreamIdType>
+void FifoWriteScheduler<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 FifoWriteScheduler<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>
+bool FifoWriteScheduler<StreamIdType>::StreamRegistered(
+    StreamIdType stream_id) const {
+  return registered_streams_.find(stream_id) != registered_streams_.end();
+}
+
+// Stream precedence is not supported by this scheduler.
+template <typename StreamIdType>
+typename FifoWriteScheduler<StreamIdType>::StreamPrecedenceType
+FifoWriteScheduler<StreamIdType>::GetStreamPrecedence(
+    StreamIdType /*stream_id*/) const {
+  return StreamPrecedenceType(kV3LowestPriority);
+}
+
+template <typename StreamIdType>
+void FifoWriteScheduler<StreamIdType>::UpdateStreamPrecedence(
+    StreamIdType /*stream_id*/,
+    const StreamPrecedenceType& /*precedence*/) {}
+
+template <typename StreamIdType>
+std::vector<StreamIdType> FifoWriteScheduler<StreamIdType>::GetStreamChildren(
+    StreamIdType /*stream_id*/) const {
+  return std::vector<StreamIdType>();
+}
+
+template <typename StreamIdType>
+void FifoWriteScheduler<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 FifoWriteScheduler<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_.begin(); it != registered_streams_.end();
+       ++it) {
+    if (stream_id <= it->first) {
+      break;
+    }
+    latest_event_time_us = std::max(latest_event_time_us, it->second);
+  }
+  return latest_event_time_us;
+}
+
+template <typename StreamIdType>
+bool FifoWriteScheduler<StreamIdType>::ShouldYield(
+    StreamIdType stream_id) const {
+  return !ready_streams_.empty() && stream_id > *ready_streams_.begin();
+}
+
+template <typename StreamIdType>
+void FifoWriteScheduler<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_DVLOG(1) << "Stream already exists in the list";
+    return;
+  }
+  ready_streams_.insert(stream_id);
+}
+
+template <typename StreamIdType>
+void FifoWriteScheduler<StreamIdType>::MarkStreamNotReady(
+    StreamIdType stream_id) {
+  auto it = ready_streams_.find(stream_id);
+  if (it == ready_streams_.end()) {
+    SPDY_DVLOG(1) << "Try to remove a stream that is not on list";
+    return;
+  }
+  ready_streams_.erase(it);
+}
+
+template <typename StreamIdType>
+bool FifoWriteScheduler<StreamIdType>::HasReadyStreams() const {
+  return !ready_streams_.empty();
+}
+
+template <typename StreamIdType>
+StreamIdType FifoWriteScheduler<StreamIdType>::PopNextReadyStream() {
+  if (ready_streams_.empty()) {
+    SPDY_BUG << "No ready streams available";
+    return 0;
+  }
+  auto it = ready_streams_.begin();
+  StreamIdType id = *it;
+  ready_streams_.erase(it);
+  return id;
+}
+
+template <typename StreamIdType>
+std::tuple<StreamIdType,
+           typename FifoWriteScheduler<StreamIdType>::StreamPrecedenceType>
+FifoWriteScheduler<StreamIdType>::PopNextReadyStreamAndPrecedence() {
+  return std::make_tuple(PopNextReadyStream(),
+                         StreamPrecedenceType(kV3LowestPriority));
+}
+
+template <typename StreamIdType>
+size_t FifoWriteScheduler<StreamIdType>::NumReadyStreams() const {
+  return ready_streams_.size();
+}
+
+template <typename StreamIdType>
+bool FifoWriteScheduler<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 FifoWriteScheduler<StreamIdType>::NumRegisteredStreams() const {
+  return registered_streams_.size();
+}
+
+template <typename StreamIdType>
+string FifoWriteScheduler<StreamIdType>::DebugString() const {
+  return SpdyStrCat(
+      "FifoWriteScheduler {num_streams=", registered_streams_.size(),
+      " num_ready_streams=", NumReadyStreams(), "}");
+}
+
+}  // namespace spdy
+
+#endif  // QUICHE_SPDY_CORE_FIFO_WRITE_SCHEDULER_H_

spdy/core/fifo_write_scheduler_test.cc

diff --git a/spdy/core/fifo_write_scheduler_test.cc b/spdy/core/fifo_write_scheduler_test.cc
new file mode 100644
index 0000000..1a6e231
--- /dev/null
+++ b/spdy/core/fifo_write_scheduler_test.cc
@@ -0,0 +1,85 @@
+// 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/fifo_write_scheduler.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 {
+
+TEST(FifoWriteSchedulerTest, BasicTest) {
+  FifoWriteScheduler<SpdyStreamId> fifo;
+  EXPECT_FALSE(fifo.HasReadyStreams());
+  EXPECT_SPDY_BUG(
+      EXPECT_EQ(0, std::get<0>(fifo.PopNextReadyStreamAndPrecedence())),
+      "No ready streams available");
+  EXPECT_SPDY_BUG(fifo.MarkStreamReady(9, true), "Stream 9 is not registered");
+  EXPECT_SPDY_BUG(fifo.IsStreamReady(9), "Stream 9 is not registered");
+
+  SpdyStreamPrecedence precedence(1);
+  fifo.RegisterStream(3, precedence);
+  EXPECT_FALSE(fifo.IsStreamReady(3));
+  fifo.RegisterStream(9, precedence);
+  fifo.RegisterStream(7, precedence);
+  fifo.RegisterStream(11, precedence);
+  fifo.RegisterStream(13, precedence);
+  fifo.RegisterStream(15, precedence);
+  fifo.RegisterStream(17, precedence);
+  EXPECT_EQ(7u, fifo.NumRegisteredStreams());
+  EXPECT_FALSE(fifo.HasReadyStreams());
+
+  fifo.MarkStreamReady(9, true);
+  EXPECT_TRUE(fifo.IsStreamReady(9));
+  EXPECT_TRUE(fifo.HasReadyStreams());
+  fifo.MarkStreamReady(15, true);
+  fifo.MarkStreamReady(7, true);
+  fifo.MarkStreamReady(13, true);
+  fifo.MarkStreamReady(11, true);
+  fifo.MarkStreamReady(3, true);
+  fifo.MarkStreamReady(17, true);
+  EXPECT_EQ(7u, fifo.NumReadyStreams());
+
+  EXPECT_EQ(3, fifo.PopNextReadyStream());
+  EXPECT_EQ(7, std::get<0>(fifo.PopNextReadyStreamAndPrecedence()));
+  EXPECT_EQ(5u, fifo.NumReadyStreams());
+
+  EXPECT_FALSE(fifo.ShouldYield(3));
+  EXPECT_FALSE(fifo.ShouldYield(9));
+  EXPECT_TRUE(fifo.ShouldYield(13));
+  EXPECT_TRUE(fifo.ShouldYield(10));
+
+  fifo.MarkStreamNotReady(9);
+  EXPECT_EQ(4u, fifo.NumReadyStreams());
+  EXPECT_FALSE(fifo.ShouldYield(10));
+  EXPECT_TRUE(fifo.ShouldYield(12));
+}
+
+TEST(FifoWriteSchedulerTest, GetLatestEventTest) {
+  FifoWriteScheduler<SpdyStreamId> fifo;
+
+  SpdyStreamPrecedence precedence(1);
+  fifo.RegisterStream(1, precedence);
+  fifo.RegisterStream(3, precedence);
+  fifo.RegisterStream(5, precedence);
+  fifo.RegisterStream(7, precedence);
+  fifo.RegisterStream(9, precedence);
+  fifo.RecordStreamEventTime(1, 3);
+  fifo.RecordStreamEventTime(3, 2);
+  fifo.RecordStreamEventTime(5, 4);
+  fifo.RecordStreamEventTime(7, 8);
+  fifo.RecordStreamEventTime(9, 1);
+
+  EXPECT_EQ(8, fifo.GetLatestEventWithPrecedence(9));
+  EXPECT_EQ(4, fifo.GetLatestEventWithPrecedence(7));
+  EXPECT_EQ(3, fifo.GetLatestEventWithPrecedence(5));
+  EXPECT_EQ(3, fifo.GetLatestEventWithPrecedence(3));
+  EXPECT_EQ(0, fifo.GetLatestEventWithPrecedence(1));
+}
+
+}  // namespace test
+
+}  // namespace spdy