duke@435: /*
xdono@905:  * Copyright 2001-2008 Sun Microsystems, Inc.  All Rights Reserved.
duke@435:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@435:  *
duke@435:  * This code is free software; you can redistribute it and/or modify it
duke@435:  * under the terms of the GNU General Public License version 2 only, as
duke@435:  * published by the Free Software Foundation.
duke@435:  *
duke@435:  * This code is distributed in the hope that it will be useful, but WITHOUT
duke@435:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@435:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
duke@435:  * version 2 for more details (a copy is included in the LICENSE file that
duke@435:  * accompanied this code).
duke@435:  *
duke@435:  * You should have received a copy of the GNU General Public License version
duke@435:  * 2 along with this work; if not, write to the Free Software Foundation,
duke@435:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@435:  *
duke@435:  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
duke@435:  * CA 95054 USA or visit www.sun.com if you need additional information or
duke@435:  * have any questions.
duke@435:  *
duke@435:  */
duke@435: 
duke@435: # include "incls/_precompiled.incl"
duke@435: # include "incls/_taskqueue.cpp.incl"
duke@435: 
duke@435: bool TaskQueueSuper::peek() {
duke@435:   return _bottom != _age.top();
duke@435: }
duke@435: 
duke@435: int TaskQueueSetSuper::randomParkAndMiller(int *seed0) {
duke@435:   const int a =      16807;
duke@435:   const int m = 2147483647;
duke@435:   const int q =     127773;  /* m div a */
duke@435:   const int r =       2836;  /* m mod a */
duke@435:   assert(sizeof(int) == 4, "I think this relies on that");
duke@435:   int seed = *seed0;
duke@435:   int hi   = seed / q;
duke@435:   int lo   = seed % q;
duke@435:   int test = a * lo - r * hi;
duke@435:   if (test > 0)
duke@435:     seed = test;
duke@435:   else
duke@435:     seed = test + m;
duke@435:   *seed0 = seed;
duke@435:   return seed;
duke@435: }
duke@435: 
duke@435: ParallelTaskTerminator::
duke@435: ParallelTaskTerminator(int n_threads, TaskQueueSetSuper* queue_set) :
duke@435:   _n_threads(n_threads),
duke@435:   _queue_set(queue_set),
duke@435:   _offered_termination(0) {}
duke@435: 
duke@435: bool ParallelTaskTerminator::peek_in_queue_set() {
duke@435:   return _queue_set->peek();
duke@435: }
duke@435: 
duke@435: void ParallelTaskTerminator::yield() {
duke@435:   os::yield();
duke@435: }
duke@435: 
duke@435: void ParallelTaskTerminator::sleep(uint millis) {
duke@435:   os::sleep(Thread::current(), millis, false);
duke@435: }
duke@435: 
ysr@777: bool
ysr@777: ParallelTaskTerminator::offer_termination(TerminatorTerminator* terminator) {
duke@435:   Atomic::inc(&_offered_termination);
duke@435: 
duke@435:   juint yield_count = 0;
duke@435:   while (true) {
duke@435:     if (_offered_termination == _n_threads) {
duke@435:       //inner_termination_loop();
duke@435:       return true;
duke@435:     } else {
duke@435:       if (yield_count <= WorkStealingYieldsBeforeSleep) {
duke@435:         yield_count++;
duke@435:         yield();
duke@435:       } else {
duke@435:         if (PrintGCDetails && Verbose) {
duke@435:          gclog_or_tty->print_cr("ParallelTaskTerminator::offer_termination() "
duke@435:            "thread %d sleeps after %d yields",
duke@435:            Thread::current(), yield_count);
duke@435:         }
duke@435:         yield_count = 0;
duke@435:         // A sleep will cause this processor to seek work on another processor's
duke@435:         // runqueue, if it has nothing else to run (as opposed to the yield
duke@435:         // which may only move the thread to the end of the this processor's
duke@435:         // runqueue).
duke@435:         sleep(WorkStealingSleepMillis);
duke@435:       }
duke@435: 
ysr@777:       if (peek_in_queue_set() ||
ysr@777:           (terminator != NULL && terminator->should_exit_termination())) {
duke@435:         Atomic::dec(&_offered_termination);
duke@435:         return false;
duke@435:       }
duke@435:     }
duke@435:   }
duke@435: }
duke@435: 
duke@435: void ParallelTaskTerminator::reset_for_reuse() {
duke@435:   if (_offered_termination != 0) {
duke@435:     assert(_offered_termination == _n_threads,
duke@435:            "Terminator may still be in use");
duke@435:     _offered_termination = 0;
duke@435:   }
duke@435: }
duke@435: 
jcoomes@810: bool RegionTaskQueueWithOverflow::is_empty() {
jcoomes@810:   return (_region_queue.size() == 0) &&
duke@435:          (_overflow_stack->length() == 0);
duke@435: }
duke@435: 
jcoomes@810: bool RegionTaskQueueWithOverflow::stealable_is_empty() {
jcoomes@810:   return _region_queue.size() == 0;
duke@435: }
duke@435: 
jcoomes@810: bool RegionTaskQueueWithOverflow::overflow_is_empty() {
duke@435:   return _overflow_stack->length() == 0;
duke@435: }
duke@435: 
jcoomes@810: void RegionTaskQueueWithOverflow::initialize() {
jcoomes@810:   _region_queue.initialize();
duke@435:   assert(_overflow_stack == 0, "Creating memory leak");
duke@435:   _overflow_stack =
jcoomes@810:     new (ResourceObj::C_HEAP) GrowableArray<RegionTask>(10, true);
duke@435: }
duke@435: 
jcoomes@810: void RegionTaskQueueWithOverflow::save(RegionTask t) {
jcoomes@810:   if (TraceRegionTasksQueuing && Verbose) {
duke@435:     gclog_or_tty->print_cr("CTQ: save " PTR_FORMAT, t);
duke@435:   }
jcoomes@810:   if(!_region_queue.push(t)) {
duke@435:     _overflow_stack->push(t);
duke@435:   }
duke@435: }
duke@435: 
jcoomes@810: // Note that using this method will retrieve all regions
duke@435: // that have been saved but that it will always check
duke@435: // the overflow stack.  It may be more efficient to
duke@435: // check the stealable queue and the overflow stack
duke@435: // separately.
jcoomes@810: bool RegionTaskQueueWithOverflow::retrieve(RegionTask& region_task) {
jcoomes@810:   bool result = retrieve_from_overflow(region_task);
duke@435:   if (!result) {
jcoomes@810:     result = retrieve_from_stealable_queue(region_task);
duke@435:   }
jcoomes@810:   if (TraceRegionTasksQueuing && Verbose && result) {
duke@435:     gclog_or_tty->print_cr("  CTQ: retrieve " PTR_FORMAT, result);
duke@435:   }
duke@435:   return result;
duke@435: }
duke@435: 
jcoomes@810: bool RegionTaskQueueWithOverflow::retrieve_from_stealable_queue(
jcoomes@810:                                    RegionTask& region_task) {
jcoomes@810:   bool result = _region_queue.pop_local(region_task);
jcoomes@810:   if (TraceRegionTasksQueuing && Verbose) {
jcoomes@810:     gclog_or_tty->print_cr("CTQ: retrieve_stealable " PTR_FORMAT, region_task);
duke@435:   }
duke@435:   return result;
duke@435: }
duke@435: 
jcoomes@810: bool
jcoomes@810: RegionTaskQueueWithOverflow::retrieve_from_overflow(RegionTask& region_task) {
duke@435:   bool result;
duke@435:   if (!_overflow_stack->is_empty()) {
jcoomes@810:     region_task = _overflow_stack->pop();
duke@435:     result = true;
duke@435:   } else {
jcoomes@810:     region_task = (RegionTask) NULL;
duke@435:     result = false;
duke@435:   }
jcoomes@810:   if (TraceRegionTasksQueuing && Verbose) {
jcoomes@810:     gclog_or_tty->print_cr("CTQ: retrieve_stealable " PTR_FORMAT, region_task);
duke@435:   }
duke@435:   return result;
duke@435: }