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