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