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

annotate src/share/vm/utilities/taskqueue.hpp @ 1311:2a1472c30599

4396719: Mark Sweep stack overflow on deeply nested Object arrays Summary: Use an explicit stack for object arrays and process them in chunks. Reviewed-by: iveresov, apetrusenko

author	jcoomes
date	Wed, 03 Mar 2010 14:48:26 -0800
parents	5f1f51edaff6
children	c18cbe5936b8

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
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	25 template <unsigned int N>
0 a61af66fc99e Initial load duke parents: diff changeset	26 class TaskQueueSuper: public CHeapObj {
a61af66fc99e Initial load duke parents: diff changeset	27 protected:
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	28 // 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	29 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	30
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	31 // 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	32 volatile uint _bottom;
0 a61af66fc99e Initial load duke parents: diff changeset	33
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	34 enum { MOD_N_MASK = N - 1 };
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	35
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	36 class Age {
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	37 public:
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	38 Age(size_t data = 0) { _data = data; }
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	39 Age(const Age& age) { _data = age._data; }
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	40 Age(idx_t top, idx_t tag) { _fields._top = top; _fields._tag = tag; }
0 a61af66fc99e Initial load duke parents: diff changeset	41
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	42 Age get() const volatile { return _data; }
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	43 void set(Age age) volatile { _data = age._data; }
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	44
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	45 idx_t top() const volatile { return _fields._top; }
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	46 idx_t tag() const volatile { return _fields._tag; }
0 a61af66fc99e Initial load duke parents: diff changeset	47
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	48 // Increment top; if it wraps, increment tag also.
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	49 void increment() {
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	50 _fields._top = increment_index(_fields._top);
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	51 if (_fields._top == 0) ++_fields._tag;
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	52 }
0 a61af66fc99e Initial load duke parents: diff changeset	53
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	54 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	55 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	56 (volatile intptr_t *)&_data,
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	57 (intptr_t)old_age._data);
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	58 }
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	59
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	60 bool operator ==(const Age& other) const { return _data == other._data; }
0 a61af66fc99e Initial load duke parents: diff changeset	61
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	62 private:
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	63 struct fields {
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	64 idx_t _top;
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	65 idx_t _tag;
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	66 };
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	67 union {
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	68 size_t _data;
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	69 fields _fields;
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	70 };
0 a61af66fc99e Initial load duke parents: diff changeset	71 };
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	72
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	73 volatile Age _age;
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 // These both operate mod N.
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	76 static uint increment_index(uint ind) {
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	77 return (ind + 1) & MOD_N_MASK;
0 a61af66fc99e Initial load duke parents: diff changeset	78 }
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	79 static uint decrement_index(uint ind) {
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	80 return (ind - 1) & MOD_N_MASK;
0 a61af66fc99e Initial load duke parents: diff changeset	81 }
a61af66fc99e Initial load duke parents: diff changeset	82
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	83 // 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	84 // interpreted as 0.
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	85 uint dirty_size(uint bot, uint top) const {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	86 return (bot - top) & MOD_N_MASK;
0 a61af66fc99e Initial load duke parents: diff changeset	87 }
a61af66fc99e Initial load duke parents: diff changeset	88
a61af66fc99e Initial load duke parents: diff changeset	89 // Returns the size corresponding to the given "bot" and "top".
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	90 uint size(uint bot, uint top) const {
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	91 uint sz = dirty_size(bot, top);
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	92 // 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	93 // 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	94 // 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	95 // _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	96 // 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	97 // 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	98 // 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	99 // 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	100 // 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	101 // 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	102 // 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	103 // 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	104 // 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	105 // _bottom == top so subsequent pushes will be performed normally.
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	106 return (sz == N - 1) ? 0 : sz;
0 a61af66fc99e Initial load duke parents: diff changeset	107 }
a61af66fc99e Initial load duke parents: diff changeset	108
a61af66fc99e Initial load duke parents: diff changeset	109 public:
a61af66fc99e Initial load duke parents: diff changeset	110 TaskQueueSuper() : _bottom(0), _age() {}
a61af66fc99e Initial load duke parents: diff changeset	111
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	112 // Return true if the TaskQueue contains any tasks.
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	113 bool peek() { return _bottom != _age.top(); }
0 a61af66fc99e Initial load duke parents: diff changeset	114
a61af66fc99e Initial load duke parents: diff changeset	115 // Return an estimate of the number of elements in the queue.
a61af66fc99e Initial load duke parents: diff changeset	116 // The "careful" version admits the possibility of pop_local/pop_global
a61af66fc99e Initial load duke parents: diff changeset	117 // races.
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	118 uint size() const {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	119 return size(_bottom, _age.top());
0 a61af66fc99e Initial load duke parents: diff changeset	120 }
a61af66fc99e Initial load duke parents: diff changeset	121
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	122 uint dirty_size() const {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	123 return dirty_size(_bottom, _age.top());
0 a61af66fc99e Initial load duke parents: diff changeset	124 }
a61af66fc99e Initial load duke parents: diff changeset	125
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	126 void set_empty() {
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	127 _bottom = 0;
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	128 _age.set(0);
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	129 }
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	130
0 a61af66fc99e Initial load duke parents: diff changeset	131 // Maximum number of elements allowed in the queue. This is two less
a61af66fc99e Initial load duke parents: diff changeset	132 // than the actual queue size, for somewhat complicated reasons.
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	133 uint max_elems() const { return N - 2; }
1284 5f1f51edaff6 6928081: G1: rename parameters common with CMS jmasa parents: 1025 diff changeset	134
5f1f51edaff6 6928081: G1: rename parameters common with CMS jmasa parents: 1025 diff changeset	135 // Total size of queue.
5f1f51edaff6 6928081: G1: rename parameters common with CMS jmasa parents: 1025 diff changeset	136 static const uint total_size() { return N; }
0 a61af66fc99e Initial load duke parents: diff changeset	137 };
a61af66fc99e Initial load duke parents: diff changeset	138
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	139 template<class E, unsigned int N = TASKQUEUE_SIZE>
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	140 class GenericTaskQueue: public TaskQueueSuper<N> {
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	141 protected:
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	142 typedef typename TaskQueueSuper<N>::Age Age;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	143 typedef typename TaskQueueSuper<N>::idx_t idx_t;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	144
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	145 using TaskQueueSuper<N>::_bottom;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	146 using TaskQueueSuper<N>::_age;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	147 using TaskQueueSuper<N>::increment_index;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	148 using TaskQueueSuper<N>::decrement_index;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	149 using TaskQueueSuper<N>::dirty_size;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	150
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	151 public:
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	152 using TaskQueueSuper<N>::max_elems;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	153 using TaskQueueSuper<N>::size;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	154
0 a61af66fc99e Initial load duke parents: diff changeset	155 private:
a61af66fc99e Initial load duke parents: diff changeset	156 // 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	157 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	158 bool pop_local_slow(uint localBot, Age oldAge);
0 a61af66fc99e Initial load duke parents: diff changeset	159
a61af66fc99e Initial load duke parents: diff changeset	160 public:
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	161 typedef E element_type;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	162
0 a61af66fc99e Initial load duke parents: diff changeset	163 // Initializes the queue to empty.
a61af66fc99e Initial load duke parents: diff changeset	164 GenericTaskQueue();
a61af66fc99e Initial load duke parents: diff changeset	165
a61af66fc99e Initial load duke parents: diff changeset	166 void initialize();
a61af66fc99e Initial load duke parents: diff changeset	167
a61af66fc99e Initial load duke parents: diff changeset	168 // Push the task "t" on the queue. Returns "false" iff the queue is
a61af66fc99e Initial load duke parents: diff changeset	169 // full.
a61af66fc99e Initial load duke parents: diff changeset	170 inline bool push(E t);
a61af66fc99e Initial load duke parents: diff changeset	171
a61af66fc99e Initial load duke parents: diff changeset	172 // If succeeds in claiming a task (from the 'local' end, that is, the
a61af66fc99e Initial load duke parents: diff changeset	173 // most recently pushed task), returns "true" and sets "t" to that task.
a61af66fc99e Initial load duke parents: diff changeset	174 // Otherwise, the queue is empty and returns false.
a61af66fc99e Initial load duke parents: diff changeset	175 inline bool pop_local(E& t);
a61af66fc99e Initial load duke parents: diff changeset	176
a61af66fc99e Initial load duke parents: diff changeset	177 // If succeeds in claiming a task (from the 'global' end, that is, the
a61af66fc99e Initial load duke parents: diff changeset	178 // least recently pushed task), returns "true" and sets "t" to that task.
a61af66fc99e Initial load duke parents: diff changeset	179 // Otherwise, the queue is empty and returns false.
a61af66fc99e Initial load duke parents: diff changeset	180 bool pop_global(E& t);
a61af66fc99e Initial load duke parents: diff changeset	181
a61af66fc99e Initial load duke parents: diff changeset	182 // Delete any resource associated with the queue.
a61af66fc99e Initial load duke parents: diff changeset	183 ~GenericTaskQueue();
a61af66fc99e Initial load duke parents: diff changeset	184
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	185 // apply the closure to all elements in the task queue
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	186 void oops_do(OopClosure* f);
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	187
0 a61af66fc99e Initial load duke parents: diff changeset	188 private:
a61af66fc99e Initial load duke parents: diff changeset	189 // Element array.
a61af66fc99e Initial load duke parents: diff changeset	190 volatile E* _elems;
a61af66fc99e Initial load duke parents: diff changeset	191 };
a61af66fc99e Initial load duke parents: diff changeset	192
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	193 template<class E, unsigned int N>
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	194 GenericTaskQueue<E, N>::GenericTaskQueue() {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	195 assert(sizeof(Age) == sizeof(size_t), "Depends on this.");
0 a61af66fc99e Initial load duke parents: diff changeset	196 }
a61af66fc99e Initial load duke parents: diff changeset	197
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	198 template<class E, unsigned int N>
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	199 void GenericTaskQueue<E, N>::initialize() {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	200 _elems = NEW_C_HEAP_ARRAY(E, N);
0 a61af66fc99e Initial load duke parents: diff changeset	201 guarantee(_elems != NULL, "Allocation failed.");
a61af66fc99e Initial load duke parents: diff changeset	202 }
a61af66fc99e Initial load duke parents: diff changeset	203
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	204 template<class E, unsigned int N>
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	205 void GenericTaskQueue<E, N>::oops_do(OopClosure* f) {
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	206 // 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	207 uint iters = size();
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	208 uint index = _bottom;
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	209 for (uint i = 0; i < iters; ++i) {
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	210 index = decrement_index(index);
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	211 // tty->print_cr(" doing entry %d," INTPTR_T " -> " INTPTR_T,
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	212 // index, &_elems[index], _elems[index]);
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	213 E* t = (E*)&_elems[index]; // cast away volatility
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	214 oop* p = (oop*)t;
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	215 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	216 f->do_oop(p);
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	217 }
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	218 // tty->print_cr("END OopTaskQueue::oops_do");
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	219 }
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	220
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	221 template<class E, unsigned int N>
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	222 bool GenericTaskQueue<E, N>::push_slow(E t, uint dirty_n_elems) {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	223 if (dirty_n_elems == N - 1) {
0 a61af66fc99e Initial load duke parents: diff changeset	224 // 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	225 uint localBot = _bottom;
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	226 // g++ complains if the volatile result of the assignment is unused.
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	227 const_cast<E&>(_elems[localBot] = t);
1024 2c03ce058f55 6888847: TaskQueue needs release_store() for correctness on RMO machines bobv parents: 907 diff changeset	228 OrderAccess::release_store(&_bottom, increment_index(localBot));
0 a61af66fc99e Initial load duke parents: diff changeset	229 return true;
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	230 }
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	231 return false;
0 a61af66fc99e Initial load duke parents: diff changeset	232 }
a61af66fc99e Initial load duke parents: diff changeset	233
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	234 template<class E, unsigned int N>
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	235 bool GenericTaskQueue<E, N>::
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	236 pop_local_slow(uint localBot, Age oldAge) {
0 a61af66fc99e Initial load duke parents: diff changeset	237 // This queue was observed to contain exactly one element; either this
a61af66fc99e Initial load duke parents: diff changeset	238 // thread will claim it, or a competing "pop_global". In either case,
a61af66fc99e Initial load duke parents: diff changeset	239 // the queue will be logically empty afterwards. Create a new Age value
a61af66fc99e Initial load duke parents: diff changeset	240 // that represents the empty queue for the given value of "_bottom". (We
a61af66fc99e Initial load duke parents: diff changeset	241 // must also increment "tag" because of the case where "bottom == 1",
a61af66fc99e Initial load duke parents: diff changeset	242 // "top == 0". A pop_global could read the queue element in that case,
a61af66fc99e Initial load duke parents: diff changeset	243 // then have the owner thread do a pop followed by another push. Without
a61af66fc99e Initial load duke parents: diff changeset	244 // the incrementing of "tag", the pop_global's CAS could succeed,
a61af66fc99e Initial load duke parents: diff changeset	245 // 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	246 Age newAge((idx_t)localBot, oldAge.tag() + 1);
0 a61af66fc99e Initial load duke parents: diff changeset	247 // Perhaps a competing pop_global has already incremented "top", in which
a61af66fc99e Initial load duke parents: diff changeset	248 // case it wins the element.
a61af66fc99e Initial load duke parents: diff changeset	249 if (localBot == oldAge.top()) {
a61af66fc99e Initial load duke parents: diff changeset	250 // No competing pop_global has yet incremented "top"; we'll try to
a61af66fc99e Initial load duke parents: diff changeset	251 // install new_age, thus claiming the element.
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	252 Age tempAge = _age.cmpxchg(newAge, oldAge);
0 a61af66fc99e Initial load duke parents: diff changeset	253 if (tempAge == oldAge) {
a61af66fc99e Initial load duke parents: diff changeset	254 // We win.
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	255 assert(dirty_size(localBot, _age.top()) != N - 1, "sanity");
0 a61af66fc99e Initial load duke parents: diff changeset	256 return true;
a61af66fc99e Initial load duke parents: diff changeset	257 }
a61af66fc99e Initial load duke parents: diff changeset	258 }
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	259 // 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	260 // 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	261 // to become the canonical one.
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	262 _age.set(newAge);
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	263 assert(dirty_size(localBot, _age.top()) != N - 1, "sanity");
0 a61af66fc99e Initial load duke parents: diff changeset	264 return false;
a61af66fc99e Initial load duke parents: diff changeset	265 }
a61af66fc99e Initial load duke parents: diff changeset	266
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	267 template<class E, unsigned int N>
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	268 bool GenericTaskQueue<E, N>::pop_global(E& t) {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	269 Age oldAge = _age.get();
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	270 uint localBot = _bottom;
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	271 uint n_elems = size(localBot, oldAge.top());
0 a61af66fc99e Initial load duke parents: diff changeset	272 if (n_elems == 0) {
a61af66fc99e Initial load duke parents: diff changeset	273 return false;
a61af66fc99e Initial load duke parents: diff changeset	274 }
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	275
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	276 const_cast<E&>(t = _elems[oldAge.top()]);
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	277 Age newAge(oldAge);
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	278 newAge.increment();
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	279 Age resAge = _age.cmpxchg(newAge, oldAge);
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	280
0 a61af66fc99e Initial load duke parents: diff changeset	281 // Note that using "_bottom" here might fail, since a pop_local might
a61af66fc99e Initial load duke parents: diff changeset	282 // have decremented it.
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	283 assert(dirty_size(localBot, newAge.top()) != N - 1, "sanity");
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	284 return resAge == oldAge;
0 a61af66fc99e Initial load duke parents: diff changeset	285 }
a61af66fc99e Initial load duke parents: diff changeset	286
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	287 template<class E, unsigned int N>
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	288 GenericTaskQueue<E, N>::~GenericTaskQueue() {
0 a61af66fc99e Initial load duke parents: diff changeset	289 FREE_C_HEAP_ARRAY(E, _elems);
a61af66fc99e Initial load duke parents: diff changeset	290 }
a61af66fc99e Initial load duke parents: diff changeset	291
a61af66fc99e Initial load duke parents: diff changeset	292 // Inherits the typedef of "Task" from above.
a61af66fc99e Initial load duke parents: diff changeset	293 class TaskQueueSetSuper: public CHeapObj {
a61af66fc99e Initial load duke parents: diff changeset	294 protected:
a61af66fc99e Initial load duke parents: diff changeset	295 static int randomParkAndMiller(int* seed0);
a61af66fc99e Initial load duke parents: diff changeset	296 public:
a61af66fc99e Initial load duke parents: diff changeset	297 // Returns "true" if some TaskQueue in the set contains a task.
a61af66fc99e Initial load duke parents: diff changeset	298 virtual bool peek() = 0;
a61af66fc99e Initial load duke parents: diff changeset	299 };
a61af66fc99e Initial load duke parents: diff changeset	300
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	301 template<class T>
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	302 class GenericTaskQueueSet: public TaskQueueSetSuper {
0 a61af66fc99e Initial load duke parents: diff changeset	303 private:
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	304 uint _n;
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	305 T** _queues;
0 a61af66fc99e Initial load duke parents: diff changeset	306
a61af66fc99e Initial load duke parents: diff changeset	307 public:
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	308 typedef typename T::element_type E;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	309
0 a61af66fc99e Initial load duke parents: diff changeset	310 GenericTaskQueueSet(int n) : _n(n) {
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	311 typedef T* GenericTaskQueuePtr;
0 a61af66fc99e Initial load duke parents: diff changeset	312 _queues = NEW_C_HEAP_ARRAY(GenericTaskQueuePtr, n);
a61af66fc99e Initial load duke parents: diff changeset	313 for (int i = 0; i < n; i++) {
a61af66fc99e Initial load duke parents: diff changeset	314 _queues[i] = NULL;
a61af66fc99e Initial load duke parents: diff changeset	315 }
a61af66fc99e Initial load duke parents: diff changeset	316 }
a61af66fc99e Initial load duke parents: diff changeset	317
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	318 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	319 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	320 bool steal_best_of_all(uint queue_num, int* seed, E& t);
0 a61af66fc99e Initial load duke parents: diff changeset	321
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	322 void register_queue(uint i, T* q);
0 a61af66fc99e Initial load duke parents: diff changeset	323
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	324 T* queue(uint n);
0 a61af66fc99e Initial load duke parents: diff changeset	325
a61af66fc99e Initial load duke parents: diff changeset	326 // The thread with queue number "queue_num" (and whose random number seed
a61af66fc99e Initial load duke parents: diff changeset	327 // is at "seed") is trying to steal a task from some other queue. (It
a61af66fc99e Initial load duke parents: diff changeset	328 // may try several queues, according to some configuration parameter.)
a61af66fc99e Initial load duke parents: diff changeset	329 // If some steal succeeds, returns "true" and sets "t" the stolen task,
a61af66fc99e Initial load duke parents: diff changeset	330 // otherwise returns false.
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	331 bool steal(uint queue_num, int* seed, E& t);
0 a61af66fc99e Initial load duke parents: diff changeset	332
a61af66fc99e Initial load duke parents: diff changeset	333 bool peek();
a61af66fc99e Initial load duke parents: diff changeset	334 };
a61af66fc99e Initial load duke parents: diff changeset	335
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	336 template<class T> void
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	337 GenericTaskQueueSet<T>::register_queue(uint i, T* q) {
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	338 assert(i < _n, "index out of range.");
0 a61af66fc99e Initial load duke parents: diff changeset	339 _queues[i] = q;
a61af66fc99e Initial load duke parents: diff changeset	340 }
a61af66fc99e Initial load duke parents: diff changeset	341
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	342 template<class T> T*
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	343 GenericTaskQueueSet<T>::queue(uint i) {
0 a61af66fc99e Initial load duke parents: diff changeset	344 return _queues[i];
a61af66fc99e Initial load duke parents: diff changeset	345 }
a61af66fc99e Initial load duke parents: diff changeset	346
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	347 template<class T> bool
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	348 GenericTaskQueueSet<T>::steal(uint queue_num, int* seed, E& t) {
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	349 for (uint i = 0; i < 2 * _n; i++)
0 a61af66fc99e Initial load duke parents: diff changeset	350 if (steal_best_of_2(queue_num, seed, t))
a61af66fc99e Initial load duke parents: diff changeset	351 return true;
a61af66fc99e Initial load duke parents: diff changeset	352 return false;
a61af66fc99e Initial load duke parents: diff changeset	353 }
a61af66fc99e Initial load duke parents: diff changeset	354
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	355 template<class T> bool
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	356 GenericTaskQueueSet<T>::steal_best_of_all(uint queue_num, int* seed, E& t) {
0 a61af66fc99e Initial load duke parents: diff changeset	357 if (_n > 2) {
a61af66fc99e Initial load duke parents: diff changeset	358 int best_k;
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	359 uint best_sz = 0;
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	360 for (uint k = 0; k < _n; k++) {
0 a61af66fc99e Initial load duke parents: diff changeset	361 if (k == queue_num) continue;
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	362 uint sz = _queues[k]->size();
0 a61af66fc99e Initial load duke parents: diff changeset	363 if (sz > best_sz) {
a61af66fc99e Initial load duke parents: diff changeset	364 best_sz = sz;
a61af66fc99e Initial load duke parents: diff changeset	365 best_k = k;
a61af66fc99e Initial load duke parents: diff changeset	366 }
a61af66fc99e Initial load duke parents: diff changeset	367 }
a61af66fc99e Initial load duke parents: diff changeset	368 return best_sz > 0 && _queues[best_k]->pop_global(t);
a61af66fc99e Initial load duke parents: diff changeset	369 } else if (_n == 2) {
a61af66fc99e Initial load duke parents: diff changeset	370 // Just try the other one.
a61af66fc99e Initial load duke parents: diff changeset	371 int k = (queue_num + 1) % 2;
a61af66fc99e Initial load duke parents: diff changeset	372 return _queues[k]->pop_global(t);
a61af66fc99e Initial load duke parents: diff changeset	373 } else {
a61af66fc99e Initial load duke parents: diff changeset	374 assert(_n == 1, "can't be zero.");
a61af66fc99e Initial load duke parents: diff changeset	375 return false;
a61af66fc99e Initial load duke parents: diff changeset	376 }
a61af66fc99e Initial load duke parents: diff changeset	377 }
a61af66fc99e Initial load duke parents: diff changeset	378
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	379 template<class T> bool
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	380 GenericTaskQueueSet<T>::steal_1_random(uint queue_num, int* seed, E& t) {
0 a61af66fc99e Initial load duke parents: diff changeset	381 if (_n > 2) {
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	382 uint k = queue_num;
0 a61af66fc99e Initial load duke parents: diff changeset	383 while (k == queue_num) k = randomParkAndMiller(seed) % _n;
a61af66fc99e Initial load duke parents: diff changeset	384 return _queues[2]->pop_global(t);
a61af66fc99e Initial load duke parents: diff changeset	385 } else if (_n == 2) {
a61af66fc99e Initial load duke parents: diff changeset	386 // Just try the other one.
a61af66fc99e Initial load duke parents: diff changeset	387 int k = (queue_num + 1) % 2;
a61af66fc99e Initial load duke parents: diff changeset	388 return _queues[k]->pop_global(t);
a61af66fc99e Initial load duke parents: diff changeset	389 } else {
a61af66fc99e Initial load duke parents: diff changeset	390 assert(_n == 1, "can't be zero.");
a61af66fc99e Initial load duke parents: diff changeset	391 return false;
a61af66fc99e Initial load duke parents: diff changeset	392 }
a61af66fc99e Initial load duke parents: diff changeset	393 }
a61af66fc99e Initial load duke parents: diff changeset	394
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	395 template<class T> bool
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	396 GenericTaskQueueSet<T>::steal_best_of_2(uint queue_num, int* seed, E& t) {
0 a61af66fc99e Initial load duke parents: diff changeset	397 if (_n > 2) {
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	398 uint k1 = queue_num;
0 a61af66fc99e Initial load duke parents: diff changeset	399 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	400 uint k2 = queue_num;
0 a61af66fc99e Initial load duke parents: diff changeset	401 while (k2 == queue_num \|\| k2 == k1) k2 = randomParkAndMiller(seed) % _n;
a61af66fc99e Initial load duke parents: diff changeset	402 // Sample both and try the larger.
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	403 uint sz1 = _queues[k1]->size();
23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	404 uint sz2 = _queues[k2]->size();
0 a61af66fc99e Initial load duke parents: diff changeset	405 if (sz2 > sz1) return _queues[k2]->pop_global(t);
a61af66fc99e Initial load duke parents: diff changeset	406 else return _queues[k1]->pop_global(t);
a61af66fc99e Initial load duke parents: diff changeset	407 } else if (_n == 2) {
a61af66fc99e Initial load duke parents: diff changeset	408 // Just try the other one.
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	409 uint k = (queue_num + 1) % 2;
0 a61af66fc99e Initial load duke parents: diff changeset	410 return _queues[k]->pop_global(t);
a61af66fc99e Initial load duke parents: diff changeset	411 } else {
a61af66fc99e Initial load duke parents: diff changeset	412 assert(_n == 1, "can't be zero.");
a61af66fc99e Initial load duke parents: diff changeset	413 return false;
a61af66fc99e Initial load duke parents: diff changeset	414 }
a61af66fc99e Initial load duke parents: diff changeset	415 }
a61af66fc99e Initial load duke parents: diff changeset	416
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	417 template<class T>
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	418 bool GenericTaskQueueSet<T>::peek() {
0 a61af66fc99e Initial load duke parents: diff changeset	419 // Try all the queues.
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	420 for (uint j = 0; j < _n; j++) {
0 a61af66fc99e Initial load duke parents: diff changeset	421 if (_queues[j]->peek())
a61af66fc99e Initial load duke parents: diff changeset	422 return true;
a61af66fc99e Initial load duke parents: diff changeset	423 }
a61af66fc99e Initial load duke parents: diff changeset	424 return false;
a61af66fc99e Initial load duke parents: diff changeset	425 }
a61af66fc99e Initial load duke parents: diff changeset	426
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	427 // When to terminate from the termination protocol.
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	428 class TerminatorTerminator: public CHeapObj {
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	429 public:
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	430 virtual bool should_exit_termination() = 0;
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	431 };
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	432
0 a61af66fc99e Initial load duke parents: diff changeset	433 // A class to aid in the termination of a set of parallel tasks using
a61af66fc99e Initial load duke parents: diff changeset	434 // TaskQueueSet's for work stealing.
a61af66fc99e Initial load duke parents: diff changeset	435
546 05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	436 #undef TRACESPINNING
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	437
0 a61af66fc99e Initial load duke parents: diff changeset	438 class ParallelTaskTerminator: public StackObj {
a61af66fc99e Initial load duke parents: diff changeset	439 private:
a61af66fc99e Initial load duke parents: diff changeset	440 int _n_threads;
a61af66fc99e Initial load duke parents: diff changeset	441 TaskQueueSetSuper* _queue_set;
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	442 int _offered_termination;
0 a61af66fc99e Initial load duke parents: diff changeset	443
546 05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	444 #ifdef TRACESPINNING
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	445 static uint _total_yields;
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	446 static uint _total_spins;
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	447 static uint _total_peeks;
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	448 #endif
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	449
0 a61af66fc99e Initial load duke parents: diff changeset	450 bool peek_in_queue_set();
a61af66fc99e Initial load duke parents: diff changeset	451 protected:
a61af66fc99e Initial load duke parents: diff changeset	452 virtual void yield();
a61af66fc99e Initial load duke parents: diff changeset	453 void sleep(uint millis);
a61af66fc99e Initial load duke parents: diff changeset	454
a61af66fc99e Initial load duke parents: diff changeset	455 public:
a61af66fc99e Initial load duke parents: diff changeset	456
a61af66fc99e Initial load duke parents: diff changeset	457 // "n_threads" is the number of threads to be terminated. "queue_set" is a
a61af66fc99e Initial load duke parents: diff changeset	458 // queue sets of work queues of other threads.
a61af66fc99e Initial load duke parents: diff changeset	459 ParallelTaskTerminator(int n_threads, TaskQueueSetSuper* queue_set);
a61af66fc99e Initial load duke parents: diff changeset	460
a61af66fc99e Initial load duke parents: diff changeset	461 // The current thread has no work, and is ready to terminate if everyone
a61af66fc99e Initial load duke parents: diff changeset	462 // else is. If returns "true", all threads are terminated. If returns
a61af66fc99e Initial load duke parents: diff changeset	463 // "false", available work has been observed in one of the task queues,
a61af66fc99e Initial load duke parents: diff changeset	464 // so the global task is not complete.
342 37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	465 bool offer_termination() {
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	466 return offer_termination(NULL);
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	467 }
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	468
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	469 // 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	470 // method of the terminator parameter returns true. If terminator is
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	471 // NULL, then it is ignored.
37f87013dfd8 6711316: Open source the Garbage-First garbage collector ysr parents: 113 diff changeset	472 bool offer_termination(TerminatorTerminator* terminator);
0 a61af66fc99e Initial load duke parents: diff changeset	473
a61af66fc99e Initial load duke parents: diff changeset	474 // Reset the terminator, so that it may be reused again.
a61af66fc99e Initial load duke parents: diff changeset	475 // The caller is responsible for ensuring that this is done
a61af66fc99e Initial load duke parents: diff changeset	476 // in an MT-safe manner, once the previous round of use of
a61af66fc99e Initial load duke parents: diff changeset	477 // the terminator is finished.
a61af66fc99e Initial load duke parents: diff changeset	478 void reset_for_reuse();
a61af66fc99e Initial load duke parents: diff changeset	479
546 05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	480 #ifdef TRACESPINNING
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	481 static uint total_yields() { return _total_yields; }
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	482 static uint total_spins() { return _total_spins; }
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	483 static uint total_peeks() { return _total_peeks; }
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	484 static void print_termination_counts();
05c6d52fa7a9 6690928: Use spinning in combination with yields for workstealing termination. jmasa parents: 541 diff changeset	485 #endif
0 a61af66fc99e Initial load duke parents: diff changeset	486 };
a61af66fc99e Initial load duke parents: diff changeset	487
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	488 template<class E, unsigned int N> inline bool
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	489 GenericTaskQueue<E, N>::push(E t) {
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	490 uint localBot = _bottom;
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	491 assert((localBot >= 0) && (localBot < N), "_bottom out of range.");
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	492 idx_t top = _age.top();
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	493 uint dirty_n_elems = dirty_size(localBot, top);
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	494 assert(dirty_n_elems < N, "n_elems out of range.");
0 a61af66fc99e Initial load duke parents: diff changeset	495 if (dirty_n_elems < max_elems()) {
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	496 // g++ complains if the volatile result of the assignment is unused.
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	497 const_cast<E&>(_elems[localBot] = t);
1024 2c03ce058f55 6888847: TaskQueue needs release_store() for correctness on RMO machines bobv parents: 907 diff changeset	498 OrderAccess::release_store(&_bottom, increment_index(localBot));
0 a61af66fc99e Initial load duke parents: diff changeset	499 return true;
a61af66fc99e Initial load duke parents: diff changeset	500 } else {
a61af66fc99e Initial load duke parents: diff changeset	501 return push_slow(t, dirty_n_elems);
a61af66fc99e Initial load duke parents: diff changeset	502 }
a61af66fc99e Initial load duke parents: diff changeset	503 }
a61af66fc99e Initial load duke parents: diff changeset	504
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	505 template<class E, unsigned int N> inline bool
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	506 GenericTaskQueue<E, N>::pop_local(E& t) {
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	507 uint localBot = _bottom;
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	508 // This value cannot be N-1. That can only occur as a result of
0 a61af66fc99e Initial load duke parents: diff changeset	509 // the assignment to bottom in this method. If it does, this method
a61af66fc99e Initial load duke parents: diff changeset	510 // resets the size( to 0 before the next call (which is sequential,
a61af66fc99e Initial load duke parents: diff changeset	511 // since this is pop_local.)
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	512 uint dirty_n_elems = dirty_size(localBot, _age.top());
3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	513 assert(dirty_n_elems != N - 1, "Shouldn't be possible...");
0 a61af66fc99e Initial load duke parents: diff changeset	514 if (dirty_n_elems == 0) return false;
a61af66fc99e Initial load duke parents: diff changeset	515 localBot = decrement_index(localBot);
a61af66fc99e Initial load duke parents: diff changeset	516 _bottom = localBot;
a61af66fc99e Initial load duke parents: diff changeset	517 // This is necessary to prevent any read below from being reordered
a61af66fc99e Initial load duke parents: diff changeset	518 // before the store just above.
a61af66fc99e Initial load duke parents: diff changeset	519 OrderAccess::fence();
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	520 const_cast<E&>(t = _elems[localBot]);
0 a61af66fc99e Initial load duke parents: diff changeset	521 // This is a second read of "age"; the "size()" above is the first.
a61af66fc99e Initial load duke parents: diff changeset	522 // If there's still at least one element in the queue, based on the
a61af66fc99e Initial load duke parents: diff changeset	523 // "_bottom" and "age" we've read, then there can be no interference with
a61af66fc99e Initial load duke parents: diff changeset	524 // a "pop_global" operation, and we're done.
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	525 idx_t tp = _age.top(); // XXX
0 a61af66fc99e Initial load duke parents: diff changeset	526 if (size(localBot, tp) > 0) {
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	527 assert(dirty_size(localBot, tp) != N - 1, "sanity");
0 a61af66fc99e Initial load duke parents: diff changeset	528 return true;
a61af66fc99e Initial load duke parents: diff changeset	529 } else {
a61af66fc99e Initial load duke parents: diff changeset	530 // Otherwise, the queue contained exactly one element; we take the slow
a61af66fc99e Initial load duke parents: diff changeset	531 // path.
907 3ee342e25e57 6821693: 64-bit TaskQueue capacity still too small jcoomes parents: 845 diff changeset	532 return pop_local_slow(localBot, _age.get());
0 a61af66fc99e Initial load duke parents: diff changeset	533 }
a61af66fc99e Initial load duke parents: diff changeset	534 }
a61af66fc99e Initial load duke parents: diff changeset	535
a61af66fc99e Initial load duke parents: diff changeset	536 typedef oop Task;
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	537 typedef GenericTaskQueue<Task> OopTaskQueue;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	538 typedef GenericTaskQueueSet<OopTaskQueue> OopTaskQueueSet;
0 a61af66fc99e Initial load duke parents: diff changeset	539
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	540 #ifdef _MSC_VER
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	541 #pragma warning(push)
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	542 // warning C4522: multiple assignment operators specified
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	543 #pragma warning(disable:4522)
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	544 #endif
113 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 // 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	547 // 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	548 // 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	549 class StarTask {
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	550 void* _holder; // either union oop* or narrowOop*
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	551
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	552 enum { COMPRESSED_OOP_MASK = 1 };
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	553
113 ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	554 public:
845 df6caf649ff7 6700789: G1: Enable use of compressed oops with G1 heaps ysr parents: 579 diff changeset	555 StarTask(narrowOop* p) {
df6caf649ff7 6700789: G1: Enable use of compressed oops with G1 heaps ysr parents: 579 diff changeset	556 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	557 _holder = (void *)((uintptr_t)p \| COMPRESSED_OOP_MASK);
df6caf649ff7 6700789: G1: Enable use of compressed oops with G1 heaps ysr parents: 579 diff changeset	558 }
df6caf649ff7 6700789: G1: Enable use of compressed oops with G1 heaps ysr parents: 579 diff changeset	559 StarTask(oop* p) {
df6caf649ff7 6700789: G1: Enable use of compressed oops with G1 heaps ysr parents: 579 diff changeset	560 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	561 _holder = (void*)p;
df6caf649ff7 6700789: G1: Enable use of compressed oops with G1 heaps ysr parents: 579 diff changeset	562 }
113 ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	563 StarTask() { _holder = NULL; }
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	564 operator oop() { return (oop)_holder; }
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	565 operator narrowOop*() {
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	566 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	567 }
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	568
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	569 StarTask& operator=(const StarTask& t) {
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	570 _holder = t._holder;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	571 return *this;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	572 }
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	573 volatile StarTask& operator=(const volatile StarTask& t) volatile {
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	574 _holder = t._holder;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	575 return *this;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	576 }
113 ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	577
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	578 bool is_narrow() const {
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	579 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	580 }
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	581 };
ba764ed4b6f2 6420645: Create a vm that uses compressed oops for up to 32gb heapsizes coleenp parents: 0 diff changeset	582
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	583 class ObjArrayTask
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	584 {
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	585 public:
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	586 ObjArrayTask(oop o = NULL, int idx = 0): _obj(o), _index(idx) { }
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	587 ObjArrayTask(oop o, size_t idx): _obj(o), _index(int(idx)) {
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	588 assert(idx <= size_t(max_jint), "too big");
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	589 }
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	590 ObjArrayTask(const ObjArrayTask& t): _obj(t._obj), _index(t._index) { }
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	591
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	592 ObjArrayTask& operator =(const ObjArrayTask& t) {
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	593 _obj = t._obj;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	594 _index = t._index;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	595 return *this;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	596 }
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	597 volatile ObjArrayTask&
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	598 operator =(const volatile ObjArrayTask& t) volatile {
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	599 _obj = t._obj;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	600 _index = t._index;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	601 return *this;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	602 }
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	603
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	604 inline oop obj() const { return _obj; }
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	605 inline int index() const { return _index; }
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	606
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	607 DEBUG_ONLY(bool is_valid() const); // Tasks to be pushed/popped must be valid.
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	608
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	609 private:
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	610 oop _obj;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	611 int _index;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	612 };
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	613
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	614 #ifdef _MSC_VER
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	615 #pragma warning(pop)
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	616 #endif
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	617
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	618 typedef GenericTaskQueue<StarTask> OopStarTaskQueue;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	619 typedef GenericTaskQueueSet<OopStarTaskQueue> OopStarTaskQueueSet;
0 a61af66fc99e Initial load duke parents: diff changeset	620
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	621 typedef size_t RegionTask; // index for region
1311 2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	622 typedef GenericTaskQueue<RegionTask> RegionTaskQueue;
2a1472c30599 4396719: Mark Sweep stack overflow on deeply nested Object arrays jcoomes parents: 1284 diff changeset	623 typedef GenericTaskQueueSet<RegionTaskQueue> RegionTaskQueueSet;
0 a61af66fc99e Initial load duke parents: diff changeset	624
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	625 class RegionTaskQueueWithOverflow: public CHeapObj {
0 a61af66fc99e Initial load duke parents: diff changeset	626 protected:
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	627 RegionTaskQueue _region_queue;
81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	628 GrowableArray<RegionTask>* _overflow_stack;
0 a61af66fc99e Initial load duke parents: diff changeset	629
a61af66fc99e Initial load duke parents: diff changeset	630 public:
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	631 RegionTaskQueueWithOverflow() : _overflow_stack(NULL) {}
0 a61af66fc99e Initial load duke parents: diff changeset	632 // Initialize both stealable queue and overflow
a61af66fc99e Initial load duke parents: diff changeset	633 void initialize();
a61af66fc99e Initial load duke parents: diff changeset	634 // Save first to stealable queue and then to overflow
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	635 void save(RegionTask t);
0 a61af66fc99e Initial load duke parents: diff changeset	636 // Retrieve first from overflow and then from stealable queue
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	637 bool retrieve(RegionTask& region_index);
0 a61af66fc99e Initial load duke parents: diff changeset	638 // Retrieve from stealable queue
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	639 bool retrieve_from_stealable_queue(RegionTask& region_index);
0 a61af66fc99e Initial load duke parents: diff changeset	640 // Retrieve from overflow
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	641 bool retrieve_from_overflow(RegionTask& region_index);
0 a61af66fc99e Initial load duke parents: diff changeset	642 bool is_empty();
a61af66fc99e Initial load duke parents: diff changeset	643 bool stealable_is_empty();
a61af66fc99e Initial load duke parents: diff changeset	644 bool overflow_is_empty();
541 23673011938d 6787254: Work queue capacity can be increased substantially on some platforms ysr parents: 375 diff changeset	645 uint stealable_size() { return _region_queue.size(); }
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	646 RegionTaskQueue* task_queue() { return &_region_queue; }
0 a61af66fc99e Initial load duke parents: diff changeset	647 };
a61af66fc99e Initial load duke parents: diff changeset	648
375 81cd571500b0 6725697: par compact - rename class ChunkData to RegionData jcoomes parents: 356 diff changeset	649 #define USE_RegionTaskQueueWithOverflow

Mercurial > hg > graal-compiler

annotate src/share/vm/utilities/taskqueue.hpp @ 1311:2a1472c30599