1 /*
2 * Copyright (c) 2014, 2017, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package jdk.incubator.http.internal.hpack;
26
27 import jdk.incubator.http.internal.hpack.HPACK.Logger;
28 import jdk.internal.vm.annotation.Stable;
29
30 import java.io.IOException;
31 import java.nio.ByteBuffer;
32 import java.util.concurrent.atomic.AtomicLong;
33
34 import static jdk.incubator.http.internal.hpack.HPACK.Logger.Level.EXTRA;
35 import static jdk.incubator.http.internal.hpack.HPACK.Logger.Level.NORMAL;
36 import static java.lang.String.format;
37 import static java.util.Objects.requireNonNull;
38
39 /**
40 * Decodes headers from their binary representation.
41 *
42 * <p> Typical lifecycle looks like this:
43 *
44 * <p> {@link #Decoder(int) new Decoder}
45 * ({@link #setMaxCapacity(int) setMaxCapacity}?
46 * {@link #decode(ByteBuffer, boolean, DecodingCallback) decode})*
47 *
48 * @apiNote
49 *
50 * <p> The design intentions behind Decoder were to facilitate flexible and
51 * incremental style of processing.
52 *
53 * <p> {@code Decoder} does not require a complete header block in a single
54 * {@code ByteBuffer}. The header block can be spread across many buffers of any
55 * size and decoded one-by-one the way it makes most sense for the user. This
56 * way also allows not to limit the size of the header block.
57 *
58 * <p> Headers are delivered to the {@linkplain DecodingCallback callback} as
59 * soon as they become decoded. Using the callback also gives the user a freedom
60 * to decide how headers are processed. The callback does not limit the number
61 * of headers decoded during single decoding operation.
62 *
63 * @since 9
64 */
65 public final class Decoder {
66
67 private final Logger logger;
68 private static final AtomicLong DECODERS_IDS = new AtomicLong();
69
70 @Stable
71 private static final State[] states = new State[256];
72
73 static {
74 // To be able to do a quick lookup, each of 256 possibilities are mapped
75 // to corresponding states.
76 //
77 // We can safely do this since patterns 1, 01, 001, 0001, 0000 are
78 // Huffman prefixes and therefore are inherently not ambiguous.
79 //
80 // I do it mainly for better debugging (to not go each time step by step
81 // through if...else tree). As for performance win for the decoding, I
82 // believe is negligible.
83 for (int i = 0; i < states.length; i++) {
84 if ((i & 0b1000_0000) == 0b1000_0000) {
85 states[i] = State.INDEXED;
86 } else if ((i & 0b1100_0000) == 0b0100_0000) {
87 states[i] = State.LITERAL_WITH_INDEXING;
88 } else if ((i & 0b1110_0000) == 0b0010_0000) {
89 states[i] = State.SIZE_UPDATE;
90 } else if ((i & 0b1111_0000) == 0b0001_0000) {
91 states[i] = State.LITERAL_NEVER_INDEXED;
92 } else if ((i & 0b1111_0000) == 0b0000_0000) {
93 states[i] = State.LITERAL;
94 } else {
95 throw new InternalError(String.valueOf(i));
96 }
97 }
98 }
99
100 private final long id;
101 private final HeaderTable table;
102
103 private State state = State.READY;
104 private final IntegerReader integerReader;
105 private final StringReader stringReader;
106 private final StringBuilder name;
107 private final StringBuilder value;
108 private int intValue;
109 private boolean firstValueRead;
110 private boolean firstValueIndex;
111 private boolean nameHuffmanEncoded;
112 private boolean valueHuffmanEncoded;
113 private int capacity;
114
115 /**
116 * Constructs a {@code Decoder} with the specified initial capacity of the
117 * header table.
118 *
119 * <p> The value has to be agreed between decoder and encoder out-of-band,
120 * e.g. by a protocol that uses HPACK
121 * (see <a href="https://tools.ietf.org/html/rfc7541#section-4.2">4.2. Maximum Table Size</a>).
122 *
123 * @param capacity
124 * a non-negative integer
125 *
126 * @throws IllegalArgumentException
127 * if capacity is negative
128 */
129 public Decoder(int capacity) {
130 id = DECODERS_IDS.incrementAndGet();
131 logger = HPACK.getLogger().subLogger("Decoder#" + id);
132 if (logger.isLoggable(NORMAL)) {
133 logger.log(NORMAL, () -> format("new decoder with maximum table size %s",
134 capacity));
135 }
136 if (logger.isLoggable(NORMAL)) {
137 /* To correlate with logging outside HPACK, knowing
138 hashCode/toString is important */
139 logger.log(NORMAL, () -> {
140 String hashCode = Integer.toHexString(
141 System.identityHashCode(this));
142 return format("toString='%s', identityHashCode=%s",
143 toString(), hashCode);
144 });
145 }
146 setMaxCapacity0(capacity);
147 table = new HeaderTable(capacity, logger.subLogger("HeaderTable"));
148 integerReader = new IntegerReader();
149 stringReader = new StringReader();
150 name = new StringBuilder(512);
151 value = new StringBuilder(1024);
152 }
153
154 /**
155 * Sets a maximum capacity of the header table.
156 *
157 * <p> The value has to be agreed between decoder and encoder out-of-band,
158 * e.g. by a protocol that uses HPACK
159 * (see <a href="https://tools.ietf.org/html/rfc7541#section-4.2">4.2. Maximum Table Size</a>).
160 *
161 * @param capacity
162 * a non-negative integer
163 *
164 * @throws IllegalArgumentException
165 * if capacity is negative
166 */
167 public void setMaxCapacity(int capacity) {
168 if (logger.isLoggable(NORMAL)) {
169 logger.log(NORMAL, () -> format("setting maximum table size to %s",
170 capacity));
171 }
172 setMaxCapacity0(capacity);
173 }
174
175 private void setMaxCapacity0(int capacity) {
176 if (capacity < 0) {
177 throw new IllegalArgumentException("capacity >= 0: " + capacity);
178 }
179 // FIXME: await capacity update if less than what was prior to it
180 this.capacity = capacity;
181 }
182
183 /**
184 * Decodes a header block from the given buffer to the given callback.
185 *
186 * <p> Suppose a header block is represented by a sequence of
187 * {@code ByteBuffer}s in the form of {@code Iterator<ByteBuffer>}. And the
188 * consumer of decoded headers is represented by the callback. Then to
189 * decode the header block, the following approach might be used:
190 *
191 * <pre>{@code
192 * while (buffers.hasNext()) {
193 * ByteBuffer input = buffers.next();
194 * decoder.decode(input, callback, !buffers.hasNext());
195 * }
196 * }</pre>
197 *
198 * <p> The decoder reads as much as possible of the header block from the
199 * given buffer, starting at the buffer's position, and increments its
200 * position to reflect the bytes read. The buffer's mark and limit will not
201 * be modified.
202 *
203 * <p> Once the method is invoked with {@code endOfHeaderBlock == true}, the
204 * current header block is deemed ended, and inconsistencies, if any, are
205 * reported immediately by throwing an {@code IOException}.
206 *
207 * <p> Each callback method is called only after the implementation has
208 * processed the corresponding bytes. If the bytes revealed a decoding
209 * error, the callback method is not called.
210 *
211 * <p> In addition to exceptions thrown directly by the method, any
212 * exceptions thrown from the {@code callback} will bubble up.
213 *
214 * @apiNote The method asks for {@code endOfHeaderBlock} flag instead of
215 * returning it for two reasons. The first one is that the user of the
216 * decoder always knows which chunk is the last. The second one is to throw
217 * the most detailed exception possible, which might be useful for
218 * diagnosing issues.
219 *
220 * @implNote This implementation is not atomic in respect to decoding
221 * errors. In other words, if the decoding operation has thrown a decoding
222 * error, the decoder is no longer usable.
223 *
224 * @param headerBlock
225 * the chunk of the header block, may be empty
226 * @param endOfHeaderBlock
227 * true if the chunk is the final (or the only one) in the sequence
228 *
229 * @param consumer
230 * the callback
231 * @throws IOException
232 * in case of a decoding error
233 * @throws NullPointerException
234 * if either headerBlock or consumer are null
235 */
236 public void decode(ByteBuffer headerBlock,
237 boolean endOfHeaderBlock,
238 DecodingCallback consumer) throws IOException {
239 requireNonNull(headerBlock, "headerBlock");
240 requireNonNull(consumer, "consumer");
241 if (logger.isLoggable(NORMAL)) {
242 logger.log(NORMAL, () -> format("reading %s, end of header block? %s",
243 headerBlock, endOfHeaderBlock));
244 }
245 while (headerBlock.hasRemaining()) {
246 proceed(headerBlock, consumer);
247 }
248 if (endOfHeaderBlock && state != State.READY) {
249 logger.log(NORMAL, () -> format("unexpected end of %s representation",
250 state));
251 throw new IOException("Unexpected end of header block");
252 }
253 }
254
255 private void proceed(ByteBuffer input, DecodingCallback action)
256 throws IOException {
257 switch (state) {
258 case READY:
259 resumeReady(input);
260 break;
261 case INDEXED:
262 resumeIndexed(input, action);
263 break;
264 case LITERAL:
265 resumeLiteral(input, action);
266 break;
267 case LITERAL_WITH_INDEXING:
268 resumeLiteralWithIndexing(input, action);
269 break;
270 case LITERAL_NEVER_INDEXED:
271 resumeLiteralNeverIndexed(input, action);
272 break;
273 case SIZE_UPDATE:
274 resumeSizeUpdate(input, action);
275 break;
276 default:
277 throw new InternalError("Unexpected decoder state: " + state);
278 }
279 }
280
281 private void resumeReady(ByteBuffer input) {
282 int b = input.get(input.position()) & 0xff; // absolute read
283 State s = states[b];
284 if (logger.isLoggable(EXTRA)) {
285 logger.log(EXTRA, () -> format("next binary representation %s (first byte 0x%02x)",
286 s, b));
287 }
288 switch (s) {
289 case INDEXED:
290 integerReader.configure(7);
291 state = State.INDEXED;
292 firstValueIndex = true;
293 break;
294 case LITERAL:
295 state = State.LITERAL;
296 firstValueIndex = (b & 0b0000_1111) != 0;
297 if (firstValueIndex) {
298 integerReader.configure(4);
299 }
300 break;
301 case LITERAL_WITH_INDEXING:
302 state = State.LITERAL_WITH_INDEXING;
303 firstValueIndex = (b & 0b0011_1111) != 0;
304 if (firstValueIndex) {
305 integerReader.configure(6);
306 }
307 break;
308 case LITERAL_NEVER_INDEXED:
309 state = State.LITERAL_NEVER_INDEXED;
310 firstValueIndex = (b & 0b0000_1111) != 0;
311 if (firstValueIndex) {
312 integerReader.configure(4);
313 }
314 break;
315 case SIZE_UPDATE:
316 integerReader.configure(5);
317 state = State.SIZE_UPDATE;
318 firstValueIndex = true;
319 break;
320 default:
321 throw new InternalError(String.valueOf(s));
322 }
323 if (!firstValueIndex) {
324 input.get(); // advance, next stop: "String Literal"
325 }
326 }
327
328 // 0 1 2 3 4 5 6 7
329 // +---+---+---+---+---+---+---+---+
330 // | 1 | Index (7+) |
331 // +---+---------------------------+
332 //
333 private void resumeIndexed(ByteBuffer input, DecodingCallback action)
334 throws IOException {
335 if (!integerReader.read(input)) {
336 return;
337 }
338 intValue = integerReader.get();
339 integerReader.reset();
340 if (logger.isLoggable(NORMAL)) {
341 logger.log(NORMAL, () -> format("indexed %s", intValue));
342 }
343 try {
344 HeaderTable.HeaderField f = getHeaderFieldAt(intValue);
345 action.onIndexed(intValue, f.name, f.value);
346 } finally {
347 state = State.READY;
348 }
349 }
350
351 private HeaderTable.HeaderField getHeaderFieldAt(int index)
352 throws IOException
353 {
354 HeaderTable.HeaderField f;
355 try {
356 f = table.get(index);
357 } catch (IndexOutOfBoundsException e) {
358 throw new IOException("header fields table index", e);
359 }
360 return f;
361 }
362
363 // 0 1 2 3 4 5 6 7
364 // +---+---+---+---+---+---+---+---+
365 // | 0 | 0 | 0 | 0 | Index (4+) |
366 // +---+---+-----------------------+
367 // | H | Value Length (7+) |
368 // +---+---------------------------+
369 // | Value String (Length octets) |
370 // +-------------------------------+
371 //
372 // 0 1 2 3 4 5 6 7
373 // +---+---+---+---+---+---+---+---+
374 // | 0 | 0 | 0 | 0 | 0 |
375 // +---+---+-----------------------+
376 // | H | Name Length (7+) |
377 // +---+---------------------------+
378 // | Name String (Length octets) |
379 // +---+---------------------------+
380 // | H | Value Length (7+) |
381 // +---+---------------------------+
382 // | Value String (Length octets) |
383 // +-------------------------------+
384 //
385 private void resumeLiteral(ByteBuffer input, DecodingCallback action)
386 throws IOException {
387 if (!completeReading(input)) {
388 return;
389 }
390 try {
391 if (firstValueIndex) {
392 if (logger.isLoggable(NORMAL)) {
393 logger.log(NORMAL, () -> format("literal without indexing ('%s', '%s')",
394 intValue, value));
395 }
396 HeaderTable.HeaderField f = getHeaderFieldAt(intValue);
397 action.onLiteral(intValue, f.name, value, valueHuffmanEncoded);
398 } else {
399 if (logger.isLoggable(NORMAL)) {
400 logger.log(NORMAL, () -> format("literal without indexing ('%s', '%s')",
401 name, value));
402 }
403 action.onLiteral(name, nameHuffmanEncoded, value, valueHuffmanEncoded);
404 }
405 } finally {
406 cleanUpAfterReading();
407 }
408 }
409
410 //
411 // 0 1 2 3 4 5 6 7
412 // +---+---+---+---+---+---+---+---+
413 // | 0 | 1 | Index (6+) |
414 // +---+---+-----------------------+
415 // | H | Value Length (7+) |
416 // +---+---------------------------+
417 // | Value String (Length octets) |
418 // +-------------------------------+
419 //
420 // 0 1 2 3 4 5 6 7
421 // +---+---+---+---+---+---+---+---+
422 // | 0 | 1 | 0 |
423 // +---+---+-----------------------+
424 // | H | Name Length (7+) |
425 // +---+---------------------------+
426 // | Name String (Length octets) |
427 // +---+---------------------------+
428 // | H | Value Length (7+) |
429 // +---+---------------------------+
430 // | Value String (Length octets) |
431 // +-------------------------------+
432 //
433 private void resumeLiteralWithIndexing(ByteBuffer input,
434 DecodingCallback action)
435 throws IOException {
436 if (!completeReading(input)) {
437 return;
438 }
439 try {
440 //
441 // 1. (name, value) will be stored in the table as strings
442 // 2. Most likely the callback will also create strings from them
443 // ------------------------------------------------------------------------
444 // Let's create those string beforehand (and only once!) to benefit everyone
445 //
446 String n;
447 String v = value.toString();
448 if (firstValueIndex) {
449 if (logger.isLoggable(NORMAL)) {
450 logger.log(NORMAL, () -> format("literal with incremental indexing ('%s', '%s')",
451 intValue, value));
452 }
453 HeaderTable.HeaderField f = getHeaderFieldAt(intValue);
454 n = f.name;
455 action.onLiteralWithIndexing(intValue, n, v, valueHuffmanEncoded);
456 } else {
457 n = name.toString();
458 if (logger.isLoggable(NORMAL)) {
459 logger.log(NORMAL, () -> format("literal with incremental indexing ('%s', '%s')",
460 n, value));
461 }
462 action.onLiteralWithIndexing(n, nameHuffmanEncoded, v, valueHuffmanEncoded);
463 }
464 table.put(n, v);
465 } finally {
466 cleanUpAfterReading();
467 }
468 }
469
470 // 0 1 2 3 4 5 6 7
471 // +---+---+---+---+---+---+---+---+
472 // | 0 | 0 | 0 | 1 | Index (4+) |
473 // +---+---+-----------------------+
474 // | H | Value Length (7+) |
475 // +---+---------------------------+
476 // | Value String (Length octets) |
477 // +-------------------------------+
478 //
479 // 0 1 2 3 4 5 6 7
480 // +---+---+---+---+---+---+---+---+
481 // | 0 | 0 | 0 | 1 | 0 |
482 // +---+---+-----------------------+
483 // | H | Name Length (7+) |
484 // +---+---------------------------+
485 // | Name String (Length octets) |
486 // +---+---------------------------+
487 // | H | Value Length (7+) |
488 // +---+---------------------------+
489 // | Value String (Length octets) |
490 // +-------------------------------+
491 //
492 private void resumeLiteralNeverIndexed(ByteBuffer input,
493 DecodingCallback action)
494 throws IOException {
495 if (!completeReading(input)) {
496 return;
497 }
498 try {
499 if (firstValueIndex) {
500 if (logger.isLoggable(NORMAL)) {
501 logger.log(NORMAL, () -> format("literal never indexed ('%s', '%s')",
502 intValue, value));
503 }
504 HeaderTable.HeaderField f = getHeaderFieldAt(intValue);
505 action.onLiteralNeverIndexed(intValue, f.name, value, valueHuffmanEncoded);
506 } else {
507 if (logger.isLoggable(NORMAL)) {
508 logger.log(NORMAL, () -> format("literal never indexed ('%s', '%s')",
509 name, value));
510 }
511 action.onLiteralNeverIndexed(name, nameHuffmanEncoded, value, valueHuffmanEncoded);
512 }
513 } finally {
514 cleanUpAfterReading();
515 }
516 }
517
518 // 0 1 2 3 4 5 6 7
519 // +---+---+---+---+---+---+---+---+
520 // | 0 | 0 | 1 | Max size (5+) |
521 // +---+---------------------------+
522 //
523 private void resumeSizeUpdate(ByteBuffer input,
524 DecodingCallback action) throws IOException {
525 if (!integerReader.read(input)) {
526 return;
527 }
528 intValue = integerReader.get();
529 if (logger.isLoggable(NORMAL)) {
530 logger.log(NORMAL, () -> format("dynamic table size update %s",
531 intValue));
532 }
533 assert intValue >= 0;
534 if (intValue > capacity) {
535 throw new IOException(
536 format("Received capacity exceeds expected: capacity=%s, expected=%s",
537 intValue, capacity));
538 }
539 integerReader.reset();
540 try {
541 action.onSizeUpdate(intValue);
542 table.setMaxSize(intValue);
543 } finally {
544 state = State.READY;
545 }
546 }
547
548 private boolean completeReading(ByteBuffer input) throws IOException {
549 if (!firstValueRead) {
550 if (firstValueIndex) {
551 if (!integerReader.read(input)) {
552 return false;
553 }
554 intValue = integerReader.get();
555 integerReader.reset();
556 } else {
557 if (!stringReader.read(input, name)) {
558 return false;
559 }
560 nameHuffmanEncoded = stringReader.isHuffmanEncoded();
561 stringReader.reset();
562 }
563 firstValueRead = true;
564 return false;
565 } else {
566 if (!stringReader.read(input, value)) {
567 return false;
568 }
569 }
570 valueHuffmanEncoded = stringReader.isHuffmanEncoded();
571 stringReader.reset();
572 return true;
573 }
574
575 private void cleanUpAfterReading() {
576 name.setLength(0);
577 value.setLength(0);
578 firstValueRead = false;
579 state = State.READY;
580 }
581
582 private enum State {
583 READY,
584 INDEXED,
585 LITERAL_NEVER_INDEXED,
586 LITERAL,
587 LITERAL_WITH_INDEXING,
588 SIZE_UPDATE
589 }
590
591 HeaderTable getTable() {
592 return table;
593 }
594 }