1 /*
   2  * Copyright (c) 2001, 2014, 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 "code/nmethod.hpp"
  27 #include "gc_implementation/g1/g1BlockOffsetTable.inline.hpp"
  28 #include "gc_implementation/g1/g1CollectedHeap.inline.hpp"
  29 #include "gc_implementation/g1/g1OopClosures.inline.hpp"
  30 #include "gc_implementation/g1/heapRegion.inline.hpp"
  31 #include "gc_implementation/g1/heapRegionRemSet.hpp"
  32 #include "gc_implementation/g1/heapRegionSeq.inline.hpp"
  33 #include "memory/genOopClosures.inline.hpp"
  34 #include "memory/iterator.hpp"
  35 #include "memory/space.inline.hpp"
  36 #include "oops/oop.inline.hpp"
  37 #include "runtime/orderAccess.inline.hpp"
  38 
  39 PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC
  40 
  41 int    HeapRegion::LogOfHRGrainBytes = 0;
  42 int    HeapRegion::LogOfHRGrainWords = 0;
  43 size_t HeapRegion::GrainBytes        = 0;
  44 size_t HeapRegion::GrainWords        = 0;
  45 size_t HeapRegion::CardsPerRegion    = 0;
  46 
  47 HeapRegionDCTOC::HeapRegionDCTOC(G1CollectedHeap* g1,
  48                                  HeapRegion* hr, ExtendedOopClosure* cl,
  49                                  CardTableModRefBS::PrecisionStyle precision,
  50                                  FilterKind fk) :
  51   DirtyCardToOopClosure(hr, cl, precision, NULL),
  52   _hr(hr), _fk(fk), _g1(g1) { }
  53 
  54 FilterOutOfRegionClosure::FilterOutOfRegionClosure(HeapRegion* r,
  55                                                    OopClosure* oc) :
  56   _r_bottom(r->bottom()), _r_end(r->end()), _oc(oc) { }
  57 
  58 template<class ClosureType>
  59 HeapWord* walk_mem_region_loop(ClosureType* cl, G1CollectedHeap* g1h,
  60                                HeapRegion* hr,
  61                                HeapWord* cur, HeapWord* top) {
  62   oop cur_oop = oop(cur);
  63   int oop_size = cur_oop->size();
  64   HeapWord* next_obj = cur + oop_size;
  65   while (next_obj < top) {
  66     // Keep filtering the remembered set.
  67     if (!g1h->is_obj_dead(cur_oop, hr)) {
  68       // Bottom lies entirely below top, so we can call the
  69       // non-memRegion version of oop_iterate below.
  70       cur_oop->oop_iterate(cl);
  71     }
  72     cur = next_obj;
  73     cur_oop = oop(cur);
  74     oop_size = cur_oop->size();
  75     next_obj = cur + oop_size;
  76   }
  77   return cur;
  78 }
  79 
  80 void HeapRegionDCTOC::walk_mem_region(MemRegion mr,
  81                                       HeapWord* bottom,
  82                                       HeapWord* top) {
  83   G1CollectedHeap* g1h = _g1;
  84   int oop_size;
  85   ExtendedOopClosure* cl2 = NULL;
  86 
  87   FilterIntoCSClosure intoCSFilt(this, g1h, _cl);
  88   FilterOutOfRegionClosure outOfRegionFilt(_hr, _cl);
  89 
  90   switch (_fk) {
  91   case NoFilterKind:          cl2 = _cl; break;
  92   case IntoCSFilterKind:      cl2 = &intoCSFilt; break;
  93   case OutOfRegionFilterKind: cl2 = &outOfRegionFilt; break;
  94   default:                    ShouldNotReachHere();
  95   }
  96 
  97   // Start filtering what we add to the remembered set. If the object is
  98   // not considered dead, either because it is marked (in the mark bitmap)
  99   // or it was allocated after marking finished, then we add it. Otherwise
 100   // we can safely ignore the object.
 101   if (!g1h->is_obj_dead(oop(bottom), _hr)) {
 102     oop_size = oop(bottom)->oop_iterate(cl2, mr);
 103   } else {
 104     oop_size = oop(bottom)->size();
 105   }
 106 
 107   bottom += oop_size;
 108 
 109   if (bottom < top) {
 110     // We replicate the loop below for several kinds of possible filters.
 111     switch (_fk) {
 112     case NoFilterKind:
 113       bottom = walk_mem_region_loop(_cl, g1h, _hr, bottom, top);
 114       break;
 115 
 116     case IntoCSFilterKind: {
 117       FilterIntoCSClosure filt(this, g1h, _cl);
 118       bottom = walk_mem_region_loop(&filt, g1h, _hr, bottom, top);
 119       break;
 120     }
 121 
 122     case OutOfRegionFilterKind: {
 123       FilterOutOfRegionClosure filt(_hr, _cl);
 124       bottom = walk_mem_region_loop(&filt, g1h, _hr, bottom, top);
 125       break;
 126     }
 127 
 128     default:
 129       ShouldNotReachHere();
 130     }
 131 
 132     // Last object. Need to do dead-obj filtering here too.
 133     if (!g1h->is_obj_dead(oop(bottom), _hr)) {
 134       oop(bottom)->oop_iterate(cl2, mr);
 135     }
 136   }
 137 }
 138 
 139 // Minimum region size; we won't go lower than that.
 140 // We might want to decrease this in the future, to deal with small
 141 // heaps a bit more efficiently.
 142 #define MIN_REGION_SIZE  (      1024 * 1024 )
 143 
 144 // Maximum region size; we don't go higher than that. There's a good
 145 // reason for having an upper bound. We don't want regions to get too
 146 // large, otherwise cleanup's effectiveness would decrease as there
 147 // will be fewer opportunities to find totally empty regions after
 148 // marking.
 149 #define MAX_REGION_SIZE  ( 32 * 1024 * 1024 )
 150 
 151 // The automatic region size calculation will try to have around this
 152 // many regions in the heap (based on the min heap size).
 153 #define TARGET_REGION_NUMBER          2048
 154 
 155 size_t HeapRegion::max_region_size() {
 156   return (size_t)MAX_REGION_SIZE;
 157 }
 158 
 159 void HeapRegion::setup_heap_region_size(size_t initial_heap_size, size_t max_heap_size) {
 160   uintx region_size = G1HeapRegionSize;
 161   if (FLAG_IS_DEFAULT(G1HeapRegionSize)) {
 162     size_t average_heap_size = (initial_heap_size + max_heap_size) / 2;
 163     region_size = MAX2(average_heap_size / TARGET_REGION_NUMBER,
 164                        (uintx) MIN_REGION_SIZE);
 165   }
 166 
 167   int region_size_log = log2_long((jlong) region_size);
 168   // Recalculate the region size to make sure it's a power of
 169   // 2. This means that region_size is the largest power of 2 that's
 170   // <= what we've calculated so far.
 171   region_size = ((uintx)1 << region_size_log);
 172 
 173   // Now make sure that we don't go over or under our limits.
 174   if (region_size < MIN_REGION_SIZE) {
 175     region_size = MIN_REGION_SIZE;
 176   } else if (region_size > MAX_REGION_SIZE) {
 177     region_size = MAX_REGION_SIZE;
 178   }
 179 
 180   // And recalculate the log.
 181   region_size_log = log2_long((jlong) region_size);
 182 
 183   // Now, set up the globals.
 184   guarantee(LogOfHRGrainBytes == 0, "we should only set it once");
 185   LogOfHRGrainBytes = region_size_log;
 186 
 187   guarantee(LogOfHRGrainWords == 0, "we should only set it once");
 188   LogOfHRGrainWords = LogOfHRGrainBytes - LogHeapWordSize;
 189 
 190   guarantee(GrainBytes == 0, "we should only set it once");
 191   // The cast to int is safe, given that we've bounded region_size by
 192   // MIN_REGION_SIZE and MAX_REGION_SIZE.
 193   GrainBytes = (size_t)region_size;
 194 
 195   guarantee(GrainWords == 0, "we should only set it once");
 196   GrainWords = GrainBytes >> LogHeapWordSize;
 197   guarantee((size_t) 1 << LogOfHRGrainWords == GrainWords, "sanity");
 198 
 199   guarantee(CardsPerRegion == 0, "we should only set it once");
 200   CardsPerRegion = GrainBytes >> CardTableModRefBS::card_shift;
 201 }
 202 
 203 void HeapRegion::reset_after_compaction() {
 204   G1OffsetTableContigSpace::reset_after_compaction();
 205   // After a compaction the mark bitmap is invalid, so we must
 206   // treat all objects as being inside the unmarked area.
 207   zero_marked_bytes();
 208   init_top_at_mark_start();
 209 }
 210 
 211 void HeapRegion::hr_clear(bool par, bool clear_space, bool locked) {
 212   assert(_humongous_type == NotHumongous,
 213          "we should have already filtered out humongous regions");
 214   assert(_humongous_start_region == NULL,
 215          "we should have already filtered out humongous regions");
 216   assert(_end == _orig_end,
 217          "we should have already filtered out humongous regions");
 218 
 219   _in_collection_set = false;
 220 
 221   set_young_index_in_cset(-1);
 222   uninstall_surv_rate_group();
 223   set_young_type(NotYoung);
 224   reset_pre_dummy_top();
 225 
 226   if (!par) {
 227     // If this is parallel, this will be done later.
 228     HeapRegionRemSet* hrrs = rem_set();
 229     if (locked) {
 230       hrrs->clear_locked();
 231     } else {
 232       hrrs->clear();
 233     }
 234     _claimed = InitialClaimValue;
 235   }
 236   zero_marked_bytes();
 237 
 238   _offsets.resize(HeapRegion::GrainWords);
 239   init_top_at_mark_start();
 240   if (clear_space) clear(SpaceDecorator::Mangle);
 241 }
 242 
 243 void HeapRegion::par_clear() {
 244   assert(used() == 0, "the region should have been already cleared");
 245   assert(capacity() == HeapRegion::GrainBytes, "should be back to normal");
 246   HeapRegionRemSet* hrrs = rem_set();
 247   hrrs->clear();
 248   CardTableModRefBS* ct_bs =
 249                    (CardTableModRefBS*)G1CollectedHeap::heap()->barrier_set();
 250   ct_bs->clear(MemRegion(bottom(), end()));
 251 }
 252 
 253 void HeapRegion::calc_gc_efficiency() {
 254   // GC efficiency is the ratio of how much space would be
 255   // reclaimed over how long we predict it would take to reclaim it.
 256   G1CollectedHeap* g1h = G1CollectedHeap::heap();
 257   G1CollectorPolicy* g1p = g1h->g1_policy();
 258 
 259   // Retrieve a prediction of the elapsed time for this region for
 260   // a mixed gc because the region will only be evacuated during a
 261   // mixed gc.
 262   double region_elapsed_time_ms =
 263     g1p->predict_region_elapsed_time_ms(this, false /* for_young_gc */);
 264   _gc_efficiency = (double) reclaimable_bytes() / region_elapsed_time_ms;
 265 }
 266 
 267 void HeapRegion::set_startsHumongous(HeapWord* new_top, HeapWord* new_end) {
 268   assert(!isHumongous(), "sanity / pre-condition");
 269   assert(end() == _orig_end,
 270          "Should be normal before the humongous object allocation");
 271   assert(top() == bottom(), "should be empty");
 272   assert(bottom() <= new_top && new_top <= new_end, "pre-condition");
 273 
 274   _humongous_type = StartsHumongous;
 275   _humongous_start_region = this;
 276 
 277   set_end(new_end);
 278   _offsets.set_for_starts_humongous(new_top);
 279 }
 280 
 281 void HeapRegion::set_continuesHumongous(HeapRegion* first_hr) {
 282   assert(!isHumongous(), "sanity / pre-condition");
 283   assert(end() == _orig_end,
 284          "Should be normal before the humongous object allocation");
 285   assert(top() == bottom(), "should be empty");
 286   assert(first_hr->startsHumongous(), "pre-condition");
 287 
 288   _humongous_type = ContinuesHumongous;
 289   _humongous_start_region = first_hr;
 290 }
 291 
 292 void HeapRegion::set_notHumongous() {
 293   assert(isHumongous(), "pre-condition");
 294 
 295   if (startsHumongous()) {
 296     assert(top() <= end(), "pre-condition");
 297     set_end(_orig_end);
 298     if (top() > end()) {
 299       // at least one "continues humongous" region after it
 300       set_top(end());
 301     }
 302   } else {
 303     // continues humongous
 304     assert(end() == _orig_end, "sanity");
 305   }
 306 
 307   assert(capacity() == HeapRegion::GrainBytes, "pre-condition");
 308   _humongous_type = NotHumongous;
 309   _humongous_start_region = NULL;
 310 }
 311 
 312 bool HeapRegion::claimHeapRegion(jint claimValue) {
 313   jint current = _claimed;
 314   if (current != claimValue) {
 315     jint res = Atomic::cmpxchg(claimValue, &_claimed, current);
 316     if (res == current) {
 317       return true;
 318     }
 319   }
 320   return false;
 321 }
 322 
 323 HeapWord* HeapRegion::next_block_start_careful(HeapWord* addr) {
 324   HeapWord* low = addr;
 325   HeapWord* high = end();
 326   while (low < high) {
 327     size_t diff = pointer_delta(high, low);
 328     // Must add one below to bias toward the high amount.  Otherwise, if
 329   // "high" were at the desired value, and "low" were one less, we
 330     // would not converge on "high".  This is not symmetric, because
 331     // we set "high" to a block start, which might be the right one,
 332     // which we don't do for "low".
 333     HeapWord* middle = low + (diff+1)/2;
 334     if (middle == high) return high;
 335     HeapWord* mid_bs = block_start_careful(middle);
 336     if (mid_bs < addr) {
 337       low = middle;
 338     } else {
 339       high = mid_bs;
 340     }
 341   }
 342   assert(low == high && low >= addr, "Didn't work.");
 343   return low;
 344 }
 345 
 346 #ifdef _MSC_VER // the use of 'this' below gets a warning, make it go away
 347 #pragma warning( disable:4355 ) // 'this' : used in base member initializer list
 348 #endif // _MSC_VER
 349 
 350 
 351 HeapRegion::HeapRegion(uint hrs_index,
 352                        G1BlockOffsetSharedArray* sharedOffsetArray,
 353                        MemRegion mr) :
 354     G1OffsetTableContigSpace(sharedOffsetArray, mr),
 355     _hrs_index(hrs_index),
 356     _humongous_type(NotHumongous), _humongous_start_region(NULL),
 357     _in_collection_set(false),
 358     _next_in_special_set(NULL), _orig_end(NULL),
 359     _claimed(InitialClaimValue), _evacuation_failed(false),
 360     _prev_marked_bytes(0), _next_marked_bytes(0), _gc_efficiency(0.0),
 361     _young_type(NotYoung), _next_young_region(NULL),
 362     _next_dirty_cards_region(NULL), _next(NULL), _prev(NULL), _pending_removal(false),
 363 #ifdef ASSERT
 364     _containing_set(NULL),
 365 #endif // ASSERT
 366      _young_index_in_cset(-1), _surv_rate_group(NULL), _age_index(-1),
 367     _rem_set(NULL), _recorded_rs_length(0), _predicted_elapsed_time_ms(0),
 368     _predicted_bytes_to_copy(0)
 369 {
 370   _rem_set = new HeapRegionRemSet(sharedOffsetArray, this);
 371   _orig_end = mr.end();
 372   // Note that initialize() will set the start of the unmarked area of the
 373   // region.
 374   hr_clear(false /*par*/, false /*clear_space*/);
 375   set_top(bottom());
 376   set_saved_mark();
 377 
 378   assert(HeapRegionRemSet::num_par_rem_sets() > 0, "Invariant.");
 379 }
 380 
 381 CompactibleSpace* HeapRegion::next_compaction_space() const {
 382   // We're not using an iterator given that it will wrap around when
 383   // it reaches the last region and this is not what we want here.
 384   G1CollectedHeap* g1h = G1CollectedHeap::heap();
 385   uint index = hrs_index() + 1;
 386   while (index < g1h->n_regions()) {
 387     HeapRegion* hr = g1h->region_at(index);
 388     if (!hr->isHumongous()) {
 389       return hr;
 390     }
 391     index += 1;
 392   }
 393   return NULL;
 394 }
 395 
 396 void HeapRegion::save_marks() {
 397   set_saved_mark();
 398 }
 399 
 400 void HeapRegion::oops_in_mr_iterate(MemRegion mr, ExtendedOopClosure* cl) {
 401   HeapWord* p = mr.start();
 402   HeapWord* e = mr.end();
 403   oop obj;
 404   while (p < e) {
 405     obj = oop(p);
 406     p += obj->oop_iterate(cl);
 407   }
 408   assert(p == e, "bad memregion: doesn't end on obj boundary");
 409 }
 410 
 411 #define HeapRegion_OOP_SINCE_SAVE_MARKS_DEFN(OopClosureType, nv_suffix) \
 412 void HeapRegion::oop_since_save_marks_iterate##nv_suffix(OopClosureType* cl) { \
 413   ContiguousSpace::oop_since_save_marks_iterate##nv_suffix(cl);              \
 414 }
 415 SPECIALIZED_SINCE_SAVE_MARKS_CLOSURES(HeapRegion_OOP_SINCE_SAVE_MARKS_DEFN)
 416 
 417 
 418 void HeapRegion::oop_before_save_marks_iterate(ExtendedOopClosure* cl) {
 419   oops_in_mr_iterate(MemRegion(bottom(), saved_mark_word()), cl);
 420 }
 421 
 422 void HeapRegion::note_self_forwarding_removal_start(bool during_initial_mark,
 423                                                     bool during_conc_mark) {
 424   // We always recreate the prev marking info and we'll explicitly
 425   // mark all objects we find to be self-forwarded on the prev
 426   // bitmap. So all objects need to be below PTAMS.
 427   _prev_top_at_mark_start = top();
 428   _prev_marked_bytes = 0;
 429 
 430   if (during_initial_mark) {
 431     // During initial-mark, we'll also explicitly mark all objects
 432     // we find to be self-forwarded on the next bitmap. So all
 433     // objects need to be below NTAMS.
 434     _next_top_at_mark_start = top();
 435     _next_marked_bytes = 0;
 436   } else if (during_conc_mark) {
 437     // During concurrent mark, all objects in the CSet (including
 438     // the ones we find to be self-forwarded) are implicitly live.
 439     // So all objects need to be above NTAMS.
 440     _next_top_at_mark_start = bottom();
 441     _next_marked_bytes = 0;
 442   }
 443 }
 444 
 445 void HeapRegion::note_self_forwarding_removal_end(bool during_initial_mark,
 446                                                   bool during_conc_mark,
 447                                                   size_t marked_bytes) {
 448   assert(0 <= marked_bytes && marked_bytes <= used(),
 449          err_msg("marked: "SIZE_FORMAT" used: "SIZE_FORMAT,
 450                  marked_bytes, used()));
 451   _prev_marked_bytes = marked_bytes;
 452 }
 453 
 454 HeapWord*
 455 HeapRegion::object_iterate_mem_careful(MemRegion mr,
 456                                                  ObjectClosure* cl) {
 457   G1CollectedHeap* g1h = G1CollectedHeap::heap();
 458   // We used to use "block_start_careful" here.  But we're actually happy
 459   // to update the BOT while we do this...
 460   HeapWord* cur = block_start(mr.start());
 461   mr = mr.intersection(used_region());
 462   if (mr.is_empty()) return NULL;
 463   // Otherwise, find the obj that extends onto mr.start().
 464 
 465   assert(cur <= mr.start()
 466          && (oop(cur)->klass_or_null() == NULL ||
 467              cur + oop(cur)->size() > mr.start()),
 468          "postcondition of block_start");
 469   oop obj;
 470   while (cur < mr.end()) {
 471     obj = oop(cur);
 472     if (obj->klass_or_null() == NULL) {
 473       // Ran into an unparseable point.
 474       return cur;
 475     } else if (!g1h->is_obj_dead(obj)) {
 476       cl->do_object(obj);
 477     }
 478     cur += obj->size();
 479   }
 480   return NULL;
 481 }
 482 
 483 HeapWord*
 484 HeapRegion::
 485 oops_on_card_seq_iterate_careful(MemRegion mr,
 486                                  FilterOutOfRegionClosure* cl,
 487                                  bool filter_young,
 488                                  jbyte* card_ptr) {
 489   // Currently, we should only have to clean the card if filter_young
 490   // is true and vice versa.
 491   if (filter_young) {
 492     assert(card_ptr != NULL, "pre-condition");
 493   } else {
 494     assert(card_ptr == NULL, "pre-condition");
 495   }
 496   G1CollectedHeap* g1h = G1CollectedHeap::heap();
 497 
 498   // If we're within a stop-world GC, then we might look at a card in a
 499   // GC alloc region that extends onto a GC LAB, which may not be
 500   // parseable.  Stop such at the "saved_mark" of the region.
 501   if (g1h->is_gc_active()) {
 502     mr = mr.intersection(used_region_at_save_marks());
 503   } else {
 504     mr = mr.intersection(used_region());
 505   }
 506   if (mr.is_empty()) return NULL;
 507   // Otherwise, find the obj that extends onto mr.start().
 508 
 509   // The intersection of the incoming mr (for the card) and the
 510   // allocated part of the region is non-empty. This implies that
 511   // we have actually allocated into this region. The code in
 512   // G1CollectedHeap.cpp that allocates a new region sets the
 513   // is_young tag on the region before allocating. Thus we
 514   // safely know if this region is young.
 515   if (is_young() && filter_young) {
 516     return NULL;
 517   }
 518 
 519   assert(!is_young(), "check value of filter_young");
 520 
 521   // We can only clean the card here, after we make the decision that
 522   // the card is not young. And we only clean the card if we have been
 523   // asked to (i.e., card_ptr != NULL).
 524   if (card_ptr != NULL) {
 525     *card_ptr = CardTableModRefBS::clean_card_val();
 526     // We must complete this write before we do any of the reads below.
 527     OrderAccess::storeload();
 528   }
 529 
 530   // Cache the boundaries of the memory region in some const locals
 531   HeapWord* const start = mr.start();
 532   HeapWord* const end = mr.end();
 533 
 534   // We used to use "block_start_careful" here.  But we're actually happy
 535   // to update the BOT while we do this...
 536   HeapWord* cur = block_start(start);
 537   assert(cur <= start, "Postcondition");
 538 
 539   oop obj;
 540 
 541   HeapWord* next = cur;
 542   while (next <= start) {
 543     cur = next;
 544     obj = oop(cur);
 545     if (obj->klass_or_null() == NULL) {
 546       // Ran into an unparseable point.
 547       return cur;
 548     }
 549     // Otherwise...
 550     next = (cur + obj->size());
 551   }
 552 
 553   // If we finish the above loop...We have a parseable object that
 554   // begins on or before the start of the memory region, and ends
 555   // inside or spans the entire region.
 556 
 557   assert(obj == oop(cur), "sanity");
 558   assert(cur <= start &&
 559          obj->klass_or_null() != NULL &&
 560          (cur + obj->size()) > start,
 561          "Loop postcondition");
 562 
 563   if (!g1h->is_obj_dead(obj)) {
 564     obj->oop_iterate(cl, mr);
 565   }
 566 
 567   while (cur < end) {
 568     obj = oop(cur);
 569     if (obj->klass_or_null() == NULL) {
 570       // Ran into an unparseable point.
 571       return cur;
 572     };
 573 
 574     // Otherwise:
 575     next = (cur + obj->size());
 576 
 577     if (!g1h->is_obj_dead(obj)) {
 578       if (next < end || !obj->is_objArray()) {
 579         // This object either does not span the MemRegion
 580         // boundary, or if it does it's not an array.
 581         // Apply closure to whole object.
 582         obj->oop_iterate(cl);
 583       } else {
 584         // This obj is an array that spans the boundary.
 585         // Stop at the boundary.
 586         obj->oop_iterate(cl, mr);
 587       }
 588     }
 589     cur = next;
 590   }
 591   return NULL;
 592 }
 593 
 594 // Code roots support
 595 
 596 void HeapRegion::add_strong_code_root(nmethod* nm) {
 597   HeapRegionRemSet* hrrs = rem_set();
 598   hrrs->add_strong_code_root(nm);
 599 }
 600 
 601 void HeapRegion::remove_strong_code_root(nmethod* nm) {
 602   HeapRegionRemSet* hrrs = rem_set();
 603   hrrs->remove_strong_code_root(nm);
 604 }
 605 
 606 void HeapRegion::migrate_strong_code_roots() {
 607   assert(in_collection_set(), "only collection set regions");
 608   assert(!isHumongous(),
 609           err_msg("humongous region "HR_FORMAT" should not have been added to collection set",
 610                   HR_FORMAT_PARAMS(this)));
 611 
 612   HeapRegionRemSet* hrrs = rem_set();
 613   hrrs->migrate_strong_code_roots();
 614 }
 615 
 616 void HeapRegion::strong_code_roots_do(CodeBlobClosure* blk) const {
 617   HeapRegionRemSet* hrrs = rem_set();
 618   hrrs->strong_code_roots_do(blk);
 619 }
 620 
 621 class VerifyStrongCodeRootOopClosure: public OopClosure {
 622   const HeapRegion* _hr;
 623   nmethod* _nm;
 624   bool _failures;
 625   bool _has_oops_in_region;
 626 
 627   template <class T> void do_oop_work(T* p) {
 628     T heap_oop = oopDesc::load_heap_oop(p);
 629     if (!oopDesc::is_null(heap_oop)) {
 630       oop obj = oopDesc::decode_heap_oop_not_null(heap_oop);
 631 
 632       // Note: not all the oops embedded in the nmethod are in the
 633       // current region. We only look at those which are.
 634       if (_hr->is_in(obj)) {
 635         // Object is in the region. Check that its less than top
 636         if (_hr->top() <= (HeapWord*)obj) {
 637           // Object is above top
 638           gclog_or_tty->print_cr("Object "PTR_FORMAT" in region "
 639                                  "["PTR_FORMAT", "PTR_FORMAT") is above "
 640                                  "top "PTR_FORMAT,
 641                                  (void *)obj, _hr->bottom(), _hr->end(), _hr->top());
 642           _failures = true;
 643           return;
 644         }
 645         // Nmethod has at least one oop in the current region
 646         _has_oops_in_region = true;
 647       }
 648     }
 649   }
 650 
 651 public:
 652   VerifyStrongCodeRootOopClosure(const HeapRegion* hr, nmethod* nm):
 653     _hr(hr), _failures(false), _has_oops_in_region(false) {}
 654 
 655   void do_oop(narrowOop* p) { do_oop_work(p); }
 656   void do_oop(oop* p)       { do_oop_work(p); }
 657 
 658   bool failures()           { return _failures; }
 659   bool has_oops_in_region() { return _has_oops_in_region; }
 660 };
 661 
 662 class VerifyStrongCodeRootCodeBlobClosure: public CodeBlobClosure {
 663   const HeapRegion* _hr;
 664   bool _failures;
 665 public:
 666   VerifyStrongCodeRootCodeBlobClosure(const HeapRegion* hr) :
 667     _hr(hr), _failures(false) {}
 668 
 669   void do_code_blob(CodeBlob* cb) {
 670     nmethod* nm = (cb == NULL) ? NULL : cb->as_nmethod_or_null();
 671     if (nm != NULL) {
 672       // Verify that the nemthod is live
 673       if (!nm->is_alive()) {
 674         gclog_or_tty->print_cr("region ["PTR_FORMAT","PTR_FORMAT"] has dead nmethod "
 675                                PTR_FORMAT" in its strong code roots",
 676                                _hr->bottom(), _hr->end(), nm);
 677         _failures = true;
 678       } else {
 679         VerifyStrongCodeRootOopClosure oop_cl(_hr, nm);
 680         nm->oops_do(&oop_cl);
 681         if (!oop_cl.has_oops_in_region()) {
 682           gclog_or_tty->print_cr("region ["PTR_FORMAT","PTR_FORMAT"] has nmethod "
 683                                  PTR_FORMAT" in its strong code roots "
 684                                  "with no pointers into region",
 685                                  _hr->bottom(), _hr->end(), nm);
 686           _failures = true;
 687         } else if (oop_cl.failures()) {
 688           gclog_or_tty->print_cr("region ["PTR_FORMAT","PTR_FORMAT"] has other "
 689                                  "failures for nmethod "PTR_FORMAT,
 690                                  _hr->bottom(), _hr->end(), nm);
 691           _failures = true;
 692         }
 693       }
 694     }
 695   }
 696 
 697   bool failures()       { return _failures; }
 698 };
 699 
 700 void HeapRegion::verify_strong_code_roots(VerifyOption vo, bool* failures) const {
 701   if (!G1VerifyHeapRegionCodeRoots) {
 702     // We're not verifying code roots.
 703     return;
 704   }
 705   if (vo == VerifyOption_G1UseMarkWord) {
 706     // Marking verification during a full GC is performed after class
 707     // unloading, code cache unloading, etc so the strong code roots
 708     // attached to each heap region are in an inconsistent state. They won't
 709     // be consistent until the strong code roots are rebuilt after the
 710     // actual GC. Skip verifying the strong code roots in this particular
 711     // time.
 712     assert(VerifyDuringGC, "only way to get here");
 713     return;
 714   }
 715 
 716   HeapRegionRemSet* hrrs = rem_set();
 717   size_t strong_code_roots_length = hrrs->strong_code_roots_list_length();
 718 
 719   // if this region is empty then there should be no entries
 720   // on its strong code root list
 721   if (is_empty()) {
 722     if (strong_code_roots_length > 0) {
 723       gclog_or_tty->print_cr("region ["PTR_FORMAT","PTR_FORMAT"] is empty "
 724                              "but has "SIZE_FORMAT" code root entries",
 725                              bottom(), end(), strong_code_roots_length);
 726       *failures = true;
 727     }
 728     return;
 729   }
 730 
 731   if (continuesHumongous()) {
 732     if (strong_code_roots_length > 0) {
 733       gclog_or_tty->print_cr("region "HR_FORMAT" is a continuation of a humongous "
 734                              "region but has "SIZE_FORMAT" code root entries",
 735                              HR_FORMAT_PARAMS(this), strong_code_roots_length);
 736       *failures = true;
 737     }
 738     return;
 739   }
 740 
 741   VerifyStrongCodeRootCodeBlobClosure cb_cl(this);
 742   strong_code_roots_do(&cb_cl);
 743 
 744   if (cb_cl.failures()) {
 745     *failures = true;
 746   }
 747 }
 748 
 749 void HeapRegion::print() const { print_on(gclog_or_tty); }
 750 void HeapRegion::print_on(outputStream* st) const {
 751   if (isHumongous()) {
 752     if (startsHumongous())
 753       st->print(" HS");
 754     else
 755       st->print(" HC");
 756   } else {
 757     st->print("   ");
 758   }
 759   if (in_collection_set())
 760     st->print(" CS");
 761   else
 762     st->print("   ");
 763   if (is_young())
 764     st->print(is_survivor() ? " SU" : " Y ");
 765   else
 766     st->print("   ");
 767   if (is_empty())
 768     st->print(" F");
 769   else
 770     st->print("  ");
 771   st->print(" TS %5d", _gc_time_stamp);
 772   st->print(" PTAMS "PTR_FORMAT" NTAMS "PTR_FORMAT,
 773             prev_top_at_mark_start(), next_top_at_mark_start());
 774   G1OffsetTableContigSpace::print_on(st);
 775 }
 776 
 777 class VerifyLiveClosure: public OopClosure {
 778 private:
 779   G1CollectedHeap* _g1h;
 780   CardTableModRefBS* _bs;
 781   oop _containing_obj;
 782   bool _failures;
 783   int _n_failures;
 784   VerifyOption _vo;
 785 public:
 786   // _vo == UsePrevMarking -> use "prev" marking information,
 787   // _vo == UseNextMarking -> use "next" marking information,
 788   // _vo == UseMarkWord    -> use mark word from object header.
 789   VerifyLiveClosure(G1CollectedHeap* g1h, VerifyOption vo) :
 790     _g1h(g1h), _bs(NULL), _containing_obj(NULL),
 791     _failures(false), _n_failures(0), _vo(vo)
 792   {
 793     BarrierSet* bs = _g1h->barrier_set();
 794     if (bs->is_a(BarrierSet::CardTableModRef))
 795       _bs = (CardTableModRefBS*)bs;
 796   }
 797 
 798   void set_containing_obj(oop obj) {
 799     _containing_obj = obj;
 800   }
 801 
 802   bool failures() { return _failures; }
 803   int n_failures() { return _n_failures; }
 804 
 805   virtual void do_oop(narrowOop* p) { do_oop_work(p); }
 806   virtual void do_oop(      oop* p) { do_oop_work(p); }
 807 
 808   void print_object(outputStream* out, oop obj) {
 809 #ifdef PRODUCT
 810     Klass* k = obj->klass();
 811     const char* class_name = InstanceKlass::cast(k)->external_name();
 812     out->print_cr("class name %s", class_name);
 813 #else // PRODUCT
 814     obj->print_on(out);
 815 #endif // PRODUCT
 816   }
 817 
 818   template <class T>
 819   void do_oop_work(T* p) {
 820     assert(_containing_obj != NULL, "Precondition");
 821     assert(!_g1h->is_obj_dead_cond(_containing_obj, _vo),
 822            "Precondition");
 823     T heap_oop = oopDesc::load_heap_oop(p);
 824     if (!oopDesc::is_null(heap_oop)) {
 825       oop obj = oopDesc::decode_heap_oop_not_null(heap_oop);
 826       bool failed = false;
 827       if (!_g1h->is_in_closed_subset(obj) || _g1h->is_obj_dead_cond(obj, _vo)) {
 828         MutexLockerEx x(ParGCRareEvent_lock,
 829                         Mutex::_no_safepoint_check_flag);
 830 
 831         if (!_failures) {
 832           gclog_or_tty->cr();
 833           gclog_or_tty->print_cr("----------");
 834         }
 835         if (!_g1h->is_in_closed_subset(obj)) {
 836           HeapRegion* from = _g1h->heap_region_containing((HeapWord*)p);
 837           gclog_or_tty->print_cr("Field "PTR_FORMAT
 838                                  " of live obj "PTR_FORMAT" in region "
 839                                  "["PTR_FORMAT", "PTR_FORMAT")",
 840                                  p, (void*) _containing_obj,
 841                                  from->bottom(), from->end());
 842           print_object(gclog_or_tty, _containing_obj);
 843           gclog_or_tty->print_cr("points to obj "PTR_FORMAT" not in the heap",
 844                                  (void*) obj);
 845         } else {
 846           HeapRegion* from = _g1h->heap_region_containing((HeapWord*)p);
 847           HeapRegion* to   = _g1h->heap_region_containing((HeapWord*)obj);
 848           gclog_or_tty->print_cr("Field "PTR_FORMAT
 849                                  " of live obj "PTR_FORMAT" in region "
 850                                  "["PTR_FORMAT", "PTR_FORMAT")",
 851                                  p, (void*) _containing_obj,
 852                                  from->bottom(), from->end());
 853           print_object(gclog_or_tty, _containing_obj);
 854           gclog_or_tty->print_cr("points to dead obj "PTR_FORMAT" in region "
 855                                  "["PTR_FORMAT", "PTR_FORMAT")",
 856                                  (void*) obj, to->bottom(), to->end());
 857           print_object(gclog_or_tty, obj);
 858         }
 859         gclog_or_tty->print_cr("----------");
 860         gclog_or_tty->flush();
 861         _failures = true;
 862         failed = true;
 863         _n_failures++;
 864       }
 865 
 866       if (!_g1h->full_collection() || G1VerifyRSetsDuringFullGC) {
 867         HeapRegion* from = _g1h->heap_region_containing((HeapWord*)p);
 868         HeapRegion* to   = _g1h->heap_region_containing(obj);
 869         if (from != NULL && to != NULL &&
 870             from != to &&
 871             !to->isHumongous()) {
 872           jbyte cv_obj = *_bs->byte_for_const(_containing_obj);
 873           jbyte cv_field = *_bs->byte_for_const(p);
 874           const jbyte dirty = CardTableModRefBS::dirty_card_val();
 875 
 876           bool is_bad = !(from->is_young()
 877                           || to->rem_set()->contains_reference(p)
 878                           || !G1HRRSFlushLogBuffersOnVerify && // buffers were not flushed
 879                               (_containing_obj->is_objArray() ?
 880                                   cv_field == dirty
 881                                : cv_obj == dirty || cv_field == dirty));
 882           if (is_bad) {
 883             MutexLockerEx x(ParGCRareEvent_lock,
 884                             Mutex::_no_safepoint_check_flag);
 885 
 886             if (!_failures) {
 887               gclog_or_tty->cr();
 888               gclog_or_tty->print_cr("----------");
 889             }
 890             gclog_or_tty->print_cr("Missing rem set entry:");
 891             gclog_or_tty->print_cr("Field "PTR_FORMAT" "
 892                                    "of obj "PTR_FORMAT", "
 893                                    "in region "HR_FORMAT,
 894                                    p, (void*) _containing_obj,
 895                                    HR_FORMAT_PARAMS(from));
 896             _containing_obj->print_on(gclog_or_tty);
 897             gclog_or_tty->print_cr("points to obj "PTR_FORMAT" "
 898                                    "in region "HR_FORMAT,
 899                                    (void*) obj,
 900                                    HR_FORMAT_PARAMS(to));
 901             obj->print_on(gclog_or_tty);
 902             gclog_or_tty->print_cr("Obj head CTE = %d, field CTE = %d.",
 903                           cv_obj, cv_field);
 904             gclog_or_tty->print_cr("----------");
 905             gclog_or_tty->flush();
 906             _failures = true;
 907             if (!failed) _n_failures++;
 908           }
 909         }
 910       }
 911     }
 912   }
 913 };
 914 
 915 // This really ought to be commoned up into OffsetTableContigSpace somehow.
 916 // We would need a mechanism to make that code skip dead objects.
 917 
 918 void HeapRegion::verify(VerifyOption vo,
 919                         bool* failures) const {
 920   G1CollectedHeap* g1 = G1CollectedHeap::heap();
 921   *failures = false;
 922   HeapWord* p = bottom();
 923   HeapWord* prev_p = NULL;
 924   VerifyLiveClosure vl_cl(g1, vo);
 925   bool is_humongous = isHumongous();
 926   bool do_bot_verify = !is_young();
 927   size_t object_num = 0;
 928   while (p < top()) {
 929     oop obj = oop(p);
 930     size_t obj_size = obj->size();
 931     object_num += 1;
 932 
 933     if (is_humongous != g1->isHumongous(obj_size)) {
 934       gclog_or_tty->print_cr("obj "PTR_FORMAT" is of %shumongous size ("
 935                              SIZE_FORMAT" words) in a %shumongous region",
 936                              p, g1->isHumongous(obj_size) ? "" : "non-",
 937                              obj_size, is_humongous ? "" : "non-");
 938        *failures = true;
 939        return;
 940     }
 941 
 942     // If it returns false, verify_for_object() will output the
 943     // appropriate messasge.
 944     if (do_bot_verify && !_offsets.verify_for_object(p, obj_size)) {
 945       *failures = true;
 946       return;
 947     }
 948 
 949     if (!g1->is_obj_dead_cond(obj, this, vo)) {
 950       if (obj->is_oop()) {
 951         Klass* klass = obj->klass();
 952         if (!klass->is_metaspace_object()) {
 953           gclog_or_tty->print_cr("klass "PTR_FORMAT" of object "PTR_FORMAT" "
 954                                  "not metadata", klass, (void *)obj);
 955           *failures = true;
 956           return;
 957         } else if (!klass->is_klass()) {
 958           gclog_or_tty->print_cr("klass "PTR_FORMAT" of object "PTR_FORMAT" "
 959                                  "not a klass", klass, (void *)obj);
 960           *failures = true;
 961           return;
 962         } else {
 963           vl_cl.set_containing_obj(obj);
 964           obj->oop_iterate_no_header(&vl_cl);
 965           if (vl_cl.failures()) {
 966             *failures = true;
 967           }
 968           if (G1MaxVerifyFailures >= 0 &&
 969               vl_cl.n_failures() >= G1MaxVerifyFailures) {
 970             return;
 971           }
 972         }
 973       } else {
 974         gclog_or_tty->print_cr(PTR_FORMAT" no an oop", (void *)obj);
 975         *failures = true;
 976         return;
 977       }
 978     }
 979     prev_p = p;
 980     p += obj_size;
 981   }
 982 
 983   if (p != top()) {
 984     gclog_or_tty->print_cr("end of last object "PTR_FORMAT" "
 985                            "does not match top "PTR_FORMAT, p, top());
 986     *failures = true;
 987     return;
 988   }
 989 
 990   HeapWord* the_end = end();
 991   assert(p == top(), "it should still hold");
 992   // Do some extra BOT consistency checking for addresses in the
 993   // range [top, end). BOT look-ups in this range should yield
 994   // top. No point in doing that if top == end (there's nothing there).
 995   if (p < the_end) {
 996     // Look up top
 997     HeapWord* addr_1 = p;
 998     HeapWord* b_start_1 = _offsets.block_start_const(addr_1);
 999     if (b_start_1 != p) {
1000       gclog_or_tty->print_cr("BOT look up for top: "PTR_FORMAT" "
1001                              " yielded "PTR_FORMAT", expecting "PTR_FORMAT,
1002                              addr_1, b_start_1, p);
1003       *failures = true;
1004       return;
1005     }
1006 
1007     // Look up top + 1
1008     HeapWord* addr_2 = p + 1;
1009     if (addr_2 < the_end) {
1010       HeapWord* b_start_2 = _offsets.block_start_const(addr_2);
1011       if (b_start_2 != p) {
1012         gclog_or_tty->print_cr("BOT look up for top + 1: "PTR_FORMAT" "
1013                                " yielded "PTR_FORMAT", expecting "PTR_FORMAT,
1014                                addr_2, b_start_2, p);
1015         *failures = true;
1016         return;
1017       }
1018     }
1019 
1020     // Look up an address between top and end
1021     size_t diff = pointer_delta(the_end, p) / 2;
1022     HeapWord* addr_3 = p + diff;
1023     if (addr_3 < the_end) {
1024       HeapWord* b_start_3 = _offsets.block_start_const(addr_3);
1025       if (b_start_3 != p) {
1026         gclog_or_tty->print_cr("BOT look up for top + diff: "PTR_FORMAT" "
1027                                " yielded "PTR_FORMAT", expecting "PTR_FORMAT,
1028                                addr_3, b_start_3, p);
1029         *failures = true;
1030         return;
1031       }
1032     }
1033 
1034     // Look up end - 1
1035     HeapWord* addr_4 = the_end - 1;
1036     HeapWord* b_start_4 = _offsets.block_start_const(addr_4);
1037     if (b_start_4 != p) {
1038       gclog_or_tty->print_cr("BOT look up for end - 1: "PTR_FORMAT" "
1039                              " yielded "PTR_FORMAT", expecting "PTR_FORMAT,
1040                              addr_4, b_start_4, p);
1041       *failures = true;
1042       return;
1043     }
1044   }
1045 
1046   if (is_humongous && object_num > 1) {
1047     gclog_or_tty->print_cr("region ["PTR_FORMAT","PTR_FORMAT"] is humongous "
1048                            "but has "SIZE_FORMAT", objects",
1049                            bottom(), end(), object_num);
1050     *failures = true;
1051     return;
1052   }
1053 
1054   verify_strong_code_roots(vo, failures);
1055 }
1056 
1057 void HeapRegion::verify() const {
1058   bool dummy = false;
1059   verify(VerifyOption_G1UsePrevMarking, /* failures */ &dummy);
1060 }
1061 
1062 // G1OffsetTableContigSpace code; copied from space.cpp.  Hope this can go
1063 // away eventually.
1064 
1065 void G1OffsetTableContigSpace::clear(bool mangle_space) {
1066   ContiguousSpace::clear(mangle_space);
1067   _offsets.zero_bottom_entry();
1068   _offsets.initialize_threshold();
1069 }
1070 
1071 void G1OffsetTableContigSpace::set_bottom(HeapWord* new_bottom) {
1072   Space::set_bottom(new_bottom);
1073   _offsets.set_bottom(new_bottom);
1074 }
1075 
1076 void G1OffsetTableContigSpace::set_end(HeapWord* new_end) {
1077   Space::set_end(new_end);
1078   _offsets.resize(new_end - bottom());
1079 }
1080 
1081 void G1OffsetTableContigSpace::print() const {
1082   print_short();
1083   gclog_or_tty->print_cr(" [" INTPTR_FORMAT ", " INTPTR_FORMAT ", "
1084                 INTPTR_FORMAT ", " INTPTR_FORMAT ")",
1085                 bottom(), top(), _offsets.threshold(), end());
1086 }
1087 
1088 HeapWord* G1OffsetTableContigSpace::initialize_threshold() {
1089   return _offsets.initialize_threshold();
1090 }
1091 
1092 HeapWord* G1OffsetTableContigSpace::cross_threshold(HeapWord* start,
1093                                                     HeapWord* end) {
1094   _offsets.alloc_block(start, end);
1095   return _offsets.threshold();
1096 }
1097 
1098 HeapWord* G1OffsetTableContigSpace::saved_mark_word() const {
1099   G1CollectedHeap* g1h = G1CollectedHeap::heap();
1100   assert( _gc_time_stamp <= g1h->get_gc_time_stamp(), "invariant" );
1101   if (_gc_time_stamp < g1h->get_gc_time_stamp())
1102     return top();
1103   else
1104     return ContiguousSpace::saved_mark_word();
1105 }
1106 
1107 void G1OffsetTableContigSpace::set_saved_mark() {
1108   G1CollectedHeap* g1h = G1CollectedHeap::heap();
1109   unsigned curr_gc_time_stamp = g1h->get_gc_time_stamp();
1110 
1111   if (_gc_time_stamp < curr_gc_time_stamp) {
1112     // The order of these is important, as another thread might be
1113     // about to start scanning this region. If it does so after
1114     // set_saved_mark and before _gc_time_stamp = ..., then the latter
1115     // will be false, and it will pick up top() as the high water mark
1116     // of region. If it does so after _gc_time_stamp = ..., then it
1117     // will pick up the right saved_mark_word() as the high water mark
1118     // of the region. Either way, the behavior will be correct.
1119     ContiguousSpace::set_saved_mark();
1120     OrderAccess::storestore();
1121     _gc_time_stamp = curr_gc_time_stamp;
1122     // No need to do another barrier to flush the writes above. If
1123     // this is called in parallel with other threads trying to
1124     // allocate into the region, the caller should call this while
1125     // holding a lock and when the lock is released the writes will be
1126     // flushed.
1127   }
1128 }
1129 
1130 G1OffsetTableContigSpace::
1131 G1OffsetTableContigSpace(G1BlockOffsetSharedArray* sharedOffsetArray,
1132                          MemRegion mr) :
1133   _offsets(sharedOffsetArray, mr),
1134   _par_alloc_lock(Mutex::leaf, "OffsetTableContigSpace par alloc lock", true),
1135   _gc_time_stamp(0)
1136 {
1137   _offsets.set_space(this);
1138   // false ==> we'll do the clearing if there's clearing to be done.
1139   ContiguousSpace::initialize(mr, false, SpaceDecorator::Mangle);
1140   _offsets.zero_bottom_entry();
1141   _offsets.initialize_threshold();
1142 }