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