1 /*
   2  * Copyright (c) 2001, 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/shared/taskqueue.hpp"
  27 #include "oops/oop.inline.hpp"
  28 #include "runtime/atomic.inline.hpp"
  29 #include "runtime/os.hpp"
  30 #include "runtime/thread.inline.hpp"
  31 #include "utilities/debug.hpp"
  32 #include "utilities/stack.inline.hpp"
  33 
  34 #ifdef TRACESPINNING
  35 uint ParallelTaskTerminator::_total_yields = 0;
  36 uint ParallelTaskTerminator::_total_spins = 0;
  37 uint ParallelTaskTerminator::_total_peeks = 0;
  38 #endif
  39 
  40 #if TASKQUEUE_STATS
  41 const char * const TaskQueueStats::_names[last_stat_id] = {
  42   "qpush", "qpop", "qpop-s", "qattempt", "qsteal", "opush", "omax"
  43 };
  44 
  45 TaskQueueStats & TaskQueueStats::operator +=(const TaskQueueStats & addend)
  46 {
  47   for (unsigned int i = 0; i < last_stat_id; ++i) {
  48     _stats[i] += addend._stats[i];
  49   }
  50   return *this;
  51 }
  52 
  53 void TaskQueueStats::print_header(unsigned int line, outputStream* const stream,
  54                                   unsigned int width)
  55 {
  56   // Use a width w: 1 <= w <= max_width
  57   const unsigned int max_width = 40;
  58   const unsigned int w = MAX2(MIN2(width, max_width), 1U);
  59 
  60   if (line == 0) { // spaces equal in width to the header
  61     const unsigned int hdr_width = w * last_stat_id + last_stat_id - 1;
  62     stream->print("%*s", hdr_width, " ");
  63   } else if (line == 1) { // labels
  64     stream->print("%*s", w, _names[0]);
  65     for (unsigned int i = 1; i < last_stat_id; ++i) {
  66       stream->print(" %*s", w, _names[i]);
  67     }
  68   } else if (line == 2) { // dashed lines
  69     char dashes[max_width + 1];
  70     memset(dashes, '-', w);
  71     dashes[w] = '\0';
  72     stream->print("%s", dashes);
  73     for (unsigned int i = 1; i < last_stat_id; ++i) {
  74       stream->print(" %s", dashes);
  75     }
  76   }
  77 }
  78 
  79 void TaskQueueStats::print(outputStream* stream, unsigned int width) const
  80 {
  81   #define FMT SIZE_FORMAT_W(*)
  82   stream->print(FMT, width, _stats[0]);
  83   for (unsigned int i = 1; i < last_stat_id; ++i) {
  84     stream->print(" " FMT, width, _stats[i]);
  85   }
  86   #undef FMT
  87 }
  88 
  89 #ifdef ASSERT
  90 // Invariants which should hold after a TaskQueue has been emptied and is
  91 // quiescent; they do not hold at arbitrary times.
  92 void TaskQueueStats::verify() const
  93 {
  94   assert(get(push) == get(pop) + get(steal),
  95          "push=" SIZE_FORMAT " pop=" SIZE_FORMAT " steal=" SIZE_FORMAT,
  96          get(push), get(pop), get(steal));
  97   assert(get(pop_slow) <= get(pop),
  98          "pop_slow=" SIZE_FORMAT " pop=" SIZE_FORMAT,
  99          get(pop_slow), get(pop));
 100   assert(get(steal) <= get(steal_attempt),
 101          "steal=" SIZE_FORMAT " steal_attempt=" SIZE_FORMAT,
 102          get(steal), get(steal_attempt));
 103   assert(get(overflow) == 0 || get(push) != 0,
 104          "overflow=" SIZE_FORMAT " push=" SIZE_FORMAT,
 105          get(overflow), get(push));
 106   assert(get(overflow_max_len) == 0 || get(overflow) != 0,
 107          "overflow_max_len=" SIZE_FORMAT " overflow=" SIZE_FORMAT,
 108          get(overflow_max_len), get(overflow));
 109 }
 110 #endif // ASSERT
 111 #endif // TASKQUEUE_STATS
 112 
 113 int TaskQueueSetSuper::randomParkAndMiller(int *seed0) {
 114   const int a =      16807;
 115   const int m = 2147483647;
 116   const int q =     127773;  /* m div a */
 117   const int r =       2836;  /* m mod a */
 118   assert(sizeof(int) == 4, "I think this relies on that");
 119   int seed = *seed0;
 120   int hi   = seed / q;
 121   int lo   = seed % q;
 122   int test = a * lo - r * hi;
 123   if (test > 0)
 124     seed = test;
 125   else
 126     seed = test + m;
 127   *seed0 = seed;
 128   return seed;
 129 }
 130 
 131 ParallelTaskTerminator::
 132 ParallelTaskTerminator(uint n_threads, TaskQueueSetSuper* queue_set) :
 133   _n_threads(n_threads),
 134   _queue_set(queue_set),
 135   _offered_termination(0) {}
 136 
 137 bool ParallelTaskTerminator::peek_in_queue_set() {
 138   return _queue_set->peek();
 139 }
 140 
 141 void ParallelTaskTerminator::yield() {
 142   assert(_offered_termination <= _n_threads, "Invariant");
 143   os::naked_yield();
 144 }
 145 
 146 void ParallelTaskTerminator::sleep(uint millis) {
 147   assert(_offered_termination <= _n_threads, "Invariant");
 148   os::sleep(Thread::current(), millis, false);
 149 }
 150 
 151 bool
 152 ParallelTaskTerminator::offer_termination(TerminatorTerminator* terminator) {
 153   assert(_n_threads > 0, "Initialization is incorrect");
 154   assert(_offered_termination < _n_threads, "Invariant");
 155   Atomic::inc((int *)&_offered_termination);
 156 
 157   uint yield_count = 0;
 158   // Number of hard spin loops done since last yield
 159   uint hard_spin_count = 0;
 160   // Number of iterations in the hard spin loop.
 161   uint hard_spin_limit = WorkStealingHardSpins;
 162 
 163   // If WorkStealingSpinToYieldRatio is 0, no hard spinning is done.
 164   // If it is greater than 0, then start with a small number
 165   // of spins and increase number with each turn at spinning until
 166   // the count of hard spins exceeds WorkStealingSpinToYieldRatio.
 167   // Then do a yield() call and start spinning afresh.
 168   if (WorkStealingSpinToYieldRatio > 0) {
 169     hard_spin_limit = WorkStealingHardSpins >> WorkStealingSpinToYieldRatio;
 170     hard_spin_limit = MAX2(hard_spin_limit, 1U);
 171   }
 172   // Remember the initial spin limit.
 173   uint hard_spin_start = hard_spin_limit;
 174 
 175   // Loop waiting for all threads to offer termination or
 176   // more work.
 177   while (true) {
 178     assert(_offered_termination <= _n_threads, "Invariant");
 179     // Are all threads offering termination?
 180     if (_offered_termination == _n_threads) {
 181       return true;
 182     } else {
 183       // Look for more work.
 184       // Periodically sleep() instead of yield() to give threads
 185       // waiting on the cores the chance to grab this code
 186       if (yield_count <= WorkStealingYieldsBeforeSleep) {
 187         // Do a yield or hardspin.  For purposes of deciding whether
 188         // to sleep, count this as a yield.
 189         yield_count++;
 190 
 191         // Periodically call yield() instead spinning
 192         // After WorkStealingSpinToYieldRatio spins, do a yield() call
 193         // and reset the counts and starting limit.
 194         if (hard_spin_count > WorkStealingSpinToYieldRatio) {
 195           yield();
 196           hard_spin_count = 0;
 197           hard_spin_limit = hard_spin_start;
 198 #ifdef TRACESPINNING
 199           _total_yields++;
 200 #endif
 201         } else {
 202           // Hard spin this time
 203           // Increase the hard spinning period but only up to a limit.
 204           hard_spin_limit = MIN2(2*hard_spin_limit,
 205                                  (uint) WorkStealingHardSpins);
 206           for (uint j = 0; j < hard_spin_limit; j++) {
 207             SpinPause();
 208           }
 209           hard_spin_count++;
 210 #ifdef TRACESPINNING
 211           _total_spins++;
 212 #endif
 213         }
 214       } else {
 215         if (PrintGCDetails && Verbose) {
 216          gclog_or_tty->print_cr("ParallelTaskTerminator::offer_termination() "
 217            "thread " PTR_FORMAT " sleeps after %u yields",
 218            p2i(Thread::current()), yield_count);
 219         }
 220         yield_count = 0;
 221         // A sleep will cause this processor to seek work on another processor's
 222         // runqueue, if it has nothing else to run (as opposed to the yield
 223         // which may only move the thread to the end of the this processor's
 224         // runqueue).
 225         sleep(WorkStealingSleepMillis);
 226       }
 227 
 228 #ifdef TRACESPINNING
 229       _total_peeks++;
 230 #endif
 231       if (peek_in_queue_set() ||
 232           (terminator != NULL && terminator->should_exit_termination())) {
 233         Atomic::dec((int *)&_offered_termination);
 234         assert(_offered_termination < _n_threads, "Invariant");
 235         return false;
 236       }
 237     }
 238   }
 239 }
 240 
 241 #ifdef TRACESPINNING
 242 void ParallelTaskTerminator::print_termination_counts() {
 243   gclog_or_tty->print_cr("ParallelTaskTerminator Total yields: %u"
 244     " Total spins: %u Total peeks: %u",
 245     total_yields(),
 246     total_spins(),
 247     total_peeks());
 248 }
 249 #endif
 250 
 251 void ParallelTaskTerminator::reset_for_reuse() {
 252   if (_offered_termination != 0) {
 253     assert(_offered_termination == _n_threads,
 254            "Terminator may still be in use");
 255     _offered_termination = 0;
 256   }
 257 }
 258 
 259 #ifdef ASSERT
 260 bool ObjArrayTask::is_valid() const {
 261   return _obj != NULL && _obj->is_objArray() && _index >= 0 &&
 262       _index < objArrayOop(_obj)->length();
 263 }
 264 #endif // ASSERT
 265 
 266 void ParallelTaskTerminator::reset_for_reuse(uint n_threads) {
 267   reset_for_reuse();
 268   _n_threads = n_threads;
 269 }