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.incubator.http.internal.hpack.HPACK.Logger;
28 import jdk.internal.vm.annotation.Stable;
29
30 import java.util.HashMap;
31 import java.util.LinkedHashMap;
32 import java.util.Map;
33 import java.util.NoSuchElementException;
34
35 import static java.lang.String.format;
36 import static jdk.incubator.http.internal.hpack.HPACK.Logger.Level.EXTRA;
37 import static jdk.incubator.http.internal.hpack.HPACK.Logger.Level.NORMAL;
38
39 //
40 // Header Table combined from two tables: static and dynamic.
41 //
42 // There is a single address space for index values. Index-aware methods
43 // correspond to the table as a whole. Size-aware methods only to the dynamic
44 // part of it.
45 //
46 final class HeaderTable {
47
48 @Stable
49 private static final HeaderField[] staticTable = {
50 null, // To make index 1-based, instead of 0-based
51 new HeaderField(":authority"),
52 new HeaderField(":method", "GET"),
53 new HeaderField(":method", "POST"),
54 new HeaderField(":path", "/"),
55 new HeaderField(":path", "/index.html"),
56 new HeaderField(":scheme", "http"),
57 new HeaderField(":scheme", "https"),
58 new HeaderField(":status", "200"),
59 new HeaderField(":status", "204"),
60 new HeaderField(":status", "206"),
61 new HeaderField(":status", "304"),
62 new HeaderField(":status", "400"),
63 new HeaderField(":status", "404"),
64 new HeaderField(":status", "500"),
65 new HeaderField("accept-charset"),
66 new HeaderField("accept-encoding", "gzip, deflate"),
67 new HeaderField("accept-language"),
68 new HeaderField("accept-ranges"),
69 new HeaderField("accept"),
70 new HeaderField("access-control-allow-origin"),
71 new HeaderField("age"),
72 new HeaderField("allow"),
73 new HeaderField("authorization"),
74 new HeaderField("cache-control"),
75 new HeaderField("content-disposition"),
76 new HeaderField("content-encoding"),
77 new HeaderField("content-language"),
78 new HeaderField("content-length"),
79 new HeaderField("content-location"),
80 new HeaderField("content-range"),
81 new HeaderField("content-type"),
82 new HeaderField("cookie"),
83 new HeaderField("date"),
84 new HeaderField("etag"),
85 new HeaderField("expect"),
86 new HeaderField("expires"),
87 new HeaderField("from"),
88 new HeaderField("host"),
89 new HeaderField("if-match"),
90 new HeaderField("if-modified-since"),
91 new HeaderField("if-none-match"),
92 new HeaderField("if-range"),
93 new HeaderField("if-unmodified-since"),
94 new HeaderField("last-modified"),
95 new HeaderField("link"),
96 new HeaderField("location"),
97 new HeaderField("max-forwards"),
98 new HeaderField("proxy-authenticate"),
99 new HeaderField("proxy-authorization"),
100 new HeaderField("range"),
101 new HeaderField("referer"),
102 new HeaderField("refresh"),
103 new HeaderField("retry-after"),
104 new HeaderField("server"),
105 new HeaderField("set-cookie"),
106 new HeaderField("strict-transport-security"),
107 new HeaderField("transfer-encoding"),
108 new HeaderField("user-agent"),
109 new HeaderField("vary"),
110 new HeaderField("via"),
111 new HeaderField("www-authenticate")
112 };
113
114 private static final int STATIC_TABLE_LENGTH = staticTable.length - 1;
115 private static final int ENTRY_SIZE = 32;
116 private static final Map<String, LinkedHashMap<String, Integer>> staticIndexes;
117
118 static {
119 staticIndexes = new HashMap<>(STATIC_TABLE_LENGTH); // TODO: Map.of
120 for (int i = 1; i <= STATIC_TABLE_LENGTH; i++) {
121 HeaderField f = staticTable[i];
122 Map<String, Integer> values = staticIndexes
123 .computeIfAbsent(f.name, k -> new LinkedHashMap<>());
124 values.put(f.value, i);
125 }
126 }
127
128 private final Logger logger;
129 private final Table dynamicTable = new Table(0);
130 private int maxSize;
131 private int size;
132
133 public HeaderTable(int maxSize, Logger logger) {
134 this.logger = logger;
135 setMaxSize(maxSize);
136 }
137
138 //
139 // The method returns:
140 //
141 // * a positive integer i where i (i = [1..Integer.MAX_VALUE]) is an
142 // index of an entry with a header (n, v), where n.equals(name) &&
143 // v.equals(value)
144 //
145 // * a negative integer j where j (j = [-Integer.MAX_VALUE..-1]) is an
146 // index of an entry with a header (n, v), where n.equals(name)
147 //
148 // * 0 if there's no entry e such that e.getName().equals(name)
149 //
150 // The rationale behind this design is to allow to pack more useful data
151 // into a single invocation, facilitating a single pass where possible
152 // (the idea is the same as in java.util.Arrays.binarySearch(int[], int)).
153 //
154 public int indexOf(CharSequence name, CharSequence value) {
155 // Invoking toString() will possibly allocate Strings for the sake of
156 // the search, which doesn't feel right.
157 String n = name.toString();
158 String v = value.toString();
159
160 // 1. Try exact match in the static region
161 Map<String, Integer> values = staticIndexes.get(n);
162 if (values != null) {
163 Integer idx = values.get(v);
164 if (idx != null) {
165 return idx;
166 }
167 }
168 // 2. Try exact match in the dynamic region
169 int didx = dynamicTable.indexOf(n, v);
170 if (didx > 0) {
171 return STATIC_TABLE_LENGTH + didx;
172 } else if (didx < 0) {
173 if (values != null) {
174 // 3. Return name match from the static region
175 return -values.values().iterator().next(); // Iterator allocation
176 } else {
177 // 4. Return name match from the dynamic region
178 return -STATIC_TABLE_LENGTH + didx;
179 }
180 } else {
181 if (values != null) {
182 // 3. Return name match from the static region
183 return -values.values().iterator().next(); // Iterator allocation
184 } else {
185 return 0;
186 }
187 }
188 }
189
190 public int size() {
191 return size;
192 }
193
194 public int maxSize() {
195 return maxSize;
196 }
197
198 public int length() {
199 return STATIC_TABLE_LENGTH + dynamicTable.size();
200 }
201
202 HeaderField get(int index) {
203 checkIndex(index);
204 if (index <= STATIC_TABLE_LENGTH) {
205 return staticTable[index];
206 } else {
207 return dynamicTable.get(index - STATIC_TABLE_LENGTH);
208 }
209 }
210
211 void put(CharSequence name, CharSequence value) {
212 // Invoking toString() will possibly allocate Strings. But that's
213 // unavoidable at this stage. If a CharSequence is going to be stored in
214 // the table, it must not be mutable (e.g. for the sake of hashing).
215 put(new HeaderField(name.toString(), value.toString()));
216 }
217
218 private void put(HeaderField h) {
219 if (logger.isLoggable(NORMAL)) {
220 logger.log(NORMAL, () -> format("adding ('%s', '%s')",
221 h.name, h.value));
222 }
223 int entrySize = sizeOf(h);
224 if (logger.isLoggable(EXTRA)) {
225 logger.log(EXTRA, () -> format("size of ('%s', '%s') is %s",
226 h.name, h.value, entrySize));
227 }
228 while (entrySize > maxSize - size && size != 0) {
229 if (logger.isLoggable(EXTRA)) {
230 logger.log(EXTRA, () -> format("insufficient space %s, must evict entry",
231 (maxSize - size)));
232 }
233 evictEntry();
234 }
235 if (entrySize > maxSize - size) {
236 if (logger.isLoggable(EXTRA)) {
237 logger.log(EXTRA, () -> format("not adding ('%s, '%s'), too big",
238 h.name, h.value));
239 }
240 return;
241 }
242 size += entrySize;
243 dynamicTable.add(h);
244 if (logger.isLoggable(EXTRA)) {
245 logger.log(EXTRA, () -> format("('%s, '%s') added", h.name, h.value));
246 logger.log(EXTRA, this::toString);
247 }
248 }
249
250 void setMaxSize(int maxSize) {
251 if (maxSize < 0) {
252 throw new IllegalArgumentException(
253 "maxSize >= 0: maxSize=" + maxSize);
254 }
255 while (maxSize < size && size != 0) {
256 evictEntry();
257 }
258 this.maxSize = maxSize;
259 int upperBound = (maxSize / ENTRY_SIZE) + 1;
260 this.dynamicTable.setCapacity(upperBound);
261 }
262
263 HeaderField evictEntry() {
264 HeaderField f = dynamicTable.remove();
265 int s = sizeOf(f);
266 this.size -= s;
267 if (logger.isLoggable(EXTRA)) {
268 logger.log(EXTRA, () -> format("evicted entry ('%s', '%s') of size %s",
269 f.name, f.value, s));
270 logger.log(EXTRA, this::toString);
271 }
272 return f;
273 }
274
275 @Override
276 public String toString() {
277 double used = maxSize == 0 ? 0 : 100 * (((double) size) / maxSize);
278 return format("dynamic length: %d, full length: %s, used space: %s/%s (%.1f%%)",
279 dynamicTable.size(), length(), size, maxSize, used);
280 }
281
282 private int checkIndex(int index) {
283 int len = length();
284 if (index < 1 || index > len) {
285 throw new IndexOutOfBoundsException(
286 format("1 <= index <= length(): index=%s, length()=%s",
287 index, len));
288 }
289 return index;
290 }
291
292 int sizeOf(HeaderField f) {
293 return f.name.length() + f.value.length() + ENTRY_SIZE;
294 }
295
296 //
297 // Diagnostic information in the form used in the RFC 7541
298 //
299 String getStateString() {
300 if (size == 0) {
301 return "empty.";
302 }
303
304 StringBuilder b = new StringBuilder();
305 for (int i = 1, size = dynamicTable.size(); i <= size; i++) {
306 HeaderField e = dynamicTable.get(i);
307 b.append(format("[%3d] (s = %3d) %s: %s\n", i,
308 sizeOf(e), e.name, e.value));
309 }
310 b.append(format(" Table size:%4s", this.size));
311 return b.toString();
312 }
313
314 // Convert to a Value Object (JDK-8046159)?
315 static final class HeaderField {
316
317 final String name;
318 final String value;
319
320 public HeaderField(String name) {
321 this(name, "");
322 }
323
324 public HeaderField(String name, String value) {
325 this.name = name;
326 this.value = value;
327 }
328
329 @Override
330 public String toString() {
331 return value.isEmpty() ? name : name + ": " + value;
332 }
333
334 @Override
335 public boolean equals(Object o) {
336 if (this == o) {
337 return true;
338 }
339 if (o == null || getClass() != o.getClass()) {
340 return false;
341 }
342 HeaderField that = (HeaderField) o;
343 return name.equals(that.name) && value.equals(that.value);
344 }
345
346 @Override
347 public int hashCode() {
348 return 31 * name.hashCode() + value.hashCode();
349 }
350 }
351
352 //
353 // To quickly find an index of an entry in the dynamic table with the given
354 // contents an effective inverse mapping is needed. Here's a simple idea
355 // behind such a mapping.
356 //
357 // # The problem:
358 //
359 // We have a queue with an O(1) lookup by index:
360 //
361 // get: index -> x
362 //
363 // What we want is an O(1) reverse lookup:
364 //
365 // indexOf: x -> index
366 //
367 // # Solution:
368 //
369 // Let's store an inverse mapping in a Map<x, Integer>. This have a problem
370 // that when a new element is added to the queue, all indexes in the map
371 // become invalid. Namely, the new element is assigned with an index of 1,
372 // and each index i, i > 1 becomes shifted by 1 to the left:
373 //
374 // 1, 1, 2, 3, ... , n-1, n
375 //
376 // Re-establishing the invariant would seem to require a pass through the
377 // map incrementing all indexes (map values) by 1, which is O(n).
378 //
379 // The good news is we can do much better then this!
380 //
381 // Let's create a single field of type long, called 'counter'. Then each
382 // time a new element 'x' is added to the queue, a value of this field gets
383 // incremented. Then the resulting value of the 'counter_x' is then put as a
384 // value under key 'x' to the map:
385 //
386 // map.put(x, counter_x)
387 //
388 // It gives us a map that maps an element to a value the counter had at the
389 // time the element had been added.
390 //
391 // In order to retrieve an index of any element 'x' in the queue (at any
392 // given time) we simply need to subtract the value (the snapshot of the
393 // counter at the time when the 'x' was added) from the current value of the
394 // counter. This operation basically answers the question:
395 //
396 // How many elements ago 'x' was the tail of the queue?
397 //
398 // Which is the same as its index in the queue now. Given, of course, it's
399 // still in the queue.
400 //
401 // I'm pretty sure in a real life long overflow will never happen, so it's
402 // not too practical to add recalibrating code, but a pedantic person might
403 // want to do so:
404 //
405 // if (counter == Long.MAX_VALUE) {
406 // recalibrate();
407 // }
408 //
409 // Where 'recalibrate()' goes through the table doing this:
410 //
411 // value -= counter
412 //
413 // That's given, of course, the size of the table itself is less than
414 // Long.MAX_VALUE :-)
415 //
416 private static final class Table {
417
418 private final Map<String, Map<String, Long>> map;
419 private final CircularBuffer<HeaderField> buffer;
420 private long counter = 1;
421
422 Table(int capacity) {
423 buffer = new CircularBuffer<>(capacity);
424 map = new HashMap<>(capacity);
425 }
426
427 void add(HeaderField f) {
428 buffer.add(f);
429 Map<String, Long> values = map.computeIfAbsent(f.name, k -> new HashMap<>());
430 values.put(f.value, counter++);
431 }
432
433 HeaderField get(int index) {
434 return buffer.get(index - 1);
435 }
436
437 int indexOf(String name, String value) {
438 Map<String, Long> values = map.get(name);
439 if (values == null) {
440 return 0;
441 }
442 Long index = values.get(value);
443 if (index != null) {
444 return (int) (counter - index);
445 } else {
446 assert !values.isEmpty();
447 Long any = values.values().iterator().next(); // Iterator allocation
448 return -(int) (counter - any);
449 }
450 }
451
452 HeaderField remove() {
453 HeaderField f = buffer.remove();
454 Map<String, Long> values = map.get(f.name);
455 Long index = values.remove(f.value);
456 assert index != null;
457 if (values.isEmpty()) {
458 map.remove(f.name);
459 }
460 return f;
461 }
462
463 int size() {
464 return buffer.size;
465 }
466
467 public void setCapacity(int capacity) {
468 buffer.resize(capacity);
469 }
470 }
471
472 // head
473 // v
474 // [ ][ ][A][B][C][D][ ][ ][ ]
475 // ^
476 // tail
477 //
478 // |<- size ->| (4)
479 // |<------ capacity ------->| (9)
480 //
481 static final class CircularBuffer<E> {
482
483 int tail, head, size, capacity;
484 Object[] elements;
485
486 CircularBuffer(int capacity) {
487 this.capacity = capacity;
488 elements = new Object[capacity];
489 }
490
491 void add(E elem) {
492 if (size == capacity) {
493 throw new IllegalStateException(
494 format("No room for '%s': capacity=%s", elem, capacity));
495 }
496 elements[head] = elem;
497 head = (head + 1) % capacity;
498 size++;
499 }
500
501 @SuppressWarnings("unchecked")
502 E remove() {
503 if (size == 0) {
504 throw new NoSuchElementException("Empty");
505 }
506 E elem = (E) elements[tail];
507 elements[tail] = null;
508 tail = (tail + 1) % capacity;
509 size--;
510 return elem;
511 }
512
513 @SuppressWarnings("unchecked")
514 E get(int index) {
515 if (index < 0 || index >= size) {
516 throw new IndexOutOfBoundsException(
517 format("0 <= index <= capacity: index=%s, capacity=%s",
518 index, capacity));
519 }
520 int idx = (tail + (size - index - 1)) % capacity;
521 return (E) elements[idx];
522 }
523
524 public void resize(int newCapacity) {
525 if (newCapacity < size) {
526 throw new IllegalStateException(
527 format("newCapacity >= size: newCapacity=%s, size=%s",
528 newCapacity, size));
529 }
530
531 Object[] newElements = new Object[newCapacity];
532
533 if (tail < head || size == 0) {
534 System.arraycopy(elements, tail, newElements, 0, size);
535 } else {
536 System.arraycopy(elements, tail, newElements, 0, elements.length - tail);
537 System.arraycopy(elements, 0, newElements, elements.length - tail, head);
538 }
539
540 elements = newElements;
541 tail = 0;
542 head = size;
543 this.capacity = newCapacity;
544 }
545 }
546 }