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