1 /*
   2  * Copyright (c) 2001, 2012, 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_implementation/g1/concurrentG1Refine.hpp"
  27 #include "gc_implementation/g1/g1BlockOffsetTable.inline.hpp"
  28 #include "gc_implementation/g1/g1CollectedHeap.inline.hpp"
  29 #include "gc_implementation/g1/heapRegionRemSet.hpp"
  30 #include "gc_implementation/g1/heapRegionSeq.inline.hpp"
  31 #include "memory/allocation.hpp"
  32 #include "memory/space.inline.hpp"
  33 #include "oops/oop.inline.hpp"
  34 #include "utilities/bitMap.inline.hpp"
  35 #include "utilities/globalDefinitions.hpp"
  36 
  37 class PerRegionTable: public CHeapObj<mtGC> {
  38   friend class OtherRegionsTable;
  39   friend class HeapRegionRemSetIterator;
  40 
  41   HeapRegion*     _hr;
  42   BitMap          _bm;
  43   jint            _occupied;
  44 
  45   // next pointer for free/allocated 'all' list
  46   PerRegionTable* _next;
  47 
  48   // prev pointer for the allocated 'all' list
  49   PerRegionTable* _prev;
  50 
  51   // next pointer in collision list
  52   PerRegionTable * _collision_list_next;
  53 
  54   // Global free list of PRTs
  55   static PerRegionTable* _free_list;
  56 
  57 protected:
  58   // We need access in order to union things into the base table.
  59   BitMap* bm() { return &_bm; }
  60 
  61   void recount_occupied() {
  62     _occupied = (jint) bm()->count_one_bits();
  63   }
  64 
  65   PerRegionTable(HeapRegion* hr) :
  66     _hr(hr),
  67     _occupied(0),
  68     _bm(HeapRegion::CardsPerRegion, false /* in-resource-area */),
  69     _collision_list_next(NULL), _next(NULL), _prev(NULL)
  70   {}
  71 
  72   void add_card_work(CardIdx_t from_card, bool par) {
  73     if (!_bm.at(from_card)) {
  74       if (par) {
  75         if (_bm.par_at_put(from_card, 1)) {
  76           Atomic::inc(&_occupied);
  77         }
  78       } else {
  79         _bm.at_put(from_card, 1);
  80         _occupied++;
  81       }
  82     }
  83   }
  84 
  85   void add_reference_work(OopOrNarrowOopStar from, bool par) {
  86     // Must make this robust in case "from" is not in "_hr", because of
  87     // concurrency.
  88 
  89     if (G1TraceHeapRegionRememberedSet) {
  90       gclog_or_tty->print_cr("    PRT::Add_reference_work(" PTR_FORMAT "->" PTR_FORMAT").",
  91                              from,
  92                              UseCompressedOops
  93                              ? oopDesc::load_decode_heap_oop((narrowOop*)from)
  94                              : oopDesc::load_decode_heap_oop((oop*)from));
  95     }
  96 
  97     HeapRegion* loc_hr = hr();
  98     // If the test below fails, then this table was reused concurrently
  99     // with this operation.  This is OK, since the old table was coarsened,
 100     // and adding a bit to the new table is never incorrect.
 101     // If the table used to belong to a continues humongous region and is
 102     // now reused for the corresponding start humongous region, we need to
 103     // make sure that we detect this. Thus, we call is_in_reserved_raw()
 104     // instead of just is_in_reserved() here.
 105     if (loc_hr->is_in_reserved_raw(from)) {
 106       size_t hw_offset = pointer_delta((HeapWord*)from, loc_hr->bottom());
 107       CardIdx_t from_card = (CardIdx_t)
 108           hw_offset >> (CardTableModRefBS::card_shift - LogHeapWordSize);
 109 
 110       assert(0 <= from_card && (size_t)from_card < HeapRegion::CardsPerRegion,
 111              "Must be in range.");
 112       add_card_work(from_card, par);
 113     }
 114   }
 115 
 116 public:
 117 
 118   HeapRegion* hr() const { return _hr; }
 119 
 120   jint occupied() const {
 121     // Overkill, but if we ever need it...
 122     // guarantee(_occupied == _bm.count_one_bits(), "Check");
 123     return _occupied;
 124   }
 125 
 126   void init(HeapRegion* hr, bool clear_links_to_all_list) {
 127     if (clear_links_to_all_list) {
 128       set_next(NULL);
 129       set_prev(NULL);
 130     }
 131     _hr = hr;
 132     _collision_list_next = NULL;
 133     _occupied = 0;
 134     _bm.clear();
 135   }
 136 
 137   void add_reference(OopOrNarrowOopStar from) {
 138     add_reference_work(from, /*parallel*/ true);
 139   }
 140 
 141   void seq_add_reference(OopOrNarrowOopStar from) {
 142     add_reference_work(from, /*parallel*/ false);
 143   }
 144 
 145   void scrub(CardTableModRefBS* ctbs, BitMap* card_bm) {
 146     HeapWord* hr_bot = hr()->bottom();
 147     size_t hr_first_card_index = ctbs->index_for(hr_bot);
 148     bm()->set_intersection_at_offset(*card_bm, hr_first_card_index);
 149     recount_occupied();
 150   }
 151 
 152   void add_card(CardIdx_t from_card_index) {
 153     add_card_work(from_card_index, /*parallel*/ true);
 154   }
 155 
 156   void seq_add_card(CardIdx_t from_card_index) {
 157     add_card_work(from_card_index, /*parallel*/ false);
 158   }
 159 
 160   // (Destructively) union the bitmap of the current table into the given
 161   // bitmap (which is assumed to be of the same size.)
 162   void union_bitmap_into(BitMap* bm) {
 163     bm->set_union(_bm);
 164   }
 165 
 166   // Mem size in bytes.
 167   size_t mem_size() const {
 168     return sizeof(this) + _bm.size_in_words() * HeapWordSize;
 169   }
 170 
 171   // Requires "from" to be in "hr()".
 172   bool contains_reference(OopOrNarrowOopStar from) const {
 173     assert(hr()->is_in_reserved(from), "Precondition.");
 174     size_t card_ind = pointer_delta(from, hr()->bottom(),
 175                                     CardTableModRefBS::card_size);
 176     return _bm.at(card_ind);
 177   }
 178 
 179   // Bulk-free the PRTs from prt to last, assumes that they are
 180   // linked together using their _next field.
 181   static void bulk_free(PerRegionTable* prt, PerRegionTable* last) {
 182     while (true) {
 183       PerRegionTable* fl = _free_list;
 184       last->set_next(fl);
 185       PerRegionTable* res = (PerRegionTable*) Atomic::cmpxchg_ptr(prt, &_free_list, fl);
 186       if (res == fl) {
 187         return;
 188       }
 189     }
 190     ShouldNotReachHere();
 191   }
 192 
 193   static void free(PerRegionTable* prt) {
 194     bulk_free(prt, prt);
 195   }
 196 
 197   // Returns an initialized PerRegionTable instance.
 198   static PerRegionTable* alloc(HeapRegion* hr) {
 199     PerRegionTable* fl = _free_list;
 200     while (fl != NULL) {
 201       PerRegionTable* nxt = fl->next();
 202       PerRegionTable* res =
 203         (PerRegionTable*)
 204         Atomic::cmpxchg_ptr(nxt, &_free_list, fl);
 205       if (res == fl) {
 206         fl->init(hr, true);
 207         return fl;
 208       } else {
 209         fl = _free_list;
 210       }
 211     }
 212     assert(fl == NULL, "Loop condition.");
 213     return new PerRegionTable(hr);
 214   }
 215 
 216   PerRegionTable* next() const { return _next; }
 217   void set_next(PerRegionTable* next) { _next = next; }
 218   PerRegionTable* prev() const { return _prev; }
 219   void set_prev(PerRegionTable* prev) { _prev = prev; }
 220 
 221   // Accessor and Modification routines for the pointer for the
 222   // singly linked collision list that links the PRTs within the
 223   // OtherRegionsTable::_fine_grain_regions hash table.
 224   //
 225   // It might be useful to also make the collision list doubly linked
 226   // to avoid iteration over the collisions list during scrubbing/deletion.
 227   // OTOH there might not be many collisions.
 228 
 229   PerRegionTable* collision_list_next() const {
 230     return _collision_list_next;
 231   }
 232 
 233   void set_collision_list_next(PerRegionTable* next) {
 234     _collision_list_next = next;
 235   }
 236 
 237   PerRegionTable** collision_list_next_addr() {
 238     return &_collision_list_next;
 239   }
 240 
 241   static size_t fl_mem_size() {
 242     PerRegionTable* cur = _free_list;
 243     size_t res = 0;
 244     while (cur != NULL) {
 245       res += cur->mem_size();
 246       cur = cur->next();
 247     }
 248     return res;
 249   }
 250 
 251 #ifndef PRODUCT
 252   static void test() {
 253     PerRegionTable* dummy = alloc(NULL);
 254     free(dummy);
 255     guarantee(dummy->mem_size() == fl_mem_size(), "fl_mem_size() does not return the correct element size");
 256   }
 257 #endif
 258 };
 259 
 260 PerRegionTable* PerRegionTable::_free_list = NULL;
 261 
 262 size_t OtherRegionsTable::_max_fine_entries = 0;
 263 size_t OtherRegionsTable::_mod_max_fine_entries_mask = 0;
 264 size_t OtherRegionsTable::_fine_eviction_stride = 0;
 265 size_t OtherRegionsTable::_fine_eviction_sample_size = 0;
 266 
 267 OtherRegionsTable::OtherRegionsTable(HeapRegion* hr) :
 268   _g1h(G1CollectedHeap::heap()),
 269   _m(Mutex::leaf, "An OtherRegionsTable lock", true),
 270   _hr(hr),
 271   _coarse_map(G1CollectedHeap::heap()->max_regions(),
 272               false /* in-resource-area */),
 273   _fine_grain_regions(NULL),
 274   _first_all_fine_prts(NULL), _last_all_fine_prts(NULL),
 275   _n_fine_entries(0), _n_coarse_entries(0),
 276   _fine_eviction_start(0),
 277   _sparse_table(hr)
 278 {
 279   typedef PerRegionTable* PerRegionTablePtr;
 280 
 281   if (_max_fine_entries == 0) {
 282     assert(_mod_max_fine_entries_mask == 0, "Both or none.");
 283     size_t max_entries_log = (size_t)log2_long((jlong)G1RSetRegionEntries);
 284     _max_fine_entries = (size_t)1 << max_entries_log;
 285     _mod_max_fine_entries_mask = _max_fine_entries - 1;
 286 
 287     assert(_fine_eviction_sample_size == 0
 288            && _fine_eviction_stride == 0, "All init at same time.");
 289     _fine_eviction_sample_size = MAX2((size_t)4, max_entries_log);
 290     _fine_eviction_stride = _max_fine_entries / _fine_eviction_sample_size;
 291   }
 292 
 293   _fine_grain_regions = new PerRegionTablePtr[_max_fine_entries];
 294 
 295   if (_fine_grain_regions == NULL) {
 296     vm_exit_out_of_memory(sizeof(void*)*_max_fine_entries, OOM_MALLOC_ERROR,
 297                           "Failed to allocate _fine_grain_entries.");
 298   }
 299 
 300   for (size_t i = 0; i < _max_fine_entries; i++) {
 301     _fine_grain_regions[i] = NULL;
 302   }
 303 }
 304 
 305 void OtherRegionsTable::link_to_all(PerRegionTable* prt) {
 306   // We always append to the beginning of the list for convenience;
 307   // the order of entries in this list does not matter.
 308   if (_first_all_fine_prts != NULL) {
 309     assert(_first_all_fine_prts->prev() == NULL, "invariant");
 310     _first_all_fine_prts->set_prev(prt);
 311     prt->set_next(_first_all_fine_prts);
 312   } else {
 313     // this is the first element we insert. Adjust the "last" pointer
 314     _last_all_fine_prts = prt;
 315     assert(prt->next() == NULL, "just checking");
 316   }
 317   // the new element is always the first element without a predecessor
 318   prt->set_prev(NULL);
 319   _first_all_fine_prts = prt;
 320 
 321   assert(prt->prev() == NULL, "just checking");
 322   assert(_first_all_fine_prts == prt, "just checking");
 323   assert((_first_all_fine_prts == NULL && _last_all_fine_prts == NULL) ||
 324          (_first_all_fine_prts != NULL && _last_all_fine_prts != NULL),
 325          "just checking");
 326   assert(_last_all_fine_prts == NULL || _last_all_fine_prts->next() == NULL,
 327          "just checking");
 328   assert(_first_all_fine_prts == NULL || _first_all_fine_prts->prev() == NULL,
 329          "just checking");
 330 }
 331 
 332 void OtherRegionsTable::unlink_from_all(PerRegionTable* prt) {
 333   if (prt->prev() != NULL) {
 334     assert(_first_all_fine_prts != prt, "just checking");
 335     prt->prev()->set_next(prt->next());
 336     // removing the last element in the list?
 337     if (_last_all_fine_prts == prt) {
 338       _last_all_fine_prts = prt->prev();
 339     }
 340   } else {
 341     assert(_first_all_fine_prts == prt, "just checking");
 342     _first_all_fine_prts = prt->next();
 343     // list is empty now?
 344     if (_first_all_fine_prts == NULL) {
 345       _last_all_fine_prts = NULL;
 346     }
 347   }
 348 
 349   if (prt->next() != NULL) {
 350     prt->next()->set_prev(prt->prev());
 351   }
 352 
 353   prt->set_next(NULL);
 354   prt->set_prev(NULL);
 355 
 356   assert((_first_all_fine_prts == NULL && _last_all_fine_prts == NULL) ||
 357          (_first_all_fine_prts != NULL && _last_all_fine_prts != NULL),
 358          "just checking");
 359   assert(_last_all_fine_prts == NULL || _last_all_fine_prts->next() == NULL,
 360          "just checking");
 361   assert(_first_all_fine_prts == NULL || _first_all_fine_prts->prev() == NULL,
 362          "just checking");
 363 }
 364 
 365 int**  OtherRegionsTable::_from_card_cache = NULL;
 366 size_t OtherRegionsTable::_from_card_cache_max_regions = 0;
 367 size_t OtherRegionsTable::_from_card_cache_mem_size = 0;
 368 
 369 void OtherRegionsTable::init_from_card_cache(size_t max_regions) {
 370   _from_card_cache_max_regions = max_regions;
 371 
 372   int n_par_rs = HeapRegionRemSet::num_par_rem_sets();
 373   _from_card_cache = NEW_C_HEAP_ARRAY(int*, n_par_rs, mtGC);
 374   for (int i = 0; i < n_par_rs; i++) {
 375     _from_card_cache[i] = NEW_C_HEAP_ARRAY(int, max_regions, mtGC);
 376     for (size_t j = 0; j < max_regions; j++) {
 377       _from_card_cache[i][j] = -1;  // An invalid value.
 378     }
 379   }
 380   _from_card_cache_mem_size = n_par_rs * max_regions * sizeof(int);
 381 }
 382 
 383 void OtherRegionsTable::shrink_from_card_cache(size_t new_n_regs) {
 384   for (int i = 0; i < HeapRegionRemSet::num_par_rem_sets(); i++) {
 385     assert(new_n_regs <= _from_card_cache_max_regions, "Must be within max.");
 386     for (size_t j = new_n_regs; j < _from_card_cache_max_regions; j++) {
 387       _from_card_cache[i][j] = -1;  // An invalid value.
 388     }
 389   }
 390 }
 391 
 392 #ifndef PRODUCT
 393 void OtherRegionsTable::print_from_card_cache() {
 394   for (int i = 0; i < HeapRegionRemSet::num_par_rem_sets(); i++) {
 395     for (size_t j = 0; j < _from_card_cache_max_regions; j++) {
 396       gclog_or_tty->print_cr("_from_card_cache[%d][%d] = %d.",
 397                     i, j, _from_card_cache[i][j]);
 398     }
 399   }
 400 }
 401 #endif
 402 
 403 void OtherRegionsTable::add_reference(OopOrNarrowOopStar from, int tid) {
 404   size_t cur_hrs_ind = (size_t) hr()->hrs_index();
 405 
 406   if (G1TraceHeapRegionRememberedSet) {
 407     gclog_or_tty->print_cr("ORT::add_reference_work(" PTR_FORMAT "->" PTR_FORMAT ").",
 408                                                     from,
 409                                                     UseCompressedOops
 410                                                     ? oopDesc::load_decode_heap_oop((narrowOop*)from)
 411                                                     : oopDesc::load_decode_heap_oop((oop*)from));
 412   }
 413 
 414   int from_card = (int)(uintptr_t(from) >> CardTableModRefBS::card_shift);
 415 
 416   if (G1TraceHeapRegionRememberedSet) {
 417     gclog_or_tty->print_cr("Table for [" PTR_FORMAT "...): card %d (cache = %d)",
 418                   hr()->bottom(), from_card,
 419                   _from_card_cache[tid][cur_hrs_ind]);
 420   }
 421 
 422   if (from_card == _from_card_cache[tid][cur_hrs_ind]) {
 423     if (G1TraceHeapRegionRememberedSet) {
 424       gclog_or_tty->print_cr("  from-card cache hit.");
 425     }
 426     assert(contains_reference(from), "We just added it!");
 427     return;
 428   } else {
 429     _from_card_cache[tid][cur_hrs_ind] = from_card;
 430   }
 431 
 432   // Note that this may be a continued H region.
 433   HeapRegion* from_hr = _g1h->heap_region_containing_raw(from);
 434   RegionIdx_t from_hrs_ind = (RegionIdx_t) from_hr->hrs_index();
 435 
 436   // If the region is already coarsened, return.
 437   if (_coarse_map.at(from_hrs_ind)) {
 438     if (G1TraceHeapRegionRememberedSet) {
 439       gclog_or_tty->print_cr("  coarse map hit.");
 440     }
 441     assert(contains_reference(from), "We just added it!");
 442     return;
 443   }
 444 
 445   // Otherwise find a per-region table to add it to.
 446   size_t ind = from_hrs_ind & _mod_max_fine_entries_mask;
 447   PerRegionTable* prt = find_region_table(ind, from_hr);
 448   if (prt == NULL) {
 449     MutexLockerEx x(&_m, Mutex::_no_safepoint_check_flag);
 450     // Confirm that it's really not there...
 451     prt = find_region_table(ind, from_hr);
 452     if (prt == NULL) {
 453 
 454       uintptr_t from_hr_bot_card_index =
 455         uintptr_t(from_hr->bottom())
 456           >> CardTableModRefBS::card_shift;
 457       CardIdx_t card_index = from_card - from_hr_bot_card_index;
 458       assert(0 <= card_index && (size_t)card_index < HeapRegion::CardsPerRegion,
 459              "Must be in range.");
 460       if (G1HRRSUseSparseTable &&
 461           _sparse_table.add_card(from_hrs_ind, card_index)) {
 462         if (G1RecordHRRSOops) {
 463           HeapRegionRemSet::record(hr(), from);
 464           if (G1TraceHeapRegionRememberedSet) {
 465             gclog_or_tty->print("   Added card " PTR_FORMAT " to region "
 466                                 "[" PTR_FORMAT "...) for ref " PTR_FORMAT ".\n",
 467                                 align_size_down(uintptr_t(from),
 468                                                 CardTableModRefBS::card_size),
 469                                 hr()->bottom(), from);
 470           }
 471         }
 472         if (G1TraceHeapRegionRememberedSet) {
 473           gclog_or_tty->print_cr("   added card to sparse table.");
 474         }
 475         assert(contains_reference_locked(from), "We just added it!");
 476         return;
 477       } else {
 478         if (G1TraceHeapRegionRememberedSet) {
 479           gclog_or_tty->print_cr("   [tid %d] sparse table entry "
 480                         "overflow(f: %d, t: %d)",
 481                         tid, from_hrs_ind, cur_hrs_ind);
 482         }
 483       }
 484 
 485       if (_n_fine_entries == _max_fine_entries) {
 486         prt = delete_region_table();
 487         // There is no need to clear the links to the 'all' list here:
 488         // prt will be reused immediately, i.e. remain in the 'all' list.
 489         prt->init(from_hr, false /* clear_links_to_all_list */);
 490       } else {
 491         prt = PerRegionTable::alloc(from_hr);
 492         link_to_all(prt);
 493       }
 494 
 495       PerRegionTable* first_prt = _fine_grain_regions[ind];
 496       prt->set_collision_list_next(first_prt);
 497       _fine_grain_regions[ind] = prt;
 498       _n_fine_entries++;
 499 
 500       if (G1HRRSUseSparseTable) {
 501         // Transfer from sparse to fine-grain.
 502         SparsePRTEntry *sprt_entry = _sparse_table.get_entry(from_hrs_ind);
 503         assert(sprt_entry != NULL, "There should have been an entry");
 504         for (int i = 0; i < SparsePRTEntry::cards_num(); i++) {
 505           CardIdx_t c = sprt_entry->card(i);
 506           if (c != SparsePRTEntry::NullEntry) {
 507             prt->add_card(c);
 508           }
 509         }
 510         // Now we can delete the sparse entry.
 511         bool res = _sparse_table.delete_entry(from_hrs_ind);
 512         assert(res, "It should have been there.");
 513       }
 514     }
 515     assert(prt != NULL && prt->hr() == from_hr, "consequence");
 516   }
 517   // Note that we can't assert "prt->hr() == from_hr", because of the
 518   // possibility of concurrent reuse.  But see head comment of
 519   // OtherRegionsTable for why this is OK.
 520   assert(prt != NULL, "Inv");
 521 
 522   prt->add_reference(from);
 523 
 524   if (G1RecordHRRSOops) {
 525     HeapRegionRemSet::record(hr(), from);
 526     if (G1TraceHeapRegionRememberedSet) {
 527       gclog_or_tty->print("Added card " PTR_FORMAT " to region "
 528                           "[" PTR_FORMAT "...) for ref " PTR_FORMAT ".\n",
 529                           align_size_down(uintptr_t(from),
 530                                           CardTableModRefBS::card_size),
 531                           hr()->bottom(), from);
 532     }
 533   }
 534   assert(contains_reference(from), "We just added it!");
 535 }
 536 
 537 PerRegionTable*
 538 OtherRegionsTable::find_region_table(size_t ind, HeapRegion* hr) const {
 539   assert(0 <= ind && ind < _max_fine_entries, "Preconditions.");
 540   PerRegionTable* prt = _fine_grain_regions[ind];
 541   while (prt != NULL && prt->hr() != hr) {
 542     prt = prt->collision_list_next();
 543   }
 544   // Loop postcondition is the method postcondition.
 545   return prt;
 546 }
 547 
 548 jint OtherRegionsTable::_n_coarsenings = 0;
 549 
 550 PerRegionTable* OtherRegionsTable::delete_region_table() {
 551   assert(_m.owned_by_self(), "Precondition");
 552   assert(_n_fine_entries == _max_fine_entries, "Precondition");
 553   PerRegionTable* max = NULL;
 554   jint max_occ = 0;
 555   PerRegionTable** max_prev;
 556   size_t max_ind;
 557 
 558   size_t i = _fine_eviction_start;
 559   for (size_t k = 0; k < _fine_eviction_sample_size; k++) {
 560     size_t ii = i;
 561     // Make sure we get a non-NULL sample.
 562     while (_fine_grain_regions[ii] == NULL) {
 563       ii++;
 564       if (ii == _max_fine_entries) ii = 0;
 565       guarantee(ii != i, "We must find one.");
 566     }
 567     PerRegionTable** prev = &_fine_grain_regions[ii];
 568     PerRegionTable* cur = *prev;
 569     while (cur != NULL) {
 570       jint cur_occ = cur->occupied();
 571       if (max == NULL || cur_occ > max_occ) {
 572         max = cur;
 573         max_prev = prev;
 574         max_ind = i;
 575         max_occ = cur_occ;
 576       }
 577       prev = cur->collision_list_next_addr();
 578       cur = cur->collision_list_next();
 579     }
 580     i = i + _fine_eviction_stride;
 581     if (i >= _n_fine_entries) i = i - _n_fine_entries;
 582   }
 583 
 584   _fine_eviction_start++;
 585 
 586   if (_fine_eviction_start >= _n_fine_entries) {
 587     _fine_eviction_start -= _n_fine_entries;
 588   }
 589 
 590   guarantee(max != NULL, "Since _n_fine_entries > 0");
 591 
 592   // Set the corresponding coarse bit.
 593   size_t max_hrs_index = (size_t) max->hr()->hrs_index();
 594   if (!_coarse_map.at(max_hrs_index)) {
 595     _coarse_map.at_put(max_hrs_index, true);
 596     _n_coarse_entries++;
 597     if (G1TraceHeapRegionRememberedSet) {
 598       gclog_or_tty->print("Coarsened entry in region [" PTR_FORMAT "...] "
 599                  "for region [" PTR_FORMAT "...] (%d coarse entries).\n",
 600                  hr()->bottom(),
 601                  max->hr()->bottom(),
 602                  _n_coarse_entries);
 603     }
 604   }
 605 
 606   // Unsplice.
 607   *max_prev = max->collision_list_next();
 608   Atomic::inc(&_n_coarsenings);
 609   _n_fine_entries--;
 610   return max;
 611 }
 612 
 613 
 614 // At present, this must be called stop-world single-threaded.
 615 void OtherRegionsTable::scrub(CardTableModRefBS* ctbs,
 616                               BitMap* region_bm, BitMap* card_bm) {
 617   // First eliminated garbage regions from the coarse map.
 618   if (G1RSScrubVerbose) {
 619     gclog_or_tty->print_cr("Scrubbing region %u:", hr()->hrs_index());
 620   }
 621 
 622   assert(_coarse_map.size() == region_bm->size(), "Precondition");
 623   if (G1RSScrubVerbose) {
 624     gclog_or_tty->print("   Coarse map: before = "SIZE_FORMAT"...",
 625                         _n_coarse_entries);
 626   }
 627   _coarse_map.set_intersection(*region_bm);
 628   _n_coarse_entries = _coarse_map.count_one_bits();
 629   if (G1RSScrubVerbose) {
 630     gclog_or_tty->print_cr("   after = "SIZE_FORMAT".", _n_coarse_entries);
 631   }
 632 
 633   // Now do the fine-grained maps.
 634   for (size_t i = 0; i < _max_fine_entries; i++) {
 635     PerRegionTable* cur = _fine_grain_regions[i];
 636     PerRegionTable** prev = &_fine_grain_regions[i];
 637     while (cur != NULL) {
 638       PerRegionTable* nxt = cur->collision_list_next();
 639       // If the entire region is dead, eliminate.
 640       if (G1RSScrubVerbose) {
 641         gclog_or_tty->print_cr("     For other region %u:",
 642                                cur->hr()->hrs_index());
 643       }
 644       if (!region_bm->at((size_t) cur->hr()->hrs_index())) {
 645         *prev = nxt;
 646         cur->set_collision_list_next(NULL);
 647         _n_fine_entries--;
 648         if (G1RSScrubVerbose) {
 649           gclog_or_tty->print_cr("          deleted via region map.");
 650         }
 651         unlink_from_all(cur);
 652         PerRegionTable::free(cur);
 653       } else {
 654         // Do fine-grain elimination.
 655         if (G1RSScrubVerbose) {
 656           gclog_or_tty->print("          occ: before = %4d.", cur->occupied());
 657         }
 658         cur->scrub(ctbs, card_bm);
 659         if (G1RSScrubVerbose) {
 660           gclog_or_tty->print_cr("          after = %4d.", cur->occupied());
 661         }
 662         // Did that empty the table completely?
 663         if (cur->occupied() == 0) {
 664           *prev = nxt;
 665           cur->set_collision_list_next(NULL);
 666           _n_fine_entries--;
 667           unlink_from_all(cur);
 668           PerRegionTable::free(cur);
 669         } else {
 670           prev = cur->collision_list_next_addr();
 671         }
 672       }
 673       cur = nxt;
 674     }
 675   }
 676   // Since we may have deleted a from_card_cache entry from the RS, clear
 677   // the FCC.
 678   clear_fcc();
 679 }
 680 
 681 
 682 size_t OtherRegionsTable::occupied() const {
 683   // Cast away const in this case.
 684   MutexLockerEx x((Mutex*)&_m, Mutex::_no_safepoint_check_flag);
 685   size_t sum = occ_fine();
 686   sum += occ_sparse();
 687   sum += occ_coarse();
 688   return sum;
 689 }
 690 
 691 size_t OtherRegionsTable::occ_fine() const {
 692   size_t sum = 0;
 693 
 694   size_t num = 0;
 695   PerRegionTable * cur = _first_all_fine_prts;
 696   while (cur != NULL) {
 697     sum += cur->occupied();
 698     cur = cur->next();
 699     num++;
 700   }
 701   guarantee(num == _n_fine_entries, "just checking");
 702   return sum;
 703 }
 704 
 705 size_t OtherRegionsTable::occ_coarse() const {
 706   return (_n_coarse_entries * HeapRegion::CardsPerRegion);
 707 }
 708 
 709 size_t OtherRegionsTable::occ_sparse() const {
 710   return _sparse_table.occupied();
 711 }
 712 
 713 size_t OtherRegionsTable::mem_size() const {
 714   // Cast away const in this case.
 715   MutexLockerEx x((Mutex*)&_m, Mutex::_no_safepoint_check_flag);
 716   size_t sum = 0;
 717   PerRegionTable * cur = _first_all_fine_prts;
 718   while (cur != NULL) {
 719     sum += cur->mem_size();
 720     cur = cur->next();
 721   }
 722   sum += (sizeof(PerRegionTable*) * _max_fine_entries);
 723   sum += (_coarse_map.size_in_words() * HeapWordSize);
 724   sum += (_sparse_table.mem_size());
 725   sum += sizeof(*this) - sizeof(_sparse_table); // Avoid double counting above.
 726   return sum;
 727 }
 728 
 729 size_t OtherRegionsTable::static_mem_size() {
 730   return _from_card_cache_mem_size;
 731 }
 732 
 733 size_t OtherRegionsTable::fl_mem_size() {
 734   return PerRegionTable::fl_mem_size();
 735 }
 736 
 737 void OtherRegionsTable::clear_fcc() {
 738   size_t hrs_idx = hr()->hrs_index();
 739   for (int i = 0; i < HeapRegionRemSet::num_par_rem_sets(); i++) {
 740     _from_card_cache[i][hrs_idx] = -1;
 741   }
 742 }
 743 
 744 void OtherRegionsTable::clear() {
 745   MutexLockerEx x(&_m, Mutex::_no_safepoint_check_flag);
 746   // if there are no entries, skip this step
 747   if (_first_all_fine_prts != NULL) {
 748     guarantee(_first_all_fine_prts != NULL && _last_all_fine_prts != NULL, "just checking");
 749     PerRegionTable::bulk_free(_first_all_fine_prts, _last_all_fine_prts);
 750     memset(_fine_grain_regions, 0, _max_fine_entries * sizeof(_fine_grain_regions[0]));
 751   } else {
 752     guarantee(_first_all_fine_prts == NULL && _last_all_fine_prts == NULL, "just checking");
 753   }
 754 
 755   _first_all_fine_prts = _last_all_fine_prts = NULL;
 756   _sparse_table.clear();
 757   _coarse_map.clear();
 758   _n_fine_entries = 0;
 759   _n_coarse_entries = 0;
 760 
 761   clear_fcc();
 762 }
 763 
 764 void OtherRegionsTable::clear_incoming_entry(HeapRegion* from_hr) {
 765   MutexLockerEx x(&_m, Mutex::_no_safepoint_check_flag);
 766   size_t hrs_ind = (size_t) from_hr->hrs_index();
 767   size_t ind = hrs_ind & _mod_max_fine_entries_mask;
 768   if (del_single_region_table(ind, from_hr)) {
 769     assert(!_coarse_map.at(hrs_ind), "Inv");
 770   } else {
 771     _coarse_map.par_at_put(hrs_ind, 0);
 772   }
 773   // Check to see if any of the fcc entries come from here.
 774   size_t hr_ind = (size_t) hr()->hrs_index();
 775   for (int tid = 0; tid < HeapRegionRemSet::num_par_rem_sets(); tid++) {
 776     int fcc_ent = _from_card_cache[tid][hr_ind];
 777     if (fcc_ent != -1) {
 778       HeapWord* card_addr = (HeapWord*)
 779         (uintptr_t(fcc_ent) << CardTableModRefBS::card_shift);
 780       if (hr()->is_in_reserved(card_addr)) {
 781         // Clear the from card cache.
 782         _from_card_cache[tid][hr_ind] = -1;
 783       }
 784     }
 785   }
 786 }
 787 
 788 bool OtherRegionsTable::del_single_region_table(size_t ind,
 789                                                 HeapRegion* hr) {
 790   assert(0 <= ind && ind < _max_fine_entries, "Preconditions.");
 791   PerRegionTable** prev_addr = &_fine_grain_regions[ind];
 792   PerRegionTable* prt = *prev_addr;
 793   while (prt != NULL && prt->hr() != hr) {
 794     prev_addr = prt->collision_list_next_addr();
 795     prt = prt->collision_list_next();
 796   }
 797   if (prt != NULL) {
 798     assert(prt->hr() == hr, "Loop postcondition.");
 799     *prev_addr = prt->collision_list_next();
 800     unlink_from_all(prt);
 801     PerRegionTable::free(prt);
 802     _n_fine_entries--;
 803     return true;
 804   } else {
 805     return false;
 806   }
 807 }
 808 
 809 bool OtherRegionsTable::contains_reference(OopOrNarrowOopStar from) const {
 810   // Cast away const in this case.
 811   MutexLockerEx x((Mutex*)&_m, Mutex::_no_safepoint_check_flag);
 812   return contains_reference_locked(from);
 813 }
 814 
 815 bool OtherRegionsTable::contains_reference_locked(OopOrNarrowOopStar from) const {
 816   HeapRegion* hr = _g1h->heap_region_containing_raw(from);
 817   if (hr == NULL) return false;
 818   RegionIdx_t hr_ind = (RegionIdx_t) hr->hrs_index();
 819   // Is this region in the coarse map?
 820   if (_coarse_map.at(hr_ind)) return true;
 821 
 822   PerRegionTable* prt = find_region_table(hr_ind & _mod_max_fine_entries_mask,
 823                                      hr);
 824   if (prt != NULL) {
 825     return prt->contains_reference(from);
 826 
 827   } else {
 828     uintptr_t from_card =
 829       (uintptr_t(from) >> CardTableModRefBS::card_shift);
 830     uintptr_t hr_bot_card_index =
 831       uintptr_t(hr->bottom()) >> CardTableModRefBS::card_shift;
 832     assert(from_card >= hr_bot_card_index, "Inv");
 833     CardIdx_t card_index = from_card - hr_bot_card_index;
 834     assert(0 <= card_index && (size_t)card_index < HeapRegion::CardsPerRegion,
 835            "Must be in range.");
 836     return _sparse_table.contains_card(hr_ind, card_index);
 837   }
 838 
 839 
 840 }
 841 
 842 void
 843 OtherRegionsTable::do_cleanup_work(HRRSCleanupTask* hrrs_cleanup_task) {
 844   _sparse_table.do_cleanup_work(hrrs_cleanup_task);
 845 }
 846 
 847 // Determines how many threads can add records to an rset in parallel.
 848 // This can be done by either mutator threads together with the
 849 // concurrent refinement threads or GC threads.
 850 int HeapRegionRemSet::num_par_rem_sets() {
 851   return (int)MAX2(DirtyCardQueueSet::num_par_ids() + ConcurrentG1Refine::thread_num(), ParallelGCThreads);
 852 }
 853 
 854 HeapRegionRemSet::HeapRegionRemSet(G1BlockOffsetSharedArray* bosa,
 855                                    HeapRegion* hr)
 856   : _bosa(bosa), _other_regions(hr) {
 857   reset_for_par_iteration();
 858 }
 859 
 860 void HeapRegionRemSet::setup_remset_size() {
 861   // Setup sparse and fine-grain tables sizes.
 862   // table_size = base * (log(region_size / 1M) + 1)
 863   const int LOG_M = 20;
 864   int region_size_log_mb = MAX2(HeapRegion::LogOfHRGrainBytes - LOG_M, 0);
 865   if (FLAG_IS_DEFAULT(G1RSetSparseRegionEntries)) {
 866     G1RSetSparseRegionEntries = G1RSetSparseRegionEntriesBase * (region_size_log_mb + 1);
 867   }
 868   if (FLAG_IS_DEFAULT(G1RSetRegionEntries)) {
 869     G1RSetRegionEntries = G1RSetRegionEntriesBase * (region_size_log_mb + 1);
 870   }
 871   guarantee(G1RSetSparseRegionEntries > 0 && G1RSetRegionEntries > 0 , "Sanity");
 872 }
 873 
 874 bool HeapRegionRemSet::claim_iter() {
 875   if (_iter_state != Unclaimed) return false;
 876   jint res = Atomic::cmpxchg(Claimed, (jint*)(&_iter_state), Unclaimed);
 877   return (res == Unclaimed);
 878 }
 879 
 880 void HeapRegionRemSet::set_iter_complete() {
 881   _iter_state = Complete;
 882 }
 883 
 884 bool HeapRegionRemSet::iter_is_complete() {
 885   return _iter_state == Complete;
 886 }
 887 
 888 #ifndef PRODUCT
 889 void HeapRegionRemSet::print() const {
 890   HeapRegionRemSetIterator iter(this);
 891   size_t card_index;
 892   while (iter.has_next(card_index)) {
 893     HeapWord* card_start =
 894       G1CollectedHeap::heap()->bot_shared()->address_for_index(card_index);
 895     gclog_or_tty->print_cr("  Card " PTR_FORMAT, card_start);
 896   }
 897   if (iter.n_yielded() != occupied()) {
 898     gclog_or_tty->print_cr("Yielded disagrees with occupied:");
 899     gclog_or_tty->print_cr("  %6d yielded (%6d coarse, %6d fine).",
 900                   iter.n_yielded(),
 901                   iter.n_yielded_coarse(), iter.n_yielded_fine());
 902     gclog_or_tty->print_cr("  %6d occ     (%6d coarse, %6d fine).",
 903                   occupied(), occ_coarse(), occ_fine());
 904   }
 905   guarantee(iter.n_yielded() == occupied(),
 906             "We should have yielded all the represented cards.");
 907 }
 908 #endif
 909 
 910 void HeapRegionRemSet::cleanup() {
 911   SparsePRT::cleanup_all();
 912 }
 913 
 914 void HeapRegionRemSet::clear() {
 915   _other_regions.clear();
 916   assert(occupied() == 0, "Should be clear.");
 917   reset_for_par_iteration();
 918 }
 919 
 920 void HeapRegionRemSet::reset_for_par_iteration() {
 921   _iter_state = Unclaimed;
 922   _iter_claimed = 0;
 923   // It's good to check this to make sure that the two methods are in sync.
 924   assert(verify_ready_for_par_iteration(), "post-condition");
 925 }
 926 
 927 void HeapRegionRemSet::scrub(CardTableModRefBS* ctbs,
 928                              BitMap* region_bm, BitMap* card_bm) {
 929   _other_regions.scrub(ctbs, region_bm, card_bm);
 930 }
 931 
 932 //-------------------- Iteration --------------------
 933 
 934 HeapRegionRemSetIterator:: HeapRegionRemSetIterator(const HeapRegionRemSet* hrrs) :
 935   _hrrs(hrrs),
 936   _g1h(G1CollectedHeap::heap()),
 937   _coarse_map(&hrrs->_other_regions._coarse_map),
 938   _fine_grain_regions(hrrs->_other_regions._fine_grain_regions),
 939   _bosa(hrrs->bosa()),
 940   _is(Sparse),
 941   // Set these values so that we increment to the first region.
 942   _coarse_cur_region_index(-1),
 943   _coarse_cur_region_cur_card(HeapRegion::CardsPerRegion-1),
 944   _cur_region_cur_card(0),
 945   _fine_array_index(-1),
 946   _fine_cur_prt(NULL),
 947   _n_yielded_coarse(0),
 948   _n_yielded_fine(0),
 949   _n_yielded_sparse(0),
 950   _sparse_iter(&hrrs->_other_regions._sparse_table) {}
 951 
 952 bool HeapRegionRemSetIterator::coarse_has_next(size_t& card_index) {
 953   if (_hrrs->_other_regions._n_coarse_entries == 0) return false;
 954   // Go to the next card.
 955   _coarse_cur_region_cur_card++;
 956   // Was the last the last card in the current region?
 957   if (_coarse_cur_region_cur_card == HeapRegion::CardsPerRegion) {
 958     // Yes: find the next region.  This may leave _coarse_cur_region_index
 959     // Set to the last index, in which case there are no more coarse
 960     // regions.
 961     _coarse_cur_region_index =
 962       (int) _coarse_map->get_next_one_offset(_coarse_cur_region_index + 1);
 963     if ((size_t)_coarse_cur_region_index < _coarse_map->size()) {
 964       _coarse_cur_region_cur_card = 0;
 965       HeapWord* r_bot =
 966         _g1h->region_at((uint) _coarse_cur_region_index)->bottom();
 967       _cur_region_card_offset = _bosa->index_for(r_bot);
 968     } else {
 969       return false;
 970     }
 971   }
 972   // If we didn't return false above, then we can yield a card.
 973   card_index = _cur_region_card_offset + _coarse_cur_region_cur_card;
 974   return true;
 975 }
 976 
 977 void HeapRegionRemSetIterator::fine_find_next_non_null_prt() {
 978   // Otherwise, find the next bucket list in the array.
 979   _fine_array_index++;
 980   while (_fine_array_index < (int) OtherRegionsTable::_max_fine_entries) {
 981     _fine_cur_prt = _fine_grain_regions[_fine_array_index];
 982     if (_fine_cur_prt != NULL) return;
 983     else _fine_array_index++;
 984   }
 985   assert(_fine_cur_prt == NULL, "Loop post");
 986 }
 987 
 988 bool HeapRegionRemSetIterator::fine_has_next(size_t& card_index) {
 989   if (fine_has_next()) {
 990     _cur_region_cur_card =
 991       _fine_cur_prt->_bm.get_next_one_offset(_cur_region_cur_card + 1);
 992   }
 993   while (!fine_has_next()) {
 994     if (_cur_region_cur_card == (size_t) HeapRegion::CardsPerRegion) {
 995       _cur_region_cur_card = 0;
 996       _fine_cur_prt = _fine_cur_prt->collision_list_next();
 997     }
 998     if (_fine_cur_prt == NULL) {
 999       fine_find_next_non_null_prt();
1000       if (_fine_cur_prt == NULL) return false;
1001     }
1002     assert(_fine_cur_prt != NULL && _cur_region_cur_card == 0,
1003            "inv.");
1004     HeapWord* r_bot =
1005       _fine_cur_prt->hr()->bottom();
1006     _cur_region_card_offset = _bosa->index_for(r_bot);
1007     _cur_region_cur_card = _fine_cur_prt->_bm.get_next_one_offset(0);
1008   }
1009   assert(fine_has_next(), "Or else we exited the loop via the return.");
1010   card_index = _cur_region_card_offset + _cur_region_cur_card;
1011   return true;
1012 }
1013 
1014 bool HeapRegionRemSetIterator::fine_has_next() {
1015   return
1016     _fine_cur_prt != NULL &&
1017     _cur_region_cur_card < HeapRegion::CardsPerRegion;
1018 }
1019 
1020 bool HeapRegionRemSetIterator::has_next(size_t& card_index) {
1021   switch (_is) {
1022   case Sparse:
1023     if (_sparse_iter.has_next(card_index)) {
1024       _n_yielded_sparse++;
1025       return true;
1026     }
1027     // Otherwise, deliberate fall-through
1028     _is = Fine;
1029   case Fine:
1030     if (fine_has_next(card_index)) {
1031       _n_yielded_fine++;
1032       return true;
1033     }
1034     // Otherwise, deliberate fall-through
1035     _is = Coarse;
1036   case Coarse:
1037     if (coarse_has_next(card_index)) {
1038       _n_yielded_coarse++;
1039       return true;
1040     }
1041     // Otherwise...
1042     break;
1043   }
1044   assert(ParallelGCThreads > 1 ||
1045          n_yielded() == _hrrs->occupied(),
1046          "Should have yielded all the cards in the rem set "
1047          "(in the non-par case).");
1048   return false;
1049 }
1050 
1051 
1052 
1053 OopOrNarrowOopStar* HeapRegionRemSet::_recorded_oops = NULL;
1054 HeapWord**          HeapRegionRemSet::_recorded_cards = NULL;
1055 HeapRegion**        HeapRegionRemSet::_recorded_regions = NULL;
1056 int                 HeapRegionRemSet::_n_recorded = 0;
1057 
1058 HeapRegionRemSet::Event* HeapRegionRemSet::_recorded_events = NULL;
1059 int*         HeapRegionRemSet::_recorded_event_index = NULL;
1060 int          HeapRegionRemSet::_n_recorded_events = 0;
1061 
1062 void HeapRegionRemSet::record(HeapRegion* hr, OopOrNarrowOopStar f) {
1063   if (_recorded_oops == NULL) {
1064     assert(_n_recorded == 0
1065            && _recorded_cards == NULL
1066            && _recorded_regions == NULL,
1067            "Inv");
1068     _recorded_oops    = NEW_C_HEAP_ARRAY(OopOrNarrowOopStar, MaxRecorded, mtGC);
1069     _recorded_cards   = NEW_C_HEAP_ARRAY(HeapWord*,          MaxRecorded, mtGC);
1070     _recorded_regions = NEW_C_HEAP_ARRAY(HeapRegion*,        MaxRecorded, mtGC);
1071   }
1072   if (_n_recorded == MaxRecorded) {
1073     gclog_or_tty->print_cr("Filled up 'recorded' (%d).", MaxRecorded);
1074   } else {
1075     _recorded_cards[_n_recorded] =
1076       (HeapWord*)align_size_down(uintptr_t(f),
1077                                  CardTableModRefBS::card_size);
1078     _recorded_oops[_n_recorded] = f;
1079     _recorded_regions[_n_recorded] = hr;
1080     _n_recorded++;
1081   }
1082 }
1083 
1084 void HeapRegionRemSet::record_event(Event evnt) {
1085   if (!G1RecordHRRSEvents) return;
1086 
1087   if (_recorded_events == NULL) {
1088     assert(_n_recorded_events == 0
1089            && _recorded_event_index == NULL,
1090            "Inv");
1091     _recorded_events = NEW_C_HEAP_ARRAY(Event, MaxRecordedEvents, mtGC);
1092     _recorded_event_index = NEW_C_HEAP_ARRAY(int, MaxRecordedEvents, mtGC);
1093   }
1094   if (_n_recorded_events == MaxRecordedEvents) {
1095     gclog_or_tty->print_cr("Filled up 'recorded_events' (%d).", MaxRecordedEvents);
1096   } else {
1097     _recorded_events[_n_recorded_events] = evnt;
1098     _recorded_event_index[_n_recorded_events] = _n_recorded;
1099     _n_recorded_events++;
1100   }
1101 }
1102 
1103 void HeapRegionRemSet::print_event(outputStream* str, Event evnt) {
1104   switch (evnt) {
1105   case Event_EvacStart:
1106     str->print("Evac Start");
1107     break;
1108   case Event_EvacEnd:
1109     str->print("Evac End");
1110     break;
1111   case Event_RSUpdateEnd:
1112     str->print("RS Update End");
1113     break;
1114   }
1115 }
1116 
1117 void HeapRegionRemSet::print_recorded() {
1118   int cur_evnt = 0;
1119   Event cur_evnt_kind;
1120   int cur_evnt_ind = 0;
1121   if (_n_recorded_events > 0) {
1122     cur_evnt_kind = _recorded_events[cur_evnt];
1123     cur_evnt_ind = _recorded_event_index[cur_evnt];
1124   }
1125 
1126   for (int i = 0; i < _n_recorded; i++) {
1127     while (cur_evnt < _n_recorded_events && i == cur_evnt_ind) {
1128       gclog_or_tty->print("Event: ");
1129       print_event(gclog_or_tty, cur_evnt_kind);
1130       gclog_or_tty->print_cr("");
1131       cur_evnt++;
1132       if (cur_evnt < MaxRecordedEvents) {
1133         cur_evnt_kind = _recorded_events[cur_evnt];
1134         cur_evnt_ind = _recorded_event_index[cur_evnt];
1135       }
1136     }
1137     gclog_or_tty->print("Added card " PTR_FORMAT " to region [" PTR_FORMAT "...]"
1138                         " for ref " PTR_FORMAT ".\n",
1139                         _recorded_cards[i], _recorded_regions[i]->bottom(),
1140                         _recorded_oops[i]);
1141   }
1142 }
1143 
1144 void HeapRegionRemSet::reset_for_cleanup_tasks() {
1145   SparsePRT::reset_for_cleanup_tasks();
1146 }
1147 
1148 void HeapRegionRemSet::do_cleanup_work(HRRSCleanupTask* hrrs_cleanup_task) {
1149   _other_regions.do_cleanup_work(hrrs_cleanup_task);
1150 }
1151 
1152 void
1153 HeapRegionRemSet::finish_cleanup_task(HRRSCleanupTask* hrrs_cleanup_task) {
1154   SparsePRT::finish_cleanup_task(hrrs_cleanup_task);
1155 }
1156 
1157 #ifndef PRODUCT
1158 void HeapRegionRemSet::test_prt() {
1159   PerRegionTable::test();
1160 }
1161 
1162 void HeapRegionRemSet::test() {
1163   os::sleep(Thread::current(), (jlong)5000, false);
1164   G1CollectedHeap* g1h = G1CollectedHeap::heap();
1165 
1166   // Run with "-XX:G1LogRSetRegionEntries=2", so that 1 and 5 end up in same
1167   // hash bucket.
1168   HeapRegion* hr0 = g1h->region_at(0);
1169   HeapRegion* hr1 = g1h->region_at(1);
1170   HeapRegion* hr2 = g1h->region_at(5);
1171   HeapRegion* hr3 = g1h->region_at(6);
1172   HeapRegion* hr4 = g1h->region_at(7);
1173   HeapRegion* hr5 = g1h->region_at(8);
1174 
1175   HeapWord* hr1_start = hr1->bottom();
1176   HeapWord* hr1_mid = hr1_start + HeapRegion::GrainWords/2;
1177   HeapWord* hr1_last = hr1->end() - 1;
1178 
1179   HeapWord* hr2_start = hr2->bottom();
1180   HeapWord* hr2_mid = hr2_start + HeapRegion::GrainWords/2;
1181   HeapWord* hr2_last = hr2->end() - 1;
1182 
1183   HeapWord* hr3_start = hr3->bottom();
1184   HeapWord* hr3_mid = hr3_start + HeapRegion::GrainWords/2;
1185   HeapWord* hr3_last = hr3->end() - 1;
1186 
1187   HeapRegionRemSet* hrrs = hr0->rem_set();
1188 
1189   // Make three references from region 0x101...
1190   hrrs->add_reference((OopOrNarrowOopStar)hr1_start);
1191   hrrs->add_reference((OopOrNarrowOopStar)hr1_mid);
1192   hrrs->add_reference((OopOrNarrowOopStar)hr1_last);
1193 
1194   hrrs->add_reference((OopOrNarrowOopStar)hr2_start);
1195   hrrs->add_reference((OopOrNarrowOopStar)hr2_mid);
1196   hrrs->add_reference((OopOrNarrowOopStar)hr2_last);
1197 
1198   hrrs->add_reference((OopOrNarrowOopStar)hr3_start);
1199   hrrs->add_reference((OopOrNarrowOopStar)hr3_mid);
1200   hrrs->add_reference((OopOrNarrowOopStar)hr3_last);
1201 
1202   // Now cause a coarsening.
1203   hrrs->add_reference((OopOrNarrowOopStar)hr4->bottom());
1204   hrrs->add_reference((OopOrNarrowOopStar)hr5->bottom());
1205 
1206   // Now, does iteration yield these three?
1207   HeapRegionRemSetIterator iter(hrrs);
1208   size_t sum = 0;
1209   size_t card_index;
1210   while (iter.has_next(card_index)) {
1211     HeapWord* card_start =
1212       G1CollectedHeap::heap()->bot_shared()->address_for_index(card_index);
1213     gclog_or_tty->print_cr("  Card " PTR_FORMAT ".", card_start);
1214     sum++;
1215   }
1216   guarantee(sum == 11 - 3 + 2048, "Failure");
1217   guarantee(sum == hrrs->occupied(), "Failure");
1218 }
1219 #endif