1 /*
   2  * Copyright (c) 2005, 2017, 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_PARALLEL_PARMARKBITMAP_HPP
  26 #define SHARE_VM_GC_PARALLEL_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 class ParCompactionManager;
  35 
  36 class ParMarkBitMap: public CHeapObj<mtGC>
  37 {
  38 public:
  39   typedef BitMap::idx_t idx_t;
  40 
  41   // Values returned by the iterate() methods.
  42   enum IterationStatus { incomplete, complete, full, would_overflow };
  43 
  44   inline ParMarkBitMap();
  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 
  51   // Return whether the specified begin or end bit is set.
  52   inline bool is_obj_beg(idx_t bit) const;
  53   inline bool is_obj_end(idx_t bit) const;
  54 
  55   // Traditional interface for testing whether an object is marked or not (these
  56   // test only the begin bits).
  57   inline bool is_marked(idx_t bit)      const;
  58   inline bool is_marked(HeapWord* addr) const;
  59   inline bool is_marked(oop obj)        const;
  60 
  61   inline bool is_unmarked(idx_t bit)      const;
  62   inline bool is_unmarked(HeapWord* addr) const;
  63   inline bool is_unmarked(oop obj)        const;
  64 
  65   // Convert sizes from bits to HeapWords and back.  An object that is n bits
  66   // long will be bits_to_words(n) words long.  An object that is m words long
  67   // will take up words_to_bits(m) bits in the bitmap.
  68   inline static size_t bits_to_words(idx_t bits);
  69   inline static idx_t  words_to_bits(size_t words);
  70 
  71   // Return the size in words of an object given a begin bit and an end bit, or
  72   // the equivalent beg_addr and end_addr.
  73   inline size_t obj_size(idx_t beg_bit, idx_t end_bit) const;
  74   inline size_t obj_size(HeapWord* beg_addr, HeapWord* end_addr) const;
  75 
  76   // Return the size in words of the object (a search is done for the end bit).
  77   inline size_t obj_size(idx_t beg_bit)  const;
  78   inline size_t obj_size(HeapWord* addr) const;
  79 
  80   // Apply live_closure to each live object that lies completely within the
  81   // range [live_range_beg, live_range_end).  This is used to iterate over the
  82   // compacted region of the heap.  Return values:
  83   //
  84   // incomplete         The iteration is not complete.  The last object that
  85   //                    begins in the range does not end in the range;
  86   //                    closure->source() is set to the start of that object.
  87   //
  88   // complete           The iteration is complete.  All objects in the range
  89   //                    were processed and the closure is not full;
  90   //                    closure->source() is set one past the end of the range.
  91   //
  92   // full               The closure is full; closure->source() is set to one
  93   //                    past the end of the last object processed.
  94   //
  95   // would_overflow     The next object in the range would overflow the closure;
  96   //                    closure->source() is set to the start of that object.
  97   IterationStatus iterate(ParMarkBitMapClosure* live_closure,
  98                           idx_t range_beg, idx_t range_end) const;
  99   inline IterationStatus iterate(ParMarkBitMapClosure* live_closure,
 100                                  HeapWord* range_beg,
 101                                  HeapWord* range_end) const;
 102 
 103   // Apply live closure as above and additionally apply dead_closure to all dead
 104   // space in the range [range_beg, dead_range_end).  Note that dead_range_end
 105   // must be >= range_end.  This is used to iterate over the dense prefix.
 106   //
 107   // This method assumes that if the first bit in the range (range_beg) is not
 108   // marked, then dead space begins at that point and the dead_closure is
 109   // applied.  Thus callers must ensure that range_beg is not in the middle of a
 110   // live object.
 111   IterationStatus iterate(ParMarkBitMapClosure* live_closure,
 112                           ParMarkBitMapClosure* dead_closure,
 113                           idx_t range_beg, idx_t range_end,
 114                           idx_t dead_range_end) const;
 115   inline IterationStatus iterate(ParMarkBitMapClosure* live_closure,
 116                                  ParMarkBitMapClosure* dead_closure,
 117                                  HeapWord* range_beg,
 118                                  HeapWord* range_end,
 119                                  HeapWord* dead_range_end) const;
 120 
 121   // Return the number of live words in the range [beg_addr, end_obj) due to
 122   // objects that start in the range.  If a live object extends onto the range,
 123   // the caller must detect and account for any live words due to that object.
 124   // If a live object extends beyond the end of the range, only the words within
 125   // the range are included in the result. The end of the range must be a live object,
 126   // which is the case when updating pointers.  This allows a branch to be removed
 127   // from inside the loop.
 128   size_t live_words_in_range(ParCompactionManager* cm, HeapWord* beg_addr, oop end_obj) const;
 129 
 130   inline HeapWord* region_start() const;
 131   inline HeapWord* region_end() const;
 132   inline size_t    region_size() const;
 133   inline size_t    size() const;
 134 
 135   size_t reserved_byte_size() const { return _reserved_byte_size; }
 136 
 137   // Convert a heap address to/from a bit index.
 138   inline idx_t     addr_to_bit(HeapWord* addr) const;
 139   inline HeapWord* bit_to_addr(idx_t bit) const;
 140 
 141   // Return the bit index of the first marked object that begins (or ends,
 142   // respectively) in the range [beg, end).  If no object is found, return end.
 143   inline idx_t find_obj_beg(idx_t beg, idx_t end) const;
 144   inline idx_t find_obj_end(idx_t beg, idx_t end) const;
 145 
 146   inline HeapWord* find_obj_beg(HeapWord* beg, HeapWord* end) const;
 147   inline HeapWord* find_obj_end(HeapWord* beg, HeapWord* end) const;
 148 
 149   // Clear a range of bits or the entire bitmap (both begin and end bits are
 150   // cleared).
 151   inline void clear_range(idx_t beg, idx_t end);
 152 
 153   // Return the number of bits required to represent the specified number of
 154   // HeapWords, or the specified region.
 155   static inline idx_t bits_required(size_t words);
 156   static inline idx_t bits_required(MemRegion covered_region);
 157 
 158   void print_on_error(outputStream* st) const {
 159     st->print_cr("Marking Bits: (ParMarkBitMap*) " PTR_FORMAT, p2i(this));
 160     _beg_bits.print_on_error(st, " Begin Bits: ");
 161     _end_bits.print_on_error(st, " End Bits:   ");
 162   }
 163 
 164 #ifdef  ASSERT
 165   void verify_clear() const;
 166   inline void verify_bit(idx_t bit) const;
 167   inline void verify_addr(HeapWord* addr) const;
 168 #endif  // #ifdef ASSERT
 169 
 170 private:
 171   size_t live_words_in_range_helper(HeapWord* beg_addr, oop end_obj) const;
 172 
 173   bool is_live_words_in_range_in_cache(ParCompactionManager* cm, HeapWord* beg_addr) const;
 174   size_t live_words_in_range_use_cache(ParCompactionManager* cm, HeapWord* beg_addr, oop end_obj) const;
 175   void update_live_words_in_range_cache(ParCompactionManager* cm, HeapWord* beg_addr, oop end_obj, size_t result) const;
 176 
 177   // Each bit in the bitmap represents one unit of 'object granularity.' Objects
 178   // are double-word aligned in 32-bit VMs, but not in 64-bit VMs, so the 32-bit
 179   // granularity is 2, 64-bit is 1.
 180   static inline size_t obj_granularity() { return size_t(MinObjAlignment); }
 181   static inline int obj_granularity_shift() { return LogMinObjAlignment; }
 182 
 183   HeapWord*       _region_start;
 184   size_t          _region_size;
 185   BitMapView      _beg_bits;
 186   BitMapView      _end_bits;
 187   PSVirtualSpace* _virtual_space;
 188   size_t          _reserved_byte_size;
 189 };
 190 
 191 #endif // SHARE_VM_GC_PARALLEL_PARMARKBITMAP_HPP