1 /*
   2  * Copyright (c) 2002, 2016, 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/parallel/gcTaskManager.hpp"
  27 #include "gc/parallel/gcTaskThread.hpp"
  28 #include "gc/shared/gcId.hpp"
  29 #include "gc/shared/workerManager.hpp"
  30 #include "logging/log.hpp"
  31 #include "memory/allocation.hpp"
  32 #include "memory/allocation.inline.hpp"
  33 #include "memory/resourceArea.hpp"
  34 #include "runtime/mutex.hpp"
  35 #include "runtime/mutexLocker.hpp"
  36 #include "runtime/orderAccess.inline.hpp"
  37 #include "runtime/os.hpp"
  38 
  39 //
  40 // GCTask
  41 //
  42 
  43 const char* GCTask::Kind::to_string(kind value) {
  44   const char* result = "unknown GCTask kind";
  45   switch (value) {
  46   default:
  47     result = "unknown GCTask kind";
  48     break;
  49   case unknown_task:
  50     result = "unknown task";
  51     break;
  52   case ordinary_task:
  53     result = "ordinary task";
  54     break;
  55   case wait_for_barrier_task:
  56     result = "wait for barrier task";
  57     break;
  58   case noop_task:
  59     result = "noop task";
  60     break;
  61   case idle_task:
  62     result = "idle task";
  63     break;
  64   }
  65   return result;
  66 };
  67 
  68 GCTask::GCTask() {
  69   initialize(Kind::ordinary_task, GCId::current());
  70 }
  71 
  72 GCTask::GCTask(Kind::kind kind) {
  73   initialize(kind, GCId::current());
  74 }
  75 
  76 GCTask::GCTask(Kind::kind kind, uint gc_id) {
  77   initialize(kind, gc_id);
  78 }
  79 
  80 void GCTask::initialize(Kind::kind kind, uint gc_id) {
  81   _kind = kind;
  82   _affinity = GCTaskManager::sentinel_worker();
  83   _older = NULL;
  84   _newer = NULL;
  85   _gc_id = gc_id;
  86 }
  87 
  88 void GCTask::destruct() {
  89   assert(older() == NULL, "shouldn't have an older task");
  90   assert(newer() == NULL, "shouldn't have a newer task");
  91   // Nothing to do.
  92 }
  93 
  94 NOT_PRODUCT(
  95 void GCTask::print(const char* message) const {
  96   tty->print(INTPTR_FORMAT " <- " INTPTR_FORMAT "(%u) -> " INTPTR_FORMAT,
  97              p2i(newer()), p2i(this), affinity(), p2i(older()));
  98 }
  99 )
 100 
 101 //
 102 // GCTaskQueue
 103 //
 104 
 105 GCTaskQueue* GCTaskQueue::create() {
 106   GCTaskQueue* result = new GCTaskQueue(false);
 107   if (TraceGCTaskQueue) {
 108     tty->print_cr("GCTaskQueue::create()"
 109                   " returns " INTPTR_FORMAT, p2i(result));
 110   }
 111   return result;
 112 }
 113 
 114 GCTaskQueue* GCTaskQueue::create_on_c_heap() {
 115   GCTaskQueue* result = new(ResourceObj::C_HEAP, mtGC) GCTaskQueue(true);
 116   if (TraceGCTaskQueue) {
 117     tty->print_cr("GCTaskQueue::create_on_c_heap()"
 118                   " returns " INTPTR_FORMAT,
 119                   p2i(result));
 120   }
 121   return result;
 122 }
 123 
 124 GCTaskQueue::GCTaskQueue(bool on_c_heap) :
 125   _is_c_heap_obj(on_c_heap) {
 126   initialize();
 127   if (TraceGCTaskQueue) {
 128     tty->print_cr("[" INTPTR_FORMAT "]"
 129                   " GCTaskQueue::GCTaskQueue() constructor",
 130                   p2i(this));
 131   }
 132 }
 133 
 134 void GCTaskQueue::destruct() {
 135   // Nothing to do.
 136 }
 137 
 138 void GCTaskQueue::destroy(GCTaskQueue* that) {
 139   if (TraceGCTaskQueue) {
 140     tty->print_cr("[" INTPTR_FORMAT "]"
 141                   " GCTaskQueue::destroy()"
 142                   "  is_c_heap_obj:  %s",
 143                   p2i(that),
 144                   that->is_c_heap_obj() ? "true" : "false");
 145   }
 146   // That instance may have been allocated as a CHeapObj,
 147   // in which case we have to free it explicitly.
 148   if (that != NULL) {
 149     that->destruct();
 150     assert(that->is_empty(), "should be empty");
 151     if (that->is_c_heap_obj()) {
 152       FreeHeap(that);
 153     }
 154   }
 155 }
 156 
 157 void GCTaskQueue::initialize() {
 158   set_insert_end(NULL);
 159   set_remove_end(NULL);
 160   set_length(0);
 161 }
 162 
 163 // Enqueue one task.
 164 void GCTaskQueue::enqueue(GCTask* task) {
 165   if (TraceGCTaskQueue) {
 166     tty->print_cr("[" INTPTR_FORMAT "]"
 167                   " GCTaskQueue::enqueue(task: "
 168                   INTPTR_FORMAT ")",
 169                   p2i(this), p2i(task));
 170     print("before:");
 171   }
 172   assert(task != NULL, "shouldn't have null task");
 173   assert(task->older() == NULL, "shouldn't be on queue");
 174   assert(task->newer() == NULL, "shouldn't be on queue");
 175   task->set_newer(NULL);
 176   task->set_older(insert_end());
 177   if (is_empty()) {
 178     set_remove_end(task);
 179   } else {
 180     insert_end()->set_newer(task);
 181   }
 182   set_insert_end(task);
 183   increment_length();
 184   verify_length();
 185   if (TraceGCTaskQueue) {
 186     print("after:");
 187   }
 188 }
 189 
 190 // Enqueue a whole list of tasks.  Empties the argument list.
 191 void GCTaskQueue::enqueue(GCTaskQueue* list) {
 192   if (TraceGCTaskQueue) {
 193     tty->print_cr("[" INTPTR_FORMAT "]"
 194                   " GCTaskQueue::enqueue(list: "
 195                   INTPTR_FORMAT ")",
 196                   p2i(this), p2i(list));
 197     print("before:");
 198     list->print("list:");
 199   }
 200   if (list->is_empty()) {
 201     // Enqueueing the empty list: nothing to do.
 202     return;
 203   }
 204   uint list_length = list->length();
 205   if (is_empty()) {
 206     // Enqueueing to empty list: just acquire elements.
 207     set_insert_end(list->insert_end());
 208     set_remove_end(list->remove_end());
 209     set_length(list_length);
 210   } else {
 211     // Prepend argument list to our queue.
 212     list->remove_end()->set_older(insert_end());
 213     insert_end()->set_newer(list->remove_end());
 214     set_insert_end(list->insert_end());
 215     set_length(length() + list_length);
 216     // empty the argument list.
 217   }
 218   list->initialize();
 219   if (TraceGCTaskQueue) {
 220     print("after:");
 221     list->print("list:");
 222   }
 223   verify_length();
 224 }
 225 
 226 // Dequeue one task.
 227 GCTask* GCTaskQueue::dequeue() {
 228   if (TraceGCTaskQueue) {
 229     tty->print_cr("[" INTPTR_FORMAT "]"
 230                   " GCTaskQueue::dequeue()", p2i(this));
 231     print("before:");
 232   }
 233   assert(!is_empty(), "shouldn't dequeue from empty list");
 234   GCTask* result = remove();
 235   assert(result != NULL, "shouldn't have NULL task");
 236   if (TraceGCTaskQueue) {
 237     tty->print_cr("    return: " INTPTR_FORMAT, p2i(result));
 238     print("after:");
 239   }
 240   return result;
 241 }
 242 
 243 // Dequeue one task, preferring one with affinity.
 244 GCTask* GCTaskQueue::dequeue(uint affinity) {
 245   if (TraceGCTaskQueue) {
 246     tty->print_cr("[" INTPTR_FORMAT "]"
 247                   " GCTaskQueue::dequeue(%u)", p2i(this), affinity);
 248     print("before:");
 249   }
 250   assert(!is_empty(), "shouldn't dequeue from empty list");
 251   // Look down to the next barrier for a task with this affinity.
 252   GCTask* result = NULL;
 253   for (GCTask* element = remove_end();
 254        element != NULL;
 255        element = element->newer()) {
 256     if (element->is_barrier_task()) {
 257       // Don't consider barrier tasks, nor past them.
 258       result = NULL;
 259       break;
 260     }
 261     if (element->affinity() == affinity) {
 262       result = remove(element);
 263       break;
 264     }
 265   }
 266   // If we didn't find anything with affinity, just take the next task.
 267   if (result == NULL) {
 268     result = remove();
 269   }
 270   if (TraceGCTaskQueue) {
 271     tty->print_cr("    return: " INTPTR_FORMAT, p2i(result));
 272     print("after:");
 273   }
 274   return result;
 275 }
 276 
 277 GCTask* GCTaskQueue::remove() {
 278   // Dequeue from remove end.
 279   GCTask* result = remove_end();
 280   assert(result != NULL, "shouldn't have null task");
 281   assert(result->older() == NULL, "not the remove_end");
 282   set_remove_end(result->newer());
 283   if (remove_end() == NULL) {
 284     assert(insert_end() == result, "not a singleton");
 285     set_insert_end(NULL);
 286   } else {
 287     remove_end()->set_older(NULL);
 288   }
 289   result->set_newer(NULL);
 290   decrement_length();
 291   assert(result->newer() == NULL, "shouldn't be on queue");
 292   assert(result->older() == NULL, "shouldn't be on queue");
 293   verify_length();
 294   return result;
 295 }
 296 
 297 GCTask* GCTaskQueue::remove(GCTask* task) {
 298   // This is slightly more work, and has slightly fewer asserts
 299   // than removing from the remove end.
 300   assert(task != NULL, "shouldn't have null task");
 301   GCTask* result = task;
 302   if (result->newer() != NULL) {
 303     result->newer()->set_older(result->older());
 304   } else {
 305     assert(insert_end() == result, "not youngest");
 306     set_insert_end(result->older());
 307   }
 308   if (result->older() != NULL) {
 309     result->older()->set_newer(result->newer());
 310   } else {
 311     assert(remove_end() == result, "not oldest");
 312     set_remove_end(result->newer());
 313   }
 314   result->set_newer(NULL);
 315   result->set_older(NULL);
 316   decrement_length();
 317   verify_length();
 318   return result;
 319 }
 320 
 321 NOT_PRODUCT(
 322 // Count the elements in the queue and verify the length against
 323 // that count.
 324 void GCTaskQueue::verify_length() const {
 325   uint count = 0;
 326   for (GCTask* element = insert_end();
 327        element != NULL;
 328        element = element->older()) {
 329 
 330     count++;
 331   }
 332   assert(count == length(), "Length does not match queue");
 333 }
 334 
 335 void GCTaskQueue::print(const char* message) const {
 336   tty->print_cr("[" INTPTR_FORMAT "] GCTaskQueue:"
 337                 "  insert_end: " INTPTR_FORMAT
 338                 "  remove_end: " INTPTR_FORMAT
 339                 "  length:       %d"
 340                 "  %s",
 341                 p2i(this), p2i(insert_end()), p2i(remove_end()), length(), message);
 342   uint count = 0;
 343   for (GCTask* element = insert_end();
 344        element != NULL;
 345        element = element->older()) {
 346     element->print("    ");
 347     count++;
 348     tty->cr();
 349   }
 350   tty->print("Total tasks: %d", count);
 351 }
 352 )
 353 
 354 //
 355 // SynchronizedGCTaskQueue
 356 //
 357 
 358 SynchronizedGCTaskQueue::SynchronizedGCTaskQueue(GCTaskQueue* queue_arg,
 359                                                  Monitor *       lock_arg) :
 360   _unsynchronized_queue(queue_arg),
 361   _lock(lock_arg) {
 362   assert(unsynchronized_queue() != NULL, "null queue");
 363   assert(lock() != NULL, "null lock");
 364 }
 365 
 366 SynchronizedGCTaskQueue::~SynchronizedGCTaskQueue() {
 367   // Nothing to do.
 368 }
 369 
 370 //
 371 // GCTaskManager
 372 //
 373 GCTaskManager::GCTaskManager(uint workers) :
 374   _workers(workers),
 375   _active_workers(0),
 376   _idle_workers(0),
 377   _created_workers(0) {
 378   initialize();
 379 }
 380 
 381 GCTaskThread* GCTaskManager::install_worker(uint t) {
 382   GCTaskThread* new_worker = GCTaskThread::create(this, t, _processor_assignment[t]);
 383   set_thread(t, new_worker);
 384   return new_worker;
 385 }
 386 
 387 void GCTaskManager::add_workers(bool initializing) {
 388   os::ThreadType worker_type = os::pgc_thread;
 389   uint previous_created_workers = _created_workers;
 390 
 391   _created_workers = WorkerManager::add_workers(this,
 392                                                 _active_workers,
 393                                                 _workers,
 394                                                 _created_workers,
 395                                                 worker_type,
 396                                                 initializing);
 397   _active_workers = MIN2(_created_workers, _active_workers);
 398 
 399   WorkerManager::log_worker_creation(this, previous_created_workers, _active_workers, _created_workers, initializing);
 400 }
 401 
 402 const char* GCTaskManager::group_name() {
 403   return "ParGC Thread";
 404 }
 405 
 406 void GCTaskManager::initialize() {
 407   if (TraceGCTaskManager) {
 408     tty->print_cr("GCTaskManager::initialize: workers: %u", workers());
 409   }
 410   assert(workers() != 0, "no workers");
 411   _monitor = new Monitor(Mutex::barrier,                // rank
 412                          "GCTaskManager monitor",       // name
 413                          Mutex::_allow_vm_block_flag,   // allow_vm_block
 414                          Monitor::_safepoint_check_never);
 415   // The queue for the GCTaskManager must be a CHeapObj.
 416   GCTaskQueue* unsynchronized_queue = GCTaskQueue::create_on_c_heap();
 417   _queue = SynchronizedGCTaskQueue::create(unsynchronized_queue, lock());
 418   _noop_task = NoopGCTask::create_on_c_heap();
 419   _resource_flag = NEW_C_HEAP_ARRAY(bool, workers(), mtGC);
 420   {
 421     // Set up worker threads.
 422     //     Distribute the workers among the available processors,
 423     //     unless we were told not to, or if the os doesn't want to.
 424     _processor_assignment = NEW_C_HEAP_ARRAY(uint, workers(), mtGC);
 425     if (!BindGCTaskThreadsToCPUs ||
 426         !os::distribute_processes(workers(), _processor_assignment)) {
 427       for (uint a = 0; a < workers(); a += 1) {
 428         _processor_assignment[a] = sentinel_worker();
 429       }
 430     }
 431 
 432     _thread = NEW_C_HEAP_ARRAY(GCTaskThread*, workers(), mtGC);
 433     _active_workers = ParallelGCThreads;
 434     if (UseDynamicNumberOfGCThreads && !FLAG_IS_CMDLINE(ParallelGCThreads)) {
 435       _active_workers = 1U;
 436     }
 437 
 438     Log(gc, task, thread) log;
 439     if (log.is_trace()) {
 440       ResourceMark rm;
 441       outputStream* out = log.trace_stream();
 442       out->print("GCTaskManager::initialize: distribution:");
 443       for (uint t = 0; t < workers(); t += 1) {
 444         out->print("  %u", _processor_assignment[t]);
 445       }
 446       out->cr();
 447     }
 448   }
 449   reset_busy_workers();
 450   set_unblocked();
 451   for (uint w = 0; w < workers(); w += 1) {
 452     set_resource_flag(w, false);
 453   }
 454   reset_delivered_tasks();
 455   reset_completed_tasks();
 456   reset_barriers();
 457   reset_emptied_queue();
 458 
 459   add_workers(true);
 460 }
 461 
 462 GCTaskManager::~GCTaskManager() {
 463   assert(busy_workers() == 0, "still have busy workers");
 464   assert(queue()->is_empty(), "still have queued work");
 465   NoopGCTask::destroy(_noop_task);
 466   _noop_task = NULL;
 467   if (_thread != NULL) {
 468     for (uint i = 0; i < created_workers(); i += 1) {
 469       GCTaskThread::destroy(thread(i));
 470       set_thread(i, NULL);
 471     }
 472     FREE_C_HEAP_ARRAY(GCTaskThread*, _thread);
 473     _thread = NULL;
 474   }
 475   if (_processor_assignment != NULL) {
 476     FREE_C_HEAP_ARRAY(uint, _processor_assignment);
 477     _processor_assignment = NULL;
 478   }
 479   if (_resource_flag != NULL) {
 480     FREE_C_HEAP_ARRAY(bool, _resource_flag);
 481     _resource_flag = NULL;
 482   }
 483   if (queue() != NULL) {
 484     GCTaskQueue* unsynchronized_queue = queue()->unsynchronized_queue();
 485     GCTaskQueue::destroy(unsynchronized_queue);
 486     SynchronizedGCTaskQueue::destroy(queue());
 487     _queue = NULL;
 488   }
 489   if (monitor() != NULL) {
 490     delete monitor();
 491     _monitor = NULL;
 492   }
 493 }
 494 
 495 void GCTaskManager::set_active_gang() {
 496   _active_workers =
 497     AdaptiveSizePolicy::calc_active_workers(workers(),
 498                                  active_workers(),
 499                                  Threads::number_of_non_daemon_threads());
 500 
 501   assert(!all_workers_active() || active_workers() == ParallelGCThreads,
 502          "all_workers_active() is  incorrect: "
 503          "active %d  ParallelGCThreads %u", active_workers(),
 504          ParallelGCThreads);
 505   _active_workers = MIN2(_active_workers, _workers);
 506   // "add_workers" does not guarantee any additional workers
 507   add_workers(false);
 508   log_trace(gc, task)("GCTaskManager::set_active_gang(): "
 509                       "all_workers_active()  %d  workers %d  "
 510                       "active  %d  ParallelGCThreads %u",
 511                       all_workers_active(), workers(),  active_workers(),
 512                       ParallelGCThreads);
 513 }
 514 
 515 // Create IdleGCTasks for inactive workers.
 516 // Creates tasks in a ResourceArea and assumes
 517 // an appropriate ResourceMark.
 518 void GCTaskManager::task_idle_workers() {
 519   {
 520     int more_inactive_workers = 0;
 521     {
 522       // Stop any idle tasks from exiting their IdleGCTask's
 523       // and get the count for additional IdleGCTask's under
 524       // the GCTaskManager's monitor so that the "more_inactive_workers"
 525       // count is correct.
 526       MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
 527       _wait_helper.set_should_wait(true);
 528       // active_workers are a number being requested.  idle_workers
 529       // are the number currently idle.  If all the workers are being
 530       // requested to be active but some are already idle, reduce
 531       // the number of active_workers to be consistent with the
 532       // number of idle_workers.  The idle_workers are stuck in
 533       // idle tasks and will no longer be release (since a new GC
 534       // is starting).  Try later to release enough idle_workers
 535       // to allow the desired number of active_workers.
 536       more_inactive_workers =
 537         created_workers() - active_workers() - idle_workers();
 538       if (more_inactive_workers < 0) {
 539         int reduced_active_workers = active_workers() + more_inactive_workers;
 540         set_active_workers(reduced_active_workers);
 541         more_inactive_workers = 0;
 542       }
 543       log_trace(gc, task)("JT: %d  workers %d  active  %d  idle %d  more %d",
 544                           Threads::number_of_non_daemon_threads(),
 545                           created_workers(),
 546                           active_workers(),
 547                           idle_workers(),
 548                           more_inactive_workers);
 549     }
 550     GCTaskQueue* q = GCTaskQueue::create();
 551     for(uint i = 0; i < (uint) more_inactive_workers; i++) {
 552       q->enqueue(IdleGCTask::create_on_c_heap());
 553       increment_idle_workers();
 554     }
 555     assert(created_workers() == active_workers() + idle_workers(),
 556       "total workers should equal active + inactive");
 557     add_list(q);
 558     // GCTaskQueue* q was created in a ResourceArea so a
 559     // destroy() call is not needed.
 560   }
 561 }
 562 
 563 void  GCTaskManager::release_idle_workers() {
 564   {
 565     MutexLockerEx ml(monitor(),
 566       Mutex::_no_safepoint_check_flag);
 567     _wait_helper.set_should_wait(false);
 568     monitor()->notify_all();
 569   // Release monitor
 570   }
 571 }
 572 
 573 void GCTaskManager::print_task_time_stamps() {
 574   if (!log_is_enabled(Debug, gc, task, time)) {
 575     return;
 576   }
 577   uint num_thr = created_workers();
 578   for(uint i=0; i < num_thr; i++) {
 579     GCTaskThread* t = thread(i);
 580     t->print_task_time_stamps();
 581   }
 582 }
 583 
 584 void GCTaskManager::print_threads_on(outputStream* st) {
 585   uint num_thr = created_workers();
 586   for (uint i = 0; i < num_thr; i++) {
 587     thread(i)->print_on(st);
 588     st->cr();
 589   }
 590 }
 591 
 592 void GCTaskManager::threads_do(ThreadClosure* tc) {
 593   assert(tc != NULL, "Null ThreadClosure");
 594   uint num_thr = created_workers();
 595   for (uint i = 0; i < num_thr; i++) {
 596     tc->do_thread(thread(i));
 597   }
 598 }
 599 
 600 GCTaskThread* GCTaskManager::thread(uint which) {
 601   assert(which < created_workers(), "index out of bounds");
 602   assert(_thread[which] != NULL, "shouldn't have null thread");
 603   return _thread[which];
 604 }
 605 
 606 void GCTaskManager::set_thread(uint which, GCTaskThread* value) {
 607   // "_created_workers" may not have been updated yet so use workers()
 608   assert(which < workers(), "index out of bounds");
 609   assert(value != NULL, "shouldn't have null thread");
 610   _thread[which] = value;
 611 }
 612 
 613 void GCTaskManager::add_task(GCTask* task) {
 614   assert(task != NULL, "shouldn't have null task");
 615   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
 616   if (TraceGCTaskManager) {
 617     tty->print_cr("GCTaskManager::add_task(" INTPTR_FORMAT " [%s])",
 618                   p2i(task), GCTask::Kind::to_string(task->kind()));
 619   }
 620   queue()->enqueue(task);
 621   // Notify with the lock held to avoid missed notifies.
 622   if (TraceGCTaskManager) {
 623     tty->print_cr("    GCTaskManager::add_task (%s)->notify_all",
 624                   monitor()->name());
 625   }
 626   (void) monitor()->notify_all();
 627   // Release monitor().
 628 }
 629 
 630 void GCTaskManager::add_list(GCTaskQueue* list) {
 631   assert(list != NULL, "shouldn't have null task");
 632   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
 633   if (TraceGCTaskManager) {
 634     tty->print_cr("GCTaskManager::add_list(%u)", list->length());
 635   }
 636   queue()->enqueue(list);
 637   // Notify with the lock held to avoid missed notifies.
 638   if (TraceGCTaskManager) {
 639     tty->print_cr("    GCTaskManager::add_list (%s)->notify_all",
 640                   monitor()->name());
 641   }
 642   (void) monitor()->notify_all();
 643   // Release monitor().
 644 }
 645 
 646 // GC workers wait in get_task() for new work to be added
 647 // to the GCTaskManager's queue.  When new work is added,
 648 // a notify is sent to the waiting GC workers which then
 649 // compete to get tasks.  If a GC worker wakes up and there
 650 // is no work on the queue, it is given a noop_task to execute
 651 // and then loops to find more work.
 652 
 653 GCTask* GCTaskManager::get_task(uint which) {
 654   GCTask* result = NULL;
 655   // Grab the queue lock.
 656   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
 657   // Wait while the queue is block or
 658   // there is nothing to do, except maybe release resources.
 659   while (is_blocked() ||
 660          (queue()->is_empty() && !should_release_resources(which))) {
 661     if (TraceGCTaskManager) {
 662       tty->print_cr("GCTaskManager::get_task(%u)"
 663                     "  blocked: %s"
 664                     "  empty: %s"
 665                     "  release: %s",
 666                     which,
 667                     is_blocked() ? "true" : "false",
 668                     queue()->is_empty() ? "true" : "false",
 669                     should_release_resources(which) ? "true" : "false");
 670       tty->print_cr("    => (%s)->wait()",
 671                     monitor()->name());
 672     }
 673     monitor()->wait(Mutex::_no_safepoint_check_flag, 0);
 674   }
 675   // We've reacquired the queue lock here.
 676   // Figure out which condition caused us to exit the loop above.
 677   if (!queue()->is_empty()) {
 678     if (UseGCTaskAffinity) {
 679       result = queue()->dequeue(which);
 680     } else {
 681       result = queue()->dequeue();
 682     }
 683     if (result->is_barrier_task()) {
 684       assert(which != sentinel_worker(),
 685              "blocker shouldn't be bogus");
 686       set_blocking_worker(which);
 687     }
 688   } else {
 689     // The queue is empty, but we were woken up.
 690     // Just hand back a Noop task,
 691     // in case someone wanted us to release resources, or whatever.
 692     result = noop_task();
 693   }
 694   assert(result != NULL, "shouldn't have null task");
 695   if (TraceGCTaskManager) {
 696     tty->print_cr("GCTaskManager::get_task(%u) => " INTPTR_FORMAT " [%s]",
 697                   which, p2i(result), GCTask::Kind::to_string(result->kind()));
 698     tty->print_cr("     %s", result->name());
 699   }
 700   if (!result->is_idle_task()) {
 701     increment_busy_workers();
 702     increment_delivered_tasks();
 703   }
 704   return result;
 705   // Release monitor().
 706 }
 707 
 708 void GCTaskManager::note_completion(uint which) {
 709   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
 710   if (TraceGCTaskManager) {
 711     tty->print_cr("GCTaskManager::note_completion(%u)", which);
 712   }
 713   // If we are blocked, check if the completing thread is the blocker.
 714   if (blocking_worker() == which) {
 715     assert(blocking_worker() != sentinel_worker(),
 716            "blocker shouldn't be bogus");
 717     increment_barriers();
 718     set_unblocked();
 719   }
 720   increment_completed_tasks();
 721   uint active = decrement_busy_workers();
 722   if ((active == 0) && (queue()->is_empty())) {
 723     increment_emptied_queue();
 724     if (TraceGCTaskManager) {
 725       tty->print_cr("    GCTaskManager::note_completion(%u) done", which);
 726     }
 727   }
 728   if (TraceGCTaskManager) {
 729     tty->print_cr("    GCTaskManager::note_completion(%u) (%s)->notify_all",
 730                   which, monitor()->name());
 731     tty->print_cr("  "
 732                   "  blocked: %s"
 733                   "  empty: %s"
 734                   "  release: %s",
 735                   is_blocked() ? "true" : "false",
 736                   queue()->is_empty() ? "true" : "false",
 737                   should_release_resources(which) ? "true" : "false");
 738     tty->print_cr("  "
 739                   "  delivered: %u"
 740                   "  completed: %u"
 741                   "  barriers: %u"
 742                   "  emptied: %u",
 743                   delivered_tasks(),
 744                   completed_tasks(),
 745                   barriers(),
 746                   emptied_queue());
 747   }
 748   // Tell everyone that a task has completed.
 749   (void) monitor()->notify_all();
 750   // Release monitor().
 751 }
 752 
 753 uint GCTaskManager::increment_busy_workers() {
 754   assert(queue()->own_lock(), "don't own the lock");
 755   _busy_workers += 1;
 756   return _busy_workers;
 757 }
 758 
 759 uint GCTaskManager::decrement_busy_workers() {
 760   assert(queue()->own_lock(), "don't own the lock");
 761   assert(_busy_workers > 0, "About to make a mistake");
 762   _busy_workers -= 1;
 763   return _busy_workers;
 764 }
 765 
 766 void GCTaskManager::release_all_resources() {
 767   // If you want this to be done atomically, do it in a WaitForBarrierGCTask.
 768   for (uint i = 0; i < created_workers(); i += 1) {
 769     set_resource_flag(i, true);
 770   }
 771 }
 772 
 773 bool GCTaskManager::should_release_resources(uint which) {
 774   // This can be done without a lock because each thread reads one element.
 775   return resource_flag(which);
 776 }
 777 
 778 void GCTaskManager::note_release(uint which) {
 779   // This can be done without a lock because each thread writes one element.
 780   set_resource_flag(which, false);
 781 }
 782 
 783 // "list" contains tasks that are ready to execute.  Those
 784 // tasks are added to the GCTaskManager's queue of tasks and
 785 // then the GC workers are notified that there is new work to
 786 // do.
 787 //
 788 // Typically different types of tasks can be added to the "list".
 789 // For example in PSScavenge OldToYoungRootsTask, SerialOldToYoungRootsTask,
 790 // ScavengeRootsTask, and StealTask tasks are all added to the list
 791 // and then the GC workers are notified of new work.  The tasks are
 792 // handed out in the order in which they are added to the list
 793 // (although execution is not necessarily in that order).  As long
 794 // as any tasks are running the GCTaskManager will wait for execution
 795 // to complete.  GC workers that execute a stealing task remain in
 796 // the stealing task until all stealing tasks have completed.  The load
 797 // balancing afforded by the stealing tasks work best if the stealing
 798 // tasks are added last to the list.
 799 
 800 void GCTaskManager::execute_and_wait(GCTaskQueue* list) {
 801   WaitForBarrierGCTask* fin = WaitForBarrierGCTask::create();
 802   list->enqueue(fin);
 803   // The barrier task will be read by one of the GC
 804   // workers once it is added to the list of tasks.
 805   // Be sure that is globally visible before the
 806   // GC worker reads it (which is after the task is added
 807   // to the list of tasks below).
 808   OrderAccess::storestore();
 809   add_list(list);
 810   fin->wait_for(true /* reset */);
 811   // We have to release the barrier tasks!
 812   WaitForBarrierGCTask::destroy(fin);
 813 }
 814 
 815 bool GCTaskManager::resource_flag(uint which) {
 816   assert(which < workers(), "index out of bounds");
 817   return _resource_flag[which];
 818 }
 819 
 820 void GCTaskManager::set_resource_flag(uint which, bool value) {
 821   assert(which < workers(), "index out of bounds");
 822   _resource_flag[which] = value;
 823 }
 824 
 825 //
 826 // NoopGCTask
 827 //
 828 
 829 NoopGCTask* NoopGCTask::create_on_c_heap() {
 830   NoopGCTask* result = new(ResourceObj::C_HEAP, mtGC) NoopGCTask();
 831   return result;
 832 }
 833 
 834 void NoopGCTask::destroy(NoopGCTask* that) {
 835   if (that != NULL) {
 836     that->destruct();
 837     FreeHeap(that);
 838   }
 839 }
 840 
 841 // This task should never be performing GC work that require
 842 // a valid GC id.
 843 NoopGCTask::NoopGCTask() : GCTask(GCTask::Kind::noop_task, GCId::undefined()) { }
 844 
 845 void NoopGCTask::destruct() {
 846   // This has to know it's superclass structure, just like the constructor.
 847   this->GCTask::destruct();
 848   // Nothing else to do.
 849 }
 850 
 851 //
 852 // IdleGCTask
 853 //
 854 
 855 IdleGCTask* IdleGCTask::create() {
 856   IdleGCTask* result = new IdleGCTask(false);
 857   assert(UseDynamicNumberOfGCThreads,
 858     "Should only be used with dynamic GC thread");
 859   return result;
 860 }
 861 
 862 IdleGCTask* IdleGCTask::create_on_c_heap() {
 863   IdleGCTask* result = new(ResourceObj::C_HEAP, mtGC) IdleGCTask(true);
 864   assert(UseDynamicNumberOfGCThreads,
 865     "Should only be used with dynamic GC thread");
 866   return result;
 867 }
 868 
 869 void IdleGCTask::do_it(GCTaskManager* manager, uint which) {
 870   WaitHelper* wait_helper = manager->wait_helper();
 871   log_trace(gc, task)("[" INTPTR_FORMAT "] IdleGCTask:::do_it() should_wait: %s",
 872       p2i(this), wait_helper->should_wait() ? "true" : "false");
 873 
 874   MutexLockerEx ml(manager->monitor(), Mutex::_no_safepoint_check_flag);
 875   log_trace(gc, task)("--- idle %d", which);
 876   // Increment has to be done when the idle tasks are created.
 877   // manager->increment_idle_workers();
 878   manager->monitor()->notify_all();
 879   while (wait_helper->should_wait()) {
 880     log_trace(gc, task)("[" INTPTR_FORMAT "] IdleGCTask::do_it()  [" INTPTR_FORMAT "] (%s)->wait()",
 881       p2i(this), p2i(manager->monitor()), manager->monitor()->name());
 882     manager->monitor()->wait(Mutex::_no_safepoint_check_flag, 0);
 883   }
 884   manager->decrement_idle_workers();
 885 
 886   log_trace(gc, task)("--- release %d", which);
 887   log_trace(gc, task)("[" INTPTR_FORMAT "] IdleGCTask::do_it() returns should_wait: %s",
 888     p2i(this), wait_helper->should_wait() ? "true" : "false");
 889   // Release monitor().
 890 }
 891 
 892 void IdleGCTask::destroy(IdleGCTask* that) {
 893   if (that != NULL) {
 894     that->destruct();
 895     if (that->is_c_heap_obj()) {
 896       FreeHeap(that);
 897     }
 898   }
 899 }
 900 
 901 void IdleGCTask::destruct() {
 902   // This has to know it's superclass structure, just like the constructor.
 903   this->GCTask::destruct();
 904   // Nothing else to do.
 905 }
 906 
 907 //
 908 // WaitForBarrierGCTask
 909 //
 910 WaitForBarrierGCTask* WaitForBarrierGCTask::create() {
 911   WaitForBarrierGCTask* result = new WaitForBarrierGCTask();
 912   return result;
 913 }
 914 
 915 WaitForBarrierGCTask::WaitForBarrierGCTask() : GCTask(GCTask::Kind::wait_for_barrier_task) { }
 916 
 917 void WaitForBarrierGCTask::destroy(WaitForBarrierGCTask* that) {
 918   if (that != NULL) {
 919     if (TraceGCTaskManager) {
 920       tty->print_cr("[" INTPTR_FORMAT "] WaitForBarrierGCTask::destroy()", p2i(that));
 921     }
 922     that->destruct();
 923   }
 924 }
 925 
 926 void WaitForBarrierGCTask::destruct() {
 927   if (TraceGCTaskManager) {
 928     tty->print_cr("[" INTPTR_FORMAT "] WaitForBarrierGCTask::destruct()", p2i(this));
 929   }
 930   this->GCTask::destruct();
 931   // Clean up that should be in the destructor,
 932   // except that ResourceMarks don't call destructors.
 933   _wait_helper.release_monitor();
 934 }
 935 
 936 void WaitForBarrierGCTask::do_it_internal(GCTaskManager* manager, uint which) {
 937   // Wait for this to be the only busy worker.
 938   assert(manager->monitor()->owned_by_self(), "don't own the lock");
 939   assert(manager->is_blocked(), "manager isn't blocked");
 940   while (manager->busy_workers() > 1) {
 941     if (TraceGCTaskManager) {
 942       tty->print_cr("WaitForBarrierGCTask::do_it(%u) waiting on %u workers",
 943                     which, manager->busy_workers());
 944     }
 945     manager->monitor()->wait(Mutex::_no_safepoint_check_flag, 0);
 946   }
 947 }
 948 
 949 void WaitForBarrierGCTask::do_it(GCTaskManager* manager, uint which) {
 950   if (TraceGCTaskManager) {
 951     tty->print_cr("[" INTPTR_FORMAT "]"
 952                   " WaitForBarrierGCTask::do_it() waiting for idle",
 953                   p2i(this));
 954   }
 955   {
 956     // First, wait for the barrier to arrive.
 957     MutexLockerEx ml(manager->lock(), Mutex::_no_safepoint_check_flag);
 958     do_it_internal(manager, which);
 959     // Release manager->lock().
 960   }
 961   // Then notify the waiter.
 962   _wait_helper.notify();
 963 }
 964 
 965 WaitHelper::WaitHelper() : _should_wait(true), _monitor(MonitorSupply::reserve()) {
 966   if (TraceGCTaskManager) {
 967     tty->print_cr("[" INTPTR_FORMAT "]"
 968                   " WaitHelper::WaitHelper()"
 969                   "  monitor: " INTPTR_FORMAT,
 970                   p2i(this), p2i(monitor()));
 971   }
 972 }
 973 
 974 void WaitHelper::release_monitor() {
 975   assert(_monitor != NULL, "");
 976   MonitorSupply::release(_monitor);
 977   _monitor = NULL;
 978 }
 979 
 980 WaitHelper::~WaitHelper() {
 981   release_monitor();
 982 }
 983 
 984 void WaitHelper::wait_for(bool reset) {
 985   if (TraceGCTaskManager) {
 986     tty->print_cr("[" INTPTR_FORMAT "]"
 987                   " WaitForBarrierGCTask::wait_for()"
 988       "  should_wait: %s",
 989       p2i(this), should_wait() ? "true" : "false");
 990   }
 991   {
 992     // Grab the lock and check again.
 993     MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
 994     while (should_wait()) {
 995       if (TraceGCTaskManager) {
 996         tty->print_cr("[" INTPTR_FORMAT "]"
 997                       " WaitForBarrierGCTask::wait_for()"
 998           "  [" INTPTR_FORMAT "] (%s)->wait()",
 999           p2i(this), p2i(monitor()), monitor()->name());
1000       }
1001       monitor()->wait(Mutex::_no_safepoint_check_flag, 0);
1002     }
1003     // Reset the flag in case someone reuses this task.
1004     if (reset) {
1005       set_should_wait(true);
1006     }
1007     if (TraceGCTaskManager) {
1008       tty->print_cr("[" INTPTR_FORMAT "]"
1009                     " WaitForBarrierGCTask::wait_for() returns"
1010         "  should_wait: %s",
1011         p2i(this), should_wait() ? "true" : "false");
1012     }
1013     // Release monitor().
1014   }
1015 }
1016 
1017 void WaitHelper::notify() {
1018   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);
1019   set_should_wait(false);
1020   // Waiter doesn't miss the notify in the wait_for method
1021   // since it checks the flag after grabbing the monitor.
1022   if (TraceGCTaskManager) {
1023     tty->print_cr("[" INTPTR_FORMAT "]"
1024                   " WaitForBarrierGCTask::do_it()"
1025                   "  [" INTPTR_FORMAT "] (%s)->notify_all()",
1026                   p2i(this), p2i(monitor()), monitor()->name());
1027   }
1028   monitor()->notify_all();
1029 }
1030 
1031 Mutex*                   MonitorSupply::_lock     = NULL;
1032 GrowableArray<Monitor*>* MonitorSupply::_freelist = NULL;
1033 
1034 Monitor* MonitorSupply::reserve() {
1035   Monitor* result = NULL;
1036   // Lazy initialization: possible race.
1037   if (lock() == NULL) {
1038     _lock = new Mutex(Mutex::barrier,                  // rank
1039                       "MonitorSupply mutex",           // name
1040                       Mutex::_allow_vm_block_flag);    // allow_vm_block
1041   }
1042   {
1043     MutexLockerEx ml(lock());
1044     // Lazy initialization.
1045     if (freelist() == NULL) {
1046       _freelist =
1047         new(ResourceObj::C_HEAP, mtGC) GrowableArray<Monitor*>(ParallelGCThreads,
1048                                                          true);
1049     }
1050     if (! freelist()->is_empty()) {
1051       result = freelist()->pop();
1052     } else {
1053       result = new Monitor(Mutex::barrier,                  // rank
1054                            "MonitorSupply monitor",         // name
1055                            Mutex::_allow_vm_block_flag,     // allow_vm_block
1056                            Monitor::_safepoint_check_never);
1057     }
1058     guarantee(result != NULL, "shouldn't return NULL");
1059     assert(!result->is_locked(), "shouldn't be locked");
1060     // release lock().
1061   }
1062   return result;
1063 }
1064 
1065 void MonitorSupply::release(Monitor* instance) {
1066   assert(instance != NULL, "shouldn't release NULL");
1067   assert(!instance->is_locked(), "shouldn't be locked");
1068   {
1069     MutexLockerEx ml(lock());
1070     freelist()->push(instance);
1071     // release lock().
1072   }
1073 }