1006 if (VerifyBeforeGC && heap->total_collections() >= VerifyGCStartAt) {
1007 HandleMark hm; // Discard invalid handles created during verification
1008 Universe::verify("Before GC");
1009 }
1010
1011 // Verify object start arrays
1012 if (VerifyObjectStartArray &&
1013 VerifyBeforeGC) {
1014 heap->old_gen()->verify_object_start_array();
1015 }
1016
1017 DEBUG_ONLY(mark_bitmap()->verify_clear();)
1018 DEBUG_ONLY(summary_data().verify_clear();)
1019
1020 ParCompactionManager::reset_all_bitmap_query_caches();
1021 }
1022
1023 void PSParallelCompact::post_compact()
1024 {
1025 GCTraceTime(Info, gc, phases) tm("Post Compact", &_gc_timer);
1026
1027 for (unsigned int id = old_space_id; id < last_space_id; ++id) {
1028 // Clear the marking bitmap, summary data and split info.
1029 clear_data_covering_space(SpaceId(id));
1030 // Update top(). Must be done after clearing the bitmap and summary data.
1031 _space_info[id].publish_new_top();
1032 }
1033
1034 MutableSpace* const eden_space = _space_info[eden_space_id].space();
1035 MutableSpace* const from_space = _space_info[from_space_id].space();
1036 MutableSpace* const to_space = _space_info[to_space_id].space();
1037
1038 ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
1039 bool eden_empty = eden_space->is_empty();
1040 if (!eden_empty) {
1041 eden_empty = absorb_live_data_from_eden(heap->size_policy(),
1042 heap->young_gen(), heap->old_gen());
1043 }
1044
1045 // Update heap occupancy information which is used as input to the soft ref
2400 // distribute them to the thread stacks. The iteration is done in reverse
2401 // order (high to low) so the regions will be removed in ascending order.
2402
2403 const ParallelCompactData& sd = PSParallelCompact::summary_data();
2404
2405 // id + 1 is used to test termination so unsigned can
2406 // be used with an old_space_id == 0.
2407 FillableRegionLogger region_logger;
2408 for (unsigned int id = to_space_id; id + 1 > old_space_id; --id) {
2409 SpaceInfo* const space_info = _space_info + id;
2410 MutableSpace* const space = space_info->space();
2411 HeapWord* const new_top = space_info->new_top();
2412
2413 const size_t beg_region = sd.addr_to_region_idx(space_info->dense_prefix());
2414 const size_t end_region =
2415 sd.addr_to_region_idx(sd.region_align_up(new_top));
2416
2417 for (size_t cur = end_region - 1; cur + 1 > beg_region; --cur) {
2418 if (sd.region(cur)->claim_unsafe()) {
2419 ParCompactionManager* cm = ParCompactionManager::manager_array(worker_id);
2420 cm->region_stack()->push(cur);
2421 region_logger.handle(cur);
2422 // Assign regions to tasks in round-robin fashion.
2423 if (++worker_id == parallel_gc_threads) {
2424 worker_id = 0;
2425 }
2426 }
2427 }
2428 region_logger.print_line();
2429 }
2430 }
2431
2432 class TaskQueue : StackObj {
2433 volatile uint _counter;
2434 uint _size;
2435 uint _insert_index;
2436 PSParallelCompact::UpdateDensePrefixTask* _backing_array;
2437 public:
2438 explicit TaskQueue(uint size) : _counter(0), _size(size), _insert_index(0), _backing_array(NULL) {
2439 _backing_array = NEW_C_HEAP_ARRAY(PSParallelCompact::UpdateDensePrefixTask, _size, mtGC);
2585
2586 static void compaction_with_stealing_work(ParallelTaskTerminator* terminator, uint worker_id) {
2587 assert(ParallelScavengeHeap::heap()->is_gc_active(), "called outside gc");
2588
2589 ParCompactionManager* cm =
2590 ParCompactionManager::gc_thread_compaction_manager(worker_id);
2591
2592 // Drain the stacks that have been preloaded with regions
2593 // that are ready to fill.
2594
2595 cm->drain_region_stacks();
2596
2597 guarantee(cm->region_stack()->is_empty(), "Not empty");
2598
2599 size_t region_index = 0;
2600
2601 while (true) {
2602 if (ParCompactionManager::steal(worker_id, region_index)) {
2603 PSParallelCompact::fill_and_update_region(cm, region_index);
2604 cm->drain_region_stacks();
2605 } else {
2606 if (terminator->offer_termination()) {
2607 break;
2608 }
2609 // Go around again.
2610 }
2611 }
2612 return;
2613 }
2614
2615 class UpdateDensePrefixAndCompactionTask: public AbstractGangTask {
2616 typedef AbstractRefProcTaskExecutor::ProcessTask ProcessTask;
2617 TaskQueue& _tq;
2618 TaskTerminator _terminator;
2619 uint _active_workers;
2620
2621 public:
2622 UpdateDensePrefixAndCompactionTask(TaskQueue& tq, uint active_workers) :
2623 AbstractGangTask("UpdateDensePrefixAndCompactionTask"),
2624 _tq(tq),
2639 // other threads.
2640 compaction_with_stealing_work(_terminator.terminator(), worker_id);
2641 }
2642 };
2643
2644 void PSParallelCompact::compact() {
2645 GCTraceTime(Info, gc, phases) tm("Compaction Phase", &_gc_timer);
2646
2647 ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
2648 PSOldGen* old_gen = heap->old_gen();
2649 old_gen->start_array()->reset();
2650 uint active_gc_threads = ParallelScavengeHeap::heap()->workers().active_workers();
2651
2652 // for [0..last_space_id)
2653 // for [0..active_gc_threads * PAR_OLD_DENSE_PREFIX_OVER_PARTITIONING)
2654 // push
2655 // push
2656 //
2657 // max push count is thus: last_space_id * (active_gc_threads * PAR_OLD_DENSE_PREFIX_OVER_PARTITIONING + 1)
2658 TaskQueue task_queue(last_space_id * (active_gc_threads * PAR_OLD_DENSE_PREFIX_OVER_PARTITIONING + 1));
2659 prepare_region_draining_tasks(active_gc_threads);
2660 enqueue_dense_prefix_tasks(task_queue, active_gc_threads);
2661
2662 {
2663 GCTraceTime(Trace, gc, phases) tm("Par Compact", &_gc_timer);
2664
2665 UpdateDensePrefixAndCompactionTask task(task_queue, active_gc_threads);
2666 ParallelScavengeHeap::heap()->workers().run_task(&task);
2667
2668 #ifdef ASSERT
2669 // Verify that all regions have been processed before the deferred updates.
2670 for (unsigned int id = old_space_id; id < last_space_id; ++id) {
2671 verify_complete(SpaceId(id));
2672 }
2673 #endif
2674 }
2675
2676 {
2677 // Update the deferred objects, if any. Any compaction manager can be used.
2678 GCTraceTime(Trace, gc, phases) tm("Deferred Updates", &_gc_timer);
2945 MutableSpace* const src_space = _space_info[src_space_id].space();
2946 HeapWord* const beg_addr = sd.region_to_addr(beg_region);
2947 assert(src_space->contains(beg_addr) || beg_addr == src_space->end(),
2948 "src_space_id does not match beg_addr");
2949 assert(src_space->contains(end_addr) || end_addr == src_space->end(),
2950 "src_space_id does not match end_addr");
2951 #endif // #ifdef ASSERT
2952
2953 RegionData* const beg = sd.region(beg_region);
2954 RegionData* const end = sd.addr_to_region_ptr(sd.region_align_up(end_addr));
2955
2956 // Regions up to new_top() are enqueued if they become available.
2957 HeapWord* const new_top = _space_info[src_space_id].new_top();
2958 RegionData* const enqueue_end =
2959 sd.addr_to_region_ptr(sd.region_align_up(new_top));
2960
2961 for (RegionData* cur = beg; cur < end; ++cur) {
2962 assert(cur->data_size() > 0, "region must have live data");
2963 cur->decrement_destination_count();
2964 if (cur < enqueue_end && cur->available() && cur->claim()) {
2965 cm->push_region(sd.region(cur));
2966 }
2967 }
2968 }
2969
2970 size_t PSParallelCompact::next_src_region(MoveAndUpdateClosure& closure,
2971 SpaceId& src_space_id,
2972 HeapWord*& src_space_top,
2973 HeapWord* end_addr)
2974 {
2975 typedef ParallelCompactData::RegionData RegionData;
2976
2977 ParallelCompactData& sd = PSParallelCompact::summary_data();
2978 const size_t region_size = ParallelCompactData::RegionSize;
2979
2980 size_t src_region_idx = 0;
2981
2982 // Skip empty regions (if any) up to the top of the space.
2983 HeapWord* const src_aligned_up = sd.region_align_up(end_addr);
2984 RegionData* src_region_ptr = sd.addr_to_region_ptr(src_aligned_up);
2985 HeapWord* const top_aligned_up = sd.region_align_up(src_space_top);
3023 "first live obj in the space must match the destination");
3024 assert(src_cp->partial_obj_size() == 0,
3025 "a space cannot begin with a partial obj");
3026
3027 src_space_id = SpaceId(space_id);
3028 src_space_top = space->top();
3029 const size_t src_region_idx = sd.region(src_cp);
3030 closure.set_source(sd.region_to_addr(src_region_idx));
3031 return src_region_idx;
3032 } else {
3033 assert(src_cp->data_size() == 0, "sanity");
3034 }
3035 }
3036 }
3037 } while (++space_id < last_space_id);
3038
3039 assert(false, "no source region was found");
3040 return 0;
3041 }
3042
3043 void PSParallelCompact::fill_region(ParCompactionManager* cm, size_t region_idx)
3044 {
3045 typedef ParMarkBitMap::IterationStatus IterationStatus;
3046 const size_t RegionSize = ParallelCompactData::RegionSize;
3047 ParMarkBitMap* const bitmap = mark_bitmap();
3048 ParallelCompactData& sd = summary_data();
3049 RegionData* const region_ptr = sd.region(region_idx);
3050
3051 // Get the items needed to construct the closure.
3052 HeapWord* dest_addr = sd.region_to_addr(region_idx);
3053 SpaceId dest_space_id = space_id(dest_addr);
3054 ObjectStartArray* start_array = _space_info[dest_space_id].start_array();
3055 HeapWord* new_top = _space_info[dest_space_id].new_top();
3056 assert(dest_addr < new_top, "sanity");
3057 const size_t words = MIN2(pointer_delta(new_top, dest_addr), RegionSize);
3058
3059 // Get the source region and related info.
3060 size_t src_region_idx = region_ptr->source_region();
3061 SpaceId src_space_id = space_id(sd.region_to_addr(src_region_idx));
3062 HeapWord* src_space_top = _space_info[src_space_id].space()->top();
3063
3064 MoveAndUpdateClosure closure(bitmap, cm, start_array, dest_addr, words);
3065 closure.set_source(first_src_addr(dest_addr, src_space_id, src_region_idx));
3066
3067 // Adjust src_region_idx to prepare for decrementing destination counts (the
3068 // destination count is not decremented when a region is copied to itself).
3069 if (src_region_idx == region_idx) {
3070 src_region_idx += 1;
3071 }
3072
3073 if (bitmap->is_unmarked(closure.source())) {
3074 // The first source word is in the middle of an object; copy the remainder
3075 // of the object or as much as will fit. The fact that pointer updates were
3076 // deferred will be noted when the object header is processed.
3077 HeapWord* const old_src_addr = closure.source();
3078 closure.copy_partial_obj();
3079 if (closure.is_full()) {
3080 decrement_destination_counts(cm, src_space_id, src_region_idx,
3081 closure.source());
3082 region_ptr->set_deferred_obj_addr(NULL);
3083 region_ptr->set_completed();
3084 return;
3085 }
3086
3087 HeapWord* const end_addr = sd.region_align_down(closure.source());
3088 if (sd.region_align_down(old_src_addr) != end_addr) {
3089 // The partial object was copied from more than one source region.
3090 decrement_destination_counts(cm, src_space_id, src_region_idx, end_addr);
3091
3092 // Move to the next source region, possibly switching spaces as well. All
3093 // args except end_addr may be modified.
3094 src_region_idx = next_src_region(closure, src_space_id, src_space_top,
3095 end_addr);
3096 }
3097 }
3098
3099 do {
3100 HeapWord* const cur_addr = closure.source();
3101 HeapWord* const end_addr = MIN2(sd.region_align_up(cur_addr + 1),
3102 src_space_top);
3103 IterationStatus status = bitmap->iterate(&closure, cur_addr, end_addr);
3112 HeapWord* const obj_end = bitmap->find_obj_end(obj_beg, range_end);
3113 if (obj_end < range_end) {
3114 // The end was found; the entire object will fit.
3115 status = closure.do_addr(obj_beg, bitmap->obj_size(obj_beg, obj_end));
3116 assert(status != ParMarkBitMap::would_overflow, "sanity");
3117 } else {
3118 // The end was not found; the object will not fit.
3119 assert(range_end < src_space_top, "obj cannot cross space boundary");
3120 status = ParMarkBitMap::would_overflow;
3121 }
3122 }
3123
3124 if (status == ParMarkBitMap::would_overflow) {
3125 // The last object did not fit. Note that interior oop updates were
3126 // deferred, then copy enough of the object to fill the region.
3127 region_ptr->set_deferred_obj_addr(closure.destination());
3128 status = closure.copy_until_full(); // copies from closure.source()
3129
3130 decrement_destination_counts(cm, src_space_id, src_region_idx,
3131 closure.source());
3132 region_ptr->set_completed();
3133 return;
3134 }
3135
3136 if (status == ParMarkBitMap::full) {
3137 decrement_destination_counts(cm, src_space_id, src_region_idx,
3138 closure.source());
3139 region_ptr->set_deferred_obj_addr(NULL);
3140 region_ptr->set_completed();
3141 return;
3142 }
3143
3144 decrement_destination_counts(cm, src_space_id, src_region_idx, end_addr);
3145
3146 // Move to the next source region, possibly switching spaces as well. All
3147 // args except end_addr may be modified.
3148 src_region_idx = next_src_region(closure, src_space_id, src_space_top,
3149 end_addr);
3150 } while (true);
3151 }
3152
3153 void PSParallelCompact::fill_blocks(size_t region_idx)
3154 {
3155 // Fill in the block table elements for the specified region. Each block
3156 // table element holds the number of live words in the region that are to the
3157 // left of the first object that starts in the block. Thus only blocks in
3158 // which an object starts need to be filled.
3159 //
3160 // The algorithm scans the section of the bitmap that corresponds to the
3161 // region, keeping a running total of the live words. When an object start is
3162 // found, if it's the first to start in the block that contains it, the
3163 // current total is written to the block table element.
3164 const size_t Log2BlockSize = ParallelCompactData::Log2BlockSize;
3165 const size_t Log2RegionSize = ParallelCompactData::Log2RegionSize;
3166 const size_t RegionSize = ParallelCompactData::RegionSize;
3167
3168 ParallelCompactData& sd = summary_data();
3169 const size_t partial_obj_size = sd.region(region_idx)->partial_obj_size();
3170 if (partial_obj_size >= RegionSize) {
3171 return; // No objects start in this region.
3172 }
3205 // We need a monotonically non-decreasing time in ms but
3206 // os::javaTimeMillis() does not guarantee monotonicity.
3207 jlong now = os::javaTimeNanos() / NANOSECS_PER_MILLISEC;
3208 jlong ret_val = now - _time_of_last_gc;
3209 // XXX See note in genCollectedHeap::millis_since_last_gc().
3210 if (ret_val < 0) {
3211 NOT_PRODUCT(log_warning(gc)("time warp: " JLONG_FORMAT, ret_val);)
3212 return 0;
3213 }
3214 return ret_val;
3215 }
3216
3217 void PSParallelCompact::reset_millis_since_last_gc() {
3218 // We need a monotonically non-decreasing time in ms but
3219 // os::javaTimeMillis() does not guarantee monotonicity.
3220 _time_of_last_gc = os::javaTimeNanos() / NANOSECS_PER_MILLISEC;
3221 }
3222
3223 ParMarkBitMap::IterationStatus MoveAndUpdateClosure::copy_until_full()
3224 {
3225 if (source() != destination()) {
3226 DEBUG_ONLY(PSParallelCompact::check_new_location(source(), destination());)
3227 Copy::aligned_conjoint_words(source(), destination(), words_remaining());
3228 }
3229 update_state(words_remaining());
3230 assert(is_full(), "sanity");
3231 return ParMarkBitMap::full;
3232 }
3233
3234 void MoveAndUpdateClosure::copy_partial_obj()
3235 {
3236 size_t words = words_remaining();
3237
3238 HeapWord* const range_end = MIN2(source() + words, bitmap()->region_end());
3239 HeapWord* const end_addr = bitmap()->find_obj_end(source(), range_end);
3240 if (end_addr < range_end) {
3241 words = bitmap()->obj_size(source(), end_addr);
3242 }
3243
3244 // This test is necessary; if omitted, the pointer updates to a partial object
3245 // that crosses the dense prefix boundary could be overwritten.
3246 if (source() != destination()) {
3247 DEBUG_ONLY(PSParallelCompact::check_new_location(source(), destination());)
3248 Copy::aligned_conjoint_words(source(), destination(), words);
3249 }
3250 update_state(words);
3251 }
3252
3253 ParMarkBitMapClosure::IterationStatus
3254 MoveAndUpdateClosure::do_addr(HeapWord* addr, size_t words) {
3255 assert(destination() != NULL, "sanity");
3256 assert(bitmap()->obj_size(addr) == words, "bad size");
3257
3258 _source = addr;
3259 assert(PSParallelCompact::summary_data().calc_new_pointer(source(), compaction_manager()) ==
3260 destination(), "wrong destination");
3261
3262 if (words > words_remaining()) {
3263 return ParMarkBitMap::would_overflow;
3264 }
3265
3266 // The start_array must be updated even if the object is not moving.
3267 if (_start_array != NULL) {
3268 _start_array->allocate_block(destination());
3269 }
3270
3271 if (destination() != source()) {
3272 DEBUG_ONLY(PSParallelCompact::check_new_location(source(), destination());)
3273 Copy::aligned_conjoint_words(source(), destination(), words);
3274 }
3275
3276 oop moved_oop = (oop) destination();
3277 compaction_manager()->update_contents(moved_oop);
3278 assert(oopDesc::is_oop_or_null(moved_oop), "Expected an oop or NULL at " PTR_FORMAT, p2i(moved_oop));
3279
3280 update_state(words);
3281 assert(destination() == (HeapWord*)moved_oop + moved_oop->size(), "sanity");
3282 return is_full() ? ParMarkBitMap::full : ParMarkBitMap::incomplete;
3283 }
3284
3285 UpdateOnlyClosure::UpdateOnlyClosure(ParMarkBitMap* mbm,
3286 ParCompactionManager* cm,
3287 PSParallelCompact::SpaceId space_id) :
3288 ParMarkBitMapClosure(mbm, cm),
3289 _space_id(space_id),
3290 _start_array(PSParallelCompact::start_array(space_id))
3291 {
3292 }
3293
3294 // Updates the references in the object to their new values.
3295 ParMarkBitMapClosure::IterationStatus
3296 UpdateOnlyClosure::do_addr(HeapWord* addr, size_t words) {
3297 do_addr(addr);
3298 return ParMarkBitMap::incomplete;
3299 }
3300
3301 FillClosure::FillClosure(ParCompactionManager* cm, PSParallelCompact::SpaceId space_id) :
3302 ParMarkBitMapClosure(PSParallelCompact::mark_bitmap(), cm),
|
1006 if (VerifyBeforeGC && heap->total_collections() >= VerifyGCStartAt) {
1007 HandleMark hm; // Discard invalid handles created during verification
1008 Universe::verify("Before GC");
1009 }
1010
1011 // Verify object start arrays
1012 if (VerifyObjectStartArray &&
1013 VerifyBeforeGC) {
1014 heap->old_gen()->verify_object_start_array();
1015 }
1016
1017 DEBUG_ONLY(mark_bitmap()->verify_clear();)
1018 DEBUG_ONLY(summary_data().verify_clear();)
1019
1020 ParCompactionManager::reset_all_bitmap_query_caches();
1021 }
1022
1023 void PSParallelCompact::post_compact()
1024 {
1025 GCTraceTime(Info, gc, phases) tm("Post Compact", &_gc_timer);
1026 ParCompactionManager::remove_all_shadow_regions();
1027
1028 for (unsigned int id = old_space_id; id < last_space_id; ++id) {
1029 // Clear the marking bitmap, summary data and split info.
1030 clear_data_covering_space(SpaceId(id));
1031 // Update top(). Must be done after clearing the bitmap and summary data.
1032 _space_info[id].publish_new_top();
1033 }
1034
1035 MutableSpace* const eden_space = _space_info[eden_space_id].space();
1036 MutableSpace* const from_space = _space_info[from_space_id].space();
1037 MutableSpace* const to_space = _space_info[to_space_id].space();
1038
1039 ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
1040 bool eden_empty = eden_space->is_empty();
1041 if (!eden_empty) {
1042 eden_empty = absorb_live_data_from_eden(heap->size_policy(),
1043 heap->young_gen(), heap->old_gen());
1044 }
1045
1046 // Update heap occupancy information which is used as input to the soft ref
2401 // distribute them to the thread stacks. The iteration is done in reverse
2402 // order (high to low) so the regions will be removed in ascending order.
2403
2404 const ParallelCompactData& sd = PSParallelCompact::summary_data();
2405
2406 // id + 1 is used to test termination so unsigned can
2407 // be used with an old_space_id == 0.
2408 FillableRegionLogger region_logger;
2409 for (unsigned int id = to_space_id; id + 1 > old_space_id; --id) {
2410 SpaceInfo* const space_info = _space_info + id;
2411 MutableSpace* const space = space_info->space();
2412 HeapWord* const new_top = space_info->new_top();
2413
2414 const size_t beg_region = sd.addr_to_region_idx(space_info->dense_prefix());
2415 const size_t end_region =
2416 sd.addr_to_region_idx(sd.region_align_up(new_top));
2417
2418 for (size_t cur = end_region - 1; cur + 1 > beg_region; --cur) {
2419 if (sd.region(cur)->claim_unsafe()) {
2420 ParCompactionManager* cm = ParCompactionManager::manager_array(worker_id);
2421 bool result = sd.region(cur)->mark_normal();
2422 assert(result, "Must succeed at this point.");
2423 cm->region_stack()->push(cur);
2424 region_logger.handle(cur);
2425 // Assign regions to tasks in round-robin fashion.
2426 if (++worker_id == parallel_gc_threads) {
2427 worker_id = 0;
2428 }
2429 }
2430 }
2431 region_logger.print_line();
2432 }
2433 }
2434
2435 class TaskQueue : StackObj {
2436 volatile uint _counter;
2437 uint _size;
2438 uint _insert_index;
2439 PSParallelCompact::UpdateDensePrefixTask* _backing_array;
2440 public:
2441 explicit TaskQueue(uint size) : _counter(0), _size(size), _insert_index(0), _backing_array(NULL) {
2442 _backing_array = NEW_C_HEAP_ARRAY(PSParallelCompact::UpdateDensePrefixTask, _size, mtGC);
2588
2589 static void compaction_with_stealing_work(ParallelTaskTerminator* terminator, uint worker_id) {
2590 assert(ParallelScavengeHeap::heap()->is_gc_active(), "called outside gc");
2591
2592 ParCompactionManager* cm =
2593 ParCompactionManager::gc_thread_compaction_manager(worker_id);
2594
2595 // Drain the stacks that have been preloaded with regions
2596 // that are ready to fill.
2597
2598 cm->drain_region_stacks();
2599
2600 guarantee(cm->region_stack()->is_empty(), "Not empty");
2601
2602 size_t region_index = 0;
2603
2604 while (true) {
2605 if (ParCompactionManager::steal(worker_id, region_index)) {
2606 PSParallelCompact::fill_and_update_region(cm, region_index);
2607 cm->drain_region_stacks();
2608 } else if (PSParallelCompact::steal_unavailable_region(cm, region_index)) {
2609 // Fill and update an unavailable region with the help of a shadow region
2610 PSParallelCompact::fill_and_update_shadow_region(cm, region_index);
2611 cm->drain_region_stacks();
2612 } else {
2613 if (terminator->offer_termination()) {
2614 break;
2615 }
2616 // Go around again.
2617 }
2618 }
2619 return;
2620 }
2621
2622 class UpdateDensePrefixAndCompactionTask: public AbstractGangTask {
2623 typedef AbstractRefProcTaskExecutor::ProcessTask ProcessTask;
2624 TaskQueue& _tq;
2625 TaskTerminator _terminator;
2626 uint _active_workers;
2627
2628 public:
2629 UpdateDensePrefixAndCompactionTask(TaskQueue& tq, uint active_workers) :
2630 AbstractGangTask("UpdateDensePrefixAndCompactionTask"),
2631 _tq(tq),
2646 // other threads.
2647 compaction_with_stealing_work(_terminator.terminator(), worker_id);
2648 }
2649 };
2650
2651 void PSParallelCompact::compact() {
2652 GCTraceTime(Info, gc, phases) tm("Compaction Phase", &_gc_timer);
2653
2654 ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
2655 PSOldGen* old_gen = heap->old_gen();
2656 old_gen->start_array()->reset();
2657 uint active_gc_threads = ParallelScavengeHeap::heap()->workers().active_workers();
2658
2659 // for [0..last_space_id)
2660 // for [0..active_gc_threads * PAR_OLD_DENSE_PREFIX_OVER_PARTITIONING)
2661 // push
2662 // push
2663 //
2664 // max push count is thus: last_space_id * (active_gc_threads * PAR_OLD_DENSE_PREFIX_OVER_PARTITIONING + 1)
2665 TaskQueue task_queue(last_space_id * (active_gc_threads * PAR_OLD_DENSE_PREFIX_OVER_PARTITIONING + 1));
2666 initialize_shadow_regions(active_gc_threads);
2667 prepare_region_draining_tasks(active_gc_threads);
2668 enqueue_dense_prefix_tasks(task_queue, active_gc_threads);
2669
2670 {
2671 GCTraceTime(Trace, gc, phases) tm("Par Compact", &_gc_timer);
2672
2673 UpdateDensePrefixAndCompactionTask task(task_queue, active_gc_threads);
2674 ParallelScavengeHeap::heap()->workers().run_task(&task);
2675
2676 #ifdef ASSERT
2677 // Verify that all regions have been processed before the deferred updates.
2678 for (unsigned int id = old_space_id; id < last_space_id; ++id) {
2679 verify_complete(SpaceId(id));
2680 }
2681 #endif
2682 }
2683
2684 {
2685 // Update the deferred objects, if any. Any compaction manager can be used.
2686 GCTraceTime(Trace, gc, phases) tm("Deferred Updates", &_gc_timer);
2953 MutableSpace* const src_space = _space_info[src_space_id].space();
2954 HeapWord* const beg_addr = sd.region_to_addr(beg_region);
2955 assert(src_space->contains(beg_addr) || beg_addr == src_space->end(),
2956 "src_space_id does not match beg_addr");
2957 assert(src_space->contains(end_addr) || end_addr == src_space->end(),
2958 "src_space_id does not match end_addr");
2959 #endif // #ifdef ASSERT
2960
2961 RegionData* const beg = sd.region(beg_region);
2962 RegionData* const end = sd.addr_to_region_ptr(sd.region_align_up(end_addr));
2963
2964 // Regions up to new_top() are enqueued if they become available.
2965 HeapWord* const new_top = _space_info[src_space_id].new_top();
2966 RegionData* const enqueue_end =
2967 sd.addr_to_region_ptr(sd.region_align_up(new_top));
2968
2969 for (RegionData* cur = beg; cur < end; ++cur) {
2970 assert(cur->data_size() > 0, "region must have live data");
2971 cur->decrement_destination_count();
2972 if (cur < enqueue_end && cur->available() && cur->claim()) {
2973 if (cur->mark_normal()) {
2974 cm->push_region(sd.region(cur));
2975 } else if (cur->mark_copied()) {
2976 // Try to copy the content of the shadow region back to its corresponding
2977 // heap region if the shadow region is filled. Otherwise, the GC thread
2978 // fills the shadow region will copy the data back (see
2979 // MoveAndUpdateShadowClosure::complete_region).
2980 copy_back(sd.region_to_addr(cur->shadow_region()), sd.region_to_addr(cur));
2981 ParCompactionManager::push_shadow_region_mt_safe(cur->shadow_region());
2982 cur->set_completed();
2983 }
2984 }
2985 }
2986 }
2987
2988 size_t PSParallelCompact::next_src_region(MoveAndUpdateClosure& closure,
2989 SpaceId& src_space_id,
2990 HeapWord*& src_space_top,
2991 HeapWord* end_addr)
2992 {
2993 typedef ParallelCompactData::RegionData RegionData;
2994
2995 ParallelCompactData& sd = PSParallelCompact::summary_data();
2996 const size_t region_size = ParallelCompactData::RegionSize;
2997
2998 size_t src_region_idx = 0;
2999
3000 // Skip empty regions (if any) up to the top of the space.
3001 HeapWord* const src_aligned_up = sd.region_align_up(end_addr);
3002 RegionData* src_region_ptr = sd.addr_to_region_ptr(src_aligned_up);
3003 HeapWord* const top_aligned_up = sd.region_align_up(src_space_top);
3041 "first live obj in the space must match the destination");
3042 assert(src_cp->partial_obj_size() == 0,
3043 "a space cannot begin with a partial obj");
3044
3045 src_space_id = SpaceId(space_id);
3046 src_space_top = space->top();
3047 const size_t src_region_idx = sd.region(src_cp);
3048 closure.set_source(sd.region_to_addr(src_region_idx));
3049 return src_region_idx;
3050 } else {
3051 assert(src_cp->data_size() == 0, "sanity");
3052 }
3053 }
3054 }
3055 } while (++space_id < last_space_id);
3056
3057 assert(false, "no source region was found");
3058 return 0;
3059 }
3060
3061 void PSParallelCompact::fill_region(ParCompactionManager* cm, MoveAndUpdateClosure& closure, size_t region_idx)
3062 {
3063 typedef ParMarkBitMap::IterationStatus IterationStatus;
3064 ParMarkBitMap* const bitmap = mark_bitmap();
3065 ParallelCompactData& sd = summary_data();
3066 RegionData* const region_ptr = sd.region(region_idx);
3067
3068 // Get the source region and related info.
3069 size_t src_region_idx = region_ptr->source_region();
3070 SpaceId src_space_id = space_id(sd.region_to_addr(src_region_idx));
3071 HeapWord* src_space_top = _space_info[src_space_id].space()->top();
3072 HeapWord* dest_addr = sd.region_to_addr(region_idx);
3073
3074 closure.set_source(first_src_addr(dest_addr, src_space_id, src_region_idx));
3075
3076 // Adjust src_region_idx to prepare for decrementing destination counts (the
3077 // destination count is not decremented when a region is copied to itself).
3078 if (src_region_idx == region_idx) {
3079 src_region_idx += 1;
3080 }
3081
3082 if (bitmap->is_unmarked(closure.source())) {
3083 // The first source word is in the middle of an object; copy the remainder
3084 // of the object or as much as will fit. The fact that pointer updates were
3085 // deferred will be noted when the object header is processed.
3086 HeapWord* const old_src_addr = closure.source();
3087 closure.copy_partial_obj();
3088 if (closure.is_full()) {
3089 decrement_destination_counts(cm, src_space_id, src_region_idx,
3090 closure.source());
3091 region_ptr->set_deferred_obj_addr(NULL);
3092 closure.complete_region(cm, dest_addr, region_ptr);
3093 return;
3094 }
3095
3096 HeapWord* const end_addr = sd.region_align_down(closure.source());
3097 if (sd.region_align_down(old_src_addr) != end_addr) {
3098 // The partial object was copied from more than one source region.
3099 decrement_destination_counts(cm, src_space_id, src_region_idx, end_addr);
3100
3101 // Move to the next source region, possibly switching spaces as well. All
3102 // args except end_addr may be modified.
3103 src_region_idx = next_src_region(closure, src_space_id, src_space_top,
3104 end_addr);
3105 }
3106 }
3107
3108 do {
3109 HeapWord* const cur_addr = closure.source();
3110 HeapWord* const end_addr = MIN2(sd.region_align_up(cur_addr + 1),
3111 src_space_top);
3112 IterationStatus status = bitmap->iterate(&closure, cur_addr, end_addr);
3121 HeapWord* const obj_end = bitmap->find_obj_end(obj_beg, range_end);
3122 if (obj_end < range_end) {
3123 // The end was found; the entire object will fit.
3124 status = closure.do_addr(obj_beg, bitmap->obj_size(obj_beg, obj_end));
3125 assert(status != ParMarkBitMap::would_overflow, "sanity");
3126 } else {
3127 // The end was not found; the object will not fit.
3128 assert(range_end < src_space_top, "obj cannot cross space boundary");
3129 status = ParMarkBitMap::would_overflow;
3130 }
3131 }
3132
3133 if (status == ParMarkBitMap::would_overflow) {
3134 // The last object did not fit. Note that interior oop updates were
3135 // deferred, then copy enough of the object to fill the region.
3136 region_ptr->set_deferred_obj_addr(closure.destination());
3137 status = closure.copy_until_full(); // copies from closure.source()
3138
3139 decrement_destination_counts(cm, src_space_id, src_region_idx,
3140 closure.source());
3141 closure.complete_region(cm, dest_addr, region_ptr);
3142 return;
3143 }
3144
3145 if (status == ParMarkBitMap::full) {
3146 decrement_destination_counts(cm, src_space_id, src_region_idx,
3147 closure.source());
3148 region_ptr->set_deferred_obj_addr(NULL);
3149 closure.complete_region(cm, dest_addr, region_ptr);
3150 return;
3151 }
3152
3153 decrement_destination_counts(cm, src_space_id, src_region_idx, end_addr);
3154
3155 // Move to the next source region, possibly switching spaces as well. All
3156 // args except end_addr may be modified.
3157 src_region_idx = next_src_region(closure, src_space_id, src_space_top,
3158 end_addr);
3159 } while (true);
3160 }
3161
3162 void PSParallelCompact::fill_and_update_region(ParCompactionManager* cm, size_t region_idx)
3163 {
3164 MoveAndUpdateClosure cl(mark_bitmap(), cm, region_idx);
3165 fill_region(cm, cl, region_idx);
3166 }
3167
3168 void PSParallelCompact::fill_and_update_shadow_region(ParCompactionManager* cm, size_t region_idx)
3169 {
3170 // Get a shadow region first
3171 ParallelCompactData& sd = summary_data();
3172 RegionData* const region_ptr = sd.region(region_idx);
3173 size_t shadow_region = ParCompactionManager::pop_shadow_region_mt_safe(region_ptr);
3174 // The InvalidShadow return value indicates the corresponding heap region is available,
3175 // so use MoveAndUpdateClosure to fill the normal region. Otherwise, use
3176 // MoveAndUpdateShadowClosure to fill the acquired shadow region.
3177 if (shadow_region == ParCompactionManager::InvalidShadow) {
3178 MoveAndUpdateClosure cl(mark_bitmap(), cm, region_idx);
3179 region_ptr->shadow_to_normal();
3180 return fill_region(cm, cl, region_idx);
3181 } else {
3182 MoveAndUpdateShadowClosure cl(mark_bitmap(), cm, region_idx, shadow_region);
3183 return fill_region(cm, cl, region_idx);
3184 }
3185 }
3186
3187 void PSParallelCompact::copy_back(HeapWord *shadow_addr, HeapWord *region_addr)
3188 {
3189 Copy::aligned_conjoint_words(shadow_addr, region_addr, _summary_data.RegionSize);
3190 }
3191
3192 bool PSParallelCompact::steal_unavailable_region(ParCompactionManager* cm, size_t ®ion_idx)
3193 {
3194 size_t next = cm->next_shadow_region();
3195 ParallelCompactData& sd = summary_data();
3196 size_t old_new_top = sd.addr_to_region_idx(_space_info[old_space_id].new_top());
3197 uint active_gc_threads = ParallelScavengeHeap::heap()->workers().active_workers();
3198
3199 while (next < old_new_top) {
3200 if (sd.region(next)->mark_shadow()) {
3201 region_idx = next;
3202 return true;
3203 }
3204 next = cm->move_next_shadow_region_by(active_gc_threads);
3205 }
3206
3207 return false;
3208 }
3209
3210 // The shadow region is an optimization to address region dependencies in full GC. The basic
3211 // idea is making more regions available by temporally storing their live objects in empty
3212 // shadow regions to resolve dependencies between them and the destination regions. Therefore,
3213 // GC threads need not wait destination regions to be available before processing sources.
3214 //
3215 // A typical workflow would be:
3216 // After draining its own stack and failing to steal from others, a GC worker would pick an
3217 // unavailable region (destination count > 0) and get a shadow region. Then the worker fills
3218 // the shadow region by copying live objects from source regions of the unavailable one. Once
3219 // the unavailable region becomes available, the data in the shadow region will be copied back.
3220 // Shadow regions are empty regions in the to-space and regions between top and end of other spaces.
3221 //
3222 // For more details, please refer to ยง4.2 of the VEE'19 paper:
3223 // Haoyu Li, Mingyu Wu, Binyu Zang, and Haibo Chen. 2019. ScissorGC: scalable and efficient
3224 // compaction for Java full garbage collection. In Proceedings of the 15th ACM SIGPLAN/SIGOPS
3225 // International Conference on Virtual Execution Environments (VEE 2019). ACM, New York, NY, USA,
3226 // 108-121. DOI: https://doi.org/10.1145/3313808.3313820
3227 void PSParallelCompact::initialize_shadow_regions(uint parallel_gc_threads)
3228 {
3229 const ParallelCompactData& sd = PSParallelCompact::summary_data();
3230
3231 for (unsigned int id = old_space_id; id < last_space_id; ++id) {
3232 SpaceInfo* const space_info = _space_info + id;
3233 MutableSpace* const space = space_info->space();
3234
3235 const size_t beg_region =
3236 sd.addr_to_region_idx(sd.region_align_up(MAX2(space_info->new_top(), space->top())));
3237 const size_t end_region =
3238 sd.addr_to_region_idx(sd.region_align_down(space->end()));
3239
3240 for (size_t cur = beg_region; cur < end_region; ++cur) {
3241 ParCompactionManager::push_shadow_region(cur);
3242 }
3243 }
3244
3245 size_t beg_region = sd.addr_to_region_idx(_space_info[old_space_id].dense_prefix());
3246 for (uint i = 0; i < parallel_gc_threads; i++) {
3247 ParCompactionManager *cm = ParCompactionManager::manager_array(i);
3248 cm->set_next_shadow_region(beg_region + i);
3249 }
3250 }
3251
3252 void PSParallelCompact::fill_blocks(size_t region_idx)
3253 {
3254 // Fill in the block table elements for the specified region. Each block
3255 // table element holds the number of live words in the region that are to the
3256 // left of the first object that starts in the block. Thus only blocks in
3257 // which an object starts need to be filled.
3258 //
3259 // The algorithm scans the section of the bitmap that corresponds to the
3260 // region, keeping a running total of the live words. When an object start is
3261 // found, if it's the first to start in the block that contains it, the
3262 // current total is written to the block table element.
3263 const size_t Log2BlockSize = ParallelCompactData::Log2BlockSize;
3264 const size_t Log2RegionSize = ParallelCompactData::Log2RegionSize;
3265 const size_t RegionSize = ParallelCompactData::RegionSize;
3266
3267 ParallelCompactData& sd = summary_data();
3268 const size_t partial_obj_size = sd.region(region_idx)->partial_obj_size();
3269 if (partial_obj_size >= RegionSize) {
3270 return; // No objects start in this region.
3271 }
3304 // We need a monotonically non-decreasing time in ms but
3305 // os::javaTimeMillis() does not guarantee monotonicity.
3306 jlong now = os::javaTimeNanos() / NANOSECS_PER_MILLISEC;
3307 jlong ret_val = now - _time_of_last_gc;
3308 // XXX See note in genCollectedHeap::millis_since_last_gc().
3309 if (ret_val < 0) {
3310 NOT_PRODUCT(log_warning(gc)("time warp: " JLONG_FORMAT, ret_val);)
3311 return 0;
3312 }
3313 return ret_val;
3314 }
3315
3316 void PSParallelCompact::reset_millis_since_last_gc() {
3317 // We need a monotonically non-decreasing time in ms but
3318 // os::javaTimeMillis() does not guarantee monotonicity.
3319 _time_of_last_gc = os::javaTimeNanos() / NANOSECS_PER_MILLISEC;
3320 }
3321
3322 ParMarkBitMap::IterationStatus MoveAndUpdateClosure::copy_until_full()
3323 {
3324 if (source() != copy_destination()) {
3325 DEBUG_ONLY(PSParallelCompact::check_new_location(source(), destination());)
3326 Copy::aligned_conjoint_words(source(), copy_destination(), words_remaining());
3327 }
3328 update_state(words_remaining());
3329 assert(is_full(), "sanity");
3330 return ParMarkBitMap::full;
3331 }
3332
3333 void MoveAndUpdateClosure::copy_partial_obj()
3334 {
3335 size_t words = words_remaining();
3336
3337 HeapWord* const range_end = MIN2(source() + words, bitmap()->region_end());
3338 HeapWord* const end_addr = bitmap()->find_obj_end(source(), range_end);
3339 if (end_addr < range_end) {
3340 words = bitmap()->obj_size(source(), end_addr);
3341 }
3342
3343 // This test is necessary; if omitted, the pointer updates to a partial object
3344 // that crosses the dense prefix boundary could be overwritten.
3345 if (source() != copy_destination()) {
3346 DEBUG_ONLY(PSParallelCompact::check_new_location(source(), destination());)
3347 Copy::aligned_conjoint_words(source(), copy_destination(), words);
3348 }
3349 update_state(words);
3350 }
3351
3352 void MoveAndUpdateClosure::complete_region(ParCompactionManager *cm, HeapWord *dest_addr,
3353 PSParallelCompact::RegionData *region_ptr) {
3354 assert(region_ptr->shadow_state() == ParallelCompactData::RegionData::NormalRegion, "Region should be finished");
3355 region_ptr->set_completed();
3356 }
3357
3358 ParMarkBitMapClosure::IterationStatus
3359 MoveAndUpdateClosure::do_addr(HeapWord* addr, size_t words) {
3360 assert(destination() != NULL, "sanity");
3361 assert(bitmap()->obj_size(addr) == words, "bad size");
3362
3363 _source = addr;
3364 assert(PSParallelCompact::summary_data().calc_new_pointer(source(), compaction_manager()) ==
3365 destination(), "wrong destination");
3366
3367 if (words > words_remaining()) {
3368 return ParMarkBitMap::would_overflow;
3369 }
3370
3371 // The start_array must be updated even if the object is not moving.
3372 if (_start_array != NULL) {
3373 _start_array->allocate_block(destination());
3374 }
3375
3376 if (copy_destination() != source()) {
3377 DEBUG_ONLY(PSParallelCompact::check_new_location(source(), destination());)
3378 Copy::aligned_conjoint_words(source(), copy_destination(), words);
3379 }
3380
3381 oop moved_oop = (oop) copy_destination();
3382 compaction_manager()->update_contents(moved_oop);
3383 assert(oopDesc::is_oop_or_null(moved_oop), "Expected an oop or NULL at " PTR_FORMAT, p2i(moved_oop));
3384
3385 update_state(words);
3386 assert(copy_destination() == (HeapWord*)moved_oop + moved_oop->size(), "sanity");
3387 return is_full() ? ParMarkBitMap::full : ParMarkBitMap::incomplete;
3388 }
3389
3390 void MoveAndUpdateShadowClosure::complete_region(ParCompactionManager *cm, HeapWord *dest_addr,
3391 PSParallelCompact::RegionData *region_ptr) {
3392 assert(region_ptr->shadow_state() == ParallelCompactData::RegionData::ShadowRegion, "Region should be shadow");
3393 // Record the shadow region index
3394 region_ptr->set_shadow_region(_shadow);
3395 // Mark the shadow region as filled to indicate the data is ready to be
3396 // copied back
3397 region_ptr->mark_filled();
3398 // Try to copy the content of the shadow region back to its corresponding
3399 // heap region if available; the GC thread that decreases the destination
3400 // count to zero will do the copying otherwise (see
3401 // PSParallelCompact::decrement_destination_counts).
3402 if (((region_ptr->available() && region_ptr->claim()) || region_ptr->claimed()) && region_ptr->mark_copied()) {
3403 region_ptr->set_completed();
3404 PSParallelCompact::copy_back(PSParallelCompact::summary_data().region_to_addr(_shadow), dest_addr);
3405 ParCompactionManager::push_shadow_region_mt_safe(_shadow);
3406 }
3407 }
3408
3409 UpdateOnlyClosure::UpdateOnlyClosure(ParMarkBitMap* mbm,
3410 ParCompactionManager* cm,
3411 PSParallelCompact::SpaceId space_id) :
3412 ParMarkBitMapClosure(mbm, cm),
3413 _space_id(space_id),
3414 _start_array(PSParallelCompact::start_array(space_id))
3415 {
3416 }
3417
3418 // Updates the references in the object to their new values.
3419 ParMarkBitMapClosure::IterationStatus
3420 UpdateOnlyClosure::do_addr(HeapWord* addr, size_t words) {
3421 do_addr(addr);
3422 return ParMarkBitMap::incomplete;
3423 }
3424
3425 FillClosure::FillClosure(ParCompactionManager* cm, PSParallelCompact::SpaceId space_id) :
3426 ParMarkBitMapClosure(PSParallelCompact::mark_bitmap(), cm),
|