1 /*

     2  * Copyright (c) 2001, 2016, 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.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_trace(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 }