/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

class oopDesc;

class ParMarkBitMapClosure;

class ParMarkBitMap: public CHeapObj

{

public:

  typedef BitMap::idx_t idx_t;

  // Values returned by the iterate() methods.

  enum IterationStatus { incomplete, complete, full, would_overflow };

  inline ParMarkBitMap();

  inline ParMarkBitMap(MemRegion covered_region);

  bool initialize(MemRegion covered_region);

  // Atomically mark an object as live.

  bool mark_obj(HeapWord* addr, size_t size);

  inline bool mark_obj(oop obj, int size);

  inline bool mark_obj(oop obj);

  // Return whether the specified begin or end bit is set.

  inline bool is_obj_beg(idx_t bit) const;

  inline bool is_obj_end(idx_t bit) const;

  // Traditional interface for testing whether an object is marked or not (these

  // test only the begin bits).

  inline bool is_marked(idx_t bit)      const;

  inline bool is_marked(HeapWord* addr) const;

  inline bool is_marked(oop obj)        const;

  inline bool is_unmarked(idx_t bit)      const;

  inline bool is_unmarked(HeapWord* addr) const;

  inline bool is_unmarked(oop obj)        const;

  // Convert sizes from bits to HeapWords and back.  An object that is n bits

  // long will be bits_to_words(n) words long.  An object that is m words long

  // will take up words_to_bits(m) bits in the bitmap.

  inline static size_t bits_to_words(idx_t bits);

  inline static idx_t  words_to_bits(size_t words);

  // Return the size in words of an object given a begin bit and an end bit, or

  // the equivalent beg_addr and end_addr.

  inline size_t obj_size(idx_t beg_bit, idx_t end_bit) const;

  inline size_t obj_size(HeapWord* beg_addr, HeapWord* end_addr) const;

  // Return the size in words of the object (a search is done for the end bit).

  inline size_t obj_size(idx_t beg_bit)  const;

  inline size_t obj_size(HeapWord* addr) const;

  inline size_t obj_size(oop obj)        const;

  // Synonyms for the above.

  size_t obj_size_in_words(oop obj) const { return obj_size((HeapWord*)obj); }

  size_t obj_size_in_words(HeapWord* addr) const { return obj_size(addr); }

  // Apply live_closure to each live object that lies completely within the

  // range [live_range_beg, live_range_end).  This is used to iterate over the

  // compacted region of the heap.  Return values:

  //

  // incomplete         The iteration is not complete.  The last object that

  //                    begins in the range does not end in the range;

  //                    closure->source() is set to the start of that object.

  //

  // complete           The iteration is complete.  All objects in the range

  //                    were processed and the closure is not full;

  //                    closure->source() is set one past the end of the range.

  //

  // full               The closure is full; closure->source() is set to one

  //                    past the end of the last object processed.

  //

  // would_overflow     The next object in the range would overflow the closure;

  //                    closure->source() is set to the start of that object.

  IterationStatus iterate(ParMarkBitMapClosure* live_closure,

                          idx_t range_beg, idx_t range_end) const;

  inline IterationStatus iterate(ParMarkBitMapClosure* live_closure,

                                 HeapWord* range_beg,

                                 HeapWord* range_end) const;

  // Apply live closure as above and additionally apply dead_closure to all dead

  // space in the range [range_beg, dead_range_end).  Note that dead_range_end

  // must be >= range_end.  This is used to iterate over the dense prefix.

  //

  // This method assumes that if the first bit in the range (range_beg) is not

  // marked, then dead space begins at that point and the dead_closure is

  // applied.  Thus callers must ensure that range_beg is not in the middle of a

  // live object.

  IterationStatus iterate(ParMarkBitMapClosure* live_closure,

                          ParMarkBitMapClosure* dead_closure,

                          idx_t range_beg, idx_t range_end,

                          idx_t dead_range_end) const;

  inline IterationStatus iterate(ParMarkBitMapClosure* live_closure,

                                 ParMarkBitMapClosure* dead_closure,

                                 HeapWord* range_beg,

                                 HeapWord* range_end,

                                 HeapWord* dead_range_end) const;

  // Return the number of live words in the range [beg_addr, end_addr) due to

  // objects that start in the range.  If a live object extends onto the range,

  // the caller must detect and account for any live words due to that object.

  // If a live object extends beyond the end of the range, only the words within

  // the range are included in the result.

  size_t live_words_in_range(HeapWord* beg_addr, HeapWord* end_addr) const;

  // Same as the above, except the end of the range must be a live object, which

  // is the case when updating pointers.  This allows a branch to be removed

  // from inside the loop.

  size_t live_words_in_range(HeapWord* beg_addr, oop end_obj) const;

  inline HeapWord* region_start() const;

  inline HeapWord* region_end() const;

  inline size_t    region_size() const;

  inline size_t    size() const;

  // Convert a heap address to/from a bit index.

  inline idx_t     addr_to_bit(HeapWord* addr) const;

  inline HeapWord* bit_to_addr(idx_t bit) const;

  // Return the bit index of the first marked object that begins (or ends,

  // respectively) in the range [beg, end).  If no object is found, return end.

  inline idx_t find_obj_beg(idx_t beg, idx_t end) const;

  inline idx_t find_obj_end(idx_t beg, idx_t end) const;

  inline HeapWord* find_obj_beg(HeapWord* beg, HeapWord* end) const;

  inline HeapWord* find_obj_end(HeapWord* beg, HeapWord* end) const;

  // Clear a range of bits or the entire bitmap (both begin and end bits are

  // cleared).

  inline void clear_range(idx_t beg, idx_t end);

  inline void clear() { clear_range(0, size()); }

  // Return the number of bits required to represent the specified number of

  // HeapWords, or the specified region.

  static inline idx_t bits_required(size_t words);

  static inline idx_t bits_required(MemRegion covered_region);

  static inline idx_t words_required(MemRegion covered_region);

#ifndef PRODUCT

  // CAS statistics.

  size_t cas_tries() { return _cas_tries; }

  size_t cas_retries() { return _cas_retries; }

  size_t cas_by_another() { return _cas_by_another; }

  void reset_counters();

#endif  // #ifndef PRODUCT

#ifdef  ASSERT

  void verify_clear() const;

  inline void verify_bit(idx_t bit) const;

  inline void verify_addr(HeapWord* addr) const;

#endif  // #ifdef ASSERT

private:

  // Each bit in the bitmap represents one unit of 'object granularity.' Objects

  // are double-word aligned in 32-bit VMs, but not in 64-bit VMs, so the 32-bit

  // granularity is 2, 64-bit is 1.

  static inline size_t obj_granularity() { return size_t(MinObjAlignment); }

  static inline int obj_granularity_shift() { return LogMinObjAlignment; }

  HeapWord*       _region_start;

  size_t          _region_size;

  BitMap          _beg_bits;

  BitMap          _end_bits;

  PSVirtualSpace* _virtual_space;

#ifndef PRODUCT

  size_t _cas_tries;

  size_t _cas_retries;

  size_t _cas_by_another;

#endif  // #ifndef PRODUCT

};

inline ParMarkBitMap::ParMarkBitMap():

  _beg_bits(),

  _end_bits()

{

  _region_start = 0;

  _virtual_space = 0;

}

inline ParMarkBitMap::ParMarkBitMap(MemRegion covered_region):

  _beg_bits(),

  _end_bits()

{

  initialize(covered_region);

}

inline void ParMarkBitMap::clear_range(idx_t beg, idx_t end)

{

  _beg_bits.clear_range(beg, end);

  _end_bits.clear_range(beg, end);

}

inline ParMarkBitMap::idx_t

ParMarkBitMap::bits_required(size_t words)

{

  // Need two bits (one begin bit, one end bit) for each unit of 'object

  // granularity' in the heap.

  return words_to_bits(words * 2);

}

inline ParMarkBitMap::idx_t

ParMarkBitMap::bits_required(MemRegion covered_region)

{

  return bits_required(covered_region.word_size());

}

inline ParMarkBitMap::idx_t

ParMarkBitMap::words_required(MemRegion covered_region)

{

  return bits_required(covered_region) / BitsPerWord;

}

inline HeapWord*

ParMarkBitMap::region_start() const

{

  return _region_start;

}

inline HeapWord*

ParMarkBitMap::region_end() const

{

  return region_start() + region_size();

}

inline size_t

ParMarkBitMap::region_size() const

{

  return _region_size;

}

inline size_t

ParMarkBitMap::size() const

{

  return _beg_bits.size();

}

inline bool ParMarkBitMap::is_obj_beg(idx_t bit) const

{

  return _beg_bits.at(bit);

}

inline bool ParMarkBitMap::is_obj_end(idx_t bit) const

{

  return _end_bits.at(bit);

}

inline bool ParMarkBitMap::is_marked(idx_t bit) const

{

  return is_obj_beg(bit);

}

inline bool ParMarkBitMap::is_marked(HeapWord* addr) const

{

  return is_marked(addr_to_bit(addr));

}

inline bool ParMarkBitMap::is_marked(oop obj) const

{

  return is_marked((HeapWord*)obj);

}

inline bool ParMarkBitMap::is_unmarked(idx_t bit) const

{

  return !is_marked(bit);

}

inline bool ParMarkBitMap::is_unmarked(HeapWord* addr) const

{

  return !is_marked(addr);

}

inline bool ParMarkBitMap::is_unmarked(oop obj) const

{

  return !is_marked(obj);

}

inline size_t

ParMarkBitMap::bits_to_words(idx_t bits)

{

  return bits << obj_granularity_shift();

}

inline ParMarkBitMap::idx_t

ParMarkBitMap::words_to_bits(size_t words)

{

  return words >> obj_granularity_shift();

}

inline size_t ParMarkBitMap::obj_size(idx_t beg_bit, idx_t end_bit) const

{

  DEBUG_ONLY(verify_bit(beg_bit);)

  DEBUG_ONLY(verify_bit(end_bit);)

  return bits_to_words(end_bit - beg_bit + 1);

}

inline size_t

ParMarkBitMap::obj_size(HeapWord* beg_addr, HeapWord* end_addr) const

{

  DEBUG_ONLY(verify_addr(beg_addr);)

  DEBUG_ONLY(verify_addr(end_addr);)

  return pointer_delta(end_addr, beg_addr) + obj_granularity();

}

inline size_t ParMarkBitMap::obj_size(idx_t beg_bit) const

{

  const idx_t end_bit = _end_bits.get_next_one_offset_inline(beg_bit, size());

  assert(is_marked(beg_bit), "obj not marked");

  assert(end_bit < size(), "end bit missing");

  return obj_size(beg_bit, end_bit);

}

inline size_t ParMarkBitMap::obj_size(HeapWord* addr) const

{

  return obj_size(addr_to_bit(addr));

}

inline size_t ParMarkBitMap::obj_size(oop obj) const

{

  return obj_size((HeapWord*)obj);

}

inline ParMarkBitMap::IterationStatus

ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure,

                       HeapWord* range_beg,

                       HeapWord* range_end) const

{

  return iterate(live_closure, addr_to_bit(range_beg), addr_to_bit(range_end));

}

inline ParMarkBitMap::IterationStatus

ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure,

                       ParMarkBitMapClosure* dead_closure,

                       HeapWord* range_beg,

                       HeapWord* range_end,

                       HeapWord* dead_range_end) const

{

  return iterate(live_closure, dead_closure,

                 addr_to_bit(range_beg), addr_to_bit(range_end),

                 addr_to_bit(dead_range_end));

}

inline bool

ParMarkBitMap::mark_obj(oop obj, int size)

{

  return mark_obj((HeapWord*)obj, (size_t)size);

}

inline BitMap::idx_t

ParMarkBitMap::addr_to_bit(HeapWord* addr) const

{

  DEBUG_ONLY(verify_addr(addr);)

  return words_to_bits(pointer_delta(addr, region_start()));

}

inline HeapWord*

ParMarkBitMap::bit_to_addr(idx_t bit) const

{

  DEBUG_ONLY(verify_bit(bit);)

  return region_start() + bits_to_words(bit);

}

inline ParMarkBitMap::idx_t

ParMarkBitMap::find_obj_beg(idx_t beg, idx_t end) const

{

  return _beg_bits.get_next_one_offset_inline_aligned_right(beg, end);

}

inline ParMarkBitMap::idx_t

ParMarkBitMap::find_obj_end(idx_t beg, idx_t end) const

{

  return _end_bits.get_next_one_offset_inline_aligned_right(beg, end);

}

inline HeapWord*

ParMarkBitMap::find_obj_beg(HeapWord* beg, HeapWord* end) const

{

  const idx_t beg_bit = addr_to_bit(beg);

  const idx_t end_bit = addr_to_bit(end);

  const idx_t search_end = BitMap::word_align_up(end_bit);

  const idx_t res_bit = MIN2(find_obj_beg(beg_bit, search_end), end_bit);

  return bit_to_addr(res_bit);

}

inline HeapWord*

ParMarkBitMap::find_obj_end(HeapWord* beg, HeapWord* end) const

{

  const idx_t beg_bit = addr_to_bit(beg);

  const idx_t end_bit = addr_to_bit(end);

  const idx_t search_end = BitMap::word_align_up(end_bit);

  const idx_t res_bit = MIN2(find_obj_end(beg_bit, search_end), end_bit);

  return bit_to_addr(res_bit);

}

#ifdef  ASSERT

inline void ParMarkBitMap::verify_bit(idx_t bit) const {

  // Allow one past the last valid bit; useful for loop bounds.

  assert(bit <= _beg_bits.size(), "bit out of range");

}

inline void ParMarkBitMap::verify_addr(HeapWord* addr) const {

  // Allow one past the last valid address; useful for loop bounds.

  assert(addr >= region_start(), "addr too small");

  assert(addr <= region_start() + region_size(), "addr too big");

}

#endif  // #ifdef ASSERT