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