Thu, 22 Sep 2011 10:57:37 -0700
6484982: G1: process references during evacuation pauses
Summary: G1 now uses two reference processors - one is used by concurrent marking and the other is used by STW GCs (both full and incremental evacuation pauses). In an evacuation pause, the reference processor is embedded into the closures used to scan objects. Doing so causes causes reference objects to be 'discovered' by the reference processor. At the end of the evacuation pause, these discovered reference objects are processed - preserving (and copying) referent objects (and their reachable graphs) as appropriate.
Reviewed-by: ysr, jwilhelm, brutisso, stefank, tonyp
1 /*
2 * Copyright (c) 2005, 2010, 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 */
25 #ifndef SHARE_VM_GC_IMPLEMENTATION_PARALLELSCAVENGE_PARMARKBITMAP_HPP
26 #define SHARE_VM_GC_IMPLEMENTATION_PARALLELSCAVENGE_PARMARKBITMAP_HPP
28 #include "memory/memRegion.hpp"
29 #include "gc_implementation/parallelScavenge/psVirtualspace.hpp"
30 #include "utilities/bitMap.inline.hpp"
32 class oopDesc;
33 class ParMarkBitMapClosure;
35 class ParMarkBitMap: public CHeapObj
36 {
37 public:
38 typedef BitMap::idx_t idx_t;
40 // Values returned by the iterate() methods.
41 enum IterationStatus { incomplete, complete, full, would_overflow };
43 inline ParMarkBitMap();
44 inline ParMarkBitMap(MemRegion covered_region);
45 bool initialize(MemRegion covered_region);
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);
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;
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;
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;
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);
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;
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;
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); }
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;
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;
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;
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;
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;
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;
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;
153 inline HeapWord* find_obj_beg(HeapWord* beg, HeapWord* end) const;
154 inline HeapWord* find_obj_end(HeapWord* beg, HeapWord* end) const;
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()); }
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);
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; }
173 void reset_counters();
174 #endif // #ifndef PRODUCT
176 #ifdef ASSERT
177 void verify_clear() const;
178 inline void verify_bit(idx_t bit) const;
179 inline void verify_addr(HeapWord* addr) const;
180 #endif // #ifdef ASSERT
182 private:
183 // Each bit in the bitmap represents one unit of 'object granularity.' Objects
184 // are double-word aligned in 32-bit VMs, but not in 64-bit VMs, so the 32-bit
185 // granularity is 2, 64-bit is 1.
186 static inline size_t obj_granularity() { return size_t(MinObjAlignment); }
187 static inline int obj_granularity_shift() { return LogMinObjAlignment; }
189 HeapWord* _region_start;
190 size_t _region_size;
191 BitMap _beg_bits;
192 BitMap _end_bits;
193 PSVirtualSpace* _virtual_space;
195 #ifndef PRODUCT
196 size_t _cas_tries;
197 size_t _cas_retries;
198 size_t _cas_by_another;
199 #endif // #ifndef PRODUCT
200 };
202 inline ParMarkBitMap::ParMarkBitMap():
203 _beg_bits(),
204 _end_bits()
205 {
206 _region_start = 0;
207 _virtual_space = 0;
208 }
210 inline ParMarkBitMap::ParMarkBitMap(MemRegion covered_region):
211 _beg_bits(),
212 _end_bits()
213 {
214 initialize(covered_region);
215 }
217 inline void ParMarkBitMap::clear_range(idx_t beg, idx_t end)
218 {
219 _beg_bits.clear_range(beg, end);
220 _end_bits.clear_range(beg, end);
221 }
223 inline ParMarkBitMap::idx_t
224 ParMarkBitMap::bits_required(size_t words)
225 {
226 // Need two bits (one begin bit, one end bit) for each unit of 'object
227 // granularity' in the heap.
228 return words_to_bits(words * 2);
229 }
231 inline ParMarkBitMap::idx_t
232 ParMarkBitMap::bits_required(MemRegion covered_region)
233 {
234 return bits_required(covered_region.word_size());
235 }
237 inline ParMarkBitMap::idx_t
238 ParMarkBitMap::words_required(MemRegion covered_region)
239 {
240 return bits_required(covered_region) / BitsPerWord;
241 }
243 inline HeapWord*
244 ParMarkBitMap::region_start() const
245 {
246 return _region_start;
247 }
249 inline HeapWord*
250 ParMarkBitMap::region_end() const
251 {
252 return region_start() + region_size();
253 }
255 inline size_t
256 ParMarkBitMap::region_size() const
257 {
258 return _region_size;
259 }
261 inline size_t
262 ParMarkBitMap::size() const
263 {
264 return _beg_bits.size();
265 }
267 inline bool ParMarkBitMap::is_obj_beg(idx_t bit) const
268 {
269 return _beg_bits.at(bit);
270 }
272 inline bool ParMarkBitMap::is_obj_end(idx_t bit) const
273 {
274 return _end_bits.at(bit);
275 }
277 inline bool ParMarkBitMap::is_marked(idx_t bit) const
278 {
279 return is_obj_beg(bit);
280 }
282 inline bool ParMarkBitMap::is_marked(HeapWord* addr) const
283 {
284 return is_marked(addr_to_bit(addr));
285 }
287 inline bool ParMarkBitMap::is_marked(oop obj) const
288 {
289 return is_marked((HeapWord*)obj);
290 }
292 inline bool ParMarkBitMap::is_unmarked(idx_t bit) const
293 {
294 return !is_marked(bit);
295 }
297 inline bool ParMarkBitMap::is_unmarked(HeapWord* addr) const
298 {
299 return !is_marked(addr);
300 }
302 inline bool ParMarkBitMap::is_unmarked(oop obj) const
303 {
304 return !is_marked(obj);
305 }
307 inline size_t
308 ParMarkBitMap::bits_to_words(idx_t bits)
309 {
310 return bits << obj_granularity_shift();
311 }
313 inline ParMarkBitMap::idx_t
314 ParMarkBitMap::words_to_bits(size_t words)
315 {
316 return words >> obj_granularity_shift();
317 }
319 inline size_t ParMarkBitMap::obj_size(idx_t beg_bit, idx_t end_bit) const
320 {
321 DEBUG_ONLY(verify_bit(beg_bit);)
322 DEBUG_ONLY(verify_bit(end_bit);)
323 return bits_to_words(end_bit - beg_bit + 1);
324 }
326 inline size_t
327 ParMarkBitMap::obj_size(HeapWord* beg_addr, HeapWord* end_addr) const
328 {
329 DEBUG_ONLY(verify_addr(beg_addr);)
330 DEBUG_ONLY(verify_addr(end_addr);)
331 return pointer_delta(end_addr, beg_addr) + obj_granularity();
332 }
334 inline size_t ParMarkBitMap::obj_size(idx_t beg_bit) const
335 {
336 const idx_t end_bit = _end_bits.get_next_one_offset_inline(beg_bit, size());
337 assert(is_marked(beg_bit), "obj not marked");
338 assert(end_bit < size(), "end bit missing");
339 return obj_size(beg_bit, end_bit);
340 }
342 inline size_t ParMarkBitMap::obj_size(HeapWord* addr) const
343 {
344 return obj_size(addr_to_bit(addr));
345 }
347 inline size_t ParMarkBitMap::obj_size(oop obj) const
348 {
349 return obj_size((HeapWord*)obj);
350 }
352 inline ParMarkBitMap::IterationStatus
353 ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure,
354 HeapWord* range_beg,
355 HeapWord* range_end) const
356 {
357 return iterate(live_closure, addr_to_bit(range_beg), addr_to_bit(range_end));
358 }
360 inline ParMarkBitMap::IterationStatus
361 ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure,
362 ParMarkBitMapClosure* dead_closure,
363 HeapWord* range_beg,
364 HeapWord* range_end,
365 HeapWord* dead_range_end) const
366 {
367 return iterate(live_closure, dead_closure,
368 addr_to_bit(range_beg), addr_to_bit(range_end),
369 addr_to_bit(dead_range_end));
370 }
372 inline bool
373 ParMarkBitMap::mark_obj(oop obj, int size)
374 {
375 return mark_obj((HeapWord*)obj, (size_t)size);
376 }
378 inline BitMap::idx_t
379 ParMarkBitMap::addr_to_bit(HeapWord* addr) const
380 {
381 DEBUG_ONLY(verify_addr(addr);)
382 return words_to_bits(pointer_delta(addr, region_start()));
383 }
385 inline HeapWord*
386 ParMarkBitMap::bit_to_addr(idx_t bit) const
387 {
388 DEBUG_ONLY(verify_bit(bit);)
389 return region_start() + bits_to_words(bit);
390 }
392 inline ParMarkBitMap::idx_t
393 ParMarkBitMap::find_obj_beg(idx_t beg, idx_t end) const
394 {
395 return _beg_bits.get_next_one_offset_inline_aligned_right(beg, end);
396 }
398 inline ParMarkBitMap::idx_t
399 ParMarkBitMap::find_obj_end(idx_t beg, idx_t end) const
400 {
401 return _end_bits.get_next_one_offset_inline_aligned_right(beg, end);
402 }
404 inline HeapWord*
405 ParMarkBitMap::find_obj_beg(HeapWord* beg, HeapWord* end) const
406 {
407 const idx_t beg_bit = addr_to_bit(beg);
408 const idx_t end_bit = addr_to_bit(end);
409 const idx_t search_end = BitMap::word_align_up(end_bit);
410 const idx_t res_bit = MIN2(find_obj_beg(beg_bit, search_end), end_bit);
411 return bit_to_addr(res_bit);
412 }
414 inline HeapWord*
415 ParMarkBitMap::find_obj_end(HeapWord* beg, HeapWord* end) const
416 {
417 const idx_t beg_bit = addr_to_bit(beg);
418 const idx_t end_bit = addr_to_bit(end);
419 const idx_t search_end = BitMap::word_align_up(end_bit);
420 const idx_t res_bit = MIN2(find_obj_end(beg_bit, search_end), end_bit);
421 return bit_to_addr(res_bit);
422 }
424 #ifdef ASSERT
425 inline void ParMarkBitMap::verify_bit(idx_t bit) const {
426 // Allow one past the last valid bit; useful for loop bounds.
427 assert(bit <= _beg_bits.size(), "bit out of range");
428 }
430 inline void ParMarkBitMap::verify_addr(HeapWord* addr) const {
431 // Allow one past the last valid address; useful for loop bounds.
432 assert(addr >= region_start(), "addr too small");
433 assert(addr <= region_start() + region_size(), "addr too big");
434 }
435 #endif // #ifdef ASSERT
437 #endif // SHARE_VM_GC_IMPLEMENTATION_PARALLELSCAVENGE_PARMARKBITMAP_HPP