Home | History | Annotate | Download | only in util
      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 
     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 
    256     // ReferenceQueue is of type V instead of Cache<K,V>
    257     // to allow SoftCacheEntry to extend SoftReference<V>
    258     private final ReferenceQueue<V> queue;
    259 
    260     public MemoryCache(boolean soft, int maxSize) {
    261         this(soft, maxSize, 0);
    262     }
    263 
    264     public MemoryCache(boolean soft, int maxSize, int lifetime) {
    265         this.maxSize = maxSize;
    266         this.lifetime = lifetime * 1000;
    267         if (soft)
    268             this.queue = new ReferenceQueue<>();
    269         else
    270             this.queue = null;
    271 
    272         int buckets = (int)(maxSize / LOAD_FACTOR) + 1;
    273         cacheMap = new LinkedHashMap<>(buckets, 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         for (Iterator<CacheEntry<K,V>> t = cacheMap.values().iterator();
    326                 t.hasNext(); ) {
    327             CacheEntry<K,V> entry = t.next();
    328             if (entry.isValid(time) == false) {
    329                 t.remove();
    330                 cnt++;
    331             }
    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     public synchronized int size() {
    342         expungeExpiredEntries();
    343         return cacheMap.size();
    344     }
    345 
    346     public synchronized void clear() {
    347         if (queue != null) {
    348             // if this is a SoftReference cache, first invalidate() all
    349             // entries so that GC does not have to enqueue them
    350             for (CacheEntry<K,V> entry : cacheMap.values()) {
    351                 entry.invalidate();
    352             }
    353             while (queue.poll() != null) {
    354                 // empty
    355             }
    356         }
    357         cacheMap.clear();
    358     }
    359 
    360     public synchronized void put(K key, V value) {
    361         emptyQueue();
    362         long expirationTime = (lifetime == 0) ? 0 :
    363                                         System.currentTimeMillis() + lifetime;
    364         CacheEntry<K,V> newEntry = newEntry(key, value, expirationTime, queue);
    365         CacheEntry<K,V> oldEntry = cacheMap.put(key, newEntry);
    366         if (oldEntry != null) {
    367             oldEntry.invalidate();
    368             return;
    369         }
    370         if (maxSize > 0 && cacheMap.size() > maxSize) {
    371             expungeExpiredEntries();
    372             if (cacheMap.size() > maxSize) { // still too large?
    373                 Iterator<CacheEntry<K,V>> t = cacheMap.values().iterator();
    374                 CacheEntry<K,V> lruEntry = t.next();
    375                 if (DEBUG) {
    376                     System.out.println("** Overflow removal "
    377                         + lruEntry.getKey() + " | " + lruEntry.getValue());
    378                 }
    379                 t.remove();
    380                 lruEntry.invalidate();
    381             }
    382         }
    383     }
    384 
    385     public synchronized V get(Object key) {
    386         emptyQueue();
    387         CacheEntry<K,V> entry = cacheMap.get(key);
    388         if (entry == null) {
    389             return null;
    390         }
    391         long time = (lifetime == 0) ? 0 : System.currentTimeMillis();
    392         if (entry.isValid(time) == false) {
    393             if (DEBUG) {
    394                 System.out.println("Ignoring expired entry");
    395             }
    396             cacheMap.remove(key);
    397             return null;
    398         }
    399         return entry.getValue();
    400     }
    401 
    402     public synchronized void remove(Object key) {
    403         emptyQueue();
    404         CacheEntry<K,V> entry = cacheMap.remove(key);
    405         if (entry != null) {
    406             entry.invalidate();
    407         }
    408     }
    409 
    410     public synchronized void setCapacity(int size) {
    411         expungeExpiredEntries();
    412         if (size > 0 && cacheMap.size() > size) {
    413             Iterator<CacheEntry<K,V>> t = cacheMap.values().iterator();
    414             for (int i = cacheMap.size() - size; i > 0; i--) {
    415                 CacheEntry<K,V> lruEntry = t.next();
    416                 if (DEBUG) {
    417                     System.out.println("** capacity reset removal "
    418                         + lruEntry.getKey() + " | " + lruEntry.getValue());
    419                 }
    420                 t.remove();
    421                 lruEntry.invalidate();
    422             }
    423         }
    424 
    425         maxSize = size > 0 ? size : 0;
    426 
    427         if (DEBUG) {
    428             System.out.println("** capacity reset to " + size);
    429         }
    430     }
    431 
    432     public synchronized void setTimeout(int timeout) {
    433         emptyQueue();
    434         lifetime = timeout > 0 ? timeout * 1000L : 0L;
    435 
    436         if (DEBUG) {
    437             System.out.println("** lifetime reset to " + timeout);
    438         }
    439     }
    440 
    441     // it is a heavyweight method.
    442     public synchronized void accept(CacheVisitor<K,V> visitor) {
    443         expungeExpiredEntries();
    444         Map<K,V> cached = getCachedEntries();
    445 
    446         visitor.visit(cached);
    447     }
    448 
    449     private Map<K,V> getCachedEntries() {
    450         Map<K,V> kvmap = new HashMap<>(cacheMap.size());
    451 
    452         for (CacheEntry<K,V> entry : cacheMap.values()) {
    453             kvmap.put(entry.getKey(), entry.getValue());
    454         }
    455 
    456         return kvmap;
    457     }
    458 
    459     protected CacheEntry<K,V> newEntry(K key, V value,
    460             long expirationTime, ReferenceQueue<V> queue) {
    461         if (queue != null) {
    462             return new SoftCacheEntry<>(key, value, expirationTime, queue);
    463         } else {
    464             return new HardCacheEntry<>(key, value, expirationTime);
    465         }
    466     }
    467 
    468     private static interface CacheEntry<K,V> {
    469 
    470         boolean isValid(long currentTime);
    471 
    472         void invalidate();
    473 
    474         K getKey();
    475 
    476         V getValue();
    477 
    478     }
    479 
    480     private static class HardCacheEntry<K,V> implements CacheEntry<K,V> {
    481 
    482         private K key;
    483         private V value;
    484         private long expirationTime;
    485 
    486         HardCacheEntry(K key, V value, long expirationTime) {
    487             this.key = key;
    488             this.value = value;
    489             this.expirationTime = expirationTime;
    490         }
    491 
    492         public K getKey() {
    493             return key;
    494         }
    495 
    496         public V getValue() {
    497             return value;
    498         }
    499 
    500         public boolean isValid(long currentTime) {
    501             boolean valid = (currentTime <= expirationTime);
    502             if (valid == false) {
    503                 invalidate();
    504             }
    505             return valid;
    506         }
    507 
    508         public void invalidate() {
    509             key = null;
    510             value = null;
    511             expirationTime = -1;
    512         }
    513     }
    514 
    515     private static class SoftCacheEntry<K,V>
    516             extends SoftReference<V>
    517             implements CacheEntry<K,V> {
    518 
    519         private K key;
    520         private long expirationTime;
    521 
    522         SoftCacheEntry(K key, V value, long expirationTime,
    523                 ReferenceQueue<V> queue) {
    524             super(value, queue);
    525             this.key = key;
    526             this.expirationTime = expirationTime;
    527         }
    528 
    529         public K getKey() {
    530             return key;
    531         }
    532 
    533         public V getValue() {
    534             return get();
    535         }
    536 
    537         public boolean isValid(long currentTime) {
    538             boolean valid = (currentTime <= expirationTime) && (get() != null);
    539             if (valid == false) {
    540                 invalidate();
    541             }
    542             return valid;
    543         }
    544 
    545         public void invalidate() {
    546             clear();
    547             key = null;
    548             expirationTime = -1;
    549         }
    550     }
    551 
    552 }
    553