1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
|
// 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_
|
