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 }