1 /*
2 * Copyright (c) 2016, 2018, 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/shared/suspendibleThreadSet.hpp"
30 #include "gc/shared/workgroup.hpp"
31 #include "logging/log.hpp"
32 #include "memory/resourceArea.hpp"
33 #include "memory/universe.hpp"
34 #include "runtime/atomic.hpp"
35 #include "runtime/globals.hpp"
36 #include "runtime/os.hpp"
37 #include "utilities/align.hpp"
38 #include "utilities/bitMap.inline.hpp"
39 #include "utilities/debug.hpp"
40
41 G1CardLiveData::G1CardLiveData() :
42 _max_capacity(0),
43 _cards_per_region(0),
44 _gc_timestamp_at_create(0),
45 _live_regions(NULL),
46 _live_regions_size_in_bits(0),
47 _live_cards(NULL),
48 _live_cards_size_in_bits(0) {
49 }
50
51 G1CardLiveData::~G1CardLiveData() {
52 free_large_bitmap(_live_cards, _live_cards_size_in_bits);
53 free_large_bitmap(_live_regions, _live_regions_size_in_bits);
54 }
55
56 G1CardLiveData::bm_word_t* G1CardLiveData::allocate_large_bitmap(size_t size_in_bits) {
57 size_t size_in_words = BitMap::calc_size_in_words(size_in_bits);
58
59 bm_word_t* map = MmapArrayAllocator<bm_word_t>::allocate(size_in_words, mtGC);
60
61 return map;
62 }
63
64 void G1CardLiveData::free_large_bitmap(bm_word_t* bitmap, size_t size_in_bits) {
65 MmapArrayAllocator<bm_word_t>::free(bitmap, BitMap::calc_size_in_words(size_in_bits));
66 }
67
68 void G1CardLiveData::initialize(size_t max_capacity, uint num_max_regions) {
69 assert(max_capacity % num_max_regions == 0,
70 "Given capacity must be evenly divisible by region size.");
71 size_t region_size = max_capacity / num_max_regions;
72 assert(region_size % (G1CardTable::card_size * BitsPerWord) == 0,
73 "Region size must be evenly divisible by area covered by a single word.");
74 _max_capacity = max_capacity;
75 _cards_per_region = region_size / G1CardTable::card_size;
76
77 _live_regions_size_in_bits = live_region_bitmap_size_in_bits();
78 _live_regions = allocate_large_bitmap(_live_regions_size_in_bits);
79 _live_cards_size_in_bits = live_card_bitmap_size_in_bits();
80 _live_cards = allocate_large_bitmap(_live_cards_size_in_bits);
81 }
82
83 void G1CardLiveData::pretouch() {
84 live_cards_bm().pretouch();
85 live_regions_bm().pretouch();
86 }
87
88 size_t G1CardLiveData::live_region_bitmap_size_in_bits() const {
89 return _max_capacity / (_cards_per_region << G1CardTable::card_shift);
90 }
91
92 size_t G1CardLiveData::live_card_bitmap_size_in_bits() const {
93 return _max_capacity >> G1CardTable::card_shift;
94 }
95
96 // Helper class that provides functionality to generate the Live Data Count
97 // information.
98 class G1CardLiveDataHelper {
99 private:
100 BitMapView _region_bm;
101 BitMapView _card_bm;
102
103 // The card number of the bottom of the G1 heap.
104 // Used in biasing indices into accounting card bitmaps.
105 BitMap::idx_t _heap_card_bias;
106
107 // Utility routine to set an exclusive range of bits on the given
108 // bitmap, optimized for very small ranges.
109 // There must be at least one bit to set.
110 void set_card_bitmap_range(BitMap::idx_t start_idx,
111 BitMap::idx_t end_idx) {
112
113 // Set the exclusive bit range [start_idx, end_idx).
114 assert((end_idx - start_idx) > 0, "at least one bit");
115
116 // For small ranges use a simple loop; otherwise use set_range.
117 // The range is made up of the cards that are spanned by an object/mem
118 // region so 8 cards will allow up to object sizes up to 4K to be handled
119 // using the loop.
120 if ((end_idx - start_idx) <= 8) {
121 for (BitMap::idx_t i = start_idx; i < end_idx; i += 1) {
122 _card_bm.set_bit(i);
123 }
124 } else {
125 _card_bm.set_range(start_idx, end_idx);
126 }
127 }
128
129 // We cache the last mark set. This avoids setting the same bit multiple times.
130 // This is particularly interesting for dense bitmaps, as this avoids doing
131 // lots of work most of the time.
132 BitMap::idx_t _last_marked_bit_idx;
133
134 void clear_card_bitmap_range(HeapWord* start, HeapWord* end) {
135 BitMap::idx_t start_idx = card_live_bitmap_index_for(start);
136 BitMap::idx_t end_idx = card_live_bitmap_index_for(align_up(end, CardTable::card_size));
137
138 _card_bm.clear_range(start_idx, end_idx);
139 }
140
141 // Mark the card liveness bitmap for the object spanning from start to end.
142 void mark_card_bitmap_range(HeapWord* start, HeapWord* end) {
143 BitMap::idx_t start_idx = card_live_bitmap_index_for(start);
144 BitMap::idx_t end_idx = card_live_bitmap_index_for(align_up(end, CardTable::card_size));
145
146 assert((end_idx - start_idx) > 0, "Trying to mark zero sized range.");
147
148 if (start_idx == _last_marked_bit_idx) {
149 start_idx++;
150 }
151 if (start_idx == end_idx) {
152 return;
153 }
154
155 // Set the bits in the card bitmap for the cards spanned by this object.
156 set_card_bitmap_range(start_idx, end_idx);
157 _last_marked_bit_idx = end_idx - 1;
158 }
159
160 void reset_mark_cache() {
161 _last_marked_bit_idx = (BitMap::idx_t)-1;
162 }
163
164 public:
165 // Returns the index in the per-card liveness count bitmap
166 // for the given address
167 inline BitMap::idx_t card_live_bitmap_index_for(HeapWord* addr) {
168 // Below, the term "card num" means the result of shifting an address
169 // by the card shift -- address 0 corresponds to card number 0. One
170 // must subtract the card num of the bottom of the heap to obtain a
171 // card table index.
172 BitMap::idx_t card_num = uintptr_t(addr) >> G1CardTable::card_shift;
173 return card_num - _heap_card_bias;
174 }
175
176 // Takes a region that's not empty (i.e., it has at least one
177 // live object in it and sets its corresponding bit on the region
178 // bitmap to 1.
179 void set_bit_for_region(HeapRegion* hr) {
180 _region_bm.par_set_bit(hr->hrm_index());
181 }
182
183 void reset_live_data(HeapRegion* hr) {
184 clear_card_bitmap_range(hr->next_top_at_mark_start(), hr->end());
185 }
186
187 // Mark the range of bits covered by allocations done since the last marking
188 // in the given heap region, i.e. from NTAMS to top of the given region.
189 // Returns if there has been some allocation in this region since the last marking.
190 bool mark_allocated_since_marking(HeapRegion* hr) {
191 reset_mark_cache();
192
193 HeapWord* ntams = hr->next_top_at_mark_start();
194 HeapWord* top = hr->top();
195
196 assert(hr->bottom() <= ntams && ntams <= hr->end(), "Preconditions.");
197
198 // Mark the allocated-since-marking portion...
199 if (ntams < top) {
200 mark_card_bitmap_range(ntams, top);
201 return true;
202 } else {
203 return false;
204 }
205 }
206
207 // Mark the range of bits covered by live objects on the mark bitmap between
208 // bottom and NTAMS of the given region.
209 // Returns the number of live bytes marked within that area for the given
210 // heap region.
211 size_t mark_marked_during_marking(G1CMBitMap* mark_bitmap, HeapRegion* hr) {
212 reset_mark_cache();
213
214 size_t marked_bytes = 0;
215
216 HeapWord* ntams = hr->next_top_at_mark_start();
217 HeapWord* start = hr->bottom();
218
219 if (ntams <= start) {
220 // Skip empty regions.
221 return 0;
222 }
223 if (hr->is_humongous()) {
224 HeapRegion* start_region = hr->humongous_start_region();
225 if (mark_bitmap->is_marked(start_region->bottom())) {
226 mark_card_bitmap_range(start, hr->top());
227 return pointer_delta(hr->top(), start, 1);
228 } else {
229 // Humongous start object was actually dead.
230 return 0;
231 }
232 }
233
234 assert(start <= hr->end() && start <= ntams && ntams <= hr->end(),
235 "Preconditions not met - "
236 "start: " PTR_FORMAT ", ntams: " PTR_FORMAT ", end: " PTR_FORMAT,
237 p2i(start), p2i(ntams), p2i(hr->end()));
238
239 // Find the first marked object at or after "start".
240 start = mark_bitmap->get_next_marked_addr(start, ntams);
241 while (start < ntams) {
242 oop obj = oop(start);
243 size_t obj_size = obj->size();
244 HeapWord* obj_end = start + obj_size;
245
246 assert(obj_end <= hr->end(), "Humongous objects must have been handled elsewhere.");
247
248 mark_card_bitmap_range(start, obj_end);
249
250 // Add the size of this object to the number of marked bytes.
251 marked_bytes += obj_size * HeapWordSize;
252
253 // Find the next marked object after this one.
254 start = mark_bitmap->get_next_marked_addr(obj_end, ntams);
255 }
256
257 return marked_bytes;
258 }
259
260 G1CardLiveDataHelper(G1CardLiveData* live_data, HeapWord* base_address) :
261 _region_bm(live_data->live_regions_bm()),
262 _card_bm(live_data->live_cards_bm()) {
263 // Calculate the card number for the bottom of the heap. Used
264 // in biasing indexes into the accounting card bitmaps.
265 _heap_card_bias =
266 uintptr_t(base_address) >> G1CardTable::card_shift;
267 }
268 };
269
270 class G1CreateCardLiveDataTask: public AbstractGangTask {
271 // Aggregate the counting data that was constructed concurrently
272 // with marking.
273 class G1CreateLiveDataClosure : public HeapRegionClosure {
274 G1CardLiveDataHelper _helper;
275
276 G1CMBitMap* _mark_bitmap;
277
278 G1ConcurrentMark* _cm;
279 public:
280 G1CreateLiveDataClosure(G1CollectedHeap* g1h,
281 G1ConcurrentMark* cm,
282 G1CMBitMap* mark_bitmap,
283 G1CardLiveData* live_data) :
284 HeapRegionClosure(),
285 _helper(live_data, g1h->reserved_region().start()),
286 _mark_bitmap(mark_bitmap),
287 _cm(cm) { }
288
289 bool do_heap_region(HeapRegion* hr) {
290 size_t marked_bytes = _helper.mark_marked_during_marking(_mark_bitmap, hr);
291 if (marked_bytes > 0) {
292 hr->add_to_marked_bytes(marked_bytes);
293 }
294
295 return (_cm->do_yield_check() && _cm->has_aborted());
296 }
297 };
298
299 G1ConcurrentMark* _cm;
300 G1CardLiveData* _live_data;
301 HeapRegionClaimer _hr_claimer;
302
303 public:
304 G1CreateCardLiveDataTask(G1CMBitMap* bitmap,
305 G1CardLiveData* live_data,
306 uint n_workers) :
307 AbstractGangTask("G1 Create Live Data"),
308 _live_data(live_data),
309 _hr_claimer(n_workers) {
310 }
311
312 void work(uint worker_id) {
313 SuspendibleThreadSetJoiner sts_join;
314
315 G1CollectedHeap* g1h = G1CollectedHeap::heap();
316 G1ConcurrentMark* cm = g1h->concurrent_mark();
317 G1CreateLiveDataClosure cl(g1h, cm, cm->next_mark_bitmap(), _live_data);
318 g1h->heap_region_par_iterate_from_worker_offset(&cl, &_hr_claimer, worker_id);
319 }
320 };
321
322 void G1CardLiveData::create(WorkGang* workers, G1CMBitMap* mark_bitmap) {
323 _gc_timestamp_at_create = G1CollectedHeap::heap()->get_gc_time_stamp();
324
325 uint n_workers = workers->active_workers();
326
327 G1CreateCardLiveDataTask cl(mark_bitmap,
328 this,
329 n_workers);
330 workers->run_task(&cl);
331 }
332
333 class G1FinalizeCardLiveDataTask: public AbstractGangTask {
334 // Finalizes the liveness counting data.
335 // Sets the bits corresponding to the interval [NTAMS, top]
336 // (which contains the implicitly live objects) in the
337 // card liveness bitmap. Also sets the bit for each region
338 // containing live data, in the region liveness bitmap.
339 class G1FinalizeCardLiveDataClosure: public HeapRegionClosure {
340 private:
341 G1CardLiveDataHelper _helper;
342
343 uint _gc_timestamp_at_create;
344
345 bool has_been_reclaimed(HeapRegion* hr) const {
346 return hr->get_gc_time_stamp() > _gc_timestamp_at_create;
347 }
348 public:
349 G1FinalizeCardLiveDataClosure(G1CollectedHeap* g1h,
350 G1CMBitMap* bitmap,
351 G1CardLiveData* live_data) :
352 HeapRegionClosure(),
353 _helper(live_data, g1h->reserved_region().start()),
354 _gc_timestamp_at_create(live_data->gc_timestamp_at_create()) { }
355
356 bool do_heap_region(HeapRegion* hr) {
357 if (has_been_reclaimed(hr)) {
358 _helper.reset_live_data(hr);
359 }
360 bool allocated_since_marking = _helper.mark_allocated_since_marking(hr);
361 if (allocated_since_marking || hr->next_marked_bytes() > 0) {
362 _helper.set_bit_for_region(hr);
363 }
364 return false;
365 }
366 };
367
368 G1CMBitMap* _bitmap;
369
370 G1CardLiveData* _live_data;
371
372 HeapRegionClaimer _hr_claimer;
373
374 public:
375 G1FinalizeCardLiveDataTask(G1CMBitMap* bitmap, G1CardLiveData* live_data, uint n_workers) :
376 AbstractGangTask("G1 Finalize Card Live Data"),
377 _bitmap(bitmap),
378 _live_data(live_data),
379 _hr_claimer(n_workers) {
380 }
381
382 void work(uint worker_id) {
383 G1FinalizeCardLiveDataClosure cl(G1CollectedHeap::heap(), _bitmap, _live_data);
384
385 G1CollectedHeap::heap()->heap_region_par_iterate_from_worker_offset(&cl, &_hr_claimer, worker_id);
386 }
387 };
388
389 void G1CardLiveData::finalize(WorkGang* workers, G1CMBitMap* mark_bitmap) {
390 // Finalize the live data.
391 G1FinalizeCardLiveDataTask cl(mark_bitmap,
392 this,
393 workers->active_workers());
394 workers->run_task(&cl);
395 }
396
397 class G1ClearCardLiveDataTask : public AbstractGangTask {
398 BitMapView _bitmap;
399 size_t _num_chunks;
400 size_t _cur_chunk;
401 public:
402 G1ClearCardLiveDataTask(const BitMapView& bitmap, size_t num_tasks) :
403 AbstractGangTask("G1 Clear Card Live Data"),
404 _bitmap(bitmap),
405 _num_chunks(num_tasks),
406 _cur_chunk(0) {
407 }
408
409 static size_t chunk_size() { return M; }
410
411 virtual void work(uint worker_id) {
412 while (true) {
413 size_t to_process = Atomic::add(1u, &_cur_chunk) - 1;
414 if (to_process >= _num_chunks) {
415 break;
416 }
417
418 BitMap::idx_t start = M * BitsPerByte * to_process;
419 BitMap::idx_t end = MIN2(start + M * BitsPerByte, _bitmap.size());
420 _bitmap.clear_range(start, end);
421 }
422 }
423 };
424
425 void G1CardLiveData::clear(WorkGang* workers) {
426 guarantee(Universe::is_fully_initialized(), "Should not call this during initialization.");
427
428 size_t const num_chunks = align_up(live_cards_bm().size_in_bytes(), G1ClearCardLiveDataTask::chunk_size()) / G1ClearCardLiveDataTask::chunk_size();
429 uint const num_workers = (uint)MIN2(num_chunks, (size_t)workers->active_workers());
430
431 G1ClearCardLiveDataTask cl(live_cards_bm(), num_chunks);
432
433 log_debug(gc, ergo)("Running %s using %u workers for " SIZE_FORMAT " work units.", cl.name(), num_workers, num_chunks);
434 workers->run_task(&cl, num_workers);
435
436 // The region live bitmap is always very small, even for huge heaps. Clear
437 // directly.
438 live_regions_bm().clear();
439 }
440
441 class G1VerifyCardLiveDataTask: public AbstractGangTask {
442 // Heap region closure used for verifying the live count data
443 // that was created concurrently and finalized during
444 // the remark pause. This closure is applied to the heap
445 // regions during the STW cleanup pause.
446 class G1VerifyCardLiveDataClosure: public HeapRegionClosure {
447 private:
448 G1CollectedHeap* _g1h;
449 G1CMBitMap* _mark_bitmap;
450 G1CardLiveDataHelper _helper;
451
452 G1CardLiveData* _act_live_data;
453
454 G1CardLiveData* _exp_live_data;
455
456 int _failures;
457
458 // Completely recreates the live data count for the given heap region and
459 // returns the number of bytes marked.
460 size_t create_live_data_count(HeapRegion* hr) {
461 size_t bytes_marked = _helper.mark_marked_during_marking(_mark_bitmap, hr);
462 bool allocated_since_marking = _helper.mark_allocated_since_marking(hr);
463 if (allocated_since_marking || bytes_marked > 0) {
464 _helper.set_bit_for_region(hr);
465 }
466 return bytes_marked;
467 }
468 public:
469 G1VerifyCardLiveDataClosure(G1CollectedHeap* g1h,
470 G1CMBitMap* mark_bitmap,
471 G1CardLiveData* act_live_data,
472 G1CardLiveData* exp_live_data) :
473 _g1h(g1h),
474 _mark_bitmap(mark_bitmap),
475 _helper(exp_live_data, g1h->reserved_region().start()),
476 _act_live_data(act_live_data),
477 _exp_live_data(exp_live_data),
478 _failures(0) { }
479
480 int failures() const { return _failures; }
481
482 bool do_heap_region(HeapRegion* hr) {
483 int failures = 0;
484
485 // Walk the marking bitmap for this region and set the corresponding bits
486 // in the expected region and card bitmaps.
487 size_t exp_marked_bytes = create_live_data_count(hr);
488 size_t act_marked_bytes = hr->next_marked_bytes();
489 // Verify the marked bytes for this region.
490
491 if (exp_marked_bytes != act_marked_bytes) {
492 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());
493 failures += 1;
494 } else if (exp_marked_bytes > HeapRegion::GrainBytes) {
495 log_error(gc)("Expected marked bytes " SIZE_FORMAT " larger than possible " SIZE_FORMAT " in region %u", exp_marked_bytes, HeapRegion::GrainBytes, hr->hrm_index());
496 failures += 1;
497 }
498
499 // Verify the bit, for this region, in the actual and expected
500 // (which was just calculated) region bit maps.
501 uint index = hr->hrm_index();
502
503 bool expected = _exp_live_data->is_region_live(index);
504 bool actual = _act_live_data->is_region_live(index);
505 if (expected != actual) {
506 log_error(gc)("Expected liveness %d not equal actual %d in region %u", expected, actual, hr->hrm_index());
507 failures += 1;
508 }
509
510 // Verify that the card bit maps for the cards spanned by the current
511 // region match.
512 BitMap::idx_t start_idx = _helper.card_live_bitmap_index_for(hr->bottom());
513 BitMap::idx_t end_idx = _helper.card_live_bitmap_index_for(hr->top());
514
515 for (BitMap::idx_t i = start_idx; i < end_idx; i+=1) {
516 expected = _exp_live_data->is_card_live_at(i);
517 actual = _act_live_data->is_card_live_at(i);
518
519 if (expected != actual) {
520 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());
521 failures += 1;
522 }
523 }
524
525 _failures += failures;
526
527 // We could stop iteration over the heap when we
528 // find the first violating region by returning true.
529 return false;
530 }
531 };
532 protected:
533 G1CollectedHeap* _g1h;
534 G1CMBitMap* _mark_bitmap;
535
536 G1CardLiveData* _act_live_data;
537
538 G1CardLiveData _exp_live_data;
539
540 int _failures;
541
542 HeapRegionClaimer _hr_claimer;
543
544 public:
545 G1VerifyCardLiveDataTask(G1CMBitMap* bitmap,
546 G1CardLiveData* act_live_data,
547 uint n_workers)
548 : AbstractGangTask("G1 Verify Card Live Data"),
549 _g1h(G1CollectedHeap::heap()),
550 _mark_bitmap(bitmap),
551 _act_live_data(act_live_data),
552 _exp_live_data(),
553 _failures(0),
554 _hr_claimer(n_workers) {
555 assert(VerifyDuringGC, "don't call this otherwise");
556 _exp_live_data.initialize(_g1h->max_capacity(), _g1h->max_regions());
557 }
558
559 void work(uint worker_id) {
560 G1VerifyCardLiveDataClosure cl(_g1h,
561 _mark_bitmap,
562 _act_live_data,
563 &_exp_live_data);
564 _g1h->heap_region_par_iterate_from_worker_offset(&cl, &_hr_claimer, worker_id);
565
566 Atomic::add(cl.failures(), &_failures);
567 }
568
569 int failures() const { return _failures; }
570 };
571
572 void G1CardLiveData::verify(WorkGang* workers, G1CMBitMap* actual_bitmap) {
573 ResourceMark rm;
574
575 G1VerifyCardLiveDataTask cl(actual_bitmap,
576 this,
577 workers->active_workers());
578 workers->run_task(&cl);
579
580 guarantee(cl.failures() == 0, "Unexpected accounting failures");
581 }
582
583 #ifndef PRODUCT
584 void G1CardLiveData::verify_is_clear() {
585 assert(live_cards_bm().count_one_bits() == 0, "Live cards bitmap must be clear.");
586 assert(live_regions_bm().count_one_bits() == 0, "Live regions bitmap must be clear.");
587 }
588 #endif