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
13using base::StringPiece;
14using std::make_pair;
15using std::max;
16using std::min;
17using std::pair;
18using std::vector;
19
20namespace 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.
25class 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
57QuicPacketCreator::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
73QuicPacketCreator::~QuicPacketCreator() {
74}
75
76void 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
84bool 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
90void 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.
102void 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
111void 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
128bool QuicPacketCreator::HasRoomForStreamFrame(QuicStreamId id,
129                                              QuicStreamOffset offset) const {
130  return BytesFree() >
131      QuicFramer::GetMinStreamFrameSize(framer_->version(), id, offset, true);
132}
133
134// static
135size_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
147size_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
207size_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
224SerializedPacket 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
250SerializedPacket 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
268bool QuicPacketCreator::HasPendingFrames() {
269  return !queued_frames_.empty();
270}
271
272size_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
291size_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
308bool QuicPacketCreator::AddSavedFrame(const QuicFrame& frame) {
309  return AddFrame(frame, true);
310}
311
312SerializedPacket 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
349SerializedPacket 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
370SerializedPacket QuicPacketCreator::SerializeConnectionClose(
371    QuicConnectionCloseFrame* close_frame) {
372  QuicFrames frames;
373  frames.push_back(QuicFrame(close_frame));
374  return SerializeAllFrames(frames);
375}
376
377QuicEncryptedPacket* 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
392void 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
416bool QuicPacketCreator::ShouldRetransmit(const QuicFrame& frame) {
417  return frame.type != ACK_FRAME && frame.type != CONGESTION_FEEDBACK_FRAME &&
418      frame.type != PADDING_FRAME;
419}
420
421bool 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
454void 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