Mercurial > hg > truffle

comparison src/share/vm/gc_implementation/parallelScavenge/parMarkBitMap.hpp @ 0:a61af66fc99e jdk7-b24

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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