1 /*
2 * Copyright (c) 2002, 2011, 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
26 package sun.security.util;
27
28 import java.util.*;
29 import java.lang.ref.*;
30 import java.util.concurrent.ConcurrentHashMap;
31 import java.util.concurrent.ConcurrentMap;
32 import java.util.concurrent.TimeUnit;
33 import java.util.function.Predicate;
34
35 /**
36 * Abstract base class and factory for caches. A cache is a key-value mapping.
37 * It has properties that make it more suitable for caching than a Map.
38 *
39 * The factory methods can be used to obtain two different implementations.
40 * They have the following properties:
41 *
42 * . keys and values reside in memory
43 *
44 * . keys and values must be non-null
45 *
46 * . maximum size. Replacements are made in LRU order.
47 *
48 * . optional lifetime, specified in seconds.
49 *
50 * . safe for concurrent use by multiple threads
51 *
52 * . values are held by either standard references or via SoftReferences.
53 * SoftReferences have the advantage that they are automatically cleared
54 * by the garbage collector in response to memory demand. This makes it
55 * possible to simple set the maximum size to a very large value and let
56 * the GC automatically size the cache dynamically depending on the
57 * amount of available memory.
58 *
59 * However, note that because of the way SoftReferences are implemented in
60 * HotSpot at the moment, this may not work perfectly as it clears them fairly
61 * eagerly. Performance may be improved if the Java heap size is set to larger
62 * value using e.g. java -ms64M -mx128M foo.Test
63 *
64 * Cache sizing: the memory cache is implemented on top of a LinkedHashMap.
65 * In its current implementation, the number of buckets (NOT entries) in
66 * (Linked)HashMaps is always a power of two. It is recommended to set the
67 * maximum cache size to value that uses those buckets fully. For example,
68 * if a cache with somewhere between 500 and 1000 entries is desired, a
69 * maximum size of 750 would be a good choice: try 1024 buckets, with a
70 * load factor of 0.75f, the number of entries can be calculated as
71 * buckets / 4 * 3. As mentioned above, with a SoftReference cache, it is
72 * generally reasonable to set the size to a fairly large value.
73 *
74 * @author Andreas Sterbenz
75 */
76 public abstract class Cache<K,V> {
77
78 protected Cache() {
79 // empty
80 }
81
82 /**
83 * Return the number of currently valid entries in the cache.
84 */
85 public abstract int size();
86
87 /**
88 * Remove all entries from the cache.
89 */
90 public abstract void clear();
91
92 /**
93 * Add an entry to the cache.
94 */
95 public abstract void put(K key, V value);
96
97 /**
98 * Get a value from the cache.
99 */
100 public abstract V get(Object key);
101
102 /**
103 * Remove an entry from the cache.
104 */
105 public abstract void remove(Object key);
106
107 /**
108 * Set the maximum size.
109 */
110 public abstract void setCapacity(int size);
111
112 /**
113 * Set the timeout(in seconds).
114 */
115 public abstract void setTimeout(int timeout);
116
117 /**
118 * accept a visitor
119 */
120 public abstract void accept(CacheVisitor<K,V> visitor);
121
122 /**
123 * Return a new memory cache with the specified maximum size, unlimited
124 * lifetime for entries, with the values held by SoftReferences.
125 */
126 public static <K,V> Cache<K,V> newSoftMemoryCache(int size) {
127 return new MemoryCache<>(true, size);
128 }
129
130 /**
131 * Return a new memory cache with the specified maximum size, the
132 * specified maximum lifetime (in seconds), with the values held
133 * by SoftReferences.
134 */
135 public static <K,V> Cache<K,V> newSoftMemoryCache(int size, int timeout) {
136 return new MemoryCache<>(true, size, timeout);
137 }
138
139 /**
140 * Return a new memory cache with the specified maximum size, unlimited
141 * lifetime for entries, with the values held by standard references.
142 */
143 public static <K,V> Cache<K,V> newHardMemoryCache(int size) {
144 return new MemoryCache<>(false, size);
145 }
146
147 /**
148 * Return a dummy cache that does nothing.
149 */
150 @SuppressWarnings("unchecked")
151 public static <K,V> Cache<K,V> newNullCache() {
152 return (Cache<K,V>) NullCache.INSTANCE;
153 }
154
155 /**
156 * Return a new memory cache with the specified maximum size, the
157 * specified maximum lifetime (in seconds), with the values held
158 * by standard references.
159 */
160 public static <K,V> Cache<K,V> newHardMemoryCache(int size, int timeout) {
161 return new MemoryCache<>(false, size, timeout);
162 }
163
164 /**
165 * Utility class that wraps a byte array and implements the equals()
166 * and hashCode() contract in a way suitable for Maps and caches.
167 */
168 public static class EqualByteArray {
169
170 private final byte[] b;
171 private int hash;
172
173 public EqualByteArray(byte[] b) {
174 this.b = b;
175 }
176
177 public int hashCode() {
178 int h = hash;
179 if (h == 0 && b.length > 0) {
180 hash = h = Arrays.hashCode(b);
181 }
182 return h;
183 }
184
185 public boolean equals(Object obj) {
186 if (this == obj) {
187 return true;
188 }
189 if (obj instanceof EqualByteArray == false) {
190 return false;
191 }
192 EqualByteArray other = (EqualByteArray)obj;
193 return Arrays.equals(this.b, other.b);
194 }
195 }
196
197 public interface CacheVisitor<K,V> {
198 public void visit(Map<K,V> map);
199 }
200
201 }
202
203 class NullCache<K,V> extends Cache<K,V> {
204
205 static final Cache<Object,Object> INSTANCE = new NullCache<>();
206
207 private NullCache() {
208 // empty
209 }
210
211 public int size() {
212 return 0;
213 }
214
215 public void clear() {
216 // empty
217 }
218
219 public void put(K key, V value) {
220 // empty
221 }
222
223 public V get(Object key) {
224 return null;
225 }
226
227 public void remove(Object key) {
228 // empty
229 }
230
231 public void setCapacity(int size) {
232 // empty
233 }
234
235 public void setTimeout(int timeout) {
236 // empty
237 }
238
239 public void accept(CacheVisitor<K,V> visitor) {
240 // empty
241 }
242
243 }
244
245 class MemoryCache<K,V> extends Cache<K,V> {
246
247 // XXXX
248 private static final boolean DEBUG = false;
249
250 private final ConcurrentMap<K, CacheEntry<K,V>> cacheMap;
251 private CacheEntry<K, V> lruEntry, mruEntry;
252 private volatile int maxSize;
253 private volatile long lifetime;
254
255 // ReferenceQueue is of type V instead of Cache<K,V>
256 // to allow SoftCacheEntry to extend SoftReference<V>
257 private final ReferenceQueue<V> queue;
258
259 public MemoryCache(boolean soft, int maxSize) {
260 this(soft, maxSize, 0 /* no time out */);
261 }
262
263 public MemoryCache(boolean soft, int maxSize, int timeout) {
264 this.maxSize = maxSize;
265 this.lifetime = timeout < 0 ? 0 : TimeUnit.SECONDS.toNanos(timeout);
266 if (soft)
267 this.queue = new ReferenceQueue<>();
268 else
269 this.queue = null;
270
271 cacheMap = new ConcurrentHashMap<>(maxSize);
272 }
273
274 /**
275 * Drain the reference queue and remove all corresponding entries
276 * from the cache.
277 *
278 * This method should be called at the beginning of each public
279 * method.
280 */
281 private void drainQueue() {
282 if (queue == null) {
283 return;
284 }
285 int removedCount = 0;
286 while (true) {
287 @SuppressWarnings("unchecked")
288 CacheEntry<K,V> ce = (CacheEntry<K,V>)queue.poll();
289 if (ce == null) {
290 break;
291 }
292 if (ce.unlink(this)) {
293 if (cacheMap.remove(ce.getKey(), ce)) {
294 removedCount++;
295 }
296 // the one who unlinks is responsible for invalidating
297 ce.invalidate();
298 }
299 }
300 if (DEBUG) {
301 if (removedCount > 0) {
302 System.out.println("*** Expunged " + removedCount
303 + " entries, " + cacheMap.size() + " entries left");
304 }
305 }
306 }
307
308 /**
309 * Drain the reference queue and remove all corresponding entries
310 * from the cache. Then expunge all expired entries.
311 *
312 * This method should be called just before doing any decisions based
313 * on the number of entries remaining in cache (i.e. cacheMap.size()).
314 */
315 private void drainQueueExpungeExpired() {
316 drainQueue();
317 int cnt = 0;
318 long currentTime = System.nanoTime();
319 long lifetime = this.lifetime;
320 if (lifetime == 0) {
321 return;
322 }
323 Predicate<CacheEntry<K, V>> entryIsInvalid =
324 ce -> !ce.isValid(currentTime, lifetime);
325 CacheEntry<K,V> lru;
326 while ((lru = CacheEntry.unlinkLruIf(this, entryIsInvalid)) != null) {
327 if (cacheMap.remove(lru.getKey(), lru)) {
328 cnt++;
329 }
330 // the one who unlinks is responsible for invalidating
331 lru.invalidate();
332 }
333 if (DEBUG) {
334 if (cnt != 0) {
335 System.out.println("Removed " + cnt
336 + " expired entries, remaining " + cacheMap.size());
337 }
338 }
339 }
340
341 /**
342 * Remove LRU entries while cache size is greater than given {@code maxSize}.
343 *
344 * @param maxSize pack cache to size no more than
345 */
346 private void reduceToMaxSize(int maxSize) {
347 if (maxSize > 0 && cacheMap.size() > maxSize) {
348 // 1st get rid of all cleared and expired entries
349 drainQueueExpungeExpired();
350 while (cacheMap.size() > maxSize) { // while still too large
351 CacheEntry<K, V> lru = CacheEntry.unlinkLruIf(this, ce -> true);
352 if (lru != null) {
353 if (DEBUG) {
354 System.out.println("** Overflow removal "
355 + lru.getKey() + " | " + lru.getValue());
356 }
357 cacheMap.remove(lru.getKey(), lru);
358 // the one who unlinks is responsible for invalidating
359 lru.invalidate();
360 }
361 }
362 }
363 }
364
365 public int size() {
366 drainQueueExpungeExpired();
367 return cacheMap.size();
368 }
369
370 public void clear() {
371 CacheEntry<K, V> lru;
372 while ((lru = CacheEntry.unlinkLruIf(this, ce -> true)) != null) {
373 cacheMap.remove(lru.getKey(), lru);
374 // the one who unlinks is responsible for invalidating
375 lru.invalidate();
376 }
377 }
378
379 public void put(K key, V value) {
380 drainQueue();
381 CacheEntry<K,V> newEntry = newEntry(key, value, queue);
382 newEntry.link(this);
383 CacheEntry<K,V> oldEntry = cacheMap.put(key, newEntry);
384 if (oldEntry != null && oldEntry.unlink(this)) {
385 // the one who unlinks is responsible for invalidating
386 oldEntry.invalidate();
387 return;
388 }
389 reduceToMaxSize(maxSize);
390 }
391
392 public V get(Object key) {
393 drainQueue();
394 CacheEntry<K,V> entry = cacheMap.get(key);
395 if (entry == null) {
396 return null;
397 }
398 // harmless data race: entry.isValid() vs. entry.invalidate()
399 if (!entry.isValid(System.nanoTime(), lifetime)) {
400 if (DEBUG) {
401 System.out.println("Ignoring expired entry");
402 }
403 if (entry.unlink(this)) {
404 cacheMap.remove(entry.getKey(), entry);
405 // the one who unlinks is responsible for invalidating
406 entry.invalidate();
407 }
408 return null;
409 }
410 return entry.getValue(); // harmless data race with entry.invalidate()
411 }
412
413 public void remove(Object key) {
414 drainQueue();
415 CacheEntry<K,V> entry = cacheMap.get(key);
416 if (entry != null) {
417 if (entry.unlink(this)) {
418 cacheMap.remove(entry.getKey(), entry);
419 // the one who unlinks is responsible for invalidating
420 entry.invalidate();
421 }
422 }
423 }
424
425 public void setCapacity(int size) {
426 if (size < 0) size = 0;
427 maxSize = size;
428 // in case maxSize was reduces, immediately reduce the cache too
429 reduceToMaxSize(size);
430
431 if (DEBUG) {
432 System.out.println("** capacity reset to " + size);
433 }
434 }
435
436 public void setTimeout(int timeout) {
437 this.lifetime = timeout < 0 ? 0 : TimeUnit.SECONDS.toNanos(timeout);
438 // in case timeout was shortened, immediately expunge newly expired entries
439 drainQueueExpungeExpired();
440 if (DEBUG) {
441 System.out.println("** lifetime reset to " + lifetime + " nanos");
442 }
443 }
444
445 // it is a heavyweight method.
446 public void accept(CacheVisitor<K,V> visitor) {
447 Map<K,V> cached = getCachedEntries();
448 visitor.visit(cached);
449 }
450
451 // return a snapshot of the valid/non-expired part of the cache
452 private Map<K,V> getCachedEntries() {
453 drainQueueExpungeExpired();
454 Map<K,V> kvmap = new HashMap<>(cacheMap.size());
455
456 for (CacheEntry<K,V> entry : cacheMap.values()) {
457 K key = entry.getKey(); // harmless data race with entry.invalidate()
458 V val = entry.getValue(); // harmless data race with entry.invalidate()
459 if (key != null && val != null) {
460 kvmap.put(key, val);
461 }
462 }
463
464 return kvmap;
465 }
466
467 protected CacheEntry<K,V> newEntry(K key, V value, ReferenceQueue<V> queue) {
468 if (queue != null) {
469 return new SoftCacheEntry<>(key, value, queue);
470 } else {
471 return new HardCacheEntry<>(key, value);
472 }
473 }
474
475 private interface CacheEntry<K, V> {
476
477 boolean isValid(long currentTime, long lifetime);
478
479 void invalidate();
480
481 K getKey();
482
483 V getValue();
484
485 // double-linked-list management
486
487 CacheEntry<K,V> prev();
488
489 CacheEntry<K,V> next();
490
491 void setPrev(CacheEntry<K,V> newPrev);
492
493 void setNext(CacheEntry<K,V> newNext);
494
495 void entryLinked();
496
497 default void link(MemoryCache<K, V> memoryCache) {
498 synchronized (memoryCache) {
499 assert prev() == this && next() == this : "Entry already linked";
500 if (memoryCache.lruEntry == null) {
501 memoryCache.lruEntry = memoryCache.mruEntry = this;
502 setPrev(null); setNext(null);
503 } else {
504 setPrev(memoryCache.mruEntry);
505 memoryCache.mruEntry.setNext(this);
506 memoryCache.mruEntry = this;
507 setNext(null);
508 }
509 entryLinked();
510 }
511 }
512
513 default boolean unlink(MemoryCache<K, V> memoryCache) {
514 synchronized (memoryCache) {
515 CacheEntry<K, V> next = next();
516 CacheEntry<K, V> prev = prev();
517 if (next == this && prev == this) {
518 // not linked
519 return false;
520 }
521 if (memoryCache.lruEntry == this) {
522 memoryCache.lruEntry = next;
523 }
524 if (memoryCache.mruEntry == this) {
525 memoryCache.mruEntry = prev;
526 }
527 if (prev != null) {
528 prev.setNext(next);
529 }
530 if (next != null) {
531 next.setPrev(prev);
532 }
533 setPrev(this);
534 setNext(this);
535 return true;
536 }
537 }
538
539 static <K, V> CacheEntry<K, V> unlinkLruIf(MemoryCache<K, V> memoryCache, Predicate<CacheEntry<K, V>> predicate) {
540 synchronized (memoryCache) {
541 CacheEntry<K, V> lru = memoryCache.lruEntry;
542 if (lru == null || !predicate.test(lru)) {
543 return null;
544 }
545 return lru.unlink(memoryCache) ? lru : null;
546 }
547 }
548 }
549
550 private static class HardCacheEntry<K,V> implements CacheEntry<K,V> {
551
552 private K key;
553 private V value;
554 private long linkTime;
555 private CacheEntry<K, V> prev = this, next = this;
556
557 HardCacheEntry(K key, V value) {
558 this.key = key;
559 this.value = value;
560 }
561
562 public K getKey() {
563 return key;
564 }
565
566 public V getValue() {
567 return value;
568 }
569
570 public boolean isValid(long currentTime, long lifetime) {
571 return value != null &&
572 (lifetime == 0 || (currentTime - linkTime) <= lifetime);
573 }
574
575 public void invalidate() {
576 key = null;
577 value = null;
578 }
579
580 @Override
581 public CacheEntry<K, V> prev() {
582 return prev;
583 }
584
585 @Override
586 public CacheEntry<K, V> next() {
587 return next;
588 }
589
590 @Override
591 public void setPrev(CacheEntry<K, V> newPrev) {
592 prev = newPrev;
593 }
594
595 @Override
596 public void setNext(CacheEntry<K, V> newNext) {
597 next = newNext;
598 }
599
600 @Override
601 public void entryLinked() {
602 // sample link time while synchronized which guarantees
603 // monotonic time increment (no decrement), so dl-list
604 // is kept sorted by linkTime
605 linkTime = System.nanoTime();
606 }
607 }
608
609 private static class SoftCacheEntry<K,V>
610 extends SoftReference<V>
611 implements CacheEntry<K,V> {
612
613 private K key;
614 private long linkTime;
615 private CacheEntry<K, V> prev = this, next = this;
616
617 SoftCacheEntry(K key, V value, ReferenceQueue<V> queue) {
618 super(value, queue);
619 this.key = key;
620 }
621
622 public K getKey() {
623 return key;
624 }
625
626 public V getValue() {
627 return get();
628 }
629
630 public boolean isValid(long currentTime, long lifetime) {
631 return get() != null &&
632 (lifetime == 0 || (currentTime - linkTime) <= lifetime);
633 }
634
635 public void invalidate() {
636 key = null;
637 clear();
638 }
639
640 @Override
641 public CacheEntry<K, V> prev() {
642 return prev;
643 }
644
645 @Override
646 public CacheEntry<K, V> next() {
647 return next;
648 }
649
650 @Override
651 public void setPrev(CacheEntry<K, V> newPrev) {
652 prev = newPrev;
653 }
654
655 @Override
656 public void setNext(CacheEntry<K, V> newNext) {
657 next = newNext;
658 }
659
660 @Override
661 public void entryLinked() {
662 // sample link time while synchronized which guarantees
663 // monotonic time increment (no decrement), so dl-list
664 // is kept sorted by linkTime
665 linkTime = System.nanoTime();
666 }
667 }
668
669 }