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