View Javadoc
1   /*
2    * Copyright 2015 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    *   http://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  
17  /*
18   * Copyright 2014 Twitter, Inc.
19   *
20   * Licensed under the Apache License, Version 2.0 (the "License");
21   * you may not use this file except in compliance with the License.
22   * You may obtain a copy of the License at
23   *
24   *     http://www.apache.org/licenses/LICENSE-2.0
25   *
26   * Unless required by applicable law or agreed to in writing, software
27   * distributed under the License is distributed on an "AS IS" BASIS,
28   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
29   * See the License for the specific language governing permissions and
30   * limitations under the License.
31   */
32  package io.netty.handler.codec.http2;
33  
34  import io.netty.buffer.ByteBuf;
35  import io.netty.handler.codec.http2.HpackUtil.IndexType;
36  import io.netty.util.AsciiString;
37  
38  import static io.netty.handler.codec.http2.Http2CodecUtil.DEFAULT_HEADER_TABLE_SIZE;
39  import static io.netty.handler.codec.http2.Http2CodecUtil.MAX_HEADER_LIST_SIZE;
40  import static io.netty.handler.codec.http2.Http2CodecUtil.MAX_HEADER_TABLE_SIZE;
41  import static io.netty.handler.codec.http2.Http2CodecUtil.MIN_HEADER_LIST_SIZE;
42  import static io.netty.handler.codec.http2.Http2CodecUtil.MIN_HEADER_TABLE_SIZE;
43  import static io.netty.handler.codec.http2.Http2CodecUtil.headerListSizeExceeded;
44  import static io.netty.handler.codec.http2.Http2Error.COMPRESSION_ERROR;
45  import static io.netty.handler.codec.http2.Http2Error.INTERNAL_ERROR;
46  import static io.netty.handler.codec.http2.Http2Error.PROTOCOL_ERROR;
47  import static io.netty.handler.codec.http2.Http2Exception.connectionError;
48  import static io.netty.util.AsciiString.EMPTY_STRING;
49  import static io.netty.util.internal.ObjectUtil.checkPositive;
50  import static io.netty.util.internal.ThrowableUtil.unknownStackTrace;
51  
52  final class HpackDecoder {
53      private static final Http2Exception DECODE_ULE_128_DECOMPRESSION_EXCEPTION = unknownStackTrace(
54              connectionError(COMPRESSION_ERROR, "HPACK - decompression failure"), HpackDecoder.class,
55              "decodeULE128(..)");
56      private static final Http2Exception DECODE_ULE_128_TO_LONG_DECOMPRESSION_EXCEPTION = unknownStackTrace(
57              connectionError(COMPRESSION_ERROR, "HPACK - long overflow"), HpackDecoder.class, "decodeULE128(..)");
58      private static final Http2Exception DECODE_ULE_128_TO_INT_DECOMPRESSION_EXCEPTION = unknownStackTrace(
59              connectionError(COMPRESSION_ERROR, "HPACK - int overflow"), HpackDecoder.class, "decodeULE128ToInt(..)");
60      private static final Http2Exception DECODE_ILLEGAL_INDEX_VALUE = unknownStackTrace(
61              connectionError(COMPRESSION_ERROR, "HPACK - illegal index value"), HpackDecoder.class, "decode(..)");
62      private static final Http2Exception INDEX_HEADER_ILLEGAL_INDEX_VALUE = unknownStackTrace(
63              connectionError(COMPRESSION_ERROR, "HPACK - illegal index value"), HpackDecoder.class, "indexHeader(..)");
64      private static final Http2Exception READ_NAME_ILLEGAL_INDEX_VALUE = unknownStackTrace(
65              connectionError(COMPRESSION_ERROR, "HPACK - illegal index value"), HpackDecoder.class, "readName(..)");
66      private static final Http2Exception INVALID_MAX_DYNAMIC_TABLE_SIZE = unknownStackTrace(
67              connectionError(COMPRESSION_ERROR, "HPACK - invalid max dynamic table size"), HpackDecoder.class,
68              "setDynamicTableSize(..)");
69      private static final Http2Exception MAX_DYNAMIC_TABLE_SIZE_CHANGE_REQUIRED = unknownStackTrace(
70              connectionError(COMPRESSION_ERROR, "HPACK - max dynamic table size change required"), HpackDecoder.class,
71              "decode(..)");
72      private static final byte READ_HEADER_REPRESENTATION = 0;
73      private static final byte READ_MAX_DYNAMIC_TABLE_SIZE = 1;
74      private static final byte READ_INDEXED_HEADER = 2;
75      private static final byte READ_INDEXED_HEADER_NAME = 3;
76      private static final byte READ_LITERAL_HEADER_NAME_LENGTH_PREFIX = 4;
77      private static final byte READ_LITERAL_HEADER_NAME_LENGTH = 5;
78      private static final byte READ_LITERAL_HEADER_NAME = 6;
79      private static final byte READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX = 7;
80      private static final byte READ_LITERAL_HEADER_VALUE_LENGTH = 8;
81      private static final byte READ_LITERAL_HEADER_VALUE = 9;
82  
83      private final HpackDynamicTable hpackDynamicTable;
84      private final HpackHuffmanDecoder hpackHuffmanDecoder;
85      private long maxHeaderListSizeGoAway;
86      private long maxHeaderListSize;
87      private long maxDynamicTableSize;
88      private long encoderMaxDynamicTableSize;
89      private boolean maxDynamicTableSizeChangeRequired;
90  
91      /**
92       * Create a new instance.
93       * @param maxHeaderListSize This is the only setting that can be configured before notifying the peer.
94       *  This is because <a href="https://tools.ietf.org/html/rfc7540#section-6.5.1">SETTINGS_MAX_HEADER_LIST_SIZE</a>
95       *  allows a lower than advertised limit from being enforced, and the default limit is unlimited
96       *  (which is dangerous).
97       * @param initialHuffmanDecodeCapacity Size of an intermediate buffer used during huffman decode.
98       */
99      HpackDecoder(long maxHeaderListSize, int initialHuffmanDecodeCapacity) {
100         this(maxHeaderListSize, initialHuffmanDecodeCapacity, DEFAULT_HEADER_TABLE_SIZE);
101     }
102 
103     /**
104      * Exposed Used for testing only! Default values used in the initial settings frame are overridden intentionally
105      * for testing but violate the RFC if used outside the scope of testing.
106      */
107     HpackDecoder(long maxHeaderListSize, int initialHuffmanDecodeCapacity, int maxHeaderTableSize) {
108         this.maxHeaderListSize = checkPositive(maxHeaderListSize, "maxHeaderListSize");
109         this.maxHeaderListSizeGoAway = Http2CodecUtil.calculateMaxHeaderListSizeGoAway(maxHeaderListSize);
110 
111         maxDynamicTableSize = encoderMaxDynamicTableSize = maxHeaderTableSize;
112         maxDynamicTableSizeChangeRequired = false;
113         hpackDynamicTable = new HpackDynamicTable(maxHeaderTableSize);
114         hpackHuffmanDecoder = new HpackHuffmanDecoder(initialHuffmanDecodeCapacity);
115     }
116 
117     /**
118      * Decode the header block into header fields.
119      * <p>
120      * This method assumes the entire header block is contained in {@code in}.
121      */
122     public void decode(int streamId, ByteBuf in, Http2Headers headers) throws Http2Exception {
123         int index = 0;
124         long headersLength = 0;
125         int nameLength = 0;
126         int valueLength = 0;
127         byte state = READ_HEADER_REPRESENTATION;
128         boolean huffmanEncoded = false;
129         CharSequence name = null;
130         IndexType indexType = IndexType.NONE;
131         while (in.isReadable()) {
132             switch (state) {
133                 case READ_HEADER_REPRESENTATION:
134                     byte b = in.readByte();
135                     if (maxDynamicTableSizeChangeRequired && (b & 0xE0) != 0x20) {
136                         // HpackEncoder MUST signal maximum dynamic table size change
137                         throw MAX_DYNAMIC_TABLE_SIZE_CHANGE_REQUIRED;
138                     }
139                     if (b < 0) {
140                         // Indexed Header Field
141                         index = b & 0x7F;
142                         switch (index) {
143                             case 0:
144                                 throw DECODE_ILLEGAL_INDEX_VALUE;
145                             case 0x7F:
146                                 state = READ_INDEXED_HEADER;
147                                 break;
148                             default:
149                                 headersLength = indexHeader(streamId, index, headers, headersLength);
150                         }
151                     } else if ((b & 0x40) == 0x40) {
152                         // Literal Header Field with Incremental Indexing
153                         indexType = IndexType.INCREMENTAL;
154                         index = b & 0x3F;
155                         switch (index) {
156                             case 0:
157                                 state = READ_LITERAL_HEADER_NAME_LENGTH_PREFIX;
158                                 break;
159                             case 0x3F:
160                                 state = READ_INDEXED_HEADER_NAME;
161                                 break;
162                             default:
163                                 // Index was stored as the prefix
164                                 name = readName(index);
165                                 state = READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX;
166                         }
167                     } else if ((b & 0x20) == 0x20) {
168                         // Dynamic Table Size Update
169                         index = b & 0x1F;
170                         if (index == 0x1F) {
171                             state = READ_MAX_DYNAMIC_TABLE_SIZE;
172                         } else {
173                             setDynamicTableSize(index);
174                             state = READ_HEADER_REPRESENTATION;
175                         }
176                     } else {
177                         // Literal Header Field without Indexing / never Indexed
178                         indexType = ((b & 0x10) == 0x10) ? IndexType.NEVER : IndexType.NONE;
179                         index = b & 0x0F;
180                         switch (index) {
181                             case 0:
182                                 state = READ_LITERAL_HEADER_NAME_LENGTH_PREFIX;
183                                 break;
184                             case 0x0F:
185                                 state = READ_INDEXED_HEADER_NAME;
186                                 break;
187                             default:
188                             // Index was stored as the prefix
189                             name = readName(index);
190                             state = READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX;
191                         }
192                     }
193                     break;
194 
195                 case READ_MAX_DYNAMIC_TABLE_SIZE:
196                     setDynamicTableSize(decodeULE128(in, (long) index));
197                     state = READ_HEADER_REPRESENTATION;
198                     break;
199 
200                 case READ_INDEXED_HEADER:
201                     headersLength = indexHeader(streamId, decodeULE128(in, index), headers, headersLength);
202                     state = READ_HEADER_REPRESENTATION;
203                     break;
204 
205                 case READ_INDEXED_HEADER_NAME:
206                     // Header Name matches an entry in the Header Table
207                     name = readName(decodeULE128(in, index));
208                     state = READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX;
209                     break;
210 
211                 case READ_LITERAL_HEADER_NAME_LENGTH_PREFIX:
212                     b = in.readByte();
213                     huffmanEncoded = (b & 0x80) == 0x80;
214                     index = b & 0x7F;
215                     if (index == 0x7f) {
216                         state = READ_LITERAL_HEADER_NAME_LENGTH;
217                     } else {
218                         if (index > maxHeaderListSizeGoAway - headersLength) {
219                             headerListSizeExceeded(maxHeaderListSizeGoAway);
220                         }
221                         nameLength = index;
222                         state = READ_LITERAL_HEADER_NAME;
223                     }
224                     break;
225 
226                 case READ_LITERAL_HEADER_NAME_LENGTH:
227                     // Header Name is a Literal String
228                     nameLength = decodeULE128(in, index);
229 
230                     if (nameLength > maxHeaderListSizeGoAway - headersLength) {
231                         headerListSizeExceeded(maxHeaderListSizeGoAway);
232                     }
233                     state = READ_LITERAL_HEADER_NAME;
234                     break;
235 
236                 case READ_LITERAL_HEADER_NAME:
237                     // Wait until entire name is readable
238                     if (in.readableBytes() < nameLength) {
239                         throw notEnoughDataException(in);
240                     }
241 
242                     name = readStringLiteral(in, nameLength, huffmanEncoded);
243 
244                     state = READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX;
245                     break;
246 
247                 case READ_LITERAL_HEADER_VALUE_LENGTH_PREFIX:
248                     b = in.readByte();
249                     huffmanEncoded = (b & 0x80) == 0x80;
250                     index = b & 0x7F;
251                     switch (index) {
252                         case 0x7f:
253                             state = READ_LITERAL_HEADER_VALUE_LENGTH;
254                             break;
255                         case 0:
256                             headersLength = insertHeader(streamId, headers, name, EMPTY_STRING, indexType,
257                                                          headersLength);
258                             state = READ_HEADER_REPRESENTATION;
259                             break;
260                         default:
261                             // Check new header size against max header size
262                             if ((long) index + nameLength > maxHeaderListSizeGoAway - headersLength) {
263                                 headerListSizeExceeded(maxHeaderListSizeGoAway);
264                             }
265                             valueLength = index;
266                             state = READ_LITERAL_HEADER_VALUE;
267                     }
268 
269                     break;
270 
271                 case READ_LITERAL_HEADER_VALUE_LENGTH:
272                     // Header Value is a Literal String
273                     valueLength = decodeULE128(in, index);
274 
275                     // Check new header size against max header size
276                     if ((long) valueLength + nameLength > maxHeaderListSizeGoAway - headersLength) {
277                         headerListSizeExceeded(maxHeaderListSizeGoAway);
278                     }
279                     state = READ_LITERAL_HEADER_VALUE;
280                     break;
281 
282                 case READ_LITERAL_HEADER_VALUE:
283                     // Wait until entire value is readable
284                     if (in.readableBytes() < valueLength) {
285                         throw notEnoughDataException(in);
286                     }
287 
288                     CharSequence value = readStringLiteral(in, valueLength, huffmanEncoded);
289                     headersLength = insertHeader(streamId, headers, name, value, indexType, headersLength);
290                     state = READ_HEADER_REPRESENTATION;
291                     break;
292 
293                 default:
294                     throw new Error("should not reach here state: " + state);
295             }
296         }
297 
298         // we have read all of our headers, and not exceeded maxHeaderListSizeGoAway see if we have
299         // exceeded our actual maxHeaderListSize. This must be done here to prevent dynamic table
300         // corruption
301         if (headersLength > maxHeaderListSize) {
302             headerListSizeExceeded(streamId, maxHeaderListSize, true);
303         }
304     }
305 
306     /**
307      * Set the maximum table size. If this is below the maximum size of the dynamic table used by
308      * the encoder, the beginning of the next header block MUST signal this change.
309      */
310     public void setMaxHeaderTableSize(long maxHeaderTableSize) throws Http2Exception {
311         if (maxHeaderTableSize < MIN_HEADER_TABLE_SIZE || maxHeaderTableSize > MAX_HEADER_TABLE_SIZE) {
312             throw connectionError(PROTOCOL_ERROR, "Header Table Size must be >= %d and <= %d but was %d",
313                     MIN_HEADER_TABLE_SIZE, MAX_HEADER_TABLE_SIZE, maxHeaderTableSize);
314         }
315         maxDynamicTableSize = maxHeaderTableSize;
316         if (maxDynamicTableSize < encoderMaxDynamicTableSize) {
317             // decoder requires less space than encoder
318             // encoder MUST signal this change
319             maxDynamicTableSizeChangeRequired = true;
320             hpackDynamicTable.setCapacity(maxDynamicTableSize);
321         }
322     }
323 
324     public void setMaxHeaderListSize(long maxHeaderListSize, long maxHeaderListSizeGoAway) throws Http2Exception {
325         if (maxHeaderListSizeGoAway < maxHeaderListSize || maxHeaderListSizeGoAway < 0) {
326             throw connectionError(INTERNAL_ERROR, "Header List Size GO_AWAY %d must be positive and >= %d",
327                     maxHeaderListSizeGoAway, maxHeaderListSize);
328         }
329         if (maxHeaderListSize < MIN_HEADER_LIST_SIZE || maxHeaderListSize > MAX_HEADER_LIST_SIZE) {
330             throw connectionError(PROTOCOL_ERROR, "Header List Size must be >= %d and <= %d but was %d",
331                     MIN_HEADER_TABLE_SIZE, MAX_HEADER_TABLE_SIZE, maxHeaderListSize);
332         }
333         this.maxHeaderListSize = maxHeaderListSize;
334         this.maxHeaderListSizeGoAway = maxHeaderListSizeGoAway;
335     }
336 
337     public long getMaxHeaderListSize() {
338         return maxHeaderListSize;
339     }
340 
341     public long getMaxHeaderListSizeGoAway() {
342         return maxHeaderListSizeGoAway;
343     }
344 
345     /**
346      * Return the maximum table size. This is the maximum size allowed by both the encoder and the
347      * decoder.
348      */
349     public long getMaxHeaderTableSize() {
350         return hpackDynamicTable.capacity();
351     }
352 
353     /**
354      * Return the number of header fields in the dynamic table. Exposed for testing.
355      */
356     int length() {
357         return hpackDynamicTable.length();
358     }
359 
360     /**
361      * Return the size of the dynamic table. Exposed for testing.
362      */
363     long size() {
364         return hpackDynamicTable.size();
365     }
366 
367     /**
368      * Return the header field at the given index. Exposed for testing.
369      */
370     HpackHeaderField getHeaderField(int index) {
371         return hpackDynamicTable.getEntry(index + 1);
372     }
373 
374     private void setDynamicTableSize(long dynamicTableSize) throws Http2Exception {
375         if (dynamicTableSize > maxDynamicTableSize) {
376             throw INVALID_MAX_DYNAMIC_TABLE_SIZE;
377         }
378         encoderMaxDynamicTableSize = dynamicTableSize;
379         maxDynamicTableSizeChangeRequired = false;
380         hpackDynamicTable.setCapacity(dynamicTableSize);
381     }
382 
383     private CharSequence readName(int index) throws Http2Exception {
384         if (index <= HpackStaticTable.length) {
385             HpackHeaderField hpackHeaderField = HpackStaticTable.getEntry(index);
386             return hpackHeaderField.name;
387         }
388         if (index - HpackStaticTable.length <= hpackDynamicTable.length()) {
389             HpackHeaderField hpackHeaderField = hpackDynamicTable.getEntry(index - HpackStaticTable.length);
390             return hpackHeaderField.name;
391         }
392         throw READ_NAME_ILLEGAL_INDEX_VALUE;
393     }
394 
395     private long indexHeader(int streamId, int index, Http2Headers headers, long headersLength) throws Http2Exception {
396         if (index <= HpackStaticTable.length) {
397             HpackHeaderField hpackHeaderField = HpackStaticTable.getEntry(index);
398             return addHeader(streamId, headers, hpackHeaderField.name, hpackHeaderField.value, headersLength);
399         }
400         if (index - HpackStaticTable.length <= hpackDynamicTable.length()) {
401             HpackHeaderField hpackHeaderField = hpackDynamicTable.getEntry(index - HpackStaticTable.length);
402             return addHeader(streamId, headers, hpackHeaderField.name, hpackHeaderField.value, headersLength);
403         }
404         throw INDEX_HEADER_ILLEGAL_INDEX_VALUE;
405     }
406 
407     private long insertHeader(int streamId, Http2Headers headers, CharSequence name, CharSequence value,
408                               IndexType indexType, long headerSize) throws Http2Exception {
409         headerSize = addHeader(streamId, headers, name, value, headerSize);
410 
411         switch (indexType) {
412             case NONE:
413             case NEVER:
414                 break;
415 
416             case INCREMENTAL:
417                 hpackDynamicTable.add(new HpackHeaderField(name, value));
418                 break;
419 
420             default:
421                 throw new Error("should not reach here");
422         }
423 
424         return headerSize;
425     }
426 
427     private long addHeader(int streamId, Http2Headers headers, CharSequence name, CharSequence value,
428                            long headersLength) throws Http2Exception {
429         headersLength += name.length() + value.length();
430         if (headersLength > maxHeaderListSizeGoAway) {
431             headerListSizeExceeded(maxHeaderListSizeGoAway);
432         }
433         headers.add(name, value);
434         return headersLength;
435     }
436 
437     private CharSequence readStringLiteral(ByteBuf in, int length, boolean huffmanEncoded) throws Http2Exception {
438         if (huffmanEncoded) {
439             return hpackHuffmanDecoder.decode(in, length);
440         }
441         byte[] buf = new byte[length];
442         in.readBytes(buf);
443         return new AsciiString(buf, false);
444     }
445 
446     private static IllegalArgumentException notEnoughDataException(ByteBuf in) {
447         return new IllegalArgumentException("decode only works with an entire header block! " + in);
448     }
449 
450     /**
451      * Unsigned Little Endian Base 128 Variable-Length Integer Encoding
452      * <p>
453      * Visible for testing only!
454      */
455     static int decodeULE128(ByteBuf in, int result) throws Http2Exception {
456         final int readerIndex = in.readerIndex();
457         final long v = decodeULE128(in, (long) result);
458         if (v > Integer.MAX_VALUE) {
459             // the maximum value that can be represented by a signed 32 bit number is:
460             // [0x1,0x7f] + 0x7f + (0x7f << 7) + (0x7f << 14) + (0x7f << 21) + (0x6 << 28)
461             // OR
462             // 0x0 + 0x7f + (0x7f << 7) + (0x7f << 14) + (0x7f << 21) + (0x7 << 28)
463             // we should reset the readerIndex if we overflowed the int type.
464             in.readerIndex(readerIndex);
465             throw DECODE_ULE_128_TO_INT_DECOMPRESSION_EXCEPTION;
466         }
467         return (int) v;
468     }
469 
470     /**
471      * Unsigned Little Endian Base 128 Variable-Length Integer Encoding
472      * <p>
473      * Visible for testing only!
474      */
475     static long decodeULE128(ByteBuf in, long result) throws Http2Exception {
476         assert result <= 0x7f && result >= 0;
477         final boolean resultStartedAtZero = result == 0;
478         final int writerIndex = in.writerIndex();
479         for (int readerIndex = in.readerIndex(), shift = 0; readerIndex < writerIndex; ++readerIndex, shift += 7) {
480             byte b = in.getByte(readerIndex);
481             if (shift == 56 && ((b & 0x80) != 0 || b == 0x7F && !resultStartedAtZero)) {
482                 // the maximum value that can be represented by a signed 64 bit number is:
483                 // [0x01L, 0x7fL] + 0x7fL + (0x7fL << 7) + (0x7fL << 14) + (0x7fL << 21) + (0x7fL << 28) + (0x7fL << 35)
484                 // + (0x7fL << 42) + (0x7fL << 49) + (0x7eL << 56)
485                 // OR
486                 // 0x0L + 0x7fL + (0x7fL << 7) + (0x7fL << 14) + (0x7fL << 21) + (0x7fL << 28) + (0x7fL << 35) +
487                 // (0x7fL << 42) + (0x7fL << 49) + (0x7fL << 56)
488                 // this means any more shifts will result in overflow so we should break out and throw an error.
489                 throw DECODE_ULE_128_TO_LONG_DECOMPRESSION_EXCEPTION;
490             }
491 
492             if ((b & 0x80) == 0) {
493                 in.readerIndex(readerIndex + 1);
494                 return result + ((b & 0x7FL) << shift);
495             }
496             result += (b & 0x7FL) << shift;
497         }
498 
499         throw DECODE_ULE_128_DECOMPRESSION_EXCEPTION;
500     }
501 }