1 /*
2 * Copyright (c) 2016, Oracle and/or its affiliates. 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 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 BitMap::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 BitMap::bm_word_t* map = MmapArrayAllocator<BitMap::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) {
61 MmapArrayAllocator<BitMap::bm_word_t, mtGC>::free(bitmap, size_in_bits / BitsPerWord);
62 }
63
64 void G1CardLiveData::initialize(size_t max_capacity, uint num_max_regions) {
65 assert(max_capacity % num_max_regions == 0,
66 "Given capacity must be evenly divisible by region size.");
67 size_t region_size = max_capacity / num_max_regions;
68 assert(region_size % (G1SATBCardTableModRefBS::card_size * BitsPerWord) == 0,
69 "Region size must be evenly divisible by area covered by a single word.");
70 _max_capacity = max_capacity;
71 _cards_per_region = region_size >> G1SATBCardTableModRefBS::card_shift;
72
73 _live_regions_size_in_bits = live_region_bitmap_size_in_bits();
74 _live_regions = allocate_large_bitmap(_live_regions_size_in_bits);
75 _live_cards_size_in_bits = live_card_bitmap_size_in_bits();
76 _live_cards = allocate_large_bitmap(_live_cards_size_in_bits);
77 }
78
79 void G1CardLiveData::pretouch() {
80 live_cards_bm().pretouch();
81 live_regions_bm().pretouch();
82 }
83
84 size_t G1CardLiveData::live_region_bitmap_size_in_bits() const {
85 return _max_capacity / (_cards_per_region << G1SATBCardTableModRefBS::card_shift);
86 }
87
88 size_t G1CardLiveData::live_card_bitmap_size_in_bits() const {
89 return _max_capacity >> G1SATBCardTableModRefBS::card_shift;
90 }
91
92 // Helper class that provides functionality to generate the Live Data Count
93 // information.
94 class G1CardLiveDataHelper VALUE_OBJ_CLASS_SPEC {
95 private:
96 BitMap _region_bm;
97 BitMap _card_bm;
98
99 // The card number of the bottom of the G1 heap.
100 // Used in biasing indices into accounting card bitmaps.
101 BitMap::idx_t _heap_card_bias;
102
103 // Utility routine to set an exclusive range of bits on the given
104 // bitmap, optimized for very small ranges.
105 // There must be at least one bit to set.
106 void set_card_bitmap_range(BitMap::idx_t start_idx,
107 BitMap::idx_t end_idx) {
108
109 // Set the exclusive bit range [start_idx, end_idx).
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() {
150 _last_marked_bit_idx = (BitMap::idx_t)-1;
151 }
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
192 // Mark the range of bits covered by live objects on the mark bitmap between
193 // bottom and NTAMS of the given region.
194 // Returns the number of live bytes marked within that area for the given
195 // heap region.
196 size_t mark_marked_during_marking(G1CMBitMap* mark_bitmap, HeapRegion* hr) {
197 reset_mark_cache();
198
199 size_t marked_bytes = 0;
200
201 HeapWord* ntams = hr->next_top_at_mark_start();
202 HeapWord* start = hr->bottom();
203
204 if (ntams <= start) {
205 // Skip empty regions.
206 return 0;
207 }
208 if (hr->is_humongous()) {
209 mark_card_bitmap_range(start, hr->top());
210 return pointer_delta(hr->top(), start, 1);
211 }
212
213 assert(start <= hr->end() && start <= ntams && ntams <= hr->end(),
214 "Preconditions not met - "
215 "start: " PTR_FORMAT ", ntams: " PTR_FORMAT ", end: " PTR_FORMAT,
216 p2i(start), p2i(ntams), p2i(hr->end()));
217
218 // Find the first marked object at or after "start".
219 start = mark_bitmap->getNextMarkedWordAddress(start, ntams);
220 while (start < ntams) {
221 oop obj = oop(start);
222 size_t obj_size = obj->size();
223 HeapWord* obj_end = start + obj_size;
224
225 assert(obj_end <= hr->end(), "Humongous objects must have been handled elsewhere.");
226
227 mark_card_bitmap_range(start, obj_end);
228
229 // Add the size of this object to the number of marked bytes.
230 marked_bytes += obj_size * HeapWordSize;
231
232 // Find the next marked object after this one.
233 start = mark_bitmap->getNextMarkedWordAddress(obj_end, ntams);
234 }
235
236 return marked_bytes;
237 }
238
239 G1CardLiveDataHelper(G1CardLiveData* live_data, HeapWord* base_address) :
240 _region_bm(live_data->live_regions_bm()),
241 _card_bm(live_data->live_cards_bm()) {
242 // Calculate the card number for the bottom of the heap. Used
243 // in biasing indexes into the accounting card bitmaps.
244 _heap_card_bias =
245 uintptr_t(base_address) >> CardTableModRefBS::card_shift;
246 }
247 };
248
249 class G1CreateCardLiveDataTask: public AbstractGangTask {
250 // Aggregate the counting data that was constructed concurrently
251 // with marking.
252 class G1CreateLiveDataClosure : public HeapRegionClosure {
253 G1CardLiveDataHelper _helper;
254
255 G1CMBitMap* _mark_bitmap;
256
257 G1ConcurrentMark* _cm;
258 public:
259 G1CreateLiveDataClosure(G1CollectedHeap* g1h,
260 G1ConcurrentMark* cm,
261 G1CMBitMap* mark_bitmap,
262 G1CardLiveData* live_data) :
263 HeapRegionClosure(),
264 _helper(live_data, g1h->reserved_region().start()),
265 _mark_bitmap(mark_bitmap),
266 _cm(cm) { }
267
268 bool doHeapRegion(HeapRegion* hr) {
269 size_t marked_bytes = _helper.mark_marked_during_marking(_mark_bitmap, hr);
270 if (marked_bytes > 0) {
271 hr->add_to_marked_bytes(marked_bytes);
272 }
273
274 if (_cm->do_yield_check() && _cm->has_aborted()) {
275 return true;
276 }
277 return false;
278 }
279 };
280
281 G1ConcurrentMark* _cm;
282 G1CardLiveData* _live_data;
283 HeapRegionClaimer _hr_claimer;
284
285 public:
286 G1CreateCardLiveDataTask(G1CMBitMap* bitmap,
287 G1CardLiveData* live_data,
288 uint n_workers) :
289 AbstractGangTask("G1 Create Live Data"),
290 _live_data(live_data),
291 _hr_claimer(n_workers) {
292 }
293
294 void work(uint worker_id) {
295 SuspendibleThreadSetJoiner sts_join;
296
297 G1CollectedHeap* g1h = G1CollectedHeap::heap();
298 G1ConcurrentMark* cm = g1h->concurrent_mark();
299 G1CreateLiveDataClosure cl(g1h, cm, cm->nextMarkBitMap(), _live_data);
300 g1h->heap_region_par_iterate(&cl, worker_id, &_hr_claimer);
301 }
302 };
303
304 void G1CardLiveData::create(WorkGang* workers, G1CMBitMap* mark_bitmap) {
305 uint n_workers = workers->active_workers();
306
307 G1CreateCardLiveDataTask cl(mark_bitmap,
308 this,
309 n_workers);
310 workers->run_task(&cl);
311 }
312
313 class G1FinalizeCardLiveDataTask: public AbstractGangTask {
314 // Finalizes the liveness counting data.
315 // Sets the bits corresponding to the interval [NTAMS, top]
316 // (which contains the implicitly live objects) in the
317 // card liveness bitmap. Also sets the bit for each region
318 // containing live data, in the region liveness bitmap.
319 class G1FinalizeCardLiveDataClosure: public HeapRegionClosure {
320 private:
321 G1CardLiveDataHelper _helper;
322 public:
323 G1FinalizeCardLiveDataClosure(G1CollectedHeap* g1h,
324 G1CMBitMap* bitmap,
325 G1CardLiveData* live_data) :
326 HeapRegionClosure(),
327 _helper(live_data, g1h->reserved_region().start()) { }
328
329 bool doHeapRegion(HeapRegion* hr) {
330 bool allocated_since_marking = _helper.mark_allocated_since_marking(hr);
331 if (allocated_since_marking || hr->next_marked_bytes() > 0) {
332 _helper.set_bit_for_region(hr);
333 }
334 return false;
335 }
336 };
337
338 G1CMBitMap* _bitmap;
339
340 G1CardLiveData* _live_data;
341
342 HeapRegionClaimer _hr_claimer;
343
344 public:
345 G1FinalizeCardLiveDataTask(G1CMBitMap* bitmap, G1CardLiveData* live_data, uint n_workers) :
346 AbstractGangTask("G1 Finalize Card Live Data"),
347 _bitmap(bitmap),
348 _live_data(live_data),
349 _hr_claimer(n_workers) {
350 }
351
352 void work(uint worker_id) {
353 G1FinalizeCardLiveDataClosure cl(G1CollectedHeap::heap(), _bitmap, _live_data);
354
355 G1CollectedHeap::heap()->heap_region_par_iterate(&cl, worker_id, &_hr_claimer);
356 }
357 };
358
359 void G1CardLiveData::finalize(WorkGang* workers, G1CMBitMap* mark_bitmap) {
360 // Finalize the live data.
361 G1FinalizeCardLiveDataTask cl(mark_bitmap,
362 this,
363 workers->active_workers());
364 workers->run_task(&cl);
365 }
366
367 class G1ClearCardLiveDataTask : public AbstractGangTask {
368 BitMap _bitmap;
369 size_t _num_chunks;
370 size_t _cur_chunk;
371 public:
372 G1ClearCardLiveDataTask(BitMap bitmap, size_t num_tasks) :
373 AbstractGangTask("G1 Clear Card Live Data"),
374 _bitmap(bitmap),
375 _num_chunks(num_tasks),
376 _cur_chunk(0) {
377 }
378
379 static size_t chunk_size() { return M; }
380
381 virtual void work(uint worker_id) {
382 while (true) {
383 size_t to_process = Atomic::add(1, &_cur_chunk) - 1;
384 if (to_process >= _num_chunks) {
385 break;
386 }
387
388 BitMap::idx_t start = M * BitsPerByte * to_process;
389 BitMap::idx_t end = MIN2(start + M * BitsPerByte, _bitmap.size());
390 _bitmap.clear_range(start, end);
391 }
392 }
393 };
394
395 void G1CardLiveData::clear(WorkGang* workers) {
396 guarantee(Universe::is_fully_initialized(), "Should not call this during initialization.");
397
398 size_t const num_chunks = align_size_up(live_cards_bm().size_in_bytes(), G1ClearCardLiveDataTask::chunk_size()) / G1ClearCardLiveDataTask::chunk_size();
399
400 G1ClearCardLiveDataTask cl(live_cards_bm(), num_chunks);
401 workers->run_task(&cl);
402
403 // The region live bitmap is always very small, even for huge heaps. Clear
404 // directly.
405 live_regions_bm().clear();
406 }
407
408 class G1VerifyCardLiveDataTask: public AbstractGangTask {
409 // Heap region closure used for verifying the live count data
410 // that was created concurrently and finalized during
411 // the remark pause. This closure is applied to the heap
412 // regions during the STW cleanup pause.
413 class G1VerifyCardLiveDataClosure: public HeapRegionClosure {
414 private:
415 G1CollectedHeap* _g1h;
416 G1CMBitMap* _mark_bitmap;
417 G1CardLiveDataHelper _helper;
418
419 G1CardLiveData* _act_live_data;
420
421 G1CardLiveData* _exp_live_data;
422
423 int _failures;
424
425 // Completely recreates the live data count for the given heap region and
426 // returns the number of bytes marked.
427 size_t create_live_data_count(HeapRegion* hr) {
428 size_t bytes_marked = _helper.mark_marked_during_marking(_mark_bitmap, hr);
429 bool allocated_since_marking = _helper.mark_allocated_since_marking(hr);
430 if (allocated_since_marking || bytes_marked > 0) {
431 _helper.set_bit_for_region(hr);
432 }
433 return bytes_marked;
434 }
435 public:
436 G1VerifyCardLiveDataClosure(G1CollectedHeap* g1h,
437 G1CMBitMap* mark_bitmap,
438 G1CardLiveData* act_live_data,
439 G1CardLiveData* exp_live_data) :
440 _g1h(g1h),
441 _mark_bitmap(mark_bitmap),
442 _helper(exp_live_data, g1h->reserved_region().start()),
443 _act_live_data(act_live_data),
444 _exp_live_data(exp_live_data),
445 _failures(0) { }
446
447 int failures() const { return _failures; }
448
449 bool doHeapRegion(HeapRegion* hr) {
450 int failures = 0;
451
452 // Walk the marking bitmap for this region and set the corresponding bits
453 // in the expected region and card bitmaps.
454 size_t exp_marked_bytes = create_live_data_count(hr);
455 size_t act_marked_bytes = hr->next_marked_bytes();
456 // Verify the marked bytes for this region.
457
458 if (exp_marked_bytes != act_marked_bytes) {
459 failures += 1;
460 } else if (exp_marked_bytes > HeapRegion::GrainBytes) {
461 failures += 1;
462 }
463
464 // Verify the bit, for this region, in the actual and expected
465 // (which was just calculated) region bit maps.
466 // We're not OK if the bit in the calculated expected region
467 // bitmap is set and the bit in the actual region bitmap is not.
468 uint index = hr->hrm_index();
469
470 bool expected = _exp_live_data->is_region_live(index);
471 bool actual = _act_live_data->is_region_live(index);
472 if (expected && !actual) {
473 failures += 1;
474 }
475
476 // Verify that the card bit maps for the cards spanned by the current
477 // region match. We have an error if we have a set bit in the expected
478 // bit map and the corresponding bit in the actual bitmap is not set.
479
480 BitMap::idx_t start_idx = _helper.card_live_bitmap_index_for(hr->bottom());
481 BitMap::idx_t end_idx = _helper.card_live_bitmap_index_for(hr->top());
482
483 for (BitMap::idx_t i = start_idx; i < end_idx; i+=1) {
484 expected = _exp_live_data->is_card_live_at(i);
485 actual = _act_live_data->is_card_live_at(i);
486
487 if (expected && !actual) {
488 failures += 1;
489 }
490 }
491
492 _failures += failures;
493
494 // We could stop iteration over the heap when we
495 // find the first violating region by returning true.
496 return false;
497 }
498 };
499 protected:
500 G1CollectedHeap* _g1h;
501 G1CMBitMap* _mark_bitmap;
502
503 G1CardLiveData* _act_live_data;
504
505 G1CardLiveData _exp_live_data;
506
507 int _failures;
508
509 HeapRegionClaimer _hr_claimer;
510
511 public:
512 G1VerifyCardLiveDataTask(G1CMBitMap* bitmap,
513 G1CardLiveData* act_live_data,
514 uint n_workers)
515 : AbstractGangTask("G1 Verify Card Live Data"),
516 _g1h(G1CollectedHeap::heap()),
517 _mark_bitmap(bitmap),
518 _act_live_data(act_live_data),
519 _exp_live_data(),
520 _failures(0),
521 _hr_claimer(n_workers) {
522 assert(VerifyDuringGC, "don't call this otherwise");
523 _exp_live_data.initialize(_g1h->max_capacity(), _g1h->max_regions());
524 }
525
526 void work(uint worker_id) {
527 G1VerifyCardLiveDataClosure cl(_g1h,
528 _mark_bitmap,
529 _act_live_data,
530 &_exp_live_data);
531 _g1h->heap_region_par_iterate(&cl, worker_id, &_hr_claimer);
532
533 Atomic::add(cl.failures(), &_failures);
534 }
535
536 int failures() const { return _failures; }
537 };
538
539 void G1CardLiveData::verify(WorkGang* workers, G1CMBitMap* actual_bitmap) {
540 ResourceMark rm;
541
542 G1VerifyCardLiveDataTask cl(actual_bitmap,
543 this,
544 workers->active_workers());
545 workers->run_task(&cl);
546
547 guarantee(cl.failures() == 0, "Unexpected accounting failures");
548 }
549
550 #ifndef PRODUCT
551 void G1CardLiveData::verify_is_clear() {
552 assert(live_cards_bm().count_one_bits() == 0, "Live cards bitmap must be clear.");
553 assert(live_regions_bm().count_one_bits() == 0, "Live regions bitmap must be clear.");
554 }
555 #endif