Officially allow out-of-order writes in QuicStreamSendBuffer This has always worked, but there was a QUIC_BUG to prevent it. Unfortunately the QUIC_BUG had a bug where QuicStreamSendBuffer::current_end_offset_ was not computed properly, so it never correctly enforced in-order writes. Chaos Protection v2 triggers this QUIC_BUG when the Client Hello size exceeds the value of the quic_send_buffer_max_data_slice_size flag. PiperOrigin-RevId: 712548578
diff --git a/quiche/quic/core/http/end_to_end_test.cc b/quiche/quic/core/http/end_to_end_test.cc index 105f0b3..0015c41 100644 --- a/quiche/quic/core/http/end_to_end_test.cc +++ b/quiche/quic/core/http/end_to_end_test.cc
@@ -6692,6 +6692,17 @@ /*drop_first_packet=*/true); } +TEST_P(EndToEndTest, FourPacketChaosProtection) { + TestMultiPacketChaosProtection(/*num_packets=*/4, + /*drop_first_packet=*/false); +} + +TEST_P(EndToEndTest, FivePacketChaosProtection) { + // Regression test for b/387486449. + TestMultiPacketChaosProtection(/*num_packets=*/5, + /*drop_first_packet=*/false); +} + void EndToEndTest::TestMultiPacketChaosProtection(int num_packets, bool drop_first_packet, bool kyber) { @@ -6752,49 +6763,32 @@ EXPECT_EQ(crypto_data_intervals.SpanningInterval().min(), 0u); EXPECT_GT(crypto_data_intervals.SpanningInterval().max(), discard_length); - ASSERT_GE(copying_writer->initial_packets().size(), 2u); - // First packet contains the start and end of the client hello. - auto& packet1 = copying_writer->initial_packets()[0]; - EXPECT_EQ(packet1->was_dropped, drop_first_packet); - EXPECT_EQ(packet1->packet_number, 1u); - EXPECT_TRUE(packet1->num_crypto_frames > 2 || packet1->num_ping_frames > 0 || - packet1->num_padding_frames > 1) - << "crypto=" << packet1->num_crypto_frames - << ", ping=" << packet1->num_ping_frames - << ", pad=" << packet1->num_padding_frames; - EXPECT_EQ(packet1->min_crypto_offset(), 0u); - EXPECT_GE(packet1->max_crypto_data(), discard_length); - EXPECT_GE(packet1->total_crypto_data_length, 500u); - // Subsequent packets contain the middle of the client hello. - auto& packet2 = copying_writer->initial_packets()[1]; - EXPECT_FALSE(packet2->was_dropped); - EXPECT_EQ(packet2->packet_number, 2u); - if (num_packets == 2) { - EXPECT_TRUE(packet2->num_crypto_frames > 2 || - packet2->num_ping_frames > 0 || packet2->num_padding_frames > 1) - << "crypto=" << packet2->num_crypto_frames - << ", ping=" << packet2->num_ping_frames - << ", pad=" << packet2->num_padding_frames; - } else { - EXPECT_GE(packet2->num_crypto_frames, 1u); + for (int i = 1; i <= num_packets; ++i) { + ASSERT_GE(copying_writer->initial_packets().size(), i); + auto& packet = copying_writer->initial_packets()[i - 1]; + EXPECT_EQ(packet->was_dropped, drop_first_packet && i == 1); + EXPECT_EQ(packet->packet_number, i); + if (i == 1 || i == num_packets) { + // Ensure first and last packets are properly chaos protected. + EXPECT_TRUE(packet->num_crypto_frames > 2 || + packet->num_ping_frames > 0 || packet->num_padding_frames > 1) + << "crypto=" << packet->num_crypto_frames + << ", ping=" << packet->num_ping_frames + << ", pad=" << packet->num_padding_frames; + } else { + // Middle packets do not have single-packet chaos protection. + EXPECT_GE(packet->num_crypto_frames, 1u); + } + if (i == 1) { + EXPECT_EQ(packet->min_crypto_offset(), 0u); + EXPECT_GE(packet->max_crypto_data(), discard_length); + } else { + EXPECT_GT(packet->min_crypto_offset(), 0u); + EXPECT_LT(packet->max_crypto_data(), discard_length); + } + EXPECT_GE(packet->total_crypto_data_length, 500u); } - EXPECT_GT(packet2->min_crypto_offset(), 0u); - EXPECT_LT(packet2->max_crypto_data(), discard_length); - EXPECT_GE(packet2->total_crypto_data_length, 500u); - if (num_packets >= 3) { - ASSERT_GE(copying_writer->initial_packets().size(), 3u); - auto& packet3 = copying_writer->initial_packets()[2]; - EXPECT_FALSE(packet3->was_dropped); - EXPECT_EQ(packet3->packet_number, 3u); - EXPECT_TRUE(packet3->num_crypto_frames > 2 || - packet3->num_ping_frames > 0 || packet3->num_padding_frames > 1) - << "crypto=" << packet3->num_crypto_frames - << ", ping=" << packet3->num_ping_frames - << ", pad=" << packet3->num_padding_frames; - EXPECT_GT(packet3->min_crypto_offset(), 0u); - EXPECT_LT(packet3->max_crypto_data(), discard_length); - EXPECT_GE(packet3->total_crypto_data_length, 500u); - } + if (!drop_first_packet) { return; }
diff --git a/quiche/quic/core/quic_stream_send_buffer.cc b/quiche/quic/core/quic_stream_send_buffer.cc index 003a040..3acd2cb 100644 --- a/quiche/quic/core/quic_stream_send_buffer.cc +++ b/quiche/quic/core/quic_stream_send_buffer.cc
@@ -50,8 +50,7 @@ QuicStreamSendBuffer::QuicStreamSendBuffer( quiche::QuicheBufferAllocator* allocator) - : current_end_offset_(0), - stream_offset_(0), + : stream_offset_(0), allocator_(allocator), stream_bytes_written_(0), stream_bytes_outstanding_(0), @@ -60,6 +59,8 @@ QuicStreamSendBuffer::~QuicStreamSendBuffer() {} void QuicStreamSendBuffer::SaveStreamData(absl::string_view data) { + QUIC_DVLOG(2) << "Save stream data offset " << stream_offset_ << " length " + << data.length(); QUICHE_DCHECK(!data.empty()); // Latch the maximum data slice size. @@ -84,11 +85,6 @@ return; } size_t length = slice.length(); - // Need to start the offsets at the right interval. - if (interval_deque_.Empty()) { - const QuicStreamOffset end = stream_offset_ + length; - current_end_offset_ = std::max(current_end_offset_, end); - } BufferedSlice bs = BufferedSlice(std::move(slice), stream_offset_); interval_deque_.PushBack(std::move(bs)); stream_offset_ += length; @@ -116,9 +112,6 @@ bool QuicStreamSendBuffer::WriteStreamData(QuicStreamOffset offset, QuicByteCount data_length, QuicDataWriter* writer) { - QUIC_BUG_IF(quic_bug_12823_1, current_end_offset_ < offset) - << "Tried to write data out of sequence. last_offset_end:" - << current_end_offset_ << ", offset:" << offset; // The iterator returned from |interval_deque_| will automatically advance // the internal write index for the QuicIntervalDeque. The incrementing is // done in operator++. @@ -139,9 +132,6 @@ } offset += copy_length; data_length -= copy_length; - const QuicStreamOffset new_end = - slice_it->offset + slice_it->slice.length(); - current_end_offset_ = std::max(current_end_offset_, new_end); } return data_length == 0; } @@ -149,6 +139,8 @@ bool QuicStreamSendBuffer::OnStreamDataAcked( QuicStreamOffset offset, QuicByteCount data_length, QuicByteCount* newly_acked_length) { + QUIC_DVLOG(2) << "Marking data acked at offset " << offset << " length " + << data_length; *newly_acked_length = 0; if (data_length == 0) { return true; @@ -273,12 +265,6 @@ void QuicStreamSendBuffer::CleanUpBufferedSlices() { while (!interval_deque_.Empty() && interval_deque_.DataBegin()->slice.empty()) { - QUIC_BUG_IF(quic_bug_12823_2, - interval_deque_.DataBegin()->offset > current_end_offset_) - << "Fail to pop front from interval_deque_. Front element contained " - "a slice whose data has not all be written. Front offset " - << interval_deque_.DataBegin()->offset << " length " - << interval_deque_.DataBegin()->slice.length(); interval_deque_.PopFront(); } }
diff --git a/quiche/quic/core/quic_stream_send_buffer.h b/quiche/quic/core/quic_stream_send_buffer.h index b892cdf..d87272a 100644 --- a/quiche/quic/core/quic_stream_send_buffer.h +++ b/quiche/quic/core/quic_stream_send_buffer.h
@@ -60,7 +60,10 @@ // QuicStreamSendBuffer contains a list of QuicStreamDataSlices. New data slices // are added to the tail of the list. Data slices are removed from the head of // the list when they get fully acked. Stream data can be retrieved and acked -// across slice boundaries. +// across slice boundaries. Stream data must be saved before being written, and +// it cannot be written after it is marked as acked. Stream data can be written +// out-of-order within those bounds, but note that in-order wites are O(1) +// whereas out-of-order writes are O(log(n)), see QuicIntervalDeque for details. class QUICHE_EXPORT QuicStreamSendBuffer { public: explicit QuicStreamSendBuffer(quiche::QuicheBufferAllocator* allocator); @@ -80,7 +83,10 @@ // Called when |bytes_consumed| bytes has been consumed by the stream. void OnStreamDataConsumed(size_t bytes_consumed); - // Write |data_length| of data starts at |offset|. + // Write |data_length| of data starts at |offset|. Returns true if all data + // was successfully written. Returns false if the writer fails to write, or if + // the data was already marked as acked, or if the data was never saved in the + // first place. bool WriteStreamData(QuicStreamOffset offset, QuicByteCount data_length, QuicDataWriter* writer); @@ -136,12 +142,9 @@ // not exist or has been acked. bool FreeMemSlices(QuicStreamOffset start, QuicStreamOffset end); - // Cleanup empty slices in order from buffered_slices_. + // Cleanup acked data from the start of the interval. void CleanUpBufferedSlices(); - // |current_end_offset_| stores the end offset of the current slice to ensure - // data isn't being written out of order when using the |interval_deque_|. - QuicStreamOffset current_end_offset_; QuicIntervalDeque<BufferedSlice> interval_deque_; // Offset of next inserted byte.
diff --git a/quiche/quic/core/quic_stream_send_buffer_test.cc b/quiche/quic/core/quic_stream_send_buffer_test.cc index fbcd90a..a9f8d3a 100644 --- a/quiche/quic/core/quic_stream_send_buffer_test.cc +++ b/quiche/quic/core/quic_stream_send_buffer_test.cc
@@ -28,8 +28,6 @@ EXPECT_EQ(0u, send_buffer_.size()); EXPECT_EQ(0u, send_buffer_.stream_bytes_written()); EXPECT_EQ(0u, send_buffer_.stream_bytes_outstanding()); - // The stream offset should be 0 since nothing is written. - EXPECT_EQ(0u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_)); std::string data1 = absl::StrCat( std::string(1536, 'a'), std::string(256, 'b'), std::string(256, 'c')); @@ -63,7 +61,7 @@ // Write all data. char buf[4000]; QuicDataWriter writer(4000, buf, quiche::HOST_BYTE_ORDER); - send_buffer_.WriteStreamData(0, 3840u, &writer); + EXPECT_TRUE(send_buffer_.WriteStreamData(0, 3840u, &writer)); send_buffer_.OnStreamDataConsumed(3840u); EXPECT_EQ(3840u, send_buffer_.stream_bytes_written()); @@ -133,13 +131,10 @@ EXPECT_EQ(copy1 + copy2, absl::string_view(buf + 1024, 2048)); // Write new data. - EXPECT_EQ(2048u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_)); ASSERT_TRUE(send_buffer_.WriteStreamData(2048, 50, &writer)); EXPECT_EQ(std::string(50, 'c'), absl::string_view(buf + 1024 + 2048, 50)); - EXPECT_EQ(3072u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_)); ASSERT_TRUE(send_buffer_.WriteStreamData(2048, 1124, &writer)); EXPECT_EQ(copy3, absl::string_view(buf + 1024 + 2048 + 50, 1124)); - EXPECT_EQ(3840u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_)); } TEST_F(QuicStreamSendBufferTest, RemoveStreamFrame) { @@ -164,7 +159,7 @@ EXPECT_EQ(0u, send_buffer_.size()); } -TEST_F(QuicStreamSendBufferTest, RemoveStreamFrameAcrossBoundries) { +TEST_F(QuicStreamSendBufferTest, RemoveStreamFrameAcrossBoundaries) { WriteAllData(); QuicByteCount newly_acked_length; @@ -280,37 +275,21 @@ EXPECT_TRUE(send_buffer_.IsStreamDataOutstanding(400, 800)); } -TEST_F(QuicStreamSendBufferTest, EndOffset) { - char buf[4000]; - QuicDataWriter writer(4000, buf, quiche::HOST_BYTE_ORDER); - - EXPECT_EQ(1024u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_)); - ASSERT_TRUE(send_buffer_.WriteStreamData(0, 1024, &writer)); - // Last offset we've seen is 1024 - EXPECT_EQ(1024u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_)); - - ASSERT_TRUE(send_buffer_.WriteStreamData(1024, 512, &writer)); - // Last offset is now 2048 as that's the end of the next slice. - EXPECT_EQ(2048u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_)); - send_buffer_.OnStreamDataConsumed(1024); - - // If data in 1st slice gets ACK'ed, it shouldn't change the indexed slice - QuicByteCount newly_acked_length; - EXPECT_TRUE(send_buffer_.OnStreamDataAcked(0, 1024, &newly_acked_length)); - // Last offset is still 2048. - EXPECT_EQ(2048u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_)); - - ASSERT_TRUE( - send_buffer_.WriteStreamData(1024 + 512, 3840 - 1024 - 512, &writer)); - - // Last offset is end offset of last slice. - EXPECT_EQ(3840u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_)); - quiche::QuicheBuffer buffer(&allocator_, 60); - memset(buffer.data(), 'e', buffer.size()); - quiche::QuicheMemSlice slice(std::move(buffer)); - send_buffer_.SaveMemSlice(std::move(slice)); - - EXPECT_EQ(3840u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_)); +TEST_F(QuicStreamSendBufferTest, OutOfOrderWrites) { + char buf[3840] = {}; + // Write data out of order. + QuicDataWriter writer2(sizeof(buf) - 1000, buf + 1000); + EXPECT_TRUE(send_buffer_.WriteStreamData(1000u, 1000u, &writer2)); + QuicDataWriter writer4(sizeof(buf) - 3000, buf + 3000); + EXPECT_TRUE(send_buffer_.WriteStreamData(3000u, 840u, &writer4)); + QuicDataWriter writer3(sizeof(buf) - 2000, buf + 2000); + EXPECT_TRUE(send_buffer_.WriteStreamData(2000u, 1000u, &writer3)); + QuicDataWriter writer1(sizeof(buf), buf); + EXPECT_TRUE(send_buffer_.WriteStreamData(0u, 1000u, &writer1)); + // Make sure it is correct. + EXPECT_EQ(absl::string_view(buf, sizeof(buf)), + absl::StrCat(std::string(1536, 'a'), std::string(256, 'b'), + std::string(1280, 'c'), std::string(768, 'd'))); } TEST_F(QuicStreamSendBufferTest, SaveMemSliceSpan) {
diff --git a/quiche/quic/test_tools/quic_stream_send_buffer_peer.cc b/quiche/quic/test_tools/quic_stream_send_buffer_peer.cc index c81b45e..c2c2806 100644 --- a/quiche/quic/test_tools/quic_stream_send_buffer_peer.cc +++ b/quiche/quic/test_tools/quic_stream_send_buffer_peer.cc
@@ -27,11 +27,6 @@ return QuicIntervalDequePeer::GetItem(&send_buffer->interval_deque_, wi); } -QuicStreamOffset QuicStreamSendBufferPeer::EndOffset( - QuicStreamSendBuffer* send_buffer) { - return send_buffer->current_end_offset_; -} - // static QuicByteCount QuicStreamSendBufferPeer::TotalLength( QuicStreamSendBuffer* send_buffer) {
diff --git a/quiche/quic/test_tools/quic_stream_send_buffer_peer.h b/quiche/quic/test_tools/quic_stream_send_buffer_peer.h index 9792290..8969241 100644 --- a/quiche/quic/test_tools/quic_stream_send_buffer_peer.h +++ b/quiche/quic/test_tools/quic_stream_send_buffer_peer.h
@@ -19,8 +19,6 @@ static const BufferedSlice* CurrentWriteSlice( QuicStreamSendBuffer* send_buffer); - static QuicStreamOffset EndOffset(QuicStreamSendBuffer* send_buffer); - static QuicByteCount TotalLength(QuicStreamSendBuffer* send_buffer); static int32_t write_index(QuicStreamSendBuffer* send_buffer);