Change the wire format of the ack frame to include a compressed version

net/quic/quic_framer.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/quic/quic_framer.h"
 
 #include "base/containers/hash_tables.h"
 #include "base/stl_util.h"
 #include "net/quic/crypto/crypto_framer.h"
 #include "net/quic/crypto/crypto_handshake_message.h"
@@ skipping 114 matching lines @@
     case PACKET_FLAGS_2BYTE_SEQUENCE:
       return PACKET_2BYTE_SEQUENCE_NUMBER;
     case PACKET_FLAGS_1BYTE_SEQUENCE:
       return PACKET_1BYTE_SEQUENCE_NUMBER;
     default:
       LOG(DFATAL) << "Unreachable case statement.";
       return PACKET_6BYTE_SEQUENCE_NUMBER;
   }
 }
 
-bool CanTruncate(const QuicFrame& frame, size_t free_bytes) {
-  if ((frame.type == ACK_FRAME || frame.type == CONNECTION_CLOSE_FRAME) &&
-      free_bytes >=
-          QuicFramer::GetMinAckFrameSize(PACKET_6BYTE_SEQUENCE_NUMBER,
-                                         PACKET_6BYTE_SEQUENCE_NUMBER)) {
-    return true;
-  }
-  return false;
-}
-
 }  // namespace
 
 bool QuicFramerVisitorInterface::OnWindowUpdateFrame(
     const QuicWindowUpdateFrame& frame) {
   return true;
 }
 
 bool QuicFramerVisitorInterface::OnBlockedFrame(const QuicBlockedFrame& frame) {
   return true;
 }
 
 QuicFramer::QuicFramer(const QuicVersionVector& supported_versions,
                        QuicTime creation_time,
                        bool is_server)
     : visitor_(NULL),
       fec_builder_(NULL),
       entropy_calculator_(NULL),
       error_(QUIC_NO_ERROR),
       last_sequence_number_(0),
       last_serialized_connection_id_(0),
       supported_versions_(supported_versions),
       decrypter_level_(ENCRYPTION_NONE),
       alternative_decrypter_level_(ENCRYPTION_NONE),
       alternative_decrypter_latch_(false),
       is_server_(is_server),
       validate_flags_(true),
-      creation_time_(creation_time) {
+      creation_time_(creation_time),
+      last_timestamp_(QuicTime::Delta::Zero()) {
   DCHECK(!supported_versions.empty());
   quic_version_ = supported_versions_[0];
   decrypter_.reset(QuicDecrypter::Create(kNULL));
   encrypter_[ENCRYPTION_NONE].reset(
       QuicEncrypter::Create(kNULL));
 }
 
 QuicFramer::~QuicFramer() {}
 
 // static
@@ skipping 113 matching lines @@
                          sequence_number_length);
   if (frame_len <= free_bytes) {
     // Frame fits within packet. Note that acks may be truncated.
     return frame_len;
   }
   // Only truncate the first frame in a packet, so if subsequent ones go
   // over, stop including more frames.
   if (!first_frame) {
     return 0;
   }
-  if (CanTruncate(frame, free_bytes)) {
+  bool can_truncate = frame.type == ACK_FRAME &&
+      free_bytes >= GetMinAckFrameSize(PACKET_6BYTE_SEQUENCE_NUMBER,
+                                       PACKET_6BYTE_SEQUENCE_NUMBER);
+  if (can_truncate) {
     // Truncate the frame so the packet will not exceed kMaxPacketSize.
     // Note that we may not use every byte of the writer in this case.
     DVLOG(1) << "Truncating large frame, free bytes: " << free_bytes;
     return free_bytes;
   }
   if (!FLAGS_quic_allow_oversized_packets_for_test) {
     return 0;
   }
   LOG(DFATAL) << "Packet size too small to fit frame.";
   return frame_len;
@@ skipping 484 matching lines @@
     uint8 first_fec_protected_packet_offset =
         header.packet_sequence_number - header.fec_group;
     if (!writer->WriteBytes(&first_fec_protected_packet_offset, 1)) {
       return false;
     }
   }
 
   return true;
 }
 
+const QuicTime::Delta QuicFramer::CalculateTimestampFromWire(
+    uint32 time_delta_us) {
+  // The new time_delta might have wrapped to the next epoch, or it
+  // might have reverse wrapped to the previous epoch, or it might
+  // remain in the same epoch. Select the time closest to the previous
+  // time.
+  //
+  // epoch_delta is the delta between epochs. A delta is 4 bytes of
+  // microseconds.
+  const uint64 epoch_delta = GG_UINT64_C(1) << 32;
+  uint64 epoch = last_timestamp_.ToMicroseconds() & ~(epoch_delta - 1);
+  // Wrapping is safe here because a wrapped value will not be ClosestTo below.
+  uint64 prev_epoch = epoch - epoch_delta;
+  uint64 next_epoch = epoch + epoch_delta;
+
+  uint64 time = ClosestTo(last_timestamp_.ToMicroseconds(),
+                          epoch + time_delta_us,
+                          ClosestTo(last_timestamp_.ToMicroseconds(),
+                                    prev_epoch + time_delta_us,
+                                    next_epoch + time_delta_us));
+
+  return QuicTime::Delta::FromMicroseconds(time);
+}
+
 QuicPacketSequenceNumber QuicFramer::CalculatePacketSequenceNumberFromWire(
     QuicSequenceNumberLength sequence_number_length,
     QuicPacketSequenceNumber packet_sequence_number) const {
   // The new sequence number might have wrapped to the next epoch, or
   // it might have reverse wrapped to the previous epoch, or it might
   // remain in the same epoch.  Select the sequence number closest to the
   // next expected sequence number, the previous sequence number plus 1.
 
   // epoch_delta is the delta between epochs the sequence number was serialized
   // with, so the correct value is likely the same epoch as the last sequence
@@ skipping 283 matching lines @@
         if (!visitor_->OnAckFrame(frame)) {
           DVLOG(1) << "Visitor asked to stop further processing.";
           // Returning true since there was no parsing error.
           return true;
         }
         continue;
       }
 
       // Congestion Feedback Frame
       if (frame_type & kQuicFrameTypeCongestionFeedbackMask) {
+        if (quic_version_ > QUIC_VERSION_22) {
+          set_detailed_error("Congestion Feedback Frame has been deprecated.");
+          DLOG(WARNING) << "Congestion Feedback Frame has been deprecated.";
+        }
         QuicCongestionFeedbackFrame frame;
-        if (!ProcessQuicCongestionFeedbackFrame(&frame)) {
+        if (!ProcessCongestionFeedbackFrame(&frame)) {
           return RaiseError(QUIC_INVALID_CONGESTION_FEEDBACK_DATA);
         }
         if (!visitor_->OnCongestionFeedbackFrame(frame)) {
           DVLOG(1) << "Visitor asked to stop further processing.";
           // Returning true since there was no parsing error.
           return true;
         }
         continue;
       }
 
@@ skipping 201 matching lines @@
     return false;
   }
 
   if (delta_time_largest_observed_us == kUFloat16MaxValue) {
     ack_frame->delta_time_largest_observed = QuicTime::Delta::Infinite();
   } else {
     ack_frame->delta_time_largest_observed =
         QuicTime::Delta::FromMicroseconds(delta_time_largest_observed_us);
   }
 
+  if (!ProcessTimestampsInAckFrame(ack_frame)) {
+    return false;
+  }
+
   if (!has_nacks) {
     return true;
   }
 
   uint8 num_missing_ranges;
   if (!reader_->ReadBytes(&num_missing_ranges, 1)) {
     set_detailed_error("Unable to read num missing packet ranges.");
     return false;
   }
 
@@ skipping 33 matching lines @@
       set_detailed_error("Unable to read revived packet.");
       return false;
     }
 
     ack_frame->revived_packets.insert(revived_packet);
   }
 
   return true;
 }
 
+bool QuicFramer::ProcessTimestampsInAckFrame(QuicAckFrame* ack_frame) {
+  if (version() > QUIC_VERSION_22 && !ack_frame->is_truncated) {
+    uint8 num_received_packets;
+    if (!reader_->ReadBytes(&num_received_packets, 1)) {
+      set_detailed_error("Unable to read num received packets.");
+      return false;
+    }
+
+    if (num_received_packets > 0) {
+      uint8 delta_from_largest_observed;
+      if (!reader_->ReadBytes(&delta_from_largest_observed,
+                              PACKET_1BYTE_SEQUENCE_NUMBER)) {
+        set_detailed_error(
+            "Unable to read sequence delta in received packets.");
+        return false;
+      }
+      QuicPacketSequenceNumber seq_num = ack_frame->largest_observed -
+          delta_from_largest_observed;
+
+      // Time delta from the framer creation.
+      uint32 time_delta_us;
+      if (!reader_->ReadBytes(&time_delta_us, sizeof(time_delta_us))) {
+        set_detailed_error("Unable to read time delta in received packets.");
+        return false;
+      }
+
+      last_timestamp_ = CalculateTimestampFromWire(time_delta_us);
+
+      ack_frame->received_packet_times.push_back(
+          make_pair(seq_num, creation_time_.Add(last_timestamp_)));
+
+      for (uint8 i = 1; i < num_received_packets; ++i) {
+        if (!reader_->ReadBytes(&delta_from_largest_observed,
+                                PACKET_1BYTE_SEQUENCE_NUMBER)) {
+          set_detailed_error(
+              "Unable to read sequence delta in received packets.");
+          return false;
+        }
+        seq_num = ack_frame->largest_observed - delta_from_largest_observed;
+
+        // Time delta from the previous timestamp.
+        uint64 incremental_time_delta_us;
+        if (!reader_->ReadUFloat16(&incremental_time_delta_us)) {
+          set_detailed_error(
+              "Unable to read incremental time delta in received packets.");
+          return false;
+        }
+
+        last_timestamp_ = last_timestamp_.Add(
+            QuicTime::Delta::FromMicroseconds(incremental_time_delta_us));
+        ack_frame->received_packet_times.push_back(
+            make_pair(seq_num, creation_time_.Add(last_timestamp_)));
+      }
+    }
+  }
+  return true;
+}
+
 bool QuicFramer::ProcessStopWaitingFrame(const QuicPacketHeader& header,
                                          QuicStopWaitingFrame* stop_waiting) {
   if (!reader_->ReadBytes(&stop_waiting->entropy_hash, 1)) {
     set_detailed_error("Unable to read entropy hash for sent packets.");
     return false;
   }
 
   QuicPacketSequenceNumber least_unacked_delta = 0;
   if (!reader_->ReadBytes(&least_unacked_delta,
                           header.public_header.sequence_number_length)) {
     set_detailed_error("Unable to read least unacked delta.");
     return false;
   }
   DCHECK_GE(header.packet_sequence_number, least_unacked_delta);
   stop_waiting->least_unacked =
       header.packet_sequence_number - least_unacked_delta;
 
   return true;
 }
 
-bool QuicFramer::ProcessQuicCongestionFeedbackFrame(
+bool QuicFramer::ProcessCongestionFeedbackFrame(
     QuicCongestionFeedbackFrame* frame) {
   uint8 feedback_type;
   if (!reader_->ReadBytes(&feedback_type, 1)) {
     set_detailed_error("Unable to read congestion feedback type.");
     return false;
   }
   frame->type =
       static_cast<CongestionFeedbackType>(feedback_type);
 
   switch (frame->type) {
-    case kTimestamp: {
-      set_detailed_error("Timestamp feedback not supported.");
-      return false;
-    }
     case kTCP: {
       CongestionFeedbackMessageTCP* tcp = &frame->tcp;
       uint16 receive_window = 0;
       if (!reader_->ReadUInt16(&receive_window)) {
         set_detailed_error("Unable to read receive window.");
         return false;
       }
       // Simple bit packing, don't send the 4 least significant bits.
       tcp->receive_window = static_cast<QuicByteCount>(receive_window) << 4;
       break;
@@ skipping 275 matching lines @@
 
   size_t ack_size = GetMinAckFrameSize(sequence_number_length,
                                        largest_observed_length);
   if (!ack_info.nack_ranges.empty()) {
     ack_size += kNumberOfNackRangesSize  + kNumberOfRevivedPacketsSize;
     ack_size += min(ack_info.nack_ranges.size(), kMaxNackRanges) *
       (missing_sequence_number_length + PACKET_1BYTE_SEQUENCE_NUMBER);
     ack_size += min(ack.revived_packets.size(),
                     kMaxRevivedPackets) * largest_observed_length;
   }
+
+  // In version 23, if the ack will be truncated due to too many nack ranges,
+  // then do not include the number of timestamps (1 byte).
+  if (version() > QUIC_VERSION_22 &&
+      ack_info.nack_ranges.size() <= kMaxNackRanges) {
+    // 1 byte for the number of timestamps.
+    ack_size += 1;
+    if (ack.received_packet_times.size() > 0) {
+      // 1 byte for sequence number, 4 bytes for timestamp for the first
+      // packet.
+      ack_size += 5;
+
+      // 1 byte for sequence number, 2 bytes for timestamp for the other
+      // packets.
+      ack_size += 3 * (ack.received_packet_times.size() - 1);
+    }
+  }
+
   return ack_size;
 }
 
 size_t QuicFramer::ComputeFrameLength(
     const QuicFrame& frame,
     bool last_frame_in_packet,
     InFecGroup is_in_fec_group,
     QuicSequenceNumberLength sequence_number_length) {
   switch (frame.type) {
     case STREAM_FRAME:
       return GetMinStreamFrameSize(frame.stream_frame->stream_id,
                                    frame.stream_frame->offset,
                                    last_frame_in_packet,
                                    is_in_fec_group) +
           frame.stream_frame->data.TotalBufferSize();
     case ACK_FRAME: {
       return GetAckFrameSize(*frame.ack_frame, sequence_number_length);
     }
     case CONGESTION_FEEDBACK_FRAME: {
       size_t len = kQuicFrameTypeSize;
       const QuicCongestionFeedbackFrame& congestion_feedback =
           *frame.congestion_feedback_frame;
       len += 1;  // Congestion feedback type.
 
       switch (congestion_feedback.type) {
-        case kTimestamp: {
-          set_detailed_error("Timestamp feedback not supported.");
-          break;
-        }
         case kTCP:
           len += 2;  // Receive window.
           break;
         default:
           set_detailed_error("Illegal feedback type.");
           DVLOG(1) << "Illegal feedback type: " << congestion_feedback.type;
           break;
       }
       return len;
     }
@@ skipping 212 matching lines @@
   if (!frame.delta_time_largest_observed.IsInfinite()) {
     DCHECK_LE(0u, frame.delta_time_largest_observed.ToMicroseconds());
     delta_time_largest_observed_us =
         frame.delta_time_largest_observed.ToMicroseconds();
   }
 
   if (!writer->WriteUFloat16(delta_time_largest_observed_us)) {
     return false;
   }
 
+  // Timestamp goes at the end of the required fields.
+  if (version() > QUIC_VERSION_22 && !truncated) {
+    if (!AppendTimestampToAckFrame(frame, writer)) {
+      return false;
+    }
+  }
+
   if (ack_info.nack_ranges.empty()) {
     return true;
   }
 
   const uint8 num_missing_ranges =
       min(ack_info.nack_ranges.size(), max_num_ranges);
   if (!writer->WriteBytes(&num_missing_ranges, 1)) {
     return false;
   }
 
@@ skipping 41 matching lines @@
 }
 
 bool QuicFramer::AppendCongestionFeedbackFrame(
     const QuicCongestionFeedbackFrame& frame,
     QuicDataWriter* writer) {
   if (!writer->WriteBytes(&frame.type, 1)) {
     return false;
   }
 
   switch (frame.type) {
-    case kTimestamp: {
-      // Timestamp feedback not supported.
-      return false;
-    }
     case kTCP: {
       const CongestionFeedbackMessageTCP& tcp = frame.tcp;
       DCHECK_LE(tcp.receive_window, 1u << 20);
       // Simple bit packing, don't send the 4 least significant bits.
       uint16 receive_window = static_cast<uint16>(tcp.receive_window >> 4);
       if (!writer->WriteUInt16(receive_window)) {
         return false;
       }
       break;
     }
     default:
       return false;
   }
 
   return true;
 }
 
+bool QuicFramer::AppendTimestampToAckFrame(const QuicAckFrame& frame,
+                                           QuicDataWriter* writer) {
+  DCHECK_GE(version(), QUIC_VERSION_23);
+  DCHECK_GE(numeric_limits<uint8>::max(), frame.received_packet_times.size());
+  // num_received_packets is only 1 byte.
+  if (frame.received_packet_times.size() > numeric_limits<uint8>::max()) {
+    return false;
+  }
+
+  uint8 num_received_packets = frame.received_packet_times.size();
+
+  if (!writer->WriteBytes(&num_received_packets, 1)) {
+    return false;
+  }
+  if (num_received_packets == 0) {
+    return true;
+  }
+
+  PacketTimeList::const_iterator it = frame.received_packet_times.begin();
+  QuicPacketSequenceNumber sequence_number = it->first;
+  QuicPacketSequenceNumber delta_from_largest_observed =
+      frame.largest_observed - sequence_number;
+
+  DCHECK_GE(numeric_limits<uint8>::max(), delta_from_largest_observed);
+  if (delta_from_largest_observed > numeric_limits<uint8>::max()) {
+    return false;
+  }
+
+  if (!writer->WriteUInt8(
+    delta_from_largest_observed & k1ByteSequenceNumberMask)) {
+    return false;
+  }
+
+  // Use the lowest 4 bytes of the time delta from the creation_time_.
+  const uint64 time_epoch_delta_us = GG_UINT64_C(1) << 32;
+  uint32 time_delta_us =
+      static_cast<uint32>(it->second.Subtract(creation_time_).ToMicroseconds()
+                          & (time_epoch_delta_us - 1));
+  if (!writer->WriteBytes(&time_delta_us, sizeof(time_delta_us))) {
+    return false;
+  }
+
+  QuicTime prev_time = it->second;
+
+  for (++it; it != frame.received_packet_times.end(); ++it) {
+    sequence_number = it->first;
+    delta_from_largest_observed = frame.largest_observed - sequence_number;
+
+    if (delta_from_largest_observed > numeric_limits<uint8>::max()) {
+      return false;
+    }
+
+    if (!writer->WriteUInt8(
+            delta_from_largest_observed & k1ByteSequenceNumberMask)) {
+      return false;
+    }
+
+    uint64 time_delta_us = it->second.Subtract(prev_time).ToMicroseconds();
+    prev_time = it->second;
+    if (!writer->WriteUFloat16(time_delta_us)) {
+      return false;
+    }
+  }
+  return true;
+}
+
 bool QuicFramer::AppendStopWaitingFrame(
     const QuicPacketHeader& header,
     const QuicStopWaitingFrame& frame,
     QuicDataWriter* writer) {
   DCHECK_GE(header.packet_sequence_number, frame.least_unacked);
   const QuicPacketSequenceNumber least_unacked_delta =
       header.packet_sequence_number - frame.least_unacked;
   const QuicPacketSequenceNumber length_shift =
       header.public_header.sequence_number_length * 8;
   if (!writer->WriteUInt8(frame.entropy_hash)) {
@@ skipping 92 matching lines @@
 
 bool QuicFramer::RaiseError(QuicErrorCode error) {
   DVLOG(1) << "Error detail: " << detailed_error_;
   set_error(error);
   visitor_->OnError(this);
   reader_.reset(NULL);
   return false;
 }
 
 }  // namespace net