Roll src/third_party/skia ff271c2:b679ca8
[chromium-blink-merge.git] / net / quic / quic_packet_creator.cc
blob6fcc9012824675b79777c090773df8adb4b63615
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_data_writer.h"
12 #include "net/quic/quic_fec_group.h"
13 #include "net/quic/quic_utils.h"
15 using base::StringPiece;
16 using std::make_pair;
17 using std::max;
18 using std::min;
19 using std::pair;
20 using std::vector;
22 namespace net {
24 namespace {
26 // Default max packets in an FEC group.
27 static const size_t kDefaultMaxPacketsPerFecGroup = 10;
28 // Lowest max packets in an FEC group.
29 static const size_t kLowestMaxPacketsPerFecGroup = 2;
31 } // namespace
33 // A QuicRandom wrapper that gets a bucket of entropy and distributes it
34 // bit-by-bit. Replenishes the bucket as needed. Not thread-safe. Expose this
35 // class if single bit randomness is needed elsewhere.
36 class QuicRandomBoolSource {
37 public:
38 // random: Source of entropy. Not owned.
39 explicit QuicRandomBoolSource(QuicRandom* random)
40 : random_(random),
41 bit_bucket_(0),
42 bit_mask_(0) {}
44 ~QuicRandomBoolSource() {}
46 // Returns the next random bit from the bucket.
47 bool RandBool() {
48 if (bit_mask_ == 0) {
49 bit_bucket_ = random_->RandUint64();
50 bit_mask_ = 1;
52 bool result = ((bit_bucket_ & bit_mask_) != 0);
53 bit_mask_ <<= 1;
54 return result;
57 private:
58 // Source of entropy.
59 QuicRandom* random_;
60 // Stored random bits.
61 uint64 bit_bucket_;
62 // The next available bit has "1" in the mask. Zero means empty bucket.
63 uint64 bit_mask_;
65 DISALLOW_COPY_AND_ASSIGN(QuicRandomBoolSource);
68 QuicPacketCreator::QuicPacketCreator(QuicConnectionId connection_id,
69 QuicFramer* framer,
70 QuicRandom* random_generator)
71 : connection_id_(connection_id),
72 encryption_level_(ENCRYPTION_NONE),
73 framer_(framer),
74 random_bool_source_(new QuicRandomBoolSource(random_generator)),
75 sequence_number_(0),
76 should_fec_protect_(false),
77 fec_group_number_(0),
78 send_version_in_packet_(framer->perspective() == Perspective::IS_CLIENT),
79 max_packets_per_fec_group_(kDefaultMaxPacketsPerFecGroup),
80 connection_id_length_(PACKET_8BYTE_CONNECTION_ID),
81 next_sequence_number_length_(PACKET_1BYTE_SEQUENCE_NUMBER),
82 sequence_number_length_(next_sequence_number_length_),
83 packet_size_(0) {
84 SetMaxPacketLength(kDefaultMaxPacketSize);
85 framer_->set_fec_builder(this);
88 QuicPacketCreator::~QuicPacketCreator() {
91 void QuicPacketCreator::OnBuiltFecProtectedPayload(
92 const QuicPacketHeader& header, StringPiece payload) {
93 if (fec_group_.get()) {
94 DCHECK_NE(0u, header.fec_group);
95 fec_group_->Update(encryption_level_, header, payload);
99 void QuicPacketCreator::SetEncrypter(EncryptionLevel level,
100 QuicEncrypter* encrypter) {
101 framer_->SetEncrypter(level, encrypter);
102 max_plaintext_size_ = framer_->GetMaxPlaintextSize(max_packet_length_);
105 void QuicPacketCreator::SetMaxPacketLength(QuicByteCount length) {
106 // |max_packet_length_| should not be changed mid-packet or mid-FEC group.
107 DCHECK(fec_group_.get() == nullptr && queued_frames_.empty());
108 max_packet_length_ = length;
109 max_plaintext_size_ = framer_->GetMaxPlaintextSize(max_packet_length_);
112 void QuicPacketCreator::set_max_packets_per_fec_group(
113 size_t max_packets_per_fec_group) {
114 max_packets_per_fec_group_ = max(kLowestMaxPacketsPerFecGroup,
115 max_packets_per_fec_group);
116 DCHECK_LT(0u, max_packets_per_fec_group_);
119 bool QuicPacketCreator::ShouldSendFec(bool force_close) const {
120 DCHECK(!HasPendingFrames());
121 return fec_group_.get() != nullptr && fec_group_->NumReceivedPackets() > 0 &&
122 (force_close ||
123 fec_group_->NumReceivedPackets() >= max_packets_per_fec_group_);
126 bool QuicPacketCreator::IsFecGroupOpen() const {
127 return fec_group_.get() != nullptr;
130 void QuicPacketCreator::StartFecProtectingPackets() {
131 if (!IsFecEnabled()) {
132 LOG(DFATAL) << "Cannot start FEC protection when FEC is not enabled.";
133 return;
135 // TODO(jri): This currently requires that the generator flush out any
136 // pending frames when FEC protection is turned on. If current packet can be
137 // converted to an FEC protected packet, do it. This will require the
138 // generator to check if the resulting expansion still allows the incoming
139 // frame to be added to the packet.
140 if (HasPendingFrames()) {
141 LOG(DFATAL) << "Cannot start FEC protection with pending frames.";
142 return;
144 DCHECK(!should_fec_protect_);
145 should_fec_protect_ = true;
148 void QuicPacketCreator::StopFecProtectingPackets() {
149 if (fec_group_.get() != nullptr) {
150 LOG(DFATAL) << "Cannot stop FEC protection with open FEC group.";
151 return;
153 DCHECK(should_fec_protect_);
154 should_fec_protect_ = false;
155 fec_group_number_ = 0;
158 bool QuicPacketCreator::IsFecProtected() const {
159 return should_fec_protect_;
162 bool QuicPacketCreator::IsFecEnabled() const {
163 return max_packets_per_fec_group_ > 0;
166 InFecGroup QuicPacketCreator::MaybeUpdateLengthsAndStartFec() {
167 if (fec_group_.get() != nullptr) {
168 // Don't update any lengths when an FEC group is open, to ensure same
169 // packet header size in all packets within a group.
170 return IN_FEC_GROUP;
172 if (!queued_frames_.empty()) {
173 // Don't change creator state if there are frames queued.
174 return fec_group_.get() == nullptr ? NOT_IN_FEC_GROUP : IN_FEC_GROUP;
177 // Update sequence number length only on packet and FEC group boundaries.
178 sequence_number_length_ = next_sequence_number_length_;
180 if (!should_fec_protect_) {
181 return NOT_IN_FEC_GROUP;
183 // Start a new FEC group since protection is on. Set the fec group number to
184 // the sequence number of the next packet.
185 fec_group_number_ = sequence_number() + 1;
186 fec_group_.reset(new QuicFecGroup());
187 return IN_FEC_GROUP;
190 // Stops serializing version of the protocol in packets sent after this call.
191 // A packet that is already open might send kQuicVersionSize bytes less than the
192 // maximum packet size if we stop sending version before it is serialized.
193 void QuicPacketCreator::StopSendingVersion() {
194 DCHECK(send_version_in_packet_);
195 send_version_in_packet_ = false;
196 if (packet_size_ > 0) {
197 DCHECK_LT(kQuicVersionSize, packet_size_);
198 packet_size_ -= kQuicVersionSize;
202 void QuicPacketCreator::UpdateSequenceNumberLength(
203 QuicPacketSequenceNumber least_packet_awaited_by_peer,
204 QuicPacketCount max_packets_in_flight) {
205 DCHECK_LE(least_packet_awaited_by_peer, sequence_number_ + 1);
206 // Since the packet creator will not change sequence number length mid FEC
207 // group, include the size of an FEC group to be safe.
208 const QuicPacketSequenceNumber current_delta =
209 max_packets_per_fec_group_ + sequence_number_ + 1
210 - least_packet_awaited_by_peer;
211 const uint64 delta = max(current_delta, max_packets_in_flight);
212 next_sequence_number_length_ =
213 QuicFramer::GetMinSequenceNumberLength(delta * 4);
216 bool QuicPacketCreator::HasRoomForStreamFrame(QuicStreamId id,
217 QuicStreamOffset offset) const {
218 // TODO(jri): This is a simple safe decision for now, but make
219 // is_in_fec_group a parameter. Same as with all public methods in
220 // QuicPacketCreator.
221 return BytesFree() >
222 QuicFramer::GetMinStreamFrameSize(id, offset, true,
223 should_fec_protect_ ? IN_FEC_GROUP :
224 NOT_IN_FEC_GROUP);
227 // static
228 size_t QuicPacketCreator::StreamFramePacketOverhead(
229 QuicConnectionIdLength connection_id_length,
230 bool include_version,
231 QuicSequenceNumberLength sequence_number_length,
232 QuicStreamOffset offset,
233 InFecGroup is_in_fec_group) {
234 return GetPacketHeaderSize(connection_id_length, include_version,
235 sequence_number_length, is_in_fec_group) +
236 // Assumes this is a stream with a single lone packet.
237 QuicFramer::GetMinStreamFrameSize(1u, offset, true, is_in_fec_group);
240 size_t QuicPacketCreator::CreateStreamFrame(QuicStreamId id,
241 const IOVector& data,
242 QuicStreamOffset offset,
243 bool fin,
244 QuicFrame* frame) {
245 DCHECK_GT(max_packet_length_, StreamFramePacketOverhead(
246 connection_id_length_, kIncludeVersion,
247 PACKET_6BYTE_SEQUENCE_NUMBER, offset, IN_FEC_GROUP));
249 InFecGroup is_in_fec_group = MaybeUpdateLengthsAndStartFec();
251 LOG_IF(DFATAL, !HasRoomForStreamFrame(id, offset))
252 << "No room for Stream frame, BytesFree: " << BytesFree()
253 << " MinStreamFrameSize: "
254 << QuicFramer::GetMinStreamFrameSize(id, offset, true, is_in_fec_group);
256 if (data.Empty()) {
257 LOG_IF(DFATAL, !fin)
258 << "Creating a stream frame with no data or fin.";
259 // Create a new packet for the fin, if necessary.
260 *frame = QuicFrame(new QuicStreamFrame(id, true, offset, data));
261 return 0;
264 const size_t data_size = data.TotalBufferSize();
265 size_t min_frame_size = QuicFramer::GetMinStreamFrameSize(
266 id, offset, /* last_frame_in_packet= */ true, is_in_fec_group);
267 size_t bytes_consumed = min<size_t>(BytesFree() - min_frame_size, data_size);
269 bool set_fin = fin && bytes_consumed == data_size; // Last frame.
270 IOVector frame_data;
271 frame_data.AppendIovecAtMostBytes(data.iovec(), data.Size(),
272 bytes_consumed);
273 DCHECK_EQ(frame_data.TotalBufferSize(), bytes_consumed);
274 *frame = QuicFrame(new QuicStreamFrame(id, set_fin, offset, frame_data));
275 return bytes_consumed;
278 SerializedPacket QuicPacketCreator::ReserializeAllFrames(
279 const RetransmittableFrames& frames,
280 QuicSequenceNumberLength original_length) {
281 DCHECK(fec_group_.get() == nullptr);
282 const QuicSequenceNumberLength saved_length = sequence_number_length_;
283 const QuicSequenceNumberLength saved_next_length =
284 next_sequence_number_length_;
285 const bool saved_should_fec_protect = should_fec_protect_;
286 const EncryptionLevel default_encryption_level = encryption_level_;
288 // Temporarily set the sequence number length, stop FEC protection,
289 // and change the encryption level.
290 sequence_number_length_ = original_length;
291 next_sequence_number_length_ = original_length;
292 should_fec_protect_ = false;
293 encryption_level_ = frames.encryption_level();
295 // Serialize the packet and restore the FEC and sequence number length state.
296 SerializedPacket serialized_packet = SerializeAllFrames(frames.frames());
297 sequence_number_length_ = saved_length;
298 next_sequence_number_length_ = saved_next_length;
299 should_fec_protect_ = saved_should_fec_protect;
300 encryption_level_ = default_encryption_level;
302 return serialized_packet;
305 // TODO(ianswett): Remove this method, because it's test only.
306 SerializedPacket QuicPacketCreator::SerializeAllFrames(
307 const QuicFrames& frames) {
308 // TODO(satyamshekhar): Verify that this DCHECK won't fail. What about queued
309 // frames from SendStreamData()[send_stream_should_flush_ == false &&
310 // data.empty() == true] and retransmit due to RTO.
311 DCHECK_EQ(0u, queued_frames_.size());
312 LOG_IF(DFATAL, frames.empty())
313 << "Attempt to serialize empty packet";
314 for (const QuicFrame& frame : frames) {
315 bool success = AddFrame(frame, false);
316 DCHECK(success);
318 SerializedPacket packet = SerializePacket();
319 DCHECK(packet.retransmittable_frames == nullptr);
320 return packet;
323 bool QuicPacketCreator::HasPendingFrames() const {
324 return !queued_frames_.empty();
327 bool QuicPacketCreator::HasPendingRetransmittableFrames() const {
328 return queued_retransmittable_frames_.get() != nullptr &&
329 !queued_retransmittable_frames_->frames().empty();
332 size_t QuicPacketCreator::ExpansionOnNewFrame() const {
333 // If packet is FEC protected, there's no expansion.
334 if (should_fec_protect_) {
335 return 0;
337 // If the last frame in the packet is a stream frame, then it will expand to
338 // include the stream_length field when a new frame is added.
339 bool has_trailing_stream_frame =
340 !queued_frames_.empty() && queued_frames_.back().type == STREAM_FRAME;
341 return has_trailing_stream_frame ? kQuicStreamPayloadLengthSize : 0;
344 size_t QuicPacketCreator::BytesFree() const {
345 DCHECK_GE(max_plaintext_size_, PacketSize());
346 return max_plaintext_size_ - min(max_plaintext_size_, PacketSize()
347 + ExpansionOnNewFrame());
350 size_t QuicPacketCreator::PacketSize() const {
351 if (!queued_frames_.empty()) {
352 return packet_size_;
354 if (fec_group_.get() == nullptr) {
355 // Update sequence number length on packet and FEC boundary.
356 sequence_number_length_ = next_sequence_number_length_;
358 packet_size_ = GetPacketHeaderSize(
359 connection_id_length_, send_version_in_packet_, sequence_number_length_,
360 should_fec_protect_ ? IN_FEC_GROUP : NOT_IN_FEC_GROUP);
361 return packet_size_;
364 bool QuicPacketCreator::AddSavedFrame(const QuicFrame& frame) {
365 return AddFrame(frame, true);
368 SerializedPacket QuicPacketCreator::SerializePacket() {
369 LOG_IF(DFATAL, queued_frames_.empty())
370 << "Attempt to serialize empty packet";
371 DCHECK_GE(sequence_number_ + 1, fec_group_number_);
372 QuicPacketHeader header;
373 FillPacketHeader(should_fec_protect_ ? fec_group_number_ : 0, false, &header);
375 MaybeAddPadding();
377 DCHECK_GE(max_plaintext_size_, packet_size_);
378 // ACK Frames will be truncated due to length only if they're the only frame
379 // in the packet, and if packet_size_ was set to max_plaintext_size_. If
380 // truncation due to length occurred, then GetSerializedFrameLength will have
381 // returned all bytes free.
382 bool possibly_truncated_by_length = packet_size_ == max_plaintext_size_ &&
383 queued_frames_.size() == 1 &&
384 queued_frames_.back().type == ACK_FRAME;
385 char buffer[kMaxPacketSize];
386 scoped_ptr<QuicPacket> packet;
387 // Use the packet_size_ instead of the buffer size to ensure smaller
388 // packet sizes are properly used.
389 scoped_ptr<char[]> large_buffer;
390 if (packet_size_ <= kMaxPacketSize) {
391 packet.reset(
392 framer_->BuildDataPacket(header, queued_frames_, buffer, packet_size_));
393 } else {
394 large_buffer.reset(new char[packet_size_]);
395 packet.reset(framer_->BuildDataPacket(header, queued_frames_,
396 large_buffer.get(), packet_size_));
398 LOG_IF(DFATAL, packet == nullptr) << "Failed to serialize "
399 << queued_frames_.size() << " frames.";
400 // Because of possible truncation, we can't be confident that our
401 // packet size calculation worked correctly.
402 if (!possibly_truncated_by_length) {
403 DCHECK_EQ(packet_size_, packet->length());
405 // Immediately encrypt the packet, to ensure we don't encrypt the same packet
406 // sequence number multiple times.
407 QuicEncryptedPacket* encrypted =
408 framer_->EncryptPacket(encryption_level_, sequence_number_, *packet);
409 if (encrypted == nullptr) {
410 LOG(DFATAL) << "Failed to encrypt packet number " << sequence_number_;
411 return NoPacket();
414 packet_size_ = 0;
415 queued_frames_.clear();
416 return SerializedPacket(header.packet_sequence_number,
417 header.public_header.sequence_number_length,
418 encrypted, QuicFramer::GetPacketEntropyHash(header),
419 queued_retransmittable_frames_.release());
422 SerializedPacket QuicPacketCreator::SerializeFec() {
423 if (fec_group_.get() == nullptr || fec_group_->NumReceivedPackets() <= 0) {
424 LOG(DFATAL) << "SerializeFEC called but no group or zero packets in group.";
425 // TODO(jri): Make this a public method of framer?
426 return NoPacket();
428 DCHECK_EQ(0u, queued_frames_.size());
429 QuicPacketHeader header;
430 FillPacketHeader(fec_group_number_, true, &header);
431 QuicFecData fec_data;
432 fec_data.fec_group = fec_group_->min_protected_packet();
433 fec_data.redundancy = fec_group_->payload_parity();
434 scoped_ptr<QuicPacket> packet(framer_->BuildFecPacket(header, fec_data));
435 fec_group_.reset(nullptr);
436 packet_size_ = 0;
437 LOG_IF(DFATAL, packet == nullptr)
438 << "Failed to serialize fec packet for group:" << fec_data.fec_group;
439 DCHECK_GE(max_packet_length_, packet->length());
440 // Immediately encrypt the packet, to ensure we don't encrypt the same packet
441 // sequence number multiple times.
442 QuicEncryptedPacket* encrypted =
443 framer_->EncryptPacket(encryption_level_, sequence_number_, *packet);
444 if (encrypted == nullptr) {
445 LOG(DFATAL) << "Failed to encrypt packet number " << sequence_number_;
446 return NoPacket();
448 SerializedPacket serialized(
449 header.packet_sequence_number,
450 header.public_header.sequence_number_length, encrypted,
451 QuicFramer::GetPacketEntropyHash(header), nullptr);
452 serialized.is_fec_packet = true;
453 return serialized;
456 QuicEncryptedPacket* QuicPacketCreator::SerializeVersionNegotiationPacket(
457 const QuicVersionVector& supported_versions) {
458 DCHECK_EQ(Perspective::IS_SERVER, framer_->perspective());
459 QuicPacketPublicHeader header;
460 header.connection_id = connection_id_;
461 header.reset_flag = false;
462 header.version_flag = true;
463 header.versions = supported_versions;
464 QuicEncryptedPacket* encrypted =
465 framer_->BuildVersionNegotiationPacket(header, supported_versions);
466 DCHECK(encrypted);
467 DCHECK_GE(max_packet_length_, encrypted->length());
468 return encrypted;
471 SerializedPacket QuicPacketCreator::NoPacket() {
472 return SerializedPacket(0, PACKET_1BYTE_SEQUENCE_NUMBER, nullptr, 0, nullptr);
475 void QuicPacketCreator::FillPacketHeader(QuicFecGroupNumber fec_group,
476 bool fec_flag,
477 QuicPacketHeader* header) {
478 header->public_header.connection_id = connection_id_;
479 header->public_header.connection_id_length = connection_id_length_;
480 header->public_header.reset_flag = false;
481 header->public_header.version_flag = send_version_in_packet_;
482 header->fec_flag = fec_flag;
483 header->packet_sequence_number = ++sequence_number_;
484 header->public_header.sequence_number_length = sequence_number_length_;
485 header->entropy_flag = random_bool_source_->RandBool();
486 header->is_in_fec_group = fec_group == 0 ? NOT_IN_FEC_GROUP : IN_FEC_GROUP;
487 header->fec_group = fec_group;
490 bool QuicPacketCreator::ShouldRetransmit(const QuicFrame& frame) {
491 switch (frame.type) {
492 case ACK_FRAME:
493 case PADDING_FRAME:
494 case STOP_WAITING_FRAME:
495 return false;
496 default:
497 return true;
501 bool QuicPacketCreator::AddFrame(const QuicFrame& frame,
502 bool save_retransmittable_frames) {
503 DVLOG(1) << "Adding frame: " << frame;
504 InFecGroup is_in_fec_group = MaybeUpdateLengthsAndStartFec();
506 size_t frame_len = framer_->GetSerializedFrameLength(
507 frame, BytesFree(), queued_frames_.empty(), true, is_in_fec_group,
508 sequence_number_length_);
509 if (frame_len == 0) {
510 return false;
512 DCHECK_LT(0u, packet_size_);
513 packet_size_ += ExpansionOnNewFrame() + frame_len;
515 if (save_retransmittable_frames && ShouldRetransmit(frame)) {
516 if (queued_retransmittable_frames_.get() == nullptr) {
517 queued_retransmittable_frames_.reset(
518 new RetransmittableFrames(encryption_level_));
520 if (frame.type == STREAM_FRAME) {
521 queued_frames_.push_back(
522 queued_retransmittable_frames_->AddStreamFrame(frame.stream_frame));
523 } else {
524 queued_frames_.push_back(
525 queued_retransmittable_frames_->AddNonStreamFrame(frame));
527 } else {
528 queued_frames_.push_back(frame);
530 return true;
533 void QuicPacketCreator::MaybeAddPadding() {
534 if (BytesFree() == 0) {
535 // Don't pad full packets.
536 return;
539 // Since ReserializeAllFrames does not populate queued_retransmittable_frames_
540 // it's not sufficient to simply call
541 // queued_retransmittable_frames_->HasCryptoHandshake().
542 // TODO(rch): we should really make ReserializeAllFrames not be a special
543 // case!
545 // If any of the frames in the current packet are on the crypto stream
546 // then they contain handshake messagses, and we should pad them.
547 bool is_handshake = false;
548 for (const QuicFrame& frame : queued_frames_) {
549 if (frame.type == STREAM_FRAME &&
550 frame.stream_frame->stream_id == kCryptoStreamId) {
551 is_handshake = true;
552 break;
555 if (!is_handshake) {
556 return;
559 QuicPaddingFrame padding;
560 bool success = AddFrame(QuicFrame(&padding), false);
561 DCHECK(success);
564 } // namespace net