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
32class ParMarkBitMapClosure;
33class PSVirtualSpace;
34class ParCompactionManager;
35
36class ParMarkBitMap: public CHeapObj<mtGC>
37{
38public:
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
170private:
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
192