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