1 /*
   2  * Copyright (c) 2001, 2015, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "gc/g1/concurrentG1Refine.hpp"
  27 #include "gc/g1/g1BlockOffsetTable.inline.hpp"
  28 #include "gc/g1/g1CollectedHeap.inline.hpp"
  29 #include "gc/g1/heapRegionManager.inline.hpp"
  30 #include "gc/g1/heapRegionRemSet.hpp"
  31 #include "gc/shared/space.inline.hpp"
  32 #include "memory/allocation.hpp"
  33 #include "memory/padded.inline.hpp"
  34 #include "oops/oop.inline.hpp"
  35 #include "runtime/atomic.inline.hpp"
  36 #include "utilities/bitMap.inline.hpp"
  37 #include "utilities/globalDefinitions.hpp"
  38 #include "utilities/growableArray.hpp"
  39 
  40 class PerRegionTable: public CHeapObj<mtGC> {
  41   friend class OtherRegionsTable;
  42   friend class HeapRegionRemSetIterator;
  43 
  44   HeapRegion*     _hr;
  45   BitMap          _bm;
  46   jint            _occupied;
  47 
  48   // next pointer for free/allocated 'all' list
  49   PerRegionTable* _next;
  50 
  51   // prev pointer for the allocated 'all' list
  52   PerRegionTable* _prev;
  53 
  54   // next pointer in collision list
  55   PerRegionTable * _collision_list_next;
  56 
  57   // Global free list of PRTs
  58   static PerRegionTable* _free_list;
  59 
  60 protected:
  61   // We need access in order to union things into the base table.
  62   BitMap* bm() { return &_bm; }
  63 
  64   void recount_occupied() {
  65     _occupied = (jint) bm()->count_one_bits();
  66   }
  67 
  68   PerRegionTable(HeapRegion* hr) :
  69     _hr(hr),
  70     _occupied(0),
  71     _bm(HeapRegion::CardsPerRegion, false /* in-resource-area */),
  72     _collision_list_next(NULL), _next(NULL), _prev(NULL)
  73   {}
  74 
  75   void add_card_work(CardIdx_t from_card, bool par) {
  76     if (!_bm.at(from_card)) {
  77       if (par) {
  78         if (_bm.par_at_put(from_card, 1)) {
  79           Atomic::inc(&_occupied);
  80         }
  81       } else {
  82         _bm.at_put(from_card, 1);
  83         _occupied++;
  84       }
  85     }
  86   }
  87 
  88   void add_reference_work(OopOrNarrowOopStar from, bool par) {
  89     // Must make this robust in case "from" is not in "_hr", because of
  90     // concurrency.
  91 
  92     log_develop(gc, remset)("    PRT::Add_reference_work(" PTR_FORMAT "->" PTR_FORMAT ").",
  93                             p2i(from),
  94                             UseCompressedOops
  95                             ? p2i(oopDesc::load_decode_heap_oop((narrowOop*)from))
  96                             : p2i(oopDesc::load_decode_heap_oop((oop*)from)));
  97 
  98     HeapRegion* loc_hr = hr();
  99     // If the test below fails, then this table was reused concurrently
 100     // with this operation.  This is OK, since the old table was coarsened,
 101     // and adding a bit to the new table is never incorrect.
 102     // If the table used to belong to a continues humongous region and is
 103     // now reused for the corresponding start humongous region, we need to
 104     // make sure that we detect this. Thus, we call is_in_reserved_raw()
 105     // instead of just is_in_reserved() here.
 106     if (loc_hr->is_in_reserved_raw(from)) {
 107       size_t hw_offset = pointer_delta((HeapWord*)from, loc_hr->bottom());
 108       CardIdx_t from_card = (CardIdx_t)
 109           hw_offset >> (CardTableModRefBS::card_shift - LogHeapWordSize);
 110 
 111       assert(0 <= from_card && (size_t)from_card < HeapRegion::CardsPerRegion,
 112              "Must be in range.");
 113       add_card_work(from_card, par);
 114     }
 115   }
 116 
 117 public:
 118 
 119   HeapRegion* hr() const { return _hr; }
 120 
 121   jint occupied() const {
 122     // Overkill, but if we ever need it...
 123     // guarantee(_occupied == _bm.count_one_bits(), "Check");
 124     return _occupied;
 125   }
 126 
 127   void init(HeapRegion* hr, bool clear_links_to_all_list) {
 128     if (clear_links_to_all_list) {
 129       set_next(NULL);
 130       set_prev(NULL);
 131     }
 132     _hr = hr;
 133     _collision_list_next = NULL;
 134     _occupied = 0;
 135     _bm.clear();
 136   }
 137 
 138   void add_reference(OopOrNarrowOopStar from) {
 139     add_reference_work(from, /*parallel*/ true);
 140   }
 141 
 142   void seq_add_reference(OopOrNarrowOopStar from) {
 143     add_reference_work(from, /*parallel*/ false);
 144   }
 145 
 146   void scrub(CardTableModRefBS* ctbs, BitMap* card_bm) {
 147     HeapWord* hr_bot = hr()->bottom();
 148     size_t hr_first_card_index = ctbs->index_for(hr_bot);
 149     bm()->set_intersection_at_offset(*card_bm, hr_first_card_index);
 150     recount_occupied();
 151   }
 152 
 153   void add_card(CardIdx_t from_card_index) {
 154     add_card_work(from_card_index, /*parallel*/ true);
 155   }
 156 
 157   void seq_add_card(CardIdx_t from_card_index) {
 158     add_card_work(from_card_index, /*parallel*/ false);
 159   }
 160 
 161   // (Destructively) union the bitmap of the current table into the given
 162   // bitmap (which is assumed to be of the same size.)
 163   void union_bitmap_into(BitMap* bm) {
 164     bm->set_union(_bm);
 165   }
 166 
 167   // Mem size in bytes.
 168   size_t mem_size() const {
 169     return sizeof(PerRegionTable) + _bm.size_in_words() * HeapWordSize;
 170   }
 171 
 172   // Requires "from" to be in "hr()".
 173   bool contains_reference(OopOrNarrowOopStar from) const {
 174     assert(hr()->is_in_reserved(from), "Precondition.");
 175     size_t card_ind = pointer_delta(from, hr()->bottom(),
 176                                     CardTableModRefBS::card_size);
 177     return _bm.at(card_ind);
 178   }
 179 
 180   // Bulk-free the PRTs from prt to last, assumes that they are
 181   // linked together using their _next field.
 182   static void bulk_free(PerRegionTable* prt, PerRegionTable* last) {
 183     while (true) {
 184       PerRegionTable* fl = _free_list;
 185       last->set_next(fl);
 186       PerRegionTable* res = (PerRegionTable*) Atomic::cmpxchg_ptr(prt, &_free_list, fl);
 187       if (res == fl) {
 188         return;
 189       }
 190     }
 191     ShouldNotReachHere();
 192   }
 193 
 194   static void free(PerRegionTable* prt) {
 195     bulk_free(prt, prt);
 196   }
 197 
 198   // Returns an initialized PerRegionTable instance.
 199   static PerRegionTable* alloc(HeapRegion* hr) {
 200     PerRegionTable* fl = _free_list;
 201     while (fl != NULL) {
 202       PerRegionTable* nxt = fl->next();
 203       PerRegionTable* res =
 204         (PerRegionTable*)
 205         Atomic::cmpxchg_ptr(nxt, &_free_list, fl);
 206       if (res == fl) {
 207         fl->init(hr, true);
 208         return fl;
 209       } else {
 210         fl = _free_list;
 211       }
 212     }
 213     assert(fl == NULL, "Loop condition.");
 214     return new PerRegionTable(hr);
 215   }
 216 
 217   PerRegionTable* next() const { return _next; }
 218   void set_next(PerRegionTable* next) { _next = next; }
 219   PerRegionTable* prev() const { return _prev; }
 220   void set_prev(PerRegionTable* prev) { _prev = prev; }
 221 
 222   // Accessor and Modification routines for the pointer for the
 223   // singly linked collision list that links the PRTs within the
 224   // OtherRegionsTable::_fine_grain_regions hash table.
 225   //
 226   // It might be useful to also make the collision list doubly linked
 227   // to avoid iteration over the collisions list during scrubbing/deletion.
 228   // OTOH there might not be many collisions.
 229 
 230   PerRegionTable* collision_list_next() const {
 231     return _collision_list_next;
 232   }
 233 
 234   void set_collision_list_next(PerRegionTable* next) {
 235     _collision_list_next = next;
 236   }
 237 
 238   PerRegionTable** collision_list_next_addr() {
 239     return &_collision_list_next;
 240   }
 241 
 242   static size_t fl_mem_size() {
 243     PerRegionTable* cur = _free_list;
 244     size_t res = 0;
 245     while (cur != NULL) {
 246       res += cur->mem_size();
 247       cur = cur->next();
 248     }
 249     return res;
 250   }
 251 
 252   static void test_fl_mem_size();
 253 };
 254 
 255 PerRegionTable* PerRegionTable::_free_list = NULL;
 256 
 257 size_t OtherRegionsTable::_max_fine_entries = 0;
 258 size_t OtherRegionsTable::_mod_max_fine_entries_mask = 0;
 259 size_t OtherRegionsTable::_fine_eviction_stride = 0;
 260 size_t OtherRegionsTable::_fine_eviction_sample_size = 0;
 261 
 262 OtherRegionsTable::OtherRegionsTable(HeapRegion* hr, Mutex* m) :
 263   _g1h(G1CollectedHeap::heap()),
 264   _hr(hr), _m(m),
 265   _coarse_map(G1CollectedHeap::heap()->max_regions(),
 266               false /* in-resource-area */),
 267   _fine_grain_regions(NULL),
 268   _first_all_fine_prts(NULL), _last_all_fine_prts(NULL),
 269   _n_fine_entries(0), _n_coarse_entries(0),
 270   _fine_eviction_start(0),
 271   _sparse_table(hr)
 272 {
 273   typedef PerRegionTable* PerRegionTablePtr;
 274 
 275   if (_max_fine_entries == 0) {
 276     assert(_mod_max_fine_entries_mask == 0, "Both or none.");
 277     size_t max_entries_log = (size_t)log2_long((jlong)G1RSetRegionEntries);
 278     _max_fine_entries = (size_t)1 << max_entries_log;
 279     _mod_max_fine_entries_mask = _max_fine_entries - 1;
 280 
 281     assert(_fine_eviction_sample_size == 0
 282            && _fine_eviction_stride == 0, "All init at same time.");
 283     _fine_eviction_sample_size = MAX2((size_t)4, max_entries_log);
 284     _fine_eviction_stride = _max_fine_entries / _fine_eviction_sample_size;
 285   }
 286 
 287   _fine_grain_regions = NEW_C_HEAP_ARRAY3(PerRegionTablePtr, _max_fine_entries,
 288                         mtGC, CURRENT_PC, AllocFailStrategy::RETURN_NULL);
 289 
 290   if (_fine_grain_regions == NULL) {
 291     vm_exit_out_of_memory(sizeof(void*)*_max_fine_entries, OOM_MALLOC_ERROR,
 292                           "Failed to allocate _fine_grain_entries.");
 293   }
 294 
 295   for (size_t i = 0; i < _max_fine_entries; i++) {
 296     _fine_grain_regions[i] = NULL;
 297   }
 298 }
 299 
 300 void OtherRegionsTable::link_to_all(PerRegionTable* prt) {
 301   // We always append to the beginning of the list for convenience;
 302   // the order of entries in this list does not matter.
 303   if (_first_all_fine_prts != NULL) {
 304     assert(_first_all_fine_prts->prev() == NULL, "invariant");
 305     _first_all_fine_prts->set_prev(prt);
 306     prt->set_next(_first_all_fine_prts);
 307   } else {
 308     // this is the first element we insert. Adjust the "last" pointer
 309     _last_all_fine_prts = prt;
 310     assert(prt->next() == NULL, "just checking");
 311   }
 312   // the new element is always the first element without a predecessor
 313   prt->set_prev(NULL);
 314   _first_all_fine_prts = prt;
 315 
 316   assert(prt->prev() == NULL, "just checking");
 317   assert(_first_all_fine_prts == prt, "just checking");
 318   assert((_first_all_fine_prts == NULL && _last_all_fine_prts == NULL) ||
 319          (_first_all_fine_prts != NULL && _last_all_fine_prts != NULL),
 320          "just checking");
 321   assert(_last_all_fine_prts == NULL || _last_all_fine_prts->next() == NULL,
 322          "just checking");
 323   assert(_first_all_fine_prts == NULL || _first_all_fine_prts->prev() == NULL,
 324          "just checking");
 325 }
 326 
 327 void OtherRegionsTable::unlink_from_all(PerRegionTable* prt) {
 328   if (prt->prev() != NULL) {
 329     assert(_first_all_fine_prts != prt, "just checking");
 330     prt->prev()->set_next(prt->next());
 331     // removing the last element in the list?
 332     if (_last_all_fine_prts == prt) {
 333       _last_all_fine_prts = prt->prev();
 334     }
 335   } else {
 336     assert(_first_all_fine_prts == prt, "just checking");
 337     _first_all_fine_prts = prt->next();
 338     // list is empty now?
 339     if (_first_all_fine_prts == NULL) {
 340       _last_all_fine_prts = NULL;
 341     }
 342   }
 343 
 344   if (prt->next() != NULL) {
 345     prt->next()->set_prev(prt->prev());
 346   }
 347 
 348   prt->set_next(NULL);
 349   prt->set_prev(NULL);
 350 
 351   assert((_first_all_fine_prts == NULL && _last_all_fine_prts == NULL) ||
 352          (_first_all_fine_prts != NULL && _last_all_fine_prts != NULL),
 353          "just checking");
 354   assert(_last_all_fine_prts == NULL || _last_all_fine_prts->next() == NULL,
 355          "just checking");
 356   assert(_first_all_fine_prts == NULL || _first_all_fine_prts->prev() == NULL,
 357          "just checking");
 358 }
 359 
 360 int**  FromCardCache::_cache = NULL;
 361 uint   FromCardCache::_max_regions = 0;
 362 size_t FromCardCache::_static_mem_size = 0;
 363 
 364 void FromCardCache::initialize(uint n_par_rs, uint max_num_regions) {
 365   guarantee(_cache == NULL, "Should not call this multiple times");
 366 
 367   _max_regions = max_num_regions;
 368   _cache = Padded2DArray<int, mtGC>::create_unfreeable(n_par_rs,
 369                                                        _max_regions,
 370                                                        &_static_mem_size);
 371 
 372   invalidate(0, _max_regions);
 373 }
 374 
 375 void FromCardCache::invalidate(uint start_idx, size_t new_num_regions) {
 376   guarantee((size_t)start_idx + new_num_regions <= max_uintx,
 377             "Trying to invalidate beyond maximum region, from %u size " SIZE_FORMAT,
 378             start_idx, new_num_regions);
 379   for (uint i = 0; i < HeapRegionRemSet::num_par_rem_sets(); i++) {
 380     uint end_idx = (start_idx + (uint)new_num_regions);
 381     assert(end_idx <= _max_regions, "Must be within max.");
 382     for (uint j = start_idx; j < end_idx; j++) {
 383       set(i, j, InvalidCard);
 384     }
 385   }
 386 }
 387 
 388 #ifndef PRODUCT
 389 void FromCardCache::print(outputStream* out) {
 390   for (uint i = 0; i < HeapRegionRemSet::num_par_rem_sets(); i++) {
 391     for (uint j = 0; j < _max_regions; j++) {
 392       out->print_cr("_from_card_cache[%u][%u] = %d.",
 393                     i, j, at(i, j));
 394     }
 395   }
 396 }
 397 #endif
 398 
 399 void FromCardCache::clear(uint region_idx) {
 400   uint num_par_remsets = HeapRegionRemSet::num_par_rem_sets();
 401   for (uint i = 0; i < num_par_remsets; i++) {
 402     set(i, region_idx, InvalidCard);
 403   }
 404 }
 405 
 406 void OtherRegionsTable::add_reference(OopOrNarrowOopStar from, uint tid) {
 407   uint cur_hrm_ind = _hr->hrm_index();
 408 
 409   log_develop(gc, remset)("ORT::add_reference_work(" PTR_FORMAT "->" PTR_FORMAT ").",
 410                                                    p2i(from),
 411                                                    UseCompressedOops
 412                                                    ? p2i(oopDesc::load_decode_heap_oop((narrowOop*)from))
 413                                                    : p2i(oopDesc::load_decode_heap_oop((oop*)from)));
 414 
 415   int from_card = (int)(uintptr_t(from) >> CardTableModRefBS::card_shift);
 416 
 417   log_develop(gc, remset)("Table for [" PTR_FORMAT "...): card %d (cache = %d)",
 418                           p2i(_hr->bottom()), from_card,
 419                           FromCardCache::at(tid, cur_hrm_ind));
 420 
 421   if (FromCardCache::contains_or_replace(tid, cur_hrm_ind, from_card)) {
 422     log_develop(gc, remset)("  from-card cache hit.");
 423     assert(contains_reference(from), "We just added it!");
 424     return;
 425   }
 426 
 427   // Note that this may be a continued H region.
 428   HeapRegion* from_hr = _g1h->heap_region_containing_raw(from);
 429   RegionIdx_t from_hrm_ind = (RegionIdx_t) from_hr->hrm_index();
 430 
 431   // If the region is already coarsened, return.
 432   if (_coarse_map.at(from_hrm_ind)) {
 433     log_develop(gc, remset)("  coarse map hit.");
 434     assert(contains_reference(from), "We just added it!");
 435     return;
 436   }
 437 
 438   // Otherwise find a per-region table to add it to.
 439   size_t ind = from_hrm_ind & _mod_max_fine_entries_mask;
 440   PerRegionTable* prt = find_region_table(ind, from_hr);
 441   if (prt == NULL) {
 442     MutexLockerEx x(_m, Mutex::_no_safepoint_check_flag);
 443     // Confirm that it's really not there...
 444     prt = find_region_table(ind, from_hr);
 445     if (prt == NULL) {
 446 
 447       uintptr_t from_hr_bot_card_index =
 448         uintptr_t(from_hr->bottom())
 449           >> CardTableModRefBS::card_shift;
 450       CardIdx_t card_index = from_card - from_hr_bot_card_index;
 451       assert(0 <= card_index && (size_t)card_index < HeapRegion::CardsPerRegion,
 452              "Must be in range.");
 453       if (G1HRRSUseSparseTable &&
 454           _sparse_table.add_card(from_hrm_ind, card_index)) {
 455         log_develop(gc, remset)("   added card to sparse table.");
 456         assert(contains_reference_locked(from), "We just added it!");
 457         return;
 458       } else {
 459         log_develop(gc, remset)("   [tid %u] sparse table entry overflow(f: %d, t: %u)",
 460                                 tid, from_hrm_ind, cur_hrm_ind);
 461       }
 462 
 463       if (_n_fine_entries == _max_fine_entries) {
 464         prt = delete_region_table();
 465         // There is no need to clear the links to the 'all' list here:
 466         // prt will be reused immediately, i.e. remain in the 'all' list.
 467         prt->init(from_hr, false /* clear_links_to_all_list */);
 468       } else {
 469         prt = PerRegionTable::alloc(from_hr);
 470         link_to_all(prt);
 471       }
 472 
 473       PerRegionTable* first_prt = _fine_grain_regions[ind];
 474       prt->set_collision_list_next(first_prt);
 475       // The assignment into _fine_grain_regions allows the prt to
 476       // start being used concurrently. In addition to
 477       // collision_list_next which must be visible (else concurrent
 478       // parsing of the list, if any, may fail to see other entries),
 479       // the content of the prt must be visible (else for instance
 480       // some mark bits may not yet seem cleared or a 'later' update
 481       // performed by a concurrent thread could be undone when the
 482       // zeroing becomes visible). This requires store ordering.
 483       OrderAccess::release_store_ptr((volatile PerRegionTable*)&_fine_grain_regions[ind], prt);
 484       _n_fine_entries++;
 485 
 486       if (G1HRRSUseSparseTable) {
 487         // Transfer from sparse to fine-grain.
 488         SparsePRTEntry *sprt_entry = _sparse_table.get_entry(from_hrm_ind);
 489         assert(sprt_entry != NULL, "There should have been an entry");
 490         for (int i = 0; i < SparsePRTEntry::cards_num(); i++) {
 491           CardIdx_t c = sprt_entry->card(i);
 492           if (c != SparsePRTEntry::NullEntry) {
 493             prt->add_card(c);
 494           }
 495         }
 496         // Now we can delete the sparse entry.
 497         bool res = _sparse_table.delete_entry(from_hrm_ind);
 498         assert(res, "It should have been there.");
 499       }
 500     }
 501     assert(prt != NULL && prt->hr() == from_hr, "consequence");
 502   }
 503   // Note that we can't assert "prt->hr() == from_hr", because of the
 504   // possibility of concurrent reuse.  But see head comment of
 505   // OtherRegionsTable for why this is OK.
 506   assert(prt != NULL, "Inv");
 507 
 508   prt->add_reference(from);
 509   assert(contains_reference(from), "We just added it!");
 510 }
 511 
 512 PerRegionTable*
 513 OtherRegionsTable::find_region_table(size_t ind, HeapRegion* hr) const {
 514   assert(ind < _max_fine_entries, "Preconditions.");
 515   PerRegionTable* prt = _fine_grain_regions[ind];
 516   while (prt != NULL && prt->hr() != hr) {
 517     prt = prt->collision_list_next();
 518   }
 519   // Loop postcondition is the method postcondition.
 520   return prt;
 521 }
 522 
 523 jint OtherRegionsTable::_n_coarsenings = 0;
 524 
 525 PerRegionTable* OtherRegionsTable::delete_region_table() {
 526   assert(_m->owned_by_self(), "Precondition");
 527   assert(_n_fine_entries == _max_fine_entries, "Precondition");
 528   PerRegionTable* max = NULL;
 529   jint max_occ = 0;
 530   PerRegionTable** max_prev = NULL;
 531   size_t max_ind;
 532 
 533   size_t i = _fine_eviction_start;
 534   for (size_t k = 0; k < _fine_eviction_sample_size; k++) {
 535     size_t ii = i;
 536     // Make sure we get a non-NULL sample.
 537     while (_fine_grain_regions[ii] == NULL) {
 538       ii++;
 539       if (ii == _max_fine_entries) ii = 0;
 540       guarantee(ii != i, "We must find one.");
 541     }
 542     PerRegionTable** prev = &_fine_grain_regions[ii];
 543     PerRegionTable* cur = *prev;
 544     while (cur != NULL) {
 545       jint cur_occ = cur->occupied();
 546       if (max == NULL || cur_occ > max_occ) {
 547         max = cur;
 548         max_prev = prev;
 549         max_ind = i;
 550         max_occ = cur_occ;
 551       }
 552       prev = cur->collision_list_next_addr();
 553       cur = cur->collision_list_next();
 554     }
 555     i = i + _fine_eviction_stride;
 556     if (i >= _n_fine_entries) i = i - _n_fine_entries;
 557   }
 558 
 559   _fine_eviction_start++;
 560 
 561   if (_fine_eviction_start >= _n_fine_entries) {
 562     _fine_eviction_start -= _n_fine_entries;
 563   }
 564 
 565   guarantee(max != NULL, "Since _n_fine_entries > 0");
 566   guarantee(max_prev != NULL, "Since max != NULL.");
 567 
 568   // Set the corresponding coarse bit.
 569   size_t max_hrm_index = (size_t) max->hr()->hrm_index();
 570   if (!_coarse_map.at(max_hrm_index)) {
 571     _coarse_map.at_put(max_hrm_index, true);
 572     _n_coarse_entries++;
 573       log_develop(gc, remset)("Coarsened entry in region [" PTR_FORMAT "...] for region [" PTR_FORMAT "...] (" SIZE_FORMAT " coarse entries)",
 574                               p2i(_hr->bottom()), p2i(max->hr()->bottom()), _n_coarse_entries);
 575   }
 576 
 577   // Unsplice.
 578   *max_prev = max->collision_list_next();
 579   Atomic::inc(&_n_coarsenings);
 580   _n_fine_entries--;
 581   return max;
 582 }
 583 
 584 void OtherRegionsTable::scrub(CardTableModRefBS* ctbs,
 585                               BitMap* region_bm, BitMap* card_bm) {
 586   // First eliminated garbage regions from the coarse map.
 587   log_develop(gc, remset, scrub)("Scrubbing region %u:", _hr->hrm_index());
 588 
 589   assert(_coarse_map.size() == region_bm->size(), "Precondition");
 590   log_develop(gc, remset, scrub)("   Coarse map: before = " SIZE_FORMAT "...", _n_coarse_entries);
 591   _coarse_map.set_intersection(*region_bm);
 592   _n_coarse_entries = _coarse_map.count_one_bits();
 593   log_develop(gc, remset, scrub)("   after = " SIZE_FORMAT ".", _n_coarse_entries);
 594 
 595   // Now do the fine-grained maps.
 596   for (size_t i = 0; i < _max_fine_entries; i++) {
 597     PerRegionTable* cur = _fine_grain_regions[i];
 598     PerRegionTable** prev = &_fine_grain_regions[i];
 599     while (cur != NULL) {
 600       PerRegionTable* nxt = cur->collision_list_next();
 601       // If the entire region is dead, eliminate.
 602       log_develop(gc, remset, scrub)("     For other region %u:", cur->hr()->hrm_index());
 603       if (!region_bm->at((size_t) cur->hr()->hrm_index())) {
 604         *prev = nxt;
 605         cur->set_collision_list_next(NULL);
 606         _n_fine_entries--;
 607         log_develop(gc, remset, scrub)("          deleted via region map.");
 608         unlink_from_all(cur);
 609         PerRegionTable::free(cur);
 610       } else {
 611         // Do fine-grain elimination.
 612         log_develop(gc, remset, scrub)("          occ: before = %4d.", cur->occupied());
 613         cur->scrub(ctbs, card_bm);
 614         log_develop(gc, remset, scrub)("          after = %4d.", cur->occupied());
 615         // Did that empty the table completely?
 616         if (cur->occupied() == 0) {
 617           *prev = nxt;
 618           cur->set_collision_list_next(NULL);
 619           _n_fine_entries--;
 620           unlink_from_all(cur);
 621           PerRegionTable::free(cur);
 622         } else {
 623           prev = cur->collision_list_next_addr();
 624         }
 625       }
 626       cur = nxt;
 627     }
 628   }
 629   // Since we may have deleted a from_card_cache entry from the RS, clear
 630   // the FCC.
 631   clear_fcc();
 632 }
 633 
 634 bool OtherRegionsTable::occupancy_less_or_equal_than(size_t limit) const {
 635   if (limit <= (size_t)G1RSetSparseRegionEntries) {
 636     return occ_coarse() == 0 && _first_all_fine_prts == NULL && occ_sparse() <= limit;
 637   } else {
 638     // Current uses of this method may only use values less than G1RSetSparseRegionEntries
 639     // for the limit. The solution, comparing against occupied() would be too slow
 640     // at this time.
 641     Unimplemented();
 642     return false;
 643   }
 644 }
 645 
 646 bool OtherRegionsTable::is_empty() const {
 647   return occ_sparse() == 0 && occ_coarse() == 0 && _first_all_fine_prts == NULL;
 648 }
 649 
 650 size_t OtherRegionsTable::occupied() const {
 651   size_t sum = occ_fine();
 652   sum += occ_sparse();
 653   sum += occ_coarse();
 654   return sum;
 655 }
 656 
 657 size_t OtherRegionsTable::occ_fine() const {
 658   size_t sum = 0;
 659 
 660   size_t num = 0;
 661   PerRegionTable * cur = _first_all_fine_prts;
 662   while (cur != NULL) {
 663     sum += cur->occupied();
 664     cur = cur->next();
 665     num++;
 666   }
 667   guarantee(num == _n_fine_entries, "just checking");
 668   return sum;
 669 }
 670 
 671 size_t OtherRegionsTable::occ_coarse() const {
 672   return (_n_coarse_entries * HeapRegion::CardsPerRegion);
 673 }
 674 
 675 size_t OtherRegionsTable::occ_sparse() const {
 676   return _sparse_table.occupied();
 677 }
 678 
 679 size_t OtherRegionsTable::mem_size() const {
 680   size_t sum = 0;
 681   // all PRTs are of the same size so it is sufficient to query only one of them.
 682   if (_first_all_fine_prts != NULL) {
 683     assert(_last_all_fine_prts != NULL &&
 684       _first_all_fine_prts->mem_size() == _last_all_fine_prts->mem_size(), "check that mem_size() is constant");
 685     sum += _first_all_fine_prts->mem_size() * _n_fine_entries;
 686   }
 687   sum += (sizeof(PerRegionTable*) * _max_fine_entries);
 688   sum += (_coarse_map.size_in_words() * HeapWordSize);
 689   sum += (_sparse_table.mem_size());
 690   sum += sizeof(OtherRegionsTable) - sizeof(_sparse_table); // Avoid double counting above.
 691   return sum;
 692 }
 693 
 694 size_t OtherRegionsTable::static_mem_size() {
 695   return FromCardCache::static_mem_size();
 696 }
 697 
 698 size_t OtherRegionsTable::fl_mem_size() {
 699   return PerRegionTable::fl_mem_size();
 700 }
 701 
 702 void OtherRegionsTable::clear_fcc() {
 703   FromCardCache::clear(_hr->hrm_index());
 704 }
 705 
 706 void OtherRegionsTable::clear() {
 707   // if there are no entries, skip this step
 708   if (_first_all_fine_prts != NULL) {
 709     guarantee(_first_all_fine_prts != NULL && _last_all_fine_prts != NULL, "just checking");
 710     PerRegionTable::bulk_free(_first_all_fine_prts, _last_all_fine_prts);
 711     memset(_fine_grain_regions, 0, _max_fine_entries * sizeof(_fine_grain_regions[0]));
 712   } else {
 713     guarantee(_first_all_fine_prts == NULL && _last_all_fine_prts == NULL, "just checking");
 714   }
 715 
 716   _first_all_fine_prts = _last_all_fine_prts = NULL;
 717   _sparse_table.clear();
 718   _coarse_map.clear();
 719   _n_fine_entries = 0;
 720   _n_coarse_entries = 0;
 721 
 722   clear_fcc();
 723 }
 724 
 725 bool OtherRegionsTable::contains_reference(OopOrNarrowOopStar from) const {
 726   // Cast away const in this case.
 727   MutexLockerEx x((Mutex*)_m, Mutex::_no_safepoint_check_flag);
 728   return contains_reference_locked(from);
 729 }
 730 
 731 bool OtherRegionsTable::contains_reference_locked(OopOrNarrowOopStar from) const {
 732   HeapRegion* hr = _g1h->heap_region_containing_raw(from);
 733   RegionIdx_t hr_ind = (RegionIdx_t) hr->hrm_index();
 734   // Is this region in the coarse map?
 735   if (_coarse_map.at(hr_ind)) return true;
 736 
 737   PerRegionTable* prt = find_region_table(hr_ind & _mod_max_fine_entries_mask,
 738                                      hr);
 739   if (prt != NULL) {
 740     return prt->contains_reference(from);
 741 
 742   } else {
 743     uintptr_t from_card =
 744       (uintptr_t(from) >> CardTableModRefBS::card_shift);
 745     uintptr_t hr_bot_card_index =
 746       uintptr_t(hr->bottom()) >> CardTableModRefBS::card_shift;
 747     assert(from_card >= hr_bot_card_index, "Inv");
 748     CardIdx_t card_index = from_card - hr_bot_card_index;
 749     assert(0 <= card_index && (size_t)card_index < HeapRegion::CardsPerRegion,
 750            "Must be in range.");
 751     return _sparse_table.contains_card(hr_ind, card_index);
 752   }
 753 }
 754 
 755 void
 756 OtherRegionsTable::do_cleanup_work(HRRSCleanupTask* hrrs_cleanup_task) {
 757   _sparse_table.do_cleanup_work(hrrs_cleanup_task);
 758 }
 759 
 760 // Determines how many threads can add records to an rset in parallel.
 761 // This can be done by either mutator threads together with the
 762 // concurrent refinement threads or GC threads.
 763 uint HeapRegionRemSet::num_par_rem_sets() {
 764   return MAX2(DirtyCardQueueSet::num_par_ids() + ConcurrentG1Refine::thread_num(), ParallelGCThreads);
 765 }
 766 
 767 HeapRegionRemSet::HeapRegionRemSet(G1BlockOffsetSharedArray* bosa,
 768                                    HeapRegion* hr)
 769   : _bosa(bosa),
 770     _m(Mutex::leaf, FormatBuffer<128>("HeapRegionRemSet lock #%u", hr->hrm_index()), true, Monitor::_safepoint_check_never),
 771     _code_roots(), _other_regions(hr, &_m), _iter_state(Unclaimed), _iter_claimed(0) {
 772   reset_for_par_iteration();
 773 }
 774 
 775 void HeapRegionRemSet::setup_remset_size() {
 776   // Setup sparse and fine-grain tables sizes.
 777   // table_size = base * (log(region_size / 1M) + 1)
 778   const int LOG_M = 20;
 779   int region_size_log_mb = MAX2(HeapRegion::LogOfHRGrainBytes - LOG_M, 0);
 780   if (FLAG_IS_DEFAULT(G1RSetSparseRegionEntries)) {
 781     G1RSetSparseRegionEntries = G1RSetSparseRegionEntriesBase * (region_size_log_mb + 1);
 782   }
 783   if (FLAG_IS_DEFAULT(G1RSetRegionEntries)) {
 784     G1RSetRegionEntries = G1RSetRegionEntriesBase * (region_size_log_mb + 1);
 785   }
 786   guarantee(G1RSetSparseRegionEntries > 0 && G1RSetRegionEntries > 0 , "Sanity");
 787 }
 788 
 789 bool HeapRegionRemSet::claim_iter() {
 790   if (_iter_state != Unclaimed) return false;
 791   jint res = Atomic::cmpxchg(Claimed, (jint*)(&_iter_state), Unclaimed);
 792   return (res == Unclaimed);
 793 }
 794 
 795 void HeapRegionRemSet::set_iter_complete() {
 796   _iter_state = Complete;
 797 }
 798 
 799 bool HeapRegionRemSet::iter_is_complete() {
 800   return _iter_state == Complete;
 801 }
 802 
 803 #ifndef PRODUCT
 804 void HeapRegionRemSet::print() {
 805   HeapRegionRemSetIterator iter(this);
 806   size_t card_index;
 807   while (iter.has_next(card_index)) {
 808     HeapWord* card_start =
 809       G1CollectedHeap::heap()->bot_shared()->address_for_index(card_index);
 810     tty->print_cr("  Card " PTR_FORMAT, p2i(card_start));
 811   }
 812   if (iter.n_yielded() != occupied()) {
 813     tty->print_cr("Yielded disagrees with occupied:");
 814     tty->print_cr("  " SIZE_FORMAT_W(6) " yielded (" SIZE_FORMAT_W(6)
 815                   " coarse, " SIZE_FORMAT_W(6) " fine).",
 816                   iter.n_yielded(),
 817                   iter.n_yielded_coarse(), iter.n_yielded_fine());
 818     tty->print_cr("  " SIZE_FORMAT_W(6) " occ     (" SIZE_FORMAT_W(6)
 819                            " coarse, " SIZE_FORMAT_W(6) " fine).",
 820                   occupied(), occ_coarse(), occ_fine());
 821   }
 822   guarantee(iter.n_yielded() == occupied(),
 823             "We should have yielded all the represented cards.");
 824 }
 825 #endif
 826 
 827 void HeapRegionRemSet::cleanup() {
 828   SparsePRT::cleanup_all();
 829 }
 830 
 831 void HeapRegionRemSet::clear() {
 832   MutexLockerEx x(&_m, Mutex::_no_safepoint_check_flag);
 833   clear_locked();
 834 }
 835 
 836 void HeapRegionRemSet::clear_locked() {
 837   _code_roots.clear();
 838   _other_regions.clear();
 839   assert(occupied_locked() == 0, "Should be clear.");
 840   reset_for_par_iteration();
 841 }
 842 
 843 void HeapRegionRemSet::reset_for_par_iteration() {
 844   _iter_state = Unclaimed;
 845   _iter_claimed = 0;
 846   // It's good to check this to make sure that the two methods are in sync.
 847   assert(verify_ready_for_par_iteration(), "post-condition");
 848 }
 849 
 850 void HeapRegionRemSet::scrub(CardTableModRefBS* ctbs,
 851                              BitMap* region_bm, BitMap* card_bm) {
 852   _other_regions.scrub(ctbs, region_bm, card_bm);
 853 }
 854 
 855 // Code roots support
 856 //
 857 // The code root set is protected by two separate locking schemes
 858 // When at safepoint the per-hrrs lock must be held during modifications
 859 // except when doing a full gc.
 860 // When not at safepoint the CodeCache_lock must be held during modifications.
 861 // When concurrent readers access the contains() function
 862 // (during the evacuation phase) no removals are allowed.
 863 
 864 void HeapRegionRemSet::add_strong_code_root(nmethod* nm) {
 865   assert(nm != NULL, "sanity");
 866   // Optimistic unlocked contains-check
 867   if (!_code_roots.contains(nm)) {
 868     MutexLockerEx ml(&_m, Mutex::_no_safepoint_check_flag);
 869     add_strong_code_root_locked(nm);
 870   }
 871 }
 872 
 873 void HeapRegionRemSet::add_strong_code_root_locked(nmethod* nm) {
 874   assert(nm != NULL, "sanity");
 875   _code_roots.add(nm);
 876 }
 877 
 878 void HeapRegionRemSet::remove_strong_code_root(nmethod* nm) {
 879   assert(nm != NULL, "sanity");
 880   assert_locked_or_safepoint(CodeCache_lock);
 881 
 882   MutexLockerEx ml(CodeCache_lock->owned_by_self() ? NULL : &_m, Mutex::_no_safepoint_check_flag);
 883   _code_roots.remove(nm);
 884 
 885   // Check that there were no duplicates
 886   guarantee(!_code_roots.contains(nm), "duplicate entry found");
 887 }
 888 
 889 void HeapRegionRemSet::strong_code_roots_do(CodeBlobClosure* blk) const {
 890   _code_roots.nmethods_do(blk);
 891 }
 892 
 893 void HeapRegionRemSet::clean_strong_code_roots(HeapRegion* hr) {
 894   _code_roots.clean(hr);
 895 }
 896 
 897 size_t HeapRegionRemSet::strong_code_roots_mem_size() {
 898   return _code_roots.mem_size();
 899 }
 900 
 901 HeapRegionRemSetIterator:: HeapRegionRemSetIterator(HeapRegionRemSet* hrrs) :
 902   _hrrs(hrrs),
 903   _g1h(G1CollectedHeap::heap()),
 904   _coarse_map(&hrrs->_other_regions._coarse_map),
 905   _bosa(hrrs->_bosa),
 906   _is(Sparse),
 907   // Set these values so that we increment to the first region.
 908   _coarse_cur_region_index(-1),
 909   _coarse_cur_region_cur_card(HeapRegion::CardsPerRegion-1),
 910   _cur_card_in_prt(HeapRegion::CardsPerRegion),
 911   _fine_cur_prt(NULL),
 912   _n_yielded_coarse(0),
 913   _n_yielded_fine(0),
 914   _n_yielded_sparse(0),
 915   _sparse_iter(&hrrs->_other_regions._sparse_table) {}
 916 
 917 bool HeapRegionRemSetIterator::coarse_has_next(size_t& card_index) {
 918   if (_hrrs->_other_regions._n_coarse_entries == 0) return false;
 919   // Go to the next card.
 920   _coarse_cur_region_cur_card++;
 921   // Was the last the last card in the current region?
 922   if (_coarse_cur_region_cur_card == HeapRegion::CardsPerRegion) {
 923     // Yes: find the next region.  This may leave _coarse_cur_region_index
 924     // Set to the last index, in which case there are no more coarse
 925     // regions.
 926     _coarse_cur_region_index =
 927       (int) _coarse_map->get_next_one_offset(_coarse_cur_region_index + 1);
 928     if ((size_t)_coarse_cur_region_index < _coarse_map->size()) {
 929       _coarse_cur_region_cur_card = 0;
 930       HeapWord* r_bot =
 931         _g1h->region_at((uint) _coarse_cur_region_index)->bottom();
 932       _cur_region_card_offset = _bosa->index_for(r_bot);
 933     } else {
 934       return false;
 935     }
 936   }
 937   // If we didn't return false above, then we can yield a card.
 938   card_index = _cur_region_card_offset + _coarse_cur_region_cur_card;
 939   return true;
 940 }
 941 
 942 bool HeapRegionRemSetIterator::fine_has_next(size_t& card_index) {
 943   if (fine_has_next()) {
 944     _cur_card_in_prt =
 945       _fine_cur_prt->_bm.get_next_one_offset(_cur_card_in_prt + 1);
 946   }
 947   if (_cur_card_in_prt == HeapRegion::CardsPerRegion) {
 948     // _fine_cur_prt may still be NULL in case if there are not PRTs at all for
 949     // the remembered set.
 950     if (_fine_cur_prt == NULL || _fine_cur_prt->next() == NULL) {
 951       return false;
 952     }
 953     PerRegionTable* next_prt = _fine_cur_prt->next();
 954     switch_to_prt(next_prt);
 955     _cur_card_in_prt = _fine_cur_prt->_bm.get_next_one_offset(_cur_card_in_prt + 1);
 956   }
 957 
 958   card_index = _cur_region_card_offset + _cur_card_in_prt;
 959   guarantee(_cur_card_in_prt < HeapRegion::CardsPerRegion,
 960             "Card index " SIZE_FORMAT " must be within the region", _cur_card_in_prt);
 961   return true;
 962 }
 963 
 964 bool HeapRegionRemSetIterator::fine_has_next() {
 965   return _cur_card_in_prt != HeapRegion::CardsPerRegion;
 966 }
 967 
 968 void HeapRegionRemSetIterator::switch_to_prt(PerRegionTable* prt) {
 969   assert(prt != NULL, "Cannot switch to NULL prt");
 970   _fine_cur_prt = prt;
 971 
 972   HeapWord* r_bot = _fine_cur_prt->hr()->bottom();
 973   _cur_region_card_offset = _bosa->index_for(r_bot);
 974 
 975   // The bitmap scan for the PRT always scans from _cur_region_cur_card + 1.
 976   // To avoid special-casing this start case, and not miss the first bitmap
 977   // entry, initialize _cur_region_cur_card with -1 instead of 0.
 978   _cur_card_in_prt = (size_t)-1;
 979 }
 980 
 981 bool HeapRegionRemSetIterator::has_next(size_t& card_index) {
 982   switch (_is) {
 983   case Sparse: {
 984     if (_sparse_iter.has_next(card_index)) {
 985       _n_yielded_sparse++;
 986       return true;
 987     }
 988     // Otherwise, deliberate fall-through
 989     _is = Fine;
 990     PerRegionTable* initial_fine_prt = _hrrs->_other_regions._first_all_fine_prts;
 991     if (initial_fine_prt != NULL) {
 992       switch_to_prt(_hrrs->_other_regions._first_all_fine_prts);
 993     }
 994   }
 995   case Fine:
 996     if (fine_has_next(card_index)) {
 997       _n_yielded_fine++;
 998       return true;
 999     }
1000     // Otherwise, deliberate fall-through
1001     _is = Coarse;
1002   case Coarse:
1003     if (coarse_has_next(card_index)) {
1004       _n_yielded_coarse++;
1005       return true;
1006     }
1007     // Otherwise...
1008     break;
1009   }
1010   assert(ParallelGCThreads > 1 ||
1011          n_yielded() == _hrrs->occupied(),
1012          "Should have yielded all the cards in the rem set "
1013          "(in the non-par case).");
1014   return false;
1015 }
1016 
1017 void HeapRegionRemSet::reset_for_cleanup_tasks() {
1018   SparsePRT::reset_for_cleanup_tasks();
1019 }
1020 
1021 void HeapRegionRemSet::do_cleanup_work(HRRSCleanupTask* hrrs_cleanup_task) {
1022   _other_regions.do_cleanup_work(hrrs_cleanup_task);
1023 }
1024 
1025 void
1026 HeapRegionRemSet::finish_cleanup_task(HRRSCleanupTask* hrrs_cleanup_task) {
1027   SparsePRT::finish_cleanup_task(hrrs_cleanup_task);
1028 }
1029 
1030 #ifndef PRODUCT
1031 void PerRegionTable::test_fl_mem_size() {
1032   PerRegionTable* dummy = alloc(NULL);
1033 
1034   size_t min_prt_size = sizeof(void*) + dummy->bm()->size_in_words() * HeapWordSize;
1035   assert(dummy->mem_size() > min_prt_size,
1036          "PerRegionTable memory usage is suspiciously small, only has " SIZE_FORMAT " bytes. "
1037          "Should be at least " SIZE_FORMAT " bytes.", dummy->mem_size(), min_prt_size);
1038   free(dummy);
1039   guarantee(dummy->mem_size() == fl_mem_size(), "fl_mem_size() does not return the correct element size");
1040   // try to reset the state
1041   _free_list = NULL;
1042   delete dummy;
1043 }
1044 
1045 void HeapRegionRemSet::test_prt() {
1046   PerRegionTable::test_fl_mem_size();
1047 }
1048 
1049 void HeapRegionRemSet::test() {
1050   os::sleep(Thread::current(), (jlong)5000, false);
1051   G1CollectedHeap* g1h = G1CollectedHeap::heap();
1052 
1053   // Run with "-XX:G1LogRSetRegionEntries=2", so that 1 and 5 end up in same
1054   // hash bucket.
1055   HeapRegion* hr0 = g1h->region_at(0);
1056   HeapRegion* hr1 = g1h->region_at(1);
1057   HeapRegion* hr2 = g1h->region_at(5);
1058   HeapRegion* hr3 = g1h->region_at(6);
1059   HeapRegion* hr4 = g1h->region_at(7);
1060   HeapRegion* hr5 = g1h->region_at(8);
1061 
1062   HeapWord* hr1_start = hr1->bottom();
1063   HeapWord* hr1_mid = hr1_start + HeapRegion::GrainWords/2;
1064   HeapWord* hr1_last = hr1->end() - 1;
1065 
1066   HeapWord* hr2_start = hr2->bottom();
1067   HeapWord* hr2_mid = hr2_start + HeapRegion::GrainWords/2;
1068   HeapWord* hr2_last = hr2->end() - 1;
1069 
1070   HeapWord* hr3_start = hr3->bottom();
1071   HeapWord* hr3_mid = hr3_start + HeapRegion::GrainWords/2;
1072   HeapWord* hr3_last = hr3->end() - 1;
1073 
1074   HeapRegionRemSet* hrrs = hr0->rem_set();
1075 
1076   // Make three references from region 0x101...
1077   hrrs->add_reference((OopOrNarrowOopStar)hr1_start);
1078   hrrs->add_reference((OopOrNarrowOopStar)hr1_mid);
1079   hrrs->add_reference((OopOrNarrowOopStar)hr1_last);
1080 
1081   hrrs->add_reference((OopOrNarrowOopStar)hr2_start);
1082   hrrs->add_reference((OopOrNarrowOopStar)hr2_mid);
1083   hrrs->add_reference((OopOrNarrowOopStar)hr2_last);
1084 
1085   hrrs->add_reference((OopOrNarrowOopStar)hr3_start);
1086   hrrs->add_reference((OopOrNarrowOopStar)hr3_mid);
1087   hrrs->add_reference((OopOrNarrowOopStar)hr3_last);
1088 
1089   // Now cause a coarsening.
1090   hrrs->add_reference((OopOrNarrowOopStar)hr4->bottom());
1091   hrrs->add_reference((OopOrNarrowOopStar)hr5->bottom());
1092 
1093   // Now, does iteration yield these three?
1094   HeapRegionRemSetIterator iter(hrrs);
1095   size_t sum = 0;
1096   size_t card_index;
1097   while (iter.has_next(card_index)) {
1098     HeapWord* card_start =
1099       G1CollectedHeap::heap()->bot_shared()->address_for_index(card_index);
1100     tty->print_cr("  Card " PTR_FORMAT ".", p2i(card_start));
1101     sum++;
1102   }
1103   guarantee(sum == 11 - 3 + 2048, "Failure");
1104   guarantee(sum == hrrs->occupied(), "Failure");
1105 }
1106 #endif