1 /*
2 * Copyright (c) 2014, 2017, 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.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"),
55 new HeaderField(":status", "200"),
56 new HeaderField(":status", "204"),
57 new HeaderField(":status", "206"),
58 new HeaderField(":status", "304"),
59 new HeaderField(":status", "400"),
60 new HeaderField(":status", "404"),
61 new HeaderField(":status", "500"),
62 new HeaderField("accept-charset"),
63 new HeaderField("accept-encoding", "gzip, deflate"),
64 new HeaderField("accept-language"),
65 new HeaderField("accept-ranges"),
66 new HeaderField("accept"),
67 new HeaderField("access-control-allow-origin"),
68 new HeaderField("age"),
69 new HeaderField("allow"),
70 new HeaderField("authorization"),
71 new HeaderField("cache-control"),
72 new HeaderField("content-disposition"),
73 new HeaderField("content-encoding"),
74 new HeaderField("content-language"),
75 new HeaderField("content-length"),
76 new HeaderField("content-location"),
77 new HeaderField("content-range"),
78 new HeaderField("content-type"),
79 new HeaderField("cookie"),
80 new HeaderField("date"),
81 new HeaderField("etag"),
82 new HeaderField("expect"),
83 new HeaderField("expires"),
84 new HeaderField("from"),
85 new HeaderField("host"),
86 new HeaderField("if-match"),
87 new HeaderField("if-modified-since"),
88 new HeaderField("if-none-match"),
89 new HeaderField("if-range"),
90 new HeaderField("if-unmodified-since"),
91 new HeaderField("last-modified"),
92 new HeaderField("link"),
93 new HeaderField("location"),
94 new HeaderField("max-forwards"),
95 new HeaderField("proxy-authenticate"),
96 new HeaderField("proxy-authorization"),
97 new HeaderField("range"),
98 new HeaderField("referer"),
99 new HeaderField("refresh"),
100 new HeaderField("retry-after"),
101 new HeaderField("server"),
102 new HeaderField("set-cookie"),
103 new HeaderField("strict-transport-security"),
104 new HeaderField("transfer-encoding"),
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) {
150 // Invoking toString() will possibly allocate Strings for the sake of
151 // the search, which doesn't feel right.
152 String n = name.toString();
153 String v = value.toString();
154
155 // 1. Try exact match in the static region
156 Map<String, Integer> values = staticIndexes.get(n);
157 if (values != null) {
158 Integer idx = values.get(v);
159 if (idx != null) {
160 return idx;
161 }
162 }
163 // 2. Try exact match in the dynamic region
164 int didx = dynamicTable.indexOf(n, v);
165 if (didx > 0) {
166 return STATIC_TABLE_LENGTH + didx;
167 } else if (didx < 0) {
168 if (values != null) {
169 // 3. Return name match from the static region
170 return -values.values().iterator().next(); // Iterator allocation
171 } else {
172 // 4. Return name match from the dynamic region
173 return -STATIC_TABLE_LENGTH + didx;
174 }
175 } else {
176 if (values != null) {
177 // 3. Return name match from the static region
178 return -values.values().iterator().next(); // Iterator allocation
179 } else {
180 return 0;
181 }
182 }
183 }
184
185 public int size() {
186 return size;
187 }
188
189 public int maxSize() {
190 return maxSize;
191 }
192
193 public int length() {
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,
276 sizeOf(e), e.name, e.value));
277 }
278 b.append(format(" Table size:%4s", this.size));
279 return b.toString();
280 }
281
282 // Convert to a Value Object (JDK-8046159)?
283 static final class HeaderField {
284
285 final String name;
286 final String value;
287
288 public HeaderField(String name) {
289 this(name, "");
290 }
291
292 public HeaderField(String name, String value) {
293 this.name = name;
294 this.value = value;
295 }
296
297 @Override
298 public String toString() {
299 return value.isEmpty() ? name : name + ": " + value;
300 }
301
302 @Override
303 public boolean equals(Object o) {
304 if (this == o) {
305 return true;
306 }
307 if (o == null || getClass() != o.getClass()) {
308 return false;
309 }
310 HeaderField that = (HeaderField) o;
311 return name.equals(that.name) && value.equals(that.value);
312 }
313
314 @Override
315 public int hashCode() {
316 return 31 * name.hashCode() + value.hashCode();
317 }
318 }
319
320 //
321 // To quickly find an index of an entry in the dynamic table with the given
322 // contents an effective inverse mapping is needed. Here's a simple idea
323 // behind such a mapping.
324 //
325 // # The problem:
326 //
327 // We have a queue with an O(1) lookup by index:
328 //
329 // get: index -> x
330 //
331 // What we want is an O(1) reverse lookup:
332 //
333 // indexOf: x -> index
334 //
335 // # Solution:
336 //
337 // Let's store an inverse mapping in a Map<x, Integer>. This have a problem
338 // that when a new element is added to the queue, all indexes in the map
339 // become invalid. Namely, the new element is assigned with an index of 1,
340 // and each index i, i > 1 becomes shifted by 1 to the left:
341 //
342 // 1, 1, 2, 3, ... , n-1, n
343 //
344 // Re-establishing the invariant would seem to require a pass through the
345 // map incrementing all indexes (map values) by 1, which is O(n).
346 //
347 // The good news is we can do much better then this!
348 //
349 // Let's create a single field of type long, called 'counter'. Then each
350 // time a new element 'x' is added to the queue, a value of this field gets
351 // incremented. Then the resulting value of the 'counter_x' is then put as a
352 // value under key 'x' to the map:
353 //
354 // map.put(x, counter_x)
355 //
356 // It gives us a map that maps an element to a value the counter had at the
357 // time the element had been added.
358 //
359 // In order to retrieve an index of any element 'x' in the queue (at any
360 // given time) we simply need to subtract the value (the snapshot of the
361 // counter at the time when the 'x' was added) from the current value of the
362 // counter. This operation basically answers the question:
363 //
364 // How many elements ago 'x' was the tail of the queue?
365 //
366 // Which is the same as its index in the queue now. Given, of course, it's
367 // still in the queue.
368 //
369 // I'm pretty sure in a real life long overflow will never happen, so it's
370 // not too practical to add recalibrating code, but a pedantic person might
371 // want to do so:
372 //
373 // if (counter == Long.MAX_VALUE) {
374 // recalibrate();
375 // }
376 //
377 // Where 'recalibrate()' goes through the table doing this:
378 //
379 // value -= counter
380 //
381 // That's given, of course, the size of the table itself is less than
382 // Long.MAX_VALUE :-)
383 //
384 private static final class Table {
385
386 private final Map<String, Map<String, Long>> map;
387 private final CircularBuffer<HeaderField> buffer;
388 private long counter = 1;
389
390 Table(int capacity) {
391 buffer = new CircularBuffer<>(capacity);
392 map = new HashMap<>(capacity);
393 }
394
395 void add(HeaderField f) {
396 buffer.add(f);
397 Map<String, Long> values = map.computeIfAbsent(f.name, k -> new HashMap<>());
398 values.put(f.value, counter++);
399 }
400
401 HeaderField get(int index) {
402 return buffer.get(index - 1);
403 }
404
405 int indexOf(String name, String value) {
406 Map<String, Long> values = map.get(name);
407 if (values == null) {
408 return 0;
409 }
410 Long index = values.get(value);
411 if (index != null) {
412 return (int) (counter - index);
413 } else {
414 assert !values.isEmpty();
415 Long any = values.values().iterator().next(); // Iterator allocation
416 return -(int) (counter - any);
417 }
418 }
419
420 HeaderField remove() {
421 HeaderField f = buffer.remove();
422 Map<String, Long> values = map.get(f.name);
423 Long index = values.remove(f.value);
424 assert index != null;
425 if (values.isEmpty()) {
426 map.remove(f.name);
427 }
428 return f;
429 }
430
431 int size() {
432 return buffer.size;
433 }
434
435 public void setCapacity(int capacity) {
436 buffer.resize(capacity);
437 }
438 }
439
440 // head
441 // v
442 // [ ][ ][A][B][C][D][ ][ ][ ]
443 // ^
444 // tail
445 //
446 // |<- size ->| (4)
447 // |<------ capacity ------->| (9)
448 //
449 static final class CircularBuffer<E> {
450
451 int tail, head, size, capacity;
452 Object[] elements;
453
454 CircularBuffer(int capacity) {
455 this.capacity = capacity;
456 elements = new Object[capacity];
457 }
458
459 void add(E elem) {
460 if (size == capacity) {
461 throw new IllegalStateException(
462 format("No room for '%s': capacity=%s", elem, capacity));
463 }
464 elements[head] = elem;
465 head = (head + 1) % capacity;
466 size++;
467 }
468
469 @SuppressWarnings("unchecked")
470 E remove() {
471 if (size == 0) {
472 throw new NoSuchElementException("Empty");
473 }
474 E elem = (E) elements[tail];
475 elements[tail] = null;
476 tail = (tail + 1) % capacity;
477 size--;
478 return elem;
479 }
480
481 @SuppressWarnings("unchecked")
482 E get(int index) {
483 if (index < 0 || index >= size) {
484 throw new IndexOutOfBoundsException(
485 format("0 <= index <= capacity: index=%s, capacity=%s",
486 index, capacity));
487 }
488 int idx = (tail + (size - index - 1)) % capacity;
489 return (E) elements[idx];
490 }
491
492 public void resize(int newCapacity) {
493 if (newCapacity < size) {
494 throw new IllegalStateException(
495 format("newCapacity >= size: newCapacity=%s, size=%s",
496 newCapacity, size));
497 }
498
499 Object[] newElements = new Object[newCapacity];
500
501 if (tail < head || size == 0) {
502 System.arraycopy(elements, tail, newElements, 0, size);
503 } else {
504 System.arraycopy(elements, tail, newElements, 0, elements.length - tail);
505 System.arraycopy(elements, 0, newElements, elements.length - tail, head);
506 }
507
508 elements = newElements;
509 tail = 0;
510 head = size;
511 this.capacity = newCapacity;
512 }
513 }
514 }