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. 4 5 #include "net/quic/quic_packet_creator.h" 6 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" 13 14 using base::StringPiece; 15 using std::make_pair; 16 using std::max; 17 using std::min; 18 using std::pair; 19 using std::vector; 20 21 namespace net { 22 23 namespace { 24 25 // Default max packets in an FEC group. 26 static const size_t kDefaultMaxPacketsPerFecGroup = 10; 27 // Lowest max packets in an FEC group. 28 static const size_t kLowestMaxPacketsPerFecGroup = 2; 29 30 } // namespace 31 32 // A QuicRandom wrapper that gets a bucket of entropy and distributes it 33 // bit-by-bit. Replenishes the bucket as needed. Not thread-safe. Expose this 34 // class if single bit randomness is needed elsewhere. 35 class QuicRandomBoolSource { 36 public: 37 // random: Source of entropy. Not owned. 38 explicit QuicRandomBoolSource(QuicRandom* random) 39 : random_(random), 40 bit_bucket_(0), 41 bit_mask_(0) {} 42 43 ~QuicRandomBoolSource() {} 44 45 // Returns the next random bit from the bucket. 46 bool RandBool() { 47 if (bit_mask_ == 0) { 48 bit_bucket_ = random_->RandUint64(); 49 bit_mask_ = 1; 50 } 51 bool result = ((bit_bucket_ & bit_mask_) != 0); 52 bit_mask_ <<= 1; 53 return result; 54 } 55 56 private: 57 // Source of entropy. 58 QuicRandom* random_; 59 // Stored random bits. 60 uint64 bit_bucket_; 61 // The next available bit has "1" in the mask. Zero means empty bucket. 62 uint64 bit_mask_; 63 64 DISALLOW_COPY_AND_ASSIGN(QuicRandomBoolSource); 65 }; 66 67 QuicPacketCreator::QuicPacketCreator(QuicConnectionId connection_id, 68 QuicFramer* framer, 69 QuicRandom* random_generator) 70 : connection_id_(connection_id), 71 encryption_level_(ENCRYPTION_NONE), 72 framer_(framer), 73 random_bool_source_(new QuicRandomBoolSource(random_generator)), 74 sequence_number_(0), 75 should_fec_protect_(false), 76 fec_group_number_(0), 77 send_version_in_packet_(!framer->is_server()), 78 max_packet_length_(kDefaultMaxPacketSize), 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 framer_->set_fec_builder(this); 85 } 86 87 QuicPacketCreator::~QuicPacketCreator() { 88 } 89 90 void QuicPacketCreator::OnBuiltFecProtectedPayload( 91 const QuicPacketHeader& header, StringPiece payload) { 92 if (fec_group_.get()) { 93 DCHECK_NE(0u, header.fec_group); 94 fec_group_->Update(encryption_level_, header, payload); 95 } 96 } 97 98 void QuicPacketCreator::set_max_packets_per_fec_group( 99 size_t max_packets_per_fec_group) { 100 max_packets_per_fec_group_ = max(kLowestMaxPacketsPerFecGroup, 101 max_packets_per_fec_group); 102 DCHECK_LT(0u, max_packets_per_fec_group_); 103 } 104 105 bool QuicPacketCreator::ShouldSendFec(bool force_close) const { 106 DCHECK(!HasPendingFrames()); 107 return fec_group_.get() != NULL && fec_group_->NumReceivedPackets() > 0 && 108 (force_close || fec_group_->NumReceivedPackets() >= 109 max_packets_per_fec_group_); 110 } 111 112 bool QuicPacketCreator::IsFecGroupOpen() const { 113 return fec_group_.get() != NULL; 114 } 115 116 void QuicPacketCreator::StartFecProtectingPackets() { 117 if (!IsFecEnabled()) { 118 LOG(DFATAL) << "Cannot start FEC protection when FEC is not enabled."; 119 return; 120 } 121 // TODO(jri): This currently requires that the generator flush out any 122 // pending frames when FEC protection is turned on. If current packet can be 123 // converted to an FEC protected packet, do it. This will require the 124 // generator to check if the resulting expansion still allows the incoming 125 // frame to be added to the packet. 126 if (HasPendingFrames()) { 127 LOG(DFATAL) << "Cannot start FEC protection with pending frames."; 128 return; 129 } 130 DCHECK(!should_fec_protect_); 131 should_fec_protect_ = true; 132 } 133 134 void QuicPacketCreator::StopFecProtectingPackets() { 135 if (fec_group_.get() != NULL) { 136 LOG(DFATAL) << "Cannot stop FEC protection with open FEC group."; 137 return; 138 } 139 DCHECK(should_fec_protect_); 140 should_fec_protect_ = false; 141 fec_group_number_ = 0; 142 } 143 144 bool QuicPacketCreator::IsFecProtected() const { 145 return should_fec_protect_; 146 } 147 148 bool QuicPacketCreator::IsFecEnabled() const { 149 return max_packets_per_fec_group_ > 0; 150 } 151 152 InFecGroup QuicPacketCreator::MaybeUpdateLengthsAndStartFec() { 153 if (fec_group_.get() != NULL) { 154 // Don't update any lengths when an FEC group is open, to ensure same 155 // packet header size in all packets within a group. 156 return IN_FEC_GROUP; 157 } 158 if (!queued_frames_.empty()) { 159 // Don't change creator state if there are frames queued. 160 return fec_group_.get() == NULL ? NOT_IN_FEC_GROUP : IN_FEC_GROUP; 161 } 162 163 // Update sequence number length only on packet and FEC group boundaries. 164 sequence_number_length_ = next_sequence_number_length_; 165 166 if (!should_fec_protect_) { 167 return NOT_IN_FEC_GROUP; 168 } 169 // Start a new FEC group since protection is on. Set the fec group number to 170 // the sequence number of the next packet. 171 fec_group_number_ = sequence_number() + 1; 172 fec_group_.reset(new QuicFecGroup()); 173 return IN_FEC_GROUP; 174 } 175 176 // Stops serializing version of the protocol in packets sent after this call. 177 // A packet that is already open might send kQuicVersionSize bytes less than the 178 // maximum packet size if we stop sending version before it is serialized. 179 void QuicPacketCreator::StopSendingVersion() { 180 DCHECK(send_version_in_packet_); 181 send_version_in_packet_ = false; 182 if (packet_size_ > 0) { 183 DCHECK_LT(kQuicVersionSize, packet_size_); 184 packet_size_ -= kQuicVersionSize; 185 } 186 } 187 188 void QuicPacketCreator::UpdateSequenceNumberLength( 189 QuicPacketSequenceNumber least_packet_awaited_by_peer, 190 QuicByteCount congestion_window) { 191 DCHECK_LE(least_packet_awaited_by_peer, sequence_number_ + 1); 192 // Since the packet creator will not change sequence number length mid FEC 193 // group, include the size of an FEC group to be safe. 194 const QuicPacketSequenceNumber current_delta = 195 max_packets_per_fec_group_ + sequence_number_ + 1 196 - least_packet_awaited_by_peer; 197 const uint64 congestion_window_packets = 198 congestion_window / max_packet_length_; 199 const uint64 delta = max(current_delta, congestion_window_packets); 200 next_sequence_number_length_ = 201 QuicFramer::GetMinSequenceNumberLength(delta * 4); 202 } 203 204 bool QuicPacketCreator::HasRoomForStreamFrame(QuicStreamId id, 205 QuicStreamOffset offset) const { 206 // TODO(jri): This is a simple safe decision for now, but make 207 // is_in_fec_group a parameter. Same as with all public methods in 208 // QuicPacketCreator. 209 return BytesFree() > 210 QuicFramer::GetMinStreamFrameSize(id, offset, true, 211 should_fec_protect_ ? IN_FEC_GROUP : 212 NOT_IN_FEC_GROUP); 213 } 214 215 // static 216 size_t QuicPacketCreator::StreamFramePacketOverhead( 217 QuicConnectionIdLength connection_id_length, 218 bool include_version, 219 QuicSequenceNumberLength sequence_number_length, 220 QuicStreamOffset offset, 221 InFecGroup is_in_fec_group) { 222 return GetPacketHeaderSize(connection_id_length, include_version, 223 sequence_number_length, is_in_fec_group) + 224 // Assumes this is a stream with a single lone packet. 225 QuicFramer::GetMinStreamFrameSize(1u, offset, true, is_in_fec_group); 226 } 227 228 size_t QuicPacketCreator::CreateStreamFrame(QuicStreamId id, 229 const IOVector& data, 230 QuicStreamOffset offset, 231 bool fin, 232 QuicFrame* frame) { 233 DCHECK_GT(max_packet_length_, StreamFramePacketOverhead( 234 PACKET_8BYTE_CONNECTION_ID, kIncludeVersion, 235 PACKET_6BYTE_SEQUENCE_NUMBER, offset, IN_FEC_GROUP)); 236 237 InFecGroup is_in_fec_group = MaybeUpdateLengthsAndStartFec(); 238 239 LOG_IF(DFATAL, !HasRoomForStreamFrame(id, offset)) 240 << "No room for Stream frame, BytesFree: " << BytesFree() 241 << " MinStreamFrameSize: " 242 << QuicFramer::GetMinStreamFrameSize(id, offset, true, is_in_fec_group); 243 244 if (data.Empty()) { 245 LOG_IF(DFATAL, !fin) 246 << "Creating a stream frame with no data or fin."; 247 // Create a new packet for the fin, if necessary. 248 *frame = QuicFrame(new QuicStreamFrame(id, true, offset, data)); 249 return 0; 250 } 251 252 const size_t data_size = data.TotalBufferSize(); 253 size_t min_frame_size = QuicFramer::GetMinStreamFrameSize( 254 id, offset, /* last_frame_in_packet= */ true, is_in_fec_group); 255 size_t bytes_consumed = min<size_t>(BytesFree() - min_frame_size, data_size); 256 257 bool set_fin = fin && bytes_consumed == data_size; // Last frame. 258 IOVector frame_data; 259 frame_data.AppendIovecAtMostBytes(data.iovec(), data.Size(), 260 bytes_consumed); 261 DCHECK_EQ(frame_data.TotalBufferSize(), bytes_consumed); 262 *frame = QuicFrame(new QuicStreamFrame(id, set_fin, offset, frame_data)); 263 return bytes_consumed; 264 } 265 266 size_t QuicPacketCreator::CreateStreamFrameWithNotifier( 267 QuicStreamId id, 268 const IOVector& data, 269 QuicStreamOffset offset, 270 bool fin, 271 QuicAckNotifier* notifier, 272 QuicFrame* frame) { 273 size_t bytes_consumed = CreateStreamFrame(id, data, offset, fin, frame); 274 275 // The frame keeps track of the QuicAckNotifier until it is serialized into 276 // a packet. At that point the notifier is informed of the sequence number 277 // of the packet that this frame was eventually sent in. 278 frame->stream_frame->notifier = notifier; 279 280 return bytes_consumed; 281 } 282 283 SerializedPacket QuicPacketCreator::ReserializeAllFrames( 284 const QuicFrames& frames, 285 QuicSequenceNumberLength original_length) { 286 DCHECK(fec_group_.get() == NULL); 287 const QuicSequenceNumberLength saved_length = sequence_number_length_; 288 const QuicSequenceNumberLength saved_next_length = 289 next_sequence_number_length_; 290 const bool saved_should_fec_protect = should_fec_protect_; 291 292 // Temporarily set the sequence number length and stop FEC protection. 293 sequence_number_length_ = original_length; 294 next_sequence_number_length_ = original_length; 295 should_fec_protect_ = false; 296 297 // Serialize the packet and restore the FEC and sequence number length state. 298 SerializedPacket serialized_packet = SerializeAllFrames(frames); 299 sequence_number_length_ = saved_length; 300 next_sequence_number_length_ = saved_next_length; 301 should_fec_protect_ = saved_should_fec_protect; 302 303 return serialized_packet; 304 } 305 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 (size_t i = 0; i < frames.size(); ++i) { 315 bool success = AddFrame(frames[i], false); 316 DCHECK(success); 317 } 318 SerializedPacket packet = SerializePacket(); 319 DCHECK(packet.retransmittable_frames == NULL); 320 return packet; 321 } 322 323 bool QuicPacketCreator::HasPendingFrames() const { 324 return !queued_frames_.empty(); 325 } 326 327 bool QuicPacketCreator::HasPendingRetransmittableFrames() const { 328 return queued_retransmittable_frames_.get() != NULL && 329 !queued_retransmittable_frames_->frames().empty(); 330 } 331 332 size_t QuicPacketCreator::ExpansionOnNewFrame() const { 333 // If packet is FEC protected, there's no expansion. 334 if (should_fec_protect_) { 335 return 0; 336 } 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; 342 } 343 344 size_t QuicPacketCreator::BytesFree() const { 345 const size_t max_plaintext_size = 346 framer_->GetMaxPlaintextSize(max_packet_length_); 347 DCHECK_GE(max_plaintext_size, PacketSize()); 348 return max_plaintext_size - min(max_plaintext_size, PacketSize() 349 + ExpansionOnNewFrame()); 350 } 351 352 size_t QuicPacketCreator::PacketSize() const { 353 if (!queued_frames_.empty()) { 354 return packet_size_; 355 } 356 if (fec_group_.get() == NULL) { 357 // Update sequence number length on packet and FEC boundary. 358 sequence_number_length_ = next_sequence_number_length_; 359 } 360 packet_size_ = GetPacketHeaderSize( 361 connection_id_length_, send_version_in_packet_, sequence_number_length_, 362 should_fec_protect_ ? IN_FEC_GROUP : NOT_IN_FEC_GROUP); 363 return packet_size_; 364 } 365 366 bool QuicPacketCreator::AddSavedFrame(const QuicFrame& frame) { 367 return AddFrame(frame, true); 368 } 369 370 SerializedPacket QuicPacketCreator::SerializePacket() { 371 LOG_IF(DFATAL, queued_frames_.empty()) 372 << "Attempt to serialize empty packet"; 373 DCHECK_GE(sequence_number_ + 1, fec_group_number_); 374 QuicPacketHeader header; 375 FillPacketHeader(should_fec_protect_ ? fec_group_number_ : 0, false, &header); 376 377 MaybeAddPadding(); 378 379 size_t max_plaintext_size = 380 framer_->GetMaxPlaintextSize(max_packet_length_); 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 SerializedPacket serialized = 390 framer_->BuildDataPacket(header, queued_frames_, packet_size_); 391 LOG_IF(DFATAL, !serialized.packet) 392 << "Failed to serialize " << queued_frames_.size() << " frames."; 393 // Because of possible truncation, we can't be confident that our 394 // packet size calculation worked correctly. 395 if (!possibly_truncated_by_length) { 396 DCHECK_EQ(packet_size_, serialized.packet->length()); 397 } 398 packet_size_ = 0; 399 queued_frames_.clear(); 400 serialized.retransmittable_frames = queued_retransmittable_frames_.release(); 401 return serialized; 402 } 403 404 SerializedPacket QuicPacketCreator::SerializeFec() { 405 if (fec_group_.get() == NULL || fec_group_->NumReceivedPackets() <= 0) { 406 LOG(DFATAL) << "SerializeFEC called but no group or zero packets in group."; 407 // TODO(jri): Make this a public method of framer? 408 SerializedPacket kNoPacket(0, PACKET_1BYTE_SEQUENCE_NUMBER, NULL, 0, NULL); 409 return kNoPacket; 410 } 411 DCHECK_EQ(0u, queued_frames_.size()); 412 QuicPacketHeader header; 413 FillPacketHeader(fec_group_number_, true, &header); 414 QuicFecData fec_data; 415 fec_data.fec_group = fec_group_->min_protected_packet(); 416 fec_data.redundancy = fec_group_->payload_parity(); 417 SerializedPacket serialized = framer_->BuildFecPacket(header, fec_data); 418 fec_group_.reset(NULL); 419 packet_size_ = 0; 420 LOG_IF(DFATAL, !serialized.packet) 421 << "Failed to serialize fec packet for group:" << fec_data.fec_group; 422 DCHECK_GE(max_packet_length_, serialized.packet->length()); 423 return serialized; 424 } 425 426 SerializedPacket QuicPacketCreator::SerializeConnectionClose( 427 QuicConnectionCloseFrame* close_frame) { 428 QuicFrames frames; 429 frames.push_back(QuicFrame(close_frame)); 430 return SerializeAllFrames(frames); 431 } 432 433 QuicEncryptedPacket* QuicPacketCreator::SerializeVersionNegotiationPacket( 434 const QuicVersionVector& supported_versions) { 435 DCHECK(framer_->is_server()); 436 QuicPacketPublicHeader header; 437 header.connection_id = connection_id_; 438 header.reset_flag = false; 439 header.version_flag = true; 440 header.versions = supported_versions; 441 QuicEncryptedPacket* encrypted = 442 framer_->BuildVersionNegotiationPacket(header, supported_versions); 443 DCHECK(encrypted); 444 DCHECK_GE(max_packet_length_, encrypted->length()); 445 return encrypted; 446 } 447 448 void QuicPacketCreator::FillPacketHeader(QuicFecGroupNumber fec_group, 449 bool fec_flag, 450 QuicPacketHeader* header) { 451 header->public_header.connection_id = connection_id_; 452 header->public_header.reset_flag = false; 453 header->public_header.version_flag = send_version_in_packet_; 454 header->fec_flag = fec_flag; 455 header->packet_sequence_number = ++sequence_number_; 456 header->public_header.sequence_number_length = sequence_number_length_; 457 header->entropy_flag = random_bool_source_->RandBool(); 458 header->is_in_fec_group = fec_group == 0 ? NOT_IN_FEC_GROUP : IN_FEC_GROUP; 459 header->fec_group = fec_group; 460 } 461 462 bool QuicPacketCreator::ShouldRetransmit(const QuicFrame& frame) { 463 switch (frame.type) { 464 case ACK_FRAME: 465 case CONGESTION_FEEDBACK_FRAME: 466 case PADDING_FRAME: 467 case STOP_WAITING_FRAME: 468 return false; 469 default: 470 return true; 471 } 472 } 473 474 bool QuicPacketCreator::AddFrame(const QuicFrame& frame, 475 bool save_retransmittable_frames) { 476 DVLOG(1) << "Adding frame: " << frame; 477 InFecGroup is_in_fec_group = MaybeUpdateLengthsAndStartFec(); 478 479 size_t frame_len = framer_->GetSerializedFrameLength( 480 frame, BytesFree(), queued_frames_.empty(), true, is_in_fec_group, 481 sequence_number_length_); 482 if (frame_len == 0) { 483 return false; 484 } 485 DCHECK_LT(0u, packet_size_); 486 packet_size_ += ExpansionOnNewFrame() + frame_len; 487 488 if (save_retransmittable_frames && ShouldRetransmit(frame)) { 489 if (queued_retransmittable_frames_.get() == NULL) { 490 queued_retransmittable_frames_.reset(new RetransmittableFrames()); 491 } 492 if (frame.type == STREAM_FRAME) { 493 queued_frames_.push_back( 494 queued_retransmittable_frames_->AddStreamFrame(frame.stream_frame)); 495 } else { 496 queued_frames_.push_back( 497 queued_retransmittable_frames_->AddNonStreamFrame(frame)); 498 } 499 } else { 500 queued_frames_.push_back(frame); 501 } 502 return true; 503 } 504 505 void QuicPacketCreator::MaybeAddPadding() { 506 if (BytesFree() == 0) { 507 // Don't pad full packets. 508 return; 509 } 510 511 // Since ReserializeAllFrames does not populate queued_retransmittable_frames_ 512 // it's not sufficient to simply call 513 // queued_retransmittable_frames_->HasCryptoHandshake(). 514 // TODO(rch): we should really make ReserializeAllFrames not be a special 515 // case! 516 517 // If any of the frames in the current packet are on the crypto stream 518 // then they contain handshake messagses, and we should pad them. 519 bool is_handshake = false; 520 for (const QuicFrame& frame : queued_frames_) { 521 if (frame.type == STREAM_FRAME && 522 frame.stream_frame->stream_id == kCryptoStreamId) { 523 is_handshake = true; 524 break; 525 } 526 } 527 if (!is_handshake) { 528 return; 529 } 530 531 QuicPaddingFrame padding; 532 bool success = AddFrame(QuicFrame(&padding), false); 533 DCHECK(success); 534 } 535 536 } // namespace net 537