1 /*
   2  * Copyright (c) 2002, 2021, 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 
  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
  50  *    by the garbage collector in response to memory demand. This makes it
  51  *    possible to simple set the maximum size to a very large value and let
  52  *    the GC automatically size the cache dynamically depending on the
  53  *    amount of available memory.
  54  *
  55  * However, note that because of the way SoftReferences are implemented in
  56  * HotSpot at the moment, this may not work perfectly as it clears them fairly
  57  * eagerly. Performance may be improved if the Java heap size is set to larger
  58  * value using e.g. java -ms64M -mx128M foo.Test
  59  *
  60  * Cache sizing: the memory cache is implemented on top of a LinkedHashMap.
  61  * In its current implementation, the number of buckets (NOT entries) in
  62  * (Linked)HashMaps is always a power of two. It is recommended to set the
  63  * maximum cache size to value that uses those buckets fully. For example,
  64  * if a cache with somewhere between 500 and 1000 entries is desired, a
  65  * maximum size of 750 would be a good choice: try 1024 buckets, with a
  66  * load factor of 0.75f, the number of entries can be calculated as
  67  * buckets / 4 * 3. As mentioned above, with a SoftReference cache, it is
  68  * generally reasonable to set the size to a fairly large value.
  69  *
  70  * @author Andreas Sterbenz
  71  */
  72 public abstract class Cache<K,V> {
  73 
  74     protected Cache() {
  75         // empty
  76     }
  77 
  78     /**
  79      * Return the number of currently valid entries in the cache.
  80      */
  81     public abstract int size();
  82 
  83     /**
  84      * Remove all entries from the cache.
  85      */
  86     public abstract void clear();
  87 
  88     /**
  89      * Add an entry to the cache.
  90      */
  91     public abstract void put(K key, V value);
  92 
  93     /**
  94      * Get a value from the cache.
  95      */
  96     public abstract V get(Object key);
  97 
  98     /**
  99      * Remove an entry from the cache.
 100      */
 101     public abstract void remove(Object key);
 102 
 103     /**
 104      * Set the maximum size.
 105      */
 106     public abstract void setCapacity(int size);
 107 
 108     /**
 109      * Set the timeout(in seconds).
 110      */
 111     public abstract void setTimeout(int timeout);
 112 
 113     /**
 114      * accept a visitor
 115      */
 116     public abstract void accept(CacheVisitor<K,V> visitor);
 117 
 118     /**
 119      * Return a new memory cache with the specified maximum size, unlimited
 120      * lifetime for entries, with the values held by SoftReferences.
 121      */
 122     public static <K,V> Cache<K,V> newSoftMemoryCache(int size) {
 123         return new MemoryCache<>(true, size);
 124     }
 125 
 126     /**
 127      * Return a new memory cache with the specified maximum size, the
 128      * specified maximum lifetime (in seconds), with the values held
 129      * by SoftReferences.
 130      */
 131     public static <K,V> Cache<K,V> newSoftMemoryCache(int size, int timeout) {
 132         return new MemoryCache<>(true, size, timeout);
 133     }
 134 
 135     /**
 136      * Return a new memory cache with the specified maximum size, unlimited
 137      * lifetime for entries, with the values held by standard references.
 138      */
 139     public static <K,V> Cache<K,V> newHardMemoryCache(int size) {
 140         return new MemoryCache<>(false, size);
 141     }
 142 
 143     /**
 144      * Return a dummy cache that does nothing.
 145      */
 146     @SuppressWarnings("unchecked")
 147     public static <K,V> Cache<K,V> newNullCache() {
 148         return (Cache<K,V>) NullCache.INSTANCE;
 149     }
 150 
 151     /**
 152      * Return a new memory cache with the specified maximum size, the
 153      * specified maximum lifetime (in seconds), with the values held
 154      * by standard references.
 155      */
 156     public static <K,V> Cache<K,V> newHardMemoryCache(int size, int timeout) {
 157         return new MemoryCache<>(false, size, timeout);
 158     }
 159 
 160     /**
 161      * Utility class that wraps a byte array and implements the equals()
 162      * and hashCode() contract in a way suitable for Maps and caches.
 163      */
 164     public static class EqualByteArray {
 165 
 166         private final byte[] b;
 167         private volatile int hash;
 168 
 169         public EqualByteArray(byte[] b) {
 170             this.b = b;
 171         }
 172 
 173         public int hashCode() {
 174             int h = hash;
 175             if (h == 0) {
 176                 h = b.length + 1;
 177                 for (int i = 0; i < b.length; i++) {
 178                     h += (b[i] & 0xff) * 37;
 179                 }
 180                 hash = h;
 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     final static 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     private final static float LOAD_FACTOR = 0.75f;
 248 
 249     // XXXX
 250     private final static boolean DEBUG = false;
 251 
 252     private final Map<K, CacheEntry<K,V>> cacheMap;
 253     private int maxSize;
 254     private long lifetime;
 255     private long nextExpirationTime = Long.MAX_VALUE;
 256 
 257     // ReferenceQueue is of type V instead of Cache<K,V>
 258     // to allow SoftCacheEntry to extend SoftReference<V>
 259     private final ReferenceQueue<V> queue;
 260 
 261     public MemoryCache(boolean soft, int maxSize) {
 262         this(soft, maxSize, 0);
 263     }
 264 
 265     public MemoryCache(boolean soft, int maxSize, int lifetime) {
 266         this.maxSize = maxSize;
 267         this.lifetime = lifetime * 1000;
 268         if (soft)
 269             this.queue = new ReferenceQueue<>();
 270         else
 271             this.queue = null;
 272 
 273         cacheMap = new LinkedHashMap<>(1, LOAD_FACTOR, true);
 274     }
 275 
 276     /**
 277      * Empty the reference queue and remove all corresponding entries
 278      * from the cache.
 279      *
 280      * This method should be called at the beginning of each public
 281      * method.
 282      */
 283     private void emptyQueue() {
 284         if (queue == null) {
 285             return;
 286         }
 287         int startSize = cacheMap.size();
 288         while (true) {
 289             @SuppressWarnings("unchecked")
 290             CacheEntry<K,V> entry = (CacheEntry<K,V>)queue.poll();
 291             if (entry == null) {
 292                 break;
 293             }
 294             K key = entry.getKey();
 295             if (key == null) {
 296                 // key is null, entry has already been removed
 297                 continue;
 298             }
 299             CacheEntry<K,V> currentEntry = cacheMap.remove(key);
 300             // check if the entry in the map corresponds to the expired
 301             // entry. If not, readd the entry
 302             if ((currentEntry != null) && (entry != currentEntry)) {
 303                 cacheMap.put(key, currentEntry);
 304             }
 305         }
 306         if (DEBUG) {
 307             int endSize = cacheMap.size();
 308             if (startSize != endSize) {
 309                 System.out.println("*** Expunged " + (startSize - endSize)
 310                         + " entries, " + endSize + " entries left");
 311             }
 312         }
 313     }
 314 
 315     /**
 316      * Scan all entries and remove all expired ones.
 317      */
 318     private void expungeExpiredEntries() {
 319         emptyQueue();
 320         if (lifetime == 0) {
 321             return;
 322         }
 323         int cnt = 0;
 324         long time = System.currentTimeMillis();
 325         if (nextExpirationTime > time) {
 326             return;
 327         }
 328         nextExpirationTime = Long.MAX_VALUE;
 329         for (Iterator<CacheEntry<K,V>> t = cacheMap.values().iterator();
 330                 t.hasNext(); ) {
 331             CacheEntry<K,V> entry = t.next();
 332             if (entry.isValid(time) == false) {
 333                 t.remove();
 334                 cnt++;
 335             } else if (nextExpirationTime > entry.getExpirationTime()) {
 336                 nextExpirationTime = entry.getExpirationTime();
 337             }
 338         }
 339         if (DEBUG) {
 340             if (cnt != 0) {
 341                 System.out.println("Removed " + cnt
 342                         + " expired entries, remaining " + cacheMap.size());
 343             }
 344         }
 345     }
 346 
 347     public synchronized int size() {
 348         expungeExpiredEntries();
 349         return cacheMap.size();
 350     }
 351 
 352     public synchronized void clear() {
 353         if (queue != null) {
 354             // if this is a SoftReference cache, first invalidate() all
 355             // entries so that GC does not have to enqueue them
 356             for (CacheEntry<K,V> entry : cacheMap.values()) {
 357                 entry.invalidate();
 358             }
 359             while (queue.poll() != null) {
 360                 // empty
 361             }
 362         }
 363         cacheMap.clear();
 364     }
 365 
 366     public synchronized void put(K key, V value) {
 367         emptyQueue();
 368         long expirationTime = (lifetime == 0) ? 0 :
 369                                         System.currentTimeMillis() + lifetime;
 370         if (expirationTime < nextExpirationTime) {
 371             nextExpirationTime = expirationTime;
 372         }
 373         CacheEntry<K,V> newEntry = newEntry(key, value, expirationTime, queue);
 374         CacheEntry<K,V> oldEntry = cacheMap.put(key, newEntry);
 375         if (oldEntry != null) {
 376             oldEntry.invalidate();
 377             return;
 378         }
 379         if (maxSize > 0 && cacheMap.size() > maxSize) {
 380             expungeExpiredEntries();
 381             if (cacheMap.size() > maxSize) { // still too large?
 382                 Iterator<CacheEntry<K,V>> t = cacheMap.values().iterator();
 383                 CacheEntry<K,V> lruEntry = t.next();
 384                 if (DEBUG) {
 385                     System.out.println("** Overflow removal "
 386                         + lruEntry.getKey() + " | " + lruEntry.getValue());
 387                 }
 388                 t.remove();
 389                 lruEntry.invalidate();
 390             }
 391         }
 392     }
 393 
 394     public synchronized V get(Object key) {
 395         emptyQueue();
 396         CacheEntry<K,V> entry = cacheMap.get(key);
 397         if (entry == null) {
 398             return null;
 399         }
 400         long time = (lifetime == 0) ? 0 : System.currentTimeMillis();
 401         if (entry.isValid(time) == false) {
 402             if (DEBUG) {
 403                 System.out.println("Ignoring expired entry");
 404             }
 405             cacheMap.remove(key);
 406             return null;
 407         }
 408         return entry.getValue();
 409     }
 410 
 411     public synchronized void remove(Object key) {
 412         emptyQueue();
 413         CacheEntry<K,V> entry = cacheMap.remove(key);
 414         if (entry != null) {
 415             entry.invalidate();
 416         }
 417     }
 418 
 419     public synchronized void setCapacity(int size) {
 420         expungeExpiredEntries();
 421         if (size > 0 && cacheMap.size() > size) {
 422             Iterator<CacheEntry<K,V>> t = cacheMap.values().iterator();
 423             for (int i = cacheMap.size() - size; i > 0; i--) {
 424                 CacheEntry<K,V> lruEntry = t.next();
 425                 if (DEBUG) {
 426                     System.out.println("** capacity reset removal "
 427                         + lruEntry.getKey() + " | " + lruEntry.getValue());
 428                 }
 429                 t.remove();
 430                 lruEntry.invalidate();
 431             }
 432         }
 433 
 434         maxSize = size > 0 ? size : 0;
 435 
 436         if (DEBUG) {
 437             System.out.println("** capacity reset to " + size);
 438         }
 439     }
 440 
 441     public synchronized void setTimeout(int timeout) {
 442         emptyQueue();
 443         lifetime = timeout > 0 ? timeout * 1000L : 0L;
 444 
 445         if (DEBUG) {
 446             System.out.println("** lifetime reset to " + timeout);
 447         }
 448     }
 449 
 450     // it is a heavyweight method.
 451     public synchronized void accept(CacheVisitor<K,V> visitor) {
 452         expungeExpiredEntries();
 453         Map<K,V> cached = getCachedEntries();
 454 
 455         visitor.visit(cached);
 456     }
 457 
 458     private Map<K,V> getCachedEntries() {
 459         Map<K,V> kvmap = new HashMap<>(cacheMap.size());
 460 
 461         for (CacheEntry<K,V> entry : cacheMap.values()) {
 462             kvmap.put(entry.getKey(), entry.getValue());
 463         }
 464 
 465         return kvmap;
 466     }
 467 
 468     protected CacheEntry<K,V> newEntry(K key, V value,
 469             long expirationTime, ReferenceQueue<V> queue) {
 470         if (queue != null) {
 471             return new SoftCacheEntry<>(key, value, expirationTime, queue);
 472         } else {
 473             return new HardCacheEntry<>(key, value, expirationTime);
 474         }
 475     }
 476 
 477     private static interface CacheEntry<K,V> {
 478 
 479         boolean isValid(long currentTime);
 480 
 481         void invalidate();
 482 
 483         K getKey();
 484 
 485         V getValue();
 486 
 487         long getExpirationTime();
 488     }
 489 
 490     private static class HardCacheEntry<K,V> implements CacheEntry<K,V> {
 491 
 492         private K key;
 493         private V value;
 494         private long expirationTime;
 495 
 496         HardCacheEntry(K key, V value, long expirationTime) {
 497             this.key = key;
 498             this.value = value;
 499             this.expirationTime = expirationTime;
 500         }
 501 
 502         public K getKey() {
 503             return key;
 504         }
 505 
 506         public V getValue() {
 507             return value;
 508         }
 509 
 510         public long getExpirationTime() {
 511             return expirationTime;
 512         }
 513 
 514         public boolean isValid(long currentTime) {
 515             boolean valid = (currentTime <= expirationTime);
 516             if (valid == false) {
 517                 invalidate();
 518             }
 519             return valid;
 520         }
 521 
 522         public void invalidate() {
 523             key = null;
 524             value = null;
 525             expirationTime = -1;
 526         }
 527     }
 528 
 529     private static class SoftCacheEntry<K,V>
 530             extends SoftReference<V>
 531             implements CacheEntry<K,V> {
 532 
 533         private K key;
 534         private long expirationTime;
 535 
 536         SoftCacheEntry(K key, V value, long expirationTime,
 537                 ReferenceQueue<V> queue) {
 538             super(value, queue);
 539             this.key = key;
 540             this.expirationTime = expirationTime;
 541         }
 542 
 543         public K getKey() {
 544             return key;
 545         }
 546 
 547         public V getValue() {
 548             return get();
 549         }
 550 
 551         public long getExpirationTime() {
 552             return expirationTime;
 553         }
 554 
 555         public boolean isValid(long currentTime) {
 556             boolean valid = (currentTime <= expirationTime) && (get() != null);
 557             if (valid == false) {
 558                 invalidate();
 559             }
 560             return valid;
 561         }
 562 
 563         public void invalidate() {
 564             clear();
 565             key = null;
 566             expirationTime = -1;
 567         }
 568     }
 569 
 570 }