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