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