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