1 /*

     2  * Copyright (c) 2005, 2015, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    20  * or visit www.oracle.com if you need additional information or have any

    21  * questions.

    22  *

    23  */

    24 

    25 #include "precompiled.hpp"

    26 #include "gc/cms/yieldingWorkgroup.hpp"

    27 #include "utilities/macros.hpp"

    28 

    29 // Forward declaration of classes declared here.

    30 

    31 class GangWorker;

    32 class WorkData;

    33 

    34 YieldingFlexibleWorkGang::YieldingFlexibleWorkGang(

    35   const char* name, uint workers, bool are_GC_task_threads) :

    36   FlexibleWorkGang(name, workers, are_GC_task_threads, false),

    37     _yielded_workers(0) {}

    38 

    39 GangWorker* YieldingFlexibleWorkGang::allocate_worker(uint which) {

    40   YieldingFlexibleGangWorker* new_member =

    41       new YieldingFlexibleGangWorker(this, which);

    42   return (YieldingFlexibleGangWorker*) new_member;

    43 }

    44 

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

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

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

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

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

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

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

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

    53 /////////////////////

    54 // Implementatiuon notes: remove before checking XXX

    55 /*

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

    57 Some subset of workers may have yielded and some may

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

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

    60 Once the task has been completed, the gang unbounds

    61 itself from the task.

    62 

    63 The yielding work gang thus exports two invokation

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

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

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

    67 already bound task that has yielded. Upon completion

    68 the binding is released and a new binding may be

    69 created.

    70 

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

    72 

    73 Overseer invokes run_task(*task).

    74    Lock gang monitor

    75    Check that there is no existing binding for the gang

    76    If so, abort with an error

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

    78    Set number of active workers (as asked)

    79    Notify workers that work is ready to be done

    80      [the requisite # workers would then start up

    81       and do the task]

    82    Wait on the monitor until either

    83      all work is completed or the task has yielded

    84      -- this is normally done through

    85         yielded + completed == active

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

    87    return appropriate status to caller

    88 

    89 Overseer invokes continue_task(*task),

    90    Lock gang monitor

    91    Check that task is the same as current binding

    92    If not, abort with an error

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

    94    Notify workers that they can continue from yield points

    95     New workers can also start up as required

    96       while satisfying the constraint that

    97          active + yielded does not exceed required number

    98    Wait (as above).

    99 

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

   101   our gangs will be of fixed population and will not

   102   therefore be flexible work gangs, just yielding work

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

   104   iteration.refinement introduce flexibility into

   105   the work gang.

   106 

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

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

   109   desist that simplified route.

   110 

   111  */

   112 /////////////////////

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

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

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

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

   117   // Bind task to gang

   118   _task = new_task;

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

   120   _sequence_number++;

   121 

   122   uint requested_size = new_task->requested_size();

   123   if (requested_size != 0) {

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

   125   } else {

   126     _active_workers = active_workers();

   127   }

   128   new_task->set_actual_size(_active_workers);

   129   new_task->set_for_termination(_active_workers);

   130 

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

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

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

   134   yielding_task()->set_status(ACTIVE);

   135 

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

   137   // and the rest will go back to sleep

   138   monitor()->notify_all();

   139   wait_for_gang();

   140 }

   141 

   142 void YieldingFlexibleWorkGang::wait_for_gang() {

   143 

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

   145   // Wait for task to complete or yield

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

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

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

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

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

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

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

   153   }

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

   155     case COMPLETED:

   156     case ABORTED: {

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

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

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

   160       break;

   161     }

   162     case YIELDED: {

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

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

   165              "Inconsistent counts");

   166       break;

   167     }

   168     case ACTIVE:

   169     case INACTIVE:

   170     case COMPLETING:

   171     case YIELDING:

   172     case ABORTING:

   173     default:

   174       ShouldNotReachHere();

   175   }

   176 }

   177 

   178 void YieldingFlexibleWorkGang::continue_task(

   179   YieldingFlexibleGangTask* gang_task) {

   180 

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

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

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

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

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

   186   // Restart the yielded gang workers

   187   yielding_task()->set_status(ACTIVE);

   188   monitor()->notify_all();

   189   wait_for_gang();

   190 }

   191 

   192 void YieldingFlexibleWorkGang::reset() {

   193   _started_workers  = 0;

   194   _finished_workers = 0;

   195   yielding_task()->set_gang(NULL);

   196   _task = NULL;    // unbind gang from task

   197 }

   198 

   199 void YieldingFlexibleWorkGang::yield() {

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

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

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

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

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

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

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

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

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

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

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

   211     return;

   212   }

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

   214     yielding_task()->set_status(YIELDED);

   215     monitor()->notify_all();

   216   } else {

   217     yielding_task()->set_status(YIELDING);

   218   }

   219 

   220   while (true) {

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

   222       case YIELDING:

   223       case YIELDED: {

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

   225         break;  // from switch

   226       }

   227       case ACTIVE:

   228       case ABORTING:

   229       case COMPLETING: {

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

   231         _yielded_workers--;

   232         return;

   233       }

   234       case INACTIVE:

   235       case ABORTED:

   236       case COMPLETED:

   237       default: {

   238         ShouldNotReachHere();

   239       }

   240     }

   241   }

   242   // Only return is from inside switch statement above

   243   ShouldNotReachHere();

   244 }

   245 

   246 void YieldingFlexibleWorkGang::abort() {

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

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

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

   250   #ifndef PRODUCT

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

   252       // allowed states

   253       case ACTIVE:

   254       case ABORTING:

   255       case COMPLETING:

   256       case YIELDING:

   257         break;

   258       // not allowed states

   259       case INACTIVE:

   260       case ABORTED:

   261       case COMPLETED:

   262       case YIELDED:

   263       default:

   264         ShouldNotReachHere();

   265     }

   266   #endif // !PRODUCT

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

   268   yielding_task()->set_status(ABORTING);

   269   if (prev_status == YIELDING) {

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

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

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

   273     monitor()->notify_all();

   274   }

   275 }

   276 

   277 ///////////////////////////////

   278 // YieldingFlexibleGangTask

   279 ///////////////////////////////

   280 void YieldingFlexibleGangTask::yield() {

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

   282   gang()->yield();

   283 }

   284 

   285 void YieldingFlexibleGangTask::abort() {

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

   287   gang()->abort();

   288 }

   289 

   290 ///////////////////////////////

   291 // YieldingFlexibleGangWorker

   292 ///////////////////////////////

   293 void YieldingFlexibleGangWorker::loop() {

   294   int previous_sequence_number = 0;

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

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

   297   WorkData data;

   298   int id;

   299   while (true) {

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

   301     // to terminate

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

   303     if (data.terminate()) {

   304       // We have been asked to terminate.

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

   306       // set_status(TERMINATED);

   307       return;

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

   309                data.sequence_number() != previous_sequence_number) {

   310       // There is work to be done.

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

   312       // are already the requisite number of workers

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

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

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

   316       } else {

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

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

   319                "Unexpected state");

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

   321         gang()->internal_note_start();

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

   323         {

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

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

   326         }

   327         // Reacquire monitor and note completion of this worker

   328         gang()->internal_note_finish();

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

   330         // finished or some have yielded

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

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

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

   334             case ABORTING: {

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

   336               break;

   337             }

   338             case ACTIVE:

   339             case COMPLETING: {

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

   341               break;

   342             }

   343             default:

   344               ShouldNotReachHere();

   345           }

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

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

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

   349                  "Counts inconsistent");

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

   351             case ACTIVE: {

   352               // first, but not only thread to complete

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

   354               break;

   355             }

   356             case YIELDING: {

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

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

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

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

   361               }

   362               break;

   363             }

   364             case ABORTING:

   365             case COMPLETING: {

   366               break; // nothing to do

   367             }

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

   369               ShouldNotReachHere();

   370           }

   371         }

   372       }

   373     }

   374     // Remember the sequence number

   375     previous_sequence_number = data.sequence_number();

   376     // Wait for more work

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

   378   }

   379 }