Use dynamic table for QPACK encoding. gfe-relnote: n/a, change to QUIC v99-only code. Protected by existing disabled gfe2_reloadable_flag_quic_enable_version_99. PiperOrigin-RevId: 264499016 Change-Id: I64289eca7487d0e84764ef30f4b250ab45e01833
diff --git a/quic/core/qpack/qpack_encoder.cc b/quic/core/qpack/qpack_encoder.cc index b6be648..6485071 100644 --- a/quic/core/qpack/qpack_encoder.cc +++ b/quic/core/qpack/qpack_encoder.cc
@@ -4,9 +4,11 @@ #include "net/third_party/quiche/src/quic/core/qpack/qpack_encoder.h" +#include <algorithm> #include <utility> #include "net/third_party/quiche/src/quic/core/qpack/qpack_constants.h" +#include "net/third_party/quiche/src/quic/core/qpack/qpack_index_conversions.h" #include "net/third_party/quiche/src/quic/core/qpack/qpack_instruction_encoder.h" #include "net/third_party/quiche/src/quic/core/qpack/qpack_required_insert_count.h" #include "net/third_party/quiche/src/quic/core/qpack/value_splitting_header_list.h" @@ -16,6 +18,19 @@ namespace quic { +namespace { + +// Fraction to calculate draining index. The oldest |kDrainingFraction| entries +// will not be referenced in header blocks. A new entry (duplicate or literal +// with name reference) will be added to the dynamic table instead. This allows +// the number of references to the draining entry to go to zero faster, so that +// it can be evicted. See +// https://quicwg.org/base-drafts/draft-ietf-quic-qpack.html#avoiding-blocked-insertions. +// TODO(bnc): Fine tune. +const float kDrainingFraction = 0.25; + +} // anonymous namespace + QpackEncoder::QpackEncoder( DecoderStreamErrorDelegate* decoder_stream_error_delegate) : decoder_stream_error_delegate_(decoder_stream_error_delegate), @@ -26,12 +41,75 @@ QpackEncoder::~QpackEncoder() {} +// static +QpackEncoder::InstructionWithValues QpackEncoder::EncodeIndexedHeaderField( + bool is_static, + uint64_t index, + QpackBlockingManager::IndexSet* referred_indices) { + InstructionWithValues instruction{QpackIndexedHeaderFieldInstruction(), {}}; + instruction.values.s_bit = is_static; + instruction.values.varint = index; + // Add |index| to |*referred_indices| only if entry is in the dynamic table. + if (!is_static) { + referred_indices->insert(index); + } + return instruction; +} + +// static +QpackEncoder::InstructionWithValues +QpackEncoder::EncodeLiteralHeaderFieldWithNameReference( + bool is_static, + uint64_t index, + QuicStringPiece value, + QpackBlockingManager::IndexSet* referred_indices) { + InstructionWithValues instruction{ + QpackLiteralHeaderFieldNameReferenceInstruction(), {}}; + instruction.values.s_bit = is_static; + instruction.values.varint = index; + instruction.values.value = value; + // Add |index| to |*referred_indices| only if entry is in the dynamic table. + if (!is_static) { + referred_indices->insert(index); + } + return instruction; +} + +// static +QpackEncoder::InstructionWithValues QpackEncoder::EncodeLiteralHeaderField( + QuicStringPiece name, + QuicStringPiece value) { + InstructionWithValues instruction{QpackLiteralHeaderFieldInstruction(), {}}; + instruction.values.name = name; + instruction.values.value = value; + return instruction; +} + QpackEncoder::Instructions QpackEncoder::FirstPassEncode( - const spdy::SpdyHeaderBlock* header_list) { + const spdy::SpdyHeaderBlock* header_list, + QpackBlockingManager::IndexSet* referred_indices) { Instructions instructions; instructions.reserve(header_list->size()); + // The index of the oldest entry that must not be evicted. + uint64_t smallest_blocking_index = + blocking_manager_.smallest_blocking_index(); + // Entries with index larger than or equal to |known_received_count| are + // blocking. + const uint64_t known_received_count = + blocking_manager_.known_received_count(); + // Only entries with index greater than or equal to |draining_index| are + // allowed to be referenced. + const uint64_t draining_index = + header_table_.draining_index(kDrainingFraction); + // Blocking references are allowed if the number of blocked streams is less + // than the limit. + // TODO(b/112770235): Also allow blocking if given stream is already blocked. + const bool blocking_allowed = + maximum_blocked_streams_ > blocking_manager_.blocked_stream_count(); + for (const auto& header : ValueSplittingHeaderList(header_list)) { + // These strings are owned by |*header_list|. QuicStringPiece name = header.first; QuicStringPiece value = header.second; @@ -43,27 +121,136 @@ switch (match_type) { case QpackHeaderTable::MatchType::kNameAndValue: - DCHECK(is_static) << "Dynamic table entries not supported yet."; + if (is_static) { + // Refer to entry directly. + instructions.push_back( + EncodeIndexedHeaderField(is_static, index, referred_indices)); - instructions.push_back({QpackIndexedHeaderFieldInstruction(), {}}); - instructions.back().values.s_bit = is_static; - instructions.back().values.varint = index; + break; + } + + if (blocking_allowed || index < known_received_count) { + if (index >= draining_index) { + // If allowed, refer to entry directly. + instructions.push_back( + EncodeIndexedHeaderField(is_static, index, referred_indices)); + smallest_blocking_index = std::min(smallest_blocking_index, index); + + break; + } + + if (blocking_allowed && + QpackEntry::Size(name, value) <= + header_table_.MaxInsertSizeWithoutEvictingGivenEntry( + std::min(smallest_blocking_index, index))) { + // If allowed, duplicate entry and refer to it. + encoder_stream_sender_.SendDuplicate( + QpackAbsoluteIndexToEncoderStreamRelativeIndex( + index, header_table_.inserted_entry_count())); + auto entry = header_table_.InsertEntry(name, value); + blocking_manager_.OnReferenceSentOnEncoderStream( + entry->InsertionIndex(), index); + instructions.push_back(EncodeIndexedHeaderField( + is_static, entry->InsertionIndex(), referred_indices)); + smallest_blocking_index = std::min(smallest_blocking_index, index); + + break; + } + } + + // Encode entry as string literals. + // TODO(b/112770235): Use already acknowledged entry with lower index if + // exists. + // TODO(b/112770235): Use static entry name with literal value if + // dynamic entry exists but cannot be used. + instructions.push_back(EncodeLiteralHeaderField(name, value)); break; + case QpackHeaderTable::MatchType::kName: - DCHECK(is_static) << "Dynamic table entries not supported yet."; + if (is_static) { + if (blocking_allowed && + QpackEntry::Size(name, value) <= + header_table_.MaxInsertSizeWithoutEvictingGivenEntry( + smallest_blocking_index)) { + // If allowed, insert entry into dynamic table and refer to it. + encoder_stream_sender_.SendInsertWithNameReference(is_static, index, + value); + auto entry = header_table_.InsertEntry(name, value); + instructions.push_back(EncodeIndexedHeaderField( + /* is_static = */ false, entry->InsertionIndex(), + referred_indices)); + smallest_blocking_index = + std::min(smallest_blocking_index, entry->InsertionIndex()); - instructions.push_back( - {QpackLiteralHeaderFieldNameReferenceInstruction(), {}}); - instructions.back().values.s_bit = is_static; - instructions.back().values.varint = index; - instructions.back().values.value = value; + break; + } + + // Emit literal field with name reference. + instructions.push_back(EncodeLiteralHeaderFieldWithNameReference( + is_static, index, value, referred_indices)); + + break; + } + + if (blocking_allowed && + QpackEntry::Size(name, value) <= + header_table_.MaxInsertSizeWithoutEvictingGivenEntry( + std::min(smallest_blocking_index, index))) { + // If allowed, insert entry with name reference and refer to it. + encoder_stream_sender_.SendInsertWithNameReference( + is_static, + QpackAbsoluteIndexToEncoderStreamRelativeIndex( + index, header_table_.inserted_entry_count()), + value); + auto entry = header_table_.InsertEntry(name, value); + blocking_manager_.OnReferenceSentOnEncoderStream( + entry->InsertionIndex(), index); + instructions.push_back(EncodeIndexedHeaderField( + is_static, entry->InsertionIndex(), referred_indices)); + smallest_blocking_index = std::min(smallest_blocking_index, index); + + break; + } + + if ((blocking_allowed || index < known_received_count) && + index >= draining_index) { + // If allowed, refer to entry name directly, with literal value. + instructions.push_back(EncodeLiteralHeaderFieldWithNameReference( + is_static, index, value, referred_indices)); + smallest_blocking_index = std::min(smallest_blocking_index, index); + + break; + } + + // Encode entry as string literals. + // TODO(b/112770235): Use already acknowledged entry with lower index if + // exists. + // TODO(b/112770235): Use static entry name with literal value if + // dynamic entry exists but cannot be used. + instructions.push_back(EncodeLiteralHeaderField(name, value)); break; + case QpackHeaderTable::MatchType::kNoMatch: - instructions.push_back({QpackLiteralHeaderFieldInstruction(), {}}); - instructions.back().values.name = name; - instructions.back().values.value = value; + if (blocking_allowed && + QpackEntry::Size(name, value) <= + header_table_.MaxInsertSizeWithoutEvictingGivenEntry( + smallest_blocking_index)) { + // If allowed, insert entry and refer to it. + encoder_stream_sender_.SendInsertWithoutNameReference(name, value); + auto entry = header_table_.InsertEntry(name, value); + instructions.push_back(EncodeIndexedHeaderField( + /* is_static = */ false, entry->InsertionIndex(), + referred_indices)); + smallest_blocking_index = + std::min(smallest_blocking_index, entry->InsertionIndex()); + + break; + } + + // Encode entry as string literals. + instructions.push_back(EncodeLiteralHeaderField(name, value)); break; } @@ -84,11 +271,22 @@ header_table_.max_entries()); values.varint2 = 0; // Delta Base. values.s_bit = false; // Delta Base sign. + const uint64_t base = required_insert_count; instruction_encoder.Encode(QpackPrefixInstruction(), values, &encoded_headers); - for (const auto& instruction : instructions) { + for (auto& instruction : instructions) { + // Dynamic table references must be transformed from absolute to relative + // indices. + if ((instruction.instruction == QpackIndexedHeaderFieldInstruction() || + instruction.instruction == + QpackLiteralHeaderFieldNameReferenceInstruction()) && + !instruction.values.s_bit) { + instruction.values.varint = + QpackAbsoluteIndexToRequestStreamRelativeIndex( + instruction.values.varint, base); + } instruction_encoder.Encode(instruction.instruction, instruction.values, &encoded_headers); } @@ -97,14 +295,22 @@ } std::string QpackEncoder::EncodeHeaderList( - QuicStreamId /* stream_id */, + QuicStreamId stream_id, const spdy::SpdyHeaderBlock* header_list) { - // First pass: encode into |instructions|. - Instructions instructions = FirstPassEncode(header_list); + // Keep track of all dynamic table indices that this header block refers to so + // that it can be passed to QpackBlockingManager. + QpackBlockingManager::IndexSet referred_indices; - // TODO(bnc): Implement dynamic entries and set Required Insert Count - // accordingly. - const uint64_t required_insert_count = 0; + // First pass: encode into |instructions|. + Instructions instructions = FirstPassEncode(header_list, &referred_indices); + + const uint64_t required_insert_count = + referred_indices.empty() + ? 0 + : QpackBlockingManager::RequiredInsertCount(referred_indices); + if (!referred_indices.empty()) { + blocking_manager_.OnHeaderBlockSent(stream_id, std::move(referred_indices)); + } // Second pass. return SecondPassEncode(std::move(instructions), required_insert_count);
diff --git a/quic/core/qpack/qpack_encoder.h b/quic/core/qpack/qpack_encoder.h index a1b6427..55dd1e9 100644 --- a/quic/core/qpack/qpack_encoder.h +++ b/quic/core/qpack/qpack_encoder.h
@@ -50,6 +50,7 @@ ~QpackEncoder() override; // Encode a header list. + // TODO(bnc): Take |header_list| by const reference instead of pointer. std::string EncodeHeaderList(QuicStreamId stream_id, const spdy::SpdyHeaderBlock* header_list); @@ -97,13 +98,41 @@ }; using Instructions = std::vector<InstructionWithValues>; - // Perform first pass of two-pass encoding: represent each header field as a - // reference to an existing entry, the name of an existing entry with a - // literal value, or a literal name and value pair. - Instructions FirstPassEncode(const spdy::SpdyHeaderBlock* header_list); + // Generate indexed header field instruction + // and optionally update |*referred_indices|. + static InstructionWithValues EncodeIndexedHeaderField( + bool is_static, + uint64_t index, + QpackBlockingManager::IndexSet* referred_indices); - // Perform second pass of two-pass encoding: serialize representations - // generated in first pass. + // Generate literal header field with name reference instruction + // and optionally update |*referred_indices|. + static InstructionWithValues EncodeLiteralHeaderFieldWithNameReference( + bool is_static, + uint64_t index, + QuicStringPiece value, + QpackBlockingManager::IndexSet* referred_indices); + + // Generate literal header field instruction. + static InstructionWithValues EncodeLiteralHeaderField(QuicStringPiece name, + QuicStringPiece value); + + // Performs first pass of two-pass encoding: represent each header field in + // |*header_list| as a reference to an existing entry, the name of an existing + // entry with a literal value, or a literal name and value pair. Sends + // necessary instructions on the encoder stream. Records absolute indices of + // referred dynamic table entries in |*referred_indices|. Returns list of + // header field representations, with all dynamic table entries referred to + // with absolute indices. Returned Instructions object may have + // QuicStringPieces pointing to strings owned by |*header_list|. + // TODO(bnc): Take |header_list| by const reference instead of pointer. + Instructions FirstPassEncode( + const spdy::SpdyHeaderBlock* header_list, + QpackBlockingManager::IndexSet* referred_indices); + + // Performs second pass of two-pass encoding: serializes representations + // generated in first pass, transforming absolute indices of dynamic table + // entries to relative indices. std::string SecondPassEncode(Instructions instructions, uint64_t required_insert_count) const;
diff --git a/quic/core/qpack/qpack_encoder_test.cc b/quic/core/qpack/qpack_encoder_test.cc index 56cfe84..01452ab 100644 --- a/quic/core/qpack/qpack_encoder_test.cc +++ b/quic/core/qpack/qpack_encoder_test.cc
@@ -12,6 +12,7 @@ #include "net/third_party/quiche/src/quic/platform/api/quic_test.h" #include "net/third_party/quiche/src/quic/platform/api/quic_text_utils.h" +using ::testing::_; using ::testing::Eq; using ::testing::StrictMock; using ::testing::Values; @@ -180,6 +181,224 @@ encoder_.OnHeaderAcknowledgement(/* stream_id = */ 0); } +TEST_F(QpackEncoderTest, DynamicTable) { + encoder_.SetMaximumDynamicTableCapacity(4096); + encoder_.SetMaximumBlockedStreams(1); + + spdy::SpdyHeaderBlock header_list; + header_list["foo"] = "bar"; + header_list.AppendValueOrAddHeader("foo", + "baz"); // name matches dynamic entry + header_list["cookie"] = "baz"; // name matches static entry + + // Insert three entries into the dynamic table. + EXPECT_CALL(encoder_stream_sender_delegate_, + WriteStreamData(Eq(QuicTextUtils::HexDecode( + "62" // insert without name reference + "94e7" // Huffman-encoded name "foo" + "03626172")))); // value "bar" + EXPECT_CALL(encoder_stream_sender_delegate_, + WriteStreamData(Eq(QuicTextUtils::HexDecode( + "80" // insert with name reference, dynamic index 0 + "0362617a")))); // value "baz" + EXPECT_CALL(encoder_stream_sender_delegate_, + WriteStreamData(Eq(QuicTextUtils::HexDecode( + "c5" // insert with name reference, static index 5 + "0362617a")))); // value "baz" + + EXPECT_EQ(QuicTextUtils::HexDecode( + "0400" // prefix + "828180"), // dynamic entries with relative index 0, 1, and 2 + Encode(&header_list)); +} + +// There is no room in the dynamic table after inserting the first entry. +TEST_F(QpackEncoderTest, SmallDynamicTable) { + encoder_.SetMaximumDynamicTableCapacity(QpackEntry::Size("foo", "bar")); + encoder_.SetMaximumBlockedStreams(1); + + spdy::SpdyHeaderBlock header_list; + header_list["foo"] = "bar"; + header_list.AppendValueOrAddHeader("foo", + "baz"); // name matches dynamic entry + header_list["cookie"] = "baz"; // name matches static entry + header_list["bar"] = "baz"; // no match + + // Insert one entry into the dynamic table. + EXPECT_CALL(encoder_stream_sender_delegate_, + WriteStreamData(Eq(QuicTextUtils::HexDecode( + "62" // insert without name reference + "94e7" // Huffman-encoded name "foo" + "03626172")))); // value "bar" + + EXPECT_EQ(QuicTextUtils::HexDecode("0200" // prefix + "80" // dynamic entry 0 + "40" // reference to dynamic entry 0 name + "0362617a" // with literal value "baz" + "55" // reference to static entry 5 name + "0362617a" // with literal value "baz" + "23626172" // literal name "bar" + "0362617a"), // with literal value "baz" + Encode(&header_list)); +} + +TEST_F(QpackEncoderTest, BlockedStream) { + encoder_.SetMaximumDynamicTableCapacity(4096); + encoder_.SetMaximumBlockedStreams(1); + + spdy::SpdyHeaderBlock header_list1; + header_list1["foo"] = "bar"; + + // Insert one entry into the dynamic table. + EXPECT_CALL(encoder_stream_sender_delegate_, + WriteStreamData(Eq(QuicTextUtils::HexDecode( + "62" // insert without name reference + "94e7" // Huffman-encoded name "foo" + "03626172")))); // value "bar" + + EXPECT_EQ(QuicTextUtils::HexDecode("0200" // prefix + "80"), // dynamic entry 0 + encoder_.EncodeHeaderList(/* stream_id = */ 1, &header_list1)); + + // Stream 1 is blocked. Stream 2 is not allowed to block. + spdy::SpdyHeaderBlock header_list2; + header_list2["foo"] = "bar"; // name and value match dynamic entry + header_list2.AppendValueOrAddHeader("foo", + "baz"); // name matches dynamic entry + header_list2["cookie"] = "baz"; // name matches static entry + header_list2["bar"] = "baz"; // no match + + EXPECT_EQ(QuicTextUtils::HexDecode("0000" // prefix + "2a94e7" // literal name "foo" + "03626172" // with literal value "bar" + "2a94e7" // literal name "foo" + "0362617a" // with literal value "baz" + "55" // name of static entry 5 + "0362617a" // with literal value "baz" + "23626172" // literal name "bar" + "0362617a"), // with literal value "baz" + encoder_.EncodeHeaderList(/* stream_id = */ 2, &header_list2)); + + // Peer acknowledges receipt of one dynamic table entry. + // Stream 1 is no longer blocked. + encoder_.OnInsertCountIncrement(1); + + // Insert three entries into the dynamic table. + EXPECT_CALL(encoder_stream_sender_delegate_, + WriteStreamData(Eq(QuicTextUtils::HexDecode( + "80" // insert with name reference, dynamic index 0 + "0362617a")))); // value "baz" + EXPECT_CALL(encoder_stream_sender_delegate_, + WriteStreamData(Eq(QuicTextUtils::HexDecode( + "c5" // insert with name reference, static index 5 + "0362617a")))); // value "baz" + EXPECT_CALL(encoder_stream_sender_delegate_, + WriteStreamData(Eq(QuicTextUtils::HexDecode( + "43" // insert without name reference + "626172" // name "bar" + "0362617a")))); // value "baz" + EXPECT_EQ(QuicTextUtils::HexDecode("0500" // prefix + "83828180"), // dynamic entries + encoder_.EncodeHeaderList(/* stream_id = */ 3, &header_list2)); + + // Stream 3 is blocked. Stream 4 is not allowed to block, but it can + // reference already acknowledged dynamic entry 0. + EXPECT_EQ(QuicTextUtils::HexDecode("0200" // prefix + "80" // dynamic entry 0 + "2a94e7" // literal name "foo" + "0362617a" // with literal value "baz" + "2c21cfd4c5" // literal name "cookie" + "0362617a" // with literal value "baz" + "23626172" // literal name "bar" + "0362617a"), // with literal value "baz" + encoder_.EncodeHeaderList(/* stream_id = */ 4, &header_list2)); + + // Peer acknowledges receipt of two more dynamic table entries. + // Stream 3 is still blocked. + encoder_.OnInsertCountIncrement(2); + + // Stream 5 is not allowed to block, but it can reference already acknowledged + // dynamic entries 0, 1, and 2. + EXPECT_EQ(QuicTextUtils::HexDecode("0400" // prefix + "828180" // dynamic entries + "23626172" // literal name "bar" + "0362617a"), // with literal value "baz" + encoder_.EncodeHeaderList(/* stream_id = */ 5, &header_list2)); + + // Peer acknowledges decoding header block on stream 3. + // Stream 3 is not blocked any longer. + encoder_.OnHeaderAcknowledgement(3); + + EXPECT_EQ(QuicTextUtils::HexDecode("0500" // prefix + "83828180"), // dynamic entries + encoder_.EncodeHeaderList(/* stream_id = */ 6, &header_list2)); +} + +TEST_F(QpackEncoderTest, Draining) { + // TODO(b/112770235): Remove when already blocking stream can emit blocking + // references. + encoder_.SetMaximumBlockedStreams(2); + + spdy::SpdyHeaderBlock header_list1; + header_list1["one"] = "foo"; + header_list1["two"] = "foo"; + header_list1["three"] = "foo"; + header_list1["four"] = "foo"; + header_list1["five"] = "foo"; + header_list1["six"] = "foo"; + header_list1["seven"] = "foo"; + header_list1["eight"] = "foo"; + header_list1["nine"] = "foo"; + header_list1["ten"] = "foo"; + + // Make just enough room in the dynamic table for the header list plus the + // first entry duplicated. This will ensure that the oldest entries are + // draining. + uint64_t maximum_dynamic_table_capacity = 0; + for (const auto& header_field : header_list1) { + maximum_dynamic_table_capacity += + QpackEntry::Size(header_field.first, header_field.second); + } + maximum_dynamic_table_capacity += QpackEntry::Size("one", "foo"); + encoder_.SetMaximumDynamicTableCapacity(maximum_dynamic_table_capacity); + + // Insert ten entries into the dynamic table. + EXPECT_CALL(encoder_stream_sender_delegate_, WriteStreamData(_)).Times(10); + + EXPECT_EQ( + QuicTextUtils::HexDecode("0b00" // prefix + "89888786858483828180"), // dynamic entries + Encode(&header_list1)); + + // Entry is identical to oldest one, which is draining. It will be + // duplicated and referenced. + spdy::SpdyHeaderBlock header_list2; + header_list2["one"] = "foo"; + + // Duplicate oldest entry. + EXPECT_CALL(encoder_stream_sender_delegate_, + WriteStreamData(Eq(QuicTextUtils::HexDecode("09")))); + + EXPECT_EQ(QuicTextUtils::HexDecode("0c00" // prefix + "80"), // most recent dynamic table entry + Encode(&header_list2)); + + spdy::SpdyHeaderBlock header_list3; + // Entry is identical to second oldest one, which is draining. There is no + // room to duplicate, it will be encoded with string literals. + header_list3.AppendValueOrAddHeader("two", "foo"); + // Entry has name identical to second oldest one, which is draining. There is + // no room to insert new entry, it will be encoded with string literals. + header_list3.AppendValueOrAddHeader("two", "bar"); + + EXPECT_EQ(QuicTextUtils::HexDecode("0000" // prefix + "2374776f" // literal name "two" + "8294e7" // literal value "foo" + "2374776f" // literal name "two" + "03626172"), // literal value "bar" + Encode(&header_list3)); +} + } // namespace } // namespace test } // namespace quic