--- jsr166/src/jsr166e/ForkJoinPool.java 2013/02/16 20:50:29 1.57 +++ jsr166/src/jsr166e/ForkJoinPool.java 2013/06/19 14:55:40 1.58 @@ -6,6 +6,7 @@ package jsr166e; +import java.lang.Thread.UncaughtExceptionHandler; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; @@ -17,6 +18,7 @@ import java.util.concurrent.ExecutorServ import java.util.concurrent.Future; import java.util.concurrent.RejectedExecutionException; import java.util.concurrent.RunnableFuture; +import java.util.concurrent.ThreadLocalRandom; import java.util.concurrent.TimeUnit; /** @@ -49,9 +51,9 @@ import java.util.concurrent.TimeUnit; * level; by default, equal to the number of available processors. The * pool attempts to maintain enough active (or available) threads by * dynamically adding, suspending, or resuming internal worker - * threads, even if some tasks are stalled waiting to join - * others. However, no such adjustments are guaranteed in the face of - * blocked I/O or other unmanaged synchronization. The nested {@link + * threads, even if some tasks are stalled waiting to join others. + * However, no such adjustments are guaranteed in the face of blocked + * I/O or other unmanaged synchronization. The nested {@link * ManagedBlocker} interface enables extension of the kinds of * synchronization accommodated. * @@ -75,38 +77,45 @@ import java.util.concurrent.TimeUnit; * there is little difference among choice of methods. * * + * * * * * * * - * + * * * * * - * + * * * * * - * + * * * * *
Summary of task execution methods
Call from non-fork/join clients Call from within fork/join computations
Arrange async execution Arrange async execution {@link #execute(ForkJoinTask)} {@link ForkJoinTask#fork}
Await and obtain result Await and obtain result {@link #invoke(ForkJoinTask)} {@link ForkJoinTask#invoke}
Arrange exec and obtain Future Arrange exec and obtain Future {@link #submit(ForkJoinTask)} {@link ForkJoinTask#fork} (ForkJoinTasks are Futures)
* *

The common pool is by default constructed with default - * parameters, but these may be controlled by setting three {@link - * System#getProperty system properties} with prefix {@code - * java.util.concurrent.ForkJoinPool.common}: {@code parallelism} -- - * an integer greater than zero, {@code threadFactory} -- the class - * name of a {@link ForkJoinWorkerThreadFactory}, and {@code - * exceptionHandler} -- the class name of a {@link - * java.lang.Thread.UncaughtExceptionHandler - * Thread.UncaughtExceptionHandler}. Upon any error in establishing - * these settings, default parameters are used. + * parameters, but these may be controlled by setting three + * {@linkplain System#getProperty system properties}: + *

+ * The system class loader is used to load these classes. + * Upon any error in establishing these settings, default parameters + * are used. It is possible to disable or limit the use of threads in + * the common pool by setting the parallelism property to zero, and/or + * using a factory that may return {@code null}. * *

Implementation notes: This implementation restricts the * maximum number of running threads to 32767. Attempts to create @@ -152,32 +161,35 @@ public class ForkJoinPool extends Abstra * (http://research.sun.com/scalable/pubs/index.html) and * "Idempotent work stealing" by Michael, Saraswat, and Vechev, * PPoPP 2009 (http://portal.acm.org/citation.cfm?id=1504186). - * The main differences ultimately stem from GC requirements that - * we null out taken slots as soon as we can, to maintain as small - * a footprint as possible even in programs generating huge - * numbers of tasks. To accomplish this, we shift the CAS - * arbitrating pop vs poll (steal) from being on the indices - * ("base" and "top") to the slots themselves. So, both a - * successful pop and poll mainly entail a CAS of a slot from - * non-null to null. Because we rely on CASes of references, we - * do not need tag bits on base or top. They are simple ints as - * used in any circular array-based queue (see for example - * ArrayDeque). Updates to the indices must still be ordered in a - * way that guarantees that top == base means the queue is empty, - * but otherwise may err on the side of possibly making the queue - * appear nonempty when a push, pop, or poll have not fully - * committed. Note that this means that the poll operation, - * considered individually, is not wait-free. One thief cannot - * successfully continue until another in-progress one (or, if - * previously empty, a push) completes. However, in the - * aggregate, we ensure at least probabilistic non-blockingness. - * If an attempted steal fails, a thief always chooses a different - * random victim target to try next. So, in order for one thief to - * progress, it suffices for any in-progress poll or new push on - * any empty queue to complete. (This is why we normally use - * method pollAt and its variants that try once at the apparent - * base index, else consider alternative actions, rather than - * method poll.) + * See also "Correct and Efficient Work-Stealing for Weak Memory + * Models" by Le, Pop, Cohen, and Nardelli, PPoPP 2013 + * (http://www.di.ens.fr/~zappa/readings/ppopp13.pdf) for an + * analysis of memory ordering (atomic, volatile etc) issues. The + * main differences ultimately stem from GC requirements that we + * null out taken slots as soon as we can, to maintain as small a + * footprint as possible even in programs generating huge numbers + * of tasks. To accomplish this, we shift the CAS arbitrating pop + * vs poll (steal) from being on the indices ("base" and "top") to + * the slots themselves. So, both a successful pop and poll + * mainly entail a CAS of a slot from non-null to null. Because + * we rely on CASes of references, we do not need tag bits on base + * or top. They are simple ints as used in any circular + * array-based queue (see for example ArrayDeque). Updates to the + * indices must still be ordered in a way that guarantees that top + * == base means the queue is empty, but otherwise may err on the + * side of possibly making the queue appear nonempty when a push, + * pop, or poll have not fully committed. Note that this means + * that the poll operation, considered individually, is not + * wait-free. One thief cannot successfully continue until another + * in-progress one (or, if previously empty, a push) completes. + * However, in the aggregate, we ensure at least probabilistic + * non-blockingness. If an attempted steal fails, a thief always + * chooses a different random victim target to try next. So, in + * order for one thief to progress, it suffices for any + * in-progress poll or new push on any empty queue to + * complete. (This is why we normally use method pollAt and its + * variants that try once at the apparent base index, else + * consider alternative actions, rather than method poll.) * * This approach also enables support of a user mode in which local * task processing is in FIFO, not LIFO order, simply by using @@ -196,18 +208,18 @@ public class ForkJoinPool extends Abstra * for work-stealing (this would contaminate lifo/fifo * processing). Instead, we randomly associate submission queues * with submitting threads, using a form of hashing. The - * ThreadLocal Submitter class contains a value initially used as - * a hash code for choosing existing queues, but may be randomly - * repositioned upon contention with other submitters. In - * essence, submitters act like workers except that they are - * restricted to executing local tasks that they submitted (or in - * the case of CountedCompleters, others with the same root task). - * However, because most shared/external queue operations are more - * expensive than internal, and because, at steady state, external - * submitters will compete for CPU with workers, ForkJoinTask.join - * and related methods disable them from repeatedly helping to - * process tasks if all workers are active. Insertion of tasks in - * shared mode requires a lock (mainly to protect in the case of + * Submitter probe value serves as a hash code for + * choosing existing queues, and may be randomly repositioned upon + * contention with other submitters. In essence, submitters act + * like workers except that they are restricted to executing local + * tasks that they submitted (or in the case of CountedCompleters, + * others with the same root task). However, because most + * shared/external queue operations are more expensive than + * internal, and because, at steady state, external submitters + * will compete for CPU with workers, ForkJoinTask.join and + * related methods disable them from repeatedly helping to process + * tasks if all workers are active. Insertion of tasks in shared + * mode requires a lock (mainly to protect in the case of * resizing) but we use only a simple spinlock (using bits in * field qlock), because submitters encountering a busy queue move * on to try or create other queues -- they block only when @@ -297,37 +309,35 @@ public class ForkJoinPool extends Abstra * has not yet entered the wait queue. We solve this by requiring * a full sweep of all workers (via repeated calls to method * scan()) both before and after a newly waiting worker is added - * to the wait queue. During a rescan, the worker might release - * some other queued worker rather than itself, which has the same - * net effect. Because enqueued workers may actually be rescanning - * rather than waiting, we set and clear the "parker" field of - * WorkQueues to reduce unnecessary calls to unpark. (This - * requires a secondary recheck to avoid missed signals.) Note - * the unusual conventions about Thread.interrupts surrounding - * parking and other blocking: Because interrupts are used solely - * to alert threads to check termination, which is checked anyway - * upon blocking, we clear status (using Thread.interrupted) - * before any call to park, so that park does not immediately - * return due to status being set via some other unrelated call to - * interrupt in user code. + * to the wait queue. Because enqueued workers may actually be + * rescanning rather than waiting, we set and clear the "parker" + * field of WorkQueues to reduce unnecessary calls to unpark. + * (This requires a secondary recheck to avoid missed signals.) + * Note the unusual conventions about Thread.interrupts + * surrounding parking and other blocking: Because interrupts are + * used solely to alert threads to check termination, which is + * checked anyway upon blocking, we clear status (using + * Thread.interrupted) before any call to park, so that park does + * not immediately return due to status being set via some other + * unrelated call to interrupt in user code. * * Signalling. We create or wake up workers only when there * appears to be at least one task they might be able to find and - * execute. However, many other threads may notice the same task - * and each signal to wake up a thread that might take it. So in - * general, pools will be over-signalled. When a submission is - * added or another worker adds a task to a queue that has fewer - * than two tasks, they signal waiting workers (or trigger - * creation of new ones if fewer than the given parallelism level - * -- signalWork), and may leave a hint to the unparked worker to - * help signal others upon wakeup). These primary signals are - * buttressed by others (see method helpSignal) whenever other - * threads scan for work or do not have a task to process. On - * most platforms, signalling (unpark) overhead time is noticeably + * execute. When a submission is added or another worker adds a + * task to a queue that has fewer than two tasks, they signal + * waiting workers (or trigger creation of new ones if fewer than + * the given parallelism level -- signalWork). These primary + * signals are buttressed by others whenever other threads remove + * a task from a queue and notice that there are other tasks there + * as well. So in general, pools will be over-signalled. On most + * platforms, signalling (unpark) overhead time is noticeably * long, and the time between signalling a thread and it actually * making progress can be very noticeably long, so it is worth * offloading these delays from critical paths as much as - * possible. + * possible. Additionally, workers spin-down gradually, by staying + * alive so long as they see the ctl state changing. Similar + * stability-sensing techniques are also used before blocking in + * awaitJoin and helpComplete. * * Trimming workers. To release resources after periods of lack of * use, a worker starting to wait when the pool is quiescent will @@ -440,7 +450,7 @@ public class ForkJoinPool extends Abstra * Common Pool * =========== * - * The static common Pool always exists after static + * The static common pool always exists after static * initialization. Since it (or any other created pool) need * never be used, we minimize initial construction overhead and * footprint to the setup of about a dozen fields, with no nested @@ -448,8 +458,11 @@ public class ForkJoinPool extends Abstra * fullExternalPush during the first submission to the pool. * * When external threads submit to the common pool, they can - * perform some subtask processing (see externalHelpJoin and - * related methods). We do not need to record whether these + * perform subtask processing (see externalHelpJoin and related + * methods). This caller-helps policy makes it sensible to set + * common pool parallelism level to one (or more) less than the + * total number of available cores, or even zero for pure + * caller-runs. We do not need to record whether external * submissions are to the common pool -- if not, externalHelpJoin * returns quickly (at the most helping to signal some common pool * workers). These submitters would otherwise be blocked waiting @@ -519,6 +532,7 @@ public class ForkJoinPool extends Abstra * * @param pool the pool this thread works in * @throws NullPointerException if the pool is null + * @return the new worker thread */ public ForkJoinWorkerThread newThread(ForkJoinPool pool); } @@ -535,26 +549,6 @@ public class ForkJoinPool extends Abstra } /** - * Per-thread records for threads that submit to pools. Currently - * holds only pseudo-random seed / index that is used to choose - * submission queues in method externalPush. In the future, this may - * also incorporate a means to implement different task rejection - * and resubmission policies. - * - * Seeds for submitters and workers/workQueues work in basically - * the same way but are initialized and updated using slightly - * different mechanics. Both are initialized using the same - * approach as in class ThreadLocal, where successive values are - * unlikely to collide with previous values. Seeds are then - * randomly modified upon collisions using xorshifts, which - * requires a non-zero seed. - */ - static final class Submitter { - int seed; - Submitter(int s) { seed = s; } - } - - /** * Class for artificial tasks that are used to replace the target * of local joins if they are removed from an interior queue slot * in WorkQueue.tryRemoveAndExec. We don't need the proxy to @@ -613,17 +607,8 @@ public class ForkJoinPool extends Abstra * do not want multiple WorkQueue instances or multiple queue * arrays sharing cache lines. (It would be best for queue objects * and their arrays to share, but there is nothing available to - * help arrange that). Unfortunately, because they are recorded - * in a common array, WorkQueue instances are often moved to be - * adjacent by garbage collectors. To reduce impact, we use field - * padding that works OK on common platforms; this effectively - * trades off slightly slower average field access for the sake of - * avoiding really bad worst-case access. (Until better JVM - * support is in place, this padding is dependent on transient - * properties of JVM field layout rules.) We also take care in - * allocating, sizing and resizing the array. Non-shared queue - * arrays are initialized by workers before use. Others are - * allocated on first use. + * help arrange that). The @Contended annotation alerts JVMs to + * try to keep instances apart. */ static final class WorkQueue { /** @@ -649,13 +634,12 @@ public class ForkJoinPool extends Abstra // Heuristic padding to ameliorate unfortunate memory placements volatile long pad00, pad01, pad02, pad03, pad04, pad05, pad06; - int seed; // for random scanning; initialize nonzero volatile int eventCount; // encoded inactivation count; < 0 if inactive int nextWait; // encoded record of next event waiter - int hint; // steal or signal hint (index) - int poolIndex; // index of this queue in pool (or 0) - final int mode; // 0: lifo, > 0: fifo, < 0: shared int nsteals; // number of steals + int hint; // steal index hint + short poolIndex; // index of this queue in pool + final short mode; // 0: lifo, > 0: fifo, < 0: shared volatile int qlock; // 1: locked, -1: terminate; else 0 volatile int base; // index of next slot for poll int top; // index of next slot for push @@ -673,8 +657,8 @@ public class ForkJoinPool extends Abstra int seed) { this.pool = pool; this.owner = owner; - this.mode = mode; - this.seed = seed; + this.mode = (short)mode; + this.hint = seed; // store initial seed for runWorker // Place indices in the center of array (that is not yet allocated) base = top = INITIAL_QUEUE_CAPACITY >>> 1; } @@ -687,7 +671,7 @@ public class ForkJoinPool extends Abstra return (n >= 0) ? 0 : -n; // ignore transient negative } - /** + /** * Provides a more accurate estimate of whether this queue has * any tasks than does queueSize, by checking whether a * near-empty queue has at least one unclaimed task. @@ -712,20 +696,18 @@ public class ForkJoinPool extends Abstra */ final void push(ForkJoinTask task) { ForkJoinTask[] a; ForkJoinPool p; - int s = top, m, n; + int s = top, n; if ((a = array) != null) { // ignore if queue removed - int j = (((m = a.length - 1) & s) << ASHIFT) + ABASE; - U.putOrderedObject(a, j, task); - if ((n = (top = s + 1) - base) <= 2) { - if ((p = pool) != null) - p.signalWork(this); - } + int m = a.length - 1; + U.putOrderedObject(a, ((m & s) << ASHIFT) + ABASE, task); + if ((n = (top = s + 1) - base) <= 2) + (p = pool).signalWork(p.workQueues, this); else if (n >= m) growArray(); } } - /** + /** * Initializes or doubles the capacity of array. Call either * by owner or with lock held -- it is OK for base, but not * top, to move while resizings are in progress. @@ -783,9 +765,8 @@ public class ForkJoinPool extends Abstra if ((a = array) != null) { int j = (((a.length - 1) & b) << ASHIFT) + ABASE; if ((t = (ForkJoinTask)U.getObjectVolatile(a, j)) != null && - base == b && - U.compareAndSwapObject(a, j, t, null)) { - base = b + 1; + base == b && U.compareAndSwapObject(a, j, t, null)) { + U.putOrderedInt(this, QBASE, b + 1); return t; } } @@ -801,9 +782,8 @@ public class ForkJoinPool extends Abstra int j = (((a.length - 1) & b) << ASHIFT) + ABASE; t = (ForkJoinTask)U.getObjectVolatile(a, j); if (t != null) { - if (base == b && - U.compareAndSwapObject(a, j, t, null)) { - base = b + 1; + if (U.compareAndSwapObject(a, j, t, null)) { + U.putOrderedInt(this, QBASE, b + 1); return t; } } @@ -860,49 +840,46 @@ public class ForkJoinPool extends Abstra ForkJoinTask.cancelIgnoringExceptions(t); } - /** - * Computes next value for random probes. Scans don't require - * a very high quality generator, but also not a crummy one. - * Marsaglia xor-shift is cheap and works well enough. Note: - * This is manually inlined in its usages in ForkJoinPool to - * avoid writes inside busy scan loops. - */ - final int nextSeed() { - int r = seed; - r ^= r << 13; - r ^= r >>> 17; - return seed = r ^= r << 5; - } - // Specialized execution methods /** - * Pops and runs tasks until empty. - */ - private void popAndExecAll() { - // A bit faster than repeated pop calls - ForkJoinTask[] a; int m, s; long j; ForkJoinTask t; - while ((a = array) != null && (m = a.length - 1) >= 0 && - (s = top - 1) - base >= 0 && - (t = ((ForkJoinTask) - U.getObject(a, j = ((m & s) << ASHIFT) + ABASE))) - != null) { - if (U.compareAndSwapObject(a, j, t, null)) { - top = s; - t.doExec(); - } - } - } - - /** * Polls and runs tasks until empty. */ - private void pollAndExecAll() { + final void pollAndExecAll() { for (ForkJoinTask t; (t = poll()) != null;) t.doExec(); } /** + * Executes a top-level task and any local tasks remaining + * after execution. + */ + final void runTask(ForkJoinTask task) { + if ((currentSteal = task) != null) { + task.doExec(); + ForkJoinTask[] a = array; + int md = mode; + ++nsteals; + currentSteal = null; + if (md != 0) + pollAndExecAll(); + else if (a != null) { + int s, m = a.length - 1; + while ((s = top - 1) - base >= 0) { + long i = ((m & s) << ASHIFT) + ABASE; + ForkJoinTask t = (ForkJoinTask)U.getObject(a, i); + if (t == null) + break; + if (U.compareAndSwapObject(a, i, t, null)) { + top = s; + t.doExec(); + } + } + } + } + } + + /** * If present, removes from queue and executes the given task, * or any other cancelled task. Returns (true) on any CAS * or consistency check failure so caller can retry. @@ -910,13 +887,15 @@ public class ForkJoinPool extends Abstra * @return false if no progress can be made, else true */ final boolean tryRemoveAndExec(ForkJoinTask task) { - boolean stat = true, removed = false, empty = true; + boolean stat; ForkJoinTask[] a; int m, s, b, n; - if ((a = array) != null && (m = a.length - 1) >= 0 && + if (task != null && (a = array) != null && (m = a.length - 1) >= 0 && (n = (s = top) - (b = base)) > 0) { + boolean removed = false, empty = true; + stat = true; for (ForkJoinTask t;;) { // traverse from s to b - int j = ((--s & m) << ASHIFT) + ABASE; - t = (ForkJoinTask)U.getObjectVolatile(a, j); + long j = ((--s & m) << ASHIFT) + ABASE; + t = (ForkJoinTask)U.getObject(a, j); if (t == null) // inconsistent length break; else if (t == task) { @@ -944,68 +923,95 @@ public class ForkJoinPool extends Abstra break; } } + if (removed) + task.doExec(); } - if (removed) - task.doExec(); + else + stat = false; return stat; } /** - * Polls for and executes the given task or any other task in - * its CountedCompleter computation. + * Tries to poll for and execute the given task or any other + * task in its CountedCompleter computation. */ - final boolean pollAndExecCC(ForkJoinTask root) { - ForkJoinTask[] a; int b; Object o; - outer: while ((b = base) - top < 0 && (a = array) != null) { + final boolean pollAndExecCC(CountedCompleter root) { + ForkJoinTask[] a; int b; Object o; CountedCompleter t, r; + if ((b = base) - top < 0 && (a = array) != null) { long j = (((a.length - 1) & b) << ASHIFT) + ABASE; - if ((o = U.getObject(a, j)) == null || - !(o instanceof CountedCompleter)) - break; - for (CountedCompleter t = (CountedCompleter)o, r = t;;) { - if (r == root) { - if (base == b && - U.compareAndSwapObject(a, j, t, null)) { - base = b + 1; - t.doExec(); + if ((o = U.getObjectVolatile(a, j)) == null) + return true; // retry + if (o instanceof CountedCompleter) { + for (t = (CountedCompleter)o, r = t;;) { + if (r == root) { + if (base == b && + U.compareAndSwapObject(a, j, t, null)) { + U.putOrderedInt(this, QBASE, b + 1); + t.doExec(); + } return true; } - else - break; // restart + else if ((r = r.completer) == null) + break; // not part of root computation } - if ((r = r.completer) == null) - break outer; // not part of root computation } } return false; } /** - * Executes a top-level task and any local tasks remaining - * after execution. + * Tries to pop and execute the given task or any other task + * in its CountedCompleter computation. */ - final void runTask(ForkJoinTask t) { - if (t != null) { - (currentSteal = t).doExec(); - currentSteal = null; - ++nsteals; - if (base - top < 0) { // process remaining local tasks - if (mode == 0) - popAndExecAll(); - else - pollAndExecAll(); + final boolean externalPopAndExecCC(CountedCompleter root) { + ForkJoinTask[] a; int s; Object o; CountedCompleter t, r; + if (base - (s = top) < 0 && (a = array) != null) { + long j = (((a.length - 1) & (s - 1)) << ASHIFT) + ABASE; + if ((o = U.getObject(a, j)) instanceof CountedCompleter) { + for (t = (CountedCompleter)o, r = t;;) { + if (r == root) { + if (U.compareAndSwapInt(this, QLOCK, 0, 1)) { + if (top == s && array == a && + U.compareAndSwapObject(a, j, t, null)) { + top = s - 1; + qlock = 0; + t.doExec(); + } + else + qlock = 0; + } + return true; + } + else if ((r = r.completer) == null) + break; + } } } + return false; } /** - * Executes a non-top-level (stolen) task. + * Internal version */ - final void runSubtask(ForkJoinTask t) { - if (t != null) { - ForkJoinTask ps = currentSteal; - (currentSteal = t).doExec(); - currentSteal = ps; + final boolean internalPopAndExecCC(CountedCompleter root) { + ForkJoinTask[] a; int s; Object o; CountedCompleter t, r; + if (base - (s = top) < 0 && (a = array) != null) { + long j = (((a.length - 1) & (s - 1)) << ASHIFT) + ABASE; + if ((o = U.getObject(a, j)) instanceof CountedCompleter) { + for (t = (CountedCompleter)o, r = t;;) { + if (r == root) { + if (U.compareAndSwapObject(a, j, t, null)) { + top = s - 1; + t.doExec(); + } + return true; + } + else if ((r = r.completer) == null) + break; + } + } } + return false; } /** @@ -1022,6 +1028,7 @@ public class ForkJoinPool extends Abstra // Unsafe mechanics private static final sun.misc.Unsafe U; + private static final long QBASE; private static final long QLOCK; private static final int ABASE; private static final int ASHIFT; @@ -1030,6 +1037,8 @@ public class ForkJoinPool extends Abstra U = getUnsafe(); Class k = WorkQueue.class; Class ak = ForkJoinTask[].class; + QBASE = U.objectFieldOffset + (k.getDeclaredField("base")); QLOCK = U.objectFieldOffset (k.getDeclaredField("qlock")); ABASE = U.arrayBaseOffset(ak); @@ -1046,13 +1055,6 @@ public class ForkJoinPool extends Abstra // static fields (initialized in static initializer below) /** - * Creates a new ForkJoinWorkerThread. This factory is used unless - * overridden in ForkJoinPool constructors. - */ - public static final ForkJoinWorkerThreadFactory - defaultForkJoinWorkerThreadFactory; - - /** * Per-thread submission bookkeeping. Shared across all pools * to reduce ThreadLocal pollution and because random motion * to avoid contention in one pool is likely to hold for others. @@ -1062,6 +1064,13 @@ public class ForkJoinPool extends Abstra static final ThreadLocal submitters; /** + * Creates a new ForkJoinWorkerThread. This factory is used unless + * overridden in ForkJoinPool constructors. + */ + public static final ForkJoinWorkerThreadFactory + defaultForkJoinWorkerThreadFactory; + + /** * Permission required for callers of methods that may start or * kill threads. */ @@ -1076,7 +1085,10 @@ public class ForkJoinPool extends Abstra static final ForkJoinPool common; /** - * Common pool parallelism. Must equal common.parallelism. + * Common pool parallelism. To allow simpler use and management + * when common pool threads are disabled, we allow the underlying + * common.parallelism field to be zero, but in that case still report + * parallelism as 1 to reflect resulting caller-runs mechanics. */ static final int commonParallelism; @@ -1215,30 +1227,19 @@ public class ForkJoinPool extends Abstra static final int FIFO_QUEUE = 1; static final int SHARED_QUEUE = -1; - // bounds for #steps in scan loop -- must be power 2 minus 1 - private static final int MIN_SCAN = 0x1ff; // cover estimation slop - private static final int MAX_SCAN = 0x1ffff; // 4 * max workers - - // Instance fields - - /* - * Field layout of this class tends to matter more than one would - * like. Runtime layout order is only loosely related to - * declaration order and may differ across JVMs, but the following - * empirically works OK on current JVMs. - */ - // Heuristic padding to ameliorate unfortunate memory placements volatile long pad00, pad01, pad02, pad03, pad04, pad05, pad06; + // Instance fields volatile long stealCount; // collects worker counts volatile long ctl; // main pool control volatile int plock; // shutdown status and seqLock volatile int indexSeed; // worker/submitter index seed - final int config; // mode and parallelism level + final short parallelism; // parallelism level + final short mode; // LIFO/FIFO WorkQueue[] workQueues; // main registry final ForkJoinWorkerThreadFactory factory; - final Thread.UncaughtExceptionHandler ueh; // per-worker UEH + final UncaughtExceptionHandler ueh; // per-worker UEH final String workerNamePrefix; // to create worker name string volatile Object pad10, pad11, pad12, pad13, pad14, pad15, pad16, pad17; @@ -1253,24 +1254,13 @@ public class ForkJoinPool extends Abstra * a more conservative alternative to a pure spinlock. */ private int acquirePlock() { - int spins = PL_SPINS, r = 0, ps, nps; + int spins = PL_SPINS, ps, nps; for (;;) { if (((ps = plock) & PL_LOCK) == 0 && U.compareAndSwapInt(this, PLOCK, ps, nps = ps + PL_LOCK)) return nps; - else if (r == 0) { // randomize spins if possible - Thread t = Thread.currentThread(); WorkQueue w; Submitter z; - if ((t instanceof ForkJoinWorkerThread) && - (w = ((ForkJoinWorkerThread)t).workQueue) != null) - r = w.seed; - else if ((z = submitters.get()) != null) - r = z.seed; - else - r = 1; - } else if (spins >= 0) { - r ^= r << 1; r ^= r >>> 3; r ^= r << 10; // xorshift - if (r >= 0) + if (ThreadLocalRandom.current().nextInt() >= 0) --spins; } else if (U.compareAndSwapInt(this, PLOCK, ps, ps | PL_SIGNAL)) { @@ -1306,11 +1296,11 @@ public class ForkJoinPool extends Abstra * parallelism level exist. Adjusts counts etc on failure. */ private void tryAddWorker() { - long c; int u; + long c; int u, e; while ((u = (int)((c = ctl) >>> 32)) < 0 && - (u & SHORT_SIGN) != 0 && (int)c == 0) { - long nc = (long)(((u + UTC_UNIT) & UTC_MASK) | - ((u + UAC_UNIT) & UAC_MASK)) << 32; + (u & SHORT_SIGN) != 0 && (e = (int)c) >= 0) { + long nc = ((long)(((u + UTC_UNIT) & UTC_MASK) | + ((u + UAC_UNIT) & UAC_MASK)) << 32) | (long)e; if (U.compareAndSwapLong(this, CTL, c, nc)) { ForkJoinWorkerThreadFactory fac; Throwable ex = null; @@ -1321,8 +1311,8 @@ public class ForkJoinPool extends Abstra wt.start(); break; } - } catch (Throwable e) { - ex = e; + } catch (Throwable rex) { + ex = rex; } deregisterWorker(wt, ex); break; @@ -1343,14 +1333,14 @@ public class ForkJoinPool extends Abstra * @return the worker's queue */ final WorkQueue registerWorker(ForkJoinWorkerThread wt) { - Thread.UncaughtExceptionHandler handler; WorkQueue[] ws; int s, ps; + UncaughtExceptionHandler handler; WorkQueue[] ws; int s, ps; wt.setDaemon(true); if ((handler = ueh) != null) wt.setUncaughtExceptionHandler(handler); do {} while (!U.compareAndSwapInt(this, INDEXSEED, s = indexSeed, s += SEED_INCREMENT) || s == 0); // skip 0 - WorkQueue w = new WorkQueue(this, wt, config >>> 16, s); + WorkQueue w = new WorkQueue(this, wt, mode, s); if (((ps = plock) & PL_LOCK) != 0 || !U.compareAndSwapInt(this, PLOCK, ps, ps += PL_LOCK)) ps = acquirePlock(); @@ -1370,14 +1360,15 @@ public class ForkJoinPool extends Abstra } } } - w.eventCount = w.poolIndex = r; // volatile write orders + w.poolIndex = (short)r; + w.eventCount = r; // volatile write orders ws[r] = w; } } finally { if (!U.compareAndSwapInt(this, PLOCK, ps, nps)) releasePlock(nps); } - wt.setName(workerNamePrefix.concat(Integer.toString(w.poolIndex))); + wt.setName(workerNamePrefix.concat(Integer.toString(w.poolIndex >>> 1))); return w; } @@ -1387,17 +1378,16 @@ public class ForkJoinPool extends Abstra * array, and adjusts counts. If pool is shutting down, tries to * complete termination. * - * @param wt the worker thread or null if construction failed + * @param wt the worker thread, or null if construction failed * @param ex the exception causing failure, or null if none */ final void deregisterWorker(ForkJoinWorkerThread wt, Throwable ex) { WorkQueue w = null; if (wt != null && (w = wt.workQueue) != null) { - int ps; + int ps; long sc; w.qlock = -1; // ensure set - long ns = w.nsteals, sc; // collect steal count - do {} while (!U.compareAndSwapLong(this, STEALCOUNT, - sc = stealCount, sc + ns)); + do {} while(!U.compareAndSwapLong(this, STEALCOUNT, sc = stealCount, + sc + w.nsteals)); if (((ps = plock) & PL_LOCK) != 0 || !U.compareAndSwapInt(this, PLOCK, ps, ps += PL_LOCK)) ps = acquirePlock(); @@ -1455,6 +1445,26 @@ public class ForkJoinPool extends Abstra // Submissions /** + * Per-thread records for threads that submit to pools. Currently + * holds only pseudo-random seed / index that is used to choose + * submission queues in method externalPush. In the future, this may + * also incorporate a means to implement different task rejection + * and resubmission policies. + * + * Seeds for submitters and workers/workQueues work in basically + * the same way but are initialized and updated using slightly + * different mechanics. Both are initialized using the same + * approach as in class ThreadLocal, where successive values are + * unlikely to collide with previous values. Seeds are then + * randomly modified upon collisions using xorshifts, which + * requires a non-zero seed. + */ + static final class Submitter { + int seed; + Submitter(int s) { seed = s; } + } + + /** * Unless shutting down, adds the given task to a submission queue * at submitter's current queue index (modulo submission * range). Only the most common path is directly handled in this @@ -1463,19 +1473,21 @@ public class ForkJoinPool extends Abstra * @param task the task. Caller must ensure non-null. */ final void externalPush(ForkJoinTask task) { - WorkQueue[] ws; WorkQueue q; Submitter z; int m; ForkJoinTask[] a; - if ((z = submitters.get()) != null && plock > 0 && - (ws = workQueues) != null && (m = (ws.length - 1)) >= 0 && - (q = ws[m & z.seed & SQMASK]) != null && + Submitter z = submitters.get(); + WorkQueue q; int r, m, s, n, am; ForkJoinTask[] a; + int ps = plock; + WorkQueue[] ws = workQueues; + if (z != null && ps > 0 && ws != null && (m = (ws.length - 1)) >= 0 && + (q = ws[m & (r = z.seed) & SQMASK]) != null && r != 0 && U.compareAndSwapInt(q, QLOCK, 0, 1)) { // lock - int b = q.base, s = q.top, n, an; - if ((a = q.array) != null && (an = a.length) > (n = s + 1 - b)) { - int j = (((an - 1) & s) << ASHIFT) + ABASE; + if ((a = q.array) != null && + (am = a.length - 1) > (n = (s = q.top) - q.base)) { + int j = ((am & s) << ASHIFT) + ABASE; U.putOrderedObject(a, j, task); q.top = s + 1; // push on to deque q.qlock = 0; - if (n <= 2) - signalWork(q); + if (n <= 1) + signalWork(ws, q); return; } q.qlock = 0; @@ -1513,13 +1525,13 @@ public class ForkJoinPool extends Abstra r = z.seed; r ^= r << 13; // same xorshift as WorkQueues r ^= r >>> 17; - z.seed = r ^ (r << 5); + z.seed = r ^= (r << 5); } - else if ((ps = plock) < 0) + if ((ps = plock) < 0) throw new RejectedExecutionException(); else if (ps == 0 || (ws = workQueues) == null || (m = ws.length - 1) < 0) { // initialize workQueues - int p = config & SMASK; // find power of two table size + int p = parallelism; // find power of two table size int n = (p > 1) ? p - 1 : 1; // ensure at least 2 slots n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; n = (n + 1) << 1; @@ -1551,7 +1563,7 @@ public class ForkJoinPool extends Abstra q.qlock = 0; // unlock } if (submitted) { - signalWork(q); + signalWork(ws, q); return; } } @@ -1559,6 +1571,7 @@ public class ForkJoinPool extends Abstra } else if (((ps = plock) & PL_LOCK) == 0) { // create new queue q = new WorkQueue(this, null, SHARED_QUEUE, r); + q.poolIndex = (short)k; if (((ps = plock) & PL_LOCK) != 0 || !U.compareAndSwapInt(this, PLOCK, ps, ps += PL_LOCK)) ps = acquirePlock(); @@ -1569,7 +1582,7 @@ public class ForkJoinPool extends Abstra releasePlock(nps); } else - r = 0; // try elsewhere while lock held + r = 0; } } @@ -1580,41 +1593,42 @@ public class ForkJoinPool extends Abstra */ final void incrementActiveCount() { long c; - do {} while (!U.compareAndSwapLong(this, CTL, c = ctl, c + AC_UNIT)); + do {} while (!U.compareAndSwapLong + (this, CTL, c = ctl, ((c & ~AC_MASK) | + ((c & AC_MASK) + AC_UNIT)))); } /** * Tries to create or activate a worker if too few are active. * - * @param q the (non-null) queue holding tasks to be signalled + * @param ws the worker array to use to find signallees + * @param q if non-null, the queue holding tasks to be processed */ - final void signalWork(WorkQueue q) { - int hint = q.poolIndex; - long c; int e, u, i, n; WorkQueue[] ws; WorkQueue w; Thread p; - while ((u = (int)((c = ctl) >>> 32)) < 0) { - if ((e = (int)c) > 0) { - if ((ws = workQueues) != null && ws.length > (i = e & SMASK) && - (w = ws[i]) != null && w.eventCount == (e | INT_SIGN)) { - long nc = (((long)(w.nextWait & E_MASK)) | - ((long)(u + UAC_UNIT) << 32)); - if (U.compareAndSwapLong(this, CTL, c, nc)) { - w.hint = hint; - w.eventCount = (e + E_SEQ) & E_MASK; - if ((p = w.parker) != null) - U.unpark(p); - break; - } - if (q.top - q.base <= 0) - break; - } - else - break; - } - else { + final void signalWork(WorkQueue[] ws, WorkQueue q) { + for (;;) { + long c; int e, u, i; WorkQueue w; Thread p; + if ((u = (int)((c = ctl) >>> 32)) >= 0) + break; + if ((e = (int)c) <= 0) { if ((short)u < 0) tryAddWorker(); break; } + if (ws == null || ws.length <= (i = e & SMASK) || + (w = ws[i]) == null) + break; + long nc = (((long)(w.nextWait & E_MASK)) | + ((long)(u + UAC_UNIT)) << 32); + int ne = (e + E_SEQ) & E_MASK; + if (w.eventCount == (e | INT_SIGN) && + U.compareAndSwapLong(this, CTL, c, nc)) { + w.eventCount = ne; + if ((p = w.parker) != null) + U.unpark(p); + break; + } + if (q != null && q.base >= q.top) + break; } } @@ -1625,215 +1639,154 @@ public class ForkJoinPool extends Abstra */ final void runWorker(WorkQueue w) { w.growArray(); // allocate queue - do { w.runTask(scan(w)); } while (w.qlock >= 0); + for (int r = w.hint; scan(w, r) == 0; ) { + r ^= r << 13; r ^= r >>> 17; r ^= r << 5; // xorshift + } } /** - * Scans for and, if found, returns one task, else possibly + * Scans for and, if found, runs one task, else possibly * inactivates the worker. This method operates on single reads of * volatile state and is designed to be re-invoked continuously, * in part because it returns upon detecting inconsistencies, * contention, or state changes that indicate possible success on * re-invocation. * - * The scan searches for tasks across queues (starting at a random - * index, and relying on registerWorker to irregularly scatter - * them within array to avoid bias), checking each at least twice. - * The scan terminates upon either finding a non-empty queue, or - * completing the sweep. If the worker is not inactivated, it - * takes and returns a task from this queue. Otherwise, if not - * activated, it signals workers (that may include itself) and - * returns so caller can retry. Also returns for true if the - * worker array may have changed during an empty scan. On failure - * to find a task, we take one of the following actions, after - * which the caller will retry calling this method unless - * terminated. - * - * * If pool is terminating, terminate the worker. - * - * * If not already enqueued, try to inactivate and enqueue the - * worker on wait queue. Or, if inactivating has caused the pool - * to be quiescent, relay to idleAwaitWork to possibly shrink - * pool. - * - * * If already enqueued and none of the above apply, possibly - * park awaiting signal, else lingering to help scan and signal. - * - * * If a non-empty queue discovered or left as a hint, - * help wake up other workers before return. + * The scan searches for tasks across queues starting at a random + * index, checking each at least twice. The scan terminates upon + * either finding a non-empty queue, or completing the sweep. If + * the worker is not inactivated, it takes and runs a task from + * this queue. Otherwise, if not activated, it tries to activate + * itself or some other worker by signalling. On failure to find a + * task, returns (for retry) if pool state may have changed during + * an empty scan, or tries to inactivate if active, else possibly + * blocks or terminates via method awaitWork. * * @param w the worker (via its WorkQueue) - * @return a task or null if none found + * @param r a random seed + * @return worker qlock status if would have waited, else 0 */ - private final ForkJoinTask scan(WorkQueue w) { + private final int scan(WorkQueue w, int r) { WorkQueue[] ws; int m; - int ps = plock; // read plock before ws - if (w != null && (ws = workQueues) != null && (m = ws.length - 1) >= 0) { - int ec = w.eventCount; // ec is negative if inactive - int r = w.seed; r ^= r << 13; r ^= r >>> 17; w.seed = r ^= r << 5; - w.hint = -1; // update seed and clear hint - int j = ((m + m + 1) | MIN_SCAN) & MAX_SCAN; - do { - WorkQueue q; ForkJoinTask[] a; int b; - if ((q = ws[(r + j) & m]) != null && (b = q.base) - q.top < 0 && - (a = q.array) != null) { // probably nonempty - int i = (((a.length - 1) & b) << ASHIFT) + ABASE; - ForkJoinTask t = (ForkJoinTask) - U.getObjectVolatile(a, i); - if (q.base == b && ec >= 0 && t != null && - U.compareAndSwapObject(a, i, t, null)) { - if ((q.base = b + 1) - q.top < 0) - signalWork(q); - return t; // taken - } - else if ((ec < 0 || j < m) && (int)(ctl >> AC_SHIFT) <= 0) { - w.hint = (r + j) & m; // help signal below - break; // cannot take - } - } - } while (--j >= 0); - - int h, e, ns; long c, sc; WorkQueue q; - if ((ns = w.nsteals) != 0) { - if (U.compareAndSwapLong(this, STEALCOUNT, - sc = stealCount, sc + ns)) - w.nsteals = 0; // collect steals and rescan - } - else if (plock != ps) // consistency check - ; // skip - else if ((e = (int)(c = ctl)) < 0) - w.qlock = -1; // pool is terminating - else { - if ((h = w.hint) < 0) { - if (ec >= 0) { // try to enqueue/inactivate - long nc = (((long)ec | - ((c - AC_UNIT) & (AC_MASK|TC_MASK)))); - w.nextWait = e; // link and mark inactive + long c = ctl; // for consistency check + if ((ws = workQueues) != null && (m = ws.length - 1) >= 0 && w != null) { + for (int j = m + m + 1, ec = w.eventCount;;) { + WorkQueue q; int b, e; ForkJoinTask[] a; ForkJoinTask t; + if ((q = ws[(r - j) & m]) != null && + (b = q.base) - q.top < 0 && (a = q.array) != null) { + long i = (((a.length - 1) & b) << ASHIFT) + ABASE; + if ((t = ((ForkJoinTask) + U.getObjectVolatile(a, i))) != null) { + if (ec < 0) + helpRelease(c, ws, w, q, b); + else if (q.base == b && + U.compareAndSwapObject(a, i, t, null)) { + U.putOrderedInt(q, QBASE, b + 1); + if ((b + 1) - q.top < 0) + signalWork(ws, q); + w.runTask(t); + } + } + break; + } + else if (--j < 0) { + if ((ec | (e = (int)c)) < 0) // inactive or terminating + return awaitWork(w, c, ec); + else if (ctl == c) { // try to inactivate and enqueue + long nc = (long)ec | ((c - AC_UNIT) & (AC_MASK|TC_MASK)); + w.nextWait = e; w.eventCount = ec | INT_SIGN; - if (ctl != c || !U.compareAndSwapLong(this, CTL, c, nc)) - w.eventCount = ec; // unmark on CAS failure - else if ((int)(c >> AC_SHIFT) == 1 - (config & SMASK)) - idleAwaitWork(w, nc, c); - } - else if (w.eventCount < 0 && ctl == c) { - Thread wt = Thread.currentThread(); - Thread.interrupted(); // clear status - U.putObject(wt, PARKBLOCKER, this); - w.parker = wt; // emulate LockSupport.park - if (w.eventCount < 0) // recheck - U.park(false, 0L); // block - w.parker = null; - U.putObject(wt, PARKBLOCKER, null); - } - } - if ((h >= 0 || (h = w.hint) >= 0) && - (ws = workQueues) != null && h < ws.length && - (q = ws[h]) != null) { // signal others before retry - WorkQueue v; Thread p; int u, i, s; - for (int n = (config & SMASK) - 1;;) { - int idleCount = (w.eventCount < 0) ? 0 : -1; - if (((s = idleCount - q.base + q.top) <= n && - (n = s) <= 0) || - (u = (int)((c = ctl) >>> 32)) >= 0 || - (e = (int)c) <= 0 || m < (i = e & SMASK) || - (v = ws[i]) == null) - break; - long nc = (((long)(v.nextWait & E_MASK)) | - ((long)(u + UAC_UNIT) << 32)); - if (v.eventCount != (e | INT_SIGN) || - !U.compareAndSwapLong(this, CTL, c, nc)) - break; - v.hint = h; - v.eventCount = (e + E_SEQ) & E_MASK; - if ((p = v.parker) != null) - U.unpark(p); - if (--n <= 0) - break; + if (!U.compareAndSwapLong(this, CTL, c, nc)) + w.eventCount = ec; // back out } + break; } } } - return null; + return 0; } /** - * If inactivating worker w has caused the pool to become - * quiescent, checks for pool termination, and, so long as this is - * not the only worker, waits for event for up to a given - * duration. On timeout, if ctl has not changed, terminates the - * worker, which will in turn wake up another worker to possibly - * repeat this process. + * A continuation of scan(), possibly blocking or terminating + * worker w. Returns without blocking if pool state has apparently + * changed since last invocation. Also, if inactivating w has + * caused the pool to become quiescent, checks for pool + * termination, and, so long as this is not the only worker, waits + * for event for up to a given duration. On timeout, if ctl has + * not changed, terminates the worker, which will in turn wake up + * another worker to possibly repeat this process. * * @param w the calling worker - * @param currentCtl the ctl value triggering possible quiescence - * @param prevCtl the ctl value to restore if thread is terminated + * @param c the ctl value on entry to scan + * @param ec the worker's eventCount on entry to scan */ - private void idleAwaitWork(WorkQueue w, long currentCtl, long prevCtl) { - if (w != null && w.eventCount < 0 && - !tryTerminate(false, false) && (int)prevCtl != 0 && - ctl == currentCtl) { - int dc = -(short)(currentCtl >>> TC_SHIFT); - long parkTime = dc < 0 ? FAST_IDLE_TIMEOUT: (dc + 1) * IDLE_TIMEOUT; - long deadline = System.nanoTime() + parkTime - TIMEOUT_SLOP; - Thread wt = Thread.currentThread(); - while (ctl == currentCtl) { - Thread.interrupted(); // timed variant of version in scan() - U.putObject(wt, PARKBLOCKER, this); - w.parker = wt; - if (ctl == currentCtl) - U.park(false, parkTime); - w.parker = null; - U.putObject(wt, PARKBLOCKER, null); - if (ctl != currentCtl) - break; - if (deadline - System.nanoTime() <= 0L && - U.compareAndSwapLong(this, CTL, currentCtl, prevCtl)) { - w.eventCount = (w.eventCount + E_SEQ) | E_MASK; - w.hint = -1; - w.qlock = -1; // shrink - break; + private final int awaitWork(WorkQueue w, long c, int ec) { + int stat, ns; long parkTime, deadline; + if ((stat = w.qlock) >= 0 && w.eventCount == ec && ctl == c && + !Thread.interrupted()) { + int e = (int)c; + int u = (int)(c >>> 32); + int d = (u >> UAC_SHIFT) + parallelism; // active count + + if (e < 0 || (d <= 0 && tryTerminate(false, false))) + stat = w.qlock = -1; // pool is terminating + else if ((ns = w.nsteals) != 0) { // collect steals and retry + long sc; + w.nsteals = 0; + do {} while(!U.compareAndSwapLong(this, STEALCOUNT, + sc = stealCount, sc + ns)); + } + else { + long pc = ((d > 0 || ec != (e | INT_SIGN)) ? 0L : + ((long)(w.nextWait & E_MASK)) | // ctl to restore + ((long)(u + UAC_UNIT)) << 32); + if (pc != 0L) { // timed wait if last waiter + int dc = -(short)(c >>> TC_SHIFT); + parkTime = (dc < 0 ? FAST_IDLE_TIMEOUT: + (dc + 1) * IDLE_TIMEOUT); + deadline = System.nanoTime() + parkTime - TIMEOUT_SLOP; + } + else + parkTime = deadline = 0L; + if (w.eventCount == ec && ctl == c) { + Thread wt = Thread.currentThread(); + U.putObject(wt, PARKBLOCKER, this); + w.parker = wt; // emulate LockSupport.park + if (w.eventCount == ec && ctl == c) + U.park(false, parkTime); // must recheck before park + w.parker = null; + U.putObject(wt, PARKBLOCKER, null); + if (parkTime != 0L && ctl == c && + deadline - System.nanoTime() <= 0L && + U.compareAndSwapLong(this, CTL, c, pc)) + stat = w.qlock = -1; // shrink pool } } } + return stat; } /** - * Scans through queues looking for work while joining a task; if - * any present, signals. May return early if more signalling is - * detectably unneeded. - * - * @param task return early if done - * @param origin an index to start scan - */ - private void helpSignal(ForkJoinTask task, int origin) { - WorkQueue[] ws; WorkQueue w; Thread p; long c; int m, u, e, i, s; - if (task != null && task.status >= 0 && - (u = (int)(ctl >>> 32)) < 0 && (u >> UAC_SHIFT) < 0 && - (ws = workQueues) != null && (m = ws.length - 1) >= 0) { - outer: for (int k = origin, j = m; j >= 0; --j) { - WorkQueue q = ws[k++ & m]; - for (int n = m;;) { // limit to at most m signals - if (task.status < 0) - break outer; - if (q == null || - ((s = -q.base + q.top) <= n && (n = s) <= 0)) - break; - if ((u = (int)((c = ctl) >>> 32)) >= 0 || - (e = (int)c) <= 0 || m < (i = e & SMASK) || - (w = ws[i]) == null) - break outer; - long nc = (((long)(w.nextWait & E_MASK)) | - ((long)(u + UAC_UNIT) << 32)); - if (w.eventCount != (e | INT_SIGN)) - break outer; - if (U.compareAndSwapLong(this, CTL, c, nc)) { - w.eventCount = (e + E_SEQ) & E_MASK; - if ((p = w.parker) != null) - U.unpark(p); - if (--n <= 0) - break; - } - } + * Possibly releases (signals) a worker. Called only from scan() + * when a worker with apparently inactive status finds a non-empty + * queue. This requires revalidating all of the associated state + * from caller. + */ + private final void helpRelease(long c, WorkQueue[] ws, WorkQueue w, + WorkQueue q, int b) { + WorkQueue v; int e, i; Thread p; + if (w != null && w.eventCount < 0 && (e = (int)c) > 0 && + ws != null && ws.length > (i = e & SMASK) && + (v = ws[i]) != null && ctl == c) { + long nc = (((long)(v.nextWait & E_MASK)) | + ((long)((int)(c >>> 32) + UAC_UNIT)) << 32); + int ne = (e + E_SEQ) & E_MASK; + if (q != null && q.base == b && w.eventCount < 0 && + v.eventCount == (e | INT_SIGN) && + U.compareAndSwapLong(this, CTL, c, nc)) { + v.eventCount = ne; + if ((p = v.parker) != null) + U.unpark(p); } } } @@ -1858,7 +1811,8 @@ public class ForkJoinPool extends Abstra */ private int tryHelpStealer(WorkQueue joiner, ForkJoinTask task) { int stat = 0, steps = 0; // bound to avoid cycles - if (joiner != null && task != null) { // hoist null checks + if (task != null && joiner != null && + joiner.base - joiner.top >= 0) { // hoist checks restart: for (;;) { ForkJoinTask subtask = task; // current target for (WorkQueue j = joiner, v;;) { // v is stealer of subtask @@ -1885,7 +1839,7 @@ public class ForkJoinPool extends Abstra } } for (;;) { // help stealer or descend to its stealer - ForkJoinTask[] a; int b; + ForkJoinTask[] a; int b; if (subtask.status < 0) // surround probes with continue restart; // consistency checks if ((b = v.base) - v.top < 0 && (a = v.array) != null) { @@ -1896,13 +1850,23 @@ public class ForkJoinPool extends Abstra v.currentSteal != subtask) continue restart; // stale stat = 1; // apparent progress - if (t != null && v.base == b && - U.compareAndSwapObject(a, i, t, null)) { - v.base = b + 1; // help stealer - joiner.runSubtask(t); + if (v.base == b) { + if (t == null) + break restart; + if (U.compareAndSwapObject(a, i, t, null)) { + U.putOrderedInt(v, QBASE, b + 1); + ForkJoinTask ps = joiner.currentSteal; + int jt = joiner.top; + do { + joiner.currentSteal = t; + t.doExec(); // clear local tasks too + } while (task.status >= 0 && + joiner.top != jt && + (t = joiner.pop()) != null); + joiner.currentSteal = ps; + break restart; + } } - else if (v.base == b && ++steps == MAX_HELP) - break restart; // v apparently stalled } else { // empty -- try to descend ForkJoinTask next = v.currentJoin; @@ -1929,27 +1893,33 @@ public class ForkJoinPool extends Abstra * and run tasks within the target's computation. * * @param task the task to join - * @param mode if shared, exit upon completing any task - * if all workers are active */ - private int helpComplete(ForkJoinTask task, int mode) { - WorkQueue[] ws; WorkQueue q; int m, n, s, u; - if (task != null && (ws = workQueues) != null && - (m = ws.length - 1) >= 0) { - for (int j = 1, origin = j;;) { + private int helpComplete(WorkQueue joiner, CountedCompleter task) { + WorkQueue[] ws; int m; + int s = 0; + if ((ws = workQueues) != null && (m = ws.length - 1) >= 0 && + joiner != null && task != null) { + int j = joiner.poolIndex; + int scans = m + m + 1; + long c = 0L; // for stability check + for (int k = scans; ; j += 2) { + WorkQueue q; if ((s = task.status) < 0) - return s; - if ((q = ws[j & m]) != null && q.pollAndExecCC(task)) { - origin = j; - if (mode == SHARED_QUEUE && - ((u = (int)(ctl >>> 32)) >= 0 || (u >> UAC_SHIFT) >= 0)) + break; + else if (joiner.internalPopAndExecCC(task)) + k = scans; + else if ((s = task.status) < 0) + break; + else if ((q = ws[j & m]) != null && q.pollAndExecCC(task)) + k = scans; + else if (--k < 0) { + if (c == (c = ctl)) break; + k = scans; } - else if ((j = (j + 2) & m) == origin) - break; } } - return 0; + return s; } /** @@ -1958,17 +1928,22 @@ public class ForkJoinPool extends Abstra * for blocking. Fails on contention or termination. Otherwise, * adds a new thread if no idle workers are available and pool * may become starved. + * + * @param c the assumed ctl value */ - final boolean tryCompensate() { - int pc = config & SMASK, e, i, tc; long c; - WorkQueue[] ws; WorkQueue w; Thread p; - if ((ws = workQueues) != null && (e = (int)(c = ctl)) >= 0) { - if (e != 0 && (i = e & SMASK) < ws.length && - (w = ws[i]) != null && w.eventCount == (e | INT_SIGN)) { + final boolean tryCompensate(long c) { + WorkQueue[] ws = workQueues; + int pc = parallelism, e = (int)c, m, tc; + if (ws != null && (m = ws.length - 1) >= 0 && e >= 0 && ctl == c) { + WorkQueue w = ws[e & m]; + if (e != 0 && w != null) { + Thread p; long nc = ((long)(w.nextWait & E_MASK) | (c & (AC_MASK|TC_MASK))); - if (U.compareAndSwapLong(this, CTL, c, nc)) { - w.eventCount = (e + E_SEQ) & E_MASK; + int ne = (e + E_SEQ) & E_MASK; + if (w.eventCount == (e | INT_SIGN) && + U.compareAndSwapLong(this, CTL, c, nc)) { + w.eventCount = ne; if ((p = w.parker) != null) U.unpark(p); return true; // replace with idle worker @@ -2011,23 +1986,20 @@ public class ForkJoinPool extends Abstra */ final int awaitJoin(WorkQueue joiner, ForkJoinTask task) { int s = 0; - if (joiner != null && task != null && (s = task.status) >= 0) { + if (task != null && (s = task.status) >= 0 && joiner != null) { ForkJoinTask prevJoin = joiner.currentJoin; joiner.currentJoin = task; - do {} while ((s = task.status) >= 0 && !joiner.isEmpty() && - joiner.tryRemoveAndExec(task)); // process local tasks - if (s >= 0 && (s = task.status) >= 0) { - helpSignal(task, joiner.poolIndex); - if ((s = task.status) >= 0 && - (task instanceof CountedCompleter)) - s = helpComplete(task, LIFO_QUEUE); - } + do {} while (joiner.tryRemoveAndExec(task) && // process local tasks + (s = task.status) >= 0); + if (s >= 0 && (task instanceof CountedCompleter)) + s = helpComplete(joiner, (CountedCompleter)task); + long cc = 0; // for stability checks while (s >= 0 && (s = task.status) >= 0) { - if ((!joiner.isEmpty() || // try helping - (s = tryHelpStealer(joiner, task)) == 0) && + if ((s = tryHelpStealer(joiner, task)) == 0 && (s = task.status) >= 0) { - helpSignal(task, joiner.poolIndex); - if ((s = task.status) >= 0 && tryCompensate()) { + if (!tryCompensate(cc)) + cc = ctl; + else { if (task.trySetSignal() && (s = task.status) >= 0) { synchronized (task) { if (task.status >= 0) { @@ -2040,9 +2012,11 @@ public class ForkJoinPool extends Abstra task.notifyAll(); } } - long c; // re-activate + long c; // reactivate do {} while (!U.compareAndSwapLong - (this, CTL, c = ctl, c + AC_UNIT)); + (this, CTL, c = ctl, + ((c & ~AC_MASK) | + ((c & AC_MASK) + AC_UNIT)))); } } } @@ -2064,15 +2038,11 @@ public class ForkJoinPool extends Abstra if (joiner != null && task != null && (s = task.status) >= 0) { ForkJoinTask prevJoin = joiner.currentJoin; joiner.currentJoin = task; - do {} while ((s = task.status) >= 0 && !joiner.isEmpty() && - joiner.tryRemoveAndExec(task)); - if (s >= 0 && (s = task.status) >= 0) { - helpSignal(task, joiner.poolIndex); - if ((s = task.status) >= 0 && - (task instanceof CountedCompleter)) - s = helpComplete(task, LIFO_QUEUE); - } - if (s >= 0 && joiner.isEmpty()) { + do {} while (joiner.tryRemoveAndExec(task) && // process local tasks + (s = task.status) >= 0); + if (s >= 0) { + if (task instanceof CountedCompleter) + helpComplete(joiner, (CountedCompleter)task); do {} while (task.status >= 0 && tryHelpStealer(joiner, task) > 0); } @@ -2084,14 +2054,14 @@ public class ForkJoinPool extends Abstra * Returns a (probably) non-empty steal queue, if one is found * during a scan, else null. This method must be retried by * caller if, by the time it tries to use the queue, it is empty. - * @param r a (random) seed for scanning */ - private WorkQueue findNonEmptyStealQueue(int r) { + private WorkQueue findNonEmptyStealQueue() { + int r = ThreadLocalRandom.current().nextInt(); for (;;) { int ps = plock, m; WorkQueue[] ws; WorkQueue q; if ((ws = workQueues) != null && (m = ws.length - 1) >= 0) { for (int j = (m + 1) << 2; j >= 0; --j) { - if ((q = ws[(((r + j) << 1) | 1) & m]) != null && + if ((q = ws[(((r - j) << 1) | 1) & m]) != null && q.base - q.top < 0) return q; } @@ -2108,35 +2078,36 @@ public class ForkJoinPool extends Abstra * find tasks either. */ final void helpQuiescePool(WorkQueue w) { + ForkJoinTask ps = w.currentSteal; for (boolean active = true;;) { long c; WorkQueue q; ForkJoinTask t; int b; - while ((t = w.nextLocalTask()) != null) { - if (w.base - w.top < 0) - signalWork(w); + while ((t = w.nextLocalTask()) != null) t.doExec(); - } - if ((q = findNonEmptyStealQueue(w.nextSeed())) != null) { + if ((q = findNonEmptyStealQueue()) != null) { if (!active) { // re-establish active count active = true; do {} while (!U.compareAndSwapLong - (this, CTL, c = ctl, c + AC_UNIT)); + (this, CTL, c = ctl, + ((c & ~AC_MASK) | + ((c & AC_MASK) + AC_UNIT)))); } if ((b = q.base) - q.top < 0 && (t = q.pollAt(b)) != null) { - if (q.base - q.top < 0) - signalWork(q); - w.runSubtask(t); + (w.currentSteal = t).doExec(); + w.currentSteal = ps; } } else if (active) { // decrement active count without queuing - long nc = (c = ctl) - AC_UNIT; - if ((int)(nc >> AC_SHIFT) + (config & SMASK) == 0) - return; // bypass decrement-then-increment + long nc = ((c = ctl) & ~AC_MASK) | ((c & AC_MASK) - AC_UNIT); + if ((int)(nc >> AC_SHIFT) + parallelism == 0) + break; // bypass decrement-then-increment if (U.compareAndSwapLong(this, CTL, c, nc)) active = false; } - else if ((int)((c = ctl) >> AC_SHIFT) + (config & SMASK) == 0 && - U.compareAndSwapLong(this, CTL, c, c + AC_UNIT)) - return; + else if ((int)((c = ctl) >> AC_SHIFT) + parallelism <= 0 && + U.compareAndSwapLong + (this, CTL, c, ((c & ~AC_MASK) | + ((c & AC_MASK) + AC_UNIT)))) + break; } } @@ -2150,13 +2121,10 @@ public class ForkJoinPool extends Abstra WorkQueue q; int b; if ((t = w.nextLocalTask()) != null) return t; - if ((q = findNonEmptyStealQueue(w.nextSeed())) == null) + if ((q = findNonEmptyStealQueue()) == null) return null; - if ((b = q.base) - q.top < 0 && (t = q.pollAt(b)) != null) { - if (q.base - q.top < 0) - signalWork(q); + if ((b = q.base) - q.top < 0 && (t = q.pollAt(b)) != null) return t; - } } } @@ -2209,7 +2177,7 @@ public class ForkJoinPool extends Abstra static int getSurplusQueuedTaskCount() { Thread t; ForkJoinWorkerThread wt; ForkJoinPool pool; WorkQueue q; if (((t = Thread.currentThread()) instanceof ForkJoinWorkerThread)) { - int p = (pool = (wt = (ForkJoinWorkerThread)t).pool).config & SMASK; + int p = (pool = (wt = (ForkJoinWorkerThread)t).pool).parallelism; int n = (q = wt.workQueue).top - q.base; int a = (int)(pool.ctl >> AC_SHIFT) + p; return n - (a > (p >>>= 1) ? 0 : @@ -2239,7 +2207,7 @@ public class ForkJoinPool extends Abstra */ private boolean tryTerminate(boolean now, boolean enable) { int ps; - if (this == common) // cannot shut down + if (this == common) // cannot shut down return false; if ((ps = plock) >= 0) { // enable by setting plock if (!enable) @@ -2253,7 +2221,7 @@ public class ForkJoinPool extends Abstra } for (long c;;) { if (((c = ctl) & STOP_BIT) != 0) { // already terminating - if ((short)(c >>> TC_SHIFT) == -(config & SMASK)) { + if ((short)(c >>> TC_SHIFT) + parallelism <= 0) { synchronized (this) { notifyAll(); // signal when 0 workers } @@ -2262,17 +2230,15 @@ public class ForkJoinPool extends Abstra } if (!now) { // check if idle & no tasks WorkQueue[] ws; WorkQueue w; - if ((int)(c >> AC_SHIFT) != -(config & SMASK)) + if ((int)(c >> AC_SHIFT) + parallelism > 0) return false; if ((ws = workQueues) != null) { for (int i = 0; i < ws.length; ++i) { - if ((w = ws[i]) != null) { - if (!w.isEmpty()) { // signal unprocessed tasks - signalWork(w); - return false; - } - if ((i & 1) != 0 && w.eventCount >= 0) - return false; // unqueued inactive worker + if ((w = ws[i]) != null && + (!w.isEmpty() || + ((i & 1) != 0 && w.eventCount >= 0))) { + signalWork(ws, w); + return false; } } } @@ -2328,7 +2294,7 @@ public class ForkJoinPool extends Abstra * least one task. */ static WorkQueue commonSubmitterQueue() { - ForkJoinPool p; WorkQueue[] ws; int m; Submitter z; + Submitter z; ForkJoinPool p; WorkQueue[] ws; int m, r; return ((z = submitters.get()) != null && (p = common) != null && (ws = p.workQueues) != null && @@ -2339,115 +2305,57 @@ public class ForkJoinPool extends Abstra /** * Tries to pop the given task from submitter's queue in common pool. */ - static boolean tryExternalUnpush(ForkJoinTask t) { - ForkJoinPool p; WorkQueue[] ws; WorkQueue q; Submitter z; - ForkJoinTask[] a; int m, s; - if (t != null && - (z = submitters.get()) != null && - (p = common) != null && - (ws = p.workQueues) != null && - (m = ws.length - 1) >= 0 && - (q = ws[m & z.seed & SQMASK]) != null && - (s = q.top) != q.base && - (a = q.array) != null) { + final boolean tryExternalUnpush(ForkJoinTask task) { + WorkQueue joiner; ForkJoinTask[] a; int m, s; + Submitter z = submitters.get(); + WorkQueue[] ws = workQueues; + boolean popped = false; + if (z != null && ws != null && (m = ws.length - 1) >= 0 && + (joiner = ws[z.seed & m & SQMASK]) != null && + joiner.base != (s = joiner.top) && + (a = joiner.array) != null) { long j = (((a.length - 1) & (s - 1)) << ASHIFT) + ABASE; - if (U.getObject(a, j) == t && - U.compareAndSwapInt(q, QLOCK, 0, 1)) { - if (q.array == a && q.top == s && // recheck - U.compareAndSwapObject(a, j, t, null)) { - q.top = s - 1; - q.qlock = 0; - return true; + if (U.getObject(a, j) == task && + U.compareAndSwapInt(joiner, QLOCK, 0, 1)) { + if (joiner.top == s && joiner.array == a && + U.compareAndSwapObject(a, j, task, null)) { + joiner.top = s - 1; + popped = true; } - q.qlock = 0; + joiner.qlock = 0; } } - return false; + return popped; } - /** - * Tries to pop and run local tasks within the same computation - * as the given root. On failure, tries to help complete from - * other queues via helpComplete. - */ - private void externalHelpComplete(WorkQueue q, ForkJoinTask root) { - ForkJoinTask[] a; int m; - if (q != null && (a = q.array) != null && (m = (a.length - 1)) >= 0 && - root != null && root.status >= 0) { - for (;;) { - int s, u; Object o; CountedCompleter task = null; - if ((s = q.top) - q.base > 0) { - long j = ((m & (s - 1)) << ASHIFT) + ABASE; - if ((o = U.getObject(a, j)) != null && - (o instanceof CountedCompleter)) { - CountedCompleter t = (CountedCompleter)o, r = t; - do { - if (r == root) { - if (U.compareAndSwapInt(q, QLOCK, 0, 1)) { - if (q.array == a && q.top == s && - U.compareAndSwapObject(a, j, t, null)) { - q.top = s - 1; - task = t; - } - q.qlock = 0; - } - break; - } - } while ((r = r.completer) != null); - } - } - if (task != null) - task.doExec(); - if (root.status < 0 || - (u = (int)(ctl >>> 32)) >= 0 || (u >> UAC_SHIFT) >= 0) + final int externalHelpComplete(CountedCompleter task) { + WorkQueue joiner; int m, j; + Submitter z = submitters.get(); + WorkQueue[] ws = workQueues; + int s = 0; + if (z != null && ws != null && (m = ws.length - 1) >= 0 && + (joiner = ws[(j = z.seed) & m & SQMASK]) != null && task != null) { + int scans = m + m + 1; + long c = 0L; // for stability check + j |= 1; // poll odd queues + for (int k = scans; ; j += 2) { + WorkQueue q; + if ((s = task.status) < 0) break; - if (task == null) { - helpSignal(root, q.poolIndex); - if (root.status >= 0) - helpComplete(root, SHARED_QUEUE); + else if (joiner.externalPopAndExecCC(task)) + k = scans; + else if ((s = task.status) < 0) break; + else if ((q = ws[j & m]) != null && q.pollAndExecCC(task)) + k = scans; + else if (--k < 0) { + if (c == (c = ctl)) + break; + k = scans; } } } - } - - /** - * Tries to help execute or signal availability of the given task - * from submitter's queue in common pool. - */ - static void externalHelpJoin(ForkJoinTask t) { - // Some hard-to-avoid overlap with tryExternalUnpush - ForkJoinPool p; WorkQueue[] ws; WorkQueue q, w; Submitter z; - ForkJoinTask[] a; int m, s, n; - if (t != null && - (z = submitters.get()) != null && - (p = common) != null && - (ws = p.workQueues) != null && - (m = ws.length - 1) >= 0 && - (q = ws[m & z.seed & SQMASK]) != null && - (a = q.array) != null) { - int am = a.length - 1; - if ((s = q.top) != q.base) { - long j = ((am & (s - 1)) << ASHIFT) + ABASE; - if (U.getObject(a, j) == t && - U.compareAndSwapInt(q, QLOCK, 0, 1)) { - if (q.array == a && q.top == s && - U.compareAndSwapObject(a, j, t, null)) { - q.top = s - 1; - q.qlock = 0; - t.doExec(); - } - else - q.qlock = 0; - } - } - if (t.status >= 0) { - if (t instanceof CountedCompleter) - p.externalHelpComplete(q, t); - else - p.helpSignal(t, q.poolIndex); - } - } + return s; } // Exported methods @@ -2514,37 +2422,46 @@ public class ForkJoinPool extends Abstra */ public ForkJoinPool(int parallelism, ForkJoinWorkerThreadFactory factory, - Thread.UncaughtExceptionHandler handler, + UncaughtExceptionHandler handler, boolean asyncMode) { + this(checkParallelism(parallelism), + checkFactory(factory), + handler, + (asyncMode ? FIFO_QUEUE : LIFO_QUEUE), + "ForkJoinPool-" + nextPoolId() + "-worker-"); checkPermission(); - if (factory == null) - throw new NullPointerException(); + } + + private static int checkParallelism(int parallelism) { if (parallelism <= 0 || parallelism > MAX_CAP) throw new IllegalArgumentException(); - this.factory = factory; - this.ueh = handler; - this.config = parallelism | (asyncMode ? (FIFO_QUEUE << 16) : 0); - long np = (long)(-parallelism); // offset ctl counts - this.ctl = ((np << AC_SHIFT) & AC_MASK) | ((np << TC_SHIFT) & TC_MASK); - int pn = nextPoolId(); - StringBuilder sb = new StringBuilder("ForkJoinPool-"); - sb.append(Integer.toString(pn)); - sb.append("-worker-"); - this.workerNamePrefix = sb.toString(); + return parallelism; + } + + private static ForkJoinWorkerThreadFactory checkFactory + (ForkJoinWorkerThreadFactory factory) { + if (factory == null) + throw new NullPointerException(); + return factory; } /** - * Constructor for common pool, suitable only for static initialization. - * Basically the same as above, but uses smallest possible initial footprint. - */ - ForkJoinPool(int parallelism, long ctl, - ForkJoinWorkerThreadFactory factory, - Thread.UncaughtExceptionHandler handler) { - this.config = parallelism; - this.ctl = ctl; + * Creates a {@code ForkJoinPool} with the given parameters, without + * any security checks or parameter validation. Invoked directly by + * makeCommonPool. + */ + private ForkJoinPool(int parallelism, + ForkJoinWorkerThreadFactory factory, + UncaughtExceptionHandler handler, + int mode, + String workerNamePrefix) { + this.workerNamePrefix = workerNamePrefix; this.factory = factory; this.ueh = handler; - this.workerNamePrefix = "ForkJoinPool.commonPool-worker-"; + this.mode = (short)mode; + this.parallelism = (short)parallelism; + long np = (long)(-parallelism); // offset ctl counts + this.ctl = ((np << AC_SHIFT) & AC_MASK) | ((np << TC_SHIFT) & TC_MASK); } /** @@ -2554,8 +2471,8 @@ public class ForkJoinPool extends Abstra * ongoing processing are automatically terminated upon program * {@link System#exit}. Any program that relies on asynchronous * task processing to complete before program termination should - * invoke {@code commonPool().}{@link #awaitQuiescence}, before - * exit. + * invoke {@code commonPool().}{@link #awaitQuiescence awaitQuiescence}, + * before exit. * * @return the common pool instance * @since 1.8 @@ -2618,7 +2535,7 @@ public class ForkJoinPool extends Abstra if (task instanceof ForkJoinTask) // avoid re-wrap job = (ForkJoinTask) task; else - job = new ForkJoinTask.AdaptedRunnableAction(task); + job = new ForkJoinTask.RunnableExecuteAction(task); externalPush(job); } @@ -2720,7 +2637,7 @@ public class ForkJoinPool extends Abstra * * @return the handler, or {@code null} if none */ - public Thread.UncaughtExceptionHandler getUncaughtExceptionHandler() { + public UncaughtExceptionHandler getUncaughtExceptionHandler() { return ueh; } @@ -2730,7 +2647,8 @@ public class ForkJoinPool extends Abstra * @return the targeted parallelism level of this pool */ public int getParallelism() { - return config & SMASK; + int par; + return ((par = parallelism) > 0) ? par : 1; } /** @@ -2752,7 +2670,7 @@ public class ForkJoinPool extends Abstra * @return the number of worker threads */ public int getPoolSize() { - return (config & SMASK) + (short)(ctl >>> TC_SHIFT); + return parallelism + (short)(ctl >>> TC_SHIFT); } /** @@ -2762,7 +2680,7 @@ public class ForkJoinPool extends Abstra * @return {@code true} if this pool uses async mode */ public boolean getAsyncMode() { - return (config >>> 16) == FIFO_QUEUE; + return mode == FIFO_QUEUE; } /** @@ -2793,7 +2711,7 @@ public class ForkJoinPool extends Abstra * @return the number of active threads */ public int getActiveThreadCount() { - int r = (config & SMASK) + (int)(ctl >> AC_SHIFT); + int r = parallelism + (int)(ctl >> AC_SHIFT); return (r <= 0) ? 0 : r; // suppress momentarily negative values } @@ -2809,7 +2727,7 @@ public class ForkJoinPool extends Abstra * @return {@code true} if all threads are currently idle */ public boolean isQuiescent() { - return (int)(ctl >> AC_SHIFT) + (config & SMASK) == 0; + return parallelism + (int)(ctl >> AC_SHIFT) <= 0; } /** @@ -2972,7 +2890,7 @@ public class ForkJoinPool extends Abstra } } } - int pc = (config & SMASK); + int pc = parallelism; int tc = pc + (short)(c >>> TC_SHIFT); int ac = pc + (int)(c >> AC_SHIFT); if (ac < 0) // ignore transient negative @@ -3045,7 +2963,7 @@ public class ForkJoinPool extends Abstra public boolean isTerminated() { long c = ctl; return ((c & STOP_BIT) != 0L && - (short)(c >>> TC_SHIFT) == -(config & SMASK)); + (short)(c >>> TC_SHIFT) + parallelism <= 0); } /** @@ -3064,7 +2982,7 @@ public class ForkJoinPool extends Abstra public boolean isTerminating() { long c = ctl; return ((c & STOP_BIT) != 0L && - (short)(c >>> TC_SHIFT) != -(config & SMASK)); + (short)(c >>> TC_SHIFT) + parallelism > 0); } /** @@ -3082,7 +3000,7 @@ public class ForkJoinPool extends Abstra * is interrupted, whichever happens first. Because the {@link * #commonPool()} never terminates until program shutdown, when * applied to the common pool, this method is equivalent to {@link - * #awaitQuiescence} but always returns {@code false}. + * #awaitQuiescence(long, TimeUnit)} but always returns {@code false}. * * @param timeout the maximum time to wait * @param unit the time unit of the timeout argument @@ -3101,19 +3019,20 @@ public class ForkJoinPool extends Abstra long nanos = unit.toNanos(timeout); if (isTerminated()) return true; - long startTime = System.nanoTime(); - boolean terminated = false; + if (nanos <= 0L) + return false; + long deadline = System.nanoTime() + nanos; synchronized (this) { - for (long waitTime = nanos, millis = 0L;;) { - if (terminated = isTerminated() || - waitTime <= 0L || - (millis = unit.toMillis(waitTime)) <= 0L) - break; - wait(millis); - waitTime = nanos - (System.nanoTime() - startTime); + for (;;) { + if (isTerminated()) + return true; + if (nanos <= 0L) + return false; + long millis = TimeUnit.NANOSECONDS.toMillis(nanos); + wait(millis > 0L ? millis : 1L); + nanos = deadline - System.nanoTime(); } } - return terminated; } /** @@ -3152,11 +3071,8 @@ public class ForkJoinPool extends Abstra ForkJoinTask t; WorkQueue q; int b; if ((q = ws[r++ & m]) != null && (b = q.base) - q.top < 0) { found = true; - if ((t = q.pollAt(b)) != null) { - if (q.base - q.top < 0) - signalWork(q); + if ((t = q.pollAt(b)) != null) t.doExec(); - } break; } } @@ -3181,9 +3097,9 @@ public class ForkJoinPool extends Abstra * not necessary. Method {@code block} blocks the current thread * if necessary (perhaps internally invoking {@code isReleasable} * before actually blocking). These actions are performed by any - * thread invoking {@link ForkJoinPool#managedBlock}. The - * unusual methods in this API accommodate synchronizers that may, - * but don't usually, block for long periods. Similarly, they + * thread invoking {@link ForkJoinPool#managedBlock(ManagedBlocker)}. + * The unusual methods in this API accommodate synchronizers that + * may, but don't usually, block for long periods. Similarly, they * allow more efficient internal handling of cases in which * additional workers may be, but usually are not, needed to * ensure sufficient parallelism. Toward this end, @@ -3241,6 +3157,7 @@ public class ForkJoinPool extends Abstra /** * Returns {@code true} if blocking is unnecessary. + * @return {@code true} if blocking is unnecessary */ boolean isReleasable(); } @@ -3270,21 +3187,8 @@ public class ForkJoinPool extends Abstra Thread t = Thread.currentThread(); if (t instanceof ForkJoinWorkerThread) { ForkJoinPool p = ((ForkJoinWorkerThread)t).pool; - while (!blocker.isReleasable()) { // variant of helpSignal - WorkQueue[] ws; WorkQueue q; int m, u; - if ((ws = p.workQueues) != null && (m = ws.length - 1) >= 0) { - for (int i = 0; i <= m; ++i) { - if (blocker.isReleasable()) - return; - if ((q = ws[i]) != null && q.base - q.top < 0) { - p.signalWork(q); - if ((u = (int)(p.ctl >>> 32)) >= 0 || - (u >> UAC_SHIFT) >= 0) - break; - } - } - } - if (p.tryCompensate()) { + while (!blocker.isReleasable()) { + if (p.tryCompensate(p.ctl)) { try { do {} while (!blocker.isReleasable() && !blocker.block()); @@ -3322,6 +3226,7 @@ public class ForkJoinPool extends Abstra private static final long STEALCOUNT; private static final long PLOCK; private static final long INDEXSEED; + private static final long QBASE; private static final long QLOCK; static { @@ -3341,6 +3246,8 @@ public class ForkJoinPool extends Abstra PARKBLOCKER = U.objectFieldOffset (tk.getDeclaredField("parkBlocker")); Class wk = WorkQueue.class; + QBASE = U.objectFieldOffset + (wk.getDeclaredField("base")); QLOCK = U.objectFieldOffset (wk.getDeclaredField("qlock")); Class ak = ForkJoinTask[].class; @@ -3354,45 +3261,51 @@ public class ForkJoinPool extends Abstra } submitters = new ThreadLocal(); - ForkJoinWorkerThreadFactory fac = defaultForkJoinWorkerThreadFactory = + defaultForkJoinWorkerThreadFactory = new DefaultForkJoinWorkerThreadFactory(); modifyThreadPermission = new RuntimePermission("modifyThread"); - /* - * Establish common pool parameters. For extra caution, - * computations to set up common pool state are here; the - * constructor just assigns these values to fields. - */ + common = java.security.AccessController.doPrivileged + (new java.security.PrivilegedAction() { + public ForkJoinPool run() { return makeCommonPool(); }}); + int par = common.parallelism; // report 1 even if threads disabled + commonParallelism = par > 0 ? par : 1; + } - int par = 0; - Thread.UncaughtExceptionHandler handler = null; - try { // TBD: limit or report ignored exceptions? + /** + * Creates and returns the common pool, respecting user settings + * specified via system properties. + */ + private static ForkJoinPool makeCommonPool() { + int parallelism = -1; + ForkJoinWorkerThreadFactory factory + = defaultForkJoinWorkerThreadFactory; + UncaughtExceptionHandler handler = null; + try { // ignore exceptions in accesing/parsing properties String pp = System.getProperty ("java.util.concurrent.ForkJoinPool.common.parallelism"); - String hp = System.getProperty - ("java.util.concurrent.ForkJoinPool.common.exceptionHandler"); String fp = System.getProperty ("java.util.concurrent.ForkJoinPool.common.threadFactory"); + String hp = System.getProperty + ("java.util.concurrent.ForkJoinPool.common.exceptionHandler"); + if (pp != null) + parallelism = Integer.parseInt(pp); if (fp != null) - fac = ((ForkJoinWorkerThreadFactory)ClassLoader. - getSystemClassLoader().loadClass(fp).newInstance()); + factory = ((ForkJoinWorkerThreadFactory)ClassLoader. + getSystemClassLoader().loadClass(fp).newInstance()); if (hp != null) - handler = ((Thread.UncaughtExceptionHandler)ClassLoader. + handler = ((UncaughtExceptionHandler)ClassLoader. getSystemClassLoader().loadClass(hp).newInstance()); - if (pp != null) - par = Integer.parseInt(pp); } catch (Exception ignore) { } - if (par <= 0) - par = Runtime.getRuntime().availableProcessors(); - if (par > MAX_CAP) - par = MAX_CAP; - commonParallelism = par; - long np = (long)(-par); // precompute initial ctl value - long ct = ((np << AC_SHIFT) & AC_MASK) | ((np << TC_SHIFT) & TC_MASK); - - common = new ForkJoinPool(par, ct, fac, handler); + if (parallelism < 0 && // default 1 less than #cores + (parallelism = Runtime.getRuntime().availableProcessors() - 1) < 0) + parallelism = 0; + if (parallelism > MAX_CAP) + parallelism = MAX_CAP; + return new ForkJoinPool(parallelism, factory, handler, LIFO_QUEUE, + "ForkJoinPool.commonPool-worker-"); } /**