2273N/A * Copyright (c) 2001, 2011, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 0N/A * published by the Free Software Foundation. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1472N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 1585N/A// Simple TaskQueue stats that are collected by default in debug builds. 1629N/A // Print the specified line of the header (does not include a line separator). 1629N/A // Print the statistics (does not include a line separator). 907N/A // Internal type for indexing the queue; also used for the tag. 907N/A // The first free element after the last one pushed (mod N). 907N/A // Increment top; if it wraps, increment tag also. 907N/A // These both operate mod N. 907N/A // Returns a number in the range [0..N). If the result is "N-1", it should be 0N/A // Returns the size corresponding to the given "bot" and "top". 907N/A // Has the queue "wrapped", so that bottom is less than top? There's a 907N/A // complicated special case here. A pair of threads could perform pop_local 907N/A // and pop_global operations concurrently, starting from a state in which 907N/A // _bottom == _top+1. The pop_local could succeed in decrementing _bottom, 907N/A // and the pop_global in incrementing _top (in which case the pop_global 907N/A // will be awarded the contested queue element.) The resulting state must 907N/A // be interpreted as an empty queue. (We only need to worry about one such 907N/A // event: only the queue owner performs pop_local's, and several concurrent 907N/A // threads attempting to perform the pop_global will all perform the same 907N/A // CAS, and only one can succeed.) Any stealing thread that reads after 907N/A // either the increment or decrement will see an empty queue, and will not 907N/A // join the competitors. The "sz == -1 || sz == N-1" state will not be 907N/A // modified by concurrent queues, so the owner thread can reset the state to 907N/A // _bottom == top so subsequent pushes will be performed normally. 0N/A // Return an estimate of the number of elements in the queue. 0N/A // Maximum number of elements allowed in the queue. This is two less 0N/A // than the actual queue size, for somewhat complicated reasons. 0N/A // Slow paths for push, pop_local. (pop_global has no fast path.) 0N/A // Initializes the queue to empty. 1558N/A // Push the task "t" on the queue. Returns "false" iff the queue is full. 1558N/A // Attempts to claim a task from the "local" end of the queue (the most 1558N/A // recently pushed). If successful, returns true and sets t to the task; 1558N/A // otherwise, returns false (the queue is empty). 1558N/A // Like pop_local(), but uses the "global" end of the queue (the least 0N/A // Delete any resource associated with the queue. 342N/A // apply the closure to all elements in the task queue 342N/A // tty->print_cr("START OopTaskQueue::oops_do"); 342N/A // tty->print_cr(" doing entry %d," INTPTR_T " -> " INTPTR_T, 342N/A // index, &_elems[index], _elems[index]); 342N/A // tty->print_cr("END OopTaskQueue::oops_do"); 0N/A // Actually means 0, so do the push. 1311N/A // g++ complains if the volatile result of the assignment is unused. 1753N/A// pop_local_slow() is done by the owning thread and is trying to 1753N/A// get the last task in the queue. It will compete with pop_global() 1753N/A// that will be used by other threads. The tag age is incremented 1753N/A// whenever the queue goes empty which it will do here if this thread 1753N/A// gets the last task or in pop_global() if the queue wraps (top == 0 1753N/A// and pop_global() succeeds, see pop_global()). 0N/A // This queue was observed to contain exactly one element; either this 0N/A // thread will claim it, or a competing "pop_global". In either case, 0N/A // the queue will be logically empty afterwards. Create a new Age value 0N/A // that represents the empty queue for the given value of "_bottom". (We 0N/A // must also increment "tag" because of the case where "bottom == 1", 0N/A // "top == 0". A pop_global could read the queue element in that case, 0N/A // then have the owner thread do a pop followed by another push. Without 0N/A // the incrementing of "tag", the pop_global's CAS could succeed, 0N/A // allowing it to believe it has claimed the stale element.) 0N/A // Perhaps a competing pop_global has already incremented "top", in which 0N/A // case it wins the element. 0N/A // No competing pop_global has yet incremented "top"; we'll try to 0N/A // install new_age, thus claiming the element. 907N/A // We lose; a completing pop_global gets the element. But the queue is empty 907N/A // and top is greater than bottom. Fix this representation of the empty queue 907N/A // to become the canonical one. 0N/A // Note that using "_bottom" here might fail, since a pop_local might 0N/A // have decremented it. 1558N/A// OverflowTaskQueue is a TaskQueue that also includes an overflow stack for 1558N/A// elements that do not fit in the TaskQueue. 1756N/A// This class hides two methods from super classes: 1558N/A// push() - push onto the task queue or, if that fails, onto the overflow stack 1558N/A// is_empty() - return true if both the TaskQueue and overflow stack are empty 1756N/A// Note that size() is not hidden--it returns the number of elements in the 1558N/A// TaskQueue, and does not include the size of the overflow stack. This 1558N/A// simplifies replacement of GenericTaskQueues with OverflowTaskQueues. 1558N/A // Push task t onto the queue or onto the overflow stack. Return true. 1558N/A // Attempt to pop from the overflow stack; return true if anything was popped. 0N/A // Returns "true" if some TaskQueue in the set contains a task. 0N/A for (
int i = 0; i < n; i++) {
1558N/A // The thread with queue number "queue_num" (and whose random number seed is 1558N/A // at "seed") is trying to steal a task from some other queue. (It may try 1558N/A // several queues, according to some configuration parameter.) If some steal 1558N/A // succeeds, returns "true" and sets "t" to the stolen task, otherwise returns 0N/A // Just try the other one. 0N/A // Just try the other one. 0N/A // Sample both and try the larger. 0N/A // Just try the other one. 0N/A // Try all the queues. 342N/A// When to terminate from the termination protocol. 0N/A// A class to aid in the termination of a set of parallel tasks using 0N/A// TaskQueueSet's for work stealing. 0N/A // "n_threads" is the number of threads to be terminated. "queue_set" is a 0N/A // queue sets of work queues of other threads. 0N/A // The current thread has no work, and is ready to terminate if everyone 0N/A // else is. If returns "true", all threads are terminated. If returns 0N/A // "false", available work has been observed in one of the task queues, 0N/A // so the global task is not complete. 907N/A // As above, but it also terminates if the should_exit_termination() 342N/A // method of the terminator parameter returns true. If terminator is 342N/A // NULL, then it is ignored. 0N/A // Reset the terminator, so that it may be reused again. 0N/A // The caller is responsible for ensuring that this is done 0N/A // in an MT-safe manner, once the previous round of use of 0N/A // the terminator is finished. 1753N/A // Same as above but the number of parallel threads is set to the 1311N/A // g++ complains if the volatile result of the assignment is unused. 907N/A // This value cannot be N-1. That can only occur as a result of 0N/A // the assignment to bottom in this method. If it does, this method 1558N/A // resets the size to 0 before the next call (which is sequential, 0N/A // since this is pop_local.) 0N/A // This is necessary to prevent any read below from being reordered 0N/A // before the store just above. 0N/A // This is a second read of "age"; the "size()" above is the first. 0N/A // If there's still at least one element in the queue, based on the 0N/A // "_bottom" and "age" we've read, then there can be no interference with 0N/A // a "pop_global" operation, and we're done. 0N/A // Otherwise, the queue contained exactly one element; we take the slow 1311N/A// warning C4522: multiple assignment operators specified 113N/A// This is a container class for either an oop* or a narrowOop*. 113N/A// Both are pushed onto a task queue and the consumer will test is_narrow() 113N/A// to determine which should be processed. 1879N/A#
endif // SHARE_VM_UTILITIES_TASKQUEUE_HPP