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"
9 #include "base/basictypes.h"
10 #include "base/logging.h"
11 #include "net/quic/crypto/quic_random.h"
12 #include "net/quic/quic_ack_notifier.h"
13 #include "net/quic/quic_data_writer.h"
14 #include "net/quic/quic_fec_group.h"
15 #include "net/quic/quic_utils.h"
17 using base::StringPiece
;
28 // Default max packets in an FEC group.
29 static const size_t kDefaultMaxPacketsPerFecGroup
= 10;
30 // Lowest max packets in an FEC group.
31 static const size_t kLowestMaxPacketsPerFecGroup
= 2;
35 // A QuicRandom wrapper that gets a bucket of entropy and distributes it
36 // bit-by-bit. Replenishes the bucket as needed. Not thread-safe. Expose this
37 // class if single bit randomness is needed elsewhere.
38 class QuicRandomBoolSource
{
40 // random: Source of entropy. Not owned.
41 explicit QuicRandomBoolSource(QuicRandom
* random
)
46 ~QuicRandomBoolSource() {}
48 // Returns the next random bit from the bucket.
51 bit_bucket_
= random_
->RandUint64();
54 bool result
= ((bit_bucket_
& bit_mask_
) != 0);
62 // Stored random bits.
64 // The next available bit has "1" in the mask. Zero means empty bucket.
67 DISALLOW_COPY_AND_ASSIGN(QuicRandomBoolSource
);
70 QuicPacketCreator::QuicPacketCreator(QuicConnectionId connection_id
,
72 QuicRandom
* random_generator
)
73 : connection_id_(connection_id
),
74 encryption_level_(ENCRYPTION_NONE
),
76 random_bool_source_(new QuicRandomBoolSource(random_generator
)),
78 should_fec_protect_(false),
80 send_version_in_packet_(framer
->perspective() == Perspective::IS_CLIENT
),
81 max_packets_per_fec_group_(kDefaultMaxPacketsPerFecGroup
),
82 connection_id_length_(PACKET_8BYTE_CONNECTION_ID
),
83 next_sequence_number_length_(PACKET_1BYTE_SEQUENCE_NUMBER
),
84 sequence_number_length_(next_sequence_number_length_
),
86 SetMaxPacketLength(kDefaultMaxPacketSize
);
89 QuicPacketCreator::~QuicPacketCreator() {
92 void QuicPacketCreator::OnBuiltFecProtectedPayload(
93 const QuicPacketHeader
& header
, StringPiece payload
) {
94 if (fec_group_
.get()) {
95 DCHECK_NE(0u, header
.fec_group
);
96 fec_group_
->Update(encryption_level_
, header
, payload
);
100 void QuicPacketCreator::SetEncrypter(EncryptionLevel level
,
101 QuicEncrypter
* encrypter
) {
102 framer_
->SetEncrypter(level
, encrypter
);
103 max_plaintext_size_
= framer_
->GetMaxPlaintextSize(max_packet_length_
);
106 void QuicPacketCreator::SetMaxPacketLength(QuicByteCount length
) {
107 // |max_packet_length_| should not be changed mid-packet or mid-FEC group.
108 DCHECK(fec_group_
.get() == nullptr && queued_frames_
.empty());
109 max_packet_length_
= length
;
110 max_plaintext_size_
= framer_
->GetMaxPlaintextSize(max_packet_length_
);
113 void QuicPacketCreator::set_max_packets_per_fec_group(
114 size_t max_packets_per_fec_group
) {
115 max_packets_per_fec_group_
= max(kLowestMaxPacketsPerFecGroup
,
116 max_packets_per_fec_group
);
117 DCHECK_LT(0u, max_packets_per_fec_group_
);
120 bool QuicPacketCreator::ShouldSendFec(bool force_close
) const {
121 DCHECK(!HasPendingFrames());
122 return fec_group_
.get() != nullptr && fec_group_
->NumReceivedPackets() > 0 &&
124 fec_group_
->NumReceivedPackets() >= max_packets_per_fec_group_
);
127 bool QuicPacketCreator::IsFecGroupOpen() const {
128 return fec_group_
.get() != nullptr;
131 void QuicPacketCreator::StartFecProtectingPackets() {
132 if (!IsFecEnabled()) {
133 LOG(DFATAL
) << "Cannot start FEC protection when FEC is not enabled.";
136 // TODO(jri): This currently requires that the generator flush out any
137 // pending frames when FEC protection is turned on. If current packet can be
138 // converted to an FEC protected packet, do it. This will require the
139 // generator to check if the resulting expansion still allows the incoming
140 // frame to be added to the packet.
141 if (HasPendingFrames()) {
142 LOG(DFATAL
) << "Cannot start FEC protection with pending frames.";
145 DCHECK(!should_fec_protect_
);
146 should_fec_protect_
= true;
149 void QuicPacketCreator::StopFecProtectingPackets() {
150 if (fec_group_
.get() != nullptr) {
151 LOG(DFATAL
) << "Cannot stop FEC protection with open FEC group.";
154 DCHECK(should_fec_protect_
);
155 should_fec_protect_
= false;
156 fec_group_number_
= 0;
159 bool QuicPacketCreator::IsFecProtected() const {
160 return should_fec_protect_
;
163 bool QuicPacketCreator::IsFecEnabled() const {
164 return max_packets_per_fec_group_
> 0;
167 InFecGroup
QuicPacketCreator::MaybeUpdateLengthsAndStartFec() {
168 if (fec_group_
.get() != nullptr) {
169 // Don't update any lengths when an FEC group is open, to ensure same
170 // packet header size in all packets within a group.
173 if (!queued_frames_
.empty()) {
174 // Don't change creator state if there are frames queued.
175 return fec_group_
.get() == nullptr ? NOT_IN_FEC_GROUP
: IN_FEC_GROUP
;
178 // Update sequence number length only on packet and FEC group boundaries.
179 sequence_number_length_
= next_sequence_number_length_
;
181 if (!should_fec_protect_
) {
182 return NOT_IN_FEC_GROUP
;
184 // Start a new FEC group since protection is on. Set the fec group number to
185 // the sequence number of the next packet.
186 fec_group_number_
= sequence_number() + 1;
187 fec_group_
.reset(new QuicFecGroup());
191 // Stops serializing version of the protocol in packets sent after this call.
192 // A packet that is already open might send kQuicVersionSize bytes less than the
193 // maximum packet size if we stop sending version before it is serialized.
194 void QuicPacketCreator::StopSendingVersion() {
195 DCHECK(send_version_in_packet_
);
196 send_version_in_packet_
= false;
197 if (packet_size_
> 0) {
198 DCHECK_LT(kQuicVersionSize
, packet_size_
);
199 packet_size_
-= kQuicVersionSize
;
203 void QuicPacketCreator::UpdateSequenceNumberLength(
204 QuicPacketSequenceNumber least_packet_awaited_by_peer
,
205 QuicPacketCount max_packets_in_flight
) {
206 DCHECK_LE(least_packet_awaited_by_peer
, sequence_number_
+ 1);
207 // Since the packet creator will not change sequence number length mid FEC
208 // group, include the size of an FEC group to be safe.
209 const QuicPacketSequenceNumber current_delta
=
210 max_packets_per_fec_group_
+ sequence_number_
+ 1
211 - least_packet_awaited_by_peer
;
212 const uint64 delta
= max(current_delta
, max_packets_in_flight
);
213 next_sequence_number_length_
=
214 QuicFramer::GetMinSequenceNumberLength(delta
* 4);
217 bool QuicPacketCreator::HasRoomForStreamFrame(QuicStreamId id
,
218 QuicStreamOffset offset
) const {
219 // TODO(jri): This is a simple safe decision for now, but make
220 // is_in_fec_group a parameter. Same as with all public methods in
221 // QuicPacketCreator.
223 QuicFramer::GetMinStreamFrameSize(id
, offset
, true,
224 should_fec_protect_
? IN_FEC_GROUP
:
229 size_t QuicPacketCreator::StreamFramePacketOverhead(
230 QuicConnectionIdLength connection_id_length
,
231 bool include_version
,
232 QuicSequenceNumberLength sequence_number_length
,
233 QuicStreamOffset offset
,
234 InFecGroup is_in_fec_group
) {
235 return GetPacketHeaderSize(connection_id_length
, include_version
,
236 sequence_number_length
, is_in_fec_group
) +
237 // Assumes this is a stream with a single lone packet.
238 QuicFramer::GetMinStreamFrameSize(1u, offset
, true, is_in_fec_group
);
241 size_t QuicPacketCreator::CreateStreamFrame(QuicStreamId id
,
242 const IOVector
& data
,
243 QuicStreamOffset offset
,
246 DCHECK_GT(max_packet_length_
, StreamFramePacketOverhead(
247 connection_id_length_
, kIncludeVersion
,
248 PACKET_6BYTE_SEQUENCE_NUMBER
, offset
, IN_FEC_GROUP
));
250 InFecGroup is_in_fec_group
= MaybeUpdateLengthsAndStartFec();
252 LOG_IF(DFATAL
, !HasRoomForStreamFrame(id
, offset
))
253 << "No room for Stream frame, BytesFree: " << BytesFree()
254 << " MinStreamFrameSize: "
255 << QuicFramer::GetMinStreamFrameSize(id
, offset
, true, is_in_fec_group
);
259 << "Creating a stream frame with no data or fin.";
260 // Create a new packet for the fin, if necessary.
261 *frame
= QuicFrame(new QuicStreamFrame(id
, true, offset
, data
));
265 const size_t data_size
= data
.TotalBufferSize();
266 size_t min_frame_size
= QuicFramer::GetMinStreamFrameSize(
267 id
, offset
, /* last_frame_in_packet= */ true, is_in_fec_group
);
268 size_t bytes_consumed
= min
<size_t>(BytesFree() - min_frame_size
, data_size
);
270 bool set_fin
= fin
&& bytes_consumed
== data_size
; // Last frame.
272 frame_data
.AppendIovecAtMostBytes(data
.iovec(), data
.Size(),
274 DCHECK_EQ(frame_data
.TotalBufferSize(), bytes_consumed
);
275 *frame
= QuicFrame(new QuicStreamFrame(id
, set_fin
, offset
, frame_data
));
276 return bytes_consumed
;
279 SerializedPacket
QuicPacketCreator::ReserializeAllFrames(
280 const RetransmittableFrames
& frames
,
281 QuicSequenceNumberLength original_length
,
284 DCHECK(fec_group_
.get() == nullptr);
285 const QuicSequenceNumberLength saved_length
= sequence_number_length_
;
286 const QuicSequenceNumberLength saved_next_length
=
287 next_sequence_number_length_
;
288 const bool saved_should_fec_protect
= should_fec_protect_
;
289 const EncryptionLevel default_encryption_level
= encryption_level_
;
291 // Temporarily set the sequence number length, stop FEC protection,
292 // and change the encryption level.
293 sequence_number_length_
= original_length
;
294 next_sequence_number_length_
= original_length
;
295 should_fec_protect_
= false;
296 encryption_level_
= frames
.encryption_level();
298 // Serialize the packet and restore the FEC and sequence number length state.
299 SerializedPacket serialized_packet
=
300 SerializeAllFrames(frames
.frames(), buffer
, buffer_len
);
301 sequence_number_length_
= saved_length
;
302 next_sequence_number_length_
= saved_next_length
;
303 should_fec_protect_
= saved_should_fec_protect
;
304 encryption_level_
= default_encryption_level
;
306 return serialized_packet
;
309 SerializedPacket
QuicPacketCreator::SerializeAllFrames(const QuicFrames
& frames
,
312 LOG_IF(DFATAL
, !queued_frames_
.empty()) << "Frames already queued.";
313 LOG_IF(DFATAL
, frames
.empty())
314 << "Attempt to serialize empty packet";
315 for (const QuicFrame
& frame
: frames
) {
316 bool success
= AddFrame(frame
, false);
319 SerializedPacket packet
= SerializePacket(buffer
, buffer_len
);
320 DCHECK(packet
.retransmittable_frames
== nullptr);
324 bool QuicPacketCreator::HasPendingFrames() const {
325 return !queued_frames_
.empty();
328 bool QuicPacketCreator::HasPendingRetransmittableFrames() const {
329 return queued_retransmittable_frames_
.get() != nullptr &&
330 !queued_retransmittable_frames_
->frames().empty();
333 size_t QuicPacketCreator::ExpansionOnNewFrame() const {
334 // If packet is FEC protected, there's no expansion.
335 if (should_fec_protect_
) {
338 // If the last frame in the packet is a stream frame, then it will expand to
339 // include the stream_length field when a new frame is added.
340 bool has_trailing_stream_frame
=
341 !queued_frames_
.empty() && queued_frames_
.back().type
== STREAM_FRAME
;
342 return has_trailing_stream_frame
? kQuicStreamPayloadLengthSize
: 0;
345 size_t QuicPacketCreator::BytesFree() const {
346 DCHECK_GE(max_plaintext_size_
, PacketSize());
347 return max_plaintext_size_
- min(max_plaintext_size_
, PacketSize()
348 + ExpansionOnNewFrame());
351 size_t QuicPacketCreator::PacketSize() const {
352 if (!queued_frames_
.empty()) {
355 if (fec_group_
.get() == nullptr) {
356 // Update sequence number length on packet and FEC boundary.
357 sequence_number_length_
= next_sequence_number_length_
;
359 packet_size_
= GetPacketHeaderSize(
360 connection_id_length_
, send_version_in_packet_
, sequence_number_length_
,
361 should_fec_protect_
? IN_FEC_GROUP
: NOT_IN_FEC_GROUP
);
365 bool QuicPacketCreator::AddSavedFrame(const QuicFrame
& frame
) {
366 return AddFrame(frame
, true);
369 SerializedPacket
QuicPacketCreator::SerializePacket(
370 char* encrypted_buffer
,
371 size_t encrypted_buffer_len
) {
372 DCHECK_LT(0u, encrypted_buffer_len
);
373 LOG_IF(DFATAL
, queued_frames_
.empty())
374 << "Attempt to serialize empty packet";
375 DCHECK_GE(sequence_number_
+ 1, fec_group_number_
);
376 QuicPacketHeader header
;
377 FillPacketHeader(should_fec_protect_
? fec_group_number_
: 0, false, &header
);
381 DCHECK_GE(max_plaintext_size_
, packet_size_
);
382 // ACK Frames will be truncated due to length only if they're the only frame
383 // in the packet, and if packet_size_ was set to max_plaintext_size_. If
384 // truncation due to length occurred, then GetSerializedFrameLength will have
385 // returned all bytes free.
386 bool possibly_truncated_by_length
= packet_size_
== max_plaintext_size_
&&
387 queued_frames_
.size() == 1 &&
388 queued_frames_
.back().type
== ACK_FRAME
;
389 char buffer
[kMaxPacketSize
];
390 scoped_ptr
<QuicPacket
> packet
;
391 // Use the packet_size_ instead of the buffer size to ensure smaller
392 // packet sizes are properly used.
393 scoped_ptr
<char[]> large_buffer
;
394 if (packet_size_
<= kMaxPacketSize
) {
396 framer_
->BuildDataPacket(header
, queued_frames_
, buffer
, packet_size_
));
398 large_buffer
.reset(new char[packet_size_
]);
399 packet
.reset(framer_
->BuildDataPacket(header
, queued_frames_
,
400 large_buffer
.get(), packet_size_
));
402 OnBuiltFecProtectedPayload(header
, packet
->FecProtectedData());
404 LOG_IF(DFATAL
, packet
== nullptr) << "Failed to serialize "
405 << queued_frames_
.size() << " frames.";
406 // Because of possible truncation, we can't be confident that our
407 // packet size calculation worked correctly.
408 if (!possibly_truncated_by_length
) {
409 DCHECK_EQ(packet_size_
, packet
->length());
411 // Immediately encrypt the packet, to ensure we don't encrypt the same packet
412 // sequence number multiple times.
413 QuicEncryptedPacket
* encrypted
=
414 framer_
->EncryptPacket(encryption_level_
, sequence_number_
, *packet
,
415 encrypted_buffer
, encrypted_buffer_len
);
416 if (encrypted
== nullptr) {
417 LOG(DFATAL
) << "Failed to encrypt packet number " << sequence_number_
;
422 queued_frames_
.clear();
423 return SerializedPacket(header
.packet_sequence_number
,
424 header
.public_header
.sequence_number_length
,
425 encrypted
, QuicFramer::GetPacketEntropyHash(header
),
426 queued_retransmittable_frames_
.release());
429 SerializedPacket
QuicPacketCreator::SerializeFec(char* buffer
,
431 DCHECK_LT(0u, buffer_len
);
432 if (fec_group_
.get() == nullptr || fec_group_
->NumReceivedPackets() <= 0) {
433 LOG(DFATAL
) << "SerializeFEC called but no group or zero packets in group.";
434 // TODO(jri): Make this a public method of framer?
437 DCHECK_EQ(0u, queued_frames_
.size());
438 QuicPacketHeader header
;
439 FillPacketHeader(fec_group_number_
, true, &header
);
440 QuicFecData fec_data
;
441 fec_data
.fec_group
= fec_group_
->min_protected_packet();
442 fec_data
.redundancy
= fec_group_
->payload_parity();
443 scoped_ptr
<QuicPacket
> packet(framer_
->BuildFecPacket(header
, fec_data
));
444 fec_group_
.reset(nullptr);
446 LOG_IF(DFATAL
, packet
== nullptr)
447 << "Failed to serialize fec packet for group:" << fec_data
.fec_group
;
448 DCHECK_GE(max_packet_length_
, packet
->length());
449 // Immediately encrypt the packet, to ensure we don't encrypt the same packet
450 // sequence number multiple times.
451 QuicEncryptedPacket
* encrypted
= framer_
->EncryptPacket(
452 encryption_level_
, sequence_number_
, *packet
, buffer
, buffer_len
);
453 if (encrypted
== nullptr) {
454 LOG(DFATAL
) << "Failed to encrypt packet number " << sequence_number_
;
457 SerializedPacket
serialized(
458 header
.packet_sequence_number
,
459 header
.public_header
.sequence_number_length
, encrypted
,
460 QuicFramer::GetPacketEntropyHash(header
), nullptr);
461 serialized
.is_fec_packet
= true;
465 QuicEncryptedPacket
* QuicPacketCreator::SerializeVersionNegotiationPacket(
466 const QuicVersionVector
& supported_versions
) {
467 DCHECK_EQ(Perspective::IS_SERVER
, framer_
->perspective());
468 QuicPacketPublicHeader header
;
469 header
.connection_id
= connection_id_
;
470 header
.reset_flag
= false;
471 header
.version_flag
= true;
472 header
.versions
= supported_versions
;
473 QuicEncryptedPacket
* encrypted
=
474 framer_
->BuildVersionNegotiationPacket(header
, supported_versions
);
476 DCHECK_GE(max_packet_length_
, encrypted
->length());
480 SerializedPacket
QuicPacketCreator::NoPacket() {
481 return SerializedPacket(0, PACKET_1BYTE_SEQUENCE_NUMBER
, nullptr, 0, nullptr);
484 void QuicPacketCreator::FillPacketHeader(QuicFecGroupNumber fec_group
,
486 QuicPacketHeader
* header
) {
487 header
->public_header
.connection_id
= connection_id_
;
488 header
->public_header
.connection_id_length
= connection_id_length_
;
489 header
->public_header
.reset_flag
= false;
490 header
->public_header
.version_flag
= send_version_in_packet_
;
491 header
->fec_flag
= fec_flag
;
492 header
->packet_sequence_number
= ++sequence_number_
;
493 header
->public_header
.sequence_number_length
= sequence_number_length_
;
494 header
->entropy_flag
= random_bool_source_
->RandBool();
495 header
->is_in_fec_group
= fec_group
== 0 ? NOT_IN_FEC_GROUP
: IN_FEC_GROUP
;
496 header
->fec_group
= fec_group
;
499 bool QuicPacketCreator::ShouldRetransmit(const QuicFrame
& frame
) {
500 switch (frame
.type
) {
503 case STOP_WAITING_FRAME
:
510 bool QuicPacketCreator::AddFrame(const QuicFrame
& frame
,
511 bool save_retransmittable_frames
) {
512 DVLOG(1) << "Adding frame: " << frame
;
513 InFecGroup is_in_fec_group
= MaybeUpdateLengthsAndStartFec();
515 size_t frame_len
= framer_
->GetSerializedFrameLength(
516 frame
, BytesFree(), queued_frames_
.empty(), true, is_in_fec_group
,
517 sequence_number_length_
);
518 if (frame_len
== 0) {
521 DCHECK_LT(0u, packet_size_
);
522 packet_size_
+= ExpansionOnNewFrame() + frame_len
;
524 if (save_retransmittable_frames
&& ShouldRetransmit(frame
)) {
525 if (queued_retransmittable_frames_
.get() == nullptr) {
526 queued_retransmittable_frames_
.reset(
527 new RetransmittableFrames(encryption_level_
));
529 if (frame
.type
== STREAM_FRAME
) {
530 queued_frames_
.push_back(
531 queued_retransmittable_frames_
->AddStreamFrame(frame
.stream_frame
));
533 queued_frames_
.push_back(
534 queued_retransmittable_frames_
->AddNonStreamFrame(frame
));
537 queued_frames_
.push_back(frame
);
542 void QuicPacketCreator::MaybeAddPadding() {
543 if (BytesFree() == 0) {
544 // Don't pad full packets.
548 // Since ReserializeAllFrames does not populate queued_retransmittable_frames_
549 // it's not sufficient to simply call
550 // queued_retransmittable_frames_->HasCryptoHandshake().
551 // TODO(rch): we should really make ReserializeAllFrames not be a special
554 // If any of the frames in the current packet are on the crypto stream
555 // then they contain handshake messagses, and we should pad them.
556 bool is_handshake
= false;
557 for (const QuicFrame
& frame
: queued_frames_
) {
558 if (frame
.type
== STREAM_FRAME
&&
559 frame
.stream_frame
->stream_id
== kCryptoStreamId
) {
568 QuicPaddingFrame padding
;
569 bool success
= AddFrame(QuicFrame(&padding
), false);