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 #include "precompiled.hpp"
26 #include "gc/g1/g1CollectedHeap.inline.hpp"
27 #include "gc/g1/g1ConcurrentMark.inline.hpp"
28 #include "gc/g1/g1CardLiveData.inline.hpp"
29 #include "gc/g1/suspendibleThreadSet.hpp"
30 #include "gc/shared/workgroup.hpp"
31 #include "memory/universe.hpp"
32 #include "runtime/atomic.inline.hpp"
33 #include "runtime/globals.hpp"
34 #include "runtime/os.hpp"
35 #include "utilities/bitMap.inline.hpp"
36 #include "utilities/debug.hpp"
37
38 G1CardLiveData::G1CardLiveData() :
39 _max_capacity(0),
40 _cards_per_region(0),
41 _live_regions(NULL),
42 _live_regions_size_in_bits(0),
43 _live_cards(NULL),
44 _live_cards_size_in_bits(0) {
45 }
46
47 G1CardLiveData::~G1CardLiveData() {
48 free_large_bitmap(_live_cards, _live_cards_size_in_bits);
49 free_large_bitmap(_live_regions, _live_regions_size_in_bits);
50 }
51
52 G1CardLiveData::bm_word_t* G1CardLiveData::allocate_large_bitmap(size_t size_in_bits) {
53 size_t size_in_words = BitMap::calc_size_in_words(size_in_bits);
54
55 bm_word_t* map = MmapArrayAllocator<bm_word_t, mtGC>::allocate(size_in_words);
56
57 return map;
58 }
59
60 void G1CardLiveData::free_large_bitmap(bm_word_t* bitmap, size_t size_in_bits) {
110 assert((end_idx - start_idx) > 0, "at least one bit");
111
112 // For small ranges use a simple loop; otherwise use set_range.
113 // The range is made up of the cards that are spanned by an object/mem
114 // region so 8 cards will allow up to object sizes up to 4K to be handled
115 // using the loop.
116 if ((end_idx - start_idx) <= 8) {
117 for (BitMap::idx_t i = start_idx; i < end_idx; i += 1) {
118 _card_bm.set_bit(i);
119 }
120 } else {
121 _card_bm.set_range(start_idx, end_idx);
122 }
123 }
124
125 // We cache the last mark set. This avoids setting the same bit multiple times.
126 // This is particularly interesting for dense bitmaps, as this avoids doing
127 // lots of work most of the time.
128 BitMap::idx_t _last_marked_bit_idx;
129
130 // Mark the card liveness bitmap for the object spanning from start to end.
131 void mark_card_bitmap_range(HeapWord* start, HeapWord* end) {
132 BitMap::idx_t start_idx = card_live_bitmap_index_for(start);
133 BitMap::idx_t end_idx = card_live_bitmap_index_for((HeapWord*)align_ptr_up(end, CardTableModRefBS::card_size));
134
135 assert((end_idx - start_idx) > 0, "Trying to mark zero sized range.");
136
137 if (start_idx == _last_marked_bit_idx) {
138 start_idx++;
139 }
140 if (start_idx == end_idx) {
141 return;
142 }
143
144 // Set the bits in the card bitmap for the cards spanned by this object.
145 set_card_bitmap_range(start_idx, end_idx);
146 _last_marked_bit_idx = end_idx - 1;
147 }
148
149 void reset_mark_cache() {
152
153 public:
154 // Returns the index in the per-card liveness count bitmap
155 // for the given address
156 inline BitMap::idx_t card_live_bitmap_index_for(HeapWord* addr) {
157 // Below, the term "card num" means the result of shifting an address
158 // by the card shift -- address 0 corresponds to card number 0. One
159 // must subtract the card num of the bottom of the heap to obtain a
160 // card table index.
161 BitMap::idx_t card_num = uintptr_t(addr) >> CardTableModRefBS::card_shift;
162 return card_num - _heap_card_bias;
163 }
164
165 // Takes a region that's not empty (i.e., it has at least one
166 // live object in it and sets its corresponding bit on the region
167 // bitmap to 1.
168 void set_bit_for_region(HeapRegion* hr) {
169 _region_bm.par_set_bit(hr->hrm_index());
170 }
171
172 // Mark the range of bits covered by allocations done since the last marking
173 // in the given heap region, i.e. from NTAMS to top of the given region.
174 // Returns if there has been some allocation in this region since the last marking.
175 bool mark_allocated_since_marking(HeapRegion* hr) {
176 reset_mark_cache();
177
178 HeapWord* ntams = hr->next_top_at_mark_start();
179 HeapWord* top = hr->top();
180
181 assert(hr->bottom() <= ntams && ntams <= hr->end(), "Preconditions.");
182
183 // Mark the allocated-since-marking portion...
184 if (ntams < top) {
185 mark_card_bitmap_range(ntams, top);
186 return true;
187 } else {
188 return false;
189 }
190 }
191
282 public:
283 G1CreateCardLiveDataTask(G1CMBitMap* bitmap,
284 G1CardLiveData* live_data,
285 uint n_workers) :
286 AbstractGangTask("G1 Create Live Data"),
287 _live_data(live_data),
288 _hr_claimer(n_workers) {
289 }
290
291 void work(uint worker_id) {
292 SuspendibleThreadSetJoiner sts_join;
293
294 G1CollectedHeap* g1h = G1CollectedHeap::heap();
295 G1ConcurrentMark* cm = g1h->concurrent_mark();
296 G1CreateLiveDataClosure cl(g1h, cm, cm->nextMarkBitMap(), _live_data);
297 g1h->heap_region_par_iterate(&cl, worker_id, &_hr_claimer);
298 }
299 };
300
301 void G1CardLiveData::create(WorkGang* workers, G1CMBitMap* mark_bitmap) {
302 uint n_workers = workers->active_workers();
303
304 G1CreateCardLiveDataTask cl(mark_bitmap,
305 this,
306 n_workers);
307 workers->run_task(&cl);
308 }
309
310 class G1FinalizeCardLiveDataTask: public AbstractGangTask {
311 // Finalizes the liveness counting data.
312 // Sets the bits corresponding to the interval [NTAMS, top]
313 // (which contains the implicitly live objects) in the
314 // card liveness bitmap. Also sets the bit for each region
315 // containing live data, in the region liveness bitmap.
316 class G1FinalizeCardLiveDataClosure: public HeapRegionClosure {
317 private:
318 G1CardLiveDataHelper _helper;
319 public:
320 G1FinalizeCardLiveDataClosure(G1CollectedHeap* g1h,
321 G1CMBitMap* bitmap,
322 G1CardLiveData* live_data) :
323 HeapRegionClosure(),
324 _helper(live_data, g1h->reserved_region().start()) { }
325
326 bool doHeapRegion(HeapRegion* hr) {
327 bool allocated_since_marking = _helper.mark_allocated_since_marking(hr);
328 if (allocated_since_marking || hr->next_marked_bytes() > 0) {
329 _helper.set_bit_for_region(hr);
330 }
331 return false;
332 }
333 };
334
335 G1CMBitMap* _bitmap;
336
337 G1CardLiveData* _live_data;
338
339 HeapRegionClaimer _hr_claimer;
340
341 public:
342 G1FinalizeCardLiveDataTask(G1CMBitMap* bitmap, G1CardLiveData* live_data, uint n_workers) :
343 AbstractGangTask("G1 Finalize Card Live Data"),
344 _bitmap(bitmap),
345 _live_data(live_data),
346 _hr_claimer(n_workers) {
436 G1CardLiveData* exp_live_data) :
437 _g1h(g1h),
438 _mark_bitmap(mark_bitmap),
439 _helper(exp_live_data, g1h->reserved_region().start()),
440 _act_live_data(act_live_data),
441 _exp_live_data(exp_live_data),
442 _failures(0) { }
443
444 int failures() const { return _failures; }
445
446 bool doHeapRegion(HeapRegion* hr) {
447 int failures = 0;
448
449 // Walk the marking bitmap for this region and set the corresponding bits
450 // in the expected region and card bitmaps.
451 size_t exp_marked_bytes = create_live_data_count(hr);
452 size_t act_marked_bytes = hr->next_marked_bytes();
453 // Verify the marked bytes for this region.
454
455 if (exp_marked_bytes != act_marked_bytes) {
456 failures += 1;
457 } else if (exp_marked_bytes > HeapRegion::GrainBytes) {
458 failures += 1;
459 }
460
461 // Verify the bit, for this region, in the actual and expected
462 // (which was just calculated) region bit maps.
463 // We're not OK if the bit in the calculated expected region
464 // bitmap is set and the bit in the actual region bitmap is not.
465 uint index = hr->hrm_index();
466
467 bool expected = _exp_live_data->is_region_live(index);
468 bool actual = _act_live_data->is_region_live(index);
469 if (expected && !actual) {
470 failures += 1;
471 }
472
473 // Verify that the card bit maps for the cards spanned by the current
474 // region match. We have an error if we have a set bit in the expected
475 // bit map and the corresponding bit in the actual bitmap is not set.
476
477 BitMap::idx_t start_idx = _helper.card_live_bitmap_index_for(hr->bottom());
478 BitMap::idx_t end_idx = _helper.card_live_bitmap_index_for(hr->top());
479
480 for (BitMap::idx_t i = start_idx; i < end_idx; i+=1) {
481 expected = _exp_live_data->is_card_live_at(i);
482 actual = _act_live_data->is_card_live_at(i);
483
484 if (expected && !actual) {
485 failures += 1;
486 }
487 }
488
489 _failures += failures;
490
491 // We could stop iteration over the heap when we
492 // find the first violating region by returning true.
493 return false;
494 }
495 };
496 protected:
497 G1CollectedHeap* _g1h;
498 G1CMBitMap* _mark_bitmap;
499
500 G1CardLiveData* _act_live_data;
501
502 G1CardLiveData _exp_live_data;
503
504 int _failures;
|
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 #include "precompiled.hpp"
26 #include "gc/g1/g1CollectedHeap.inline.hpp"
27 #include "gc/g1/g1ConcurrentMark.inline.hpp"
28 #include "gc/g1/g1CardLiveData.inline.hpp"
29 #include "gc/g1/suspendibleThreadSet.hpp"
30 #include "gc/shared/workgroup.hpp"
31 #include "logging/log.hpp"
32 #include "memory/universe.hpp"
33 #include "runtime/atomic.inline.hpp"
34 #include "runtime/globals.hpp"
35 #include "runtime/os.hpp"
36 #include "utilities/bitMap.inline.hpp"
37 #include "utilities/debug.hpp"
38
39 G1CardLiveData::G1CardLiveData() :
40 _max_capacity(0),
41 _cards_per_region(0),
42 _gc_timestamp_at_create(0),
43 _live_regions(NULL),
44 _live_regions_size_in_bits(0),
45 _live_cards(NULL),
46 _live_cards_size_in_bits(0) {
47 }
48
49 G1CardLiveData::~G1CardLiveData() {
50 free_large_bitmap(_live_cards, _live_cards_size_in_bits);
51 free_large_bitmap(_live_regions, _live_regions_size_in_bits);
52 }
53
54 G1CardLiveData::bm_word_t* G1CardLiveData::allocate_large_bitmap(size_t size_in_bits) {
55 size_t size_in_words = BitMap::calc_size_in_words(size_in_bits);
56
57 bm_word_t* map = MmapArrayAllocator<bm_word_t, mtGC>::allocate(size_in_words);
58
59 return map;
60 }
61
62 void G1CardLiveData::free_large_bitmap(bm_word_t* bitmap, size_t size_in_bits) {
112 assert((end_idx - start_idx) > 0, "at least one bit");
113
114 // For small ranges use a simple loop; otherwise use set_range.
115 // The range is made up of the cards that are spanned by an object/mem
116 // region so 8 cards will allow up to object sizes up to 4K to be handled
117 // using the loop.
118 if ((end_idx - start_idx) <= 8) {
119 for (BitMap::idx_t i = start_idx; i < end_idx; i += 1) {
120 _card_bm.set_bit(i);
121 }
122 } else {
123 _card_bm.set_range(start_idx, end_idx);
124 }
125 }
126
127 // We cache the last mark set. This avoids setting the same bit multiple times.
128 // This is particularly interesting for dense bitmaps, as this avoids doing
129 // lots of work most of the time.
130 BitMap::idx_t _last_marked_bit_idx;
131
132 void clear_card_bitmap_range(HeapWord* start, HeapWord* end) {
133 BitMap::idx_t start_idx = card_live_bitmap_index_for(start);
134 BitMap::idx_t end_idx = card_live_bitmap_index_for((HeapWord*)align_ptr_up(end, CardTableModRefBS::card_size));
135
136 _card_bm.clear_range(start_idx, end_idx);
137 }
138
139 // Mark the card liveness bitmap for the object spanning from start to end.
140 void mark_card_bitmap_range(HeapWord* start, HeapWord* end) {
141 BitMap::idx_t start_idx = card_live_bitmap_index_for(start);
142 BitMap::idx_t end_idx = card_live_bitmap_index_for((HeapWord*)align_ptr_up(end, CardTableModRefBS::card_size));
143
144 assert((end_idx - start_idx) > 0, "Trying to mark zero sized range.");
145
146 if (start_idx == _last_marked_bit_idx) {
147 start_idx++;
148 }
149 if (start_idx == end_idx) {
150 return;
151 }
152
153 // Set the bits in the card bitmap for the cards spanned by this object.
154 set_card_bitmap_range(start_idx, end_idx);
155 _last_marked_bit_idx = end_idx - 1;
156 }
157
158 void reset_mark_cache() {
161
162 public:
163 // Returns the index in the per-card liveness count bitmap
164 // for the given address
165 inline BitMap::idx_t card_live_bitmap_index_for(HeapWord* addr) {
166 // Below, the term "card num" means the result of shifting an address
167 // by the card shift -- address 0 corresponds to card number 0. One
168 // must subtract the card num of the bottom of the heap to obtain a
169 // card table index.
170 BitMap::idx_t card_num = uintptr_t(addr) >> CardTableModRefBS::card_shift;
171 return card_num - _heap_card_bias;
172 }
173
174 // Takes a region that's not empty (i.e., it has at least one
175 // live object in it and sets its corresponding bit on the region
176 // bitmap to 1.
177 void set_bit_for_region(HeapRegion* hr) {
178 _region_bm.par_set_bit(hr->hrm_index());
179 }
180
181 void reset_live_data(HeapRegion* hr) {
182 clear_card_bitmap_range(hr->next_top_at_mark_start(), hr->end());
183 }
184
185 // Mark the range of bits covered by allocations done since the last marking
186 // in the given heap region, i.e. from NTAMS to top of the given region.
187 // Returns if there has been some allocation in this region since the last marking.
188 bool mark_allocated_since_marking(HeapRegion* hr) {
189 reset_mark_cache();
190
191 HeapWord* ntams = hr->next_top_at_mark_start();
192 HeapWord* top = hr->top();
193
194 assert(hr->bottom() <= ntams && ntams <= hr->end(), "Preconditions.");
195
196 // Mark the allocated-since-marking portion...
197 if (ntams < top) {
198 mark_card_bitmap_range(ntams, top);
199 return true;
200 } else {
201 return false;
202 }
203 }
204
295 public:
296 G1CreateCardLiveDataTask(G1CMBitMap* bitmap,
297 G1CardLiveData* live_data,
298 uint n_workers) :
299 AbstractGangTask("G1 Create Live Data"),
300 _live_data(live_data),
301 _hr_claimer(n_workers) {
302 }
303
304 void work(uint worker_id) {
305 SuspendibleThreadSetJoiner sts_join;
306
307 G1CollectedHeap* g1h = G1CollectedHeap::heap();
308 G1ConcurrentMark* cm = g1h->concurrent_mark();
309 G1CreateLiveDataClosure cl(g1h, cm, cm->nextMarkBitMap(), _live_data);
310 g1h->heap_region_par_iterate(&cl, worker_id, &_hr_claimer);
311 }
312 };
313
314 void G1CardLiveData::create(WorkGang* workers, G1CMBitMap* mark_bitmap) {
315 _gc_timestamp_at_create = G1CollectedHeap::heap()->get_gc_time_stamp();
316
317 uint n_workers = workers->active_workers();
318
319 G1CreateCardLiveDataTask cl(mark_bitmap,
320 this,
321 n_workers);
322 workers->run_task(&cl);
323 }
324
325 class G1FinalizeCardLiveDataTask: public AbstractGangTask {
326 // Finalizes the liveness counting data.
327 // Sets the bits corresponding to the interval [NTAMS, top]
328 // (which contains the implicitly live objects) in the
329 // card liveness bitmap. Also sets the bit for each region
330 // containing live data, in the region liveness bitmap.
331 class G1FinalizeCardLiveDataClosure: public HeapRegionClosure {
332 private:
333 G1CardLiveDataHelper _helper;
334
335 uint _gc_timestamp_at_create;
336
337 bool has_been_reclaimed(HeapRegion* hr) const {
338 return hr->get_gc_time_stamp() > _gc_timestamp_at_create;
339 }
340 public:
341 G1FinalizeCardLiveDataClosure(G1CollectedHeap* g1h,
342 G1CMBitMap* bitmap,
343 G1CardLiveData* live_data) :
344 HeapRegionClosure(),
345 _helper(live_data, g1h->reserved_region().start()),
346 _gc_timestamp_at_create(live_data->gc_timestamp_at_create()) { }
347
348 bool doHeapRegion(HeapRegion* hr) {
349 if (has_been_reclaimed(hr)) {
350 _helper.reset_live_data(hr);
351 }
352 bool allocated_since_marking = _helper.mark_allocated_since_marking(hr);
353 if (allocated_since_marking || hr->next_marked_bytes() > 0) {
354 _helper.set_bit_for_region(hr);
355 }
356 return false;
357 }
358 };
359
360 G1CMBitMap* _bitmap;
361
362 G1CardLiveData* _live_data;
363
364 HeapRegionClaimer _hr_claimer;
365
366 public:
367 G1FinalizeCardLiveDataTask(G1CMBitMap* bitmap, G1CardLiveData* live_data, uint n_workers) :
368 AbstractGangTask("G1 Finalize Card Live Data"),
369 _bitmap(bitmap),
370 _live_data(live_data),
371 _hr_claimer(n_workers) {
461 G1CardLiveData* exp_live_data) :
462 _g1h(g1h),
463 _mark_bitmap(mark_bitmap),
464 _helper(exp_live_data, g1h->reserved_region().start()),
465 _act_live_data(act_live_data),
466 _exp_live_data(exp_live_data),
467 _failures(0) { }
468
469 int failures() const { return _failures; }
470
471 bool doHeapRegion(HeapRegion* hr) {
472 int failures = 0;
473
474 // Walk the marking bitmap for this region and set the corresponding bits
475 // in the expected region and card bitmaps.
476 size_t exp_marked_bytes = create_live_data_count(hr);
477 size_t act_marked_bytes = hr->next_marked_bytes();
478 // Verify the marked bytes for this region.
479
480 if (exp_marked_bytes != act_marked_bytes) {
481 log_error(gc)("Expected marked bytes " SIZE_FORMAT " != actual marked bytes " SIZE_FORMAT " in region %u", exp_marked_bytes, act_marked_bytes, hr->hrm_index());
482 failures += 1;
483 } else if (exp_marked_bytes > HeapRegion::GrainBytes) {
484 log_error(gc)("Expected marked bytes " SIZE_FORMAT " larger than possible " SIZE_FORMAT " in region %u", exp_marked_bytes, HeapRegion::GrainBytes, hr->hrm_index());
485 failures += 1;
486 }
487
488 // Verify the bit, for this region, in the actual and expected
489 // (which was just calculated) region bit maps.
490 // We're not OK if the bit in the calculated expected region
491 // bitmap is set and the bit in the actual region bitmap is not.
492 uint index = hr->hrm_index();
493
494 bool expected = _exp_live_data->is_region_live(index);
495 bool actual = _act_live_data->is_region_live(index);
496 if (expected != actual) {
497 log_error(gc)("Expected liveness %d not equal actual %d in region %u", expected, actual, hr->hrm_index());
498 failures += 1;
499 }
500
501 // Verify that the card bit maps for the cards spanned by the current
502 // region match. We have an error if we have a set bit in the expected
503 // bit map and the corresponding bit in the actual bitmap is not set.
504
505 BitMap::idx_t start_idx = _helper.card_live_bitmap_index_for(hr->bottom());
506 BitMap::idx_t end_idx = _helper.card_live_bitmap_index_for(hr->top());
507
508 for (BitMap::idx_t i = start_idx; i < end_idx; i+=1) {
509 expected = _exp_live_data->is_card_live_at(i);
510 actual = _act_live_data->is_card_live_at(i);
511
512 if (expected != actual) {
513 log_error(gc)("Expected card liveness %d not equal actual card liveness %d at card " SIZE_FORMAT " in region %u", expected, actual, i, hr->hrm_index());
514 failures += 1;
515 }
516 }
517
518 _failures += failures;
519
520 // We could stop iteration over the heap when we
521 // find the first violating region by returning true.
522 return false;
523 }
524 };
525 protected:
526 G1CollectedHeap* _g1h;
527 G1CMBitMap* _mark_bitmap;
528
529 G1CardLiveData* _act_live_data;
530
531 G1CardLiveData _exp_live_data;
532
533 int _failures;
|