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