Implement keycode text conversion functions for Ozone.
[chromium-blink-merge.git] / net / quic / quic_packet_creator.cc
blob9deb614f13068fe0804f85b56f1e2cb9c8faf96c
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 <algorithm>
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;
18 using std::make_pair;
19 using std::max;
20 using std::min;
21 using std::pair;
22 using std::vector;
24 namespace net {
26 namespace {
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;
33 } // namespace
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 {
39 public:
40 // random: Source of entropy. Not owned.
41 explicit QuicRandomBoolSource(QuicRandom* random)
42 : random_(random),
43 bit_bucket_(0),
44 bit_mask_(0) {}
46 ~QuicRandomBoolSource() {}
48 // Returns the next random bit from the bucket.
49 bool RandBool() {
50 if (bit_mask_ == 0) {
51 bit_bucket_ = random_->RandUint64();
52 bit_mask_ = 1;
54 bool result = ((bit_bucket_ & bit_mask_) != 0);
55 bit_mask_ <<= 1;
56 return result;
59 private:
60 // Source of entropy.
61 QuicRandom* random_;
62 // Stored random bits.
63 uint64 bit_bucket_;
64 // The next available bit has "1" in the mask. Zero means empty bucket.
65 uint64 bit_mask_;
67 DISALLOW_COPY_AND_ASSIGN(QuicRandomBoolSource);
70 QuicPacketCreator::QuicPacketCreator(QuicConnectionId connection_id,
71 QuicFramer* framer,
72 QuicRandom* random_generator)
73 : connection_id_(connection_id),
74 encryption_level_(ENCRYPTION_NONE),
75 framer_(framer),
76 random_bool_source_(new QuicRandomBoolSource(random_generator)),
77 sequence_number_(0),
78 should_fec_protect_(false),
79 fec_group_number_(0),
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_),
85 packet_size_(0) {
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 &&
123 (force_close ||
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.";
134 return;
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.";
143 return;
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.";
152 return;
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.
171 return IN_FEC_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());
188 return IN_FEC_GROUP;
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.
222 return BytesFree() >
223 QuicFramer::GetMinStreamFrameSize(id, offset, true,
224 should_fec_protect_ ? IN_FEC_GROUP :
225 NOT_IN_FEC_GROUP);
228 // static
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,
244 bool fin,
245 QuicFrame* frame) {
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);
257 if (data.Empty()) {
258 LOG_IF(DFATAL, !fin)
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));
262 return 0;
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.
271 IOVector frame_data;
272 frame_data.AppendIovecAtMostBytes(data.iovec(), data.Size(),
273 bytes_consumed);
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,
282 char* buffer,
283 size_t buffer_len) {
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,
310 char* buffer,
311 size_t buffer_len) {
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);
317 DCHECK(success);
319 SerializedPacket packet = SerializePacket(buffer, buffer_len);
320 DCHECK(packet.retransmittable_frames == nullptr);
321 return packet;
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_) {
336 return 0;
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()) {
353 return packet_size_;
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);
362 return packet_size_;
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);
379 MaybeAddPadding();
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) {
395 packet.reset(
396 framer_->BuildDataPacket(header, queued_frames_, buffer, packet_size_));
397 } else {
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_;
418 return NoPacket();
421 packet_size_ = 0;
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,
430 size_t buffer_len) {
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?
435 return NoPacket();
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);
445 packet_size_ = 0;
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_;
455 return NoPacket();
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;
462 return serialized;
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);
475 DCHECK(encrypted);
476 DCHECK_GE(max_packet_length_, encrypted->length());
477 return encrypted;
480 SerializedPacket QuicPacketCreator::NoPacket() {
481 return SerializedPacket(0, PACKET_1BYTE_SEQUENCE_NUMBER, nullptr, 0, nullptr);
484 void QuicPacketCreator::FillPacketHeader(QuicFecGroupNumber fec_group,
485 bool fec_flag,
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) {
501 case ACK_FRAME:
502 case PADDING_FRAME:
503 case STOP_WAITING_FRAME:
504 return false;
505 default:
506 return true;
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) {
519 return false;
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));
532 } else {
533 queued_frames_.push_back(
534 queued_retransmittable_frames_->AddNonStreamFrame(frame));
536 } else {
537 queued_frames_.push_back(frame);
539 return true;
542 void QuicPacketCreator::MaybeAddPadding() {
543 if (BytesFree() == 0) {
544 // Don't pad full packets.
545 return;
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
552 // case!
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) {
560 is_handshake = true;
561 break;
564 if (!is_handshake) {
565 return;
568 QuicPaddingFrame padding;
569 bool success = AddFrame(QuicFrame(&padding), false);
570 DCHECK(success);
573 } // namespace net