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