317 // tty->print_cr("START OopTaskQueue::oops_do");
318 uint iters = size();
319 uint index = _bottom;
320 for (uint i = 0; i < iters; ++i) {
321 index = decrement_index(index);
322 // tty->print_cr(" doing entry %d," INTPTR_T " -> " INTPTR_T,
323 // index, &_elems[index], _elems[index]);
324 E* t = (E*)&_elems[index]; // cast away volatility
325 oop* p = (oop*)t;
326 assert((*t)->is_oop_or_null(), "Not an oop or null");
327 f->do_oop(p);
328 }
329 // tty->print_cr("END OopTaskQueue::oops_do");
330 }
331
332 template<class E, unsigned int N>
333 bool GenericTaskQueue<E, N>::push_slow(E t, uint dirty_n_elems) {
334 if (dirty_n_elems == N - 1) {
335 // Actually means 0, so do the push.
336 uint localBot = _bottom;
337 // g++ complains if the volatile result of the assignment is unused.
338 const_cast<E&>(_elems[localBot] = t);
339 OrderAccess::release_store(&_bottom, increment_index(localBot));
340 TASKQUEUE_STATS_ONLY(stats.record_push());
341 return true;
342 }
343 return false;
344 }
345
346 // pop_local_slow() is done by the owning thread and is trying to
347 // get the last task in the queue. It will compete with pop_global()
348 // that will be used by other threads. The tag age is incremented
349 // whenever the queue goes empty which it will do here if this thread
350 // gets the last task or in pop_global() if the queue wraps (top == 0
351 // and pop_global() succeeds, see pop_global()).
352 template<class E, unsigned int N>
353 bool GenericTaskQueue<E, N>::pop_local_slow(uint localBot, Age oldAge) {
354 // This queue was observed to contain exactly one element; either this
355 // thread will claim it, or a competing "pop_global". In either case,
356 // the queue will be logically empty afterwards. Create a new Age value
357 // that represents the empty queue for the given value of "_bottom". (We
358 // must also increment "tag" because of the case where "bottom == 1",
374 return true;
375 }
376 }
377 // We lose; a completing pop_global gets the element. But the queue is empty
378 // and top is greater than bottom. Fix this representation of the empty queue
379 // to become the canonical one.
380 _age.set(newAge);
381 assert(dirty_size(localBot, _age.top()) != N - 1, "sanity");
382 return false;
383 }
384
385 template<class E, unsigned int N>
386 bool GenericTaskQueue<E, N>::pop_global(E& t) {
387 Age oldAge = _age.get();
388 uint localBot = _bottom;
389 uint n_elems = size(localBot, oldAge.top());
390 if (n_elems == 0) {
391 return false;
392 }
393
394 const_cast<E&>(t = _elems[oldAge.top()]);
395 Age newAge(oldAge);
396 newAge.increment();
397 Age resAge = _age.cmpxchg(newAge, oldAge);
398
399 // Note that using "_bottom" here might fail, since a pop_local might
400 // have decremented it.
401 assert(dirty_size(localBot, newAge.top()) != N - 1, "sanity");
402 return resAge == oldAge;
403 }
404
405 template<class E, unsigned int N>
406 GenericTaskQueue<E, N>::~GenericTaskQueue() {
407 FREE_C_HEAP_ARRAY(E, _elems);
408 }
409
410 // OverflowTaskQueue is a TaskQueue that also includes an overflow stack for
411 // elements that do not fit in the TaskQueue.
412 //
413 // This class hides two methods from super classes:
414 //
656 // Same as above but the number of parallel threads is set to the
657 // given number.
658 void reset_for_reuse(int n_threads);
659
660 #ifdef TRACESPINNING
661 static uint total_yields() { return _total_yields; }
662 static uint total_spins() { return _total_spins; }
663 static uint total_peeks() { return _total_peeks; }
664 static void print_termination_counts();
665 #endif
666 };
667
668 template<class E, unsigned int N> inline bool
669 GenericTaskQueue<E, N>::push(E t) {
670 uint localBot = _bottom;
671 assert((localBot >= 0) && (localBot < N), "_bottom out of range.");
672 idx_t top = _age.top();
673 uint dirty_n_elems = dirty_size(localBot, top);
674 assert(dirty_n_elems < N, "n_elems out of range.");
675 if (dirty_n_elems < max_elems()) {
676 // g++ complains if the volatile result of the assignment is unused.
677 const_cast<E&>(_elems[localBot] = t);
678 OrderAccess::release_store(&_bottom, increment_index(localBot));
679 TASKQUEUE_STATS_ONLY(stats.record_push());
680 return true;
681 } else {
682 return push_slow(t, dirty_n_elems);
683 }
684 }
685
686 template<class E, unsigned int N> inline bool
687 GenericTaskQueue<E, N>::pop_local(E& t) {
688 uint localBot = _bottom;
689 // This value cannot be N-1. That can only occur as a result of
690 // the assignment to bottom in this method. If it does, this method
691 // resets the size to 0 before the next call (which is sequential,
692 // since this is pop_local.)
693 uint dirty_n_elems = dirty_size(localBot, _age.top());
694 assert(dirty_n_elems != N - 1, "Shouldn't be possible...");
695 if (dirty_n_elems == 0) return false;
696 localBot = decrement_index(localBot);
697 _bottom = localBot;
698 // This is necessary to prevent any read below from being reordered
699 // before the store just above.
700 OrderAccess::fence();
701 const_cast<E&>(t = _elems[localBot]);
702 // This is a second read of "age"; the "size()" above is the first.
703 // If there's still at least one element in the queue, based on the
704 // "_bottom" and "age" we've read, then there can be no interference with
705 // a "pop_global" operation, and we're done.
706 idx_t tp = _age.top(); // XXX
707 if (size(localBot, tp) > 0) {
708 assert(dirty_size(localBot, tp) != N - 1, "sanity");
709 TASKQUEUE_STATS_ONLY(stats.record_pop());
710 return true;
711 } else {
712 // Otherwise, the queue contained exactly one element; we take the slow
713 // path.
714 return pop_local_slow(localBot, _age.get());
715 }
716 }
717
718 typedef GenericTaskQueue<oop> OopTaskQueue;
719 typedef GenericTaskQueueSet<OopTaskQueue> OopTaskQueueSet;
720
721 #ifdef _MSC_VER
|
317 // tty->print_cr("START OopTaskQueue::oops_do");
318 uint iters = size();
319 uint index = _bottom;
320 for (uint i = 0; i < iters; ++i) {
321 index = decrement_index(index);
322 // tty->print_cr(" doing entry %d," INTPTR_T " -> " INTPTR_T,
323 // index, &_elems[index], _elems[index]);
324 E* t = (E*)&_elems[index]; // cast away volatility
325 oop* p = (oop*)t;
326 assert((*t)->is_oop_or_null(), "Not an oop or null");
327 f->do_oop(p);
328 }
329 // tty->print_cr("END OopTaskQueue::oops_do");
330 }
331
332 template<class E, unsigned int N>
333 bool GenericTaskQueue<E, N>::push_slow(E t, uint dirty_n_elems) {
334 if (dirty_n_elems == N - 1) {
335 // Actually means 0, so do the push.
336 uint localBot = _bottom;
337 // g++ complains if the volatile result of the assignment is
338 // unused, so we cast the volatile away. We cannot cast directly
339 // to void, because gcc treats that as not using the result of the
340 // assignment. However, casting to E& means that we trigger an
341 // unused-value warning. So, we cast the E& to void.
342 (void)const_cast<E&>(_elems[localBot] = t);
343 OrderAccess::release_store(&_bottom, increment_index(localBot));
344 TASKQUEUE_STATS_ONLY(stats.record_push());
345 return true;
346 }
347 return false;
348 }
349
350 // pop_local_slow() is done by the owning thread and is trying to
351 // get the last task in the queue. It will compete with pop_global()
352 // that will be used by other threads. The tag age is incremented
353 // whenever the queue goes empty which it will do here if this thread
354 // gets the last task or in pop_global() if the queue wraps (top == 0
355 // and pop_global() succeeds, see pop_global()).
356 template<class E, unsigned int N>
357 bool GenericTaskQueue<E, N>::pop_local_slow(uint localBot, Age oldAge) {
358 // This queue was observed to contain exactly one element; either this
359 // thread will claim it, or a competing "pop_global". In either case,
360 // the queue will be logically empty afterwards. Create a new Age value
361 // that represents the empty queue for the given value of "_bottom". (We
362 // must also increment "tag" because of the case where "bottom == 1",
378 return true;
379 }
380 }
381 // We lose; a completing pop_global gets the element. But the queue is empty
382 // and top is greater than bottom. Fix this representation of the empty queue
383 // to become the canonical one.
384 _age.set(newAge);
385 assert(dirty_size(localBot, _age.top()) != N - 1, "sanity");
386 return false;
387 }
388
389 template<class E, unsigned int N>
390 bool GenericTaskQueue<E, N>::pop_global(E& t) {
391 Age oldAge = _age.get();
392 uint localBot = _bottom;
393 uint n_elems = size(localBot, oldAge.top());
394 if (n_elems == 0) {
395 return false;
396 }
397
398 // g++ complains if the volatile result of the assignment is
399 // unused, so we cast the volatile away. We cannot cast directly
400 // to void, because gcc treats that as not using the result of the
401 // assignment. However, casting to E& means that we trigger an
402 // unused-value warning. So, we cast the E& to void.
403 (void) const_cast<E&>(t = _elems[oldAge.top()]);
404 Age newAge(oldAge);
405 newAge.increment();
406 Age resAge = _age.cmpxchg(newAge, oldAge);
407
408 // Note that using "_bottom" here might fail, since a pop_local might
409 // have decremented it.
410 assert(dirty_size(localBot, newAge.top()) != N - 1, "sanity");
411 return resAge == oldAge;
412 }
413
414 template<class E, unsigned int N>
415 GenericTaskQueue<E, N>::~GenericTaskQueue() {
416 FREE_C_HEAP_ARRAY(E, _elems);
417 }
418
419 // OverflowTaskQueue is a TaskQueue that also includes an overflow stack for
420 // elements that do not fit in the TaskQueue.
421 //
422 // This class hides two methods from super classes:
423 //
665 // Same as above but the number of parallel threads is set to the
666 // given number.
667 void reset_for_reuse(int n_threads);
668
669 #ifdef TRACESPINNING
670 static uint total_yields() { return _total_yields; }
671 static uint total_spins() { return _total_spins; }
672 static uint total_peeks() { return _total_peeks; }
673 static void print_termination_counts();
674 #endif
675 };
676
677 template<class E, unsigned int N> inline bool
678 GenericTaskQueue<E, N>::push(E t) {
679 uint localBot = _bottom;
680 assert((localBot >= 0) && (localBot < N), "_bottom out of range.");
681 idx_t top = _age.top();
682 uint dirty_n_elems = dirty_size(localBot, top);
683 assert(dirty_n_elems < N, "n_elems out of range.");
684 if (dirty_n_elems < max_elems()) {
685 // g++ complains if the volatile result of the assignment is
686 // unused, so we cast the volatile away. We cannot cast directly
687 // to void, because gcc treats that as not using the result of the
688 // assignment. However, casting to E& means that we trigger an
689 // unused-value warning. So, we cast the E& to void.
690 (void) const_cast<E&>(_elems[localBot] = t);
691 OrderAccess::release_store(&_bottom, increment_index(localBot));
692 TASKQUEUE_STATS_ONLY(stats.record_push());
693 return true;
694 } else {
695 return push_slow(t, dirty_n_elems);
696 }
697 }
698
699 template<class E, unsigned int N> inline bool
700 GenericTaskQueue<E, N>::pop_local(E& t) {
701 uint localBot = _bottom;
702 // This value cannot be N-1. That can only occur as a result of
703 // the assignment to bottom in this method. If it does, this method
704 // resets the size to 0 before the next call (which is sequential,
705 // since this is pop_local.)
706 uint dirty_n_elems = dirty_size(localBot, _age.top());
707 assert(dirty_n_elems != N - 1, "Shouldn't be possible...");
708 if (dirty_n_elems == 0) return false;
709 localBot = decrement_index(localBot);
710 _bottom = localBot;
711 // This is necessary to prevent any read below from being reordered
712 // before the store just above.
713 OrderAccess::fence();
714 // g++ complains if the volatile result of the assignment is
715 // unused, so we cast the volatile away. We cannot cast directly
716 // to void, because gcc treats that as not using the result of the
717 // assignment. However, casting to E& means that we trigger an
718 // unused-value warning. So, we cast the E& to void.
719 (void) const_cast<E&>(t = _elems[localBot]);
720 // This is a second read of "age"; the "size()" above is the first.
721 // If there's still at least one element in the queue, based on the
722 // "_bottom" and "age" we've read, then there can be no interference with
723 // a "pop_global" operation, and we're done.
724 idx_t tp = _age.top(); // XXX
725 if (size(localBot, tp) > 0) {
726 assert(dirty_size(localBot, tp) != N - 1, "sanity");
727 TASKQUEUE_STATS_ONLY(stats.record_pop());
728 return true;
729 } else {
730 // Otherwise, the queue contained exactly one element; we take the slow
731 // path.
732 return pop_local_slow(localBot, _age.get());
733 }
734 }
735
736 typedef GenericTaskQueue<oop> OopTaskQueue;
737 typedef GenericTaskQueueSet<OopTaskQueue> OopTaskQueueSet;
738
739 #ifdef _MSC_VER
|