1 // Copyright (c) 2017 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 "quiche/quic/core/quic_control_frame_manager.h"
6
7 #include <string>
8
9 #include "absl/strings/str_cat.h"
10 #include "quiche/quic/core/frames/quic_ack_frequency_frame.h"
11 #include "quiche/quic/core/frames/quic_frame.h"
12 #include "quiche/quic/core/frames/quic_new_connection_id_frame.h"
13 #include "quiche/quic/core/frames/quic_retire_connection_id_frame.h"
14 #include "quiche/quic/core/quic_constants.h"
15 #include "quiche/quic/core/quic_session.h"
16 #include "quiche/quic/core/quic_types.h"
17 #include "quiche/quic/core/quic_utils.h"
18 #include "quiche/quic/platform/api/quic_bug_tracker.h"
19 #include "quiche/quic/platform/api/quic_flag_utils.h"
20 #include "quiche/quic/platform/api/quic_flags.h"
21
22 namespace quic {
23
24 namespace {
25
26 // The maximum number of buffered control frames which are waiting to be ACKed
27 // or sent for the first time.
28 const size_t kMaxNumControlFrames = 1000;
29
30 } // namespace
31
QuicControlFrameManager(QuicSession * session)32 QuicControlFrameManager::QuicControlFrameManager(QuicSession* session)
33 : last_control_frame_id_(kInvalidControlFrameId),
34 least_unacked_(1),
35 least_unsent_(1),
36 delegate_(session),
37 num_buffered_max_stream_frames_(0) {}
38
~QuicControlFrameManager()39 QuicControlFrameManager::~QuicControlFrameManager() {
40 while (!control_frames_.empty()) {
41 DeleteFrame(&control_frames_.front());
42 control_frames_.pop_front();
43 }
44 }
45
WriteOrBufferQuicFrame(QuicFrame frame)46 void QuicControlFrameManager::WriteOrBufferQuicFrame(QuicFrame frame) {
47 const bool had_buffered_frames = HasBufferedFrames();
48 control_frames_.emplace_back(frame);
49 if (control_frames_.size() > kMaxNumControlFrames) {
50 delegate_->OnControlFrameManagerError(
51 QUIC_TOO_MANY_BUFFERED_CONTROL_FRAMES,
52 absl::StrCat("More than ", kMaxNumControlFrames,
53 "buffered control frames, least_unacked: ", least_unacked_,
54 ", least_unsent_: ", least_unsent_));
55 return;
56 }
57 if (had_buffered_frames) {
58 return;
59 }
60 WriteBufferedFrames();
61 }
62
WriteOrBufferRstStream(QuicStreamId id,QuicResetStreamError error,QuicStreamOffset bytes_written)63 void QuicControlFrameManager::WriteOrBufferRstStream(
64 QuicStreamId id, QuicResetStreamError error,
65 QuicStreamOffset bytes_written) {
66 QUIC_DVLOG(1) << "Writing RST_STREAM_FRAME";
67 WriteOrBufferQuicFrame((QuicFrame(new QuicRstStreamFrame(
68 ++last_control_frame_id_, id, error, bytes_written))));
69 }
70
WriteOrBufferGoAway(QuicErrorCode error,QuicStreamId last_good_stream_id,const std::string & reason)71 void QuicControlFrameManager::WriteOrBufferGoAway(
72 QuicErrorCode error, QuicStreamId last_good_stream_id,
73 const std::string& reason) {
74 QUIC_DVLOG(1) << "Writing GOAWAY_FRAME";
75 WriteOrBufferQuicFrame(QuicFrame(new QuicGoAwayFrame(
76 ++last_control_frame_id_, error, last_good_stream_id, reason)));
77 }
78
WriteOrBufferWindowUpdate(QuicStreamId id,QuicStreamOffset byte_offset)79 void QuicControlFrameManager::WriteOrBufferWindowUpdate(
80 QuicStreamId id, QuicStreamOffset byte_offset) {
81 QUIC_DVLOG(1) << "Writing WINDOW_UPDATE_FRAME";
82 WriteOrBufferQuicFrame(QuicFrame(
83 QuicWindowUpdateFrame(++last_control_frame_id_, id, byte_offset)));
84 }
85
WriteOrBufferBlocked(QuicStreamId id,QuicStreamOffset byte_offset)86 void QuicControlFrameManager::WriteOrBufferBlocked(
87 QuicStreamId id, QuicStreamOffset byte_offset) {
88 QUIC_DVLOG(1) << "Writing BLOCKED_FRAME";
89 WriteOrBufferQuicFrame(
90 QuicFrame(QuicBlockedFrame(++last_control_frame_id_, id, byte_offset)));
91 }
92
WriteOrBufferStreamsBlocked(QuicStreamCount count,bool unidirectional)93 void QuicControlFrameManager::WriteOrBufferStreamsBlocked(QuicStreamCount count,
94 bool unidirectional) {
95 QUIC_DVLOG(1) << "Writing STREAMS_BLOCKED Frame";
96 QUIC_CODE_COUNT(quic_streams_blocked_transmits);
97 WriteOrBufferQuicFrame(QuicFrame(QuicStreamsBlockedFrame(
98 ++last_control_frame_id_, count, unidirectional)));
99 }
100
WriteOrBufferMaxStreams(QuicStreamCount count,bool unidirectional)101 void QuicControlFrameManager::WriteOrBufferMaxStreams(QuicStreamCount count,
102 bool unidirectional) {
103 QUIC_DVLOG(1) << "Writing MAX_STREAMS Frame";
104 QUIC_CODE_COUNT(quic_max_streams_transmits);
105 WriteOrBufferQuicFrame(QuicFrame(
106 QuicMaxStreamsFrame(++last_control_frame_id_, count, unidirectional)));
107 ++num_buffered_max_stream_frames_;
108 }
109
WriteOrBufferStopSending(QuicResetStreamError error,QuicStreamId stream_id)110 void QuicControlFrameManager::WriteOrBufferStopSending(
111 QuicResetStreamError error, QuicStreamId stream_id) {
112 QUIC_DVLOG(1) << "Writing STOP_SENDING_FRAME";
113 WriteOrBufferQuicFrame(QuicFrame(
114 QuicStopSendingFrame(++last_control_frame_id_, stream_id, error)));
115 }
116
WriteOrBufferHandshakeDone()117 void QuicControlFrameManager::WriteOrBufferHandshakeDone() {
118 QUIC_DVLOG(1) << "Writing HANDSHAKE_DONE";
119 WriteOrBufferQuicFrame(
120 QuicFrame(QuicHandshakeDoneFrame(++last_control_frame_id_)));
121 }
122
WriteOrBufferAckFrequency(const QuicAckFrequencyFrame & ack_frequency_frame)123 void QuicControlFrameManager::WriteOrBufferAckFrequency(
124 const QuicAckFrequencyFrame& ack_frequency_frame) {
125 QUIC_DVLOG(1) << "Writing ACK_FREQUENCY frame";
126 QuicControlFrameId control_frame_id = ++last_control_frame_id_;
127 // Using the control_frame_id for sequence_number here leaves gaps in
128 // sequence_number.
129 WriteOrBufferQuicFrame(
130 QuicFrame(new QuicAckFrequencyFrame(control_frame_id,
131 /*sequence_number=*/control_frame_id,
132 ack_frequency_frame.packet_tolerance,
133 ack_frequency_frame.max_ack_delay)));
134 }
135
WriteOrBufferNewConnectionId(const QuicConnectionId & connection_id,uint64_t sequence_number,uint64_t retire_prior_to,const StatelessResetToken & stateless_reset_token)136 void QuicControlFrameManager::WriteOrBufferNewConnectionId(
137 const QuicConnectionId& connection_id, uint64_t sequence_number,
138 uint64_t retire_prior_to,
139 const StatelessResetToken& stateless_reset_token) {
140 QUIC_DVLOG(1) << "Writing NEW_CONNECTION_ID frame";
141 WriteOrBufferQuicFrame(QuicFrame(new QuicNewConnectionIdFrame(
142 ++last_control_frame_id_, connection_id, sequence_number,
143 stateless_reset_token, retire_prior_to)));
144 }
145
WriteOrBufferRetireConnectionId(uint64_t sequence_number)146 void QuicControlFrameManager::WriteOrBufferRetireConnectionId(
147 uint64_t sequence_number) {
148 QUIC_DVLOG(1) << "Writing RETIRE_CONNECTION_ID frame";
149 WriteOrBufferQuicFrame(QuicFrame(new QuicRetireConnectionIdFrame(
150 ++last_control_frame_id_, sequence_number)));
151 }
152
WriteOrBufferNewToken(absl::string_view token)153 void QuicControlFrameManager::WriteOrBufferNewToken(absl::string_view token) {
154 QUIC_DVLOG(1) << "Writing NEW_TOKEN frame";
155 WriteOrBufferQuicFrame(
156 QuicFrame(new QuicNewTokenFrame(++last_control_frame_id_, token)));
157 }
158
OnControlFrameSent(const QuicFrame & frame)159 void QuicControlFrameManager::OnControlFrameSent(const QuicFrame& frame) {
160 QuicControlFrameId id = GetControlFrameId(frame);
161 if (id == kInvalidControlFrameId) {
162 QUIC_BUG(quic_bug_12727_1)
163 << "Send or retransmit a control frame with invalid control frame id";
164 return;
165 }
166 if (frame.type == WINDOW_UPDATE_FRAME) {
167 QuicStreamId stream_id = frame.window_update_frame.stream_id;
168 if (window_update_frames_.contains(stream_id) &&
169 id > window_update_frames_[stream_id]) {
170 // Consider the older window update of the same stream as acked.
171 OnControlFrameIdAcked(window_update_frames_[stream_id]);
172 }
173 window_update_frames_[stream_id] = id;
174 }
175 if (pending_retransmissions_.contains(id)) {
176 // This is retransmitted control frame.
177 pending_retransmissions_.erase(id);
178 return;
179 }
180 if (id > least_unsent_) {
181 QUIC_BUG(quic_bug_10517_1)
182 << "Try to send control frames out of order, id: " << id
183 << " least_unsent: " << least_unsent_;
184 delegate_->OnControlFrameManagerError(
185 QUIC_INTERNAL_ERROR, "Try to send control frames out of order");
186 return;
187 }
188 ++least_unsent_;
189 }
190
OnControlFrameAcked(const QuicFrame & frame)191 bool QuicControlFrameManager::OnControlFrameAcked(const QuicFrame& frame) {
192 QuicControlFrameId id = GetControlFrameId(frame);
193 if (!OnControlFrameIdAcked(id)) {
194 return false;
195 }
196 if (frame.type == WINDOW_UPDATE_FRAME) {
197 QuicStreamId stream_id = frame.window_update_frame.stream_id;
198 if (window_update_frames_.contains(stream_id) &&
199 window_update_frames_[stream_id] == id) {
200 window_update_frames_.erase(stream_id);
201 }
202 }
203 if (frame.type == MAX_STREAMS_FRAME) {
204 if (num_buffered_max_stream_frames_ == 0) {
205 QUIC_BUG(invalid_num_buffered_max_stream_frames);
206 } else {
207 --num_buffered_max_stream_frames_;
208 }
209 }
210 return true;
211 }
212
OnControlFrameLost(const QuicFrame & frame)213 void QuicControlFrameManager::OnControlFrameLost(const QuicFrame& frame) {
214 QuicControlFrameId id = GetControlFrameId(frame);
215 if (id == kInvalidControlFrameId) {
216 // Frame does not have a valid control frame ID, ignore it.
217 return;
218 }
219 if (id >= least_unsent_) {
220 QUIC_BUG(quic_bug_10517_2) << "Try to mark unsent control frame as lost";
221 delegate_->OnControlFrameManagerError(
222 QUIC_INTERNAL_ERROR, "Try to mark unsent control frame as lost");
223 return;
224 }
225 if (id < least_unacked_ ||
226 GetControlFrameId(control_frames_.at(id - least_unacked_)) ==
227 kInvalidControlFrameId) {
228 // This frame has already been acked.
229 return;
230 }
231 if (!pending_retransmissions_.contains(id)) {
232 pending_retransmissions_[id] = true;
233 QUIC_BUG_IF(quic_bug_12727_2,
234 pending_retransmissions_.size() > control_frames_.size())
235 << "least_unacked_: " << least_unacked_
236 << ", least_unsent_: " << least_unsent_;
237 }
238 }
239
IsControlFrameOutstanding(const QuicFrame & frame) const240 bool QuicControlFrameManager::IsControlFrameOutstanding(
241 const QuicFrame& frame) const {
242 QuicControlFrameId id = GetControlFrameId(frame);
243 if (id == kInvalidControlFrameId) {
244 // Frame without a control frame ID should not be retransmitted.
245 return false;
246 }
247 // Consider this frame is outstanding if it does not get acked.
248 return id < least_unacked_ + control_frames_.size() && id >= least_unacked_ &&
249 GetControlFrameId(control_frames_.at(id - least_unacked_)) !=
250 kInvalidControlFrameId;
251 }
252
HasPendingRetransmission() const253 bool QuicControlFrameManager::HasPendingRetransmission() const {
254 return !pending_retransmissions_.empty();
255 }
256
WillingToWrite() const257 bool QuicControlFrameManager::WillingToWrite() const {
258 return HasPendingRetransmission() || HasBufferedFrames();
259 }
260
NumBufferedMaxStreams() const261 size_t QuicControlFrameManager::NumBufferedMaxStreams() const {
262 return num_buffered_max_stream_frames_;
263 }
264
NextPendingRetransmission() const265 QuicFrame QuicControlFrameManager::NextPendingRetransmission() const {
266 QUIC_BUG_IF(quic_bug_12727_3, pending_retransmissions_.empty())
267 << "Unexpected call to NextPendingRetransmission() with empty pending "
268 << "retransmission list.";
269 QuicControlFrameId id = pending_retransmissions_.begin()->first;
270 return control_frames_.at(id - least_unacked_);
271 }
272
OnCanWrite()273 void QuicControlFrameManager::OnCanWrite() {
274 if (HasPendingRetransmission()) {
275 // Exit early to allow streams to write pending retransmissions if any.
276 WritePendingRetransmission();
277 return;
278 }
279 WriteBufferedFrames();
280 }
281
RetransmitControlFrame(const QuicFrame & frame,TransmissionType type)282 bool QuicControlFrameManager::RetransmitControlFrame(const QuicFrame& frame,
283 TransmissionType type) {
284 QUICHE_DCHECK(type == PTO_RETRANSMISSION);
285 QuicControlFrameId id = GetControlFrameId(frame);
286 if (id == kInvalidControlFrameId) {
287 // Frame does not have a valid control frame ID, ignore it. Returns true
288 // to allow writing following frames.
289 return true;
290 }
291 if (id >= least_unsent_) {
292 QUIC_BUG(quic_bug_10517_3) << "Try to retransmit unsent control frame";
293 delegate_->OnControlFrameManagerError(
294 QUIC_INTERNAL_ERROR, "Try to retransmit unsent control frame");
295 return false;
296 }
297 if (id < least_unacked_ ||
298 GetControlFrameId(control_frames_.at(id - least_unacked_)) ==
299 kInvalidControlFrameId) {
300 // This frame has already been acked.
301 return true;
302 }
303 QuicFrame copy = CopyRetransmittableControlFrame(frame);
304 QUIC_DVLOG(1) << "control frame manager is forced to retransmit frame: "
305 << frame;
306 if (delegate_->WriteControlFrame(copy, type)) {
307 return true;
308 }
309 DeleteFrame(©);
310 return false;
311 }
312
WriteBufferedFrames()313 void QuicControlFrameManager::WriteBufferedFrames() {
314 while (HasBufferedFrames()) {
315 QuicFrame frame_to_send =
316 control_frames_.at(least_unsent_ - least_unacked_);
317 QuicFrame copy = CopyRetransmittableControlFrame(frame_to_send);
318 if (!delegate_->WriteControlFrame(copy, NOT_RETRANSMISSION)) {
319 // Connection is write blocked.
320 DeleteFrame(©);
321 break;
322 }
323 OnControlFrameSent(frame_to_send);
324 }
325 }
326
WritePendingRetransmission()327 void QuicControlFrameManager::WritePendingRetransmission() {
328 while (HasPendingRetransmission()) {
329 QuicFrame pending = NextPendingRetransmission();
330 QuicFrame copy = CopyRetransmittableControlFrame(pending);
331 if (!delegate_->WriteControlFrame(copy, LOSS_RETRANSMISSION)) {
332 // Connection is write blocked.
333 DeleteFrame(©);
334 break;
335 }
336 OnControlFrameSent(pending);
337 }
338 }
339
OnControlFrameIdAcked(QuicControlFrameId id)340 bool QuicControlFrameManager::OnControlFrameIdAcked(QuicControlFrameId id) {
341 if (id == kInvalidControlFrameId) {
342 // Frame does not have a valid control frame ID, ignore it.
343 return false;
344 }
345 if (id >= least_unsent_) {
346 QUIC_BUG(quic_bug_10517_4) << "Try to ack unsent control frame";
347 delegate_->OnControlFrameManagerError(QUIC_INTERNAL_ERROR,
348 "Try to ack unsent control frame");
349 return false;
350 }
351 if (id < least_unacked_ ||
352 GetControlFrameId(control_frames_.at(id - least_unacked_)) ==
353 kInvalidControlFrameId) {
354 // This frame has already been acked.
355 return false;
356 }
357
358 // Set control frame ID of acked frames to 0.
359 SetControlFrameId(kInvalidControlFrameId,
360 &control_frames_.at(id - least_unacked_));
361 // Remove acked control frames from pending retransmissions.
362 pending_retransmissions_.erase(id);
363 // Clean up control frames queue and increment least_unacked_.
364 while (!control_frames_.empty() &&
365 GetControlFrameId(control_frames_.front()) == kInvalidControlFrameId) {
366 DeleteFrame(&control_frames_.front());
367 control_frames_.pop_front();
368 ++least_unacked_;
369 }
370 return true;
371 }
372
HasBufferedFrames() const373 bool QuicControlFrameManager::HasBufferedFrames() const {
374 return least_unsent_ < least_unacked_ + control_frames_.size();
375 }
376
377 } // namespace quic
378