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.lang.Thread.UncaughtExceptionHandler;
  39 import java.lang.invoke.MethodHandles;
  40 import java.lang.invoke.VarHandle;
  41 import java.security.AccessController;
  42 import java.security.AccessControlContext;
  43 import java.security.Permission;
  44 import java.security.Permissions;
  45 import java.security.PrivilegedAction;
  46 import java.security.ProtectionDomain;
  47 import java.util.ArrayList;
  48 import java.util.Collection;
  49 import java.util.Collections;
  50 import java.util.List;
  51 import java.util.function.Predicate;
  52 import java.util.concurrent.locks.LockSupport;
  53 import jdk.internal.misc.Strands;
  54 
  55 /**
  56  * An {@link ExecutorService} for running {@link ForkJoinTask}s.
  57  * A {@code ForkJoinPool} provides the entry point for submissions
  58  * from non-{@code ForkJoinTask} clients, as well as management and
  59  * monitoring operations.
  60  *
  61  * <p>A {@code ForkJoinPool} differs from other kinds of {@link
  62  * ExecutorService} mainly by virtue of employing
  63  * <em>work-stealing</em>: all threads in the pool attempt to find and
  64  * execute tasks submitted to the pool and/or created by other active
  65  * tasks (eventually blocking waiting for work if none exist). This
  66  * enables efficient processing when most tasks spawn other subtasks
  67  * (as do most {@code ForkJoinTask}s), as well as when many small
  68  * tasks are submitted to the pool from external clients.  Especially
  69  * when setting <em>asyncMode</em> to true in constructors, {@code
  70  * ForkJoinPool}s may also be appropriate for use with event-style
  71  * tasks that are never joined. All worker threads are initialized
  72  * with {@link Thread#isDaemon} set {@code true}.
  73  *
  74  * <p>A static {@link #commonPool()} is available and appropriate for
  75  * most applications. The common pool is used by any ForkJoinTask that
  76  * is not explicitly submitted to a specified pool. Using the common
  77  * pool normally reduces resource usage (its threads are slowly
  78  * reclaimed during periods of non-use, and reinstated upon subsequent
  79  * use).
  80  *
  81  * <p>For applications that require separate or custom pools, a {@code
  82  * ForkJoinPool} may be constructed with a given target parallelism
  83  * level; by default, equal to the number of available processors.
  84  * The pool attempts to maintain enough active (or available) threads
  85  * by dynamically adding, suspending, or resuming internal worker
  86  * threads, even if some tasks are stalled waiting to join others.
  87  * However, no such adjustments are guaranteed in the face of blocked
  88  * I/O or other unmanaged synchronization. The nested {@link
  89  * ManagedBlocker} interface enables extension of the kinds of
  90  * synchronization accommodated. The default policies may be
  91  * overridden using a constructor with parameters corresponding to
  92  * those documented in class {@link ThreadPoolExecutor}.
  93  *
  94  * <p>In addition to execution and lifecycle control methods, this
  95  * class provides status check methods (for example
  96  * {@link #getStealCount}) that are intended to aid in developing,
  97  * tuning, and monitoring fork/join applications. Also, method
  98  * {@link #toString} returns indications of pool state in a
  99  * convenient form for informal monitoring.
 100  *
 101  * <p>As is the case with other ExecutorServices, there are three
 102  * main task execution methods summarized in the following table.
 103  * These are designed to be used primarily by clients not already
 104  * engaged in fork/join computations in the current pool.  The main
 105  * forms of these methods accept instances of {@code ForkJoinTask},
 106  * but overloaded forms also allow mixed execution of plain {@code
 107  * Runnable}- or {@code Callable}- based activities as well.  However,
 108  * tasks that are already executing in a pool should normally instead
 109  * use the within-computation forms listed in the table unless using
 110  * async event-style tasks that are not usually joined, in which case
 111  * there is little difference among choice of methods.
 112  *
 113  * <table class="plain">
 114  * <caption>Summary of task execution methods</caption>
 115  *  <tr>
 116  *    <td></td>
 117  *    <th scope="col"> Call from non-fork/join clients</th>
 118  *    <th scope="col"> Call from within fork/join computations</th>
 119  *  </tr>
 120  *  <tr>
 121  *    <th scope="row" style="text-align:left"> Arrange async execution</th>
 122  *    <td> {@link #execute(ForkJoinTask)}</td>
 123  *    <td> {@link ForkJoinTask#fork}</td>
 124  *  </tr>
 125  *  <tr>
 126  *    <th scope="row" style="text-align:left"> Await and obtain result</th>
 127  *    <td> {@link #invoke(ForkJoinTask)}</td>
 128  *    <td> {@link ForkJoinTask#invoke}</td>
 129  *  </tr>
 130  *  <tr>
 131  *    <th scope="row" style="text-align:left"> Arrange exec and obtain Future</th>
 132  *    <td> {@link #submit(ForkJoinTask)}</td>
 133  *    <td> {@link ForkJoinTask#fork} (ForkJoinTasks <em>are</em> Futures)</td>
 134  *  </tr>
 135  * </table>
 136  *
 137  * <p>The parameters used to construct the common pool may be controlled by
 138  * setting the following {@linkplain System#getProperty system properties}:
 139  * <ul>
 140  * <li>{@systemProperty java.util.concurrent.ForkJoinPool.common.parallelism}
 141  * - the parallelism level, a non-negative integer
 142  * <li>{@systemProperty java.util.concurrent.ForkJoinPool.common.threadFactory}
 143  * - the class name of a {@link ForkJoinWorkerThreadFactory}.
 144  * The {@linkplain ClassLoader#getSystemClassLoader() system class loader}
 145  * is used to load this class.
 146  * <li>{@systemProperty java.util.concurrent.ForkJoinPool.common.exceptionHandler}
 147  * - the class name of a {@link UncaughtExceptionHandler}.
 148  * The {@linkplain ClassLoader#getSystemClassLoader() system class loader}
 149  * is used to load this class.
 150  * <li>{@systemProperty java.util.concurrent.ForkJoinPool.common.maximumSpares}
 151  * - the maximum number of allowed extra threads to maintain target
 152  * parallelism (default 256).
 153  * </ul>
 154  * If no thread factory is supplied via a system property, then the
 155  * common pool uses a factory that uses the system class loader as the
 156  * {@linkplain Thread#getContextClassLoader() thread context class loader}.
 157  * In addition, if a {@link SecurityManager} is present, then
 158  * the common pool uses a factory supplying threads that have no
 159  * {@link Permissions} enabled.
 160  *
 161  * Upon any error in establishing these settings, default parameters
 162  * are used. It is possible to disable or limit the use of threads in
 163  * the common pool by setting the parallelism property to zero, and/or
 164  * using a factory that may return {@code null}. However doing so may
 165  * cause unjoined tasks to never be executed.
 166  *
 167  * <p><b>Implementation notes</b>: This implementation restricts the
 168  * maximum number of running threads to 32767. Attempts to create
 169  * pools with greater than the maximum number result in
 170  * {@code IllegalArgumentException}.
 171  *
 172  * <p>This implementation rejects submitted tasks (that is, by throwing
 173  * {@link RejectedExecutionException}) only when the pool is shut down
 174  * or internal resources have been exhausted.
 175  *
 176  * @since 1.7
 177  * @author Doug Lea
 178  */
 179 public class ForkJoinPool extends AbstractExecutorService {
 180 
 181     /*
 182      * Implementation Overview
 183      *
 184      * This class and its nested classes provide the main
 185      * functionality and control for a set of worker threads:
 186      * Submissions from non-FJ threads enter into submission queues.
 187      * Workers take these tasks and typically split them into subtasks
 188      * that may be stolen by other workers. Work-stealing based on
 189      * randomized scans generally leads to better throughput than
 190      * "work dealing" in which producers assign tasks to idle threads,
 191      * in part because threads that have finished other tasks before
 192      * the signalled thread wakes up (which can be a long time) can
 193      * take the task instead.  Preference rules give first priority to
 194      * processing tasks from their own queues (LIFO or FIFO, depending
 195      * on mode), then to randomized FIFO steals of tasks in other
 196      * queues.  This framework began as vehicle for supporting
 197      * tree-structured parallelism using work-stealing.  Over time,
 198      * its scalability advantages led to extensions and changes to
 199      * better support more diverse usage contexts.  Because most
 200      * internal methods and nested classes are interrelated, their
 201      * main rationale and descriptions are presented here; individual
 202      * methods and nested classes contain only brief comments about
 203      * details.
 204      *
 205      * WorkQueues
 206      * ==========
 207      *
 208      * Most operations occur within work-stealing queues (in nested
 209      * class WorkQueue).  These are special forms of Deques that
 210      * support only three of the four possible end-operations -- push,
 211      * pop, and poll (aka steal), under the further constraints that
 212      * push and pop are called only from the owning thread (or, as
 213      * extended here, under a lock), while poll may be called from
 214      * other threads.  (If you are unfamiliar with them, you probably
 215      * want to read Herlihy and Shavit's book "The Art of
 216      * Multiprocessor programming", chapter 16 describing these in
 217      * more detail before proceeding.)  The main work-stealing queue
 218      * design is roughly similar to those in the papers "Dynamic
 219      * Circular Work-Stealing Deque" by Chase and Lev, SPAA 2005
 220      * (http://research.sun.com/scalable/pubs/index.html) and
 221      * "Idempotent work stealing" by Michael, Saraswat, and Vechev,
 222      * PPoPP 2009 (http://portal.acm.org/citation.cfm?id=1504186).
 223      * The main differences ultimately stem from GC requirements that
 224      * we null out taken slots as soon as we can, to maintain as small
 225      * a footprint as possible even in programs generating huge
 226      * numbers of tasks. To accomplish this, we shift the CAS
 227      * arbitrating pop vs poll (steal) from being on the indices
 228      * ("base" and "top") to the slots themselves.
 229      *
 230      * Adding tasks then takes the form of a classic array push(task)
 231      * in a circular buffer:
 232      *    q.array[q.top++ % length] = task;
 233      *
 234      * (The actual code needs to null-check and size-check the array,
 235      * uses masking, not mod, for indexing a power-of-two-sized array,
 236      * adds a release fence for publication, and possibly signals
 237      * waiting workers to start scanning -- see below.)  Both a
 238      * successful pop and poll mainly entail a CAS of a slot from
 239      * non-null to null.
 240      *
 241      * The pop operation (always performed by owner) is:
 242      *   if ((the task at top slot is not null) and
 243      *        (CAS slot to null))
 244      *           decrement top and return task;
 245      *
 246      * And the poll operation (usually by a stealer) is
 247      *    if ((the task at base slot is not null) and
 248      *        (CAS slot to null))
 249      *           increment base and return task;
 250      *
 251      * There are several variants of each of these. Most uses occur
 252      * within operations that also interleave contention or emptiness
 253      * tracking or inspection of elements before extracting them, so
 254      * must interleave these with the above code. When performed by
 255      * owner, getAndSet is used instead of CAS (see for example method
 256      * nextLocalTask) which is usually more efficient, and possible
 257      * because the top index cannot independently change during the
 258      * operation.
 259      *
 260      * Memory ordering.  See "Correct and Efficient Work-Stealing for
 261      * Weak Memory Models" by Le, Pop, Cohen, and Nardelli, PPoPP 2013
 262      * (http://www.di.ens.fr/~zappa/readings/ppopp13.pdf) for an
 263      * analysis of memory ordering requirements in work-stealing
 264      * algorithms similar to (but different than) the one used here.
 265      * Extracting tasks in array slots via (fully fenced) CAS provides
 266      * primary synchronization. The base and top indices imprecisely
 267      * guide where to extract from. We do not usually require strict
 268      * orderings of array and index updates. Many index accesses use
 269      * plain mode, with ordering constrained by surrounding context
 270      * (usually with respect to element CASes or the two WorkQueue
 271      * volatile fields source and phase). When not otherwise already
 272      * constrained, reads of "base" by queue owners use acquire-mode,
 273      * and some externally callable methods preface accesses with
 274      * acquire fences.  Additionally, to ensure that index update
 275      * writes are not coalesced or postponed in loops etc, "opaque"
 276      * mode is used in a few cases where timely writes are not
 277      * otherwise ensured. The "locked" versions of push- and pop-
 278      * based methods for shared queues differ from owned versions
 279      * because locking already forces some of the ordering.
 280      *
 281      * Because indices and slot contents cannot always be consistent,
 282      * a check that base == top indicates (momentary) emptiness, but
 283      * otherwise may err on the side of possibly making the queue
 284      * appear nonempty when a push, pop, or poll have not fully
 285      * committed, or making it appear empty when an update of top has
 286      * not yet been visibly written.  (Method isEmpty() checks the
 287      * case of a partially completed removal of the last element.)
 288      * Because of this, the poll operation, considered individually,
 289      * is not wait-free. One thief cannot successfully continue until
 290      * another in-progress one (or, if previously empty, a push)
 291      * visibly completes.  This can stall threads when required to
 292      * consume from a given queue (see method poll()).  However, in
 293      * the aggregate, we ensure at least probabilistic
 294      * non-blockingness.  If an attempted steal fails, a scanning
 295      * thief chooses a different random victim target to try next. So,
 296      * in order for one thief to progress, it suffices for any
 297      * in-progress poll or new push on any empty queue to complete.
 298      *
 299      * This approach also enables support of a user mode in which
 300      * local task processing is in FIFO, not LIFO order, simply by
 301      * using poll rather than pop.  This can be useful in
 302      * message-passing frameworks in which tasks are never joined.
 303      *
 304      * WorkQueues are also used in a similar way for tasks submitted
 305      * to the pool. We cannot mix these tasks in the same queues used
 306      * by workers. Instead, we randomly associate submission queues
 307      * with submitting threads, using a form of hashing.  The
 308      * ThreadLocalRandom probe value serves as a hash code for
 309      * choosing existing queues, and may be randomly repositioned upon
 310      * contention with other submitters.  In essence, submitters act
 311      * like workers except that they are restricted to executing local
 312      * tasks that they submitted.  Insertion of tasks in shared mode
 313      * requires a lock but we use only a simple spinlock (using field
 314      * phase), because submitters encountering a busy queue move to a
 315      * different position to use or create other queues -- they block
 316      * only when creating and registering new queues. Because it is
 317      * used only as a spinlock, unlocking requires only a "releasing"
 318      * store (using setRelease) unless otherwise signalling.
 319      *
 320      * Management
 321      * ==========
 322      *
 323      * The main throughput advantages of work-stealing stem from
 324      * decentralized control -- workers mostly take tasks from
 325      * themselves or each other, at rates that can exceed a billion
 326      * per second.  The pool itself creates, activates (enables
 327      * scanning for and running tasks), deactivates, blocks, and
 328      * terminates threads, all with minimal central information.
 329      * There are only a few properties that we can globally track or
 330      * maintain, so we pack them into a small number of variables,
 331      * often maintaining atomicity without blocking or locking.
 332      * Nearly all essentially atomic control state is held in a few
 333      * volatile variables that are by far most often read (not
 334      * written) as status and consistency checks. We pack as much
 335      * information into them as we can.
 336      *
 337      * Field "ctl" contains 64 bits holding information needed to
 338      * atomically decide to add, enqueue (on an event queue), and
 339      * dequeue and release workers.  To enable this packing, we
 340      * restrict maximum parallelism to (1<<15)-1 (which is far in
 341      * excess of normal operating range) to allow ids, counts, and
 342      * their negations (used for thresholding) to fit into 16bit
 343      * subfields.
 344      *
 345      * Field "mode" holds configuration parameters as well as lifetime
 346      * status, atomically and monotonically setting SHUTDOWN, STOP,
 347      * and finally TERMINATED bits.
 348      *
 349      * Field "workQueues" holds references to WorkQueues.  It is
 350      * updated (only during worker creation and termination) under
 351      * lock (using field workerNamePrefix as lock), but is otherwise
 352      * concurrently readable, and accessed directly. We also ensure
 353      * that uses of the array reference itself never become too stale
 354      * in case of resizing, by arranging that (re-)reads are separated
 355      * by at least one acquiring read access.  To simplify index-based
 356      * operations, the array size is always a power of two, and all
 357      * readers must tolerate null slots. Worker queues are at odd
 358      * indices. Shared (submission) queues are at even indices, up to
 359      * a maximum of 64 slots, to limit growth even if the array needs
 360      * to expand to add more workers. Grouping them together in this
 361      * way simplifies and speeds up task scanning.
 362      *
 363      * All worker thread creation is on-demand, triggered by task
 364      * submissions, replacement of terminated workers, and/or
 365      * compensation for blocked workers. However, all other support
 366      * code is set up to work with other policies.  To ensure that we
 367      * do not hold on to worker references that would prevent GC, all
 368      * accesses to workQueues are via indices into the workQueues
 369      * array (which is one source of some of the messy code
 370      * constructions here). In essence, the workQueues array serves as
 371      * a weak reference mechanism. Thus for example the stack top
 372      * subfield of ctl stores indices, not references.
 373      *
 374      * Queuing Idle Workers. Unlike HPC work-stealing frameworks, we
 375      * cannot let workers spin indefinitely scanning for tasks when
 376      * none can be found immediately, and we cannot start/resume
 377      * workers unless there appear to be tasks available.  On the
 378      * other hand, we must quickly prod them into action when new
 379      * tasks are submitted or generated. In many usages, ramp-up time
 380      * is the main limiting factor in overall performance, which is
 381      * compounded at program start-up by JIT compilation and
 382      * allocation. So we streamline this as much as possible.
 383      *
 384      * The "ctl" field atomically maintains total worker and
 385      * "released" worker counts, plus the head of the available worker
 386      * queue (actually stack, represented by the lower 32bit subfield
 387      * of ctl).  Released workers are those known to be scanning for
 388      * and/or running tasks. Unreleased ("available") workers are
 389      * recorded in the ctl stack. These workers are made available for
 390      * signalling by enqueuing in ctl (see method runWorker).  The
 391      * "queue" is a form of Treiber stack. This is ideal for
 392      * activating threads in most-recently used order, and improves
 393      * performance and locality, outweighing the disadvantages of
 394      * being prone to contention and inability to release a worker
 395      * unless it is topmost on stack.  To avoid missed signal problems
 396      * inherent in any wait/signal design, available workers rescan
 397      * for (and if found run) tasks after enqueuing.  Normally their
 398      * release status will be updated while doing so, but the released
 399      * worker ctl count may underestimate the number of active
 400      * threads. (However, it is still possible to determine quiescence
 401      * via a validation traversal -- see isQuiescent).  After an
 402      * unsuccessful rescan, available workers are blocked until
 403      * signalled (see signalWork).  The top stack state holds the
 404      * value of the "phase" field of the worker: its index and status,
 405      * plus a version counter that, in addition to the count subfields
 406      * (also serving as version stamps) provide protection against
 407      * Treiber stack ABA effects.
 408      *
 409      * Creating workers. To create a worker, we pre-increment counts
 410      * (serving as a reservation), and attempt to construct a
 411      * ForkJoinWorkerThread via its factory. Upon construction, the
 412      * new thread invokes registerWorker, where it constructs a
 413      * WorkQueue and is assigned an index in the workQueues array
 414      * (expanding the array if necessary). The thread is then started.
 415      * Upon any exception across these steps, or null return from
 416      * factory, deregisterWorker adjusts counts and records
 417      * accordingly.  If a null return, the pool continues running with
 418      * fewer than the target number workers. If exceptional, the
 419      * exception is propagated, generally to some external caller.
 420      * Worker index assignment avoids the bias in scanning that would
 421      * occur if entries were sequentially packed starting at the front
 422      * of the workQueues array. We treat the array as a simple
 423      * power-of-two hash table, expanding as needed. The seedIndex
 424      * increment ensures no collisions until a resize is needed or a
 425      * worker is deregistered and replaced, and thereafter keeps
 426      * probability of collision low. We cannot use
 427      * ThreadLocalRandom.getProbe() for similar purposes here because
 428      * the thread has not started yet, but do so for creating
 429      * submission queues for existing external threads (see
 430      * externalPush).
 431      *
 432      * WorkQueue field "phase" is used by both workers and the pool to
 433      * manage and track whether a worker is UNSIGNALLED (possibly
 434      * blocked waiting for a signal).  When a worker is enqueued its
 435      * phase field is set. Note that phase field updates lag queue CAS
 436      * releases so usage requires care -- seeing a negative phase does
 437      * not guarantee that the worker is available. When queued, the
 438      * lower 16 bits of scanState must hold its pool index. So we
 439      * place the index there upon initialization and otherwise keep it
 440      * there or restore it when necessary.
 441      *
 442      * The ctl field also serves as the basis for memory
 443      * synchronization surrounding activation. This uses a more
 444      * efficient version of a Dekker-like rule that task producers and
 445      * consumers sync with each other by both writing/CASing ctl (even
 446      * if to its current value).  This would be extremely costly. So
 447      * we relax it in several ways: (1) Producers only signal when
 448      * their queue is possibly empty at some point during a push
 449      * operation. (2) Other workers propagate this signal
 450      * when they find tasks in a queue with size greater than one. (3)
 451      * Workers only enqueue after scanning (see below) and not finding
 452      * any tasks.  (4) Rather than CASing ctl to its current value in
 453      * the common case where no action is required, we reduce write
 454      * contention by equivalently prefacing signalWork when called by
 455      * an external task producer using a memory access with
 456      * full-volatile semantics or a "fullFence".
 457      *
 458      * Almost always, too many signals are issued, in part because a
 459      * task producer cannot tell if some existing worker is in the
 460      * midst of finishing one task (or already scanning) and ready to
 461      * take another without being signalled. So the producer might
 462      * instead activate a different worker that does not find any
 463      * work, and then inactivates. This scarcely matters in
 464      * steady-state computations involving all workers, but can create
 465      * contention and bookkeeping bottlenecks during ramp-up,
 466      * ramp-down, and small computations involving only a few workers.
 467      *
 468      * Scanning. Method scan (from runWorker) performs top-level
 469      * scanning for tasks. (Similar scans appear in helpQuiesce and
 470      * pollScan.)  Each scan traverses and tries to poll from each
 471      * queue starting at a random index. Scans are not performed in
 472      * ideal random permutation order, to reduce cacheline
 473      * contention. The pseudorandom generator need not have
 474      * high-quality statistical properties in the long term, but just
 475      * within computations; We use Marsaglia XorShifts (often via
 476      * ThreadLocalRandom.nextSecondarySeed), which are cheap and
 477      * suffice. Scanning also includes contention reduction: When
 478      * scanning workers fail to extract an apparently existing task,
 479      * they soon restart at a different pseudorandom index.  This form
 480      * of backoff improves throughput when many threads are trying to
 481      * take tasks from few queues, which can be common in some usages.
 482      * Scans do not otherwise explicitly take into account core
 483      * affinities, loads, cache localities, etc, However, they do
 484      * exploit temporal locality (which usually approximates these) by
 485      * preferring to re-poll from the same queue after a successful
 486      * poll before trying others (see method topLevelExec). However
 487      * this preference is bounded (see TOP_BOUND_SHIFT) as a safeguard
 488      * against infinitely unfair looping under unbounded user task
 489      * recursion, and also to reduce long-term contention when many
 490      * threads poll few queues holding many small tasks. The bound is
 491      * high enough to avoid much impact on locality and scheduling
 492      * overhead.
 493      *
 494      * Trimming workers. To release resources after periods of lack of
 495      * use, a worker starting to wait when the pool is quiescent will
 496      * time out and terminate (see method runWorker) if the pool has
 497      * remained quiescent for period given by field keepAlive.
 498      *
 499      * Shutdown and Termination. A call to shutdownNow invokes
 500      * tryTerminate to atomically set a runState bit. The calling
 501      * thread, as well as every other worker thereafter terminating,
 502      * helps terminate others by cancelling their unprocessed tasks,
 503      * and waking them up, doing so repeatedly until stable. Calls to
 504      * non-abrupt shutdown() preface this by checking whether
 505      * termination should commence by sweeping through queues (until
 506      * stable) to ensure lack of in-flight submissions and workers
 507      * about to process them before triggering the "STOP" phase of
 508      * termination.
 509      *
 510      * Joining Tasks
 511      * =============
 512      *
 513      * Any of several actions may be taken when one worker is waiting
 514      * to join a task stolen (or always held) by another.  Because we
 515      * are multiplexing many tasks on to a pool of workers, we can't
 516      * always just let them block (as in Thread.join).  We also cannot
 517      * just reassign the joiner's run-time stack with another and
 518      * replace it later, which would be a form of "continuation", that
 519      * even if possible is not necessarily a good idea since we may
 520      * need both an unblocked task and its continuation to progress.
 521      * Instead we combine two tactics:
 522      *
 523      *   Helping: Arranging for the joiner to execute some task that it
 524      *      would be running if the steal had not occurred.
 525      *
 526      *   Compensating: Unless there are already enough live threads,
 527      *      method tryCompensate() may create or re-activate a spare
 528      *      thread to compensate for blocked joiners until they unblock.
 529      *
 530      * A third form (implemented in tryRemoveAndExec) amounts to
 531      * helping a hypothetical compensator: If we can readily tell that
 532      * a possible action of a compensator is to steal and execute the
 533      * task being joined, the joining thread can do so directly,
 534      * without the need for a compensation thread.
 535      *
 536      * The ManagedBlocker extension API can't use helping so relies
 537      * only on compensation in method awaitBlocker.
 538      *
 539      * The algorithm in awaitJoin entails a form of "linear helping".
 540      * Each worker records (in field source) the id of the queue from
 541      * which it last stole a task.  The scan in method awaitJoin uses
 542      * these markers to try to find a worker to help (i.e., steal back
 543      * a task from and execute it) that could hasten completion of the
 544      * actively joined task.  Thus, the joiner executes a task that
 545      * would be on its own local deque if the to-be-joined task had
 546      * not been stolen. This is a conservative variant of the approach
 547      * described in Wagner & Calder "Leapfrogging: a portable
 548      * technique for implementing efficient futures" SIGPLAN Notices,
 549      * 1993 (http://portal.acm.org/citation.cfm?id=155354). It differs
 550      * mainly in that we only record queue ids, not full dependency
 551      * links.  This requires a linear scan of the workQueues array to
 552      * locate stealers, but isolates cost to when it is needed, rather
 553      * than adding to per-task overhead. Searches can fail to locate
 554      * stealers GC stalls and the like delay recording sources.
 555      * Further, even when accurately identified, stealers might not
 556      * ever produce a task that the joiner can in turn help with. So,
 557      * compensation is tried upon failure to find tasks to run.
 558      *
 559      * Compensation does not by default aim to keep exactly the target
 560      * parallelism number of unblocked threads running at any given
 561      * time. Some previous versions of this class employed immediate
 562      * compensations for any blocked join. However, in practice, the
 563      * vast majority of blockages are transient byproducts of GC and
 564      * other JVM or OS activities that are made worse by replacement
 565      * when they cause longer-term oversubscription.  Rather than
 566      * impose arbitrary policies, we allow users to override the
 567      * default of only adding threads upon apparent starvation.  The
 568      * compensation mechanism may also be bounded.  Bounds for the
 569      * commonPool (see COMMON_MAX_SPARES) better enable JVMs to cope
 570      * with programming errors and abuse before running out of
 571      * resources to do so.
 572      *
 573      * Common Pool
 574      * ===========
 575      *
 576      * The static common pool always exists after static
 577      * initialization.  Since it (or any other created pool) need
 578      * never be used, we minimize initial construction overhead and
 579      * footprint to the setup of about a dozen fields.
 580      *
 581      * When external threads submit to the common pool, they can
 582      * perform subtask processing (see externalHelpComplete and
 583      * related methods) upon joins.  This caller-helps policy makes it
 584      * sensible to set common pool parallelism level to one (or more)
 585      * less than the total number of available cores, or even zero for
 586      * pure caller-runs.  We do not need to record whether external
 587      * submissions are to the common pool -- if not, external help
 588      * methods return quickly. These submitters would otherwise be
 589      * blocked waiting for completion, so the extra effort (with
 590      * liberally sprinkled task status checks) in inapplicable cases
 591      * amounts to an odd form of limited spin-wait before blocking in
 592      * ForkJoinTask.join.
 593      *
 594      * As a more appropriate default in managed environments, unless
 595      * overridden by system properties, we use workers of subclass
 596      * InnocuousForkJoinWorkerThread when there is a SecurityManager
 597      * present. These workers have no permissions set, do not belong
 598      * to any user-defined ThreadGroup, and erase all ThreadLocals
 599      * after executing any top-level task (see
 600      * WorkQueue.afterTopLevelExec).  The associated mechanics (mainly
 601      * in ForkJoinWorkerThread) may be JVM-dependent and must access
 602      * particular Thread class fields to achieve this effect.
 603      *
 604      * Memory placement
 605      * ================
 606      *
 607      * Performance can be very sensitive to placement of instances of
 608      * ForkJoinPool and WorkQueues and their queue arrays. To reduce
 609      * false-sharing impact, the @Contended annotation isolates
 610      * adjacent WorkQueue instances, as well as the ForkJoinPool.ctl
 611      * field. WorkQueue arrays are allocated (by their threads) with
 612      * larger initial sizes than most ever need, mostly to reduce
 613      * false sharing with current garbage collectors that use cardmark
 614      * tables.
 615      *
 616      * Style notes
 617      * ===========
 618      *
 619      * Memory ordering relies mainly on VarHandles.  This can be
 620      * awkward and ugly, but also reflects the need to control
 621      * outcomes across the unusual cases that arise in very racy code
 622      * with very few invariants. All fields are read into locals
 623      * before use, and null-checked if they are references.  Array
 624      * accesses using masked indices include checks (that are always
 625      * true) that the array length is non-zero to avoid compilers
 626      * inserting more expensive traps.  This is usually done in a
 627      * "C"-like style of listing declarations at the heads of methods
 628      * or blocks, and using inline assignments on first encounter.
 629      * Nearly all explicit checks lead to bypass/return, not exception
 630      * throws, because they may legitimately arise due to
 631      * cancellation/revocation during shutdown.
 632      *
 633      * There is a lot of representation-level coupling among classes
 634      * ForkJoinPool, ForkJoinWorkerThread, and ForkJoinTask.  The
 635      * fields of WorkQueue maintain data structures managed by
 636      * ForkJoinPool, so are directly accessed.  There is little point
 637      * trying to reduce this, since any associated future changes in
 638      * representations will need to be accompanied by algorithmic
 639      * changes anyway. Several methods intrinsically sprawl because
 640      * they must accumulate sets of consistent reads of fields held in
 641      * local variables. Some others are artificially broken up to
 642      * reduce producer/consumer imbalances due to dynamic compilation.
 643      * There are also other coding oddities (including several
 644      * unnecessary-looking hoisted null checks) that help some methods
 645      * perform reasonably even when interpreted (not compiled).
 646      *
 647      * The order of declarations in this file is (with a few exceptions):
 648      * (1) Static utility functions
 649      * (2) Nested (static) classes
 650      * (3) Static fields
 651      * (4) Fields, along with constants used when unpacking some of them
 652      * (5) Internal control methods
 653      * (6) Callbacks and other support for ForkJoinTask methods
 654      * (7) Exported methods
 655      * (8) Static block initializing statics in minimally dependent order
 656      */
 657 
 658     // Static utilities
 659 
 660     /**
 661      * If there is a security manager, makes sure caller has
 662      * permission to modify threads.
 663      */
 664     private static void checkPermission() {
 665         SecurityManager security = System.getSecurityManager();
 666         if (security != null)
 667             security.checkPermission(modifyThreadPermission);
 668     }
 669 
 670     // Nested classes
 671 
 672     /**
 673      * Factory for creating new {@link ForkJoinWorkerThread}s.
 674      * A {@code ForkJoinWorkerThreadFactory} must be defined and used
 675      * for {@code ForkJoinWorkerThread} subclasses that extend base
 676      * functionality or initialize threads with different contexts.
 677      */
 678     public static interface ForkJoinWorkerThreadFactory {
 679         /**
 680          * Returns a new worker thread operating in the given pool.
 681          * Returning null or throwing an exception may result in tasks
 682          * never being executed.  If this method throws an exception,
 683          * it is relayed to the caller of the method (for example
 684          * {@code execute}) causing attempted thread creation. If this
 685          * method returns null or throws an exception, it is not
 686          * retried until the next attempted creation (for example
 687          * another call to {@code execute}).
 688          *
 689          * @param pool the pool this thread works in
 690          * @return the new worker thread, or {@code null} if the request
 691          *         to create a thread is rejected
 692          * @throws NullPointerException if the pool is null
 693          */
 694         public ForkJoinWorkerThread newThread(ForkJoinPool pool);
 695     }
 696 
 697     static AccessControlContext contextWithPermissions(Permission ... perms) {
 698         Permissions permissions = new Permissions();
 699         for (Permission perm : perms)
 700             permissions.add(perm);
 701         return new AccessControlContext(
 702             new ProtectionDomain[] { new ProtectionDomain(null, permissions) });
 703     }
 704 
 705     /**
 706      * Default ForkJoinWorkerThreadFactory implementation; creates a
 707      * new ForkJoinWorkerThread using the system class loader as the
 708      * thread context class loader.
 709      */
 710     private static final class DefaultForkJoinWorkerThreadFactory
 711         implements ForkJoinWorkerThreadFactory {
 712         private static final AccessControlContext ACC = contextWithPermissions(
 713             new RuntimePermission("getClassLoader"),
 714             new RuntimePermission("setContextClassLoader"));
 715 
 716         public final ForkJoinWorkerThread newThread(ForkJoinPool pool) {
 717             return AccessController.doPrivileged(
 718                 new PrivilegedAction<>() {
 719                     public ForkJoinWorkerThread run() {
 720                         return new ForkJoinWorkerThread(
 721                             pool, ClassLoader.getSystemClassLoader()); }},
 722                 ACC);
 723         }
 724     }
 725 
 726     // Constants shared across ForkJoinPool and WorkQueue
 727 
 728     // Bounds
 729     static final int SWIDTH       = 16;            // width of short
 730     static final int SMASK        = 0xffff;        // short bits == max index
 731     static final int MAX_CAP      = 0x7fff;        // max #workers - 1
 732     static final int SQMASK       = 0x007e;        // max 64 (even) slots
 733 
 734     // Masks and units for WorkQueue.phase and ctl sp subfield
 735     static final int UNSIGNALLED  = 1 << 31;       // must be negative
 736     static final int SS_SEQ       = 1 << 16;       // version count
 737     static final int QLOCK        = 1;             // must be 1
 738 
 739     // Mode bits and sentinels, some also used in WorkQueue id and.source fields
 740     static final int OWNED        = 1;             // queue has owner thread
 741     static final int FIFO         = 1 << 16;       // fifo queue or access mode
 742     static final int SHUTDOWN     = 1 << 18;
 743     static final int TERMINATED   = 1 << 19;
 744     static final int STOP         = 1 << 31;       // must be negative
 745     static final int QUIET        = 1 << 30;       // not scanning or working
 746     static final int DORMANT      = QUIET | UNSIGNALLED;
 747 
 748     /**
 749      * Initial capacity of work-stealing queue array.
 750      * Must be a power of two, at least 2.
 751      */
 752     static final int INITIAL_QUEUE_CAPACITY = 1 << 13;
 753 
 754     /**
 755      * Maximum capacity for queue arrays. Must be a power of two less
 756      * than or equal to 1 << (31 - width of array entry) to ensure
 757      * lack of wraparound of index calculations, but defined to a
 758      * value a bit less than this to help users trap runaway programs
 759      * before saturating systems.
 760      */
 761     static final int MAXIMUM_QUEUE_CAPACITY = 1 << 26; // 64M
 762 
 763     /**
 764      * The maximum number of top-level polls per worker before
 765      * checking other queues, expressed as a bit shift.  See above for
 766      * rationale.
 767      */
 768     static final int TOP_BOUND_SHIFT = 10;
 769 
 770     /**
 771      * Queues supporting work-stealing as well as external task
 772      * submission. See above for descriptions and algorithms.
 773      */
 774     @jdk.internal.vm.annotation.Contended
 775     static final class WorkQueue {
 776         volatile int source;       // source queue id, or sentinel
 777         int id;                    // pool index, mode, tag
 778         int base;                  // index of next slot for poll
 779         int top;                   // index of next slot for push
 780         volatile int phase;        // versioned, negative: queued, 1: locked
 781         int stackPred;             // pool stack (ctl) predecessor link
 782         int nsteals;               // number of steals
 783         ForkJoinTask<?>[] array;   // the queued tasks; power of 2 size
 784         final ForkJoinPool pool;   // the containing pool (may be null)
 785         final ForkJoinWorkerThread owner; // owning thread or null if shared
 786 
 787         WorkQueue(ForkJoinPool pool, ForkJoinWorkerThread owner) {
 788             this.pool = pool;
 789             this.owner = owner;
 790             // Place indices in the center of array (that is not yet allocated)
 791             base = top = INITIAL_QUEUE_CAPACITY >>> 1;
 792         }
 793 
 794         /**
 795          * Tries to lock shared queue by CASing phase field.
 796          */
 797         final boolean tryLockPhase() {
 798             return PHASE.compareAndSet(this, 0, 1);
 799         }
 800 
 801         final void releasePhaseLock() {
 802             PHASE.setRelease(this, 0);
 803         }
 804 
 805         /**
 806          * Returns an exportable index (used by ForkJoinWorkerThread).
 807          */
 808         final int getPoolIndex() {
 809             return (id & 0xffff) >>> 1; // ignore odd/even tag bit
 810         }
 811 
 812         /**
 813          * Returns the approximate number of tasks in the queue.
 814          */
 815         final int queueSize() {
 816             int n = (int)BASE.getAcquire(this) - top;
 817             return (n >= 0) ? 0 : -n; // ignore transient negative
 818         }
 819 
 820         /**
 821          * Provides a more accurate estimate of whether this queue has
 822          * any tasks than does queueSize, by checking whether a
 823          * near-empty queue has at least one unclaimed task.
 824          */
 825         final boolean isEmpty() {
 826             ForkJoinTask<?>[] a; int n, cap, b;
 827             VarHandle.acquireFence(); // needed by external callers
 828             return ((n = (b = base) - top) >= 0 || // possibly one task
 829                     (n == -1 && ((a = array) == null ||
 830                                  (cap = a.length) == 0 ||
 831                                  a[(cap - 1) & b] == null)));
 832         }
 833 
 834         /**
 835          * Pushes a task. Call only by owner in unshared queues.
 836          *
 837          * @param task the task. Caller must ensure non-null.
 838          * @throws RejectedExecutionException if array cannot be resized
 839          */
 840         final void push(ForkJoinTask<?> task) {
 841             ForkJoinTask<?>[] a;
 842             int s = top, d = s - base, cap, m;
 843             ForkJoinPool p = pool;
 844             if ((a = array) != null && (cap = a.length) > 0) {
 845                 QA.setRelease(a, (m = cap - 1) & s, task);
 846                 top = s + 1;
 847                 if (d == m)
 848                     growArray(false);
 849                 else if (QA.getAcquire(a, m & (s - 1)) == null && p != null) {
 850                     VarHandle.fullFence();  // was empty
 851                     p.signalWork(null);
 852                 }
 853             }
 854         }
 855 
 856         /**
 857          * Version of push for shared queues. Call only with phase lock held.
 858          * @return true if should signal work
 859          */
 860         final boolean lockedPush(ForkJoinTask<?> task) {
 861             ForkJoinTask<?>[] a;
 862             boolean signal = false;
 863             int s = top, d = s - base, cap, m;
 864             if ((a = array) != null && (cap = a.length) > 0) {
 865                 a[(m = (cap - 1)) & s] = task;
 866                 top = s + 1;
 867                 if (d == m)
 868                     growArray(true);
 869                 else {
 870                     phase = 0; // full volatile unlock
 871                     if (((s - base) & ~1) == 0) // size 0 or 1
 872                         signal = true;
 873                 }
 874             }
 875             return signal;
 876         }
 877 
 878         /**
 879          * Doubles the capacity of array. Call either by owner or with
 880          * lock held -- it is OK for base, but not top, to move while
 881          * resizings are in progress.
 882          */
 883         final void growArray(boolean locked) {
 884             ForkJoinTask<?>[] newA = null;
 885             try {
 886                 ForkJoinTask<?>[] oldA; int oldSize, newSize;
 887                 if ((oldA = array) != null && (oldSize = oldA.length) > 0 &&
 888                     (newSize = oldSize << 1) <= MAXIMUM_QUEUE_CAPACITY &&
 889                     newSize > 0) {
 890                     try {
 891                         newA = new ForkJoinTask<?>[newSize];
 892                     } catch (OutOfMemoryError ex) {
 893                     }
 894                     if (newA != null) { // poll from old array, push to new
 895                         int oldMask = oldSize - 1, newMask = newSize - 1;
 896                         for (int s = top - 1, k = oldMask; k >= 0; --k) {
 897                             ForkJoinTask<?> x = (ForkJoinTask<?>)
 898                                 QA.getAndSet(oldA, s & oldMask, null);
 899                             if (x != null)
 900                                 newA[s-- & newMask] = x;
 901                             else
 902                                 break;
 903                         }
 904                         array = newA;
 905                         VarHandle.releaseFence();
 906                     }
 907                 }
 908             } finally {
 909                 if (locked)
 910                     phase = 0;
 911             }
 912             if (newA == null)
 913                 throw new RejectedExecutionException("Queue capacity exceeded");
 914         }
 915 
 916         /**
 917          * Takes next task, if one exists, in FIFO order.
 918          */
 919         final ForkJoinTask<?> poll() {
 920             int b, k, cap; ForkJoinTask<?>[] a;
 921             while ((a = array) != null && (cap = a.length) > 0 &&
 922                    top - (b = base) > 0) {
 923                 ForkJoinTask<?> t = (ForkJoinTask<?>)
 924                     QA.getAcquire(a, k = (cap - 1) & b);
 925                 if (base == b++) {
 926                     if (t == null)
 927                         Thread.yield(); // await index advance
 928                     else if (QA.compareAndSet(a, k, t, null)) {
 929                         BASE.setOpaque(this, b);
 930                         return t;
 931                     }
 932                 }
 933             }
 934             return null;
 935         }
 936 
 937         /**
 938          * Takes next task, if one exists, in order specified by mode.
 939          */
 940         final ForkJoinTask<?> nextLocalTask() {
 941             ForkJoinTask<?> t = null;
 942             int md = id, b, s, d, cap; ForkJoinTask<?>[] a;
 943             if ((a = array) != null && (cap = a.length) > 0 &&
 944                 (d = (s = top) - (b = base)) > 0) {
 945                 if ((md & FIFO) == 0 || d == 1) {
 946                     if ((t = (ForkJoinTask<?>)
 947                          QA.getAndSet(a, (cap - 1) & --s, null)) != null)
 948                         TOP.setOpaque(this, s);
 949                 }
 950                 else if ((t = (ForkJoinTask<?>)
 951                           QA.getAndSet(a, (cap - 1) & b++, null)) != null) {
 952                     BASE.setOpaque(this, b);
 953                 }
 954                 else // on contention in FIFO mode, use regular poll
 955                     t = poll();
 956             }
 957             return t;
 958         }
 959 
 960         /**
 961          * Returns next task, if one exists, in order specified by mode.
 962          */
 963         final ForkJoinTask<?> peek() {
 964             int cap; ForkJoinTask<?>[] a;
 965             return ((a = array) != null && (cap = a.length) > 0) ?
 966                 a[(cap - 1) & ((id & FIFO) != 0 ? base : top - 1)] : null;
 967         }
 968 
 969         /**
 970          * Pops the given task only if it is at the current top.
 971          */
 972         final boolean tryUnpush(ForkJoinTask<?> task) {
 973             boolean popped = false;
 974             int s, cap; ForkJoinTask<?>[] a;
 975             if ((a = array) != null && (cap = a.length) > 0 &&
 976                 (s = top) != base &&
 977                 (popped = QA.compareAndSet(a, (cap - 1) & --s, task, null)))
 978                 TOP.setOpaque(this, s);
 979             return popped;
 980         }
 981 
 982         /**
 983          * Shared version of tryUnpush.
 984          */
 985         final boolean tryLockedUnpush(ForkJoinTask<?> task) {
 986             boolean popped = false;
 987             int s = top - 1, k, cap; ForkJoinTask<?>[] a;
 988             if ((a = array) != null && (cap = a.length) > 0 &&
 989                 a[k = (cap - 1) & s] == task && tryLockPhase()) {
 990                 if (top == s + 1 && array == a &&
 991                     (popped = QA.compareAndSet(a, k, task, null)))
 992                     top = s;
 993                 releasePhaseLock();
 994             }
 995             return popped;
 996         }
 997 
 998         /**
 999          * Removes and cancels all known tasks, ignoring any exceptions.
1000          */
1001         final void cancelAll() {
1002             for (ForkJoinTask<?> t; (t = poll()) != null; )
1003                 ForkJoinTask.cancelIgnoringExceptions(t);
1004         }
1005 
1006         // Specialized execution methods
1007 
1008         /**
1009          * Runs the given (stolen) task if nonnull, as well as
1010          * remaining local tasks and others available from the given
1011          * queue, up to bound n (to avoid infinite unfairness).
1012          */
1013         final void topLevelExec(ForkJoinTask<?> t, WorkQueue q, int n) {
1014             int nstolen = 1;
1015             for (int j = 0;;) {
1016                 if (t != null)
1017                     t.doExec();
1018                 if (j++ <= n)
1019                     t = nextLocalTask();
1020                 else {
1021                     j = 0;
1022                     t = null;
1023                 }
1024                 if (t == null) {
1025                     if (q != null && (t = q.poll()) != null) {
1026                         ++nstolen;
1027                         j = 0;
1028                     }
1029                     else if (j != 0)
1030                         break;
1031                 }
1032             }
1033             ForkJoinWorkerThread thread = owner;
1034             nsteals += nstolen;
1035             source = 0;
1036             if (thread != null)
1037                 thread.afterTopLevelExec();
1038         }
1039 
1040         /**
1041          * If present, removes task from queue and executes it.
1042          */
1043         final void tryRemoveAndExec(ForkJoinTask<?> task) {
1044             ForkJoinTask<?>[] a; int s, cap;
1045             if ((a = array) != null && (cap = a.length) > 0 &&
1046                 (s = top) - base > 0) { // traverse from top
1047                 for (int m = cap - 1, ns = s - 1, i = ns; ; --i) {
1048                     int index = i & m;
1049                     ForkJoinTask<?> t = (ForkJoinTask<?>)QA.get(a, index);
1050                     if (t == null)
1051                         break;
1052                     else if (t == task) {
1053                         if (QA.compareAndSet(a, index, t, null)) {
1054                             top = ns;   // safely shift down
1055                             for (int j = i; j != ns; ++j) {
1056                                 ForkJoinTask<?> f;
1057                                 int pindex = (j + 1) & m;
1058                                 f = (ForkJoinTask<?>)QA.get(a, pindex);
1059                                 QA.setVolatile(a, pindex, null);
1060                                 int jindex = j & m;
1061                                 QA.setRelease(a, jindex, f);
1062                             }
1063                             VarHandle.releaseFence();
1064                             t.doExec();
1065                         }
1066                         break;
1067                     }
1068                 }
1069             }
1070         }
1071 
1072         /**
1073          * Tries to pop and run tasks within the target's computation
1074          * until done, not found, or limit exceeded.
1075          *
1076          * @param task root of CountedCompleter computation
1077          * @param limit max runs, or zero for no limit
1078          * @param shared true if must lock to extract task
1079          * @return task status on exit
1080          */
1081         final int helpCC(CountedCompleter<?> task, int limit, boolean shared) {
1082             int status = 0;
1083             if (task != null && (status = task.status) >= 0) {
1084                 int s, k, cap; ForkJoinTask<?>[] a;
1085                 while ((a = array) != null && (cap = a.length) > 0 &&
1086                        (s = top) - base > 0) {
1087                     CountedCompleter<?> v = null;
1088                     ForkJoinTask<?> o = a[k = (cap - 1) & (s - 1)];
1089                     if (o instanceof CountedCompleter) {
1090                         CountedCompleter<?> t = (CountedCompleter<?>)o;
1091                         for (CountedCompleter<?> f = t;;) {
1092                             if (f != task) {
1093                                 if ((f = f.completer) == null)
1094                                     break;
1095                             }
1096                             else if (shared) {
1097                                 if (tryLockPhase()) {
1098                                     if (top == s && array == a &&
1099                                         QA.compareAndSet(a, k, t, null)) {
1100                                         top = s - 1;
1101                                         v = t;
1102                                     }
1103                                     releasePhaseLock();
1104                                 }
1105                                 break;
1106                             }
1107                             else {
1108                                 if (QA.compareAndSet(a, k, t, null)) {
1109                                     top = s - 1;
1110                                     v = t;
1111                                 }
1112                                 break;
1113                             }
1114                         }
1115                     }
1116                     if (v != null)
1117                         v.doExec();
1118                     if ((status = task.status) < 0 || v == null ||
1119                         (limit != 0 && --limit == 0))
1120                         break;
1121                 }
1122             }
1123             return status;
1124         }
1125 
1126         /**
1127          * Tries to poll and run AsynchronousCompletionTasks until
1128          * none found or blocker is released
1129          *
1130          * @param blocker the blocker
1131          */
1132         final void helpAsyncBlocker(ManagedBlocker blocker) {
1133             if (blocker != null) {
1134                 int b, k, cap; ForkJoinTask<?>[] a; ForkJoinTask<?> t;
1135                 while ((a = array) != null && (cap = a.length) > 0 &&
1136                        top - (b = base) > 0) {
1137                     t = (ForkJoinTask<?>)QA.getAcquire(a, k = (cap - 1) & b);
1138                     if (blocker.isReleasable())
1139                         break;
1140                     else if (base == b++ && t != null) {
1141                         if (!(t instanceof CompletableFuture.
1142                               AsynchronousCompletionTask))
1143                             break;
1144                         else if (QA.compareAndSet(a, k, t, null)) {
1145                             BASE.setOpaque(this, b);
1146                             t.doExec();
1147                         }
1148                     }
1149                 }
1150             }
1151         }
1152 
1153         /**
1154          * Returns true if owned and not known to be blocked.
1155          */
1156         final boolean isApparentlyUnblocked() {
1157             Thread wt; Thread.State s;
1158             return ((wt = owner) != null &&
1159                     (s = wt.getState()) != Thread.State.BLOCKED &&
1160                     s != Thread.State.WAITING &&
1161                     s != Thread.State.TIMED_WAITING);
1162         }
1163 
1164         // VarHandle mechanics.
1165         static final VarHandle PHASE;
1166         static final VarHandle BASE;
1167         static final VarHandle TOP;
1168         static {
1169             try {
1170                 MethodHandles.Lookup l = MethodHandles.lookup();
1171                 PHASE = l.findVarHandle(WorkQueue.class, "phase", int.class);
1172                 BASE = l.findVarHandle(WorkQueue.class, "base", int.class);
1173                 TOP = l.findVarHandle(WorkQueue.class, "top", int.class);
1174             } catch (ReflectiveOperationException e) {
1175                 throw new ExceptionInInitializerError(e);
1176             }
1177         }
1178     }
1179 
1180     // static fields (initialized in static initializer below)
1181 
1182     /**
1183      * Creates a new ForkJoinWorkerThread. This factory is used unless
1184      * overridden in ForkJoinPool constructors.
1185      */
1186     public static final ForkJoinWorkerThreadFactory
1187         defaultForkJoinWorkerThreadFactory;
1188 
1189     /**
1190      * Permission required for callers of methods that may start or
1191      * kill threads.
1192      */
1193     static final RuntimePermission modifyThreadPermission;
1194 
1195     /**
1196      * Common (static) pool. Non-null for public use unless a static
1197      * construction exception, but internal usages null-check on use
1198      * to paranoically avoid potential initialization circularities
1199      * as well as to simplify generated code.
1200      */
1201     static final ForkJoinPool common;
1202 
1203     /**
1204      * Common pool parallelism. To allow simpler use and management
1205      * when common pool threads are disabled, we allow the underlying
1206      * common.parallelism field to be zero, but in that case still report
1207      * parallelism as 1 to reflect resulting caller-runs mechanics.
1208      */
1209     static final int COMMON_PARALLELISM;
1210 
1211     /**
1212      * Limit on spare thread construction in tryCompensate.
1213      */
1214     private static final int COMMON_MAX_SPARES;
1215 
1216     /**
1217      * Sequence number for creating workerNamePrefix.
1218      */
1219     private static int poolNumberSequence;
1220 
1221     /**
1222      * Returns the next sequence number. We don't expect this to
1223      * ever contend, so use simple builtin sync.
1224      */
1225     private static final synchronized int nextPoolId() {
1226         return ++poolNumberSequence;
1227     }
1228 
1229     // static configuration constants
1230 
1231     /**
1232      * Default idle timeout value (in milliseconds) for the thread
1233      * triggering quiescence to park waiting for new work
1234      */
1235     private static final long DEFAULT_KEEPALIVE = 60_000L;
1236 
1237     /**
1238      * Undershoot tolerance for idle timeouts
1239      */
1240     private static final long TIMEOUT_SLOP = 20L;
1241 
1242     /**
1243      * The default value for COMMON_MAX_SPARES.  Overridable using the
1244      * "java.util.concurrent.ForkJoinPool.common.maximumSpares" system
1245      * property.  The default value is far in excess of normal
1246      * requirements, but also far short of MAX_CAP and typical OS
1247      * thread limits, so allows JVMs to catch misuse/abuse before
1248      * running out of resources needed to do so.
1249      */
1250     private static final int DEFAULT_COMMON_MAX_SPARES = 256;
1251 
1252     /**
1253      * Increment for seed generators. See class ThreadLocal for
1254      * explanation.
1255      */
1256     private static final int SEED_INCREMENT = 0x9e3779b9;
1257 
1258     /*
1259      * Bits and masks for field ctl, packed with 4 16 bit subfields:
1260      * RC: Number of released (unqueued) workers minus target parallelism
1261      * TC: Number of total workers minus target parallelism
1262      * SS: version count and status of top waiting thread
1263      * ID: poolIndex of top of Treiber stack of waiters
1264      *
1265      * When convenient, we can extract the lower 32 stack top bits
1266      * (including version bits) as sp=(int)ctl.  The offsets of counts
1267      * by the target parallelism and the positionings of fields makes
1268      * it possible to perform the most common checks via sign tests of
1269      * fields: When ac is negative, there are not enough unqueued
1270      * workers, when tc is negative, there are not enough total
1271      * workers.  When sp is non-zero, there are waiting workers.  To
1272      * deal with possibly negative fields, we use casts in and out of
1273      * "short" and/or signed shifts to maintain signedness.
1274      *
1275      * Because it occupies uppermost bits, we can add one release count
1276      * using getAndAddLong of RC_UNIT, rather than CAS, when returning
1277      * from a blocked join.  Other updates entail multiple subfields
1278      * and masking, requiring CAS.
1279      *
1280      * The limits packed in field "bounds" are also offset by the
1281      * parallelism level to make them comparable to the ctl rc and tc
1282      * fields.
1283      */
1284 
1285     // Lower and upper word masks
1286     private static final long SP_MASK    = 0xffffffffL;
1287     private static final long UC_MASK    = ~SP_MASK;
1288 
1289     // Release counts
1290     private static final int  RC_SHIFT   = 48;
1291     private static final long RC_UNIT    = 0x0001L << RC_SHIFT;
1292     private static final long RC_MASK    = 0xffffL << RC_SHIFT;
1293 
1294     // Total counts
1295     private static final int  TC_SHIFT   = 32;
1296     private static final long TC_UNIT    = 0x0001L << TC_SHIFT;
1297     private static final long TC_MASK    = 0xffffL << TC_SHIFT;
1298     private static final long ADD_WORKER = 0x0001L << (TC_SHIFT + 15); // sign
1299 
1300     // Instance fields
1301 
1302     volatile long stealCount;            // collects worker nsteals
1303     final long keepAlive;                // milliseconds before dropping if idle
1304     int indexSeed;                       // next worker index
1305     final int bounds;                    // min, max threads packed as shorts
1306     volatile int mode;                   // parallelism, runstate, queue mode
1307     WorkQueue[] workQueues;              // main registry
1308     final String workerNamePrefix;       // for worker thread string; sync lock
1309     final ForkJoinWorkerThreadFactory factory;
1310     final UncaughtExceptionHandler ueh;  // per-worker UEH
1311     final Predicate<? super ForkJoinPool> saturate;
1312 
1313     @jdk.internal.vm.annotation.Contended("fjpctl") // segregate
1314     volatile long ctl;                   // main pool control
1315 
1316     // Creating, registering and deregistering workers
1317 
1318     /**
1319      * Tries to construct and start one worker. Assumes that total
1320      * count has already been incremented as a reservation.  Invokes
1321      * deregisterWorker on any failure.
1322      *
1323      * @return true if successful
1324      */
1325     private boolean createWorker() {
1326         ForkJoinWorkerThreadFactory fac = factory;
1327         Throwable ex = null;
1328         ForkJoinWorkerThread wt = null;
1329         try {
1330             if (fac != null && (wt = fac.newThread(this)) != null) {
1331                 wt.start();
1332                 return true;
1333             }
1334         } catch (Throwable rex) {
1335             ex = rex;
1336         }
1337         deregisterWorker(wt, ex);
1338         return false;
1339     }
1340 
1341     /**
1342      * Tries to add one worker, incrementing ctl counts before doing
1343      * so, relying on createWorker to back out on failure.
1344      *
1345      * @param c incoming ctl value, with total count negative and no
1346      * idle workers.  On CAS failure, c is refreshed and retried if
1347      * this holds (otherwise, a new worker is not needed).
1348      */
1349     private void tryAddWorker(long c) {
1350         do {
1351             long nc = ((RC_MASK & (c + RC_UNIT)) |
1352                        (TC_MASK & (c + TC_UNIT)));
1353             if (ctl == c && CTL.compareAndSet(this, c, nc)) {
1354                 createWorker();
1355                 break;
1356             }
1357         } while (((c = ctl) & ADD_WORKER) != 0L && (int)c == 0);
1358     }
1359 
1360     /**
1361      * Callback from ForkJoinWorkerThread constructor to establish and
1362      * record its WorkQueue.
1363      *
1364      * @param wt the worker thread
1365      * @return the worker's queue
1366      */
1367     final WorkQueue registerWorker(ForkJoinWorkerThread wt) {
1368         UncaughtExceptionHandler handler;
1369         wt.setDaemon(true);                             // configure thread
1370         if ((handler = ueh) != null)
1371             wt.setUncaughtExceptionHandler(handler);
1372         int tid = 0;                                    // for thread name
1373         int idbits = mode & FIFO;
1374         String prefix = workerNamePrefix;
1375         WorkQueue w = new WorkQueue(this, wt);
1376         if (prefix != null) {
1377             synchronized (prefix) {
1378                 WorkQueue[] ws = workQueues; int n;
1379                 int s = indexSeed += SEED_INCREMENT;
1380                 idbits |= (s & ~(SMASK | FIFO | DORMANT));
1381                 if (ws != null && (n = ws.length) > 1) {
1382                     int m = n - 1;
1383                     tid = m & ((s << 1) | 1);           // odd-numbered indices
1384                     for (int probes = n >>> 1;;) {      // find empty slot
1385                         WorkQueue q;
1386                         if ((q = ws[tid]) == null || q.phase == QUIET)
1387                             break;
1388                         else if (--probes == 0) {
1389                             tid = n | 1;                // resize below
1390                             break;
1391                         }
1392                         else
1393                             tid = (tid + 2) & m;
1394                     }
1395                     w.phase = w.id = tid | idbits;      // now publishable
1396 
1397                     if (tid < n)
1398                         ws[tid] = w;
1399                     else {                              // expand array
1400                         int an = n << 1;
1401                         WorkQueue[] as = new WorkQueue[an];
1402                         as[tid] = w;
1403                         int am = an - 1;
1404                         for (int j = 0; j < n; ++j) {
1405                             WorkQueue v;                // copy external queue
1406                             if ((v = ws[j]) != null)    // position may change
1407                                 as[v.id & am & SQMASK] = v;
1408                             if (++j >= n)
1409                                 break;
1410                             as[j] = ws[j];              // copy worker
1411                         }
1412                         workQueues = as;
1413                     }
1414                 }
1415             }
1416             wt.setName(prefix.concat(Integer.toString(tid)));
1417         }
1418         return w;
1419     }
1420 
1421     /**
1422      * Final callback from terminating worker, as well as upon failure
1423      * to construct or start a worker.  Removes record of worker from
1424      * array, and adjusts counts. If pool is shutting down, tries to
1425      * complete termination.
1426      *
1427      * @param wt the worker thread, or null if construction failed
1428      * @param ex the exception causing failure, or null if none
1429      */
1430     final void deregisterWorker(ForkJoinWorkerThread wt, Throwable ex) {
1431         WorkQueue w = null;
1432         int phase = 0;
1433         if (wt != null && (w = wt.workQueue) != null) {
1434             Object lock = workerNamePrefix;
1435             int wid = w.id;
1436             long ns = (long)w.nsteals & 0xffffffffL;
1437             if (lock != null) {
1438                 synchronized (lock) {
1439                     WorkQueue[] ws; int n, i;         // remove index from array
1440                     if ((ws = workQueues) != null && (n = ws.length) > 0 &&
1441                         ws[i = wid & (n - 1)] == w)
1442                         ws[i] = null;
1443                     stealCount += ns;
1444                 }
1445             }
1446             phase = w.phase;
1447         }
1448         if (phase != QUIET) {                         // else pre-adjusted
1449             long c;                                   // decrement counts
1450             do {} while (!CTL.weakCompareAndSet
1451                          (this, c = ctl, ((RC_MASK & (c - RC_UNIT)) |
1452                                           (TC_MASK & (c - TC_UNIT)) |
1453                                           (SP_MASK & c))));
1454         }
1455         if (w != null)
1456             w.cancelAll();                            // cancel remaining tasks
1457 
1458         if (!tryTerminate(false, false) &&            // possibly replace worker
1459             w != null && w.array != null)             // avoid repeated failures
1460             signalWork(null);
1461 
1462         if (ex == null)                               // help clean on way out
1463             ForkJoinTask.helpExpungeStaleExceptions();
1464         else                                          // rethrow
1465             ForkJoinTask.rethrow(ex);
1466     }
1467 
1468     /**
1469      * Tries to create or release a worker if too few are running.
1470      * @param q if non-null recheck if empty on CAS failure
1471      */
1472     final void signalWork(WorkQueue q) {
1473         for (;;) {
1474             long c; int sp; WorkQueue[] ws; int i; WorkQueue v;
1475             if ((c = ctl) >= 0L)                      // enough workers
1476                 break;
1477             else if ((sp = (int)c) == 0) {            // no idle workers
1478                 if ((c & ADD_WORKER) != 0L)           // too few workers
1479                     tryAddWorker(c);
1480                 break;
1481             }
1482             else if ((ws = workQueues) == null)
1483                 break;                                // unstarted/terminated
1484             else if (ws.length <= (i = sp & SMASK))
1485                 break;                                // terminated
1486             else if ((v = ws[i]) == null)
1487                 break;                                // terminating
1488             else {
1489                 int np = sp & ~UNSIGNALLED;
1490                 int vp = v.phase;
1491                 long nc = (v.stackPred & SP_MASK) | (UC_MASK & (c + RC_UNIT));
1492                 Thread vt = v.owner;
1493                 if (sp == vp && CTL.compareAndSet(this, c, nc)) {
1494                     v.phase = np;
1495                     if (vt != null && v.source < 0)
1496                         LockSupport.unpark(vt);
1497                     break;
1498                 }
1499                 else if (q != null && q.isEmpty())     // no need to retry
1500                     break;
1501             }
1502         }
1503     }
1504 
1505     /**
1506      * Tries to decrement counts (sometimes implicitly) and possibly
1507      * arrange for a compensating worker in preparation for blocking:
1508      * If not all core workers yet exist, creates one, else if any are
1509      * unreleased (possibly including caller) releases one, else if
1510      * fewer than the minimum allowed number of workers running,
1511      * checks to see that they are all active, and if so creates an
1512      * extra worker unless over maximum limit and policy is to
1513      * saturate.  Most of these steps can fail due to interference, in
1514      * which case 0 is returned so caller will retry. A negative
1515      * return value indicates that the caller doesn't need to
1516      * re-adjust counts when later unblocked.
1517      *
1518      * @return 1: block then adjust, -1: block without adjust, 0 : retry
1519      */
1520     private int tryCompensate(WorkQueue w) {
1521         int t, n, sp;
1522         long c = ctl;
1523         WorkQueue[] ws = workQueues;
1524         if ((t = (short)(c >>> TC_SHIFT)) >= 0) {
1525             if (ws == null || (n = ws.length) <= 0 || w == null)
1526                 return 0;                        // disabled
1527             else if ((sp = (int)c) != 0) {       // replace or release
1528                 WorkQueue v = ws[sp & (n - 1)];
1529                 int wp = w.phase;
1530                 long uc = UC_MASK & ((wp < 0) ? c + RC_UNIT : c);
1531                 int np = sp & ~UNSIGNALLED;
1532                 if (v != null) {
1533                     int vp = v.phase;
1534                     Thread vt = v.owner;
1535                     long nc = ((long)v.stackPred & SP_MASK) | uc;
1536                     if (vp == sp && CTL.compareAndSet(this, c, nc)) {
1537                         v.phase = np;
1538                         if (vt != null && v.source < 0)
1539                             LockSupport.unpark(vt);
1540                         return (wp < 0) ? -1 : 1;
1541                     }
1542                 }
1543                 return 0;
1544             }
1545             else if ((int)(c >> RC_SHIFT) -      // reduce parallelism
1546                      (short)(bounds & SMASK) > 0) {
1547                 long nc = ((RC_MASK & (c - RC_UNIT)) | (~RC_MASK & c));
1548                 return CTL.compareAndSet(this, c, nc) ? 1 : 0;
1549             }
1550             else {                               // validate
1551                 int md = mode, pc = md & SMASK, tc = pc + t, bc = 0;
1552                 boolean unstable = false;
1553                 for (int i = 1; i < n; i += 2) {
1554                     WorkQueue q; Thread wt; Thread.State ts;
1555                     if ((q = ws[i]) != null) {
1556                         if (q.source == 0) {
1557                             unstable = true;
1558                             break;
1559                         }
1560                         else {
1561                             --tc;
1562                             if ((wt = q.owner) != null &&
1563                                 ((ts = wt.getState()) == Thread.State.BLOCKED ||
1564                                  ts == Thread.State.WAITING))
1565                                 ++bc;            // worker is blocking
1566                         }
1567                     }
1568                 }
1569                 if (unstable || tc != 0 || ctl != c)
1570                     return 0;                    // inconsistent
1571                 else if (t + pc >= MAX_CAP || t >= (bounds >>> SWIDTH)) {
1572                     Predicate<? super ForkJoinPool> sat;
1573                     if ((sat = saturate) != null && sat.test(this))
1574                         return -1;
1575                     else if (bc < pc) {          // lagging
1576                         Thread.yield();          // for retry spins
1577                         return 0;
1578                     }
1579                     else
1580                         throw new RejectedExecutionException(
1581                             "Thread limit exceeded replacing blocked worker");
1582                 }
1583             }
1584         }
1585 
1586         long nc = ((c + TC_UNIT) & TC_MASK) | (c & ~TC_MASK); // expand pool
1587         return CTL.compareAndSet(this, c, nc) && createWorker() ? 1 : 0;
1588     }
1589 
1590     /**
1591      * Top-level runloop for workers, called by ForkJoinWorkerThread.run.
1592      * See above for explanation.
1593      */
1594     final void runWorker(WorkQueue w) {
1595         int r = (w.id ^ ThreadLocalRandom.nextSecondarySeed()) | FIFO; // rng
1596         w.array = new ForkJoinTask<?>[INITIAL_QUEUE_CAPACITY]; // initialize
1597         for (;;) {
1598             int phase;
1599             if (scan(w, r)) {                     // scan until apparently empty
1600                 r ^= r << 13; r ^= r >>> 17; r ^= r << 5; // move (xorshift)
1601             }
1602             else if ((phase = w.phase) >= 0) {    // enqueue, then rescan
1603                 long np = (w.phase = (phase + SS_SEQ) | UNSIGNALLED) & SP_MASK;
1604                 long c, nc;
1605                 do {
1606                     w.stackPred = (int)(c = ctl);
1607                     nc = ((c - RC_UNIT) & UC_MASK) | np;
1608                 } while (!CTL.weakCompareAndSet(this, c, nc));
1609             }
1610             else {                                // already queued
1611                 int pred = w.stackPred;
1612                 Thread.interrupted();             // clear before park
1613                 w.source = DORMANT;               // enable signal
1614                 long c = ctl;
1615                 int md = mode, rc = (md & SMASK) + (int)(c >> RC_SHIFT);
1616                 if (md < 0)                       // terminating
1617                     break;
1618                 else if (rc <= 0 && (md & SHUTDOWN) != 0 &&
1619                          tryTerminate(false, false))
1620                     break;                        // quiescent shutdown
1621                 else if (w.phase < 0) {
1622                     if (rc <= 0 && pred != 0 && phase == (int)c) {
1623                         long nc = (UC_MASK & (c - TC_UNIT)) | (SP_MASK & pred);
1624                         long d = keepAlive + System.currentTimeMillis();
1625                         LockSupport.parkUntil(this, d);
1626                         if (ctl == c &&           // drop on timeout if all idle
1627                             d - System.currentTimeMillis() <= TIMEOUT_SLOP &&
1628                             CTL.compareAndSet(this, c, nc)) {
1629                             w.phase = QUIET;
1630                             break;
1631                         }
1632                     }
1633                     else {
1634                         LockSupport.park(this);
1635                         if (w.phase < 0)          // one spurious wakeup check
1636                             LockSupport.park(this);
1637                     }
1638                 }
1639                 w.source = 0;                     // disable signal
1640             }
1641         }
1642     }
1643 
1644     /**
1645      * Scans for and if found executes one or more top-level tasks from a queue.
1646      *
1647      * @return true if found an apparently non-empty queue, and
1648      * possibly ran task(s).
1649      */
1650     private boolean scan(WorkQueue w, int r) {
1651         WorkQueue[] ws; int n;
1652         if ((ws = workQueues) != null && (n = ws.length) > 0 && w != null) {
1653             for (int m = n - 1, j = r & m;;) {
1654                 WorkQueue q; int b;
1655                 if ((q = ws[j]) != null && q.top != (b = q.base)) {
1656                     int qid = q.id;
1657                     ForkJoinTask<?>[] a; int cap, k; ForkJoinTask<?> t;
1658                     if ((a = q.array) != null && (cap = a.length) > 0) {
1659                         t = (ForkJoinTask<?>)QA.getAcquire(a, k = (cap - 1) & b);
1660                         if (q.base == b++ && t != null &&
1661                             QA.compareAndSet(a, k, t, null)) {
1662                             q.base = b;
1663                             w.source = qid;
1664                             if (a[(cap - 1) & b] != null)
1665                                 signalWork(q);    // help signal if more tasks
1666                             w.topLevelExec(t, q,  // random fairness bound
1667                                            (r | (1 << TOP_BOUND_SHIFT)) & SMASK);
1668                         }
1669                     }
1670                     return true;
1671                 }
1672                 else if (--n > 0)
1673                     j = (j + 1) & m;
1674                 else
1675                     break;
1676             }
1677         }
1678         return false;
1679     }
1680 
1681     /**
1682      * Helps and/or blocks until the given task is done or timeout.
1683      * First tries locally helping, then scans other queues for a task
1684      * produced by one of w's stealers; compensating and blocking if
1685      * none are found (rescanning if tryCompensate fails).
1686      *
1687      * @param w caller
1688      * @param task the task
1689      * @param deadline for timed waits, if nonzero
1690      * @return task status on exit
1691      */
1692     final int awaitJoin(WorkQueue w, ForkJoinTask<?> task, long deadline) {
1693         int s = 0;
1694         int seed = ThreadLocalRandom.nextSecondarySeed();
1695         if (w != null && task != null &&
1696             (!(task instanceof CountedCompleter) ||
1697              (s = w.helpCC((CountedCompleter<?>)task, 0, false)) >= 0)) {
1698             w.tryRemoveAndExec(task);
1699             int src = w.source, id = w.id;
1700             int r = (seed >>> 16) | 1, step = (seed & ~1) | 2;
1701             s = task.status;
1702             while (s >= 0) {
1703                 WorkQueue[] ws;
1704                 int n = (ws = workQueues) == null ? 0 : ws.length, m = n - 1;
1705                 while (n > 0) {
1706                     WorkQueue q; int b;
1707                     if ((q = ws[r & m]) != null && q.source == id &&
1708                         q.top != (b = q.base)) {
1709                         ForkJoinTask<?>[] a; int cap, k;
1710                         int qid = q.id;
1711                         if ((a = q.array) != null && (cap = a.length) > 0) {
1712                             ForkJoinTask<?> t = (ForkJoinTask<?>)
1713                                 QA.getAcquire(a, k = (cap - 1) & b);
1714                             if (q.source == id && q.base == b++ &&
1715                                 t != null && QA.compareAndSet(a, k, t, null)) {
1716                                 q.base = b;
1717                                 w.source = qid;
1718                                 t.doExec();
1719                                 w.source = src;
1720                             }
1721                         }
1722                         break;
1723                     }
1724                     else {
1725                         r += step;
1726                         --n;
1727                     }
1728                 }
1729                 if ((s = task.status) < 0)
1730                     break;
1731                 else if (n == 0) { // empty scan
1732                     long ms, ns; int block;
1733                     if (deadline == 0L)
1734                         ms = 0L;                       // untimed
1735                     else if ((ns = deadline - System.nanoTime()) <= 0L)
1736                         break;                         // timeout
1737                     else if ((ms = TimeUnit.NANOSECONDS.toMillis(ns)) <= 0L)
1738                         ms = 1L;                       // avoid 0 for timed wait
1739                     if ((block = tryCompensate(w)) != 0) {
1740                         task.internalWait(ms);
1741                         CTL.getAndAdd(this, (block > 0) ? RC_UNIT : 0L);
1742                     }
1743                     s = task.status;
1744                 }
1745             }
1746         }
1747         return s;
1748     }
1749 
1750     /**
1751      * Runs tasks until {@code isQuiescent()}. Rather than blocking
1752      * when tasks cannot be found, rescans until all others cannot
1753      * find tasks either.
1754      */
1755     final void helpQuiescePool(WorkQueue w) {
1756         int prevSrc = w.source;
1757         int seed = ThreadLocalRandom.nextSecondarySeed();
1758         int r = seed >>> 16, step = r | 1;
1759         for (int source = prevSrc, released = -1;;) { // -1 until known
1760             ForkJoinTask<?> localTask; WorkQueue[] ws;
1761             while ((localTask = w.nextLocalTask()) != null)
1762                 localTask.doExec();
1763             if (w.phase >= 0 && released == -1)
1764                 released = 1;
1765             boolean quiet = true, empty = true;
1766             int n = (ws = workQueues) == null ? 0 : ws.length;
1767             for (int m = n - 1; n > 0; r += step, --n) {
1768                 WorkQueue q; int b;
1769                 if ((q = ws[r & m]) != null) {
1770                     int qs = q.source;
1771                     if (q.top != (b = q.base)) {
1772                         quiet = empty = false;
1773                         ForkJoinTask<?>[] a; int cap, k;
1774                         int qid = q.id;
1775                         if ((a = q.array) != null && (cap = a.length) > 0) {
1776                             if (released == 0) {    // increment
1777                                 released = 1;
1778                                 CTL.getAndAdd(this, RC_UNIT);
1779                             }
1780                             ForkJoinTask<?> t = (ForkJoinTask<?>)
1781                                 QA.getAcquire(a, k = (cap - 1) & b);
1782                             if (q.base == b++ && t != null &&
1783                                 QA.compareAndSet(a, k, t, null)) {
1784                                 q.base = b;
1785                                 w.source = qid;
1786                                 t.doExec();
1787                                 w.source = source = prevSrc;
1788                             }
1789                         }
1790                         break;
1791                     }
1792                     else if ((qs & QUIET) == 0)
1793                         quiet = false;
1794                 }
1795             }
1796             if (quiet) {
1797                 if (released == 0)
1798                     CTL.getAndAdd(this, RC_UNIT);
1799                 w.source = prevSrc;
1800                 break;
1801             }
1802             else if (empty) {
1803                 if (source != QUIET)
1804                     w.source = source = QUIET;
1805                 if (released == 1) {                 // decrement
1806                     released = 0;
1807                     CTL.getAndAdd(this, RC_MASK & -RC_UNIT);
1808                 }
1809             }
1810         }
1811     }
1812 
1813     /**
1814      * Scans for and returns a polled task, if available.
1815      * Used only for untracked polls.
1816      *
1817      * @param submissionsOnly if true, only scan submission queues
1818      */
1819     private ForkJoinTask<?> pollScan(boolean submissionsOnly) {
1820         WorkQueue[] ws; int n;
1821         rescan: while ((mode & STOP) == 0 && (ws = workQueues) != null &&
1822                       (n = ws.length) > 0) {
1823             int m = n - 1;
1824             int r = ThreadLocalRandom.nextSecondarySeed();
1825             int h = r >>> 16;
1826             int origin, step;
1827             if (submissionsOnly) {
1828                 origin = (r & ~1) & m;         // even indices and steps
1829                 step = (h & ~1) | 2;
1830             }
1831             else {
1832                 origin = r & m;
1833                 step = h | 1;
1834             }
1835             boolean nonempty = false;
1836             for (int i = origin, oldSum = 0, checkSum = 0;;) {
1837                 WorkQueue q;
1838                 if ((q = ws[i]) != null) {
1839                     int b; ForkJoinTask<?> t;
1840                     if (q.top - (b = q.base) > 0) {
1841                         nonempty = true;
1842                         if ((t = q.poll()) != null)
1843                             return t;
1844                     }
1845                     else
1846                         checkSum += b + q.id;
1847                 }
1848                 if ((i = (i + step) & m) == origin) {
1849                     if (!nonempty && oldSum == (oldSum = checkSum))
1850                         break rescan;
1851                     checkSum = 0;
1852                     nonempty = false;
1853                 }
1854             }
1855         }
1856         return null;
1857     }
1858 
1859     /**
1860      * Gets and removes a local or stolen task for the given worker.
1861      *
1862      * @return a task, if available
1863      */
1864     final ForkJoinTask<?> nextTaskFor(WorkQueue w) {
1865         ForkJoinTask<?> t;
1866         if (w == null || (t = w.nextLocalTask()) == null)
1867             t = pollScan(false);
1868         return t;
1869     }
1870 
1871     // External operations
1872 
1873     /**
1874      * Adds the given task to a submission queue at submitter's
1875      * current queue, creating one if null or contended.
1876      *
1877      * @param task the task. Caller must ensure non-null.
1878      */
1879     final void externalPush(ForkJoinTask<?> task) {
1880         int r;                                // initialize caller's probe
1881         if ((r = ThreadLocalRandom.getProbe()) == 0) {
1882             ThreadLocalRandom.localInit();
1883             r = ThreadLocalRandom.getProbe();
1884         }
1885         for (;;) {
1886             WorkQueue q;
1887             int md = mode, n;
1888             WorkQueue[] ws = workQueues;
1889             if ((md & SHUTDOWN) != 0 || ws == null || (n = ws.length) <= 0)
1890                 throw new RejectedExecutionException();
1891             else if ((q = ws[(n - 1) & r & SQMASK]) == null) { // add queue
1892                 int qid = (r | QUIET) & ~(FIFO | OWNED);
1893                 Object lock = workerNamePrefix;
1894                 ForkJoinTask<?>[] qa =
1895                     new ForkJoinTask<?>[INITIAL_QUEUE_CAPACITY];
1896                 q = new WorkQueue(this, null);
1897                 q.array = qa;
1898                 q.id = qid;
1899                 q.source = QUIET;
1900                 if (lock != null) {     // unless disabled, lock pool to install
1901                     synchronized (lock) {
1902                         WorkQueue[] vs; int i, vn;
1903                         if ((vs = workQueues) != null && (vn = vs.length) > 0 &&
1904                             vs[i = qid & (vn - 1) & SQMASK] == null)
1905                             vs[i] = q;  // else another thread already installed
1906                     }
1907                 }
1908             }
1909             else if (!q.tryLockPhase()) // move if busy
1910                 r = ThreadLocalRandom.advanceProbe(r);
1911             else {
1912                 if (q.lockedPush(task))
1913                     signalWork(null);
1914                 return;
1915             }
1916         }
1917     }
1918 
1919     /**
1920      * Pushes a possibly-external submission.
1921      */
1922     private <T> ForkJoinTask<T> externalSubmit(ForkJoinTask<T> task) {
1923         Thread t; ForkJoinWorkerThread w; WorkQueue q;
1924         if (task == null)
1925             throw new NullPointerException();
1926         if (((t = Strands.currentCarrierThread()) instanceof ForkJoinWorkerThread) &&
1927             (w = (ForkJoinWorkerThread)t).pool == this &&
1928             (q = w.workQueue) != null)
1929             q.push(task);
1930         else
1931             externalPush(task);
1932         return task;
1933     }
1934 
1935     /**
1936      * Returns common pool queue for an external thread.
1937      */
1938     static WorkQueue commonSubmitterQueue() {
1939         ForkJoinPool p = common;
1940         int r = ThreadLocalRandom.getProbe();
1941         WorkQueue[] ws; int n;
1942         return (p != null && (ws = p.workQueues) != null &&
1943                 (n = ws.length) > 0) ?
1944             ws[(n - 1) & r & SQMASK] : null;
1945     }
1946 
1947     /**
1948      * Performs tryUnpush for an external submitter.
1949      */
1950     final boolean tryExternalUnpush(ForkJoinTask<?> task) {
1951         int r = ThreadLocalRandom.getProbe();
1952         WorkQueue[] ws; WorkQueue w; int n;
1953         return ((ws = workQueues) != null &&
1954                 (n = ws.length) > 0 &&
1955                 (w = ws[(n - 1) & r & SQMASK]) != null &&
1956                 w.tryLockedUnpush(task));
1957     }
1958 
1959     /**
1960      * Performs helpComplete for an external submitter.
1961      */
1962     final int externalHelpComplete(CountedCompleter<?> task, int maxTasks) {
1963         int r = ThreadLocalRandom.getProbe();
1964         WorkQueue[] ws; WorkQueue w; int n;
1965         return ((ws = workQueues) != null && (n = ws.length) > 0 &&
1966                 (w = ws[(n - 1) & r & SQMASK]) != null) ?
1967             w.helpCC(task, maxTasks, true) : 0;
1968     }
1969 
1970     /**
1971      * Tries to steal and run tasks within the target's computation.
1972      * The maxTasks argument supports external usages; internal calls
1973      * use zero, allowing unbounded steps (external calls trap
1974      * non-positive values).
1975      *
1976      * @param w caller
1977      * @param maxTasks if non-zero, the maximum number of other tasks to run
1978      * @return task status on exit
1979      */
1980     final int helpComplete(WorkQueue w, CountedCompleter<?> task,
1981                            int maxTasks) {
1982         return (w == null) ? 0 : w.helpCC(task, maxTasks, false);
1983     }
1984 
1985     /**
1986      * Returns a cheap heuristic guide for task partitioning when
1987      * programmers, frameworks, tools, or languages have little or no
1988      * idea about task granularity.  In essence, by offering this
1989      * method, we ask users only about tradeoffs in overhead vs
1990      * expected throughput and its variance, rather than how finely to
1991      * partition tasks.
1992      *
1993      * In a steady state strict (tree-structured) computation, each
1994      * thread makes available for stealing enough tasks for other
1995      * threads to remain active. Inductively, if all threads play by
1996      * the same rules, each thread should make available only a
1997      * constant number of tasks.
1998      *
1999      * The minimum useful constant is just 1. But using a value of 1
2000      * would require immediate replenishment upon each steal to
2001      * maintain enough tasks, which is infeasible.  Further,
2002      * partitionings/granularities of offered tasks should minimize
2003      * steal rates, which in general means that threads nearer the top
2004      * of computation tree should generate more than those nearer the
2005      * bottom. In perfect steady state, each thread is at
2006      * approximately the same level of computation tree. However,
2007      * producing extra tasks amortizes the uncertainty of progress and
2008      * diffusion assumptions.
2009      *
2010      * So, users will want to use values larger (but not much larger)
2011      * than 1 to both smooth over transient shortages and hedge
2012      * against uneven progress; as traded off against the cost of
2013      * extra task overhead. We leave the user to pick a threshold
2014      * value to compare with the results of this call to guide
2015      * decisions, but recommend values such as 3.
2016      *
2017      * When all threads are active, it is on average OK to estimate
2018      * surplus strictly locally. In steady-state, if one thread is
2019      * maintaining say 2 surplus tasks, then so are others. So we can
2020      * just use estimated queue length.  However, this strategy alone
2021      * leads to serious mis-estimates in some non-steady-state
2022      * conditions (ramp-up, ramp-down, other stalls). We can detect
2023      * many of these by further considering the number of "idle"
2024      * threads, that are known to have zero queued tasks, so
2025      * compensate by a factor of (#idle/#active) threads.
2026      */
2027     static int getSurplusQueuedTaskCount() {
2028         Thread t; ForkJoinWorkerThread wt; ForkJoinPool pool; WorkQueue q;
2029         if (((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) &&
2030             (pool = (wt = (ForkJoinWorkerThread)t).pool) != null &&
2031             (q = wt.workQueue) != null) {
2032             int p = pool.mode & SMASK;
2033             int a = p + (int)(pool.ctl >> RC_SHIFT);
2034             int n = q.top - q.base;
2035             return n - (a > (p >>>= 1) ? 0 :
2036                         a > (p >>>= 1) ? 1 :
2037                         a > (p >>>= 1) ? 2 :
2038                         a > (p >>>= 1) ? 4 :
2039                         8);
2040         }
2041         return 0;
2042     }
2043 
2044     // Termination
2045 
2046     /**
2047      * Possibly initiates and/or completes termination.
2048      *
2049      * @param now if true, unconditionally terminate, else only
2050      * if no work and no active workers
2051      * @param enable if true, terminate when next possible
2052      * @return true if terminating or terminated
2053      */
2054     private boolean tryTerminate(boolean now, boolean enable) {
2055         int md; // 3 phases: try to set SHUTDOWN, then STOP, then TERMINATED
2056 
2057         while (((md = mode) & SHUTDOWN) == 0) {
2058             if (!enable || this == common)        // cannot shutdown
2059                 return false;
2060             else
2061                 MODE.compareAndSet(this, md, md | SHUTDOWN);
2062         }
2063 
2064         while (((md = mode) & STOP) == 0) {       // try to initiate termination
2065             if (!now) {                           // check if quiescent & empty
2066                 for (long oldSum = 0L;;) {        // repeat until stable
2067                     boolean running = false;
2068                     long checkSum = ctl;
2069                     WorkQueue[] ws = workQueues;
2070                     if ((md & SMASK) + (int)(checkSum >> RC_SHIFT) > 0)
2071                         running = true;
2072                     else if (ws != null) {
2073                         WorkQueue w;
2074                         for (int i = 0; i < ws.length; ++i) {
2075                             if ((w = ws[i]) != null) {
2076                                 int s = w.source, p = w.phase;
2077                                 int d = w.id, b = w.base;
2078                                 if (b != w.top ||
2079                                     ((d & 1) == 1 && (s >= 0 || p >= 0))) {
2080                                     running = true;
2081                                     break;     // working, scanning, or have work
2082                                 }
2083                                 checkSum += (((long)s << 48) + ((long)p << 32) +
2084                                              ((long)b << 16) + (long)d);
2085                             }
2086                         }
2087                     }
2088                     if (((md = mode) & STOP) != 0)
2089                         break;                 // already triggered
2090                     else if (running)
2091                         return false;
2092                     else if (workQueues == ws && oldSum == (oldSum = checkSum))
2093                         break;
2094                 }
2095             }
2096             if ((md & STOP) == 0)
2097                 MODE.compareAndSet(this, md, md | STOP);
2098         }
2099 
2100         while (((md = mode) & TERMINATED) == 0) { // help terminate others
2101             for (long oldSum = 0L;;) {            // repeat until stable
2102                 WorkQueue[] ws; WorkQueue w;
2103                 long checkSum = ctl;
2104                 if ((ws = workQueues) != null) {
2105                     for (int i = 0; i < ws.length; ++i) {
2106                         if ((w = ws[i]) != null) {
2107                             ForkJoinWorkerThread wt = w.owner;
2108                             w.cancelAll();        // clear queues
2109                             if (wt != null) {
2110                                 try {             // unblock join or park
2111                                     wt.interrupt();
2112                                 } catch (Throwable ignore) {
2113                                 }
2114                             }
2115                             checkSum += ((long)w.phase << 32) + w.base;
2116                         }
2117                     }
2118                 }
2119                 if (((md = mode) & TERMINATED) != 0 ||
2120                     (workQueues == ws && oldSum == (oldSum = checkSum)))
2121                     break;
2122             }
2123             if ((md & TERMINATED) != 0)
2124                 break;
2125             else if ((md & SMASK) + (short)(ctl >>> TC_SHIFT) > 0)
2126                 break;
2127             else if (MODE.compareAndSet(this, md, md | TERMINATED)) {
2128                 synchronized (this) {
2129                     notifyAll();                  // for awaitTermination
2130                 }
2131                 break;
2132             }
2133         }
2134         return true;
2135     }
2136 
2137     // Exported methods
2138 
2139     // Constructors
2140 
2141     /**
2142      * Creates a {@code ForkJoinPool} with parallelism equal to {@link
2143      * java.lang.Runtime#availableProcessors}, using defaults for all
2144      * other parameters (see {@link #ForkJoinPool(int,
2145      * ForkJoinWorkerThreadFactory, UncaughtExceptionHandler, boolean,
2146      * int, int, int, Predicate, long, TimeUnit)}).
2147      *
2148      * @throws SecurityException if a security manager exists and
2149      *         the caller is not permitted to modify threads
2150      *         because it does not hold {@link
2151      *         java.lang.RuntimePermission}{@code ("modifyThread")}
2152      */
2153     public ForkJoinPool() {
2154         this(Math.min(MAX_CAP, Runtime.getRuntime().availableProcessors()),
2155              defaultForkJoinWorkerThreadFactory, null, false,
2156              0, MAX_CAP, 1, null, DEFAULT_KEEPALIVE, TimeUnit.MILLISECONDS);
2157     }
2158 
2159     /**
2160      * Creates a {@code ForkJoinPool} with the indicated parallelism
2161      * level, using defaults for all other parameters (see {@link
2162      * #ForkJoinPool(int, ForkJoinWorkerThreadFactory,
2163      * UncaughtExceptionHandler, boolean, int, int, int, Predicate,
2164      * long, TimeUnit)}).
2165      *
2166      * @param parallelism the parallelism level
2167      * @throws IllegalArgumentException if parallelism less than or
2168      *         equal to zero, or greater than implementation limit
2169      * @throws SecurityException if a security manager exists and
2170      *         the caller is not permitted to modify threads
2171      *         because it does not hold {@link
2172      *         java.lang.RuntimePermission}{@code ("modifyThread")}
2173      */
2174     public ForkJoinPool(int parallelism) {
2175         this(parallelism, defaultForkJoinWorkerThreadFactory, null, false,
2176              0, MAX_CAP, 1, null, DEFAULT_KEEPALIVE, TimeUnit.MILLISECONDS);
2177     }
2178 
2179     /**
2180      * Creates a {@code ForkJoinPool} with the given parameters (using
2181      * defaults for others -- see {@link #ForkJoinPool(int,
2182      * ForkJoinWorkerThreadFactory, UncaughtExceptionHandler, boolean,
2183      * int, int, int, Predicate, long, TimeUnit)}).
2184      *
2185      * @param parallelism the parallelism level. For default value,
2186      * use {@link java.lang.Runtime#availableProcessors}.
2187      * @param factory the factory for creating new threads. For default value,
2188      * use {@link #defaultForkJoinWorkerThreadFactory}.
2189      * @param handler the handler for internal worker threads that
2190      * terminate due to unrecoverable errors encountered while executing
2191      * tasks. For default value, use {@code null}.
2192      * @param asyncMode if true,
2193      * establishes local first-in-first-out scheduling mode for forked
2194      * tasks that are never joined. This mode may be more appropriate
2195      * than default locally stack-based mode in applications in which
2196      * worker threads only process event-style asynchronous tasks.
2197      * For default value, use {@code false}.
2198      * @throws IllegalArgumentException if parallelism less than or
2199      *         equal to zero, or greater than implementation limit
2200      * @throws NullPointerException if the factory is null
2201      * @throws SecurityException if a security manager exists and
2202      *         the caller is not permitted to modify threads
2203      *         because it does not hold {@link
2204      *         java.lang.RuntimePermission}{@code ("modifyThread")}
2205      */
2206     public ForkJoinPool(int parallelism,
2207                         ForkJoinWorkerThreadFactory factory,
2208                         UncaughtExceptionHandler handler,
2209                         boolean asyncMode) {
2210         this(parallelism, factory, handler, asyncMode,
2211              0, MAX_CAP, 1, null, DEFAULT_KEEPALIVE, TimeUnit.MILLISECONDS);
2212     }
2213 
2214     /**
2215      * Creates a {@code ForkJoinPool} with the given parameters.
2216      *
2217      * @param parallelism the parallelism level. For default value,
2218      * use {@link java.lang.Runtime#availableProcessors}.
2219      *
2220      * @param factory the factory for creating new threads. For
2221      * default value, use {@link #defaultForkJoinWorkerThreadFactory}.
2222      *
2223      * @param handler the handler for internal worker threads that
2224      * terminate due to unrecoverable errors encountered while
2225      * executing tasks. For default value, use {@code null}.
2226      *
2227      * @param asyncMode if true, establishes local first-in-first-out
2228      * scheduling mode for forked tasks that are never joined. This
2229      * mode may be more appropriate than default locally stack-based
2230      * mode in applications in which worker threads only process
2231      * event-style asynchronous tasks.  For default value, use {@code
2232      * false}.
2233      *
2234      * @param corePoolSize the number of threads to keep in the pool
2235      * (unless timed out after an elapsed keep-alive). Normally (and
2236      * by default) this is the same value as the parallelism level,
2237      * but may be set to a larger value to reduce dynamic overhead if
2238      * tasks regularly block. Using a smaller value (for example
2239      * {@code 0}) has the same effect as the default.
2240      *
2241      * @param maximumPoolSize the maximum number of threads allowed.
2242      * When the maximum is reached, attempts to replace blocked
2243      * threads fail.  (However, because creation and termination of
2244      * different threads may overlap, and may be managed by the given
2245      * thread factory, this value may be transiently exceeded.)  To
2246      * arrange the same value as is used by default for the common
2247      * pool, use {@code 256} plus the {@code parallelism} level. (By
2248      * default, the common pool allows a maximum of 256 spare
2249      * threads.)  Using a value (for example {@code
2250      * Integer.MAX_VALUE}) larger than the implementation's total
2251      * thread limit has the same effect as using this limit (which is
2252      * the default).
2253      *
2254      * @param minimumRunnable the minimum allowed number of core
2255      * threads not blocked by a join or {@link ManagedBlocker}.  To
2256      * ensure progress, when too few unblocked threads exist and
2257      * unexecuted tasks may exist, new threads are constructed, up to
2258      * the given maximumPoolSize.  For the default value, use {@code
2259      * 1}, that ensures liveness.  A larger value might improve
2260      * throughput in the presence of blocked activities, but might
2261      * not, due to increased overhead.  A value of zero may be
2262      * acceptable when submitted tasks cannot have dependencies
2263      * requiring additional threads.
2264      *
2265      * @param saturate if non-null, a predicate invoked upon attempts
2266      * to create more than the maximum total allowed threads.  By
2267      * default, when a thread is about to block on a join or {@link
2268      * ManagedBlocker}, but cannot be replaced because the
2269      * maximumPoolSize would be exceeded, a {@link
2270      * RejectedExecutionException} is thrown.  But if this predicate
2271      * returns {@code true}, then no exception is thrown, so the pool
2272      * continues to operate with fewer than the target number of
2273      * runnable threads, which might not ensure progress.
2274      *
2275      * @param keepAliveTime the elapsed time since last use before
2276      * a thread is terminated (and then later replaced if needed).
2277      * For the default value, use {@code 60, TimeUnit.SECONDS}.
2278      *
2279      * @param unit the time unit for the {@code keepAliveTime} argument
2280      *
2281      * @throws IllegalArgumentException if parallelism is less than or
2282      *         equal to zero, or is greater than implementation limit,
2283      *         or if maximumPoolSize is less than parallelism,
2284      *         of if the keepAliveTime is less than or equal to zero.
2285      * @throws NullPointerException if the factory is null
2286      * @throws SecurityException if a security manager exists and
2287      *         the caller is not permitted to modify threads
2288      *         because it does not hold {@link
2289      *         java.lang.RuntimePermission}{@code ("modifyThread")}
2290      * @since 9
2291      */
2292     public ForkJoinPool(int parallelism,
2293                         ForkJoinWorkerThreadFactory factory,
2294                         UncaughtExceptionHandler handler,
2295                         boolean asyncMode,
2296                         int corePoolSize,
2297                         int maximumPoolSize,
2298                         int minimumRunnable,
2299                         Predicate<? super ForkJoinPool> saturate,
2300                         long keepAliveTime,
2301                         TimeUnit unit) {
2302         // check, encode, pack parameters
2303         if (parallelism <= 0 || parallelism > MAX_CAP ||
2304             maximumPoolSize < parallelism || keepAliveTime <= 0L)
2305             throw new IllegalArgumentException();
2306         if (factory == null)
2307             throw new NullPointerException();
2308         long ms = Math.max(unit.toMillis(keepAliveTime), TIMEOUT_SLOP);
2309 
2310         int corep = Math.min(Math.max(corePoolSize, parallelism), MAX_CAP);
2311         long c = ((((long)(-corep)       << TC_SHIFT) & TC_MASK) |
2312                   (((long)(-parallelism) << RC_SHIFT) & RC_MASK));
2313         int m = parallelism | (asyncMode ? FIFO : 0);
2314         int maxSpares = Math.min(maximumPoolSize, MAX_CAP) - parallelism;
2315         int minAvail = Math.min(Math.max(minimumRunnable, 0), MAX_CAP);
2316         int b = ((minAvail - parallelism) & SMASK) | (maxSpares << SWIDTH);
2317         int n = (parallelism > 1) ? parallelism - 1 : 1; // at least 2 slots
2318         n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16;
2319         n = (n + 1) << 1; // power of two, including space for submission queues
2320 
2321         this.workerNamePrefix = "ForkJoinPool-" + nextPoolId() + "-worker-";
2322         this.workQueues = new WorkQueue[n];
2323         this.factory = factory;
2324         this.ueh = handler;
2325         this.saturate = saturate;
2326         this.keepAlive = ms;
2327         this.bounds = b;
2328         this.mode = m;
2329         this.ctl = c;
2330         checkPermission();
2331     }
2332 
2333     private static Object newInstanceFromSystemProperty(String property)
2334         throws ReflectiveOperationException {
2335         String className = System.getProperty(property);
2336         return (className == null)
2337             ? null
2338             : ClassLoader.getSystemClassLoader().loadClass(className)
2339             .getConstructor().newInstance();
2340     }
2341 
2342     /**
2343      * Constructor for common pool using parameters possibly
2344      * overridden by system properties
2345      */
2346     private ForkJoinPool(byte forCommonPoolOnly) {
2347         int parallelism = -1;
2348         ForkJoinWorkerThreadFactory fac = null;
2349         UncaughtExceptionHandler handler = null;
2350         try {  // ignore exceptions in accessing/parsing properties
2351             String pp = System.getProperty
2352                 ("java.util.concurrent.ForkJoinPool.common.parallelism");
2353             if (pp != null)
2354                 parallelism = Integer.parseInt(pp);
2355             fac = (ForkJoinWorkerThreadFactory) newInstanceFromSystemProperty(
2356                 "java.util.concurrent.ForkJoinPool.common.threadFactory");
2357             handler = (UncaughtExceptionHandler) newInstanceFromSystemProperty(
2358                 "java.util.concurrent.ForkJoinPool.common.exceptionHandler");
2359         } catch (Exception ignore) {
2360         }
2361 
2362         if (fac == null) {
2363             if (System.getSecurityManager() == null)
2364                 fac = defaultForkJoinWorkerThreadFactory;
2365             else // use security-managed default
2366                 fac = new InnocuousForkJoinWorkerThreadFactory();
2367         }
2368         if (parallelism < 0 && // default 1 less than #cores
2369             (parallelism = Runtime.getRuntime().availableProcessors() - 1) <= 0)
2370             parallelism = 1;
2371         if (parallelism > MAX_CAP)
2372             parallelism = MAX_CAP;
2373 
2374         long c = ((((long)(-parallelism) << TC_SHIFT) & TC_MASK) |
2375                   (((long)(-parallelism) << RC_SHIFT) & RC_MASK));
2376         int b = ((1 - parallelism) & SMASK) | (COMMON_MAX_SPARES << SWIDTH);
2377         int n = (parallelism > 1) ? parallelism - 1 : 1;
2378         n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16;
2379         n = (n + 1) << 1;
2380 
2381         this.workerNamePrefix = "ForkJoinPool.commonPool-worker-";
2382         this.workQueues = new WorkQueue[n];
2383         this.factory = fac;
2384         this.ueh = handler;
2385         this.saturate = null;
2386         this.keepAlive = DEFAULT_KEEPALIVE;
2387         this.bounds = b;
2388         this.mode = parallelism;
2389         this.ctl = c;
2390     }
2391 
2392     /**
2393      * Returns the common pool instance. This pool is statically
2394      * constructed; its run state is unaffected by attempts to {@link
2395      * #shutdown} or {@link #shutdownNow}. However this pool and any
2396      * ongoing processing are automatically terminated upon program
2397      * {@link System#exit}.  Any program that relies on asynchronous
2398      * task processing to complete before program termination should
2399      * invoke {@code commonPool().}{@link #awaitQuiescence awaitQuiescence},
2400      * before exit.
2401      *
2402      * @return the common pool instance
2403      * @since 1.8
2404      */
2405     public static ForkJoinPool commonPool() {
2406         // assert common != null : "static init error";
2407         return common;
2408     }
2409 
2410     // Execution methods
2411 
2412     /**
2413      * Performs the given task, returning its result upon completion.
2414      * If the computation encounters an unchecked Exception or Error,
2415      * it is rethrown as the outcome of this invocation.  Rethrown
2416      * exceptions behave in the same way as regular exceptions, but,
2417      * when possible, contain stack traces (as displayed for example
2418      * using {@code ex.printStackTrace()}) of both the current thread
2419      * as well as the thread actually encountering the exception;
2420      * minimally only the latter.
2421      *
2422      * @param task the task
2423      * @param <T> the type of the task's result
2424      * @return the task's result
2425      * @throws NullPointerException if the task is null
2426      * @throws RejectedExecutionException if the task cannot be
2427      *         scheduled for execution
2428      */
2429     public <T> T invoke(ForkJoinTask<T> task) {
2430         if (task == null)
2431             throw new NullPointerException();
2432         externalSubmit(task);
2433         return task.join();
2434     }
2435 
2436     /**
2437      * Arranges for (asynchronous) execution of the given task.
2438      *
2439      * @param task the task
2440      * @throws NullPointerException if the task is null
2441      * @throws RejectedExecutionException if the task cannot be
2442      *         scheduled for execution
2443      */
2444     public void execute(ForkJoinTask<?> task) {
2445         externalSubmit(task);
2446     }
2447 
2448     // AbstractExecutorService methods
2449 
2450     /**
2451      * @throws NullPointerException if the task is null
2452      * @throws RejectedExecutionException if the task cannot be
2453      *         scheduled for execution
2454      */
2455     public void execute(Runnable task) {
2456         if (task == null)
2457             throw new NullPointerException();
2458         ForkJoinTask<?> job;
2459         if (task instanceof ForkJoinTask<?>) // avoid re-wrap
2460             job = (ForkJoinTask<?>) task;
2461         else
2462             job = new ForkJoinTask.RunnableExecuteAction(task);
2463         externalSubmit(job);
2464     }
2465 
2466     /**
2467      * Submits a ForkJoinTask for execution.
2468      *
2469      * @param task the task to submit
2470      * @param <T> the type of the task's result
2471      * @return the task
2472      * @throws NullPointerException if the task is null
2473      * @throws RejectedExecutionException if the task cannot be
2474      *         scheduled for execution
2475      */
2476     public <T> ForkJoinTask<T> submit(ForkJoinTask<T> task) {
2477         return externalSubmit(task);
2478     }
2479 
2480     /**
2481      * @throws NullPointerException if the task is null
2482      * @throws RejectedExecutionException if the task cannot be
2483      *         scheduled for execution
2484      */
2485     public <T> ForkJoinTask<T> submit(Callable<T> task) {
2486         return externalSubmit(new ForkJoinTask.AdaptedCallable<T>(task));
2487     }
2488 
2489     /**
2490      * @throws NullPointerException if the task is null
2491      * @throws RejectedExecutionException if the task cannot be
2492      *         scheduled for execution
2493      */
2494     public <T> ForkJoinTask<T> submit(Runnable task, T result) {
2495         return externalSubmit(new ForkJoinTask.AdaptedRunnable<T>(task, result));
2496     }
2497 
2498     /**
2499      * @throws NullPointerException if the task is null
2500      * @throws RejectedExecutionException if the task cannot be
2501      *         scheduled for execution
2502      */
2503     @SuppressWarnings("unchecked")
2504     public ForkJoinTask<?> submit(Runnable task) {
2505         if (task == null)
2506             throw new NullPointerException();
2507         return externalSubmit((task instanceof ForkJoinTask<?>)
2508             ? (ForkJoinTask<Void>) task // avoid re-wrap
2509             : new ForkJoinTask.AdaptedRunnableAction(task));
2510     }
2511 
2512     /**
2513      * @throws NullPointerException       {@inheritDoc}
2514      * @throws RejectedExecutionException {@inheritDoc}
2515      */
2516     public <T> List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks) {
2517         // In previous versions of this class, this method constructed
2518         // a task to run ForkJoinTask.invokeAll, but now external
2519         // invocation of multiple tasks is at least as efficient.
2520         ArrayList<Future<T>> futures = new ArrayList<>(tasks.size());
2521 
2522         try {
2523             for (Callable<T> t : tasks) {
2524                 ForkJoinTask<T> f = new ForkJoinTask.AdaptedCallable<T>(t);
2525                 futures.add(f);
2526                 externalSubmit(f);
2527             }
2528             for (int i = 0, size = futures.size(); i < size; i++)
2529                 ((ForkJoinTask<?>)futures.get(i)).quietlyJoin();
2530             return futures;
2531         } catch (Throwable t) {
2532             for (int i = 0, size = futures.size(); i < size; i++)
2533                 futures.get(i).cancel(false);
2534             throw t;
2535         }
2536     }
2537 
2538     /**
2539      * Returns the factory used for constructing new workers.
2540      *
2541      * @return the factory used for constructing new workers
2542      */
2543     public ForkJoinWorkerThreadFactory getFactory() {
2544         return factory;
2545     }
2546 
2547     /**
2548      * Returns the handler for internal worker threads that terminate
2549      * due to unrecoverable errors encountered while executing tasks.
2550      *
2551      * @return the handler, or {@code null} if none
2552      */
2553     public UncaughtExceptionHandler getUncaughtExceptionHandler() {
2554         return ueh;
2555     }
2556 
2557     /**
2558      * Returns the targeted parallelism level of this pool.
2559      *
2560      * @return the targeted parallelism level of this pool
2561      */
2562     public int getParallelism() {
2563         int par = mode & SMASK;
2564         return (par > 0) ? par : 1;
2565     }
2566 
2567     /**
2568      * Returns the targeted parallelism level of the common pool.
2569      *
2570      * @return the targeted parallelism level of the common pool
2571      * @since 1.8
2572      */
2573     public static int getCommonPoolParallelism() {
2574         return COMMON_PARALLELISM;
2575     }
2576 
2577     /**
2578      * Returns the number of worker threads that have started but not
2579      * yet terminated.  The result returned by this method may differ
2580      * from {@link #getParallelism} when threads are created to
2581      * maintain parallelism when others are cooperatively blocked.
2582      *
2583      * @return the number of worker threads
2584      */
2585     public int getPoolSize() {
2586         return ((mode & SMASK) + (short)(ctl >>> TC_SHIFT));
2587     }
2588 
2589     /**
2590      * Returns {@code true} if this pool uses local first-in-first-out
2591      * scheduling mode for forked tasks that are never joined.
2592      *
2593      * @return {@code true} if this pool uses async mode
2594      */
2595     public boolean getAsyncMode() {
2596         return (mode & FIFO) != 0;
2597     }
2598 
2599     /**
2600      * Returns an estimate of the number of worker threads that are
2601      * not blocked waiting to join tasks or for other managed
2602      * synchronization. This method may overestimate the
2603      * number of running threads.
2604      *
2605      * @return the number of worker threads
2606      */
2607     public int getRunningThreadCount() {
2608         WorkQueue[] ws; WorkQueue w;
2609         VarHandle.acquireFence();
2610         int rc = 0;
2611         if ((ws = workQueues) != null) {
2612             for (int i = 1; i < ws.length; i += 2) {
2613                 if ((w = ws[i]) != null && w.isApparentlyUnblocked())
2614                     ++rc;
2615             }
2616         }
2617         return rc;
2618     }
2619 
2620     /**
2621      * Returns an estimate of the number of threads that are currently
2622      * stealing or executing tasks. This method may overestimate the
2623      * number of active threads.
2624      *
2625      * @return the number of active threads
2626      */
2627     public int getActiveThreadCount() {
2628         int r = (mode & SMASK) + (int)(ctl >> RC_SHIFT);
2629         return (r <= 0) ? 0 : r; // suppress momentarily negative values
2630     }
2631 
2632     /**
2633      * Returns {@code true} if all worker threads are currently idle.
2634      * An idle worker is one that cannot obtain a task to execute
2635      * because none are available to steal from other threads, and
2636      * there are no pending submissions to the pool. This method is
2637      * conservative; it might not return {@code true} immediately upon
2638      * idleness of all threads, but will eventually become true if
2639      * threads remain inactive.
2640      *
2641      * @return {@code true} if all threads are currently idle
2642      */
2643     public boolean isQuiescent() {
2644         for (;;) {
2645             long c = ctl;
2646             int md = mode, pc = md & SMASK;
2647             int tc = pc + (short)(c >>> TC_SHIFT);
2648             int rc = pc + (int)(c >> RC_SHIFT);
2649             if ((md & (STOP | TERMINATED)) != 0)
2650                 return true;
2651             else if (rc > 0)
2652                 return false;
2653             else {
2654                 WorkQueue[] ws; WorkQueue v;
2655                 if ((ws = workQueues) != null) {
2656                     for (int i = 1; i < ws.length; i += 2) {
2657                         if ((v = ws[i]) != null) {
2658                             if (v.source > 0)
2659                                 return false;
2660                             --tc;
2661                         }
2662                     }
2663                 }
2664                 if (tc == 0 && ctl == c)
2665                     return true;
2666             }
2667         }
2668     }
2669 
2670     /**
2671      * Returns an estimate of the total number of completed tasks that
2672      * were executed by a thread other than their submitter. The
2673      * reported value underestimates the actual total number of steals
2674      * when the pool is not quiescent. This value may be useful for
2675      * monitoring and tuning fork/join programs: in general, steal
2676      * counts should be high enough to keep threads busy, but low
2677      * enough to avoid overhead and contention across threads.
2678      *
2679      * @return the number of steals
2680      */
2681     public long getStealCount() {
2682         long count = stealCount;
2683         WorkQueue[] ws; WorkQueue w;
2684         if ((ws = workQueues) != null) {
2685             for (int i = 1; i < ws.length; i += 2) {
2686                 if ((w = ws[i]) != null)
2687                     count += (long)w.nsteals & 0xffffffffL;
2688             }
2689         }
2690         return count;
2691     }
2692 
2693     /**
2694      * Returns an estimate of the total number of tasks currently held
2695      * in queues by worker threads (but not including tasks submitted
2696      * to the pool that have not begun executing). This value is only
2697      * an approximation, obtained by iterating across all threads in
2698      * the pool. This method may be useful for tuning task
2699      * granularities.
2700      *
2701      * @return the number of queued tasks
2702      */
2703     public long getQueuedTaskCount() {
2704         WorkQueue[] ws; WorkQueue w;
2705         VarHandle.acquireFence();
2706         int count = 0;
2707         if ((ws = workQueues) != null) {
2708             for (int i = 1; i < ws.length; i += 2) {
2709                 if ((w = ws[i]) != null)
2710                     count += w.queueSize();
2711             }
2712         }
2713         return count;
2714     }
2715 
2716     /**
2717      * Returns an estimate of the number of tasks submitted to this
2718      * pool that have not yet begun executing.  This method may take
2719      * time proportional to the number of submissions.
2720      *
2721      * @return the number of queued submissions
2722      */
2723     public int getQueuedSubmissionCount() {
2724         WorkQueue[] ws; WorkQueue w;
2725         VarHandle.acquireFence();
2726         int count = 0;
2727         if ((ws = workQueues) != null) {
2728             for (int i = 0; i < ws.length; i += 2) {
2729                 if ((w = ws[i]) != null)
2730                     count += w.queueSize();
2731             }
2732         }
2733         return count;
2734     }
2735 
2736     /**
2737      * Returns {@code true} if there are any tasks submitted to this
2738      * pool that have not yet begun executing.
2739      *
2740      * @return {@code true} if there are any queued submissions
2741      */
2742     public boolean hasQueuedSubmissions() {
2743         WorkQueue[] ws; WorkQueue w;
2744         VarHandle.acquireFence();
2745         if ((ws = workQueues) != null) {
2746             for (int i = 0; i < ws.length; i += 2) {
2747                 if ((w = ws[i]) != null && !w.isEmpty())
2748                     return true;
2749             }
2750         }
2751         return false;
2752     }
2753 
2754     /**
2755      * Removes and returns the next unexecuted submission if one is
2756      * available.  This method may be useful in extensions to this
2757      * class that re-assign work in systems with multiple pools.
2758      *
2759      * @return the next submission, or {@code null} if none
2760      */
2761     protected ForkJoinTask<?> pollSubmission() {
2762         return pollScan(true);
2763     }
2764 
2765     /**
2766      * Removes all available unexecuted submitted and forked tasks
2767      * from scheduling queues and adds them to the given collection,
2768      * without altering their execution status. These may include
2769      * artificially generated or wrapped tasks. This method is
2770      * designed to be invoked only when the pool is known to be
2771      * quiescent. Invocations at other times may not remove all
2772      * tasks. A failure encountered while attempting to add elements
2773      * to collection {@code c} may result in elements being in
2774      * neither, either or both collections when the associated
2775      * exception is thrown.  The behavior of this operation is
2776      * undefined if the specified collection is modified while the
2777      * operation is in progress.
2778      *
2779      * @param c the collection to transfer elements into
2780      * @return the number of elements transferred
2781      */
2782     protected int drainTasksTo(Collection<? super ForkJoinTask<?>> c) {
2783         WorkQueue[] ws; WorkQueue w; ForkJoinTask<?> t;
2784         VarHandle.acquireFence();
2785         int count = 0;
2786         if ((ws = workQueues) != null) {
2787             for (int i = 0; i < ws.length; ++i) {
2788                 if ((w = ws[i]) != null) {
2789                     while ((t = w.poll()) != null) {
2790                         c.add(t);
2791                         ++count;
2792                     }
2793                 }
2794             }
2795         }
2796         return count;
2797     }
2798 
2799     /**
2800      * Returns a string identifying this pool, as well as its state,
2801      * including indications of run state, parallelism level, and
2802      * worker and task counts.
2803      *
2804      * @return a string identifying this pool, as well as its state
2805      */
2806     public String toString() {
2807         // Use a single pass through workQueues to collect counts
2808         int md = mode; // read volatile fields first
2809         long c = ctl;
2810         long st = stealCount;
2811         long qt = 0L, qs = 0L; int rc = 0;
2812         WorkQueue[] ws; WorkQueue w;
2813         if ((ws = workQueues) != null) {
2814             for (int i = 0; i < ws.length; ++i) {
2815                 if ((w = ws[i]) != null) {
2816                     int size = w.queueSize();
2817                     if ((i & 1) == 0)
2818                         qs += size;
2819                     else {
2820                         qt += size;
2821                         st += (long)w.nsteals & 0xffffffffL;
2822                         if (w.isApparentlyUnblocked())
2823                             ++rc;
2824                     }
2825                 }
2826             }
2827         }
2828 
2829         int pc = (md & SMASK);
2830         int tc = pc + (short)(c >>> TC_SHIFT);
2831         int ac = pc + (int)(c >> RC_SHIFT);
2832         if (ac < 0) // ignore transient negative
2833             ac = 0;
2834         String level = ((md & TERMINATED) != 0 ? "Terminated" :
2835                         (md & STOP)       != 0 ? "Terminating" :
2836                         (md & SHUTDOWN)   != 0 ? "Shutting down" :
2837                         "Running");
2838         return super.toString() +
2839             "[" + level +
2840             ", parallelism = " + pc +
2841             ", size = " + tc +
2842             ", active = " + ac +
2843             ", running = " + rc +
2844             ", steals = " + st +
2845             ", tasks = " + qt +
2846             ", submissions = " + qs +
2847             "]";
2848     }
2849 
2850     /**
2851      * Possibly initiates an orderly shutdown in which previously
2852      * submitted tasks are executed, but no new tasks will be
2853      * accepted. Invocation has no effect on execution state if this
2854      * is the {@link #commonPool()}, and no additional effect if
2855      * already shut down.  Tasks that are in the process of being
2856      * submitted concurrently during the course of this method may or
2857      * may not be rejected.
2858      *
2859      * @throws SecurityException if a security manager exists and
2860      *         the caller is not permitted to modify threads
2861      *         because it does not hold {@link
2862      *         java.lang.RuntimePermission}{@code ("modifyThread")}
2863      */
2864     public void shutdown() {
2865         checkPermission();
2866         tryTerminate(false, true);
2867     }
2868 
2869     /**
2870      * Possibly attempts to cancel and/or stop all tasks, and reject
2871      * all subsequently submitted tasks.  Invocation has no effect on
2872      * execution state if this is the {@link #commonPool()}, and no
2873      * additional effect if already shut down. Otherwise, tasks that
2874      * are in the process of being submitted or executed concurrently
2875      * during the course of this method may or may not be
2876      * rejected. This method cancels both existing and unexecuted
2877      * tasks, in order to permit termination in the presence of task
2878      * dependencies. So the method always returns an empty list
2879      * (unlike the case for some other Executors).
2880      *
2881      * @return an empty list
2882      * @throws SecurityException if a security manager exists and
2883      *         the caller is not permitted to modify threads
2884      *         because it does not hold {@link
2885      *         java.lang.RuntimePermission}{@code ("modifyThread")}
2886      */
2887     public List<Runnable> shutdownNow() {
2888         checkPermission();
2889         tryTerminate(true, true);
2890         return Collections.emptyList();
2891     }
2892 
2893     /**
2894      * Returns {@code true} if all tasks have completed following shut down.
2895      *
2896      * @return {@code true} if all tasks have completed following shut down
2897      */
2898     public boolean isTerminated() {
2899         return (mode & TERMINATED) != 0;
2900     }
2901 
2902     /**
2903      * Returns {@code true} if the process of termination has
2904      * commenced but not yet completed.  This method may be useful for
2905      * debugging. A return of {@code true} reported a sufficient
2906      * period after shutdown may indicate that submitted tasks have
2907      * ignored or suppressed interruption, or are waiting for I/O,
2908      * causing this executor not to properly terminate. (See the
2909      * advisory notes for class {@link ForkJoinTask} stating that
2910      * tasks should not normally entail blocking operations.  But if
2911      * they do, they must abort them on interrupt.)
2912      *
2913      * @return {@code true} if terminating but not yet terminated
2914      */
2915     public boolean isTerminating() {
2916         int md = mode;
2917         return (md & STOP) != 0 && (md & TERMINATED) == 0;
2918     }
2919 
2920     /**
2921      * Returns {@code true} if this pool has been shut down.
2922      *
2923      * @return {@code true} if this pool has been shut down
2924      */
2925     public boolean isShutdown() {
2926         return (mode & SHUTDOWN) != 0;
2927     }
2928 
2929     /**
2930      * Blocks until all tasks have completed execution after a
2931      * shutdown request, or the timeout occurs, or the current thread
2932      * is interrupted, whichever happens first. Because the {@link
2933      * #commonPool()} never terminates until program shutdown, when
2934      * applied to the common pool, this method is equivalent to {@link
2935      * #awaitQuiescence(long, TimeUnit)} but always returns {@code false}.
2936      *
2937      * @param timeout the maximum time to wait
2938      * @param unit the time unit of the timeout argument
2939      * @return {@code true} if this executor terminated and
2940      *         {@code false} if the timeout elapsed before termination
2941      * @throws InterruptedException if interrupted while waiting
2942      */
2943     public boolean awaitTermination(long timeout, TimeUnit unit)
2944         throws InterruptedException {
2945         if (Thread.interrupted())
2946             throw new InterruptedException();
2947         if (this == common) {
2948             awaitQuiescence(timeout, unit);
2949             return false;
2950         }
2951         long nanos = unit.toNanos(timeout);
2952         if (isTerminated())
2953             return true;
2954         if (nanos <= 0L)
2955             return false;
2956         long deadline = System.nanoTime() + nanos;
2957         synchronized (this) {
2958             for (;;) {
2959                 if (isTerminated())
2960                     return true;
2961                 if (nanos <= 0L)
2962                     return false;
2963                 long millis = TimeUnit.NANOSECONDS.toMillis(nanos);
2964                 wait(millis > 0L ? millis : 1L);
2965                 nanos = deadline - System.nanoTime();
2966             }
2967         }
2968     }
2969 
2970     /**
2971      * If called by a ForkJoinTask operating in this pool, equivalent
2972      * in effect to {@link ForkJoinTask#helpQuiesce}. Otherwise,
2973      * waits and/or attempts to assist performing tasks until this
2974      * pool {@link #isQuiescent} or the indicated timeout elapses.
2975      *
2976      * @param timeout the maximum time to wait
2977      * @param unit the time unit of the timeout argument
2978      * @return {@code true} if quiescent; {@code false} if the
2979      * timeout elapsed.
2980      */
2981     public boolean awaitQuiescence(long timeout, TimeUnit unit) {
2982         long nanos = unit.toNanos(timeout);
2983         ForkJoinWorkerThread wt;
2984         Thread thread = Thread.currentThread();
2985         if ((thread instanceof ForkJoinWorkerThread) &&
2986             (wt = (ForkJoinWorkerThread)thread).pool == this) {
2987             helpQuiescePool(wt.workQueue);
2988             return true;
2989         }
2990         else {
2991             for (long startTime = System.nanoTime();;) {
2992                 ForkJoinTask<?> t;
2993                 if ((t = pollScan(false)) != null)
2994                     t.doExec();
2995                 else if (isQuiescent())
2996                     return true;
2997                 else if ((System.nanoTime() - startTime) > nanos)
2998                     return false;
2999                 else
3000                     Thread.yield(); // cannot block
3001             }
3002         }
3003     }
3004 
3005     /**
3006      * Waits and/or attempts to assist performing tasks indefinitely
3007      * until the {@link #commonPool()} {@link #isQuiescent}.
3008      */
3009     static void quiesceCommonPool() {
3010         common.awaitQuiescence(Long.MAX_VALUE, TimeUnit.NANOSECONDS);
3011     }
3012 
3013     /**
3014      * Interface for extending managed parallelism for tasks running
3015      * in {@link ForkJoinPool}s.
3016      *
3017      * <p>A {@code ManagedBlocker} provides two methods.  Method
3018      * {@link #isReleasable} must return {@code true} if blocking is
3019      * not necessary. Method {@link #block} blocks the current thread
3020      * if necessary (perhaps internally invoking {@code isReleasable}
3021      * before actually blocking). These actions are performed by any
3022      * thread invoking {@link ForkJoinPool#managedBlock(ManagedBlocker)}.
3023      * The unusual methods in this API accommodate synchronizers that
3024      * may, but don't usually, block for long periods. Similarly, they
3025      * allow more efficient internal handling of cases in which
3026      * additional workers may be, but usually are not, needed to
3027      * ensure sufficient parallelism.  Toward this end,
3028      * implementations of method {@code isReleasable} must be amenable
3029      * to repeated invocation.
3030      *
3031      * <p>For example, here is a ManagedBlocker based on a
3032      * ReentrantLock:
3033      * <pre> {@code
3034      * class ManagedLocker implements ManagedBlocker {
3035      *   final ReentrantLock lock;
3036      *   boolean hasLock = false;
3037      *   ManagedLocker(ReentrantLock lock) { this.lock = lock; }
3038      *   public boolean block() {
3039      *     if (!hasLock)
3040      *       lock.lock();
3041      *     return true;
3042      *   }
3043      *   public boolean isReleasable() {
3044      *     return hasLock || (hasLock = lock.tryLock());
3045      *   }
3046      * }}</pre>
3047      *
3048      * <p>Here is a class that possibly blocks waiting for an
3049      * item on a given queue:
3050      * <pre> {@code
3051      * class QueueTaker<E> implements ManagedBlocker {
3052      *   final BlockingQueue<E> queue;
3053      *   volatile E item = null;
3054      *   QueueTaker(BlockingQueue<E> q) { this.queue = q; }
3055      *   public boolean block() throws InterruptedException {
3056      *     if (item == null)
3057      *       item = queue.take();
3058      *     return true;
3059      *   }
3060      *   public boolean isReleasable() {
3061      *     return item != null || (item = queue.poll()) != null;
3062      *   }
3063      *   public E getItem() { // call after pool.managedBlock completes
3064      *     return item;
3065      *   }
3066      * }}</pre>
3067      */
3068     public static interface ManagedBlocker {
3069         /**
3070          * Possibly blocks the current thread, for example waiting for
3071          * a lock or condition.
3072          *
3073          * @return {@code true} if no additional blocking is necessary
3074          * (i.e., if isReleasable would return true)
3075          * @throws InterruptedException if interrupted while waiting
3076          * (the method is not required to do so, but is allowed to)
3077          */
3078         boolean block() throws InterruptedException;
3079 
3080         /**
3081          * Returns {@code true} if blocking is unnecessary.
3082          * @return {@code true} if blocking is unnecessary
3083          */
3084         boolean isReleasable();
3085     }
3086 
3087     /**
3088      * Runs the given possibly blocking task.  When {@linkplain
3089      * ForkJoinTask#inForkJoinPool() running in a ForkJoinPool}, this
3090      * method possibly arranges for a spare thread to be activated if
3091      * necessary to ensure sufficient parallelism while the current
3092      * thread is blocked in {@link ManagedBlocker#block blocker.block()}.
3093      *
3094      * <p>This method repeatedly calls {@code blocker.isReleasable()} and
3095      * {@code blocker.block()} until either method returns {@code true}.
3096      * Every call to {@code blocker.block()} is preceded by a call to
3097      * {@code blocker.isReleasable()} that returned {@code false}.
3098      *
3099      * <p>If not running in a ForkJoinPool, this method is
3100      * behaviorally equivalent to
3101      * <pre> {@code
3102      * while (!blocker.isReleasable())
3103      *   if (blocker.block())
3104      *     break;}</pre>
3105      *
3106      * If running in a ForkJoinPool, the pool may first be expanded to
3107      * ensure sufficient parallelism available during the call to
3108      * {@code blocker.block()}.
3109      *
3110      * @param blocker the blocker task
3111      * @throws InterruptedException if {@code blocker.block()} did so
3112      */
3113     public static void managedBlock(ManagedBlocker blocker)
3114         throws InterruptedException {
3115         if (blocker == null) throw new NullPointerException();
3116         ForkJoinPool p;
3117         ForkJoinWorkerThread wt;
3118         WorkQueue w;
3119         Thread t = Strands.currentCarrierThread();
3120         if ((t instanceof ForkJoinWorkerThread) &&
3121             (p = (wt = (ForkJoinWorkerThread)t).pool) != null &&
3122             (w = wt.workQueue) != null) {
3123             int block;
3124             while (!blocker.isReleasable()) {
3125                 if ((block = p.tryCompensate(w)) != 0) {
3126                     try {
3127                         do {} while (!blocker.isReleasable() &&
3128                                      !blocker.block());
3129                     } finally {
3130                         CTL.getAndAdd(p, (block > 0) ? RC_UNIT : 0L);
3131                     }
3132                     break;
3133                 }
3134             }
3135         }
3136         else {
3137             do {} while (!blocker.isReleasable() &&
3138                          !blocker.block());
3139         }
3140     }
3141 
3142     /**
3143      * If the given executor is a ForkJoinPool, poll and execute
3144      * AsynchronousCompletionTasks from worker's queue until none are
3145      * available or blocker is released.
3146      */
3147     static void helpAsyncBlocker(Executor e, ManagedBlocker blocker) {
3148         if (e instanceof ForkJoinPool) {
3149             WorkQueue w; ForkJoinWorkerThread wt; WorkQueue[] ws; int r, n;
3150             ForkJoinPool p = (ForkJoinPool)e;
3151             Thread thread = Thread.currentThread();
3152             if (thread instanceof ForkJoinWorkerThread &&
3153                 (wt = (ForkJoinWorkerThread)thread).pool == p)
3154                 w = wt.workQueue;
3155             else if ((r = ThreadLocalRandom.getProbe()) != 0 &&
3156                      (ws = p.workQueues) != null && (n = ws.length) > 0)
3157                 w = ws[(n - 1) & r & SQMASK];
3158             else
3159                 w = null;
3160             if (w != null)
3161                 w.helpAsyncBlocker(blocker);
3162         }
3163     }
3164 
3165     // AbstractExecutorService overrides.  These rely on undocumented
3166     // fact that ForkJoinTask.adapt returns ForkJoinTasks that also
3167     // implement RunnableFuture.
3168 
3169     protected <T> RunnableFuture<T> newTaskFor(Runnable runnable, T value) {
3170         return new ForkJoinTask.AdaptedRunnable<T>(runnable, value);
3171     }
3172 
3173     protected <T> RunnableFuture<T> newTaskFor(Callable<T> callable) {
3174         return new ForkJoinTask.AdaptedCallable<T>(callable);
3175     }
3176 
3177     // VarHandle mechanics
3178     private static final VarHandle CTL;
3179     private static final VarHandle MODE;
3180     static final VarHandle QA;
3181 
3182     static {
3183         try {
3184             MethodHandles.Lookup l = MethodHandles.lookup();
3185             CTL = l.findVarHandle(ForkJoinPool.class, "ctl", long.class);
3186             MODE = l.findVarHandle(ForkJoinPool.class, "mode", int.class);
3187             QA = MethodHandles.arrayElementVarHandle(ForkJoinTask[].class);
3188         } catch (ReflectiveOperationException e) {
3189             throw new ExceptionInInitializerError(e);
3190         }
3191 
3192         // Reduce the risk of rare disastrous classloading in first call to
3193         // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
3194         Class<?> ensureLoaded = LockSupport.class;
3195 
3196         int commonMaxSpares = DEFAULT_COMMON_MAX_SPARES;
3197         try {
3198             String p = System.getProperty
3199                 ("java.util.concurrent.ForkJoinPool.common.maximumSpares");
3200             if (p != null)
3201                 commonMaxSpares = Integer.parseInt(p);
3202         } catch (Exception ignore) {}
3203         COMMON_MAX_SPARES = commonMaxSpares;
3204 
3205         defaultForkJoinWorkerThreadFactory =
3206             new DefaultForkJoinWorkerThreadFactory();
3207         modifyThreadPermission = new RuntimePermission("modifyThread");
3208 
3209         common = AccessController.doPrivileged(new PrivilegedAction<>() {
3210             public ForkJoinPool run() {
3211                 return new ForkJoinPool((byte)0); }});
3212 
3213         COMMON_PARALLELISM = Math.max(common.mode & SMASK, 1);
3214     }
3215 
3216     /**
3217      * Factory for innocuous worker threads.
3218      */
3219     private static final class InnocuousForkJoinWorkerThreadFactory
3220         implements ForkJoinWorkerThreadFactory {
3221 
3222         /**
3223          * An ACC to restrict permissions for the factory itself.
3224          * The constructed workers have no permissions set.
3225          */
3226         private static final AccessControlContext ACC = contextWithPermissions(
3227             modifyThreadPermission,
3228             new RuntimePermission("enableContextClassLoaderOverride"),
3229             new RuntimePermission("modifyThreadGroup"),
3230             new RuntimePermission("getClassLoader"),
3231             new RuntimePermission("setContextClassLoader"));
3232 
3233         public final ForkJoinWorkerThread newThread(ForkJoinPool pool) {
3234             return AccessController.doPrivileged(
3235                 new PrivilegedAction<>() {
3236                     public ForkJoinWorkerThread run() {
3237                         return new ForkJoinWorkerThread.
3238                             InnocuousForkJoinWorkerThread(pool); }},
3239                 ACC);
3240         }
3241     }
3242 }