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 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 && b.length > 0) { 176 hash = h = Arrays.hashCode(b); 177 } 178 return h; 179 } 180 181 public boolean equals(Object obj) { 182 if (this == obj) { 183 return true; 184 } 185 if (obj instanceof EqualByteArray == false) { 186 return false; 187 } 188 EqualByteArray other = (EqualByteArray)obj; 189 return Arrays.equals(this.b, other.b); 190 } 191 } 192 193 public interface CacheVisitor<K,V> { 194 public void visit(Map<K,V> map); 195 } 196 197 } 198 199 class NullCache<K,V> extends Cache<K,V> { 200 201 static final Cache<Object,Object> INSTANCE = new NullCache<>(); 202 203 private NullCache() { 204 // empty 205 } 206 207 public int size() { 208 return 0; 209 } 210 211 public void clear() { 212 // empty 213 } 214 215 public void put(K key, V value) { 216 // empty 217 } 218 219 public V get(Object key) { 220 return null; 221 } 222 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 }