1 /*
  2  * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
  3  * Copyright (c) 2020, Red Hat, Inc. and/or its affiliates.
  4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  5  *
  6  * This code is free software; you can redistribute it and/or modify it
  7  * under the terms of the GNU General Public License version 2 only, as
  8  * published by the Free Software Foundation.
  9  *
 10  * This code is distributed in the hope that it will be useful, but WITHOUT
 11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 13  * version 2 for more details (a copy is included in the LICENSE file that
 14  * accompanied this code).
 15  *
 16  * You should have received a copy of the GNU General Public License version
 17  * 2 along with this work; if not, write to the Free Software Foundation,
 18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 19  *
 20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 21  * or visit www.oracle.com if you need additional information or have any
 22  * questions.
 23  *
 24  */
 25 
 26 #include "precompiled.hpp"
 27 #include "gc/shenandoah/shenandoahMarkBitMap.inline.hpp"
 28 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
 29 #include "utilities/globalDefinitions.hpp"
 30 
 31 ShenandoahMarkBitMap::ShenandoahMarkBitMap(MemRegion heap, MemRegion storage) :
 32   _shift(LogMinObjAlignment),
 33   _covered(heap),
 34   _map((BitMap::bm_word_t*) storage.start()),
 35   _size((heap.word_size() * 2) >> _shift) {
 36 }
 37 
 38 size_t ShenandoahMarkBitMap::compute_size(size_t heap_size) {
 39   return ReservedSpace::allocation_align_size_up(heap_size / mark_distance());
 40 }
 41 
 42 size_t ShenandoahMarkBitMap::mark_distance() {
 43   return MinObjAlignmentInBytes * BitsPerByte / 2;
 44 }
 45 
 46 bool ShenandoahMarkBitMap::is_bitmap_clear_range(const HeapWord* start, const HeapWord* end) const {
 47   // Similar to get_next_marked_addr(), without assertion.
 48   // Round addr up to a possible object boundary to be safe.
 49   if (start == end) {
 50     return true;
 51   }
 52   size_t const addr_offset = address_to_index(align_up(start, HeapWordSize << LogMinObjAlignment));
 53   size_t const limit_offset = address_to_index(end);
 54   size_t const next_offset = get_next_one_offset(addr_offset, limit_offset);
 55   HeapWord* result = index_to_address(next_offset);
 56   return (result == end);
 57 }
 58 
 59 
 60 HeapWord* ShenandoahMarkBitMap::get_next_marked_addr(const HeapWord* addr,
 61                                                      const HeapWord* limit) const {
 62 #ifdef ASSERT
 63   ShenandoahHeap* heap = ShenandoahHeap::heap();
 64   ShenandoahHeapRegion* r = heap->heap_region_containing(addr);
 65   ShenandoahMarkingContext* ctx = heap->marking_context();
 66   HeapWord* tams = ctx->top_at_mark_start(r);
 67   assert(limit != NULL, "limit must not be NULL");
 68   assert(limit <= tams, "limit must be less than TAMS");
 69 #endif
 70 
 71   // Round addr up to a possible object boundary to be safe.
 72   size_t const addr_offset = address_to_index(align_up(addr, HeapWordSize << LogMinObjAlignment));
 73   size_t const limit_offset = address_to_index(limit);
 74   size_t const nextOffset = get_next_one_offset(addr_offset, limit_offset);
 75   HeapWord* result = index_to_address(nextOffset);
 76   return result;
 77 }
 78 
 79 void ShenandoahMarkBitMap::clear_range_within_word(idx_t beg, idx_t end) {
 80   // With a valid range (beg <= end), this test ensures that end != 0, as
 81   // required by inverted_bit_mask_for_range.  Also avoids an unnecessary write.
 82   if (beg != end) {
 83     bm_word_t mask = inverted_bit_mask_for_range(beg, end);
 84     *word_addr(beg) &= mask;
 85   }
 86 }
 87 
 88 void ShenandoahMarkBitMap::clear_range(idx_t beg, idx_t end) {
 89   verify_range(beg, end);
 90 
 91   idx_t beg_full_word = to_words_align_up(beg);
 92   idx_t end_full_word = to_words_align_down(end);
 93 
 94   if (beg_full_word < end_full_word) {
 95     // The range includes at least one full word.
 96     clear_range_within_word(beg, bit_index(beg_full_word));
 97     clear_range_of_words(beg_full_word, end_full_word);
 98     clear_range_within_word(bit_index(end_full_word), end);
 99   } else {
100     // The range spans at most 2 partial words.
101     idx_t boundary = MIN2(bit_index(beg_full_word), end);
102     clear_range_within_word(beg, boundary);
103     clear_range_within_word(boundary, end);
104   }
105 }
106 
107 bool ShenandoahMarkBitMap::is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word) {
108   // There is little point to call large version on small ranges.
109   // Need to check carefully, keeping potential idx_t over/underflow in mind,
110   // because beg_full_word > end_full_word can occur when beg and end are in
111   // the same word.
112   // The threshold should be at least one word.
113   STATIC_ASSERT(small_range_words >= 1);
114   return beg_full_word + small_range_words >= end_full_word;
115 }
116 
117 
118 void ShenandoahMarkBitMap::clear_large_range(idx_t beg, idx_t end) {
119   verify_range(beg, end);
120 
121   idx_t beg_full_word = to_words_align_up(beg);
122   idx_t end_full_word = to_words_align_down(end);
123 
124   if (is_small_range_of_words(beg_full_word, end_full_word)) {
125     clear_range(beg, end);
126     return;
127   }
128 
129   // The range includes at least one full word.
130   clear_range_within_word(beg, bit_index(beg_full_word));
131   clear_large_range_of_words(beg_full_word, end_full_word);
132   clear_range_within_word(bit_index(end_full_word), end);
133 }
134 
135 void ShenandoahMarkBitMap::clear_range_large(MemRegion mr) {
136   MemRegion intersection = mr.intersection(_covered);
137   assert(!intersection.is_empty(),
138          "Given range from " PTR_FORMAT " to " PTR_FORMAT " is completely outside the heap",
139           p2i(mr.start()), p2i(mr.end()));
140   // convert address range into offset range
141   size_t beg = address_to_index(intersection.start());
142   size_t end = address_to_index(intersection.end());
143   clear_large_range(beg, end);
144 }
145 
146 #ifdef ASSERT
147 void ShenandoahMarkBitMap::check_mark(HeapWord* addr) const {
148   assert(ShenandoahHeap::heap()->is_in(addr),
149          "Trying to access bitmap " PTR_FORMAT " for address " PTR_FORMAT " not in the heap.",
150          p2i(this), p2i(addr));
151 }
152 
153 void ShenandoahMarkBitMap::verify_index(idx_t bit) const {
154   assert(bit < _size,
155          "BitMap index out of bounds: " SIZE_FORMAT " >= " SIZE_FORMAT,
156          bit, _size);
157 }
158 
159 void ShenandoahMarkBitMap::verify_limit(idx_t bit) const {
160   assert(bit <= _size,
161          "BitMap limit out of bounds: " SIZE_FORMAT " > " SIZE_FORMAT,
162          bit, _size);
163 }
164 
165 void ShenandoahMarkBitMap::verify_range(idx_t beg, idx_t end) const {
166   assert(beg <= end,
167          "BitMap range error: " SIZE_FORMAT " > " SIZE_FORMAT, beg, end);
168   verify_limit(end);
169 }
170 #endif