1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/utilities/taskqueue.hpp Sat Dec 01 00:00:00 2007 +0000
1.3 @@ -0,0 +1,525 @@
1.4 +/*
1.5 + * Copyright 2001-2006 Sun Microsystems, Inc. All Rights Reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or
1.24 + * have any questions.
1.25 + *
1.26 + */
1.27 +
1.28 +class TaskQueueSuper: public CHeapObj {
1.29 +protected:
1.30 + // The first free element after the last one pushed (mod _n).
1.31 + // (For now we'll assume only 32-bit CAS).
1.32 + volatile juint _bottom;
1.33 +
1.34 + // log2 of the size of the queue.
1.35 + enum SomeProtectedConstants {
1.36 + Log_n = 14
1.37 + };
1.38 +
1.39 + // Size of the queue.
1.40 + juint n() { return (1 << Log_n); }
1.41 + // For computing "x mod n" efficiently.
1.42 + juint n_mod_mask() { return n() - 1; }
1.43 +
1.44 + struct Age {
1.45 + jushort _top;
1.46 + jushort _tag;
1.47 +
1.48 + jushort tag() const { return _tag; }
1.49 + jushort top() const { return _top; }
1.50 +
1.51 + Age() { _tag = 0; _top = 0; }
1.52 +
1.53 + friend bool operator ==(const Age& a1, const Age& a2) {
1.54 + return a1.tag() == a2.tag() && a1.top() == a2.top();
1.55 + }
1.56 +
1.57 + };
1.58 + Age _age;
1.59 + // These make sure we do single atomic reads and writes.
1.60 + Age get_age() {
1.61 + jint res = *(volatile jint*)(&_age);
1.62 + return *(Age*)(&res);
1.63 + }
1.64 + void set_age(Age a) {
1.65 + *(volatile jint*)(&_age) = *(int*)(&a);
1.66 + }
1.67 +
1.68 + jushort get_top() {
1.69 + return get_age().top();
1.70 + }
1.71 +
1.72 + // These both operate mod _n.
1.73 + juint increment_index(juint ind) {
1.74 + return (ind + 1) & n_mod_mask();
1.75 + }
1.76 + juint decrement_index(juint ind) {
1.77 + return (ind - 1) & n_mod_mask();
1.78 + }
1.79 +
1.80 + // Returns a number in the range [0.._n). If the result is "n-1", it
1.81 + // should be interpreted as 0.
1.82 + juint dirty_size(juint bot, juint top) {
1.83 + return ((jint)bot - (jint)top) & n_mod_mask();
1.84 + }
1.85 +
1.86 + // Returns the size corresponding to the given "bot" and "top".
1.87 + juint size(juint bot, juint top) {
1.88 + juint sz = dirty_size(bot, top);
1.89 + // Has the queue "wrapped", so that bottom is less than top?
1.90 + // There's a complicated special case here. A pair of threads could
1.91 + // perform pop_local and pop_global operations concurrently, starting
1.92 + // from a state in which _bottom == _top+1. The pop_local could
1.93 + // succeed in decrementing _bottom, and the pop_global in incrementing
1.94 + // _top (in which case the pop_global will be awarded the contested
1.95 + // queue element.) The resulting state must be interpreted as an empty
1.96 + // queue. (We only need to worry about one such event: only the queue
1.97 + // owner performs pop_local's, and several concurrent threads
1.98 + // attempting to perform the pop_global will all perform the same CAS,
1.99 + // and only one can succeed. Any stealing thread that reads after
1.100 + // either the increment or decrement will seen an empty queue, and will
1.101 + // not join the competitors. The "sz == -1 || sz == _n-1" state will
1.102 + // not be modified by concurrent queues, so the owner thread can reset
1.103 + // the state to _bottom == top so subsequent pushes will be performed
1.104 + // normally.
1.105 + if (sz == (n()-1)) return 0;
1.106 + else return sz;
1.107 + }
1.108 +
1.109 +public:
1.110 + TaskQueueSuper() : _bottom(0), _age() {}
1.111 +
1.112 + // Return "true" if the TaskQueue contains any tasks.
1.113 + bool peek();
1.114 +
1.115 + // Return an estimate of the number of elements in the queue.
1.116 + // The "careful" version admits the possibility of pop_local/pop_global
1.117 + // races.
1.118 + juint size() {
1.119 + return size(_bottom, get_top());
1.120 + }
1.121 +
1.122 + juint dirty_size() {
1.123 + return dirty_size(_bottom, get_top());
1.124 + }
1.125 +
1.126 + // Maximum number of elements allowed in the queue. This is two less
1.127 + // than the actual queue size, for somewhat complicated reasons.
1.128 + juint max_elems() { return n() - 2; }
1.129 +
1.130 +};
1.131 +
1.132 +template<class E> class GenericTaskQueue: public TaskQueueSuper {
1.133 +private:
1.134 + // Slow paths for push, pop_local. (pop_global has no fast path.)
1.135 + bool push_slow(E t, juint dirty_n_elems);
1.136 + bool pop_local_slow(juint localBot, Age oldAge);
1.137 +
1.138 +public:
1.139 + // Initializes the queue to empty.
1.140 + GenericTaskQueue();
1.141 +
1.142 + void initialize();
1.143 +
1.144 + // Push the task "t" on the queue. Returns "false" iff the queue is
1.145 + // full.
1.146 + inline bool push(E t);
1.147 +
1.148 + // If succeeds in claiming a task (from the 'local' end, that is, the
1.149 + // most recently pushed task), returns "true" and sets "t" to that task.
1.150 + // Otherwise, the queue is empty and returns false.
1.151 + inline bool pop_local(E& t);
1.152 +
1.153 + // If succeeds in claiming a task (from the 'global' end, that is, the
1.154 + // least recently pushed task), returns "true" and sets "t" to that task.
1.155 + // Otherwise, the queue is empty and returns false.
1.156 + bool pop_global(E& t);
1.157 +
1.158 + // Delete any resource associated with the queue.
1.159 + ~GenericTaskQueue();
1.160 +
1.161 +private:
1.162 + // Element array.
1.163 + volatile E* _elems;
1.164 +};
1.165 +
1.166 +template<class E>
1.167 +GenericTaskQueue<E>::GenericTaskQueue():TaskQueueSuper() {
1.168 + assert(sizeof(Age) == sizeof(jint), "Depends on this.");
1.169 +}
1.170 +
1.171 +template<class E>
1.172 +void GenericTaskQueue<E>::initialize() {
1.173 + _elems = NEW_C_HEAP_ARRAY(E, n());
1.174 + guarantee(_elems != NULL, "Allocation failed.");
1.175 +}
1.176 +
1.177 +template<class E>
1.178 +bool GenericTaskQueue<E>::push_slow(E t, juint dirty_n_elems) {
1.179 + if (dirty_n_elems == n() - 1) {
1.180 + // Actually means 0, so do the push.
1.181 + juint localBot = _bottom;
1.182 + _elems[localBot] = t;
1.183 + _bottom = increment_index(localBot);
1.184 + return true;
1.185 + } else
1.186 + return false;
1.187 +}
1.188 +
1.189 +template<class E>
1.190 +bool GenericTaskQueue<E>::
1.191 +pop_local_slow(juint localBot, Age oldAge) {
1.192 + // This queue was observed to contain exactly one element; either this
1.193 + // thread will claim it, or a competing "pop_global". In either case,
1.194 + // the queue will be logically empty afterwards. Create a new Age value
1.195 + // that represents the empty queue for the given value of "_bottom". (We
1.196 + // must also increment "tag" because of the case where "bottom == 1",
1.197 + // "top == 0". A pop_global could read the queue element in that case,
1.198 + // then have the owner thread do a pop followed by another push. Without
1.199 + // the incrementing of "tag", the pop_global's CAS could succeed,
1.200 + // allowing it to believe it has claimed the stale element.)
1.201 + Age newAge;
1.202 + newAge._top = localBot;
1.203 + newAge._tag = oldAge.tag() + 1;
1.204 + // Perhaps a competing pop_global has already incremented "top", in which
1.205 + // case it wins the element.
1.206 + if (localBot == oldAge.top()) {
1.207 + Age tempAge;
1.208 + // No competing pop_global has yet incremented "top"; we'll try to
1.209 + // install new_age, thus claiming the element.
1.210 + assert(sizeof(Age) == sizeof(jint) && sizeof(jint) == sizeof(juint),
1.211 + "Assumption about CAS unit.");
1.212 + *(jint*)&tempAge = Atomic::cmpxchg(*(jint*)&newAge, (volatile jint*)&_age, *(jint*)&oldAge);
1.213 + if (tempAge == oldAge) {
1.214 + // We win.
1.215 + assert(dirty_size(localBot, get_top()) != n() - 1,
1.216 + "Shouldn't be possible...");
1.217 + return true;
1.218 + }
1.219 + }
1.220 + // We fail; a completing pop_global gets the element. But the queue is
1.221 + // empty (and top is greater than bottom.) Fix this representation of
1.222 + // the empty queue to become the canonical one.
1.223 + set_age(newAge);
1.224 + assert(dirty_size(localBot, get_top()) != n() - 1,
1.225 + "Shouldn't be possible...");
1.226 + return false;
1.227 +}
1.228 +
1.229 +template<class E>
1.230 +bool GenericTaskQueue<E>::pop_global(E& t) {
1.231 + Age newAge;
1.232 + Age oldAge = get_age();
1.233 + juint localBot = _bottom;
1.234 + juint n_elems = size(localBot, oldAge.top());
1.235 + if (n_elems == 0) {
1.236 + return false;
1.237 + }
1.238 + t = _elems[oldAge.top()];
1.239 + newAge = oldAge;
1.240 + newAge._top = increment_index(newAge.top());
1.241 + if ( newAge._top == 0 ) newAge._tag++;
1.242 + Age resAge;
1.243 + *(jint*)&resAge = Atomic::cmpxchg(*(jint*)&newAge, (volatile jint*)&_age, *(jint*)&oldAge);
1.244 + // Note that using "_bottom" here might fail, since a pop_local might
1.245 + // have decremented it.
1.246 + assert(dirty_size(localBot, newAge._top) != n() - 1,
1.247 + "Shouldn't be possible...");
1.248 + return (resAge == oldAge);
1.249 +}
1.250 +
1.251 +template<class E>
1.252 +GenericTaskQueue<E>::~GenericTaskQueue() {
1.253 + FREE_C_HEAP_ARRAY(E, _elems);
1.254 +}
1.255 +
1.256 +// Inherits the typedef of "Task" from above.
1.257 +class TaskQueueSetSuper: public CHeapObj {
1.258 +protected:
1.259 + static int randomParkAndMiller(int* seed0);
1.260 +public:
1.261 + // Returns "true" if some TaskQueue in the set contains a task.
1.262 + virtual bool peek() = 0;
1.263 +};
1.264 +
1.265 +template<class E> class GenericTaskQueueSet: public TaskQueueSetSuper {
1.266 +private:
1.267 + int _n;
1.268 + GenericTaskQueue<E>** _queues;
1.269 +
1.270 +public:
1.271 + GenericTaskQueueSet(int n) : _n(n) {
1.272 + typedef GenericTaskQueue<E>* GenericTaskQueuePtr;
1.273 + _queues = NEW_C_HEAP_ARRAY(GenericTaskQueuePtr, n);
1.274 + guarantee(_queues != NULL, "Allocation failure.");
1.275 + for (int i = 0; i < n; i++) {
1.276 + _queues[i] = NULL;
1.277 + }
1.278 + }
1.279 +
1.280 + bool steal_1_random(int queue_num, int* seed, E& t);
1.281 + bool steal_best_of_2(int queue_num, int* seed, E& t);
1.282 + bool steal_best_of_all(int queue_num, int* seed, E& t);
1.283 +
1.284 + void register_queue(int i, GenericTaskQueue<E>* q);
1.285 +
1.286 + GenericTaskQueue<E>* queue(int n);
1.287 +
1.288 + // The thread with queue number "queue_num" (and whose random number seed
1.289 + // is at "seed") is trying to steal a task from some other queue. (It
1.290 + // may try several queues, according to some configuration parameter.)
1.291 + // If some steal succeeds, returns "true" and sets "t" the stolen task,
1.292 + // otherwise returns false.
1.293 + bool steal(int queue_num, int* seed, E& t);
1.294 +
1.295 + bool peek();
1.296 +};
1.297 +
1.298 +template<class E>
1.299 +void GenericTaskQueueSet<E>::register_queue(int i, GenericTaskQueue<E>* q) {
1.300 + assert(0 <= i && i < _n, "index out of range.");
1.301 + _queues[i] = q;
1.302 +}
1.303 +
1.304 +template<class E>
1.305 +GenericTaskQueue<E>* GenericTaskQueueSet<E>::queue(int i) {
1.306 + return _queues[i];
1.307 +}
1.308 +
1.309 +template<class E>
1.310 +bool GenericTaskQueueSet<E>::steal(int queue_num, int* seed, E& t) {
1.311 + for (int i = 0; i < 2 * _n; i++)
1.312 + if (steal_best_of_2(queue_num, seed, t))
1.313 + return true;
1.314 + return false;
1.315 +}
1.316 +
1.317 +template<class E>
1.318 +bool GenericTaskQueueSet<E>::steal_best_of_all(int queue_num, int* seed, E& t) {
1.319 + if (_n > 2) {
1.320 + int best_k;
1.321 + jint best_sz = 0;
1.322 + for (int k = 0; k < _n; k++) {
1.323 + if (k == queue_num) continue;
1.324 + jint sz = _queues[k]->size();
1.325 + if (sz > best_sz) {
1.326 + best_sz = sz;
1.327 + best_k = k;
1.328 + }
1.329 + }
1.330 + return best_sz > 0 && _queues[best_k]->pop_global(t);
1.331 + } else if (_n == 2) {
1.332 + // Just try the other one.
1.333 + int k = (queue_num + 1) % 2;
1.334 + return _queues[k]->pop_global(t);
1.335 + } else {
1.336 + assert(_n == 1, "can't be zero.");
1.337 + return false;
1.338 + }
1.339 +}
1.340 +
1.341 +template<class E>
1.342 +bool GenericTaskQueueSet<E>::steal_1_random(int queue_num, int* seed, E& t) {
1.343 + if (_n > 2) {
1.344 + int k = queue_num;
1.345 + while (k == queue_num) k = randomParkAndMiller(seed) % _n;
1.346 + return _queues[2]->pop_global(t);
1.347 + } else if (_n == 2) {
1.348 + // Just try the other one.
1.349 + int k = (queue_num + 1) % 2;
1.350 + return _queues[k]->pop_global(t);
1.351 + } else {
1.352 + assert(_n == 1, "can't be zero.");
1.353 + return false;
1.354 + }
1.355 +}
1.356 +
1.357 +template<class E>
1.358 +bool GenericTaskQueueSet<E>::steal_best_of_2(int queue_num, int* seed, E& t) {
1.359 + if (_n > 2) {
1.360 + int k1 = queue_num;
1.361 + while (k1 == queue_num) k1 = randomParkAndMiller(seed) % _n;
1.362 + int k2 = queue_num;
1.363 + while (k2 == queue_num || k2 == k1) k2 = randomParkAndMiller(seed) % _n;
1.364 + // Sample both and try the larger.
1.365 + juint sz1 = _queues[k1]->size();
1.366 + juint sz2 = _queues[k2]->size();
1.367 + if (sz2 > sz1) return _queues[k2]->pop_global(t);
1.368 + else return _queues[k1]->pop_global(t);
1.369 + } else if (_n == 2) {
1.370 + // Just try the other one.
1.371 + int k = (queue_num + 1) % 2;
1.372 + return _queues[k]->pop_global(t);
1.373 + } else {
1.374 + assert(_n == 1, "can't be zero.");
1.375 + return false;
1.376 + }
1.377 +}
1.378 +
1.379 +template<class E>
1.380 +bool GenericTaskQueueSet<E>::peek() {
1.381 + // Try all the queues.
1.382 + for (int j = 0; j < _n; j++) {
1.383 + if (_queues[j]->peek())
1.384 + return true;
1.385 + }
1.386 + return false;
1.387 +}
1.388 +
1.389 +// A class to aid in the termination of a set of parallel tasks using
1.390 +// TaskQueueSet's for work stealing.
1.391 +
1.392 +class ParallelTaskTerminator: public StackObj {
1.393 +private:
1.394 + int _n_threads;
1.395 + TaskQueueSetSuper* _queue_set;
1.396 + jint _offered_termination;
1.397 +
1.398 + bool peek_in_queue_set();
1.399 +protected:
1.400 + virtual void yield();
1.401 + void sleep(uint millis);
1.402 +
1.403 +public:
1.404 +
1.405 + // "n_threads" is the number of threads to be terminated. "queue_set" is a
1.406 + // queue sets of work queues of other threads.
1.407 + ParallelTaskTerminator(int n_threads, TaskQueueSetSuper* queue_set);
1.408 +
1.409 + // The current thread has no work, and is ready to terminate if everyone
1.410 + // else is. If returns "true", all threads are terminated. If returns
1.411 + // "false", available work has been observed in one of the task queues,
1.412 + // so the global task is not complete.
1.413 + bool offer_termination();
1.414 +
1.415 + // Reset the terminator, so that it may be reused again.
1.416 + // The caller is responsible for ensuring that this is done
1.417 + // in an MT-safe manner, once the previous round of use of
1.418 + // the terminator is finished.
1.419 + void reset_for_reuse();
1.420 +
1.421 +};
1.422 +
1.423 +#define SIMPLE_STACK 0
1.424 +
1.425 +template<class E> inline bool GenericTaskQueue<E>::push(E t) {
1.426 +#if SIMPLE_STACK
1.427 + juint localBot = _bottom;
1.428 + if (_bottom < max_elems()) {
1.429 + _elems[localBot] = t;
1.430 + _bottom = localBot + 1;
1.431 + return true;
1.432 + } else {
1.433 + return false;
1.434 + }
1.435 +#else
1.436 + juint localBot = _bottom;
1.437 + assert((localBot >= 0) && (localBot < n()), "_bottom out of range.");
1.438 + jushort top = get_top();
1.439 + juint dirty_n_elems = dirty_size(localBot, top);
1.440 + assert((dirty_n_elems >= 0) && (dirty_n_elems < n()),
1.441 + "n_elems out of range.");
1.442 + if (dirty_n_elems < max_elems()) {
1.443 + _elems[localBot] = t;
1.444 + _bottom = increment_index(localBot);
1.445 + return true;
1.446 + } else {
1.447 + return push_slow(t, dirty_n_elems);
1.448 + }
1.449 +#endif
1.450 +}
1.451 +
1.452 +template<class E> inline bool GenericTaskQueue<E>::pop_local(E& t) {
1.453 +#if SIMPLE_STACK
1.454 + juint localBot = _bottom;
1.455 + assert(localBot > 0, "precondition.");
1.456 + localBot--;
1.457 + t = _elems[localBot];
1.458 + _bottom = localBot;
1.459 + return true;
1.460 +#else
1.461 + juint localBot = _bottom;
1.462 + // This value cannot be n-1. That can only occur as a result of
1.463 + // the assignment to bottom in this method. If it does, this method
1.464 + // resets the size( to 0 before the next call (which is sequential,
1.465 + // since this is pop_local.)
1.466 + juint dirty_n_elems = dirty_size(localBot, get_top());
1.467 + assert(dirty_n_elems != n() - 1, "Shouldn't be possible...");
1.468 + if (dirty_n_elems == 0) return false;
1.469 + localBot = decrement_index(localBot);
1.470 + _bottom = localBot;
1.471 + // This is necessary to prevent any read below from being reordered
1.472 + // before the store just above.
1.473 + OrderAccess::fence();
1.474 + t = _elems[localBot];
1.475 + // This is a second read of "age"; the "size()" above is the first.
1.476 + // If there's still at least one element in the queue, based on the
1.477 + // "_bottom" and "age" we've read, then there can be no interference with
1.478 + // a "pop_global" operation, and we're done.
1.479 + juint tp = get_top();
1.480 + if (size(localBot, tp) > 0) {
1.481 + assert(dirty_size(localBot, tp) != n() - 1,
1.482 + "Shouldn't be possible...");
1.483 + return true;
1.484 + } else {
1.485 + // Otherwise, the queue contained exactly one element; we take the slow
1.486 + // path.
1.487 + return pop_local_slow(localBot, get_age());
1.488 + }
1.489 +#endif
1.490 +}
1.491 +
1.492 +typedef oop Task;
1.493 +typedef GenericTaskQueue<Task> OopTaskQueue;
1.494 +typedef GenericTaskQueueSet<Task> OopTaskQueueSet;
1.495 +
1.496 +typedef oop* StarTask;
1.497 +typedef GenericTaskQueue<StarTask> OopStarTaskQueue;
1.498 +typedef GenericTaskQueueSet<StarTask> OopStarTaskQueueSet;
1.499 +
1.500 +typedef size_t ChunkTask; // index for chunk
1.501 +typedef GenericTaskQueue<ChunkTask> ChunkTaskQueue;
1.502 +typedef GenericTaskQueueSet<ChunkTask> ChunkTaskQueueSet;
1.503 +
1.504 +class ChunkTaskQueueWithOverflow: public CHeapObj {
1.505 + protected:
1.506 + ChunkTaskQueue _chunk_queue;
1.507 + GrowableArray<ChunkTask>* _overflow_stack;
1.508 +
1.509 + public:
1.510 + ChunkTaskQueueWithOverflow() : _overflow_stack(NULL) {}
1.511 + // Initialize both stealable queue and overflow
1.512 + void initialize();
1.513 + // Save first to stealable queue and then to overflow
1.514 + void save(ChunkTask t);
1.515 + // Retrieve first from overflow and then from stealable queue
1.516 + bool retrieve(ChunkTask& chunk_index);
1.517 + // Retrieve from stealable queue
1.518 + bool retrieve_from_stealable_queue(ChunkTask& chunk_index);
1.519 + // Retrieve from overflow
1.520 + bool retrieve_from_overflow(ChunkTask& chunk_index);
1.521 + bool is_empty();
1.522 + bool stealable_is_empty();
1.523 + bool overflow_is_empty();
1.524 + juint stealable_size() { return _chunk_queue.size(); }
1.525 + ChunkTaskQueue* task_queue() { return &_chunk_queue; }
1.526 +};
1.527 +
1.528 +#define USE_ChunkTaskQueueWithOverflow
