Refactor QUIC Receive Timestamp serialization into a separate class. PiperOrigin-RevId: 954684354
diff --git a/build/source_list.bzl b/build/source_list.bzl index 38cbf2c..82ef409 100644 --- a/build/source_list.bzl +++ b/build/source_list.bzl
@@ -306,6 +306,7 @@ "quic/core/qpack/qpack_stream_sender_delegate.h", "quic/core/qpack/value_splitting_header_list.h", "quic/core/quic_ack_listener_interface.h", + "quic/core/quic_ack_timestamp_list.h", "quic/core/quic_alarm.h", "quic/core/quic_alarm_factory.h", "quic/core/quic_alarm_factory_proxy.h", @@ -654,6 +655,7 @@ "quic/core/qpack/qpack_static_table.cc", "quic/core/qpack/value_splitting_header_list.cc", "quic/core/quic_ack_listener_interface.cc", + "quic/core/quic_ack_timestamp_list.cc", "quic/core/quic_alarm.cc", "quic/core/quic_bandwidth.cc", "quic/core/quic_blocked_writer_list.cc", @@ -1322,6 +1324,7 @@ "quic/core/qpack/qpack_send_stream_test.cc", "quic/core/qpack/qpack_static_table_test.cc", "quic/core/qpack/value_splitting_header_list_test.cc", + "quic/core/quic_ack_timestamp_list_test.cc", "quic/core/quic_alarm_test.cc", "quic/core/quic_arena_scoped_ptr_test.cc", "quic/core/quic_bandwidth_test.cc",
diff --git a/build/source_list.gni b/build/source_list.gni index f23c1b9..712ad24 100644 --- a/build/source_list.gni +++ b/build/source_list.gni
@@ -306,6 +306,7 @@ "src/quiche/quic/core/qpack/qpack_stream_sender_delegate.h", "src/quiche/quic/core/qpack/value_splitting_header_list.h", "src/quiche/quic/core/quic_ack_listener_interface.h", + "src/quiche/quic/core/quic_ack_timestamp_list.h", "src/quiche/quic/core/quic_alarm.h", "src/quiche/quic/core/quic_alarm_factory.h", "src/quiche/quic/core/quic_alarm_factory_proxy.h", @@ -654,6 +655,7 @@ "src/quiche/quic/core/qpack/qpack_static_table.cc", "src/quiche/quic/core/qpack/value_splitting_header_list.cc", "src/quiche/quic/core/quic_ack_listener_interface.cc", + "src/quiche/quic/core/quic_ack_timestamp_list.cc", "src/quiche/quic/core/quic_alarm.cc", "src/quiche/quic/core/quic_bandwidth.cc", "src/quiche/quic/core/quic_blocked_writer_list.cc", @@ -1323,6 +1325,7 @@ "src/quiche/quic/core/qpack/qpack_send_stream_test.cc", "src/quiche/quic/core/qpack/qpack_static_table_test.cc", "src/quiche/quic/core/qpack/value_splitting_header_list_test.cc", + "src/quiche/quic/core/quic_ack_timestamp_list_test.cc", "src/quiche/quic/core/quic_alarm_test.cc", "src/quiche/quic/core/quic_arena_scoped_ptr_test.cc", "src/quiche/quic/core/quic_bandwidth_test.cc",
diff --git a/build/source_list.json b/build/source_list.json index dcbd9bf..d2f82f4 100644 --- a/build/source_list.json +++ b/build/source_list.json
@@ -305,6 +305,7 @@ "quiche/quic/core/qpack/qpack_stream_sender_delegate.h", "quiche/quic/core/qpack/value_splitting_header_list.h", "quiche/quic/core/quic_ack_listener_interface.h", + "quiche/quic/core/quic_ack_timestamp_list.h", "quiche/quic/core/quic_alarm.h", "quiche/quic/core/quic_alarm_factory.h", "quiche/quic/core/quic_alarm_factory_proxy.h", @@ -653,6 +654,7 @@ "quiche/quic/core/qpack/qpack_static_table.cc", "quiche/quic/core/qpack/value_splitting_header_list.cc", "quiche/quic/core/quic_ack_listener_interface.cc", + "quiche/quic/core/quic_ack_timestamp_list.cc", "quiche/quic/core/quic_alarm.cc", "quiche/quic/core/quic_bandwidth.cc", "quiche/quic/core/quic_blocked_writer_list.cc", @@ -1322,6 +1324,7 @@ "quiche/quic/core/qpack/qpack_send_stream_test.cc", "quiche/quic/core/qpack/qpack_static_table_test.cc", "quiche/quic/core/qpack/value_splitting_header_list_test.cc", + "quiche/quic/core/quic_ack_timestamp_list_test.cc", "quiche/quic/core/quic_alarm_test.cc", "quiche/quic/core/quic_arena_scoped_ptr_test.cc", "quiche/quic/core/quic_bandwidth_test.cc",
diff --git a/quiche/quic/core/quic_ack_timestamp_list.cc b/quiche/quic/core/quic_ack_timestamp_list.cc new file mode 100644 index 0000000..32c7081 --- /dev/null +++ b/quiche/quic/core/quic_ack_timestamp_list.cc
@@ -0,0 +1,169 @@ +// Copyright 2026 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 "quiche/quic/core/quic_ack_timestamp_list.h" + +#include <algorithm> +#include <cstddef> +#include <cstdint> + +#include "absl/types/span.h" +#include "quiche/quic/core/frames/quic_ack_frame.h" +#include "quiche/quic/core/quic_data_writer.h" +#include "quiche/quic/core/quic_packet_number.h" +#include "quiche/quic/core/quic_time.h" +#include "quiche/quic/core/quic_types.h" +#include "quiche/quic/platform/api/quic_logging.h" +#include "quiche/common/platform/api/quiche_logging.h" + +namespace quic { + +namespace { + +// The maximum exponent allowed by the specification. +constexpr uint32_t kMaxExponent = 20; + +// TimestampDeltaEncoder wraps the timestamp delta encoding parameters +// (`exponent`) to improve readability via Encode/Decode methods. +struct TimestampDeltaEncoder { + uint32_t exponent; + + uint64_t Encode(QuicTimeDelta delta) { + return delta.ToMicroseconds() >> exponent; + } + uint64_t EncodeWhileRoundingUp(QuicTimeDelta delta) { + if (delta.IsZero()) { + // Avoid bitshift arithmetic on negative numbers in the edge case when + // `delta` is zero. + return 0; + } + return ((delta.ToMicroseconds() - 1) >> exponent) + 1; + } + QuicTimeDelta Decode(uint64_t encoded_delta) { + return QuicTimeDelta::FromMicroseconds(encoded_delta << exponent); + } +}; + +QuicByteCount VarintSize(uint64_t value) { + return static_cast<QuicByteCount>(QuicDataWriter::GetVarInt62Len(value)); +} + +} // namespace + +QuicAckTimestampList::QuicAckTimestampList(const QuicAckFrame& ack, + uint32_t max_ack_count, + uint32_t exponent, + QuicTime receive_timestamp_basis) + : timestamps_( + std::min<size_t>(ack.received_packet_times.size(), max_ack_count)) { + if (exponent > kMaxExponent) { + error_ = + "The specified exponent exceeds the one allowed by the specification"; + return; + } + TimestampDeltaEncoder encoder(exponent); + + // Since the timestamps are delta-encoded and rounded, we need to keep track + // of what is the latest timestamp written as it would be computed by the + // decoder. + QuicTime effective_previous_time = QuicTime::Zero(); + + for (uint32_t i = 0; i < timestamps_.size(); ++i) { + // `i` is the index into the output timestamp list; `i_src` is the index + // into the original list. They differ since `ack.received_packet_times` is + // sorted in the ascending time order, and the serialization is required + // to be in descending order. Also, the output range can be smaller than the + // input range, in which case the newer timestamps are selected as suggested + // by the spec. + const size_t i_src = ack.received_packet_times.size() - i - 1; + const auto [packet_number, timestamp] = ack.received_packet_times[i_src]; + + if (timestamp < receive_timestamp_basis) { + error_ = "Packet is received earlier than framer creation time"; + return; + } + if (packet_number > ack.largest_acked) { + error_ = "Packet number listed higher than largest_acked"; + return; + } + + bool should_open_new_range; + if (i >= 1) { + QUICHE_DCHECK(effective_previous_time.IsInitialized()); + const auto [prev_packet_number, prev_timestamp] = + ack.received_packet_times[i_src + 1]; + if (timestamp > prev_timestamp) { + error_ = + "Receive timestamps have to be in monotonically ascending order."; + return; + } + + should_open_new_range = prev_packet_number != (packet_number + 1); + timestamps_[i] = encoder.Encode(effective_previous_time - timestamp); + effective_previous_time = + effective_previous_time - encoder.Decode(timestamps_[i]); + } else { + QUICHE_DCHECK(!effective_previous_time.IsInitialized()); + should_open_new_range = true; + timestamps_[i] = + encoder.EncodeWhileRoundingUp(timestamp - receive_timestamp_basis); + effective_previous_time = + receive_timestamp_basis + encoder.Decode(timestamps_[i]); + } + + if (should_open_new_range) { + ranges_.push_back(TimestampRange{ + .delta_from_largest_acked = ack.largest_acked - packet_number, + .first_timestamp = i, + .timestamp_count = 0}); + } + ++ranges_.back().timestamp_count; + } +} + +QuicByteCount QuicAckTimestampList::EncodedSize() const { + if (!error_.empty()) { + QUIC_LOG(DFATAL) << "EncodedSize() called when error() is non-empty"; + return 0; + } + + QuicByteCount total_size = 0; + total_size += VarintSize(ranges_.size()); + for (const TimestampRange& range : ranges_) { + total_size += VarintSize(range.delta_from_largest_acked); + total_size += VarintSize(range.timestamp_count); + } + // Every element in `timestamps_` belongs to exactly one TimestampRange. + for (const uint64_t timestamp : timestamps_) { + total_size += VarintSize(timestamp); + } + return total_size; +} + +[[nodiscard]] bool QuicAckTimestampList::Write(QuicDataWriter& writer) const { + if (!error_.empty()) { + QUIC_LOG(DFATAL) << "Write() called when error() is non-empty"; + return false; + } + + if (!writer.WriteVarInt62(ranges_.size())) { + return false; + } + for (const TimestampRange& range : ranges_) { + if (!writer.WriteVarInt62(range.delta_from_largest_acked) || + !writer.WriteVarInt62(range.timestamp_count)) { + return false; + } + const absl::Span<const uint64_t> timestamps_in_range( + timestamps_.begin() + range.first_timestamp, range.timestamp_count); + for (const uint64_t timestamp : timestamps_in_range) { + if (!writer.WriteVarInt62(timestamp)) { + return false; + } + } + } + return true; +} + +} // namespace quic
diff --git a/quiche/quic/core/quic_ack_timestamp_list.h b/quiche/quic/core/quic_ack_timestamp_list.h new file mode 100644 index 0000000..81b70ab --- /dev/null +++ b/quiche/quic/core/quic_ack_timestamp_list.h
@@ -0,0 +1,65 @@ +// Copyright 2026 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. + +#ifndef QUICHE_QUIC_CORE_QUIC_ACK_TIMESTAMP_LIST_H_ +#define QUICHE_QUIC_CORE_QUIC_ACK_TIMESTAMP_LIST_H_ + +#include <cstdint> +#include <string> + +#include "absl/container/fixed_array.h" +#include "absl/container/inlined_vector.h" +#include "quiche/quic/core/frames/quic_ack_frame.h" +#include "quiche/quic/core/quic_data_writer.h" +#include "quiche/quic/core/quic_time.h" +#include "quiche/quic/core/quic_types.h" +#include "quiche/common/platform/api/quiche_export.h" + +namespace quic { + +// QuicAckTimestampList stores the block of ACK timestamps +// (draft-ietf-quic-receive-ts-02) in a form suitable for serialization. +class QUICHE_EXPORT QuicAckTimestampList { + public: + // Constructs the ACK timestamp list from the provided `ack` frame. If an + // error is encountered, `error()` will be set to a non-empty string. + explicit QuicAckTimestampList(const QuicAckFrame& ack, uint32_t max_ack_count, + uint32_t exponent, + QuicTime receive_timestamp_basis); + + // Avoid moving QuicAckTimestampList. It should always be allocated on the + // stack, since all of the data here is transient. + QuicAckTimestampList(const QuicAckTimestampList&) = delete; + QuicAckTimestampList(QuicAckTimestampList&&) = delete; + QuicAckTimestampList& operator=(const QuicAckTimestampList&) = delete; + QuicAckTimestampList& operator=(QuicAckTimestampList&&) = delete; + + // Returns the total encoded size of the ACK timestamp list in bytes. + QuicByteCount EncodedSize() const; + // Serializes the timestamp list into the `writer`. Returns false if the + // writer runs out of space while serializing. + [[nodiscard]] bool Write(QuicDataWriter& writer) const; + + const std::string& error() const { return error_; } + + private: + // `Timestamp Range` as defined in draft-ietf-quic-receive-ts-02. + struct QUICHE_EXPORT TimestampRange { + QuicPacketCount delta_from_largest_acked; + // Offset into `timestamps_` list. + uint32_t first_timestamp; + uint32_t timestamp_count; + }; + + // Timestamp ranges, in the order they would be encoded on the wire. + absl::InlinedVector<TimestampRange, 2> ranges_; + // Timestamps, in the format it would be encoded on the wire. + absl::FixedArray<uint64_t> timestamps_; + // Parse error message; empty if there is no error. + std::string error_; +}; + +} // namespace quic + +#endif // QUICHE_QUIC_CORE_QUIC_ACK_TIMESTAMP_LIST_H_
diff --git a/quiche/quic/core/quic_ack_timestamp_list_test.cc b/quiche/quic/core/quic_ack_timestamp_list_test.cc new file mode 100644 index 0000000..0378e58 --- /dev/null +++ b/quiche/quic/core/quic_ack_timestamp_list_test.cc
@@ -0,0 +1,311 @@ +// Copyright 2026 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 "quiche/quic/core/quic_ack_timestamp_list.h" + +#include <cstdint> +#include <string> + +#include "absl/strings/escaping.h" +#include "absl/strings/string_view.h" +#include "quiche/quic/core/frames/quic_ack_frame.h" +#include "quiche/quic/core/quic_data_writer.h" +#include "quiche/quic/core/quic_packet_number.h" +#include "quiche/quic/core/quic_time.h" +#include "quiche/quic/core/quic_types.h" +#include "quiche/common/platform/api/quiche_test.h" +#include "quiche/common/quiche_text_utils.h" + +namespace quic::test { +namespace { + +class QuicAckTimestampListTest : public quiche::test::QuicheTest { + protected: + QuicAckTimestampListTest() + : basis_(QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(1000)) {} + + QuicTime TimePlus(uint64_t offset_us) { + return basis_ + QuicTime::Delta::FromMicroseconds(offset_us); + } + + void ExpectBinaryEncoding(const QuicAckTimestampList& list, + absl::string_view hex) { + std::string expected; + ASSERT_TRUE(absl::HexStringToBytes(hex, &expected)); + EXPECT_EQ(list.EncodedSize(), expected.size()); + + std::string buffer(list.EncodedSize(), '\0'); + QuicDataWriter writer(buffer.size(), buffer.data()); + EXPECT_TRUE(list.Write(writer)); + EXPECT_EQ(writer.remaining(), 0u); + + EXPECT_EQ(expected, buffer) << quiche::QuicheTextUtils::HexDump(buffer); + } + + QuicAckFrame ack_; + QuicTime basis_; +}; + +TEST_F(QuicAckTimestampListTest, EmptyList) { + ack_.largest_acked = QuicPacketNumber(100); + QuicAckTimestampList list(ack_, /*max_ack_count=*/100, /*exponent=*/0, + basis_); + EXPECT_EQ(list.error(), ""); + ExpectBinaryEncoding(list, + // Range count = 0 + "00"); +} + +// Based on Section 8, Table 1 of draft-ietf-quic-receive-ts-02. +TEST_F(QuicAckTimestampListTest, DraftExampleTable1) { + ack_.largest_acked = QuicPacketNumber(100); + ack_.received_packet_times = { + {QuicPacketNumber(87), TimePlus(300)}, + {QuicPacketNumber(88), TimePlus(305)}, + {QuicPacketNumber(89), TimePlus(310)}, + {QuicPacketNumber(90), TimePlus(320)}, + {QuicPacketNumber(91), TimePlus(330)}, + {QuicPacketNumber(96), TimePlus(350)}, + {QuicPacketNumber(97), TimePlus(355)}, + {QuicPacketNumber(98), TimePlus(360)}, + {QuicPacketNumber(99), TimePlus(370)}, + {QuicPacketNumber(100), TimePlus(380)}, + }; + + QuicAckTimestampList list(ack_, /*max_ack_count=*/100, /*exponent=*/0, + basis_); + EXPECT_EQ(list.error(), ""); + ExpectBinaryEncoding(list, + "02" // Range count = 2 + // ------------ Range 1 ------------ + "00" // Delta largest acked = 0 + "05" // Count = 5 + "417c0a0a0505" // Deltas = 380, 10, 10, 5, 5 + // ------------ Range 2 ------------ + "09" // Delta largest acked = 9 + "05" // Count = 5 + "140a0a0505" // Deltas = 20, 10, 10, 5, 5 + ); +} + +// Based on Section 8, Table 2 of draft-ietf-quic-receive-ts-02. +TEST_F(QuicAckTimestampListTest, DraftExampleTable2OutOfOrder) { + ack_.largest_acked = QuicPacketNumber(100); + ack_.received_packet_times = { + {QuicPacketNumber(87), TimePlus(300)}, + {QuicPacketNumber(88), TimePlus(305)}, + {QuicPacketNumber(89), TimePlus(310)}, + {QuicPacketNumber(90), TimePlus(320)}, + {QuicPacketNumber(91), TimePlus(330)}, + {QuicPacketNumber(96), TimePlus(350)}, + {QuicPacketNumber(97), TimePlus(355)}, + {QuicPacketNumber(98), TimePlus(360)}, + {QuicPacketNumber(99), TimePlus(370)}, + {QuicPacketNumber(100), TimePlus(380)}, + {QuicPacketNumber(92), TimePlus(390)}, + {QuicPacketNumber(93), TimePlus(392)}, + {QuicPacketNumber(94), TimePlus(394)}, + {QuicPacketNumber(95), TimePlus(395)}, + }; + + QuicAckTimestampList list(ack_, /*max_ack_count=*/100, /*exponent=*/0, + basis_); + EXPECT_EQ(list.error(), ""); + ExpectBinaryEncoding(list, + "03" // Range count = 3 + // ------------ Range 1 ------------ + "05" // Delta largest acked = 5 + "04" // Count = 4 + "418b010202" // Deltas = 395, 1, 2, 2 + // ------------ Range 2 ------------ + "00" // Delta largest acked = 0 + "05" // Count = 5 + "0a0a0a0505" // Deltas = 10, 10, 10, 5, 5 + // ------------ Range 3 ------------ + "09" // Delta largest acked = 9 + "05" // Count = 5 + "140a0a0505" // Deltas = 20, 10, 10, 5, 5 + ); +} + +// Derived from AckFrameMultipleReceiveTimestampRanges in quic_framer_test.cc. +// Tests encoding multiple ranges with gaps where the first range does not +// start at largest_acked. +TEST_F(QuicAckTimestampListTest, InspiredByFramerTestMultipleRanges) { + ack_.largest_acked = QuicPacketNumber(1000); + ack_.received_packet_times = { + // Range 3: Delta largest acked = 21 (979), Count = 2 + {QuicPacketNumber(978), TimePlus(100)}, + {QuicPacketNumber(979), TimePlus(110)}, + // Range 2: Delta largest acked = 11 (989), Count = 1 + {QuicPacketNumber(989), TimePlus(200)}, + // Range 1: Delta largest acked = 2 (998), Count = 3 + {QuicPacketNumber(996), TimePlus(300)}, + {QuicPacketNumber(997), TimePlus(350)}, + {QuicPacketNumber(998), TimePlus(400)}, + }; + + QuicAckTimestampList list(ack_, /*max_ack_count=*/100, /*exponent=*/0, + basis_); + EXPECT_EQ(list.error(), ""); + ExpectBinaryEncoding(list, + "03" // Range count = 3 + // ------------ Range 1 ------------ + "02" // Delta largest acked = 2 + "03" // Count = 3 + "41903232" // Deltas = 400, 50, 50 + // ------------ Range 2 ------------ + "0b" // Delta largest acked = 11 + "01" // Count = 1 + "4064" // Deltas = 100 + // ------------ Range 3 ------------ + "15" // Delta largest acked = 21 + "02" // Count = 2 + "405a0a" // Deltas = 90, 10 + ); +} + +// Ensure that ACK timestamps are truncated up to the limit specified by the +// peer. +TEST_F(QuicAckTimestampListTest, MaxAckCountTruncation) { + ack_.largest_acked = QuicPacketNumber(10); + ack_.received_packet_times = { + {QuicPacketNumber(6), TimePlus(60)}, + {QuicPacketNumber(7), TimePlus(70)}, + {QuicPacketNumber(8), TimePlus(80)}, + {QuicPacketNumber(9), TimePlus(90)}, + {QuicPacketNumber(10), TimePlus(100)}, + }; + + // Only the 3 newest timestamps (packets 10, 9, 8) should be included. + QuicAckTimestampList list(ack_, /*max_ack_count=*/3, /*exponent=*/0, basis_); + EXPECT_EQ(list.error(), ""); + ExpectBinaryEncoding(list, + "01" // Range count = 1 + // Range 1 + "00" // Delta largest acked = 0 + "03" // Count = 3 + "40640a0a" // Deltas = 100, 10, 10 + ); +} + +TEST_F(QuicAckTimestampListTest, ExponentAndRounding) { + ack_.largest_acked = QuicPacketNumber(3); + ack_.received_packet_times = { + {QuicPacketNumber(1), TimePlus(17)}, + {QuicPacketNumber(2), TimePlus(25)}, + {QuicPacketNumber(3), TimePlus(41)}, + }; + + // Exponent 3 encodes time deltas in units of 2^3 = 8 microseconds. + // First delta is rounded up: + // ((41 - 1) >> 3) + 1 = 6 + // Effective time = 48 + // Second delta: + // (48 - 25) >> 3 = 2 + // Effective time = 32. + // Third delta: + // (32 - 17) >> 3 = 1 + // Effective time = 24. + QuicAckTimestampList list(ack_, /*max_ack_count=*/10, /*exponent=*/3, basis_); + EXPECT_EQ(list.error(), ""); + ExpectBinaryEncoding(list, + "01" // Range count = 1 + // Range 1 + "00" // Delta largest acked = 0 + "03" // Count = 3 + "060201" // Deltas = 6, 2, 1 + ); +} + +TEST_F(QuicAckTimestampListTest, EncodeWhileRoundingUpZeroDelta) { + ack_.largest_acked = QuicPacketNumber(3); + ack_.received_packet_times = { + {QuicPacketNumber(1), basis_}, + {QuicPacketNumber(2), basis_}, + {QuicPacketNumber(3), basis_}, + }; + + QuicAckTimestampList list(ack_, /*max_ack_count=*/10, /*exponent=*/3, basis_); + EXPECT_EQ(list.error(), ""); + ExpectBinaryEncoding(list, + "01" // Range count = 1 + // Range 1 + "00" // Delta largest acked = 0 + "03" // Count = 3 + "000000" // Deltas = 0, 0, 0 + ); +} + +TEST_F(QuicAckTimestampListTest, ErrorPacketEarlierThanBasis) { + ack_.largest_acked = QuicPacketNumber(10); + ack_.received_packet_times = { + {QuicPacketNumber(10), basis_ - QuicTime::Delta::FromMicroseconds(1)}, + }; + + QuicAckTimestampList list(ack_, /*max_ack_count=*/10, /*exponent=*/0, basis_); + EXPECT_EQ(list.error(), + "Packet is received earlier than framer creation time"); +} + +TEST_F(QuicAckTimestampListTest, ErrorPacketNumberHigherThanLargestAcked) { + ack_.largest_acked = QuicPacketNumber(50); + ack_.received_packet_times = { + {QuicPacketNumber(51), TimePlus(100)}, + }; + + QuicAckTimestampList list(ack_, /*max_ack_count=*/10, /*exponent=*/0, basis_); + EXPECT_EQ(list.error(), "Packet number listed higher than largest_acked"); +} + +TEST_F(QuicAckTimestampListTest, ErrorTimestampsNotMonotonicallyAscending) { + ack_.largest_acked = QuicPacketNumber(10); + ack_.received_packet_times = { + {QuicPacketNumber(9), TimePlus(100)}, + {QuicPacketNumber(10), TimePlus(90)}, + }; + + QuicAckTimestampList list(ack_, /*max_ack_count=*/10, /*exponent=*/0, basis_); + EXPECT_EQ(list.error(), + "Receive timestamps have to be in monotonically ascending order."); +} + +TEST_F(QuicAckTimestampListTest, ErrorExponentTooLarge) { + ack_.largest_acked = QuicPacketNumber(10); + ack_.received_packet_times = { + {QuicPacketNumber(10), TimePlus(100)}, + }; + + QuicAckTimestampList valid_list(ack_, /*max_ack_count=*/10, /*exponent=*/20, + basis_); + EXPECT_EQ(valid_list.error(), ""); + + QuicAckTimestampList invalid_list(ack_, /*max_ack_count=*/10, /*exponent=*/21, + basis_); + EXPECT_EQ( + invalid_list.error(), + "The specified exponent exceeds the one allowed by the specification"); +} + +TEST_F(QuicAckTimestampListTest, BufferTooSmall) { + ack_.largest_acked = QuicPacketNumber(100); + ack_.received_packet_times = { + {QuicPacketNumber(99), TimePlus(10)}, + {QuicPacketNumber(100), TimePlus(20)}, + }; + + QuicAckTimestampList list(ack_, /*max_ack_count=*/10, /*exponent=*/0, basis_); + EXPECT_EQ(list.error(), ""); + const QuicByteCount expected_size = list.EncodedSize(); + EXPECT_GT(expected_size, 0u); + + for (QuicByteCount buf_len = 0; buf_len < expected_size; ++buf_len) { + std::string buffer(buf_len, '\0'); + QuicDataWriter writer(buffer.size(), buffer.data()); + EXPECT_FALSE(list.Write(writer)) << "buf_len: " << buf_len; + } +} + +} // namespace +} // namespace quic::test
diff --git a/quiche/quic/core/quic_framer.cc b/quiche/quic/core/quic_framer.cc index e5e4090..4e6f8f2 100644 --- a/quiche/quic/core/quic_framer.cc +++ b/quiche/quic/core/quic_framer.cc
@@ -43,6 +43,7 @@ #include "quiche/quic/core/frames/quic_datagram_frame.h" #include "quiche/quic/core/frames/quic_immediate_ack_frame.h" #include "quiche/quic/core/frames/quic_reset_stream_at_frame.h" +#include "quiche/quic/core/quic_ack_timestamp_list.h" #include "quiche/quic/core/quic_connection_id.h" #include "quiche/quic/core/quic_constants.h" #include "quiche/quic/core/quic_data_reader.h" @@ -4792,16 +4793,15 @@ size_t QuicFramer::GetIetfAckFrameTimestampSize(const QuicAckFrame& ack) { QUICHE_DCHECK(!ack.received_packet_times.empty()); - std::string detailed_error; - absl::InlinedVector<AckTimestampRange, 2> timestamp_ranges = - GetAckTimestampRanges(ack, detailed_error); - if (!detailed_error.empty()) { + QuicAckTimestampList timestamp_list(ack, peer_max_receive_timestamps_per_ack_, + peer_receive_timestamps_exponent_, + creation_time_); + if (!timestamp_list.error().empty()) { + QUIC_BUG(quic_framer_ack_ts_list_error) << timestamp_list.error(); return 0; } - int64_t size = - FrameAckTimestampRanges(ack, timestamp_ranges, /*writer=*/nullptr); - return std::max<int64_t>(0, size); + return timestamp_list.EncodedSize(); } size_t QuicFramer::GetAckFrameSize( @@ -5449,200 +5449,20 @@ return true; } -absl::InlinedVector<QuicFramer::AckTimestampRange, 2> -QuicFramer::GetAckTimestampRanges(const QuicAckFrame& frame, - std::string& detailed_error) const { - detailed_error = ""; - if (frame.received_packet_times.empty()) { - return {}; - } - - absl::InlinedVector<AckTimestampRange, 2> timestamp_ranges; - - for (size_t r = 0; r < std::min<size_t>(peer_max_receive_timestamps_per_ack_, - frame.received_packet_times.size()); - ++r) { - const size_t i = frame.received_packet_times.size() - 1 - r; - const QuicPacketNumber packet_number = frame.received_packet_times[i].first; - const QuicTime receive_timestamp = frame.received_packet_times[i].second; - - if (timestamp_ranges.empty()) { - if (receive_timestamp < creation_time_ || - LargestAcked(frame) < packet_number) { - detailed_error = - "The first packet is either received earlier than framer creation " - "time, or larger than largest acked packet."; - QUIC_BUG(quic_framer_ack_ts_first_packet_bad) - << detailed_error << " receive_timestamp:" << receive_timestamp - << ", framer_creation_time:" << creation_time_ - << ", packet_number:" << packet_number - << ", largest_acked:" << LargestAcked(frame); - return {}; - } - timestamp_ranges.push_back(AckTimestampRange()); - timestamp_ranges.back().delta_from_largest_acked = - LargestAcked(frame) - packet_number; - timestamp_ranges.back().range_begin = i; - timestamp_ranges.back().range_end = i; - continue; - } - - const size_t prev_i = timestamp_ranges.back().range_end; - const QuicPacketNumber prev_packet_number = - frame.received_packet_times[prev_i].first; - const QuicTime prev_receive_timestamp = - frame.received_packet_times[prev_i].second; - - QUIC_DVLOG(3) << "prev_packet_number:" << prev_packet_number - << ", packet_number:" << packet_number; - if (prev_receive_timestamp < receive_timestamp) { - detailed_error = "Receive time not in order."; - QUIC_BUG(quic_framer_ack_ts_time_out_of_order) - << detailed_error << " packet_number:" << packet_number - << ", receive_timestamp:" << receive_timestamp - << ", prev_packet_number:" << prev_packet_number - << ", prev_receive_timestamp:" << prev_receive_timestamp; - return {}; - } - - if (prev_packet_number == packet_number + 1) { - timestamp_ranges.back().range_end = i; - } else { - timestamp_ranges.push_back(AckTimestampRange()); - timestamp_ranges.back().delta_from_largest_acked = - LargestAcked(frame) - packet_number; - timestamp_ranges.back().range_begin = i; - timestamp_ranges.back().range_end = i; - } - } - - return timestamp_ranges; -} - -namespace { - -// Wrapper around a nullable pointer to QuicDataWriter. Always computes the -// length of data written. -class QuicDataWriterWrapper { - public: - explicit QuicDataWriterWrapper(QuicDataWriter* absl_nullable writer) - : writer_(writer) {} - - [[nodiscard]] bool WriteVarInt62(uint64_t value) { - bytes_written_ += QuicDataWriter::GetVarInt62Len(value); - if (writer_ == nullptr) { - // Null writer means we are computing the length; assume that all writes - // succeed for that purpose. - return true; - } - return writer_->WriteVarInt62(value); - } - - size_t bytes_written() const { return bytes_written_; } - - private: - QuicDataWriter* absl_nullable writer_; - size_t bytes_written_ = 0; -}; - -} // namespace - -int64_t QuicFramer::FrameAckTimestampRanges( - const QuicAckFrame& frame, - const absl::InlinedVector<AckTimestampRange, 2>& timestamp_ranges, - QuicDataWriter* absl_nullable writer) const { - QuicDataWriterWrapper wrapper(writer); - - if (!wrapper.WriteVarInt62(timestamp_ranges.size())) { - return -1; - } - - int64_t size = wrapper.bytes_written(); - // |effective_prev_time| is the exponent-encoded timestamp of the previous - // packet. - std::optional<QuicTime> effective_prev_time; - for (const AckTimestampRange& range : timestamp_ranges) { - int64_t range_size = - FrameAckTimestampRange(frame, range, effective_prev_time, writer); - if (range_size < 0) { - return -1; - } - size += range_size; - } - - return size; -} - -int64_t QuicFramer::FrameAckTimestampRange( - const QuicAckFrame& frame, const AckTimestampRange& range, - std::optional<QuicTime>& effective_prev_time, - QuicDataWriter* absl_nullable writer) const { - QuicDataWriterWrapper wrapper(writer); - - QUIC_DVLOG(3) << "Range: delta:" << range.delta_from_largest_acked - << ", beg:" << range.range_begin << ", end:" << range.range_end; - if (!wrapper.WriteVarInt62(range.delta_from_largest_acked)) { - return -1; - } - - if (!wrapper.WriteVarInt62(range.range_begin - range.range_end + 1)) { - return -1; - } - - for (int64_t i = range.range_begin; i >= range.range_end; --i) { - const QuicTime receive_timestamp = frame.received_packet_times[i].second; - uint64_t time_delta; - if (effective_prev_time.has_value()) { - time_delta = (*effective_prev_time - receive_timestamp).ToMicroseconds(); - QUIC_DVLOG(3) << "time_delta:" << time_delta - << ", exponent:" << peer_receive_timestamps_exponent_ - << ", effective_prev_time:" << *effective_prev_time - << ", recv_time:" << receive_timestamp; - time_delta = time_delta >> peer_receive_timestamps_exponent_; - effective_prev_time = - *effective_prev_time - - QuicTime::Delta::FromMicroseconds( - time_delta << peer_receive_timestamps_exponent_); - } else { - // The first delta is from framer creation to the current receive - // timestamp (forward in time), whereas in the common case subsequent - // deltas move backwards in time. - time_delta = (receive_timestamp - creation_time_).ToMicroseconds(); - QUIC_DVLOG(3) << "First time_delta:" << time_delta - << ", exponent:" << peer_receive_timestamps_exponent_ - << ", recv_time:" << receive_timestamp - << ", creation_time:" << creation_time_; - // Round up the first exponent-encoded time delta so that the next - // receive timestamp is guaranteed to be decreasing. - time_delta = ((time_delta - 1) >> peer_receive_timestamps_exponent_) + 1; - effective_prev_time = - creation_time_ + QuicTime::Delta::FromMicroseconds( - time_delta << peer_receive_timestamps_exponent_); - } - - if (!wrapper.WriteVarInt62(time_delta)) { - return -1; - } - } - - return wrapper.bytes_written(); -} - bool QuicFramer::AppendIetfTimestampsToAckFrame(const QuicAckFrame& frame, QuicDataWriter* writer) { QUICHE_DCHECK(!frame.received_packet_times.empty()); - std::string detailed_error; - const absl::InlinedVector<AckTimestampRange, 2> timestamp_ranges = - GetAckTimestampRanges(frame, detailed_error); - if (!detailed_error.empty()) { - set_detailed_error(std::move(detailed_error)); + QuicAckTimestampList timestamp_list( + frame, peer_max_receive_timestamps_per_ack_, + peer_receive_timestamps_exponent_, creation_time_); + if (!timestamp_list.error().empty()) { + QUIC_BUG(quic_framer_ack_ts_list_error) << timestamp_list.error(); + set_detailed_error(timestamp_list.error()); return false; } - // Compute the size first using a null writer. - int64_t size = - FrameAckTimestampRanges(frame, timestamp_ranges, /*writer=*/nullptr); - if (size > static_cast<int64_t>(writer->capacity() - writer->length())) { + const QuicByteCount size = timestamp_list.EncodedSize(); + if (size > writer->capacity() - writer->length()) { QUIC_DVLOG(1) << "Insufficient room to write IETF ack receive timestamps. " "size_remain:" << (writer->capacity() - writer->length()) @@ -5651,7 +5471,7 @@ return writer->WriteVarInt62(0); } - return FrameAckTimestampRanges(frame, timestamp_ranges, writer) > 0; + return timestamp_list.Write(*writer); } bool QuicFramer::AppendIetfAckFrameAndTypeByte(const QuicAckFrame& frame,
diff --git a/quiche/quic/core/quic_framer.h b/quiche/quic/core/quic_framer.h index 01fcd2b..26671f8 100644 --- a/quiche/quic/core/quic_framer.h +++ b/quiche/quic/core/quic_framer.h
@@ -790,27 +790,6 @@ using NackRangeMap = std::map<QuicPacketNumber, uint8_t>; using AssociatedDataStorage = absl::InlinedVector<char, 20>; - // AckTimestampRange is a data structure derived from a QuicAckFrame. It is - // used to serialize timestamps in a IETF_ACK_RECEIVE_TIMESTAMPS frame. - struct QUICHE_EXPORT AckTimestampRange { - QuicPacketCount delta_from_largest_acked; - // |range_begin| and |range_end| are index(es) in - // QuicAckFrame.received_packet_times, representing a continuous range of - // packet numbers in descending order. |range_begin| >= |range_end|. - int64_t range_begin; // Inclusive - int64_t range_end; // Inclusive - }; - absl::InlinedVector<AckTimestampRange, 2> GetAckTimestampRanges( - const QuicAckFrame& frame, std::string& detailed_error) const; - int64_t FrameAckTimestampRanges( - const QuicAckFrame& frame, - const absl::InlinedVector<AckTimestampRange, 2>& timestamp_ranges, - QuicDataWriter* absl_nullable writer) const; - int64_t FrameAckTimestampRange(const QuicAckFrame& frame, - const AckTimestampRange& range, - std::optional<QuicTime>& effective_prev_time, - QuicDataWriter* absl_nullable writer) const; - struct QUICHE_EXPORT AckFrameInfo { AckFrameInfo(); AckFrameInfo(const AckFrameInfo& other);
diff --git a/quiche/quic/core/quic_framer_test.cc b/quiche/quic/core/quic_framer_test.cc index b6da809..08e96c5 100644 --- a/quiche/quic/core/quic_framer_test.cc +++ b/quiche/quic/core/quic_framer_test.cc
@@ -7431,8 +7431,9 @@ ack_frame.ack_delay_time = QuicTime::Delta::Zero(); QuicFrames frames = {QuicFrame(&ack_frame)}; - EXPECT_QUIC_BUG(BuildDataPacket(header, frames), - "Receive time not in order."); + EXPECT_QUIC_BUG( + BuildDataPacket(header, frames), + "Receive timestamps have to be in monotonically ascending order."); } TEST_P(QuicFramerTest, ProcessIetfAckReceiveTimestampsExceedsMaxTimestamps) {