1 // Copyright 2014 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "net/third_party/quiche/src/quic/core/quic_write_blocked_list.h"
6
7 #include "net/third_party/quiche/src/quic/platform/api/quic_flag_utils.h"
8 #include "net/third_party/quiche/src/quic/platform/api/quic_flags.h"
9
10 namespace quic {
11
QuicWriteBlockedList(QuicTransportVersion version)12 QuicWriteBlockedList::QuicWriteBlockedList(QuicTransportVersion version)
13 : priority_write_scheduler_(
14 std::make_unique<spdy::PriorityWriteScheduler<QuicStreamId>>(
15 QuicVersionUsesCryptoFrames(version)
16 ? std::numeric_limits<QuicStreamId>::max()
17 : 0)),
18 last_priority_popped_(0),
19 scheduler_type_(spdy::WriteSchedulerType::SPDY) {
20 memset(batch_write_stream_id_, 0, sizeof(batch_write_stream_id_));
21 memset(bytes_left_for_batch_write_, 0, sizeof(bytes_left_for_batch_write_));
22 }
23
~QuicWriteBlockedList()24 QuicWriteBlockedList::~QuicWriteBlockedList() {}
25
ShouldYield(QuicStreamId id) const26 bool QuicWriteBlockedList::ShouldYield(QuicStreamId id) const {
27 for (const auto& stream : static_stream_collection_) {
28 if (stream.id == id) {
29 // Static streams should never yield to data streams, or to lower
30 // priority static stream.
31 return false;
32 }
33 if (stream.is_blocked) {
34 return true; // All data streams yield to static streams.
35 }
36 }
37
38 return priority_write_scheduler_->ShouldYield(id);
39 }
40
SwitchWriteScheduler(spdy::WriteSchedulerType type,QuicTransportVersion version)41 bool QuicWriteBlockedList::SwitchWriteScheduler(spdy::WriteSchedulerType type,
42 QuicTransportVersion version) {
43 if (scheduler_type_ == type) {
44 return true;
45 }
46 if (priority_write_scheduler_->NumRegisteredStreams() != 0) {
47 QUIC_BUG << "Cannot switch scheduler with registered streams";
48 return false;
49 }
50 QUIC_DVLOG(1) << "Switching to scheduler type: "
51 << spdy::WriteSchedulerTypeToString(type);
52 switch (type) {
53 case spdy::WriteSchedulerType::LIFO:
54 priority_write_scheduler_ =
55 std::make_unique<spdy::LifoWriteScheduler<QuicStreamId>>();
56 break;
57 case spdy::WriteSchedulerType::SPDY:
58 priority_write_scheduler_ =
59 std::make_unique<spdy::PriorityWriteScheduler<QuicStreamId>>(
60 QuicVersionUsesCryptoFrames(version)
61 ? std::numeric_limits<QuicStreamId>::max()
62 : 0);
63 break;
64 case spdy::WriteSchedulerType::HTTP2:
65 priority_write_scheduler_ =
66 std::make_unique<spdy::Http2PriorityWriteScheduler<QuicStreamId>>();
67 break;
68 case spdy::WriteSchedulerType::FIFO:
69 priority_write_scheduler_ =
70 std::make_unique<spdy::FifoWriteScheduler<QuicStreamId>>();
71 break;
72 default:
73 QUIC_BUG << "Scheduler is not supported for type: "
74 << spdy::WriteSchedulerTypeToString(type);
75 return false;
76 }
77 scheduler_type_ = type;
78 return true;
79 }
80
PopFront()81 QuicStreamId QuicWriteBlockedList::PopFront() {
82 QuicStreamId static_stream_id;
83 if (static_stream_collection_.UnblockFirstBlocked(&static_stream_id)) {
84 return static_stream_id;
85 }
86
87 const auto id_and_precedence =
88 priority_write_scheduler_->PopNextReadyStreamAndPrecedence();
89 const QuicStreamId id = std::get<0>(id_and_precedence);
90 if (scheduler_type_ != spdy::WriteSchedulerType::SPDY) {
91 // No batch writing logic for non-SPDY priority write scheduler.
92 return id;
93 }
94 const spdy::SpdyPriority priority =
95 std::get<1>(id_and_precedence).spdy3_priority();
96
97 if (!priority_write_scheduler_->HasReadyStreams()) {
98 // If no streams are blocked, don't bother latching. This stream will be
99 // the first popped for its priority anyway.
100 batch_write_stream_id_[priority] = 0;
101 last_priority_popped_ = priority;
102 } else if (batch_write_stream_id_[priority] != id) {
103 // If newly latching this batch write stream, let it write 16k.
104 batch_write_stream_id_[priority] = id;
105 bytes_left_for_batch_write_[priority] = 16000;
106 last_priority_popped_ = priority;
107 }
108
109 return id;
110 }
111
RegisterStream(QuicStreamId stream_id,bool is_static_stream,const spdy::SpdyStreamPrecedence & precedence)112 void QuicWriteBlockedList::RegisterStream(
113 QuicStreamId stream_id,
114 bool is_static_stream,
115 const spdy::SpdyStreamPrecedence& precedence) {
116 DCHECK(!priority_write_scheduler_->StreamRegistered(stream_id))
117 << "stream " << stream_id << " already registered";
118 DCHECK(PrecedenceMatchesSchedulerType(precedence));
119 if (is_static_stream) {
120 static_stream_collection_.Register(stream_id);
121 return;
122 }
123
124 priority_write_scheduler_->RegisterStream(stream_id, precedence);
125 }
126
UnregisterStream(QuicStreamId stream_id,bool is_static)127 void QuicWriteBlockedList::UnregisterStream(QuicStreamId stream_id,
128 bool is_static) {
129 if (is_static) {
130 static_stream_collection_.Unregister(stream_id);
131 return;
132 }
133 priority_write_scheduler_->UnregisterStream(stream_id);
134 }
135
UpdateStreamPriority(QuicStreamId stream_id,const spdy::SpdyStreamPrecedence & new_precedence)136 void QuicWriteBlockedList::UpdateStreamPriority(
137 QuicStreamId stream_id,
138 const spdy::SpdyStreamPrecedence& new_precedence) {
139 DCHECK(!static_stream_collection_.IsRegistered(stream_id));
140 DCHECK(PrecedenceMatchesSchedulerType(new_precedence));
141 priority_write_scheduler_->UpdateStreamPrecedence(stream_id, new_precedence);
142 }
143
UpdateBytesForStream(QuicStreamId stream_id,size_t bytes)144 void QuicWriteBlockedList::UpdateBytesForStream(QuicStreamId stream_id,
145 size_t bytes) {
146 if (scheduler_type_ != spdy::WriteSchedulerType::SPDY) {
147 return;
148 }
149 if (batch_write_stream_id_[last_priority_popped_] == stream_id) {
150 // If this was the last data stream popped by PopFront, update the
151 // bytes remaining in its batch write.
152 bytes_left_for_batch_write_[last_priority_popped_] -=
153 std::min(bytes_left_for_batch_write_[last_priority_popped_], bytes);
154 }
155 }
156
AddStream(QuicStreamId stream_id)157 void QuicWriteBlockedList::AddStream(QuicStreamId stream_id) {
158 if (static_stream_collection_.SetBlocked(stream_id)) {
159 return;
160 }
161
162 bool push_front =
163 scheduler_type_ == spdy::WriteSchedulerType::SPDY &&
164 stream_id == batch_write_stream_id_[last_priority_popped_] &&
165 bytes_left_for_batch_write_[last_priority_popped_] > 0;
166 priority_write_scheduler_->MarkStreamReady(stream_id, push_front);
167 }
168
IsStreamBlocked(QuicStreamId stream_id) const169 bool QuicWriteBlockedList::IsStreamBlocked(QuicStreamId stream_id) const {
170 for (const auto& stream : static_stream_collection_) {
171 if (stream.id == stream_id) {
172 return stream.is_blocked;
173 }
174 }
175
176 return priority_write_scheduler_->IsStreamReady(stream_id);
177 }
178
PrecedenceMatchesSchedulerType(const spdy::SpdyStreamPrecedence & precedence)179 bool QuicWriteBlockedList::PrecedenceMatchesSchedulerType(
180 const spdy::SpdyStreamPrecedence& precedence) {
181 switch (scheduler_type_) {
182 case spdy::WriteSchedulerType::LIFO:
183 break;
184 case spdy::WriteSchedulerType::SPDY:
185 return precedence.is_spdy3_priority();
186 case spdy::WriteSchedulerType::HTTP2:
187 return !precedence.is_spdy3_priority();
188 case spdy::WriteSchedulerType::FIFO:
189 break;
190 default:
191 DCHECK(false);
192 return false;
193 }
194 return true;
195 }
196
Register(QuicStreamId id)197 void QuicWriteBlockedList::StaticStreamCollection::Register(QuicStreamId id) {
198 DCHECK(!IsRegistered(id));
199 streams_.push_back({id, false});
200 }
201
IsRegistered(QuicStreamId id) const202 bool QuicWriteBlockedList::StaticStreamCollection::IsRegistered(
203 QuicStreamId id) const {
204 for (const auto& stream : streams_) {
205 if (stream.id == id) {
206 return true;
207 }
208 }
209 return false;
210 }
211
Unregister(QuicStreamId id)212 void QuicWriteBlockedList::StaticStreamCollection::Unregister(QuicStreamId id) {
213 for (auto it = streams_.begin(); it != streams_.end(); ++it) {
214 if (it->id == id) {
215 if (it->is_blocked) {
216 --num_blocked_;
217 }
218 streams_.erase(it);
219 return;
220 }
221 }
222 DCHECK(false) << "Erasing a non-exist stream with id " << id;
223 }
224
SetBlocked(QuicStreamId id)225 bool QuicWriteBlockedList::StaticStreamCollection::SetBlocked(QuicStreamId id) {
226 for (auto& stream : streams_) {
227 if (stream.id == id) {
228 if (!stream.is_blocked) {
229 stream.is_blocked = true;
230 ++num_blocked_;
231 }
232 return true;
233 }
234 }
235 return false;
236 }
237
UnblockFirstBlocked(QuicStreamId * id)238 bool QuicWriteBlockedList::StaticStreamCollection::UnblockFirstBlocked(
239 QuicStreamId* id) {
240 for (auto& stream : streams_) {
241 if (stream.is_blocked) {
242 --num_blocked_;
243 stream.is_blocked = false;
244 *id = stream.id;
245 return true;
246 }
247 }
248 return false;
249 }
250
251 } // namespace quic
252