|
1 /* |
|
2 * Copyright (c) 2005, 2013, 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 |
|
31 #ifdef ASSERT |
|
32 inline void BitMap::verify_index(idx_t index) const { |
|
33 assert(index < _size, "BitMap index out of bounds"); |
|
34 } |
|
35 |
|
36 inline void BitMap::verify_range(idx_t beg_index, idx_t end_index) const { |
|
37 assert(beg_index <= end_index, "BitMap range error"); |
|
38 // Note that [0,0) and [size,size) are both valid ranges. |
|
39 if (end_index != _size) verify_index(end_index); |
|
40 } |
|
41 #endif // #ifdef ASSERT |
|
42 |
|
43 inline void BitMap::set_bit(idx_t bit) { |
|
44 verify_index(bit); |
|
45 *word_addr(bit) |= bit_mask(bit); |
|
46 } |
|
47 |
|
48 inline void BitMap::clear_bit(idx_t bit) { |
|
49 verify_index(bit); |
|
50 *word_addr(bit) &= ~bit_mask(bit); |
|
51 } |
|
52 |
|
53 inline bool BitMap::par_set_bit(idx_t bit) { |
|
54 verify_index(bit); |
|
55 volatile bm_word_t* const addr = word_addr(bit); |
|
56 const bm_word_t mask = bit_mask(bit); |
|
57 bm_word_t old_val = *addr; |
|
58 |
|
59 do { |
|
60 const bm_word_t new_val = old_val | mask; |
|
61 if (new_val == old_val) { |
|
62 return false; // Someone else beat us to it. |
|
63 } |
|
64 const bm_word_t cur_val = (bm_word_t) Atomic::cmpxchg_ptr((void*) new_val, |
|
65 (volatile void*) addr, |
|
66 (void*) old_val); |
|
67 if (cur_val == old_val) { |
|
68 return true; // Success. |
|
69 } |
|
70 old_val = cur_val; // The value changed, try again. |
|
71 } while (true); |
|
72 } |
|
73 |
|
74 inline bool BitMap::par_clear_bit(idx_t bit) { |
|
75 verify_index(bit); |
|
76 volatile bm_word_t* const addr = word_addr(bit); |
|
77 const bm_word_t mask = ~bit_mask(bit); |
|
78 bm_word_t old_val = *addr; |
|
79 |
|
80 do { |
|
81 const bm_word_t new_val = old_val & mask; |
|
82 if (new_val == old_val) { |
|
83 return false; // Someone else beat us to it. |
|
84 } |
|
85 const bm_word_t cur_val = (bm_word_t) Atomic::cmpxchg_ptr((void*) new_val, |
|
86 (volatile void*) addr, |
|
87 (void*) old_val); |
|
88 if (cur_val == old_val) { |
|
89 return true; // Success. |
|
90 } |
|
91 old_val = cur_val; // The value changed, try again. |
|
92 } while (true); |
|
93 } |
|
94 |
|
95 inline void BitMap::set_range(idx_t beg, idx_t end, RangeSizeHint hint) { |
|
96 if (hint == small_range && end - beg == 1) { |
|
97 set_bit(beg); |
|
98 } else { |
|
99 if (hint == large_range) { |
|
100 set_large_range(beg, end); |
|
101 } else { |
|
102 set_range(beg, end); |
|
103 } |
|
104 } |
|
105 } |
|
106 |
|
107 inline void BitMap::clear_range(idx_t beg, idx_t end, RangeSizeHint hint) { |
|
108 if (hint == small_range && end - beg == 1) { |
|
109 clear_bit(beg); |
|
110 } else { |
|
111 if (hint == large_range) { |
|
112 clear_large_range(beg, end); |
|
113 } else { |
|
114 clear_range(beg, end); |
|
115 } |
|
116 } |
|
117 } |
|
118 |
|
119 inline void BitMap::par_set_range(idx_t beg, idx_t end, RangeSizeHint hint) { |
|
120 if (hint == small_range && end - beg == 1) { |
|
121 par_at_put(beg, true); |
|
122 } else { |
|
123 if (hint == large_range) { |
|
124 par_at_put_large_range(beg, end, true); |
|
125 } else { |
|
126 par_at_put_range(beg, end, true); |
|
127 } |
|
128 } |
|
129 } |
|
130 |
|
131 inline void BitMap::set_range_of_words(idx_t beg, idx_t end) { |
|
132 bm_word_t* map = _map; |
|
133 for (idx_t i = beg; i < end; ++i) map[i] = ~(uintptr_t)0; |
|
134 } |
|
135 |
|
136 |
|
137 inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) { |
|
138 bm_word_t* map = _map; |
|
139 for (idx_t i = beg; i < end; ++i) map[i] = 0; |
|
140 } |
|
141 |
|
142 |
|
143 inline void BitMap::clear() { |
|
144 clear_range_of_words(0, size_in_words()); |
|
145 } |
|
146 |
|
147 |
|
148 inline void BitMap::par_clear_range(idx_t beg, idx_t end, RangeSizeHint hint) { |
|
149 if (hint == small_range && end - beg == 1) { |
|
150 par_at_put(beg, false); |
|
151 } else { |
|
152 if (hint == large_range) { |
|
153 par_at_put_large_range(beg, end, false); |
|
154 } else { |
|
155 par_at_put_range(beg, end, false); |
|
156 } |
|
157 } |
|
158 } |
|
159 |
|
160 inline BitMap::idx_t |
|
161 BitMap::get_next_one_offset_inline(idx_t l_offset, idx_t r_offset) const { |
|
162 assert(l_offset <= size(), "BitMap index out of bounds"); |
|
163 assert(r_offset <= size(), "BitMap index out of bounds"); |
|
164 assert(l_offset <= r_offset, "l_offset > r_offset ?"); |
|
165 |
|
166 if (l_offset == r_offset) { |
|
167 return l_offset; |
|
168 } |
|
169 idx_t index = word_index(l_offset); |
|
170 idx_t r_index = word_index(r_offset-1) + 1; |
|
171 idx_t res_offset = l_offset; |
|
172 |
|
173 // check bits including and to the _left_ of offset's position |
|
174 idx_t pos = bit_in_word(res_offset); |
|
175 idx_t res = map(index) >> pos; |
|
176 if (res != (uintptr_t)NoBits) { |
|
177 // find the position of the 1-bit |
|
178 for (; !(res & 1); res_offset++) { |
|
179 res = res >> 1; |
|
180 } |
|
181 |
|
182 #ifdef ASSERT |
|
183 // In the following assert, if r_offset is not bitamp word aligned, |
|
184 // checking that res_offset is strictly less than r_offset is too |
|
185 // strong and will trip the assert. |
|
186 // |
|
187 // Consider the case where l_offset is bit 15 and r_offset is bit 17 |
|
188 // of the same map word, and where bits [15:16:17:18] == [00:00:00:01]. |
|
189 // All the bits in the range [l_offset:r_offset) are 0. |
|
190 // The loop that calculates res_offset, above, would yield the offset |
|
191 // of bit 18 because it's in the same map word as l_offset and there |
|
192 // is a set bit in that map word above l_offset (i.e. res != NoBits). |
|
193 // |
|
194 // In this case, however, we can assert is that res_offset is strictly |
|
195 // less than size() since we know that there is at least one set bit |
|
196 // at an offset above, but in the same map word as, r_offset. |
|
197 // Otherwise, if r_offset is word aligned then it will not be in the |
|
198 // same map word as l_offset (unless it equals l_offset). So either |
|
199 // there won't be a set bit between l_offset and the end of it's map |
|
200 // word (i.e. res == NoBits), or res_offset will be less than r_offset. |
|
201 |
|
202 idx_t limit = is_word_aligned(r_offset) ? r_offset : size(); |
|
203 assert(res_offset >= l_offset && res_offset < limit, "just checking"); |
|
204 #endif // ASSERT |
|
205 return MIN2(res_offset, r_offset); |
|
206 } |
|
207 // skip over all word length 0-bit runs |
|
208 for (index++; index < r_index; index++) { |
|
209 res = map(index); |
|
210 if (res != (uintptr_t)NoBits) { |
|
211 // found a 1, return the offset |
|
212 for (res_offset = bit_index(index); !(res & 1); res_offset++) { |
|
213 res = res >> 1; |
|
214 } |
|
215 assert(res & 1, "tautology; see loop condition"); |
|
216 assert(res_offset >= l_offset, "just checking"); |
|
217 return MIN2(res_offset, r_offset); |
|
218 } |
|
219 } |
|
220 return r_offset; |
|
221 } |
|
222 |
|
223 inline BitMap::idx_t |
|
224 BitMap::get_next_zero_offset_inline(idx_t l_offset, idx_t r_offset) const { |
|
225 assert(l_offset <= size(), "BitMap index out of bounds"); |
|
226 assert(r_offset <= size(), "BitMap index out of bounds"); |
|
227 assert(l_offset <= r_offset, "l_offset > r_offset ?"); |
|
228 |
|
229 if (l_offset == r_offset) { |
|
230 return l_offset; |
|
231 } |
|
232 idx_t index = word_index(l_offset); |
|
233 idx_t r_index = word_index(r_offset-1) + 1; |
|
234 idx_t res_offset = l_offset; |
|
235 |
|
236 // check bits including and to the _left_ of offset's position |
|
237 idx_t pos = res_offset & (BitsPerWord - 1); |
|
238 idx_t res = (map(index) >> pos) | left_n_bits((int)pos); |
|
239 |
|
240 if (res != (uintptr_t)AllBits) { |
|
241 // find the position of the 0-bit |
|
242 for (; res & 1; res_offset++) { |
|
243 res = res >> 1; |
|
244 } |
|
245 assert(res_offset >= l_offset, "just checking"); |
|
246 return MIN2(res_offset, r_offset); |
|
247 } |
|
248 // skip over all word length 1-bit runs |
|
249 for (index++; index < r_index; index++) { |
|
250 res = map(index); |
|
251 if (res != (uintptr_t)AllBits) { |
|
252 // found a 0, return the offset |
|
253 for (res_offset = index << LogBitsPerWord; res & 1; |
|
254 res_offset++) { |
|
255 res = res >> 1; |
|
256 } |
|
257 assert(!(res & 1), "tautology; see loop condition"); |
|
258 assert(res_offset >= l_offset, "just checking"); |
|
259 return MIN2(res_offset, r_offset); |
|
260 } |
|
261 } |
|
262 return r_offset; |
|
263 } |
|
264 |
|
265 inline BitMap::idx_t |
|
266 BitMap::get_next_one_offset_inline_aligned_right(idx_t l_offset, |
|
267 idx_t r_offset) const |
|
268 { |
|
269 verify_range(l_offset, r_offset); |
|
270 assert(bit_in_word(r_offset) == 0, "r_offset not word-aligned"); |
|
271 |
|
272 if (l_offset == r_offset) { |
|
273 return l_offset; |
|
274 } |
|
275 idx_t index = word_index(l_offset); |
|
276 idx_t r_index = word_index(r_offset); |
|
277 idx_t res_offset = l_offset; |
|
278 |
|
279 // check bits including and to the _left_ of offset's position |
|
280 idx_t res = map(index) >> bit_in_word(res_offset); |
|
281 if (res != (uintptr_t)NoBits) { |
|
282 // find the position of the 1-bit |
|
283 for (; !(res & 1); res_offset++) { |
|
284 res = res >> 1; |
|
285 } |
|
286 assert(res_offset >= l_offset && |
|
287 res_offset < r_offset, "just checking"); |
|
288 return res_offset; |
|
289 } |
|
290 // skip over all word length 0-bit runs |
|
291 for (index++; index < r_index; index++) { |
|
292 res = map(index); |
|
293 if (res != (uintptr_t)NoBits) { |
|
294 // found a 1, return the offset |
|
295 for (res_offset = bit_index(index); !(res & 1); res_offset++) { |
|
296 res = res >> 1; |
|
297 } |
|
298 assert(res & 1, "tautology; see loop condition"); |
|
299 assert(res_offset >= l_offset && res_offset < r_offset, "just checking"); |
|
300 return res_offset; |
|
301 } |
|
302 } |
|
303 return r_offset; |
|
304 } |
|
305 |
|
306 |
|
307 // Returns a bit mask for a range of bits [beg, end) within a single word. Each |
|
308 // bit in the mask is 0 if the bit is in the range, 1 if not in the range. The |
|
309 // returned mask can be used directly to clear the range, or inverted to set the |
|
310 // range. Note: end must not be 0. |
|
311 inline BitMap::bm_word_t |
|
312 BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const { |
|
313 assert(end != 0, "does not work when end == 0"); |
|
314 assert(beg == end || word_index(beg) == word_index(end - 1), |
|
315 "must be a single-word range"); |
|
316 bm_word_t mask = bit_mask(beg) - 1; // low (right) bits |
|
317 if (bit_in_word(end) != 0) { |
|
318 mask |= ~(bit_mask(end) - 1); // high (left) bits |
|
319 } |
|
320 return mask; |
|
321 } |
|
322 |
|
323 inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) { |
|
324 memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(uintptr_t)); |
|
325 } |
|
326 |
|
327 inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) { |
|
328 memset(_map + beg, 0, (end - beg) * sizeof(uintptr_t)); |
|
329 } |
|
330 |
|
331 inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const { |
|
332 idx_t bit_rounded_up = bit + (BitsPerWord - 1); |
|
333 // Check for integer arithmetic overflow. |
|
334 return bit_rounded_up > bit ? word_index(bit_rounded_up) : size_in_words(); |
|
335 } |
|
336 |
|
337 inline BitMap::idx_t BitMap::get_next_one_offset(idx_t l_offset, |
|
338 idx_t r_offset) const { |
|
339 return get_next_one_offset_inline(l_offset, r_offset); |
|
340 } |
|
341 |
|
342 inline BitMap::idx_t BitMap::get_next_zero_offset(idx_t l_offset, |
|
343 idx_t r_offset) const { |
|
344 return get_next_zero_offset_inline(l_offset, r_offset); |
|
345 } |
|
346 |
|
347 inline void BitMap2D::clear() { |
|
348 _map.clear(); |
|
349 } |
|
350 |
|
351 #endif // SHARE_VM_UTILITIES_BITMAP_INLINE_HPP |