jdk-sandbox: comparison jdk/src/java.base/share/classes/java/util/concurrent/ForkJoinPool.java

equal deleted inserted replaced

-:5da963ed0720
+:5853628b0e63
 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;
 /**
 * 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
+* level; by default, equal to the number of available processors.
-* pool attempts to maintain enough active (or available) threads by
+* The pool attempts to maintain enough active (or available) threads
-* dynamically adding, suspending, or resuming internal worker
+* 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.
 * - 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}
+* <li>{@code java.util.concurrent.ForkJoinPool.common.maximumSpares}
+* - the maximum number of allowed extra threads to maintain target
+* parallelism (default 256).
 * </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.
 * 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.
+* 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
 * 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).
-* See also "Correct and Efficient Work-Stealing for Weak Memory
+* The main differences ultimately stem from GC requirements that
-* Models" by Le, Pop, Cohen, and Nardelli, PPoPP 2013
+* we null out taken slots as soon as we can, to maintain as small
-* (http://www.di.ens.fr/~zappa/readings/ppopp13.pdf) for an
+* a footprint as possible even in programs generating huge
-* analysis of memory ordering (atomic, volatile etc) issues.  The
+* numbers of tasks. To accomplish this, we shift the CAS
-* main differences ultimately stem from GC requirements that we
+* arbitrating pop vs poll (steal) from being on the indices
-* null out taken slots as soon as we can, to maintain as small a
+* ("base" and "top") to the slots themselves.
-* footprint as possible even in programs generating huge numbers
+*
-* of tasks. To accomplish this, we shift the CAS arbitrating pop
+* Adding tasks then takes the form of a classic array push(task):
-* vs poll (steal) from being on the indices ("base" and "top") to
+*    q.array[q.top] = task; ++q.top;
-* the slots themselves.  So, both a successful pop and poll
+*
-* mainly entail a CAS of a slot from non-null to null.  Because
+* (The actual code needs to null-check and size-check the array,
-* we rely on CASes of references, we do not need tag bits on base
+* properly fence the accesses, and possibly signal waiting
-* or top.  They are simple ints as used in any circular
+* 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 must still be ordered in a way that guarantees that top
+* indices guarantee that top == base means the queue is empty,
-* == base means the queue is empty, but otherwise may err on the
+* but otherwise may err on the side of possibly making the queue
-* side of possibly making the queue appear nonempty when a push,
+* appear nonempty when a push, pop, or poll have not fully
-* pop, or poll have not fully committed. Note that this means
+* committed. (Method isEmpty() checks the case of a partially
-* that the poll operation, considered individually, is not
+* completed removal of the last element.)  Because of this, the
-* wait-free. One thief cannot successfully continue until another
+* poll operation, considered individually, is not wait-free. One
-* in-progress one (or, if previously empty, a push) completes.
+* thief cannot successfully continue until another in-progress
-* However, in the aggregate, we ensure at least probabilistic
+* 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.)
+* 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
+* This approach also enables support of a user mode in which
-* poll rather than pop.  This can be useful in message-passing
+* local task processing is in FIFO, not LIFO order, simply by
-* frameworks in which tasks are never joined.  However neither
+* using poll rather than pop.  This can be useful in
-* mode considers affinities, loads, cache localities, etc, so
+* message-passing frameworks in which tasks are never joined.
-* rarely provide the best possible performance on a given
+* However neither mode considers affinities, loads, cache
-* machine, but portably provide good throughput by averaging over
+* localities, etc, so rarely provide the best possible
-* these factors.  (Further, even if we did try to use such
+* performance on a given machine, but portably provide good
-* information, we do not usually have a basis for exploiting it.
+* throughput by averaging over these factors.  Further, even if
-* For example, some sets of tasks profit from cache affinities,
+* we did try to use such information, we do not usually have a
-* but others are harmed by cache pollution effects.)
+* 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
-* for work-stealing (this would contaminate lifo/fifo
+* by workers. Instead, we randomly associate submission queues
-* processing). 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).  However, because most
+* others with the same root task).  Insertion of tasks in shared
-* shared/external queue operations are more expensive than
-* internal, and because, at steady state, external submitters
-* will compete for CPU with workers, ForkJoinTask.join and
-* related methods disable them from repeatedly helping to process
-* tasks if all workers are active.  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 bits in
+* resizing) but we use only a simple spinlock (using field
-* field qlock), because submitters encountering a busy queue move
+* qlock), because submitters encountering a busy queue move on to
-* on to try or create other queues -- they block only when
+* try or create other queues -- they block only when creating and
-* creating and registering new queues.
+* 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. We cannot negate this in the
+* themselves or each other, at rates that can exceed a billion
-* implementation of other management responsibilities. The main
+* per second.  The pool itself creates, activates (enables
-* tactic for avoiding bottlenecks is packing nearly all
+* scanning for and running tasks), deactivates, blocks, and
-* essentially atomic control state into two volatile variables
+* terminates threads, all with minimal central information.
-* that are by far most often read (not written) as status and
+* There are only a few properties that we can globally track or
-* consistency checks.
+* maintain, so we pack them into a small number of variables,
-*
+* often maintaining atomicity without blocking or locking.
-* Field "ctl" contains 64 bits holding all the information needed
+* Nearly all essentially atomic control state is held in two
-* to atomically decide to add, inactivate, enqueue (on an event
+* 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
-* fields.
+* subfields.
 *
-* Field "plock" is a form of sequence lock with a saturating
+* Field "runState" holds lockable state bits (STARTED, STOP, etc)
-* shutdown bit (similarly for per-queue "qlocks"), mainly
+* also protecting updates to the workQueues array.  When used as
-* protecting updates to the workQueues array, as well as to
+* a lock, it is normally held only for a few instructions (the
-* enable shutdown.  When used as a lock, it is normally only very
+* only exceptions are one-time array initialization and uncommon
-* briefly held, so is nearly always available after at most a
+* resizing), so is nearly always available after at most a brief
-* brief spin, but we use a monitor-based backup strategy to
+* spin. But to be extra-cautious, after spinning, method
-* block when needed.
+* 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 that is created upon first use and expanded
+* "workQueues" array. The array is created upon first use (see
-* if necessary.  Updates to the array while recording new workers
+* externalSubmit) and expanded if necessary.  Updates to the
-* and unrecording terminated ones are protected from each other
+* array while recording new workers and unrecording terminated
-* by a lock but the array is otherwise concurrently readable, and
+* ones are protected from each other by the runState lock, but
-* accessed directly.  To simplify index-based operations, the
+* the array is otherwise concurrently readable, and accessed
-* array size is always a power of two, and all readers must
+* directly. We also ensure that reads of the array reference
-* tolerate null slots. Worker queues are at odd indices. Shared
+* itself never become too stale. To simplify index-based
-* (submission) queues are at even indices, up to a maximum of 64
+* operations, the array size is always a power of two, and all
-* slots, to limit growth even if array needs to expand to add
+* readers must tolerate null slots. Worker queues are at odd
-* more workers. Grouping them together in this way simplifies and
+* indices. Shared (submission) queues are at even indices, up to
-* speeds up task scanning.
+* 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
+* 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 wait queue
+* a weak reference mechanism. Thus for example the stack top
-* field of ctl stores indices, not references.  Access to the
+* subfield of ctl stores indices, not references.
-* workQueues in associated methods (for example signalWork) must
+*
-* both index-check and null-check the IDs. All such accesses
+* Queuing Idle Workers. Unlike HPC work-stealing frameworks, we
-* ignore bad IDs by returning out early from what they are doing,
+* cannot let workers spin indefinitely scanning for tasks when
-* since this can only be associated with termination, in which
+* none can be found immediately, and we cannot start/resume
-* case it is OK to give up.  All uses of the workQueues array
+* workers unless there appear to be tasks available.  On the
-* also check that it is non-null (even if previously
+* other hand, we must quickly prod them into action when new
-* non-null). This allows nulling during termination, which is
+* tasks are submitted or generated. In many usages, ramp-up time
-* currently not necessary, but remains an option for
+* to activate workers is the main limiting factor in overall
-* resource-revocation-based shutdown schemes. It also helps
+* performance, which is compounded at program start-up by JIT
-* reduce JIT issuance of uncommon-trap code, which tends to
+* compilation and allocation. So we streamline this as much as
-* unnecessarily complicate control flow in some methods.
+* possible.
 *
-* Event Queuing. Unlike HPC work-stealing frameworks, we cannot
+* The "ctl" field atomically maintains active and total worker
-* let workers spin indefinitely scanning for tasks when none can
+* counts as well as a queue to place waiting threads so they can
-* be found immediately, and we cannot start/resume workers unless
+* be located for signalling. Active counts also play the role of
-* there appear to be tasks available.  On the other hand, we must
+* quiescence indicators, so are decremented when workers believe
-* quickly prod them into action when new tasks are submitted or
+* that there are no more tasks to execute. The "queue" is
-* generated. In many usages, ramp-up time to activate workers is
+* actually a form of Treiber stack.  A stack is ideal for
-* the main limiting factor in overall performance (this is
+* activating threads in most-recently used order. This improves
-* compounded at program start-up by JIT compilation and
+* performance and locality, outweighing the disadvantages of
-* allocation). So we try to streamline this as much as possible.
+* being prone to contention and inability to release a worker
-* We park/unpark workers after placing in an event wait queue
+* unless it is topmost on stack.  We park/unpark workers after
-* when they cannot find work. This "queue" is actually a simple
+* pushing on the idle worker stack (represented by the lower
-* Treiber stack, headed by the "id" field of ctl, plus a 15bit
+* 32bit subfield of ctl) when they cannot find work.  The top
-* counter value (that reflects the number of times a worker has
+* stack state holds the value of the "scanState" field of the
-* been inactivated) to avoid ABA effects (we need only as many
+* worker: its index and status, plus a version counter that, in
-* version numbers as worker threads). Successors are held in
+* addition to the count subfields (also serving as version
-* field WorkQueue.nextWait.  Queuing deals with several intrinsic
+* stamps) provide protection against Treiber stack ABA effects.
-* races, mainly that a task-producing thread can miss seeing (and
+*
-* signalling) another thread that gave up looking for work but
+* Field scanState is used by both workers and the pool to manage
-* has not yet entered the wait queue. We solve this by requiring
+* and track whether a worker is INACTIVE (possibly blocked
-* a full sweep of all workers (via repeated calls to method
+* waiting for a signal), or SCANNING for tasks (when neither hold
-* scan()) both before and after a newly waiting worker is added
+* it is busy running tasks).  When a worker is inactivated, its
-* to the wait queue.  Because enqueued workers may actually be
+* scanState field is set, and is prevented from executing tasks,
-* rescanning rather than waiting, we set and clear the "parker"
+* 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.)
-* 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.  We create or wake up workers only when there
-* appears to be at least one task they might be able to find and
-* execute.  When a submission is added or another worker adds a
-* task to a queue that has fewer than two tasks, they signal
-* waiting workers (or trigger creation of new ones if fewer than
-* the given parallelism level -- signalWork).  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.  So in general, pools will be over-signalled. 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. Additionally, workers spin-down gradually, by staying
-* alive so long as they see the ctl state changing.  Similar
-* stability-sensing techniques are also used before blocking in
-* awaitJoin and helpComplete.
 *
 * 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 if the pool has remained quiescent for a
+* time out and terminate (see awaitWork) if the pool has remained
-* given period -- a short period if there are more threads than
+* quiescent for period IDLE_TIMEOUT, increasing the period as the
-* parallelism, longer as the number of threads decreases. This
+* number of threads decreases, eventually removing all workers.
-* will slowly propagate, eventually terminating all workers after
+* Also, when more than two spare threads exist, excess threads
-* periods of non-use.
+* are immediately terminated at the next quiescent point.
-*
+* (Padding by two avoids hysteresis.)
-* Shutdown and Termination. A call to shutdownNow atomically sets
+*
-* a plock bit and then (non-atomically) sets each worker's
+* Shutdown and Termination. A call to shutdownNow invokes
-* qlock status, cancels all unprocessed tasks, and wakes up
+* tryTerminate to atomically set a runState bit. The calling
-* all waiting workers.  Detecting whether termination should
+* thread, as well as every other worker thereafter terminating,
-* commence after a non-abrupt shutdown() call requires more work
+* helps terminate others by setting their (qlock) status,
-* and bookkeeping. We need consensus about quiescence (i.e., that
+* cancelling their unprocessed tasks, and waking them up, doing
-* there is no more work). The active count provides a primary
+* so repeatedly until stable (but with a loop bounded by the
-* indication but non-abrupt shutdown still requires a rechecking
+* number of workers).  Calls to non-abrupt shutdown() preface
-* scan for any workers that are inactive but not queued.
+* 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 sometimes need
+* possible is not necessarily a good idea since we may need both
-* both an unblocked task and its continuation to progress.
+* an unblocked task and its continuation to progress.  Instead we
-* Instead we combine two tactics:
+* 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,
 * typically worthwhile).
 *
 * The ManagedBlocker extension API can't use helping so relies
 * only on compensation in method awaitBlocker.
 *
-* The algorithm in tryHelpStealer entails a form of "linear"
+* The algorithm in helpStealer entails a form of "linear
-* helping: Each worker records (in field currentSteal) the most
+* helping".  Each worker records (in field currentSteal) the most
-* recent task it stole from some other worker. Plus, it records
+* recent task it stole from some other worker (or a submission).
-* (in field currentJoin) the task it is currently actively
+* It also records (in field currentJoin) the task it is currently
-* joining. Method tryHelpStealer uses these markers to try to
+* actively joining. Method helpStealer uses these markers to try
-* find a worker to help (i.e., steal back a task from and execute
+* to find a worker to help (i.e., steal back a task from and
-* it) that could hasten completion of the actively joined task.
+* execute it) that could hasten completion of the actively joined
-* In essence, the joiner executes a task that would be on its own
+* task.  Thus, the joiner executes a task that would be on its
-* local deque had the to-be-joined task not been stolen. This may
+* own local deque had the to-be-joined task not been stolen. This
-* be seen as a conservative variant of the approach in Wagner &
+* 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
 * 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 (see MAX_HELP) and fall back to suspending the
+* to find work using checksums and fall back to suspending the
 * worker and if necessary replacing it with another.
 *
-* Helping actions for CountedCompleters are much simpler: Method
+* Helping actions for CountedCompleters do not require tracking
-* helpComplete can take and execute any task with the same root
+* currentJoins: Method helpComplete takes and executes any task
-* as the task being waited on. However, this still entails some
+* with the same root as the task being waited on (preferring
-* traversal of completer chains, so is less efficient than using
+* local pops to non-local polls). However, this still entails
-* CountedCompleters without explicit joins.
+* some traversal of completer chains, so is less efficient than
-*
+* using CountedCompleters without explicit joins.
-* It is impossible to keep exactly the target parallelism number
+*
-* of threads running at any given time.  Determining the
+* Compensation does not aim to keep exactly the target
-* existence of conservatively safe helping targets, the
+* parallelism number of unblocked threads running at any given
-* availability of already-created spares, and the apparent need
+* time. Some previous versions of this class employed immediate
-* to create new spares are all racy, so we rely on multiple
+* compensations for any blocked join. However, in practice, the
-* retries of each.  Compensation in the apparent absence of
+* vast majority of blockages are transient byproducts of GC and
-* helping opportunities is challenging to control on JVMs, where
+* other JVM or OS activities that are made worse by replacement.
-* GC and other activities can stall progress of tasks that in
+* Currently, compensation is attempted only after validating that
-* turn stall out many other dependent tasks, without us being
+* all purportedly active threads are processing tasks by checking
-* able to determine whether they will ever require compensation.
+* field WorkQueue.scanState, which eliminates most false
-* Even though work-stealing otherwise encounters little
+* positives.  Also, compensation is bypassed (tolerating fewer
-* degradation in the presence of more threads than cores,
+* threads) in the most common case in which it is rarely
-* aggressively adding new threads in such cases entails risk of
+* beneficial: when a worker with an empty queue (thus no
-* unwanted positive feedback control loops in which more threads
+* continuation tasks) blocks on a join and there still remain
-* cause more dependent stalls (as well as delayed progress of
+* enough threads to ensure liveness.
-* unblocked threads to the point that we know they are available)
+*
-* leading to more situations requiring more threads, and so
+* The compensation mechanism may be bounded.  Bounds for the
-* on. This aspect of control can be seen as an (analytically
+* commonPool (see commonMaxSpares) better enable JVMs to cope
-* intractable) game with an opponent that may choose the worst
+* with programming errors and abuse before running out of
-* (for us) active thread to stall at any time.  We take several
+* resources to do so. In other cases, users may supply factories
-* precautions to bound losses (and thus bound gains), mainly in
+* that limit thread construction. The effects of bounding in this
-* methods tryCompensate and awaitJoin.
+* 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
-* fullExternalPush during the first submission to the pool.
+* externalSubmit during the first submission to the pool.
 *
 * When external threads submit to the common pool, they can
-* perform subtask processing (see externalHelpJoin and related
+* perform subtask processing (see externalHelpComplete and
-* methods).  This caller-helps policy makes it sensible to set
+* related methods) upon joins.  This caller-helps policy makes it
-* common pool parallelism level to one (or more) less than the
+* sensible to set common pool parallelism level to one (or more)
-* total number of available cores, or even zero for pure
+* less than the total number of available cores, or even zero for
-* caller-runs.  We do not need to record whether external
+* pure caller-runs.  We do not need to record whether external
-* submissions are to the common pool -- if not, externalHelpJoin
+* submissions are to the common pool -- if not, external help
-* returns quickly (at the most helping to signal some common pool
+* methods return quickly. These submitters would otherwise be
-* workers). These submitters would otherwise be blocked waiting
+* blocked waiting for completion, so the extra effort (with
-* for completion, so the extra effort (with liberally sprinkled
+* liberally sprinkled task status checks) in inapplicable cases
-* task status checks) in inapplicable cases amounts to an odd
+* amounts to an odd form of limited spin-wait before blocking in
-* form of limited spin-wait before blocking in ForkJoinTask.join.
+* 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
+* after executing any top-level task (see WorkQueue.runTask).
-* associated mechanics (mainly in ForkJoinWorkerThread) may be
+* The associated mechanics (mainly in ForkJoinWorkerThread) may
-* JVM-dependent and must access particular Thread class fields to
+* be JVM-dependent and must access particular Thread class fields
-* achieve this effect.
+* 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 volatiles held
+* they must accumulate sets of consistent reads of fields held in
-* in local variables.  Methods signalWork() and scan() are the
+* local variables.  There are also other coding oddities
-* main bottlenecks, so are especially heavily
+* (including several unnecessary-looking hoisted null checks)
-* micro-optimized/mangled.  There are lots of inline assignments
+* that help some methods perform reasonably even when interpreted
-* (of form "while ((local = field) != 0)") which are usually the
+* (not compiled).
-* simplest way to ensure the required read orderings (which are
+*
-* sometimes critical). This leads to a "C"-like style of listing
+* The order of declarations in this file is (with a few exceptions):
-* declarations of these locals at the heads of methods or blocks.
-* There are several occurrences of the unusual "do {} while
-* (!cas...)"  which is the simplest way to force an update of a
-* CAS'ed variable. 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:
 * (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
 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 main rationale and algorithms.
+* submission. See above for descriptions and algorithms.
-* Implementation relies heavily on "Unsafe" intrinsics
-* and selective use of "volatile":
-*
-* Field "base" is the index (mod array.length) of the least valid
-* queue slot, which is always the next position to steal (poll)
-* from if nonempty. Reads and writes require volatile orderings
-* but not CAS, because updates are only performed after slot
-* CASes.
-*
-* Field "top" is the index (mod array.length) of the next queue
-* slot to push to or pop from. It is written only by owner thread
-* for push, or under lock for external/shared push, and accessed
-* by other threads only after reading (volatile) base.  Both top
-* and base are allowed to wrap around on overflow, but (top -
-* base) (or more commonly -(base - top) to force volatile read of
-* base before top) still estimates size. The lock ("qlock") is
-* forced to -1 on termination, causing all further lock attempts
-* to fail. (Note: we don't need CAS for termination state because
-* upon pool shutdown, all shared-queues will stop being used
-* anyway.)  Nearly all lock bodies are set up so that exceptions
-* within lock bodies are "impossible" (modulo JVM errors that
-* would cause failure anyway.)
-*
-* The array slots are read and written using the emulation of
-* volatiles/atomics provided by Unsafe. Insertions must in
-* general use putOrderedObject as a form of releasing store to
-* ensure that all writes to the task object are ordered before
-* its publication in the queue.  All removals entail a CAS to
-* null.  The array is always a power of two. To ensure safety of
-* Unsafe array operations, all accesses perform explicit null
-* checks and implicit bounds checks via power-of-two masking.
-*
-* In addition to basic queuing support, this class contains
-* fields described elsewhere to control execution. It turns out
-* to work better memory-layout-wise to include them in this class
-* rather than a separate class.
-*
 * 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. (It would be best for queue objects
+* arrays sharing cache lines. The @Contended annotation alerts
-* and their arrays to share, but there is nothing available to
+* JVMs to try to keep instances apart.
-* help arrange that). 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
 * value a bit less than this to help users trap runaway
 * programs before saturating systems.
 */
 static final int MAXIMUM_QUEUE_CAPACITY = 1 << 26; // 64M
-volatile int eventCount;   // encoded inactivation count; < 0 if inactive
+// Instance fields
-int nextWait;              // encoded record of next event waiter
+volatile int scanState;    // versioned, <0: inactive; odd:scanning
+int stackPred;             // pool stack (ctl) predecessor
 int nsteals;               // number of steals
-int hint;                  // steal index hint
+int hint;                  // randomization and stealer index hint
-short poolIndex;           // index of this queue in pool
+int config;                // pool index and mode
-final short mode;          // 0: lifo, > 0: fifo, < 0: shared
+volatile int qlock;        // 1: locked, < 0: terminate; else 0
-volatile int qlock;        // 1: locked, -1: 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
-ForkJoinTask<?> currentSteal; // current non-local task being executed
+volatile ForkJoinTask<?> currentSteal; // mainly used by helpStealer
-WorkQueue(ForkJoinPool pool, ForkJoinWorkerThread owner, int mode,
+WorkQueue(ForkJoinPool pool, ForkJoinWorkerThread owner) {
-int seed) {
 this.pool = pool;
 this.owner = owner;
-this.mode = (short)mode;
-this.hint = seed; // store initial seed for runWorker
 // 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.
 */
 * 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 m, s;
+ForkJoinTask<?>[] a; int n, m, s;
-int n = base - (s = top);
+return ((n = base - (s = top)) >= 0 ||
-return (n >= 0 ||
+(n == -1 &&           // possibly one task
-(n == -1 &&
+((a = array) == null || (m = a.length - 1) < 0 ||
-((a = array) == null ||
-(m = a.length - 1) < 0 ||
 U.getObject
 (a, (long)((m & (s - 1)) << ASHIFT) + ABASE) == null)));
 }
 /**
 * @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 s = top, n;
+int b = base, s = top, n;
 if ((a = array) != null) {    // ignore if queue removed
-int m = a.length - 1;
+int m = a.length - 1;     // fenced write for task visibility
 U.putOrderedObject(a, ((m & s) << ASHIFT) + ABASE, task);
-if ((n = (top = s + 1) - base) <= 2)
+U.putOrderedInt(this, QTOP, s + 1);
-(p = pool).signalWork(p.workQueues, this);
+if ((n = s - b) <= 1) {
+if ((p = pool) != null)
+p.signalWork(p.workQueues, this);
+}
 else if (n >= m)
 growArray();
 }
 }
 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 {
+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 &&
 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)) {
-top = s;
+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 tryHelpStealer.
+* 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)) {
-U.putOrderedInt(this, QBASE, b + 1);
+base = b + 1;
 return t;
 }
 }
 return null;
 }
 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 (t != null) {
+if (base == b) {
-if (U.compareAndSwapObject(a, j, t, null)) {
+if (t != null) {
-U.putOrderedInt(this, QBASE, b + 1);
+if (U.compareAndSwapObject(a, j, t, null)) {
-return t;
+base = b + 1;
+return t;
+}
 }
-}
+else if (b + 1 == top) // now empty
-else if (base == b) {
-if (b + 1 == top)
 break;
-Thread.yield(); // wait for lagging update (very rare)
 }
 }
 return null;
 }
 /**
 * Takes next task, if one exists, in order specified by mode.
 */
 final ForkJoinTask<?> nextLocalTask() {
-return mode == 0 ? pop() : poll();
+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 = mode == 0 ? top - 1 : base;
+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)) {
-top = s;
+U.putOrderedInt(this, QTOP, s);
 return true;
 }
 return false;
 }
 /**
 * Removes and cancels all known tasks, ignoring any exceptions.
 */
 final void cancelAll() {
-ForkJoinTask.cancelIgnoringExceptions(currentJoin);
+ForkJoinTask<?> t;
-ForkJoinTask.cancelIgnoringExceptions(currentSteal);
+if ((t = currentJoin) != null) {
-for (ForkJoinTask<?> t; (t = poll()) != 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
 for (ForkJoinTask<?> t; (t = poll()) != null;)
 t.doExec();
 }
 /**
-* Executes a top-level task and any local tasks remaining
+* Removes and executes all local tasks. If LIFO, invokes
-* after execution.
+* pollAndExecAll. Otherwise implements a specialized pop loop
+* to exec until empty.
 */
-final void runTask(ForkJoinTask<?> task) {
+final void execLocalTasks() {
-if ((currentSteal = task) != null) {
+int b = base, m, s;
-ForkJoinWorkerThread thread;
+ForkJoinTask<?>[] a = array;
-task.doExec();
+if (b - (s = top - 1) <= 0 && a != null &&
-ForkJoinTask<?>[] a = array;
+(m = a.length - 1) >= 0) {
-int md = mode;
+if ((config & FIFO_QUEUE) == 0) {
-++nsteals;
+for (ForkJoinTask<?> t;;) {
-currentSteal = null;
+if ((t = (ForkJoinTask<?>)U.getAndSetObject
-if (md != 0)
+(a, ((m & s) << ASHIFT) + ABASE, null)) == null)
-pollAndExecAll();
+break;
-else if (a != null) {
+U.putOrderedInt(this, QTOP, s);
-int s, m = a.length - 1;
-ForkJoinTask<?> t;
-while ((s = top - 1) - base >= 0 &&
-(t = (ForkJoinTask<?>)U.getAndSetObject
-(a, ((m & s) << ASHIFT) + ABASE, null)) != null) {
-top = s;
 t.doExec();
-}
+if (base - (s = top - 1) > 0)
-}
-if ((thread = owner) != null) // no need to do in finally clause
-thread.afterTopLevelExec();
-}
-}
-/**
-* If present, removes from queue and executes the given task,
-* or any other cancelled task. Returns (true) on any CAS
-* or consistency check failure so caller can retry.
-*
-* @return false if no progress can be made, else true
-*/
-final boolean tryRemoveAndExec(ForkJoinTask<?> task) {
-boolean stat;
-ForkJoinTask<?>[] a; int m, s, b, n;
-if (task != null && (a = array) != null && (m = a.length - 1) >= 0 &&
-(n = (s = top) - (b = base)) > 0) {
-boolean removed = false, empty = true;
-stat = true;
-for (ForkJoinTask<?> t;;) {           // traverse from s to b
-long j = ((--s & m) << ASHIFT) + ABASE;
-t = (ForkJoinTask<?>)U.getObject(a, j);
-if (t == null)                    // inconsistent length
-break;
-else if (t == task) {
-if (s + 1 == top) {           // pop
-if (!U.compareAndSwapObject(a, j, task, null))
-break;
-top = s;
-removed = true;
-}
-else if (base == b)           // replace with proxy
-removed = U.compareAndSwapObject(a, j, task,
-new EmptyTask());
-break;
-}
-else if (t.status >= 0)
-empty = false;
-else if (s + 1 == top) {          // pop and throw away
-if (U.compareAndSwapObject(a, j, t, null))
-top = s;
-break;
-}
-if (--n == 0) {
-if (!empty && base == b)
-stat = false;
-break;
-}
-}
-if (removed)
-task.doExec();
-}
-else
-stat = false;
-return stat;
-}
-/**
-* Tries to poll for and execute the given task or any other
-* task in its CountedCompleter computation.
-*/
-final boolean pollAndExecCC(CountedCompleter<?> root) {
-ForkJoinTask<?>[] a; int b; Object o; CountedCompleter<?> t, r;
-if ((b = base) - top < 0 && (a = array) != null) {
-long j = (((a.length - 1) & b) << ASHIFT) + ABASE;
-if ((o = U.getObjectVolatile(a, j)) == null)
-return true; // retry
-if (o instanceof CountedCompleter) {
-for (t = (CountedCompleter<?>)o, r = t;;) {
-if (r == root) {
-if (base == b &&
-U.compareAndSwapObject(a, j, t, null)) {
-U.putOrderedInt(this, QBASE, b + 1);
-t.doExec();
-}
-return true;
-}
-else if ((r = r.completer) == null)
-break; // not part of root computation
-}
-}
-}
-return false;
-}
-/**
-* Tries to pop and execute the given task or any other task
-* in its CountedCompleter computation.
-*/
-final boolean externalPopAndExecCC(CountedCompleter<?> root) {
-ForkJoinTask<?>[] a; int s; Object o; CountedCompleter<?> t, r;
-if (base - (s = top) < 0 && (a = array) != null) {
-long j = (((a.length - 1) & (s - 1)) << ASHIFT) + ABASE;
-if ((o = U.getObject(a, j)) instanceof CountedCompleter) {
-for (t = (CountedCompleter<?>)o, r = t;;) {
-if (r == root) {
-if (U.compareAndSwapInt(this, QLOCK, 0, 1)) {
-if (top == s && array == a &&
-U.compareAndSwapObject(a, j, t, null)) {
-top = s - 1;
-qlock = 0;
-t.doExec();
-}
-else
-qlock = 0;
-}
-return true;
-}
-else if ((r = r.completer) == null)
 break;
 }
 }
-}
+else
-return false;
+pollAndExecAll();
+}
 }
 /**
-* Internal version
+* Executes the given task and any remaining local tasks.
 */
-final boolean internalPopAndExecCC(CountedCompleter<?> root) {
+final void runTask(ForkJoinTask<?> task) {
-ForkJoinTask<?>[] a; int s; Object o; CountedCompleter<?> t, r;
+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.getObject(a, j)) instanceof CountedCompleter) {
+if ((o = U.getObjectVolatile(a, j)) != null &&
-for (t = (CountedCompleter<?>)o, r = t;;) {
+(o instanceof CountedCompleter)) {
-if (r == root) {
+CountedCompleter<?> t = (CountedCompleter<?>)o;
-if (U.compareAndSwapObject(a, j, t, null)) {
+for (CountedCompleter<?> r = t;;) {
-top = s - 1;
+if (r == task) {
-t.doExec();
+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);
+}
 }
-return true;
+else if (U.compareAndSwapObject(a, j, t, null)) {
+U.putOrderedInt(this, QTOP, s - 1);
+return t;
+}
+break;
 }
-else if ((r = r.completer) == null)
+else if ((r = r.completer) == null) // try parent
 break;
 }
 }
 }
-return false;
+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 (eventCount >= 0 &&
+return (scanState >= 0 &&
 (wt = owner) != null &&
 (s = wt.getState()) != Thread.State.BLOCKED &&
 s != Thread.State.WAITING &&
 s != Thread.State.TIMED_WAITING);
 }
-// Unsafe mechanics
+// Unsafe mechanics. Note that some are (and must be) the same as in FJP
 private static final sun.misc.Unsafe U;
-private static final long QBASE;
+private static final int  ABASE;
+private static final int  ASHIFT;
+private static final long QTOP;
 private static final long QLOCK;
-private static final int ABASE;
+private static final long QCURRENTSTEAL;
-private static final int ASHIFT;
 static {
 try {
 U = sun.misc.Unsafe.getUnsafe();
-Class<?> k = WorkQueue.class;
+Class<?> wk = WorkQueue.class;
 Class<?> ak = ForkJoinTask[].class;
-QBASE = U.objectFieldOffset
+QTOP = U.objectFieldOffset
-(k.getDeclaredField("base"));
+(wk.getDeclaredField("top"));
 QLOCK = U.objectFieldOffset
-(k.getDeclaredField("qlock"));
+(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);
 * 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;
 /**
 */
 private static final synchronized int nextPoolId() {
 return ++poolNumberSequence;
 }
-// static constants
+// 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
+private static final long IDLE_TIMEOUT = 2000L * 1000L * 1000L; // 2sec
-/**
-* Timeout value when there are more threads than parallelism level
-*/
-private static final long FAST_IDLE_TIMEOUT =  200L * 1000L * 1000L;
 /**
 * Tolerance for idle timeouts, to cope with timer undershoots
 */
-private static final long TIMEOUT_SLOP = 2000000L;
+private static final long TIMEOUT_SLOP = 20L * 1000L * 1000L;  // 20ms
 /**
-* The maximum stolen->joining link depth allowed in method
+* The initial value for commonMaxSpares during static
-* tryHelpStealer.  Must be a power of two.  Depths for legitimate
+* initialization unless overridden using System property
-* chains are unbounded, but we use a fixed constant to avoid
+* "java.util.concurrent.ForkJoinPool.common.maximumSpares".  The
-* (otherwise unchecked) cycles and to bound staleness of
+* default value is far in excess of normal requirements, but also
-* traversal parameters at the expense of sometimes blocking when
+* far short of MAX_CAP and typical OS thread limits, so allows
-* we could be helping.
+* JVMs to catch misuse/abuse before running out of resources
-*/
+* needed to do so.
-private static final int MAX_HELP = 64;
+*/
+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. If/when MWAIT-like intrinsics becomes available, they
+* may allow quieter spinning. The value of SPINS must be a power
+* of two, at least 4. The current value causes spinning for a
+* small fraction of typical context-switch times, well worthwhile
+* given the typical likelihoods that blocking is not necessary.
+*/
+private static final int SPINS  = 1 << 11;
 /**
 * Increment for seed generators. See class ThreadLocal for
 * explanation.
 */
 private static final int SEED_INCREMENT = 0x9e3779b9;
 /*
-* Bits and masks for control variables
+* Bits and masks for field ctl, packed with 4 16 bit subfields:
-*
+* AC: Number of active running workers minus target parallelism
-* Field ctl is a long packed with:
+* TC: Number of total workers minus target parallelism
-* AC: Number of active running workers minus target parallelism (16 bits)
+* SS: version count and status of top waiting thread
-* TC: Number of total workers minus target parallelism (16 bits)
+* ID: poolIndex of top of Treiber stack of waiters
-* ST: true if pool is terminating (1 bit)
+*
-* EC: the wait count of top waiting thread (15 bits)
+* When convenient, we can extract the lower 32 stack top bits
-* ID: poolIndex of top of Treiber stack of waiters (16 bits)
+* (including version bits) as sp=(int)ctl.  The offsets of counts
-*
+* by the target parallelism and the positionings of fields makes
-* When convenient, we can extract the upper 32 bits of counts and
+* it possible to perform the most common checks via sign tests of
-* the lower 32 bits of queue state, u = (int)(ctl >>> 32) and e =
+* fields: When ac is negative, there are not enough active
-* (int)ctl.  The ec field is never accessed alone, but always
+* workers, when tc is negative, there are not enough total
-* together with id and st. The offsets of counts by the target
+* workers.  When sp is non-zero, there are waiting workers.  To
-* parallelism and the positionings of fields makes it possible to
+* deal with possibly negative fields, we use casts in and out of
-* perform the most common checks via sign tests of fields: When
+* "short" and/or signed shifts to maintain signedness.
-* ac is negative, there are not enough active workers, when tc is
+*
-* negative, there are not enough total workers, and when e is
+* Because it occupies uppermost bits, we can add one active count
-* negative, the pool is terminating.  To deal with these possibly
+* using getAndAddLong of AC_UNIT, rather than CAS, when returning
-* negative fields, we use casts in and out of "short" and/or
+* from a blocked join.  Other updates entail multiple subfields
-* signed shifts to maintain signedness.
+* and masking, requiring CAS.
-*
+*/
-* When a thread is queued (inactivated), its eventCount field is
-* set negative, which is the only way to tell if a worker is
+// Lower and upper word masks
-* prevented from executing tasks, even though it must continue to
+private static final long SP_MASK    = 0xffffffffL;
-* scan for them to avoid queuing races. Note however that
+private static final long UC_MASK    = ~SP_MASK;
-* eventCount updates lag releases so usage requires care.
-*
+// Active counts
-* Field plock is an int packed with:
-* SHUTDOWN: true if shutdown is enabled (1 bit)
-* SEQ:  a sequence lock, with PL_LOCK bit set if locked (30 bits)
-* SIGNAL: set when threads may be waiting on the lock (1 bit)
-*
-* The sequence number enables simple consistency checks:
-* Staleness of read-only operations on the workQueues array can
-* be checked by comparing plock before vs after the reads.
-*/
-// bit positions/shifts for fields
 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 int  ST_SHIFT   = 31;
+private static final long TC_UNIT    = 0x0001L << TC_SHIFT;
-private static final int  EC_SHIFT   = 16;
+private static final long TC_MASK    = 0xffffL << TC_SHIFT;
+private static final long ADD_WORKER = 0x0001L << (TC_SHIFT + 15); // sign
-// bounds
-private static final int  SMASK      = 0xffff;  // short bits
+// runState bits: SHUTDOWN must be negative, others arbitrary powers of two
-private static final int  MAX_CAP    = 0x7fff;  // max #workers - 1
+private static final int  RSLOCK     = 1;
-private static final int  EVENMASK   = 0xfffe;  // even short bits
+private static final int  RSIGNAL    = 1 << 1;
-private static final int  SQMASK     = 0x007e;  // max 64 (even) slots
+private static final int  STARTED    = 1 << 2;
-private static final int  SHORT_SIGN = 1 << 15;
+private static final int  STOP       = 1 << 29;
-private static final int  INT_SIGN   = 1 << 31;
+private static final int  TERMINATED = 1 << 30;
+private static final int  SHUTDOWN   = 1 << 31;
-// masks
-private static final long STOP_BIT   = 0x0001L << ST_SHIFT;
-private static final long AC_MASK    = ((long)SMASK) << AC_SHIFT;
-private static final long TC_MASK    = ((long)SMASK) << TC_SHIFT;
-// units for incrementing and decrementing
-private static final long TC_UNIT    = 1L << TC_SHIFT;
-private static final long AC_UNIT    = 1L << AC_SHIFT;
-// masks and units for dealing with u = (int)(ctl >>> 32)
-private static final int  UAC_SHIFT  = AC_SHIFT - 32;
-private static final int  UTC_SHIFT  = TC_SHIFT - 32;
-private static final int  UAC_MASK   = SMASK << UAC_SHIFT;
-private static final int  UTC_MASK   = SMASK << UTC_SHIFT;
-private static final int  UAC_UNIT   = 1 << UAC_SHIFT;
-private static final int  UTC_UNIT   = 1 << UTC_SHIFT;
-// masks and units for dealing with e = (int)ctl
-private static final int E_MASK      = 0x7fffffff; // no STOP_BIT
-private static final int E_SEQ       = 1 << EC_SHIFT;
-// plock bits
-private static final int SHUTDOWN    = 1 << 31;
-private static final int PL_LOCK     = 2;
-private static final int PL_SIGNAL   = 1;
-private static final int PL_SPINS    = 1 << 8;
-// access mode for WorkQueue
-static final int LIFO_QUEUE          =  0;
-static final int FIFO_QUEUE          =  1;
-static final int SHARED_QUEUE        = -1;
 // Instance fields
-volatile long stealCount;                  // collects worker counts
+volatile long ctl;                   // main pool control
-volatile long ctl;                         // main pool control
+volatile int runState;               // lockable status
-volatile int plock;                        // shutdown status and seqLock
+final int config;                    // parallelism, mode
-volatile int indexSeed;                    // worker/submitter index seed
+int indexSeed;                       // to generate worker index
-final short parallelism;                   // parallelism level
+volatile WorkQueue[] workQueues;     // main registry
-final short mode;                          // LIFO/FIFO
-WorkQueue[] workQueues;                    // main registry
 final ForkJoinWorkerThreadFactory factory;
-final UncaughtExceptionHandler ueh;        // per-worker UEH
+final UncaughtExceptionHandler ueh;  // per-worker UEH
-final String workerNamePrefix;             // to create worker name string
+final String workerNamePrefix;       // to create worker name string
+volatile AtomicLong stealCounter;    // also used as sync monitor
-/**
-* Acquires the plock lock to protect worker array and related
+/**
-* updates. This method is called only if an initial CAS on plock
+* Acquires the runState lock; returns current (locked) runState.
-* fails. This acts as a spinlock for normal cases, but falls back
+*/
-* to builtin monitor to block when (rarely) needed. This would be
+private int lockRunState() {
-* a terrible idea for a highly contended lock, but works fine as
+int rs;
-* a more conservative alternative to a pure spinlock.
+return ((((rs = runState) & RSLOCK) != 0 ||
-*/
+!U.compareAndSwapInt(this, RUNSTATE, rs, rs |= RSLOCK)) ?
-private int acquirePlock() {
+awaitRunStateLock() : rs);
-int spins = PL_SPINS, ps, nps;
+}
-for (;;) {
-if (((ps = plock) & PL_LOCK) == 0 &&
+/**
-U.compareAndSwapInt(this, PLOCK, ps, nps = ps + PL_LOCK))
+* Spins and/or blocks until runstate lock is available.  See
-return nps;
+* above for explanation.
-else if (spins >= 0) {
+*/
-if (ThreadLocalRandom.nextSecondarySeed() >= 0)
+private int awaitRunStateLock() {
+Object lock;
+boolean wasInterrupted = false;
+for (int spins = SPINS, r = 0, rs, ns;;) {
+if (((rs = runState) & RSLOCK) == 0) {
+if (U.compareAndSwapInt(this, RUNSTATE, rs, ns = rs | RSLOCK)) {
+if (wasInterrupted) {
+try {
+Thread.currentThread().interrupt();
+} catch (SecurityException ignore) {
+}
+}
+return ns;
+}
+}
+else if (r == 0)
+r = ThreadLocalRandom.nextSecondarySeed();
+else if (spins > 0) {
+r ^= r << 6; r ^= r >>> 21; r ^= r << 7; // xorshift
+if (r >= 0)
 --spins;
 }
-else if (U.compareAndSwapInt(this, PLOCK, ps, ps | PL_SIGNAL)) {
+else if ((rs & STARTED) == 0 || (lock = stealCounter) == null)
-synchronized (this) {
+Thread.yield();   // initialization race
-if ((plock & PL_SIGNAL) != 0) {
+else if (U.compareAndSwapInt(this, RUNSTATE, rs, rs | RSIGNAL)) {
+synchronized (lock) {
+if ((runState & RSIGNAL) != 0) {
 try {
-wait();
+lock.wait();
 } catch (InterruptedException ie) {
-try {
+if (!(Thread.currentThread() instanceof
-Thread.currentThread().interrupt();
+ForkJoinWorkerThread))
-} catch (SecurityException ignore) {
+wasInterrupted = true;
-}
 }
 }
 else
-notifyAll();
+lock.notifyAll();
 }
 }
 }
 }
 /**
-* Unlocks and signals any thread waiting for plock. Called only
+* Unlocks and sets runState to newRunState.
-* when CAS of seq value for unlock fails.
+*
-*/
+* @param oldRunState a value returned from lockRunState
-private void releasePlock(int ps) {
+* @param newRunState the next value (must have lock bit clear).
-plock = ps;
+*/
-synchronized (this) { notifyAll(); }
+private void unlockRunState(int oldRunState, int newRunState) {
-}
+if (!U.compareAndSwapInt(this, RUNSTATE, oldRunState, newRunState)) {
+Object lock = stealCounter;
-/**
+runState = newRunState;              // clears RSIGNAL bit
-* Tries to create and start one worker if fewer than target
+if (lock != null)
-* parallelism level exist. Adjusts counts etc on failure.
+synchronized (lock) { lock.notifyAll(); }
-*/
+}
-private void tryAddWorker() {
+}
-long c; int u, e;
-while ((u = (int)((c = ctl) >>> 32)) < 0 &&
+// Creating, registering and deregistering workers
-(u & SHORT_SIGN) != 0 && (e = (int)c) >= 0) {
-long nc = ((long)(((u + UTC_UNIT) & UTC_MASK) |
+/**
-((u + UAC_UNIT) & UAC_MASK)) << 32) | (long)e;
+* Tries to construct and start one worker. Assumes that total
-if (U.compareAndSwapLong(this, CTL, c, nc)) {
+* count has already been incremented as a reservation.  Invokes
-ForkJoinWorkerThreadFactory fac;
+* deregisterWorker on any failure.
-Throwable ex = null;
+*
-ForkJoinWorkerThread wt = null;
+* @return true if successful
-try {
+*/
-if ((fac = factory) != null &&
+private boolean createWorker() {
-(wt = fac.newThread(this)) != null) {
+ForkJoinWorkerThreadFactory fac = factory;
-wt.start();
+Throwable ex = null;
-break;
+ForkJoinWorkerThread wt = null;
-}
+try {
-} catch (Throwable rex) {
+if (fac != null && (wt = fac.newThread(this)) != null) {
-ex = rex;
+wt.start();
+return true;
+}
+} catch (Throwable rex) {
+ex = rex;
+}
+deregisterWorker(wt, ex);
+return false;
+}
+/**
+* Tries to add one worker, incrementing ctl counts before doing
+* so, relying on createWorker to back out on failure.
+*
+* @param c incoming ctl value, with total count negative and no
+* idle workers.  On CAS failure, c is refreshed and retried if
+* this holds (otherwise, a new worker is not needed).
+*/
+private void tryAddWorker(long c) {
+boolean add = false;
+do {
+long nc = ((AC_MASK & (c + AC_UNIT)) |
+(TC_MASK & (c + TC_UNIT)));
+if (ctl == c) {
+int rs, stop;                 // check if terminating
+if ((stop = (rs = lockRunState()) & STOP) == 0)
+add = U.compareAndSwapLong(this, CTL, c, nc);
+unlockRunState(rs, rs & ~RSLOCK);
+if (stop != 0)
+break;
+if (add) {
+createWorker();
+break;
 }
-deregisterWorker(wt, ex);
+}
-break;
+} while (((c = ctl) & ADD_WORKER) != 0L && (int)c == 0);
 }
-}
-}
+/**
+* Callback from ForkJoinWorkerThread constructor to establish and
-//  Registering and deregistering workers
+* record its WorkQueue.
-/**
-* Callback from ForkJoinWorkerThread to establish and record its
-* WorkQueue. To avoid scanning bias due to packing entries in
-* front of the workQueues array, we treat the array as a simple
-* power-of-two hash table using per-thread seed as hash,
-* expanding as needed.
 *
 * @param wt the worker thread
 * @return the worker's queue
 */
 final WorkQueue registerWorker(ForkJoinWorkerThread wt) {
-UncaughtExceptionHandler handler; WorkQueue[] ws; int s, ps;
+UncaughtExceptionHandler handler;
-wt.setDaemon(true);
+wt.setDaemon(true);                           // configure thread
 if ((handler = ueh) != null)
 wt.setUncaughtExceptionHandler(handler);
-do {} while (!U.compareAndSwapInt(this, INDEXSEED, s = indexSeed,
+WorkQueue w = new WorkQueue(this, wt);
-s += SEED_INCREMENT) ||
+int i = 0;                                    // assign a pool index
-s == 0); // skip 0
+int mode = config & MODE_MASK;
-WorkQueue w = new WorkQueue(this, wt, mode, s);
+int rs = lockRunState();
-if (((ps = plock) & PL_LOCK) != 0 ||
-!U.compareAndSwapInt(this, PLOCK, ps, ps += PL_LOCK))
-ps = acquirePlock();
-int nps = (ps & SHUTDOWN) | ((ps + PL_LOCK) & ~SHUTDOWN);
 try {
-if ((ws = workQueues) != null) {    // skip if shutting down
+WorkQueue[] ws; int n;                    // skip if no array
-int n = ws.length, m = n - 1;
+if ((ws = workQueues) != null && (n = ws.length) > 0) {
-int r = (s << 1) | 1;           // use odd-numbered indices
+int s = indexSeed += SEED_INCREMENT;  // unlikely to collide
-if (ws[r &= m] != null) {       // collision
+int m = n - 1;
-int probes = 0;             // step by approx half size
+i = ((s << 1) | 1) & m;               // odd-numbered indices
+if (ws[i] != null) {                  // collision
+int probes = 0;                   // step by approx half n
 int step = (n <= 4) ? 2 : ((n >>> 1) & EVENMASK) + 2;
-while (ws[r = (r + step) & m] != null) {
+while (ws[i = (i + step) & m] != null) {
 if (++probes >= n) {
 workQueues = ws = Arrays.copyOf(ws, n <<= 1);
 m = n - 1;
 probes = 0;
 }
 }
 }
-w.poolIndex = (short)r;
+w.hint = s;                           // use as random seed
-w.eventCount = r; // volatile write orders
+w.config = i | mode;
-ws[r] = w;
+w.scanState = i;                      // publication fence
+ws[i] = w;
 }
 } finally {
-if (!U.compareAndSwapInt(this, PLOCK, ps, nps))
+unlockRunState(rs, rs & ~RSLOCK);
-releasePlock(nps);
+}
-}
+wt.setName(workerNamePrefix.concat(Integer.toString(i >>> 1)));
-wt.setName(workerNamePrefix.concat(Integer.toString(w.poolIndex >>> 1)));
 return w;
 }
 /**
 * Final callback from terminating worker, as well as upon failure
 * @param ex the exception causing failure, or null if none
 */
 final void deregisterWorker(ForkJoinWorkerThread wt, Throwable ex) {
 WorkQueue w = null;
 if (wt != null && (w = wt.workQueue) != null) {
-int ps;
+WorkQueue[] ws;                           // remove index from array
-w.qlock = -1;                // ensure set
+int idx = w.config & SMASK;
-U.getAndAddLong(this, STEALCOUNT, w.nsteals); // collect steals
+int rs = lockRunState();
-if (((ps = plock) & PL_LOCK) != 0 ||
+if ((ws = workQueues) != null && ws.length > idx && ws[idx] == w)
-!U.compareAndSwapInt(this, PLOCK, ps, ps += PL_LOCK))
+ws[idx] = null;
-ps = acquirePlock();
+unlockRunState(rs, rs & ~RSLOCK);
-int nps = (ps & SHUTDOWN) | ((ps + PL_LOCK) & ~SHUTDOWN);
+}
-try {
+long c;                                       // decrement counts
-int idx = w.poolIndex;
-WorkQueue[] ws = workQueues;
-if (ws != null && idx >= 0 && idx < ws.length && ws[idx] == w)
-ws[idx] = null;
-} finally {
-if (!U.compareAndSwapInt(this, PLOCK, ps, nps))
-releasePlock(nps);
-}
-}
-long c;                          // adjust ctl counts
 do {} while (!U.compareAndSwapLong
-(this, CTL, c = ctl, (((c - AC_UNIT) & AC_MASK) |
+(this, CTL, c = ctl, ((AC_MASK & (c - AC_UNIT)) |
-((c - TC_UNIT) & TC_MASK) |
+(TC_MASK & (c - TC_UNIT)) |
-(c & ~(AC_MASK|TC_MASK)))));
+(SP_MASK & c))));
+if (w != null) {
-if (!tryTerminate(false, false) && w != null && w.array != null) {
+w.qlock = -1;                             // ensure set
-w.cancelAll();               // cancel remaining tasks
+w.transferStealCount(this);
-WorkQueue[] ws; WorkQueue v; Thread p; int u, i, e;
+w.cancelAll();                            // cancel remaining tasks
-while ((u = (int)((c = ctl) >>> 32)) < 0 && (e = (int)c) >= 0) {
+}
-if (e > 0) {             // activate or create replacement
+for (;;) {                                    // possibly replace
-if ((ws = workQueues) == null ||
+WorkQueue[] ws; int m, sp;
-(i = e & SMASK) >= ws.length ||
+if (tryTerminate(false, false) || w == null || w.array == null ||
-(v = ws[i]) == null)
+(runState & STOP) != 0 || (ws = workQueues) == null ||
-break;
+(m = ws.length - 1) < 0)              // already terminating
-long nc = (((long)(v.nextWait & E_MASK)) |
+break;
-((long)(u + UAC_UNIT) << 32));
+if ((sp = (int)(c = ctl)) != 0) {         // wake up replacement
-if (v.eventCount != (e | INT_SIGN))
+if (tryRelease(c, ws[sp & m], AC_UNIT))
-break;
-if (U.compareAndSwapLong(this, CTL, c, nc)) {
-v.eventCount = (e + E_SEQ) & E_MASK;
-if ((p = v.parker) != null)
-U.unpark(p);
-break;
-}
-}
-else {
-if ((short)u < 0)
-tryAddWorker();
 break;
 }
-}
+else if (ex != null && (c & ADD_WORKER) != 0L) {
-}
+tryAddWorker(c);                      // create replacement
-if (ex == null)                     // help clean refs on way out
+break;
+}
+else                                      // don't need replacement
+break;
+}
+if (ex == null)                               // help clean on way out
 ForkJoinTask.helpExpungeStaleExceptions();
-else                                // rethrow
+else                                          // rethrow
 ForkJoinTask.rethrow(ex);
 }
-// Submissions
+// Signalling
-/**
-* Unless shutting down, adds the given task to a submission queue
-* at submitter's current queue index (modulo submission
-* range). Only the most common path is directly handled in this
-* method. All others are relayed to fullExternalPush.
-*
-* @param task the task. Caller must ensure non-null.
-*/
-final void externalPush(ForkJoinTask<?> task) {
-WorkQueue q; int m, s, n, am; ForkJoinTask<?>[] a;
-int r = ThreadLocalRandom.getProbe();
-int ps = plock;
-WorkQueue[] ws = workQueues;
-if (ps > 0 && ws != null && (m = (ws.length - 1)) >= 0 &&
-(q = ws[m & r & SQMASK]) != null && r != 0 &&
-U.compareAndSwapInt(q, QLOCK, 0, 1)) { // lock
-if ((a = q.array) != null &&
-(am = a.length - 1) > (n = (s = q.top) - q.base)) {
-int j = ((am & s) << ASHIFT) + ABASE;
-U.putOrderedObject(a, j, task);
-q.top = s + 1;                     // push on to deque
-q.qlock = 0;
-if (n <= 1)
-signalWork(ws, q);
-return;
-}
-q.qlock = 0;
-}
-fullExternalPush(task);
-}
-/**
-* Full version of externalPush. This method is called, among
-* other times, upon the first submission of the first task to the
-* pool, so must perform secondary initialization.  It also
-* detects first submission by an external thread by looking up
-* its ThreadLocal, and creates a new shared queue if the one at
-* index if empty or contended. The plock lock body must be
-* exception-free (so no try/finally) so we optimistically
-* allocate new queues outside the lock and throw them away if
-* (very rarely) not needed.
-*
-* Secondary initialization occurs when plock is zero, to create
-* workQueue array and set plock to a valid value.  This lock body
-* must also be exception-free. Because the plock seq value can
-* eventually wrap around zero, this method harmlessly fails to
-* reinitialize if workQueues exists, while still advancing plock.
-*/
-private void fullExternalPush(ForkJoinTask<?> task) {
-int r;
-if ((r = ThreadLocalRandom.getProbe()) == 0) {
-ThreadLocalRandom.localInit();
-r = ThreadLocalRandom.getProbe();
-}
-for (;;) {
-WorkQueue[] ws; WorkQueue q; int ps, m, k;
-boolean move = false;
-if ((ps = plock) < 0)
-throw new RejectedExecutionException();
-else if (ps == 0 || (ws = workQueues) == null ||
-(m = ws.length - 1) < 0) { // initialize workQueues
-int p = parallelism;            // find power of two table size
-int n = (p > 1) ? p - 1 : 1;    // ensure at least 2 slots
-n |= n >>> 1; n |= n >>> 2;  n |= n >>> 4;
-n |= n >>> 8; n |= n >>> 16; n = (n + 1) << 1;
-WorkQueue[] nws = ((ws = workQueues) == null || ws.length == 0 ?
-new WorkQueue[n] : null);
-if (((ps = plock) & PL_LOCK) != 0 ||
-!U.compareAndSwapInt(this, PLOCK, ps, ps += PL_LOCK))
-ps = acquirePlock();
-if (((ws = workQueues) == null || ws.length == 0) && nws != null)
-workQueues = nws;
-int nps = (ps & SHUTDOWN) | ((ps + PL_LOCK) & ~SHUTDOWN);
-if (!U.compareAndSwapInt(this, PLOCK, ps, nps))
-releasePlock(nps);
-}
-else if ((q = ws[k = r & m & SQMASK]) != null) {
-if (q.qlock == 0 && U.compareAndSwapInt(q, QLOCK, 0, 1)) {
-ForkJoinTask<?>[] a = q.array;
-int s = q.top;
-boolean submitted = false;
-try {                      // locked version of push
-if ((a != null && a.length > s + 1 - q.base) ||
-(a = q.growArray()) != null) {   // must presize
-int j = (((a.length - 1) & s) << ASHIFT) + ABASE;
-U.putOrderedObject(a, j, task);
-q.top = s + 1;
-submitted = true;
-}
-} finally {
-q.qlock = 0;  // unlock
-}
-if (submitted) {
-signalWork(ws, q);
-return;
-}
-}
-move = true; // move on failure
-}
-else if (((ps = plock) & PL_LOCK) == 0) { // create new queue
-q = new WorkQueue(this, null, SHARED_QUEUE, r);
-q.poolIndex = (short)k;
-if (((ps = plock) & PL_LOCK) != 0 ||
-!U.compareAndSwapInt(this, PLOCK, ps, ps += PL_LOCK))
-ps = acquirePlock();
-if ((ws = workQueues) != null && k < ws.length && ws[k] == null)
-ws[k] = q;
-int nps = (ps & SHUTDOWN) | ((ps + PL_LOCK) & ~SHUTDOWN);
-if (!U.compareAndSwapInt(this, PLOCK, ps, nps))
-releasePlock(nps);
-}
-else
-move = true; // move if busy
-if (move)
-r = ThreadLocalRandom.advanceProbe(r);
-}
-}
-// Maintaining ctl counts
-/**
-* Increments active count; mainly called upon return from blocking.
-*/
-final void incrementActiveCount() {
-long c;
-do {} while (!U.compareAndSwapLong
-(this, CTL, c = ctl, ((c & ~AC_MASK) |
-((c & AC_MASK) + AC_UNIT))));
-}
 /**
 * Tries to create or activate a worker if too few are active.
 *
 * @param ws the worker array to use to find signallees
-* @param q if non-null, the queue holding tasks to be processed
+* @param q a WorkQueue --if non-null, don't retry if now empty
 */
 final void signalWork(WorkQueue[] ws, WorkQueue q) {
-for (;;) {
+long c; int sp, i; WorkQueue v; Thread p;
-long c; int e, u, i; WorkQueue w; Thread p;
+while ((c = ctl) < 0L) {                       // too few active
-if ((u = (int)((c = ctl) >>> 32)) >= 0)
+if ((sp = (int)c) == 0) {                  // no idle workers
+if ((c & ADD_WORKER) != 0L)            // too few workers
+tryAddWorker(c);
 break;
-if ((e = (int)c) <= 0) {
+}
-if ((short)u < 0)
+if (ws == null)                            // unstarted/terminated
-tryAddWorker();
 break;
-}
+if (ws.length <= (i = sp & SMASK))         // terminated
-if (ws == null || ws.length <= (i = e & SMASK) ||
-(w = ws[i]) == null)
 break;
-long nc = (((long)(w.nextWait & E_MASK)) |
+if ((v = ws[i]) == null)                   // terminating
-((long)(u + UAC_UNIT)) << 32);
+break;
-int ne = (e + E_SEQ) & E_MASK;
+int vs = (sp + SS_SEQ) & ~INACTIVE;        // next scanState
-if (w.eventCount == (e | INT_SIGN) &&
+int d = sp - v.scanState;                  // screen CAS
-U.compareAndSwapLong(this, CTL, c, nc)) {
+long nc = (UC_MASK & (c + AC_UNIT)) | (SP_MASK & v.stackPred);
-w.eventCount = ne;
+if (d == 0 && U.compareAndSwapLong(this, CTL, c, nc)) {
-if ((p = w.parker) != null)
+v.scanState = vs;                      // activate v
+if ((p = v.parker) != null)
 U.unpark(p);
 break;
 }
-if (q != null && q.base >= q.top)
+if (q != null && q.base == q.top)          // no more work
 break;
 }
 }
+/**
+* Signals and releases worker v if it is top of idle worker
+* stack.  This performs a one-shot version of signalWork only if
+* there is (apparently) at least one idle worker.
+*
+* @param c incoming ctl value
+* @param v if non-null, a worker
+* @param inc the increment to active count (zero when compensating)
+* @return true if successful
+*/
+private boolean tryRelease(long c, WorkQueue v, long inc) {
+int sp = (int)c, vs = (sp + SS_SEQ) & ~INACTIVE; Thread p;
+if (v != null && v.scanState == sp) {          // v is at top of stack
+long nc = (UC_MASK & (c + inc)) | (SP_MASK & v.stackPred);
+if (U.compareAndSwapLong(this, CTL, c, nc)) {
+v.scanState = vs;
+if ((p = v.parker) != null)
+U.unpark(p);
+return true;
+}
+}
+return false;
+}
 // Scanning for tasks
 /**
 * Top-level runloop for workers, called by ForkJoinWorkerThread.run.
 */
 final void runWorker(WorkQueue w) {
-w.growArray(); // allocate queue
+w.growArray();                   // allocate queue
-for (int r = w.hint; scan(w, r) == 0; ) {
+int seed = w.hint;               // initially holds randomization hint
+int r = (seed == 0) ? 1 : seed;  // avoid 0 for xorShift
+for (ForkJoinTask<?> t;;) {
+if ((t = scan(w, r)) != null)
+w.runTask(t);
+else if (!awaitWork(w, r))
+break;
 r ^= r << 13; r ^= r >>> 17; r ^= r << 5; // xorshift
 }
 }
 /**
-* Scans for and, if found, runs one task, else possibly
+* Scans for and tries to steal a top-level task. Scans start at a
-* inactivates the worker. This method operates on single reads of
+* random location, randomly moving on apparent contention,
-* volatile state and is designed to be re-invoked continuously,
+* otherwise continuing linearly until reaching two consecutive
-* in part because it returns upon detecting inconsistencies,
+* empty passes over all queues with the same checksum (summing
-* contention, or state changes that indicate possible success on
+* each base index of each queue, that moves on each steal), at
-* re-invocation.
+* which point the worker tries to inactivate and then re-scans,
-*
+* attempting to re-activate (itself or some other worker) if
-* The scan searches for tasks across queues starting at a random
+* finding a task; otherwise returning null to await work.  Scans
-* index, checking each at least twice.  The scan terminates upon
+* otherwise touch as little memory as possible, to reduce
-* either finding a non-empty queue, or completing the sweep. If
+* disruption on other scanning threads.
-* the worker is not inactivated, it takes and runs a task from
-* this queue. Otherwise, if not activated, it tries to activate
-* itself or some other worker by signalling. On failure to find a
-* task, returns (for retry) if pool state may have changed during
-* an empty scan, or tries to inactivate if active, else possibly
-* blocks or terminates via method awaitWork.
 *
 * @param w the worker (via its WorkQueue)
 * @param r a random seed
-* @return worker qlock status if would have waited, else 0
+* @return a task, or null if none found
 */
-private final int scan(WorkQueue w, int r) {
+private ForkJoinTask<?> scan(WorkQueue w, int r) {
 WorkQueue[] ws; int m;
-long c = ctl;                            // for consistency check
+if ((ws = workQueues) != null && (m = ws.length - 1) > 0 && w != null) {
-if ((ws = workQueues) != null && (m = ws.length - 1) >= 0 && w != null) {
+int ss = w.scanState;                     // initially non-negative
-for (int j = m + m + 1, ec = w.eventCount;;) {
+for (int origin = r & m, k = origin, oldSum = 0, checkSum = 0;;) {
-WorkQueue q; int b, e; ForkJoinTask<?>[] a; ForkJoinTask<?> t;
+WorkQueue q; ForkJoinTask<?>[] a; ForkJoinTask<?> t;
-if ((q = ws[(r - j) & m]) != null &&
+int b, n; long c;
-(b = q.base) - q.top < 0 && (a = q.array) != null) {
+if ((q = ws[k]) != null) {
-long i = (((a.length - 1) & b) << ASHIFT) + ABASE;
+if ((n = (b = q.base) - q.top) < 0 &&
-if ((t = ((ForkJoinTask<?>)
+(a = q.array) != null) {      // non-empty
-U.getObjectVolatile(a, i))) != null) {
+long i = (((a.length - 1) & b) << ASHIFT) + ABASE;
-if (ec < 0)
+if ((t = ((ForkJoinTask<?>)
-helpRelease(c, ws, w, q, b);
+U.getObjectVolatile(a, i))) != null &&
-else if (q.base == b &&
+q.base == b) {
-U.compareAndSwapObject(a, i, t, null)) {
+if (ss >= 0) {
-U.putOrderedInt(q, QBASE, b + 1);
+if (U.compareAndSwapObject(a, i, t, null)) {
-if ((b + 1) - q.top < 0)
+q.base = b + 1;
-signalWork(ws, q);
+if (n < -1)       // signal others
-w.runTask(t);
+signalWork(ws, q);
+return t;
+}
+}
+else if (oldSum == 0 &&   // try to activate
+w.scanState < 0)
+tryRelease(c = ctl, ws[m & (int)c], AC_UNIT);
 }
+if (ss < 0)                   // refresh
+ss = w.scanState;
+r ^= r << 1; r ^= r >>> 3; r ^= r << 10;
+origin = k = r & m;           // move and rescan
+oldSum = checkSum = 0;
+continue;
 }
-break;
+checkSum += b;
 }
-else if (--j < 0) {
+if ((k = (k + 1) & m) == origin) {    // continue until stable
-if ((ec | (e = (int)c)) < 0) // inactive or terminating
+if ((ss >= 0 || (ss == (ss = w.scanState))) &&
-return awaitWork(w, c, ec);
+oldSum == (oldSum = checkSum)) {
-else if (ctl == c) {         // try to inactivate and enqueue
+if (ss < 0 || w.qlock < 0)    // already inactive
-long nc = (long)ec | ((c - AC_UNIT) & (AC_MASK|TC_MASK));
+break;
-w.nextWait = e;
+int ns = ss | INACTIVE;       // try to inactivate
-w.eventCount = ec | INT_SIGN;
+long nc = ((SP_MASK & ns) |
-if (!U.compareAndSwapLong(this, CTL, c, nc))
+(UC_MASK & ((c = ctl) - AC_UNIT)));
-w.eventCount = ec;   // back out
+w.stackPred = (int)c;         // hold prev stack top
+U.putInt(w, QSCANSTATE, ns);
+if (U.compareAndSwapLong(this, CTL, c, nc))
+ss = ns;
+else
+w.scanState = ss;         // back out
 }
-break;
+checkSum = 0;
 }
 }
 }
-return 0;
+return null;
 }
 /**
-* A continuation of scan(), possibly blocking or terminating
+* Possibly blocks worker w waiting for a task to steal, or
-* worker w. Returns without blocking if pool state has apparently
+* returns false if the worker should terminate.  If inactivating
-* changed since last invocation.  Also, if inactivating w has
+* w has caused the pool to become quiescent, checks for pool
-* caused the pool to become quiescent, checks for pool
 * termination, and, so long as this is not the only worker, waits
-* for event for up to a given duration.  On timeout, if ctl has
+* for up to a given duration.  On timeout, if ctl has not
-* not changed, terminates the worker, which will in turn wake up
+* changed, terminates the worker, which will in turn wake up
 * another worker to possibly repeat this process.
 *
 * @param w the calling worker
-* @param c the ctl value on entry to scan
+* @param r a random seed (for spins)
-* @param ec the worker's eventCount on entry to scan
+* @return false if the worker should terminate
 */
-private final int awaitWork(WorkQueue w, long c, int ec) {
+private boolean awaitWork(WorkQueue w, int r) {
-int stat, ns; long parkTime, deadline;
+if (w == null || w.qlock < 0)                 // w is terminating
-if ((stat = w.qlock) >= 0 && w.eventCount == ec && ctl == c &&
+return false;
-!Thread.interrupted()) {
+for (int pred = w.stackPred, spins = SPINS, ss;;) {
-int e = (int)c;
+if ((ss = w.scanState) >= 0)
-int u = (int)(c >>> 32);
+break;
-int d = (u >> UAC_SHIFT) + parallelism; // active count
+else if (spins > 0) {
+r ^= r << 6; r ^= r >>> 21; r ^= r << 7;
-if (e < 0 || (d <= 0 && tryTerminate(false, false)))
+if (r >= 0 && --spins == 0) {         // randomize spins
-stat = w.qlock = -1;          // pool is terminating
+WorkQueue v; WorkQueue[] ws; int s, j; AtomicLong sc;
-else if ((ns = w.nsteals) != 0) { // collect steals and retry
+if (pred != 0 && (ws = workQueues) != null &&
-w.nsteals = 0;
+(j = pred & SMASK) < ws.length &&
-U.getAndAddLong(this, STEALCOUNT, (long)ns);
+(v = ws[j]) != null &&        // see if pred parking
-}
+(v.parker == null || v.scanState >= 0))
-else {
+spins = SPINS;                // continue spinning
-long pc = ((d > 0 || ec != (e | INT_SIGN)) ? 0L :
+}
-((long)(w.nextWait & E_MASK)) | // ctl to restore
+}
-((long)(u + UAC_UNIT)) << 32);
+else if (w.qlock < 0)                     // recheck after spins
-if (pc != 0L) {               // timed wait if last waiter
+return false;
-int dc = -(short)(c >>> TC_SHIFT);
+else if (!Thread.interrupted()) {
-parkTime = (dc < 0 ? FAST_IDLE_TIMEOUT:
+long c, prevctl, parkTime, deadline;
-(dc + 1) * IDLE_TIMEOUT);
+int ac = (int)((c = ctl) >> AC_SHIFT) + (config & SMASK);
+if ((ac <= 0 && tryTerminate(false, false)) ||
+(runState & STOP) != 0)           // pool terminating
+return false;
+if (ac <= 0 && ss == (int)c) {        // is last waiter
+prevctl = (UC_MASK & (c + AC_UNIT)) | (SP_MASK & pred);
+int t = (short)(c >>> TC_SHIFT);  // shrink excess spares
+if (t > 2 && U.compareAndSwapLong(this, CTL, c, prevctl))
+return false;                 // else use timed wait
+parkTime = IDLE_TIMEOUT * ((t >= 0) ? 1 : 1 - t);
 deadline = System.nanoTime() + parkTime - TIMEOUT_SLOP;
 }
 else
-parkTime = deadline = 0L;
+prevctl = parkTime = deadline = 0L;
-if (w.eventCount == ec && ctl == c) {
+Thread wt = Thread.currentThread();
-Thread wt = Thread.currentThread();
+U.putObject(wt, PARKBLOCKER, this);   // emulate LockSupport
-U.putObject(wt, PARKBLOCKER, this);
+w.parker = wt;
-w.parker = wt;            // emulate LockSupport.park
+if (w.scanState < 0 && ctl == c)      // recheck before park
-if (w.eventCount == ec && ctl == c)
+U.park(false, parkTime);
-U.park(false, parkTime);  // must recheck before park
+U.putOrderedObject(w, QPARKER, null);
-w.parker = null;
+U.putObject(wt, PARKBLOCKER, null);
-U.putObject(wt, PARKBLOCKER, null);
+if (w.scanState >= 0)
-if (parkTime != 0L && ctl == c &&
+break;
-deadline - System.nanoTime() <= 0L &&
+if (parkTime != 0L && ctl == c &&
-U.compareAndSwapLong(this, CTL, c, pc))
+deadline - System.nanoTime() <= 0L &&
-stat = w.qlock = -1;  // shrink pool
+U.compareAndSwapLong(this, CTL, c, prevctl))
+return false;                     // shrink pool
+}
+}
+return true;
+}
+// Joining tasks
+/**
+* Tries to steal and run tasks within the target's computation.
+* Uses a variant of the top-level algorithm, restricted to tasks
+* with the given task as ancestor: It prefers taking and running
+* eligible tasks popped from the worker's own queue (via
+* popCC). Otherwise it scans others, randomly moving on
+* contention or execution, deciding to give up based on a
+* checksum (via return codes frob pollAndExecCC). The maxTasks
+* argument supports external usages; internal calls use zero,
+* allowing unbounded steps (external calls trap non-positive
+* values).
+*
+* @param w caller
+* @param maxTasks if non-zero, the maximum number of other tasks to run
+* @return task status on exit
+*/
+final int helpComplete(WorkQueue w, CountedCompleter<?> task,
+int maxTasks) {
+WorkQueue[] ws; int s = 0, m;
+if ((ws = workQueues) != null && (m = ws.length - 1) >= 0 &&
+task != null && w != null) {
+int mode = w.config;                 // for popCC
+int r = w.hint ^ w.top;              // arbitrary seed for origin
+int origin = r & m;                  // first queue to scan
+int h = 1;                           // 1:ran, >1:contended, <0:hash
+for (int k = origin, oldSum = 0, checkSum = 0;;) {
+CountedCompleter<?> p; WorkQueue q;
+if ((s = task.status) < 0)
+break;
+if (h == 1 && (p = w.popCC(task, mode)) != null) {
+p.doExec();                  // run local task
+if (maxTasks != 0 && --maxTasks == 0)
+break;
+origin = k;                  // reset
+oldSum = checkSum = 0;
 }
-}
+else {                           // poll other queues
-}
+if ((q = ws[k]) == null)
-return stat;
+h = 0;
-}
+else if ((h = q.pollAndExecCC(task)) < 0)
+checkSum += h;
-/**
+if (h > 0) {
-* Possibly releases (signals) a worker. Called only from scan()
+if (h == 1 && maxTasks != 0 && --maxTasks == 0)
-* when a worker with apparently inactive status finds a non-empty
+break;
-* queue. This requires revalidating all of the associated state
+r ^= r << 13; r ^= r >>> 17; r ^= r << 5; // xorshift
-* from caller.
+origin = k = r & m;      // move and restart
-*/
+oldSum = checkSum = 0;
-private final void helpRelease(long c, WorkQueue[] ws, WorkQueue w,
+}
-WorkQueue q, int b) {
+else if ((k = (k + 1) & m) == origin) {
-WorkQueue v; int e, i; Thread p;
+if (oldSum == (oldSum = checkSum))
-if (w != null && w.eventCount < 0 && (e = (int)c) > 0 &&
+break;
-ws != null && ws.length > (i = e & SMASK) &&
+checkSum = 0;
-(v = ws[i]) != null && ctl == c) {
+}
-long nc = (((long)(v.nextWait & E_MASK)) |
+}
-((long)((int)(c >>> 32) + UAC_UNIT)) << 32);
+}
-int ne = (e + E_SEQ) & E_MASK;
+}
-if (q != null && q.base == b && w.eventCount < 0 &&
+return s;
-v.eventCount == (e | INT_SIGN) &&
-U.compareAndSwapLong(this, CTL, c, nc)) {
-v.eventCount = ne;
-if ((p = v.parker) != null)
-U.unpark(p);
-}
-}
 }
 /**
 * Tries to locate and execute tasks for a stealer of the given
 * task, or in turn one of its stealers, Traces currentSteal ->
 * currentJoin links looking for a thread working on a descendant
 * of the given task and with a non-empty queue to steal back and
 * execute tasks from. The first call to this method upon a
 * waiting join will often entail scanning/search, (which is OK
 * because the joiner has nothing better to do), but this method
-* leaves hints in workers to speed up subsequent calls. The
+* leaves hints in workers to speed up subsequent calls.
-* implementation is very branchy to cope with potential
+*
-* inconsistencies or loops encountering chains that are stale,
+* @param w caller
-* unknown, or so long that they are likely cyclic.
-*
-* @param joiner the joining worker
 * @param task the task to join
-* @return 0 if no progress can be made, negative if task
+*/
-* known complete, else positive
+private void helpStealer(WorkQueue w, ForkJoinTask<?> task) {
-*/
+WorkQueue[] ws = workQueues;
-private int tryHelpStealer(WorkQueue joiner, ForkJoinTask<?> task) {
+int oldSum = 0, checkSum, m;
-int stat = 0, steps = 0;                    // bound to avoid cycles
+if (ws != null && (m = ws.length - 1) >= 0 && w != null &&
-if (task != null && joiner != null &&
+task != null) {
-joiner.base - joiner.top >= 0) {        // hoist checks
+do {                                       // restart point
-restart: for (;;) {
+checkSum = 0;                          // for stability check
-ForkJoinTask<?> subtask = task;     // current target
+ForkJoinTask<?> subtask;
-for (WorkQueue j = joiner, v;;) {   // v is stealer of subtask
+WorkQueue j = w, v;                    // v is subtask stealer
-WorkQueue[] ws; int m, s, h;
+descent: for (subtask = task; subtask.status >= 0; ) {
-if ((s = task.status) < 0) {
+for (int h = j.hint | 1, k = 0, i; ; k += 2) {
-stat = s;
+if (k > m)                     // can't find stealer
-break restart;
+break descent;
-}
+if ((v = ws[i = (h + k) & m]) != null) {
-if ((ws = workQueues) == null || (m = ws.length - 1) <= 0)
+if (v.currentSteal == subtask) {
-break restart;              // shutting down
+j.hint = i;
-if ((v = ws[h = (j.hint | 1) & m]) == null ||
-v.currentSteal != subtask) {
-for (int origin = h;;) {    // find stealer
-if (((h = (h + 2) & m) & 15) == 1 &&
-(subtask.status < 0 || j.currentJoin != subtask))
-continue restart;   // occasional staleness check
-if ((v = ws[h]) != null &&
-v.currentSteal == subtask) {
-j.hint = h;        // save hint
 break;
 }
-if (h == origin)
+checkSum += v.base;
-break restart;      // cannot find stealer
 }
 }
-for (;;) { // help stealer or descend to its stealer
+for (;;) {                         // help v or descend
 ForkJoinTask<?>[] a; int b;
-if (subtask.status < 0)     // surround probes with
+checkSum += (b = v.base);
-continue restart;       //   consistency checks
+ForkJoinTask<?> next = v.currentJoin;
-if ((b = v.base) - v.top < 0 && (a = v.array) != null) {
+if (subtask.status < 0 || j.currentJoin != subtask ||
-int i = (((a.length - 1) & b) << ASHIFT) + ABASE;
+v.currentSteal != subtask) // stale
-ForkJoinTask<?> t =
+break descent;
-(ForkJoinTask<?>)U.getObjectVolatile(a, i);
+if (b - v.top >= 0 || (a = v.array) == null) {
-if (subtask.status < 0 || j.currentJoin != subtask ||
+if ((subtask = next) == null)
-v.currentSteal != subtask)
+break descent;
-continue restart;   // stale
+j = v;
-stat = 1;               // apparent progress
+break;
-if (v.base == b) {
-if (t == null)
-break restart;
-if (U.compareAndSwapObject(a, i, t, null)) {
-U.putOrderedInt(v, QBASE, b + 1);
-ForkJoinTask<?> ps = joiner.currentSteal;
-int jt = joiner.top;
-do {
-joiner.currentSteal = t;
-t.doExec(); // clear local tasks too
-} while (task.status >= 0 &&
-joiner.top != jt &&
-(t = joiner.pop()) != null);
-joiner.currentSteal = ps;
-break restart;
-}
-}
 }
-else {                      // empty -- try to descend
+int i = (((a.length - 1) & b) << ASHIFT) + ABASE;
-ForkJoinTask<?> next = v.currentJoin;
+ForkJoinTask<?> t = ((ForkJoinTask<?>)
-if (subtask.status < 0 || j.currentJoin != subtask ||
+U.getObjectVolatile(a, i));
-v.currentSteal != subtask)
+if (v.base == b) {
-continue restart;   // stale
+if (t == null)             // stale
-else if (next == null || ++steps == MAX_HELP)
+break descent;
-break restart;      // dead-end or maybe cyclic
+if (U.compareAndSwapObject(a, i, t, null)) {
-else {
+v.base = b + 1;
-subtask = next;
+ForkJoinTask<?> ps = w.currentSteal;
-j = v;
+int top = w.top;
-break;
+do {
+U.putOrderedObject(w, QCURRENTSTEAL, t);
+t.doExec();        // clear local tasks too
+} while (task.status >= 0 &&
+w.top != top &&
+(t = w.pop()) != null);
+U.putOrderedObject(w, QCURRENTSTEAL, ps);
+if (w.base != w.top)
+return;            // can't further help
 }
 }
 }
 }
-}
+} while (task.status >= 0 && oldSum != (oldSum = checkSum));
 }
-return stat;
+}
-}
+/**
-/**
+* Tries to decrement active count (sometimes implicitly) and
-* Analog of tryHelpStealer for CountedCompleters. Tries to steal
+* possibly release or create a compensating worker in preparation
-* and run tasks within the target's computation.
+* for blocking. Returns false (retryable by caller), on
-*
+* contention, detected staleness, instability, or termination.
-* @param task the task to join
+*
-* @param maxTasks the maximum number of other tasks to run
+* @param w caller
 */
-final int helpComplete(WorkQueue joiner, CountedCompleter<?> task,
+private boolean tryCompensate(WorkQueue w) {
-int maxTasks) {
+boolean canBlock;
-WorkQueue[] ws; int m;
+WorkQueue[] ws; long c; int m, pc, sp;
+if (w == null || w.qlock < 0 ||           // caller terminating
+(ws = workQueues) == null || (m = ws.length - 1) <= 0 ||
+(pc = config & SMASK) == 0)           // parallelism disabled
+canBlock = false;
+else if ((sp = (int)(c = ctl)) != 0)      // release idle worker
+canBlock = tryRelease(c, ws[sp & m], 0L);
+else {
+int ac = (int)(c >> AC_SHIFT) + pc;
+int tc = (short)(c >> TC_SHIFT) + pc;
+int nbusy = 0;                        // validate saturation
+for (int i = 0; i <= m; ++i) {        // two passes of odd indices
+WorkQueue v;
+if ((v = ws[((i << 1) | 1) & m]) != null) {
+if ((v.scanState & SCANNING) != 0)
+break;
+++nbusy;
+}
+}
+if (nbusy != (tc << 1) || ctl != c)
+canBlock = false;                 // unstable or stale
+else if (tc >= pc && ac > 1 && w.isEmpty()) {
+long nc = ((AC_MASK & (c - AC_UNIT)) |
+(~AC_MASK & c));       // uncompensated
+canBlock = U.compareAndSwapLong(this, CTL, c, nc);
+}
+else if (tc >= MAX_CAP ||
+(this == common && tc >= pc + commonMaxSpares))
+throw new RejectedExecutionException(
+"Thread limit exceeded replacing blocked worker");
+else {                                // similar to tryAddWorker
+boolean add = false; int rs;      // CAS within lock
+long nc = ((AC_MASK & c) |
+(TC_MASK & (c + TC_UNIT)));
+if (((rs = lockRunState()) & STOP) == 0)
+add = U.compareAndSwapLong(this, CTL, c, nc);
+unlockRunState(rs, rs & ~RSLOCK);
+canBlock = add && createWorker(); // throws on exception
+}
+}
+return canBlock;
+}
+/**
+* Helps and/or blocks until the given task is done or timeout.
+*
+* @param w caller
+* @param task the task
+* @param deadline for timed waits, if nonzero
+* @return task status on exit
+*/
+final int awaitJoin(WorkQueue w, ForkJoinTask<?> task, long deadline) {
 int s = 0;
-if ((ws = workQueues) != null && (m = ws.length - 1) >= 0 &&
+if (task != null && w != null) {
-joiner != null && task != null) {
+ForkJoinTask<?> prevJoin = w.currentJoin;
-int j = joiner.poolIndex;
+U.putOrderedObject(w, QCURRENTJOIN, task);
-int scans = m + m + 1;
+CountedCompleter<?> cc = (task instanceof CountedCompleter) ?
-long c = 0L;              // for stability check
+(CountedCompleter<?>)task : null;
-for (int k = scans; ; j += 2) {
+for (;;) {
-WorkQueue q;
 if ((s = task.status) < 0)
 break;
-else if (joiner.internalPopAndExecCC(task)) {
+if (cc != null)
-if (--maxTasks <= 0) {
+helpComplete(w, cc, 0);
-s = task.status;
+else if (w.base == w.top || w.tryRemoveAndExec(task))
-break;
+helpStealer(w, task);
-}
+if ((s = task.status) < 0)
-k = scans;
+break;
+long ms, ns;
+if (deadline == 0L)
+ms = 0L;
+else if ((ns = deadline - System.nanoTime()) <= 0L)
+break;
+else if ((ms = TimeUnit.NANOSECONDS.toMillis(ns)) <= 0L)
+ms = 1L;
+if (tryCompensate(w)) {
+task.internalWait(ms);
+U.getAndAddLong(this, CTL, AC_UNIT);
 }
-else if ((s = task.status) < 0)
+}
-break;
+U.putOrderedObject(w, QCURRENTJOIN, prevJoin);
-else if ((q = ws[j & m]) != null && q.pollAndExecCC(task)) {
-if (--maxTasks <= 0) {
-s = task.status;
-break;
-}
-k = scans;
-}
-else if (--k < 0) {
-if (c == (c = ctl))
-break;
-k = scans;
-}
-}
 }
 return s;
 }
-/**
+// Specialized scanning
-* Tries to decrement active count (sometimes implicitly) and
-* possibly release or create a compensating worker in preparation
-* for blocking. Fails on contention or termination. Otherwise,
-* adds a new thread if no idle workers are available and pool
-* may become starved.
-*
-* @param c the assumed ctl value
-*/
-final boolean tryCompensate(long c) {
-WorkQueue[] ws = workQueues;
-int pc = parallelism, e = (int)c, m, tc;
-if (ws != null && (m = ws.length - 1) >= 0 && e >= 0 && ctl == c) {
-WorkQueue w = ws[e & m];
-if (e != 0 && w != null) {
-Thread p;
-long nc = ((long)(w.nextWait & E_MASK) |
-(c & (AC_MASK|TC_MASK)));
-int ne = (e + E_SEQ) & E_MASK;
-if (w.eventCount == (e | INT_SIGN) &&
-U.compareAndSwapLong(this, CTL, c, nc)) {
-w.eventCount = ne;
-if ((p = w.parker) != null)
-U.unpark(p);
-return true;   // replace with idle worker
-}
-}
-else if ((tc = (short)(c >>> TC_SHIFT)) >= 0 &&
-(int)(c >> AC_SHIFT) + pc > 1) {
-long nc = ((c - AC_UNIT) & AC_MASK) | (c & ~AC_MASK);
-if (U.compareAndSwapLong(this, CTL, c, nc))
-return true;   // no compensation
-}
-else if (tc + pc < MAX_CAP) {
-long nc = ((c + TC_UNIT) & TC_MASK) | (c & ~TC_MASK);
-if (U.compareAndSwapLong(this, CTL, c, nc)) {
-ForkJoinWorkerThreadFactory fac;
-Throwable ex = null;
-ForkJoinWorkerThread wt = null;
-try {
-if ((fac = factory) != null &&
-(wt = fac.newThread(this)) != null) {
-wt.start();
-return true;
-}
-} catch (Throwable rex) {
-ex = rex;
-}
-deregisterWorker(wt, ex); // clean up and return false
-}
-}
-}
-return false;
-}
-/**
-* Helps and/or blocks until the given task is done.
-*
-* @param joiner the joining worker
-* @param task the task
-* @return task status on exit
-*/
-final int awaitJoin(WorkQueue joiner, ForkJoinTask<?> task) {
-int s = 0;
-if (task != null && (s = task.status) >= 0 && joiner != null) {
-ForkJoinTask<?> prevJoin = joiner.currentJoin;
-joiner.currentJoin = task;
-do {} while (joiner.tryRemoveAndExec(task) && // process local tasks
-(s = task.status) >= 0);
-if (s >= 0 && (task instanceof CountedCompleter))
-s = helpComplete(joiner, (CountedCompleter<?>)task, Integer.MAX_VALUE);
-long cc = 0;        // for stability checks
-while (s >= 0 && (s = task.status) >= 0) {
-if ((s = tryHelpStealer(joiner, task)) == 0 &&
-(s = task.status) >= 0) {
-if (!tryCompensate(cc))
-cc = ctl;
-else {
-if (task.trySetSignal() && (s = task.status) >= 0) {
-synchronized (task) {
-if (task.status >= 0) {
-try {                // see ForkJoinTask
-task.wait();     //  for explanation
-} catch (InterruptedException ie) {
-}
-}
-else
-task.notifyAll();
-}
-}
-long c; // reactivate
-do {} while (!U.compareAndSwapLong
-(this, CTL, c = ctl,
-((c & ~AC_MASK) |
-((c & AC_MASK) + AC_UNIT))));
-}
-}
-}
-joiner.currentJoin = prevJoin;
-}
-return s;
-}
-/**
-* Stripped-down variant of awaitJoin used by timed joins. Tries
-* to help join only while there is continuous progress. (Caller
-* will then enter a timed wait.)
-*
-* @param joiner the joining worker
-* @param task the task
-*/
-final void helpJoinOnce(WorkQueue joiner, ForkJoinTask<?> task) {
-int s;
-if (joiner != null && task != null && (s = task.status) >= 0) {
-ForkJoinTask<?> prevJoin = joiner.currentJoin;
-joiner.currentJoin = task;
-do {} while (joiner.tryRemoveAndExec(task) && // process local tasks
-(s = task.status) >= 0);
-if (s >= 0) {
-if (task instanceof CountedCompleter)
-helpComplete(joiner, (CountedCompleter<?>)task, Integer.MAX_VALUE);
-do {} while (task.status >= 0 &&
-tryHelpStealer(joiner, task) > 0);
-}
-joiner.currentJoin = prevJoin;
-}
-}
 /**
 * Returns a (probably) non-empty steal queue, if one is found
 * during a scan, else null.  This method must be retried by
 * caller if, by the time it tries to use the queue, it is empty.
 */
 private WorkQueue findNonEmptyStealQueue() {
+WorkQueue[] ws; int m;  // one-shot version of scan loop
 int r = ThreadLocalRandom.nextSecondarySeed();
-for (;;) {
+if ((ws = workQueues) != null && (m = ws.length - 1) >= 0) {
-int ps = plock, m; WorkQueue[] ws; WorkQueue q;
+for (int origin = r & m, k = origin, oldSum = 0, checkSum = 0;;) {
-if ((ws = workQueues) != null && (m = ws.length - 1) >= 0) {
+WorkQueue q; int b;
-for (int j = (m + 1) << 2; j >= 0; --j) {
+if ((q = ws[k]) != null) {
-if ((q = ws[(((r - j) << 1) | 1) & m]) != null &&
+if ((b = q.base) - q.top < 0)
-q.base - q.top < 0)
 return q;
+checkSum += b;
 }
-}
+if ((k = (k + 1) & m) == origin) {
-if (plock == ps)
+if (oldSum == (oldSum = checkSum))
-return null;
+break;
-}
+checkSum = 0;
+}
+}
+}
+return null;
 }
 /**
 * Runs tasks until {@code isQuiescent()}. We piggyback on
 * active count ctl maintenance, but rather than blocking
 * when tasks cannot be found, we rescan until all others cannot
 * find tasks either.
 */
 final void helpQuiescePool(WorkQueue w) {
-ForkJoinTask<?> ps = w.currentSteal;
+ForkJoinTask<?> ps = w.currentSteal; // save context
 for (boolean active = true;;) {
 long c; WorkQueue q; ForkJoinTask<?> t; int b;
-while ((t = w.nextLocalTask()) != null)
+w.execLocalTasks();     // run locals before each scan
-t.doExec();
 if ((q = findNonEmptyStealQueue()) != null) {
 if (!active) {      // re-establish active count
 active = true;
-do {} while (!U.compareAndSwapLong
+U.getAndAddLong(this, CTL, AC_UNIT);
-(this, CTL, c = ctl,
-((c & ~AC_MASK) |
-((c & AC_MASK) + AC_UNIT))));
 }
-if ((b = q.base) - q.top < 0 && (t = q.pollAt(b)) != null)
+if ((b = q.base) - q.top < 0 && (t = q.pollAt(b)) != null) {
-w.runTask(t);
+U.putOrderedObject(w, QCURRENTSTEAL, t);
+t.doExec();
+if (++w.nsteals < 0)
+w.transferStealCount(this);
+}
 }
 else if (active) {      // decrement active count without queuing
-long nc = ((c = ctl) & ~AC_MASK) | ((c & AC_MASK) - AC_UNIT);
+long nc = (AC_MASK & ((c = ctl) - AC_UNIT)) | (~AC_MASK & c);
-if ((int)(nc >> AC_SHIFT) + parallelism == 0)
+if ((int)(nc >> AC_SHIFT) + (config & SMASK) <= 0)
 break;          // bypass decrement-then-increment
 if (U.compareAndSwapLong(this, CTL, c, nc))
 active = false;
 }
-else if ((int)((c = ctl) >> AC_SHIFT) + parallelism <= 0 &&
+else if ((int)((c = ctl) >> AC_SHIFT) + (config & SMASK) <= 0 &&
-U.compareAndSwapLong
+U.compareAndSwapLong(this, CTL, c, c + AC_UNIT))
-(this, CTL, c, ((c & ~AC_MASK) |
-((c & AC_MASK) + AC_UNIT))))
 break;
 }
+U.putOrderedObject(w, QCURRENTSTEAL, ps);
 }
 /**
 * Gets and removes a local or stolen task for the given worker.
 *
 }
 /**
 * Returns a cheap heuristic guide for task partitioning when
 * programmers, frameworks, tools, or languages have little or no
-* idea about task granularity.  In essence by offering this
+* idea about task granularity.  In essence, by offering this
 * method, we ask users only about tradeoffs in overhead vs
 * expected throughput and its variance, rather than how finely to
 * partition tasks.
 *
 * In a steady state strict (tree-structured) computation, each
 * leads to serious mis-estimates in some non-steady-state
 * conditions (ramp-up, ramp-down, other stalls). We can detect
 * many of these by further considering the number of "idle"
 * threads, that are known to have zero queued tasks, so
 * compensate by a factor of (#idle/#active) threads.
-*
-* Note: The approximation of #busy workers as #active workers is
-* not very good under current signalling scheme, and should be
-* improved.
 */
 static int getSurplusQueuedTaskCount() {
 Thread t; ForkJoinWorkerThread wt; ForkJoinPool pool; WorkQueue q;
 if (((t = Thread.currentThread()) instanceof ForkJoinWorkerThread)) {
-int p = (pool = (wt = (ForkJoinWorkerThread)t).pool).parallelism;
+int p = (pool = (wt = (ForkJoinWorkerThread)t).pool).
+config & SMASK;
 int n = (q = wt.workQueue).top - q.base;
 int a = (int)(pool.ctl >> AC_SHIFT) + p;
 return n - (a > (p >>>= 1) ? 0 :
 a > (p >>>= 1) ? 1 :
 a > (p >>>= 1) ? 2 :
 }
 //  Termination
 /**
-* Possibly initiates and/or completes termination.  The caller
+* Possibly initiates and/or completes termination.
-* triggering termination runs three passes through workQueues:
-* (0) Setting termination status, followed by wakeups of queued
-* workers; (1) cancelling all tasks; (2) interrupting lagging
-* threads (likely in external tasks, but possibly also blocked in
-* joins).  Each pass repeats previous steps because of potential
-* lagging thread creation.
 *
 * @param now if true, unconditionally terminate, else only
 * if no work and no active workers
 * @param enable if true, enable shutdown when next possible
 * @return true if now terminating or terminated
 */
 private boolean tryTerminate(boolean now, boolean enable) {
-int ps;
+int rs;
-if (this == common)                        // cannot shut down
+if (this == common)                       // cannot shut down
 return false;
-if ((ps = plock) >= 0) {                   // enable by setting plock
+if ((rs = runState) >= 0) {
 if (!enable)
 return false;
-if ((ps & PL_LOCK) != 0 ||
+rs = lockRunState();                  // enter SHUTDOWN phase
-!U.compareAndSwapInt(this, PLOCK, ps, ps += PL_LOCK))
+unlockRunState(rs, (rs & ~RSLOCK) | SHUTDOWN);
-ps = acquirePlock();
+}
-int nps = ((ps + PL_LOCK) & ~SHUTDOWN) | SHUTDOWN;
-if (!U.compareAndSwapInt(this, PLOCK, ps, nps))
+if ((rs & STOP) == 0) {
-releasePlock(nps);
+if (!now) {                           // check quiescence
-}
+for (long oldSum = 0L;;) {        // repeat until stable
-for (long c;;) {
+WorkQueue[] ws; WorkQueue w; int m, b; long c;
-if (((c = ctl) & STOP_BIT) != 0) {     // already terminating
+long checkSum = ctl;
-if ((short)(c >>> TC_SHIFT) + parallelism <= 0) {
+if ((int)(checkSum >> AC_SHIFT) + (config & SMASK) > 0)
-synchronized (this) {
+return false;             // still active workers
-notifyAll();               // signal when 0 workers
+if ((ws = workQueues) == null || (m = ws.length - 1) <= 0)
+break;                    // check queues
+for (int i = 0; i <= m; ++i) {
+if ((w = ws[i]) != null) {
+if ((b = w.base) != w.top || w.scanState >= 0 ||
+w.currentSteal != null) {
+tryRelease(c = ctl, ws[m & (int)c], AC_UNIT);
+return false;     // arrange for recheck
+}
+checkSum += b;
+if ((i & 1) == 0)
+w.qlock = -1;     // try to disable external
+}
 }
+if (oldSum == (oldSum = checkSum))
+break;
 }
-return true;
+}
-}
+if ((runState & STOP) == 0) {
-if (!now) {                            // check if idle & no tasks
+rs = lockRunState();              // enter STOP phase
-WorkQueue[] ws; WorkQueue w;
+unlockRunState(rs, (rs & ~RSLOCK) | STOP);
-if ((int)(c >> AC_SHIFT) + parallelism > 0)
+}
-return false;
+}
-if ((ws = workQueues) != null) {
-for (int i = 0; i < ws.length; ++i) {
+int pass = 0;                             // 3 passes to help terminate
-if ((w = ws[i]) != null &&
+for (long oldSum = 0L;;) {                // or until done or stable
-(!w.isEmpty() ||
+WorkQueue[] ws; WorkQueue w; ForkJoinWorkerThread wt; int m;
-((i & 1) != 0 && w.eventCount >= 0))) {
+long checkSum = ctl;
-signalWork(ws, w);
+if ((short)(checkSum >>> TC_SHIFT) + (config & SMASK) <= 0 ||
-return false;
+(ws = workQueues) == null || (m = ws.length - 1) <= 0) {
+if ((runState & TERMINATED) == 0) {
+rs = lockRunState();          // done
+unlockRunState(rs, (rs & ~RSLOCK) | TERMINATED);
+synchronized (this) { notifyAll(); } // for awaitTermination
+}
+break;
+}
+for (int i = 0; i <= m; ++i) {
+if ((w = ws[i]) != null) {
+checkSum += w.base;
+w.qlock = -1;                 // try to disable
+if (pass > 0) {
+w.cancelAll();            // clear queue
+if (pass > 1 && (wt = w.owner) != null) {
+if (!wt.isInterrupted()) {
+try {             // unblock join
+wt.interrupt();
+} catch (Throwable ignore) {
+}
+}
+if (w.scanState < 0)
+U.unpark(wt);     // wake up
 }
 }
 }
 }
-if (U.compareAndSwapLong(this, CTL, c, c | STOP_BIT)) {
+if (checkSum != oldSum) {             // unstable
-for (int pass = 0; pass < 3; ++pass) {
+oldSum = checkSum;
-WorkQueue[] ws; WorkQueue w; Thread wt;
+pass = 0;
-if ((ws = workQueues) != null) {
+}
-int n = ws.length;
+else if (pass > 3 && pass > m)        // can't further help
-for (int i = 0; i < n; ++i) {
+break;
-if ((w = ws[i]) != null) {
+else if (++pass > 1) {                // try to dequeue
-w.qlock = -1;
+long c; int j = 0, sp;            // bound attempts
-if (pass > 0) {
+while (j++ <= m && (sp = (int)(c = ctl)) != 0)
-w.cancelAll();
+tryRelease(c, ws[sp & m], AC_UNIT);
-if (pass > 1 && (wt = w.owner) != null) {
+}
-if (!wt.isInterrupted()) {
+}
-try {
+return true;
-wt.interrupt();
+}
-} catch (Throwable ignore) {
-}
+// External operations
-}
-U.unpark(wt);
+/**
-}
+* Full version of externalPush, handling uncommon cases, as well
-}
+* as performing secondary initialization upon the first
-}
+* submission of the first task to the pool.  It also detects
+* first submission by an external thread and creates a new shared
+* queue if the one at index if empty or contended.
+*
+* @param task the task. Caller must ensure non-null.
+*/
+private void externalSubmit(ForkJoinTask<?> task) {
+int r;                                    // initialize caller's probe
+if ((r = ThreadLocalRandom.getProbe()) == 0) {
+ThreadLocalRandom.localInit();
+r = ThreadLocalRandom.getProbe();
+}
+for (;;) {
+WorkQueue[] ws; WorkQueue q; int rs, m, k;
+boolean move = false;
+if ((rs = runState) < 0) {
+tryTerminate(false, false);     // help terminate
+throw new RejectedExecutionException();
+}
+else if ((rs & STARTED) == 0 ||     // initialize
+((ws = workQueues) == null || (m = ws.length - 1) < 0)) {
+int ns = 0;
+rs = lockRunState();
+try {
+if ((rs & STARTED) == 0) {
+U.compareAndSwapObject(this, STEALCOUNTER, null,
+new AtomicLong());
+// create workQueues array with size a power of two
+int p = config & SMASK; // ensure at least 2 slots
+int n = (p > 1) ? p - 1 : 1;
+n |= n >>> 1; n |= n >>> 2;  n |= n >>> 4;
+n |= n >>> 8; n |= n >>> 16; n = (n + 1) << 1;
+workQueues = new WorkQueue[n];
+ns = STARTED;
+}
+} finally {
+unlockRunState(rs, (rs & ~RSLOCK) | ns);
+}
+}
+else if ((q = ws[k = r & m & SQMASK]) != null) {
+if (q.qlock == 0 && U.compareAndSwapInt(q, QLOCK, 0, 1)) {
+ForkJoinTask<?>[] a = q.array;
+int s = q.top;
+boolean submitted = false; // initial submission or resizing
+try {                      // locked version of push
+if ((a != null && a.length > s + 1 - q.base) ||
+(a = q.growArray()) != null) {
+int j = (((a.length - 1) & s) << ASHIFT) + ABASE;
+U.putOrderedObject(a, j, task);
+U.putOrderedInt(q, QTOP, s + 1);
+submitted = true;
 }
-// Wake up workers parked on event queue
+} finally {
-int i, e; long cc; Thread p;
+U.compareAndSwapInt(q, QLOCK, 1, 0);
-while ((e = (int)(cc = ctl) & E_MASK) != 0 &&
+}
-(i = e & SMASK) < n && i >= 0 &&
+if (submitted) {
-(w = ws[i]) != null) {
+signalWork(ws, q);
-long nc = ((long)(w.nextWait & E_MASK) |
+return;
-((cc + AC_UNIT) & AC_MASK) |
-(cc & (TC_MASK|STOP_BIT)));
-if (w.eventCount == (e | INT_SIGN) &&
-U.compareAndSwapLong(this, CTL, cc, nc)) {
-w.eventCount = (e + E_SEQ) & E_MASK;
-w.qlock = -1;
-if ((p = w.parker) != null)
-U.unpark(p);
-}
-}
 }
 }
-}
+move = true;                   // move on failure
 }
-}
+else if (((rs = runState) & RSLOCK) == 0) { // create new queue
+q = new WorkQueue(this, null);
-// external operations on common pool
+q.hint = r;
+q.config = k | SHARED_QUEUE;
-/**
+q.scanState = INACTIVE;
-* Returns common pool queue for a thread that has submitted at
+rs = lockRunState();           // publish index
-* least one task.
+if (rs > 0 &&  (ws = workQueues) != null &&
+k < ws.length && ws[k] == null)
+ws[k] = q;                 // else terminated
+unlockRunState(rs, rs & ~RSLOCK);
+}
+else
+move = true;                   // move if busy
+if (move)
+r = ThreadLocalRandom.advanceProbe(r);
+}
+}
+/**
+* Tries to add the given task to a submission queue at
+* submitter's current queue. Only the (vastly) most common path
+* is directly handled in this method, while screening for need
+* for externalSubmit.
+*
+* @param task the task. Caller must ensure non-null.
+*/
+final void externalPush(ForkJoinTask<?> task) {
+WorkQueue[] ws; WorkQueue q; int m;
+int r = ThreadLocalRandom.getProbe();
+int rs = runState;
+if ((ws = workQueues) != null && (m = (ws.length - 1)) >= 0 &&
+(q = ws[m & r & SQMASK]) != null && r != 0 && rs > 0 &&
+U.compareAndSwapInt(q, QLOCK, 0, 1)) {
+ForkJoinTask<?>[] a; int am, n, s;
+if ((a = q.array) != null &&
+(am = a.length - 1) > (n = (s = q.top) - q.base)) {
+int j = ((am & s) << ASHIFT) + ABASE;
+U.putOrderedObject(a, j, task);
+U.putOrderedInt(q, QTOP, s + 1);
+U.putOrderedInt(q, QLOCK, 0);
+if (n <= 1)
+signalWork(ws, q);
+return;
+}
+U.compareAndSwapInt(q, QLOCK, 1, 0);
+}
+externalSubmit(task);
+}
+/**
+* Returns common pool queue for an external thread.
 */
 static WorkQueue commonSubmitterQueue() {
-ForkJoinPool p; WorkQueue[] ws; int m, z;
+ForkJoinPool p = common;
-return ((z = ThreadLocalRandom.getProbe()) != 0 &&
+int r = ThreadLocalRandom.getProbe();
-(p = common) != null &&
+WorkQueue[] ws; int m;
-(ws = p.workQueues) != null &&
+return (p != null && (ws = p.workQueues) != null &&
 (m = ws.length - 1) >= 0) ?
-ws[m & z & SQMASK] : null;
+ws[m & r & SQMASK] : null;
 }
 /**
-* Tries to pop the given task from submitter's queue in common pool.
+* Performs tryUnpush for an external submitter: Finds queue,
+* locks if apparently non-empty, validates upon locking, and
+* adjusts top. Each check can fail but rarely does.
 */
 final boolean tryExternalUnpush(ForkJoinTask<?> task) {
-WorkQueue joiner; ForkJoinTask<?>[] a; int m, s;
+WorkQueue[] ws; WorkQueue w; ForkJoinTask<?>[] a; int m, s;
-WorkQueue[] ws = workQueues;
+int r = ThreadLocalRandom.getProbe();
-int z = ThreadLocalRandom.getProbe();
+if ((ws = workQueues) != null && (m = ws.length - 1) >= 0 &&
-boolean popped = false;
+(w = ws[m & r & SQMASK]) != null &&
-if (ws != null && (m = ws.length - 1) >= 0 &&
+(a = w.array) != null && (s = w.top) != w.base) {
-(joiner = ws[z & m & SQMASK]) != null &&
-joiner.base != (s = joiner.top) &&
-(a = joiner.array) != null) {
 long j = (((a.length - 1) & (s - 1)) << ASHIFT) + ABASE;
-if (U.getObject(a, j) == task &&
+if (U.compareAndSwapInt(w, QLOCK, 0, 1)) {
-U.compareAndSwapInt(joiner, QLOCK, 0, 1)) {
+if (w.top == s && w.array == a &&
-if (joiner.top == s && joiner.array == a &&
+U.getObject(a, j) == task &&
 U.compareAndSwapObject(a, j, task, null)) {
-joiner.top = s - 1;
+U.putOrderedInt(w, QTOP, s - 1);
-popped = true;
+U.putOrderedInt(w, QLOCK, 0);
+return true;
 }
-joiner.qlock = 0;
+U.compareAndSwapInt(w, QLOCK, 1, 0);
 }
 }
-return popped;
+return false;
 }
+/**
+* Performs helpComplete for an external submitter.
+*/
 final int externalHelpComplete(CountedCompleter<?> task, int maxTasks) {
-WorkQueue joiner; int m;
+WorkQueue[] ws; int n;
-WorkQueue[] ws = workQueues;
+int r = ThreadLocalRandom.getProbe();
-int j = ThreadLocalRandom.getProbe();
+return ((ws = workQueues) == null || (n = ws.length) == 0) ? 0 :
-int s = 0;
+helpComplete(ws[(n - 1) & r & SQMASK], task, maxTasks);
-if (ws != null && (m = ws.length - 1) >= 0 &&
-(joiner = ws[j & m & SQMASK]) != null && task != null) {
-int scans = m + m + 1;
-long c = 0L;             // for stability check
-j |= 1;                  // poll odd queues
-for (int k = scans; ; j += 2) {
-WorkQueue q;
-if ((s = task.status) < 0)
-break;
-else if (joiner.externalPopAndExecCC(task)) {
-if (--maxTasks <= 0) {
-s = task.status;
-break;
-}
-k = scans;
-}
-else if ((s = task.status) < 0)
-break;
-else if ((q = ws[j & m]) != null && q.pollAndExecCC(task)) {
-if (--maxTasks <= 0) {
-s = task.status;
-break;
-}
-k = scans;
-}
-else if (--k < 0) {
-if (c == (c = ctl))
-break;
-k = scans;
-}
-}
-}
-return s;
 }
 // Exported methods
 // Constructors
 UncaughtExceptionHandler handler,
 boolean asyncMode) {
 this(checkParallelism(parallelism),
 checkFactory(factory),
 handler,
-(asyncMode ? FIFO_QUEUE : LIFO_QUEUE),
+asyncMode ? FIFO_QUEUE : LIFO_QUEUE,
 "ForkJoinPool-" + nextPoolId() + "-worker-");
 checkPermission();
 }
 private static int checkParallelism(int parallelism) {
 int mode,
 String workerNamePrefix) {
 this.workerNamePrefix = workerNamePrefix;
 this.factory = factory;
 this.ueh = handler;
-this.mode = (short)mode;
+this.config = (parallelism & SMASK) | mode;
-this.parallelism = (short)parallelism;
 long np = (long)(-parallelism); // offset ctl counts
 this.ctl = ((np << AC_SHIFT) & AC_MASK) | ((np << TC_SHIFT) & TC_MASK);
 }
 /**
 */
 public <T> List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks) {
 // In previous versions of this class, this method constructed
 // a task to run ForkJoinTask.invokeAll, but now external
 // invocation of multiple tasks is at least as efficient.
-ArrayList<Future<T>> futures = new ArrayList<Future<T>>(tasks.size());
+ArrayList<Future<T>> futures = new ArrayList<>(tasks.size());
 boolean done = false;
 try {
 for (Callable<T> t : tasks) {
 ForkJoinTask<T> f = new ForkJoinTask.AdaptedCallable<T>(t);
 *
 * @return the targeted parallelism level of this pool
 */
 public int getParallelism() {
 int par;
-return ((par = parallelism) > 0) ? par : 1;
+return ((par = config & SMASK) > 0) ? par : 1;
 }
 /**
 * Returns the targeted parallelism level of the common pool.
 *
 * maintain parallelism when others are cooperatively blocked.
 *
 * @return the number of worker threads
 */
 public int getPoolSize() {
-return parallelism + (short)(ctl >>> TC_SHIFT);
+return (config & SMASK) + (short)(ctl >>> TC_SHIFT);
 }
 /**
 * Returns {@code true} if this pool uses local first-in-first-out
 * scheduling mode for forked tasks that are never joined.
 *
 * @return {@code true} if this pool uses async mode
 */
 public boolean getAsyncMode() {
-return mode == FIFO_QUEUE;
+return (config & FIFO_QUEUE) != 0;
 }
 /**
 * Returns an estimate of the number of worker threads that are
 * not blocked waiting to join tasks or for other managed
 * number of active threads.
 *
 * @return the number of active threads
 */
 public int getActiveThreadCount() {
-int r = parallelism + (int)(ctl >> AC_SHIFT);
+int r = (config & SMASK) + (int)(ctl >> AC_SHIFT);
 return (r <= 0) ? 0 : r; // suppress momentarily negative values
 }
 /**
 * Returns {@code true} if all worker threads are currently idle.
 * threads remain inactive.
 *
 * @return {@code true} if all threads are currently idle
 */
 public boolean isQuiescent() {
-return parallelism + (int)(ctl >> AC_SHIFT) <= 0;
+return (config & SMASK) + (int)(ctl >> AC_SHIFT) <= 0;
 }
 /**
 * Returns an estimate of the total number of tasks stolen from
 * one thread's work queue by another. The reported value
 * overhead and contention across threads.
 *
 * @return the number of steals
 */
 public long getStealCount() {
-long count = stealCount;
+AtomicLong sc = stealCounter;
+long count = (sc == null) ? 0L : sc.get();
 WorkQueue[] ws; WorkQueue w;
 if ((ws = workQueues) != null) {
 for (int i = 1; i < ws.length; i += 2) {
 if ((w = ws[i]) != null)
 count += w.nsteals;
 * @return a string identifying this pool, as well as its state
 */
 public String toString() {
 // Use a single pass through workQueues to collect counts
 long qt = 0L, qs = 0L; int rc = 0;
-long st = stealCount;
+AtomicLong sc = stealCounter;
+long st = (sc == null) ? 0L : sc.get();
 long c = ctl;
 WorkQueue[] ws; WorkQueue w;
 if ((ws = workQueues) != null) {
 for (int i = 0; i < ws.length; ++i) {
 if ((w = ws[i]) != null) {
 ++rc;
 }
 }
 }
 }
-int pc = parallelism;
+int pc = (config & SMASK);
 int tc = pc + (short)(c >>> TC_SHIFT);
 int ac = pc + (int)(c >> AC_SHIFT);
 if (ac < 0) // ignore transient negative
 ac = 0;
-String level;
+int rs = runState;
-if ((c & STOP_BIT) != 0)
+String level = ((rs & TERMINATED) != 0 ? "Terminated" :
-level = (tc == 0) ? "Terminated" : "Terminating";
+(rs & STOP)       != 0 ? "Terminating" :
-else
+(rs & SHUTDOWN)   != 0 ? "Shutting down" :
-level = plock < 0 ? "Shutting down" : "Running";
+"Running");
 return super.toString() +
 "[" + level +
 ", parallelism = " + pc +
 ", size = " + tc +
 ", active = " + ac +
 * Returns {@code true} if all tasks have completed following shut down.
 *
 * @return {@code true} if all tasks have completed following shut down
 */
 public boolean isTerminated() {
-long c = ctl;
+return (runState & TERMINATED) != 0;
-return ((c & STOP_BIT) != 0L &&
-(short)(c >>> TC_SHIFT) + parallelism <= 0);
 }
 /**
 * Returns {@code true} if the process of termination has
 * commenced but not yet completed.  This method may be useful for
 * they do, they must abort them on interrupt.)
 *
 * @return {@code true} if terminating but not yet terminated
 */
 public boolean isTerminating() {
-long c = ctl;
+int rs = runState;
-return ((c & STOP_BIT) != 0L &&
+return (rs & STOP) != 0 && (rs & TERMINATED) == 0;
-(short)(c >>> TC_SHIFT) + parallelism > 0);
 }
 /**
 * Returns {@code true} if this pool has been shut down.
 *
 * @return {@code true} if this pool has been shut down
 */
 public boolean isShutdown() {
-return plock < 0;
+return (runState & SHUTDOWN) != 0;
 }
 /**
 * Blocks until all tasks have completed execution after a
 * shutdown request, or the timeout occurs, or the current thread
 return false;
 Thread.yield(); // cannot block
 }
 found = false;
 for (int j = (m + 1) << 2; j >= 0; --j) {
-ForkJoinTask<?> t; WorkQueue q; int b;
+ForkJoinTask<?> t; WorkQueue q; int b, k;
-if ((q = ws[r++ & m]) != null && (b = q.base) - q.top < 0) {
+if ((k = r++ & m) <= m && k >= 0 && (q = ws[k]) != null &&
+(b = q.base) - q.top < 0) {
 found = true;
 if ((t = q.pollAt(b)) != null)
 t.doExec();
 break;
 }
 /**
 * Interface for extending managed parallelism for tasks running
 * in {@link ForkJoinPool}s.
 *
 * <p>A {@code ManagedBlocker} provides two methods.  Method
-* {@code isReleasable} must return {@code true} if blocking is
+* {@link #isReleasable} must return {@code true} if blocking is
-* not necessary. Method {@code block} blocks the current thread
+* not necessary. Method {@link #block} blocks the current thread
 * if necessary (perhaps internally invoking {@code isReleasable}
 * before actually blocking). These actions are performed by any
 * thread invoking {@link ForkJoinPool#managedBlock(ManagedBlocker)}.
 * The unusual methods in this API accommodate synchronizers that
 * may, but don't usually, block for long periods. Similarly, they
 */
 boolean isReleasable();
 }
 /**
-* Blocks in accord with the given blocker.  If the current thread
+* Runs the given possibly blocking task.  When {@linkplain
-* is a {@link ForkJoinWorkerThread}, this method possibly
+* ForkJoinTask#inForkJoinPool() running in a ForkJoinPool}, this
-* arranges for a spare thread to be activated if necessary to
+* method possibly arranges for a spare thread to be activated if
-* ensure sufficient parallelism while the current thread is blocked.
+* necessary to ensure sufficient parallelism while the current
-*
+* thread is blocked in {@link ManagedBlocker#block blocker.block()}.
-* <p>If the caller is not a {@link ForkJoinTask}, this method is
+*
+* <p>This method repeatedly calls {@code blocker.isReleasable()} and
+* {@code blocker.block()} until either method returns {@code true}.
+* Every call to {@code blocker.block()} is preceded by a call to
+* {@code blocker.isReleasable()} that returned {@code false}.
+*
+* <p>If not running in a ForkJoinPool, this method is
 * behaviorally equivalent to
 *  <pre> {@code
 * while (!blocker.isReleasable())
 *   if (blocker.block())
-*     return;
+*     break;}</pre>
-* }</pre>
+*
-*
+* If running in a ForkJoinPool, the pool may first be expanded to
-* If the caller is a {@code ForkJoinTask}, then the pool may
+* ensure sufficient parallelism available during the call to
-* first be expanded to ensure parallelism, and later adjusted.
+* {@code blocker.block()}.
 *
-* @param blocker the blocker
+* @param blocker the blocker task
-* @throws InterruptedException if blocker.block did so
+* @throws InterruptedException if {@code blocker.block()} did so
 */
 public static void managedBlock(ManagedBlocker blocker)
 throws InterruptedException {
+ForkJoinPool p;
+ForkJoinWorkerThread wt;
 Thread t = Thread.currentThread();
-if (t instanceof ForkJoinWorkerThread) {
+if ((t instanceof ForkJoinWorkerThread) &&
-ForkJoinPool p = ((ForkJoinWorkerThread)t).pool;
+(p = (wt = (ForkJoinWorkerThread)t).pool) != null) {
+WorkQueue w = wt.workQueue;
 while (!blocker.isReleasable()) {
-if (p.tryCompensate(p.ctl)) {
+if (p.tryCompensate(w)) {
 try {
 do {} while (!blocker.isReleasable() &&
 !blocker.block());
 } finally {
-p.incrementActiveCount();
+U.getAndAddLong(p, CTL, AC_UNIT);
 }
 break;
 }
 }
 }
 return new ForkJoinTask.AdaptedCallable<T>(callable);
 }
 // Unsafe mechanics
 private static final sun.misc.Unsafe U;
+private static final int  ABASE;
+private static final int  ASHIFT;
 private static final long CTL;
+private static final long RUNSTATE;
+private static final long STEALCOUNTER;
 private static final long PARKBLOCKER;
-private static final int ABASE;
+private static final long QTOP;
-private static final int ASHIFT;
-private static final long STEALCOUNT;
-private static final long PLOCK;
-private static final long INDEXSEED;
-private static final long QBASE;
 private static final long QLOCK;
+private static final long QSCANSTATE;
+private static final long QPARKER;
+private static final long QCURRENTSTEAL;
+private static final long QCURRENTJOIN;
 static {
 // initialize field offsets for CAS etc
 try {
 U = sun.misc.Unsafe.getUnsafe();
 Class<?> k = ForkJoinPool.class;
 CTL = U.objectFieldOffset
 (k.getDeclaredField("ctl"));
-STEALCOUNT = U.objectFieldOffset
+RUNSTATE = U.objectFieldOffset
-(k.getDeclaredField("stealCount"));
+(k.getDeclaredField("runState"));
-PLOCK = U.objectFieldOffset
+STEALCOUNTER = U.objectFieldOffset
-(k.getDeclaredField("plock"));
+(k.getDeclaredField("stealCounter"));
-INDEXSEED = U.objectFieldOffset
-(k.getDeclaredField("indexSeed"));
 Class<?> tk = Thread.class;
 PARKBLOCKER = U.objectFieldOffset
 (tk.getDeclaredField("parkBlocker"));
 Class<?> wk = WorkQueue.class;
-QBASE = U.objectFieldOffset
+QTOP = U.objectFieldOffset
-(wk.getDeclaredField("base"));
+(wk.getDeclaredField("top"));
 QLOCK = U.objectFieldOffset
 (wk.getDeclaredField("qlock"));
+QSCANSTATE = U.objectFieldOffset
+(wk.getDeclaredField("scanState"));
+QPARKER = U.objectFieldOffset
+(wk.getDeclaredField("parker"));
+QCURRENTSTEAL = U.objectFieldOffset
+(wk.getDeclaredField("currentSteal"));
+QCURRENTJOIN = U.objectFieldOffset
+(wk.getDeclaredField("currentJoin"));
 Class<?> ak = ForkJoinTask[].class;
 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);
 }
+commonMaxSpares = DEFAULT_COMMON_MAX_SPARES;
 defaultForkJoinWorkerThreadFactory =
 new DefaultForkJoinWorkerThreadFactory();
 modifyThreadPermission = new RuntimePermission("modifyThread");
 common = java.security.AccessController.doPrivileged
 (new java.security.PrivilegedAction<ForkJoinPool>() {
 public ForkJoinPool run() { return makeCommonPool(); }});
-int par = common.parallelism; // report 1 even if threads disabled
+int par = common.config & SMASK; // report 1 even if threads disabled
 commonParallelism = par > 0 ? par : 1;
 }
 /**
 * Creates and returns the common pool, respecting user settings
 ("java.util.concurrent.ForkJoinPool.common.parallelism");
 String fp = System.getProperty
 ("java.util.concurrent.ForkJoinPool.common.threadFactory");
 String hp = System.getProperty
 ("java.util.concurrent.ForkJoinPool.common.exceptionHandler");
+String mp = System.getProperty
+("java.util.concurrent.ForkJoinPool.common.maximumSpares");
 if (pp != null)
 parallelism = Integer.parseInt(pp);
 if (fp != null)
 factory = ((ForkJoinWorkerThreadFactory)ClassLoader.
 getSystemClassLoader().loadClass(fp).newInstance());
 if (hp != null)
 handler = ((UncaughtExceptionHandler)ClassLoader.
 getSystemClassLoader().loadClass(hp).newInstance());
+if (mp != null)
+commonMaxSpares = Integer.parseInt(mp);
 } catch (Exception ignore) {
 }
 if (factory == null) {
 if (System.getSecurityManager() == null)
 factory = defaultForkJoinWorkerThreadFactory;

changeset 26448	5853628b0e63
parent 25859	3317bb8137f4
child 30036	3d4eb4503c18