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 YieldingFlexibleGangWorker::YieldingFlexibleGangWorker(YieldingFlexibleWorkGang* gang, int id)
  30     : AbstractGangWorker(gang, id) {}
  31 
  32 YieldingFlexibleWorkGang::YieldingFlexibleWorkGang(
  33     const char* name, uint workers, bool are_GC_task_threads) :
  34          AbstractWorkGang(name, workers, are_GC_task_threads, false),
  35          _yielded_workers(0),
  36          _started_workers(0),
  37          _finished_workers(0),
  38          _sequence_number(0),
  39          _task(NULL) {
  40 
  41   // Other initialization.
  42   _monitor = new Monitor(/* priority */       Mutex::leaf,
  43                          /* name */           "WorkGroup monitor",
  44                          /* allow_vm_block */ are_GC_task_threads,
  45                                               Monitor::_safepoint_check_sometimes);
  46 
  47   assert(monitor() != NULL, "Failed to allocate monitor");
  48 }
  49 
  50 AbstractGangWorker* YieldingFlexibleWorkGang::allocate_worker(uint which) {
  51   return new YieldingFlexibleGangWorker(this, which);
  52 }
  53 
  54 void YieldingFlexibleWorkGang::internal_worker_poll(YieldingWorkData* data) const {
  55   assert(data != NULL, "worker data is null");
  56   data->set_task(task());
  57   data->set_sequence_number(sequence_number());
  58 }
  59 
  60 void YieldingFlexibleWorkGang::internal_note_start() {
  61   assert(monitor()->owned_by_self(), "note_finish is an internal method");
  62   _started_workers += 1;
  63 }
  64 
  65 void YieldingFlexibleWorkGang::internal_note_finish() {
  66   assert(monitor()->owned_by_self(), "note_finish is an internal method");
  67   _finished_workers += 1;
  68 }
  69 
  70 // Run a task; returns when the task is done, or the workers yield,
  71 // or the task is aborted.
  72 // A task that has been yielded can be continued via this interface
  73 // by using the same task repeatedly as the argument to the call.
  74 // It is expected that the YieldingFlexibleGangTask carries the appropriate
  75 // continuation information used by workers to continue the task
  76 // from its last yield point. Thus, a completed task will return
  77 // immediately with no actual work having been done by the workers.
  78 /////////////////////
  79 // Implementatiuon notes: remove before checking XXX
  80 /*
  81 Each gang is working on a task at a certain time.
  82 Some subset of workers may have yielded and some may
  83 have finished their quota of work. Until this task has
  84 been completed, the workers are bound to that task.
  85 Once the task has been completed, the gang unbounds
  86 itself from the task.
  87 
  88 The yielding work gang thus exports two invokation
  89 interfaces: run_task() and continue_task(). The
  90 first is used to initiate a new task and bind it
  91 to the workers; the second is used to continue an
  92 already bound task that has yielded. Upon completion
  93 the binding is released and a new binding may be
  94 created.
  95 
  96 The shape of a yielding work gang is as follows:
  97 
  98 Overseer invokes run_task(*task).
  99    Lock gang monitor
 100    Check that there is no existing binding for the gang
 101    If so, abort with an error
 102    Else, create a new binding of this gang to the given task
 103    Set number of active workers (as asked)
 104    Notify workers that work is ready to be done
 105      [the requisite # workers would then start up
 106       and do the task]
 107    Wait on the monitor until either
 108      all work is completed or the task has yielded
 109      -- this is normally done through
 110         yielded + completed == active
 111         [completed workers are rest to idle state by overseer?]
 112    return appropriate status to caller
 113 
 114 Overseer invokes continue_task(*task),
 115    Lock gang monitor
 116    Check that task is the same as current binding
 117    If not, abort with an error
 118    Else, set the number of active workers as requested?
 119    Notify workers that they can continue from yield points
 120     New workers can also start up as required
 121       while satisfying the constraint that
 122          active + yielded does not exceed required number
 123    Wait (as above).
 124 
 125 NOTE: In the above, for simplicity in a first iteration
 126   our gangs will be of fixed population and will not
 127   therefore be flexible work gangs, just yielding work
 128   gangs. Once this works well, we will in a second
 129   iteration.refinement introduce flexibility into
 130   the work gang.
 131 
 132 NOTE: we can always create a new gang per each iteration
 133   in order to get the flexibility, but we will for now
 134   desist that simplified route.
 135 
 136  */
 137 /////////////////////
 138 void YieldingFlexibleWorkGang::start_task(YieldingFlexibleGangTask* new_task) {
 139   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
 140   assert(task() == NULL, "Gang currently tied to a task");
 141   assert(new_task != NULL, "Null task");
 142   // Bind task to gang
 143   _task = new_task;
 144   new_task->set_gang(this);  // Establish 2-way binding to support yielding
 145   _sequence_number++;
 146 
 147   uint requested_size = new_task->requested_size();
 148   if (requested_size != 0) {
 149     _active_workers = MIN2(requested_size, total_workers());
 150   } else {
 151     _active_workers = active_workers();
 152   }
 153   new_task->set_actual_size(_active_workers);
 154   new_task->set_for_termination(_active_workers);
 155 
 156   assert(_started_workers == 0, "Tabula rasa non");
 157   assert(_finished_workers == 0, "Tabula rasa non");
 158   assert(_yielded_workers == 0, "Tabula rasa non");
 159   yielding_task()->set_status(ACTIVE);
 160 
 161   // Wake up all the workers, the first few will get to work,
 162   // and the rest will go back to sleep
 163   monitor()->notify_all();
 164   wait_for_gang();
 165 }
 166 
 167 void YieldingFlexibleWorkGang::wait_for_gang() {
 168 
 169   assert(monitor()->owned_by_self(), "Data race");
 170   // Wait for task to complete or yield
 171   for (Status status = yielding_task()->status();
 172        status != COMPLETED && status != YIELDED && status != ABORTED;
 173        status = yielding_task()->status()) {
 174     assert(started_workers() <= active_workers(), "invariant");
 175     assert(finished_workers() <= active_workers(), "invariant");
 176     assert(yielded_workers() <= active_workers(), "invariant");
 177     monitor()->wait(Mutex::_no_safepoint_check_flag);
 178   }
 179   switch (yielding_task()->status()) {
 180     case COMPLETED:
 181     case ABORTED: {
 182       assert(finished_workers() == active_workers(), "Inconsistent status");
 183       assert(yielded_workers() == 0, "Invariant");
 184       reset();   // for next task; gang<->task binding released
 185       break;
 186     }
 187     case YIELDED: {
 188       assert(yielded_workers() > 0, "Invariant");
 189       assert(yielded_workers() + finished_workers() == active_workers(),
 190              "Inconsistent counts");
 191       break;
 192     }
 193     case ACTIVE:
 194     case INACTIVE:
 195     case COMPLETING:
 196     case YIELDING:
 197     case ABORTING:
 198     default:
 199       ShouldNotReachHere();
 200   }
 201 }
 202 
 203 void YieldingFlexibleWorkGang::continue_task(
 204   YieldingFlexibleGangTask* gang_task) {
 205 
 206   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
 207   assert(task() != NULL && task() == gang_task, "Incorrect usage");
 208   assert(_started_workers == _active_workers, "Precondition");
 209   assert(_yielded_workers > 0 && yielding_task()->status() == YIELDED,
 210          "Else why are we calling continue_task()");
 211   // Restart the yielded gang workers
 212   yielding_task()->set_status(ACTIVE);
 213   monitor()->notify_all();
 214   wait_for_gang();
 215 }
 216 
 217 void YieldingFlexibleWorkGang::reset() {
 218   _started_workers  = 0;
 219   _finished_workers = 0;
 220   yielding_task()->set_gang(NULL);
 221   _task = NULL;    // unbind gang from task
 222 }
 223 
 224 void YieldingFlexibleWorkGang::yield() {
 225   assert(task() != NULL, "Inconsistency; should have task binding");
 226   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
 227   assert(yielded_workers() < active_workers(), "Consistency check");
 228   if (yielding_task()->status() == ABORTING) {
 229     // Do not yield; we need to abort as soon as possible
 230     // XXX NOTE: This can cause a performance pathology in the
 231     // current implementation in Mustang, as of today, and
 232     // pre-Mustang in that as soon as an overflow occurs,
 233     // yields will not be honoured. The right way to proceed
 234     // of course is to fix bug # TBF, so that abort's cause
 235     // us to return at each potential yield point.
 236     return;
 237   }
 238   if (++_yielded_workers + finished_workers() == active_workers()) {
 239     yielding_task()->set_status(YIELDED);
 240     monitor()->notify_all();
 241   } else {
 242     yielding_task()->set_status(YIELDING);
 243   }
 244 
 245   while (true) {
 246     switch (yielding_task()->status()) {
 247       case YIELDING:
 248       case YIELDED: {
 249         monitor()->wait(Mutex::_no_safepoint_check_flag);
 250         break;  // from switch
 251       }
 252       case ACTIVE:
 253       case ABORTING:
 254       case COMPLETING: {
 255         assert(_yielded_workers > 0, "Else why am i here?");
 256         _yielded_workers--;
 257         return;
 258       }
 259       case INACTIVE:
 260       case ABORTED:
 261       case COMPLETED:
 262       default: {
 263         ShouldNotReachHere();
 264       }
 265     }
 266   }
 267   // Only return is from inside switch statement above
 268   ShouldNotReachHere();
 269 }
 270 
 271 void YieldingFlexibleWorkGang::abort() {
 272   assert(task() != NULL, "Inconsistency; should have task binding");
 273   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
 274   assert(yielded_workers() < active_workers(), "Consistency check");
 275   #ifndef PRODUCT
 276     switch (yielding_task()->status()) {
 277       // allowed states
 278       case ACTIVE:
 279       case ABORTING:
 280       case COMPLETING:
 281       case YIELDING:
 282         break;
 283       // not allowed states
 284       case INACTIVE:
 285       case ABORTED:
 286       case COMPLETED:
 287       case YIELDED:
 288       default:
 289         ShouldNotReachHere();
 290     }
 291   #endif // !PRODUCT
 292   Status prev_status = yielding_task()->status();
 293   yielding_task()->set_status(ABORTING);
 294   if (prev_status == YIELDING) {
 295     assert(yielded_workers() > 0, "Inconsistency");
 296     // At least one thread has yielded, wake it up
 297     // so it can go back to waiting stations ASAP.
 298     monitor()->notify_all();
 299   }
 300 }
 301 
 302 ///////////////////////////////
 303 // YieldingFlexibleGangTask
 304 ///////////////////////////////
 305 void YieldingFlexibleGangTask::yield() {
 306   assert(gang() != NULL, "No gang to signal");
 307   gang()->yield();
 308 }
 309 
 310 void YieldingFlexibleGangTask::abort() {
 311   assert(gang() != NULL, "No gang to signal");
 312   gang()->abort();
 313 }
 314 
 315 ///////////////////////////////
 316 // YieldingFlexibleGangWorker
 317 ///////////////////////////////
 318 void YieldingFlexibleGangWorker::loop() {
 319   int previous_sequence_number = 0;
 320   Monitor* gang_monitor = yf_gang()->monitor();
 321   MutexLockerEx ml(gang_monitor, Mutex::_no_safepoint_check_flag);
 322   YieldingWorkData data;
 323   int id;
 324   while (true) {
 325     // Check if there is work to do.
 326     yf_gang()->internal_worker_poll(&data);
 327     if (data.task() != NULL && data.sequence_number() != previous_sequence_number) {
 328       // There is work to be done.
 329       // First check if we need to become active or if there
 330       // are already the requisite number of workers
 331       if (yf_gang()->started_workers() == yf_gang()->active_workers()) {
 332         // There are already enough workers, we do not need to
 333         // to run; fall through and wait on monitor.
 334       } else {
 335         // We need to pitch in and do the work.
 336         assert(yf_gang()->started_workers() < yf_gang()->active_workers(),
 337                "Unexpected state");
 338         id = yf_gang()->started_workers();
 339         yf_gang()->internal_note_start();
 340         // Now, release the gang mutex and do the work.
 341         {
 342           MutexUnlockerEx mul(gang_monitor, Mutex::_no_safepoint_check_flag);

 343           data.task()->work(id);   // This might include yielding
 344         }
 345         // Reacquire monitor and note completion of this worker
 346         yf_gang()->internal_note_finish();
 347         // Update status of task based on whether all workers have
 348         // finished or some have yielded
 349         assert(data.task() == yf_gang()->task(), "Confused task binding");
 350         if (yf_gang()->finished_workers() == yf_gang()->active_workers()) {
 351           switch (data.yf_task()->status()) {
 352             case ABORTING: {
 353               data.yf_task()->set_status(ABORTED);
 354               break;
 355             }
 356             case ACTIVE:
 357             case COMPLETING: {
 358               data.yf_task()->set_status(COMPLETED);
 359               break;
 360             }
 361             default:
 362               ShouldNotReachHere();
 363           }
 364           gang_monitor->notify_all();  // Notify overseer
 365         } else { // at least one worker is still working or yielded
 366           assert(yf_gang()->finished_workers() < yf_gang()->active_workers(),
 367                  "Counts inconsistent");
 368           switch (data.yf_task()->status()) {
 369             case ACTIVE: {
 370               // first, but not only thread to complete
 371               data.yf_task()->set_status(COMPLETING);
 372               break;
 373             }
 374             case YIELDING: {
 375               if (yf_gang()->finished_workers() + yf_gang()->yielded_workers()
 376                   == yf_gang()->active_workers()) {
 377                 data.yf_task()->set_status(YIELDED);
 378                 gang_monitor->notify_all();  // notify overseer
 379               }
 380               break;
 381             }
 382             case ABORTING:
 383             case COMPLETING: {
 384               break; // nothing to do
 385             }
 386             default: // everything else: INACTIVE, YIELDED, ABORTED, COMPLETED
 387               ShouldNotReachHere();
 388           }
 389         }
 390       }
 391     }
 392     // Remember the sequence number
 393     previous_sequence_number = data.sequence_number();
 394     // Wait for more work
 395     gang_monitor->wait(Mutex::_no_safepoint_check_flag);
 396   }
 397 }
--- EOF ---