taskqueue.cpp revision 9056:dc9930a04ab0 
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
35uint ParallelTaskTerminator::_total_yields = 0;
36uint ParallelTaskTerminator::_total_spins = 0;
37uint ParallelTaskTerminator::_total_peeks = 0;
38#endif
39
40#if TASKQUEUE_STATS
41const char * const TaskQueueStats::_names[last_stat_id] = {
42  "qpush", "qpop", "qpop-s", "qattempt", "qsteal", "opush", "omax"
43};
44
45TaskQueueStats & 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
53void 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
79void 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.
92void 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
113int 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
131ParallelTaskTerminator::
132ParallelTaskTerminator(uint n_threads, TaskQueueSetSuper* queue_set) :
133  _n_threads(n_threads),
134  _queue_set(queue_set),
135  _offered_termination(0) {}
136
137bool ParallelTaskTerminator::peek_in_queue_set() {
138  return _queue_set->peek();
139}
140
141void ParallelTaskTerminator::yield() {
142  assert(_offered_termination <= _n_threads, "Invariant");
143  os::naked_yield();
144}
145
146void ParallelTaskTerminator::sleep(uint millis) {
147  assert(_offered_termination <= _n_threads, "Invariant");
148  os::sleep(Thread::current(), millis, false);
149}
150
151bool
152ParallelTaskTerminator::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
242void 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
251void 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
260bool ObjArrayTask::is_valid() const {
261  return _obj != NULL && _obj->is_objArray() && _index >= 0 &&
262      _index < objArrayOop(_obj)->length();
263}
264#endif // ASSERT
265
266void ParallelTaskTerminator::reset_for_reuse(uint n_threads) {
267  reset_for_reuse();
268  _n_threads = n_threads;
269}
270