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