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.internal.net.http.hpack;

    26 

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

    28 

    29 import java.util.NoSuchElementException;

    30 

    31 import static jdk.internal.net.http.hpack.HPACK.Logger.Level.EXTRA;

    32 import static jdk.internal.net.http.hpack.HPACK.Logger.Level.NORMAL;

    33 import static java.lang.String.format;

    34 

    35 /*

    36  * A header table consists of two tables, the static table and the dynamic

    37  * table. Following the vocabulary of RFC 7541, the length of the header table

    38  * is the total number of entries in both the static and the dynamic tables.

    39  * The size of the table is the sum of the sizes of its dynamic table's entries.

    40  */

    41 class SimpleHeaderTable {

    42 

    43     protected static final HeaderField[] staticTable = {

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

    45             new HeaderField(":authority"),

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

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

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

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

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

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

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

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

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

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

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

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

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

    59             new HeaderField("accept-charset"),

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

    61             new HeaderField("accept-language"),

    62             new HeaderField("accept-ranges"),

    63             new HeaderField("accept"),

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

    65             new HeaderField("age"),

    66             new HeaderField("allow"),

    67             new HeaderField("authorization"),

    68             new HeaderField("cache-control"),

    69             new HeaderField("content-disposition"),

    70             new HeaderField("content-encoding"),

    71             new HeaderField("content-language"),

    72             new HeaderField("content-length"),

    73             new HeaderField("content-location"),

    74             new HeaderField("content-range"),

    75             new HeaderField("content-type"),

    76             new HeaderField("cookie"),

    77             new HeaderField("date"),

    78             new HeaderField("etag"),

    79             new HeaderField("expect"),

    80             new HeaderField("expires"),

    81             new HeaderField("from"),

    82             new HeaderField("host"),

    83             new HeaderField("if-match"),

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

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

    86             new HeaderField("if-range"),

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

    88             new HeaderField("last-modified"),

    89             new HeaderField("link"),

    90             new HeaderField("location"),

    91             new HeaderField("max-forwards"),

    92             new HeaderField("proxy-authenticate"),

    93             new HeaderField("proxy-authorization"),

    94             new HeaderField("range"),

    95             new HeaderField("referer"),

    96             new HeaderField("refresh"),

    97             new HeaderField("retry-after"),

    98             new HeaderField("server"),

    99             new HeaderField("set-cookie"),

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

   101             new HeaderField("transfer-encoding"),

   102             new HeaderField("user-agent"),

   103             new HeaderField("vary"),

   104             new HeaderField("via"),

   105             new HeaderField("www-authenticate")

   106     };

   107 

   108     protected static final int STATIC_TABLE_LENGTH = staticTable.length - 1;

   109     protected static final int ENTRY_SIZE = 32;

   110 

   111     private final Logger logger;

   112 

   113     private int maxSize;

   114     private int size;

   115 

   116     public SimpleHeaderTable(int maxSize, Logger logger) {

   117         this.logger = logger;

   118         setMaxSize(maxSize);

   119     }

   120 

   121     public int size() {

   122         return size;

   123     }

   124 

   125     public int maxSize() {

   126         return maxSize;

   127     }

   128 

   129     public int length() {

   130         return STATIC_TABLE_LENGTH + buffer.size;

   131     }

   132 

   133     HeaderField get(int index) {

   134         checkIndex(index);

   135         if (index <= STATIC_TABLE_LENGTH) {

   136             return staticTable[index];

   137         } else {

   138             return buffer.get(index - STATIC_TABLE_LENGTH - 1);

   139         }

   140     }

   141 

   142     void put(CharSequence name, CharSequence value) {

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

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

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

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

   147     }

   148 

   149     private void put(HeaderField h) {

   150         if (logger.isLoggable(NORMAL)) {

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

   152                                             h.name, h.value));

   153         }

   154         int entrySize = sizeOf(h);

   155         if (logger.isLoggable(EXTRA)) {

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

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

   158         }

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

   160             if (logger.isLoggable(EXTRA)) {

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

   162                                                (maxSize - size)));

   163             }

   164             evictEntry();

   165         }

   166         if (entrySize > maxSize - size) {

   167             if (logger.isLoggable(EXTRA)) {

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

   169                                                h.name, h.value));

   170             }

   171             return;

   172         }

   173         size += entrySize;

   174         add(h);

   175         if (logger.isLoggable(EXTRA)) {

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

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

   178         }

   179     }

   180 

   181     void setMaxSize(int maxSize) {

   182         if (maxSize < 0) {

   183             throw new IllegalArgumentException(

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

   185         }

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

   187             evictEntry();

   188         }

   189         this.maxSize = maxSize;

   190         // A header table cannot accommodate more entries than this

   191         int upperBound = maxSize / ENTRY_SIZE;

   192         buffer.resize(upperBound);

   193     }

   194 

   195     HeaderField evictEntry() {

   196         HeaderField f = remove();

   197         int s = sizeOf(f);

   198         this.size -= s;

   199         if (logger.isLoggable(EXTRA)) {

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

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

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

   203         }

   204         return f;

   205     }

   206 

   207     @Override

   208     public String toString() {

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

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

   211                       buffer.size, length(), size, maxSize, used);

   212     }

   213 

   214     private int checkIndex(int index) {

   215         int len = length();

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

   217             throw new IndexOutOfBoundsException(

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

   219                            index, len));

   220         }

   221         return index;

   222     }

   223 

   224     int sizeOf(HeaderField f) {

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

   226     }

   227 

   228     //

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

   230     //

   231     String getStateString() {

   232         if (size == 0) {

   233             return "empty.";

   234         }

   235 

   236         StringBuilder b = new StringBuilder();

   237         for (int i = 1, size = buffer.size; i <= size; i++) {

   238             HeaderField e = buffer.get(i - 1);

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

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

   241         }

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

   243         return b.toString();

   244     }

   245 

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

   247     protected static final class HeaderField {

   248 

   249         final String name;

   250         final String value;

   251 

   252         public HeaderField(String name) {

   253             this(name, "");

   254         }

   255 

   256         public HeaderField(String name, String value) {

   257             this.name = name;

   258             this.value = value;

   259         }

   260 

   261         @Override

   262         public String toString() {

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

   264         }

   265 

   266         @Override // TODO: remove since used only for testing

   267         public boolean equals(Object o) {

   268             if (this == o) {

   269                 return true;

   270             }

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

   272                 return false;

   273             }

   274             HeaderField that = (HeaderField) o;

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

   276         }

   277 

   278         @Override // TODO: remove since used only for testing

   279         public int hashCode() {

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

   281         }

   282     }

   283 

   284     private final CircularBuffer<HeaderField> buffer = new CircularBuffer<>(0);

   285 

   286     protected void add(HeaderField f) {

   287         buffer.add(f);

   288     }

   289 

   290     protected HeaderField remove() {

   291         return buffer.remove();

   292     }

   293 

   294     //                    head

   295     //                    v

   296     // [ ][ ][A][B][C][D][ ][ ][ ]

   297     //        ^

   298     //        tail

   299     //

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

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

   302     //

   303     static final class CircularBuffer<E> {

   304 

   305         int tail, head, size, capacity;

   306         Object[] elements;

   307 

   308         CircularBuffer(int capacity) {

   309             this.capacity = capacity;

   310             elements = new Object[capacity];

   311         }

   312 

   313         void add(E elem) {

   314             if (size == capacity) {

   315                 throw new IllegalStateException(

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

   317             }

   318             elements[head] = elem;

   319             head = (head + 1) % capacity;

   320             size++;

   321         }

   322 

   323         @SuppressWarnings("unchecked")

   324         E remove() {

   325             if (size == 0) {

   326                 throw new NoSuchElementException("Empty");

   327             }

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

   329             elements[tail] = null;

   330             tail = (tail + 1) % capacity;

   331             size--;

   332             return elem;

   333         }

   334 

   335         @SuppressWarnings("unchecked")

   336         E get(int index) {

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

   338                 throw new IndexOutOfBoundsException(

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

   340                                index, capacity));

   341             }

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

   343             return (E) elements[idx];

   344         }

   345 

   346         public void resize(int newCapacity) {

   347             if (newCapacity < size) {

   348                 throw new IllegalStateException(

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

   350                                newCapacity, size));

   351             }

   352 

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

   354 

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

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

   357             } else {

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

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

   360             }

   361 

   362             elements = newElements;

   363             tail = 0;

   364             head = size;

   365             this.capacity = newCapacity;

   366         }

   367     }

   368 }