|
0
|
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
|
