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