10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_UTILITIES_BITMAP_HPP
26 #define SHARE_UTILITIES_BITMAP_HPP
27
28 #include "memory/allocation.hpp"
29 #include "runtime/atomic.hpp"
30 #include "utilities/align.hpp"
31
32 // Forward decl;
33 class BitMapClosure;
34
35 // Operations for bitmaps represented as arrays of unsigned integers.
36 // Bit offsets are numbered from 0 to size-1.
37
38 // The "abstract" base BitMap class.
39 //
40 // The constructor and destructor are protected to prevent
41 // creation of BitMap instances outside of the BitMap class.
42 //
43 // The BitMap class doesn't use virtual calls on purpose,
44 // this ensures that we don't get a vtable unnecessarily.
45 //
46 // The allocation of the backing storage for the BitMap are handled by
47 // the subclasses. BitMap doesn't allocate or delete backing storage.
48 class BitMap {
49 friend class BitMap2D;
50
51 public:
52 typedef size_t idx_t; // Type used for bit and word indices.
53 typedef uintptr_t bm_word_t; // Element type of array that represents
54 // the bitmap.
55
56 // Hints for range sizes.
57 typedef enum {
58 unknown_range, small_range, large_range
59 } RangeSizeHint;
60
61 private:
62 bm_word_t* _map; // First word in bitmap
63 idx_t _size; // Size of bitmap (in bits)
64
65 // Helper for get_next_{zero,one}_bit variants.
66 // - flip designates whether searching for 1s or 0s. Must be one of
67 // find_{zeros,ones}_flip.
68 // - aligned_right is true if r_index is a priori on a bm_word_t boundary.
69 template<bm_word_t flip, bool aligned_right>
70 inline idx_t get_next_bit_impl(idx_t l_index, idx_t r_index) const;
71
72 // Values for get_next_bit_impl flip parameter.
73 static const bm_word_t find_ones_flip = 0;
74 static const bm_word_t find_zeros_flip = ~(bm_word_t)0;
75
76 // Threshold for performing small range operation, even when large range
77 // operation was requested. Measured in words.
78 static const size_t small_range_words = 32;
79
80 protected:
81 // Return the position of bit within the word that contains it (e.g., if
82 // bitmap words are 32 bits, return a number 0 <= n <= 31).
83 static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); }
84
85 // Return a mask that will select the specified bit, when applied to the word
86 // containing the bit.
87 static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); }
88
89 // Return the index of the word containing the specified bit.
90 static idx_t word_index(idx_t bit) { return bit >> LogBitsPerWord; }
91
92 // Return the bit number of the first bit in the specified word.
93 static idx_t bit_index(idx_t word) { return word << LogBitsPerWord; }
94
95 // Return the array of bitmap words, or a specific word from it.
96 bm_word_t* map() { return _map; }
97 const bm_word_t* map() const { return _map; }
98 bm_word_t map(idx_t word) const { return _map[word]; }
99
100 // Return a pointer to the word containing the specified bit.
101 bm_word_t* word_addr(idx_t bit) { return map() + word_index(bit); }
102 const bm_word_t* word_addr(idx_t bit) const { return map() + word_index(bit); }
103
104 // Set a word to a specified value or to all ones; clear a word.
105 void set_word (idx_t word, bm_word_t val) { _map[word] = val; }
106 void set_word (idx_t word) { set_word(word, ~(bm_word_t)0); }
107 void clear_word(idx_t word) { _map[word] = 0; }
108
109 static inline const bm_word_t load_word_ordered(const volatile bm_word_t* const addr, atomic_memory_order memory_order);
110
111 // Utilities for ranges of bits. Ranges are half-open [beg, end).
112
113 // Ranges within a single word.
114 bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const;
115 void set_range_within_word (idx_t beg, idx_t end);
116 void clear_range_within_word (idx_t beg, idx_t end);
117 void par_put_range_within_word (idx_t beg, idx_t end, bool value);
118
119 // Ranges spanning entire words.
120 void set_range_of_words (idx_t beg, idx_t end);
121 void clear_range_of_words (idx_t beg, idx_t end);
122 void set_large_range_of_words (idx_t beg, idx_t end);
123 void clear_large_range_of_words (idx_t beg, idx_t end);
124
125 static void clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end);
126
127 static bool is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word);
128
129 // The index of the first full word in a range.
130 idx_t word_index_round_up(idx_t bit) const;
131
132 // Verification.
133 void verify_index(idx_t index) const NOT_DEBUG_RETURN;
134 void verify_range(idx_t beg_index, idx_t end_index) const NOT_DEBUG_RETURN;
135
136 // Statistics.
137 static const idx_t* _pop_count_table;
138 static void init_pop_count_table();
139 static idx_t num_set_bits(bm_word_t w);
140 static idx_t num_set_bits_from_table(unsigned char c);
141
142 // Allocation Helpers.
143
144 // Allocates and clears the bitmap memory.
145 template <class Allocator>
146 static bm_word_t* allocate(const Allocator&, idx_t size_in_bits, bool clear = true);
147
148 // Reallocates and clears the new bitmap memory.
149 template <class Allocator>
150 static bm_word_t* reallocate(const Allocator&, bm_word_t* map, idx_t old_size_in_bits, idx_t new_size_in_bits, bool clear = true);
151
152 // Free the bitmap memory.
153 template <class Allocator>
154 static void free(const Allocator&, bm_word_t* map, idx_t size_in_bits);
165 // Set up and clear the bitmap memory.
166 //
167 // Precondition: The bitmap was default constructed and has
168 // not yet had memory allocated via resize or (re)initialize.
169 template <class Allocator>
170 void initialize(const Allocator& allocator, idx_t size_in_bits, bool clear);
171
172 // Set up and clear the bitmap memory.
173 //
174 // Can be called on previously initialized bitmaps.
175 template <class Allocator>
176 void reinitialize(const Allocator& allocator, idx_t new_size_in_bits, bool clear);
177
178 // Set the map and size.
179 void update(bm_word_t* map, idx_t size) {
180 _map = map;
181 _size = size;
182 }
183
184 // Protected constructor and destructor.
185 BitMap(bm_word_t* map, idx_t size_in_bits) : _map(map), _size(size_in_bits) {}
186 ~BitMap() {}
187
188 public:
189 // Pretouch the entire range of memory this BitMap covers.
190 void pretouch();
191
192 // Accessing
193 static idx_t calc_size_in_words(size_t size_in_bits) {
194 return word_index(size_in_bits + BitsPerWord - 1);
195 }
196
197 static idx_t calc_size_in_bytes(size_t size_in_bits) {
198 return calc_size_in_words(size_in_bits) * BytesPerWord;
199 }
200
201 idx_t size() const { return _size; }
202 idx_t size_in_words() const { return calc_size_in_words(size()); }
203 idx_t size_in_bytes() const { return calc_size_in_bytes(size()); }
204
205 bool at(idx_t index) const {
206 verify_index(index);
207 return (*word_addr(index) & bit_mask(index)) != 0;
208 }
209
210 // memory_order must be memory_order_relaxed or memory_order_acquire.
211 bool par_at(idx_t index, atomic_memory_order memory_order = memory_order_acquire) const;
212
213 // Align bit index up or down to the next bitmap word boundary, or check
214 // alignment.
215 static idx_t word_align_up(idx_t bit) {
216 return align_up(bit, BitsPerWord);
217 }
218 static idx_t word_align_down(idx_t bit) {
219 return align_down(bit, BitsPerWord);
220 }
221 static bool is_word_aligned(idx_t bit) {
222 return word_align_up(bit) == bit;
223 }
224
225 // Set or clear the specified bit.
226 inline void set_bit(idx_t bit);
227 inline void clear_bit(idx_t bit);
228
229 // Attempts to change a bit to a desired value. The operation returns true if
230 // this thread changed the value of the bit. It was changed with a RMW operation
231 // using the specified memory_order. The operation returns false if the change
232 // could not be set due to the bit already being observed in the desired state.
233 // The atomic access that observed the bit in the desired state has acquire
234 // semantics, unless memory_order is memory_order_relaxed or memory_order_release.
235 inline bool par_set_bit(idx_t bit, atomic_memory_order memory_order = memory_order_conservative);
236 inline bool par_clear_bit(idx_t bit, atomic_memory_order memory_order = memory_order_conservative);
237
238 // Put the given value at the given offset. The parallel version
239 // will CAS the value into the bitmap and is quite a bit slower.
240 // The parallel version also returns a value indicating if the
241 // calling thread was the one that changed the value of the bit.
242 void at_put(idx_t index, bool value);
243 bool par_at_put(idx_t index, bool value);
244
245 // Update a range of bits. Ranges are half-open [beg, end).
246 void set_range (idx_t beg, idx_t end);
247 void clear_range (idx_t beg, idx_t end);
248 void set_large_range (idx_t beg, idx_t end);
249 void clear_large_range (idx_t beg, idx_t end);
250 void at_put_range(idx_t beg, idx_t end, bool value);
251 void par_at_put_range(idx_t beg, idx_t end, bool value);
252 void at_put_large_range(idx_t beg, idx_t end, bool value);
253 void par_at_put_large_range(idx_t beg, idx_t end, bool value);
254
255 // Update a range of bits, using a hint about the size. Currently only
256 // inlines the predominant case of a 1-bit range. Works best when hint is a
257 // compile-time constant.
258 void set_range(idx_t beg, idx_t end, RangeSizeHint hint);
437 _map(size_in_slots * bits_per_slot), _bits_per_slot(bits_per_slot) {}
438
439 idx_t size_in_bits() {
440 return _map.size();
441 }
442
443 bool is_valid_index(idx_t slot_index, idx_t bit_within_slot_index);
444 bool at(idx_t slot_index, idx_t bit_within_slot_index) const;
445 void set_bit(idx_t slot_index, idx_t bit_within_slot_index);
446 void clear_bit(idx_t slot_index, idx_t bit_within_slot_index);
447 void at_put(idx_t slot_index, idx_t bit_within_slot_index, bool value);
448 void at_put_grow(idx_t slot_index, idx_t bit_within_slot_index, bool value);
449 };
450
451 // Closure for iterating over BitMaps
452
453 class BitMapClosure {
454 public:
455 // Callback when bit in map is set. Should normally return "true";
456 // return of false indicates that the bitmap iteration should terminate.
457 virtual bool do_bit(BitMap::idx_t offset) = 0;
458 };
459
460 #endif // SHARE_UTILITIES_BITMAP_HPP
|
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_UTILITIES_BITMAP_HPP
26 #define SHARE_UTILITIES_BITMAP_HPP
27
28 #include "memory/allocation.hpp"
29 #include "runtime/atomic.hpp"
30
31 // Forward decl;
32 class BitMapClosure;
33
34 // Operations for bitmaps represented as arrays of unsigned integers.
35 // Bits are numbered from 0 to size-1.
36
37 // The "abstract" base BitMap class.
38 //
39 // The constructor and destructor are protected to prevent
40 // creation of BitMap instances outside of the BitMap class.
41 //
42 // The BitMap class doesn't use virtual calls on purpose,
43 // this ensures that we don't get a vtable unnecessarily.
44 //
45 // The allocation of the backing storage for the BitMap are handled by
46 // the subclasses. BitMap doesn't allocate or delete backing storage.
47 class BitMap {
48 friend class BitMap2D;
49
50 public:
51 typedef size_t idx_t; // Type used for bit and word indices.
52 typedef uintptr_t bm_word_t; // Element type of array that represents the
53 // bitmap, with BitsPerWord bits per element.
54 // If this were to fail, there are lots of places that would need repair.
55 STATIC_ASSERT((sizeof(bm_word_t) * BitsPerByte) == BitsPerWord);
56
57 // Hints for range sizes.
58 typedef enum {
59 unknown_range, small_range, large_range
60 } RangeSizeHint;
61
62 private:
63 bm_word_t* _map; // First word in bitmap
64 idx_t _size; // Size of bitmap (in bits)
65
66 // Limit max_size_in_bits so aligning up to a word never overflows.
67 static idx_t max_size_in_words() { return raw_to_words_align_down(~idx_t(0)); }
68 static idx_t max_size_in_bits() { return max_size_in_words() * BitsPerWord; }
69
70 // Assumes relevant validity checking for bit has already been done.
71 static idx_t raw_to_words_align_up(idx_t bit) {
72 return raw_to_words_align_down(bit + (BitsPerWord - 1));
73 }
74
75 // Assumes relevant validity checking for bit has already been done.
76 static idx_t raw_to_words_align_down(idx_t bit) {
77 return bit >> LogBitsPerWord;
78 }
79
80 // Word-aligns bit and converts it to a word offset.
81 // precondition: bit <= size()
82 idx_t to_words_align_up(idx_t bit) const {
83 verify_limit(bit);
84 return raw_to_words_align_up(bit);
85 }
86
87 // Word-aligns bit and converts it to a word offset.
88 // precondition: bit <= size()
89 inline idx_t to_words_align_down(idx_t bit) const {
90 verify_limit(bit);
91 return raw_to_words_align_down(bit);
92 }
93
94 // Helper for get_next_{zero,one}_bit variants.
95 // - flip designates whether searching for 1s or 0s. Must be one of
96 // find_{zeros,ones}_flip.
97 // - aligned_right is true if r_index is a priori on a bm_word_t boundary.
98 template<bm_word_t flip, bool aligned_right>
99 inline idx_t get_next_bit_impl(idx_t l_index, idx_t r_index) const;
100
101 // Values for get_next_bit_impl flip parameter.
102 static const bm_word_t find_ones_flip = 0;
103 static const bm_word_t find_zeros_flip = ~(bm_word_t)0;
104
105 // Threshold for performing small range operation, even when large range
106 // operation was requested. Measured in words.
107 static const size_t small_range_words = 32;
108
109 static bool is_small_range_of_words(idx_t beg_full_word, idx_t end_full_word);
110
111 protected:
112 // Return the position of bit within the word that contains it (e.g., if
113 // bitmap words are 32 bits, return a number 0 <= n <= 31).
114 static idx_t bit_in_word(idx_t bit) { return bit & (BitsPerWord - 1); }
115
116 // Return a mask that will select the specified bit, when applied to the word
117 // containing the bit.
118 static bm_word_t bit_mask(idx_t bit) { return (bm_word_t)1 << bit_in_word(bit); }
119
120 // Return the bit number of the first bit in the specified word.
121 static idx_t bit_index(idx_t word) { return word << LogBitsPerWord; }
122
123 // Return the array of bitmap words, or a specific word from it.
124 bm_word_t* map() { return _map; }
125 const bm_word_t* map() const { return _map; }
126 bm_word_t map(idx_t word) const { return _map[word]; }
127
128 // Return a pointer to the word containing the specified bit.
129 bm_word_t* word_addr(idx_t bit) {
130 return map() + to_words_align_down(bit);
131 }
132 const bm_word_t* word_addr(idx_t bit) const {
133 return map() + to_words_align_down(bit);
134 }
135
136 // Set a word to a specified value or to all ones; clear a word.
137 void set_word (idx_t word, bm_word_t val) { _map[word] = val; }
138 void set_word (idx_t word) { set_word(word, ~(bm_word_t)0); }
139 void clear_word(idx_t word) { _map[word] = 0; }
140
141 static inline const bm_word_t load_word_ordered(const volatile bm_word_t* const addr, atomic_memory_order memory_order);
142
143 // Utilities for ranges of bits. Ranges are half-open [beg, end).
144
145 // Ranges within a single word.
146 bm_word_t inverted_bit_mask_for_range(idx_t beg, idx_t end) const;
147 void set_range_within_word (idx_t beg, idx_t end);
148 void clear_range_within_word (idx_t beg, idx_t end);
149 void par_put_range_within_word (idx_t beg, idx_t end, bool value);
150
151 // Ranges spanning entire words.
152 void set_range_of_words (idx_t beg, idx_t end);
153 void clear_range_of_words (idx_t beg, idx_t end);
154 void set_large_range_of_words (idx_t beg, idx_t end);
155 void clear_large_range_of_words (idx_t beg, idx_t end);
156
157 static void clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end);
158
159 // Verification.
160
161 // Verify size_in_bits does not exceed maximum size.
162 static void verify_size(idx_t size_in_bits) NOT_DEBUG_RETURN;
163 // Verify bit is less than size.
164 void verify_index(idx_t bit) const NOT_DEBUG_RETURN;
165 // Verify bit is not greater than size.
166 void verify_limit(idx_t bit) const NOT_DEBUG_RETURN;
167 // Verify [beg,end) is a valid range, e.g. beg <= end <= size().
168 void verify_range(idx_t beg, idx_t end) const NOT_DEBUG_RETURN;
169
170 // Statistics.
171 static const idx_t* _pop_count_table;
172 static void init_pop_count_table();
173 static idx_t num_set_bits(bm_word_t w);
174 static idx_t num_set_bits_from_table(unsigned char c);
175
176 // Allocation Helpers.
177
178 // Allocates and clears the bitmap memory.
179 template <class Allocator>
180 static bm_word_t* allocate(const Allocator&, idx_t size_in_bits, bool clear = true);
181
182 // Reallocates and clears the new bitmap memory.
183 template <class Allocator>
184 static bm_word_t* reallocate(const Allocator&, bm_word_t* map, idx_t old_size_in_bits, idx_t new_size_in_bits, bool clear = true);
185
186 // Free the bitmap memory.
187 template <class Allocator>
188 static void free(const Allocator&, bm_word_t* map, idx_t size_in_bits);
199 // Set up and clear the bitmap memory.
200 //
201 // Precondition: The bitmap was default constructed and has
202 // not yet had memory allocated via resize or (re)initialize.
203 template <class Allocator>
204 void initialize(const Allocator& allocator, idx_t size_in_bits, bool clear);
205
206 // Set up and clear the bitmap memory.
207 //
208 // Can be called on previously initialized bitmaps.
209 template <class Allocator>
210 void reinitialize(const Allocator& allocator, idx_t new_size_in_bits, bool clear);
211
212 // Set the map and size.
213 void update(bm_word_t* map, idx_t size) {
214 _map = map;
215 _size = size;
216 }
217
218 // Protected constructor and destructor.
219 BitMap(bm_word_t* map, idx_t size_in_bits) : _map(map), _size(size_in_bits) {
220 verify_size(size_in_bits);
221 }
222 ~BitMap() {}
223
224 public:
225 // Pretouch the entire range of memory this BitMap covers.
226 void pretouch();
227
228 // Accessing
229 static idx_t calc_size_in_words(size_t size_in_bits) {
230 verify_size(size_in_bits);
231 return raw_to_words_align_up(size_in_bits);
232 }
233
234 idx_t size() const { return _size; }
235 idx_t size_in_words() const { return calc_size_in_words(size()); }
236 idx_t size_in_bytes() const { return size_in_words() * BytesPerWord; }
237
238 bool at(idx_t index) const {
239 verify_index(index);
240 return (*word_addr(index) & bit_mask(index)) != 0;
241 }
242
243 // memory_order must be memory_order_relaxed or memory_order_acquire.
244 bool par_at(idx_t index, atomic_memory_order memory_order = memory_order_acquire) const;
245
246 // Set or clear the specified bit.
247 inline void set_bit(idx_t bit);
248 inline void clear_bit(idx_t bit);
249
250 // Attempts to change a bit to a desired value. The operation returns true if
251 // this thread changed the value of the bit. It was changed with a RMW operation
252 // using the specified memory_order. The operation returns false if the change
253 // could not be set due to the bit already being observed in the desired state.
254 // The atomic access that observed the bit in the desired state has acquire
255 // semantics, unless memory_order is memory_order_relaxed or memory_order_release.
256 inline bool par_set_bit(idx_t bit, atomic_memory_order memory_order = memory_order_conservative);
257 inline bool par_clear_bit(idx_t bit, atomic_memory_order memory_order = memory_order_conservative);
258
259 // Put the given value at the given index. The parallel version
260 // will CAS the value into the bitmap and is quite a bit slower.
261 // The parallel version also returns a value indicating if the
262 // calling thread was the one that changed the value of the bit.
263 void at_put(idx_t index, bool value);
264 bool par_at_put(idx_t index, bool value);
265
266 // Update a range of bits. Ranges are half-open [beg, end).
267 void set_range (idx_t beg, idx_t end);
268 void clear_range (idx_t beg, idx_t end);
269 void set_large_range (idx_t beg, idx_t end);
270 void clear_large_range (idx_t beg, idx_t end);
271 void at_put_range(idx_t beg, idx_t end, bool value);
272 void par_at_put_range(idx_t beg, idx_t end, bool value);
273 void at_put_large_range(idx_t beg, idx_t end, bool value);
274 void par_at_put_large_range(idx_t beg, idx_t end, bool value);
275
276 // Update a range of bits, using a hint about the size. Currently only
277 // inlines the predominant case of a 1-bit range. Works best when hint is a
278 // compile-time constant.
279 void set_range(idx_t beg, idx_t end, RangeSizeHint hint);
458 _map(size_in_slots * bits_per_slot), _bits_per_slot(bits_per_slot) {}
459
460 idx_t size_in_bits() {
461 return _map.size();
462 }
463
464 bool is_valid_index(idx_t slot_index, idx_t bit_within_slot_index);
465 bool at(idx_t slot_index, idx_t bit_within_slot_index) const;
466 void set_bit(idx_t slot_index, idx_t bit_within_slot_index);
467 void clear_bit(idx_t slot_index, idx_t bit_within_slot_index);
468 void at_put(idx_t slot_index, idx_t bit_within_slot_index, bool value);
469 void at_put_grow(idx_t slot_index, idx_t bit_within_slot_index, bool value);
470 };
471
472 // Closure for iterating over BitMaps
473
474 class BitMapClosure {
475 public:
476 // Callback when bit in map is set. Should normally return "true";
477 // return of false indicates that the bitmap iteration should terminate.
478 virtual bool do_bit(BitMap::idx_t index) = 0;
479 };
480
481 #endif // SHARE_UTILITIES_BITMAP_HPP
|