1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package io.netty.handler.codec.http3;
17
18 import io.netty.buffer.ByteBuf;
19 import io.netty.handler.codec.quic.QuicStreamChannel;
20 import io.netty.util.AsciiString;
21 import io.netty.util.collection.IntObjectHashMap;
22 import io.netty.util.collection.IntObjectMap.PrimitiveEntry;
23 import io.netty.util.internal.logging.InternalLogger;
24 import io.netty.util.internal.logging.InternalLoggerFactory;
25
26 import java.util.ArrayList;
27 import java.util.List;
28 import java.util.function.BiConsumer;
29
30 import static io.netty.handler.codec.http3.Http3CodecUtils.closeOnFailure;
31 import static io.netty.handler.codec.http3.QpackDecoderStateSyncStrategy.ackEachInsert;
32 import static io.netty.handler.codec.http3.QpackUtil.decodePrefixedIntegerAsInt;
33 import static io.netty.handler.codec.http3.QpackUtil.encodePrefixedInteger;
34 import static io.netty.handler.codec.http3.QpackUtil.firstByteEquals;
35 import static io.netty.handler.codec.http3.QpackUtil.toIntOrThrow;
36 import static java.lang.Math.floorDiv;
37
38 final class QpackDecoder {
39 private static final InternalLogger logger = InternalLoggerFactory.getInstance(QpackDecoder.class);
40 private static final QpackException DYNAMIC_TABLE_CAPACITY_EXCEEDS_MAX =
41 QpackException.newStatic(QpackDecoder.class, "setDynamicTableCapacity(...)",
42 "QPACK - decoder dynamic table capacity exceeds max capacity.");
43 private static final QpackException HEADER_ILLEGAL_INDEX_VALUE =
44 QpackException.newStatic(QpackDecoder.class, "decodeIndexed(...)", "QPACK - illegal index value");
45 private static final QpackException NAME_ILLEGAL_INDEX_VALUE =
46 QpackException.newStatic(QpackDecoder.class, "decodeLiteralWithNameRef(...)",
47 "QPACK - illegal name index value");
48 private static final QpackException INVALID_REQUIRED_INSERT_COUNT =
49 QpackException.newStatic(QpackDecoder.class, "decodeRequiredInsertCount(...)",
50 "QPACK - invalid required insert count");
51 private static final QpackException INVALID_LENGTH_ENCODED_LITERAL =
52 QpackException.newStatic(QpackDecoder.class, "decodeHuffmanEncodedLiteral(...)",
53 "QPACK - invalid length for LITERAL");
54 private static final QpackException MAX_BLOCKED_STREAMS_EXCEEDED =
55 QpackException.newStatic(QpackDecoder.class, "shouldWaitForDynamicTableUpdates(...)",
56 "QPACK - exceeded max blocked streams");
57 private static final QpackException BLOCKED_STREAM_RESUMPTION_FAILED =
58 QpackException.newStatic(QpackDecoder.class, "sendInsertCountIncrementIfRequired(...)",
59 "QPACK - failed to resume a blocked stream");
60
61 private static final QpackException UNKNOWN_TYPE =
62 QpackException.newStatic(QpackDecoder.class, "decode(...)", "QPACK - unknown type");
63 private static final QpackException TRUNCATED_PREFIXED_INTEGER =
64 QpackException.newStatic(QpackDecoder.class, "decode(...)",
65 "QPACK - truncated prefixed integer in field section");
66
67 private final QpackHuffmanDecoder huffmanDecoder;
68 private final QpackDecoderDynamicTable dynamicTable;
69 private final long maxTableCapacity;
70 private final int maxBlockedStreams;
71 private final QpackDecoderStateSyncStrategy stateSyncStrategy;
72
73
74
75
76 private final IntObjectHashMap<List<BlockedStream>> blockedStreams;
77
78 private final long maxEntries;
79 private final long fullRange;
80 private int blockedStreamsCount;
81 private long lastAckInsertCount;
82
83 QpackDecoder(long maxTableCapacity, int maxBlockedStreams) {
84 this(maxTableCapacity, maxBlockedStreams, new QpackDecoderDynamicTable(), ackEachInsert());
85 }
86
87 QpackDecoder(long maxTableCapacity, int maxBlockedStreams,
88 QpackDecoderDynamicTable dynamicTable, QpackDecoderStateSyncStrategy stateSyncStrategy) {
89 huffmanDecoder = new QpackHuffmanDecoder();
90 this.maxTableCapacity = maxTableCapacity;
91 this.maxBlockedStreams = maxBlockedStreams;
92 this.stateSyncStrategy = stateSyncStrategy;
93 blockedStreams = new IntObjectHashMap<>(Math.min(16, maxBlockedStreams));
94 this.dynamicTable = dynamicTable;
95 maxEntries = QpackUtil.maxEntries(maxTableCapacity);
96 try {
97 fullRange = toIntOrThrow(2 * maxEntries);
98 } catch (QpackException e) {
99 throw new IllegalArgumentException(e);
100 }
101 }
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119 public boolean decode(QpackAttributes qpackAttributes, long streamId, ByteBuf in,
120 int length, BiConsumer<CharSequence, CharSequence> sink, Runnable whenDecoded)
121 throws QpackException {
122 final int initialReaderIdx = in.readerIndex();
123 final int requiredInsertCount = decodeRequiredInsertCount(qpackAttributes, in);
124 if (shouldWaitForDynamicTableUpdates(requiredInsertCount)) {
125 blockedStreamsCount++;
126 blockedStreams.computeIfAbsent(requiredInsertCount, __ -> new ArrayList<>(2))
127 .add(new BlockedStream(streamId, whenDecoded));
128 in.readerIndex(initialReaderIdx);
129 return false;
130 }
131
132 in = in.readSlice(length - (in.readerIndex() - initialReaderIdx));
133 final int base = decodeBase(in, requiredInsertCount);
134
135 while (in.isReadable()) {
136 byte b = in.getByte(in.readerIndex());
137 if (isIndexed(b)) {
138 decodeIndexed(in, sink, base);
139 } else if (isIndexedWithPostBase(b)) {
140 decodeIndexedWithPostBase(in, sink, base);
141 } else if (isLiteralWithNameRef(b)) {
142 decodeLiteralWithNameRef(in, sink, base);
143 } else if (isLiteralWithPostBaseNameRef(b)) {
144 decodeLiteralWithPostBaseNameRef(in, sink, base);
145 } else if (isLiteral(b)) {
146 decodeLiteral(in, sink);
147 } else {
148 throw UNKNOWN_TYPE;
149 }
150 }
151 if (requiredInsertCount > 0) {
152 assert !qpackAttributes.dynamicTableDisabled();
153 assert qpackAttributes.decoderStreamAvailable();
154
155 stateSyncStrategy.sectionAcknowledged(requiredInsertCount);
156
157
158
159 if (requiredInsertCount > lastAckInsertCount) {
160 lastAckInsertCount = requiredInsertCount;
161 }
162 final ByteBuf sectionAck = qpackAttributes.decoderStream().alloc().buffer(8);
163 encodePrefixedInteger(sectionAck, (byte) 0b1000_0000, 7, streamId);
164 closeOnFailure(qpackAttributes.decoderStream().writeAndFlush(sectionAck));
165 }
166 return true;
167 }
168
169
170
171
172
173
174
175
176
177 void setDynamicTableCapacity(long capacity) throws QpackException {
178 if (capacity > maxTableCapacity) {
179 throw DYNAMIC_TABLE_CAPACITY_EXCEEDS_MAX;
180 }
181 dynamicTable.setCapacity(capacity);
182 }
183
184
185
186
187
188
189
190
191
192
193
194
195
196 void insertWithNameReference(QuicStreamChannel qpackDecoderStream, boolean staticTableRef, int nameIdx,
197 CharSequence value) throws QpackException {
198 final QpackHeaderField entryForName;
199 if (staticTableRef) {
200 entryForName = QpackStaticTable.getField(nameIdx);
201 } else {
202 entryForName = dynamicTable.getEntryRelativeEncoderInstructions(nameIdx);
203 }
204 dynamicTable.add(new QpackHeaderField(entryForName.name, value));
205 sendInsertCountIncrementIfRequired(qpackDecoderStream);
206 }
207
208
209
210
211
212
213
214
215
216
217
218 void insertLiteral(QuicStreamChannel qpackDecoderStream, CharSequence name, CharSequence value)
219 throws QpackException {
220 dynamicTable.add(new QpackHeaderField(name, value));
221 sendInsertCountIncrementIfRequired(qpackDecoderStream);
222 }
223
224
225
226
227
228
229
230
231
232
233 void duplicate(QuicStreamChannel qpackDecoderStream, int index)
234 throws QpackException {
235 dynamicTable.add(dynamicTable.getEntryRelativeEncoderInstructions(index));
236 sendInsertCountIncrementIfRequired(qpackDecoderStream);
237 }
238
239
240
241
242
243
244
245
246 void streamAbandoned(QuicStreamChannel qpackDecoderStream, long streamId) {
247 if (maxTableCapacity == 0) {
248 return;
249 }
250 releaseBlockedStream(streamId);
251 sendStreamCancellation(qpackDecoderStream, streamId);
252 }
253
254 void sendStreamCancellation(QuicStreamChannel qpackDecoderStream, long streamId) {
255
256
257
258
259
260 final ByteBuf cancel = qpackDecoderStream.alloc().buffer(8);
261 encodePrefixedInteger(cancel, (byte) 0b0100_0000, 6, streamId);
262 closeOnFailure(qpackDecoderStream.writeAndFlush(cancel));
263 }
264
265 boolean releaseBlockedStream(long streamId) {
266 if (blockedStreamsCount == 0) {
267 return false;
268 }
269 for (PrimitiveEntry<List<BlockedStream>> entry : blockedStreams.entries()) {
270 List<BlockedStream> list = entry.value();
271 for (int i = 0; i < list.size(); i++) {
272 if (list.get(i).streamId == streamId) {
273 list.remove(i);
274 blockedStreamsCount--;
275 if (list.isEmpty()) {
276 blockedStreams.remove(entry.key());
277 }
278 return true;
279 }
280 }
281 }
282 return false;
283 }
284
285 private static boolean isIndexed(byte b) {
286
287
288
289
290
291 return (b & 0b1000_0000) == 0b1000_0000;
292 }
293
294 private static boolean isLiteralWithNameRef(byte b) {
295
296
297
298
299
300 return (b & 0b1100_0000) == 0b0100_0000;
301 }
302
303 private static boolean isLiteral(byte b) {
304
305
306
307
308
309 return (b & 0b1110_0000) == 0b0010_0000;
310 }
311
312 private static boolean isIndexedWithPostBase(byte b) {
313
314
315
316
317
318 return (b & 0b1111_0000) == 0b0001_0000;
319 }
320
321 private static boolean isLiteralWithPostBaseNameRef(byte b) {
322
323
324
325
326
327 return (b & 0b1111_0000) == 0b0000_0000;
328 }
329
330
331
332
333
334
335 private int decodePrefixedIntOrThrow(ByteBuf in, int prefixLength) throws QpackException {
336 final int i = decodePrefixedIntegerAsInt(in, prefixLength);
337 if (i < 0) {
338 throw TRUNCATED_PREFIXED_INTEGER;
339 }
340 return i;
341 }
342
343 private static long decodePrefixedLongOrThrow(ByteBuf in, int prefixLength) throws QpackException {
344 final long i = QpackUtil.decodePrefixedInteger(in, prefixLength);
345 if (i < 0) {
346 throw TRUNCATED_PREFIXED_INTEGER;
347 }
348 return i;
349 }
350
351 private void decodeIndexed(ByteBuf in, BiConsumer<CharSequence, CharSequence> sink, int base)
352 throws QpackException {
353
354
355
356
357
358
359
360 final QpackHeaderField field;
361 if (firstByteEquals(in, (byte) 0b1100_0000)) {
362 final int idx = decodePrefixedIntOrThrow(in, 6);
363 if (idx >= QpackStaticTable.length) {
364 throw HEADER_ILLEGAL_INDEX_VALUE;
365 }
366 field = QpackStaticTable.getField(idx);
367 } else {
368 final int idx = decodePrefixedIntOrThrow(in, 6);
369 field = dynamicTable.getEntryRelativeEncodedField(base - idx - 1);
370 }
371 sink.accept(field.name, field.value);
372 }
373
374 private void decodeIndexedWithPostBase(ByteBuf in, BiConsumer<CharSequence, CharSequence> sink, int base)
375 throws QpackException {
376
377
378
379
380
381 final int idx = decodePrefixedIntOrThrow(in, 4);
382 QpackHeaderField field = dynamicTable.getEntryRelativeEncodedField(base + idx);
383 sink.accept(field.name, field.value);
384 }
385
386 private void decodeLiteralWithNameRef(ByteBuf in, BiConsumer<CharSequence, CharSequence> sink, int base)
387 throws QpackException {
388 final CharSequence name;
389
390
391
392
393
394
395
396
397
398
399
400 if (firstByteEquals(in, (byte) 0b0001_0000)) {
401 final int idx = decodePrefixedIntOrThrow(in, 4);
402 if (idx >= QpackStaticTable.length) {
403 throw NAME_ILLEGAL_INDEX_VALUE;
404 }
405 name = QpackStaticTable.getField(idx).name;
406 } else {
407 final int idx = decodePrefixedIntOrThrow(in, 4);
408 name = dynamicTable.getEntryRelativeEncodedField(base - idx - 1).name;
409 }
410 final CharSequence value = decodeHuffmanEncodedLiteral(in, 7);
411 sink.accept(name, value);
412 }
413
414 private void decodeLiteralWithPostBaseNameRef(ByteBuf in, BiConsumer<CharSequence, CharSequence> sink, int base)
415 throws QpackException {
416
417
418
419
420
421
422
423
424
425 final int idx = decodePrefixedIntOrThrow(in, 3);
426 CharSequence name = dynamicTable.getEntryRelativeEncodedField(base + idx).name;
427 final CharSequence value = decodeHuffmanEncodedLiteral(in, 7);
428 sink.accept(name, value);
429 }
430
431 private void decodeLiteral(ByteBuf in, BiConsumer<CharSequence, CharSequence> sink) throws QpackException {
432
433
434
435
436
437
438
439
440
441
442
443 final CharSequence name = decodeHuffmanEncodedLiteral(in, 3);
444 final CharSequence value = decodeHuffmanEncodedLiteral(in, 7);
445 sink.accept(name, value);
446 }
447
448 private CharSequence decodeHuffmanEncodedLiteral(ByteBuf in, int prefix) throws QpackException {
449 assert prefix < 8;
450 final boolean huffmanEncoded = firstByteEquals(in, (byte) (1 << prefix));
451 final int length = decodePrefixedIntOrThrow(in, prefix);
452 if (huffmanEncoded) {
453 return huffmanDecoder.decode(in, length);
454 }
455 if (in.readableBytes() < length) {
456 throw INVALID_LENGTH_ENCODED_LITERAL;
457 }
458 byte[] buf = new byte[length];
459 in.readBytes(buf);
460 return new AsciiString(buf, false);
461 }
462
463
464 int decodeRequiredInsertCount(QpackAttributes qpackAttributes, ByteBuf buf) throws QpackException {
465 final long encodedInsertCount = decodePrefixedLongOrThrow(buf, 8);
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490 if (encodedInsertCount == 0) {
491 return 0;
492 }
493 if (qpackAttributes.dynamicTableDisabled() || encodedInsertCount > fullRange) {
494 throw INVALID_REQUIRED_INSERT_COUNT;
495 }
496
497 final long maxValue = dynamicTable.insertCount() + maxEntries;
498 final long maxWrapped = floorDiv(maxValue, fullRange) * fullRange;
499 long requiredInsertCount = maxWrapped + encodedInsertCount - 1;
500
501 if (requiredInsertCount > maxValue) {
502 if (requiredInsertCount <= fullRange) {
503 throw INVALID_REQUIRED_INSERT_COUNT;
504 }
505 requiredInsertCount -= fullRange;
506 }
507
508 if (requiredInsertCount == 0) {
509 throw INVALID_REQUIRED_INSERT_COUNT;
510 }
511 return toIntOrThrow(requiredInsertCount);
512 }
513
514
515 int decodeBase(ByteBuf buf, int requiredInsertCount) throws QpackException {
516
517
518
519
520
521 final boolean s = (buf.getByte(buf.readerIndex()) & 0b1000_0000) == 0b1000_0000;
522 final int deltaBase = decodePrefixedIntOrThrow(buf, 7);
523
524
525
526
527
528 return s ? requiredInsertCount - deltaBase - 1 : requiredInsertCount + deltaBase;
529 }
530
531 private boolean shouldWaitForDynamicTableUpdates(int requiredInsertCount) throws QpackException {
532 if (requiredInsertCount > dynamicTable.insertCount()) {
533 if (blockedStreamsCount >= maxBlockedStreams) {
534 throw MAX_BLOCKED_STREAMS_EXCEEDED;
535 }
536 return true;
537 }
538 return false;
539 }
540
541 private void sendInsertCountIncrementIfRequired(QuicStreamChannel qpackDecoderStream) throws QpackException {
542 final int insertCount = dynamicTable.insertCount();
543 final List<BlockedStream> streams = this.blockedStreams.remove(insertCount);
544 if (streams != null) {
545 blockedStreamsCount -= streams.size();
546 boolean failed = false;
547 for (BlockedStream stream : streams) {
548 try {
549 stream.whenDecoded.run();
550 } catch (Exception e) {
551 failed = true;
552 logger.error("Failed to resume a blocked stream {}.", stream.whenDecoded, e);
553 }
554 }
555 if (failed) {
556 throw BLOCKED_STREAM_RESUMPTION_FAILED;
557 }
558 }
559 if (stateSyncStrategy.entryAdded(insertCount) &&
560
561 insertCount > lastAckInsertCount) {
562
563
564
565
566
567 final ByteBuf incr = qpackDecoderStream.alloc().buffer(8);
568 encodePrefixedInteger(incr, (byte) 0b0, 6, insertCount - lastAckInsertCount);
569 lastAckInsertCount = insertCount;
570 closeOnFailure(qpackDecoderStream.writeAndFlush(incr));
571 }
572 }
573
574 private static final class BlockedStream {
575 final long streamId;
576 final Runnable whenDecoded;
577
578 BlockedStream(long streamId, Runnable whenDecoded) {
579 this.streamId = streamId;
580 this.whenDecoded = whenDecoded;
581 }
582 }
583 }