aoqi@0: /*
aoqi@0:  * Copyright (c) 2005, 2013, Oracle and/or its affiliates. All rights reserved.
aoqi@0:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
aoqi@0:  *
aoqi@0:  * This code is free software; you can redistribute it and/or modify it
aoqi@0:  * under the terms of the GNU General Public License version 2 only, as
aoqi@0:  * published by the Free Software Foundation.
aoqi@0:  *
aoqi@0:  * This code is distributed in the hope that it will be useful, but WITHOUT
aoqi@0:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
aoqi@0:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
aoqi@0:  * version 2 for more details (a copy is included in the LICENSE file that
aoqi@0:  * accompanied this code).
aoqi@0:  *
aoqi@0:  * You should have received a copy of the GNU General Public License version
aoqi@0:  * 2 along with this work; if not, write to the Free Software Foundation,
aoqi@0:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
aoqi@0:  *
aoqi@0:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
aoqi@0:  * or visit www.oracle.com if you need additional information or have any
aoqi@0:  * questions.
aoqi@0:  *
aoqi@0:  */
aoqi@0: 
aoqi@0: #include "precompiled.hpp"
aoqi@0: #include "utilities/macros.hpp"
aoqi@0: #include "utilities/yieldingWorkgroup.hpp"
aoqi@0: 
aoqi@0: // Forward declaration of classes declared here.
aoqi@0: 
aoqi@0: class GangWorker;
aoqi@0: class WorkData;
aoqi@0: 
aoqi@0: YieldingFlexibleWorkGang::YieldingFlexibleWorkGang(
aoqi@0:   const char* name, uint workers, bool are_GC_task_threads) :
aoqi@0:   FlexibleWorkGang(name, workers, are_GC_task_threads, false),
aoqi@0:     _yielded_workers(0) {}
aoqi@0: 
aoqi@0: GangWorker* YieldingFlexibleWorkGang::allocate_worker(uint which) {
aoqi@0:   YieldingFlexibleGangWorker* new_member =
aoqi@0:       new YieldingFlexibleGangWorker(this, which);
aoqi@0:   return (YieldingFlexibleGangWorker*) new_member;
aoqi@0: }
aoqi@0: 
aoqi@0: // Run a task; returns when the task is done, or the workers yield,
aoqi@0: // or the task is aborted, or the work gang is terminated via stop().
aoqi@0: // A task that has been yielded can be continued via this interface
aoqi@0: // by using the same task repeatedly as the argument to the call.
aoqi@0: // It is expected that the YieldingFlexibleGangTask carries the appropriate
aoqi@0: // continuation information used by workers to continue the task
aoqi@0: // from its last yield point. Thus, a completed task will return
aoqi@0: // immediately with no actual work having been done by the workers.
aoqi@0: /////////////////////
aoqi@0: // Implementatiuon notes: remove before checking XXX
aoqi@0: /*
aoqi@0: Each gang is working on a task at a certain time.
aoqi@0: Some subset of workers may have yielded and some may
aoqi@0: have finished their quota of work. Until this task has
aoqi@0: been completed, the workers are bound to that task.
aoqi@0: Once the task has been completed, the gang unbounds
aoqi@0: itself from the task.
aoqi@0: 
aoqi@0: The yielding work gang thus exports two invokation
aoqi@0: interfaces: run_task() and continue_task(). The
aoqi@0: first is used to initiate a new task and bind it
aoqi@0: to the workers; the second is used to continue an
aoqi@0: already bound task that has yielded. Upon completion
aoqi@0: the binding is released and a new binding may be
aoqi@0: created.
aoqi@0: 
aoqi@0: The shape of a yielding work gang is as follows:
aoqi@0: 
aoqi@0: Overseer invokes run_task(*task).
aoqi@0:    Lock gang monitor
aoqi@0:    Check that there is no existing binding for the gang
aoqi@0:    If so, abort with an error
aoqi@0:    Else, create a new binding of this gang to the given task
aoqi@0:    Set number of active workers (as asked)
aoqi@0:    Notify workers that work is ready to be done
aoqi@0:      [the requisite # workers would then start up
aoqi@0:       and do the task]
aoqi@0:    Wait on the monitor until either
aoqi@0:      all work is completed or the task has yielded
aoqi@0:      -- this is normally done through
aoqi@0:         yielded + completed == active
aoqi@0:         [completed workers are rest to idle state by overseer?]
aoqi@0:    return appropriate status to caller
aoqi@0: 
aoqi@0: Overseer invokes continue_task(*task),
aoqi@0:    Lock gang monitor
aoqi@0:    Check that task is the same as current binding
aoqi@0:    If not, abort with an error
aoqi@0:    Else, set the number of active workers as requested?
aoqi@0:    Notify workers that they can continue from yield points
aoqi@0:     New workers can also start up as required
aoqi@0:       while satisfying the constraint that
aoqi@0:          active + yielded does not exceed required number
aoqi@0:    Wait (as above).
aoqi@0: 
aoqi@0: NOTE: In the above, for simplicity in a first iteration
aoqi@0:   our gangs will be of fixed population and will not
aoqi@0:   therefore be flexible work gangs, just yielding work
aoqi@0:   gangs. Once this works well, we will in a second
aoqi@0:   iteration.refinement introduce flexibility into
aoqi@0:   the work gang.
aoqi@0: 
aoqi@0: NOTE: we can always create a new gang per each iteration
aoqi@0:   in order to get the flexibility, but we will for now
aoqi@0:   desist that simplified route.
aoqi@0: 
aoqi@0:  */
aoqi@0: /////////////////////
aoqi@0: void YieldingFlexibleWorkGang::start_task(YieldingFlexibleGangTask* new_task) {
aoqi@0:   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
aoqi@0:   assert(task() == NULL, "Gang currently tied to a task");
aoqi@0:   assert(new_task != NULL, "Null task");
aoqi@0:   // Bind task to gang
aoqi@0:   _task = new_task;
aoqi@0:   new_task->set_gang(this);  // Establish 2-way binding to support yielding
aoqi@0:   _sequence_number++;
aoqi@0: 
aoqi@0:   uint requested_size = new_task->requested_size();
aoqi@0:   assert(requested_size >= 0, "Should be non-negative");
aoqi@0:   if (requested_size != 0) {
aoqi@0:     _active_workers = MIN2(requested_size, total_workers());
aoqi@0:   } else {
aoqi@0:     _active_workers = active_workers();
aoqi@0:   }
aoqi@0:   new_task->set_actual_size(_active_workers);
aoqi@0:   new_task->set_for_termination(_active_workers);
aoqi@0: 
aoqi@0:   assert(_started_workers == 0, "Tabula rasa non");
aoqi@0:   assert(_finished_workers == 0, "Tabula rasa non");
aoqi@0:   assert(_yielded_workers == 0, "Tabula rasa non");
aoqi@0:   yielding_task()->set_status(ACTIVE);
aoqi@0: 
aoqi@0:   // Wake up all the workers, the first few will get to work,
aoqi@0:   // and the rest will go back to sleep
aoqi@0:   monitor()->notify_all();
aoqi@0:   wait_for_gang();
aoqi@0: }
aoqi@0: 
aoqi@0: void YieldingFlexibleWorkGang::wait_for_gang() {
aoqi@0: 
aoqi@0:   assert(monitor()->owned_by_self(), "Data race");
aoqi@0:   // Wait for task to complete or yield
aoqi@0:   for (Status status = yielding_task()->status();
aoqi@0:        status != COMPLETED && status != YIELDED && status != ABORTED;
aoqi@0:        status = yielding_task()->status()) {
aoqi@0:     assert(started_workers() <= active_workers(), "invariant");
aoqi@0:     assert(finished_workers() <= active_workers(), "invariant");
aoqi@0:     assert(yielded_workers() <= active_workers(), "invariant");
aoqi@0:     monitor()->wait(Mutex::_no_safepoint_check_flag);
aoqi@0:   }
aoqi@0:   switch (yielding_task()->status()) {
aoqi@0:     case COMPLETED:
aoqi@0:     case ABORTED: {
aoqi@0:       assert(finished_workers() == active_workers(), "Inconsistent status");
aoqi@0:       assert(yielded_workers() == 0, "Invariant");
aoqi@0:       reset();   // for next task; gang<->task binding released
aoqi@0:       break;
aoqi@0:     }
aoqi@0:     case YIELDED: {
aoqi@0:       assert(yielded_workers() > 0, "Invariant");
aoqi@0:       assert(yielded_workers() + finished_workers() == active_workers(),
aoqi@0:              "Inconsistent counts");
aoqi@0:       break;
aoqi@0:     }
aoqi@0:     case ACTIVE:
aoqi@0:     case INACTIVE:
aoqi@0:     case COMPLETING:
aoqi@0:     case YIELDING:
aoqi@0:     case ABORTING:
aoqi@0:     default:
aoqi@0:       ShouldNotReachHere();
aoqi@0:   }
aoqi@0: }
aoqi@0: 
aoqi@0: void YieldingFlexibleWorkGang::continue_task(
aoqi@0:   YieldingFlexibleGangTask* gang_task) {
aoqi@0: 
aoqi@0:   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
aoqi@0:   assert(task() != NULL && task() == gang_task, "Incorrect usage");
aoqi@0:   assert(_started_workers == _active_workers, "Precondition");
aoqi@0:   assert(_yielded_workers > 0 && yielding_task()->status() == YIELDED,
aoqi@0:          "Else why are we calling continue_task()");
aoqi@0:   // Restart the yielded gang workers
aoqi@0:   yielding_task()->set_status(ACTIVE);
aoqi@0:   monitor()->notify_all();
aoqi@0:   wait_for_gang();
aoqi@0: }
aoqi@0: 
aoqi@0: void YieldingFlexibleWorkGang::reset() {
aoqi@0:   _started_workers  = 0;
aoqi@0:   _finished_workers = 0;
aoqi@0:   yielding_task()->set_gang(NULL);
aoqi@0:   _task = NULL;    // unbind gang from task
aoqi@0: }
aoqi@0: 
aoqi@0: void YieldingFlexibleWorkGang::yield() {
aoqi@0:   assert(task() != NULL, "Inconsistency; should have task binding");
aoqi@0:   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
aoqi@0:   assert(yielded_workers() < active_workers(), "Consistency check");
aoqi@0:   if (yielding_task()->status() == ABORTING) {
aoqi@0:     // Do not yield; we need to abort as soon as possible
aoqi@0:     // XXX NOTE: This can cause a performance pathology in the
aoqi@0:     // current implementation in Mustang, as of today, and
aoqi@0:     // pre-Mustang in that as soon as an overflow occurs,
aoqi@0:     // yields will not be honoured. The right way to proceed
aoqi@0:     // of course is to fix bug # TBF, so that abort's cause
aoqi@0:     // us to return at each potential yield point.
aoqi@0:     return;
aoqi@0:   }
aoqi@0:   if (++_yielded_workers + finished_workers() == active_workers()) {
aoqi@0:     yielding_task()->set_status(YIELDED);
aoqi@0:     monitor()->notify_all();
aoqi@0:   } else {
aoqi@0:     yielding_task()->set_status(YIELDING);
aoqi@0:   }
aoqi@0: 
aoqi@0:   while (true) {
aoqi@0:     switch (yielding_task()->status()) {
aoqi@0:       case YIELDING:
aoqi@0:       case YIELDED: {
aoqi@0:         monitor()->wait(Mutex::_no_safepoint_check_flag);
aoqi@0:         break;  // from switch
aoqi@0:       }
aoqi@0:       case ACTIVE:
aoqi@0:       case ABORTING:
aoqi@0:       case COMPLETING: {
aoqi@0:         assert(_yielded_workers > 0, "Else why am i here?");
aoqi@0:         _yielded_workers--;
aoqi@0:         return;
aoqi@0:       }
aoqi@0:       case INACTIVE:
aoqi@0:       case ABORTED:
aoqi@0:       case COMPLETED:
aoqi@0:       default: {
aoqi@0:         ShouldNotReachHere();
aoqi@0:       }
aoqi@0:     }
aoqi@0:   }
aoqi@0:   // Only return is from inside switch statement above
aoqi@0:   ShouldNotReachHere();
aoqi@0: }
aoqi@0: 
aoqi@0: void YieldingFlexibleWorkGang::abort() {
aoqi@0:   assert(task() != NULL, "Inconsistency; should have task binding");
aoqi@0:   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
aoqi@0:   assert(yielded_workers() < active_workers(), "Consistency check");
aoqi@0:   #ifndef PRODUCT
aoqi@0:     switch (yielding_task()->status()) {
aoqi@0:       // allowed states
aoqi@0:       case ACTIVE:
aoqi@0:       case ABORTING:
aoqi@0:       case COMPLETING:
aoqi@0:       case YIELDING:
aoqi@0:         break;
aoqi@0:       // not allowed states
aoqi@0:       case INACTIVE:
aoqi@0:       case ABORTED:
aoqi@0:       case COMPLETED:
aoqi@0:       case YIELDED:
aoqi@0:       default:
aoqi@0:         ShouldNotReachHere();
aoqi@0:     }
aoqi@0:   #endif // !PRODUCT
aoqi@0:   Status prev_status = yielding_task()->status();
aoqi@0:   yielding_task()->set_status(ABORTING);
aoqi@0:   if (prev_status == YIELDING) {
aoqi@0:     assert(yielded_workers() > 0, "Inconsistency");
aoqi@0:     // At least one thread has yielded, wake it up
aoqi@0:     // so it can go back to waiting stations ASAP.
aoqi@0:     monitor()->notify_all();
aoqi@0:   }
aoqi@0: }
aoqi@0: 
aoqi@0: ///////////////////////////////
aoqi@0: // YieldingFlexibleGangTask
aoqi@0: ///////////////////////////////
aoqi@0: void YieldingFlexibleGangTask::yield() {
aoqi@0:   assert(gang() != NULL, "No gang to signal");
aoqi@0:   gang()->yield();
aoqi@0: }
aoqi@0: 
aoqi@0: void YieldingFlexibleGangTask::abort() {
aoqi@0:   assert(gang() != NULL, "No gang to signal");
aoqi@0:   gang()->abort();
aoqi@0: }
aoqi@0: 
aoqi@0: ///////////////////////////////
aoqi@0: // YieldingFlexibleGangWorker
aoqi@0: ///////////////////////////////
aoqi@0: void YieldingFlexibleGangWorker::loop() {
aoqi@0:   int previous_sequence_number = 0;
aoqi@0:   Monitor* gang_monitor = gang()->monitor();
aoqi@0:   MutexLockerEx ml(gang_monitor, Mutex::_no_safepoint_check_flag);
aoqi@0:   WorkData data;
aoqi@0:   int id;
aoqi@0:   while (true) {
aoqi@0:     // Check if there is work to do or if we have been asked
aoqi@0:     // to terminate
aoqi@0:     gang()->internal_worker_poll(&data);
aoqi@0:     if (data.terminate()) {
aoqi@0:       // We have been asked to terminate.
aoqi@0:       assert(gang()->task() == NULL, "No task binding");
aoqi@0:       // set_status(TERMINATED);
aoqi@0:       return;
aoqi@0:     } else if (data.task() != NULL &&
aoqi@0:                data.sequence_number() != previous_sequence_number) {
aoqi@0:       // There is work to be done.
aoqi@0:       // First check if we need to become active or if there
aoqi@0:       // are already the requisite number of workers
aoqi@0:       if (gang()->started_workers() == yf_gang()->active_workers()) {
aoqi@0:         // There are already enough workers, we do not need to
aoqi@0:         // to run; fall through and wait on monitor.
aoqi@0:       } else {
aoqi@0:         // We need to pitch in and do the work.
aoqi@0:         assert(gang()->started_workers() < yf_gang()->active_workers(),
aoqi@0:                "Unexpected state");
aoqi@0:         id = gang()->started_workers();
aoqi@0:         gang()->internal_note_start();
aoqi@0:         // Now, release the gang mutex and do the work.
aoqi@0:         {
aoqi@0:           MutexUnlockerEx mul(gang_monitor, Mutex::_no_safepoint_check_flag);
aoqi@0:           data.task()->work(id);   // This might include yielding
aoqi@0:         }
aoqi@0:         // Reacquire monitor and note completion of this worker
aoqi@0:         gang()->internal_note_finish();
aoqi@0:         // Update status of task based on whether all workers have
aoqi@0:         // finished or some have yielded
aoqi@0:         assert(data.task() == gang()->task(), "Confused task binding");
aoqi@0:         if (gang()->finished_workers() == yf_gang()->active_workers()) {
aoqi@0:           switch (data.yf_task()->status()) {
aoqi@0:             case ABORTING: {
aoqi@0:               data.yf_task()->set_status(ABORTED);
aoqi@0:               break;
aoqi@0:             }
aoqi@0:             case ACTIVE:
aoqi@0:             case COMPLETING: {
aoqi@0:               data.yf_task()->set_status(COMPLETED);
aoqi@0:               break;
aoqi@0:             }
aoqi@0:             default:
aoqi@0:               ShouldNotReachHere();
aoqi@0:           }
aoqi@0:           gang_monitor->notify_all();  // Notify overseer
aoqi@0:         } else { // at least one worker is still working or yielded
aoqi@0:           assert(gang()->finished_workers() < yf_gang()->active_workers(),
aoqi@0:                  "Counts inconsistent");
aoqi@0:           switch (data.yf_task()->status()) {
aoqi@0:             case ACTIVE: {
aoqi@0:               // first, but not only thread to complete
aoqi@0:               data.yf_task()->set_status(COMPLETING);
aoqi@0:               break;
aoqi@0:             }
aoqi@0:             case YIELDING: {
aoqi@0:               if (gang()->finished_workers() + yf_gang()->yielded_workers()
aoqi@0:                   == yf_gang()->active_workers()) {
aoqi@0:                 data.yf_task()->set_status(YIELDED);
aoqi@0:                 gang_monitor->notify_all();  // notify overseer
aoqi@0:               }
aoqi@0:               break;
aoqi@0:             }
aoqi@0:             case ABORTING:
aoqi@0:             case COMPLETING: {
aoqi@0:               break; // nothing to do
aoqi@0:             }
aoqi@0:             default: // everything else: INACTIVE, YIELDED, ABORTED, COMPLETED
aoqi@0:               ShouldNotReachHere();
aoqi@0:           }
aoqi@0:         }
aoqi@0:       }
aoqi@0:     }
aoqi@0:     // Remember the sequence number
aoqi@0:     previous_sequence_number = data.sequence_number();
aoqi@0:     // Wait for more work
aoqi@0:     gang_monitor->wait(Mutex::_no_safepoint_check_flag);
aoqi@0:   }
aoqi@0: }