001 /*
002 Copyright (c) 1996-2009, Damon Hart-Davis
003 All rights reserved.
004
005 Redistribution and use in source and binary forms, with or without
006 modification, are permitted provided that the following conditions are
007 met:
008
009 * Redistributions of source code must retain the above copyright
010 notice, this list of conditions and the following disclaimer.
011
012 * Redistributions in binary form must reproduce the above copyright
013 notice, this list of conditions and the following disclaimer in the
014 documentation and/or other materials provided with the
015 distribution.
016
017 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
018 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
019 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
020 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
021 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
022 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
023 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
024 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
025 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
026 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
027 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
028 */
029 package org.hd.d.pg2k.svrCore;
030
031 import java.lang.ref.ReferenceQueue;
032 import java.lang.ref.SoftReference;
033 import java.lang.ref.WeakReference;
034 import java.util.ArrayList;
035 import java.util.Collection;
036 import java.util.ConcurrentModificationException;
037 import java.util.Date;
038 import java.util.HashMap;
039 import java.util.Iterator;
040 import java.util.LinkedHashMap;
041 import java.util.List;
042 import java.util.Map;
043 import java.util.Queue;
044 import java.util.Set;
045 import java.util.Timer;
046 import java.util.TimerTask;
047 import java.util.WeakHashMap;
048 import java.util.concurrent.Callable;
049 import java.util.concurrent.ConcurrentHashMap;
050 import java.util.concurrent.ConcurrentLinkedQueue;
051 import java.util.concurrent.ConcurrentMap;
052 import java.util.concurrent.CopyOnWriteArrayList;
053 import java.util.concurrent.atomic.AtomicReference;
054 import java.util.concurrent.locks.ReentrantLock;
055
056 import ORG.hd.d.IsDebug;
057
058
059 /**This contains utilities for memory intensive/sensitive operations.
060 * For example, this can veto or partly serialise memory-intensive
061 * operations such as image resizing in order to prevent the JVM
062 * running out of memory in a resource-constrained environment
063 * such as a Web server.
064 */
065 public final class MemoryTools
066 {
067 /**Prevent creation of instances of this class. */
068 private MemoryTools() { }
069
070 /**Used by (and private to) isMemoryStressed() to detect memory stress; never null.
071 * We use clearing of this reference as an indication of possible memory stress,
072 * or at least of fast memory turnover wrt the rate of poll of this value.
073 * <p>
074 * Marked volatile for thread-safe lock-free access.
075 */
076 private static volatile SoftReference<Object> _iMS_SR = new SoftReference<Object>(new Object());
077
078 /**Time of last check of _iMS_SR; the least significant bit indicates state detected.
079 * If the last bit is 1 it indicates that stress was detected, else none was.
080 * <p>
081 * Marked volatile for thread-safe lock-free access.
082 * <p>
083 * The initial state indicates that stress was not detected.
084 */
085 private static volatile long _iMS_lastCheck = System.currentTimeMillis() & ~1;
086
087 /**Very quick non-blocking internal poll of stress state.
088 * Only to be used internally,
089 * and only valid if isMemoryStressed() is polled regularly.
090 * <p>
091 * Can be used to bias allocators, etc.
092 * <p>
093 * Can be used in a short-cut conditional such as
094 * <code>(_isMemoryStressedQ() && isMemoryStressed())</code>
095 * to avoid running the full-blown isMemoryStressed()
096 * unless we were recently stressed,
097 * ie is quick if not recently stressed
098 * and doesn't give false positives.
099 */
100 private static boolean _isMemoryStressedQ()
101 { return((_iMS_lastCheck & 1) != 0); }
102
103 /**Minimum interval for check/update of _iMS_SR in ms; strictly positive.
104 * If this is too small then the LRU mechanism that should be built into SoftReferences
105 * may mask all but the most severe shortage just before an OOM would have been thrown
106 * if isMemoryStressed() is being called very frequently.
107 * <p>
108 * We probably want to be able to detect milder stress than this,
109 * so a poll on the order of seconds is probably reasonable,
110 * but we try to avoid making this an obvious (sub-)multiple of any regular activity.
111 */
112 private static final int _IMS_CHECK_MS = 2111;
113
114 /**Returns true if the memory system may be under stress, eg not enough free.
115 * This can help the application to avert a shortage by avoiding discretionary allocation,
116 * as well as in reacting to an unexpected shortage/stress.
117 * <p>
118 * This may work best if polled reasonably regularly.
119 * <p>
120 * This is likely to be at best stochastic,
121 * ie more likely to return true under severe memory stress,
122 * and less likely to return true when not under significant memory stress.
123 * <p>
124 * This checks the clearing of a SoftReference as one measure of memory stress:
125 * <ul>
126 * <li>On a system with plenty of free memory this should rarely/never be cleared.
127 * <li>On a system under severe memory stress this may be cleared frequently.
128 * </ul>
129 * <p>
130 * This also makes sure that at least a reasonable fraction of the current heap
131 * 'total' memory is reported as free.
132 * <p>
133 * This may attempt to initiate release of some memory asynchronously
134 * when it detects memory stress.
135 * <p>
136 * TODO: make use of MemoryPoolMXBean (etc) facilities for more robust detection.
137 */
138 public static final boolean isMemoryStressed()
139 {
140 // If it is too soon since we last polled our SoftReference to poll it again
141 // then return whatever 'stress' state we last observed.
142 final long now = System.currentTimeMillis();
143 final long lastCheck = _iMS_lastCheck;
144 if(now - lastCheck <= _IMS_CHECK_MS) { return((lastCheck & 1) != 0); }
145
146 // If our SoftReference has not been cleared
147 // and at least a reasonable fraction (~3%) of the current heap is free
148 // then we record/return that the memory system is apparently not currently stressed.
149 final Runtime r = Runtime.getRuntime();
150 // NOTE: always poll the SoftReference here to keep it 'live', regardless of other checks.
151 final boolean referenceOK = (_iMS_SR.get() != null);
152 final boolean notVeryLowOnMemory = r.freeMemory() > (r.totalMemory() >> 5);
153 if(referenceOK && notVeryLowOnMemory)
154 {
155 _iMS_lastCheck = now & ~1;
156 return(false);
157 }
158
159 // If our SoftReference has been cleared (or we are otherwise very low on memory)
160 // then we deduce that the memory subsystem is currently stressed,
161 // replace the SoftReference with a new (non-null) one if necessary,
162 // and record the 'is stressed' state bit along with the timestamp.
163 if(!referenceOK) { _iMS_SR = new SoftReference<Object>(new Object()); }
164 _iMS_lastCheck = now | 1; // Record the stress that we detected.
165 /* if(IsDebug.isDebug) */ { System.err.println("WARNING: memory subsystem under stress free/total/max "+TextUtils.sizeAsText(r.freeMemory(), true)+"/"+TextUtils.sizeAsText(r.totalMemory(), true)+"/"+TextUtils.sizeAsText(r.maxMemory(), true) + (referenceOK ? "" : " (SoftReferences cleared)" + " @ "+(new Date()))); }
166
167 // Attempt to initiate some memory release in the background.
168 // Also initiate emergency memory frees
169 // iff our soft reference was cleared AND we are low on free space.
170 // which indicates that the system probably is stressed.
171 // This avoids blocking the caller or doing anything intensive on their stack for example.
172 // This is started AFTER cacheing the 'stressed' state
173 // so that a recursive call (soon after) will find it and not have to recompute.
174 _emergencyTrimMemoryUseAsync(!referenceOK && !notVeryLowOnMemory);
175
176 return(true);
177 }
178
179 /**Target amount of free heap space (a decent fraction of current heap size).
180 * Small enough not to be rejected by _makeMemoryAvailable() outright.
181 */
182 private static long _targetFreeMemory()
183 { return(Runtime.getRuntime().totalMemory() >> 2); }
184
185 /**True when there's currently lots of memory free and memory is not otherwise stressed. */
186 public static boolean lotsFree()
187 {
188 return((Runtime.getRuntime().freeMemory() > _targetFreeMemory()) &&
189 !isMemoryStressed());
190 }
191
192 /**Estimate of percentage of free space remaining as a fraction of the system target; in range[0,100].
193 * If at least the target amount of memory is free such that lotsFree() could be true
194 * then this returns 100.
195 * <p>
196 * Nominally, if less than 1% of the target amount of free space is available
197 * the this returns 0, though an OOME is likely before this is reached.
198 * <p>
199 * Lower numbers indicate increasing memory pressure.
200 *
201 * @return value in range zero to 100 inclusive with 0 indicating complete heap exhaustion
202 * and 100 indicating that there is a comfortable portion of heap left.
203 */
204 public static int percentFreeWithinTarget()
205 {
206 final long freeMemory = Runtime.getRuntime().freeMemory();
207 final long targetFreeMemory = _targetFreeMemory();
208 if(freeMemory >= targetFreeMemory) { return(100); } // Plenty of space.
209 // Compute result: overflow is currently unlikely...
210 return((int) ((100 * freeMemory) / targetFreeMemory)); // Conservatively rounds down.
211 }
212
213 /**Thread-safe Collection of registered Compactable instances to containers trimmable at run-time without change to their logical state; never null (except possibly during initialisation).
214 * All Compactable instances are held via WeakReference wrappers to avoid preventing their GC.
215 * <p>
216 * The Collection implementation is unbounded,
217 * should make insertion/deletion O(1),
218 * and must allow safe/sensible concurrent use of iterator() with other uses/modification
219 * and without throwing ConcurrentModificationException so that we can avoid any locking/blocking.
220 * <p>
221 * This is intended only to hold a smallish number of potentially-large collections/containers.
222 */
223 private static final Collection<WeakReference<Compactable>> _tMU_registered = new ConcurrentLinkedQueue<WeakReference<Compactable>>();
224
225 /**Allows a local Compactable instance to register itself.
226 * This is intended only to hold a smallish number of potentially-large collections/containers
227 * that may each be repeatedly compacted over time.
228 * <p>
229 * Should be largely wait-free.
230 * <p>
231 * This may fail to register an item during initialisation,
232 * but in any case no Compactable instance should rely on this to call compact()
233 * but should also be doing the equivalent itself, eg on most accessors as per WeakHashMap.
234 * <p>
235 * @param c fully-constructed non-null Compactable instance
236 */
237 public static final void registerCompactable(final Compactable c)
238 {
239 if(null == c) { throw new IllegalArgumentException(); }
240 // Safe to register concurrently with other activity...
241 _tMU_registered.add(new WeakReference<Compactable>(c));
242 }
243
244 /**If true then attempt to incrementally clear the _emergencyFreeQueue in the background.
245 * The aim is to prevent the _emergencyFreeQueue itself
246 * retaining memory uselessly when many items in it are dead.
247 * <p>
248 * This seems to be much more expensive than expected.
249 */
250 private static final boolean INCR_HOUSEKEEP_EFQ = true;
251
252 /**Queue of one-shot entries that can be called in an emergency to free memory; never null.
253 * Entries are held by weak reference to ensure that they don't prevent GC.
254 * <p>
255 * Whenever we detect that memory is under great stress
256 * we work through this queue in order calling the target
257 * (unless the WeakReference has already expired, in which case we simply discard the entry).
258 * <p>
259 * We may periodically purge this queue of expired items
260 * to avoid it becoming a problem itself.
261 * <p>
262 * Anything that is called by this would need to re-register
263 * in order to be called again, ie on the next emergency.
264 * It is safe to re-register the same Runnable instance in such a case.
265 * <p>
266 * Thread-safe (and its iterators won't ever throw exceptions).
267 */
268 private static final Queue<WeakReference<Runnable>> _emergencyFreeQueue = new ConcurrentLinkedQueue<WeakReference<Runnable>>();
269
270 /**Queue up a handle to be called at most once to release memory on demand when detected to be very low.
271 * Entries are held by weak reference to ensure that they don't prevent GC.
272 * <p>
273 * Anything that is called by this would need to re-register
274 * in order to be called again, ie on the next emergency.
275 * It is safe to re-register the same Runnable instance in such a case,
276 * though registering multiple times would be inadvisable.
277 * <p>
278 * These handles should ideally run without blocking at all,
279 * or at least be quick and avoid deadlock.
280 * <p>
281 * Thread-safe.
282 */
283 public static void registerEmergencyFreeHandle(final Runnable r)
284 {
285 if(null == r) { throw new IllegalArgumentException(); }
286 final Queue<WeakReference<Runnable>> efq = _emergencyFreeQueue;
287
288 // Avoid a possible problem with recursive class initialisation...
289 if(null == efq) { return; }
290
291 // Quickly add the new handle...
292 efq.add(new WeakReference<Runnable>(r));
293 }
294
295 /**Interface for emergency-free handles expecting to be called zero-or-more times. */
296 public interface RecurrentEmergencyFreeHandle extends Runnable { }
297
298 /**Concurrent and thread-safe read-mainly store of permanent emergency-free callbacks; never null once class is initialised. */
299 private static final CopyOnWriteArrayList<WeakReference<RecurrentEmergencyFreeHandle>> _emergencyFreeQueueRecurrent = new CopyOnWriteArrayList<WeakReference<RecurrentEmergencyFreeHandle>>();
300
301 /**Queue up a handle to be called back as often as necessary to release memory on demand when detected to be very low.
302 * Entries are held by weak reference to ensure that they don't prevent GC,
303 * and need not unregister themselves but instead may simply be released to be GCed.
304 * <p>
305 * These entries need not and must not attempt to re-register themselves
306 * or be otherwise registered multiple times.
307 * <p>
308 * We try very hard to make sure that any significant memory required
309 * is allocated (and thus may possibly fail) during registration
310 * rather than when attempting to actually use the callbacks,
311 * thus maximising the chance of working correctly!
312 * <p>
313 * These handles should ideally run without blocking at all,
314 * or at least be quick and avoid deadlock.
315 * <p>
316 * These are assumed to be added (and expire) infrequently.
317 * <p>
318 * Thread-safe.
319 */
320 public static void registerRecurrentEmergencyFreeHandle(final RecurrentEmergencyFreeHandle r)
321 {
322 if(null == r) { throw new IllegalArgumentException(); }
323 final List<WeakReference<RecurrentEmergencyFreeHandle>> efqr = _emergencyFreeQueueRecurrent;
324
325 // Avoid a possible problem with recursive class initialisation...
326 if(null == efqr) { throw new IllegalStateException("store not ready"); }
327
328 assert(!efqr.contains(r));
329
330 // Quickly add the new handle...
331 efqr.add(new WeakReference<RecurrentEmergencyFreeHandle>(r));
332
333 if(ORG.hd.d.IsDebug.isDebug) { System.out.println("RecurrentEmergencyFreeHandle count = "+efqr.size()+"; added "+r+"..."); }
334 }
335
336 /**Private lock for _trimMemoryUse(); never null (except possibly during initialisation). */
337 private static final ReentrantLock _tMU_lock = new ReentrantLock();
338
339 /**Internal routine, thread-safe, to try to (fairly firmly) trim some memory use on demand.
340 * May take some time and resources of its own,
341 * so possibly best only called if there is significant memory stress evident.
342 * <p>
343 * Doesn't force any emergency memory release.
344 * <p>
345 * Thread-safe: silently returns if already running (lock already held)
346 * or in the (unusual) case of the lock not yet initialised/set-up.
347 */
348 private static void _trimMemoryUse()
349 {
350 final ReentrantLock l = _tMU_lock;
351 if(null == l) { return; }
352
353 // Activity counters.
354 int countCompacted = 0;
355
356 if(!l.tryLock()) { return; }
357 try
358 {
359 // Try to trim dead Internable entries...
360 heldInternableCount();
361
362 // Run pending finalizers if possible.
363 System.runFinalization();
364
365 // Trim the fat from all registered Compactable instances.
366 // It is safe to do this concurrently with other activity
367 // (on the registered list and on the objects themselves)
368 // and no ConcurrentModificationException will be thrown.
369 for(final Iterator<WeakReference<Compactable>> it = _tMU_registered.iterator(); it.hasNext(); )
370 {
371 final Compactable c = it.next().get();
372 if(null == c)
373 {
374 // Entry has expired and the instance has been GCed, so zap it...
375 it.remove();
376 continue;
377 }
378
379 // Compact the instance if possible.
380 c.compact(); // Note that this may block.
381 ++countCompacted;
382 }
383
384 if(INCR_HOUSEKEEP_EFQ)
385 {
386 final Queue<WeakReference<Runnable>> efq = _emergencyFreeQueue;
387
388 // Scan the (start of the) queue for dead items
389 // and stop as soon as we encounter a live one
390 // or when there's nothing left in the list.
391 // Helps keep the queue size down.
392 //
393 // Deliberately rotate the queue
394 // to expose 'dead' items further down the list.
395 WeakReference<Runnable> wrr;
396 while(null != (wrr = efq.poll()))
397 {
398 if(null != wrr.get())
399 {
400 // Found a live entry.
401 // Put it back on the end of the queue and stop!
402 efq.add(wrr);
403 break;
404 }
405 }
406
407 // Remove dead recurrent callbacks.
408 // Only do at most once each time as this will be expensive.
409 for(final WeakReference<RecurrentEmergencyFreeHandle> wrrr : _emergencyFreeQueueRecurrent)
410 {
411 if(wrrr.get() == null)
412 {
413 System.out.println("INFO: RecurrentEmergencyFreeHandle expired");
414 // Stop if we actually successfully pruned a dead item.
415 if(_emergencyFreeQueueRecurrent.remove(wrrr)) { break; }
416 }
417 }
418 }
419
420 System.currentTimeMillis();
421 }
422 /* Ensure that the lock is released. */
423 finally { l.unlock(); }
424
425 if(IsDebug.isDebug && (countCompacted != 0))
426 {
427 System.err.println("WARNING: MemoryTools: trimmed memory use: compact()ed "+countCompacted);
428 }
429 }
430
431 /**Private lock for _doEmergencyFree(); never null (except possibly during initialisation). */
432 private static final ReentrantLock _dEF_lock = new ReentrantLock();
433
434 /**Do emergency free/release of memory.
435 * Processes all non-recurrent items in the queue
436 * by draining it into another collection first
437 * then processing all the moved items.
438 * (This prevents items that re-register themselves
439 * from being re-run continuously!)
440 * <p>
441 * FIXME: danger of 'losing' handles if we get another OOM here while moving them around.
442 * <p>
443 * Thread-safe: silently returns (-1) if already running (lock already held)
444 * or in the (unusual) case of the lock not yet initialised/set-up.
445 */
446 private static int _doEmergencyFree()
447 {
448 final Queue<WeakReference<Runnable>> efq = _emergencyFreeQueue;
449 final CopyOnWriteArrayList<WeakReference<RecurrentEmergencyFreeHandle>> efqr = _emergencyFreeQueueRecurrent;
450
451 // Avoid a possible problem with recursive class initialisation...
452 if((null == efq) || (null == efqr)) { return(0); }
453
454 final ReentrantLock l = _dEF_lock;
455 if(null == l) { return(-1); }
456 if(!l.tryLock()) { return(-1); }
457 try {
458 // Do all the recurrent/permanent ones first...
459 int recurrentsDone = 0;
460 for(final WeakReference<RecurrentEmergencyFreeHandle> wrrr : efqr)
461 {
462 // Attempt to prune...
463 final RecurrentEmergencyFreeHandle refh = wrrr.get();
464 if(refh == null) { continue; } // Don't attempt to free dead handle here...
465 System.err.println("About to run recurrent emergency free handle " + refh);
466 try { refh.run(); }
467 // Absorb but report all errors encountered.
468 catch(final Throwable t) { t.printStackTrace(); }
469 ++recurrentsDone;
470 }
471
472 int nonRecurrentsDone = 0;
473 if(null != efq.peek())
474 {
475 // Move to a working List (dropping any dead ones in passing)
476 // all the registered non-recurrent 'emergency free' handles.
477 final List<Runnable> toProcess = new ArrayList<Runnable>();
478 WeakReference<Runnable> wrr;
479 while(null != (wrr = efq.poll()))
480 {
481 final Runnable r = wrr.get();
482 if(r == null) { continue; }
483 toProcess.add(r);
484 }
485
486 // Call all the 'emergency free' handles that we saved above..
487 for(final Runnable r : toProcess)
488 {
489 System.err.println("About to run non-recurrent emergency free handle " + r);
490 try { r.run(); }
491 // Absorb but report all errors encountered.
492 catch(final Throwable t) { t.printStackTrace(); }
493 ++nonRecurrentsDone;
494 }
495 }
496
497 final int freed = nonRecurrentsDone + recurrentsDone;
498 if(freed != 0)
499 { System.err.println("WARNING: MemoryTools: emergency frees processed: "+freed+" ("+recurrentsDone+" recurrent) @ "+(new Date())); }
500
501 return(freed);
502 }
503 finally { l.unlock(); }
504 }
505
506 /**Timer used to process _emergencyTrimMemoryUseAsync() activity; never null.
507 * Runs as a daemon to allow the JVM to exit.
508 * <p>
509 * Avoids having more than one Thread run this concurrently.
510 * <p>
511 * We may also run other periodic tasks with this timer.
512 * TODO: move expensive/periodic checks to this so that isMemoryStressed() calls all just poll a volatile flag
513 */
514 private static final Timer _eTMUATimer = new Timer("_eTMUATimer", true);
515
516 /**Run _trimMemoryUse(), _doEmergencyFree() if requested plus forced GC, asynchronously.
517 * @param doEmergencyFree if true then call the emergency-free handlers and possibly force GC
518 */
519 private static void _emergencyTrimMemoryUseAsync(final boolean doEmergencyFree)
520 {
521 // Schedule task to start ASAP.
522 _eTMUATimer.schedule(new TimerTask(){
523 @Override public void run()
524 {
525 try
526 {
527 _trimMemoryUse(); // Do gentler stuff first that may also yield useful diagnostics.
528 if(doEmergencyFree)
529 { _doEmergencyFree(); } // Now the nuclear option...
530 preemptiveGC(); // Now try to force some space to be *visibly* free.
531
532 final Runtime r = Runtime.getRuntime();
533 /* if(IsDebug.isDebug) */ { System.err.println("INFO: _emergencyTrimMemoryUseAsync() complete: free/total/max "+TextUtils.sizeAsText(r.freeMemory(), true)+"/"+TextUtils.sizeAsText(r.totalMemory(), true)+"/"+TextUtils.sizeAsText(r.maxMemory(), true) + " @ "+(new Date())); }
534 }
535 catch(final Throwable t) { t.printStackTrace(); } // Log error, but absorb it to protect Timer.
536 }
537 }, 0);
538 }
539
540
541 /**If true, only allows one memory-intensive operation to run at once.
542 * This reduces the chance of blowing up the heap,
543 * in return for reducing concurrency on multi-CPU machines.
544 * <p>
545 * We must not hold a lock to enforce this as doing so may cause deadlock;
546 * we veto any concurrent call immediately.
547 */
548 private static final boolean NO_MEM_INTENSIVE_CONCURRENCY = true;
549
550 /**Attempt to make sure that the specified amount of memory is available; return true if so.
551 * If this cannot be done
552 * (eg the requested space is apparently not available,
553 * or it is too soon since the last GC to try to force another full GC)
554 * then this returns false.
555 * <p>
556 * This does not hold any locks.
557 * <p>
558 * We try very hard to avoid actually calling System.gc()
559 * as doing so may upset the ergonomics of almost any GC implementation,
560 * and in particular is quite likely to result in an unwanted long stop-the-world pause.
561 *
562 * @param bytes approximate number of bytes of heap free required; non-negative
563 *
564 * @return true if requested memory is apparently available, false if not available
565 */
566 private static boolean _makeMemoryAvailable(final long bytes)
567 {
568 assert(bytes >= 0);
569
570 final Runtime runtime = Runtime.getRuntime();
571
572 // If the request is less than is currently free
573 // then return true immediately.
574 // Optimisation: we hope that this (short) path will be the usual one.
575 final long freeMemoryInitial = runtime.freeMemory();
576 if(bytes <= freeMemoryInitial) { return(true); }
577
578 // If the request is more than could ever reasonably be available for one purpose
579 // (which we take to be half the maximum heap size, if specified)
580 // then return false immediately.
581 // No point in even trying if this is true...
582 if(bytes >= runtime.maxMemory() >> 1) { return(false); }
583
584
585 // Time before we start any System.gc().
586 final long beforeGC = System.currentTimeMillis();
587
588 // Find out if it is long enough since our last call to System.gc().
589 //
590 // If not then return false immediately to avoid pointlessly thrashing the memory system.
591 if(_rMIO_noGCBefore > beforeGC) { return(false); }
592
593 // Loop to free up memory if necessary, if we can.
594 // The number of iterations is limited.
595 for(int i = _rMIO_MAX_GC_CALLS; --i >= 0; )
596 {
597 // Try some relatively-gentle things first that may help GC,
598 // and that may liberate a little memory immediately.
599 _trimMemoryUse();
600
601 // Force finalize()rs to run while we are at it,
602 // since it might release other resources.
603 // This may also force us to see more of real GC costs.
604 System.runFinalization();
605
606 // If the request is less than is currently/now free
607 // then return true immediately.
608 if(bytes < runtime.freeMemory()) { return(true); }
609
610 // If the request is less than *could* be allocated given maxMemory() and space already in use,
611 // then return true immediately.
612 // But we only trust maxMemory() if it is something less/other than Long.MAX_VALUE.
613 final long maxMemory = runtime.maxMemory();
614 if((maxMemory != Long.MAX_VALUE) &&
615 (bytes < (maxMemory - (runtime.totalMemory() - runtime.freeMemory()))))
616 { return(true); }
617
618 // OK, really try to force some GC.
619 // Of course this may be entirely ignored...
620 System.gc();
621
622 // Postpone the next use of GC by any other caller.
623 final long now = System.currentTimeMillis();
624 final long notBefore =
625 now + Math.max(MIN_WAIT_AFTER_FAILED_GC,
626 ((now - beforeGC) * _rMIO_MAX_GC_FRAC));
627 // Attempt to ensure that we only put the "not-before" time forwards
628 // since there may be other concurrent updaters of this value,
629 // though it is not vital to get it precisely right
630 // (residual races are safe since _rMIO_noGCBefore is volatile and thus accesses are atomic).
631 _rMIO_noGCBefore = Math.max(_rMIO_noGCBefore, notBefore);
632 }
633
634 final boolean succeeded = bytes < runtime.freeMemory(); // Test again...
635 if(!succeeded) { System.err.println("[MemoryTools: FORCED GC FAILED trying to make available "+bytes+" bytes: total GC time: " + (System.currentTimeMillis() - beforeGC) + "ms; free/total/max bytes = "+runtime.freeMemory()+'/'+runtime.totalMemory()+'/'+runtime.maxMemory()+".]"); }
636 return(succeeded); // Failed to free up enough memory...
637 }
638
639 /**Wrapper round runMemoryIntensiveOperation(Runnable, ...) for value-returning tasks that must always be run.
640 * Returns a pair of a Boolean (true if the task ran, false if not)
641 * and the value returned by the Callable (always false if the task is not run).
642 *
643 * @throws Exception any exception thrown by the Callable or our handler routine
644 */
645 public static <V, E extends Exception> V runMemoryIntensiveOperation(
646 final Callable<V> task,
647 final int estimatedMinBytesRequired)
648 throws Exception
649 {
650 final AtomicReference<Exception> ex = new AtomicReference<Exception>();
651 final AtomicReference<V> v = new AtomicReference<V>();
652 final boolean ran = runMemoryIntensiveOperation((new Runnable(){
653 public void run()
654 {
655 try { v.set(task.call()); }
656 catch(final Exception e) { ex.set(e); }
657 }
658 }),
659 true,
660 estimatedMinBytesRequired);
661
662 // Rethrow any Exception generated.
663 final Exception e = ex.get();
664 if(null != e) { throw e; }
665 // Handle the case where the task was not run...
666 assert(ran) : "task must be run";
667 // All OK, return the result...
668 return(v.get());
669 }
670
671 /**Wrapper round runMemoryIntensiveOperation(Runnable, ...) for value-returning tasks.
672 * Returns a pair of a Boolean (true if the task ran, false if not)
673 * and the value returned by the Callable (always false if the task is not run).
674 *
675 * @throws Exception any exception thrown by the Callable or our handler routine
676 */
677 public static <V> Tuple.Pair<Boolean, V> runMemoryIntensiveOperation(
678 final Callable<V> task,
679 final boolean unlimitedMemory,
680 final int estimatedMinBytesRequired)
681 throws Exception
682 {
683 final AtomicReference<Exception> ex = new AtomicReference<Exception>();
684 final AtomicReference<V> v = new AtomicReference<V>();
685 final boolean ran = runMemoryIntensiveOperation((new Runnable(){
686 public void run()
687 {
688 try { v.set(task.call()); }
689 catch(final Exception e) { ex.set(e); }
690 }
691 }),
692 unlimitedMemory,
693 estimatedMinBytesRequired);
694
695 // Rethrow any Exception generated.
696 final Exception e = ex.get();
697 if(null != e) { throw e; }
698 // Handle the case where the task was not run...
699 if(!ran) { return(new Tuple.Pair(Boolean.FALSE, null)); }
700 // All OK, return the result...
701 return(new Tuple.Pair(Boolean.TRUE, v.get()));
702 }
703
704
705 /**Run (or veto by refusing to run) a memory-intensive operation.
706 * This is passed a task to be run,
707 * with an estimate of the amount of extra memory required to run it.
708 * <p>
709 * The task is run, possibly after a delay,
710 * if resources seem to be available for it,
711 * and this routine returns true.
712 * <p>
713 * If sufficient resource (ie memory) does not seem to be available,
714 * then the task is not return and this routine returns false.
715 * <p>
716 * This routine may attempt to free memory by calling System.gc() one
717 * or more times, but because this may be slow and may impact system
718 * performance (eg concurrency) badly, this waits a significant
719 * multiple of the time taken to perform GC between such attempts,
720 * so this routine may refuse to try to free memory for a task even if
721 * it would work.
722 * <p>
723 * This keeps a static variable to track memory use between separate
724 * (concurrent) callers and is thus implicitly counting memory shared
725 * in this JVM or class loader. This routine tries to be robust enough
726 * to work reasonably well even with multiple separate copies of this
727 * class in separate class loaders within one JVM.
728 * <p>
729 * If the unlimitedMemory parameter is true then the task is
730 * always run immediately, and can be used for testing and for
731 * situations where heap space is freely available, eg the heap
732 * may be easily expanded.
733 * <p>
734 * No checked exception is propagated to the caller,
735 * but a non-checked exception may be.
736 * <p>
737 * This routine holds no lock for its duration to avoid deadlocks,
738 * but may "baulk" at (ie refuse to run) concurrent calls so as to limit concurrency.
739 *
740 * @param task the task to be run
741 * @param estimatedMinBytesRequired estimate of peak number of bytes
742 * of heap that the task will use (overestimate rather than
743 * underestimate this value); must be non-negative
744 * @param unlimitedMemory if true, the task is always run
745 * on the assumption that at the moment resources are effectively
746 * unlimited (or at least that this task must be run)
747 * but other memory-intensive tasks may be denied
748 * @return true if the task was run,
749 * false if it was not run because of apparent memory shortage
750 * or because too many other memory-intensive tasks are running
751 *
752 * @throws IllegalArgumentException if the task is null or
753 * a negative amount of memory is specified
754 * @throws IllegalStateException if too much aggregate memory
755 * is being requested between all the concurrent tasks
756 */
757 public static boolean runMemoryIntensiveOperation(
758 final Runnable task,
759 final boolean unlimitedMemory,
760 final int estimatedMinBytesRequired)
761 throws IllegalArgumentException,
762 IllegalStateException
763 {
764 if((task == null) ||
765 (estimatedMinBytesRequired < 0))
766 { throw new IllegalArgumentException(); }
767
768 // Our (possibly inflated) view of the actual memory to set aside.
769 // We have to do whole calculation as a long to avoid overflow
770 // on extreme values.
771 //
772 // We ensure that this is positive,
773 // which ensures that our view of committed memory
774 // will always be positive when at least one
775 // memory-intensive task is running.
776 final long inflatedMemoryEstimate =
777 1 + (estimatedMinBytesRequired * (long) _rMIO_FREE_MEM_MULT);
778
779 // Adjust the committed memory on the way in
780 // (and keep a copy of that new value).
781 // We will release it at the end of the following try/finally.
782 final long committedBytes;
783 synchronized(_rMIO_lock)
784 {
785 if(NO_MEM_INTENSIVE_CONCURRENCY && !unlimitedMemory &&
786 (_rMIO_commitedBytes > 0))
787 { return(false); } // Fail immediately; another in progress.
788
789 committedBytes =
790 (_rMIO_commitedBytes += inflatedMemoryEstimate);
791 }
792 // Release committed memory at the end of this try block...
793 try
794 {
795 // If committedBytes was so huge that our total has wrapped,
796 // then refuse to run this task and undo the change.
797 if(committedBytes <= 0)
798 { throw new IllegalStateException(); }
799
800 // If we have unlimited memory
801 // then always run the task.
802 if(unlimitedMemory)
803 {
804 task.run();
805 return(true); // Ran the task!
806 }
807
808 // If we can't make the memory available then give up and don't run the task.
809 // We allow for memory already committed but possibly not yet allocated
810 // (ie in outer calls where this call is nested).
811 if(!_makeMemoryAvailable(committedBytes))
812 { return(false); }
813
814 // Got the memory: run task!
815 // Yeah baby, yeah!
816 task.run();
817 return(true); // Ran the task.
818 }
819 finally
820 {
821 // Release the committed memory for this task on the way out...
822 synchronized(_rMIO_lock)
823 { _rMIO_commitedBytes -= inflatedMemoryEstimate; }
824 }
825 }
826
827
828 /**Bytes of memory ``committed'' to runMemoryIntensiveOperation().
829 * Private to runMemoryIntensiveOperation() and accessed by it under
830 * the _rMIO_lock lock.
831 * <p>
832 * Initially zero.
833 */
834 private static long _rMIO_commitedBytes;
835
836 /**Time before which System.gc() should not be retried; private to _makeMemoryAvailable().
837 * Based on how long was spent running System.gc() on a previous
838 * attempt, this prevents system resources being significantly
839 * impacted by us continually running System.gc().
840 * <p>
841 * Initialised with 'now' to postpone the first attempt to force GC.
842 * <p>
843 * Is volatile to allow it to be read/written safely without a lock.
844 */
845 private static volatile long _rMIO_noGCBefore = System.currentTimeMillis();
846
847 /**Private lock for runMemoryIntensiveOperation(). */
848 private static final Object _rMIO_lock = new Object();
849
850 /**Maximum fraction of wall-clock time we will spend running GC; strictly positive.
851 * If this is N we will spend at most 1/(1+N) of wall-clock time running
852 * System.gc().
853 * <p>
854 * TODO: we might additionally abort if we've spent more than some
855 * fixed time, eg 30s, trying to collect garbage already.
856 * <p>
857 * This is used to limit impact on global system performance.
858 * <p>
859 * A value between 10 and 100 is probably reasonable.
860 */
861 private static final int _rMIO_MAX_GC_FRAC = 37;
862
863 /**Minimum time before attempting forced GC after previous attempt (ms); strictly positive.
864 * This can save us from churning the heap too hard,
865 * or wasting time when System.gc() does nothing at all.
866 * <p>
867 * This can be a few seconds through to a few minutes.
868 */
869 private static final int MIN_WAIT_AFTER_FAILED_GC = 50000 + Rnd.fastRnd.nextInt(31013);
870
871 /**Maximum number of times that we will call System.gc() to free memory; strictly positive.
872 * This is per call to runMemoryIntensiveOperation();
873 * we may do less than this.
874 * <p>
875 * It may be worth calling System.gc() more than once because it may
876 * in fact take several passes in some JVMs to liberate all the
877 * heap from several different heap areas and across several threads,
878 * but calling it lots of times is probably just a huge drain on system
879 * resources or may simply be ignored by the JVM.
880 * <p>
881 * A value from 1 to 3 inclusive is probably good.
882 */
883 private static final int _rMIO_MAX_GC_CALLS = 2;
884
885 /**Multiple of excess free memory there should be before attempting memory-intensive task; strictly positive.
886 * Bigger numbers are more conservative and reduce the probability
887 * of a crash due to running out of memory, but increase the
888 * chance of not running such as task when we otherwise could.
889 * <p>
890 * If we eliminate concurrency between memory-intensive operations
891 * then we can be less conservative than we otherwise would be,
892 * and indeed can possibly drop this down to 1.
893 * <p>
894 * A value in the range 1--4 is probably good.
895 */
896 private static final int _rMIO_FREE_MEM_MULT =
897 NO_MEM_INTENSIVE_CONCURRENCY ? 1 : 2;
898
899
900 /**Request a pre-emptive garbage collection, for example while the system is (too) quiet.
901 * This request may be ignored (eg if too soon after a previous one)
902 * and the system may ignore any attempts made here,
903 * or may do it asynchronously, or may do a partial GC.
904 * <p>
905 * This should be called when the system seems to be idle
906 * (in terms of human user, eg Web site visitor, activity)
907 * and is likely to idle for (say) a minute or so,
908 * to allow us to get in a full GC run while no one is looking,
909 * so as we can last as long as possible without an intrusive
910 * GC when the system <em>is</em> in use later.
911 * This may help recover from (for example) leaked file handles
912 * preventing any clients contacting us.
913 * <p>
914 * An alternative use is when we can't see
915 * a comfortable margin of free memory
916 * (possibly even though we've just trimmed significant fat)
917 * and we want to try to force such a margin to be visibly free.
918 *
919 * @return true if we apparently managed to free up some memory, else false
920 */
921 public static boolean preemptiveGC()
922 {
923 final Runtime runtime = Runtime.getRuntime();
924
925 // Do some trivial internal non-destructive things...
926 heldInternableCount();
927
928 // Always run finalisers where possible
929 // since this should be reasonably quick
930 // and may release some orphaned resources
931 // including non-memory resources such as file handles.
932 runtime.runFinalization();
933
934 // Our target is to have about one quarter of the heap free,
935 // which suggests an efficient and relatively-unstressed system.
936 // This is 'lotsFree()'.
937 final long targetFree = _targetFreeMemory();
938 if(runtime.freeMemory() > targetFree) { return(false); }
939
940 // If we did not have our target memory free
941 // then push to get more free()d up to get some hysteresis and less churn.
942 // This may invoke System.gc().
943 if(!_makeMemoryAvailable(targetFree))
944 { return(false); } // Didn't manage to do much useful...
945
946 System.out.println("[MemoryTools.preemptiveGC(): free="+
947 TextUtils.sizeAsText(runtime.freeMemory(), true)+"/"+
948 TextUtils.sizeAsText(runtime.totalMemory(), true)+"/"+
949 TextUtils.sizeAsText(runtime.maxMemory(), true)+" "+
950 "Internable#"+heldInternableCount()+".]");
951 return(true);
952 }
953
954
955
956 /**Marker interface indicating class is suitable for deduping by intern().
957 * Any class implementing this interface must be immutable,
958 * and must have working equals() and hashCode() methods.
959 */
960 public static interface Internable { }
961
962 // /**Marker for Internable class that some instances are more equal than others.
963 // * Of two instances that are equals(),
964 // * that with a lower internableRank() is preferred
965 // * and may replace the higher-valued one.
966 // * <p>
967 // * Will only be called on items with equals() == true.
968 // * <p>
969 // * This should provide a total ordering like Comparable.
970 // * <p>
971 // * Note that objects supporting this interface cannot rely on == for equality
972 // * since multiple instances with the same value may exist concurrently,
973 // * though they should generally be few and gravitating towards the 'best'.
974 // * <p>
975 // * Use with care as this may end up causing unexpected loss of copy control
976 // * and thus something that behaves like a 'leak'.
977 // */
978 // public static interface InternableRank extends Internable { int internableRank(InternableRank obj); }
979
980 /**Marker interface indicating that a class is suitable for compacting in memory.
981 * Generally the single compact() method should not change the logical state,
982 * nor should it consume lots of resources if avoidable
983 * (eg lots of memory, or lots of CPUs)
984 * and may call Thread.yield() periodically,
985 * and by the time it returns all compact()ion activity has completed
986 * (ie this will not launch background threads to do the work,
987 * though may often be launched from one).
988 * <p>
989 * Calling the compact() method should be thread-safe,
990 * ie so we can do it asynchronously from a background thread if we wish,
991 * for example when we detect system memory to be under stress.
992 */
993 public static interface Compactable { void compact(); }
994
995 /**If true then force single-CPU mode. */
996 private static final boolean FORCE_SINGLE_CPU_MODE = false;
997
998 /**If true then run in single-CPU mode to save some space and time overheads by giving up some concurrency. */
999 private static final boolean SINGLE_CPU_MODE = FORCE_SINGLE_CPU_MODE || (ThreadUtils.AVAILABLE_PROCESSORS == 1);
1000
1001 /**Power of maximum concurrency available in intern(); non-negative (0 in single-CPU mode). */
1002 private static final int MAX_INTERN_CONC_POWER = SINGLE_CPU_MODE ? 0 : 6;
1003
1004 /**Private to intern(): for holding Internable values.
1005 * Each map must be accessed only under a lock on that map to serialise access
1006 * as WeakHashMap is not itself thread-safe.
1007 * <p>
1008 * We start this off reasonably large,
1009 * and with a low load factor, for access performance.
1010 * <p>
1011 * Unless in SINGLE_CPU mode we have many maps
1012 * to usually allow multiple concurrent intern() operations.
1013 */
1014 private static final WeakHashMap<Internable, WeakReference<Internable>>[] WHM_Internables =
1015 GenUtils.<WeakHashMap<Internable, WeakReference<Internable>>[]>cast(new WeakHashMap[1 << MAX_INTERN_CONC_POWER]);
1016 static
1017 {
1018 final int subMapInitialCapacity = Math.max(128, 32788 >>> MAX_INTERN_CONC_POWER);
1019 for(int i = WHM_Internables.length; --i >= 0; )
1020 { WHM_Internables[i] = new WeakHashMap<Internable, WeakReference<Internable>>(subMapInitialCapacity, 0.5f); }
1021 }
1022
1023 /**Get current number of Internable items held, and purge any dead entries too. */
1024 private static int heldInternableCount()
1025 {
1026 int totalSize = 0;
1027 for(int i = WHM_Internables.length; --i >= 0; )
1028 {
1029 final WeakHashMap<Internable, WeakReference<Internable>> WHM_Internable = WHM_Internables[i];
1030 synchronized(WHM_Internable)
1031 { totalSize += WHM_Internable.size(); }
1032 }
1033 return(totalSize);
1034 }
1035
1036 /**If true, we trust String.intern() to be sensible and to allow GC of unused entries, and thus we delegate handling of at least some String values to it. */
1037 private static final boolean _USE_STRING_INTERN = true;
1038
1039 /**Strings no longer than this use our storage rather than String.intern().
1040 * If this threshold is less than Integer.MAX_VALUE
1041 * then this has the effect of keeping big Strings out of the PermGen in Sun's JVMs,
1042 * which probably would not meld with any JVM-intern()ed value anyway.
1043 * Avoiding String.intern() may save time as well as heap-management problems.
1044 * (Allowing some short values to use String.intern() may increase available concurrency slightly.)
1045 * <p>
1046 * A reasonable value for this threshold is probably in the range -1--1024, for example:
1047 * <ul>
1048 * <li>-1 prevents use of String.intern(),</li>
1049 * <li>0 allows only "" use of String.intern(),</li>
1050 * <li>Integer.MAX_VALUE to allow all values to use String.intern().</li>
1051 * </ul>
1052 */
1053 private static final int MAX_STRING_INTERN = 1; // Allow (presumably relatively few) tiny values only.
1054
1055 /**Specific overloading of intern() for String to avoid runtime instanceof cost where possible.
1056 */
1057 public static String intern(final String s)
1058 {
1059 if(s == null) { return(null); }
1060
1061 // Assume that JVM's String.intern() is sensible and efficient and robust
1062 // and allows GC of no-longer-used items in modern JVMs (1.4+)...
1063 // At least for smallish String values.
1064 if(_USE_STRING_INTERN && (s.length() <= MAX_STRING_INTERN))
1065 {
1066 //System.out.println("MemoryTools.intern(String): using String.intern() for length "+s.length() + ": " + s);
1067 return(s.intern());
1068 }
1069
1070 //System.out.println("MemoryTools.intern(String): avoiding String.intern() for length "+s.length() + ": " + s);
1071
1072 // Use our generic Internable mechanism for long(er) String values.
1073 final class StringWrapper implements Internable
1074 {
1075 /**Our encapsulated immutable String; never null. */
1076 final String str = s;
1077
1078 /**Hash code as from underlying String. */
1079 @Override
1080 public final int hashCode() { return(str.hashCode()); }
1081
1082 /**Equality based on underlying String instances being equal. */
1083 @Override
1084 public final boolean equals(final Object obj)
1085 {
1086 if(this == obj) { return(true); }
1087 if(!(obj instanceof StringWrapper)) { return(false); }
1088 final StringWrapper other = (StringWrapper) obj;
1089 return(str.equals(other.str));
1090 }
1091 }
1092
1093 // Recursively handle the wrapped value as an Internable.
1094 return((intern(new StringWrapper())).str);
1095 }
1096
1097 /**Specific overloading of intern() for Internable to avoid runtime instanceof cost where possible.
1098 */
1099 @SuppressWarnings("unchecked")
1100 public static <E extends Internable> E intern(final E o)
1101 {
1102 if(o == null) { return(null); }
1103
1104 final WeakHashMap<Internable, WeakReference<Internable>> WHM_Internable;
1105 if(SINGLE_CPU_MODE)
1106 { WHM_Internable = WHM_Internables[0]; } // Just one map in SINGLE_CPU_MODE...
1107 else
1108 {
1109 // Select which sub-map we're working on (concurrently)...
1110 int oHash = o.getClass().hashCode() ^ o.hashCode();
1111 oHash ^= (oHash >>> 24) - (oHash >> 13);
1112 oHash ^= (oHash >>> MAX_INTERN_CONC_POWER) ^ (oHash >>> (2*MAX_INTERN_CONC_POWER));
1113 final int index = oHash & ((1 << MAX_INTERN_CONC_POWER) - 1);
1114 WHM_Internable = WHM_Internables[index];
1115 }
1116
1117 // Serialise access to protect the (non-thread-safe) Map and
1118 // to eliminate races so that we get complete canonicalisation.
1119 // Note that separate sub-maps can be accessed concurrently.
1120 synchronized(WHM_Internable)
1121 {
1122 // If we have an extant entry then return it
1123 // unless it is beaten on InternalRank.
1124 final WeakReference<E> v = (WeakReference<E>) WHM_Internable.get(o);
1125 final E old;
1126 if((v != null) && (null != (old = v.get())))
1127 {
1128 // // Return old instance if this new instance is not ranked,
1129 // // or if it has a non-positive ranking compared to (ie is no worse than)
1130 // // the new value.
1131 // if((!(old instanceof InternableRank)) ||
1132 // (((InternableRank) old).internableRank((InternableRank)o) <= 0))
1133 { return(old); } // Return existing intern()ed (non-null) value.
1134 }
1135
1136 // Insert (and return) new (unique or lowest ranked) value just passed in.
1137 WHM_Internable.put(o, new WeakReference<Internable>(o));
1138 return(o); // Return original (unique or lowest ranked) instance.
1139 }
1140 }
1141
1142 /**Specific overloading of intern() for Number to avoid runtime instanceof cost where possible.
1143 */
1144 @SuppressWarnings("unchecked")
1145 public static <E extends Number> E intern(final E o)
1146 {
1147 if(o == null) { return(null); }
1148
1149 final Class oC = o.getClass();
1150 if( (oC == java.lang.Long.class) ||
1151 (oC == java.lang.Integer.class) ||
1152 (oC == java.lang.Short.class) ||
1153 (oC == java.lang.Float.class) ||
1154 (oC == java.lang.Double.class))
1155 {
1156 final Number n = o;
1157
1158 final class NumberWrapper implements Internable
1159 {
1160 /**Our encapsulated immutable Number; never null. */
1161 final Number num = n;
1162
1163 /**Hash code as from underlying Number. */
1164 @Override
1165 public final int hashCode() { return(num.hashCode()); }
1166
1167 /**Equality based on underlying Number instances being equal. */
1168 @Override
1169 public final boolean equals(final Object obj)
1170 {
1171 if(this == obj) { return(true); }
1172 if(!(obj instanceof NumberWrapper)) { return(false); }
1173 final NumberWrapper other = (NumberWrapper) obj;
1174 return(num.equals(other.num));
1175 }
1176 }
1177
1178 // Recursively handle the wrapped value as an Internable.
1179 return((E) (intern(new NumberWrapper())).num);
1180 }
1181 // Eliminate duplicate Byte values with JDK1.5+ Byte.valueOf()
1182 // as an efficient alternative to our generic mechanism.
1183 else if(o instanceof java.lang.Byte)
1184 { return((E) Byte.valueOf(((Byte) o).byteValue())); }
1185
1186 return(o); // Can't handle this unknown Number subtype.
1187 }
1188
1189 /**Generic equivalent of String.intern(), for more immutable objects that we care about.
1190 * Any object which is immutable (and probably final) and has functional
1191 * equals() and hashcode() methods where only apparently-identical instances
1192 * are equal can potentially be cached/canonicalised/deduped
1193 * via this routine.
1194 * <p>
1195 * This generic routine is for where we do not know the type until run-time;
1196 * the compiler may select a better overloading at compile-time otherwise.
1197 * Thanks to Peter Ahé of Sun for the suggestion!
1198 * <p>
1199 * Note that lots of immutable/final objects are <em>not</em>
1200 * suitable for canonicalisation with this routine.
1201 * Caveat programmer.
1202 * <p>
1203 * A unique instance is returned of the same type.
1204 * <p>
1205 * When the intern method is invoked, if the pool already contains an
1206 * Object equal to this <code>Object</code> o as determined by
1207 * the equals(Object) method, then the object from the pool is
1208 * returned. Otherwise, this <code>Object</code> is added to the
1209 * pool and a reference to this <code>Object</code> is returned.
1210 * <p>
1211 * It follows that for any two Objects <code>s</code> and <code>t</code>,
1212 * <code>intern(s) == intern(t)</code> is <code>true</code>
1213 * if and only if <code>s.equals(t)</code> is <code>true</code>.
1214 * <p>
1215 * Entries are automatically dropped sometime after the last
1216 * strong/soft reference to them has gone,
1217 * possibly on the next call to this routine.
1218 * <p>
1219 * Unlike String.intern(), this applies to more than just String elements,
1220 * and memory is guaranteed to be recoverable from non-referenced items
1221 * (whereas String.intern() has not always been so and is still
1222 * not clear in the spec).
1223 * <p>
1224 * It is probably not especially useful to put String constants or other
1225 * static items in here routinely as their entries are unlikely
1226 * to become unreferenced.
1227 * <p>
1228 * This routine is likely to be quite slow and have significant overhead,
1229 * so only use it when not doing so would cause huge memory bloat or churn,
1230 * and when you expect the intern()ed values to live for a long time.
1231 * <p>
1232 * May not in fact be able to cache/canonicalise all or any objects;
1233 * mutable objects should never be intern()ed.
1234 * <p>
1235 * Calling this with null returns null.
1236 *
1237 * @return an Object that has the same contents as this Object,
1238 * but is guaranteed to be from a pool of unique Objects.
1239 */
1240 // public static final Object intern(final Object o)
1241 @SuppressWarnings("unchecked")
1242 public static <E> E intern(final E o)
1243 {
1244 if(o == null) { return(null); }
1245
1246 // Default is to do nothing.
1247 E result = o;
1248
1249 // Extract the class for quick comparison...
1250 final Class oC = o.getClass();
1251
1252 // Assume that String values are very frequent intern()ees,
1253 // so handle these first.
1254 if(oC == String.class)
1255 { result = (E) intern((String) o); }
1256
1257 // Handle Internable objects...
1258 else if(o instanceof Internable)
1259 { result = (E) intern((Internable) o); }
1260
1261 // Handle specific immutable instances of Number.
1262 // We only attempt to handle the common JDK-supplied types
1263 // from the java.lang.* API that we know to be immutable/safe.
1264 else if(o instanceof java.lang.Number)
1265 { result = (E) intern((Number) o); }
1266
1267 // Canonicalise Boolean values in the obvious way...
1268 else if(oC == Boolean.class)
1269 { result = (E) (((Boolean) o).booleanValue() ? Boolean.TRUE : Boolean.FALSE); }
1270
1271 // Else consider warning about pointless calls to intern().
1272 else if(IsDebug.isDebug)
1273 { System.err.println("WARNING: MemoryTools.intern() cannot handle objects of type: " + o.getClass().getName()); }
1274
1275 // Check that the expected invariants hold when we're done.
1276 assert(result.getClass() == o.getClass());
1277 assert(result.equals(o) && o.equals(result) && (result.hashCode() == o.hashCode()));
1278
1279 return(result);
1280 }
1281
1282
1283 /**Simplified thread-safe map with fixed capacity that discards excess items in LRU (Least Recently Used) order.
1284 * This provides a map with a fixed upper size.
1285 * Attempts to insert more items than the capacity
1286 * will result in old items being removed in LRU order,
1287 * thus leaving the newest items in the cache.
1288 * <p>
1289 * Each put() or get() makes its key/value pair the most-recently used
1290 * and thus the last to be removed from the map
1291 * of current key/value pairs
1292 * when a series of put()s forces the map to overflow.
1293 * <p>
1294 * Thread-safe.
1295 * <p>
1296 * A lock can be held on instances of this object to make compound operations atomic.
1297 * <p>
1298 * Does not support the full Map interface.
1299 */
1300 public static final class SimpleLRUMap<K,V>
1301 {
1302 /**Default load factor. */
1303 private static final float defaultLoadFactor = 0.7f;
1304
1305 /**Underlying (non-thread-safe) LinkedHashMap on which this is based; never null. */
1306 private final LinkedHashMap<K,V> lhm;
1307
1308 /**Optional name for diagnostics; can be null. */
1309 private final String name;
1310
1311 /**Create an instance with given (positive) maximum size and the default load factor. */
1312 public SimpleLRUMap(final int maxCapacity, final String name) { this(maxCapacity, defaultLoadFactor, name); }
1313
1314 /**Create an instance with given (positive) maximum size and load factor. */
1315 public SimpleLRUMap(final int maxCapacity, final float loadFactor, final String name)
1316 {
1317 if((maxCapacity < 0) || (loadFactor <= 0) || (loadFactor >= 1))
1318 { throw new IllegalArgumentException(); }
1319 // Build access-order map with override for removal of oldest entry when map too big.
1320 lhm = new LinkedHashMap<K,V>(maxCapacity, loadFactor, true){
1321 @Override protected final boolean removeEldestEntry(final Map.Entry<K, V> entry)
1322 { return(size() > maxCapacity); }
1323 /**Unique Serialisation class ID generated by http://random.hd.org/. */
1324 private static final long serialVersionUID = 3013203100902112945L;
1325 };
1326 this.name = name;
1327 }
1328
1329 /**Get an entry from the map, making it the Most Recently Used; null if no such element. */
1330 public synchronized V get(final K key) { return(lhm.get(key)); }
1331
1332 /**Put an entry in the map, making it the Most Recently Used, returning previous value if any. */
1333 public synchronized V put(final K key, final V value) { return(lhm.put(key, value)); }
1334
1335 /**Remove an entry from the map and return the removed value, if any, else null. */
1336 public synchronized V remove(final K key) { return(lhm.remove(key)); }
1337
1338 /**Clear the map. */
1339 public synchronized void clear() { lhm.clear(); }
1340
1341 /**Take a copy of the map contents, which does not alter LRU; never null. */
1342 public synchronized Map<K,V> getCopy() { return(new HashMap<K,V>(lhm)); }
1343
1344 /**Return the number of entries in the map; non-negative. */
1345 public synchronized int size() { return(lhm.size()); }
1346
1347 /**Provide a human-readable summary of status.
1348 * Useful for debugging/tuning, for example.
1349 */
1350 @Override
1351 public synchronized String toString()
1352 { return("SimpleLRUMap: name '"+name+"', size "+lhm.size()); }
1353 }
1354
1355
1356 /**Simplified map with fixed capacity bounds that discards excess items in LRU (Least Recently Used) order to meet a hit/miss ratio goal.
1357 * This adjusts its size to maintain a specific hit/miss ratio in get(),
1358 * a miss being a get() that returns null,
1359 * trimming away older items at insert to maintain the ratio.
1360 * <p>
1361 * This will also discard entries LRU if memory is under stress
1362 * while the map is above its minimum size.
1363 * <p>
1364 * This provides optional fixed lower and upper sizes.
1365 * Attempts to insert more items than the ceiling capacity
1366 * will result in old items being removed in LRU order,
1367 * thus leaving the newest items in the cache.
1368 * <p>
1369 * Each put() or get() makes its key/value pair the most-recently used
1370 * and thus the last to be removed from the map
1371 * of current key/value pairs
1372 * when a series of put()s forces the map to overflow.
1373 * <p>
1374 * Thread-safe.
1375 * <p>
1376 * A lock can be held on instances of this object to make compound operations atomic.
1377 * <p>
1378 * Does not support the full Map interface.
1379 */
1380 public static final class SimpleLRUMapAutoSizeForHitRate<K,V> implements Compactable
1381 {
1382 /**Default maximum miss rate ]0.0,1.0[. */
1383 public static final float DEFAULT_MAX_MISS_RATE = 0.01f;
1384
1385 /**Default load factor. */
1386 public static final float DEFAULT_LOAD_FACTOR = 0.7f;
1387
1388 /**Default minimum size/capacity, also initial capacity; strictly positive. */
1389 public static final int DEFAULT_MIN_SIZE = 11;
1390
1391 /**Underlying LinkedHashMap on which this is based; never null. */
1392 private final LinkedHashMap<K,V> lhm;
1393
1394 /**The minimum size/capacity; strictly positive. */
1395 private final int minSize;
1396
1397 /**The maximum size/capacity; strictly positive and greater than minSize. */
1398 private final int maxCapacity;
1399
1400 /**The rounded negative log2 of the maximum miss rate usable as an int shift; in the range [1,30]. */
1401 private final int missFracPower;
1402
1403 /**Number of non-miss get()s after which we consider trimming the map if meeting the max-miss-rate targets; strictly positive.
1404 * This is inversely related to our maxMissRate so as to avoid
1405 * us shrinking the map too quickly and throwing away rarely-accessed
1406 * but still-useful items at the tail of our distribution.
1407 */
1408 private final int trimCheckRate;
1409
1410 /**Name of this container instance for tracking purposes, or null if none. */
1411 private final String name;
1412
1413 /**Create an instance with all defaults and therefore an effectively-unbounded upper capacity of Integer.MAX_VALUE. */
1414 private SimpleLRUMapAutoSizeForHitRate()
1415 { this(DEFAULT_MAX_MISS_RATE, DEFAULT_MIN_SIZE, Integer.MAX_VALUE, DEFAULT_LOAD_FACTOR, null); }
1416
1417 /**Create an instance with all defaults and therefore an effectively-unbounded upper capacity of Integer.MAX_VALUE. */
1418 public static <K,V> SimpleLRUMapAutoSizeForHitRate<K,V> create()
1419 {
1420 final SimpleLRUMapAutoSizeForHitRate<K,V> result = new SimpleLRUMapAutoSizeForHitRate<K,V>();
1421 registerCompactable(result);
1422 return(result);
1423 }
1424
1425 /**Create an instance with all defaults except for the specified minimum/maximum capacities. */
1426 public static <K,V> SimpleLRUMapAutoSizeForHitRate<K,V> create(final int minSize, final int maxCapacity, final String name)
1427 {
1428 final SimpleLRUMapAutoSizeForHitRate<K,V> result = new SimpleLRUMapAutoSizeForHitRate<K,V>(DEFAULT_MAX_MISS_RATE, minSize, maxCapacity, DEFAULT_LOAD_FACTOR, name);
1429 registerCompactable(result);
1430 return(result);
1431 }
1432
1433 /**Create an instance with the given parameters.
1434 * The standard default is used for the load factor,
1435 * and the map size is effectively unlimited.
1436 *
1437 * @param maxMissRate the target cache maximum miss rate;
1438 * in the range 0.0f to 1.0f exclusive (typically << 0.1)
1439 * @param minSize the minimum (and initial) capacity;
1440 * strictly positive
1441 * @param name for memory-footprint tuning/debugging; may be null
1442 */
1443 public static <K,V> SimpleLRUMapAutoSizeForHitRate<K,V> create(final float maxMissRate, final int minSize, final String name)
1444 {
1445 final SimpleLRUMapAutoSizeForHitRate<K,V> result = new SimpleLRUMapAutoSizeForHitRate<K,V>(maxMissRate, minSize, Integer.MAX_VALUE, DEFAULT_LOAD_FACTOR, name);
1446 registerCompactable(result);
1447 return(result);
1448 }
1449
1450 /**Create an instance with the given parameters.
1451 *
1452 * @param maxMissRate the target cache maximum miss rate;
1453 * in the range 0.0f to 1.0f exclusive (typically << 0.1)
1454 * @param minSize the minimum (and initial) capacity;
1455 * non-negative
1456 * @param maxCapacity the maximum capacity;
1457 * greater than minCapacity (and this strictly positive)
1458 * @param loadFactor the load factor of the underlying hash table;
1459 * in the range 0.0f to 1.0f exclusive (typically ~0.7f)
1460 */
1461 private SimpleLRUMapAutoSizeForHitRate(final float maxMissRate, final int minSize, final int maxCapacity, final float loadFactor, final String name)
1462 {
1463 if((minSize < 0) || (maxCapacity <= minSize) ||
1464 (maxMissRate <= 0) || (maxMissRate >= 1) ||
1465 (loadFactor <= 0) || (loadFactor >= 1))
1466 { throw new IllegalArgumentException(); }
1467
1468 this.minSize = minSize;
1469 this.maxCapacity = maxCapacity;
1470
1471 final int exp = Math.getExponent(maxMissRate);
1472 //if(IsDebug.isDebug) { System.out.println("SimpleLRUMapAutoSizeForHitRate: maxMissrate="+maxMissRate+", exponent="+exp); }
1473 this.missFracPower = Math.max(1, Math.min(30, -exp));
1474
1475 // Choose a sensible value significantly greater than 1
1476 // so as to keep the per-get() call cost down,
1477 // and high enough to avoid discarding useful long-tail entries...
1478 this.trimCheckRate = Math.max(7+(minSize>>>2), Math.min(maxCapacity,
1479 Math.round(0.101f / maxMissRate)));
1480
1481 // Build access-order map with override for removal of oldest entry when map too big.
1482 lhm = new LinkedHashMap<K,V>(minSize, loadFactor, true){
1483 @Override
1484 protected final boolean removeEldestEntry(final Map.Entry<K, V> entry)
1485 {
1486 final int s = size();
1487
1488 // If over-size then always zap the eldest entry.
1489 if(s > maxCapacity) { return(true); }
1490
1491 // If under-size then definitely don't zap anything.
1492 if(s <= minSize) { return(false); }
1493
1494 // If we're meeting the maximum-miss-rate target
1495 // or system memory is lower than target
1496 // then we zap the oldest entry
1497 // so as to stop the map from growing any larger...
1498 return(meetingMissRateTarget() || (s > computeCapacityCap()));
1499 }
1500 /**Unique Serialisation class ID generated by http://random.hd.org/. */
1501 private static final long serialVersionUID = 3013203108802112945L;
1502 };
1503
1504 // Instance 'name' for tracking memory use, etc.
1505 this.name = name;
1506 }
1507
1508 /**Count of get() calls; non-negative and usually no larger than maxCapacity. */
1509 private int countGets;
1510
1511 /**Count of get() calls that returned null, ie misses; non-negative and no larger than countGets. */
1512 private int countGetMisses;
1513
1514 /**Count to trigger possible trim of cache size; non-negative. */
1515 private int cacheTrimTryCount;
1516
1517 /**Returns true if we are meeting/bettering the miss-rate target.
1518 * Will not return true until we have a reasonable number of samples.
1519 * <p>
1520 * We avoid potentially-slow floating-point arithmetic on the call,
1521 * since it may be made quite often.
1522 */
1523 private boolean meetingMissRateTarget()
1524 {
1525 // If no (recent) misses at all then we are definitely doing OK!
1526 if(countGetMisses == 0) { return(true); }
1527
1528 // If the number of actual misses is exceeded by
1529 // the number of misses allowed given the get() count and target rate
1530 // then we are meeting the target.
1531 // return(Math.round(countGets * maxMissRate) >= countGetMisses);
1532 return((countGets >>> missFracPower) >= countGets);
1533 }
1534
1535 /**Computes target map size cap based on system memory availability; in range [minSize,maxCapacity].
1536 * If free memory fall below the system target
1537 * this computes a reduced cap between the two hand limits supplied.
1538 * <p>
1539 * Always returns Integer.MAX_VALUE if maxCapacity is Integer.MAX_VALUE.
1540 */
1541 private int computeCapacityCap()
1542 {
1543 // Treat maxCapacity of Integer.MAX_VALUE as effectively 'unbounded'.
1544 if(maxCapacity == Integer.MAX_VALUE) { return(Integer.MAX_VALUE); }
1545
1546 // Adjust size cap in inverse proportion to heap shortage.
1547 final int pcFree = MemoryTools.percentFreeWithinTarget();
1548 if(pcFree < 1) // Dire shortage: minimise entry lifetime.
1549 { return(minSize); }
1550 if(pcFree > 99) // Loads of space: maximise entry lifetime.
1551 { return(maxCapacity); }
1552
1553 // Interpolate linearly (avoiding overflow).
1554 // As the percentage free goes up so does the maximum allowed size.
1555 final int sizeCap = (int)
1556 (((((long)pcFree) * maxCapacity) + ((100L - pcFree) * minSize)) / 100);
1557 assert((sizeCap >= minSize) && (sizeCap <= maxCapacity));
1558 return(sizeCap);
1559 }
1560
1561
1562 /**Get an entry from the map, making it the Most Recently Used; null if no such element. */
1563 public synchronized V get(final K key)
1564 {
1565 // Note the get() operation,
1566 // and rescale all values if getting relatively large.
1567 // (We must use >= since maxCapacity may be Integer.MAX_VALUE.)
1568 if(++countGets >= maxCapacity)
1569 { countGets >>>= 1; countGetMisses >>>= 1; }
1570
1571 final V result = lhm.get(key);
1572
1573 // Note any cache "miss"...
1574 if(result == null)
1575 {
1576 // Rescale counts here if they represent too long a history,
1577 // ie could prevent us reacting to changing usage patterns.
1578 final int size = lhm.size();
1579 if(++countGetMisses > Math.max(size >>> 1, trimCheckRate))
1580 { countGets >>>= 1; countGetMisses >>>= 1; }
1581 return(null);
1582 }
1583
1584 // Else throw away the oldest map entry
1585 // (on a small sampling of successful calls
1586 // to reduce the amortised cost and rate of map shrinkage)
1587 // but only if we have bettered the miss-rate target
1588 // or the system doesn't have lots of free memory
1589 // and the map is above its minimum size.
1590 else if(++cacheTrimTryCount > trimCheckRate)
1591 {
1592 // Reset count ready for next trim sample/attempt.
1593 cacheTrimTryCount = 0;
1594
1595 // Trim if memory is low/stressed.
1596 trimOldestEntryIfPossible(true);
1597 }
1598
1599 return(result);
1600 }
1601
1602 /**Create an instance with the given parameters.
1603 *
1604 * @param maxMissRate the target cache maximum miss rate;
1605 * in the range 0.0f to 1.0f exclusive (typically << 0.1)
1606 * @param minSize the minimum (and initial) capacity;
1607 * strictly positive
1608 * @param maxCapacity the maximum capacity;
1609 * greater than minCapacity (and this strictly positive)
1610 * @param loadFactor the load factor of the underlying hash table;
1611 * in the range 0.0f to 1.0f exclusive (typically ~0.7f)
1612 * @param name for memory-footprint tuning/debugging; may be null
1613 */
1614 public static <K,V> SimpleLRUMapAutoSizeForHitRate<K,V> create(final float maxMissRate, final int minSize, final int maxCapacity, final float loadFactor, final String name)
1615 {
1616 final SimpleLRUMapAutoSizeForHitRate<K,V> result = new SimpleLRUMapAutoSizeForHitRate<K,V>(maxMissRate, minSize, maxCapacity, loadFactor, name);
1617 registerCompactable(result);
1618 return(result);
1619 }
1620
1621 /**Trim oldest entries providing that the miss-rate target and minimum size are met.
1622 * This caps the size below the maximum if free heap space is below target.
1623 *
1624 * @param ignoreMissRateTarget if true, then ignore the miss-rate target when trimming.
1625 */
1626 private synchronized void trimOldestEntriesIfPossible(final boolean ignoreMissRateTarget, final boolean all)
1627 {
1628 if(ignoreMissRateTarget || meetingMissRateTarget())
1629 {
1630 final int cap = computeCapacityCap();
1631 while(lhm.size() > cap)
1632 {
1633 // Discard the oldest entry so as to trim the map size.
1634 final Iterator<Map.Entry<K,V>> it = lhm.entrySet().iterator();
1635 assert(it.hasNext());
1636 /* final Map.Entry<K,V> oldest = */ it.next();
1637 //if(IsDebug.isDebug) { System.out.println("[SimpleLRUMapAutoSizeForHitRate.get(): miss rate = "+(countGetMisses/(float)Math.max(1,countGets))+": size = "+lhm.size()+": trimming oldest entry: "+oldest+".]"); }
1638 it.remove();
1639 // If not trimming all items then stop here.
1640 if(!all) { break; }
1641 }
1642 }
1643 }
1644
1645 /**Trim (at most one) oldest entry providing that the miss-rate target and minimum size are met.
1646 * @param ignoreMissRateTarget if true, then ignore the miss-rate target when trimming.
1647 */
1648 private void trimOldestEntryIfPossible(final boolean ignoreMissRateTarget)
1649 { trimOldestEntriesIfPossible(ignoreMissRateTarget, false); }
1650
1651 /**Compact by discarding some or all LRU items above the minimum size, ignoring the miss-rate target.
1652 * Excessive use may reduce the effectiveness of this map.
1653 * <p>
1654 * May be automatically called in the background when memory is low/stressed.
1655 */
1656 public void compact()
1657 {
1658 if((size() > 0) && isMemoryStressed()) { System.err.println(this); } // Log data retention *before* emergency prune.
1659 trimOldestEntriesIfPossible(true, true);
1660 }
1661
1662 /**Put an entry in the map, making it the Most Recently Used, returning the previous value if any. */
1663 public synchronized V put(final K key, final V value)
1664 {
1665 final V result = lhm.put(key, value);
1666 // If memory is stressed then try hard to actually shrink this map.
1667 trimOldestEntryIfPossible(_isMemoryStressedQ());
1668 return(result);
1669 }
1670
1671 /**Remove an entry from the map and return the removed value, if any, else null. */
1672 public synchronized V remove(final K key) { return(lhm.remove(key)); }
1673
1674 /**Clear the map and reset the hit/miss counters. */
1675 public synchronized void clear() { lhm.clear(); countGets = 0; countGetMisses = 0; }
1676
1677 /**Return the number of entries in the map; non-negative. */
1678 public synchronized int size() { return(lhm.size()); }
1679
1680 /**Take a copy of the map contents, which does not alter LRU; never null. */
1681 public synchronized Map<K,V> getCopy() { return(new HashMap<K,V>(lhm)); }
1682
1683 /**Provide a human-readable summary of status.
1684 * Useful for debugging/tuning, for example.
1685 */
1686 @Override
1687 public String toString()
1688 {
1689 return("SimpleLRUMapAutoSizeForHitRate: name '"+name+"', miss rate "+(countGetMisses/(float)Math.max(1,countGets))+": size "+lhm.size()+", min|cap|max "+minSize+"|"+computeCapacityCap()+"|"+maxCapacity);
1690 }
1691 }
1692
1693
1694
1695 /**Enqueueable SoftReference for SoftReferenceConcurrentMap. */
1696 private final static class SRCMSoftReference<K, V> extends SoftReference<V>
1697 {
1698 /**Create an instance with the key and value (all non-null); only call from factory method. */
1699 SRCMSoftReference(final K key, final V value, final ReferenceQueue<V> refQ)
1700 {
1701 super(value, refQ);
1702 if(key == null) { throw new IllegalArgumentException(); }
1703 if(value == null) { throw new IllegalArgumentException(); }
1704 assert(refQ != null);
1705 this.key = key; // To help us know what to kill later...
1706 }
1707 /**Valid full exhibit name; never null. */
1708 final K key;
1709 }
1710
1711 /**Soft cache as highly-threadable (thread-safe) Map which holds each value via a SoftReference and discards mapping when the values are GCed.
1712 * Similar to a WeakHashMap in its automatic trimming of expired values,
1713 * and in that presence in this map does not prevent the values being GCed.
1714 * <p>
1715 * When values are GCed they will appear to vanish from the map asynchronously.
1716 * <p>
1717 * It is possible to safely iterate over the content with an iterator over the keySet
1718 * which will return elements reflecting the state of the keys in the Map
1719 * at some point at or since the creation of the iterator.
1720 * It does <em>not</em> throw {@link ConcurrentModificationException}.
1721 * However, iterators are designed to be used by only one thread at a time.
1722 * <p>
1723 * Permits neither null keys nor null values.
1724 * <p>
1725 * Not all operations (ie on the value or entry sets) are be supported.
1726 */
1727 public static final class SoftReferenceMap<K, V> implements Map<K, V>, Compactable
1728 {
1729 /**The internal map; never null. */
1730 private final ConcurrentMap<K, SRCMSoftReference<K, V>> m;
1731
1732 /**Queue of dead SoftReference entries; never null. */
1733 private final ReferenceQueue<V> _deadRefQueue = new ReferenceQueue<V>();
1734
1735 /**Optional name for diagnostics; can be null. */
1736 private final String name;
1737
1738 /**Compacts the representation of this collection if possible. */
1739 public void compact()
1740 {
1741 _clearDeadEntries();
1742 if(!m.isEmpty() && isMemoryStressed()) { System.err.println(this); }
1743 }
1744
1745 /**Provide a human-readable summary of status.
1746 * Useful for debugging/tuning, for example.
1747 */
1748 @Override
1749 public synchronized String toString()
1750 { return("SoftReferenceMap: name '"+name+"', size "+ m.size()); }
1751
1752 /**Expunges any dead entries.
1753 * This avoids races with replacement of values for keys just expired.
1754 * <p>
1755 * This should be called from enough places and/or otherwise often enough
1756 * to remove expired entries in a timely manner.
1757 */
1758 private void _clearDeadEntries()
1759 {
1760 SRCMSoftReference<K,V> dead;
1761 while(null != (dead = (SRCMSoftReference<K,V>) _deadRefQueue.poll()))
1762 {
1763 assert(dead.get() == null); // Reference is dead.
1764 // Iff this dead ref is still the entry for its key then atomically purge it...
1765 final boolean purged = m.remove(dead.key, dead);
1766 if(IsDebug.isDebug && purged) { System.out.println("SoftReferenceMap entry purged for key " + dead.key + ", map size now "+m.size()); }
1767 }
1768 }
1769
1770 /**Create an empty map with default characteristics.
1771 * Private to force use via factory method.
1772 */
1773 private SoftReferenceMap(final String name)
1774 {
1775 m = new ConcurrentHashMap<K, SRCMSoftReference<K, V>>();
1776 this.name = name;
1777 }
1778
1779 /**Create an empty map with the specified initial capacity.
1780 * Private to force use via factory method.
1781 * @param capacity initial capacity; strictly positive
1782 */
1783 private SoftReferenceMap(final int capacity, final String name)
1784 {
1785 m = new ConcurrentHashMap<K, SRCMSoftReference<K, V>>(capacity);
1786 this.name = name;
1787 }
1788
1789 /**Create an empty map with default characteristics.
1790 */
1791 public static <K, V> SoftReferenceMap<K, V> create(final String name)
1792 {
1793 final SoftReferenceMap<K, V> result = new SoftReferenceMap<K, V>(name);
1794 registerCompactable(result); // Allow externally-initiated run-time trimming when memory is low...
1795 return(result);
1796 }
1797
1798 /**Create an empty map with the specified initial capacity.
1799 * @param capacity initial capacity; strictly positive
1800 */
1801 public static <K, V> SoftReferenceMap<K, V> create(final int capacity, final String name)
1802 {
1803 final SoftReferenceMap<K, V> result = new SoftReferenceMap<K, V>(capacity, name);
1804 registerCompactable(result); // Allow externally-initiated run-time trimming when memory is low...
1805 return(result);
1806 }
1807
1808 public void clear() { _clearDeadEntries(); m.clear(); }
1809
1810 public boolean containsKey(final Object key) { _clearDeadEntries(); return(m.containsKey(key)); }
1811
1812 public int size() { _clearDeadEntries(); return(m.size()); }
1813
1814 public boolean isEmpty() { _clearDeadEntries(); return(m.isEmpty()); }
1815
1816 public Set<K> keySet() { _clearDeadEntries(); return(m.keySet()); }
1817
1818 public V get(final Object key)
1819 {
1820 _clearDeadEntries();
1821 final SoftReference<V> oldValueSR = m.get(key);
1822 return((null == oldValueSR) ? null : oldValueSR.get());
1823 }
1824
1825 public V put(final K key, final V value)
1826 {
1827 _clearDeadEntries();
1828 final SoftReference<V> oldValueSR = m.put(key, new SRCMSoftReference<K,V>(key, value, _deadRefQueue));
1829 return((null == oldValueSR) ? null : oldValueSR.get());
1830 }
1831
1832 public void putAll(final Map<? extends K, ? extends V> newValues)
1833 {
1834 _clearDeadEntries();
1835 for(final K key : newValues.keySet())
1836 { m.put(key, new SRCMSoftReference<K,V>(key, newValues.get(key), _deadRefQueue)); }
1837 }
1838
1839 public V remove(final Object key)
1840 {
1841 _clearDeadEntries();
1842 final SoftReference<V> oldValueSR = m.remove(key);
1843 return((null == oldValueSR) ? null : oldValueSR.get());
1844 }
1845
1846 public boolean containsValue(final Object value)
1847 {
1848 throw new UnsupportedOperationException(); // FIXME
1849 }
1850
1851 public Collection<V> values()
1852 {
1853 throw new UnsupportedOperationException(); // FIXME
1854 }
1855
1856 public Set<Entry<K, V>> entrySet()
1857 {
1858 throw new UnsupportedOperationException(); // FIXME
1859 }
1860 }
1861 }