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