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