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 "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) { 63 MmapArrayAllocator<bm_word_t, mtGC>::free(bitmap, size_in_bits / BitsPerWord); 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 BitMap _region_bm; 99 BitMap _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 mark_card_bitmap_range(start, hr->top()); 223 return pointer_delta(hr->top(), start, 1); 224 } 225 226 assert(start <= hr->end() && start <= ntams && ntams <= hr->end(), 227 "Preconditions not met - " 228 "start: " PTR_FORMAT ", ntams: " PTR_FORMAT ", end: " PTR_FORMAT, 229 p2i(start), p2i(ntams), p2i(hr->end())); 230 231 // Find the first marked object at or after "start". 232 start = mark_bitmap->getNextMarkedWordAddress(start, ntams); 233 while (start < ntams) { 234 oop obj = oop(start); 235 size_t obj_size = obj->size(); 236 HeapWord* obj_end = start + obj_size; 237 238 assert(obj_end <= hr->end(), "Humongous objects must have been handled elsewhere."); 239 240 mark_card_bitmap_range(start, obj_end); 241 242 // Add the size of this object to the number of marked bytes. 243 marked_bytes += obj_size * HeapWordSize; 244 245 // Find the next marked object after this one. 246 start = mark_bitmap->getNextMarkedWordAddress(obj_end, ntams); 247 } 248 249 return marked_bytes; 250 } 251 252 G1CardLiveDataHelper(G1CardLiveData* live_data, HeapWord* base_address) : 253 _region_bm(live_data->live_regions_bm()), 254 _card_bm(live_data->live_cards_bm()) { 255 // Calculate the card number for the bottom of the heap. Used 256 // in biasing indexes into the accounting card bitmaps. 257 _heap_card_bias = 258 uintptr_t(base_address) >> CardTableModRefBS::card_shift; 259 } 260 }; 261 262 class G1CreateCardLiveDataTask: public AbstractGangTask { 263 // Aggregate the counting data that was constructed concurrently 264 // with marking. 265 class G1CreateLiveDataClosure : public HeapRegionClosure { 266 G1CardLiveDataHelper _helper; 267 268 G1CMBitMap* _mark_bitmap; 269 270 G1ConcurrentMark* _cm; 271 public: 272 G1CreateLiveDataClosure(G1CollectedHeap* g1h, 273 G1ConcurrentMark* cm, 274 G1CMBitMap* mark_bitmap, 275 G1CardLiveData* live_data) : 276 HeapRegionClosure(), 277 _helper(live_data, g1h->reserved_region().start()), 278 _mark_bitmap(mark_bitmap), 279 _cm(cm) { } 280 281 bool doHeapRegion(HeapRegion* hr) { 282 size_t marked_bytes = _helper.mark_marked_during_marking(_mark_bitmap, hr); 283 if (marked_bytes > 0) { 284 hr->add_to_marked_bytes(marked_bytes); 285 } 286 287 return (_cm->do_yield_check() && _cm->has_aborted()); 288 } 289 }; 290 291 G1ConcurrentMark* _cm; 292 G1CardLiveData* _live_data; 293 HeapRegionClaimer _hr_claimer; 294 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) { 372 } 373 374 void work(uint worker_id) { 375 G1FinalizeCardLiveDataClosure cl(G1CollectedHeap::heap(), _bitmap, _live_data); 376 377 G1CollectedHeap::heap()->heap_region_par_iterate(&cl, worker_id, &_hr_claimer); 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 BitMap _bitmap; 391 size_t _num_chunks; 392 size_t _cur_chunk; 393 public: 394 G1ClearCardLiveDataTask(BitMap 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 422 G1ClearCardLiveDataTask cl(live_cards_bm(), num_chunks); 423 workers->run_task(&cl); 424 425 // The region live bitmap is always very small, even for huge heaps. Clear 426 // directly. 427 live_regions_bm().clear(); 428 } 429 430 class G1VerifyCardLiveDataTask: public AbstractGangTask { 431 // Heap region closure used for verifying the live count data 432 // that was created concurrently and finalized during 433 // the remark pause. This closure is applied to the heap 434 // regions during the STW cleanup pause. 435 class G1VerifyCardLiveDataClosure: public HeapRegionClosure { 436 private: 437 G1CollectedHeap* _g1h; 438 G1CMBitMap* _mark_bitmap; 439 G1CardLiveDataHelper _helper; 440 441 G1CardLiveData* _act_live_data; 442 443 G1CardLiveData* _exp_live_data; 444 445 int _failures; 446 447 // Completely recreates the live data count for the given heap region and 448 // returns the number of bytes marked. 449 size_t create_live_data_count(HeapRegion* hr) { 450 size_t bytes_marked = _helper.mark_marked_during_marking(_mark_bitmap, hr); 451 bool allocated_since_marking = _helper.mark_allocated_since_marking(hr); 452 if (allocated_since_marking || bytes_marked > 0) { 453 _helper.set_bit_for_region(hr); 454 } 455 return bytes_marked; 456 } 457 public: 458 G1VerifyCardLiveDataClosure(G1CollectedHeap* g1h, 459 G1CMBitMap* mark_bitmap, 460 G1CardLiveData* act_live_data, 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; 534 535 HeapRegionClaimer _hr_claimer; 536 537 public: 538 G1VerifyCardLiveDataTask(G1CMBitMap* bitmap, 539 G1CardLiveData* act_live_data, 540 uint n_workers) 541 : AbstractGangTask("G1 Verify Card Live Data"), 542 _g1h(G1CollectedHeap::heap()), 543 _mark_bitmap(bitmap), 544 _act_live_data(act_live_data), 545 _exp_live_data(), 546 _failures(0), 547 _hr_claimer(n_workers) { 548 assert(VerifyDuringGC, "don't call this otherwise"); 549 _exp_live_data.initialize(_g1h->max_capacity(), _g1h->max_regions()); 550 } 551 552 void work(uint worker_id) { 553 G1VerifyCardLiveDataClosure cl(_g1h, 554 _mark_bitmap, 555 _act_live_data, 556 &_exp_live_data); 557 _g1h->heap_region_par_iterate(&cl, worker_id, &_hr_claimer); 558 559 Atomic::add(cl.failures(), &_failures); 560 } 561 562 int failures() const { return _failures; } 563 }; 564 565 void G1CardLiveData::verify(WorkGang* workers, G1CMBitMap* actual_bitmap) { 566 ResourceMark rm; 567 568 G1VerifyCardLiveDataTask cl(actual_bitmap, 569 this, 570 workers->active_workers()); 571 workers->run_task(&cl); 572 573 guarantee(cl.failures() == 0, "Unexpected accounting failures"); 574 } 575 576 #ifndef PRODUCT 577 void G1CardLiveData::verify_is_clear() { 578 assert(live_cards_bm().count_one_bits() == 0, "Live cards bitmap must be clear."); 579 assert(live_regions_bm().count_one_bits() == 0, "Live regions bitmap must be clear."); 580 } 581 #endif