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