diff options
Diffstat (limited to 'jetty-http2/http2-hpack/src/main/java/org/eclipse/jetty/http2/hpack/HpackContext.java')
| -rw-r--r-- | jetty-http2/http2-hpack/src/main/java/org/eclipse/jetty/http2/hpack/HpackContext.java | 515 |
1 files changed, 515 insertions, 0 deletions
diff --git a/jetty-http2/http2-hpack/src/main/java/org/eclipse/jetty/http2/hpack/HpackContext.java b/jetty-http2/http2-hpack/src/main/java/org/eclipse/jetty/http2/hpack/HpackContext.java new file mode 100644 index 0000000000..89fbf00e4a --- /dev/null +++ b/jetty-http2/http2-hpack/src/main/java/org/eclipse/jetty/http2/hpack/HpackContext.java @@ -0,0 +1,515 @@ +// +// ======================================================================== +// Copyright (c) 1995-2016 Mort Bay Consulting Pty. Ltd. +// ------------------------------------------------------------------------ +// All rights reserved. This program and the accompanying materials +// are made available under the terms of the Eclipse Public License v1.0 +// and Apache License v2.0 which accompanies this distribution. +// +// The Eclipse Public License is available at +// http://www.eclipse.org/legal/epl-v10.html +// +// The Apache License v2.0 is available at +// http://www.opensource.org/licenses/apache2.0.php +// +// You may elect to redistribute this code under either of these licenses. +// ======================================================================== +// + +package org.eclipse.jetty.http2.hpack; + +import java.nio.ByteBuffer; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Map; +import java.util.Set; + +import org.eclipse.jetty.http.HttpField; +import org.eclipse.jetty.http.HttpHeader; +import org.eclipse.jetty.http.HttpMethod; +import org.eclipse.jetty.http.HttpScheme; +import org.eclipse.jetty.util.ArrayQueue; +import org.eclipse.jetty.util.ArrayTernaryTrie; +import org.eclipse.jetty.util.StringUtil; +import org.eclipse.jetty.util.Trie; +import org.eclipse.jetty.util.log.Log; +import org.eclipse.jetty.util.log.Logger; + + +/* ------------------------------------------------------------ */ +/** HPACK - Header Compression for HTTP/2 + * <p>This class maintains the compression context for a single HTTP/2 + * connection. Specifically it holds the static and dynamic Header Field Tables + * and the associated sizes and limits. + * </p> + * <p>It is compliant with draft 11 of the specification</p> + */ +public class HpackContext +{ + public static final Logger LOG = Log.getLogger(HpackContext.class); + + public static final String[][] STATIC_TABLE = + { + {null,null}, + /* 1 */ {":authority",null}, + /* 2 */ {":method","GET"}, + /* 3 */ {":method","POST"}, + /* 4 */ {":path","/"}, + /* 5 */ {":path","/index.html"}, + /* 6 */ {":scheme","http"}, + /* 7 */ {":scheme","https"}, + /* 8 */ {":status","200"}, + /* 9 */ {":status","204"}, + /* 10 */ {":status","206"}, + /* 11 */ {":status","304"}, + /* 12 */ {":status","400"}, + /* 13 */ {":status","404"}, + /* 14 */ {":status","500"}, + /* 15 */ {"accept-charset",null}, + /* 16 */ {"accept-encoding","gzip, deflate"}, + /* 17 */ {"accept-language",null}, + /* 18 */ {"accept-ranges",null}, + /* 19 */ {"accept",null}, + /* 20 */ {"access-control-allow-origin",null}, + /* 21 */ {"age",null}, + /* 22 */ {"allow",null}, + /* 23 */ {"authorization",null}, + /* 24 */ {"cache-control",null}, + /* 25 */ {"content-disposition",null}, + /* 26 */ {"content-encoding",null}, + /* 27 */ {"content-language",null}, + /* 28 */ {"content-length",null}, + /* 29 */ {"content-location",null}, + /* 30 */ {"content-range",null}, + /* 31 */ {"content-type",null}, + /* 32 */ {"cookie",null}, + /* 33 */ {"date",null}, + /* 34 */ {"etag",null}, + /* 35 */ {"expect",null}, + /* 36 */ {"expires",null}, + /* 37 */ {"from",null}, + /* 38 */ {"host",null}, + /* 39 */ {"if-match",null}, + /* 40 */ {"if-modified-since",null}, + /* 41 */ {"if-none-match",null}, + /* 42 */ {"if-range",null}, + /* 43 */ {"if-unmodified-since",null}, + /* 44 */ {"last-modified",null}, + /* 45 */ {"link",null}, + /* 46 */ {"location",null}, + /* 47 */ {"max-forwards",null}, + /* 48 */ {"proxy-authenticate",null}, + /* 49 */ {"proxy-authorization",null}, + /* 50 */ {"range",null}, + /* 51 */ {"referer",null}, + /* 52 */ {"refresh",null}, + /* 53 */ {"retry-after",null}, + /* 54 */ {"server",null}, + /* 55 */ {"set-cookie",null}, + /* 56 */ {"strict-transport-security",null}, + /* 57 */ {"transfer-encoding",null}, + /* 58 */ {"user-agent",null}, + /* 59 */ {"vary",null}, + /* 60 */ {"via",null}, + /* 61 */ {"www-authenticate",null}, + }; + + private static final Map<HttpField,Entry> __staticFieldMap = new HashMap<>(); + private static final Trie<StaticEntry> __staticNameMap = new ArrayTernaryTrie<>(true,512); + private static final StaticEntry[] __staticTableByHeader = new StaticEntry[HttpHeader.UNKNOWN.ordinal()]; + private static final StaticEntry[] __staticTable=new StaticEntry[STATIC_TABLE.length]; + static + { + Set<String> added = new HashSet<>(); + for (int i=1;i<STATIC_TABLE.length;i++) + { + StaticEntry entry=null; + + String name = STATIC_TABLE[i][0]; + String value = STATIC_TABLE[i][1]; + HttpHeader header = HttpHeader.CACHE.get(name); + if (header!=null && value!=null) + { + switch (header) + { + case C_METHOD: + { + + HttpMethod method = HttpMethod.CACHE.get(value); + if (method!=null) + entry=new StaticEntry(i,new StaticTableHttpField(header,name,value,method)); + break; + } + + case C_SCHEME: + { + + HttpScheme scheme = HttpScheme.CACHE.get(value); + if (scheme!=null) + entry=new StaticEntry(i,new StaticTableHttpField(header,name,value,scheme)); + break; + } + + case C_STATUS: + { + entry=new StaticEntry(i,new StaticTableHttpField(header,name,value,Integer.valueOf(value))); + break; + } + + default: + break; + } + } + + if (entry==null) + entry=new StaticEntry(i,header==null?new HttpField(STATIC_TABLE[i][0],value):new HttpField(header,name,value)); + + + __staticTable[i]=entry; + + if (entry._field.getValue()!=null) + __staticFieldMap.put(entry._field,entry); + + if (!added.contains(entry._field.getName())) + { + added.add(entry._field.getName()); + __staticNameMap.put(entry._field.getName(),entry); + if (__staticNameMap.get(entry._field.getName())==null) + throw new IllegalStateException("name trie too small"); + } + } + + for (HttpHeader h : HttpHeader.values()) + { + StaticEntry entry = __staticNameMap.get(h.asString()); + if (entry!=null) + __staticTableByHeader[h.ordinal()]=entry; + } + } + + private int _maxDynamicTableSizeInBytes; + private int _dynamicTableSizeInBytes; + private final DynamicTable _dynamicTable; + private final Map<HttpField,Entry> _fieldMap = new HashMap<>(); + private final Map<String,Entry> _nameMap = new HashMap<>(); + + HpackContext(int maxDynamicTableSize) + { + _maxDynamicTableSizeInBytes=maxDynamicTableSize; + int guesstimateEntries = 10+maxDynamicTableSize/(32+10+10); + _dynamicTable=new DynamicTable(guesstimateEntries,guesstimateEntries+10); + if (LOG.isDebugEnabled()) + LOG.debug(String.format("HdrTbl[%x] created max=%d",hashCode(),maxDynamicTableSize)); + } + + public void resize(int newMaxDynamicTableSize) + { + if (LOG.isDebugEnabled()) + LOG.debug(String.format("HdrTbl[%x] resized max=%d->%d",hashCode(),_maxDynamicTableSizeInBytes,newMaxDynamicTableSize)); + _maxDynamicTableSizeInBytes=newMaxDynamicTableSize; + int guesstimateEntries = 10+newMaxDynamicTableSize/(32+10+10); + evict(); + _dynamicTable.resizeUnsafe(guesstimateEntries); + } + + public Entry get(HttpField field) + { + Entry entry = _fieldMap.get(field); + if (entry==null) + entry=__staticFieldMap.get(field); + return entry; + } + + public Entry get(String name) + { + Entry entry = __staticNameMap.get(name); + if (entry!=null) + return entry; + return _nameMap.get(StringUtil.asciiToLowerCase(name)); + } + + public Entry get(int index) + { + if (index<__staticTable.length) + return __staticTable[index]; + + int d=_dynamicTable.size()-index+__staticTable.length-1; + + if (d>=0) + return _dynamicTable.getUnsafe(d); + return null; + } + + public Entry get(HttpHeader header) + { + Entry e = __staticTableByHeader[header.ordinal()]; + if (e==null) + return get(header.asString()); + return e; + } + + public static Entry getStatic(HttpHeader header) + { + return __staticTableByHeader[header.ordinal()]; + } + + public Entry add(HttpField field) + { + int slot=_dynamicTable.getNextSlotUnsafe(); + Entry entry=new Entry(slot,field); + int size = entry.getSize(); + if (size>_maxDynamicTableSizeInBytes) + { + if (LOG.isDebugEnabled()) + LOG.debug(String.format("HdrTbl[%x] !added size %d>%d",hashCode(),size,_maxDynamicTableSizeInBytes)); + return null; + } + _dynamicTableSizeInBytes+=size; + _dynamicTable.addUnsafe(entry); + _fieldMap.put(field,entry); + _nameMap.put(StringUtil.asciiToLowerCase(field.getName()),entry); + + if (LOG.isDebugEnabled()) + LOG.debug(String.format("HdrTbl[%x] added %s",hashCode(),entry)); + evict(); + return entry; + } + + /** + * @return Current dynamic table size in entries + */ + public int size() + { + return _dynamicTable.size(); + } + + /** + * @return Current Dynamic table size in Octets + */ + public int getDynamicTableSize() + { + return _dynamicTableSizeInBytes; + } + + /** + * @return Max Dynamic table size in Octets + */ + public int getMaxDynamicTableSize() + { + return _maxDynamicTableSizeInBytes; + } + + public int index(Entry entry) + { + if (entry._slot<0) + return 0; + if (entry.isStatic()) + return entry._slot; + + return _dynamicTable.index(entry)+__staticTable.length-1; + } + + public static int staticIndex(HttpHeader header) + { + if (header==null) + return 0; + Entry entry=__staticNameMap.get(header.asString()); + if (entry==null) + return 0; + return entry.getSlot(); + } + + private void evict() + { + while (_dynamicTableSizeInBytes>_maxDynamicTableSizeInBytes) + { + Entry entry = _dynamicTable.pollUnsafe(); + if (LOG.isDebugEnabled()) + LOG.debug(String.format("HdrTbl[%x] evict %s",hashCode(),entry)); + _dynamicTableSizeInBytes-=entry.getSize(); + entry._slot=-1; + _fieldMap.remove(entry.getHttpField()); + String lc=StringUtil.asciiToLowerCase(entry.getHttpField().getName()); + if (entry==_nameMap.get(lc)) + _nameMap.remove(lc); + } + if (LOG.isDebugEnabled()) + LOG.debug(String.format("HdrTbl[%x] entries=%d, size=%d, max=%d",hashCode(),_dynamicTable.size(),_dynamicTableSizeInBytes,_maxDynamicTableSizeInBytes)); + } + + @Override + public String toString() + { + return String.format("HpackContext@%x{entries=%d,size=%d,max=%d}",hashCode(),_dynamicTable.size(),_dynamicTableSizeInBytes,_maxDynamicTableSizeInBytes); + } + + + + /* ------------------------------------------------------------ */ + /** + */ + private class DynamicTable extends ArrayQueue<HpackContext.Entry> + { + /* ------------------------------------------------------------ */ + /** + * @param initCapacity + * @param growBy + */ + private DynamicTable(int initCapacity, int growBy) + { + super(initCapacity,growBy); + } + + /* ------------------------------------------------------------ */ + /** + * @see org.eclipse.jetty.util.ArrayQueue#growUnsafe() + */ + @Override + protected void resizeUnsafe(int newCapacity) + { + // Relay on super.growUnsafe to pack all entries 0 to _nextSlot + super.resizeUnsafe(newCapacity); + for (int s=0;s<_nextSlot;s++) + ((Entry)_elements[s])._slot=s; + } + + /* ------------------------------------------------------------ */ + /** + * @see org.eclipse.jetty.util.ArrayQueue#enqueue(java.lang.Object) + */ + @Override + public boolean enqueue(Entry e) + { + return super.enqueue(e); + } + + /* ------------------------------------------------------------ */ + /** + * @see org.eclipse.jetty.util.ArrayQueue#dequeue() + */ + @Override + public Entry dequeue() + { + return super.dequeue(); + } + + /* ------------------------------------------------------------ */ + /** + * @param entry + * @return + */ + private int index(Entry entry) + { + return entry._slot>=_nextE?_size-entry._slot+_nextE:_nextSlot-entry._slot; + } + + } + + + + /* ------------------------------------------------------------ */ + /* ------------------------------------------------------------ */ + /* ------------------------------------------------------------ */ + public static class Entry + { + final HttpField _field; + int _slot; + + Entry() + { + _slot=0; + _field=null; + } + + Entry(int index,String name, String value) + { + _slot=index; + _field=new HttpField(name,value); + } + + Entry(int slot, HttpField field) + { + _slot=slot; + _field=field; + } + + public int getSize() + { + return 32+_field.getName().length()+_field.getValue().length(); + } + + public HttpField getHttpField() + { + return _field; + } + + public boolean isStatic() + { + return false; + } + + public byte[] getStaticHuffmanValue() + { + return null; + } + + public int getSlot() + { + return _slot; + } + + public String toString() + { + return String.format("{%s,%d,%s,%x}",isStatic()?"S":"D",_slot,_field,hashCode()); + } + } + + public static class StaticEntry extends Entry + { + private final byte[] _huffmanValue; + private final byte _encodedField; + + StaticEntry(int index,HttpField field) + { + super(index,field); + String value = field.getValue(); + if (value!=null && value.length()>0) + { + int huffmanLen = Huffman.octetsNeeded(value); + int lenLen = NBitInteger.octectsNeeded(7,huffmanLen); + _huffmanValue = new byte[1+lenLen+huffmanLen]; + ByteBuffer buffer = ByteBuffer.wrap(_huffmanValue); + + // Indicate Huffman + buffer.put((byte)0x80); + // Add huffman length + NBitInteger.encode(buffer,7,huffmanLen); + // Encode value + Huffman.encode(buffer,value); + } + else + _huffmanValue=null; + + _encodedField=(byte)(0x80|index); + } + + @Override + public boolean isStatic() + { + return true; + } + + @Override + public byte[] getStaticHuffmanValue() + { + return _huffmanValue; + } + + public byte getEncodedField() + { + return _encodedField; + } + } + + +} |