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


 217                               p2i(Thread::current()), yield_count);

 218         yield_count = 0;
 219         // A sleep will cause this processor to seek work on another processor's
 220         // runqueue, if it has nothing else to run (as opposed to the yield
 221         // which may only move the thread to the end of the this processor's
 222         // runqueue).
 223         sleep(WorkStealingSleepMillis);
 224       }
 225 
 226 #ifdef TRACESPINNING
 227       _total_peeks++;
 228 #endif
 229       if (peek_in_queue_set() ||
 230           (terminator != NULL && terminator->should_exit_termination())) {
 231         Atomic::dec((int *)&_offered_termination);
 232         assert(_offered_termination < _n_threads, "Invariant");
 233         return false;
 234       }
 235     }
 236   }
 237 }
 238 
 239 #ifdef TRACESPINNING
 240 void ParallelTaskTerminator::print_termination_counts() {
 241   log_trace(gc, task)("ParallelTaskTerminator Total yields: %u"
 242     " Total spins: %u Total peeks: %u",
 243     total_yields(),
 244     total_spins(),
 245     total_peeks());
 246 }
 247 #endif
 248 
 249 void ParallelTaskTerminator::reset_for_reuse() {
 250   if (_offered_termination != 0) {
 251     assert(_offered_termination == _n_threads,
 252            "Terminator may still be in use");
 253     _offered_termination = 0;
 254   }
 255 }
 256 
 257 #ifdef ASSERT
 258 bool ObjArrayTask::is_valid() const {
 259   return _obj != NULL && _obj->is_objArray() && _index >= 0 &&
 260       _index < objArrayOop(_obj)->length();
 261 }
 262 #endif // ASSERT
 263 
 264 void ParallelTaskTerminator::reset_for_reuse(uint n_threads) {
 265   reset_for_reuse();
 266   _n_threads = n_threads;
 267 }
--- EOF ---