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
31 /**
32 * Abstract base class and factory for caches. A cache is a key-value mapping.
33 * It has properties that make it more suitable for caching than a Map.
34 *
35 * The factory methods can be used to obtain two different implementations.
36 * They have the following properties:
37 *
38 * . keys and values reside in memory
39 *
40 * . keys and values must be non-null
41 *
42 * . maximum size. Replacements are made in LRU order.
43 *
44 * . optional lifetime, specified in seconds.
45 *
46 * . safe for concurrent use by multiple threads
47 *
48 * . values are held by either standard references or via SoftReferences.
49 * SoftReferences have the advantage that they are automatically cleared
223 public void remove(Object key) {
224 // empty
225 }
226
227 public void setCapacity(int size) {
228 // empty
229 }
230
231 public void setTimeout(int timeout) {
232 // empty
233 }
234
235 public void accept(CacheVisitor<K,V> visitor) {
236 // empty
237 }
238
239 }
240
241 class MemoryCache<K,V> extends Cache<K,V> {
242
243 private static final float LOAD_FACTOR = 0.75f;
244
245 // XXXX
246 private static final boolean DEBUG = false;
247
248 private final Map<K, CacheEntry<K,V>> cacheMap;
249 private int maxSize;
250 private long lifetime;
251
252 // ReferenceQueue is of type V instead of Cache<K,V>
253 // to allow SoftCacheEntry to extend SoftReference<V>
254 private final ReferenceQueue<V> queue;
255
256 public MemoryCache(boolean soft, int maxSize) {
257 this(soft, maxSize, 0);
258 }
259
260 public MemoryCache(boolean soft, int maxSize, int lifetime) {
261 this.maxSize = maxSize;
262 this.lifetime = lifetime * 1000;
263 if (soft)
264 this.queue = new ReferenceQueue<>();
265 else
266 this.queue = null;
267
268 int buckets = (int)(maxSize / LOAD_FACTOR) + 1;
269 cacheMap = new LinkedHashMap<>(buckets, LOAD_FACTOR, true);
270 }
271
272 /**
273 * Empty the reference queue and remove all corresponding entries
274 * from the cache.
275 *
276 * This method should be called at the beginning of each public
277 * method.
278 */
279 private void emptyQueue() {
280 if (queue == null) {
281 return;
282 }
283 int startSize = cacheMap.size();
284 while (true) {
285 @SuppressWarnings("unchecked")
286 CacheEntry<K,V> entry = (CacheEntry<K,V>)queue.poll();
287 if (entry == null) {
288 break;
289 }
290 K key = entry.getKey();
291 if (key == null) {
292 // key is null, entry has already been removed
293 continue;
294 }
295 CacheEntry<K,V> currentEntry = cacheMap.remove(key);
296 // check if the entry in the map corresponds to the expired
297 // entry. If not, readd the entry
298 if ((currentEntry != null) && (entry != currentEntry)) {
299 cacheMap.put(key, currentEntry);
300 }
301 }
302 if (DEBUG) {
303 int endSize = cacheMap.size();
304 if (startSize != endSize) {
305 System.out.println("*** Expunged " + (startSize - endSize)
306 + " entries, " + endSize + " entries left");
307 }
308 }
309 }
310
311 /**
312 * Scan all entries and remove all expired ones.
313 */
314 private void expungeExpiredEntries() {
315 emptyQueue();
316 if (lifetime == 0) {
317 return;
318 }
319 int cnt = 0;
320 long time = System.currentTimeMillis();
321 for (Iterator<CacheEntry<K,V>> t = cacheMap.values().iterator();
322 t.hasNext(); ) {
323 CacheEntry<K,V> entry = t.next();
324 if (entry.isValid(time) == false) {
325 t.remove();
326 cnt++;
327 }
328 }
329 if (DEBUG) {
330 if (cnt != 0) {
331 System.out.println("Removed " + cnt
332 + " expired entries, remaining " + cacheMap.size());
333 }
334 }
335 }
336
337 public synchronized int size() {
338 expungeExpiredEntries();
339 return cacheMap.size();
340 }
341
342 public synchronized void clear() {
343 if (queue != null) {
344 // if this is a SoftReference cache, first invalidate() all
345 // entries so that GC does not have to enqueue them
346 for (CacheEntry<K,V> entry : cacheMap.values()) {
347 entry.invalidate();
348 }
349 while (queue.poll() != null) {
350 // empty
351 }
352 }
353 cacheMap.clear();
354 }
355
356 public synchronized void put(K key, V value) {
357 emptyQueue();
358 long expirationTime = (lifetime == 0) ? 0 :
359 System.currentTimeMillis() + lifetime;
360 CacheEntry<K,V> newEntry = newEntry(key, value, expirationTime, queue);
361 CacheEntry<K,V> oldEntry = cacheMap.put(key, newEntry);
362 if (oldEntry != null) {
363 oldEntry.invalidate();
364 return;
365 }
366 if (maxSize > 0 && cacheMap.size() > maxSize) {
367 expungeExpiredEntries();
368 if (cacheMap.size() > maxSize) { // still too large?
369 Iterator<CacheEntry<K,V>> t = cacheMap.values().iterator();
370 CacheEntry<K,V> lruEntry = t.next();
371 if (DEBUG) {
372 System.out.println("** Overflow removal "
373 + lruEntry.getKey() + " | " + lruEntry.getValue());
374 }
375 t.remove();
376 lruEntry.invalidate();
377 }
378 }
379 }
380
381 public synchronized V get(Object key) {
382 emptyQueue();
383 CacheEntry<K,V> entry = cacheMap.get(key);
384 if (entry == null) {
385 return null;
386 }
387 long time = (lifetime == 0) ? 0 : System.currentTimeMillis();
388 if (entry.isValid(time) == false) {
389 if (DEBUG) {
390 System.out.println("Ignoring expired entry");
391 }
392 cacheMap.remove(key);
393 return null;
394 }
395 return entry.getValue();
396 }
397
398 public synchronized void remove(Object key) {
399 emptyQueue();
400 CacheEntry<K,V> entry = cacheMap.remove(key);
401 if (entry != null) {
402 entry.invalidate();
403 }
404 }
405
406 public synchronized void setCapacity(int size) {
407 expungeExpiredEntries();
408 if (size > 0 && cacheMap.size() > size) {
409 Iterator<CacheEntry<K,V>> t = cacheMap.values().iterator();
410 for (int i = cacheMap.size() - size; i > 0; i--) {
411 CacheEntry<K,V> lruEntry = t.next();
412 if (DEBUG) {
413 System.out.println("** capacity reset removal "
414 + lruEntry.getKey() + " | " + lruEntry.getValue());
415 }
416 t.remove();
417 lruEntry.invalidate();
418 }
419 }
420
421 maxSize = size > 0 ? size : 0;
422
423 if (DEBUG) {
424 System.out.println("** capacity reset to " + size);
425 }
426 }
427
428 public synchronized void setTimeout(int timeout) {
429 emptyQueue();
430 lifetime = timeout > 0 ? timeout * 1000L : 0L;
431
432 if (DEBUG) {
433 System.out.println("** lifetime reset to " + timeout);
434 }
435 }
436
437 // it is a heavyweight method.
438 public synchronized void accept(CacheVisitor<K,V> visitor) {
439 expungeExpiredEntries();
440 Map<K,V> cached = getCachedEntries();
441
442 visitor.visit(cached);
443 }
444
445 private Map<K,V> getCachedEntries() {
446 Map<K,V> kvmap = new HashMap<>(cacheMap.size());
447
448 for (CacheEntry<K,V> entry : cacheMap.values()) {
449 kvmap.put(entry.getKey(), entry.getValue());
450 }
451
452 return kvmap;
453 }
454
455 protected CacheEntry<K,V> newEntry(K key, V value,
456 long expirationTime, ReferenceQueue<V> queue) {
457 if (queue != null) {
458 return new SoftCacheEntry<>(key, value, expirationTime, queue);
459 } else {
460 return new HardCacheEntry<>(key, value, expirationTime);
461 }
462 }
463
464 private static interface CacheEntry<K,V> {
465
466 boolean isValid(long currentTime);
467
468 void invalidate();
469
470 K getKey();
471
472 V getValue();
473
474 }
475
476 private static class HardCacheEntry<K,V> implements CacheEntry<K,V> {
477
478 private K key;
479 private V value;
480 private long expirationTime;
481
482 HardCacheEntry(K key, V value, long expirationTime) {
483 this.key = key;
484 this.value = value;
485 this.expirationTime = expirationTime;
486 }
487
488 public K getKey() {
489 return key;
490 }
491
492 public V getValue() {
493 return value;
494 }
495
496 public boolean isValid(long currentTime) {
497 boolean valid = (currentTime <= expirationTime);
498 if (valid == false) {
499 invalidate();
500 }
501 return valid;
502 }
503
504 public void invalidate() {
505 key = null;
506 value = null;
507 expirationTime = -1;
508 }
509 }
510
511 private static class SoftCacheEntry<K,V>
512 extends SoftReference<V>
513 implements CacheEntry<K,V> {
514
515 private K key;
516 private long expirationTime;
517
518 SoftCacheEntry(K key, V value, long expirationTime,
519 ReferenceQueue<V> queue) {
520 super(value, queue);
521 this.key = key;
522 this.expirationTime = expirationTime;
523 }
524
525 public K getKey() {
526 return key;
527 }
528
529 public V getValue() {
530 return get();
531 }
532
533 public boolean isValid(long currentTime) {
534 boolean valid = (currentTime <= expirationTime) && (get() != null);
535 if (valid == false) {
536 invalidate();
537 }
538 return valid;
539 }
540
541 public void invalidate() {
542 clear();
543 key = null;
544 expirationTime = -1;
545 }
546 }
547
548 }
|
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
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 }
|