001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one
003: * or more contributor license agreements. See the NOTICE file
004: * distributed with this work for additional information
005: * regarding copyright ownership. The ASF licenses this file
006: * to you under the Apache License, Version 2.0 (the
007: * "License"); you may not use this file except in compliance
008: * with the License. You may obtain a copy of the License at
009: *
010: * http://www.apache.org/licenses/LICENSE-2.0
011: *
012: * Unless required by applicable law or agreed to in writing,
013: * software distributed under the License is distributed on an
014: * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015: * KIND, either express or implied. See the License for the
016: * specific language governing permissions and limitations
017: * under the License.
018: */
019: /*
020: * Written by Dawid Kurzyniec, based on code written by Doug Lea with assistance
021: * from members of JCP JSR-166 Expert Group. Released to the public domain,
022: * as explained at http://creativecommons.org/licenses/publicdomain.
023: * Thanks to Craig Mattocks for suggesting to use <code>sun.misc.Perf</code>.
024: */
025:
026: package org.apache.openjpa.lib.util.concurrent;
027:
028: import java.lang.reflect.Array;
029: import java.security.AccessController;
030: import java.security.PrivilegedAction;
031: import java.util.Collection;
032: import java.util.Iterator;
033:
034: import org.apache.openjpa.lib.util.J2DoPrivHelper;
035:
036: /**
037: * This class groups together the functionality of java.util.concurrent that
038: * cannot be fully and reliably implemented in backport, but for which some
039: * form of emulation is possible.
040: * Currently, this class contains methods related to nanosecond-precision
041: * timing, particularly via the {@link #nanoTime} method. To measure time
042: * accurately, this method by default uses <code>java.sun.Perf</code> on
043: * JDK1.4.2 and it falls back to <code>System.currentTimeMillis</code>
044: * on earlier JDKs.
045: *
046: * @author Dawid Kurzyniec
047: * @version 1.0
048: */
049: public final class Utils {
050:
051: private final static NanoTimer nanoTimer;
052: private final static String providerProp = "edu.emory.mathcs.backport.java.util.concurrent.NanoTimerProvider";
053:
054: static {
055: NanoTimer timer = null;
056: try {
057: String nanoTimerClassName = (String) AccessController
058: .doPrivileged(J2DoPrivHelper
059: .getPropertyAction(providerProp));
060: if (nanoTimerClassName != null) {
061: Class cls = Class.forName(nanoTimerClassName);
062: timer = (NanoTimer) AccessController
063: .doPrivileged(J2DoPrivHelper
064: .newInstanceAction(cls));
065: }
066: } catch (Exception e) {
067: System.err
068: .println("WARNING: unable to load the system-property-defined "
069: + "nanotime provider; switching to the default");
070: e.printStackTrace();
071: }
072:
073: if (timer == null) {
074: try {
075: timer = new SunPerfProvider();
076: } catch (Throwable e) {
077: }
078: }
079:
080: if (timer == null) {
081: timer = new MillisProvider();
082: }
083:
084: nanoTimer = timer;
085: }
086:
087: private Utils() {
088: }
089:
090: /**
091: * Returns the current value of the most precise available system timer,
092: * in nanoseconds. This method can only be used to measure elapsed time and
093: * is not related to any other notion of system or wall-clock time. The
094: * value returned represents nanoseconds since some fixed but arbitrary
095: * time(perhaps in the future, so values may be negative). This method
096: * provides nanosecond precision, but not necessarily nanosecond accuracy.
097: * No guarantees are made about how frequently values change. Differences
098: * in successive calls that span greater than approximately 292 years
099: * (2^63 nanoseconds) will not accurately compute elapsed time due to
100: * numerical overflow.
101: *
102: * <em>Implementation note:</em>By default, this method uses
103: * <code>sun.misc.Perf</code> on Java 1.4.2, and falls back to
104: * System.currentTimeMillis() emulation on earlier JDKs. Custom
105: * timer can be provided via the system property
106: * <code>edu.emory.mathcs.backport.java.util.concurrent.NanoTimerProvider</code>.
107: * The value of the property should name a class implementing
108: * {@link NanoTimer} interface.
109: * Note: on JDK 1.4.2, <code>sun.misc.Perf</code> timer seems to have
110: * resolution of the order of 1 microsecond, measured on Linux.
111: *
112: * @return The current value of the system timer, in nanoseconds.
113: */
114: public static long nanoTime() {
115: return nanoTimer.nanoTime();
116: }
117:
118: /**
119: * Causes the current thread to wait until it is signalled or interrupted,
120: * or the specified waiting time elapses. This method originally appears
121: * in the {@link Condition} interface, but it was moved to here since it
122: * can only be emulated, with very little accuracy guarantees: the
123: * efficient implementation requires accurate nanosecond timer and native
124: * support for nanosecond-precision wait queues, which are not usually
125: * present in JVMs prior to 1.5. Loss of precision may cause total waiting
126: * times to be systematically shorter than specified when re-waits occur.
127: * The lock associated with this condition is atomically
128: * released and the current thread becomes disabled for thread scheduling
129: * purposes and lies dormant until <em>one</em> of five things happens:
130: * <ul>
131: * <li>Some other thread invokes the {@link
132: * edu.emory.mathcs.backport.java.util.concurrent.locks.Condition#signal}
133: * method for this
134: * <tt>Condition</tt> and the current thread happens to be chosen as the
135: * thread to be awakened; or
136: * <li>Some other thread invokes the {@link
137: * edu.emory.mathcs.backport.java.util.concurrent.locks.Condition#signalAll}
138: * method for this
139: * <tt>Condition</tt>; or
140: * <li>Some other thread {@link Thread#interrupt interrupts} the current
141: * thread, and interruption of thread suspension is supported; or
142: * <li>The specified waiting time elapses; or
143: * <li>A "<em>spurious wakeup</em>" occurs.
144: * </ul> In all cases, before this method can return the current thread must
145: * re-acquire the lock associated with this condition. When the
146: * thread returns it is <em>guaranteed</em> to hold this lock.
147: * If the current thread:
148: * <ul>
149: * <li>has its interrupted status set on entry to this method; or
150: * <li>is {@link Thread#interrupt interrupted} while waiting
151: * and interruption of thread suspension is supported,
152: * </ul>
153: * then {@link InterruptedException} is thrown and the current thread's
154: * interrupted status is cleared. It is not specified, in the first
155: * case, whether or not the test for interruption occurs before the lock
156: * is released. The method returns an estimate of the number of nanoseconds
157: * remaining to wait given the supplied <tt>nanosTimeout</tt>
158: * value upon return, or a value less than or equal to zero if it
159: * timed out. Accuracy of this estimate is directly dependent on the
160: * accuracy of {@link #nanoTime}. This value can be used to determine
161: * whether and how long to re-wait in cases where the wait returns but an
162: * awaited condition still does not hold. Typical uses of this method take
163: * the following form:
164: *
165: * <pre> synchronized boolean aMethod(long timeout, TimeUnit unit) {
166: * long nanosTimeout = unit.toNanos(timeout);
167: * while (!conditionBeingWaitedFor) { if (nanosTimeout > 0)
168: * nanosTimeout = theCondition.awaitNanos(nanosTimeout); else return false;
169: * } // ... }
170: * </pre>
171: *
172: * <b>Implementation Considerations</b>
173: * The current thread is assumed to hold the lock associated with this
174: * <tt>Condition</tt> when this method is called.
175: * It is up to the implementation to determine if this is
176: * the case and if not, how to respond. Typically, an exception will be
177: * thrown(such as {@link IllegalMonitorStateException}) and the
178: * implementation must document that fact.
179: * A condition implementation can favor responding to an interrupt over
180: * normal method return in response to a signal, or over indicating the
181: * elapse of the specified waiting time. In either case the implementation
182: * must ensure that the signal is redirected to another waiting thread, if
183: * there is one.
184: *
185: * @param cond the condition to wait for
186: * @param nanosTimeout the maximum time to wait, in nanoseconds
187: * @return A value less than or equal to zero if the wait has
188: * timed out; otherwise an estimate, that
189: * is strictly less than the <tt>nanosTimeout</tt> argument,
190: * of the time still remaining when this method returned.
191: * @throws InterruptedException if the current thread is interrupted(and
192: * interruption of thread suspension is supported).
193: */
194: public static long awaitNanos(Condition cond, long nanosTimeout)
195: throws InterruptedException {
196: if (nanosTimeout <= 0)
197: return nanosTimeout;
198: long now = nanoTime();
199: cond.await(nanosTimeout, TimeUnit.NANOSECONDS);
200: return nanosTimeout - (nanoTime() - now);
201: }
202:
203: private static final class SunPerfProvider implements NanoTimer {
204:
205: final sun.misc.Perf perf;
206: final long multiplier, divisor;
207:
208: SunPerfProvider() {
209: perf = (sun.misc.Perf) AccessController
210: .doPrivileged(new PrivilegedAction() {
211: public Object run() {
212: return sun.misc.Perf.getPerf();
213: }
214: });
215: // trying to avoid BOTH overflow and rounding errors
216: long numerator = 1000000000;
217: long denominator = perf.highResFrequency();
218: long gcd = gcd(numerator, denominator);
219: this .multiplier = numerator / gcd;
220: this .divisor = denominator / gcd;
221: }
222:
223: public long nanoTime() {
224: long ctr = perf.highResCounter();
225:
226: // anything less sophisticated suffers either from rounding errors
227: // (FP arithmetics, backport v1.0) or overflow, when gcd is small
228: // (a bug in backport v1.0_01 reported by Ramesh Nethi)
229:
230: return ((ctr / divisor) * multiplier) + (ctr % divisor)
231: * multiplier / divisor;
232:
233: // even the above can theoretically cause problems if your JVM is
234: // running for sufficiently long time, but "sufficiently" means 292
235: // years(worst case), or 30,000 years(common case).
236:
237: // Details: when the ticks ctr overflows, there is no way to avoid
238: // discontinuity in computed nanos, even in infinite arithmetics,
239: // unless we count number of overflows that the ctr went through
240: // since the JVM started. This follows from the fact that
241: // (2^64*multiplier/divisor) mod(2^64) > 0 in general case.
242: // Theoretically we could find out the number of overflows by
243: // checking System.currentTimeMillis(), but this is unreliable
244: // since the system time can unpredictably change during the JVM
245: // lifetime.
246: // The time to overflow is 2^63 / ticks frequency. With current
247: // ticks frequencies of several MHz, it gives about 30,000 years
248: // before the problem happens. If ticks frequency reaches 1 GHz, the
249: // time to overflow is 292 years. It is unlikely that the frequency
250: // ever exceeds 1 GHz. We could double the time to overflow
251: // (to 2^64 / frequency) by using unsigned arithmetics, e.g. by
252: // adding the following correction whenever the ticks is negative:
253: // -2*((Long.MIN_VALUE / divisor) * multiplier +
254: // (Long.MIN_VALUE % divisor) * multiplier / divisor)
255: // But, with the worst case of as much as 292 years, it does not
256: // seem justified.
257: }
258: }
259:
260: private static final class MillisProvider implements NanoTimer {
261:
262: MillisProvider() {
263: }
264:
265: public long nanoTime() {
266: return System.currentTimeMillis() * 1000000;
267: }
268: }
269:
270: private static long gcd(long a, long b) {
271: long r;
272: while (b > 0) {
273: r = a % b;
274: a = b;
275: b = r;
276: }
277: return a;
278: }
279:
280: public static Object[] collectionToArray(Collection c) {
281: // guess the array size; expect to possibly be different
282: int len = c.size();
283: Object[] arr = new Object[len];
284: Iterator itr = c.iterator();
285: int idx = 0;
286: while (true) {
287: while (idx < len && itr.hasNext()) {
288: arr[idx++] = itr.next();
289: }
290: if (!itr.hasNext()) {
291: if (idx == len)
292: return arr;
293: // otherwise have to trim
294: return Arrays.copyOf(arr, idx, Object[].class);
295: }
296: // otherwise, have to grow
297: int newcap = ((arr.length / 2) + 1) * 3;
298: if (newcap < arr.length) {
299: // overflow
300: if (arr.length < Integer.MAX_VALUE) {
301: newcap = Integer.MAX_VALUE;
302: } else {
303: throw new OutOfMemoryError(
304: "required array size too large");
305: }
306: }
307: arr = Arrays.copyOf(arr, newcap, Object[].class);
308: len = newcap;
309: }
310: }
311:
312: public static Object[] collectionToArray(Collection c, Object[] a) {
313: Class aType = a.getClass();
314: // guess the array size; expect to possibly be different
315: int len = c.size();
316: Object[] arr = (a.length >= len ? a : (Object[]) Array
317: .newInstance(aType.getComponentType(), len));
318: Iterator itr = c.iterator();
319: int idx = 0;
320: while (true) {
321: while (idx < len && itr.hasNext()) {
322: arr[idx++] = itr.next();
323: }
324: if (!itr.hasNext()) {
325: if (idx == len)
326: return arr;
327: if (arr == a) {
328: // orig array -> null terminate
329: a[idx] = null;
330: return a;
331: } else {
332: // have to trim
333: return Arrays.copyOf(arr, idx, aType);
334: }
335: }
336: // otherwise, have to grow
337: int newcap = ((arr.length / 2) + 1) * 3;
338: if (newcap < arr.length) {
339: // overflow
340: if (arr.length < Integer.MAX_VALUE) {
341: newcap = Integer.MAX_VALUE;
342: } else {
343: throw new OutOfMemoryError(
344: "required array size too large");
345: }
346: }
347: arr = Arrays.copyOf(arr, newcap, aType);
348: len = newcap;
349: }
350: }
351: }
|