| /* |
| * Copyright (c) 2016, 2017, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| * |
| */ |
| |
| #include "precompiled.hpp" |
| #include "gc/g1/g1CollectedHeap.inline.hpp" |
| #include "gc/g1/g1ConcurrentMark.inline.hpp" |
| #include "gc/g1/g1CardLiveData.inline.hpp" |
| #include "gc/g1/suspendibleThreadSet.hpp" |
| #include "gc/shared/workgroup.hpp" |
| #include "logging/log.hpp" |
| #include "memory/universe.hpp" |
| #include "runtime/atomic.hpp" |
| #include "runtime/globals.hpp" |
| #include "runtime/os.hpp" |
| #include "utilities/align.hpp" |
| #include "utilities/bitMap.inline.hpp" |
| #include "utilities/debug.hpp" |
| |
| G1CardLiveData::G1CardLiveData() : |
| _max_capacity(0), |
| _cards_per_region(0), |
| _gc_timestamp_at_create(0), |
| _live_regions(NULL), |
| _live_regions_size_in_bits(0), |
| _live_cards(NULL), |
| _live_cards_size_in_bits(0) { |
| } |
| |
| G1CardLiveData::~G1CardLiveData() { |
| free_large_bitmap(_live_cards, _live_cards_size_in_bits); |
| free_large_bitmap(_live_regions, _live_regions_size_in_bits); |
| } |
| |
| G1CardLiveData::bm_word_t* G1CardLiveData::allocate_large_bitmap(size_t size_in_bits) { |
| size_t size_in_words = BitMap::calc_size_in_words(size_in_bits); |
| |
| bm_word_t* map = MmapArrayAllocator<bm_word_t>::allocate(size_in_words, mtGC); |
| |
| return map; |
| } |
| |
| void G1CardLiveData::free_large_bitmap(bm_word_t* bitmap, size_t size_in_bits) { |
| MmapArrayAllocator<bm_word_t>::free(bitmap, BitMap::calc_size_in_words(size_in_bits)); |
| } |
| |
| void G1CardLiveData::initialize(size_t max_capacity, uint num_max_regions) { |
| assert(max_capacity % num_max_regions == 0, |
| "Given capacity must be evenly divisible by region size."); |
| size_t region_size = max_capacity / num_max_regions; |
| assert(region_size % (G1SATBCardTableModRefBS::card_size * BitsPerWord) == 0, |
| "Region size must be evenly divisible by area covered by a single word."); |
| _max_capacity = max_capacity; |
| _cards_per_region = region_size / G1SATBCardTableModRefBS::card_size; |
| |
| _live_regions_size_in_bits = live_region_bitmap_size_in_bits(); |
| _live_regions = allocate_large_bitmap(_live_regions_size_in_bits); |
| _live_cards_size_in_bits = live_card_bitmap_size_in_bits(); |
| _live_cards = allocate_large_bitmap(_live_cards_size_in_bits); |
| } |
| |
| void G1CardLiveData::pretouch() { |
| live_cards_bm().pretouch(); |
| live_regions_bm().pretouch(); |
| } |
| |
| size_t G1CardLiveData::live_region_bitmap_size_in_bits() const { |
| return _max_capacity / (_cards_per_region << G1SATBCardTableModRefBS::card_shift); |
| } |
| |
| size_t G1CardLiveData::live_card_bitmap_size_in_bits() const { |
| return _max_capacity >> G1SATBCardTableModRefBS::card_shift; |
| } |
| |
| // Helper class that provides functionality to generate the Live Data Count |
| // information. |
| class G1CardLiveDataHelper VALUE_OBJ_CLASS_SPEC { |
| private: |
| BitMapView _region_bm; |
| BitMapView _card_bm; |
| |
| // The card number of the bottom of the G1 heap. |
| // Used in biasing indices into accounting card bitmaps. |
| BitMap::idx_t _heap_card_bias; |
| |
| // Utility routine to set an exclusive range of bits on the given |
| // bitmap, optimized for very small ranges. |
| // There must be at least one bit to set. |
| void set_card_bitmap_range(BitMap::idx_t start_idx, |
| BitMap::idx_t end_idx) { |
| |
| // Set the exclusive bit range [start_idx, end_idx). |
| assert((end_idx - start_idx) > 0, "at least one bit"); |
| |
| // For small ranges use a simple loop; otherwise use set_range. |
| // The range is made up of the cards that are spanned by an object/mem |
| // region so 8 cards will allow up to object sizes up to 4K to be handled |
| // using the loop. |
| if ((end_idx - start_idx) <= 8) { |
| for (BitMap::idx_t i = start_idx; i < end_idx; i += 1) { |
| _card_bm.set_bit(i); |
| } |
| } else { |
| _card_bm.set_range(start_idx, end_idx); |
| } |
| } |
| |
| // We cache the last mark set. This avoids setting the same bit multiple times. |
| // This is particularly interesting for dense bitmaps, as this avoids doing |
| // lots of work most of the time. |
| BitMap::idx_t _last_marked_bit_idx; |
| |
| void clear_card_bitmap_range(HeapWord* start, HeapWord* end) { |
| BitMap::idx_t start_idx = card_live_bitmap_index_for(start); |
| BitMap::idx_t end_idx = card_live_bitmap_index_for(align_up(end, CardTableModRefBS::card_size)); |
| |
| _card_bm.clear_range(start_idx, end_idx); |
| } |
| |
| // Mark the card liveness bitmap for the object spanning from start to end. |
| void mark_card_bitmap_range(HeapWord* start, HeapWord* end) { |
| BitMap::idx_t start_idx = card_live_bitmap_index_for(start); |
| BitMap::idx_t end_idx = card_live_bitmap_index_for(align_up(end, CardTableModRefBS::card_size)); |
| |
| assert((end_idx - start_idx) > 0, "Trying to mark zero sized range."); |
| |
| if (start_idx == _last_marked_bit_idx) { |
| start_idx++; |
| } |
| if (start_idx == end_idx) { |
| return; |
| } |
| |
| // Set the bits in the card bitmap for the cards spanned by this object. |
| set_card_bitmap_range(start_idx, end_idx); |
| _last_marked_bit_idx = end_idx - 1; |
| } |
| |
| void reset_mark_cache() { |
| _last_marked_bit_idx = (BitMap::idx_t)-1; |
| } |
| |
| public: |
| // Returns the index in the per-card liveness count bitmap |
| // for the given address |
| inline BitMap::idx_t card_live_bitmap_index_for(HeapWord* addr) { |
| // Below, the term "card num" means the result of shifting an address |
| // by the card shift -- address 0 corresponds to card number 0. One |
| // must subtract the card num of the bottom of the heap to obtain a |
| // card table index. |
| BitMap::idx_t card_num = uintptr_t(addr) >> CardTableModRefBS::card_shift; |
| return card_num - _heap_card_bias; |
| } |
| |
| // Takes a region that's not empty (i.e., it has at least one |
| // live object in it and sets its corresponding bit on the region |
| // bitmap to 1. |
| void set_bit_for_region(HeapRegion* hr) { |
| _region_bm.par_set_bit(hr->hrm_index()); |
| } |
| |
| void reset_live_data(HeapRegion* hr) { |
| clear_card_bitmap_range(hr->next_top_at_mark_start(), hr->end()); |
| } |
| |
| // Mark the range of bits covered by allocations done since the last marking |
| // in the given heap region, i.e. from NTAMS to top of the given region. |
| // Returns if there has been some allocation in this region since the last marking. |
| bool mark_allocated_since_marking(HeapRegion* hr) { |
| reset_mark_cache(); |
| |
| HeapWord* ntams = hr->next_top_at_mark_start(); |
| HeapWord* top = hr->top(); |
| |
| assert(hr->bottom() <= ntams && ntams <= hr->end(), "Preconditions."); |
| |
| // Mark the allocated-since-marking portion... |
| if (ntams < top) { |
| mark_card_bitmap_range(ntams, top); |
| return true; |
| } else { |
| return false; |
| } |
| } |
| |
| // Mark the range of bits covered by live objects on the mark bitmap between |
| // bottom and NTAMS of the given region. |
| // Returns the number of live bytes marked within that area for the given |
| // heap region. |
| size_t mark_marked_during_marking(G1CMBitMap* mark_bitmap, HeapRegion* hr) { |
| reset_mark_cache(); |
| |
| size_t marked_bytes = 0; |
| |
| HeapWord* ntams = hr->next_top_at_mark_start(); |
| HeapWord* start = hr->bottom(); |
| |
| if (ntams <= start) { |
| // Skip empty regions. |
| return 0; |
| } |
| if (hr->is_humongous()) { |
| HeapRegion* start_region = hr->humongous_start_region(); |
| if (mark_bitmap->is_marked(start_region->bottom())) { |
| mark_card_bitmap_range(start, hr->top()); |
| return pointer_delta(hr->top(), start, 1); |
| } else { |
| // Humongous start object was actually dead. |
| return 0; |
| } |
| } |
| |
| assert(start <= hr->end() && start <= ntams && ntams <= hr->end(), |
| "Preconditions not met - " |
| "start: " PTR_FORMAT ", ntams: " PTR_FORMAT ", end: " PTR_FORMAT, |
| p2i(start), p2i(ntams), p2i(hr->end())); |
| |
| // Find the first marked object at or after "start". |
| start = mark_bitmap->get_next_marked_addr(start, ntams); |
| while (start < ntams) { |
| oop obj = oop(start); |
| size_t obj_size = obj->size(); |
| HeapWord* obj_end = start + obj_size; |
| |
| assert(obj_end <= hr->end(), "Humongous objects must have been handled elsewhere."); |
| |
| mark_card_bitmap_range(start, obj_end); |
| |
| // Add the size of this object to the number of marked bytes. |
| marked_bytes += obj_size * HeapWordSize; |
| |
| // Find the next marked object after this one. |
| start = mark_bitmap->get_next_marked_addr(obj_end, ntams); |
| } |
| |
| return marked_bytes; |
| } |
| |
| G1CardLiveDataHelper(G1CardLiveData* live_data, HeapWord* base_address) : |
| _region_bm(live_data->live_regions_bm()), |
| _card_bm(live_data->live_cards_bm()) { |
| // Calculate the card number for the bottom of the heap. Used |
| // in biasing indexes into the accounting card bitmaps. |
| _heap_card_bias = |
| uintptr_t(base_address) >> CardTableModRefBS::card_shift; |
| } |
| }; |
| |
| class G1CreateCardLiveDataTask: public AbstractGangTask { |
| // Aggregate the counting data that was constructed concurrently |
| // with marking. |
| class G1CreateLiveDataClosure : public HeapRegionClosure { |
| G1CardLiveDataHelper _helper; |
| |
| G1CMBitMap* _mark_bitmap; |
| |
| G1ConcurrentMark* _cm; |
| public: |
| G1CreateLiveDataClosure(G1CollectedHeap* g1h, |
| G1ConcurrentMark* cm, |
| G1CMBitMap* mark_bitmap, |
| G1CardLiveData* live_data) : |
| HeapRegionClosure(), |
| _helper(live_data, g1h->reserved_region().start()), |
| _mark_bitmap(mark_bitmap), |
| _cm(cm) { } |
| |
| bool doHeapRegion(HeapRegion* hr) { |
| size_t marked_bytes = _helper.mark_marked_during_marking(_mark_bitmap, hr); |
| if (marked_bytes > 0) { |
| hr->add_to_marked_bytes(marked_bytes); |
| } |
| |
| return (_cm->do_yield_check() && _cm->has_aborted()); |
| } |
| }; |
| |
| G1ConcurrentMark* _cm; |
| G1CardLiveData* _live_data; |
| HeapRegionClaimer _hr_claimer; |
| |
| public: |
| G1CreateCardLiveDataTask(G1CMBitMap* bitmap, |
| G1CardLiveData* live_data, |
| uint n_workers) : |
| AbstractGangTask("G1 Create Live Data"), |
| _live_data(live_data), |
| _hr_claimer(n_workers) { |
| } |
| |
| void work(uint worker_id) { |
| SuspendibleThreadSetJoiner sts_join; |
| |
| G1CollectedHeap* g1h = G1CollectedHeap::heap(); |
| G1ConcurrentMark* cm = g1h->concurrent_mark(); |
| G1CreateLiveDataClosure cl(g1h, cm, cm->nextMarkBitMap(), _live_data); |
| g1h->heap_region_par_iterate(&cl, worker_id, &_hr_claimer); |
| } |
| }; |
| |
| void G1CardLiveData::create(WorkGang* workers, G1CMBitMap* mark_bitmap) { |
| _gc_timestamp_at_create = G1CollectedHeap::heap()->get_gc_time_stamp(); |
| |
| uint n_workers = workers->active_workers(); |
| |
| G1CreateCardLiveDataTask cl(mark_bitmap, |
| this, |
| n_workers); |
| workers->run_task(&cl); |
| } |
| |
| class G1FinalizeCardLiveDataTask: public AbstractGangTask { |
| // Finalizes the liveness counting data. |
| // Sets the bits corresponding to the interval [NTAMS, top] |
| // (which contains the implicitly live objects) in the |
| // card liveness bitmap. Also sets the bit for each region |
| // containing live data, in the region liveness bitmap. |
| class G1FinalizeCardLiveDataClosure: public HeapRegionClosure { |
| private: |
| G1CardLiveDataHelper _helper; |
| |
| uint _gc_timestamp_at_create; |
| |
| bool has_been_reclaimed(HeapRegion* hr) const { |
| return hr->get_gc_time_stamp() > _gc_timestamp_at_create; |
| } |
| public: |
| G1FinalizeCardLiveDataClosure(G1CollectedHeap* g1h, |
| G1CMBitMap* bitmap, |
| G1CardLiveData* live_data) : |
| HeapRegionClosure(), |
| _helper(live_data, g1h->reserved_region().start()), |
| _gc_timestamp_at_create(live_data->gc_timestamp_at_create()) { } |
| |
| bool doHeapRegion(HeapRegion* hr) { |
| if (has_been_reclaimed(hr)) { |
| _helper.reset_live_data(hr); |
| } |
| bool allocated_since_marking = _helper.mark_allocated_since_marking(hr); |
| if (allocated_since_marking || hr->next_marked_bytes() > 0) { |
| _helper.set_bit_for_region(hr); |
| } |
| return false; |
| } |
| }; |
| |
| G1CMBitMap* _bitmap; |
| |
| G1CardLiveData* _live_data; |
| |
| HeapRegionClaimer _hr_claimer; |
| |
| public: |
| G1FinalizeCardLiveDataTask(G1CMBitMap* bitmap, G1CardLiveData* live_data, uint n_workers) : |
| AbstractGangTask("G1 Finalize Card Live Data"), |
| _bitmap(bitmap), |
| _live_data(live_data), |
| _hr_claimer(n_workers) { |
| } |
| |
| void work(uint worker_id) { |
| G1FinalizeCardLiveDataClosure cl(G1CollectedHeap::heap(), _bitmap, _live_data); |
| |
| G1CollectedHeap::heap()->heap_region_par_iterate(&cl, worker_id, &_hr_claimer); |
| } |
| }; |
| |
| void G1CardLiveData::finalize(WorkGang* workers, G1CMBitMap* mark_bitmap) { |
| // Finalize the live data. |
| G1FinalizeCardLiveDataTask cl(mark_bitmap, |
| this, |
| workers->active_workers()); |
| workers->run_task(&cl); |
| } |
| |
| class G1ClearCardLiveDataTask : public AbstractGangTask { |
| BitMapView _bitmap; |
| size_t _num_chunks; |
| size_t _cur_chunk; |
| public: |
| G1ClearCardLiveDataTask(const BitMapView& bitmap, size_t num_tasks) : |
| AbstractGangTask("G1 Clear Card Live Data"), |
| _bitmap(bitmap), |
| _num_chunks(num_tasks), |
| _cur_chunk(0) { |
| } |
| |
| static size_t chunk_size() { return M; } |
| |
| virtual void work(uint worker_id) { |
| while (true) { |
| size_t to_process = Atomic::add(1u, &_cur_chunk) - 1; |
| if (to_process >= _num_chunks) { |
| break; |
| } |
| |
| BitMap::idx_t start = M * BitsPerByte * to_process; |
| BitMap::idx_t end = MIN2(start + M * BitsPerByte, _bitmap.size()); |
| _bitmap.clear_range(start, end); |
| } |
| } |
| }; |
| |
| void G1CardLiveData::clear(WorkGang* workers) { |
| guarantee(Universe::is_fully_initialized(), "Should not call this during initialization."); |
| |
| size_t const num_chunks = align_up(live_cards_bm().size_in_bytes(), G1ClearCardLiveDataTask::chunk_size()) / G1ClearCardLiveDataTask::chunk_size(); |
| uint const num_workers = (uint)MIN2(num_chunks, (size_t)workers->active_workers()); |
| |
| G1ClearCardLiveDataTask cl(live_cards_bm(), num_chunks); |
| |
| log_debug(gc, ergo)("Running %s using %u workers for " SIZE_FORMAT " work units.", cl.name(), num_workers, num_chunks); |
| workers->run_task(&cl, num_workers); |
| |
| // The region live bitmap is always very small, even for huge heaps. Clear |
| // directly. |
| live_regions_bm().clear(); |
| } |
| |
| class G1VerifyCardLiveDataTask: public AbstractGangTask { |
| // Heap region closure used for verifying the live count data |
| // that was created concurrently and finalized during |
| // the remark pause. This closure is applied to the heap |
| // regions during the STW cleanup pause. |
| class G1VerifyCardLiveDataClosure: public HeapRegionClosure { |
| private: |
| G1CollectedHeap* _g1h; |
| G1CMBitMap* _mark_bitmap; |
| G1CardLiveDataHelper _helper; |
| |
| G1CardLiveData* _act_live_data; |
| |
| G1CardLiveData* _exp_live_data; |
| |
| int _failures; |
| |
| // Completely recreates the live data count for the given heap region and |
| // returns the number of bytes marked. |
| size_t create_live_data_count(HeapRegion* hr) { |
| size_t bytes_marked = _helper.mark_marked_during_marking(_mark_bitmap, hr); |
| bool allocated_since_marking = _helper.mark_allocated_since_marking(hr); |
| if (allocated_since_marking || bytes_marked > 0) { |
| _helper.set_bit_for_region(hr); |
| } |
| return bytes_marked; |
| } |
| public: |
| G1VerifyCardLiveDataClosure(G1CollectedHeap* g1h, |
| G1CMBitMap* mark_bitmap, |
| G1CardLiveData* act_live_data, |
| G1CardLiveData* exp_live_data) : |
| _g1h(g1h), |
| _mark_bitmap(mark_bitmap), |
| _helper(exp_live_data, g1h->reserved_region().start()), |
| _act_live_data(act_live_data), |
| _exp_live_data(exp_live_data), |
| _failures(0) { } |
| |
| int failures() const { return _failures; } |
| |
| bool doHeapRegion(HeapRegion* hr) { |
| int failures = 0; |
| |
| // Walk the marking bitmap for this region and set the corresponding bits |
| // in the expected region and card bitmaps. |
| size_t exp_marked_bytes = create_live_data_count(hr); |
| size_t act_marked_bytes = hr->next_marked_bytes(); |
| // Verify the marked bytes for this region. |
| |
| if (exp_marked_bytes != act_marked_bytes) { |
| log_error(gc)("Expected marked bytes " SIZE_FORMAT " != actual marked bytes " SIZE_FORMAT " in region %u", exp_marked_bytes, act_marked_bytes, hr->hrm_index()); |
| failures += 1; |
| } else if (exp_marked_bytes > HeapRegion::GrainBytes) { |
| log_error(gc)("Expected marked bytes " SIZE_FORMAT " larger than possible " SIZE_FORMAT " in region %u", exp_marked_bytes, HeapRegion::GrainBytes, hr->hrm_index()); |
| failures += 1; |
| } |
| |
| // Verify the bit, for this region, in the actual and expected |
| // (which was just calculated) region bit maps. |
| uint index = hr->hrm_index(); |
| |
| bool expected = _exp_live_data->is_region_live(index); |
| bool actual = _act_live_data->is_region_live(index); |
| if (expected != actual) { |
| log_error(gc)("Expected liveness %d not equal actual %d in region %u", expected, actual, hr->hrm_index()); |
| failures += 1; |
| } |
| |
| // Verify that the card bit maps for the cards spanned by the current |
| // region match. |
| BitMap::idx_t start_idx = _helper.card_live_bitmap_index_for(hr->bottom()); |
| BitMap::idx_t end_idx = _helper.card_live_bitmap_index_for(hr->top()); |
| |
| for (BitMap::idx_t i = start_idx; i < end_idx; i+=1) { |
| expected = _exp_live_data->is_card_live_at(i); |
| actual = _act_live_data->is_card_live_at(i); |
| |
| if (expected != actual) { |
| log_error(gc)("Expected card liveness %d not equal actual card liveness %d at card " SIZE_FORMAT " in region %u", expected, actual, i, hr->hrm_index()); |
| failures += 1; |
| } |
| } |
| |
| _failures += failures; |
| |
| // We could stop iteration over the heap when we |
| // find the first violating region by returning true. |
| return false; |
| } |
| }; |
| protected: |
| G1CollectedHeap* _g1h; |
| G1CMBitMap* _mark_bitmap; |
| |
| G1CardLiveData* _act_live_data; |
| |
| G1CardLiveData _exp_live_data; |
| |
| int _failures; |
| |
| HeapRegionClaimer _hr_claimer; |
| |
| public: |
| G1VerifyCardLiveDataTask(G1CMBitMap* bitmap, |
| G1CardLiveData* act_live_data, |
| uint n_workers) |
| : AbstractGangTask("G1 Verify Card Live Data"), |
| _g1h(G1CollectedHeap::heap()), |
| _mark_bitmap(bitmap), |
| _act_live_data(act_live_data), |
| _exp_live_data(), |
| _failures(0), |
| _hr_claimer(n_workers) { |
| assert(VerifyDuringGC, "don't call this otherwise"); |
| _exp_live_data.initialize(_g1h->max_capacity(), _g1h->max_regions()); |
| } |
| |
| void work(uint worker_id) { |
| G1VerifyCardLiveDataClosure cl(_g1h, |
| _mark_bitmap, |
| _act_live_data, |
| &_exp_live_data); |
| _g1h->heap_region_par_iterate(&cl, worker_id, &_hr_claimer); |
| |
| Atomic::add(cl.failures(), &_failures); |
| } |
| |
| int failures() const { return _failures; } |
| }; |
| |
| void G1CardLiveData::verify(WorkGang* workers, G1CMBitMap* actual_bitmap) { |
| ResourceMark rm; |
| |
| G1VerifyCardLiveDataTask cl(actual_bitmap, |
| this, |
| workers->active_workers()); |
| workers->run_task(&cl); |
| |
| guarantee(cl.failures() == 0, "Unexpected accounting failures"); |
| } |
| |
| #ifndef PRODUCT |
| void G1CardLiveData::verify_is_clear() { |
| assert(live_cards_bm().count_one_bits() == 0, "Live cards bitmap must be clear."); |
| assert(live_regions_bm().count_one_bits() == 0, "Live regions bitmap must be clear."); |
| } |
| #endif |