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