1 /*
2 * Copyright (c) 2018, 2025, Oracle and/or its affiliates. All rights reserved.
3 * Copyright (c) 2020, Red Hat, Inc. and/or its affiliates.
4 * Copyright Amazon.com Inc. or its affiliates. All Rights Reserved.
5 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 *
7 * This code is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License version 2 only, as
9 * published by the Free Software Foundation.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 *
25 */
26
27 #ifndef SHARE_GC_SHENANDOAH_SHENANDOAHMARKBITMAP_HPP
28 #define SHARE_GC_SHENANDOAH_SHENANDOAHMARKBITMAP_HPP
29
30 #include "memory/memRegion.hpp"
31 #include "runtime/atomicAccess.hpp"
32 #include "utilities/globalDefinitions.hpp"
33
34 class ShenandoahMarkBitMap {
35 public:
36 typedef size_t idx_t; // Type used for bit and word indices.
37 typedef uintptr_t bm_word_t; // Element type of array that represents the
38 // bitmap, with BitsPerWord bits per element.
39
40 private:
41 // Values for get_next_bit_impl flip parameter.
42 static const bm_word_t find_ones_flip = 0;
43 static const bm_word_t find_zeros_flip = ~(bm_word_t)0;
44
45 int const _shift;
46 MemRegion _covered;
47
48 bm_word_t* _map; // First word in bitmap
49 idx_t _size; // Size of bitmap (in bits)
50
51 // Threshold for performing small range operation, even when large range
52 // operation was requested. Measured in words.
53 static const size_t small_range_words = 32;
54
55 static bool is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word);
56
57 inline size_t address_to_index(const HeapWord* addr) const;
58 inline HeapWord* index_to_address(size_t offset) const;
59
60 void check_mark(HeapWord* addr) const NOT_DEBUG_RETURN;
61
62 // Return a mask that will select the specified bit, when applied to the word
63 // containing the bit.
64 static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); }
65
66 // Return the bit number of the first bit in the specified word.
67 static idx_t bit_index(idx_t word) { return word << LogBitsPerWord; }
68
69 // Return the position of bit within the word that contains it (e.g., if
70 // bitmap words are 32 bits, return a number 0 <= n <= 31).
71 static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); }
72
73 bm_word_t* map() { return _map; }
74 const bm_word_t* map() const { return _map; }
75 bm_word_t map(idx_t word) const { return _map[word]; }
76
77 // Return a pointer to the word containing the specified bit.
78 bm_word_t* word_addr(idx_t bit) {
79 return map() + to_words_align_down(bit);
80 }
81
82 const bm_word_t* word_addr(idx_t bit) const {
83 return map() + to_words_align_down(bit);
84 }
85
86 bool at(idx_t index) const {
87 verify_index(index);
88 return (*word_addr(index) & bit_mask(index)) != 0;
89 }
90
91 // Assumes relevant validity checking for bit has already been done.
92 static idx_t raw_to_words_align_up(idx_t bit) {
93 return raw_to_words_align_down(bit + (BitsPerWord - 1));
94 }
95
96 // Assumes relevant validity checking for bit has already been done.
97 static idx_t raw_to_words_align_down(idx_t bit) {
98 return bit >> LogBitsPerWord;
99 }
100
101 // Word-aligns bit and converts it to a word offset.
102 // precondition: bit <= size()
103 idx_t to_words_align_up(idx_t bit) const {
104 verify_limit(bit);
105 return raw_to_words_align_up(bit);
106 }
107
108 // Word-aligns bit and converts it to a word offset.
109 // precondition: bit <= size()
110 inline idx_t to_words_align_down(idx_t bit) const {
111 verify_limit(bit);
112 return raw_to_words_align_down(bit);
113 }
114
115 // Helper for get_next_{zero,one}_bit variants.
116 // - flip designates whether searching for 1s or 0s. Must be one of
117 // find_{zeros,ones}_flip.
118 // - aligned_right is true if r_index is a priori on a bm_word_t boundary.
119 template<bm_word_t flip, bool aligned_right>
120 inline idx_t get_next_bit_impl(idx_t l_index, idx_t r_index) const;
121
122 // Helper for get_prev_{zero,one}_bit variants.
123 // - flip designates whether searching for 1s or 0s. Must be one of
124 // find_{zeros,ones}_flip.
125 // - aligned_left is true if l_index is a priori on a bm_word_t boundary.
126 template<bm_word_t flip, bool aligned_left>
127 inline idx_t get_prev_bit_impl(idx_t l_index, idx_t r_index) const;
128
129 // Search for the first marked address in the range [l_index, r_index), or r_index if none found.
130 inline idx_t get_next_one_offset(idx_t l_index, idx_t r_index) const;
131
132 // Search for last one in the range [l_index, r_index). Return r_index if not found.
133 inline idx_t get_prev_one_offset(idx_t l_index, idx_t r_index) const;
134
135 // Clear the strong and weak mark bits for all index positions >= l_index and < r_index.
136 void clear_large_range(idx_t beg, idx_t end);
137
138 // Verify bit is less than size().
139 void verify_index(idx_t bit) const NOT_DEBUG_RETURN;
140 // Verify bit is not greater than size().
141 void verify_limit(idx_t bit) const NOT_DEBUG_RETURN;
142 // Verify [beg,end) is a valid range, e.g. beg <= end <= size().
143 void verify_range(idx_t beg, idx_t end) const NOT_DEBUG_RETURN;
144
145 public:
146 static size_t compute_size(size_t heap_size);
147 // Returns the amount of bytes on the heap between two marks in the bitmap.
148 static size_t mark_distance();
149 // Returns how many bytes (or bits) of the heap a single byte (or bit) of the
150 // mark bitmap corresponds to. This is the same as the mark distance above.
151 static size_t heap_map_factor() {
152 return mark_distance();
153 }
154
155 ShenandoahMarkBitMap(MemRegion heap, MemRegion storage);
156
157 // Mark word as 'strong' if it hasn't been marked strong yet.
158 // Return true if the word has been marked strong, false if it has already been
159 // marked strong or if another thread has beat us by marking it
160 // strong.
161 // Words that have been marked final before or by a concurrent thread will be
162 // upgraded to strong. In this case, this method also returns true.
163 inline bool mark_strong(HeapWord* w, bool& was_upgraded);
164
165 // Mark word as 'weak' if it hasn't been marked weak or strong yet.
166 // Return true if the word has been marked weak, false if it has already been
167 // marked strong or weak or if another thread has beat us by marking it
168 // strong or weak.
169 inline bool mark_weak(HeapWord* heap_addr);
170
171 inline bool is_marked(HeapWord* addr) const;
172 inline bool is_marked_strong(HeapWord* w) const;
173 inline bool is_marked_weak(HeapWord* addr) const;
174
175 bool is_bitmap_clear_range(const HeapWord* start, const HeapWord* end) const;
176
177 // Return the first marked address in the range [addr, limit), or limit if none found.
178 HeapWord* get_next_marked_addr(const HeapWord* addr,
179 const HeapWord* limit) const;
180
181 // Return the last marked address in the range [limit, addr], or addr+1 if none found.
182 HeapWord* get_prev_marked_addr(const HeapWord* limit,
183 const HeapWord* addr) const;
184
185 bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const;
186 void clear_range_within_word (idx_t beg, idx_t end);
187 void clear_range (idx_t beg, idx_t end);
188 void clear_range_large(MemRegion mr);
189
190 void clear_range_of_words(idx_t beg, idx_t end);
191 void clear_large_range_of_words(idx_t beg, idx_t end);
192 static void clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end);
193 };
194
195 #endif // SHARE_GC_SHENANDOAH_SHENANDOAHMARKBITMAP_HPP