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    *   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  
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   *     https://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.handler.codec.http2.Http2HeadersEncoder.SensitivityDetector;
37  import io.netty.util.AsciiString;
38  import io.netty.util.CharsetUtil;
39  
40  import java.util.Arrays;
41  import java.util.Map;
42  
43  import static io.netty.handler.codec.http2.HpackUtil.equalsConstantTime;
44  import static io.netty.handler.codec.http2.HpackUtil.equalsVariableTime;
45  import static io.netty.handler.codec.http2.Http2CodecUtil.DEFAULT_HEADER_TABLE_SIZE;
46  import static io.netty.handler.codec.http2.Http2CodecUtil.MAX_HEADER_LIST_SIZE;
47  import static io.netty.handler.codec.http2.Http2CodecUtil.MAX_HEADER_TABLE_SIZE;
48  import static io.netty.handler.codec.http2.Http2CodecUtil.MIN_HEADER_LIST_SIZE;
49  import static io.netty.handler.codec.http2.Http2CodecUtil.MIN_HEADER_TABLE_SIZE;
50  import static io.netty.handler.codec.http2.Http2CodecUtil.headerListSizeExceeded;
51  import static io.netty.handler.codec.http2.Http2Error.PROTOCOL_ERROR;
52  import static io.netty.handler.codec.http2.Http2Exception.connectionError;
53  import static io.netty.util.internal.MathUtil.findNextPositivePowerOfTwo;
54  import static java.lang.Math.max;
55  import static java.lang.Math.min;
56  
57  /**
58   * An HPACK encoder.
59   *
60   * <p>Implementation note:  This class is security sensitive, and depends on users correctly identifying their headers
61   * as security sensitive or not.  If a header is considered not sensitive, methods names "insensitive" are used which
62   * are fast, but don't provide any security guarantees.
63   */
64  final class HpackEncoder {
65      static final int NOT_FOUND = -1;
66      static final int HUFF_CODE_THRESHOLD = 512;
67      // a linked hash map of header fields
68      private final HeaderEntry[] headerFields;
69      private final HeaderEntry head = new HeaderEntry(-1, AsciiString.EMPTY_STRING,
70              AsciiString.EMPTY_STRING, Integer.MAX_VALUE, null);
71      private final HpackHuffmanEncoder hpackHuffmanEncoder = new HpackHuffmanEncoder();
72      private final byte hashMask;
73      private final boolean ignoreMaxHeaderListSize;
74      private final int huffCodeThreshold;
75      private long size;
76      private long maxHeaderTableSize;
77      private long maxHeaderListSize;
78  
79      /**
80       * Creates a new encoder.
81       */
82      HpackEncoder() {
83          this(false);
84      }
85  
86      /**
87       * Creates a new encoder.
88       */
89      HpackEncoder(boolean ignoreMaxHeaderListSize) {
90          this(ignoreMaxHeaderListSize, 16, HUFF_CODE_THRESHOLD);
91      }
92  
93      /**
94       * Creates a new encoder.
95       */
96      HpackEncoder(boolean ignoreMaxHeaderListSize, int arraySizeHint, int huffCodeThreshold) {
97          this.ignoreMaxHeaderListSize = ignoreMaxHeaderListSize;
98          maxHeaderTableSize = DEFAULT_HEADER_TABLE_SIZE;
99          maxHeaderListSize = MAX_HEADER_LIST_SIZE;
100         // Enforce a bound of [2, 128] because hashMask is a byte. The max possible value of hashMask is one less
101         // than the length of this array, and we want the mask to be > 0.
102         headerFields = new HeaderEntry[findNextPositivePowerOfTwo(max(2, min(arraySizeHint, 128)))];
103         hashMask = (byte) (headerFields.length - 1);
104         head.before = head.after = head;
105         this.huffCodeThreshold = huffCodeThreshold;
106     }
107 
108     /**
109      * Encode the header field into the header block.
110      *
111      * <strong>The given {@link CharSequence}s must be immutable!</strong>
112      */
113     public void encodeHeaders(int streamId, ByteBuf out, Http2Headers headers, SensitivityDetector sensitivityDetector)
114             throws Http2Exception {
115         if (ignoreMaxHeaderListSize) {
116             encodeHeadersIgnoreMaxHeaderListSize(out, headers, sensitivityDetector);
117         } else {
118             encodeHeadersEnforceMaxHeaderListSize(streamId, out, headers, sensitivityDetector);
119         }
120     }
121 
122     private void encodeHeadersEnforceMaxHeaderListSize(int streamId, ByteBuf out, Http2Headers headers,
123                                                        SensitivityDetector sensitivityDetector)
124             throws Http2Exception {
125         long headerSize = 0;
126         // To ensure we stay consistent with our peer check the size is valid before we potentially modify HPACK state.
127         for (Map.Entry<CharSequence, CharSequence> header : headers) {
128             CharSequence name = header.getKey();
129             CharSequence value = header.getValue();
130             // OK to increment now and check for bounds after because this value is limited to unsigned int and will not
131             // overflow.
132             headerSize += HpackHeaderField.sizeOf(name, value);
133             if (headerSize > maxHeaderListSize) {
134                 headerListSizeExceeded(streamId, maxHeaderListSize, false);
135             }
136         }
137         encodeHeadersIgnoreMaxHeaderListSize(out, headers, sensitivityDetector);
138     }
139 
140     private void encodeHeadersIgnoreMaxHeaderListSize(ByteBuf out, Http2Headers headers,
141                                                       SensitivityDetector sensitivityDetector) throws Http2Exception {
142         for (Map.Entry<CharSequence, CharSequence> header : headers) {
143             CharSequence name = header.getKey();
144             CharSequence value = header.getValue();
145             encodeHeader(out, name, value, sensitivityDetector.isSensitive(name, value),
146                          HpackHeaderField.sizeOf(name, value));
147         }
148     }
149 
150     /**
151      * Encode the header field into the header block.
152      *
153      * <strong>The given {@link CharSequence}s must be immutable!</strong>
154      */
155     private void encodeHeader(ByteBuf out, CharSequence name, CharSequence value, boolean sensitive, long headerSize) {
156         // If the header value is sensitive then it must never be indexed
157         if (sensitive) {
158             int nameIndex = getNameIndex(name);
159             encodeLiteral(out, name, value, IndexType.NEVER, nameIndex);
160             return;
161         }
162 
163         // If the peer will only use the static table
164         if (maxHeaderTableSize == 0) {
165             int staticTableIndex = HpackStaticTable.getIndexInsensitive(name, value);
166             if (staticTableIndex == HpackStaticTable.NOT_FOUND) {
167                 int nameIndex = HpackStaticTable.getIndex(name);
168                 encodeLiteral(out, name, value, IndexType.NONE, nameIndex);
169             } else {
170                 encodeInteger(out, 0x80, 7, staticTableIndex);
171             }
172             return;
173         }
174 
175         // If the headerSize is greater than the max table size then it must be encoded literally
176         if (headerSize > maxHeaderTableSize) {
177             int nameIndex = getNameIndex(name);
178             encodeLiteral(out, name, value, IndexType.NONE, nameIndex);
179             return;
180         }
181 
182         HeaderEntry headerField = getEntryInsensitive(name, value);
183         if (headerField != null) {
184             int index = getIndex(headerField.index) + HpackStaticTable.length;
185             // Section 6.1. Indexed Header Field Representation
186             encodeInteger(out, 0x80, 7, index);
187         } else {
188             int staticTableIndex = HpackStaticTable.getIndexInsensitive(name, value);
189             if (staticTableIndex != HpackStaticTable.NOT_FOUND) {
190                 // Section 6.1. Indexed Header Field Representation
191                 encodeInteger(out, 0x80, 7, staticTableIndex);
192             } else {
193                 ensureCapacity(headerSize);
194                 encodeLiteral(out, name, value, IndexType.INCREMENTAL, getNameIndex(name));
195                 add(name, value, headerSize);
196             }
197         }
198     }
199 
200     /**
201      * Set the maximum table size.
202      */
203     public void setMaxHeaderTableSize(ByteBuf out, long maxHeaderTableSize) throws Http2Exception {
204         if (maxHeaderTableSize < MIN_HEADER_TABLE_SIZE || maxHeaderTableSize > MAX_HEADER_TABLE_SIZE) {
205             throw connectionError(PROTOCOL_ERROR, "Header Table Size must be >= %d and <= %d but was %d",
206                     MIN_HEADER_TABLE_SIZE, MAX_HEADER_TABLE_SIZE, maxHeaderTableSize);
207         }
208         if (this.maxHeaderTableSize == maxHeaderTableSize) {
209             return;
210         }
211         this.maxHeaderTableSize = maxHeaderTableSize;
212         ensureCapacity(0);
213         // Casting to integer is safe as we verified the maxHeaderTableSize is a valid unsigned int.
214         encodeInteger(out, 0x20, 5, maxHeaderTableSize);
215     }
216 
217     /**
218      * Return the maximum table size.
219      */
220     public long getMaxHeaderTableSize() {
221         return maxHeaderTableSize;
222     }
223 
224     public void setMaxHeaderListSize(long maxHeaderListSize) throws Http2Exception {
225         if (maxHeaderListSize < MIN_HEADER_LIST_SIZE || maxHeaderListSize > MAX_HEADER_LIST_SIZE) {
226             throw connectionError(PROTOCOL_ERROR, "Header List Size must be >= %d and <= %d but was %d",
227                     MIN_HEADER_LIST_SIZE, MAX_HEADER_LIST_SIZE, maxHeaderListSize);
228         }
229         this.maxHeaderListSize = maxHeaderListSize;
230     }
231 
232     public long getMaxHeaderListSize() {
233         return maxHeaderListSize;
234     }
235 
236     /**
237      * Encode integer according to <a href="https://tools.ietf.org/html/rfc7541#section-5.1">Section 5.1</a>.
238      */
239     private static void encodeInteger(ByteBuf out, int mask, int n, int i) {
240         encodeInteger(out, mask, n, (long) i);
241     }
242 
243     /**
244      * Encode integer according to <a href="https://tools.ietf.org/html/rfc7541#section-5.1">Section 5.1</a>.
245      */
246     private static void encodeInteger(ByteBuf out, int mask, int n, long i) {
247         assert n >= 0 && n <= 8 : "N: " + n;
248         int nbits = 0xFF >>> 8 - n;
249         if (i < nbits) {
250             out.writeByte((int) (mask | i));
251         } else {
252             out.writeByte(mask | nbits);
253             long length = i - nbits;
254             for (; (length & ~0x7F) != 0; length >>>= 7) {
255                 out.writeByte((int) (length & 0x7F | 0x80));
256             }
257             out.writeByte((int) length);
258         }
259     }
260 
261     /**
262      * Encode string literal according to Section 5.2.
263      */
264     private void encodeStringLiteral(ByteBuf out, CharSequence string) {
265         int huffmanLength;
266         if (string.length() >= huffCodeThreshold
267                 && (huffmanLength = hpackHuffmanEncoder.getEncodedLength(string)) < string.length()) {
268             encodeInteger(out, 0x80, 7, huffmanLength);
269             hpackHuffmanEncoder.encode(out, string);
270         } else {
271             encodeInteger(out, 0x00, 7, string.length());
272             if (string instanceof AsciiString) {
273                 // Fast-path
274                 AsciiString asciiString = (AsciiString) string;
275                 out.writeBytes(asciiString.array(), asciiString.arrayOffset(), asciiString.length());
276             } else {
277                 // Only ASCII is allowed in http2 headers, so its fine to use this.
278                 // https://tools.ietf.org/html/rfc7540#section-8.1.2
279                 out.writeCharSequence(string, CharsetUtil.ISO_8859_1);
280             }
281         }
282     }
283 
284     /**
285      * Encode literal header field according to Section 6.2.
286      */
287     private void encodeLiteral(ByteBuf out, CharSequence name, CharSequence value, IndexType indexType,
288                                int nameIndex) {
289         boolean nameIndexValid = nameIndex != NOT_FOUND;
290         switch (indexType) {
291             case INCREMENTAL:
292                 encodeInteger(out, 0x40, 6, nameIndexValid ? nameIndex : 0);
293                 break;
294             case NONE:
295                 encodeInteger(out, 0x00, 4, nameIndexValid ? nameIndex : 0);
296                 break;
297             case NEVER:
298                 encodeInteger(out, 0x10, 4, nameIndexValid ? nameIndex : 0);
299                 break;
300             default:
301                 throw new Error("should not reach here");
302         }
303         if (!nameIndexValid) {
304             encodeStringLiteral(out, name);
305         }
306         encodeStringLiteral(out, value);
307     }
308 
309     private int getNameIndex(CharSequence name) {
310         int index = HpackStaticTable.getIndex(name);
311         if (index == HpackStaticTable.NOT_FOUND) {
312             index = getIndex(name);
313             if (index >= 0) {
314                 index += HpackStaticTable.length;
315             }
316         }
317         return index;
318     }
319 
320     /**
321      * Ensure that the dynamic table has enough room to hold 'headerSize' more bytes. Removes the
322      * oldest entry from the dynamic table until sufficient space is available.
323      */
324     private void ensureCapacity(long headerSize) {
325         while (maxHeaderTableSize - size < headerSize) {
326             int index = length();
327             if (index == 0) {
328                 break;
329             }
330             remove();
331         }
332     }
333 
334     /**
335      * Return the number of header fields in the dynamic table. Exposed for testing.
336      */
337     int length() {
338         return size == 0 ? 0 : head.after.index - head.before.index + 1;
339     }
340 
341     /**
342      * Return the size of the dynamic table. Exposed for testing.
343      */
344     long size() {
345         return size;
346     }
347 
348     /**
349      * Return the header field at the given index. Exposed for testing.
350      */
351     HpackHeaderField getHeaderField(int index) {
352         HeaderEntry entry = head;
353         while (index-- >= 0) {
354             entry = entry.before;
355         }
356         return entry;
357     }
358 
359     /**
360      * Returns the header entry with the lowest index value for the header field. Returns null if
361      * header field is not in the dynamic table.
362      */
363     private HeaderEntry getEntryInsensitive(CharSequence name, CharSequence value) {
364         if (length() == 0 || name == null || value == null) {
365             return null;
366         }
367         int h = AsciiString.hashCode(name);
368         int i = index(h);
369         for (HeaderEntry e = headerFields[i]; e != null; e = e.next) {
370             // Check the value before then name, as it is more likely the value will be different incase there is no
371             // match.
372             if (e.hash == h && equalsVariableTime(value, e.value) && equalsVariableTime(name, e.name)) {
373                 return e;
374             }
375         }
376         return null;
377     }
378 
379     /**
380      * Returns the lowest index value for the header field name in the dynamic table. Returns -1 if
381      * the header field name is not in the dynamic table.
382      */
383     private int getIndex(CharSequence name) {
384         if (length() == 0 || name == null) {
385             return NOT_FOUND;
386         }
387         int h = AsciiString.hashCode(name);
388         int i = index(h);
389         for (HeaderEntry e = headerFields[i]; e != null; e = e.next) {
390             if (e.hash == h && equalsConstantTime(name, e.name) != 0) {
391                 return getIndex(e.index);
392             }
393         }
394         return NOT_FOUND;
395     }
396 
397     /**
398      * Compute the index into the dynamic table given the index in the header entry.
399      */
400     private int getIndex(int index) {
401         return index == NOT_FOUND ? NOT_FOUND : index - head.before.index + 1;
402     }
403 
404     /**
405      * Add the header field to the dynamic table. Entries are evicted from the dynamic table until
406      * the size of the table and the new header field is less than the table's maxHeaderTableSize. If the size
407      * of the new entry is larger than the table's maxHeaderTableSize, the dynamic table will be cleared.
408      */
409     private void add(CharSequence name, CharSequence value, long headerSize) {
410         // Clear the table if the header field size is larger than the maxHeaderTableSize.
411         if (headerSize > maxHeaderTableSize) {
412             clear();
413             return;
414         }
415 
416         // Evict oldest entries until we have enough maxHeaderTableSize.
417         while (maxHeaderTableSize - size < headerSize) {
418             remove();
419         }
420 
421         int h = AsciiString.hashCode(name);
422         int i = index(h);
423         HeaderEntry old = headerFields[i];
424         HeaderEntry e = new HeaderEntry(h, name, value, head.before.index - 1, old);
425         headerFields[i] = e;
426         e.addBefore(head);
427         size += headerSize;
428     }
429 
430     /**
431      * Remove and return the oldest header field from the dynamic table.
432      */
433     private HpackHeaderField remove() {
434         if (size == 0) {
435             return null;
436         }
437         HeaderEntry eldest = head.after;
438         int h = eldest.hash;
439         int i = index(h);
440         HeaderEntry prev = headerFields[i];
441         HeaderEntry e = prev;
442         while (e != null) {
443             HeaderEntry next = e.next;
444             if (e == eldest) {
445                 if (prev == eldest) {
446                     headerFields[i] = next;
447                 } else {
448                     prev.next = next;
449                 }
450                 eldest.remove();
451                 size -= eldest.size();
452                 return eldest;
453             }
454             prev = e;
455             e = next;
456         }
457         return null;
458     }
459 
460     /**
461      * Remove all entries from the dynamic table.
462      */
463     private void clear() {
464         Arrays.fill(headerFields, null);
465         head.before = head.after = head;
466         size = 0;
467     }
468 
469     /**
470      * Returns the index into the hash table for the hash code h.
471      */
472     private int index(int h) {
473         return h & hashMask;
474     }
475 
476     /**
477      * A linked hash map HpackHeaderField entry.
478      */
479     private static final class HeaderEntry extends HpackHeaderField {
480         // These fields comprise the doubly linked list used for iteration.
481         HeaderEntry before, after;
482 
483         // These fields comprise the chained list for header fields with the same hash.
484         HeaderEntry next;
485         int hash;
486 
487         // This is used to compute the index in the dynamic table.
488         int index;
489 
490         /**
491          * Creates new entry.
492          */
493         HeaderEntry(int hash, CharSequence name, CharSequence value, int index, HeaderEntry next) {
494             super(name, value);
495             this.index = index;
496             this.hash = hash;
497             this.next = next;
498         }
499 
500         /**
501          * Removes this entry from the linked list.
502          */
503         private void remove() {
504             before.after = after;
505             after.before = before;
506             before = null; // null references to prevent nepotism in generational GC.
507             after = null;
508             next = null;
509         }
510 
511         /**
512          * Inserts this entry before the specified existing entry in the list.
513          */
514         private void addBefore(HeaderEntry existingEntry) {
515             after = existingEntry;
516             before = existingEntry.before;
517             before.after = this;
518             after.before = this;
519         }
520     }
521 }