1 /*
   2  * Copyright (c) 1997, 2013, 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 "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     Copy::disjoint_words((HeapWord*)old_map, (HeapWord*) _map,
  72                          MIN2(old_size_in_words, new_size_in_words));
  73   } else {
  74     _map = _map_allocator.reallocate(new_size_in_words);
  75   }
  76 
  77   if (new_size_in_words > old_size_in_words) {
  78     clear_range_of_words(old_size_in_words, new_size_in_words);
  79   }
  80 }
  81 
  82 void BitMap::set_range_within_word(idx_t beg, idx_t end) {
  83   // With a valid range (beg <= end), this test ensures that end != 0, as
  84   // required by inverted_bit_mask_for_range.  Also avoids an unnecessary write.
  85   if (beg != end) {
  86     bm_word_t mask = inverted_bit_mask_for_range(beg, end);
  87     *word_addr(beg) |= ~mask;
  88   }
  89 }
  90 
  91 void BitMap::clear_range_within_word(idx_t beg, idx_t end) {
  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     bm_word_t mask = inverted_bit_mask_for_range(beg, end);
  96     *word_addr(beg) &= mask;
  97   }
  98 }
  99 
 100 void BitMap::par_put_range_within_word(idx_t beg, idx_t end, bool value) {
 101   assert(value == 0 || value == 1, "0 for clear, 1 for set");
 102   // With a valid range (beg <= end), this test ensures that end != 0, as
 103   // required by inverted_bit_mask_for_range.  Also avoids an unnecessary write.
 104   if (beg != end) {
 105     intptr_t* pw  = (intptr_t*)word_addr(beg);
 106     intptr_t  w   = *pw;
 107     intptr_t  mr  = (intptr_t)inverted_bit_mask_for_range(beg, end);
 108     intptr_t  nw  = value ? (w | ~mr) : (w & mr);
 109     while (true) {
 110       intptr_t res = Atomic::cmpxchg_ptr(nw, pw, w);
 111       if (res == w) break;
 112       w  = res;
 113       nw = value ? (w | ~mr) : (w & mr);
 114     }
 115   }
 116 }
 117 
 118 void BitMap::set_range(idx_t beg, idx_t end) {
 119   verify_range(beg, end);
 120 
 121   idx_t beg_full_word = word_index_round_up(beg);
 122   idx_t end_full_word = word_index(end);
 123 
 124   if (beg_full_word < end_full_word) {
 125     // The range includes at least one full word.
 126     set_range_within_word(beg, bit_index(beg_full_word));
 127     set_range_of_words(beg_full_word, end_full_word);
 128     set_range_within_word(bit_index(end_full_word), end);
 129   } else {
 130     // The range spans at most 2 partial words.
 131     idx_t boundary = MIN2(bit_index(beg_full_word), end);
 132     set_range_within_word(beg, boundary);
 133     set_range_within_word(boundary, end);
 134   }
 135 }
 136 
 137 void BitMap::clear_range(idx_t beg, idx_t end) {
 138   verify_range(beg, end);
 139 
 140   idx_t beg_full_word = word_index_round_up(beg);
 141   idx_t end_full_word = word_index(end);
 142 
 143   if (beg_full_word < end_full_word) {
 144     // The range includes at least one full word.
 145     clear_range_within_word(beg, bit_index(beg_full_word));
 146     clear_range_of_words(beg_full_word, end_full_word);
 147     clear_range_within_word(bit_index(end_full_word), end);
 148   } else {
 149     // The range spans at most 2 partial words.
 150     idx_t boundary = MIN2(bit_index(beg_full_word), end);
 151     clear_range_within_word(beg, boundary);
 152     clear_range_within_word(boundary, end);
 153   }
 154 }
 155 
 156 void BitMap::set_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   set_range_within_word(beg, bit_index(beg_full_word));
 167   set_large_range_of_words(beg_full_word, end_full_word);
 168   set_range_within_word(bit_index(end_full_word), end);
 169 }
 170 
 171 void BitMap::clear_large_range(idx_t beg, idx_t end) {
 172   verify_range(beg, end);
 173 
 174   idx_t beg_full_word = word_index_round_up(beg);
 175   idx_t end_full_word = word_index(end);
 176 
 177   assert(end_full_word - beg_full_word >= 32,
 178          "the range must include at least 32 bytes");
 179 
 180   // The range includes at least one full word.
 181   clear_range_within_word(beg, bit_index(beg_full_word));
 182   clear_large_range_of_words(beg_full_word, end_full_word);
 183   clear_range_within_word(bit_index(end_full_word), end);
 184 }
 185 
 186 void BitMap::at_put(idx_t offset, bool value) {
 187   if (value) {
 188     set_bit(offset);
 189   } else {
 190     clear_bit(offset);
 191   }
 192 }
 193 
 194 // Return true to indicate that this thread changed
 195 // the bit, false to indicate that someone else did.
 196 // In either case, the requested bit is in the
 197 // requested state some time during the period that
 198 // this thread is executing this call. More importantly,
 199 // if no other thread is executing an action to
 200 // change the requested bit to a state other than
 201 // the one that this thread is trying to set it to,
 202 // then the the bit is in the expected state
 203 // at exit from this method. However, rather than
 204 // make such a strong assertion here, based on
 205 // assuming such constrained use (which though true
 206 // today, could change in the future to service some
 207 // funky parallel algorithm), we encourage callers
 208 // to do such verification, as and when appropriate.
 209 bool BitMap::par_at_put(idx_t bit, bool value) {
 210   return value ? par_set_bit(bit) : par_clear_bit(bit);
 211 }
 212 
 213 void BitMap::at_put_grow(idx_t offset, bool value) {
 214   if (offset >= size()) {
 215     resize(2 * MAX2(size(), offset));
 216   }
 217   at_put(offset, value);
 218 }
 219 
 220 void BitMap::at_put_range(idx_t start_offset, idx_t end_offset, bool value) {
 221   if (value) {
 222     set_range(start_offset, end_offset);
 223   } else {
 224     clear_range(start_offset, end_offset);
 225   }
 226 }
 227 
 228 void BitMap::par_at_put_range(idx_t beg, idx_t end, bool value) {
 229   verify_range(beg, end);
 230 
 231   idx_t beg_full_word = word_index_round_up(beg);
 232   idx_t end_full_word = word_index(end);
 233 
 234   if (beg_full_word < end_full_word) {
 235     // The range includes at least one full word.
 236     par_put_range_within_word(beg, bit_index(beg_full_word), value);
 237     if (value) {
 238       set_range_of_words(beg_full_word, end_full_word);
 239     } else {
 240       clear_range_of_words(beg_full_word, end_full_word);
 241     }
 242     par_put_range_within_word(bit_index(end_full_word), end, value);
 243   } else {
 244     // The range spans at most 2 partial words.
 245     idx_t boundary = MIN2(bit_index(beg_full_word), end);
 246     par_put_range_within_word(beg, boundary, value);
 247     par_put_range_within_word(boundary, end, value);
 248   }
 249 
 250 }
 251 
 252 void BitMap::at_put_large_range(idx_t beg, idx_t end, bool value) {
 253   if (value) {
 254     set_large_range(beg, end);
 255   } else {
 256     clear_large_range(beg, end);
 257   }
 258 }
 259 
 260 void BitMap::par_at_put_large_range(idx_t beg, idx_t end, bool value) {
 261   verify_range(beg, end);
 262 
 263   idx_t beg_full_word = word_index_round_up(beg);
 264   idx_t end_full_word = word_index(end);
 265 
 266   assert(end_full_word - beg_full_word >= 32,
 267          "the range must include at least 32 bytes");
 268 
 269   // The range includes at least one full word.
 270   par_put_range_within_word(beg, bit_index(beg_full_word), value);
 271   if (value) {
 272     set_large_range_of_words(beg_full_word, end_full_word);
 273   } else {
 274     clear_large_range_of_words(beg_full_word, end_full_word);
 275   }
 276   par_put_range_within_word(bit_index(end_full_word), end, value);
 277 }
 278 
 279 bool BitMap::contains(const BitMap other) const {
 280   assert(size() == other.size(), "must have same size");
 281   bm_word_t* dest_map = map();
 282   bm_word_t* other_map = other.map();
 283   idx_t size = size_in_words();
 284   for (idx_t index = 0; index < size_in_words(); index++) {
 285     bm_word_t word_union = dest_map[index] | other_map[index];
 286     // If this has more bits set than dest_map[index], then other is not a
 287     // subset.
 288     if (word_union != dest_map[index]) return false;
 289   }
 290   return true;
 291 }
 292 
 293 bool BitMap::intersects(const BitMap other) const {
 294   assert(size() == other.size(), "must have same size");
 295   bm_word_t* dest_map = map();
 296   bm_word_t* other_map = other.map();
 297   idx_t size = size_in_words();
 298   for (idx_t index = 0; index < size_in_words(); index++) {
 299     if ((dest_map[index] & other_map[index]) != 0) return true;
 300   }
 301   // Otherwise, no intersection.
 302   return false;
 303 }
 304 
 305 void BitMap::set_union(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_difference(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_in_words(); index++) {
 322     dest_map[index] = dest_map[index] & ~(other_map[index]);
 323   }
 324 }
 325 
 326 
 327 void BitMap::set_intersection(BitMap other) {
 328   assert(size() == other.size(), "must have same size");
 329   bm_word_t* dest_map = map();
 330   bm_word_t* other_map = other.map();
 331   idx_t size = size_in_words();
 332   for (idx_t index = 0; index < size; index++) {
 333     dest_map[index]  = dest_map[index] & other_map[index];
 334   }
 335 }
 336 
 337 
 338 void BitMap::set_intersection_at_offset(BitMap other, idx_t offset) {
 339   assert(other.size() >= offset, "offset not in range");
 340   assert(other.size() - offset >= size(), "other not large enough");
 341   // XXX Ideally, we would remove this restriction.
 342   guarantee((offset % (sizeof(bm_word_t) * BitsPerByte)) == 0,
 343             "Only handle aligned cases so far.");
 344   bm_word_t* dest_map = map();
 345   bm_word_t* other_map = other.map();
 346   idx_t offset_word_ind = word_index(offset);
 347   idx_t size = size_in_words();
 348   for (idx_t index = 0; index < size; index++) {
 349     dest_map[index] = dest_map[index] & other_map[offset_word_ind + index];
 350   }
 351 }
 352 
 353 bool BitMap::set_union_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     idx_t temp = map(index) | other_map[index];
 361     changed = changed || (temp != map(index));
 362     map()[index] = temp;
 363   }
 364   return changed;
 365 }
 366 
 367 
 368 bool BitMap::set_difference_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 temp = dest_map[index] & ~(other_map[index]);
 376     changed = changed || (temp != dest_map[index]);
 377     dest_map[index] = temp;
 378   }
 379   return changed;
 380 }
 381 
 382 
 383 bool BitMap::set_intersection_with_result(BitMap other) {
 384   assert(size() == other.size(), "must have same size");
 385   bool changed = false;
 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     bm_word_t orig = dest_map[index];
 391     bm_word_t temp = orig & other_map[index];
 392     changed = changed || (temp != orig);
 393     dest_map[index]  = temp;
 394   }
 395   return changed;
 396 }
 397 
 398 
 399 void BitMap::set_from(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     dest_map[index] = other_map[index];
 406   }
 407 }
 408 
 409 
 410 bool BitMap::is_same(BitMap other) {
 411   assert(size() == other.size(), "must have same size");
 412   bm_word_t* dest_map = map();
 413   bm_word_t* other_map = other.map();
 414   idx_t size = size_in_words();
 415   for (idx_t index = 0; index < size; index++) {
 416     if (dest_map[index] != other_map[index]) return false;
 417   }
 418   return true;
 419 }
 420 
 421 bool BitMap::is_full() const {
 422   bm_word_t* word = map();
 423   idx_t rest = size();
 424   for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) {
 425     if (*word != (bm_word_t) AllBits) return false;
 426     word++;
 427   }
 428   return rest == 0 || (*word | ~right_n_bits((int)rest)) == (bm_word_t) AllBits;
 429 }
 430 
 431 
 432 bool BitMap::is_empty() const {
 433   bm_word_t* word = map();
 434   idx_t rest = size();
 435   for (; rest >= (idx_t) BitsPerWord; rest -= BitsPerWord) {
 436     if (*word != (bm_word_t) NoBits) return false;
 437     word++;
 438   }
 439   return rest == 0 || (*word & right_n_bits((int)rest)) == (bm_word_t) NoBits;
 440 }
 441 
 442 void BitMap::clear_large() {
 443   clear_large_range_of_words(0, size_in_words());
 444 }
 445 
 446 // Note that if the closure itself modifies the bitmap
 447 // then modifications in and to the left of the _bit_ being
 448 // currently sampled will not be seen. Note also that the
 449 // interval [leftOffset, rightOffset) is right open.
 450 bool BitMap::iterate(BitMapClosure* blk, idx_t leftOffset, idx_t rightOffset) {
 451   verify_range(leftOffset, rightOffset);
 452 
 453   idx_t startIndex = word_index(leftOffset);
 454   idx_t endIndex   = MIN2(word_index(rightOffset) + 1, size_in_words());
 455   for (idx_t index = startIndex, offset = leftOffset;
 456        offset < rightOffset && index < endIndex;
 457        offset = (++index) << LogBitsPerWord) {
 458     idx_t rest = map(index) >> (offset & (BitsPerWord - 1));
 459     for (; offset < rightOffset && rest != (bm_word_t)NoBits; offset++) {
 460       if (rest & 1) {
 461         if (!blk->do_bit(offset)) return false;
 462         //  resample at each closure application
 463         // (see, for instance, CMS bug 4525989)
 464         rest = map(index) >> (offset & (BitsPerWord -1));
 465       }
 466       rest = rest >> 1;
 467     }
 468   }
 469   return true;
 470 }
 471 
 472 BitMap::idx_t* BitMap::_pop_count_table = NULL;
 473 
 474 void BitMap::init_pop_count_table() {
 475   if (_pop_count_table == NULL) {
 476     BitMap::idx_t *table = NEW_C_HEAP_ARRAY(idx_t, 256, mtInternal);
 477     for (uint i = 0; i < 256; i++) {
 478       table[i] = num_set_bits(i);
 479     }
 480 
 481     intptr_t res = Atomic::cmpxchg_ptr((intptr_t)  table,
 482                                        (intptr_t*) &_pop_count_table,
 483                                        (intptr_t)  NULL_WORD);
 484     if (res != NULL_WORD) {
 485       guarantee( _pop_count_table == (void*) res, "invariant" );
 486       FREE_C_HEAP_ARRAY(bm_word_t, table, mtInternal);
 487     }
 488   }
 489 }
 490 
 491 BitMap::idx_t BitMap::num_set_bits(bm_word_t w) {
 492   idx_t bits = 0;
 493 
 494   while (w != 0) {
 495     while ((w & 1) == 0) {
 496       w >>= 1;
 497     }
 498     bits++;
 499     w >>= 1;
 500   }
 501   return bits;
 502 }
 503 
 504 BitMap::idx_t BitMap::num_set_bits_from_table(unsigned char c) {
 505   assert(_pop_count_table != NULL, "precondition");
 506   return _pop_count_table[c];
 507 }
 508 
 509 BitMap::idx_t BitMap::count_one_bits() const {
 510   init_pop_count_table(); // If necessary.
 511   idx_t sum = 0;
 512   typedef unsigned char uchar;
 513   for (idx_t i = 0; i < size_in_words(); i++) {
 514     bm_word_t w = map()[i];
 515     for (size_t j = 0; j < sizeof(bm_word_t); j++) {
 516       sum += num_set_bits_from_table(uchar(w & 255));
 517       w >>= 8;
 518     }
 519   }
 520   return sum;
 521 }
 522 
 523 void BitMap::print_on_error(outputStream* st, const char* prefix) const {
 524   st->print_cr("%s[" PTR_FORMAT ", " PTR_FORMAT ")",
 525       prefix, map(), (char*)map() + (size() >> LogBitsPerByte));
 526 }
 527 
 528 #ifndef PRODUCT
 529 
 530 void BitMap::print_on(outputStream* st) const {
 531   tty->print("Bitmap(%d):", size());
 532   for (idx_t index = 0; index < size(); index++) {
 533     tty->print("%c", at(index) ? '1' : '0');
 534   }
 535   tty->cr();
 536 }
 537 
 538 class TestBitMap : public AllStatic {
 539   const static BitMap::idx_t BITMAP_SIZE = 1024;
 540   static void fillBitMap(BitMap& map) {
 541     map.set_bit(1);
 542     map.set_bit(3);
 543     map.set_bit(17);
 544     map.set_bit(512);
 545   }
 546 
 547   static void testResize(bool in_resource_area) {
 548     {
 549       BitMap map(0, 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(128, 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       BitMap map(BITMAP_SIZE, in_resource_area);
 570       map.resize(BITMAP_SIZE, in_resource_area);
 571       fillBitMap(map);
 572 
 573       BitMap map2(BITMAP_SIZE, in_resource_area);
 574       fillBitMap(map2);
 575       assert(map.is_same(map2), "could be");
 576     }
 577   }
 578 
 579   static void testResizeResource() {
 580     ResourceMark rm;
 581     testResize(true);
 582   }
 583 
 584   static void testResizeNonResource() {
 585     testResize(false);
 586     {
 587       uintx bitmap_bytes = BITMAP_SIZE / BitsPerByte;
 588       UIntFlagSetting 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 }