1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/share/vm/utilities/bitMap.inline.hpp Wed Apr 27 01:25:04 2016 +0800 1.3 @@ -0,0 +1,351 @@ 1.4 +/* 1.5 + * Copyright (c) 2005, 2013, Oracle and/or its affiliates. All rights reserved. 1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1.7 + * 1.8 + * This code is free software; you can redistribute it and/or modify it 1.9 + * under the terms of the GNU General Public License version 2 only, as 1.10 + * published by the Free Software Foundation. 1.11 + * 1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT 1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1.15 + * version 2 for more details (a copy is included in the LICENSE file that 1.16 + * accompanied this code). 1.17 + * 1.18 + * You should have received a copy of the GNU General Public License version 1.19 + * 2 along with this work; if not, write to the Free Software Foundation, 1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1.21 + * 1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 1.23 + * or visit www.oracle.com if you need additional information or have any 1.24 + * questions. 1.25 + * 1.26 + */ 1.27 + 1.28 +#ifndef SHARE_VM_UTILITIES_BITMAP_INLINE_HPP 1.29 +#define SHARE_VM_UTILITIES_BITMAP_INLINE_HPP 1.30 + 1.31 +#include "runtime/atomic.hpp" 1.32 +#include "utilities/bitMap.hpp" 1.33 + 1.34 +#ifdef ASSERT 1.35 +inline void BitMap::verify_index(idx_t index) const { 1.36 + assert(index < _size, "BitMap index out of bounds"); 1.37 +} 1.38 + 1.39 +inline void BitMap::verify_range(idx_t beg_index, idx_t end_index) const { 1.40 + assert(beg_index <= end_index, "BitMap range error"); 1.41 + // Note that [0,0) and [size,size) are both valid ranges. 1.42 + if (end_index != _size) verify_index(end_index); 1.43 +} 1.44 +#endif // #ifdef ASSERT 1.45 + 1.46 +inline void BitMap::set_bit(idx_t bit) { 1.47 + verify_index(bit); 1.48 + *word_addr(bit) |= bit_mask(bit); 1.49 +} 1.50 + 1.51 +inline void BitMap::clear_bit(idx_t bit) { 1.52 + verify_index(bit); 1.53 + *word_addr(bit) &= ~bit_mask(bit); 1.54 +} 1.55 + 1.56 +inline bool BitMap::par_set_bit(idx_t bit) { 1.57 + verify_index(bit); 1.58 + volatile bm_word_t* const addr = word_addr(bit); 1.59 + const bm_word_t mask = bit_mask(bit); 1.60 + bm_word_t old_val = *addr; 1.61 + 1.62 + do { 1.63 + const bm_word_t new_val = old_val | mask; 1.64 + if (new_val == old_val) { 1.65 + return false; // Someone else beat us to it. 1.66 + } 1.67 + const bm_word_t cur_val = (bm_word_t) Atomic::cmpxchg_ptr((void*) new_val, 1.68 + (volatile void*) addr, 1.69 + (void*) old_val); 1.70 + if (cur_val == old_val) { 1.71 + return true; // Success. 1.72 + } 1.73 + old_val = cur_val; // The value changed, try again. 1.74 + } while (true); 1.75 +} 1.76 + 1.77 +inline bool BitMap::par_clear_bit(idx_t bit) { 1.78 + verify_index(bit); 1.79 + volatile bm_word_t* const addr = word_addr(bit); 1.80 + const bm_word_t mask = ~bit_mask(bit); 1.81 + bm_word_t old_val = *addr; 1.82 + 1.83 + do { 1.84 + const bm_word_t new_val = old_val & mask; 1.85 + if (new_val == old_val) { 1.86 + return false; // Someone else beat us to it. 1.87 + } 1.88 + const bm_word_t cur_val = (bm_word_t) Atomic::cmpxchg_ptr((void*) new_val, 1.89 + (volatile void*) addr, 1.90 + (void*) old_val); 1.91 + if (cur_val == old_val) { 1.92 + return true; // Success. 1.93 + } 1.94 + old_val = cur_val; // The value changed, try again. 1.95 + } while (true); 1.96 +} 1.97 + 1.98 +inline void BitMap::set_range(idx_t beg, idx_t end, RangeSizeHint hint) { 1.99 + if (hint == small_range && end - beg == 1) { 1.100 + set_bit(beg); 1.101 + } else { 1.102 + if (hint == large_range) { 1.103 + set_large_range(beg, end); 1.104 + } else { 1.105 + set_range(beg, end); 1.106 + } 1.107 + } 1.108 +} 1.109 + 1.110 +inline void BitMap::clear_range(idx_t beg, idx_t end, RangeSizeHint hint) { 1.111 + if (hint == small_range && end - beg == 1) { 1.112 + clear_bit(beg); 1.113 + } else { 1.114 + if (hint == large_range) { 1.115 + clear_large_range(beg, end); 1.116 + } else { 1.117 + clear_range(beg, end); 1.118 + } 1.119 + } 1.120 +} 1.121 + 1.122 +inline void BitMap::par_set_range(idx_t beg, idx_t end, RangeSizeHint hint) { 1.123 + if (hint == small_range && end - beg == 1) { 1.124 + par_at_put(beg, true); 1.125 + } else { 1.126 + if (hint == large_range) { 1.127 + par_at_put_large_range(beg, end, true); 1.128 + } else { 1.129 + par_at_put_range(beg, end, true); 1.130 + } 1.131 + } 1.132 +} 1.133 + 1.134 +inline void BitMap::set_range_of_words(idx_t beg, idx_t end) { 1.135 + bm_word_t* map = _map; 1.136 + for (idx_t i = beg; i < end; ++i) map[i] = ~(uintptr_t)0; 1.137 +} 1.138 + 1.139 + 1.140 +inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) { 1.141 + bm_word_t* map = _map; 1.142 + for (idx_t i = beg; i < end; ++i) map[i] = 0; 1.143 +} 1.144 + 1.145 + 1.146 +inline void BitMap::clear() { 1.147 + clear_range_of_words(0, size_in_words()); 1.148 +} 1.149 + 1.150 + 1.151 +inline void BitMap::par_clear_range(idx_t beg, idx_t end, RangeSizeHint hint) { 1.152 + if (hint == small_range && end - beg == 1) { 1.153 + par_at_put(beg, false); 1.154 + } else { 1.155 + if (hint == large_range) { 1.156 + par_at_put_large_range(beg, end, false); 1.157 + } else { 1.158 + par_at_put_range(beg, end, false); 1.159 + } 1.160 + } 1.161 +} 1.162 + 1.163 +inline BitMap::idx_t 1.164 +BitMap::get_next_one_offset_inline(idx_t l_offset, idx_t r_offset) const { 1.165 + assert(l_offset <= size(), "BitMap index out of bounds"); 1.166 + assert(r_offset <= size(), "BitMap index out of bounds"); 1.167 + assert(l_offset <= r_offset, "l_offset > r_offset ?"); 1.168 + 1.169 + if (l_offset == r_offset) { 1.170 + return l_offset; 1.171 + } 1.172 + idx_t index = word_index(l_offset); 1.173 + idx_t r_index = word_index(r_offset-1) + 1; 1.174 + idx_t res_offset = l_offset; 1.175 + 1.176 + // check bits including and to the _left_ of offset's position 1.177 + idx_t pos = bit_in_word(res_offset); 1.178 + idx_t res = map(index) >> pos; 1.179 + if (res != (uintptr_t)NoBits) { 1.180 + // find the position of the 1-bit 1.181 + for (; !(res & 1); res_offset++) { 1.182 + res = res >> 1; 1.183 + } 1.184 + 1.185 +#ifdef ASSERT 1.186 + // In the following assert, if r_offset is not bitamp word aligned, 1.187 + // checking that res_offset is strictly less than r_offset is too 1.188 + // strong and will trip the assert. 1.189 + // 1.190 + // Consider the case where l_offset is bit 15 and r_offset is bit 17 1.191 + // of the same map word, and where bits [15:16:17:18] == [00:00:00:01]. 1.192 + // All the bits in the range [l_offset:r_offset) are 0. 1.193 + // The loop that calculates res_offset, above, would yield the offset 1.194 + // of bit 18 because it's in the same map word as l_offset and there 1.195 + // is a set bit in that map word above l_offset (i.e. res != NoBits). 1.196 + // 1.197 + // In this case, however, we can assert is that res_offset is strictly 1.198 + // less than size() since we know that there is at least one set bit 1.199 + // at an offset above, but in the same map word as, r_offset. 1.200 + // Otherwise, if r_offset is word aligned then it will not be in the 1.201 + // same map word as l_offset (unless it equals l_offset). So either 1.202 + // there won't be a set bit between l_offset and the end of it's map 1.203 + // word (i.e. res == NoBits), or res_offset will be less than r_offset. 1.204 + 1.205 + idx_t limit = is_word_aligned(r_offset) ? r_offset : size(); 1.206 + assert(res_offset >= l_offset && res_offset < limit, "just checking"); 1.207 +#endif // ASSERT 1.208 + return MIN2(res_offset, r_offset); 1.209 + } 1.210 + // skip over all word length 0-bit runs 1.211 + for (index++; index < r_index; index++) { 1.212 + res = map(index); 1.213 + if (res != (uintptr_t)NoBits) { 1.214 + // found a 1, return the offset 1.215 + for (res_offset = bit_index(index); !(res & 1); res_offset++) { 1.216 + res = res >> 1; 1.217 + } 1.218 + assert(res & 1, "tautology; see loop condition"); 1.219 + assert(res_offset >= l_offset, "just checking"); 1.220 + return MIN2(res_offset, r_offset); 1.221 + } 1.222 + } 1.223 + return r_offset; 1.224 +} 1.225 + 1.226 +inline BitMap::idx_t 1.227 +BitMap::get_next_zero_offset_inline(idx_t l_offset, idx_t r_offset) const { 1.228 + assert(l_offset <= size(), "BitMap index out of bounds"); 1.229 + assert(r_offset <= size(), "BitMap index out of bounds"); 1.230 + assert(l_offset <= r_offset, "l_offset > r_offset ?"); 1.231 + 1.232 + if (l_offset == r_offset) { 1.233 + return l_offset; 1.234 + } 1.235 + idx_t index = word_index(l_offset); 1.236 + idx_t r_index = word_index(r_offset-1) + 1; 1.237 + idx_t res_offset = l_offset; 1.238 + 1.239 + // check bits including and to the _left_ of offset's position 1.240 + idx_t pos = res_offset & (BitsPerWord - 1); 1.241 + idx_t res = (map(index) >> pos) | left_n_bits((int)pos); 1.242 + 1.243 + if (res != (uintptr_t)AllBits) { 1.244 + // find the position of the 0-bit 1.245 + for (; res & 1; res_offset++) { 1.246 + res = res >> 1; 1.247 + } 1.248 + assert(res_offset >= l_offset, "just checking"); 1.249 + return MIN2(res_offset, r_offset); 1.250 + } 1.251 + // skip over all word length 1-bit runs 1.252 + for (index++; index < r_index; index++) { 1.253 + res = map(index); 1.254 + if (res != (uintptr_t)AllBits) { 1.255 + // found a 0, return the offset 1.256 + for (res_offset = index << LogBitsPerWord; res & 1; 1.257 + res_offset++) { 1.258 + res = res >> 1; 1.259 + } 1.260 + assert(!(res & 1), "tautology; see loop condition"); 1.261 + assert(res_offset >= l_offset, "just checking"); 1.262 + return MIN2(res_offset, r_offset); 1.263 + } 1.264 + } 1.265 + return r_offset; 1.266 +} 1.267 + 1.268 +inline BitMap::idx_t 1.269 +BitMap::get_next_one_offset_inline_aligned_right(idx_t l_offset, 1.270 + idx_t r_offset) const 1.271 +{ 1.272 + verify_range(l_offset, r_offset); 1.273 + assert(bit_in_word(r_offset) == 0, "r_offset not word-aligned"); 1.274 + 1.275 + if (l_offset == r_offset) { 1.276 + return l_offset; 1.277 + } 1.278 + idx_t index = word_index(l_offset); 1.279 + idx_t r_index = word_index(r_offset); 1.280 + idx_t res_offset = l_offset; 1.281 + 1.282 + // check bits including and to the _left_ of offset's position 1.283 + idx_t res = map(index) >> bit_in_word(res_offset); 1.284 + if (res != (uintptr_t)NoBits) { 1.285 + // find the position of the 1-bit 1.286 + for (; !(res & 1); res_offset++) { 1.287 + res = res >> 1; 1.288 + } 1.289 + assert(res_offset >= l_offset && 1.290 + res_offset < r_offset, "just checking"); 1.291 + return res_offset; 1.292 + } 1.293 + // skip over all word length 0-bit runs 1.294 + for (index++; index < r_index; index++) { 1.295 + res = map(index); 1.296 + if (res != (uintptr_t)NoBits) { 1.297 + // found a 1, return the offset 1.298 + for (res_offset = bit_index(index); !(res & 1); res_offset++) { 1.299 + res = res >> 1; 1.300 + } 1.301 + assert(res & 1, "tautology; see loop condition"); 1.302 + assert(res_offset >= l_offset && res_offset < r_offset, "just checking"); 1.303 + return res_offset; 1.304 + } 1.305 + } 1.306 + return r_offset; 1.307 +} 1.308 + 1.309 + 1.310 +// Returns a bit mask for a range of bits [beg, end) within a single word. Each 1.311 +// bit in the mask is 0 if the bit is in the range, 1 if not in the range. The 1.312 +// returned mask can be used directly to clear the range, or inverted to set the 1.313 +// range. Note: end must not be 0. 1.314 +inline BitMap::bm_word_t 1.315 +BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const { 1.316 + assert(end != 0, "does not work when end == 0"); 1.317 + assert(beg == end || word_index(beg) == word_index(end - 1), 1.318 + "must be a single-word range"); 1.319 + bm_word_t mask = bit_mask(beg) - 1; // low (right) bits 1.320 + if (bit_in_word(end) != 0) { 1.321 + mask |= ~(bit_mask(end) - 1); // high (left) bits 1.322 + } 1.323 + return mask; 1.324 +} 1.325 + 1.326 +inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) { 1.327 + memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(uintptr_t)); 1.328 +} 1.329 + 1.330 +inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) { 1.331 + memset(_map + beg, 0, (end - beg) * sizeof(uintptr_t)); 1.332 +} 1.333 + 1.334 +inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const { 1.335 + idx_t bit_rounded_up = bit + (BitsPerWord - 1); 1.336 + // Check for integer arithmetic overflow. 1.337 + return bit_rounded_up > bit ? word_index(bit_rounded_up) : size_in_words(); 1.338 +} 1.339 + 1.340 +inline BitMap::idx_t BitMap::get_next_one_offset(idx_t l_offset, 1.341 + idx_t r_offset) const { 1.342 + return get_next_one_offset_inline(l_offset, r_offset); 1.343 +} 1.344 + 1.345 +inline BitMap::idx_t BitMap::get_next_zero_offset(idx_t l_offset, 1.346 + idx_t r_offset) const { 1.347 + return get_next_zero_offset_inline(l_offset, r_offset); 1.348 +} 1.349 + 1.350 +inline void BitMap2D::clear() { 1.351 + _map.clear(); 1.352 +} 1.353 + 1.354 +#endif // SHARE_VM_UTILITIES_BITMAP_INLINE_HPP