1 /*

     2  * Copyright (c) 2015, 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 #ifndef SHARE_VM_GC_SHARED_TASKQUEUE_INLINE_HPP

    26 #define SHARE_VM_GC_SHARED_TASKQUEUE_INLINE_HPP

    27 

    28 #include "gc/shared/taskqueue.hpp"

    29 #include "memory/allocation.inline.hpp"

    30 #include "oops/oop.inline.hpp"

    31 #include "runtime/atomic.hpp"

    32 #include "runtime/orderAccess.inline.hpp"

    33 #include "utilities/debug.hpp"

    34 #include "utilities/stack.inline.hpp"

    35 

    36 template <class T, MEMFLAGS F>

    37 inline GenericTaskQueueSet<T, F>::GenericTaskQueueSet(int n) : _n(n) {

    38   typedef T* GenericTaskQueuePtr;

    39   _queues = NEW_C_HEAP_ARRAY(GenericTaskQueuePtr, n, F);

    40   for (int i = 0; i < n; i++) {

    41     _queues[i] = NULL;

    42   }

    43 }

    44 

    45 template<class E, MEMFLAGS F, unsigned int N>

    46 inline void GenericTaskQueue<E, F, N>::initialize() {

    47   _elems = ArrayAllocator<E>::allocate(N, F);

    48 }

    49 

    50 template<class E, MEMFLAGS F, unsigned int N>

    51 inline GenericTaskQueue<E, F, N>::~GenericTaskQueue() {

    52   assert(false, "This code is currently never called");

    53   ArrayAllocator<E>::free(const_cast<E*>(_elems), N);

    54 }

    55 

    56 template<class E, MEMFLAGS F, unsigned int N>

    57 bool GenericTaskQueue<E, F, N>::push_slow(E t, uint dirty_n_elems) {

    58   if (dirty_n_elems == N - 1) {

    59     // Actually means 0, so do the push.

    60     uint localBot = _bottom;

    61     // g++ complains if the volatile result of the assignment is

    62     // unused, so we cast the volatile away.  We cannot cast directly

    63     // to void, because gcc treats that as not using the result of the

    64     // assignment.  However, casting to E& means that we trigger an

    65     // unused-value warning.  So, we cast the E& to void.

    66     (void)const_cast<E&>(_elems[localBot] = t);

    67     OrderAccess::release_store(&_bottom, increment_index(localBot));

    68     TASKQUEUE_STATS_ONLY(stats.record_push());

    69     return true;

    70   }

    71   return false;

    72 }

    73 

    74 template<class E, MEMFLAGS F, unsigned int N> inline bool

    75 GenericTaskQueue<E, F, N>::push(E t) {

    76   uint localBot = _bottom;

    77   assert(localBot < N, "_bottom out of range.");

    78   idx_t top = _age.top();

    79   uint dirty_n_elems = dirty_size(localBot, top);

    80   assert(dirty_n_elems < N, "n_elems out of range.");

    81   if (dirty_n_elems < max_elems()) {

    82     // g++ complains if the volatile result of the assignment is

    83     // unused, so we cast the volatile away.  We cannot cast directly

    84     // to void, because gcc treats that as not using the result of the

    85     // assignment.  However, casting to E& means that we trigger an

    86     // unused-value warning.  So, we cast the E& to void.

    87     (void) const_cast<E&>(_elems[localBot] = t);

    88     OrderAccess::release_store(&_bottom, increment_index(localBot));

    89     TASKQUEUE_STATS_ONLY(stats.record_push());

    90     return true;

    91   } else {

    92     return push_slow(t, dirty_n_elems);

    93   }

    94 }

    95 

    96 template <class E, MEMFLAGS F, unsigned int N>

    97 inline bool OverflowTaskQueue<E, F, N>::push(E t)

    98 {

    99   if (!taskqueue_t::push(t)) {

   100     overflow_stack()->push(t);

   101     TASKQUEUE_STATS_ONLY(stats.record_overflow(overflow_stack()->size()));

   102   }

   103   return true;

   104 }

   105 

   106 template <class E, MEMFLAGS F, unsigned int N>

   107 inline bool OverflowTaskQueue<E, F, N>::try_push_to_taskqueue(E t) {

   108   return taskqueue_t::push(t);

   109 }

   110 

   111 // pop_local_slow() is done by the owning thread and is trying to

   112 // get the last task in the queue.  It will compete with pop_global()

   113 // that will be used by other threads.  The tag age is incremented

   114 // whenever the queue goes empty which it will do here if this thread

   115 // gets the last task or in pop_global() if the queue wraps (top == 0

   116 // and pop_global() succeeds, see pop_global()).

   117 template<class E, MEMFLAGS F, unsigned int N>

   118 bool GenericTaskQueue<E, F, N>::pop_local_slow(uint localBot, Age oldAge) {

   119   // This queue was observed to contain exactly one element; either this

   120   // thread will claim it, or a competing "pop_global".  In either case,

   121   // the queue will be logically empty afterwards.  Create a new Age value

   122   // that represents the empty queue for the given value of "_bottom".  (We

   123   // must also increment "tag" because of the case where "bottom == 1",

   124   // "top == 0".  A pop_global could read the queue element in that case,

   125   // then have the owner thread do a pop followed by another push.  Without

   126   // the incrementing of "tag", the pop_global's CAS could succeed,

   127   // allowing it to believe it has claimed the stale element.)

   128   Age newAge((idx_t)localBot, oldAge.tag() + 1);

   129   // Perhaps a competing pop_global has already incremented "top", in which

   130   // case it wins the element.

   131   if (localBot == oldAge.top()) {

   132     // No competing pop_global has yet incremented "top"; we'll try to

   133     // install new_age, thus claiming the element.

   134     Age tempAge = _age.cmpxchg(newAge, oldAge);

   135     if (tempAge == oldAge) {

   136       // We win.

   137       assert(dirty_size(localBot, _age.top()) != N - 1, "sanity");

   138       TASKQUEUE_STATS_ONLY(stats.record_pop_slow());

   139       return true;

   140     }

   141   }

   142   // We lose; a completing pop_global gets the element.  But the queue is empty

   143   // and top is greater than bottom.  Fix this representation of the empty queue

   144   // to become the canonical one.

   145   _age.set(newAge);

   146   assert(dirty_size(localBot, _age.top()) != N - 1, "sanity");

   147   return false;

   148 }

   149 

   150 template<class E, MEMFLAGS F, unsigned int N> inline bool

   151 GenericTaskQueue<E, F, N>::pop_local(volatile E& t) {

   152   uint localBot = _bottom;

   153   // This value cannot be N-1.  That can only occur as a result of

   154   // the assignment to bottom in this method.  If it does, this method

   155   // resets the size to 0 before the next call (which is sequential,

   156   // since this is pop_local.)

   157   uint dirty_n_elems = dirty_size(localBot, _age.top());

   158   assert(dirty_n_elems != N - 1, "Shouldn't be possible...");

   159   if (dirty_n_elems == 0) return false;

   160   localBot = decrement_index(localBot);

   161   _bottom = localBot;

   162   // This is necessary to prevent any read below from being reordered

   163   // before the store just above.

   164   OrderAccess::fence();

   165   // g++ complains if the volatile result of the assignment is

   166   // unused, so we cast the volatile away.  We cannot cast directly

   167   // to void, because gcc treats that as not using the result of the

   168   // assignment.  However, casting to E& means that we trigger an

   169   // unused-value warning.  So, we cast the E& to void.

   170   (void) const_cast<E&>(t = _elems[localBot]);

   171   // This is a second read of "age"; the "size()" above is the first.

   172   // If there's still at least one element in the queue, based on the

   173   // "_bottom" and "age" we've read, then there can be no interference with

   174   // a "pop_global" operation, and we're done.

   175   idx_t tp = _age.top();    // XXX

   176   if (size(localBot, tp) > 0) {

   177     assert(dirty_size(localBot, tp) != N - 1, "sanity");

   178     TASKQUEUE_STATS_ONLY(stats.record_pop());

   179     return true;

   180   } else {

   181     // Otherwise, the queue contained exactly one element; we take the slow

   182     // path.

   183     return pop_local_slow(localBot, _age.get());

   184   }

   185 }

   186 

   187 template <class E, MEMFLAGS F, unsigned int N>

   188 bool OverflowTaskQueue<E, F, N>::pop_overflow(E& t)

   189 {

   190   if (overflow_empty()) return false;

   191   t = overflow_stack()->pop();

   192   return true;

   193 }

   194 

   195 template<class E, MEMFLAGS F, unsigned int N>

   196 bool GenericTaskQueue<E, F, N>::pop_global(volatile E& t) {

   197   Age oldAge = _age.get();

   198   // Architectures with weak memory model require a barrier here

   199   // to guarantee that bottom is not older than age,

   200   // which is crucial for the correctness of the algorithm.

   201 #if !(defined SPARC || defined IA32 || defined AMD64)

   202   OrderAccess::fence();

   203 #endif

   204   uint localBot = OrderAccess::load_acquire((volatile juint*)&_bottom);

   205   uint n_elems = size(localBot, oldAge.top());

   206   if (n_elems == 0) {

   207     return false;

   208   }

   209 

   210   // g++ complains if the volatile result of the assignment is

   211   // unused, so we cast the volatile away.  We cannot cast directly

   212   // to void, because gcc treats that as not using the result of the

   213   // assignment.  However, casting to E& means that we trigger an

   214   // unused-value warning.  So, we cast the E& to void.

   215   (void) const_cast<E&>(t = _elems[oldAge.top()]);

   216   Age newAge(oldAge);

   217   newAge.increment();

   218   Age resAge = _age.cmpxchg(newAge, oldAge);

   219 

   220   // Note that using "_bottom" here might fail, since a pop_local might

   221   // have decremented it.

   222   assert(dirty_size(localBot, newAge.top()) != N - 1, "sanity");

   223   return resAge == oldAge;

   224 }

   225 

   226 template<class T, MEMFLAGS F> bool

   227 GenericTaskQueueSet<T, F>::steal_best_of_2(uint queue_num, int* seed, E& t) {

   228   if (_n > 2) {

   229     uint k1 = queue_num;

   230     while (k1 == queue_num) k1 = TaskQueueSetSuper::randomParkAndMiller(seed) % _n;

   231     uint k2 = queue_num;

   232     while (k2 == queue_num || k2 == k1) k2 = TaskQueueSetSuper::randomParkAndMiller(seed) % _n;

   233     // Sample both and try the larger.

   234     uint sz1 = _queues[k1]->size();

   235     uint sz2 = _queues[k2]->size();

   236     if (sz2 > sz1) return _queues[k2]->pop_global(t);

   237     else return _queues[k1]->pop_global(t);

   238   } else if (_n == 2) {

   239     // Just try the other one.

   240     uint k = (queue_num + 1) % 2;

   241     return _queues[k]->pop_global(t);

   242   } else {

   243     assert(_n == 1, "can't be zero.");

   244     return false;

   245   }

   246 }

   247 

   248 template<class T, MEMFLAGS F> bool

   249 GenericTaskQueueSet<T, F>::steal(uint queue_num, int* seed, E& t) {

   250   for (uint i = 0; i < 2 * _n; i++) {

   251     if (steal_best_of_2(queue_num, seed, t)) {

   252       TASKQUEUE_STATS_ONLY(queue(queue_num)->stats.record_steal(true));

   253       return true;

   254     }

   255   }

   256   TASKQUEUE_STATS_ONLY(queue(queue_num)->stats.record_steal(false));

   257   return false;

   258 }

   259 

   260 template <unsigned int N, MEMFLAGS F>

   261 inline typename TaskQueueSuper<N, F>::Age TaskQueueSuper<N, F>::Age::cmpxchg(const Age new_age, const Age old_age) volatile {

   262   return (size_t) Atomic::cmpxchg_ptr((intptr_t)new_age._data,

   263                                       (volatile intptr_t *)&_data,

   264                                       (intptr_t)old_age._data);

   265 }

   266 

   267 template<class E, MEMFLAGS F, unsigned int N>

   268 template<class Fn>

   269 inline void GenericTaskQueue<E, F, N>::iterate(Fn fn) {

   270   uint iters = size();

   271   uint index = _bottom;

   272   for (uint i = 0; i < iters; ++i) {

   273     index = decrement_index(index);

   274     fn(const_cast<E&>(_elems[index])); // cast away volatility

   275   }

   276 }

   277 

   278 

   279 #endif // SHARE_VM_GC_SHARED_TASKQUEUE_INLINE_HPP