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