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