1 // Copyright (c) 2012 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.
5 #include "net/quic/quic_packet_creator.h"
7 #include "base/basictypes.h"
8 #include "base/logging.h"
9 #include "net/quic/crypto/quic_random.h"
10 #include "net/quic/quic_ack_notifier.h"
11 #include "net/quic/quic_fec_group.h"
12 #include "net/quic/quic_utils.h"
14 using base::StringPiece
;
23 // A QuicRandom wrapper that gets a bucket of entropy and distributes it
24 // bit-by-bit. Replenishes the bucket as needed. Not thread-safe. Expose this
25 // class if single bit randomness is needed elsewhere.
26 class QuicRandomBoolSource
{
28 // random: Source of entropy. Not owned.
29 explicit QuicRandomBoolSource(QuicRandom
* random
)
34 ~QuicRandomBoolSource() {}
36 // Returns the next random bit from the bucket.
39 bit_bucket_
= random_
->RandUint64();
42 bool result
= ((bit_bucket_
& bit_mask_
) != 0);
50 // Stored random bits.
52 // The next available bit has "1" in the mask. Zero means empty bucket.
55 DISALLOW_COPY_AND_ASSIGN(QuicRandomBoolSource
);
58 QuicPacketCreator::QuicPacketCreator(QuicConnectionId connection_id
,
60 QuicRandom
* random_generator
,
62 : connection_id_(connection_id
),
64 random_bool_source_(new QuicRandomBoolSource(random_generator
)),
67 is_server_(is_server
),
68 send_version_in_packet_(!is_server
),
69 sequence_number_length_(options_
.send_sequence_number_length
),
71 framer_
->set_fec_builder(this);
74 QuicPacketCreator::~QuicPacketCreator() {
77 void QuicPacketCreator::OnBuiltFecProtectedPayload(
78 const QuicPacketHeader
& header
, StringPiece payload
) {
79 if (fec_group_
.get()) {
80 DCHECK_NE(0u, header
.fec_group
);
81 fec_group_
->Update(header
, payload
);
85 bool QuicPacketCreator::ShouldSendFec(bool force_close
) const {
86 return fec_group_
.get() != NULL
&& fec_group_
->NumReceivedPackets() > 0 &&
88 fec_group_
->NumReceivedPackets() >= options_
.max_packets_per_fec_group
);
91 void QuicPacketCreator::MaybeStartFEC() {
92 // Don't send FEC until QUIC_VERSION_15.
93 if (framer_
->version() > QUIC_VERSION_14
&&
94 options_
.max_packets_per_fec_group
> 0 && fec_group_
.get() == NULL
) {
95 DCHECK(queued_frames_
.empty());
96 // Set the fec group number to the sequence number of the next packet.
97 fec_group_number_
= sequence_number() + 1;
98 fec_group_
.reset(new QuicFecGroup());
102 // Stops serializing version of the protocol in packets sent after this call.
103 // A packet that is already open might send kQuicVersionSize bytes less than the
104 // maximum packet size if we stop sending version before it is serialized.
105 void QuicPacketCreator::StopSendingVersion() {
106 DCHECK(send_version_in_packet_
);
107 send_version_in_packet_
= false;
108 if (packet_size_
> 0) {
109 DCHECK_LT(kQuicVersionSize
, packet_size_
);
110 packet_size_
-= kQuicVersionSize
;
114 void QuicPacketCreator::UpdateSequenceNumberLength(
115 QuicPacketSequenceNumber least_packet_awaited_by_peer
,
116 QuicByteCount bytes_per_second
) {
117 DCHECK_LE(least_packet_awaited_by_peer
, sequence_number_
+ 1);
118 // Since the packet creator will not change sequence number length mid FEC
119 // group, include the size of an FEC group to be safe.
120 const QuicPacketSequenceNumber current_delta
=
121 options_
.max_packets_per_fec_group
+ sequence_number_
+ 1
122 - least_packet_awaited_by_peer
;
123 const uint64 congestion_window
=
124 bytes_per_second
/ options_
.max_packet_length
;
125 const uint64 delta
= max(current_delta
, congestion_window
);
127 options_
.send_sequence_number_length
=
128 QuicFramer::GetMinSequenceNumberLength(delta
* 4);
131 bool QuicPacketCreator::HasRoomForStreamFrame(QuicStreamId id
,
132 QuicStreamOffset offset
) const {
134 QuicFramer::GetMinStreamFrameSize(framer_
->version(), id
, offset
, true);
138 size_t QuicPacketCreator::StreamFramePacketOverhead(
140 QuicConnectionIdLength connection_id_length
,
141 bool include_version
,
142 QuicSequenceNumberLength sequence_number_length
,
143 InFecGroup is_in_fec_group
) {
144 return GetPacketHeaderSize(connection_id_length
, include_version
,
145 sequence_number_length
, is_in_fec_group
) +
146 // Assumes this is a stream with a single lone packet.
147 QuicFramer::GetMinStreamFrameSize(version
, 1u, 0u, true);
150 size_t QuicPacketCreator::CreateStreamFrame(QuicStreamId id
,
151 const IOVector
& data
,
152 QuicStreamOffset offset
,
155 DCHECK_GT(options_
.max_packet_length
,
156 StreamFramePacketOverhead(
157 framer_
->version(), PACKET_8BYTE_CONNECTION_ID
, kIncludeVersion
,
158 PACKET_6BYTE_SEQUENCE_NUMBER
, IN_FEC_GROUP
));
159 LOG_IF(DFATAL
, !HasRoomForStreamFrame(id
, offset
))
160 << "No room for Stream frame, BytesFree: " << BytesFree()
161 << " MinStreamFrameSize: "
162 << QuicFramer::GetMinStreamFrameSize(
163 framer_
->version(), id
, offset
, true);
167 << "Creating a stream frame with no data or fin.";
168 // Create a new packet for the fin, if necessary.
169 *frame
= QuicFrame(new QuicStreamFrame(id
, true, offset
, data
));
173 const size_t free_bytes
= BytesFree();
174 size_t bytes_consumed
= 0;
175 const size_t data_size
= data
.TotalBufferSize();
177 // When a STREAM frame is the last frame in a packet, it consumes two fewer
178 // bytes of framing overhead.
179 // Anytime more data is available than fits in with the extra two bytes,
180 // the frame will be the last, and up to two extra bytes are consumed.
181 // TODO(ianswett): If QUIC pads, the 1 byte PADDING frame does not fit when
182 // 1 byte is available, because then the STREAM frame isn't the last.
184 // The minimum frame size(0 bytes of data) if it's not the last frame.
185 size_t min_frame_size
= QuicFramer::GetMinStreamFrameSize(
186 framer_
->version(), id
, offset
, false);
187 // Check if it's the last frame in the packet.
188 if (data_size
+ min_frame_size
> free_bytes
) {
189 // The minimum frame size(0 bytes of data) if it is the last frame.
190 size_t min_last_frame_size
= QuicFramer::GetMinStreamFrameSize(
191 framer_
->version(), id
, offset
, true);
193 min
<size_t>(free_bytes
- min_last_frame_size
, data_size
);
195 DCHECK_LT(data_size
, BytesFree());
196 bytes_consumed
= data_size
;
199 bool set_fin
= fin
&& bytes_consumed
== data_size
; // Last frame.
201 frame_data
.AppendIovecAtMostBytes(data
.iovec(), data
.Size(),
203 DCHECK_EQ(frame_data
.TotalBufferSize(), bytes_consumed
);
204 *frame
= QuicFrame(new QuicStreamFrame(id
, set_fin
, offset
, frame_data
));
205 return bytes_consumed
;
208 size_t QuicPacketCreator::CreateStreamFrameWithNotifier(
210 const IOVector
& data
,
211 QuicStreamOffset offset
,
213 QuicAckNotifier
* notifier
,
215 size_t bytes_consumed
= CreateStreamFrame(id
, data
, offset
, fin
, frame
);
217 // The frame keeps track of the QuicAckNotifier until it is serialized into
218 // a packet. At that point the notifier is informed of the sequence number
219 // of the packet that this frame was eventually sent in.
220 frame
->stream_frame
->notifier
= notifier
;
222 return bytes_consumed
;
225 SerializedPacket
QuicPacketCreator::ReserializeAllFrames(
226 const QuicFrames
& frames
,
227 QuicSequenceNumberLength original_length
) {
228 const QuicSequenceNumberLength start_length
= sequence_number_length_
;
229 const QuicSequenceNumberLength start_options_length
=
230 options_
.send_sequence_number_length
;
231 const QuicFecGroupNumber start_fec_group
= fec_group_number_
;
232 const size_t start_max_packets_per_fec_group
=
233 options_
.max_packets_per_fec_group
;
235 // Temporarily set the sequence number length and disable FEC.
236 sequence_number_length_
= original_length
;
237 options_
.send_sequence_number_length
= original_length
;
238 fec_group_number_
= 0;
239 options_
.max_packets_per_fec_group
= 0;
241 // Serialize the packet and restore the fec and sequence number length state.
242 SerializedPacket serialized_packet
= SerializeAllFrames(frames
);
243 sequence_number_length_
= start_length
;
244 options_
.send_sequence_number_length
= start_options_length
;
245 fec_group_number_
= start_fec_group
;
246 options_
.max_packets_per_fec_group
= start_max_packets_per_fec_group
;
248 return serialized_packet
;
251 SerializedPacket
QuicPacketCreator::SerializeAllFrames(
252 const QuicFrames
& frames
) {
253 // TODO(satyamshekhar): Verify that this DCHECK won't fail. What about queued
254 // frames from SendStreamData()[send_stream_should_flush_ == false &&
255 // data.empty() == true] and retransmit due to RTO.
256 DCHECK_EQ(0u, queued_frames_
.size());
257 LOG_IF(DFATAL
, frames
.empty())
258 << "Attempt to serialize empty packet";
259 for (size_t i
= 0; i
< frames
.size(); ++i
) {
260 bool success
= AddFrame(frames
[i
], false);
263 SerializedPacket packet
= SerializePacket();
264 DCHECK(packet
.retransmittable_frames
== NULL
);
268 bool QuicPacketCreator::HasPendingFrames() {
269 return !queued_frames_
.empty();
272 size_t QuicPacketCreator::BytesFree() const {
273 const size_t max_plaintext_size
=
274 framer_
->GetMaxPlaintextSize(options_
.max_packet_length
);
275 DCHECK_GE(max_plaintext_size
, PacketSize());
277 // If the last frame in the packet is a stream frame, then it can be
278 // two bytes smaller than if it were not the last. So this means that
279 // there are two fewer bytes available to the next frame in this case.
280 bool has_trailing_stream_frame
=
281 !queued_frames_
.empty() && queued_frames_
.back().type
== STREAM_FRAME
;
282 size_t expanded_packet_size
= PacketSize() +
283 (has_trailing_stream_frame
? kQuicStreamPayloadLengthSize
: 0);
285 if (expanded_packet_size
>= max_plaintext_size
) {
288 return max_plaintext_size
- expanded_packet_size
;
291 size_t QuicPacketCreator::PacketSize() const {
292 if (queued_frames_
.empty()) {
293 // Only adjust the sequence number length when the FEC group is not open,
294 // to ensure no packets in a group are too large.
295 if (fec_group_
.get() == NULL
||
296 fec_group_
->NumReceivedPackets() == 0) {
297 sequence_number_length_
= options_
.send_sequence_number_length
;
299 packet_size_
= GetPacketHeaderSize(options_
.send_connection_id_length
,
300 send_version_in_packet_
,
301 sequence_number_length_
,
302 options_
.max_packets_per_fec_group
== 0 ?
303 NOT_IN_FEC_GROUP
: IN_FEC_GROUP
);
308 bool QuicPacketCreator::AddSavedFrame(const QuicFrame
& frame
) {
309 return AddFrame(frame
, true);
312 SerializedPacket
QuicPacketCreator::SerializePacket() {
313 LOG_IF(DFATAL
, queued_frames_
.empty())
314 << "Attempt to serialize empty packet";
315 QuicPacketHeader header
;
316 FillPacketHeader(fec_group_number_
, false, &header
);
320 size_t max_plaintext_size
=
321 framer_
->GetMaxPlaintextSize(options_
.max_packet_length
);
322 DCHECK_GE(max_plaintext_size
, packet_size_
);
323 // ACK and CONNECTION_CLOSE Frames will be truncated only if they're
324 // the first frame in the packet. If truncation is to occur, then
325 // GetSerializedFrameLength will have returned all bytes free.
326 bool possibly_truncated
=
327 packet_size_
!= max_plaintext_size
||
328 queued_frames_
.size() != 1 ||
329 (queued_frames_
.back().type
== ACK_FRAME
||
330 queued_frames_
.back().type
== CONNECTION_CLOSE_FRAME
);
331 SerializedPacket serialized
=
332 framer_
->BuildDataPacket(header
, queued_frames_
, packet_size_
);
333 LOG_IF(DFATAL
, !serialized
.packet
)
334 << "Failed to serialize " << queued_frames_
.size() << " frames.";
335 // Because of possible truncation, we can't be confident that our
336 // packet size calculation worked correctly.
337 if (!possibly_truncated
)
338 DCHECK_EQ(packet_size_
, serialized
.packet
->length());
341 queued_frames_
.clear();
342 serialized
.retransmittable_frames
= queued_retransmittable_frames_
.release();
346 SerializedPacket
QuicPacketCreator::SerializeFec() {
347 DCHECK_LT(0u, fec_group_
->NumReceivedPackets());
348 DCHECK_EQ(0u, queued_frames_
.size());
349 QuicPacketHeader header
;
350 FillPacketHeader(fec_group_number_
, true, &header
);
351 QuicFecData fec_data
;
352 fec_data
.fec_group
= fec_group_
->min_protected_packet();
353 fec_data
.redundancy
= fec_group_
->payload_parity();
354 SerializedPacket serialized
= framer_
->BuildFecPacket(header
, fec_data
);
355 fec_group_
.reset(NULL
);
356 fec_group_number_
= 0;
358 LOG_IF(DFATAL
, !serialized
.packet
)
359 << "Failed to serialize fec packet for group:" << fec_data
.fec_group
;
360 DCHECK_GE(options_
.max_packet_length
, serialized
.packet
->length());
364 SerializedPacket
QuicPacketCreator::SerializeConnectionClose(
365 QuicConnectionCloseFrame
* close_frame
) {
367 frames
.push_back(QuicFrame(close_frame
));
368 return SerializeAllFrames(frames
);
371 QuicEncryptedPacket
* QuicPacketCreator::SerializeVersionNegotiationPacket(
372 const QuicVersionVector
& supported_versions
) {
374 QuicPacketPublicHeader header
;
375 header
.connection_id
= connection_id_
;
376 header
.reset_flag
= false;
377 header
.version_flag
= true;
378 header
.versions
= supported_versions
;
379 QuicEncryptedPacket
* encrypted
=
380 framer_
->BuildVersionNegotiationPacket(header
, supported_versions
);
382 DCHECK_GE(options_
.max_packet_length
, encrypted
->length());
386 void QuicPacketCreator::FillPacketHeader(QuicFecGroupNumber fec_group
,
388 QuicPacketHeader
* header
) {
389 header
->public_header
.connection_id
= connection_id_
;
390 header
->public_header
.reset_flag
= false;
391 header
->public_header
.version_flag
= send_version_in_packet_
;
392 header
->fec_flag
= fec_flag
;
393 header
->packet_sequence_number
= ++sequence_number_
;
394 header
->public_header
.sequence_number_length
= sequence_number_length_
;
395 header
->entropy_flag
= random_bool_source_
->RandBool();
396 header
->is_in_fec_group
= fec_group
== 0 ? NOT_IN_FEC_GROUP
: IN_FEC_GROUP
;
397 header
->fec_group
= fec_group
;
400 bool QuicPacketCreator::ShouldRetransmit(const QuicFrame
& frame
) {
401 switch (frame
.type
) {
403 case CONGESTION_FEEDBACK_FRAME
:
405 case STOP_WAITING_FRAME
:
412 bool QuicPacketCreator::AddFrame(const QuicFrame
& frame
,
413 bool save_retransmittable_frames
) {
414 DVLOG(1) << "Adding frame: " << frame
;
415 size_t frame_len
= framer_
->GetSerializedFrameLength(
416 frame
, BytesFree(), queued_frames_
.empty(), true,
417 options()->send_sequence_number_length
);
418 if (frame_len
== 0) {
421 DCHECK_LT(0u, packet_size_
);
423 packet_size_
+= frame_len
;
424 // If the last frame in the packet was a stream frame, then once we add the
425 // new frame it's serialization will be two bytes larger.
426 if (!queued_frames_
.empty() && queued_frames_
.back().type
== STREAM_FRAME
) {
427 packet_size_
+= kQuicStreamPayloadLengthSize
;
429 if (save_retransmittable_frames
&& ShouldRetransmit(frame
)) {
430 if (queued_retransmittable_frames_
.get() == NULL
) {
431 queued_retransmittable_frames_
.reset(new RetransmittableFrames());
433 if (frame
.type
== STREAM_FRAME
) {
434 queued_frames_
.push_back(
435 queued_retransmittable_frames_
->AddStreamFrame(frame
.stream_frame
));
437 queued_frames_
.push_back(
438 queued_retransmittable_frames_
->AddNonStreamFrame(frame
));
441 queued_frames_
.push_back(frame
);
446 void QuicPacketCreator::MaybeAddPadding() {
447 if (BytesFree() == 0) {
448 // Don't pad full packets.
452 // If any of the frames in the current packet are on the crypto stream
453 // then they contain handshake messagses, and we should pad them.
454 bool is_handshake
= false;
455 for (size_t i
= 0; i
< queued_frames_
.size(); ++i
) {
456 if (queued_frames_
[i
].type
== STREAM_FRAME
&&
457 queued_frames_
[i
].stream_frame
->stream_id
== kCryptoStreamId
) {
466 QuicPaddingFrame padding
;
467 bool success
= AddFrame(QuicFrame(&padding
), false);