duke@435: /*
mikael@4153:  * Copyright (c) 2005, 2012, Oracle and/or its affiliates. All rights reserved.
duke@435:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@435:  *
duke@435:  * This code is free software; you can redistribute it and/or modify it
duke@435:  * under the terms of the GNU General Public License version 2 only, as
duke@435:  * published by the Free Software Foundation.
duke@435:  *
duke@435:  * This code is distributed in the hope that it will be useful, but WITHOUT
duke@435:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@435:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
duke@435:  * version 2 for more details (a copy is included in the LICENSE file that
duke@435:  * accompanied this code).
duke@435:  *
duke@435:  * You should have received a copy of the GNU General Public License version
duke@435:  * 2 along with this work; if not, write to the Free Software Foundation,
duke@435:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@435:  *
trims@1907:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
trims@1907:  * or visit www.oracle.com if you need additional information or have any
trims@1907:  * questions.
duke@435:  *
duke@435:  */
duke@435: 
stefank@2314: #ifndef SHARE_VM_GC_IMPLEMENTATION_PARALLELSCAVENGE_PARMARKBITMAP_HPP
stefank@2314: #define SHARE_VM_GC_IMPLEMENTATION_PARALLELSCAVENGE_PARMARKBITMAP_HPP
stefank@2314: 
stefank@2325: #include "memory/memRegion.hpp"
stefank@2314: #include "gc_implementation/parallelScavenge/psVirtualspace.hpp"
stefank@2314: #include "utilities/bitMap.inline.hpp"
stefank@2314: 
duke@435: class oopDesc;
duke@435: class ParMarkBitMapClosure;
duke@435: 
zgu@3900: class ParMarkBitMap: public CHeapObj<mtGC>
duke@435: {
duke@435: public:
duke@435:   typedef BitMap::idx_t idx_t;
duke@435: 
duke@435:   // Values returned by the iterate() methods.
duke@435:   enum IterationStatus { incomplete, complete, full, would_overflow };
duke@435: 
duke@435:   inline ParMarkBitMap();
duke@435:   inline ParMarkBitMap(MemRegion covered_region);
duke@435:   bool initialize(MemRegion covered_region);
duke@435: 
duke@435:   // Atomically mark an object as live.
duke@435:   bool mark_obj(HeapWord* addr, size_t size);
duke@435:   inline bool mark_obj(oop obj, int size);
duke@435:   inline bool mark_obj(oop obj);
duke@435: 
duke@435:   // Return whether the specified begin or end bit is set.
duke@435:   inline bool is_obj_beg(idx_t bit) const;
duke@435:   inline bool is_obj_end(idx_t bit) const;
duke@435: 
duke@435:   // Traditional interface for testing whether an object is marked or not (these
duke@435:   // test only the begin bits).
duke@435:   inline bool is_marked(idx_t bit)      const;
duke@435:   inline bool is_marked(HeapWord* addr) const;
duke@435:   inline bool is_marked(oop obj)        const;
duke@435: 
duke@435:   inline bool is_unmarked(idx_t bit)      const;
duke@435:   inline bool is_unmarked(HeapWord* addr) const;
duke@435:   inline bool is_unmarked(oop obj)        const;
duke@435: 
duke@435:   // Convert sizes from bits to HeapWords and back.  An object that is n bits
duke@435:   // long will be bits_to_words(n) words long.  An object that is m words long
duke@435:   // will take up words_to_bits(m) bits in the bitmap.
duke@435:   inline static size_t bits_to_words(idx_t bits);
duke@435:   inline static idx_t  words_to_bits(size_t words);
duke@435: 
duke@435:   // Return the size in words of an object given a begin bit and an end bit, or
duke@435:   // the equivalent beg_addr and end_addr.
duke@435:   inline size_t obj_size(idx_t beg_bit, idx_t end_bit) const;
duke@435:   inline size_t obj_size(HeapWord* beg_addr, HeapWord* end_addr) const;
duke@435: 
duke@435:   // Return the size in words of the object (a search is done for the end bit).
duke@435:   inline size_t obj_size(idx_t beg_bit)  const;
duke@435:   inline size_t obj_size(HeapWord* addr) const;
duke@435:   inline size_t obj_size(oop obj)        const;
duke@435: 
duke@435:   // Synonyms for the above.
duke@435:   size_t obj_size_in_words(oop obj) const { return obj_size((HeapWord*)obj); }
duke@435:   size_t obj_size_in_words(HeapWord* addr) const { return obj_size(addr); }
duke@435: 
duke@435:   // Apply live_closure to each live object that lies completely within the
duke@435:   // range [live_range_beg, live_range_end).  This is used to iterate over the
duke@435:   // compacted region of the heap.  Return values:
duke@435:   //
duke@435:   // incomplete         The iteration is not complete.  The last object that
duke@435:   //                    begins in the range does not end in the range;
duke@435:   //                    closure->source() is set to the start of that object.
duke@435:   //
duke@435:   // complete           The iteration is complete.  All objects in the range
duke@435:   //                    were processed and the closure is not full;
duke@435:   //                    closure->source() is set one past the end of the range.
duke@435:   //
duke@435:   // full               The closure is full; closure->source() is set to one
duke@435:   //                    past the end of the last object processed.
duke@435:   //
duke@435:   // would_overflow     The next object in the range would overflow the closure;
duke@435:   //                    closure->source() is set to the start of that object.
duke@435:   IterationStatus iterate(ParMarkBitMapClosure* live_closure,
duke@435:                           idx_t range_beg, idx_t range_end) const;
duke@435:   inline IterationStatus iterate(ParMarkBitMapClosure* live_closure,
duke@435:                                  HeapWord* range_beg,
duke@435:                                  HeapWord* range_end) const;
duke@435: 
duke@435:   // Apply live closure as above and additionally apply dead_closure to all dead
duke@435:   // space in the range [range_beg, dead_range_end).  Note that dead_range_end
duke@435:   // must be >= range_end.  This is used to iterate over the dense prefix.
duke@435:   //
duke@435:   // This method assumes that if the first bit in the range (range_beg) is not
duke@435:   // marked, then dead space begins at that point and the dead_closure is
duke@435:   // applied.  Thus callers must ensure that range_beg is not in the middle of a
duke@435:   // live object.
duke@435:   IterationStatus iterate(ParMarkBitMapClosure* live_closure,
duke@435:                           ParMarkBitMapClosure* dead_closure,
duke@435:                           idx_t range_beg, idx_t range_end,
duke@435:                           idx_t dead_range_end) const;
duke@435:   inline IterationStatus iterate(ParMarkBitMapClosure* live_closure,
duke@435:                                  ParMarkBitMapClosure* dead_closure,
duke@435:                                  HeapWord* range_beg,
duke@435:                                  HeapWord* range_end,
duke@435:                                  HeapWord* dead_range_end) const;
duke@435: 
duke@435:   // Return the number of live words in the range [beg_addr, end_addr) due to
duke@435:   // objects that start in the range.  If a live object extends onto the range,
duke@435:   // the caller must detect and account for any live words due to that object.
duke@435:   // If a live object extends beyond the end of the range, only the words within
duke@435:   // the range are included in the result.
duke@435:   size_t live_words_in_range(HeapWord* beg_addr, HeapWord* end_addr) const;
duke@435: 
duke@435:   // Same as the above, except the end of the range must be a live object, which
duke@435:   // is the case when updating pointers.  This allows a branch to be removed
duke@435:   // from inside the loop.
duke@435:   size_t live_words_in_range(HeapWord* beg_addr, oop end_obj) const;
duke@435: 
duke@435:   inline HeapWord* region_start() const;
duke@435:   inline HeapWord* region_end() const;
duke@435:   inline size_t    region_size() const;
duke@435:   inline size_t    size() const;
duke@435: 
duke@435:   // Convert a heap address to/from a bit index.
duke@435:   inline idx_t     addr_to_bit(HeapWord* addr) const;
duke@435:   inline HeapWord* bit_to_addr(idx_t bit) const;
duke@435: 
duke@435:   // Return the bit index of the first marked object that begins (or ends,
duke@435:   // respectively) in the range [beg, end).  If no object is found, return end.
duke@435:   inline idx_t find_obj_beg(idx_t beg, idx_t end) const;
duke@435:   inline idx_t find_obj_end(idx_t beg, idx_t end) const;
duke@435: 
duke@435:   inline HeapWord* find_obj_beg(HeapWord* beg, HeapWord* end) const;
duke@435:   inline HeapWord* find_obj_end(HeapWord* beg, HeapWord* end) const;
duke@435: 
duke@435:   // Clear a range of bits or the entire bitmap (both begin and end bits are
duke@435:   // cleared).
duke@435:   inline void clear_range(idx_t beg, idx_t end);
duke@435:   inline void clear() { clear_range(0, size()); }
duke@435: 
duke@435:   // Return the number of bits required to represent the specified number of
duke@435:   // HeapWords, or the specified region.
duke@435:   static inline idx_t bits_required(size_t words);
duke@435:   static inline idx_t bits_required(MemRegion covered_region);
duke@435:   static inline idx_t words_required(MemRegion covered_region);
duke@435: 
duke@435: #ifndef PRODUCT
duke@435:   // CAS statistics.
duke@435:   size_t cas_tries() { return _cas_tries; }
duke@435:   size_t cas_retries() { return _cas_retries; }
duke@435:   size_t cas_by_another() { return _cas_by_another; }
duke@435: 
duke@435:   void reset_counters();
duke@435: #endif  // #ifndef PRODUCT
duke@435: 
stefank@4904:   void print_on_error(outputStream* st) const {
stefank@4904:     st->print_cr("Marking Bits: (ParMarkBitMap*) " PTR_FORMAT, this);
stefank@4904:     _beg_bits.print_on_error(st, " Begin Bits: ");
stefank@4904:     _end_bits.print_on_error(st, " End Bits:   ");
stefank@4904:   }
stefank@4904: 
duke@435: #ifdef  ASSERT
duke@435:   void verify_clear() const;
duke@435:   inline void verify_bit(idx_t bit) const;
duke@435:   inline void verify_addr(HeapWord* addr) const;
duke@435: #endif  // #ifdef ASSERT
duke@435: 
duke@435: private:
duke@435:   // Each bit in the bitmap represents one unit of 'object granularity.' Objects
duke@435:   // are double-word aligned in 32-bit VMs, but not in 64-bit VMs, so the 32-bit
duke@435:   // granularity is 2, 64-bit is 1.
duke@435:   static inline size_t obj_granularity() { return size_t(MinObjAlignment); }
jcoomes@1243:   static inline int obj_granularity_shift() { return LogMinObjAlignment; }
duke@435: 
duke@435:   HeapWord*       _region_start;
duke@435:   size_t          _region_size;
duke@435:   BitMap          _beg_bits;
duke@435:   BitMap          _end_bits;
duke@435:   PSVirtualSpace* _virtual_space;
duke@435: 
duke@435: #ifndef PRODUCT
duke@435:   size_t _cas_tries;
duke@435:   size_t _cas_retries;
duke@435:   size_t _cas_by_another;
duke@435: #endif  // #ifndef PRODUCT
duke@435: };
duke@435: 
duke@435: inline ParMarkBitMap::ParMarkBitMap():
ysr@777:   _beg_bits(),
ysr@777:   _end_bits()
duke@435: {
duke@435:   _region_start = 0;
duke@435:   _virtual_space = 0;
duke@435: }
duke@435: 
duke@435: inline ParMarkBitMap::ParMarkBitMap(MemRegion covered_region):
ysr@777:   _beg_bits(),
ysr@777:   _end_bits()
duke@435: {
duke@435:   initialize(covered_region);
duke@435: }
duke@435: 
duke@435: inline void ParMarkBitMap::clear_range(idx_t beg, idx_t end)
duke@435: {
duke@435:   _beg_bits.clear_range(beg, end);
duke@435:   _end_bits.clear_range(beg, end);
duke@435: }
duke@435: 
duke@435: inline ParMarkBitMap::idx_t
duke@435: ParMarkBitMap::bits_required(size_t words)
duke@435: {
duke@435:   // Need two bits (one begin bit, one end bit) for each unit of 'object
duke@435:   // granularity' in the heap.
duke@435:   return words_to_bits(words * 2);
duke@435: }
duke@435: 
duke@435: inline ParMarkBitMap::idx_t
duke@435: ParMarkBitMap::bits_required(MemRegion covered_region)
duke@435: {
duke@435:   return bits_required(covered_region.word_size());
duke@435: }
duke@435: 
duke@435: inline ParMarkBitMap::idx_t
duke@435: ParMarkBitMap::words_required(MemRegion covered_region)
duke@435: {
duke@435:   return bits_required(covered_region) / BitsPerWord;
duke@435: }
duke@435: 
duke@435: inline HeapWord*
duke@435: ParMarkBitMap::region_start() const
duke@435: {
duke@435:   return _region_start;
duke@435: }
duke@435: 
duke@435: inline HeapWord*
duke@435: ParMarkBitMap::region_end() const
duke@435: {
duke@435:   return region_start() + region_size();
duke@435: }
duke@435: 
duke@435: inline size_t
duke@435: ParMarkBitMap::region_size() const
duke@435: {
duke@435:   return _region_size;
duke@435: }
duke@435: 
duke@435: inline size_t
duke@435: ParMarkBitMap::size() const
duke@435: {
duke@435:   return _beg_bits.size();
duke@435: }
duke@435: 
duke@435: inline bool ParMarkBitMap::is_obj_beg(idx_t bit) const
duke@435: {
duke@435:   return _beg_bits.at(bit);
duke@435: }
duke@435: 
duke@435: inline bool ParMarkBitMap::is_obj_end(idx_t bit) const
duke@435: {
duke@435:   return _end_bits.at(bit);
duke@435: }
duke@435: 
duke@435: inline bool ParMarkBitMap::is_marked(idx_t bit) const
duke@435: {
duke@435:   return is_obj_beg(bit);
duke@435: }
duke@435: 
duke@435: inline bool ParMarkBitMap::is_marked(HeapWord* addr) const
duke@435: {
duke@435:   return is_marked(addr_to_bit(addr));
duke@435: }
duke@435: 
duke@435: inline bool ParMarkBitMap::is_marked(oop obj) const
duke@435: {
duke@435:   return is_marked((HeapWord*)obj);
duke@435: }
duke@435: 
duke@435: inline bool ParMarkBitMap::is_unmarked(idx_t bit) const
duke@435: {
duke@435:   return !is_marked(bit);
duke@435: }
duke@435: 
duke@435: inline bool ParMarkBitMap::is_unmarked(HeapWord* addr) const
duke@435: {
duke@435:   return !is_marked(addr);
duke@435: }
duke@435: 
duke@435: inline bool ParMarkBitMap::is_unmarked(oop obj) const
duke@435: {
duke@435:   return !is_marked(obj);
duke@435: }
duke@435: 
duke@435: inline size_t
duke@435: ParMarkBitMap::bits_to_words(idx_t bits)
duke@435: {
jcoomes@1243:   return bits << obj_granularity_shift();
duke@435: }
duke@435: 
duke@435: inline ParMarkBitMap::idx_t
duke@435: ParMarkBitMap::words_to_bits(size_t words)
duke@435: {
jcoomes@1243:   return words >> obj_granularity_shift();
duke@435: }
duke@435: 
duke@435: inline size_t ParMarkBitMap::obj_size(idx_t beg_bit, idx_t end_bit) const
duke@435: {
duke@435:   DEBUG_ONLY(verify_bit(beg_bit);)
duke@435:   DEBUG_ONLY(verify_bit(end_bit);)
duke@435:   return bits_to_words(end_bit - beg_bit + 1);
duke@435: }
duke@435: 
duke@435: inline size_t
duke@435: ParMarkBitMap::obj_size(HeapWord* beg_addr, HeapWord* end_addr) const
duke@435: {
duke@435:   DEBUG_ONLY(verify_addr(beg_addr);)
duke@435:   DEBUG_ONLY(verify_addr(end_addr);)
duke@435:   return pointer_delta(end_addr, beg_addr) + obj_granularity();
duke@435: }
duke@435: 
duke@435: inline size_t ParMarkBitMap::obj_size(idx_t beg_bit) const
duke@435: {
ysr@777:   const idx_t end_bit = _end_bits.get_next_one_offset_inline(beg_bit, size());
duke@435:   assert(is_marked(beg_bit), "obj not marked");
duke@435:   assert(end_bit < size(), "end bit missing");
duke@435:   return obj_size(beg_bit, end_bit);
duke@435: }
duke@435: 
duke@435: inline size_t ParMarkBitMap::obj_size(HeapWord* addr) const
duke@435: {
duke@435:   return obj_size(addr_to_bit(addr));
duke@435: }
duke@435: 
duke@435: inline size_t ParMarkBitMap::obj_size(oop obj) const
duke@435: {
duke@435:   return obj_size((HeapWord*)obj);
duke@435: }
duke@435: 
duke@435: inline ParMarkBitMap::IterationStatus
duke@435: ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure,
duke@435:                        HeapWord* range_beg,
duke@435:                        HeapWord* range_end) const
duke@435: {
duke@435:   return iterate(live_closure, addr_to_bit(range_beg), addr_to_bit(range_end));
duke@435: }
duke@435: 
duke@435: inline ParMarkBitMap::IterationStatus
duke@435: ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure,
duke@435:                        ParMarkBitMapClosure* dead_closure,
duke@435:                        HeapWord* range_beg,
duke@435:                        HeapWord* range_end,
duke@435:                        HeapWord* dead_range_end) const
duke@435: {
duke@435:   return iterate(live_closure, dead_closure,
duke@435:                  addr_to_bit(range_beg), addr_to_bit(range_end),
duke@435:                  addr_to_bit(dead_range_end));
duke@435: }
duke@435: 
duke@435: inline bool
duke@435: ParMarkBitMap::mark_obj(oop obj, int size)
duke@435: {
duke@435:   return mark_obj((HeapWord*)obj, (size_t)size);
duke@435: }
duke@435: 
duke@435: inline BitMap::idx_t
duke@435: ParMarkBitMap::addr_to_bit(HeapWord* addr) const
duke@435: {
duke@435:   DEBUG_ONLY(verify_addr(addr);)
duke@435:   return words_to_bits(pointer_delta(addr, region_start()));
duke@435: }
duke@435: 
duke@435: inline HeapWord*
duke@435: ParMarkBitMap::bit_to_addr(idx_t bit) const
duke@435: {
duke@435:   DEBUG_ONLY(verify_bit(bit);)
duke@435:   return region_start() + bits_to_words(bit);
duke@435: }
duke@435: 
duke@435: inline ParMarkBitMap::idx_t
duke@435: ParMarkBitMap::find_obj_beg(idx_t beg, idx_t end) const
duke@435: {
ysr@777:   return _beg_bits.get_next_one_offset_inline_aligned_right(beg, end);
duke@435: }
duke@435: 
duke@435: inline ParMarkBitMap::idx_t
duke@435: ParMarkBitMap::find_obj_end(idx_t beg, idx_t end) const
duke@435: {
ysr@777:   return _end_bits.get_next_one_offset_inline_aligned_right(beg, end);
duke@435: }
duke@435: 
duke@435: inline HeapWord*
duke@435: ParMarkBitMap::find_obj_beg(HeapWord* beg, HeapWord* end) const
duke@435: {
duke@435:   const idx_t beg_bit = addr_to_bit(beg);
duke@435:   const idx_t end_bit = addr_to_bit(end);
duke@435:   const idx_t search_end = BitMap::word_align_up(end_bit);
duke@435:   const idx_t res_bit = MIN2(find_obj_beg(beg_bit, search_end), end_bit);
duke@435:   return bit_to_addr(res_bit);
duke@435: }
duke@435: 
duke@435: inline HeapWord*
duke@435: ParMarkBitMap::find_obj_end(HeapWord* beg, HeapWord* end) const
duke@435: {
duke@435:   const idx_t beg_bit = addr_to_bit(beg);
duke@435:   const idx_t end_bit = addr_to_bit(end);
duke@435:   const idx_t search_end = BitMap::word_align_up(end_bit);
duke@435:   const idx_t res_bit = MIN2(find_obj_end(beg_bit, search_end), end_bit);
duke@435:   return bit_to_addr(res_bit);
duke@435: }
duke@435: 
duke@435: #ifdef  ASSERT
duke@435: inline void ParMarkBitMap::verify_bit(idx_t bit) const {
duke@435:   // Allow one past the last valid bit; useful for loop bounds.
duke@435:   assert(bit <= _beg_bits.size(), "bit out of range");
duke@435: }
duke@435: 
duke@435: inline void ParMarkBitMap::verify_addr(HeapWord* addr) const {
duke@435:   // Allow one past the last valid address; useful for loop bounds.
duke@435:   assert(addr >= region_start(), "addr too small");
duke@435:   assert(addr <= region_start() + region_size(), "addr too big");
duke@435: }
duke@435: #endif  // #ifdef ASSERT
stefank@2314: 
stefank@2314: #endif // SHARE_VM_GC_IMPLEMENTATION_PARALLELSCAVENGE_PARMARKBITMAP_HPP