/*
* Written by Dawid Kurzyniec, based on code written by Doug Lea with assistance
* from members of JCP JSR-166 Expert Group. Released to the public domain,
* as explained at http://creativecommons.org/licenses/publicdomain.
*
* Thanks to Craig Mattocks for suggesting to use <code>sun.misc.Perf</code>.
*/
package scala.actors.threadpool.helpers;
//import edu.emory.mathcs.backport.java.util.*;
import scala.actors.threadpool.*;
import scala.actors.threadpool.locks.*;
import java.security.AccessController;
import java.security.PrivilegedAction;
import java.lang.reflect.Array;
import java.util.Iterator;
import java.util.Collection;
/**
* <p>
* This class groups together the functionality of java.util.concurrent that
* cannot be fully and reliably implemented in backport, but for which some
* form of emulation is possible.
* <p>
* Currently, this class contains methods related to nanosecond-precision
* timing, particularly via the {@link #nanoTime} method. To measure time
* accurately, this method by default uses <code>java.sun.Perf</code> on
* JDK1.4.2 and it falls back to <code>System.currentTimeMillis</code>
* on earlier JDKs.
*
* @author Dawid Kurzyniec
* @version 1.0
*/
public final class Utils {
private final static NanoTimer nanoTimer;
private final static String providerProp =
"edu.emory.mathcs.backport.java.util.concurrent.NanoTimerProvider";
static {
NanoTimer timer = null;
try {
String nanoTimerClassName =
AccessController.doPrivileged(new PrivilegedAction<String>() {
public String run() {
return System.getProperty(providerProp);
}
});
if (nanoTimerClassName != null) {
Class cls = Class.forName(nanoTimerClassName);
timer = (NanoTimer) cls.newInstance();
}
}
catch (Exception e) {
System.err.println("WARNING: unable to load the system-property-defined " +
"nanotime provider; switching to the default");
e.printStackTrace();
}
if (timer == null) {
try {
timer = new SunPerfProvider();
}
catch (Throwable e) {}
}
if (timer == null) {
timer = new MillisProvider();
}
nanoTimer = timer;
}
private Utils() {}
/**
* Returns the current value of the most precise available system timer,
* in nanoseconds. This method can only be used to measure elapsed time and
* is not related to any other notion of system or wall-clock time. The
* value returned represents nanoseconds since some fixed but arbitrary
* time (perhaps in the future, so values may be negative). This method
* provides nanosecond precision, but not necessarily nanosecond accuracy.
* No guarantees are made about how frequently values change. Differences
* in successive calls that span greater than approximately 292 years
* (2^63 nanoseconds) will not accurately compute elapsed time due to
* numerical overflow.
* <p>
* <em>Implementation note:</em>By default, this method uses
* <code>sun.misc.Perf</code> on Java 1.4.2, and falls back to
* System.currentTimeMillis() emulation on earlier JDKs. Custom
* timer can be provided via the system property
* <code>edu.emory.mathcs.backport.java.util.concurrent.NanoTimerProvider</code>.
* The value of the property should name a class implementing
* {@link NanoTimer} interface.
* <p>
* Note: on JDK 1.4.2, <code>sun.misc.Perf</code> timer seems to have
* resolution of the order of 1 microsecond, measured on Linux.
*
* @return The current value of the system timer, in nanoseconds.
*/
public static long nanoTime() {
return nanoTimer.nanoTime();
}
/**
* Causes the current thread to wait until it is signalled or interrupted,
* or the specified waiting time elapses. This method originally appears
* in the {@link Condition} interface, but it was moved to here since it
* can only be emulated, with very little accuracy guarantees: the
* efficient implementation requires accurate nanosecond timer and native
* support for nanosecond-precision wait queues, which are not usually
* present in JVMs prior to 1.5. Loss of precision may cause total waiting
* times to be systematically shorter than specified when re-waits occur.
*
* <p>The lock associated with this condition is atomically
* released and the current thread becomes disabled for thread scheduling
* purposes and lies dormant until <em>one</em> of five things happens:
* <ul>
* <li>Some other thread invokes the {@link
* edu.emory.mathcs.backport.java.util.concurrent.locks.Condition#signal}
* method for this
* <tt>Condition</tt> and the current thread happens to be chosen as the
* thread to be awakened; or
* <li>Some other thread invokes the {@link
* edu.emory.mathcs.backport.java.util.concurrent.locks.Condition#signalAll}
* method for this
* <tt>Condition</tt>; or
* <li>Some other thread {@link Thread#interrupt interrupts} the current
* thread, and interruption of thread suspension is supported; or
* <li>The specified waiting time elapses; or
* <li>A "<em>spurious wakeup</em>" occurs.
* </ul>
*
* <p>In all cases, before this method can return the current thread must
* re-acquire the lock associated with this condition. When the
* thread returns it is <em>guaranteed</em> to hold this lock.
*
* <p>If the current thread:
* <ul>
* <li>has its interrupted status set on entry to this method; or
* <li>is {@link Thread#interrupt interrupted} while waiting
* and interruption of thread suspension is supported,
* </ul>
* then {@link InterruptedException} is thrown and the current thread's
* interrupted status is cleared. It is not specified, in the first
* case, whether or not the test for interruption occurs before the lock
* is released.
*
* <p>The method returns an estimate of the number of nanoseconds
* remaining to wait given the supplied <tt>nanosTimeout</tt>
* value upon return, or a value less than or equal to zero if it
* timed out. Accuracy of this estimate is directly dependent on the
* accuracy of {@link #nanoTime}. This value can be used to determine
* whether and how long to re-wait in cases where the wait returns but an
* awaited condition still does not hold. Typical uses of this method take
* the following form:
*
* <pre>
* synchronized boolean aMethod(long timeout, TimeUnit unit) {
* long nanosTimeout = unit.toNanos(timeout);
* while (!conditionBeingWaitedFor) {
* if (nanosTimeout > 0)
* nanosTimeout = theCondition.awaitNanos(nanosTimeout);
* else
* return false;
* }
* // ...
* }
* </pre>
*
* <p><b>Implementation Considerations</b>
* <p>The current thread is assumed to hold the lock associated with this
* <tt>Condition</tt> when this method is called.
* It is up to the implementation to determine if this is
* the case and if not, how to respond. Typically, an exception will be
* thrown (such as {@link IllegalMonitorStateException}) and the
* implementation must document that fact.
*
* <p>A condition implementation can favor responding to an interrupt over
* normal method return in response to a signal, or over indicating the
* elapse of the specified waiting time. In either case the implementation
* must ensure that the signal is redirected to another waiting thread, if
* there is one.
*
* @param cond the condition to wait for
* @param nanosTimeout the maximum time to wait, in nanoseconds
* @return A value less than or equal to zero if the wait has
* timed out; otherwise an estimate, that
* is strictly less than the <tt>nanosTimeout</tt> argument,
* of the time still remaining when this method returned.
*
* @throws InterruptedException if the current thread is interrupted (and
* interruption of thread suspension is supported).
*/
public static long awaitNanos(Condition cond, long nanosTimeout)
throws InterruptedException
{
if (nanosTimeout <= 0) return nanosTimeout;
long now = nanoTime();
cond.await(nanosTimeout, TimeUnit.NANOSECONDS);
return nanosTimeout - (nanoTime() - now);
}
private static final class SunPerfProvider implements NanoTimer {
final Perf perf;
final long multiplier, divisor;
SunPerfProvider() {
perf =
AccessController.doPrivileged(new PrivilegedAction<Perf>() {
public Perf run() {
return Perf.getPerf();
}
});
// trying to avoid BOTH overflow and rounding errors
long numerator = 1000000000;
long denominator = perf.highResFrequency();
long gcd = gcd(numerator, denominator);
this.multiplier = numerator / gcd;
this.divisor = denominator / gcd;
}
public long nanoTime() {
long ctr = perf.highResCounter();
// anything less sophisticated suffers either from rounding errors
// (FP arithmetics, backport v1.0) or overflow, when gcd is small
// (a bug in backport v1.0_01 reported by Ramesh Nethi)
return ((ctr / divisor) * multiplier) +
(ctr % divisor) * multiplier / divisor;
// even the above can theoretically cause problems if your JVM is
// running for sufficiently long time, but "sufficiently" means 292
// years (worst case), or 30,000 years (common case).
// Details: when the ticks ctr overflows, there is no way to avoid
// discontinuity in computed nanos, even in infinite arithmetics,
// unless we count number of overflows that the ctr went through
// since the JVM started. This follows from the fact that
// (2^64*multiplier/divisor) mod (2^64) > 0 in general case.
// Theoretically we could find out the number of overflows by
// checking System.currentTimeMillis(), but this is unreliable
// since the system time can unpredictably change during the JVM
// lifetime.
// The time to overflow is 2^63 / ticks frequency. With current
// ticks frequencies of several MHz, it gives about 30,000 years
// before the problem happens. If ticks frequency reaches 1 GHz, the
// time to overflow is 292 years. It is unlikely that the frequency
// ever exceeds 1 GHz. We could double the time to overflow
// (to 2^64 / frequency) by using unsigned arithmetics, e.g. by
// adding the following correction whenever the ticks is negative:
// -2*((Long.MIN_VALUE / divisor) * multiplier +
// (Long.MIN_VALUE % divisor) * multiplier / divisor)
// But, with the worst case of as much as 292 years, it does not
// seem justified.
}
}
private static final class MillisProvider implements NanoTimer {
MillisProvider() {}
public long nanoTime() {
return System.currentTimeMillis() * 1000000;
}
}
private static long gcd(long a, long b) {
long r;
while (b>0) { r = a % b; a = b; b = r; }
return a;
}
public static Object[] collectionToArray(Collection c) {
// guess the array size; expect to possibly be different
int len = c.size();
Object[] arr = new Object[len];
Iterator itr = c.iterator();
int idx = 0;
while (true) {
while (idx < len && itr.hasNext()) {
arr[idx++] = itr.next();
}
if (!itr.hasNext()) {
if (idx == len) return arr;
// otherwise have to trim
return Arrays.copyOf(arr, idx, Object[].class);
}
// otherwise, have to grow
int newcap = ((arr.length/2)+1)*3;
if (newcap < arr.length) {
// overflow
if (arr.length < Integer.MAX_VALUE) {
newcap = Integer.MAX_VALUE;
}
else {
throw new OutOfMemoryError("required array size too large");
}
}
arr = Arrays.copyOf(arr, newcap, Object[].class);
len = newcap;
}
}
public static Object[] collectionToArray(Collection c, Object[] a) {
Class aType = a.getClass();
// guess the array size; expect to possibly be different
int len = c.size();
Object[] arr = (a.length >= len ? a :
(Object[])Array.newInstance(aType.getComponentType(), len));
Iterator itr = c.iterator();
int idx = 0;
while (true) {
while (idx < len && itr.hasNext()) {
arr[idx++] = itr.next();
}
if (!itr.hasNext()) {
if (idx == len) return arr;
if (arr == a) {
// orig array -> null terminate
a[idx] = null;
return a;
}
else {
// have to trim
return Arrays.copyOf(arr, idx, aType);
}
}
// otherwise, have to grow
int newcap = ((arr.length/2)+1)*3;
if (newcap < arr.length) {
// overflow
if (arr.length < Integer.MAX_VALUE) {
newcap = Integer.MAX_VALUE;
}
else {
throw new OutOfMemoryError("required array size too large");
}
}
arr = Arrays.copyOf(arr, newcap, aType);
len = newcap;
}
}
}
