/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

/*

 * This file is available under and governed by the GNU General Public

 * License version 2 only, as published by the Free Software Foundation.

 * However, the following notice accompanied the original version of this

 * file:

 *

 * Written by Doug Lea with assistance from members of JCP JSR-166

 * Expert Group and released to the public domain, as explained at

 * http://creativecommons.org/publicdomain/zero/1.0/

 */

package java.util.concurrent;

import java.lang.Thread.UncaughtExceptionHandler;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collection;

import java.util.Collections;

import java.util.List;

import java.util.concurrent.AbstractExecutorService;

import java.util.concurrent.Callable;

import java.util.concurrent.ExecutorService;

import java.util.concurrent.Future;

import java.util.concurrent.RejectedExecutionException;

import java.util.concurrent.RunnableFuture;

import java.util.concurrent.ThreadLocalRandom;

import java.util.concurrent.TimeUnit;

import java.util.concurrent.atomic.AtomicLong;

import java.security.AccessControlContext;

import java.security.ProtectionDomain;

import java.security.Permissions;

/**

 * An {@link ExecutorService} for running {@link ForkJoinTask}s.

 * A {@code ForkJoinPool} provides the entry point for submissions

 * from non-{@code ForkJoinTask} clients, as well as management and

 * monitoring operations.

 *

 * <p>A {@code ForkJoinPool} differs from other kinds of {@link

 * ExecutorService} mainly by virtue of employing

 * <em>work-stealing</em>: all threads in the pool attempt to find and

 * execute tasks submitted to the pool and/or created by other active

 * tasks (eventually blocking waiting for work if none exist). This

 * enables efficient processing when most tasks spawn other subtasks

 * (as do most {@code ForkJoinTask}s), as well as when many small

 * tasks are submitted to the pool from external clients.  Especially

 * when setting <em>asyncMode</em> to true in constructors, {@code

 * ForkJoinPool}s may also be appropriate for use with event-style

 * tasks that are never joined.

 *

 * <p>A static {@link #commonPool()} is available and appropriate for

 * most applications. The common pool is used by any ForkJoinTask that

 * is not explicitly submitted to a specified pool. Using the common

 * pool normally reduces resource usage (its threads are slowly

 * reclaimed during periods of non-use, and reinstated upon subsequent

 * use).

 *

 * <p>For applications that require separate or custom pools, a {@code

 * ForkJoinPool} may be constructed with a given target parallelism

 * level; by default, equal to the number of available processors.

 * The pool attempts to maintain enough active (or available) threads

 * by dynamically adding, suspending, or resuming internal worker

 * threads, even if some tasks are stalled waiting to join others.

 * However, no such adjustments are guaranteed in the face of blocked

 * I/O or other unmanaged synchronization. The nested {@link

 * ManagedBlocker} interface enables extension of the kinds of

 * synchronization accommodated.

 *

 * <p>In addition to execution and lifecycle control methods, this

 * class provides status check methods (for example

 * {@link #getStealCount}) that are intended to aid in developing,

 * tuning, and monitoring fork/join applications. Also, method

 * {@link #toString} returns indications of pool state in a

 * convenient form for informal monitoring.

 *

 * <p>As is the case with other ExecutorServices, there are three

 * main task execution methods summarized in the following table.

 * These are designed to be used primarily by clients not already

 * engaged in fork/join computations in the current pool.  The main

 * forms of these methods accept instances of {@code ForkJoinTask},

 * but overloaded forms also allow mixed execution of plain {@code

 * Runnable}- or {@code Callable}- based activities as well.  However,

 * tasks that are already executing in a pool should normally instead

 * use the within-computation forms listed in the table unless using

 * async event-style tasks that are not usually joined, in which case

 * there is little difference among choice of methods.

 *

 * <table BORDER CELLPADDING=3 CELLSPACING=1>

 * <caption>Summary of task execution methods</caption>

 *  <tr>

 *    <td></td>

 *    <td ALIGN=CENTER> <b>Call from non-fork/join clients</b></td>

 *    <td ALIGN=CENTER> <b>Call from within fork/join computations</b></td>

 *  </tr>

 *  <tr>

 *    <td> <b>Arrange async execution</b></td>

 *    <td> {@link #execute(ForkJoinTask)}</td>

 *    <td> {@link ForkJoinTask#fork}</td>

 *  </tr>

 *  <tr>

 *    <td> <b>Await and obtain result</b></td>

 *    <td> {@link #invoke(ForkJoinTask)}</td>

 *    <td> {@link ForkJoinTask#invoke}</td>

 *  </tr>

 *  <tr>

 *    <td> <b>Arrange exec and obtain Future</b></td>

 *    <td> {@link #submit(ForkJoinTask)}</td>

 *    <td> {@link ForkJoinTask#fork} (ForkJoinTasks <em>are</em> Futures)</td>

 *  </tr>

 * </table>

 *

 * <p>The common pool is by default constructed with default

 * parameters, but these may be controlled by setting three

 * {@linkplain System#getProperty system properties}:

 * <ul>

 * <li>{@code java.util.concurrent.ForkJoinPool.common.parallelism}

 * - the parallelism level, a non-negative integer

 * <li>{@code java.util.concurrent.ForkJoinPool.common.threadFactory}

 * - the class name of a {@link ForkJoinWorkerThreadFactory}

 * <li>{@code java.util.concurrent.ForkJoinPool.common.exceptionHandler}

 * - the class name of a {@link UncaughtExceptionHandler}

 * </ul>

 * If a {@link SecurityManager} is present and no factory is

 * specified, then the default pool uses a factory supplying

 * threads that have no {@link Permissions} enabled.

 * The system class loader is used to load these classes.

 * Upon any error in establishing these settings, default parameters

 * are used. It is possible to disable or limit the use of threads in

 * the common pool by setting the parallelism property to zero, and/or

 * using a factory that may return {@code null}. However doing so may

 * cause unjoined tasks to never be executed.

 *

 * <p><b>Implementation notes</b>: This implementation restricts the

 * maximum number of running threads to 32767. Attempts to create

 * pools with greater than the maximum number result in

 * {@code IllegalArgumentException}.

 *

 * <p>This implementation rejects submitted tasks (that is, by throwing

 * {@link RejectedExecutionException}) only when the pool is shut down

 * or internal resources have been exhausted.

 *

 * @since 1.7

 * @author Doug Lea

 */

@sun.misc.Contended

public class ForkJoinPool extends AbstractExecutorService {

    /*

     * Implementation Overview

     *

     * This class and its nested classes provide the main

     * functionality and control for a set of worker threads:

     * Submissions from non-FJ threads enter into submission queues.

     * Workers take these tasks and typically split them into subtasks

     * that may be stolen by other workers.  Preference rules give

     * first priority to processing tasks from their own queues (LIFO

     * or FIFO, depending on mode), then to randomized FIFO steals of

     * tasks in other queues.  This framework began as vehicle for

     * supporting tree-structured parallelism using work-stealing.

     * Over time, its scalability advantages led to extensions and

     * changes to better support more diverse usage contexts.  Because

     * most internal methods and nested classes are interrelated,

     * their main rationale and descriptions are presented here;

     * individual methods and nested classes contain only brief

     * comments about details.

     *

     * WorkQueues

     * ==========

     *

     * Most operations occur within work-stealing queues (in nested

     * class WorkQueue).  These are special forms of Deques that

     * support only three of the four possible end-operations -- push,

     * pop, and poll (aka steal), under the further constraints that

     * push and pop are called only from the owning thread (or, as

     * extended here, under a lock), while poll may be called from

     * other threads.  (If you are unfamiliar with them, you probably

     * want to read Herlihy and Shavit's book "The Art of

     * Multiprocessor programming", chapter 16 describing these in

     * more detail before proceeding.)  The main work-stealing queue

     * design is roughly similar to those in the papers "Dynamic

     * Circular Work-Stealing Deque" by Chase and Lev, SPAA 2005

     * (http://research.sun.com/scalable/pubs/index.html) and

     * "Idempotent work stealing" by Michael, Saraswat, and Vechev,

     * PPoPP 2009 (http://portal.acm.org/citation.cfm?id=1504186).

     * The main differences ultimately stem from GC requirements that

     * we null out taken slots as soon as we can, to maintain as small

     * a footprint as possible even in programs generating huge

     * numbers of tasks. To accomplish this, we shift the CAS

     * arbitrating pop vs poll (steal) from being on the indices

     * ("base" and "top") to the slots themselves.

     *

     * Adding tasks then takes the form of a classic array push(task):

     *    q.array[q.top] = task; ++q.top;

     *

     * (The actual code needs to null-check and size-check the array,

     * properly fence the accesses, and possibly signal waiting

     * workers to start scanning -- see below.)  Both a successful pop

     * and poll mainly entail a CAS of a slot from non-null to null.

     *

     * The pop operation (always performed by owner) is:

     *   if ((base != top) and

     *        (the task at top slot is not null) and

     *        (CAS slot to null))

     *           decrement top and return task;

     *

     * And the poll operation (usually by a stealer) is

     *    if ((base != top) and

     *        (the task at base slot is not null) and

     *        (base has not changed) and

     *        (CAS slot to null))

     *           increment base and return task;

     *

     * Because we rely on CASes of references, we do not need tag bits

     * on base or top.  They are simple ints as used in any circular

     * array-based queue (see for example ArrayDeque).  Updates to the

     * indices guarantee that top == base means the queue is empty,

     * but otherwise may err on the side of possibly making the queue

     * appear nonempty when a push, pop, or poll have not fully

     * committed. (Method isEmpty() checks the case of a partially

     * completed removal of the last element.)  Because of this, the

     * poll operation, considered individually, is not wait-free. One

     * thief cannot successfully continue until another in-progress

     * one (or, if previously empty, a push) completes.  However, in

     * the aggregate, we ensure at least probabilistic

     * non-blockingness.  If an attempted steal fails, a thief always

     * chooses a different random victim target to try next. So, in

     * order for one thief to progress, it suffices for any

     * in-progress poll or new push on any empty queue to

     * complete. (This is why we normally use method pollAt and its

     * variants that try once at the apparent base index, else

     * consider alternative actions, rather than method poll, which

     * retries.)

     *

     * This approach also enables support of a user mode in which

     * local task processing is in FIFO, not LIFO order, simply by

     * using poll rather than pop.  This can be useful in

     * message-passing frameworks in which tasks are never joined.

     * However neither mode considers affinities, loads, cache

     * localities, etc, so rarely provide the best possible

     * performance on a given machine, but portably provide good

     * throughput by averaging over these factors.  Further, even if

     * we did try to use such information, we do not usually have a

     * basis for exploiting it.  For example, some sets of tasks

     * profit from cache affinities, but others are harmed by cache

     * pollution effects. Additionally, even though it requires

     * scanning, long-term throughput is often best using random

     * selection rather than directed selection policies, so cheap

     * randomization of sufficient quality is used whenever

     * applicable.  Various Marsaglia XorShifts (some with different

     * shift constants) are inlined at use points.

     *

     * WorkQueues are also used in a similar way for tasks submitted

     * to the pool. We cannot mix these tasks in the same queues used

     * by workers. Instead, we randomly associate submission queues

     * with submitting threads, using a form of hashing.  The

     * ThreadLocalRandom probe value serves as a hash code for

     * choosing existing queues, and may be randomly repositioned upon

     * contention with other submitters.  In essence, submitters act

     * like workers except that they are restricted to executing local

     * tasks that they submitted (or in the case of CountedCompleters,

     * others with the same root task).  Insertion of tasks in shared

     * mode requires a lock (mainly to protect in the case of

     * resizing) but we use only a simple spinlock (using field

     * qlock), because submitters encountering a busy queue move on to

     * try or create other queues -- they block only when creating and

     * registering new queues. Additionally, "qlock" saturates to an

     * unlockable value (-1) at shutdown. Unlocking still can be and

     * is performed by cheaper ordered writes of "qlock" in successful

     * cases, but uses CAS in unsuccessful cases.

     *

     * Management

     * ==========

     *

     * The main throughput advantages of work-stealing stem from

     * decentralized control -- workers mostly take tasks from

     * themselves or each other, at rates that can exceed a billion

     * per second.  The pool itself creates, activates (enables

     * scanning for and running tasks), deactivates, blocks, and

     * terminates threads, all with minimal central information.

     * There are only a few properties that we can globally track or

     * maintain, so we pack them into a small number of variables,

     * often maintaining atomicity without blocking or locking.

     * Nearly all essentially atomic control state is held in two

     * volatile variables that are by far most often read (not

     * written) as status and consistency checks. (Also, field

     * "config" holds unchanging configuration state.)

     *

     * Field "ctl" contains 64 bits holding information needed to

     * atomically decide to add, inactivate, enqueue (on an event

     * queue), dequeue, and/or re-activate workers.  To enable this

     * packing, we restrict maximum parallelism to (1<<15)-1 (which is

     * far in excess of normal operating range) to allow ids, counts,

     * and their negations (used for thresholding) to fit into 16bit

     * subfields.

     *

     * Field "runState" holds lockable state bits (STARTED, STOP, etc)

     * also protecting updates to the workQueues array.  When used as

     * a lock, it is normally held only for a few instructions (the

     * only exceptions are one-time array initialization and uncommon

     * resizing), so is nearly always available after at most a brief

     * spin. But to be extra-cautious, after spinning, method

     * awaitRunStateLock (called only if an initial CAS fails), uses a

     * wait/notify mechanics on a builtin monitor to block when

     * (rarely) needed. This would be a terrible idea for a highly

     * contended lock, but most pools run without the lock ever

     * contending after the spin limit, so this works fine as a more

     * conservative alternative. Because we don't otherwise have an

     * internal Object to use as a monitor, the "stealCounter" (an

     * AtomicLong) is used when available (it too must be lazily

     * initialized; see externalSubmit).

     *

     * Usages of "runState" vs "ctl" interact in only one case:

     * deciding to add a worker thread (see tryAddWorker), in which

     * case the ctl CAS is performed while the lock is held.

     *

     * Recording WorkQueues.  WorkQueues are recorded in the

     * "workQueues" array. The array is created upon first use (see

     * externalSubmit) and expanded if necessary.  Updates to the

     * array while recording new workers and unrecording terminated

     * ones are protected from each other by the runState lock, but

     * the array is otherwise concurrently readable, and accessed

     * directly. We also ensure that reads of the array reference

     * itself never become too stale. To simplify index-based

     * operations, the array size is always a power of two, and all

     * readers must tolerate null slots. Worker queues are at odd

     * indices. Shared (submission) queues are at even indices, up to

     * a maximum of 64 slots, to limit growth even if array needs to

     * expand to add more workers. Grouping them together in this way

     * simplifies and speeds up task scanning.

     *

     * All worker thread creation is on-demand, triggered by task

     * submissions, replacement of terminated workers, and/or

     * compensation for blocked workers. However, all other support

     * code is set up to work with other policies.  To ensure that we

     * do not hold on to worker references that would prevent GC, All

     * accesses to workQueues are via indices into the workQueues

     * array (which is one source of some of the messy code

     * constructions here). In essence, the workQueues array serves as

     * a weak reference mechanism. Thus for example the stack top

     * subfield of ctl stores indices, not references.

     *

     * Queuing Idle Workers. Unlike HPC work-stealing frameworks, we

     * cannot let workers spin indefinitely scanning for tasks when

     * none can be found immediately, and we cannot start/resume

     * workers unless there appear to be tasks available.  On the

     * other hand, we must quickly prod them into action when new

     * tasks are submitted or generated. In many usages, ramp-up time

     * to activate workers is the main limiting factor in overall

     * performance, which is compounded at program start-up by JIT

     * compilation and allocation. So we streamline this as much as

     * possible.

     *

     * The "ctl" field atomically maintains active and total worker

     * counts as well as a queue to place waiting threads so they can

     * be located for signalling. Active counts also play the role of

     * quiescence indicators, so are decremented when workers believe

     * that there are no more tasks to execute. The "queue" is

     * actually a form of Treiber stack.  A stack is ideal for

     * activating threads in most-recently used order. This improves

     * performance and locality, outweighing the disadvantages of

     * being prone to contention and inability to release a worker

     * unless it is topmost on stack.  We park/unpark workers after

     * pushing on the idle worker stack (represented by the lower

     * 32bit subfield of ctl) when they cannot find work.  The top

     * stack state holds the value of the "scanState" field of the

     * worker: its index and status, plus a version counter that, in

     * addition to the count subfields (also serving as version

     * stamps) provide protection against Treiber stack ABA effects.

     *

     * Field scanState is used by both workers and the pool to manage

     * and track whether a worker is INACTIVE (possibly blocked

     * waiting for a signal), or SCANNING for tasks (when neither hold

     * it is busy running tasks).  When a worker is inactivated, its

     * scanState field is set, and is prevented from executing tasks,

     * even though it must scan once for them to avoid queuing

     * races. Note that scanState updates lag queue CAS releases so

     * usage requires care. When queued, the lower 16 bits of

     * scanState must hold its pool index. So we place the index there

     * upon initialization (see registerWorker) and otherwise keep it

     * there or restore it when necessary.

     *

     * Memory ordering.  See "Correct and Efficient Work-Stealing for

     * Weak Memory Models" by Le, Pop, Cohen, and Nardelli, PPoPP 2013

     * (http://www.di.ens.fr/~zappa/readings/ppopp13.pdf) for an

     * analysis of memory ordering requirements in work-stealing

     * algorithms similar to the one used here.  We usually need

     * stronger than minimal ordering because we must sometimes signal

     * workers, requiring Dekker-like full-fences to avoid lost

     * signals.  Arranging for enough ordering without expensive

     * over-fencing requires tradeoffs among the supported means of

     * expressing access constraints. The most central operations,

     * taking from queues and updating ctl state, require full-fence

     * CAS.  Array slots are read using the emulation of volatiles

     * provided by Unsafe.  Access from other threads to WorkQueue

     * base, top, and array requires a volatile load of the first of

     * any of these read.  We use the convention of declaring the

     * "base" index volatile, and always read it before other fields.

     * The owner thread must ensure ordered updates, so writes use

     * ordered intrinsics unless they can piggyback on those for other

     * writes.  Similar conventions and rationales hold for other

     * WorkQueue fields (such as "currentSteal") that are only written

     * by owners but observed by others.

     *

     * Creating workers. To create a worker, we pre-increment total

     * count (serving as a reservation), and attempt to construct a

     * ForkJoinWorkerThread via its factory. Upon construction, the

     * new thread invokes registerWorker, where it constructs a

     * WorkQueue and is assigned an index in the workQueues array

     * (expanding the array if necessary). The thread is then

     * started. Upon any exception across these steps, or null return

     * from factory, deregisterWorker adjusts counts and records

     * accordingly.  If a null return, the pool continues running with

     * fewer than the target number workers. If exceptional, the

     * exception is propagated, generally to some external caller.

     * Worker index assignment avoids the bias in scanning that would

     * occur if entries were sequentially packed starting at the front

     * of the workQueues array. We treat the array as a simple

     * power-of-two hash table, expanding as needed. The seedIndex

     * increment ensures no collisions until a resize is needed or a

     * worker is deregistered and replaced, and thereafter keeps

     * probability of collision low. We cannot use

     * ThreadLocalRandom.getProbe() for similar purposes here because

     * the thread has not started yet, but do so for creating

     * submission queues for existing external threads.

     *

     * Deactivation and waiting. Queuing encounters several intrinsic

     * races; most notably that a task-producing thread can miss

     * seeing (and signalling) another thread that gave up looking for

     * work but has not yet entered the wait queue.  When a worker

     * cannot find a task to steal, it deactivates and enqueues. Very

     * often, the lack of tasks is transient due to GC or OS

     * scheduling. To reduce false-alarm deactivation, scanners

     * compute checksums of queue states during sweeps.  (The

     * stability checks used here and elsewhere are probabilistic

     * variants of snapshot techniques -- see Herlihy & Shavit.)

     * Workers give up and try to deactivate only after the sum is

     * stable across scans. Further, to avoid missed signals, they

     * repeat this scanning process after successful enqueuing until

     * again stable.  In this state, the worker cannot take/run a task

     * it sees until it is released from the queue, so the worker

     * itself eventually tries to release itself or any successor (see

     * tryRelease).  Otherwise, upon an empty scan, a deactivated

     * worker uses an adaptive local spin construction (see awaitWork)

     * before blocking (via park). Note the unusual conventions about

     * Thread.interrupts surrounding parking and other blocking:

     * Because interrupts are used solely to alert threads to check

     * termination, which is checked anyway upon blocking, we clear

     * status (using Thread.interrupted) before any call to park, so

     * that park does not immediately return due to status being set

     * via some other unrelated call to interrupt in user code.

     *

     * Signalling and activation.  Workers are created or activated

     * only when there appears to be at least one task they might be

     * able to find and execute.  Upon push (either by a worker or an

     * external submission) to a previously (possibly) empty queue,

     * workers are signalled if idle, or created if fewer exist than

     * the given parallelism level.  These primary signals are

     * buttressed by others whenever other threads remove a task from

     * a queue and notice that there are other tasks there as well.

     * On most platforms, signalling (unpark) overhead time is

     * noticeably long, and the time between signalling a thread and

     * it actually making progress can be very noticeably long, so it

     * is worth offloading these delays from critical paths as much as

     * possible. Also, because inactive workers are often rescanning

     * or spinning rather than blocking, we set and clear the "parker"

     * field of WorkQueues to reduce unnecessary calls to unpark.

     * (This requires a secondary recheck to avoid missed signals.)

     *

     * Trimming workers. To release resources after periods of lack of

     * use, a worker starting to wait when the pool is quiescent will

     * time out and terminate (see awaitWork) if the pool has remained

     * quiescent for period IDLE_TIMEOUT, increasing the period as the

     * number of threads decreases, eventually removing all workers.

     * Also, when more than two spare threads exist, excess threads

     * are immediately terminated at the next quiescent point.

     * (Padding by two avoids hysteresis.)

     *

     * Shutdown and Termination. A call to shutdownNow invokes

     * tryTerminate to atomically set a runState bit. The calling

     * thread, as well as every other worker thereafter terminating,

     * helps terminate others by setting their (qlock) status,

     * cancelling their unprocessed tasks, and waking them up, doing

     * so repeatedly until stable (but with a loop bounded by the

     * number of workers).  Calls to non-abrupt shutdown() preface

     * this by checking whether termination should commence. This

     * relies primarily on the active count bits of "ctl" maintaining

     * consensus -- tryTerminate is called from awaitWork whenever

     * quiescent. However, external submitters do not take part in

     * this consensus.  So, tryTerminate sweeps through queues (until

     * stable) to ensure lack of in-flight submissions and workers

     * about to process them before triggering the "STOP" phase of

     * termination. (Note: there is an intrinsic conflict if

     * helpQuiescePool is called when shutdown is enabled. Both wait

     * for quiescence, but tryTerminate is biased to not trigger until

     * helpQuiescePool completes.)

     *

     *

     * Joining Tasks

     * =============

     *

     * Any of several actions may be taken when one worker is waiting

     * to join a task stolen (or always held) by another.  Because we

     * are multiplexing many tasks on to a pool of workers, we can't

     * just let them block (as in Thread.join).  We also cannot just

     * reassign the joiner's run-time stack with another and replace

     * it later, which would be a form of "continuation", that even if

     * possible is not necessarily a good idea since we may need both

     * an unblocked task and its continuation to progress.  Instead we

     * combine two tactics:

     *

     *   Helping: Arranging for the joiner to execute some task that it

     *      would be running if the steal had not occurred.

     *

     *   Compensating: Unless there are already enough live threads,

     *      method tryCompensate() may create or re-activate a spare

     *      thread to compensate for blocked joiners until they unblock.

     *

     * A third form (implemented in tryRemoveAndExec) amounts to

     * helping a hypothetical compensator: If we can readily tell that

     * a possible action of a compensator is to steal and execute the

     * task being joined, the joining thread can do so directly,

     * without the need for a compensation thread (although at the

     * expense of larger run-time stacks, but the tradeoff is

     * typically worthwhile).

     *

     * The ManagedBlocker extension API can't use helping so relies

     * only on compensation in method awaitBlocker.

     *

     * The algorithm in helpStealer entails a form of "linear

     * helping".  Each worker records (in field currentSteal) the most

     * recent task it stole from some other worker (or a submission).

     * It also records (in field currentJoin) the task it is currently

     * actively joining. Method helpStealer uses these markers to try

     * to find a worker to help (i.e., steal back a task from and

     * execute it) that could hasten completion of the actively joined

     * task.  Thus, the joiner executes a task that would be on its

     * own local deque had the to-be-joined task not been stolen. This

     * is a conservative variant of the approach described in Wagner &

     * Calder "Leapfrogging: a portable technique for implementing

     * efficient futures" SIGPLAN Notices, 1993

     * (http://portal.acm.org/citation.cfm?id=155354). It differs in

     * that: (1) We only maintain dependency links across workers upon

     * steals, rather than use per-task bookkeeping.  This sometimes

     * requires a linear scan of workQueues array to locate stealers,

     * but often doesn't because stealers leave hints (that may become

     * stale/wrong) of where to locate them.  It is only a hint

     * because a worker might have had multiple steals and the hint

     * records only one of them (usually the most current).  Hinting

     * isolates cost to when it is needed, rather than adding to

     * per-task overhead.  (2) It is "shallow", ignoring nesting and

     * potentially cyclic mutual steals.  (3) It is intentionally

     * racy: field currentJoin is updated only while actively joining,

     * which means that we miss links in the chain during long-lived

     * tasks, GC stalls etc (which is OK since blocking in such cases

     * is usually a good idea).  (4) We bound the number of attempts

     * to find work using checksums and fall back to suspending the

     * worker and if necessary replacing it with another.

     *

     * Helping actions for CountedCompleters do not require tracking

     * currentJoins: Method helpComplete takes and executes any task

     * with the same root as the task being waited on (preferring

     * local pops to non-local polls). However, this still entails

     * some traversal of completer chains, so is less efficient than

     * using CountedCompleters without explicit joins.

     *

     * Compensation does not aim to keep exactly the target

     * parallelism number of unblocked threads running at any given

     * time. Some previous versions of this class employed immediate

     * compensations for any blocked join. However, in practice, the

     * vast majority of blockages are transient byproducts of GC and

     * other JVM or OS activities that are made worse by replacement.

     * Currently, compensation is attempted only after validating that

     * all purportedly active threads are processing tasks by checking

     * field WorkQueue.scanState, which eliminates most false

     * positives.  Also, compensation is bypassed (tolerating fewer

     * threads) in the most common case in which it is rarely

     * beneficial: when a worker with an empty queue (thus no

     * continuation tasks) blocks on a join and there still remain

     * enough threads to ensure liveness.

     *

     * The compensation mechanism may be bounded.  Bounds for the

     * commonPool (see commonMaxSpares) better enable JVMs to cope

     * with programming errors and abuse before running out of

     * resources to do so. In other cases, users may supply factories

     * that limit thread construction. The effects of bounding in this

     * pool (like all others) is imprecise.  Total worker counts are

     * decremented when threads deregister, not when they exit and

     * resources are reclaimed by the JVM and OS. So the number of

     * simultaneously live threads may transiently exceed bounds.

     *

     * Common Pool

     * ===========

     *

     * The static common pool always exists after static

     * initialization.  Since it (or any other created pool) need

     * never be used, we minimize initial construction overhead and

     * footprint to the setup of about a dozen fields, with no nested

     * allocation. Most bootstrapping occurs within method

     * externalSubmit during the first submission to the pool.

     *

     * When external threads submit to the common pool, they can

     * perform subtask processing (see externalHelpComplete and

     * related methods) upon joins.  This caller-helps policy makes it

     * sensible to set common pool parallelism level to one (or more)

     * less than the total number of available cores, or even zero for

     * pure caller-runs.  We do not need to record whether external

     * submissions are to the common pool -- if not, external help

     * methods return quickly. These submitters would otherwise be

     * blocked waiting for completion, so the extra effort (with

     * liberally sprinkled task status checks) in inapplicable cases

     * amounts to an odd form of limited spin-wait before blocking in

     * ForkJoinTask.join.

     *

     * As a more appropriate default in managed environments, unless

     * overridden by system properties, we use workers of subclass

     * InnocuousForkJoinWorkerThread when there is a SecurityManager

     * present. These workers have no permissions set, do not belong

     * to any user-defined ThreadGroup, and erase all ThreadLocals

     * after executing any top-level task (see WorkQueue.runTask).

     * The associated mechanics (mainly in ForkJoinWorkerThread) may

     * be JVM-dependent and must access particular Thread class fields

     * to achieve this effect.

     *

     * Style notes

     * ===========

     *

     * Memory ordering relies mainly on Unsafe intrinsics that carry

     * the further responsibility of explicitly performing null- and

     * bounds- checks otherwise carried out implicitly by JVMs.  This

     * can be awkward and ugly, but also reflects the need to control

     * outcomes across the unusual cases that arise in very racy code

     * with very few invariants. So these explicit checks would exist

     * in some form anyway.  All fields are read into locals before

     * use, and null-checked if they are references.  This is usually

     * done in a "C"-like style of listing declarations at the heads

     * of methods or blocks, and using inline assignments on first

     * encounter.  Array bounds-checks are usually performed by

     * masking with array.length-1, which relies on the invariant that

     * these arrays are created with positive lengths, which is itself

     * paranoically checked. Nearly all explicit checks lead to

     * bypass/return, not exception throws, because they may

     * legitimately arise due to cancellation/revocation during

     * shutdown.

     *

     * There is a lot of representation-level coupling among classes

     * ForkJoinPool, ForkJoinWorkerThread, and ForkJoinTask.  The

     * fields of WorkQueue maintain data structures managed by

     * ForkJoinPool, so are directly accessed.  There is little point

     * trying to reduce this, since any associated future changes in

     * representations will need to be accompanied by algorithmic

     * changes anyway. Several methods intrinsically sprawl because

     * they must accumulate sets of consistent reads of fields held in

     * local variables.  There are also other coding oddities

     * (including several unnecessary-looking hoisted null checks)

     * that help some methods perform reasonably even when interpreted

     * (not compiled).

     *

     * The order of declarations in this file is (with a few exceptions):

     * (1) Static utility functions

     * (2) Nested (static) classes

     * (3) Static fields

     * (4) Fields, along with constants used when unpacking some of them

     * (5) Internal control methods

     * (6) Callbacks and other support for ForkJoinTask methods

     * (7) Exported methods

     * (8) Static block initializing statics in minimally dependent order

     */

    // Static utilities

    /**

     * If there is a security manager, makes sure caller has

     * permission to modify threads.

     */

    private static void checkPermission() {

        SecurityManager security = System.getSecurityManager();

        if (security != null)

            security.checkPermission(modifyThreadPermission);

    }

    // Nested classes

    /**

     * Factory for creating new {@link ForkJoinWorkerThread}s.

     * A {@code ForkJoinWorkerThreadFactory} must be defined and used

     * for {@code ForkJoinWorkerThread} subclasses that extend base

     * functionality or initialize threads with different contexts.

     */

    public static interface ForkJoinWorkerThreadFactory {

        /**

         * Returns a new worker thread operating in the given pool.

         *

         * @param pool the pool this thread works in

         * @return the new worker thread

         * @throws NullPointerException if the pool is null

         */

        public ForkJoinWorkerThread newThread(ForkJoinPool pool);

    }

    /**

     * Default ForkJoinWorkerThreadFactory implementation; creates a

     * new ForkJoinWorkerThread.

     */

    static final class DefaultForkJoinWorkerThreadFactory

        implements ForkJoinWorkerThreadFactory {

        public final ForkJoinWorkerThread newThread(ForkJoinPool pool) {

            return new ForkJoinWorkerThread(pool);

        }

    }

    /**

     * Class for artificial tasks that are used to replace the target

     * of local joins if they are removed from an interior queue slot

     * in WorkQueue.tryRemoveAndExec. We don't need the proxy to

     * actually do anything beyond having a unique identity.

     */

    static final class EmptyTask extends ForkJoinTask<Void> {

        private static final long serialVersionUID = -7721805057305804111L;

        EmptyTask() { status = ForkJoinTask.NORMAL; } // force done

        public final Void getRawResult() { return null; }

        public final void setRawResult(Void x) {}

        public final boolean exec() { return true; }

    }

    // Constants shared across ForkJoinPool and WorkQueue

    // Bounds

    static final int SMASK        = 0xffff;        // short bits == max index

    static final int MAX_CAP      = 0x7fff;        // max #workers - 1

    static final int EVENMASK     = 0xfffe;        // even short bits

    static final int SQMASK       = 0x007e;        // max 64 (even) slots

    // Masks and units for WorkQueue.scanState and ctl sp subfield

    static final int SCANNING     = 1;             // false when running tasks

    static final int INACTIVE     = 1 << 31;       // must be negative

    static final int SS_SEQ       = 1 << 16;       // version count

    // Mode bits for ForkJoinPool.config and WorkQueue.config

    static final int MODE_MASK    = 0xffff << 16;  // top half of int

    static final int LIFO_QUEUE   = 0;

    static final int FIFO_QUEUE   = 1 << 16;

    static final int SHARED_QUEUE = 1 << 31;       // must be negative

    /**

     * Queues supporting work-stealing as well as external task

     * submission. See above for descriptions and algorithms.

     * Performance on most platforms is very sensitive to placement of

     * instances of both WorkQueues and their arrays -- we absolutely

     * do not want multiple WorkQueue instances or multiple queue

     * arrays sharing cache lines. The @Contended annotation alerts

     * JVMs to try to keep instances apart.

     */

    @sun.misc.Contended

    static final class WorkQueue {

        /**

         * Capacity of work-stealing queue array upon initialization.

         * Must be a power of two; at least 4, but should be larger to

         * reduce or eliminate cacheline sharing among queues.

         * Currently, it is much larger, as a partial workaround for

         * the fact that JVMs often place arrays in locations that

         * share GC bookkeeping (especially cardmarks) such that

         * per-write accesses encounter serious memory contention.

         */

        static final int INITIAL_QUEUE_CAPACITY = 1 << 13;

        /**

         * Maximum size for queue arrays. Must be a power of two less

         * than or equal to 1 << (31 - width of array entry) to ensure

         * lack of wraparound of index calculations, but defined to a

         * value a bit less than this to help users trap runaway

         * programs before saturating systems.

         */

        static final int MAXIMUM_QUEUE_CAPACITY = 1 << 26; // 64M

        // Instance fields

        volatile int scanState;    // versioned, <0: inactive; odd:scanning

        int stackPred;             // pool stack (ctl) predecessor

        int nsteals;               // number of steals

        int hint;                  // randomization and stealer index hint

        int config;                // pool index and mode

        volatile int qlock;        // 1: locked, < 0: terminate; else 0

        volatile int base;         // index of next slot for poll

        int top;                   // index of next slot for push

        ForkJoinTask<?>[] array;   // the elements (initially unallocated)

        final ForkJoinPool pool;   // the containing pool (may be null)

        final ForkJoinWorkerThread owner; // owning thread or null if shared

        volatile Thread parker;    // == owner during call to park; else null

        volatile ForkJoinTask<?> currentJoin;  // task being joined in awaitJoin

        volatile ForkJoinTask<?> currentSteal; // mainly used by helpStealer

        WorkQueue(ForkJoinPool pool, ForkJoinWorkerThread owner) {

            this.pool = pool;

            this.owner = owner;

            // Place indices in the center of array (that is not yet allocated)

            base = top = INITIAL_QUEUE_CAPACITY >>> 1;

        }

        /**

         * Returns an exportable index (used by ForkJoinWorkerThread).

         */

        final int getPoolIndex() {

            return (config & 0xffff) >>> 1; // ignore odd/even tag bit

        }

        /**

         * Returns the approximate number of tasks in the queue.

         */

        final int queueSize() {

            int n = base - top;       // non-owner callers must read base first

            return (n >= 0) ? 0 : -n; // ignore transient negative

        }

        /**

         * Provides a more accurate estimate of whether this queue has

         * any tasks than does queueSize, by checking whether a

         * near-empty queue has at least one unclaimed task.

         */

        final boolean isEmpty() {

            ForkJoinTask<?>[] a; int n, m, s;

            return ((n = base - (s = top)) >= 0 ||

                    (n == -1 &&           // possibly one task

                     ((a = array) == null || (m = a.length - 1) < 0 ||

                      U.getObject

                      (a, (long)((m & (s - 1)) << ASHIFT) + ABASE) == null)));

        }

        /**

         * Pushes a task. Call only by owner in unshared queues.  (The

         * shared-queue version is embedded in method externalPush.)

         *

         * @param task the task. Caller must ensure non-null.

         * @throws RejectedExecutionException if array cannot be resized

         */

        final void push(ForkJoinTask<?> task) {

            ForkJoinTask<?>[] a; ForkJoinPool p;

            int b = base, s = top, n;

            if ((a = array) != null) {    // ignore if queue removed

                int m = a.length - 1;     // fenced write for task visibility

                U.putOrderedObject(a, ((m & s) << ASHIFT) + ABASE, task);

                U.putOrderedInt(this, QTOP, s + 1);

                if ((n = s - b) <= 1) {

                    if ((p = pool) != null)

                        p.signalWork(p.workQueues, this);

                }

                else if (n >= m)

                    growArray();

            }

        }

        /**

         * Initializes or doubles the capacity of array. Call either

         * by owner or with lock held -- it is OK for base, but not

         * top, to move while resizings are in progress.

         */

        final ForkJoinTask<?>[] growArray() {

            ForkJoinTask<?>[] oldA = array;

            int size = oldA != null ? oldA.length << 1 : INITIAL_QUEUE_CAPACITY;

            if (size > MAXIMUM_QUEUE_CAPACITY)

                throw new RejectedExecutionException("Queue capacity exceeded");

            int oldMask, t, b;

            ForkJoinTask<?>[] a = array = new ForkJoinTask<?>[size];

            if (oldA != null && (oldMask = oldA.length - 1) >= 0 &&

                (t = top) - (b = base) > 0) {

                int mask = size - 1;

                do { // emulate poll from old array, push to new array

                    ForkJoinTask<?> x;

                    int oldj = ((b & oldMask) << ASHIFT) + ABASE;

                    int j    = ((b &    mask) << ASHIFT) + ABASE;

                    x = (ForkJoinTask<?>)U.getObjectVolatile(oldA, oldj);

                    if (x != null &&

                        U.compareAndSwapObject(oldA, oldj, x, null))

                        U.putObjectVolatile(a, j, x);

                } while (++b != t);

            }

            return a;

        }

        /**

         * Takes next task, if one exists, in LIFO order.  Call only

         * by owner in unshared queues.

         */

        final ForkJoinTask<?> pop() {

            ForkJoinTask<?>[] a; ForkJoinTask<?> t; int m;

            if ((a = array) != null && (m = a.length - 1) >= 0) {

                for (int s; (s = top - 1) - base >= 0;) {

                    long j = ((m & s) << ASHIFT) + ABASE;

                    if ((t = (ForkJoinTask<?>)U.getObject(a, j)) == null)

                        break;

                    if (U.compareAndSwapObject(a, j, t, null)) {

                        U.putOrderedInt(this, QTOP, s);

                        return t;

                    }

                }

            }

            return null;

        }

        /**

         * Takes a task in FIFO order if b is base of queue and a task

         * can be claimed without contention. Specialized versions

         * appear in ForkJoinPool methods scan and helpStealer.

         */

        final ForkJoinTask<?> pollAt(int b) {

            ForkJoinTask<?> t; ForkJoinTask<?>[] a;

            if ((a = array) != null) {

                int j = (((a.length - 1) & b) << ASHIFT) + ABASE;

                if ((t = (ForkJoinTask<?>)U.getObjectVolatile(a, j)) != null &&

                    base == b && U.compareAndSwapObject(a, j, t, null)) {

                    base = b + 1;

                    return t;

                }

            }

            return null;

        }

        /**

         * Takes next task, if one exists, in FIFO order.

         */

        final ForkJoinTask<?> poll() {

            ForkJoinTask<?>[] a; int b; ForkJoinTask<?> t;

            while ((b = base) - top < 0 && (a = array) != null) {

                int j = (((a.length - 1) & b) << ASHIFT) + ABASE;

                t = (ForkJoinTask<?>)U.getObjectVolatile(a, j);

                if (base == b) {

                    if (t != null) {

                        if (U.compareAndSwapObject(a, j, t, null)) {

                            base = b + 1;

                            return t;

                        }

                    }

                    else if (b + 1 == top) // now empty

                        break;

                }

            }

            return null;

        }

        /**

         * Takes next task, if one exists, in order specified by mode.

         */

        final ForkJoinTask<?> nextLocalTask() {

            return (config & FIFO_QUEUE) == 0 ? pop() : poll();

        }

        /**

         * Returns next task, if one exists, in order specified by mode.

         */

        final ForkJoinTask<?> peek() {

            ForkJoinTask<?>[] a = array; int m;

            if (a == null || (m = a.length - 1) < 0)

                return null;

            int i = (config & FIFO_QUEUE) == 0 ? top - 1 : base;

            int j = ((i & m) << ASHIFT) + ABASE;

            return (ForkJoinTask<?>)U.getObjectVolatile(a, j);

        }

        /**

         * Pops the given task only if it is at the current top.

         * (A shared version is available only via FJP.tryExternalUnpush)

        */

        final boolean tryUnpush(ForkJoinTask<?> t) {

            ForkJoinTask<?>[] a; int s;

            if ((a = array) != null && (s = top) != base &&

                U.compareAndSwapObject

                (a, (((a.length - 1) & --s) << ASHIFT) + ABASE, t, null)) {

                U.putOrderedInt(this, QTOP, s);

                return true;

            }

            return false;

        }

        /**

         * Removes and cancels all known tasks, ignoring any exceptions.

         */

        final void cancelAll() {

            ForkJoinTask<?> t;

            if ((t = currentJoin) != null) {

                currentJoin = null;

                ForkJoinTask.cancelIgnoringExceptions(t);

            }

            if ((t = currentSteal) != null) {

                currentSteal = null;

                ForkJoinTask.cancelIgnoringExceptions(t);

            }

            while ((t = poll()) != null)

                ForkJoinTask.cancelIgnoringExceptions(t);

        }

        // Specialized execution methods

        /**

         * Polls and runs tasks until empty.

         */

        final void pollAndExecAll() {

            for (ForkJoinTask<?> t; (t = poll()) != null;)

                t.doExec();

        }

        /**

         * Removes and executes all local tasks. If LIFO, invokes

         * pollAndExecAll. Otherwise implements a specialized pop loop

         * to exec until empty.

         */

        final void execLocalTasks() {

            int b = base, m, s;

            ForkJoinTask<?>[] a = array;

            if (b - (s = top - 1) <= 0 && a != null &&

                (m = a.length - 1) >= 0) {

                if ((config & FIFO_QUEUE) == 0) {

                    for (ForkJoinTask<?> t;;) {

                        if ((t = (ForkJoinTask<?>)U.getAndSetObject

                             (a, ((m & s) << ASHIFT) + ABASE, null)) == null)

                            break;

                        U.putOrderedInt(this, QTOP, s);

                        t.doExec();

                        if (base - (s = top - 1) > 0)

                            break;

                    }

                }

                else

                    pollAndExecAll();

            }

        }

        /**

         * Executes the given task and any remaining local tasks.

         */

        final void runTask(ForkJoinTask<?> task) {

            if (task != null) {

                scanState &= ~SCANNING; // mark as busy

                (currentSteal = task).doExec();

                U.putOrderedObject(this, QCURRENTSTEAL, null); // release for GC

                execLocalTasks();

                ForkJoinWorkerThread thread = owner;

                if (++nsteals < 0)      // collect on overflow

                    transferStealCount(pool);

                scanState |= SCANNING;

                if (thread != null)

                    thread.afterTopLevelExec();

            }

        }

        /**

         * Adds steal count to pool stealCounter if it exists, and resets.

         */

        final void transferStealCount(ForkJoinPool p) {

            AtomicLong sc;

            if (p != null && (sc = p.stealCounter) != null) {

                int s = nsteals;

                nsteals = 0;            // if negative, correct for overflow

                sc.getAndAdd((long)(s < 0 ? Integer.MAX_VALUE : s));

            }

        }

        /**

         * If present, removes from queue and executes the given task,

         * or any other cancelled task. Used only by awaitJoin.

         *

         * @return true if queue empty and task not known to be done

         */

        final boolean tryRemoveAndExec(ForkJoinTask<?> task) {

            ForkJoinTask<?>[] a; int m, s, b, n;

            if ((a = array) != null && (m = a.length - 1) >= 0 &&

                task != null) {

                while ((n = (s = top) - (b = base)) > 0) {

                    for (ForkJoinTask<?> t;;) {      // traverse from s to b

                        long j = ((--s & m) << ASHIFT) + ABASE;

                        if ((t = (ForkJoinTask<?>)U.getObject(a, j)) == null)

                            return s + 1 == top;     // shorter than expected

                        else if (t == task) {

                            boolean removed = false;

                            if (s + 1 == top) {      // pop

                                if (U.compareAndSwapObject(a, j, task, null)) {

                                    U.putOrderedInt(this, QTOP, s);

                                    removed = true;

                                }

                            }

                            else if (base == b)      // replace with proxy

                                removed = U.compareAndSwapObject(

                                    a, j, task, new EmptyTask());

                            if (removed)

                                task.doExec();

                            break;

                        }

                        else if (t.status < 0 && s + 1 == top) {

                            if (U.compareAndSwapObject(a, j, t, null))

                                U.putOrderedInt(this, QTOP, s);

                            break;                  // was cancelled

                        }

                        if (--n == 0)

                            return false;

                    }

                    if (task.status < 0)

                        return false;

                }

            }

            return true;

        }

        /**

         * Pops task if in the same CC computation as the given task,

         * in either shared or owned mode. Used only by helpComplete.

         */

        final CountedCompleter<?> popCC(CountedCompleter<?> task, int mode) {

            int s; ForkJoinTask<?>[] a; Object o;

            if (base - (s = top) < 0 && (a = array) != null) {

                long j = (((a.length - 1) & (s - 1)) << ASHIFT) + ABASE;

                if ((o = U.getObjectVolatile(a, j)) != null &&

                    (o instanceof CountedCompleter)) {

                    CountedCompleter<?> t = (CountedCompleter<?>)o;

                    for (CountedCompleter<?> r = t;;) {

                        if (r == task) {

                            if (mode < 0) { // must lock

                                if (U.compareAndSwapInt(this, QLOCK, 0, 1)) {

                                    if (top == s && array == a &&

                                        U.compareAndSwapObject(a, j, t, null)) {

                                        U.putOrderedInt(this, QTOP, s - 1);

                                        U.putOrderedInt(this, QLOCK, 0);

                                        return t;

                                    }

                                    U.compareAndSwapInt(this, QLOCK, 1, 0);

                                }

                            }

                            else if (U.compareAndSwapObject(a, j, t, null)) {

                                U.putOrderedInt(this, QTOP, s - 1);

                                return t;

                            }

                            break;

                        }

                        else if ((r = r.completer) == null) // try parent

                            break;

                    }

                }

            }

            return null;

        }

        /**

         * Steals and runs a task in the same CC computation as the

         * given task if one exists and can be taken without

         * contention. Otherwise returns a checksum/control value for

         * use by method helpComplete.

         *

         * @return 1 if successful, 2 if retryable (lost to another

         * stealer), -1 if non-empty but no matching task found, else

         * the base index, forced negative.

         */

        final int pollAndExecCC(CountedCompleter<?> task) {

            int b, h; ForkJoinTask<?>[] a; Object o;

            if ((b = base) - top >= 0 || (a = array) == null)

                h = b | Integer.MIN_VALUE;  // to sense movement on re-poll

            else {

                long j = (((a.length - 1) & b) << ASHIFT) + ABASE;

                if ((o = U.getObjectVolatile(a, j)) == null)

                    h = 2;                  // retryable

                else if (!(o instanceof CountedCompleter))

                    h = -1;                 // unmatchable

                else {

                    CountedCompleter<?> t = (CountedCompleter<?>)o;

                    for (CountedCompleter<?> r = t;;) {

                        if (r == task) {

                            if (base == b &&

                                U.compareAndSwapObject(a, j, t, null)) {

                                base = b + 1;

                                t.doExec();

                                h = 1;      // success

                            }

                            else

                                h = 2;      // lost CAS

                            break;

                        }

                        else if ((r = r.completer) == null) {

                            h = -1;         // unmatched

                            break;

                        }

                    }

                }

            }

            return h;

        }

        /**

         * Returns true if owned and not known to be blocked.

         */

        final boolean isApparentlyUnblocked() {

            Thread wt; Thread.State s;

            return (scanState >= 0 &&

                    (wt = owner) != null &&

                    (s = wt.getState()) != Thread.State.BLOCKED &&

                    s != Thread.State.WAITING &&

                    s != Thread.State.TIMED_WAITING);

        }

        // Unsafe mechanics. Note that some are (and must be) the same as in FJP

        private static final sun.misc.Unsafe U;

        private static final int  ABASE;

        private static final int  ASHIFT;

        private static final long QTOP;

        private static final long QLOCK;

        private static final long QCURRENTSTEAL;

        static {

            try {

                U = sun.misc.Unsafe.getUnsafe();

                Class<?> wk = WorkQueue.class;

                Class<?> ak = ForkJoinTask[].class;

                QTOP = U.objectFieldOffset

                    (wk.getDeclaredField("top"));

                QLOCK = U.objectFieldOffset

                    (wk.getDeclaredField("qlock"));

                QCURRENTSTEAL = U.objectFieldOffset

                    (wk.getDeclaredField("currentSteal"));

                ABASE = U.arrayBaseOffset(ak);

                int scale = U.arrayIndexScale(ak);

                if ((scale & (scale - 1)) != 0)

                    throw new Error("data type scale not a power of two");

                ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);

            } catch (Exception e) {

                throw new Error(e);

            }

        }

    }

    // static fields (initialized in static initializer below)

    /**

     * Creates a new ForkJoinWorkerThread. This factory is used unless

     * overridden in ForkJoinPool constructors.

     */

    public static final ForkJoinWorkerThreadFactory

        defaultForkJoinWorkerThreadFactory;

    /**

     * Permission required for callers of methods that may start or

     * kill threads.

     */

    private static final RuntimePermission modifyThreadPermission;

    /**

     * Common (static) pool. Non-null for public use unless a static

     * construction exception, but internal usages null-check on use

     * to paranoically avoid potential initialization circularities

     * as well as to simplify generated code.

     */

    static final ForkJoinPool common;

    /**

     * Common pool parallelism. To allow simpler use and management

     * when common pool threads are disabled, we allow the underlying

     * common.parallelism field to be zero, but in that case still report

     * parallelism as 1 to reflect resulting caller-runs mechanics.

     */

    static final int commonParallelism;

    /**

     * Limit on spare thread construction in tryCompensate.

     */

    private static int commonMaxSpares;

    /**

     * Sequence number for creating workerNamePrefix.

     */

    private static int poolNumberSequence;

    /**

     * Returns the next sequence number. We don't expect this to

     * ever contend, so use simple builtin sync.

     */

    private static final synchronized int nextPoolId() {

        return ++poolNumberSequence;

    }

    // static configuration constants

    /**

     * Initial timeout value (in nanoseconds) for the thread

     * triggering quiescence to park waiting for new work. On timeout,

     * the thread will instead try to shrink the number of

     * workers. The value should be large enough to avoid overly

     * aggressive shrinkage during most transient stalls (long GCs

     * etc).

     */

    private static final long IDLE_TIMEOUT = 2000L * 1000L * 1000L; // 2sec

    /**

     * Tolerance for idle timeouts, to cope with timer undershoots

     */

    private static final long TIMEOUT_SLOP = 20L * 1000L * 1000L;  // 20ms

    /**

     * The initial value for commonMaxSpares during static

     * initialization. The value is far in excess of normal

     * requirements, but also far short of MAX_CAP and typical

     * OS thread limits, so allows JVMs to catch misuse/abuse

     * before running out of resources needed to do so.

     */

    private static final int DEFAULT_COMMON_MAX_SPARES = 256;

    /**

     * Number of times to spin-wait before blocking. The spins (in

     * awaitRunStateLock and awaitWork) currently use randomized

     * spins. Currently set to zero to reduce CPU usage.

     *

     * If greater than zero the value of SPINS must be a power

     * of two, at least 4.  A value of 2048 causes spinning for a

     * small fraction of typical context-switch times.

     *

     * If/when MWAIT-like intrinsics becomes available, they

     * may allow quieter spinning.

     */

    private static final int SPINS  = 0;

    /**

     * Increment for seed generators. See class ThreadLocal for

     * explanation.

     */

    private static final int SEED_INCREMENT = 0x9e3779b9;

    /*

     * Bits and masks for field ctl, packed with 4 16 bit subfields:

     * AC: Number of active running workers minus target parallelism

     * TC: Number of total workers minus target parallelism

     * SS: version count and status of top waiting thread

     * ID: poolIndex of top of Treiber stack of waiters

     *

     * When convenient, we can extract the lower 32 stack top bits

     * (including version bits) as sp=(int)ctl.  The offsets of counts

     * by the target parallelism and the positionings of fields makes

     * it possible to perform the most common checks via sign tests of

     * fields: When ac is negative, there are not enough active

     * workers, when tc is negative, there are not enough total

     * workers.  When sp is non-zero, there are waiting workers.  To

     * deal with possibly negative fields, we use casts in and out of

     * "short" and/or signed shifts to maintain signedness.

     *

     * Because it occupies uppermost bits, we can add one active count

     * using getAndAddLong of AC_UNIT, rather than CAS, when returning

     * from a blocked join.  Other updates entail multiple subfields

     * and masking, requiring CAS.

     */

    // Lower and upper word masks

    private static final long SP_MASK    = 0xffffffffL;

    private static final long UC_MASK    = ~SP_MASK;

    // Active counts

    private static final int  AC_SHIFT   = 48;

    private static final long AC_UNIT    = 0x0001L << AC_SHIFT;

    private static final long AC_MASK    = 0xffffL << AC_SHIFT;

    // Total counts

    private static final int  TC_SHIFT   = 32;

    private static final long TC_UNIT    = 0x0001L << TC_SHIFT;

    private static final long TC_MASK    = 0xffffL << TC_SHIFT;

    private static final long ADD_WORKER = 0x0001L << (TC_SHIFT + 15); // sign

    // runState bits: SHUTDOWN must be negative, others arbitrary powers of two

    private static final int  RSLOCK     = 1;

    private static final int  RSIGNAL    = 1 << 1;

    private static final int  STARTED    = 1 << 2;

    private static final int  STOP       = 1 << 29;

    private static final int  TERMINATED = 1 << 30;

    private static final int  SHUTDOWN   = 1 << 31;

    // Instance fields

    volatile long ctl;                   // main pool control

    volatile int runState;               // lockable status

    final int config;                    // parallelism, mode