001 /*
002 Copyright (c) 1996-2012, 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.io.BufferedOutputStream;
032 import java.io.FileOutputStream;
033 import java.io.IOException;
034 import java.io.OutputStream;
035 import java.lang.ref.SoftReference;
036 import java.lang.ref.WeakReference;
037 import java.util.ArrayList;
038 import java.util.Collection;
039 import java.util.Collections;
040 import java.util.Date;
041 import java.util.HashMap;
042 import java.util.Iterator;
043 import java.util.List;
044 import java.util.Map;
045 import java.util.Queue;
046 import java.util.Timer;
047 import java.util.TimerTask;
048 import java.util.WeakHashMap;
049 import java.util.concurrent.Callable;
050 import java.util.concurrent.ConcurrentLinkedQueue;
051 import java.util.concurrent.CopyOnWriteArrayList;
052 import java.util.concurrent.atomic.AtomicInteger;
053 import java.util.concurrent.atomic.AtomicReference;
054 import java.util.concurrent.locks.ReentrantLock;
055
056 import ORG.hd.d.IsDebug;
057
058
059 /**This contains utilities for memory intensive/sensitive operations.
060 * For example, this can veto or partly serialise memory-intensive
061 * operations such as image resizing in order to prevent the JVM
062 * running out of memory in a resource-constrained environment
063 * such as a Web server.
064 */
065 public final class MemoryTools
066 {
067 /**Prevent creation of instances of this class. */
068 private MemoryTools() { }
069
070 /**Used by (and private to) isMemoryStressed() to detect memory stress; never null.
071 * We use clearing of this reference as an indication of possible memory stress,
072 * or at least of fast memory turnover wrt the rate of poll of this value.
073 * <p>
074 * Marked volatile for thread-safe lock-free access.
075 */
076 private static volatile SoftReference<Object> _iMS_SR = new SoftReference<Object>(new Object());
077
078 /**Time of last check of _iMS_SR; the least significant bit indicates state detected.
079 * If the last bit is 1 it indicates that stress was detected, else none was.
080 * <p>
081 * Marked volatile for thread-safe lock-free access.
082 * <p>
083 * The initial state indicates that stress was not detected.
084 */
085 private static volatile long _iMS_lastCheck = System.currentTimeMillis() & ~1;
086
087 // /**Very quick non-blocking internal poll of stress state.
088 // * Only to be used internally,
089 // * and only valid if isMemoryStressed() is polled regularly.
090 // * <p>
091 // * Can be used to bias allocators, etc.
092 // * <p>
093 // * Can be used in a short-cut conditional such as
094 // * <code>(_isMemoryStressedQ() && isMemoryStressed())</code>
095 // * to avoid running the full-blown isMemoryStressed()
096 // * unless we were recently stressed,
097 // * ie is quick if not recently stressed
098 // * and doesn't give false positives.
099 // */
100 // private static boolean _isMemoryStressedQ()
101 // { return((_iMS_lastCheck & 1) != 0); }
102
103 /**Minimum interval for check/update of _iMS_SR in ms; strictly positive.
104 * If this is too small then the LRU mechanism that should be built into SoftReferences
105 * may mask all but the most severe shortage just before an OOM would have been thrown
106 * if isMemoryStressed() is being called very frequently.
107 * <p>
108 * We probably want to be able to detect milder stress than this,
109 * so a poll on the order of seconds is probably reasonable,
110 * but we try to avoid making this an obvious (sub-)multiple of any regular activity.
111 */
112 private static final int _IMS_CHECK_MS = 2111;
113
114 /**Returns true if the memory system may be under (great) stress, eg not enough free.
115 * This can help the application to avert a shortage by avoiding discretionary allocation,
116 * as well as in reacting to an unexpected shortage/stress.
117 * <p>
118 * This may work best if polled reasonably regularly.
119 * <p>
120 * This is likely to be at best stochastic,
121 * ie more likely to return true under severe memory stress,
122 * and less likely to return true when not under significant memory stress.
123 * <p>
124 * This checks the clearing of a SoftReference as one measure of memory stress:
125 * <ul>
126 * <li>On a system with plenty of free memory this should rarely/never be cleared.
127 * <li>On a system under severe memory stress this may be cleared frequently.
128 * </ul>
129 * <p>
130 * This also makes sure that at least a reasonable fraction of the current heap
131 * 'total' memory is reported as free.
132 * <p>
133 * This may attempt to initiate release of some memory asynchronously
134 * when it detects memory stress.
135 * <p>
136 * TODO: make use of MemoryPoolMXBean (etc) facilities for more robust detection.
137 */
138 public static final boolean isMemoryStressed()
139 {
140 // If it is too soon since we last polled our SoftReference to poll it again
141 // then return whatever 'stress' state we last observed.
142 final long now = System.currentTimeMillis();
143 final long lastCheck = _iMS_lastCheck;
144 if(now - lastCheck <= _IMS_CHECK_MS) { return((lastCheck & 1) != 0); }
145
146 // If our SoftReference has not been cleared
147 // and at least a reasonable fraction (~3%) of the current heap is free
148 // then we record/return that the memory system is apparently not currently stressed.
149 final Runtime r = Runtime.getRuntime();
150 // NOTE: always poll the SoftReference here to keep it 'live', regardless of other checks.
151 final boolean referenceOK = (_iMS_SR.get() != null);
152 final boolean notVeryLowOnMemory = r.freeMemory() > (r.totalMemory() >> 5);
153 if(referenceOK && notVeryLowOnMemory)
154 {
155 _iMS_lastCheck = now & ~1;
156 return(false);
157 }
158
159 // If our SoftReference has been cleared (or we are otherwise very low on memory)
160 // then we deduce that the memory subsystem is currently stressed,
161 // replace the SoftReference with a new (non-null) one if necessary,
162 // and record the 'is stressed' state bit along with the timestamp.
163 if(!referenceOK) { _iMS_SR = new SoftReference<Object>(new Object()); }
164 _iMS_lastCheck = now | 1; // Record the stress that we detected.
165 /* if(IsDebug.isDebug) */ { System.err.println("WARNING: memory subsystem under stress free/total/max "+TextUtils.sizeAsText(r.freeMemory(), true)+"/"+TextUtils.sizeAsText(r.totalMemory(), true)+"/"+TextUtils.sizeAsText(r.maxMemory(), true) + (referenceOK ? "" : " (SoftReferences cleared)" + " @ "+(new Date()))); }
166
167 // Attempt to initiate some memory release in the background.
168 // Also initiate emergency memory frees
169 // iff our soft reference was cleared AND we are low on free space.
170 // which indicates that the system probably is stressed.
171 // This avoids blocking the caller or doing anything intensive on their stack for example.
172 // This is started AFTER cacheing the 'stressed' state
173 // so that a recursive call (soon after) will find it and not have to recompute.
174 _emergencyTrimMemoryUseAsync(!referenceOK && !notVeryLowOnMemory);
175
176 return(true);
177 }
178
179 /**Target amount of free heap space (a decent fraction of current heap size).
180 * Small enough not to be rejected by _makeMemoryAvailable() outright,
181 * currently 25% of total heap size.
182 */
183 private static long _targetFreeMemory()
184 { return(Runtime.getRuntime().totalMemory() >> 2); }
185
186 /**True when there's currently lots of memory free and memory is not otherwise stressed.
187 * This takes into account reservations for memory-intensive operations,
188 * so may be over-conservative at times from double counting,
189 * but may provide a better view of 'availability' in the medium term.
190 */
191 public static boolean lotsFree()
192 {
193 return((Runtime.getRuntime().freeMemory() - Math.max(0, _rMIO_commitedBytes) > _targetFreeMemory()) &&
194 !isMemoryStressed());
195 }
196
197 /**Estimate of percentage of free space remaining as a fraction of the system target; in range[0,100].
198 * If at least the target amount of memory is free such that lotsFree() could be true
199 * then this returns 100.
200 * <p>
201 * Nominally, if less than 1% of the target amount of free space is available
202 * the this returns 0, though an OOME is likely before this is reached.
203 * <p>
204 * Lower numbers indicate increasing memory pressure.
205 *
206 * @return value in range zero to 100 inclusive with 0 indicating complete heap exhaustion
207 * and 100 indicating that there is a comfortable portion of heap left.
208 */
209 public static int percentFreeWithinTarget()
210 {
211 final long freeMemory = Runtime.getRuntime().freeMemory();
212 final long targetFreeMemory = _targetFreeMemory();
213 if(freeMemory >= targetFreeMemory) { return(100); } // Plenty of space.
214 // Compute result: overflow is currently unlikely...
215 return((int) ((100 * freeMemory) / targetFreeMemory)); // Conservatively rounds down.
216 }
217
218 /**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).
219 * All Compactable instances are held via WeakReference wrappers to avoid preventing their GC.
220 * <p>
221 * The Collection implementation is unbounded,
222 * should make insertion/deletion O(1),
223 * and must allow safe/sensible concurrent use of iterator() with other uses/modification
224 * and without throwing ConcurrentModificationException so that we can avoid any locking/blocking.
225 * <p>
226 * This is intended only to hold a smallish number of potentially-large collections/containers.
227 */
228 private static final Collection<WeakReference<Compactable>> _tMU_registered = new ConcurrentLinkedQueue<WeakReference<Compactable>>();
229
230 /**Allows a local Compactable instance to register itself.
231 * This is intended only to hold a smallish number of potentially-large collections/containers
232 * that may each be repeatedly compacted over time.
233 * <p>
234 * Should be largely wait-free.
235 * <p>
236 * This may fail to register an item during initialisation,
237 * but in any case no Compactable instance should rely on this to call compact()
238 * but should also be doing the equivalent itself, eg on most accessors as per WeakHashMap.
239 * <p>
240 * @param c fully-constructed non-null Compactable instance
241 */
242 public static final void registerCompactable(final Compactable c)
243 {
244 if(null == c) { throw new IllegalArgumentException(); }
245 // Safe to register concurrently with other activity...
246 _tMU_registered.add(new WeakReference<Compactable>(c));
247 }
248
249 /**If true then attempt to incrementally clear the _emergencyFreeQueue in the background.
250 * The aim is to prevent the _emergencyFreeQueue itself
251 * retaining memory uselessly when many items in it are dead.
252 */
253 private static final boolean INCR_HOUSEKEEP_EFQ = true;
254
255 /**Queue of one-shot entries that can be called in an emergency to free memory; never null.
256 * Entries are held by weak reference to ensure that they don't prevent GC.
257 * <p>
258 * Whenever we detect that memory is under great stress
259 * we work through this queue in order calling the target
260 * (unless the WeakReference has already expired, in which case we simply discard the entry).
261 * <p>
262 * We may periodically purge this queue of expired items
263 * to avoid it becoming a problem itself.
264 * <p>
265 * Anything that is called by this would need to re-register
266 * in order to be called again, ie on the next emergency.
267 * It is safe to re-register the same Runnable instance in such a case.
268 * <p>
269 * Thread-safe (and its iterators won't ever throw exceptions).
270 */
271 private static final Queue<WeakReference<Runnable>> _emergencyFreeQueue = new ConcurrentLinkedQueue<WeakReference<Runnable>>();
272
273 /**Queue up a handle to be called at most once to release memory on demand when detected to be very low.
274 * Entries are held by weak reference to ensure that they don't prevent GC.
275 * <p>
276 * Anything that is called by this would need to re-register
277 * in order to be called again, ie on the next emergency.
278 * It is safe to re-register the same Runnable instance in such a case,
279 * though registering multiple times would be inadvisable.
280 * <p>
281 * These handles should ideally run without blocking at all,
282 * or at least be quick and avoid deadlock.
283 * <p>
284 * Thread-safe.
285 */
286 public static void registerEmergencyFreeHandle(final Runnable r)
287 {
288 if(null == r) { throw new IllegalArgumentException(); }
289 final Queue<WeakReference<Runnable>> efq = _emergencyFreeQueue;
290
291 // Avoid a possible problem with recursive class initialisation...
292 if(null == efq) { return; }
293
294 // Quickly add the new handle...
295 efq.add(new WeakReference<Runnable>(r));
296 }
297
298 /**Interface for emergency-free handles expecting to be called zero-or-more times. */
299 public interface RecurrentEmergencyFreeHandle extends Runnable { }
300
301 /**Concurrent and thread-safe read-mainly store of permanent emergency-free callbacks; never null once class is initialised. */
302 private static final CopyOnWriteArrayList<WeakReference<RecurrentEmergencyFreeHandle>> _emergencyFreeQueueRecurrent = new CopyOnWriteArrayList<WeakReference<RecurrentEmergencyFreeHandle>>();
303
304 /**Queue up a handle to be called back as often as necessary to release memory on demand when detected to be very low.
305 * Entries are held by weak reference to ensure that they don't prevent GC,
306 * and need not unregister themselves but instead may simply be released to be GCed.
307 * <p>
308 * These entries need not and must not attempt to re-register themselves
309 * or be otherwise registered multiple times.
310 * <p>
311 * This tries very hard to make sure that any significant memory required
312 * is allocated (and thus may possibly fail) during registration
313 * rather than when attempting to actually use the callbacks,
314 * thus maximising the chance of working correctly!
315 * <p>
316 * These handles should ideally run without blocking at all,
317 * or at least be quick and avoid deadlock.
318 * <p>
319 * These are assumed to be added (and expire) infrequently.
320 * <p>
321 * Thread-safe.
322 */
323 public static void registerRecurrentEmergencyFreeHandle(final RecurrentEmergencyFreeHandle r)
324 {
325 if(null == r) { throw new IllegalArgumentException(); }
326 final List<WeakReference<RecurrentEmergencyFreeHandle>> efqr = _emergencyFreeQueueRecurrent;
327
328 // Avoid a possible problem with recursive class initialisation...
329 if(null == efqr) { throw new IllegalStateException("store not ready"); }
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 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 * and/or as a low-frequency event to do housekeeping when not memory stressed.
344 * <p>
345 * Doesn't force any emergency memory release,
346 * and indeed should actually be safe to call at any time if necessary.
347 * <p>
348 * Thread-safe: silently returns if routine already running (lock already held)
349 * or in the (unusual) case of the lock not yet initialised/set-up.
350 */
351 private static void _trimMemoryUse()
352 {
353 final ReentrantLock l = _tMU_lock;
354 if(null == l) { return; }
355
356 // Activity counter.
357 List<String> compacted = null;
358 int internableCount = -1;
359
360 if(!l.tryLock()) { return; }
361 try
362 {
363 // Try to trim dead Internable entries...
364 internableCount = heldInternableCount();
365
366 // Run pending finalizers if possible.
367 System.runFinalization();
368
369 // Trim fat from all registered Compactable instances.
370 // It is safe to do this concurrently with other activity
371 // (on the registered list and on the objects themselves)
372 // and no ConcurrentModificationException will be thrown.
373 compacted = new ArrayList<String>(32);
374 for(final Iterator<WeakReference<Compactable>> it = _tMU_registered.iterator(); it.hasNext(); )
375 {
376 final Compactable c = it.next().get();
377 if(null == c)
378 {
379 // Entry has expired and the instance has been GCed, so zap it...
380 it.remove();
381 continue;
382 }
383
384 // Compact the instance if possible.
385 c.compact(); // Note that this may block.
386 String compactableDetails = c.getCompactableInstanceName();
387 if(null == compactableDetails) { compactableDetails = "<"+c.getClass().getName()+">"; }
388
389 if(c instanceof CacheMiniMap)
390 {
391 if(((CacheMiniMap) c).size() == 0) { continue; } // Prune output...
392 compactableDetails += "(" + (((CacheMiniMap<?, ?>)c).size()) + ")";
393 }
394
395 compacted.add(compactableDetails);
396 }
397
398 if(INCR_HOUSEKEEP_EFQ)
399 {
400 final Queue<WeakReference<Runnable>> efq = _emergencyFreeQueue;
401
402 // Scan the (start of the) queue for dead items
403 // and stop as soon as we encounter a live one
404 // or when there's nothing left in the list.
405 // Helps keep the queue size down.
406 //
407 // Deliberately rotate the queue
408 // to expose 'dead' items further down the list.
409 WeakReference<Runnable> wrr;
410 while(null != (wrr = efq.poll()))
411 {
412 if(null != wrr.get())
413 {
414 // Found a live entry.
415 // Put it back on the end of the queue and stop!
416 efq.add(wrr);
417 break;
418 }
419 }
420
421 // Remove dead recurrent callbacks.
422 // Only do at most once each time as this will be expensive.
423 for(final WeakReference<RecurrentEmergencyFreeHandle> wrrr : _emergencyFreeQueueRecurrent)
424 {
425 if(wrrr.get() == null)
426 {
427 if(IsDebug.isDebug) { System.out.println("DEBUG: RecurrentEmergencyFreeHandle expired and removed, remaining: "+_emergencyFreeQueueRecurrent.size()); }
428 // Stop if we actually successfully pruned a dead item.
429 if(_emergencyFreeQueueRecurrent.remove(wrrr)) { break; }
430 }
431 }
432 }
433
434 System.currentTimeMillis();
435 }
436 /* Ensure that the lock is released. */
437 finally { l.unlock(); }
438
439 if((null != compacted) && !lotsFree())
440 {
441 System.err.println("WARNING: MemoryTools: trimmed memory use && !lotsFree(): compact()ed "+compacted.size()+", internableCount="+internableCount+", "+percentFreeWithinTarget()+"% target free heap @ "+(new Date()));
442 System.err.println("Registered Compactable instances(entries): "+compacted);
443 }
444 }
445
446 /**Private lock for _doEmergencyFree(); never null (except possibly during initialisation). */
447 private static final ReentrantLock _dEF_lock = new ReentrantLock();
448
449 /**Do emergency free/release of memory.
450 * Processes all non-recurrent items in the queue
451 * by draining it into another collection first
452 * then processing all the moved items.
453 * (This prevents items that re-register themselves
454 * from being re-run continuously!)
455 * <p>
456 * FIXME: danger of 'losing' handles if we get another OOM here while moving them around.
457 * <p>
458 * Thread-safe: silently returns (-1) if already running (lock already held)
459 * or in the (unusual) case of the lock not yet initialised/set-up.
460 */
461 private static int _doEmergencyFree()
462 {
463 final Queue<WeakReference<Runnable>> efq = _emergencyFreeQueue;
464 final CopyOnWriteArrayList<WeakReference<RecurrentEmergencyFreeHandle>> efqr = _emergencyFreeQueueRecurrent;
465
466 // Avoid a possible problem with recursive class initialisation...
467 if((null == efq) || (null == efqr)) { return(0); }
468
469 final ReentrantLock l = _dEF_lock;
470 if(null == l) { return(-1); }
471 if(!l.tryLock()) { return(-1); }
472 try {
473 // Do all the recurrent/permanent ones first...
474 int recurrentsDone = 0;
475 for(final WeakReference<RecurrentEmergencyFreeHandle> wrrr : efqr)
476 {
477 // Attempt to prune...
478 final RecurrentEmergencyFreeHandle refh = wrrr.get();
479 if(refh == null) { continue; } // Don't attempt to free dead handle here...
480 System.err.println("About to run RecurrentEmergencyFreeHandle " + refh);
481 try { refh.run(); }
482 // Absorb but report all errors encountered.
483 catch(final Throwable t) { t.printStackTrace(); }
484 ++recurrentsDone;
485 }
486
487 int nonRecurrentsDone = 0;
488 if(null != efq.peek())
489 {
490 // Move to a working List (dropping any dead ones in passing)
491 // all the registered non-recurrent 'emergency free' handles.
492 final List<Runnable> toProcess = new ArrayList<Runnable>();
493 WeakReference<Runnable> wrr;
494 while(null != (wrr = efq.poll()))
495 {
496 final Runnable r = wrr.get();
497 if(r == null) { continue; }
498 toProcess.add(r);
499 }
500
501 // Call all the 'emergency free' handles that we saved above..
502 for(final Runnable r : toProcess)
503 {
504 System.err.println("About to run non-recurrent emergency free handle " + r);
505 try { r.run(); }
506 // Absorb but report all errors encountered.
507 catch(final Throwable t) { t.printStackTrace(); }
508 ++nonRecurrentsDone;
509 }
510 }
511
512 final int freed = nonRecurrentsDone + recurrentsDone;
513 if(freed != 0)
514 { System.err.println("WARNING: MemoryTools: emergency frees processed: "+freed+" ("+recurrentsDone+" recurrent) @ "+(new Date())); }
515
516 return(freed);
517 }
518 finally { l.unlock(); }
519 }
520
521 /**Used to ensure that a small fraction of the time _trimMemoryUse() calls are made even without memory stress. */
522 private static final AtomicInteger _tMU_count = new AtomicInteger();
523
524 /**Timer used to process _emergencyTrimMemoryUseAsync() activity; never null.
525 * Runs as a daemon to allow the JVM to exit.
526 * <p>
527 * Avoids having more than one Thread run this concurrently.
528 * <p>
529 * We may also run other periodic memory-management tasks with this timer.
530 * TODO: move expensive/periodic checks to this so that isMemoryStressed() calls all just poll a volatile flag
531 */
532 private static final Timer _eTMUATimer = new Timer("Emergency Memory-Trim Timer", true);
533 /**Interval between attempts to keep target memory free, ms, strictly positive. */
534 private static final int TARGET_FREE_FORCE_POLL_MS = 121000; // ~2 minutes.
535 /**Set up a periodic timer to try to maintain the target amount of free heap. */
536 static
537 {
538 // Schedule task to start ASAP.
539 _eTMUATimer.schedule(new TimerTask(){
540 @Override public void run()
541 {
542 // Usually return immediately if lotsFree(),
543 // but occasionally run anyway to do some preemptive housekeeping.
544 if((0 != (_tMU_count.incrementAndGet() & 7)) && lotsFree()) { return; }
545 // Didn't have lots of memory free so try to gently liberate some memory.
546 try { _trimMemoryUse(); }
547 catch(final Throwable t) { t.printStackTrace(); } // Log error, but absorb it to protect Timer.
548 }
549 }, TARGET_FREE_FORCE_POLL_MS/2, TARGET_FREE_FORCE_POLL_MS);
550 }
551
552 /**Run _trimMemoryUse(), _doEmergencyFree() if requested plus forced GC, asynchronously.
553 * @param doEmergencyFree if true then call the emergency-free handlers and possibly force GC
554 */
555 private static void _emergencyTrimMemoryUseAsync(final boolean doEmergencyFree)
556 {
557 // Schedule task to start ASAP.
558 _eTMUATimer.schedule(new TimerTask(){
559 @Override public void run()
560 {
561 try
562 {
563 _trimMemoryUse(); // Do gentler stuff first that may also yield useful diagnostics.
564 if(doEmergencyFree)
565 { _doEmergencyFree(); } // Now the nuclear option...
566 preemptiveGC(); // Now try to force some space to be *visibly* free.
567
568 final Runtime r = Runtime.getRuntime();
569 /* 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())); }
570 }
571 catch(final Throwable t) { t.printStackTrace(); } // Log error, but absorb it to protect Timer.
572 }
573 }, 0);
574 }
575
576
577 /**If true, only allows one memory-intensive operation to run at once.
578 * This reduces the chance of blowing up the heap,
579 * in return for reducing concurrency on multi-CPU machines.
580 * <p>
581 * We must not hold a lock to enforce this as doing so may cause deadlock;
582 * we veto any concurrent call immediately when true.
583 */
584 private static final boolean NO_MEM_INTENSIVE_CONCURRENCY = true;
585
586 /**Attempt to make sure that the specified amount of memory is available; return true if so.
587 * If this cannot be done
588 * (eg the requested space is apparently not available,
589 * or it is too soon since the last GC to try to force another full GC)
590 * then this returns false.
591 * <p>
592 * This does not hold any locks.
593 * <p>
594 * We try very hard to avoid actually calling System.gc()
595 * as doing so may upset the ergonomics of almost any GC implementation,
596 * and in particular is quite likely to result in an unwanted long stop-the-world pause.
597 *
598 * @param bytes approximate number of bytes of heap free required; non-negative
599 *
600 * @return true if requested memory is apparently available, false if not available
601 */
602 private static boolean _makeMemoryAvailable(final long bytes)
603 {
604 assert(bytes >= 0);
605
606 final Runtime runtime = Runtime.getRuntime();
607
608 // If the request is less than is currently free
609 // then return true immediately.
610 // Optimisation: we hope that this (short) path will be the usual one.
611 final long freeMemoryInitial = runtime.freeMemory();
612 if(bytes <= freeMemoryInitial) { return(true); }
613
614 // If the request is more than could ever reasonably be available for one purpose
615 // (which we take to be half the maximum heap size, if specified)
616 // then return false immediately.
617 // No point in even trying if this is true...
618 if(bytes >= runtime.maxMemory() >> 1) { return(false); }
619
620
621 // Time before we start any System.gc().
622 final long beforeGC = System.currentTimeMillis();
623
624 // Find out if it is long enough since our last call to System.gc().
625 //
626 // If not then return false immediately to avoid pointlessly thrashing the memory system.
627 if(_rMIO_noGCBefore > beforeGC) { return(false); }
628
629 // Loop to free up memory if necessary, if we can.
630 // The number of iterations is limited.
631 for(int i = _rMIO_MAX_GC_CALLS; --i >= 0; )
632 {
633 // Note time of System.gc() and prep work on this round.
634 final long beforeCurrentGCRound = System.currentTimeMillis();
635
636 // Try some relatively-gentle things first that may help GC,
637 // and that may liberate a little memory immediately.
638 _trimMemoryUse();
639
640 // Force finalize()rs to run while we are at it,
641 // since it might release other resources.
642 // This may also force us to see more of real GC costs.
643 System.runFinalization();
644
645 // If the request is less than is currently/now free
646 // then return true immediately.
647 if(bytes < runtime.freeMemory()) { return(true); }
648
649 // If the request is less than *could* be allocated given maxMemory() and space already in use,
650 // then return true immediately.
651 // But we only trust maxMemory() if it is something less/other than Long.MAX_VALUE.
652 final long maxMemory = runtime.maxMemory();
653 if((maxMemory != Long.MAX_VALUE) &&
654 (bytes < (maxMemory - (runtime.totalMemory() - runtime.freeMemory()))))
655 { return(true); }
656
657 // OK, really try to force some GC.
658 // This may be entirely ignored...
659 final long freeMemoryBeforeGC = runtime.freeMemory();
660 System.err.println("MemoryTools: running System.gc() with free memory "+freeMemoryBeforeGC+"...");
661 System.gc();
662 final long freeMemoryAfterGC = runtime.freeMemory();
663 // Did it seem to work? (May be illusory even if so.)
664 final boolean worked = (freeMemoryAfterGC > freeMemoryBeforeGC);
665
666 // Postpone the next use of GC by any other caller.
667 final long now = System.currentTimeMillis();
668 final long notBefore =
669 now + Math.max((worked ? MIN_WAIT_AFTER_GC : MIN_WAIT_AFTER_FAILED_GC),
670 ((now - beforeCurrentGCRound) * _rMIO_MAX_GC_FRAC));
671 // Attempt to ensure that we only put the "not-before" time forwards
672 // since there may be other concurrent updaters of this value,
673 // though it is not vital to get it precisely right
674 // (residual races are safe since _rMIO_noGCBefore is volatile and thus accesses are atomic).
675 _rMIO_noGCBefore = Math.max(_rMIO_noGCBefore, notBefore);
676
677 // Stop if apparently unsuccessful in liberating more space.
678 if(!worked) { break; }
679 }
680
681 final boolean succeeded = bytes < runtime.freeMemory(); // Test again...
682 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())+"."); }
683 return(succeeded); // Failed to free up enough memory...
684 }
685
686 /**Wrapper round runMemoryIntensiveOperation(Runnable, ...) for value-returning tasks that must always be run.
687 * Returns a pair of a Boolean (true if the task ran, false if not)
688 * and the value returned by the Callable (always false if the task is not run).
689 *
690 * @throws Exception any exception thrown by the Callable or our handler routine
691 */
692 public static <V, E extends Exception> V runMemoryIntensiveOperation(
693 final Callable<V> task,
694 final int estimatedMinBytesRequired)
695 throws Exception
696 {
697 final AtomicReference<Exception> ex = new AtomicReference<Exception>();
698 final AtomicReference<V> v = new AtomicReference<V>();
699 final boolean ran = runMemoryIntensiveOperation((new Runnable(){
700 public void run()
701 {
702 try { v.set(task.call()); }
703 catch(final Exception e) { ex.set(e); }
704 }
705 }),
706 true,
707 estimatedMinBytesRequired);
708
709 // Rethrow any Exception generated.
710 final Exception e = ex.get();
711 if(null != e) { throw e; }
712 // Handle the case where the task was not run...
713 assert(ran) : "task must be run";
714 // All OK, return the result...
715 return(v.get());
716 }
717
718 /**Wrapper round runMemoryIntensiveOperation(Runnable, ...) for value-returning tasks.
719 * Returns a pair of a Boolean (true if the task ran, false if not)
720 * and the value returned by the Callable (always false if the task is not run).
721 *
722 * @throws Exception any exception thrown by the Callable or our handler routine
723 */
724 public static <V> Tuple.Pair<Boolean, V> runMemoryIntensiveOperation(
725 final Callable<V> task,
726 final boolean unlimitedMemory,
727 final int estimatedMinBytesRequired)
728 throws Exception
729 {
730 final AtomicReference<Exception> ex = new AtomicReference<Exception>();
731 final AtomicReference<V> v = new AtomicReference<V>();
732 final boolean ran = runMemoryIntensiveOperation((new Runnable(){
733 public void run()
734 {
735 try { v.set(task.call()); }
736 catch(final Exception e) { ex.set(e); }
737 }
738 }),
739 unlimitedMemory,
740 estimatedMinBytesRequired);
741
742 // Rethrow any Exception generated.
743 final Exception e = ex.get();
744 if(null != e) { throw e; }
745 // Handle the case where the task was not run...
746 if(!ran) { return(new Tuple.Pair<Boolean, V>(Boolean.FALSE, null)); }
747 // All OK, return the result...
748 return(new Tuple.Pair<Boolean, V>(Boolean.TRUE, v.get()));
749 }
750
751
752 /**Run (or veto by refusing to run) a memory-intensive operation.
753 * This is passed a task to be run,
754 * with an estimate of the amount of extra memory required to run it.
755 * <p>
756 * The task is run, possibly after a delay,
757 * if resources seem to be available for it,
758 * and this routine returns true.
759 * <p>
760 * If sufficient resource (ie memory) does not seem to be available,
761 * then the task is not return and this routine returns false.
762 * <p>
763 * This routine may attempt to free memory by calling System.gc() one
764 * or more times, but because this may be slow and may impact system
765 * performance (eg concurrency) badly, this waits a significant
766 * multiple of the time taken to perform GC between such attempts,
767 * so this routine may refuse to try to free memory for a task even if
768 * it would work.
769 * <p>
770 * This keeps a static variable to track memory use between separate
771 * (concurrent) callers and is thus implicitly counting memory shared
772 * in this JVM or class loader. This routine tries to be robust enough
773 * to work reasonably well even with multiple separate copies of this
774 * class in separate class loaders within one JVM.
775 * <p>
776 * If the unlimitedMemory parameter is true then the task is
777 * always run immediately, and can be used for testing and for
778 * situations where heap space is freely available, eg the heap
779 * may be easily expanded.
780 * <p>
781 * No checked exception is propagated to the caller,
782 * but a non-checked exception may be.
783 * <p>
784 * This routine holds no lock for its duration to avoid deadlocks,
785 * but may "baulk" at (ie refuse to run) concurrent calls so as to limit concurrency.
786 *
787 * @param task the task to be run
788 * @param estimatedMinBytesRequired estimate of peak number of bytes
789 * of heap that the task will use (overestimate rather than
790 * underestimate this value); must be non-negative
791 * @param unlimitedMemory if true, the task is always run
792 * on the assumption that at the moment resources are effectively
793 * unlimited (or at least that this task must be run)
794 * but other memory-intensive tasks may be denied
795 * @return true if the task was run,
796 * false if it was not run because of apparent memory shortage
797 * or because too many other memory-intensive tasks are running
798 *
799 * @throws IllegalArgumentException if the task is null or
800 * a negative amount of memory is specified
801 * @throws IllegalStateException if too much aggregate memory
802 * is being requested between all the concurrent tasks
803 */
804 public static boolean runMemoryIntensiveOperation(
805 final Runnable task,
806 final boolean unlimitedMemory,
807 final int estimatedMinBytesRequired)
808 throws IllegalArgumentException,
809 IllegalStateException
810 {
811 if((task == null) ||
812 (estimatedMinBytesRequired < 0))
813 { throw new IllegalArgumentException(); }
814
815 // Our (possibly inflated) view of the actual memory to set aside.
816 // We have to do whole calculation as a long to avoid overflow
817 // on extreme values.
818 //
819 // We ensure that this is positive,
820 // which ensures that our view of committed memory
821 // will always be positive when at least one
822 // memory-intensive task is running.
823 final long inflatedMemoryEstimate = 1L + ((_rMIO_FREE_MEM_MULT == 1) ?
824 estimatedMinBytesRequired :
825 (estimatedMinBytesRequired * (long) _rMIO_FREE_MEM_MULT));
826
827 // Adjust the committed memory on the way in atomically
828 // (and keep a copy of that new value).
829 // We will release it at the end of the following try/finally.
830 final long committedBytes;
831 synchronized(_rMIO_lock)
832 {
833 if(NO_MEM_INTENSIVE_CONCURRENCY && !unlimitedMemory &&
834 (_rMIO_commitedBytes > 0))
835 { return(false); } // Fail immediately; another in progress.
836
837 committedBytes =
838 (_rMIO_commitedBytes += inflatedMemoryEstimate);
839 }
840 // Release committed memory at the end of this try block...
841 try
842 {
843 // If committedBytes was so huge that our total has wrapped,
844 // then refuse to run this task and undo the change.
845 if(committedBytes <= 0)
846 { throw new IllegalStateException(); }
847
848 // If we have unlimited memory
849 // then always run the task.
850 if(unlimitedMemory)
851 {
852 task.run();
853 return(true); // Ran the task!
854 }
855
856 // If we can't make the memory available then give up and don't run the task.
857 // We allow for memory already committed but possibly not yet allocated
858 // (ie in outer calls where this call is nested).
859 if(!_makeMemoryAvailable(committedBytes))
860 { return(false); }
861
862 // Got the memory: run task!
863 // Yeah baby, yeah!
864 task.run();
865 return(true); // Ran the task.
866 }
867 finally
868 {
869 // Release the committed memory for this task on the way out...
870 synchronized(_rMIO_lock)
871 { _rMIO_commitedBytes -= inflatedMemoryEstimate; }
872 }
873 }
874
875
876 /**Bytes of memory ``committed'' to runMemoryIntensiveOperation(); non-negative.
877 * Private to runMemoryIntensiveOperation() and accessed by it under
878 * the _rMIO_lock lock.
879 * <p>
880 * Also used by lotsFree() to make more conservative estimates of availability.
881 * <p>
882 * Initially zero.
883 * <p>
884 * Marked volatile for lock-free thread-safe access.
885 */
886 private static volatile long _rMIO_commitedBytes;
887
888 /**Time before which System.gc() should not be retried; private to _makeMemoryAvailable().
889 * Based on how long was spent running System.gc() on a previous
890 * attempt, this prevents system resources being significantly
891 * impacted by us continually running System.gc().
892 * <p>
893 * Initialised with 'now' to postpone the first attempt to force GC.
894 * <p>
895 * Is volatile to allow it to be read/written safely without a lock.
896 */
897 private static volatile long _rMIO_noGCBefore = System.currentTimeMillis();
898
899 /**Private lock for runMemoryIntensiveOperation(). */
900 private static final Object _rMIO_lock = new Object();
901
902 /**Maximum fraction of wall-clock time we will spend forcing GC; strictly positive.
903 * If this is N we will spend at most 1/(1+N) of wall-clock time
904 * explicitly running System.gc().
905 * <p>
906 * TODO: we might additionally abort if we've spent more than some
907 * fixed time, eg 30s, trying to collect garbage already.
908 * <p>
909 * This is used to limit impact on global system performance.
910 * <p>
911 * A value between 10 and 100 is probably reasonable.
912 */
913 private static final int _rMIO_MAX_GC_FRAC = 11;
914
915 /**Minimum time before attempting forced GC after previous attempt (ms); strictly positive.
916 * This can save us from churning the heap too hard,
917 * or wasting time when System.gc() does nothing at all.
918 * <p>
919 * This can be a few seconds through to a few minutes.
920 */
921 private static final int MIN_WAIT_AFTER_GC = 8192 + Rnd.fastRnd.nextInt(1024);
922
923 /**Minimum time before attempting forced GC after previous failed attempt (ms); strictly positive.
924 * This can save us from churning the heap too hard,
925 * or wasting time when System.gc() does nothing at all.
926 * <p>
927 * This can be a few seconds through to a few minutes.
928 */
929 private static final int MIN_WAIT_AFTER_FAILED_GC = 2*MIN_WAIT_AFTER_GC + 25000;
930
931 /**Maximum number of times that we will call System.gc() to free memory; strictly positive.
932 * This is per call to runMemoryIntensiveOperation();
933 * we may do less than this.
934 * <p>
935 * It may be worth calling System.gc() more than once because it may
936 * in fact take several passes in some JVMs to liberate all the
937 * heap from several different heap areas and across several threads,
938 * but calling it lots of times is probably just a huge drain on system
939 * resources or may simply be ignored by the JVM.
940 * <p>
941 * A value from 1 to 3 inclusive is probably good.
942 */
943 private static final int _rMIO_MAX_GC_CALLS = 2;
944
945 /**Multiple of excess free memory there should be before attempting memory-intensive task; strictly positive.
946 * Bigger numbers are more conservative and reduce the probability
947 * of a crash due to running out of memory, but increase the
948 * chance of not running such as task when we otherwise could.
949 * <p>
950 * If we eliminate concurrency between memory-intensive operations
951 * then we can be less conservative than we otherwise would be,
952 * and indeed can possibly drop this down to 1.
953 * <p>
954 * A value in the range 1--4 is probably good.
955 */
956 private static final int _rMIO_FREE_MEM_MULT =
957 NO_MEM_INTENSIVE_CONCURRENCY ? 1 : 2;
958
959
960 /**Request a preemptive garbage collection, for example while the system is (too) quiet.
961 * This request may be ignored (eg if too soon after a previous one)
962 * and the system may ignore any attempts made here,
963 * or may do it asynchronously, or may do a partial GC.
964 * <p>
965 * This should be called when the system seems to be idle
966 * (in terms of human user, eg Web site visitor, activity)
967 * and is likely to idle for (say) a minute or so,
968 * to allow us to slip in a full GC run while no one is looking,
969 * so as we can last as long as possible without an intrusive
970 * GC when the system <em>is</em> in use later.
971 * This may help recover from (for example) leaked file handles
972 * preventing any clients contacting us.
973 * <p>
974 * An alternative use is when we can't see
975 * a comfortable margin of free memory
976 * (possibly even though we've just trimmed significant fat)
977 * and we want to try to force such a margin to be visibly free.
978 *
979 * @return true if we apparently managed to free up some memory, else false
980 */
981 public static boolean preemptiveGC()
982 {
983 final Runtime runtime = Runtime.getRuntime();
984
985 // Do some safe non-destructive trimming...
986 _trimMemoryUse();
987
988 // Always run finalizers where possible
989 // since this should be reasonably quick
990 // and may release some orphaned resources
991 // including non-memory resources such as file handles.
992 runtime.runFinalization();
993
994 // Our target is to have about one quarter of the heap free,
995 // which suggests an efficient and relatively-unstressed system.
996 // This is 'lotsFree()'.
997 final long targetFree = _targetFreeMemory();
998 if(runtime.freeMemory() > targetFree) { return(false); }
999
1000 // If we did not have our target memory free
1001 // then push to get more free()d up to get some hysteresis and less churn.
1002 // This may invoke System.gc().
1003 if(!_makeMemoryAvailable(targetFree))
1004 { return(false); } // Didn't manage to do much useful...
1005
1006 System.out.println("[MemoryTools.preemptiveGC(): free="+
1007 TextUtils.sizeAsText(runtime.freeMemory(), true)+"/"+
1008 TextUtils.sizeAsText(runtime.totalMemory(), true)+"/"+
1009 TextUtils.sizeAsText(runtime.maxMemory(), true)+", "+
1010 "free within target ~ "+percentFreeWithinTarget()+"%.]");
1011 return(true);
1012 }
1013
1014
1015
1016 /**Marker interface indicating class is suitable for deduping by intern().
1017 * Any class implementing this interface must be immutable,
1018 * and must have working equals() and hashCode() methods.
1019 */
1020 public static interface Internable { }
1021
1022
1023 /**Marker interface indicating that an instance may 'auto-expire'.
1024 * This indicates that an item in a container can be spontaneously removed,
1025 * ie 'evaporate' like dead entries in a WeakHashMap.
1026 * <p>
1027 * This interface need not be restricted to container management.
1028 * <p>
1029 * Calling methods on this interface should be thread-safe and relatively cheap,
1030 * eg so that they can be called asynchronously from a background thread,
1031 * and should not take externally-visible locks (ie risk deadlock).
1032 */
1033 public static interface AutoExpirable
1034 {
1035 /**If true this item has expired, and may for example be ripe for removal from a container.
1036 * Generally does not become false for a given instance once true,
1037 * though may do so if resources become less constrained for example.
1038 * @return true if beyond sell-by date.
1039 */
1040 public boolean hasExpired();
1041 }
1042
1043 /**Base class for AutoExpirable with a fixed lifetime after construction.
1044 * Is 'intrusive' as a base to avoid overhead of extra wrapper class layer...
1045 * <p>
1046 * Is itself immutable after construction.
1047 */
1048 public static abstract class AutoExpirableFixedLifeBase implements AutoExpirable
1049 {
1050 /**Expiry time, absolute Java ms. */
1051 protected final long expiresAt;
1052 /**Construct instance with lifetime measured in ms.
1053 * @param msLifetime nominally-positive lifetime from now; non-positive value causes immediate expiry
1054 * Use of 'int' parameter avoids need to check value
1055 * as damaging overflow not really possible for example,
1056 * and an 'auto' expiry of well over 200 days is already pushing it!
1057 */
1058 protected AutoExpirableFixedLifeBase(final int msLifetime)
1059 { expiresAt = System.currentTimeMillis() + msLifetime; }
1060 /**Expires at or beyond stored deadline. */
1061 public boolean hasExpired()
1062 { return(System.currentTimeMillis() >= expiresAt); };
1063 }
1064
1065 /**Marker interface indicating that a class is suitable for compacting in memory.
1066 * Generally the single compact() method should not change the logical state,
1067 * nor should it consume lots of resources if avoidable
1068 * (eg lots of memory, or lots of CPUs)
1069 * and may call Thread.yield() periodically,
1070 * and by the time it returns all compact()ion activity has completed
1071 * (ie this will not launch background threads to do the work,
1072 * though may often be launched from one).
1073 * <p>
1074 * Calling the compact() method should be thread-safe,
1075 * ie so we can do it asynchronously from a background thread if we wish,
1076 * for example when we detect system memory to be under stress.
1077 * <p>
1078 * The compact() entry point may be called periodically even when there is no memory shortage,
1079 * to help trim expired elements from collections (eg dead AutoExpirable instances).
1080 */
1081 public static interface Compactable
1082 {
1083 /**Attempt to compact the data structure, possibly sensitive to current heap state. */
1084 void compact();
1085 /**Get instance name; may be null. */
1086 String getCompactableInstanceName();
1087 }
1088
1089 /**If true then force single-CPU mode. */
1090 private static final boolean FORCE_SINGLE_CPU_MODE = false;
1091
1092 /**If true then run in single-CPU mode to save some space and time overheads by giving up some concurrency. */
1093 private static final boolean SINGLE_CPU_MODE = FORCE_SINGLE_CPU_MODE || (ThreadUtils.AVAILABLE_PROCESSORS == 1);
1094
1095 /**Power of maximum concurrency available in intern(); non-negative (0 in single-CPU mode). */
1096 private static final int MAX_INTERN_CONC_POWER = SINGLE_CPU_MODE ? 0 : 6;
1097
1098 /**Private to intern(): for holding Internable values; never null nor zero-size nor containing nulls.
1099 * Each map must be accessed only under a lock on that map to serialise access
1100 * as WeakHashMap is not itself thread-safe.
1101 * <p>
1102 * Unless in SINGLE_CPU mode we have many (low-load-factor) maps
1103 * to usually allow concurrent (and fast) intern() operations.
1104 * <p>
1105 * We assume that SINGLE_CPU systems typically have smaller heaps than otherwise.
1106 */
1107 private static final WeakHashMap<Internable, WeakReference<Internable>>[] WHM_Internables =
1108 GenUtils.<WeakHashMap<Internable, WeakReference<Internable>>[]>cast(new WeakHashMap[1 << MAX_INTERN_CONC_POWER]);
1109 /**Private to intern(); reference to 0 element of WHM_Internables as optimisation for single-CPU systems; never null. */
1110 private static final WeakHashMap<Internable, WeakReference<Internable>> WHM_Internables_0;
1111 /**Initialise WHM_Internables and WHM_Internables_0. */
1112 static
1113 {
1114 // Aim for an initial total capacity of ~16K (~300K is a normal total working capacity @20100711).
1115 final int subMapInitialCapacity = Math.max(128, (1<<14) >>> MAX_INTERN_CONC_POWER);
1116 for(int i = WHM_Internables.length; --i >= 0; )
1117 { WHM_Internables[i] = new WeakHashMap<Internable, WeakReference<Internable>>(subMapInitialCapacity, SINGLE_CPU_MODE ? 0.85f : 0.75f); }
1118 WHM_Internables_0 = WHM_Internables[0];
1119 }
1120
1121 /**Get current number of Internable items held, and purge any dead entries too. */
1122 private static int heldInternableCount()
1123 {
1124 int totalSize = 0;
1125 for(int i = WHM_Internables.length; --i >= 0; )
1126 {
1127 final WeakHashMap<Internable, WeakReference<Internable>> WHM_Internable = WHM_Internables[i];
1128 synchronized(WHM_Internable)
1129 { totalSize += WHM_Internable.size(); }
1130 }
1131 return(totalSize);
1132 }
1133
1134 /**Return map of counts of Internable classes held; never null though may be empty.
1135 * Diagnostic only; most likely disabled in non-debug builds for security and performance reasons.
1136 * <p>
1137 * Will likely be fairly expensive and lock out some intern() operations for noticeable time.
1138 * <p>
1139 * The results should not be held longer than necessary to avoid blocking class GC, etc.
1140 */
1141 public static Map<Class<? extends Internable>, Integer> _heldInternablesByClass()
1142 {
1143 // Return an empty map when not in debug mode.
1144 if(!IsDebug.isDebug) { return(Collections.emptyMap()); }
1145
1146 final Map<Class<? extends Internable>, Integer> result = new HashMap<Class<? extends Internable>, Integer>();
1147
1148 for(int i = WHM_Internables.length; --i >= 0; )
1149 {
1150 final WeakHashMap<Internable, WeakReference<Internable>> WHM_Internable = WHM_Internables[i];
1151 synchronized(WHM_Internable)
1152 {
1153 for(final Internable key : WHM_Internable.keySet())
1154 {
1155 final Class<? extends Internable> c = key.getClass();
1156 final Integer count = result.get(c);
1157 if(null == count) { result.put(c, Integer.valueOf(1)); }
1158 else { result.put(c, Integer.valueOf(1 + count.intValue())); }
1159 }
1160 }
1161 }
1162
1163 return(result);
1164 }
1165
1166 /**Dump Internable Name instances held, one per line, to an ASCII file; never null though may be empty.
1167 * Diagnostic only; most likely disabled in non-debug builds for security and performance reasons.
1168 * <p>
1169 * Will likely be fairly expensive and lock out some intern() operations for noticeable time.
1170 * <p>
1171 * Is deadlock-safe for Name.
1172 */
1173 public static void _heldNameInstancesDump()
1174 {
1175 // Return immediately when not in debug mode.
1176 if(!IsDebug.isDebug) { return; }
1177
1178 // Try to clear spurious references first...
1179 System.gc();
1180
1181 try
1182 {
1183 final OutputStream os = new BufferedOutputStream(new FileOutputStream(".interned.Name.dump.txt"));
1184 try
1185 {
1186 for(int i = WHM_Internables.length; --i >= 0; )
1187 {
1188 final WeakHashMap<Internable, WeakReference<Internable>> WHM_Internable = WHM_Internables[i];
1189 synchronized(WHM_Internable)
1190 {
1191 for(final Internable key : WHM_Internable.keySet())
1192 {
1193 final Class<? extends Internable> c = key.getClass();
1194 if(c != Name.class) { continue; }
1195 final Name n = (Name) key;
1196 final int length = n.length();
1197 // Sanitize any non-printable, non-ASCII characters.
1198 for(int index = 0; index < length; ++index)
1199 {
1200 final byte b = n.byteAt(index);
1201 if((b < 32) || (b >= 127)) { os.write('?'); }
1202 else { os.write(b); }
1203 }
1204 os.write('\n');
1205 }
1206 }
1207 }
1208 }
1209 finally
1210 { os.close(); }
1211 }
1212 catch(final IOException e)
1213 { e.printStackTrace(); } // Log error but absorb it.
1214 }
1215
1216 /**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. */
1217 private static final boolean _USE_STRING_INTERN = true;
1218
1219 /**Strings no longer than this use our storage rather than String.intern().
1220 * If this threshold is less than Integer.MAX_VALUE
1221 * then this has the effect of keeping big Strings out of the PermGen in Sun's JVMs,
1222 * which probably would not meld with any JVM-intern()ed value anyway.
1223 * Avoiding String.intern() may save time as well as heap-management problems.
1224 * (Allowing some short values to use String.intern() may increase available concurrency slightly.)
1225 * <p>
1226 * A reasonable value for this threshold is probably in the range -1--1024, for example:
1227 * <ul>
1228 * <li>-1 prevents use of String.intern(),</li>
1229 * <li>0 allows only "" use of String.intern(),</li>
1230 * <li>Integer.MAX_VALUE to allow all values to use String.intern().</li>
1231 * </ul>
1232 */
1233 private static final int MAX_STRING_INTERN = 1; // Allow (presumably relatively few) tiny values only.
1234
1235 /**Specific overloading of intern() for String to avoid runtime instanceof cost where possible. */
1236 public static String intern(final String s)
1237 {
1238 if(s == null) { return(null); }
1239
1240 // Assume that JVM's String.intern() is sensible and efficient and robust
1241 // and allows GC of no-longer-used items in modern JVMs (1.4+)...
1242 // At least for smallish String values.
1243 if(_USE_STRING_INTERN && (s.length() <= MAX_STRING_INTERN))
1244 {
1245 //System.out.println("MemoryTools.intern(String): using String.intern() for length "+s.length() + ": " + s);
1246 return(s.intern());
1247 }
1248
1249 //System.out.println("MemoryTools.intern(String): avoiding String.intern() for length "+s.length() + ": " + s);
1250
1251 // Use our generic Internable mechanism for long(er) String values.
1252 final class StringWrapper implements Internable
1253 {
1254 /**Our encapsulated immutable String; never null. */
1255 final String str = s;
1256
1257 /**Hash code as from underlying String. */
1258 @Override
1259 public final int hashCode() { return(str.hashCode()); }
1260
1261 /**Equality based on underlying String instances being equal. */
1262 @Override
1263 public final boolean equals(final Object obj)
1264 {
1265 if(this == obj) { return(true); }
1266 if(!(obj instanceof StringWrapper)) { return(false); }
1267 final StringWrapper other = (StringWrapper) obj;
1268 return(str.equals(other.str));
1269 }
1270 }
1271
1272 // Recursively handle the wrapped value as an Internable.
1273 return((intern(new StringWrapper())).str);
1274 }
1275
1276 /**Specific overloading of intern() for Internable to avoid runtime instanceof cost where possible. */
1277 @SuppressWarnings("unchecked")
1278 public static <E extends Internable> E intern(final E o)
1279 {
1280 if(o == null) { return(null); }
1281
1282 final WeakHashMap<Internable, WeakReference<Internable>> WHM_Internable;
1283 if(SINGLE_CPU_MODE)
1284 { WHM_Internable = WHM_Internables_0; } // Just one map in SINGLE_CPU_MODE, so save an indirection.
1285 else
1286 {
1287 // Select which sub-map we're working on (concurrently)...
1288 int oHash = o.getClass().hashCode() ^ o.hashCode();
1289 oHash ^= (oHash >>> 24) - (oHash >> 13);
1290 oHash ^= (oHash >>> MAX_INTERN_CONC_POWER) ^ (oHash >>> (2*MAX_INTERN_CONC_POWER));
1291 final int index = oHash & ((1 << MAX_INTERN_CONC_POWER) - 1);
1292 WHM_Internable = WHM_Internables[index];
1293 }
1294
1295 // Serialise access to protect the (non-thread-safe) Map and
1296 // to eliminate races so that we get complete canonicalisation.
1297 // Note that separate sub-maps can be accessed concurrently.
1298 synchronized(WHM_Internable)
1299 {
1300 // If we have an extant entry then return it
1301 // unless it is beaten on InternalRank.
1302 final WeakReference<E> v = (WeakReference<E>) WHM_Internable.get(o);
1303 final E old;
1304 if((v != null) && (null != (old = v.get())))
1305 {
1306 // // Return old instance if this new instance is not ranked,
1307 // // or if it has a non-positive ranking compared to (ie is no worse than)
1308 // // the new value.
1309 // if((!(old instanceof InternableRank)) ||
1310 // (((InternableRank) old).internableRank((InternableRank)o) <= 0))
1311 { return(old); } // Return existing intern()ed (non-null) value.
1312 }
1313
1314 // Insert (and return) new (unique or lowest ranked) value just passed in.
1315 WHM_Internable.put(o, new WeakReference<Internable>(o));
1316 return(o); // Return original (unique or lowest ranked) instance.
1317 }
1318 }
1319
1320 /**Specific overloading of intern() for Number to avoid runtime instanceof cost where possible.
1321 */
1322 @SuppressWarnings("unchecked")
1323 public static <E extends Number> E intern(final E o)
1324 {
1325 if(o == null) { return(null); }
1326
1327 final Class<?> oC = o.getClass();
1328 if( (oC == java.lang.Long.class) ||
1329 (oC == java.lang.Integer.class) ||
1330 (oC == java.lang.Short.class) ||
1331 (oC == java.lang.Float.class) ||
1332 (oC == java.lang.Double.class))
1333 {
1334 final Number n = o;
1335
1336 final class NumberWrapper implements Internable
1337 {
1338 /**Our encapsulated immutable Number; never null. */
1339 final Number num = n;
1340
1341 /**Hash code as from underlying Number. */
1342 @Override
1343 public final int hashCode() { return(num.hashCode()); }
1344
1345 /**Equality based on underlying Number instances being equal. */
1346 @Override
1347 public final boolean equals(final Object obj)
1348 {
1349 if(this == obj) { return(true); }
1350 if(!(obj instanceof NumberWrapper)) { return(false); }
1351 final NumberWrapper other = (NumberWrapper) obj;
1352 return(num.equals(other.num));
1353 }
1354 }
1355
1356 // Recursively handle the wrapped value as an Internable.
1357 return((E) (intern(new NumberWrapper())).num);
1358 }
1359 // Eliminate duplicate Byte values with JDK1.5+ Byte.valueOf()
1360 // as an efficient alternative to our generic mechanism.
1361 else if(o instanceof java.lang.Byte)
1362 { return((E) Byte.valueOf(((Byte) o).byteValue())); }
1363
1364 return(o); // Can't handle this unknown Number subtype.
1365 }
1366
1367 /**Generic equivalent of String.intern(), for more immutable objects that we care about.
1368 * Any object which is immutable (and probably final) and has functional
1369 * equals() and hashcode() methods where only apparently-identical instances
1370 * are equal can potentially be cached/canonicalised/deduped
1371 * via this routine.
1372 * <p>
1373 * This generic routine is for where we do not know the type until run-time;
1374 * the compiler may select a better overloading at compile-time otherwise.
1375 * Thanks to Peter Ahé of Sun for the suggestion!
1376 * <p>
1377 * Note that lots of immutable/final objects are <em>not</em>
1378 * suitable for canonicalisation with this routine.
1379 * Caveat programmer.
1380 * <p>
1381 * A unique instance is returned of the same type.
1382 * <p>
1383 * When the intern method is invoked, if the pool already contains an
1384 * Object equal to this <code>Object</code> o as determined by
1385 * the equals(Object) method, then the object from the pool is
1386 * returned. Otherwise, this <code>Object</code> is added to the
1387 * pool and a reference to this <code>Object</code> is returned.
1388 * <p>
1389 * It follows that for any two Objects <code>s</code> and <code>t</code>,
1390 * <code>intern(s) == intern(t)</code> is <code>true</code>
1391 * if and only if <code>s.equals(t)</code> is <code>true</code>.
1392 * <p>
1393 * Entries are automatically dropped sometime after the last
1394 * strong/soft reference to them has gone,
1395 * possibly on the next call to this routine.
1396 * <p>
1397 * Unlike String.intern(), this applies to more than just String elements,
1398 * and memory is guaranteed to be recoverable from non-referenced items
1399 * (whereas String.intern() has not always been so and is still
1400 * not clear in the spec).
1401 * <p>
1402 * It is probably not especially useful to put String constants or other
1403 * static items in here routinely as their entries are unlikely
1404 * to become unreferenced.
1405 * <p>
1406 * This routine is likely to be quite slow and have significant overhead,
1407 * so only use it when not doing so would cause huge memory bloat or churn,
1408 * and when you expect the intern()ed values to live for a long time.
1409 * <p>
1410 * May not in fact be able to cache/canonicalise all or any objects;
1411 * mutable objects should never be intern()ed.
1412 * <p>
1413 * Calling this with null returns null.
1414 *
1415 * @return an Object that has the same contents as this Object,
1416 * but is guaranteed to be from a pool of unique Objects.
1417 */
1418 @SuppressWarnings("unchecked")
1419 public static <E> E intern(final E o)
1420 {
1421 if(o == null) { return(null); }
1422
1423 // Default is to do nothing.
1424 E result = o;
1425
1426 // Extract the class for quick comparison...
1427 final Class<?> oC = o.getClass();
1428
1429 // Assume that String values are very frequent intern()ees,
1430 // so handle these first.
1431 if(oC == String.class)
1432 { result = (E) intern((String) o); }
1433
1434 // Handle Internable objects...
1435 else if(o instanceof Internable)
1436 { result = (E) intern((Internable) o); }
1437
1438 // Handle specific immutable instances of Number.
1439 // We only attempt to handle the common JDK-supplied types
1440 // from the java.lang.* API that we know to be immutable/safe.
1441 else if(o instanceof java.lang.Number)
1442 { result = (E) intern((Number) o); }
1443
1444 // Canonicalise Boolean values in the obvious way...
1445 else if(oC == Boolean.class)
1446 { result = (E) (((Boolean) o).booleanValue() ? Boolean.TRUE : Boolean.FALSE); }
1447
1448 // Else consider warning about pointless calls to intern().
1449 else if(IsDebug.isDebug)
1450 { System.err.println("WARNING: MemoryTools.intern() cannot handle objects of type: " + o.getClass().getName()); }
1451
1452 // Check that the expected invariants hold when we're done.
1453 assert(result.getClass() == o.getClass());
1454 assert(result.equals(o) && o.equals(result) && (result.hashCode() == o.hashCode()));
1455
1456 return(result);
1457 }
1458
1459
1460 /**Interface for minimal Map subset for caches of various flavours. */
1461 public interface CacheMiniMap<K,V>
1462 {
1463 /**Get an entry from the map; null if no such element. */
1464 public V get(final K key);
1465
1466 /**Put an entry in the map, returning previous value if any. */
1467 public V put(final K key, final V value);
1468
1469 /**Remove an entry from the map and return the removed value, if any, else null. */
1470 public V remove(final K key);
1471
1472 /**Clear the map. */
1473 public void clear();
1474
1475 /**Return the number of entries in the map; non-negative. */
1476 public int size();
1477
1478 /**True if the map is non-empty.
1479 * Equivalent to (size() == 0) but may be faster for some implementations.
1480 */
1481 public boolean isEmpty();
1482 }
1483
1484 /**Lower percentage threshold of free space to force reported capacity cap to minimum; strictly positive and less than 99.
1485 * A value a little greater than 1 helps quickly flush out residual entries when very short of memory,
1486 * which may yield a disproportionate reduction in GC costs.
1487 */
1488 public static final int LOWER_PC_THRESHOLD_FOR_MIN_CAPACITY = 10;
1489
1490 /**Computes target map size cap based on system memory availability; in range [minSize,maxCapacity].
1491 * If free heap falls below the system target
1492 * this computes a reduced cap between the two hard limits supplied.
1493 * <p>
1494 * Always returns Integer.MAX_VALUE if maxCapacity is Integer.MAX_VALUE.
1495 */
1496 public static int computeCapacityCap(final int minSize, final int maxCapacity)
1497 {
1498 // Treat maxCapacity of Integer.MAX_VALUE as effectively 'unbounded'.
1499 if(maxCapacity == Integer.MAX_VALUE) { return(Integer.MAX_VALUE); }
1500
1501 // Adjust size cap in inverse proportion to heap shortage.
1502 final int pcFree = MemoryTools.percentFreeWithinTarget();
1503 if(pcFree < LOWER_PC_THRESHOLD_FOR_MIN_CAPACITY) // Dire shortage: minimise entry lifetime.
1504 { return(minSize); }
1505 if(pcFree > 99) // Loads of space: maximise entry lifetime.
1506 { return(maxCapacity); }
1507
1508 // Interpolate linearly (avoiding overflow).
1509 // As the percentage free goes up so does the maximum allowed size.
1510 final int sizeCap = (int)
1511 (((((long)pcFree) * maxCapacity) + ((100L - pcFree) * minSize)) / 100);
1512 assert((sizeCap >= minSize) && (sizeCap <= maxCapacity));
1513 return(sizeCap);
1514 }
1515 }