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