1 /*

     2  * Copyright 2005 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    20  * CA 95054 USA or visit www.sun.com if you need additional information or

    21  * have any questions.

    22  *

    23  */

    24 

    25 # include "incls/_precompiled.incl"

    26 # include "incls/_yieldingWorkgroup.cpp.incl"

    27 

    28 // Forward declaration of classes declared here.

    29 

    30 class GangWorker;

    31 class WorkData;

    32 

    33 YieldingFlexibleWorkGang::YieldingFlexibleWorkGang(

    34   const char* name, int workers, bool are_GC_threads) :

    35   AbstractWorkGang(name, are_GC_threads) {

    36   // Save arguments.

    37   _total_workers = workers;

    38   assert(_total_workers > 0, "Must have more than 1 worker");

    39 

    40   _yielded_workers = 0;

    41 

    42   if (TraceWorkGang) {

    43     tty->print_cr("Constructing work gang %s with %d threads", name, workers);

    44   }

    45   _gang_workers = NEW_C_HEAP_ARRAY(GangWorker*, workers);

    46   assert(gang_workers() != NULL, "Failed to allocate gang workers");

    47   for (int worker = 0; worker < total_workers(); worker += 1) {

    48     YieldingFlexibleGangWorker* new_worker =

    49       new YieldingFlexibleGangWorker(this, worker);

    50     assert(new_worker != NULL, "Failed to allocate YieldingFlexibleGangWorker");

    51     _gang_workers[worker] = new_worker;

    52     if (new_worker == NULL || !os::create_thread(new_worker, os::pgc_thread))

    53       vm_exit_out_of_memory(0, "Cannot create worker GC thread. Out of system resources.");

    54     if (!DisableStartThread) {

    55       os::start_thread(new_worker);

    56     }

    57   }

    58 }

    59 

    60 // Run a task; returns when the task is done, or the workers yield,

    61 // or the task is aborted, or the work gang is terminated via stop().

    62 // A task that has been yielded can be continued via this interface

    63 // by using the same task repeatedly as the argument to the call.

    64 // It is expected that the YieldingFlexibleGangTask carries the appropriate

    65 // continuation information used by workers to continue the task

    66 // from its last yield point. Thus, a completed task will return

    67 // immediately with no actual work having been done by the workers.

    68 /////////////////////

    69 // Implementatiuon notes: remove before checking XXX

    70 /*

    71 Each gang is working on a task at a certain time.

    72 Some subset of workers may have yielded and some may

    73 have finished their quota of work. Until this task has

    74 been completed, the workers are bound to that task.

    75 Once the task has been completed, the gang unbounds

    76 itself from the task.

    77 

    78 The yielding work gang thus exports two invokation

    79 interfaces: run_task() and continue_task(). The

    80 first is used to initiate a new task and bind it

    81 to the workers; the second is used to continue an

    82 already bound task that has yielded. Upon completion

    83 the binding is released and a new binding may be

    84 created.

    85 

    86 The shape of a yielding work gang is as follows:

    87 

    88 Overseer invokes run_task(*task).

    89    Lock gang monitor

    90    Check that there is no existing binding for the gang

    91    If so, abort with an error

    92    Else, create a new binding of this gang to the given task

    93    Set number of active workers (as asked)

    94    Notify workers that work is ready to be done

    95      [the requisite # workers would then start up

    96       and do the task]

    97    Wait on the monitor until either

    98      all work is completed or the task has yielded

    99      -- this is normally done through

   100         yielded + completed == active

   101         [completed workers are rest to idle state by overseer?]

   102    return appropriate status to caller

   103 

   104 Overseer invokes continue_task(*task),

   105    Lock gang monitor

   106    Check that task is the same as current binding

   107    If not, abort with an error

   108    Else, set the number of active workers as requested?

   109    Notify workers that they can continue from yield points

   110     New workers can also start up as required

   111       while satisfying the constraint that

   112          active + yielded does not exceed required number

   113    Wait (as above).

   114 

   115 NOTE: In the above, for simplicity in a first iteration

   116   our gangs will be of fixed population and will not

   117   therefore be flexible work gangs, just yielding work

   118   gangs. Once this works well, we will in a second

   119   iteration.refinement introduce flexibility into

   120   the work gang.

   121 

   122 NOTE: we can always create a new gang per each iteration

   123   in order to get the flexibility, but we will for now

   124   desist that simplified route.

   125 

   126  */

   127 /////////////////////

   128 void YieldingFlexibleWorkGang::start_task(YieldingFlexibleGangTask* new_task) {

   129   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);

   130   assert(task() == NULL, "Gang currently tied to a task");

   131   assert(new_task != NULL, "Null task");

   132   // Bind task to gang

   133   _task = new_task;

   134   new_task->set_gang(this);  // Establish 2-way binding to support yielding

   135   _sequence_number++;

   136 

   137   int requested_size = new_task->requested_size();

   138   assert(requested_size >= 0, "Should be non-negative");

   139   if (requested_size != 0) {

   140     _active_workers = MIN2(requested_size, total_workers());

   141   } else {

   142     _active_workers = total_workers();

   143   }

   144   new_task->set_actual_size(_active_workers);

   145 

   146   assert(_started_workers == 0, "Tabula rasa non");

   147   assert(_finished_workers == 0, "Tabula rasa non");

   148   assert(_yielded_workers == 0, "Tabula rasa non");

   149   yielding_task()->set_status(ACTIVE);

   150 

   151   // Wake up all the workers, the first few will get to work,

   152   // and the rest will go back to sleep

   153   monitor()->notify_all();

   154   wait_for_gang();

   155 }

   156 

   157 void YieldingFlexibleWorkGang::wait_for_gang() {

   158 

   159   assert(monitor()->owned_by_self(), "Data race");

   160   // Wait for task to complete or yield

   161   for (Status status = yielding_task()->status();

   162        status != COMPLETED && status != YIELDED && status != ABORTED;

   163        status = yielding_task()->status()) {

   164     assert(started_workers() <= active_workers(), "invariant");

   165     assert(finished_workers() <= active_workers(), "invariant");

   166     assert(yielded_workers() <= active_workers(), "invariant");

   167     monitor()->wait(Mutex::_no_safepoint_check_flag);

   168   }

   169   switch (yielding_task()->status()) {

   170     case COMPLETED:

   171     case ABORTED: {

   172       assert(finished_workers() == active_workers(), "Inconsistent status");

   173       assert(yielded_workers() == 0, "Invariant");

   174       reset();   // for next task; gang<->task binding released

   175       break;

   176     }

   177     case YIELDED: {

   178       assert(yielded_workers() > 0, "Invariant");

   179       assert(yielded_workers() + finished_workers() == active_workers(),

   180              "Inconsistent counts");

   181       break;

   182     }

   183     case ACTIVE:

   184     case INACTIVE:

   185     case COMPLETING:

   186     case YIELDING:

   187     case ABORTING:

   188     default:

   189       ShouldNotReachHere();

   190   }

   191 }

   192 

   193 void YieldingFlexibleWorkGang::continue_task(

   194   YieldingFlexibleGangTask* gang_task) {

   195 

   196   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);

   197   assert(task() != NULL && task() == gang_task, "Incorrect usage");

   198   // assert(_active_workers == total_workers(), "For now");

   199   assert(_started_workers == _active_workers, "Precondition");

   200   assert(_yielded_workers > 0 && yielding_task()->status() == YIELDED,

   201          "Else why are we calling continue_task()");

   202   // Restart the yielded gang workers

   203   yielding_task()->set_status(ACTIVE);

   204   monitor()->notify_all();

   205   wait_for_gang();

   206 }

   207 

   208 void YieldingFlexibleWorkGang::reset() {

   209   _started_workers  = 0;

   210   _finished_workers = 0;

   211   _active_workers   = 0;

   212   yielding_task()->set_gang(NULL);

   213   _task = NULL;    // unbind gang from task

   214 }

   215 

   216 void YieldingFlexibleWorkGang::yield() {

   217   assert(task() != NULL, "Inconsistency; should have task binding");

   218   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);

   219   assert(yielded_workers() < active_workers(), "Consistency check");

   220   if (yielding_task()->status() == ABORTING) {

   221     // Do not yield; we need to abort as soon as possible

   222     // XXX NOTE: This can cause a performance pathology in the

   223     // current implementation in Mustang, as of today, and

   224     // pre-Mustang in that as soon as an overflow occurs,

   225     // yields will not be honoured. The right way to proceed

   226     // of course is to fix bug # TBF, so that abort's cause

   227     // us to return at each potential yield point.

   228     return;

   229   }

   230   if (++_yielded_workers + finished_workers() == active_workers()) {

   231     yielding_task()->set_status(YIELDED);

   232     monitor()->notify_all();

   233   } else {

   234     yielding_task()->set_status(YIELDING);

   235   }

   236 

   237   while (true) {

   238     switch (yielding_task()->status()) {

   239       case YIELDING:

   240       case YIELDED: {

   241         monitor()->wait(Mutex::_no_safepoint_check_flag);

   242         break;  // from switch

   243       }

   244       case ACTIVE:

   245       case ABORTING:

   246       case COMPLETING: {

   247         assert(_yielded_workers > 0, "Else why am i here?");

   248         _yielded_workers--;

   249         return;

   250       }

   251       case INACTIVE:

   252       case ABORTED:

   253       case COMPLETED:

   254       default: {

   255         ShouldNotReachHere();

   256       }

   257     }

   258   }

   259   // Only return is from inside switch statement above

   260   ShouldNotReachHere();

   261 }

   262 

   263 void YieldingFlexibleWorkGang::abort() {

   264   assert(task() != NULL, "Inconsistency; should have task binding");

   265   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);

   266   assert(yielded_workers() < active_workers(), "Consistency check");

   267   #ifndef PRODUCT

   268     switch (yielding_task()->status()) {

   269       // allowed states

   270       case ACTIVE:

   271       case ABORTING:

   272       case COMPLETING:

   273       case YIELDING:

   274         break;

   275       // not allowed states

   276       case INACTIVE:

   277       case ABORTED:

   278       case COMPLETED:

   279       case YIELDED:

   280       default:

   281         ShouldNotReachHere();

   282     }

   283   #endif // !PRODUCT

   284   Status prev_status = yielding_task()->status();

   285   yielding_task()->set_status(ABORTING);

   286   if (prev_status == YIELDING) {

   287     assert(yielded_workers() > 0, "Inconsistency");

   288     // At least one thread has yielded, wake it up

   289     // so it can go back to waiting stations ASAP.

   290     monitor()->notify_all();

   291   }

   292 }

   293 

   294 ///////////////////////////////

   295 // YieldingFlexibleGangTask

   296 ///////////////////////////////

   297 void YieldingFlexibleGangTask::yield() {

   298   assert(gang() != NULL, "No gang to signal");

   299   gang()->yield();

   300 }

   301 

   302 void YieldingFlexibleGangTask::abort() {

   303   assert(gang() != NULL, "No gang to signal");

   304   gang()->abort();

   305 }

   306 

   307 ///////////////////////////////

   308 // YieldingFlexibleGangWorker

   309 ///////////////////////////////

   310 void YieldingFlexibleGangWorker::loop() {

   311   int previous_sequence_number = 0;

   312   Monitor* gang_monitor = gang()->monitor();

   313   MutexLockerEx ml(gang_monitor, Mutex::_no_safepoint_check_flag);

   314   WorkData data;

   315   int id;

   316   while (true) {

   317     // Check if there is work to do or if we have been asked

   318     // to terminate

   319     gang()->internal_worker_poll(&data);

   320     if (data.terminate()) {

   321       // We have been asked to terminate.

   322       assert(gang()->task() == NULL, "No task binding");

   323       // set_status(TERMINATED);

   324       return;

   325     } else if (data.task() != NULL &&

   326                data.sequence_number() != previous_sequence_number) {

   327       // There is work to be done.

   328       // First check if we need to become active or if there

   329       // are already the requisite number of workers

   330       if (gang()->started_workers() == yf_gang()->active_workers()) {

   331         // There are already enough workers, we do not need to

   332         // to run; fall through and wait on monitor.

   333       } else {

   334         // We need to pitch in and do the work.

   335         assert(gang()->started_workers() < yf_gang()->active_workers(),

   336                "Unexpected state");

   337         id = gang()->started_workers();

   338         gang()->internal_note_start();

   339         // Now, release the gang mutex and do the work.

   340         {

   341           MutexUnlockerEx mul(gang_monitor, Mutex::_no_safepoint_check_flag);

   342           data.task()->work(id);   // This might include yielding

   343         }

   344         // Reacquire monitor and note completion of this worker

   345         gang()->internal_note_finish();

   346         // Update status of task based on whether all workers have

   347         // finished or some have yielded

   348         assert(data.task() == gang()->task(), "Confused task binding");

   349         if (gang()->finished_workers() == yf_gang()->active_workers()) {

   350           switch (data.yf_task()->status()) {

   351             case ABORTING: {

   352               data.yf_task()->set_status(ABORTED);

   353               break;

   354             }

   355             case ACTIVE:

   356             case COMPLETING: {

   357               data.yf_task()->set_status(COMPLETED);

   358               break;

   359             }

   360             default:

   361               ShouldNotReachHere();

   362           }

   363           gang_monitor->notify_all();  // Notify overseer

   364         } else { // at least one worker is still working or yielded

   365           assert(gang()->finished_workers() < yf_gang()->active_workers(),

   366                  "Counts inconsistent");

   367           switch (data.yf_task()->status()) {

   368             case ACTIVE: {

   369               // first, but not only thread to complete

   370               data.yf_task()->set_status(COMPLETING);

   371               break;

   372             }

   373             case YIELDING: {

   374               if (gang()->finished_workers() + yf_gang()->yielded_workers()

   375                   == yf_gang()->active_workers()) {

   376                 data.yf_task()->set_status(YIELDED);

   377                 gang_monitor->notify_all();  // notify overseer

   378               }

   379               break;

   380             }

   381             case ABORTING:

   382             case COMPLETING: {

   383               break; // nothing to do

   384             }

   385             default: // everything else: INACTIVE, YIELDED, ABORTED, COMPLETED

   386               ShouldNotReachHere();

   387           }

   388         }

   389       }

   390     }

   391     // Remember the sequence number

   392     previous_sequence_number = data.sequence_number();

   393     // Wait for more work

   394     gang_monitor->wait(Mutex::_no_safepoint_check_flag);

   395   }

   396 }