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.reflect.Field;
  40 import java.security.AccessController;
  41 import java.security.AccessControlContext;
  42 import java.security.Permission;
  43 import java.security.Permissions;
  44 import java.security.PrivilegedAction;
  45 import java.security.ProtectionDomain;
  46 import java.util.ArrayList;
  47 import java.util.Collection;
  48 import java.util.Collections;
  49 import java.util.List;
  50 import java.util.Objects;
  51 import java.util.function.Predicate;
  52 import java.util.concurrent.CountDownLatch;
  53 import java.util.concurrent.locks.LockSupport;
  54 import jdk.internal.access.JavaUtilConcurrentFJPAccess;
  55 import jdk.internal.access.SharedSecrets;
  56 import jdk.internal.misc.Unsafe;
  57 import jdk.internal.vm.SharedThreadContainer;
  58 
  59 /**
  60  * An {@link ExecutorService} for running {@link ForkJoinTask}s.
  61  * A {@code ForkJoinPool} provides the entry point for submissions
  62  * from non-{@code ForkJoinTask} clients, as well as management and
  63  * monitoring operations.
  64  *
  65  * <p>A {@code ForkJoinPool} differs from other kinds of {@link
  66  * ExecutorService} mainly by virtue of employing
  67  * <em>work-stealing</em>: all threads in the pool attempt to find and
  68  * execute tasks submitted to the pool and/or created by other active
  69  * tasks (eventually blocking waiting for work if none exist). This
  70  * enables efficient processing when most tasks spawn other subtasks
  71  * (as do most {@code ForkJoinTask}s), as well as when many small
  72  * tasks are submitted to the pool from external clients.  Especially
  73  * when setting <em>asyncMode</em> to true in constructors, {@code
  74  * ForkJoinPool}s may also be appropriate for use with event-style
  75  * tasks that are never joined. All worker threads are initialized
  76  * with {@link Thread#isDaemon} set {@code true}.
  77  *
  78  * <p>A static {@link #commonPool()} is available and appropriate for
  79  * most applications. The common pool is used by any ForkJoinTask that
  80  * is not explicitly submitted to a specified pool. Using the common
  81  * pool normally reduces resource usage (its threads are slowly
  82  * reclaimed during periods of non-use, and reinstated upon subsequent
  83  * use).
  84  *
  85  * <p>For applications that require separate or custom pools, a {@code
  86  * ForkJoinPool} may be constructed with a given target parallelism
  87  * level; by default, equal to the number of available processors.
  88  * The pool attempts to maintain enough active (or available) threads
  89  * by dynamically adding, suspending, or resuming internal worker
  90  * threads, even if some tasks are stalled waiting to join others.
  91  * However, no such adjustments are guaranteed in the face of blocked
  92  * I/O or other unmanaged synchronization. The nested {@link
  93  * ManagedBlocker} interface enables extension of the kinds of
  94  * synchronization accommodated. The default policies may be
  95  * overridden using a constructor with parameters corresponding to
  96  * those documented in class {@link ThreadPoolExecutor}.
  97  *
  98  * <p>In addition to execution and lifecycle control methods, this
  99  * class provides status check methods (for example
 100  * {@link #getStealCount}) that are intended to aid in developing,
 101  * tuning, and monitoring fork/join applications. Also, method
 102  * {@link #toString} returns indications of pool state in a
 103  * convenient form for informal monitoring.
 104  *
 105  * <p>As is the case with other ExecutorServices, there are three
 106  * main task execution methods summarized in the following table.
 107  * These are designed to be used primarily by clients not already
 108  * engaged in fork/join computations in the current pool.  The main
 109  * forms of these methods accept instances of {@code ForkJoinTask},
 110  * but overloaded forms also allow mixed execution of plain {@code
 111  * Runnable}- or {@code Callable}- based activities as well.  However,
 112  * tasks that are already executing in a pool should normally instead
 113  * use the within-computation forms listed in the table unless using
 114  * async event-style tasks that are not usually joined, in which case
 115  * there is little difference among choice of methods.
 116  *
 117  * <table class="plain">
 118  * <caption>Summary of task execution methods</caption>
 119  *  <tr>
 120  *    <td></td>
 121  *    <th scope="col"> Call from non-fork/join clients</th>
 122  *    <th scope="col"> Call from within fork/join computations</th>
 123  *  </tr>
 124  *  <tr>
 125  *    <th scope="row" style="text-align:left"> Arrange async execution</th>
 126  *    <td> {@link #execute(ForkJoinTask)}</td>
 127  *    <td> {@link ForkJoinTask#fork}</td>
 128  *  </tr>
 129  *  <tr>
 130  *    <th scope="row" style="text-align:left"> Await and obtain result</th>
 131  *    <td> {@link #invoke(ForkJoinTask)}</td>
 132  *    <td> {@link ForkJoinTask#invoke}</td>
 133  *  </tr>
 134  *  <tr>
 135  *    <th scope="row" style="text-align:left"> Arrange exec and obtain Future</th>
 136  *    <td> {@link #submit(ForkJoinTask)}</td>
 137  *    <td> {@link ForkJoinTask#fork} (ForkJoinTasks <em>are</em> Futures)</td>
 138  *  </tr>
 139  * </table>
 140  *
 141  * <p>The parameters used to construct the common pool may be controlled by
 142  * setting the following {@linkplain System#getProperty system properties}:
 143  * <ul>
 144  * <li>{@systemProperty java.util.concurrent.ForkJoinPool.common.parallelism}
 145  * - the parallelism level, a non-negative integer
 146  * <li>{@systemProperty java.util.concurrent.ForkJoinPool.common.threadFactory}
 147  * - the class name of a {@link ForkJoinWorkerThreadFactory}.
 148  * The {@linkplain ClassLoader#getSystemClassLoader() system class loader}
 149  * is used to load this class.
 150  * <li>{@systemProperty java.util.concurrent.ForkJoinPool.common.exceptionHandler}
 151  * - the class name of a {@link UncaughtExceptionHandler}.
 152  * The {@linkplain ClassLoader#getSystemClassLoader() system class loader}
 153  * is used to load this class.
 154  * <li>{@systemProperty java.util.concurrent.ForkJoinPool.common.maximumSpares}
 155  * - the maximum number of allowed extra threads to maintain target
 156  * parallelism (default 256).
 157  * </ul>
 158  * If no thread factory is supplied via a system property, then the
 159  * common pool uses a factory that uses the system class loader as the
 160  * {@linkplain Thread#getContextClassLoader() thread context class loader}.
 161  * In addition, if a {@link SecurityManager} is present, then
 162  * the common pool uses a factory supplying threads that have no
 163  * {@link Permissions} enabled, and are not guaranteed to preserve
 164  * the values of {@link java.lang.ThreadLocal} variables across tasks.
 165  *
 166  * Upon any error in establishing these settings, default parameters
 167  * are used. It is possible to disable or limit the use of threads in
 168  * the common pool by setting the parallelism property to zero, and/or
 169  * using a factory that may return {@code null}. However doing so may
 170  * cause unjoined tasks to never be executed.
 171  *
 172  * @implNote This implementation restricts the maximum number of
 173  * running threads to 32767. Attempts to create pools with greater
 174  * than the maximum number result in {@code
 175  * IllegalArgumentException}. Also, this implementation rejects
 176  * submitted tasks (that is, by throwing {@link
 177  * RejectedExecutionException}) only when the pool is shut down or
 178  * internal resources have been exhausted.
 179  *
 180  * @since 1.7
 181  * @author Doug Lea
 182  */
 183 public class ForkJoinPool extends AbstractExecutorService {
 184 
 185     /*
 186      * Implementation Overview
 187      *
 188      * This class and its nested classes provide the main
 189      * functionality and control for a set of worker threads.  Because
 190      * most internal methods and nested classes are interrelated,
 191      * their main rationale and descriptions are presented here;
 192      * individual methods and nested classes contain only brief
 193      * comments about details. Broadly: submissions from non-FJ
 194      * threads enter into submission queues.  Workers take these tasks
 195      * and typically split them into subtasks that may be stolen by
 196      * other workers. Work-stealing based on randomized scans
 197      * generally leads to better throughput than "work dealing" in
 198      * which producers assign tasks to idle threads, in part because
 199      * threads that have finished other tasks before the signalled
 200      * thread wakes up (which can be a long time) can take the task
 201      * instead.  Preference rules give first priority to processing
 202      * tasks from their own queues (LIFO or FIFO, depending on mode),
 203      * then to randomized FIFO steals of tasks in other queues.  This
 204      * framework began as vehicle for supporting tree-structured
 205      * parallelism using work-stealing.  Over time, its scalability
 206      * advantages led to extensions and changes to better support more
 207      * diverse usage contexts.  Here's a brief history of major
 208      * revisions, each also with other minor features and changes.
 209      *
 210      * 1. Only handle recursively structured computational tasks
 211      * 2. Async (FIFO) mode and striped submission queues
 212      * 3. Completion-based tasks (mainly CountedCompleters)
 213      * 4. CommonPool and parallelStream support
 214      * 5. InterruptibleTasks for externally submitted tasks
 215      *
 216      * Most changes involve adaptions of base algorithms using
 217      * combinations of static and dynamic bitwise mode settings (both
 218      * here and in ForkJoinTask), and subclassing of ForkJoinTask.
 219      * There are a fair number of odd code constructions and design
 220      * decisions for components that reside at the edge of Java vs JVM
 221      * functionality.
 222      *
 223      * WorkQueues
 224      * ==========
 225      *
 226      * Most operations occur within work-stealing queues (in nested
 227      * class WorkQueue).  These are special forms of Deques that
 228      * support only three of the four possible end-operations -- push,
 229      * pop, and poll (aka steal), under the further constraints that
 230      * push and pop are called only from the owning thread (or, as
 231      * extended here, under a lock), while poll may be called from
 232      * other threads.  (If you are unfamiliar with them, you probably
 233      * want to read Herlihy and Shavit's book "The Art of
 234      * Multiprocessor programming", chapter 16 describing these in
 235      * more detail before proceeding.)  The main work-stealing queue
 236      * design is roughly similar to those in the papers "Dynamic
 237      * Circular Work-Stealing Deque" by Chase and Lev, SPAA 2005
 238      * (http://research.sun.com/scalable/pubs/index.html) and
 239      * "Idempotent work stealing" by Michael, Saraswat, and Vechev,
 240      * PPoPP 2009 (http://portal.acm.org/citation.cfm?id=1504186).
 241      * The main differences ultimately stem from GC requirements that
 242      * we null out taken slots as soon as we can, to maintain as small
 243      * a footprint as possible even in programs generating huge
 244      * numbers of tasks. To accomplish this, we shift the CAS
 245      * arbitrating pop vs poll (steal) from being on the indices
 246      * ("base" and "top") to the slots themselves. These provide the
 247      * primary required memory ordering -- see "Correct and Efficient
 248      * Work-Stealing for Weak Memory Models" by Le, Pop, Cohen, and
 249      * Nardelli, PPoPP 2013
 250      * (http://www.di.ens.fr/~zappa/readings/ppopp13.pdf) for an
 251      * analysis of memory ordering requirements in work-stealing
 252      * algorithms similar to the one used here.  We use per-operation
 253      * ordered writes of various kinds for updates, but usually use
 254      * explicit load fences for reads, to cover access of several
 255      * fields of possibly several objects without further constraining
 256      * read-by-read ordering.
 257      *
 258      * We also support a user mode in which local task processing is
 259      * in FIFO, not LIFO order, simply by using a local version of
 260      * poll rather than pop.  This can be useful in message-passing
 261      * frameworks in which tasks are never joined, although with
 262      * increased contention among task producers and consumers. Also,
 263      * the same data structure (and class) is used for "submission
 264      * queues" (described below) holding externally submitted tasks,
 265      * that differ only in that a lock (using field "phase"; see below) is
 266      * required by external callers to push and pop tasks.
 267      *
 268      * Adding tasks then takes the form of a classic array push(task)
 269      * in a circular buffer:
 270      *    q.array[q.top++ % length] = task;
 271      *
 272      * The actual code needs to null-check and size-check the array,
 273      * uses masking, not mod, for indexing a power-of-two-sized array,
 274      * enforces memory ordering, supports resizing, and possibly
 275      * signals waiting workers to start scanning (described below),
 276      * which requires stronger forms of order accesses.
 277      *
 278      * The pop operation (always performed by owner) is of the form:
 279      *   if ((task = getAndSet(q.array, (q.top-1) % length, null)) != null)
 280      *        decrement top and return task;
 281      * If this fails, the queue is empty. This operation is one part
 282      * of the nextLocalTask method, that instead does a local-poll
 283      * in FIFO mode.
 284      *
 285      * The poll operation is, basically:
 286      *   if (CAS nonnull task t = q.array[k = q.base % length] to null)
 287      *       increment base and return task;
 288      *
 289      * However, there are several more cases that must be dealt with.
 290      * Some of them are just due to asynchrony; others reflect
 291      * contention and stealing policies. Stepping through them
 292      * illustrates some of the implementation decisions in this class.
 293      *
 294      *  * Slot k must be read with an acquiring read, which it must
 295      *    anyway to dereference and run the task if the (acquiring)
 296      *    CAS succeeds, but uses an explicit acquire fence to support
 297      *    the following rechecks even if the CAS is not attempted.  To
 298      *    more easily distinguish among kinds of CAS failures, we use
 299      *    the compareAndExchange version, and usually handle null
 300      *    returns (indicating contention) separately from others.
 301      *
 302      *  * q.base may change between reading and using its value to
 303      *    index the slot. To avoid trying to use the wrong t, the
 304      *    index and slot must be reread (not necessarily immediately)
 305      *    until consistent, unless this is a local poll by owner, in
 306      *    which case this form of inconsistency can only appear as t
 307      *    being null, below.
 308      *
 309      *  * Similarly, q.array may change (due to a resize), unless this
 310      *    is a local poll by owner. Otherwise, when t is present, this
 311      *    only needs consideration on CAS failure (since a CAS
 312      *    confirms the non-resized case.)
 313      *
 314      *  * t may appear null because a previous poll operation has not
 315      *    yet incremented q.base, so the read is from an already-taken
 316      *    index. This form of stall reflects the non-lock-freedom of
 317      *    the poll operation. Stalls can be detected by observing that
 318      *    q.base doesn't change on repeated reads of null t and when
 319      *    no other alternatives apply, spin-wait for it to settle.  To
 320      *    reduce producing these kinds of stalls by other stealers, we
 321      *    encourage timely writes to indices using otherwise
 322      *    unnecessarily strong writes.
 323      *
 324      *  * The CAS may fail, in which case we may want to retry unless
 325      *    there is too much contention. One goal is to balance and
 326      *    spread out the many forms of contention that may be
 327      *    encountered across polling and other operations to avoid
 328      *    sustained performance degradations. Across all cases where
 329      *    alternatives exist, a bounded number of CAS misses or stalls
 330      *    are tolerated (for slots, ctl, and elsewhere described
 331      *    below) before taking alternative action. These may move
 332      *    contention or retries elsewhere, which is still preferable
 333      *    to single-point bottlenecks.
 334      *
 335      *  * Even though the check "top == base" is quiescently accurate
 336      *    to determine whether a queue is empty, it is not of much use
 337      *    when deciding whether to try to poll or repoll after a
 338      *    failure.  Both top and base may move independently, and both
 339      *    lag updates to the underlying array. To reduce memory
 340      *    contention, non-owners avoid reading the "top" when
 341      *    possible, by using one-ahead reads to check whether to
 342      *    repoll, relying on the fact that a non-empty queue does not
 343      *    have two null slots in a row, except in cases (resizes and
 344      *    shifts) that can be detected with a secondary recheck that
 345      *    is less likely to conflict with owner writes.
 346      *
 347      * The poll operations in q.poll(), scan(), helpJoin(), and
 348      * elsewhere differ with respect to whether other queues are
 349      * available to try, and the presence or nature of screening steps
 350      * when only some kinds of tasks can be taken. When alternatives
 351      * (or failing) is an option, they uniformly give up after
 352      * bounded numbers of stalls and/or CAS failures, which reduces
 353      * contention when too many workers are polling too few tasks.
 354      * Overall, in the aggregate, we ensure probabilistic
 355      * non-blockingness of work-stealing at least until checking
 356      * quiescence (which is intrinsically blocking): If an attempted
 357      * steal fails in these ways, a scanning thief chooses a different
 358      * target to try next. In contexts where alternatives aren't
 359      * available, and when progress conditions can be isolated to
 360      * values of a single variable, simple spinloops (using
 361      * Thread.onSpinWait) are used to reduce memory traffic.
 362      *
 363      * WorkQueues are also used in a similar way for tasks submitted
 364      * to the pool. We cannot mix these tasks in the same queues used
 365      * by workers. Instead, we randomly associate submission queues
 366      * with submitting threads, using a form of hashing.  The
 367      * ThreadLocalRandom probe value serves as a hash code for
 368      * choosing existing queues, and may be randomly repositioned upon
 369      * contention with other submitters.  In essence, submitters act
 370      * like workers except that they are restricted to executing local
 371      * tasks that they submitted (or when known, subtasks thereof).
 372      * Insertion of tasks in shared mode requires a lock. We use only
 373      * a simple spinlock (as one role of field "phase") because
 374      * submitters encountering a busy queue move to a different
 375      * position to use or create other queues.  They (spin) block when
 376      * registering new queues, or indirectly elsewhere, by revisiting
 377      * later.
 378      *
 379      * Management
 380      * ==========
 381      *
 382      * The main throughput advantages of work-stealing stem from
 383      * decentralized control -- workers mostly take tasks from
 384      * themselves or each other, at rates that can exceed a billion
 385      * per second.  Most non-atomic control is performed by some form
 386      * of scanning across or within queues.  The pool itself creates,
 387      * activates (enables scanning for and running tasks),
 388      * deactivates, blocks, and terminates threads, all with minimal
 389      * central information.  There are only a few properties that we
 390      * can globally track or maintain, so we pack them into a small
 391      * number of variables, often maintaining atomicity without
 392      * blocking or locking.  Nearly all essentially atomic control
 393      * state is held in a few variables that are by far most often
 394      * read (not written) as status and consistency checks. We pack as
 395      * much information into them as we can.
 396      *
 397      * Field "ctl" contains 64 bits holding information needed to
 398      * atomically decide to add, enqueue (on an event queue), and
 399      * dequeue and release workers.  To enable this packing, we
 400      * restrict maximum parallelism to (1<<15)-1 (which is far in
 401      * excess of normal operating range) to allow ids, counts, and
 402      * their negations (used for thresholding) to fit into 16bit
 403      * subfields.
 404      *
 405      * Field "runState" and per-WorkQueue field "phase" play similar
 406      * roles, as lockable, versioned counters. Field runState also
 407      * includes monotonic event bits (SHUTDOWN, STOP, and TERMINATED).
 408      * The version tags enable detection of state changes (by
 409      * comparing two reads) modulo bit wraparound. The bit range in
 410      * each case suffices for purposes of determining quiescence,
 411      * termination, avoiding ABA-like errors, and signal control, most
 412      * of which are ultimately based on at most 15bit ranges (due to
 413      * 32767 max total workers). RunState updates do not need to be
 414      * atomic with respect to ctl updates, but because they are not,
 415      * some care is required to avoid stalls. The seqLock properties
 416      * detect changes and conditionally upgrade to coordinate with
 417      * updates. It is typically held for less than a dozen
 418      * instructions unless the queue array is being resized, during
 419      * which contention is rare. To be conservative, lockRunState is
 420      * implemented as a spin/sleep loop. Here and elsewhere spin
 421      * constants are short enough to apply even on systems with few
 422      * available processors.  In addition to checking pool status,
 423      * reads of runState sometimes serve as acquire fences before
 424      * reading other fields.
 425      *
 426      * Field "parallelism" holds the target parallelism (normally
 427      * corresponding to pool size). Users can dynamically reset target
 428      * parallelism, but is only accessed when signalling or awaiting
 429      * work, so only slowly has an effect in creating threads or
 430      * letting them time out and terminate when idle.
 431      *
 432      * Array "queues" holds references to WorkQueues.  It is updated
 433      * (only during worker creation and termination) under the
 434      * runState lock. It is otherwise concurrently readable but reads
 435      * for use in scans (see below) are always prefaced by a volatile
 436      * read of runState (or equivalent constructions), ensuring that
 437      * its state is current at the point it is used (which is all we
 438      * require). To simplify index-based operations, the array size is
 439      * always a power of two, and all readers must tolerate null
 440      * slots.  Worker queues are at odd indices. Worker phase ids
 441      * masked with SMASK match their index. Shared (submission) queues
 442      * are at even indices. Grouping them together in this way aids in
 443      * task scanning: At top-level, both kinds of queues should be
 444      * sampled with approximately the same probability, which is
 445      * simpler if they are all in the same array. But we also need to
 446      * identify what kind they are without looking at them, leading to
 447      * this odd/even scheme. One disadvantage is that there are
 448      * usually many fewer submission queues, so there can be many
 449      * wasted probes (null slots). But this is still cheaper than
 450      * alternatives. Other loops over the queues array vary in origin
 451      * and stride depending on whether they cover only submission
 452      * (even) or worker (odd) queues or both, and whether they require
 453      * randomness (in which case cyclically exhaustive strides may be
 454      * used).
 455      *
 456      * All worker thread creation is on-demand, triggered by task
 457      * submissions, replacement of terminated workers, and/or
 458      * compensation for blocked workers. However, all other support
 459      * code is set up to work with other policies.  To ensure that we
 460      * do not hold on to worker or task references that would prevent
 461      * GC, all accesses to workQueues in waiting, signalling, and
 462      * control methods are via indices into the queues array (which is
 463      * one source of some of the messy code constructions here). In
 464      * essence, the queues array serves as a weak reference
 465      * mechanism. In particular, the stack top subfield of ctl stores
 466      * indices, not references. Operations on queues obtained from
 467      * these indices remain valid (with at most some unnecessary extra
 468      * work) even if an underlying worker failed and was replaced by
 469      * another at the same index. During termination, worker queue
 470      * array updates are disabled.
 471      *
 472      * Queuing Idle Workers. Unlike HPC work-stealing frameworks, we
 473      * cannot let workers spin indefinitely scanning for tasks when
 474      * none can be found immediately, and we cannot start/resume
 475      * workers unless there appear to be tasks available.  On the
 476      * other hand, we must quickly prod them into action when new
 477      * tasks are submitted or generated. These latencies are mainly a
 478      * function of JVM park/unpark (and underlying OS) performance,
 479      * which can be slow and variable (even though usages are
 480      * streamlined as much as possible).  In many usages, ramp-up time
 481      * is the main limiting factor in overall performance, which is
 482      * compounded at program start-up by JIT compilation and
 483      * allocation. On the other hand, throughput degrades when too
 484      * many threads poll for too few tasks. (See below.)
 485      *
 486      * The "ctl" field atomically maintains total and "released"
 487      * worker counts, plus the head of the available worker queue
 488      * (actually stack, represented by the lower 32bit subfield of
 489      * ctl).  Released workers are those known to be scanning for
 490      * and/or running tasks (we cannot accurately determine
 491      * which). Unreleased ("available") workers are recorded in the
 492      * ctl stack. These workers are made eligible for signalling by
 493      * enqueuing in ctl (see method runWorker).  This "queue" is a
 494      * form of Treiber stack. This is ideal for activating threads in
 495      * most-recently used order, and improves performance and
 496      * locality, outweighing the disadvantages of being prone to
 497      * contention and inability to release a worker unless it is
 498      * topmost on stack. The top stack state holds the value of the
 499      * "phase" field of the worker: its index and status, plus a
 500      * version counter that, in addition to the count subfields (also
 501      * serving as version stamps) provide protection against Treiber
 502      * stack ABA effects.
 503      *
 504      * Creating workers. To create a worker, we pre-increment counts
 505      * (serving as a reservation), and attempt to construct a
 506      * ForkJoinWorkerThread via its factory. On starting, the new
 507      * thread first invokes registerWorker, where it constructs a
 508      * WorkQueue and is assigned an index in the queues array
 509      * (expanding the array if necessary).  Upon any exception across
 510      * these steps, or null return from factory, deregisterWorker
 511      * adjusts counts and records accordingly.  If a null return, the
 512      * pool continues running with fewer than the target number
 513      * workers. If exceptional, the exception is propagated, generally
 514      * to some external caller.
 515      *
 516      * WorkQueue field "phase" encodes the queue array id in lower
 517      * bits, and otherwise acts similarly to the pool runState field:
 518      * The "IDLE" bit is clear while active (either a released worker
 519      * or a locked external queue), with other bits serving as a
 520      * version counter to distinguish changes across multiple reads.
 521      * Note that phase field updates lag queue CAS releases; seeing a
 522      * non-idle phase does not guarantee that the worker is available
 523      * (and so is never checked in this way).
 524      *
 525      * The ctl field also serves as the basis for memory
 526      * synchronization surrounding activation. This uses a more
 527      * efficient version of a Dekker-like rule that task producers and
 528      * consumers sync with each other by both writing/CASing ctl (even
 529      * if to its current value).  However, rather than CASing ctl to
 530      * its current value in the common case where no action is
 531      * required, we reduce write contention by ensuring that
 532      * signalWork invocations are prefaced with a fully fenced memory
 533      * access (which is usually needed anyway).
 534      *
 535      * Signalling. Signals (in signalWork) cause new or reactivated
 536      * workers to scan for tasks.  Method signalWork and its callers
 537      * try to approximate the unattainable goal of having the right
 538      * number of workers activated for the tasks at hand, but must err
 539      * on the side of too many workers vs too few to avoid stalls:
 540      *
 541      *  * If computations are purely tree structured, it suffices for
 542      *    every worker to activate another when it pushes a task into
 543      *    an empty queue, resulting in O(log(#threads)) steps to full
 544      *    activation. Emptiness must be conservatively approximated,
 545      *    sometimes resulting in unnecessary signals.  Also, to reduce
 546      *    resource usages in some cases, at the expense of slower
 547      *    startup in others, activation of an idle thread is preferred
 548      *    over creating a new one, here and elsewhere.
 549      *
 550      *  * If instead, tasks come in serially from only a single
 551      *    producer, each worker taking its first (since the last
 552      *    activation) task from a queue should propagate a signal if
 553      *    there are more tasks in that queue. This is equivalent to,
 554      *    but generally faster than, arranging the stealer take
 555      *    multiple tasks, re-pushing one or more on its own queue, and
 556      *    signalling (because its queue is empty), also resulting in
 557      *    logarithmic full activation time
 558      *
 559      * * Because we don't know about usage patterns (or most commonly,
 560      *    mixtures), we use both approaches, which present even more
 561      *    opportunities to over-signal.  Note that in either of these
 562      *    contexts, signals may be (and often are) unnecessary because
 563      *    active workers continue scanning after running tasks without
 564      *    the need to be signalled (which is one reason work stealing
 565      *    is often faster than alternatives), so additional workers
 566      *    aren't needed. We filter out some of these cases by exiting
 567      *    retry loops in signalWork if the task responsible for the
 568      *    signal has already been taken.
 569      *
 570      * * For rapidly branching tasks that require full pool resources,
 571      *   oversignalling is OK, because signalWork will soon have no
 572      *   more workers to create or reactivate. But for others (mainly
 573      *   externally submitted tasks), overprovisioning may cause very
 574      *   noticeable slowdowns due to contention and resource
 575      *   wastage. All remedies are intrinsically heuristic. We use a
 576      *   strategy that works well in most cases: We track "sources"
 577      *   (queue ids) of non-empty (usually polled) queues while
 578      *   scanning. These are maintained in the "source" field of
 579      *   WorkQueues for use in method helpJoin and elsewhere (see
 580      *   below). We also maintain them as arguments/results of
 581      *   top-level polls (argument "window" in method scan, with setup
 582      *   in method runWorker) as an encoded sliding window of current
 583      *   and previous two sources (or INVALID_ID if none), and stop
 584      *   signalling when all were from the same source. These
 585      *   mechanisms may result in transiently too few workers, but
 586      *   once workers poll from a new source, they rapidly reactivate
 587      *   others.
 588      *
 589      * * Despite these, signal contention and overhead effects still
 590      *   occur during ramp-up and ramp-down of small computations.
 591      *
 592      * Scanning. Method scan performs top-level scanning for (and
 593      * execution of) tasks by polling a pseudo-random permutation of
 594      * the array (by starting at a given index, and using a constant
 595      * cyclically exhaustive stride.)  It uses the same basic polling
 596      * method as WorkQueue.poll(), but restarts with a different
 597      * permutation on each invocation.  The pseudorandom generator
 598      * need not have high-quality statistical properties in the long
 599      * term. We use Marsaglia XorShifts, seeded with the Weyl sequence
 600      * from ThreadLocalRandom probes, which are cheap and
 601      * suffice. Scans do not otherwise explicitly take into account
 602      * core affinities, loads, cache localities, etc, However, they do
 603      * exploit temporal locality (which usually approximates these) by
 604      * preferring to re-poll from the same queue (either in method
 605      * tryPoll() or scan) after a successful poll before trying others
 606      * (see method topLevelExec), which also reduces bookkeeping,
 607      * cache traffic, and scanning overhead. But it also reduces
 608      * fairness, which is partially counteracted by giving up on
 609      * contention.
 610      *
 611      * Deactivation. When method scan indicates that no tasks are
 612      * found by a worker, it tries to deactivate (in awaitWork),
 613      * giving up (and rescanning) on ctl contention. To avoid missed
 614      * signals during deactivation, the method rescans and reactivates
 615      * if there may have been a missed signal during deactivation,
 616      * filtering out most cases in which this is unnecessary. Because
 617      * idle workers are often not yet blocked (parked), we use the
 618      * WorkQueue parking field to advertise that a waiter actually
 619      * needs unparking upon signal.
 620      *
 621      * Quiescence. Workers scan looking for work, giving up when they
 622      * don't find any, without being sure that none are available.
 623      * However, some required functionality relies on consensus about
 624      * quiescence (also termination, discussed below). The count
 625      * fields in ctl allow accurate discovery of states in which all
 626      * workers are idle.  However, because external (asynchronous)
 627      * submitters are not part of this vote, these mechanisms
 628      * themselves do not guarantee that the pool is in a quiescent
 629      * state with respect to methods isQuiescent, shutdown (which
 630      * begins termination when quiescent), helpQuiesce, and indirectly
 631      * others including tryCompensate. Method quiescent() is
 632      * used in all of these contexts. It provides checks that all
 633      * workers are idle and there are no submissions that they could
 634      * poll if they were not idle, retrying on inconsistent reads of
 635      * queues and using the runState seqLock to retry on queue array
 636      * updates.  (It also reports quiescence if the pool is
 637      * terminating.) A true report means only that there was a moment
 638      * at which quiescence held.  False negatives are inevitable (for
 639      * example when queues indices lag updates, as described above),
 640      * which is accommodated when (tentatively) idle by scanning for
 641      * work etc, and then re-invoking. This includes cases in which
 642      * the final unparked thread (in awaitWork) uses quiescent()
 643      * to check for tasks that could have been added during a race
 644      * window that would not be accompanied by a signal, in which case
 645      * re-activating itself (or any other worker) to rescan. Method
 646      * helpQuiesce acts similarly but cannot rely on ctl counts to
 647      * determine that all workers are inactive because the caller and
 648      * any others executing helpQuiesce are not included in counts.
 649      *
 650      * Termination. A call to shutdownNow invokes tryTerminate to
 651      * atomically set a runState mode bit.  However, the process of
 652      * termination is intrinsically non-atomic. The calling thread, as
 653      * well as other workers thereafter terminating help cancel queued
 654      * tasks and interrupt other workers. These actions race with
 655      * unterminated workers.  By default, workers check for
 656      * termination only when accessing pool state.  This may take a
 657      * while but suffices for structured computational tasks.  But not
 658      * necessarily for others. Class InterruptibleTask (see below)
 659      * further arranges runState checks before executing task bodies,
 660      * and ensures interrupts while terminating. Even so, there are no
 661      * guarantees after an abrupt shutdown that remaining tasks
 662      * complete normally or exceptionally or are cancelled.
 663      * Termination may fail to complete if running tasks ignore both
 664      * task status and interrupts and/or produce more tasks after
 665      * others that could cancel them have exited.
 666      *
 667      * Trimming workers. To release resources after periods of lack of
 668      * use, a worker starting to wait when the pool is quiescent will
 669      * time out and terminate if the pool has remained quiescent for
 670      * period given by field keepAlive (default 60sec), which applies
 671      * to the first timeout of a fully populated pool. Subsequent (or
 672      * other) cases use delays such that, if still quiescent, all will
 673      * be released before one additional keepAlive unit elapses.
 674      *
 675      * Joining Tasks
 676      * =============
 677      *
 678      * The "Join" part of ForkJoinPools consists of a set of
 679      * mechanisms that sometimes or always (depending on the kind of
 680      * task) avoid context switching or adding worker threads when one
 681      * task would otherwise be blocked waiting for completion of
 682      * another, basically, just by running that task or one of its
 683      * subtasks if not already taken. These mechanics are disabled for
 684      * InterruptibleTasks, that guarantee that callers do not execute
 685      * submitted tasks.
 686      *
 687      * The basic structure of joining is an extended spin/block scheme
 688      * in which workers check for task completions status between
 689      * steps to find other work, until relevant pool state stabilizes
 690      * enough to believe that no such tasks are available, at which
 691      * point blocking. This is usually a good choice of when to block
 692      * that would otherwise be harder to approximate.
 693      *
 694      * These forms of helping may increase stack space usage, but that
 695      * space is bounded in tree/dag structured procedurally parallel
 696      * designs to be no more than that if a task were executed only by
 697      * the joining thread. This is arranged by associated task
 698      * subclasses that also help detect and control the ways in which
 699      * this may occur.
 700      *
 701      * Normally, the first option when joining a task that is not done
 702      * is to try to take it from the local queue and run it. Method
 703      * tryRemoveAndExec tries to do so.  For tasks with any form of
 704      * subtasks that must be completed first, we try to locate these
 705      * subtasks and run them as well. This is easy when local, but
 706      * when stolen, steal-backs are restricted to the same rules as
 707      * stealing (polling), which requires additional bookkeeping and
 708      * scanning. This cost is still very much worthwhile because of
 709      * its impact on task scheduling and resource control.
 710      *
 711      * The two methods for finding and executing subtasks vary in
 712      * details.  The algorithm in helpJoin entails a form of "linear
 713      * helping".  Each worker records (in field "source") the index of
 714      * the internal queue from which it last stole a task. (Note:
 715      * because chains cannot include even-numbered external queues,
 716      * they are ignored, and 0 is an OK default.) The scan in method
 717      * helpJoin uses these markers to try to find a worker to help
 718      * (i.e., steal back a task from and execute it) that could make
 719      * progress toward completion of the actively joined task.  Thus,
 720      * the joiner executes a task that would be on its own local deque
 721      * if the to-be-joined task had not been stolen. This is a
 722      * conservative variant of the approach described in Wagner &
 723      * Calder "Leapfrogging: a portable technique for implementing
 724      * efficient futures" SIGPLAN Notices, 1993
 725      * (http://portal.acm.org/citation.cfm?id=155354). It differs
 726      * mainly in that we only record queues, not full dependency
 727      * links.  This requires a linear scan of the queues to locate
 728      * stealers, but isolates cost to when it is needed, rather than
 729      * adding to per-task overhead.  For CountedCompleters, the
 730      * analogous method helpComplete doesn't need stealer-tracking,
 731      * but requires a similar (but simpler) check of completion
 732      * chains.
 733      *
 734      * In either case, searches can fail to locate stealers when
 735      * stalls delay recording sources or issuing subtasks. We avoid
 736      * some of these cases by using snapshotted values of ctl as a
 737      * check that the numbers of workers are not changing, along with
 738      * rescans to deal with contention and stalls.  But even when
 739      * accurately identified, stealers might not ever produce a task
 740      * that the joiner can in turn help with.
 741      *
 742      * Related method helpAsyncBlocker does not directly rely on
 743      * subtask structure, but instead avoids or postpones blocking of
 744      * tagged tasks (CompletableFuture.AsynchronousCompletionTask) by
 745      * executing other asyncs that can be processed in any order.
 746      * This is currently invoked only in non-join-based blocking
 747      * contexts from classes CompletableFuture and
 748      * SubmissionPublisher, that could be further generalized.
 749      *
 750      * When any of the above fail to avoid blocking, we rely on
 751      * "compensation" -- an indirect form of context switching that
 752      * either activates an existing worker to take the place of the
 753      * blocked one, or expands the number of workers.
 754      *
 755      * Compensation does not by default aim to keep exactly the target
 756      * parallelism number of unblocked threads running at any given
 757      * time. Some previous versions of this class employed immediate
 758      * compensations for any blocked join. However, in practice, the
 759      * vast majority of blockages are transient byproducts of GC and
 760      * other JVM or OS activities that are made worse by replacement
 761      * by causing longer-term oversubscription. These are inevitable
 762      * without (unobtainably) perfect information about whether worker
 763      * creation is actually necessary.  False alarms are common enough
 764      * to negatively impact performance, so compensation is by default
 765      * attempted only when it appears possible that the pool could
 766      * stall due to lack of any unblocked workers.  However, we allow
 767      * users to override defaults using the long form of the
 768      * ForkJoinPool constructor. The compensation mechanism may also
 769      * be bounded.  Bounds for the commonPool better enable JVMs to
 770      * cope with programming errors and abuse before running out of
 771      * resources to do so.
 772      *
 773      * The ManagedBlocker extension API can't use helping so relies
 774      * only on compensation in method awaitBlocker. This API was
 775      * designed to highlight the uncertainty of compensation decisions
 776      * by requiring implementation of method isReleasable to abort
 777      * compensation during attempts to obtain a stable snapshot. But
 778      * users now rely upon the fact that if isReleasable always
 779      * returns false, the API can be used to obtain precautionary
 780      * compensation, which is sometimes the only reasonable option
 781      * when running unknown code in tasks; which is now supported more
 782      * simply (see method beginCompensatedBlock).
 783      *
 784      * Common Pool
 785      * ===========
 786      *
 787      * The static common pool always exists after static
 788      * initialization.  Since it (or any other created pool) need
 789      * never be used, we minimize initial construction overhead and
 790      * footprint to the setup of about a dozen fields, although with
 791      * some System property parsing and security processing that takes
 792      * far longer than the actual construction when SecurityManagers
 793      * are used or properties are set. The common pool is
 794      * distinguished by having a null workerNamePrefix (which is an
 795      * odd convention, but avoids the need to decode status in factory
 796      * classes).  It also has PRESET_SIZE config set if parallelism
 797      * was configured by system property.
 798      *
 799      * When external threads use the common pool, they can perform
 800      * subtask processing (see helpComplete and related methods) upon
 801      * joins, unless they are submitted using ExecutorService
 802      * submission methods, which implicitly disallow this.  This
 803      * caller-helps policy makes it sensible to set common pool
 804      * parallelism level to one (or more) less than the total number
 805      * of available cores, or even zero for pure caller-runs. External
 806      * threads waiting for joins first check the common pool for their
 807      * task, which fails quickly if the caller did not fork to common
 808      * pool.
 809      *
 810      * Guarantees for common pool parallelism zero are limited to
 811      * tasks that are joined by their callers in a tree-structured
 812      * fashion or use CountedCompleters (as is true for jdk
 813      * parallelStreams). Support infiltrates several methods,
 814      * including those that retry helping steps until we are sure that
 815      * none apply if there are no workers.
 816      *
 817      * As a more appropriate default in managed environments, unless
 818      * overridden by system properties, we use workers of subclass
 819      * InnocuousForkJoinWorkerThread when there is a SecurityManager
 820      * present. These workers have no permissions set, do not belong
 821      * to any user-defined ThreadGroup, and clear all ThreadLocals
 822      * after executing any top-level task.  The associated mechanics
 823      * may be JVM-dependent and must access particular Thread class
 824      * fields to achieve this effect.
 825      *
 826      * InterruptibleTasks
 827      * ====================
 828      *
 829      * Regular ForkJoinTasks manage task cancellation (method cancel)
 830      * independently from the interrupt status of threads running
 831      * tasks.  Interrupts are issued internally only while
 832      * terminating, to wake up workers and cancel queued tasks.  By
 833      * default, interrupts are cleared only when necessary to ensure
 834      * that calls to LockSupport.park do not loop indefinitely (park
 835      * returns immediately if the current thread is interrupted).
 836      *
 837      * To comply with ExecutorService specs, we use subclasses of
 838      * abstract class InterruptibleTask for tasks that require
 839      * stronger interruption and cancellation guarantees.  External
 840      * submitters never run these tasks, even if in the common pool.
 841      * InterruptibleTasks include a "runner" field (implemented
 842      * similarly to FutureTask) to support cancel(true).  Upon pool
 843      * shutdown, runners are interrupted so they can cancel. Since
 844      * external joining callers never run these tasks, they must await
 845      * cancellation by others, which can occur along several different
 846      * paths.
 847      *
 848      * Across these APIs, rules for reporting exceptions for tasks
 849      * with results accessed via join() differ from those via get(),
 850      * which differ from those invoked using pool submit methods by
 851      * non-workers (which comply with Future.get() specs). Internal
 852      * usages of ForkJoinTasks ignore interrupt status when executing
 853      * or awaiting completion.  Otherwise, reporting task results or
 854      * exceptions is preferred to throwing InterruptedExecptions,
 855      * which are in turn preferred to timeouts. Similarly, completion
 856      * status is preferred to reporting cancellation.  Cancellation is
 857      * reported as an unchecked exception by join(), and by worker
 858      * calls to get(), but is otherwise wrapped in a (checked)
 859      * ExecutionException.
 860      *
 861      * Worker Threads cannot be VirtualThreads, as enforced by
 862      * requiring ForkJoinWorkerThreads in factories.  There are
 863      * several constructions relying on this.  However as of this
 864      * writing, virtual thread bodies are by default run as some form
 865      * of InterruptibleTask.
 866      *
 867      * Memory placement
 868      * ================
 869      *
 870      * Performance is very sensitive to placement of instances of
 871      * ForkJoinPool and WorkQueues and their queue arrays, as well as
 872      * the placement of their fields. Caches misses and contention due
 873      * to false-sharing have been observed to slow down some programs
 874      * by more than a factor of four. Effects may vary across initial
 875      * memory configuarations, applications, and different garbage
 876      * collectors and GC settings, so there is no perfect solution.
 877      * Too much isolation may generate more cache misses in common
 878      * cases (because some fields snd slots are usually read at the
 879      * same time). The @Contended annotation provides only rough
 880      * control (for good reason). Similarly for relying on fields
 881      * being placed in size-sorted declaration order.
 882      *
 883      * We isolate the ForkJoinPool.ctl field that otherwise causes the
 884      * most false-sharing misses with respect to other fields. Also,
 885      * ForkJoinPool fields are ordered such that fields less prone to
 886      * contention effects are first, offsetting those that otherwise
 887      * would be, while also reducing total footprint vs using
 888      * multiple @Contended regions, which tends to slow down
 889      * less-contended applications. For class WorkQueue, an
 890      * embedded @Contended region segregates fields most heavily
 891      * updated by owners from those most commonly read by stealers or
 892      * other management.  Initial sizing and resizing of WorkQueue
 893      * arrays is an even more delicate tradeoff because the best
 894      * strategy systematically varies across garbage collectors. Small
 895      * arrays are better for locality and reduce GC scan time, but
 896      * large arrays reduce both direct false-sharing and indirect
 897      * cases due to GC bookkeeping (cardmarks etc), and reduce the
 898      * number of resizes, which are not especially fast because they
 899      * require atomic transfers.  Currently, arrays are initialized to
 900      * be fairly small.  (Maintenance note: any changes in fields,
 901      * queues, or their uses, or JVM layout policies, must be
 902      * accompanied by re-evaluation of these placement and sizing
 903      * decisions.)
 904      *
 905      * Style notes
 906      * ===========
 907      *
 908      * Memory ordering relies mainly on atomic operations (CAS,
 909      * getAndSet, getAndAdd) along with moded accesses. These use
 910      * jdk-internal Unsafe for atomics and special memory modes,
 911      * rather than VarHandles, to avoid initialization dependencies in
 912      * other jdk components that require early parallelism.  This can
 913      * be awkward and ugly, but also reflects the need to control
 914      * outcomes across the unusual cases that arise in very racy code
 915      * with very few invariants. All atomic task slot updates use
 916      * Unsafe operations requiring offset positions, not indices, as
 917      * computed by method slotOffset. All fields are read into locals
 918      * before use, and null-checked if they are references, even if
 919      * they can never be null under current usages. Usually,
 920      * computations (held in local variables) are defined as soon as
 921      * logically enabled, sometimes to convince compilers that they
 922      * may be performed despite memory ordering constraints.  Array
 923      * accesses using masked indices include checks (that are always
 924      * true) that the array length is non-zero to avoid compilers
 925      * inserting more expensive traps.  This is usually done in a
 926      * "C"-like style of listing declarations at the heads of methods
 927      * or blocks, and using inline assignments on first encounter.
 928      * Nearly all explicit checks lead to bypass/return, not exception
 929      * throws, because they may legitimately arise during shutdown. A
 930      * few unusual loop constructions encourage (with varying
 931      * effectiveness) JVMs about where (not) to place safepoints.
 932      *
 933      * There is a lot of representation-level coupling among classes
 934      * ForkJoinPool, ForkJoinWorkerThread, and ForkJoinTask.  The
 935      * fields of WorkQueue maintain data structures managed by
 936      * ForkJoinPool, so are directly accessed.  There is little point
 937      * trying to reduce this, since any associated future changes in
 938      * representations will need to be accompanied by algorithmic
 939      * changes anyway. Several methods intrinsically sprawl because
 940      * they must accumulate sets of consistent reads of fields held in
 941      * local variables. Some others are artificially broken up to
 942      * reduce producer/consumer imbalances due to dynamic compilation.
 943      * There are also other coding oddities (including several
 944      * unnecessary-looking hoisted null checks) that help some methods
 945      * perform reasonably even when interpreted (not compiled).
 946      *
 947      * The order of declarations in this file is (with a few exceptions):
 948      * (1) Static configuration constants
 949      * (2) Static utility functions
 950      * (3) Nested (static) classes
 951      * (4) Fields, along with constants used when unpacking some of them
 952      * (5) Internal control methods
 953      * (6) Callbacks and other support for ForkJoinTask methods
 954      * (7) Exported methods
 955      * (8) Static block initializing statics in minimally dependent order
 956      *
 957      * Revision notes
 958      * ==============
 959      *
 960      * The main sources of differences from previous version are:
 961      *
 962      * * New abstract class ForkJoinTask.InterruptibleTask ensures
 963      *   handling of tasks submitted under the ExecutorService
 964      *   API are consistent with specs.
 965      * * Method quiescent() replaces previous quiescence-related
 966      *   checks, relying on versioning and sequence locking instead
 967      *   of ReentrantLock.
 968      * * Termination processing now ensures that internal data
 969      *   structures are maintained consistently enough while stopping
 970      *   to interrupt all workers and cancel all tasks. It also uses a
 971      *   CountDownLatch instead of a Condition for termination because
 972      *   of lock change.
 973      * * Many other changes to avoid performance regressions due
 974      *   to the above.
 975      */
 976 
 977     // static configuration constants
 978 
 979     /**
 980      * Default idle timeout value (in milliseconds) for idle threads
 981      * to park waiting for new work before terminating.
 982      */
 983     static final long DEFAULT_KEEPALIVE = 60_000L;
 984 
 985     /**
 986      * Undershoot tolerance for idle timeouts
 987      */
 988     static final long TIMEOUT_SLOP = 20L;
 989 
 990     /**
 991      * The default value for common pool maxSpares.  Overridable using
 992      * the "java.util.concurrent.ForkJoinPool.common.maximumSpares"
 993      * system property.  The default value is far in excess of normal
 994      * requirements, but also far short of maximum capacity and typical OS
 995      * thread limits, so allows JVMs to catch misuse/abuse before
 996      * running out of resources needed to do so.
 997      */
 998     static final int DEFAULT_COMMON_MAX_SPARES = 256;
 999 
1000     /**
1001      * Initial capacity of work-stealing queue array.  Must be a power
1002      * of two, at least 2. See above.
1003      */
1004     static final int INITIAL_QUEUE_CAPACITY = 1 << 6;
1005 
1006     // conversions among short, int, long
1007     static final int  SMASK           = 0xffff;      // (unsigned) short bits
1008     static final long LMASK           = 0xffffffffL; // lower 32 bits of long
1009     static final long UMASK           = ~LMASK;      // upper 32 bits
1010 
1011     // masks and sentinels for queue indices
1012     static final int MAX_CAP          = 0x7fff;   // max # workers
1013     static final int EXTERNAL_ID_MASK = 0x3ffe;   // max external queue id
1014     static final int INVALID_ID       = 0x4000;   // unused external queue id
1015 
1016     // pool.runState bits
1017     static final int STOP             = 1 <<  0;   // terminating
1018     static final int SHUTDOWN         = 1 <<  1;   // terminate when quiescent
1019     static final int TERMINATED       = 1 <<  2;   // only set if STOP also set
1020     static final int RS_LOCK          = 1 <<  3;   // lowest seqlock bit
1021 
1022     // spin/sleep limits for runState locking and elsewhere
1023     static final int SPIN_WAITS       = 1 <<  7;   // max calls to onSpinWait
1024     static final int MIN_SLEEP        = 1 << 10;   // approx 1 usec as nanos
1025     static final int MAX_SLEEP        = 1 << 20;   // approx 1 sec  as nanos
1026 
1027     // {pool, workQueue} config bits
1028     static final int FIFO             = 1 << 0;   // fifo queue or access mode
1029     static final int CLEAR_TLS        = 1 << 1;   // set for Innocuous workers
1030     static final int PRESET_SIZE      = 1 << 2;   // size was set by property
1031 
1032     // source history window packing used in scan() and runWorker()
1033     static final long RESCAN          = 1L << 63; // must be negative
1034     static final long HMASK           = ((((long)SMASK) << 32) |
1035                                          (((long)SMASK) << 16)); // history bits
1036     static final long NO_HISTORY      = ((((long)INVALID_ID) << 32) | // no 3rd
1037                                          (((long)INVALID_ID) << 16)); // no 2nd
1038 
1039     // others
1040     static final int DEREGISTERED     = 1 << 31;  // worker terminating
1041     static final int UNCOMPENSATE     = 1 << 16;  // tryCompensate return
1042     static final int IDLE             = 1 << 16;  // phase seqlock/version count
1043 
1044     /*
1045      * Bits and masks for ctl and bounds are packed with 4 16 bit subfields:
1046      * RC: Number of released (unqueued) workers
1047      * TC: Number of total workers
1048      * SS: version count and status of top waiting thread
1049      * ID: poolIndex of top of Treiber stack of waiters
1050      *
1051      * When convenient, we can extract the lower 32 stack top bits
1052      * (including version bits) as sp=(int)ctl. When sp is non-zero,
1053      * there are waiting workers.  Count fields may be transiently
1054      * negative during termination because of out-of-order updates.
1055      * To deal with this, we use casts in and out of "short" and/or
1056      * signed shifts to maintain signedness. Because it occupies
1057      * uppermost bits, we can add one release count using getAndAdd of
1058      * RC_UNIT, rather than CAS, when returning from a blocked join.
1059      * Other updates of multiple subfields require CAS.
1060      */
1061 
1062     // Release counts
1063     static final int  RC_SHIFT = 48;
1064     static final long RC_UNIT  = 0x0001L << RC_SHIFT;
1065     static final long RC_MASK  = 0xffffL << RC_SHIFT;
1066     // Total counts
1067     static final int  TC_SHIFT = 32;
1068     static final long TC_UNIT  = 0x0001L << TC_SHIFT;
1069     static final long TC_MASK  = 0xffffL << TC_SHIFT;
1070 
1071     /*
1072      * All atomic operations on task arrays (queues) use Unsafe
1073      * operations that take array offsets versus indices, based on
1074      * array base and shift constants established during static
1075      * initialization.
1076      */
1077     static final long ABASE;
1078     static final int  ASHIFT;
1079 
1080     // Static utilities
1081 
1082     /**
1083      * Returns the array offset corresponding to the given index for
1084      * Unsafe task queue operations
1085      */
1086     static long slotOffset(int index) {
1087         return ((long)index << ASHIFT) + ABASE;
1088     }
1089 
1090     /**
1091      * If there is a security manager, makes sure caller has
1092      * permission to modify threads.
1093      */
1094     @SuppressWarnings("removal")
1095     private static void checkPermission() {
1096         SecurityManager security; RuntimePermission perm;
1097         if ((security = System.getSecurityManager()) != null) {
1098             if ((perm = modifyThreadPermission) == null)
1099                 modifyThreadPermission = perm = // races OK
1100                     new RuntimePermission("modifyThread");
1101             security.checkPermission(perm);
1102         }
1103     }
1104 
1105     // Nested classes
1106 
1107     /**
1108      * Factory for creating new {@link ForkJoinWorkerThread}s.
1109      * A {@code ForkJoinWorkerThreadFactory} must be defined and used
1110      * for {@code ForkJoinWorkerThread} subclasses that extend base
1111      * functionality or initialize threads with different contexts.
1112      */
1113     public static interface ForkJoinWorkerThreadFactory {
1114         /**
1115          * Returns a new worker thread operating in the given pool.
1116          * Returning null or throwing an exception may result in tasks
1117          * never being executed.  If this method throws an exception,
1118          * it is relayed to the caller of the method (for example
1119          * {@code execute}) causing attempted thread creation. If this
1120          * method returns null or throws an exception, it is not
1121          * retried until the next attempted creation (for example
1122          * another call to {@code execute}).
1123          *
1124          * @param pool the pool this thread works in
1125          * @return the new worker thread, or {@code null} if the request
1126          *         to create a thread is rejected
1127          * @throws NullPointerException if the pool is null
1128          */
1129         public ForkJoinWorkerThread newThread(ForkJoinPool pool);
1130     }
1131 
1132     /**
1133      * Default ForkJoinWorkerThreadFactory implementation; creates a
1134      * new ForkJoinWorkerThread using the system class loader as the
1135      * thread context class loader.
1136      */
1137     static final class DefaultForkJoinWorkerThreadFactory
1138         implements ForkJoinWorkerThreadFactory {
1139         public final ForkJoinWorkerThread newThread(ForkJoinPool pool) {
1140             boolean isCommon = (pool.workerNamePrefix == null);
1141             @SuppressWarnings("removal")
1142             SecurityManager sm = System.getSecurityManager();
1143             if (sm == null)
1144                 return new ForkJoinWorkerThread(null, pool, true, false);
1145             else if (isCommon)
1146                 return newCommonWithACC(pool);
1147             else
1148                 return newRegularWithACC(pool);
1149         }
1150 
1151         /*
1152          * Create and use static AccessControlContexts only if there
1153          * is a SecurityManager. (These can be removed if/when
1154          * SecurityManagers are removed from platform.) The ACCs are
1155          * immutable and equivalent even when racily initialized, so
1156          * they don't require locking, although with the chance of
1157          * needlessly duplicate construction.
1158          */
1159         @SuppressWarnings("removal")
1160         static volatile AccessControlContext regularACC, commonACC;
1161 
1162         @SuppressWarnings("removal")
1163         static ForkJoinWorkerThread newRegularWithACC(ForkJoinPool pool) {
1164             AccessControlContext acc = regularACC;
1165             if (acc == null) {
1166                 Permissions ps = new Permissions();
1167                 ps.add(new RuntimePermission("getClassLoader"));
1168                 ps.add(new RuntimePermission("setContextClassLoader"));
1169                 regularACC = acc =
1170                     new AccessControlContext(new ProtectionDomain[] {
1171                             new ProtectionDomain(null, ps) });
1172             }
1173             return AccessController.doPrivileged(
1174                 new PrivilegedAction<>() {
1175                     public ForkJoinWorkerThread run() {
1176                         return new ForkJoinWorkerThread(null, pool, true, false);
1177                     }}, acc);
1178         }
1179 
1180         @SuppressWarnings("removal")
1181         static ForkJoinWorkerThread newCommonWithACC(ForkJoinPool pool) {
1182             AccessControlContext acc = commonACC;
1183             if (acc == null) {
1184                 Permissions ps = new Permissions();
1185                 ps.add(new RuntimePermission("getClassLoader"));
1186                 ps.add(new RuntimePermission("setContextClassLoader"));
1187                 ps.add(new RuntimePermission("modifyThread"));
1188                 ps.add(new RuntimePermission("enableContextClassLoaderOverride"));
1189                 ps.add(new RuntimePermission("modifyThreadGroup"));
1190                 commonACC = acc =
1191                     new AccessControlContext(new ProtectionDomain[] {
1192                             new ProtectionDomain(null, ps) });
1193             }
1194             return AccessController.doPrivileged(
1195                 new PrivilegedAction<>() {
1196                     public ForkJoinWorkerThread run() {
1197                         return new ForkJoinWorkerThread.
1198                             InnocuousForkJoinWorkerThread(pool);
1199                     }}, acc);
1200         }
1201     }
1202 
1203     /**
1204      * Queues supporting work-stealing as well as external task
1205      * submission. See above for descriptions and algorithms.
1206      */
1207     static final class WorkQueue {
1208         // fields declared in order of their likely layout on most VMs
1209         final ForkJoinWorkerThread owner; // null if shared
1210         ForkJoinTask<?>[] array;   // the queued tasks; power of 2 size
1211         int base;                  // index of next slot for poll
1212         final int config;          // mode bits
1213 
1214         // fields otherwise causing more unnecessary false-sharing cache misses
1215         @jdk.internal.vm.annotation.Contended("w")
1216         int top;                   // index of next slot for push
1217         @jdk.internal.vm.annotation.Contended("w")
1218         volatile int phase;        // versioned active status
1219         @jdk.internal.vm.annotation.Contended("w")
1220         int stackPred;             // pool stack (ctl) predecessor link
1221         @jdk.internal.vm.annotation.Contended("w")
1222         volatile int source;       // source queue id (or DEREGISTERED)
1223         @jdk.internal.vm.annotation.Contended("w")
1224         int nsteals;               // number of steals from other queues
1225         @jdk.internal.vm.annotation.Contended("w")
1226         volatile int parking;      // nonzero if parked in awaitWork
1227 
1228         // Support for atomic operations
1229         private static final Unsafe U;
1230         private static final long PHASE;
1231         private static final long BASE;
1232         private static final long TOP;
1233         private static final long SOURCE;
1234         private static final long ARRAY;
1235 
1236         final void updateBase(int v) {
1237             U.putIntVolatile(this, BASE, v);
1238         }
1239         final void updateTop(int v) {
1240             U.putIntOpaque(this, TOP, v);
1241         }
1242         final void forgetSource() {
1243             U.putIntOpaque(this, SOURCE, 0);
1244         }
1245         final void updateArray(ForkJoinTask<?>[] a) {
1246             U.getAndSetReference(this, ARRAY, a);
1247         }
1248         final void unlockPhase() {
1249             U.getAndAddInt(this, PHASE, IDLE);
1250         }
1251         final boolean tryLockPhase() {    // seqlock acquire
1252             int p;
1253             return (((p = phase) & IDLE) != 0 &&
1254                     U.compareAndSetInt(this, PHASE, p, p + IDLE));
1255         }
1256 
1257         /**
1258          * Constructor. For internal queues, most fields are initialized
1259          * upon thread start in pool.registerWorker.
1260          */
1261         WorkQueue(ForkJoinWorkerThread owner, int id, int cfg,
1262                   boolean clearThreadLocals) {
1263             if (clearThreadLocals)
1264                 cfg |= CLEAR_TLS;
1265             this.config = cfg;
1266             top = base = 1;
1267             this.phase = id;
1268             this.owner = owner;
1269         }
1270 
1271         /**
1272          * Returns an exportable index (used by ForkJoinWorkerThread).
1273          */
1274         final int getPoolIndex() {
1275             return (phase & 0xffff) >>> 1; // ignore odd/even tag bit
1276         }
1277 
1278         /**
1279          * Returns the approximate number of tasks in the queue.
1280          */
1281         final int queueSize() {
1282             int unused = phase;             // for ordering effect
1283             return Math.max(top - base, 0); // ignore transient negative
1284         }
1285 
1286         /**
1287          * Pushes a task. Called only by owner or if already locked
1288          *
1289          * @param task the task. Caller must ensure non-null.
1290          * @param pool the pool to signal if was previously empty, else null
1291          * @param internal if caller owns this queue
1292          * @throws RejectedExecutionException if array could not be resized
1293          */
1294         final void push(ForkJoinTask<?> task, ForkJoinPool pool,
1295                         boolean internal) {
1296             int s = top, b = base, cap, m, p, room, newCap; ForkJoinTask<?>[] a;
1297             if ((a = array) == null || (cap = a.length) <= 0 ||
1298                 (room = (m = cap - 1) - (s - b)) < 0) { // could not resize
1299                 if (!internal)
1300                     unlockPhase();
1301                 throw new RejectedExecutionException("Queue capacity exceeded");
1302             }
1303             top = s + 1;
1304             long pos = slotOffset(p = m & s);
1305             if (!internal)
1306                 U.putReference(a, pos, task);         // inside lock
1307             else
1308                 U.getAndSetReference(a, pos, task);   // fully fenced
1309             if (room == 0 && (newCap = cap << 1) > 0) {
1310                 ForkJoinTask<?>[] newArray = null;
1311                 try {                                 // resize for next time
1312                     newArray = new ForkJoinTask<?>[newCap];
1313                 } catch (OutOfMemoryError ex) {
1314                 }
1315                 if (newArray != null) {               // else throw on next push
1316                     int newMask = newCap - 1;         // poll old, push to new
1317                     for (int k = s, j = cap; j > 0; --j, --k) {
1318                         ForkJoinTask<?> u;
1319                         if ((u = (ForkJoinTask<?>)U.getAndSetReference(
1320                                  a, slotOffset(k & m), null)) == null)
1321                             break;                    // lost to pollers
1322                         newArray[k & newMask] = u;
1323                     }
1324                     updateArray(newArray);            // fully fenced
1325                 }
1326                 a = null;                             // always signal
1327             }
1328             if (!internal)
1329                 unlockPhase();
1330             if ((a == null || a[m & (s - 1)] == null) && pool != null)
1331                 pool.signalWork(a, p);
1332         }
1333 
1334         /**
1335          * Takes next task, if one exists, in order specified by mode,
1336          * so acts as either local-pop or local-poll. Called only by owner.
1337          * @param fifo nonzero if FIFO mode
1338          */
1339         private ForkJoinTask<?> nextLocalTask(int fifo) {
1340             ForkJoinTask<?> t = null;
1341             ForkJoinTask<?>[] a = array;
1342             int b = base, p = top, cap;
1343             if (a != null && (cap = a.length) > 0) {
1344                 for (int m = cap - 1, s, nb; p - b > 0; ) {
1345                     if (fifo == 0 || (nb = b + 1) == p) {
1346                         if ((t = (ForkJoinTask<?>)U.getAndSetReference(
1347                                  a, slotOffset(m & (s = p - 1)), null)) != null)
1348                             updateTop(s);       // else lost race for only task
1349                         break;
1350                     }
1351                     if ((t = (ForkJoinTask<?>)U.getAndSetReference(
1352                              a, slotOffset(m & b), null)) != null) {
1353                         updateBase(nb);
1354                         break;
1355                     }
1356                     while (b == (b = base)) {
1357                         U.loadFence();
1358                         Thread.onSpinWait();    // spin to reduce memory traffic
1359                     }
1360                 }
1361             }
1362             return t;
1363         }
1364 
1365         /**
1366          * Takes next task, if one exists, using configured mode.
1367          * (Always internal, never called for Common pool.)
1368          */
1369         final ForkJoinTask<?> nextLocalTask() {
1370             return nextLocalTask(config & FIFO);
1371         }
1372 
1373         /**
1374          * Pops the given task only if it is at the current top.
1375          * @param task the task. Caller must ensure non-null.
1376          * @param internal if caller owns this queue
1377          */
1378         final boolean tryUnpush(ForkJoinTask<?> task, boolean internal) {
1379             boolean taken = false;
1380             ForkJoinTask<?>[] a = array;
1381             int p = top, s = p - 1, cap, k;
1382             if (a != null && (cap = a.length) > 0 &&
1383                 a[k = (cap - 1) & s] == task &&
1384                 (internal || tryLockPhase())) {
1385                 if (top == p &&
1386                     U.compareAndSetReference(a, slotOffset(k), task, null)) {
1387                     taken = true;
1388                     updateTop(s);
1389                 }
1390                 if (!internal)
1391                     unlockPhase();
1392             }
1393             return taken;
1394         }
1395 
1396         /**
1397          * Returns next task, if one exists, in order specified by mode.
1398          */
1399         final ForkJoinTask<?> peek() {
1400             ForkJoinTask<?>[] a = array;
1401             int b = base, cfg = config, p = top, cap;
1402             if (p != b && a != null && (cap = a.length) > 0) {
1403                 if ((cfg & FIFO) == 0)
1404                     return a[(cap - 1) & (p - 1)];
1405                 else { // skip over in-progress removals
1406                     ForkJoinTask<?> t;
1407                     for ( ; p - b > 0; ++b) {
1408                         if ((t = a[(cap - 1) & b]) != null)
1409                             return t;
1410                     }
1411                 }
1412             }
1413             return null;
1414         }
1415 
1416         /**
1417          * Polls for a task. Used only by non-owners.
1418          *
1419          * @param pool if nonnull, pool to signal if more tasks exist
1420          */
1421         final ForkJoinTask<?> poll(ForkJoinPool pool) {
1422             for (;;) {
1423                 ForkJoinTask<?>[] a = array;
1424                 int b = base, cap, k;
1425                 if (a == null || (cap = a.length) <= 0)
1426                     break;
1427                 ForkJoinTask<?> t = a[k = b & (cap - 1)];
1428                 U.loadFence();
1429                 if (base == b) {
1430                     Object o;
1431                     int nb = b + 1, nk = nb & (cap - 1);
1432                     if (t == null)
1433                         o = a[k];
1434                     else if (t == (o = U.compareAndExchangeReference(
1435                                        a, slotOffset(k), t, null))) {
1436                         updateBase(nb);
1437                         if (a[nk] != null && pool != null)
1438                             pool.signalWork(a, nk); // propagate
1439                         return t;
1440                     }
1441                     if (o == null && a[nk] == null && array == a &&
1442                         (phase & (IDLE | 1)) != 0 && top - base <= 0)
1443                         break;                    // empty
1444                 }
1445             }
1446             return null;
1447         }
1448 
1449         /**
1450          * Tries to poll next task in FIFO order, failing without
1451          * retries on contention or stalls. Used only by topLevelExec
1452          * to repoll from the queue obtained from pool.scan.
1453          */
1454         private ForkJoinTask<?> tryPoll() {
1455             ForkJoinTask<?>[] a; int cap;
1456             if ((a = array) != null && (cap = a.length) > 0) {
1457                 for (int b = base, k;;) {  // loop only if inconsistent
1458                     ForkJoinTask<?> t = a[k = b & (cap - 1)];
1459                     U.loadFence();
1460                     if (b == (b = base)) {
1461                         Object o;
1462                         if (t == null)
1463                             o = a[k];
1464                         else if (t == (o = U.compareAndExchangeReference(
1465                                            a, slotOffset(k), t, null))) {
1466                             updateBase(b + 1);
1467                             return t;
1468                         }
1469                         if (o == null)
1470                             break;
1471                     }
1472                 }
1473             }
1474             return null;
1475         }
1476 
1477         // specialized execution methods
1478 
1479         /**
1480          * Runs the given (stolen) task if nonnull, as well as
1481          * remaining local tasks and/or others available from the
1482          * given queue, if any.
1483          */
1484         final void topLevelExec(ForkJoinTask<?> task, WorkQueue src, int srcId) {
1485             int cfg = config, fifo = cfg & FIFO, nstolen = nsteals + 1;
1486             if ((srcId & 1) != 0) // don't record external sources
1487                 source = srcId;
1488             if ((cfg & CLEAR_TLS) != 0)
1489                 ThreadLocalRandom.eraseThreadLocals(Thread.currentThread());
1490             while (task != null) {
1491                 task.doExec();
1492                 if ((task = nextLocalTask(fifo)) == null && src != null &&
1493                     (task = src.tryPoll()) != null)
1494                     ++nstolen;
1495             }
1496             nsteals = nstolen;
1497             forgetSource();
1498         }
1499 
1500         /**
1501          * Deep form of tryUnpush: Traverses from top and removes and
1502          * runs task if present.
1503          */
1504         final void tryRemoveAndExec(ForkJoinTask<?> task, boolean internal) {
1505             ForkJoinTask<?>[] a = array;
1506             int b = base, p = top, s = p - 1, d = p - b, cap;
1507             if (a != null && (cap = a.length) > 0) {
1508                 for (int m = cap - 1, i = s; d > 0; --i, --d) {
1509                     ForkJoinTask<?> t; int k; boolean taken;
1510                     if ((t = a[k = i & m]) == null)
1511                         break;
1512                     if (t == task) {
1513                         long pos = slotOffset(k);
1514                         if (!internal && !tryLockPhase())
1515                             break;                  // fail if locked
1516                         if (taken =
1517                             (top == p &&
1518                              U.compareAndSetReference(a, pos, task, null))) {
1519                             if (i == s)             // act as pop
1520                                 updateTop(s);
1521                             else if (i == base)     // act as poll
1522                                 updateBase(i + 1);
1523                             else {                  // swap with top
1524                                 U.putReferenceVolatile(
1525                                     a, pos, (ForkJoinTask<?>)
1526                                     U.getAndSetReference(
1527                                         a, slotOffset(s & m), null));
1528                                 updateTop(s);
1529                             }
1530                         }
1531                         if (!internal)
1532                             unlockPhase();
1533                         if (taken)
1534                             task.doExec();
1535                         break;
1536                     }
1537                 }
1538             }
1539         }
1540 
1541         /**
1542          * Tries to pop and run tasks within the target's computation
1543          * until done, not found, or limit exceeded.
1544          *
1545          * @param task root of computation
1546          * @param limit max runs, or zero for no limit
1547          * @return task status if known to be done
1548          */
1549         final int helpComplete(ForkJoinTask<?> task, boolean internal, int limit) {
1550             int status = 0;
1551             if (task != null) {
1552                 outer: for (;;) {
1553                     ForkJoinTask<?>[] a; ForkJoinTask<?> t; boolean taken;
1554                     int stat, p, s, cap, k;
1555                     if ((stat = task.status) < 0) {
1556                         status = stat;
1557                         break;
1558                     }
1559                     if ((a = array) == null || (cap = a.length) <= 0)
1560                         break;
1561                     if ((t = a[k = (cap - 1) & (s = (p = top) - 1)]) == null)
1562                         break;
1563                     if (!(t instanceof CountedCompleter))
1564                         break;
1565                     CountedCompleter<?> f = (CountedCompleter<?>)t;
1566                     for (int steps = cap;;) {       // bound path
1567                         if (f == task)
1568                             break;
1569                         if ((f = f.completer) == null || --steps == 0)
1570                             break outer;
1571                     }
1572                     if (!internal && !tryLockPhase())
1573                         break;
1574                     if (taken =
1575                         (top == p &&
1576                          U.compareAndSetReference(a, slotOffset(k), t, null)))
1577                         updateTop(s);
1578                     if (!internal)
1579                         unlockPhase();
1580                     if (!taken)
1581                         break;
1582                     t.doExec();
1583                     if (limit != 0 && --limit == 0)
1584                         break;
1585                 }
1586             }
1587             return status;
1588         }
1589 
1590         /**
1591          * Tries to poll and run AsynchronousCompletionTasks until
1592          * none found or blocker is released
1593          *
1594          * @param blocker the blocker
1595          */
1596         final void helpAsyncBlocker(ManagedBlocker blocker) {
1597             for (;;) {
1598                 ForkJoinTask<?>[] a; int b, cap, k;
1599                 if ((a = array) == null || (cap = a.length) <= 0)
1600                     break;
1601                 ForkJoinTask<?> t = a[k = (b = base) & (cap - 1)];
1602                 U.loadFence();
1603                 if (t == null) {
1604                     if (top - b <= 0)
1605                         break;
1606                 }
1607                 else if (!(t instanceof CompletableFuture
1608                            .AsynchronousCompletionTask))
1609                     break;
1610                 if (blocker != null && blocker.isReleasable())
1611                     break;
1612                 if (base == b && t != null &&
1613                     U.compareAndSetReference(a, slotOffset(k), t, null)) {
1614                     updateBase(b + 1);
1615                     t.doExec();
1616                 }
1617             }
1618         }
1619 
1620         // misc
1621 
1622         /**
1623          * Returns true if internal and not known to be blocked.
1624          */
1625         final boolean isApparentlyUnblocked() {
1626             Thread wt; Thread.State s;
1627             return ((wt = owner) != null && (phase & IDLE) != 0 &&
1628                     (s = wt.getState()) != Thread.State.BLOCKED &&
1629                     s != Thread.State.WAITING &&
1630                     s != Thread.State.TIMED_WAITING);
1631         }
1632 
1633         static {
1634             U = Unsafe.getUnsafe();
1635             Class<WorkQueue> klass = WorkQueue.class;
1636             PHASE = U.objectFieldOffset(klass, "phase");
1637             BASE = U.objectFieldOffset(klass, "base");
1638             TOP = U.objectFieldOffset(klass, "top");
1639             SOURCE = U.objectFieldOffset(klass, "source");
1640             ARRAY = U.objectFieldOffset(klass, "array");
1641         }
1642     }
1643 
1644     // static fields (initialized in static initializer below)
1645 
1646     /**
1647      * Creates a new ForkJoinWorkerThread. This factory is used unless
1648      * overridden in ForkJoinPool constructors.
1649      */
1650     public static final ForkJoinWorkerThreadFactory
1651         defaultForkJoinWorkerThreadFactory;
1652 
1653     /**
1654      * Common (static) pool. Non-null for public use unless a static
1655      * construction exception, but internal usages null-check on use
1656      * to paranoically avoid potential initialization circularities
1657      * as well as to simplify generated code.
1658      */
1659     static final ForkJoinPool common;
1660 
1661     /**
1662      * Sequence number for creating worker names
1663      */
1664     private static volatile int poolIds;
1665 
1666     /**
1667      * Permission required for callers of methods that may start or
1668      * kill threads. Lazily constructed.
1669      */
1670     static volatile RuntimePermission modifyThreadPermission;
1671 
1672     // fields declared in order of their likely layout on most VMs
1673     volatile CountDownLatch termination; // lazily constructed
1674     final Predicate<? super ForkJoinPool> saturate;
1675     final ForkJoinWorkerThreadFactory factory;
1676     final UncaughtExceptionHandler ueh;  // per-worker UEH
1677     final SharedThreadContainer container;
1678     final String workerNamePrefix;       // null for common pool
1679     WorkQueue[] queues;                  // main registry
1680     final long keepAlive;                // milliseconds before dropping if idle
1681     final long config;                   // static configuration bits
1682     volatile long stealCount;            // collects worker nsteals
1683     volatile long threadIds;             // for worker thread names
1684     volatile int runState;               // versioned, lockable
1685     @jdk.internal.vm.annotation.Contended("fjpctl") // segregate
1686     volatile long ctl;                   // main pool control
1687     @jdk.internal.vm.annotation.Contended("fjpctl") // colocate
1688     int parallelism;                     // target number of workers
1689 
1690     // Support for atomic operations
1691     private static final Unsafe U;
1692     private static final long CTL;
1693     private static final long RUNSTATE;
1694     private static final long PARALLELISM;
1695     private static final long THREADIDS;
1696     private static final long TERMINATION;
1697     private static final Object POOLIDS_BASE;
1698     private static final long POOLIDS;
1699 
1700     private boolean compareAndSetCtl(long c, long v) {
1701         return U.compareAndSetLong(this, CTL, c, v);
1702     }
1703     private long compareAndExchangeCtl(long c, long v) {
1704         return U.compareAndExchangeLong(this, CTL, c, v);
1705     }
1706     private long getAndAddCtl(long v) {
1707         return U.getAndAddLong(this, CTL, v);
1708     }
1709     private long incrementThreadIds() {
1710         return U.getAndAddLong(this, THREADIDS, 1L);
1711     }
1712     private static int getAndAddPoolIds(int x) {
1713         return U.getAndAddInt(POOLIDS_BASE, POOLIDS, x);
1714     }
1715     private int getAndSetParallelism(int v) {
1716         return U.getAndSetInt(this, PARALLELISM, v);
1717     }
1718     private int getParallelismOpaque() {
1719         return U.getIntOpaque(this, PARALLELISM);
1720     }
1721     private CountDownLatch cmpExTerminationSignal(CountDownLatch x) {
1722         return (CountDownLatch)
1723             U.compareAndExchangeReference(this, TERMINATION, null, x);
1724     }
1725 
1726     // runState operations
1727 
1728     private int getAndBitwiseOrRunState(int v) { // for status bits
1729         return U.getAndBitwiseOrInt(this, RUNSTATE, v);
1730     }
1731     private boolean casRunState(int c, int v) {
1732         return U.compareAndSetInt(this, RUNSTATE, c, v);
1733     }
1734     private void unlockRunState() {              // increment lock bit
1735         U.getAndAddInt(this, RUNSTATE, RS_LOCK);
1736     }
1737     private int lockRunState() {                // lock and return current state
1738         int s, u;                               // locked when RS_LOCK set
1739         if (((s = runState) & RS_LOCK) == 0 && casRunState(s, u = s + RS_LOCK))
1740             return u;
1741         else
1742             return spinLockRunState();
1743     }
1744     private int spinLockRunState() {            // spin/sleep
1745         for (int waits = 0, s, u;;) {
1746             if (((s = runState) & RS_LOCK) == 0) {
1747                 if (casRunState(s, u = s + RS_LOCK))
1748                     return u;
1749                 waits = 0;
1750             } else if (waits < SPIN_WAITS) {
1751                 ++waits;
1752                 Thread.onSpinWait();
1753             } else {
1754                 if (waits < MIN_SLEEP)
1755                     waits = MIN_SLEEP;
1756                 LockSupport.parkNanos(this, (long)waits);
1757                 if (waits < MAX_SLEEP)
1758                     waits <<= 1;
1759             }
1760         }
1761     }
1762 
1763     static boolean poolIsStopping(ForkJoinPool p) { // Used by ForkJoinTask
1764         return p != null && (p.runState & STOP) != 0;
1765     }
1766 
1767     // Creating, registering, and deregistering workers
1768 
1769     /**
1770      * Tries to construct and start one worker. Assumes that total
1771      * count has already been incremented as a reservation.  Invokes
1772      * deregisterWorker on any failure.
1773      *
1774      * @return true if successful
1775      */
1776     private boolean createWorker() {
1777         ForkJoinWorkerThreadFactory fac = factory;
1778         SharedThreadContainer ctr = container;
1779         Throwable ex = null;
1780         ForkJoinWorkerThread wt = null;
1781         try {
1782             if ((runState & STOP) == 0 &&  // avoid construction if terminating
1783                 fac != null && (wt = fac.newThread(this)) != null) {
1784                 if (ctr != null)
1785                     ctr.start(wt);
1786                 else
1787                     wt.start();
1788                 return true;
1789             }
1790         } catch (Throwable rex) {
1791             ex = rex;
1792         }
1793         deregisterWorker(wt, ex);
1794         return false;
1795     }
1796 
1797     /**
1798      * Provides a name for ForkJoinWorkerThread constructor.
1799      */
1800     final String nextWorkerThreadName() {
1801         String prefix = workerNamePrefix;
1802         long tid = incrementThreadIds() + 1L;
1803         if (prefix == null) // commonPool has no prefix
1804             prefix = "ForkJoinPool.commonPool-worker-";
1805         return prefix.concat(Long.toString(tid));
1806     }
1807 
1808     /**
1809      * Finishes initializing and records internal queue.
1810      *
1811      * @param w caller's WorkQueue
1812      */
1813     final void registerWorker(WorkQueue w) {
1814         if (w != null) {
1815             w.array = new ForkJoinTask<?>[INITIAL_QUEUE_CAPACITY];
1816             ThreadLocalRandom.localInit();
1817             int seed = w.stackPred = ThreadLocalRandom.getProbe();
1818             int phaseSeq = seed & ~((IDLE << 1) - 1); // initial phase tag
1819             int id = ((seed << 1) | 1) & SMASK; // base of linear-probe-like scan
1820             int stop = lockRunState() & STOP;
1821             try {
1822                 WorkQueue[] qs; int n;
1823                 if (stop == 0 && (qs = queues) != null && (n = qs.length) > 0) {
1824                     for (int k = n, m = n - 1;  ; id += 2) {
1825                         if (qs[id &= m] == null)
1826                             break;
1827                         if ((k -= 2) <= 0) {
1828                             id |= n;
1829                             break;
1830                         }
1831                     }
1832                     w.phase = id | phaseSeq;    // now publishable
1833                     if (id < n)
1834                         qs[id] = w;
1835                     else {                      // expand
1836                         int an = n << 1, am = an - 1;
1837                         WorkQueue[] as = new WorkQueue[an];
1838                         as[id & am] = w;
1839                         for (int j = 1; j < n; j += 2)
1840                             as[j] = qs[j];
1841                         for (int j = 0; j < n; j += 2) {
1842                             WorkQueue q;        // shared queues may move
1843                             if ((q = qs[j]) != null)
1844                                 as[q.phase & EXTERNAL_ID_MASK & am] = q;
1845                         }
1846                         U.storeFence();         // fill before publish
1847                         queues = as;
1848                     }
1849                 }
1850             } finally {
1851                 unlockRunState();
1852             }
1853         }
1854     }
1855 
1856     /**
1857      * Final callback from terminating worker, as well as upon failure
1858      * to construct or start a worker.  Removes record of worker from
1859      * array, and adjusts counts. If pool is shutting down, tries to
1860      * complete termination.
1861      *
1862      * @param wt the worker thread, or null if construction failed
1863      * @param ex the exception causing failure, or null if none
1864      */
1865     final void deregisterWorker(ForkJoinWorkerThread wt, Throwable ex) {
1866         WorkQueue w = null;
1867         int src = 0, phase = 0;
1868         boolean replaceable = false;
1869         if (wt != null && (w = wt.workQueue) != null) {
1870             phase = w.phase;
1871             if ((src = w.source) != DEREGISTERED) { // else trimmed on timeout
1872                 w.source = DEREGISTERED;
1873                 if (phase != 0) {         // else failed to start
1874                     replaceable = true;
1875                     if ((phase & IDLE) != 0)
1876                         reactivate(w);    // pool stopped before released
1877                 }
1878             }
1879         }
1880         long c = ctl;
1881         if (src != DEREGISTERED)          // decrement counts
1882             do {} while (c != (c = compareAndExchangeCtl(
1883                                    c, ((RC_MASK & (c - RC_UNIT)) |
1884                                        (TC_MASK & (c - TC_UNIT)) |
1885                                        (LMASK & c)))));
1886         else if ((int)c != 0)
1887             replaceable = true;           // signal below to cascade timeouts
1888         if (w != null) {                  // cancel remaining tasks
1889             for (ForkJoinTask<?> t; (t = w.nextLocalTask()) != null; ) {
1890                 try {
1891                     t.cancel(false);
1892                 } catch (Throwable ignore) {
1893                 }
1894             }
1895         }
1896         if ((tryTerminate(false, false) & STOP) == 0 && w != null) {
1897             WorkQueue[] qs; int n, i;     // remove index unless terminating
1898             long ns = w.nsteals & 0xffffffffL;
1899             int stop = lockRunState() & STOP;
1900             if (stop == 0 && (qs = queues) != null && (n = qs.length) > 0 &&
1901                 qs[i = phase & SMASK & (n - 1)] == w) {
1902                 qs[i] = null;
1903                 stealCount += ns;         // accumulate steals
1904             }
1905             unlockRunState();
1906         }
1907         if ((runState & STOP) == 0 && replaceable)
1908             signalWork(null, 0); // may replace unless trimmed or uninitialized
1909         if (ex != null)
1910             ForkJoinTask.rethrow(ex);
1911     }
1912 
1913     /**
1914      * Releases an idle worker, or creates one if not enough exist,
1915      * returning on contention if a signal task is already taken.
1916      *
1917      * @param a if nonnull, a task array holding task signalled
1918      * @param k index of task in array
1919      */
1920     final void signalWork(ForkJoinTask<?>[] a, int k) {
1921         int pc = parallelism;
1922         for (long c = ctl;;) {
1923             WorkQueue[] qs = queues;
1924             long ac = (c + RC_UNIT) & RC_MASK, nc;
1925             int sp = (int)c, i = sp & SMASK;
1926             if (qs == null || qs.length <= i)
1927                 break;
1928             WorkQueue w = qs[i], v = null;
1929             if (sp == 0) {
1930                 if ((short)(c >>> TC_SHIFT) >= pc)
1931                     break;
1932                 nc = ((c + TC_UNIT) & TC_MASK);
1933             }
1934             else if ((short)(c >>> RC_SHIFT) >= pc || (v = w) == null)
1935                 break;
1936             else
1937                 nc = (v.stackPred & LMASK) | (c & TC_MASK);
1938             if (c == (c = compareAndExchangeCtl(c, nc | ac))) {
1939                 if (v == null)
1940                     createWorker();
1941                 else {
1942                     v.phase = sp;
1943                     if (v.parking != 0)
1944                         U.unpark(v.owner);
1945                 }
1946                 break;
1947             }
1948             if (a != null && k >= 0 && k < a.length && a[k] == null)
1949                 break;
1950         }
1951     }
1952 
1953     /**
1954      * Reactivates the given worker, and possibly others if not top of
1955      * ctl stack. Called only during shutdown to ensure release on
1956      * termination.
1957      */
1958     private void reactivate(WorkQueue w) {
1959         for (long c = ctl;;) {
1960             WorkQueue[] qs; WorkQueue v; int sp, i;
1961             if ((qs = queues) == null || (sp = (int)c) == 0 ||
1962                 qs.length <= (i = sp & SMASK) || (v = qs[i]) == null ||
1963                 (v != w && w != null && (w.phase & IDLE) == 0))
1964                 break;
1965             if (c == (c = compareAndExchangeCtl(
1966                           c, ((UMASK & (c + RC_UNIT)) | (c & TC_MASK) |
1967                               (v.stackPred & LMASK))))) {
1968                 v.phase = sp;
1969                 if (v == w)
1970                     break;
1971                 if (v.parking != 0)
1972                     U.unpark(v.owner);
1973             }
1974         }
1975     }
1976 
1977     /**
1978      * Internal version of isQuiescent and related functionality.
1979      * @return true if terminating or all workers are inactive and
1980      * submission queues are empty and unlocked; if so, setting STOP
1981      * if shutdown is enabled
1982      */
1983     private boolean quiescent() {
1984         outer: for (;;) {
1985             long phaseSum = 0L;
1986             boolean swept = false;
1987             for (int e, prevRunState = 0; ; prevRunState = e) {
1988                 long c = ctl;
1989                 if (((e = runState) & STOP) != 0)
1990                     return true;                          // terminating
1991                 else if ((c & RC_MASK) > 0L)
1992                     return false;                         // at least one active
1993                 else if (!swept || e != prevRunState || (e & RS_LOCK) != 0) {
1994                     long sum = c;
1995                     WorkQueue[] qs = queues; WorkQueue q;
1996                     int n = (qs == null) ? 0 : qs.length;
1997                     for (int i = 0; i < n; ++i) {         // scan queues
1998                         if ((q = qs[i]) != null) {
1999                             int p = q.phase, s = q.top, b = q.base;
2000                             sum += (p & 0xffffffffL) | ((long)b << 32);
2001                             if ((p & IDLE) == 0 || s - b > 0) {
2002                                 if ((i & 1) == 0 && compareAndSetCtl(c, c))
2003                                     signalWork(null, 0);  // ensure live
2004                                 return false;
2005                             }
2006                         }
2007                     }
2008                     swept = (phaseSum == (phaseSum = sum));
2009                 }
2010                 else if ((e & SHUTDOWN) == 0)
2011                     return true;
2012                 else if (compareAndSetCtl(c, c) && casRunState(e, e | STOP)) {
2013                     interruptAll();                       // confirmed
2014                     return true;                          // enable termination
2015                 }
2016                 else
2017                     break;                                // restart
2018             }
2019         }
2020     }
2021 
2022     /**
2023      * Top-level runloop for workers, called by ForkJoinWorkerThread.run.
2024      * See above for explanation.
2025      *
2026      * @param w caller's WorkQueue (may be null on failed initialization)
2027      */
2028     final void runWorker(WorkQueue w) {
2029         if (w != null) {
2030             int phase = w.phase, r = w.stackPred; // seed from registerWorker
2031             long window = (long)((r >>> 16) & SMASK) | NO_HISTORY;
2032             do {
2033                 r ^= r << 13; r ^= r >>> 17; r ^= r << 5; // xorshift
2034             } while ((runState & STOP) == 0 &&
2035                      (((window = scan(w, window, r)) < 0L ||
2036                        ((phase = awaitWork(w, phase)) & IDLE) == 0)));
2037         }
2038     }
2039 
2040     /**
2041      * Scans for and if found executes top-level tasks: Tries to poll
2042      * each queue starting at initial index with random stride,
2043      * returning next scan window and retry indicator.
2044      *
2045      * @param w caller's WorkQueue
2046      * @param window up to three queue indices
2047      * @param r random seed
2048      * @return the next window to use, with RESCAN set for rescan
2049      */
2050     private long scan(WorkQueue w, long window, int r) {
2051         WorkQueue[] qs = queues;
2052         int n = (qs == null) ? 0 : qs.length, step = (r << 1) | 1;
2053         long next = window & ~RESCAN;
2054         outer: for (int i = (short)window, l = n; l > 0; --l, i += step) {
2055             int j, cap; WorkQueue q; ForkJoinTask<?>[] a;
2056             if ((q = qs[j = i & SMASK & (n - 1)]) != null &&
2057                 (a = q.array) != null && (cap = a.length) > 0) {
2058                 for (int b = q.base;;) {
2059                     int nb = b + 1, nk = nb & (cap - 1), k;
2060                     ForkJoinTask<?> t = a[k = b & (cap - 1)];
2061                     U.loadFence();                // re-read b and t
2062                     if (b == (b = q.base)) {      // else inconsistent; retry
2063                         Object o;
2064                         if (t == null)
2065                             o = a[k];
2066                         else if (t == (o = U.compareAndExchangeReference(
2067                                            a, slotOffset(k), t, null))) {
2068                             q.updateBase(nb);
2069                             next = RESCAN | ((window << 16) & HMASK) | j;
2070                             if (window != next && a[nk] != null)
2071                                 signalWork(a, nk); // limit propagation
2072                             if (w != null)        // always true
2073                                 w.topLevelExec(t, q, j);
2074                             break outer;
2075                         }
2076                         if (o == null) {
2077                             if (next >= 0L && a[nk] != null)
2078                                 next |= RESCAN;
2079                             break;
2080                         }
2081                     }
2082                 }
2083             }
2084         }
2085         return next;
2086     }
2087 
2088     /**
2089      * Tries to inactivate, and if successful, awaits signal or termination.
2090      *
2091      * @param w the worker (may be null if already terminated)
2092      * @param phase current phase
2093      * @return current phase, with IDLE set if worker should exit
2094      */
2095     private int awaitWork(WorkQueue w, int phase) {
2096         boolean quiet;                           // true if possibly quiescent
2097         int active = phase + (IDLE << 1), p = phase | IDLE, e;
2098         if (w != null) {
2099             w.phase = p;                         // deactivate
2100             long np = active & LMASK, pc = ctl;  // try to enqueue
2101             long qc = np | ((pc - RC_UNIT) & UMASK);
2102             w.stackPred = (int)pc;               // set ctl stack link
2103             if (pc != (pc = compareAndExchangeCtl(pc, qc))) {
2104                 qc = np | ((pc - RC_UNIT) & UMASK);
2105                 w.stackPred = (int)pc;           // retry once
2106                 if (pc != (pc = compareAndExchangeCtl(pc, qc)))
2107                     p = w.phase = phase;         // back out
2108             }
2109             if (p != phase && ((e = runState) & STOP) == 0 &&
2110                 (!(quiet = (qc & RC_MASK) <= 0L) || (e & SHUTDOWN) == 0 ||
2111                  !(quiet = quiescent()) || (runState & STOP) == 0)) {
2112                 long deadline = 0L;              // not terminating
2113                 if (quiet) {                     // use timeout if trimmable
2114                     int nt = (short)(qc >>> TC_SHIFT);
2115                     long delay = keepAlive;      // scale if not at target
2116                     if (nt != (nt = Math.max(nt, parallelism)) && nt > 0)
2117                         delay = Math.max(TIMEOUT_SLOP, delay / nt);
2118                     if ((deadline = delay + System.currentTimeMillis()) == 0L)
2119                         deadline = 1L;           // avoid zero
2120                 }
2121                 boolean release = quiet;
2122                 WorkQueue[] qs = queues;         // recheck queues
2123                 int n = (qs == null) ? 0 : qs.length;
2124                 for (int l = -n, j = active; l < n; ++l, ++j) {
2125                     WorkQueue q; ForkJoinTask<?>[] a; int cap;
2126                     if ((p = w.phase) == active) // interleave signal checks
2127                         break;
2128                     if ((q = qs[j & (n - 1)]) != null &&
2129                         (a = q.array) != null && (cap = a.length) > 0 &&
2130                         a[q.base & (cap - 1)] != null) {
2131                         if (release && qc == ctl && compareAndSetCtl(qc, pc)) {
2132                             p = w.phase = active;
2133                             break;               // possible missed signal
2134                         }
2135                         release = true;          // track multiple or reencounter
2136                     }
2137                     Thread.onSpinWait();         // reduce memory traffic
2138                 }
2139                 if (p != active) {               // emulate LockSupport.park
2140                     LockSupport.setCurrentBlocker(this);
2141                     w.parking = 1;
2142                     for (;;) {
2143                         if ((runState & STOP) != 0 || (p = w.phase) == active)
2144                             break;
2145                         U.park(deadline != 0L, deadline);
2146                         if ((p = w.phase) == active || (runState & STOP) != 0)
2147                             break;
2148                         Thread.interrupted();    // clear for next park
2149                         if (deadline != 0L && TIMEOUT_SLOP >
2150                             deadline - System.currentTimeMillis()) {
2151                             long sp = w.stackPred & LMASK, c = ctl;
2152                             long nc = sp | (UMASK & (c - TC_UNIT));
2153                             if (((int)c & SMASK) == (active & SMASK) &&
2154                                 compareAndSetCtl(c, nc)) {
2155                                 w.source = DEREGISTERED;
2156                                 w.phase = active;
2157                                 break;           // trimmed on timeout
2158                             }
2159                             deadline = 0L;       // no longer trimmable
2160                         }
2161                     }
2162                     w.parking = 0;
2163                     LockSupport.setCurrentBlocker(null);
2164                 }
2165             }
2166         }
2167         return p;
2168     }
2169 
2170     /**
2171      * Scans for and returns a polled task, if available.  Used only
2172      * for untracked polls. Begins scan at a random index to avoid
2173      * systematic unfairness.
2174      *
2175      * @param submissionsOnly if true, only scan submission queues
2176      */
2177     private ForkJoinTask<?> pollScan(boolean submissionsOnly) {
2178         if ((runState & STOP) == 0) {
2179             WorkQueue[] qs; int n; WorkQueue q; ForkJoinTask<?> t;
2180             int r = ThreadLocalRandom.nextSecondarySeed();
2181             if (submissionsOnly)                 // even indices only
2182                 r &= ~1;
2183             int step = (submissionsOnly) ? 2 : 1;
2184             if ((qs = queues) != null && (n = qs.length) > 0) {
2185                 for (int i = n; i > 0; i -= step, r += step) {
2186                     if ((q = qs[r & (n - 1)]) != null &&
2187                         (t = q.poll(this)) != null)
2188                         return t;
2189                 }
2190             }
2191         }
2192         return null;
2193     }
2194 
2195     /**
2196      * Tries to decrement counts (sometimes implicitly) and possibly
2197      * arrange for a compensating worker in preparation for
2198      * blocking. May fail due to interference, in which case -1 is
2199      * returned so caller may retry. A zero return value indicates
2200      * that the caller doesn't need to re-adjust counts when later
2201      * unblocked.
2202      *
2203      * @param c incoming ctl value
2204      * @return UNCOMPENSATE: block then adjust, 0: block, -1 : retry
2205      */
2206     private int tryCompensate(long c) {
2207         Predicate<? super ForkJoinPool> sat;
2208         long b = config;
2209         int pc        = parallelism,                    // unpack fields
2210             minActive = (short)(b >>> RC_SHIFT),
2211             maxTotal  = (short)(b >>> TC_SHIFT) + pc,
2212             active    = (short)(c >>> RC_SHIFT),
2213             total     = (short)(c >>> TC_SHIFT),
2214             sp        = (int)c,
2215             stat      = -1;                             // default retry return
2216         if (sp != 0 && active <= pc) {                  // activate idle worker
2217             WorkQueue[] qs; WorkQueue v; int i;
2218             if ((qs = queues) != null && qs.length > (i = sp & SMASK) &&
2219                 (v = qs[i]) != null &&
2220                 compareAndSetCtl(c, (c & UMASK) | (v.stackPred & LMASK))) {
2221                 v.phase = sp;
2222                 if (v.parking != 0)
2223                     U.unpark(v.owner);
2224                 stat = UNCOMPENSATE;
2225             }
2226         }
2227         else if (active > minActive && total >= pc) {   // reduce active workers
2228             if (compareAndSetCtl(c, ((c - RC_UNIT) & RC_MASK) | (c & ~RC_MASK)))
2229                 stat = UNCOMPENSATE;
2230         }
2231         else if (total < maxTotal && total < MAX_CAP) { // try to expand pool
2232             long nc = ((c + TC_UNIT) & TC_MASK) | (c & ~TC_MASK);
2233             if ((runState & STOP) != 0)                 // terminating
2234                 stat = 0;
2235             else if (compareAndSetCtl(c, nc))
2236                 stat = createWorker() ? UNCOMPENSATE : 0;
2237         }
2238         else if (!compareAndSetCtl(c, c))               // validate
2239             ;
2240         else if ((sat = saturate) != null && sat.test(this))
2241             stat = 0;
2242         else
2243             throw new RejectedExecutionException(
2244                 "Thread limit exceeded replacing blocked worker");
2245         return stat;
2246     }
2247 
2248     /**
2249      * Readjusts RC count; called from ForkJoinTask after blocking.
2250      */
2251     final void uncompensate() {
2252         getAndAddCtl(RC_UNIT);
2253     }
2254 
2255     /**
2256      * Helps if possible until the given task is done.  Processes
2257      * compatible local tasks and scans other queues for task produced
2258      * by w's stealers; returning compensated blocking sentinel if
2259      * none are found.
2260      *
2261      * @param task the task
2262      * @param w caller's WorkQueue
2263      * @param internal true if w is owned by a ForkJoinWorkerThread
2264      * @return task status on exit, or UNCOMPENSATE for compensated blocking
2265      */
2266 
2267     final int helpJoin(ForkJoinTask<?> task, WorkQueue w, boolean internal) {
2268         if (w != null)
2269             w.tryRemoveAndExec(task, internal);
2270         int s = 0;
2271         if (task != null && (s = task.status) >= 0 && internal && w != null) {
2272             int wid = w.phase & SMASK, r = wid + 2, wsrc = w.source;
2273             long sctl = 0L;                             // track stability
2274             outer: for (boolean rescan = true;;) {
2275                 if ((s = task.status) < 0)
2276                     break;
2277                 if (!rescan) {
2278                     if ((runState & STOP) != 0)
2279                         break;
2280                     if (sctl == (sctl = ctl) && (s = tryCompensate(sctl)) >= 0)
2281                         break;
2282                 }
2283                 rescan = false;
2284                 WorkQueue[] qs = queues;
2285                 int n = (qs == null) ? 0 : qs.length;
2286                 scan: for (int l = n >>> 1; l > 0; --l, r += 2) {
2287                     int j; WorkQueue q;
2288                     if ((q = qs[j = r & SMASK & (n - 1)]) != null) {
2289                         for (;;) {
2290                             int sq = q.source, b, cap, k; ForkJoinTask<?>[] a;
2291                             if ((a = q.array) == null || (cap = a.length) <= 0)
2292                                 break;
2293                             ForkJoinTask<?> t = a[k = (b = q.base) & (cap - 1)];
2294                             U.loadFence();
2295                             boolean eligible = false;
2296                             if (t == task)
2297                                 eligible = true;
2298                             else if (t != null) {       // check steal chain
2299                                 for (int v = sq, d = cap;;) {
2300                                     WorkQueue p;
2301                                     if (v == wid) {
2302                                         eligible = true;
2303                                         break;
2304                                     }
2305                                     if ((v & 1) == 0 || // external or none
2306                                         --d < 0 ||      // bound depth
2307                                         (p = qs[v & (n - 1)]) == null)
2308                                         break;
2309                                     v = p.source;
2310                                 }
2311                             }
2312                             if ((s = task.status) < 0)
2313                                 break outer;            // validate
2314                             if (q.source == sq && q.base == b && a[k] == t) {
2315                                 int nb = b + 1, nk = nb & (cap - 1);
2316                                 if (!eligible) {        // revisit if nonempty
2317                                     if (!rescan && t == null &&
2318                                         (a[nk] != null || q.top - b > 0))
2319                                         rescan = true;
2320                                     break;
2321                                 }
2322                                 if (U.compareAndSetReference(
2323                                         a, slotOffset(k), t, null)) {
2324                                     q.updateBase(nb);
2325                                     w.source = j;
2326                                     t.doExec();
2327                                     w.source = wsrc;
2328                                     rescan = true;   // restart at index r
2329                                     break scan;
2330                                 }
2331                             }
2332                         }
2333                     }
2334                 }
2335             }
2336         }
2337         return s;
2338     }
2339 
2340     /**
2341      * Version of helpJoin for CountedCompleters.
2342      *
2343      * @param task root of computation (only called when a CountedCompleter)
2344      * @param w caller's WorkQueue
2345      * @param internal true if w is owned by a ForkJoinWorkerThread
2346      * @return task status on exit, or UNCOMPENSATE for compensated blocking
2347      */
2348     final int helpComplete(ForkJoinTask<?> task, WorkQueue w, boolean internal) {
2349         int s = 0;
2350         if (task != null && (s = task.status) >= 0 && w != null) {
2351             int r = w.phase + 1;                          // for indexing
2352             long sctl = 0L;                               // track stability
2353             outer: for (boolean rescan = true, locals = true;;) {
2354                 if (locals && (s = w.helpComplete(task, internal, 0)) < 0)
2355                     break;
2356                 if ((s = task.status) < 0)
2357                     break;
2358                 if (!rescan) {
2359                     if ((runState & STOP) != 0)
2360                         break;
2361                     if (sctl == (sctl = ctl) &&
2362                         (!internal || (s = tryCompensate(sctl)) >= 0))
2363                         break;
2364                 }
2365                 rescan = locals = false;
2366                 WorkQueue[] qs = queues;
2367                 int n = (qs == null) ? 0 : qs.length;
2368                 scan: for (int l = n; l > 0; --l, ++r) {
2369                     int j; WorkQueue q;
2370                     if ((q = qs[j = r & SMASK & (n - 1)]) != null) {
2371                         for (;;) {
2372                             ForkJoinTask<?>[] a; int b, cap, k;
2373                             if ((a = q.array) == null || (cap = a.length) <= 0)
2374                                 break;
2375                             ForkJoinTask<?> t = a[k = (b = q.base) & (cap - 1)];
2376                             U.loadFence();
2377                             boolean eligible = false;
2378                             if (t instanceof CountedCompleter) {
2379                                 CountedCompleter<?> f = (CountedCompleter<?>)t;
2380                                 for (int steps = cap; steps > 0; --steps) {
2381                                     if (f == task) {
2382                                         eligible = true;
2383                                         break;
2384                                     }
2385                                     if ((f = f.completer) == null)
2386                                         break;
2387                                 }
2388                             }
2389                             if ((s = task.status) < 0)    // validate
2390                                 break outer;
2391                             if (q.base == b) {
2392                                 int nb = b + 1, nk = nb & (cap - 1);
2393                                 if (eligible) {
2394                                     if (U.compareAndSetReference(
2395                                             a, slotOffset(k), t, null)) {
2396                                         q.updateBase(nb);
2397                                         t.doExec();
2398                                         locals = rescan = true;
2399                                         break scan;
2400                                     }
2401                                 }
2402                                 else if (a[k] == t) {
2403                                     if (!rescan && t == null &&
2404                                         (a[nk] != null || q.top - b > 0))
2405                                         rescan = true;    // revisit
2406                                     break;
2407                                 }
2408                             }
2409                         }
2410                     }
2411                 }
2412             }
2413         }
2414         return s;
2415      }
2416 
2417     /**
2418      * Runs tasks until all workers are inactive and no tasks are
2419      * found. Rather than blocking when tasks cannot be found, rescans
2420      * until all others cannot find tasks either.
2421      *
2422      * @param nanos max wait time (Long.MAX_VALUE if effectively untimed)
2423      * @param interruptible true if return on interrupt
2424      * @return positive if quiescent, negative if interrupted, else 0
2425      */
2426     private int helpQuiesce(WorkQueue w, long nanos, boolean interruptible) {
2427         int phase; // w.phase inactive bit set when temporarily quiescent
2428         if (w == null || ((phase = w.phase) & IDLE) != 0)
2429             return 0;
2430         int wsrc = w.source;
2431         long startTime = System.nanoTime();
2432         long maxSleep = Math.min(nanos >>> 8, MAX_SLEEP); // approx 1% nanos
2433         long prevSum = 0L;
2434         int activePhase = phase, inactivePhase = phase + IDLE;
2435         int r = phase + 1, waits = 0, returnStatus = 1;
2436         boolean locals = true;
2437         for (int e = runState;;) {
2438             if ((e & STOP) != 0)
2439                 break;                      // terminating
2440             if (interruptible && Thread.interrupted()) {
2441                 returnStatus = -1;
2442                 break;
2443             }
2444             if (locals) {                   // run local tasks before (re)polling
2445                 locals = false;
2446                 for (ForkJoinTask<?> u; (u = w.nextLocalTask()) != null;)
2447                     u.doExec();
2448             }
2449             WorkQueue[] qs = queues;
2450             int n = (qs == null) ? 0 : qs.length;
2451             long phaseSum = 0L;
2452             boolean rescan = false, busy = false;
2453             scan: for (int l = n; l > 0; --l, ++r) {
2454                 int j; WorkQueue q;
2455                 if ((q = qs[j = r & SMASK & (n - 1)]) != null && q != w) {
2456                     for (;;) {
2457                         ForkJoinTask<?>[] a; int b, cap, k;
2458                         if ((a = q.array) == null || (cap = a.length) <= 0)
2459                             break;
2460                         ForkJoinTask<?> t = a[k = (b = q.base) & (cap - 1)];
2461                         if (t != null && phase == inactivePhase) // reactivate
2462                             w.phase = phase = activePhase;
2463                         U.loadFence();
2464                         if (q.base == b && a[k] == t) {
2465                             int nb = b + 1;
2466                             if (t == null) {
2467                                 if (!rescan) {
2468                                     int qp = q.phase, mq = qp & (IDLE | 1);
2469                                     phaseSum += qp;
2470                                     if (mq == 0 || q.top - b > 0)
2471                                         rescan = true;
2472                                     else if (mq == 1)
2473                                         busy = true;
2474                                 }
2475                                 break;
2476                             }
2477                             if (U.compareAndSetReference(
2478                                     a, slotOffset(k), t, null)) {
2479                                 q.updateBase(nb);
2480                                 w.source = j;
2481                                 t.doExec();
2482                                 w.source = wsrc;
2483                                 rescan = locals = true;
2484                                 break scan;
2485                             }
2486                         }
2487                     }
2488                 }
2489             }
2490             if (e != (e = runState) || prevSum != (prevSum = phaseSum) ||
2491                 rescan || (e & RS_LOCK) != 0)
2492                 ;                   // inconsistent
2493             else if (!busy)
2494                 break;
2495             else if (phase == activePhase) {
2496                 waits = 0;          // recheck, then sleep
2497                 w.phase = phase = inactivePhase;
2498             }
2499             else if (System.nanoTime() - startTime > nanos) {
2500                 returnStatus = 0;   // timed out
2501                 break;
2502             }
2503             else if (waits == 0)   // same as spinLockRunState except
2504                 waits = MIN_SLEEP; //   with rescan instead of onSpinWait
2505             else {
2506                 LockSupport.parkNanos(this, (long)waits);
2507                 if (waits < maxSleep)
2508                     waits <<= 1;
2509             }
2510         }
2511         w.phase = activePhase;
2512         return returnStatus;
2513     }
2514 
2515     /**
2516      * Helps quiesce from external caller until done, interrupted, or timeout
2517      *
2518      * @param nanos max wait time (Long.MAX_VALUE if effectively untimed)
2519      * @param interruptible true if return on interrupt
2520      * @return positive if quiescent, negative if interrupted, else 0
2521      */
2522     private int externalHelpQuiesce(long nanos, boolean interruptible) {
2523         if (!quiescent()) {
2524             long startTime = System.nanoTime();
2525             long maxSleep = Math.min(nanos >>> 8, MAX_SLEEP);
2526             for (int waits = 0;;) {
2527                 ForkJoinTask<?> t;
2528                 if (interruptible && Thread.interrupted())
2529                     return -1;
2530                 else if ((t = pollScan(false)) != null) {
2531                     waits = 0;
2532                     t.doExec();
2533                 }
2534                 else if (quiescent())
2535                     break;
2536                 else if (System.nanoTime() - startTime > nanos)
2537                     return 0;
2538                 else if (waits == 0)
2539                     waits = MIN_SLEEP;
2540                 else {
2541                     LockSupport.parkNanos(this, (long)waits);
2542                     if (waits < maxSleep)
2543                         waits <<= 1;
2544                 }
2545             }
2546         }
2547         return 1;
2548     }
2549 
2550     /**
2551      * Helps quiesce from either internal or external caller
2552      *
2553      * @param pool the pool to use, or null if any
2554      * @param nanos max wait time (Long.MAX_VALUE if effectively untimed)
2555      * @param interruptible true if return on interrupt
2556      * @return positive if quiescent, negative if interrupted, else 0
2557      */
2558     static final int helpQuiescePool(ForkJoinPool pool, long nanos,
2559                                      boolean interruptible) {
2560         Thread t; ForkJoinPool p; ForkJoinWorkerThread wt;
2561         if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread &&
2562             (p = (wt = (ForkJoinWorkerThread)t).pool) != null &&
2563             (p == pool || pool == null))
2564             return p.helpQuiesce(wt.workQueue, nanos, interruptible);
2565         else if ((p = pool) != null || (p = common) != null)
2566             return p.externalHelpQuiesce(nanos, interruptible);
2567         else
2568             return 0;
2569     }
2570 
2571     /**
2572      * Gets and removes a local or stolen task for the given worker.
2573      *
2574      * @return a task, if available
2575      */
2576     final ForkJoinTask<?> nextTaskFor(WorkQueue w) {
2577         ForkJoinTask<?> t;
2578         if (w == null || (t = w.nextLocalTask()) == null)
2579             t = pollScan(false);
2580         return t;
2581     }
2582 
2583     // External operations
2584 
2585     /**
2586      * Finds and locks a WorkQueue for an external submitter, or
2587      * throws RejectedExecutionException if shutdown or terminating.
2588      * @param r current ThreadLocalRandom.getProbe() value
2589      * @param isSubmit false if this is for a common pool fork
2590      */
2591     private WorkQueue submissionQueue(int r) {
2592         if (r == 0) {
2593             ThreadLocalRandom.localInit();           // initialize caller's probe
2594             r = ThreadLocalRandom.getProbe();
2595         }
2596         for (;;) {
2597             int n, i, id; WorkQueue[] qs; WorkQueue q;
2598             if ((qs = queues) == null)
2599                 break;
2600             if ((n = qs.length) <= 0)
2601                 break;
2602             if ((q = qs[i = (id = r & EXTERNAL_ID_MASK) & (n - 1)]) == null) {
2603                 WorkQueue w = new WorkQueue(null, id, 0, false);
2604                 w.array = new ForkJoinTask<?>[INITIAL_QUEUE_CAPACITY];
2605                 int stop = lockRunState() & STOP;
2606                 if (stop == 0 && queues == qs && qs[i] == null)
2607                     q = qs[i] = w;                   // else discard; retry
2608                 unlockRunState();
2609                 if (q != null)
2610                     return q;
2611                 if (stop != 0)
2612                     break;
2613             }
2614             else if (!q.tryLockPhase())              // move index
2615                 r = ThreadLocalRandom.advanceProbe(r);
2616             else if ((runState & SHUTDOWN) != 0) {
2617                 q.unlockPhase();                     // check while q lock held
2618                 break;
2619             }
2620             else
2621                 return q;
2622         }
2623         tryTerminate(false, false);
2624         throw new RejectedExecutionException();
2625     }
2626 
2627     private void poolSubmit(boolean signalIfEmpty, ForkJoinTask<?> task) {
2628         Thread t; ForkJoinWorkerThread wt; WorkQueue q; boolean internal;
2629         if (((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) &&
2630             (wt = (ForkJoinWorkerThread)t).pool == this) {
2631             internal = true;
2632             q = wt.workQueue;
2633         }
2634         else {                     // find and lock queue
2635             internal = false;
2636             q = submissionQueue(ThreadLocalRandom.getProbe());
2637         }
2638         q.push(task, signalIfEmpty ? this : null, internal);
2639     }
2640 
2641     /**
2642      * Returns queue for an external submission, bypassing call to
2643      * submissionQueue if already established and unlocked.
2644      */
2645     final WorkQueue externalSubmissionQueue() {
2646         WorkQueue[] qs; WorkQueue q; int n;
2647         int r = ThreadLocalRandom.getProbe();
2648         return (((qs = queues) != null && (n = qs.length) > 0 &&
2649                  (q = qs[r & EXTERNAL_ID_MASK & (n - 1)]) != null && r != 0 &&
2650                  q.tryLockPhase()) ? q : submissionQueue(r));
2651     }
2652 
2653     /**
2654      * Returns queue for an external thread, if one exists that has
2655      * possibly ever submitted to the given pool (nonzero probe), or
2656      * null if none.
2657      */
2658     static WorkQueue externalQueue(ForkJoinPool p) {
2659         WorkQueue[] qs; int n;
2660         int r = ThreadLocalRandom.getProbe();
2661         return (p != null && (qs = p.queues) != null &&
2662                 (n = qs.length) > 0 && r != 0) ?
2663             qs[r & EXTERNAL_ID_MASK & (n - 1)] : null;
2664     }
2665 
2666     /**
2667      * Returns external queue for common pool.
2668      */
2669     static WorkQueue commonQueue() {
2670         return externalQueue(common);
2671     }
2672 
2673     /**
2674      * If the given executor is a ForkJoinPool, poll and execute
2675      * AsynchronousCompletionTasks from worker's queue until none are
2676      * available or blocker is released.
2677      */
2678     static void helpAsyncBlocker(Executor e, ManagedBlocker blocker) {
2679         WorkQueue w = null; Thread t; ForkJoinWorkerThread wt;
2680         if (((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) &&
2681             (wt = (ForkJoinWorkerThread)t).pool == e)
2682             w = wt.workQueue;
2683         else if (e instanceof ForkJoinPool)
2684             w = externalQueue((ForkJoinPool)e);
2685         if (w != null)
2686             w.helpAsyncBlocker(blocker);
2687     }
2688 
2689     /**
2690      * Returns a cheap heuristic guide for task partitioning when
2691      * programmers, frameworks, tools, or languages have little or no
2692      * idea about task granularity.  In essence, by offering this
2693      * method, we ask users only about tradeoffs in overhead vs
2694      * expected throughput and its variance, rather than how finely to
2695      * partition tasks.
2696      *
2697      * In a steady state strict (tree-structured) computation, each
2698      * thread makes available for stealing enough tasks for other
2699      * threads to remain active. Inductively, if all threads play by
2700      * the same rules, each thread should make available only a
2701      * constant number of tasks.
2702      *
2703      * The minimum useful constant is just 1. But using a value of 1
2704      * would require immediate replenishment upon each steal to
2705      * maintain enough tasks, which is infeasible.  Further,
2706      * partitionings/granularities of offered tasks should minimize
2707      * steal rates, which in general means that threads nearer the top
2708      * of computation tree should generate more than those nearer the
2709      * bottom. In perfect steady state, each thread is at
2710      * approximately the same level of computation tree. However,
2711      * producing extra tasks amortizes the uncertainty of progress and
2712      * diffusion assumptions.
2713      *
2714      * So, users will want to use values larger (but not much larger)
2715      * than 1 to both smooth over transient shortages and hedge
2716      * against uneven progress; as traded off against the cost of
2717      * extra task overhead. We leave the user to pick a threshold
2718      * value to compare with the results of this call to guide
2719      * decisions, but recommend values such as 3.
2720      *
2721      * When all threads are active, it is on average OK to estimate
2722      * surplus strictly locally. In steady-state, if one thread is
2723      * maintaining say 2 surplus tasks, then so are others. So we can
2724      * just use estimated queue length.  However, this strategy alone
2725      * leads to serious mis-estimates in some non-steady-state
2726      * conditions (ramp-up, ramp-down, other stalls). We can detect
2727      * many of these by further considering the number of "idle"
2728      * threads, that are known to have zero queued tasks, so
2729      * compensate by a factor of (#idle/#active) threads.
2730      */
2731     static int getSurplusQueuedTaskCount() {
2732         Thread t; ForkJoinWorkerThread wt; ForkJoinPool pool; WorkQueue q;
2733         if (((t = Thread.currentThread()) instanceof ForkJoinWorkerThread) &&
2734             (pool = (wt = (ForkJoinWorkerThread)t).pool) != null &&
2735             (q = wt.workQueue) != null) {
2736             int n = q.top - q.base;
2737             int p = pool.parallelism;
2738             int a = (short)(pool.ctl >>> RC_SHIFT);
2739             return n - (a > (p >>>= 1) ? 0 :
2740                         a > (p >>>= 1) ? 1 :
2741                         a > (p >>>= 1) ? 2 :
2742                         a > (p >>>= 1) ? 4 :
2743                         8);
2744         }
2745         return 0;
2746     }
2747 
2748     // Termination
2749 
2750     /**
2751      * Possibly initiates and/or completes pool termination.
2752      *
2753      * @param now if true, unconditionally terminate, else only
2754      * if no work and no active workers
2755      * @param enable if true, terminate when next possible
2756      * @return runState on exit
2757      */
2758     private int tryTerminate(boolean now, boolean enable) {
2759         int e = runState;
2760         if ((e & STOP) == 0) {
2761             if (now) {
2762                 int s = lockRunState();
2763                 runState = e = (s + RS_LOCK) | STOP | SHUTDOWN;
2764                 if ((s & STOP) == 0)
2765                     interruptAll();
2766             }
2767             else {
2768                 int isShutdown = (e & SHUTDOWN);
2769                 if (isShutdown == 0 && enable)
2770                     getAndBitwiseOrRunState(isShutdown = SHUTDOWN);
2771                 if (isShutdown != 0)
2772                     quiescent();                 // may trigger STOP
2773                 e = runState;
2774             }
2775         }
2776         if ((e & (STOP | TERMINATED)) == STOP) { // help cancel tasks
2777             int r = (int)Thread.currentThread().threadId(); // stagger traversals
2778             WorkQueue[] qs = queues;
2779             int n = (qs == null) ? 0 : qs.length;
2780             for (int l = n; l > 0; --l, ++r) {
2781                 int j = r & SMASK & (n - 1); WorkQueue q; ForkJoinTask<?> t;
2782                 while ((q = qs[j]) != null && q.source != DEREGISTERED &&
2783                        (t = q.poll(null)) != null) {
2784                     try {
2785                         t.cancel(false);
2786                     } catch (Throwable ignore) {
2787                     }
2788                 }
2789             }
2790             if (((e = runState) & TERMINATED) == 0 && ctl == 0L) {
2791                 if ((getAndBitwiseOrRunState(TERMINATED) & TERMINATED) == 0) {
2792                     CountDownLatch done; SharedThreadContainer ctr;
2793                     if ((done = termination) != null)
2794                         done.countDown();
2795                     if ((ctr = container) != null)
2796                         ctr.close();
2797                 }
2798                 e = runState;
2799             }
2800         }
2801         return e;
2802     }
2803 
2804     /**
2805      * Interrupts all workers
2806      */
2807     private void interruptAll() {
2808         Thread current = Thread.currentThread();
2809         WorkQueue[] qs = queues;
2810         int n = (qs == null) ? 0 : qs.length;
2811         for (int i = 1; i < n; i += 2) {
2812             WorkQueue q; Thread o;
2813             if ((q = qs[i]) != null && (o = q.owner) != null && o != current &&
2814                 q.source != DEREGISTERED) {
2815                 try {
2816                     o.interrupt();
2817                 } catch (Throwable ignore) {
2818                 }
2819             }
2820         }
2821     }
2822 
2823     /**
2824      * Returns termination signal, constructing if necessary
2825      */
2826     private CountDownLatch terminationSignal() {
2827         CountDownLatch signal, s, u;
2828         if ((signal = termination) == null)
2829             signal = ((u = cmpExTerminationSignal(
2830                            s = new CountDownLatch(1))) == null) ? s : u;
2831         return signal;
2832     }
2833 
2834     // Exported methods
2835 
2836     // Constructors
2837 
2838     /**
2839      * Creates a {@code ForkJoinPool} with parallelism equal to {@link
2840      * java.lang.Runtime#availableProcessors}, using defaults for all
2841      * other parameters (see {@link #ForkJoinPool(int,
2842      * ForkJoinWorkerThreadFactory, UncaughtExceptionHandler, boolean,
2843      * int, int, int, Predicate, long, TimeUnit)}).
2844      *
2845      * @throws SecurityException if a security manager exists and
2846      *         the caller is not permitted to modify threads
2847      *         because it does not hold {@link
2848      *         java.lang.RuntimePermission}{@code ("modifyThread")}
2849      */
2850     public ForkJoinPool() {
2851         this(Math.min(MAX_CAP, Runtime.getRuntime().availableProcessors()),
2852              defaultForkJoinWorkerThreadFactory, null, false,
2853              0, MAX_CAP, 1, null, DEFAULT_KEEPALIVE, TimeUnit.MILLISECONDS);
2854     }
2855 
2856     /**
2857      * Creates a {@code ForkJoinPool} with the indicated parallelism
2858      * level, using defaults for all other parameters (see {@link
2859      * #ForkJoinPool(int, ForkJoinWorkerThreadFactory,
2860      * UncaughtExceptionHandler, boolean, int, int, int, Predicate,
2861      * long, TimeUnit)}).
2862      *
2863      * @param parallelism the parallelism level
2864      * @throws IllegalArgumentException if parallelism less than or
2865      *         equal to zero, or greater than implementation limit
2866      * @throws SecurityException if a security manager exists and
2867      *         the caller is not permitted to modify threads
2868      *         because it does not hold {@link
2869      *         java.lang.RuntimePermission}{@code ("modifyThread")}
2870      */
2871     public ForkJoinPool(int parallelism) {
2872         this(parallelism, defaultForkJoinWorkerThreadFactory, null, false,
2873              0, MAX_CAP, 1, null, DEFAULT_KEEPALIVE, TimeUnit.MILLISECONDS);
2874     }
2875 
2876     /**
2877      * Creates a {@code ForkJoinPool} with the given parameters (using
2878      * defaults for others -- see {@link #ForkJoinPool(int,
2879      * ForkJoinWorkerThreadFactory, UncaughtExceptionHandler, boolean,
2880      * int, int, int, Predicate, long, TimeUnit)}).
2881      *
2882      * @param parallelism the parallelism level. For default value,
2883      * use {@link java.lang.Runtime#availableProcessors}.
2884      * @param factory the factory for creating new threads. For default value,
2885      * use {@link #defaultForkJoinWorkerThreadFactory}.
2886      * @param handler the handler for internal worker threads that
2887      * terminate due to unrecoverable errors encountered while executing
2888      * tasks. For default value, use {@code null}.
2889      * @param asyncMode if true,
2890      * establishes local first-in-first-out scheduling mode for forked
2891      * tasks that are never joined. This mode may be more appropriate
2892      * than default locally stack-based mode in applications in which
2893      * worker threads only process event-style asynchronous tasks.
2894      * For default value, use {@code false}.
2895      * @throws IllegalArgumentException if parallelism less than or
2896      *         equal to zero, or greater than implementation limit
2897      * @throws NullPointerException if the factory is null
2898      * @throws SecurityException if a security manager exists and
2899      *         the caller is not permitted to modify threads
2900      *         because it does not hold {@link
2901      *         java.lang.RuntimePermission}{@code ("modifyThread")}
2902      */
2903     public ForkJoinPool(int parallelism,
2904                         ForkJoinWorkerThreadFactory factory,
2905                         UncaughtExceptionHandler handler,
2906                         boolean asyncMode) {
2907         this(parallelism, factory, handler, asyncMode,
2908              0, MAX_CAP, 1, null, DEFAULT_KEEPALIVE, TimeUnit.MILLISECONDS);
2909     }
2910 
2911     /**
2912      * Creates a {@code ForkJoinPool} with the given parameters.
2913      *
2914      * @param parallelism the parallelism level. For default value,
2915      * use {@link java.lang.Runtime#availableProcessors}.
2916      *
2917      * @param factory the factory for creating new threads. For
2918      * default value, use {@link #defaultForkJoinWorkerThreadFactory}.
2919      *
2920      * @param handler the handler for internal worker threads that
2921      * terminate due to unrecoverable errors encountered while
2922      * executing tasks. For default value, use {@code null}.
2923      *
2924      * @param asyncMode if true, establishes local first-in-first-out
2925      * scheduling mode for forked tasks that are never joined. This
2926      * mode may be more appropriate than default locally stack-based
2927      * mode in applications in which worker threads only process
2928      * event-style asynchronous tasks.  For default value, use {@code
2929      * false}.
2930      *
2931      * @param corePoolSize the number of threads to keep in the pool
2932      * (unless timed out after an elapsed keep-alive). Normally (and
2933      * by default) this is the same value as the parallelism level,
2934      * but may be set to a larger value to reduce dynamic overhead if
2935      * tasks regularly block. Using a smaller value (for example
2936      * {@code 0}) has the same effect as the default.
2937      *
2938      * @param maximumPoolSize the maximum number of threads allowed.
2939      * When the maximum is reached, attempts to replace blocked
2940      * threads fail.  (However, because creation and termination of
2941      * different threads may overlap, and may be managed by the given
2942      * thread factory, this value may be transiently exceeded.)  To
2943      * arrange the same value as is used by default for the common
2944      * pool, use {@code 256} plus the {@code parallelism} level. (By
2945      * default, the common pool allows a maximum of 256 spare
2946      * threads.)  Using a value (for example {@code
2947      * Integer.MAX_VALUE}) larger than the implementation's total
2948      * thread limit has the same effect as using this limit (which is
2949      * the default).
2950      *
2951      * @param minimumRunnable the minimum allowed number of core
2952      * threads not blocked by a join or {@link ManagedBlocker}.  To
2953      * ensure progress, when too few unblocked threads exist and
2954      * unexecuted tasks may exist, new threads are constructed, up to
2955      * the given maximumPoolSize.  For the default value, use {@code
2956      * 1}, that ensures liveness.  A larger value might improve
2957      * throughput in the presence of blocked activities, but might
2958      * not, due to increased overhead.  A value of zero may be
2959      * acceptable when submitted tasks cannot have dependencies
2960      * requiring additional threads.
2961      *
2962      * @param saturate if non-null, a predicate invoked upon attempts
2963      * to create more than the maximum total allowed threads.  By
2964      * default, when a thread is about to block on a join or {@link
2965      * ManagedBlocker}, but cannot be replaced because the
2966      * maximumPoolSize would be exceeded, a {@link
2967      * RejectedExecutionException} is thrown.  But if this predicate
2968      * returns {@code true}, then no exception is thrown, so the pool
2969      * continues to operate with fewer than the target number of
2970      * runnable threads, which might not ensure progress.
2971      *
2972      * @param keepAliveTime the elapsed time since last use before
2973      * a thread is terminated (and then later replaced if needed).
2974      * For the default value, use {@code 60, TimeUnit.SECONDS}.
2975      *
2976      * @param unit the time unit for the {@code keepAliveTime} argument
2977      *
2978      * @throws IllegalArgumentException if parallelism is less than or
2979      *         equal to zero, or is greater than implementation limit,
2980      *         or if maximumPoolSize is less than parallelism,
2981      *         of if the keepAliveTime is less than or equal to zero.
2982      * @throws NullPointerException if the factory is null
2983      * @throws SecurityException if a security manager exists and
2984      *         the caller is not permitted to modify threads
2985      *         because it does not hold {@link
2986      *         java.lang.RuntimePermission}{@code ("modifyThread")}
2987      * @since 9
2988      */
2989     public ForkJoinPool(int parallelism,
2990                         ForkJoinWorkerThreadFactory factory,
2991                         UncaughtExceptionHandler handler,
2992                         boolean asyncMode,
2993                         int corePoolSize,
2994                         int maximumPoolSize,
2995                         int minimumRunnable,
2996                         Predicate<? super ForkJoinPool> saturate,
2997                         long keepAliveTime,
2998                         TimeUnit unit) {
2999         checkPermission();
3000         int p = parallelism;
3001         if (p <= 0 || p > MAX_CAP || p > maximumPoolSize || keepAliveTime <= 0L)
3002             throw new IllegalArgumentException();
3003         if (factory == null || unit == null)
3004             throw new NullPointerException();
3005         int size = 1 << (33 - Integer.numberOfLeadingZeros(p - 1));
3006         this.parallelism = p;
3007         this.factory = factory;
3008         this.ueh = handler;
3009         this.saturate = saturate;
3010         this.keepAlive = Math.max(unit.toMillis(keepAliveTime), TIMEOUT_SLOP);
3011         int maxSpares = Math.clamp(maximumPoolSize - p, 0, MAX_CAP);
3012         int minAvail = Math.clamp(minimumRunnable, 0, MAX_CAP);
3013         this.config = (((asyncMode ? FIFO : 0) & LMASK) |
3014                        (((long)maxSpares) << TC_SHIFT) |
3015                        (((long)minAvail)  << RC_SHIFT));
3016         this.queues = new WorkQueue[size];
3017         String pid = Integer.toString(getAndAddPoolIds(1) + 1);
3018         String name = "ForkJoinPool-" + pid;
3019         this.workerNamePrefix = name + "-worker-";
3020         this.container = SharedThreadContainer.create(name);
3021     }
3022 
3023     /**
3024      * Constructor for common pool using parameters possibly
3025      * overridden by system properties
3026      */
3027     private ForkJoinPool(byte forCommonPoolOnly) {
3028         ForkJoinWorkerThreadFactory fac = defaultForkJoinWorkerThreadFactory;
3029         UncaughtExceptionHandler handler = null;
3030         int maxSpares = DEFAULT_COMMON_MAX_SPARES;
3031         int pc = 0, preset = 0; // nonzero if size set as property
3032         try {  // ignore exceptions in accessing/parsing properties
3033             String pp = System.getProperty
3034                 ("java.util.concurrent.ForkJoinPool.common.parallelism");
3035             if (pp != null) {
3036                 pc = Math.max(0, Integer.parseInt(pp));
3037                 preset = PRESET_SIZE;
3038             }
3039             String ms = System.getProperty
3040                 ("java.util.concurrent.ForkJoinPool.common.maximumSpares");
3041             if (ms != null)
3042                 maxSpares = Math.clamp(Integer.parseInt(ms), 0, MAX_CAP);
3043             String sf = System.getProperty
3044                 ("java.util.concurrent.ForkJoinPool.common.threadFactory");
3045             String sh = System.getProperty
3046                 ("java.util.concurrent.ForkJoinPool.common.exceptionHandler");
3047             if (sf != null || sh != null) {
3048                 ClassLoader ldr = ClassLoader.getSystemClassLoader();
3049                 if (sf != null)
3050                     fac = (ForkJoinWorkerThreadFactory)
3051                         ldr.loadClass(sf).getConstructor().newInstance();
3052                 if (sh != null)
3053                     handler = (UncaughtExceptionHandler)
3054                         ldr.loadClass(sh).getConstructor().newInstance();
3055             }
3056         } catch (Exception ignore) {
3057         }
3058         if (preset == 0)
3059             pc = Math.max(1, Runtime.getRuntime().availableProcessors() - 1);
3060         int p = Math.min(pc, MAX_CAP);
3061         int size = (p == 0) ? 1 : 1 << (33 - Integer.numberOfLeadingZeros(p-1));
3062         this.parallelism = p;
3063         this.config = ((preset & LMASK) | (((long)maxSpares) << TC_SHIFT) |
3064                        (1L << RC_SHIFT));
3065         this.factory = fac;
3066         this.ueh = handler;
3067         this.keepAlive = DEFAULT_KEEPALIVE;
3068         this.saturate = null;
3069         this.workerNamePrefix = null;
3070         this.queues = new WorkQueue[size];
3071         this.container = SharedThreadContainer.create("ForkJoinPool.commonPool");
3072     }
3073 
3074     /**
3075      * Returns the common pool instance. This pool is statically
3076      * constructed; its run state is unaffected by attempts to {@link
3077      * #shutdown} or {@link #shutdownNow}. However this pool and any
3078      * ongoing processing are automatically terminated upon program
3079      * {@link System#exit}.  Any program that relies on asynchronous
3080      * task processing to complete before program termination should
3081      * invoke {@code commonPool().}{@link #awaitQuiescence awaitQuiescence},
3082      * before exit.
3083      *
3084      * @return the common pool instance
3085      * @since 1.8
3086      */
3087     public static ForkJoinPool commonPool() {
3088         // assert common != null : "static init error";
3089         return common;
3090     }
3091 
3092     // Execution methods
3093 
3094     /**
3095      * Performs the given task, returning its result upon completion.
3096      * If the computation encounters an unchecked Exception or Error,
3097      * it is rethrown as the outcome of this invocation.  Rethrown
3098      * exceptions behave in the same way as regular exceptions, but,
3099      * when possible, contain stack traces (as displayed for example
3100      * using {@code ex.printStackTrace()}) of both the current thread
3101      * as well as the thread actually encountering the exception;
3102      * minimally only the latter.
3103      *
3104      * @param task the task
3105      * @param <T> the type of the task's result
3106      * @return the task's result
3107      * @throws NullPointerException if the task is null
3108      * @throws RejectedExecutionException if the task cannot be
3109      *         scheduled for execution
3110      */
3111     public <T> T invoke(ForkJoinTask<T> task) {
3112         Objects.requireNonNull(task);
3113         poolSubmit(true, task);
3114         try {
3115             return task.join();
3116         } catch (RuntimeException | Error unchecked) {
3117             throw unchecked;
3118         } catch (Exception checked) {
3119             throw new RuntimeException(checked);
3120         }
3121     }
3122 
3123     /**
3124      * Arranges for (asynchronous) execution of the given task.
3125      *
3126      * @param task the task
3127      * @throws NullPointerException if the task is null
3128      * @throws RejectedExecutionException if the task cannot be
3129      *         scheduled for execution
3130      */
3131     public void execute(ForkJoinTask<?> task) {
3132         Objects.requireNonNull(task);
3133         poolSubmit(true, task);
3134     }
3135 
3136     // AbstractExecutorService methods
3137 
3138     /**
3139      * @throws NullPointerException if the task is null
3140      * @throws RejectedExecutionException if the task cannot be
3141      *         scheduled for execution
3142      */
3143     @Override
3144     @SuppressWarnings("unchecked")
3145     public void execute(Runnable task) {
3146         poolSubmit(true, (task instanceof ForkJoinTask<?>)
3147                    ? (ForkJoinTask<Void>) task // avoid re-wrap
3148                    : new ForkJoinTask.RunnableExecuteAction(task));
3149     }
3150 
3151     /**
3152      * Submits a ForkJoinTask for execution.
3153      *
3154      * @implSpec
3155      * This method is equivalent to {@link #externalSubmit(ForkJoinTask)}
3156      * when called from a thread that is not in this pool.
3157      *
3158      * @param task the task to submit
3159      * @param <T> the type of the task's result
3160      * @return the task
3161      * @throws NullPointerException if the task is null
3162      * @throws RejectedExecutionException if the task cannot be
3163      *         scheduled for execution
3164      */
3165     public <T> ForkJoinTask<T> submit(ForkJoinTask<T> task) {
3166         Objects.requireNonNull(task);
3167         poolSubmit(true, task);
3168         return task;
3169     }
3170 
3171     /**
3172      * @throws NullPointerException if the task is null
3173      * @throws RejectedExecutionException if the task cannot be
3174      *         scheduled for execution
3175      */
3176     @Override
3177     public <T> ForkJoinTask<T> submit(Callable<T> task) {
3178         ForkJoinTask<T> t =
3179             (Thread.currentThread() instanceof ForkJoinWorkerThread) ?
3180             new ForkJoinTask.AdaptedCallable<T>(task) :
3181             new ForkJoinTask.AdaptedInterruptibleCallable<T>(task);
3182         poolSubmit(true, t);
3183         return t;
3184     }
3185 
3186     /**
3187      * @throws NullPointerException if the task is null
3188      * @throws RejectedExecutionException if the task cannot be
3189      *         scheduled for execution
3190      */
3191     @Override
3192     public <T> ForkJoinTask<T> submit(Runnable task, T result) {
3193         ForkJoinTask<T> t =
3194             (Thread.currentThread() instanceof ForkJoinWorkerThread) ?
3195             new ForkJoinTask.AdaptedRunnable<T>(task, result) :
3196             new ForkJoinTask.AdaptedInterruptibleRunnable<T>(task, result);
3197         poolSubmit(true, t);
3198         return t;
3199     }
3200 
3201     /**
3202      * @throws NullPointerException if the task is null
3203      * @throws RejectedExecutionException if the task cannot be
3204      *         scheduled for execution
3205      */
3206     @Override
3207     @SuppressWarnings("unchecked")
3208     public ForkJoinTask<?> submit(Runnable task) {
3209         ForkJoinTask<?> f = (task instanceof ForkJoinTask<?>) ?
3210             (ForkJoinTask<Void>) task : // avoid re-wrap
3211             ((Thread.currentThread() instanceof ForkJoinWorkerThread) ?
3212              new ForkJoinTask.AdaptedRunnable<Void>(task, null) :
3213              new ForkJoinTask.AdaptedInterruptibleRunnable<Void>(task, null));
3214         poolSubmit(true, f);
3215         return f;
3216     }
3217 
3218     /**
3219      * Submits the given task as if submitted from a non-{@code ForkJoinTask}
3220      * client. The task is added to a scheduling queue for submissions to the
3221      * pool even when called from a thread in the pool.
3222      *
3223      * @implSpec
3224      * This method is equivalent to {@link #submit(ForkJoinTask)} when called
3225      * from a thread that is not in this pool.
3226      *
3227      * @return the task
3228      * @param task the task to submit
3229      * @param <T> the type of the task's result
3230      * @throws NullPointerException if the task is null
3231      * @throws RejectedExecutionException if the task cannot be
3232      *         scheduled for execution
3233      * @since 20
3234      */
3235     public <T> ForkJoinTask<T> externalSubmit(ForkJoinTask<T> task) {
3236         Objects.requireNonNull(task);
3237         externalSubmissionQueue().push(task, this, false);
3238         return task;
3239     }
3240 
3241     /**
3242      * Submits the given task without guaranteeing that it will
3243      * eventually execute in the absence of available active threads.
3244      * In some contexts, this method may reduce contention and
3245      * overhead by relying on context-specific knowledge that existing
3246      * threads (possibly including the calling thread if operating in
3247      * this pool) will eventually be available to execute the task.
3248      *
3249      * @param task the task
3250      * @param <T> the type of the task's result
3251      * @return the task
3252      * @throws NullPointerException if the task is null
3253      * @throws RejectedExecutionException if the task cannot be
3254      *         scheduled for execution
3255      * @since 19
3256      */
3257     public <T> ForkJoinTask<T> lazySubmit(ForkJoinTask<T> task) {
3258         Objects.requireNonNull(task);
3259         poolSubmit(false, task);
3260         return task;
3261     }
3262 
3263     /**
3264      * Changes the target parallelism of this pool, controlling the
3265      * future creation, use, and termination of worker threads.
3266      * Applications include contexts in which the number of available
3267      * processors changes over time.
3268      *
3269      * @implNote This implementation restricts the maximum number of
3270      * running threads to 32767
3271      *
3272      * @param size the target parallelism level
3273      * @return the previous parallelism level.
3274      * @throws IllegalArgumentException if size is less than 1 or
3275      *         greater than the maximum supported by this pool.
3276      * @throws UnsupportedOperationException this is the{@link
3277      *         #commonPool()} and parallelism level was set by System
3278      *         property {@systemProperty
3279      *         java.util.concurrent.ForkJoinPool.common.parallelism}.
3280      * @throws SecurityException if a security manager exists and
3281      *         the caller is not permitted to modify threads
3282      *         because it does not hold {@link
3283      *         java.lang.RuntimePermission}{@code ("modifyThread")}
3284      * @since 19
3285      */
3286     public int setParallelism(int size) {
3287         if (size < 1 || size > MAX_CAP)
3288             throw new IllegalArgumentException();
3289         if ((config & PRESET_SIZE) != 0)
3290             throw new UnsupportedOperationException("Cannot override System property");
3291         checkPermission();
3292         return getAndSetParallelism(size);
3293     }
3294 
3295     /**
3296      * Uninterrupible version of {@code invokeAll}. Executes the given
3297      * tasks, returning a list of Futures holding their status and
3298      * results when all complete, ignoring interrupts.  {@link
3299      * Future#isDone} is {@code true} for each element of the returned
3300      * list.  Note that a <em>completed</em> task could have
3301      * terminated either normally or by throwing an exception.  The
3302      * results of this method are undefined if the given collection is
3303      * modified while this operation is in progress.
3304      *
3305      * @apiNote This method supports usages that previously relied on an
3306      * incompatible override of
3307      * {@link ExecutorService#invokeAll(java.util.Collection)}.
3308      *
3309      * @param tasks the collection of tasks
3310      * @param <T> the type of the values returned from the tasks
3311      * @return a list of Futures representing the tasks, in the same
3312      *         sequential order as produced by the iterator for the
3313      *         given task list, each of which has completed
3314      * @throws NullPointerException if tasks or any of its elements are {@code null}
3315      * @throws RejectedExecutionException if any task cannot be
3316      *         scheduled for execution
3317      * @since 22
3318      */
3319     public <T> List<Future<T>> invokeAllUninterruptibly(Collection<? extends Callable<T>> tasks) {
3320         ArrayList<Future<T>> futures = new ArrayList<>(tasks.size());
3321         try {
3322             for (Callable<T> t : tasks) {
3323                 ForkJoinTask<T> f = ForkJoinTask.adapt(t);
3324                 futures.add(f);
3325                 poolSubmit(true, f);
3326             }
3327             for (int i = futures.size() - 1; i >= 0; --i)
3328                 ((ForkJoinTask<?>)futures.get(i)).quietlyJoin();
3329             return futures;
3330         } catch (Throwable t) {
3331             for (Future<T> e : futures)
3332                 e.cancel(true);
3333             throw t;
3334         }
3335     }
3336 
3337     /**
3338      * Common support for timed and untimed invokeAll
3339      */
3340     private  <T> List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks,
3341                                            long deadline)
3342         throws InterruptedException {
3343         ArrayList<Future<T>> futures = new ArrayList<>(tasks.size());
3344         try {
3345             for (Callable<T> t : tasks) {
3346                 ForkJoinTask<T> f = ForkJoinTask.adaptInterruptible(t);
3347                 futures.add(f);
3348                 poolSubmit(true, f);
3349             }
3350             for (int i = futures.size() - 1; i >= 0; --i)
3351                 ((ForkJoinTask<?>)futures.get(i))
3352                     .quietlyJoinPoolInvokeAllTask(deadline);
3353             return futures;
3354         } catch (Throwable t) {
3355             for (Future<T> e : futures)
3356                 e.cancel(true);
3357             throw t;
3358         }
3359     }
3360 
3361     @Override
3362     public <T> List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks)
3363         throws InterruptedException {
3364         return invokeAll(tasks, 0L);
3365     }
3366     // for jdk version < 22, replace with
3367     // /**
3368     //  * @throws NullPointerException       {@inheritDoc}
3369     //  * @throws RejectedExecutionException {@inheritDoc}
3370     //  */
3371     // @Override
3372     // public <T> List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks) {
3373     //     return invokeAllUninterruptibly(tasks);
3374     // }
3375 
3376     @Override
3377     public <T> List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks,
3378                                          long timeout, TimeUnit unit)
3379         throws InterruptedException {
3380         return invokeAll(tasks, (System.nanoTime() + unit.toNanos(timeout)) | 1L);
3381     }
3382 
3383     @Override
3384     public <T> T invokeAny(Collection<? extends Callable<T>> tasks)
3385         throws InterruptedException, ExecutionException {
3386         try {
3387             return new ForkJoinTask.InvokeAnyRoot<T>()
3388                 .invokeAny(tasks, this, false, 0L);
3389         } catch (TimeoutException cannotHappen) {
3390             assert false;
3391             return null;
3392         }
3393     }
3394 
3395     @Override
3396     public <T> T invokeAny(Collection<? extends Callable<T>> tasks,
3397                            long timeout, TimeUnit unit)
3398         throws InterruptedException, ExecutionException, TimeoutException {
3399         return new ForkJoinTask.InvokeAnyRoot<T>()
3400             .invokeAny(tasks, this, true, unit.toNanos(timeout));
3401     }
3402 
3403     /**
3404      * Returns the factory used for constructing new workers.
3405      *
3406      * @return the factory used for constructing new workers
3407      */
3408     public ForkJoinWorkerThreadFactory getFactory() {
3409         return factory;
3410     }
3411 
3412     /**
3413      * Returns the handler for internal worker threads that terminate
3414      * due to unrecoverable errors encountered while executing tasks.
3415      *
3416      * @return the handler, or {@code null} if none
3417      */
3418     public UncaughtExceptionHandler getUncaughtExceptionHandler() {
3419         return ueh;
3420     }
3421 
3422     /**
3423      * Returns the targeted parallelism level of this pool.
3424      *
3425      * @return the targeted parallelism level of this pool
3426      */
3427     public int getParallelism() {
3428         return Math.max(getParallelismOpaque(), 1);
3429     }
3430 
3431     /**
3432      * Returns the targeted parallelism level of the common pool.
3433      *
3434      * @return the targeted parallelism level of the common pool
3435      * @since 1.8
3436      */
3437     public static int getCommonPoolParallelism() {
3438         return common.getParallelism();
3439     }
3440 
3441     /**
3442      * Returns the number of worker threads that have started but not
3443      * yet terminated.  The result returned by this method may differ
3444      * from {@link #getParallelism} when threads are created to
3445      * maintain parallelism when others are cooperatively blocked.
3446      *
3447      * @return the number of worker threads
3448      */
3449     public int getPoolSize() {
3450         return (short)(ctl >>> TC_SHIFT);
3451     }
3452 
3453     /**
3454      * Returns {@code true} if this pool uses local first-in-first-out
3455      * scheduling mode for forked tasks that are never joined.
3456      *
3457      * @return {@code true} if this pool uses async mode
3458      */
3459     public boolean getAsyncMode() {
3460         return (config & FIFO) != 0;
3461     }
3462 
3463     /**
3464      * Returns an estimate of the number of worker threads that are
3465      * not blocked waiting to join tasks or for other managed
3466      * synchronization. This method may overestimate the
3467      * number of running threads.
3468      *
3469      * @return the number of worker threads
3470      */
3471     public int getRunningThreadCount() {
3472         WorkQueue[] qs; WorkQueue q;
3473         int rc = 0;
3474         if ((runState & TERMINATED) == 0 && (qs = queues) != null) {
3475             for (int i = 1; i < qs.length; i += 2) {
3476                 if ((q = qs[i]) != null && q.isApparentlyUnblocked())
3477                     ++rc;
3478             }
3479         }
3480         return rc;
3481     }
3482 
3483     /**
3484      * Returns an estimate of the number of threads that are currently
3485      * stealing or executing tasks. This method may overestimate the
3486      * number of active threads.
3487      *
3488      * @return the number of active threads
3489      */
3490     public int getActiveThreadCount() {
3491         return Math.max((short)(ctl >>> RC_SHIFT), 0);
3492     }
3493 
3494     /**
3495      * Returns {@code true} if all worker threads are currently idle.
3496      * An idle worker is one that cannot obtain a task to execute
3497      * because none are available to steal from other threads, and
3498      * there are no pending submissions to the pool. This method is
3499      * conservative; it might not return {@code true} immediately upon
3500      * idleness of all threads, but will eventually become true if
3501      * threads remain inactive.
3502      *
3503      * @return {@code true} if all threads are currently idle
3504      */
3505     public boolean isQuiescent() {
3506         return quiescent();
3507     }
3508 
3509     /**
3510      * Returns an estimate of the total number of completed tasks that
3511      * were executed by a thread other than their submitter. The
3512      * reported value underestimates the actual total number of steals
3513      * when the pool is not quiescent. This value may be useful for
3514      * monitoring and tuning fork/join programs: in general, steal
3515      * counts should be high enough to keep threads busy, but low
3516      * enough to avoid overhead and contention across threads.
3517      *
3518      * @return the number of steals
3519      */
3520     public long getStealCount() {
3521         long count = stealCount;
3522         WorkQueue[] qs; WorkQueue q;
3523         if ((qs = queues) != null) {
3524             for (int i = 1; i < qs.length; i += 2) {
3525                 if ((q = qs[i]) != null)
3526                      count += (long)q.nsteals & 0xffffffffL;
3527             }
3528         }
3529         return count;
3530     }
3531 
3532     /**
3533      * Returns an estimate of the total number of tasks currently held
3534      * in queues by worker threads (but not including tasks submitted
3535      * to the pool that have not begun executing). This value is only
3536      * an approximation, obtained by iterating across all threads in
3537      * the pool. This method may be useful for tuning task
3538      * granularities.
3539      *
3540      * @return the number of queued tasks
3541      * @see ForkJoinWorkerThread#getQueuedTaskCount()
3542      */
3543     public long getQueuedTaskCount() {
3544         WorkQueue[] qs; WorkQueue q;
3545         int count = 0;
3546         if ((runState & TERMINATED) == 0 && (qs = queues) != null) {
3547             for (int i = 1; i < qs.length; i += 2) {
3548                 if ((q = qs[i]) != null)
3549                     count += q.queueSize();
3550             }
3551         }
3552         return count;
3553     }
3554 
3555     /**
3556      * Returns an estimate of the number of tasks submitted to this
3557      * pool that have not yet begun executing.  This method may take
3558      * time proportional to the number of submissions.
3559      *
3560      * @return the number of queued submissions
3561      */
3562     public int getQueuedSubmissionCount() {
3563         WorkQueue[] qs; WorkQueue q;
3564         int count = 0;
3565         if ((runState & TERMINATED) == 0 && (qs = queues) != null) {
3566             for (int i = 0; i < qs.length; i += 2) {
3567                 if ((q = qs[i]) != null)
3568                     count += q.queueSize();
3569             }
3570         }
3571         return count;
3572     }
3573 
3574     /**
3575      * Returns {@code true} if there are any tasks submitted to this
3576      * pool that have not yet begun executing.
3577      *
3578      * @return {@code true} if there are any queued submissions
3579      */
3580     public boolean hasQueuedSubmissions() {
3581         WorkQueue[] qs; WorkQueue q;
3582         if ((runState & STOP) == 0 && (qs = queues) != null) {
3583             for (int i = 0; i < qs.length; i += 2) {
3584                 if ((q = qs[i]) != null && q.queueSize() > 0)
3585                     return true;
3586             }
3587         }
3588         return false;
3589     }
3590 
3591     /**
3592      * Removes and returns the next unexecuted submission if one is
3593      * available.  This method may be useful in extensions to this
3594      * class that re-assign work in systems with multiple pools.
3595      *
3596      * @return the next submission, or {@code null} if none
3597      */
3598     protected ForkJoinTask<?> pollSubmission() {
3599         return pollScan(true);
3600     }
3601 
3602     /**
3603      * Removes all available unexecuted submitted and forked tasks
3604      * from scheduling queues and adds them to the given collection,
3605      * without altering their execution status. These may include
3606      * artificially generated or wrapped tasks. This method is
3607      * designed to be invoked only when the pool is known to be
3608      * quiescent. Invocations at other times may not remove all
3609      * tasks. A failure encountered while attempting to add elements
3610      * to collection {@code c} may result in elements being in
3611      * neither, either or both collections when the associated
3612      * exception is thrown.  The behavior of this operation is
3613      * undefined if the specified collection is modified while the
3614      * operation is in progress.
3615      *
3616      * @param c the collection to transfer elements into
3617      * @return the number of elements transferred
3618      */
3619     protected int drainTasksTo(Collection<? super ForkJoinTask<?>> c) {
3620         int count = 0;
3621         for (ForkJoinTask<?> t; (t = pollScan(false)) != null; ) {
3622             c.add(t);
3623             ++count;
3624         }
3625         return count;
3626     }
3627 
3628     /**
3629      * Returns a string identifying this pool, as well as its state,
3630      * including indications of run state, parallelism level, and
3631      * worker and task counts.
3632      *
3633      * @return a string identifying this pool, as well as its state
3634      */
3635     public String toString() {
3636         // Use a single pass through queues to collect counts
3637         int e = runState;
3638         long st = stealCount;
3639         long qt = 0L, ss = 0L; int rc = 0;
3640         WorkQueue[] qs; WorkQueue q;
3641         if ((qs = queues) != null) {
3642             for (int i = 0; i < qs.length; ++i) {
3643                 if ((q = qs[i]) != null) {
3644                     int size = q.queueSize();
3645                     if ((i & 1) == 0)
3646                         ss += size;
3647                     else {
3648                         qt += size;
3649                         st += (long)q.nsteals & 0xffffffffL;
3650                         if (q.isApparentlyUnblocked())
3651                             ++rc;
3652                     }
3653                 }
3654             }
3655         }
3656 
3657         int pc = parallelism;
3658         long c = ctl;
3659         int tc = (short)(c >>> TC_SHIFT);
3660         int ac = (short)(c >>> RC_SHIFT);
3661         if (ac < 0) // ignore transient negative
3662             ac = 0;
3663         String level = ((e & TERMINATED) != 0 ? "Terminated" :
3664                         (e & STOP)       != 0 ? "Terminating" :
3665                         (e & SHUTDOWN)   != 0 ? "Shutting down" :
3666                         "Running");
3667         return super.toString() +
3668             "[" + level +
3669             ", parallelism = " + pc +
3670             ", size = " + tc +
3671             ", active = " + ac +
3672             ", running = " + rc +
3673             ", steals = " + st +
3674             ", tasks = " + qt +
3675             ", submissions = " + ss +
3676             "]";
3677     }
3678 
3679     /**
3680      * Possibly initiates an orderly shutdown in which previously
3681      * submitted tasks are executed, but no new tasks will be
3682      * accepted. Invocation has no effect on execution state if this
3683      * is the {@link #commonPool()}, and no additional effect if
3684      * already shut down.  Tasks that are in the process of being
3685      * submitted concurrently during the course of this method may or
3686      * may not be rejected.
3687      *
3688      * @throws SecurityException if a security manager exists and
3689      *         the caller is not permitted to modify threads
3690      *         because it does not hold {@link
3691      *         java.lang.RuntimePermission}{@code ("modifyThread")}
3692      */
3693     public void shutdown() {
3694         checkPermission();
3695         if (workerNamePrefix != null) // not common pool
3696             tryTerminate(false, true);
3697     }
3698 
3699     /**
3700      * Possibly attempts to cancel and/or stop all tasks, and reject
3701      * all subsequently submitted tasks.  Invocation has no effect on
3702      * execution state if this is the {@link #commonPool()}, and no
3703      * additional effect if already shut down. Otherwise, tasks that
3704      * are in the process of being submitted or executed concurrently
3705      * during the course of this method may or may not be
3706      * rejected. This method cancels both existing and unexecuted
3707      * tasks, in order to permit termination in the presence of task
3708      * dependencies. So the method always returns an empty list
3709      * (unlike the case for some other Executors).
3710      *
3711      * @return an empty list
3712      * @throws SecurityException if a security manager exists and
3713      *         the caller is not permitted to modify threads
3714      *         because it does not hold {@link
3715      *         java.lang.RuntimePermission}{@code ("modifyThread")}
3716      */
3717     public List<Runnable> shutdownNow() {
3718         checkPermission();
3719         if (workerNamePrefix != null) // not common pool
3720             tryTerminate(true, true);
3721         return Collections.emptyList();
3722     }
3723 
3724     /**
3725      * Returns {@code true} if all tasks have completed following shut down.
3726      *
3727      * @return {@code true} if all tasks have completed following shut down
3728      */
3729     public boolean isTerminated() {
3730         return (tryTerminate(false, false) & TERMINATED) != 0;
3731     }
3732 
3733     /**
3734      * Returns {@code true} if the process of termination has
3735      * commenced but not yet completed.  This method may be useful for
3736      * debugging. A return of {@code true} reported a sufficient
3737      * period after shutdown may indicate that submitted tasks have
3738      * ignored or suppressed interruption, or are waiting for I/O,
3739      * causing this executor not to properly terminate. (See the
3740      * advisory notes for class {@link ForkJoinTask} stating that
3741      * tasks should not normally entail blocking operations.  But if
3742      * they do, they must abort them on interrupt.)
3743      *
3744      * @return {@code true} if terminating but not yet terminated
3745      */
3746     public boolean isTerminating() {
3747         return (tryTerminate(false, false) & (STOP | TERMINATED)) == STOP;
3748     }
3749 
3750     /**
3751      * Returns {@code true} if this pool has been shut down.
3752      *
3753      * @return {@code true} if this pool has been shut down
3754      */
3755     public boolean isShutdown() {
3756         return (runState & SHUTDOWN) != 0;
3757     }
3758 
3759     /**
3760      * Blocks until all tasks have completed execution after a
3761      * shutdown request, or the timeout occurs, or the current thread
3762      * is interrupted, whichever happens first. Because the {@link
3763      * #commonPool()} never terminates until program shutdown, when
3764      * applied to the common pool, this method is equivalent to {@link
3765      * #awaitQuiescence(long, TimeUnit)} but always returns {@code false}.
3766      *
3767      * @param timeout the maximum time to wait
3768      * @param unit the time unit of the timeout argument
3769      * @return {@code true} if this executor terminated and
3770      *         {@code false} if the timeout elapsed before termination
3771      * @throws InterruptedException if interrupted while waiting
3772      */
3773     public boolean awaitTermination(long timeout, TimeUnit unit)
3774         throws InterruptedException {
3775         long nanos = unit.toNanos(timeout);
3776         CountDownLatch done;
3777         if (workerNamePrefix == null) {    // is common pool
3778             if (helpQuiescePool(this, nanos, true) < 0)
3779                 throw new InterruptedException();
3780             return false;
3781         }
3782         else if ((tryTerminate(false, false) & TERMINATED) != 0 ||
3783                  (done = terminationSignal()) == null ||
3784                  (runState & TERMINATED) != 0)
3785             return true;
3786         else
3787             return done.await(nanos, TimeUnit.NANOSECONDS);
3788     }
3789 
3790     /**
3791      * If called by a ForkJoinTask operating in this pool, equivalent
3792      * in effect to {@link ForkJoinTask#helpQuiesce}. Otherwise,
3793      * waits and/or attempts to assist performing tasks until this
3794      * pool {@link #isQuiescent} or the indicated timeout elapses.
3795      *
3796      * @param timeout the maximum time to wait
3797      * @param unit the time unit of the timeout argument
3798      * @return {@code true} if quiescent; {@code false} if the
3799      * timeout elapsed.
3800      */
3801     public boolean awaitQuiescence(long timeout, TimeUnit unit) {
3802         return (helpQuiescePool(this, unit.toNanos(timeout), false) > 0);
3803     }
3804 
3805     /**
3806      * Unless this is the {@link #commonPool()}, initiates an orderly
3807      * shutdown in which previously submitted tasks are executed, but
3808      * no new tasks will be accepted, and waits until all tasks have
3809      * completed execution and the executor has terminated.
3810      *
3811      * <p> If already terminated, or this is the {@link
3812      * #commonPool()}, this method has no effect on execution, and
3813      * does not wait. Otherwise, if interrupted while waiting, this
3814      * method stops all executing tasks as if by invoking {@link
3815      * #shutdownNow()}. It then continues to wait until all actively
3816      * executing tasks have completed. Tasks that were awaiting
3817      * execution are not executed. The interrupt status will be
3818      * re-asserted before this method returns.
3819      *
3820      * @throws SecurityException if a security manager exists and
3821      *         shutting down this ExecutorService may manipulate
3822      *         threads that the caller is not permitted to modify
3823      *         because it does not hold {@link
3824      *         java.lang.RuntimePermission}{@code ("modifyThread")},
3825      *         or the security manager's {@code checkAccess} method
3826      *         denies access.
3827      * @since 19
3828      */
3829     @Override
3830     public void close() {
3831         if (workerNamePrefix != null) {
3832             checkPermission();
3833             CountDownLatch done = null;
3834             boolean interrupted = false;
3835             while ((tryTerminate(interrupted, true) & TERMINATED) == 0) {
3836                 if (done == null)
3837                     done = terminationSignal();
3838                 else {
3839                     try {
3840                         done.await();
3841                         break;
3842                     } catch (InterruptedException ex) {
3843                         interrupted = true;
3844                     }
3845                 }
3846             }
3847             if (interrupted)
3848                 Thread.currentThread().interrupt();
3849         }
3850     }
3851 
3852     /**
3853      * Interface for extending managed parallelism for tasks running
3854      * in {@link ForkJoinPool}s.
3855      *
3856      * <p>A {@code ManagedBlocker} provides two methods.  Method
3857      * {@link #isReleasable} must return {@code true} if blocking is
3858      * not necessary. Method {@link #block} blocks the current thread
3859      * if necessary (perhaps internally invoking {@code isReleasable}
3860      * before actually blocking). These actions are performed by any
3861      * thread invoking {@link
3862      * ForkJoinPool#managedBlock(ManagedBlocker)}.  The unusual
3863      * methods in this API accommodate synchronizers that may, but
3864      * don't usually, block for long periods. Similarly, they allow
3865      * more efficient internal handling of cases in which additional
3866      * workers may be, but usually are not, needed to ensure
3867      * sufficient parallelism.  Toward this end, implementations of
3868      * method {@code isReleasable} must be amenable to repeated
3869      * invocation. Neither method is invoked after a prior invocation
3870      * of {@code isReleasable} or {@code block} returns {@code true}.
3871      *
3872      * <p>For example, here is a ManagedBlocker based on a
3873      * ReentrantLock:
3874      * <pre> {@code
3875      * class ManagedLocker implements ManagedBlocker {
3876      *   final ReentrantLock lock;
3877      *   boolean hasLock = false;
3878      *   ManagedLocker(ReentrantLock lock) { this.lock = lock; }
3879      *   public boolean block() {
3880      *     if (!hasLock)
3881      *       lock.lock();
3882      *     return true;
3883      *   }
3884      *   public boolean isReleasable() {
3885      *     return hasLock || (hasLock = lock.tryLock());
3886      *   }
3887      * }}</pre>
3888      *
3889      * <p>Here is a class that possibly blocks waiting for an
3890      * item on a given queue:
3891      * <pre> {@code
3892      * class QueueTaker<E> implements ManagedBlocker {
3893      *   final BlockingQueue<E> queue;
3894      *   volatile E item = null;
3895      *   QueueTaker(BlockingQueue<E> q) { this.queue = q; }
3896      *   public boolean block() throws InterruptedException {
3897      *     if (item == null)
3898      *       item = queue.take();
3899      *     return true;
3900      *   }
3901      *   public boolean isReleasable() {
3902      *     return item != null || (item = queue.poll()) != null;
3903      *   }
3904      *   public E getItem() { // call after pool.managedBlock completes
3905      *     return item;
3906      *   }
3907      * }}</pre>
3908      */
3909     public static interface ManagedBlocker {
3910         /**
3911          * Possibly blocks the current thread, for example waiting for
3912          * a lock or condition.
3913          *
3914          * @return {@code true} if no additional blocking is necessary
3915          * (i.e., if isReleasable would return true)
3916          * @throws InterruptedException if interrupted while waiting
3917          * (the method is not required to do so, but is allowed to)
3918          */
3919         boolean block() throws InterruptedException;
3920 
3921         /**
3922          * Returns {@code true} if blocking is unnecessary.
3923          * @return {@code true} if blocking is unnecessary
3924          */
3925         boolean isReleasable();
3926     }
3927 
3928     /**
3929      * Runs the given possibly blocking task.  When {@linkplain
3930      * ForkJoinTask#inForkJoinPool() running in a ForkJoinPool}, this
3931      * method possibly arranges for a spare thread to be activated if
3932      * necessary to ensure sufficient parallelism while the current
3933      * thread is blocked in {@link ManagedBlocker#block blocker.block()}.
3934      *
3935      * <p>This method repeatedly calls {@code blocker.isReleasable()} and
3936      * {@code blocker.block()} until either method returns {@code true}.
3937      * Every call to {@code blocker.block()} is preceded by a call to
3938      * {@code blocker.isReleasable()} that returned {@code false}.
3939      *
3940      * <p>If not running in a ForkJoinPool, this method is
3941      * behaviorally equivalent to
3942      * <pre> {@code
3943      * while (!blocker.isReleasable())
3944      *   if (blocker.block())
3945      *     break;}</pre>
3946      *
3947      * If running in a ForkJoinPool, the pool may first be expanded to
3948      * ensure sufficient parallelism available during the call to
3949      * {@code blocker.block()}.
3950      *
3951      * @param blocker the blocker task
3952      * @throws InterruptedException if {@code blocker.block()} did so
3953      */
3954     public static void managedBlock(ManagedBlocker blocker)
3955         throws InterruptedException {
3956         Thread t; ForkJoinPool p;
3957         if ((t = Thread.currentThread()) instanceof ForkJoinWorkerThread &&
3958             (p = ((ForkJoinWorkerThread)t).pool) != null)
3959             p.compensatedBlock(blocker);
3960         else
3961             unmanagedBlock(blocker);
3962     }
3963 
3964     /** ManagedBlock for ForkJoinWorkerThreads */
3965     private void compensatedBlock(ManagedBlocker blocker)
3966         throws InterruptedException {
3967         Objects.requireNonNull(blocker);
3968         for (;;) {
3969             int comp; boolean done;
3970             long c = ctl;
3971             if (blocker.isReleasable())
3972                 break;
3973             if ((runState & STOP) != 0)
3974                 throw new InterruptedException();
3975             if ((comp = tryCompensate(c)) >= 0) {
3976                 try {
3977                     done = blocker.block();
3978                 } finally {
3979                     if (comp > 0)
3980                         getAndAddCtl(RC_UNIT);
3981                 }
3982                 if (done)
3983                     break;
3984             }
3985         }
3986     }
3987 
3988     /**
3989      * Invokes tryCompensate to create or re-activate a spare thread to
3990      * compensate for a thread that performs a blocking operation. When the
3991      * blocking operation is done then endCompensatedBlock must be invoked
3992      * with the value returned by this method to re-adjust the parallelism.
3993      */
3994     final long beginCompensatedBlock() {
3995         int c;
3996         do {} while ((c = tryCompensate(ctl)) < 0);
3997         return (c == 0) ? 0L : RC_UNIT;
3998     }
3999 
4000     /**
4001      * Re-adjusts parallelism after a blocking operation completes.
4002      */
4003     void endCompensatedBlock(long post) {
4004         if (post > 0L) {
4005             getAndAddCtl(post);
4006         }
4007     }
4008 
4009     /** ManagedBlock for external threads */
4010     private static void unmanagedBlock(ManagedBlocker blocker)
4011         throws InterruptedException {
4012         Objects.requireNonNull(blocker);
4013         do {} while (!blocker.isReleasable() && !blocker.block());
4014     }
4015 
4016     @Override
4017     protected <T> RunnableFuture<T> newTaskFor(Runnable runnable, T value) {
4018         return (Thread.currentThread() instanceof ForkJoinWorkerThread) ?
4019             new ForkJoinTask.AdaptedRunnable<T>(runnable, value) :
4020             new ForkJoinTask.AdaptedInterruptibleRunnable<T>(runnable, value);
4021     }
4022 
4023     @Override
4024     protected <T> RunnableFuture<T> newTaskFor(Callable<T> callable) {
4025         return (Thread.currentThread() instanceof ForkJoinWorkerThread) ?
4026             new ForkJoinTask.AdaptedCallable<T>(callable) :
4027             new ForkJoinTask.AdaptedInterruptibleCallable<T>(callable);
4028     }
4029 
4030     static {
4031         U = Unsafe.getUnsafe();
4032         Class<ForkJoinPool> klass = ForkJoinPool.class;
4033         try {
4034             Field poolIdsField = klass.getDeclaredField("poolIds");
4035             POOLIDS_BASE = U.staticFieldBase(poolIdsField);
4036             POOLIDS = U.staticFieldOffset(poolIdsField);
4037         } catch (NoSuchFieldException e) {
4038             throw new ExceptionInInitializerError(e);
4039         }
4040         CTL = U.objectFieldOffset(klass, "ctl");
4041         RUNSTATE = U.objectFieldOffset(klass, "runState");
4042         PARALLELISM =  U.objectFieldOffset(klass, "parallelism");
4043         THREADIDS = U.objectFieldOffset(klass, "threadIds");
4044         TERMINATION = U.objectFieldOffset(klass, "termination");
4045         Class<ForkJoinTask[]> aklass = ForkJoinTask[].class;
4046         ABASE = U.arrayBaseOffset(aklass);
4047         int scale = U.arrayIndexScale(aklass);
4048         ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
4049         if ((scale & (scale - 1)) != 0)
4050             throw new Error("array index scale not a power of two");
4051 
4052         defaultForkJoinWorkerThreadFactory =
4053             new DefaultForkJoinWorkerThreadFactory();
4054         @SuppressWarnings("removal")
4055         ForkJoinPool p = common = (System.getSecurityManager() == null) ?
4056             new ForkJoinPool((byte)0) :
4057             AccessController.doPrivileged(new PrivilegedAction<>() {
4058                     public ForkJoinPool run() {
4059                         return new ForkJoinPool((byte)0); }});
4060         // allow access to non-public methods
4061         SharedSecrets.setJavaUtilConcurrentFJPAccess(
4062             new JavaUtilConcurrentFJPAccess() {
4063                 @Override
4064                 public long beginCompensatedBlock(ForkJoinPool pool) {
4065                     return pool.beginCompensatedBlock();
4066                 }
4067                 public void endCompensatedBlock(ForkJoinPool pool, long post) {
4068                     pool.endCompensatedBlock(post);
4069                 }
4070             });
4071         Class<?> dep = LockSupport.class; // ensure loaded
4072     }
4073 }