1 /*
2 * Copyright 2020 The Netty Project
3 *
4 * The Netty Project licenses this file to you under the Apache License,
5 * version 2.0 (the "License"); you may not use this file except in compliance
6 * with the License. You may obtain a copy of the License at:
7 *
8 * https://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13 * License for the specific language governing permissions and limitations
14 * under the License.
15 */
16 package io.netty.handler.codec.http3;
17
18 import io.netty.buffer.ByteBuf;
19 import io.netty.buffer.ByteBufAllocator;
20 import io.netty.handler.codec.quic.QuicStreamChannel;
21 import io.netty.util.ReferenceCountUtil;
22 import io.netty.util.collection.LongObjectHashMap;
23
24 import java.util.ArrayDeque;
25 import java.util.Arrays;
26 import java.util.Map;
27 import java.util.Queue;
28
29 import static io.netty.handler.codec.http3.Http3CodecUtils.closeOnFailure;
30 import static io.netty.handler.codec.http3.QpackHeaderField.sizeOf;
31 import static io.netty.handler.codec.http3.QpackUtil.encodePrefixedInteger;
32
33 /**
34 * A QPACK encoder.
35 */
36 final class QpackEncoder {
37 private static final QpackException INVALID_SECTION_ACKNOWLEDGMENT =
38 QpackException.newStatic(QpackDecoder.class, "sectionAcknowledgment(...)",
39 "QPACK - section acknowledgment received for unknown stream.");
40 private static final int DYNAMIC_TABLE_ENCODE_NOT_DONE = -1;
41 private static final int DYNAMIC_TABLE_ENCODE_NOT_POSSIBLE = -2;
42
43 private final QpackHuffmanEncoder huffmanEncoder;
44 private final QpackEncoderDynamicTable dynamicTable;
45 private int maxBlockedStreams;
46 private int blockedStreams;
47 private LongObjectHashMap<Queue<Indices>> streamSectionTrackers;
48
49 QpackEncoder() {
50 this(new QpackEncoderDynamicTable());
51 }
52
53 QpackEncoder(QpackEncoderDynamicTable dynamicTable) {
54 huffmanEncoder = new QpackHuffmanEncoder();
55 this.dynamicTable = dynamicTable;
56 }
57
58 /**
59 * Encode the header field into the header block.
60 *
61 * TODO: do we need to support sensitivity detector?
62 */
63 void encodeHeaders(QpackAttributes qpackAttributes, ByteBuf out, ByteBufAllocator allocator, long streamId,
64 Http3Headers headers) {
65 final int base = dynamicTable.insertCount();
66 // Allocate a new buffer as we have to go back and write a variable length base and required insert count
67 // later.
68 ByteBuf tmp = allocator.buffer();
69 try {
70 int maxDynamicTblIdx = -1;
71 int requiredInsertCount = 0;
72 Indices dynamicTableIndices = null;
73 for (Map.Entry<CharSequence, CharSequence> header : headers) {
74 CharSequence name = header.getKey();
75 CharSequence value = header.getValue();
76 int dynamicTblIdx = encodeHeader(qpackAttributes, tmp, base, name, value);
77 if (dynamicTblIdx >= 0) {
78 int req = dynamicTable.addReferenceToEntry(name, value, dynamicTblIdx);
79 if (dynamicTblIdx > maxDynamicTblIdx) {
80 maxDynamicTblIdx = dynamicTblIdx;
81 requiredInsertCount = req;
82 }
83 if (dynamicTableIndices == null) {
84 dynamicTableIndices = new Indices();
85 }
86 dynamicTableIndices.add(dynamicTblIdx);
87 }
88 }
89
90 // Track all the indices that we need to ack later.
91 if (dynamicTableIndices != null) {
92 assert streamSectionTrackers != null;
93 streamSectionTrackers.computeIfAbsent(streamId, __ -> new ArrayDeque<>())
94 .add(dynamicTableIndices);
95 }
96
97 // https://www.rfc-editor.org/rfc/rfc9204.html#name-encoded-field-section-prefi
98 // 0 1 2 3 4 5 6 7
99 // +---+---+---+---+---+---+---+---+
100 // | Required Insert Count (8+) |
101 // +---+---------------------------+
102 // | S | Delta Base (7+) |
103 // +---+---------------------------+
104 encodePrefixedInteger(out, (byte) 0b0, 8, dynamicTable.encodedRequiredInsertCount(requiredInsertCount));
105 if (base >= requiredInsertCount) {
106 encodePrefixedInteger(out, (byte) 0b0, 7, base - requiredInsertCount);
107 } else {
108 encodePrefixedInteger(out, (byte) 0b1000_0000, 7, requiredInsertCount - base - 1);
109 }
110 out.writeBytes(tmp);
111 } finally {
112 tmp.release();
113 }
114 }
115
116 void configureDynamicTable(QpackAttributes attributes, long maxTableCapacity, int blockedStreams)
117 throws QpackException {
118 if (maxTableCapacity > 0) {
119 assert attributes.encoderStreamAvailable();
120 final QuicStreamChannel encoderStream = attributes.encoderStream();
121 dynamicTable.maxTableCapacity(maxTableCapacity);
122 final ByteBuf tableCapacity = encoderStream.alloc().buffer(8);
123 // https://www.rfc-editor.org/rfc/rfc9204.html#name-set-dynamic-table-capacity
124 // 0 1 2 3 4 5 6 7
125 // +---+---+---+---+---+---+---+---+
126 // | 0 | 0 | 1 | Capacity (5+) |
127 // +---+---+---+-------------------+
128 encodePrefixedInteger(tableCapacity, (byte) 0b0010_0000, 5, maxTableCapacity);
129 closeOnFailure(encoderStream.writeAndFlush(tableCapacity));
130
131 streamSectionTrackers = new LongObjectHashMap<>();
132 maxBlockedStreams = blockedStreams;
133 }
134 }
135
136 /**
137 * <a href="https://quicwg.org/base-drafts/draft-ietf-quic-qpack.html#name-section-acknowledgment">
138 * Section acknowledgment</a> for the passed {@code streamId}.
139 *
140 * @param streamId For which the header fields section is acknowledged.
141 */
142 void sectionAcknowledgment(long streamId) throws QpackException {
143 assert streamSectionTrackers != null;
144 final Queue<Indices> tracker = streamSectionTrackers.get(streamId);
145 if (tracker == null) {
146 throw INVALID_SECTION_ACKNOWLEDGMENT;
147 }
148
149 Indices dynamicTableIndices = tracker.poll();
150
151 if (tracker.isEmpty()) {
152 streamSectionTrackers.remove(streamId);
153 }
154
155 if (dynamicTableIndices == null) {
156 throw INVALID_SECTION_ACKNOWLEDGMENT;
157 }
158
159 dynamicTableIndices.forEach(dynamicTable::acknowledgeInsertCountOnAck);
160 }
161
162 /**
163 * <a href="https://quicwg.org/base-drafts/draft-ietf-quic-qpack.html#name-stream-cancellation">
164 * Stream cancellation</a> for the passed {@code streamId}.
165 *
166 * @param streamId which is cancelled.
167 */
168 void streamCancellation(long streamId) throws QpackException {
169 // If a configureDynamicTable(...) was called with a maxTableCapacity of 0 we will have not instanced
170 // streamSectionTrackers. The remote peer might still send a stream cancellation for a stream, while it
171 // is optional. See https://www.rfc-editor.org/rfc/rfc9204.html#section-2.2.2.2
172 if (streamSectionTrackers == null) {
173 return;
174 }
175 final Queue<Indices> tracker = streamSectionTrackers.remove(streamId);
176 if (tracker != null) {
177 for (;;) {
178 Indices dynamicTableIndices = tracker.poll();
179 if (dynamicTableIndices == null) {
180 break;
181 }
182 dynamicTableIndices.forEach(dynamicTable::acknowledgeInsertCountOnCancellation);
183 }
184 }
185 }
186
187 /**
188 * <a href="https://quicwg.org/base-drafts/draft-ietf-quic-qpack.html#name-insert-count-increment">
189 * Insert count increment</a>.
190 *
191 * @param increment for the known received count.
192 */
193 void insertCountIncrement(int increment) throws QpackException {
194 dynamicTable.incrementKnownReceivedCount(increment);
195 }
196
197 /**
198 * Encode the header field into the header block.
199 * @param qpackAttributes {@link QpackAttributes} for the channel.
200 * @param out {@link ByteBuf} to which encoded header field is to be written.
201 * @param base Base for the dynamic table index.
202 * @param name for the header field.
203 * @param value for the header field.
204 * @return Index in the dynamic table if the header field was encoded as a reference to the dynamic table,
205 * {@link #DYNAMIC_TABLE_ENCODE_NOT_DONE } otherwise.
206 */
207 private int encodeHeader(QpackAttributes qpackAttributes, ByteBuf out, int base, CharSequence name,
208 CharSequence value) {
209 int index = QpackStaticTable.findFieldIndex(name, value);
210 if (index == QpackStaticTable.NOT_FOUND) {
211 if (qpackAttributes.dynamicTableDisabled()) {
212 encodeLiteral(out, name, value);
213 return DYNAMIC_TABLE_ENCODE_NOT_POSSIBLE;
214 }
215 return encodeWithDynamicTable(qpackAttributes, out, base, name, value);
216 } else if ((index & QpackStaticTable.MASK_NAME_REF) == QpackStaticTable.MASK_NAME_REF) {
217 int dynamicTblIdx = tryEncodeWithDynamicTable(qpackAttributes, out, base, name, value);
218 if (dynamicTblIdx >= 0) {
219 return dynamicTblIdx;
220 }
221 final int nameIdx = index ^ QpackStaticTable.MASK_NAME_REF;
222 dynamicTblIdx = tryAddToDynamicTable(qpackAttributes, true, nameIdx, name, value);
223 if (dynamicTblIdx >= 0) {
224 if (dynamicTblIdx >= base) {
225 encodePostBaseIndexed(out, base, dynamicTblIdx);
226 } else {
227 encodeIndexedDynamicTable(out, base, dynamicTblIdx);
228 }
229 return dynamicTblIdx;
230 }
231 encodeLiteralWithNameRefStaticTable(out, nameIdx, value);
232 } else {
233 encodeIndexedStaticTable(out, index);
234 }
235 return qpackAttributes.dynamicTableDisabled() ? DYNAMIC_TABLE_ENCODE_NOT_POSSIBLE :
236 DYNAMIC_TABLE_ENCODE_NOT_DONE;
237 }
238
239 /**
240 * Encode the header field using dynamic table, if possible.
241 *
242 * @param qpackAttributes {@link QpackAttributes} for the channel.
243 * @param out {@link ByteBuf} to which encoded header field is to be written.
244 * @param base Base for the dynamic table index.
245 * @param name for the header field.
246 * @param value for the header field.
247 * @return Index in the dynamic table if the header field was encoded as a reference to the dynamic table,
248 * {@link #DYNAMIC_TABLE_ENCODE_NOT_DONE } otherwise.
249 */
250 private int encodeWithDynamicTable(QpackAttributes qpackAttributes, ByteBuf out, int base, CharSequence name,
251 CharSequence value) {
252 int idx = tryEncodeWithDynamicTable(qpackAttributes, out, base, name, value);
253 if (idx >= 0) {
254 return idx;
255 }
256
257 if (idx == DYNAMIC_TABLE_ENCODE_NOT_DONE) {
258 idx = tryAddToDynamicTable(qpackAttributes, false, -1, name, value);
259 if (idx >= 0) {
260 if (idx >= base) {
261 encodePostBaseIndexed(out, base, idx);
262 } else {
263 encodeIndexedDynamicTable(out, base, idx);
264 }
265 return idx;
266 }
267 }
268 encodeLiteral(out, name, value);
269 return idx;
270 }
271
272 /**
273 * Try to encode the header field using dynamic table, otherwise do not encode.
274 *
275 * @param qpackAttributes {@link QpackAttributes} for the channel.
276 * @param out {@link ByteBuf} to which encoded header field is to be written.
277 * @param base Base for the dynamic table index.
278 * @param name for the header field.
279 * @param value for the header field.
280 * @return Index in the dynamic table if the header field was encoded as a reference to the dynamic table.
281 * {@link #DYNAMIC_TABLE_ENCODE_NOT_DONE } if encoding was not done. {@link #DYNAMIC_TABLE_ENCODE_NOT_POSSIBLE }
282 * if dynamic table encoding is not possible (size constraint) and hence should not be tried for this header.
283 */
284 private int tryEncodeWithDynamicTable(QpackAttributes qpackAttributes, ByteBuf out, int base, CharSequence name,
285 CharSequence value) {
286 if (qpackAttributes.dynamicTableDisabled()) {
287 return DYNAMIC_TABLE_ENCODE_NOT_POSSIBLE;
288 }
289 assert qpackAttributes.encoderStreamAvailable();
290 final QuicStreamChannel encoderStream = qpackAttributes.encoderStream();
291
292 int idx = dynamicTable.getEntryIndex(name, value);
293 if (idx == QpackEncoderDynamicTable.NOT_FOUND) {
294 return DYNAMIC_TABLE_ENCODE_NOT_DONE;
295 }
296 if (idx >= 0) {
297 if (dynamicTable.requiresDuplication(idx, sizeOf(name, value))) {
298 idx = dynamicTable.add(name, value, sizeOf(name, value));
299 assert idx >= 0;
300 // https://www.rfc-editor.org/rfc/rfc9204.html#section-4.3.4
301 // 0 1 2 3 4 5 6 7
302 // +---+---+---+---+---+---+---+---+
303 // | 0 | 0 | 0 | Index (5+) |
304 // +---+---+---+-------------------+
305 ByteBuf duplicate = encoderStream.alloc().buffer(8);
306 encodePrefixedInteger(duplicate, (byte) 0b0000_0000, 5,
307 dynamicTable.relativeIndexForEncoderInstructions(idx));
308 closeOnFailure(encoderStream.writeAndFlush(duplicate));
309 if (mayNotBlockStream()) {
310 // Add to the table but do not use the entry in the header block to avoid blocking.
311 return DYNAMIC_TABLE_ENCODE_NOT_POSSIBLE;
312 }
313 }
314 if (idx >= base) {
315 encodePostBaseIndexed(out, base, idx);
316 } else {
317 encodeIndexedDynamicTable(out, base, idx);
318 }
319 } else { // name match
320 idx = -(idx + 1);
321 int addIdx = tryAddToDynamicTable(qpackAttributes, false,
322 dynamicTable.relativeIndexForEncoderInstructions(idx), name, value);
323 if (addIdx < 0) {
324 return DYNAMIC_TABLE_ENCODE_NOT_POSSIBLE;
325 }
326 idx = addIdx;
327
328 if (idx >= base) {
329 encodeLiteralWithPostBaseNameRef(out, base, idx, value);
330 } else {
331 encodeLiteralWithNameRefDynamicTable(out, base, idx, value);
332 }
333 }
334 return idx;
335 }
336
337 /**
338 * Try adding the header field to the dynamic table.
339 *
340 * @param qpackAttributes {@link QpackAttributes} for the channel.
341 * @param staticTableNameRef if {@code nameIdx} is an index in the static table.
342 * @param nameIdx Index of the name if {@code > 0}.
343 * @param name for the header field.
344 * @param value for the header field.
345 * @return Index in the dynamic table if the header field was encoded as a reference to the dynamic table,
346 * {@link #DYNAMIC_TABLE_ENCODE_NOT_DONE} otherwise.
347 */
348 private int tryAddToDynamicTable(QpackAttributes qpackAttributes, boolean staticTableNameRef, int nameIdx,
349 CharSequence name, CharSequence value) {
350 if (qpackAttributes.dynamicTableDisabled()) {
351 return DYNAMIC_TABLE_ENCODE_NOT_POSSIBLE;
352 }
353 assert qpackAttributes.encoderStreamAvailable();
354 final QuicStreamChannel encoderStream = qpackAttributes.encoderStream();
355
356 int idx = dynamicTable.add(name, value, sizeOf(name, value));
357 if (idx >= 0) {
358 ByteBuf insert = null;
359 try {
360 if (nameIdx >= 0) {
361 // 2 prefixed integers (name index and value length) each requires a maximum of 8 bytes
362 insert = encoderStream.alloc().buffer(value.length() + 16);
363 // https://www.rfc-editor.org/rfc/rfc9204.html#name-insert-with-name-reference
364 // 0 1 2 3 4 5 6 7
365 // +---+---+---+---+---+---+---+---+
366 // | 1 | T | Name Index (6+) |
367 // +---+---+-----------------------+
368 encodePrefixedInteger(insert, (byte) (staticTableNameRef ? 0b1100_0000 : 0b1000_0000), 6, nameIdx);
369 } else {
370 // 2 prefixed integers (name and value length) each requires a maximum of 8 bytes
371 insert = encoderStream.alloc().buffer(name.length() + value.length() + 16);
372 // https://www.rfc-editor.org/rfc/rfc9204.html#name-insert-with-literal-name
373 // 0 1 2 3 4 5 6 7
374 // +---+---+---+---+---+---+---+---+
375 // | 0 | 1 | H | Name Length (5+) |
376 // +---+---+---+-------------------+
377 // | Name String (Length bytes) |
378 // +---+---------------------------+
379 // TODO: Force H = 1 till we support sensitivity detector
380 encodeLengthPrefixedHuffmanEncodedLiteral(insert, (byte) 0b0110_0000, 5, name);
381 }
382 // 0 1 2 3 4 5 6 7
383 // +---+---+-----------------------+
384 // | H | Value Length (7+) |
385 // +---+---------------------------+
386 // | Value String (Length bytes) |
387 // +-------------------------------+
388 encodeStringLiteral(insert, value);
389 } catch (Exception e) {
390 ReferenceCountUtil.release(insert);
391 return DYNAMIC_TABLE_ENCODE_NOT_DONE;
392 }
393 closeOnFailure(encoderStream.writeAndFlush(insert));
394 if (mayNotBlockStream()) {
395 // Add to the table but do not use the entry in the header block to avoid blocking.
396 return DYNAMIC_TABLE_ENCODE_NOT_DONE;
397 }
398 blockedStreams++;
399 }
400 return idx;
401 }
402
403 private void encodeIndexedStaticTable(ByteBuf out, int index) {
404 // https://www.rfc-editor.org/rfc/rfc9204.html#name-indexed-field-line
405 // 0 1 2 3 4 5 6 7
406 // +---+---+---+---+---+---+---+---+
407 // | 1 | T | Index (6+) |
408 // +---+---+-----------------------+
409 encodePrefixedInteger(out, (byte) 0b1100_0000, 6, index);
410 }
411
412 private void encodeIndexedDynamicTable(ByteBuf out, int base, int index) {
413 // https://www.rfc-editor.org/rfc/rfc9204.html#name-indexed-field-line
414 // 0 1 2 3 4 5 6 7
415 // +---+---+---+---+---+---+---+---+
416 // | 1 | T | Index (6+) |
417 // +---+---+-----------------------+
418 encodePrefixedInteger(out, (byte) 0b1000_0000, 6, base - index - 1);
419 }
420
421 private void encodePostBaseIndexed(ByteBuf out, int base, int index) {
422 // https://www.rfc-editor.org/rfc/rfc9204.html#name-indexed-field-line-with-pos
423 // 0 1 2 3 4 5 6 7
424 // +---+---+---+---+---+---+---+---+
425 // | 0 | 0 | 0 | 1 | Index (4+) |
426 // +---+---+---+---+---------------+
427 encodePrefixedInteger(out, (byte) 0b0001_0000, 4, index - base);
428 }
429
430 private void encodeLiteralWithNameRefStaticTable(ByteBuf out, int nameIndex, CharSequence value) {
431 // https://www.rfc-editor.org/rfc/rfc9204.html#name-literal-field-line-with-nam
432 // 0 1 2 3 4 5 6 7
433 // +---+---+---+---+---+---+---+---+
434 // | 0 | 1 | N | T |Name Index (4+)|
435 // +---+---+---+---+---------------+
436 // | H | Value Length (7+) |
437 // +---+---------------------------+
438 // | Value String (Length bytes) |
439 // +-------------------------------+
440 // TODO: Force N = 0 till we support sensitivity detector
441 encodePrefixedInteger(out, (byte) 0b0101_0000, 4, nameIndex);
442 encodeStringLiteral(out, value);
443 }
444
445 private void encodeLiteralWithNameRefDynamicTable(ByteBuf out, int base, int nameIndex, CharSequence value) {
446 // https://www.rfc-editor.org/rfc/rfc9204.html#name-literal-field-line-with-nam
447 // 0 1 2 3 4 5 6 7
448 // +---+---+---+---+---+---+---+---+
449 // | 0 | 1 | N | T |Name Index (4+)|
450 // +---+---+---+---+---------------+
451 // | H | Value Length (7+) |
452 // +---+---------------------------+
453 // | Value String (Length bytes) |
454 // +-------------------------------+
455 // TODO: Force N = 0 till we support sensitivity detector
456 encodePrefixedInteger(out, (byte) 0b0101_0000, 4, base - nameIndex - 1);
457 encodeStringLiteral(out, value);
458 }
459
460 private void encodeLiteralWithPostBaseNameRef(ByteBuf out, int base, int nameIndex, CharSequence value) {
461 // https://www.rfc-editor.org/rfc/rfc9204.html#name-literal-field-line-with-pos
462 // 0 1 2 3 4 5 6 7
463 // +---+---+---+---+---+---+---+---+
464 // | 0 | 0 | 0 | 0 | N |NameIdx(3+)|
465 // +---+---+---+---+---+-----------+
466 // | H | Value Length (7+) |
467 // +---+---------------------------+
468 // | Value String (Length bytes) |
469 // +-------------------------------+
470 // TODO: Force N = 0 till we support sensitivity detector
471 encodePrefixedInteger(out, (byte) 0b0000_0000, 4, nameIndex - base);
472 encodeStringLiteral(out, value);
473 }
474
475 private void encodeLiteral(ByteBuf out, CharSequence name, CharSequence value) {
476 // https://www.rfc-editor.org/rfc/rfc9204.html#name-literal-field-line-with-lit
477 // 0 1 2 3 4 5 6 7
478 // +---+---+---+---+---+---+---+---+
479 // | 0 | 0 | 1 | N | H |NameLen(3+)|
480 // +---+---+---+---+---+-----------+
481 // | Name String (Length bytes) |
482 // +---+---------------------------+
483 // | H | Value Length (7+) |
484 // +---+---------------------------+
485 // | Value String (Length bytes) |
486 // +-------------------------------+
487 // TODO: Force N = 0 & H = 1 till we support sensitivity detector
488 encodeLengthPrefixedHuffmanEncodedLiteral(out, (byte) 0b0010_1000, 3, name);
489 encodeStringLiteral(out, value);
490 }
491
492 /**
493 * Encode string literal according to Section 5.2.
494 * <a href="https://tools.ietf.org/html/rfc7541#section-5.2">Section 5.2</a>.
495 */
496 private void encodeStringLiteral(ByteBuf out, CharSequence value) {
497 // 0 1 2 3 4 5 6 7
498 // +---+---+---+---+---+---+---+---+
499 // | H | String Length (7+) |
500 // +---+---------------------------+
501 // | String Data (Length octets) |
502 // +-------------------------------+
503 // TODO: Force H = 1 till we support sensitivity detector
504 encodeLengthPrefixedHuffmanEncodedLiteral(out, (byte) 0b1000_0000, 7, value);
505 }
506
507 /**
508 * Encode a string literal.
509 */
510 private void encodeLengthPrefixedHuffmanEncodedLiteral(ByteBuf out, byte mask, int prefix, CharSequence value) {
511 int huffmanLength = huffmanEncoder.getEncodedLength(value);
512 encodePrefixedInteger(out, mask, prefix, huffmanLength);
513 huffmanEncoder.encode(out, value);
514 }
515
516 private boolean mayNotBlockStream() {
517 return blockedStreams >= maxBlockedStreams - 1;
518 }
519
520 private static final class Indices {
521 private int idx;
522 // Let's just assume 4 indices for now that we will store here as max.
523 private int[] array = new int[4];
524
525 void add(int index) {
526 if (idx == array.length) {
527 // Double it if needed.
528 array = Arrays.copyOf(array, array.length << 1);
529 }
530 array[idx++] = index;
531 }
532
533 void forEach(IndexConsumer consumer) throws QpackException {
534 for (int i = 0; i < idx; i++) {
535 consumer.accept(array[i]);
536 }
537 }
538
539 @FunctionalInterface
540 interface IndexConsumer {
541 void accept(int idx) throws QpackException;
542 }
543 }
544 }