graal-compiler: src/share/vm/utilities/taskqueue.hpp annotate

annotate src/share/vm/utilities/taskqueue.hpp @ 1091:6aa7255741f3

6906727: UseCompressedOops: some card-marking fixes related to object arrays Summary: Introduced a new write_ref_array(HeapWords* start, size_t count) method that does the requisite MemRegion range calculation so (some of the) clients of the erstwhile write_ref_array(MemRegion mr) do not need to worry. This removed all external uses of array_size(), which was also simplified and made private. Asserts were added to catch other possible issues. Further, less essential, fixes stemming from this investigation are deferred to CR 6904516 (to follow shortly in hs17). Reviewed-by: kvn, coleenp, jmasa

author	ysr
date	Thu, 03 Dec 2009 15:01:57 -0800
parents	1ee412f7fec9
children	5f1f51edaff6

rev	line source
0 a61af66fc99e Initial load duke parents: diff changeset	1 /*
579 0fbdb4381b99 6814575: Update copyright year xdono parents: 546 diff changeset	2 * Copyright 2001-2009 Sun Microsystems, Inc. All Rights Reserved.
0 a61af66fc99e Initial load duke parents: diff changeset	3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
a61af66fc99e Initial load duke parents: diff changeset	4 *
a61af66fc99e Initial load duke parents: diff changeset	5 * This code is free software; you can redistribute it and/or modify it
a61af66fc99e Initial load duke parents: diff changeset	6 * under the terms of the GNU General Public License version 2 only, as
a61af66fc99e Initial load duke parents: diff changeset	7 * published by the Free Software Foundation.
a61af66fc99e Initial load duke parents: diff changeset	8 *
a61af66fc99e Initial load duke parents: diff changeset	9 * This code is distributed in the hope that it will be useful, but WITHOUT
a61af66fc99e Initial load duke parents: diff changeset	10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
a61af66fc99e Initial load duke parents: diff changeset	11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
a61af66fc99e Initial load duke parents: diff changeset	12 * version 2 for more details (a copy is included in the LICENSE file that
a61af66fc99e Initial load duke parents: diff changeset	13 * accompanied this code).
a61af66fc99e Initial load duke parents: diff changeset	14 *
a61af66fc99e Initial load duke parents: diff changeset	15 * You should have received a copy of the GNU General Public License version
a61af66fc99e Initial load duke parents: diff changeset	16 * 2 along with this work; if not, write to the Free Software Foundation,
a61af66fc99e Initial load duke parents: diff changeset	17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
a61af66fc99e Initial load duke parents: diff changeset	18 *
a61af66fc99e Initial load duke parents: diff changeset	19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
a61af66fc99e Initial load duke parents: diff changeset	20 * CA 95054 USA or visit www.sun.com if you need additional information or
a61af66fc99e Initial load duke parents: diff changeset	21 * have any questions.
a61af66fc99e Initial load duke parents: diff changeset	22 *
a61af66fc99e Initial load duke parents: diff changeset	23 */
a61af66fc99e Initial load duke parents: diff changeset	24
a61af66fc99e Initial load duke parents: diff changeset	25 class TaskQueueSuper: public CHeapObj {
a61af66fc99e Initial load duke parents: diff changeset	26 protected:
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	27 // Internal type for indexing the queue; also used for the tag.
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	28 typedef NOT_LP64(uint16_t) LP64_ONLY(uint32_t) idx_t;
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	29
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	30 // The first free element after the last one pushed (mod N).
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	31 volatile uint _bottom;
0 a61af66fc99e Initial load duke parents: diff changeset	32
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	33 enum {
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	34 N = 1 << NOT_LP64(14) LP64_ONLY(17), // Queue size: 16K or 128K
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	35 MOD_N_MASK = N - 1 // To compute x mod N efficiently.
0 a61af66fc99e Initial load duke parents: diff changeset	36 };
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	37
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	38 class Age {
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	39 public:
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	40 Age(size_t data = 0) { _data = data; }
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	41 Age(const Age& age) { _data = age._data; }
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	42 Age(idx_t top, idx_t tag) { _fields._top = top; _fields._tag = tag; }
0 a61af66fc99e Initial load duke parents: diff changeset	43
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	44 Age get() const volatile { return _data; }
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	45 void set(Age age) volatile { _data = age._data; }
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	46
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	47 idx_t top() const volatile { return _fields._top; }
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	48 idx_t tag() const volatile { return _fields._tag; }
0 a61af66fc99e Initial load duke parents: diff changeset	49
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	50 // Increment top; if it wraps, increment tag also.
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	51 void increment() {
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	52 _fields._top = increment_index(_fields._top);
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	53 if (_fields._top == 0) ++_fields._tag;
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	54 }
0 a61af66fc99e Initial load duke parents: diff changeset	55
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	56 Age cmpxchg(const Age new_age, const Age old_age) volatile {
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	57 return (size_t) Atomic::cmpxchg_ptr((intptr_t)new_age._data,
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	58 (volatile intptr_t *)&_data,
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	59 (intptr_t)old_age._data);
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	60 }
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	61
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	62 bool operator ==(const Age& other) const { return _data == other._data; }
0 a61af66fc99e Initial load duke parents: diff changeset	63
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	64 private:
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	65 struct fields {
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	66 idx_t _top;
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	67 idx_t _tag;
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	68 };
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	69 union {
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	70 size_t _data;
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	71 fields _fields;
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	72 };
0 a61af66fc99e Initial load duke parents: diff changeset	73 };
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	74
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	75 volatile Age _age;
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	76
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	77 // These both operate mod N.
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	78 static uint increment_index(uint ind) {
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	79 return (ind + 1) & MOD_N_MASK;
0 a61af66fc99e Initial load duke parents: diff changeset	80 }
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	81 static uint decrement_index(uint ind) {
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	82 return (ind - 1) & MOD_N_MASK;
0 a61af66fc99e Initial load duke parents: diff changeset	83 }
a61af66fc99e Initial load duke parents: diff changeset	84
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	85 // Returns a number in the range [0..N). If the result is "N-1", it should be
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	86 // interpreted as 0.
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	87 uint dirty_size(uint bot, uint top) {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	88 return (bot - top) & MOD_N_MASK;
0 a61af66fc99e Initial load duke parents: diff changeset	89 }
a61af66fc99e Initial load duke parents: diff changeset	90
a61af66fc99e Initial load duke parents: diff changeset	91 // Returns the size corresponding to the given "bot" and "top".
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	92 uint size(uint bot, uint top) {
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	93 uint sz = dirty_size(bot, top);
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	94 // Has the queue "wrapped", so that bottom is less than top? There's a
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	95 // complicated special case here. A pair of threads could perform pop_local
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	96 // and pop_global operations concurrently, starting from a state in which
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	97 // _bottom == _top+1. The pop_local could succeed in decrementing _bottom,
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	98 // and the pop_global in incrementing _top (in which case the pop_global
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	99 // will be awarded the contested queue element.) The resulting state must
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	100 // be interpreted as an empty queue. (We only need to worry about one such
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	101 // event: only the queue owner performs pop_local's, and several concurrent
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	102 // threads attempting to perform the pop_global will all perform the same
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	103 // CAS, and only one can succeed.) Any stealing thread that reads after
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	104 // either the increment or decrement will see an empty queue, and will not
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	105 // join the competitors. The "sz == -1 \|\| sz == N-1" state will not be
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	106 // modified by concurrent queues, so the owner thread can reset the state to
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	107 // _bottom == top so subsequent pushes will be performed normally.
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	108 return (sz == N - 1) ? 0 : sz;
0 a61af66fc99e Initial load duke parents: diff changeset	109 }
a61af66fc99e Initial load duke parents: diff changeset	110
a61af66fc99e Initial load duke parents: diff changeset	111 public:
a61af66fc99e Initial load duke parents: diff changeset	112 TaskQueueSuper() : _bottom(0), _age() {}
a61af66fc99e Initial load duke parents: diff changeset	113
a61af66fc99e Initial load duke parents: diff changeset	114 // Return "true" if the TaskQueue contains any tasks.
a61af66fc99e Initial load duke parents: diff changeset	115 bool peek();
a61af66fc99e Initial load duke parents: diff changeset	116
a61af66fc99e Initial load duke parents: diff changeset	117 // Return an estimate of the number of elements in the queue.
a61af66fc99e Initial load duke parents: diff changeset	118 // The "careful" version admits the possibility of pop_local/pop_global
a61af66fc99e Initial load duke parents: diff changeset	119 // races.
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	120 uint size() {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	121 return size(_bottom, _age.top());
0 a61af66fc99e Initial load duke parents: diff changeset	122 }
a61af66fc99e Initial load duke parents: diff changeset	123
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	124 uint dirty_size() {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	125 return dirty_size(_bottom, _age.top());
0 a61af66fc99e Initial load duke parents: diff changeset	126 }
a61af66fc99e Initial load duke parents: diff changeset	127
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	128 void set_empty() {
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	129 _bottom = 0;
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	130 _age.set(0);
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	131 }
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	132
0 a61af66fc99e Initial load duke parents: diff changeset	133 // Maximum number of elements allowed in the queue. This is two less
a61af66fc99e Initial load duke parents: diff changeset	134 // than the actual queue size, for somewhat complicated reasons.
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	135 uint max_elems() { return N - 2; }
0 a61af66fc99e Initial load duke parents: diff changeset	136 };
a61af66fc99e Initial load duke parents: diff changeset	137
a61af66fc99e Initial load duke parents: diff changeset	138 template<class E> class GenericTaskQueue: public TaskQueueSuper {
a61af66fc99e Initial load duke parents: diff changeset	139 private:
a61af66fc99e Initial load duke parents: diff changeset	140 // Slow paths for push, pop_local. (pop_global has no fast path.)
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	141 bool push_slow(E t, uint dirty_n_elems);
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	142 bool pop_local_slow(uint localBot, Age oldAge);
0 a61af66fc99e Initial load duke parents: diff changeset	143
a61af66fc99e Initial load duke parents: diff changeset	144 public:
a61af66fc99e Initial load duke parents: diff changeset	145 // Initializes the queue to empty.
a61af66fc99e Initial load duke parents: diff changeset	146 GenericTaskQueue();
a61af66fc99e Initial load duke parents: diff changeset	147
a61af66fc99e Initial load duke parents: diff changeset	148 void initialize();
a61af66fc99e Initial load duke parents: diff changeset	149
a61af66fc99e Initial load duke parents: diff changeset	150 // Push the task "t" on the queue. Returns "false" iff the queue is
a61af66fc99e Initial load duke parents: diff changeset	151 // full.
a61af66fc99e Initial load duke parents: diff changeset	152 inline bool push(E t);
a61af66fc99e Initial load duke parents: diff changeset	153
a61af66fc99e Initial load duke parents: diff changeset	154 // If succeeds in claiming a task (from the 'local' end, that is, the
a61af66fc99e Initial load duke parents: diff changeset	155 // most recently pushed task), returns "true" and sets "t" to that task.
a61af66fc99e Initial load duke parents: diff changeset	156 // Otherwise, the queue is empty and returns false.
a61af66fc99e Initial load duke parents: diff changeset	157 inline bool pop_local(E& t);
a61af66fc99e Initial load duke parents: diff changeset	158
a61af66fc99e Initial load duke parents: diff changeset	159 // If succeeds in claiming a task (from the 'global' end, that is, the
a61af66fc99e Initial load duke parents: diff changeset	160 // least recently pushed task), returns "true" and sets "t" to that task.
a61af66fc99e Initial load duke parents: diff changeset	161 // Otherwise, the queue is empty and returns false.
a61af66fc99e Initial load duke parents: diff changeset	162 bool pop_global(E& t);
a61af66fc99e Initial load duke parents: diff changeset	163
a61af66fc99e Initial load duke parents: diff changeset	164 // Delete any resource associated with the queue.
a61af66fc99e Initial load duke parents: diff changeset	165 ~GenericTaskQueue();
a61af66fc99e Initial load duke parents: diff changeset	166
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	167 // apply the closure to all elements in the task queue
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	168 void oops_do(OopClosure* f);
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	169
0 a61af66fc99e Initial load duke parents: diff changeset	170 private:
a61af66fc99e Initial load duke parents: diff changeset	171 // Element array.
a61af66fc99e Initial load duke parents: diff changeset	172 volatile E* _elems;
a61af66fc99e Initial load duke parents: diff changeset	173 };
a61af66fc99e Initial load duke parents: diff changeset	174
a61af66fc99e Initial load duke parents: diff changeset	175 template<class E>
a61af66fc99e Initial load duke parents: diff changeset	176 GenericTaskQueue<E>::GenericTaskQueue():TaskQueueSuper() {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	177 assert(sizeof(Age) == sizeof(size_t), "Depends on this.");
0 a61af66fc99e Initial load duke parents: diff changeset	178 }
a61af66fc99e Initial load duke parents: diff changeset	179
a61af66fc99e Initial load duke parents: diff changeset	180 template<class E>
a61af66fc99e Initial load duke parents: diff changeset	181 void GenericTaskQueue<E>::initialize() {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	182 _elems = NEW_C_HEAP_ARRAY(E, N);
0 a61af66fc99e Initial load duke parents: diff changeset	183 guarantee(_elems != NULL, "Allocation failed.");
a61af66fc99e Initial load duke parents: diff changeset	184 }
a61af66fc99e Initial load duke parents: diff changeset	185
a61af66fc99e Initial load duke parents: diff changeset	186 template<class E>
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	187 void GenericTaskQueue<E>::oops_do(OopClosure* f) {
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	188 // tty->print_cr("START OopTaskQueue::oops_do");
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	189 uint iters = size();
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	190 uint index = _bottom;
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	191 for (uint i = 0; i < iters; ++i) {
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	192 index = decrement_index(index);
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	193 // tty->print_cr(" doing entry %d," INTPTR_T " -> " INTPTR_T,
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	194 // index, &_elems[index], _elems[index]);
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	195 E* t = (E*)&_elems[index]; // cast away volatility
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	196 oop* p = (oop*)t;
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	197 assert((*t)->is_oop_or_null(), "Not an oop or null");
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	198 f->do_oop(p);
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	199 }
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	200 // tty->print_cr("END OopTaskQueue::oops_do");
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	201 }
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	202
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	203
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	204 template<class E>
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	205 bool GenericTaskQueue<E>::push_slow(E t, uint dirty_n_elems) {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	206 if (dirty_n_elems == N - 1) {
0 a61af66fc99e Initial load duke parents: diff changeset	207 // Actually means 0, so do the push.
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	208 uint localBot = _bottom;
0 a61af66fc99e Initial load duke parents: diff changeset	209 _elems[localBot] = t;
1024 2c03ce058f55 6888847: TaskQueue needs release_store() for correctness on RMO machines bobv parents: 907 diff changeset	210 OrderAccess::release_store(&_bottom, increment_index(localBot));
0 a61af66fc99e Initial load duke parents: diff changeset	211 return true;
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	212 }
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	213 return false;
0 a61af66fc99e Initial load duke parents: diff changeset	214 }
a61af66fc99e Initial load duke parents: diff changeset	215
a61af66fc99e Initial load duke parents: diff changeset	216 template<class E>
a61af66fc99e Initial load duke parents: diff changeset	217 bool GenericTaskQueue<E>::
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	218 pop_local_slow(uint localBot, Age oldAge) {
0 a61af66fc99e Initial load duke parents: diff changeset	219 // This queue was observed to contain exactly one element; either this
a61af66fc99e Initial load duke parents: diff changeset	220 // thread will claim it, or a competing "pop_global". In either case,
a61af66fc99e Initial load duke parents: diff changeset	221 // the queue will be logically empty afterwards. Create a new Age value
a61af66fc99e Initial load duke parents: diff changeset	222 // that represents the empty queue for the given value of "_bottom". (We
a61af66fc99e Initial load duke parents: diff changeset	223 // must also increment "tag" because of the case where "bottom == 1",
a61af66fc99e Initial load duke parents: diff changeset	224 // "top == 0". A pop_global could read the queue element in that case,
a61af66fc99e Initial load duke parents: diff changeset	225 // then have the owner thread do a pop followed by another push. Without
a61af66fc99e Initial load duke parents: diff changeset	226 // the incrementing of "tag", the pop_global's CAS could succeed,
a61af66fc99e Initial load duke parents: diff changeset	227 // allowing it to believe it has claimed the stale element.)
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	228 Age newAge((idx_t)localBot, oldAge.tag() + 1);
0 a61af66fc99e Initial load duke parents: diff changeset	229 // Perhaps a competing pop_global has already incremented "top", in which
a61af66fc99e Initial load duke parents: diff changeset	230 // case it wins the element.
a61af66fc99e Initial load duke parents: diff changeset	231 if (localBot == oldAge.top()) {
a61af66fc99e Initial load duke parents: diff changeset	232 // No competing pop_global has yet incremented "top"; we'll try to
a61af66fc99e Initial load duke parents: diff changeset	233 // install new_age, thus claiming the element.
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	234 Age tempAge = _age.cmpxchg(newAge, oldAge);
0 a61af66fc99e Initial load duke parents: diff changeset	235 if (tempAge == oldAge) {
a61af66fc99e Initial load duke parents: diff changeset	236 // We win.
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	237 assert(dirty_size(localBot, _age.top()) != N - 1, "sanity");
0 a61af66fc99e Initial load duke parents: diff changeset	238 return true;
a61af66fc99e Initial load duke parents: diff changeset	239 }
a61af66fc99e Initial load duke parents: diff changeset	240 }
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	241 // We lose; a completing pop_global gets the element. But the queue is empty
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	242 // and top is greater than bottom. Fix this representation of the empty queue
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	243 // to become the canonical one.
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	244 _age.set(newAge);
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	245 assert(dirty_size(localBot, _age.top()) != N - 1, "sanity");
0 a61af66fc99e Initial load duke parents: diff changeset	246 return false;
a61af66fc99e Initial load duke parents: diff changeset	247 }
a61af66fc99e Initial load duke parents: diff changeset	248
a61af66fc99e Initial load duke parents: diff changeset	249 template<class E>
a61af66fc99e Initial load duke parents: diff changeset	250 bool GenericTaskQueue<E>::pop_global(E& t) {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	251 Age oldAge = _age.get();
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	252 uint localBot = _bottom;
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	253 uint n_elems = size(localBot, oldAge.top());
0 a61af66fc99e Initial load duke parents: diff changeset	254 if (n_elems == 0) {
a61af66fc99e Initial load duke parents: diff changeset	255 return false;
a61af66fc99e Initial load duke parents: diff changeset	256 }
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	257
0 a61af66fc99e Initial load duke parents: diff changeset	258 t = _elems[oldAge.top()];
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	259 Age newAge(oldAge);
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	260 newAge.increment();
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	261 Age resAge = _age.cmpxchg(newAge, oldAge);
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	262
0 a61af66fc99e Initial load duke parents: diff changeset	263 // Note that using "_bottom" here might fail, since a pop_local might
a61af66fc99e Initial load duke parents: diff changeset	264 // have decremented it.
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	265 assert(dirty_size(localBot, newAge.top()) != N - 1, "sanity");
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	266 return resAge == oldAge;
0 a61af66fc99e Initial load duke parents: diff changeset	267 }
a61af66fc99e Initial load duke parents: diff changeset	268
a61af66fc99e Initial load duke parents: diff changeset	269 template<class E>
a61af66fc99e Initial load duke parents: diff changeset	270 GenericTaskQueue<E>::~GenericTaskQueue() {
a61af66fc99e Initial load duke parents: diff changeset	271 FREE_C_HEAP_ARRAY(E, _elems);
a61af66fc99e Initial load duke parents: diff changeset	272 }
a61af66fc99e Initial load duke parents: diff changeset	273
a61af66fc99e Initial load duke parents: diff changeset	274 // Inherits the typedef of "Task" from above.
a61af66fc99e Initial load duke parents: diff changeset	275 class TaskQueueSetSuper: public CHeapObj {
a61af66fc99e Initial load duke parents: diff changeset	276 protected:
a61af66fc99e Initial load duke parents: diff changeset	277 static int randomParkAndMiller(int* seed0);
a61af66fc99e Initial load duke parents: diff changeset	278 public:
a61af66fc99e Initial load duke parents: diff changeset	279 // Returns "true" if some TaskQueue in the set contains a task.
a61af66fc99e Initial load duke parents: diff changeset	280 virtual bool peek() = 0;
a61af66fc99e Initial load duke parents: diff changeset	281 };
a61af66fc99e Initial load duke parents: diff changeset	282
a61af66fc99e Initial load duke parents: diff changeset	283 template<class E> class GenericTaskQueueSet: public TaskQueueSetSuper {
a61af66fc99e Initial load duke parents: diff changeset	284 private:
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	285 uint _n;
0 a61af66fc99e Initial load duke parents: diff changeset	286 GenericTaskQueue<E>** _queues;
a61af66fc99e Initial load duke parents: diff changeset	287
a61af66fc99e Initial load duke parents: diff changeset	288 public:
a61af66fc99e Initial load duke parents: diff changeset	289 GenericTaskQueueSet(int n) : _n(n) {
a61af66fc99e Initial load duke parents: diff changeset	290 typedef GenericTaskQueue<E>* GenericTaskQueuePtr;
a61af66fc99e Initial load duke parents: diff changeset	291 _queues = NEW_C_HEAP_ARRAY(GenericTaskQueuePtr, n);
a61af66fc99e Initial load duke parents: diff changeset	292 guarantee(_queues != NULL, "Allocation failure.");
a61af66fc99e Initial load duke parents: diff changeset	293 for (int i = 0; i < n; i++) {
a61af66fc99e Initial load duke parents: diff changeset	294 _queues[i] = NULL;
a61af66fc99e Initial load duke parents: diff changeset	295 }
a61af66fc99e Initial load duke parents: diff changeset	296 }
a61af66fc99e Initial load duke parents: diff changeset	297
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	298 bool steal_1_random(uint queue_num, int* seed, E& t);
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	299 bool steal_best_of_2(uint queue_num, int* seed, E& t);
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	300 bool steal_best_of_all(uint queue_num, int* seed, E& t);
0 a61af66fc99e Initial load duke parents: diff changeset	301
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	302 void register_queue(uint i, GenericTaskQueue<E>* q);
0 a61af66fc99e Initial load duke parents: diff changeset	303
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	304 GenericTaskQueue<E>* queue(uint n);
0 a61af66fc99e Initial load duke parents: diff changeset	305
a61af66fc99e Initial load duke parents: diff changeset	306 // The thread with queue number "queue_num" (and whose random number seed
a61af66fc99e Initial load duke parents: diff changeset	307 // is at "seed") is trying to steal a task from some other queue. (It
a61af66fc99e Initial load duke parents: diff changeset	308 // may try several queues, according to some configuration parameter.)
a61af66fc99e Initial load duke parents: diff changeset	309 // If some steal succeeds, returns "true" and sets "t" the stolen task,
a61af66fc99e Initial load duke parents: diff changeset	310 // otherwise returns false.
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	311 bool steal(uint queue_num, int* seed, E& t);
0 a61af66fc99e Initial load duke parents: diff changeset	312
a61af66fc99e Initial load duke parents: diff changeset	313 bool peek();
a61af66fc99e Initial load duke parents: diff changeset	314 };
a61af66fc99e Initial load duke parents: diff changeset	315
a61af66fc99e Initial load duke parents: diff changeset	316 template<class E>
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	317 void GenericTaskQueueSet<E>::register_queue(uint i, GenericTaskQueue<E>* q) {
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	318 assert(i < _n, "index out of range.");
0 a61af66fc99e Initial load duke parents: diff changeset	319 _queues[i] = q;
a61af66fc99e Initial load duke parents: diff changeset	320 }
a61af66fc99e Initial load duke parents: diff changeset	321
a61af66fc99e Initial load duke parents: diff changeset	322 template<class E>
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	323 GenericTaskQueue<E>* GenericTaskQueueSet<E>::queue(uint i) {
0 a61af66fc99e Initial load duke parents: diff changeset	324 return _queues[i];
a61af66fc99e Initial load duke parents: diff changeset	325 }
a61af66fc99e Initial load duke parents: diff changeset	326
a61af66fc99e Initial load duke parents: diff changeset	327 template<class E>
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	328 bool GenericTaskQueueSet<E>::steal(uint queue_num, int* seed, E& t) {
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	329 for (uint i = 0; i < 2 * _n; i++)
0 a61af66fc99e Initial load duke parents: diff changeset	330 if (steal_best_of_2(queue_num, seed, t))
a61af66fc99e Initial load duke parents: diff changeset	331 return true;
a61af66fc99e Initial load duke parents: diff changeset	332 return false;
a61af66fc99e Initial load duke parents: diff changeset	333 }
a61af66fc99e Initial load duke parents: diff changeset	334
a61af66fc99e Initial load duke parents: diff changeset	335 template<class E>
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	336 bool GenericTaskQueueSet<E>::steal_best_of_all(uint queue_num, int* seed, E& t) {
0 a61af66fc99e Initial load duke parents: diff changeset	337 if (_n > 2) {
a61af66fc99e Initial load duke parents: diff changeset	338 int best_k;
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	339 uint best_sz = 0;
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	340 for (uint k = 0; k < _n; k++) {
0 a61af66fc99e Initial load duke parents: diff changeset	341 if (k == queue_num) continue;
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	342 uint sz = _queues[k]->size();
0 a61af66fc99e Initial load duke parents: diff changeset	343 if (sz > best_sz) {
a61af66fc99e Initial load duke parents: diff changeset	344 best_sz = sz;
a61af66fc99e Initial load duke parents: diff changeset	345 best_k = k;
a61af66fc99e Initial load duke parents: diff changeset	346 }
a61af66fc99e Initial load duke parents: diff changeset	347 }
a61af66fc99e Initial load duke parents: diff changeset	348 return best_sz > 0 && _queues[best_k]->pop_global(t);
a61af66fc99e Initial load duke parents: diff changeset	349 } else if (_n == 2) {
a61af66fc99e Initial load duke parents: diff changeset	350 // Just try the other one.
a61af66fc99e Initial load duke parents: diff changeset	351 int k = (queue_num + 1) % 2;
a61af66fc99e Initial load duke parents: diff changeset	352 return _queues[k]->pop_global(t);
a61af66fc99e Initial load duke parents: diff changeset	353 } else {
a61af66fc99e Initial load duke parents: diff changeset	354 assert(_n == 1, "can't be zero.");
a61af66fc99e Initial load duke parents: diff changeset	355 return false;
a61af66fc99e Initial load duke parents: diff changeset	356 }
a61af66fc99e Initial load duke parents: diff changeset	357 }
a61af66fc99e Initial load duke parents: diff changeset	358
a61af66fc99e Initial load duke parents: diff changeset	359 template<class E>
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	360 bool GenericTaskQueueSet<E>::steal_1_random(uint queue_num, int* seed, E& t) {
0 a61af66fc99e Initial load duke parents: diff changeset	361 if (_n > 2) {
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	362 uint k = queue_num;
0 a61af66fc99e Initial load duke parents: diff changeset	363 while (k == queue_num) k = randomParkAndMiller(seed) % _n;
a61af66fc99e Initial load duke parents: diff changeset	364 return _queues[2]->pop_global(t);
a61af66fc99e Initial load duke parents: diff changeset	365 } else if (_n == 2) {
a61af66fc99e Initial load duke parents: diff changeset	366 // Just try the other one.
a61af66fc99e Initial load duke parents: diff changeset	367 int k = (queue_num + 1) % 2;
a61af66fc99e Initial load duke parents: diff changeset	368 return _queues[k]->pop_global(t);
a61af66fc99e Initial load duke parents: diff changeset	369 } else {
a61af66fc99e Initial load duke parents: diff changeset	370 assert(_n == 1, "can't be zero.");
a61af66fc99e Initial load duke parents: diff changeset	371 return false;
a61af66fc99e Initial load duke parents: diff changeset	372 }
a61af66fc99e Initial load duke parents: diff changeset	373 }
a61af66fc99e Initial load duke parents: diff changeset	374
a61af66fc99e Initial load duke parents: diff changeset	375 template<class E>
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	376 bool GenericTaskQueueSet<E>::steal_best_of_2(uint queue_num, int* seed, E& t) {
0 a61af66fc99e Initial load duke parents: diff changeset	377 if (_n > 2) {
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	378 uint k1 = queue_num;
0 a61af66fc99e Initial load duke parents: diff changeset	379 while (k1 == queue_num) k1 = randomParkAndMiller(seed) % _n;
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	380 uint k2 = queue_num;
0 a61af66fc99e Initial load duke parents: diff changeset	381 while (k2 == queue_num \|\| k2 == k1) k2 = randomParkAndMiller(seed) % _n;
a61af66fc99e Initial load duke parents: diff changeset	382 // Sample both and try the larger.
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	383 uint sz1 = _queues[k1]->size();
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	384 uint sz2 = _queues[k2]->size();
0 a61af66fc99e Initial load duke parents: diff changeset	385 if (sz2 > sz1) return _queues[k2]->pop_global(t);
a61af66fc99e Initial load duke parents: diff changeset	386 else return _queues[k1]->pop_global(t);
a61af66fc99e Initial load duke parents: diff changeset	387 } else if (_n == 2) {
a61af66fc99e Initial load duke parents: diff changeset	388 // Just try the other one.
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	389 uint k = (queue_num + 1) % 2;
0 a61af66fc99e Initial load duke parents: diff changeset	390 return _queues[k]->pop_global(t);
a61af66fc99e Initial load duke parents: diff changeset	391 } else {
a61af66fc99e Initial load duke parents: diff changeset	392 assert(_n == 1, "can't be zero.");
a61af66fc99e Initial load duke parents: diff changeset	393 return false;
a61af66fc99e Initial load duke parents: diff changeset	394 }
a61af66fc99e Initial load duke parents: diff changeset	395 }
a61af66fc99e Initial load duke parents: diff changeset	396
a61af66fc99e Initial load duke parents: diff changeset	397 template<class E>
a61af66fc99e Initial load duke parents: diff changeset	398 bool GenericTaskQueueSet<E>::peek() {
a61af66fc99e Initial load duke parents: diff changeset	399 // Try all the queues.
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	400 for (uint j = 0; j < _n; j++) {
0 a61af66fc99e Initial load duke parents: diff changeset	401 if (_queues[j]->peek())
a61af66fc99e Initial load duke parents: diff changeset	402 return true;
a61af66fc99e Initial load duke parents: diff changeset	403 }
a61af66fc99e Initial load duke parents: diff changeset	404 return false;
a61af66fc99e Initial load duke parents: diff changeset	405 }
a61af66fc99e Initial load duke parents: diff changeset	406
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	407 // When to terminate from the termination protocol.
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	408 class TerminatorTerminator: public CHeapObj {
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	409 public:
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	410 virtual bool should_exit_termination() = 0;
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	411 };
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	412
0 a61af66fc99e Initial load duke parents: diff changeset	413 // A class to aid in the termination of a set of parallel tasks using
a61af66fc99e Initial load duke parents: diff changeset	414 // TaskQueueSet's for work stealing.
a61af66fc99e Initial load duke parents: diff changeset	415
546 05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	416 #undef TRACESPINNING
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	417
0 a61af66fc99e Initial load duke parents: diff changeset	418 class ParallelTaskTerminator: public StackObj {
a61af66fc99e Initial load duke parents: diff changeset	419 private:
a61af66fc99e Initial load duke parents: diff changeset	420 int _n_threads;
a61af66fc99e Initial load duke parents: diff changeset	421 TaskQueueSetSuper* _queue_set;
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	422 int _offered_termination;
0 a61af66fc99e Initial load duke parents: diff changeset	423
546 05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	424 #ifdef TRACESPINNING
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	425 static uint _total_yields;
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	426 static uint _total_spins;
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	427 static uint _total_peeks;
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	428 #endif
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	429
0 a61af66fc99e Initial load duke parents: diff changeset	430 bool peek_in_queue_set();
a61af66fc99e Initial load duke parents: diff changeset	431 protected:
a61af66fc99e Initial load duke parents: diff changeset	432 virtual void yield();
a61af66fc99e Initial load duke parents: diff changeset	433 void sleep(uint millis);
a61af66fc99e Initial load duke parents: diff changeset	434
a61af66fc99e Initial load duke parents: diff changeset	435 public:
a61af66fc99e Initial load duke parents: diff changeset	436
a61af66fc99e Initial load duke parents: diff changeset	437 // "n_threads" is the number of threads to be terminated. "queue_set" is a
a61af66fc99e Initial load duke parents: diff changeset	438 // queue sets of work queues of other threads.
a61af66fc99e Initial load duke parents: diff changeset	439 ParallelTaskTerminator(int n_threads, TaskQueueSetSuper* queue_set);
a61af66fc99e Initial load duke parents: diff changeset	440
a61af66fc99e Initial load duke parents: diff changeset	441 // The current thread has no work, and is ready to terminate if everyone
a61af66fc99e Initial load duke parents: diff changeset	442 // else is. If returns "true", all threads are terminated. If returns
a61af66fc99e Initial load duke parents: diff changeset	443 // "false", available work has been observed in one of the task queues,
a61af66fc99e Initial load duke parents: diff changeset	444 // so the global task is not complete.
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	445 bool offer_termination() {
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	446 return offer_termination(NULL);
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	447 }
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	448
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	449 // As above, but it also terminates if the should_exit_termination()
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	450 // method of the terminator parameter returns true. If terminator is
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	451 // NULL, then it is ignored.
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	452 bool offer_termination(TerminatorTerminator* terminator);
0 a61af66fc99e Initial load duke parents: diff changeset	453
a61af66fc99e Initial load duke parents: diff changeset	454 // Reset the terminator, so that it may be reused again.
a61af66fc99e Initial load duke parents: diff changeset	455 // The caller is responsible for ensuring that this is done
a61af66fc99e Initial load duke parents: diff changeset	456 // in an MT-safe manner, once the previous round of use of
a61af66fc99e Initial load duke parents: diff changeset	457 // the terminator is finished.
a61af66fc99e Initial load duke parents: diff changeset	458 void reset_for_reuse();
a61af66fc99e Initial load duke parents: diff changeset	459
546 05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	460 #ifdef TRACESPINNING
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	461 static uint total_yields() { return _total_yields; }
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	462 static uint total_spins() { return _total_spins; }
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	463 static uint total_peeks() { return _total_peeks; }
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	464 static void print_termination_counts();
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	465 #endif
0 a61af66fc99e Initial load duke parents: diff changeset	466 };
a61af66fc99e Initial load duke parents: diff changeset	467
a61af66fc99e Initial load duke parents: diff changeset	468 template<class E> inline bool GenericTaskQueue<E>::push(E t) {
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	469 uint localBot = _bottom;
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	470 assert((localBot >= 0) && (localBot < N), "_bottom out of range.");
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	471 idx_t top = _age.top();
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	472 uint dirty_n_elems = dirty_size(localBot, top);
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	473 assert((dirty_n_elems >= 0) && (dirty_n_elems < N), "n_elems out of range.");
0 a61af66fc99e Initial load duke parents: diff changeset	474 if (dirty_n_elems < max_elems()) {
a61af66fc99e Initial load duke parents: diff changeset	475 _elems[localBot] = t;
1024 2c03ce058f55 6888847: TaskQueue needs release_store() for correctness on RMO machines bobv parents: 907 diff changeset	476 OrderAccess::release_store(&_bottom, increment_index(localBot));
0 a61af66fc99e Initial load duke parents: diff changeset	477 return true;
a61af66fc99e Initial load duke parents: diff changeset	478 } else {
a61af66fc99e Initial load duke parents: diff changeset	479 return push_slow(t, dirty_n_elems);
a61af66fc99e Initial load duke parents: diff changeset	480 }
a61af66fc99e Initial load duke parents: diff changeset	481 }
a61af66fc99e Initial load duke parents: diff changeset	482
a61af66fc99e Initial load duke parents: diff changeset	483 template<class E> inline bool GenericTaskQueue<E>::pop_local(E& t) {
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	484 uint localBot = _bottom;
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	485 // This value cannot be N-1. That can only occur as a result of
0 a61af66fc99e Initial load duke parents: diff changeset	486 // the assignment to bottom in this method. If it does, this method
a61af66fc99e Initial load duke parents: diff changeset	487 // resets the size( to 0 before the next call (which is sequential,
a61af66fc99e Initial load duke parents: diff changeset	488 // since this is pop_local.)
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	489 uint dirty_n_elems = dirty_size(localBot, _age.top());
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	490 assert(dirty_n_elems != N - 1, "Shouldn't be possible...");
0 a61af66fc99e Initial load duke parents: diff changeset	491 if (dirty_n_elems == 0) return false;
a61af66fc99e Initial load duke parents: diff changeset	492 localBot = decrement_index(localBot);
a61af66fc99e Initial load duke parents: diff changeset	493 _bottom = localBot;
a61af66fc99e Initial load duke parents: diff changeset	494 // This is necessary to prevent any read below from being reordered
a61af66fc99e Initial load duke parents: diff changeset	495 // before the store just above.
a61af66fc99e Initial load duke parents: diff changeset	496 OrderAccess::fence();
a61af66fc99e Initial load duke parents: diff changeset	497 t = _elems[localBot];
a61af66fc99e Initial load duke parents: diff changeset	498 // This is a second read of "age"; the "size()" above is the first.
a61af66fc99e Initial load duke parents: diff changeset	499 // If there's still at least one element in the queue, based on the
a61af66fc99e Initial load duke parents: diff changeset	500 // "_bottom" and "age" we've read, then there can be no interference with
a61af66fc99e Initial load duke parents: diff changeset	501 // a "pop_global" operation, and we're done.
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	502 idx_t tp = _age.top(); // XXX
0 a61af66fc99e Initial load duke parents: diff changeset	503 if (size(localBot, tp) > 0) {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	504 assert(dirty_size(localBot, tp) != N - 1, "sanity");
0 a61af66fc99e Initial load duke parents: diff changeset	505 return true;
a61af66fc99e Initial load duke parents: diff changeset	506 } else {
a61af66fc99e Initial load duke parents: diff changeset	507 // Otherwise, the queue contained exactly one element; we take the slow
a61af66fc99e Initial load duke parents: diff changeset	508 // path.
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	509 return pop_local_slow(localBot, _age.get());
0 a61af66fc99e Initial load duke parents: diff changeset	510 }
a61af66fc99e Initial load duke parents: diff changeset	511 }
a61af66fc99e Initial load duke parents: diff changeset	512
a61af66fc99e Initial load duke parents: diff changeset	513 typedef oop Task;
a61af66fc99e Initial load duke parents: diff changeset	514 typedef GenericTaskQueue<Task> OopTaskQueue;
a61af66fc99e Initial load duke parents: diff changeset	515 typedef GenericTaskQueueSet<Task> OopTaskQueueSet;
a61af66fc99e Initial load duke parents: diff changeset	516
113 ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	517
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	518 #define COMPRESSED_OOP_MASK 1
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	519
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	520 // This is a container class for either an oop* or a narrowOop*.
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	521 // Both are pushed onto a task queue and the consumer will test is_narrow()
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	522 // to determine which should be processed.
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	523 class StarTask {
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	524 void* _holder; // either union oop* or narrowOop*
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	525 public:
845 df6caf649ff7 6700789: G1: Enable use of compressed oops with G1 heaps ysr parents: 579 diff changeset	526 StarTask(narrowOop* p) {
df6caf649ff7 6700789: G1: Enable use of compressed oops with G1 heaps ysr parents: 579 diff changeset	527 assert(((uintptr_t)p & COMPRESSED_OOP_MASK) == 0, "Information loss!");
df6caf649ff7 6700789: G1: Enable use of compressed oops with G1 heaps ysr parents: 579 diff changeset	528 _holder = (void *)((uintptr_t)p \| COMPRESSED_OOP_MASK);
df6caf649ff7 6700789: G1: Enable use of compressed oops with G1 heaps ysr parents: 579 diff changeset	529 }
df6caf649ff7 6700789: G1: Enable use of compressed oops with G1 heaps ysr parents: 579 diff changeset	530 StarTask(oop* p) {
df6caf649ff7 6700789: G1: Enable use of compressed oops with G1 heaps ysr parents: 579 diff changeset	531 assert(((uintptr_t)p & COMPRESSED_OOP_MASK) == 0, "Information loss!");
df6caf649ff7 6700789: G1: Enable use of compressed oops with G1 heaps ysr parents: 579 diff changeset	532 _holder = (void*)p;
df6caf649ff7 6700789: G1: Enable use of compressed oops with G1 heaps ysr parents: 579 diff changeset	533 }
113 ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	534 StarTask() { _holder = NULL; }
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	535 operator oop() { return (oop)_holder; }
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	536 operator narrowOop*() {
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	537 return (narrowOop*)((uintptr_t)_holder & ~COMPRESSED_OOP_MASK);
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	538 }
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	539
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	540 // Operators to preserve const/volatile in assignments required by gcc
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	541 void operator=(const volatile StarTask& t) volatile { _holder = t._holder; }
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	542
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	543 bool is_narrow() const {
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	544 return (((uintptr_t)_holder & COMPRESSED_OOP_MASK) != 0);
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	545 }
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	546 };
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	547
0 a61af66fc99e Initial load duke parents: diff changeset	548 typedef GenericTaskQueue<StarTask> OopStarTaskQueue;
a61af66fc99e Initial load duke parents: diff changeset	549 typedef GenericTaskQueueSet<StarTask> OopStarTaskQueueSet;
a61af66fc99e Initial load duke parents: diff changeset	550
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	551 typedef size_t RegionTask; // index for region
81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	552 typedef GenericTaskQueue<RegionTask> RegionTaskQueue;
81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	553 typedef GenericTaskQueueSet<RegionTask> RegionTaskQueueSet;
0 a61af66fc99e Initial load duke parents: diff changeset	554
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	555 class RegionTaskQueueWithOverflow: public CHeapObj {
0 a61af66fc99e Initial load duke parents: diff changeset	556 protected:
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	557 RegionTaskQueue _region_queue;
81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	558 GrowableArray<RegionTask>* _overflow_stack;
0 a61af66fc99e Initial load duke parents: diff changeset	559
a61af66fc99e Initial load duke parents: diff changeset	560 public:
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	561 RegionTaskQueueWithOverflow() : _overflow_stack(NULL) {}
0 a61af66fc99e Initial load duke parents: diff changeset	562 // Initialize both stealable queue and overflow
a61af66fc99e Initial load duke parents: diff changeset	563 void initialize();
a61af66fc99e Initial load duke parents: diff changeset	564 // Save first to stealable queue and then to overflow
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	565 void save(RegionTask t);
0 a61af66fc99e Initial load duke parents: diff changeset	566 // Retrieve first from overflow and then from stealable queue
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	567 bool retrieve(RegionTask& region_index);
0 a61af66fc99e Initial load duke parents: diff changeset	568 // Retrieve from stealable queue
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	569 bool retrieve_from_stealable_queue(RegionTask& region_index);
0 a61af66fc99e Initial load duke parents: diff changeset	570 // Retrieve from overflow
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	571 bool retrieve_from_overflow(RegionTask& region_index);
0 a61af66fc99e Initial load duke parents: diff changeset	572 bool is_empty();
a61af66fc99e Initial load duke parents: diff changeset	573 bool stealable_is_empty();
a61af66fc99e Initial load duke parents: diff changeset	574 bool overflow_is_empty();
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	575 uint stealable_size() { return _region_queue.size(); }
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	576 RegionTaskQueue* task_queue() { return &_region_queue; }
0 a61af66fc99e Initial load duke parents: diff changeset	577 };
a61af66fc99e Initial load duke parents: diff changeset	578
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	579 #define USE_RegionTaskQueueWithOverflow

Mercurial > hg > graal-compiler

annotate src/share/vm/utilities/taskqueue.hpp @ 1091:6aa7255741f3