1 /*

     2  * Copyright (c) 2014, 2018, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 package jdk.incubator.http.internal.hpack;

    26 

    27 import jdk.incubator.http.internal.hpack.HPACK.Logger;

    28 import jdk.internal.vm.annotation.Stable;

    29 

    30 import java.util.HashMap;

    31 import java.util.LinkedHashMap;

    32 import java.util.Map;

    33 import java.util.NoSuchElementException;

    34 

    35 import static java.lang.String.format;

    36 import static jdk.incubator.http.internal.hpack.HPACK.Logger.Level.EXTRA;

    37 import static jdk.incubator.http.internal.hpack.HPACK.Logger.Level.NORMAL;

    38 

    39 //

    40 // Header Table combined from two tables: static and dynamic.

    41 //

    42 // There is a single address space for index values. Index-aware methods

    43 // correspond to the table as a whole. Size-aware methods only to the dynamic

    44 // part of it.

    45 //

    46 final class HeaderTable {

    47 

    48     @Stable

    49     private static final HeaderField[] staticTable = {

    50             null, // To make index 1-based, instead of 0-based

    51             new HeaderField(":authority"),

    52             new HeaderField(":method", "GET"),

    53             new HeaderField(":method", "POST"),

    54             new HeaderField(":path", "/"),

    55             new HeaderField(":path", "/index.html"),

    56             new HeaderField(":scheme", "http"),

    57             new HeaderField(":scheme", "https"),

    58             new HeaderField(":status", "200"),

    59             new HeaderField(":status", "204"),

    60             new HeaderField(":status", "206"),

    61             new HeaderField(":status", "304"),

    62             new HeaderField(":status", "400"),

    63             new HeaderField(":status", "404"),

    64             new HeaderField(":status", "500"),

    65             new HeaderField("accept-charset"),

    66             new HeaderField("accept-encoding", "gzip, deflate"),

    67             new HeaderField("accept-language"),

    68             new HeaderField("accept-ranges"),

    69             new HeaderField("accept"),

    70             new HeaderField("access-control-allow-origin"),

    71             new HeaderField("age"),

    72             new HeaderField("allow"),

    73             new HeaderField("authorization"),

    74             new HeaderField("cache-control"),

    75             new HeaderField("content-disposition"),

    76             new HeaderField("content-encoding"),

    77             new HeaderField("content-language"),

    78             new HeaderField("content-length"),

    79             new HeaderField("content-location"),

    80             new HeaderField("content-range"),

    81             new HeaderField("content-type"),

    82             new HeaderField("cookie"),

    83             new HeaderField("date"),

    84             new HeaderField("etag"),

    85             new HeaderField("expect"),

    86             new HeaderField("expires"),

    87             new HeaderField("from"),

    88             new HeaderField("host"),

    89             new HeaderField("if-match"),

    90             new HeaderField("if-modified-since"),

    91             new HeaderField("if-none-match"),

    92             new HeaderField("if-range"),

    93             new HeaderField("if-unmodified-since"),

    94             new HeaderField("last-modified"),

    95             new HeaderField("link"),

    96             new HeaderField("location"),

    97             new HeaderField("max-forwards"),

    98             new HeaderField("proxy-authenticate"),

    99             new HeaderField("proxy-authorization"),

   100             new HeaderField("range"),

   101             new HeaderField("referer"),

   102             new HeaderField("refresh"),

   103             new HeaderField("retry-after"),

   104             new HeaderField("server"),

   105             new HeaderField("set-cookie"),

   106             new HeaderField("strict-transport-security"),

   107             new HeaderField("transfer-encoding"),

   108             new HeaderField("user-agent"),

   109             new HeaderField("vary"),

   110             new HeaderField("via"),

   111             new HeaderField("www-authenticate")

   112     };

   113 

   114     private static final int STATIC_TABLE_LENGTH = staticTable.length - 1;

   115     private static final int ENTRY_SIZE = 32;

   116     private static final Map<String, LinkedHashMap<String, Integer>> staticIndexes;

   117 

   118     static {

   119         staticIndexes = new HashMap<>(STATIC_TABLE_LENGTH); // TODO: Map.of

   120         for (int i = 1; i <= STATIC_TABLE_LENGTH; i++) {

   121             HeaderField f = staticTable[i];

   122             Map<String, Integer> values = staticIndexes

   123                     .computeIfAbsent(f.name, k -> new LinkedHashMap<>());

   124             values.put(f.value, i);

   125         }

   126     }

   127 

   128     private final Logger logger;

   129     private final Table dynamicTable = new Table(0);

   130     private int maxSize;

   131     private int size;

   132 

   133     public HeaderTable(int maxSize, Logger logger) {

   134         this.logger = logger;

   135         setMaxSize(maxSize);

   136     }

   137 

   138     //

   139     // The method returns:

   140     //

   141     // * a positive integer i where i (i = [1..Integer.MAX_VALUE]) is an

   142     // index of an entry with a header (n, v), where n.equals(name) &&

   143     // v.equals(value)

   144     //

   145     // * a negative integer j where j (j = [-Integer.MAX_VALUE..-1]) is an

   146     // index of an entry with a header (n, v), where n.equals(name)

   147     //

   148     // * 0 if there's no entry e such that e.getName().equals(name)

   149     //

   150     // The rationale behind this design is to allow to pack more useful data

   151     // into a single invocation, facilitating a single pass where possible

   152     // (the idea is the same as in java.util.Arrays.binarySearch(int[], int)).

   153     //

   154     public int indexOf(CharSequence name, CharSequence value) {

   155         // Invoking toString() will possibly allocate Strings for the sake of

   156         // the search, which doesn't feel right.

   157         String n = name.toString();

   158         String v = value.toString();

   159 

   160         // 1. Try exact match in the static region

   161         Map<String, Integer> values = staticIndexes.get(n);

   162         if (values != null) {

   163             Integer idx = values.get(v);

   164             if (idx != null) {

   165                 return idx;

   166             }

   167         }

   168         // 2. Try exact match in the dynamic region

   169         int didx = dynamicTable.indexOf(n, v);

   170         if (didx > 0) {

   171             return STATIC_TABLE_LENGTH + didx;

   172         } else if (didx < 0) {

   173             if (values != null) {

   174                 // 3. Return name match from the static region

   175                 return -values.values().iterator().next(); // Iterator allocation

   176             } else {

   177                 // 4. Return name match from the dynamic region

   178                 return -STATIC_TABLE_LENGTH + didx;

   179             }

   180         } else {

   181             if (values != null) {

   182                 // 3. Return name match from the static region

   183                 return -values.values().iterator().next(); // Iterator allocation

   184             } else {

   185                 return 0;

   186             }

   187         }

   188     }

   189 

   190     public int size() {

   191         return size;

   192     }

   193 

   194     public int maxSize() {

   195         return maxSize;

   196     }

   197 

   198     public int length() {

   199         return STATIC_TABLE_LENGTH + dynamicTable.size();

   200     }

   201 

   202     HeaderField get(int index) {

   203         checkIndex(index);

   204         if (index <= STATIC_TABLE_LENGTH) {

   205             return staticTable[index];

   206         } else {

   207             return dynamicTable.get(index - STATIC_TABLE_LENGTH);

   208         }

   209     }

   210 

   211     void put(CharSequence name, CharSequence value) {

   212         // Invoking toString() will possibly allocate Strings. But that's

   213         // unavoidable at this stage. If a CharSequence is going to be stored in

   214         // the table, it must not be mutable (e.g. for the sake of hashing).

   215         put(new HeaderField(name.toString(), value.toString()));

   216     }

   217 

   218     private void put(HeaderField h) {

   219         if (logger.isLoggable(NORMAL)) {

   220             logger.log(NORMAL, () -> format("adding ('%s', '%s')",

   221                                             h.name, h.value));

   222         }

   223         int entrySize = sizeOf(h);

   224         if (logger.isLoggable(EXTRA)) {

   225             logger.log(EXTRA, () -> format("size of ('%s', '%s') is %s",

   226                                            h.name, h.value, entrySize));

   227         }

   228         while (entrySize > maxSize - size && size != 0) {

   229             if (logger.isLoggable(EXTRA)) {

   230                 logger.log(EXTRA, () -> format("insufficient space %s, must evict entry",

   231                                                (maxSize - size)));

   232             }

   233             evictEntry();

   234         }

   235         if (entrySize > maxSize - size) {

   236             if (logger.isLoggable(EXTRA)) {

   237                 logger.log(EXTRA, () -> format("not adding ('%s, '%s'), too big",

   238                                                h.name, h.value));

   239             }

   240             return;

   241         }

   242         size += entrySize;

   243         dynamicTable.add(h);

   244         if (logger.isLoggable(EXTRA)) {

   245             logger.log(EXTRA, () -> format("('%s, '%s') added", h.name, h.value));

   246             logger.log(EXTRA, this::toString);

   247         }

   248     }

   249 

   250     void setMaxSize(int maxSize) {

   251         if (maxSize < 0) {

   252             throw new IllegalArgumentException(

   253                     "maxSize >= 0: maxSize=" + maxSize);

   254         }

   255         while (maxSize < size && size != 0) {

   256             evictEntry();

   257         }

   258         this.maxSize = maxSize;

   259         int upperBound = (maxSize / ENTRY_SIZE) + 1;

   260         this.dynamicTable.setCapacity(upperBound);

   261     }

   262 

   263     HeaderField evictEntry() {

   264         HeaderField f = dynamicTable.remove();

   265         int s = sizeOf(f);

   266         this.size -= s;

   267         if (logger.isLoggable(EXTRA)) {

   268             logger.log(EXTRA, () -> format("evicted entry ('%s', '%s') of size %s",

   269                                            f.name, f.value, s));

   270             logger.log(EXTRA, this::toString);

   271         }

   272         return f;

   273     }

   274 

   275     @Override

   276     public String toString() {

   277         double used = maxSize == 0 ? 0 : 100 * (((double) size) / maxSize);

   278         return format("dynamic length: %d, full length: %s, used space: %s/%s (%.1f%%)",

   279                       dynamicTable.size(), length(), size, maxSize, used);

   280     }

   281 

   282     private int checkIndex(int index) {

   283         int len = length();

   284         if (index < 1 || index > len) {

   285             throw new IndexOutOfBoundsException(

   286                     format("1 <= index <= length(): index=%s, length()=%s",

   287                            index, len));

   288         }

   289         return index;

   290     }

   291 

   292     int sizeOf(HeaderField f) {

   293         return f.name.length() + f.value.length() + ENTRY_SIZE;

   294     }

   295 

   296     //

   297     // Diagnostic information in the form used in the RFC 7541

   298     //

   299     String getStateString() {

   300         if (size == 0) {

   301             return "empty.";

   302         }

   303 

   304         StringBuilder b = new StringBuilder();

   305         for (int i = 1, size = dynamicTable.size(); i <= size; i++) {

   306             HeaderField e = dynamicTable.get(i);

   307             b.append(format("[%3d] (s = %3d) %s: %s\n", i,

   308                     sizeOf(e), e.name, e.value));

   309         }

   310         b.append(format("      Table size:%4s", this.size));

   311         return b.toString();

   312     }

   313 

   314     // Convert to a Value Object (JDK-8046159)?

   315     static final class HeaderField {

   316 

   317         final String name;

   318         final String value;

   319 

   320         public HeaderField(String name) {

   321             this(name, "");

   322         }

   323 

   324         public HeaderField(String name, String value) {

   325             this.name = name;

   326             this.value = value;

   327         }

   328 

   329         @Override

   330         public String toString() {

   331             return value.isEmpty() ? name : name + ": " + value;

   332         }

   333 

   334         @Override

   335         public boolean equals(Object o) {

   336             if (this == o) {

   337                 return true;

   338             }

   339             if (o == null || getClass() != o.getClass()) {

   340                 return false;

   341             }

   342             HeaderField that = (HeaderField) o;

   343             return name.equals(that.name) && value.equals(that.value);

   344         }

   345 

   346         @Override

   347         public int hashCode() {

   348             return 31 * name.hashCode() + value.hashCode();

   349         }

   350     }

   351 

   352     //

   353     // To quickly find an index of an entry in the dynamic table with the given

   354     // contents an effective inverse mapping is needed. Here's a simple idea

   355     // behind such a mapping.

   356     //

   357     // # The problem:

   358     //

   359     // We have a queue with an O(1) lookup by index:

   360     //

   361     //     get: index -> x

   362     //

   363     // What we want is an O(1) reverse lookup:

   364     //

   365     //     indexOf: x -> index

   366     //

   367     // # Solution:

   368     //

   369     // Let's store an inverse mapping in a Map<x, Integer>. This have a problem

   370     // that when a new element is added to the queue, all indexes in the map

   371     // become invalid. Namely, the new element is assigned with an index of 1,

   372     // and each index i, i > 1 becomes shifted by 1 to the left:

   373     //

   374     //     1, 1, 2, 3, ... , n-1, n

   375     //

   376     // Re-establishing the invariant would seem to require a pass through the

   377     // map incrementing all indexes (map values) by 1, which is O(n).

   378     //

   379     // The good news is we can do much better then this!

   380     //

   381     // Let's create a single field of type long, called 'counter'. Then each

   382     // time a new element 'x' is added to the queue, a value of this field gets

   383     // incremented. Then the resulting value of the 'counter_x' is then put as a

   384     // value under key 'x' to the map:

   385     //

   386     //    map.put(x, counter_x)

   387     //

   388     // It gives us a map that maps an element to a value the counter had at the

   389     // time the element had been added.

   390     //

   391     // In order to retrieve an index of any element 'x' in the queue (at any

   392     // given time) we simply need to subtract the value (the snapshot of the

   393     // counter at the time when the 'x' was added) from the current value of the

   394     // counter. This operation basically answers the question:

   395     //

   396     //     How many elements ago 'x' was the tail of the queue?

   397     //

   398     // Which is the same as its index in the queue now. Given, of course, it's

   399     // still in the queue.

   400     //

   401     // I'm pretty sure in a real life long overflow will never happen, so it's

   402     // not too practical to add recalibrating code, but a pedantic person might

   403     // want to do so:

   404     //

   405     //     if (counter == Long.MAX_VALUE) {

   406     //         recalibrate();

   407     //     }

   408     //

   409     // Where 'recalibrate()' goes through the table doing this:

   410     //

   411     //     value -= counter

   412     //

   413     // That's given, of course, the size of the table itself is less than

   414     // Long.MAX_VALUE :-)

   415     //

   416     private static final class Table {

   417 

   418         private final Map<String, Map<String, Long>> map;

   419         private final CircularBuffer<HeaderField> buffer;

   420         private long counter = 1;

   421 

   422         Table(int capacity) {

   423             buffer = new CircularBuffer<>(capacity);

   424             map = new HashMap<>(capacity);

   425         }

   426 

   427         void add(HeaderField f) {

   428             buffer.add(f);

   429             Map<String, Long> values = map.computeIfAbsent(f.name, k -> new HashMap<>());

   430             values.put(f.value, counter++);

   431         }

   432 

   433         HeaderField get(int index) {

   434             return buffer.get(index - 1);

   435         }

   436 

   437         int indexOf(String name, String value) {

   438             Map<String, Long> values = map.get(name);

   439             if (values == null) {

   440                 return 0;

   441             }

   442             Long index = values.get(value);

   443             if (index != null) {

   444                 return (int) (counter - index);

   445             } else {

   446                 assert !values.isEmpty();

   447                 Long any = values.values().iterator().next(); // Iterator allocation

   448                 return -(int) (counter - any);

   449             }

   450         }

   451 

   452         HeaderField remove() {

   453             HeaderField f = buffer.remove();

   454             Map<String, Long> values = map.get(f.name);

   455             Long index = values.remove(f.value);

   456             assert index != null;

   457             if (values.isEmpty()) {

   458                 map.remove(f.name);

   459             }

   460             return f;

   461         }

   462 

   463         int size() {

   464             return buffer.size;

   465         }

   466 

   467         public void setCapacity(int capacity) {

   468             buffer.resize(capacity);

   469         }

   470     }

   471 

   472     //                    head

   473     //                    v

   474     // [ ][ ][A][B][C][D][ ][ ][ ]

   475     //        ^

   476     //        tail

   477     //

   478     //       |<- size ->| (4)

   479     // |<------ capacity ------->| (9)

   480     //

   481     static final class CircularBuffer<E> {

   482 

   483         int tail, head, size, capacity;

   484         Object[] elements;

   485 

   486         CircularBuffer(int capacity) {

   487             this.capacity = capacity;

   488             elements = new Object[capacity];

   489         }

   490 

   491         void add(E elem) {

   492             if (size == capacity) {

   493                 throw new IllegalStateException(

   494                         format("No room for '%s': capacity=%s", elem, capacity));

   495             }

   496             elements[head] = elem;

   497             head = (head + 1) % capacity;

   498             size++;

   499         }

   500 

   501         @SuppressWarnings("unchecked")

   502         E remove() {

   503             if (size == 0) {

   504                 throw new NoSuchElementException("Empty");

   505             }

   506             E elem = (E) elements[tail];

   507             elements[tail] = null;

   508             tail = (tail + 1) % capacity;

   509             size--;

   510             return elem;

   511         }

   512 

   513         @SuppressWarnings("unchecked")

   514         E get(int index) {

   515             if (index < 0 || index >= size) {

   516                 throw new IndexOutOfBoundsException(

   517                         format("0 <= index <= capacity: index=%s, capacity=%s",

   518                                 index, capacity));

   519             }

   520             int idx = (tail + (size - index - 1)) % capacity;

   521             return (E) elements[idx];

   522         }

   523 

   524         public void resize(int newCapacity) {

   525             if (newCapacity < size) {

   526                 throw new IllegalStateException(

   527                         format("newCapacity >= size: newCapacity=%s, size=%s",

   528                                 newCapacity, size));

   529             }

   530 

   531             Object[] newElements = new Object[newCapacity];

   532 

   533             if (tail < head || size == 0) {

   534                 System.arraycopy(elements, tail, newElements, 0, size);

   535             } else {

   536                 System.arraycopy(elements, tail, newElements, 0, elements.length - tail);

   537                 System.arraycopy(elements, 0, newElements, elements.length - tail, head);

   538             }

   539 

   540             elements = newElements;

   541             tail = 0;

   542             head = size;

   543             this.capacity = newCapacity;

   544         }

   545     }

   546 }