Home | History | Annotate | Download | only in concurrent
      1 /*
      2  * Written by Doug Lea with assistance from members of JCP JSR-166
      3  * Expert Group and released to the public domain, as explained at
      4  * http://creativecommons.org/publicdomain/zero/1.0/
      5  */
      6 
      7 package java.util.concurrent;
      8 
      9 import java.util.ArrayList;
     10 import java.util.Arrays;
     11 import java.util.Collection;
     12 import java.util.Collections;
     13 import java.util.List;
     14 import java.util.concurrent.AbstractExecutorService;
     15 import java.util.concurrent.Callable;
     16 import java.util.concurrent.ExecutorService;
     17 import java.util.concurrent.Future;
     18 import java.util.concurrent.RejectedExecutionException;
     19 import java.util.concurrent.RunnableFuture;
     20 import java.util.concurrent.TimeUnit;
     21 
     22 /**
     23  * An {@link ExecutorService} for running {@link ForkJoinTask}s.
     24  * A {@code ForkJoinPool} provides the entry point for submissions
     25  * from non-{@code ForkJoinTask} clients, as well as management and
     26  * monitoring operations.
     27  *
     28  * <p>A {@code ForkJoinPool} differs from other kinds of {@link
     29  * ExecutorService} mainly by virtue of employing
     30  * <em>work-stealing</em>: all threads in the pool attempt to find and
     31  * execute tasks submitted to the pool and/or created by other active
     32  * tasks (eventually blocking waiting for work if none exist). This
     33  * enables efficient processing when most tasks spawn other subtasks
     34  * (as do most {@code ForkJoinTask}s), as well as when many small
     35  * tasks are submitted to the pool from external clients.  Especially
     36  * when setting <em>asyncMode</em> to true in constructors, {@code
     37  * ForkJoinPool}s may also be appropriate for use with event-style
     38  * tasks that are never joined.
     39  *
     40  * <p>A static {@link #commonPool()} is available and appropriate for
     41  * most applications. The common pool is used by any ForkJoinTask that
     42  * is not explicitly submitted to a specified pool. Using the common
     43  * pool normally reduces resource usage (its threads are slowly
     44  * reclaimed during periods of non-use, and reinstated upon subsequent
     45  * use).
     46  *
     47  * <p>For applications that require separate or custom pools, a {@code
     48  * ForkJoinPool} may be constructed with a given target parallelism
     49  * level; by default, equal to the number of available processors. The
     50  * pool attempts to maintain enough active (or available) threads by
     51  * dynamically adding, suspending, or resuming internal worker
     52  * threads, even if some tasks are stalled waiting to join
     53  * others. However, no such adjustments are guaranteed in the face of
     54  * blocked I/O or other unmanaged synchronization. The nested {@link
     55  * ManagedBlocker} interface enables extension of the kinds of
     56  * synchronization accommodated.
     57  *
     58  * <p>In addition to execution and lifecycle control methods, this
     59  * class provides status check methods (for example
     60  * {@link #getStealCount}) that are intended to aid in developing,
     61  * tuning, and monitoring fork/join applications. Also, method
     62  * {@link #toString} returns indications of pool state in a
     63  * convenient form for informal monitoring.
     64  *
     65  * <p>As is the case with other ExecutorServices, there are three
     66  * main task execution methods summarized in the following table.
     67  * These are designed to be used primarily by clients not already
     68  * engaged in fork/join computations in the current pool.  The main
     69  * forms of these methods accept instances of {@code ForkJoinTask},
     70  * but overloaded forms also allow mixed execution of plain {@code
     71  * Runnable}- or {@code Callable}- based activities as well.  However,
     72  * tasks that are already executing in a pool should normally instead
     73  * use the within-computation forms listed in the table unless using
     74  * async event-style tasks that are not usually joined, in which case
     75  * there is little difference among choice of methods.
     76  *
     77  * <table BORDER CELLPADDING=3 CELLSPACING=1>
     78  *  <tr>
     79  *    <td></td>
     80  *    <td ALIGN=CENTER> <b>Call from non-fork/join clients</b></td>
     81  *    <td ALIGN=CENTER> <b>Call from within fork/join computations</b></td>
     82  *  </tr>
     83  *  <tr>
     84  *    <td> <b>Arrange async execution</td>
     85  *    <td> {@link #execute(ForkJoinTask)}</td>
     86  *    <td> {@link ForkJoinTask#fork}</td>
     87  *  </tr>
     88  *  <tr>
     89  *    <td> <b>Await and obtain result</td>
     90  *    <td> {@link #invoke(ForkJoinTask)}</td>
     91  *    <td> {@link ForkJoinTask#invoke}</td>
     92  *  </tr>
     93  *  <tr>
     94  *    <td> <b>Arrange exec and obtain Future</td>
     95  *    <td> {@link #submit(ForkJoinTask)}</td>
     96  *    <td> {@link ForkJoinTask#fork} (ForkJoinTasks <em>are</em> Futures)</td>
     97  *  </tr>
     98  * </table>
     99  *
    100  * <p>The common pool is by default constructed with default
    101  * parameters, but these may be controlled by setting three {@link
    102  * System#getProperty system properties} with prefix {@code
    103  * java.util.concurrent.ForkJoinPool.common}: {@code parallelism} --
    104  * an integer greater than zero, {@code threadFactory} -- the class
    105  * name of a {@link ForkJoinWorkerThreadFactory}, and {@code
    106  * exceptionHandler} -- the class name of a {@link
    107  * java.lang.Thread.UncaughtExceptionHandler
    108  * Thread.UncaughtExceptionHandler}. Upon any error in establishing
    109  * these settings, default parameters are used.
    110  *
    111  * <p><b>Implementation notes</b>: This implementation restricts the
    112  * maximum number of running threads to 32767. Attempts to create
    113  * pools with greater than the maximum number result in
    114  * {@code IllegalArgumentException}.
    115  *
    116  * <p>This implementation rejects submitted tasks (that is, by throwing
    117  * {@link RejectedExecutionException}) only when the pool is shut down
    118  * or internal resources have been exhausted.
    119  *
    120  * @since 1.7
    121  * @hide
    122  * @author Doug Lea
    123  */
    124 public class ForkJoinPool extends AbstractExecutorService {
    125 
    126     /*
    127      * Implementation Overview
    128      *
    129      * This class and its nested classes provide the main
    130      * functionality and control for a set of worker threads:
    131      * Submissions from non-FJ threads enter into submission queues.
    132      * Workers take these tasks and typically split them into subtasks
    133      * that may be stolen by other workers.  Preference rules give
    134      * first priority to processing tasks from their own queues (LIFO
    135      * or FIFO, depending on mode), then to randomized FIFO steals of
    136      * tasks in other queues.
    137      *
    138      * WorkQueues
    139      * ==========
    140      *
    141      * Most operations occur within work-stealing queues (in nested
    142      * class WorkQueue).  These are special forms of Deques that
    143      * support only three of the four possible end-operations -- push,
    144      * pop, and poll (aka steal), under the further constraints that
    145      * push and pop are called only from the owning thread (or, as
    146      * extended here, under a lock), while poll may be called from
    147      * other threads.  (If you are unfamiliar with them, you probably
    148      * want to read Herlihy and Shavit's book "The Art of
    149      * Multiprocessor programming", chapter 16 describing these in
    150      * more detail before proceeding.)  The main work-stealing queue
    151      * design is roughly similar to those in the papers "Dynamic
    152      * Circular Work-Stealing Deque" by Chase and Lev, SPAA 2005
    153      * (http://research.sun.com/scalable/pubs/index.html) and
    154      * "Idempotent work stealing" by Michael, Saraswat, and Vechev,
    155      * PPoPP 2009 (http://portal.acm.org/citation.cfm?id=1504186).
    156      * The main differences ultimately stem from GC requirements that
    157      * we null out taken slots as soon as we can, to maintain as small
    158      * a footprint as possible even in programs generating huge
    159      * numbers of tasks. To accomplish this, we shift the CAS
    160      * arbitrating pop vs poll (steal) from being on the indices
    161      * ("base" and "top") to the slots themselves.  So, both a
    162      * successful pop and poll mainly entail a CAS of a slot from
    163      * non-null to null.  Because we rely on CASes of references, we
    164      * do not need tag bits on base or top.  They are simple ints as
    165      * used in any circular array-based queue (see for example
    166      * ArrayDeque).  Updates to the indices must still be ordered in a
    167      * way that guarantees that top == base means the queue is empty,
    168      * but otherwise may err on the side of possibly making the queue
    169      * appear nonempty when a push, pop, or poll have not fully
    170      * committed. Note that this means that the poll operation,
    171      * considered individually, is not wait-free. One thief cannot
    172      * successfully continue until another in-progress one (or, if
    173      * previously empty, a push) completes.  However, in the
    174      * aggregate, we ensure at least probabilistic non-blockingness.
    175      * If an attempted steal fails, a thief always chooses a different
    176      * random victim target to try next. So, in order for one thief to
    177      * progress, it suffices for any in-progress poll or new push on
    178      * any empty queue to complete. (This is why we normally use
    179      * method pollAt and its variants that try once at the apparent
    180      * base index, else consider alternative actions, rather than
    181      * method poll.)
    182      *
    183      * This approach also enables support of a user mode in which local
    184      * task processing is in FIFO, not LIFO order, simply by using
    185      * poll rather than pop.  This can be useful in message-passing
    186      * frameworks in which tasks are never joined.  However neither
    187      * mode considers affinities, loads, cache localities, etc, so
    188      * rarely provide the best possible performance on a given
    189      * machine, but portably provide good throughput by averaging over
    190      * these factors.  (Further, even if we did try to use such
    191      * information, we do not usually have a basis for exploiting it.
    192      * For example, some sets of tasks profit from cache affinities,
    193      * but others are harmed by cache pollution effects.)
    194      *
    195      * WorkQueues are also used in a similar way for tasks submitted
    196      * to the pool. We cannot mix these tasks in the same queues used
    197      * for work-stealing (this would contaminate lifo/fifo
    198      * processing). Instead, we randomly associate submission queues
    199      * with submitting threads, using a form of hashing.  The
    200      * ThreadLocal Submitter class contains a value initially used as
    201      * a hash code for choosing existing queues, but may be randomly
    202      * repositioned upon contention with other submitters.  In
    203      * essence, submitters act like workers except that they are
    204      * restricted to executing local tasks that they submitted (or in
    205      * the case of CountedCompleters, others with the same root task).
    206      * However, because most shared/external queue operations are more
    207      * expensive than internal, and because, at steady state, external
    208      * submitters will compete for CPU with workers, ForkJoinTask.join
    209      * and related methods disable them from repeatedly helping to
    210      * process tasks if all workers are active.  Insertion of tasks in
    211      * shared mode requires a lock (mainly to protect in the case of
    212      * resizing) but we use only a simple spinlock (using bits in
    213      * field qlock), because submitters encountering a busy queue move
    214      * on to try or create other queues -- they block only when
    215      * creating and registering new queues.
    216      *
    217      * Management
    218      * ==========
    219      *
    220      * The main throughput advantages of work-stealing stem from
    221      * decentralized control -- workers mostly take tasks from
    222      * themselves or each other. We cannot negate this in the
    223      * implementation of other management responsibilities. The main
    224      * tactic for avoiding bottlenecks is packing nearly all
    225      * essentially atomic control state into two volatile variables
    226      * that are by far most often read (not written) as status and
    227      * consistency checks.
    228      *
    229      * Field "ctl" contains 64 bits holding all the information needed
    230      * to atomically decide to add, inactivate, enqueue (on an event
    231      * queue), dequeue, and/or re-activate workers.  To enable this
    232      * packing, we restrict maximum parallelism to (1<<15)-1 (which is
    233      * far in excess of normal operating range) to allow ids, counts,
    234      * and their negations (used for thresholding) to fit into 16bit
    235      * fields.
    236      *
    237      * Field "plock" is a form of sequence lock with a saturating
    238      * shutdown bit (similarly for per-queue "qlocks"), mainly
    239      * protecting updates to the workQueues array, as well as to
    240      * enable shutdown.  When used as a lock, it is normally only very
    241      * briefly held, so is nearly always available after at most a
    242      * brief spin, but we use a monitor-based backup strategy to
    243      * block when needed.
    244      *
    245      * Recording WorkQueues.  WorkQueues are recorded in the
    246      * "workQueues" array that is created upon first use and expanded
    247      * if necessary.  Updates to the array while recording new workers
    248      * and unrecording terminated ones are protected from each other
    249      * by a lock but the array is otherwise concurrently readable, and
    250      * accessed directly.  To simplify index-based operations, the
    251      * array size is always a power of two, and all readers must
    252      * tolerate null slots. Worker queues are at odd indices. Shared
    253      * (submission) queues are at even indices, up to a maximum of 64
    254      * slots, to limit growth even if array needs to expand to add
    255      * more workers. Grouping them together in this way simplifies and
    256      * speeds up task scanning.
    257      *
    258      * All worker thread creation is on-demand, triggered by task
    259      * submissions, replacement of terminated workers, and/or
    260      * compensation for blocked workers. However, all other support
    261      * code is set up to work with other policies.  To ensure that we
    262      * do not hold on to worker references that would prevent GC, ALL
    263      * accesses to workQueues are via indices into the workQueues
    264      * array (which is one source of some of the messy code
    265      * constructions here). In essence, the workQueues array serves as
    266      * a weak reference mechanism. Thus for example the wait queue
    267      * field of ctl stores indices, not references.  Access to the
    268      * workQueues in associated methods (for example signalWork) must
    269      * both index-check and null-check the IDs. All such accesses
    270      * ignore bad IDs by returning out early from what they are doing,
    271      * since this can only be associated with termination, in which
    272      * case it is OK to give up.  All uses of the workQueues array
    273      * also check that it is non-null (even if previously
    274      * non-null). This allows nulling during termination, which is
    275      * currently not necessary, but remains an option for
    276      * resource-revocation-based shutdown schemes. It also helps
    277      * reduce JIT issuance of uncommon-trap code, which tends to
    278      * unnecessarily complicate control flow in some methods.
    279      *
    280      * Event Queuing. Unlike HPC work-stealing frameworks, we cannot
    281      * let workers spin indefinitely scanning for tasks when none can
    282      * be found immediately, and we cannot start/resume workers unless
    283      * there appear to be tasks available.  On the other hand, we must
    284      * quickly prod them into action when new tasks are submitted or
    285      * generated. In many usages, ramp-up time to activate workers is
    286      * the main limiting factor in overall performance (this is
    287      * compounded at program start-up by JIT compilation and
    288      * allocation). So we try to streamline this as much as possible.
    289      * We park/unpark workers after placing in an event wait queue
    290      * when they cannot find work. This "queue" is actually a simple
    291      * Treiber stack, headed by the "id" field of ctl, plus a 15bit
    292      * counter value (that reflects the number of times a worker has
    293      * been inactivated) to avoid ABA effects (we need only as many
    294      * version numbers as worker threads). Successors are held in
    295      * field WorkQueue.nextWait.  Queuing deals with several intrinsic
    296      * races, mainly that a task-producing thread can miss seeing (and
    297      * signalling) another thread that gave up looking for work but
    298      * has not yet entered the wait queue. We solve this by requiring
    299      * a full sweep of all workers (via repeated calls to method
    300      * scan()) both before and after a newly waiting worker is added
    301      * to the wait queue. During a rescan, the worker might release
    302      * some other queued worker rather than itself, which has the same
    303      * net effect. Because enqueued workers may actually be rescanning
    304      * rather than waiting, we set and clear the "parker" field of
    305      * WorkQueues to reduce unnecessary calls to unpark.  (This
    306      * requires a secondary recheck to avoid missed signals.)  Note
    307      * the unusual conventions about Thread.interrupts surrounding
    308      * parking and other blocking: Because interrupts are used solely
    309      * to alert threads to check termination, which is checked anyway
    310      * upon blocking, we clear status (using Thread.interrupted)
    311      * before any call to park, so that park does not immediately
    312      * return due to status being set via some other unrelated call to
    313      * interrupt in user code.
    314      *
    315      * Signalling.  We create or wake up workers only when there
    316      * appears to be at least one task they might be able to find and
    317      * execute. However, many other threads may notice the same task
    318      * and each signal to wake up a thread that might take it. So in
    319      * general, pools will be over-signalled.  When a submission is
    320      * added or another worker adds a task to a queue that has fewer
    321      * than two tasks, they signal waiting workers (or trigger
    322      * creation of new ones if fewer than the given parallelism level
    323      * -- signalWork), and may leave a hint to the unparked worker to
    324      * help signal others upon wakeup).  These primary signals are
    325      * buttressed by others (see method helpSignal) whenever other
    326      * threads scan for work or do not have a task to process.  On
    327      * most platforms, signalling (unpark) overhead time is noticeably
    328      * long, and the time between signalling a thread and it actually
    329      * making progress can be very noticeably long, so it is worth
    330      * offloading these delays from critical paths as much as
    331      * possible.
    332      *
    333      * Trimming workers. To release resources after periods of lack of
    334      * use, a worker starting to wait when the pool is quiescent will
    335      * time out and terminate if the pool has remained quiescent for a
    336      * given period -- a short period if there are more threads than
    337      * parallelism, longer as the number of threads decreases. This
    338      * will slowly propagate, eventually terminating all workers after
    339      * periods of non-use.
    340      *
    341      * Shutdown and Termination. A call to shutdownNow atomically sets
    342      * a plock bit and then (non-atomically) sets each worker's
    343      * qlock status, cancels all unprocessed tasks, and wakes up
    344      * all waiting workers.  Detecting whether termination should
    345      * commence after a non-abrupt shutdown() call requires more work
    346      * and bookkeeping. We need consensus about quiescence (i.e., that
    347      * there is no more work). The active count provides a primary
    348      * indication but non-abrupt shutdown still requires a rechecking
    349      * scan for any workers that are inactive but not queued.
    350      *
    351      * Joining Tasks
    352      * =============
    353      *
    354      * Any of several actions may be taken when one worker is waiting
    355      * to join a task stolen (or always held) by another.  Because we
    356      * are multiplexing many tasks on to a pool of workers, we can't
    357      * just let them block (as in Thread.join).  We also cannot just
    358      * reassign the joiner's run-time stack with another and replace
    359      * it later, which would be a form of "continuation", that even if
    360      * possible is not necessarily a good idea since we sometimes need
    361      * both an unblocked task and its continuation to progress.
    362      * Instead we combine two tactics:
    363      *
    364      *   Helping: Arranging for the joiner to execute some task that it
    365      *      would be running if the steal had not occurred.
    366      *
    367      *   Compensating: Unless there are already enough live threads,
    368      *      method tryCompensate() may create or re-activate a spare
    369      *      thread to compensate for blocked joiners until they unblock.
    370      *
    371      * A third form (implemented in tryRemoveAndExec) amounts to
    372      * helping a hypothetical compensator: If we can readily tell that
    373      * a possible action of a compensator is to steal and execute the
    374      * task being joined, the joining thread can do so directly,
    375      * without the need for a compensation thread (although at the
    376      * expense of larger run-time stacks, but the tradeoff is
    377      * typically worthwhile).
    378      *
    379      * The ManagedBlocker extension API can't use helping so relies
    380      * only on compensation in method awaitBlocker.
    381      *
    382      * The algorithm in tryHelpStealer entails a form of "linear"
    383      * helping: Each worker records (in field currentSteal) the most
    384      * recent task it stole from some other worker. Plus, it records
    385      * (in field currentJoin) the task it is currently actively
    386      * joining. Method tryHelpStealer uses these markers to try to
    387      * find a worker to help (i.e., steal back a task from and execute
    388      * it) that could hasten completion of the actively joined task.
    389      * In essence, the joiner executes a task that would be on its own
    390      * local deque had the to-be-joined task not been stolen. This may
    391      * be seen as a conservative variant of the approach in Wagner &
    392      * Calder "Leapfrogging: a portable technique for implementing
    393      * efficient futures" SIGPLAN Notices, 1993
    394      * (http://portal.acm.org/citation.cfm?id=155354). It differs in
    395      * that: (1) We only maintain dependency links across workers upon
    396      * steals, rather than use per-task bookkeeping.  This sometimes
    397      * requires a linear scan of workQueues array to locate stealers,
    398      * but often doesn't because stealers leave hints (that may become
    399      * stale/wrong) of where to locate them.  It is only a hint
    400      * because a worker might have had multiple steals and the hint
    401      * records only one of them (usually the most current).  Hinting
    402      * isolates cost to when it is needed, rather than adding to
    403      * per-task overhead.  (2) It is "shallow", ignoring nesting and
    404      * potentially cyclic mutual steals.  (3) It is intentionally
    405      * racy: field currentJoin is updated only while actively joining,
    406      * which means that we miss links in the chain during long-lived
    407      * tasks, GC stalls etc (which is OK since blocking in such cases
    408      * is usually a good idea).  (4) We bound the number of attempts
    409      * to find work (see MAX_HELP) and fall back to suspending the
    410      * worker and if necessary replacing it with another.
    411      *
    412      * Helping actions for CountedCompleters are much simpler: Method
    413      * helpComplete can take and execute any task with the same root
    414      * as the task being waited on. However, this still entails some
    415      * traversal of completer chains, so is less efficient than using
    416      * CountedCompleters without explicit joins.
    417      *
    418      * It is impossible to keep exactly the target parallelism number
    419      * of threads running at any given time.  Determining the
    420      * existence of conservatively safe helping targets, the
    421      * availability of already-created spares, and the apparent need
    422      * to create new spares are all racy, so we rely on multiple
    423      * retries of each.  Compensation in the apparent absence of
    424      * helping opportunities is challenging to control on JVMs, where
    425      * GC and other activities can stall progress of tasks that in
    426      * turn stall out many other dependent tasks, without us being
    427      * able to determine whether they will ever require compensation.
    428      * Even though work-stealing otherwise encounters little
    429      * degradation in the presence of more threads than cores,
    430      * aggressively adding new threads in such cases entails risk of
    431      * unwanted positive feedback control loops in which more threads
    432      * cause more dependent stalls (as well as delayed progress of
    433      * unblocked threads to the point that we know they are available)
    434      * leading to more situations requiring more threads, and so
    435      * on. This aspect of control can be seen as an (analytically
    436      * intractable) game with an opponent that may choose the worst
    437      * (for us) active thread to stall at any time.  We take several
    438      * precautions to bound losses (and thus bound gains), mainly in
    439      * methods tryCompensate and awaitJoin.
    440      *
    441      * Common Pool
    442      * ===========
    443      *
    444      * The static commonPool always exists after static
    445      * initialization.  Since it (or any other created pool) need
    446      * never be used, we minimize initial construction overhead and
    447      * footprint to the setup of about a dozen fields, with no nested
    448      * allocation. Most bootstrapping occurs within method
    449      * fullExternalPush during the first submission to the pool.
    450      *
    451      * When external threads submit to the common pool, they can
    452      * perform some subtask processing (see externalHelpJoin and
    453      * related methods).  We do not need to record whether these
    454      * submissions are to the common pool -- if not, externalHelpJoin
    455      * returns quickly (at the most helping to signal some common pool
    456      * workers). These submitters would otherwise be blocked waiting
    457      * for completion, so the extra effort (with liberally sprinkled
    458      * task status checks) in inapplicable cases amounts to an odd
    459      * form of limited spin-wait before blocking in ForkJoinTask.join.
    460      *
    461      * Style notes
    462      * ===========
    463      *
    464      * There is a lot of representation-level coupling among classes
    465      * ForkJoinPool, ForkJoinWorkerThread, and ForkJoinTask.  The
    466      * fields of WorkQueue maintain data structures managed by
    467      * ForkJoinPool, so are directly accessed.  There is little point
    468      * trying to reduce this, since any associated future changes in
    469      * representations will need to be accompanied by algorithmic
    470      * changes anyway. Several methods intrinsically sprawl because
    471      * they must accumulate sets of consistent reads of volatiles held
    472      * in local variables.  Methods signalWork() and scan() are the
    473      * main bottlenecks, so are especially heavily
    474      * micro-optimized/mangled.  There are lots of inline assignments
    475      * (of form "while ((local = field) != 0)") which are usually the
    476      * simplest way to ensure the required read orderings (which are
    477      * sometimes critical). This leads to a "C"-like style of listing
    478      * declarations of these locals at the heads of methods or blocks.
    479      * There are several occurrences of the unusual "do {} while
    480      * (!cas...)"  which is the simplest way to force an update of a
    481      * CAS'ed variable. There are also other coding oddities (including
    482      * several unnecessary-looking hoisted null checks) that help
    483      * some methods perform reasonably even when interpreted (not
    484      * compiled).
    485      *
    486      * The order of declarations in this file is:
    487      * (1) Static utility functions
    488      * (2) Nested (static) classes
    489      * (3) Static fields
    490      * (4) Fields, along with constants used when unpacking some of them
    491      * (5) Internal control methods
    492      * (6) Callbacks and other support for ForkJoinTask methods
    493      * (7) Exported methods
    494      * (8) Static block initializing statics in minimally dependent order
    495      */
    496 
    497     // Static utilities
    498 
    499     /**
    500      * If there is a security manager, makes sure caller has
    501      * permission to modify threads.
    502      */
    503     private static void checkPermission() {
    504         SecurityManager security = System.getSecurityManager();
    505         if (security != null)
    506             security.checkPermission(modifyThreadPermission);
    507     }
    508 
    509     // Nested classes
    510 
    511     /**
    512      * Factory for creating new {@link ForkJoinWorkerThread}s.
    513      * A {@code ForkJoinWorkerThreadFactory} must be defined and used
    514      * for {@code ForkJoinWorkerThread} subclasses that extend base
    515      * functionality or initialize threads with different contexts.
    516      */
    517     public static interface ForkJoinWorkerThreadFactory {
    518         /**
    519          * Returns a new worker thread operating in the given pool.
    520          *
    521          * @param pool the pool this thread works in
    522          * @throws NullPointerException if the pool is null
    523          */
    524         public ForkJoinWorkerThread newThread(ForkJoinPool pool);
    525     }
    526 
    527     /**
    528      * Default ForkJoinWorkerThreadFactory implementation; creates a
    529      * new ForkJoinWorkerThread.
    530      */
    531     static final class DefaultForkJoinWorkerThreadFactory
    532         implements ForkJoinWorkerThreadFactory {
    533         public final ForkJoinWorkerThread newThread(ForkJoinPool pool) {
    534             return new ForkJoinWorkerThread(pool);
    535         }
    536     }
    537 
    538     /**
    539      * Per-thread records for threads that submit to pools. Currently
    540      * holds only pseudo-random seed / index that is used to choose
    541      * submission queues in method externalPush. In the future, this may
    542      * also incorporate a means to implement different task rejection
    543      * and resubmission policies.
    544      *
    545      * Seeds for submitters and workers/workQueues work in basically
    546      * the same way but are initialized and updated using slightly
    547      * different mechanics. Both are initialized using the same
    548      * approach as in class ThreadLocal, where successive values are
    549      * unlikely to collide with previous values. Seeds are then
    550      * randomly modified upon collisions using xorshifts, which
    551      * requires a non-zero seed.
    552      */
    553     static final class Submitter {
    554         int seed;
    555         Submitter(int s) { seed = s; }
    556     }
    557 
    558     /**
    559      * Class for artificial tasks that are used to replace the target
    560      * of local joins if they are removed from an interior queue slot
    561      * in WorkQueue.tryRemoveAndExec. We don't need the proxy to
    562      * actually do anything beyond having a unique identity.
    563      */
    564     static final class EmptyTask extends ForkJoinTask<Void> {
    565         private static final long serialVersionUID = -7721805057305804111L;
    566         EmptyTask() { status = ForkJoinTask.NORMAL; } // force done
    567         public final Void getRawResult() { return null; }
    568         public final void setRawResult(Void x) {}
    569         public final boolean exec() { return true; }
    570     }
    571 
    572     /**
    573      * Queues supporting work-stealing as well as external task
    574      * submission. See above for main rationale and algorithms.
    575      * Implementation relies heavily on "Unsafe" intrinsics
    576      * and selective use of "volatile":
    577      *
    578      * Field "base" is the index (mod array.length) of the least valid
    579      * queue slot, which is always the next position to steal (poll)
    580      * from if nonempty. Reads and writes require volatile orderings
    581      * but not CAS, because updates are only performed after slot
    582      * CASes.
    583      *
    584      * Field "top" is the index (mod array.length) of the next queue
    585      * slot to push to or pop from. It is written only by owner thread
    586      * for push, or under lock for external/shared push, and accessed
    587      * by other threads only after reading (volatile) base.  Both top
    588      * and base are allowed to wrap around on overflow, but (top -
    589      * base) (or more commonly -(base - top) to force volatile read of
    590      * base before top) still estimates size. The lock ("qlock") is
    591      * forced to -1 on termination, causing all further lock attempts
    592      * to fail. (Note: we don't need CAS for termination state because
    593      * upon pool shutdown, all shared-queues will stop being used
    594      * anyway.)  Nearly all lock bodies are set up so that exceptions
    595      * within lock bodies are "impossible" (modulo JVM errors that
    596      * would cause failure anyway.)
    597      *
    598      * The array slots are read and written using the emulation of
    599      * volatiles/atomics provided by Unsafe. Insertions must in
    600      * general use putOrderedObject as a form of releasing store to
    601      * ensure that all writes to the task object are ordered before
    602      * its publication in the queue.  All removals entail a CAS to
    603      * null.  The array is always a power of two. To ensure safety of
    604      * Unsafe array operations, all accesses perform explicit null
    605      * checks and implicit bounds checks via power-of-two masking.
    606      *
    607      * In addition to basic queuing support, this class contains
    608      * fields described elsewhere to control execution. It turns out
    609      * to work better memory-layout-wise to include them in this class
    610      * rather than a separate class.
    611      *
    612      * Performance on most platforms is very sensitive to placement of
    613      * instances of both WorkQueues and their arrays -- we absolutely
    614      * do not want multiple WorkQueue instances or multiple queue
    615      * arrays sharing cache lines. (It would be best for queue objects
    616      * and their arrays to share, but there is nothing available to
    617      * help arrange that).  Unfortunately, because they are recorded
    618      * in a common array, WorkQueue instances are often moved to be
    619      * adjacent by garbage collectors. To reduce impact, we use field
    620      * padding that works OK on common platforms; this effectively
    621      * trades off slightly slower average field access for the sake of
    622      * avoiding really bad worst-case access. (Until better JVM
    623      * support is in place, this padding is dependent on transient
    624      * properties of JVM field layout rules.) We also take care in
    625      * allocating, sizing and resizing the array. Non-shared queue
    626      * arrays are initialized by workers before use. Others are
    627      * allocated on first use.
    628      */
    629     static final class WorkQueue {
    630         /**
    631          * Capacity of work-stealing queue array upon initialization.
    632          * Must be a power of two; at least 4, but should be larger to
    633          * reduce or eliminate cacheline sharing among queues.
    634          * Currently, it is much larger, as a partial workaround for
    635          * the fact that JVMs often place arrays in locations that
    636          * share GC bookkeeping (especially cardmarks) such that
    637          * per-write accesses encounter serious memory contention.
    638          */
    639         static final int INITIAL_QUEUE_CAPACITY = 1 << 13;
    640 
    641         /**
    642          * Maximum size for queue arrays. Must be a power of two less
    643          * than or equal to 1 << (31 - width of array entry) to ensure
    644          * lack of wraparound of index calculations, but defined to a
    645          * value a bit less than this to help users trap runaway
    646          * programs before saturating systems.
    647          */
    648         static final int MAXIMUM_QUEUE_CAPACITY = 1 << 26; // 64M
    649 
    650         // Heuristic padding to ameliorate unfortunate memory placements
    651         volatile long pad00, pad01, pad02, pad03, pad04, pad05, pad06;
    652 
    653         int seed;                  // for random scanning; initialize nonzero
    654         volatile int eventCount;   // encoded inactivation count; < 0 if inactive
    655         int nextWait;              // encoded record of next event waiter
    656         int hint;                  // steal or signal hint (index)
    657         int poolIndex;             // index of this queue in pool (or 0)
    658         final int mode;            // 0: lifo, > 0: fifo, < 0: shared
    659         int nsteals;               // number of steals
    660         volatile int qlock;        // 1: locked, -1: terminate; else 0
    661         volatile int base;         // index of next slot for poll
    662         int top;                   // index of next slot for push
    663         ForkJoinTask<?>[] array;   // the elements (initially unallocated)
    664         final ForkJoinPool pool;   // the containing pool (may be null)
    665         final ForkJoinWorkerThread owner; // owning thread or null if shared
    666         volatile Thread parker;    // == owner during call to park; else null
    667         volatile ForkJoinTask<?> currentJoin;  // task being joined in awaitJoin
    668         ForkJoinTask<?> currentSteal; // current non-local task being executed
    669 
    670         volatile Object pad10, pad11, pad12, pad13, pad14, pad15, pad16, pad17;
    671         volatile Object pad18, pad19, pad1a, pad1b, pad1c, pad1d;
    672 
    673         WorkQueue(ForkJoinPool pool, ForkJoinWorkerThread owner, int mode,
    674                   int seed) {
    675             this.pool = pool;
    676             this.owner = owner;
    677             this.mode = mode;
    678             this.seed = seed;
    679             // Place indices in the center of array (that is not yet allocated)
    680             base = top = INITIAL_QUEUE_CAPACITY >>> 1;
    681         }
    682 
    683         /**
    684          * Returns the approximate number of tasks in the queue.
    685          */
    686         final int queueSize() {
    687             int n = base - top;       // non-owner callers must read base first
    688             return (n >= 0) ? 0 : -n; // ignore transient negative
    689         }
    690 
    691        /**
    692          * Provides a more accurate estimate of whether this queue has
    693          * any tasks than does queueSize, by checking whether a
    694          * near-empty queue has at least one unclaimed task.
    695          */
    696         final boolean isEmpty() {
    697             ForkJoinTask<?>[] a; int m, s;
    698             int n = base - (s = top);
    699             return (n >= 0 ||
    700                     (n == -1 &&
    701                      ((a = array) == null ||
    702                       (m = a.length - 1) < 0 ||
    703                       U.getObject
    704                       (a, (long)((m & (s - 1)) << ASHIFT) + ABASE) == null)));
    705         }
    706 
    707         /**
    708          * Pushes a task. Call only by owner in unshared queues.  (The
    709          * shared-queue version is embedded in method externalPush.)
    710          *
    711          * @param task the task. Caller must ensure non-null.
    712          * @throws RejectedExecutionException if array cannot be resized
    713          */
    714         final void push(ForkJoinTask<?> task) {
    715             ForkJoinTask<?>[] a; ForkJoinPool p;
    716             int s = top, m, n;
    717             if ((a = array) != null) {    // ignore if queue removed
    718                 int j = (((m = a.length - 1) & s) << ASHIFT) + ABASE;
    719                 U.putOrderedObject(a, j, task);
    720                 if ((n = (top = s + 1) - base) <= 2) {
    721                     if ((p = pool) != null)
    722                         p.signalWork(this);
    723                 }
    724                 else if (n >= m)
    725                     growArray();
    726             }
    727         }
    728 
    729        /**
    730          * Initializes or doubles the capacity of array. Call either
    731          * by owner or with lock held -- it is OK for base, but not
    732          * top, to move while resizings are in progress.
    733          */
    734         final ForkJoinTask<?>[] growArray() {
    735             ForkJoinTask<?>[] oldA = array;
    736             int size = oldA != null ? oldA.length << 1 : INITIAL_QUEUE_CAPACITY;
    737             if (size > MAXIMUM_QUEUE_CAPACITY)
    738                 throw new RejectedExecutionException("Queue capacity exceeded");
    739             int oldMask, t, b;
    740             ForkJoinTask<?>[] a = array = new ForkJoinTask<?>[size];
    741             if (oldA != null && (oldMask = oldA.length - 1) >= 0 &&
    742                 (t = top) - (b = base) > 0) {
    743                 int mask = size - 1;
    744                 do {
    745                     ForkJoinTask<?> x;
    746                     int oldj = ((b & oldMask) << ASHIFT) + ABASE;
    747                     int j    = ((b &    mask) << ASHIFT) + ABASE;
    748                     x = (ForkJoinTask<?>)U.getObjectVolatile(oldA, oldj);
    749                     if (x != null &&
    750                         U.compareAndSwapObject(oldA, oldj, x, null))
    751                         U.putObjectVolatile(a, j, x);
    752                 } while (++b != t);
    753             }
    754             return a;
    755         }
    756 
    757         /**
    758          * Takes next task, if one exists, in LIFO order.  Call only
    759          * by owner in unshared queues.
    760          */
    761         final ForkJoinTask<?> pop() {
    762             ForkJoinTask<?>[] a; ForkJoinTask<?> t; int m;
    763             if ((a = array) != null && (m = a.length - 1) >= 0) {
    764                 for (int s; (s = top - 1) - base >= 0;) {
    765                     long j = ((m & s) << ASHIFT) + ABASE;
    766                     if ((t = (ForkJoinTask<?>)U.getObject(a, j)) == null)
    767                         break;
    768                     if (U.compareAndSwapObject(a, j, t, null)) {
    769                         top = s;
    770                         return t;
    771                     }
    772                 }
    773             }
    774             return null;
    775         }
    776 
    777         /**
    778          * Takes a task in FIFO order if b is base of queue and a task
    779          * can be claimed without contention. Specialized versions
    780          * appear in ForkJoinPool methods scan and tryHelpStealer.
    781          */
    782         final ForkJoinTask<?> pollAt(int b) {
    783             ForkJoinTask<?> t; ForkJoinTask<?>[] a;
    784             if ((a = array) != null) {
    785                 int j = (((a.length - 1) & b) << ASHIFT) + ABASE;
    786                 if ((t = (ForkJoinTask<?>)U.getObjectVolatile(a, j)) != null &&
    787                     base == b &&
    788                     U.compareAndSwapObject(a, j, t, null)) {
    789                     base = b + 1;
    790                     return t;
    791                 }
    792             }
    793             return null;
    794         }
    795 
    796         /**
    797          * Takes next task, if one exists, in FIFO order.
    798          */
    799         final ForkJoinTask<?> poll() {
    800             ForkJoinTask<?>[] a; int b; ForkJoinTask<?> t;
    801             while ((b = base) - top < 0 && (a = array) != null) {
    802                 int j = (((a.length - 1) & b) << ASHIFT) + ABASE;
    803                 t = (ForkJoinTask<?>)U.getObjectVolatile(a, j);
    804                 if (t != null) {
    805                     if (base == b &&
    806                         U.compareAndSwapObject(a, j, t, null)) {
    807                         base = b + 1;
    808                         return t;
    809                     }
    810                 }
    811                 else if (base == b) {
    812                     if (b + 1 == top)
    813                         break;
    814                     Thread.yield(); // wait for lagging update (very rare)
    815                 }
    816             }
    817             return null;
    818         }
    819 
    820         /**
    821          * Takes next task, if one exists, in order specified by mode.
    822          */
    823         final ForkJoinTask<?> nextLocalTask() {
    824             return mode == 0 ? pop() : poll();
    825         }
    826 
    827         /**
    828          * Returns next task, if one exists, in order specified by mode.
    829          */
    830         final ForkJoinTask<?> peek() {
    831             ForkJoinTask<?>[] a = array; int m;
    832             if (a == null || (m = a.length - 1) < 0)
    833                 return null;
    834             int i = mode == 0 ? top - 1 : base;
    835             int j = ((i & m) << ASHIFT) + ABASE;
    836             return (ForkJoinTask<?>)U.getObjectVolatile(a, j);
    837         }
    838 
    839         /**
    840          * Pops the given task only if it is at the current top.
    841          * (A shared version is available only via FJP.tryExternalUnpush)
    842          */
    843         final boolean tryUnpush(ForkJoinTask<?> t) {
    844             ForkJoinTask<?>[] a; int s;
    845             if ((a = array) != null && (s = top) != base &&
    846                 U.compareAndSwapObject
    847                 (a, (((a.length - 1) & --s) << ASHIFT) + ABASE, t, null)) {
    848                 top = s;
    849                 return true;
    850             }
    851             return false;
    852         }
    853 
    854         /**
    855          * Removes and cancels all known tasks, ignoring any exceptions.
    856          */
    857         final void cancelAll() {
    858             ForkJoinTask.cancelIgnoringExceptions(currentJoin);
    859             ForkJoinTask.cancelIgnoringExceptions(currentSteal);
    860             for (ForkJoinTask<?> t; (t = poll()) != null; )
    861                 ForkJoinTask.cancelIgnoringExceptions(t);
    862         }
    863 
    864         /**
    865          * Computes next value for random probes.  Scans don't require
    866          * a very high quality generator, but also not a crummy one.
    867          * Marsaglia xor-shift is cheap and works well enough.  Note:
    868          * This is manually inlined in its usages in ForkJoinPool to
    869          * avoid writes inside busy scan loops.
    870          */
    871         final int nextSeed() {
    872             int r = seed;
    873             r ^= r << 13;
    874             r ^= r >>> 17;
    875             return seed = r ^= r << 5;
    876         }
    877 
    878         // Specialized execution methods
    879 
    880         /**
    881          * Pops and runs tasks until empty.
    882          */
    883         private void popAndExecAll() {
    884             // A bit faster than repeated pop calls
    885             ForkJoinTask<?>[] a; int m, s; long j; ForkJoinTask<?> t;
    886             while ((a = array) != null && (m = a.length - 1) >= 0 &&
    887                    (s = top - 1) - base >= 0 &&
    888                    (t = ((ForkJoinTask<?>)
    889                          U.getObject(a, j = ((m & s) << ASHIFT) + ABASE)))
    890                    != null) {
    891                 if (U.compareAndSwapObject(a, j, t, null)) {
    892                     top = s;
    893                     t.doExec();
    894                 }
    895             }
    896         }
    897 
    898         /**
    899          * Polls and runs tasks until empty.
    900          */
    901         private void pollAndExecAll() {
    902             for (ForkJoinTask<?> t; (t = poll()) != null;)
    903                 t.doExec();
    904         }
    905 
    906         /**
    907          * If present, removes from queue and executes the given task,
    908          * or any other cancelled task. Returns (true) on any CAS
    909          * or consistency check failure so caller can retry.
    910          *
    911          * @return false if no progress can be made, else true
    912          */
    913         final boolean tryRemoveAndExec(ForkJoinTask<?> task) {
    914             boolean stat = true, removed = false, empty = true;
    915             ForkJoinTask<?>[] a; int m, s, b, n;
    916             if ((a = array) != null && (m = a.length - 1) >= 0 &&
    917                 (n = (s = top) - (b = base)) > 0) {
    918                 for (ForkJoinTask<?> t;;) {           // traverse from s to b
    919                     int j = ((--s & m) << ASHIFT) + ABASE;
    920                     t = (ForkJoinTask<?>)U.getObjectVolatile(a, j);
    921                     if (t == null)                    // inconsistent length
    922                         break;
    923                     else if (t == task) {
    924                         if (s + 1 == top) {           // pop
    925                             if (!U.compareAndSwapObject(a, j, task, null))
    926                                 break;
    927                             top = s;
    928                             removed = true;
    929                         }
    930                         else if (base == b)           // replace with proxy
    931                             removed = U.compareAndSwapObject(a, j, task,
    932                                                              new EmptyTask());
    933                         break;
    934                     }
    935                     else if (t.status >= 0)
    936                         empty = false;
    937                     else if (s + 1 == top) {          // pop and throw away
    938                         if (U.compareAndSwapObject(a, j, t, null))
    939                             top = s;
    940                         break;
    941                     }
    942                     if (--n == 0) {
    943                         if (!empty && base == b)
    944                             stat = false;
    945                         break;
    946                     }
    947                 }
    948             }
    949             if (removed)
    950                 task.doExec();
    951             return stat;
    952         }
    953 
    954         /**
    955          * Polls for and executes the given task or any other task in
    956          * its CountedCompleter computation.
    957          */
    958         final boolean pollAndExecCC(ForkJoinTask<?> root) {
    959             ForkJoinTask<?>[] a; int b; Object o;
    960             outer: while ((b = base) - top < 0 && (a = array) != null) {
    961                 long j = (((a.length - 1) & b) << ASHIFT) + ABASE;
    962                 if ((o = U.getObject(a, j)) == null ||
    963                     !(o instanceof CountedCompleter))
    964                     break;
    965                 for (CountedCompleter<?> t = (CountedCompleter<?>)o, r = t;;) {
    966                     if (r == root) {
    967                         if (base == b &&
    968                             U.compareAndSwapObject(a, j, t, null)) {
    969                             base = b + 1;
    970                             t.doExec();
    971                             return true;
    972                         }
    973                         else
    974                             break; // restart
    975                     }
    976                     if ((r = r.completer) == null)
    977                         break outer; // not part of root computation
    978                 }
    979             }
    980             return false;
    981         }
    982 
    983         /**
    984          * Executes a top-level task and any local tasks remaining
    985          * after execution.
    986          */
    987         final void runTask(ForkJoinTask<?> t) {
    988             if (t != null) {
    989                 (currentSteal = t).doExec();
    990                 currentSteal = null;
    991                 ++nsteals;
    992                 if (base - top < 0) {       // process remaining local tasks
    993                     if (mode == 0)
    994                         popAndExecAll();
    995                     else
    996                         pollAndExecAll();
    997                 }
    998             }
    999         }
   1000 
   1001         /**
   1002          * Executes a non-top-level (stolen) task.
   1003          */
   1004         final void runSubtask(ForkJoinTask<?> t) {
   1005             if (t != null) {
   1006                 ForkJoinTask<?> ps = currentSteal;
   1007                 (currentSteal = t).doExec();
   1008                 currentSteal = ps;
   1009             }
   1010         }
   1011 
   1012         /**
   1013          * Returns true if owned and not known to be blocked.
   1014          */
   1015         final boolean isApparentlyUnblocked() {
   1016             Thread wt; Thread.State s;
   1017             return (eventCount >= 0 &&
   1018                     (wt = owner) != null &&
   1019                     (s = wt.getState()) != Thread.State.BLOCKED &&
   1020                     s != Thread.State.WAITING &&
   1021                     s != Thread.State.TIMED_WAITING);
   1022         }
   1023 
   1024         // Unsafe mechanics
   1025         private static final sun.misc.Unsafe U;
   1026         private static final long QLOCK;
   1027         private static final int ABASE;
   1028         private static final int ASHIFT;
   1029         static {
   1030             try {
   1031                 U = sun.misc.Unsafe.getUnsafe();
   1032                 Class<?> k = WorkQueue.class;
   1033                 Class<?> ak = ForkJoinTask[].class;
   1034                 QLOCK = U.objectFieldOffset
   1035                     (k.getDeclaredField("qlock"));
   1036                 ABASE = U.arrayBaseOffset(ak);
   1037                 int scale = U.arrayIndexScale(ak);
   1038                 if ((scale & (scale - 1)) != 0)
   1039                     throw new Error("data type scale not a power of two");
   1040                 ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
   1041             } catch (Exception e) {
   1042                 throw new Error(e);
   1043             }
   1044         }
   1045     }
   1046 
   1047     // static fields (initialized in static initializer below)
   1048 
   1049     /**
   1050      * Creates a new ForkJoinWorkerThread. This factory is used unless
   1051      * overridden in ForkJoinPool constructors.
   1052      */
   1053     public static final ForkJoinWorkerThreadFactory
   1054         defaultForkJoinWorkerThreadFactory;
   1055 
   1056     /**
   1057      * Per-thread submission bookkeeping. Shared across all pools
   1058      * to reduce ThreadLocal pollution and because random motion
   1059      * to avoid contention in one pool is likely to hold for others.
   1060      * Lazily initialized on first submission (but null-checked
   1061      * in other contexts to avoid unnecessary initialization).
   1062      */
   1063     static final ThreadLocal<Submitter> submitters;
   1064 
   1065     /**
   1066      * Permission required for callers of methods that may start or
   1067      * kill threads.
   1068      */
   1069     private static final RuntimePermission modifyThreadPermission;
   1070 
   1071     /**
   1072      * Common (static) pool. Non-null for public use unless a static
   1073      * construction exception, but internal usages null-check on use
   1074      * to paranoically avoid potential initialization circularities
   1075      * as well as to simplify generated code.
   1076      */
   1077     static final ForkJoinPool commonPool;
   1078 
   1079     /**
   1080      * Common pool parallelism. Must equal commonPool.parallelism.
   1081      */
   1082     static final int commonPoolParallelism;
   1083 
   1084     /**
   1085      * Sequence number for creating workerNamePrefix.
   1086      */
   1087     private static int poolNumberSequence;
   1088 
   1089     /**
   1090      * Returns the next sequence number. We don't expect this to
   1091      * ever contend, so use simple builtin sync.
   1092      */
   1093     private static final synchronized int nextPoolId() {
   1094         return ++poolNumberSequence;
   1095     }
   1096 
   1097     // static constants
   1098 
   1099     /**
   1100      * Initial timeout value (in nanoseconds) for the thread
   1101      * triggering quiescence to park waiting for new work. On timeout,
   1102      * the thread will instead try to shrink the number of
   1103      * workers. The value should be large enough to avoid overly
   1104      * aggressive shrinkage during most transient stalls (long GCs
   1105      * etc).
   1106      */
   1107     private static final long IDLE_TIMEOUT      = 2000L * 1000L * 1000L; // 2sec
   1108 
   1109     /**
   1110      * Timeout value when there are more threads than parallelism level
   1111      */
   1112     private static final long FAST_IDLE_TIMEOUT =  200L * 1000L * 1000L;
   1113 
   1114     /**
   1115      * Tolerance for idle timeouts, to cope with timer undershoots
   1116      */
   1117     private static final long TIMEOUT_SLOP = 2000000L; // 20ms
   1118 
   1119     /**
   1120      * The maximum stolen->joining link depth allowed in method
   1121      * tryHelpStealer.  Must be a power of two.  Depths for legitimate
   1122      * chains are unbounded, but we use a fixed constant to avoid
   1123      * (otherwise unchecked) cycles and to bound staleness of
   1124      * traversal parameters at the expense of sometimes blocking when
   1125      * we could be helping.
   1126      */
   1127     private static final int MAX_HELP = 64;
   1128 
   1129     /**
   1130      * Increment for seed generators. See class ThreadLocal for
   1131      * explanation.
   1132      */
   1133     private static final int SEED_INCREMENT = 0x61c88647;
   1134 
   1135     /*
   1136      * Bits and masks for control variables
   1137      *
   1138      * Field ctl is a long packed with:
   1139      * AC: Number of active running workers minus target parallelism (16 bits)
   1140      * TC: Number of total workers minus target parallelism (16 bits)
   1141      * ST: true if pool is terminating (1 bit)
   1142      * EC: the wait count of top waiting thread (15 bits)
   1143      * ID: poolIndex of top of Treiber stack of waiters (16 bits)
   1144      *
   1145      * When convenient, we can extract the upper 32 bits of counts and
   1146      * the lower 32 bits of queue state, u = (int)(ctl >>> 32) and e =
   1147      * (int)ctl.  The ec field is never accessed alone, but always
   1148      * together with id and st. The offsets of counts by the target
   1149      * parallelism and the positionings of fields makes it possible to
   1150      * perform the most common checks via sign tests of fields: When
   1151      * ac is negative, there are not enough active workers, when tc is
   1152      * negative, there are not enough total workers, and when e is
   1153      * negative, the pool is terminating.  To deal with these possibly
   1154      * negative fields, we use casts in and out of "short" and/or
   1155      * signed shifts to maintain signedness.
   1156      *
   1157      * When a thread is queued (inactivated), its eventCount field is
   1158      * set negative, which is the only way to tell if a worker is
   1159      * prevented from executing tasks, even though it must continue to
   1160      * scan for them to avoid queuing races. Note however that
   1161      * eventCount updates lag releases so usage requires care.
   1162      *
   1163      * Field plock is an int packed with:
   1164      * SHUTDOWN: true if shutdown is enabled (1 bit)
   1165      * SEQ:  a sequence lock, with PL_LOCK bit set if locked (30 bits)
   1166      * SIGNAL: set when threads may be waiting on the lock (1 bit)
   1167      *
   1168      * The sequence number enables simple consistency checks:
   1169      * Staleness of read-only operations on the workQueues array can
   1170      * be checked by comparing plock before vs after the reads.
   1171      */
   1172 
   1173     // bit positions/shifts for fields
   1174     private static final int  AC_SHIFT   = 48;
   1175     private static final int  TC_SHIFT   = 32;
   1176     private static final int  ST_SHIFT   = 31;
   1177     private static final int  EC_SHIFT   = 16;
   1178 
   1179     // bounds
   1180     private static final int  SMASK      = 0xffff;  // short bits
   1181     private static final int  MAX_CAP    = 0x7fff;  // max #workers - 1
   1182     private static final int  EVENMASK   = 0xfffe;  // even short bits
   1183     private static final int  SQMASK     = 0x007e;  // max 64 (even) slots
   1184     private static final int  SHORT_SIGN = 1 << 15;
   1185     private static final int  INT_SIGN   = 1 << 31;
   1186 
   1187     // masks
   1188     private static final long STOP_BIT   = 0x0001L << ST_SHIFT;
   1189     private static final long AC_MASK    = ((long)SMASK) << AC_SHIFT;
   1190     private static final long TC_MASK    = ((long)SMASK) << TC_SHIFT;
   1191 
   1192     // units for incrementing and decrementing
   1193     private static final long TC_UNIT    = 1L << TC_SHIFT;
   1194     private static final long AC_UNIT    = 1L << AC_SHIFT;
   1195 
   1196     // masks and units for dealing with u = (int)(ctl >>> 32)
   1197     private static final int  UAC_SHIFT  = AC_SHIFT - 32;
   1198     private static final int  UTC_SHIFT  = TC_SHIFT - 32;
   1199     private static final int  UAC_MASK   = SMASK << UAC_SHIFT;
   1200     private static final int  UTC_MASK   = SMASK << UTC_SHIFT;
   1201     private static final int  UAC_UNIT   = 1 << UAC_SHIFT;
   1202     private static final int  UTC_UNIT   = 1 << UTC_SHIFT;
   1203 
   1204     // masks and units for dealing with e = (int)ctl
   1205     private static final int E_MASK      = 0x7fffffff; // no STOP_BIT
   1206     private static final int E_SEQ       = 1 << EC_SHIFT;
   1207 
   1208     // plock bits
   1209     private static final int SHUTDOWN    = 1 << 31;
   1210     private static final int PL_LOCK     = 2;
   1211     private static final int PL_SIGNAL   = 1;
   1212     private static final int PL_SPINS    = 1 << 8;
   1213 
   1214     // access mode for WorkQueue
   1215     static final int LIFO_QUEUE          =  0;
   1216     static final int FIFO_QUEUE          =  1;
   1217     static final int SHARED_QUEUE        = -1;
   1218 
   1219     // bounds for #steps in scan loop -- must be power 2 minus 1
   1220     private static final int MIN_SCAN    = 0x1ff;   // cover estimation slop
   1221     private static final int MAX_SCAN    = 0x1ffff; // 4 * max workers
   1222 
   1223     // Instance fields
   1224 
   1225     /*
   1226      * Field layout of this class tends to matter more than one would
   1227      * like. Runtime layout order is only loosely related to
   1228      * declaration order and may differ across JVMs, but the following
   1229      * empirically works OK on current JVMs.
   1230      */
   1231 
   1232     // Heuristic padding to ameliorate unfortunate memory placements
   1233     volatile long pad00, pad01, pad02, pad03, pad04, pad05, pad06;
   1234 
   1235     volatile long stealCount;                  // collects worker counts
   1236     volatile long ctl;                         // main pool control
   1237     volatile int plock;                        // shutdown status and seqLock
   1238     volatile int indexSeed;                    // worker/submitter index seed
   1239     final int config;                          // mode and parallelism level
   1240     WorkQueue[] workQueues;                    // main registry
   1241     final ForkJoinWorkerThreadFactory factory;
   1242     final Thread.UncaughtExceptionHandler ueh; // per-worker UEH
   1243     final String workerNamePrefix;             // to create worker name string
   1244 
   1245     volatile Object pad10, pad11, pad12, pad13, pad14, pad15, pad16, pad17;
   1246     volatile Object pad18, pad19, pad1a, pad1b;
   1247 
   1248     /**
   1249      * Acquires the plock lock to protect worker array and related
   1250      * updates. This method is called only if an initial CAS on plock
   1251      * fails. This acts as a spinlock for normal cases, but falls back
   1252      * to builtin monitor to block when (rarely) needed. This would be
   1253      * a terrible idea for a highly contended lock, but works fine as
   1254      * a more conservative alternative to a pure spinlock.
   1255      */
   1256     private int acquirePlock() {
   1257         int spins = PL_SPINS, r = 0, ps, nps;
   1258         for (;;) {
   1259             if (((ps = plock) & PL_LOCK) == 0 &&
   1260                 U.compareAndSwapInt(this, PLOCK, ps, nps = ps + PL_LOCK))
   1261                 return nps;
   1262             else if (r == 0) { // randomize spins if possible
   1263                 Thread t = Thread.currentThread(); WorkQueue w; Submitter z;
   1264                 if ((t instanceof ForkJoinWorkerThread) &&
   1265                     (w = ((ForkJoinWorkerThread)t).workQueue) != null)
   1266                     r = w.seed;
   1267                 else if ((z = submitters.get()) != null)
   1268                     r = z.seed;
   1269                 else
   1270                     r = 1;
   1271             }
   1272             else if (spins >= 0) {
   1273                 r ^= r << 1; r ^= r >>> 3; r ^= r << 10; // xorshift
   1274                 if (r >= 0)
   1275                     --spins;
   1276             }
   1277             else if (U.compareAndSwapInt(this, PLOCK, ps, ps | PL_SIGNAL)) {
   1278                 synchronized (this) {
   1279                     if ((plock & PL_SIGNAL) != 0) {
   1280                         try {
   1281                             wait();
   1282                         } catch (InterruptedException ie) {
   1283                             try {
   1284                                 Thread.currentThread().interrupt();
   1285                             } catch (SecurityException ignore) {
   1286                             }
   1287                         }
   1288                     }
   1289                     else
   1290                         notifyAll();
   1291                 }
   1292             }
   1293         }
   1294     }
   1295 
   1296     /**
   1297      * Unlocks and signals any thread waiting for plock. Called only
   1298      * when CAS of seq value for unlock fails.
   1299      */
   1300     private void releasePlock(int ps) {
   1301         plock = ps;
   1302         synchronized (this) { notifyAll(); }
   1303     }
   1304 
   1305     /**
   1306      * Performs secondary initialization, called when plock is zero.
   1307      * Creates workQueue array and sets plock to a valid value.  The
   1308      * lock body must be exception-free (so no try/finally) so we
   1309      * optimistically allocate new array outside the lock and throw
   1310      * away if (very rarely) not needed. (A similar tactic is used in
   1311      * fullExternalPush.)  Because the plock seq value can eventually
   1312      * wrap around zero, this method harmlessly fails to reinitialize
   1313      * if workQueues exists, while still advancing plock.
   1314      *
   1315      * Additionally tries to create the first worker.
   1316      */
   1317     private void initWorkers() {
   1318         WorkQueue[] ws, nws; int ps;
   1319         int p = config & SMASK;        // find power of two table size
   1320         int n = (p > 1) ? p - 1 : 1;   // ensure at least 2 slots
   1321         n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16;
   1322         n = (n + 1) << 1;
   1323         if ((ws = workQueues) == null || ws.length == 0)
   1324             nws = new WorkQueue[n];
   1325         else
   1326             nws = null;
   1327         if (((ps = plock) & PL_LOCK) != 0 ||
   1328             !U.compareAndSwapInt(this, PLOCK, ps, ps += PL_LOCK))
   1329             ps = acquirePlock();
   1330         if (((ws = workQueues) == null || ws.length == 0) && nws != null)
   1331             workQueues = nws;
   1332         int nps = (ps & SHUTDOWN) | ((ps + PL_LOCK) & ~SHUTDOWN);
   1333         if (!U.compareAndSwapInt(this, PLOCK, ps, nps))
   1334             releasePlock(nps);
   1335         tryAddWorker();
   1336     }
   1337 
   1338     /**
   1339      * Tries to create and start one worker if fewer than target
   1340      * parallelism level exist. Adjusts counts etc on failure.
   1341      */
   1342     private void tryAddWorker() {
   1343         long c; int u;
   1344         while ((u = (int)((c = ctl) >>> 32)) < 0 &&
   1345                (u & SHORT_SIGN) != 0 && (int)c == 0) {
   1346             long nc = (long)(((u + UTC_UNIT) & UTC_MASK) |
   1347                              ((u + UAC_UNIT) & UAC_MASK)) << 32;
   1348             if (U.compareAndSwapLong(this, CTL, c, nc)) {
   1349                 ForkJoinWorkerThreadFactory fac;
   1350                 Throwable ex = null;
   1351                 ForkJoinWorkerThread wt = null;
   1352                 try {
   1353                     if ((fac = factory) != null &&
   1354                         (wt = fac.newThread(this)) != null) {
   1355                         wt.start();
   1356                         break;
   1357                     }
   1358                 } catch (Throwable e) {
   1359                     ex = e;
   1360                 }
   1361                 deregisterWorker(wt, ex);
   1362                 break;
   1363             }
   1364         }
   1365     }
   1366 
   1367     //  Registering and deregistering workers
   1368 
   1369     /**
   1370      * Callback from ForkJoinWorkerThread to establish and record its
   1371      * WorkQueue. To avoid scanning bias due to packing entries in
   1372      * front of the workQueues array, we treat the array as a simple
   1373      * power-of-two hash table using per-thread seed as hash,
   1374      * expanding as needed.
   1375      *
   1376      * @param wt the worker thread
   1377      * @return the worker's queue
   1378      */
   1379     final WorkQueue registerWorker(ForkJoinWorkerThread wt) {
   1380         Thread.UncaughtExceptionHandler handler; WorkQueue[] ws; int s, ps;
   1381         wt.setDaemon(true);
   1382         if ((handler = ueh) != null)
   1383             wt.setUncaughtExceptionHandler(handler);
   1384         do {} while (!U.compareAndSwapInt(this, INDEXSEED, s = indexSeed,
   1385                                           s += SEED_INCREMENT) ||
   1386                      s == 0); // skip 0
   1387         WorkQueue w = new WorkQueue(this, wt, config >>> 16, s);
   1388         if (((ps = plock) & PL_LOCK) != 0 ||
   1389             !U.compareAndSwapInt(this, PLOCK, ps, ps += PL_LOCK))
   1390             ps = acquirePlock();
   1391         int nps = (ps & SHUTDOWN) | ((ps + PL_LOCK) & ~SHUTDOWN);
   1392         try {
   1393             if ((ws = workQueues) != null) {    // skip if shutting down
   1394                 int n = ws.length, m = n - 1;
   1395                 int r = (s << 1) | 1;           // use odd-numbered indices
   1396                 if (ws[r &= m] != null) {       // collision
   1397                     int probes = 0;             // step by approx half size
   1398                     int step = (n <= 4) ? 2 : ((n >>> 1) & EVENMASK) + 2;
   1399                     while (ws[r = (r + step) & m] != null) {
   1400                         if (++probes >= n) {
   1401                             workQueues = ws = Arrays.copyOf(ws, n <<= 1);
   1402                             m = n - 1;
   1403                             probes = 0;
   1404                         }
   1405                     }
   1406                 }
   1407                 w.eventCount = w.poolIndex = r; // volatile write orders
   1408                 ws[r] = w;
   1409             }
   1410         } finally {
   1411             if (!U.compareAndSwapInt(this, PLOCK, ps, nps))
   1412                 releasePlock(nps);
   1413         }
   1414         wt.setName(workerNamePrefix.concat(Integer.toString(w.poolIndex)));
   1415         return w;
   1416     }
   1417 
   1418     /**
   1419      * Final callback from terminating worker, as well as upon failure
   1420      * to construct or start a worker.  Removes record of worker from
   1421      * array, and adjusts counts. If pool is shutting down, tries to
   1422      * complete termination.
   1423      *
   1424      * @param wt the worker thread or null if construction failed
   1425      * @param ex the exception causing failure, or null if none
   1426      */
   1427     final void deregisterWorker(ForkJoinWorkerThread wt, Throwable ex) {
   1428         WorkQueue w = null;
   1429         if (wt != null && (w = wt.workQueue) != null) {
   1430             int ps;
   1431             w.qlock = -1;                // ensure set
   1432             long ns = w.nsteals, sc;     // collect steal count
   1433             do {} while (!U.compareAndSwapLong(this, STEALCOUNT,
   1434                                                sc = stealCount, sc + ns));
   1435             if (((ps = plock) & PL_LOCK) != 0 ||
   1436                 !U.compareAndSwapInt(this, PLOCK, ps, ps += PL_LOCK))
   1437                 ps = acquirePlock();
   1438             int nps = (ps & SHUTDOWN) | ((ps + PL_LOCK) & ~SHUTDOWN);
   1439             try {
   1440                 int idx = w.poolIndex;
   1441                 WorkQueue[] ws = workQueues;
   1442                 if (ws != null && idx >= 0 && idx < ws.length && ws[idx] == w)
   1443                     ws[idx] = null;
   1444             } finally {
   1445                 if (!U.compareAndSwapInt(this, PLOCK, ps, nps))
   1446                     releasePlock(nps);
   1447             }
   1448         }
   1449 
   1450         long c;                          // adjust ctl counts
   1451         do {} while (!U.compareAndSwapLong
   1452                      (this, CTL, c = ctl, (((c - AC_UNIT) & AC_MASK) |
   1453                                            ((c - TC_UNIT) & TC_MASK) |
   1454                                            (c & ~(AC_MASK|TC_MASK)))));
   1455 
   1456         if (!tryTerminate(false, false) && w != null && w.array != null) {
   1457             w.cancelAll();               // cancel remaining tasks
   1458             WorkQueue[] ws; WorkQueue v; Thread p; int u, i, e;
   1459             while ((u = (int)((c = ctl) >>> 32)) < 0 && (e = (int)c) >= 0) {
   1460                 if (e > 0) {             // activate or create replacement
   1461                     if ((ws = workQueues) == null ||
   1462                         (i = e & SMASK) >= ws.length ||
   1463                         (v = ws[i]) != null)
   1464                         break;
   1465                     long nc = (((long)(v.nextWait & E_MASK)) |
   1466                                ((long)(u + UAC_UNIT) << 32));
   1467                     if (v.eventCount != (e | INT_SIGN))
   1468                         break;
   1469                     if (U.compareAndSwapLong(this, CTL, c, nc)) {
   1470                         v.eventCount = (e + E_SEQ) & E_MASK;
   1471                         if ((p = v.parker) != null)
   1472                             U.unpark(p);
   1473                         break;
   1474                     }
   1475                 }
   1476                 else {
   1477                     if ((short)u < 0)
   1478                         tryAddWorker();
   1479                     break;
   1480                 }
   1481             }
   1482         }
   1483         if (ex == null)                     // help clean refs on way out
   1484             ForkJoinTask.helpExpungeStaleExceptions();
   1485         else                                // rethrow
   1486             ForkJoinTask.rethrow(ex);
   1487     }
   1488 
   1489     // Submissions
   1490 
   1491     /**
   1492      * Unless shutting down, adds the given task to a submission queue
   1493      * at submitter's current queue index (modulo submission
   1494      * range). Only the most common path is directly handled in this
   1495      * method. All others are relayed to fullExternalPush.
   1496      *
   1497      * @param task the task. Caller must ensure non-null.
   1498      */
   1499     final void externalPush(ForkJoinTask<?> task) {
   1500         WorkQueue[] ws; WorkQueue q; Submitter z; int m; ForkJoinTask<?>[] a;
   1501         if ((z = submitters.get()) != null && plock > 0 &&
   1502             (ws = workQueues) != null && (m = (ws.length - 1)) >= 0 &&
   1503             (q = ws[m & z.seed & SQMASK]) != null &&
   1504             U.compareAndSwapInt(q, QLOCK, 0, 1)) { // lock
   1505             int b = q.base, s = q.top, n, an;
   1506             if ((a = q.array) != null && (an = a.length) > (n = s + 1 - b)) {
   1507                 int j = (((an - 1) & s) << ASHIFT) + ABASE;
   1508                 U.putOrderedObject(a, j, task);
   1509                 q.top = s + 1;                     // push on to deque
   1510                 q.qlock = 0;
   1511                 if (n <= 2)
   1512                     signalWork(q);
   1513                 return;
   1514             }
   1515             q.qlock = 0;
   1516         }
   1517         fullExternalPush(task);
   1518     }
   1519 
   1520     /**
   1521      * Full version of externalPush. This method is called, among
   1522      * other times, upon the first submission of the first task to the
   1523      * pool, so must perform secondary initialization (via
   1524      * initWorkers). It also detects first submission by an external
   1525      * thread by looking up its ThreadLocal, and creates a new shared
   1526      * queue if the one at index if empty or contended. The plock lock
   1527      * body must be exception-free (so no try/finally) so we
   1528      * optimistically allocate new queues outside the lock and throw
   1529      * them away if (very rarely) not needed.
   1530      */
   1531     private void fullExternalPush(ForkJoinTask<?> task) {
   1532         int r = 0; // random index seed
   1533         for (Submitter z = submitters.get();;) {
   1534             WorkQueue[] ws; WorkQueue q; int ps, m, k;
   1535             if (z == null) {
   1536                 if (U.compareAndSwapInt(this, INDEXSEED, r = indexSeed,
   1537                                         r += SEED_INCREMENT) && r != 0)
   1538                     submitters.set(z = new Submitter(r));
   1539             }
   1540             else if (r == 0) {               // move to a different index
   1541                 r = z.seed;
   1542                 r ^= r << 13;                // same xorshift as WorkQueues
   1543                 r ^= r >>> 17;
   1544                 z.seed = r ^ (r << 5);
   1545             }
   1546             else if ((ps = plock) < 0)
   1547                 throw new RejectedExecutionException();
   1548             else if (ps == 0 || (ws = workQueues) == null ||
   1549                      (m = ws.length - 1) < 0)
   1550                 initWorkers();
   1551             else if ((q = ws[k = r & m & SQMASK]) != null) {
   1552                 if (q.qlock == 0 && U.compareAndSwapInt(q, QLOCK, 0, 1)) {
   1553                     ForkJoinTask<?>[] a = q.array;
   1554                     int s = q.top;
   1555                     boolean submitted = false;
   1556                     try {                      // locked version of push
   1557                         if ((a != null && a.length > s + 1 - q.base) ||
   1558                             (a = q.growArray()) != null) {   // must presize
   1559                             int j = (((a.length - 1) & s) << ASHIFT) + ABASE;
   1560                             U.putOrderedObject(a, j, task);
   1561                             q.top = s + 1;
   1562                             submitted = true;
   1563                         }
   1564                     } finally {
   1565                         q.qlock = 0;  // unlock
   1566                     }
   1567                     if (submitted) {
   1568                         signalWork(q);
   1569                         return;
   1570                     }
   1571                 }
   1572                 r = 0; // move on failure
   1573             }
   1574             else if (((ps = plock) & PL_LOCK) == 0) { // create new queue
   1575                 q = new WorkQueue(this, null, SHARED_QUEUE, r);
   1576                 if (((ps = plock) & PL_LOCK) != 0 ||
   1577                     !U.compareAndSwapInt(this, PLOCK, ps, ps += PL_LOCK))
   1578                     ps = acquirePlock();
   1579                 if ((ws = workQueues) != null && k < ws.length && ws[k] == null)
   1580                     ws[k] = q;
   1581                 int nps = (ps & SHUTDOWN) | ((ps + PL_LOCK) & ~SHUTDOWN);
   1582                 if (!U.compareAndSwapInt(this, PLOCK, ps, nps))
   1583                     releasePlock(nps);
   1584             }
   1585             else
   1586                 r = 0; // try elsewhere while lock held
   1587         }
   1588     }
   1589 
   1590     // Maintaining ctl counts
   1591 
   1592     /**
   1593      * Increments active count; mainly called upon return from blocking.
   1594      */
   1595     final void incrementActiveCount() {
   1596         long c;
   1597         do {} while (!U.compareAndSwapLong(this, CTL, c = ctl, c + AC_UNIT));
   1598     }
   1599 
   1600     /**
   1601      * Tries to create or activate a worker if too few are active.
   1602      *
   1603      * @param q the (non-null) queue holding tasks to be signalled
   1604      */
   1605     final void signalWork(WorkQueue q) {
   1606         int hint = q.poolIndex;
   1607         long c; int e, u, i, n; WorkQueue[] ws; WorkQueue w; Thread p;
   1608         while ((u = (int)((c = ctl) >>> 32)) < 0) {
   1609             if ((e = (int)c) > 0) {
   1610                 if ((ws = workQueues) != null && ws.length > (i = e & SMASK) &&
   1611                     (w = ws[i]) != null && w.eventCount == (e | INT_SIGN)) {
   1612                     long nc = (((long)(w.nextWait & E_MASK)) |
   1613                                ((long)(u + UAC_UNIT) << 32));
   1614                     if (U.compareAndSwapLong(this, CTL, c, nc)) {
   1615                         w.hint = hint;
   1616                         w.eventCount = (e + E_SEQ) & E_MASK;
   1617                         if ((p = w.parker) != null)
   1618                             U.unpark(p);
   1619                         break;
   1620                     }
   1621                     if (q.top - q.base <= 0)
   1622                         break;
   1623                 }
   1624                 else
   1625                     break;
   1626             }
   1627             else {
   1628                 if ((short)u < 0)
   1629                     tryAddWorker();
   1630                 break;
   1631             }
   1632         }
   1633     }
   1634 
   1635     // Scanning for tasks
   1636 
   1637     /**
   1638      * Top-level runloop for workers, called by ForkJoinWorkerThread.run.
   1639      */
   1640     final void runWorker(WorkQueue w) {
   1641         w.growArray(); // allocate queue
   1642         do { w.runTask(scan(w)); } while (w.qlock >= 0);
   1643     }
   1644 
   1645     /**
   1646      * Scans for and, if found, returns one task, else possibly
   1647      * inactivates the worker. This method operates on single reads of
   1648      * volatile state and is designed to be re-invoked continuously,
   1649      * in part because it returns upon detecting inconsistencies,
   1650      * contention, or state changes that indicate possible success on
   1651      * re-invocation.
   1652      *
   1653      * The scan searches for tasks across queues (starting at a random
   1654      * index, and relying on registerWorker to irregularly scatter
   1655      * them within array to avoid bias), checking each at least twice.
   1656      * The scan terminates upon either finding a non-empty queue, or
   1657      * completing the sweep. If the worker is not inactivated, it
   1658      * takes and returns a task from this queue. Otherwise, if not
   1659      * activated, it signals workers (that may include itself) and
   1660      * returns so caller can retry. Also returns for true if the
   1661      * worker array may have changed during an empty scan.  On failure
   1662      * to find a task, we take one of the following actions, after
   1663      * which the caller will retry calling this method unless
   1664      * terminated.
   1665      *
   1666      * * If pool is terminating, terminate the worker.
   1667      *
   1668      * * If not already enqueued, try to inactivate and enqueue the
   1669      * worker on wait queue. Or, if inactivating has caused the pool
   1670      * to be quiescent, relay to idleAwaitWork to possibly shrink
   1671      * pool.
   1672      *
   1673      * * If already enqueued and none of the above apply, possibly
   1674      * park awaiting signal, else lingering to help scan and signal.
   1675      *
   1676      * * If a non-empty queue discovered or left as a hint,
   1677      * help wake up other workers before return.
   1678      *
   1679      * @param w the worker (via its WorkQueue)
   1680      * @return a task or null if none found
   1681      */
   1682     private final ForkJoinTask<?> scan(WorkQueue w) {
   1683         WorkQueue[] ws; int m;
   1684         int ps = plock;                          // read plock before ws
   1685         if (w != null && (ws = workQueues) != null && (m = ws.length - 1) >= 0) {
   1686             int ec = w.eventCount;               // ec is negative if inactive
   1687             int r = w.seed; r ^= r << 13; r ^= r >>> 17; w.seed = r ^= r << 5;
   1688             w.hint = -1;                         // update seed and clear hint
   1689             int j = ((m + m + 1) | MIN_SCAN) & MAX_SCAN;
   1690             do {
   1691                 WorkQueue q; ForkJoinTask<?>[] a; int b;
   1692                 if ((q = ws[(r + j) & m]) != null && (b = q.base) - q.top < 0 &&
   1693                     (a = q.array) != null) {     // probably nonempty
   1694                     int i = (((a.length - 1) & b) << ASHIFT) + ABASE;
   1695                     ForkJoinTask<?> t = (ForkJoinTask<?>)
   1696                         U.getObjectVolatile(a, i);
   1697                     if (q.base == b && ec >= 0 && t != null &&
   1698                         U.compareAndSwapObject(a, i, t, null)) {
   1699                         if ((q.base = b + 1) - q.top < 0)
   1700                             signalWork(q);
   1701                         return t;                // taken
   1702                     }
   1703                     else if ((ec < 0 || j < m) && (int)(ctl >> AC_SHIFT) <= 0) {
   1704                         w.hint = (r + j) & m;    // help signal below
   1705                         break;                   // cannot take
   1706                     }
   1707                 }
   1708             } while (--j >= 0);
   1709 
   1710             int h, e, ns; long c, sc; WorkQueue q;
   1711             if ((ns = w.nsteals) != 0) {
   1712                 if (U.compareAndSwapLong(this, STEALCOUNT,
   1713                                          sc = stealCount, sc + ns))
   1714                     w.nsteals = 0;               // collect steals and rescan
   1715             }
   1716             else if (plock != ps)                // consistency check
   1717                 ;                                // skip
   1718             else if ((e = (int)(c = ctl)) < 0)
   1719                 w.qlock = -1;                    // pool is terminating
   1720             else {
   1721                 if ((h = w.hint) < 0) {
   1722                     if (ec >= 0) {               // try to enqueue/inactivate
   1723                         long nc = (((long)ec |
   1724                                     ((c - AC_UNIT) & (AC_MASK|TC_MASK))));
   1725                         w.nextWait = e;          // link and mark inactive
   1726                         w.eventCount = ec | INT_SIGN;
   1727                         if (ctl != c || !U.compareAndSwapLong(this, CTL, c, nc))
   1728                             w.eventCount = ec;   // unmark on CAS failure
   1729                         else if ((int)(c >> AC_SHIFT) == 1 - (config & SMASK))
   1730                             idleAwaitWork(w, nc, c);
   1731                     }
   1732                     else if (w.eventCount < 0 && !tryTerminate(false, false) &&
   1733                              ctl == c) {         // block
   1734                         Thread wt = Thread.currentThread();
   1735                         Thread.interrupted();    // clear status
   1736                         U.putObject(wt, PARKBLOCKER, this);
   1737                         w.parker = wt;           // emulate LockSupport.park
   1738                         if (w.eventCount < 0)    // recheck
   1739                             U.park(false, 0L);
   1740                         w.parker = null;
   1741                         U.putObject(wt, PARKBLOCKER, null);
   1742                     }
   1743                 }
   1744                 if ((h >= 0 || (h = w.hint) >= 0) &&
   1745                     (ws = workQueues) != null && h < ws.length &&
   1746                     (q = ws[h]) != null) {      // signal others before retry
   1747                     WorkQueue v; Thread p; int u, i, s;
   1748                     for (int n = (config & SMASK) >>> 1;;) {
   1749                         int idleCount = (w.eventCount < 0) ? 0 : -1;
   1750                         if (((s = idleCount - q.base + q.top) <= n &&
   1751                              (n = s) <= 0) ||
   1752                             (u = (int)((c = ctl) >>> 32)) >= 0 ||
   1753                             (e = (int)c) <= 0 || m < (i = e & SMASK) ||
   1754                             (v = ws[i]) == null)
   1755                             break;
   1756                         long nc = (((long)(v.nextWait & E_MASK)) |
   1757                                    ((long)(u + UAC_UNIT) << 32));
   1758                         if (v.eventCount != (e | INT_SIGN) ||
   1759                             !U.compareAndSwapLong(this, CTL, c, nc))
   1760                             break;
   1761                         v.hint = h;
   1762                         v.eventCount = (e + E_SEQ) & E_MASK;
   1763                         if ((p = v.parker) != null)
   1764                             U.unpark(p);
   1765                         if (--n <= 0)
   1766                             break;
   1767                     }
   1768                 }
   1769             }
   1770         }
   1771         return null;
   1772     }
   1773 
   1774     /**
   1775      * If inactivating worker w has caused the pool to become
   1776      * quiescent, checks for pool termination, and, so long as this is
   1777      * not the only worker, waits for event for up to a given
   1778      * duration.  On timeout, if ctl has not changed, terminates the
   1779      * worker, which will in turn wake up another worker to possibly
   1780      * repeat this process.
   1781      *
   1782      * @param w the calling worker
   1783      * @param currentCtl the ctl value triggering possible quiescence
   1784      * @param prevCtl the ctl value to restore if thread is terminated
   1785      */
   1786     private void idleAwaitWork(WorkQueue w, long currentCtl, long prevCtl) {
   1787         if (w != null && w.eventCount < 0 &&
   1788             !tryTerminate(false, false) && (int)prevCtl != 0) {
   1789             int dc = -(short)(currentCtl >>> TC_SHIFT);
   1790             long parkTime = dc < 0 ? FAST_IDLE_TIMEOUT: (dc + 1) * IDLE_TIMEOUT;
   1791             long deadline = System.nanoTime() + parkTime - TIMEOUT_SLOP;
   1792             Thread wt = Thread.currentThread();
   1793             while (ctl == currentCtl) {
   1794                 Thread.interrupted();  // timed variant of version in scan()
   1795                 U.putObject(wt, PARKBLOCKER, this);
   1796                 w.parker = wt;
   1797                 if (ctl == currentCtl)
   1798                     U.park(false, parkTime);
   1799                 w.parker = null;
   1800                 U.putObject(wt, PARKBLOCKER, null);
   1801                 if (ctl != currentCtl)
   1802                     break;
   1803                 if (deadline - System.nanoTime() <= 0L &&
   1804                     U.compareAndSwapLong(this, CTL, currentCtl, prevCtl)) {
   1805                     w.eventCount = (w.eventCount + E_SEQ) | E_MASK;
   1806                     w.qlock = -1;   // shrink
   1807                     break;
   1808                 }
   1809             }
   1810         }
   1811     }
   1812 
   1813     /**
   1814      * Scans through queues looking for work while joining a task; if
   1815      * any present, signals. May return early if more signalling is
   1816      * detectably unneeded.
   1817      *
   1818      * @param task return early if done
   1819      * @param origin an index to start scan
   1820      */
   1821     private void helpSignal(ForkJoinTask<?> task, int origin) {
   1822         WorkQueue[] ws; WorkQueue w; Thread p; long c; int m, u, e, i, s;
   1823         if (task != null && task.status >= 0 &&
   1824             (u = (int)(ctl >>> 32)) < 0 && (u >> UAC_SHIFT) < 0 &&
   1825             (ws = workQueues) != null && (m = ws.length - 1) >= 0) {
   1826             outer: for (int k = origin, j = m; j >= 0; --j) {
   1827                 WorkQueue q = ws[k++ & m];
   1828                 for (int n = m;;) { // limit to at most m signals
   1829                     if (task.status < 0)
   1830                         break outer;
   1831                     if (q == null ||
   1832                         ((s = -q.base + q.top) <= n && (n = s) <= 0))
   1833                         break;
   1834                     if ((u = (int)((c = ctl) >>> 32)) >= 0 ||
   1835                         (e = (int)c) <= 0 || m < (i = e & SMASK) ||
   1836                         (w = ws[i]) == null)
   1837                         break outer;
   1838                     long nc = (((long)(w.nextWait & E_MASK)) |
   1839                                ((long)(u + UAC_UNIT) << 32));
   1840                     if (w.eventCount != (e | INT_SIGN))
   1841                         break outer;
   1842                     if (U.compareAndSwapLong(this, CTL, c, nc)) {
   1843                         w.eventCount = (e + E_SEQ) & E_MASK;
   1844                         if ((p = w.parker) != null)
   1845                             U.unpark(p);
   1846                         if (--n <= 0)
   1847                             break;
   1848                     }
   1849                 }
   1850             }
   1851         }
   1852     }
   1853 
   1854     /**
   1855      * Tries to locate and execute tasks for a stealer of the given
   1856      * task, or in turn one of its stealers, Traces currentSteal ->
   1857      * currentJoin links looking for a thread working on a descendant
   1858      * of the given task and with a non-empty queue to steal back and
   1859      * execute tasks from. The first call to this method upon a
   1860      * waiting join will often entail scanning/search, (which is OK
   1861      * because the joiner has nothing better to do), but this method
   1862      * leaves hints in workers to speed up subsequent calls. The
   1863      * implementation is very branchy to cope with potential
   1864      * inconsistencies or loops encountering chains that are stale,
   1865      * unknown, or so long that they are likely cyclic.
   1866      *
   1867      * @param joiner the joining worker
   1868      * @param task the task to join
   1869      * @return 0 if no progress can be made, negative if task
   1870      * known complete, else positive
   1871      */
   1872     private int tryHelpStealer(WorkQueue joiner, ForkJoinTask<?> task) {
   1873         int stat = 0, steps = 0;                    // bound to avoid cycles
   1874         if (joiner != null && task != null) {       // hoist null checks
   1875             restart: for (;;) {
   1876                 ForkJoinTask<?> subtask = task;     // current target
   1877                 for (WorkQueue j = joiner, v;;) {   // v is stealer of subtask
   1878                     WorkQueue[] ws; int m, s, h;
   1879                     if ((s = task.status) < 0) {
   1880                         stat = s;
   1881                         break restart;
   1882                     }
   1883                     if ((ws = workQueues) == null || (m = ws.length - 1) <= 0)
   1884                         break restart;              // shutting down
   1885                     if ((v = ws[h = (j.hint | 1) & m]) == null ||
   1886                         v.currentSteal != subtask) {
   1887                         for (int origin = h;;) {    // find stealer
   1888                             if (((h = (h + 2) & m) & 15) == 1 &&
   1889                                 (subtask.status < 0 || j.currentJoin != subtask))
   1890                                 continue restart;   // occasional staleness check
   1891                             if ((v = ws[h]) != null &&
   1892                                 v.currentSteal == subtask) {
   1893                                 j.hint = h;        // save hint
   1894                                 break;
   1895                             }
   1896                             if (h == origin)
   1897                                 break restart;      // cannot find stealer
   1898                         }
   1899                     }
   1900                     for (;;) { // help stealer or descend to its stealer
   1901                         ForkJoinTask[] a;  int b;
   1902                         if (subtask.status < 0)     // surround probes with
   1903                             continue restart;       //   consistency checks
   1904                         if ((b = v.base) - v.top < 0 && (a = v.array) != null) {
   1905                             int i = (((a.length - 1) & b) << ASHIFT) + ABASE;
   1906                             ForkJoinTask<?> t =
   1907                                 (ForkJoinTask<?>)U.getObjectVolatile(a, i);
   1908                             if (subtask.status < 0 || j.currentJoin != subtask ||
   1909                                 v.currentSteal != subtask)
   1910                                 continue restart;   // stale
   1911                             stat = 1;               // apparent progress
   1912                             if (t != null && v.base == b &&
   1913                                 U.compareAndSwapObject(a, i, t, null)) {
   1914                                 v.base = b + 1;     // help stealer
   1915                                 joiner.runSubtask(t);
   1916                             }
   1917                             else if (v.base == b && ++steps == MAX_HELP)
   1918                                 break restart;      // v apparently stalled
   1919                         }
   1920                         else {                      // empty -- try to descend
   1921                             ForkJoinTask<?> next = v.currentJoin;
   1922                             if (subtask.status < 0 || j.currentJoin != subtask ||
   1923                                 v.currentSteal != subtask)
   1924                                 continue restart;   // stale
   1925                             else if (next == null || ++steps == MAX_HELP)
   1926                                 break restart;      // dead-end or maybe cyclic
   1927                             else {
   1928                                 subtask = next;
   1929                                 j = v;
   1930                                 break;
   1931                             }
   1932                         }
   1933                     }
   1934                 }
   1935             }
   1936         }
   1937         return stat;
   1938     }
   1939 
   1940     /**
   1941      * Analog of tryHelpStealer for CountedCompleters. Tries to steal
   1942      * and run tasks within the target's computation.
   1943      *
   1944      * @param task the task to join
   1945      * @param mode if shared, exit upon completing any task
   1946      * if all workers are active
   1947      */
   1948     private int helpComplete(ForkJoinTask<?> task, int mode) {
   1949         WorkQueue[] ws; WorkQueue q; int m, n, s, u;
   1950         if (task != null && (ws = workQueues) != null &&
   1951             (m = ws.length - 1) >= 0) {
   1952             for (int j = 1, origin = j;;) {
   1953                 if ((s = task.status) < 0)
   1954                     return s;
   1955                 if ((q = ws[j & m]) != null && q.pollAndExecCC(task)) {
   1956                     origin = j;
   1957                     if (mode == SHARED_QUEUE &&
   1958                         ((u = (int)(ctl >>> 32)) >= 0 || (u >> UAC_SHIFT) >= 0))
   1959                         break;
   1960                 }
   1961                 else if ((j = (j + 2) & m) == origin)
   1962                     break;
   1963             }
   1964         }
   1965         return 0;
   1966     }
   1967 
   1968     /**
   1969      * Tries to decrement active count (sometimes implicitly) and
   1970      * possibly release or create a compensating worker in preparation
   1971      * for blocking. Fails on contention or termination. Otherwise,
   1972      * adds a new thread if no idle workers are available and pool
   1973      * may become starved.
   1974      */
   1975     final boolean tryCompensate() {
   1976         int pc = config & SMASK, e, i, tc; long c;
   1977         WorkQueue[] ws; WorkQueue w; Thread p;
   1978         if ((ws = workQueues) != null && (e = (int)(c = ctl)) >= 0) {
   1979             if (e != 0 && (i = e & SMASK) < ws.length &&
   1980                 (w = ws[i]) != null && w.eventCount == (e | INT_SIGN)) {
   1981                 long nc = ((long)(w.nextWait & E_MASK) |
   1982                            (c & (AC_MASK|TC_MASK)));
   1983                 if (U.compareAndSwapLong(this, CTL, c, nc)) {
   1984                     w.eventCount = (e + E_SEQ) & E_MASK;
   1985                     if ((p = w.parker) != null)
   1986                         U.unpark(p);
   1987                     return true;   // replace with idle worker
   1988                 }
   1989             }
   1990             else if ((tc = (short)(c >>> TC_SHIFT)) >= 0 &&
   1991                      (int)(c >> AC_SHIFT) + pc > 1) {
   1992                 long nc = ((c - AC_UNIT) & AC_MASK) | (c & ~AC_MASK);
   1993                 if (U.compareAndSwapLong(this, CTL, c, nc))
   1994                     return true;   // no compensation
   1995             }
   1996             else if (tc + pc < MAX_CAP) {
   1997                 long nc = ((c + TC_UNIT) & TC_MASK) | (c & ~TC_MASK);
   1998                 if (U.compareAndSwapLong(this, CTL, c, nc)) {
   1999                     ForkJoinWorkerThreadFactory fac;
   2000                     Throwable ex = null;
   2001                     ForkJoinWorkerThread wt = null;
   2002                     try {
   2003                         if ((fac = factory) != null &&
   2004                             (wt = fac.newThread(this)) != null) {
   2005                             wt.start();
   2006                             return true;
   2007                         }
   2008                     } catch (Throwable rex) {
   2009                         ex = rex;
   2010                     }
   2011                     deregisterWorker(wt, ex); // clean up and return false
   2012                 }
   2013             }
   2014         }
   2015         return false;
   2016     }
   2017 
   2018     /**
   2019      * Helps and/or blocks until the given task is done.
   2020      *
   2021      * @param joiner the joining worker
   2022      * @param task the task
   2023      * @return task status on exit
   2024      */
   2025     final int awaitJoin(WorkQueue joiner, ForkJoinTask<?> task) {
   2026         int s = 0;
   2027         if (joiner != null && task != null && (s = task.status) >= 0) {
   2028             ForkJoinTask<?> prevJoin = joiner.currentJoin;
   2029             joiner.currentJoin = task;
   2030             do {} while ((s = task.status) >= 0 && !joiner.isEmpty() &&
   2031                          joiner.tryRemoveAndExec(task)); // process local tasks
   2032             if (s >= 0 && (s = task.status) >= 0) {
   2033                 helpSignal(task, joiner.poolIndex);
   2034                 if ((s = task.status) >= 0 &&
   2035                     (task instanceof CountedCompleter))
   2036                     s = helpComplete(task, LIFO_QUEUE);
   2037             }
   2038             while (s >= 0 && (s = task.status) >= 0) {
   2039                 if ((!joiner.isEmpty() ||           // try helping
   2040                      (s = tryHelpStealer(joiner, task)) == 0) &&
   2041                     (s = task.status) >= 0) {
   2042                     helpSignal(task, joiner.poolIndex);
   2043                     if ((s = task.status) >= 0 && tryCompensate()) {
   2044                         if (task.trySetSignal() && (s = task.status) >= 0) {
   2045                             synchronized (task) {
   2046                                 if (task.status >= 0) {
   2047                                     try {                // see ForkJoinTask
   2048                                         task.wait();     //  for explanation
   2049                                     } catch (InterruptedException ie) {
   2050                                     }
   2051                                 }
   2052                                 else
   2053                                     task.notifyAll();
   2054                             }
   2055                         }
   2056                         long c;                          // re-activate
   2057                         do {} while (!U.compareAndSwapLong
   2058                                      (this, CTL, c = ctl, c + AC_UNIT));
   2059                     }
   2060                 }
   2061             }
   2062             joiner.currentJoin = prevJoin;
   2063         }
   2064         return s;
   2065     }
   2066 
   2067     /**
   2068      * Stripped-down variant of awaitJoin used by timed joins. Tries
   2069      * to help join only while there is continuous progress. (Caller
   2070      * will then enter a timed wait.)
   2071      *
   2072      * @param joiner the joining worker
   2073      * @param task the task
   2074      */
   2075     final void helpJoinOnce(WorkQueue joiner, ForkJoinTask<?> task) {
   2076         int s;
   2077         if (joiner != null && task != null && (s = task.status) >= 0) {
   2078             ForkJoinTask<?> prevJoin = joiner.currentJoin;
   2079             joiner.currentJoin = task;
   2080             do {} while ((s = task.status) >= 0 && !joiner.isEmpty() &&
   2081                          joiner.tryRemoveAndExec(task));
   2082             if (s >= 0 && (s = task.status) >= 0) {
   2083                 helpSignal(task, joiner.poolIndex);
   2084                 if ((s = task.status) >= 0 &&
   2085                     (task instanceof CountedCompleter))
   2086                     s = helpComplete(task, LIFO_QUEUE);
   2087             }
   2088             if (s >= 0 && joiner.isEmpty()) {
   2089                 do {} while (task.status >= 0 &&
   2090                              tryHelpStealer(joiner, task) > 0);
   2091             }
   2092             joiner.currentJoin = prevJoin;
   2093         }
   2094     }
   2095 
   2096     /**
   2097      * Returns a (probably) non-empty steal queue, if one is found
   2098      * during a random, then cyclic scan, else null.  This method must
   2099      * be retried by caller if, by the time it tries to use the queue,
   2100      * it is empty.
   2101      * @param r a (random) seed for scanning
   2102      */
   2103     private WorkQueue findNonEmptyStealQueue(int r) {
   2104         for (WorkQueue[] ws;;) {
   2105             int ps = plock, m, n;
   2106             if ((ws = workQueues) == null || (m = ws.length - 1) < 1)
   2107                 return null;
   2108             for (int j = (m + 1) << 2; ;) {
   2109                 WorkQueue q = ws[(((r + j) << 1) | 1) & m];
   2110                 if (q != null && (n = q.base - q.top) < 0) {
   2111                     if (n < -1)
   2112                         signalWork(q);
   2113                     return q;
   2114                 }
   2115                 else if (--j < 0) {
   2116                     if (plock == ps)
   2117                         return null;
   2118                     break;
   2119                 }
   2120             }
   2121         }
   2122     }
   2123 
   2124     /**
   2125      * Runs tasks until {@code isQuiescent()}. We piggyback on
   2126      * active count ctl maintenance, but rather than blocking
   2127      * when tasks cannot be found, we rescan until all others cannot
   2128      * find tasks either.
   2129      */
   2130     final void helpQuiescePool(WorkQueue w) {
   2131         for (boolean active = true;;) {
   2132             ForkJoinTask<?> localTask; // exhaust local queue
   2133             while ((localTask = w.nextLocalTask()) != null)
   2134                 localTask.doExec();
   2135             // Similar to loop in scan(), but ignoring submissions
   2136             WorkQueue q = findNonEmptyStealQueue(w.nextSeed());
   2137             if (q != null) {
   2138                 ForkJoinTask<?> t; int b;
   2139                 if (!active) {      // re-establish active count
   2140                     long c;
   2141                     active = true;
   2142                     do {} while (!U.compareAndSwapLong
   2143                                  (this, CTL, c = ctl, c + AC_UNIT));
   2144                 }
   2145                 if ((b = q.base) - q.top < 0 && (t = q.pollAt(b)) != null)
   2146                     w.runSubtask(t);
   2147             }
   2148             else {
   2149                 long c;
   2150                 if (active) {       // decrement active count without queuing
   2151                     active = false;
   2152                     do {} while (!U.compareAndSwapLong
   2153                                  (this, CTL, c = ctl, c -= AC_UNIT));
   2154                 }
   2155                 else
   2156                     c = ctl;        // re-increment on exit
   2157                 if ((int)(c >> AC_SHIFT) + (config & SMASK) == 0) {
   2158                     do {} while (!U.compareAndSwapLong
   2159                                  (this, CTL, c = ctl, c + AC_UNIT));
   2160                     break;
   2161                 }
   2162             }
   2163         }
   2164     }
   2165 
   2166     /**
   2167      * Gets and removes a local or stolen task for the given worker.
   2168      *
   2169      * @return a task, if available
   2170      */
   2171     final ForkJoinTask<?> nextTaskFor(WorkQueue w) {
   2172         for (ForkJoinTask<?> t;;) {
   2173             WorkQueue q; int b;
   2174             if ((t = w.nextLocalTask()) != null)
   2175                 return t;
   2176             if ((q = findNonEmptyStealQueue(w.nextSeed())) == null)
   2177                 return null;
   2178             if ((b = q.base) - q.top < 0 && (t = q.pollAt(b)) != null)
   2179                 return t;
   2180         }
   2181     }
   2182 
   2183     /**
   2184      * Returns a cheap heuristic guide for task partitioning when
   2185      * programmers, frameworks, tools, or languages have little or no
   2186      * idea about task granularity.  In essence by offering this
   2187      * method, we ask users only about tradeoffs in overhead vs
   2188      * expected throughput and its variance, rather than how finely to
   2189      * partition tasks.
   2190      *
   2191      * In a steady state strict (tree-structured) computation, each
   2192      * thread makes available for stealing enough tasks for other
   2193      * threads to remain active. Inductively, if all threads play by
   2194      * the same rules, each thread should make available only a
   2195      * constant number of tasks.
   2196      *
   2197      * The minimum useful constant is just 1. But using a value of 1
   2198      * would require immediate replenishment upon each steal to
   2199      * maintain enough tasks, which is infeasible.  Further,
   2200      * partitionings/granularities of offered tasks should minimize
   2201      * steal rates, which in general means that threads nearer the top
   2202      * of computation tree should generate more than those nearer the
   2203      * bottom. In perfect steady state, each thread is at
   2204      * approximately the same level of computation tree. However,
   2205      * producing extra tasks amortizes the uncertainty of progress and
   2206      * diffusion assumptions.
   2207      *
   2208      * So, users will want to use values larger (but not much larger)
   2209      * than 1 to both smooth over transient shortages and hedge
   2210      * against uneven progress; as traded off against the cost of
   2211      * extra task overhead. We leave the user to pick a threshold
   2212      * value to compare with the results of this call to guide
   2213      * decisions, but recommend values such as 3.
   2214      *
   2215      * When all threads are active, it is on average OK to estimate
   2216      * surplus strictly locally. In steady-state, if one thread is
   2217      * maintaining say 2 surplus tasks, then so are others. So we can
   2218      * just use estimated queue length.  However, this strategy alone
   2219      * leads to serious mis-estimates in some non-steady-state
   2220      * conditions (ramp-up, ramp-down, other stalls). We can detect
   2221      * many of these by further considering the number of "idle"
   2222      * threads, that are known to have zero queued tasks, so
   2223      * compensate by a factor of (#idle/#active) threads.
   2224      *
   2225      * Note: The approximation of #busy workers as #active workers is
   2226      * not very good under current signalling scheme, and should be
   2227      * improved.
   2228      */
   2229     static int getSurplusQueuedTaskCount() {
   2230         Thread t; ForkJoinWorkerThread wt; ForkJoinPool pool; WorkQueue q;
   2231         if (((t = Thread.currentThread()) instanceof ForkJoinWorkerThread)) {
   2232             int p = (pool = (wt = (ForkJoinWorkerThread)t).pool).config & SMASK;
   2233             int n = (q = wt.workQueue).top - q.base;
   2234             int a = (int)(pool.ctl >> AC_SHIFT) + p;
   2235             return n - (a > (p >>>= 1) ? 0 :
   2236                         a > (p >>>= 1) ? 1 :
   2237                         a > (p >>>= 1) ? 2 :
   2238                         a > (p >>>= 1) ? 4 :
   2239                         8);
   2240         }
   2241         return 0;
   2242     }
   2243 
   2244     //  Termination
   2245 
   2246     /**
   2247      * Possibly initiates and/or completes termination.  The caller
   2248      * triggering termination runs three passes through workQueues:
   2249      * (0) Setting termination status, followed by wakeups of queued
   2250      * workers; (1) cancelling all tasks; (2) interrupting lagging
   2251      * threads (likely in external tasks, but possibly also blocked in
   2252      * joins).  Each pass repeats previous steps because of potential
   2253      * lagging thread creation.
   2254      *
   2255      * @param now if true, unconditionally terminate, else only
   2256      * if no work and no active workers
   2257      * @param enable if true, enable shutdown when next possible
   2258      * @return true if now terminating or terminated
   2259      */
   2260     private boolean tryTerminate(boolean now, boolean enable) {
   2261         if (this == commonPool)                     // cannot shut down
   2262             return false;
   2263         for (long c;;) {
   2264             if (((c = ctl) & STOP_BIT) != 0) {      // already terminating
   2265                 if ((short)(c >>> TC_SHIFT) == -(config & SMASK)) {
   2266                     synchronized (this) {
   2267                         notifyAll();                // signal when 0 workers
   2268                     }
   2269                 }
   2270                 return true;
   2271             }
   2272             if (plock >= 0) {                       // not yet enabled
   2273                 int ps;
   2274                 if (!enable)
   2275                     return false;
   2276                 if (((ps = plock) & PL_LOCK) != 0 ||
   2277                     !U.compareAndSwapInt(this, PLOCK, ps, ps += PL_LOCK))
   2278                     ps = acquirePlock();
   2279                 if (!U.compareAndSwapInt(this, PLOCK, ps, SHUTDOWN))
   2280                     releasePlock(SHUTDOWN);
   2281             }
   2282             if (!now) {                             // check if idle & no tasks
   2283                 if ((int)(c >> AC_SHIFT) != -(config & SMASK) ||
   2284                     hasQueuedSubmissions())
   2285                     return false;
   2286                 // Check for unqueued inactive workers. One pass suffices.
   2287                 WorkQueue[] ws = workQueues; WorkQueue w;
   2288                 if (ws != null) {
   2289                     for (int i = 1; i < ws.length; i += 2) {
   2290                         if ((w = ws[i]) != null && w.eventCount >= 0)
   2291                             return false;
   2292                     }
   2293                 }
   2294             }
   2295             if (U.compareAndSwapLong(this, CTL, c, c | STOP_BIT)) {
   2296                 for (int pass = 0; pass < 3; ++pass) {
   2297                     WorkQueue[] ws = workQueues;
   2298                     if (ws != null) {
   2299                         WorkQueue w; Thread wt;
   2300                         int n = ws.length;
   2301                         for (int i = 0; i < n; ++i) {
   2302                             if ((w = ws[i]) != null) {
   2303                                 w.qlock = -1;
   2304                                 if (pass > 0) {
   2305                                     w.cancelAll();
   2306                                     if (pass > 1 && (wt = w.owner) != null) {
   2307                                         if (!wt.isInterrupted()) {
   2308                                             try {
   2309                                                 wt.interrupt();
   2310                                             } catch (SecurityException ignore) {
   2311                                             }
   2312                                         }
   2313                                         U.unpark(wt);
   2314                                     }
   2315                                 }
   2316                             }
   2317                         }
   2318                         // Wake up workers parked on event queue
   2319                         int i, e; long cc; Thread p;
   2320                         while ((e = (int)(cc = ctl) & E_MASK) != 0 &&
   2321                                (i = e & SMASK) < n &&
   2322                                (w = ws[i]) != null) {
   2323                             long nc = ((long)(w.nextWait & E_MASK) |
   2324                                        ((cc + AC_UNIT) & AC_MASK) |
   2325                                        (cc & (TC_MASK|STOP_BIT)));
   2326                             if (w.eventCount == (e | INT_SIGN) &&
   2327                                 U.compareAndSwapLong(this, CTL, cc, nc)) {
   2328                                 w.eventCount = (e + E_SEQ) & E_MASK;
   2329                                 w.qlock = -1;
   2330                                 if ((p = w.parker) != null)
   2331                                     U.unpark(p);
   2332                             }
   2333                         }
   2334                     }
   2335                 }
   2336             }
   2337         }
   2338     }
   2339 
   2340     // external operations on common pool
   2341 
   2342     /**
   2343      * Returns common pool queue for a thread that has submitted at
   2344      * least one task.
   2345      */
   2346     static WorkQueue commonSubmitterQueue() {
   2347         ForkJoinPool p; WorkQueue[] ws; int m; Submitter z;
   2348         return ((z = submitters.get()) != null &&
   2349                 (p = commonPool) != null &&
   2350                 (ws = p.workQueues) != null &&
   2351                 (m = ws.length - 1) >= 0) ?
   2352             ws[m & z.seed & SQMASK] : null;
   2353     }
   2354 
   2355     /**
   2356      * Tries to pop the given task from submitter's queue in common pool.
   2357      */
   2358     static boolean tryExternalUnpush(ForkJoinTask<?> t) {
   2359         ForkJoinPool p; WorkQueue[] ws; WorkQueue q; Submitter z;
   2360         ForkJoinTask<?>[] a;  int m, s;
   2361         if (t != null &&
   2362             (z = submitters.get()) != null &&
   2363             (p = commonPool) != null &&
   2364             (ws = p.workQueues) != null &&
   2365             (m = ws.length - 1) >= 0 &&
   2366             (q = ws[m & z.seed & SQMASK]) != null &&
   2367             (s = q.top) != q.base &&
   2368             (a = q.array) != null) {
   2369             long j = (((a.length - 1) & (s - 1)) << ASHIFT) + ABASE;
   2370             if (U.getObject(a, j) == t &&
   2371                 U.compareAndSwapInt(q, QLOCK, 0, 1)) {
   2372                 if (q.array == a && q.top == s && // recheck
   2373                     U.compareAndSwapObject(a, j, t, null)) {
   2374                     q.top = s - 1;
   2375                     q.qlock = 0;
   2376                     return true;
   2377                 }
   2378                 q.qlock = 0;
   2379             }
   2380         }
   2381         return false;
   2382     }
   2383 
   2384     /**
   2385      * Tries to pop and run local tasks within the same computation
   2386      * as the given root. On failure, tries to help complete from
   2387      * other queues via helpComplete.
   2388      */
   2389     private void externalHelpComplete(WorkQueue q, ForkJoinTask<?> root) {
   2390         ForkJoinTask<?>[] a; int m;
   2391         if (q != null && (a = q.array) != null && (m = (a.length - 1)) >= 0 &&
   2392             root != null && root.status >= 0) {
   2393             for (;;) {
   2394                 int s, u; Object o; CountedCompleter<?> task = null;
   2395                 if ((s = q.top) - q.base > 0) {
   2396                     long j = ((m & (s - 1)) << ASHIFT) + ABASE;
   2397                     if ((o = U.getObject(a, j)) != null &&
   2398                         (o instanceof CountedCompleter)) {
   2399                         CountedCompleter<?> t = (CountedCompleter<?>)o, r = t;
   2400                         do {
   2401                             if (r == root) {
   2402                                 if (U.compareAndSwapInt(q, QLOCK, 0, 1)) {
   2403                                     if (q.array == a && q.top == s &&
   2404                                         U.compareAndSwapObject(a, j, t, null)) {
   2405                                         q.top = s - 1;
   2406                                         task = t;
   2407                                     }
   2408                                     q.qlock = 0;
   2409                                 }
   2410                                 break;
   2411                             }
   2412                         } while ((r = r.completer) != null);
   2413                     }
   2414                 }
   2415                 if (task != null)
   2416                     task.doExec();
   2417                 if (root.status < 0 ||
   2418                     (u = (int)(ctl >>> 32)) >= 0 || (u >> UAC_SHIFT) >= 0)
   2419                     break;
   2420                 if (task == null) {
   2421                     helpSignal(root, q.poolIndex);
   2422                     if (root.status >= 0)
   2423                         helpComplete(root, SHARED_QUEUE);
   2424                     break;
   2425                 }
   2426             }
   2427         }
   2428     }
   2429 
   2430     /**
   2431      * Tries to help execute or signal availability of the given task
   2432      * from submitter's queue in common pool.
   2433      */
   2434     static void externalHelpJoin(ForkJoinTask<?> t) {
   2435         // Some hard-to-avoid overlap with tryExternalUnpush
   2436         ForkJoinPool p; WorkQueue[] ws; WorkQueue q, w; Submitter z;
   2437         ForkJoinTask<?>[] a;  int m, s, n;
   2438         if (t != null &&
   2439             (z = submitters.get()) != null &&
   2440             (p = commonPool) != null &&
   2441             (ws = p.workQueues) != null &&
   2442             (m = ws.length - 1) >= 0 &&
   2443             (q = ws[m & z.seed & SQMASK]) != null &&
   2444             (a = q.array) != null) {
   2445             int am = a.length - 1;
   2446             if ((s = q.top) != q.base) {
   2447                 long j = ((am & (s - 1)) << ASHIFT) + ABASE;
   2448                 if (U.getObject(a, j) == t &&
   2449                     U.compareAndSwapInt(q, QLOCK, 0, 1)) {
   2450                     if (q.array == a && q.top == s &&
   2451                         U.compareAndSwapObject(a, j, t, null)) {
   2452                         q.top = s - 1;
   2453                         q.qlock = 0;
   2454                         t.doExec();
   2455                     }
   2456                     else
   2457                         q.qlock = 0;
   2458                 }
   2459             }
   2460             if (t.status >= 0) {
   2461                 if (t instanceof CountedCompleter)
   2462                     p.externalHelpComplete(q, t);
   2463                 else
   2464                     p.helpSignal(t, q.poolIndex);
   2465             }
   2466         }
   2467     }
   2468 
   2469     /**
   2470      * Restricted version of helpQuiescePool for external callers
   2471      */
   2472     static void externalHelpQuiescePool() {
   2473         ForkJoinPool p; ForkJoinTask<?> t; WorkQueue q; int b;
   2474         if ((p = commonPool) != null &&
   2475             (q = p.findNonEmptyStealQueue(1)) != null &&
   2476             (b = q.base) - q.top < 0 &&
   2477             (t = q.pollAt(b)) != null)
   2478             t.doExec();
   2479     }
   2480 
   2481     // Exported methods
   2482 
   2483     // Constructors
   2484 
   2485     /**
   2486      * Creates a {@code ForkJoinPool} with parallelism equal to {@link
   2487      * java.lang.Runtime#availableProcessors}, using the {@linkplain
   2488      * #defaultForkJoinWorkerThreadFactory default thread factory},
   2489      * no UncaughtExceptionHandler, and non-async LIFO processing mode.
   2490      */
   2491     public ForkJoinPool() {
   2492         this(Math.min(MAX_CAP, Runtime.getRuntime().availableProcessors()),
   2493              defaultForkJoinWorkerThreadFactory, null, false);
   2494     }
   2495 
   2496     /**
   2497      * Creates a {@code ForkJoinPool} with the indicated parallelism
   2498      * level, the {@linkplain
   2499      * #defaultForkJoinWorkerThreadFactory default thread factory},
   2500      * no UncaughtExceptionHandler, and non-async LIFO processing mode.
   2501      *
   2502      * @param parallelism the parallelism level
   2503      * @throws IllegalArgumentException if parallelism less than or
   2504      *         equal to zero, or greater than implementation limit
   2505      */
   2506     public ForkJoinPool(int parallelism) {
   2507         this(parallelism, defaultForkJoinWorkerThreadFactory, null, false);
   2508     }
   2509 
   2510     /**
   2511      * Creates a {@code ForkJoinPool} with the given parameters.
   2512      *
   2513      * @param parallelism the parallelism level. For default value,
   2514      * use {@link java.lang.Runtime#availableProcessors}.
   2515      * @param factory the factory for creating new threads. For default value,
   2516      * use {@link #defaultForkJoinWorkerThreadFactory}.
   2517      * @param handler the handler for internal worker threads that
   2518      * terminate due to unrecoverable errors encountered while executing
   2519      * tasks. For default value, use {@code null}.
   2520      * @param asyncMode if true,
   2521      * establishes local first-in-first-out scheduling mode for forked
   2522      * tasks that are never joined. This mode may be more appropriate
   2523      * than default locally stack-based mode in applications in which
   2524      * worker threads only process event-style asynchronous tasks.
   2525      * For default value, use {@code false}.
   2526      * @throws IllegalArgumentException if parallelism less than or
   2527      *         equal to zero, or greater than implementation limit
   2528      * @throws NullPointerException if the factory is null
   2529      */
   2530     public ForkJoinPool(int parallelism,
   2531                         ForkJoinWorkerThreadFactory factory,
   2532                         Thread.UncaughtExceptionHandler handler,
   2533                         boolean asyncMode) {
   2534         checkPermission();
   2535         if (factory == null)
   2536             throw new NullPointerException();
   2537         if (parallelism <= 0 || parallelism > MAX_CAP)
   2538             throw new IllegalArgumentException();
   2539         this.factory = factory;
   2540         this.ueh = handler;
   2541         this.config = parallelism | (asyncMode ? (FIFO_QUEUE << 16) : 0);
   2542         long np = (long)(-parallelism); // offset ctl counts
   2543         this.ctl = ((np << AC_SHIFT) & AC_MASK) | ((np << TC_SHIFT) & TC_MASK);
   2544         int pn = nextPoolId();
   2545         StringBuilder sb = new StringBuilder("ForkJoinPool-");
   2546         sb.append(Integer.toString(pn));
   2547         sb.append("-worker-");
   2548         this.workerNamePrefix = sb.toString();
   2549     }
   2550 
   2551     /**
   2552      * Constructor for common pool, suitable only for static initialization.
   2553      * Basically the same as above, but uses smallest possible initial footprint.
   2554      */
   2555     ForkJoinPool(int parallelism, long ctl,
   2556                  ForkJoinWorkerThreadFactory factory,
   2557                  Thread.UncaughtExceptionHandler handler) {
   2558         this.config = parallelism;
   2559         this.ctl = ctl;
   2560         this.factory = factory;
   2561         this.ueh = handler;
   2562         this.workerNamePrefix = "ForkJoinPool.commonPool-worker-";
   2563     }
   2564 
   2565     /**
   2566      * Returns the common pool instance.
   2567      *
   2568      * @return the common pool instance
   2569      * @since 1.8
   2570      * @hide
   2571      */
   2572     public static ForkJoinPool commonPool() {
   2573         // assert commonPool != null : "static init error";
   2574         return commonPool;
   2575     }
   2576 
   2577     // Execution methods
   2578 
   2579     /**
   2580      * Performs the given task, returning its result upon completion.
   2581      * If the computation encounters an unchecked Exception or Error,
   2582      * it is rethrown as the outcome of this invocation.  Rethrown
   2583      * exceptions behave in the same way as regular exceptions, but,
   2584      * when possible, contain stack traces (as displayed for example
   2585      * using {@code ex.printStackTrace()}) of both the current thread
   2586      * as well as the thread actually encountering the exception;
   2587      * minimally only the latter.
   2588      *
   2589      * @param task the task
   2590      * @return the task's result
   2591      * @throws NullPointerException if the task is null
   2592      * @throws RejectedExecutionException if the task cannot be
   2593      *         scheduled for execution
   2594      */
   2595     public <T> T invoke(ForkJoinTask<T> task) {
   2596         if (task == null)
   2597             throw new NullPointerException();
   2598         externalPush(task);
   2599         return task.join();
   2600     }
   2601 
   2602     /**
   2603      * Arranges for (asynchronous) execution of the given task.
   2604      *
   2605      * @param task the task
   2606      * @throws NullPointerException if the task is null
   2607      * @throws RejectedExecutionException if the task cannot be
   2608      *         scheduled for execution
   2609      */
   2610     public void execute(ForkJoinTask<?> task) {
   2611         if (task == null)
   2612             throw new NullPointerException();
   2613         externalPush(task);
   2614     }
   2615 
   2616     // AbstractExecutorService methods
   2617 
   2618     /**
   2619      * @throws NullPointerException if the task is null
   2620      * @throws RejectedExecutionException if the task cannot be
   2621      *         scheduled for execution
   2622      */
   2623     public void execute(Runnable task) {
   2624         if (task == null)
   2625             throw new NullPointerException();
   2626         ForkJoinTask<?> job;
   2627         if (task instanceof ForkJoinTask<?>) // avoid re-wrap
   2628             job = (ForkJoinTask<?>) task;
   2629         else
   2630             job = new ForkJoinTask.AdaptedRunnableAction(task);
   2631         externalPush(job);
   2632     }
   2633 
   2634     /**
   2635      * Submits a ForkJoinTask for execution.
   2636      *
   2637      * @param task the task to submit
   2638      * @return the task
   2639      * @throws NullPointerException if the task is null
   2640      * @throws RejectedExecutionException if the task cannot be
   2641      *         scheduled for execution
   2642      */
   2643     public <T> ForkJoinTask<T> submit(ForkJoinTask<T> task) {
   2644         if (task == null)
   2645             throw new NullPointerException();
   2646         externalPush(task);
   2647         return task;
   2648     }
   2649 
   2650     /**
   2651      * @throws NullPointerException if the task is null
   2652      * @throws RejectedExecutionException if the task cannot be
   2653      *         scheduled for execution
   2654      */
   2655     public <T> ForkJoinTask<T> submit(Callable<T> task) {
   2656         ForkJoinTask<T> job = new ForkJoinTask.AdaptedCallable<T>(task);
   2657         externalPush(job);
   2658         return job;
   2659     }
   2660 
   2661     /**
   2662      * @throws NullPointerException if the task is null
   2663      * @throws RejectedExecutionException if the task cannot be
   2664      *         scheduled for execution
   2665      */
   2666     public <T> ForkJoinTask<T> submit(Runnable task, T result) {
   2667         ForkJoinTask<T> job = new ForkJoinTask.AdaptedRunnable<T>(task, result);
   2668         externalPush(job);
   2669         return job;
   2670     }
   2671 
   2672     /**
   2673      * @throws NullPointerException if the task is null
   2674      * @throws RejectedExecutionException if the task cannot be
   2675      *         scheduled for execution
   2676      */
   2677     public ForkJoinTask<?> submit(Runnable task) {
   2678         if (task == null)
   2679             throw new NullPointerException();
   2680         ForkJoinTask<?> job;
   2681         if (task instanceof ForkJoinTask<?>) // avoid re-wrap
   2682             job = (ForkJoinTask<?>) task;
   2683         else
   2684             job = new ForkJoinTask.AdaptedRunnableAction(task);
   2685         externalPush(job);
   2686         return job;
   2687     }
   2688 
   2689     /**
   2690      * @throws NullPointerException       {@inheritDoc}
   2691      * @throws RejectedExecutionException {@inheritDoc}
   2692      */
   2693     public <T> List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks) {
   2694         // In previous versions of this class, this method constructed
   2695         // a task to run ForkJoinTask.invokeAll, but now external
   2696         // invocation of multiple tasks is at least as efficient.
   2697         ArrayList<Future<T>> futures = new ArrayList<Future<T>>(tasks.size());
   2698 
   2699         boolean done = false;
   2700         try {
   2701             for (Callable<T> t : tasks) {
   2702                 ForkJoinTask<T> f = new ForkJoinTask.AdaptedCallable<T>(t);
   2703                 futures.add(f);
   2704                 externalPush(f);
   2705             }
   2706             for (int i = 0, size = futures.size(); i < size; i++)
   2707                 ((ForkJoinTask<?>)futures.get(i)).quietlyJoin();
   2708             done = true;
   2709             return futures;
   2710         } finally {
   2711             if (!done)
   2712                 for (int i = 0, size = futures.size(); i < size; i++)
   2713                     futures.get(i).cancel(false);
   2714         }
   2715     }
   2716 
   2717     /**
   2718      * Returns the factory used for constructing new workers.
   2719      *
   2720      * @return the factory used for constructing new workers
   2721      */
   2722     public ForkJoinWorkerThreadFactory getFactory() {
   2723         return factory;
   2724     }
   2725 
   2726     /**
   2727      * Returns the handler for internal worker threads that terminate
   2728      * due to unrecoverable errors encountered while executing tasks.
   2729      *
   2730      * @return the handler, or {@code null} if none
   2731      */
   2732     public Thread.UncaughtExceptionHandler getUncaughtExceptionHandler() {
   2733         return ueh;
   2734     }
   2735 
   2736     /**
   2737      * Returns the targeted parallelism level of this pool.
   2738      *
   2739      * @return the targeted parallelism level of this pool
   2740      */
   2741     public int getParallelism() {
   2742         return config & SMASK;
   2743     }
   2744 
   2745     /**
   2746      * Returns the targeted parallelism level of the common pool.
   2747      *
   2748      * @return the targeted parallelism level of the common pool
   2749      * @since 1.8
   2750      * @hide
   2751      */
   2752     public static int getCommonPoolParallelism() {
   2753         return commonPoolParallelism;
   2754     }
   2755 
   2756     /**
   2757      * Returns the number of worker threads that have started but not
   2758      * yet terminated.  The result returned by this method may differ
   2759      * from {@link #getParallelism} when threads are created to
   2760      * maintain parallelism when others are cooperatively blocked.
   2761      *
   2762      * @return the number of worker threads
   2763      */
   2764     public int getPoolSize() {
   2765         return (config & SMASK) + (short)(ctl >>> TC_SHIFT);
   2766     }
   2767 
   2768     /**
   2769      * Returns {@code true} if this pool uses local first-in-first-out
   2770      * scheduling mode for forked tasks that are never joined.
   2771      *
   2772      * @return {@code true} if this pool uses async mode
   2773      */
   2774     public boolean getAsyncMode() {
   2775         return (config >>> 16) == FIFO_QUEUE;
   2776     }
   2777 
   2778     /**
   2779      * Returns an estimate of the number of worker threads that are
   2780      * not blocked waiting to join tasks or for other managed
   2781      * synchronization. This method may overestimate the
   2782      * number of running threads.
   2783      *
   2784      * @return the number of worker threads
   2785      */
   2786     public int getRunningThreadCount() {
   2787         int rc = 0;
   2788         WorkQueue[] ws; WorkQueue w;
   2789         if ((ws = workQueues) != null) {
   2790             for (int i = 1; i < ws.length; i += 2) {
   2791                 if ((w = ws[i]) != null && w.isApparentlyUnblocked())
   2792                     ++rc;
   2793             }
   2794         }
   2795         return rc;
   2796     }
   2797 
   2798     /**
   2799      * Returns an estimate of the number of threads that are currently
   2800      * stealing or executing tasks. This method may overestimate the
   2801      * number of active threads.
   2802      *
   2803      * @return the number of active threads
   2804      */
   2805     public int getActiveThreadCount() {
   2806         int r = (config & SMASK) + (int)(ctl >> AC_SHIFT);
   2807         return (r <= 0) ? 0 : r; // suppress momentarily negative values
   2808     }
   2809 
   2810     /**
   2811      * Returns {@code true} if all worker threads are currently idle.
   2812      * An idle worker is one that cannot obtain a task to execute
   2813      * because none are available to steal from other threads, and
   2814      * there are no pending submissions to the pool. This method is
   2815      * conservative; it might not return {@code true} immediately upon
   2816      * idleness of all threads, but will eventually become true if
   2817      * threads remain inactive.
   2818      *
   2819      * @return {@code true} if all threads are currently idle
   2820      */
   2821     public boolean isQuiescent() {
   2822         return (int)(ctl >> AC_SHIFT) + (config & SMASK) == 0;
   2823     }
   2824 
   2825     /**
   2826      * Returns an estimate of the total number of tasks stolen from
   2827      * one thread's work queue by another. The reported value
   2828      * underestimates the actual total number of steals when the pool
   2829      * is not quiescent. This value may be useful for monitoring and
   2830      * tuning fork/join programs: in general, steal counts should be
   2831      * high enough to keep threads busy, but low enough to avoid
   2832      * overhead and contention across threads.
   2833      *
   2834      * @return the number of steals
   2835      */
   2836     public long getStealCount() {
   2837         long count = stealCount;
   2838         WorkQueue[] ws; WorkQueue w;
   2839         if ((ws = workQueues) != null) {
   2840             for (int i = 1; i < ws.length; i += 2) {
   2841                 if ((w = ws[i]) != null)
   2842                     count += w.nsteals;
   2843             }
   2844         }
   2845         return count;
   2846     }
   2847 
   2848     /**
   2849      * Returns an estimate of the total number of tasks currently held
   2850      * in queues by worker threads (but not including tasks submitted
   2851      * to the pool that have not begun executing). This value is only
   2852      * an approximation, obtained by iterating across all threads in
   2853      * the pool. This method may be useful for tuning task
   2854      * granularities.
   2855      *
   2856      * @return the number of queued tasks
   2857      */
   2858     public long getQueuedTaskCount() {
   2859         long count = 0;
   2860         WorkQueue[] ws; WorkQueue w;
   2861         if ((ws = workQueues) != null) {
   2862             for (int i = 1; i < ws.length; i += 2) {
   2863                 if ((w = ws[i]) != null)
   2864                     count += w.queueSize();
   2865             }
   2866         }
   2867         return count;
   2868     }
   2869 
   2870     /**
   2871      * Returns an estimate of the number of tasks submitted to this
   2872      * pool that have not yet begun executing.  This method may take
   2873      * time proportional to the number of submissions.
   2874      *
   2875      * @return the number of queued submissions
   2876      */
   2877     public int getQueuedSubmissionCount() {
   2878         int count = 0;
   2879         WorkQueue[] ws; WorkQueue w;
   2880         if ((ws = workQueues) != null) {
   2881             for (int i = 0; i < ws.length; i += 2) {
   2882                 if ((w = ws[i]) != null)
   2883                     count += w.queueSize();
   2884             }
   2885         }
   2886         return count;
   2887     }
   2888 
   2889     /**
   2890      * Returns {@code true} if there are any tasks submitted to this
   2891      * pool that have not yet begun executing.
   2892      *
   2893      * @return {@code true} if there are any queued submissions
   2894      */
   2895     public boolean hasQueuedSubmissions() {
   2896         WorkQueue[] ws; WorkQueue w;
   2897         if ((ws = workQueues) != null) {
   2898             for (int i = 0; i < ws.length; i += 2) {
   2899                 if ((w = ws[i]) != null && !w.isEmpty())
   2900                     return true;
   2901             }
   2902         }
   2903         return false;
   2904     }
   2905 
   2906     /**
   2907      * Removes and returns the next unexecuted submission if one is
   2908      * available.  This method may be useful in extensions to this
   2909      * class that re-assign work in systems with multiple pools.
   2910      *
   2911      * @return the next submission, or {@code null} if none
   2912      */
   2913     protected ForkJoinTask<?> pollSubmission() {
   2914         WorkQueue[] ws; WorkQueue w; ForkJoinTask<?> t;
   2915         if ((ws = workQueues) != null) {
   2916             for (int i = 0; i < ws.length; i += 2) {
   2917                 if ((w = ws[i]) != null && (t = w.poll()) != null)
   2918                     return t;
   2919             }
   2920         }
   2921         return null;
   2922     }
   2923 
   2924     /**
   2925      * Removes all available unexecuted submitted and forked tasks
   2926      * from scheduling queues and adds them to the given collection,
   2927      * without altering their execution status. These may include
   2928      * artificially generated or wrapped tasks. This method is
   2929      * designed to be invoked only when the pool is known to be
   2930      * quiescent. Invocations at other times may not remove all
   2931      * tasks. A failure encountered while attempting to add elements
   2932      * to collection {@code c} may result in elements being in
   2933      * neither, either or both collections when the associated
   2934      * exception is thrown.  The behavior of this operation is
   2935      * undefined if the specified collection is modified while the
   2936      * operation is in progress.
   2937      *
   2938      * @param c the collection to transfer elements into
   2939      * @return the number of elements transferred
   2940      */
   2941     protected int drainTasksTo(Collection<? super ForkJoinTask<?>> c) {
   2942         int count = 0;
   2943         WorkQueue[] ws; WorkQueue w; ForkJoinTask<?> t;
   2944         if ((ws = workQueues) != null) {
   2945             for (int i = 0; i < ws.length; ++i) {
   2946                 if ((w = ws[i]) != null) {
   2947                     while ((t = w.poll()) != null) {
   2948                         c.add(t);
   2949                         ++count;
   2950                     }
   2951                 }
   2952             }
   2953         }
   2954         return count;
   2955     }
   2956 
   2957     /**
   2958      * Returns a string identifying this pool, as well as its state,
   2959      * including indications of run state, parallelism level, and
   2960      * worker and task counts.
   2961      *
   2962      * @return a string identifying this pool, as well as its state
   2963      */
   2964     public String toString() {
   2965         // Use a single pass through workQueues to collect counts
   2966         long qt = 0L, qs = 0L; int rc = 0;
   2967         long st = stealCount;
   2968         long c = ctl;
   2969         WorkQueue[] ws; WorkQueue w;
   2970         if ((ws = workQueues) != null) {
   2971             for (int i = 0; i < ws.length; ++i) {
   2972                 if ((w = ws[i]) != null) {
   2973                     int size = w.queueSize();
   2974                     if ((i & 1) == 0)
   2975                         qs += size;
   2976                     else {
   2977                         qt += size;
   2978                         st += w.nsteals;
   2979                         if (w.isApparentlyUnblocked())
   2980                             ++rc;
   2981                     }
   2982                 }
   2983             }
   2984         }
   2985         int pc = (config & SMASK);
   2986         int tc = pc + (short)(c >>> TC_SHIFT);
   2987         int ac = pc + (int)(c >> AC_SHIFT);
   2988         if (ac < 0) // ignore transient negative
   2989             ac = 0;
   2990         String level;
   2991         if ((c & STOP_BIT) != 0)
   2992             level = (tc == 0) ? "Terminated" : "Terminating";
   2993         else
   2994             level = plock < 0 ? "Shutting down" : "Running";
   2995         return super.toString() +
   2996             "[" + level +
   2997             ", parallelism = " + pc +
   2998             ", size = " + tc +
   2999             ", active = " + ac +
   3000             ", running = " + rc +
   3001             ", steals = " + st +
   3002             ", tasks = " + qt +
   3003             ", submissions = " + qs +
   3004             "]";
   3005     }
   3006 
   3007     /**
   3008      * Possibly initiates an orderly shutdown in which previously
   3009      * submitted tasks are executed, but no new tasks will be
   3010      * accepted. Invocation has no effect on execution state if this
   3011      * is the {@link #commonPool()}, and no additional effect if
   3012      * already shut down.  Tasks that are in the process of being
   3013      * submitted concurrently during the course of this method may or
   3014      * may not be rejected.
   3015      *
   3016      * @throws SecurityException if a security manager exists and
   3017      *         the caller is not permitted to modify threads
   3018      *         because it does not hold {@link
   3019      *         java.lang.RuntimePermission}{@code ("modifyThread")}
   3020      */
   3021     public void shutdown() {
   3022         checkPermission();
   3023         tryTerminate(false, true);
   3024     }
   3025 
   3026     /**
   3027      * Possibly attempts to cancel and/or stop all tasks, and reject
   3028      * all subsequently submitted tasks.  Invocation has no effect on
   3029      * execution state if this is the {@link #commonPool()}, and no
   3030      * additional effect if already shut down. Otherwise, tasks that
   3031      * are in the process of being submitted or executed concurrently
   3032      * during the course of this method may or may not be
   3033      * rejected. This method cancels both existing and unexecuted
   3034      * tasks, in order to permit termination in the presence of task
   3035      * dependencies. So the method always returns an empty list
   3036      * (unlike the case for some other Executors).
   3037      *
   3038      * @return an empty list
   3039      */
   3040     public List<Runnable> shutdownNow() {
   3041         checkPermission();
   3042         tryTerminate(true, true);
   3043         return Collections.emptyList();
   3044     }
   3045 
   3046     /**
   3047      * Returns {@code true} if all tasks have completed following shut down.
   3048      *
   3049      * @return {@code true} if all tasks have completed following shut down
   3050      */
   3051     public boolean isTerminated() {
   3052         long c = ctl;
   3053         return ((c & STOP_BIT) != 0L &&
   3054                 (short)(c >>> TC_SHIFT) == -(config & SMASK));
   3055     }
   3056 
   3057     /**
   3058      * Returns {@code true} if the process of termination has
   3059      * commenced but not yet completed.  This method may be useful for
   3060      * debugging. A return of {@code true} reported a sufficient
   3061      * period after shutdown may indicate that submitted tasks have
   3062      * ignored or suppressed interruption, or are waiting for I/O,
   3063      * causing this executor not to properly terminate. (See the
   3064      * advisory notes for class {@link ForkJoinTask} stating that
   3065      * tasks should not normally entail blocking operations.  But if
   3066      * they do, they must abort them on interrupt.)
   3067      *
   3068      * @return {@code true} if terminating but not yet terminated
   3069      */
   3070     public boolean isTerminating() {
   3071         long c = ctl;
   3072         return ((c & STOP_BIT) != 0L &&
   3073                 (short)(c >>> TC_SHIFT) != -(config & SMASK));
   3074     }
   3075 
   3076     /**
   3077      * Returns {@code true} if this pool has been shut down.
   3078      *
   3079      * @return {@code true} if this pool has been shut down
   3080      */
   3081     public boolean isShutdown() {
   3082         return plock < 0;
   3083     }
   3084 
   3085     /**
   3086      * Blocks until all tasks have completed execution after a
   3087      * shutdown request, or the timeout occurs, or the current thread
   3088      * is interrupted, whichever happens first. Note that the {@link
   3089      * #commonPool()} never terminates until program shutdown so
   3090      * this method will always time out.
   3091      *
   3092      * @param timeout the maximum time to wait
   3093      * @param unit the time unit of the timeout argument
   3094      * @return {@code true} if this executor terminated and
   3095      *         {@code false} if the timeout elapsed before termination
   3096      * @throws InterruptedException if interrupted while waiting
   3097      */
   3098     public boolean awaitTermination(long timeout, TimeUnit unit)
   3099         throws InterruptedException {
   3100         long nanos = unit.toNanos(timeout);
   3101         if (isTerminated())
   3102             return true;
   3103         if (nanos <= 0L)
   3104             return false;
   3105         long deadline = System.nanoTime() + nanos;
   3106         synchronized (this) {
   3107             for (;;) {
   3108                 if (isTerminated())
   3109                     return true;
   3110                 if (nanos <= 0L)
   3111                     return false;
   3112                 long millis = TimeUnit.NANOSECONDS.toMillis(nanos);
   3113                 wait(millis > 0L ? millis : 1L);
   3114                 nanos = deadline - System.nanoTime();
   3115             }
   3116         }
   3117     }
   3118 
   3119     /**
   3120      * Interface for extending managed parallelism for tasks running
   3121      * in {@link ForkJoinPool}s.
   3122      *
   3123      * <p>A {@code ManagedBlocker} provides two methods.  Method
   3124      * {@code isReleasable} must return {@code true} if blocking is
   3125      * not necessary. Method {@code block} blocks the current thread
   3126      * if necessary (perhaps internally invoking {@code isReleasable}
   3127      * before actually blocking). These actions are performed by any
   3128      * thread invoking {@link ForkJoinPool#managedBlock}.  The
   3129      * unusual methods in this API accommodate synchronizers that may,
   3130      * but don't usually, block for long periods. Similarly, they
   3131      * allow more efficient internal handling of cases in which
   3132      * additional workers may be, but usually are not, needed to
   3133      * ensure sufficient parallelism.  Toward this end,
   3134      * implementations of method {@code isReleasable} must be amenable
   3135      * to repeated invocation.
   3136      *
   3137      * <p>For example, here is a ManagedBlocker based on a
   3138      * ReentrantLock:
   3139      *  <pre> {@code
   3140      * class ManagedLocker implements ManagedBlocker {
   3141      *   final ReentrantLock lock;
   3142      *   boolean hasLock = false;
   3143      *   ManagedLocker(ReentrantLock lock) { this.lock = lock; }
   3144      *   public boolean block() {
   3145      *     if (!hasLock)
   3146      *       lock.lock();
   3147      *     return true;
   3148      *   }
   3149      *   public boolean isReleasable() {
   3150      *     return hasLock || (hasLock = lock.tryLock());
   3151      *   }
   3152      * }}</pre>
   3153      *
   3154      * <p>Here is a class that possibly blocks waiting for an
   3155      * item on a given queue:
   3156      *  <pre> {@code
   3157      * class QueueTaker<E> implements ManagedBlocker {
   3158      *   final BlockingQueue<E> queue;
   3159      *   volatile E item = null;
   3160      *   QueueTaker(BlockingQueue<E> q) { this.queue = q; }
   3161      *   public boolean block() throws InterruptedException {
   3162      *     if (item == null)
   3163      *       item = queue.take();
   3164      *     return true;
   3165      *   }
   3166      *   public boolean isReleasable() {
   3167      *     return item != null || (item = queue.poll()) != null;
   3168      *   }
   3169      *   public E getItem() { // call after pool.managedBlock completes
   3170      *     return item;
   3171      *   }
   3172      * }}</pre>
   3173      */
   3174     public static interface ManagedBlocker {
   3175         /**
   3176          * Possibly blocks the current thread, for example waiting for
   3177          * a lock or condition.
   3178          *
   3179          * @return {@code true} if no additional blocking is necessary
   3180          * (i.e., if isReleasable would return true)
   3181          * @throws InterruptedException if interrupted while waiting
   3182          * (the method is not required to do so, but is allowed to)
   3183          */
   3184         boolean block() throws InterruptedException;
   3185 
   3186         /**
   3187          * Returns {@code true} if blocking is unnecessary.
   3188          */
   3189         boolean isReleasable();
   3190     }
   3191 
   3192     /**
   3193      * Blocks in accord with the given blocker.  If the current thread
   3194      * is a {@link ForkJoinWorkerThread}, this method possibly
   3195      * arranges for a spare thread to be activated if necessary to
   3196      * ensure sufficient parallelism while the current thread is blocked.
   3197      *
   3198      * <p>If the caller is not a {@link ForkJoinTask}, this method is
   3199      * behaviorally equivalent to
   3200      *  <pre> {@code
   3201      * while (!blocker.isReleasable())
   3202      *   if (blocker.block())
   3203      *     return;
   3204      * }</pre>
   3205      *
   3206      * If the caller is a {@code ForkJoinTask}, then the pool may
   3207      * first be expanded to ensure parallelism, and later adjusted.
   3208      *
   3209      * @param blocker the blocker
   3210      * @throws InterruptedException if blocker.block did so
   3211      */
   3212     public static void managedBlock(ManagedBlocker blocker)
   3213         throws InterruptedException {
   3214         Thread t = Thread.currentThread();
   3215         if (t instanceof ForkJoinWorkerThread) {
   3216             ForkJoinPool p = ((ForkJoinWorkerThread)t).pool;
   3217             while (!blocker.isReleasable()) { // variant of helpSignal
   3218                 WorkQueue[] ws; WorkQueue q; int m, u;
   3219                 if ((ws = p.workQueues) != null && (m = ws.length - 1) >= 0) {
   3220                     for (int i = 0; i <= m; ++i) {
   3221                         if (blocker.isReleasable())
   3222                             return;
   3223                         if ((q = ws[i]) != null && q.base - q.top < 0) {
   3224                             p.signalWork(q);
   3225                             if ((u = (int)(p.ctl >>> 32)) >= 0 ||
   3226                                 (u >> UAC_SHIFT) >= 0)
   3227                                 break;
   3228                         }
   3229                     }
   3230                 }
   3231                 if (p.tryCompensate()) {
   3232                     try {
   3233                         do {} while (!blocker.isReleasable() &&
   3234                                      !blocker.block());
   3235                     } finally {
   3236                         p.incrementActiveCount();
   3237                     }
   3238                     break;
   3239                 }
   3240             }
   3241         }
   3242         else {
   3243             do {} while (!blocker.isReleasable() &&
   3244                          !blocker.block());
   3245         }
   3246     }
   3247 
   3248     // AbstractExecutorService overrides.  These rely on undocumented
   3249     // fact that ForkJoinTask.adapt returns ForkJoinTasks that also
   3250     // implement RunnableFuture.
   3251 
   3252     protected <T> RunnableFuture<T> newTaskFor(Runnable runnable, T value) {
   3253         return new ForkJoinTask.AdaptedRunnable<T>(runnable, value);
   3254     }
   3255 
   3256     protected <T> RunnableFuture<T> newTaskFor(Callable<T> callable) {
   3257         return new ForkJoinTask.AdaptedCallable<T>(callable);
   3258     }
   3259 
   3260     // Unsafe mechanics
   3261     private static final sun.misc.Unsafe U;
   3262     private static final long CTL;
   3263     private static final long PARKBLOCKER;
   3264     private static final int ABASE;
   3265     private static final int ASHIFT;
   3266     private static final long STEALCOUNT;
   3267     private static final long PLOCK;
   3268     private static final long INDEXSEED;
   3269     private static final long QLOCK;
   3270 
   3271     static {
   3272         // initialize field offsets for CAS etc
   3273         try {
   3274             U = sun.misc.Unsafe.getUnsafe();
   3275             Class<?> k = ForkJoinPool.class;
   3276             CTL = U.objectFieldOffset
   3277                 (k.getDeclaredField("ctl"));
   3278             STEALCOUNT = U.objectFieldOffset
   3279                 (k.getDeclaredField("stealCount"));
   3280             PLOCK = U.objectFieldOffset
   3281                 (k.getDeclaredField("plock"));
   3282             INDEXSEED = U.objectFieldOffset
   3283                 (k.getDeclaredField("indexSeed"));
   3284             Class<?> tk = Thread.class;
   3285             PARKBLOCKER = U.objectFieldOffset
   3286                 (tk.getDeclaredField("parkBlocker"));
   3287             Class<?> wk = WorkQueue.class;
   3288             QLOCK = U.objectFieldOffset
   3289                 (wk.getDeclaredField("qlock"));
   3290             Class<?> ak = ForkJoinTask[].class;
   3291             ABASE = U.arrayBaseOffset(ak);
   3292             int scale = U.arrayIndexScale(ak);
   3293             if ((scale & (scale - 1)) != 0)
   3294                 throw new Error("data type scale not a power of two");
   3295             ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
   3296         } catch (Exception e) {
   3297             throw new Error(e);
   3298         }
   3299 
   3300         submitters = new ThreadLocal<Submitter>();
   3301         ForkJoinWorkerThreadFactory fac = defaultForkJoinWorkerThreadFactory =
   3302             new DefaultForkJoinWorkerThreadFactory();
   3303         modifyThreadPermission = new RuntimePermission("modifyThread");
   3304 
   3305         /*
   3306          * Establish common pool parameters.  For extra caution,
   3307          * computations to set up common pool state are here; the
   3308          * constructor just assigns these values to fields.
   3309          */
   3310 
   3311         int par = 0;
   3312         Thread.UncaughtExceptionHandler handler = null;
   3313         try {  // TBD: limit or report ignored exceptions?
   3314             String pp = System.getProperty
   3315                 ("java.util.concurrent.ForkJoinPool.common.parallelism");
   3316             String hp = System.getProperty
   3317                 ("java.util.concurrent.ForkJoinPool.common.exceptionHandler");
   3318             String fp = System.getProperty
   3319                 ("java.util.concurrent.ForkJoinPool.common.threadFactory");
   3320             if (fp != null)
   3321                 fac = ((ForkJoinWorkerThreadFactory)ClassLoader.
   3322                        getSystemClassLoader().loadClass(fp).newInstance());
   3323             if (hp != null)
   3324                 handler = ((Thread.UncaughtExceptionHandler)ClassLoader.
   3325                            getSystemClassLoader().loadClass(hp).newInstance());
   3326             if (pp != null)
   3327                 par = Integer.parseInt(pp);
   3328         } catch (Exception ignore) {
   3329         }
   3330 
   3331         if (par <= 0)
   3332             par = Runtime.getRuntime().availableProcessors();
   3333         if (par > MAX_CAP)
   3334             par = MAX_CAP;
   3335         commonPoolParallelism = par;
   3336         long np = (long)(-par); // precompute initial ctl value
   3337         long ct = ((np << AC_SHIFT) & AC_MASK) | ((np << TC_SHIFT) & TC_MASK);
   3338 
   3339         commonPool = new ForkJoinPool(par, ct, fac, handler);
   3340     }
   3341 
   3342 }
   3343