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