| // Copyright (c) 2018 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/qpack/qpack_encoder.h" |
| |
| #include <algorithm> |
| #include <utility> |
| |
| #include "absl/strings/str_cat.h" |
| #include "absl/strings/string_view.h" |
| #include "quiche/quic/core/qpack/qpack_index_conversions.h" |
| #include "quiche/quic/core/qpack/qpack_instruction_encoder.h" |
| #include "quiche/quic/core/qpack/qpack_required_insert_count.h" |
| #include "quiche/quic/core/qpack/value_splitting_header_list.h" |
| #include "quiche/quic/platform/api/quic_flag_utils.h" |
| #include "quiche/quic/platform/api/quic_flags.h" |
| #include "quiche/quic/platform/api/quic_logging.h" |
| |
| 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, |
| HuffmanEncoding huffman_encoding) |
| : huffman_encoding_(huffman_encoding), |
| decoder_stream_error_delegate_(decoder_stream_error_delegate), |
| decoder_stream_receiver_(this), |
| encoder_stream_sender_(huffman_encoding), |
| maximum_blocked_streams_(0), |
| header_list_count_(0) { |
| QUICHE_DCHECK(decoder_stream_error_delegate_); |
| } |
| |
| QpackEncoder::~QpackEncoder() {} |
| |
| // static |
| QpackEncoder::Representation QpackEncoder::EncodeIndexedHeaderField( |
| bool is_static, uint64_t index, |
| QpackBlockingManager::IndexSet* referred_indices) { |
| // Add |index| to |*referred_indices| only if entry is in the dynamic table. |
| if (!is_static) { |
| referred_indices->insert(index); |
| } |
| return Representation::IndexedHeaderField(is_static, index); |
| } |
| |
| // static |
| QpackEncoder::Representation |
| QpackEncoder::EncodeLiteralHeaderFieldWithNameReference( |
| bool is_static, uint64_t index, absl::string_view value, |
| QpackBlockingManager::IndexSet* referred_indices) { |
| // Add |index| to |*referred_indices| only if entry is in the dynamic table. |
| if (!is_static) { |
| referred_indices->insert(index); |
| } |
| return Representation::LiteralHeaderFieldNameReference(is_static, index, |
| value); |
| } |
| |
| // static |
| QpackEncoder::Representation QpackEncoder::EncodeLiteralHeaderField( |
| absl::string_view name, absl::string_view value) { |
| return Representation::LiteralHeaderField(name, value); |
| } |
| |
| QpackEncoder::Representations QpackEncoder::FirstPassEncode( |
| QuicStreamId stream_id, const spdy::Http2HeaderBlock& header_list, |
| QpackBlockingManager::IndexSet* referred_indices, |
| QuicByteCount* encoder_stream_sent_byte_count) { |
| // If previous instructions are buffered in |encoder_stream_sender_|, |
| // do not count them towards the current header block. |
| const QuicByteCount initial_encoder_stream_buffered_byte_count = |
| encoder_stream_sender_.BufferedByteCount(); |
| |
| const bool can_write_to_encoder_stream = encoder_stream_sender_.CanWrite(); |
| |
| Representations representations; |
| representations.reserve(header_list.size()); |
| |
| // Entries with index larger than or equal to |known_received_count| are |
| // blocking. |
| const uint64_t known_received_count = |
| blocking_manager_.known_received_count(); |
| |
| // The index of the oldest entry that must not be evicted. Blocking entries |
| // must not be evicted. Also, unacknowledged entries must not be evicted, |
| // even if they have no outstanding references (see https://crbug.com/1441880 |
| // for more context). |
| uint64_t smallest_non_evictable_index = std::min( |
| blocking_manager_.smallest_blocking_index(), 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. |
| const bool blocking_allowed = blocking_manager_.blocking_allowed_on_stream( |
| stream_id, maximum_blocked_streams_); |
| |
| // Track events for histograms. |
| bool dynamic_table_insertion_blocked = false; |
| bool blocked_stream_limit_exhausted = false; |
| |
| for (const auto& header : ValueSplittingHeaderList(&header_list)) { |
| // These strings are owned by |header_list|. |
| absl::string_view name = header.first; |
| absl::string_view value = header.second; |
| |
| bool is_static; |
| uint64_t index; |
| |
| auto match_type = |
| header_table_.FindHeaderField(name, value, &is_static, &index); |
| |
| switch (match_type) { |
| case QpackEncoderHeaderTable::MatchType::kNameAndValue: |
| if (is_static) { |
| // Refer to entry directly. |
| representations.push_back( |
| EncodeIndexedHeaderField(is_static, index, referred_indices)); |
| |
| break; |
| } |
| |
| if (index >= draining_index) { |
| // If allowed, refer to entry directly. |
| if (!blocking_allowed && index >= known_received_count) { |
| blocked_stream_limit_exhausted = true; |
| } else { |
| representations.push_back( |
| EncodeIndexedHeaderField(is_static, index, referred_indices)); |
| smallest_non_evictable_index = |
| std::min(smallest_non_evictable_index, index); |
| header_table_.set_dynamic_table_entry_referenced(); |
| |
| break; |
| } |
| } else { |
| // Entry is draining, needs to be duplicated. |
| if (!blocking_allowed) { |
| blocked_stream_limit_exhausted = true; |
| } else if (QpackEntry::Size(name, value) > |
| header_table_.MaxInsertSizeWithoutEvictingGivenEntry( |
| std::min(smallest_non_evictable_index, index))) { |
| dynamic_table_insertion_blocked = true; |
| } else { |
| if (can_write_to_encoder_stream) { |
| // If allowed, duplicate entry and refer to it. |
| encoder_stream_sender_.SendDuplicate( |
| QpackAbsoluteIndexToEncoderStreamRelativeIndex( |
| index, header_table_.inserted_entry_count())); |
| uint64_t new_index = header_table_.InsertEntry(name, value); |
| representations.push_back(EncodeIndexedHeaderField( |
| is_static, new_index, referred_indices)); |
| smallest_non_evictable_index = |
| std::min(smallest_non_evictable_index, index); |
| header_table_.set_dynamic_table_entry_referenced(); |
| |
| 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. |
| representations.push_back(EncodeLiteralHeaderField(name, value)); |
| |
| break; |
| |
| case QpackEncoderHeaderTable::MatchType::kName: |
| if (is_static) { |
| if (blocking_allowed && |
| QpackEntry::Size(name, value) <= |
| header_table_.MaxInsertSizeWithoutEvictingGivenEntry( |
| smallest_non_evictable_index)) { |
| // If allowed, insert entry into dynamic table and refer to it. |
| if (can_write_to_encoder_stream) { |
| encoder_stream_sender_.SendInsertWithNameReference(is_static, |
| index, value); |
| uint64_t new_index = header_table_.InsertEntry(name, value); |
| representations.push_back(EncodeIndexedHeaderField( |
| /* is_static = */ false, new_index, referred_indices)); |
| smallest_non_evictable_index = |
| std::min<uint64_t>(smallest_non_evictable_index, new_index); |
| |
| break; |
| } |
| } |
| |
| // Emit literal field with name reference. |
| representations.push_back(EncodeLiteralHeaderFieldWithNameReference( |
| is_static, index, value, referred_indices)); |
| |
| break; |
| } |
| |
| if (!blocking_allowed) { |
| blocked_stream_limit_exhausted = true; |
| } else if (QpackEntry::Size(name, value) > |
| header_table_.MaxInsertSizeWithoutEvictingGivenEntry( |
| std::min(smallest_non_evictable_index, index))) { |
| dynamic_table_insertion_blocked = true; |
| } else { |
| // If allowed, insert entry with name reference and refer to it. |
| if (can_write_to_encoder_stream) { |
| encoder_stream_sender_.SendInsertWithNameReference( |
| is_static, |
| QpackAbsoluteIndexToEncoderStreamRelativeIndex( |
| index, header_table_.inserted_entry_count()), |
| value); |
| uint64_t new_index = header_table_.InsertEntry(name, value); |
| representations.push_back(EncodeIndexedHeaderField( |
| is_static, new_index, referred_indices)); |
| smallest_non_evictable_index = |
| std::min(smallest_non_evictable_index, index); |
| header_table_.set_dynamic_table_entry_referenced(); |
| |
| break; |
| } |
| } |
| |
| if ((blocking_allowed || index < known_received_count) && |
| index >= draining_index) { |
| // If allowed, refer to entry name directly, with literal value. |
| representations.push_back(EncodeLiteralHeaderFieldWithNameReference( |
| is_static, index, value, referred_indices)); |
| smallest_non_evictable_index = |
| std::min(smallest_non_evictable_index, index); |
| header_table_.set_dynamic_table_entry_referenced(); |
| |
| 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. |
| representations.push_back(EncodeLiteralHeaderField(name, value)); |
| |
| break; |
| |
| case QpackEncoderHeaderTable::MatchType::kNoMatch: |
| // If allowed, insert entry and refer to it. |
| if (!blocking_allowed) { |
| blocked_stream_limit_exhausted = true; |
| } else if (QpackEntry::Size(name, value) > |
| header_table_.MaxInsertSizeWithoutEvictingGivenEntry( |
| smallest_non_evictable_index)) { |
| dynamic_table_insertion_blocked = true; |
| } else { |
| if (can_write_to_encoder_stream) { |
| encoder_stream_sender_.SendInsertWithoutNameReference(name, value); |
| uint64_t new_index = header_table_.InsertEntry(name, value); |
| representations.push_back(EncodeIndexedHeaderField( |
| /* is_static = */ false, new_index, referred_indices)); |
| smallest_non_evictable_index = |
| std::min<uint64_t>(smallest_non_evictable_index, new_index); |
| |
| break; |
| } |
| } |
| |
| // Encode entry as string literals. |
| // TODO(b/112770235): Consider also adding to dynamic table to improve |
| // compression ratio for subsequent header blocks with peers that do not |
| // allow any blocked streams. |
| representations.push_back(EncodeLiteralHeaderField(name, value)); |
| |
| break; |
| } |
| } |
| |
| const QuicByteCount encoder_stream_buffered_byte_count = |
| encoder_stream_sender_.BufferedByteCount(); |
| QUICHE_DCHECK_GE(encoder_stream_buffered_byte_count, |
| initial_encoder_stream_buffered_byte_count); |
| |
| if (encoder_stream_sent_byte_count) { |
| *encoder_stream_sent_byte_count = |
| encoder_stream_buffered_byte_count - |
| initial_encoder_stream_buffered_byte_count; |
| } |
| if (can_write_to_encoder_stream) { |
| encoder_stream_sender_.Flush(); |
| } else { |
| QUICHE_DCHECK_EQ(encoder_stream_buffered_byte_count, |
| initial_encoder_stream_buffered_byte_count); |
| } |
| |
| ++header_list_count_; |
| |
| if (dynamic_table_insertion_blocked) { |
| QUIC_HISTOGRAM_COUNTS( |
| "QuicSession.Qpack.HeaderListCountWhenInsertionBlocked", |
| header_list_count_, /* min = */ 1, /* max = */ 1000, |
| /* bucket_count = */ 50, |
| "The ordinality of a header list within a connection during the " |
| "encoding of which at least one dynamic table insertion was " |
| "blocked."); |
| } else { |
| QUIC_HISTOGRAM_COUNTS( |
| "QuicSession.Qpack.HeaderListCountWhenInsertionNotBlocked", |
| header_list_count_, /* min = */ 1, /* max = */ 1000, |
| /* bucket_count = */ 50, |
| "The ordinality of a header list within a connection during the " |
| "encoding of which no dynamic table insertion was blocked."); |
| } |
| |
| if (blocked_stream_limit_exhausted) { |
| QUIC_HISTOGRAM_COUNTS( |
| "QuicSession.Qpack.HeaderListCountWhenBlockedStreamLimited", |
| header_list_count_, /* min = */ 1, /* max = */ 1000, |
| /* bucket_count = */ 50, |
| "The ordinality of a header list within a connection during the " |
| "encoding of which unacknowledged dynamic table entries could not be " |
| "referenced due to the limit on the number of blocked streams."); |
| } else { |
| QUIC_HISTOGRAM_COUNTS( |
| "QuicSession.Qpack.HeaderListCountWhenNotBlockedStreamLimited", |
| header_list_count_, /* min = */ 1, /* max = */ 1000, |
| /* bucket_count = */ 50, |
| "The ordinality of a header list within a connection during the " |
| "encoding of which the limit on the number of blocked streams did " |
| "not " |
| "prevent referencing unacknowledged dynamic table entries."); |
| } |
| |
| return representations; |
| } |
| |
| std::string QpackEncoder::SecondPassEncode( |
| QpackEncoder::Representations representations, |
| uint64_t required_insert_count) const { |
| QpackInstructionEncoder instruction_encoder(huffman_encoding_); |
| std::string encoded_headers; |
| |
| // Header block prefix. |
| instruction_encoder.Encode( |
| Representation::Prefix(QpackEncodeRequiredInsertCount( |
| required_insert_count, header_table_.max_entries())), |
| &encoded_headers); |
| |
| const uint64_t base = required_insert_count; |
| |
| for (auto& representation : representations) { |
| // Dynamic table references must be transformed from absolute to relative |
| // indices. |
| if ((representation.instruction() == QpackIndexedHeaderFieldInstruction() || |
| representation.instruction() == |
| QpackLiteralHeaderFieldNameReferenceInstruction()) && |
| !representation.s_bit()) { |
| representation.set_varint(QpackAbsoluteIndexToRequestStreamRelativeIndex( |
| representation.varint(), base)); |
| } |
| instruction_encoder.Encode(representation, &encoded_headers); |
| } |
| |
| return encoded_headers; |
| } |
| |
| std::string QpackEncoder::EncodeHeaderList( |
| QuicStreamId stream_id, const spdy::Http2HeaderBlock& header_list, |
| QuicByteCount* encoder_stream_sent_byte_count) { |
| // 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; |
| |
| // First pass: encode into |representations|. |
| Representations representations = |
| FirstPassEncode(stream_id, header_list, &referred_indices, |
| encoder_stream_sent_byte_count); |
| |
| 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(representations), required_insert_count); |
| } |
| |
| bool QpackEncoder::SetMaximumDynamicTableCapacity( |
| uint64_t maximum_dynamic_table_capacity) { |
| return header_table_.SetMaximumDynamicTableCapacity( |
| maximum_dynamic_table_capacity); |
| } |
| |
| void QpackEncoder::SetDynamicTableCapacity(uint64_t dynamic_table_capacity) { |
| encoder_stream_sender_.SendSetDynamicTableCapacity(dynamic_table_capacity); |
| // Do not flush encoder stream. This write can safely be delayed until more |
| // instructions are written. |
| |
| bool success = header_table_.SetDynamicTableCapacity(dynamic_table_capacity); |
| QUICHE_DCHECK(success); |
| } |
| |
| bool QpackEncoder::SetMaximumBlockedStreams(uint64_t maximum_blocked_streams) { |
| if (maximum_blocked_streams < maximum_blocked_streams_) { |
| return false; |
| } |
| maximum_blocked_streams_ = maximum_blocked_streams; |
| return true; |
| } |
| |
| void QpackEncoder::OnInsertCountIncrement(uint64_t increment) { |
| if (increment == 0) { |
| OnErrorDetected(QUIC_QPACK_DECODER_STREAM_INVALID_ZERO_INCREMENT, |
| "Invalid increment value 0."); |
| return; |
| } |
| |
| if (!blocking_manager_.OnInsertCountIncrement(increment)) { |
| OnErrorDetected(QUIC_QPACK_DECODER_STREAM_INCREMENT_OVERFLOW, |
| "Insert Count Increment instruction causes overflow."); |
| } |
| |
| if (blocking_manager_.known_received_count() > |
| header_table_.inserted_entry_count()) { |
| OnErrorDetected(QUIC_QPACK_DECODER_STREAM_IMPOSSIBLE_INSERT_COUNT, |
| absl::StrCat("Increment value ", increment, |
| " raises known received count to ", |
| blocking_manager_.known_received_count(), |
| " exceeding inserted entry count ", |
| header_table_.inserted_entry_count())); |
| } |
| } |
| |
| void QpackEncoder::OnHeaderAcknowledgement(QuicStreamId stream_id) { |
| if (!blocking_manager_.OnHeaderAcknowledgement(stream_id)) { |
| OnErrorDetected( |
| QUIC_QPACK_DECODER_STREAM_INCORRECT_ACKNOWLEDGEMENT, |
| absl::StrCat("Header Acknowledgement received for stream ", stream_id, |
| " with no outstanding header blocks.")); |
| } |
| } |
| |
| void QpackEncoder::OnStreamCancellation(QuicStreamId stream_id) { |
| blocking_manager_.OnStreamCancellation(stream_id); |
| } |
| |
| void QpackEncoder::OnErrorDetected(QuicErrorCode error_code, |
| absl::string_view error_message) { |
| decoder_stream_error_delegate_->OnDecoderStreamError(error_code, |
| error_message); |
| } |
| |
| } // namespace quic |
