1 /*
   2  * Copyright (c) 2001, 2019, 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 #ifndef SHARE_GC_G1_HEAPREGIONREMSET_HPP
  26 #define SHARE_GC_G1_HEAPREGIONREMSET_HPP
  27 
  28 #include "gc/g1/g1CodeCacheRemSet.hpp"
  29 #include "gc/g1/g1FromCardCache.hpp"
  30 #include "gc/g1/sparsePRT.hpp"
  31 #include "utilities/bitMap.hpp"
  32 
  33 // Remembered set for a heap region.  Represent a set of "cards" that
  34 // contain pointers into the owner heap region.  Cards are defined somewhat
  35 // abstractly, in terms of what the "BlockOffsetTable" in use can parse.
  36 
  37 class G1CollectedHeap;
  38 class G1BlockOffsetTable;
  39 class G1CardLiveData;
  40 class HeapRegion;
  41 class PerRegionTable;
  42 class SparsePRT;
  43 class nmethod;
  44 
  45 // The "_coarse_map" is a bitmap with one bit for each region, where set
  46 // bits indicate that the corresponding region may contain some pointer
  47 // into the owning region.
  48 
  49 // The "_fine_grain_entries" array is an open hash table of PerRegionTables
  50 // (PRTs), indicating regions for which we're keeping the RS as a set of
  51 // cards.  The strategy is to cap the size of the fine-grain table,
  52 // deleting an entry and setting the corresponding coarse-grained bit when
  53 // we would overflow this cap.
  54 
  55 // We use a mixture of locking and lock-free techniques here.  We allow
  56 // threads to locate PRTs without locking, but threads attempting to alter
  57 // a bucket list obtain a lock.  This means that any failing attempt to
  58 // find a PRT must be retried with the lock.  It might seem dangerous that
  59 // a read can find a PRT that is concurrently deleted.  This is all right,
  60 // because:
  61 //
  62 //   1) We only actually free PRT's at safe points (though we reuse them at
  63 //      other times).
  64 //   2) We find PRT's in an attempt to add entries.  If a PRT is deleted,
  65 //      it's _coarse_map bit is set, so the that we were attempting to add
  66 //      is represented.  If a deleted PRT is re-used, a thread adding a bit,
  67 //      thinking the PRT is for a different region, does no harm.
  68 
  69 class OtherRegionsTable {
  70   G1CollectedHeap* _g1h;
  71   Mutex*           _m;
  72 
  73   // These are protected by "_m".
  74   CHeapBitMap _coarse_map;
  75   size_t      _n_coarse_entries;
  76   static jint _n_coarsenings;
  77 
  78   PerRegionTable** _fine_grain_regions;
  79   size_t           _n_fine_entries;
  80 
  81   // The fine grain remembered sets are doubly linked together using
  82   // their 'next' and 'prev' fields.
  83   // This allows fast bulk freeing of all the fine grain remembered
  84   // set entries, and fast finding of all of them without iterating
  85   // over the _fine_grain_regions table.
  86   PerRegionTable * _first_all_fine_prts;
  87   PerRegionTable * _last_all_fine_prts;
  88 
  89   // Used to sample a subset of the fine grain PRTs to determine which
  90   // PRT to evict and coarsen.
  91   size_t        _fine_eviction_start;
  92   static size_t _fine_eviction_stride;
  93   static size_t _fine_eviction_sample_size;
  94 
  95   SparsePRT   _sparse_table;
  96 
  97   // These are static after init.
  98   static size_t _max_fine_entries;
  99   static size_t _mod_max_fine_entries_mask;
 100 
 101   // Requires "prt" to be the first element of the bucket list appropriate
 102   // for "hr".  If this list contains an entry for "hr", return it,
 103   // otherwise return "NULL".
 104   PerRegionTable* find_region_table(size_t ind, HeapRegion* hr) const;
 105 
 106   // Find, delete, and return a candidate PerRegionTable, if any exists,
 107   // adding the deleted region to the coarse bitmap.  Requires the caller
 108   // to hold _m, and the fine-grain table to be full.
 109   PerRegionTable* delete_region_table();
 110 
 111   // link/add the given fine grain remembered set into the "all" list
 112   void link_to_all(PerRegionTable * prt);
 113   // unlink/remove the given fine grain remembered set into the "all" list
 114   void unlink_from_all(PerRegionTable * prt);
 115 
 116   bool contains_reference_locked(OopOrNarrowOopStar from) const;
 117 
 118   size_t occ_fine() const;
 119   size_t occ_coarse() const;
 120   size_t occ_sparse() const;
 121 
 122 public:
 123   // Create a new remembered set. The given mutex is used to ensure consistency.
 124   OtherRegionsTable(Mutex* m);
 125 
 126   template <class Closure>
 127   void iterate(Closure& v);
 128 
 129   // Returns the card index of the given within_region pointer relative to the bottom
 130   // of the given heap region.
 131   static CardIdx_t card_within_region(OopOrNarrowOopStar within_region, HeapRegion* hr);
 132   // Adds the reference from "from to this remembered set.
 133   void add_reference(OopOrNarrowOopStar from, uint tid);
 134 
 135   // Returns whether the remembered set contains the given reference.
 136   bool contains_reference(OopOrNarrowOopStar from) const;
 137 
 138   // Returns whether this remembered set (and all sub-sets) have an occupancy
 139   // that is less or equal than the given occupancy.
 140   bool occupancy_less_or_equal_than(size_t limit) const;
 141 
 142   // Returns whether this remembered set (and all sub-sets) does not contain any entry.
 143   bool is_empty() const;
 144 
 145   // Returns the number of cards contained in this remembered set.
 146   size_t occupied() const;
 147 
 148   static jint n_coarsenings() { return _n_coarsenings; }
 149 
 150   // Returns size of the actual remembered set containers in bytes.
 151   size_t mem_size() const;
 152   // Returns the size of static data in bytes.
 153   static size_t static_mem_size();
 154   // Returns the size of the free list content in bytes.
 155   static size_t fl_mem_size();
 156 
 157   // Clear the entire contents of this remembered set.
 158   void clear();
 159 };
 160 
 161 class PerRegionTable: public CHeapObj<mtGC> {
 162   friend class OtherRegionsTable;
 163 
 164   HeapRegion*     _hr;
 165   CHeapBitMap     _bm;
 166   jint            _occupied;
 167 
 168   // next pointer for free/allocated 'all' list
 169   PerRegionTable* _next;
 170 
 171   // prev pointer for the allocated 'all' list
 172   PerRegionTable* _prev;
 173 
 174   // next pointer in collision list
 175   PerRegionTable * _collision_list_next;
 176 
 177   // Global free list of PRTs
 178   static PerRegionTable* volatile _free_list;
 179 
 180 protected:
 181   PerRegionTable(HeapRegion* hr) :
 182     _hr(hr),
 183     _bm(HeapRegion::CardsPerRegion, mtGC),
 184     _occupied(0),
 185     _next(NULL), _prev(NULL),
 186     _collision_list_next(NULL)
 187   {}
 188 
 189 public:
 190   // We need access in order to union things into the base table.
 191   BitMap* bm() { return &_bm; }
 192 
 193   HeapRegion* hr() const { return OrderAccess::load_acquire(&_hr); }
 194 
 195   jint occupied() const {
 196     // Overkill, but if we ever need it...
 197     // guarantee(_occupied == _bm.count_one_bits(), "Check");
 198     return _occupied;
 199   }
 200 
 201   void init(HeapRegion* hr, bool clear_links_to_all_list);
 202 
 203   inline void add_reference(OopOrNarrowOopStar from);
 204 
 205   inline void add_card(CardIdx_t from_card_index);
 206 
 207   // (Destructively) union the bitmap of the current table into the given
 208   // bitmap (which is assumed to be of the same size.)
 209   void union_bitmap_into(BitMap* bm) {
 210     bm->set_union(_bm);
 211   }
 212 
 213   // Mem size in bytes.
 214   size_t mem_size() const {
 215     return sizeof(PerRegionTable) + _bm.size_in_words() * HeapWordSize;
 216   }
 217 
 218   // Requires "from" to be in "hr()".
 219   bool contains_reference(OopOrNarrowOopStar from) const {
 220     assert(hr()->is_in_reserved(from), "Precondition.");
 221     size_t card_ind = pointer_delta(from, hr()->bottom(),
 222                                     G1CardTable::card_size);
 223     return _bm.at(card_ind);
 224   }
 225 
 226   // Bulk-free the PRTs from prt to last, assumes that they are
 227   // linked together using their _next field.
 228   static void bulk_free(PerRegionTable* prt, PerRegionTable* last) {
 229     while (true) {
 230       PerRegionTable* fl = _free_list;
 231       last->set_next(fl);
 232       PerRegionTable* res = Atomic::cmpxchg(prt, &_free_list, fl);
 233       if (res == fl) {
 234         return;
 235       }
 236     }
 237     ShouldNotReachHere();
 238   }
 239 
 240   static void free(PerRegionTable* prt) {
 241     bulk_free(prt, prt);
 242   }
 243 
 244   // Returns an initialized PerRegionTable instance.
 245   static PerRegionTable* alloc(HeapRegion* hr);
 246 
 247   PerRegionTable* next() const { return _next; }
 248   void set_next(PerRegionTable* next) { _next = next; }
 249   PerRegionTable* prev() const { return _prev; }
 250   void set_prev(PerRegionTable* prev) { _prev = prev; }
 251 
 252   // Accessor and Modification routines for the pointer for the
 253   // singly linked collision list that links the PRTs within the
 254   // OtherRegionsTable::_fine_grain_regions hash table.
 255   //
 256   // It might be useful to also make the collision list doubly linked
 257   // to avoid iteration over the collisions list during scrubbing/deletion.
 258   // OTOH there might not be many collisions.
 259 
 260   PerRegionTable* collision_list_next() const {
 261     return _collision_list_next;
 262   }
 263 
 264   void set_collision_list_next(PerRegionTable* next) {
 265     _collision_list_next = next;
 266   }
 267 
 268   PerRegionTable** collision_list_next_addr() {
 269     return &_collision_list_next;
 270   }
 271 
 272   static size_t fl_mem_size() {
 273     PerRegionTable* cur = _free_list;
 274     size_t res = 0;
 275     while (cur != NULL) {
 276       res += cur->mem_size();
 277       cur = cur->next();
 278     }
 279     return res;
 280   }
 281 
 282   static void test_fl_mem_size();
 283 };
 284 
 285 class HeapRegionRemSet : public CHeapObj<mtGC> {
 286   friend class VMStructs;
 287 
 288 private:
 289   G1BlockOffsetTable* _bot;
 290 
 291   // A set of code blobs (nmethods) whose code contains pointers into
 292   // the region that owns this RSet.
 293   G1CodeRootSet _code_roots;
 294 
 295   Mutex _m;
 296 
 297   OtherRegionsTable _other_regions;
 298 
 299   HeapRegion* _hr;
 300 
 301   void clear_fcc();
 302 
 303 public:
 304   HeapRegionRemSet(G1BlockOffsetTable* bot, HeapRegion* hr);
 305 
 306   // Setup sparse and fine-grain tables sizes.
 307   static void setup_remset_size();
 308 
 309   bool is_empty() const {
 310     return (strong_code_roots_list_length() == 0) && _other_regions.is_empty();
 311   }
 312 
 313   bool occupancy_less_or_equal_than(size_t occ) const {
 314     return (strong_code_roots_list_length() == 0) && _other_regions.occupancy_less_or_equal_than(occ);
 315   }
 316 
 317   // For each PRT in the card (remembered) set call one of the following methods
 318   // of the given closure:
 319   //
 320   // set_full_region_dirty(uint region_idx) - pass the region index for coarse PRTs
 321   // set_bitmap_dirty(uint region_idx, BitMap* bitmap) - pass the region index and bitmap for fine PRTs
 322   // set_cards_dirty(uint region_idx, elem_t* cards, uint num_cards) - pass region index and cards for sparse PRTs
 323   template <class Closure>
 324   inline void iterate_prts(Closure& cl);
 325 
 326   size_t occupied() {
 327     MutexLocker x(&_m, Mutex::_no_safepoint_check_flag);
 328     return occupied_locked();
 329   }
 330   size_t occupied_locked() {
 331     return _other_regions.occupied();
 332   }
 333 
 334   static jint n_coarsenings() { return OtherRegionsTable::n_coarsenings(); }
 335 
 336 private:
 337   enum RemSetState {
 338     Untracked,
 339     Updating,
 340     Complete
 341   };
 342 
 343   RemSetState _state;
 344 
 345   static const char* _state_strings[];
 346   static const char* _short_state_strings[];
 347 public:
 348 
 349   const char* get_state_str() const { return _state_strings[_state]; }
 350   const char* get_short_state_str() const { return _short_state_strings[_state]; }
 351 
 352   bool is_tracked() { return _state != Untracked; }
 353   bool is_updating() { return _state == Updating; }
 354   bool is_complete() { return _state == Complete; }
 355 
 356   void set_state_empty() {
 357     guarantee(SafepointSynchronize::is_at_safepoint() || !is_tracked(), "Should only set to Untracked during safepoint but is %s.", get_state_str());
 358     if (_state == Untracked) {
 359       return;
 360     }
 361     clear_fcc();
 362     _state = Untracked;
 363   }
 364 
 365   void set_state_updating() {
 366     guarantee(SafepointSynchronize::is_at_safepoint() && !is_tracked(), "Should only set to Updating from Untracked during safepoint but is %s", get_state_str());
 367     clear_fcc();
 368     _state = Updating;
 369   }
 370 
 371   void set_state_complete() {
 372     clear_fcc();
 373     _state = Complete;
 374   }
 375 
 376   void add_reference(OopOrNarrowOopStar from, uint tid) {
 377     RemSetState state = _state;
 378     if (state == Untracked) {
 379       return;
 380     }
 381 
 382     uint cur_idx = _hr->hrm_index();
 383     uintptr_t from_card = uintptr_t(from) >> CardTable::card_shift;
 384 
 385     if (G1FromCardCache::contains_or_replace(tid, cur_idx, from_card)) {
 386       assert(contains_reference(from), "We just found " PTR_FORMAT " in the FromCardCache", p2i(from));
 387       return;
 388     }
 389 
 390     _other_regions.add_reference(from, tid);
 391   }
 392 
 393   // The region is being reclaimed; clear its remset, and any mention of
 394   // entries for this region in other remsets.
 395   void clear(bool only_cardset = false);
 396   void clear_locked(bool only_cardset = false);
 397 
 398   // The actual # of bytes this hr_remset takes up.
 399   // Note also includes the strong code root set.
 400   size_t mem_size() {
 401     MutexLocker x(&_m, Mutex::_no_safepoint_check_flag);
 402     return _other_regions.mem_size()
 403       // This correction is necessary because the above includes the second
 404       // part.
 405       + (sizeof(HeapRegionRemSet) - sizeof(OtherRegionsTable))
 406       + strong_code_roots_mem_size();
 407   }
 408 
 409   // Returns the memory occupancy of all static data structures associated
 410   // with remembered sets.
 411   static size_t static_mem_size() {
 412     return OtherRegionsTable::static_mem_size() + G1CodeRootSet::static_mem_size();
 413   }
 414 
 415   // Returns the memory occupancy of all free_list data structures associated
 416   // with remembered sets.
 417   static size_t fl_mem_size() {
 418     return OtherRegionsTable::fl_mem_size();
 419   }
 420 
 421   bool contains_reference(OopOrNarrowOopStar from) const {
 422     return _other_regions.contains_reference(from);
 423   }
 424 
 425   // Routines for managing the list of code roots that point into
 426   // the heap region that owns this RSet.
 427   void add_strong_code_root(nmethod* nm);
 428   void add_strong_code_root_locked(nmethod* nm);
 429   void remove_strong_code_root(nmethod* nm);
 430 
 431   // Applies blk->do_code_blob() to each of the entries in
 432   // the strong code roots list
 433   void strong_code_roots_do(CodeBlobClosure* blk) const;
 434 
 435   void clean_strong_code_roots(HeapRegion* hr);
 436 
 437   // Returns the number of elements in the strong code roots list
 438   size_t strong_code_roots_list_length() const {
 439     return _code_roots.length();
 440   }
 441 
 442   // Returns true if the strong code roots contains the given
 443   // nmethod.
 444   bool strong_code_roots_list_contains(nmethod* nm) {
 445     return _code_roots.contains(nm);
 446   }
 447 
 448   // Returns the amount of memory, in bytes, currently
 449   // consumed by the strong code roots.
 450   size_t strong_code_roots_mem_size();
 451 
 452   static void invalidate_from_card_cache(uint start_idx, size_t num_regions) {
 453     G1FromCardCache::invalidate(start_idx, num_regions);
 454   }
 455 
 456 #ifndef PRODUCT
 457   static void print_from_card_cache() {
 458     G1FromCardCache::print();
 459   }
 460 
 461   static void test();
 462 #endif
 463 };
 464 
 465 #endif // SHARE_GC_G1_HEAPREGIONREMSET_HPP