1 /*
   2  * Copyright (c) 2016, 2019, Red Hat, Inc. All rights reserved.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.
   7  *
   8  * This code is distributed in the hope that it will be useful, but WITHOUT
   9  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  10  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  11  * version 2 for more details (a copy is included in the LICENSE file that
  12  * accompanied this code).
  13  *
  14  * You should have received a copy of the GNU General Public License version
  15  * 2 along with this work; if not, write to the Free Software Foundation,
  16  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  17  *
  18  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  19  * or visit www.oracle.com if you need additional information or have any
  20  * questions.
  21  *
  22  */
  23 
  24 #include "precompiled.hpp"
  25 
  26 #include "gc_implementation/shenandoah/shenandoahHeap.inline.hpp"
  27 #include "gc_implementation/shenandoah/shenandoahLogging.hpp"
  28 #include "gc_implementation/shenandoah/shenandoahTaskqueue.inline.hpp"
  29 
  30 void ShenandoahObjToScanQueueSet::clear() {
  31   uint size = GenericTaskQueueSet<ShenandoahObjToScanQueue, mtGC>::size();
  32   for (uint index = 0; index < size; index ++) {
  33     ShenandoahObjToScanQueue* q = queue(index);
  34     assert(q != NULL, "Sanity");
  35     q->clear();
  36   }
  37 }
  38 
  39 bool ShenandoahObjToScanQueueSet::is_empty() {
  40   uint size = GenericTaskQueueSet<ShenandoahObjToScanQueue, mtGC>::size();
  41   for (uint index = 0; index < size; index ++) {
  42     ShenandoahObjToScanQueue* q = queue(index);
  43     assert(q != NULL, "Sanity");
  44     if (!q->is_empty()) {
  45       return false;
  46     }
  47   }
  48   return true;
  49 }
  50 
  51 bool ShenandoahTaskTerminator::offer_termination(ShenandoahTerminatorTerminator* terminator) {
  52   assert(_n_threads > 0, "Initialization is incorrect");
  53   assert(_offered_termination < _n_threads, "Invariant");
  54   assert(_blocker != NULL, "Invariant");
  55 
  56   // single worker, done
  57   if (_n_threads == 1) {
  58     return true;
  59   }
  60 
  61   _blocker->lock_without_safepoint_check();
  62   // all arrived, done
  63   if (++ _offered_termination == _n_threads) {
  64     _blocker->notify_all();
  65     _blocker->unlock();
  66     return true;
  67   }
  68 
  69   Thread* the_thread = Thread::current();
  70   while (true) {
  71     if (_spin_master == NULL) {
  72       _spin_master = the_thread;
  73 
  74       _blocker->unlock();
  75 
  76       if (do_spin_master_work(terminator)) {
  77         assert(_offered_termination == _n_threads, "termination condition");
  78         return true;
  79       } else {
  80         _blocker->lock_without_safepoint_check();
  81       }
  82     } else {
  83       _blocker->wait(true, WorkStealingSleepMillis);
  84 
  85       if (_offered_termination == _n_threads) {
  86         _blocker->unlock();
  87         return true;
  88       }
  89     }
  90 
  91     if (peek_in_queue_set() || (terminator != NULL && terminator->should_exit_termination())) {
  92       _offered_termination --;
  93       _blocker->unlock();
  94       return false;
  95     }
  96   }
  97 }
  98 
  99 #if TASKQUEUE_STATS
 100 void ShenandoahObjToScanQueueSet::print_taskqueue_stats_hdr(outputStream* const st) {
 101   st->print_raw_cr("GC Task Stats");
 102   st->print_raw("thr "); TaskQueueStats::print_header(1, st); st->cr();
 103   st->print_raw("--- "); TaskQueueStats::print_header(2, st); st->cr();
 104 }
 105 
 106 void ShenandoahObjToScanQueueSet::print_taskqueue_stats() {
 107   if (! ShenandoahLogTrace) {
 108     return;
 109   }
 110   ResourceMark rm;
 111   outputStream* st = gclog_or_tty;
 112   print_taskqueue_stats_hdr(st);
 113 
 114   TaskQueueStats totals;
 115   const uint n = size();
 116   for (uint i = 0; i < n; ++i) {
 117     st->print(UINT32_FORMAT_W(3), i);
 118     queue(i)->stats.print(st);
 119     st->cr();
 120     totals += queue(i)->stats;
 121   }
 122   st->print("tot "); totals.print(st); st->cr();
 123   DEBUG_ONLY(totals.verify());
 124 }
 125 
 126 void ShenandoahObjToScanQueueSet::reset_taskqueue_stats() {
 127   const uint n = size();
 128   for (uint i = 0; i < n; ++i) {
 129     queue(i)->stats.reset();
 130   }
 131 }
 132 #endif // TASKQUEUE_STATS
 133 
 134 bool ShenandoahTaskTerminator::do_spin_master_work(ShenandoahTerminatorTerminator* terminator) {
 135   uint yield_count = 0;
 136   // Number of hard spin loops done since last yield
 137   uint hard_spin_count = 0;
 138   // Number of iterations in the hard spin loop.
 139   uint hard_spin_limit = WorkStealingHardSpins;
 140 
 141   // If WorkStealingSpinToYieldRatio is 0, no hard spinning is done.
 142   // If it is greater than 0, then start with a small number
 143   // of spins and increase number with each turn at spinning until
 144   // the count of hard spins exceeds WorkStealingSpinToYieldRatio.
 145   // Then do a yield() call and start spinning afresh.
 146   if (WorkStealingSpinToYieldRatio > 0) {
 147     hard_spin_limit = WorkStealingHardSpins >> WorkStealingSpinToYieldRatio;
 148     hard_spin_limit = MAX2(hard_spin_limit, 1U);
 149   }
 150   // Remember the initial spin limit.
 151   uint hard_spin_start = hard_spin_limit;
 152 
 153   // Loop waiting for all threads to offer termination or
 154   // more work.
 155   while (true) {
 156     // Look for more work.
 157     // Periodically sleep() instead of yield() to give threads
 158     // waiting on the cores the chance to grab this code
 159     if (yield_count <= WorkStealingYieldsBeforeSleep) {
 160       // Do a yield or hardspin.  For purposes of deciding whether
 161       // to sleep, count this as a yield.
 162       yield_count++;
 163 
 164       // Periodically call yield() instead spinning
 165       // After WorkStealingSpinToYieldRatio spins, do a yield() call
 166       // and reset the counts and starting limit.
 167       if (hard_spin_count > WorkStealingSpinToYieldRatio) {
 168         yield();
 169         hard_spin_count = 0;
 170         hard_spin_limit = hard_spin_start;
 171 #ifdef TRACESPINNING
 172         _total_yields++;
 173 #endif
 174       } else {
 175         // Hard spin this time
 176         // Increase the hard spinning period but only up to a limit.
 177         hard_spin_limit = MIN2(2*hard_spin_limit,
 178                                (uint) WorkStealingHardSpins);
 179         for (uint j = 0; j < hard_spin_limit; j++) {
 180           SpinPause();
 181         }
 182         hard_spin_count++;
 183 #ifdef TRACESPINNING
 184         _total_spins++;
 185 #endif
 186       }
 187     } else {
 188       log_develop_trace(gc, task)("ShenanddoahTaskTerminator::do_spin_master_work() thread " PTR_FORMAT " sleeps after %u yields",
 189                                   p2i(Thread::current()), yield_count);
 190       yield_count = 0;
 191 
 192       MonitorLockerEx locker(_blocker, Mutex::_no_safepoint_check_flag);   // no safepoint check
 193       _spin_master = NULL;
 194       locker.wait(Mutex::_no_safepoint_check_flag, WorkStealingSleepMillis);
 195       if (_spin_master == NULL) {
 196         _spin_master = Thread::current();
 197       } else {
 198         return false;
 199       }
 200     }
 201 
 202 #ifdef TRACESPINNING
 203       _total_peeks++;
 204 #endif
 205     size_t tasks = tasks_in_queue_set();
 206     if (tasks > 0 || (terminator != NULL && terminator->should_exit_termination())) {
 207       MonitorLockerEx locker(_blocker, Mutex::_no_safepoint_check_flag);   // no safepoint check
 208 
 209       if ((int) tasks >= _offered_termination - 1) {
 210         locker.notify_all();
 211       } else {
 212         for (; tasks > 1; tasks --) {
 213           locker.notify();
 214         }
 215       }
 216       _spin_master = NULL;
 217       return false;
 218     } else if (_offered_termination == _n_threads) {
 219       return true;
 220     }
 221   }
 222 }
 223 
 224 bool ShenandoahTerminatorTerminator::should_exit_termination() {
 225   return _heap->cancelled_gc();
 226 }
 227