1 /*
   2  * Copyright (c) 2016, 2020, Red Hat, Inc. 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_GC_SHENANDOAH_SHENANDOAHTASKQUEUE_HPP
  26 #define SHARE_GC_SHENANDOAH_SHENANDOAHTASKQUEUE_HPP
  27 
  28 #include "gc/shared/taskTerminator.hpp"
  29 #include "gc/shared/taskqueue.hpp"
  30 #include "gc/shenandoah/shenandoahPadding.hpp"
  31 #include "memory/allocation.hpp"
  32 #include "runtime/atomic.hpp"
  33 #include "runtime/mutex.hpp"
  34 #include "runtime/thread.hpp"
  35 
  36 template<class E, MEMFLAGS F, unsigned int N = TASKQUEUE_SIZE>
  37 class BufferedOverflowTaskQueue: public OverflowTaskQueue<E, F, N>
  38 {
  39 public:
  40   typedef OverflowTaskQueue<E, F, N> taskqueue_t;
  41 
  42   BufferedOverflowTaskQueue() : _buf_empty(true) {};
  43 
  44   TASKQUEUE_STATS_ONLY(using taskqueue_t::stats;)
  45 
  46   // Push task t into the queue. Returns true on success.
  47   inline bool push(E t);
  48 
  49   // Attempt to pop from the queue. Returns true on success.
  50   inline bool pop(E &t);
  51 
  52   inline void clear();
  53 
  54   inline bool is_empty()        const {
  55     return _buf_empty && taskqueue_t::is_empty();
  56   }
  57 
  58 private:
  59   bool _buf_empty;
  60   E _elem;
  61 };
  62 
  63 // ObjArrayChunkedTask
  64 //
  65 // Encodes both regular oops, and the array oops plus chunking data for parallel array processing.
  66 // The design goal is to make the regular oop ops very fast, because that would be the prevailing
  67 // case. On the other hand, it should not block parallel array processing from efficiently dividing
  68 // the array work.
  69 //
  70 // The idea is to steal the bits from the 64-bit oop to encode array data, if needed. For the
  71 // proper divide-and-conquer strategies, we want to encode the "blocking" data. It turns out, the
  72 // most efficient way to do this is to encode the array block as (chunk * 2^pow), where it is assumed
  73 // that the block has the size of 2^pow. This requires for pow to have only 5 bits (2^32) to encode
  74 // all possible arrays.
  75 //
  76 //    |---------oop---------|-pow-|--chunk---|
  77 //    0                    49     54        64
  78 //
  79 // By definition, chunk == 0 means "no chunk", i.e. chunking starts from 1.
  80 //
  81 // This encoding gives a few interesting benefits:
  82 //
  83 // a) Encoding/decoding regular oops is very simple, because the upper bits are zero in that task:
  84 //
  85 //    |---------oop---------|00000|0000000000| // no chunk data
  86 //
  87 //    This helps the most ubiquitous path. The initialization amounts to putting the oop into the word
  88 //    with zero padding. Testing for "chunkedness" is testing for zero with chunk mask.
  89 //
  90 // b) Splitting tasks for divide-and-conquer is possible. Suppose we have chunk <C, P> that covers
  91 // interval [ (C-1)*2^P; C*2^P ). We can then split it into two chunks:
  92 //      <2*C - 1, P-1>, that covers interval [ (2*C - 2)*2^(P-1); (2*C - 1)*2^(P-1) )
  93 //      <2*C, P-1>,     that covers interval [ (2*C - 1)*2^(P-1);       2*C*2^(P-1) )
  94 //
  95 //    Observe that the union of these two intervals is:
  96 //      [ (2*C - 2)*2^(P-1); 2*C*2^(P-1) )
  97 //
  98 //    ...which is the original interval:
  99 //      [ (C-1)*2^P; C*2^P )
 100 //
 101 // c) The divide-and-conquer strategy could even start with chunk <1, round-log2-len(arr)>, and split
 102 //    down in the parallel threads, which alleviates the upfront (serial) splitting costs.
 103 //
 104 // Encoding limitations caused by current bitscales mean:
 105 //    10 bits for chunk: max 1024 blocks per array
 106 //     5 bits for power: max 2^32 array
 107 //    49 bits for   oop: max 512 TB of addressable space
 108 //
 109 // Stealing bits from oop trims down the addressable space. Stealing too few bits for chunk ID limits
 110 // potential parallelism. Stealing too few bits for pow limits the maximum array size that can be handled.
 111 // In future, these might be rebalanced to favor one degree of freedom against another. For example,
 112 // if/when Arrays 2.0 bring 2^64-sized arrays, we might need to steal another bit for power. We could regain
 113 // some bits back if chunks are counted in ObjArrayMarkingStride units.
 114 //
 115 // There is also a fallback version that uses plain fields, when we don't have enough space to steal the
 116 // bits from the native pointer. It is useful to debug the optimized version.
 117 //
 118 
 119 #ifdef _MSC_VER
 120 #pragma warning(push)
 121 // warning C4522: multiple assignment operators specified
 122 #pragma warning( disable:4522 )
 123 #endif
 124 
 125 #ifdef _LP64
 126 #define SHENANDOAH_OPTIMIZED_OBJTASK 1
 127 #else
 128 #define SHENANDOAH_OPTIMIZED_OBJTASK 0
 129 #endif
 130 
 131 #if SHENANDOAH_OPTIMIZED_OBJTASK
 132 class ObjArrayChunkedTask
 133 {
 134 public:
 135   enum {
 136     chunk_bits   = 10,
 137     pow_bits     = 5,
 138     oop_bits     = sizeof(uintptr_t)*8 - chunk_bits - pow_bits
 139   };
 140   enum {
 141     oop_shift    = 0,
 142     pow_shift    = oop_shift + oop_bits,
 143     chunk_shift  = pow_shift + pow_bits
 144   };
 145 
 146 public:
 147   ObjArrayChunkedTask(oop o = NULL) {
 148     assert(decode_oop(encode_oop(o)) ==  o, "oop can be encoded: " PTR_FORMAT, p2i(o));
 149     _obj = encode_oop(o);
 150   }
 151   ObjArrayChunkedTask(oop o, int chunk, int pow) {
 152     assert(decode_oop(encode_oop(o)) == o, "oop can be encoded: " PTR_FORMAT, p2i(o));
 153     assert(decode_chunk(encode_chunk(chunk)) == chunk, "chunk can be encoded: %d", chunk);
 154     assert(decode_pow(encode_pow(pow)) == pow, "pow can be encoded: %d", pow);
 155     _obj = encode_oop(o) | encode_chunk(chunk) | encode_pow(pow);
 156   }
 157   ObjArrayChunkedTask(const ObjArrayChunkedTask& t): _obj(t._obj) { }
 158 
 159   ObjArrayChunkedTask& operator =(const ObjArrayChunkedTask& t) {
 160     _obj = t._obj;
 161     return *this;
 162   }
 163   volatile ObjArrayChunkedTask&
 164   operator =(const volatile ObjArrayChunkedTask& t) volatile {
 165     (void)const_cast<uintptr_t&>(_obj = t._obj);
 166     return *this;
 167   }
 168 
 169   inline oop decode_oop(uintptr_t val) const {
 170     return (oop) reinterpret_cast<void*>((val >> oop_shift) & right_n_bits(oop_bits));
 171   }
 172 
 173   inline int decode_chunk(uintptr_t val) const {
 174     return (int) ((val >> chunk_shift) & right_n_bits(chunk_bits));
 175   }
 176 
 177   inline int decode_pow(uintptr_t val) const {
 178     return (int) ((val >> pow_shift) & right_n_bits(pow_bits));
 179   }
 180 
 181   inline uintptr_t encode_oop(oop obj) const {
 182     return ((uintptr_t)(void*) obj) << oop_shift;
 183   }
 184 
 185   inline uintptr_t encode_chunk(int chunk) const {
 186     return ((uintptr_t) chunk) << chunk_shift;
 187   }
 188 
 189   inline uintptr_t encode_pow(int pow) const {
 190     return ((uintptr_t) pow) << pow_shift;
 191   }
 192 
 193   inline oop obj()   const { return decode_oop(_obj);   }
 194   inline int chunk() const { return decode_chunk(_obj); }
 195   inline int pow()   const { return decode_pow(_obj);   }
 196   inline bool is_not_chunked() const { return (_obj & ~right_n_bits(oop_bits + pow_bits)) == 0; }
 197 
 198   DEBUG_ONLY(bool is_valid() const); // Tasks to be pushed/popped must be valid.
 199 
 200   static uintptr_t max_addressable() {
 201     return nth_bit(oop_bits);
 202   }
 203 
 204   static int chunk_size() {
 205     return nth_bit(chunk_bits);
 206   }
 207 
 208 private:
 209   uintptr_t _obj;
 210 };
 211 #else
 212 class ObjArrayChunkedTask
 213 {
 214 public:
 215   enum {
 216     chunk_bits  = 10,
 217     pow_bits    = 5,
 218   };
 219 public:
 220   ObjArrayChunkedTask(oop o = NULL, int chunk = 0, int pow = 0): _obj(o) {
 221     assert(0 <= chunk && chunk < nth_bit(chunk_bits), "chunk is sane: %d", chunk);
 222     assert(0 <= pow && pow < nth_bit(pow_bits), "pow is sane: %d", pow);
 223     _chunk = chunk;
 224     _pow = pow;
 225   }
 226   ObjArrayChunkedTask(const ObjArrayChunkedTask& t): _obj(t._obj), _chunk(t._chunk), _pow(t._pow) { }
 227 
 228   ObjArrayChunkedTask& operator =(const ObjArrayChunkedTask& t) {
 229     _obj = t._obj;
 230     _chunk = t._chunk;
 231     _pow = t._pow;
 232     return *this;
 233   }
 234   volatile ObjArrayChunkedTask&
 235   operator =(const volatile ObjArrayChunkedTask& t) volatile {
 236     (void)const_cast<oop&>(_obj = t._obj);
 237     _chunk = t._chunk;
 238     _pow = t._pow;
 239     return *this;
 240   }
 241 
 242   inline oop obj()   const { return _obj; }
 243   inline int chunk() const { return _chunk; }
 244   inline int pow()  const { return _pow; }
 245 
 246   inline bool is_not_chunked() const { return _chunk == 0; }
 247 
 248   DEBUG_ONLY(bool is_valid() const); // Tasks to be pushed/popped must be valid.
 249 
 250   static size_t max_addressable() {
 251     return sizeof(oop);
 252   }
 253 
 254   static int chunk_size() {
 255     return nth_bit(chunk_bits);
 256   }
 257 
 258 private:
 259   oop _obj;
 260   int _chunk;
 261   int _pow;
 262 };
 263 #endif // SHENANDOAH_OPTIMIZED_OBJTASK
 264 
 265 #ifdef _MSC_VER
 266 #pragma warning(pop)
 267 #endif
 268 
 269 typedef ObjArrayChunkedTask ShenandoahMarkTask;
 270 typedef BufferedOverflowTaskQueue<ShenandoahMarkTask, mtGC> ShenandoahBufferedOverflowTaskQueue;
 271 typedef Padded<ShenandoahBufferedOverflowTaskQueue> ShenandoahObjToScanQueue;
 272 
 273 template <class T, MEMFLAGS F>
 274 class ParallelClaimableQueueSet: public GenericTaskQueueSet<T, F> {
 275 private:
 276   shenandoah_padding(0);
 277   volatile jint     _claimed_index;
 278   shenandoah_padding(1);
 279 
 280   debug_only(uint   _reserved;  )
 281 
 282 public:
 283   using GenericTaskQueueSet<T, F>::size;
 284 
 285 public:
 286   ParallelClaimableQueueSet(int n) : GenericTaskQueueSet<T, F>(n), _claimed_index(0) {
 287     debug_only(_reserved = 0; )
 288   }
 289 
 290   void clear_claimed() { _claimed_index = 0; }
 291   T*   claim_next();
 292 
 293   // reserve queues that not for parallel claiming
 294   void reserve(uint n) {
 295     assert(n <= size(), "Sanity");
 296     _claimed_index = (jint)n;
 297     debug_only(_reserved = n;)
 298   }
 299 
 300   debug_only(uint get_reserved() const { return (uint)_reserved; })
 301 };
 302 
 303 template <class T, MEMFLAGS F>
 304 T* ParallelClaimableQueueSet<T, F>::claim_next() {
 305   jint size = (jint)GenericTaskQueueSet<T, F>::size();
 306 
 307   if (_claimed_index >= size) {
 308     return NULL;
 309   }
 310 
 311   jint index = Atomic::add(&_claimed_index, 1);
 312 
 313   if (index <= size) {
 314     return GenericTaskQueueSet<T, F>::queue((uint)index - 1);
 315   } else {
 316     return NULL;
 317   }
 318 }
 319 
 320 class ShenandoahObjToScanQueueSet: public ParallelClaimableQueueSet<ShenandoahObjToScanQueue, mtGC> {
 321 public:
 322   ShenandoahObjToScanQueueSet(int n) : ParallelClaimableQueueSet<ShenandoahObjToScanQueue, mtGC>(n) {}
 323 
 324   bool is_empty();
 325   void clear();
 326 
 327 #if TASKQUEUE_STATS
 328   static void print_taskqueue_stats_hdr(outputStream* const st);
 329   void print_taskqueue_stats() const;
 330   void reset_taskqueue_stats();
 331 #endif // TASKQUEUE_STATS
 332 };
 333 
 334 class ShenandoahTerminatorTerminator : public TerminatorTerminator {
 335 private:
 336   ShenandoahHeap* _heap;
 337 public:
 338   ShenandoahTerminatorTerminator(ShenandoahHeap* const heap) : _heap(heap) { }
 339   virtual bool should_exit_termination();
 340 };
 341 
 342 #endif // SHARE_GC_SHENANDOAH_SHENANDOAHTASKQUEUE_HPP