1 // Copyright (c) 2018 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "quiche/quic/core/qpack/qpack_encoder.h"
6
7 #include <algorithm>
8 #include <utility>
9
10 #include "absl/strings/str_cat.h"
11 #include "absl/strings/string_view.h"
12 #include "quiche/quic/core/qpack/qpack_index_conversions.h"
13 #include "quiche/quic/core/qpack/qpack_instruction_encoder.h"
14 #include "quiche/quic/core/qpack/qpack_required_insert_count.h"
15 #include "quiche/quic/core/qpack/value_splitting_header_list.h"
16 #include "quiche/quic/platform/api/quic_flag_utils.h"
17 #include "quiche/quic/platform/api/quic_flags.h"
18 #include "quiche/quic/platform/api/quic_logging.h"
19
20 namespace quic {
21
22 namespace {
23
24 // Fraction to calculate draining index. The oldest |kDrainingFraction| entries
25 // will not be referenced in header blocks. A new entry (duplicate or literal
26 // with name reference) will be added to the dynamic table instead. This allows
27 // the number of references to the draining entry to go to zero faster, so that
28 // it can be evicted. See
29 // https://quicwg.org/base-drafts/draft-ietf-quic-qpack.html#avoiding-blocked-insertions.
30 // TODO(bnc): Fine tune.
31 const float kDrainingFraction = 0.25;
32
33 } // anonymous namespace
34
QpackEncoder(DecoderStreamErrorDelegate * decoder_stream_error_delegate,HuffmanEncoding huffman_encoding)35 QpackEncoder::QpackEncoder(
36 DecoderStreamErrorDelegate* decoder_stream_error_delegate,
37 HuffmanEncoding huffman_encoding)
38 : huffman_encoding_(huffman_encoding),
39 decoder_stream_error_delegate_(decoder_stream_error_delegate),
40 decoder_stream_receiver_(this),
41 encoder_stream_sender_(huffman_encoding),
42 maximum_blocked_streams_(0),
43 header_list_count_(0) {
44 QUICHE_DCHECK(decoder_stream_error_delegate_);
45 }
46
~QpackEncoder()47 QpackEncoder::~QpackEncoder() {}
48
49 // static
EncodeIndexedHeaderField(bool is_static,uint64_t index,QpackBlockingManager::IndexSet * referred_indices)50 QpackEncoder::Representation QpackEncoder::EncodeIndexedHeaderField(
51 bool is_static, uint64_t index,
52 QpackBlockingManager::IndexSet* referred_indices) {
53 // Add |index| to |*referred_indices| only if entry is in the dynamic table.
54 if (!is_static) {
55 referred_indices->insert(index);
56 }
57 return Representation::IndexedHeaderField(is_static, index);
58 }
59
60 // static
61 QpackEncoder::Representation
EncodeLiteralHeaderFieldWithNameReference(bool is_static,uint64_t index,absl::string_view value,QpackBlockingManager::IndexSet * referred_indices)62 QpackEncoder::EncodeLiteralHeaderFieldWithNameReference(
63 bool is_static, uint64_t index, absl::string_view value,
64 QpackBlockingManager::IndexSet* referred_indices) {
65 // Add |index| to |*referred_indices| only if entry is in the dynamic table.
66 if (!is_static) {
67 referred_indices->insert(index);
68 }
69 return Representation::LiteralHeaderFieldNameReference(is_static, index,
70 value);
71 }
72
73 // static
EncodeLiteralHeaderField(absl::string_view name,absl::string_view value)74 QpackEncoder::Representation QpackEncoder::EncodeLiteralHeaderField(
75 absl::string_view name, absl::string_view value) {
76 return Representation::LiteralHeaderField(name, value);
77 }
78
FirstPassEncode(QuicStreamId stream_id,const spdy::Http2HeaderBlock & header_list,QpackBlockingManager::IndexSet * referred_indices,QuicByteCount * encoder_stream_sent_byte_count)79 QpackEncoder::Representations QpackEncoder::FirstPassEncode(
80 QuicStreamId stream_id, const spdy::Http2HeaderBlock& header_list,
81 QpackBlockingManager::IndexSet* referred_indices,
82 QuicByteCount* encoder_stream_sent_byte_count) {
83 // If previous instructions are buffered in |encoder_stream_sender_|,
84 // do not count them towards the current header block.
85 const QuicByteCount initial_encoder_stream_buffered_byte_count =
86 encoder_stream_sender_.BufferedByteCount();
87
88 const bool can_write_to_encoder_stream = encoder_stream_sender_.CanWrite();
89
90 Representations representations;
91 representations.reserve(header_list.size());
92
93 // Entries with index larger than or equal to |known_received_count| are
94 // blocking.
95 const uint64_t known_received_count =
96 blocking_manager_.known_received_count();
97
98 // The index of the oldest entry that must not be evicted. Blocking entries
99 // must not be evicted. Also, unacknowledged entries must not be evicted,
100 // even if they have no outstanding references (see https://crbug.com/1441880
101 // for more context).
102 uint64_t smallest_non_evictable_index = std::min(
103 blocking_manager_.smallest_blocking_index(), known_received_count);
104
105 // Only entries with index greater than or equal to |draining_index| are
106 // allowed to be referenced.
107 const uint64_t draining_index =
108 header_table_.draining_index(kDrainingFraction);
109 // Blocking references are allowed if the number of blocked streams is less
110 // than the limit.
111 const bool blocking_allowed = blocking_manager_.blocking_allowed_on_stream(
112 stream_id, maximum_blocked_streams_);
113
114 // Track events for histograms.
115 bool dynamic_table_insertion_blocked = false;
116 bool blocked_stream_limit_exhausted = false;
117
118 for (const auto& header : ValueSplittingHeaderList(&header_list)) {
119 // These strings are owned by |header_list|.
120 absl::string_view name = header.first;
121 absl::string_view value = header.second;
122
123 bool is_static;
124 uint64_t index;
125
126 auto match_type =
127 header_table_.FindHeaderField(name, value, &is_static, &index);
128
129 switch (match_type) {
130 case QpackEncoderHeaderTable::MatchType::kNameAndValue:
131 if (is_static) {
132 // Refer to entry directly.
133 representations.push_back(
134 EncodeIndexedHeaderField(is_static, index, referred_indices));
135
136 break;
137 }
138
139 if (index >= draining_index) {
140 // If allowed, refer to entry directly.
141 if (!blocking_allowed && index >= known_received_count) {
142 blocked_stream_limit_exhausted = true;
143 } else {
144 representations.push_back(
145 EncodeIndexedHeaderField(is_static, index, referred_indices));
146 smallest_non_evictable_index =
147 std::min(smallest_non_evictable_index, index);
148 header_table_.set_dynamic_table_entry_referenced();
149
150 break;
151 }
152 } else {
153 // Entry is draining, needs to be duplicated.
154 if (!blocking_allowed) {
155 blocked_stream_limit_exhausted = true;
156 } else if (QpackEntry::Size(name, value) >
157 header_table_.MaxInsertSizeWithoutEvictingGivenEntry(
158 std::min(smallest_non_evictable_index, index))) {
159 dynamic_table_insertion_blocked = true;
160 } else {
161 if (can_write_to_encoder_stream) {
162 // If allowed, duplicate entry and refer to it.
163 encoder_stream_sender_.SendDuplicate(
164 QpackAbsoluteIndexToEncoderStreamRelativeIndex(
165 index, header_table_.inserted_entry_count()));
166 uint64_t new_index = header_table_.InsertEntry(name, value);
167 representations.push_back(EncodeIndexedHeaderField(
168 is_static, new_index, referred_indices));
169 smallest_non_evictable_index =
170 std::min(smallest_non_evictable_index, index);
171 header_table_.set_dynamic_table_entry_referenced();
172
173 break;
174 }
175 }
176 }
177
178 // Encode entry as string literals.
179 // TODO(b/112770235): Use already acknowledged entry with lower index if
180 // exists.
181 // TODO(b/112770235): Use static entry name with literal value if
182 // dynamic entry exists but cannot be used.
183 representations.push_back(EncodeLiteralHeaderField(name, value));
184
185 break;
186
187 case QpackEncoderHeaderTable::MatchType::kName:
188 if (is_static) {
189 if (blocking_allowed &&
190 QpackEntry::Size(name, value) <=
191 header_table_.MaxInsertSizeWithoutEvictingGivenEntry(
192 smallest_non_evictable_index)) {
193 // If allowed, insert entry into dynamic table and refer to it.
194 if (can_write_to_encoder_stream) {
195 encoder_stream_sender_.SendInsertWithNameReference(is_static,
196 index, value);
197 uint64_t new_index = header_table_.InsertEntry(name, value);
198 representations.push_back(EncodeIndexedHeaderField(
199 /* is_static = */ false, new_index, referred_indices));
200 smallest_non_evictable_index =
201 std::min<uint64_t>(smallest_non_evictable_index, new_index);
202
203 break;
204 }
205 }
206
207 // Emit literal field with name reference.
208 representations.push_back(EncodeLiteralHeaderFieldWithNameReference(
209 is_static, index, value, referred_indices));
210
211 break;
212 }
213
214 if (!blocking_allowed) {
215 blocked_stream_limit_exhausted = true;
216 } else if (QpackEntry::Size(name, value) >
217 header_table_.MaxInsertSizeWithoutEvictingGivenEntry(
218 std::min(smallest_non_evictable_index, index))) {
219 dynamic_table_insertion_blocked = true;
220 } else {
221 // If allowed, insert entry with name reference and refer to it.
222 if (can_write_to_encoder_stream) {
223 encoder_stream_sender_.SendInsertWithNameReference(
224 is_static,
225 QpackAbsoluteIndexToEncoderStreamRelativeIndex(
226 index, header_table_.inserted_entry_count()),
227 value);
228 uint64_t new_index = header_table_.InsertEntry(name, value);
229 representations.push_back(EncodeIndexedHeaderField(
230 is_static, new_index, referred_indices));
231 smallest_non_evictable_index =
232 std::min(smallest_non_evictable_index, index);
233 header_table_.set_dynamic_table_entry_referenced();
234
235 break;
236 }
237 }
238
239 if ((blocking_allowed || index < known_received_count) &&
240 index >= draining_index) {
241 // If allowed, refer to entry name directly, with literal value.
242 representations.push_back(EncodeLiteralHeaderFieldWithNameReference(
243 is_static, index, value, referred_indices));
244 smallest_non_evictable_index =
245 std::min(smallest_non_evictable_index, index);
246 header_table_.set_dynamic_table_entry_referenced();
247
248 break;
249 }
250
251 // Encode entry as string literals.
252 // TODO(b/112770235): Use already acknowledged entry with lower index if
253 // exists.
254 // TODO(b/112770235): Use static entry name with literal value if
255 // dynamic entry exists but cannot be used.
256 representations.push_back(EncodeLiteralHeaderField(name, value));
257
258 break;
259
260 case QpackEncoderHeaderTable::MatchType::kNoMatch:
261 // If allowed, insert entry and refer to it.
262 if (!blocking_allowed) {
263 blocked_stream_limit_exhausted = true;
264 } else if (QpackEntry::Size(name, value) >
265 header_table_.MaxInsertSizeWithoutEvictingGivenEntry(
266 smallest_non_evictable_index)) {
267 dynamic_table_insertion_blocked = true;
268 } else {
269 if (can_write_to_encoder_stream) {
270 encoder_stream_sender_.SendInsertWithoutNameReference(name, value);
271 uint64_t new_index = header_table_.InsertEntry(name, value);
272 representations.push_back(EncodeIndexedHeaderField(
273 /* is_static = */ false, new_index, referred_indices));
274 smallest_non_evictable_index =
275 std::min<uint64_t>(smallest_non_evictable_index, new_index);
276
277 break;
278 }
279 }
280
281 // Encode entry as string literals.
282 // TODO(b/112770235): Consider also adding to dynamic table to improve
283 // compression ratio for subsequent header blocks with peers that do not
284 // allow any blocked streams.
285 representations.push_back(EncodeLiteralHeaderField(name, value));
286
287 break;
288 }
289 }
290
291 const QuicByteCount encoder_stream_buffered_byte_count =
292 encoder_stream_sender_.BufferedByteCount();
293 QUICHE_DCHECK_GE(encoder_stream_buffered_byte_count,
294 initial_encoder_stream_buffered_byte_count);
295
296 if (encoder_stream_sent_byte_count) {
297 *encoder_stream_sent_byte_count =
298 encoder_stream_buffered_byte_count -
299 initial_encoder_stream_buffered_byte_count;
300 }
301 if (can_write_to_encoder_stream) {
302 encoder_stream_sender_.Flush();
303 } else {
304 QUICHE_DCHECK_EQ(encoder_stream_buffered_byte_count,
305 initial_encoder_stream_buffered_byte_count);
306 }
307
308 ++header_list_count_;
309
310 if (dynamic_table_insertion_blocked) {
311 QUIC_HISTOGRAM_COUNTS(
312 "QuicSession.Qpack.HeaderListCountWhenInsertionBlocked",
313 header_list_count_, /* min = */ 1, /* max = */ 1000,
314 /* bucket_count = */ 50,
315 "The ordinality of a header list within a connection during the "
316 "encoding of which at least one dynamic table insertion was "
317 "blocked.");
318 } else {
319 QUIC_HISTOGRAM_COUNTS(
320 "QuicSession.Qpack.HeaderListCountWhenInsertionNotBlocked",
321 header_list_count_, /* min = */ 1, /* max = */ 1000,
322 /* bucket_count = */ 50,
323 "The ordinality of a header list within a connection during the "
324 "encoding of which no dynamic table insertion was blocked.");
325 }
326
327 if (blocked_stream_limit_exhausted) {
328 QUIC_HISTOGRAM_COUNTS(
329 "QuicSession.Qpack.HeaderListCountWhenBlockedStreamLimited",
330 header_list_count_, /* min = */ 1, /* max = */ 1000,
331 /* bucket_count = */ 50,
332 "The ordinality of a header list within a connection during the "
333 "encoding of which unacknowledged dynamic table entries could not be "
334 "referenced due to the limit on the number of blocked streams.");
335 } else {
336 QUIC_HISTOGRAM_COUNTS(
337 "QuicSession.Qpack.HeaderListCountWhenNotBlockedStreamLimited",
338 header_list_count_, /* min = */ 1, /* max = */ 1000,
339 /* bucket_count = */ 50,
340 "The ordinality of a header list within a connection during the "
341 "encoding of which the limit on the number of blocked streams did "
342 "not "
343 "prevent referencing unacknowledged dynamic table entries.");
344 }
345
346 return representations;
347 }
348
SecondPassEncode(QpackEncoder::Representations representations,uint64_t required_insert_count) const349 std::string QpackEncoder::SecondPassEncode(
350 QpackEncoder::Representations representations,
351 uint64_t required_insert_count) const {
352 QpackInstructionEncoder instruction_encoder(huffman_encoding_);
353 std::string encoded_headers;
354
355 // Header block prefix.
356 instruction_encoder.Encode(
357 Representation::Prefix(QpackEncodeRequiredInsertCount(
358 required_insert_count, header_table_.max_entries())),
359 &encoded_headers);
360
361 const uint64_t base = required_insert_count;
362
363 for (auto& representation : representations) {
364 // Dynamic table references must be transformed from absolute to relative
365 // indices.
366 if ((representation.instruction() == QpackIndexedHeaderFieldInstruction() ||
367 representation.instruction() ==
368 QpackLiteralHeaderFieldNameReferenceInstruction()) &&
369 !representation.s_bit()) {
370 representation.set_varint(QpackAbsoluteIndexToRequestStreamRelativeIndex(
371 representation.varint(), base));
372 }
373 instruction_encoder.Encode(representation, &encoded_headers);
374 }
375
376 return encoded_headers;
377 }
378
EncodeHeaderList(QuicStreamId stream_id,const spdy::Http2HeaderBlock & header_list,QuicByteCount * encoder_stream_sent_byte_count)379 std::string QpackEncoder::EncodeHeaderList(
380 QuicStreamId stream_id, const spdy::Http2HeaderBlock& header_list,
381 QuicByteCount* encoder_stream_sent_byte_count) {
382 // Keep track of all dynamic table indices that this header block refers to so
383 // that it can be passed to QpackBlockingManager.
384 QpackBlockingManager::IndexSet referred_indices;
385
386 // First pass: encode into |representations|.
387 Representations representations =
388 FirstPassEncode(stream_id, header_list, &referred_indices,
389 encoder_stream_sent_byte_count);
390
391 const uint64_t required_insert_count =
392 referred_indices.empty()
393 ? 0
394 : QpackBlockingManager::RequiredInsertCount(referred_indices);
395 if (!referred_indices.empty()) {
396 blocking_manager_.OnHeaderBlockSent(stream_id, std::move(referred_indices));
397 }
398
399 // Second pass.
400 return SecondPassEncode(std::move(representations), required_insert_count);
401 }
402
SetMaximumDynamicTableCapacity(uint64_t maximum_dynamic_table_capacity)403 bool QpackEncoder::SetMaximumDynamicTableCapacity(
404 uint64_t maximum_dynamic_table_capacity) {
405 return header_table_.SetMaximumDynamicTableCapacity(
406 maximum_dynamic_table_capacity);
407 }
408
SetDynamicTableCapacity(uint64_t dynamic_table_capacity)409 void QpackEncoder::SetDynamicTableCapacity(uint64_t dynamic_table_capacity) {
410 encoder_stream_sender_.SendSetDynamicTableCapacity(dynamic_table_capacity);
411 // Do not flush encoder stream. This write can safely be delayed until more
412 // instructions are written.
413
414 bool success = header_table_.SetDynamicTableCapacity(dynamic_table_capacity);
415 QUICHE_DCHECK(success);
416 }
417
SetMaximumBlockedStreams(uint64_t maximum_blocked_streams)418 bool QpackEncoder::SetMaximumBlockedStreams(uint64_t maximum_blocked_streams) {
419 if (maximum_blocked_streams < maximum_blocked_streams_) {
420 return false;
421 }
422 maximum_blocked_streams_ = maximum_blocked_streams;
423 return true;
424 }
425
OnInsertCountIncrement(uint64_t increment)426 void QpackEncoder::OnInsertCountIncrement(uint64_t increment) {
427 if (increment == 0) {
428 OnErrorDetected(QUIC_QPACK_DECODER_STREAM_INVALID_ZERO_INCREMENT,
429 "Invalid increment value 0.");
430 return;
431 }
432
433 if (!blocking_manager_.OnInsertCountIncrement(increment)) {
434 OnErrorDetected(QUIC_QPACK_DECODER_STREAM_INCREMENT_OVERFLOW,
435 "Insert Count Increment instruction causes overflow.");
436 }
437
438 if (blocking_manager_.known_received_count() >
439 header_table_.inserted_entry_count()) {
440 OnErrorDetected(QUIC_QPACK_DECODER_STREAM_IMPOSSIBLE_INSERT_COUNT,
441 absl::StrCat("Increment value ", increment,
442 " raises known received count to ",
443 blocking_manager_.known_received_count(),
444 " exceeding inserted entry count ",
445 header_table_.inserted_entry_count()));
446 }
447 }
448
OnHeaderAcknowledgement(QuicStreamId stream_id)449 void QpackEncoder::OnHeaderAcknowledgement(QuicStreamId stream_id) {
450 if (!blocking_manager_.OnHeaderAcknowledgement(stream_id)) {
451 OnErrorDetected(
452 QUIC_QPACK_DECODER_STREAM_INCORRECT_ACKNOWLEDGEMENT,
453 absl::StrCat("Header Acknowledgement received for stream ", stream_id,
454 " with no outstanding header blocks."));
455 }
456 }
457
OnStreamCancellation(QuicStreamId stream_id)458 void QpackEncoder::OnStreamCancellation(QuicStreamId stream_id) {
459 blocking_manager_.OnStreamCancellation(stream_id);
460 }
461
OnErrorDetected(QuicErrorCode error_code,absl::string_view error_message)462 void QpackEncoder::OnErrorDetected(QuicErrorCode error_code,
463 absl::string_view error_message) {
464 decoder_stream_error_delegate_->OnDecoderStreamError(error_code,
465 error_message);
466 }
467
468 } // namespace quic
469