blob: 599c575b72342aca63eb91e08f06daa78256959f [file] [log] [blame]
// 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 "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"
#include "net/third_party/quiche/src/quic/platform/api/quic_logging.h"
#include "net/third_party/quiche/src/quic/platform/api/quic_str_cat.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)
: decoder_stream_error_delegate_(decoder_stream_error_delegate),
decoder_stream_receiver_(this),
maximum_blocked_streams_(0),
header_list_count_(0) {
DCHECK(decoder_stream_error_delegate_);
}
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(
QuicStreamId stream_id,
const spdy::SpdyHeaderBlock& header_list,
QpackBlockingManager::IndexSet* referred_indices,
QuicByteCount* encoder_stream_sent_byte_count) {
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.
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|.
QuicStringPiece name = header.first;
QuicStringPiece value = header.second;
bool is_static;
uint64_t index;
auto match_type =
header_table_.FindHeaderField(name, value, &is_static, &index);
switch (match_type) {
case QpackHeaderTable::MatchType::kNameAndValue:
if (is_static) {
// Refer to entry directly.
instructions.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 {
instructions.push_back(
EncodeIndexedHeaderField(is_static, index, referred_indices));
smallest_blocking_index = std::min(smallest_blocking_index, index);
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_blocking_index, index))) {
dynamic_table_insertion_blocked = true;
} else {
// 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);
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:
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<uint64_t>(
smallest_blocking_index, entry->InsertionIndex());
break;
}
// Emit literal field with name reference.
instructions.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_blocking_index, index))) {
dynamic_table_insertion_blocked = true;
} else {
// 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);
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:
// 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_blocking_index)) {
dynamic_table_insertion_blocked = true;
} else {
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<uint64_t>(smallest_blocking_index,
entry->InsertionIndex());
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.
instructions.push_back(EncodeLiteralHeaderField(name, value));
break;
}
}
const QuicByteCount sent_byte_count = encoder_stream_sender_.Flush();
if (encoder_stream_sent_byte_count) {
*encoder_stream_sent_byte_count = sent_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 instructions;
}
std::string QpackEncoder::SecondPassEncode(
QpackEncoder::Instructions instructions,
uint64_t required_insert_count) const {
QpackInstructionEncoder instruction_encoder;
std::string encoded_headers;
// Header block prefix.
QpackInstructionEncoder::Values values;
values.varint = QpackEncodeRequiredInsertCount(required_insert_count,
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 (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);
}
return encoded_headers;
}
std::string QpackEncoder::EncodeHeaderList(
QuicStreamId stream_id,
const spdy::SpdyHeaderBlock& 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 |instructions|.
Instructions instructions =
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(instructions), required_insert_count);
}
void QpackEncoder::SetMaximumDynamicTableCapacity(
uint64_t maximum_dynamic_table_capacity) {
header_table_.SetMaximumDynamicTableCapacity(maximum_dynamic_table_capacity);
}
void QpackEncoder::SetDynamicTableCapacity(uint64_t dynamic_table_capacity) {
encoder_stream_sender_.SendSetDynamicTableCapacity(dynamic_table_capacity);
encoder_stream_sender_.Flush();
bool success = header_table_.SetDynamicTableCapacity(dynamic_table_capacity);
DCHECK(success);
}
void QpackEncoder::SetMaximumBlockedStreams(uint64_t maximum_blocked_streams) {
maximum_blocked_streams_ = maximum_blocked_streams;
}
void QpackEncoder::OnInsertCountIncrement(uint64_t increment) {
if (increment == 0) {
decoder_stream_error_delegate_->OnDecoderStreamError(
"Invalid increment value 0.");
return;
}
if (!blocking_manager_.OnInsertCountIncrement(increment)) {
decoder_stream_error_delegate_->OnDecoderStreamError(
"Insert Count Increment instruction causes overflow.");
}
if (blocking_manager_.known_received_count() >
header_table_.inserted_entry_count()) {
decoder_stream_error_delegate_->OnDecoderStreamError(QuicStrCat(
"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)) {
decoder_stream_error_delegate_->OnDecoderStreamError(
QuicStrCat("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(QuicStringPiece error_message) {
decoder_stream_error_delegate_->OnDecoderStreamError(error_message);
}
} // namespace quic