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 HeapWord* ShenandoahMarkBitMap::get_next_marked_addr(const HeapWord* addr,
 47                                                      const HeapWord* limit) const {
 48   assert(limit != NULL, "limit must not be NULL");
 49   // Round addr up to a possible object boundary to be safe.
 50   size_t const addr_offset = address_to_index(align_up(addr, HeapWordSize << LogMinObjAlignment));
 51   size_t const limit_offset = address_to_index(limit);
 52   size_t const nextOffset = get_next_one_offset(addr_offset, limit_offset);
 53   return index_to_address(nextOffset);
 54 }
 55 
 56 void ShenandoahMarkBitMap::clear_range_within_word(idx_t beg, idx_t end) {
 57   // With a valid range (beg <= end), this test ensures that end != 0, as
 58   // required by inverted_bit_mask_for_range.  Also avoids an unnecessary write.
 59   if (beg != end) {
 60     bm_word_t mask = inverted_bit_mask_for_range(beg, end);
 61     *word_addr(beg) &= mask;
 62   }
 63 }
 64 
 65 void ShenandoahMarkBitMap::clear_range(idx_t beg, idx_t end) {
 66   verify_range(beg, end);
 67 
 68   idx_t beg_full_word = to_words_align_up(beg);
 69   idx_t end_full_word = to_words_align_down(end);
 70 
 71   if (beg_full_word < end_full_word) {
 72     // The range includes at least one full word.
 73     clear_range_within_word(beg, bit_index(beg_full_word));
 74     clear_range_of_words(beg_full_word, end_full_word);
 75     clear_range_within_word(bit_index(end_full_word), end);
 76   } else {
 77     // The range spans at most 2 partial words.
 78     idx_t boundary = MIN2(bit_index(beg_full_word), end);
 79     clear_range_within_word(beg, boundary);
 80     clear_range_within_word(boundary, end);
 81   }
 82 }
 83 
 84 bool ShenandoahMarkBitMap::is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word) {
 85   // There is little point to call large version on small ranges.
 86   // Need to check carefully, keeping potential idx_t over/underflow in mind,
 87   // because beg_full_word > end_full_word can occur when beg and end are in
 88   // the same word.
 89   // The threshold should be at least one word.
 90   STATIC_ASSERT(small_range_words >= 1);
 91   return beg_full_word + small_range_words >= end_full_word;
 92 }
 93 
 94 
 95 void ShenandoahMarkBitMap::clear_large_range(idx_t beg, idx_t end) {
 96   verify_range(beg, end);
 97 
 98   idx_t beg_full_word = to_words_align_up(beg);
 99   idx_t end_full_word = to_words_align_down(end);
100 
101   if (is_small_range_of_words(beg_full_word, end_full_word)) {
102     clear_range(beg, end);
103     return;
104   }
105 
106   // The range includes at least one full word.
107   clear_range_within_word(beg, bit_index(beg_full_word));
108   clear_large_range_of_words(beg_full_word, end_full_word);
109   clear_range_within_word(bit_index(end_full_word), end);
110 }
111 
112 void ShenandoahMarkBitMap::clear_range_large(MemRegion mr) {
113   MemRegion intersection = mr.intersection(_covered);
114   assert(!intersection.is_empty(),
115          "Given range from " PTR_FORMAT " to " PTR_FORMAT " is completely outside the heap",
116           p2i(mr.start()), p2i(mr.end()));
117   // convert address range into offset range
118   size_t beg = address_to_index(intersection.start());
119   size_t end = address_to_index(intersection.end());
120   clear_large_range(beg, end);
121 }
122 
123 #ifdef ASSERT
124 void ShenandoahMarkBitMap::check_mark(HeapWord* addr) const {
125   assert(ShenandoahHeap::heap()->is_in(addr),
126          "Trying to access bitmap " PTR_FORMAT " for address " PTR_FORMAT " not in the heap.",
127          p2i(this), p2i(addr));
128 }
129 
130 void ShenandoahMarkBitMap::verify_index(idx_t bit) const {
131   assert(bit < _size,
132          "BitMap index out of bounds: " SIZE_FORMAT " >= " SIZE_FORMAT,
133          bit, _size);
134 }
135 
136 void ShenandoahMarkBitMap::verify_limit(idx_t bit) const {
137   assert(bit <= _size,
138          "BitMap limit out of bounds: " SIZE_FORMAT " > " SIZE_FORMAT,
139          bit, _size);
140 }
141 
142 void ShenandoahMarkBitMap::verify_range(idx_t beg, idx_t end) const {
143   assert(beg <= end,
144          "BitMap range error: " SIZE_FORMAT " > " SIZE_FORMAT, beg, end);
145   verify_limit(end);
146 }
147 #endif