Thu, 01 Jul 2010 21:40:45 -0700
6957084: simplify TaskQueue overflow handling
Reviewed-by: ysr, jmasa
1 /*
2 * Copyright (c) 2002, 2010, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
25 #include "incls/_precompiled.incl"
26 #include "incls/_psPromotionManager.cpp.incl"
28 PSPromotionManager** PSPromotionManager::_manager_array = NULL;
29 OopStarTaskQueueSet* PSPromotionManager::_stack_array_depth = NULL;
30 OopTaskQueueSet* PSPromotionManager::_stack_array_breadth = NULL;
31 PSOldGen* PSPromotionManager::_old_gen = NULL;
32 MutableSpace* PSPromotionManager::_young_space = NULL;
34 void PSPromotionManager::initialize() {
35 ParallelScavengeHeap* heap = (ParallelScavengeHeap*)Universe::heap();
36 assert(heap->kind() == CollectedHeap::ParallelScavengeHeap, "Sanity");
38 _old_gen = heap->old_gen();
39 _young_space = heap->young_gen()->to_space();
41 assert(_manager_array == NULL, "Attempt to initialize twice");
42 _manager_array = NEW_C_HEAP_ARRAY(PSPromotionManager*, ParallelGCThreads+1 );
43 guarantee(_manager_array != NULL, "Could not initialize promotion manager");
45 if (UseDepthFirstScavengeOrder) {
46 _stack_array_depth = new OopStarTaskQueueSet(ParallelGCThreads);
47 guarantee(_stack_array_depth != NULL, "Count not initialize promotion manager");
48 } else {
49 _stack_array_breadth = new OopTaskQueueSet(ParallelGCThreads);
50 guarantee(_stack_array_breadth != NULL, "Count not initialize promotion manager");
51 }
53 // Create and register the PSPromotionManager(s) for the worker threads.
54 for(uint i=0; i<ParallelGCThreads; i++) {
55 _manager_array[i] = new PSPromotionManager();
56 guarantee(_manager_array[i] != NULL, "Could not create PSPromotionManager");
57 if (UseDepthFirstScavengeOrder) {
58 stack_array_depth()->register_queue(i, _manager_array[i]->claimed_stack_depth());
59 } else {
60 stack_array_breadth()->register_queue(i, _manager_array[i]->claimed_stack_breadth());
61 }
62 }
64 // The VMThread gets its own PSPromotionManager, which is not available
65 // for work stealing.
66 _manager_array[ParallelGCThreads] = new PSPromotionManager();
67 guarantee(_manager_array[ParallelGCThreads] != NULL, "Could not create PSPromotionManager");
68 }
70 PSPromotionManager* PSPromotionManager::gc_thread_promotion_manager(int index) {
71 assert(index >= 0 && index < (int)ParallelGCThreads, "index out of range");
72 assert(_manager_array != NULL, "Sanity");
73 return _manager_array[index];
74 }
76 PSPromotionManager* PSPromotionManager::vm_thread_promotion_manager() {
77 assert(_manager_array != NULL, "Sanity");
78 return _manager_array[ParallelGCThreads];
79 }
81 void PSPromotionManager::pre_scavenge() {
82 ParallelScavengeHeap* heap = (ParallelScavengeHeap*)Universe::heap();
83 assert(heap->kind() == CollectedHeap::ParallelScavengeHeap, "Sanity");
85 _young_space = heap->young_gen()->to_space();
87 for(uint i=0; i<ParallelGCThreads+1; i++) {
88 manager_array(i)->reset();
89 }
90 }
92 void PSPromotionManager::post_scavenge() {
93 #if PS_PM_STATS
94 print_stats();
95 #endif // PS_PM_STATS
97 for (uint i = 0; i < ParallelGCThreads + 1; i++) {
98 PSPromotionManager* manager = manager_array(i);
99 if (UseDepthFirstScavengeOrder) {
100 assert(manager->claimed_stack_depth()->is_empty(), "should be empty");
101 } else {
102 assert(manager->claimed_stack_breadth()->is_empty(), "should be empty");
103 }
104 manager->flush_labs();
105 }
106 }
108 #if PS_PM_STATS
110 void
111 PSPromotionManager::print_stats(uint i) {
112 tty->print_cr("---- GC Worker %2d Stats", i);
113 tty->print_cr(" total pushes %8d", _total_pushes);
114 tty->print_cr(" masked pushes %8d", _masked_pushes);
115 tty->print_cr(" overflow pushes %8d", _overflow_pushes);
116 tty->print_cr(" max overflow length %8d", _max_overflow_length);
117 tty->print_cr("");
118 tty->print_cr(" arrays chunked %8d", _arrays_chunked);
119 tty->print_cr(" array chunks processed %8d", _array_chunks_processed);
120 tty->print_cr("");
121 tty->print_cr(" total steals %8d", _total_steals);
122 tty->print_cr(" masked steals %8d", _masked_steals);
123 tty->print_cr("");
124 }
126 void
127 PSPromotionManager::print_stats() {
128 tty->print_cr("== GC Tasks Stats (%s), GC %3d",
129 (UseDepthFirstScavengeOrder) ? "Depth-First" : "Breadth-First",
130 Universe::heap()->total_collections());
132 for (uint i = 0; i < ParallelGCThreads+1; ++i) {
133 PSPromotionManager* manager = manager_array(i);
134 manager->print_stats(i);
135 }
136 }
138 #endif // PS_PM_STATS
140 PSPromotionManager::PSPromotionManager() {
141 ParallelScavengeHeap* heap = (ParallelScavengeHeap*)Universe::heap();
142 assert(heap->kind() == CollectedHeap::ParallelScavengeHeap, "Sanity");
143 _depth_first = UseDepthFirstScavengeOrder;
145 // We set the old lab's start array.
146 _old_lab.set_start_array(old_gen()->start_array());
148 uint queue_size;
149 if (depth_first()) {
150 claimed_stack_depth()->initialize();
151 queue_size = claimed_stack_depth()->max_elems();
152 } else {
153 claimed_stack_breadth()->initialize();
154 queue_size = claimed_stack_breadth()->max_elems();
155 }
157 _totally_drain = (ParallelGCThreads == 1) || (GCDrainStackTargetSize == 0);
158 if (_totally_drain) {
159 _target_stack_size = 0;
160 } else {
161 // don't let the target stack size to be more than 1/4 of the entries
162 _target_stack_size = (uint) MIN2((uint) GCDrainStackTargetSize,
163 (uint) (queue_size / 4));
164 }
166 _array_chunk_size = ParGCArrayScanChunk;
167 // let's choose 1.5x the chunk size
168 _min_array_size_for_chunking = 3 * _array_chunk_size / 2;
170 reset();
171 }
173 void PSPromotionManager::reset() {
174 assert(stacks_empty(), "reset of non-empty stack");
176 // We need to get an assert in here to make sure the labs are always flushed.
178 ParallelScavengeHeap* heap = (ParallelScavengeHeap*)Universe::heap();
179 assert(heap->kind() == CollectedHeap::ParallelScavengeHeap, "Sanity");
181 // Do not prefill the LAB's, save heap wastage!
182 HeapWord* lab_base = young_space()->top();
183 _young_lab.initialize(MemRegion(lab_base, (size_t)0));
184 _young_gen_is_full = false;
186 lab_base = old_gen()->object_space()->top();
187 _old_lab.initialize(MemRegion(lab_base, (size_t)0));
188 _old_gen_is_full = false;
190 _prefetch_queue.clear();
192 #if PS_PM_STATS
193 _total_pushes = 0;
194 _masked_pushes = 0;
195 _overflow_pushes = 0;
196 _max_overflow_length = 0;
197 _arrays_chunked = 0;
198 _array_chunks_processed = 0;
199 _total_steals = 0;
200 _masked_steals = 0;
201 #endif // PS_PM_STATS
202 }
205 void PSPromotionManager::drain_stacks_depth(bool totally_drain) {
206 assert(depth_first(), "invariant");
207 assert(claimed_stack_depth()->overflow_stack() != NULL, "invariant");
208 totally_drain = totally_drain || _totally_drain;
210 #ifdef ASSERT
211 ParallelScavengeHeap* heap = (ParallelScavengeHeap*)Universe::heap();
212 assert(heap->kind() == CollectedHeap::ParallelScavengeHeap, "Sanity");
213 MutableSpace* to_space = heap->young_gen()->to_space();
214 MutableSpace* old_space = heap->old_gen()->object_space();
215 MutableSpace* perm_space = heap->perm_gen()->object_space();
216 #endif /* ASSERT */
218 OopStarTaskQueue* const tq = claimed_stack_depth();
219 do {
220 StarTask p;
222 // Drain overflow stack first, so other threads can steal from
223 // claimed stack while we work.
224 while (tq->pop_overflow(p)) {
225 process_popped_location_depth(p);
226 }
228 if (totally_drain) {
229 while (tq->pop_local(p)) {
230 process_popped_location_depth(p);
231 }
232 } else {
233 while (tq->size() > _target_stack_size && tq->pop_local(p)) {
234 process_popped_location_depth(p);
235 }
236 }
237 } while (totally_drain && !tq->taskqueue_empty() || !tq->overflow_empty());
239 assert(!totally_drain || tq->taskqueue_empty(), "Sanity");
240 assert(totally_drain || tq->size() <= _target_stack_size, "Sanity");
241 assert(tq->overflow_empty(), "Sanity");
242 }
244 void PSPromotionManager::drain_stacks_breadth(bool totally_drain) {
245 assert(!depth_first(), "invariant");
246 assert(claimed_stack_breadth()->overflow_stack() != NULL, "invariant");
247 totally_drain = totally_drain || _totally_drain;
249 #ifdef ASSERT
250 ParallelScavengeHeap* heap = (ParallelScavengeHeap*)Universe::heap();
251 assert(heap->kind() == CollectedHeap::ParallelScavengeHeap, "Sanity");
252 MutableSpace* to_space = heap->young_gen()->to_space();
253 MutableSpace* old_space = heap->old_gen()->object_space();
254 MutableSpace* perm_space = heap->perm_gen()->object_space();
255 #endif /* ASSERT */
257 OverflowTaskQueue<oop>* const tq = claimed_stack_breadth();
258 do {
259 oop obj;
261 // Drain overflow stack first, so other threads can steal from
262 // claimed stack while we work.
263 while (tq->pop_overflow(obj)) {
264 obj->copy_contents(this);
265 }
267 if (totally_drain) {
268 while (tq->pop_local(obj)) {
269 obj->copy_contents(this);
270 }
271 } else {
272 while (tq->size() > _target_stack_size && tq->pop_local(obj)) {
273 obj->copy_contents(this);
274 }
275 }
277 // If we could not find any other work, flush the prefetch queue
278 if (tq->is_empty()) {
279 flush_prefetch_queue();
280 }
281 } while (totally_drain && !tq->taskqueue_empty() || !tq->overflow_empty());
283 assert(!totally_drain || tq->taskqueue_empty(), "Sanity");
284 assert(totally_drain || tq->size() <= _target_stack_size, "Sanity");
285 assert(tq->overflow_empty(), "Sanity");
286 }
288 void PSPromotionManager::flush_labs() {
289 assert(stacks_empty(), "Attempt to flush lab with live stack");
291 // If either promotion lab fills up, we can flush the
292 // lab but not refill it, so check first.
293 assert(!_young_lab.is_flushed() || _young_gen_is_full, "Sanity");
294 if (!_young_lab.is_flushed())
295 _young_lab.flush();
297 assert(!_old_lab.is_flushed() || _old_gen_is_full, "Sanity");
298 if (!_old_lab.is_flushed())
299 _old_lab.flush();
301 // Let PSScavenge know if we overflowed
302 if (_young_gen_is_full) {
303 PSScavenge::set_survivor_overflow(true);
304 }
305 }
307 //
308 // This method is pretty bulky. It would be nice to split it up
309 // into smaller submethods, but we need to be careful not to hurt
310 // performance.
311 //
313 oop PSPromotionManager::copy_to_survivor_space(oop o, bool depth_first) {
314 assert(PSScavenge::should_scavenge(&o), "Sanity");
316 oop new_obj = NULL;
318 // NOTE! We must be very careful with any methods that access the mark
319 // in o. There may be multiple threads racing on it, and it may be forwarded
320 // at any time. Do not use oop methods for accessing the mark!
321 markOop test_mark = o->mark();
323 // The same test as "o->is_forwarded()"
324 if (!test_mark->is_marked()) {
325 bool new_obj_is_tenured = false;
326 size_t new_obj_size = o->size();
328 // Find the objects age, MT safe.
329 int age = (test_mark->has_displaced_mark_helper() /* o->has_displaced_mark() */) ?
330 test_mark->displaced_mark_helper()->age() : test_mark->age();
332 // Try allocating obj in to-space (unless too old)
333 if (age < PSScavenge::tenuring_threshold()) {
334 new_obj = (oop) _young_lab.allocate(new_obj_size);
335 if (new_obj == NULL && !_young_gen_is_full) {
336 // Do we allocate directly, or flush and refill?
337 if (new_obj_size > (YoungPLABSize / 2)) {
338 // Allocate this object directly
339 new_obj = (oop)young_space()->cas_allocate(new_obj_size);
340 } else {
341 // Flush and fill
342 _young_lab.flush();
344 HeapWord* lab_base = young_space()->cas_allocate(YoungPLABSize);
345 if (lab_base != NULL) {
346 _young_lab.initialize(MemRegion(lab_base, YoungPLABSize));
347 // Try the young lab allocation again.
348 new_obj = (oop) _young_lab.allocate(new_obj_size);
349 } else {
350 _young_gen_is_full = true;
351 }
352 }
353 }
354 }
356 // Otherwise try allocating obj tenured
357 if (new_obj == NULL) {
358 #ifndef PRODUCT
359 if (Universe::heap()->promotion_should_fail()) {
360 return oop_promotion_failed(o, test_mark);
361 }
362 #endif // #ifndef PRODUCT
364 new_obj = (oop) _old_lab.allocate(new_obj_size);
365 new_obj_is_tenured = true;
367 if (new_obj == NULL) {
368 if (!_old_gen_is_full) {
369 // Do we allocate directly, or flush and refill?
370 if (new_obj_size > (OldPLABSize / 2)) {
371 // Allocate this object directly
372 new_obj = (oop)old_gen()->cas_allocate(new_obj_size);
373 } else {
374 // Flush and fill
375 _old_lab.flush();
377 HeapWord* lab_base = old_gen()->cas_allocate(OldPLABSize);
378 if(lab_base != NULL) {
379 _old_lab.initialize(MemRegion(lab_base, OldPLABSize));
380 // Try the old lab allocation again.
381 new_obj = (oop) _old_lab.allocate(new_obj_size);
382 }
383 }
384 }
386 // This is the promotion failed test, and code handling.
387 // The code belongs here for two reasons. It is slightly
388 // different thatn the code below, and cannot share the
389 // CAS testing code. Keeping the code here also minimizes
390 // the impact on the common case fast path code.
392 if (new_obj == NULL) {
393 _old_gen_is_full = true;
394 return oop_promotion_failed(o, test_mark);
395 }
396 }
397 }
399 assert(new_obj != NULL, "allocation should have succeeded");
401 // Copy obj
402 Copy::aligned_disjoint_words((HeapWord*)o, (HeapWord*)new_obj, new_obj_size);
404 // Now we have to CAS in the header.
405 if (o->cas_forward_to(new_obj, test_mark)) {
406 // We won any races, we "own" this object.
407 assert(new_obj == o->forwardee(), "Sanity");
409 // Increment age if obj still in new generation. Now that
410 // we're dealing with a markOop that cannot change, it is
411 // okay to use the non mt safe oop methods.
412 if (!new_obj_is_tenured) {
413 new_obj->incr_age();
414 assert(young_space()->contains(new_obj), "Attempt to push non-promoted obj");
415 }
417 if (depth_first) {
418 // Do the size comparison first with new_obj_size, which we
419 // already have. Hopefully, only a few objects are larger than
420 // _min_array_size_for_chunking, and most of them will be arrays.
421 // So, the is->objArray() test would be very infrequent.
422 if (new_obj_size > _min_array_size_for_chunking &&
423 new_obj->is_objArray() &&
424 PSChunkLargeArrays) {
425 // we'll chunk it
426 #if PS_PM_STATS
427 ++_arrays_chunked;
428 #endif // PS_PM_STATS
429 oop* const masked_o = mask_chunked_array_oop(o);
430 push_depth(masked_o);
431 #if PS_PM_STATS
432 ++_masked_pushes;
433 #endif // PS_PM_STATS
434 } else {
435 // we'll just push its contents
436 new_obj->push_contents(this);
437 }
438 } else {
439 push_breadth(new_obj);
440 }
441 } else {
442 // We lost, someone else "owns" this object
443 guarantee(o->is_forwarded(), "Object must be forwarded if the cas failed.");
445 // Try to deallocate the space. If it was directly allocated we cannot
446 // deallocate it, so we have to test. If the deallocation fails,
447 // overwrite with a filler object.
448 if (new_obj_is_tenured) {
449 if (!_old_lab.unallocate_object(new_obj)) {
450 CollectedHeap::fill_with_object((HeapWord*) new_obj, new_obj_size);
451 }
452 } else if (!_young_lab.unallocate_object(new_obj)) {
453 CollectedHeap::fill_with_object((HeapWord*) new_obj, new_obj_size);
454 }
456 // don't update this before the unallocation!
457 new_obj = o->forwardee();
458 }
459 } else {
460 assert(o->is_forwarded(), "Sanity");
461 new_obj = o->forwardee();
462 }
464 #ifdef DEBUG
465 // This code must come after the CAS test, or it will print incorrect
466 // information.
467 if (TraceScavenge) {
468 gclog_or_tty->print_cr("{%s %s " PTR_FORMAT " -> " PTR_FORMAT " (" SIZE_FORMAT ")}",
469 PSScavenge::should_scavenge(&new_obj) ? "copying" : "tenuring",
470 new_obj->blueprint()->internal_name(), o, new_obj, new_obj->size());
471 }
472 #endif
474 return new_obj;
475 }
477 template <class T> void PSPromotionManager::process_array_chunk_work(
478 oop obj,
479 int start, int end) {
480 assert(start < end, "invariant");
481 T* const base = (T*)objArrayOop(obj)->base();
482 T* p = base + start;
483 T* const chunk_end = base + end;
484 while (p < chunk_end) {
485 if (PSScavenge::should_scavenge(p)) {
486 claim_or_forward_depth(p);
487 }
488 ++p;
489 }
490 }
492 void PSPromotionManager::process_array_chunk(oop old) {
493 assert(PSChunkLargeArrays, "invariant");
494 assert(old->is_objArray(), "invariant");
495 assert(old->is_forwarded(), "invariant");
497 #if PS_PM_STATS
498 ++_array_chunks_processed;
499 #endif // PS_PM_STATS
501 oop const obj = old->forwardee();
503 int start;
504 int const end = arrayOop(old)->length();
505 if (end > (int) _min_array_size_for_chunking) {
506 // we'll chunk more
507 start = end - _array_chunk_size;
508 assert(start > 0, "invariant");
509 arrayOop(old)->set_length(start);
510 push_depth(mask_chunked_array_oop(old));
511 #if PS_PM_STATS
512 ++_masked_pushes;
513 #endif // PS_PM_STATS
514 } else {
515 // this is the final chunk for this array
516 start = 0;
517 int const actual_length = arrayOop(obj)->length();
518 arrayOop(old)->set_length(actual_length);
519 }
521 if (UseCompressedOops) {
522 process_array_chunk_work<narrowOop>(obj, start, end);
523 } else {
524 process_array_chunk_work<oop>(obj, start, end);
525 }
526 }
528 oop PSPromotionManager::oop_promotion_failed(oop obj, markOop obj_mark) {
529 assert(_old_gen_is_full || PromotionFailureALot, "Sanity");
531 // Attempt to CAS in the header.
532 // This tests if the header is still the same as when
533 // this started. If it is the same (i.e., no forwarding
534 // pointer has been installed), then this thread owns
535 // it.
536 if (obj->cas_forward_to(obj, obj_mark)) {
537 // We won any races, we "own" this object.
538 assert(obj == obj->forwardee(), "Sanity");
540 if (depth_first()) {
541 obj->push_contents(this);
542 } else {
543 // Don't bother incrementing the age, just push
544 // onto the claimed_stack..
545 push_breadth(obj);
546 }
548 // Save the mark if needed
549 PSScavenge::oop_promotion_failed(obj, obj_mark);
550 } else {
551 // We lost, someone else "owns" this object
552 guarantee(obj->is_forwarded(), "Object must be forwarded if the cas failed.");
554 // No unallocation to worry about.
555 obj = obj->forwardee();
556 }
558 #ifdef DEBUG
559 if (TraceScavenge) {
560 gclog_or_tty->print_cr("{%s %s 0x%x (%d)}",
561 "promotion-failure",
562 obj->blueprint()->internal_name(),
563 obj, obj->size());
565 }
566 #endif
568 return obj;
569 }