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.internal.vm.annotation.Stable;
28
29 import java.util.HashMap;
30 import java.util.LinkedHashMap;
31 import java.util.Map;
32 import java.util.NoSuchElementException;
33
34 import static java.lang.String.format;
35
36 //
37 // Header Table combined from two tables: static and dynamic.
38 //
39 // There is a single address space for index values. Index-aware methods
40 // correspond to the table as a whole. Size-aware methods only to the dynamic
41 // part of it.
42 //
43 final class HeaderTable {
44
45 @Stable
46 private static final HeaderField[] staticTable = {
47 null, // To make index 1-based, instead of 0-based
48 new HeaderField(":authority"),
49 new HeaderField(":method", "GET"),
50 new HeaderField(":method", "POST"),
51 new HeaderField(":path", "/"),
52 new HeaderField(":path", "/index.html"),
53 new HeaderField(":scheme", "http"),
54 new HeaderField(":scheme", "https"),
105 new HeaderField("user-agent"),
106 new HeaderField("vary"),
107 new HeaderField("via"),
108 new HeaderField("www-authenticate")
109 };
110
111 private static final int STATIC_TABLE_LENGTH = staticTable.length - 1;
112 private static final int ENTRY_SIZE = 32;
113 private static final Map<String, LinkedHashMap<String, Integer>> staticIndexes;
114
115 static {
116 staticIndexes = new HashMap<>(STATIC_TABLE_LENGTH); // TODO: Map.of
117 for (int i = 1; i <= STATIC_TABLE_LENGTH; i++) {
118 HeaderField f = staticTable[i];
119 Map<String, Integer> values = staticIndexes
120 .computeIfAbsent(f.name, k -> new LinkedHashMap<>());
121 values.put(f.value, i);
122 }
123 }
124
125 private final Table dynamicTable = new Table(0);
126 private int maxSize;
127 private int size;
128
129 public HeaderTable(int maxSize) {
130 setMaxSize(maxSize);
131 }
132
133 //
134 // The method returns:
135 //
136 // * a positive integer i where i (i = [1..Integer.MAX_VALUE]) is an
137 // index of an entry with a header (n, v), where n.equals(name) &&
138 // v.equals(value)
139 //
140 // * a negative integer j where j (j = [-Integer.MAX_VALUE..-1]) is an
141 // index of an entry with a header (n, v), where n.equals(name)
142 //
143 // * 0 if there's no entry e such that e.getName().equals(name)
144 //
145 // The rationale behind this design is to allow to pack more useful data
146 // into a single invocation, facilitating a single pass where possible
147 // (the idea is the same as in java.util.Arrays.binarySearch(int[], int)).
148 //
149 public int indexOf(CharSequence name, CharSequence value) {
194 return STATIC_TABLE_LENGTH + dynamicTable.size();
195 }
196
197 HeaderField get(int index) {
198 checkIndex(index);
199 if (index <= STATIC_TABLE_LENGTH) {
200 return staticTable[index];
201 } else {
202 return dynamicTable.get(index - STATIC_TABLE_LENGTH);
203 }
204 }
205
206 void put(CharSequence name, CharSequence value) {
207 // Invoking toString() will possibly allocate Strings. But that's
208 // unavoidable at this stage. If a CharSequence is going to be stored in
209 // the table, it must not be mutable (e.g. for the sake of hashing).
210 put(new HeaderField(name.toString(), value.toString()));
211 }
212
213 private void put(HeaderField h) {
214 int entrySize = sizeOf(h);
215 while (entrySize > maxSize - size && size != 0) {
216 evictEntry();
217 }
218 if (entrySize > maxSize - size) {
219 return;
220 }
221 size += entrySize;
222 dynamicTable.add(h);
223 }
224
225 void setMaxSize(int maxSize) {
226 if (maxSize < 0) {
227 throw new IllegalArgumentException
228 ("maxSize >= 0: maxSize=" + maxSize);
229 }
230 while (maxSize < size && size != 0) {
231 evictEntry();
232 }
233 this.maxSize = maxSize;
234 int upperBound = (maxSize / ENTRY_SIZE) + 1;
235 this.dynamicTable.setCapacity(upperBound);
236 }
237
238 HeaderField evictEntry() {
239 HeaderField f = dynamicTable.remove();
240 size -= sizeOf(f);
241 return f;
242 }
243
244 @Override
245 public String toString() {
246 double used = maxSize == 0 ? 0 : 100 * (((double) size) / maxSize);
247 return format("entries: %d; used %s/%s (%.1f%%)", dynamicTable.size(),
248 size, maxSize, used);
249 }
250
251 int checkIndex(int index) {
252 if (index < 1 || index > STATIC_TABLE_LENGTH + dynamicTable.size()) {
253 throw new IllegalArgumentException(
254 format("1 <= index <= length(): index=%s, length()=%s",
255 index, length()));
256 }
257 return index;
258 }
259
260 int sizeOf(HeaderField f) {
261 return f.name.length() + f.value.length() + ENTRY_SIZE;
262 }
263
264 //
265 // Diagnostic information in the form used in the RFC 7541
266 //
267 String getStateString() {
268 if (size == 0) {
269 return "empty.";
270 }
271
272 StringBuilder b = new StringBuilder();
273 for (int i = 1, size = dynamicTable.size(); i <= size; i++) {
274 HeaderField e = dynamicTable.get(i);
275 b.append(format("[%3d] (s = %3d) %s: %s\n", i,
|
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"),
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) {
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,
|