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