net/quic/quic_packet_creator.cc

   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 (queued_retransmittable_frames_.get() == NULL) {
 507     return;
 508   }
 509   if (!queued_retransmittable_frames_->HasCryptoHandshake()) {
 510     return;
 511   }
 512   if (BytesFree() == 0) {
 513     // Don't pad full packets.
 514     return;
 515   }
 516   QuicPaddingFrame padding;
 517   bool success = AddFrame(QuicFrame(&padding), false);
 518   DCHECK(success);
 519 }
 520
 521 }  // namespace net