View Javadoc
1   /*
2    * Copyright 2013 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License,
5    * version 2.0 (the "License"); you may not use this file except in compliance
6    * with the License. You may obtain a copy of the License at:
7    *
8    *   http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations
14   * under the License.
15   */
16  
17  /*
18   * Written by Doug Lea with assistance from members of JCP JSR-166
19   * Expert Group and released to the public domain, as explained at
20   * http://creativecommons.org/publicdomain/zero/1.0/
21   */
22  
23  package io.netty.util.internal.chmv8;
24  
25  import java.io.Serializable;
26  import java.lang.ref.ReferenceQueue;
27  import java.lang.ref.WeakReference;
28  import java.lang.reflect.Constructor;
29  import java.util.Collection;
30  import java.util.List;
31  import java.util.RandomAccess;
32  import java.util.concurrent.Callable;
33  import java.util.concurrent.CancellationException;
34  import java.util.concurrent.ExecutionException;
35  import java.util.concurrent.Future;
36  import java.util.concurrent.Phaser;
37  import java.util.concurrent.RecursiveAction;
38  import java.util.concurrent.RecursiveTask;
39  import java.util.concurrent.RejectedExecutionException;
40  import java.util.concurrent.RunnableFuture;
41  import java.util.concurrent.TimeUnit;
42  import java.util.concurrent.TimeoutException;
43  import java.util.concurrent.locks.ReentrantLock;
44  
45  /**
46   * Abstract base class for tasks that run within a {@link ForkJoinPool}.
47   * A {@code ForkJoinTask} is a thread-like entity that is much
48   * lighter weight than a normal thread.  Huge numbers of tasks and
49   * subtasks may be hosted by a small number of actual threads in a
50   * ForkJoinPool, at the price of some usage limitations.
51   *
52   * <p>A "main" {@code ForkJoinTask} begins execution when it is
53   * explicitly submitted to a {@link ForkJoinPool}, or, if not already
54   * engaged in a ForkJoin computation, commenced in the {@link
55   * ForkJoinPool#commonPool()} via {@link #fork}, {@link #invoke}, or
56   * related methods.  Once started, it will usually in turn start other
57   * subtasks.  As indicated by the name of this class, many programs
58   * using {@code ForkJoinTask} employ only methods {@link #fork} and
59   * {@link #join}, or derivatives such as {@link
60   * #invokeAll(ForkJoinTask...) invokeAll}.  However, this class also
61   * provides a number of other methods that can come into play in
62   * advanced usages, as well as extension mechanics that allow support
63   * of new forms of fork/join processing.
64   *
65   * <p>A {@code ForkJoinTask} is a lightweight form of {@link Future}.
66   * The efficiency of {@code ForkJoinTask}s stems from a set of
67   * restrictions (that are only partially statically enforceable)
68   * reflecting their main use as computational tasks calculating pure
69   * functions or operating on purely isolated objects.  The primary
70   * coordination mechanisms are {@link #fork}, that arranges
71   * asynchronous execution, and {@link #join}, that doesn't proceed
72   * until the task's result has been computed.  Computations should
73   * ideally avoid {@code synchronized} methods or blocks, and should
74   * minimize other blocking synchronization apart from joining other
75   * tasks or using synchronizers such as Phasers that are advertised to
76   * cooperate with fork/join scheduling. Subdividable tasks should also
77   * not perform blocking I/O, and should ideally access variables that
78   * are completely independent of those accessed by other running
79   * tasks. These guidelines are loosely enforced by not permitting
80   * checked exceptions such as {@code IOExceptions} to be
81   * thrown. However, computations may still encounter unchecked
82   * exceptions, that are rethrown to callers attempting to join
83   * them. These exceptions may additionally include {@link
84   * RejectedExecutionException} stemming from internal resource
85   * exhaustion, such as failure to allocate internal task
86   * queues. Rethrown exceptions behave in the same way as regular
87   * exceptions, but, when possible, contain stack traces (as displayed
88   * for example using {@code ex.printStackTrace()}) of both the thread
89   * that initiated the computation as well as the thread actually
90   * encountering the exception; minimally only the latter.
91   *
92   * <p>It is possible to define and use ForkJoinTasks that may block,
93   * but doing do requires three further considerations: (1) Completion
94   * of few if any <em>other</em> tasks should be dependent on a task
95   * that blocks on external synchronization or I/O. Event-style async
96   * tasks that are never joined (for example, those subclassing {@link
97   * CountedCompleter}) often fall into this category.  (2) To minimize
98   * resource impact, tasks should be small; ideally performing only the
99   * (possibly) blocking action. (3) Unless the {@link
100  * ForkJoinPool.ManagedBlocker} API is used, or the number of possibly
101  * blocked tasks is known to be less than the pool's {@link
102  * ForkJoinPool#getParallelism} level, the pool cannot guarantee that
103  * enough threads will be available to ensure progress or good
104  * performance.
105  *
106  * <p>The primary method for awaiting completion and extracting
107  * results of a task is {@link #join}, but there are several variants:
108  * The {@link Future#get} methods support interruptible and/or timed
109  * waits for completion and report results using {@code Future}
110  * conventions. Method {@link #invoke} is semantically
111  * equivalent to {@code fork(); join()} but always attempts to begin
112  * execution in the current thread. The "<em>quiet</em>" forms of
113  * these methods do not extract results or report exceptions. These
114  * may be useful when a set of tasks are being executed, and you need
115  * to delay processing of results or exceptions until all complete.
116  * Method {@code invokeAll} (available in multiple versions)
117  * performs the most common form of parallel invocation: forking a set
118  * of tasks and joining them all.
119  *
120  * <p>In the most typical usages, a fork-join pair act like a call
121  * (fork) and return (join) from a parallel recursive function. As is
122  * the case with other forms of recursive calls, returns (joins)
123  * should be performed innermost-first. For example, {@code a.fork();
124  * b.fork(); b.join(); a.join();} is likely to be substantially more
125  * efficient than joining {@code a} before {@code b}.
126  *
127  * <p>The execution status of tasks may be queried at several levels
128  * of detail: {@link #isDone} is true if a task completed in any way
129  * (including the case where a task was cancelled without executing);
130  * {@link #isCompletedNormally} is true if a task completed without
131  * cancellation or encountering an exception; {@link #isCancelled} is
132  * true if the task was cancelled (in which case {@link #getException}
133  * returns a {@link java.util.concurrent.CancellationException}); and
134  * {@link #isCompletedAbnormally} is true if a task was either
135  * cancelled or encountered an exception, in which case {@link
136  * #getException} will return either the encountered exception or
137  * {@link java.util.concurrent.CancellationException}.
138  *
139  * <p>The ForkJoinTask class is not usually directly subclassed.
140  * Instead, you subclass one of the abstract classes that support a
141  * particular style of fork/join processing, typically {@link
142  * RecursiveAction} for most computations that do not return results,
143  * {@link RecursiveTask} for those that do, and {@link
144  * CountedCompleter} for those in which completed actions trigger
145  * other actions.  Normally, a concrete ForkJoinTask subclass declares
146  * fields comprising its parameters, established in a constructor, and
147  * then defines a {@code compute} method that somehow uses the control
148  * methods supplied by this base class.
149  *
150  * <p>Method {@link #join} and its variants are appropriate for use
151  * only when completion dependencies are acyclic; that is, the
152  * parallel computation can be described as a directed acyclic graph
153  * (DAG). Otherwise, executions may encounter a form of deadlock as
154  * tasks cyclically wait for each other.  However, this framework
155  * supports other methods and techniques (for example the use of
156  * {@link Phaser}, {@link #helpQuiesce}, and {@link #complete}) that
157  * may be of use in constructing custom subclasses for problems that
158  * are not statically structured as DAGs. To support such usages, a
159  * ForkJoinTask may be atomically <em>tagged</em> with a {@code short}
160  * value using {@link #setForkJoinTaskTag} or {@link
161  * #compareAndSetForkJoinTaskTag} and checked using {@link
162  * #getForkJoinTaskTag}. The ForkJoinTask implementation does not use
163  * these {@code protected} methods or tags for any purpose, but they
164  * may be of use in the construction of specialized subclasses.  For
165  * example, parallel graph traversals can use the supplied methods to
166  * avoid revisiting nodes/tasks that have already been processed.
167  * (Method names for tagging are bulky in part to encourage definition
168  * of methods that reflect their usage patterns.)
169  *
170  * <p>Most base support methods are {@code final}, to prevent
171  * overriding of implementations that are intrinsically tied to the
172  * underlying lightweight task scheduling framework.  Developers
173  * creating new basic styles of fork/join processing should minimally
174  * implement {@code protected} methods {@link #exec}, {@link
175  * #setRawResult}, and {@link #getRawResult}, while also introducing
176  * an abstract computational method that can be implemented in its
177  * subclasses, possibly relying on other {@code protected} methods
178  * provided by this class.
179  *
180  * <p>ForkJoinTasks should perform relatively small amounts of
181  * computation. Large tasks should be split into smaller subtasks,
182  * usually via recursive decomposition. As a very rough rule of thumb,
183  * a task should perform more than 100 and less than 10000 basic
184  * computational steps, and should avoid indefinite looping. If tasks
185  * are too big, then parallelism cannot improve throughput. If too
186  * small, then memory and internal task maintenance overhead may
187  * overwhelm processing.
188  *
189  * <p>This class provides {@code adapt} methods for {@link Runnable}
190  * and {@link Callable}, that may be of use when mixing execution of
191  * {@code ForkJoinTasks} with other kinds of tasks. When all tasks are
192  * of this form, consider using a pool constructed in <em>asyncMode</em>.
193  *
194  * <p>ForkJoinTasks are {@code Serializable}, which enables them to be
195  * used in extensions such as remote execution frameworks. It is
196  * sensible to serialize tasks only before or after, but not during,
197  * execution. Serialization is not relied on during execution itself.
198  *
199  * @since 1.7
200  * @author Doug Lea
201  */
202 @SuppressWarnings("all")
203 public abstract class ForkJoinTask<V> implements Future<V>, Serializable {
204 
205     /*
206      * See the internal documentation of class ForkJoinPool for a
207      * general implementation overview.  ForkJoinTasks are mainly
208      * responsible for maintaining their "status" field amidst relays
209      * to methods in ForkJoinWorkerThread and ForkJoinPool.
210      *
211      * The methods of this class are more-or-less layered into
212      * (1) basic status maintenance
213      * (2) execution and awaiting completion
214      * (3) user-level methods that additionally report results.
215      * This is sometimes hard to see because this file orders exported
216      * methods in a way that flows well in javadocs.
217      */
218 
219     /*
220      * The status field holds run control status bits packed into a
221      * single int to minimize footprint and to ensure atomicity (via
222      * CAS).  Status is initially zero, and takes on nonnegative
223      * values until completed, upon which status (anded with
224      * DONE_MASK) holds value NORMAL, CANCELLED, or EXCEPTIONAL. Tasks
225      * undergoing blocking waits by other threads have the SIGNAL bit
226      * set.  Completion of a stolen task with SIGNAL set awakens any
227      * waiters via notifyAll. Even though suboptimal for some
228      * purposes, we use basic builtin wait/notify to take advantage of
229      * "monitor inflation" in JVMs that we would otherwise need to
230      * emulate to avoid adding further per-task bookkeeping overhead.
231      * We want these monitors to be "fat", i.e., not use biasing or
232      * thin-lock techniques, so use some odd coding idioms that tend
233      * to avoid them, mainly by arranging that every synchronized
234      * block performs a wait, notifyAll or both.
235      *
236      * These control bits occupy only (some of) the upper half (16
237      * bits) of status field. The lower bits are used for user-defined
238      * tags.
239      */
240 
241     /** The run status of this task */
242     volatile int status; // accessed directly by pool and workers
243     static final int DONE_MASK   = 0xf0000000;  // mask out non-completion bits
244     static final int NORMAL      = 0xf0000000;  // must be negative
245     static final int CANCELLED   = 0xc0000000;  // must be < NORMAL
246     static final int EXCEPTIONAL = 0x80000000;  // must be < CANCELLED
247     static final int SIGNAL      = 0x00010000;  // must be >= 1 << 16
248     static final int SMASK       = 0x0000ffff;  // short bits for tags
249 
250     /**
251      * Marks completion and wakes up threads waiting to join this
252      * task.
253      *
254      * @param completion one of NORMAL, CANCELLED, EXCEPTIONAL
255      * @return completion status on exit
256      */
257     private int setCompletion(int completion) {
258         for (int s;;) {
259             if ((s = status) < 0)
260                 return s;
261             if (U.compareAndSwapInt(this, STATUS, s, s | completion)) {
262                 if ((s >>> 16) != 0)
263                     synchronized (this) { notifyAll(); }
264                 return completion;
265             }
266         }
267     }
268 
269     /**
270      * Primary execution method for stolen tasks. Unless done, calls
271      * exec and records status if completed, but doesn't wait for
272      * completion otherwise.
273      *
274      * @return status on exit from this method
275      */
276     final int doExec() {
277         int s; boolean completed;
278         if ((s = status) >= 0) {
279             try {
280                 completed = exec();
281             } catch (Throwable rex) {
282                 return setExceptionalCompletion(rex);
283             }
284             if (completed)
285                 s = setCompletion(NORMAL);
286         }
287         return s;
288     }
289 
290     /**
291      * Tries to set SIGNAL status unless already completed. Used by
292      * ForkJoinPool. Other variants are directly incorporated into
293      * externalAwaitDone etc.
294      *
295      * @return true if successful
296      */
297     final boolean trySetSignal() {
298         int s = status;
299         return s >= 0 && U.compareAndSwapInt(this, STATUS, s, s | SIGNAL);
300     }
301 
302     /**
303      * Blocks a non-worker-thread until completion.
304      * @return status upon completion
305      */
306     private int externalAwaitDone() {
307         int s;
308         ForkJoinPool cp = ForkJoinPool.common;
309         if ((s = status) >= 0) {
310             if (cp != null) {
311                 if (this instanceof CountedCompleter)
312                     s = cp.externalHelpComplete((CountedCompleter<?>)this);
313                 else if (cp.tryExternalUnpush(this))
314                     s = doExec();
315             }
316             if (s >= 0 && (s = status) >= 0) {
317                 boolean interrupted = false;
318                 do {
319                     if (U.compareAndSwapInt(this, STATUS, s, s | SIGNAL)) {
320                         synchronized (this) {
321                             if (status >= 0) {
322                                 try {
323                                     wait();
324                                 } catch (InterruptedException ie) {
325                                     interrupted = true;
326                                 }
327                             }
328                             else
329                                 notifyAll();
330                         }
331                     }
332                 } while ((s = status) >= 0);
333                 if (interrupted)
334                     Thread.currentThread().interrupt();
335             }
336         }
337         return s;
338     }
339 
340     /**
341      * Blocks a non-worker-thread until completion or interruption.
342      */
343     private int externalInterruptibleAwaitDone() throws InterruptedException {
344         int s;
345         ForkJoinPool cp = ForkJoinPool.common;
346         if (Thread.interrupted())
347             throw new InterruptedException();
348         if ((s = status) >= 0 && cp != null) {
349             if (this instanceof CountedCompleter)
350                 cp.externalHelpComplete((CountedCompleter<?>)this);
351             else if (cp.tryExternalUnpush(this))
352                 doExec();
353         }
354         while ((s = status) >= 0) {
355             if (U.compareAndSwapInt(this, STATUS, s, s | SIGNAL)) {
356                 synchronized (this) {
357                     if (status >= 0)
358                         wait();
359                     else
360                         notifyAll();
361                 }
362             }
363         }
364         return s;
365     }
366 
367 
368     /**
369      * Implementation for join, get, quietlyJoin. Directly handles
370      * only cases of already-completed, external wait, and
371      * unfork+exec.  Others are relayed to ForkJoinPool.awaitJoin.
372      *
373      * @return status upon completion
374      */
375     private int doJoin() {
376         int s; Thread t; ForkJoinWorkerThread wt; ForkJoinPool.WorkQueue w;
377         return (s = status) < 0 ? s :
378                 ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) ?
379                         (w = (wt = (ForkJoinWorkerThread)t).workQueue).
380                                 tryUnpush(this) && (s = doExec()) < 0 ? s :
381                                 wt.pool.awaitJoin(w, this) :
382                         externalAwaitDone();
383     }
384 
385     /**
386      * Implementation for invoke, quietlyInvoke.
387      *
388      * @return status upon completion
389      */
390     private int doInvoke() {
391         int s; Thread t; ForkJoinWorkerThread wt;
392         return (s = doExec()) < 0 ? s :
393                 ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) ?
394                         (wt = (ForkJoinWorkerThread)t).pool.awaitJoin(wt.workQueue, this) :
395                         externalAwaitDone();
396     }
397 
398     // Exception table support
399 
400     /**
401      * Table of exceptions thrown by tasks, to enable reporting by
402      * callers. Because exceptions are rare, we don't directly keep
403      * them with task objects, but instead use a weak ref table.  Note
404      * that cancellation exceptions don't appear in the table, but are
405      * instead recorded as status values.
406      *
407      * Note: These statics are initialized below in static block.
408      */
409     private static final ExceptionNode[] exceptionTable;
410     private static final ReentrantLock exceptionTableLock;
411     private static final ReferenceQueue<Object> exceptionTableRefQueue;
412 
413     /**
414      * Fixed capacity for exceptionTable.
415      */
416     private static final int EXCEPTION_MAP_CAPACITY = 32;
417 
418     /**
419      * Key-value nodes for exception table.  The chained hash table
420      * uses identity comparisons, full locking, and weak references
421      * for keys. The table has a fixed capacity because it only
422      * maintains task exceptions long enough for joiners to access
423      * them, so should never become very large for sustained
424      * periods. However, since we do not know when the last joiner
425      * completes, we must use weak references and expunge them. We do
426      * so on each operation (hence full locking). Also, some thread in
427      * any ForkJoinPool will call helpExpungeStaleExceptions when its
428      * pool becomes isQuiescent.
429      */
430     static final class ExceptionNode extends WeakReference<ForkJoinTask<?>> {
431         final Throwable ex;
432         ExceptionNode next;
433         final long thrower;  // use id not ref to avoid weak cycles
434         ExceptionNode(ForkJoinTask<?> task, Throwable ex, ExceptionNode next) {
435             super(task, exceptionTableRefQueue);
436             this.ex = ex;
437             this.next = next;
438             this.thrower = Thread.currentThread().getId();
439         }
440     }
441 
442     /**
443      * Records exception and sets status.
444      *
445      * @return status on exit
446      */
447     final int recordExceptionalCompletion(Throwable ex) {
448         int s;
449         if ((s = status) >= 0) {
450             int h = System.identityHashCode(this);
451             final ReentrantLock lock = exceptionTableLock;
452             lock.lock();
453             try {
454                 expungeStaleExceptions();
455                 ExceptionNode[] t = exceptionTable;
456                 int i = h & (t.length - 1);
457                 for (ExceptionNode e = t[i]; ; e = e.next) {
458                     if (e == null) {
459                         t[i] = new ExceptionNode(this, ex, t[i]);
460                         break;
461                     }
462                     if (e.get() == this) // already present
463                         break;
464                 }
465             } finally {
466                 lock.unlock();
467             }
468             s = setCompletion(EXCEPTIONAL);
469         }
470         return s;
471     }
472 
473     /**
474      * Records exception and possibly propagates.
475      *
476      * @return status on exit
477      */
478     private int setExceptionalCompletion(Throwable ex) {
479         int s = recordExceptionalCompletion(ex);
480         if ((s & DONE_MASK) == EXCEPTIONAL)
481             internalPropagateException(ex);
482         return s;
483     }
484 
485     /**
486      * Hook for exception propagation support for tasks with completers.
487      */
488     void internalPropagateException(Throwable ex) {
489     }
490 
491     /**
492      * Cancels, ignoring any exceptions thrown by cancel. Used during
493      * worker and pool shutdown. Cancel is spec'ed not to throw any
494      * exceptions, but if it does anyway, we have no recourse during
495      * shutdown, so guard against this case.
496      */
497     static final void cancelIgnoringExceptions(ForkJoinTask<?> t) {
498         if (t != null && t.status >= 0) {
499             try {
500                 t.cancel(false);
501             } catch (Throwable ignore) {
502             }
503         }
504     }
505 
506     /**
507      * Removes exception node and clears status.
508      */
509     private void clearExceptionalCompletion() {
510         int h = System.identityHashCode(this);
511         final ReentrantLock lock = exceptionTableLock;
512         lock.lock();
513         try {
514             ExceptionNode[] t = exceptionTable;
515             int i = h & (t.length - 1);
516             ExceptionNode e = t[i];
517             ExceptionNode pred = null;
518             while (e != null) {
519                 ExceptionNode next = e.next;
520                 if (e.get() == this) {
521                     if (pred == null)
522                         t[i] = next;
523                     else
524                         pred.next = next;
525                     break;
526                 }
527                 pred = e;
528                 e = next;
529             }
530             expungeStaleExceptions();
531             status = 0;
532         } finally {
533             lock.unlock();
534         }
535     }
536 
537     /**
538      * Returns a rethrowable exception for the given task, if
539      * available. To provide accurate stack traces, if the exception
540      * was not thrown by the current thread, we try to create a new
541      * exception of the same type as the one thrown, but with the
542      * recorded exception as its cause. If there is no such
543      * constructor, we instead try to use a no-arg constructor,
544      * followed by initCause, to the same effect. If none of these
545      * apply, or any fail due to other exceptions, we return the
546      * recorded exception, which is still correct, although it may
547      * contain a misleading stack trace.
548      *
549      * @return the exception, or null if none
550      */
551     private Throwable getThrowableException() {
552         if ((status & DONE_MASK) != EXCEPTIONAL)
553             return null;
554         int h = System.identityHashCode(this);
555         ExceptionNode e;
556         final ReentrantLock lock = exceptionTableLock;
557         lock.lock();
558         try {
559             expungeStaleExceptions();
560             ExceptionNode[] t = exceptionTable;
561             e = t[h & (t.length - 1)];
562             while (e != null && e.get() != this)
563                 e = e.next;
564         } finally {
565             lock.unlock();
566         }
567         Throwable ex;
568         if (e == null || (ex = e.ex) == null)
569             return null;
570         if (false && e.thrower != Thread.currentThread().getId()) {
571             Class<? extends Throwable> ec = ex.getClass();
572             try {
573                 Constructor<?> noArgCtor = null;
574                 Constructor<?>[] cs = ec.getConstructors();// public ctors only
575                 for (int i = 0; i < cs.length; ++i) {
576                     Constructor<?> c = cs[i];
577                     Class<?>[] ps = c.getParameterTypes();
578                     if (ps.length == 0)
579                         noArgCtor = c;
580                     else if (ps.length == 1 && ps[0] == Throwable.class)
581                         return (Throwable)(c.newInstance(ex));
582                 }
583                 if (noArgCtor != null) {
584                     Throwable wx = (Throwable)(noArgCtor.newInstance());
585                     wx.initCause(ex);
586                     return wx;
587                 }
588             } catch (Exception ignore) {
589             }
590         }
591         return ex;
592     }
593 
594     /**
595      * Poll stale refs and remove them. Call only while holding lock.
596      */
597     private static void expungeStaleExceptions() {
598         for (Object x; (x = exceptionTableRefQueue.poll()) != null;) {
599             if (x instanceof ExceptionNode) {
600                 ForkJoinTask<?> key = ((ExceptionNode)x).get();
601                 ExceptionNode[] t = exceptionTable;
602                 int i = System.identityHashCode(key) & (t.length - 1);
603                 ExceptionNode e = t[i];
604                 ExceptionNode pred = null;
605                 while (e != null) {
606                     ExceptionNode next = e.next;
607                     if (e == x) {
608                         if (pred == null)
609                             t[i] = next;
610                         else
611                             pred.next = next;
612                         break;
613                     }
614                     pred = e;
615                     e = next;
616                 }
617             }
618         }
619     }
620 
621     /**
622      * If lock is available, poll stale refs and remove them.
623      * Called from ForkJoinPool when pools become quiescent.
624      */
625     static final void helpExpungeStaleExceptions() {
626         final ReentrantLock lock = exceptionTableLock;
627         if (lock.tryLock()) {
628             try {
629                 expungeStaleExceptions();
630             } finally {
631                 lock.unlock();
632             }
633         }
634     }
635 
636     /**
637      * A version of "sneaky throw" to relay exceptions
638      */
639     static void rethrow(Throwable ex) {
640         if (ex != null)
641             ForkJoinTask.<RuntimeException>uncheckedThrow(ex);
642     }
643 
644     /**
645      * The sneaky part of sneaky throw, relying on generics
646      * limitations to evade compiler complaints about rethrowing
647      * unchecked exceptions
648      */
649     @SuppressWarnings("unchecked") static <T extends Throwable>
650     void uncheckedThrow(Throwable t) throws T {
651         throw (T)t; // rely on vacuous cast
652     }
653 
654     /**
655      * Throws exception, if any, associated with the given status.
656      */
657     private void reportException(int s) {
658         if (s == CANCELLED)
659             throw new CancellationException();
660         if (s == EXCEPTIONAL)
661             rethrow(getThrowableException());
662     }
663 
664     // public methods
665 
666     /**
667      * Arranges to asynchronously execute this task in the pool the
668      * current task is running in, if applicable, or using the {@link
669      * ForkJoinPool#commonPool()} if not {@link #inForkJoinPool}.  While
670      * it is not necessarily enforced, it is a usage error to fork a
671      * task more than once unless it has completed and been
672      * reinitialized.  Subsequent modifications to the state of this
673      * task or any data it operates on are not necessarily
674      * consistently observable by any thread other than the one
675      * executing it unless preceded by a call to {@link #join} or
676      * related methods, or a call to {@link #isDone} returning {@code
677      * true}.
678      *
679      * @return {@code this}, to simplify usage
680      */
681     public final ForkJoinTask<V> fork() {
682         Thread t;
683         if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread)
684             ((ForkJoinWorkerThread)t).workQueue.push(this);
685         else
686             ForkJoinPool.common.externalPush(this);
687         return this;
688     }
689 
690     /**
691      * Returns the result of the computation when it {@link #isDone is
692      * done}.  This method differs from {@link #get()} in that
693      * abnormal completion results in {@code RuntimeException} or
694      * {@code Error}, not {@code ExecutionException}, and that
695      * interrupts of the calling thread do <em>not</em> cause the
696      * method to abruptly return by throwing {@code
697      * InterruptedException}.
698      *
699      * @return the computed result
700      */
701     public final V join() {
702         int s;
703         if ((s = doJoin() & DONE_MASK) != NORMAL)
704             reportException(s);
705         return getRawResult();
706     }
707 
708     /**
709      * Commences performing this task, awaits its completion if
710      * necessary, and returns its result, or throws an (unchecked)
711      * {@code RuntimeException} or {@code Error} if the underlying
712      * computation did so.
713      *
714      * @return the computed result
715      */
716     public final V invoke() {
717         int s;
718         if ((s = doInvoke() & DONE_MASK) != NORMAL)
719             reportException(s);
720         return getRawResult();
721     }
722 
723     /**
724      * Forks the given tasks, returning when {@code isDone} holds for
725      * each task or an (unchecked) exception is encountered, in which
726      * case the exception is rethrown. If more than one task
727      * encounters an exception, then this method throws any one of
728      * these exceptions. If any task encounters an exception, the
729      * other may be cancelled. However, the execution status of
730      * individual tasks is not guaranteed upon exceptional return. The
731      * status of each task may be obtained using {@link
732      * #getException()} and related methods to check if they have been
733      * cancelled, completed normally or exceptionally, or left
734      * unprocessed.
735      *
736      * @param t1 the first task
737      * @param t2 the second task
738      * @throws NullPointerException if any task is null
739      */
740     public static void invokeAll(ForkJoinTask<?> t1, ForkJoinTask<?> t2) {
741         int s1, s2;
742         t2.fork();
743         if ((s1 = t1.doInvoke() & DONE_MASK) != NORMAL)
744             t1.reportException(s1);
745         if ((s2 = t2.doJoin() & DONE_MASK) != NORMAL)
746             t2.reportException(s2);
747     }
748 
749     /**
750      * Forks the given tasks, returning when {@code isDone} holds for
751      * each task or an (unchecked) exception is encountered, in which
752      * case the exception is rethrown. If more than one task
753      * encounters an exception, then this method throws any one of
754      * these exceptions. If any task encounters an exception, others
755      * may be cancelled. However, the execution status of individual
756      * tasks is not guaranteed upon exceptional return. The status of
757      * each task may be obtained using {@link #getException()} and
758      * related methods to check if they have been cancelled, completed
759      * normally or exceptionally, or left unprocessed.
760      *
761      * @param tasks the tasks
762      * @throws NullPointerException if any task is null
763      */
764     public static void invokeAll(ForkJoinTask<?>... tasks) {
765         Throwable ex = null;
766         int last = tasks.length - 1;
767         for (int i = last; i >= 0; --i) {
768             ForkJoinTask<?> t = tasks[i];
769             if (t == null) {
770                 if (ex == null)
771                     ex = new NullPointerException();
772             }
773             else if (i != 0)
774                 t.fork();
775             else if (t.doInvoke() < NORMAL && ex == null)
776                 ex = t.getException();
777         }
778         for (int i = 1; i <= last; ++i) {
779             ForkJoinTask<?> t = tasks[i];
780             if (t != null) {
781                 if (ex != null)
782                     t.cancel(false);
783                 else if (t.doJoin() < NORMAL)
784                     ex = t.getException();
785             }
786         }
787         if (ex != null)
788             rethrow(ex);
789     }
790 
791     /**
792      * Forks all tasks in the specified collection, returning when
793      * {@code isDone} holds for each task or an (unchecked) exception
794      * is encountered, in which case the exception is rethrown. If
795      * more than one task encounters an exception, then this method
796      * throws any one of these exceptions. If any task encounters an
797      * exception, others may be cancelled. However, the execution
798      * status of individual tasks is not guaranteed upon exceptional
799      * return. The status of each task may be obtained using {@link
800      * #getException()} and related methods to check if they have been
801      * cancelled, completed normally or exceptionally, or left
802      * unprocessed.
803      *
804      * @param tasks the collection of tasks
805      * @return the tasks argument, to simplify usage
806      * @throws NullPointerException if tasks or any element are null
807      */
808     public static <T extends ForkJoinTask<?>> Collection<T> invokeAll(Collection<T> tasks) {
809         if (!(tasks instanceof RandomAccess) || !(tasks instanceof List<?>)) {
810             invokeAll(tasks.toArray(new ForkJoinTask<?>[tasks.size()]));
811             return tasks;
812         }
813         @SuppressWarnings("unchecked")
814         List<? extends ForkJoinTask<?>> ts =
815                 (List<? extends ForkJoinTask<?>>) tasks;
816         Throwable ex = null;
817         int last = ts.size() - 1;
818         for (int i = last; i >= 0; --i) {
819             ForkJoinTask<?> t = ts.get(i);
820             if (t == null) {
821                 if (ex == null)
822                     ex = new NullPointerException();
823             }
824             else if (i != 0)
825                 t.fork();
826             else if (t.doInvoke() < NORMAL && ex == null)
827                 ex = t.getException();
828         }
829         for (int i = 1; i <= last; ++i) {
830             ForkJoinTask<?> t = ts.get(i);
831             if (t != null) {
832                 if (ex != null)
833                     t.cancel(false);
834                 else if (t.doJoin() < NORMAL)
835                     ex = t.getException();
836             }
837         }
838         if (ex != null)
839             rethrow(ex);
840         return tasks;
841     }
842 
843     /**
844      * Attempts to cancel execution of this task. This attempt will
845      * fail if the task has already completed or could not be
846      * cancelled for some other reason. If successful, and this task
847      * has not started when {@code cancel} is called, execution of
848      * this task is suppressed. After this method returns
849      * successfully, unless there is an intervening call to {@link
850      * #reinitialize}, subsequent calls to {@link #isCancelled},
851      * {@link #isDone}, and {@code cancel} will return {@code true}
852      * and calls to {@link #join} and related methods will result in
853      * {@code CancellationException}.
854      *
855      * <p>This method may be overridden in subclasses, but if so, must
856      * still ensure that these properties hold. In particular, the
857      * {@code cancel} method itself must not throw exceptions.
858      *
859      * <p>This method is designed to be invoked by <em>other</em>
860      * tasks. To terminate the current task, you can just return or
861      * throw an unchecked exception from its computation method, or
862      * invoke {@link #completeExceptionally(Throwable)}.
863      *
864      * @param mayInterruptIfRunning this value has no effect in the
865      * default implementation because interrupts are not used to
866      * control cancellation.
867      *
868      * @return {@code true} if this task is now cancelled
869      */
870     public boolean cancel(boolean mayInterruptIfRunning) {
871         return (setCompletion(CANCELLED) & DONE_MASK) == CANCELLED;
872     }
873 
874     public final boolean isDone() {
875         return status < 0;
876     }
877 
878     public final boolean isCancelled() {
879         return (status & DONE_MASK) == CANCELLED;
880     }
881 
882     /**
883      * Returns {@code true} if this task threw an exception or was cancelled.
884      *
885      * @return {@code true} if this task threw an exception or was cancelled
886      */
887     public final boolean isCompletedAbnormally() {
888         return status < NORMAL;
889     }
890 
891     /**
892      * Returns {@code true} if this task completed without throwing an
893      * exception and was not cancelled.
894      *
895      * @return {@code true} if this task completed without throwing an
896      * exception and was not cancelled
897      */
898     public final boolean isCompletedNormally() {
899         return (status & DONE_MASK) == NORMAL;
900     }
901 
902     /**
903      * Returns the exception thrown by the base computation, or a
904      * {@code CancellationException} if cancelled, or {@code null} if
905      * none or if the method has not yet completed.
906      *
907      * @return the exception, or {@code null} if none
908      */
909     public final Throwable getException() {
910         int s = status & DONE_MASK;
911         return ((s >= NORMAL)    ? null :
912                 (s == CANCELLED) ? new CancellationException() :
913                         getThrowableException());
914     }
915 
916     /**
917      * Completes this task abnormally, and if not already aborted or
918      * cancelled, causes it to throw the given exception upon
919      * {@code join} and related operations. This method may be used
920      * to induce exceptions in asynchronous tasks, or to force
921      * completion of tasks that would not otherwise complete.  Its use
922      * in other situations is discouraged.  This method is
923      * overridable, but overridden versions must invoke {@code super}
924      * implementation to maintain guarantees.
925      *
926      * @param ex the exception to throw. If this exception is not a
927      * {@code RuntimeException} or {@code Error}, the actual exception
928      * thrown will be a {@code RuntimeException} with cause {@code ex}.
929      */
930     public void completeExceptionally(Throwable ex) {
931         setExceptionalCompletion((ex instanceof RuntimeException) ||
932                 (ex instanceof Error) ? ex :
933                 new RuntimeException(ex));
934     }
935 
936     /**
937      * Completes this task, and if not already aborted or cancelled,
938      * returning the given value as the result of subsequent
939      * invocations of {@code join} and related operations. This method
940      * may be used to provide results for asynchronous tasks, or to
941      * provide alternative handling for tasks that would not otherwise
942      * complete normally. Its use in other situations is
943      * discouraged. This method is overridable, but overridden
944      * versions must invoke {@code super} implementation to maintain
945      * guarantees.
946      *
947      * @param value the result value for this task
948      */
949     public void complete(V value) {
950         try {
951             setRawResult(value);
952         } catch (Throwable rex) {
953             setExceptionalCompletion(rex);
954             return;
955         }
956         setCompletion(NORMAL);
957     }
958 
959     /**
960      * Completes this task normally without setting a value. The most
961      * recent value established by {@link #setRawResult} (or {@code
962      * null} by default) will be returned as the result of subsequent
963      * invocations of {@code join} and related operations.
964      *
965      * @since 1.8
966      */
967     public final void quietlyComplete() {
968         setCompletion(NORMAL);
969     }
970 
971     /**
972      * Waits if necessary for the computation to complete, and then
973      * retrieves its result.
974      *
975      * @return the computed result
976      * @throws CancellationException if the computation was cancelled
977      * @throws ExecutionException if the computation threw an
978      * exception
979      * @throws InterruptedException if the current thread is not a
980      * member of a ForkJoinPool and was interrupted while waiting
981      */
982     public final V get() throws InterruptedException, ExecutionException {
983         int s = (Thread.currentThread() instanceof ForkJoinWorkerThread) ?
984                 doJoin() : externalInterruptibleAwaitDone();
985         Throwable ex;
986         if ((s &= DONE_MASK) == CANCELLED)
987             throw new CancellationException();
988         if (s == EXCEPTIONAL && (ex = getThrowableException()) != null)
989             throw new ExecutionException(ex);
990         return getRawResult();
991     }
992 
993     /**
994      * Waits if necessary for at most the given time for the computation
995      * to complete, and then retrieves its result, if available.
996      *
997      * @param timeout the maximum time to wait
998      * @param unit the time unit of the timeout argument
999      * @return the computed result
1000      * @throws CancellationException if the computation was cancelled
1001      * @throws ExecutionException if the computation threw an
1002      * exception
1003      * @throws InterruptedException if the current thread is not a
1004      * member of a ForkJoinPool and was interrupted while waiting
1005      * @throws TimeoutException if the wait timed out
1006      */
1007     public final V get(long timeout, TimeUnit unit)
1008             throws InterruptedException, ExecutionException, TimeoutException {
1009         if (Thread.interrupted())
1010             throw new InterruptedException();
1011         // Messy in part because we measure in nanosecs, but wait in millisecs
1012         int s; long ms;
1013         long ns = unit.toNanos(timeout);
1014         ForkJoinPool cp;
1015         if ((s = status) >= 0 && ns > 0L) {
1016             long deadline = System.nanoTime() + ns;
1017             ForkJoinPool p = null;
1018             ForkJoinPool.WorkQueue w = null;
1019             Thread t = Thread.currentThread();
1020             if (t instanceof ForkJoinWorkerThread) {
1021                 ForkJoinWorkerThread wt = (ForkJoinWorkerThread)t;
1022                 p = wt.pool;
1023                 w = wt.workQueue;
1024                 p.helpJoinOnce(w, this); // no retries on failure
1025             }
1026             else if ((cp = ForkJoinPool.common) != null) {
1027                 if (this instanceof CountedCompleter)
1028                     cp.externalHelpComplete((CountedCompleter<?>)this);
1029                 else if (cp.tryExternalUnpush(this))
1030                     doExec();
1031             }
1032             boolean canBlock = false;
1033             boolean interrupted = false;
1034             try {
1035                 while ((s = status) >= 0) {
1036                     if (w != null && w.qlock < 0)
1037                         cancelIgnoringExceptions(this);
1038                     else if (!canBlock) {
1039                         if (p == null || p.tryCompensate(p.ctl))
1040                             canBlock = true;
1041                     }
1042                     else {
1043                         if ((ms = TimeUnit.NANOSECONDS.toMillis(ns)) > 0L &&
1044                                 U.compareAndSwapInt(this, STATUS, s, s | SIGNAL)) {
1045                             synchronized (this) {
1046                                 if (status >= 0) {
1047                                     try {
1048                                         wait(ms);
1049                                     } catch (InterruptedException ie) {
1050                                         if (p == null)
1051                                             interrupted = true;
1052                                     }
1053                                 }
1054                                 else
1055                                     notifyAll();
1056                             }
1057                         }
1058                         if ((s = status) < 0 || interrupted ||
1059                                 (ns = deadline - System.nanoTime()) <= 0L)
1060                             break;
1061                     }
1062                 }
1063             } finally {
1064                 if (p != null && canBlock)
1065                     p.incrementActiveCount();
1066             }
1067             if (interrupted)
1068                 throw new InterruptedException();
1069         }
1070         if ((s &= DONE_MASK) != NORMAL) {
1071             Throwable ex;
1072             if (s == CANCELLED)
1073                 throw new CancellationException();
1074             if (s != EXCEPTIONAL)
1075                 throw new TimeoutException();
1076             if ((ex = getThrowableException()) != null)
1077                 throw new ExecutionException(ex);
1078         }
1079         return getRawResult();
1080     }
1081 
1082     /**
1083      * Joins this task, without returning its result or throwing its
1084      * exception. This method may be useful when processing
1085      * collections of tasks when some have been cancelled or otherwise
1086      * known to have aborted.
1087      */
1088     public final void quietlyJoin() {
1089         doJoin();
1090     }
1091 
1092     /**
1093      * Commences performing this task and awaits its completion if
1094      * necessary, without returning its result or throwing its
1095      * exception.
1096      */
1097     public final void quietlyInvoke() {
1098         doInvoke();
1099     }
1100 
1101     /**
1102      * Possibly executes tasks until the pool hosting the current task
1103      * {@link ForkJoinPool#isQuiescent is quiescent}. This method may
1104      * be of use in designs in which many tasks are forked, but none
1105      * are explicitly joined, instead executing them until all are
1106      * processed.
1107      */
1108     public static void helpQuiesce() {
1109         Thread t;
1110         if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) {
1111             ForkJoinWorkerThread wt = (ForkJoinWorkerThread)t;
1112             wt.pool.helpQuiescePool(wt.workQueue);
1113         }
1114         else
1115             ForkJoinPool.quiesceCommonPool();
1116     }
1117 
1118     /**
1119      * Resets the internal bookkeeping state of this task, allowing a
1120      * subsequent {@code fork}. This method allows repeated reuse of
1121      * this task, but only if reuse occurs when this task has either
1122      * never been forked, or has been forked, then completed and all
1123      * outstanding joins of this task have also completed. Effects
1124      * under any other usage conditions are not guaranteed.
1125      * This method may be useful when executing
1126      * pre-constructed trees of subtasks in loops.
1127      *
1128      * <p>Upon completion of this method, {@code isDone()} reports
1129      * {@code false}, and {@code getException()} reports {@code
1130      * null}. However, the value returned by {@code getRawResult} is
1131      * unaffected. To clear this value, you can invoke {@code
1132      * setRawResult(null)}.
1133      */
1134     public void reinitialize() {
1135         if ((status & DONE_MASK) == EXCEPTIONAL)
1136             clearExceptionalCompletion();
1137         else
1138             status = 0;
1139     }
1140 
1141     /**
1142      * Returns the pool hosting the current task execution, or null
1143      * if this task is executing outside of any ForkJoinPool.
1144      *
1145      * @see #inForkJoinPool
1146      * @return the pool, or {@code null} if none
1147      */
1148     public static ForkJoinPool getPool() {
1149         Thread t = Thread.currentThread();
1150         return (t instanceof ForkJoinWorkerThread) ?
1151                 ((ForkJoinWorkerThread) t).pool : null;
1152     }
1153 
1154     /**
1155      * Returns {@code true} if the current thread is a {@link
1156      * ForkJoinWorkerThread} executing as a ForkJoinPool computation.
1157      *
1158      * @return {@code true} if the current thread is a {@link
1159      * ForkJoinWorkerThread} executing as a ForkJoinPool computation,
1160      * or {@code false} otherwise
1161      */
1162     public static boolean inForkJoinPool() {
1163         return Thread.currentThread() instanceof ForkJoinWorkerThread;
1164     }
1165 
1166     /**
1167      * Tries to unschedule this task for execution. This method will
1168      * typically (but is not guaranteed to) succeed if this task is
1169      * the most recently forked task by the current thread, and has
1170      * not commenced executing in another thread.  This method may be
1171      * useful when arranging alternative local processing of tasks
1172      * that could have been, but were not, stolen.
1173      *
1174      * @return {@code true} if unforked
1175      */
1176     public boolean tryUnfork() {
1177         Thread t;
1178         return (((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) ?
1179                 ((ForkJoinWorkerThread)t).workQueue.tryUnpush(this) :
1180                 ForkJoinPool.common.tryExternalUnpush(this));
1181     }
1182 
1183     /**
1184      * Returns an estimate of the number of tasks that have been
1185      * forked by the current worker thread but not yet executed. This
1186      * value may be useful for heuristic decisions about whether to
1187      * fork other tasks.
1188      *
1189      * @return the number of tasks
1190      */
1191     public static int getQueuedTaskCount() {
1192         Thread t; ForkJoinPool.WorkQueue q;
1193         if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread)
1194             q = ((ForkJoinWorkerThread)t).workQueue;
1195         else
1196             q = ForkJoinPool.commonSubmitterQueue();
1197         return (q == null) ? 0 : q.queueSize();
1198     }
1199 
1200     /**
1201      * Returns an estimate of how many more locally queued tasks are
1202      * held by the current worker thread than there are other worker
1203      * threads that might steal them, or zero if this thread is not
1204      * operating in a ForkJoinPool. This value may be useful for
1205      * heuristic decisions about whether to fork other tasks. In many
1206      * usages of ForkJoinTasks, at steady state, each worker should
1207      * aim to maintain a small constant surplus (for example, 3) of
1208      * tasks, and to process computations locally if this threshold is
1209      * exceeded.
1210      *
1211      * @return the surplus number of tasks, which may be negative
1212      */
1213     public static int getSurplusQueuedTaskCount() {
1214         return ForkJoinPool.getSurplusQueuedTaskCount();
1215     }
1216 
1217     // Extension methods
1218 
1219     /**
1220      * Returns the result that would be returned by {@link #join}, even
1221      * if this task completed abnormally, or {@code null} if this task
1222      * is not known to have been completed.  This method is designed
1223      * to aid debugging, as well as to support extensions. Its use in
1224      * any other context is discouraged.
1225      *
1226      * @return the result, or {@code null} if not completed
1227      */
1228     public abstract V getRawResult();
1229 
1230     /**
1231      * Forces the given value to be returned as a result.  This method
1232      * is designed to support extensions, and should not in general be
1233      * called otherwise.
1234      *
1235      * @param value the value
1236      */
1237     protected abstract void setRawResult(V value);
1238 
1239     /**
1240      * Immediately performs the base action of this task and returns
1241      * true if, upon return from this method, this task is guaranteed
1242      * to have completed normally. This method may return false
1243      * otherwise, to indicate that this task is not necessarily
1244      * complete (or is not known to be complete), for example in
1245      * asynchronous actions that require explicit invocations of
1246      * completion methods. This method may also throw an (unchecked)
1247      * exception to indicate abnormal exit. This method is designed to
1248      * support extensions, and should not in general be called
1249      * otherwise.
1250      *
1251      * @return {@code true} if this task is known to have completed normally
1252      */
1253     protected abstract boolean exec();
1254 
1255     /**
1256      * Returns, but does not unschedule or execute, a task queued by
1257      * the current thread but not yet executed, if one is immediately
1258      * available. There is no guarantee that this task will actually
1259      * be polled or executed next. Conversely, this method may return
1260      * null even if a task exists but cannot be accessed without
1261      * contention with other threads.  This method is designed
1262      * primarily to support extensions, and is unlikely to be useful
1263      * otherwise.
1264      *
1265      * @return the next task, or {@code null} if none are available
1266      */
1267     protected static ForkJoinTask<?> peekNextLocalTask() {
1268         Thread t; ForkJoinPool.WorkQueue q;
1269         if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread)
1270             q = ((ForkJoinWorkerThread)t).workQueue;
1271         else
1272             q = ForkJoinPool.commonSubmitterQueue();
1273         return (q == null) ? null : q.peek();
1274     }
1275 
1276     /**
1277      * Unschedules and returns, without executing, the next task
1278      * queued by the current thread but not yet executed, if the
1279      * current thread is operating in a ForkJoinPool.  This method is
1280      * designed primarily to support extensions, and is unlikely to be
1281      * useful otherwise.
1282      *
1283      * @return the next task, or {@code null} if none are available
1284      */
1285     protected static ForkJoinTask<?> pollNextLocalTask() {
1286         Thread t;
1287         return ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) ?
1288                 ((ForkJoinWorkerThread)t).workQueue.nextLocalTask() :
1289                 null;
1290     }
1291 
1292     /**
1293      * If the current thread is operating in a ForkJoinPool,
1294      * unschedules and returns, without executing, the next task
1295      * queued by the current thread but not yet executed, if one is
1296      * available, or if not available, a task that was forked by some
1297      * other thread, if available. Availability may be transient, so a
1298      * {@code null} result does not necessarily imply quiescence of
1299      * the pool this task is operating in.  This method is designed
1300      * primarily to support extensions, and is unlikely to be useful
1301      * otherwise.
1302      *
1303      * @return a task, or {@code null} if none are available
1304      */
1305     protected static ForkJoinTask<?> pollTask() {
1306         Thread t; ForkJoinWorkerThread wt;
1307         return ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) ?
1308                 (wt = (ForkJoinWorkerThread)t).pool.nextTaskFor(wt.workQueue) :
1309                 null;
1310     }
1311 
1312     // tag operations
1313 
1314     /**
1315      * Returns the tag for this task.
1316      *
1317      * @return the tag for this task
1318      * @since 1.8
1319      */
1320     public final short getForkJoinTaskTag() {
1321         return (short)status;
1322     }
1323 
1324     /**
1325      * Atomically sets the tag value for this task.
1326      *
1327      * @param tag the tag value
1328      * @return the previous value of the tag
1329      * @since 1.8
1330      */
1331     public final short setForkJoinTaskTag(short tag) {
1332         for (int s;;) {
1333             if (U.compareAndSwapInt(this, STATUS, s = status,
1334                     (s & ~SMASK) | (tag & SMASK)))
1335                 return (short)s;
1336         }
1337     }
1338 
1339     /**
1340      * Atomically conditionally sets the tag value for this task.
1341      * Among other applications, tags can be used as visit markers
1342      * in tasks operating on graphs, as in methods that check: {@code
1343      * if (task.compareAndSetForkJoinTaskTag((short)0, (short)1))}
1344      * before processing, otherwise exiting because the node has
1345      * already been visited.
1346      *
1347      * @param e the expected tag value
1348      * @param tag the new tag value
1349      * @return {@code true} if successful; i.e., the current value was
1350      * equal to e and is now tag.
1351      * @since 1.8
1352      */
1353     public final boolean compareAndSetForkJoinTaskTag(short e, short tag) {
1354         for (int s;;) {
1355             if ((short)(s = status) != e)
1356                 return false;
1357             if (U.compareAndSwapInt(this, STATUS, s,
1358                     (s & ~SMASK) | (tag & SMASK)))
1359                 return true;
1360         }
1361     }
1362 
1363     /**
1364      * Adaptor for Runnables. This implements RunnableFuture
1365      * to be compliant with AbstractExecutorService constraints
1366      * when used in ForkJoinPool.
1367      */
1368     static final class AdaptedRunnable<T> extends ForkJoinTask<T>
1369             implements RunnableFuture<T> {
1370         final Runnable runnable;
1371         T result;
1372         AdaptedRunnable(Runnable runnable, T result) {
1373             if (runnable == null) throw new NullPointerException();
1374             this.runnable = runnable;
1375             this.result = result; // OK to set this even before completion
1376         }
1377         public final T getRawResult() { return result; }
1378         public final void setRawResult(T v) { result = v; }
1379         public final boolean exec() { runnable.run(); return true; }
1380         public final void run() { invoke(); }
1381         private static final long serialVersionUID = 5232453952276885070L;
1382     }
1383 
1384     /**
1385      * Adaptor for Runnables without results
1386      */
1387     static final class AdaptedRunnableAction extends ForkJoinTask<Void>
1388             implements RunnableFuture<Void> {
1389         final Runnable runnable;
1390         AdaptedRunnableAction(Runnable runnable) {
1391             if (runnable == null) throw new NullPointerException();
1392             this.runnable = runnable;
1393         }
1394         public final Void getRawResult() { return null; }
1395         public final void setRawResult(Void v) { }
1396         public final boolean exec() { runnable.run(); return true; }
1397         public final void run() { invoke(); }
1398         private static final long serialVersionUID = 5232453952276885070L;
1399     }
1400 
1401     /**
1402      * Adaptor for Runnables in which failure forces worker exception
1403      */
1404     static final class RunnableExecuteAction extends ForkJoinTask<Void> {
1405         final Runnable runnable;
1406         RunnableExecuteAction(Runnable runnable) {
1407             if (runnable == null) throw new NullPointerException();
1408             this.runnable = runnable;
1409         }
1410         public final Void getRawResult() { return null; }
1411         public final void setRawResult(Void v) { }
1412         public final boolean exec() { runnable.run(); return true; }
1413         void internalPropagateException(Throwable ex) {
1414             rethrow(ex); // rethrow outside exec() catches.
1415         }
1416         private static final long serialVersionUID = 5232453952276885070L;
1417     }
1418 
1419     /**
1420      * Adaptor for Callables
1421      */
1422     static final class AdaptedCallable<T> extends ForkJoinTask<T>
1423             implements RunnableFuture<T> {
1424         final Callable<? extends T> callable;
1425         T result;
1426         AdaptedCallable(Callable<? extends T> callable) {
1427             if (callable == null) throw new NullPointerException();
1428             this.callable = callable;
1429         }
1430         public final T getRawResult() { return result; }
1431         public final void setRawResult(T v) { result = v; }
1432         public final boolean exec() {
1433             try {
1434                 result = callable.call();
1435                 return true;
1436             } catch (Error err) {
1437                 throw err;
1438             } catch (RuntimeException rex) {
1439                 throw rex;
1440             } catch (Exception ex) {
1441                 throw new RuntimeException(ex);
1442             }
1443         }
1444         public final void run() { invoke(); }
1445         private static final long serialVersionUID = 2838392045355241008L;
1446     }
1447 
1448     /**
1449      * Returns a new {@code ForkJoinTask} that performs the {@code run}
1450      * method of the given {@code Runnable} as its action, and returns
1451      * a null result upon {@link #join}.
1452      *
1453      * @param runnable the runnable action
1454      * @return the task
1455      */
1456     public static ForkJoinTask<?> adapt(Runnable runnable) {
1457         return new AdaptedRunnableAction(runnable);
1458     }
1459 
1460     /**
1461      * Returns a new {@code ForkJoinTask} that performs the {@code run}
1462      * method of the given {@code Runnable} as its action, and returns
1463      * the given result upon {@link #join}.
1464      *
1465      * @param runnable the runnable action
1466      * @param result the result upon completion
1467      * @return the task
1468      */
1469     public static <T> ForkJoinTask<T> adapt(Runnable runnable, T result) {
1470         return new AdaptedRunnable<T>(runnable, result);
1471     }
1472 
1473     /**
1474      * Returns a new {@code ForkJoinTask} that performs the {@code call}
1475      * method of the given {@code Callable} as its action, and returns
1476      * its result upon {@link #join}, translating any checked exceptions
1477      * encountered into {@code RuntimeException}.
1478      *
1479      * @param callable the callable action
1480      * @return the task
1481      */
1482     public static <T> ForkJoinTask<T> adapt(Callable<? extends T> callable) {
1483         return new AdaptedCallable<T>(callable);
1484     }
1485 
1486     // Serialization support
1487 
1488     private static final long serialVersionUID = -7721805057305804111L;
1489 
1490     /**
1491      * Saves this task to a stream (that is, serializes it).
1492      *
1493      * @serialData the current run status and the exception thrown
1494      * during execution, or {@code null} if none
1495      */
1496     private void writeObject(java.io.ObjectOutputStream s)
1497             throws java.io.IOException {
1498         s.defaultWriteObject();
1499         s.writeObject(getException());
1500     }
1501 
1502     /**
1503      * Reconstitutes this task from a stream (that is, deserializes it).
1504      */
1505     private void readObject(java.io.ObjectInputStream s)
1506             throws java.io.IOException, ClassNotFoundException {
1507         s.defaultReadObject();
1508         Object ex = s.readObject();
1509         if (ex != null)
1510             setExceptionalCompletion((Throwable)ex);
1511     }
1512 
1513     // Unsafe mechanics
1514     private static final sun.misc.Unsafe U;
1515     private static final long STATUS;
1516 
1517     static {
1518         exceptionTableLock = new ReentrantLock();
1519         exceptionTableRefQueue = new ReferenceQueue<Object>();
1520         exceptionTable = new ExceptionNode[EXCEPTION_MAP_CAPACITY];
1521         try {
1522             U = getUnsafe();
1523             Class<?> k = ForkJoinTask.class;
1524             STATUS = U.objectFieldOffset
1525                     (k.getDeclaredField("status"));
1526         } catch (Exception e) {
1527             throw new Error(e);
1528         }
1529     }
1530 
1531     /**
1532      * Returns a sun.misc.Unsafe.  Suitable for use in a 3rd party package.
1533      * Replace with a simple call to Unsafe.getUnsafe when integrating
1534      * into a jdk.
1535      *
1536      * @return a sun.misc.Unsafe
1537      */
1538     private static sun.misc.Unsafe getUnsafe() {
1539         try {
1540             return sun.misc.Unsafe.getUnsafe();
1541         } catch (SecurityException tryReflectionInstead) {}
1542         try {
1543             return java.security.AccessController.doPrivileged
1544                     (new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
1545                         public sun.misc.Unsafe run() throws Exception {
1546                             Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
1547                             for (java.lang.reflect.Field f : k.getDeclaredFields()) {
1548                                 f.setAccessible(true);
1549                                 Object x = f.get(null);
1550                                 if (k.isInstance(x))
1551                                     return k.cast(x);
1552                             }
1553                             throw new NoSuchFieldError("the Unsafe");
1554                         }});
1555         } catch (java.security.PrivilegedActionException e) {
1556             throw new RuntimeException("Could not initialize intrinsics",
1557                     e.getCause());
1558         }
1559     }
1560 }