1 /* 2 * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 // Simple TaskQueue stats that are collected by default in debug builds. 26 27 #if !defined(TASKQUEUE_STATS) && defined(ASSERT) 28 #define TASKQUEUE_STATS 1 29 #elif !defined(TASKQUEUE_STATS) 30 #define TASKQUEUE_STATS 0 31 #endif 32 33 #if TASKQUEUE_STATS 34 #define TASKQUEUE_STATS_ONLY(code) code 35 #else 36 #define TASKQUEUE_STATS_ONLY(code) 37 #endif // TASKQUEUE_STATS 38 39 #if TASKQUEUE_STATS 40 class TaskQueueStats { 41 public: 42 enum StatId { 43 push, // number of taskqueue pushes 44 pop, // number of taskqueue pops 45 pop_slow, // subset of taskqueue pops that were done slow-path 46 steal_attempt, // number of taskqueue steal attempts 47 steal, // number of taskqueue steals 48 overflow, // number of overflow pushes 49 overflow_max_len, // max length of overflow stack 50 last_stat_id 51 }; 52 53 public: 54 inline TaskQueueStats() { reset(); } 55 56 inline void record_push() { ++_stats[push]; } 57 inline void record_pop() { ++_stats[pop]; } 58 inline void record_pop_slow() { record_pop(); ++_stats[pop_slow]; } 59 inline void record_steal(bool success); 60 inline void record_overflow(size_t new_length); 61 62 TaskQueueStats & operator +=(const TaskQueueStats & addend); 63 64 inline size_t get(StatId id) const { return _stats[id]; } 65 inline const size_t* get() const { return _stats; } 66 67 inline void reset(); 68 69 // Print the specified line of the header (does not include a line separator). 70 static void print_header(unsigned int line, outputStream* const stream = tty, 71 unsigned int width = 10); 72 // Print the statistics (does not include a line separator). 73 void print(outputStream* const stream = tty, unsigned int width = 10) const; 74 75 DEBUG_ONLY(void verify() const;) 76 77 private: 78 size_t _stats[last_stat_id]; 79 static const char * const _names[last_stat_id]; 80 }; 81 82 void TaskQueueStats::record_steal(bool success) { 83 ++_stats[steal_attempt]; 84 if (success) ++_stats[steal]; 85 } 86 87 void TaskQueueStats::record_overflow(size_t new_len) { 88 ++_stats[overflow]; 89 if (new_len > _stats[overflow_max_len]) _stats[overflow_max_len] = new_len; 90 } 91 92 void TaskQueueStats::reset() { 93 memset(_stats, 0, sizeof(_stats)); 94 } 95 #endif // TASKQUEUE_STATS 96 97 template <unsigned int N> 98 class TaskQueueSuper: public CHeapObj { 99 protected: 100 // Internal type for indexing the queue; also used for the tag. 101 typedef NOT_LP64(uint16_t) LP64_ONLY(uint32_t) idx_t; 102 103 // The first free element after the last one pushed (mod N). 104 volatile uint _bottom; 105 106 enum { MOD_N_MASK = N - 1 }; 107 108 class Age { 109 public: 110 Age(size_t data = 0) { _data = data; } 111 Age(const Age& age) { _data = age._data; } 112 Age(idx_t top, idx_t tag) { _fields._top = top; _fields._tag = tag; } 113 114 Age get() const volatile { return _data; } 115 void set(Age age) volatile { _data = age._data; } 116 117 idx_t top() const volatile { return _fields._top; } 118 idx_t tag() const volatile { return _fields._tag; } 119 120 // Increment top; if it wraps, increment tag also. 121 void increment() { 122 _fields._top = increment_index(_fields._top); 123 if (_fields._top == 0) ++_fields._tag; 124 } 125 126 Age cmpxchg(const Age new_age, const Age old_age) volatile { 127 return (size_t) Atomic::cmpxchg_ptr((intptr_t)new_age._data, 128 (volatile intptr_t *)&_data, 129 (intptr_t)old_age._data); 130 } 131 132 bool operator ==(const Age& other) const { return _data == other._data; } 133 134 private: 135 struct fields { 136 idx_t _top; 137 idx_t _tag; 138 }; 139 union { 140 size_t _data; 141 fields _fields; 142 }; 143 }; 144 145 volatile Age _age; 146 147 // These both operate mod N. 148 static uint increment_index(uint ind) { 149 return (ind + 1) & MOD_N_MASK; 150 } 151 static uint decrement_index(uint ind) { 152 return (ind - 1) & MOD_N_MASK; 153 } 154 155 // Returns a number in the range [0..N). If the result is "N-1", it should be 156 // interpreted as 0. 157 uint dirty_size(uint bot, uint top) const { 158 return (bot - top) & MOD_N_MASK; 159 } 160 161 // Returns the size corresponding to the given "bot" and "top". 162 uint size(uint bot, uint top) const { 163 uint sz = dirty_size(bot, top); 164 // Has the queue "wrapped", so that bottom is less than top? There's a 165 // complicated special case here. A pair of threads could perform pop_local 166 // and pop_global operations concurrently, starting from a state in which 167 // _bottom == _top+1. The pop_local could succeed in decrementing _bottom, 168 // and the pop_global in incrementing _top (in which case the pop_global 169 // will be awarded the contested queue element.) The resulting state must 170 // be interpreted as an empty queue. (We only need to worry about one such 171 // event: only the queue owner performs pop_local's, and several concurrent 172 // threads attempting to perform the pop_global will all perform the same 173 // CAS, and only one can succeed.) Any stealing thread that reads after 174 // either the increment or decrement will see an empty queue, and will not 175 // join the competitors. The "sz == -1 || sz == N-1" state will not be 176 // modified by concurrent queues, so the owner thread can reset the state to 177 // _bottom == top so subsequent pushes will be performed normally. 178 return (sz == N - 1) ? 0 : sz; 179 } 180 181 public: 182 TaskQueueSuper() : _bottom(0), _age() {} 183 184 // Return true if the TaskQueue contains/does not contain any tasks. 185 bool peek() const { return _bottom != _age.top(); } 186 bool is_empty() const { return size() == 0; } 187 188 // Return an estimate of the number of elements in the queue. 189 // The "careful" version admits the possibility of pop_local/pop_global 190 // races. 191 uint size() const { 192 return size(_bottom, _age.top()); 193 } 194 195 uint dirty_size() const { 196 return dirty_size(_bottom, _age.top()); 197 } 198 199 void set_empty() { 200 _bottom = 0; 201 _age.set(0); 202 } 203 204 // Maximum number of elements allowed in the queue. This is two less 205 // than the actual queue size, for somewhat complicated reasons. 206 uint max_elems() const { return N - 2; } 207 208 // Total size of queue. 209 static const uint total_size() { return N; } 210 211 TASKQUEUE_STATS_ONLY(TaskQueueStats stats;) 212 }; 213 214 template<class E, unsigned int N = TASKQUEUE_SIZE> 215 class GenericTaskQueue: public TaskQueueSuper<N> { 216 protected: 217 typedef typename TaskQueueSuper<N>::Age Age; 218 typedef typename TaskQueueSuper<N>::idx_t idx_t; 219 220 using TaskQueueSuper<N>::_bottom; 221 using TaskQueueSuper<N>::_age; 222 using TaskQueueSuper<N>::increment_index; 223 using TaskQueueSuper<N>::decrement_index; 224 using TaskQueueSuper<N>::dirty_size; 225 226 public: 227 using TaskQueueSuper<N>::max_elems; 228 using TaskQueueSuper<N>::size; 229 TASKQUEUE_STATS_ONLY(using TaskQueueSuper<N>::stats;) 230 231 private: 232 // Slow paths for push, pop_local. (pop_global has no fast path.) 233 bool push_slow(E t, uint dirty_n_elems); 234 bool pop_local_slow(uint localBot, Age oldAge); 235 236 public: 237 typedef E element_type; 238 239 // Initializes the queue to empty. 240 GenericTaskQueue(); 241 242 void initialize(); 243 244 // Push the task "t" on the queue. Returns "false" iff the queue is full. 245 inline bool push(E t); 246 247 // Attempts to claim a task from the "local" end of the queue (the most 248 // recently pushed). If successful, returns true and sets t to the task; 249 // otherwise, returns false (the queue is empty). 250 inline bool pop_local(E& t); 251 252 // Like pop_local(), but uses the "global" end of the queue (the least 253 // recently pushed). 254 bool pop_global(E& t); 255 256 // Delete any resource associated with the queue. 257 ~GenericTaskQueue(); 258 259 // apply the closure to all elements in the task queue 260 void oops_do(OopClosure* f); 261 262 private: 263 // Element array. 264 volatile E* _elems; 265 }; 266 267 template<class E, unsigned int N> 268 GenericTaskQueue<E, N>::GenericTaskQueue() { 269 assert(sizeof(Age) == sizeof(size_t), "Depends on this."); 270 } 271 272 template<class E, unsigned int N> 273 void GenericTaskQueue<E, N>::initialize() { 274 _elems = NEW_C_HEAP_ARRAY(E, N); 275 } 276 277 template<class E, unsigned int N> 278 void GenericTaskQueue<E, N>::oops_do(OopClosure* f) { 279 // tty->print_cr("START OopTaskQueue::oops_do"); 280 uint iters = size(); 281 uint index = _bottom; 282 for (uint i = 0; i < iters; ++i) { 283 index = decrement_index(index); 284 // tty->print_cr(" doing entry %d," INTPTR_T " -> " INTPTR_T, 285 // index, &_elems[index], _elems[index]); 286 E* t = (E*)&_elems[index]; // cast away volatility 287 oop* p = (oop*)t; 288 assert((*t)->is_oop_or_null(), "Not an oop or null"); 289 f->do_oop(p); 290 } 291 // tty->print_cr("END OopTaskQueue::oops_do"); 292 } 293 294 template<class E, unsigned int N> 295 bool GenericTaskQueue<E, N>::push_slow(E t, uint dirty_n_elems) { 296 if (dirty_n_elems == N - 1) { 297 // Actually means 0, so do the push. 298 uint localBot = _bottom; 299 // g++ complains if the volatile result of the assignment is unused. 300 const_cast<E&>(_elems[localBot] = t); 301 OrderAccess::release_store(&_bottom, increment_index(localBot)); 302 TASKQUEUE_STATS_ONLY(stats.record_push()); 303 return true; 304 } 305 return false; 306 } 307 308 // pop_local_slow() is done by the owning thread and is trying to 309 // get the last task in the queue. It will compete with pop_global() 310 // that will be used by other threads. The tag age is incremented 311 // whenever the queue goes empty which it will do here if this thread 312 // gets the last task or in pop_global() if the queue wraps (top == 0 313 // and pop_global() succeeds, see pop_global()). 314 template<class E, unsigned int N> 315 bool GenericTaskQueue<E, N>::pop_local_slow(uint localBot, Age oldAge) { 316 // This queue was observed to contain exactly one element; either this 317 // thread will claim it, or a competing "pop_global". In either case, 318 // the queue will be logically empty afterwards. Create a new Age value 319 // that represents the empty queue for the given value of "_bottom". (We 320 // must also increment "tag" because of the case where "bottom == 1", 321 // "top == 0". A pop_global could read the queue element in that case, 322 // then have the owner thread do a pop followed by another push. Without 323 // the incrementing of "tag", the pop_global's CAS could succeed, 324 // allowing it to believe it has claimed the stale element.) 325 Age newAge((idx_t)localBot, oldAge.tag() + 1); 326 // Perhaps a competing pop_global has already incremented "top", in which 327 // case it wins the element. 328 if (localBot == oldAge.top()) { 329 // No competing pop_global has yet incremented "top"; we'll try to 330 // install new_age, thus claiming the element. 331 Age tempAge = _age.cmpxchg(newAge, oldAge); 332 if (tempAge == oldAge) { 333 // We win. 334 assert(dirty_size(localBot, _age.top()) != N - 1, "sanity"); 335 TASKQUEUE_STATS_ONLY(stats.record_pop_slow()); 336 return true; 337 } 338 } 339 // We lose; a completing pop_global gets the element. But the queue is empty 340 // and top is greater than bottom. Fix this representation of the empty queue 341 // to become the canonical one. 342 _age.set(newAge); 343 assert(dirty_size(localBot, _age.top()) != N - 1, "sanity"); 344 return false; 345 } 346 347 template<class E, unsigned int N> 348 bool GenericTaskQueue<E, N>::pop_global(E& t) { 349 Age oldAge = _age.get(); 350 uint localBot = _bottom; 351 uint n_elems = size(localBot, oldAge.top()); 352 if (n_elems == 0) { 353 return false; 354 } 355 356 const_cast<E&>(t = _elems[oldAge.top()]); 357 Age newAge(oldAge); 358 newAge.increment(); 359 Age resAge = _age.cmpxchg(newAge, oldAge); 360 361 // Note that using "_bottom" here might fail, since a pop_local might 362 // have decremented it. 363 assert(dirty_size(localBot, newAge.top()) != N - 1, "sanity"); 364 return resAge == oldAge; 365 } 366 367 template<class E, unsigned int N> 368 GenericTaskQueue<E, N>::~GenericTaskQueue() { 369 FREE_C_HEAP_ARRAY(E, _elems); 370 } 371 372 // OverflowTaskQueue is a TaskQueue that also includes an overflow stack for 373 // elements that do not fit in the TaskQueue. 374 // 375 // This class hides two methods from super classes: 376 // 377 // push() - push onto the task queue or, if that fails, onto the overflow stack 378 // is_empty() - return true if both the TaskQueue and overflow stack are empty 379 // 380 // Note that size() is not hidden--it returns the number of elements in the 381 // TaskQueue, and does not include the size of the overflow stack. This 382 // simplifies replacement of GenericTaskQueues with OverflowTaskQueues. 383 template<class E, unsigned int N = TASKQUEUE_SIZE> 384 class OverflowTaskQueue: public GenericTaskQueue<E, N> 385 { 386 public: 387 typedef Stack<E> overflow_t; 388 typedef GenericTaskQueue<E, N> taskqueue_t; 389 390 TASKQUEUE_STATS_ONLY(using taskqueue_t::stats;) 391 392 // Push task t onto the queue or onto the overflow stack. Return true. 393 inline bool push(E t); 394 395 // Attempt to pop from the overflow stack; return true if anything was popped. 396 inline bool pop_overflow(E& t); 397 398 inline overflow_t* overflow_stack() { return &_overflow_stack; } 399 400 inline bool taskqueue_empty() const { return taskqueue_t::is_empty(); } 401 inline bool overflow_empty() const { return _overflow_stack.is_empty(); } 402 inline bool is_empty() const { 403 return taskqueue_empty() && overflow_empty(); 404 } 405 406 private: 407 overflow_t _overflow_stack; 408 }; 409 410 template <class E, unsigned int N> 411 bool OverflowTaskQueue<E, N>::push(E t) 412 { 413 if (!taskqueue_t::push(t)) { 414 overflow_stack()->push(t); 415 TASKQUEUE_STATS_ONLY(stats.record_overflow(overflow_stack()->size())); 416 } 417 return true; 418 } 419 420 template <class E, unsigned int N> 421 bool OverflowTaskQueue<E, N>::pop_overflow(E& t) 422 { 423 if (overflow_empty()) return false; 424 t = overflow_stack()->pop(); 425 return true; 426 } 427 428 class TaskQueueSetSuper: public CHeapObj { 429 protected: 430 static int randomParkAndMiller(int* seed0); 431 public: 432 // Returns "true" if some TaskQueue in the set contains a task. 433 virtual bool peek() = 0; 434 }; 435 436 template<class T> 437 class GenericTaskQueueSet: public TaskQueueSetSuper { 438 private: 439 uint _n; 440 T** _queues; 441 442 public: 443 typedef typename T::element_type E; 444 445 GenericTaskQueueSet(int n) : _n(n) { 446 typedef T* GenericTaskQueuePtr; 447 _queues = NEW_C_HEAP_ARRAY(GenericTaskQueuePtr, n); 448 for (int i = 0; i < n; i++) { 449 _queues[i] = NULL; 450 } 451 } 452 453 bool steal_1_random(uint queue_num, int* seed, E& t); 454 bool steal_best_of_2(uint queue_num, int* seed, E& t); 455 bool steal_best_of_all(uint queue_num, int* seed, E& t); 456 457 void register_queue(uint i, T* q); 458 459 T* queue(uint n); 460 461 // The thread with queue number "queue_num" (and whose random number seed is 462 // at "seed") is trying to steal a task from some other queue. (It may try 463 // several queues, according to some configuration parameter.) If some steal 464 // succeeds, returns "true" and sets "t" to the stolen task, otherwise returns 465 // false. 466 bool steal(uint queue_num, int* seed, E& t); 467 468 bool peek(); 469 }; 470 471 template<class T> void 472 GenericTaskQueueSet<T>::register_queue(uint i, T* q) { 473 assert(i < _n, "index out of range."); 474 _queues[i] = q; 475 } 476 477 template<class T> T* 478 GenericTaskQueueSet<T>::queue(uint i) { 479 return _queues[i]; 480 } 481 482 template<class T> bool 483 GenericTaskQueueSet<T>::steal(uint queue_num, int* seed, E& t) { 484 for (uint i = 0; i < 2 * _n; i++) { 485 if (steal_best_of_2(queue_num, seed, t)) { 486 TASKQUEUE_STATS_ONLY(queue(queue_num)->stats.record_steal(true)); 487 return true; 488 } 489 } 490 TASKQUEUE_STATS_ONLY(queue(queue_num)->stats.record_steal(false)); 491 return false; 492 } 493 494 template<class T> bool 495 GenericTaskQueueSet<T>::steal_best_of_all(uint queue_num, int* seed, E& t) { 496 if (_n > 2) { 497 int best_k; 498 uint best_sz = 0; 499 for (uint k = 0; k < _n; k++) { 500 if (k == queue_num) continue; 501 uint sz = _queues[k]->size(); 502 if (sz > best_sz) { 503 best_sz = sz; 504 best_k = k; 505 } 506 } 507 return best_sz > 0 && _queues[best_k]->pop_global(t); 508 } else if (_n == 2) { 509 // Just try the other one. 510 int k = (queue_num + 1) % 2; 511 return _queues[k]->pop_global(t); 512 } else { 513 assert(_n == 1, "can't be zero."); 514 return false; 515 } 516 } 517 518 template<class T> bool 519 GenericTaskQueueSet<T>::steal_1_random(uint queue_num, int* seed, E& t) { 520 if (_n > 2) { 521 uint k = queue_num; 522 while (k == queue_num) k = randomParkAndMiller(seed) % _n; 523 return _queues[2]->pop_global(t); 524 } else if (_n == 2) { 525 // Just try the other one. 526 int k = (queue_num + 1) % 2; 527 return _queues[k]->pop_global(t); 528 } else { 529 assert(_n == 1, "can't be zero."); 530 return false; 531 } 532 } 533 534 template<class T> bool 535 GenericTaskQueueSet<T>::steal_best_of_2(uint queue_num, int* seed, E& t) { 536 if (_n > 2) { 537 uint k1 = queue_num; 538 while (k1 == queue_num) k1 = randomParkAndMiller(seed) % _n; 539 uint k2 = queue_num; 540 while (k2 == queue_num || k2 == k1) k2 = randomParkAndMiller(seed) % _n; 541 // Sample both and try the larger. 542 uint sz1 = _queues[k1]->size(); 543 uint sz2 = _queues[k2]->size(); 544 if (sz2 > sz1) return _queues[k2]->pop_global(t); 545 else return _queues[k1]->pop_global(t); 546 } else if (_n == 2) { 547 // Just try the other one. 548 uint k = (queue_num + 1) % 2; 549 return _queues[k]->pop_global(t); 550 } else { 551 assert(_n == 1, "can't be zero."); 552 return false; 553 } 554 } 555 556 template<class T> 557 bool GenericTaskQueueSet<T>::peek() { 558 // Try all the queues. 559 for (uint j = 0; j < _n; j++) { 560 if (_queues[j]->peek()) 561 return true; 562 } 563 return false; 564 } 565 566 // When to terminate from the termination protocol. 567 class TerminatorTerminator: public CHeapObj { 568 public: 569 virtual bool should_exit_termination() = 0; 570 }; 571 572 // A class to aid in the termination of a set of parallel tasks using 573 // TaskQueueSet's for work stealing. 574 575 #undef TRACESPINNING 576 577 class ParallelTaskTerminator: public StackObj { 578 private: 579 int _n_threads; 580 TaskQueueSetSuper* _queue_set; 581 int _offered_termination; 582 583 #ifdef TRACESPINNING 584 static uint _total_yields; 585 static uint _total_spins; 586 static uint _total_peeks; 587 #endif 588 589 bool peek_in_queue_set(); 590 protected: 591 virtual void yield(); 592 void sleep(uint millis); 593 594 public: 595 596 // "n_threads" is the number of threads to be terminated. "queue_set" is a 597 // queue sets of work queues of other threads. 598 ParallelTaskTerminator(int n_threads, TaskQueueSetSuper* queue_set); 599 600 // The current thread has no work, and is ready to terminate if everyone 601 // else is. If returns "true", all threads are terminated. If returns 602 // "false", available work has been observed in one of the task queues, 603 // so the global task is not complete. 604 bool offer_termination() { 605 return offer_termination(NULL); 606 } 607 608 // As above, but it also terminates if the should_exit_termination() 609 // method of the terminator parameter returns true. If terminator is 610 // NULL, then it is ignored. 611 bool offer_termination(TerminatorTerminator* terminator); 612 613 // Reset the terminator, so that it may be reused again. 614 // The caller is responsible for ensuring that this is done 615 // in an MT-safe manner, once the previous round of use of 616 // the terminator is finished. 617 void reset_for_reuse(); 618 // Same as above but the number of parallel threads is set to the 619 // given number. 620 void reset_for_reuse(int n_threads); 621 622 #ifdef TRACESPINNING 623 static uint total_yields() { return _total_yields; } 624 static uint total_spins() { return _total_spins; } 625 static uint total_peeks() { return _total_peeks; } 626 static void print_termination_counts(); 627 #endif 628 }; 629 630 template<class E, unsigned int N> inline bool 631 GenericTaskQueue<E, N>::push(E t) { 632 uint localBot = _bottom; 633 assert((localBot >= 0) && (localBot < N), "_bottom out of range."); 634 idx_t top = _age.top(); 635 uint dirty_n_elems = dirty_size(localBot, top); 636 assert(dirty_n_elems < N, "n_elems out of range."); 637 if (dirty_n_elems < max_elems()) { 638 // g++ complains if the volatile result of the assignment is unused. 639 const_cast<E&>(_elems[localBot] = t); 640 OrderAccess::release_store(&_bottom, increment_index(localBot)); 641 TASKQUEUE_STATS_ONLY(stats.record_push()); 642 return true; 643 } else { 644 return push_slow(t, dirty_n_elems); 645 } 646 } 647 648 template<class E, unsigned int N> inline bool 649 GenericTaskQueue<E, N>::pop_local(E& t) { 650 uint localBot = _bottom; 651 // This value cannot be N-1. That can only occur as a result of 652 // the assignment to bottom in this method. If it does, this method 653 // resets the size to 0 before the next call (which is sequential, 654 // since this is pop_local.) 655 uint dirty_n_elems = dirty_size(localBot, _age.top()); 656 assert(dirty_n_elems != N - 1, "Shouldn't be possible..."); 657 if (dirty_n_elems == 0) return false; 658 localBot = decrement_index(localBot); 659 _bottom = localBot; 660 // This is necessary to prevent any read below from being reordered 661 // before the store just above. 662 OrderAccess::fence(); 663 const_cast<E&>(t = _elems[localBot]); 664 // This is a second read of "age"; the "size()" above is the first. 665 // If there's still at least one element in the queue, based on the 666 // "_bottom" and "age" we've read, then there can be no interference with 667 // a "pop_global" operation, and we're done. 668 idx_t tp = _age.top(); // XXX 669 if (size(localBot, tp) > 0) { 670 assert(dirty_size(localBot, tp) != N - 1, "sanity"); 671 TASKQUEUE_STATS_ONLY(stats.record_pop()); 672 return true; 673 } else { 674 // Otherwise, the queue contained exactly one element; we take the slow 675 // path. 676 return pop_local_slow(localBot, _age.get()); 677 } 678 } 679 680 typedef GenericTaskQueue<oop> OopTaskQueue; 681 typedef GenericTaskQueueSet<OopTaskQueue> OopTaskQueueSet; 682 683 #ifdef _MSC_VER 684 #pragma warning(push) 685 // warning C4522: multiple assignment operators specified 686 #pragma warning(disable:4522) 687 #endif 688 689 // This is a container class for either an oop* or a narrowOop*. 690 // Both are pushed onto a task queue and the consumer will test is_narrow() 691 // to determine which should be processed. 692 class StarTask { 693 void* _holder; // either union oop* or narrowOop* 694 695 enum { COMPRESSED_OOP_MASK = 1 }; 696 697 public: 698 StarTask(narrowOop* p) { 699 assert(((uintptr_t)p & COMPRESSED_OOP_MASK) == 0, "Information loss!"); 700 _holder = (void *)((uintptr_t)p | COMPRESSED_OOP_MASK); 701 } 702 StarTask(oop* p) { 703 assert(((uintptr_t)p & COMPRESSED_OOP_MASK) == 0, "Information loss!"); 704 _holder = (void*)p; 705 } 706 StarTask() { _holder = NULL; } 707 operator oop*() { return (oop*)_holder; } 708 operator narrowOop*() { 709 return (narrowOop*)((uintptr_t)_holder & ~COMPRESSED_OOP_MASK); 710 } 711 712 StarTask& operator=(const StarTask& t) { 713 _holder = t._holder; 714 return *this; 715 } 716 volatile StarTask& operator=(const volatile StarTask& t) volatile { 717 _holder = t._holder; 718 return *this; 719 } 720 721 bool is_narrow() const { 722 return (((uintptr_t)_holder & COMPRESSED_OOP_MASK) != 0); 723 } 724 }; 725 726 class ObjArrayTask 727 { 728 public: 729 ObjArrayTask(oop o = NULL, int idx = 0): _obj(o), _index(idx) { } 730 ObjArrayTask(oop o, size_t idx): _obj(o), _index(int(idx)) { 731 assert(idx <= size_t(max_jint), "too big"); 732 } 733 ObjArrayTask(const ObjArrayTask& t): _obj(t._obj), _index(t._index) { } 734 735 ObjArrayTask& operator =(const ObjArrayTask& t) { 736 _obj = t._obj; 737 _index = t._index; 738 return *this; 739 } 740 volatile ObjArrayTask& 741 operator =(const volatile ObjArrayTask& t) volatile { 742 _obj = t._obj; 743 _index = t._index; 744 return *this; 745 } 746 747 inline oop obj() const { return _obj; } 748 inline int index() const { return _index; } 749 750 DEBUG_ONLY(bool is_valid() const); // Tasks to be pushed/popped must be valid. 751 752 private: 753 oop _obj; 754 int _index; 755 }; 756 757 #ifdef _MSC_VER 758 #pragma warning(pop) 759 #endif 760 761 typedef OverflowTaskQueue<StarTask> OopStarTaskQueue; 762 typedef GenericTaskQueueSet<OopStarTaskQueue> OopStarTaskQueueSet; 763 764 typedef OverflowTaskQueue<size_t> RegionTaskQueue; 765 typedef GenericTaskQueueSet<RegionTaskQueue> RegionTaskQueueSet; 766