1 /*

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

     3  *

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

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

     6  * published by the Free Software Foundation.  Oracle designates this

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

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

     9  *

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

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

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

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

    14  * accompanied this code).

    15  *

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

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

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

    19  *

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

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

    22  * questions.

    23  */

    24 

    25 /*

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

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

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

    29  * file:

    30  *

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

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

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

    34  */

    35 

    36 package java.util.concurrent;

    37 

    38 import java.lang.Thread.UncaughtExceptionHandler;

    39 import java.util.ArrayList;

    40 import java.util.Arrays;

    41 import java.util.Collection;

    42 import java.util.Collections;

    43 import java.util.List;

    44 import java.util.concurrent.AbstractExecutorService;

    45 import java.util.concurrent.Callable;

    46 import java.util.concurrent.ExecutorService;

    47 import java.util.concurrent.Future;

    48 import java.util.concurrent.RejectedExecutionException;

    49 import java.util.concurrent.RunnableFuture;

    50 import java.util.concurrent.ThreadLocalRandom;

    51 import java.util.concurrent.TimeUnit;

    52 import java.security.AccessControlContext;

    53 import java.security.ProtectionDomain;

    54 import java.security.Permissions;

    55 

    56 /**

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

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

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

    60  * monitoring operations.

    61  *

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

    63  * ExecutorService} mainly by virtue of employing

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

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

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

    67  * enables efficient processing when most tasks spawn other subtasks

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

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

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

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

    72  * tasks that are never joined.

    73  *

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

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

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

    77  * pool normally reduces resource usage (its threads are slowly

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

    79  * use).

    80  *

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

    82  * ForkJoinPool} may be constructed with a given target parallelism

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

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

    85  * dynamically adding, suspending, or resuming internal worker

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

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

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

    89  * ManagedBlocker} interface enables extension of the kinds of

    90  * synchronization accommodated.

    91  *

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

    93  * class provides status check methods (for example

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

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

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

    97  * convenient form for informal monitoring.

    98  *

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

   100  * main task execution methods summarized in the following table.

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

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

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

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

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

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

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

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

   109  * there is little difference among choice of methods.

   110  *

   111  * <table BORDER CELLPADDING=3 CELLSPACING=1>

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

   113  *  <tr>

   114  *    <td></td>

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

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

   117  *  </tr>

   118  *  <tr>

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

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

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

   122  *  </tr>

   123  *  <tr>

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

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

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

   127  *  </tr>

   128  *  <tr>

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

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

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

   132  *  </tr>

   133  * </table>

   134  *

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

   136  * parameters, but these may be controlled by setting three

   137  * {@linkplain System#getProperty system properties}:

   138  * <ul>

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

   140  * - the parallelism level, a non-negative integer

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

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

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

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

   145  * </ul>

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

   147  * specified, then the default pool uses a factory supplying

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

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

   150  * Upon any error in establishing these settings, default parameters

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

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

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

   154  * cause unjoined tasks to never be executed.

   155  *

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

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

   158  * pools with greater than the maximum number result in

   159  * {@code IllegalArgumentException}.

   160  *

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

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

   163  * or internal resources have been exhausted.

   164  *

   165  * @since 1.7

   166  * @author Doug Lea

   167  */

   168 @sun.misc.Contended

   169 public class ForkJoinPool extends AbstractExecutorService {

   170 

   171     /*

   172      * Implementation Overview

   173      *

   174      * This class and its nested classes provide the main

   175      * functionality and control for a set of worker threads:

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

   177      * Workers take these tasks and typically split them into subtasks

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

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

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

   181      * tasks in other queues.

   182      *

   183      * WorkQueues

   184      * ==========

   185      *

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

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

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

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

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

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

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

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

   194      * Multiprocessor programming", chapter 16 describing these in

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

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

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

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

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

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

   201      * See also "Correct and Efficient Work-Stealing for Weak Memory

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

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

   204      * analysis of memory ordering (atomic, volatile etc) issues.  The

   205      * main differences ultimately stem from GC requirements that we

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

   207      * footprint as possible even in programs generating huge numbers

   208      * of tasks. To accomplish this, we shift the CAS arbitrating pop

   209      * vs poll (steal) from being on the indices ("base" and "top") to

   210      * the slots themselves.  So, both a successful pop and poll

   211      * mainly entail a CAS of a slot from non-null to null.  Because

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

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

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

   215      * indices must still be ordered in a way that guarantees that top

   216      * == base means the queue is empty, but otherwise may err on the

   217      * side of possibly making the queue appear nonempty when a push,

   218      * pop, or poll have not fully committed. Note that this means

   219      * that the poll operation, considered individually, is not

   220      * wait-free. One thief cannot successfully continue until another

   221      * in-progress one (or, if previously empty, a push) completes.

   222      * However, in the aggregate, we ensure at least probabilistic

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

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

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

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

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

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

   229      * consider alternative actions, rather than method poll.)

   230      *

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

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

   233      * poll rather than pop.  This can be useful in message-passing

   234      * frameworks in which tasks are never joined.  However neither

   235      * mode considers affinities, loads, cache localities, etc, so

   236      * rarely provide the best possible performance on a given

   237      * machine, but portably provide good throughput by averaging over

   238      * these factors.  (Further, even if we did try to use such

   239      * information, we do not usually have a basis for exploiting it.

   240      * For example, some sets of tasks profit from cache affinities,

   241      * but others are harmed by cache pollution effects.)

   242      *

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

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

   245      * for work-stealing (this would contaminate lifo/fifo

   246      * processing). Instead, we randomly associate submission queues

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

   248      * ThreadLocalRandom probe value serves as a hash code for

   249      * choosing existing queues, and may be randomly repositioned upon

   250      * contention with other submitters.  In essence, submitters act

   251      * like workers except that they are restricted to executing local

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

   253      * others with the same root task).  However, because most

   254      * shared/external queue operations are more expensive than

   255      * internal, and because, at steady state, external submitters

   256      * will compete for CPU with workers, ForkJoinTask.join and

   257      * related methods disable them from repeatedly helping to process

   258      * tasks if all workers are active.  Insertion of tasks in shared

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

   260      * resizing) but we use only a simple spinlock (using bits in

   261      * field qlock), because submitters encountering a busy queue move

   262      * on to try or create other queues -- they block only when

   263      * creating and registering new queues.

   264      *

   265      * Management

   266      * ==========

   267      *

   268      * The main throughput advantages of work-stealing stem from

   269      * decentralized control -- workers mostly take tasks from

   270      * themselves or each other. We cannot negate this in the

   271      * implementation of other management responsibilities. The main

   272      * tactic for avoiding bottlenecks is packing nearly all

   273      * essentially atomic control state into two volatile variables

   274      * that are by far most often read (not written) as status and

   275      * consistency checks.

   276      *

   277      * Field "ctl" contains 64 bits holding all the information needed

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

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

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

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

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

   283      * fields.

   284      *

   285      * Field "plock" is a form of sequence lock with a saturating

   286      * shutdown bit (similarly for per-queue "qlocks"), mainly

   287      * protecting updates to the workQueues array, as well as to

   288      * enable shutdown.  When used as a lock, it is normally only very

   289      * briefly held, so is nearly always available after at most a

   290      * brief spin, but we use a monitor-based backup strategy to

   291      * block when needed.

   292      *

   293      * Recording WorkQueues.  WorkQueues are recorded in the

   294      * "workQueues" array that is created upon first use and expanded

   295      * if necessary.  Updates to the array while recording new workers

   296      * and unrecording terminated ones are protected from each other

   297      * by a lock but the array is otherwise concurrently readable, and

   298      * accessed directly.  To simplify index-based operations, the

   299      * array size is always a power of two, and all readers must

   300      * tolerate null slots. Worker queues are at odd indices. Shared

   301      * (submission) queues are at even indices, up to a maximum of 64

   302      * slots, to limit growth even if array needs to expand to add

   303      * more workers. Grouping them together in this way simplifies and

   304      * speeds up task scanning.

   305      *

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

   307      * submissions, replacement of terminated workers, and/or

   308      * compensation for blocked workers. However, all other support

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

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

   311      * accesses to workQueues are via indices into the workQueues

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

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

   314      * a weak reference mechanism. Thus for example the wait queue

   315      * field of ctl stores indices, not references.  Access to the

   316      * workQueues in associated methods (for example signalWork) must

   317      * both index-check and null-check the IDs. All such accesses

   318      * ignore bad IDs by returning out early from what they are doing,

   319      * since this can only be associated with termination, in which

   320      * case it is OK to give up.  All uses of the workQueues array

   321      * also check that it is non-null (even if previously

   322      * non-null). This allows nulling during termination, which is

   323      * currently not necessary, but remains an option for

   324      * resource-revocation-based shutdown schemes. It also helps

   325      * reduce JIT issuance of uncommon-trap code, which tends to

   326      * unnecessarily complicate control flow in some methods.

   327      *

   328      * Event Queuing. Unlike HPC work-stealing frameworks, we cannot

   329      * let workers spin indefinitely scanning for tasks when none can

   330      * be found immediately, and we cannot start/resume workers unless

   331      * there appear to be tasks available.  On the other hand, we must

   332      * quickly prod them into action when new tasks are submitted or

   333      * generated. In many usages, ramp-up time to activate workers is

   334      * the main limiting factor in overall performance (this is

   335      * compounded at program start-up by JIT compilation and

   336      * allocation). So we try to streamline this as much as possible.

   337      * We park/unpark workers after placing in an event wait queue

   338      * when they cannot find work. This "queue" is actually a simple

   339      * Treiber stack, headed by the "id" field of ctl, plus a 15bit

   340      * counter value (that reflects the number of times a worker has

   341      * been inactivated) to avoid ABA effects (we need only as many

   342      * version numbers as worker threads). Successors are held in

   343      * field WorkQueue.nextWait.  Queuing deals with several intrinsic

   344      * races, mainly that a task-producing thread can miss seeing (and

   345      * signalling) another thread that gave up looking for work but

   346      * has not yet entered the wait queue. We solve this by requiring

   347      * a full sweep of all workers (via repeated calls to method

   348      * scan()) both before and after a newly waiting worker is added

   349      * to the wait queue.  Because enqueued workers may actually be

   350      * rescanning rather than waiting, we set and clear the "parker"

   351      * field of WorkQueues to reduce unnecessary calls to unpark.

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

   353      * Note the unusual conventions about Thread.interrupts

   354      * surrounding parking and other blocking: Because interrupts are

   355      * used solely to alert threads to check termination, which is

   356      * checked anyway upon blocking, we clear status (using

   357      * Thread.interrupted) before any call to park, so that park does

   358      * not immediately return due to status being set via some other

   359      * unrelated call to interrupt in user code.

   360      *

   361      * Signalling.  We create or wake up workers only when there

   362      * appears to be at least one task they might be able to find and

   363      * execute.  When a submission is added or another worker adds a

   364      * task to a queue that has fewer than two tasks, they signal

   365      * waiting workers (or trigger creation of new ones if fewer than

   366      * the given parallelism level -- signalWork).  These primary

   367      * signals are buttressed by others whenever other threads remove

   368      * a task from a queue and notice that there are other tasks there

   369      * as well.  So in general, pools will be over-signalled. On most

   370      * platforms, signalling (unpark) overhead time is noticeably

   371      * long, and the time between signalling a thread and it actually

   372      * making progress can be very noticeably long, so it is worth

   373      * offloading these delays from critical paths as much as

   374      * possible. Additionally, workers spin-down gradually, by staying

   375      * alive so long as they see the ctl state changing.  Similar

   376      * stability-sensing techniques are also used before blocking in

   377      * awaitJoin and helpComplete.

   378      *

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

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

   381      * time out and terminate if the pool has remained quiescent for a

   382      * given period -- a short period if there are more threads than

   383      * parallelism, longer as the number of threads decreases. This

   384      * will slowly propagate, eventually terminating all workers after

   385      * periods of non-use.

   386      *

   387      * Shutdown and Termination. A call to shutdownNow atomically sets

   388      * a plock bit and then (non-atomically) sets each worker's

   389      * qlock status, cancels all unprocessed tasks, and wakes up

   390      * all waiting workers.  Detecting whether termination should

   391      * commence after a non-abrupt shutdown() call requires more work

   392      * and bookkeeping. We need consensus about quiescence (i.e., that

   393      * there is no more work). The active count provides a primary

   394      * indication but non-abrupt shutdown still requires a rechecking

   395      * scan for any workers that are inactive but not queued.

   396      *

   397      * Joining Tasks

   398      * =============

   399      *

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

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

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

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

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

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

   406      * possible is not necessarily a good idea since we sometimes need

   407      * both an unblocked task and its continuation to progress.

   408      * Instead we combine two tactics:

   409      *

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

   411      *      would be running if the steal had not occurred.

   412      *

   413      *   Compensating: Unless there are already enough live threads,

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

   415      *      thread to compensate for blocked joiners until they unblock.

   416      *

   417      * A third form (implemented in tryRemoveAndExec) amounts to

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

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

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

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

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

   423      * typically worthwhile).

   424      *

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

   426      * only on compensation in method awaitBlocker.

   427      *

   428      * The algorithm in tryHelpStealer entails a form of "linear"

   429      * helping: Each worker records (in field currentSteal) the most

   430      * recent task it stole from some other worker. Plus, it records

   431      * (in field currentJoin) the task it is currently actively

   432      * joining. Method tryHelpStealer uses these markers to try to

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

   434      * it) that could hasten completion of the actively joined task.

   435      * In essence, the joiner executes a task that would be on its own

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

   437      * be seen as a conservative variant of the approach in Wagner &

   438      * Calder "Leapfrogging: a portable technique for implementing

   439      * efficient futures" SIGPLAN Notices, 1993

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   455      * to find work (see MAX_HELP) and fall back to suspending the

   456      * worker and if necessary replacing it with another.

   457      *

   458      * Helping actions for CountedCompleters are much simpler: Method

   459      * helpComplete can take and execute any task with the same root

   460      * as the task being waited on. However, this still entails some

   461      * traversal of completer chains, so is less efficient than using

   462      * CountedCompleters without explicit joins.

   463      *

   464      * It is impossible to keep exactly the target parallelism number

   465      * of threads running at any given time.  Determining the

   466      * existence of conservatively safe helping targets, the

   467      * availability of already-created spares, and the apparent need

   468      * to create new spares are all racy, so we rely on multiple

   469      * retries of each.  Compensation in the apparent absence of

   470      * helping opportunities is challenging to control on JVMs, where

   471      * GC and other activities can stall progress of tasks that in

   472      * turn stall out many other dependent tasks, without us being

   473      * able to determine whether they will ever require compensation.

   474      * Even though work-stealing otherwise encounters little

   475      * degradation in the presence of more threads than cores,

   476      * aggressively adding new threads in such cases entails risk of

   477      * unwanted positive feedback control loops in which more threads

   478      * cause more dependent stalls (as well as delayed progress of

   479      * unblocked threads to the point that we know they are available)

   480      * leading to more situations requiring more threads, and so

   481      * on. This aspect of control can be seen as an (analytically

   482      * intractable) game with an opponent that may choose the worst

   483      * (for us) active thread to stall at any time.  We take several

   484      * precautions to bound losses (and thus bound gains), mainly in

   485      * methods tryCompensate and awaitJoin.

   486      *

   487      * Common Pool

   488      * ===========

   489      *

   490      * The static common pool always exists after static

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

   492      * never be used, we minimize initial construction overhead and

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

   494      * allocation. Most bootstrapping occurs within method

   495      * fullExternalPush during the first submission to the pool.

   496      *

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

   498      * perform subtask processing (see externalHelpJoin and related

   499      * methods).  This caller-helps policy makes it sensible to set

   500      * common pool parallelism level to one (or more) less than the

   501      * total number of available cores, or even zero for pure

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

   503      * submissions are to the common pool -- if not, externalHelpJoin

   504      * returns quickly (at the most helping to signal some common pool

   505      * workers). These submitters would otherwise be blocked waiting

   506      * for completion, so the extra effort (with liberally sprinkled

   507      * task status checks) in inapplicable cases amounts to an odd

   508      * form of limited spin-wait before blocking in ForkJoinTask.join.

   509      *

   510      * As a more appropriate default in managed environments, unless

   511      * overridden by system properties, we use workers of subclass

   512      * InnocuousForkJoinWorkerThread when there is a SecurityManager

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

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

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

   516      * associated mechanics (mainly in ForkJoinWorkerThread) may be

   517      * JVM-dependent and must access particular Thread class fields to

   518      * achieve this effect.

   519      *

   520      * Style notes

   521      * ===========

   522      *

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

   524      * ForkJoinPool, ForkJoinWorkerThread, and ForkJoinTask.  The

   525      * fields of WorkQueue maintain data structures managed by

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

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

   528      * representations will need to be accompanied by algorithmic

   529      * changes anyway. Several methods intrinsically sprawl because

   530      * they must accumulate sets of consistent reads of volatiles held

   531      * in local variables.  Methods signalWork() and scan() are the

   532      * main bottlenecks, so are especially heavily

   533      * micro-optimized/mangled.  There are lots of inline assignments

   534      * (of form "while ((local = field) != 0)") which are usually the

   535      * simplest way to ensure the required read orderings (which are

   536      * sometimes critical). This leads to a "C"-like style of listing

   537      * declarations of these locals at the heads of methods or blocks.

   538      * There are several occurrences of the unusual "do {} while

   539      * (!cas...)"  which is the simplest way to force an update of a

   540      * CAS'ed variable. There are also other coding oddities (including

   541      * several unnecessary-looking hoisted null checks) that help

   542      * some methods perform reasonably even when interpreted (not

   543      * compiled).

   544      *

   545      * The order of declarations in this file is:

   546      * (1) Static utility functions

   547      * (2) Nested (static) classes

   548      * (3) Static fields

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

   550      * (5) Internal control methods

   551      * (6) Callbacks and other support for ForkJoinTask methods

   552      * (7) Exported methods

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

   554      */

   555 

   556     // Static utilities

   557 

   558     /**

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

   560      * permission to modify threads.

   561      */

   562     private static void checkPermission() {

   563         SecurityManager security = System.getSecurityManager();

   564         if (security != null)

   565             security.checkPermission(modifyThreadPermission);

   566     }

   567 

   568     // Nested classes

   569 

   570     /**

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

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

   573      * for {@code ForkJoinWorkerThread} subclasses that extend base

   574      * functionality or initialize threads with different contexts.

   575      */

   576     public static interface ForkJoinWorkerThreadFactory {

   577         /**

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

   579          *

   580          * @param pool the pool this thread works in

   581          * @return the new worker thread

   582          * @throws NullPointerException if the pool is null

   583          */

   584         public ForkJoinWorkerThread newThread(ForkJoinPool pool);

   585     }

   586 

   587     /**

   588      * Default ForkJoinWorkerThreadFactory implementation; creates a

   589      * new ForkJoinWorkerThread.

   590      */

   591     static final class DefaultForkJoinWorkerThreadFactory

   592         implements ForkJoinWorkerThreadFactory {

   593         public final ForkJoinWorkerThread newThread(ForkJoinPool pool) {

   594             return new ForkJoinWorkerThread(pool);

   595         }

   596     }

   597 

   598     /**

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

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

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

   602      * actually do anything beyond having a unique identity.

   603      */

   604     static final class EmptyTask extends ForkJoinTask<Void> {

   605         private static final long serialVersionUID = -7721805057305804111L;

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

   607         public final Void getRawResult() { return null; }

   608         public final void setRawResult(Void x) {}

   609         public final boolean exec() { return true; }

   610     }

   611 

   612     /**

   613      * Queues supporting work-stealing as well as external task

   614      * submission. See above for main rationale and algorithms.

   615      * Implementation relies heavily on "Unsafe" intrinsics

   616      * and selective use of "volatile":

   617      *

   618      * Field "base" is the index (mod array.length) of the least valid

   619      * queue slot, which is always the next position to steal (poll)

   620      * from if nonempty. Reads and writes require volatile orderings

   621      * but not CAS, because updates are only performed after slot

   622      * CASes.

   623      *

   624      * Field "top" is the index (mod array.length) of the next queue

   625      * slot to push to or pop from. It is written only by owner thread

   626      * for push, or under lock for external/shared push, and accessed

   627      * by other threads only after reading (volatile) base.  Both top

   628      * and base are allowed to wrap around on overflow, but (top -

   629      * base) (or more commonly -(base - top) to force volatile read of

   630      * base before top) still estimates size. The lock ("qlock") is

   631      * forced to -1 on termination, causing all further lock attempts

   632      * to fail. (Note: we don't need CAS for termination state because

   633      * upon pool shutdown, all shared-queues will stop being used

   634      * anyway.)  Nearly all lock bodies are set up so that exceptions

   635      * within lock bodies are "impossible" (modulo JVM errors that

   636      * would cause failure anyway.)

   637      *

   638      * The array slots are read and written using the emulation of

   639      * volatiles/atomics provided by Unsafe. Insertions must in

   640      * general use putOrderedObject as a form of releasing store to

   641      * ensure that all writes to the task object are ordered before

   642      * its publication in the queue.  All removals entail a CAS to

   643      * null.  The array is always a power of two. To ensure safety of

   644      * Unsafe array operations, all accesses perform explicit null

   645      * checks and implicit bounds checks via power-of-two masking.

   646      *

   647      * In addition to basic queuing support, this class contains

   648      * fields described elsewhere to control execution. It turns out

   649      * to work better memory-layout-wise to include them in this class

   650      * rather than a separate class.

   651      *

   652      * Performance on most platforms is very sensitive to placement of

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

   654      * do not want multiple WorkQueue instances or multiple queue

   655      * arrays sharing cache lines. (It would be best for queue objects

   656      * and their arrays to share, but there is nothing available to

   657      * help arrange that). The @Contended annotation alerts JVMs to

   658      * try to keep instances apart.

   659      */

   660     @sun.misc.Contended

   661     static final class WorkQueue {

   662         /**

   663          * Capacity of work-stealing queue array upon initialization.

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

   665          * reduce or eliminate cacheline sharing among queues.

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

   667          * the fact that JVMs often place arrays in locations that

   668          * share GC bookkeeping (especially cardmarks) such that

   669          * per-write accesses encounter serious memory contention.

   670          */

   671         static final int INITIAL_QUEUE_CAPACITY = 1 << 13;

   672 

   673         /**

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

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

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

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

   678          * programs before saturating systems.

   679          */

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

   681 

   682         volatile int eventCount;   // encoded inactivation count; < 0 if inactive

   683         int nextWait;              // encoded record of next event waiter

   684         int nsteals;               // number of steals

   685         int hint;                  // steal index hint

   686         short poolIndex;           // index of this queue in pool

   687         final short mode;          // 0: lifo, > 0: fifo, < 0: shared

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

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

   690         int top;                   // index of next slot for push

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

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

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

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

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

   696         ForkJoinTask<?> currentSteal; // current non-local task being executed

   697 

   698         WorkQueue(ForkJoinPool pool, ForkJoinWorkerThread owner, int mode,

   699                   int seed) {

   700             this.pool = pool;

   701             this.owner = owner;

   702             this.mode = (short)mode;

   703             this.hint = seed; // store initial seed for runWorker

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

   705             base = top = INITIAL_QUEUE_CAPACITY >>> 1;

   706         }

   707 

   708         /**

   709          * Returns the approximate number of tasks in the queue.

   710          */

   711         final int queueSize() {

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

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

   714         }

   715 

   716         /**

   717          * Provides a more accurate estimate of whether this queue has

   718          * any tasks than does queueSize, by checking whether a

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

   720          */

   721         final boolean isEmpty() {

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

   723             int n = base - (s = top);

   724             return (n >= 0 ||

   725                     (n == -1 &&

   726                      ((a = array) == null ||

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

   728                       U.getObject

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

   730         }

   731 

   732         /**

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

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

   735          *

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

   737          * @throws RejectedExecutionException if array cannot be resized

   738          */

   739         final void push(ForkJoinTask<?> task) {

   740             ForkJoinTask<?>[] a; ForkJoinPool p;

   741             int s = top, n;

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

   743                 int m = a.length - 1;

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

   745                 if ((n = (top = s + 1) - base) <= 2)

   746                     (p = pool).signalWork(p.workQueues, this);

   747                 else if (n >= m)

   748                     growArray();

   749             }

   750         }

   751 

   752         /**

   753          * Initializes or doubles the capacity of array. Call either

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

   755          * top, to move while resizings are in progress.

   756          */

   757         final ForkJoinTask<?>[] growArray() {

   758             ForkJoinTask<?>[] oldA = array;

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

   760             if (size > MAXIMUM_QUEUE_CAPACITY)

   761                 throw new RejectedExecutionException("Queue capacity exceeded");

   762             int oldMask, t, b;

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

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

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

   766                 int mask = size - 1;

   767                 do {

   768                     ForkJoinTask<?> x;

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

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

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

   772                     if (x != null &&

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

   774                         U.putObjectVolatile(a, j, x);

   775                 } while (++b != t);

   776             }

   777             return a;

   778         }

   779 

   780         /**

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

   782          * by owner in unshared queues.

   783          */

   784         final ForkJoinTask<?> pop() {

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

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

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

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

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

   790                         break;

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

   792                         top = s;

   793                         return t;

   794                     }

   795                 }

   796             }

   797             return null;

   798         }

   799 

   800         /**

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

   802          * can be claimed without contention. Specialized versions

   803          * appear in ForkJoinPool methods scan and tryHelpStealer.

   804          */

   805         final ForkJoinTask<?> pollAt(int b) {

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

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

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

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

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

   811                     U.putOrderedInt(this, QBASE, b + 1);

   812                     return t;

   813                 }

   814             }

   815             return null;

   816         }

   817 

   818         /**

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

   820          */

   821         final ForkJoinTask<?> poll() {

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

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

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

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

   826                 if (t != null) {

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

   828                         U.putOrderedInt(this, QBASE, b + 1);

   829                         return t;

   830                     }

   831                 }

   832                 else if (base == b) {

   833                     if (b + 1 == top)

   834                         break;

   835                     Thread.yield(); // wait for lagging update (very rare)

   836                 }

   837             }

   838             return null;

   839         }

   840 

   841         /**

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

   843          */

   844         final ForkJoinTask<?> nextLocalTask() {

   845             return mode == 0 ? pop() : poll();

   846         }

   847 

   848         /**

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

   850          */

   851         final ForkJoinTask<?> peek() {

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

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

   854                 return null;

   855             int i = mode == 0 ? top - 1 : base;

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

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

   858         }

   859 

   860         /**

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

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

   863          */

   864         final boolean tryUnpush(ForkJoinTask<?> t) {

   865             ForkJoinTask<?>[] a; int s;

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

   867                 U.compareAndSwapObject

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

   869                 top = s;

   870                 return true;

   871             }

   872             return false;

   873         }

   874 

   875         /**

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

   877          */

   878         final void cancelAll() {

   879             ForkJoinTask.cancelIgnoringExceptions(currentJoin);

   880             ForkJoinTask.cancelIgnoringExceptions(currentSteal);

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

   882                 ForkJoinTask.cancelIgnoringExceptions(t);

   883         }

   884 

   885         // Specialized execution methods

   886 

   887         /**

   888          * Polls and runs tasks until empty.

   889          */

   890         final void pollAndExecAll() {

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

   892                 t.doExec();

   893         }

   894 

   895         /**

   896          * Executes a top-level task and any local tasks remaining

   897          * after execution.

   898          */

   899         final void runTask(ForkJoinTask<?> task) {

   900             if ((currentSteal = task) != null) {

   901                 ForkJoinWorkerThread thread;

   902                 task.doExec();

   903                 ForkJoinTask<?>[] a = array;

   904                 int md = mode;

   905                 ++nsteals;

   906                 currentSteal = null;

   907                 if (md != 0)

   908                     pollAndExecAll();

   909                 else if (a != null) {

   910                     int s, m = a.length - 1;

   911                     ForkJoinTask<?> t;

   912                     while ((s = top - 1) - base >= 0 &&

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

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

   915                         top = s;

   916                         t.doExec();

   917                     }

   918                 }

   919                 if ((thread = owner) != null) // no need to do in finally clause

   920                     thread.afterTopLevelExec();

   921             }

   922         }

   923 

   924         /**

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

   926          * or any other cancelled task. Returns (true) on any CAS

   927          * or consistency check failure so caller can retry.

   928          *

   929          * @return false if no progress can be made, else true

   930          */

   931         final boolean tryRemoveAndExec(ForkJoinTask<?> task) {

   932             boolean stat;

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

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

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

   936                 boolean removed = false, empty = true;

   937                 stat = true;

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

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

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

   941                     if (t == null)                    // inconsistent length

   942                         break;

   943                     else if (t == task) {

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

   945                             if (!U.compareAndSwapObject(a, j, task, null))

   946                                 break;

   947                             top = s;

   948                             removed = true;

   949                         }

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

   951                             removed = U.compareAndSwapObject(a, j, task,

   952                                                              new EmptyTask());

   953                         break;

   954                     }

   955                     else if (t.status >= 0)

   956                         empty = false;

   957                     else if (s + 1 == top) {          // pop and throw away

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

   959                             top = s;

   960                         break;

   961                     }

   962                     if (--n == 0) {

   963                         if (!empty && base == b)

   964                             stat = false;

   965                         break;

   966                     }

   967                 }

   968                 if (removed)

   969                     task.doExec();

   970             }

   971             else

   972                 stat = false;

   973             return stat;

   974         }

   975 

   976         /**

   977          * Tries to poll for and execute the given task or any other

   978          * task in its CountedCompleter computation.

   979          */

   980         final boolean pollAndExecCC(CountedCompleter<?> root) {

   981             ForkJoinTask<?>[] a; int b; Object o; CountedCompleter<?> t, r;

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

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

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

   985                     return true; // retry

   986                 if (o instanceof CountedCompleter) {

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

   988                         if (r == root) {

   989                             if (base == b &&

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

   991                                 U.putOrderedInt(this, QBASE, b + 1);

   992                                 t.doExec();

   993                             }

   994                             return true;

   995                         }

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

   997                             break; // not part of root computation

   998                     }

   999                 }

  1000             }

  1001             return false;

  1002         }

  1003 

  1004         /**

  1005          * Tries to pop and execute the given task or any other task

  1006          * in its CountedCompleter computation.

  1007          */

  1008         final boolean externalPopAndExecCC(CountedCompleter<?> root) {

  1009             ForkJoinTask<?>[] a; int s; Object o; CountedCompleter<?> t, r;

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

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

  1012                 if ((o = U.getObject(a, j)) instanceof CountedCompleter) {

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

  1014                         if (r == root) {

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

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

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

  1018                                     top = s - 1;

  1019                                     qlock = 0;

  1020                                     t.doExec();

  1021                                 }

  1022                                 else

  1023                                     qlock = 0;

  1024                             }

  1025                             return true;

  1026                         }

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

  1028                             break;

  1029                     }

  1030                 }

  1031             }

  1032             return false;

  1033         }

  1034 

  1035         /**

  1036          * Internal version

  1037          */

  1038         final boolean internalPopAndExecCC(CountedCompleter<?> root) {

  1039             ForkJoinTask<?>[] a; int s; Object o; CountedCompleter<?> t, r;

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

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

  1042                 if ((o = U.getObject(a, j)) instanceof CountedCompleter) {

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

  1044                         if (r == root) {

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

  1046                                 top = s - 1;

  1047                                 t.doExec();

  1048                             }

  1049                             return true;

  1050                         }

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

  1052                             break;

  1053                     }

  1054                 }

  1055             }

  1056             return false;

  1057         }

  1058 

  1059         /**

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

  1061          */

  1062         final boolean isApparentlyUnblocked() {

  1063             Thread wt; Thread.State s;

  1064             return (eventCount >= 0 &&

  1065                     (wt = owner) != null &&

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

  1067                     s != Thread.State.WAITING &&

  1068                     s != Thread.State.TIMED_WAITING);

  1069         }

  1070 

  1071         // Unsafe mechanics

  1072         private static final sun.misc.Unsafe U;

  1073         private static final long QBASE;

  1074         private static final long QLOCK;

  1075         private static final int ABASE;

  1076         private static final int ASHIFT;

  1077         static {

  1078             try {

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

  1080                 Class<?> k = WorkQueue.class;

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

  1082                 QBASE = U.objectFieldOffset

  1083                     (k.getDeclaredField("base"));

  1084                 QLOCK = U.objectFieldOffset

  1085                     (k.getDeclaredField("qlock"));

  1086                 ABASE = U.arrayBaseOffset(ak);

  1087                 int scale = U.arrayIndexScale(ak);

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

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

  1090                 ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);

  1091             } catch (Exception e) {

  1092                 throw new Error(e);

  1093             }

  1094         }

  1095     }

  1096 

  1097     // static fields (initialized in static initializer below)

  1098 

  1099     /**

  1100      * Creates a new ForkJoinWorkerThread. This factory is used unless

  1101      * overridden in ForkJoinPool constructors.

  1102      */

  1103     public static final ForkJoinWorkerThreadFactory

  1104         defaultForkJoinWorkerThreadFactory;

  1105 

  1106     /**

  1107      * Permission required for callers of methods that may start or

  1108      * kill threads.

  1109      */

  1110     private static final RuntimePermission modifyThreadPermission;

  1111 

  1112     /**

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

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

  1115      * to paranoically avoid potential initialization circularities

  1116      * as well as to simplify generated code.

  1117      */

  1118     static final ForkJoinPool common;

  1119 

  1120     /**

  1121      * Common pool parallelism. To allow simpler use and management

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

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

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

  1125      */

  1126     static final int commonParallelism;

  1127 

  1128     /**

  1129      * Sequence number for creating workerNamePrefix.

  1130      */

  1131     private static int poolNumberSequence;

  1132 

  1133     /**

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