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