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.
5 #include "net/quic/quic_packet_creator.h"
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"
14 using base::StringPiece;
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 {
28 // random: Source of entropy. Not owned.
29 explicit QuicRandomBoolSource(QuicRandom* random)
34 ~QuicRandomBoolSource() {}
36 // Returns the next random bit from the bucket.
39 bit_bucket_ = random_->RandUint64();
42 bool result = ((bit_bucket_ & bit_mask_) != 0);
50 // Stored random bits.
52 // The next available bit has "1" in the mask. Zero means empty bucket.
55 DISALLOW_COPY_AND_ASSIGN(QuicRandomBoolSource);
58 QuicPacketCreator::QuicPacketCreator(QuicGuid guid,
60 QuicRandom* random_generator,
64 random_bool_source_(new QuicRandomBoolSource(random_generator)),
67 is_server_(is_server),
68 send_version_in_packet_(!is_server),
69 sequence_number_length_(options_.send_sequence_number_length),
71 framer_->set_fec_builder(this);
74 QuicPacketCreator::~QuicPacketCreator() {
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);
85 bool QuicPacketCreator::ShouldSendFec(bool force_close) const {
86 return fec_group_.get() != NULL && fec_group_->NumReceivedPackets() > 0 &&
88 fec_group_->NumReceivedPackets() >= options_.max_packets_per_fec_group);
91 void QuicPacketCreator::MaybeStartFEC() {
92 // Don't send FEC until QUIC_VERSION_15.
93 if (framer_->version() > QUIC_VERSION_14 &&
94 options_.max_packets_per_fec_group > 0 && fec_group_.get() == NULL) {
95 DCHECK(queued_frames_.empty());
96 // Set the fec group number to the sequence number of the next packet.
97 fec_group_number_ = sequence_number() + 1;
98 fec_group_.reset(new QuicFecGroup());
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;
114 void QuicPacketCreator::UpdateSequenceNumberLength(
115 QuicPacketSequenceNumber least_packet_awaited_by_peer,
116 QuicByteCount bytes_per_second) {
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 =
124 bytes_per_second / options_.max_packet_length;
125 const uint64 delta = max(current_delta, congestion_window);
127 options_.send_sequence_number_length =
128 QuicFramer::GetMinSequenceNumberLength(delta * 4);
131 bool QuicPacketCreator::HasRoomForStreamFrame(QuicStreamId id,
132 QuicStreamOffset offset) const {
134 QuicFramer::GetMinStreamFrameSize(framer_->version(), id, offset, true);
138 size_t QuicPacketCreator::StreamFramePacketOverhead(
140 QuicGuidLength guid_length,
141 bool include_version,
142 QuicSequenceNumberLength sequence_number_length,
143 InFecGroup is_in_fec_group) {
144 return GetPacketHeaderSize(guid_length, include_version,
145 sequence_number_length, is_in_fec_group) +
146 // Assumes this is a stream with a single lone packet.
147 QuicFramer::GetMinStreamFrameSize(version, 1u, 0u, true);
150 size_t QuicPacketCreator::CreateStreamFrame(QuicStreamId id,
151 const IOVector& data,
152 QuicStreamOffset offset,
155 DCHECK_GT(options_.max_packet_length,
156 StreamFramePacketOverhead(
157 framer_->version(), PACKET_8BYTE_GUID, kIncludeVersion,
158 PACKET_6BYTE_SEQUENCE_NUMBER, IN_FEC_GROUP));
159 if (!HasRoomForStreamFrame(id, offset)) {
160 LOG(DFATAL) << "No room for Stream frame, BytesFree: " << BytesFree()
161 << " MinStreamFrameSize: "
162 << QuicFramer::GetMinStreamFrameSize(
163 framer_->version(), id, offset, true);
168 LOG(DFATAL) << "Creating a stream frame with no data or fin.";
170 // Create a new packet for the fin, if necessary.
171 *frame = QuicFrame(new QuicStreamFrame(id, true, offset, data));
175 const size_t free_bytes = BytesFree();
176 size_t bytes_consumed = 0;
177 const size_t data_size = data.TotalBufferSize();
179 // When a STREAM frame is the last frame in a packet, it consumes two fewer
180 // bytes of framing overhead.
181 // Anytime more data is available than fits in with the extra two bytes,
182 // the frame will be the last, and up to two extra bytes are consumed.
183 // TODO(ianswett): If QUIC pads, the 1 byte PADDING frame does not fit when
184 // 1 byte is available, because then the STREAM frame isn't the last.
186 // The minimum frame size(0 bytes of data) if it's not the last frame.
187 size_t min_frame_size = QuicFramer::GetMinStreamFrameSize(
188 framer_->version(), id, offset, false);
189 // Check if it's the last frame in the packet.
190 if (data_size + min_frame_size > free_bytes) {
191 // The minimum frame size(0 bytes of data) if it is the last frame.
192 size_t min_last_frame_size = QuicFramer::GetMinStreamFrameSize(
193 framer_->version(), id, offset, true);
195 min<size_t>(free_bytes - min_last_frame_size, data_size);
197 DCHECK_LT(data_size, BytesFree());
198 bytes_consumed = data_size;
201 bool set_fin = fin && bytes_consumed == data_size; // Last frame.
203 frame_data.AppendIovecAtMostBytes(data.iovec(), data.Size(),
205 DCHECK_EQ(frame_data.TotalBufferSize(), bytes_consumed);
206 *frame = QuicFrame(new QuicStreamFrame(id, set_fin, offset, frame_data));
207 return bytes_consumed;
210 size_t QuicPacketCreator::CreateStreamFrameWithNotifier(
212 const IOVector& data,
213 QuicStreamOffset offset,
215 QuicAckNotifier* notifier,
217 size_t bytes_consumed = CreateStreamFrame(id, data, offset, fin, frame);
219 // The frame keeps track of the QuicAckNotifier until it is serialized into
220 // a packet. At that point the notifier is informed of the sequence number
221 // of the packet that this frame was eventually sent in.
222 frame->stream_frame->notifier = notifier;
224 return bytes_consumed;
227 SerializedPacket QuicPacketCreator::ReserializeAllFrames(
228 const QuicFrames& frames,
229 QuicSequenceNumberLength original_length) {
230 const QuicSequenceNumberLength start_length = sequence_number_length_;
231 const QuicSequenceNumberLength start_options_length =
232 options_.send_sequence_number_length;
233 const QuicFecGroupNumber start_fec_group = fec_group_number_;
234 const size_t start_max_packets_per_fec_group =
235 options_.max_packets_per_fec_group;
237 // Temporarily set the sequence number length and disable FEC.
238 sequence_number_length_ = original_length;
239 options_.send_sequence_number_length = original_length;
240 fec_group_number_ = 0;
241 options_.max_packets_per_fec_group = 0;
243 // Serialize the packet and restore the fec and sequence number length state.
244 SerializedPacket serialized_packet = SerializeAllFrames(frames);
245 sequence_number_length_ = start_length;
246 options_.send_sequence_number_length = start_options_length;
247 fec_group_number_ = start_fec_group;
248 options_.max_packets_per_fec_group = start_max_packets_per_fec_group;
250 return serialized_packet;
253 SerializedPacket QuicPacketCreator::SerializeAllFrames(
254 const QuicFrames& frames) {
255 // TODO(satyamshekhar): Verify that this DCHECK won't fail. What about queued
256 // frames from SendStreamData()[send_stream_should_flush_ == false &&
257 // data.empty() == true] and retransmit due to RTO.
258 DCHECK_EQ(0u, queued_frames_.size());
259 if (frames.empty()) {
260 LOG(DFATAL) << "Attempt to serialize empty packet";
262 for (size_t i = 0; i < frames.size(); ++i) {
263 bool success = AddFrame(frames[i], false);
266 SerializedPacket packet = SerializePacket();
267 DCHECK(packet.retransmittable_frames == NULL);
271 bool QuicPacketCreator::HasPendingFrames() {
272 return !queued_frames_.empty();
275 size_t QuicPacketCreator::BytesFree() const {
276 const size_t max_plaintext_size =
277 framer_->GetMaxPlaintextSize(options_.max_packet_length);
278 DCHECK_GE(max_plaintext_size, PacketSize());
280 // If the last frame in the packet is a stream frame, then it can be
281 // two bytes smaller than if it were not the last. So this means that
282 // there are two fewer bytes available to the next frame in this case.
283 bool has_trailing_stream_frame =
284 !queued_frames_.empty() && queued_frames_.back().type == STREAM_FRAME;
285 size_t expanded_packet_size = PacketSize() +
286 (has_trailing_stream_frame ? kQuicStreamPayloadLengthSize : 0);
288 if (expanded_packet_size >= max_plaintext_size) {
291 return max_plaintext_size - expanded_packet_size;
294 size_t QuicPacketCreator::PacketSize() const {
295 if (queued_frames_.empty()) {
296 // Only adjust the sequence number length when the FEC group is not open,
297 // to ensure no packets in a group are too large.
298 if (fec_group_.get() == NULL ||
299 fec_group_->NumReceivedPackets() == 0) {
300 sequence_number_length_ = options_.send_sequence_number_length;
302 packet_size_ = GetPacketHeaderSize(options_.send_guid_length,
303 send_version_in_packet_,
304 sequence_number_length_,
305 options_.max_packets_per_fec_group == 0 ?
306 NOT_IN_FEC_GROUP : IN_FEC_GROUP);
311 bool QuicPacketCreator::AddSavedFrame(const QuicFrame& frame) {
312 return AddFrame(frame, true);
315 SerializedPacket QuicPacketCreator::SerializePacket() {
316 if (queued_frames_.empty()) {
317 LOG(DFATAL) << "Attempt to serialize empty packet";
319 QuicPacketHeader header;
320 FillPacketHeader(fec_group_number_, false, &header);
324 size_t max_plaintext_size =
325 framer_->GetMaxPlaintextSize(options_.max_packet_length);
326 DCHECK_GE(max_plaintext_size, packet_size_);
327 // ACK and CONNECTION_CLOSE Frames will be truncated only if they're
328 // the first frame in the packet. If truncation is to occur, then
329 // GetSerializedFrameLength will have returned all bytes free.
330 bool possibly_truncated =
331 packet_size_ != max_plaintext_size ||
332 queued_frames_.size() != 1 ||
333 (queued_frames_.back().type == ACK_FRAME ||
334 queued_frames_.back().type == CONNECTION_CLOSE_FRAME);
335 SerializedPacket serialized =
336 framer_->BuildDataPacket(header, queued_frames_, packet_size_);
337 if (!serialized.packet) {
338 LOG(DFATAL) << "Failed to serialize " << queued_frames_.size()
341 // Because of possible truncation, we can't be confident that our
342 // packet size calculation worked correctly.
343 if (!possibly_truncated)
344 DCHECK_EQ(packet_size_, serialized.packet->length());
347 queued_frames_.clear();
348 serialized.retransmittable_frames = queued_retransmittable_frames_.release();
352 SerializedPacket QuicPacketCreator::SerializeFec() {
353 DCHECK_LT(0u, fec_group_->NumReceivedPackets());
354 DCHECK_EQ(0u, queued_frames_.size());
355 QuicPacketHeader header;
356 FillPacketHeader(fec_group_number_, true, &header);
357 QuicFecData fec_data;
358 fec_data.fec_group = fec_group_->min_protected_packet();
359 fec_data.redundancy = fec_group_->payload_parity();
360 SerializedPacket serialized = framer_->BuildFecPacket(header, fec_data);
361 fec_group_.reset(NULL);
362 fec_group_number_ = 0;
364 if (!serialized.packet) {
365 LOG(DFATAL) << "Failed to serialize fec packet for group:"
366 << fec_data.fec_group;
368 DCHECK_GE(options_.max_packet_length, serialized.packet->length());
372 SerializedPacket QuicPacketCreator::SerializeConnectionClose(
373 QuicConnectionCloseFrame* close_frame) {
375 frames.push_back(QuicFrame(close_frame));
376 return SerializeAllFrames(frames);
379 QuicEncryptedPacket* QuicPacketCreator::SerializeVersionNegotiationPacket(
380 const QuicVersionVector& supported_versions) {
382 QuicPacketPublicHeader header;
384 header.reset_flag = false;
385 header.version_flag = true;
386 header.versions = supported_versions;
387 QuicEncryptedPacket* encrypted =
388 framer_->BuildVersionNegotiationPacket(header, supported_versions);
390 DCHECK_GE(options_.max_packet_length, encrypted->length());
394 void QuicPacketCreator::FillPacketHeader(QuicFecGroupNumber fec_group,
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 header->entropy_flag = random_bool_source_->RandBool();
404 header->is_in_fec_group = fec_group == 0 ? NOT_IN_FEC_GROUP : IN_FEC_GROUP;
405 header->fec_group = fec_group;
408 bool QuicPacketCreator::ShouldRetransmit(const QuicFrame& frame) {
409 return frame.type != ACK_FRAME && frame.type != CONGESTION_FEEDBACK_FRAME &&
410 frame.type != PADDING_FRAME;
413 bool QuicPacketCreator::AddFrame(const QuicFrame& frame,
414 bool save_retransmittable_frames) {
415 DVLOG(1) << "Adding frame: " << frame;
416 size_t frame_len = framer_->GetSerializedFrameLength(
417 frame, BytesFree(), queued_frames_.empty(), true,
418 options()->send_sequence_number_length);
419 if (frame_len == 0) {
422 DCHECK_LT(0u, packet_size_);
424 packet_size_ += frame_len;
425 // If the last frame in the packet was a stream frame, then once we add the
426 // new frame it's serialization will be two bytes larger.
427 if (!queued_frames_.empty() && queued_frames_.back().type == STREAM_FRAME) {
428 packet_size_ += kQuicStreamPayloadLengthSize;
430 if (save_retransmittable_frames && ShouldRetransmit(frame)) {
431 if (queued_retransmittable_frames_.get() == NULL) {
432 queued_retransmittable_frames_.reset(new RetransmittableFrames());
434 if (frame.type == STREAM_FRAME) {
435 queued_frames_.push_back(
436 queued_retransmittable_frames_->AddStreamFrame(frame.stream_frame));
438 queued_frames_.push_back(
439 queued_retransmittable_frames_->AddNonStreamFrame(frame));
442 queued_frames_.push_back(frame);
447 void QuicPacketCreator::MaybeAddPadding() {
448 if (BytesFree() == 0) {
449 // Don't pad full packets.
453 // If any of the frames in the current packet are on the crypto stream
454 // then they contain handshake messagses, and we should pad them.
455 bool is_handshake = false;
456 for (size_t i = 0; i < queued_frames_.size(); ++i) {
457 if (queued_frames_[i].type == STREAM_FRAME &&
458 queued_frames_[i].stream_frame->stream_id == kCryptoStreamId) {
467 QuicPaddingFrame padding;
468 bool success = AddFrame(QuicFrame(&padding), false);