--- jsr166/src/jsr166y/ForkJoinTask.java 2010/11/28 21:21:03 1.73 +++ jsr166/src/jsr166y/ForkJoinTask.java 2011/02/22 00:39:31 1.74 @@ -12,7 +12,8 @@ import java.util.Collections; import java.util.List; import java.util.RandomAccess; import java.util.Map; -import java.util.WeakHashMap; +import java.lang.ref.WeakReference; +import java.lang.ref.ReferenceQueue; import java.util.concurrent.Callable; import java.util.concurrent.CancellationException; import java.util.concurrent.ExecutionException; @@ -23,6 +24,8 @@ import java.util.concurrent.RejectedExec import java.util.concurrent.RunnableFuture; import java.util.concurrent.TimeUnit; import java.util.concurrent.TimeoutException; +import java.util.concurrent.locks.ReentrantLock; +import java.lang.reflect.Constructor; /** * Abstract base class for tasks that run within a {@link ForkJoinPool}. @@ -66,7 +69,11 @@ import java.util.concurrent.TimeoutExcep * rethrown to callers attempting to join them. These exceptions may * additionally include {@link RejectedExecutionException} stemming * from internal resource exhaustion, such as failure to allocate - * internal task queues. + * internal task queues. Rethrown exceptions behave in the same way as + * regular exceptions, but, when possible, contain stack traces (as + * displayed for example using {@code ex.printStackTrace()}) of both + * the thread that initiated the computation as well as the thread + * actually encountering the exception; minimally only the latter. * *

The primary method for awaiting completion and extracting * results of a task is {@link #join}, but there are several variants: @@ -163,8 +170,7 @@ public abstract class ForkJoinTask im * status maintenance (2) execution and awaiting completion (3) * user-level methods that additionally report results. This is * sometimes hard to see because this file orders exported methods - * in a way that flows well in javadocs. In particular, most - * join mechanics are in method quietlyJoin, below. + * in a way that flows well in javadocs. */ /* @@ -186,91 +192,67 @@ public abstract class ForkJoinTask im /** The run status of this task */ volatile int status; // accessed directly by pool and workers - private static final int NORMAL = -1; private static final int CANCELLED = -2; private static final int EXCEPTIONAL = -3; private static final int SIGNAL = 1; /** - * Table of exceptions thrown by tasks, to enable reporting by - * callers. Because exceptions are rare, we don't directly keep - * them with task objects, but instead use a weak ref table. Note - * that cancellation exceptions don't appear in the table, but are - * instead recorded as status values. - * TODO: Use ConcurrentReferenceHashMap - */ - static final Map, Throwable> exceptionMap = - Collections.synchronizedMap - (new WeakHashMap, Throwable>()); - - // Maintaining completion status - - /** * Marks completion and wakes up threads waiting to join this task, * also clearing signal request bits. * * @param completion one of NORMAL, CANCELLED, EXCEPTIONAL + * @return completion status on exit */ - private void setCompletion(int completion) { - int s; - while ((s = status) >= 0) { + private int setCompletion(int completion) { + for (int s;;) { + if ((s = status) < 0) + return s; if (UNSAFE.compareAndSwapInt(this, statusOffset, s, completion)) { if (s != 0) synchronized (this) { notifyAll(); } - break; + return completion; } } } /** - * Records exception and sets exceptional completion. + * Tries to block a worker thread until completed or timed out. + * Uses Object.wait time argument conventions. + * May fail on contention or interrupt. * - * @return status on exit + * @param millis if > 0, wait time. */ - private void setExceptionalCompletion(Throwable rex) { - exceptionMap.put(this, rex); - setCompletion(EXCEPTIONAL); - } - - /** - * Blocks a worker thread until completed or timed out. Called - * only by pool. - */ - final void internalAwaitDone(long millis, int nanos) { - int s = status; - if ((s == 0 && - UNSAFE.compareAndSwapInt(this, statusOffset, 0, SIGNAL)) || - s > 0) { - try { // the odd construction reduces lock bias effects + final void tryAwaitDone(long millis) { + int s; + try { + if (((s = status) > 0 || + (s == 0 && + UNSAFE.compareAndSwapInt(this, statusOffset, 0, SIGNAL))) && + status > 0) { synchronized (this) { if (status > 0) - wait(millis, nanos); - else - notifyAll(); + wait(millis); } - } catch (InterruptedException ie) { - cancelIfTerminating(); } + } catch (InterruptedException ie) { + // caller must check termination } } /** * Blocks a non-worker-thread until completion. + * @return status upon completion */ - private void externalAwaitDone() { - if (status >= 0) { + private int externalAwaitDone() { + int s; + if ((s = status) >= 0) { boolean interrupted = false; synchronized (this) { - for (;;) { - int s = status; + while ((s = status) >= 0) { if (s == 0) UNSAFE.compareAndSwapInt(this, statusOffset, 0, SIGNAL); - else if (s < 0) { - notifyAll(); - break; - } else { try { wait(); @@ -283,53 +265,305 @@ public abstract class ForkJoinTask im if (interrupted) Thread.currentThread().interrupt(); } + return s; } /** * Blocks a non-worker-thread until completion or interruption or timeout. */ - private void externalInterruptibleAwaitDone(boolean timed, long nanos) + private int externalInterruptibleAwaitDone(long millis) throws InterruptedException { + int s; if (Thread.interrupted()) throw new InterruptedException(); - if (status >= 0) { - long startTime = timed ? System.nanoTime() : 0L; + if ((s = status) >= 0) { synchronized (this) { - for (;;) { - long nt; - int s = status; + while ((s = status) >= 0) { if (s == 0) UNSAFE.compareAndSwapInt(this, statusOffset, 0, SIGNAL); - else if (s < 0) { - notifyAll(); - break; - } - else if (!timed) - wait(); - else if ((nt = nanos - (System.nanoTime()-startTime)) > 0L) - wait(nt / 1000000, (int)(nt % 1000000)); else - break; + wait(millis); } } } + return s; } /** - * Unless done, calls exec and records status if completed, but - * doesn't wait for completion otherwise. Primary execution method - * for ForkJoinWorkerThread. + * Primary execution method for stolen tasks. Unless done, calls + * exec and records status if completed, but doesn't wait for + * completion otherwise. */ - final void quietlyExec() { - try { - if (status < 0 || !exec()) + final void doExec() { + if (status >= 0) { + boolean completed; + try { + completed = exec(); + } catch (Throwable rex) { + setExceptionalCompletion(rex); return; + } + if (completed) + setCompletion(NORMAL); // must be outside try block + } + } + + /** + * Primary mechanics for join, get, quietlyJoin. + * @return status upon completion + */ + private int doJoin() { + Thread t; ForkJoinWorkerThread w; int s; boolean completed; + if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) { + if ((s = status) < 0) + return s; + if ((w = (ForkJoinWorkerThread)t).unpushTask(this)) { + try { + completed = exec(); + } catch (Throwable rex) { + return setExceptionalCompletion(rex); + } + if (completed) + return setCompletion(NORMAL); + } + return w.joinTask(this); + } + else + return externalAwaitDone(); + } + + /** + * Primary mechanics for invoke, quietlyInvoke. + * @return status upon completion + */ + private int doInvoke() { + int s; boolean completed; + if ((s = status) < 0) + return s; + try { + completed = exec(); } catch (Throwable rex) { - setExceptionalCompletion(rex); - return; + return setExceptionalCompletion(rex); } - setCompletion(NORMAL); // must be outside try block + if (completed) + return setCompletion(NORMAL); + else + return doJoin(); + } + + // Exception table support + + /** + * Table of exceptions thrown by tasks, to enable reporting by + * callers. Because exceptions are rare, we don't directly keep + * them with task objects, but instead use a weak ref table. Note + * that cancellation exceptions don't appear in the table, but are + * instead recorded as status values. + * + * Note: These statics are initialized below in static block. + */ + private static final ExceptionNode[] exceptionTable; + private static final ReentrantLock exceptionTableLock; + private static final ReferenceQueue exceptionTableRefQueue; + + /** + * Fixed capacity for exceptionTable. + */ + private static final int EXCEPTION_MAP_CAPACITY = 32; + + /** + * Key-value nodes for exception table. The chained hash table + * uses identity comparisons, full locking, and weak references + * for keys. The table has a fixed capacity because it only + * maintains task exceptions long enough for joiners to access + * them, so should never become very large for sustained + * periods. However, since we do not know when the last joiner + * completes, we must use weak references and expunge them. We do + * so on each operation (hence full locking). Also, some thread in + * any ForkJoinPool will call helpExpunge when its pool becomes + * isQuiescent. + */ + static final class ExceptionNode extends WeakReference>{ + final Throwable ex; + ExceptionNode next; + final long thrower; + ExceptionNode(ForkJoinTask task, Throwable ex, ExceptionNode next) { + super(task, exceptionTableRefQueue); + this.ex = ex; + this.next = next; + this.thrower = Thread.currentThread().getId(); + } + } + + /** + * Records exception and sets exceptional completion. + * + * @return status on exit + */ + private int setExceptionalCompletion(Throwable ex) { + int h = System.identityHashCode(this); + ReentrantLock lock = exceptionTableLock; + lock.lock(); + try { + expungeStaleExceptions(); + ExceptionNode[] t = exceptionTable; + int i = h & (t.length - 1); + for (ExceptionNode e = t[i]; ; e = e.next) { + if (e == null) { + t[i] = new ExceptionNode(this, ex, t[i]); + break; + } + if (e.get() == this) // already present + break; + } + } finally { + lock.unlock(); + } + return setCompletion(EXCEPTIONAL); + } + + /** + * Removes exception node and clears status + */ + private void clearExceptionalCompletion() { + int h = System.identityHashCode(this); + ReentrantLock lock = exceptionTableLock; + lock.lock(); + try { + ExceptionNode[] t = exceptionTable; + int i = h & (t.length - 1); + ExceptionNode e = t[i]; + ExceptionNode pred = null; + while (e != null) { + ExceptionNode next = e.next; + if (e.get() == this) { + if (pred == null) + t[i] = next; + else + pred.next = next; + break; + } + pred = e; + e = next; + } + expungeStaleExceptions(); + status = 0; + } finally { + lock.unlock(); + } + } + + /** + * Returns a rethrowable exception for the given task, if + * available. To provide accurate stack traces, if the exception + * was not thrown by the current thread, we try to create a new + * exception of the same type as the one thrown, but with the + * recorded exception as its cause. If there is no such + * constructor, we instead try to use a no-arg constructor, + * followed by initCause, to the same effect. If none of these + * apply, or any fail due to other exceptions, we return the + * recorded exception, which is still correct, although it may + * contain a misleading stack trace. + * + * @return the exception, or null if none + */ + private Throwable getThrowableException() { + if (status != EXCEPTIONAL) + return null; + int h = System.identityHashCode(this); + ExceptionNode e; + ReentrantLock lock = exceptionTableLock; + lock.lock(); + try { + expungeStaleExceptions(); + ExceptionNode[] t = exceptionTable; + e = t[h & (t.length - 1)]; + while (e != null && e.get() != this) + e = e.next; + } finally { + lock.unlock(); + } + Throwable ex; + if (e == null || (ex = e.ex) == null) + return null; + if (e.thrower != Thread.currentThread().getId()) { + Class ec = ex.getClass(); + try { + Constructor noArgCtor = null; + Constructor[] cs = ec.getConstructors();// public ctors only + for (int i = 0; i < cs.length; ++i) { + Constructor c = cs[i]; + Class[] ps = c.getParameterTypes(); + if (ps.length == 0) + noArgCtor = c; + else if (ps.length == 1 && ps[0] == Throwable.class) + return (Throwable)(c.newInstance(ex)); + } + if (noArgCtor != null) { + Throwable wx = (Throwable)(noArgCtor.newInstance()); + wx.initCause(ex); + return wx; + } + } catch (Exception ignore) { + } + } + return ex; + } + + /** + * Poll stale refs and remove them. Call only while holding lock. + */ + private static void expungeStaleExceptions() { + for (Object x; (x = exceptionTableRefQueue.poll()) != null;) { + if (x instanceof ExceptionNode) { + ForkJoinTask key = ((ExceptionNode)x).get(); + ExceptionNode[] t = exceptionTable; + int i = System.identityHashCode(key) & (t.length - 1); + ExceptionNode e = t[i]; + ExceptionNode pred = null; + while (e != null) { + ExceptionNode next = e.next; + if (e == x) { + if (pred == null) + t[i] = next; + else + pred.next = next; + break; + } + pred = e; + e = next; + } + } + } + } + + /** + * If lock is available, poll any stale refs and remove them. + * Called from ForkJoinPool when pools become quiescent. + */ + static final void helpExpungeStaleExceptions() { + ReentrantLock lock = exceptionTableLock; + if (lock.tryLock()) { + try { + expungeStaleExceptions(); + } finally { + lock.unlock(); + } + } + } + + /** + * Report the result of invoke or join; called only upon + * non-normal return of internal versions. + */ + private V reportResult() { + int s; Throwable ex; + if ((s = status) == CANCELLED) + throw new CancellationException(); + if (s == EXCEPTIONAL && (ex = getThrowableException()) != null) + UNSAFE.throwException(ex); + return getRawResult(); } // public methods @@ -370,11 +604,10 @@ public abstract class ForkJoinTask im * @return the computed result */ public final V join() { - quietlyJoin(); - Throwable ex; - if (status < NORMAL && (ex = getException()) != null) - UNSAFE.throwException(ex); - return getRawResult(); + if (doJoin() != NORMAL) + return reportResult(); + else + return getRawResult(); } /** @@ -386,11 +619,10 @@ public abstract class ForkJoinTask im * @return the computed result */ public final V invoke() { - quietlyInvoke(); - Throwable ex; - if (status < NORMAL && (ex = getException()) != null) - UNSAFE.throwException(ex); - return getRawResult(); + if (doInvoke() != NORMAL) + return reportResult(); + else + return getRawResult(); } /** @@ -454,22 +686,16 @@ public abstract class ForkJoinTask im } else if (i != 0) t.fork(); - else { - t.quietlyInvoke(); - if (ex == null && t.status < NORMAL) - ex = t.getException(); - } + else if (t.doInvoke() < NORMAL && ex == null) + ex = t.getException(); } for (int i = 1; i <= last; ++i) { ForkJoinTask t = tasks[i]; if (t != null) { if (ex != null) t.cancel(false); - else { - t.quietlyJoin(); - if (ex == null && t.status < NORMAL) - ex = t.getException(); - } + else if (t.doJoin() < NORMAL && ex == null) + ex = t.getException(); } } if (ex != null) @@ -517,22 +743,16 @@ public abstract class ForkJoinTask im } else if (i != 0) t.fork(); - else { - t.quietlyInvoke(); - if (ex == null && t.status < NORMAL) - ex = t.getException(); - } + else if (t.doInvoke() < NORMAL && ex == null) + ex = t.getException(); } for (int i = 1; i <= last; ++i) { ForkJoinTask t = ts.get(i); if (t != null) { if (ex != null) t.cancel(false); - else { - t.quietlyJoin(); - if (ex == null && t.status < NORMAL) - ex = t.getException(); - } + else if (t.doJoin() < NORMAL && ex == null) + ex = t.getException(); } } if (ex != null) @@ -568,8 +788,7 @@ public abstract class ForkJoinTask im * @return {@code true} if this task is now cancelled */ public boolean cancel(boolean mayInterruptIfRunning) { - setCompletion(CANCELLED); - return status == CANCELLED; + return setCompletion(CANCELLED) == CANCELLED; } /** @@ -585,21 +804,6 @@ public abstract class ForkJoinTask im } } - /** - * Cancels if current thread is a terminating worker thread, - * ignoring any exceptions thrown by cancel. - */ - final void cancelIfTerminating() { - Thread t = Thread.currentThread(); - if ((t instanceof ForkJoinWorkerThread) && - ((ForkJoinWorkerThread) t).isTerminating()) { - try { - cancel(false); - } catch (Throwable ignore) { - } - } - } - public final boolean isDone() { return status < 0; } @@ -639,7 +843,7 @@ public abstract class ForkJoinTask im int s = status; return ((s >= NORMAL) ? null : (s == CANCELLED) ? new CancellationException() : - exceptionMap.get(this)); + getThrowableException()); } /** @@ -697,19 +901,13 @@ public abstract class ForkJoinTask im * member of a ForkJoinPool and was interrupted while waiting */ public final V get() throws InterruptedException, ExecutionException { - Thread t = Thread.currentThread(); - if (t instanceof ForkJoinWorkerThread) - quietlyJoin(); - else - externalInterruptibleAwaitDone(false, 0L); - int s = status; - if (s != NORMAL) { - Throwable ex; - if (s == CANCELLED) - throw new CancellationException(); - if (s == EXCEPTIONAL && (ex = exceptionMap.get(this)) != null) - throw new ExecutionException(ex); - } + int s = (Thread.currentThread() instanceof ForkJoinWorkerThread) ? + doJoin() : externalInterruptibleAwaitDone(0L); + Throwable ex; + if (s == CANCELLED) + throw new CancellationException(); + if (s == EXCEPTIONAL && (ex = getThrowableException()) != null) + throw new ExecutionException(ex); return getRawResult(); } @@ -729,20 +927,39 @@ public abstract class ForkJoinTask im */ public final V get(long timeout, TimeUnit unit) throws InterruptedException, ExecutionException, TimeoutException { - long nanos = unit.toNanos(timeout); Thread t = Thread.currentThread(); - if (t instanceof ForkJoinWorkerThread) - ((ForkJoinWorkerThread)t).joinTask(this, true, nanos); - else - externalInterruptibleAwaitDone(true, nanos); + if (t instanceof ForkJoinWorkerThread) { + ForkJoinWorkerThread w = (ForkJoinWorkerThread) t; + long nanos = unit.toNanos(timeout); + if (status >= 0) { + boolean completed = false; + if (w.unpushTask(this)) { + try { + completed = exec(); + } catch (Throwable rex) { + setExceptionalCompletion(rex); + } + } + if (completed) + setCompletion(NORMAL); + else if (status >= 0 && nanos > 0) + w.pool.timedAwaitJoin(this, nanos); + } + } + else { + long millis = unit.toMillis(timeout); + if (millis > 0) + externalInterruptibleAwaitDone(millis); + } int s = status; if (s != NORMAL) { Throwable ex; if (s == CANCELLED) throw new CancellationException(); - if (s == EXCEPTIONAL && (ex = exceptionMap.get(this)) != null) + if (s != EXCEPTIONAL) + throw new TimeoutException(); + if ((ex = getThrowableException()) != null) throw new ExecutionException(ex); - throw new TimeoutException(); } return getRawResult(); } @@ -754,28 +971,7 @@ public abstract class ForkJoinTask im * known to have aborted. */ public final void quietlyJoin() { - Thread t; - if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) { - ForkJoinWorkerThread w = (ForkJoinWorkerThread) t; - if (status >= 0) { - if (w.unpushTask(this)) { - boolean completed; - try { - completed = exec(); - } catch (Throwable rex) { - setExceptionalCompletion(rex); - return; - } - if (completed) { - setCompletion(NORMAL); - return; - } - } - w.joinTask(this, false, 0L); - } - } - else - externalAwaitDone(); + doJoin(); } /** @@ -784,19 +980,7 @@ public abstract class ForkJoinTask im * exception. */ public final void quietlyInvoke() { - if (status >= 0) { - boolean completed; - try { - completed = exec(); - } catch (Throwable rex) { - setExceptionalCompletion(rex); - return; - } - if (completed) - setCompletion(NORMAL); - else - quietlyJoin(); - } + doInvoke(); } /** @@ -835,8 +1019,9 @@ public abstract class ForkJoinTask im */ public void reinitialize() { if (status == EXCEPTIONAL) - exceptionMap.remove(this); - status = 0; + clearExceptionalCompletion(); + else + status = 0; } /** @@ -1147,23 +1332,22 @@ public abstract class ForkJoinTask im s.defaultReadObject(); Object ex = s.readObject(); if (ex != null) - setExceptionalCompletion((Throwable) ex); + setExceptionalCompletion((Throwable)ex); } // Unsafe mechanics - - private static final sun.misc.Unsafe UNSAFE = getUnsafe(); - private static final long statusOffset = - objectFieldOffset("status", ForkJoinTask.class); - - private static long objectFieldOffset(String field, Class klazz) { + private static final sun.misc.Unsafe UNSAFE; + private static final long statusOffset; + static { + exceptionTableLock = new ReentrantLock(); + exceptionTableRefQueue = new ReferenceQueue(); + exceptionTable = new ExceptionNode[EXCEPTION_MAP_CAPACITY]; try { - return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field)); - } catch (NoSuchFieldException e) { - // Convert Exception to corresponding Error - NoSuchFieldError error = new NoSuchFieldError(field); - error.initCause(e); - throw error; + UNSAFE = getUnsafe(); + statusOffset = UNSAFE.objectFieldOffset + (ForkJoinTask.class.getDeclaredField("status")); + } catch (Exception e) { + throw new Error(e); } }