blob: 7bf8c4ed475dbe52eabf5a23ca6933585f0db6a8 [file] [log] [blame]
// 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 <string>
#include "absl/strings/str_cat.h"
#include "spdy/core/write_scheduler.h"
#include "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;
// Stream precedence is available but note that it is not used for scheduling
// in this scheduler.
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;
std::string DebugString() const override;
private:
struct StreamInfo {
SpdyPriority priority;
int64_t event_time; // read/write event time (us since Unix epoch).
};
std::set<StreamIdType> ready_streams_;
std::map<StreamIdType, StreamInfo> 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,
StreamInfo{/*priority=*/precedence.spdy3_priority(), /*event_time=*/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 {
auto it = registered_streams_.find(stream_id);
if (it == registered_streams_.end()) {
SPDY_DVLOG(1) << "Stream " << stream_id << " not registered";
return StreamPrecedenceType(kV3LowestPriority);
}
return StreamPrecedenceType(it->second.priority);
}
template <typename StreamIdType>
void FifoWriteScheduler<StreamIdType>::UpdateStreamPrecedence(
StreamIdType stream_id,
const StreamPrecedenceType& precedence) {
auto it = registered_streams_.find(stream_id);
if (it == registered_streams_.end()) {
SPDY_DVLOG(1) << "Stream " << stream_id << " not registered";
return;
}
it->second.priority = precedence.spdy3_priority();
}
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.event_time = 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.event_time);
}
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>
std::string FifoWriteScheduler<StreamIdType>::DebugString() const {
return absl::StrCat(
"FifoWriteScheduler {num_streams=", registered_streams_.size(),
" num_ready_streams=", NumReadyStreams(), "}");
}
} // namespace spdy
#endif // QUICHE_SPDY_CORE_FIFO_WRITE_SCHEDULER_H_