jaroslav@1890: /* jaroslav@1890: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. jaroslav@1890: * jaroslav@1890: * This code is free software; you can redistribute it and/or modify it jaroslav@1890: * under the terms of the GNU General Public License version 2 only, as jaroslav@1890: * published by the Free Software Foundation. Oracle designates this jaroslav@1890: * particular file as subject to the "Classpath" exception as provided jaroslav@1890: * by Oracle in the LICENSE file that accompanied this code. jaroslav@1890: * jaroslav@1890: * This code is distributed in the hope that it will be useful, but WITHOUT jaroslav@1890: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or jaroslav@1890: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License jaroslav@1890: * version 2 for more details (a copy is included in the LICENSE file that jaroslav@1890: * accompanied this code). jaroslav@1890: * jaroslav@1890: * You should have received a copy of the GNU General Public License version jaroslav@1890: * 2 along with this work; if not, write to the Free Software Foundation, jaroslav@1890: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. jaroslav@1890: * jaroslav@1890: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA jaroslav@1890: * or visit www.oracle.com if you need additional information or have any jaroslav@1890: * questions. jaroslav@1890: */ jaroslav@1890: jaroslav@1890: /* jaroslav@1890: * This file is available under and governed by the GNU General Public jaroslav@1890: * License version 2 only, as published by the Free Software Foundation. jaroslav@1890: * However, the following notice accompanied the original version of this jaroslav@1890: * file: jaroslav@1890: * jaroslav@1890: * Written by Doug Lea with assistance from members of JCP JSR-166 jaroslav@1890: * Expert Group and released to the public domain, as explained at jaroslav@1890: * http://creativecommons.org/publicdomain/zero/1.0/ jaroslav@1890: */ jaroslav@1890: jaroslav@1890: package java.util.concurrent; jaroslav@1890: jaroslav@1890: import java.util.Collection; jaroslav@1890: import java.util.concurrent.RejectedExecutionException; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * A thread managed by a {@link ForkJoinPool}, which executes jaroslav@1890: * {@link ForkJoinTask}s. jaroslav@1890: * This class is subclassable solely for the sake of adding jaroslav@1890: * functionality -- there are no overridable methods dealing with jaroslav@1890: * scheduling or execution. However, you can override initialization jaroslav@1890: * and termination methods surrounding the main task processing loop. jaroslav@1890: * If you do create such a subclass, you will also need to supply a jaroslav@1890: * custom {@link ForkJoinPool.ForkJoinWorkerThreadFactory} to use it jaroslav@1890: * in a {@code ForkJoinPool}. jaroslav@1890: * jaroslav@1890: * @since 1.7 jaroslav@1890: * @author Doug Lea jaroslav@1890: */ jaroslav@1890: public class ForkJoinWorkerThread extends Thread { jaroslav@1890: /* jaroslav@1890: * Overview: jaroslav@1890: * jaroslav@1890: * ForkJoinWorkerThreads are managed by ForkJoinPools and perform jaroslav@1890: * ForkJoinTasks. This class includes bookkeeping in support of jaroslav@1890: * worker activation, suspension, and lifecycle control described jaroslav@1890: * in more detail in the internal documentation of class jaroslav@1890: * ForkJoinPool. And as described further below, this class also jaroslav@1890: * includes special-cased support for some ForkJoinTask jaroslav@1890: * methods. But the main mechanics involve work-stealing: jaroslav@1890: * jaroslav@1890: * Work-stealing queues are special forms of Deques that support jaroslav@1890: * only three of the four possible end-operations -- push, pop, jaroslav@1890: * and deq (aka steal), under the further constraints that push jaroslav@1890: * and pop are called only from the owning thread, while deq may jaroslav@1890: * be called from other threads. (If you are unfamiliar with jaroslav@1890: * them, you probably want to read Herlihy and Shavit's book "The jaroslav@1890: * Art of Multiprocessor programming", chapter 16 describing these jaroslav@1890: * in more detail before proceeding.) The main work-stealing jaroslav@1890: * queue design is roughly similar to those in the papers "Dynamic jaroslav@1890: * Circular Work-Stealing Deque" by Chase and Lev, SPAA 2005 jaroslav@1890: * (http://research.sun.com/scalable/pubs/index.html) and jaroslav@1890: * "Idempotent work stealing" by Michael, Saraswat, and Vechev, jaroslav@1890: * PPoPP 2009 (http://portal.acm.org/citation.cfm?id=1504186). jaroslav@1890: * The main differences ultimately stem from gc requirements that jaroslav@1890: * we null out taken slots as soon as we can, to maintain as small jaroslav@1890: * a footprint as possible even in programs generating huge jaroslav@1890: * numbers of tasks. To accomplish this, we shift the CAS jaroslav@1890: * arbitrating pop vs deq (steal) from being on the indices jaroslav@1890: * ("queueBase" and "queueTop") to the slots themselves (mainly jaroslav@1890: * via method "casSlotNull()"). So, both a successful pop and deq jaroslav@1890: * mainly entail a CAS of a slot from non-null to null. Because jaroslav@1890: * we rely on CASes of references, we do not need tag bits on jaroslav@1890: * queueBase or queueTop. They are simple ints as used in any jaroslav@1890: * circular array-based queue (see for example ArrayDeque). jaroslav@1890: * Updates to the indices must still be ordered in a way that jaroslav@1890: * guarantees that queueTop == queueBase means the queue is empty, jaroslav@1890: * but otherwise may err on the side of possibly making the queue jaroslav@1890: * appear nonempty when a push, pop, or deq have not fully jaroslav@1890: * committed. Note that this means that the deq operation, jaroslav@1890: * considered individually, is not wait-free. One thief cannot jaroslav@1890: * successfully continue until another in-progress one (or, if jaroslav@1890: * previously empty, a push) completes. However, in the jaroslav@1890: * aggregate, we ensure at least probabilistic non-blockingness. jaroslav@1890: * If an attempted steal fails, a thief always chooses a different jaroslav@1890: * random victim target to try next. So, in order for one thief to jaroslav@1890: * progress, it suffices for any in-progress deq or new push on jaroslav@1890: * any empty queue to complete. jaroslav@1890: * jaroslav@1890: * This approach also enables support for "async mode" where local jaroslav@1890: * task processing is in FIFO, not LIFO order; simply by using a jaroslav@1890: * version of deq rather than pop when locallyFifo is true (as set jaroslav@1890: * by the ForkJoinPool). This allows use in message-passing jaroslav@1890: * frameworks in which tasks are never joined. However neither jaroslav@1890: * mode considers affinities, loads, cache localities, etc, so jaroslav@1890: * rarely provide the best possible performance on a given jaroslav@1890: * machine, but portably provide good throughput by averaging over jaroslav@1890: * these factors. (Further, even if we did try to use such jaroslav@1890: * information, we do not usually have a basis for exploiting jaroslav@1890: * it. For example, some sets of tasks profit from cache jaroslav@1890: * affinities, but others are harmed by cache pollution effects.) jaroslav@1890: * jaroslav@1890: * When a worker would otherwise be blocked waiting to join a jaroslav@1890: * task, it first tries a form of linear helping: Each worker jaroslav@1890: * records (in field currentSteal) the most recent task it stole jaroslav@1890: * from some other worker. Plus, it records (in field currentJoin) jaroslav@1890: * the task it is currently actively joining. Method joinTask uses jaroslav@1890: * these markers to try to find a worker to help (i.e., steal back jaroslav@1890: * a task from and execute it) that could hasten completion of the jaroslav@1890: * actively joined task. In essence, the joiner executes a task jaroslav@1890: * that would be on its own local deque had the to-be-joined task jaroslav@1890: * not been stolen. This may be seen as a conservative variant of jaroslav@1890: * the approach in Wagner & Calder "Leapfrogging: a portable jaroslav@1890: * technique for implementing efficient futures" SIGPLAN Notices, jaroslav@1890: * 1993 (http://portal.acm.org/citation.cfm?id=155354). It differs jaroslav@1890: * in that: (1) We only maintain dependency links across workers jaroslav@1890: * upon steals, rather than use per-task bookkeeping. This may jaroslav@1890: * require a linear scan of workers array to locate stealers, but jaroslav@1890: * usually doesn't because stealers leave hints (that may become jaroslav@1890: * stale/wrong) of where to locate them. This isolates cost to jaroslav@1890: * when it is needed, rather than adding to per-task overhead. jaroslav@1890: * (2) It is "shallow", ignoring nesting and potentially cyclic jaroslav@1890: * mutual steals. (3) It is intentionally racy: field currentJoin jaroslav@1890: * is updated only while actively joining, which means that we jaroslav@1890: * miss links in the chain during long-lived tasks, GC stalls etc jaroslav@1890: * (which is OK since blocking in such cases is usually a good jaroslav@1890: * idea). (4) We bound the number of attempts to find work (see jaroslav@1890: * MAX_HELP) and fall back to suspending the worker and if jaroslav@1890: * necessary replacing it with another. jaroslav@1890: * jaroslav@1890: * Efficient implementation of these algorithms currently relies jaroslav@1890: * on an uncomfortable amount of "Unsafe" mechanics. To maintain jaroslav@1890: * correct orderings, reads and writes of variable queueBase jaroslav@1890: * require volatile ordering. Variable queueTop need not be jaroslav@1890: * volatile because non-local reads always follow those of jaroslav@1890: * queueBase. Similarly, because they are protected by volatile jaroslav@1890: * queueBase reads, reads of the queue array and its slots by jaroslav@1890: * other threads do not need volatile load semantics, but writes jaroslav@1890: * (in push) require store order and CASes (in pop and deq) jaroslav@1890: * require (volatile) CAS semantics. (Michael, Saraswat, and jaroslav@1890: * Vechev's algorithm has similar properties, but without support jaroslav@1890: * for nulling slots.) Since these combinations aren't supported jaroslav@1890: * using ordinary volatiles, the only way to accomplish these jaroslav@1890: * efficiently is to use direct Unsafe calls. (Using external jaroslav@1890: * AtomicIntegers and AtomicReferenceArrays for the indices and jaroslav@1890: * array is significantly slower because of memory locality and jaroslav@1890: * indirection effects.) jaroslav@1890: * jaroslav@1890: * Further, performance on most platforms is very sensitive to jaroslav@1890: * placement and sizing of the (resizable) queue array. Even jaroslav@1890: * though these queues don't usually become all that big, the jaroslav@1890: * initial size must be large enough to counteract cache jaroslav@1890: * contention effects across multiple queues (especially in the jaroslav@1890: * presence of GC cardmarking). Also, to improve thread-locality, jaroslav@1890: * queues are initialized after starting. jaroslav@1890: */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Mask for pool indices encoded as shorts jaroslav@1890: */ jaroslav@1890: private static final int SMASK = 0xffff; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Capacity of work-stealing queue array upon initialization. jaroslav@1890: * Must be a power of two. Initial size must be at least 4, but is jaroslav@1890: * padded to minimize cache effects. jaroslav@1890: */ jaroslav@1890: private static final int INITIAL_QUEUE_CAPACITY = 1 << 13; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Maximum size for queue array. Must be a power of two jaroslav@1890: * less than or equal to 1 << (31 - width of array entry) to jaroslav@1890: * ensure lack of index wraparound, but is capped at a lower jaroslav@1890: * value to help users trap runaway computations. jaroslav@1890: */ jaroslav@1890: private static final int MAXIMUM_QUEUE_CAPACITY = 1 << 24; // 16M jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * The work-stealing queue array. Size must be a power of two. jaroslav@1890: * Initialized when started (as oposed to when constructed), to jaroslav@1890: * improve memory locality. jaroslav@1890: */ jaroslav@1890: ForkJoinTask[] queue; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * The pool this thread works in. Accessed directly by ForkJoinTask. jaroslav@1890: */ jaroslav@1890: final ForkJoinPool pool; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Index (mod queue.length) of next queue slot to push to or pop jaroslav@1890: * from. It is written only by owner thread, and accessed by other jaroslav@1890: * threads only after reading (volatile) queueBase. Both queueTop jaroslav@1890: * and queueBase are allowed to wrap around on overflow, but jaroslav@1890: * (queueTop - queueBase) still estimates size. jaroslav@1890: */ jaroslav@1890: int queueTop; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Index (mod queue.length) of least valid queue slot, which is jaroslav@1890: * always the next position to steal from if nonempty. jaroslav@1890: */ jaroslav@1890: volatile int queueBase; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * The index of most recent stealer, used as a hint to avoid jaroslav@1890: * traversal in method helpJoinTask. This is only a hint because a jaroslav@1890: * worker might have had multiple steals and this only holds one jaroslav@1890: * of them (usually the most current). Declared non-volatile, jaroslav@1890: * relying on other prevailing sync to keep reasonably current. jaroslav@1890: */ jaroslav@1890: int stealHint; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Index of this worker in pool array. Set once by pool before jaroslav@1890: * running, and accessed directly by pool to locate this worker in jaroslav@1890: * its workers array. jaroslav@1890: */ jaroslav@1890: final int poolIndex; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Encoded record for pool task waits. Usages are always jaroslav@1890: * surrounded by volatile reads/writes jaroslav@1890: */ jaroslav@1890: int nextWait; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Complement of poolIndex, offset by count of entries of task jaroslav@1890: * waits. Accessed by ForkJoinPool to manage event waiters. jaroslav@1890: */ jaroslav@1890: volatile int eventCount; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Seed for random number generator for choosing steal victims. jaroslav@1890: * Uses Marsaglia xorshift. Must be initialized as nonzero. jaroslav@1890: */ jaroslav@1890: int seed; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Number of steals. Directly accessed (and reset) by pool when jaroslav@1890: * idle. jaroslav@1890: */ jaroslav@1890: int stealCount; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * True if this worker should or did terminate jaroslav@1890: */ jaroslav@1890: volatile boolean terminate; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Set to true before LockSupport.park; false on return jaroslav@1890: */ jaroslav@1890: volatile boolean parked; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * True if use local fifo, not default lifo, for local polling. jaroslav@1890: * Shadows value from ForkJoinPool. jaroslav@1890: */ jaroslav@1890: final boolean locallyFifo; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * The task most recently stolen from another worker (or jaroslav@1890: * submission queue). All uses are surrounded by enough volatile jaroslav@1890: * reads/writes to maintain as non-volatile. jaroslav@1890: */ jaroslav@1890: ForkJoinTask currentSteal; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * The task currently being joined, set only when actively trying jaroslav@1890: * to help other stealers in helpJoinTask. All uses are surrounded jaroslav@1890: * by enough volatile reads/writes to maintain as non-volatile. jaroslav@1890: */ jaroslav@1890: ForkJoinTask currentJoin; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Creates a ForkJoinWorkerThread operating in the given pool. jaroslav@1890: * jaroslav@1890: * @param pool the pool this thread works in jaroslav@1890: * @throws NullPointerException if pool is null jaroslav@1890: */ jaroslav@1890: protected ForkJoinWorkerThread(ForkJoinPool pool) { jaroslav@1890: super(pool.nextWorkerName()); jaroslav@1890: this.pool = pool; jaroslav@1890: int k = pool.registerWorker(this); jaroslav@1890: poolIndex = k; jaroslav@1890: eventCount = ~k & SMASK; // clear wait count jaroslav@1890: locallyFifo = pool.locallyFifo; jaroslav@1890: Thread.UncaughtExceptionHandler ueh = pool.ueh; jaroslav@1890: if (ueh != null) jaroslav@1890: setUncaughtExceptionHandler(ueh); jaroslav@1890: setDaemon(true); jaroslav@1890: } jaroslav@1890: jaroslav@1890: // Public methods jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns the pool hosting this thread. jaroslav@1890: * jaroslav@1890: * @return the pool jaroslav@1890: */ jaroslav@1890: public ForkJoinPool getPool() { jaroslav@1890: return pool; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns the index number of this thread in its pool. The jaroslav@1890: * returned value ranges from zero to the maximum number of jaroslav@1890: * threads (minus one) that have ever been created in the pool. jaroslav@1890: * This method may be useful for applications that track status or jaroslav@1890: * collect results per-worker rather than per-task. jaroslav@1890: * jaroslav@1890: * @return the index number jaroslav@1890: */ jaroslav@1890: public int getPoolIndex() { jaroslav@1890: return poolIndex; jaroslav@1890: } jaroslav@1890: jaroslav@1890: // Randomization jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Computes next value for random victim probes and backoffs. jaroslav@1890: * Scans don't require a very high quality generator, but also not jaroslav@1890: * a crummy one. Marsaglia xor-shift is cheap and works well jaroslav@1890: * enough. Note: This is manually inlined in FJP.scan() to avoid jaroslav@1890: * writes inside busy loops. jaroslav@1890: */ jaroslav@1890: private int nextSeed() { jaroslav@1890: int r = seed; jaroslav@1890: r ^= r << 13; jaroslav@1890: r ^= r >>> 17; jaroslav@1890: r ^= r << 5; jaroslav@1890: return seed = r; jaroslav@1890: } jaroslav@1890: jaroslav@1890: // Run State management jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Initializes internal state after construction but before jaroslav@1890: * processing any tasks. If you override this method, you must jaroslav@1890: * invoke {@code super.onStart()} at the beginning of the method. jaroslav@1890: * Initialization requires care: Most fields must have legal jaroslav@1890: * default values, to ensure that attempted accesses from other jaroslav@1890: * threads work correctly even before this thread starts jaroslav@1890: * processing tasks. jaroslav@1890: */ jaroslav@1890: protected void onStart() { jaroslav@1890: queue = new ForkJoinTask[INITIAL_QUEUE_CAPACITY]; jaroslav@1890: int r = pool.workerSeedGenerator.nextInt(); jaroslav@1890: seed = (r == 0) ? 1 : r; // must be nonzero jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Performs cleanup associated with termination of this worker jaroslav@1890: * thread. If you override this method, you must invoke jaroslav@1890: * {@code super.onTermination} at the end of the overridden method. jaroslav@1890: * jaroslav@1890: * @param exception the exception causing this thread to abort due jaroslav@1890: * to an unrecoverable error, or {@code null} if completed normally jaroslav@1890: */ jaroslav@1890: protected void onTermination(Throwable exception) { jaroslav@1890: try { jaroslav@1890: terminate = true; jaroslav@1890: cancelTasks(); jaroslav@1890: pool.deregisterWorker(this, exception); jaroslav@1890: } catch (Throwable ex) { // Shouldn't ever happen jaroslav@1890: if (exception == null) // but if so, at least rethrown jaroslav@1890: exception = ex; jaroslav@1890: } finally { jaroslav@1890: if (exception != null) jaroslav@1890: UNSAFE.throwException(exception); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * This method is required to be public, but should never be jaroslav@1890: * called explicitly. It performs the main run loop to execute jaroslav@1890: * {@link ForkJoinTask}s. jaroslav@1890: */ jaroslav@1890: public void run() { jaroslav@1890: Throwable exception = null; jaroslav@1890: try { jaroslav@1890: onStart(); jaroslav@1890: pool.work(this); jaroslav@1890: } catch (Throwable ex) { jaroslav@1890: exception = ex; jaroslav@1890: } finally { jaroslav@1890: onTermination(exception); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /* jaroslav@1890: * Intrinsics-based atomic writes for queue slots. These are jaroslav@1890: * basically the same as methods in AtomicReferenceArray, but jaroslav@1890: * specialized for (1) ForkJoinTask elements (2) requirement that jaroslav@1890: * nullness and bounds checks have already been performed by jaroslav@1890: * callers and (3) effective offsets are known not to overflow jaroslav@1890: * from int to long (because of MAXIMUM_QUEUE_CAPACITY). We don't jaroslav@1890: * need corresponding version for reads: plain array reads are OK jaroslav@1890: * because they are protected by other volatile reads and are jaroslav@1890: * confirmed by CASes. jaroslav@1890: * jaroslav@1890: * Most uses don't actually call these methods, but instead jaroslav@1890: * contain inlined forms that enable more predictable jaroslav@1890: * optimization. We don't define the version of write used in jaroslav@1890: * pushTask at all, but instead inline there a store-fenced array jaroslav@1890: * slot write. jaroslav@1890: * jaroslav@1890: * Also in most methods, as a performance (not correctness) issue, jaroslav@1890: * we'd like to encourage compilers not to arbitrarily postpone jaroslav@1890: * setting queueTop after writing slot. Currently there is no jaroslav@1890: * intrinsic for arranging this, but using Unsafe putOrderedInt jaroslav@1890: * may be a preferable strategy on some compilers even though its jaroslav@1890: * main effect is a pre-, not post- fence. To simplify possible jaroslav@1890: * changes, the option is left in comments next to the associated jaroslav@1890: * assignments. jaroslav@1890: */ jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * CASes slot i of array q from t to null. Caller must ensure q is jaroslav@1890: * non-null and index is in range. jaroslav@1890: */ jaroslav@1890: private static final boolean casSlotNull(ForkJoinTask[] q, int i, jaroslav@1890: ForkJoinTask t) { jaroslav@1890: return UNSAFE.compareAndSwapObject(q, (i << ASHIFT) + ABASE, t, null); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Performs a volatile write of the given task at given slot of jaroslav@1890: * array q. Caller must ensure q is non-null and index is in jaroslav@1890: * range. This method is used only during resets and backouts. jaroslav@1890: */ jaroslav@1890: private static final void writeSlot(ForkJoinTask[] q, int i, jaroslav@1890: ForkJoinTask t) { jaroslav@1890: UNSAFE.putObjectVolatile(q, (i << ASHIFT) + ABASE, t); jaroslav@1890: } jaroslav@1890: jaroslav@1890: // queue methods jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Pushes a task. Call only from this thread. jaroslav@1890: * jaroslav@1890: * @param t the task. Caller must ensure non-null. jaroslav@1890: */ jaroslav@1890: final void pushTask(ForkJoinTask t) { jaroslav@1890: ForkJoinTask[] q; int s, m; jaroslav@1890: if ((q = queue) != null) { // ignore if queue removed jaroslav@1890: long u = (((s = queueTop) & (m = q.length - 1)) << ASHIFT) + ABASE; jaroslav@1890: UNSAFE.putOrderedObject(q, u, t); jaroslav@1890: queueTop = s + 1; // or use putOrderedInt jaroslav@1890: if ((s -= queueBase) <= 2) jaroslav@1890: pool.signalWork(); jaroslav@1890: else if (s == m) jaroslav@1890: growQueue(); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Creates or doubles queue array. Transfers elements by jaroslav@1890: * emulating steals (deqs) from old array and placing, oldest jaroslav@1890: * first, into new array. jaroslav@1890: */ jaroslav@1890: private void growQueue() { jaroslav@1890: ForkJoinTask[] oldQ = queue; jaroslav@1890: int size = oldQ != null ? oldQ.length << 1 : INITIAL_QUEUE_CAPACITY; jaroslav@1890: if (size > MAXIMUM_QUEUE_CAPACITY) jaroslav@1890: throw new RejectedExecutionException("Queue capacity exceeded"); jaroslav@1890: if (size < INITIAL_QUEUE_CAPACITY) jaroslav@1890: size = INITIAL_QUEUE_CAPACITY; jaroslav@1890: ForkJoinTask[] q = queue = new ForkJoinTask[size]; jaroslav@1890: int mask = size - 1; jaroslav@1890: int top = queueTop; jaroslav@1890: int oldMask; jaroslav@1890: if (oldQ != null && (oldMask = oldQ.length - 1) >= 0) { jaroslav@1890: for (int b = queueBase; b != top; ++b) { jaroslav@1890: long u = ((b & oldMask) << ASHIFT) + ABASE; jaroslav@1890: Object x = UNSAFE.getObjectVolatile(oldQ, u); jaroslav@1890: if (x != null && UNSAFE.compareAndSwapObject(oldQ, u, x, null)) jaroslav@1890: UNSAFE.putObjectVolatile jaroslav@1890: (q, ((b & mask) << ASHIFT) + ABASE, x); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Tries to take a task from the base of the queue, failing if jaroslav@1890: * empty or contended. Note: Specializations of this code appear jaroslav@1890: * in locallyDeqTask and elsewhere. jaroslav@1890: * jaroslav@1890: * @return a task, or null if none or contended jaroslav@1890: */ jaroslav@1890: final ForkJoinTask deqTask() { jaroslav@1890: ForkJoinTask t; ForkJoinTask[] q; int b, i; jaroslav@1890: if (queueTop != (b = queueBase) && jaroslav@1890: (q = queue) != null && // must read q after b jaroslav@1890: (i = (q.length - 1) & b) >= 0 && jaroslav@1890: (t = q[i]) != null && queueBase == b && jaroslav@1890: UNSAFE.compareAndSwapObject(q, (i << ASHIFT) + ABASE, t, null)) { jaroslav@1890: queueBase = b + 1; jaroslav@1890: return t; jaroslav@1890: } jaroslav@1890: return null; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Tries to take a task from the base of own queue. Called only jaroslav@1890: * by this thread. jaroslav@1890: * jaroslav@1890: * @return a task, or null if none jaroslav@1890: */ jaroslav@1890: final ForkJoinTask locallyDeqTask() { jaroslav@1890: ForkJoinTask t; int m, b, i; jaroslav@1890: ForkJoinTask[] q = queue; jaroslav@1890: if (q != null && (m = q.length - 1) >= 0) { jaroslav@1890: while (queueTop != (b = queueBase)) { jaroslav@1890: if ((t = q[i = m & b]) != null && jaroslav@1890: queueBase == b && jaroslav@1890: UNSAFE.compareAndSwapObject(q, (i << ASHIFT) + ABASE, jaroslav@1890: t, null)) { jaroslav@1890: queueBase = b + 1; jaroslav@1890: return t; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: return null; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns a popped task, or null if empty. jaroslav@1890: * Called only by this thread. jaroslav@1890: */ jaroslav@1890: private ForkJoinTask popTask() { jaroslav@1890: int m; jaroslav@1890: ForkJoinTask[] q = queue; jaroslav@1890: if (q != null && (m = q.length - 1) >= 0) { jaroslav@1890: for (int s; (s = queueTop) != queueBase;) { jaroslav@1890: int i = m & --s; jaroslav@1890: long u = (i << ASHIFT) + ABASE; // raw offset jaroslav@1890: ForkJoinTask t = q[i]; jaroslav@1890: if (t == null) // lost to stealer jaroslav@1890: break; jaroslav@1890: if (UNSAFE.compareAndSwapObject(q, u, t, null)) { jaroslav@1890: queueTop = s; // or putOrderedInt jaroslav@1890: return t; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: return null; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Specialized version of popTask to pop only if topmost element jaroslav@1890: * is the given task. Called only by this thread. jaroslav@1890: * jaroslav@1890: * @param t the task. Caller must ensure non-null. jaroslav@1890: */ jaroslav@1890: final boolean unpushTask(ForkJoinTask t) { jaroslav@1890: ForkJoinTask[] q; jaroslav@1890: int s; jaroslav@1890: if ((q = queue) != null && (s = queueTop) != queueBase && jaroslav@1890: UNSAFE.compareAndSwapObject jaroslav@1890: (q, (((q.length - 1) & --s) << ASHIFT) + ABASE, t, null)) { jaroslav@1890: queueTop = s; // or putOrderedInt jaroslav@1890: return true; jaroslav@1890: } jaroslav@1890: return false; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns next task, or null if empty or contended. jaroslav@1890: */ jaroslav@1890: final ForkJoinTask peekTask() { jaroslav@1890: int m; jaroslav@1890: ForkJoinTask[] q = queue; jaroslav@1890: if (q == null || (m = q.length - 1) < 0) jaroslav@1890: return null; jaroslav@1890: int i = locallyFifo ? queueBase : (queueTop - 1); jaroslav@1890: return q[i & m]; jaroslav@1890: } jaroslav@1890: jaroslav@1890: // Support methods for ForkJoinPool jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Runs the given task, plus any local tasks until queue is empty jaroslav@1890: */ jaroslav@1890: final void execTask(ForkJoinTask t) { jaroslav@1890: currentSteal = t; jaroslav@1890: for (;;) { jaroslav@1890: if (t != null) jaroslav@1890: t.doExec(); jaroslav@1890: if (queueTop == queueBase) jaroslav@1890: break; jaroslav@1890: t = locallyFifo ? locallyDeqTask() : popTask(); jaroslav@1890: } jaroslav@1890: ++stealCount; jaroslav@1890: currentSteal = null; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Removes and cancels all tasks in queue. Can be called from any jaroslav@1890: * thread. jaroslav@1890: */ jaroslav@1890: final void cancelTasks() { jaroslav@1890: ForkJoinTask cj = currentJoin; // try to cancel ongoing tasks jaroslav@1890: if (cj != null && cj.status >= 0) jaroslav@1890: cj.cancelIgnoringExceptions(); jaroslav@1890: ForkJoinTask cs = currentSteal; jaroslav@1890: if (cs != null && cs.status >= 0) jaroslav@1890: cs.cancelIgnoringExceptions(); jaroslav@1890: while (queueBase != queueTop) { jaroslav@1890: ForkJoinTask t = deqTask(); jaroslav@1890: if (t != null) jaroslav@1890: t.cancelIgnoringExceptions(); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Drains tasks to given collection c. jaroslav@1890: * jaroslav@1890: * @return the number of tasks drained jaroslav@1890: */ jaroslav@1890: final int drainTasksTo(Collection> c) { jaroslav@1890: int n = 0; jaroslav@1890: while (queueBase != queueTop) { jaroslav@1890: ForkJoinTask t = deqTask(); jaroslav@1890: if (t != null) { jaroslav@1890: c.add(t); jaroslav@1890: ++n; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: return n; jaroslav@1890: } jaroslav@1890: jaroslav@1890: // Support methods for ForkJoinTask jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Returns an estimate of the number of tasks in the queue. jaroslav@1890: */ jaroslav@1890: final int getQueueSize() { jaroslav@1890: return queueTop - queueBase; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Gets and removes a local task. jaroslav@1890: * jaroslav@1890: * @return a task, if available jaroslav@1890: */ jaroslav@1890: final ForkJoinTask pollLocalTask() { jaroslav@1890: return locallyFifo ? locallyDeqTask() : popTask(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Gets and removes a local or stolen task. jaroslav@1890: * jaroslav@1890: * @return a task, if available jaroslav@1890: */ jaroslav@1890: final ForkJoinTask pollTask() { jaroslav@1890: ForkJoinWorkerThread[] ws; jaroslav@1890: ForkJoinTask t = pollLocalTask(); jaroslav@1890: if (t != null || (ws = pool.workers) == null) jaroslav@1890: return t; jaroslav@1890: int n = ws.length; // cheap version of FJP.scan jaroslav@1890: int steps = n << 1; jaroslav@1890: int r = nextSeed(); jaroslav@1890: int i = 0; jaroslav@1890: while (i < steps) { jaroslav@1890: ForkJoinWorkerThread w = ws[(i++ + r) & (n - 1)]; jaroslav@1890: if (w != null && w.queueBase != w.queueTop && w.queue != null) { jaroslav@1890: if ((t = w.deqTask()) != null) jaroslav@1890: return t; jaroslav@1890: i = 0; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: return null; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * The maximum stolen->joining link depth allowed in helpJoinTask, jaroslav@1890: * as well as the maximum number of retries (allowing on average jaroslav@1890: * one staleness retry per level) per attempt to instead try jaroslav@1890: * compensation. Depths for legitimate chains are unbounded, but jaroslav@1890: * we use a fixed constant to avoid (otherwise unchecked) cycles jaroslav@1890: * and bound staleness of traversal parameters at the expense of jaroslav@1890: * sometimes blocking when we could be helping. jaroslav@1890: */ jaroslav@1890: private static final int MAX_HELP = 16; jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Possibly runs some tasks and/or blocks, until joinMe is done. jaroslav@1890: * jaroslav@1890: * @param joinMe the task to join jaroslav@1890: * @return completion status on exit jaroslav@1890: */ jaroslav@1890: final int joinTask(ForkJoinTask joinMe) { jaroslav@1890: ForkJoinTask prevJoin = currentJoin; jaroslav@1890: currentJoin = joinMe; jaroslav@1890: for (int s, retries = MAX_HELP;;) { jaroslav@1890: if ((s = joinMe.status) < 0) { jaroslav@1890: currentJoin = prevJoin; jaroslav@1890: return s; jaroslav@1890: } jaroslav@1890: if (retries > 0) { jaroslav@1890: if (queueTop != queueBase) { jaroslav@1890: if (!localHelpJoinTask(joinMe)) jaroslav@1890: retries = 0; // cannot help jaroslav@1890: } jaroslav@1890: else if (retries == MAX_HELP >>> 1) { jaroslav@1890: --retries; // check uncommon case jaroslav@1890: if (tryDeqAndExec(joinMe) >= 0) jaroslav@1890: Thread.yield(); // for politeness jaroslav@1890: } jaroslav@1890: else jaroslav@1890: retries = helpJoinTask(joinMe) ? MAX_HELP : retries - 1; jaroslav@1890: } jaroslav@1890: else { jaroslav@1890: retries = MAX_HELP; // restart if not done jaroslav@1890: pool.tryAwaitJoin(joinMe); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * If present, pops and executes the given task, or any other jaroslav@1890: * cancelled task jaroslav@1890: * jaroslav@1890: * @return false if any other non-cancelled task exists in local queue jaroslav@1890: */ jaroslav@1890: private boolean localHelpJoinTask(ForkJoinTask joinMe) { jaroslav@1890: int s, i; ForkJoinTask[] q; ForkJoinTask t; jaroslav@1890: if ((s = queueTop) != queueBase && (q = queue) != null && jaroslav@1890: (i = (q.length - 1) & --s) >= 0 && jaroslav@1890: (t = q[i]) != null) { jaroslav@1890: if (t != joinMe && t.status >= 0) jaroslav@1890: return false; jaroslav@1890: if (UNSAFE.compareAndSwapObject jaroslav@1890: (q, (i << ASHIFT) + ABASE, t, null)) { jaroslav@1890: queueTop = s; // or putOrderedInt jaroslav@1890: t.doExec(); jaroslav@1890: } jaroslav@1890: } jaroslav@1890: return true; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Tries to locate and execute tasks for a stealer of the given jaroslav@1890: * task, or in turn one of its stealers, Traces jaroslav@1890: * currentSteal->currentJoin links looking for a thread working on jaroslav@1890: * a descendant of the given task and with a non-empty queue to jaroslav@1890: * steal back and execute tasks from. The implementation is very jaroslav@1890: * branchy to cope with potential inconsistencies or loops jaroslav@1890: * encountering chains that are stale, unknown, or of length jaroslav@1890: * greater than MAX_HELP links. All of these cases are dealt with jaroslav@1890: * by just retrying by caller. jaroslav@1890: * jaroslav@1890: * @param joinMe the task to join jaroslav@1890: * @param canSteal true if local queue is empty jaroslav@1890: * @return true if ran a task jaroslav@1890: */ jaroslav@1890: private boolean helpJoinTask(ForkJoinTask joinMe) { jaroslav@1890: boolean helped = false; jaroslav@1890: int m = pool.scanGuard & SMASK; jaroslav@1890: ForkJoinWorkerThread[] ws = pool.workers; jaroslav@1890: if (ws != null && ws.length > m && joinMe.status >= 0) { jaroslav@1890: int levels = MAX_HELP; // remaining chain length jaroslav@1890: ForkJoinTask task = joinMe; // base of chain jaroslav@1890: outer:for (ForkJoinWorkerThread thread = this;;) { jaroslav@1890: // Try to find v, the stealer of task, by first using hint jaroslav@1890: ForkJoinWorkerThread v = ws[thread.stealHint & m]; jaroslav@1890: if (v == null || v.currentSteal != task) { jaroslav@1890: for (int j = 0; ;) { // search array jaroslav@1890: if ((v = ws[j]) != null && v.currentSteal == task) { jaroslav@1890: thread.stealHint = j; jaroslav@1890: break; // save hint for next time jaroslav@1890: } jaroslav@1890: if (++j > m) jaroslav@1890: break outer; // can't find stealer jaroslav@1890: } jaroslav@1890: } jaroslav@1890: // Try to help v, using specialized form of deqTask jaroslav@1890: for (;;) { jaroslav@1890: ForkJoinTask[] q; int b, i; jaroslav@1890: if (joinMe.status < 0) jaroslav@1890: break outer; jaroslav@1890: if ((b = v.queueBase) == v.queueTop || jaroslav@1890: (q = v.queue) == null || jaroslav@1890: (i = (q.length-1) & b) < 0) jaroslav@1890: break; // empty jaroslav@1890: long u = (i << ASHIFT) + ABASE; jaroslav@1890: ForkJoinTask t = q[i]; jaroslav@1890: if (task.status < 0) jaroslav@1890: break outer; // stale jaroslav@1890: if (t != null && v.queueBase == b && jaroslav@1890: UNSAFE.compareAndSwapObject(q, u, t, null)) { jaroslav@1890: v.queueBase = b + 1; jaroslav@1890: v.stealHint = poolIndex; jaroslav@1890: ForkJoinTask ps = currentSteal; jaroslav@1890: currentSteal = t; jaroslav@1890: t.doExec(); jaroslav@1890: currentSteal = ps; jaroslav@1890: helped = true; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: // Try to descend to find v's stealer jaroslav@1890: ForkJoinTask next = v.currentJoin; jaroslav@1890: if (--levels > 0 && task.status >= 0 && jaroslav@1890: next != null && next != task) { jaroslav@1890: task = next; jaroslav@1890: thread = v; jaroslav@1890: } jaroslav@1890: else jaroslav@1890: break; // max levels, stale, dead-end, or cyclic jaroslav@1890: } jaroslav@1890: } jaroslav@1890: return helped; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Performs an uncommon case for joinTask: If task t is at base of jaroslav@1890: * some workers queue, steals and executes it. jaroslav@1890: * jaroslav@1890: * @param t the task jaroslav@1890: * @return t's status jaroslav@1890: */ jaroslav@1890: private int tryDeqAndExec(ForkJoinTask t) { jaroslav@1890: int m = pool.scanGuard & SMASK; jaroslav@1890: ForkJoinWorkerThread[] ws = pool.workers; jaroslav@1890: if (ws != null && ws.length > m && t.status >= 0) { jaroslav@1890: for (int j = 0; j <= m; ++j) { jaroslav@1890: ForkJoinTask[] q; int b, i; jaroslav@1890: ForkJoinWorkerThread v = ws[j]; jaroslav@1890: if (v != null && jaroslav@1890: (b = v.queueBase) != v.queueTop && jaroslav@1890: (q = v.queue) != null && jaroslav@1890: (i = (q.length - 1) & b) >= 0 && jaroslav@1890: q[i] == t) { jaroslav@1890: long u = (i << ASHIFT) + ABASE; jaroslav@1890: if (v.queueBase == b && jaroslav@1890: UNSAFE.compareAndSwapObject(q, u, t, null)) { jaroslav@1890: v.queueBase = b + 1; jaroslav@1890: v.stealHint = poolIndex; jaroslav@1890: ForkJoinTask ps = currentSteal; jaroslav@1890: currentSteal = t; jaroslav@1890: t.doExec(); jaroslav@1890: currentSteal = ps; jaroslav@1890: } jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: return t.status; jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Implements ForkJoinTask.getSurplusQueuedTaskCount(). Returns jaroslav@1890: * an estimate of the number of tasks, offset by a function of jaroslav@1890: * number of idle workers. jaroslav@1890: * jaroslav@1890: * This method provides a cheap heuristic guide for task jaroslav@1890: * partitioning when programmers, frameworks, tools, or languages jaroslav@1890: * have little or no idea about task granularity. In essence by jaroslav@1890: * offering this method, we ask users only about tradeoffs in jaroslav@1890: * overhead vs expected throughput and its variance, rather than jaroslav@1890: * how finely to partition tasks. jaroslav@1890: * jaroslav@1890: * In a steady state strict (tree-structured) computation, each jaroslav@1890: * thread makes available for stealing enough tasks for other jaroslav@1890: * threads to remain active. Inductively, if all threads play by jaroslav@1890: * the same rules, each thread should make available only a jaroslav@1890: * constant number of tasks. jaroslav@1890: * jaroslav@1890: * The minimum useful constant is just 1. But using a value of 1 jaroslav@1890: * would require immediate replenishment upon each steal to jaroslav@1890: * maintain enough tasks, which is infeasible. Further, jaroslav@1890: * partitionings/granularities of offered tasks should minimize jaroslav@1890: * steal rates, which in general means that threads nearer the top jaroslav@1890: * of computation tree should generate more than those nearer the jaroslav@1890: * bottom. In perfect steady state, each thread is at jaroslav@1890: * approximately the same level of computation tree. However, jaroslav@1890: * producing extra tasks amortizes the uncertainty of progress and jaroslav@1890: * diffusion assumptions. jaroslav@1890: * jaroslav@1890: * So, users will want to use values larger, but not much larger jaroslav@1890: * than 1 to both smooth over transient shortages and hedge jaroslav@1890: * against uneven progress; as traded off against the cost of jaroslav@1890: * extra task overhead. We leave the user to pick a threshold jaroslav@1890: * value to compare with the results of this call to guide jaroslav@1890: * decisions, but recommend values such as 3. jaroslav@1890: * jaroslav@1890: * When all threads are active, it is on average OK to estimate jaroslav@1890: * surplus strictly locally. In steady-state, if one thread is jaroslav@1890: * maintaining say 2 surplus tasks, then so are others. So we can jaroslav@1890: * just use estimated queue length (although note that (queueTop - jaroslav@1890: * queueBase) can be an overestimate because of stealers lagging jaroslav@1890: * increments of queueBase). However, this strategy alone leads jaroslav@1890: * to serious mis-estimates in some non-steady-state conditions jaroslav@1890: * (ramp-up, ramp-down, other stalls). We can detect many of these jaroslav@1890: * by further considering the number of "idle" threads, that are jaroslav@1890: * known to have zero queued tasks, so compensate by a factor of jaroslav@1890: * (#idle/#active) threads. jaroslav@1890: */ jaroslav@1890: final int getEstimatedSurplusTaskCount() { jaroslav@1890: return queueTop - queueBase - pool.idlePerActive(); jaroslav@1890: } jaroslav@1890: jaroslav@1890: /** jaroslav@1890: * Runs tasks until {@code pool.isQuiescent()}. We piggyback on jaroslav@1890: * pool's active count ctl maintenance, but rather than blocking jaroslav@1890: * when tasks cannot be found, we rescan until all others cannot jaroslav@1890: * find tasks either. The bracketing by pool quiescerCounts jaroslav@1890: * updates suppresses pool auto-shutdown mechanics that could jaroslav@1890: * otherwise prematurely terminate the pool because all threads jaroslav@1890: * appear to be inactive. jaroslav@1890: */ jaroslav@1890: final void helpQuiescePool() { jaroslav@1890: boolean active = true; jaroslav@1890: ForkJoinTask ps = currentSteal; // to restore below jaroslav@1890: ForkJoinPool p = pool; jaroslav@1890: p.addQuiescerCount(1); jaroslav@1890: for (;;) { jaroslav@1890: ForkJoinWorkerThread[] ws = p.workers; jaroslav@1890: ForkJoinWorkerThread v = null; jaroslav@1890: int n; jaroslav@1890: if (queueTop != queueBase) jaroslav@1890: v = this; jaroslav@1890: else if (ws != null && (n = ws.length) > 1) { jaroslav@1890: ForkJoinWorkerThread w; jaroslav@1890: int r = nextSeed(); // cheap version of FJP.scan jaroslav@1890: int steps = n << 1; jaroslav@1890: for (int i = 0; i < steps; ++i) { jaroslav@1890: if ((w = ws[(i + r) & (n - 1)]) != null && jaroslav@1890: w.queueBase != w.queueTop) { jaroslav@1890: v = w; jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: if (v != null) { jaroslav@1890: ForkJoinTask t; jaroslav@1890: if (!active) { jaroslav@1890: active = true; jaroslav@1890: p.addActiveCount(1); jaroslav@1890: } jaroslav@1890: if ((t = (v != this) ? v.deqTask() : jaroslav@1890: locallyFifo ? locallyDeqTask() : popTask()) != null) { jaroslav@1890: currentSteal = t; jaroslav@1890: t.doExec(); jaroslav@1890: currentSteal = ps; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: else { jaroslav@1890: if (active) { jaroslav@1890: active = false; jaroslav@1890: p.addActiveCount(-1); jaroslav@1890: } jaroslav@1890: if (p.isQuiescent()) { jaroslav@1890: p.addActiveCount(1); jaroslav@1890: p.addQuiescerCount(-1); jaroslav@1890: break; jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: } jaroslav@1890: jaroslav@1890: // Unsafe mechanics jaroslav@1890: private static final sun.misc.Unsafe UNSAFE; jaroslav@1890: private static final long ABASE; jaroslav@1890: private static final int ASHIFT; jaroslav@1890: jaroslav@1890: static { jaroslav@1890: int s; jaroslav@1890: try { jaroslav@1890: UNSAFE = sun.misc.Unsafe.getUnsafe(); jaroslav@1890: Class a = ForkJoinTask[].class; jaroslav@1890: ABASE = UNSAFE.arrayBaseOffset(a); jaroslav@1890: s = UNSAFE.arrayIndexScale(a); jaroslav@1890: } catch (Exception e) { jaroslav@1890: throw new Error(e); jaroslav@1890: } jaroslav@1890: if ((s & (s-1)) != 0) jaroslav@1890: throw new Error("data type scale not a power of two"); jaroslav@1890: ASHIFT = 31 - Integer.numberOfLeadingZeros(s); jaroslav@1890: } jaroslav@1890: jaroslav@1890: }