Blocked decoding part 2: QpackProgressiveDecoder.
gfe-relnote: n/a, QUIC v99-only change.
PiperOrigin-RevId: 257158970
Change-Id: If3aad9939945daf170042038978ab7739078a8bd
diff --git a/quic/core/qpack/qpack_decoder_test.cc b/quic/core/qpack/qpack_decoder_test.cc
index 185aab9..af3a6a2 100644
--- a/quic/core/qpack/qpack_decoder_test.cc
+++ b/quic/core/qpack/qpack_decoder_test.cc
@@ -14,6 +14,7 @@
#include "net/third_party/quiche/src/spdy/core/spdy_header_block.h"
using ::testing::Eq;
+using ::testing::Mock;
using ::testing::Sequence;
using ::testing::StrictMock;
using ::testing::Values;
@@ -40,17 +41,36 @@
qpack_decoder_.DecodeEncoderStreamData(data);
}
- void DecodeHeaderBlock(QuicStringPiece data) {
+ // Set up |progressive_decoder_|.
+ void StartDecoding() {
+ progressive_decoder_ =
+ qpack_decoder_.CreateProgressiveDecoder(/* stream_id = */ 1, &handler_);
+ }
+
+ // Pass header block data to QpackProgressiveDecoder::Decode()
+ // in fragments dictated by |fragment_mode_|.
+ void DecodeData(QuicStringPiece data) {
auto fragment_size_generator =
FragmentModeToFragmentSizeGenerator(fragment_mode_);
- auto progressive_decoder =
- qpack_decoder_.CreateProgressiveDecoder(/* stream_id = */ 1, &handler_);
while (!data.empty()) {
size_t fragment_size = std::min(fragment_size_generator(), data.size());
- progressive_decoder->Decode(data.substr(0, fragment_size));
+ progressive_decoder_->Decode(data.substr(0, fragment_size));
data = data.substr(fragment_size);
}
- progressive_decoder->EndHeaderBlock();
+ }
+
+ // Signal end of header block to QpackProgressiveDecoder.
+ void EndDecoding() {
+ progressive_decoder_->EndHeaderBlock();
+ // |progressive_decoder_| is kept alive so that it can
+ // handle callbacks later in case of blocked decoding.
+ }
+
+ // Decode an entire header block.
+ void DecodeHeaderBlock(QuicStringPiece data) {
+ StartDecoding();
+ DecodeData(data);
+ EndDecoding();
}
StrictMock<MockEncoderStreamErrorDelegate> encoder_stream_error_delegate_;
@@ -60,6 +80,7 @@
private:
QpackDecoder qpack_decoder_;
const FragmentMode fragment_mode_;
+ std::unique_ptr<QpackProgressiveDecoder> progressive_decoder_;
};
INSTANTIATE_TEST_SUITE_P(,
@@ -387,8 +408,8 @@
// This must cause the entry to be evicted.
DecodeEncoderStreamData(QuicTextUtils::HexDecode("3f01"));
- EXPECT_CALL(handler_,
- OnDecodingErrorDetected(Eq("Dynamic table entry not found.")));
+ EXPECT_CALL(handler_, OnDecodingErrorDetected(
+ Eq("Dynamic table entry already evicted.")));
DecodeHeaderBlock(QuicTextUtils::HexDecode(
"0200" // Required Insert Count 1 and Delta Base 0.
@@ -446,6 +467,9 @@
TEST_P(QpackDecoderTest, InvalidDynamicEntryWhenBaseIsZero) {
EXPECT_CALL(handler_, OnDecodingErrorDetected(Eq("Invalid relative index.")));
+ // Add literal entry with name "foo" and value "bar".
+ DecodeEncoderStreamData(QuicTextUtils::HexDecode("6294e703626172"));
+
DecodeHeaderBlock(QuicTextUtils::HexDecode(
"0280" // Required Insert Count is 1. Base 1 - 1 - 0 = 0 is explicitly
// permitted by the spec.
@@ -465,8 +489,36 @@
// Add literal entry with name "foo" and value "bar".
DecodeEncoderStreamData(QuicTextUtils::HexDecode("6294e703626172"));
- EXPECT_CALL(handler_,
- OnDecodingErrorDetected(Eq("Dynamic table entry not found.")));
+ EXPECT_CALL(handler_, OnDecodingErrorDetected(Eq("Invalid relative index.")));
+
+ DecodeHeaderBlock(QuicTextUtils::HexDecode(
+ "0200" // Required Insert Count 1 and Delta Base 0.
+ // Base is 1 + 0 = 1.
+ "81")); // Indexed Header Field instruction addressing relative index 1.
+ // This is absolute index -1, which is invalid.
+
+ EXPECT_CALL(handler_, OnDecodingErrorDetected(Eq("Invalid relative index.")));
+
+ DecodeHeaderBlock(QuicTextUtils::HexDecode(
+ "0200" // Required Insert Count 1 and Delta Base 0.
+ // Base is 1 + 0 = 1.
+ "4100")); // Literal Header Field with Name Reference instruction
+ // addressing relative index 1. This is absolute index -1,
+ // which is invalid.
+}
+
+TEST_P(QpackDecoderTest, EvictedDynamicTableEntry) {
+ // Update dynamic table capacity to 128.
+ DecodeEncoderStreamData(QuicTextUtils::HexDecode("3f61"));
+
+ // Add literal entry with name "foo" and value "bar", size 32 + 3 + 3 = 38.
+ // This fits in the table three times.
+ DecodeEncoderStreamData(QuicTextUtils::HexDecode("6294e703626172"));
+ // Duplicate entry four times. This evicts the first two instances.
+ DecodeEncoderStreamData(QuicTextUtils::HexDecode("00000000"));
+
+ EXPECT_CALL(handler_, OnDecodingErrorDetected(
+ Eq("Dynamic table entry already evicted.")));
DecodeHeaderBlock(QuicTextUtils::HexDecode(
"0500" // Required Insert Count 4 and Delta Base 0.
@@ -474,16 +526,8 @@
"82")); // Indexed Header Field instruction addressing relative index 2.
// This is absolute index 1. Such entry does not exist.
- EXPECT_CALL(handler_, OnDecodingErrorDetected(Eq("Invalid relative index.")));
-
- DecodeHeaderBlock(QuicTextUtils::HexDecode(
- "0500" // Required Insert Count 4 and Delta Base 0.
- // Base is 4 + 0 = 4.
- "84")); // Indexed Header Field instruction addressing relative index 4.
- // This is absolute index -1, which is invalid.
-
- EXPECT_CALL(handler_,
- OnDecodingErrorDetected(Eq("Dynamic table entry not found.")));
+ EXPECT_CALL(handler_, OnDecodingErrorDetected(
+ Eq("Dynamic table entry already evicted.")));
DecodeHeaderBlock(QuicTextUtils::HexDecode(
"0500" // Required Insert Count 4 and Delta Base 0.
@@ -492,22 +536,8 @@
// addressing relative index 2. This is absolute index 1. Such
// entry does not exist.
- EXPECT_CALL(handler_, OnDecodingErrorDetected(Eq("Invalid relative index.")));
-
- DecodeHeaderBlock(QuicTextUtils::HexDecode(
- "0500" // Required Insert Count 4 and Delta Base 0.
- // Base is 4 + 0 = 4.
- "4400")); // Literal Header Field with Name Reference instruction
- // addressing relative index 4. This is absolute index -1,
- // which is invalid.
-}
-
-TEST_P(QpackDecoderTest, InvalidDynamicEntryByPostBaseIndex) {
- // Add literal entry with name "foo" and value "bar".
- DecodeEncoderStreamData(QuicTextUtils::HexDecode("6294e703626172"));
-
- EXPECT_CALL(handler_,
- OnDecodingErrorDetected(Eq("Dynamic table entry not found.")));
+ EXPECT_CALL(handler_, OnDecodingErrorDetected(
+ Eq("Dynamic table entry already evicted.")));
DecodeHeaderBlock(QuicTextUtils::HexDecode(
"0380" // Required Insert Count 2 and Delta Base 0 with sign bit set.
@@ -516,8 +546,8 @@
// entry with post-base index 0, absolute index 1. Such entry
// does not exist.
- EXPECT_CALL(handler_,
- OnDecodingErrorDetected(Eq("Dynamic table entry not found.")));
+ EXPECT_CALL(handler_, OnDecodingErrorDetected(
+ Eq("Dynamic table entry already evicted.")));
DecodeHeaderBlock(QuicTextUtils::HexDecode(
"0380" // Required Insert Count 2 and Delta Base 0 with sign bit set.
@@ -590,6 +620,9 @@
}
TEST_P(QpackDecoderTest, NonZeroRequiredInsertCountButNoDynamicEntries) {
+ // Add literal entry with name "foo" and value "bar".
+ DecodeEncoderStreamData(QuicTextUtils::HexDecode("6294e703626172"));
+
EXPECT_CALL(handler_, OnHeaderDecoded(Eq(":method"), Eq("GET")));
EXPECT_CALL(handler_,
OnDecodingErrorDetected(Eq("Required Insert Count too large.")));
@@ -600,6 +633,9 @@
}
TEST_P(QpackDecoderTest, AddressEntryNotAllowedByRequiredInsertCount) {
+ // Add literal entry with name "foo" and value "bar".
+ DecodeEncoderStreamData(QuicTextUtils::HexDecode("6294e703626172"));
+
EXPECT_CALL(
handler_,
OnDecodingErrorDetected(
@@ -655,7 +691,9 @@
TEST_P(QpackDecoderTest, PromisedRequiredInsertCountLargerThanActual) {
// Add literal entry with name "foo" and value "bar".
DecodeEncoderStreamData(QuicTextUtils::HexDecode("6294e703626172"));
- // Duplicate entry.
+ // Duplicate entry twice so that decoding of header blocks with Required
+ // Insert Count not exceeding 3 is not blocked.
+ DecodeEncoderStreamData(QuicTextUtils::HexDecode("00"));
DecodeEncoderStreamData(QuicTextUtils::HexDecode("00"));
EXPECT_CALL(handler_, OnHeaderDecoded(Eq("foo"), Eq("bar")));
@@ -707,6 +745,86 @@
// count of 2, even though Required Insert Count is 3.
}
+TEST_P(QpackDecoderTest, BlockedDecoding) {
+ DecodeHeaderBlock(QuicTextUtils::HexDecode(
+ "0200" // Required Insert Count 1 and Delta Base 0.
+ // Base is 1 + 0 = 1.
+ "80")); // Indexed Header Field instruction addressing dynamic table
+ // entry with relative index 0, absolute index 0.
+
+ EXPECT_CALL(handler_, OnHeaderDecoded(Eq("foo"), Eq("bar")));
+ EXPECT_CALL(handler_, OnDecodingCompleted());
+ EXPECT_CALL(decoder_stream_sender_delegate_,
+ WriteStreamData(Eq(kHeaderAcknowledgement)));
+
+ // Add literal entry with name "foo" and value "bar".
+ DecodeEncoderStreamData(QuicTextUtils::HexDecode("6294e703626172"));
+}
+
+TEST_P(QpackDecoderTest, BlockedDecodingUnblockedBeforeEndOfHeaderBlock) {
+ StartDecoding();
+ DecodeData(QuicTextUtils::HexDecode(
+ "0200" // Required Insert Count 1 and Delta Base 0.
+ // Base is 1 + 0 = 1.
+ "80" // Indexed Header Field instruction addressing dynamic table
+ // entry with relative index 0, absolute index 0.
+ "d1")); // Static table entry with index 17.
+
+ // Add literal entry with name "foo" and value "bar". Decoding is now
+ // unblocked because dynamic table Insert Count reached the Required Insert
+ // Count of the header block. |handler_| methods are called immediately for
+ // the already consumed part of the header block.
+ EXPECT_CALL(handler_, OnHeaderDecoded(Eq("foo"), Eq("bar")));
+ EXPECT_CALL(handler_, OnHeaderDecoded(Eq(":method"), Eq("GET")));
+ DecodeEncoderStreamData(QuicTextUtils::HexDecode("6294e703626172"));
+ Mock::VerifyAndClearExpectations(&handler_);
+
+ // Rest of header block is processed by QpackProgressiveDecoder
+ // in the unblocked state.
+ EXPECT_CALL(handler_, OnHeaderDecoded(Eq("foo"), Eq("bar")));
+ EXPECT_CALL(handler_, OnHeaderDecoded(Eq(":scheme"), Eq("https")));
+ DecodeData(QuicTextUtils::HexDecode(
+ "80" // Indexed Header Field instruction addressing dynamic table
+ // entry with relative index 0, absolute index 0.
+ "d7")); // Static table entry with index 23.
+ Mock::VerifyAndClearExpectations(&handler_);
+
+ EXPECT_CALL(handler_, OnDecodingCompleted());
+ EXPECT_CALL(decoder_stream_sender_delegate_,
+ WriteStreamData(Eq(kHeaderAcknowledgement)));
+ EndDecoding();
+}
+
+// Make sure that Required Insert Count is compared to Insert Count,
+// not size of dynamic table.
+TEST_P(QpackDecoderTest, BlockedDecodingAndEvictedEntries) {
+ // Update dynamic table capacity to 128.
+ // At most three non-empty entries fit in the dynamic table.
+ DecodeEncoderStreamData(QuicTextUtils::HexDecode("3f61"));
+
+ StartDecoding();
+ DecodeHeaderBlock(QuicTextUtils::HexDecode(
+ "0700" // Required Insert Count 6 and Delta Base 0.
+ // Base is 6 + 0 = 6.
+ "80")); // Indexed Header Field instruction addressing dynamic table
+ // entry with relative index 0, absolute index 5.
+
+ // Add literal entry with name "foo" and value "bar".
+ DecodeEncoderStreamData(QuicTextUtils::HexDecode("6294e703626172"));
+
+ // Duplicate entry four times. This evicts the first two instances.
+ DecodeEncoderStreamData(QuicTextUtils::HexDecode("00000000"));
+
+ EXPECT_CALL(handler_, OnHeaderDecoded(Eq("foo"), Eq("baz")));
+ EXPECT_CALL(handler_, OnDecodingCompleted());
+ EXPECT_CALL(decoder_stream_sender_delegate_,
+ WriteStreamData(Eq(kHeaderAcknowledgement)));
+
+ // Add literal entry with name "foo" and value "bar".
+ // Insert Count is now 6, reaching Required Insert Count of the header block.
+ DecodeEncoderStreamData(QuicTextUtils::HexDecode("6294e70362617a"));
+}
+
} // namespace
} // namespace test
} // namespace quic
diff --git a/quic/core/qpack/qpack_progressive_decoder.cc b/quic/core/qpack/qpack_progressive_decoder.cc
index 5a60084..07e2091 100644
--- a/quic/core/qpack/qpack_progressive_decoder.cc
+++ b/quic/core/qpack/qpack_progressive_decoder.cc
@@ -8,7 +8,6 @@
#include <limits>
#include "net/third_party/quiche/src/quic/core/qpack/qpack_constants.h"
-#include "net/third_party/quiche/src/quic/core/qpack/qpack_header_table.h"
#include "net/third_party/quiche/src/quic/platform/api/quic_logging.h"
#include "net/third_party/quiche/src/quic/platform/api/quic_ptr_util.h"
@@ -30,6 +29,7 @@
base_(0),
required_insert_count_so_far_(0),
prefix_decoded_(false),
+ blocked_(false),
decoding_(true),
error_detected_(false) {}
@@ -93,6 +93,8 @@
// Decode prefix byte by byte until the first (and only) instruction is
// decoded.
while (!prefix_decoded_) {
+ DCHECK(!blocked_);
+
prefix_decoder_->Decode(data.substr(0, 1));
if (error_detected_) {
return;
@@ -104,38 +106,33 @@
}
}
- instruction_decoder_.Decode(data);
+ if (blocked_) {
+ buffer_.append(data.data(), data.size());
+ } else {
+ DCHECK(buffer_.empty());
+
+ instruction_decoder_.Decode(data);
+ }
}
void QpackProgressiveDecoder::EndHeaderBlock() {
DCHECK(decoding_);
decoding_ = false;
- if (error_detected_) {
- return;
+ if (!blocked_) {
+ FinishDecoding();
}
-
- if (!instruction_decoder_.AtInstructionBoundary()) {
- OnError("Incomplete header block.");
- return;
- }
-
- if (!prefix_decoded_) {
- OnError("Incomplete header data prefix.");
- return;
- }
-
- if (required_insert_count_ != required_insert_count_so_far_) {
- OnError("Required Insert Count too large.");
- return;
- }
-
- decoder_stream_sender_->SendHeaderAcknowledgement(stream_id_);
- handler_->OnDecodingCompleted();
}
bool QpackProgressiveDecoder::OnInstructionDecoded(
const QpackInstruction* instruction) {
+ if (instruction == QpackPrefixInstruction()) {
+ return DoPrefixInstruction();
+ }
+
+ DCHECK(prefix_decoded_);
+ DCHECK_LE(required_insert_count_, header_table_->inserted_entry_count());
+
if (instruction == QpackIndexedHeaderFieldInstruction()) {
return DoIndexedHeaderFieldInstruction();
}
@@ -148,11 +145,8 @@
if (instruction == QpackLiteralHeaderFieldPostBaseInstruction()) {
return DoLiteralHeaderFieldPostBaseInstruction();
}
- if (instruction == QpackLiteralHeaderFieldInstruction()) {
- return DoLiteralHeaderFieldInstruction();
- }
- DCHECK_EQ(instruction, QpackPrefixInstruction());
- return DoPrefixInstruction();
+ DCHECK_EQ(instruction, QpackLiteralHeaderFieldInstruction());
+ return DoLiteralHeaderFieldInstruction();
}
void QpackProgressiveDecoder::OnError(QuicStringPiece error_message) {
@@ -162,6 +156,21 @@
handler_->OnDecodingErrorDetected(error_message);
}
+void QpackProgressiveDecoder::OnInsertCountReachedThreshold() {
+ DCHECK(blocked_);
+
+ if (!buffer_.empty()) {
+ instruction_decoder_.Decode(buffer_);
+ buffer_.clear();
+ }
+
+ blocked_ = false;
+
+ if (!decoding_) {
+ FinishDecoding();
+ }
+}
+
bool QpackProgressiveDecoder::DoIndexedHeaderFieldInstruction() {
if (!instruction_decoder_.s_bit()) {
uint64_t absolute_index;
@@ -183,7 +192,7 @@
auto entry =
header_table_->LookupEntry(/* is_static = */ false, absolute_index);
if (!entry) {
- OnError("Dynamic table entry not found.");
+ OnError("Dynamic table entry already evicted.");
return false;
}
@@ -222,7 +231,7 @@
auto entry =
header_table_->LookupEntry(/* is_static = */ false, absolute_index);
if (!entry) {
- OnError("Dynamic table entry not found.");
+ OnError("Dynamic table entry already evicted.");
return false;
}
@@ -251,7 +260,7 @@
auto entry =
header_table_->LookupEntry(/* is_static = */ false, absolute_index);
if (!entry) {
- OnError("Dynamic table entry not found.");
+ OnError("Dynamic table entry already evicted.");
return false;
}
@@ -290,7 +299,7 @@
auto entry =
header_table_->LookupEntry(/* is_static = */ false, absolute_index);
if (!entry) {
- OnError("Dynamic table entry not found.");
+ OnError("Dynamic table entry already evicted.");
return false;
}
@@ -324,9 +333,42 @@
prefix_decoded_ = true;
+ if (required_insert_count_ > header_table_->inserted_entry_count()) {
+ blocked_ = true;
+ header_table_->RegisterObserver(this, required_insert_count_);
+ }
+
return true;
}
+void QpackProgressiveDecoder::FinishDecoding() {
+ DCHECK(buffer_.empty());
+ DCHECK(!blocked_);
+ DCHECK(!decoding_);
+
+ if (error_detected_) {
+ return;
+ }
+
+ if (!instruction_decoder_.AtInstructionBoundary()) {
+ OnError("Incomplete header block.");
+ return;
+ }
+
+ if (!prefix_decoded_) {
+ OnError("Incomplete header data prefix.");
+ return;
+ }
+
+ if (required_insert_count_ != required_insert_count_so_far_) {
+ OnError("Required Insert Count too large.");
+ return;
+ }
+
+ decoder_stream_sender_->SendHeaderAcknowledgement(stream_id_);
+ handler_->OnDecodingCompleted();
+}
+
bool QpackProgressiveDecoder::DeltaBaseToBase(bool sign,
uint64_t delta_base,
uint64_t* base) {
diff --git a/quic/core/qpack/qpack_progressive_decoder.h b/quic/core/qpack/qpack_progressive_decoder.h
index 52adf45..c2e8f87 100644
--- a/quic/core/qpack/qpack_progressive_decoder.h
+++ b/quic/core/qpack/qpack_progressive_decoder.h
@@ -11,6 +11,7 @@
#include "net/third_party/quiche/src/quic/core/qpack/qpack_decoder_stream_sender.h"
#include "net/third_party/quiche/src/quic/core/qpack/qpack_encoder_stream_receiver.h"
+#include "net/third_party/quiche/src/quic/core/qpack/qpack_header_table.h"
#include "net/third_party/quiche/src/quic/core/qpack/qpack_instruction_decoder.h"
#include "net/third_party/quiche/src/quic/core/quic_types.h"
#include "net/third_party/quiche/src/quic/platform/api/quic_export.h"
@@ -22,7 +23,8 @@
// Class to decode a single header block.
class QUIC_EXPORT_PRIVATE QpackProgressiveDecoder
- : public QpackInstructionDecoder::Delegate {
+ : public QpackInstructionDecoder::Delegate,
+ public QpackHeaderTable::Observer {
public:
// Interface for receiving decoded header block from the decoder.
class QUIC_EXPORT_PRIVATE HeadersHandlerInterface {
@@ -39,7 +41,7 @@
// The decoder will not access the handler after this call.
// Note that this method might not be called synchronously when the header
// block is received on the wire, in case decoding is blocked on receiving
- // entries on the encoder stream. TODO(bnc): Implement blocked decoding.
+ // entries on the encoder stream.
virtual void OnDecodingCompleted() = 0;
// Called when a decoding error has occurred. No other methods will be
@@ -76,6 +78,9 @@
bool OnInstructionDecoded(const QpackInstruction* instruction) override;
void OnError(QuicStringPiece error_message) override;
+ // QpackHeaderTable::Observer implementation.
+ void OnInsertCountReachedThreshold() override;
+
private:
bool DoIndexedHeaderFieldInstruction();
bool DoIndexedHeaderFieldPostBaseInstruction();
@@ -84,6 +89,9 @@
bool DoLiteralHeaderFieldInstruction();
bool DoPrefixInstruction();
+ // Called as soon as EndHeaderBlock() is called and decoding is not blocked.
+ void FinishDecoding();
+
// Calculates Base from |required_insert_count_|, which must be set before
// calling this method, and sign bit and Delta Base in the Header Data Prefix,
// which are passed in as arguments. Returns true on success, false on
@@ -110,7 +118,7 @@
std::unique_ptr<QpackInstructionDecoder> prefix_decoder_;
QpackInstructionDecoder instruction_decoder_;
- const QpackHeaderTable* const header_table_;
+ QpackHeaderTable* const header_table_;
QpackDecoderStreamSender* const decoder_stream_sender_;
HeadersHandlerInterface* const handler_;
@@ -128,6 +136,12 @@
// False until prefix is fully read and decoded.
bool prefix_decoded_;
+ // True if waiting for dynamic table entries to arrive.
+ bool blocked_;
+
+ // Buffer the entire header block after the prefix while decoding is blocked.
+ std::string buffer_;
+
// True until EndHeaderBlock() is called.
bool decoding_;