Mercurial > jdk8-mips64-public > hotspot / file revision
src/share/vm/utilities/bitMap.inline.hpp@c96030fff130
src/share/vm/utilities/bitMap.inline.hpp
Thu, 20 Nov 2008 16:56:09 -0800
- author
- ysr
- date
- Thu, 20 Nov 2008 16:56:09 -0800
- changeset 888
- c96030fff130
- parent 777
- 37f87013dfd8
- child 1244
- 6e2afda171db
- permissions
- -rw-r--r--
6684579: SoftReference processing can be made more efficient
Summary: For current soft-ref clearing policies, we can decide at marking time if a soft-reference will definitely not be cleared, postponing the decision of whether it will definitely be cleared to the final reference processing phase. This can be especially beneficial in the case of concurrent collectors where the marking is usually concurrent but reference processing is usually not.
Reviewed-by: jmasa
1 /*
2 * Copyright 2005-2006 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
22 *
23 */
26 inline void BitMap::set_bit(idx_t bit) {
27 verify_index(bit);
28 *word_addr(bit) |= bit_mask(bit);
29 }
31 inline void BitMap::clear_bit(idx_t bit) {
32 verify_index(bit);
33 *word_addr(bit) &= ~bit_mask(bit);
34 }
36 inline bool BitMap::par_set_bit(idx_t bit) {
37 verify_index(bit);
38 volatile idx_t* const addr = word_addr(bit);
39 const idx_t mask = bit_mask(bit);
40 idx_t old_val = *addr;
42 do {
43 const idx_t new_val = old_val | mask;
44 if (new_val == old_val) {
45 return false; // Someone else beat us to it.
46 }
47 const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val,
48 (volatile void*) addr,
49 (void*) old_val);
50 if (cur_val == old_val) {
51 return true; // Success.
52 }
53 old_val = cur_val; // The value changed, try again.
54 } while (true);
55 }
57 inline bool BitMap::par_clear_bit(idx_t bit) {
58 verify_index(bit);
59 volatile idx_t* const addr = word_addr(bit);
60 const idx_t mask = ~bit_mask(bit);
61 idx_t old_val = *addr;
63 do {
64 const idx_t new_val = old_val & mask;
65 if (new_val == old_val) {
66 return false; // Someone else beat us to it.
67 }
68 const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val,
69 (volatile void*) addr,
70 (void*) old_val);
71 if (cur_val == old_val) {
72 return true; // Success.
73 }
74 old_val = cur_val; // The value changed, try again.
75 } while (true);
76 }
78 inline void BitMap::set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
79 if (hint == small_range && end - beg == 1) {
80 set_bit(beg);
81 } else {
82 if (hint == large_range) {
83 set_large_range(beg, end);
84 } else {
85 set_range(beg, end);
86 }
87 }
88 }
90 inline void BitMap::clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
91 if (hint == small_range && end - beg == 1) {
92 clear_bit(beg);
93 } else {
94 if (hint == large_range) {
95 clear_large_range(beg, end);
96 } else {
97 clear_range(beg, end);
98 }
99 }
100 }
102 inline void BitMap::par_set_range(idx_t beg, idx_t end, RangeSizeHint hint) {
103 if (hint == small_range && end - beg == 1) {
104 par_at_put(beg, true);
105 } else {
106 if (hint == large_range) {
107 par_at_put_large_range(beg, end, true);
108 } else {
109 par_at_put_range(beg, end, true);
110 }
111 }
112 }
114 inline void BitMap::set_range_of_words(idx_t beg, idx_t end) {
115 bm_word_t* map = _map;
116 for (idx_t i = beg; i < end; ++i) map[i] = ~(uintptr_t)0;
117 }
120 inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) {
121 bm_word_t* map = _map;
122 for (idx_t i = beg; i < end; ++i) map[i] = 0;
123 }
126 inline void BitMap::clear() {
127 clear_range_of_words(0, size_in_words());
128 }
131 inline void BitMap::par_clear_range(idx_t beg, idx_t end, RangeSizeHint hint) {
132 if (hint == small_range && end - beg == 1) {
133 par_at_put(beg, false);
134 } else {
135 if (hint == large_range) {
136 par_at_put_large_range(beg, end, false);
137 } else {
138 par_at_put_range(beg, end, false);
139 }
140 }
141 }
143 inline BitMap::idx_t
144 BitMap::get_next_one_offset_inline(idx_t l_offset, idx_t r_offset) const {
145 assert(l_offset <= size(), "BitMap index out of bounds");
146 assert(r_offset <= size(), "BitMap index out of bounds");
147 assert(l_offset <= r_offset, "l_offset > r_offset ?");
149 if (l_offset == r_offset) {
150 return l_offset;
151 }
152 idx_t index = word_index(l_offset);
153 idx_t r_index = word_index(r_offset-1) + 1;
154 idx_t res_offset = l_offset;
156 // check bits including and to the _left_ of offset's position
157 idx_t pos = bit_in_word(res_offset);
158 idx_t res = map(index) >> pos;
159 if (res != (uintptr_t)NoBits) {
160 // find the position of the 1-bit
161 for (; !(res & 1); res_offset++) {
162 res = res >> 1;
163 }
164 assert(res_offset >= l_offset &&
165 res_offset < r_offset, "just checking");
166 return MIN2(res_offset, r_offset);
167 }
168 // skip over all word length 0-bit runs
169 for (index++; index < r_index; index++) {
170 res = map(index);
171 if (res != (uintptr_t)NoBits) {
172 // found a 1, return the offset
173 for (res_offset = bit_index(index); !(res & 1); res_offset++) {
174 res = res >> 1;
175 }
176 assert(res & 1, "tautology; see loop condition");
177 assert(res_offset >= l_offset, "just checking");
178 return MIN2(res_offset, r_offset);
179 }
180 }
181 return r_offset;
182 }
184 inline BitMap::idx_t
185 BitMap::get_next_zero_offset_inline(idx_t l_offset, idx_t r_offset) const {
186 assert(l_offset <= size(), "BitMap index out of bounds");
187 assert(r_offset <= size(), "BitMap index out of bounds");
188 assert(l_offset <= r_offset, "l_offset > r_offset ?");
190 if (l_offset == r_offset) {
191 return l_offset;
192 }
193 idx_t index = word_index(l_offset);
194 idx_t r_index = word_index(r_offset-1) + 1;
195 idx_t res_offset = l_offset;
197 // check bits including and to the _left_ of offset's position
198 idx_t pos = res_offset & (BitsPerWord - 1);
199 idx_t res = (map(index) >> pos) | left_n_bits((int)pos);
201 if (res != (uintptr_t)AllBits) {
202 // find the position of the 0-bit
203 for (; res & 1; res_offset++) {
204 res = res >> 1;
205 }
206 assert(res_offset >= l_offset, "just checking");
207 return MIN2(res_offset, r_offset);
208 }
209 // skip over all word length 1-bit runs
210 for (index++; index < r_index; index++) {
211 res = map(index);
212 if (res != (uintptr_t)AllBits) {
213 // found a 0, return the offset
214 for (res_offset = index << LogBitsPerWord; res & 1;
215 res_offset++) {
216 res = res >> 1;
217 }
218 assert(!(res & 1), "tautology; see loop condition");
219 assert(res_offset >= l_offset, "just checking");
220 return MIN2(res_offset, r_offset);
221 }
222 }
223 return r_offset;
224 }
226 inline BitMap::idx_t
227 BitMap::get_next_one_offset_inline_aligned_right(idx_t l_offset,
228 idx_t r_offset) const
229 {
230 verify_range(l_offset, r_offset);
231 assert(bit_in_word(r_offset) == 0, "r_offset not word-aligned");
233 if (l_offset == r_offset) {
234 return l_offset;
235 }
236 idx_t index = word_index(l_offset);
237 idx_t r_index = word_index(r_offset);
238 idx_t res_offset = l_offset;
240 // check bits including and to the _left_ of offset's position
241 idx_t res = map(index) >> bit_in_word(res_offset);
242 if (res != (uintptr_t)NoBits) {
243 // find the position of the 1-bit
244 for (; !(res & 1); res_offset++) {
245 res = res >> 1;
246 }
247 assert(res_offset >= l_offset &&
248 res_offset < r_offset, "just checking");
249 return res_offset;
250 }
251 // skip over all word length 0-bit runs
252 for (index++; index < r_index; index++) {
253 res = map(index);
254 if (res != (uintptr_t)NoBits) {
255 // found a 1, return the offset
256 for (res_offset = bit_index(index); !(res & 1); res_offset++) {
257 res = res >> 1;
258 }
259 assert(res & 1, "tautology; see loop condition");
260 assert(res_offset >= l_offset && res_offset < r_offset, "just checking");
261 return res_offset;
262 }
263 }
264 return r_offset;
265 }
268 // Returns a bit mask for a range of bits [beg, end) within a single word. Each
269 // bit in the mask is 0 if the bit is in the range, 1 if not in the range. The
270 // returned mask can be used directly to clear the range, or inverted to set the
271 // range. Note: end must not be 0.
272 inline BitMap::bm_word_t
273 BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const {
274 assert(end != 0, "does not work when end == 0");
275 assert(beg == end || word_index(beg) == word_index(end - 1),
276 "must be a single-word range");
277 bm_word_t mask = bit_mask(beg) - 1; // low (right) bits
278 if (bit_in_word(end) != 0) {
279 mask |= ~(bit_mask(end) - 1); // high (left) bits
280 }
281 return mask;
282 }
284 inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) {
285 memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(uintptr_t));
286 }
288 inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) {
289 memset(_map + beg, 0, (end - beg) * sizeof(uintptr_t));
290 }
292 inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const {
293 idx_t bit_rounded_up = bit + (BitsPerWord - 1);
294 // Check for integer arithmetic overflow.
295 return bit_rounded_up > bit ? word_index(bit_rounded_up) : size_in_words();
296 }
298 inline BitMap::idx_t BitMap::get_next_one_offset(idx_t l_offset,
299 idx_t r_offset) const {
300 return get_next_one_offset_inline(l_offset, r_offset);
301 }
303 inline BitMap::idx_t BitMap::get_next_zero_offset(idx_t l_offset,
304 idx_t r_offset) const {
305 return get_next_zero_offset_inline(l_offset, r_offset);
306 }
308 inline void BitMap2D::clear() {
309 _map.clear();
310 }
