|
1 /* |
|
2 * Copyright 2005-2006 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
|
20 * CA 95054 USA or visit www.sun.com if you need additional information or |
|
21 * have any questions. |
|
22 * |
|
23 */ |
|
24 |
|
25 class oopDesc; |
|
26 class ParMarkBitMapClosure; |
|
27 |
|
28 class ParMarkBitMap: public CHeapObj |
|
29 { |
|
30 public: |
|
31 typedef BitMap::idx_t idx_t; |
|
32 |
|
33 // Values returned by the iterate() methods. |
|
34 enum IterationStatus { incomplete, complete, full, would_overflow }; |
|
35 |
|
36 inline ParMarkBitMap(); |
|
37 inline ParMarkBitMap(MemRegion covered_region); |
|
38 bool initialize(MemRegion covered_region); |
|
39 |
|
40 // Atomically mark an object as live. |
|
41 bool mark_obj(HeapWord* addr, size_t size); |
|
42 inline bool mark_obj(oop obj, int size); |
|
43 inline bool mark_obj(oop obj); |
|
44 |
|
45 // Return whether the specified begin or end bit is set. |
|
46 inline bool is_obj_beg(idx_t bit) const; |
|
47 inline bool is_obj_end(idx_t bit) const; |
|
48 |
|
49 // Traditional interface for testing whether an object is marked or not (these |
|
50 // test only the begin bits). |
|
51 inline bool is_marked(idx_t bit) const; |
|
52 inline bool is_marked(HeapWord* addr) const; |
|
53 inline bool is_marked(oop obj) const; |
|
54 |
|
55 inline bool is_unmarked(idx_t bit) const; |
|
56 inline bool is_unmarked(HeapWord* addr) const; |
|
57 inline bool is_unmarked(oop obj) const; |
|
58 |
|
59 // Convert sizes from bits to HeapWords and back. An object that is n bits |
|
60 // long will be bits_to_words(n) words long. An object that is m words long |
|
61 // will take up words_to_bits(m) bits in the bitmap. |
|
62 inline static size_t bits_to_words(idx_t bits); |
|
63 inline static idx_t words_to_bits(size_t words); |
|
64 |
|
65 // Return the size in words of an object given a begin bit and an end bit, or |
|
66 // the equivalent beg_addr and end_addr. |
|
67 inline size_t obj_size(idx_t beg_bit, idx_t end_bit) const; |
|
68 inline size_t obj_size(HeapWord* beg_addr, HeapWord* end_addr) const; |
|
69 |
|
70 // Return the size in words of the object (a search is done for the end bit). |
|
71 inline size_t obj_size(idx_t beg_bit) const; |
|
72 inline size_t obj_size(HeapWord* addr) const; |
|
73 inline size_t obj_size(oop obj) const; |
|
74 |
|
75 // Synonyms for the above. |
|
76 size_t obj_size_in_words(oop obj) const { return obj_size((HeapWord*)obj); } |
|
77 size_t obj_size_in_words(HeapWord* addr) const { return obj_size(addr); } |
|
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_addr) 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. |
|
125 size_t live_words_in_range(HeapWord* beg_addr, HeapWord* end_addr) const; |
|
126 |
|
127 // Same as the above, except the end of the range must be a live object, which |
|
128 // is the case when updating pointers. This allows a branch to be removed |
|
129 // from inside the loop. |
|
130 size_t live_words_in_range(HeapWord* beg_addr, oop end_obj) const; |
|
131 |
|
132 inline HeapWord* region_start() const; |
|
133 inline HeapWord* region_end() const; |
|
134 inline size_t region_size() const; |
|
135 inline size_t size() const; |
|
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 inline void clear() { clear_range(0, size()); } |
|
153 |
|
154 // Return the number of bits required to represent the specified number of |
|
155 // HeapWords, or the specified region. |
|
156 static inline idx_t bits_required(size_t words); |
|
157 static inline idx_t bits_required(MemRegion covered_region); |
|
158 static inline idx_t words_required(MemRegion covered_region); |
|
159 |
|
160 #ifndef PRODUCT |
|
161 // CAS statistics. |
|
162 size_t cas_tries() { return _cas_tries; } |
|
163 size_t cas_retries() { return _cas_retries; } |
|
164 size_t cas_by_another() { return _cas_by_another; } |
|
165 |
|
166 void reset_counters(); |
|
167 #endif // #ifndef PRODUCT |
|
168 |
|
169 #ifdef ASSERT |
|
170 void verify_clear() const; |
|
171 inline void verify_bit(idx_t bit) const; |
|
172 inline void verify_addr(HeapWord* addr) const; |
|
173 #endif // #ifdef ASSERT |
|
174 |
|
175 private: |
|
176 // Each bit in the bitmap represents one unit of 'object granularity.' Objects |
|
177 // are double-word aligned in 32-bit VMs, but not in 64-bit VMs, so the 32-bit |
|
178 // granularity is 2, 64-bit is 1. |
|
179 static inline size_t obj_granularity() { return size_t(MinObjAlignment); } |
|
180 |
|
181 HeapWord* _region_start; |
|
182 size_t _region_size; |
|
183 BitMap _beg_bits; |
|
184 BitMap _end_bits; |
|
185 PSVirtualSpace* _virtual_space; |
|
186 |
|
187 #ifndef PRODUCT |
|
188 size_t _cas_tries; |
|
189 size_t _cas_retries; |
|
190 size_t _cas_by_another; |
|
191 #endif // #ifndef PRODUCT |
|
192 }; |
|
193 |
|
194 inline ParMarkBitMap::ParMarkBitMap(): |
|
195 _beg_bits(NULL, 0), |
|
196 _end_bits(NULL, 0) |
|
197 { |
|
198 _region_start = 0; |
|
199 _virtual_space = 0; |
|
200 } |
|
201 |
|
202 inline ParMarkBitMap::ParMarkBitMap(MemRegion covered_region): |
|
203 _beg_bits(NULL, 0), |
|
204 _end_bits(NULL, 0) |
|
205 { |
|
206 initialize(covered_region); |
|
207 } |
|
208 |
|
209 inline void ParMarkBitMap::clear_range(idx_t beg, idx_t end) |
|
210 { |
|
211 _beg_bits.clear_range(beg, end); |
|
212 _end_bits.clear_range(beg, end); |
|
213 } |
|
214 |
|
215 inline ParMarkBitMap::idx_t |
|
216 ParMarkBitMap::bits_required(size_t words) |
|
217 { |
|
218 // Need two bits (one begin bit, one end bit) for each unit of 'object |
|
219 // granularity' in the heap. |
|
220 return words_to_bits(words * 2); |
|
221 } |
|
222 |
|
223 inline ParMarkBitMap::idx_t |
|
224 ParMarkBitMap::bits_required(MemRegion covered_region) |
|
225 { |
|
226 return bits_required(covered_region.word_size()); |
|
227 } |
|
228 |
|
229 inline ParMarkBitMap::idx_t |
|
230 ParMarkBitMap::words_required(MemRegion covered_region) |
|
231 { |
|
232 return bits_required(covered_region) / BitsPerWord; |
|
233 } |
|
234 |
|
235 inline HeapWord* |
|
236 ParMarkBitMap::region_start() const |
|
237 { |
|
238 return _region_start; |
|
239 } |
|
240 |
|
241 inline HeapWord* |
|
242 ParMarkBitMap::region_end() const |
|
243 { |
|
244 return region_start() + region_size(); |
|
245 } |
|
246 |
|
247 inline size_t |
|
248 ParMarkBitMap::region_size() const |
|
249 { |
|
250 return _region_size; |
|
251 } |
|
252 |
|
253 inline size_t |
|
254 ParMarkBitMap::size() const |
|
255 { |
|
256 return _beg_bits.size(); |
|
257 } |
|
258 |
|
259 inline bool ParMarkBitMap::is_obj_beg(idx_t bit) const |
|
260 { |
|
261 return _beg_bits.at(bit); |
|
262 } |
|
263 |
|
264 inline bool ParMarkBitMap::is_obj_end(idx_t bit) const |
|
265 { |
|
266 return _end_bits.at(bit); |
|
267 } |
|
268 |
|
269 inline bool ParMarkBitMap::is_marked(idx_t bit) const |
|
270 { |
|
271 return is_obj_beg(bit); |
|
272 } |
|
273 |
|
274 inline bool ParMarkBitMap::is_marked(HeapWord* addr) const |
|
275 { |
|
276 return is_marked(addr_to_bit(addr)); |
|
277 } |
|
278 |
|
279 inline bool ParMarkBitMap::is_marked(oop obj) const |
|
280 { |
|
281 return is_marked((HeapWord*)obj); |
|
282 } |
|
283 |
|
284 inline bool ParMarkBitMap::is_unmarked(idx_t bit) const |
|
285 { |
|
286 return !is_marked(bit); |
|
287 } |
|
288 |
|
289 inline bool ParMarkBitMap::is_unmarked(HeapWord* addr) const |
|
290 { |
|
291 return !is_marked(addr); |
|
292 } |
|
293 |
|
294 inline bool ParMarkBitMap::is_unmarked(oop obj) const |
|
295 { |
|
296 return !is_marked(obj); |
|
297 } |
|
298 |
|
299 inline size_t |
|
300 ParMarkBitMap::bits_to_words(idx_t bits) |
|
301 { |
|
302 return bits * obj_granularity(); |
|
303 } |
|
304 |
|
305 inline ParMarkBitMap::idx_t |
|
306 ParMarkBitMap::words_to_bits(size_t words) |
|
307 { |
|
308 return words / obj_granularity(); |
|
309 } |
|
310 |
|
311 inline size_t ParMarkBitMap::obj_size(idx_t beg_bit, idx_t end_bit) const |
|
312 { |
|
313 DEBUG_ONLY(verify_bit(beg_bit);) |
|
314 DEBUG_ONLY(verify_bit(end_bit);) |
|
315 return bits_to_words(end_bit - beg_bit + 1); |
|
316 } |
|
317 |
|
318 inline size_t |
|
319 ParMarkBitMap::obj_size(HeapWord* beg_addr, HeapWord* end_addr) const |
|
320 { |
|
321 DEBUG_ONLY(verify_addr(beg_addr);) |
|
322 DEBUG_ONLY(verify_addr(end_addr);) |
|
323 return pointer_delta(end_addr, beg_addr) + obj_granularity(); |
|
324 } |
|
325 |
|
326 inline size_t ParMarkBitMap::obj_size(idx_t beg_bit) const |
|
327 { |
|
328 const idx_t end_bit = _end_bits.find_next_one_bit(beg_bit, size()); |
|
329 assert(is_marked(beg_bit), "obj not marked"); |
|
330 assert(end_bit < size(), "end bit missing"); |
|
331 return obj_size(beg_bit, end_bit); |
|
332 } |
|
333 |
|
334 inline size_t ParMarkBitMap::obj_size(HeapWord* addr) const |
|
335 { |
|
336 return obj_size(addr_to_bit(addr)); |
|
337 } |
|
338 |
|
339 inline size_t ParMarkBitMap::obj_size(oop obj) const |
|
340 { |
|
341 return obj_size((HeapWord*)obj); |
|
342 } |
|
343 |
|
344 inline ParMarkBitMap::IterationStatus |
|
345 ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure, |
|
346 HeapWord* range_beg, |
|
347 HeapWord* range_end) const |
|
348 { |
|
349 return iterate(live_closure, addr_to_bit(range_beg), addr_to_bit(range_end)); |
|
350 } |
|
351 |
|
352 inline ParMarkBitMap::IterationStatus |
|
353 ParMarkBitMap::iterate(ParMarkBitMapClosure* live_closure, |
|
354 ParMarkBitMapClosure* dead_closure, |
|
355 HeapWord* range_beg, |
|
356 HeapWord* range_end, |
|
357 HeapWord* dead_range_end) const |
|
358 { |
|
359 return iterate(live_closure, dead_closure, |
|
360 addr_to_bit(range_beg), addr_to_bit(range_end), |
|
361 addr_to_bit(dead_range_end)); |
|
362 } |
|
363 |
|
364 inline bool |
|
365 ParMarkBitMap::mark_obj(oop obj, int size) |
|
366 { |
|
367 return mark_obj((HeapWord*)obj, (size_t)size); |
|
368 } |
|
369 |
|
370 inline BitMap::idx_t |
|
371 ParMarkBitMap::addr_to_bit(HeapWord* addr) const |
|
372 { |
|
373 DEBUG_ONLY(verify_addr(addr);) |
|
374 return words_to_bits(pointer_delta(addr, region_start())); |
|
375 } |
|
376 |
|
377 inline HeapWord* |
|
378 ParMarkBitMap::bit_to_addr(idx_t bit) const |
|
379 { |
|
380 DEBUG_ONLY(verify_bit(bit);) |
|
381 return region_start() + bits_to_words(bit); |
|
382 } |
|
383 |
|
384 inline ParMarkBitMap::idx_t |
|
385 ParMarkBitMap::find_obj_beg(idx_t beg, idx_t end) const |
|
386 { |
|
387 return _beg_bits.find_next_one_bit(beg, end); |
|
388 } |
|
389 |
|
390 inline ParMarkBitMap::idx_t |
|
391 ParMarkBitMap::find_obj_end(idx_t beg, idx_t end) const |
|
392 { |
|
393 return _end_bits.find_next_one_bit(beg, end); |
|
394 } |
|
395 |
|
396 inline HeapWord* |
|
397 ParMarkBitMap::find_obj_beg(HeapWord* beg, HeapWord* end) const |
|
398 { |
|
399 const idx_t beg_bit = addr_to_bit(beg); |
|
400 const idx_t end_bit = addr_to_bit(end); |
|
401 const idx_t search_end = BitMap::word_align_up(end_bit); |
|
402 const idx_t res_bit = MIN2(find_obj_beg(beg_bit, search_end), end_bit); |
|
403 return bit_to_addr(res_bit); |
|
404 } |
|
405 |
|
406 inline HeapWord* |
|
407 ParMarkBitMap::find_obj_end(HeapWord* beg, HeapWord* end) const |
|
408 { |
|
409 const idx_t beg_bit = addr_to_bit(beg); |
|
410 const idx_t end_bit = addr_to_bit(end); |
|
411 const idx_t search_end = BitMap::word_align_up(end_bit); |
|
412 const idx_t res_bit = MIN2(find_obj_end(beg_bit, search_end), end_bit); |
|
413 return bit_to_addr(res_bit); |
|
414 } |
|
415 |
|
416 #ifdef ASSERT |
|
417 inline void ParMarkBitMap::verify_bit(idx_t bit) const { |
|
418 // Allow one past the last valid bit; useful for loop bounds. |
|
419 assert(bit <= _beg_bits.size(), "bit out of range"); |
|
420 } |
|
421 |
|
422 inline void ParMarkBitMap::verify_addr(HeapWord* addr) const { |
|
423 // Allow one past the last valid address; useful for loop bounds. |
|
424 assert(addr >= region_start(), "addr too small"); |
|
425 assert(addr <= region_start() + region_size(), "addr too big"); |
|
426 } |
|
427 #endif // #ifdef ASSERT |