1 /*
   2  * Copyright (c) 2005, 2012, 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 #ifndef SHARE_VM_GC_IMPLEMENTATION_PARALLELSCAVENGE_PARMARKBITMAP_HPP
  26 #define SHARE_VM_GC_IMPLEMENTATION_PARALLELSCAVENGE_PARMARKBITMAP_HPP
  27 
  28 #include "memory/memRegion.hpp"
  29 #include "gc_implementation/parallelScavenge/psVirtualspace.hpp"
  30 #include "utilities/bitMap.inline.hpp"
  31 
  32 class oopDesc;
  33 class ParMarkBitMapClosure;

  34 
  35 class ParMarkBitMap: public CHeapObj<mtGC>
  36 {
  37 public:
  38   typedef BitMap::idx_t idx_t;
  39 
  40   // Values returned by the iterate() methods.
  41   enum IterationStatus { incomplete, complete, full, would_overflow };
  42 
  43   inline ParMarkBitMap();
  44   inline ParMarkBitMap(MemRegion covered_region);
  45   bool initialize(MemRegion covered_region);
  46 
  47   // Atomically mark an object as live.
  48   bool mark_obj(HeapWord* addr, size_t size);
  49   inline bool mark_obj(oop obj, int size);
  50   inline bool mark_obj(oop obj);
  51 
  52   // Return whether the specified begin or end bit is set.
  53   inline bool is_obj_beg(idx_t bit) const;
  54   inline bool is_obj_end(idx_t bit) const;
  55 
  56   // Traditional interface for testing whether an object is marked or not (these
  57   // test only the begin bits).
  58   inline bool is_marked(idx_t bit)      const;
  59   inline bool is_marked(HeapWord* addr) const;
  60   inline bool is_marked(oop obj)        const;
  61 
  62   inline bool is_unmarked(idx_t bit)      const;
  63   inline bool is_unmarked(HeapWord* addr) const;
  64   inline bool is_unmarked(oop obj)        const;
  65 
  66   // Convert sizes from bits to HeapWords and back.  An object that is n bits
  67   // long will be bits_to_words(n) words long.  An object that is m words long
  68   // will take up words_to_bits(m) bits in the bitmap.
  69   inline static size_t bits_to_words(idx_t bits);
  70   inline static idx_t  words_to_bits(size_t words);
  71 
  72   // Return the size in words of an object given a begin bit and an end bit, or
  73   // the equivalent beg_addr and end_addr.
  74   inline size_t obj_size(idx_t beg_bit, idx_t end_bit) const;
  75   inline size_t obj_size(HeapWord* beg_addr, HeapWord* end_addr) const;
  76 
  77   // Return the size in words of the object (a search is done for the end bit).
  78   inline size_t obj_size(idx_t beg_bit)  const;
  79   inline size_t obj_size(HeapWord* addr) const;
  80   inline size_t obj_size(oop obj)        const;
  81 
  82   // Synonyms for the above.
  83   size_t obj_size_in_words(oop obj) const { return obj_size((HeapWord*)obj); }
  84   size_t obj_size_in_words(HeapWord* addr) const { return obj_size(addr); }
  85 
  86   // Apply live_closure to each live object that lies completely within the
  87   // range [live_range_beg, live_range_end).  This is used to iterate over the
  88   // compacted region of the heap.  Return values:
  89   //
  90   // incomplete         The iteration is not complete.  The last object that
  91   //                    begins in the range does not end in the range;
  92   //                    closure->source() is set to the start of that object.
  93   //
  94   // complete           The iteration is complete.  All objects in the range
  95   //                    were processed and the closure is not full;
  96   //                    closure->source() is set one past the end of the range.
  97   //
  98   // full               The closure is full; closure->source() is set to one
  99   //                    past the end of the last object processed.
 100   //
 101   // would_overflow     The next object in the range would overflow the closure;
 102   //                    closure->source() is set to the start of that object.
 103   IterationStatus iterate(ParMarkBitMapClosure* live_closure,
 104                           idx_t range_beg, idx_t range_end) const;
 105   inline IterationStatus iterate(ParMarkBitMapClosure* live_closure,
 106                                  HeapWord* range_beg,
 107                                  HeapWord* range_end) const;
 108 
 109   // Apply live closure as above and additionally apply dead_closure to all dead
 110   // space in the range [range_beg, dead_range_end).  Note that dead_range_end
 111   // must be >= range_end.  This is used to iterate over the dense prefix.
 112   //
 113   // This method assumes that if the first bit in the range (range_beg) is not
 114   // marked, then dead space begins at that point and the dead_closure is
 115   // applied.  Thus callers must ensure that range_beg is not in the middle of a
 116   // live object.
 117   IterationStatus iterate(ParMarkBitMapClosure* live_closure,
 118                           ParMarkBitMapClosure* dead_closure,
 119                           idx_t range_beg, idx_t range_end,
 120                           idx_t dead_range_end) const;
 121   inline IterationStatus iterate(ParMarkBitMapClosure* live_closure,
 122                                  ParMarkBitMapClosure* dead_closure,
 123                                  HeapWord* range_beg,
 124                                  HeapWord* range_end,
 125                                  HeapWord* dead_range_end) const;
 126 
 127   // Return the number of live words in the range [beg_addr, end_addr) due to
 128   // objects that start in the range.  If a live object extends onto the range,
 129   // the caller must detect and account for any live words due to that object.
 130   // If a live object extends beyond the end of the range, only the words within
 131   // the range are included in the result.
 132   size_t live_words_in_range(HeapWord* beg_addr, HeapWord* end_addr) const;
 133 
 134   // Same as the above, except the end of the range must be a live object, which
 135   // is the case when updating pointers.  This allows a branch to be removed
 136   // from inside the loop.
 137   size_t live_words_in_range(HeapWord* beg_addr, oop end_obj) const;
 138 
 139   inline HeapWord* region_start() const;
 140   inline HeapWord* region_end() const;
 141   inline size_t    region_size() const;
 142   inline size_t    size() const;
 143 
 144   // Convert a heap address to/from a bit index.
 145   inline idx_t     addr_to_bit(HeapWord* addr) const;
 146   inline HeapWord* bit_to_addr(idx_t bit) const;
 147 
 148   // Return the bit index of the first marked object that begins (or ends,
 149   // respectively) in the range [beg, end).  If no object is found, return end.
 150   inline idx_t find_obj_beg(idx_t beg, idx_t end) const;
 151   inline idx_t find_obj_end(idx_t beg, idx_t end) const;
 152 
 153   inline HeapWord* find_obj_beg(HeapWord* beg, HeapWord* end) const;
 154   inline HeapWord* find_obj_end(HeapWord* beg, HeapWord* end) const;
 155 
 156   // Clear a range of bits or the entire bitmap (both begin and end bits are
 157   // cleared).
 158   inline void clear_range(idx_t beg, idx_t end);
 159   inline void clear() { clear_range(0, size()); }
 160 
 161   // Return the number of bits required to represent the specified number of
 162   // HeapWords, or the specified region.
 163   static inline idx_t bits_required(size_t words);
 164   static inline idx_t bits_required(MemRegion covered_region);
 165   static inline idx_t words_required(MemRegion covered_region);
 166 
 167 #ifndef PRODUCT
 168   // CAS statistics.
 169   size_t cas_tries() { return _cas_tries; }
 170   size_t cas_retries() { return _cas_retries; }
 171   size_t cas_by_another() { return _cas_by_another; }
 172 
 173   void reset_counters();
 174 #endif  // #ifndef PRODUCT
 175 
 176   void print_on_error(outputStream* st) const {
 177     st->print_cr("Marking Bits: (ParMarkBitMap*) " PTR_FORMAT, this);
 178     _beg_bits.print_on_error(st, " Begin Bits: ");
 179     _end_bits.print_on_error(st, " End Bits:   ");
 180   }
 181 
 182 #ifdef  ASSERT
 183   void verify_clear() const;
 184   inline void verify_bit(idx_t bit) const;
 185   inline void verify_addr(HeapWord* addr) const;
 186 #endif  // #ifdef ASSERT
 187 
 188 private:
 189   // Each bit in the bitmap represents one unit of 'object granularity.' Objects
 190   // are double-word aligned in 32-bit VMs, but not in 64-bit VMs, so the 32-bit
 191   // granularity is 2, 64-bit is 1.
 192   static inline size_t obj_granularity() { return size_t(MinObjAlignment); }
 193   static inline int obj_granularity_shift() { return LogMinObjAlignment; }
 194 
 195   HeapWord*       _region_start;
 196   size_t          _region_size;
 197   BitMap          _beg_bits;
 198   BitMap          _end_bits;
 199   PSVirtualSpace* _virtual_space;
 200 
 201 #ifndef PRODUCT
 202   size_t _cas_tries;
 203   size_t _cas_retries;
 204   size_t _cas_by_another;
 205 #endif  // #ifndef PRODUCT
 206 };
 207 
 208 inline ParMarkBitMap::ParMarkBitMap():
 209   _beg_bits(),
 210   _end_bits()
 211 {
 212   _region_start = 0;
 213   _virtual_space = 0;
 214 }
 215 
 216 inline ParMarkBitMap::ParMarkBitMap(MemRegion covered_region):
 217   _beg_bits(),
 218   _end_bits()
 219 {
 220   initialize(covered_region);
 221 }
 222 
 223 inline void ParMarkBitMap::clear_range(idx_t beg, idx_t end)
 224 {
 225   _beg_bits.clear_range(beg, end);
 226   _end_bits.clear_range(beg, end);
 227 }
 228 
 229 inline ParMarkBitMap::idx_t
 230 ParMarkBitMap::bits_required(size_t words)
 231 {
 232   // Need two bits (one begin bit, one end bit) for each unit of 'object
 233   // granularity' in the heap.
 234   return words_to_bits(words * 2);
 235 }
 236 
 237 inline ParMarkBitMap::idx_t
 238 ParMarkBitMap::bits_required(MemRegion covered_region)
 239 {
 240   return bits_required(covered_region.word_size());
 241 }
 242 
 243 inline ParMarkBitMap::idx_t
 244 ParMarkBitMap::words_required(MemRegion covered_region)
 245 {
 246   return bits_required(covered_region) / BitsPerWord;
 247 }
 248 
 249 inline HeapWord*
 250 ParMarkBitMap::region_start() const
 251 {
 252   return _region_start;
 253 }
 254 
 255 inline HeapWord*
 256 ParMarkBitMap::region_end() const
 257 {
 258   return region_start() + region_size();
 259 }
 260 
 261 inline size_t
 262 ParMarkBitMap::region_size() const
 263 {
 264   return _region_size;
 265 }
 266 
 267 inline size_t
 268 ParMarkBitMap::size() const
 269 {
 270   return _beg_bits.size();
 271 }
 272 
 273 inline bool ParMarkBitMap::is_obj_beg(idx_t bit) const
 274 {
 275   return _beg_bits.at(bit);
 276 }
 277 
 278 inline bool ParMarkBitMap::is_obj_end(idx_t bit) const
 279 {
 280   return _end_bits.at(bit);
 281 }
 282 
 283 inline bool ParMarkBitMap::is_marked(idx_t bit) const
 284 {
 285   return is_obj_beg(bit);
 286 }
 287 
 288 inline bool ParMarkBitMap::is_marked(HeapWord* addr) const
 289 {
 290   return is_marked(addr_to_bit(addr));
 291 }
 292 
 293 inline bool ParMarkBitMap::is_marked(oop obj) const
 294 {
 295   return is_marked((HeapWord*)obj);
 296 }
 297 
 298 inline bool ParMarkBitMap::is_unmarked(idx_t bit) const
 299 {
 300   return !is_marked(bit);
 301 }
 302 
 303 inline bool ParMarkBitMap::is_unmarked(HeapWord* addr) const
 304 {
 305   return !is_marked(addr);
 306 }
 307 
 308 inline bool ParMarkBitMap::is_unmarked(oop obj) const
 309 {
 310   return !is_marked(obj);
 311 }
 312 
 313 inline size_t
 314 ParMarkBitMap::bits_to_words(idx_t bits)
 315 {
 316   return bits << obj_granularity_shift();
 317 }
 318 
 319 inline ParMarkBitMap::idx_t
 320 ParMarkBitMap::words_to_bits(size_t words)
 321 {
 322   return words >> obj_granularity_shift();
 323 }
 324 
 325 inline size_t ParMarkBitMap::obj_size(idx_t beg_bit, idx_t end_bit) const
 326 {
 327   DEBUG_ONLY(verify_bit(beg_bit);)
 328   DEBUG_ONLY(verify_bit(end_bit);)
 329   return bits_to_words(end_bit - beg_bit + 1);
 330 }
 331 
 332 inline size_t
 333 ParMarkBitMap::obj_size(HeapWord* beg_addr, HeapWord* end_addr) const
 334 {
 335   DEBUG_ONLY(verify_addr(beg_addr);)
 336   DEBUG_ONLY(verify_addr(end_addr);)
 337   return pointer_delta(end_addr, beg_addr) + obj_granularity();
 338 }
 339 
 340 inline size_t ParMarkBitMap::obj_size(idx_t beg_bit) const
 341 {
 342   const idx_t end_bit = _end_bits.get_next_one_offset_inline(beg_bit, size());
 343   assert(is_marked(beg_bit), "obj not marked");
 344   assert(end_bit < size(), "end bit missing");
 345   return obj_size(beg_bit, end_bit);
 346 }
 347 
 348 inline size_t ParMarkBitMap::obj_size(HeapWord* addr) const
 349 {
 350   return obj_size(addr_to_bit(addr));
 351 }
 352 
 353 inline size_t ParMarkBitMap::obj_size(oop obj) const
 354 {
 355   return obj_size((HeapWord*)obj);
 356 }
 357 
 358 inline ParMarkBitMap::IterationStatus
 359 ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure,
 360                        HeapWord* range_beg,
 361                        HeapWord* range_end) const
 362 {
 363   return iterate(live_closure, addr_to_bit(range_beg), addr_to_bit(range_end));
 364 }
 365 
 366 inline ParMarkBitMap::IterationStatus
 367 ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure,
 368                        ParMarkBitMapClosure* dead_closure,
 369                        HeapWord* range_beg,
 370                        HeapWord* range_end,
 371                        HeapWord* dead_range_end) const
 372 {
 373   return iterate(live_closure, dead_closure,
 374                  addr_to_bit(range_beg), addr_to_bit(range_end),
 375                  addr_to_bit(dead_range_end));
 376 }
 377 
 378 inline bool
 379 ParMarkBitMap::mark_obj(oop obj, int size)
 380 {
 381   return mark_obj((HeapWord*)obj, (size_t)size);
 382 }
 383 
 384 inline BitMap::idx_t
 385 ParMarkBitMap::addr_to_bit(HeapWord* addr) const
 386 {
 387   DEBUG_ONLY(verify_addr(addr);)
 388   return words_to_bits(pointer_delta(addr, region_start()));
 389 }
 390 
 391 inline HeapWord*
 392 ParMarkBitMap::bit_to_addr(idx_t bit) const
 393 {
 394   DEBUG_ONLY(verify_bit(bit);)
 395   return region_start() + bits_to_words(bit);
 396 }
 397 
 398 inline ParMarkBitMap::idx_t
 399 ParMarkBitMap::find_obj_beg(idx_t beg, idx_t end) const
 400 {
 401   return _beg_bits.get_next_one_offset_inline_aligned_right(beg, end);
 402 }
 403 
 404 inline ParMarkBitMap::idx_t
 405 ParMarkBitMap::find_obj_end(idx_t beg, idx_t end) const
 406 {
 407   return _end_bits.get_next_one_offset_inline_aligned_right(beg, end);
 408 }
 409 
 410 inline HeapWord*
 411 ParMarkBitMap::find_obj_beg(HeapWord* beg, HeapWord* end) const
 412 {
 413   const idx_t beg_bit = addr_to_bit(beg);
 414   const idx_t end_bit = addr_to_bit(end);
 415   const idx_t search_end = BitMap::word_align_up(end_bit);
 416   const idx_t res_bit = MIN2(find_obj_beg(beg_bit, search_end), end_bit);
 417   return bit_to_addr(res_bit);
 418 }
 419 
 420 inline HeapWord*
 421 ParMarkBitMap::find_obj_end(HeapWord* beg, HeapWord* end) const
 422 {
 423   const idx_t beg_bit = addr_to_bit(beg);
 424   const idx_t end_bit = addr_to_bit(end);
 425   const idx_t search_end = BitMap::word_align_up(end_bit);
 426   const idx_t res_bit = MIN2(find_obj_end(beg_bit, search_end), end_bit);
 427   return bit_to_addr(res_bit);
 428 }
 429 
 430 #ifdef  ASSERT
 431 inline void ParMarkBitMap::verify_bit(idx_t bit) const {
 432   // Allow one past the last valid bit; useful for loop bounds.
 433   assert(bit <= _beg_bits.size(), "bit out of range");
 434 }
 435 
 436 inline void ParMarkBitMap::verify_addr(HeapWord* addr) const {
 437   // Allow one past the last valid address; useful for loop bounds.
 438   assert(addr >= region_start(), "addr too small");
 439   assert(addr <= region_start() + region_size(), "addr too big");


 440 }
 441 #endif  // #ifdef ASSERT
 442 
 443 #endif // SHARE_VM_GC_IMPLEMENTATION_PARALLELSCAVENGE_PARMARKBITMAP_HPP
--- EOF ---