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/licenses/publicdomain
  34  */
  35 
  36 package java.util.concurrent;
  37 
  38 import java.io.Serializable;
  39 import java.util.Collection;
  40 import java.util.Collections;
  41 import java.util.List;
  42 import java.util.RandomAccess;
  43 import java.util.Map;
  44 import java.util.WeakHashMap;
  45 import java.util.concurrent.Callable;
  46 import java.util.concurrent.CancellationException;
  47 import java.util.concurrent.ExecutionException;
  48 import java.util.concurrent.Executor;
  49 import java.util.concurrent.ExecutorService;
  50 import java.util.concurrent.Future;
  51 import java.util.concurrent.RejectedExecutionException;
  52 import java.util.concurrent.RunnableFuture;
  53 import java.util.concurrent.TimeUnit;
  54 import java.util.concurrent.TimeoutException;
  55 
  56 /**
  57  * Abstract base class for tasks that run within a {@link ForkJoinPool}.
  58  * A {@code ForkJoinTask} is a thread-like entity that is much
  59  * lighter weight than a normal thread.  Huge numbers of tasks and
  60  * subtasks may be hosted by a small number of actual threads in a
  61  * ForkJoinPool, at the price of some usage limitations.
  62  *
  63  * <p>A "main" {@code ForkJoinTask} begins execution when submitted
  64  * to a {@link ForkJoinPool}.  Once started, it will usually in turn
  65  * start other subtasks.  As indicated by the name of this class,
  66  * many programs using {@code ForkJoinTask} employ only methods
  67  * {@link #fork} and {@link #join}, or derivatives such as {@link
  68  * #invokeAll(ForkJoinTask...) invokeAll}.  However, this class also
  69  * provides a number of other methods that can come into play in
  70  * advanced usages, as well as extension mechanics that allow
  71  * support of new forms of fork/join processing.
  72  *
  73  * <p>A {@code ForkJoinTask} is a lightweight form of {@link Future}.
  74  * The efficiency of {@code ForkJoinTask}s stems from a set of
  75  * restrictions (that are only partially statically enforceable)
  76  * reflecting their intended use as computational tasks calculating
  77  * pure functions or operating on purely isolated objects.  The
  78  * primary coordination mechanisms are {@link #fork}, that arranges
  79  * asynchronous execution, and {@link #join}, that doesn't proceed
  80  * until the task's result has been computed.  Computations should
  81  * avoid {@code synchronized} methods or blocks, and should minimize
  82  * other blocking synchronization apart from joining other tasks or
  83  * using synchronizers such as Phasers that are advertised to
  84  * cooperate with fork/join scheduling. Tasks should also not perform
  85  * blocking IO, and should ideally access variables that are
  86  * completely independent of those accessed by other running
  87  * tasks. Minor breaches of these restrictions, for example using
  88  * shared output streams, may be tolerable in practice, but frequent
  89  * use may result in poor performance, and the potential to
  90  * indefinitely stall if the number of threads not waiting for IO or
  91  * other external synchronization becomes exhausted. This usage
  92  * restriction is in part enforced by not permitting checked
  93  * exceptions such as {@code IOExceptions} to be thrown. However,
  94  * computations may still encounter unchecked exceptions, that are
  95  * rethrown to callers attempting to join them. These exceptions may
  96  * additionally include {@link RejectedExecutionException} stemming
  97  * from internal resource exhaustion, such as failure to allocate
  98  * internal task queues.
  99  *
 100  * <p>The primary method for awaiting completion and extracting
 101  * results of a task is {@link #join}, but there are several variants:
 102  * The {@link Future#get} methods support interruptible and/or timed
 103  * waits for completion and report results using {@code Future}
 104  * conventions. Method {@link #invoke} is semantically
 105  * equivalent to {@code fork(); join()} but always attempts to begin
 106  * execution in the current thread. The "<em>quiet</em>" forms of
 107  * these methods do not extract results or report exceptions. These
 108  * may be useful when a set of tasks are being executed, and you need
 109  * to delay processing of results or exceptions until all complete.
 110  * Method {@code invokeAll} (available in multiple versions)
 111  * performs the most common form of parallel invocation: forking a set
 112  * of tasks and joining them all.
 113  *
 114  * <p>The execution status of tasks may be queried at several levels
 115  * of detail: {@link #isDone} is true if a task completed in any way
 116  * (including the case where a task was cancelled without executing);
 117  * {@link #isCompletedNormally} is true if a task completed without
 118  * cancellation or encountering an exception; {@link #isCancelled} is
 119  * true if the task was cancelled (in which case {@link #getException}
 120  * returns a {@link java.util.concurrent.CancellationException}); and
 121  * {@link #isCompletedAbnormally} is true if a task was either
 122  * cancelled or encountered an exception, in which case {@link
 123  * #getException} will return either the encountered exception or
 124  * {@link java.util.concurrent.CancellationException}.
 125  *
 126  * <p>The ForkJoinTask class is not usually directly subclassed.
 127  * Instead, you subclass one of the abstract classes that support a
 128  * particular style of fork/join processing, typically {@link
 129  * RecursiveAction} for computations that do not return results, or
 130  * {@link RecursiveTask} for those that do.  Normally, a concrete
 131  * ForkJoinTask subclass declares fields comprising its parameters,
 132  * established in a constructor, and then defines a {@code compute}
 133  * method that somehow uses the control methods supplied by this base
 134  * class. While these methods have {@code public} access (to allow
 135  * instances of different task subclasses to call each other's
 136  * methods), some of them may only be called from within other
 137  * ForkJoinTasks (as may be determined using method {@link
 138  * #inForkJoinPool}).  Attempts to invoke them in other contexts
 139  * result in exceptions or errors, possibly including
 140  * {@code ClassCastException}.
 141  *
 142  * <p>Method {@link #join} and its variants are appropriate for use
 143  * only when completion dependencies are acyclic; that is, the
 144  * parallel computation can be described as a directed acyclic graph
 145  * (DAG). Otherwise, executions may encounter a form of deadlock as
 146  * tasks cyclically wait for each other.  However, this framework
 147  * supports other methods and techniques (for example the use of
 148  * {@link Phaser}, {@link #helpQuiesce}, and {@link #complete}) that
 149  * may be of use in constructing custom subclasses for problems that
 150  * are not statically structured as DAGs.
 151  *
 152  * <p>Most base support methods are {@code final}, to prevent
 153  * overriding of implementations that are intrinsically tied to the
 154  * underlying lightweight task scheduling framework.  Developers
 155  * creating new basic styles of fork/join processing should minimally
 156  * implement {@code protected} methods {@link #exec}, {@link
 157  * #setRawResult}, and {@link #getRawResult}, while also introducing
 158  * an abstract computational method that can be implemented in its
 159  * subclasses, possibly relying on other {@code protected} methods
 160  * provided by this class.
 161  *
 162  * <p>ForkJoinTasks should perform relatively small amounts of
 163  * computation. Large tasks should be split into smaller subtasks,
 164  * usually via recursive decomposition. As a very rough rule of thumb,
 165  * a task should perform more than 100 and less than 10000 basic
 166  * computational steps, and should avoid indefinite looping. If tasks
 167  * are too big, then parallelism cannot improve throughput. If too
 168  * small, then memory and internal task maintenance overhead may
 169  * overwhelm processing.
 170  *
 171  * <p>This class provides {@code adapt} methods for {@link Runnable}
 172  * and {@link Callable}, that may be of use when mixing execution of
 173  * {@code ForkJoinTasks} with other kinds of tasks. When all tasks are
 174  * of this form, consider using a pool constructed in <em>asyncMode</em>.
 175  *
 176  * <p>ForkJoinTasks are {@code Serializable}, which enables them to be
 177  * used in extensions such as remote execution frameworks. It is
 178  * sensible to serialize tasks only before or after, but not during,
 179  * execution. Serialization is not relied on during execution itself.
 180  *
 181  * @since 1.7
 182  * @author Doug Lea
 183  */
 184 public abstract class ForkJoinTask<V> implements Future<V>, Serializable {
 185 
 186     /*
 187      * See the internal documentation of class ForkJoinPool for a
 188      * general implementation overview.  ForkJoinTasks are mainly
 189      * responsible for maintaining their "status" field amidst relays
 190      * to methods in ForkJoinWorkerThread and ForkJoinPool. The
 191      * methods of this class are more-or-less layered into (1) basic
 192      * status maintenance (2) execution and awaiting completion (3)
 193      * user-level methods that additionally report results. This is
 194      * sometimes hard to see because this file orders exported methods
 195      * in a way that flows well in javadocs. In particular, most
 196      * join mechanics are in method quietlyJoin, below.
 197      */
 198 
 199     /*
 200      * The status field holds run control status bits packed into a
 201      * single int to minimize footprint and to ensure atomicity (via
 202      * CAS).  Status is initially zero, and takes on nonnegative
 203      * values until completed, upon which status holds value
 204      * NORMAL, CANCELLED, or EXCEPTIONAL. Tasks undergoing blocking
 205      * waits by other threads have the SIGNAL bit set.  Completion of
 206      * a stolen task with SIGNAL set awakens any waiters via
 207      * notifyAll. Even though suboptimal for some purposes, we use
 208      * basic builtin wait/notify to take advantage of "monitor
 209      * inflation" in JVMs that we would otherwise need to emulate to
 210      * avoid adding further per-task bookkeeping overhead.  We want
 211      * these monitors to be "fat", i.e., not use biasing or thin-lock
 212      * techniques, so use some odd coding idioms that tend to avoid
 213      * them.
 214      */
 215 
 216     /** The run status of this task */
 217     volatile int status; // accessed directly by pool and workers
 218 
 219     private static final int NORMAL      = -1;
 220     private static final int CANCELLED   = -2;
 221     private static final int EXCEPTIONAL = -3;
 222     private static final int SIGNAL      =  1;
 223 
 224     /**
 225      * Table of exceptions thrown by tasks, to enable reporting by
 226      * callers. Because exceptions are rare, we don't directly keep
 227      * them with task objects, but instead use a weak ref table.  Note
 228      * that cancellation exceptions don't appear in the table, but are
 229      * instead recorded as status values.
 230      * TODO: Use ConcurrentReferenceHashMap
 231      */
 232     static final Map<ForkJoinTask<?>, Throwable> exceptionMap =
 233         Collections.synchronizedMap
 234         (new WeakHashMap<ForkJoinTask<?>, Throwable>());
 235 
 236     // Maintaining completion status
 237 
 238     /**
 239      * Marks completion and wakes up threads waiting to join this task,
 240      * also clearing signal request bits.
 241      *
 242      * @param completion one of NORMAL, CANCELLED, EXCEPTIONAL
 243      */
 244     private void setCompletion(int completion) {
 245         int s;
 246         while ((s = status) >= 0) {
 247             if (UNSAFE.compareAndSwapInt(this, statusOffset, s, completion)) {
 248                 if (s != 0)
 249                     synchronized (this) { notifyAll(); }
 250                 break;
 251             }
 252         }
 253     }
 254 
 255     /**
 256      * Records exception and sets exceptional completion.
 257      *
 258      * @return status on exit
 259      */
 260     private void setExceptionalCompletion(Throwable rex) {
 261         exceptionMap.put(this, rex);
 262         setCompletion(EXCEPTIONAL);
 263     }
 264 
 265     /**



















 266      * Blocks a worker thread until completed or timed out.  Called
 267      * only by pool.


 268      */
 269     final void internalAwaitDone(long millis, int nanos) {
 270         int s = status;
 271         if ((s == 0 &&
 272              UNSAFE.compareAndSwapInt(this, statusOffset, 0, SIGNAL)) ||
 273             s > 0)  {
 274             try {     // the odd construction reduces lock bias effects
 275                 synchronized (this) {
 276                     if (status > 0)
 277                         wait(millis, nanos);
 278                     else
 279                         notifyAll();
 280                 }
 281             } catch (InterruptedException ie) {
 282                 cancelIfTerminating();
 283             }

 284         }

 285     }
 286 
 287     /**
 288      * Blocks a non-worker-thread until completion.
 289      */
 290     private void externalAwaitDone() {
 291         if (status >= 0) {



 292             boolean interrupted = false;
 293             synchronized (this) {
 294                 for (;;) {
 295                     int s = status;
 296                     if (s == 0)
 297                         UNSAFE.compareAndSwapInt(this, statusOffset,
 298                                                  0, SIGNAL);
 299                     else if (s < 0) {
 300                         notifyAll();
 301                         break;
 302                     }
 303                     else {
 304                         try {
 305                             wait();
 306                         } catch (InterruptedException ie) {
 307                             interrupted = true;
 308                         }
 309                     }
 310                 }
 311             }
 312             if (interrupted)
 313                 Thread.currentThread().interrupt();
 314         }
 315     }
 316 
 317     /**
 318      * Blocks a non-worker-thread until completion or interruption or timeout.
 319      */
 320     private void externalInterruptibleAwaitDone(boolean timed, long nanos)
 321         throws InterruptedException {
 322         if (Thread.interrupted())
 323             throw new InterruptedException();
 324         if (status >= 0) {
 325             long startTime = timed ? System.nanoTime() : 0L;
 326             synchronized (this) {
 327                 for (;;) {
 328                     long nt;
 329                     int s = status;
 330                     if (s == 0)
 331                         UNSAFE.compareAndSwapInt(this, statusOffset,
 332                                                  0, SIGNAL);
 333                     else if (s < 0) {
 334                         notifyAll();
 335                         break;
 336                     }
 337                     else if (!timed)
 338                         wait();
 339                     else if ((nt = nanos - (System.nanoTime()-startTime)) > 0L)
 340                         wait(nt / 1000000, (int)(nt % 1000000));
 341                     else
 342                         break;
 343                 }
 344             }
 345         }
 346     }
 347 
 348     /**
 349      * Unless done, calls exec and records status if completed, but
 350      * doesn't wait for completion otherwise. Primary execution method
 351      * for ForkJoinWorkerThread.
 352      */
 353     final void quietlyExec() {
 354         try {
 355             if (status < 0 || !exec())
 356                 return;
 357         } catch (Throwable rex) {
 358             setExceptionalCompletion(rex);
 359             return;
 360         }
 361         setCompletion(NORMAL); // must be outside try block
 362     }
 363 
 364     // public methods
 365 
 366     /**
 367      * Arranges to asynchronously execute this task.  While it is not
 368      * necessarily enforced, it is a usage error to fork a task more
 369      * than once unless it has completed and been reinitialized.
 370      * Subsequent modifications to the state of this task or any data
 371      * it operates on are not necessarily consistently observable by
 372      * any thread other than the one executing it unless preceded by a
 373      * call to {@link #join} or related methods, or a call to {@link
 374      * #isDone} returning {@code true}.
 375      *
 376      * <p>This method may be invoked only from within {@code
 377      * ForkJoinPool} computations (as may be determined using method
 378      * {@link #inForkJoinPool}).  Attempts to invoke in other contexts
 379      * result in exceptions or errors, possibly including {@code
 380      * ClassCastException}.
 381      *
 382      * @return {@code this}, to simplify usage
 383      */
 384     public final ForkJoinTask<V> fork() {
 385         ((ForkJoinWorkerThread) Thread.currentThread())
 386             .pushTask(this);
 387         return this;
 388     }
 389 
 390     /**
 391      * Returns the result of the computation when it {@link #isDone is
 392      * done}.  This method differs from {@link #get()} in that
 393      * abnormal completion results in {@code RuntimeException} or
 394      * {@code Error}, not {@code ExecutionException}, and that
 395      * interrupts of the calling thread do <em>not</em> cause the
 396      * method to abruptly return by throwing {@code
 397      * InterruptedException}.
 398      *
 399      * @return the computed result
 400      */
 401     public final V join() {
 402         quietlyJoin();
 403         Throwable ex;
 404         if (status < NORMAL && (ex = getException()) != null)
 405             UNSAFE.throwException(ex);
 406         return getRawResult();
 407     }
 408 
 409     /**
 410      * Commences performing this task, awaits its completion if
 411      * necessary, and returns its result, or throws an (unchecked)
 412      * {@code RuntimeException} or {@code Error} if the underlying
 413      * computation did so.
 414      *
 415      * @return the computed result
 416      */
 417     public final V invoke() {
 418         quietlyInvoke();
 419         Throwable ex;
 420         if (status < NORMAL && (ex = getException()) != null)
 421             UNSAFE.throwException(ex);
 422         return getRawResult();
 423     }
 424 
 425     /**
 426      * Forks the given tasks, returning when {@code isDone} holds for
 427      * each task or an (unchecked) exception is encountered, in which
 428      * case the exception is rethrown. If more than one task
 429      * encounters an exception, then this method throws any one of
 430      * these exceptions. If any task encounters an exception, the
 431      * other may be cancelled. However, the execution status of
 432      * individual tasks is not guaranteed upon exceptional return. The
 433      * status of each task may be obtained using {@link
 434      * #getException()} and related methods to check if they have been
 435      * cancelled, completed normally or exceptionally, or left
 436      * unprocessed.
 437      *
 438      * <p>This method may be invoked only from within {@code
 439      * ForkJoinPool} computations (as may be determined using method
 440      * {@link #inForkJoinPool}).  Attempts to invoke in other contexts
 441      * result in exceptions or errors, possibly including {@code
 442      * ClassCastException}.
 443      *
 444      * @param t1 the first task
 445      * @param t2 the second task
 446      * @throws NullPointerException if any task is null
 447      */
 448     public static void invokeAll(ForkJoinTask<?> t1, ForkJoinTask<?> t2) {
 449         t2.fork();
 450         t1.invoke();
 451         t2.join();
 452     }
 453 
 454     /**
 455      * Forks the given tasks, returning when {@code isDone} holds for
 456      * each task or an (unchecked) exception is encountered, in which
 457      * case the exception is rethrown. If more than one task
 458      * encounters an exception, then this method throws any one of
 459      * these exceptions. If any task encounters an exception, others
 460      * may be cancelled. However, the execution status of individual
 461      * tasks is not guaranteed upon exceptional return. The status of
 462      * each task may be obtained using {@link #getException()} and
 463      * related methods to check if they have been cancelled, completed
 464      * normally or exceptionally, or left unprocessed.
 465      *
 466      * <p>This method may be invoked only from within {@code
 467      * ForkJoinPool} computations (as may be determined using method
 468      * {@link #inForkJoinPool}).  Attempts to invoke in other contexts
 469      * result in exceptions or errors, possibly including {@code
 470      * ClassCastException}.
 471      *
 472      * @param tasks the tasks
 473      * @throws NullPointerException if any task is null
 474      */
 475     public static void invokeAll(ForkJoinTask<?>... tasks) {
 476         Throwable ex = null;
 477         int last = tasks.length - 1;
 478         for (int i = last; i >= 0; --i) {
 479             ForkJoinTask<?> t = tasks[i];
 480             if (t == null) {
 481                 if (ex == null)
 482                     ex = new NullPointerException();
 483             }
 484             else if (i != 0)
 485                 t.fork();
 486             else {
 487                 t.quietlyInvoke();
 488                 if (ex == null && t.status < NORMAL)
 489                     ex = t.getException();
 490             }
 491         }
 492         for (int i = 1; i <= last; ++i) {
 493             ForkJoinTask<?> t = tasks[i];
 494             if (t != null) {
 495                 if (ex != null)
 496                     t.cancel(false);
 497                 else {
 498                     t.quietlyJoin();
 499                     if (ex == null && t.status < NORMAL)
 500                         ex = t.getException();
 501                 }
 502             }
 503         }
 504         if (ex != null)
 505             UNSAFE.throwException(ex);
 506     }
 507 
 508     /**
 509      * Forks all tasks in the specified collection, returning when
 510      * {@code isDone} holds for each task or an (unchecked) exception
 511      * is encountered, in which case the exception is rethrown. If
 512      * more than one task encounters an exception, then this method
 513      * throws any one of these exceptions. If any task encounters an
 514      * exception, others may be cancelled. However, the execution
 515      * status of individual tasks is not guaranteed upon exceptional
 516      * return. The status of each task may be obtained using {@link
 517      * #getException()} and related methods to check if they have been
 518      * cancelled, completed normally or exceptionally, or left
 519      * unprocessed.
 520      *
 521      * <p>This method may be invoked only from within {@code
 522      * ForkJoinPool} computations (as may be determined using method
 523      * {@link #inForkJoinPool}).  Attempts to invoke in other contexts
 524      * result in exceptions or errors, possibly including {@code
 525      * ClassCastException}.
 526      *
 527      * @param tasks the collection of tasks
 528      * @return the tasks argument, to simplify usage
 529      * @throws NullPointerException if tasks or any element are null
 530      */
 531     public static <T extends ForkJoinTask<?>> Collection<T> invokeAll(Collection<T> tasks) {
 532         if (!(tasks instanceof RandomAccess) || !(tasks instanceof List<?>)) {
 533             invokeAll(tasks.toArray(new ForkJoinTask<?>[tasks.size()]));
 534             return tasks;
 535         }
 536         @SuppressWarnings("unchecked")
 537         List<? extends ForkJoinTask<?>> ts =
 538             (List<? extends ForkJoinTask<?>>) tasks;
 539         Throwable ex = null;
 540         int last = ts.size() - 1;
 541         for (int i = last; i >= 0; --i) {
 542             ForkJoinTask<?> t = ts.get(i);
 543             if (t == null) {
 544                 if (ex == null)
 545                     ex = new NullPointerException();
 546             }
 547             else if (i != 0)
 548                 t.fork();
 549             else {
 550                 t.quietlyInvoke();
 551                 if (ex == null && t.status < NORMAL)
 552                     ex = t.getException();
 553             }
 554         }
 555         for (int i = 1; i <= last; ++i) {
 556             ForkJoinTask<?> t = ts.get(i);
 557             if (t != null) {
 558                 if (ex != null)
 559                     t.cancel(false);
 560                 else {
 561                     t.quietlyJoin();
 562                     if (ex == null && t.status < NORMAL)
 563                         ex = t.getException();
 564                 }
 565             }
 566         }
 567         if (ex != null)
 568             UNSAFE.throwException(ex);
 569         return tasks;
 570     }
 571 
 572     /**
 573      * Attempts to cancel execution of this task. This attempt will
 574      * fail if the task has already completed or could not be
 575      * cancelled for some other reason. If successful, and this task
 576      * has not started when {@code cancel} is called, execution of
 577      * this task is suppressed. After this method returns
 578      * successfully, unless there is an intervening call to {@link
 579      * #reinitialize}, subsequent calls to {@link #isCancelled},
 580      * {@link #isDone}, and {@code cancel} will return {@code true}
 581      * and calls to {@link #join} and related methods will result in
 582      * {@code CancellationException}.
 583      *
 584      * <p>This method may be overridden in subclasses, but if so, must
 585      * still ensure that these properties hold. In particular, the
 586      * {@code cancel} method itself must not throw exceptions.
 587      *
 588      * <p>This method is designed to be invoked by <em>other</em>
 589      * tasks. To terminate the current task, you can just return or
 590      * throw an unchecked exception from its computation method, or
 591      * invoke {@link #completeExceptionally}.
 592      *
 593      * @param mayInterruptIfRunning this value has no effect in the
 594      * default implementation because interrupts are not used to
 595      * control cancellation.
 596      *
 597      * @return {@code true} if this task is now cancelled
 598      */
 599     public boolean cancel(boolean mayInterruptIfRunning) {
 600         setCompletion(CANCELLED);
 601         return status == CANCELLED;
 602     }
 603 
 604     /**
 605      * Cancels, ignoring any exceptions thrown by cancel. Used during
 606      * worker and pool shutdown. Cancel is spec'ed not to throw any
 607      * exceptions, but if it does anyway, we have no recourse during
 608      * shutdown, so guard against this case.
 609      */
 610     final void cancelIgnoringExceptions() {
 611         try {
 612             cancel(false);
 613         } catch (Throwable ignore) {
 614         }
 615     }
 616 
 617     /**
 618      * Cancels if current thread is a terminating worker thread,
 619      * ignoring any exceptions thrown by cancel.
 620      */
 621     final void cancelIfTerminating() {
 622         Thread t = Thread.currentThread();
 623         if ((t instanceof ForkJoinWorkerThread) &&
 624             ((ForkJoinWorkerThread) t).isTerminating()) {
 625             try {
 626                 cancel(false);
 627             } catch (Throwable ignore) {
 628             }
 629         }
 630     }
 631 
 632     public final boolean isDone() {
 633         return status < 0;
 634     }
 635 
 636     public final boolean isCancelled() {
 637         return status == CANCELLED;
 638     }
 639 
 640     /**
 641      * Returns {@code true} if this task threw an exception or was cancelled.
 642      *
 643      * @return {@code true} if this task threw an exception or was cancelled
 644      */
 645     public final boolean isCompletedAbnormally() {
 646         return status < NORMAL;
 647     }
 648 
 649     /**
 650      * Returns {@code true} if this task completed without throwing an
 651      * exception and was not cancelled.
 652      *
 653      * @return {@code true} if this task completed without throwing an
 654      * exception and was not cancelled
 655      */
 656     public final boolean isCompletedNormally() {
 657         return status == NORMAL;
 658     }
 659 
 660     /**
 661      * Returns the exception thrown by the base computation, or a
 662      * {@code CancellationException} if cancelled, or {@code null} if
 663      * none or if the method has not yet completed.
 664      *
 665      * @return the exception, or {@code null} if none
 666      */
 667     public final Throwable getException() {
 668         int s = status;
 669         return ((s >= NORMAL)    ? null :
 670                 (s == CANCELLED) ? new CancellationException() :
 671                 exceptionMap.get(this));
 672     }
 673 
 674     /**
 675      * Completes this task abnormally, and if not already aborted or
 676      * cancelled, causes it to throw the given exception upon
 677      * {@code join} and related operations. This method may be used
 678      * to induce exceptions in asynchronous tasks, or to force
 679      * completion of tasks that would not otherwise complete.  Its use
 680      * in other situations is discouraged.  This method is
 681      * overridable, but overridden versions must invoke {@code super}
 682      * implementation to maintain guarantees.
 683      *
 684      * @param ex the exception to throw. If this exception is not a
 685      * {@code RuntimeException} or {@code Error}, the actual exception
 686      * thrown will be a {@code RuntimeException} with cause {@code ex}.
 687      */
 688     public void completeExceptionally(Throwable ex) {
 689         setExceptionalCompletion((ex instanceof RuntimeException) ||
 690                                  (ex instanceof Error) ? ex :
 691                                  new RuntimeException(ex));
 692     }
 693 
 694     /**
 695      * Completes this task, and if not already aborted or cancelled,
 696      * returning the given value as the result of subsequent
 697      * invocations of {@code join} and related operations. This method
 698      * may be used to provide results for asynchronous tasks, or to
 699      * provide alternative handling for tasks that would not otherwise
 700      * complete normally. Its use in other situations is
 701      * discouraged. This method is overridable, but overridden
 702      * versions must invoke {@code super} implementation to maintain
 703      * guarantees.
 704      *
 705      * @param value the result value for this task
 706      */
 707     public void complete(V value) {
 708         try {
 709             setRawResult(value);
 710         } catch (Throwable rex) {
 711             setExceptionalCompletion(rex);
 712             return;
 713         }
 714         setCompletion(NORMAL);
 715     }
 716 
 717     /**
 718      * Waits if necessary for the computation to complete, and then
 719      * retrieves its result.
 720      *
 721      * @return the computed result
 722      * @throws CancellationException if the computation was cancelled
 723      * @throws ExecutionException if the computation threw an
 724      * exception
 725      * @throws InterruptedException if the current thread is not a
 726      * member of a ForkJoinPool and was interrupted while waiting
 727      */
 728     public final V get() throws InterruptedException, ExecutionException {
 729         Thread t = Thread.currentThread();
 730         if (t instanceof ForkJoinWorkerThread)
 731             quietlyJoin();
 732         else
 733             externalInterruptibleAwaitDone(false, 0L);
 734         int s = status;
 735         if (s != NORMAL) {










 736             Throwable ex;
 737             if (s == CANCELLED)
 738                 throw new CancellationException();
 739             if (s == EXCEPTIONAL && (ex = exceptionMap.get(this)) != null)
 740                 throw new ExecutionException(ex);
 741         }
 742         return getRawResult();
 743     }
 744 
 745     /**
 746      * Waits if necessary for at most the given time for the computation
 747      * to complete, and then retrieves its result, if available.
 748      *
 749      * @param timeout the maximum time to wait
 750      * @param unit the time unit of the timeout argument
 751      * @return the computed result
 752      * @throws CancellationException if the computation was cancelled
 753      * @throws ExecutionException if the computation threw an
 754      * exception
 755      * @throws InterruptedException if the current thread is not a
 756      * member of a ForkJoinPool and was interrupted while waiting
 757      * @throws TimeoutException if the wait timed out
 758      */
 759     public final V get(long timeout, TimeUnit unit)
 760         throws InterruptedException, ExecutionException, TimeoutException {
 761         long nanos = unit.toNanos(timeout);
 762         Thread t = Thread.currentThread();
 763         if (t instanceof ForkJoinWorkerThread)
 764             ((ForkJoinWorkerThread)t).joinTask(this, true, nanos);





 765         else
 766             externalInterruptibleAwaitDone(true, nanos);















 767         int s = status;
 768         if (s != NORMAL) {



































 769             Throwable ex;
 770             if (s == CANCELLED)
 771                 throw new CancellationException();
 772             if (s == EXCEPTIONAL && (ex = exceptionMap.get(this)) != null)
 773                 throw new ExecutionException(ex);
 774             throw new TimeoutException();
 775         }
 776         return getRawResult();
 777     }
 778 
 779     /**
 780      * Joins this task, without returning its result or throwing its
 781      * exception. This method may be useful when processing
 782      * collections of tasks when some have been cancelled or otherwise
 783      * known to have aborted.
 784      */
 785     public final void quietlyJoin() {
 786         Thread t;
 787         if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) {
 788             ForkJoinWorkerThread w = (ForkJoinWorkerThread) t;
 789             if (status >= 0) {
 790                 if (w.unpushTask(this)) {
 791                     boolean completed;
 792                     try {
 793                         completed = exec();
 794                     } catch (Throwable rex) {
 795                         setExceptionalCompletion(rex);
 796                         return;
 797                     }
 798                     if (completed) {
 799                         setCompletion(NORMAL);
 800                         return;
 801                     }
 802                 }
 803                 w.joinTask(this, false, 0L);
 804             }
 805         }
 806         else
 807             externalAwaitDone();
 808     }
 809 
 810     /**
 811      * Commences performing this task and awaits its completion if
 812      * necessary, without returning its result or throwing its
 813      * exception.
 814      */
 815     public final void quietlyInvoke() {
 816         if (status >= 0) {
 817             boolean completed;
 818             try {
 819                 completed = exec();
 820             } catch (Throwable rex) {
 821                 setExceptionalCompletion(rex);
 822                 return;
 823             }
 824             if (completed)
 825                 setCompletion(NORMAL);
 826             else
 827                 quietlyJoin();
 828         }
 829     }
 830 
 831     /**
 832      * Possibly executes tasks until the pool hosting the current task
 833      * {@link ForkJoinPool#isQuiescent is quiescent}. This method may
 834      * be of use in designs in which many tasks are forked, but none
 835      * are explicitly joined, instead executing them until all are
 836      * processed.
 837      *
 838      * <p>This method may be invoked only from within {@code
 839      * ForkJoinPool} computations (as may be determined using method
 840      * {@link #inForkJoinPool}).  Attempts to invoke in other contexts
 841      * result in exceptions or errors, possibly including {@code
 842      * ClassCastException}.
 843      */
 844     public static void helpQuiesce() {
 845         ((ForkJoinWorkerThread) Thread.currentThread())
 846             .helpQuiescePool();
 847     }
 848 
 849     /**
 850      * Resets the internal bookkeeping state of this task, allowing a
 851      * subsequent {@code fork}. This method allows repeated reuse of
 852      * this task, but only if reuse occurs when this task has either
 853      * never been forked, or has been forked, then completed and all
 854      * outstanding joins of this task have also completed. Effects
 855      * under any other usage conditions are not guaranteed.
 856      * This method may be useful when executing
 857      * pre-constructed trees of subtasks in loops.
 858      *
 859      * <p>Upon completion of this method, {@code isDone()} reports
 860      * {@code false}, and {@code getException()} reports {@code
 861      * null}. However, the value returned by {@code getRawResult} is
 862      * unaffected. To clear this value, you can invoke {@code
 863      * setRawResult(null)}.
 864      */
 865     public void reinitialize() {
 866         if (status == EXCEPTIONAL)
 867             exceptionMap.remove(this);
 868         status = 0;
 869     }
 870 
 871     /**
 872      * Returns the pool hosting the current task execution, or null
 873      * if this task is executing outside of any ForkJoinPool.
 874      *
 875      * @see #inForkJoinPool
 876      * @return the pool, or {@code null} if none
 877      */
 878     public static ForkJoinPool getPool() {
 879         Thread t = Thread.currentThread();
 880         return (t instanceof ForkJoinWorkerThread) ?
 881             ((ForkJoinWorkerThread) t).pool : null;
 882     }
 883 
 884     /**
 885      * Returns {@code true} if the current thread is a {@link
 886      * ForkJoinWorkerThread} executing as a ForkJoinPool computation.
 887      *
 888      * @return {@code true} if the current thread is a {@link
 889      * ForkJoinWorkerThread} executing as a ForkJoinPool computation,
 890      * or {@code false} otherwise
 891      */
 892     public static boolean inForkJoinPool() {
 893         return Thread.currentThread() instanceof ForkJoinWorkerThread;
 894     }
 895 
 896     /**
 897      * Tries to unschedule this task for execution. This method will
 898      * typically succeed if this task is the most recently forked task
 899      * by the current thread, and has not commenced executing in
 900      * another thread.  This method may be useful when arranging
 901      * alternative local processing of tasks that could have been, but
 902      * were not, stolen.
 903      *
 904      * <p>This method may be invoked only from within {@code
 905      * ForkJoinPool} computations (as may be determined using method
 906      * {@link #inForkJoinPool}).  Attempts to invoke in other contexts
 907      * result in exceptions or errors, possibly including {@code
 908      * ClassCastException}.
 909      *
 910      * @return {@code true} if unforked
 911      */
 912     public boolean tryUnfork() {
 913         return ((ForkJoinWorkerThread) Thread.currentThread())
 914             .unpushTask(this);
 915     }
 916 
 917     /**
 918      * Returns an estimate of the number of tasks that have been
 919      * forked by the current worker thread but not yet executed. This
 920      * value may be useful for heuristic decisions about whether to
 921      * fork other tasks.
 922      *
 923      * <p>This method may be invoked only from within {@code
 924      * ForkJoinPool} computations (as may be determined using method
 925      * {@link #inForkJoinPool}).  Attempts to invoke in other contexts
 926      * result in exceptions or errors, possibly including {@code
 927      * ClassCastException}.
 928      *
 929      * @return the number of tasks
 930      */
 931     public static int getQueuedTaskCount() {
 932         return ((ForkJoinWorkerThread) Thread.currentThread())
 933             .getQueueSize();
 934     }
 935 
 936     /**
 937      * Returns an estimate of how many more locally queued tasks are
 938      * held by the current worker thread than there are other worker
 939      * threads that might steal them.  This value may be useful for
 940      * heuristic decisions about whether to fork other tasks. In many
 941      * usages of ForkJoinTasks, at steady state, each worker should
 942      * aim to maintain a small constant surplus (for example, 3) of
 943      * tasks, and to process computations locally if this threshold is
 944      * exceeded.
 945      *
 946      * <p>This method may be invoked only from within {@code
 947      * ForkJoinPool} computations (as may be determined using method
 948      * {@link #inForkJoinPool}).  Attempts to invoke in other contexts
 949      * result in exceptions or errors, possibly including {@code
 950      * ClassCastException}.
 951      *
 952      * @return the surplus number of tasks, which may be negative
 953      */
 954     public static int getSurplusQueuedTaskCount() {
 955         return ((ForkJoinWorkerThread) Thread.currentThread())
 956             .getEstimatedSurplusTaskCount();
 957     }
 958 
 959     // Extension methods
 960 
 961     /**
 962      * Returns the result that would be returned by {@link #join}, even
 963      * if this task completed abnormally, or {@code null} if this task
 964      * is not known to have been completed.  This method is designed
 965      * to aid debugging, as well as to support extensions. Its use in
 966      * any other context is discouraged.
 967      *
 968      * @return the result, or {@code null} if not completed
 969      */
 970     public abstract V getRawResult();
 971 
 972     /**
 973      * Forces the given value to be returned as a result.  This method
 974      * is designed to support extensions, and should not in general be
 975      * called otherwise.
 976      *
 977      * @param value the value
 978      */
 979     protected abstract void setRawResult(V value);
 980 
 981     /**
 982      * Immediately performs the base action of this task.  This method
 983      * is designed to support extensions, and should not in general be
 984      * called otherwise. The return value controls whether this task
 985      * is considered to be done normally. It may return false in
 986      * asynchronous actions that require explicit invocations of
 987      * {@link #complete} to become joinable. It may also throw an
 988      * (unchecked) exception to indicate abnormal exit.
 989      *
 990      * @return {@code true} if completed normally
 991      */
 992     protected abstract boolean exec();
 993 
 994     /**
 995      * Returns, but does not unschedule or execute, a task queued by
 996      * the current thread but not yet executed, if one is immediately
 997      * available. There is no guarantee that this task will actually
 998      * be polled or executed next. Conversely, this method may return
 999      * null even if a task exists but cannot be accessed without
1000      * contention with other threads.  This method is designed
1001      * primarily to support extensions, and is unlikely to be useful
1002      * otherwise.
1003      *
1004      * <p>This method may be invoked only from within {@code
1005      * ForkJoinPool} computations (as may be determined using method
1006      * {@link #inForkJoinPool}).  Attempts to invoke in other contexts
1007      * result in exceptions or errors, possibly including {@code
1008      * ClassCastException}.
1009      *
1010      * @return the next task, or {@code null} if none are available
1011      */
1012     protected static ForkJoinTask<?> peekNextLocalTask() {
1013         return ((ForkJoinWorkerThread) Thread.currentThread())
1014             .peekTask();
1015     }
1016 
1017     /**
1018      * Unschedules and returns, without executing, the next task
1019      * queued by the current thread but not yet executed.  This method
1020      * is designed primarily to support extensions, and is unlikely to
1021      * be useful otherwise.
1022      *
1023      * <p>This method may be invoked only from within {@code
1024      * ForkJoinPool} computations (as may be determined using method
1025      * {@link #inForkJoinPool}).  Attempts to invoke in other contexts
1026      * result in exceptions or errors, possibly including {@code
1027      * ClassCastException}.
1028      *
1029      * @return the next task, or {@code null} if none are available
1030      */
1031     protected static ForkJoinTask<?> pollNextLocalTask() {
1032         return ((ForkJoinWorkerThread) Thread.currentThread())
1033             .pollLocalTask();
1034     }
1035 
1036     /**
1037      * Unschedules and returns, without executing, the next task
1038      * queued by the current thread but not yet executed, if one is
1039      * available, or if not available, a task that was forked by some
1040      * other thread, if available. Availability may be transient, so a
1041      * {@code null} result does not necessarily imply quiescence
1042      * of the pool this task is operating in.  This method is designed
1043      * primarily to support extensions, and is unlikely to be useful
1044      * otherwise.
1045      *
1046      * <p>This method may be invoked only from within {@code
1047      * ForkJoinPool} computations (as may be determined using method
1048      * {@link #inForkJoinPool}).  Attempts to invoke in other contexts
1049      * result in exceptions or errors, possibly including {@code
1050      * ClassCastException}.
1051      *
1052      * @return a task, or {@code null} if none are available
1053      */
1054     protected static ForkJoinTask<?> pollTask() {
1055         return ((ForkJoinWorkerThread) Thread.currentThread())
1056             .pollTask();
1057     }
1058 
1059     /**
1060      * Adaptor for Runnables. This implements RunnableFuture
1061      * to be compliant with AbstractExecutorService constraints
1062      * when used in ForkJoinPool.
1063      */
1064     static final class AdaptedRunnable<T> extends ForkJoinTask<T>
1065         implements RunnableFuture<T> {
1066         final Runnable runnable;
1067         final T resultOnCompletion;
1068         T result;
1069         AdaptedRunnable(Runnable runnable, T result) {
1070             if (runnable == null) throw new NullPointerException();
1071             this.runnable = runnable;
1072             this.resultOnCompletion = result;
1073         }
1074         public T getRawResult() { return result; }
1075         public void setRawResult(T v) { result = v; }
1076         public boolean exec() {
1077             runnable.run();
1078             result = resultOnCompletion;
1079             return true;
1080         }
1081         public void run() { invoke(); }
1082         private static final long serialVersionUID = 5232453952276885070L;
1083     }
1084 
1085     /**
1086      * Adaptor for Callables
1087      */
1088     static final class AdaptedCallable<T> extends ForkJoinTask<T>
1089         implements RunnableFuture<T> {
1090         final Callable<? extends T> callable;
1091         T result;
1092         AdaptedCallable(Callable<? extends T> callable) {
1093             if (callable == null) throw new NullPointerException();
1094             this.callable = callable;
1095         }
1096         public T getRawResult() { return result; }
1097         public void setRawResult(T v) { result = v; }
1098         public boolean exec() {
1099             try {
1100                 result = callable.call();
1101                 return true;
1102             } catch (Error err) {
1103                 throw err;
1104             } catch (RuntimeException rex) {
1105                 throw rex;
1106             } catch (Exception ex) {
1107                 throw new RuntimeException(ex);
1108             }
1109         }
1110         public void run() { invoke(); }
1111         private static final long serialVersionUID = 2838392045355241008L;
1112     }
1113 
1114     /**
1115      * Returns a new {@code ForkJoinTask} that performs the {@code run}
1116      * method of the given {@code Runnable} as its action, and returns
1117      * a null result upon {@link #join}.
1118      *
1119      * @param runnable the runnable action
1120      * @return the task
1121      */
1122     public static ForkJoinTask<?> adapt(Runnable runnable) {
1123         return new AdaptedRunnable<Void>(runnable, null);
1124     }
1125 
1126     /**
1127      * Returns a new {@code ForkJoinTask} that performs the {@code run}
1128      * method of the given {@code Runnable} as its action, and returns
1129      * the given result upon {@link #join}.
1130      *
1131      * @param runnable the runnable action
1132      * @param result the result upon completion
1133      * @return the task
1134      */
1135     public static <T> ForkJoinTask<T> adapt(Runnable runnable, T result) {
1136         return new AdaptedRunnable<T>(runnable, result);
1137     }
1138 
1139     /**
1140      * Returns a new {@code ForkJoinTask} that performs the {@code call}
1141      * method of the given {@code Callable} as its action, and returns
1142      * its result upon {@link #join}, translating any checked exceptions
1143      * encountered into {@code RuntimeException}.
1144      *
1145      * @param callable the callable action
1146      * @return the task
1147      */
1148     public static <T> ForkJoinTask<T> adapt(Callable<? extends T> callable) {
1149         return new AdaptedCallable<T>(callable);
1150     }
1151 
1152     // Serialization support
1153 
1154     private static final long serialVersionUID = -7721805057305804111L;
1155 
1156     /**
1157      * Saves the state to a stream (that is, serializes it).
1158      *
1159      * @serialData the current run status and the exception thrown
1160      * during execution, or {@code null} if none
1161      * @param s the stream
1162      */
1163     private void writeObject(java.io.ObjectOutputStream s)
1164         throws java.io.IOException {
1165         s.defaultWriteObject();
1166         s.writeObject(getException());
1167     }
1168 
1169     /**
1170      * Reconstitutes the instance from a stream (that is, deserializes it).
1171      *
1172      * @param s the stream
1173      */
1174     private void readObject(java.io.ObjectInputStream s)
1175         throws java.io.IOException, ClassNotFoundException {
1176         s.defaultReadObject();
1177         Object ex = s.readObject();
1178         if (ex != null)
1179             setExceptionalCompletion((Throwable) ex);
1180     }
1181 
1182     // Unsafe mechanics
1183 
1184     private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
1185     private static final long statusOffset =
1186         objectFieldOffset("status", ForkJoinTask.class);
1187 
1188     private static long objectFieldOffset(String field, Class<?> klazz) {
1189         try {
1190             return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));
1191         } catch (NoSuchFieldException e) {
1192             // Convert Exception to corresponding Error
1193             NoSuchFieldError error = new NoSuchFieldError(field);
1194             error.initCause(e);
1195             throw error;
1196         }
1197     }
1198 }
--- EOF ---