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