Mercurial > hg > truffle
comparison src/share/vm/gc_implementation/parallelScavenge/parMarkBitMap.hpp @ 0:a61af66fc99e jdk7-b24
Initial load
author | duke |
---|---|
date | Sat, 01 Dec 2007 00:00:00 +0000 |
parents | |
children | 37f87013dfd8 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:a61af66fc99e |
---|---|
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 |