1 /*
  2  * Copyright (c) 2018, 2022, 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 #ifndef SHARE_VM_GC_SHENANDOAH_SHENANDOAHMARKBITMAP_INLINE_HPP
 27 #define SHARE_VM_GC_SHENANDOAH_SHENANDOAHMARKBITMAP_INLINE_HPP
 28 
 29 #include "gc/shenandoah/shenandoahMarkBitMap.hpp"
 30 
 31 #include "runtime/atomic.hpp"
 32 #include "utilities/count_trailing_zeros.hpp"
 33 
 34 inline size_t ShenandoahMarkBitMap::address_to_index(const HeapWord* addr) const {
 35   return (pointer_delta(addr, _covered.start()) << 1) >> _shift;
 36 }
 37 
 38 inline HeapWord* ShenandoahMarkBitMap::index_to_address(size_t offset) const {
 39   return _covered.start() + ((offset >> 1) << _shift);
 40 }
 41 
 42 inline bool ShenandoahMarkBitMap::mark_strong(HeapWord* heap_addr, bool& was_upgraded) {
 43   check_mark(heap_addr);
 44 
 45   idx_t bit = address_to_index(heap_addr);
 46   verify_index(bit);
 47   volatile bm_word_t* const addr = word_addr(bit);
 48   const bm_word_t mask = bit_mask(bit);
 49   const bm_word_t mask_weak = (bm_word_t)1 << (bit_in_word(bit) + 1);
 50   bm_word_t old_val = Atomic::load(addr);
 51 
 52   do {
 53     const bm_word_t new_val = old_val | mask;
 54     if (new_val == old_val) {
 55       assert(!was_upgraded, "Should be false already");
 56       return false;     // Someone else beat us to it.
 57     }
 58     const bm_word_t cur_val = Atomic::cmpxchg(addr, old_val, new_val, memory_order_relaxed);
 59     if (cur_val == old_val) {
 60       was_upgraded = (cur_val & mask_weak) != 0;
 61       return true;      // Success.
 62     }
 63     old_val = cur_val;  // The value changed, try again.
 64   } while (true);
 65 }
 66 
 67 inline bool ShenandoahMarkBitMap::mark_weak(HeapWord* heap_addr) {
 68   check_mark(heap_addr);
 69 
 70   idx_t bit = address_to_index(heap_addr);
 71   verify_index(bit);
 72   volatile bm_word_t* const addr = word_addr(bit);
 73   const bm_word_t mask_weak = (bm_word_t)1 << (bit_in_word(bit) + 1);
 74   const bm_word_t mask_strong = (bm_word_t)1 << bit_in_word(bit);
 75   bm_word_t old_val = Atomic::load(addr);
 76 
 77   do {
 78     if ((old_val & mask_strong) != 0) {
 79       return false;     // Already marked strong
 80     }
 81     const bm_word_t new_val = old_val | mask_weak;
 82     if (new_val == old_val) {
 83       return false;     // Someone else beat us to it.
 84     }
 85     const bm_word_t cur_val = Atomic::cmpxchg(addr, old_val, new_val, memory_order_relaxed);
 86     if (cur_val == old_val) {
 87       return true;      // Success.
 88     }
 89     old_val = cur_val;  // The value changed, try again.
 90   } while (true);
 91 }
 92 
 93 inline bool ShenandoahMarkBitMap::is_marked_strong(HeapWord* addr)  const {
 94   check_mark(addr);
 95   return at(address_to_index(addr));
 96 }
 97 
 98 inline bool ShenandoahMarkBitMap::is_marked_weak(HeapWord* addr) const {
 99   check_mark(addr);
100   return at(address_to_index(addr) + 1);
101 }
102 
103 inline bool ShenandoahMarkBitMap::is_marked(HeapWord* addr) const {
104   check_mark(addr);
105   idx_t index = address_to_index(addr);
106   verify_index(index);
107   bm_word_t mask = (bm_word_t)3 << bit_in_word(index);
108   return (*word_addr(index) & mask) != 0;
109 }
110 
111 template<ShenandoahMarkBitMap::bm_word_t flip, bool aligned_right>
112 inline ShenandoahMarkBitMap::idx_t ShenandoahMarkBitMap::get_next_bit_impl(idx_t l_index, idx_t r_index) const {
113   STATIC_ASSERT(flip == find_ones_flip || flip == find_zeros_flip);
114   verify_range(l_index, r_index);
115   assert(!aligned_right || is_aligned(r_index, BitsPerWord), "r_index not aligned");
116 
117   // The first word often contains an interesting bit, either due to
118   // density or because of features of the calling algorithm.  So it's
119   // important to examine that first word with a minimum of fuss,
120   // minimizing setup time for later words that will be wasted if the
121   // first word is indeed interesting.
122 
123   // The benefit from aligned_right being true is relatively small.
124   // It saves an operation in the setup for the word search loop.
125   // It also eliminates the range check on the final result.
126   // However, callers often have a comparison with r_index, and
127   // inlining often allows the two comparisons to be combined; it is
128   // important when !aligned_right that return paths either return
129   // r_index or a value dominated by a comparison with r_index.
130   // aligned_right is still helpful when the caller doesn't have a
131   // range check because features of the calling algorithm guarantee
132   // an interesting bit will be present.
133 
134   if (l_index < r_index) {
135     // Get the word containing l_index, and shift out low bits.
136     idx_t index = to_words_align_down(l_index);
137     bm_word_t cword = (map(index) ^ flip) >> bit_in_word(l_index);
138     if ((cword & 1) != 0) {
139       // The first bit is similarly often interesting. When it matters
140       // (density or features of the calling algorithm make it likely
141       // the first bit is set), going straight to the next clause compares
142       // poorly with doing this check first; count_trailing_zeros can be
143       // relatively expensive, plus there is the additional range check.
144       // But when the first bit isn't set, the cost of having tested for
145       // it is relatively small compared to the rest of the search.
146       return l_index;
147     } else if (cword != 0) {
148       // Flipped and shifted first word is non-zero.
149       idx_t result = l_index + count_trailing_zeros(cword);
150       if (aligned_right || (result < r_index)) return result;
151       // Result is beyond range bound; return r_index.
152     } else {
153       // Flipped and shifted first word is zero.  Word search through
154       // aligned up r_index for a non-zero flipped word.
155       idx_t limit = aligned_right
156                     ? to_words_align_down(r_index) // Minuscule savings when aligned.
157                     : to_words_align_up(r_index);
158       while (++index < limit) {
159         cword = map(index) ^ flip;
160         if (cword != 0) {
161           idx_t result = bit_index(index) + count_trailing_zeros(cword);
162           if (aligned_right || (result < r_index)) return result;
163           // Result is beyond range bound; return r_index.
164           assert((index + 1) == limit, "invariant");
165           break;
166         }
167       }
168       // No bits in range; return r_index.
169     }
170   }
171   return r_index;
172 }
173 
174 inline ShenandoahMarkBitMap::idx_t ShenandoahMarkBitMap::get_next_one_offset(idx_t l_offset, idx_t r_offset) const {
175   return get_next_bit_impl<find_ones_flip, false>(l_offset, r_offset);
176 }
177 
178 // Returns a bit mask for a range of bits [beg, end) within a single word.  Each
179 // bit in the mask is 0 if the bit is in the range, 1 if not in the range.  The
180 // returned mask can be used directly to clear the range, or inverted to set the
181 // range.  Note:  end must not be 0.
182 inline ShenandoahMarkBitMap::bm_word_t
183 ShenandoahMarkBitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const {
184   assert(end != 0, "does not work when end == 0");
185   assert(beg == end || to_words_align_down(beg) == to_words_align_down(end - 1),
186          "must be a single-word range");
187   bm_word_t mask = bit_mask(beg) - 1;   // low (right) bits
188   if (bit_in_word(end) != 0) {
189     mask |= ~(bit_mask(end) - 1);       // high (left) bits
190   }
191   return mask;
192 }
193 
194 inline void ShenandoahMarkBitMap::clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end) {
195   for (idx_t i = beg; i < end; ++i) map[i] = 0;
196 }
197 
198 inline void ShenandoahMarkBitMap::clear_large_range_of_words(idx_t beg, idx_t end) {
199   assert(beg <= end, "underflow");
200   memset(_map + beg, 0, (end - beg) * sizeof(bm_word_t));
201 }
202 
203 inline void ShenandoahMarkBitMap::clear_range_of_words(idx_t beg, idx_t end) {
204   clear_range_of_words(_map, beg, end);
205 }
206 
207 
208 #endif // SHARE_VM_GC_SHENANDOAH_SHENANDOAHMARKBITMAP_INLINE_HPP