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_progressive_decoder.h"
6
7 #include <algorithm>
8 #include <limits>
9 #include <utility>
10
11 #include "absl/strings/string_view.h"
12 #include "quiche/quic/core/qpack/qpack_index_conversions.h"
13 #include "quiche/quic/core/qpack/qpack_instructions.h"
14 #include "quiche/quic/core/qpack/qpack_required_insert_count.h"
15 #include "quiche/quic/platform/api/quic_flag_utils.h"
16 #include "quiche/quic/platform/api/quic_flags.h"
17 #include "quiche/quic/platform/api/quic_logging.h"
18
19 namespace quic {
20
21 namespace {
22
23 // The value argument passed to OnHeaderDecoded() is from an entry in the static
24 // table.
25 constexpr bool kValueFromStaticTable = true;
26
27 } // anonymous namespace
28
QpackProgressiveDecoder(QuicStreamId stream_id,BlockedStreamLimitEnforcer * enforcer,DecodingCompletedVisitor * visitor,QpackDecoderHeaderTable * header_table,HeadersHandlerInterface * handler)29 QpackProgressiveDecoder::QpackProgressiveDecoder(
30 QuicStreamId stream_id, BlockedStreamLimitEnforcer* enforcer,
31 DecodingCompletedVisitor* visitor, QpackDecoderHeaderTable* header_table,
32 HeadersHandlerInterface* handler)
33 : stream_id_(stream_id),
34 prefix_decoder_(std::make_unique<QpackInstructionDecoder>(
35 QpackPrefixLanguage(), this)),
36 instruction_decoder_(QpackRequestStreamLanguage(), this),
37 enforcer_(enforcer),
38 visitor_(visitor),
39 header_table_(header_table),
40 handler_(handler),
41 required_insert_count_(0),
42 base_(0),
43 required_insert_count_so_far_(0),
44 prefix_decoded_(false),
45 blocked_(false),
46 decoding_(true),
47 error_detected_(false),
48 cancelled_(false) {}
49
~QpackProgressiveDecoder()50 QpackProgressiveDecoder::~QpackProgressiveDecoder() {
51 if (blocked_ && !cancelled_) {
52 header_table_->UnregisterObserver(required_insert_count_, this);
53 }
54 }
55
Decode(absl::string_view data)56 void QpackProgressiveDecoder::Decode(absl::string_view data) {
57 QUICHE_DCHECK(decoding_);
58
59 if (data.empty() || error_detected_) {
60 return;
61 }
62
63 // Decode prefix byte by byte until the first (and only) instruction is
64 // decoded.
65 while (!prefix_decoded_) {
66 QUICHE_DCHECK(!blocked_);
67
68 if (!prefix_decoder_->Decode(data.substr(0, 1))) {
69 return;
70 }
71
72 // |prefix_decoder_->Decode()| must return false if an error is detected.
73 QUICHE_DCHECK(!error_detected_);
74
75 data = data.substr(1);
76 if (data.empty()) {
77 return;
78 }
79 }
80
81 if (blocked_) {
82 buffer_.append(data.data(), data.size());
83 } else {
84 QUICHE_DCHECK(buffer_.empty());
85
86 instruction_decoder_.Decode(data);
87 }
88 }
89
EndHeaderBlock()90 void QpackProgressiveDecoder::EndHeaderBlock() {
91 QUICHE_DCHECK(decoding_);
92 decoding_ = false;
93
94 if (!blocked_) {
95 FinishDecoding();
96 }
97 }
98
OnInstructionDecoded(const QpackInstruction * instruction)99 bool QpackProgressiveDecoder::OnInstructionDecoded(
100 const QpackInstruction* instruction) {
101 if (instruction == QpackPrefixInstruction()) {
102 return DoPrefixInstruction();
103 }
104
105 QUICHE_DCHECK(prefix_decoded_);
106 QUICHE_DCHECK_LE(required_insert_count_,
107 header_table_->inserted_entry_count());
108
109 if (instruction == QpackIndexedHeaderFieldInstruction()) {
110 return DoIndexedHeaderFieldInstruction();
111 }
112 if (instruction == QpackIndexedHeaderFieldPostBaseInstruction()) {
113 return DoIndexedHeaderFieldPostBaseInstruction();
114 }
115 if (instruction == QpackLiteralHeaderFieldNameReferenceInstruction()) {
116 return DoLiteralHeaderFieldNameReferenceInstruction();
117 }
118 if (instruction == QpackLiteralHeaderFieldPostBaseInstruction()) {
119 return DoLiteralHeaderFieldPostBaseInstruction();
120 }
121 QUICHE_DCHECK_EQ(instruction, QpackLiteralHeaderFieldInstruction());
122 return DoLiteralHeaderFieldInstruction();
123 }
124
OnInstructionDecodingError(QpackInstructionDecoder::ErrorCode,absl::string_view error_message)125 void QpackProgressiveDecoder::OnInstructionDecodingError(
126 QpackInstructionDecoder::ErrorCode /* error_code */,
127 absl::string_view error_message) {
128 // Ignore |error_code| and always use QUIC_QPACK_DECOMPRESSION_FAILED to avoid
129 // having to define a new QuicErrorCode for every instruction decoder error.
130 OnError(QUIC_QPACK_DECOMPRESSION_FAILED, error_message);
131 }
132
OnInsertCountReachedThreshold()133 void QpackProgressiveDecoder::OnInsertCountReachedThreshold() {
134 QUICHE_DCHECK(blocked_);
135
136 // Clear |blocked_| before calling instruction_decoder_.Decode() below,
137 // because that might destroy |this| and ~QpackProgressiveDecoder() needs to
138 // know not to call UnregisterObserver().
139 blocked_ = false;
140 enforcer_->OnStreamUnblocked(stream_id_);
141
142 if (!buffer_.empty()) {
143 std::string buffer(std::move(buffer_));
144 buffer_.clear();
145 if (!instruction_decoder_.Decode(buffer)) {
146 // |this| might be destroyed.
147 return;
148 }
149 }
150
151 if (!decoding_) {
152 FinishDecoding();
153 }
154 }
155
Cancel()156 void QpackProgressiveDecoder::Cancel() { cancelled_ = true; }
157
DoIndexedHeaderFieldInstruction()158 bool QpackProgressiveDecoder::DoIndexedHeaderFieldInstruction() {
159 if (!instruction_decoder_.s_bit()) {
160 uint64_t absolute_index;
161 if (!QpackRequestStreamRelativeIndexToAbsoluteIndex(
162 instruction_decoder_.varint(), base_, &absolute_index)) {
163 OnError(QUIC_QPACK_DECOMPRESSION_FAILED, "Invalid relative index.");
164 return false;
165 }
166
167 if (absolute_index >= required_insert_count_) {
168 OnError(QUIC_QPACK_DECOMPRESSION_FAILED,
169 "Absolute Index must be smaller than Required Insert Count.");
170 return false;
171 }
172
173 QUICHE_DCHECK_LT(absolute_index, std::numeric_limits<uint64_t>::max());
174 required_insert_count_so_far_ =
175 std::max(required_insert_count_so_far_, absolute_index + 1);
176
177 auto entry =
178 header_table_->LookupEntry(/* is_static = */ false, absolute_index);
179 if (!entry) {
180 OnError(QUIC_QPACK_DECOMPRESSION_FAILED,
181 "Dynamic table entry already evicted.");
182 return false;
183 }
184
185 header_table_->set_dynamic_table_entry_referenced();
186 return OnHeaderDecoded(!kValueFromStaticTable, entry->name(),
187 entry->value());
188 }
189
190 auto entry = header_table_->LookupEntry(/* is_static = */ true,
191 instruction_decoder_.varint());
192 if (!entry) {
193 OnError(QUIC_QPACK_DECOMPRESSION_FAILED, "Static table entry not found.");
194 return false;
195 }
196
197 return OnHeaderDecoded(kValueFromStaticTable, entry->name(), entry->value());
198 }
199
DoIndexedHeaderFieldPostBaseInstruction()200 bool QpackProgressiveDecoder::DoIndexedHeaderFieldPostBaseInstruction() {
201 uint64_t absolute_index;
202 if (!QpackPostBaseIndexToAbsoluteIndex(instruction_decoder_.varint(), base_,
203 &absolute_index)) {
204 OnError(QUIC_QPACK_DECOMPRESSION_FAILED, "Invalid post-base index.");
205 return false;
206 }
207
208 if (absolute_index >= required_insert_count_) {
209 OnError(QUIC_QPACK_DECOMPRESSION_FAILED,
210 "Absolute Index must be smaller than Required Insert Count.");
211 return false;
212 }
213
214 QUICHE_DCHECK_LT(absolute_index, std::numeric_limits<uint64_t>::max());
215 required_insert_count_so_far_ =
216 std::max(required_insert_count_so_far_, absolute_index + 1);
217
218 auto entry =
219 header_table_->LookupEntry(/* is_static = */ false, absolute_index);
220 if (!entry) {
221 OnError(QUIC_QPACK_DECOMPRESSION_FAILED,
222 "Dynamic table entry already evicted.");
223 return false;
224 }
225
226 header_table_->set_dynamic_table_entry_referenced();
227 return OnHeaderDecoded(!kValueFromStaticTable, entry->name(), entry->value());
228 }
229
DoLiteralHeaderFieldNameReferenceInstruction()230 bool QpackProgressiveDecoder::DoLiteralHeaderFieldNameReferenceInstruction() {
231 if (!instruction_decoder_.s_bit()) {
232 uint64_t absolute_index;
233 if (!QpackRequestStreamRelativeIndexToAbsoluteIndex(
234 instruction_decoder_.varint(), base_, &absolute_index)) {
235 OnError(QUIC_QPACK_DECOMPRESSION_FAILED, "Invalid relative index.");
236 return false;
237 }
238
239 if (absolute_index >= required_insert_count_) {
240 OnError(QUIC_QPACK_DECOMPRESSION_FAILED,
241 "Absolute Index must be smaller than Required Insert Count.");
242 return false;
243 }
244
245 QUICHE_DCHECK_LT(absolute_index, std::numeric_limits<uint64_t>::max());
246 required_insert_count_so_far_ =
247 std::max(required_insert_count_so_far_, absolute_index + 1);
248
249 auto entry =
250 header_table_->LookupEntry(/* is_static = */ false, absolute_index);
251 if (!entry) {
252 OnError(QUIC_QPACK_DECOMPRESSION_FAILED,
253 "Dynamic table entry already evicted.");
254 return false;
255 }
256
257 header_table_->set_dynamic_table_entry_referenced();
258 return OnHeaderDecoded(!kValueFromStaticTable, entry->name(),
259 instruction_decoder_.value());
260 }
261
262 auto entry = header_table_->LookupEntry(/* is_static = */ true,
263 instruction_decoder_.varint());
264 if (!entry) {
265 OnError(QUIC_QPACK_DECOMPRESSION_FAILED, "Static table entry not found.");
266 return false;
267 }
268
269 return OnHeaderDecoded(kValueFromStaticTable, entry->name(),
270 instruction_decoder_.value());
271 }
272
DoLiteralHeaderFieldPostBaseInstruction()273 bool QpackProgressiveDecoder::DoLiteralHeaderFieldPostBaseInstruction() {
274 uint64_t absolute_index;
275 if (!QpackPostBaseIndexToAbsoluteIndex(instruction_decoder_.varint(), base_,
276 &absolute_index)) {
277 OnError(QUIC_QPACK_DECOMPRESSION_FAILED, "Invalid post-base index.");
278 return false;
279 }
280
281 if (absolute_index >= required_insert_count_) {
282 OnError(QUIC_QPACK_DECOMPRESSION_FAILED,
283 "Absolute Index must be smaller than Required Insert Count.");
284 return false;
285 }
286
287 QUICHE_DCHECK_LT(absolute_index, std::numeric_limits<uint64_t>::max());
288 required_insert_count_so_far_ =
289 std::max(required_insert_count_so_far_, absolute_index + 1);
290
291 auto entry =
292 header_table_->LookupEntry(/* is_static = */ false, absolute_index);
293 if (!entry) {
294 OnError(QUIC_QPACK_DECOMPRESSION_FAILED,
295 "Dynamic table entry already evicted.");
296 return false;
297 }
298
299 header_table_->set_dynamic_table_entry_referenced();
300 return OnHeaderDecoded(!kValueFromStaticTable, entry->name(),
301 instruction_decoder_.value());
302 }
303
DoLiteralHeaderFieldInstruction()304 bool QpackProgressiveDecoder::DoLiteralHeaderFieldInstruction() {
305 return OnHeaderDecoded(!kValueFromStaticTable, instruction_decoder_.name(),
306 instruction_decoder_.value());
307 }
308
DoPrefixInstruction()309 bool QpackProgressiveDecoder::DoPrefixInstruction() {
310 QUICHE_DCHECK(!prefix_decoded_);
311
312 if (!QpackDecodeRequiredInsertCount(
313 prefix_decoder_->varint(), header_table_->max_entries(),
314 header_table_->inserted_entry_count(), &required_insert_count_)) {
315 OnError(QUIC_QPACK_DECOMPRESSION_FAILED,
316 "Error decoding Required Insert Count.");
317 return false;
318 }
319
320 const bool sign = prefix_decoder_->s_bit();
321 const uint64_t delta_base = prefix_decoder_->varint2();
322 if (!DeltaBaseToBase(sign, delta_base, &base_)) {
323 OnError(QUIC_QPACK_DECOMPRESSION_FAILED, "Error calculating Base.");
324 return false;
325 }
326
327 prefix_decoded_ = true;
328
329 if (required_insert_count_ > header_table_->inserted_entry_count()) {
330 if (!enforcer_->OnStreamBlocked(stream_id_)) {
331 OnError(QUIC_QPACK_DECOMPRESSION_FAILED,
332 "Limit on number of blocked streams exceeded.");
333 return false;
334 }
335 blocked_ = true;
336 header_table_->RegisterObserver(required_insert_count_, this);
337 }
338
339 return true;
340 }
341
OnHeaderDecoded(bool,absl::string_view name,absl::string_view value)342 bool QpackProgressiveDecoder::OnHeaderDecoded(bool /*value_from_static_table*/,
343 absl::string_view name,
344 absl::string_view value) {
345 handler_->OnHeaderDecoded(name, value);
346 return true;
347 }
348
FinishDecoding()349 void QpackProgressiveDecoder::FinishDecoding() {
350 QUICHE_DCHECK(buffer_.empty());
351 QUICHE_DCHECK(!blocked_);
352 QUICHE_DCHECK(!decoding_);
353
354 if (error_detected_) {
355 return;
356 }
357
358 if (!instruction_decoder_.AtInstructionBoundary()) {
359 OnError(QUIC_QPACK_DECOMPRESSION_FAILED, "Incomplete header block.");
360 return;
361 }
362
363 if (!prefix_decoded_) {
364 OnError(QUIC_QPACK_DECOMPRESSION_FAILED, "Incomplete header data prefix.");
365 return;
366 }
367
368 if (required_insert_count_ != required_insert_count_so_far_) {
369 OnError(QUIC_QPACK_DECOMPRESSION_FAILED,
370 "Required Insert Count too large.");
371 return;
372 }
373
374 visitor_->OnDecodingCompleted(stream_id_, required_insert_count_);
375 handler_->OnDecodingCompleted();
376 }
377
OnError(QuicErrorCode error_code,absl::string_view error_message)378 void QpackProgressiveDecoder::OnError(QuicErrorCode error_code,
379 absl::string_view error_message) {
380 QUICHE_DCHECK(!error_detected_);
381
382 error_detected_ = true;
383 // Might destroy |this|.
384 handler_->OnDecodingErrorDetected(error_code, error_message);
385 }
386
DeltaBaseToBase(bool sign,uint64_t delta_base,uint64_t * base)387 bool QpackProgressiveDecoder::DeltaBaseToBase(bool sign, uint64_t delta_base,
388 uint64_t* base) {
389 if (sign) {
390 if (delta_base == std::numeric_limits<uint64_t>::max() ||
391 required_insert_count_ < delta_base + 1) {
392 return false;
393 }
394 *base = required_insert_count_ - delta_base - 1;
395 return true;
396 }
397
398 if (delta_base >
399 std::numeric_limits<uint64_t>::max() - required_insert_count_) {
400 return false;
401 }
402 *base = required_insert_count_ + delta_base;
403 return true;
404 }
405
406 } // namespace quic
407