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