1 /*
2 * Copyright (c) 2005, 2014, 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, p2i(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, p2i(addr), p2i(region_start())));
394 assert(addr <= region_end(),
395 err_msg("addr too big, addr: " PTR_FORMAT " region end: " PTR_FORMAT, p2i(addr), p2i(region_end())));
396 }
397 #endif // #ifdef ASSERT
398
399 #endif // SHARE_VM_GC_IMPLEMENTATION_PARALLELSCAVENGE_PARMARKBITMAP_HPP