1 /*
2 * Copyright (c) 1997, 2015, 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 #include "precompiled.hpp"
26 #include "memory/allocation.inline.hpp"
27 #include "memory/resourceArea.hpp"
28 #include "runtime/atomic.inline.hpp"
29 #include "utilities/bitMap.inline.hpp"
30 #include "utilities/copy.hpp"
31
32 STATIC_ASSERT(sizeof(BitMap::bm_word_t) == BytesPerWord); // "Implementation assumption."
33
34 BitMap::BitMap(idx_t size_in_bits, bool in_resource_area) :
35 _map(NULL), _size(0)
36 {
37 resize(size_in_bits, in_resource_area);
38 }
39
40 #ifdef ASSERT
41 void BitMap::verify_index(idx_t index) const {
42 assert(index < _size, "BitMap index out of bounds");
43 }
44
45 void BitMap::verify_range(idx_t beg_index, idx_t end_index) const {
46 assert(beg_index <= end_index, "BitMap range error");
47 // Note that [0,0) and [size,size) are both valid ranges.
48 if (end_index != _size) verify_index(end_index);
49 }
50 #endif // #ifdef ASSERT
51
52 void BitMap::resize(idx_t size_in_bits, bool in_resource_area) {
53 idx_t old_size_in_words = size_in_words();
54 bm_word_t* old_map = map();
55
56 _size = size_in_bits;
57 idx_t new_size_in_words = size_in_words();
58 if (in_resource_area) {
59 _map = NEW_RESOURCE_ARRAY(bm_word_t, new_size_in_words);
60 Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) _map,
61 MIN2(old_size_in_words, new_size_in_words));
62 } else {
63 _map = ArrayAllocator<bm_word_t, mtInternal>::reallocate(old_map, old_size_in_words, new_size_in_words);
64 }
65
66 if (new_size_in_words > old_size_in_words) {
67 clear_range_of_words(old_size_in_words, new_size_in_words);
68 }
69 }
70
71 void BitMap::set_range_within_word(idx_t beg, idx_t end) {
72 // With a valid range (beg <= end), this test ensures that end != 0, as
73 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
74 if (beg != end) {
75 bm_word_t mask = inverted_bit_mask_for_range(beg, end);
76 *word_addr(beg) |= ~mask;
77 }
78 }
79
80 void BitMap::clear_range_within_word(idx_t beg, idx_t end) {
81 // With a valid range (beg <= end), this test ensures that end != 0, as
82 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
83 if (beg != end) {
84 bm_word_t mask = inverted_bit_mask_for_range(beg, end);
85 *word_addr(beg) &= mask;
86 }
87 }
88
89 void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) {
90 assert(value == 0 || value == 1, "0 for clear, 1 for set");
91 // With a valid range (beg <= end), this test ensures that end != 0, as
92 // required by inverted_bit_mask_for_range. Also avoids an unnecessary write.
93 if (beg != end) {
94 intptr_t* pw = (intptr_t*)word_addr(beg);
95 intptr_t w = *pw;
96 intptr_t mr = (intptr_t)inverted_bit_mask_for_range(beg, end);
97 intptr_t nw = value ? (w | ~mr) : (w & mr);
98 while (true) {
99 intptr_t res = Atomic::cmpxchg_ptr(nw, pw, w);
100 if (res == w) break;
101 w = res;
102 nw = value ? (w | ~mr) : (w & mr);
103 }
104 }
105 }
106
107 void BitMap::set_range(idx_t beg, idx_t end) {
108 verify_range(beg, end);
109
110 idx_t beg_full_word = word_index_round_up(beg);
111 idx_t end_full_word = word_index(end);
112
113 if (beg_full_word < end_full_word) {
114 // The range includes at least one full word.
115 set_range_within_word(beg, bit_index(beg_full_word));
116 set_range_of_words(beg_full_word, end_full_word);
117 set_range_within_word(bit_index(end_full_word), end);
118 } else {
119 // The range spans at most 2 partial words.
120 idx_t boundary = MIN2(bit_index(beg_full_word), end);
121 set_range_within_word(beg, boundary);
122 set_range_within_word(boundary, end);
123 }
124 }
125
126 void BitMap::clear_range(idx_t beg, idx_t end) {
127 verify_range(beg, end);
128
129 idx_t beg_full_word = word_index_round_up(beg);
130 idx_t end_full_word = word_index(end);
131
132 if (beg_full_word < end_full_word) {
133 // The range includes at least one full word.
134 clear_range_within_word(beg, bit_index(beg_full_word));
135 clear_range_of_words(beg_full_word, end_full_word);
136 clear_range_within_word(bit_index(end_full_word), end);
137 } else {
138 // The range spans at most 2 partial words.
139 idx_t boundary = MIN2(bit_index(beg_full_word), end);
140 clear_range_within_word(beg, boundary);
141 clear_range_within_word(boundary, end);
142 }
143 }
144
145 void BitMap::set_large_range(idx_t beg, idx_t end) {
146 verify_range(beg, end);
147
148 idx_t beg_full_word = word_index_round_up(beg);
149 idx_t end_full_word = word_index(end);
150
151 assert(end_full_word - beg_full_word >= 32,
152 "the range must include at least 32 bytes");
153
154 // The range includes at least one full word.
155 set_range_within_word(beg, bit_index(beg_full_word));
156 set_large_range_of_words(beg_full_word, end_full_word);
157 set_range_within_word(bit_index(end_full_word), end);
158 }
159
160 void BitMap::clear_large_range(idx_t beg, idx_t end) {
161 verify_range(beg, end);
162
163 idx_t beg_full_word = word_index_round_up(beg);
164 idx_t end_full_word = word_index(end);
165
166 assert(end_full_word - beg_full_word >= 32,
167 "the range must include at least 32 bytes");
168
169 // The range includes at least one full word.
170 clear_range_within_word(beg, bit_index(beg_full_word));
171 clear_large_range_of_words(beg_full_word, end_full_word);
172 clear_range_within_word(bit_index(end_full_word), end);
173 }
174
175 void BitMap::at_put(idx_t offset, bool value) {
176 if (value) {
177 set_bit(offset);
178 } else {
179 clear_bit(offset);
180 }
181 }
182
183 // Return true to indicate that this thread changed
184 // the bit, false to indicate that someone else did.
185 // In either case, the requested bit is in the
186 // requested state some time during the period that
187 // this thread is executing this call. More importantly,
188 // if no other thread is executing an action to
189 // change the requested bit to a state other than
190 // the one that this thread is trying to set it to,
191 // then the the bit is in the expected state
192 // at exit from this method. However, rather than
193 // make such a strong assertion here, based on
194 // assuming such constrained use (which though true
195 // today, could change in the future to service some
196 // funky parallel algorithm), we encourage callers
197 // to do such verification, as and when appropriate.
198 bool BitMap::par_at_put(idx_t bit, bool value) {
199 return value ? par_set_bit(bit) : par_clear_bit(bit);
200 }
201
202 void BitMap::at_put_grow(idx_t offset, bool value) {
203 if (offset >= size()) {
204 resize(2 * MAX2(size(), offset));
205 }
206 at_put(offset, value);
207 }
208
209 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) {
210 if (value) {
211 set_range(start_offset, end_offset);
212 } else {
213 clear_range(start_offset, end_offset);
214 }
215 }
216
217 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
218 verify_range(beg, end);
219
220 idx_t beg_full_word = word_index_round_up(beg);
221 idx_t end_full_word = word_index(end);
222
223 if (beg_full_word < end_full_word) {
224 // The range includes at least one full word.
225 par_put_range_within_word(beg, bit_index(beg_full_word), value);
226 if (value) {
227 set_range_of_words(beg_full_word, end_full_word);
228 } else {
229 clear_range_of_words(beg_full_word, end_full_word);
230 }
231 par_put_range_within_word(bit_index(end_full_word), end, value);
232 } else {
233 // The range spans at most 2 partial words.
234 idx_t boundary = MIN2(bit_index(beg_full_word), end);
235 par_put_range_within_word(beg, boundary, value);
236 par_put_range_within_word(boundary, end, value);
237 }
238
239 }
240
241 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
242 if (value) {
243 set_large_range(beg, end);
244 } else {
245 clear_large_range(beg, end);
246 }
247 }
248
249 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
250 verify_range(beg, end);
251
252 idx_t beg_full_word = word_index_round_up(beg);
253 idx_t end_full_word = word_index(end);
254
255 assert(end_full_word - beg_full_word >= 32,
256 "the range must include at least 32 bytes");
257
258 // The range includes at least one full word.
259 par_put_range_within_word(beg, bit_index(beg_full_word), value);
260 if (value) {
261 set_large_range_of_words(beg_full_word, end_full_word);
262 } else {
263 clear_large_range_of_words(beg_full_word, end_full_word);
264 }
265 par_put_range_within_word(bit_index(end_full_word), end, value);
266 }
267
268 bool BitMap::contains(const BitMap other) const {
269 assert(size() == other.size(), "must have same size");
270 bm_word_t* dest_map = map();
271 bm_word_t* other_map = other.map();
272 idx_t size = size_in_words();
273 for (idx_t index = 0; index < size_in_words(); index++) {
274 bm_word_t word_union = dest_map[index] | other_map[index];
275 // If this has more bits set than dest_map[index], then other is not a
276 // subset.
277 if (word_union != dest_map[index]) return false;
278 }
279 return true;
280 }
281
282 bool BitMap::intersects(const BitMap other) const {
283 assert(size() == other.size(), "must have same size");
284 bm_word_t* dest_map = map();
285 bm_word_t* other_map = other.map();
286 idx_t size = size_in_words();
287 for (idx_t index = 0; index < size_in_words(); index++) {
288 if ((dest_map[index] & other_map[index]) != 0) return true;
289 }
290 // Otherwise, no intersection.
291 return false;
292 }
293
294 void BitMap::set_union(BitMap other) {
295 assert(size() == other.size(), "must have same size");
296 bm_word_t* dest_map = map();
297 bm_word_t* other_map = other.map();
298 idx_t size = size_in_words();
299 for (idx_t index = 0; index < size_in_words(); index++) {
300 dest_map[index] = dest_map[index] | other_map[index];
301 }
302 }
303
304
305 void BitMap::set_difference(BitMap other) {
306 assert(size() == other.size(), "must have same size");
307 bm_word_t* dest_map = map();
308 bm_word_t* other_map = other.map();
309 idx_t size = size_in_words();
310 for (idx_t index = 0; index < size_in_words(); index++) {
311 dest_map[index] = dest_map[index] & ~(other_map[index]);
312 }
313 }
314
315
316 void BitMap::set_intersection(BitMap other) {
317 assert(size() == other.size(), "must have same size");
318 bm_word_t* dest_map = map();
319 bm_word_t* other_map = other.map();
320 idx_t size = size_in_words();
321 for (idx_t index = 0; index < size; index++) {
322 dest_map[index] = dest_map[index] & other_map[index];
323 }
324 }
325
326
327 void BitMap::set_intersection_at_offset(BitMap other, idx_t offset) {
328 assert(other.size() >= offset, "offset not in range");
329 assert(other.size() - offset >= size(), "other not large enough");
330 // XXX Ideally, we would remove this restriction.
331 guarantee((offset % (sizeof(bm_word_t) * BitsPerByte)) == 0,
332 "Only handle aligned cases so far.");
333 bm_word_t* dest_map = map();
334 bm_word_t* other_map = other.map();
335 idx_t offset_word_ind = word_index(offset);
336 idx_t size = size_in_words();
337 for (idx_t index = 0; index < size; index++) {
338 dest_map[index] = dest_map[index] & other_map[offset_word_ind + index];
339 }
340 }
341
342 bool BitMap::set_union_with_result(BitMap other) {
343 assert(size() == other.size(), "must have same size");
344 bool changed = false;
345 bm_word_t* dest_map = map();
346 bm_word_t* other_map = other.map();
347 idx_t size = size_in_words();
348 for (idx_t index = 0; index < size; index++) {
349 idx_t temp = dest_map[index] | other_map[index];
350 changed = changed || (temp != dest_map[index]);
351 dest_map[index] = temp;
352 }
353 return changed;
354 }
355
356
357 bool BitMap::set_difference_with_result(BitMap other) {
358 assert(size() == other.size(), "must have same size");
359 bool changed = false;
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; index++) {
364 bm_word_t temp = dest_map[index] & ~(other_map[index]);
365 changed = changed || (temp != dest_map[index]);
366 dest_map[index] = temp;
367 }
368 return changed;
369 }
370
371
372 bool BitMap::set_intersection_with_result(BitMap other) {
373 assert(size() == other.size(), "must have same size");
374 bool changed = false;
375 bm_word_t* dest_map = map();
376 bm_word_t* other_map = other.map();
377 idx_t size = size_in_words();
378 for (idx_t index = 0; index < size; index++) {
379 bm_word_t orig = dest_map[index];
380 bm_word_t temp = orig & other_map[index];
381 changed = changed || (temp != orig);
382 dest_map[index] = temp;
383 }
384 return changed;
385 }
386
387
388 void BitMap::set_from(BitMap other) {
389 assert(size() == other.size(), "must have same size");
390 bm_word_t* dest_map = map();
391 bm_word_t* other_map = other.map();
392 idx_t size = size_in_words();
393 for (idx_t index = 0; index < size; index++) {
394 dest_map[index] = other_map[index];
395 }
396 }
397
398
399 bool BitMap::is_same(BitMap other) {
400 assert(size() == other.size(), "must have same size");
401 bm_word_t* dest_map = map();
402 bm_word_t* other_map = other.map();
403 idx_t size = size_in_words();
404 for (idx_t index = 0; index < size; index++) {
405 if (dest_map[index] != other_map[index]) return false;
406 }
407 return true;
408 }
409
410 bool BitMap::is_full() const {
411 bm_word_t* word = map();
412 idx_t rest = size();
413 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) {
414 if (*word != ~(bm_word_t)0) return false;
415 word++;
416 }
417 return rest == 0 || (*word | ~right_n_bits((int)rest)) == ~(bm_word_t)0;
418 }
419
420
421 bool BitMap::is_empty() const {
422 bm_word_t* word = map();
423 idx_t rest = size();
424 for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) {
425 if (*word != 0) return false;
426 word++;
427 }
428 return rest == 0 || (*word & right_n_bits((int)rest)) == 0;
429 }
430
431 void BitMap::clear_large() {
432 clear_large_range_of_words(0, size_in_words());
433 }
434
435 // Note that if the closure itself modifies the bitmap
436 // then modifications in and to the left of the _bit_ being
437 // currently sampled will not be seen. Note also that the
438 // interval [leftOffset, rightOffset) is right open.
439 bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) {
440 verify_range(leftOffset, rightOffset);
441
442 idx_t startIndex = word_index(leftOffset);
443 idx_t endIndex = MIN2(word_index(rightOffset) + 1, size_in_words());
444 for (idx_t index = startIndex, offset = leftOffset;
445 offset < rightOffset && index < endIndex;
446 offset = (++index) << LogBitsPerWord) {
447 idx_t rest = map(index) >> (offset & (BitsPerWord - 1));
448 for (; offset < rightOffset && rest != 0; offset++) {
449 if (rest & 1) {
450 if (!blk->do_bit(offset)) return false;
451 // resample at each closure application
452 // (see, for instance, CMS bug 4525989)
453 rest = map(index) >> (offset & (BitsPerWord -1));
454 }
455 rest = rest >> 1;
456 }
457 }
458 return true;
459 }
460
461 BitMap::idx_t* BitMap::_pop_count_table = NULL;
462
463 void BitMap::init_pop_count_table() {
464 if (_pop_count_table == NULL) {
465 BitMap::idx_t *table = NEW_C_HEAP_ARRAY(idx_t, 256, mtInternal);
466 for (uint i = 0; i < 256; i++) {
467 table[i] = num_set_bits(i);
468 }
469
470 intptr_t res = Atomic::cmpxchg_ptr((intptr_t) table,
471 (intptr_t*) &_pop_count_table,
472 (intptr_t) NULL_WORD);
473 if (res != NULL_WORD) {
474 guarantee( _pop_count_table == (void*) res, "invariant" );
475 FREE_C_HEAP_ARRAY(idx_t, table);
476 }
477 }
478 }
479
480 BitMap::idx_t BitMap::num_set_bits(bm_word_t w) {
481 idx_t bits = 0;
482
483 while (w != 0) {
484 while ((w & 1) == 0) {
485 w >>= 1;
486 }
487 bits++;
488 w >>= 1;
489 }
490 return bits;
491 }
492
493 BitMap::idx_t BitMap::num_set_bits_from_table(unsigned char c) {
494 assert(_pop_count_table != NULL, "precondition");
495 return _pop_count_table[c];
496 }
497
498 BitMap::idx_t BitMap::count_one_bits() const {
499 init_pop_count_table(); // If necessary.
500 idx_t sum = 0;
501 typedef unsigned char uchar;
502 for (idx_t i = 0; i < size_in_words(); i++) {
503 bm_word_t w = map()[i];
504 for (size_t j = 0; j < sizeof(bm_word_t); j++) {
505 sum += num_set_bits_from_table(uchar(w & 255));
506 w >>= 8;
507 }
508 }
509 return sum;
510 }
511
512 void BitMap::print_on_error(outputStream* st, const char* prefix) const {
513 st->print_cr("%s[" PTR_FORMAT ", " PTR_FORMAT ")",
514 prefix, p2i(map()), p2i((char*)map() + (size() >> LogBitsPerByte)));
515 }
516
517 #ifndef PRODUCT
518
519 void BitMap::print_on(outputStream* st) const {
520 tty->print("Bitmap(" SIZE_FORMAT "):", size());
521 for (idx_t index = 0; index < size(); index++) {
522 tty->print("%c", at(index) ? '1' : '0');
523 }
524 tty->cr();
525 }
526
527 class TestBitMap : public AllStatic {
528 const static BitMap::idx_t BITMAP_SIZE = 1024;
529 static void fillBitMap(BitMap& map) {
530 map.set_bit(1);
531 map.set_bit(3);
532 map.set_bit(17);
533 map.set_bit(512);
534 }
535
536 static void testResize(bool in_resource_area) {
537 {
538 BitMap map(0, in_resource_area);
539 map.resize(BITMAP_SIZE, in_resource_area);
540 fillBitMap(map);
541
542 BitMap map2(BITMAP_SIZE, in_resource_area);
543 fillBitMap(map2);
544 assert(map.is_same(map2), "could be");
545 }
546
547 {
548 BitMap map(128, in_resource_area);
549 map.resize(BITMAP_SIZE, in_resource_area);
550 fillBitMap(map);
551
552 BitMap map2(BITMAP_SIZE, in_resource_area);
553 fillBitMap(map2);
554 assert(map.is_same(map2), "could be");
555 }
556
557 {
558 BitMap map(BITMAP_SIZE, in_resource_area);
559 map.resize(BITMAP_SIZE, in_resource_area);
560 fillBitMap(map);
561
562 BitMap map2(BITMAP_SIZE, in_resource_area);
563 fillBitMap(map2);
564 assert(map.is_same(map2), "could be");
565 }
566 }
567
568 static void testResizeResource() {
569 ResourceMark rm;
570 testResize(true);
571 }
572
573 static void testResizeNonResource() {
574 const size_t bitmap_bytes = BITMAP_SIZE / BitsPerByte;
575
576 // Test the default behavior
577 testResize(false);
578
579 {
580 // Make sure that AllocatorMallocLimit is larger than our allocation request
581 // forcing it to call standard malloc()
582 SizeTFlagSetting fs(ArrayAllocatorMallocLimit, bitmap_bytes * 4);
583 testResize(false);
584 }
585 {
586 // Make sure that AllocatorMallocLimit is smaller than our allocation request
587 // forcing it to call mmap() (or equivalent)
588 SizeTFlagSetting fs(ArrayAllocatorMallocLimit, bitmap_bytes / 4);
589 testResize(false);
590 }
591 }
592
593 public:
594 static void test() {
595 testResizeResource();
596 testResizeNonResource();
597 }
598
599 };
600
601 void TestBitMap_test() {
602 TestBitMap::test();
603 }
604 #endif
605
606
607 BitMap2D::BitMap2D(bm_word_t* map, idx_t size_in_slots, idx_t bits_per_slot)
608 : _bits_per_slot(bits_per_slot)
609 , _map(map, size_in_slots * bits_per_slot)
610 {
611 }
612
613
614 BitMap2D::BitMap2D(idx_t size_in_slots, idx_t bits_per_slot)
615 : _bits_per_slot(bits_per_slot)
616 , _map(size_in_slots * bits_per_slot)
617 {
618 }