# HG changeset patch # User prappo # Date 1523017268 -3600 # Node ID c08eb1e2dc3800d1321c86056529637ea0cb755e # Parent 49faeb51d1ca8699697107a5d8d052e36dd39109 http-client-branch: (HPACK) updates and cleanup diff -r 49faeb51d1ca -r c08eb1e2dc38 src/java.net.http/share/classes/jdk/internal/net/http/hpack/Decoder.java --- a/src/java.net.http/share/classes/jdk/internal/net/http/hpack/Decoder.java Wed Apr 04 15:50:02 2018 +0100 +++ b/src/java.net.http/share/classes/jdk/internal/net/http/hpack/Decoder.java Fri Apr 06 13:21:08 2018 +0100 @@ -98,7 +98,7 @@ } private final long id; - private final HeaderTable table; + private final SimpleHeaderTable table; private State state = State.READY; private final IntegerReader integerReader; @@ -144,7 +144,7 @@ }); } setMaxCapacity0(capacity); - table = new HeaderTable(capacity, logger.subLogger("HeaderTable")); + table = new SimpleHeaderTable(capacity, logger.subLogger("HeaderTable")); integerReader = new IntegerReader(); stringReader = new StringReader(); name = new StringBuilder(512); @@ -341,17 +341,17 @@ logger.log(NORMAL, () -> format("indexed %s", intValue)); } try { - HeaderTable.HeaderField f = getHeaderFieldAt(intValue); + SimpleHeaderTable.HeaderField f = getHeaderFieldAt(intValue); action.onIndexed(intValue, f.name, f.value); } finally { state = State.READY; } } - private HeaderTable.HeaderField getHeaderFieldAt(int index) + private SimpleHeaderTable.HeaderField getHeaderFieldAt(int index) throws IOException { - HeaderTable.HeaderField f; + SimpleHeaderTable.HeaderField f; try { f = table.get(index); } catch (IndexOutOfBoundsException e) { @@ -393,7 +393,7 @@ logger.log(NORMAL, () -> format("literal without indexing ('%s', '%s')", intValue, value)); } - HeaderTable.HeaderField f = getHeaderFieldAt(intValue); + SimpleHeaderTable.HeaderField f = getHeaderFieldAt(intValue); action.onLiteral(intValue, f.name, value, valueHuffmanEncoded); } else { if (logger.isLoggable(NORMAL)) { @@ -450,7 +450,7 @@ logger.log(NORMAL, () -> format("literal with incremental indexing ('%s', '%s')", intValue, value)); } - HeaderTable.HeaderField f = getHeaderFieldAt(intValue); + SimpleHeaderTable.HeaderField f = getHeaderFieldAt(intValue); n = f.name; action.onLiteralWithIndexing(intValue, n, v, valueHuffmanEncoded); } else { @@ -501,7 +501,7 @@ logger.log(NORMAL, () -> format("literal never indexed ('%s', '%s')", intValue, value)); } - HeaderTable.HeaderField f = getHeaderFieldAt(intValue); + SimpleHeaderTable.HeaderField f = getHeaderFieldAt(intValue); action.onLiteralNeverIndexed(intValue, f.name, value, valueHuffmanEncoded); } else { if (logger.isLoggable(NORMAL)) { @@ -588,7 +588,7 @@ SIZE_UPDATE } - HeaderTable getTable() { + SimpleHeaderTable getTable() { return table; } } diff -r 49faeb51d1ca -r c08eb1e2dc38 src/java.net.http/share/classes/jdk/internal/net/http/hpack/Encoder.java --- a/src/java.net.http/share/classes/jdk/internal/net/http/hpack/Encoder.java Wed Apr 04 15:50:02 2018 +0100 +++ b/src/java.net.http/share/classes/jdk/internal/net/http/hpack/Encoder.java Fri Apr 06 13:21:08 2018 +0100 @@ -121,6 +121,9 @@ = new BulkSizeUpdateWriter(); private BinaryRepresentationWriter writer; + // The default implementation of Encoder does not use dynamic region of the + // HeaderTable. Thus the performance profile should be similar to that of + // SimpleHeaderTable. private final HeaderTable headerTable; private boolean encoding; diff -r 49faeb51d1ca -r c08eb1e2dc38 src/java.net.http/share/classes/jdk/internal/net/http/hpack/HeaderTable.java --- a/src/java.net.http/share/classes/jdk/internal/net/http/hpack/HeaderTable.java Wed Apr 04 15:50:02 2018 +0100 +++ b/src/java.net.http/share/classes/jdk/internal/net/http/hpack/HeaderTable.java Fri Apr 06 13:21:08 2018 +0100 @@ -25,333 +25,19 @@ package jdk.internal.net.http.hpack; import jdk.internal.net.http.hpack.HPACK.Logger; -import jdk.internal.vm.annotation.Stable; import java.util.Deque; import java.util.HashMap; import java.util.LinkedHashMap; import java.util.LinkedList; import java.util.Map; -import java.util.NoSuchElementException; -import static java.lang.String.format; -import static jdk.internal.net.http.hpack.HPACK.Logger.Level.EXTRA; -import static jdk.internal.net.http.hpack.HPACK.Logger.Level.NORMAL; - -// -// Header Table combined from two tables: static and dynamic. -// -// There is a single address space for index values. Index-aware methods -// correspond to the table as a whole. Size-aware methods only to the dynamic -// part of it. -// -final class HeaderTable { - - @Stable - private static final HeaderField[] staticTable = { - null, // To make index 1-based, instead of 0-based - new HeaderField(":authority"), - new HeaderField(":method", "GET"), - new HeaderField(":method", "POST"), - new HeaderField(":path", "/"), - new HeaderField(":path", "/index.html"), - new HeaderField(":scheme", "http"), - new HeaderField(":scheme", "https"), - new HeaderField(":status", "200"), - new HeaderField(":status", "204"), - new HeaderField(":status", "206"), - new HeaderField(":status", "304"), - new HeaderField(":status", "400"), - new HeaderField(":status", "404"), - new HeaderField(":status", "500"), - new HeaderField("accept-charset"), - new HeaderField("accept-encoding", "gzip, deflate"), - new HeaderField("accept-language"), - new HeaderField("accept-ranges"), - new HeaderField("accept"), - new HeaderField("access-control-allow-origin"), - new HeaderField("age"), - new HeaderField("allow"), - new HeaderField("authorization"), - new HeaderField("cache-control"), - new HeaderField("content-disposition"), - new HeaderField("content-encoding"), - new HeaderField("content-language"), - new HeaderField("content-length"), - new HeaderField("content-location"), - new HeaderField("content-range"), - new HeaderField("content-type"), - new HeaderField("cookie"), - new HeaderField("date"), - new HeaderField("etag"), - new HeaderField("expect"), - new HeaderField("expires"), - new HeaderField("from"), - new HeaderField("host"), - new HeaderField("if-match"), - new HeaderField("if-modified-since"), - new HeaderField("if-none-match"), - new HeaderField("if-range"), - new HeaderField("if-unmodified-since"), - new HeaderField("last-modified"), - new HeaderField("link"), - new HeaderField("location"), - new HeaderField("max-forwards"), - new HeaderField("proxy-authenticate"), - new HeaderField("proxy-authorization"), - new HeaderField("range"), - new HeaderField("referer"), - new HeaderField("refresh"), - new HeaderField("retry-after"), - new HeaderField("server"), - new HeaderField("set-cookie"), - new HeaderField("strict-transport-security"), - new HeaderField("transfer-encoding"), - new HeaderField("user-agent"), - new HeaderField("vary"), - new HeaderField("via"), - new HeaderField("www-authenticate") - }; - - private static final int STATIC_TABLE_LENGTH = staticTable.length - 1; - private static final int ENTRY_SIZE = 32; - private static final Map> staticIndexes; - - static { - staticIndexes = new HashMap<>(STATIC_TABLE_LENGTH); // TODO: Map.of - for (int i = 1; i <= STATIC_TABLE_LENGTH; i++) { - HeaderField f = staticTable[i]; - Map values = staticIndexes - .computeIfAbsent(f.name, k -> new LinkedHashMap<>()); - values.put(f.value, i); - } - } - - private final Logger logger; - private final Table dynamicTable = new Table(0); - private int maxSize; - private int size; - - public HeaderTable(int maxSize, Logger logger) { - this.logger = logger; - setMaxSize(maxSize); - } - - // - // The method returns: - // - // * a positive integer i where i (i = [1..Integer.MAX_VALUE]) is an - // index of an entry with a header (n, v), where n.equals(name) && - // v.equals(value) - // - // * a negative integer j where j (j = [-Integer.MAX_VALUE..-1]) is an - // index of an entry with a header (n, v), where n.equals(name) - // - // * 0 if there's no entry e such that e.getName().equals(name) - // - // The rationale behind this design is to allow to pack more useful data - // into a single invocation, facilitating a single pass where possible - // (the idea is the same as in java.util.Arrays.binarySearch(int[], int)). - // - public int indexOf(CharSequence name, CharSequence value) { - // Invoking toString() will possibly allocate Strings for the sake of - // the search, which doesn't feel right. - String n = name.toString(); - String v = value.toString(); - - // 1. Try exact match in the static region - Map values = staticIndexes.get(n); - if (values != null) { - Integer idx = values.get(v); - if (idx != null) { - return idx; - } - } - // 2. Try exact match in the dynamic region - int didx = dynamicTable.indexOf(n, v); - if (didx > 0) { - return STATIC_TABLE_LENGTH + didx; - } else if (didx < 0) { - if (values != null) { - // 3. Return name match from the static region - return -values.values().iterator().next(); // Iterator allocation - } else { - // 4. Return name match from the dynamic region - return -STATIC_TABLE_LENGTH + didx; - } - } else { - if (values != null) { - // 3. Return name match from the static region - return -values.values().iterator().next(); // Iterator allocation - } else { - return 0; - } - } - } - - public int size() { - return size; - } - - public int maxSize() { - return maxSize; - } - - public int length() { - return STATIC_TABLE_LENGTH + dynamicTable.size(); - } - - HeaderField get(int index) { - checkIndex(index); - if (index <= STATIC_TABLE_LENGTH) { - return staticTable[index]; - } else { - return dynamicTable.get(index - STATIC_TABLE_LENGTH); - } - } - - void put(CharSequence name, CharSequence value) { - // Invoking toString() will possibly allocate Strings. But that's - // unavoidable at this stage. If a CharSequence is going to be stored in - // the table, it must not be mutable (e.g. for the sake of hashing). - put(new HeaderField(name.toString(), value.toString())); - } - - private void put(HeaderField h) { - if (logger.isLoggable(NORMAL)) { - logger.log(NORMAL, () -> format("adding ('%s', '%s')", - h.name, h.value)); - } - int entrySize = sizeOf(h); - if (logger.isLoggable(EXTRA)) { - logger.log(EXTRA, () -> format("size of ('%s', '%s') is %s", - h.name, h.value, entrySize)); - } - while (entrySize > maxSize - size && size != 0) { - if (logger.isLoggable(EXTRA)) { - logger.log(EXTRA, () -> format("insufficient space %s, must evict entry", - (maxSize - size))); - } - evictEntry(); - } - if (entrySize > maxSize - size) { - if (logger.isLoggable(EXTRA)) { - logger.log(EXTRA, () -> format("not adding ('%s, '%s'), too big", - h.name, h.value)); - } - return; - } - size += entrySize; - dynamicTable.add(h); - if (logger.isLoggable(EXTRA)) { - logger.log(EXTRA, () -> format("('%s, '%s') added", h.name, h.value)); - logger.log(EXTRA, this::toString); - } - } - - void setMaxSize(int maxSize) { - if (maxSize < 0) { - throw new IllegalArgumentException( - "maxSize >= 0: maxSize=" + maxSize); - } - while (maxSize < size && size != 0) { - evictEntry(); - } - this.maxSize = maxSize; - int upperBound = (maxSize / ENTRY_SIZE) + 1; - this.dynamicTable.setCapacity(upperBound); - } - - HeaderField evictEntry() { - HeaderField f = dynamicTable.remove(); - int s = sizeOf(f); - this.size -= s; - if (logger.isLoggable(EXTRA)) { - logger.log(EXTRA, () -> format("evicted entry ('%s', '%s') of size %s", - f.name, f.value, s)); - logger.log(EXTRA, this::toString); - } - return f; - } - - @Override - public String toString() { - double used = maxSize == 0 ? 0 : 100 * (((double) size) / maxSize); - return format("dynamic length: %d, full length: %s, used space: %s/%s (%.1f%%)", - dynamicTable.size(), length(), size, maxSize, used); - } - - private int checkIndex(int index) { - int len = length(); - if (index < 1 || index > len) { - throw new IndexOutOfBoundsException( - format("1 <= index <= length(): index=%s, length()=%s", - index, len)); - } - return index; - } - - int sizeOf(HeaderField f) { - return f.name.length() + f.value.length() + ENTRY_SIZE; - } - - // - // Diagnostic information in the form used in the RFC 7541 - // - String getStateString() { - if (size == 0) { - return "empty."; - } - - StringBuilder b = new StringBuilder(); - for (int i = 1, size = dynamicTable.size(); i <= size; i++) { - HeaderField e = dynamicTable.get(i); - // Use \n instead of %n as this output is used in - // tests with string comparison. - b.append(format("[%3d] (s = %3d) %s: %s\n", i, - sizeOf(e), e.name, e.value)); - } - b.append(format(" Table size:%4s", this.size)); - return b.toString(); - } - - // Convert to a Value Object (JDK-8046159)? - static final class HeaderField { - - final String name; - final String value; - - public HeaderField(String name) { - this(name, ""); - } - - public HeaderField(String name, String value) { - this.name = name; - this.value = value; - } - - @Override - public String toString() { - return value.isEmpty() ? name : name + ": " + value; - } - - @Override - public boolean equals(Object o) { - if (this == o) { - return true; - } - if (o == null || getClass() != o.getClass()) { - return false; - } - HeaderField that = (HeaderField) o; - return name.equals(that.name) && value.equals(that.value); - } - - @Override - public int hashCode() { - return 31 * name.hashCode() + value.hashCode(); - } - } +/* + * Adds reverse lookup to SimpleHeaderTable. Separated from SimpleHeaderTable + * for performance reasons. Decoder does not need this functionality. On the + * other hand, Encoder does. + */ +final class HeaderTable extends SimpleHeaderTable { // // To quickly find an index of an entry in the dynamic table with the given @@ -417,154 +103,130 @@ // That's given, of course, the size of the table itself is less than // Long.MAX_VALUE :-) // - private static final class Table { - // name -> (value -> [index]) - private final Map>> map; - private final CircularBuffer buffer; - private long counter = 1; - - Table(int capacity) { - buffer = new CircularBuffer<>(capacity); - map = new HashMap<>(capacity); - } - - void add(HeaderField f) { - buffer.add(f); - Map> values = map.computeIfAbsent(f.name, k -> new HashMap<>()); - Deque indexes = values.computeIfAbsent(f.value, k -> new LinkedList<>()); - long counterSnapshot = counter++; - indexes.add(counterSnapshot); - assert indexesUniqueAndOrdered(indexes); - } - - private boolean indexesUniqueAndOrdered(Deque indexes) { - long maxIndexSoFar = -1; - for (long l : indexes) { - if (l <= maxIndexSoFar) { - return false; - } else { - maxIndexSoFar = l; - } - } - return true; - } - - HeaderField get(int index) { - return buffer.get(index - 1); - } + private static final Map> staticIndexes; - int indexOf(String name, String value) { - Map> values = map.get(name); - if (values == null) { - return 0; - } - Deque indexes = values.get(value); - if (indexes != null) { - return (int) (counter - indexes.peekLast()); - } else { - assert !values.isEmpty(); - Long any = values.values().iterator().next().peekLast(); // Iterator allocation - return -(int) (counter - any); - } - } - - HeaderField remove() { - HeaderField f = buffer.remove(); - Map> values = map.get(f.name); - Deque indexes = values.get(f.value); - Long index = indexes.pollFirst(); - if (indexes.isEmpty()) { - values.remove(f.value); - } - assert index != null; - if (values.isEmpty()) { - map.remove(f.name); - } - return f; - } - - int size() { - return buffer.size; - } - - public void setCapacity(int capacity) { - buffer.resize(capacity); + static { + staticIndexes = new HashMap<>(STATIC_TABLE_LENGTH); // TODO: Map.of + for (int i = 1; i <= STATIC_TABLE_LENGTH; i++) { + HeaderField f = staticTable[i]; + Map values = staticIndexes + .computeIfAbsent(f.name, k -> new LinkedHashMap<>()); + values.put(f.value, i); } } - // head - // v - // [ ][ ][A][B][C][D][ ][ ][ ] - // ^ - // tail - // - // |<- size ->| (4) - // |<------ capacity ------->| (9) - // - static final class CircularBuffer { + // name -> (value -> [index]) + private final Map>> map; + private long counter = 1; - int tail, head, size, capacity; - Object[] elements; + public HeaderTable(int maxSize, Logger logger) { + super(maxSize, logger); + map = new HashMap<>(); + } - CircularBuffer(int capacity) { - this.capacity = capacity; - elements = new Object[capacity]; - } + // + // This method returns: + // + // * a positive integer i where i (i = [1..Integer.MAX_VALUE]) is an + // index of an entry with a header (n, v), where n.equals(name) && + // v.equals(value) + // + // * a negative integer j where j (j = [-Integer.MAX_VALUE..-1]) is an + // index of an entry with a header (n, v), where n.equals(name) + // + // * 0 if there's no entry e such that e.getName().equals(name) + // + // The rationale behind this design is to allow to pack more useful data + // into a single invocation, facilitating a single pass where possible + // (the idea is the same as in java.util.Arrays.binarySearch(int[], int)). + // + public int indexOf(CharSequence name, CharSequence value) { + // Invoking toString() will possibly allocate Strings for the sake of + // the search, which doesn't feel right. + String n = name.toString(); + String v = value.toString(); - void add(E elem) { - if (size == capacity) { - throw new IllegalStateException( - format("No room for '%s': capacity=%s", elem, capacity)); - } - elements[head] = elem; - head = (head + 1) % capacity; - size++; - } - - @SuppressWarnings("unchecked") - E remove() { - if (size == 0) { - throw new NoSuchElementException("Empty"); + // 1. Try exact match in the static region + Map values = staticIndexes.get(n); + if (values != null) { + Integer idx = values.get(v); + if (idx != null) { + return idx; } - E elem = (E) elements[tail]; - elements[tail] = null; - tail = (tail + 1) % capacity; - size--; - return elem; } - - @SuppressWarnings("unchecked") - E get(int index) { - if (index < 0 || index >= size) { - throw new IndexOutOfBoundsException( - format("0 <= index <= capacity: index=%s, capacity=%s", - index, capacity)); + // 2. Try exact match in the dynamic region + int didx = search(n, v); + if (didx > 0) { + return STATIC_TABLE_LENGTH + didx; + } else if (didx < 0) { + if (values != null) { + // 3. Return name match from the static region + return -values.values().iterator().next(); // Iterator allocation + } else { + // 4. Return name match from the dynamic region + return -STATIC_TABLE_LENGTH + didx; } - int idx = (tail + (size - index - 1)) % capacity; - return (E) elements[idx]; - } - - public void resize(int newCapacity) { - if (newCapacity < size) { - throw new IllegalStateException( - format("newCapacity >= size: newCapacity=%s, size=%s", - newCapacity, size)); + } else { + if (values != null) { + // 3. Return name match from the static region + return -values.values().iterator().next(); // Iterator allocation + } else { + return 0; } - - Object[] newElements = new Object[newCapacity]; - - if (tail < head || size == 0) { - System.arraycopy(elements, tail, newElements, 0, size); - } else { - System.arraycopy(elements, tail, newElements, 0, elements.length - tail); - System.arraycopy(elements, 0, newElements, elements.length - tail, head); - } - - elements = newElements; - tail = 0; - head = size; - this.capacity = newCapacity; } } + + @Override + protected void add(HeaderField f) { + super.add(f); + Map> values = map.computeIfAbsent(f.name, k -> new HashMap<>()); + Deque indexes = values.computeIfAbsent(f.value, k -> new LinkedList<>()); + long counterSnapshot = counter++; + indexes.add(counterSnapshot); + assert indexesUniqueAndOrdered(indexes); + } + + private boolean indexesUniqueAndOrdered(Deque indexes) { + long maxIndexSoFar = -1; + for (long l : indexes) { + if (l <= maxIndexSoFar) { + return false; + } else { + maxIndexSoFar = l; + } + } + return true; + } + + int search(String name, String value) { + Map> values = map.get(name); + if (values == null) { + return 0; + } + Deque indexes = values.get(value); + if (indexes != null) { + return (int) (counter - indexes.peekLast()); + } else { + assert !values.isEmpty(); + Long any = values.values().iterator().next().peekLast(); // Iterator allocation + return -(int) (counter - any); + } + } + + @Override + protected HeaderField remove() { + HeaderField f = super.remove(); + Map> values = map.get(f.name); + Deque indexes = values.get(f.value); + Long index = indexes.pollFirst(); + if (indexes.isEmpty()) { + values.remove(f.value); + } + assert index != null; + if (values.isEmpty()) { + map.remove(f.name); + } + return f; + } } diff -r 49faeb51d1ca -r c08eb1e2dc38 src/java.net.http/share/classes/jdk/internal/net/http/hpack/IntegerWriter.java --- a/src/java.net.http/share/classes/jdk/internal/net/http/hpack/IntegerWriter.java Wed Apr 04 15:50:02 2018 +0100 +++ b/src/java.net.http/share/classes/jdk/internal/net/http/hpack/IntegerWriter.java Fri Apr 06 13:21:08 2018 +0100 @@ -90,7 +90,7 @@ } if (state == FIRST_BYTE_WRITTEN) { while (value >= 128 && output.hasRemaining()) { - output.put((byte) (value % 128 + 128)); + output.put((byte) ((value & 127) + 128)); value /= 128; } if (!output.hasRemaining()) { diff -r 49faeb51d1ca -r c08eb1e2dc38 src/java.net.http/share/classes/jdk/internal/net/http/hpack/SimpleHeaderTable.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/java.net.http/share/classes/jdk/internal/net/http/hpack/SimpleHeaderTable.java Fri Apr 06 13:21:08 2018 +0100 @@ -0,0 +1,370 @@ +/* + * Copyright (c) 2014, 2018, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Oracle designates this + * particular file as subject to the "Classpath" exception as provided + * by Oracle in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package jdk.internal.net.http.hpack; + +import jdk.internal.net.http.hpack.HPACK.Logger; +import jdk.internal.vm.annotation.Stable; + +import java.util.NoSuchElementException; + +import static jdk.internal.net.http.hpack.HPACK.Logger.Level.EXTRA; +import static jdk.internal.net.http.hpack.HPACK.Logger.Level.NORMAL; +import static java.lang.String.format; + +/* + * A header table consists of two tables, the static table and the dynamic + * table. Following the vocabulary of RFC 7541, the length of the header table + * is the total number of entries in both the static and the dynamic tables. + * The size of the table is the sum of the sizes of its dynamic table's entries. + */ +class SimpleHeaderTable { + + @Stable + protected static final HeaderField[] staticTable = { + null, // To make index 1-based, instead of 0-based + new HeaderField(":authority"), + new HeaderField(":method", "GET"), + new HeaderField(":method", "POST"), + new HeaderField(":path", "/"), + new HeaderField(":path", "/index.html"), + new HeaderField(":scheme", "http"), + new HeaderField(":scheme", "https"), + new HeaderField(":status", "200"), + new HeaderField(":status", "204"), + new HeaderField(":status", "206"), + new HeaderField(":status", "304"), + new HeaderField(":status", "400"), + new HeaderField(":status", "404"), + new HeaderField(":status", "500"), + new HeaderField("accept-charset"), + new HeaderField("accept-encoding", "gzip, deflate"), + new HeaderField("accept-language"), + new HeaderField("accept-ranges"), + new HeaderField("accept"), + new HeaderField("access-control-allow-origin"), + new HeaderField("age"), + new HeaderField("allow"), + new HeaderField("authorization"), + new HeaderField("cache-control"), + new HeaderField("content-disposition"), + new HeaderField("content-encoding"), + new HeaderField("content-language"), + new HeaderField("content-length"), + new HeaderField("content-location"), + new HeaderField("content-range"), + new HeaderField("content-type"), + new HeaderField("cookie"), + new HeaderField("date"), + new HeaderField("etag"), + new HeaderField("expect"), + new HeaderField("expires"), + new HeaderField("from"), + new HeaderField("host"), + new HeaderField("if-match"), + new HeaderField("if-modified-since"), + new HeaderField("if-none-match"), + new HeaderField("if-range"), + new HeaderField("if-unmodified-since"), + new HeaderField("last-modified"), + new HeaderField("link"), + new HeaderField("location"), + new HeaderField("max-forwards"), + new HeaderField("proxy-authenticate"), + new HeaderField("proxy-authorization"), + new HeaderField("range"), + new HeaderField("referer"), + new HeaderField("refresh"), + new HeaderField("retry-after"), + new HeaderField("server"), + new HeaderField("set-cookie"), + new HeaderField("strict-transport-security"), + new HeaderField("transfer-encoding"), + new HeaderField("user-agent"), + new HeaderField("vary"), + new HeaderField("via"), + new HeaderField("www-authenticate") + }; + + protected static final int STATIC_TABLE_LENGTH = staticTable.length - 1; + protected static final int ENTRY_SIZE = 32; + + private final Logger logger; + + private int maxSize; + private int size; + + public SimpleHeaderTable(int maxSize, Logger logger) { + this.logger = logger; + setMaxSize(maxSize); + } + + public int size() { + return size; + } + + public int maxSize() { + return maxSize; + } + + public int length() { + return STATIC_TABLE_LENGTH + buffer.size; + } + + HeaderField get(int index) { + checkIndex(index); + if (index <= STATIC_TABLE_LENGTH) { + return staticTable[index]; + } else { + return buffer.get(index - STATIC_TABLE_LENGTH - 1); + } + } + + void put(CharSequence name, CharSequence value) { + // Invoking toString() will possibly allocate Strings. But that's + // unavoidable at this stage. If a CharSequence is going to be stored in + // the table, it must not be mutable (e.g. for the sake of hashing). + put(new HeaderField(name.toString(), value.toString())); + } + + private void put(HeaderField h) { + if (logger.isLoggable(NORMAL)) { + logger.log(NORMAL, () -> format("adding ('%s', '%s')", + h.name, h.value)); + } + int entrySize = sizeOf(h); + if (logger.isLoggable(EXTRA)) { + logger.log(EXTRA, () -> format("size of ('%s', '%s') is %s", + h.name, h.value, entrySize)); + } + while (entrySize > maxSize - size && size != 0) { + if (logger.isLoggable(EXTRA)) { + logger.log(EXTRA, () -> format("insufficient space %s, must evict entry", + (maxSize - size))); + } + evictEntry(); + } + if (entrySize > maxSize - size) { + if (logger.isLoggable(EXTRA)) { + logger.log(EXTRA, () -> format("not adding ('%s, '%s'), too big", + h.name, h.value)); + } + return; + } + size += entrySize; + add(h); + if (logger.isLoggable(EXTRA)) { + logger.log(EXTRA, () -> format("('%s, '%s') added", h.name, h.value)); + logger.log(EXTRA, this::toString); + } + } + + void setMaxSize(int maxSize) { + if (maxSize < 0) { + throw new IllegalArgumentException( + "maxSize >= 0: maxSize=" + maxSize); + } + while (maxSize < size && size != 0) { + evictEntry(); + } + this.maxSize = maxSize; + // A header table cannot accommodate more entries than this + int upperBound = maxSize / ENTRY_SIZE; + buffer.resize(upperBound); + } + + HeaderField evictEntry() { + HeaderField f = remove(); + int s = sizeOf(f); + this.size -= s; + if (logger.isLoggable(EXTRA)) { + logger.log(EXTRA, () -> format("evicted entry ('%s', '%s') of size %s", + f.name, f.value, s)); + logger.log(EXTRA, this::toString); + } + return f; + } + + @Override + public String toString() { + double used = maxSize == 0 ? 0 : 100 * (((double) size) / maxSize); + return format("dynamic length: %d, full length: %s, used space: %s/%s (%.1f%%)", + buffer.size, length(), size, maxSize, used); + } + + private int checkIndex(int index) { + int len = length(); + if (index < 1 || index > len) { + throw new IndexOutOfBoundsException( + format("1 <= index <= length(): index=%s, length()=%s", + index, len)); + } + return index; + } + + int sizeOf(HeaderField f) { + return f.name.length() + f.value.length() + ENTRY_SIZE; + } + + // + // Diagnostic information in the form used in the RFC 7541 + // + String getStateString() { + if (size == 0) { + return "empty."; + } + + StringBuilder b = new StringBuilder(); + for (int i = 1, size = buffer.size; i <= size; i++) { + HeaderField e = buffer.get(i - 1); + b.append(format("[%3d] (s = %3d) %s: %s\n", i, + sizeOf(e), e.name, e.value)); + } + b.append(format(" Table size:%4s", this.size)); + return b.toString(); + } + + // Convert to a Value Object (JDK-8046159)? + protected static final class HeaderField { + + final String name; + final String value; + + public HeaderField(String name) { + this(name, ""); + } + + public HeaderField(String name, String value) { + this.name = name; + this.value = value; + } + + @Override + public String toString() { + return value.isEmpty() ? name : name + ": " + value; + } + + @Override // TODO: remove since used only for testing + public boolean equals(Object o) { + if (this == o) { + return true; + } + if (o == null || getClass() != o.getClass()) { + return false; + } + HeaderField that = (HeaderField) o; + return name.equals(that.name) && value.equals(that.value); + } + + @Override // TODO: remove since used only for testing + public int hashCode() { + return 31 * name.hashCode() + value.hashCode(); + } + } + + private final CircularBuffer buffer = new CircularBuffer<>(0); + + protected void add(HeaderField f) { + buffer.add(f); + } + + protected HeaderField remove() { + return buffer.remove(); + } + + // head + // v + // [ ][ ][A][B][C][D][ ][ ][ ] + // ^ + // tail + // + // |<- size ->| (4) + // |<------ capacity ------->| (9) + // + static final class CircularBuffer { + + int tail, head, size, capacity; + Object[] elements; + + CircularBuffer(int capacity) { + this.capacity = capacity; + elements = new Object[capacity]; + } + + void add(E elem) { + if (size == capacity) { + throw new IllegalStateException( + format("No room for '%s': capacity=%s", elem, capacity)); + } + elements[head] = elem; + head = (head + 1) % capacity; + size++; + } + + @SuppressWarnings("unchecked") + E remove() { + if (size == 0) { + throw new NoSuchElementException("Empty"); + } + E elem = (E) elements[tail]; + elements[tail] = null; + tail = (tail + 1) % capacity; + size--; + return elem; + } + + @SuppressWarnings("unchecked") + E get(int index) { + if (index < 0 || index >= size) { + throw new IndexOutOfBoundsException( + format("0 <= index <= capacity: index=%s, capacity=%s", + index, capacity)); + } + int idx = (tail + (size - index - 1)) % capacity; + return (E) elements[idx]; + } + + public void resize(int newCapacity) { + if (newCapacity < size) { + throw new IllegalStateException( + format("newCapacity >= size: newCapacity=%s, size=%s", + newCapacity, size)); + } + + Object[] newElements = new Object[newCapacity]; + + if (tail < head || size == 0) { + System.arraycopy(elements, tail, newElements, 0, size); + } else { + System.arraycopy(elements, tail, newElements, 0, elements.length - tail); + System.arraycopy(elements, 0, newElements, elements.length - tail, head); + } + + elements = newElements; + tail = 0; + head = size; + this.capacity = newCapacity; + } + } +} diff -r 49faeb51d1ca -r c08eb1e2dc38 test/jdk/java/net/httpclient/http2/java.net.http/jdk/internal/net/http/hpack/BinaryPrimitivesTest.java --- a/test/jdk/java/net/httpclient/http2/java.net.http/jdk/internal/net/http/hpack/BinaryPrimitivesTest.java Wed Apr 04 15:50:02 2018 +0100 +++ b/test/jdk/java/net/httpclient/http2/java.net.http/jdk/internal/net/http/hpack/BinaryPrimitivesTest.java Fri Apr 06 13:21:08 2018 +0100 @@ -44,7 +44,7 @@ // public final class BinaryPrimitivesTest { - private final Random rnd = newRandom(); + private final Random random = newRandom(); @Test public void integerRead1() { @@ -100,8 +100,8 @@ buf.clear(); } } - System.out.printf("totalCases: %,d, maxFilling: %,d, maxValue: %,d%n", - totalCases, maxFilling, MAX_VALUE); +// System.out.printf("totalCases: %,d, maxFilling: %,d, maxValue: %,d%n", +// totalCases, maxFilling, MAX_VALUE); } @Test @@ -111,9 +111,9 @@ ByteBuffer bb = ByteBuffer.allocate(8); IntegerWriter w = new IntegerWriter(); for (int i = 0; i < NUM_TESTS; i++) { - final int N = 1 + rnd.nextInt(8); - final int expected = rnd.nextInt(Integer.MAX_VALUE) + 1; - w.reset().configure(expected, N, rnd.nextInt()).write(bb); + final int N = 1 + random.nextInt(8); + final int expected = random.nextInt(Integer.MAX_VALUE) + 1; + w.reset().configure(expected, N, random.nextInt()).write(bb); bb.flip(); forEachSplit(bb, @@ -143,9 +143,9 @@ IntegerWriter w = new IntegerWriter(); IntegerReader r = new IntegerReader(); for (int i = 0; i < 1024; i++) { // number of tests - final int N = 1 + rnd.nextInt(8); - final int payload = rnd.nextInt(255); - final int expected = rnd.nextInt(Integer.MAX_VALUE) + 1; + final int N = 1 + random.nextInt(8); + final int payload = random.nextInt(255); + final int expected = random.nextInt(Integer.MAX_VALUE) + 1; forEachSplit(bb, (buffers) -> { @@ -195,7 +195,7 @@ chars.clear(); byte[] b = new byte[len]; - rnd.nextBytes(b); + random.nextBytes(b); String expected = new String(b, StandardCharsets.ISO_8859_1); // reference string @@ -236,7 +236,7 @@ for (int len = 0; len <= MAX_STRING_LENGTH; len++) { byte[] b = new byte[len]; - rnd.nextBytes(b); + random.nextBytes(b); String expected = new String(b, StandardCharsets.ISO_8859_1); // reference string @@ -276,7 +276,7 @@ for (int len = 0; len <= MAX_STRING_LENGTH; len++) { byte[] b = new byte[len]; - rnd.nextBytes(b); + random.nextBytes(b); String expected = new String(b, StandardCharsets.ISO_8859_1); // reference string @@ -325,7 +325,7 @@ // binary.clear(); // // byte[] bytes = new byte[len]; -// rnd.nextBytes(bytes); +// random.nextBytes(bytes); // // String s = new String(bytes, StandardCharsets.ISO_8859_1); // @@ -356,7 +356,7 @@ } catch (IOException e) { throw new UncheckedIOException(e); } - assertEquals(expected, reader.get()); + assertEquals(reader.get(), expected); } private void verifyWrite(byte[] expected, int data, int N) { @@ -364,6 +364,6 @@ ByteBuffer buf = ByteBuffer.allocate(2 * expected.length); w.configure(data, N, 1).write(buf); buf.flip(); - assertEquals(ByteBuffer.wrap(expected), buf); + assertEquals(buf, ByteBuffer.wrap(expected)); } } diff -r 49faeb51d1ca -r c08eb1e2dc38 test/jdk/java/net/httpclient/http2/java.net.http/jdk/internal/net/http/hpack/CircularBufferTest.java --- a/test/jdk/java/net/httpclient/http2/java.net.http/jdk/internal/net/http/hpack/CircularBufferTest.java Wed Apr 04 15:50:02 2018 +0100 +++ b/test/jdk/java/net/httpclient/http2/java.net.http/jdk/internal/net/http/hpack/CircularBufferTest.java Fri Apr 06 13:21:08 2018 +0100 @@ -22,25 +22,20 @@ */ package jdk.internal.net.http.hpack; -import org.testng.annotations.BeforeClass; import org.testng.annotations.Test; -import jdk.internal.net.http.hpack.HeaderTable.CircularBuffer; +import jdk.internal.net.http.hpack.SimpleHeaderTable.CircularBuffer; import java.util.Queue; import java.util.Random; import java.util.concurrent.ArrayBlockingQueue; import static org.testng.Assert.assertEquals; +import static jdk.internal.net.http.hpack.TestHelper.assertVoidThrows; import static jdk.internal.net.http.hpack.TestHelper.newRandom; public final class CircularBufferTest { - private final Random r = newRandom(); - - @BeforeClass - public void setUp() { - r.setSeed(System.currentTimeMillis()); - } + private final Random random = newRandom(); @Test public void queue() { @@ -62,6 +57,27 @@ buffer.resize(15); } + @Test + public void newCapacityLessThanCurrentSize1() { + CircularBuffer buffer = new CircularBuffer<>(0); + buffer.resize(5); + buffer.add(1); + buffer.add(1); + buffer.add(1); + assertVoidThrows(IllegalStateException.class, () -> buffer.resize(2)); + assertVoidThrows(IllegalStateException.class, () -> buffer.resize(1)); + } + + @Test + public void newCapacityLessThanCurrentSize2() { + CircularBuffer buffer = new CircularBuffer<>(5); + buffer.add(1); + buffer.add(1); + buffer.add(1); + assertVoidThrows(IllegalStateException.class, () -> buffer.resize(2)); + assertVoidThrows(IllegalStateException.class, () -> buffer.resize(1)); + } + private void resizeOnce(int capacity) { int nextNumberToPut = 0; @@ -74,12 +90,12 @@ buffer.add(nextNumberToPut); referenceQueue.add(nextNumberToPut); } - int gets = r.nextInt(capacity); // [0, capacity) + int gets = random.nextInt(capacity); // [0, capacity) for (int i = 0; i < gets; i++) { referenceQueue.poll(); buffer.remove(); } - int puts = r.nextInt(gets + 1); // [0, gets] + int puts = random.nextInt(gets + 1); // [0, gets] for (int i = 0; i < puts; i++, nextNumberToPut++) { buffer.add(nextNumberToPut); referenceQueue.add(nextNumberToPut); @@ -104,7 +120,7 @@ while (totalPuts < putsLimit) { assert remainingCapacity + size == capacity; - int puts = r.nextInt(remainingCapacity + 1); // [0, remainingCapacity] + int puts = random.nextInt(remainingCapacity + 1); // [0, remainingCapacity] remainingCapacity -= puts; size += puts; for (int i = 0; i < puts; i++, nextNumberToPut++) { @@ -112,7 +128,7 @@ buffer.add(nextNumberToPut); } totalPuts += puts; - int gets = r.nextInt(size + 1); // [0, size] + int gets = random.nextInt(size + 1); // [0, size] size -= gets; remainingCapacity += gets; for (int i = 0; i < gets; i++) { diff -r 49faeb51d1ca -r c08eb1e2dc38 test/jdk/java/net/httpclient/http2/java.net.http/jdk/internal/net/http/hpack/HeaderTableTest.java --- a/test/jdk/java/net/httpclient/http2/java.net.http/jdk/internal/net/http/hpack/HeaderTableTest.java Wed Apr 04 15:50:02 2018 +0100 +++ b/test/jdk/java/net/httpclient/http2/java.net.http/jdk/internal/net/http/hpack/HeaderTableTest.java Fri Apr 06 13:21:08 2018 +0100 @@ -22,101 +22,24 @@ */ package jdk.internal.net.http.hpack; +import jdk.internal.net.http.hpack.SimpleHeaderTable.HeaderField; import org.testng.annotations.Test; -import jdk.internal.net.http.hpack.HeaderTable.HeaderField; -import java.nio.charset.StandardCharsets; -import java.util.Collections; import java.util.HashMap; -import java.util.Locale; import java.util.Map; -import java.util.Random; -import java.util.regex.Matcher; -import java.util.regex.Pattern; - -import static java.lang.String.format; -import static org.testng.Assert.assertEquals; -import static jdk.internal.net.http.hpack.TestHelper.assertExceptionMessageContains; -import static jdk.internal.net.http.hpack.TestHelper.assertThrows; -import static jdk.internal.net.http.hpack.TestHelper.assertVoidThrows; -import static jdk.internal.net.http.hpack.TestHelper.newRandom; - -public class HeaderTableTest { - // - // https://tools.ietf.org/html/rfc7541#appendix-A - // - // @formatter:off - private static final String SPEC = - " | 1 | :authority | |\n" + - " | 2 | :method | GET |\n" + - " | 3 | :method | POST |\n" + - " | 4 | :path | / |\n" + - " | 5 | :path | /index.html |\n" + - " | 6 | :scheme | http |\n" + - " | 7 | :scheme | https |\n" + - " | 8 | :status | 200 |\n" + - " | 9 | :status | 204 |\n" + - " | 10 | :status | 206 |\n" + - " | 11 | :status | 304 |\n" + - " | 12 | :status | 400 |\n" + - " | 13 | :status | 404 |\n" + - " | 14 | :status | 500 |\n" + - " | 15 | accept-charset | |\n" + - " | 16 | accept-encoding | gzip, deflate |\n" + - " | 17 | accept-language | |\n" + - " | 18 | accept-ranges | |\n" + - " | 19 | accept | |\n" + - " | 20 | access-control-allow-origin | |\n" + - " | 21 | age | |\n" + - " | 22 | allow | |\n" + - " | 23 | authorization | |\n" + - " | 24 | cache-control | |\n" + - " | 25 | content-disposition | |\n" + - " | 26 | content-encoding | |\n" + - " | 27 | content-language | |\n" + - " | 28 | content-length | |\n" + - " | 29 | content-location | |\n" + - " | 30 | content-range | |\n" + - " | 31 | content-type | |\n" + - " | 32 | cookie | |\n" + - " | 33 | date | |\n" + - " | 34 | etag | |\n" + - " | 35 | expect | |\n" + - " | 36 | expires | |\n" + - " | 37 | from | |\n" + - " | 38 | host | |\n" + - " | 39 | if-match | |\n" + - " | 40 | if-modified-since | |\n" + - " | 41 | if-none-match | |\n" + - " | 42 | if-range | |\n" + - " | 43 | if-unmodified-since | |\n" + - " | 44 | last-modified | |\n" + - " | 45 | link | |\n" + - " | 46 | location | |\n" + - " | 47 | max-forwards | |\n" + - " | 48 | proxy-authenticate | |\n" + - " | 49 | proxy-authorization | |\n" + - " | 50 | range | |\n" + - " | 51 | referer | |\n" + - " | 52 | refresh | |\n" + - " | 53 | retry-after | |\n" + - " | 54 | server | |\n" + - " | 55 | set-cookie | |\n" + - " | 56 | strict-transport-security | |\n" + - " | 57 | transfer-encoding | |\n" + - " | 58 | user-agent | |\n" + - " | 59 | vary | |\n" + - " | 60 | via | |\n" + - " | 61 | www-authenticate | |\n"; - // @formatter:on +import static org.testng.Assert.assertEquals; + +public class HeaderTableTest extends SimpleHeaderTableTest { - private static final int STATIC_TABLE_LENGTH = createStaticEntries().size(); - private final Random rnd = newRandom(); + @Override + protected HeaderTable createHeaderTable(int maxSize) { + return new HeaderTable(maxSize, HPACK.getLogger()); + } @Test public void staticData() { - HeaderTable table = new HeaderTable(0, HPACK.getLogger()); + HeaderTable table = createHeaderTable(0); Map staticHeaderFields = createStaticEntries(); Map minimalIndexes = new HashMap<>(); @@ -157,88 +80,8 @@ } @Test - public void constructorSetsMaxSize() { - int size = rnd.nextInt(64); - HeaderTable t = new HeaderTable(size, HPACK.getLogger()); - assertEquals(t.size(), 0); - assertEquals(t.maxSize(), size); - } - - @Test - public void negativeMaximumSize() { - int maxSize = -(rnd.nextInt(100) + 1); // [-100, -1] - IllegalArgumentException e = - assertVoidThrows(IllegalArgumentException.class, - () -> new HeaderTable(0, HPACK.getLogger()).setMaxSize(maxSize)); - assertExceptionMessageContains(e, "maxSize"); - } - - @Test - public void zeroMaximumSize() { - HeaderTable table = new HeaderTable(0, HPACK.getLogger()); - table.setMaxSize(0); - assertEquals(table.maxSize(), 0); - } - - @Test - public void negativeIndex() { - int idx = -(rnd.nextInt(256) + 1); // [-256, -1] - IndexOutOfBoundsException e = - assertVoidThrows(IndexOutOfBoundsException.class, - () -> new HeaderTable(0, HPACK.getLogger()).get(idx)); - assertExceptionMessageContains(e, "index"); - } - - @Test - public void zeroIndex() { - IndexOutOfBoundsException e = - assertThrows(IndexOutOfBoundsException.class, - () -> new HeaderTable(0, HPACK.getLogger()).get(0)); - assertExceptionMessageContains(e, "index"); - } - - @Test - public void length() { - HeaderTable table = new HeaderTable(0, HPACK.getLogger()); - assertEquals(table.length(), STATIC_TABLE_LENGTH); - } - - @Test - public void indexOutsideStaticRange() { - HeaderTable table = new HeaderTable(0, HPACK.getLogger()); - int idx = table.length() + (rnd.nextInt(256) + 1); - IndexOutOfBoundsException e = - assertThrows(IndexOutOfBoundsException.class, - () -> table.get(idx)); - assertExceptionMessageContains(e, "index"); - } - - @Test - public void entryPutAfterStaticArea() { - HeaderTable table = new HeaderTable(256, HPACK.getLogger()); - int idx = table.length() + 1; - assertThrows(IndexOutOfBoundsException.class, () -> table.get(idx)); - - byte[] bytes = new byte[32]; - rnd.nextBytes(bytes); - String name = new String(bytes, StandardCharsets.ISO_8859_1); - String value = "custom-value"; - - table.put(name, value); - HeaderField f = table.get(idx); - assertEquals(name, f.name); - assertEquals(value, f.value); - } - - @Test - public void staticTableHasZeroSize() { - HeaderTable table = new HeaderTable(0, HPACK.getLogger()); - assertEquals(0, table.size()); - } - - @Test public void lowerIndexPriority() { - HeaderTable table = new HeaderTable(256, HPACK.getLogger()); + HeaderTable table = createHeaderTable(256); int oldLength = table.length(); table.put("bender", "rodriguez"); table.put("bender", "rodriguez"); @@ -246,178 +89,63 @@ assertEquals(table.length(), oldLength + 3); // more like an assumption int i = table.indexOf("bender", "rodriguez"); - assertEquals(oldLength + 1, i); + assertEquals(i, oldLength + 1); } @Test public void indexesAreNotLost2() { - HeaderTable table = new HeaderTable(256, HPACK.getLogger()); + HeaderTable table = createHeaderTable(256); int oldLength = table.length(); table.put("bender", "rodriguez"); - assertEquals(oldLength + 1, table.indexOf("bender", "rodriguez")); + assertEquals(table.indexOf("bender", "rodriguez"), oldLength + 1); table.put("bender", "rodriguez"); - assertEquals(oldLength + 1, table.indexOf("bender", "rodriguez")); + assertEquals(table.indexOf("bender", "rodriguez"), oldLength + 1); table.evictEntry(); - assertEquals(oldLength + 1, table.indexOf("bender", "rodriguez")); + assertEquals(table.indexOf("bender", "rodriguez"), oldLength + 1); table.evictEntry(); - assertEquals(0, table.indexOf("bender", "rodriguez")); + assertEquals(table.indexOf("bender", "rodriguez"), 0); } @Test public void lowerIndexPriority2() { - HeaderTable table = new HeaderTable(256, HPACK.getLogger()); + HeaderTable table = createHeaderTable(256); int oldLength = table.length(); int idx = rnd.nextInt(oldLength) + 1; HeaderField f = table.get(idx); table.put(f.name, f.value); assertEquals(table.length(), oldLength + 1); int i = table.indexOf(f.name, f.value); - assertEquals(idx, i); - } - - // TODO: negative indexes check - // TODO: ensure full table clearance when adding huge header field - // TODO: ensure eviction deletes minimum needed entries, not more - - @Test - public void fifo() { - // Let's add a series of header fields - int NUM_HEADERS = 32; - HeaderTable t = new HeaderTable((32 + 4) * NUM_HEADERS, HPACK.getLogger()); - // ^ ^ - // entry overhead symbols per entry (max 2x2 digits) - for (int i = 1; i <= NUM_HEADERS; i++) { - String s = String.valueOf(i); - t.put(s, s); - } - // They MUST appear in a FIFO order: - // newer entries are at lower indexes - // older entries are at higher indexes - for (int j = 1; j <= NUM_HEADERS; j++) { - HeaderField f = t.get(STATIC_TABLE_LENGTH + j); - int actualName = Integer.parseInt(f.name); - int expectedName = NUM_HEADERS - j + 1; - assertEquals(expectedName, actualName); - } - // Entries MUST be evicted in the order they were added: - // the newer the entry the later it is evicted - for (int k = 1; k <= NUM_HEADERS; k++) { - HeaderField f = t.evictEntry(); - assertEquals(String.valueOf(k), f.name); - } + assertEquals(i, idx); } @Test public void indexOf() { // Let's put a series of header fields int NUM_HEADERS = 32; - HeaderTable t = new HeaderTable((32 + 4) * NUM_HEADERS, HPACK.getLogger()); - // ^ ^ - // entry overhead symbols per entry (max 2x2 digits) + HeaderTable table = + createHeaderTable((32 + 4) * NUM_HEADERS); + // ^ ^ + // entry overhead symbols per entry (max 2x2 digits) for (int i = 1; i <= NUM_HEADERS; i++) { String s = String.valueOf(i); - t.put(s, s); + table.put(s, s); } // and verify indexOf (reverse lookup) returns correct indexes for // full lookup for (int j = 1; j <= NUM_HEADERS; j++) { String s = String.valueOf(j); - int actualIndex = t.indexOf(s, s); + int actualIndex = table.indexOf(s, s); int expectedIndex = STATIC_TABLE_LENGTH + NUM_HEADERS - j + 1; - assertEquals(expectedIndex, actualIndex); + assertEquals(actualIndex, expectedIndex); } // as well as for just a name lookup for (int j = 1; j <= NUM_HEADERS; j++) { String s = String.valueOf(j); - int actualIndex = t.indexOf(s, "blah"); + int actualIndex = table.indexOf(s, "blah"); int expectedIndex = -(STATIC_TABLE_LENGTH + NUM_HEADERS - j + 1); - assertEquals(expectedIndex, actualIndex); + assertEquals(actualIndex, expectedIndex); } // lookup for non-existent name returns 0 - assertEquals(0, t.indexOf("chupacabra", "1")); - } - - @Test - public void testToString() { - testToString0(); - } - - @Test - public void testToStringDifferentLocale() { - Locale locale = Locale.getDefault(); - Locale.setDefault(Locale.FRENCH); - try { - String s = format("%.1f", 3.1); - assertEquals("3,1", s); // assumption of the test, otherwise the test is useless - testToString0(); - } finally { - Locale.setDefault(locale); - } - } - - private void testToString0() { - HeaderTable table = new HeaderTable(0, HPACK.getLogger()); - { - int maxSize = 2048; - table.setMaxSize(maxSize); - String expected = format( - "dynamic length: %s, full length: %s, used space: %s/%s (%.1f%%)", - 0, STATIC_TABLE_LENGTH, 0, maxSize, 0.0); - assertEquals(expected, table.toString()); - } - - { - String name = "custom-name"; - String value = "custom-value"; - int size = 512; - - table.setMaxSize(size); - table.put(name, value); - String s = table.toString(); - - int used = name.length() + value.length() + 32; - double ratio = used * 100.0 / size; - - String expected = format( - "dynamic length: %s, full length: %s, used space: %s/%s (%.1f%%)", - 1, STATIC_TABLE_LENGTH + 1, used, size, ratio); - assertEquals(expected, s); - } - - { - table.setMaxSize(78); - table.put(":method", ""); - table.put(":status", ""); - String s = table.toString(); - String expected = - format("dynamic length: %s, full length: %s, used space: %s/%s (%.1f%%)", - 2, STATIC_TABLE_LENGTH + 2, 78, 78, 100.0); - assertEquals(expected, s); - } - } - - @Test - public void stateString() { - HeaderTable table = new HeaderTable(256, HPACK.getLogger()); - table.put("custom-key", "custom-header"); - // @formatter:off - assertEquals("[ 1] (s = 55) custom-key: custom-header\n" + - " Table size: 55", table.getStateString()); - // @formatter:on - } - - private static Map createStaticEntries() { - Pattern line = Pattern.compile( - "\\|\\s*(?\\d+?)\\s*\\|\\s*(?.+?)\\s*\\|\\s*(?.*?)\\s*\\|"); - Matcher m = line.matcher(SPEC); - Map result = new HashMap<>(); - while (m.find()) { - int index = Integer.parseInt(m.group("index")); - String name = m.group("name"); - String value = m.group("value"); - HeaderField f = new HeaderField(name, value); - result.put(index, f); - } - return Collections.unmodifiableMap(result); // lol + assertEquals(table.indexOf("chupacabra", "1"), 0); } } diff -r 49faeb51d1ca -r c08eb1e2dc38 test/jdk/java/net/httpclient/http2/java.net.http/jdk/internal/net/http/hpack/SimpleHeaderTableTest.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/jdk/java/net/httpclient/http2/java.net.http/jdk/internal/net/http/hpack/SimpleHeaderTableTest.java Fri Apr 06 13:21:08 2018 +0100 @@ -0,0 +1,332 @@ +/* + * Copyright (c) 2014, 2018, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package jdk.internal.net.http.hpack; + +import jdk.internal.net.http.hpack.SimpleHeaderTable.HeaderField; +import org.testng.annotations.Test; + +import java.nio.charset.StandardCharsets; +import java.util.Collections; +import java.util.HashMap; +import java.util.Locale; +import java.util.Map; +import java.util.Random; +import java.util.regex.Matcher; +import java.util.regex.Pattern; + +import static jdk.internal.net.http.hpack.TestHelper.assertExceptionMessageContains; +import static jdk.internal.net.http.hpack.TestHelper.assertThrows; +import static jdk.internal.net.http.hpack.TestHelper.assertVoidThrows; +import static jdk.internal.net.http.hpack.TestHelper.newRandom; +import static java.lang.String.format; +import static org.testng.Assert.assertEquals; + +public class SimpleHeaderTableTest { + + // + // https://tools.ietf.org/html/rfc7541#appendix-A + // + // @formatter:off + private static final String SPEC = + " | 1 | :authority | |\n" + + " | 2 | :method | GET |\n" + + " | 3 | :method | POST |\n" + + " | 4 | :path | / |\n" + + " | 5 | :path | /index.html |\n" + + " | 6 | :scheme | http |\n" + + " | 7 | :scheme | https |\n" + + " | 8 | :status | 200 |\n" + + " | 9 | :status | 204 |\n" + + " | 10 | :status | 206 |\n" + + " | 11 | :status | 304 |\n" + + " | 12 | :status | 400 |\n" + + " | 13 | :status | 404 |\n" + + " | 14 | :status | 500 |\n" + + " | 15 | accept-charset | |\n" + + " | 16 | accept-encoding | gzip, deflate |\n" + + " | 17 | accept-language | |\n" + + " | 18 | accept-ranges | |\n" + + " | 19 | accept | |\n" + + " | 20 | access-control-allow-origin | |\n" + + " | 21 | age | |\n" + + " | 22 | allow | |\n" + + " | 23 | authorization | |\n" + + " | 24 | cache-control | |\n" + + " | 25 | content-disposition | |\n" + + " | 26 | content-encoding | |\n" + + " | 27 | content-language | |\n" + + " | 28 | content-length | |\n" + + " | 29 | content-location | |\n" + + " | 30 | content-range | |\n" + + " | 31 | content-type | |\n" + + " | 32 | cookie | |\n" + + " | 33 | date | |\n" + + " | 34 | etag | |\n" + + " | 35 | expect | |\n" + + " | 36 | expires | |\n" + + " | 37 | from | |\n" + + " | 38 | host | |\n" + + " | 39 | if-match | |\n" + + " | 40 | if-modified-since | |\n" + + " | 41 | if-none-match | |\n" + + " | 42 | if-range | |\n" + + " | 43 | if-unmodified-since | |\n" + + " | 44 | last-modified | |\n" + + " | 45 | link | |\n" + + " | 46 | location | |\n" + + " | 47 | max-forwards | |\n" + + " | 48 | proxy-authenticate | |\n" + + " | 49 | proxy-authorization | |\n" + + " | 50 | range | |\n" + + " | 51 | referer | |\n" + + " | 52 | refresh | |\n" + + " | 53 | retry-after | |\n" + + " | 54 | server | |\n" + + " | 55 | set-cookie | |\n" + + " | 56 | strict-transport-security | |\n" + + " | 57 | transfer-encoding | |\n" + + " | 58 | user-agent | |\n" + + " | 59 | vary | |\n" + + " | 60 | via | |\n" + + " | 61 | www-authenticate | |\n"; + // @formatter:on + + static final int STATIC_TABLE_LENGTH = createStaticEntries().size(); + final Random rnd = newRandom(); + + /** Creates a header table under test. Override in subclass. */ + protected SimpleHeaderTable createHeaderTable(int maxSize) { + return new SimpleHeaderTable(maxSize, HPACK.getLogger()); + } + + @Test + public void staticData0() { + SimpleHeaderTable table = createHeaderTable(0); + Map staticHeaderFields = createStaticEntries(); + staticHeaderFields.forEach((index, expectedHeaderField) -> { + SimpleHeaderTable.HeaderField actualHeaderField = table.get(index); + assertEquals(actualHeaderField, expectedHeaderField); + }); + } + + @Test + public void constructorSetsMaxSize() { + int size = rnd.nextInt(64); + SimpleHeaderTable table = createHeaderTable(size); + assertEquals(table.size(), 0); + assertEquals(table.maxSize(), size); + } + + @Test + public void negativeMaximumSize() { + int maxSize = -(rnd.nextInt(100) + 1); // [-100, -1] + SimpleHeaderTable table = createHeaderTable(0); + IllegalArgumentException e = + assertVoidThrows(IllegalArgumentException.class, + () -> table.setMaxSize(maxSize)); + assertExceptionMessageContains(e, "maxSize"); + } + + @Test + public void zeroMaximumSize() { + SimpleHeaderTable table = createHeaderTable(0); + table.setMaxSize(0); + assertEquals(table.maxSize(), 0); + } + + @Test + public void negativeIndex() { + int idx = -(rnd.nextInt(256) + 1); // [-256, -1] + SimpleHeaderTable table = createHeaderTable(0); + IndexOutOfBoundsException e = + assertVoidThrows(IndexOutOfBoundsException.class, + () -> table.get(idx)); + assertExceptionMessageContains(e, "index"); + } + + @Test + public void zeroIndex() { + SimpleHeaderTable table = createHeaderTable(0); + IndexOutOfBoundsException e = + assertThrows(IndexOutOfBoundsException.class, + () -> table.get(0)); + assertExceptionMessageContains(e, "index"); + } + + @Test + public void length() { + SimpleHeaderTable table = createHeaderTable(0); + assertEquals(table.length(), STATIC_TABLE_LENGTH); + } + + @Test + public void indexOutsideStaticRange() { + SimpleHeaderTable table = createHeaderTable(0); + int idx = table.length() + (rnd.nextInt(256) + 1); + IndexOutOfBoundsException e = + assertThrows(IndexOutOfBoundsException.class, + () -> table.get(idx)); + assertExceptionMessageContains(e, "index"); + } + + @Test + public void entryPutAfterStaticArea() { + SimpleHeaderTable table = createHeaderTable(256); + int idx = table.length() + 1; + assertThrows(IndexOutOfBoundsException.class, () -> table.get(idx)); + + byte[] bytes = new byte[32]; + rnd.nextBytes(bytes); + String name = new String(bytes, StandardCharsets.ISO_8859_1); + String value = "custom-value"; + + table.put(name, value); + SimpleHeaderTable.HeaderField f = table.get(idx); + assertEquals(f.name, name); + assertEquals(f.value, value); + } + + @Test + public void staticTableHasZeroSize() { + SimpleHeaderTable table = createHeaderTable(0); + assertEquals(table.size(), 0); + } + + // TODO: negative indexes check + // TODO: ensure full table clearance when adding huge header field + // TODO: ensure eviction deletes minimum needed entries, not more + + @Test + public void fifo() { + // Let's add a series of header fields + int NUM_HEADERS = 32; + SimpleHeaderTable table = + createHeaderTable((32 + 4) * NUM_HEADERS); + // ^ ^ + // entry overhead symbols per entry (max 2x2 digits) + for (int i = 1; i <= NUM_HEADERS; i++) { + String s = String.valueOf(i); + table.put(s, s); + } + // They MUST appear in a FIFO order: + // newer entries are at lower indexes + // older entries are at higher indexes + for (int j = 1; j <= NUM_HEADERS; j++) { + SimpleHeaderTable.HeaderField f = table.get(STATIC_TABLE_LENGTH + j); + int actualName = Integer.parseInt(f.name); + int expectedName = NUM_HEADERS - j + 1; + assertEquals(actualName, expectedName); + } + // Entries MUST be evicted in the order they were added: + // the newer the entry the later it is evicted + for (int k = 1; k <= NUM_HEADERS; k++) { + SimpleHeaderTable.HeaderField f = table.evictEntry(); + assertEquals(f.name, String.valueOf(k)); + } + } + + @Test + public void testToString() { + testToString0(); + } + + @Test + public void testToStringDifferentLocale() { + Locale locale = Locale.getDefault(); + Locale.setDefault(Locale.FRENCH); + try { + String s = format("%.1f", 3.1); + assertEquals(s, "3,1"); // assumption of the test, otherwise the test is useless + testToString0(); + } finally { + Locale.setDefault(locale); + } + } + + private void testToString0() { + SimpleHeaderTable table = createHeaderTable(0); + { + int maxSize = 2048; + table.setMaxSize(maxSize); + String expected = format( + "dynamic length: %s, full length: %s, used space: %s/%s (%.1f%%)", + 0, STATIC_TABLE_LENGTH, 0, maxSize, 0.0); + assertEquals(table.toString(), expected); + } + + { + String name = "custom-name"; + String value = "custom-value"; + int size = 512; + + table.setMaxSize(size); + table.put(name, value); + String s = table.toString(); + + int used = name.length() + value.length() + 32; + double ratio = used * 100.0 / size; + + String expected = format( + "dynamic length: %s, full length: %s, used space: %s/%s (%.1f%%)", + 1, STATIC_TABLE_LENGTH + 1, used, size, ratio); + assertEquals(s, expected); + } + + { + table.setMaxSize(78); + table.put(":method", ""); + table.put(":status", ""); + String s = table.toString(); + String expected = + format("dynamic length: %s, full length: %s, used space: %s/%s (%.1f%%)", + 2, STATIC_TABLE_LENGTH + 2, 78, 78, 100.0); + assertEquals(s, expected); + } + } + + @Test + public void stateString() { + SimpleHeaderTable table = createHeaderTable(256); + table.put("custom-key", "custom-header"); + // @formatter:off + assertEquals(table.getStateString(), + "[ 1] (s = 55) custom-key: custom-header\n" + + " Table size: 55"); + // @formatter:on + } + + static Map createStaticEntries() { + Pattern line = Pattern.compile( + "\\|\\s*(?\\d+?)\\s*\\|\\s*(?.+?)\\s*\\|\\s*(?.*?)\\s*\\|"); + Matcher m = line.matcher(SPEC); + Map result = new HashMap<>(); + while (m.find()) { + int index = Integer.parseInt(m.group("index")); + String name = m.group("name"); + String value = m.group("value"); + HeaderField f = new HeaderField(name, value); + result.put(index, f); + } + return Collections.unmodifiableMap(result); // lol + } +}