Mercurial > hg > truffle
annotate src/share/vm/utilities/bitMap.cpp @ 1716:be3f9c242c9d
6948538: CMS: BOT walkers can fall into object allocation and initialization cracks
Summary: GC workers now recognize an intermediate transient state of blocks which are allocated but have not yet completed initialization. blk_start() calls do not attempt to determine the size of a block in the transient state, rather waiting for the block to become initialized so that it is safe to query its size. Audited and ensured the order of initialization of object fields (klass, free bit and size) to respect block state transition protocol. Also included some new assertion checking code enabled in debug mode.
Reviewed-by: chrisphi, johnc, poonam
| author | ysr |
|---|---|
| date | Mon, 16 Aug 2010 15:58:42 -0700 |
| parents | c18cbe5936b8 |
| children | f95d63e2154a |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
2 * Copyright (c) 1997, 2009, Oracle and/or its affiliates. All rights reserved. |
| 0 | 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 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 25 # include "incls/_precompiled.incl" | |
| 26 # include "incls/_bitMap.cpp.incl" | |
| 27 | |
| 28 | |
| 342 | 29 BitMap::BitMap(bm_word_t* map, idx_t size_in_bits) : |
| 30 _map(map), _size(size_in_bits) | |
| 31 { | |
| 32 assert(sizeof(bm_word_t) == BytesPerWord, "Implementation assumption."); | |
| 0 | 33 assert(size_in_bits >= 0, "just checking"); |
| 34 } | |
| 35 | |
| 36 | |
| 342 | 37 BitMap::BitMap(idx_t size_in_bits, bool in_resource_area) : |
| 38 _map(NULL), _size(0) | |
| 39 { | |
| 40 assert(sizeof(bm_word_t) == BytesPerWord, "Implementation assumption."); | |
| 41 resize(size_in_bits, in_resource_area); | |
| 0 | 42 } |
| 43 | |
| 342 | 44 void BitMap::resize(idx_t size_in_bits, bool in_resource_area) { |
| 0 | 45 assert(size_in_bits >= 0, "just checking"); |
| 342 | 46 idx_t old_size_in_words = size_in_words(); |
| 47 bm_word_t* old_map = map(); | |
| 48 | |
| 0 | 49 _size = size_in_bits; |
| 342 | 50 idx_t new_size_in_words = size_in_words(); |
| 51 if (in_resource_area) { | |
| 52 _map = NEW_RESOURCE_ARRAY(bm_word_t, new_size_in_words); | |
| 53 } else { | |
| 54 if (old_map != NULL) FREE_C_HEAP_ARRAY(bm_word_t, _map); | |
| 55 _map = NEW_C_HEAP_ARRAY(bm_word_t, new_size_in_words); | |
| 56 } | |
| 57 Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) _map, | |
| 58 MIN2(old_size_in_words, new_size_in_words)); | |
| 0 | 59 if (new_size_in_words > old_size_in_words) { |
| 60 clear_range_of_words(old_size_in_words, size_in_words()); | |
| 61 } | |
| 62 } | |
| 63 | |
| 64 void BitMap::set_range_within_word(idx_t beg, idx_t end) { | |
| 65 // With a valid range (beg <= end), this test ensures that end != 0, as | |
| 66 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. | |
| 67 if (beg != end) { | |
| 342 | 68 bm_word_t mask = inverted_bit_mask_for_range(beg, end); |
| 0 | 69 *word_addr(beg) |= ~mask; |
| 70 } | |
| 71 } | |
| 72 | |
| 73 void BitMap::clear_range_within_word(idx_t beg, idx_t end) { | |
| 74 // With a valid range (beg <= end), this test ensures that end != 0, as | |
| 75 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. | |
| 76 if (beg != end) { | |
| 342 | 77 bm_word_t mask = inverted_bit_mask_for_range(beg, end); |
| 0 | 78 *word_addr(beg) &= mask; |
| 79 } | |
| 80 } | |
| 81 | |
| 82 void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) { | |
| 83 assert(value == 0 || value == 1, "0 for clear, 1 for set"); | |
| 84 // With a valid range (beg <= end), this test ensures that end != 0, as | |
| 85 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write. | |
| 86 if (beg != end) { | |
| 87 intptr_t* pw = (intptr_t*)word_addr(beg); | |
| 88 intptr_t w = *pw; | |
| 89 intptr_t mr = (intptr_t)inverted_bit_mask_for_range(beg, end); | |
| 90 intptr_t nw = value ? (w | ~mr) : (w & mr); | |
| 91 while (true) { | |
| 92 intptr_t res = Atomic::cmpxchg_ptr(nw, pw, w); | |
| 93 if (res == w) break; | |
| 94 w = *pw; | |
| 95 nw = value ? (w | ~mr) : (w & mr); | |
| 96 } | |
| 97 } | |
| 98 } | |
| 99 | |
| 100 void BitMap::set_range(idx_t beg, idx_t end) { | |
| 101 verify_range(beg, end); | |
| 102 | |
| 103 idx_t beg_full_word = word_index_round_up(beg); | |
| 104 idx_t end_full_word = word_index(end); | |
| 105 | |
| 106 if (beg_full_word < end_full_word) { | |
| 107 // The range includes at least one full word. | |
| 108 set_range_within_word(beg, bit_index(beg_full_word)); | |
| 109 set_range_of_words(beg_full_word, end_full_word); | |
| 110 set_range_within_word(bit_index(end_full_word), end); | |
| 111 } else { | |
| 112 // The range spans at most 2 partial words. | |
| 113 idx_t boundary = MIN2(bit_index(beg_full_word), end); | |
| 114 set_range_within_word(beg, boundary); | |
| 115 set_range_within_word(boundary, end); | |
| 116 } | |
| 117 } | |
| 118 | |
| 119 void BitMap::clear_range(idx_t beg, idx_t end) { | |
| 120 verify_range(beg, end); | |
| 121 | |
| 122 idx_t beg_full_word = word_index_round_up(beg); | |
| 123 idx_t end_full_word = word_index(end); | |
| 124 | |
| 125 if (beg_full_word < end_full_word) { | |
| 126 // The range includes at least one full word. | |
| 127 clear_range_within_word(beg, bit_index(beg_full_word)); | |
| 128 clear_range_of_words(beg_full_word, end_full_word); | |
| 129 clear_range_within_word(bit_index(end_full_word), end); | |
| 130 } else { | |
| 131 // The range spans at most 2 partial words. | |
| 132 idx_t boundary = MIN2(bit_index(beg_full_word), end); | |
| 133 clear_range_within_word(beg, boundary); | |
| 134 clear_range_within_word(boundary, end); | |
| 135 } | |
| 136 } | |
| 137 | |
| 138 void BitMap::set_large_range(idx_t beg, idx_t end) { | |
| 139 verify_range(beg, end); | |
| 140 | |
| 141 idx_t beg_full_word = word_index_round_up(beg); | |
| 142 idx_t end_full_word = word_index(end); | |
| 143 | |
| 144 assert(end_full_word - beg_full_word >= 32, | |
| 145 "the range must include at least 32 bytes"); | |
| 146 | |
| 147 // The range includes at least one full word. | |
| 148 set_range_within_word(beg, bit_index(beg_full_word)); | |
| 149 set_large_range_of_words(beg_full_word, end_full_word); | |
| 150 set_range_within_word(bit_index(end_full_word), end); | |
| 151 } | |
| 152 | |
| 153 void BitMap::clear_large_range(idx_t beg, idx_t end) { | |
| 154 verify_range(beg, end); | |
| 155 | |
| 156 idx_t beg_full_word = word_index_round_up(beg); | |
| 157 idx_t end_full_word = word_index(end); | |
| 158 | |
| 159 assert(end_full_word - beg_full_word >= 32, | |
| 160 "the range must include at least 32 bytes"); | |
| 161 | |
| 162 // The range includes at least one full word. | |
| 163 clear_range_within_word(beg, bit_index(beg_full_word)); | |
| 164 clear_large_range_of_words(beg_full_word, end_full_word); | |
| 165 clear_range_within_word(bit_index(end_full_word), end); | |
| 166 } | |
| 167 | |
| 342 | 168 void BitMap::mostly_disjoint_range_union(BitMap* from_bitmap, |
| 169 idx_t from_start_index, | |
| 170 idx_t to_start_index, | |
| 171 size_t word_num) { | |
| 172 // Ensure that the parameters are correct. | |
| 173 // These shouldn't be that expensive to check, hence I left them as | |
| 174 // guarantees. | |
| 175 guarantee(from_bitmap->bit_in_word(from_start_index) == 0, | |
| 176 "it should be aligned on a word boundary"); | |
| 177 guarantee(bit_in_word(to_start_index) == 0, | |
| 178 "it should be aligned on a word boundary"); | |
| 179 guarantee(word_num >= 2, "word_num should be at least 2"); | |
| 180 | |
| 181 intptr_t* from = (intptr_t*) from_bitmap->word_addr(from_start_index); | |
| 182 intptr_t* to = (intptr_t*) word_addr(to_start_index); | |
| 183 | |
| 184 if (*from != 0) { | |
| 185 // if it's 0, then there's no point in doing the CAS | |
| 186 while (true) { | |
| 187 intptr_t old_value = *to; | |
| 188 intptr_t new_value = old_value | *from; | |
| 189 intptr_t res = Atomic::cmpxchg_ptr(new_value, to, old_value); | |
| 190 if (res == old_value) break; | |
| 191 } | |
| 192 } | |
| 193 ++from; | |
| 194 ++to; | |
| 195 | |
| 196 for (size_t i = 0; i < word_num - 2; ++i) { | |
| 197 if (*from != 0) { | |
| 198 // if it's 0, then there's no point in doing the CAS | |
| 199 assert(*to == 0, "nobody else should be writing here"); | |
| 200 intptr_t new_value = *from; | |
| 201 *to = new_value; | |
| 202 } | |
| 203 | |
| 204 ++from; | |
| 205 ++to; | |
| 206 } | |
| 207 | |
| 208 if (*from != 0) { | |
| 209 // if it's 0, then there's no point in doing the CAS | |
| 210 while (true) { | |
| 211 intptr_t old_value = *to; | |
| 212 intptr_t new_value = old_value | *from; | |
| 213 intptr_t res = Atomic::cmpxchg_ptr(new_value, to, old_value); | |
| 214 if (res == old_value) break; | |
| 215 } | |
| 216 } | |
| 217 | |
| 218 // the -1 is because we didn't advance them after the final CAS | |
| 219 assert(from == | |
| 220 (intptr_t*) from_bitmap->word_addr(from_start_index) + word_num - 1, | |
| 221 "invariant"); | |
| 222 assert(to == (intptr_t*) word_addr(to_start_index) + word_num - 1, | |
| 223 "invariant"); | |
| 224 } | |
| 225 | |
| 0 | 226 void BitMap::at_put(idx_t offset, bool value) { |
| 227 if (value) { | |
| 228 set_bit(offset); | |
| 229 } else { | |
| 230 clear_bit(offset); | |
| 231 } | |
| 232 } | |
| 233 | |
| 234 // Return true to indicate that this thread changed | |
| 235 // the bit, false to indicate that someone else did. | |
| 236 // In either case, the requested bit is in the | |
| 237 // requested state some time during the period that | |
| 238 // this thread is executing this call. More importantly, | |
| 239 // if no other thread is executing an action to | |
| 240 // change the requested bit to a state other than | |
| 241 // the one that this thread is trying to set it to, | |
| 242 // then the the bit is in the expected state | |
| 243 // at exit from this method. However, rather than | |
| 244 // make such a strong assertion here, based on | |
| 245 // assuming such constrained use (which though true | |
| 246 // today, could change in the future to service some | |
| 247 // funky parallel algorithm), we encourage callers | |
| 248 // to do such verification, as and when appropriate. | |
| 249 bool BitMap::par_at_put(idx_t bit, bool value) { | |
| 250 return value ? par_set_bit(bit) : par_clear_bit(bit); | |
| 251 } | |
| 252 | |
| 253 void BitMap::at_put_grow(idx_t offset, bool value) { | |
| 254 if (offset >= size()) { | |
| 255 resize(2 * MAX2(size(), offset)); | |
| 256 } | |
| 257 at_put(offset, value); | |
| 258 } | |
| 259 | |
| 260 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) { | |
| 261 if (value) { | |
| 262 set_range(start_offset, end_offset); | |
| 263 } else { | |
| 264 clear_range(start_offset, end_offset); | |
| 265 } | |
| 266 } | |
| 267 | |
| 268 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) { | |
| 269 verify_range(beg, end); | |
| 270 | |
| 271 idx_t beg_full_word = word_index_round_up(beg); | |
| 272 idx_t end_full_word = word_index(end); | |
| 273 | |
| 274 if (beg_full_word < end_full_word) { | |
| 275 // The range includes at least one full word. | |
| 276 par_put_range_within_word(beg, bit_index(beg_full_word), value); | |
| 277 if (value) { | |
| 278 set_range_of_words(beg_full_word, end_full_word); | |
| 279 } else { | |
| 280 clear_range_of_words(beg_full_word, end_full_word); | |
| 281 } | |
| 282 par_put_range_within_word(bit_index(end_full_word), end, value); | |
| 283 } else { | |
| 284 // The range spans at most 2 partial words. | |
| 285 idx_t boundary = MIN2(bit_index(beg_full_word), end); | |
| 286 par_put_range_within_word(beg, boundary, value); | |
| 287 par_put_range_within_word(boundary, end, value); | |
| 288 } | |
| 289 | |
| 290 } | |
| 291 | |
| 292 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) { | |
| 293 if (value) { | |
| 294 set_large_range(beg, end); | |
| 295 } else { | |
| 296 clear_large_range(beg, end); | |
| 297 } | |
| 298 } | |
| 299 | |
| 300 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) { | |
| 301 verify_range(beg, end); | |
| 302 | |
| 303 idx_t beg_full_word = word_index_round_up(beg); | |
| 304 idx_t end_full_word = word_index(end); | |
| 305 | |
| 306 assert(end_full_word - beg_full_word >= 32, | |
| 307 "the range must include at least 32 bytes"); | |
| 308 | |
| 309 // The range includes at least one full word. | |
| 310 par_put_range_within_word(beg, bit_index(beg_full_word), value); | |
| 311 if (value) { | |
| 312 set_large_range_of_words(beg_full_word, end_full_word); | |
| 313 } else { | |
| 314 clear_large_range_of_words(beg_full_word, end_full_word); | |
| 315 } | |
| 316 par_put_range_within_word(bit_index(end_full_word), end, value); | |
| 317 } | |
| 318 | |
| 319 bool BitMap::contains(const BitMap other) const { | |
| 320 assert(size() == other.size(), "must have same size"); | |
| 342 | 321 bm_word_t* dest_map = map(); |
| 322 bm_word_t* other_map = other.map(); | |
| 0 | 323 idx_t size = size_in_words(); |
| 324 for (idx_t index = 0; index < size_in_words(); index++) { | |
| 342 | 325 bm_word_t word_union = dest_map[index] | other_map[index]; |
| 0 | 326 // If this has more bits set than dest_map[index], then other is not a |
| 327 // subset. | |
| 328 if (word_union != dest_map[index]) return false; | |
| 329 } | |
| 330 return true; | |
| 331 } | |
| 332 | |
| 333 bool BitMap::intersects(const BitMap other) const { | |
| 334 assert(size() == other.size(), "must have same size"); | |
| 342 | 335 bm_word_t* dest_map = map(); |
| 336 bm_word_t* other_map = other.map(); | |
| 0 | 337 idx_t size = size_in_words(); |
| 338 for (idx_t index = 0; index < size_in_words(); index++) { | |
| 339 if ((dest_map[index] & other_map[index]) != 0) return true; | |
| 340 } | |
| 341 // Otherwise, no intersection. | |
| 342 return false; | |
| 343 } | |
| 344 | |
| 345 void BitMap::set_union(BitMap other) { | |
| 346 assert(size() == other.size(), "must have same size"); | |
| 342 | 347 bm_word_t* dest_map = map(); |
| 348 bm_word_t* other_map = other.map(); | |
| 0 | 349 idx_t size = size_in_words(); |
| 350 for (idx_t index = 0; index < size_in_words(); index++) { | |
| 351 dest_map[index] = dest_map[index] | other_map[index]; | |
| 352 } | |
| 353 } | |
| 354 | |
| 355 | |
| 356 void BitMap::set_difference(BitMap other) { | |
| 357 assert(size() == other.size(), "must have same size"); | |
| 342 | 358 bm_word_t* dest_map = map(); |
| 359 bm_word_t* other_map = other.map(); | |
| 0 | 360 idx_t size = size_in_words(); |
| 361 for (idx_t index = 0; index < size_in_words(); index++) { | |
| 362 dest_map[index] = dest_map[index] & ~(other_map[index]); | |
| 363 } | |
| 364 } | |
| 365 | |
| 366 | |
| 367 void BitMap::set_intersection(BitMap other) { | |
| 368 assert(size() == other.size(), "must have same size"); | |
| 342 | 369 bm_word_t* dest_map = map(); |
| 370 bm_word_t* other_map = other.map(); | |
| 0 | 371 idx_t size = size_in_words(); |
| 372 for (idx_t index = 0; index < size; index++) { | |
| 373 dest_map[index] = dest_map[index] & other_map[index]; | |
| 374 } | |
| 375 } | |
| 376 | |
| 377 | |
| 342 | 378 void BitMap::set_intersection_at_offset(BitMap other, idx_t offset) { |
| 379 assert(other.size() >= offset, "offset not in range"); | |
| 380 assert(other.size() - offset >= size(), "other not large enough"); | |
| 381 // XXX Ideally, we would remove this restriction. | |
| 382 guarantee((offset % (sizeof(bm_word_t) * BitsPerByte)) == 0, | |
| 383 "Only handle aligned cases so far."); | |
| 384 bm_word_t* dest_map = map(); | |
| 385 bm_word_t* other_map = other.map(); | |
| 386 idx_t offset_word_ind = word_index(offset); | |
| 387 idx_t size = size_in_words(); | |
| 388 for (idx_t index = 0; index < size; index++) { | |
| 389 dest_map[index] = dest_map[index] & other_map[offset_word_ind + index]; | |
| 390 } | |
| 391 } | |
| 392 | |
| 0 | 393 bool BitMap::set_union_with_result(BitMap other) { |
| 394 assert(size() == other.size(), "must have same size"); | |
| 395 bool changed = false; | |
| 342 | 396 bm_word_t* dest_map = map(); |
| 397 bm_word_t* other_map = other.map(); | |
| 0 | 398 idx_t size = size_in_words(); |
| 399 for (idx_t index = 0; index < size; index++) { | |
| 400 idx_t temp = map(index) | other_map[index]; | |
| 401 changed = changed || (temp != map(index)); | |
| 402 map()[index] = temp; | |
| 403 } | |
| 404 return changed; | |
| 405 } | |
| 406 | |
| 407 | |
| 408 bool BitMap::set_difference_with_result(BitMap other) { | |
| 409 assert(size() == other.size(), "must have same size"); | |
| 410 bool changed = false; | |
| 342 | 411 bm_word_t* dest_map = map(); |
| 412 bm_word_t* other_map = other.map(); | |
| 0 | 413 idx_t size = size_in_words(); |
| 414 for (idx_t index = 0; index < size; index++) { | |
| 342 | 415 bm_word_t temp = dest_map[index] & ~(other_map[index]); |
| 0 | 416 changed = changed || (temp != dest_map[index]); |
| 417 dest_map[index] = temp; | |
| 418 } | |
| 419 return changed; | |
| 420 } | |
| 421 | |
| 422 | |
| 423 bool BitMap::set_intersection_with_result(BitMap other) { | |
| 424 assert(size() == other.size(), "must have same size"); | |
| 425 bool changed = false; | |
| 342 | 426 bm_word_t* dest_map = map(); |
| 427 bm_word_t* other_map = other.map(); | |
| 0 | 428 idx_t size = size_in_words(); |
| 429 for (idx_t index = 0; index < size; index++) { | |
| 342 | 430 bm_word_t orig = dest_map[index]; |
| 431 bm_word_t temp = orig & other_map[index]; | |
| 0 | 432 changed = changed || (temp != orig); |
| 433 dest_map[index] = temp; | |
| 434 } | |
| 435 return changed; | |
| 436 } | |
| 437 | |
| 438 | |
| 439 void BitMap::set_from(BitMap other) { | |
| 440 assert(size() == other.size(), "must have same size"); | |
| 342 | 441 bm_word_t* dest_map = map(); |
| 442 bm_word_t* other_map = other.map(); | |
| 0 | 443 idx_t size = size_in_words(); |
| 444 for (idx_t index = 0; index < size; index++) { | |
| 445 dest_map[index] = other_map[index]; | |
| 446 } | |
| 447 } | |
| 448 | |
| 449 | |
| 450 bool BitMap::is_same(BitMap other) { | |
| 451 assert(size() == other.size(), "must have same size"); | |
| 342 | 452 bm_word_t* dest_map = map(); |
| 453 bm_word_t* other_map = other.map(); | |
| 0 | 454 idx_t size = size_in_words(); |
| 455 for (idx_t index = 0; index < size; index++) { | |
| 456 if (dest_map[index] != other_map[index]) return false; | |
| 457 } | |
| 458 return true; | |
| 459 } | |
| 460 | |
| 461 bool BitMap::is_full() const { | |
| 342 | 462 bm_word_t* word = map(); |
| 0 | 463 idx_t rest = size(); |
| 464 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) { | |
| 342 | 465 if (*word != (bm_word_t) AllBits) return false; |
| 0 | 466 word++; |
| 467 } | |
| 342 | 468 return rest == 0 || (*word | ~right_n_bits((int)rest)) == (bm_word_t) AllBits; |
| 0 | 469 } |
| 470 | |
| 471 | |
| 472 bool BitMap::is_empty() const { | |
| 342 | 473 bm_word_t* word = map(); |
| 0 | 474 idx_t rest = size(); |
| 475 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) { | |
| 342 | 476 if (*word != (bm_word_t) NoBits) return false; |
| 0 | 477 word++; |
| 478 } | |
| 342 | 479 return rest == 0 || (*word & right_n_bits((int)rest)) == (bm_word_t) NoBits; |
| 0 | 480 } |
| 481 | |
| 482 void BitMap::clear_large() { | |
| 483 clear_large_range_of_words(0, size_in_words()); | |
| 484 } | |
| 485 | |
| 486 // Note that if the closure itself modifies the bitmap | |
| 487 // then modifications in and to the left of the _bit_ being | |
| 488 // currently sampled will not be seen. Note also that the | |
| 489 // interval [leftOffset, rightOffset) is right open. | |
| 342 | 490 bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) { |
| 0 | 491 verify_range(leftOffset, rightOffset); |
| 492 | |
| 493 idx_t startIndex = word_index(leftOffset); | |
| 494 idx_t endIndex = MIN2(word_index(rightOffset) + 1, size_in_words()); | |
| 495 for (idx_t index = startIndex, offset = leftOffset; | |
| 496 offset < rightOffset && index < endIndex; | |
| 497 offset = (++index) << LogBitsPerWord) { | |
| 498 idx_t rest = map(index) >> (offset & (BitsPerWord - 1)); | |
| 342 | 499 for (; offset < rightOffset && rest != (bm_word_t)NoBits; offset++) { |
| 0 | 500 if (rest & 1) { |
| 342 | 501 if (!blk->do_bit(offset)) return false; |
| 0 | 502 // resample at each closure application |
| 503 // (see, for instance, CMS bug 4525989) | |
| 504 rest = map(index) >> (offset & (BitsPerWord -1)); | |
| 505 } | |
| 506 rest = rest >> 1; | |
| 507 } | |
| 508 } | |
| 342 | 509 return true; |
| 510 } | |
| 511 | |
| 512 BitMap::idx_t* BitMap::_pop_count_table = NULL; | |
| 513 | |
| 514 void BitMap::init_pop_count_table() { | |
| 515 if (_pop_count_table == NULL) { | |
| 516 BitMap::idx_t *table = NEW_C_HEAP_ARRAY(idx_t, 256); | |
| 517 for (uint i = 0; i < 256; i++) { | |
| 518 table[i] = num_set_bits(i); | |
| 519 } | |
| 520 | |
| 521 intptr_t res = Atomic::cmpxchg_ptr((intptr_t) table, | |
| 522 (intptr_t*) &_pop_count_table, | |
| 523 (intptr_t) NULL_WORD); | |
| 524 if (res != NULL_WORD) { | |
| 525 guarantee( _pop_count_table == (void*) res, "invariant" ); | |
| 526 FREE_C_HEAP_ARRAY(bm_word_t, table); | |
| 527 } | |
| 528 } | |
| 0 | 529 } |
| 530 | |
| 342 | 531 BitMap::idx_t BitMap::num_set_bits(bm_word_t w) { |
| 532 idx_t bits = 0; | |
| 0 | 533 |
| 342 | 534 while (w != 0) { |
| 535 while ((w & 1) == 0) { | |
| 536 w >>= 1; | |
| 0 | 537 } |
| 342 | 538 bits++; |
| 539 w >>= 1; | |
| 0 | 540 } |
| 342 | 541 return bits; |
| 0 | 542 } |
| 543 | |
| 342 | 544 BitMap::idx_t BitMap::num_set_bits_from_table(unsigned char c) { |
| 545 assert(_pop_count_table != NULL, "precondition"); | |
| 546 return _pop_count_table[c]; | |
| 547 } | |
| 0 | 548 |
| 342 | 549 BitMap::idx_t BitMap::count_one_bits() const { |
| 550 init_pop_count_table(); // If necessary. | |
| 551 idx_t sum = 0; | |
| 552 typedef unsigned char uchar; | |
| 553 for (idx_t i = 0; i < size_in_words(); i++) { | |
| 554 bm_word_t w = map()[i]; | |
| 555 for (size_t j = 0; j < sizeof(bm_word_t); j++) { | |
| 556 sum += num_set_bits_from_table(uchar(w & 255)); | |
| 557 w >>= 8; | |
| 0 | 558 } |
| 559 } | |
| 342 | 560 return sum; |
| 0 | 561 } |
| 562 | |
| 342 | 563 |
| 0 | 564 #ifndef PRODUCT |
| 565 | |
| 566 void BitMap::print_on(outputStream* st) const { | |
| 567 tty->print("Bitmap(%d):", size()); | |
| 568 for (idx_t index = 0; index < size(); index++) { | |
| 569 tty->print("%c", at(index) ? '1' : '0'); | |
| 570 } | |
| 571 tty->cr(); | |
| 572 } | |
| 573 | |
| 574 #endif | |
| 575 | |
| 576 | |
| 342 | 577 BitMap2D::BitMap2D(bm_word_t* map, idx_t size_in_slots, idx_t bits_per_slot) |
| 0 | 578 : _bits_per_slot(bits_per_slot) |
| 579 , _map(map, size_in_slots * bits_per_slot) | |
| 580 { | |
| 581 } | |
| 582 | |
| 583 | |
| 584 BitMap2D::BitMap2D(idx_t size_in_slots, idx_t bits_per_slot) | |
| 585 : _bits_per_slot(bits_per_slot) | |
| 586 , _map(size_in_slots * bits_per_slot) | |
| 587 { | |
| 588 } |