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