1 /*
2 * Copyright (c) 2005, 2012, 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 "gc_implementation/parallelScavenge/psVirtualspace.hpp"
30 #include "utilities/bitMap.inline.hpp"
31
32 class oopDesc;
33 class ParMarkBitMapClosure;
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 inline ParMarkBitMap(MemRegion covered_region);
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 inline bool mark_obj(oop obj);
51
52 // Return whether the specified begin or end bit is set.
53 inline bool is_obj_beg(idx_t bit) const;
54 inline bool is_obj_end(idx_t bit) const;
55
56 // Traditional interface for testing whether an object is marked or not (these
57 // test only the begin bits).
58 inline bool is_marked(idx_t bit) const;
59 inline bool is_marked(HeapWord* addr) const;
60 inline bool is_marked(oop obj) const;
61
62 inline bool is_unmarked(idx_t bit) const;
63 inline bool is_unmarked(HeapWord* addr) const;
64 inline bool is_unmarked(oop obj) const;
65
66 // Convert sizes from bits to HeapWords and back. An object that is n bits
67 // long will be bits_to_words(n) words long. An object that is m words long
68 // will take up words_to_bits(m) bits in the bitmap.
69 inline static size_t bits_to_words(idx_t bits);
70 inline static idx_t words_to_bits(size_t words);
71
72 // Return the size in words of an object given a begin bit and an end bit, or
73 // the equivalent beg_addr and end_addr.
74 inline size_t obj_size(idx_t beg_bit, idx_t end_bit) const;
75 inline size_t obj_size(HeapWord* beg_addr, HeapWord* end_addr) const;
76
77 // Return the size in words of the object (a search is done for the end bit).
78 inline size_t obj_size(idx_t beg_bit) const;
79 inline size_t obj_size(HeapWord* addr) const;
80 inline size_t obj_size(oop obj) const;
81
82 // Synonyms for the above.
83 size_t obj_size_in_words(oop obj) const { return obj_size((HeapWord*)obj); }
84 size_t obj_size_in_words(HeapWord* addr) const { return obj_size(addr); }
85
86 // Apply live_closure to each live object that lies completely within the
87 // range [live_range_beg, live_range_end). This is used to iterate over the
88 // compacted region of the heap. Return values:
89 //
90 // incomplete The iteration is not complete. The last object that
91 // begins in the range does not end in the range;
92 // closure->source() is set to the start of that object.
93 //
94 // complete The iteration is complete. All objects in the range
95 // were processed and the closure is not full;
96 // closure->source() is set one past the end of the range.
97 //
98 // full The closure is full; closure->source() is set to one
99 // past the end of the last object processed.
100 //
101 // would_overflow The next object in the range would overflow the closure;
102 // closure->source() is set to the start of that object.
103 IterationStatus iterate(ParMarkBitMapClosure* live_closure,
104 idx_t range_beg, idx_t range_end) const;
105 inline IterationStatus iterate(ParMarkBitMapClosure* live_closure,
106 HeapWord* range_beg,
107 HeapWord* range_end) const;
108
109 // Apply live closure as above and additionally apply dead_closure to all dead
110 // space in the range [range_beg, dead_range_end). Note that dead_range_end
111 // must be >= range_end. This is used to iterate over the dense prefix.
112 //
113 // This method assumes that if the first bit in the range (range_beg) is not
114 // marked, then dead space begins at that point and the dead_closure is
115 // applied. Thus callers must ensure that range_beg is not in the middle of a
116 // live object.
117 IterationStatus iterate(ParMarkBitMapClosure* live_closure,
118 ParMarkBitMapClosure* dead_closure,
119 idx_t range_beg, idx_t range_end,
120 idx_t dead_range_end) const;
121 inline IterationStatus iterate(ParMarkBitMapClosure* live_closure,
122 ParMarkBitMapClosure* dead_closure,
123 HeapWord* range_beg,
124 HeapWord* range_end,
125 HeapWord* dead_range_end) const;
126
127 // Return the number of live words in the range [beg_addr, end_addr) due to
128 // objects that start in the range. If a live object extends onto the range,
129 // the caller must detect and account for any live words due to that object.
130 // If a live object extends beyond the end of the range, only the words within
131 // the range are included in the result.
132 size_t live_words_in_range(HeapWord* beg_addr, HeapWord* end_addr) const;
133
134 // Same as the above, except the end of the range must be a live object, which
135 // is the case when updating pointers. This allows a branch to be removed
136 // from inside the loop.
137 size_t live_words_in_range(HeapWord* beg_addr, oop end_obj) const;
138
139 inline HeapWord* region_start() const;
140 inline HeapWord* region_end() const;
141 inline size_t region_size() const;
142 inline size_t size() const;
143
144 // Convert a heap address to/from a bit index.
145 inline idx_t addr_to_bit(HeapWord* addr) const;
146 inline HeapWord* bit_to_addr(idx_t bit) const;
147
148 // Return the bit index of the first marked object that begins (or ends,
149 // respectively) in the range [beg, end). If no object is found, return end.
150 inline idx_t find_obj_beg(idx_t beg, idx_t end) const;
151 inline idx_t find_obj_end(idx_t beg, idx_t end) const;
152
153 inline HeapWord* find_obj_beg(HeapWord* beg, HeapWord* end) const;
154 inline HeapWord* find_obj_end(HeapWord* beg, HeapWord* end) const;
155
156 // Clear a range of bits or the entire bitmap (both begin and end bits are
157 // cleared).
158 inline void clear_range(idx_t beg, idx_t end);
159 inline void clear() { clear_range(0, size()); }
160
161 // Return the number of bits required to represent the specified number of
162 // HeapWords, or the specified region.
163 static inline idx_t bits_required(size_t words);
164 static inline idx_t bits_required(MemRegion covered_region);
165 static inline idx_t words_required(MemRegion covered_region);
166
167 #ifndef PRODUCT
168 // CAS statistics.
169 size_t cas_tries() { return _cas_tries; }
170 size_t cas_retries() { return _cas_retries; }
171 size_t cas_by_another() { return _cas_by_another; }
172
173 void reset_counters();
174 #endif // #ifndef PRODUCT
175
176 void print_on_error(outputStream* st) const {
177 st->print_cr("Marking Bits: (ParMarkBitMap*) " PTR_FORMAT, this);
178 _beg_bits.print_on_error(st, " Begin Bits: ");
179 _end_bits.print_on_error(st, " End Bits: ");
180 }
181
182 #ifdef ASSERT
183 void verify_clear() const;
184 inline void verify_bit(idx_t bit) const;
185 inline void verify_addr(HeapWord* addr) const;
186 #endif // #ifdef ASSERT
187
188 private:
189 // Each bit in the bitmap represents one unit of 'object granularity.' Objects
190 // are double-word aligned in 32-bit VMs, but not in 64-bit VMs, so the 32-bit
191 // granularity is 2, 64-bit is 1.
192 static inline size_t obj_granularity() { return size_t(MinObjAlignment); }
193 static inline int obj_granularity_shift() { return LogMinObjAlignment; }
194
195 HeapWord* _region_start;
196 size_t _region_size;
197 BitMap _beg_bits;
198 BitMap _end_bits;
199 PSVirtualSpace* _virtual_space;
200
201 #ifndef PRODUCT
202 size_t _cas_tries;
203 size_t _cas_retries;
204 size_t _cas_by_another;
205 #endif // #ifndef PRODUCT
206 };
207
208 inline ParMarkBitMap::ParMarkBitMap():
209 _beg_bits(),
210 _end_bits()
211 {
212 _region_start = 0;
213 _virtual_space = 0;
214 }
215
216 inline ParMarkBitMap::ParMarkBitMap(MemRegion covered_region):
217 _beg_bits(),
218 _end_bits()
219 {
220 initialize(covered_region);
221 }
222
223 inline void ParMarkBitMap::clear_range(idx_t beg, idx_t end)
224 {
225 _beg_bits.clear_range(beg, end);
226 _end_bits.clear_range(beg, end);
227 }
228
229 inline ParMarkBitMap::idx_t
230 ParMarkBitMap::bits_required(size_t words)
231 {
232 // Need two bits (one begin bit, one end bit) for each unit of 'object
233 // granularity' in the heap.
234 return words_to_bits(words * 2);
235 }
236
237 inline ParMarkBitMap::idx_t
238 ParMarkBitMap::bits_required(MemRegion covered_region)
239 {
240 return bits_required(covered_region.word_size());
241 }
242
243 inline ParMarkBitMap::idx_t
244 ParMarkBitMap::words_required(MemRegion covered_region)
245 {
246 return bits_required(covered_region) / BitsPerWord;
247 }
248
249 inline HeapWord*
250 ParMarkBitMap::region_start() const
251 {
252 return _region_start;
253 }
254
255 inline HeapWord*
256 ParMarkBitMap::region_end() const
257 {
258 return region_start() + region_size();
259 }
260
261 inline size_t
262 ParMarkBitMap::region_size() const
263 {
264 return _region_size;
265 }
266
267 inline size_t
268 ParMarkBitMap::size() const
269 {
270 return _beg_bits.size();
271 }
272
273 inline bool ParMarkBitMap::is_obj_beg(idx_t bit) const
274 {
275 return _beg_bits.at(bit);
276 }
277
278 inline bool ParMarkBitMap::is_obj_end(idx_t bit) const
279 {
280 return _end_bits.at(bit);
281 }
282
283 inline bool ParMarkBitMap::is_marked(idx_t bit) const
284 {
285 return is_obj_beg(bit);
286 }
287
288 inline bool ParMarkBitMap::is_marked(HeapWord* addr) const
289 {
290 return is_marked(addr_to_bit(addr));
291 }
292
293 inline bool ParMarkBitMap::is_marked(oop obj) const
294 {
295 return is_marked((HeapWord*)obj);
296 }
297
298 inline bool ParMarkBitMap::is_unmarked(idx_t bit) const
299 {
300 return !is_marked(bit);
301 }
302
303 inline bool ParMarkBitMap::is_unmarked(HeapWord* addr) const
304 {
305 return !is_marked(addr);
306 }
307
308 inline bool ParMarkBitMap::is_unmarked(oop obj) const
309 {
310 return !is_marked(obj);
311 }
312
313 inline size_t
314 ParMarkBitMap::bits_to_words(idx_t bits)
315 {
316 return bits << obj_granularity_shift();
317 }
318
319 inline ParMarkBitMap::idx_t
320 ParMarkBitMap::words_to_bits(size_t words)
321 {
322 return words >> obj_granularity_shift();
323 }
324
325 inline size_t ParMarkBitMap::obj_size(idx_t beg_bit, idx_t end_bit) const
326 {
327 DEBUG_ONLY(verify_bit(beg_bit);)
328 DEBUG_ONLY(verify_bit(end_bit);)
329 return bits_to_words(end_bit - beg_bit + 1);
330 }
331
332 inline size_t
333 ParMarkBitMap::obj_size(HeapWord* beg_addr, HeapWord* end_addr) const
334 {
335 DEBUG_ONLY(verify_addr(beg_addr);)
336 DEBUG_ONLY(verify_addr(end_addr);)
337 return pointer_delta(end_addr, beg_addr) + obj_granularity();
338 }
339
340 inline size_t ParMarkBitMap::obj_size(idx_t beg_bit) const
341 {
342 const idx_t end_bit = _end_bits.get_next_one_offset_inline(beg_bit, size());
343 assert(is_marked(beg_bit), "obj not marked");
344 assert(end_bit < size(), "end bit missing");
345 return obj_size(beg_bit, end_bit);
346 }
347
348 inline size_t ParMarkBitMap::obj_size(HeapWord* addr) const
349 {
350 return obj_size(addr_to_bit(addr));
351 }
352
353 inline size_t ParMarkBitMap::obj_size(oop obj) const
354 {
355 return obj_size((HeapWord*)obj);
356 }
357
358 inline ParMarkBitMap::IterationStatus
359 ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure,
360 HeapWord* range_beg,
361 HeapWord* range_end) const
362 {
363 return iterate(live_closure, addr_to_bit(range_beg), addr_to_bit(range_end));
364 }
365
366 inline ParMarkBitMap::IterationStatus
367 ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure,
368 ParMarkBitMapClosure* dead_closure,
369 HeapWord* range_beg,
370 HeapWord* range_end,
371 HeapWord* dead_range_end) const
372 {
373 return iterate(live_closure, dead_closure,
374 addr_to_bit(range_beg), addr_to_bit(range_end),
375 addr_to_bit(dead_range_end));
376 }
377
378 inline bool
379 ParMarkBitMap::mark_obj(oop obj, int size)
380 {
381 return mark_obj((HeapWord*)obj, (size_t)size);
382 }
383
384 inline BitMap::idx_t
385 ParMarkBitMap::addr_to_bit(HeapWord* addr) const
386 {
387 DEBUG_ONLY(verify_addr(addr);)
388 return words_to_bits(pointer_delta(addr, region_start()));
389 }
390
391 inline HeapWord*
392 ParMarkBitMap::bit_to_addr(idx_t bit) const
393 {
394 DEBUG_ONLY(verify_bit(bit);)
395 return region_start() + bits_to_words(bit);
396 }
397
398 inline ParMarkBitMap::idx_t
399 ParMarkBitMap::find_obj_beg(idx_t beg, idx_t end) const
400 {
401 return _beg_bits.get_next_one_offset_inline_aligned_right(beg, end);
402 }
403
404 inline ParMarkBitMap::idx_t
405 ParMarkBitMap::find_obj_end(idx_t beg, idx_t end) const
406 {
407 return _end_bits.get_next_one_offset_inline_aligned_right(beg, end);
408 }
409
410 inline HeapWord*
411 ParMarkBitMap::find_obj_beg(HeapWord* beg, HeapWord* end) const
412 {
413 const idx_t beg_bit = addr_to_bit(beg);
414 const idx_t end_bit = addr_to_bit(end);
415 const idx_t search_end = BitMap::word_align_up(end_bit);
416 const idx_t res_bit = MIN2(find_obj_beg(beg_bit, search_end), end_bit);
417 return bit_to_addr(res_bit);
418 }
419
420 inline HeapWord*
421 ParMarkBitMap::find_obj_end(HeapWord* beg, HeapWord* end) const
422 {
423 const idx_t beg_bit = addr_to_bit(beg);
424 const idx_t end_bit = addr_to_bit(end);
425 const idx_t search_end = BitMap::word_align_up(end_bit);
426 const idx_t res_bit = MIN2(find_obj_end(beg_bit, search_end), end_bit);
427 return bit_to_addr(res_bit);
428 }
429
430 #ifdef ASSERT
431 inline void ParMarkBitMap::verify_bit(idx_t bit) const {
432 // Allow one past the last valid bit; useful for loop bounds.
433 assert(bit <= _beg_bits.size(), "bit out of range");
434 }
435
436 inline void ParMarkBitMap::verify_addr(HeapWord* addr) const {
437 // Allow one past the last valid address; useful for loop bounds.
438 assert(addr >= region_start(), "addr too small");
439 assert(addr <= region_start() + region_size(), "addr too big");
440 }
441 #endif // #ifdef ASSERT
442
443 #endif // SHARE_VM_GC_IMPLEMENTATION_PARALLELSCAVENGE_PARMARKBITMAP_HPP