blob: cbe53d20ae2cfe1bb0287c9c120206b57edfb2f6 [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_LIFO_WRITE_SCHEDULER_H_
#define QUICHE_SPDY_CORE_LIFO_WRITE_SCHEDULER_H_
#include <cstdint>
#include <map>
#include <set>
#include <string>
#include "absl/strings/str_cat.h"
#include "spdy/core/write_scheduler.h"
#include "spdy/platform/api/spdy_containers.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 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 {
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;
std::string DebugString() const override;
private:
friend class test::LifoWriteSchedulerPeer<StreamIdType>;
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 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,
StreamInfo{/*priority=*/precedence.spdy3_priority(), /*event_time=*/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>
typename LifoWriteScheduler<StreamIdType>::StreamPrecedenceType
LifoWriteScheduler<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 LifoWriteScheduler<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>
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.event_time = 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.event_time > latest_event_time_us) {
latest_event_time_us = it->second.event_time;
}
} 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>
std::string LifoWriteScheduler<StreamIdType>::DebugString() const {
return absl::StrCat(
"LifoWriteScheduler {num_streams=", registered_streams_.size(),
" num_ready_streams=", NumReadyStreams(), "}");
}
} // namespace spdy
#endif // QUICHE_SPDY_CORE_LIFO_WRITE_SCHEDULER_H_