Thu, 20 Nov 2008 16:56:09 -0800
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 1997-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 */
25 # include "incls/_precompiled.incl"
26 # include "incls/_bitMap.cpp.incl"
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.");
33 assert(size_in_bits >= 0, "just checking");
34 }
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);
42 }
45 void BitMap::verify_index(idx_t index) const {
46 assert(index < _size, "BitMap index out of bounds");
47 }
49 void BitMap::verify_range(idx_t beg_index, idx_t end_index) const {
50 #ifdef ASSERT
51 assert(beg_index <= end_index, "BitMap range error");
52 // Note that [0,0) and [size,size) are both valid ranges.
53 if (end_index != _size) verify_index(end_index);
54 #endif
55 }
57 void BitMap::resize(idx_t size_in_bits, bool in_resource_area) {
58 assert(size_in_bits >= 0, "just checking");
59 idx_t old_size_in_words = size_in_words();
60 bm_word_t* old_map = map();
62 _size = size_in_bits;
63 idx_t new_size_in_words = size_in_words();
64 if (in_resource_area) {
65 _map = NEW_RESOURCE_ARRAY(bm_word_t, new_size_in_words);
66 } else {
67 if (old_map != NULL) FREE_C_HEAP_ARRAY(bm_word_t, _map);
68 _map = NEW_C_HEAP_ARRAY(bm_word_t, new_size_in_words);
69 }
70 Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) _map,
71 MIN2(old_size_in_words, new_size_in_words));
72 if (new_size_in_words > old_size_in_words) {
73 clear_range_of_words(old_size_in_words, size_in_words());
74 }
75 }
77 void BitMap::set_range_within_word(idx_t beg, idx_t end) {
78 // With a valid range (beg <= end), this test ensures that end != 0, as
79 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
80 if (beg != end) {
81 bm_word_t mask = inverted_bit_mask_for_range(beg, end);
82 *word_addr(beg) |= ~mask;
83 }
84 }
86 void BitMap::clear_range_within_word(idx_t beg, idx_t end) {
87 // With a valid range (beg <= end), this test ensures that end != 0, as
88 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
89 if (beg != end) {
90 bm_word_t mask = inverted_bit_mask_for_range(beg, end);
91 *word_addr(beg) &= mask;
92 }
93 }
95 void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) {
96 assert(value == 0 || value == 1, "0 for clear, 1 for set");
97 // With a valid range (beg <= end), this test ensures that end != 0, as
98 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
99 if (beg != end) {
100 intptr_t* pw = (intptr_t*)word_addr(beg);
101 intptr_t w = *pw;
102 intptr_t mr = (intptr_t)inverted_bit_mask_for_range(beg, end);
103 intptr_t nw = value ? (w | ~mr) : (w & mr);
104 while (true) {
105 intptr_t res = Atomic::cmpxchg_ptr(nw, pw, w);
106 if (res == w) break;
107 w = *pw;
108 nw = value ? (w | ~mr) : (w & mr);
109 }
110 }
111 }
113 void BitMap::set_range(idx_t beg, idx_t end) {
114 verify_range(beg, end);
116 idx_t beg_full_word = word_index_round_up(beg);
117 idx_t end_full_word = word_index(end);
119 if (beg_full_word < end_full_word) {
120 // The range includes at least one full word.
121 set_range_within_word(beg, bit_index(beg_full_word));
122 set_range_of_words(beg_full_word, end_full_word);
123 set_range_within_word(bit_index(end_full_word), end);
124 } else {
125 // The range spans at most 2 partial words.
126 idx_t boundary = MIN2(bit_index(beg_full_word), end);
127 set_range_within_word(beg, boundary);
128 set_range_within_word(boundary, end);
129 }
130 }
132 void BitMap::clear_range(idx_t beg, idx_t end) {
133 verify_range(beg, end);
135 idx_t beg_full_word = word_index_round_up(beg);
136 idx_t end_full_word = word_index(end);
138 if (beg_full_word < end_full_word) {
139 // The range includes at least one full word.
140 clear_range_within_word(beg, bit_index(beg_full_word));
141 clear_range_of_words(beg_full_word, end_full_word);
142 clear_range_within_word(bit_index(end_full_word), end);
143 } else {
144 // The range spans at most 2 partial words.
145 idx_t boundary = MIN2(bit_index(beg_full_word), end);
146 clear_range_within_word(beg, boundary);
147 clear_range_within_word(boundary, end);
148 }
149 }
151 void BitMap::set_large_range(idx_t beg, idx_t end) {
152 verify_range(beg, end);
154 idx_t beg_full_word = word_index_round_up(beg);
155 idx_t end_full_word = word_index(end);
157 assert(end_full_word - beg_full_word >= 32,
158 "the range must include at least 32 bytes");
160 // The range includes at least one full word.
161 set_range_within_word(beg, bit_index(beg_full_word));
162 set_large_range_of_words(beg_full_word, end_full_word);
163 set_range_within_word(bit_index(end_full_word), end);
164 }
166 void BitMap::clear_large_range(idx_t beg, idx_t end) {
167 verify_range(beg, end);
169 idx_t beg_full_word = word_index_round_up(beg);
170 idx_t end_full_word = word_index(end);
172 assert(end_full_word - beg_full_word >= 32,
173 "the range must include at least 32 bytes");
175 // The range includes at least one full word.
176 clear_range_within_word(beg, bit_index(beg_full_word));
177 clear_large_range_of_words(beg_full_word, end_full_word);
178 clear_range_within_word(bit_index(end_full_word), end);
179 }
181 void BitMap::mostly_disjoint_range_union(BitMap* from_bitmap,
182 idx_t from_start_index,
183 idx_t to_start_index,
184 size_t word_num) {
185 // Ensure that the parameters are correct.
186 // These shouldn't be that expensive to check, hence I left them as
187 // guarantees.
188 guarantee(from_bitmap->bit_in_word(from_start_index) == 0,
189 "it should be aligned on a word boundary");
190 guarantee(bit_in_word(to_start_index) == 0,
191 "it should be aligned on a word boundary");
192 guarantee(word_num >= 2, "word_num should be at least 2");
194 intptr_t* from = (intptr_t*) from_bitmap->word_addr(from_start_index);
195 intptr_t* to = (intptr_t*) word_addr(to_start_index);
197 if (*from != 0) {
198 // if it's 0, then there's no point in doing the CAS
199 while (true) {
200 intptr_t old_value = *to;
201 intptr_t new_value = old_value | *from;
202 intptr_t res = Atomic::cmpxchg_ptr(new_value, to, old_value);
203 if (res == old_value) break;
204 }
205 }
206 ++from;
207 ++to;
209 for (size_t i = 0; i < word_num - 2; ++i) {
210 if (*from != 0) {
211 // if it's 0, then there's no point in doing the CAS
212 assert(*to == 0, "nobody else should be writing here");
213 intptr_t new_value = *from;
214 *to = new_value;
215 }
217 ++from;
218 ++to;
219 }
221 if (*from != 0) {
222 // if it's 0, then there's no point in doing the CAS
223 while (true) {
224 intptr_t old_value = *to;
225 intptr_t new_value = old_value | *from;
226 intptr_t res = Atomic::cmpxchg_ptr(new_value, to, old_value);
227 if (res == old_value) break;
228 }
229 }
231 // the -1 is because we didn't advance them after the final CAS
232 assert(from ==
233 (intptr_t*) from_bitmap->word_addr(from_start_index) + word_num - 1,
234 "invariant");
235 assert(to == (intptr_t*) word_addr(to_start_index) + word_num - 1,
236 "invariant");
237 }
239 void BitMap::at_put(idx_t offset, bool value) {
240 if (value) {
241 set_bit(offset);
242 } else {
243 clear_bit(offset);
244 }
245 }
247 // Return true to indicate that this thread changed
248 // the bit, false to indicate that someone else did.
249 // In either case, the requested bit is in the
250 // requested state some time during the period that
251 // this thread is executing this call. More importantly,
252 // if no other thread is executing an action to
253 // change the requested bit to a state other than
254 // the one that this thread is trying to set it to,
255 // then the the bit is in the expected state
256 // at exit from this method. However, rather than
257 // make such a strong assertion here, based on
258 // assuming such constrained use (which though true
259 // today, could change in the future to service some
260 // funky parallel algorithm), we encourage callers
261 // to do such verification, as and when appropriate.
262 bool BitMap::par_at_put(idx_t bit, bool value) {
263 return value ? par_set_bit(bit) : par_clear_bit(bit);
264 }
266 void BitMap::at_put_grow(idx_t offset, bool value) {
267 if (offset >= size()) {
268 resize(2 * MAX2(size(), offset));
269 }
270 at_put(offset, value);
271 }
273 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) {
274 if (value) {
275 set_range(start_offset, end_offset);
276 } else {
277 clear_range(start_offset, end_offset);
278 }
279 }
281 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
282 verify_range(beg, end);
284 idx_t beg_full_word = word_index_round_up(beg);
285 idx_t end_full_word = word_index(end);
287 if (beg_full_word < end_full_word) {
288 // The range includes at least one full word.
289 par_put_range_within_word(beg, bit_index(beg_full_word), value);
290 if (value) {
291 set_range_of_words(beg_full_word, end_full_word);
292 } else {
293 clear_range_of_words(beg_full_word, end_full_word);
294 }
295 par_put_range_within_word(bit_index(end_full_word), end, value);
296 } else {
297 // The range spans at most 2 partial words.
298 idx_t boundary = MIN2(bit_index(beg_full_word), end);
299 par_put_range_within_word(beg, boundary, value);
300 par_put_range_within_word(boundary, end, value);
301 }
303 }
305 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
306 if (value) {
307 set_large_range(beg, end);
308 } else {
309 clear_large_range(beg, end);
310 }
311 }
313 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
314 verify_range(beg, end);
316 idx_t beg_full_word = word_index_round_up(beg);
317 idx_t end_full_word = word_index(end);
319 assert(end_full_word - beg_full_word >= 32,
320 "the range must include at least 32 bytes");
322 // The range includes at least one full word.
323 par_put_range_within_word(beg, bit_index(beg_full_word), value);
324 if (value) {
325 set_large_range_of_words(beg_full_word, end_full_word);
326 } else {
327 clear_large_range_of_words(beg_full_word, end_full_word);
328 }
329 par_put_range_within_word(bit_index(end_full_word), end, value);
330 }
332 bool BitMap::contains(const BitMap other) const {
333 assert(size() == other.size(), "must have same size");
334 bm_word_t* dest_map = map();
335 bm_word_t* other_map = other.map();
336 idx_t size = size_in_words();
337 for (idx_t index = 0; index < size_in_words(); index++) {
338 bm_word_t word_union = dest_map[index] | other_map[index];
339 // If this has more bits set than dest_map[index], then other is not a
340 // subset.
341 if (word_union != dest_map[index]) return false;
342 }
343 return true;
344 }
346 bool BitMap::intersects(const BitMap other) const {
347 assert(size() == other.size(), "must have same size");
348 bm_word_t* dest_map = map();
349 bm_word_t* other_map = other.map();
350 idx_t size = size_in_words();
351 for (idx_t index = 0; index < size_in_words(); index++) {
352 if ((dest_map[index] & other_map[index]) != 0) return true;
353 }
354 // Otherwise, no intersection.
355 return false;
356 }
358 void BitMap::set_union(BitMap other) {
359 assert(size() == other.size(), "must have same size");
360 bm_word_t* dest_map = map();
361 bm_word_t* other_map = other.map();
362 idx_t size = size_in_words();
363 for (idx_t index = 0; index < size_in_words(); index++) {
364 dest_map[index] = dest_map[index] | other_map[index];
365 }
366 }
369 void BitMap::set_difference(BitMap other) {
370 assert(size() == other.size(), "must have same size");
371 bm_word_t* dest_map = map();
372 bm_word_t* other_map = other.map();
373 idx_t size = size_in_words();
374 for (idx_t index = 0; index < size_in_words(); index++) {
375 dest_map[index] = dest_map[index] & ~(other_map[index]);
376 }
377 }
380 void BitMap::set_intersection(BitMap other) {
381 assert(size() == other.size(), "must have same size");
382 bm_word_t* dest_map = map();
383 bm_word_t* other_map = other.map();
384 idx_t size = size_in_words();
385 for (idx_t index = 0; index < size; index++) {
386 dest_map[index] = dest_map[index] & other_map[index];
387 }
388 }
391 void BitMap::set_intersection_at_offset(BitMap other, idx_t offset) {
392 assert(other.size() >= offset, "offset not in range");
393 assert(other.size() - offset >= size(), "other not large enough");
394 // XXX Ideally, we would remove this restriction.
395 guarantee((offset % (sizeof(bm_word_t) * BitsPerByte)) == 0,
396 "Only handle aligned cases so far.");
397 bm_word_t* dest_map = map();
398 bm_word_t* other_map = other.map();
399 idx_t offset_word_ind = word_index(offset);
400 idx_t size = size_in_words();
401 for (idx_t index = 0; index < size; index++) {
402 dest_map[index] = dest_map[index] & other_map[offset_word_ind + index];
403 }
404 }
406 bool BitMap::set_union_with_result(BitMap other) {
407 assert(size() == other.size(), "must have same size");
408 bool changed = false;
409 bm_word_t* dest_map = map();
410 bm_word_t* other_map = other.map();
411 idx_t size = size_in_words();
412 for (idx_t index = 0; index < size; index++) {
413 idx_t temp = map(index) | other_map[index];
414 changed = changed || (temp != map(index));
415 map()[index] = temp;
416 }
417 return changed;
418 }
421 bool BitMap::set_difference_with_result(BitMap other) {
422 assert(size() == other.size(), "must have same size");
423 bool changed = false;
424 bm_word_t* dest_map = map();
425 bm_word_t* other_map = other.map();
426 idx_t size = size_in_words();
427 for (idx_t index = 0; index < size; index++) {
428 bm_word_t temp = dest_map[index] & ~(other_map[index]);
429 changed = changed || (temp != dest_map[index]);
430 dest_map[index] = temp;
431 }
432 return changed;
433 }
436 bool BitMap::set_intersection_with_result(BitMap other) {
437 assert(size() == other.size(), "must have same size");
438 bool changed = false;
439 bm_word_t* dest_map = map();
440 bm_word_t* other_map = other.map();
441 idx_t size = size_in_words();
442 for (idx_t index = 0; index < size; index++) {
443 bm_word_t orig = dest_map[index];
444 bm_word_t temp = orig & other_map[index];
445 changed = changed || (temp != orig);
446 dest_map[index] = temp;
447 }
448 return changed;
449 }
452 void BitMap::set_from(BitMap other) {
453 assert(size() == other.size(), "must have same size");
454 bm_word_t* dest_map = map();
455 bm_word_t* other_map = other.map();
456 idx_t size = size_in_words();
457 for (idx_t index = 0; index < size; index++) {
458 dest_map[index] = other_map[index];
459 }
460 }
463 bool BitMap::is_same(BitMap other) {
464 assert(size() == other.size(), "must have same size");
465 bm_word_t* dest_map = map();
466 bm_word_t* other_map = other.map();
467 idx_t size = size_in_words();
468 for (idx_t index = 0; index < size; index++) {
469 if (dest_map[index] != other_map[index]) return false;
470 }
471 return true;
472 }
474 bool BitMap::is_full() const {
475 bm_word_t* word = map();
476 idx_t rest = size();
477 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) {
478 if (*word != (bm_word_t) AllBits) return false;
479 word++;
480 }
481 return rest == 0 || (*word | ~right_n_bits((int)rest)) == (bm_word_t) AllBits;
482 }
485 bool BitMap::is_empty() const {
486 bm_word_t* word = map();
487 idx_t rest = size();
488 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) {
489 if (*word != (bm_word_t) NoBits) return false;
490 word++;
491 }
492 return rest == 0 || (*word & right_n_bits((int)rest)) == (bm_word_t) NoBits;
493 }
495 void BitMap::clear_large() {
496 clear_large_range_of_words(0, size_in_words());
497 }
499 // Note that if the closure itself modifies the bitmap
500 // then modifications in and to the left of the _bit_ being
501 // currently sampled will not be seen. Note also that the
502 // interval [leftOffset, rightOffset) is right open.
503 bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) {
504 verify_range(leftOffset, rightOffset);
506 idx_t startIndex = word_index(leftOffset);
507 idx_t endIndex = MIN2(word_index(rightOffset) + 1, size_in_words());
508 for (idx_t index = startIndex, offset = leftOffset;
509 offset < rightOffset && index < endIndex;
510 offset = (++index) << LogBitsPerWord) {
511 idx_t rest = map(index) >> (offset & (BitsPerWord - 1));
512 for (; offset < rightOffset && rest != (bm_word_t)NoBits; offset++) {
513 if (rest & 1) {
514 if (!blk->do_bit(offset)) return false;
515 // resample at each closure application
516 // (see, for instance, CMS bug 4525989)
517 rest = map(index) >> (offset & (BitsPerWord -1));
518 }
519 rest = rest >> 1;
520 }
521 }
522 return true;
523 }
525 BitMap::idx_t* BitMap::_pop_count_table = NULL;
527 void BitMap::init_pop_count_table() {
528 if (_pop_count_table == NULL) {
529 BitMap::idx_t *table = NEW_C_HEAP_ARRAY(idx_t, 256);
530 for (uint i = 0; i < 256; i++) {
531 table[i] = num_set_bits(i);
532 }
534 intptr_t res = Atomic::cmpxchg_ptr((intptr_t) table,
535 (intptr_t*) &_pop_count_table,
536 (intptr_t) NULL_WORD);
537 if (res != NULL_WORD) {
538 guarantee( _pop_count_table == (void*) res, "invariant" );
539 FREE_C_HEAP_ARRAY(bm_word_t, table);
540 }
541 }
542 }
544 BitMap::idx_t BitMap::num_set_bits(bm_word_t w) {
545 idx_t bits = 0;
547 while (w != 0) {
548 while ((w & 1) == 0) {
549 w >>= 1;
550 }
551 bits++;
552 w >>= 1;
553 }
554 return bits;
555 }
557 BitMap::idx_t BitMap::num_set_bits_from_table(unsigned char c) {
558 assert(_pop_count_table != NULL, "precondition");
559 return _pop_count_table[c];
560 }
562 BitMap::idx_t BitMap::count_one_bits() const {
563 init_pop_count_table(); // If necessary.
564 idx_t sum = 0;
565 typedef unsigned char uchar;
566 for (idx_t i = 0; i < size_in_words(); i++) {
567 bm_word_t w = map()[i];
568 for (size_t j = 0; j < sizeof(bm_word_t); j++) {
569 sum += num_set_bits_from_table(uchar(w & 255));
570 w >>= 8;
571 }
572 }
573 return sum;
574 }
577 #ifndef PRODUCT
579 void BitMap::print_on(outputStream* st) const {
580 tty->print("Bitmap(%d):", size());
581 for (idx_t index = 0; index < size(); index++) {
582 tty->print("%c", at(index) ? '1' : '0');
583 }
584 tty->cr();
585 }
587 #endif
590 BitMap2D::BitMap2D(bm_word_t* map, idx_t size_in_slots, idx_t bits_per_slot)
591 : _bits_per_slot(bits_per_slot)
592 , _map(map, size_in_slots * bits_per_slot)
593 {
594 }
597 BitMap2D::BitMap2D(idx_t size_in_slots, idx_t bits_per_slot)
598 : _bits_per_slot(bits_per_slot)
599 , _map(size_in_slots * bits_per_slot)
600 {
601 }