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