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