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