1 /*
  2  * Copyright (c) 2005, 2020, Oracle and/or its affiliates. All rights reserved.
  3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  4  *
  5  * This code is free software; you can redistribute it and/or modify it
  6  * under the terms of the GNU General Public License version 2 only, as
  7  * published by the Free Software Foundation.
  8  *
  9  * This code is distributed in the hope that it will be useful, but WITHOUT
 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_INLINE_HPP
 26 #define SHARE_UTILITIES_BITMAP_INLINE_HPP
 27 
 28 #include "utilities/bitMap.hpp"
 29 
 30 #include "runtime/atomic.hpp"
 31 #include "utilities/align.hpp"
 32 #include "utilities/count_trailing_zeros.hpp"
 33 
 34 inline void BitMap::set_bit(idx_t bit) {
 35   verify_index(bit);
 36   *word_addr(bit) |= bit_mask(bit);
 37 }
 38 
 39 inline void BitMap::clear_bit(idx_t bit) {
 40   verify_index(bit);
 41   *word_addr(bit) &= ~bit_mask(bit);
 42 }
 43 
 44 inline const BitMap::bm_word_t BitMap::load_word_ordered(const volatile bm_word_t* const addr, atomic_memory_order memory_order) {
 45   if (memory_order == memory_order_relaxed || memory_order == memory_order_release) {
 46     return Atomic::load(addr);
 47   } else {
 48     assert(memory_order == memory_order_acq_rel ||
 49            memory_order == memory_order_acquire ||
 50            memory_order == memory_order_conservative,
 51            "unexpected memory ordering");
 52     return Atomic::load_acquire(addr);
 53   }
 54 }
 55 
 56 inline bool BitMap::par_at(idx_t index, atomic_memory_order memory_order) const {
 57   verify_index(index);
 58   assert(memory_order == memory_order_acquire ||
 59          memory_order == memory_order_relaxed,
 60          "unexpected memory ordering");
 61   const volatile bm_word_t* const addr = word_addr(index);
 62   return (load_word_ordered(addr, memory_order) & bit_mask(index)) != 0;
 63 }
 64 
 65 inline bool BitMap::par_set_bit(idx_t bit, atomic_memory_order memory_order) {
 66   verify_index(bit);
 67   volatile bm_word_t* const addr = word_addr(bit);
 68   const bm_word_t mask = bit_mask(bit);
 69   bm_word_t old_val = load_word_ordered(addr, memory_order);
 70 
 71   do {
 72     const bm_word_t new_val = old_val | mask;
 73     if (new_val == old_val) {
 74       return false;     // Someone else beat us to it.
 75     }
 76     const bm_word_t cur_val = Atomic::cmpxchg(addr, old_val, new_val, memory_order);
 77     if (cur_val == old_val) {
 78       return true;      // Success.
 79     }
 80     old_val = cur_val;  // The value changed, try again.
 81   } while (true);
 82 }
 83 
 84 inline bool BitMap::par_clear_bit(idx_t bit, atomic_memory_order memory_order) {
 85   verify_index(bit);
 86   volatile bm_word_t* const addr = word_addr(bit);
 87   const bm_word_t mask = ~bit_mask(bit);
 88   bm_word_t old_val = load_word_ordered(addr, memory_order);
 89 
 90   do {
 91     const bm_word_t new_val = old_val & mask;
 92     if (new_val == old_val) {
 93       return false;     // Someone else beat us to it.
 94     }
 95     const bm_word_t cur_val = Atomic::cmpxchg(addr, old_val, new_val, memory_order);
 96     if (cur_val == old_val) {
 97       return true;      // Success.
 98     }
 99     old_val = cur_val;  // The value changed, try again.
100   } while (true);
101 }
102 
103 inline void BitMap::set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
104   if (hint == small_range && end - beg == 1) {
105     set_bit(beg);
106   } else {
107     if (hint == large_range) {
108       set_large_range(beg, end);
109     } else {
110       set_range(beg, end);
111     }
112   }
113 }
114 
115 inline void BitMap::clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
116   if (end - beg == 1) {
117     clear_bit(beg);
118   } else {
119     if (hint == large_range) {
120       clear_large_range(beg, end);
121     } else {
122       clear_range(beg, end);
123     }
124   }
125 }
126 
127 inline void BitMap::par_set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
128   if (hint == small_range && end - beg == 1) {
129     par_at_put(beg, true);
130   } else {
131     if (hint == large_range) {
132       par_at_put_large_range(beg, end, true);
133     } else {
134       par_at_put_range(beg, end, true);
135     }
136   }
137 }
138 
139 inline void BitMap::set_range_of_words(idx_t beg, idx_t end) {
140   bm_word_t* map = _map;
141   for (idx_t i = beg; i < end; ++i) map[i] = ~(bm_word_t)0;
142 }
143 
144 inline void BitMap::clear_range_of_words(bm_word_t* map, idx_t beg, idx_t end) {
145   for (idx_t i = beg; i < end; ++i) map[i] = 0;
146 }
147 
148 inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) {
149   clear_range_of_words(_map, beg, end);
150 }
151 
152 inline void BitMap::clear() {
153   clear_range_of_words(0, size_in_words());
154 }
155 
156 inline void BitMap::par_clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
157   if (hint == small_range && end - beg == 1) {
158     par_at_put(beg, false);
159   } else {
160     if (hint == large_range) {
161       par_at_put_large_range(beg, end, false);
162     } else {
163       par_at_put_range(beg, end, false);
164     }
165   }
166 }
167 
168 template<BitMap::bm_word_t flip, bool aligned_right>
169 inline BitMap::idx_t BitMap::get_next_bit_impl(idx_t l_index, idx_t r_index) const {
170   STATIC_ASSERT(flip == find_ones_flip || flip == find_zeros_flip);
171   verify_range(l_index, r_index);
172   assert(!aligned_right || is_aligned(r_index, BitsPerWord), "r_index not aligned");
173 
174   // The first word often contains an interesting bit, either due to
175   // density or because of features of the calling algorithm.  So it's
176   // important to examine that first word with a minimum of fuss,
177   // minimizing setup time for later words that will be wasted if the
178   // first word is indeed interesting.
179 
180   // The benefit from aligned_right being true is relatively small.
181   // It saves an operation in the setup for the word search loop.
182   // It also eliminates the range check on the final result.
183   // However, callers often have a comparison with r_index, and
184   // inlining often allows the two comparisons to be combined; it is
185   // important when !aligned_right that return paths either return
186   // r_index or a value dominated by a comparison with r_index.
187   // aligned_right is still helpful when the caller doesn't have a
188   // range check because features of the calling algorithm guarantee
189   // an interesting bit will be present.
190 
191   if (l_index < r_index) {
192     // Get the word containing l_index, and shift out low bits.
193     idx_t index = to_words_align_down(l_index);
194     bm_word_t cword = (map(index) ^ flip) >> bit_in_word(l_index);
195     if ((cword & 1) != 0) {
196       // The first bit is similarly often interesting. When it matters
197       // (density or features of the calling algorithm make it likely
198       // the first bit is set), going straight to the next clause compares
199       // poorly with doing this check first; count_trailing_zeros can be
200       // relatively expensive, plus there is the additional range check.
201       // But when the first bit isn't set, the cost of having tested for
202       // it is relatively small compared to the rest of the search.
203       return l_index;
204     } else if (cword != 0) {
205       // Flipped and shifted first word is non-zero.
206       idx_t result = l_index + count_trailing_zeros(cword);
207       if (aligned_right || (result < r_index)) return result;
208       // Result is beyond range bound; return r_index.
209     } else {
210       // Flipped and shifted first word is zero.  Word search through
211       // aligned up r_index for a non-zero flipped word.
212       idx_t limit = aligned_right
213         ? to_words_align_down(r_index) // Miniscule savings when aligned.
214         : to_words_align_up(r_index);
215       while (++index < limit) {
216         cword = map(index) ^ flip;
217         if (cword != 0) {
218           idx_t result = bit_index(index) + count_trailing_zeros(cword);
219           if (aligned_right || (result < r_index)) return result;
220           // Result is beyond range bound; return r_index.
221           assert((index + 1) == limit, "invariant");
222           break;
223         }
224       }
225       // No bits in range; return r_index.
226     }
227   }
228   return r_index;
229 }
230 
231 inline BitMap::idx_t
232 BitMap::get_next_one_offset(idx_t l_offset, idx_t r_offset) const {
233   return get_next_bit_impl<find_ones_flip, false>(l_offset, r_offset);
234 }
235 
236 inline BitMap::idx_t
237 BitMap::get_next_zero_offset(idx_t l_offset, idx_t r_offset) const {
238   return get_next_bit_impl<find_zeros_flip, false>(l_offset, r_offset);
239 }
240 
241 inline BitMap::idx_t
242 BitMap::get_next_one_offset_aligned_right(idx_t l_offset, idx_t r_offset) const {
243   return get_next_bit_impl<find_ones_flip, true>(l_offset, r_offset);
244 }
245 
246 inline bool BitMap::iterate(BitMapClosure* cl, idx_t beg, idx_t end) {
247   for (idx_t index = beg; true; ++index) {
248     index = get_next_one_offset(index, end);
249     if (index >= end) {
250       return true;
251     } else if (!cl->do_bit(index)) {
252       return false;
253     }
254   }
255 }
256 
257 inline bool BitMap::iterate(BitMapClosure* cl) {
258   return iterate(cl, 0, size());
259 }
260 
261 // Returns a bit mask for a range of bits [beg, end) within a single word.  Each
262 // bit in the mask is 0 if the bit is in the range, 1 if not in the range.  The
263 // returned mask can be used directly to clear the range, or inverted to set the
264 // range.  Note:  end must not be 0.
265 inline BitMap::bm_word_t
266 BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const {
267   assert(end != 0, "does not work when end == 0");
268   assert(beg == end || to_words_align_down(beg) == to_words_align_down(end - 1),
269          "must be a single-word range");
270   bm_word_t mask = bit_mask(beg) - 1;   // low (right) bits
271   if (bit_in_word(end) != 0) {
272     mask |= ~(bit_mask(end) - 1);       // high (left) bits
273   }
274   return mask;
275 }
276 
277 inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) {
278   assert(beg <= end, "underflow");
279   memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(bm_word_t));
280 }
281 
282 inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) {
283   assert(beg <= end, "underflow");
284   memset(_map + beg, 0, (end - beg) * sizeof(bm_word_t));
285 }
286 
287 inline bool BitMap2D::is_valid_index(idx_t slot_index, idx_t bit_within_slot_index) {
288   verify_bit_within_slot_index(bit_within_slot_index);
289   return (bit_index(slot_index, bit_within_slot_index) < size_in_bits());
290 }
291 
292 inline bool BitMap2D::at(idx_t slot_index, idx_t bit_within_slot_index) const {
293   verify_bit_within_slot_index(bit_within_slot_index);
294   return _map.at(bit_index(slot_index, bit_within_slot_index));
295 }
296 
297 inline void BitMap2D::set_bit(idx_t slot_index, idx_t bit_within_slot_index) {
298   verify_bit_within_slot_index(bit_within_slot_index);
299   _map.set_bit(bit_index(slot_index, bit_within_slot_index));
300 }
301 
302 inline void BitMap2D::clear_bit(idx_t slot_index, idx_t bit_within_slot_index) {
303   verify_bit_within_slot_index(bit_within_slot_index);
304   _map.clear_bit(bit_index(slot_index, bit_within_slot_index));
305 }
306 
307 inline void BitMap2D::at_put(idx_t slot_index, idx_t bit_within_slot_index, bool value) {
308   verify_bit_within_slot_index(bit_within_slot_index);
309   _map.at_put(bit_index(slot_index, bit_within_slot_index), value);
310 }
311 
312 inline void BitMap2D::at_put_grow(idx_t slot_index, idx_t bit_within_slot_index, bool value) {
313   verify_bit_within_slot_index(bit_within_slot_index);
314 
315   idx_t bit = bit_index(slot_index, bit_within_slot_index);
316   if (bit >= _map.size()) {
317     _map.resize(2 * MAX2(_map.size(), bit));
318   }
319   _map.at_put(bit, value);
320 }
321 
322 #endif // SHARE_UTILITIES_BITMAP_INLINE_HPP